[btrfs-devel][patch]Cache blocks in the hole at beginning of a block group

[Yan Zheng]

2007/9/12, Chris Mason <chris.mason at oracle.com>:
> Thanks, you've definitely found a bug in the current code, but I'm
> afraid we can't assume the start of the block group is free.  There
> could be an extent allocated in the last block group that extends into
> the current one.
>

Thanks for comment.

I feel if there are extent items across block group boundary,  we also
can't guarantee start of the block group is free in other tests (in
cache_block_group) . In addition, the subtraction operation in codes
like:
--------------------------------------------------------
if (found) {
    hole_size = block_group->key.objectid +
                         block_group->key.offset - last;
}
-------------------------------------------------------
may overflow. The overflow bug can  easily produce by adding a extent
item across boundary of block group 0 and block group 1.


here is the new patch . it finds the start of free block in a block
group by checking the first extent item (the one found by
btrfs_search_slot directly, it should belong to preceding block group
except for the first block group).  it also add check for overflow.

Regards
YZ

diff -r 9cb5f0f5c713 extent-tree.c
--- a/extent-tree.c	Thu Aug 30 12:16:51 2007 -0400
+++ b/extent-tree.c	Wed Sep 12 13:08:17 2007 +0800
@@ -39,6 +39,7 @@ static int cache_block_group(struct btrf
 	u64 i;
 	u64 last = 0;
 	u64 hole_size;
+	u64 first_free;
 	int found = 0;

 	root = root->fs_info->extent_root;
@@ -52,6 +53,7 @@ static int cache_block_group(struct btrf
 	if (!path)
 		return -ENOMEM;
 	path->reada = 2;
+	first_free = block_group->key.objectid;
 	key.objectid = block_group->key.objectid;
 	key.flags = 0;
 	key.offset = 0;
@@ -71,13 +73,13 @@ static int cache_block_group(struct btrf
 			if (ret == 0) {
 				continue;
 			} else {
-				if (found) {
-					hole_size = block_group->key.objectid +
-						block_group->key.offset - last;
-				} else {
-					last = block_group->key.objectid;
-					hole_size = block_group->key.offset;
-				}
+				if (!found)
+					last = first_free;
+				if (block_group->key.objectid +
+				    block_group->key.offset < last)
+					break;
+				hole_size = block_group->key.objectid +
+					block_group->key.offset - last;
 				for (i = 0; i < hole_size; i++) {
 					set_radix_bit(extent_radix,
 						      last + i);
@@ -86,15 +88,20 @@ static int cache_block_group(struct btrf
 			}
 		}
 		btrfs_disk_key_to_cpu(&key, &leaf->items[slot].key);
+		if (key.objectid < block_group->key.objectid) {
+			if (key.objectid + key.offset > first_free)
+				first_free = key.objectid + key.offset;
+			goto next;
+		}
 		if (key.objectid >= block_group->key.objectid +
 		    block_group->key.offset) {
-			if (found) {
-				hole_size = block_group->key.objectid +
-					block_group->key.offset - last;
-			} else {
-				last = block_group->key.objectid;
-				hole_size = block_group->key.offset;
-			}
+			if (!found)
+				last = first_free;
+			if (block_group->key.objectid +
+			    block_group->key.offset < last)	
+				break;
+			hole_size = block_group->key.objectid +
+				block_group->key.offset - last;
 			for (i = 0; i < hole_size; i++) {
 				set_radix_bit(extent_radix, last + i);
 			}
@@ -102,16 +109,16 @@ static int cache_block_group(struct btrf
 		}
 		if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
 			if (!found) {
-				last = key.objectid + key.offset;
+				last = first_free;
 				found = 1;
-			} else {
-				hole_size = key.objectid - last;
-				for (i = 0; i < hole_size; i++) {
-					set_radix_bit(extent_radix, last + i);
-				}
-				last = key.objectid + key.offset;
-			}
-		}
+			}
+			hole_size = key.objectid - last;
+			for (i = 0; i < hole_size; i++) {
+				set_radix_bit(extent_radix, last + i);
+			}
+			last = key.objectid + key.offset;
+		}
+next:
 		path->slots[0]++;
 	}
-------------- next part --------------
A non-text attachment was scrubbed...
Name: extent-tree.patch
Type: text/x-patch
Size: 2673 bytes
Desc: not available
Url : http://oss.oracle.com/pipermail/btrfs-devel/attachments/20070912/330807f3/extent-tree.bin