FIFO files
Hi all,
I recently encountered a need for such a contraption as file-backed FIFOs. These are files where one process can append records at one end, and one other process can read records from the beginning of the file, chopping off the head of the file once it's not needed anymore. As I had to implement something right now on existing systems, I worked around the general absence for such a facility, but still, I'm wondering how difficult it would to write a reiserfs4 plug-in which would allow one to do the equivalent of a truncate() but truncating what's between the position 0 and the current cursor (effectively shifting all subsequent file positions), rather than truncating what's between the cursor and the end of file. (network considerations are explicitly out of the scope of this musing)
-- Cyrille
Hi Cyrille,
Quoted 6 lines · Cyrille Chepelov
I recently encountered a need for such a contraption as file-backed FIFOs. These are files where one process can append records at one end, and one other process can read records from the beginning of the file, chopping off the head of the file once it's not needed anymore. As I had to implement something right now on existing systems, I worked around the general absence
This facility has been present in linux for years. Just google for "sparse files".
Carl-Daniel
Signature · 1 line
http://www.hailfinger.org/
Quoted 13 lines · Carl-Daniel Hailfinger
Hi Cyrille,
Quoted 7 lines · Cyrille Chepelov
I recently encountered a need for such a contraption as file-backed FIFOs. These are files where one process can append records at one end, and one other process can read records from the beginning of the file, chopping off the head of the file once it's not needed anymore. As I had to implement something right now on existing systems, I worked around the general absence
Quoted 6 lines
This facility has been present in linux for years. Just google for "sparse files".
Carl-Daniel
No, he is resetting the location of the first byte of the file.
Signature · 1 line
Hans
Quoted 10 lines · Hans Reiser
Quoted 9 lines · Carl-Daniel Hailfinger
Quoted 6 lines · Cyrille Chepelov
I recently encountered a need for such a contraption as file-backed
FIFOs. These are files where one process can append records at one
end, and one other process can read records from the beginning of the file, chopping off the head of the file once it's not needed anymore. As I had to implement something right now on existing systems, I worked around the general absence
Quoted 4 lines
Quoted 2 lines
This facility has been present in linux for years. Just google for "sparse files".
No, he is resetting the location of the first byte of the file.
Yes, but if I understood Cyrille correctly, her/his(?) needs should be completely satisfied by sparse files.
One process can append records at the end, and one other process can read records from the beginning of the file, marking the read data empty. The disk usage is the same as with Cyrille's solution, but the races are avoided. The only reason I know for wanting to chop off the head of a file is trying to keep the file small.
Carl-Daniel
Hello!
Quoted 4 lines · Carl-Daniel Hailfinger
Yes, but if I understood Cyrille correctly, her/his(?) needs should be completely satisfied by sparse files.
One process can append records at the end, and one other process can read records from the beginning of the file, marking the read data empty. The
Hm, I am sorry, but this part is unclear.
I do not remember any API to create holes in existing files in place of already present data.
Bye,
Oleg
Quoted 11 lines · Oleg Drokin
Hello!
Quoted 4 lines · Carl-Daniel Hailfinger
Yes, but if I understood Cyrille correctly, her/his(?) needs should be completely satisfied by sparse files.
One process can append records at the end, and one other process can read records from the beginning of the file, marking the read data empty. TheHm, I am sorry, but this part is unclear.
I do not remember any API to create holes in existing files in place of already present data.
There isn't one.
XFS uses an ioctl to punch holes, dm_punch_hole, but it's prototype is specific to XDSM.
Once multiple filesystems implement the same functionality it makes sense to have a common interface - maybe a new entry in struct inode_operations, and a corresponding systemcall?
Something like:
int punch_hole(const char *path, off_t offset, size_t len); int fpunch_hole(int fd, off_t offset, size_t len);
The reader of the file would have to punch the holes after reading the data. IMHO punch_hole should not "move" the contents of the file, so the data is still available at the same offsets. If one rather would like the data to be available at the beginning of the file at all times something else is needed, maybe:
int truncate_start(const char *path, off_t offset); int ftruncate_start(int fd, off_t offset);
that truncates the beginning of the file, moving the data from pos offset to pos 0.
But punch_hole is much more generic, and could be useful in cases like HSM and others. Basicly I think punch_hole is just something missing from the linux VFS - logically it should be there. It should be relatively easy to implement on all filesystems supporting sparse files, as the end result is the same.
Truncate_start is another beast. One some filesystems like ext2/3 it would not be possible to implement it effectively for large files, and there are problems with offsets that are not multiple of the blocksize.
Signature · 2 lines
Ragnar Kjørstad Zet.no
It might be more appropriate to continue discussing this at linux-fsdevel.
Quoted 21 lines · Ragnar Kjørstad
Quoted 4 lines · Oleg Drokin
Hello!
On Tue, Jun 17, 2003 at 07:00:25PM +0200, Carl-Daniel Hailfinger wrote:
Quoted 8 lines
Quoted 4 lines
Yes, but if I understood Cyrille correctly, her/his(?) needs should be completely satisfied by sparse files.
One process can append records at the end, and one other process can read records from the beginning of the file, marking the read data empty. TheHm, I am sorry, but this part is unclear.
I do not remember any API to create holes in existing files in place of already present data.There isn't one.
XFS uses an ioctl to punch holes,
dm_punch_hole, but it's prototype is specific to XDSM.
Quoted 7 lines
Once multiple filesystems implement the same functionality it makes sense to have a common interface - maybe a new entry in struct
inode_operations, and a corresponding systemcall?Something like:
intpunch_hole(const char *path, off_t offset, size_t len); intfpunch_hole(int fd, off_t offset, size_t len);
make_hole or zap_range would be alternative names.
Quoted 19 lines
The reader of the file would have to punch the holes after reading the data. IMHO
punch_holeshould not "move" the contents of the file, so the data is still available at the same offsets. If one rather would like the data to be available at the beginning of the file at all times something else is needed, maybe:int
truncate_start(const char *path, off_t offset); intftruncate_start(int fd, off_t offset);that truncates the beginning of the file, moving the data from pos offset to pos 0.
But
punch_holeis much more generic, and could be useful in cases like HSM and others. Basicly I thinkpunch_holeis just something missing from the linux VFS - logically it should be there. It should be relatively easy to implement on all filesystems supporting sparse files, as the end result is the same.
Quoted 3 lines
Truncate_startis another beast. One some filesystems like ext2/3 it would not be possible to implement it effectively for large files, and there are problems with offsets that are not multiple of the blocksize.
Regards,
Carl-Daniel
Quoted 71 lines · Carl-Daniel Hailfinger
It might be more appropriate to continue discussing this at linux-fsdevel.
Quoted 26 lines · Ragnar Kjørstad
Quoted 12 lines · Oleg Drokin
Hello!
Quoted 6 lines · Carl-Daniel Hailfinger
Yes, but if I understood Cyrille correctly, her/his(?) needs should be completely satisfied by sparse files.
One process can append records at the end, and one other process can read records from the beginning of the file, marking the read data empty. TheQuoted 5 lines
Hm, I am sorry, but this part is unclear.
I do not remember any API to create holes in existing files in place of already present data.There isn't one.
XFS uses an ioctl to punch holes,
dm_punch_hole, but it's prototype is specific to XDSM.Quoted 8 lines
Once multiple filesystems implement the same functionality it makes sense to have a common interface - maybe a new entry in struct
inode_operations, and a corresponding systemcall?Something like:
intpunch_hole(const char *path, off_t offset, size_t len); intfpunch_hole(int fd, off_t offset, size_t len);
make_holeorzap_rangewould be alternative names.Quoted 19 lines
The reader of the file would have to punch the holes after reading the data. IMHO
punch_holeshould not "move" the contents of the file, so the data is still available at the same offsets. If one rather would like the data to be available at the beginning of the file at all times something else is needed, maybe:int
truncate_start(const char *path, off_t offset); intftruncate_start(int fd, off_t offset);that truncates the beginning of the file, moving the data from pos offset to pos 0.
But
punch_holeis much more generic, and could be useful in cases like HSM and others. Basicly I thinkpunch_holeis just something missing from the linux VFS - logically it should be there. It should be relatively easy to implement on all filesystems supporting sparse files, as the end result is the same.Quoted 5 lines
Truncate_startis another beast. One some filesystems like ext2/3 it would not be possible to implement it effectively for large files, and there are problems with offsets that are not multiple of the blocksize.
Quoted 7 lines
Regards,
Carl-Daniel
I am generally friendly to patches to punch holes in reiser4 files if anyone finds the time to write such a thing (perhaps filename/..punch/start/length).
Signature · 1 line
Hans
Quoted 11 lines · Carl-Daniel Hailfinger
Quoted 11 lines
Quoted 2 lines
I do not remember any API to create holes in existing files in place of already present data.
There isn't one.
XFS uses an ioctl to punch holes,
dm_punch_hole, but it's prototype is specific to XDSM.Once multiple filesystems implement the same functionality it makes sense to have a common interface - maybe a new entry in struct
inode_operations, and a corresponding systemcall?
I want to implement this for JFFS2 but refused to do it with an ioctl; it can be done through something non-fs-specific or not at all. As soon as there's a non-bletcherous way to expose it to the user, I'll be implementing it.
Signature · 1 line
dwmw2
Quoted 4 lines · David Woodhouse
I want to implement this for JFFS2 but refused to do it with an ioctl; it can be done through something non-fs-specific or not at all. As soon as there's a non-bletcherous way to expose it to the user, I'll be implementing it.
irix uses an fcntl to do it, but i see no reason to copy bad interface design. a new syscall would seem appropriate.
has anyone analysed this for races? are they the same as the ones for truncate? (i suspect they aren't). what are the semantics of another thread or process reading from a block that's been punched out? what are the semantics of another thread or process writing to a block that gets punched out? what are the semantics of another thread or process that has this region of the file mmaped? what are the semantics if this thread has it mmaped? what if two threads try to punch out overlapping regions simultaneously? what if a region is being truncated and punched out at the same time?
Signature · 3 lines
"It's not Hollywood. War is real, war is primarily not about defeat or victory, it is about death. I've seen thousands and thousands of dead bodies. Do you think I want to have an academic debate on this subject?" -- Robert Fisk
Quoted 9 lines · Matthew Wilcox
has anyone analysed this for races? are they the same as the ones for truncate? (i suspect they aren't). what are the semantics of another thread or process reading from a block that's been punched out? what are the semantics of another thread or process writing to a block that gets punched out? what are the semantics of another thread or process that has this region of the file mmaped? what are the semantics if this thread has it mmaped? what if two threads try to punch out overlapping regions simultaneously? what if a region is being truncated and punched out at the same time?
In what way are they different from that of truncate?
It seems to me that punching a hole in a file is actually easier than truncating a file as we don't have to change the length. The issues of mmap'd files and writing to a block that's being punched should be the same as if the file was truncated.
The only thing that punching a hole has to handle that truncating doesn't is the corner case of punching a hole that does not align on block boundaries, in which case zeros have to be written to the parts that aren't block aligned, and for consistency they probably have to be written atomically.
As for truncating and punching at the same time, surely that would just be equivalent to a truncate to whichever gives the shortest file and both system calls would return success.
Signature · 4 lines
http://www.coker.com.au/selinux/ My NSA Security Enhanced Linux packages http://www.coker.com.au/bonnie++/ Bonnie++ hard drive benchmark http://www.coker.com.au/postal/ Postal SMTP/POP benchmark http://www.coker.com.au/~russell/ My home page
Quoted 1 line · Russell Coker
In what way are they different from that of truncate?
truncate? Surely the semantics are equivalent to writing all zeroes, not truncate?
Quoted 4 lines
It seems to me that punching a hole in a file is actually easier than truncating a file as we don't have to change the length. The issues of mmap'd files and writing to a block that's being punched should be the same as if the file was truncated.
Except with truncate it's hard, and for 'punch' (or fclear()) I'd suggest that you're allowed to just refrain from freeing the backing store for the page in question if it's mapped shared writable.
It should be considered identical to mmapping /dev/zero and writing from it, the _only_ exception being that it hints to the underlying file system that it _may_ want to free the backing store for the range in question.
Quoted 4 lines
The only thing that punching a hole has to handle that truncating doesn't is the corner case of punching a hole that does not align on block boundaries, in which case zeros have to be written to the parts that aren't block aligned, and for consistency they probably have to be written atomically.
We don't even bother with atomicity in write() do we? We do a page at a time and if reads happen while a writer is between pages, they see that the write() isn't atomic.
Quoted 3 lines
As for truncating and punching at the same time, surely that would just be equivalent to a truncate to whichever gives the shortest file and both system calls would return success.
Either the truncate happens first and the punch then extends i_size to the last byte which was punched, or the punch happens first and the file is subsequently truncated.
Signature · 1 line
dwmw2
Quoted 7 lines
It seems to me that punching a hole in a file is actually easier than truncating a file as we don't have to change the length. The issues of mmap'd files and writing to a block that's being punched should be the
same
Quoted 1 line
as if the file was truncated.
Except that in most Linux kernels, a VM interface specifically for truncating is exported for use by loadable modules, whereas there isn't an interface to remove pages from the middle of a file cache.
There ought to be, though. I consider this a gaping hole in the Linux VM interface. Proposals to fill it in have been floated recently on linux-kernel.
Bryan Henderson IBM Almaden Research Center
San Jose CA Filesystems
The semantics are really not controversial. They are the same as a write() of zeroes.
Quoted 2 lines
what are the semantics of another
thread or process reading from a block that's been punched out?
It should read zeroes.
Quoted 3 lines
what are
the semantics of another thread or process writing to a block that gets punched out?
If it writes after the punching, the data it writes ends up in the file. If it writes before the punching, a hole ends up in the file. It can't write at the same time as the punching because of the atomic write guarantee.
Quoted 2 lines
what are the semantics of another thread or process that has this region of the file mmaped?
It should see zeroes.
Quoted 1 line
what are the semantics if this thread has it mmaped?
Same.
Quoted 2 lines
what if two threads try to punch out overlapping regions simultaneously?
The union of the two regions gets cleared (but there might be fewer blocks actually removed from the file than if the entire region were punched at once, owing to implementation realities).
Quoted 2 lines
what if a region is being truncated and punched out at the same time?
Same.
Quoted 8 lines
Quoted 6 lines
XFS uses an ioctl to punch holes,
dm_punch_hole, but it's prototype is specific to XDSM.
make_holeorzap_rangewould be alternative names.
The concept is a good one, and a separate system call, defined in a filesystem-type-independent way, is better than an ioctl or fcntl, but the interface should not be defined in terms of making holes. At the highest level, a file is just a stream of bytes. A continuous stream. So what this interface should be seen as, and named as, is something that simply clears a region of the file to zeroes. In a particular implementation, if it makes sense, this can be implemented by deallocating blocks that back that region of the file.
Note that in some filesystem types, there may not be any concept of allocated blocks or sparse vs dense files.
AIX has a system call for this and it is called fclear(). I like that better than any alternative I've seen.
Bryan Henderson IBM Almaden Research Center
San Jose CA Filesystems
Quoted 2 lines · Carl-Daniel Hailfinger
This facility has been present in linux for years. Just google for "sparse files".
Yes sparse files would do. However, after a sizeable use of the facility, you'd end up with a giant hole at the beginning, whatever queued data, and EOF.
What I want to do is the ability to just remove the hole in front (just as when there is no point in having a hole at the end of the file, you just truncate that hole out), so that seek(SEEK_BEGIN,0) positions me at the beginning of useful data (or EOF if my queue is empty).
-- Cyrille
Quoted 6 lines · Cyrille Chepelov
Quoted 2 lines · Carl-Daniel Hailfinger
This facility has been present in linux for years. Just google for "sparse files".
Quoted 7 lines
Yes sparse files would do. However, after a sizeable use of the facility, you'd end up with a giant hole at the beginning, whatever queued data, and EOF.
What I want to do is the ability to just remove the hole in front (just as when there is no point in having a hole at the end of the file, you just truncate that hole out), so thatseek(SEEK_BEGIN,0)positions me at the beginning of useful data (or EOF if my queue is empty).
A few thoughts.
1) Does it really need to be a single file? Could a directory of files for each "transaction" suffice?
2) Can the buffer be bounded? If so, why not use a classic ring buffer?
3) If it can't be bounded, must it be simple file operations, or could you use something like sleepy cat's db4 or mysql?
Come to think of it, if sparse files are used you could have a classic ring buffer that is effectively unbounded.
Signature · 2 lines
Chris Dukes I tried being reasonable once--I didn't like it.
Quoted 3 lines · Chris Dukes
A few thoughts.
1) Does it really need to be a single file? Could a directory of files for each "transaction" suffice?
In theory, yes, in practice we got bitten going that road (especially since while I'm wondering whether head-truncate could be added as a plug-in on reiserfs4, the application is really running on <dirty>NTFS</dirty>).
Quoted 1 line
2) Can the buffer be bounded? If so, why not use a classic ring buffer?
no
Quoted 2 lines
3) If it can't be bounded, must it be simple file operations, or could you use something like sleepy cat's db4 or mysql?
Yes it must be simple file operations, so no a database engine is out of question (DB4 might be simple enough, but sounds like massive overkill).
Quoted 2 lines
Come to think of it, if sparse files are used you could have a classic ring buffer that is effectively unbounded.
True, as long as we are 100% sure the offsets aren't hitting some implementation limit.
(given the patterns of use of the FIFOish buffer and the underlying OS, the way I developed it, it's effectively a ring buffer with no bound, and a "magic behaviour" that when the queue is empty, both pointers are reset to the first position and the file is truncated. The situation where the hole in front is significantly large is transient enough that making the file sparse doesn't warrant the effort, waiting for a complete drain and the eventual truncate takes care of space concerns).
The goal of my initial post was not to get someone to help me out of a problem, but to learn whether the planned reiserfs4 plug-in system would allow one to implement heterodox behaviours.
(it is true that a combination of sparse files + pointer-reset-on-drain should bring a better solution, by removing the need for non-portable extensions).
-- Cyrille
Quoted 9 lines · Cyrille Chepelov
Quoted 4 lines · Carl-Daniel Hailfinger
This facility has been present in linux for years. Just google for "sparse files".
Quoted 11 lines
Yes sparse files would do. However, after a sizeable use of the facility, you'd end up with a giant hole at the beginning, whatever queued data, and EOF. What I want to do is the ability to just remove the hole in front (just as when there is no point in having a hole at the end of the file, you just truncate that hole out), so that
seek(SEEK_BEGIN,0)positions me at the beginning of useful data (or EOF if my queue is empty).-- Cyrille
So in answer, yes, this is quite feasible and reasonable to do. I will be likely to accept such a patch, though you should send a detailed design first to reiserfs-list before writing code.
Signature · 1 line
Hans
Quoted 3 lines · Hans Reiser
So in answer, yes, this is quite feasible and reasonable to do. I will be likely to accept such a patch, though you should send a detailed design first to reiserfs-list before writing code.
I don't know whether I'll have the time to tackle such a project (at least not in the immediate future), but I'm happy to know that you judge that feasible. It seems to me wise to wait for a released version of the fs before proceeding anyway.
Once I'm ready to give that a spin, I will start by discussing the technical aspects here.
-- Cyrille
Quoted 13 lines · Cyrille Chepelov
Hi all,
I recently encountered a need for such a contraption as file-backed FIFOs. These are files where one process can append records at one end, and one other process can read records from the beginning of the file, chopping off the head of the file once it's not needed anymore. As I had to implement something right now on existing systems, I worked around the general absence for such a facility, but still, I'm wondering how difficult it would to write a reiserfs4 plug-in which would allow one to do the equivalent of a
truncate()but truncating what's between the position 0 and the current cursor (effectively shifting all subsequent file positions), rather than truncating what's between the cursor and the end of file. (network considerations are explicitly out of the scope of this musing)
There's a program called "cupyvei" which allows one process to append records to a file, and any number of other processes to read independently from the beginning. It isn't unlimited though; it's a circular buffer, and the size is specified when you create it. Is that of any interest?
phma
Signature · 3 lines
.i toljundi do .ibabo mi'afra tu'a do .ibabo damba do .ibabo do jinga .icu'u la ma'atman.