Re: fallocate support for bitmap-based files

[Dave Kleikamp <shaggy@linux.vnet.ibm.com>]

On Fri, 2007-06-29 at 16:52 -0400, Mike Waychison wrote:
> Dave Kleikamp wrote:
> > 
> > By truncating the blocks file at the correct byte offset, only needing
> > to zero some bits of the last byte of the file.
> 
> We were thinking the unwritten blocks file would be indexed by physical 
> block number of the block device.  There wouldn't be a logical to 
> physical relationship for the blocks, so we wouldn't be able to get away 
> with truncating the blocks file itself.

I misunderstood.  I was thinking about a block-file per regular file
(that had preallocated blocks).  Ignore that comment.

> >>- When the fs comes to read a block from disk, it will need to consult
> >>  the unwritten blocks file to see if that block should be zeroed by the
> >>  CPU.
> >>
> >>- When the unwritten-block is written to, its bit in the unwritten blocks
> >>  file gets zeroed.
> >>
> >>- An obvious efficiency concern: if a user file has no unwritten blocks
> >>  in it, we don't need to consult the unwritten blocks file.
> >>
> >>  Need to work out how to do this.  An obvious solution would be to have
> >>  a number-of-unwritten-blocks counter in the inode.  But do we have space
> >>  for that?
> > 
> > 
> > Would it be too expensive to test the blocks-file page each time a bit
> > is cleared to see if it is all-zero, and then free the page, making it a
> > hole?  This test would stop if if finds any non-zero word, so it may not
> > be too bad.  (This could further be done on a block basis if the block
> > size is less than a page.)
> 
> When clearing the bits, we'd likely see a large stream of writes to the 
> unwritten blocks, which could result in a O(n^2) pass of rescanning the 
> page over and over.  

If you start checking for zero at the bit that was just zeroed, you'd
likely find a non-zero bit right away, so you wouldn't be looking at too
much of the page in the typical case.

> Maybe a per-unwritten-block-file block 
> per-block-header with a count that could be cheaply tested?  Ie: the 
> unwritten block file is composed of blocks that each have a small header 
> that contains count -- when the count hits zero, we could punch a hole 
> in the file.

Having the data be just a bitmap seems more elegant to me.  It would be
nice to avoid keeping a count in the bitmap page if possible.
-- 
David Kleikamp
IBM Linux Technology Center