Btrfs: support for items bigger than 1/2 the blocksize

Signed-off-by: Chris Mason <chris.mason@oracle.com>

1 files changed, 97 insertions, 35 deletions

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 9ef65e2ecf5..864ee423b30 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -6,7 +6,8 @@
 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
 		      *root, struct btrfs_path *path, int level);
 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
-		      *root, struct btrfs_path *path, int data_size);
+		      *root, struct btrfs_key *ins_key,
+		      struct btrfs_path *path, int data_size);
 static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root
 			  *root, struct buffer_head *dst, struct buffer_head
 			  *src);
@@ -102,19 +103,6 @@ static inline unsigned int leaf_data_end(struct btrfs_root *root,
 }
 
 /*
- * The space between the end of the leaf items and
- * the start of the leaf data.  IOW, how much room
- * the leaf has left for both items and data
- */
-int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf)
-{
-	int data_end = leaf_data_end(root, leaf);
-	int nritems = btrfs_header_nritems(&leaf->header);
-	char *items_end = (char *)(leaf->items + nritems + 1);
-	return (char *)(btrfs_leaf_data(leaf) + data_end) - (char *)items_end;
-}
-
-/*
  * compare two keys in a memcmp fashion
  */
 static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
@@ -510,8 +498,8 @@ again:
 			if (ret && slot > 0)
 				slot -= 1;
 			p->slots[level] = slot;
-			if (ins_len > 0 && btrfs_header_nritems(&c->header) ==
-			    BTRFS_NODEPTRS_PER_BLOCK(root)) {
+			if (ins_len > 0 && btrfs_header_nritems(&c->header) >=
+			    BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
 				int sret = split_node(trans, root, p, level);
 				BUG_ON(sret > 0);
 				if (sret)
@@ -537,7 +525,8 @@ again:
 			p->slots[level] = slot;
 			if (ins_len > 0 && btrfs_leaf_free_space(root, l) <
 			    sizeof(struct btrfs_item) + ins_len) {
-				int sret = split_leaf(trans, root, p, ins_len);
+				int sret = split_leaf(trans, root, key,
+						      p, ins_len);
 				BUG_ON(sret > 0);
 				if (sret)
 					return sret;
@@ -825,17 +814,30 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
 static int leaf_space_used(struct btrfs_leaf *l, int start, int nr)
 {
 	int data_len;
-	int end = start + nr - 1;
+	int nritems = btrfs_header_nritems(&l->header);
+	int end = min(nritems, start + nr) - 1;
 
 	if (!nr)
 		return 0;
 	data_len = btrfs_item_end(l->items + start);
 	data_len = data_len - btrfs_item_offset(l->items + end);
 	data_len += sizeof(struct btrfs_item) * nr;
+	WARN_ON(data_len < 0);
 	return data_len;
 }
 
 /*
+ * The space between the end of the leaf items and
+ * the start of the leaf data.  IOW, how much room
+ * the leaf has left for both items and data
+ */
+int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf)
+{
+	int nritems = btrfs_header_nritems(&leaf->header);
+	return BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
+}
+
+/*
  * push some data in the path leaf to the right, trying to free up at
  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
  *
@@ -1084,7 +1086,8 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
  * returns 0 if all went well and < 0 on failure.
  */
 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
-		      *root, struct btrfs_path *path, int data_size)
+		      *root, struct btrfs_key *ins_key,
+		      struct btrfs_path *path, int data_size)
 {
 	struct buffer_head *l_buf;
 	struct btrfs_leaf *l;
@@ -1097,8 +1100,10 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
 	int data_copy_size;
 	int rt_data_off;
 	int i;
-	int ret;
+	int ret = 0;
 	int wret;
+	int double_split = 0;
+	struct btrfs_disk_key disk_key;
 
 	/* first try to make some room by pushing left and right */
 	wret = push_leaf_left(trans, root, path, data_size);
@@ -1127,26 +1132,58 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
 	mid = (nritems + 1)/ 2;
 	right_buffer = btrfs_alloc_free_block(trans, root);
 	BUG_ON(!right_buffer);
-	BUG_ON(mid == nritems);
 	right = btrfs_buffer_leaf(right_buffer);
 	memset(&right->header, 0, sizeof(right->header));
-	if (mid <= slot) {
-		/* FIXME, just alloc a new leaf here */
-		if (leaf_space_used(l, mid, nritems - mid) + space_needed >
-			BTRFS_LEAF_DATA_SIZE(root))
-			BUG();
-	} else {
-		/* FIXME, just alloc a new leaf here */
-		if (leaf_space_used(l, 0, mid + 1) + space_needed >
-			BTRFS_LEAF_DATA_SIZE(root))
-			BUG();
-	}
-	btrfs_set_header_nritems(&right->header, nritems - mid);
 	btrfs_set_header_blocknr(&right->header, right_buffer->b_blocknr);
 	btrfs_set_header_generation(&right->header, trans->transid);
 	btrfs_set_header_level(&right->header, 0);
 	btrfs_set_header_parentid(&right->header,
 	      btrfs_header_parentid(btrfs_buffer_header(root->node)));
+	if (mid <= slot) {
+		if (nritems == 1 ||
+		    leaf_space_used(l, mid, nritems - mid) + space_needed >
+			BTRFS_LEAF_DATA_SIZE(root)) {
+			if (slot >= nritems) {
+				btrfs_cpu_key_to_disk(&disk_key, ins_key);
+				btrfs_set_header_nritems(&right->header, 0);
+				wret = insert_ptr(trans, root, path,
+						  &disk_key,
+						  right_buffer->b_blocknr,
+						  path->slots[1] + 1, 1);
+				if (wret)
+					ret = wret;
+				btrfs_block_release(root, path->nodes[0]);
+				path->nodes[0] = right_buffer;
+				path->slots[0] = 0;
+				path->slots[1] += 1;
+				return ret;
+			}
+			mid = slot;
+			double_split = 1;
+		}
+	} else {
+		if (leaf_space_used(l, 0, mid + 1) + space_needed >
+			BTRFS_LEAF_DATA_SIZE(root)) {
+			if (slot == 0) {
+				btrfs_cpu_key_to_disk(&disk_key, ins_key);
+				btrfs_set_header_nritems(&right->header, 0);
+				wret = insert_ptr(trans, root, path,
+						  &disk_key,
+						  right_buffer->b_blocknr,
+						  path->slots[1] - 1, 1);
+				if (wret)
+					ret = wret;
+				btrfs_block_release(root, path->nodes[0]);
+				path->nodes[0] = right_buffer;
+				path->slots[0] = 0;
+				path->slots[1] -= 1;
+				return ret;
+			}
+			mid = slot;
+			double_split = 1;
+		}
+	}
+	btrfs_set_header_nritems(&right->header, nritems - mid);
 	data_copy_size = btrfs_item_end(l->items + mid) -
 			 leaf_data_end(root, l);
 	btrfs_memcpy(root, right, right->items, l->items + mid,
@@ -1180,6 +1217,31 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
 	} else
 		btrfs_block_release(root, right_buffer);
 	BUG_ON(path->slots[0] < 0);
+
+	if (!double_split)
+		return ret;
+	right_buffer = btrfs_alloc_free_block(trans, root);
+	BUG_ON(!right_buffer);
+	right = btrfs_buffer_leaf(right_buffer);
+	memset(&right->header, 0, sizeof(right->header));
+	btrfs_set_header_blocknr(&right->header, right_buffer->b_blocknr);
+	btrfs_set_header_generation(&right->header, trans->transid);
+	btrfs_set_header_level(&right->header, 0);
+	btrfs_set_header_parentid(&right->header,
+	      btrfs_header_parentid(btrfs_buffer_header(root->node)));
+	btrfs_cpu_key_to_disk(&disk_key, ins_key);
+	btrfs_set_header_nritems(&right->header, 0);
+	wret = insert_ptr(trans, root, path,
+			  &disk_key,
+			  right_buffer->b_blocknr,
+			  path->slots[1], 1);
+	if (wret)
+		ret = wret;
+	btrfs_block_release(root, path->nodes[0]);
+	path->nodes[0] = right_buffer;
+	path->slots[0] = 0;
+	check_node(root, path, 1);
+	check_leaf(root, path, 0);
 	return ret;
 }
 
@@ -1220,9 +1282,9 @@ int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root
 	data_end = leaf_data_end(root, leaf);
 
 	if (btrfs_leaf_free_space(root, leaf) <
-	    sizeof(struct btrfs_item) + data_size)
+	    sizeof(struct btrfs_item) + data_size) {
 		BUG();
-
+	}
 	slot = path->slots[0];
 	BUG_ON(slot < 0);
 	if (slot != nritems) {