Re: question on ext2fs_get_free_blocks() in e2fsprogs

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

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().

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.

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