seekable pipes

seekable pipes

[Frederik Eaton]

Wow, what happened to Ian Turner's "seekable pipes" proposal? 

http://marc.theaimsgroup.com/?l=linux-kernel&m=110153524529112&w=2

I have wanted to propose something very similar. I think it would be a
great way of implementing a lot of functionality that we think of as
belonging to more complicated userspace filesystems. For instance, if
the kernel had seekable pipes then I could write a command that just
serialized the protocol and allowed me to read and write files over an
'ssh' session, with very simple syntax:

some-editor <(ssh-file host:path)
some-editor <(cmd-file ssh host open-file path)

or inside a tar file (maybe reading only), or on an FTP site, etc.

some-editor <(url-file ftp://host:path)

It might even make more sense than the AVFS way of doing things,
because commands can take multiple file arguments:

some-editor <(patched-file file.c file.patch) # writes changes to file.patch

- difficult to do with AVFS file system modules which are "mounted" on
a single base file.

Kernel support could mean support for mmap and exec, which you
couldn't easily get from a library implementation.

Something like this could be the basis and core of a more complete
userspace file system protocol. But since the seekable pipe concept
also has independent applications I think it would be a good thing to
factor out and focus on getting right independently of
namespace-dependent functionality. Plus even without kernel support
for allowing processes to export virtual directories to each other,
seekable pipes would still give shared-library based userspace
filesystems such as AVFS-preload a way to present host processes with
a much more complete file system interface, by solving their mmap and
exec problems.

Ian admits that his idea of a protocol was too simple, since - if you
will allow me to use the terms 'master' and 'slave' - it didn't allow
multiple slaves for one master. And it didn't allow the slave half of
the pipe to write data, which I think would be an important feature;
also, for good random-access performance I think the master should be
able to provide a block of data with an expiration time which is
cached independently of slave seek position.

But aside from that, the protocol need not be complex. Except for the
problem of creating the special file descriptors, the rest could be
done on the master side with read/write (read a request for data,
write a block of data with a description header). Creating the
descriptor pair could be done with an ioctl "promoting" the pipe
descriptors as in Ian's proposal, although since seekable pipes
wouldn't share much in common with regular pipes, the kernel pipe data
structures would probably be created and then destroyed unnecessarily
in this case - ugly if not a performance issue. I guess there are
several other possibilities. Being able to name the slave as with a
devpts-like solution could have advantages but perhaps not enough to
justify the complexity.

I feel that this kind of feature, in some form, could be the shortest
path to a lot of neat applications. What do other people think?

Frederik

-- 
http://ofb.net/~frederik/

Re: seekable pipes

[Bryan Henderson]

I like it.  I like it a lot.

But I'd expect it to do all of the open file operations, not just seek. (A 
seek-only implementation is certainly acceptable, but the structure should 
be for the whole concept).

So it's a light userspace filesystem -- leaving the directories, creating 
and deleting filesystem objects, opening files, and namespace issues to 
another filesystem.  And no buffer cache or page cache involvement.

The idea of doing seeks by using lseek() on both sides seems unnatural to 
me.  A file doesn't magically change its position.  I'd just use ioctls on 
the master side.

This won't work for many of the things you'd like it to because many 
application programs are too smart for their own good.  The proper way to 
determine whether a file is seekable is to try a seek and see what 
happens.  But many of them stat the file and check its type.  We might 
want something really ugly like an ioctl that sets the stat type.

BTW, what you're calling AVFS is I believe what is now known as FUSE and 
has been discussed a lot recently.  Fortunately, most of the difficult 
problems discussed in re FUSE wouldn't apply to these user space files. 
One of them might, if you could set the filesystem object type to regular 
file:  There are programs that look at arbitrary files on the system and 
expect certain things of the file access that could not be guaranteed if a 
user space program were on the other side.  For example, the program might 
expect the access to complete in a reasonable amount of time.


I think many people aren't familiar with Bash process substitution, so 
allow me:

The shell command

  cat <(ls)

creates a process that runs 'ls',  It creates a fifo and opens the write 
side as ls' Standard Output.  It passes e.g. "/proc/self/fd/63" as the 
argument to 'cat', where file descriptor 63 is the fifo that the shell 
created.  Ergo, 'cat' opens and reads the fifo and consequently writes a 
file listing to Standard Output.

This example does not, of course, demonstrate any utility.  But

  diff <(cd old; ls) <(cd new; ls)

does.

--
Bryan Henderson                     IBM Almaden Research Center
San Jose CA                         Filesystems 

Re: seekable pipes

[x]

All,

I set this project aside when I realized I had bit off
more than I could chew. My original idea was simply to
be able to feed a pipe to any program that expected a
file, and have it just work. In particular, I wanted
to be able to feed a Postgres large-file to a
multimedia player.

I took this off the burner primarily because of the
necessity of handling multiple readers (or clients).
You suggest this as desirable, but in fact it's a
requirement, because the client can fork, and you have
to be able to handle that on both sides. Which makes
things a lot messier.

Given all this, I agree with Bryan that this makes
more sense when done with IOCTLs on the server side.
But the introduction of multiple readers brings in
concurrency, which is not easy at all. In particular,
my original idea allowed the kernel to buffer some
amount of data, just like a regular pipe. But if there
are multiple clients with read/write capability,
you're basically forced to engage in substantial
quantities of trickery, or else pass every client
system call over to the server, and wait for the
response. Not good.

All that said, I'm happy to dedicate my meager
intellectual resources to this project, but I think
the amount of hackery required to do this right is
probably beyond me.

All the best,

--Ian Turner

--- Frederik Eaton <frederik@a5.repetae.net> wrote:

> Wow, what happened to Ian Turner's "seekable pipes"
> proposal? 
> 
>
http://marc.theaimsgroup.com/?l=linux-kernel&m=110153524529112&w=2
> 
> I have wanted to propose something very similar. I
> think it would be a
> great way of implementing a lot of functionality
> that we think of as
> belonging to more complicated userspace filesystems.
> For instance, if
> the kernel had seekable pipes then I could write a
> command that just
> serialized the protocol and allowed me to read and
> write files over an
> 'ssh' session, with very simple syntax:
> 
> some-editor <(ssh-file host:path)
> some-editor <(cmd-file ssh host open-file path)
> 
> or inside a tar file (maybe reading only), or on an
> FTP site, etc.
> 
> some-editor <(url-file ftp://host:path)
> 
> It might even make more sense than the AVFS way of
> doing things,
> because commands can take multiple file arguments:
> 
> some-editor <(patched-file file.c file.patch) #
> writes changes to file.patch
> 
> - difficult to do with AVFS file system modules
> which are "mounted" on
> a single base file.
> 
> Kernel support could mean support for mmap and exec,
> which you
> couldn't easily get from a library implementation.
> 
> Something like this could be the basis and core of a
> more complete
> userspace file system protocol. But since the
> seekable pipe concept
> also has independent applications I think it would
> be a good thing to
> factor out and focus on getting right independently
> of
> namespace-dependent functionality. Plus even without
> kernel support
> for allowing processes to export virtual directories
> to each other,
> seekable pipes would still give shared-library based
> userspace
> filesystems such as AVFS-preload a way to present
> host processes with
> a much more complete file system interface, by
> solving their mmap and
> exec problems.
> 
> Ian admits that his idea of a protocol was too
> simple, since - if you
> will allow me to use the terms 'master' and 'slave'
> - it didn't allow
> multiple slaves for one master. And it didn't allow
> the slave half of
> the pipe to write data, which I think would be an
> important feature;
> also, for good random-access performance I think the
> master should be
> able to provide a block of data with an expiration
> time which is
> cached independently of slave seek position.
> 
> But aside from that, the protocol need not be
> complex. Except for the
> problem of creating the special file descriptors,
> the rest could be
> done on the master side with read/write (read a
> request for data,
> write a block of data with a description header).
> Creating the
> descriptor pair could be done with an ioctl
> "promoting" the pipe
> descriptors as in Ian's proposal, although since
> seekable pipes
> wouldn't share much in common with regular pipes,
> the kernel pipe data
> structures would probably be created and then
> destroyed unnecessarily
> in this case - ugly if not a performance issue. I
> guess there are
> several other possibilities. Being able to name the
> slave as with a
> devpts-like solution could have advantages but
> perhaps not enough to
> justify the complexity.
> 
> I feel that this kind of feature, in some form,
> could be the shortest
> path to a lot of neat applications. What do other
> people think?
> 
> Frederik
> 
> -- 
> http://ofb.net/~frederik/
> 



		
__________________________________ 
Discover Yahoo! 
Stay in touch with email, IM, photo sharing and more. Check it out! 
http://discover.yahoo.com/stayintouch.html

Re: seekable pipes

[Frederik Eaton]

On Tue, Jun 07, 2005 at 01:31:21PM -0700, Bryan Henderson wrote:
> I like it.  I like it a lot.

Good!

> But I'd expect it to do all of the open file operations, not just seek. (A 
> seek-only implementation is certainly acceptable, but the structure should 
> be for the whole concept).

Like ... ioctl, flock? What else isn't implementable in terms of read,
write, seek?

> The idea of doing seeks by using lseek() on both sides seems unnatural to 
> me.  A file doesn't magically change its position.  I'd just use ioctls on 
> the master side.

I guess I agree about lseek(); I'd considered ioctls but I thought the
advantage of a stream-based protocol using 'read' and 'write' would be
that it would be easy to forward over network connections, etc.

> This won't work for many of the things you'd like it to because many 
> application programs are too smart for their own good.  The proper way to 
> determine whether a file is seekable is to try a seek and see what 
> happens.  But many of them stat the file and check its type.  We might 
> want something really ugly like an ioctl that sets the stat type.

The stat type for <() files is "character special" - such files are
usually seekable. In any case, emacs and vim are cool. If an
application doesn't work because of what you describe, then it would
also have problems with other uses of that shell syntax, so I think
it's not a big issue for us.

On Tue, Jun 07, 2005 at 02:56:14PM -0700, x wrote:
...
> Given all this, I agree with Bryan that this makes
> more sense when done with IOCTLs on the server side.
> But the introduction of multiple readers brings in
> concurrency, which is not easy at all. In particular,
> my original idea allowed the kernel to buffer some
> amount of data, just like a regular pipe. But if there
> are multiple clients with read/write capability,
> you're basically forced to engage in substantial
> quantities of trickery, or else pass every client
> system call over to the server, and wait for the
> response. Not good.

My proposal involved buffering too. I said "for good random-access
performance I think the master should be able to provide a block of
data with an expiration time which is cached independently of slave
seek position." Why wouldn't this work?

> All that said, I'm happy to dedicate my meager
> intellectual resources to this project, but I think
> the amount of hackery required to do this right is
> probably beyond me.

I'm not sure if I would be qualified to work on it either, last time I
looked inside the kernel was a long time ago, and I'm busy. Is there a
wiki where we could work out a specification in case someone comes
along who decides it would make a good project?

Frederik

> --- Frederik Eaton <frederik@a5.repetae.net> wrote:
> 
> > Wow, what happened to Ian Turner's "seekable pipes"
> > proposal? 
> > 
> >
> http://marc.theaimsgroup.com/?l=linux-kernel&m=110153524529112&w=2

> > I have wanted to propose something very similar. I think it would
> > be a great way of implementing a lot of functionality that we
> > think of as belonging to more complicated userspace filesystems.
> > For instance, if the kernel had seekable pipes then I could write
> > a command that just serialized the protocol and allowed me to read
> > and write files over an 'ssh' session, with very simple syntax:

> > some-editor <(ssh-file host:path)
> > some-editor <(cmd-file ssh host open-file path)

> > or inside a tar file (maybe reading only), or on an FTP site, etc.

> > some-editor <(url-file ftp://host:path)

> > It might even make more sense than the AVFS way of doing things,
> > because commands can take multiple file arguments:

> > some-editor <(patched-file file.c file.patch) #
> > writes changes to file.patch

> > - difficult to do with AVFS file system modules which are
> > "mounted" on a single base file.

> > Kernel support could mean support for mmap and exec, which you
> > couldn't easily get from a library implementation.

> > Something like this could be the basis and core of a more complete
> > userspace file system protocol. But since the seekable pipe
> > concept also has independent applications I think it would be a
> > good thing to factor out and focus on getting right independently
> > of namespace-dependent functionality. Plus even without kernel
> > support for allowing processes to export virtual directories to
> > each other, seekable pipes would still give shared-library based
> > userspace filesystems such as AVFS-preload a way to present host
> > processes with a much more complete file system interface, by
> > solving their mmap and exec problems.

> > Ian admits that his idea of a protocol was too simple, since - if
> > you will allow me to use the terms 'master' and 'slave' - it
> > didn't allow multiple slaves for one master. And it didn't allow
> > the slave half of the pipe to write data, which I think would be
> > an important feature; also, for good random-access performance I
> > think the master should be able to provide a block of data with an
> > expiration time which is cached independently of slave seek
> > position.
> > 
> > But aside from that, the protocol need not be complex. Except for
> > the problem of creating the special file descriptors, the rest
> > could be done on the master side with read/write (read a request
> > for data, write a block of data with a description header).
> > Creating the descriptor pair could be done with an ioctl
> > "promoting" the pipe descriptors as in Ian's proposal, although
> > since seekable pipes wouldn't share much in common with regular
> > pipes, the kernel pipe data structures would probably be created
> > and then destroyed unnecessarily in this case - ugly if not a
> > performance issue. I guess there are several other possibilities.
> > Being able to name the slave as with a devpts-like solution could
> > have advantages but perhaps not enough to justify the complexity.
> > 
> > I feel that this kind of feature, in some form,
> > could be the shortest
> > path to a lot of neat applications. What do other
> > people think?
> > 
> > Frederik
> > 
> > -- 
> > http://ofb.net/~frederik/
> > 
> 
> 
> 
> 		
> __________________________________ 
> Discover Yahoo! 
> Stay in touch with email, IM, photo sharing and more. Check it out! 
> http://discover.yahoo.com/stayintouch.html
> -
> To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

-- 
http://ofb.net/~frederik/

Re: seekable pipes

[Bryan Henderson]

>> But I'd expect it to do all of the open file operations, not just seek. 
(A 
>> seek-only implementation is certainly acceptable, but the structure 
should 
>> be for the whole concept).
>
>Like ... ioctl, flock? What else isn't implementable in terms of read,
>write, seek?

I guess most of the open file operations can't be moved to user space 
(mmap, readv, etc.).  Looking at the list (of VFS operations), I see read, 
write, seek, ioctl, flock, lock, fsync, and flush that could sensibly be 
transported across a pipe.

>The stat type for <() files is "character special"

When I do it, it's "FIFO" (st_mode contains S_IFIFO).

>such files are usually seekable.

Really?  Character device special files are usually not in my experience: 
terminals, tapes, serial ports.

>In any case, emacs and vim are cool.

You can edit a device special file?  Emacs gives me "file cannot be read" 
on various pipe and character device special files I tried.  strace shows 
that it does an lstat(), then gives up.

--
Bryan Henderson                     IBM Almaden Research Center
San Jose CA                         Filesystems

Re: seekable pipes

[Frederik Eaton]

> >The stat type for <() files is "character special"
> 
> When I do it, it's "FIFO" (st_mode contains S_IFIFO).
> 
> >such files are usually seekable.
> 
> Really?  Character device special files are usually not in my experience: 
> terminals, tapes, serial ports.
> 
> >In any case, emacs and vim are cool.
> 
> You can edit a device special file?  Emacs gives me "file cannot be read" 
> on various pipe and character device special files I tried.  strace shows 
> that it does an lstat(), then gives up.

I stand corrected. Sorry. Thanks for verifying. I was testing on
/proc/self/fd/XX after opening it with 'exec', obviously not the same.
So this is a real problem then.

I guess the issue is that the shell has to insert a fifo at the end of
the pipeline in a <() construct in order to get something that can be
read from when written to?

Maybe the solution would be to introduce a <>() construct which uses a
seekable pipe instead of a fifo at the end? And that would suggest a
new version of "|" as well.

Or your suggestion of using an ioctl to change the file type... If a
seekable pipe were created by "upgrading" a regular one then perhaps
this could automatically change the file type at the slave to "regular
file" (from "fifo"). This way the shell wouldn't have to know about
seekable pipes, which would be good. But I can't see how to get around
the race condition where the slave side of the pipe might do a 'stat'
call before the master side has had a chance to change the file type.
It could be possible to have 'stat' block until the master has written
something, but that might introduce deadlocks in existing programs.

Frederik

-- 
http://ofb.net/~frederik/

Re: seekable pipes

[Bryan Henderson]

When you first described the concept, I was thinking of named pipes, which 
someone would separately create.  It's still good for that.  For 
shell-made pipes
(| and <>()), though, I agree -- the shell has to change.  I don't see any 
other reasonable way.

--
Bryan Henderson                     IBM Almaden Research Center
San Jose CA                         Filesystems 

Re: seekable pipes

[x]

Actually, I don't see how it matters either way. Named
pipes get set up in pretty much the same way as
anonymous ones, except the two processes don't have to
be related. But the point is that the seekability of
the pipe is essentially a property of the reader of
that pipe, not the writer -- thus one can imagine
being able to do:
$ command_that_understands_seekable_pipes |
command_that_requires_seekable_stdin
without the second command or the shell having to know
anything in particular about the seekable pipes API. 

One can also imagine a special command, seekcat, which
takes unseekable stdin, and buffers it to create a
seekable stdout.

--- Bryan Henderson <hbryan@us.ibm.com> wrote:

> When you first described the concept, I was thinking
> of named pipes, which 
> someone would separately create.  It's still good
> for that.  For 
> shell-made pipes
> (| and <>()), though, I agree -- the shell has to
> change.  I don't see any 
> other reasonable way.
> 
> --
> Bryan Henderson                     IBM Almaden
> Research Center
> San Jose CA                         Filesystems 
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 

Re: seekable pipes

[Bryan Henderson]

>Actually, I don't see how it matters either way. Named
>pipes get set up in pretty much the same way as
>anonymous ones, except the two processes don't have to
>be related.

It's the fact that the two processes don't have to be related that is 
crucial.  Maybe worded better:  It's the fact that someone who knows about 
seekable pipes can synchronize the process that makes the pipe seekable 
with the process that needs it to be seekable.  In the anonymous case 
(more precisely, the case of the anonymous pipe generated and deployed by 
a seekable-pipe-agnostic program such as Bash), you can't make sure the 
guy who makes the pipe seekable does so before the guy who needs it to be 
seekable notices that it's not.  In the named case, the user can make sure 
he doesn't start the process that needs the pipe to be seekable until the 
process that makes it seekable has done so.

>one can imagine
>being able to do:
>$ command_that_understands_seekable_pipes |
>command_that_requires_seekable_stdin
>without the second command or the shell having to know
>anything in particular about the seekable pipes API. 

If you mean without making Bash seekable-pipe-aware, then 
"command_that_requires_seekable_stdin" might try to seek (or conclude from 
its S_IFIFO mode that it isn't seekable) before 
"command_that_understands_seekable_pipes" makes the seek possible (or 
makes sure S_IFIFO isn't set).

By the way, I don't think reader vs writer is what we care about.  It's 
what we've been calling master vs slave (from pseudo-tty terminology), and 
would probably better be termed client vs server.  The client is the 
program that thinks he's looking at a conventional file, so he can seek, 
read, and write.  The server is the guy who knows it's a special seekable 
pipe file and whose job it is to make the client see a conventional file.

--
Bryan Henderson                     IBM Almaden Research Center
San Jose CA                         Filesystems 

Re: seekable pipes

[x]

> In
> the anonymous case 
> (more precisely, the case of the anonymous pipe
> generated and deployed by 
> a seekable-pipe-agnostic program such as Bash), you
> can't make sure the 
> guy who makes the pipe seekable does so before the
> guy who needs it to be 
> seekable notices that it's not.

OK. This can of course be circumvented by doing
$ command_that_understands_seekable_pipes |
(command_that_checks_stdin;
command_that_requires_seekable_stdin)

But I see how this is something best done in the
shell.

In any case, you'd need some kind of ioctl to ask the
kernel to wait for the other end of the pipe to become
seekable (or be written or closed).

> The client is the 
> program that thinks he's looking at a conventional
> file, so he can seek, 
> read, and write.  The server is the guy who knows
> it's a special seekable 
> pipe file and whose job it is to make the client see
> a conventional file.

That's fine; we have no disagreement there. But I'm
not sure it's correct to return S_ISREG; Seems to me
of the two seekable file types (regular and block
device), block device is closer to the truth. I was
planning to leave the type as S_IFIFO in my original
plan, but I see how that's problematic.

--Ian


		
__________________________________ 
Do you Yahoo!? 
Read only the mail you want - Yahoo! Mail SpamGuard. 
http://promotions.yahoo.com/new_mail 

Re: seekable pipes

[Jeff Anderson-Lee]

x wrote:

>>In
>>the anonymous case 
>>(more precisely, the case of the anonymous pipe
>>generated and deployed by 
>>a seekable-pipe-agnostic program such as Bash), you
>>can't make sure the 
>>guy who makes the pipe seekable does so before the
>>guy who needs it to be 
>>seekable notices that it's not.
>>    
>>
>
>OK. This can of course be circumvented by doing
>$ command_that_understands_seekable_pipes |
>(command_that_checks_stdin;
>command_that_requires_seekable_stdin)
>
>But I see how this is something best done in the
>shell.
>
>In any case, you'd need some kind of ioctl to ask the
>kernel to wait for the other end of the pipe to become
>seekable (or be written or closed).
>
To paraphrase: "the wonderful things about shells is that there are so 
many to choose from".  However one doesn't need to reinvent (or retool) 
the entire wheel/shell industry to get started.  What about just 
starting with a simple "one line" seek-in command that can be called in 
such cases as required?  If it becomes used enough, shell developers 
will eventually absorb it as they did with "test" and "echo", etc.

The syntax could be something like:

$ command_to_manage_seekable_stdout | seek-in [--] 
command_to_use_seekable_stdin

Where seek-in pauses briefly to allow the first command to convert the 
pipe to seekable mode before execing its arguments.  The shell variable 
parsing and other redirection is inherited from (managed by) the 
surrounding shell.  An optional time-out might prevent an infinite wait 
if the first command never converted the pipe.

Jeff Anderson-Lee

Re: seekable pipes

[Bryan Henderson]

>$ command_to_manage_seekable_stdout | seek-in [--] 
>command_to_use_seekable_stdin

I think that's a great idea.  Of course, I'd like to see a program more 
general than this example demonstrates:  one that negotiates general file 
semantics for both Standard Input and Standard Output.

Now do you have an idea for the process substitution case?
I.e. command_to_use_seekable_named_file <(command_to_implement_file) .

There are probably more examples where that's needed than where the | 
thing is needed, because I think the programs that expect advanced 
functions such as seek from files tend to open the files themselves, as 
opposed to getting them pre-opened as stdin or stdout.  E.g. editors.

>An optional time-out might prevent an infinite wait 
>if the first command never converted the pipe.

That would be out of place.  The concept of giving up on something because 
it's taken too much wall clock time is quite complex and not specific to 
setting up of seekable pipes, so should be done at a higher level. SIGALRM 
is good for that.

--
Bryan Henderson                               San Jose California
IBM Almaden Research Center                   Filesystems

Re: seekable pipes

[Frederik Eaton]

On Tue, Jun 21, 2005 at 10:47:22AM -0700, Bryan Henderson wrote:
> When you first described the concept, I was thinking of named pipes, which 
> someone would separately create.  It's still good for that.  For 
> shell-made pipes
> (| and <>()), though, I agree -- the shell has to change.  I don't see any 
> other reasonable way.

OK, that you agree is a good sign. Maybe I shouldn't have mentioned
"|", though. I think it's pretty obvious that the great majority of
commands that expect seekable input take it in the form of a file name
argument and not stdin, so probably only <>() is needed. And once
kernel support for seekable pipes is available it shouldn't be very
hard to extend the shells. That syntax is a parse error in both bash
and zsh, by the way, so I think it could be backward compatible...

Frederik

-- 
http://ofb.net/~frederik/