linux-ext4 - Re: fallocate support for bitmap-based files

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <1183152295.12702.20.camel@kleikamp.austin.ibm.com>
Date:	Fri, 29 Jun 2007 16:24:55 -0500
From:	Dave Kleikamp <shaggy@...ux.vnet.ibm.com>
To:	Mike Waychison <mikew@...gle.com>
Cc:	Andrew Morton <akpm@...ux-foundation.org>,
	"Theodore Ts'o" <tytso@....edu>,
	Andreas Dilger <adilger@...sterfs.com>,
	Sreenivasa Busam <sreenivasac@...gle.com>,
	"linux-ext4@...r.kernel.org" <linux-ext4@...r.kernel.org>
Subject: Re: fallocate support for bitmap-based files

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

-
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html