1be0e5c09SChris Mason #include <stdio.h> 2be0e5c09SChris Mason #include <stdlib.h> 3be0e5c09SChris Mason #include "kerncompat.h" 4eb60ceacSChris Mason #include "radix-tree.h" 5eb60ceacSChris Mason #include "ctree.h" 6eb60ceacSChris Mason #include "disk-io.h" 7be0e5c09SChris Mason 85c680ed6SChris Mason #define SEARCH_READ 0 95c680ed6SChris Mason #define SEARCH_WRITE 1 105c680ed6SChris Mason 119a8dd150SChris Mason #define CTREE_EXTENT_PENDING 0 129a8dd150SChris Mason 135c680ed6SChris Mason int split_node(struct ctree_root *root, struct ctree_path *path, int level); 145c680ed6SChris Mason int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size); 159a8dd150SChris Mason struct tree_buffer *alloc_free_block(struct ctree_root *root); 169a8dd150SChris Mason int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks); 17d97e63b6SChris Mason 18be0e5c09SChris Mason static inline void init_path(struct ctree_path *p) 19be0e5c09SChris Mason { 20be0e5c09SChris Mason memset(p, 0, sizeof(*p)); 21be0e5c09SChris Mason } 22be0e5c09SChris Mason 23eb60ceacSChris Mason static void release_path(struct ctree_root *root, struct ctree_path *p) 24eb60ceacSChris Mason { 25eb60ceacSChris Mason int i; 26eb60ceacSChris Mason for (i = 0; i < MAX_LEVEL; i++) { 27eb60ceacSChris Mason if (!p->nodes[i]) 28eb60ceacSChris Mason break; 29eb60ceacSChris Mason tree_block_release(root, p->nodes[i]); 30eb60ceacSChris Mason } 31eb60ceacSChris Mason } 32eb60ceacSChris Mason 3374123bd7SChris Mason /* 3474123bd7SChris Mason * The leaf data grows from end-to-front in the node. 3574123bd7SChris Mason * this returns the address of the start of the last item, 3674123bd7SChris Mason * which is the stop of the leaf data stack 3774123bd7SChris Mason */ 38be0e5c09SChris Mason static inline unsigned int leaf_data_end(struct leaf *leaf) 39be0e5c09SChris Mason { 40be0e5c09SChris Mason unsigned int nr = leaf->header.nritems; 41be0e5c09SChris Mason if (nr == 0) 42d97e63b6SChris Mason return sizeof(leaf->data); 43be0e5c09SChris Mason return leaf->items[nr-1].offset; 44be0e5c09SChris Mason } 45be0e5c09SChris Mason 4674123bd7SChris Mason /* 4774123bd7SChris Mason * The space between the end of the leaf items and 4874123bd7SChris Mason * the start of the leaf data. IOW, how much room 4974123bd7SChris Mason * the leaf has left for both items and data 5074123bd7SChris Mason */ 51be0e5c09SChris Mason static inline int leaf_free_space(struct leaf *leaf) 52be0e5c09SChris Mason { 53be0e5c09SChris Mason int data_end = leaf_data_end(leaf); 54be0e5c09SChris Mason int nritems = leaf->header.nritems; 55be0e5c09SChris Mason char *items_end = (char *)(leaf->items + nritems + 1); 56be0e5c09SChris Mason return (char *)(leaf->data + data_end) - (char *)items_end; 57be0e5c09SChris Mason } 58be0e5c09SChris Mason 5974123bd7SChris Mason /* 6074123bd7SChris Mason * compare two keys in a memcmp fashion 6174123bd7SChris Mason */ 62be0e5c09SChris Mason int comp_keys(struct key *k1, struct key *k2) 63be0e5c09SChris Mason { 64be0e5c09SChris Mason if (k1->objectid > k2->objectid) 65be0e5c09SChris Mason return 1; 66be0e5c09SChris Mason if (k1->objectid < k2->objectid) 67be0e5c09SChris Mason return -1; 68be0e5c09SChris Mason if (k1->flags > k2->flags) 69be0e5c09SChris Mason return 1; 70be0e5c09SChris Mason if (k1->flags < k2->flags) 71be0e5c09SChris Mason return -1; 72be0e5c09SChris Mason if (k1->offset > k2->offset) 73be0e5c09SChris Mason return 1; 74be0e5c09SChris Mason if (k1->offset < k2->offset) 75be0e5c09SChris Mason return -1; 76be0e5c09SChris Mason return 0; 77be0e5c09SChris Mason } 7874123bd7SChris Mason 7974123bd7SChris Mason /* 8074123bd7SChris Mason * search for key in the array p. items p are item_size apart 8174123bd7SChris Mason * and there are 'max' items in p 8274123bd7SChris Mason * the slot in the array is returned via slot, and it points to 8374123bd7SChris Mason * the place where you would insert key if it is not found in 8474123bd7SChris Mason * the array. 8574123bd7SChris Mason * 8674123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 8774123bd7SChris Mason */ 88be0e5c09SChris Mason int generic_bin_search(char *p, int item_size, struct key *key, 89be0e5c09SChris Mason int max, int *slot) 90be0e5c09SChris Mason { 91be0e5c09SChris Mason int low = 0; 92be0e5c09SChris Mason int high = max; 93be0e5c09SChris Mason int mid; 94be0e5c09SChris Mason int ret; 95be0e5c09SChris Mason struct key *tmp; 96be0e5c09SChris Mason 97be0e5c09SChris Mason while(low < high) { 98be0e5c09SChris Mason mid = (low + high) / 2; 99be0e5c09SChris Mason tmp = (struct key *)(p + mid * item_size); 100be0e5c09SChris Mason ret = comp_keys(tmp, key); 101be0e5c09SChris Mason 102be0e5c09SChris Mason if (ret < 0) 103be0e5c09SChris Mason low = mid + 1; 104be0e5c09SChris Mason else if (ret > 0) 105be0e5c09SChris Mason high = mid; 106be0e5c09SChris Mason else { 107be0e5c09SChris Mason *slot = mid; 108be0e5c09SChris Mason return 0; 109be0e5c09SChris Mason } 110be0e5c09SChris Mason } 111be0e5c09SChris Mason *slot = low; 112be0e5c09SChris Mason return 1; 113be0e5c09SChris Mason } 114be0e5c09SChris Mason 115be0e5c09SChris Mason int bin_search(struct node *c, struct key *key, int *slot) 116be0e5c09SChris Mason { 117be0e5c09SChris Mason if (is_leaf(c->header.flags)) { 118be0e5c09SChris Mason struct leaf *l = (struct leaf *)c; 119be0e5c09SChris Mason return generic_bin_search((void *)l->items, sizeof(struct item), 120be0e5c09SChris Mason key, c->header.nritems, slot); 121be0e5c09SChris Mason } else { 122be0e5c09SChris Mason return generic_bin_search((void *)c->keys, sizeof(struct key), 123be0e5c09SChris Mason key, c->header.nritems, slot); 124be0e5c09SChris Mason } 125be0e5c09SChris Mason return -1; 126be0e5c09SChris Mason } 127be0e5c09SChris Mason 12874123bd7SChris Mason /* 12974123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 13074123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 13174123bd7SChris Mason * level of the path (level 0) 13274123bd7SChris Mason * 13374123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 13474123bd7SChris Mason * be inserted. 13574123bd7SChris Mason */ 1365c680ed6SChris Mason int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p, int ins_len) 137be0e5c09SChris Mason { 138eb60ceacSChris Mason struct tree_buffer *b = root->node; 139eb60ceacSChris Mason struct node *c; 140be0e5c09SChris Mason int slot; 141be0e5c09SChris Mason int ret; 142be0e5c09SChris Mason int level; 1435c680ed6SChris Mason 144eb60ceacSChris Mason b->count++; 145eb60ceacSChris Mason while (b) { 146eb60ceacSChris Mason c = &b->node; 147be0e5c09SChris Mason level = node_level(c->header.flags); 148eb60ceacSChris Mason p->nodes[level] = b; 149be0e5c09SChris Mason ret = bin_search(c, key, &slot); 150be0e5c09SChris Mason if (!is_leaf(c->header.flags)) { 151be0e5c09SChris Mason if (ret && slot > 0) 152be0e5c09SChris Mason slot -= 1; 153be0e5c09SChris Mason p->slots[level] = slot; 1545c680ed6SChris Mason if (ins_len && c->header.nritems == NODEPTRS_PER_BLOCK) { 1555c680ed6SChris Mason int sret = split_node(root, p, level); 1565c680ed6SChris Mason BUG_ON(sret > 0); 1575c680ed6SChris Mason if (sret) 1585c680ed6SChris Mason return sret; 1595c680ed6SChris Mason b = p->nodes[level]; 1605c680ed6SChris Mason c = &b->node; 1615c680ed6SChris Mason slot = p->slots[level]; 1625c680ed6SChris Mason } 163eb60ceacSChris Mason b = read_tree_block(root, c->blockptrs[slot]); 164be0e5c09SChris Mason continue; 165be0e5c09SChris Mason } else { 1665c680ed6SChris Mason struct leaf *l = (struct leaf *)c; 167be0e5c09SChris Mason p->slots[level] = slot; 1685c680ed6SChris Mason if (ins_len && leaf_free_space(l) < sizeof(struct item) + ins_len) { 1695c680ed6SChris Mason int sret = split_leaf(root, p, ins_len); 1705c680ed6SChris Mason BUG_ON(sret > 0); 1715c680ed6SChris Mason if (sret) 1725c680ed6SChris Mason return sret; 1735c680ed6SChris Mason } 174be0e5c09SChris Mason return ret; 175be0e5c09SChris Mason } 176be0e5c09SChris Mason } 177be0e5c09SChris Mason return -1; 178be0e5c09SChris Mason } 179be0e5c09SChris Mason 18074123bd7SChris Mason /* 18174123bd7SChris Mason * adjust the pointers going up the tree, starting at level 18274123bd7SChris Mason * making sure the right key of each node is points to 'key'. 18374123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 18474123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 18574123bd7SChris Mason * higher levels 18674123bd7SChris Mason */ 187eb60ceacSChris Mason static void fixup_low_keys(struct ctree_root *root, 188eb60ceacSChris Mason struct ctree_path *path, struct key *key, 189be0e5c09SChris Mason int level) 190be0e5c09SChris Mason { 191be0e5c09SChris Mason int i; 192be0e5c09SChris Mason for (i = level; i < MAX_LEVEL; i++) { 193eb60ceacSChris Mason struct node *t; 194be0e5c09SChris Mason int tslot = path->slots[i]; 195eb60ceacSChris Mason if (!path->nodes[i]) 196be0e5c09SChris Mason break; 197eb60ceacSChris Mason t = &path->nodes[i]->node; 198be0e5c09SChris Mason memcpy(t->keys + tslot, key, sizeof(*key)); 199eb60ceacSChris Mason write_tree_block(root, path->nodes[i]); 200be0e5c09SChris Mason if (tslot != 0) 201be0e5c09SChris Mason break; 202be0e5c09SChris Mason } 203be0e5c09SChris Mason } 204be0e5c09SChris Mason 20574123bd7SChris Mason /* 20674123bd7SChris Mason * try to push data from one node into the next node left in the 20774123bd7SChris Mason * tree. The src node is found at specified level in the path. 20874123bd7SChris Mason * If some bytes were pushed, return 0, otherwise return 1. 20974123bd7SChris Mason * 21074123bd7SChris Mason * Lower nodes/leaves in the path are not touched, higher nodes may 21174123bd7SChris Mason * be modified to reflect the push. 21274123bd7SChris Mason * 21374123bd7SChris Mason * The path is altered to reflect the push. 21474123bd7SChris Mason */ 215be0e5c09SChris Mason int push_node_left(struct ctree_root *root, struct ctree_path *path, int level) 216be0e5c09SChris Mason { 217be0e5c09SChris Mason int slot; 218be0e5c09SChris Mason struct node *left; 219be0e5c09SChris Mason struct node *right; 220be0e5c09SChris Mason int push_items = 0; 221be0e5c09SChris Mason int left_nritems; 222be0e5c09SChris Mason int right_nritems; 223eb60ceacSChris Mason struct tree_buffer *t; 224eb60ceacSChris Mason struct tree_buffer *right_buf; 225be0e5c09SChris Mason 226be0e5c09SChris Mason if (level == MAX_LEVEL - 1 || path->nodes[level + 1] == 0) 227be0e5c09SChris Mason return 1; 228be0e5c09SChris Mason slot = path->slots[level + 1]; 229be0e5c09SChris Mason if (slot == 0) 230be0e5c09SChris Mason return 1; 231be0e5c09SChris Mason 232eb60ceacSChris Mason t = read_tree_block(root, 233eb60ceacSChris Mason path->nodes[level + 1]->node.blockptrs[slot - 1]); 234eb60ceacSChris Mason left = &t->node; 235eb60ceacSChris Mason right_buf = path->nodes[level]; 236eb60ceacSChris Mason right = &right_buf->node; 237be0e5c09SChris Mason left_nritems = left->header.nritems; 238be0e5c09SChris Mason right_nritems = right->header.nritems; 239be0e5c09SChris Mason push_items = NODEPTRS_PER_BLOCK - (left_nritems + 1); 240eb60ceacSChris Mason if (push_items <= 0) { 241eb60ceacSChris Mason tree_block_release(root, t); 242be0e5c09SChris Mason return 1; 243eb60ceacSChris Mason } 244be0e5c09SChris Mason 245be0e5c09SChris Mason if (right_nritems < push_items) 246be0e5c09SChris Mason push_items = right_nritems; 247be0e5c09SChris Mason memcpy(left->keys + left_nritems, right->keys, 248be0e5c09SChris Mason push_items * sizeof(struct key)); 249be0e5c09SChris Mason memcpy(left->blockptrs + left_nritems, right->blockptrs, 250be0e5c09SChris Mason push_items * sizeof(u64)); 251be0e5c09SChris Mason memmove(right->keys, right->keys + push_items, 252be0e5c09SChris Mason (right_nritems - push_items) * sizeof(struct key)); 253be0e5c09SChris Mason memmove(right->blockptrs, right->blockptrs + push_items, 254be0e5c09SChris Mason (right_nritems - push_items) * sizeof(u64)); 255be0e5c09SChris Mason right->header.nritems -= push_items; 256be0e5c09SChris Mason left->header.nritems += push_items; 257be0e5c09SChris Mason 258be0e5c09SChris Mason /* adjust the pointers going up the tree */ 259eb60ceacSChris Mason fixup_low_keys(root, path, right->keys, level + 1); 260eb60ceacSChris Mason 261eb60ceacSChris Mason write_tree_block(root, t); 262eb60ceacSChris Mason write_tree_block(root, right_buf); 263be0e5c09SChris Mason 264be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 265be0e5c09SChris Mason if (path->slots[level] < push_items) { 266be0e5c09SChris Mason path->slots[level] += left_nritems; 267eb60ceacSChris Mason tree_block_release(root, path->nodes[level]); 268eb60ceacSChris Mason path->nodes[level] = t; 269be0e5c09SChris Mason path->slots[level + 1] -= 1; 270be0e5c09SChris Mason } else { 271be0e5c09SChris Mason path->slots[level] -= push_items; 272eb60ceacSChris Mason tree_block_release(root, t); 273be0e5c09SChris Mason } 274be0e5c09SChris Mason return 0; 275be0e5c09SChris Mason } 276be0e5c09SChris Mason 27774123bd7SChris Mason /* 27874123bd7SChris Mason * try to push data from one node into the next node right in the 27974123bd7SChris Mason * tree. The src node is found at specified level in the path. 28074123bd7SChris Mason * If some bytes were pushed, return 0, otherwise return 1. 28174123bd7SChris Mason * 28274123bd7SChris Mason * Lower nodes/leaves in the path are not touched, higher nodes may 28374123bd7SChris Mason * be modified to reflect the push. 28474123bd7SChris Mason * 28574123bd7SChris Mason * The path is altered to reflect the push. 28674123bd7SChris Mason */ 287be0e5c09SChris Mason int push_node_right(struct ctree_root *root, struct ctree_path *path, int level) 288be0e5c09SChris Mason { 289be0e5c09SChris Mason int slot; 290eb60ceacSChris Mason struct tree_buffer *t; 291eb60ceacSChris Mason struct tree_buffer *src_buffer; 292be0e5c09SChris Mason struct node *dst; 293be0e5c09SChris Mason struct node *src; 294be0e5c09SChris Mason int push_items = 0; 295be0e5c09SChris Mason int dst_nritems; 296be0e5c09SChris Mason int src_nritems; 297be0e5c09SChris Mason 29874123bd7SChris Mason /* can't push from the root */ 299be0e5c09SChris Mason if (level == MAX_LEVEL - 1 || path->nodes[level + 1] == 0) 300be0e5c09SChris Mason return 1; 30174123bd7SChris Mason 30274123bd7SChris Mason /* only try to push inside the node higher up */ 303be0e5c09SChris Mason slot = path->slots[level + 1]; 304be0e5c09SChris Mason if (slot == NODEPTRS_PER_BLOCK - 1) 305be0e5c09SChris Mason return 1; 306be0e5c09SChris Mason 307eb60ceacSChris Mason if (slot >= path->nodes[level + 1]->node.header.nritems -1) 308be0e5c09SChris Mason return 1; 309be0e5c09SChris Mason 310eb60ceacSChris Mason t = read_tree_block(root, 311eb60ceacSChris Mason path->nodes[level + 1]->node.blockptrs[slot + 1]); 312eb60ceacSChris Mason dst = &t->node; 313eb60ceacSChris Mason src_buffer = path->nodes[level]; 314eb60ceacSChris Mason src = &src_buffer->node; 315be0e5c09SChris Mason dst_nritems = dst->header.nritems; 316be0e5c09SChris Mason src_nritems = src->header.nritems; 317be0e5c09SChris Mason push_items = NODEPTRS_PER_BLOCK - (dst_nritems + 1); 318eb60ceacSChris Mason if (push_items <= 0) { 319eb60ceacSChris Mason tree_block_release(root, t); 320be0e5c09SChris Mason return 1; 321eb60ceacSChris Mason } 322be0e5c09SChris Mason 323be0e5c09SChris Mason if (src_nritems < push_items) 324be0e5c09SChris Mason push_items = src_nritems; 325be0e5c09SChris Mason memmove(dst->keys + push_items, dst->keys, 326be0e5c09SChris Mason dst_nritems * sizeof(struct key)); 327be0e5c09SChris Mason memcpy(dst->keys, src->keys + src_nritems - push_items, 328be0e5c09SChris Mason push_items * sizeof(struct key)); 329be0e5c09SChris Mason 330be0e5c09SChris Mason memmove(dst->blockptrs + push_items, dst->blockptrs, 331be0e5c09SChris Mason dst_nritems * sizeof(u64)); 332be0e5c09SChris Mason memcpy(dst->blockptrs, src->blockptrs + src_nritems - push_items, 333be0e5c09SChris Mason push_items * sizeof(u64)); 334be0e5c09SChris Mason 335be0e5c09SChris Mason src->header.nritems -= push_items; 336be0e5c09SChris Mason dst->header.nritems += push_items; 337be0e5c09SChris Mason 338be0e5c09SChris Mason /* adjust the pointers going up the tree */ 339eb60ceacSChris Mason memcpy(path->nodes[level + 1]->node.keys + path->slots[level + 1] + 1, 340be0e5c09SChris Mason dst->keys, sizeof(struct key)); 341eb60ceacSChris Mason 342eb60ceacSChris Mason write_tree_block(root, path->nodes[level + 1]); 343eb60ceacSChris Mason write_tree_block(root, t); 344eb60ceacSChris Mason write_tree_block(root, src_buffer); 345eb60ceacSChris Mason 34674123bd7SChris Mason /* then fixup the pointers in the path */ 347be0e5c09SChris Mason if (path->slots[level] >= src->header.nritems) { 348be0e5c09SChris Mason path->slots[level] -= src->header.nritems; 349eb60ceacSChris Mason tree_block_release(root, path->nodes[level]); 350eb60ceacSChris Mason path->nodes[level] = t; 351be0e5c09SChris Mason path->slots[level + 1] += 1; 352eb60ceacSChris Mason } else { 353eb60ceacSChris Mason tree_block_release(root, t); 354be0e5c09SChris Mason } 355be0e5c09SChris Mason return 0; 356be0e5c09SChris Mason } 357be0e5c09SChris Mason 3585c680ed6SChris Mason static int insert_new_root(struct ctree_root *root, struct ctree_path *path, int level) 35974123bd7SChris Mason { 36074123bd7SChris Mason struct tree_buffer *t; 3615c680ed6SChris Mason struct node *lower; 3625c680ed6SChris Mason struct node *c; 3635c680ed6SChris Mason struct key *lower_key; 3645c680ed6SChris Mason 3655c680ed6SChris Mason BUG_ON(path->nodes[level]); 3665c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 3675c680ed6SChris Mason 36874123bd7SChris Mason t = alloc_free_block(root); 36974123bd7SChris Mason c = &t->node; 37074123bd7SChris Mason memset(c, 0, sizeof(c)); 3715c680ed6SChris Mason c->header.nritems = 1; 37274123bd7SChris Mason c->header.flags = node_level(level); 37374123bd7SChris Mason c->header.blocknr = t->blocknr; 374cfaa7295SChris Mason c->header.parentid = root->node->node.header.parentid; 37574123bd7SChris Mason lower = &path->nodes[level-1]->node; 37674123bd7SChris Mason if (is_leaf(lower->header.flags)) 37774123bd7SChris Mason lower_key = &((struct leaf *)lower)->items[0].key; 37874123bd7SChris Mason else 37974123bd7SChris Mason lower_key = lower->keys; 38074123bd7SChris Mason memcpy(c->keys, lower_key, sizeof(struct key)); 38174123bd7SChris Mason c->blockptrs[0] = path->nodes[level-1]->blocknr; 382cfaa7295SChris Mason /* the super has an extra ref to root->node */ 38374123bd7SChris Mason tree_block_release(root, root->node); 38474123bd7SChris Mason root->node = t; 38574123bd7SChris Mason t->count++; 38674123bd7SChris Mason write_tree_block(root, t); 38774123bd7SChris Mason path->nodes[level] = t; 38874123bd7SChris Mason path->slots[level] = 0; 38974123bd7SChris Mason return 0; 39074123bd7SChris Mason } 3915c680ed6SChris Mason 3925c680ed6SChris Mason /* 3935c680ed6SChris Mason * worker function to insert a single pointer in a node. 3945c680ed6SChris Mason * the node should have enough room for the pointer already 3955c680ed6SChris Mason * slot and level indicate where you want the key to go, and 3965c680ed6SChris Mason * blocknr is the block the key points to. 3975c680ed6SChris Mason */ 3985c680ed6SChris Mason int insert_ptr(struct ctree_root *root, 3995c680ed6SChris Mason struct ctree_path *path, struct key *key, 4005c680ed6SChris Mason u64 blocknr, int slot, int level) 4015c680ed6SChris Mason { 4025c680ed6SChris Mason struct node *lower; 4035c680ed6SChris Mason int nritems; 4045c680ed6SChris Mason 4055c680ed6SChris Mason BUG_ON(!path->nodes[level]); 40674123bd7SChris Mason lower = &path->nodes[level]->node; 40774123bd7SChris Mason nritems = lower->header.nritems; 40874123bd7SChris Mason if (slot > nritems) 40974123bd7SChris Mason BUG(); 41074123bd7SChris Mason if (nritems == NODEPTRS_PER_BLOCK) 41174123bd7SChris Mason BUG(); 41274123bd7SChris Mason if (slot != nritems) { 41374123bd7SChris Mason memmove(lower->keys + slot + 1, lower->keys + slot, 41474123bd7SChris Mason (nritems - slot) * sizeof(struct key)); 41574123bd7SChris Mason memmove(lower->blockptrs + slot + 1, lower->blockptrs + slot, 41674123bd7SChris Mason (nritems - slot) * sizeof(u64)); 41774123bd7SChris Mason } 41874123bd7SChris Mason memcpy(lower->keys + slot, key, sizeof(struct key)); 41974123bd7SChris Mason lower->blockptrs[slot] = blocknr; 42074123bd7SChris Mason lower->header.nritems++; 42174123bd7SChris Mason if (lower->keys[1].objectid == 0) 42274123bd7SChris Mason BUG(); 42374123bd7SChris Mason write_tree_block(root, path->nodes[level]); 42474123bd7SChris Mason return 0; 42574123bd7SChris Mason } 42674123bd7SChris Mason 4275c680ed6SChris Mason int split_node(struct ctree_root *root, struct ctree_path *path, int level) 428be0e5c09SChris Mason { 4295c680ed6SChris Mason struct tree_buffer *t; 4305c680ed6SChris Mason struct node *c; 4315c680ed6SChris Mason struct tree_buffer *split_buffer; 4325c680ed6SChris Mason struct node *split; 433be0e5c09SChris Mason int mid; 4345c680ed6SChris Mason int ret; 435be0e5c09SChris Mason 4365c680ed6SChris Mason ret = push_node_left(root, path, level); 4375c680ed6SChris Mason if (!ret) 4385c680ed6SChris Mason return 0; 4395c680ed6SChris Mason ret = push_node_right(root, path, level); 4405c680ed6SChris Mason if (!ret) 4415c680ed6SChris Mason return 0; 4425c680ed6SChris Mason t = path->nodes[level]; 443eb60ceacSChris Mason c = &t->node; 4445c680ed6SChris Mason if (t == root->node) { 4455c680ed6SChris Mason /* trying to split the root, lets make a new one */ 4465c680ed6SChris Mason ret = insert_new_root(root, path, level + 1); 4475c680ed6SChris Mason if (ret) 4485c680ed6SChris Mason return ret; 4495c680ed6SChris Mason } 4505c680ed6SChris Mason split_buffer = alloc_free_block(root); 4515c680ed6SChris Mason split = &split_buffer->node; 4525c680ed6SChris Mason split->header.flags = c->header.flags; 4535c680ed6SChris Mason split->header.blocknr = split_buffer->blocknr; 4545c680ed6SChris Mason split->header.parentid = root->node->node.header.parentid; 455be0e5c09SChris Mason mid = (c->header.nritems + 1) / 2; 4565c680ed6SChris Mason memcpy(split->keys, c->keys + mid, 457be0e5c09SChris Mason (c->header.nritems - mid) * sizeof(struct key)); 4585c680ed6SChris Mason memcpy(split->blockptrs, c->blockptrs + mid, 459be0e5c09SChris Mason (c->header.nritems - mid) * sizeof(u64)); 4605c680ed6SChris Mason split->header.nritems = c->header.nritems - mid; 461be0e5c09SChris Mason c->header.nritems = mid; 462eb60ceacSChris Mason write_tree_block(root, t); 4635c680ed6SChris Mason write_tree_block(root, split_buffer); 4645c680ed6SChris Mason insert_ptr(root, path, split->keys, split_buffer->blocknr, 4655c680ed6SChris Mason path->slots[level + 1] + 1, level + 1); 4665c680ed6SChris Mason if (path->slots[level] > mid) { 4675c680ed6SChris Mason path->slots[level] -= mid; 4685c680ed6SChris Mason tree_block_release(root, t); 4695c680ed6SChris Mason path->nodes[level] = split_buffer; 4705c680ed6SChris Mason path->slots[level + 1] += 1; 471eb60ceacSChris Mason } else { 4725c680ed6SChris Mason tree_block_release(root, split_buffer); 473be0e5c09SChris Mason } 4745c680ed6SChris Mason return 0; 475be0e5c09SChris Mason } 476be0e5c09SChris Mason 47774123bd7SChris Mason /* 47874123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 47974123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 48074123bd7SChris Mason * space used both by the item structs and the item data 48174123bd7SChris Mason */ 482be0e5c09SChris Mason int leaf_space_used(struct leaf *l, int start, int nr) 483be0e5c09SChris Mason { 484be0e5c09SChris Mason int data_len; 485be0e5c09SChris Mason int end = start + nr - 1; 486be0e5c09SChris Mason 487be0e5c09SChris Mason if (!nr) 488be0e5c09SChris Mason return 0; 489be0e5c09SChris Mason data_len = l->items[start].offset + l->items[start].size; 490be0e5c09SChris Mason data_len = data_len - l->items[end].offset; 491be0e5c09SChris Mason data_len += sizeof(struct item) * nr; 492be0e5c09SChris Mason return data_len; 493be0e5c09SChris Mason } 494be0e5c09SChris Mason 49574123bd7SChris Mason /* 49674123bd7SChris Mason * push some data in the path leaf to the left, trying to free up at 49774123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 49874123bd7SChris Mason */ 499be0e5c09SChris Mason int push_leaf_left(struct ctree_root *root, struct ctree_path *path, 500be0e5c09SChris Mason int data_size) 501be0e5c09SChris Mason { 502eb60ceacSChris Mason struct tree_buffer *right_buf = path->nodes[0]; 503eb60ceacSChris Mason struct leaf *right = &right_buf->leaf; 504eb60ceacSChris Mason struct tree_buffer *t; 505be0e5c09SChris Mason struct leaf *left; 506be0e5c09SChris Mason int slot; 507be0e5c09SChris Mason int i; 508be0e5c09SChris Mason int free_space; 509be0e5c09SChris Mason int push_space = 0; 510be0e5c09SChris Mason int push_items = 0; 511be0e5c09SChris Mason struct item *item; 512be0e5c09SChris Mason int old_left_nritems; 513be0e5c09SChris Mason 514be0e5c09SChris Mason slot = path->slots[1]; 515be0e5c09SChris Mason if (slot == 0) { 516be0e5c09SChris Mason return 1; 517be0e5c09SChris Mason } 518be0e5c09SChris Mason if (!path->nodes[1]) { 519be0e5c09SChris Mason return 1; 520be0e5c09SChris Mason } 521eb60ceacSChris Mason t = read_tree_block(root, path->nodes[1]->node.blockptrs[slot - 1]); 522eb60ceacSChris Mason left = &t->leaf; 523be0e5c09SChris Mason free_space = leaf_free_space(left); 524be0e5c09SChris Mason if (free_space < data_size + sizeof(struct item)) { 525eb60ceacSChris Mason tree_block_release(root, t); 526be0e5c09SChris Mason return 1; 527be0e5c09SChris Mason } 528be0e5c09SChris Mason for (i = 0; i < right->header.nritems; i++) { 529be0e5c09SChris Mason item = right->items + i; 530be0e5c09SChris Mason if (path->slots[0] == i) 531be0e5c09SChris Mason push_space += data_size + sizeof(*item); 532be0e5c09SChris Mason if (item->size + sizeof(*item) + push_space > free_space) 533be0e5c09SChris Mason break; 534be0e5c09SChris Mason push_items++; 535be0e5c09SChris Mason push_space += item->size + sizeof(*item); 536be0e5c09SChris Mason } 537be0e5c09SChris Mason if (push_items == 0) { 538eb60ceacSChris Mason tree_block_release(root, t); 539be0e5c09SChris Mason return 1; 540be0e5c09SChris Mason } 541be0e5c09SChris Mason /* push data from right to left */ 542be0e5c09SChris Mason memcpy(left->items + left->header.nritems, 543be0e5c09SChris Mason right->items, push_items * sizeof(struct item)); 544be0e5c09SChris Mason push_space = LEAF_DATA_SIZE - right->items[push_items -1].offset; 545be0e5c09SChris Mason memcpy(left->data + leaf_data_end(left) - push_space, 546be0e5c09SChris Mason right->data + right->items[push_items - 1].offset, 547be0e5c09SChris Mason push_space); 548be0e5c09SChris Mason old_left_nritems = left->header.nritems; 549eb60ceacSChris Mason BUG_ON(old_left_nritems < 0); 550eb60ceacSChris Mason 551be0e5c09SChris Mason for(i = old_left_nritems; i < old_left_nritems + push_items; i++) { 552be0e5c09SChris Mason left->items[i].offset -= LEAF_DATA_SIZE - 553be0e5c09SChris Mason left->items[old_left_nritems -1].offset; 554be0e5c09SChris Mason } 555be0e5c09SChris Mason left->header.nritems += push_items; 556be0e5c09SChris Mason 557be0e5c09SChris Mason /* fixup right node */ 558be0e5c09SChris Mason push_space = right->items[push_items-1].offset - leaf_data_end(right); 559be0e5c09SChris Mason memmove(right->data + LEAF_DATA_SIZE - push_space, right->data + 560be0e5c09SChris Mason leaf_data_end(right), push_space); 561be0e5c09SChris Mason memmove(right->items, right->items + push_items, 562be0e5c09SChris Mason (right->header.nritems - push_items) * sizeof(struct item)); 563be0e5c09SChris Mason right->header.nritems -= push_items; 564be0e5c09SChris Mason push_space = LEAF_DATA_SIZE; 565eb60ceacSChris Mason 566be0e5c09SChris Mason for (i = 0; i < right->header.nritems; i++) { 567be0e5c09SChris Mason right->items[i].offset = push_space - right->items[i].size; 568be0e5c09SChris Mason push_space = right->items[i].offset; 569be0e5c09SChris Mason } 570eb60ceacSChris Mason 571eb60ceacSChris Mason write_tree_block(root, t); 572eb60ceacSChris Mason write_tree_block(root, right_buf); 573eb60ceacSChris Mason 574eb60ceacSChris Mason fixup_low_keys(root, path, &right->items[0].key, 1); 575be0e5c09SChris Mason 576be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 577be0e5c09SChris Mason if (path->slots[0] < push_items) { 578be0e5c09SChris Mason path->slots[0] += old_left_nritems; 579eb60ceacSChris Mason tree_block_release(root, path->nodes[0]); 580eb60ceacSChris Mason path->nodes[0] = t; 581be0e5c09SChris Mason path->slots[1] -= 1; 582be0e5c09SChris Mason } else { 583eb60ceacSChris Mason tree_block_release(root, t); 584be0e5c09SChris Mason path->slots[0] -= push_items; 585be0e5c09SChris Mason } 586eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 587be0e5c09SChris Mason return 0; 588be0e5c09SChris Mason } 589be0e5c09SChris Mason 59074123bd7SChris Mason /* 59174123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 59274123bd7SChris Mason * available for the resulting leaf level of the path. 59374123bd7SChris Mason */ 594be0e5c09SChris Mason int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size) 595be0e5c09SChris Mason { 596eb60ceacSChris Mason struct tree_buffer *l_buf = path->nodes[0]; 597eb60ceacSChris Mason struct leaf *l = &l_buf->leaf; 598eb60ceacSChris Mason int nritems; 599eb60ceacSChris Mason int mid; 600eb60ceacSChris Mason int slot; 601be0e5c09SChris Mason struct leaf *right; 602eb60ceacSChris Mason struct tree_buffer *right_buffer; 603be0e5c09SChris Mason int space_needed = data_size + sizeof(struct item); 604be0e5c09SChris Mason int data_copy_size; 605be0e5c09SChris Mason int rt_data_off; 606be0e5c09SChris Mason int i; 607be0e5c09SChris Mason int ret; 608be0e5c09SChris Mason 609be0e5c09SChris Mason if (push_leaf_left(root, path, data_size) == 0) { 610eb60ceacSChris Mason l_buf = path->nodes[0]; 611eb60ceacSChris Mason l = &l_buf->leaf; 612eb60ceacSChris Mason if (leaf_free_space(l) >= sizeof(struct item) + data_size) 613be0e5c09SChris Mason return 0; 614be0e5c09SChris Mason } 6155c680ed6SChris Mason if (!path->nodes[1]) { 6165c680ed6SChris Mason ret = insert_new_root(root, path, 1); 6175c680ed6SChris Mason if (ret) 6185c680ed6SChris Mason return ret; 6195c680ed6SChris Mason } 620eb60ceacSChris Mason slot = path->slots[0]; 621eb60ceacSChris Mason nritems = l->header.nritems; 622eb60ceacSChris Mason mid = (nritems + 1)/ 2; 623eb60ceacSChris Mason 624eb60ceacSChris Mason right_buffer = alloc_free_block(root); 625eb60ceacSChris Mason BUG_ON(!right_buffer); 626eb60ceacSChris Mason BUG_ON(mid == nritems); 627eb60ceacSChris Mason right = &right_buffer->leaf; 628be0e5c09SChris Mason memset(right, 0, sizeof(*right)); 629be0e5c09SChris Mason if (mid <= slot) { 630be0e5c09SChris Mason if (leaf_space_used(l, mid, nritems - mid) + space_needed > 631be0e5c09SChris Mason LEAF_DATA_SIZE) 632be0e5c09SChris Mason BUG(); 633be0e5c09SChris Mason } else { 634be0e5c09SChris Mason if (leaf_space_used(l, 0, mid + 1) + space_needed > 635be0e5c09SChris Mason LEAF_DATA_SIZE) 636be0e5c09SChris Mason BUG(); 637be0e5c09SChris Mason } 638be0e5c09SChris Mason right->header.nritems = nritems - mid; 639eb60ceacSChris Mason right->header.blocknr = right_buffer->blocknr; 640eb60ceacSChris Mason right->header.flags = node_level(0); 641cfaa7295SChris Mason right->header.parentid = root->node->node.header.parentid; 642be0e5c09SChris Mason data_copy_size = l->items[mid].offset + l->items[mid].size - 643be0e5c09SChris Mason leaf_data_end(l); 644be0e5c09SChris Mason memcpy(right->items, l->items + mid, 645be0e5c09SChris Mason (nritems - mid) * sizeof(struct item)); 646be0e5c09SChris Mason memcpy(right->data + LEAF_DATA_SIZE - data_copy_size, 647be0e5c09SChris Mason l->data + leaf_data_end(l), data_copy_size); 648be0e5c09SChris Mason rt_data_off = LEAF_DATA_SIZE - 649be0e5c09SChris Mason (l->items[mid].offset + l->items[mid].size); 65074123bd7SChris Mason 65174123bd7SChris Mason for (i = 0; i < right->header.nritems; i++) 652be0e5c09SChris Mason right->items[i].offset += rt_data_off; 65374123bd7SChris Mason 654be0e5c09SChris Mason l->header.nritems = mid; 655be0e5c09SChris Mason ret = insert_ptr(root, path, &right->items[0].key, 6565c680ed6SChris Mason right_buffer->blocknr, path->slots[1] + 1, 1); 657eb60ceacSChris Mason write_tree_block(root, right_buffer); 658eb60ceacSChris Mason write_tree_block(root, l_buf); 659eb60ceacSChris Mason 660eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 661be0e5c09SChris Mason if (mid <= slot) { 662eb60ceacSChris Mason tree_block_release(root, path->nodes[0]); 663eb60ceacSChris Mason path->nodes[0] = right_buffer; 664be0e5c09SChris Mason path->slots[0] -= mid; 665be0e5c09SChris Mason path->slots[1] += 1; 666eb60ceacSChris Mason } else 667eb60ceacSChris Mason tree_block_release(root, right_buffer); 668eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 669be0e5c09SChris Mason return ret; 670be0e5c09SChris Mason } 671be0e5c09SChris Mason 67274123bd7SChris Mason /* 67374123bd7SChris Mason * Given a key and some data, insert an item into the tree. 67474123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 67574123bd7SChris Mason */ 676be0e5c09SChris Mason int insert_item(struct ctree_root *root, struct key *key, 677be0e5c09SChris Mason void *data, int data_size) 678be0e5c09SChris Mason { 679be0e5c09SChris Mason int ret; 680be0e5c09SChris Mason int slot; 681eb60ceacSChris Mason int slot_orig; 682be0e5c09SChris Mason struct leaf *leaf; 683eb60ceacSChris Mason struct tree_buffer *leaf_buf; 684be0e5c09SChris Mason unsigned int nritems; 685be0e5c09SChris Mason unsigned int data_end; 686be0e5c09SChris Mason struct ctree_path path; 687be0e5c09SChris Mason 68874123bd7SChris Mason /* create a root if there isn't one */ 6895c680ed6SChris Mason if (!root->node) 690cfaa7295SChris Mason BUG(); 691be0e5c09SChris Mason init_path(&path); 6925c680ed6SChris Mason ret = search_slot(root, key, &path, data_size); 693eb60ceacSChris Mason if (ret == 0) { 694eb60ceacSChris Mason release_path(root, &path); 695be0e5c09SChris Mason return -EEXIST; 696eb60ceacSChris Mason } 697be0e5c09SChris Mason 698eb60ceacSChris Mason slot_orig = path.slots[0]; 699eb60ceacSChris Mason leaf_buf = path.nodes[0]; 700eb60ceacSChris Mason leaf = &leaf_buf->leaf; 70174123bd7SChris Mason 702be0e5c09SChris Mason nritems = leaf->header.nritems; 703be0e5c09SChris Mason data_end = leaf_data_end(leaf); 704eb60ceacSChris Mason 705be0e5c09SChris Mason if (leaf_free_space(leaf) < sizeof(struct item) + data_size) 706be0e5c09SChris Mason BUG(); 707be0e5c09SChris Mason 708be0e5c09SChris Mason slot = path.slots[0]; 709eb60ceacSChris Mason BUG_ON(slot < 0); 710be0e5c09SChris Mason if (slot == 0) 711eb60ceacSChris Mason fixup_low_keys(root, &path, key, 1); 712be0e5c09SChris Mason if (slot != nritems) { 713be0e5c09SChris Mason int i; 714be0e5c09SChris Mason unsigned int old_data = leaf->items[slot].offset + 715be0e5c09SChris Mason leaf->items[slot].size; 716be0e5c09SChris Mason 717be0e5c09SChris Mason /* 718be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 719be0e5c09SChris Mason */ 720be0e5c09SChris Mason /* first correct the data pointers */ 721be0e5c09SChris Mason for (i = slot; i < nritems; i++) 722be0e5c09SChris Mason leaf->items[i].offset -= data_size; 723be0e5c09SChris Mason 724be0e5c09SChris Mason /* shift the items */ 725be0e5c09SChris Mason memmove(leaf->items + slot + 1, leaf->items + slot, 726be0e5c09SChris Mason (nritems - slot) * sizeof(struct item)); 727be0e5c09SChris Mason 728be0e5c09SChris Mason /* shift the data */ 729be0e5c09SChris Mason memmove(leaf->data + data_end - data_size, leaf->data + 730be0e5c09SChris Mason data_end, old_data - data_end); 731be0e5c09SChris Mason data_end = old_data; 732be0e5c09SChris Mason } 73374123bd7SChris Mason /* copy the new data in */ 734be0e5c09SChris Mason memcpy(&leaf->items[slot].key, key, sizeof(struct key)); 735be0e5c09SChris Mason leaf->items[slot].offset = data_end - data_size; 736be0e5c09SChris Mason leaf->items[slot].size = data_size; 737be0e5c09SChris Mason memcpy(leaf->data + data_end - data_size, data, data_size); 738be0e5c09SChris Mason leaf->header.nritems += 1; 739eb60ceacSChris Mason write_tree_block(root, leaf_buf); 740be0e5c09SChris Mason if (leaf_free_space(leaf) < 0) 741be0e5c09SChris Mason BUG(); 742eb60ceacSChris Mason release_path(root, &path); 743be0e5c09SChris Mason return 0; 744be0e5c09SChris Mason } 745be0e5c09SChris Mason 74674123bd7SChris Mason /* 74774123bd7SChris Mason * delete the pointer from a given level in the path. The path is not 74874123bd7SChris Mason * fixed up, so after calling this it is not valid at that level. 74974123bd7SChris Mason * 75074123bd7SChris Mason * If the delete empties a node, the node is removed from the tree, 75174123bd7SChris Mason * continuing all the way the root if required. The root is converted into 75274123bd7SChris Mason * a leaf if all the nodes are emptied. 75374123bd7SChris Mason */ 754be0e5c09SChris Mason int del_ptr(struct ctree_root *root, struct ctree_path *path, int level) 755be0e5c09SChris Mason { 756be0e5c09SChris Mason int slot; 757eb60ceacSChris Mason struct tree_buffer *t; 758be0e5c09SChris Mason struct node *node; 759be0e5c09SChris Mason int nritems; 7609a8dd150SChris Mason u64 blocknr; 761be0e5c09SChris Mason 762be0e5c09SChris Mason while(1) { 763eb60ceacSChris Mason t = path->nodes[level]; 764eb60ceacSChris Mason if (!t) 765be0e5c09SChris Mason break; 766eb60ceacSChris Mason node = &t->node; 767be0e5c09SChris Mason slot = path->slots[level]; 768be0e5c09SChris Mason nritems = node->header.nritems; 769be0e5c09SChris Mason 770be0e5c09SChris Mason if (slot != nritems -1) { 771be0e5c09SChris Mason memmove(node->keys + slot, node->keys + slot + 1, 772be0e5c09SChris Mason sizeof(struct key) * (nritems - slot - 1)); 773be0e5c09SChris Mason memmove(node->blockptrs + slot, 774be0e5c09SChris Mason node->blockptrs + slot + 1, 775be0e5c09SChris Mason sizeof(u64) * (nritems - slot - 1)); 776be0e5c09SChris Mason } 777be0e5c09SChris Mason node->header.nritems--; 778eb60ceacSChris Mason write_tree_block(root, t); 7799a8dd150SChris Mason blocknr = t->blocknr; 780be0e5c09SChris Mason if (node->header.nritems != 0) { 781be0e5c09SChris Mason int tslot; 782be0e5c09SChris Mason if (slot == 0) 783eb60ceacSChris Mason fixup_low_keys(root, path, node->keys, 784eb60ceacSChris Mason level + 1); 785be0e5c09SChris Mason tslot = path->slots[level+1]; 786eb60ceacSChris Mason t->count++; 787be0e5c09SChris Mason push_node_left(root, path, level); 788be0e5c09SChris Mason if (node->header.nritems) { 789be0e5c09SChris Mason push_node_right(root, path, level); 790be0e5c09SChris Mason } 791eb60ceacSChris Mason if (node->header.nritems) { 792eb60ceacSChris Mason tree_block_release(root, t); 793be0e5c09SChris Mason break; 794eb60ceacSChris Mason } 795eb60ceacSChris Mason tree_block_release(root, t); 7964920c9acSChris Mason path->slots[level+1] = tslot; 797be0e5c09SChris Mason } 798eb60ceacSChris Mason if (t == root->node) { 799eb60ceacSChris Mason /* just turn the root into a leaf and break */ 800eb60ceacSChris Mason root->node->node.header.flags = node_level(0); 801eb60ceacSChris Mason write_tree_block(root, t); 802be0e5c09SChris Mason break; 803be0e5c09SChris Mason } 804be0e5c09SChris Mason level++; 8059a8dd150SChris Mason free_extent(root, blocknr, 1); 806be0e5c09SChris Mason if (!path->nodes[level]) 807be0e5c09SChris Mason BUG(); 808be0e5c09SChris Mason } 809be0e5c09SChris Mason return 0; 810be0e5c09SChris Mason } 811be0e5c09SChris Mason 81274123bd7SChris Mason /* 81374123bd7SChris Mason * delete the item at the leaf level in path. If that empties 81474123bd7SChris Mason * the leaf, remove it from the tree 81574123bd7SChris Mason */ 8164920c9acSChris Mason int del_item(struct ctree_root *root, struct ctree_path *path) 817be0e5c09SChris Mason { 818be0e5c09SChris Mason int slot; 819be0e5c09SChris Mason struct leaf *leaf; 820eb60ceacSChris Mason struct tree_buffer *leaf_buf; 821be0e5c09SChris Mason int doff; 822be0e5c09SChris Mason int dsize; 823be0e5c09SChris Mason 824eb60ceacSChris Mason leaf_buf = path->nodes[0]; 825eb60ceacSChris Mason leaf = &leaf_buf->leaf; 8264920c9acSChris Mason slot = path->slots[0]; 827be0e5c09SChris Mason doff = leaf->items[slot].offset; 828be0e5c09SChris Mason dsize = leaf->items[slot].size; 829be0e5c09SChris Mason 830be0e5c09SChris Mason if (slot != leaf->header.nritems - 1) { 831be0e5c09SChris Mason int i; 832be0e5c09SChris Mason int data_end = leaf_data_end(leaf); 833be0e5c09SChris Mason memmove(leaf->data + data_end + dsize, 834be0e5c09SChris Mason leaf->data + data_end, 835be0e5c09SChris Mason doff - data_end); 836be0e5c09SChris Mason for (i = slot + 1; i < leaf->header.nritems; i++) 837be0e5c09SChris Mason leaf->items[i].offset += dsize; 838be0e5c09SChris Mason memmove(leaf->items + slot, leaf->items + slot + 1, 839be0e5c09SChris Mason sizeof(struct item) * 840be0e5c09SChris Mason (leaf->header.nritems - slot - 1)); 841be0e5c09SChris Mason } 842be0e5c09SChris Mason leaf->header.nritems -= 1; 84374123bd7SChris Mason /* delete the leaf if we've emptied it */ 844be0e5c09SChris Mason if (leaf->header.nritems == 0) { 845eb60ceacSChris Mason if (leaf_buf == root->node) { 846eb60ceacSChris Mason leaf->header.flags = node_level(0); 847eb60ceacSChris Mason write_tree_block(root, leaf_buf); 8489a8dd150SChris Mason } else { 8494920c9acSChris Mason del_ptr(root, path, 1); 8509a8dd150SChris Mason free_extent(root, leaf_buf->blocknr, 1); 8519a8dd150SChris Mason } 852be0e5c09SChris Mason } else { 853be0e5c09SChris Mason if (slot == 0) 854eb60ceacSChris Mason fixup_low_keys(root, path, &leaf->items[0].key, 1); 855eb60ceacSChris Mason write_tree_block(root, leaf_buf); 85674123bd7SChris Mason /* delete the leaf if it is mostly empty */ 857be0e5c09SChris Mason if (leaf_space_used(leaf, 0, leaf->header.nritems) < 858be0e5c09SChris Mason LEAF_DATA_SIZE / 4) { 859be0e5c09SChris Mason /* push_leaf_left fixes the path. 860be0e5c09SChris Mason * make sure the path still points to our leaf 861be0e5c09SChris Mason * for possible call to del_ptr below 862be0e5c09SChris Mason */ 8634920c9acSChris Mason slot = path->slots[1]; 864eb60ceacSChris Mason leaf_buf->count++; 8654920c9acSChris Mason push_leaf_left(root, path, 1); 866be0e5c09SChris Mason if (leaf->header.nritems == 0) { 8674920c9acSChris Mason path->slots[1] = slot; 8684920c9acSChris Mason del_ptr(root, path, 1); 869be0e5c09SChris Mason } 870eb60ceacSChris Mason tree_block_release(root, leaf_buf); 871be0e5c09SChris Mason } 872be0e5c09SChris Mason } 873be0e5c09SChris Mason return 0; 874be0e5c09SChris Mason } 875be0e5c09SChris Mason 8769a8dd150SChris Mason static int del_pending_extents(struct ctree_root *extent_root) 8779a8dd150SChris Mason { 8789a8dd150SChris Mason int ret; 8799a8dd150SChris Mason struct key key; 8809a8dd150SChris Mason struct tree_buffer *gang[4]; 8819a8dd150SChris Mason int i; 8829a8dd150SChris Mason struct ctree_path path; 8839a8dd150SChris Mason 8849a8dd150SChris Mason while(1) { 8859a8dd150SChris Mason ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix, 8869a8dd150SChris Mason (void **)gang, 0, ARRAY_SIZE(gang), 8879a8dd150SChris Mason CTREE_EXTENT_PENDING); 8889a8dd150SChris Mason if (!ret) 8899a8dd150SChris Mason break; 8909a8dd150SChris Mason for (i = 0; i < ret; i++) { 8919a8dd150SChris Mason key.objectid = gang[i]->blocknr; 8929a8dd150SChris Mason key.flags = 0; 8939a8dd150SChris Mason key.offset = 1; 8949a8dd150SChris Mason init_path(&path); 8959a8dd150SChris Mason ret = search_slot(extent_root, &key, &path, 0); 8969a8dd150SChris Mason if (ret) { 8979a8dd150SChris Mason BUG(); 8989a8dd150SChris Mason // FIXME undo it and return sane 8999a8dd150SChris Mason return ret; 9009a8dd150SChris Mason } 9019a8dd150SChris Mason ret = del_item(extent_root, &path); 9029a8dd150SChris Mason if (ret) { 9039a8dd150SChris Mason BUG(); 9049a8dd150SChris Mason return ret; 9059a8dd150SChris Mason } 9069a8dd150SChris Mason release_path(extent_root, &path); 9079a8dd150SChris Mason radix_tree_tag_clear(&extent_root->cache_radix, gang[i]->blocknr, 9089a8dd150SChris Mason CTREE_EXTENT_PENDING); 9099a8dd150SChris Mason tree_block_release(extent_root, gang[i]); 9109a8dd150SChris Mason } 9119a8dd150SChris Mason } 9129a8dd150SChris Mason return 0; 9139a8dd150SChris Mason } 9149a8dd150SChris Mason 9159a8dd150SChris Mason int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks) 9169a8dd150SChris Mason { 9179a8dd150SChris Mason struct ctree_path path; 9189a8dd150SChris Mason struct key key; 9199a8dd150SChris Mason struct ctree_root *extent_root = root->extent_root; 9209a8dd150SChris Mason struct tree_buffer *t; 9219a8dd150SChris Mason int pending_ret; 9229a8dd150SChris Mason int ret; 9239a8dd150SChris Mason 9249a8dd150SChris Mason key.objectid = blocknr; 9259a8dd150SChris Mason key.flags = 0; 9269a8dd150SChris Mason key.offset = num_blocks; 9279a8dd150SChris Mason if (root == extent_root) { 9289a8dd150SChris Mason t = read_tree_block(root, key.objectid); 9299a8dd150SChris Mason radix_tree_tag_set(&root->cache_radix, key.objectid, CTREE_EXTENT_PENDING); 9309a8dd150SChris Mason return 0; 9319a8dd150SChris Mason } 9329a8dd150SChris Mason init_path(&path); 9339a8dd150SChris Mason ret = search_slot(extent_root, &key, &path, 0); 9349a8dd150SChris Mason if (ret) 9359a8dd150SChris Mason BUG(); 9369a8dd150SChris Mason ret = del_item(extent_root, &path); 9379a8dd150SChris Mason release_path(extent_root, &path); 9389a8dd150SChris Mason pending_ret = del_pending_extents(root->extent_root); 9399a8dd150SChris Mason return ret ? ret : pending_ret; 9409a8dd150SChris Mason } 9419a8dd150SChris Mason 942d97e63b6SChris Mason int next_leaf(struct ctree_root *root, struct ctree_path *path) 943d97e63b6SChris Mason { 944d97e63b6SChris Mason int slot; 945d97e63b6SChris Mason int level = 1; 946d97e63b6SChris Mason u64 blocknr; 947d97e63b6SChris Mason struct tree_buffer *c; 948cfaa7295SChris Mason struct tree_buffer *next = NULL; 949d97e63b6SChris Mason 950d97e63b6SChris Mason while(level < MAX_LEVEL) { 951d97e63b6SChris Mason if (!path->nodes[level]) 952d97e63b6SChris Mason return -1; 953d97e63b6SChris Mason slot = path->slots[level] + 1; 954d97e63b6SChris Mason c = path->nodes[level]; 955d97e63b6SChris Mason if (slot >= c->node.header.nritems) { 956d97e63b6SChris Mason level++; 957d97e63b6SChris Mason continue; 958d97e63b6SChris Mason } 959d97e63b6SChris Mason blocknr = c->node.blockptrs[slot]; 960cfaa7295SChris Mason if (next) 961cfaa7295SChris Mason tree_block_release(root, next); 962d97e63b6SChris Mason next = read_tree_block(root, blocknr); 963d97e63b6SChris Mason break; 964d97e63b6SChris Mason } 965d97e63b6SChris Mason path->slots[level] = slot; 966d97e63b6SChris Mason while(1) { 967d97e63b6SChris Mason level--; 968d97e63b6SChris Mason c = path->nodes[level]; 969d97e63b6SChris Mason tree_block_release(root, c); 970d97e63b6SChris Mason path->nodes[level] = next; 971d97e63b6SChris Mason path->slots[level] = 0; 972d97e63b6SChris Mason if (!level) 973d97e63b6SChris Mason break; 974d97e63b6SChris Mason next = read_tree_block(root, next->node.blockptrs[0]); 975d97e63b6SChris Mason } 976d97e63b6SChris Mason return 0; 977d97e63b6SChris Mason } 978d97e63b6SChris Mason 9799a8dd150SChris Mason int find_free_extent(struct ctree_root *orig_root, u64 num_blocks, u64 search_start, 9809a8dd150SChris Mason u64 search_end, struct key *ins) 981d97e63b6SChris Mason { 982d97e63b6SChris Mason struct ctree_path path; 983d97e63b6SChris Mason struct key *key; 984d97e63b6SChris Mason int ret; 985d97e63b6SChris Mason u64 hole_size = 0; 986d97e63b6SChris Mason int slot = 0; 987d97e63b6SChris Mason u64 last_block; 988d97e63b6SChris Mason int start_found = 0; 989d97e63b6SChris Mason struct leaf *l; 990cfaa7295SChris Mason struct ctree_root * root = orig_root->extent_root; 991d97e63b6SChris Mason 992d97e63b6SChris Mason init_path(&path); 993d97e63b6SChris Mason ins->objectid = search_start; 994d97e63b6SChris Mason ins->offset = 0; 995d97e63b6SChris Mason ins->flags = 0; 9969a8dd150SChris Mason ret = search_slot(root, ins, &path, 0); 997d97e63b6SChris Mason while (1) { 998d97e63b6SChris Mason l = &path.nodes[0]->leaf; 999d97e63b6SChris Mason slot = path.slots[0]; 1000d97e63b6SChris Mason if (!l) { 1001d97e63b6SChris Mason // FIXME allocate root 1002d97e63b6SChris Mason } 1003d97e63b6SChris Mason if (slot >= l->header.nritems) { 1004d97e63b6SChris Mason ret = next_leaf(root, &path); 1005d97e63b6SChris Mason if (ret == 0) 1006d97e63b6SChris Mason continue; 1007d97e63b6SChris Mason if (!start_found) { 1008d97e63b6SChris Mason ins->objectid = search_start; 1009d97e63b6SChris Mason ins->offset = num_blocks; 1010d97e63b6SChris Mason hole_size = search_end - search_start; 10119a8dd150SChris Mason start_found = 1; 1012d97e63b6SChris Mason goto insert; 1013d97e63b6SChris Mason } 1014d97e63b6SChris Mason ins->objectid = last_block; 1015d97e63b6SChris Mason ins->offset = num_blocks; 1016d97e63b6SChris Mason hole_size = search_end - last_block; 1017d97e63b6SChris Mason goto insert; 1018d97e63b6SChris Mason } 1019d97e63b6SChris Mason key = &l->items[slot].key; 1020d97e63b6SChris Mason if (start_found) { 1021d97e63b6SChris Mason hole_size = key->objectid - last_block; 1022d97e63b6SChris Mason if (hole_size > num_blocks) { 1023d97e63b6SChris Mason ins->objectid = last_block; 1024d97e63b6SChris Mason ins->offset = num_blocks; 1025d97e63b6SChris Mason goto insert; 1026d97e63b6SChris Mason } 1027d97e63b6SChris Mason } else 1028d97e63b6SChris Mason start_found = 1; 1029d97e63b6SChris Mason last_block = key->objectid + key->offset; 10309a8dd150SChris Mason insert_failed: 1031d97e63b6SChris Mason path.slots[0]++; 1032d97e63b6SChris Mason } 1033d97e63b6SChris Mason // FIXME -ENOSPC 1034d97e63b6SChris Mason insert: 10359a8dd150SChris Mason if (orig_root->extent_root == orig_root) { 10369a8dd150SChris Mason BUG_ON(num_blocks != 1); 10379a8dd150SChris Mason if ((root->current_insert.objectid <= ins->objectid && 10389a8dd150SChris Mason root->current_insert.objectid + root->current_insert.offset > 10399a8dd150SChris Mason ins->objectid) || 10409a8dd150SChris Mason (root->current_insert.objectid > ins->objectid && 10419a8dd150SChris Mason root->current_insert.objectid <= ins->objectid + ins->offset) || 10429a8dd150SChris Mason radix_tree_tag_get(&root->cache_radix, ins->objectid, 10439a8dd150SChris Mason CTREE_EXTENT_PENDING)) { 10449a8dd150SChris Mason last_block = ins->objectid + 1; 10459a8dd150SChris Mason search_start = last_block; 10469a8dd150SChris Mason goto insert_failed; 10479a8dd150SChris Mason } 10489a8dd150SChris Mason } 1049cfaa7295SChris Mason release_path(root, &path); 10509a8dd150SChris Mason if (ins->offset != 1) 10519a8dd150SChris Mason BUG(); 10529a8dd150SChris Mason return 0; 10539a8dd150SChris Mason } 10549a8dd150SChris Mason 10559a8dd150SChris Mason static int insert_pending_extents(struct ctree_root *extent_root) 10569a8dd150SChris Mason { 10579a8dd150SChris Mason int ret; 10589a8dd150SChris Mason struct key key; 10599a8dd150SChris Mason struct extent_item item; 10609a8dd150SChris Mason struct tree_buffer *gang[4]; 10619a8dd150SChris Mason int i; 10629a8dd150SChris Mason 10639a8dd150SChris Mason // FIXME -ENOSPC 10649a8dd150SChris Mason item.refs = 1; 10659a8dd150SChris Mason item.owner = extent_root->node->node.header.parentid; 10669a8dd150SChris Mason while(1) { 10679a8dd150SChris Mason ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix, 10689a8dd150SChris Mason (void **)gang, 0, ARRAY_SIZE(gang), 10699a8dd150SChris Mason CTREE_EXTENT_PENDING); 10709a8dd150SChris Mason if (!ret) 10719a8dd150SChris Mason break; 10729a8dd150SChris Mason for (i = 0; i < ret; i++) { 10739a8dd150SChris Mason key.objectid = gang[i]->blocknr; 10749a8dd150SChris Mason key.flags = 0; 10759a8dd150SChris Mason key.offset = 1; 10769a8dd150SChris Mason ret = insert_item(extent_root, &key, &item, sizeof(item)); 10779a8dd150SChris Mason if (ret) { 10789a8dd150SChris Mason BUG(); 10799a8dd150SChris Mason // FIXME undo it and return sane 10809a8dd150SChris Mason return ret; 10819a8dd150SChris Mason } 10829a8dd150SChris Mason radix_tree_tag_clear(&extent_root->cache_radix, gang[i]->blocknr, 10839a8dd150SChris Mason CTREE_EXTENT_PENDING); 10849a8dd150SChris Mason tree_block_release(extent_root, gang[i]); 10859a8dd150SChris Mason } 10869a8dd150SChris Mason } 10879a8dd150SChris Mason return 0; 10889a8dd150SChris Mason } 10899a8dd150SChris Mason 10909a8dd150SChris Mason int alloc_extent(struct ctree_root *root, u64 num_blocks, u64 search_start, 10919a8dd150SChris Mason u64 search_end, u64 owner, struct key *ins, struct tree_buffer **buf) 10929a8dd150SChris Mason { 10939a8dd150SChris Mason int ret; 10949a8dd150SChris Mason int pending_ret; 10959a8dd150SChris Mason struct extent_item extent_item; 10969a8dd150SChris Mason 1097d97e63b6SChris Mason extent_item.refs = 1; 1098d97e63b6SChris Mason extent_item.owner = owner; 10999a8dd150SChris Mason 11009a8dd150SChris Mason ret = find_free_extent(root, num_blocks, search_start, search_end, ins); 11019a8dd150SChris Mason if (ret) 11029a8dd150SChris Mason return ret; 11039a8dd150SChris Mason 11049a8dd150SChris Mason if (root != root->extent_root) { 11059a8dd150SChris Mason memcpy(&root->extent_root->current_insert, ins, sizeof(*ins)); 1106cfaa7295SChris Mason ret = insert_item(root->extent_root, ins, &extent_item, sizeof(extent_item)); 11079a8dd150SChris Mason memset(&root->extent_root->current_insert, 0, sizeof(struct key)); 11089a8dd150SChris Mason pending_ret = insert_pending_extents(root->extent_root); 11099a8dd150SChris Mason if (ret) 1110d97e63b6SChris Mason return ret; 11119a8dd150SChris Mason if (pending_ret) 11129a8dd150SChris Mason return pending_ret; 11139a8dd150SChris Mason *buf = find_tree_block(root, ins->objectid); 11149a8dd150SChris Mason return 0; 11159a8dd150SChris Mason } 11169a8dd150SChris Mason /* we're allocating an extent for the extent tree, don't recurse */ 11179a8dd150SChris Mason BUG_ON(ins->offset != 1); 11189a8dd150SChris Mason *buf = find_tree_block(root, ins->objectid); 11199a8dd150SChris Mason BUG_ON(!*buf); 11209a8dd150SChris Mason radix_tree_tag_set(&root->cache_radix, ins->objectid, CTREE_EXTENT_PENDING); 11219a8dd150SChris Mason (*buf)->count++; 11229a8dd150SChris Mason return 0; 11239a8dd150SChris Mason 1124d97e63b6SChris Mason } 1125d97e63b6SChris Mason 11269a8dd150SChris Mason struct tree_buffer *alloc_free_block(struct ctree_root *root) 1127d97e63b6SChris Mason { 11289a8dd150SChris Mason struct key ins; 1129d97e63b6SChris Mason int ret; 11309a8dd150SChris Mason struct tree_buffer *buf = NULL; 1131d97e63b6SChris Mason 11329a8dd150SChris Mason ret = alloc_extent(root, 1, 0, (unsigned long)-1, root->node->node.header.parentid, 11339a8dd150SChris Mason &ins, &buf); 11349a8dd150SChris Mason 11359a8dd150SChris Mason if (ret) { 1136d97e63b6SChris Mason BUG(); 11379a8dd150SChris Mason return NULL; 1138d97e63b6SChris Mason } 11399a8dd150SChris Mason if (root != root->extent_root) 11409a8dd150SChris Mason BUG_ON(radix_tree_tag_get(&root->extent_root->cache_radix, buf->blocknr, 11419a8dd150SChris Mason CTREE_EXTENT_PENDING)); 11429a8dd150SChris Mason return buf; 1143d97e63b6SChris Mason } 1144d97e63b6SChris Mason 1145be0e5c09SChris Mason void print_leaf(struct leaf *l) 1146be0e5c09SChris Mason { 1147be0e5c09SChris Mason int i; 1148be0e5c09SChris Mason int nr = l->header.nritems; 1149be0e5c09SChris Mason struct item *item; 1150cfaa7295SChris Mason struct extent_item *ei; 1151eb60ceacSChris Mason printf("leaf %lu total ptrs %d free space %d\n", l->header.blocknr, nr, 1152be0e5c09SChris Mason leaf_free_space(l)); 1153be0e5c09SChris Mason fflush(stdout); 1154be0e5c09SChris Mason for (i = 0 ; i < nr ; i++) { 1155be0e5c09SChris Mason item = l->items + i; 1156be0e5c09SChris Mason printf("\titem %d key (%lu %u %lu) itemoff %d itemsize %d\n", 1157be0e5c09SChris Mason i, 1158be0e5c09SChris Mason item->key.objectid, item->key.flags, item->key.offset, 1159be0e5c09SChris Mason item->offset, item->size); 1160be0e5c09SChris Mason fflush(stdout); 1161be0e5c09SChris Mason printf("\t\titem data %.*s\n", item->size, l->data+item->offset); 1162cfaa7295SChris Mason ei = (struct extent_item *)(l->data + item->offset); 1163cfaa7295SChris Mason printf("\t\textent data %u %lu\n", ei->refs, ei->owner); 1164be0e5c09SChris Mason fflush(stdout); 1165be0e5c09SChris Mason } 1166be0e5c09SChris Mason } 1167eb60ceacSChris Mason void print_tree(struct ctree_root *root, struct tree_buffer *t) 1168be0e5c09SChris Mason { 1169be0e5c09SChris Mason int i; 1170be0e5c09SChris Mason int nr; 1171eb60ceacSChris Mason struct node *c; 1172be0e5c09SChris Mason 1173eb60ceacSChris Mason if (!t) 1174be0e5c09SChris Mason return; 1175eb60ceacSChris Mason c = &t->node; 1176be0e5c09SChris Mason nr = c->header.nritems; 1177eb60ceacSChris Mason if (c->header.blocknr != t->blocknr) 1178eb60ceacSChris Mason BUG(); 1179be0e5c09SChris Mason if (is_leaf(c->header.flags)) { 1180be0e5c09SChris Mason print_leaf((struct leaf *)c); 1181be0e5c09SChris Mason return; 1182be0e5c09SChris Mason } 1183eb60ceacSChris Mason printf("node %lu level %d total ptrs %d free spc %lu\n", t->blocknr, 1184be0e5c09SChris Mason node_level(c->header.flags), c->header.nritems, 1185be0e5c09SChris Mason NODEPTRS_PER_BLOCK - c->header.nritems); 1186be0e5c09SChris Mason fflush(stdout); 1187be0e5c09SChris Mason for (i = 0; i < nr; i++) { 1188eb60ceacSChris Mason printf("\tkey %d (%lu %u %lu) block %lu\n", 1189be0e5c09SChris Mason i, 1190be0e5c09SChris Mason c->keys[i].objectid, c->keys[i].flags, c->keys[i].offset, 1191be0e5c09SChris Mason c->blockptrs[i]); 1192be0e5c09SChris Mason fflush(stdout); 1193be0e5c09SChris Mason } 1194be0e5c09SChris Mason for (i = 0; i < nr; i++) { 1195eb60ceacSChris Mason struct tree_buffer *next_buf = read_tree_block(root, 1196eb60ceacSChris Mason c->blockptrs[i]); 1197eb60ceacSChris Mason struct node *next = &next_buf->node; 1198be0e5c09SChris Mason if (is_leaf(next->header.flags) && 1199be0e5c09SChris Mason node_level(c->header.flags) != 1) 1200be0e5c09SChris Mason BUG(); 1201be0e5c09SChris Mason if (node_level(next->header.flags) != 1202be0e5c09SChris Mason node_level(c->header.flags) - 1) 1203be0e5c09SChris Mason BUG(); 1204eb60ceacSChris Mason print_tree(root, next_buf); 1205eb60ceacSChris Mason tree_block_release(root, next_buf); 1206be0e5c09SChris Mason } 1207be0e5c09SChris Mason 1208be0e5c09SChris Mason } 1209be0e5c09SChris Mason 1210be0e5c09SChris Mason /* for testing only */ 1211be0e5c09SChris Mason int next_key(int i, int max_key) { 12125c680ed6SChris Mason // return rand() % max_key; 12135c680ed6SChris Mason return i; 1214be0e5c09SChris Mason } 1215be0e5c09SChris Mason 1216be0e5c09SChris Mason int main() { 1217eb60ceacSChris Mason struct ctree_root *root; 1218be0e5c09SChris Mason struct key ins; 12194920c9acSChris Mason struct key last = { (u64)-1, 0, 0}; 1220be0e5c09SChris Mason char *buf; 1221be0e5c09SChris Mason int i; 1222be0e5c09SChris Mason int num; 1223be0e5c09SChris Mason int ret; 1224cfaa7295SChris Mason int run_size = 10000; 1225be0e5c09SChris Mason int max_key = 100000000; 1226be0e5c09SChris Mason int tree_size = 0; 1227be0e5c09SChris Mason struct ctree_path path; 1228cfaa7295SChris Mason struct ctree_super_block super; 1229be0e5c09SChris Mason 1230eb60ceacSChris Mason radix_tree_init(); 1231eb60ceacSChris Mason 1232eb60ceacSChris Mason 1233cfaa7295SChris Mason root = open_ctree("dbfile", &super); 1234cfaa7295SChris Mason printf("root tree\n"); 1235cfaa7295SChris Mason print_tree(root, root->node); 1236cfaa7295SChris Mason printf("map tree\n"); 1237cfaa7295SChris Mason print_tree(root->extent_root, root->extent_root->node); 12389a8dd150SChris Mason fflush(stdout); 1239be0e5c09SChris Mason 1240be0e5c09SChris Mason srand(55); 1241be0e5c09SChris Mason for (i = 0; i < run_size; i++) { 1242be0e5c09SChris Mason buf = malloc(64); 1243be0e5c09SChris Mason num = next_key(i, max_key); 1244be0e5c09SChris Mason // num = i; 1245be0e5c09SChris Mason sprintf(buf, "string-%d", num); 1246be0e5c09SChris Mason // printf("insert %d\n", num); 1247be0e5c09SChris Mason ins.objectid = num; 1248be0e5c09SChris Mason ins.offset = 0; 1249be0e5c09SChris Mason ins.flags = 0; 1250eb60ceacSChris Mason ret = insert_item(root, &ins, buf, strlen(buf)); 1251be0e5c09SChris Mason if (!ret) 1252be0e5c09SChris Mason tree_size++; 1253be0e5c09SChris Mason } 1254cfaa7295SChris Mason write_ctree_super(root, &super); 1255eb60ceacSChris Mason close_ctree(root); 1256cfaa7295SChris Mason 1257cfaa7295SChris Mason root = open_ctree("dbfile", &super); 1258eb60ceacSChris Mason printf("starting search\n"); 1259be0e5c09SChris Mason srand(55); 1260be0e5c09SChris Mason for (i = 0; i < run_size; i++) { 1261be0e5c09SChris Mason num = next_key(i, max_key); 1262be0e5c09SChris Mason ins.objectid = num; 1263be0e5c09SChris Mason init_path(&path); 12645c680ed6SChris Mason ret = search_slot(root, &ins, &path, 0); 1265be0e5c09SChris Mason if (ret) { 1266eb60ceacSChris Mason print_tree(root, root->node); 1267be0e5c09SChris Mason printf("unable to find %d\n", num); 1268be0e5c09SChris Mason exit(1); 1269be0e5c09SChris Mason } 1270eb60ceacSChris Mason release_path(root, &path); 1271be0e5c09SChris Mason } 1272cfaa7295SChris Mason write_ctree_super(root, &super); 1273eb60ceacSChris Mason close_ctree(root); 1274cfaa7295SChris Mason root = open_ctree("dbfile", &super); 1275eb60ceacSChris Mason printf("node %p level %d total ptrs %d free spc %lu\n", root->node, 1276eb60ceacSChris Mason node_level(root->node->node.header.flags), 1277eb60ceacSChris Mason root->node->node.header.nritems, 1278eb60ceacSChris Mason NODEPTRS_PER_BLOCK - root->node->node.header.nritems); 1279eb60ceacSChris Mason printf("all searches good, deleting some items\n"); 1280be0e5c09SChris Mason i = 0; 1281be0e5c09SChris Mason srand(55); 12824920c9acSChris Mason for (i = 0 ; i < run_size/4; i++) { 1283be0e5c09SChris Mason num = next_key(i, max_key); 1284be0e5c09SChris Mason ins.objectid = num; 12854920c9acSChris Mason init_path(&path); 12865c680ed6SChris Mason ret = search_slot(root, &ins, &path, 0); 12874920c9acSChris Mason if (ret) 12884920c9acSChris Mason continue; 1289eb60ceacSChris Mason ret = del_item(root, &path); 12904920c9acSChris Mason if (ret != 0) 12914920c9acSChris Mason BUG(); 1292eb60ceacSChris Mason release_path(root, &path); 12934920c9acSChris Mason tree_size--; 12944920c9acSChris Mason } 12954920c9acSChris Mason srand(128); 12964920c9acSChris Mason for (i = 0; i < run_size; i++) { 12974920c9acSChris Mason buf = malloc(64); 12984920c9acSChris Mason num = next_key(i, max_key); 12994920c9acSChris Mason sprintf(buf, "string-%d", num); 13004920c9acSChris Mason ins.objectid = num; 1301eb60ceacSChris Mason ret = insert_item(root, &ins, buf, strlen(buf)); 13024920c9acSChris Mason if (!ret) 13034920c9acSChris Mason tree_size++; 13049a8dd150SChris Mason if (i >= 5) { 13059a8dd150SChris Mason struct key ugh; 13069a8dd150SChris Mason ugh.objectid = 5; 13079a8dd150SChris Mason ugh.flags = 0; 13089a8dd150SChris Mason ugh.offset = 0; 13099a8dd150SChris Mason init_path(&path); 13109a8dd150SChris Mason ret = search_slot(root, &ugh, &path, 0); 13119a8dd150SChris Mason if (ret) { 13129a8dd150SChris Mason print_tree(root, root->node); 13139a8dd150SChris Mason printf("unable to find 5 %d\n", num); 13149a8dd150SChris Mason exit(1); 13159a8dd150SChris Mason } 13169a8dd150SChris Mason release_path(root, &path); 13179a8dd150SChris Mason 13189a8dd150SChris Mason } 13194920c9acSChris Mason } 1320cfaa7295SChris Mason write_ctree_super(root, &super); 1321eb60ceacSChris Mason close_ctree(root); 1322cfaa7295SChris Mason root = open_ctree("dbfile", &super); 1323eb60ceacSChris Mason srand(128); 13249a8dd150SChris Mason printf("starting search2\n"); 1325eb60ceacSChris Mason for (i = 0; i < run_size; i++) { 1326eb60ceacSChris Mason num = next_key(i, max_key); 1327eb60ceacSChris Mason ins.objectid = num; 1328eb60ceacSChris Mason init_path(&path); 13295c680ed6SChris Mason ret = search_slot(root, &ins, &path, 0); 1330eb60ceacSChris Mason if (ret) { 1331eb60ceacSChris Mason print_tree(root, root->node); 1332eb60ceacSChris Mason printf("unable to find %d\n", num); 1333eb60ceacSChris Mason exit(1); 1334eb60ceacSChris Mason } 1335eb60ceacSChris Mason release_path(root, &path); 1336eb60ceacSChris Mason } 1337eb60ceacSChris Mason printf("starting big long delete run\n"); 1338eb60ceacSChris Mason while(root->node && root->node->node.header.nritems > 0) { 13394920c9acSChris Mason struct leaf *leaf; 13404920c9acSChris Mason int slot; 13414920c9acSChris Mason ins.objectid = (u64)-1; 13424920c9acSChris Mason init_path(&path); 13435c680ed6SChris Mason ret = search_slot(root, &ins, &path, 0); 13444920c9acSChris Mason if (ret == 0) 13454920c9acSChris Mason BUG(); 13464920c9acSChris Mason 1347eb60ceacSChris Mason leaf = &path.nodes[0]->leaf; 13484920c9acSChris Mason slot = path.slots[0]; 13494920c9acSChris Mason if (slot != leaf->header.nritems) 13504920c9acSChris Mason BUG(); 13514920c9acSChris Mason while(path.slots[0] > 0) { 13524920c9acSChris Mason path.slots[0] -= 1; 13534920c9acSChris Mason slot = path.slots[0]; 1354eb60ceacSChris Mason leaf = &path.nodes[0]->leaf; 13554920c9acSChris Mason 13564920c9acSChris Mason if (comp_keys(&last, &leaf->items[slot].key) <= 0) 13574920c9acSChris Mason BUG(); 13584920c9acSChris Mason memcpy(&last, &leaf->items[slot].key, sizeof(last)); 1359eb60ceacSChris Mason ret = del_item(root, &path); 1360eb60ceacSChris Mason if (ret != 0) { 1361eb60ceacSChris Mason printf("del_item returned %d\n", ret); 13624920c9acSChris Mason BUG(); 1363eb60ceacSChris Mason } 13644920c9acSChris Mason tree_size--; 13654920c9acSChris Mason } 1366eb60ceacSChris Mason release_path(root, &path); 1367be0e5c09SChris Mason } 1368cfaa7295SChris Mason write_ctree_super(root, &super); 1369eb60ceacSChris Mason close_ctree(root); 13704920c9acSChris Mason printf("tree size is now %d\n", tree_size); 13719a8dd150SChris Mason printf("map tree\n"); 13729a8dd150SChris Mason print_tree(root->extent_root, root->extent_root->node); 1373be0e5c09SChris Mason return 0; 1374be0e5c09SChris Mason } 1375