Re: question on ext2fs_get_free_blocks() in e2fsprogs

Andreas Dilger wrote:
> I believe there was some discussion of this code when Takashi first
> submitted it.  It might shed more light here.  Improved comments are
> also welcome.

Ok, the only discussion I found was in march, here (not from Takashi, 
but from Coywolf Qi Hunt):

http://marc.theaimsgroup.com/?l=ext2-devel&m=114265237011473&w=2

The feedback from Ted was that:

> One of the correct ways to use
> ext2fs_get_free_blocks is to start looking at block 50000, but if all
> of the blocks are from there to the end of the file are in use, then
> wrap back to the beginnin and start searching until the caller reaches
> the finish point (Whcih if it is not set, is the same as the starting
> point).

and:

> It's a general purpose library routine ... If the caller only wants to
> allocate inside a block group, it can specify start and finish
> appropriately, and the fact that the termination condition didn't
> catch it is a bug.
> 
> But if finish is 0, what is supposed to happen is that
> ext2fs_get_free_blocks is supposed to search the entire filesystem,
> starting the search at <<start>> for data layout optimization reasons.

So, there is at least definitely a bug here; if the start->finish range 
butts up against the end of the filesystem:

|<------------filesystem------------>|
                     start          finish
                       |--------------|

and that requested range is full:
                       |-----| nospc
                          |-----| nospc
                             |-----| nospc
                                |-----| nospc
start+num-1 > s_blocks_count -->  |-----|

then start wraps back to the beginning:

|-----|
    |-----|
       ...

and if there is no space anywhere on the filesystem, this will loop 
forever, because:

if (b+num-1 > fs->super->s_blocks_count)
           b = fs->super->s_first_data_block;

keeps the:
   } while (b != finish);

check from ever being true.

In addition, there is asymmetric behavior based on where "finish" lands 
(or more precicely, where start + num - 1 lands).  If the range is well 
within the middle of the filesystem:

|<------------filesystem------------>|
            start          finish
              |--------------|

and that requested range is full:
              |-----| nospc
                 |-----| nospc
                    |-----| nospc
                       |-----| nospc
                          |-----| nospc
                             |-----| nospc

then the function will stop and return EXT2_ET_BLOCK_ALLOC_FAIL

So in the first case, "start" is a hint and "finish" is irrelevant; in 
the 2nd case, "start" and "finish" are mandatory.

So I guess I need to work out what the -intended- functionality is, and 
then try to fix up the code so it works as intended.  :)

It would seem reasonable to me if it behaved as follows, and I think 
this is the intent:

* If neither start nor finish is specified, search the whole filesystem
   starting at the beginning.
* If only start is specified, but not finish, start is a hint only;
   search the whole filesystem, starting at "start", wrapping if needed.
* If start and finish are both specified, the range is mandatory.
   Return ALLOC_FAIL if requested blocks are not available in the range.

Further, I'd probably set the semantics to say that if start and finish 
are both specified, then that means that the number of requested blocks 
must be available between start & finish, inclusive, or ALLOC_FAIL is 
returned.

Am I close? :)

-Eric

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642