[TUHS] Excise process from a pipe

[TUHS] Excise process from a pipe

[Noel Chiappa]

    > the downstream process is in the middle of a read call (waiting for
    > more data to be put in the pipe), and it has already computed a pointer
    > to the pipe's inode, and it's looping waiting for that inode to have
    > data.
    > So now I have to regroup and figure out how to deal with that. My most
    > likely approach is to copy the inode data across

So I've had a good look at the pipe code, and it turns out that the simple
hack won't work, for two reasons.

First, the pipe on the _other_ side of the middle process is _also_ probably
in the middle of a write call, and so you can't snarf its inode out from
underneath it. (This whole problem reminds me of 'musical chairs' - I just
want the music to stop so everything will go quiet so I can move things
around! :-)

Second, if the process that wants to close down and do a splice is either the
start or end process, its neighbour is going to go from having a pipe to
having a plain file - and the pipe code knows the inode for a pipe has two
users, etc.

So I think it would be necessary to make non-trivial adjustments to the pipe
and file reading/writing code to make this work; either i) some sort of flag
bit to say 'you've been spliced, take appropriate action' which the pipe code
would have to check on being woken up, and then back out to let the main file
reading/writing code take another crack at it, or ii) perhaps some sort of
non-local goto to forcefully back out the call to readp()/writep(), back to
the start of the read/write sequence.

(Simply terminating the read/write call will not work, I think, because that
will often, AFAICT, return with 0 bytes transferred, which will look like an
EOF, etc; so the I/O will have to be restarted.)


I'm not sure I want to do the work to make this actually work - it's not
clear if anyone is really that interested? And it's not something that I'm
interested in having for my own use.

Anyway, none of this is in any way a problem with the fundamental service
model - it's purely kernel implementation issues.

	Noel

[TUHS] Excise process from a pipe

[Noel Chiappa]

    >> the downstream process is in the middle of a read call (waiting for
    >> more data to be put in the pipe), and it has already computed a pointer
    >> to the pipe's inode, and it's looping waiting for that inode to have
    >> data.

    > I think it would be necessary to make non-trivial adjustments to the
    > pipe and file reading/writing code to make this work; either i) some
    > sort of flag bit to say 'you've been spliced, take appropriate action'
    > which the pipe code would have to check on being woken up, and then
    > back out to let the main file reading/writing code take another crack
    > at it
    > ...
    > I'm not sure I want to do the work to make this actually work - it's
    > not clear if anyone is really that interested? And it's not something
    > that I'm interested in having for my own use.

So I decided that it was silly to put all that work into this, and not get it
to work. I did 'cut a corner', by not handling the case where it's the first
or last process which is bailing (which requires a file-pipe splice, not a
pipe-pipe; the former is more complex); i.e. I was just doing a 'working proof
of concept', not a full implementation.

I used the 'flag bit on the inode' approach; the pipe-pipe case could be dealt
with entirely inside pipe.c/readp(). Here's the added code in readp() (at the
loop start):

	if ((ip->i_flag & ISPLICE) != 0) {
		closei(ip, 0);
		ip = rp->f_inode;
		}

It worked first time!

In more detail, I had written a 'splicetest' program that simply passed input
to its output, looking for a line with a single keyword ("stop"); at that
point, it did a splice() call and exited.  When I did "cat input | splicetest
| cat > output", with appropriate test data in "input", all of the test data
(less the "stop" line) appeared in the output file!

For the first time (AFAIK) a process succesfully departed a pipeline, which
continued to operate! So it is do-able. (If anyone has any interest in the
code, let me know.)

	Noel

[TUHS] Excise process from a pipe

[Noel Chiappa]

    >> From: Doug McIlroy <doug at cs.dartmouth.edu>

    >> The spec below isn't hard: just hook two buffer chains together and
    >> twiddle a couple of file desciptors.

    > In thinking about how to implement it, I was thinking that if there was
    > any buffered data in an output pipe, that the process doing the
    > splice() would wait (inside the splice() system call) on all the
    > buffered data being read by the down-stream process.
    > ...
    > As a side-benefit, if one adopted that line, one wouldn't have to deal
    > with the case (in the middle of the chain) of a pipe-pipe splice with u
    > buffered data in both pipes (where one would have to copy the data
    > across); instead one could just use the exact same code for both cases

So a couple of days ago I suffered a Big Hack Attack and actually wrote the
code for splice() (for V6, of course :-).

It took me a day or so to get 'mostly' running. (I got tripped up by pointer
arithmetic issues in a number of places, because V6 declares just about
_everything_ to be "int *", so e.g. "ip + 1" doesn't produce the right value
for sleep() if ip is declared to be "struct inode *", which is what I did
automatically.)

My code only had one real bug so far (I forgot to mark the user's channels as
closed, which resulted in their file entries getting sub-zero usage counts
when the middle (departing) process exited).


However, now I have run across a real problem: I was just copying the system
file table entry for the middle process' input channel over to the entry for
the downstream's input (so further reads on its part would read the channel
the middle process used to be reading). Copying the data from one entry to
another meant I didn't have to go chase down file table pointers in the other
process' U structure, etc.

Alas, this simple approach doesn't work.

Using the approach I outlined (where the middle channel waits for the
downstream pipe to be empty, so it can discard it and do the splice by
copying the file table entries) doesn't work, because the downstream process
is in the middle of a read call (waiting for more data to be put in the
pipe), and it has already computed a pointer to the pipe's inode, and it's
looping waiting for that inode to have data.

So now I have to regroup and figure out how to deal with that. My most likely
approach is to copy the inode data across (so I don't have to go mess with the
downstream process to get it to go look at another inode), but i) I want to
think about it a bit first, and ii) I have to check that it won't screw
anything else up if I move the inode data to another slot.

	Noel

[TUHS] Excise process from a pipe

[Noel Chiappa]

    > From: Doug McIlroy <doug at cs.dartmouth.edu>

    > The spec below isn't hard: just hook two buffer chains together and
    > twiddle a couple of file desciptors.

How amusing! I was about to send a message with almost the exact same
description - it even had the exact same syntax for the splice() call! A
couple of points from my thoughts which were not covered in your message:


In thinking about how to implement it, I was thinking that if there was any
buffered data in an output pipe, that the process doing the splice() would
wait (inside the splice() system call) on all the buffered data being read by
the down-stream process.

The main point of this is for the case where the up-stream is the head of the
chain (i.e. it's reading from a file), where one more or less has to wait,
because one will want to set the down-streams' file descriptor to point to
the file - but one can't really do that until all the buffered data was
consumed (else it will be lost - one can't exactly put it into the file :-).

As a side-benefit, if one adopted that line, one wouldn't have to deal with
the case (in the middle of the chain) of a pipe-pipe splice with buffered
data in both pipes (where one would have to copy the data across); instead
one could just use the exact same code for both cases, and in that case the
wait would be until the down-stream pipe can simply be discarded.

One thing I couldn't decide is what to do if the upstream is a pipe with
buffered data, and the downstream is a file - does one discard the buffered
data, write it to the file, abort the system call so the calling process can
deal with the buffered data, or what? Perhaps there could be a flag argument
to control the behaviour in such cases.


Speaking of which, I'm not sure I quite grokked this:

    > If file descriptor fd0 is associated with a pipe and fd1 is not, then
    > fd1 is updated to reflect the effect of buffered data for fd0, and the
    > pipe's other descriptor is replaced with a duplicate of fd1.

But what happens to the data? Is it written to the file? (That's the
implication, but it's not stated directly.)

    > The same statement holds when "fd0" is exchanged with "fd1" and "write"
    > is exchanged with "read".

Ditto - what happens to the data? One can't simply stuff it into the input
file? I think the 'wait in the system call until it drains' approach is
better.


Also, it seemed to me that the right thing to do was to bash the entry in the
system-wide file table (i.e. not the specific pointers in the u area). That
would automatically pick up any children.

Finally, there are 'potential' security issues (I say 'potential' because I'm
not sure they're really problems). For instance, suppose that an end process
(i.e. reading/writing a file) has access to that file (e.g. because it
executed a SUID program), but its neighbour process does not. If the end
process wants to go away, should the neighbour process be allowed access to
the file? A 'simple' implementation would do so (since IIRC file permissions
are only checked at open time, not read/write time).


I don't pretend that this is a complete list of issues - just what I managed
to think up while considering the new call.


    > For stdio, of course, one would need fsplice(3), which must flush the
    > in-process buffers--penance for stdio's original sin of said buffering.

Err, why is buffering data in the process a sin? (Or was this just a
humourous aside?)

	Noel

[TUHS] Excise process from a pipe

[Doug McIlroy]

Larry wrote in separate emails

> If you really think that this could be done I'd suggest trying to
> write the man page for the call.

> I already claimed splice(2) back in 1998; the Linux guys did
> implement part of it ...

I began to write the following spec without knowing that Linux had
appropriated the name "splice" for a capability that was in DTSS
over 40 years ago under a more accurate name, "copy". The spec
below isn't hard: just hook two buffer chains together and twiddle
a couple of file desciptors.  For stdio, of course, one would need
fsplice(3), which must flush the in-process buffers--penance for
stdio's original sin of said buffering.

Incidentally, the question is not abstract. I have code that takes
quadratic time because it grows a pipeline of length proportional
to the input, though only a bounded number of the processes are
usefully active at any one time; the rest are cats. Splicing out
the cats would make it linear. Linear approaches that don't need
splice are not nearly as clean.

Doug

SPLICE(2)

SYNOPSIS

int splice(int fd0, int fd1);

DESCRIPTION

Splice connects the source for a reading file descriptor fd0
directly to the destination for a writing file descriptor fd1
and closes both fd0 and fd1. Either the source or the destination
must be another process (via a pipe). Data buffered for fd0 at
the time of splicing follows such data for fd1. If both source
and destination are processes, they become connected by a pipe. If
the source (destination) is a process, the file descriptor
in that process becomes write-only (read-only).

If file descriptor fd0 is associated with a pipe and fd1 is not,
then fd1 is updated to reflect the effect of buffered data for fd0,
and the pipe's other descriptor is replaced with a duplicate of fd1.
The same statement holds when "fd0" is exchanged with "fd1" and
"write" is exchanged with "read".

Splice's effect on any file descriptor propagates to shared file
descriptors in all processes.

NOTES

One file must be a pipe lest the spliced data stream have no
controlling process. It might seem that a socket would suffice,
ceding control to a remote system; but that would allow the
uncontrolled connection file-socket-socket-file.

The provision about a file descriptor becoming either write-only or
read-only sidesteps complications due to read-write file descriptors.

[TUHS] Excise process from a pipe

[Noel Chiappa]

PS: I see I have over-generalized the problem. Doug's original message say "a
process could excise itself from a pipeline". So presumably the initiation
would come from process2 itself, and it would know when it had no
internally-buffered data.

So now we're back to the issue of 'either we need a system call to merge two
pipes into one, or the process has to hang around and turn itself into a cat'.

	Noel

[TUHS] Excise process from a pipe

[Noel Chiappa]

    > From: Larry McVoy <lm at mcvoy.com>

    > Making what you are talking about work is gonna be a mess of buffer
    > management and it's going to be hard to design system calls that would
    > work and still give you reasonable semantics on the pipe. Consider
    > calls that want to know if there is data in the pipe

Oh, I didn't say it would work well, and cleanly! :-) I mean, taking one
element in an existing, operating, chain, and blowing it away, is almost
bound to cause problems.

My previous note was merely to say that the file descriptor/pipe
re-arrangement involved might be easier done with a system call - in fact, now
that I think about it, as someone has already sort of pointed out, without a
system call to merge the two pipes into one, you have to keep the middle
process around, and have it turn into a 'cat'.


Thinking out loud for a moment, though, along the lines you suggest....
Here's one problem - suppose process2 has read some data, but not yet
processed it and output it towards process3, when you go to do the splice.
How would the anything outside the process (be it the OS, or the command
interpreter or whatever is initiating the splice) even detect that, much less
retrieve the data?

Even using a heuristic such as 'wait for process2 to try and read data, at
which point we can assume that it no longer has any internally buffered data,
and it's OK to do the splice' fails, because process2 may have decided it
didn't have a complete semantic unit in hand (e.g. a complete line), and
decided to go back and get the rest of the unit before outputting the
complete, processed semantic unit (i.e. including data it had previously
buffered internally).

And suppose the reads _never_ happen to coincide with the semantic units
being output; i.e. process2 will _always_ have some buffered data inside it,
until the whole chain starts to shut down with EOFs from the first stage?


In short, maybe this problem isn't solvable in the general case. In which
case I guess we're back to your "Every utility that you put in a pipeline
would have to be reworked".

Stages would have to have some way to say 'I am not now holding any buffered
data', and only when that state was true could they be spliced out. Or there
could be some signal defined which means 'go into "not holding any buffered
data" state'. At which point my proposed splice() system call might be some
use... :-)

	Noel

[TUHS] Excise process from a pipe

[Larry McVoy]

On Thu, Jul 10, 2014 at 12:06:58PM -0400, Noel Chiappa wrote:
> Stages would have to have some way to say 'I am not now holding any buffered
> data', and only when that state was true could they be spliced out. Or there
> could be some signal defined which means 'go into "not holding any buffered
> data" state'. At which point my proposed splice() system call might be some
> use... :-)

Heh.  I already claimed splice(2) back in 1998; the Linux guys did implement
part of it but never really carried to the logical end I envisioned:

http://www.mcvoy.com/lm/bitmover/lm/papers/splice.ps
-- 
---
Larry McVoy            	     lm at mcvoy.com             http://www.mcvoy.com/lm 

[TUHS] Excise process from a pipe

[Larry McVoy]

In BitKeeper we've got lots of code that deals with jiggering where
stdout goes.  Making that work on all the Unix variants and Windows has
been, um, challenging.  Making what you are talking about work is gonna
be a mess of buffer management and it's going to be hard to design system
calls that would work and still give you reasonable semantics on the pipe.
Consider calls that want to know if there is data in the pipe followed
by a reconnect.

If you really think that this could be done I'd suggest trying to write
the man page for the call.  I'm not trying to be snarky, in my personal
experience I've found the best way to prove out my own ideas is to try
and document them for other programmers.  If the docs feel like they
make sense then the idea usually has merit.  I don't know how I'd write
the docs for this stuff and have it work with the existing semantics.

On Thu, Jul 10, 2014 at 11:10:21AM -0400, Noel Chiappa wrote:
>     > From: Larry McVoy <lm at mcvoy.com>
> 
>     > Every utility that you put in a pipeline would have to be reworked to
>     > pass file descriptors around
> 
> Unless the whole operation is supported in the OS directly:
> 
> 	if ((pipe1 = process1->stdout) == process2->stdin) &&
> 	   ((pipe2 = process2->stdout) == process3->stdin) {
> 		prepend_buffer_contents(pipe1, pipe2);
> 		process1->stdout = process2->stdout;
> 		kill_pipe(pipe1);
> 		}
> 
> to be invoked from the chain's parent (e.g. shell).
> 
> (The code would probably want to do something with process2's stdin and
> stdout, like close them; I wouldn't have the call kill process2 directly, that
> could be left to the parent, except in the rare

-- 
---
Larry McVoy            	     lm at mcvoy.com             http://www.mcvoy.com/lm 

[TUHS] Excise process from a pipe

[Noel Chiappa]

    > From: Larry McVoy <lm at mcvoy.com>

    > Every utility that you put in a pipeline would have to be reworked to
    > pass file descriptors around

Unless the whole operation is supported in the OS directly:

	if ((pipe1 = process1->stdout) == process2->stdin) &&
	   ((pipe2 = process2->stdout) == process3->stdin) {
		prepend_buffer_contents(pipe1, pipe2);
		process1->stdout = process2->stdout;
		kill_pipe(pipe1);
		}

to be invoked from the chain's parent (e.g. shell).

(The code would probably want to do something with process2's stdin and
stdout, like close them; I wouldn't have the call kill process2 directly, that
could be left to the parent, except in the rare cases where it might have some
use for the spliced-out process.)

	Noel

[TUHS] Excise process from a pipe

[Larry McVoy]

I'm pretty aware of the various flavors of Unix and unless the process 
in question is willing to help I can't see how this could work.

There are system calls for passing file descriptors but you have the 
problem that the pipe itself is a buffer of some size and you'd have
the problem of draining it.

Every utility that you put in a pipeline would have to be reworked
to pass file descriptors around, it would be really unpleasant and
not at all Unix like.

On Thu, Jul 10, 2014 at 08:04:43AM -0400, Doug McIlroy wrote:
> In the suggested answer, the code changes but the process survives.
> 
> I suspect the answer to my original question is no, but I know only a tiny
> fraction of the cumulative API of the extended Unix family.
> 
> Doug
> 
> >> Was there ever a
> >> flavor of Unix in which a process could excise itself
> >> from a pipeline without breaking the pipeline?
> >
> > If in the middle of a pipeline, all I can think of is:
> >
> >       close fd 0 and fd 1
> >       dup() read end of pipe 1 to be stdin (fd 0)
> >       dup() write end of pipe 2 to be stdout (fd 1)
> >       exec("/bin/cat")
> _______________________________________________
> TUHS mailing list
> TUHS at minnie.tuhs.org
> https://minnie.tuhs.org/mailman/listinfo/tuhs

-- 
---
Larry McVoy            	     lm at mcvoy.com             http://www.mcvoy.com/lm 

[TUHS] Excise process from a pipe

[Doug McIlroy]

In the suggested answer, the code changes but the process survives.

I suspect the answer to my original question is no, but I know only a tiny
fraction of the cumulative API of the extended Unix family.

Doug

>> Was there ever a
>> flavor of Unix in which a process could excise itself
>> from a pipeline without breaking the pipeline?
>
> If in the middle of a pipeline, all I can think of is:
>
>       close fd 0 and fd 1
>       dup() read end of pipe 1 to be stdin (fd 0)
>       dup() write end of pipe 2 to be stdout (fd 1)
>       exec("/bin/cat")

[TUHS] Excise process from a pipe

[Doug McIlroy]

In the suggested answer, the code changes but the process survives.

[TUHS] Excise process from a pipe

[Warren Toomey]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1061 bytes --]

>    On Thu, Jul 10, 2014 at 2:52 PM, Warren Toomey <[1]wkt at tuhs.org> wrote:
>      Â  Â  Â  Â  close fd 0 and fd 1
>      Â  Â  Â  Â  dup() read end of pipe 1 to be stdin (fd 0)
>      Â  Â  Â  Â  dup() write end of pipe 2 to be stdout (fd 1)
>      Â  Â  Â  Â  exec("/bin/cat")

On Thu, Jul 10, 2014 at 03:06:11PM +1000, Christopher Vance wrote:
>    Hi, Warren.
>    That still leaves a process, even if it is a relatively lean one.

Hi Chris! Very true.

>    Besides your fd 0 is presumably already the read end of the input pipe,
>    and fd 1 is already the write end of the output pipe. You could
>    probably reduce the whole thing to the last line.

Of course. If the shell set up the pipeline then we only have to exec("cat")
and leave /bin/cat shuffling the data from one pipe-end to the other.

As there are two distinct pipes, each with their own buffers, I can't see
a way of coalescing them into a single pipe without, as Chris suggests,
some kernelly goodness. Indeed, ugliness and complexity kernel-wise!

Cheers, Warren

[TUHS] Excise process from a pipe

[Christopher Vance]

On Thu, Jul 10, 2014 at 2:52 PM, Warren Toomey <wkt at tuhs.org> wrote:

> On Wed, Jul 09, 2014 at 10:49:22PM -0400, Doug McIlroy wrote:
> > It's easy for a process to insert a new process into a
> > pipeline either upstream or downstream. Was there ever a
> > flavor of Unix in which a process could excise itself
> > from a pipeline without breaking the pipeline?
>
> If in the middle of a pipeline, all I can think of is:
>
>         close fd 0 and fd 1
>         dup() read end of pipe 1 to be stdin (fd 0)
>         dup() write end of pipe 2 to be stdout (fd 1)
>         exec("/bin/cat")
>
> Cheers, Warren
> _______________________________________________
> TUHS mailing list
> TUHS at minnie.tuhs.org
> https://minnie.tuhs.org/mailman/listinfo/tuhs
>

Hi, Warren.

That still leaves a process, even if it is a relatively lean one. Besides
your fd 0 is presumably already the read end of the input pipe, and fd 1 is
already the write end of the output pipe. You could probably reduce the
whole thing to the last line.

I don't think Doug's request can be done without some new kernel call (or
other kernelly goodness) to munge file table entries (nomenclature?) for
the process on at least one side (or more likely both) of the self-excisor.
Someone may have done it, since I have heard rumours of some novel hacks,
but it presumably didn't get very far.

Assuming you have pipes on each side, consider what to do with any buffered
data.

-- 
Christopher Vance
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20140710/e50cda86/attachment.html>

[TUHS] Excise process from a pipe

[Dave Horsfall]

On Thu, 10 Jul 2014, Warren Toomey wrote:

> If in the middle of a pipeline, all I can think of is:
> 
> 	close fd 0 and fd 1

My Unix kernel knowledge is a little rusty (shame on me!), but wouldn't 
that generate pipe errors on both sides i.e. EPIPE and the infamous 
ENOTOBACCO?

-- Dave

[TUHS] Excise process from a pipe

[Warren Toomey]

On Wed, Jul 09, 2014 at 10:49:22PM -0400, Doug McIlroy wrote:
> It's easy for a process to insert a new process into a
> pipeline either upstream or downstream. Was there ever a 
> flavor of Unix in which a process could excise itself
> from a pipeline without breaking the pipeline?

If in the middle of a pipeline, all I can think of is:

	close fd 0 and fd 1
	dup() read end of pipe 1 to be stdin (fd 0)
	dup() write end of pipe 2 to be stdout (fd 1)
	exec("/bin/cat")

Cheers, Warren