Re: question on ext2fs_get_free_blocks() in e2fsprogs

Andreas Dilger wrote:
> On Aug 25, 2006  12:52 -0500, Eric Sandeen wrote:
>> 	/* check for overflows or reversed range*/
>> 	if ((start + num - 1 < start) || (finish < start))
>> 		return EXT2_ET_BLOCK_ALLOC_FAIL;
> 
> Concievably, it would be possible to exclude a region [a,b] in the
> middle of the filesystem by specifying start=b+1, finish=a-1, but
> I don't know if that is desirable or ever used, and it makes the
> code much more complex...

Yeah, I thought about that, but nobody calls it that way today...

> If that was the case, I'd rather just have "offset = start" and then
> do a scan from [0, finish'] and do modulo s_blocks_count everywhere.
> 
>> 	do {
>> 		if (ext2fs_fast_test_block_bitmap_range(map, start, num)) {
>> 			*ret = start;
>> 			return 0;
>> 		}
>> 		start++;
> 
> We should probably set start at the next free bit, instead of re-checking
> each and every range that might already be allocated.  Strangely, I can't
> see a routine like ext2fs_find_next_bit_free(), though there is a routine
> ext2fs_find_next_bit_set().

Yep, this struck me as quite inefficient.

> I'd think that a more efficient implementation would be something like
> (might need some more smarts to avoid looping).  It assumes we do NOT
> want to allow the finish < start case.

Ok, let me study up on that for a bit :)

Thanks,

-Eric

> 	/* don't want to allow wrapping if start=0, finish=~0UL */
> 	if (start <= fs->super->s_first_data_block)
> 		wrap_ok = 0;
> 
> 	do {
> 		/* skip range checking until we find some free space */
> 		start = ext2fs_find_next_bit_free(map, start);
> 		if (start >= finish)
> 			break;
>  		if (start > fs->super->s_blocks_count - num + 1) {
> 			if (!wrap_ok)
> 				break;
>  			start = fs->super->s_first_data_block;
> 			wrap_ok = 0; /* only wrap once */
> 		}
> 
>  		if (ext2fs_fast_test_block_bitmap_range(map, start, num)) {
>  			*ret = start;
>  			return 0;
>  		}
> 		
> 		/* skip to the next range of free bits, since this one isn't
> 		 * large enough. */
> 		start = ext2fs_find_next_bit_set(map, start);
> 		if (start >= finish)
> 			break;
>  		if (start > fs->super->s_blocks_count - num + 1) {
> 			if (!wrap_ok)
> 				break;
>  			start = fs->super->s_first_data_block;
> 			wrap_ok = 0; /* only wrap once */
> 		}
>  	} while ((wrap_ok && (start != finish)) ||
>  		 (!wrap_ok && (start <= finish - num + 1)));
> 
> Cheers, Andreas
> --
> Andreas Dilger
> Principal Software Engineer
> Cluster File Systems, Inc.
> 


-------------------------------------------------------------------------
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