X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=ctree.c;h=01baa0bfe0cb4b73ffb10c4692157e03a34c2048;hb=8d1d13c786b6edca8c8fa3d4f4c8763948f43502;hp=489019ac04b8db1c587679cacf109665cfbc5847;hpb=b2e2afd7b4f10536f10771bd6ba2b0a98357d481;p=platform%2Fupstream%2Fbtrfs-progs.git diff --git a/ctree.c b/ctree.c index 489019a..01baa0b 100644 --- a/ctree.c +++ b/ctree.c @@ -6,63 +6,64 @@ #include "disk-io.h" #include "print-tree.h" -static int split_node(struct ctree_root *root, struct ctree_path *path, - int level); -static int split_leaf(struct ctree_root *root, struct ctree_path *path, - int data_size); -static int push_node_left(struct ctree_root *root, struct tree_buffer *dst, - struct tree_buffer *src); -static int balance_node_right(struct ctree_root *root, - struct tree_buffer *dst_buf, - struct tree_buffer *src_buf); -static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, - int slot); - -inline void init_path(struct ctree_path *p) +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); +static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_buffer *dst, struct btrfs_buffer + *src); +static int balance_node_right(struct btrfs_trans_handle *trans, struct + btrfs_root *root, struct btrfs_buffer *dst_buf, + struct btrfs_buffer *src_buf); +static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, + struct btrfs_path *path, int level, int slot); + +inline void btrfs_init_path(struct btrfs_path *p) { memset(p, 0, sizeof(*p)); } -void release_path(struct ctree_root *root, struct ctree_path *p) +void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) { int i; - for (i = 0; i < MAX_LEVEL; i++) { + for (i = 0; i < BTRFS_MAX_LEVEL; i++) { if (!p->nodes[i]) break; - tree_block_release(root, p->nodes[i]); + btrfs_block_release(root, p->nodes[i]); } memset(p, 0, sizeof(*p)); } -int btrfs_cow_block(struct ctree_root *root, - struct tree_buffer *buf, - struct tree_buffer *parent, - int parent_slot, - struct tree_buffer **cow_ret) +static int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_buffer *buf, struct btrfs_buffer + *parent, int parent_slot, struct btrfs_buffer + **cow_ret) { - struct tree_buffer *cow; + struct btrfs_buffer *cow; if (!list_empty(&buf->dirty)) { *cow_ret = buf; return 0; } - cow = alloc_free_block(root); - memcpy(&cow->node, &buf->node, sizeof(buf->node)); + cow = btrfs_alloc_free_block(trans, root); + memcpy(&cow->node, &buf->node, root->blocksize); btrfs_set_header_blocknr(&cow->node.header, cow->blocknr); *cow_ret = cow; - btrfs_inc_ref(root, buf); + btrfs_inc_ref(trans, root, buf); if (buf == root->node) { root->node = cow; cow->count++; if (buf != root->commit_root) - free_extent(root, buf->blocknr, 1); - tree_block_release(root, buf); + btrfs_free_extent(trans, root, buf->blocknr, 1, 1); + btrfs_block_release(root, buf); } else { - parent->node.blockptrs[parent_slot] = cow->blocknr; + btrfs_set_node_blockptr(&parent->node, parent_slot, + cow->blocknr); BUG_ON(list_empty(&parent->dirty)); - free_extent(root, buf->blocknr, 1); + btrfs_free_extent(trans, root, buf->blocknr, 1, 1); } - tree_block_release(root, buf); + btrfs_block_release(root, buf); return 0; } @@ -71,12 +72,13 @@ int btrfs_cow_block(struct ctree_root *root, * this returns the address of the start of the last item, * which is the stop of the leaf data stack */ -static inline unsigned int leaf_data_end(struct leaf *leaf) +static inline unsigned int leaf_data_end(struct btrfs_root *root, + struct btrfs_leaf *leaf) { u32 nr = btrfs_header_nritems(&leaf->header); if (nr == 0) - return sizeof(leaf->data); - return leaf->items[nr-1].offset; + return BTRFS_LEAF_DATA_SIZE(root); + return btrfs_item_offset(leaf->items + nr - 1); } /* @@ -84,18 +86,18 @@ static inline unsigned int leaf_data_end(struct leaf *leaf) * the start of the leaf data. IOW, how much room * the leaf has left for both items and data */ -int leaf_free_space(struct leaf *leaf) +int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf) { - int data_end = leaf_data_end(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 *)(leaf->data + data_end) - (char *)items_end; + return (char *)(btrfs_leaf_data(leaf) + data_end) - (char *)items_end; } /* * compare two keys in a memcmp fashion */ -int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) +static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) { struct btrfs_key k1; @@ -116,11 +118,12 @@ int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) return 0; } -int check_node(struct ctree_path *path, int level) +static int check_node(struct btrfs_root *root, struct btrfs_path *path, + int level) { int i; - struct node *parent = NULL; - struct node *node = &path->nodes[level]->node; + struct btrfs_node *parent = NULL; + struct btrfs_node *node = &path->nodes[level]->node; int parent_slot; u32 nritems = btrfs_header_nritems(&node->header); @@ -130,43 +133,44 @@ int check_node(struct ctree_path *path, int level) BUG_ON(nritems == 0); if (parent) { struct btrfs_disk_key *parent_key; - parent_key = &parent->keys[parent_slot]; - BUG_ON(memcmp(parent_key, node->keys, + parent_key = &parent->ptrs[parent_slot].key; + BUG_ON(memcmp(parent_key, &node->ptrs[0].key, sizeof(struct btrfs_disk_key))); - BUG_ON(parent->blockptrs[parent_slot] != + BUG_ON(btrfs_node_blockptr(parent, parent_slot) != btrfs_header_blocknr(&node->header)); } - BUG_ON(nritems > NODEPTRS_PER_BLOCK); + BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); for (i = 0; nritems > 1 && i < nritems - 2; i++) { struct btrfs_key cpukey; - btrfs_disk_key_to_cpu(&cpukey, &node->keys[i + 1]); - BUG_ON(comp_keys(&node->keys[i], &cpukey) >= 0); + btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key); + BUG_ON(comp_keys(&node->ptrs[i].key, &cpukey) >= 0); } return 0; } -int check_leaf(struct ctree_path *path, int level) +static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, + int level) { int i; - struct leaf *leaf = &path->nodes[level]->leaf; - struct node *parent = NULL; + struct btrfs_leaf *leaf = &path->nodes[level]->leaf; + struct btrfs_node *parent = NULL; int parent_slot; u32 nritems = btrfs_header_nritems(&leaf->header); if (path->nodes[level + 1]) parent = &path->nodes[level + 1]->node; parent_slot = path->slots[level + 1]; - BUG_ON(leaf_free_space(leaf) < 0); + BUG_ON(btrfs_leaf_free_space(root, leaf) < 0); if (nritems == 0) return 0; if (parent) { struct btrfs_disk_key *parent_key; - parent_key = &parent->keys[parent_slot]; + parent_key = &parent->ptrs[parent_slot].key; BUG_ON(memcmp(parent_key, &leaf->items[0].key, sizeof(struct btrfs_disk_key))); - BUG_ON(parent->blockptrs[parent_slot] != + BUG_ON(btrfs_node_blockptr(parent, parent_slot) != btrfs_header_blocknr(&leaf->header)); } for (i = 0; nritems > 1 && i < nritems - 2; i++) { @@ -174,21 +178,23 @@ int check_leaf(struct ctree_path *path, int level) btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key); BUG_ON(comp_keys(&leaf->items[i].key, &cpukey) >= 0); - BUG_ON(leaf->items[i].offset != leaf->items[i + 1].offset + - leaf->items[i + 1].size); + BUG_ON(btrfs_item_offset(leaf->items + i) != + btrfs_item_end(leaf->items + i + 1)); if (i == 0) { - BUG_ON(leaf->items[i].offset + leaf->items[i].size != - LEAF_DATA_SIZE); + BUG_ON(btrfs_item_offset(leaf->items + i) + + btrfs_item_size(leaf->items + i) != + BTRFS_LEAF_DATA_SIZE(root)); } } return 0; } -int check_block(struct ctree_path *path, int level) +static int check_block(struct btrfs_root *root, struct btrfs_path *path, + int level) { if (level == 0) - return check_leaf(path, level); - return check_node(path, level); + return check_leaf(root, path, level); + return check_node(root, path, level); } /* @@ -200,7 +206,7 @@ int check_block(struct ctree_path *path, int level) * * slot may point to max if the key is bigger than all of the keys */ -int generic_bin_search(char *p, int item_size, struct btrfs_key *key, +static int generic_bin_search(char *p, int item_size, struct btrfs_key *key, int max, int *slot) { int low = 0; @@ -231,45 +237,46 @@ int generic_bin_search(char *p, int item_size, struct btrfs_key *key, * simple bin_search frontend that does the right thing for * leaves vs nodes */ -int bin_search(struct node *c, struct btrfs_key *key, int *slot) +static int bin_search(struct btrfs_node *c, struct btrfs_key *key, int *slot) { if (btrfs_is_leaf(c)) { - struct leaf *l = (struct leaf *)c; - return generic_bin_search((void *)l->items, sizeof(struct item), + struct btrfs_leaf *l = (struct btrfs_leaf *)c; + return generic_bin_search((void *)l->items, + sizeof(struct btrfs_item), key, btrfs_header_nritems(&c->header), slot); } else { - return generic_bin_search((void *)c->keys, - sizeof(struct btrfs_disk_key), + return generic_bin_search((void *)c->ptrs, + sizeof(struct btrfs_key_ptr), key, btrfs_header_nritems(&c->header), slot); } return -1; } -struct tree_buffer *read_node_slot(struct ctree_root *root, - struct tree_buffer *parent_buf, +static struct btrfs_buffer *read_node_slot(struct btrfs_root *root, + struct btrfs_buffer *parent_buf, int slot) { - struct node *node = &parent_buf->node; + struct btrfs_node *node = &parent_buf->node; if (slot < 0) return NULL; if (slot >= btrfs_header_nritems(&node->header)) return NULL; - return read_tree_block(root, node->blockptrs[slot]); + return read_tree_block(root, btrfs_node_blockptr(node, slot)); } -static int balance_level(struct ctree_root *root, struct ctree_path *path, - int level) +static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_path *path, int level) { - struct tree_buffer *right_buf; - struct tree_buffer *mid_buf; - struct tree_buffer *left_buf; - struct tree_buffer *parent_buf = NULL; - struct node *right = NULL; - struct node *mid; - struct node *left = NULL; - struct node *parent = NULL; + struct btrfs_buffer *right_buf; + struct btrfs_buffer *mid_buf; + struct btrfs_buffer *left_buf; + struct btrfs_buffer *parent_buf = NULL; + struct btrfs_node *right = NULL; + struct btrfs_node *mid; + struct btrfs_node *left = NULL; + struct btrfs_node *parent = NULL; int ret = 0; int wret; int pslot; @@ -281,14 +288,18 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, mid_buf = path->nodes[level]; mid = &mid_buf->node; - orig_ptr = mid->blockptrs[orig_slot]; + orig_ptr = btrfs_node_blockptr(mid, orig_slot); - if (level < MAX_LEVEL - 1) + if (level < BTRFS_MAX_LEVEL - 1) parent_buf = path->nodes[level + 1]; pslot = path->slots[level + 1]; + /* + * deal with the case where there is only one pointer in the root + * by promoting the node below to a root + */ if (!parent_buf) { - struct tree_buffer *child; + struct btrfs_buffer *child; u64 blocknr = mid_buf->blocknr; if (btrfs_header_nritems(&mid->header) != 1) @@ -300,15 +311,16 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, root->node = child; path->nodes[level] = NULL; /* once for the path */ - tree_block_release(root, mid_buf); + btrfs_block_release(root, mid_buf); /* once for the root ptr */ - tree_block_release(root, mid_buf); - clean_tree_block(root, mid_buf); - return free_extent(root, blocknr, 1); + btrfs_block_release(root, mid_buf); + clean_tree_block(trans, root, mid_buf); + return btrfs_free_extent(trans, root, blocknr, 1, 1); } parent = &parent_buf->node; - if (btrfs_header_nritems(&mid->header) > NODEPTRS_PER_BLOCK / 4) + if (btrfs_header_nritems(&mid->header) > + BTRFS_NODEPTRS_PER_BLOCK(root) / 4) return 0; left_buf = read_node_slot(root, parent_buf, pslot - 1); @@ -316,11 +328,11 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, /* first, try to make some room in the middle buffer */ if (left_buf) { - btrfs_cow_block(root, left_buf, parent_buf, - pslot - 1, &left_buf); + btrfs_cow_block(trans, root, left_buf, parent_buf, pslot - 1, + &left_buf); left = &left_buf->node; orig_slot += btrfs_header_nritems(&left->header); - wret = push_node_left(root, left_buf, mid_buf); + wret = push_node_left(trans, root, left_buf, mid_buf); if (wret < 0) ret = wret; } @@ -329,26 +341,28 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, * then try to empty the right most buffer into the middle */ if (right_buf) { - btrfs_cow_block(root, right_buf, parent_buf, - pslot + 1, &right_buf); + btrfs_cow_block(trans, root, right_buf, parent_buf, pslot + 1, + &right_buf); right = &right_buf->node; - wret = push_node_left(root, mid_buf, right_buf); + wret = push_node_left(trans, root, mid_buf, right_buf); if (wret < 0) ret = wret; if (btrfs_header_nritems(&right->header) == 0) { u64 blocknr = right_buf->blocknr; - tree_block_release(root, right_buf); - clean_tree_block(root, right_buf); + btrfs_block_release(root, right_buf); + clean_tree_block(trans, root, right_buf); right_buf = NULL; right = NULL; - wret = del_ptr(root, path, level + 1, pslot + 1); + wret = del_ptr(trans, root, path, level + 1, pslot + + 1); if (wret) ret = wret; - wret = free_extent(root, blocknr, 1); + wret = btrfs_free_extent(trans, root, blocknr, 1, 1); if (wret) ret = wret; } else { - memcpy(parent->keys + pslot + 1, right->keys, + memcpy(&parent->ptrs[pslot + 1].key, + &right->ptrs[0].key, sizeof(struct btrfs_disk_key)); BUG_ON(list_empty(&parent_buf->dirty)); } @@ -364,7 +378,7 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, * right */ BUG_ON(!left_buf); - wret = balance_node_right(root, mid_buf, left_buf); + wret = balance_node_right(trans, root, mid_buf, left_buf); if (wret < 0) ret = wret; BUG_ON(wret == 1); @@ -372,19 +386,19 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, if (btrfs_header_nritems(&mid->header) == 0) { /* we've managed to empty the middle node, drop it */ u64 blocknr = mid_buf->blocknr; - tree_block_release(root, mid_buf); - clean_tree_block(root, mid_buf); + btrfs_block_release(root, mid_buf); + clean_tree_block(trans, root, mid_buf); mid_buf = NULL; mid = NULL; - wret = del_ptr(root, path, level + 1, pslot); + wret = del_ptr(trans, root, path, level + 1, pslot); if (wret) ret = wret; - wret = free_extent(root, blocknr, 1); + wret = btrfs_free_extent(trans, root, blocknr, 1, 1); if (wret) ret = wret; } else { /* update the parent key to reflect our changes */ - memcpy(parent->keys + pslot, mid->keys, + memcpy(&parent->ptrs[pslot].key, &mid->ptrs[0].key, sizeof(struct btrfs_disk_key)); BUG_ON(list_empty(&parent_buf->dirty)); } @@ -397,21 +411,22 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, path->slots[level + 1] -= 1; path->slots[level] = orig_slot; if (mid_buf) - tree_block_release(root, mid_buf); + btrfs_block_release(root, mid_buf); } else { orig_slot -= btrfs_header_nritems(&left->header); path->slots[level] = orig_slot; } } /* double check we haven't messed things up */ - check_block(path, level); - if (orig_ptr != path->nodes[level]->node.blockptrs[path->slots[level]]) + check_block(root, path, level); + if (orig_ptr != btrfs_node_blockptr(&path->nodes[level]->node, + path->slots[level])) BUG(); if (right_buf) - tree_block_release(root, right_buf); + btrfs_block_release(root, right_buf); if (left_buf) - tree_block_release(root, left_buf); + btrfs_block_release(root, left_buf); return ret; } @@ -428,12 +443,13 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path, * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if * possible) */ -int search_slot(struct ctree_root *root, struct btrfs_key *key, - struct ctree_path *p, int ins_len, int cow) +int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_key *key, struct btrfs_path *p, int + ins_len, int cow) { - struct tree_buffer *b; - struct tree_buffer *cow_buf; - struct node *c; + struct btrfs_buffer *b; + struct btrfs_buffer *cow_buf; + struct btrfs_node *c; int slot; int ret; int level; @@ -445,14 +461,15 @@ again: level = btrfs_header_level(&b->node.header); if (cow) { int wret; - wret = btrfs_cow_block(root, b, p->nodes[level + 1], - p->slots[level + 1], &cow_buf); + wret = btrfs_cow_block(trans, root, b, p->nodes[level + + 1], p->slots[level + 1], + &cow_buf); b = cow_buf; } BUG_ON(!cow && ins_len); c = &b->node; p->nodes[level] = b; - ret = check_block(p, level); + ret = check_block(root, p, level); if (ret) return -1; ret = bin_search(c, key, &slot); @@ -461,8 +478,8 @@ again: slot -= 1; p->slots[level] = slot; if (ins_len > 0 && btrfs_header_nritems(&c->header) == - NODEPTRS_PER_BLOCK) { - int sret = split_node(root, p, level); + BTRFS_NODEPTRS_PER_BLOCK(root)) { + int sret = split_node(trans, root, p, level); BUG_ON(sret > 0); if (sret) return sret; @@ -470,7 +487,8 @@ again: c = &b->node; slot = p->slots[level]; } else if (ins_len < 0) { - int sret = balance_level(root, p, level); + int sret = balance_level(trans, root, p, + level); if (sret) return sret; b = p->nodes[level]; @@ -480,13 +498,13 @@ again: slot = p->slots[level]; BUG_ON(btrfs_header_nritems(&c->header) == 1); } - b = read_tree_block(root, c->blockptrs[slot]); + b = read_tree_block(root, btrfs_node_blockptr(c, slot)); } else { - struct leaf *l = (struct leaf *)c; + struct btrfs_leaf *l = (struct btrfs_leaf *)c; p->slots[level] = slot; - if (ins_len > 0 && leaf_free_space(l) < - sizeof(struct item) + ins_len) { - int sret = split_leaf(root, p, ins_len); + 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); BUG_ON(sret > 0); if (sret) return sret; @@ -509,19 +527,19 @@ again: * If this fails to write a tree block, it returns -1, but continues * fixing up the blocks in ram so the tree is consistent. */ -static int fixup_low_keys(struct ctree_root *root, - struct ctree_path *path, struct btrfs_disk_key *key, - int level) +static int fixup_low_keys(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_path *path, struct btrfs_disk_key + *key, int level) { int i; int ret = 0; - for (i = level; i < MAX_LEVEL; i++) { - struct node *t; + for (i = level; i < BTRFS_MAX_LEVEL; i++) { + struct btrfs_node *t; int tslot = path->slots[i]; if (!path->nodes[i]) break; t = &path->nodes[i]->node; - memcpy(t->keys + tslot, key, sizeof(*key)); + memcpy(&t->ptrs[tslot].key, key, sizeof(*key)); BUG_ON(list_empty(&path->nodes[i]->dirty)); if (tslot != 0) break; @@ -536,11 +554,12 @@ static int fixup_low_keys(struct ctree_root *root, * returns 0 if some ptrs were pushed left, < 0 if there was some horrible * error, and > 0 if there was no room in the left hand block. */ -static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf, - struct tree_buffer *src_buf) +static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_buffer *dst_buf, struct + btrfs_buffer *src_buf) { - struct node *src = &src_buf->node; - struct node *dst = &dst_buf->node; + struct btrfs_node *src = &src_buf->node; + struct btrfs_node *dst = &dst_buf->node; int push_items = 0; int src_nritems; int dst_nritems; @@ -548,7 +567,7 @@ static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf, src_nritems = btrfs_header_nritems(&src->header); dst_nritems = btrfs_header_nritems(&dst->header); - push_items = NODEPTRS_PER_BLOCK - dst_nritems; + push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; if (push_items <= 0) { return 1; } @@ -556,16 +575,12 @@ static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf, if (src_nritems < push_items) push_items = src_nritems; - memcpy(dst->keys + dst_nritems, src->keys, - push_items * sizeof(struct btrfs_disk_key)); - memcpy(dst->blockptrs + dst_nritems, src->blockptrs, - push_items * sizeof(u64)); + memcpy(dst->ptrs + dst_nritems, src->ptrs, + push_items * sizeof(struct btrfs_key_ptr)); if (push_items < src_nritems) { - memmove(src->keys, src->keys + push_items, + memmove(src->ptrs, src->ptrs + push_items, (src_nritems - push_items) * - sizeof(struct btrfs_disk_key)); - memmove(src->blockptrs, src->blockptrs + push_items, - (src_nritems - push_items) * sizeof(u64)); + sizeof(struct btrfs_key_ptr)); } btrfs_set_header_nritems(&src->header, src_nritems - push_items); btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); @@ -583,12 +598,12 @@ static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf, * * this will only push up to 1/2 the contents of the left node over */ -static int balance_node_right(struct ctree_root *root, - struct tree_buffer *dst_buf, - struct tree_buffer *src_buf) +static int balance_node_right(struct btrfs_trans_handle *trans, struct + btrfs_root *root, struct btrfs_buffer *dst_buf, + struct btrfs_buffer *src_buf) { - struct node *src = &src_buf->node; - struct node *dst = &dst_buf->node; + struct btrfs_node *src = &src_buf->node; + struct btrfs_node *dst = &dst_buf->node; int push_items = 0; int max_push; int src_nritems; @@ -597,7 +612,7 @@ static int balance_node_right(struct ctree_root *root, src_nritems = btrfs_header_nritems(&src->header); dst_nritems = btrfs_header_nritems(&dst->header); - push_items = NODEPTRS_PER_BLOCK - dst_nritems; + push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; if (push_items <= 0) { return 1; } @@ -609,14 +624,10 @@ static int balance_node_right(struct ctree_root *root, if (max_push < push_items) push_items = max_push; - memmove(dst->keys + push_items, dst->keys, - dst_nritems * sizeof(struct btrfs_disk_key)); - memmove(dst->blockptrs + push_items, dst->blockptrs, - dst_nritems * sizeof(u64)); - memcpy(dst->keys, src->keys + src_nritems - push_items, - push_items * sizeof(struct btrfs_disk_key)); - memcpy(dst->blockptrs, src->blockptrs + src_nritems - push_items, - push_items * sizeof(u64)); + memmove(dst->ptrs + push_items, dst->ptrs, + dst_nritems * sizeof(struct btrfs_key_ptr)); + memcpy(dst->ptrs, src->ptrs + src_nritems - push_items, + push_items * sizeof(struct btrfs_key_ptr)); btrfs_set_header_nritems(&src->header, src_nritems - push_items); btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); @@ -633,34 +644,32 @@ static int balance_node_right(struct ctree_root *root, * * returns zero on success or < 0 on failure. */ -static int insert_new_root(struct ctree_root *root, - struct ctree_path *path, int level) +static int insert_new_root(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_path *path, int level) { - struct tree_buffer *t; - struct node *lower; - struct node *c; + struct btrfs_buffer *t; + struct btrfs_node *lower; + struct btrfs_node *c; struct btrfs_disk_key *lower_key; BUG_ON(path->nodes[level]); BUG_ON(path->nodes[level-1] != root->node); - t = alloc_free_block(root); + t = btrfs_alloc_free_block(trans, root); c = &t->node; - memset(c, 0, sizeof(c)); + memset(c, 0, root->blocksize); btrfs_set_header_nritems(&c->header, 1); btrfs_set_header_level(&c->header, level); btrfs_set_header_blocknr(&c->header, t->blocknr); - btrfs_set_header_parentid(&c->header, - btrfs_header_parentid(&root->node->node.header)); lower = &path->nodes[level-1]->node; if (btrfs_is_leaf(lower)) - lower_key = &((struct leaf *)lower)->items[0].key; + lower_key = &((struct btrfs_leaf *)lower)->items[0].key; else - lower_key = lower->keys; - memcpy(c->keys, lower_key, sizeof(struct btrfs_disk_key)); - c->blockptrs[0] = path->nodes[level-1]->blocknr; + lower_key = &lower->ptrs[0].key; + memcpy(&c->ptrs[0].key, lower_key, sizeof(struct btrfs_disk_key)); + btrfs_set_node_blockptr(c, 0, path->nodes[level - 1]->blocknr); /* the super has an extra ref to root->node */ - tree_block_release(root, root->node); + btrfs_block_release(root, root->node); root->node = t; t->count++; path->nodes[level] = t; @@ -677,11 +686,11 @@ static int insert_new_root(struct ctree_root *root, * * returns zero on success and < 0 on any error */ -static int insert_ptr(struct ctree_root *root, - struct ctree_path *path, struct btrfs_disk_key *key, - u64 blocknr, int slot, int level) +static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_path *path, struct btrfs_disk_key + *key, u64 blocknr, int slot, int level) { - struct node *lower; + struct btrfs_node *lower; int nritems; BUG_ON(!path->nodes[level]); @@ -689,19 +698,15 @@ static int insert_ptr(struct ctree_root *root, nritems = btrfs_header_nritems(&lower->header); if (slot > nritems) BUG(); - if (nritems == NODEPTRS_PER_BLOCK) + if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) BUG(); if (slot != nritems) { - memmove(lower->keys + slot + 1, lower->keys + slot, - (nritems - slot) * sizeof(struct btrfs_disk_key)); - memmove(lower->blockptrs + slot + 1, lower->blockptrs + slot, - (nritems - slot) * sizeof(u64)); + memmove(lower->ptrs + slot + 1, lower->ptrs + slot, + (nritems - slot) * sizeof(struct btrfs_key_ptr)); } - memcpy(lower->keys + slot, key, sizeof(struct btrfs_disk_key)); - lower->blockptrs[slot] = blocknr; + memcpy(&lower->ptrs[slot].key, key, sizeof(struct btrfs_disk_key)); + btrfs_set_node_blockptr(lower, slot, blocknr); btrfs_set_header_nritems(&lower->header, nritems + 1); - if (lower->keys[1].objectid == 0) - BUG(); BUG_ON(list_empty(&path->nodes[level]->dirty)); return 0; } @@ -715,13 +720,13 @@ static int insert_ptr(struct ctree_root *root, * * returns 0 on success and < 0 on failure */ -static int split_node(struct ctree_root *root, struct ctree_path *path, - int level) +static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_path *path, int level) { - struct tree_buffer *t; - struct node *c; - struct tree_buffer *split_buffer; - struct node *split; + struct btrfs_buffer *t; + struct btrfs_node *c; + struct btrfs_buffer *split_buffer; + struct btrfs_node *split; int mid; int ret; int wret; @@ -731,39 +736,37 @@ static int split_node(struct ctree_root *root, struct ctree_path *path, c = &t->node; if (t == root->node) { /* trying to split the root, lets make a new one */ - ret = insert_new_root(root, path, level + 1); + ret = insert_new_root(trans, root, path, level + 1); if (ret) return ret; } c_nritems = btrfs_header_nritems(&c->header); - split_buffer = alloc_free_block(root); + split_buffer = btrfs_alloc_free_block(trans, root); split = &split_buffer->node; btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header)); + btrfs_set_header_level(&split->header, btrfs_header_level(&c->header)); btrfs_set_header_blocknr(&split->header, split_buffer->blocknr); - btrfs_set_header_parentid(&split->header, - btrfs_header_parentid(&root->node->node.header)); mid = (c_nritems + 1) / 2; - memcpy(split->keys, c->keys + mid, - (c_nritems - mid) * sizeof(struct btrfs_disk_key)); - memcpy(split->blockptrs, c->blockptrs + mid, - (c_nritems - mid) * sizeof(u64)); + memcpy(split->ptrs, c->ptrs + mid, + (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); btrfs_set_header_nritems(&split->header, c_nritems - mid); btrfs_set_header_nritems(&c->header, mid); ret = 0; BUG_ON(list_empty(&t->dirty)); - wret = insert_ptr(root, path, split->keys, split_buffer->blocknr, - path->slots[level + 1] + 1, level + 1); + wret = insert_ptr(trans, root, path, &split->ptrs[0].key, + split_buffer->blocknr, path->slots[level + 1] + 1, + level + 1); if (wret) ret = wret; if (path->slots[level] >= mid) { path->slots[level] -= mid; - tree_block_release(root, t); + btrfs_block_release(root, t); path->nodes[level] = split_buffer; path->slots[level + 1] += 1; } else { - tree_block_release(root, split_buffer); + btrfs_block_release(root, split_buffer); } return ret; } @@ -773,16 +776,16 @@ static int split_node(struct ctree_root *root, struct ctree_path *path, * and nr indicate which items in the leaf to check. This totals up the * space used both by the item structs and the item data */ -static int leaf_space_used(struct leaf *l, int start, int nr) +static int leaf_space_used(struct btrfs_leaf *l, int start, int nr) { int data_len; int end = start + nr - 1; if (!nr) return 0; - data_len = l->items[start].offset + l->items[start].size; - data_len = data_len - l->items[end].offset; - data_len += sizeof(struct item) * nr; + 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; return data_len; } @@ -793,20 +796,20 @@ static int leaf_space_used(struct leaf *l, int start, int nr) * returns 1 if the push failed because the other node didn't have enough * room, 0 if everything worked out and < 0 if there were major errors. */ -static int push_leaf_right(struct ctree_root *root, struct ctree_path *path, - int data_size) +static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_path *path, int data_size) { - struct tree_buffer *left_buf = path->nodes[0]; - struct leaf *left = &left_buf->leaf; - struct leaf *right; - struct tree_buffer *right_buf; - struct tree_buffer *upper; + struct btrfs_buffer *left_buf = path->nodes[0]; + struct btrfs_leaf *left = &left_buf->leaf; + struct btrfs_leaf *right; + struct btrfs_buffer *right_buf; + struct btrfs_buffer *upper; int slot; int i; int free_space; int push_space = 0; int push_items = 0; - struct item *item; + struct btrfs_item *item; u32 left_nritems; u32 right_nritems; @@ -818,19 +821,20 @@ static int push_leaf_right(struct ctree_root *root, struct ctree_path *path, if (slot >= btrfs_header_nritems(&upper->node.header) - 1) { return 1; } - right_buf = read_tree_block(root, upper->node.blockptrs[slot + 1]); + right_buf = read_tree_block(root, btrfs_node_blockptr(&upper->node, + slot + 1)); right = &right_buf->leaf; - free_space = leaf_free_space(right); - if (free_space < data_size + sizeof(struct item)) { - tree_block_release(root, right_buf); + free_space = btrfs_leaf_free_space(root, right); + if (free_space < data_size + sizeof(struct btrfs_item)) { + btrfs_block_release(root, right_buf); return 1; } /* cow and double check */ - btrfs_cow_block(root, right_buf, upper, slot + 1, &right_buf); + btrfs_cow_block(trans, root, right_buf, upper, slot + 1, &right_buf); right = &right_buf->leaf; - free_space = leaf_free_space(right); - if (free_space < data_size + sizeof(struct item)) { - tree_block_release(root, right_buf); + free_space = btrfs_leaf_free_space(root, right); + if (free_space < data_size + sizeof(struct btrfs_item)) { + btrfs_block_release(root, right_buf); return 1; } @@ -839,59 +843,59 @@ static int push_leaf_right(struct ctree_root *root, struct ctree_path *path, item = left->items + i; if (path->slots[0] == i) push_space += data_size + sizeof(*item); - if (item->size + sizeof(*item) + push_space > free_space) + if (btrfs_item_size(item) + sizeof(*item) + push_space > + free_space) break; push_items++; - push_space += item->size + sizeof(*item); + push_space += btrfs_item_size(item) + sizeof(*item); } if (push_items == 0) { - tree_block_release(root, right_buf); + btrfs_block_release(root, right_buf); return 1; } right_nritems = btrfs_header_nritems(&right->header); /* push left to right */ - push_space = left->items[left_nritems - push_items].offset + - left->items[left_nritems - push_items].size; - push_space -= leaf_data_end(left); + push_space = btrfs_item_end(left->items + left_nritems - push_items); + push_space -= leaf_data_end(root, left); /* make room in the right data area */ - memmove(right->data + leaf_data_end(right) - push_space, - right->data + leaf_data_end(right), - LEAF_DATA_SIZE - leaf_data_end(right)); + memmove(btrfs_leaf_data(right) + leaf_data_end(root, right) - + push_space, btrfs_leaf_data(right) + leaf_data_end(root, right), + BTRFS_LEAF_DATA_SIZE(root) - leaf_data_end(root, right)); /* copy from the left data area */ - memcpy(right->data + LEAF_DATA_SIZE - push_space, - left->data + leaf_data_end(left), - push_space); + memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - push_space, + btrfs_leaf_data(left) + leaf_data_end(root, left), push_space); memmove(right->items + push_items, right->items, - right_nritems * sizeof(struct item)); + right_nritems * sizeof(struct btrfs_item)); /* copy the items from left to right */ memcpy(right->items, left->items + left_nritems - push_items, - push_items * sizeof(struct item)); + push_items * sizeof(struct btrfs_item)); /* update the item pointers */ right_nritems += push_items; btrfs_set_header_nritems(&right->header, right_nritems); - push_space = LEAF_DATA_SIZE; + push_space = BTRFS_LEAF_DATA_SIZE(root); for (i = 0; i < right_nritems; i++) { - right->items[i].offset = push_space - right->items[i].size; - push_space = right->items[i].offset; + btrfs_set_item_offset(right->items + i, push_space - + btrfs_item_size(right->items + i)); + push_space = btrfs_item_offset(right->items + i); } left_nritems -= push_items; btrfs_set_header_nritems(&left->header, left_nritems); BUG_ON(list_empty(&left_buf->dirty)); BUG_ON(list_empty(&right_buf->dirty)); - memcpy(upper->node.keys + slot + 1, + memcpy(&upper->node.ptrs[slot + 1].key, &right->items[0].key, sizeof(struct btrfs_disk_key)); BUG_ON(list_empty(&upper->dirty)); /* then fixup the leaf pointer in the path */ if (path->slots[0] >= left_nritems) { path->slots[0] -= left_nritems; - tree_block_release(root, path->nodes[0]); + btrfs_block_release(root, path->nodes[0]); path->nodes[0] = right_buf; path->slots[1] += 1; } else { - tree_block_release(root, right_buf); + btrfs_block_release(root, right_buf); } return 0; } @@ -899,19 +903,19 @@ static int push_leaf_right(struct ctree_root *root, struct ctree_path *path, * push some data in the path leaf to the left, trying to free up at * least data_size bytes. returns zero if the push worked, nonzero otherwise */ -static int push_leaf_left(struct ctree_root *root, struct ctree_path *path, - int data_size) +static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_path *path, int data_size) { - struct tree_buffer *right_buf = path->nodes[0]; - struct leaf *right = &right_buf->leaf; - struct tree_buffer *t; - struct leaf *left; + struct btrfs_buffer *right_buf = path->nodes[0]; + struct btrfs_leaf *right = &right_buf->leaf; + struct btrfs_buffer *t; + struct btrfs_leaf *left; int slot; int i; int free_space; int push_space = 0; int push_items = 0; - struct item *item; + struct btrfs_item *item; u32 old_left_nritems; int ret = 0; int wret; @@ -923,20 +927,21 @@ static int push_leaf_left(struct ctree_root *root, struct ctree_path *path, if (!path->nodes[1]) { return 1; } - t = read_tree_block(root, path->nodes[1]->node.blockptrs[slot - 1]); + t = read_tree_block(root, btrfs_node_blockptr(&path->nodes[1]->node, + slot - 1)); left = &t->leaf; - free_space = leaf_free_space(left); - if (free_space < data_size + sizeof(struct item)) { - tree_block_release(root, t); + free_space = btrfs_leaf_free_space(root, left); + if (free_space < data_size + sizeof(struct btrfs_item)) { + btrfs_block_release(root, t); return 1; } /* cow and double check */ - btrfs_cow_block(root, t, path->nodes[1], slot - 1, &t); + btrfs_cow_block(trans, root, t, path->nodes[1], slot - 1, &t); left = &t->leaf; - free_space = leaf_free_space(left); - if (free_space < data_size + sizeof(struct item)) { - tree_block_release(root, t); + free_space = btrfs_leaf_free_space(root, left); + if (free_space < data_size + sizeof(struct btrfs_item)) { + btrfs_block_release(root, t); return 1; } @@ -944,63 +949,72 @@ static int push_leaf_left(struct ctree_root *root, struct ctree_path *path, item = right->items + i; if (path->slots[0] == i) push_space += data_size + sizeof(*item); - if (item->size + sizeof(*item) + push_space > free_space) + if (btrfs_item_size(item) + sizeof(*item) + push_space > + free_space) break; push_items++; - push_space += item->size + sizeof(*item); + push_space += btrfs_item_size(item) + sizeof(*item); } if (push_items == 0) { - tree_block_release(root, t); + btrfs_block_release(root, t); return 1; } /* push data from right to left */ memcpy(left->items + btrfs_header_nritems(&left->header), - right->items, push_items * sizeof(struct item)); - push_space = LEAF_DATA_SIZE - right->items[push_items -1].offset; - memcpy(left->data + leaf_data_end(left) - push_space, - right->data + right->items[push_items - 1].offset, + right->items, push_items * sizeof(struct btrfs_item)); + push_space = BTRFS_LEAF_DATA_SIZE(root) - + btrfs_item_offset(right->items + push_items -1); + memcpy(btrfs_leaf_data(left) + leaf_data_end(root, left) - push_space, + btrfs_leaf_data(right) + + btrfs_item_offset(right->items + push_items - 1), push_space); old_left_nritems = btrfs_header_nritems(&left->header); BUG_ON(old_left_nritems < 0); - for(i = old_left_nritems; i < old_left_nritems + push_items; i++) { - left->items[i].offset -= LEAF_DATA_SIZE - - left->items[old_left_nritems -1].offset; + for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { + u32 ioff = btrfs_item_offset(left->items + i); + btrfs_set_item_offset(left->items + i, ioff - + (BTRFS_LEAF_DATA_SIZE(root) - + btrfs_item_offset(left->items + + old_left_nritems - 1))); } btrfs_set_header_nritems(&left->header, old_left_nritems + push_items); /* fixup right node */ - push_space = right->items[push_items-1].offset - leaf_data_end(right); - memmove(right->data + LEAF_DATA_SIZE - push_space, right->data + - leaf_data_end(right), push_space); + push_space = btrfs_item_offset(right->items + push_items - 1) - + leaf_data_end(root, right); + memmove(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - + push_space, btrfs_leaf_data(right) + + leaf_data_end(root, right), push_space); memmove(right->items, right->items + push_items, (btrfs_header_nritems(&right->header) - push_items) * - sizeof(struct item)); + sizeof(struct btrfs_item)); btrfs_set_header_nritems(&right->header, btrfs_header_nritems(&right->header) - push_items); - push_space = LEAF_DATA_SIZE; + push_space = BTRFS_LEAF_DATA_SIZE(root); for (i = 0; i < btrfs_header_nritems(&right->header); i++) { - right->items[i].offset = push_space - right->items[i].size; - push_space = right->items[i].offset; + btrfs_set_item_offset(right->items + i, push_space - + btrfs_item_size(right->items + i)); + push_space = btrfs_item_offset(right->items + i); } BUG_ON(list_empty(&t->dirty)); BUG_ON(list_empty(&right_buf->dirty)); - wret = fixup_low_keys(root, path, &right->items[0].key, 1); + wret = fixup_low_keys(trans, root, path, &right->items[0].key, 1); if (wret) ret = wret; /* then fixup the leaf pointer in the path */ if (path->slots[0] < push_items) { path->slots[0] += old_left_nritems; - tree_block_release(root, path->nodes[0]); + btrfs_block_release(root, path->nodes[0]); path->nodes[0] = t; path->slots[1] -= 1; } else { - tree_block_release(root, t); + btrfs_block_release(root, t); path->slots[0] -= push_items; } BUG_ON(path->slots[0] < 0); @@ -1013,74 +1027,85 @@ static int push_leaf_left(struct ctree_root *root, struct ctree_path *path, * * returns 0 if all went well and < 0 on failure. */ -static int split_leaf(struct ctree_root *root, struct ctree_path *path, - int data_size) +static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_path *path, int data_size) { - struct tree_buffer *l_buf; - struct leaf *l; + struct btrfs_buffer *l_buf; + struct btrfs_leaf *l; u32 nritems; int mid; int slot; - struct leaf *right; - struct tree_buffer *right_buffer; - int space_needed = data_size + sizeof(struct item); + struct btrfs_leaf *right; + struct btrfs_buffer *right_buffer; + int space_needed = data_size + sizeof(struct btrfs_item); int data_copy_size; int rt_data_off; int i; int ret; int wret; + /* first try to make some room by pushing left and right */ + wret = push_leaf_left(trans, root, path, data_size); + if (wret < 0) + return wret; + if (wret) { + wret = push_leaf_right(trans, root, path, data_size); + if (wret < 0) + return wret; + } l_buf = path->nodes[0]; l = &l_buf->leaf; /* did the pushes work? */ - if (leaf_free_space(l) >= sizeof(struct item) + data_size) + if (btrfs_leaf_free_space(root, l) >= + sizeof(struct btrfs_item) + data_size) return 0; if (!path->nodes[1]) { - ret = insert_new_root(root, path, 1); + ret = insert_new_root(trans, root, path, 1); if (ret) return ret; } slot = path->slots[0]; nritems = btrfs_header_nritems(&l->header); mid = (nritems + 1)/ 2; - right_buffer = alloc_free_block(root); + right_buffer = btrfs_alloc_free_block(trans, root); BUG_ON(!right_buffer); BUG_ON(mid == nritems); right = &right_buffer->leaf; - memset(right, 0, sizeof(*right)); + 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 > - LEAF_DATA_SIZE) + BTRFS_LEAF_DATA_SIZE(root)) BUG(); } else { /* FIXME, just alloc a new leaf here */ if (leaf_space_used(l, 0, mid + 1) + space_needed > - LEAF_DATA_SIZE) + BTRFS_LEAF_DATA_SIZE(root)) BUG(); } btrfs_set_header_nritems(&right->header, nritems - mid); btrfs_set_header_blocknr(&right->header, right_buffer->blocknr); btrfs_set_header_level(&right->header, 0); - btrfs_set_header_parentid(&right->header, - btrfs_header_parentid(&root->node->node.header)); - data_copy_size = l->items[mid].offset + l->items[mid].size - - leaf_data_end(l); + data_copy_size = btrfs_item_end(l->items + mid) - + leaf_data_end(root, l); memcpy(right->items, l->items + mid, - (nritems - mid) * sizeof(struct item)); - memcpy(right->data + LEAF_DATA_SIZE - data_copy_size, - l->data + leaf_data_end(l), data_copy_size); - rt_data_off = LEAF_DATA_SIZE - - (l->items[mid].offset + l->items[mid].size); + (nritems - mid) * sizeof(struct btrfs_item)); + memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - + data_copy_size, btrfs_leaf_data(l) + + leaf_data_end(root, l), data_copy_size); + rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - + btrfs_item_end(l->items + mid); - for (i = 0; i < btrfs_header_nritems(&right->header); i++) - right->items[i].offset += rt_data_off; + for (i = 0; i < btrfs_header_nritems(&right->header); i++) { + u32 ioff = btrfs_item_offset(right->items + i); + btrfs_set_item_offset(right->items + i, ioff + rt_data_off); + } btrfs_set_header_nritems(&l->header, mid); ret = 0; - wret = insert_ptr(root, path, &right->items[0].key, + wret = insert_ptr(trans, root, path, &right->items[0].key, right_buffer->blocknr, path->slots[1] + 1, 1); if (wret) ret = wret; @@ -1088,12 +1113,12 @@ static int split_leaf(struct ctree_root *root, struct ctree_path *path, BUG_ON(list_empty(&l_buf->dirty)); BUG_ON(path->slots[0] != slot); if (mid <= slot) { - tree_block_release(root, path->nodes[0]); + btrfs_block_release(root, path->nodes[0]); path->nodes[0] = right_buffer; path->slots[0] -= mid; path->slots[1] += 1; } else - tree_block_release(root, right_buffer); + btrfs_block_release(root, right_buffer); BUG_ON(path->slots[0] < 0); return ret; } @@ -1102,17 +1127,17 @@ static int split_leaf(struct ctree_root *root, struct ctree_path *path, * Given a key and some data, insert an item into the tree. * This does all the path init required, making room in the tree if needed. */ -int insert_item(struct ctree_root *root, struct btrfs_key *cpu_key, - void *data, int data_size) +int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_path *path, struct btrfs_key + *cpu_key, u32 data_size) { int ret = 0; int slot; int slot_orig; - struct leaf *leaf; - struct tree_buffer *leaf_buf; + struct btrfs_leaf *leaf; + struct btrfs_buffer *leaf_buf; u32 nritems; unsigned int data_end; - struct ctree_path path; struct btrfs_disk_key disk_key; btrfs_cpu_key_to_disk(&disk_key, cpu_key); @@ -1120,66 +1145,89 @@ int insert_item(struct ctree_root *root, struct btrfs_key *cpu_key, /* create a root if there isn't one */ if (!root->node) BUG(); - init_path(&path); - ret = search_slot(root, cpu_key, &path, data_size, 1); + ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1); if (ret == 0) { - release_path(root, &path); + btrfs_release_path(root, path); return -EEXIST; } if (ret < 0) goto out; - slot_orig = path.slots[0]; - leaf_buf = path.nodes[0]; + slot_orig = path->slots[0]; + leaf_buf = path->nodes[0]; leaf = &leaf_buf->leaf; nritems = btrfs_header_nritems(&leaf->header); - data_end = leaf_data_end(leaf); + data_end = leaf_data_end(root, leaf); - if (leaf_free_space(leaf) < sizeof(struct item) + data_size) + if (btrfs_leaf_free_space(root, leaf) < + sizeof(struct btrfs_item) + data_size) BUG(); - slot = path.slots[0]; + slot = path->slots[0]; BUG_ON(slot < 0); if (slot != nritems) { int i; - unsigned int old_data = leaf->items[slot].offset + - leaf->items[slot].size; + unsigned int old_data = btrfs_item_end(leaf->items + slot); /* * item0..itemN ... dataN.offset..dataN.size .. data0.size */ /* first correct the data pointers */ - for (i = slot; i < nritems; i++) - leaf->items[i].offset -= data_size; + for (i = slot; i < nritems; i++) { + u32 ioff = btrfs_item_offset(leaf->items + i); + btrfs_set_item_offset(leaf->items + i, + ioff - data_size); + } /* shift the items */ memmove(leaf->items + slot + 1, leaf->items + slot, - (nritems - slot) * sizeof(struct item)); + (nritems - slot) * sizeof(struct btrfs_item)); /* shift the data */ - memmove(leaf->data + data_end - data_size, leaf->data + + memmove(btrfs_leaf_data(leaf) + data_end - data_size, + btrfs_leaf_data(leaf) + data_end, old_data - data_end); data_end = old_data; } - /* copy the new data in */ + /* setup the item for the new data */ memcpy(&leaf->items[slot].key, &disk_key, sizeof(struct btrfs_disk_key)); - leaf->items[slot].offset = data_end - data_size; - leaf->items[slot].size = data_size; - memcpy(leaf->data + data_end - data_size, data, data_size); + btrfs_set_item_offset(leaf->items + slot, data_end - data_size); + btrfs_set_item_size(leaf->items + slot, data_size); btrfs_set_header_nritems(&leaf->header, nritems + 1); ret = 0; if (slot == 0) - ret = fixup_low_keys(root, &path, &disk_key, 1); + ret = fixup_low_keys(trans, root, path, &disk_key, 1); BUG_ON(list_empty(&leaf_buf->dirty)); - if (leaf_free_space(leaf) < 0) + if (btrfs_leaf_free_space(root, leaf) < 0) BUG(); - check_leaf(&path, 0); + check_leaf(root, path, 0); out: - release_path(root, &path); + return ret; +} + +/* + * Given a key and some data, insert an item into the tree. + * This does all the path init required, making room in the tree if needed. + */ +int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root + *root, struct btrfs_key *cpu_key, void *data, u32 + data_size) +{ + int ret = 0; + struct btrfs_path path; + u8 *ptr; + + btrfs_init_path(&path); + ret = btrfs_insert_empty_item(trans, root, &path, cpu_key, data_size); + if (!ret) { + ptr = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0], u8); + memcpy(ptr, data, data_size); + } + btrfs_release_path(root, &path); return ret; } @@ -1190,11 +1238,11 @@ out: * continuing all the way the root if required. The root is converted into * a leaf if all the nodes are emptied. */ -static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, - int slot) +static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, + struct btrfs_path *path, int level, int slot) { - struct node *node; - struct tree_buffer *parent = path->nodes[level]; + struct btrfs_node *node; + struct btrfs_buffer *parent = path->nodes[level]; u32 nritems; int ret = 0; int wret; @@ -1202,11 +1250,8 @@ static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, node = &parent->node; nritems = btrfs_header_nritems(&node->header); if (slot != nritems -1) { - memmove(node->keys + slot, node->keys + slot + 1, - sizeof(struct btrfs_disk_key) * (nritems - slot - 1)); - memmove(node->blockptrs + slot, - node->blockptrs + slot + 1, - sizeof(u64) * (nritems - slot - 1)); + memmove(node->ptrs + slot, node->ptrs + slot + 1, + sizeof(struct btrfs_key_ptr) * (nritems - slot - 1)); } nritems--; btrfs_set_header_nritems(&node->header, nritems); @@ -1215,7 +1260,8 @@ static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, /* just turn the root into a leaf and break */ btrfs_set_header_level(&root->node->node.header, 0); } else if (slot == 0) { - wret = fixup_low_keys(root, path, node->keys, level + 1); + wret = fixup_low_keys(trans, root, path, &node->ptrs[0].key, + level + 1); if (wret) ret = wret; } @@ -1227,11 +1273,12 @@ static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, * delete the item at the leaf level in path. If that empties * the leaf, remove it from the tree */ -int del_item(struct ctree_root *root, struct ctree_path *path) +int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, + struct btrfs_path *path) { int slot; - struct leaf *leaf; - struct tree_buffer *leaf_buf; + struct btrfs_leaf *leaf; + struct btrfs_buffer *leaf_buf; int doff; int dsize; int ret = 0; @@ -1241,20 +1288,22 @@ int del_item(struct ctree_root *root, struct ctree_path *path) leaf_buf = path->nodes[0]; leaf = &leaf_buf->leaf; slot = path->slots[0]; - doff = leaf->items[slot].offset; - dsize = leaf->items[slot].size; + doff = btrfs_item_offset(leaf->items + slot); + dsize = btrfs_item_size(leaf->items + slot); nritems = btrfs_header_nritems(&leaf->header); if (slot != nritems - 1) { int i; - int data_end = leaf_data_end(leaf); - memmove(leaf->data + data_end + dsize, - leaf->data + data_end, + int data_end = leaf_data_end(root, leaf); + memmove(btrfs_leaf_data(leaf) + data_end + dsize, + btrfs_leaf_data(leaf) + data_end, doff - data_end); - for (i = slot + 1; i < nritems; i++) - leaf->items[i].offset += dsize; + for (i = slot + 1; i < nritems; i++) { + u32 ioff = btrfs_item_offset(leaf->items + i); + btrfs_set_item_offset(leaf->items + i, ioff + dsize); + } memmove(leaf->items + slot, leaf->items + slot + 1, - sizeof(struct item) * + sizeof(struct btrfs_item) * (nritems - slot - 1)); } btrfs_set_header_nritems(&leaf->header, nritems - 1); @@ -1265,53 +1314,55 @@ int del_item(struct ctree_root *root, struct ctree_path *path) btrfs_set_header_level(&leaf->header, 0); BUG_ON(list_empty(&leaf_buf->dirty)); } else { - clean_tree_block(root, leaf_buf); - wret = del_ptr(root, path, 1, path->slots[1]); + clean_tree_block(trans, root, leaf_buf); + wret = del_ptr(trans, root, path, 1, path->slots[1]); if (wret) ret = wret; - wret = free_extent(root, leaf_buf->blocknr, 1); + wret = btrfs_free_extent(trans, root, + leaf_buf->blocknr, 1, 1); if (wret) ret = wret; } } else { int used = leaf_space_used(leaf, 0, nritems); if (slot == 0) { - wret = fixup_low_keys(root, path, - &leaf->items[0].key, 1); + wret = fixup_low_keys(trans, root, path, + &leaf->items[0].key, 1); if (wret) ret = wret; } BUG_ON(list_empty(&leaf_buf->dirty)); /* delete the leaf if it is mostly empty */ - if (used < LEAF_DATA_SIZE / 3) { + if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { /* push_leaf_left fixes the path. * make sure the path still points to our leaf * for possible call to del_ptr below */ slot = path->slots[1]; leaf_buf->count++; - wret = push_leaf_left(root, path, 1); + wret = push_leaf_left(trans, root, path, 1); if (wret < 0) ret = wret; if (path->nodes[0] == leaf_buf && btrfs_header_nritems(&leaf->header)) { - wret = push_leaf_right(root, path, 1); + wret = push_leaf_right(trans, root, path, 1); if (wret < 0) ret = wret; } if (btrfs_header_nritems(&leaf->header) == 0) { u64 blocknr = leaf_buf->blocknr; - clean_tree_block(root, leaf_buf); - wret = del_ptr(root, path, 1, slot); + clean_tree_block(trans, root, leaf_buf); + wret = del_ptr(trans, root, path, 1, slot); if (wret) ret = wret; - tree_block_release(root, leaf_buf); - wret = free_extent(root, blocknr, 1); + btrfs_block_release(root, leaf_buf); + wret = btrfs_free_extent(trans, root, blocknr, + 1, 1); if (wret) ret = wret; } else { - tree_block_release(root, leaf_buf); + btrfs_block_release(root, leaf_buf); } } } @@ -1323,15 +1374,15 @@ int del_item(struct ctree_root *root, struct ctree_path *path) * returns 0 if it found something or 1 if there are no greater leaves. * returns < 0 on io errors. */ -int next_leaf(struct ctree_root *root, struct ctree_path *path) +int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) { int slot; int level = 1; u64 blocknr; - struct tree_buffer *c; - struct tree_buffer *next = NULL; + struct btrfs_buffer *c; + struct btrfs_buffer *next = NULL; - while(level < MAX_LEVEL) { + while(level < BTRFS_MAX_LEVEL) { if (!path->nodes[level]) return 1; slot = path->slots[level] + 1; @@ -1340,9 +1391,9 @@ int next_leaf(struct ctree_root *root, struct ctree_path *path) level++; continue; } - blocknr = c->node.blockptrs[slot]; + blocknr = btrfs_node_blockptr(&c->node, slot); if (next) - tree_block_release(root, next); + btrfs_block_release(root, next); next = read_tree_block(root, blocknr); break; } @@ -1350,14 +1401,13 @@ int next_leaf(struct ctree_root *root, struct ctree_path *path) while(1) { level--; c = path->nodes[level]; - tree_block_release(root, c); + btrfs_block_release(root, c); path->nodes[level] = next; path->slots[level] = 0; if (!level) break; - next = read_tree_block(root, next->node.blockptrs[0]); + next = read_tree_block(root, + btrfs_node_blockptr(&next->node, 0)); } return 0; } - -