3 ms·

You know, I've always been kinda amused that something very simple like "cat a b >c" or even "fa = open("a", O_APPEND | O_WRONLY); fb = open("b", O_RDONLY); sen

You know, I've always been kinda amused that something very simple like "cat a b >c" or even "fa = open("a", O_APPEND | O_WRONLY); fb = open("b", O_RDONLY); sendfile(fa, fb, NULL, 0x7ffff000);" doesn't really have either user-visible specialized API nor under-the-hood speed ups in the FS implementations. It's just gluing two files together, it's got to be a very popular operation, about as popular as "prepend the contents of file A to file B". But you can't do it in-place which is kinda annoying when you have to preserve the existing files' attributes.

jmole 2y ago
What attributes would be worth preserving that you wouldn’t otherwise be able to do?
- Joker_vD 2y ago
  Having the same permissions and the owner would be nice, which a bit annoying to pull off with the "write to a temporary file, then rename it over the original one" approach. Also, mtime/atime. And the xattrs, of course.
derefr 2y ago
Yes, in theory, any filesystem could trivially add a feature of "ref-counted immutable extents" — where a special syscall equivalent to `cat a b c > d` could be implemented that creates an inode d that consists of references to the existing extents of a+b+c. (The shared extents have to be immutable, because on non-CoW filesystems, filesystem locks apply to "byte ranges of inodes", not to extents or slices thereof; so extents could only be safely shared between inodes if they forced the inodes referencing them to act as if they were always reader-locked.) You could even implement this on e.g. Linux ext4 today — you could consider extents immutable if they're part of an immutable (chattr +i) file that has no additional hard links; and you could prevent any files that are "sharing" immutable extents from being made non-immutable (where in the above, the syscall would create a file that is immediately immutable.) This would basically result in the same semantics + efficiencies that you get with "composite uploads" in an object store. --- Given a CoW filesystem, you could probably extend this concept to allow arbitrary CoW blocks to be explicitly referenced from file A into file B without any need for immutability — it'd just be an explicit "partial" reflink. (This is already possible for the simple A->B case, by starting with a CoW clone, and then overwriting the blocks that shouldn't be shared. But more complex cases like A+B+C->D above, aren't possible; nor is having those shared blocks be in a different position in the clone than they are in the original; and so forth.) It wouldn't quite work like you're imagining with sendfile(2), though, because the CoW sharing could only occur at filesystem-block boundaries. You still wouldn't be able to use partial reflinking to optimize the operation of e.g. adding three bytes of header to a file (unless you also added BLKSZ-3 bytes of padding.)
magicalhippo 2y ago
> about as popular as "prepend the contents of file A to file B" I've never understood why filesystems don't easily support prepending data, or to truncate the start of a file. It should be, as far as I can see, about as trivial to support as appending and truncating the end, and is something that comes up quite often in application code. Even if it is a bit more tricky, I think the benefits would be great in the cases where it's needed. Instead applications are left having to rewrite the contents.
- kbolino 2y ago
  A queue is simpler to implement than a deque and the same is true of a file system: supporting growing the file in both directions is more complicated than supporting growing the file in one direction. In practice, append is much more common than prepend, so the extra bookkeeping and code doesn't seem to be worth it in general.
  - o11c 2y ago
    That's much less of a concern ever since everybody switched to extent-based filesystems. The real concern is block alignment.
tedunangst 2y ago
So if I prepend 17 bytes to a file, where are they stored? And if I prepend another 47 bytes, etc.? How would this be tracked?
- kbolino 2y ago
  Same as going forward, you'd grab a free block and simply fill it backwards from the end instead of forwards from the beginning. But the file system would have to support file data starting mid-block and new blocks getting added to the head of the file. The problem is that there'd be more bookkeeping data to store, more code to implement it, and more edge cases to handle for concurrent writes.
  - tedunangst 2y ago
    That'd be hell for mmap, too.
    - Joker_vD 2y ago
      Unironically, I think it'd be easier for purely mmap-based API to support such scenarios.
o11c 2y ago
On some Linux filesystems you can do this if the chunk to be inserted is a multiple of the block size. See `FALLOC_FL_COLLAPSE_RANGE` and `FALLOC_FL_INSERT_RANGE` in `fallocate(2)`
lmm 2y ago
> It's just gluing two files together, it's got to be a very popular operation, about as popular as "prepend the contents of file A to file B". Realistically I don't think that's going to happen very often. What would be the use case? The only case I can think of is something like tar where you pack up a bunch of files as a single file, and you usually do compression at the same time in that case.
- Joker_vD 2y ago
  > What would be the use case? Every time you need to extend the length of the field in the middle of your data (e.g., increase a variable-length-field in the header). Many file formats resort to trailer chunks specifically because of that (see ID3v2 of MP3 files, or ZIP). Or think about how SQLite's on-disk file format uses freelist of file pages: it's literally an embryonic file system in itself, built on top of the existing one. Or hey — what about linking object files together? It's kind of like the merge sort, since you need to re-slice text/data/misc and then re-glue them. Traditional linkers would create several temporary files for each combined section and then merge those files together.

jmole 2y ago

What attributes would be worth preserving that you wouldn’t otherwise be able to do?

Joker_vD 2y ago
Having the same permissions and the owner would be nice, which a bit annoying to pull off with the "write to a temporary file, then rename it over the original one" approach. Also, mtime/atime. And the xattrs, of course.

derefr 2y ago

Yes, in theory, any filesystem could trivially add a feature of "ref-counted immutable extents" — where a special syscall equivalent to `cat a b c > d` could be implemented that creates an inode d that consists of references to the existing extents of a+b+c. (The shared extents have to be immutable, because on non-CoW filesystems, filesystem locks apply to "byte ranges of inodes", not to extents or slices thereof; so extents could only be safely shared between inodes if they forced the inodes referencing them to act as if they were always reader-locked.) You could even implement this on e.g. Linux ext4 today — you could consider extents immutable if they're part of an immutable (chattr +i) file that has no additional hard links; and you could prevent any files that are "sharing" immutable extents from being made non-immutable (where in the above, the syscall would create a file that is immediately immutable.) This would basically result in the same semantics + efficiencies that you get with "composite uploads" in an object store. --- Given a CoW filesystem, you could probably extend this concept to allow arbitrary CoW blocks to be explicitly referenced from file A into file B without any need for immutability — it'd just be an explicit "partial" reflink. (This is already possible for the simple A->B case, by starting with a CoW clone, and then overwriting the blocks that shouldn't be shared. But more complex cases like A+B+C->D above, aren't possible; nor is having those shared blocks be in a different position in the clone than they are in the original; and so forth.) It wouldn't quite work like you're imagining with sendfile(2), though, because the CoW sharing could only occur at filesystem-block boundaries. You still wouldn't be able to use partial reflinking to optimize the operation of e.g. adding three bytes of header to a file (unless you also added BLKSZ-3 bytes of padding.)

magicalhippo 2y ago

> about as popular as "prepend the contents of file A to file B" I've never understood why filesystems don't easily support prepending data, or to truncate the start of a file. It should be, as far as I can see, about as trivial to support as appending and truncating the end, and is something that comes up quite often in application code. Even if it is a bit more tricky, I think the benefits would be great in the cases where it's needed. Instead applications are left having to rewrite the contents.

kbolino 2y ago
A queue is simpler to implement than a deque and the same is true of a file system: supporting growing the file in both directions is more complicated than supporting growing the file in one direction. In practice, append is much more common than prepend, so the extra bookkeeping and code doesn't seem to be worth it in general.
- o11c 2y ago
  That's much less of a concern ever since everybody switched to extent-based filesystems. The real concern is block alignment.

tedunangst 2y ago

So if I prepend 17 bytes to a file, where are they stored? And if I prepend another 47 bytes, etc.? How would this be tracked?

kbolino 2y ago
Same as going forward, you'd grab a free block and simply fill it backwards from the end instead of forwards from the beginning. But the file system would have to support file data starting mid-block and new blocks getting added to the head of the file. The problem is that there'd be more bookkeeping data to store, more code to implement it, and more edge cases to handle for concurrent writes.
- tedunangst 2y ago
  That'd be hell for mmap, too.
  - Joker_vD 2y ago
    Unironically, I think it'd be easier for purely mmap-based API to support such scenarios.

o11c 2y ago

On some Linux filesystems you can do this if the chunk to be inserted is a multiple of the block size. See `FALLOC_FL_COLLAPSE_RANGE` and `FALLOC_FL_INSERT_RANGE` in `fallocate(2)`

lmm 2y ago

> It's just gluing two files together, it's got to be a very popular operation, about as popular as "prepend the contents of file A to file B". Realistically I don't think that's going to happen very often. What would be the use case? The only case I can think of is something like tar where you pack up a bunch of files as a single file, and you usually do compression at the same time in that case.

Joker_vD 2y ago
> What would be the use case? Every time you need to extend the length of the field in the middle of your data (e.g., increase a variable-length-field in the header). Many file formats resort to trailer chunks specifically because of that (see ID3v2 of MP3 files, or ZIP). Or think about how SQLite's on-disk file format uses freelist of file pages: it's literally an embryonic file system in itself, built on top of the existing one. Or hey — what about linking object files together? It's kind of like the merge sort, since you need to re-slice text/data/misc and then re-glue them. Traditional linkers would create several temporary files for each combined section and then merge those files together.