Prepending Data to a File

Question

There's no way in any operating system I'm aware of for a program to prepend data to a file efficiently. And yet, this doesn't seem difficult -- the file system can add another extent to a file descriptor if needed.

So the question is, why don't operating systems implement this (rather trivial) operation?

Gauzy

In response to a similar question on SO the other day, I spent 45 minutes trying to find an XFS ioctl() that would do just that; but after not finding it for a very long time, I gave up -- maybe my memory mislead me. Even though I wouldn't call it trivial (not like appending, any way :) I agree that providing prepending support should enable some tasks to run much faster than the usual read-and-write-every-byte approach. – Specialistic

Answer 1

I don't think it's as easy as you suggest. It's true that the file-system could allocate a new block, store the prepended data in it, change the file pointer to point to that block and then chain the rest of the file from that block. Just like adding a node to the front of a linked list, right?

But what happens when (as is probably the case) the prepended data doesn't fill the assigned block. I don't imagine that many filesystems would have a machanism for chaining partial blocks, but even if they do it would result in huge inefficiencies. You'd end up with a file consisting of mostly empty blocks, and you have to have to read and write the entire file to defragment it. Might as well just do the read-and-write operation up front when you're prepending in the first place.

Hogue

+1: Prepending a partial block is the necessary counter-example to prove that the operation is not "rather trivial". – Cyprian

Ah you're absolutely right!! I totally forgot about the case when the block wouldn't be completely filled, silly me. :) Thanks for the great explanation! – Gauzy

+1 Great answer, that's the answer I was looking for as well, I didn't consider the block may not get filled up and was thinking the same as the OP :) – Knobby

Looking back at this answer 6 years later, and I'm not convinced anymore :-) if you can append, you can prepend... you just mirror the exact same algorithm. A filesystem will support whatever the OS primarily associated with it wants (that's how they usually get written), so lack of support isn't terribly convincing. I have hunches as to what the correct answer might be, but thought I'd leave this comment and see if anyone has a response first... – Gauzy

Answer 2

In prepending or appending data to a file, there is always an issue of allocating space. Appending additional space to a file is much easier than prepending because of file descriptors pointing to the beginning of a file's stream. If you want to append to a file, the file descriptor need not be changed, just the size of the file and the allocated memory. If you want to prepend to a file, a new file descriptor must be immediately instantiated, either to write the prepended data to first or to store the location of the data being prepended while the original is updated.

Making a new file descriptor can be tricky, as you must also update any references pointing to it. This is why it is easy for an OS to implement appending data and slightly harder to implement prepending.

Unhappy