Skip to contentSkip to conversation

Efficient handling of sparse files

DISCUSSION Matthew Wilcox 7 participants 10 messages Feb 28, 2005 – Mar 1, 2005 VFS

lore
Share & tools
lore
#0 lore raw

This problem came up with the systemimager program which uses rsync to install files from a master server to many clients. Red Hat has a system user with uid 2^32-1 which causes lastlog to grow to 1.2GB in size. rsync does understand the concept of sparse files (with the -S flag), but it has to read every block to discover that it is indeed empty. This sucks.

I was wondering if we could introduce a new system call (or ioctl?) that, given an fd would find the next block with data in it. We could use the ->bmap method ... except that has dire warnings about adding new callers and viro may soon be in testicle-gouging range.

One system interface hack would be to introduce lseek(fd, 0, SEEK_DATA) ... but without permission to reuse ->bmap for this purpose, it's pointless to discuss user interfaces.

Suggestions?

Signature · 6 lines
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain
#1 lore raw
Quoted 12 lines · Matthew Wilcox

This problem came up with the systemimager program which uses rsync to install files from a master server to many clients. Red Hat has a system user with uid 2^32-1 which causes lastlog to grow to 1.2GB in size. rsync does understand the concept of sparse files (with the -S flag), but it has to read every block to discover that it is indeed empty. This sucks.

I was wondering if we could introduce a new system call (or ioctl?) that, given an fd would find the next block with data in it. We could use the ->bmap method ... except that has dire warnings about adding new callers and viro may soon be in testicle-gouging range.

Quoted 5 lines

One system interface hack would be to introduce lseek(fd, 0, SEEK_DATA) ... but without permission to reuse ->bmap for this purpose, it's pointless to discuss user interfaces.

Suggestions?

This is very similar to the Windows ability to do a query to get the block map of a sparse file. Might be worth looking at that interface to see what we can learn.

Jeremy.

#2 lore raw
Quoted 3 lines

This is very similar to the Windows ability to do a query to get the block map of a sparse file. Might be worth looking at that interface to see what we can learn.

XDSM (better but incorrectly known by the generic term DMAPI) also has one of those, for use in migrating or backing up sparse files and restoring them to their original sparseness.

I'd resist any interface that exposes implementation details like that. The user program shouldn't know anything about block allocations.

On the other hand, I can see the value in exposing the concept of a clear section of file (a hole), as distinct from one filled with zeroes.

I once had to deal with this in a system that would have to transfer mass quantities of zero bytes over a network for sparse files. I found then that the most convenient interface was a new form of the read call. It returned an indicator of whether the offsets being read were clear or filled plus, if filled, the values. If clear, the values are by definition zero. At boundaries between clear and filled sections of the file, it would do a short read. Otherwise, the semantics were pretty much the same as classic Unix character stream read.

My interface didn't have the ability to tell you how far the hole extends without you having to allocate a buffer that big (because you don't know until you do the read if you're reading a hole or not), but that seems like a reasonable addition.

If someone's expending development effort on exploiting file sparseness, I'd rather see it spent implementing a clear (aka punch) system call first. Or has that been done when I wasn't looking?

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

#3 lore raw
Quoted 2 lines · Bryan Henderson

I'd resist any interface that exposes implementation details like that. The user program shouldn't know anything about block allocations.

A database or file scanner that must read a lot of data can benefit from having even a rough idea of the layout of the data on disk.

When you have to scan a lot of data, the performance improvement from sweeping across a disk in block order can be significant - more so than trying to schedule lots of asynchronous I/O for the elevator to sort.

But despite this use, ->bmap is not ideal for that type of optimisation because it does not always correspond to position on the physical device.

-- Jamie

#4 lore raw
Quoted 2 lines

A database or file scanner that must read a lot of data can benefit from having even a rough idea of the layout of the data on disk.

True. There's always room for interfaces that dive into the lower layers for those users who want to be there. (Of course, you end up crossing a line fairly quickly where you shouldn't be pretending to use a filesystem at all and should just use a block disk).

But I first want to see an abstract interface where an application can recognize cleared regions of file without actually knowing anything about how the filesystem represents them or what the filesystem does with them. In particular, there's no reason to give up the character stream notion of a file and start talking about blocks just to have visible cleared regions (holes).

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

#5 lore raw
In reply to Matthew Wilcox
Quoted 5 lines · Matthew Wilcox

This problem came up with the systemimager program which uses rsync to install files from a master server to many clients. Red Hat has a system user with uid 2^32-1 which causes lastlog to grow to 1.2GB in size. rsync does understand the concept of sparse files (with the -S flag), but it has to read every block to discover that it is indeed empty. This sucks.

XFS supports what you want. I made a related benchmark some years ago, if you are interested,

	http://marc.theaimsgroup.com/?l=reiserfs&m=105827549109079
Quoted 2 lines

I was wondering if we could introduce a new system call (or ioctl?) that, given an fd would find the next block with data in it.

I think, this is a bad idea. The XFS or the NTFS interface could be a better start.

Szaka

#6 lore raw
In reply to Matthew Wilcox
Quoted 5 lines

I was wondering if we could introduce a new system call (or ioctl?) that, given an fd would find the next block with data in it. We could use the ->bmap method ... except that has dire warnings about adding new callers and viro may soon be in testicle-gouging range.

Hmm. What you're talking about reminds me of some ioctl()s Alex has for ext3+extents and it feels like the pagevec apis that want to find populated pages across the page cache index space.

Sooo.

struct fs_extent {
	u64 file_start;
	u64 block_start;
	u64 contig;
};

(I don't really care if those are in bytes or blocks or whatever. someone with strong opinions can pick a unit :))

long sys_find_extents_please(int fd, off_t file_start,

	struct fs_extent *extents, long nr_extents);

so it'll fill in as many extent structs in the caller as it finds contiguous regions on disk starting with the given file position, returning the number populated.

I'd, somewhat obviously, want to push this into an fs method perhaps with a generic_ that just spins on bmap().

I think this would let Alex kill his ioctl() and ocfs2 could certainly fill this with reasonable results.

To move into lala land, I wonder if we would want to consider the difference between mapped blocks with data and mapped blocks that haven't been touched and which are going to return zeros. One could argue that it's marginally ridiculous that there isn't a shared interface to reserve blocks without having to manually zero them. If we did have such an interface, something like rsync doesn't actually care that they're mapped if the fs knows that they're still just zeros. I acknowledge that this is a bit out there :)

In any case, if you want help rolling proofs-of-concept I could lend a few hours.

- z

#7 lore raw
In reply to Matthew Wilcox
Quoted 11 lines · Matthew Wilcox

This problem came up with the systemimager program which uses rsync to install files from a master server to many clients. Red Hat has a system user with uid 2^32-1 which causes lastlog to grow to 1.2GB in size. rsync does understand the concept of sparse files (with the -S flag), but it has to read every block to discover that it is indeed empty. This sucks.

I was wondering if we could introduce a new system call (or ioctl?) that, given an fd would find the next block with data in it. We could use the ->bmap method ... except that has dire warnings about adding new callers and viro may soon be in testicle-gouging range.

Quoted 5 lines

One system interface hack would be to introduce lseek(fd, 0, SEEK_DATA) ... but without permission to reuse ->bmap for this purpose, it's pointless to discuss user interfaces.

Suggestions?

Please keep one thing in mind and that is that there are file systems where ->bmap actually makes no sense whatsoever - for example NTFS where you can have compressed or encrypted file in both of which you do not have any blocks on disk where you can read/write the actual data and in addition to those you also have resident files where the file content itself is stored inside the on-disk inode (at a variable and unaligned offset) so here again there is no block a ->bmap could return that would only contain the file data - it would also contain metadata and the data would certainly not start at a block boundary.

This is one of the reasons why noone should be using ->bmap. It is a stupid interface that only fits very particular sets of file systems and cannot be applied generically.

Best regards,

Anton

Signature · 4 lines
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer / IRC: #ntfs on irc.freenode.net
WWW: http://linux-ntfs.sf.net/ & http://www-stu.christs.cam.ac.uk/~aia21/
#8 lore raw
Quoted 3 lines

Please keep one thing in mind and that is that there are file systems where ->bmap actually makes no sense whatsoever

Of course, so return -ESORRY.

Quoted 3 lines

This is one of the reasons why noone should be using ->bmap. It is a stupid interface that only fits very particular sets of file systems and cannot be applied generically.

No, it's a reason to only ask about the details of block mapping in cases where it actually makes sense (like, wanting to find out of concurrent file extension is getting good batched contiguous allocation, etc). Just because file systems x, y, and z can't answer the question meaningfully doesn't mean it isn't a reasonble thing to ask of file systems m, n, and o.

Now, I'm not at all opposed to an explicit sparse-testing interface that doesn't confuse that functionality with querying specific block mappings.

- z

#9 lore raw
Quoted 4 lines · Zach Brown
Quoted 2 lines

Please keep one thing in mind and that is that there are file systems where ->bmap actually makes no sense whatsoever

Of course, so return -ESORRY.

Ah but it gets even worse, ->bmap uses 0 to mean sparse when in NTFS 0 is a valid block so it cannot be sparse, sparse needs its own namespace outside 0-2^63-1. Internally in NTFS I use -1 for sparse for example.

Quoted 11 lines
Quoted 3 lines

This is one of the reasons why noone should be using ->bmap. It is a stupid interface that only fits very particular sets of file systems and cannot be applied generically.

No, it's a reason to only ask about the details of block mapping in cases where it actually makes sense (like, wanting to find out of concurrent file extension is getting good batched contiguous allocation, etc). Just because file systems x, y, and z can't answer the question meaningfully doesn't mean it isn't a reasonble thing to ask of file systems m, n, and o.

Quoted 2 lines

Now, I'm not at all opposed to an explicit sparse-testing interface that doesn't confuse that functionality with querying specific block mappings.

That's cool. Just an array of zero-data[file offset, length]n would be sufficient, no? Note I think doing just sparse is not as good as doing zero-data because on NTFS you can have on-disk blocks allocated but the file can be marked as empty beyond a certain offset (in that case the on-disk blocks contain random garbage and the driver just knows to fill in with zero on read - i.e. no disk access needed at all on reads and to do actual writes to disk on non-zero write). This is actually used in Windows by applications (office and outlook for example) that want to have guaranteed storage allocations (e.g. for the mail INBOX) so deliveries cannot fail but want to efficiently clear the file contents beyond a certain offset. I suppose the ntfs driver could simply pretend that this non-initialized but allocated space is sparse if a sys_get_sparse_regions() rather than a sys_get_zero_regions() is implemented so it wouldn't be such a big problem.

Best regards,

Anton

Signature · 4 lines
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer / IRC: #ntfs on irc.freenode.net
WWW: http://linux-ntfs.sf.net/ & http://www-stu.christs.cam.ac.uk/~aia21/