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" 75de08d7dSChris Mason #include "print-tree.h" 89a8dd150SChris Mason 9aa5d6bedSChris Mason static int split_node(struct ctree_root *root, struct ctree_path *path, 10aa5d6bedSChris Mason int level); 11aa5d6bedSChris Mason static int split_leaf(struct ctree_root *root, struct ctree_path *path, 12aa5d6bedSChris Mason int data_size); 13bb803951SChris Mason static int push_node_left(struct ctree_root *root, struct tree_buffer *dst, 14bb803951SChris Mason struct tree_buffer *src); 15bb803951SChris Mason static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, 16bb803951SChris Mason int slot); 17d97e63b6SChris Mason 185de08d7dSChris Mason inline void init_path(struct ctree_path *p) 19be0e5c09SChris Mason { 20be0e5c09SChris Mason memset(p, 0, sizeof(*p)); 21be0e5c09SChris Mason } 22be0e5c09SChris Mason 235de08d7dSChris Mason 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 } 31aa5d6bedSChris Mason memset(p, 0, sizeof(*p)); 32eb60ceacSChris Mason } 33eb60ceacSChris Mason 3474123bd7SChris Mason /* 3574123bd7SChris Mason * The leaf data grows from end-to-front in the node. 3674123bd7SChris Mason * this returns the address of the start of the last item, 3774123bd7SChris Mason * which is the stop of the leaf data stack 3874123bd7SChris Mason */ 39be0e5c09SChris Mason static inline unsigned int leaf_data_end(struct leaf *leaf) 40be0e5c09SChris Mason { 41be0e5c09SChris Mason unsigned int nr = leaf->header.nritems; 42be0e5c09SChris Mason if (nr == 0) 43d97e63b6SChris Mason return sizeof(leaf->data); 44be0e5c09SChris Mason return leaf->items[nr-1].offset; 45be0e5c09SChris Mason } 46be0e5c09SChris Mason 4774123bd7SChris Mason /* 4874123bd7SChris Mason * The space between the end of the leaf items and 4974123bd7SChris Mason * the start of the leaf data. IOW, how much room 5074123bd7SChris Mason * the leaf has left for both items and data 5174123bd7SChris Mason */ 525de08d7dSChris Mason int leaf_free_space(struct leaf *leaf) 53be0e5c09SChris Mason { 54be0e5c09SChris Mason int data_end = leaf_data_end(leaf); 55be0e5c09SChris Mason int nritems = leaf->header.nritems; 56be0e5c09SChris Mason char *items_end = (char *)(leaf->items + nritems + 1); 57be0e5c09SChris Mason return (char *)(leaf->data + data_end) - (char *)items_end; 58be0e5c09SChris Mason } 59be0e5c09SChris Mason 6074123bd7SChris Mason /* 6174123bd7SChris Mason * compare two keys in a memcmp fashion 6274123bd7SChris Mason */ 63be0e5c09SChris Mason int comp_keys(struct key *k1, struct key *k2) 64be0e5c09SChris Mason { 65be0e5c09SChris Mason if (k1->objectid > k2->objectid) 66be0e5c09SChris Mason return 1; 67be0e5c09SChris Mason if (k1->objectid < k2->objectid) 68be0e5c09SChris Mason return -1; 69be0e5c09SChris Mason if (k1->flags > k2->flags) 70be0e5c09SChris Mason return 1; 71be0e5c09SChris Mason if (k1->flags < k2->flags) 72be0e5c09SChris Mason return -1; 73be0e5c09SChris Mason if (k1->offset > k2->offset) 74be0e5c09SChris Mason return 1; 75be0e5c09SChris Mason if (k1->offset < k2->offset) 76be0e5c09SChris Mason return -1; 77be0e5c09SChris Mason return 0; 78be0e5c09SChris Mason } 7974123bd7SChris Mason 80aa5d6bedSChris Mason int check_node(struct ctree_path *path, int level) 81aa5d6bedSChris Mason { 82aa5d6bedSChris Mason int i; 83aa5d6bedSChris Mason struct node *parent = NULL; 84aa5d6bedSChris Mason struct node *node = &path->nodes[level]->node; 85aa5d6bedSChris Mason int parent_slot; 86aa5d6bedSChris Mason 87aa5d6bedSChris Mason if (path->nodes[level + 1]) 88aa5d6bedSChris Mason parent = &path->nodes[level + 1]->node; 89aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 90aa5d6bedSChris Mason if (parent && node->header.nritems > 0) { 91aa5d6bedSChris Mason struct key *parent_key; 92aa5d6bedSChris Mason parent_key = &parent->keys[parent_slot]; 93aa5d6bedSChris Mason BUG_ON(memcmp(parent_key, node->keys, sizeof(struct key))); 94aa5d6bedSChris Mason BUG_ON(parent->blockptrs[parent_slot] != node->header.blocknr); 95aa5d6bedSChris Mason } 96aa5d6bedSChris Mason BUG_ON(node->header.nritems > NODEPTRS_PER_BLOCK); 97aa5d6bedSChris Mason for (i = 0; i < node->header.nritems - 2; i++) { 98aa5d6bedSChris Mason BUG_ON(comp_keys(&node->keys[i], &node->keys[i+1]) >= 0); 99aa5d6bedSChris Mason } 100aa5d6bedSChris Mason return 0; 101aa5d6bedSChris Mason } 102aa5d6bedSChris Mason 103aa5d6bedSChris Mason int check_leaf(struct ctree_path *path, int level) 104aa5d6bedSChris Mason { 105aa5d6bedSChris Mason int i; 106aa5d6bedSChris Mason struct leaf *leaf = &path->nodes[level]->leaf; 107aa5d6bedSChris Mason struct node *parent = NULL; 108aa5d6bedSChris Mason int parent_slot; 109aa5d6bedSChris Mason 110aa5d6bedSChris Mason if (path->nodes[level + 1]) 111aa5d6bedSChris Mason parent = &path->nodes[level + 1]->node; 112aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 113aa5d6bedSChris Mason if (parent && leaf->header.nritems > 0) { 114aa5d6bedSChris Mason struct key *parent_key; 115aa5d6bedSChris Mason parent_key = &parent->keys[parent_slot]; 116aa5d6bedSChris Mason BUG_ON(memcmp(parent_key, &leaf->items[0].key, 117aa5d6bedSChris Mason sizeof(struct key))); 118aa5d6bedSChris Mason BUG_ON(parent->blockptrs[parent_slot] != leaf->header.blocknr); 119aa5d6bedSChris Mason } 120aa5d6bedSChris Mason for (i = 0; i < leaf->header.nritems - 2; i++) { 121aa5d6bedSChris Mason BUG_ON(comp_keys(&leaf->items[i].key, 122aa5d6bedSChris Mason &leaf->items[i+1].key) >= 0); 123aa5d6bedSChris Mason BUG_ON(leaf->items[i].offset != leaf->items[i + 1].offset + 124aa5d6bedSChris Mason leaf->items[i + 1].size); 125aa5d6bedSChris Mason if (i == 0) { 126aa5d6bedSChris Mason BUG_ON(leaf->items[i].offset + leaf->items[i].size != 127aa5d6bedSChris Mason LEAF_DATA_SIZE); 128aa5d6bedSChris Mason } 129aa5d6bedSChris Mason } 130aa5d6bedSChris Mason BUG_ON(leaf_free_space(leaf) < 0); 131aa5d6bedSChris Mason return 0; 132aa5d6bedSChris Mason } 133aa5d6bedSChris Mason 134aa5d6bedSChris Mason int check_block(struct ctree_path *path, int level) 135aa5d6bedSChris Mason { 136aa5d6bedSChris Mason if (level == 0) 137aa5d6bedSChris Mason return check_leaf(path, level); 138aa5d6bedSChris Mason return check_node(path, level); 139aa5d6bedSChris Mason } 140aa5d6bedSChris Mason 14174123bd7SChris Mason /* 14274123bd7SChris Mason * search for key in the array p. items p are item_size apart 14374123bd7SChris Mason * and there are 'max' items in p 14474123bd7SChris Mason * the slot in the array is returned via slot, and it points to 14574123bd7SChris Mason * the place where you would insert key if it is not found in 14674123bd7SChris Mason * the array. 14774123bd7SChris Mason * 14874123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 14974123bd7SChris Mason */ 150be0e5c09SChris Mason int generic_bin_search(char *p, int item_size, struct key *key, 151be0e5c09SChris Mason int max, int *slot) 152be0e5c09SChris Mason { 153be0e5c09SChris Mason int low = 0; 154be0e5c09SChris Mason int high = max; 155be0e5c09SChris Mason int mid; 156be0e5c09SChris Mason int ret; 157be0e5c09SChris Mason struct key *tmp; 158be0e5c09SChris Mason 159be0e5c09SChris Mason while(low < high) { 160be0e5c09SChris Mason mid = (low + high) / 2; 161be0e5c09SChris Mason tmp = (struct key *)(p + mid * item_size); 162be0e5c09SChris Mason ret = comp_keys(tmp, key); 163be0e5c09SChris Mason 164be0e5c09SChris Mason if (ret < 0) 165be0e5c09SChris Mason low = mid + 1; 166be0e5c09SChris Mason else if (ret > 0) 167be0e5c09SChris Mason high = mid; 168be0e5c09SChris Mason else { 169be0e5c09SChris Mason *slot = mid; 170be0e5c09SChris Mason return 0; 171be0e5c09SChris Mason } 172be0e5c09SChris Mason } 173be0e5c09SChris Mason *slot = low; 174be0e5c09SChris Mason return 1; 175be0e5c09SChris Mason } 176be0e5c09SChris Mason 17797571fd0SChris Mason /* 17897571fd0SChris Mason * simple bin_search frontend that does the right thing for 17997571fd0SChris Mason * leaves vs nodes 18097571fd0SChris Mason */ 181be0e5c09SChris Mason int bin_search(struct node *c, struct key *key, int *slot) 182be0e5c09SChris Mason { 183be0e5c09SChris Mason if (is_leaf(c->header.flags)) { 184be0e5c09SChris Mason struct leaf *l = (struct leaf *)c; 185be0e5c09SChris Mason return generic_bin_search((void *)l->items, sizeof(struct item), 186be0e5c09SChris Mason key, c->header.nritems, slot); 187be0e5c09SChris Mason } else { 188be0e5c09SChris Mason return generic_bin_search((void *)c->keys, sizeof(struct key), 189be0e5c09SChris Mason key, c->header.nritems, slot); 190be0e5c09SChris Mason } 191be0e5c09SChris Mason return -1; 192be0e5c09SChris Mason } 193be0e5c09SChris Mason 194bb803951SChris Mason struct tree_buffer *read_node_slot(struct ctree_root *root, 195bb803951SChris Mason struct tree_buffer *parent_buf, 196bb803951SChris Mason int slot) 197bb803951SChris Mason { 198bb803951SChris Mason struct node *node = &parent_buf->node; 199bb803951SChris Mason if (slot < 0) 200bb803951SChris Mason return NULL; 201bb803951SChris Mason if (slot >= node->header.nritems) 202bb803951SChris Mason return NULL; 203bb803951SChris Mason return read_tree_block(root, node->blockptrs[slot]); 204bb803951SChris Mason } 205bb803951SChris Mason 206bb803951SChris Mason static int balance_level(struct ctree_root *root, struct ctree_path *path, 207bb803951SChris Mason int level) 208bb803951SChris Mason { 209bb803951SChris Mason struct tree_buffer *right_buf; 210bb803951SChris Mason struct tree_buffer *mid_buf; 211bb803951SChris Mason struct tree_buffer *left_buf; 212bb803951SChris Mason struct tree_buffer *parent_buf = NULL; 213bb803951SChris Mason struct node *right = NULL; 214bb803951SChris Mason struct node *mid; 215bb803951SChris Mason struct node *left = NULL; 216bb803951SChris Mason struct node *parent = NULL; 217bb803951SChris Mason int ret = 0; 218bb803951SChris Mason int wret; 219bb803951SChris Mason int pslot; 220bb803951SChris Mason int used = 0; 221bb803951SChris Mason int count; 222bb803951SChris Mason int orig_slot = path->slots[level]; 223bb803951SChris Mason 224bb803951SChris Mason if (level == 0) 225bb803951SChris Mason return 0; 226bb803951SChris Mason 227bb803951SChris Mason mid_buf = path->nodes[level]; 228bb803951SChris Mason mid = &mid_buf->node; 229bb803951SChris Mason if (level < MAX_LEVEL - 1) 230bb803951SChris Mason parent_buf = path->nodes[level + 1]; 231bb803951SChris Mason pslot = path->slots[level + 1]; 232bb803951SChris Mason 233bb803951SChris Mason if (!parent_buf) { 234bb803951SChris Mason struct tree_buffer *child; 235bb803951SChris Mason u64 blocknr = mid_buf->blocknr; 236bb803951SChris Mason 237bb803951SChris Mason if (mid->header.nritems != 1) 238bb803951SChris Mason return 0; 239bb803951SChris Mason 240bb803951SChris Mason /* promote the child to a root */ 241bb803951SChris Mason child = read_node_slot(root, mid_buf, 0); 242bb803951SChris Mason BUG_ON(!child); 243bb803951SChris Mason root->node = child; 244bb803951SChris Mason path->nodes[level] = NULL; 245bb803951SChris Mason /* once for the path */ 246bb803951SChris Mason tree_block_release(root, mid_buf); 247bb803951SChris Mason /* once for the root ptr */ 248bb803951SChris Mason tree_block_release(root, mid_buf); 249bb803951SChris Mason return free_extent(root, blocknr, 1); 250bb803951SChris Mason } 251bb803951SChris Mason parent = &parent_buf->node; 252bb803951SChris Mason 253bb803951SChris Mason if (mid->header.nritems > NODEPTRS_PER_BLOCK / 4) 254bb803951SChris Mason return 0; 255bb803951SChris Mason 256bb803951SChris Mason // print_tree(root, root->node); 257bb803951SChris Mason left_buf = read_node_slot(root, parent_buf, pslot - 1); 258bb803951SChris Mason right_buf = read_node_slot(root, parent_buf, pslot + 1); 259bb803951SChris Mason if (right_buf) { 260bb803951SChris Mason right = &right_buf->node; 261bb803951SChris Mason used = right->header.nritems; 262bb803951SChris Mason count = 1; 263bb803951SChris Mason } 264bb803951SChris Mason if (left_buf) { 265bb803951SChris Mason left = &left_buf->node; 266bb803951SChris Mason used += left->header.nritems; 267bb803951SChris Mason orig_slot += left->header.nritems; 268bb803951SChris Mason count++; 269bb803951SChris Mason } 270bb803951SChris Mason if (left_buf) 271bb803951SChris Mason push_node_left(root, left_buf, mid_buf); 272bb803951SChris Mason if (right_buf) { 273bb803951SChris Mason push_node_left(root, mid_buf, right_buf); 274bb803951SChris Mason if (right->header.nritems == 0) { 275bb803951SChris Mason u64 blocknr = right_buf->blocknr; 276bb803951SChris Mason tree_block_release(root, right_buf); 277bb803951SChris Mason right_buf = NULL; 278bb803951SChris Mason right = NULL; 279bb803951SChris Mason wret = del_ptr(root, path, level + 1, pslot + 1); 280bb803951SChris Mason if (wret) 281bb803951SChris Mason ret = wret; 282bb803951SChris Mason wret = free_extent(root, blocknr, 1); 283bb803951SChris Mason if (wret) 284bb803951SChris Mason ret = wret; 285bb803951SChris Mason } else { 286bb803951SChris Mason memcpy(parent->keys + pslot + 1, right->keys, 287bb803951SChris Mason sizeof(struct key)); 288bb803951SChris Mason } 289bb803951SChris Mason } 290bb803951SChris Mason if (mid->header.nritems == 0) { 291bb803951SChris Mason u64 blocknr = mid_buf->blocknr; 292bb803951SChris Mason tree_block_release(root, mid_buf); 293bb803951SChris Mason mid_buf = NULL; 294bb803951SChris Mason mid = NULL; 295bb803951SChris Mason wret = del_ptr(root, path, level + 1, pslot); 296bb803951SChris Mason if (wret) 297bb803951SChris Mason ret = wret; 298bb803951SChris Mason wret = free_extent(root, blocknr, 1); 299bb803951SChris Mason if (wret) 300bb803951SChris Mason ret = wret; 301bb803951SChris Mason } else 302bb803951SChris Mason memcpy(parent->keys + pslot, mid->keys, sizeof(struct key)); 303bb803951SChris Mason 304bb803951SChris Mason if (left_buf) { 305bb803951SChris Mason if (left->header.nritems >= orig_slot) { 306bb803951SChris Mason left_buf->count++; // released below 307bb803951SChris Mason path->nodes[level] = left_buf; 308bb803951SChris Mason path->slots[level + 1] -= 1; 309bb803951SChris Mason path->slots[level] = orig_slot; 310bb803951SChris Mason if (mid_buf) 311bb803951SChris Mason tree_block_release(root, mid_buf); 312bb803951SChris Mason } else { 313bb803951SChris Mason orig_slot -= left->header.nritems; 314bb803951SChris Mason path->slots[level] = orig_slot; 315bb803951SChris Mason } 316bb803951SChris Mason } 317bb803951SChris Mason 318bb803951SChris Mason if (right_buf) 319bb803951SChris Mason tree_block_release(root, right_buf); 320bb803951SChris Mason if (left_buf) 321bb803951SChris Mason tree_block_release(root, left_buf); 322bb803951SChris Mason 323bb803951SChris Mason return ret; 324bb803951SChris Mason } 325bb803951SChris Mason 32674123bd7SChris Mason /* 32774123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 32874123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 32974123bd7SChris Mason * level of the path (level 0) 33074123bd7SChris Mason * 33174123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 332aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 333aa5d6bedSChris Mason * search a negative error number is returned. 33497571fd0SChris Mason * 33597571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 33697571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 33797571fd0SChris Mason * possible) 33874123bd7SChris Mason */ 3395de08d7dSChris Mason int search_slot(struct ctree_root *root, struct key *key, 3405de08d7dSChris Mason struct ctree_path *p, int ins_len) 341be0e5c09SChris Mason { 342bb803951SChris Mason struct tree_buffer *b; 343eb60ceacSChris Mason struct node *c; 344be0e5c09SChris Mason int slot; 345be0e5c09SChris Mason int ret; 346be0e5c09SChris Mason int level; 3475c680ed6SChris Mason 348bb803951SChris Mason again: 349bb803951SChris Mason b = root->node; 350eb60ceacSChris Mason b->count++; 351eb60ceacSChris Mason while (b) { 352eb60ceacSChris Mason c = &b->node; 353be0e5c09SChris Mason level = node_level(c->header.flags); 354eb60ceacSChris Mason p->nodes[level] = b; 355aa5d6bedSChris Mason ret = check_block(p, level); 356aa5d6bedSChris Mason if (ret) 357aa5d6bedSChris Mason return -1; 358be0e5c09SChris Mason ret = bin_search(c, key, &slot); 359be0e5c09SChris Mason if (!is_leaf(c->header.flags)) { 360be0e5c09SChris Mason if (ret && slot > 0) 361be0e5c09SChris Mason slot -= 1; 362be0e5c09SChris Mason p->slots[level] = slot; 3635de08d7dSChris Mason if (ins_len > 0 && 3645de08d7dSChris Mason c->header.nritems == NODEPTRS_PER_BLOCK) { 3655c680ed6SChris Mason int sret = split_node(root, p, level); 3665c680ed6SChris Mason BUG_ON(sret > 0); 3675c680ed6SChris Mason if (sret) 3685c680ed6SChris Mason return sret; 3695c680ed6SChris Mason b = p->nodes[level]; 3705c680ed6SChris Mason c = &b->node; 3715c680ed6SChris Mason slot = p->slots[level]; 372bb803951SChris Mason } else if (ins_len < 0) { 373bb803951SChris Mason int sret = balance_level(root, p, level); 374bb803951SChris Mason if (sret) 375bb803951SChris Mason return sret; 376bb803951SChris Mason b = p->nodes[level]; 377bb803951SChris Mason if (!b) 378bb803951SChris Mason goto again; 379bb803951SChris Mason c = &b->node; 380bb803951SChris Mason slot = p->slots[level]; 3815c680ed6SChris Mason } 382eb60ceacSChris Mason b = read_tree_block(root, c->blockptrs[slot]); 383be0e5c09SChris Mason } else { 3845c680ed6SChris Mason struct leaf *l = (struct leaf *)c; 385be0e5c09SChris Mason p->slots[level] = slot; 3865de08d7dSChris Mason if (ins_len > 0 && leaf_free_space(l) < 3875de08d7dSChris Mason sizeof(struct item) + ins_len) { 3885c680ed6SChris Mason int sret = split_leaf(root, p, ins_len); 3895c680ed6SChris Mason BUG_ON(sret > 0); 3905c680ed6SChris Mason if (sret) 3915c680ed6SChris Mason return sret; 3925c680ed6SChris Mason } 393bb803951SChris Mason BUG_ON(root->node->count == 1); 394be0e5c09SChris Mason return ret; 395be0e5c09SChris Mason } 396be0e5c09SChris Mason } 397bb803951SChris Mason BUG_ON(root->node->count == 1); 398aa5d6bedSChris Mason return 1; 399be0e5c09SChris Mason } 400be0e5c09SChris Mason 40174123bd7SChris Mason /* 40274123bd7SChris Mason * adjust the pointers going up the tree, starting at level 40374123bd7SChris Mason * making sure the right key of each node is points to 'key'. 40474123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 40574123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 40674123bd7SChris Mason * higher levels 407aa5d6bedSChris Mason * 408aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 409aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 41074123bd7SChris Mason */ 411aa5d6bedSChris Mason static int fixup_low_keys(struct ctree_root *root, 412eb60ceacSChris Mason struct ctree_path *path, struct key *key, 413be0e5c09SChris Mason int level) 414be0e5c09SChris Mason { 415be0e5c09SChris Mason int i; 416aa5d6bedSChris Mason int ret = 0; 417aa5d6bedSChris Mason int wret; 418be0e5c09SChris Mason for (i = level; i < MAX_LEVEL; i++) { 419eb60ceacSChris Mason struct node *t; 420be0e5c09SChris Mason int tslot = path->slots[i]; 421eb60ceacSChris Mason if (!path->nodes[i]) 422be0e5c09SChris Mason break; 423eb60ceacSChris Mason t = &path->nodes[i]->node; 424be0e5c09SChris Mason memcpy(t->keys + tslot, key, sizeof(*key)); 425aa5d6bedSChris Mason wret = write_tree_block(root, path->nodes[i]); 426aa5d6bedSChris Mason if (wret) 427aa5d6bedSChris Mason ret = wret; 428be0e5c09SChris Mason if (tslot != 0) 429be0e5c09SChris Mason break; 430be0e5c09SChris Mason } 431aa5d6bedSChris Mason return ret; 432be0e5c09SChris Mason } 433be0e5c09SChris Mason 43474123bd7SChris Mason /* 43574123bd7SChris Mason * try to push data from one node into the next node left in the 43674123bd7SChris Mason * tree. The src node is found at specified level in the path. 43774123bd7SChris Mason * If some bytes were pushed, return 0, otherwise return 1. 43874123bd7SChris Mason * 43974123bd7SChris Mason * Lower nodes/leaves in the path are not touched, higher nodes may 44074123bd7SChris Mason * be modified to reflect the push. 44174123bd7SChris Mason * 44274123bd7SChris Mason * The path is altered to reflect the push. 443aa5d6bedSChris Mason * 444aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 445aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 44674123bd7SChris Mason */ 447bb803951SChris Mason static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf, 448bb803951SChris Mason struct tree_buffer *src_buf) 449be0e5c09SChris Mason { 450bb803951SChris Mason struct node *src = &src_buf->node; 451bb803951SChris Mason struct node *dst = &dst_buf->node; 452be0e5c09SChris Mason int push_items = 0; 453bb803951SChris Mason int src_nritems; 454bb803951SChris Mason int dst_nritems; 455aa5d6bedSChris Mason int ret = 0; 456aa5d6bedSChris Mason int wret; 457be0e5c09SChris Mason 458be0e5c09SChris Mason src_nritems = src->header.nritems; 459bb803951SChris Mason dst_nritems = dst->header.nritems; 460bb803951SChris Mason push_items = NODEPTRS_PER_BLOCK - dst_nritems; 461eb60ceacSChris Mason if (push_items <= 0) { 462be0e5c09SChris Mason return 1; 463eb60ceacSChris Mason } 464be0e5c09SChris Mason 465be0e5c09SChris Mason if (src_nritems < push_items) 466be0e5c09SChris Mason push_items =src_nritems; 467bb803951SChris Mason memcpy(dst->keys + dst_nritems, src->keys, 468be0e5c09SChris Mason push_items * sizeof(struct key)); 469bb803951SChris Mason memcpy(dst->blockptrs + dst_nritems, src->blockptrs, 470be0e5c09SChris Mason push_items * sizeof(u64)); 471bb803951SChris Mason if (push_items < src_nritems) { 472bb803951SChris Mason memmove(src->keys, src->keys + push_items, 473bb803951SChris Mason (src_nritems - push_items) * sizeof(struct key)); 474bb803951SChris Mason memmove(src->blockptrs, src->blockptrs + push_items, 475bb803951SChris Mason (src_nritems - push_items) * sizeof(u64)); 476bb803951SChris Mason } 477be0e5c09SChris Mason src->header.nritems -= push_items; 478be0e5c09SChris Mason dst->header.nritems += push_items; 479be0e5c09SChris Mason 480bb803951SChris Mason wret = write_tree_block(root, src_buf); 481bb803951SChris Mason if (wret < 0) 482bb803951SChris Mason ret = wret; 483eb60ceacSChris Mason 484bb803951SChris Mason wret = write_tree_block(root, dst_buf); 485bb803951SChris Mason if (wret < 0) 486bb803951SChris Mason ret = wret; 487bb803951SChris Mason return ret; 488be0e5c09SChris Mason } 489be0e5c09SChris Mason 49097571fd0SChris Mason /* 49197571fd0SChris Mason * helper function to insert a new root level in the tree. 49297571fd0SChris Mason * A new node is allocated, and a single item is inserted to 49397571fd0SChris Mason * point to the existing root 494aa5d6bedSChris Mason * 495aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 49697571fd0SChris Mason */ 4975de08d7dSChris Mason static int insert_new_root(struct ctree_root *root, 4985de08d7dSChris Mason struct ctree_path *path, int level) 49974123bd7SChris Mason { 50074123bd7SChris Mason struct tree_buffer *t; 5015c680ed6SChris Mason struct node *lower; 5025c680ed6SChris Mason struct node *c; 5035c680ed6SChris Mason struct key *lower_key; 5045c680ed6SChris Mason 5055c680ed6SChris Mason BUG_ON(path->nodes[level]); 5065c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 5075c680ed6SChris Mason 50874123bd7SChris Mason t = alloc_free_block(root); 50974123bd7SChris Mason c = &t->node; 51074123bd7SChris Mason memset(c, 0, sizeof(c)); 5115c680ed6SChris Mason c->header.nritems = 1; 51274123bd7SChris Mason c->header.flags = node_level(level); 51374123bd7SChris Mason c->header.blocknr = t->blocknr; 514cfaa7295SChris Mason c->header.parentid = root->node->node.header.parentid; 51574123bd7SChris Mason lower = &path->nodes[level-1]->node; 51674123bd7SChris Mason if (is_leaf(lower->header.flags)) 51774123bd7SChris Mason lower_key = &((struct leaf *)lower)->items[0].key; 51874123bd7SChris Mason else 51974123bd7SChris Mason lower_key = lower->keys; 52074123bd7SChris Mason memcpy(c->keys, lower_key, sizeof(struct key)); 52174123bd7SChris Mason c->blockptrs[0] = path->nodes[level-1]->blocknr; 522cfaa7295SChris Mason /* the super has an extra ref to root->node */ 52374123bd7SChris Mason tree_block_release(root, root->node); 52474123bd7SChris Mason root->node = t; 52574123bd7SChris Mason t->count++; 52674123bd7SChris Mason write_tree_block(root, t); 52774123bd7SChris Mason path->nodes[level] = t; 52874123bd7SChris Mason path->slots[level] = 0; 52974123bd7SChris Mason return 0; 53074123bd7SChris Mason } 5315c680ed6SChris Mason 5325c680ed6SChris Mason /* 5335c680ed6SChris Mason * worker function to insert a single pointer in a node. 5345c680ed6SChris Mason * the node should have enough room for the pointer already 53597571fd0SChris Mason * 5365c680ed6SChris Mason * slot and level indicate where you want the key to go, and 5375c680ed6SChris Mason * blocknr is the block the key points to. 538aa5d6bedSChris Mason * 539aa5d6bedSChris Mason * returns zero on success and < 0 on any error 5405c680ed6SChris Mason */ 541aa5d6bedSChris Mason static int insert_ptr(struct ctree_root *root, 5425c680ed6SChris Mason struct ctree_path *path, struct key *key, 5435c680ed6SChris Mason u64 blocknr, int slot, int level) 5445c680ed6SChris Mason { 5455c680ed6SChris Mason struct node *lower; 5465c680ed6SChris Mason int nritems; 5475c680ed6SChris Mason 5485c680ed6SChris Mason BUG_ON(!path->nodes[level]); 54974123bd7SChris Mason lower = &path->nodes[level]->node; 55074123bd7SChris Mason nritems = lower->header.nritems; 55174123bd7SChris Mason if (slot > nritems) 55274123bd7SChris Mason BUG(); 55374123bd7SChris Mason if (nritems == NODEPTRS_PER_BLOCK) 55474123bd7SChris Mason BUG(); 55574123bd7SChris Mason if (slot != nritems) { 55674123bd7SChris Mason memmove(lower->keys + slot + 1, lower->keys + slot, 55774123bd7SChris Mason (nritems - slot) * sizeof(struct key)); 55874123bd7SChris Mason memmove(lower->blockptrs + slot + 1, lower->blockptrs + slot, 55974123bd7SChris Mason (nritems - slot) * sizeof(u64)); 56074123bd7SChris Mason } 56174123bd7SChris Mason memcpy(lower->keys + slot, key, sizeof(struct key)); 56274123bd7SChris Mason lower->blockptrs[slot] = blocknr; 56374123bd7SChris Mason lower->header.nritems++; 56474123bd7SChris Mason if (lower->keys[1].objectid == 0) 56574123bd7SChris Mason BUG(); 56674123bd7SChris Mason write_tree_block(root, path->nodes[level]); 56774123bd7SChris Mason return 0; 56874123bd7SChris Mason } 56974123bd7SChris Mason 57097571fd0SChris Mason /* 57197571fd0SChris Mason * split the node at the specified level in path in two. 57297571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 57397571fd0SChris Mason * 57497571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 57597571fd0SChris Mason * left and right, if either one works, it returns right away. 576aa5d6bedSChris Mason * 577aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 57897571fd0SChris Mason */ 579aa5d6bedSChris Mason static int split_node(struct ctree_root *root, struct ctree_path *path, 580aa5d6bedSChris Mason int level) 581be0e5c09SChris Mason { 5825c680ed6SChris Mason struct tree_buffer *t; 5835c680ed6SChris Mason struct node *c; 5845c680ed6SChris Mason struct tree_buffer *split_buffer; 5855c680ed6SChris Mason struct node *split; 586be0e5c09SChris Mason int mid; 5875c680ed6SChris Mason int ret; 588aa5d6bedSChris Mason int wret; 589be0e5c09SChris Mason 5905c680ed6SChris Mason t = path->nodes[level]; 591eb60ceacSChris Mason c = &t->node; 5925c680ed6SChris Mason if (t == root->node) { 5935c680ed6SChris Mason /* trying to split the root, lets make a new one */ 5945c680ed6SChris Mason ret = insert_new_root(root, path, level + 1); 5955c680ed6SChris Mason if (ret) 5965c680ed6SChris Mason return ret; 5975c680ed6SChris Mason } 5985c680ed6SChris Mason split_buffer = alloc_free_block(root); 5995c680ed6SChris Mason split = &split_buffer->node; 6005c680ed6SChris Mason split->header.flags = c->header.flags; 6015c680ed6SChris Mason split->header.blocknr = split_buffer->blocknr; 6025c680ed6SChris Mason split->header.parentid = root->node->node.header.parentid; 603be0e5c09SChris Mason mid = (c->header.nritems + 1) / 2; 6045c680ed6SChris Mason memcpy(split->keys, c->keys + mid, 605be0e5c09SChris Mason (c->header.nritems - mid) * sizeof(struct key)); 6065c680ed6SChris Mason memcpy(split->blockptrs, c->blockptrs + mid, 607be0e5c09SChris Mason (c->header.nritems - mid) * sizeof(u64)); 6085c680ed6SChris Mason split->header.nritems = c->header.nritems - mid; 609be0e5c09SChris Mason c->header.nritems = mid; 610aa5d6bedSChris Mason ret = 0; 611aa5d6bedSChris Mason 612aa5d6bedSChris Mason wret = write_tree_block(root, t); 613aa5d6bedSChris Mason if (wret) 614aa5d6bedSChris Mason ret = wret; 615aa5d6bedSChris Mason wret = write_tree_block(root, split_buffer); 616aa5d6bedSChris Mason if (wret) 617aa5d6bedSChris Mason ret = wret; 618aa5d6bedSChris Mason wret = insert_ptr(root, path, split->keys, split_buffer->blocknr, 6195c680ed6SChris Mason path->slots[level + 1] + 1, level + 1); 620aa5d6bedSChris Mason if (wret) 621aa5d6bedSChris Mason ret = wret; 622aa5d6bedSChris Mason 6235de08d7dSChris Mason if (path->slots[level] >= mid) { 6245c680ed6SChris Mason path->slots[level] -= mid; 6255c680ed6SChris Mason tree_block_release(root, t); 6265c680ed6SChris Mason path->nodes[level] = split_buffer; 6275c680ed6SChris Mason path->slots[level + 1] += 1; 628eb60ceacSChris Mason } else { 6295c680ed6SChris Mason tree_block_release(root, split_buffer); 630be0e5c09SChris Mason } 631aa5d6bedSChris Mason return ret; 632be0e5c09SChris Mason } 633be0e5c09SChris Mason 63474123bd7SChris Mason /* 63574123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 63674123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 63774123bd7SChris Mason * space used both by the item structs and the item data 63874123bd7SChris Mason */ 639aa5d6bedSChris Mason static int leaf_space_used(struct leaf *l, int start, int nr) 640be0e5c09SChris Mason { 641be0e5c09SChris Mason int data_len; 642be0e5c09SChris Mason int end = start + nr - 1; 643be0e5c09SChris Mason 644be0e5c09SChris Mason if (!nr) 645be0e5c09SChris Mason return 0; 646be0e5c09SChris Mason data_len = l->items[start].offset + l->items[start].size; 647be0e5c09SChris Mason data_len = data_len - l->items[end].offset; 648be0e5c09SChris Mason data_len += sizeof(struct item) * nr; 649be0e5c09SChris Mason return data_len; 650be0e5c09SChris Mason } 651be0e5c09SChris Mason 65274123bd7SChris Mason /* 65300ec4c51SChris Mason * push some data in the path leaf to the right, trying to free up at 65400ec4c51SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 655aa5d6bedSChris Mason * 656aa5d6bedSChris Mason * returns 1 if the push failed because the other node didn't have enough 657aa5d6bedSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 65800ec4c51SChris Mason */ 659aa5d6bedSChris Mason static int push_leaf_right(struct ctree_root *root, struct ctree_path *path, 66000ec4c51SChris Mason int data_size) 66100ec4c51SChris Mason { 66200ec4c51SChris Mason struct tree_buffer *left_buf = path->nodes[0]; 66300ec4c51SChris Mason struct leaf *left = &left_buf->leaf; 66400ec4c51SChris Mason struct leaf *right; 66500ec4c51SChris Mason struct tree_buffer *right_buf; 66600ec4c51SChris Mason struct tree_buffer *upper; 66700ec4c51SChris Mason int slot; 66800ec4c51SChris Mason int i; 66900ec4c51SChris Mason int free_space; 67000ec4c51SChris Mason int push_space = 0; 67100ec4c51SChris Mason int push_items = 0; 67200ec4c51SChris Mason struct item *item; 67300ec4c51SChris Mason 67400ec4c51SChris Mason slot = path->slots[1]; 67500ec4c51SChris Mason if (!path->nodes[1]) { 67600ec4c51SChris Mason return 1; 67700ec4c51SChris Mason } 67800ec4c51SChris Mason upper = path->nodes[1]; 67900ec4c51SChris Mason if (slot >= upper->node.header.nritems - 1) { 68000ec4c51SChris Mason return 1; 68100ec4c51SChris Mason } 68200ec4c51SChris Mason right_buf = read_tree_block(root, upper->node.blockptrs[slot + 1]); 68300ec4c51SChris Mason right = &right_buf->leaf; 68400ec4c51SChris Mason free_space = leaf_free_space(right); 68500ec4c51SChris Mason if (free_space < data_size + sizeof(struct item)) { 68600ec4c51SChris Mason tree_block_release(root, right_buf); 68700ec4c51SChris Mason return 1; 68800ec4c51SChris Mason } 68900ec4c51SChris Mason for (i = left->header.nritems - 1; i >= 0; i--) { 69000ec4c51SChris Mason item = left->items + i; 69100ec4c51SChris Mason if (path->slots[0] == i) 69200ec4c51SChris Mason push_space += data_size + sizeof(*item); 69300ec4c51SChris Mason if (item->size + sizeof(*item) + push_space > free_space) 69400ec4c51SChris Mason break; 69500ec4c51SChris Mason push_items++; 69600ec4c51SChris Mason push_space += item->size + sizeof(*item); 69700ec4c51SChris Mason } 69800ec4c51SChris Mason if (push_items == 0) { 69900ec4c51SChris Mason tree_block_release(root, right_buf); 70000ec4c51SChris Mason return 1; 70100ec4c51SChris Mason } 70200ec4c51SChris Mason /* push left to right */ 70300ec4c51SChris Mason push_space = left->items[left->header.nritems - push_items].offset + 70400ec4c51SChris Mason left->items[left->header.nritems - push_items].size; 70500ec4c51SChris Mason push_space -= leaf_data_end(left); 70600ec4c51SChris Mason /* make room in the right data area */ 70700ec4c51SChris Mason memmove(right->data + leaf_data_end(right) - push_space, 70800ec4c51SChris Mason right->data + leaf_data_end(right), 70900ec4c51SChris Mason LEAF_DATA_SIZE - leaf_data_end(right)); 71000ec4c51SChris Mason /* copy from the left data area */ 71100ec4c51SChris Mason memcpy(right->data + LEAF_DATA_SIZE - push_space, 71200ec4c51SChris Mason left->data + leaf_data_end(left), 71300ec4c51SChris Mason push_space); 71400ec4c51SChris Mason memmove(right->items + push_items, right->items, 71500ec4c51SChris Mason right->header.nritems * sizeof(struct item)); 71600ec4c51SChris Mason /* copy the items from left to right */ 71700ec4c51SChris Mason memcpy(right->items, left->items + left->header.nritems - push_items, 71800ec4c51SChris Mason push_items * sizeof(struct item)); 71900ec4c51SChris Mason 72000ec4c51SChris Mason /* update the item pointers */ 72100ec4c51SChris Mason right->header.nritems += push_items; 72200ec4c51SChris Mason push_space = LEAF_DATA_SIZE; 72300ec4c51SChris Mason for (i = 0; i < right->header.nritems; i++) { 72400ec4c51SChris Mason right->items[i].offset = push_space - right->items[i].size; 72500ec4c51SChris Mason push_space = right->items[i].offset; 72600ec4c51SChris Mason } 72700ec4c51SChris Mason left->header.nritems -= push_items; 72800ec4c51SChris Mason 72900ec4c51SChris Mason write_tree_block(root, left_buf); 73000ec4c51SChris Mason write_tree_block(root, right_buf); 73100ec4c51SChris Mason memcpy(upper->node.keys + slot + 1, 73200ec4c51SChris Mason &right->items[0].key, sizeof(struct key)); 73300ec4c51SChris Mason write_tree_block(root, upper); 73400ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 73500ec4c51SChris Mason if (path->slots[0] >= left->header.nritems) { 73600ec4c51SChris Mason path->slots[0] -= left->header.nritems; 73700ec4c51SChris Mason tree_block_release(root, path->nodes[0]); 73800ec4c51SChris Mason path->nodes[0] = right_buf; 73900ec4c51SChris Mason path->slots[1] += 1; 74000ec4c51SChris Mason } else { 74100ec4c51SChris Mason tree_block_release(root, right_buf); 74200ec4c51SChris Mason } 74300ec4c51SChris Mason return 0; 74400ec4c51SChris Mason } 74500ec4c51SChris Mason /* 74674123bd7SChris Mason * push some data in the path leaf to the left, trying to free up at 74774123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 74874123bd7SChris Mason */ 749aa5d6bedSChris Mason static int push_leaf_left(struct ctree_root *root, struct ctree_path *path, 750be0e5c09SChris Mason int data_size) 751be0e5c09SChris Mason { 752eb60ceacSChris Mason struct tree_buffer *right_buf = path->nodes[0]; 753eb60ceacSChris Mason struct leaf *right = &right_buf->leaf; 754eb60ceacSChris Mason struct tree_buffer *t; 755be0e5c09SChris Mason struct leaf *left; 756be0e5c09SChris Mason int slot; 757be0e5c09SChris Mason int i; 758be0e5c09SChris Mason int free_space; 759be0e5c09SChris Mason int push_space = 0; 760be0e5c09SChris Mason int push_items = 0; 761be0e5c09SChris Mason struct item *item; 762be0e5c09SChris Mason int old_left_nritems; 763aa5d6bedSChris Mason int ret = 0; 764aa5d6bedSChris Mason int wret; 765be0e5c09SChris Mason 766be0e5c09SChris Mason slot = path->slots[1]; 767be0e5c09SChris Mason if (slot == 0) { 768be0e5c09SChris Mason return 1; 769be0e5c09SChris Mason } 770be0e5c09SChris Mason if (!path->nodes[1]) { 771be0e5c09SChris Mason return 1; 772be0e5c09SChris Mason } 773eb60ceacSChris Mason t = read_tree_block(root, path->nodes[1]->node.blockptrs[slot - 1]); 774eb60ceacSChris Mason left = &t->leaf; 775be0e5c09SChris Mason free_space = leaf_free_space(left); 776be0e5c09SChris Mason if (free_space < data_size + sizeof(struct item)) { 777eb60ceacSChris Mason tree_block_release(root, t); 778be0e5c09SChris Mason return 1; 779be0e5c09SChris Mason } 780be0e5c09SChris Mason for (i = 0; i < right->header.nritems; i++) { 781be0e5c09SChris Mason item = right->items + i; 782be0e5c09SChris Mason if (path->slots[0] == i) 783be0e5c09SChris Mason push_space += data_size + sizeof(*item); 784be0e5c09SChris Mason if (item->size + sizeof(*item) + push_space > free_space) 785be0e5c09SChris Mason break; 786be0e5c09SChris Mason push_items++; 787be0e5c09SChris Mason push_space += item->size + sizeof(*item); 788be0e5c09SChris Mason } 789be0e5c09SChris Mason if (push_items == 0) { 790eb60ceacSChris Mason tree_block_release(root, t); 791be0e5c09SChris Mason return 1; 792be0e5c09SChris Mason } 793be0e5c09SChris Mason /* push data from right to left */ 794be0e5c09SChris Mason memcpy(left->items + left->header.nritems, 795be0e5c09SChris Mason right->items, push_items * sizeof(struct item)); 796be0e5c09SChris Mason push_space = LEAF_DATA_SIZE - right->items[push_items -1].offset; 797be0e5c09SChris Mason memcpy(left->data + leaf_data_end(left) - push_space, 798be0e5c09SChris Mason right->data + right->items[push_items - 1].offset, 799be0e5c09SChris Mason push_space); 800be0e5c09SChris Mason old_left_nritems = left->header.nritems; 801eb60ceacSChris Mason BUG_ON(old_left_nritems < 0); 802eb60ceacSChris Mason 803be0e5c09SChris Mason for(i = old_left_nritems; i < old_left_nritems + push_items; i++) { 804be0e5c09SChris Mason left->items[i].offset -= LEAF_DATA_SIZE - 805be0e5c09SChris Mason left->items[old_left_nritems -1].offset; 806be0e5c09SChris Mason } 807be0e5c09SChris Mason left->header.nritems += push_items; 808be0e5c09SChris Mason 809be0e5c09SChris Mason /* fixup right node */ 810be0e5c09SChris Mason push_space = right->items[push_items-1].offset - leaf_data_end(right); 811be0e5c09SChris Mason memmove(right->data + LEAF_DATA_SIZE - push_space, right->data + 812be0e5c09SChris Mason leaf_data_end(right), push_space); 813be0e5c09SChris Mason memmove(right->items, right->items + push_items, 814be0e5c09SChris Mason (right->header.nritems - push_items) * sizeof(struct item)); 815be0e5c09SChris Mason right->header.nritems -= push_items; 816be0e5c09SChris Mason push_space = LEAF_DATA_SIZE; 817eb60ceacSChris Mason 818be0e5c09SChris Mason for (i = 0; i < right->header.nritems; i++) { 819be0e5c09SChris Mason right->items[i].offset = push_space - right->items[i].size; 820be0e5c09SChris Mason push_space = right->items[i].offset; 821be0e5c09SChris Mason } 822eb60ceacSChris Mason 823aa5d6bedSChris Mason wret = write_tree_block(root, t); 824aa5d6bedSChris Mason if (wret) 825aa5d6bedSChris Mason ret = wret; 826aa5d6bedSChris Mason wret = write_tree_block(root, right_buf); 827aa5d6bedSChris Mason if (wret) 828aa5d6bedSChris Mason ret = wret; 829eb60ceacSChris Mason 830aa5d6bedSChris Mason wret = fixup_low_keys(root, path, &right->items[0].key, 1); 831aa5d6bedSChris Mason if (wret) 832aa5d6bedSChris Mason ret = wret; 833be0e5c09SChris Mason 834be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 835be0e5c09SChris Mason if (path->slots[0] < push_items) { 836be0e5c09SChris Mason path->slots[0] += old_left_nritems; 837eb60ceacSChris Mason tree_block_release(root, path->nodes[0]); 838eb60ceacSChris Mason path->nodes[0] = t; 839be0e5c09SChris Mason path->slots[1] -= 1; 840be0e5c09SChris Mason } else { 841eb60ceacSChris Mason tree_block_release(root, t); 842be0e5c09SChris Mason path->slots[0] -= push_items; 843be0e5c09SChris Mason } 844eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 845aa5d6bedSChris Mason return ret; 846be0e5c09SChris Mason } 847be0e5c09SChris Mason 84874123bd7SChris Mason /* 84974123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 85074123bd7SChris Mason * available for the resulting leaf level of the path. 851aa5d6bedSChris Mason * 852aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 85374123bd7SChris Mason */ 854aa5d6bedSChris Mason static int split_leaf(struct ctree_root *root, struct ctree_path *path, 855aa5d6bedSChris Mason int data_size) 856be0e5c09SChris Mason { 857aa5d6bedSChris Mason struct tree_buffer *l_buf; 858aa5d6bedSChris Mason struct leaf *l; 859eb60ceacSChris Mason int nritems; 860eb60ceacSChris Mason int mid; 861eb60ceacSChris Mason int slot; 862be0e5c09SChris Mason struct leaf *right; 863eb60ceacSChris Mason struct tree_buffer *right_buffer; 864be0e5c09SChris Mason int space_needed = data_size + sizeof(struct item); 865be0e5c09SChris Mason int data_copy_size; 866be0e5c09SChris Mason int rt_data_off; 867be0e5c09SChris Mason int i; 868be0e5c09SChris Mason int ret; 869aa5d6bedSChris Mason int wret; 870be0e5c09SChris Mason 871aa5d6bedSChris Mason wret = push_leaf_left(root, path, data_size); 872aa5d6bedSChris Mason if (wret < 0) 873aa5d6bedSChris Mason return wret; 874aa5d6bedSChris Mason if (wret) { 875aa5d6bedSChris Mason wret = push_leaf_right(root, path, data_size); 876aa5d6bedSChris Mason if (wret < 0) 877aa5d6bedSChris Mason return wret; 878aa5d6bedSChris Mason } 879eb60ceacSChris Mason l_buf = path->nodes[0]; 880eb60ceacSChris Mason l = &l_buf->leaf; 881aa5d6bedSChris Mason 882aa5d6bedSChris Mason /* did the pushes work? */ 883eb60ceacSChris Mason if (leaf_free_space(l) >= sizeof(struct item) + data_size) 884be0e5c09SChris Mason return 0; 885aa5d6bedSChris Mason 8865c680ed6SChris Mason if (!path->nodes[1]) { 8875c680ed6SChris Mason ret = insert_new_root(root, path, 1); 8885c680ed6SChris Mason if (ret) 8895c680ed6SChris Mason return ret; 8905c680ed6SChris Mason } 891eb60ceacSChris Mason slot = path->slots[0]; 892eb60ceacSChris Mason nritems = l->header.nritems; 893eb60ceacSChris Mason mid = (nritems + 1)/ 2; 894eb60ceacSChris Mason 895eb60ceacSChris Mason right_buffer = alloc_free_block(root); 896eb60ceacSChris Mason BUG_ON(!right_buffer); 897eb60ceacSChris Mason BUG_ON(mid == nritems); 898eb60ceacSChris Mason right = &right_buffer->leaf; 899be0e5c09SChris Mason memset(right, 0, sizeof(*right)); 900be0e5c09SChris Mason if (mid <= slot) { 90197571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 902be0e5c09SChris Mason if (leaf_space_used(l, mid, nritems - mid) + space_needed > 903be0e5c09SChris Mason LEAF_DATA_SIZE) 904be0e5c09SChris Mason BUG(); 905be0e5c09SChris Mason } else { 90697571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 907be0e5c09SChris Mason if (leaf_space_used(l, 0, mid + 1) + space_needed > 908be0e5c09SChris Mason LEAF_DATA_SIZE) 909be0e5c09SChris Mason BUG(); 910be0e5c09SChris Mason } 911be0e5c09SChris Mason right->header.nritems = nritems - mid; 912eb60ceacSChris Mason right->header.blocknr = right_buffer->blocknr; 913eb60ceacSChris Mason right->header.flags = node_level(0); 914cfaa7295SChris Mason right->header.parentid = root->node->node.header.parentid; 915be0e5c09SChris Mason data_copy_size = l->items[mid].offset + l->items[mid].size - 916be0e5c09SChris Mason leaf_data_end(l); 917be0e5c09SChris Mason memcpy(right->items, l->items + mid, 918be0e5c09SChris Mason (nritems - mid) * sizeof(struct item)); 919be0e5c09SChris Mason memcpy(right->data + LEAF_DATA_SIZE - data_copy_size, 920be0e5c09SChris Mason l->data + leaf_data_end(l), data_copy_size); 921be0e5c09SChris Mason rt_data_off = LEAF_DATA_SIZE - 922be0e5c09SChris Mason (l->items[mid].offset + l->items[mid].size); 92374123bd7SChris Mason 92474123bd7SChris Mason for (i = 0; i < right->header.nritems; i++) 925be0e5c09SChris Mason right->items[i].offset += rt_data_off; 92674123bd7SChris Mason 927be0e5c09SChris Mason l->header.nritems = mid; 928aa5d6bedSChris Mason ret = 0; 929aa5d6bedSChris Mason wret = insert_ptr(root, path, &right->items[0].key, 9305c680ed6SChris Mason right_buffer->blocknr, path->slots[1] + 1, 1); 931aa5d6bedSChris Mason if (wret) 932aa5d6bedSChris Mason ret = wret; 933aa5d6bedSChris Mason wret = write_tree_block(root, right_buffer); 934aa5d6bedSChris Mason if (wret) 935aa5d6bedSChris Mason ret = wret; 936aa5d6bedSChris Mason wret = write_tree_block(root, l_buf); 937aa5d6bedSChris Mason if (wret) 938aa5d6bedSChris Mason ret = wret; 939eb60ceacSChris Mason 940eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 941be0e5c09SChris Mason if (mid <= slot) { 942eb60ceacSChris Mason tree_block_release(root, path->nodes[0]); 943eb60ceacSChris Mason path->nodes[0] = right_buffer; 944be0e5c09SChris Mason path->slots[0] -= mid; 945be0e5c09SChris Mason path->slots[1] += 1; 946eb60ceacSChris Mason } else 947eb60ceacSChris Mason tree_block_release(root, right_buffer); 948eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 949be0e5c09SChris Mason return ret; 950be0e5c09SChris Mason } 951be0e5c09SChris Mason 95274123bd7SChris Mason /* 95374123bd7SChris Mason * Given a key and some data, insert an item into the tree. 95474123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 95574123bd7SChris Mason */ 956be0e5c09SChris Mason int insert_item(struct ctree_root *root, struct key *key, 957be0e5c09SChris Mason void *data, int data_size) 958be0e5c09SChris Mason { 959aa5d6bedSChris Mason int ret = 0; 960aa5d6bedSChris Mason int wret; 961be0e5c09SChris Mason int slot; 962eb60ceacSChris Mason int slot_orig; 963be0e5c09SChris Mason struct leaf *leaf; 964eb60ceacSChris Mason struct tree_buffer *leaf_buf; 965be0e5c09SChris Mason unsigned int nritems; 966be0e5c09SChris Mason unsigned int data_end; 967be0e5c09SChris Mason struct ctree_path path; 968be0e5c09SChris Mason 96974123bd7SChris Mason /* create a root if there isn't one */ 9705c680ed6SChris Mason if (!root->node) 971cfaa7295SChris Mason BUG(); 972be0e5c09SChris Mason init_path(&path); 9735c680ed6SChris Mason ret = search_slot(root, key, &path, data_size); 974eb60ceacSChris Mason if (ret == 0) { 975eb60ceacSChris Mason release_path(root, &path); 976be0e5c09SChris Mason return -EEXIST; 977eb60ceacSChris Mason } 978aa5d6bedSChris Mason if (ret < 0) { 979aa5d6bedSChris Mason release_path(root, &path); 980aa5d6bedSChris Mason return ret; 981aa5d6bedSChris Mason } 982be0e5c09SChris Mason 983eb60ceacSChris Mason slot_orig = path.slots[0]; 984eb60ceacSChris Mason leaf_buf = path.nodes[0]; 985eb60ceacSChris Mason leaf = &leaf_buf->leaf; 98674123bd7SChris Mason 987be0e5c09SChris Mason nritems = leaf->header.nritems; 988be0e5c09SChris Mason data_end = leaf_data_end(leaf); 989eb60ceacSChris Mason 990be0e5c09SChris Mason if (leaf_free_space(leaf) < sizeof(struct item) + data_size) 991be0e5c09SChris Mason BUG(); 992be0e5c09SChris Mason 993be0e5c09SChris Mason slot = path.slots[0]; 994eb60ceacSChris Mason BUG_ON(slot < 0); 995be0e5c09SChris Mason if (slot != nritems) { 996be0e5c09SChris Mason int i; 997be0e5c09SChris Mason unsigned int old_data = leaf->items[slot].offset + 998be0e5c09SChris Mason leaf->items[slot].size; 999be0e5c09SChris Mason 1000be0e5c09SChris Mason /* 1001be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 1002be0e5c09SChris Mason */ 1003be0e5c09SChris Mason /* first correct the data pointers */ 1004be0e5c09SChris Mason for (i = slot; i < nritems; i++) 1005be0e5c09SChris Mason leaf->items[i].offset -= data_size; 1006be0e5c09SChris Mason 1007be0e5c09SChris Mason /* shift the items */ 1008be0e5c09SChris Mason memmove(leaf->items + slot + 1, leaf->items + slot, 1009be0e5c09SChris Mason (nritems - slot) * sizeof(struct item)); 1010be0e5c09SChris Mason 1011be0e5c09SChris Mason /* shift the data */ 1012be0e5c09SChris Mason memmove(leaf->data + data_end - data_size, leaf->data + 1013be0e5c09SChris Mason data_end, old_data - data_end); 1014be0e5c09SChris Mason data_end = old_data; 1015be0e5c09SChris Mason } 101674123bd7SChris Mason /* copy the new data in */ 1017be0e5c09SChris Mason memcpy(&leaf->items[slot].key, key, sizeof(struct key)); 1018be0e5c09SChris Mason leaf->items[slot].offset = data_end - data_size; 1019be0e5c09SChris Mason leaf->items[slot].size = data_size; 1020be0e5c09SChris Mason memcpy(leaf->data + data_end - data_size, data, data_size); 1021be0e5c09SChris Mason leaf->header.nritems += 1; 1022aa5d6bedSChris Mason 1023aa5d6bedSChris Mason ret = 0; 10248e19f2cdSChris Mason if (slot == 0) 1025aa5d6bedSChris Mason ret = fixup_low_keys(root, &path, key, 1); 1026aa5d6bedSChris Mason 1027aa5d6bedSChris Mason wret = write_tree_block(root, leaf_buf); 1028aa5d6bedSChris Mason if (wret) 1029aa5d6bedSChris Mason ret = wret; 1030aa5d6bedSChris Mason 1031be0e5c09SChris Mason if (leaf_free_space(leaf) < 0) 1032be0e5c09SChris Mason BUG(); 1033bb803951SChris Mason check_leaf(&path, 0); 1034eb60ceacSChris Mason release_path(root, &path); 1035aa5d6bedSChris Mason return ret; 1036be0e5c09SChris Mason } 1037be0e5c09SChris Mason 103874123bd7SChris Mason /* 10395de08d7dSChris Mason * delete the pointer from a given node. 104074123bd7SChris Mason * 104174123bd7SChris Mason * If the delete empties a node, the node is removed from the tree, 104274123bd7SChris Mason * continuing all the way the root if required. The root is converted into 104374123bd7SChris Mason * a leaf if all the nodes are emptied. 104474123bd7SChris Mason */ 1045bb803951SChris Mason static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, 1046bb803951SChris Mason int slot) 1047be0e5c09SChris Mason { 1048be0e5c09SChris Mason struct node *node; 1049bb803951SChris Mason struct tree_buffer *parent = path->nodes[level]; 1050be0e5c09SChris Mason int nritems; 1051aa5d6bedSChris Mason int ret = 0; 1052bb803951SChris Mason int wret; 1053be0e5c09SChris Mason 1054bb803951SChris Mason node = &parent->node; 1055be0e5c09SChris Mason nritems = node->header.nritems; 1056be0e5c09SChris Mason 1057be0e5c09SChris Mason if (slot != nritems -1) { 1058be0e5c09SChris Mason memmove(node->keys + slot, node->keys + slot + 1, 1059be0e5c09SChris Mason sizeof(struct key) * (nritems - slot - 1)); 1060be0e5c09SChris Mason memmove(node->blockptrs + slot, 1061be0e5c09SChris Mason node->blockptrs + slot + 1, 1062be0e5c09SChris Mason sizeof(u64) * (nritems - slot - 1)); 1063be0e5c09SChris Mason } 1064be0e5c09SChris Mason node->header.nritems--; 1065bb803951SChris Mason if (node->header.nritems == 0 && parent == root->node) { 1066bb803951SChris Mason BUG_ON(node_level(root->node->node.header.flags) != 1); 1067eb60ceacSChris Mason /* just turn the root into a leaf and break */ 1068eb60ceacSChris Mason root->node->node.header.flags = node_level(0); 1069bb803951SChris Mason } else if (slot == 0) { 1070bb803951SChris Mason wret = fixup_low_keys(root, path, node->keys, level + 1); 10710f70abe2SChris Mason if (wret) 10720f70abe2SChris Mason ret = wret; 1073be0e5c09SChris Mason } 1074bb803951SChris Mason wret = write_tree_block(root, parent); 1075bb803951SChris Mason if (wret) 1076bb803951SChris Mason ret = wret; 1077aa5d6bedSChris Mason return ret; 1078be0e5c09SChris Mason } 1079be0e5c09SChris Mason 108074123bd7SChris Mason /* 108174123bd7SChris Mason * delete the item at the leaf level in path. If that empties 108274123bd7SChris Mason * the leaf, remove it from the tree 108374123bd7SChris Mason */ 10844920c9acSChris Mason int del_item(struct ctree_root *root, struct ctree_path *path) 1085be0e5c09SChris Mason { 1086be0e5c09SChris Mason int slot; 1087be0e5c09SChris Mason struct leaf *leaf; 1088eb60ceacSChris Mason struct tree_buffer *leaf_buf; 1089be0e5c09SChris Mason int doff; 1090be0e5c09SChris Mason int dsize; 1091aa5d6bedSChris Mason int ret = 0; 1092aa5d6bedSChris Mason int wret; 1093be0e5c09SChris Mason 1094eb60ceacSChris Mason leaf_buf = path->nodes[0]; 1095eb60ceacSChris Mason leaf = &leaf_buf->leaf; 10964920c9acSChris Mason slot = path->slots[0]; 1097be0e5c09SChris Mason doff = leaf->items[slot].offset; 1098be0e5c09SChris Mason dsize = leaf->items[slot].size; 1099be0e5c09SChris Mason 1100be0e5c09SChris Mason if (slot != leaf->header.nritems - 1) { 1101be0e5c09SChris Mason int i; 1102be0e5c09SChris Mason int data_end = leaf_data_end(leaf); 1103be0e5c09SChris Mason memmove(leaf->data + data_end + dsize, 1104be0e5c09SChris Mason leaf->data + data_end, 1105be0e5c09SChris Mason doff - data_end); 1106be0e5c09SChris Mason for (i = slot + 1; i < leaf->header.nritems; i++) 1107be0e5c09SChris Mason leaf->items[i].offset += dsize; 1108be0e5c09SChris Mason memmove(leaf->items + slot, leaf->items + slot + 1, 1109be0e5c09SChris Mason sizeof(struct item) * 1110be0e5c09SChris Mason (leaf->header.nritems - slot - 1)); 1111be0e5c09SChris Mason } 1112be0e5c09SChris Mason leaf->header.nritems -= 1; 111374123bd7SChris Mason /* delete the leaf if we've emptied it */ 1114be0e5c09SChris Mason if (leaf->header.nritems == 0) { 1115eb60ceacSChris Mason if (leaf_buf == root->node) { 1116eb60ceacSChris Mason leaf->header.flags = node_level(0); 1117eb60ceacSChris Mason write_tree_block(root, leaf_buf); 11189a8dd150SChris Mason } else { 1119bb803951SChris Mason wret = del_ptr(root, path, 1, path->slots[1]); 1120aa5d6bedSChris Mason if (wret) 1121aa5d6bedSChris Mason ret = wret; 11220f70abe2SChris Mason wret = free_extent(root, leaf_buf->blocknr, 1); 11230f70abe2SChris Mason if (wret) 11240f70abe2SChris Mason ret = wret; 11259a8dd150SChris Mason } 1126be0e5c09SChris Mason } else { 11275de08d7dSChris Mason int used = leaf_space_used(leaf, 0, leaf->header.nritems); 1128aa5d6bedSChris Mason if (slot == 0) { 1129aa5d6bedSChris Mason wret = fixup_low_keys(root, path, 1130aa5d6bedSChris Mason &leaf->items[0].key, 1); 1131aa5d6bedSChris Mason if (wret) 1132aa5d6bedSChris Mason ret = wret; 1133aa5d6bedSChris Mason } 1134aa5d6bedSChris Mason wret = write_tree_block(root, leaf_buf); 1135aa5d6bedSChris Mason if (wret) 1136aa5d6bedSChris Mason ret = wret; 1137aa5d6bedSChris Mason 113874123bd7SChris Mason /* delete the leaf if it is mostly empty */ 11395de08d7dSChris Mason if (used < LEAF_DATA_SIZE / 3) { 1140be0e5c09SChris Mason /* push_leaf_left fixes the path. 1141be0e5c09SChris Mason * make sure the path still points to our leaf 1142be0e5c09SChris Mason * for possible call to del_ptr below 1143be0e5c09SChris Mason */ 11444920c9acSChris Mason slot = path->slots[1]; 1145eb60ceacSChris Mason leaf_buf->count++; 1146aa5d6bedSChris Mason wret = push_leaf_left(root, path, 1); 1147aa5d6bedSChris Mason if (wret < 0) 1148aa5d6bedSChris Mason ret = wret; 1149aa5d6bedSChris Mason if (leaf->header.nritems) { 1150aa5d6bedSChris Mason wret = push_leaf_right(root, path, 1); 1151aa5d6bedSChris Mason if (wret < 0) 1152aa5d6bedSChris Mason ret = wret; 1153aa5d6bedSChris Mason } 1154be0e5c09SChris Mason if (leaf->header.nritems == 0) { 11555de08d7dSChris Mason u64 blocknr = leaf_buf->blocknr; 1156bb803951SChris Mason wret = del_ptr(root, path, 1, slot); 1157aa5d6bedSChris Mason if (wret) 1158aa5d6bedSChris Mason ret = wret; 11595de08d7dSChris Mason tree_block_release(root, leaf_buf); 11600f70abe2SChris Mason wret = free_extent(root, blocknr, 1); 11610f70abe2SChris Mason if (wret) 11620f70abe2SChris Mason ret = wret; 11635de08d7dSChris Mason } else { 1164eb60ceacSChris Mason tree_block_release(root, leaf_buf); 1165be0e5c09SChris Mason } 1166be0e5c09SChris Mason } 11679a8dd150SChris Mason } 1168aa5d6bedSChris Mason return ret; 11699a8dd150SChris Mason } 11709a8dd150SChris Mason 117197571fd0SChris Mason /* 117297571fd0SChris Mason * walk up the tree as far as required to find the next leaf. 11730f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 11740f70abe2SChris Mason * returns < 0 on io errors. 117597571fd0SChris Mason */ 1176d97e63b6SChris Mason int next_leaf(struct ctree_root *root, struct ctree_path *path) 1177d97e63b6SChris Mason { 1178d97e63b6SChris Mason int slot; 1179d97e63b6SChris Mason int level = 1; 1180d97e63b6SChris Mason u64 blocknr; 1181d97e63b6SChris Mason struct tree_buffer *c; 1182cfaa7295SChris Mason struct tree_buffer *next = NULL; 1183d97e63b6SChris Mason 1184d97e63b6SChris Mason while(level < MAX_LEVEL) { 1185d97e63b6SChris Mason if (!path->nodes[level]) 11860f70abe2SChris Mason return 1; 1187d97e63b6SChris Mason slot = path->slots[level] + 1; 1188d97e63b6SChris Mason c = path->nodes[level]; 1189d97e63b6SChris Mason if (slot >= c->node.header.nritems) { 1190d97e63b6SChris Mason level++; 1191d97e63b6SChris Mason continue; 1192d97e63b6SChris Mason } 1193d97e63b6SChris Mason blocknr = c->node.blockptrs[slot]; 1194cfaa7295SChris Mason if (next) 1195cfaa7295SChris Mason tree_block_release(root, next); 1196d97e63b6SChris Mason next = read_tree_block(root, blocknr); 1197d97e63b6SChris Mason break; 1198d97e63b6SChris Mason } 1199d97e63b6SChris Mason path->slots[level] = slot; 1200d97e63b6SChris Mason while(1) { 1201d97e63b6SChris Mason level--; 1202d97e63b6SChris Mason c = path->nodes[level]; 1203d97e63b6SChris Mason tree_block_release(root, c); 1204d97e63b6SChris Mason path->nodes[level] = next; 1205d97e63b6SChris Mason path->slots[level] = 0; 1206d97e63b6SChris Mason if (!level) 1207d97e63b6SChris Mason break; 1208d97e63b6SChris Mason next = read_tree_block(root, next->node.blockptrs[0]); 1209d97e63b6SChris Mason } 1210d97e63b6SChris Mason return 0; 1211d97e63b6SChris Mason } 1212d97e63b6SChris Mason 1213