11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README 31da177e4SLinus Torvalds */ 41da177e4SLinus Torvalds 51da177e4SLinus Torvalds /** 61da177e4SLinus Torvalds ** old_item_num 71da177e4SLinus Torvalds ** old_entry_num 81da177e4SLinus Torvalds ** set_entry_sizes 91da177e4SLinus Torvalds ** create_virtual_node 101da177e4SLinus Torvalds ** check_left 111da177e4SLinus Torvalds ** check_right 121da177e4SLinus Torvalds ** directory_part_size 131da177e4SLinus Torvalds ** get_num_ver 141da177e4SLinus Torvalds ** set_parameters 151da177e4SLinus Torvalds ** is_leaf_removable 161da177e4SLinus Torvalds ** are_leaves_removable 171da177e4SLinus Torvalds ** get_empty_nodes 181da177e4SLinus Torvalds ** get_lfree 191da177e4SLinus Torvalds ** get_rfree 201da177e4SLinus Torvalds ** is_left_neighbor_in_cache 211da177e4SLinus Torvalds ** decrement_key 221da177e4SLinus Torvalds ** get_far_parent 231da177e4SLinus Torvalds ** get_parents 241da177e4SLinus Torvalds ** can_node_be_removed 251da177e4SLinus Torvalds ** ip_check_balance 261da177e4SLinus Torvalds ** dc_check_balance_internal 271da177e4SLinus Torvalds ** dc_check_balance_leaf 281da177e4SLinus Torvalds ** dc_check_balance 291da177e4SLinus Torvalds ** check_balance 301da177e4SLinus Torvalds ** get_direct_parent 311da177e4SLinus Torvalds ** get_neighbors 321da177e4SLinus Torvalds ** fix_nodes 331da177e4SLinus Torvalds ** 341da177e4SLinus Torvalds ** 351da177e4SLinus Torvalds **/ 361da177e4SLinus Torvalds 371da177e4SLinus Torvalds #include <linux/time.h> 381da177e4SLinus Torvalds #include <linux/string.h> 391da177e4SLinus Torvalds #include <linux/reiserfs_fs.h> 401da177e4SLinus Torvalds #include <linux/buffer_head.h> 411da177e4SLinus Torvalds 421da177e4SLinus Torvalds /* To make any changes in the tree we find a node, that contains item 431da177e4SLinus Torvalds to be changed/deleted or position in the node we insert a new item 441da177e4SLinus Torvalds to. We call this node S. To do balancing we need to decide what we 451da177e4SLinus Torvalds will shift to left/right neighbor, or to a new node, where new item 461da177e4SLinus Torvalds will be etc. To make this analysis simpler we build virtual 471da177e4SLinus Torvalds node. Virtual node is an array of items, that will replace items of 481da177e4SLinus Torvalds node S. (For instance if we are going to delete an item, virtual 491da177e4SLinus Torvalds node does not contain it). Virtual node keeps information about 501da177e4SLinus Torvalds item sizes and types, mergeability of first and last items, sizes 511da177e4SLinus Torvalds of all entries in directory item. We use this array of items when 521da177e4SLinus Torvalds calculating what we can shift to neighbors and how many nodes we 531da177e4SLinus Torvalds have to have if we do not any shiftings, if we shift to left/right 541da177e4SLinus Torvalds neighbor or to both. */ 551da177e4SLinus Torvalds 561da177e4SLinus Torvalds /* taking item number in virtual node, returns number of item, that it has in source buffer */ 571da177e4SLinus Torvalds static inline int old_item_num(int new_num, int affected_item_num, int mode) 581da177e4SLinus Torvalds { 591da177e4SLinus Torvalds if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num) 601da177e4SLinus Torvalds return new_num; 611da177e4SLinus Torvalds 621da177e4SLinus Torvalds if (mode == M_INSERT) { 631da177e4SLinus Torvalds 641da177e4SLinus Torvalds RFALSE(new_num == 0, 651da177e4SLinus Torvalds "vs-8005: for INSERT mode and item number of inserted item"); 661da177e4SLinus Torvalds 671da177e4SLinus Torvalds return new_num - 1; 681da177e4SLinus Torvalds } 691da177e4SLinus Torvalds 701da177e4SLinus Torvalds RFALSE(mode != M_DELETE, 71bd4c625cSLinus Torvalds "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'", 72bd4c625cSLinus Torvalds mode); 731da177e4SLinus Torvalds /* delete mode */ 741da177e4SLinus Torvalds return new_num + 1; 751da177e4SLinus Torvalds } 761da177e4SLinus Torvalds 771da177e4SLinus Torvalds static void create_virtual_node(struct tree_balance *tb, int h) 781da177e4SLinus Torvalds { 791da177e4SLinus Torvalds struct item_head *ih; 801da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn; 811da177e4SLinus Torvalds int new_num; 821da177e4SLinus Torvalds struct buffer_head *Sh; /* this comes from tb->S[h] */ 831da177e4SLinus Torvalds 841da177e4SLinus Torvalds Sh = PATH_H_PBUFFER(tb->tb_path, h); 851da177e4SLinus Torvalds 861da177e4SLinus Torvalds /* size of changed node */ 87bd4c625cSLinus Torvalds vn->vn_size = 88bd4c625cSLinus Torvalds MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h]; 891da177e4SLinus Torvalds 901da177e4SLinus Torvalds /* for internal nodes array if virtual items is not created */ 911da177e4SLinus Torvalds if (h) { 921da177e4SLinus Torvalds vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE); 931da177e4SLinus Torvalds return; 941da177e4SLinus Torvalds } 951da177e4SLinus Torvalds 961da177e4SLinus Torvalds /* number of items in virtual node */ 97bd4c625cSLinus Torvalds vn->vn_nr_item = 98bd4c625cSLinus Torvalds B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) - 99bd4c625cSLinus Torvalds ((vn->vn_mode == M_DELETE) ? 1 : 0); 1001da177e4SLinus Torvalds 1011da177e4SLinus Torvalds /* first virtual item */ 1021da177e4SLinus Torvalds vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1); 1031da177e4SLinus Torvalds memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item)); 1041da177e4SLinus Torvalds vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item); 1051da177e4SLinus Torvalds 1061da177e4SLinus Torvalds /* first item in the node */ 1071da177e4SLinus Torvalds ih = B_N_PITEM_HEAD(Sh, 0); 1081da177e4SLinus Torvalds 1091da177e4SLinus Torvalds /* define the mergeability for 0-th item (if it is not being deleted) */ 110bd4c625cSLinus Torvalds if (op_is_left_mergeable(&(ih->ih_key), Sh->b_size) 111bd4c625cSLinus Torvalds && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num)) 1121da177e4SLinus Torvalds vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE; 1131da177e4SLinus Torvalds 1141da177e4SLinus Torvalds /* go through all items those remain in the virtual node (except for the new (inserted) one) */ 1151da177e4SLinus Torvalds for (new_num = 0; new_num < vn->vn_nr_item; new_num++) { 1161da177e4SLinus Torvalds int j; 1171da177e4SLinus Torvalds struct virtual_item *vi = vn->vn_vi + new_num; 118bd4c625cSLinus Torvalds int is_affected = 119bd4c625cSLinus Torvalds ((new_num != vn->vn_affected_item_num) ? 0 : 1); 1201da177e4SLinus Torvalds 1211da177e4SLinus Torvalds if (is_affected && vn->vn_mode == M_INSERT) 1221da177e4SLinus Torvalds continue; 1231da177e4SLinus Torvalds 1241da177e4SLinus Torvalds /* get item number in source node */ 125bd4c625cSLinus Torvalds j = old_item_num(new_num, vn->vn_affected_item_num, 126bd4c625cSLinus Torvalds vn->vn_mode); 1271da177e4SLinus Torvalds 1281da177e4SLinus Torvalds vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE; 1291da177e4SLinus Torvalds vi->vi_ih = ih + j; 1301da177e4SLinus Torvalds vi->vi_item = B_I_PITEM(Sh, ih + j); 1311da177e4SLinus Torvalds vi->vi_uarea = vn->vn_free_ptr; 1321da177e4SLinus Torvalds 1331da177e4SLinus Torvalds // FIXME: there is no check, that item operation did not 1341da177e4SLinus Torvalds // consume too much memory 135bd4c625cSLinus Torvalds vn->vn_free_ptr += 136bd4c625cSLinus Torvalds op_create_vi(vn, vi, is_affected, tb->insert_size[0]); 1371da177e4SLinus Torvalds if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr) 138bd4c625cSLinus Torvalds reiserfs_panic(tb->tb_sb, 139bd4c625cSLinus Torvalds "vs-8030: create_virtual_node: " 1401da177e4SLinus Torvalds "virtual node space consumed"); 1411da177e4SLinus Torvalds 1421da177e4SLinus Torvalds if (!is_affected) 1431da177e4SLinus Torvalds /* this is not being changed */ 1441da177e4SLinus Torvalds continue; 1451da177e4SLinus Torvalds 1461da177e4SLinus Torvalds if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) { 1471da177e4SLinus Torvalds vn->vn_vi[new_num].vi_item_len += tb->insert_size[0]; 1481da177e4SLinus Torvalds vi->vi_new_data = vn->vn_data; // pointer to data which is going to be pasted 1491da177e4SLinus Torvalds } 1501da177e4SLinus Torvalds } 1511da177e4SLinus Torvalds 1521da177e4SLinus Torvalds /* virtual inserted item is not defined yet */ 1531da177e4SLinus Torvalds if (vn->vn_mode == M_INSERT) { 1541da177e4SLinus Torvalds struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num; 1551da177e4SLinus Torvalds 1569dce07f1SAl Viro RFALSE(vn->vn_ins_ih == NULL, 1571da177e4SLinus Torvalds "vs-8040: item header of inserted item is not specified"); 1581da177e4SLinus Torvalds vi->vi_item_len = tb->insert_size[0]; 1591da177e4SLinus Torvalds vi->vi_ih = vn->vn_ins_ih; 1601da177e4SLinus Torvalds vi->vi_item = vn->vn_data; 1611da177e4SLinus Torvalds vi->vi_uarea = vn->vn_free_ptr; 1621da177e4SLinus Torvalds 163bd4c625cSLinus Torvalds op_create_vi(vn, vi, 0 /*not pasted or cut */ , 164bd4c625cSLinus Torvalds tb->insert_size[0]); 1651da177e4SLinus Torvalds } 1661da177e4SLinus Torvalds 1671da177e4SLinus Torvalds /* set right merge flag we take right delimiting key and check whether it is a mergeable item */ 1681da177e4SLinus Torvalds if (tb->CFR[0]) { 1691da177e4SLinus Torvalds struct reiserfs_key *key; 1701da177e4SLinus Torvalds 1711da177e4SLinus Torvalds key = B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]); 172bd4c625cSLinus Torvalds if (op_is_left_mergeable(key, Sh->b_size) 173bd4c625cSLinus Torvalds && (vn->vn_mode != M_DELETE 174bd4c625cSLinus Torvalds || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) 175bd4c625cSLinus Torvalds vn->vn_vi[vn->vn_nr_item - 1].vi_type |= 176bd4c625cSLinus Torvalds VI_TYPE_RIGHT_MERGEABLE; 1771da177e4SLinus Torvalds 1781da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 1791da177e4SLinus Torvalds if (op_is_left_mergeable(key, Sh->b_size) && 180bd4c625cSLinus Torvalds !(vn->vn_mode != M_DELETE 181bd4c625cSLinus Torvalds || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) { 1821da177e4SLinus Torvalds /* we delete last item and it could be merged with right neighbor's first item */ 183bd4c625cSLinus Torvalds if (! 184bd4c625cSLinus Torvalds (B_NR_ITEMS(Sh) == 1 185bd4c625cSLinus Torvalds && is_direntry_le_ih(B_N_PITEM_HEAD(Sh, 0)) 186bd4c625cSLinus Torvalds && I_ENTRY_COUNT(B_N_PITEM_HEAD(Sh, 0)) == 1)) { 1871da177e4SLinus Torvalds /* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */ 1881da177e4SLinus Torvalds print_block(Sh, 0, -1, -1); 189bd4c625cSLinus Torvalds reiserfs_panic(tb->tb_sb, 190bd4c625cSLinus Torvalds "vs-8045: create_virtual_node: rdkey %k, affected item==%d (mode==%c) Must be %c", 191bd4c625cSLinus Torvalds key, vn->vn_affected_item_num, 192bd4c625cSLinus Torvalds vn->vn_mode, M_DELETE); 193cd02b966SVladimir V. Saveliev } 1941da177e4SLinus Torvalds } 1951da177e4SLinus Torvalds #endif 1961da177e4SLinus Torvalds 1971da177e4SLinus Torvalds } 1981da177e4SLinus Torvalds } 1991da177e4SLinus Torvalds 2001da177e4SLinus Torvalds /* using virtual node check, how many items can be shifted to left 2011da177e4SLinus Torvalds neighbor */ 2021da177e4SLinus Torvalds static void check_left(struct tree_balance *tb, int h, int cur_free) 2031da177e4SLinus Torvalds { 2041da177e4SLinus Torvalds int i; 2051da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn; 2061da177e4SLinus Torvalds struct virtual_item *vi; 2071da177e4SLinus Torvalds int d_size, ih_size; 2081da177e4SLinus Torvalds 2091da177e4SLinus Torvalds RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free); 2101da177e4SLinus Torvalds 2111da177e4SLinus Torvalds /* internal level */ 2121da177e4SLinus Torvalds if (h > 0) { 2131da177e4SLinus Torvalds tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE); 2141da177e4SLinus Torvalds return; 2151da177e4SLinus Torvalds } 2161da177e4SLinus Torvalds 2171da177e4SLinus Torvalds /* leaf level */ 2181da177e4SLinus Torvalds 2191da177e4SLinus Torvalds if (!cur_free || !vn->vn_nr_item) { 2201da177e4SLinus Torvalds /* no free space or nothing to move */ 2211da177e4SLinus Torvalds tb->lnum[h] = 0; 2221da177e4SLinus Torvalds tb->lbytes = -1; 2231da177e4SLinus Torvalds return; 2241da177e4SLinus Torvalds } 2251da177e4SLinus Torvalds 2261da177e4SLinus Torvalds RFALSE(!PATH_H_PPARENT(tb->tb_path, 0), 2271da177e4SLinus Torvalds "vs-8055: parent does not exist or invalid"); 2281da177e4SLinus Torvalds 2291da177e4SLinus Torvalds vi = vn->vn_vi; 230bd4c625cSLinus Torvalds if ((unsigned int)cur_free >= 231bd4c625cSLinus Torvalds (vn->vn_size - 232bd4c625cSLinus Torvalds ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) { 2331da177e4SLinus Torvalds /* all contents of S[0] fits into L[0] */ 2341da177e4SLinus Torvalds 2351da177e4SLinus Torvalds RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE, 2361da177e4SLinus Torvalds "vs-8055: invalid mode or balance condition failed"); 2371da177e4SLinus Torvalds 2381da177e4SLinus Torvalds tb->lnum[0] = vn->vn_nr_item; 2391da177e4SLinus Torvalds tb->lbytes = -1; 2401da177e4SLinus Torvalds return; 2411da177e4SLinus Torvalds } 2421da177e4SLinus Torvalds 2431da177e4SLinus Torvalds d_size = 0, ih_size = IH_SIZE; 2441da177e4SLinus Torvalds 2451da177e4SLinus Torvalds /* first item may be merge with last item in left neighbor */ 2461da177e4SLinus Torvalds if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE) 2471da177e4SLinus Torvalds d_size = -((int)IH_SIZE), ih_size = 0; 2481da177e4SLinus Torvalds 2491da177e4SLinus Torvalds tb->lnum[0] = 0; 250bd4c625cSLinus Torvalds for (i = 0; i < vn->vn_nr_item; 251bd4c625cSLinus Torvalds i++, ih_size = IH_SIZE, d_size = 0, vi++) { 2521da177e4SLinus Torvalds d_size += vi->vi_item_len; 2531da177e4SLinus Torvalds if (cur_free >= d_size) { 2541da177e4SLinus Torvalds /* the item can be shifted entirely */ 2551da177e4SLinus Torvalds cur_free -= d_size; 2561da177e4SLinus Torvalds tb->lnum[0]++; 2571da177e4SLinus Torvalds continue; 2581da177e4SLinus Torvalds } 2591da177e4SLinus Torvalds 2601da177e4SLinus Torvalds /* the item cannot be shifted entirely, try to split it */ 2611da177e4SLinus Torvalds /* check whether L[0] can hold ih and at least one byte of the item body */ 2621da177e4SLinus Torvalds if (cur_free <= ih_size) { 2631da177e4SLinus Torvalds /* cannot shift even a part of the current item */ 2641da177e4SLinus Torvalds tb->lbytes = -1; 2651da177e4SLinus Torvalds return; 2661da177e4SLinus Torvalds } 2671da177e4SLinus Torvalds cur_free -= ih_size; 2681da177e4SLinus Torvalds 2691da177e4SLinus Torvalds tb->lbytes = op_check_left(vi, cur_free, 0, 0); 2701da177e4SLinus Torvalds if (tb->lbytes != -1) 2711da177e4SLinus Torvalds /* count partially shifted item */ 2721da177e4SLinus Torvalds tb->lnum[0]++; 2731da177e4SLinus Torvalds 2741da177e4SLinus Torvalds break; 2751da177e4SLinus Torvalds } 2761da177e4SLinus Torvalds 2771da177e4SLinus Torvalds return; 2781da177e4SLinus Torvalds } 2791da177e4SLinus Torvalds 2801da177e4SLinus Torvalds /* using virtual node check, how many items can be shifted to right 2811da177e4SLinus Torvalds neighbor */ 2821da177e4SLinus Torvalds static void check_right(struct tree_balance *tb, int h, int cur_free) 2831da177e4SLinus Torvalds { 2841da177e4SLinus Torvalds int i; 2851da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn; 2861da177e4SLinus Torvalds struct virtual_item *vi; 2871da177e4SLinus Torvalds int d_size, ih_size; 2881da177e4SLinus Torvalds 2891da177e4SLinus Torvalds RFALSE(cur_free < 0, "vs-8070: cur_free < 0"); 2901da177e4SLinus Torvalds 2911da177e4SLinus Torvalds /* internal level */ 2921da177e4SLinus Torvalds if (h > 0) { 2931da177e4SLinus Torvalds tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE); 2941da177e4SLinus Torvalds return; 2951da177e4SLinus Torvalds } 2961da177e4SLinus Torvalds 2971da177e4SLinus Torvalds /* leaf level */ 2981da177e4SLinus Torvalds 2991da177e4SLinus Torvalds if (!cur_free || !vn->vn_nr_item) { 3001da177e4SLinus Torvalds /* no free space */ 3011da177e4SLinus Torvalds tb->rnum[h] = 0; 3021da177e4SLinus Torvalds tb->rbytes = -1; 3031da177e4SLinus Torvalds return; 3041da177e4SLinus Torvalds } 3051da177e4SLinus Torvalds 3061da177e4SLinus Torvalds RFALSE(!PATH_H_PPARENT(tb->tb_path, 0), 3071da177e4SLinus Torvalds "vs-8075: parent does not exist or invalid"); 3081da177e4SLinus Torvalds 3091da177e4SLinus Torvalds vi = vn->vn_vi + vn->vn_nr_item - 1; 310bd4c625cSLinus Torvalds if ((unsigned int)cur_free >= 311bd4c625cSLinus Torvalds (vn->vn_size - 312bd4c625cSLinus Torvalds ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) { 3131da177e4SLinus Torvalds /* all contents of S[0] fits into R[0] */ 3141da177e4SLinus Torvalds 3151da177e4SLinus Torvalds RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE, 3161da177e4SLinus Torvalds "vs-8080: invalid mode or balance condition failed"); 3171da177e4SLinus Torvalds 3181da177e4SLinus Torvalds tb->rnum[h] = vn->vn_nr_item; 3191da177e4SLinus Torvalds tb->rbytes = -1; 3201da177e4SLinus Torvalds return; 3211da177e4SLinus Torvalds } 3221da177e4SLinus Torvalds 3231da177e4SLinus Torvalds d_size = 0, ih_size = IH_SIZE; 3241da177e4SLinus Torvalds 3251da177e4SLinus Torvalds /* last item may be merge with first item in right neighbor */ 3261da177e4SLinus Torvalds if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) 3271da177e4SLinus Torvalds d_size = -(int)IH_SIZE, ih_size = 0; 3281da177e4SLinus Torvalds 3291da177e4SLinus Torvalds tb->rnum[0] = 0; 330bd4c625cSLinus Torvalds for (i = vn->vn_nr_item - 1; i >= 0; 331bd4c625cSLinus Torvalds i--, d_size = 0, ih_size = IH_SIZE, vi--) { 3321da177e4SLinus Torvalds d_size += vi->vi_item_len; 3331da177e4SLinus Torvalds if (cur_free >= d_size) { 3341da177e4SLinus Torvalds /* the item can be shifted entirely */ 3351da177e4SLinus Torvalds cur_free -= d_size; 3361da177e4SLinus Torvalds tb->rnum[0]++; 3371da177e4SLinus Torvalds continue; 3381da177e4SLinus Torvalds } 3391da177e4SLinus Torvalds 3401da177e4SLinus Torvalds /* check whether R[0] can hold ih and at least one byte of the item body */ 3411da177e4SLinus Torvalds if (cur_free <= ih_size) { /* cannot shift even a part of the current item */ 3421da177e4SLinus Torvalds tb->rbytes = -1; 3431da177e4SLinus Torvalds return; 3441da177e4SLinus Torvalds } 3451da177e4SLinus Torvalds 3461da177e4SLinus Torvalds /* R[0] can hold the header of the item and at least one byte of its body */ 3471da177e4SLinus Torvalds cur_free -= ih_size; /* cur_free is still > 0 */ 3481da177e4SLinus Torvalds 3491da177e4SLinus Torvalds tb->rbytes = op_check_right(vi, cur_free); 3501da177e4SLinus Torvalds if (tb->rbytes != -1) 3511da177e4SLinus Torvalds /* count partially shifted item */ 3521da177e4SLinus Torvalds tb->rnum[0]++; 3531da177e4SLinus Torvalds 3541da177e4SLinus Torvalds break; 3551da177e4SLinus Torvalds } 3561da177e4SLinus Torvalds 3571da177e4SLinus Torvalds return; 3581da177e4SLinus Torvalds } 3591da177e4SLinus Torvalds 3601da177e4SLinus Torvalds /* 3611da177e4SLinus Torvalds * from - number of items, which are shifted to left neighbor entirely 3621da177e4SLinus Torvalds * to - number of item, which are shifted to right neighbor entirely 3631da177e4SLinus Torvalds * from_bytes - number of bytes of boundary item (or directory entries) which are shifted to left neighbor 3641da177e4SLinus Torvalds * to_bytes - number of bytes of boundary item (or directory entries) which are shifted to right neighbor */ 3651da177e4SLinus Torvalds static int get_num_ver(int mode, struct tree_balance *tb, int h, 3661da177e4SLinus Torvalds int from, int from_bytes, 367bd4c625cSLinus Torvalds int to, int to_bytes, short *snum012, int flow) 3681da177e4SLinus Torvalds { 3691da177e4SLinus Torvalds int i; 3701da177e4SLinus Torvalds int cur_free; 3711da177e4SLinus Torvalds // int bytes; 3721da177e4SLinus Torvalds int units; 3731da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn; 3741da177e4SLinus Torvalds // struct virtual_item * vi; 3751da177e4SLinus Torvalds 3761da177e4SLinus Torvalds int total_node_size, max_node_size, current_item_size; 3771da177e4SLinus Torvalds int needed_nodes; 3781da177e4SLinus Torvalds int start_item, /* position of item we start filling node from */ 3791da177e4SLinus Torvalds end_item, /* position of item we finish filling node by */ 3801da177e4SLinus Torvalds start_bytes, /* number of first bytes (entries for directory) of start_item-th item 3811da177e4SLinus Torvalds we do not include into node that is being filled */ 3821da177e4SLinus Torvalds end_bytes; /* number of last bytes (entries for directory) of end_item-th item 3831da177e4SLinus Torvalds we do node include into node that is being filled */ 3841da177e4SLinus Torvalds int split_item_positions[2]; /* these are positions in virtual item of 3851da177e4SLinus Torvalds items, that are split between S[0] and 3861da177e4SLinus Torvalds S1new and S1new and S2new */ 3871da177e4SLinus Torvalds 3881da177e4SLinus Torvalds split_item_positions[0] = -1; 3891da177e4SLinus Torvalds split_item_positions[1] = -1; 3901da177e4SLinus Torvalds 3911da177e4SLinus Torvalds /* We only create additional nodes if we are in insert or paste mode 3921da177e4SLinus Torvalds or we are in replace mode at the internal level. If h is 0 and 3931da177e4SLinus Torvalds the mode is M_REPLACE then in fix_nodes we change the mode to 3941da177e4SLinus Torvalds paste or insert before we get here in the code. */ 3951da177e4SLinus Torvalds RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE), 3961da177e4SLinus Torvalds "vs-8100: insert_size < 0 in overflow"); 3971da177e4SLinus Torvalds 3981da177e4SLinus Torvalds max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h)); 3991da177e4SLinus Torvalds 4001da177e4SLinus Torvalds /* snum012 [0-2] - number of items, that lay 4011da177e4SLinus Torvalds to S[0], first new node and second new node */ 4021da177e4SLinus Torvalds snum012[3] = -1; /* s1bytes */ 4031da177e4SLinus Torvalds snum012[4] = -1; /* s2bytes */ 4041da177e4SLinus Torvalds 4051da177e4SLinus Torvalds /* internal level */ 4061da177e4SLinus Torvalds if (h > 0) { 4071da177e4SLinus Torvalds i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE); 4081da177e4SLinus Torvalds if (i == max_node_size) 4091da177e4SLinus Torvalds return 1; 4101da177e4SLinus Torvalds return (i / max_node_size + 1); 4111da177e4SLinus Torvalds } 4121da177e4SLinus Torvalds 4131da177e4SLinus Torvalds /* leaf level */ 4141da177e4SLinus Torvalds needed_nodes = 1; 4151da177e4SLinus Torvalds total_node_size = 0; 4161da177e4SLinus Torvalds cur_free = max_node_size; 4171da177e4SLinus Torvalds 4181da177e4SLinus Torvalds // start from 'from'-th item 4191da177e4SLinus Torvalds start_item = from; 4201da177e4SLinus Torvalds // skip its first 'start_bytes' units 4211da177e4SLinus Torvalds start_bytes = ((from_bytes != -1) ? from_bytes : 0); 4221da177e4SLinus Torvalds 4231da177e4SLinus Torvalds // last included item is the 'end_item'-th one 4241da177e4SLinus Torvalds end_item = vn->vn_nr_item - to - 1; 4251da177e4SLinus Torvalds // do not count last 'end_bytes' units of 'end_item'-th item 4261da177e4SLinus Torvalds end_bytes = (to_bytes != -1) ? to_bytes : 0; 4271da177e4SLinus Torvalds 4281da177e4SLinus Torvalds /* go through all item beginning from the start_item-th item and ending by 4291da177e4SLinus Torvalds the end_item-th item. Do not count first 'start_bytes' units of 4301da177e4SLinus Torvalds 'start_item'-th item and last 'end_bytes' of 'end_item'-th item */ 4311da177e4SLinus Torvalds 4321da177e4SLinus Torvalds for (i = start_item; i <= end_item; i++) { 4331da177e4SLinus Torvalds struct virtual_item *vi = vn->vn_vi + i; 4341da177e4SLinus Torvalds int skip_from_end = ((i == end_item) ? end_bytes : 0); 4351da177e4SLinus Torvalds 4361da177e4SLinus Torvalds RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed"); 4371da177e4SLinus Torvalds 4381da177e4SLinus Torvalds /* get size of current item */ 4391da177e4SLinus Torvalds current_item_size = vi->vi_item_len; 4401da177e4SLinus Torvalds 4411da177e4SLinus Torvalds /* do not take in calculation head part (from_bytes) of from-th item */ 442bd4c625cSLinus Torvalds current_item_size -= 443bd4c625cSLinus Torvalds op_part_size(vi, 0 /*from start */ , start_bytes); 4441da177e4SLinus Torvalds 4451da177e4SLinus Torvalds /* do not take in calculation tail part of last item */ 446bd4c625cSLinus Torvalds current_item_size -= 447bd4c625cSLinus Torvalds op_part_size(vi, 1 /*from end */ , skip_from_end); 4481da177e4SLinus Torvalds 4491da177e4SLinus Torvalds /* if item fits into current node entierly */ 4501da177e4SLinus Torvalds if (total_node_size + current_item_size <= max_node_size) { 4511da177e4SLinus Torvalds snum012[needed_nodes - 1]++; 4521da177e4SLinus Torvalds total_node_size += current_item_size; 4531da177e4SLinus Torvalds start_bytes = 0; 4541da177e4SLinus Torvalds continue; 4551da177e4SLinus Torvalds } 4561da177e4SLinus Torvalds 4571da177e4SLinus Torvalds if (current_item_size > max_node_size) { 4581da177e4SLinus Torvalds /* virtual item length is longer, than max size of item in 4591da177e4SLinus Torvalds a node. It is impossible for direct item */ 4601da177e4SLinus Torvalds RFALSE(is_direct_le_ih(vi->vi_ih), 4611da177e4SLinus Torvalds "vs-8110: " 4621da177e4SLinus Torvalds "direct item length is %d. It can not be longer than %d", 4631da177e4SLinus Torvalds current_item_size, max_node_size); 4641da177e4SLinus Torvalds /* we will try to split it */ 4651da177e4SLinus Torvalds flow = 1; 4661da177e4SLinus Torvalds } 4671da177e4SLinus Torvalds 4681da177e4SLinus Torvalds if (!flow) { 4691da177e4SLinus Torvalds /* as we do not split items, take new node and continue */ 470bd4c625cSLinus Torvalds needed_nodes++; 471bd4c625cSLinus Torvalds i--; 472bd4c625cSLinus Torvalds total_node_size = 0; 4731da177e4SLinus Torvalds continue; 4741da177e4SLinus Torvalds } 4751da177e4SLinus Torvalds // calculate number of item units which fit into node being 4761da177e4SLinus Torvalds // filled 4771da177e4SLinus Torvalds { 4781da177e4SLinus Torvalds int free_space; 4791da177e4SLinus Torvalds 4801da177e4SLinus Torvalds free_space = max_node_size - total_node_size - IH_SIZE; 481bd4c625cSLinus Torvalds units = 482bd4c625cSLinus Torvalds op_check_left(vi, free_space, start_bytes, 483bd4c625cSLinus Torvalds skip_from_end); 4841da177e4SLinus Torvalds if (units == -1) { 4851da177e4SLinus Torvalds /* nothing fits into current node, take new node and continue */ 4861da177e4SLinus Torvalds needed_nodes++, i--, total_node_size = 0; 4871da177e4SLinus Torvalds continue; 4881da177e4SLinus Torvalds } 4891da177e4SLinus Torvalds } 4901da177e4SLinus Torvalds 4911da177e4SLinus Torvalds /* something fits into the current node */ 4921da177e4SLinus Torvalds //if (snum012[3] != -1 || needed_nodes != 1) 4931da177e4SLinus Torvalds // reiserfs_panic (tb->tb_sb, "vs-8115: get_num_ver: too many nodes required"); 4941da177e4SLinus Torvalds //snum012[needed_nodes - 1 + 3] = op_unit_num (vi) - start_bytes - units; 4951da177e4SLinus Torvalds start_bytes += units; 4961da177e4SLinus Torvalds snum012[needed_nodes - 1 + 3] = units; 4971da177e4SLinus Torvalds 4981da177e4SLinus Torvalds if (needed_nodes > 2) 499*45b03d5eSJeff Mahoney reiserfs_warning(tb->tb_sb, "vs-8111", 500*45b03d5eSJeff Mahoney "split_item_position is out of range"); 5011da177e4SLinus Torvalds snum012[needed_nodes - 1]++; 5021da177e4SLinus Torvalds split_item_positions[needed_nodes - 1] = i; 5031da177e4SLinus Torvalds needed_nodes++; 5041da177e4SLinus Torvalds /* continue from the same item with start_bytes != -1 */ 5051da177e4SLinus Torvalds start_item = i; 5061da177e4SLinus Torvalds i--; 5071da177e4SLinus Torvalds total_node_size = 0; 5081da177e4SLinus Torvalds } 5091da177e4SLinus Torvalds 5101da177e4SLinus Torvalds // sum012[4] (if it is not -1) contains number of units of which 5111da177e4SLinus Torvalds // are to be in S1new, snum012[3] - to be in S0. They are supposed 5121da177e4SLinus Torvalds // to be S1bytes and S2bytes correspondingly, so recalculate 5131da177e4SLinus Torvalds if (snum012[4] > 0) { 5141da177e4SLinus Torvalds int split_item_num; 5151da177e4SLinus Torvalds int bytes_to_r, bytes_to_l; 5161da177e4SLinus Torvalds int bytes_to_S1new; 5171da177e4SLinus Torvalds 5181da177e4SLinus Torvalds split_item_num = split_item_positions[1]; 519bd4c625cSLinus Torvalds bytes_to_l = 520bd4c625cSLinus Torvalds ((from == split_item_num 521bd4c625cSLinus Torvalds && from_bytes != -1) ? from_bytes : 0); 522bd4c625cSLinus Torvalds bytes_to_r = 523bd4c625cSLinus Torvalds ((end_item == split_item_num 524bd4c625cSLinus Torvalds && end_bytes != -1) ? end_bytes : 0); 525bd4c625cSLinus Torvalds bytes_to_S1new = 526bd4c625cSLinus Torvalds ((split_item_positions[0] == 527bd4c625cSLinus Torvalds split_item_positions[1]) ? snum012[3] : 0); 5281da177e4SLinus Torvalds 5291da177e4SLinus Torvalds // s2bytes 530bd4c625cSLinus Torvalds snum012[4] = 531bd4c625cSLinus Torvalds op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] - 532bd4c625cSLinus Torvalds bytes_to_r - bytes_to_l - bytes_to_S1new; 5331da177e4SLinus Torvalds 5341da177e4SLinus Torvalds if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY && 5351da177e4SLinus Torvalds vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT) 536*45b03d5eSJeff Mahoney reiserfs_warning(tb->tb_sb, "vs-8115", 537*45b03d5eSJeff Mahoney "not directory or indirect item"); 5381da177e4SLinus Torvalds } 5391da177e4SLinus Torvalds 5401da177e4SLinus Torvalds /* now we know S2bytes, calculate S1bytes */ 5411da177e4SLinus Torvalds if (snum012[3] > 0) { 5421da177e4SLinus Torvalds int split_item_num; 5431da177e4SLinus Torvalds int bytes_to_r, bytes_to_l; 5441da177e4SLinus Torvalds int bytes_to_S2new; 5451da177e4SLinus Torvalds 5461da177e4SLinus Torvalds split_item_num = split_item_positions[0]; 547bd4c625cSLinus Torvalds bytes_to_l = 548bd4c625cSLinus Torvalds ((from == split_item_num 549bd4c625cSLinus Torvalds && from_bytes != -1) ? from_bytes : 0); 550bd4c625cSLinus Torvalds bytes_to_r = 551bd4c625cSLinus Torvalds ((end_item == split_item_num 552bd4c625cSLinus Torvalds && end_bytes != -1) ? end_bytes : 0); 553bd4c625cSLinus Torvalds bytes_to_S2new = 554bd4c625cSLinus Torvalds ((split_item_positions[0] == split_item_positions[1] 555bd4c625cSLinus Torvalds && snum012[4] != -1) ? snum012[4] : 0); 5561da177e4SLinus Torvalds 5571da177e4SLinus Torvalds // s1bytes 558bd4c625cSLinus Torvalds snum012[3] = 559bd4c625cSLinus Torvalds op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] - 560bd4c625cSLinus Torvalds bytes_to_r - bytes_to_l - bytes_to_S2new; 5611da177e4SLinus Torvalds } 5621da177e4SLinus Torvalds 5631da177e4SLinus Torvalds return needed_nodes; 5641da177e4SLinus Torvalds } 5651da177e4SLinus Torvalds 5661da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 5671da177e4SLinus Torvalds extern struct tree_balance *cur_tb; 5681da177e4SLinus Torvalds #endif 5691da177e4SLinus Torvalds 5701da177e4SLinus Torvalds /* Set parameters for balancing. 5711da177e4SLinus Torvalds * Performs write of results of analysis of balancing into structure tb, 5721da177e4SLinus Torvalds * where it will later be used by the functions that actually do the balancing. 5731da177e4SLinus Torvalds * Parameters: 5741da177e4SLinus Torvalds * tb tree_balance structure; 5751da177e4SLinus Torvalds * h current level of the node; 5761da177e4SLinus Torvalds * lnum number of items from S[h] that must be shifted to L[h]; 5771da177e4SLinus Torvalds * rnum number of items from S[h] that must be shifted to R[h]; 5781da177e4SLinus Torvalds * blk_num number of blocks that S[h] will be splitted into; 5791da177e4SLinus Torvalds * s012 number of items that fall into splitted nodes. 5801da177e4SLinus Torvalds * lbytes number of bytes which flow to the left neighbor from the item that is not 5811da177e4SLinus Torvalds * not shifted entirely 5821da177e4SLinus Torvalds * rbytes number of bytes which flow to the right neighbor from the item that is not 5831da177e4SLinus Torvalds * not shifted entirely 5841da177e4SLinus Torvalds * s1bytes number of bytes which flow to the first new node when S[0] splits (this number is contained in s012 array) 5851da177e4SLinus Torvalds */ 5861da177e4SLinus Torvalds 5871da177e4SLinus Torvalds static void set_parameters(struct tree_balance *tb, int h, int lnum, 5881da177e4SLinus Torvalds int rnum, int blk_num, short *s012, int lb, int rb) 5891da177e4SLinus Torvalds { 5901da177e4SLinus Torvalds 5911da177e4SLinus Torvalds tb->lnum[h] = lnum; 5921da177e4SLinus Torvalds tb->rnum[h] = rnum; 5931da177e4SLinus Torvalds tb->blknum[h] = blk_num; 5941da177e4SLinus Torvalds 595bd4c625cSLinus Torvalds if (h == 0) { /* only for leaf level */ 596bd4c625cSLinus Torvalds if (s012 != NULL) { 5971da177e4SLinus Torvalds tb->s0num = *s012++, 598bd4c625cSLinus Torvalds tb->s1num = *s012++, tb->s2num = *s012++; 5991da177e4SLinus Torvalds tb->s1bytes = *s012++; 6001da177e4SLinus Torvalds tb->s2bytes = *s012; 6011da177e4SLinus Torvalds } 6021da177e4SLinus Torvalds tb->lbytes = lb; 6031da177e4SLinus Torvalds tb->rbytes = rb; 6041da177e4SLinus Torvalds } 6051da177e4SLinus Torvalds PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum); 6061da177e4SLinus Torvalds PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum); 6071da177e4SLinus Torvalds 6081da177e4SLinus Torvalds PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb); 6091da177e4SLinus Torvalds PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb); 6101da177e4SLinus Torvalds } 6111da177e4SLinus Torvalds 6121da177e4SLinus Torvalds /* check, does node disappear if we shift tb->lnum[0] items to left 6131da177e4SLinus Torvalds neighbor and tb->rnum[0] to the right one. */ 6141da177e4SLinus Torvalds static int is_leaf_removable(struct tree_balance *tb) 6151da177e4SLinus Torvalds { 6161da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn; 6171da177e4SLinus Torvalds int to_left, to_right; 6181da177e4SLinus Torvalds int size; 6191da177e4SLinus Torvalds int remain_items; 6201da177e4SLinus Torvalds 6211da177e4SLinus Torvalds /* number of items, that will be shifted to left (right) neighbor 6221da177e4SLinus Torvalds entirely */ 6231da177e4SLinus Torvalds to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0); 6241da177e4SLinus Torvalds to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0); 6251da177e4SLinus Torvalds remain_items = vn->vn_nr_item; 6261da177e4SLinus Torvalds 6271da177e4SLinus Torvalds /* how many items remain in S[0] after shiftings to neighbors */ 6281da177e4SLinus Torvalds remain_items -= (to_left + to_right); 6291da177e4SLinus Torvalds 6301da177e4SLinus Torvalds if (remain_items < 1) { 6311da177e4SLinus Torvalds /* all content of node can be shifted to neighbors */ 632bd4c625cSLinus Torvalds set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0, 633bd4c625cSLinus Torvalds NULL, -1, -1); 6341da177e4SLinus Torvalds return 1; 6351da177e4SLinus Torvalds } 6361da177e4SLinus Torvalds 6371da177e4SLinus Torvalds if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1) 6381da177e4SLinus Torvalds /* S[0] is not removable */ 6391da177e4SLinus Torvalds return 0; 6401da177e4SLinus Torvalds 6411da177e4SLinus Torvalds /* check, whether we can divide 1 remaining item between neighbors */ 6421da177e4SLinus Torvalds 6431da177e4SLinus Torvalds /* get size of remaining item (in item units) */ 6441da177e4SLinus Torvalds size = op_unit_num(&(vn->vn_vi[to_left])); 6451da177e4SLinus Torvalds 6461da177e4SLinus Torvalds if (tb->lbytes + tb->rbytes >= size) { 647bd4c625cSLinus Torvalds set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL, 648bd4c625cSLinus Torvalds tb->lbytes, -1); 6491da177e4SLinus Torvalds return 1; 6501da177e4SLinus Torvalds } 6511da177e4SLinus Torvalds 6521da177e4SLinus Torvalds return 0; 6531da177e4SLinus Torvalds } 6541da177e4SLinus Torvalds 6551da177e4SLinus Torvalds /* check whether L, S, R can be joined in one node */ 6561da177e4SLinus Torvalds static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree) 6571da177e4SLinus Torvalds { 6581da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn; 6591da177e4SLinus Torvalds int ih_size; 6601da177e4SLinus Torvalds struct buffer_head *S0; 6611da177e4SLinus Torvalds 6621da177e4SLinus Torvalds S0 = PATH_H_PBUFFER(tb->tb_path, 0); 6631da177e4SLinus Torvalds 6641da177e4SLinus Torvalds ih_size = 0; 6651da177e4SLinus Torvalds if (vn->vn_nr_item) { 6661da177e4SLinus Torvalds if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE) 6671da177e4SLinus Torvalds ih_size += IH_SIZE; 6681da177e4SLinus Torvalds 669bd4c625cSLinus Torvalds if (vn->vn_vi[vn->vn_nr_item - 1]. 670bd4c625cSLinus Torvalds vi_type & VI_TYPE_RIGHT_MERGEABLE) 6711da177e4SLinus Torvalds ih_size += IH_SIZE; 6721da177e4SLinus Torvalds } else { 6731da177e4SLinus Torvalds /* there was only one item and it will be deleted */ 6741da177e4SLinus Torvalds struct item_head *ih; 6751da177e4SLinus Torvalds 6761da177e4SLinus Torvalds RFALSE(B_NR_ITEMS(S0) != 1, 677bd4c625cSLinus Torvalds "vs-8125: item number must be 1: it is %d", 678bd4c625cSLinus Torvalds B_NR_ITEMS(S0)); 6791da177e4SLinus Torvalds 6801da177e4SLinus Torvalds ih = B_N_PITEM_HEAD(S0, 0); 681bd4c625cSLinus Torvalds if (tb->CFR[0] 682bd4c625cSLinus Torvalds && !comp_short_le_keys(&(ih->ih_key), 683bd4c625cSLinus Torvalds B_N_PDELIM_KEY(tb->CFR[0], 684bd4c625cSLinus Torvalds tb->rkey[0]))) 6851da177e4SLinus Torvalds if (is_direntry_le_ih(ih)) { 6861da177e4SLinus Torvalds /* Directory must be in correct state here: that is 6871da177e4SLinus Torvalds somewhere at the left side should exist first directory 6881da177e4SLinus Torvalds item. But the item being deleted can not be that first 6891da177e4SLinus Torvalds one because its right neighbor is item of the same 6901da177e4SLinus Torvalds directory. (But first item always gets deleted in last 6911da177e4SLinus Torvalds turn). So, neighbors of deleted item can be merged, so 6921da177e4SLinus Torvalds we can save ih_size */ 6931da177e4SLinus Torvalds ih_size = IH_SIZE; 6941da177e4SLinus Torvalds 6951da177e4SLinus Torvalds /* we might check that left neighbor exists and is of the 6961da177e4SLinus Torvalds same directory */ 6971da177e4SLinus Torvalds RFALSE(le_ih_k_offset(ih) == DOT_OFFSET, 6981da177e4SLinus Torvalds "vs-8130: first directory item can not be removed until directory is not empty"); 6991da177e4SLinus Torvalds } 7001da177e4SLinus Torvalds 7011da177e4SLinus Torvalds } 7021da177e4SLinus Torvalds 7031da177e4SLinus Torvalds if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) { 7041da177e4SLinus Torvalds set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1); 7051da177e4SLinus Torvalds PROC_INFO_INC(tb->tb_sb, leaves_removable); 7061da177e4SLinus Torvalds return 1; 7071da177e4SLinus Torvalds } 7081da177e4SLinus Torvalds return 0; 7091da177e4SLinus Torvalds 7101da177e4SLinus Torvalds } 7111da177e4SLinus Torvalds 7121da177e4SLinus Torvalds /* when we do not split item, lnum and rnum are numbers of entire items */ 7131da177e4SLinus Torvalds #define SET_PAR_SHIFT_LEFT \ 7141da177e4SLinus Torvalds if (h)\ 7151da177e4SLinus Torvalds {\ 7161da177e4SLinus Torvalds int to_l;\ 7171da177e4SLinus Torvalds \ 7181da177e4SLinus Torvalds to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\ 7191da177e4SLinus Torvalds (MAX_NR_KEY(Sh) + 1 - lpar);\ 7201da177e4SLinus Torvalds \ 7211da177e4SLinus Torvalds set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\ 7221da177e4SLinus Torvalds }\ 7231da177e4SLinus Torvalds else \ 7241da177e4SLinus Torvalds {\ 7251da177e4SLinus Torvalds if (lset==LEFT_SHIFT_FLOW)\ 7261da177e4SLinus Torvalds set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\ 7271da177e4SLinus Torvalds tb->lbytes, -1);\ 7281da177e4SLinus Torvalds else\ 7291da177e4SLinus Torvalds set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\ 7301da177e4SLinus Torvalds -1, -1);\ 7311da177e4SLinus Torvalds } 7321da177e4SLinus Torvalds 7331da177e4SLinus Torvalds #define SET_PAR_SHIFT_RIGHT \ 7341da177e4SLinus Torvalds if (h)\ 7351da177e4SLinus Torvalds {\ 7361da177e4SLinus Torvalds int to_r;\ 7371da177e4SLinus Torvalds \ 7381da177e4SLinus Torvalds to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\ 7391da177e4SLinus Torvalds \ 7401da177e4SLinus Torvalds set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\ 7411da177e4SLinus Torvalds }\ 7421da177e4SLinus Torvalds else \ 7431da177e4SLinus Torvalds {\ 7441da177e4SLinus Torvalds if (rset==RIGHT_SHIFT_FLOW)\ 7451da177e4SLinus Torvalds set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\ 7461da177e4SLinus Torvalds -1, tb->rbytes);\ 7471da177e4SLinus Torvalds else\ 7481da177e4SLinus Torvalds set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\ 7491da177e4SLinus Torvalds -1, -1);\ 7501da177e4SLinus Torvalds } 7511da177e4SLinus Torvalds 752bd4c625cSLinus Torvalds static void free_buffers_in_tb(struct tree_balance *p_s_tb) 753bd4c625cSLinus Torvalds { 7541da177e4SLinus Torvalds int n_counter; 7551da177e4SLinus Torvalds 7561da177e4SLinus Torvalds decrement_counters_in_path(p_s_tb->tb_path); 7571da177e4SLinus Torvalds 7581da177e4SLinus Torvalds for (n_counter = 0; n_counter < MAX_HEIGHT; n_counter++) { 7591da177e4SLinus Torvalds decrement_bcount(p_s_tb->L[n_counter]); 7601da177e4SLinus Torvalds p_s_tb->L[n_counter] = NULL; 7611da177e4SLinus Torvalds decrement_bcount(p_s_tb->R[n_counter]); 7621da177e4SLinus Torvalds p_s_tb->R[n_counter] = NULL; 7631da177e4SLinus Torvalds decrement_bcount(p_s_tb->FL[n_counter]); 7641da177e4SLinus Torvalds p_s_tb->FL[n_counter] = NULL; 7651da177e4SLinus Torvalds decrement_bcount(p_s_tb->FR[n_counter]); 7661da177e4SLinus Torvalds p_s_tb->FR[n_counter] = NULL; 7671da177e4SLinus Torvalds decrement_bcount(p_s_tb->CFL[n_counter]); 7681da177e4SLinus Torvalds p_s_tb->CFL[n_counter] = NULL; 7691da177e4SLinus Torvalds decrement_bcount(p_s_tb->CFR[n_counter]); 7701da177e4SLinus Torvalds p_s_tb->CFR[n_counter] = NULL; 7711da177e4SLinus Torvalds } 7721da177e4SLinus Torvalds } 7731da177e4SLinus Torvalds 7741da177e4SLinus Torvalds /* Get new buffers for storing new nodes that are created while balancing. 7751da177e4SLinus Torvalds * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked; 7761da177e4SLinus Torvalds * CARRY_ON - schedule didn't occur while the function worked; 7771da177e4SLinus Torvalds * NO_DISK_SPACE - no disk space. 7781da177e4SLinus Torvalds */ 7791da177e4SLinus Torvalds /* The function is NOT SCHEDULE-SAFE! */ 780bd4c625cSLinus Torvalds static int get_empty_nodes(struct tree_balance *p_s_tb, int n_h) 781bd4c625cSLinus Torvalds { 7821da177e4SLinus Torvalds struct buffer_head *p_s_new_bh, 7831da177e4SLinus Torvalds *p_s_Sh = PATH_H_PBUFFER(p_s_tb->tb_path, n_h); 784bd4c625cSLinus Torvalds b_blocknr_t *p_n_blocknr, a_n_blocknrs[MAX_AMOUNT_NEEDED] = { 0, }; 785bd4c625cSLinus Torvalds int n_counter, n_number_of_freeblk, n_amount_needed, /* number of needed empty blocks */ 7861da177e4SLinus Torvalds n_retval = CARRY_ON; 7871da177e4SLinus Torvalds struct super_block *p_s_sb = p_s_tb->tb_sb; 7881da177e4SLinus Torvalds 7891da177e4SLinus Torvalds /* number_of_freeblk is the number of empty blocks which have been 7901da177e4SLinus Torvalds acquired for use by the balancing algorithm minus the number of 7911da177e4SLinus Torvalds empty blocks used in the previous levels of the analysis, 7921da177e4SLinus Torvalds number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs 7931da177e4SLinus Torvalds after empty blocks are acquired, and the balancing analysis is 7941da177e4SLinus Torvalds then restarted, amount_needed is the number needed by this level 7951da177e4SLinus Torvalds (n_h) of the balancing analysis. 7961da177e4SLinus Torvalds 7971da177e4SLinus Torvalds Note that for systems with many processes writing, it would be 7981da177e4SLinus Torvalds more layout optimal to calculate the total number needed by all 7991da177e4SLinus Torvalds levels and then to run reiserfs_new_blocks to get all of them at once. */ 8001da177e4SLinus Torvalds 8011da177e4SLinus Torvalds /* Initiate number_of_freeblk to the amount acquired prior to the restart of 8021da177e4SLinus Torvalds the analysis or 0 if not restarted, then subtract the amount needed 8031da177e4SLinus Torvalds by all of the levels of the tree below n_h. */ 8041da177e4SLinus Torvalds /* blknum includes S[n_h], so we subtract 1 in this calculation */ 805bd4c625cSLinus Torvalds for (n_counter = 0, n_number_of_freeblk = p_s_tb->cur_blknum; 806bd4c625cSLinus Torvalds n_counter < n_h; n_counter++) 807bd4c625cSLinus Torvalds n_number_of_freeblk -= 808bd4c625cSLinus Torvalds (p_s_tb->blknum[n_counter]) ? (p_s_tb->blknum[n_counter] - 809bd4c625cSLinus Torvalds 1) : 0; 8101da177e4SLinus Torvalds 8111da177e4SLinus Torvalds /* Allocate missing empty blocks. */ 8121da177e4SLinus Torvalds /* if p_s_Sh == 0 then we are getting a new root */ 8131da177e4SLinus Torvalds n_amount_needed = (p_s_Sh) ? (p_s_tb->blknum[n_h] - 1) : 1; 8141da177e4SLinus Torvalds /* Amount_needed = the amount that we need more than the amount that we have. */ 8151da177e4SLinus Torvalds if (n_amount_needed > n_number_of_freeblk) 8161da177e4SLinus Torvalds n_amount_needed -= n_number_of_freeblk; 8171da177e4SLinus Torvalds else /* If we have enough already then there is nothing to do. */ 8181da177e4SLinus Torvalds return CARRY_ON; 8191da177e4SLinus Torvalds 8201da177e4SLinus Torvalds /* No need to check quota - is not allocated for blocks used for formatted nodes */ 8211da177e4SLinus Torvalds if (reiserfs_new_form_blocknrs(p_s_tb, a_n_blocknrs, 8221da177e4SLinus Torvalds n_amount_needed) == NO_DISK_SPACE) 8231da177e4SLinus Torvalds return NO_DISK_SPACE; 8241da177e4SLinus Torvalds 8251da177e4SLinus Torvalds /* for each blocknumber we just got, get a buffer and stick it on FEB */ 826bd4c625cSLinus Torvalds for (p_n_blocknr = a_n_blocknrs, n_counter = 0; 827bd4c625cSLinus Torvalds n_counter < n_amount_needed; p_n_blocknr++, n_counter++) { 8281da177e4SLinus Torvalds 8291da177e4SLinus Torvalds RFALSE(!*p_n_blocknr, 8301da177e4SLinus Torvalds "PAP-8135: reiserfs_new_blocknrs failed when got new blocks"); 8311da177e4SLinus Torvalds 8321da177e4SLinus Torvalds p_s_new_bh = sb_getblk(p_s_sb, *p_n_blocknr); 8331da177e4SLinus Torvalds RFALSE(buffer_dirty(p_s_new_bh) || 8341da177e4SLinus Torvalds buffer_journaled(p_s_new_bh) || 8351da177e4SLinus Torvalds buffer_journal_dirty(p_s_new_bh), 8361da177e4SLinus Torvalds "PAP-8140: journlaled or dirty buffer %b for the new block", 8371da177e4SLinus Torvalds p_s_new_bh); 8381da177e4SLinus Torvalds 8391da177e4SLinus Torvalds /* Put empty buffers into the array. */ 8401da177e4SLinus Torvalds RFALSE(p_s_tb->FEB[p_s_tb->cur_blknum], 8411da177e4SLinus Torvalds "PAP-8141: busy slot for new buffer"); 8421da177e4SLinus Torvalds 8431da177e4SLinus Torvalds set_buffer_journal_new(p_s_new_bh); 8441da177e4SLinus Torvalds p_s_tb->FEB[p_s_tb->cur_blknum++] = p_s_new_bh; 8451da177e4SLinus Torvalds } 8461da177e4SLinus Torvalds 8471da177e4SLinus Torvalds if (n_retval == CARRY_ON && FILESYSTEM_CHANGED_TB(p_s_tb)) 8481da177e4SLinus Torvalds n_retval = REPEAT_SEARCH; 8491da177e4SLinus Torvalds 8501da177e4SLinus Torvalds return n_retval; 8511da177e4SLinus Torvalds } 8521da177e4SLinus Torvalds 8531da177e4SLinus Torvalds /* Get free space of the left neighbor, which is stored in the parent 8541da177e4SLinus Torvalds * node of the left neighbor. */ 8551da177e4SLinus Torvalds static int get_lfree(struct tree_balance *tb, int h) 8561da177e4SLinus Torvalds { 8571da177e4SLinus Torvalds struct buffer_head *l, *f; 8581da177e4SLinus Torvalds int order; 8591da177e4SLinus Torvalds 8609dce07f1SAl Viro if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL || 8619dce07f1SAl Viro (l = tb->FL[h]) == NULL) 8621da177e4SLinus Torvalds return 0; 8631da177e4SLinus Torvalds 8641da177e4SLinus Torvalds if (f == l) 8651da177e4SLinus Torvalds order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1; 8661da177e4SLinus Torvalds else { 8671da177e4SLinus Torvalds order = B_NR_ITEMS(l); 8681da177e4SLinus Torvalds f = l; 8691da177e4SLinus Torvalds } 8701da177e4SLinus Torvalds 8711da177e4SLinus Torvalds return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order))); 8721da177e4SLinus Torvalds } 8731da177e4SLinus Torvalds 8741da177e4SLinus Torvalds /* Get free space of the right neighbor, 8751da177e4SLinus Torvalds * which is stored in the parent node of the right neighbor. 8761da177e4SLinus Torvalds */ 8771da177e4SLinus Torvalds static int get_rfree(struct tree_balance *tb, int h) 8781da177e4SLinus Torvalds { 8791da177e4SLinus Torvalds struct buffer_head *r, *f; 8801da177e4SLinus Torvalds int order; 8811da177e4SLinus Torvalds 8829dce07f1SAl Viro if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL || 8839dce07f1SAl Viro (r = tb->FR[h]) == NULL) 8841da177e4SLinus Torvalds return 0; 8851da177e4SLinus Torvalds 8861da177e4SLinus Torvalds if (f == r) 8871da177e4SLinus Torvalds order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1; 8881da177e4SLinus Torvalds else { 8891da177e4SLinus Torvalds order = 0; 8901da177e4SLinus Torvalds f = r; 8911da177e4SLinus Torvalds } 8921da177e4SLinus Torvalds 8931da177e4SLinus Torvalds return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order))); 8941da177e4SLinus Torvalds 8951da177e4SLinus Torvalds } 8961da177e4SLinus Torvalds 8971da177e4SLinus Torvalds /* Check whether left neighbor is in memory. */ 898bd4c625cSLinus Torvalds static int is_left_neighbor_in_cache(struct tree_balance *p_s_tb, int n_h) 899bd4c625cSLinus Torvalds { 9001da177e4SLinus Torvalds struct buffer_head *p_s_father, *left; 9011da177e4SLinus Torvalds struct super_block *p_s_sb = p_s_tb->tb_sb; 9021da177e4SLinus Torvalds b_blocknr_t n_left_neighbor_blocknr; 9031da177e4SLinus Torvalds int n_left_neighbor_position; 9041da177e4SLinus Torvalds 9051da177e4SLinus Torvalds if (!p_s_tb->FL[n_h]) /* Father of the left neighbor does not exist. */ 9061da177e4SLinus Torvalds return 0; 9071da177e4SLinus Torvalds 9081da177e4SLinus Torvalds /* Calculate father of the node to be balanced. */ 9091da177e4SLinus Torvalds p_s_father = PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1); 9101da177e4SLinus Torvalds 9111da177e4SLinus Torvalds RFALSE(!p_s_father || 9121da177e4SLinus Torvalds !B_IS_IN_TREE(p_s_father) || 9131da177e4SLinus Torvalds !B_IS_IN_TREE(p_s_tb->FL[n_h]) || 9141da177e4SLinus Torvalds !buffer_uptodate(p_s_father) || 9151da177e4SLinus Torvalds !buffer_uptodate(p_s_tb->FL[n_h]), 9161da177e4SLinus Torvalds "vs-8165: F[h] (%b) or FL[h] (%b) is invalid", 9171da177e4SLinus Torvalds p_s_father, p_s_tb->FL[n_h]); 9181da177e4SLinus Torvalds 9191da177e4SLinus Torvalds /* Get position of the pointer to the left neighbor into the left father. */ 9201da177e4SLinus Torvalds n_left_neighbor_position = (p_s_father == p_s_tb->FL[n_h]) ? 9211da177e4SLinus Torvalds p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->FL[n_h]); 9221da177e4SLinus Torvalds /* Get left neighbor block number. */ 923bd4c625cSLinus Torvalds n_left_neighbor_blocknr = 924bd4c625cSLinus Torvalds B_N_CHILD_NUM(p_s_tb->FL[n_h], n_left_neighbor_position); 9251da177e4SLinus Torvalds /* Look for the left neighbor in the cache. */ 9261da177e4SLinus Torvalds if ((left = sb_find_get_block(p_s_sb, n_left_neighbor_blocknr))) { 9271da177e4SLinus Torvalds 9281da177e4SLinus Torvalds RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left), 929bd4c625cSLinus Torvalds "vs-8170: left neighbor (%b %z) is not in the tree", 930bd4c625cSLinus Torvalds left, left); 9311da177e4SLinus Torvalds put_bh(left); 9321da177e4SLinus Torvalds return 1; 9331da177e4SLinus Torvalds } 9341da177e4SLinus Torvalds 9351da177e4SLinus Torvalds return 0; 9361da177e4SLinus Torvalds } 9371da177e4SLinus Torvalds 9381da177e4SLinus Torvalds #define LEFT_PARENTS 'l' 9391da177e4SLinus Torvalds #define RIGHT_PARENTS 'r' 9401da177e4SLinus Torvalds 9411da177e4SLinus Torvalds static void decrement_key(struct cpu_key *p_s_key) 9421da177e4SLinus Torvalds { 9431da177e4SLinus Torvalds // call item specific function for this key 9441da177e4SLinus Torvalds item_ops[cpu_key_k_type(p_s_key)]->decrement_key(p_s_key); 9451da177e4SLinus Torvalds } 9461da177e4SLinus Torvalds 9471da177e4SLinus Torvalds /* Calculate far left/right parent of the left/right neighbor of the current node, that 9481da177e4SLinus Torvalds * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h]. 9491da177e4SLinus Torvalds * Calculate left/right common parent of the current node and L[h]/R[h]. 9501da177e4SLinus Torvalds * Calculate left/right delimiting key position. 9511da177e4SLinus Torvalds * Returns: PATH_INCORRECT - path in the tree is not correct; 9521da177e4SLinus Torvalds SCHEDULE_OCCURRED - schedule occurred while the function worked; 9531da177e4SLinus Torvalds * CARRY_ON - schedule didn't occur while the function worked; 9541da177e4SLinus Torvalds */ 9551da177e4SLinus Torvalds static int get_far_parent(struct tree_balance *p_s_tb, 9561da177e4SLinus Torvalds int n_h, 9571da177e4SLinus Torvalds struct buffer_head **pp_s_father, 958bd4c625cSLinus Torvalds struct buffer_head **pp_s_com_father, char c_lr_par) 9591da177e4SLinus Torvalds { 9601da177e4SLinus Torvalds struct buffer_head *p_s_parent; 9611da177e4SLinus Torvalds INITIALIZE_PATH(s_path_to_neighbor_father); 962fec6d055SJosef "Jeff" Sipek struct treepath *p_s_path = p_s_tb->tb_path; 9631da177e4SLinus Torvalds struct cpu_key s_lr_father_key; 9641da177e4SLinus Torvalds int n_counter, 9651da177e4SLinus Torvalds n_position = INT_MAX, 9661da177e4SLinus Torvalds n_first_last_position = 0, 9671da177e4SLinus Torvalds n_path_offset = PATH_H_PATH_OFFSET(p_s_path, n_h); 9681da177e4SLinus Torvalds 9691da177e4SLinus Torvalds /* Starting from F[n_h] go upwards in the tree, and look for the common 9701da177e4SLinus Torvalds ancestor of F[n_h], and its neighbor l/r, that should be obtained. */ 9711da177e4SLinus Torvalds 9721da177e4SLinus Torvalds n_counter = n_path_offset; 9731da177e4SLinus Torvalds 9741da177e4SLinus Torvalds RFALSE(n_counter < FIRST_PATH_ELEMENT_OFFSET, 9751da177e4SLinus Torvalds "PAP-8180: invalid path length"); 9761da177e4SLinus Torvalds 9771da177e4SLinus Torvalds for (; n_counter > FIRST_PATH_ELEMENT_OFFSET; n_counter--) { 9781da177e4SLinus Torvalds /* Check whether parent of the current buffer in the path is really parent in the tree. */ 979bd4c625cSLinus Torvalds if (!B_IS_IN_TREE 980bd4c625cSLinus Torvalds (p_s_parent = PATH_OFFSET_PBUFFER(p_s_path, n_counter - 1))) 9811da177e4SLinus Torvalds return REPEAT_SEARCH; 9821da177e4SLinus Torvalds /* Check whether position in the parent is correct. */ 983bd4c625cSLinus Torvalds if ((n_position = 984bd4c625cSLinus Torvalds PATH_OFFSET_POSITION(p_s_path, 985bd4c625cSLinus Torvalds n_counter - 1)) > 986bd4c625cSLinus Torvalds B_NR_ITEMS(p_s_parent)) 9871da177e4SLinus Torvalds return REPEAT_SEARCH; 9881da177e4SLinus Torvalds /* Check whether parent at the path really points to the child. */ 9891da177e4SLinus Torvalds if (B_N_CHILD_NUM(p_s_parent, n_position) != 9901da177e4SLinus Torvalds PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr) 9911da177e4SLinus Torvalds return REPEAT_SEARCH; 9921da177e4SLinus Torvalds /* Return delimiting key if position in the parent is not equal to first/last one. */ 9931da177e4SLinus Torvalds if (c_lr_par == RIGHT_PARENTS) 9941da177e4SLinus Torvalds n_first_last_position = B_NR_ITEMS(p_s_parent); 9951da177e4SLinus Torvalds if (n_position != n_first_last_position) { 9961da177e4SLinus Torvalds *pp_s_com_father = p_s_parent; 9971da177e4SLinus Torvalds get_bh(*pp_s_com_father); 9981da177e4SLinus Torvalds /*(*pp_s_com_father = p_s_parent)->b_count++; */ 9991da177e4SLinus Torvalds break; 10001da177e4SLinus Torvalds } 10011da177e4SLinus Torvalds } 10021da177e4SLinus Torvalds 10031da177e4SLinus Torvalds /* if we are in the root of the tree, then there is no common father */ 10041da177e4SLinus Torvalds if (n_counter == FIRST_PATH_ELEMENT_OFFSET) { 10051da177e4SLinus Torvalds /* Check whether first buffer in the path is the root of the tree. */ 1006bd4c625cSLinus Torvalds if (PATH_OFFSET_PBUFFER 1007bd4c625cSLinus Torvalds (p_s_tb->tb_path, 1008bd4c625cSLinus Torvalds FIRST_PATH_ELEMENT_OFFSET)->b_blocknr == 10091da177e4SLinus Torvalds SB_ROOT_BLOCK(p_s_tb->tb_sb)) { 10101da177e4SLinus Torvalds *pp_s_father = *pp_s_com_father = NULL; 10111da177e4SLinus Torvalds return CARRY_ON; 10121da177e4SLinus Torvalds } 10131da177e4SLinus Torvalds return REPEAT_SEARCH; 10141da177e4SLinus Torvalds } 10151da177e4SLinus Torvalds 10161da177e4SLinus Torvalds RFALSE(B_LEVEL(*pp_s_com_father) <= DISK_LEAF_NODE_LEVEL, 10171da177e4SLinus Torvalds "PAP-8185: (%b %z) level too small", 10181da177e4SLinus Torvalds *pp_s_com_father, *pp_s_com_father); 10191da177e4SLinus Torvalds 10201da177e4SLinus Torvalds /* Check whether the common parent is locked. */ 10211da177e4SLinus Torvalds 10221da177e4SLinus Torvalds if (buffer_locked(*pp_s_com_father)) { 10231da177e4SLinus Torvalds __wait_on_buffer(*pp_s_com_father); 10241da177e4SLinus Torvalds if (FILESYSTEM_CHANGED_TB(p_s_tb)) { 10251da177e4SLinus Torvalds decrement_bcount(*pp_s_com_father); 10261da177e4SLinus Torvalds return REPEAT_SEARCH; 10271da177e4SLinus Torvalds } 10281da177e4SLinus Torvalds } 10291da177e4SLinus Torvalds 10301da177e4SLinus Torvalds /* So, we got common parent of the current node and its left/right neighbor. 10311da177e4SLinus Torvalds Now we are geting the parent of the left/right neighbor. */ 10321da177e4SLinus Torvalds 10331da177e4SLinus Torvalds /* Form key to get parent of the left/right neighbor. */ 1034bd4c625cSLinus Torvalds le_key2cpu_key(&s_lr_father_key, 1035bd4c625cSLinus Torvalds B_N_PDELIM_KEY(*pp_s_com_father, 1036bd4c625cSLinus Torvalds (c_lr_par == 1037bd4c625cSLinus Torvalds LEFT_PARENTS) ? (p_s_tb->lkey[n_h - 1] = 1038bd4c625cSLinus Torvalds n_position - 1039bd4c625cSLinus Torvalds 1) : (p_s_tb->rkey[n_h - 1040bd4c625cSLinus Torvalds 1] = 1041bd4c625cSLinus Torvalds n_position))); 10421da177e4SLinus Torvalds 10431da177e4SLinus Torvalds if (c_lr_par == LEFT_PARENTS) 10441da177e4SLinus Torvalds decrement_key(&s_lr_father_key); 10451da177e4SLinus Torvalds 1046bd4c625cSLinus Torvalds if (search_by_key 1047bd4c625cSLinus Torvalds (p_s_tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father, 1048bd4c625cSLinus Torvalds n_h + 1) == IO_ERROR) 10491da177e4SLinus Torvalds // path is released 10501da177e4SLinus Torvalds return IO_ERROR; 10511da177e4SLinus Torvalds 10521da177e4SLinus Torvalds if (FILESYSTEM_CHANGED_TB(p_s_tb)) { 10531da177e4SLinus Torvalds decrement_counters_in_path(&s_path_to_neighbor_father); 10541da177e4SLinus Torvalds decrement_bcount(*pp_s_com_father); 10551da177e4SLinus Torvalds return REPEAT_SEARCH; 10561da177e4SLinus Torvalds } 10571da177e4SLinus Torvalds 10581da177e4SLinus Torvalds *pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father); 10591da177e4SLinus Torvalds 10601da177e4SLinus Torvalds RFALSE(B_LEVEL(*pp_s_father) != n_h + 1, 10611da177e4SLinus Torvalds "PAP-8190: (%b %z) level too small", *pp_s_father, *pp_s_father); 1062bd4c625cSLinus Torvalds RFALSE(s_path_to_neighbor_father.path_length < 1063bd4c625cSLinus Torvalds FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small"); 10641da177e4SLinus Torvalds 10651da177e4SLinus Torvalds s_path_to_neighbor_father.path_length--; 10661da177e4SLinus Torvalds decrement_counters_in_path(&s_path_to_neighbor_father); 10671da177e4SLinus Torvalds return CARRY_ON; 10681da177e4SLinus Torvalds } 10691da177e4SLinus Torvalds 10701da177e4SLinus Torvalds /* Get parents of neighbors of node in the path(S[n_path_offset]) and common parents of 10711da177e4SLinus Torvalds * S[n_path_offset] and L[n_path_offset]/R[n_path_offset]: F[n_path_offset], FL[n_path_offset], 10721da177e4SLinus Torvalds * FR[n_path_offset], CFL[n_path_offset], CFR[n_path_offset]. 10731da177e4SLinus Torvalds * Calculate numbers of left and right delimiting keys position: lkey[n_path_offset], rkey[n_path_offset]. 10741da177e4SLinus Torvalds * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked; 10751da177e4SLinus Torvalds * CARRY_ON - schedule didn't occur while the function worked; 10761da177e4SLinus Torvalds */ 10771da177e4SLinus Torvalds static int get_parents(struct tree_balance *p_s_tb, int n_h) 10781da177e4SLinus Torvalds { 1079fec6d055SJosef "Jeff" Sipek struct treepath *p_s_path = p_s_tb->tb_path; 10801da177e4SLinus Torvalds int n_position, 10811da177e4SLinus Torvalds n_ret_value, 10821da177e4SLinus Torvalds n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h); 1083bd4c625cSLinus Torvalds struct buffer_head *p_s_curf, *p_s_curcf; 10841da177e4SLinus Torvalds 10851da177e4SLinus Torvalds /* Current node is the root of the tree or will be root of the tree */ 10861da177e4SLinus Torvalds if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) { 10871da177e4SLinus Torvalds /* The root can not have parents. 10881da177e4SLinus Torvalds Release nodes which previously were obtained as parents of the current node neighbors. */ 10891da177e4SLinus Torvalds decrement_bcount(p_s_tb->FL[n_h]); 10901da177e4SLinus Torvalds decrement_bcount(p_s_tb->CFL[n_h]); 10911da177e4SLinus Torvalds decrement_bcount(p_s_tb->FR[n_h]); 10921da177e4SLinus Torvalds decrement_bcount(p_s_tb->CFR[n_h]); 1093bd4c625cSLinus Torvalds p_s_tb->FL[n_h] = p_s_tb->CFL[n_h] = p_s_tb->FR[n_h] = 1094bd4c625cSLinus Torvalds p_s_tb->CFR[n_h] = NULL; 10951da177e4SLinus Torvalds return CARRY_ON; 10961da177e4SLinus Torvalds } 10971da177e4SLinus Torvalds 10981da177e4SLinus Torvalds /* Get parent FL[n_path_offset] of L[n_path_offset]. */ 10991da177e4SLinus Torvalds if ((n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1))) { 11001da177e4SLinus Torvalds /* Current node is not the first child of its parent. */ 11011da177e4SLinus Torvalds /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */ 1102bd4c625cSLinus Torvalds p_s_curf = p_s_curcf = 1103bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1); 11041da177e4SLinus Torvalds get_bh(p_s_curf); 11051da177e4SLinus Torvalds get_bh(p_s_curf); 11061da177e4SLinus Torvalds p_s_tb->lkey[n_h] = n_position - 1; 1107bd4c625cSLinus Torvalds } else { 11081da177e4SLinus Torvalds /* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node. 11091da177e4SLinus Torvalds Calculate current common parent of L[n_path_offset] and the current node. Note that 11101da177e4SLinus Torvalds CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset]. 11111da177e4SLinus Torvalds Calculate lkey[n_path_offset]. */ 11121da177e4SLinus Torvalds if ((n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf, 1113bd4c625cSLinus Torvalds &p_s_curcf, 1114bd4c625cSLinus Torvalds LEFT_PARENTS)) != CARRY_ON) 11151da177e4SLinus Torvalds return n_ret_value; 11161da177e4SLinus Torvalds } 11171da177e4SLinus Torvalds 11181da177e4SLinus Torvalds decrement_bcount(p_s_tb->FL[n_h]); 11191da177e4SLinus Torvalds p_s_tb->FL[n_h] = p_s_curf; /* New initialization of FL[n_h]. */ 11201da177e4SLinus Torvalds decrement_bcount(p_s_tb->CFL[n_h]); 11211da177e4SLinus Torvalds p_s_tb->CFL[n_h] = p_s_curcf; /* New initialization of CFL[n_h]. */ 11221da177e4SLinus Torvalds 11231da177e4SLinus Torvalds RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) || 11241da177e4SLinus Torvalds (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)), 11251da177e4SLinus Torvalds "PAP-8195: FL (%b) or CFL (%b) is invalid", p_s_curf, p_s_curcf); 11261da177e4SLinus Torvalds 11271da177e4SLinus Torvalds /* Get parent FR[n_h] of R[n_h]. */ 11281da177e4SLinus Torvalds 11291da177e4SLinus Torvalds /* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */ 11301da177e4SLinus Torvalds if (n_position == B_NR_ITEMS(PATH_H_PBUFFER(p_s_path, n_h + 1))) { 11311da177e4SLinus Torvalds /* Calculate current parent of R[n_h], which is the right neighbor of F[n_h]. 11321da177e4SLinus Torvalds Calculate current common parent of R[n_h] and current node. Note that CFR[n_h] 11331da177e4SLinus Torvalds not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */ 1134bd4c625cSLinus Torvalds if ((n_ret_value = 1135bd4c625cSLinus Torvalds get_far_parent(p_s_tb, n_h + 1, &p_s_curf, &p_s_curcf, 1136bd4c625cSLinus Torvalds RIGHT_PARENTS)) != CARRY_ON) 11371da177e4SLinus Torvalds return n_ret_value; 1138bd4c625cSLinus Torvalds } else { 11391da177e4SLinus Torvalds /* Current node is not the last child of its parent F[n_h]. */ 11401da177e4SLinus Torvalds /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */ 1141bd4c625cSLinus Torvalds p_s_curf = p_s_curcf = 1142bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1); 11431da177e4SLinus Torvalds get_bh(p_s_curf); 11441da177e4SLinus Torvalds get_bh(p_s_curf); 11451da177e4SLinus Torvalds p_s_tb->rkey[n_h] = n_position; 11461da177e4SLinus Torvalds } 11471da177e4SLinus Torvalds 11481da177e4SLinus Torvalds decrement_bcount(p_s_tb->FR[n_h]); 11491da177e4SLinus Torvalds p_s_tb->FR[n_h] = p_s_curf; /* New initialization of FR[n_path_offset]. */ 11501da177e4SLinus Torvalds 11511da177e4SLinus Torvalds decrement_bcount(p_s_tb->CFR[n_h]); 11521da177e4SLinus Torvalds p_s_tb->CFR[n_h] = p_s_curcf; /* New initialization of CFR[n_path_offset]. */ 11531da177e4SLinus Torvalds 11541da177e4SLinus Torvalds RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) || 11551da177e4SLinus Torvalds (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)), 11561da177e4SLinus Torvalds "PAP-8205: FR (%b) or CFR (%b) is invalid", p_s_curf, p_s_curcf); 11571da177e4SLinus Torvalds 11581da177e4SLinus Torvalds return CARRY_ON; 11591da177e4SLinus Torvalds } 11601da177e4SLinus Torvalds 11611da177e4SLinus Torvalds /* it is possible to remove node as result of shiftings to 11621da177e4SLinus Torvalds neighbors even when we insert or paste item. */ 1163bd4c625cSLinus Torvalds static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree, 1164bd4c625cSLinus Torvalds struct tree_balance *tb, int h) 11651da177e4SLinus Torvalds { 11661da177e4SLinus Torvalds struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h); 11671da177e4SLinus Torvalds int levbytes = tb->insert_size[h]; 11681da177e4SLinus Torvalds struct item_head *ih; 11691da177e4SLinus Torvalds struct reiserfs_key *r_key = NULL; 11701da177e4SLinus Torvalds 11711da177e4SLinus Torvalds ih = B_N_PITEM_HEAD(Sh, 0); 11721da177e4SLinus Torvalds if (tb->CFR[h]) 11731da177e4SLinus Torvalds r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]); 11741da177e4SLinus Torvalds 1175bd4c625cSLinus Torvalds if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes 11761da177e4SLinus Torvalds /* shifting may merge items which might save space */ 1177bd4c625cSLinus Torvalds - 1178bd4c625cSLinus Torvalds ((!h 1179bd4c625cSLinus Torvalds && op_is_left_mergeable(&(ih->ih_key), Sh->b_size)) ? IH_SIZE : 0) 1180bd4c625cSLinus Torvalds - 1181bd4c625cSLinus Torvalds ((!h && r_key 1182bd4c625cSLinus Torvalds && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0) 1183bd4c625cSLinus Torvalds + ((h) ? KEY_SIZE : 0)) { 11841da177e4SLinus Torvalds /* node can not be removed */ 11851da177e4SLinus Torvalds if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */ 11861da177e4SLinus Torvalds if (!h) 1187bd4c625cSLinus Torvalds tb->s0num = 1188bd4c625cSLinus Torvalds B_NR_ITEMS(Sh) + 1189bd4c625cSLinus Torvalds ((mode == M_INSERT) ? 1 : 0); 11901da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 11911da177e4SLinus Torvalds return NO_BALANCING_NEEDED; 11921da177e4SLinus Torvalds } 11931da177e4SLinus Torvalds } 11941da177e4SLinus Torvalds PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]); 11951da177e4SLinus Torvalds return !NO_BALANCING_NEEDED; 11961da177e4SLinus Torvalds } 11971da177e4SLinus Torvalds 11981da177e4SLinus Torvalds /* Check whether current node S[h] is balanced when increasing its size by 11991da177e4SLinus Torvalds * Inserting or Pasting. 12001da177e4SLinus Torvalds * Calculate parameters for balancing for current level h. 12011da177e4SLinus Torvalds * Parameters: 12021da177e4SLinus Torvalds * tb tree_balance structure; 12031da177e4SLinus Torvalds * h current level of the node; 12041da177e4SLinus Torvalds * inum item number in S[h]; 12051da177e4SLinus Torvalds * mode i - insert, p - paste; 12061da177e4SLinus Torvalds * Returns: 1 - schedule occurred; 12071da177e4SLinus Torvalds * 0 - balancing for higher levels needed; 12081da177e4SLinus Torvalds * -1 - no balancing for higher levels needed; 12091da177e4SLinus Torvalds * -2 - no disk space. 12101da177e4SLinus Torvalds */ 12111da177e4SLinus Torvalds /* ip means Inserting or Pasting */ 12121da177e4SLinus Torvalds static int ip_check_balance(struct tree_balance *tb, int h) 12131da177e4SLinus Torvalds { 12141da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn; 12151da177e4SLinus Torvalds int levbytes, /* Number of bytes that must be inserted into (value 12161da177e4SLinus Torvalds is negative if bytes are deleted) buffer which 12171da177e4SLinus Torvalds contains node being balanced. The mnemonic is 12181da177e4SLinus Torvalds that the attempted change in node space used level 12191da177e4SLinus Torvalds is levbytes bytes. */ 12201da177e4SLinus Torvalds n_ret_value; 12211da177e4SLinus Torvalds 12221da177e4SLinus Torvalds int lfree, sfree, rfree /* free space in L, S and R */ ; 12231da177e4SLinus Torvalds 12241da177e4SLinus Torvalds /* nver is short for number of vertixes, and lnver is the number if 12251da177e4SLinus Torvalds we shift to the left, rnver is the number if we shift to the 12261da177e4SLinus Torvalds right, and lrnver is the number if we shift in both directions. 12271da177e4SLinus Torvalds The goal is to minimize first the number of vertixes, and second, 12281da177e4SLinus Torvalds the number of vertixes whose contents are changed by shifting, 12291da177e4SLinus Torvalds and third the number of uncached vertixes whose contents are 12301da177e4SLinus Torvalds changed by shifting and must be read from disk. */ 12311da177e4SLinus Torvalds int nver, lnver, rnver, lrnver; 12321da177e4SLinus Torvalds 12331da177e4SLinus Torvalds /* used at leaf level only, S0 = S[0] is the node being balanced, 12341da177e4SLinus Torvalds sInum [ I = 0,1,2 ] is the number of items that will 12351da177e4SLinus Torvalds remain in node SI after balancing. S1 and S2 are new 12361da177e4SLinus Torvalds nodes that might be created. */ 12371da177e4SLinus Torvalds 12381da177e4SLinus Torvalds /* we perform 8 calls to get_num_ver(). For each call we calculate five parameters. 12391da177e4SLinus Torvalds where 4th parameter is s1bytes and 5th - s2bytes 12401da177e4SLinus Torvalds */ 12411da177e4SLinus Torvalds short snum012[40] = { 0, }; /* s0num, s1num, s2num for 8 cases 12421da177e4SLinus Torvalds 0,1 - do not shift and do not shift but bottle 12431da177e4SLinus Torvalds 2 - shift only whole item to left 12441da177e4SLinus Torvalds 3 - shift to left and bottle as much as possible 12451da177e4SLinus Torvalds 4,5 - shift to right (whole items and as much as possible 12461da177e4SLinus Torvalds 6,7 - shift to both directions (whole items and as much as possible) 12471da177e4SLinus Torvalds */ 12481da177e4SLinus Torvalds 12491da177e4SLinus Torvalds /* Sh is the node whose balance is currently being checked */ 12501da177e4SLinus Torvalds struct buffer_head *Sh; 12511da177e4SLinus Torvalds 12521da177e4SLinus Torvalds Sh = PATH_H_PBUFFER(tb->tb_path, h); 12531da177e4SLinus Torvalds levbytes = tb->insert_size[h]; 12541da177e4SLinus Torvalds 12551da177e4SLinus Torvalds /* Calculate balance parameters for creating new root. */ 12561da177e4SLinus Torvalds if (!Sh) { 12571da177e4SLinus Torvalds if (!h) 1258bd4c625cSLinus Torvalds reiserfs_panic(tb->tb_sb, 1259bd4c625cSLinus Torvalds "vs-8210: ip_check_balance: S[0] can not be 0"); 12601da177e4SLinus Torvalds switch (n_ret_value = get_empty_nodes(tb, h)) { 12611da177e4SLinus Torvalds case CARRY_ON: 12621da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 12631da177e4SLinus Torvalds return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */ 12641da177e4SLinus Torvalds 12651da177e4SLinus Torvalds case NO_DISK_SPACE: 12661da177e4SLinus Torvalds case REPEAT_SEARCH: 12671da177e4SLinus Torvalds return n_ret_value; 12681da177e4SLinus Torvalds default: 1269bd4c625cSLinus Torvalds reiserfs_panic(tb->tb_sb, 1270bd4c625cSLinus Torvalds "vs-8215: ip_check_balance: incorrect return value of get_empty_nodes"); 12711da177e4SLinus Torvalds } 12721da177e4SLinus Torvalds } 12731da177e4SLinus Torvalds 12741da177e4SLinus Torvalds if ((n_ret_value = get_parents(tb, h)) != CARRY_ON) /* get parents of S[h] neighbors. */ 12751da177e4SLinus Torvalds return n_ret_value; 12761da177e4SLinus Torvalds 12771da177e4SLinus Torvalds sfree = B_FREE_SPACE(Sh); 12781da177e4SLinus Torvalds 12791da177e4SLinus Torvalds /* get free space of neighbors */ 12801da177e4SLinus Torvalds rfree = get_rfree(tb, h); 12811da177e4SLinus Torvalds lfree = get_lfree(tb, h); 12821da177e4SLinus Torvalds 1283bd4c625cSLinus Torvalds if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) == 1284bd4c625cSLinus Torvalds NO_BALANCING_NEEDED) 12851da177e4SLinus Torvalds /* and new item fits into node S[h] without any shifting */ 12861da177e4SLinus Torvalds return NO_BALANCING_NEEDED; 12871da177e4SLinus Torvalds 12881da177e4SLinus Torvalds create_virtual_node(tb, h); 12891da177e4SLinus Torvalds 12901da177e4SLinus Torvalds /* 12911da177e4SLinus Torvalds determine maximal number of items we can shift to the left neighbor (in tb structure) 12921da177e4SLinus Torvalds and the maximal number of bytes that can flow to the left neighbor 12931da177e4SLinus Torvalds from the left most liquid item that cannot be shifted from S[0] entirely (returned value) 12941da177e4SLinus Torvalds */ 12951da177e4SLinus Torvalds check_left(tb, h, lfree); 12961da177e4SLinus Torvalds 12971da177e4SLinus Torvalds /* 12981da177e4SLinus Torvalds determine maximal number of items we can shift to the right neighbor (in tb structure) 12991da177e4SLinus Torvalds and the maximal number of bytes that can flow to the right neighbor 13001da177e4SLinus Torvalds from the right most liquid item that cannot be shifted from S[0] entirely (returned value) 13011da177e4SLinus Torvalds */ 13021da177e4SLinus Torvalds check_right(tb, h, rfree); 13031da177e4SLinus Torvalds 13041da177e4SLinus Torvalds /* all contents of internal node S[h] can be moved into its 13051da177e4SLinus Torvalds neighbors, S[h] will be removed after balancing */ 13061da177e4SLinus Torvalds if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) { 13071da177e4SLinus Torvalds int to_r; 13081da177e4SLinus Torvalds 13091da177e4SLinus Torvalds /* Since we are working on internal nodes, and our internal 13101da177e4SLinus Torvalds nodes have fixed size entries, then we can balance by the 13111da177e4SLinus Torvalds number of items rather than the space they consume. In this 13121da177e4SLinus Torvalds routine we set the left node equal to the right node, 13131da177e4SLinus Torvalds allowing a difference of less than or equal to 1 child 13141da177e4SLinus Torvalds pointer. */ 1315bd4c625cSLinus Torvalds to_r = 1316bd4c625cSLinus Torvalds ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] + 1317bd4c625cSLinus Torvalds vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - 1318bd4c625cSLinus Torvalds tb->rnum[h]); 1319bd4c625cSLinus Torvalds set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, 1320bd4c625cSLinus Torvalds -1, -1); 13211da177e4SLinus Torvalds return CARRY_ON; 13221da177e4SLinus Torvalds } 13231da177e4SLinus Torvalds 13241da177e4SLinus Torvalds /* this checks balance condition, that any two neighboring nodes can not fit in one node */ 13251da177e4SLinus Torvalds RFALSE(h && 13261da177e4SLinus Torvalds (tb->lnum[h] >= vn->vn_nr_item + 1 || 13271da177e4SLinus Torvalds tb->rnum[h] >= vn->vn_nr_item + 1), 13281da177e4SLinus Torvalds "vs-8220: tree is not balanced on internal level"); 13291da177e4SLinus Torvalds RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) || 13301da177e4SLinus Torvalds (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))), 13311da177e4SLinus Torvalds "vs-8225: tree is not balanced on leaf level"); 13321da177e4SLinus Torvalds 13331da177e4SLinus Torvalds /* all contents of S[0] can be moved into its neighbors 13341da177e4SLinus Torvalds S[0] will be removed after balancing. */ 13351da177e4SLinus Torvalds if (!h && is_leaf_removable(tb)) 13361da177e4SLinus Torvalds return CARRY_ON; 13371da177e4SLinus Torvalds 13381da177e4SLinus Torvalds /* why do we perform this check here rather than earlier?? 13391da177e4SLinus Torvalds Answer: we can win 1 node in some cases above. Moreover we 13401da177e4SLinus Torvalds checked it above, when we checked, that S[0] is not removable 13411da177e4SLinus Torvalds in principle */ 13421da177e4SLinus Torvalds if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */ 13431da177e4SLinus Torvalds if (!h) 13441da177e4SLinus Torvalds tb->s0num = vn->vn_nr_item; 13451da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 13461da177e4SLinus Torvalds return NO_BALANCING_NEEDED; 13471da177e4SLinus Torvalds } 13481da177e4SLinus Torvalds 13491da177e4SLinus Torvalds { 13501da177e4SLinus Torvalds int lpar, rpar, nset, lset, rset, lrset; 13511da177e4SLinus Torvalds /* 13521da177e4SLinus Torvalds * regular overflowing of the node 13531da177e4SLinus Torvalds */ 13541da177e4SLinus Torvalds 13551da177e4SLinus Torvalds /* get_num_ver works in 2 modes (FLOW & NO_FLOW) 13561da177e4SLinus Torvalds lpar, rpar - number of items we can shift to left/right neighbor (including splitting item) 13571da177e4SLinus Torvalds nset, lset, rset, lrset - shows, whether flowing items give better packing 13581da177e4SLinus Torvalds */ 13591da177e4SLinus Torvalds #define FLOW 1 13601da177e4SLinus Torvalds #define NO_FLOW 0 /* do not any splitting */ 13611da177e4SLinus Torvalds 13621da177e4SLinus Torvalds /* we choose one the following */ 13631da177e4SLinus Torvalds #define NOTHING_SHIFT_NO_FLOW 0 13641da177e4SLinus Torvalds #define NOTHING_SHIFT_FLOW 5 13651da177e4SLinus Torvalds #define LEFT_SHIFT_NO_FLOW 10 13661da177e4SLinus Torvalds #define LEFT_SHIFT_FLOW 15 13671da177e4SLinus Torvalds #define RIGHT_SHIFT_NO_FLOW 20 13681da177e4SLinus Torvalds #define RIGHT_SHIFT_FLOW 25 13691da177e4SLinus Torvalds #define LR_SHIFT_NO_FLOW 30 13701da177e4SLinus Torvalds #define LR_SHIFT_FLOW 35 13711da177e4SLinus Torvalds 13721da177e4SLinus Torvalds lpar = tb->lnum[h]; 13731da177e4SLinus Torvalds rpar = tb->rnum[h]; 13741da177e4SLinus Torvalds 13751da177e4SLinus Torvalds /* calculate number of blocks S[h] must be split into when 13761da177e4SLinus Torvalds nothing is shifted to the neighbors, 13771da177e4SLinus Torvalds as well as number of items in each part of the split node (s012 numbers), 13781da177e4SLinus Torvalds and number of bytes (s1bytes) of the shared drop which flow to S1 if any */ 13791da177e4SLinus Torvalds nset = NOTHING_SHIFT_NO_FLOW; 13801da177e4SLinus Torvalds nver = get_num_ver(vn->vn_mode, tb, h, 13811da177e4SLinus Torvalds 0, -1, h ? vn->vn_nr_item : 0, -1, 13821da177e4SLinus Torvalds snum012, NO_FLOW); 13831da177e4SLinus Torvalds 1384bd4c625cSLinus Torvalds if (!h) { 13851da177e4SLinus Torvalds int nver1; 13861da177e4SLinus Torvalds 13871da177e4SLinus Torvalds /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */ 13881da177e4SLinus Torvalds nver1 = get_num_ver(vn->vn_mode, tb, h, 13891da177e4SLinus Torvalds 0, -1, 0, -1, 13901da177e4SLinus Torvalds snum012 + NOTHING_SHIFT_FLOW, FLOW); 13911da177e4SLinus Torvalds if (nver > nver1) 13921da177e4SLinus Torvalds nset = NOTHING_SHIFT_FLOW, nver = nver1; 13931da177e4SLinus Torvalds } 13941da177e4SLinus Torvalds 13951da177e4SLinus Torvalds /* calculate number of blocks S[h] must be split into when 13961da177e4SLinus Torvalds l_shift_num first items and l_shift_bytes of the right most 13971da177e4SLinus Torvalds liquid item to be shifted are shifted to the left neighbor, 13981da177e4SLinus Torvalds as well as number of items in each part of the splitted node (s012 numbers), 13991da177e4SLinus Torvalds and number of bytes (s1bytes) of the shared drop which flow to S1 if any 14001da177e4SLinus Torvalds */ 14011da177e4SLinus Torvalds lset = LEFT_SHIFT_NO_FLOW; 14021da177e4SLinus Torvalds lnver = get_num_ver(vn->vn_mode, tb, h, 1403bd4c625cSLinus Torvalds lpar - ((h || tb->lbytes == -1) ? 0 : 1), 1404bd4c625cSLinus Torvalds -1, h ? vn->vn_nr_item : 0, -1, 14051da177e4SLinus Torvalds snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW); 1406bd4c625cSLinus Torvalds if (!h) { 14071da177e4SLinus Torvalds int lnver1; 14081da177e4SLinus Torvalds 14091da177e4SLinus Torvalds lnver1 = get_num_ver(vn->vn_mode, tb, h, 1410bd4c625cSLinus Torvalds lpar - 1411bd4c625cSLinus Torvalds ((tb->lbytes != -1) ? 1 : 0), 1412bd4c625cSLinus Torvalds tb->lbytes, 0, -1, 14131da177e4SLinus Torvalds snum012 + LEFT_SHIFT_FLOW, FLOW); 14141da177e4SLinus Torvalds if (lnver > lnver1) 14151da177e4SLinus Torvalds lset = LEFT_SHIFT_FLOW, lnver = lnver1; 14161da177e4SLinus Torvalds } 14171da177e4SLinus Torvalds 14181da177e4SLinus Torvalds /* calculate number of blocks S[h] must be split into when 14191da177e4SLinus Torvalds r_shift_num first items and r_shift_bytes of the left most 14201da177e4SLinus Torvalds liquid item to be shifted are shifted to the right neighbor, 14211da177e4SLinus Torvalds as well as number of items in each part of the splitted node (s012 numbers), 14221da177e4SLinus Torvalds and number of bytes (s1bytes) of the shared drop which flow to S1 if any 14231da177e4SLinus Torvalds */ 14241da177e4SLinus Torvalds rset = RIGHT_SHIFT_NO_FLOW; 14251da177e4SLinus Torvalds rnver = get_num_ver(vn->vn_mode, tb, h, 1426bd4c625cSLinus Torvalds 0, -1, 1427bd4c625cSLinus Torvalds h ? (vn->vn_nr_item - rpar) : (rpar - 1428bd4c625cSLinus Torvalds ((tb-> 1429bd4c625cSLinus Torvalds rbytes != 1430bd4c625cSLinus Torvalds -1) ? 1 : 1431bd4c625cSLinus Torvalds 0)), -1, 14321da177e4SLinus Torvalds snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW); 1433bd4c625cSLinus Torvalds if (!h) { 14341da177e4SLinus Torvalds int rnver1; 14351da177e4SLinus Torvalds 14361da177e4SLinus Torvalds rnver1 = get_num_ver(vn->vn_mode, tb, h, 1437bd4c625cSLinus Torvalds 0, -1, 1438bd4c625cSLinus Torvalds (rpar - 1439bd4c625cSLinus Torvalds ((tb->rbytes != -1) ? 1 : 0)), 1440bd4c625cSLinus Torvalds tb->rbytes, 14411da177e4SLinus Torvalds snum012 + RIGHT_SHIFT_FLOW, FLOW); 14421da177e4SLinus Torvalds 14431da177e4SLinus Torvalds if (rnver > rnver1) 14441da177e4SLinus Torvalds rset = RIGHT_SHIFT_FLOW, rnver = rnver1; 14451da177e4SLinus Torvalds } 14461da177e4SLinus Torvalds 14471da177e4SLinus Torvalds /* calculate number of blocks S[h] must be split into when 14481da177e4SLinus Torvalds items are shifted in both directions, 14491da177e4SLinus Torvalds as well as number of items in each part of the splitted node (s012 numbers), 14501da177e4SLinus Torvalds and number of bytes (s1bytes) of the shared drop which flow to S1 if any 14511da177e4SLinus Torvalds */ 14521da177e4SLinus Torvalds lrset = LR_SHIFT_NO_FLOW; 14531da177e4SLinus Torvalds lrnver = get_num_ver(vn->vn_mode, tb, h, 1454bd4c625cSLinus Torvalds lpar - ((h || tb->lbytes == -1) ? 0 : 1), 1455bd4c625cSLinus Torvalds -1, 1456bd4c625cSLinus Torvalds h ? (vn->vn_nr_item - rpar) : (rpar - 1457bd4c625cSLinus Torvalds ((tb-> 1458bd4c625cSLinus Torvalds rbytes != 1459bd4c625cSLinus Torvalds -1) ? 1 : 1460bd4c625cSLinus Torvalds 0)), -1, 14611da177e4SLinus Torvalds snum012 + LR_SHIFT_NO_FLOW, NO_FLOW); 1462bd4c625cSLinus Torvalds if (!h) { 14631da177e4SLinus Torvalds int lrnver1; 14641da177e4SLinus Torvalds 14651da177e4SLinus Torvalds lrnver1 = get_num_ver(vn->vn_mode, tb, h, 1466bd4c625cSLinus Torvalds lpar - 1467bd4c625cSLinus Torvalds ((tb->lbytes != -1) ? 1 : 0), 1468bd4c625cSLinus Torvalds tb->lbytes, 1469bd4c625cSLinus Torvalds (rpar - 1470bd4c625cSLinus Torvalds ((tb->rbytes != -1) ? 1 : 0)), 1471bd4c625cSLinus Torvalds tb->rbytes, 14721da177e4SLinus Torvalds snum012 + LR_SHIFT_FLOW, FLOW); 14731da177e4SLinus Torvalds if (lrnver > lrnver1) 14741da177e4SLinus Torvalds lrset = LR_SHIFT_FLOW, lrnver = lrnver1; 14751da177e4SLinus Torvalds } 14761da177e4SLinus Torvalds 14771da177e4SLinus Torvalds /* Our general shifting strategy is: 14781da177e4SLinus Torvalds 1) to minimized number of new nodes; 14791da177e4SLinus Torvalds 2) to minimized number of neighbors involved in shifting; 14801da177e4SLinus Torvalds 3) to minimized number of disk reads; */ 14811da177e4SLinus Torvalds 14821da177e4SLinus Torvalds /* we can win TWO or ONE nodes by shifting in both directions */ 1483bd4c625cSLinus Torvalds if (lrnver < lnver && lrnver < rnver) { 14841da177e4SLinus Torvalds RFALSE(h && 14851da177e4SLinus Torvalds (tb->lnum[h] != 1 || 14861da177e4SLinus Torvalds tb->rnum[h] != 1 || 1487bd4c625cSLinus Torvalds lrnver != 1 || rnver != 2 || lnver != 2 1488bd4c625cSLinus Torvalds || h != 1), "vs-8230: bad h"); 14891da177e4SLinus Torvalds if (lrset == LR_SHIFT_FLOW) 1490bd4c625cSLinus Torvalds set_parameters(tb, h, tb->lnum[h], tb->rnum[h], 1491bd4c625cSLinus Torvalds lrnver, snum012 + lrset, 14921da177e4SLinus Torvalds tb->lbytes, tb->rbytes); 14931da177e4SLinus Torvalds else 1494bd4c625cSLinus Torvalds set_parameters(tb, h, 1495bd4c625cSLinus Torvalds tb->lnum[h] - 1496bd4c625cSLinus Torvalds ((tb->lbytes == -1) ? 0 : 1), 1497bd4c625cSLinus Torvalds tb->rnum[h] - 1498bd4c625cSLinus Torvalds ((tb->rbytes == -1) ? 0 : 1), 1499bd4c625cSLinus Torvalds lrnver, snum012 + lrset, -1, -1); 15001da177e4SLinus Torvalds 15011da177e4SLinus Torvalds return CARRY_ON; 15021da177e4SLinus Torvalds } 15031da177e4SLinus Torvalds 15041da177e4SLinus Torvalds /* if shifting doesn't lead to better packing then don't shift */ 1505bd4c625cSLinus Torvalds if (nver == lrnver) { 1506bd4c625cSLinus Torvalds set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1, 1507bd4c625cSLinus Torvalds -1); 15081da177e4SLinus Torvalds return CARRY_ON; 15091da177e4SLinus Torvalds } 15101da177e4SLinus Torvalds 15111da177e4SLinus Torvalds /* now we know that for better packing shifting in only one 15121da177e4SLinus Torvalds direction either to the left or to the right is required */ 15131da177e4SLinus Torvalds 15141da177e4SLinus Torvalds /* if shifting to the left is better than shifting to the right */ 1515bd4c625cSLinus Torvalds if (lnver < rnver) { 15161da177e4SLinus Torvalds SET_PAR_SHIFT_LEFT; 15171da177e4SLinus Torvalds return CARRY_ON; 15181da177e4SLinus Torvalds } 15191da177e4SLinus Torvalds 15201da177e4SLinus Torvalds /* if shifting to the right is better than shifting to the left */ 1521bd4c625cSLinus Torvalds if (lnver > rnver) { 15221da177e4SLinus Torvalds SET_PAR_SHIFT_RIGHT; 15231da177e4SLinus Torvalds return CARRY_ON; 15241da177e4SLinus Torvalds } 15251da177e4SLinus Torvalds 15261da177e4SLinus Torvalds /* now shifting in either direction gives the same number 15271da177e4SLinus Torvalds of nodes and we can make use of the cached neighbors */ 1528bd4c625cSLinus Torvalds if (is_left_neighbor_in_cache(tb, h)) { 15291da177e4SLinus Torvalds SET_PAR_SHIFT_LEFT; 15301da177e4SLinus Torvalds return CARRY_ON; 15311da177e4SLinus Torvalds } 15321da177e4SLinus Torvalds 15331da177e4SLinus Torvalds /* shift to the right independently on whether the right neighbor in cache or not */ 15341da177e4SLinus Torvalds SET_PAR_SHIFT_RIGHT; 15351da177e4SLinus Torvalds return CARRY_ON; 15361da177e4SLinus Torvalds } 15371da177e4SLinus Torvalds } 15381da177e4SLinus Torvalds 15391da177e4SLinus Torvalds /* Check whether current node S[h] is balanced when Decreasing its size by 15401da177e4SLinus Torvalds * Deleting or Cutting for INTERNAL node of S+tree. 15411da177e4SLinus Torvalds * Calculate parameters for balancing for current level h. 15421da177e4SLinus Torvalds * Parameters: 15431da177e4SLinus Torvalds * tb tree_balance structure; 15441da177e4SLinus Torvalds * h current level of the node; 15451da177e4SLinus Torvalds * inum item number in S[h]; 15461da177e4SLinus Torvalds * mode i - insert, p - paste; 15471da177e4SLinus Torvalds * Returns: 1 - schedule occurred; 15481da177e4SLinus Torvalds * 0 - balancing for higher levels needed; 15491da177e4SLinus Torvalds * -1 - no balancing for higher levels needed; 15501da177e4SLinus Torvalds * -2 - no disk space. 15511da177e4SLinus Torvalds * 15521da177e4SLinus Torvalds * Note: Items of internal nodes have fixed size, so the balance condition for 15531da177e4SLinus Torvalds * the internal part of S+tree is as for the B-trees. 15541da177e4SLinus Torvalds */ 15551da177e4SLinus Torvalds static int dc_check_balance_internal(struct tree_balance *tb, int h) 15561da177e4SLinus Torvalds { 15571da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn; 15581da177e4SLinus Torvalds 15591da177e4SLinus Torvalds /* Sh is the node whose balance is currently being checked, 15601da177e4SLinus Torvalds and Fh is its father. */ 15611da177e4SLinus Torvalds struct buffer_head *Sh, *Fh; 1562bd4c625cSLinus Torvalds int maxsize, n_ret_value; 15631da177e4SLinus Torvalds int lfree, rfree /* free space in L and R */ ; 15641da177e4SLinus Torvalds 15651da177e4SLinus Torvalds Sh = PATH_H_PBUFFER(tb->tb_path, h); 15661da177e4SLinus Torvalds Fh = PATH_H_PPARENT(tb->tb_path, h); 15671da177e4SLinus Torvalds 15681da177e4SLinus Torvalds maxsize = MAX_CHILD_SIZE(Sh); 15691da177e4SLinus Torvalds 15701da177e4SLinus Torvalds /* using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */ 15711da177e4SLinus Torvalds /* new_nr_item = number of items node would have if operation is */ 15721da177e4SLinus Torvalds /* performed without balancing (new_nr_item); */ 15731da177e4SLinus Torvalds create_virtual_node(tb, h); 15741da177e4SLinus Torvalds 1575bd4c625cSLinus Torvalds if (!Fh) { /* S[h] is the root. */ 1576bd4c625cSLinus Torvalds if (vn->vn_nr_item > 0) { 15771da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 15781da177e4SLinus Torvalds return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */ 15791da177e4SLinus Torvalds } 15801da177e4SLinus Torvalds /* new_nr_item == 0. 15811da177e4SLinus Torvalds * Current root will be deleted resulting in 15821da177e4SLinus Torvalds * decrementing the tree height. */ 15831da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 0, NULL, -1, -1); 15841da177e4SLinus Torvalds return CARRY_ON; 15851da177e4SLinus Torvalds } 15861da177e4SLinus Torvalds 15871da177e4SLinus Torvalds if ((n_ret_value = get_parents(tb, h)) != CARRY_ON) 15881da177e4SLinus Torvalds return n_ret_value; 15891da177e4SLinus Torvalds 15901da177e4SLinus Torvalds /* get free space of neighbors */ 15911da177e4SLinus Torvalds rfree = get_rfree(tb, h); 15921da177e4SLinus Torvalds lfree = get_lfree(tb, h); 15931da177e4SLinus Torvalds 15941da177e4SLinus Torvalds /* determine maximal number of items we can fit into neighbors */ 15951da177e4SLinus Torvalds check_left(tb, h, lfree); 15961da177e4SLinus Torvalds check_right(tb, h, rfree); 15971da177e4SLinus Torvalds 1598bd4c625cSLinus Torvalds if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) { /* Balance condition for the internal node is valid. 15991da177e4SLinus Torvalds * In this case we balance only if it leads to better packing. */ 1600bd4c625cSLinus Torvalds if (vn->vn_nr_item == MIN_NR_KEY(Sh)) { /* Here we join S[h] with one of its neighbors, 16011da177e4SLinus Torvalds * which is impossible with greater values of new_nr_item. */ 1602bd4c625cSLinus Torvalds if (tb->lnum[h] >= vn->vn_nr_item + 1) { 16031da177e4SLinus Torvalds /* All contents of S[h] can be moved to L[h]. */ 16041da177e4SLinus Torvalds int n; 16051da177e4SLinus Torvalds int order_L; 16061da177e4SLinus Torvalds 1607bd4c625cSLinus Torvalds order_L = 1608bd4c625cSLinus Torvalds ((n = 1609bd4c625cSLinus Torvalds PATH_H_B_ITEM_ORDER(tb->tb_path, 1610bd4c625cSLinus Torvalds h)) == 1611bd4c625cSLinus Torvalds 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; 1612bd4c625cSLinus Torvalds n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / 1613bd4c625cSLinus Torvalds (DC_SIZE + KEY_SIZE); 1614bd4c625cSLinus Torvalds set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, 1615bd4c625cSLinus Torvalds -1); 16161da177e4SLinus Torvalds return CARRY_ON; 16171da177e4SLinus Torvalds } 16181da177e4SLinus Torvalds 1619bd4c625cSLinus Torvalds if (tb->rnum[h] >= vn->vn_nr_item + 1) { 16201da177e4SLinus Torvalds /* All contents of S[h] can be moved to R[h]. */ 16211da177e4SLinus Torvalds int n; 16221da177e4SLinus Torvalds int order_R; 16231da177e4SLinus Torvalds 1624bd4c625cSLinus Torvalds order_R = 1625bd4c625cSLinus Torvalds ((n = 1626bd4c625cSLinus Torvalds PATH_H_B_ITEM_ORDER(tb->tb_path, 1627bd4c625cSLinus Torvalds h)) == 1628bd4c625cSLinus Torvalds B_NR_ITEMS(Fh)) ? 0 : n + 1; 1629bd4c625cSLinus Torvalds n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / 1630bd4c625cSLinus Torvalds (DC_SIZE + KEY_SIZE); 1631bd4c625cSLinus Torvalds set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, 1632bd4c625cSLinus Torvalds -1); 16331da177e4SLinus Torvalds return CARRY_ON; 16341da177e4SLinus Torvalds } 16351da177e4SLinus Torvalds } 16361da177e4SLinus Torvalds 1637bd4c625cSLinus Torvalds if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) { 16381da177e4SLinus Torvalds /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */ 16391da177e4SLinus Torvalds int to_r; 16401da177e4SLinus Torvalds 1641bd4c625cSLinus Torvalds to_r = 1642bd4c625cSLinus Torvalds ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - 1643bd4c625cSLinus Torvalds tb->rnum[h] + vn->vn_nr_item + 1) / 2 - 16441da177e4SLinus Torvalds (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]); 1645bd4c625cSLinus Torvalds set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 1646bd4c625cSLinus Torvalds 0, NULL, -1, -1); 16471da177e4SLinus Torvalds return CARRY_ON; 16481da177e4SLinus Torvalds } 16491da177e4SLinus Torvalds 16501da177e4SLinus Torvalds /* Balancing does not lead to better packing. */ 16511da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 16521da177e4SLinus Torvalds return NO_BALANCING_NEEDED; 16531da177e4SLinus Torvalds } 16541da177e4SLinus Torvalds 16551da177e4SLinus Torvalds /* Current node contain insufficient number of items. Balancing is required. */ 16561da177e4SLinus Torvalds /* Check whether we can merge S[h] with left neighbor. */ 16571da177e4SLinus Torvalds if (tb->lnum[h] >= vn->vn_nr_item + 1) 1658bd4c625cSLinus Torvalds if (is_left_neighbor_in_cache(tb, h) 1659bd4c625cSLinus Torvalds || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) { 16601da177e4SLinus Torvalds int n; 16611da177e4SLinus Torvalds int order_L; 16621da177e4SLinus Torvalds 1663bd4c625cSLinus Torvalds order_L = 1664bd4c625cSLinus Torvalds ((n = 1665bd4c625cSLinus Torvalds PATH_H_B_ITEM_ORDER(tb->tb_path, 1666bd4c625cSLinus Torvalds h)) == 1667bd4c625cSLinus Torvalds 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; 1668bd4c625cSLinus Torvalds n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE + 1669bd4c625cSLinus Torvalds KEY_SIZE); 16701da177e4SLinus Torvalds set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1); 16711da177e4SLinus Torvalds return CARRY_ON; 16721da177e4SLinus Torvalds } 16731da177e4SLinus Torvalds 16741da177e4SLinus Torvalds /* Check whether we can merge S[h] with right neighbor. */ 1675bd4c625cSLinus Torvalds if (tb->rnum[h] >= vn->vn_nr_item + 1) { 16761da177e4SLinus Torvalds int n; 16771da177e4SLinus Torvalds int order_R; 16781da177e4SLinus Torvalds 1679bd4c625cSLinus Torvalds order_R = 1680bd4c625cSLinus Torvalds ((n = 1681bd4c625cSLinus Torvalds PATH_H_B_ITEM_ORDER(tb->tb_path, 1682bd4c625cSLinus Torvalds h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1); 1683bd4c625cSLinus Torvalds n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE + 1684bd4c625cSLinus Torvalds KEY_SIZE); 16851da177e4SLinus Torvalds set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1); 16861da177e4SLinus Torvalds return CARRY_ON; 16871da177e4SLinus Torvalds } 16881da177e4SLinus Torvalds 16891da177e4SLinus Torvalds /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */ 1690bd4c625cSLinus Torvalds if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) { 16911da177e4SLinus Torvalds int to_r; 16921da177e4SLinus Torvalds 1693bd4c625cSLinus Torvalds to_r = 1694bd4c625cSLinus Torvalds ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] + 1695bd4c625cSLinus Torvalds vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - 1696bd4c625cSLinus Torvalds tb->rnum[h]); 1697bd4c625cSLinus Torvalds set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, 1698bd4c625cSLinus Torvalds -1, -1); 16991da177e4SLinus Torvalds return CARRY_ON; 17001da177e4SLinus Torvalds } 17011da177e4SLinus Torvalds 17021da177e4SLinus Torvalds /* For internal nodes try to borrow item from a neighbor */ 17031da177e4SLinus Torvalds RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root"); 17041da177e4SLinus Torvalds 17051da177e4SLinus Torvalds /* Borrow one or two items from caching neighbor */ 1706bd4c625cSLinus Torvalds if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) { 17071da177e4SLinus Torvalds int from_l; 17081da177e4SLinus Torvalds 1709bd4c625cSLinus Torvalds from_l = 1710bd4c625cSLinus Torvalds (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item + 1711bd4c625cSLinus Torvalds 1) / 2 - (vn->vn_nr_item + 1); 17121da177e4SLinus Torvalds set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1); 17131da177e4SLinus Torvalds return CARRY_ON; 17141da177e4SLinus Torvalds } 17151da177e4SLinus Torvalds 1716bd4c625cSLinus Torvalds set_parameters(tb, h, 0, 1717bd4c625cSLinus Torvalds -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item + 1718bd4c625cSLinus Torvalds 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1); 17191da177e4SLinus Torvalds return CARRY_ON; 17201da177e4SLinus Torvalds } 17211da177e4SLinus Torvalds 17221da177e4SLinus Torvalds /* Check whether current node S[h] is balanced when Decreasing its size by 17231da177e4SLinus Torvalds * Deleting or Truncating for LEAF node of S+tree. 17241da177e4SLinus Torvalds * Calculate parameters for balancing for current level h. 17251da177e4SLinus Torvalds * Parameters: 17261da177e4SLinus Torvalds * tb tree_balance structure; 17271da177e4SLinus Torvalds * h current level of the node; 17281da177e4SLinus Torvalds * inum item number in S[h]; 17291da177e4SLinus Torvalds * mode i - insert, p - paste; 17301da177e4SLinus Torvalds * Returns: 1 - schedule occurred; 17311da177e4SLinus Torvalds * 0 - balancing for higher levels needed; 17321da177e4SLinus Torvalds * -1 - no balancing for higher levels needed; 17331da177e4SLinus Torvalds * -2 - no disk space. 17341da177e4SLinus Torvalds */ 17351da177e4SLinus Torvalds static int dc_check_balance_leaf(struct tree_balance *tb, int h) 17361da177e4SLinus Torvalds { 17371da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn; 17381da177e4SLinus Torvalds 17391da177e4SLinus Torvalds /* Number of bytes that must be deleted from 17401da177e4SLinus Torvalds (value is negative if bytes are deleted) buffer which 17411da177e4SLinus Torvalds contains node being balanced. The mnemonic is that the 17421da177e4SLinus Torvalds attempted change in node space used level is levbytes bytes. */ 17431da177e4SLinus Torvalds int levbytes; 17441da177e4SLinus Torvalds /* the maximal item size */ 1745bd4c625cSLinus Torvalds int maxsize, n_ret_value; 17461da177e4SLinus Torvalds /* S0 is the node whose balance is currently being checked, 17471da177e4SLinus Torvalds and F0 is its father. */ 17481da177e4SLinus Torvalds struct buffer_head *S0, *F0; 17491da177e4SLinus Torvalds int lfree, rfree /* free space in L and R */ ; 17501da177e4SLinus Torvalds 17511da177e4SLinus Torvalds S0 = PATH_H_PBUFFER(tb->tb_path, 0); 17521da177e4SLinus Torvalds F0 = PATH_H_PPARENT(tb->tb_path, 0); 17531da177e4SLinus Torvalds 17541da177e4SLinus Torvalds levbytes = tb->insert_size[h]; 17551da177e4SLinus Torvalds 17561da177e4SLinus Torvalds maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */ 17571da177e4SLinus Torvalds 1758bd4c625cSLinus Torvalds if (!F0) { /* S[0] is the root now. */ 17591da177e4SLinus Torvalds 17601da177e4SLinus Torvalds RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0), 17611da177e4SLinus Torvalds "vs-8240: attempt to create empty buffer tree"); 17621da177e4SLinus Torvalds 17631da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 17641da177e4SLinus Torvalds return NO_BALANCING_NEEDED; 17651da177e4SLinus Torvalds } 17661da177e4SLinus Torvalds 17671da177e4SLinus Torvalds if ((n_ret_value = get_parents(tb, h)) != CARRY_ON) 17681da177e4SLinus Torvalds return n_ret_value; 17691da177e4SLinus Torvalds 17701da177e4SLinus Torvalds /* get free space of neighbors */ 17711da177e4SLinus Torvalds rfree = get_rfree(tb, h); 17721da177e4SLinus Torvalds lfree = get_lfree(tb, h); 17731da177e4SLinus Torvalds 17741da177e4SLinus Torvalds create_virtual_node(tb, h); 17751da177e4SLinus Torvalds 17761da177e4SLinus Torvalds /* if 3 leaves can be merge to one, set parameters and return */ 17771da177e4SLinus Torvalds if (are_leaves_removable(tb, lfree, rfree)) 17781da177e4SLinus Torvalds return CARRY_ON; 17791da177e4SLinus Torvalds 17801da177e4SLinus Torvalds /* determine maximal number of items we can shift to the left/right neighbor 17811da177e4SLinus Torvalds and the maximal number of bytes that can flow to the left/right neighbor 17821da177e4SLinus Torvalds from the left/right most liquid item that cannot be shifted from S[0] entirely 17831da177e4SLinus Torvalds */ 17841da177e4SLinus Torvalds check_left(tb, h, lfree); 17851da177e4SLinus Torvalds check_right(tb, h, rfree); 17861da177e4SLinus Torvalds 17871da177e4SLinus Torvalds /* check whether we can merge S with left neighbor. */ 17881da177e4SLinus Torvalds if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1) 1789bd4c625cSLinus Torvalds if (is_left_neighbor_in_cache(tb, h) || ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_item) || /* S can not be merged with R */ 17901da177e4SLinus Torvalds !tb->FR[h]) { 17911da177e4SLinus Torvalds 1792bd4c625cSLinus Torvalds RFALSE(!tb->FL[h], 1793bd4c625cSLinus Torvalds "vs-8245: dc_check_balance_leaf: FL[h] must exist"); 17941da177e4SLinus Torvalds 17951da177e4SLinus Torvalds /* set parameter to merge S[0] with its left neighbor */ 17961da177e4SLinus Torvalds set_parameters(tb, h, -1, 0, 0, NULL, -1, -1); 17971da177e4SLinus Torvalds return CARRY_ON; 17981da177e4SLinus Torvalds } 17991da177e4SLinus Torvalds 18001da177e4SLinus Torvalds /* check whether we can merge S[0] with right neighbor. */ 18011da177e4SLinus Torvalds if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) { 18021da177e4SLinus Torvalds set_parameters(tb, h, 0, -1, 0, NULL, -1, -1); 18031da177e4SLinus Torvalds return CARRY_ON; 18041da177e4SLinus Torvalds } 18051da177e4SLinus Torvalds 18061da177e4SLinus Torvalds /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */ 18071da177e4SLinus Torvalds if (is_leaf_removable(tb)) 18081da177e4SLinus Torvalds return CARRY_ON; 18091da177e4SLinus Torvalds 18101da177e4SLinus Torvalds /* Balancing is not required. */ 18111da177e4SLinus Torvalds tb->s0num = vn->vn_nr_item; 18121da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 18131da177e4SLinus Torvalds return NO_BALANCING_NEEDED; 18141da177e4SLinus Torvalds } 18151da177e4SLinus Torvalds 18161da177e4SLinus Torvalds /* Check whether current node S[h] is balanced when Decreasing its size by 18171da177e4SLinus Torvalds * Deleting or Cutting. 18181da177e4SLinus Torvalds * Calculate parameters for balancing for current level h. 18191da177e4SLinus Torvalds * Parameters: 18201da177e4SLinus Torvalds * tb tree_balance structure; 18211da177e4SLinus Torvalds * h current level of the node; 18221da177e4SLinus Torvalds * inum item number in S[h]; 18231da177e4SLinus Torvalds * mode d - delete, c - cut. 18241da177e4SLinus Torvalds * Returns: 1 - schedule occurred; 18251da177e4SLinus Torvalds * 0 - balancing for higher levels needed; 18261da177e4SLinus Torvalds * -1 - no balancing for higher levels needed; 18271da177e4SLinus Torvalds * -2 - no disk space. 18281da177e4SLinus Torvalds */ 18291da177e4SLinus Torvalds static int dc_check_balance(struct tree_balance *tb, int h) 18301da177e4SLinus Torvalds { 1831bd4c625cSLinus Torvalds RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)), 1832bd4c625cSLinus Torvalds "vs-8250: S is not initialized"); 18331da177e4SLinus Torvalds 18341da177e4SLinus Torvalds if (h) 18351da177e4SLinus Torvalds return dc_check_balance_internal(tb, h); 18361da177e4SLinus Torvalds else 18371da177e4SLinus Torvalds return dc_check_balance_leaf(tb, h); 18381da177e4SLinus Torvalds } 18391da177e4SLinus Torvalds 18401da177e4SLinus Torvalds /* Check whether current node S[h] is balanced. 18411da177e4SLinus Torvalds * Calculate parameters for balancing for current level h. 18421da177e4SLinus Torvalds * Parameters: 18431da177e4SLinus Torvalds * 18441da177e4SLinus Torvalds * tb tree_balance structure: 18451da177e4SLinus Torvalds * 18461da177e4SLinus Torvalds * tb is a large structure that must be read about in the header file 18471da177e4SLinus Torvalds * at the same time as this procedure if the reader is to successfully 18481da177e4SLinus Torvalds * understand this procedure 18491da177e4SLinus Torvalds * 18501da177e4SLinus Torvalds * h current level of the node; 18511da177e4SLinus Torvalds * inum item number in S[h]; 18521da177e4SLinus Torvalds * mode i - insert, p - paste, d - delete, c - cut. 18531da177e4SLinus Torvalds * Returns: 1 - schedule occurred; 18541da177e4SLinus Torvalds * 0 - balancing for higher levels needed; 18551da177e4SLinus Torvalds * -1 - no balancing for higher levels needed; 18561da177e4SLinus Torvalds * -2 - no disk space. 18571da177e4SLinus Torvalds */ 18581da177e4SLinus Torvalds static int check_balance(int mode, 18591da177e4SLinus Torvalds struct tree_balance *tb, 18601da177e4SLinus Torvalds int h, 18611da177e4SLinus Torvalds int inum, 18621da177e4SLinus Torvalds int pos_in_item, 1863bd4c625cSLinus Torvalds struct item_head *ins_ih, const void *data) 18641da177e4SLinus Torvalds { 18651da177e4SLinus Torvalds struct virtual_node *vn; 18661da177e4SLinus Torvalds 18671da177e4SLinus Torvalds vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf); 18681da177e4SLinus Torvalds vn->vn_free_ptr = (char *)(tb->tb_vn + 1); 18691da177e4SLinus Torvalds vn->vn_mode = mode; 18701da177e4SLinus Torvalds vn->vn_affected_item_num = inum; 18711da177e4SLinus Torvalds vn->vn_pos_in_item = pos_in_item; 18721da177e4SLinus Torvalds vn->vn_ins_ih = ins_ih; 18731da177e4SLinus Torvalds vn->vn_data = data; 18741da177e4SLinus Torvalds 18751da177e4SLinus Torvalds RFALSE(mode == M_INSERT && !vn->vn_ins_ih, 18761da177e4SLinus Torvalds "vs-8255: ins_ih can not be 0 in insert mode"); 18771da177e4SLinus Torvalds 18781da177e4SLinus Torvalds if (tb->insert_size[h] > 0) 18791da177e4SLinus Torvalds /* Calculate balance parameters when size of node is increasing. */ 18801da177e4SLinus Torvalds return ip_check_balance(tb, h); 18811da177e4SLinus Torvalds 18821da177e4SLinus Torvalds /* Calculate balance parameters when size of node is decreasing. */ 18831da177e4SLinus Torvalds return dc_check_balance(tb, h); 18841da177e4SLinus Torvalds } 18851da177e4SLinus Torvalds 18861da177e4SLinus Torvalds /* Check whether parent at the path is the really parent of the current node.*/ 1887bd4c625cSLinus Torvalds static int get_direct_parent(struct tree_balance *p_s_tb, int n_h) 1888bd4c625cSLinus Torvalds { 18891da177e4SLinus Torvalds struct buffer_head *p_s_bh; 1890fec6d055SJosef "Jeff" Sipek struct treepath *p_s_path = p_s_tb->tb_path; 18911da177e4SLinus Torvalds int n_position, 18921da177e4SLinus Torvalds n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h); 18931da177e4SLinus Torvalds 18941da177e4SLinus Torvalds /* We are in the root or in the new root. */ 18951da177e4SLinus Torvalds if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) { 18961da177e4SLinus Torvalds 18971da177e4SLinus Torvalds RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET - 1, 18981da177e4SLinus Torvalds "PAP-8260: invalid offset in the path"); 18991da177e4SLinus Torvalds 1900bd4c625cSLinus Torvalds if (PATH_OFFSET_PBUFFER(p_s_path, FIRST_PATH_ELEMENT_OFFSET)-> 1901bd4c625cSLinus Torvalds b_blocknr == SB_ROOT_BLOCK(p_s_tb->tb_sb)) { 19021da177e4SLinus Torvalds /* Root is not changed. */ 19031da177e4SLinus Torvalds PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1) = NULL; 19041da177e4SLinus Torvalds PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1) = 0; 19051da177e4SLinus Torvalds return CARRY_ON; 19061da177e4SLinus Torvalds } 19071da177e4SLinus Torvalds return REPEAT_SEARCH; /* Root is changed and we must recalculate the path. */ 19081da177e4SLinus Torvalds } 19091da177e4SLinus Torvalds 1910bd4c625cSLinus Torvalds if (!B_IS_IN_TREE 1911bd4c625cSLinus Torvalds (p_s_bh = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))) 19121da177e4SLinus Torvalds return REPEAT_SEARCH; /* Parent in the path is not in the tree. */ 19131da177e4SLinus Torvalds 1914bd4c625cSLinus Torvalds if ((n_position = 1915bd4c625cSLinus Torvalds PATH_OFFSET_POSITION(p_s_path, 1916bd4c625cSLinus Torvalds n_path_offset - 1)) > B_NR_ITEMS(p_s_bh)) 19171da177e4SLinus Torvalds return REPEAT_SEARCH; 19181da177e4SLinus Torvalds 1919bd4c625cSLinus Torvalds if (B_N_CHILD_NUM(p_s_bh, n_position) != 1920bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER(p_s_path, n_path_offset)->b_blocknr) 19211da177e4SLinus Torvalds /* Parent in the path is not parent of the current node in the tree. */ 19221da177e4SLinus Torvalds return REPEAT_SEARCH; 19231da177e4SLinus Torvalds 19241da177e4SLinus Torvalds if (buffer_locked(p_s_bh)) { 19251da177e4SLinus Torvalds __wait_on_buffer(p_s_bh); 19261da177e4SLinus Torvalds if (FILESYSTEM_CHANGED_TB(p_s_tb)) 19271da177e4SLinus Torvalds return REPEAT_SEARCH; 19281da177e4SLinus Torvalds } 19291da177e4SLinus Torvalds 19301da177e4SLinus Torvalds return CARRY_ON; /* Parent in the path is unlocked and really parent of the current node. */ 19311da177e4SLinus Torvalds } 19321da177e4SLinus Torvalds 19331da177e4SLinus Torvalds /* Using lnum[n_h] and rnum[n_h] we should determine what neighbors 19341da177e4SLinus Torvalds * of S[n_h] we 19351da177e4SLinus Torvalds * need in order to balance S[n_h], and get them if necessary. 19361da177e4SLinus Torvalds * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked; 19371da177e4SLinus Torvalds * CARRY_ON - schedule didn't occur while the function worked; 19381da177e4SLinus Torvalds */ 1939bd4c625cSLinus Torvalds static int get_neighbors(struct tree_balance *p_s_tb, int n_h) 1940bd4c625cSLinus Torvalds { 19411da177e4SLinus Torvalds int n_child_position, 19421da177e4SLinus Torvalds n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h + 1); 19431da177e4SLinus Torvalds unsigned long n_son_number; 19441da177e4SLinus Torvalds struct super_block *p_s_sb = p_s_tb->tb_sb; 19451da177e4SLinus Torvalds struct buffer_head *p_s_bh; 19461da177e4SLinus Torvalds 19471da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, get_neighbors[n_h]); 19481da177e4SLinus Torvalds 19491da177e4SLinus Torvalds if (p_s_tb->lnum[n_h]) { 19501da177e4SLinus Torvalds /* We need left neighbor to balance S[n_h]. */ 19511da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, need_l_neighbor[n_h]); 19521da177e4SLinus Torvalds p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset); 19531da177e4SLinus Torvalds 19541da177e4SLinus Torvalds RFALSE(p_s_bh == p_s_tb->FL[n_h] && 19551da177e4SLinus Torvalds !PATH_OFFSET_POSITION(p_s_tb->tb_path, n_path_offset), 19561da177e4SLinus Torvalds "PAP-8270: invalid position in the parent"); 19571da177e4SLinus Torvalds 1958bd4c625cSLinus Torvalds n_child_position = 1959bd4c625cSLinus Torvalds (p_s_bh == 1960bd4c625cSLinus Torvalds p_s_tb->FL[n_h]) ? p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb-> 1961bd4c625cSLinus Torvalds FL[n_h]); 19621da177e4SLinus Torvalds n_son_number = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position); 19631da177e4SLinus Torvalds p_s_bh = sb_bread(p_s_sb, n_son_number); 19641da177e4SLinus Torvalds if (!p_s_bh) 19651da177e4SLinus Torvalds return IO_ERROR; 19661da177e4SLinus Torvalds if (FILESYSTEM_CHANGED_TB(p_s_tb)) { 19671da177e4SLinus Torvalds decrement_bcount(p_s_bh); 19681da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]); 19691da177e4SLinus Torvalds return REPEAT_SEARCH; 19701da177e4SLinus Torvalds } 19711da177e4SLinus Torvalds 19721da177e4SLinus Torvalds RFALSE(!B_IS_IN_TREE(p_s_tb->FL[n_h]) || 19731da177e4SLinus Torvalds n_child_position > B_NR_ITEMS(p_s_tb->FL[n_h]) || 19741da177e4SLinus Torvalds B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position) != 19751da177e4SLinus Torvalds p_s_bh->b_blocknr, "PAP-8275: invalid parent"); 19761da177e4SLinus Torvalds RFALSE(!B_IS_IN_TREE(p_s_bh), "PAP-8280: invalid child"); 19771da177e4SLinus Torvalds RFALSE(!n_h && 1978bd4c625cSLinus Torvalds B_FREE_SPACE(p_s_bh) != 1979bd4c625cSLinus Torvalds MAX_CHILD_SIZE(p_s_bh) - 1980bd4c625cSLinus Torvalds dc_size(B_N_CHILD(p_s_tb->FL[0], n_child_position)), 19811da177e4SLinus Torvalds "PAP-8290: invalid child size of left neighbor"); 19821da177e4SLinus Torvalds 19831da177e4SLinus Torvalds decrement_bcount(p_s_tb->L[n_h]); 19841da177e4SLinus Torvalds p_s_tb->L[n_h] = p_s_bh; 19851da177e4SLinus Torvalds } 19861da177e4SLinus Torvalds 19871da177e4SLinus Torvalds if (p_s_tb->rnum[n_h]) { /* We need right neighbor to balance S[n_path_offset]. */ 19881da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, need_r_neighbor[n_h]); 19891da177e4SLinus Torvalds p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset); 19901da177e4SLinus Torvalds 19911da177e4SLinus Torvalds RFALSE(p_s_bh == p_s_tb->FR[n_h] && 1992bd4c625cSLinus Torvalds PATH_OFFSET_POSITION(p_s_tb->tb_path, 1993bd4c625cSLinus Torvalds n_path_offset) >= 1994bd4c625cSLinus Torvalds B_NR_ITEMS(p_s_bh), 19951da177e4SLinus Torvalds "PAP-8295: invalid position in the parent"); 19961da177e4SLinus Torvalds 1997bd4c625cSLinus Torvalds n_child_position = 1998bd4c625cSLinus Torvalds (p_s_bh == p_s_tb->FR[n_h]) ? p_s_tb->rkey[n_h] + 1 : 0; 19991da177e4SLinus Torvalds n_son_number = B_N_CHILD_NUM(p_s_tb->FR[n_h], n_child_position); 20001da177e4SLinus Torvalds p_s_bh = sb_bread(p_s_sb, n_son_number); 20011da177e4SLinus Torvalds if (!p_s_bh) 20021da177e4SLinus Torvalds return IO_ERROR; 20031da177e4SLinus Torvalds if (FILESYSTEM_CHANGED_TB(p_s_tb)) { 20041da177e4SLinus Torvalds decrement_bcount(p_s_bh); 20051da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]); 20061da177e4SLinus Torvalds return REPEAT_SEARCH; 20071da177e4SLinus Torvalds } 20081da177e4SLinus Torvalds decrement_bcount(p_s_tb->R[n_h]); 20091da177e4SLinus Torvalds p_s_tb->R[n_h] = p_s_bh; 20101da177e4SLinus Torvalds 2011bd4c625cSLinus Torvalds RFALSE(!n_h 2012bd4c625cSLinus Torvalds && B_FREE_SPACE(p_s_bh) != 2013bd4c625cSLinus Torvalds MAX_CHILD_SIZE(p_s_bh) - 2014bd4c625cSLinus Torvalds dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)), 20151da177e4SLinus Torvalds "PAP-8300: invalid child size of right neighbor (%d != %d - %d)", 20161da177e4SLinus Torvalds B_FREE_SPACE(p_s_bh), MAX_CHILD_SIZE(p_s_bh), 20171da177e4SLinus Torvalds dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position))); 20181da177e4SLinus Torvalds 20191da177e4SLinus Torvalds } 20201da177e4SLinus Torvalds return CARRY_ON; 20211da177e4SLinus Torvalds } 20221da177e4SLinus Torvalds 20231da177e4SLinus Torvalds static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh) 20241da177e4SLinus Torvalds { 20251da177e4SLinus Torvalds int max_num_of_items; 20261da177e4SLinus Torvalds int max_num_of_entries; 20271da177e4SLinus Torvalds unsigned long blocksize = sb->s_blocksize; 20281da177e4SLinus Torvalds 20291da177e4SLinus Torvalds #define MIN_NAME_LEN 1 20301da177e4SLinus Torvalds 20311da177e4SLinus Torvalds max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN); 20321da177e4SLinus Torvalds max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) / 20331da177e4SLinus Torvalds (DEH_SIZE + MIN_NAME_LEN); 20341da177e4SLinus Torvalds 20351da177e4SLinus Torvalds return sizeof(struct virtual_node) + 20361da177e4SLinus Torvalds max(max_num_of_items * sizeof(struct virtual_item), 20371da177e4SLinus Torvalds sizeof(struct virtual_item) + sizeof(struct direntry_uarea) + 20381da177e4SLinus Torvalds (max_num_of_entries - 1) * sizeof(__u16)); 20391da177e4SLinus Torvalds } 20401da177e4SLinus Torvalds 20411da177e4SLinus Torvalds /* maybe we should fail balancing we are going to perform when kmalloc 20421da177e4SLinus Torvalds fails several times. But now it will loop until kmalloc gets 20431da177e4SLinus Torvalds required memory */ 20441da177e4SLinus Torvalds static int get_mem_for_virtual_node(struct tree_balance *tb) 20451da177e4SLinus Torvalds { 20461da177e4SLinus Torvalds int check_fs = 0; 20471da177e4SLinus Torvalds int size; 20481da177e4SLinus Torvalds char *buf; 20491da177e4SLinus Torvalds 20501da177e4SLinus Torvalds size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path)); 20511da177e4SLinus Torvalds 20521da177e4SLinus Torvalds if (size > tb->vn_buf_size) { 20531da177e4SLinus Torvalds /* we have to allocate more memory for virtual node */ 20541da177e4SLinus Torvalds if (tb->vn_buf) { 20551da177e4SLinus Torvalds /* free memory allocated before */ 2056d739b42bSPekka Enberg kfree(tb->vn_buf); 20571da177e4SLinus Torvalds /* this is not needed if kfree is atomic */ 20581da177e4SLinus Torvalds check_fs = 1; 20591da177e4SLinus Torvalds } 20601da177e4SLinus Torvalds 20611da177e4SLinus Torvalds /* virtual node requires now more memory */ 20621da177e4SLinus Torvalds tb->vn_buf_size = size; 20631da177e4SLinus Torvalds 20641da177e4SLinus Torvalds /* get memory for virtual item */ 2065d739b42bSPekka Enberg buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN); 20661da177e4SLinus Torvalds if (!buf) { 20671da177e4SLinus Torvalds /* getting memory with GFP_KERNEL priority may involve 20681da177e4SLinus Torvalds balancing now (due to indirect_to_direct conversion on 20691da177e4SLinus Torvalds dcache shrinking). So, release path and collected 20701da177e4SLinus Torvalds resources here */ 20711da177e4SLinus Torvalds free_buffers_in_tb(tb); 2072d739b42bSPekka Enberg buf = kmalloc(size, GFP_NOFS); 20731da177e4SLinus Torvalds if (!buf) { 20741da177e4SLinus Torvalds tb->vn_buf_size = 0; 20751da177e4SLinus Torvalds } 20761da177e4SLinus Torvalds tb->vn_buf = buf; 20771da177e4SLinus Torvalds schedule(); 20781da177e4SLinus Torvalds return REPEAT_SEARCH; 20791da177e4SLinus Torvalds } 20801da177e4SLinus Torvalds 20811da177e4SLinus Torvalds tb->vn_buf = buf; 20821da177e4SLinus Torvalds } 20831da177e4SLinus Torvalds 20841da177e4SLinus Torvalds if (check_fs && FILESYSTEM_CHANGED_TB(tb)) 20851da177e4SLinus Torvalds return REPEAT_SEARCH; 20861da177e4SLinus Torvalds 20871da177e4SLinus Torvalds return CARRY_ON; 20881da177e4SLinus Torvalds } 20891da177e4SLinus Torvalds 20901da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 20911da177e4SLinus Torvalds static void tb_buffer_sanity_check(struct super_block *p_s_sb, 20921da177e4SLinus Torvalds struct buffer_head *p_s_bh, 2093bd4c625cSLinus Torvalds const char *descr, int level) 2094bd4c625cSLinus Torvalds { 20951da177e4SLinus Torvalds if (p_s_bh) { 20961da177e4SLinus Torvalds if (atomic_read(&(p_s_bh->b_count)) <= 0) { 20971da177e4SLinus Torvalds 2098bd4c625cSLinus Torvalds reiserfs_panic(p_s_sb, 2099bd4c625cSLinus Torvalds "jmacd-1: tb_buffer_sanity_check(): negative or zero reference counter for buffer %s[%d] (%b)\n", 2100bd4c625cSLinus Torvalds descr, level, p_s_bh); 21011da177e4SLinus Torvalds } 21021da177e4SLinus Torvalds 21031da177e4SLinus Torvalds if (!buffer_uptodate(p_s_bh)) { 2104bd4c625cSLinus Torvalds reiserfs_panic(p_s_sb, 2105bd4c625cSLinus Torvalds "jmacd-2: tb_buffer_sanity_check(): buffer is not up to date %s[%d] (%b)\n", 2106bd4c625cSLinus Torvalds descr, level, p_s_bh); 21071da177e4SLinus Torvalds } 21081da177e4SLinus Torvalds 21091da177e4SLinus Torvalds if (!B_IS_IN_TREE(p_s_bh)) { 2110bd4c625cSLinus Torvalds reiserfs_panic(p_s_sb, 2111bd4c625cSLinus Torvalds "jmacd-3: tb_buffer_sanity_check(): buffer is not in tree %s[%d] (%b)\n", 2112bd4c625cSLinus Torvalds descr, level, p_s_bh); 21131da177e4SLinus Torvalds } 21141da177e4SLinus Torvalds 21151da177e4SLinus Torvalds if (p_s_bh->b_bdev != p_s_sb->s_bdev) { 2116bd4c625cSLinus Torvalds reiserfs_panic(p_s_sb, 2117bd4c625cSLinus Torvalds "jmacd-4: tb_buffer_sanity_check(): buffer has wrong device %s[%d] (%b)\n", 2118bd4c625cSLinus Torvalds descr, level, p_s_bh); 21191da177e4SLinus Torvalds } 21201da177e4SLinus Torvalds 21211da177e4SLinus Torvalds if (p_s_bh->b_size != p_s_sb->s_blocksize) { 2122bd4c625cSLinus Torvalds reiserfs_panic(p_s_sb, 2123bd4c625cSLinus Torvalds "jmacd-5: tb_buffer_sanity_check(): buffer has wrong blocksize %s[%d] (%b)\n", 2124bd4c625cSLinus Torvalds descr, level, p_s_bh); 21251da177e4SLinus Torvalds } 21261da177e4SLinus Torvalds 21271da177e4SLinus Torvalds if (p_s_bh->b_blocknr > SB_BLOCK_COUNT(p_s_sb)) { 2128bd4c625cSLinus Torvalds reiserfs_panic(p_s_sb, 2129bd4c625cSLinus Torvalds "jmacd-6: tb_buffer_sanity_check(): buffer block number too high %s[%d] (%b)\n", 2130bd4c625cSLinus Torvalds descr, level, p_s_bh); 21311da177e4SLinus Torvalds } 21321da177e4SLinus Torvalds } 21331da177e4SLinus Torvalds } 21341da177e4SLinus Torvalds #else 21351da177e4SLinus Torvalds static void tb_buffer_sanity_check(struct super_block *p_s_sb, 21361da177e4SLinus Torvalds struct buffer_head *p_s_bh, 21371da177e4SLinus Torvalds const char *descr, int level) 2138bd4c625cSLinus Torvalds {; 2139bd4c625cSLinus Torvalds } 21401da177e4SLinus Torvalds #endif 21411da177e4SLinus Torvalds 2142bd4c625cSLinus Torvalds static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh) 2143bd4c625cSLinus Torvalds { 21441da177e4SLinus Torvalds return reiserfs_prepare_for_journal(s, bh, 0); 21451da177e4SLinus Torvalds } 21461da177e4SLinus Torvalds 21471da177e4SLinus Torvalds static int wait_tb_buffers_until_unlocked(struct tree_balance *p_s_tb) 21481da177e4SLinus Torvalds { 21491da177e4SLinus Torvalds struct buffer_head *locked; 21501da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 21511da177e4SLinus Torvalds int repeat_counter = 0; 21521da177e4SLinus Torvalds #endif 21531da177e4SLinus Torvalds int i; 21541da177e4SLinus Torvalds 21551da177e4SLinus Torvalds do { 21561da177e4SLinus Torvalds 21571da177e4SLinus Torvalds locked = NULL; 21581da177e4SLinus Torvalds 2159bd4c625cSLinus Torvalds for (i = p_s_tb->tb_path->path_length; 2160bd4c625cSLinus Torvalds !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) { 21611da177e4SLinus Torvalds if (PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) { 21621da177e4SLinus Torvalds /* if I understand correctly, we can only be sure the last buffer 21631da177e4SLinus Torvalds ** in the path is in the tree --clm 21641da177e4SLinus Torvalds */ 21651da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 21661da177e4SLinus Torvalds if (PATH_PLAST_BUFFER(p_s_tb->tb_path) == 21671da177e4SLinus Torvalds PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) { 21681da177e4SLinus Torvalds tb_buffer_sanity_check(p_s_tb->tb_sb, 2169bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER 2170bd4c625cSLinus Torvalds (p_s_tb->tb_path, 2171bd4c625cSLinus Torvalds i), "S", 2172bd4c625cSLinus Torvalds p_s_tb->tb_path-> 2173bd4c625cSLinus Torvalds path_length - i); 21741da177e4SLinus Torvalds } 21751da177e4SLinus Torvalds #endif 21761da177e4SLinus Torvalds if (!clear_all_dirty_bits(p_s_tb->tb_sb, 2177bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER 2178bd4c625cSLinus Torvalds (p_s_tb->tb_path, 2179bd4c625cSLinus Torvalds i))) { 2180bd4c625cSLinus Torvalds locked = 2181bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER(p_s_tb->tb_path, 2182bd4c625cSLinus Torvalds i); 21831da177e4SLinus Torvalds } 21841da177e4SLinus Torvalds } 21851da177e4SLinus Torvalds } 21861da177e4SLinus Torvalds 2187bd4c625cSLinus Torvalds for (i = 0; !locked && i < MAX_HEIGHT && p_s_tb->insert_size[i]; 2188bd4c625cSLinus Torvalds i++) { 21891da177e4SLinus Torvalds 21901da177e4SLinus Torvalds if (p_s_tb->lnum[i]) { 21911da177e4SLinus Torvalds 21921da177e4SLinus Torvalds if (p_s_tb->L[i]) { 2193bd4c625cSLinus Torvalds tb_buffer_sanity_check(p_s_tb->tb_sb, 2194bd4c625cSLinus Torvalds p_s_tb->L[i], 2195bd4c625cSLinus Torvalds "L", i); 2196bd4c625cSLinus Torvalds if (!clear_all_dirty_bits 2197bd4c625cSLinus Torvalds (p_s_tb->tb_sb, p_s_tb->L[i])) 21981da177e4SLinus Torvalds locked = p_s_tb->L[i]; 21991da177e4SLinus Torvalds } 22001da177e4SLinus Torvalds 22011da177e4SLinus Torvalds if (!locked && p_s_tb->FL[i]) { 2202bd4c625cSLinus Torvalds tb_buffer_sanity_check(p_s_tb->tb_sb, 2203bd4c625cSLinus Torvalds p_s_tb->FL[i], 2204bd4c625cSLinus Torvalds "FL", i); 2205bd4c625cSLinus Torvalds if (!clear_all_dirty_bits 2206bd4c625cSLinus Torvalds (p_s_tb->tb_sb, p_s_tb->FL[i])) 22071da177e4SLinus Torvalds locked = p_s_tb->FL[i]; 22081da177e4SLinus Torvalds } 22091da177e4SLinus Torvalds 22101da177e4SLinus Torvalds if (!locked && p_s_tb->CFL[i]) { 2211bd4c625cSLinus Torvalds tb_buffer_sanity_check(p_s_tb->tb_sb, 2212bd4c625cSLinus Torvalds p_s_tb->CFL[i], 2213bd4c625cSLinus Torvalds "CFL", i); 2214bd4c625cSLinus Torvalds if (!clear_all_dirty_bits 2215bd4c625cSLinus Torvalds (p_s_tb->tb_sb, p_s_tb->CFL[i])) 22161da177e4SLinus Torvalds locked = p_s_tb->CFL[i]; 22171da177e4SLinus Torvalds } 22181da177e4SLinus Torvalds 22191da177e4SLinus Torvalds } 22201da177e4SLinus Torvalds 22211da177e4SLinus Torvalds if (!locked && (p_s_tb->rnum[i])) { 22221da177e4SLinus Torvalds 22231da177e4SLinus Torvalds if (p_s_tb->R[i]) { 2224bd4c625cSLinus Torvalds tb_buffer_sanity_check(p_s_tb->tb_sb, 2225bd4c625cSLinus Torvalds p_s_tb->R[i], 2226bd4c625cSLinus Torvalds "R", i); 2227bd4c625cSLinus Torvalds if (!clear_all_dirty_bits 2228bd4c625cSLinus Torvalds (p_s_tb->tb_sb, p_s_tb->R[i])) 22291da177e4SLinus Torvalds locked = p_s_tb->R[i]; 22301da177e4SLinus Torvalds } 22311da177e4SLinus Torvalds 22321da177e4SLinus Torvalds if (!locked && p_s_tb->FR[i]) { 2233bd4c625cSLinus Torvalds tb_buffer_sanity_check(p_s_tb->tb_sb, 2234bd4c625cSLinus Torvalds p_s_tb->FR[i], 2235bd4c625cSLinus Torvalds "FR", i); 2236bd4c625cSLinus Torvalds if (!clear_all_dirty_bits 2237bd4c625cSLinus Torvalds (p_s_tb->tb_sb, p_s_tb->FR[i])) 22381da177e4SLinus Torvalds locked = p_s_tb->FR[i]; 22391da177e4SLinus Torvalds } 22401da177e4SLinus Torvalds 22411da177e4SLinus Torvalds if (!locked && p_s_tb->CFR[i]) { 2242bd4c625cSLinus Torvalds tb_buffer_sanity_check(p_s_tb->tb_sb, 2243bd4c625cSLinus Torvalds p_s_tb->CFR[i], 2244bd4c625cSLinus Torvalds "CFR", i); 2245bd4c625cSLinus Torvalds if (!clear_all_dirty_bits 2246bd4c625cSLinus Torvalds (p_s_tb->tb_sb, p_s_tb->CFR[i])) 22471da177e4SLinus Torvalds locked = p_s_tb->CFR[i]; 22481da177e4SLinus Torvalds } 22491da177e4SLinus Torvalds } 22501da177e4SLinus Torvalds } 22511da177e4SLinus Torvalds /* as far as I can tell, this is not required. The FEB list seems 22521da177e4SLinus Torvalds ** to be full of newly allocated nodes, which will never be locked, 22531da177e4SLinus Torvalds ** dirty, or anything else. 22541da177e4SLinus Torvalds ** To be safe, I'm putting in the checks and waits in. For the moment, 22551da177e4SLinus Torvalds ** they are needed to keep the code in journal.c from complaining 22561da177e4SLinus Torvalds ** about the buffer. That code is inside CONFIG_REISERFS_CHECK as well. 22571da177e4SLinus Torvalds ** --clm 22581da177e4SLinus Torvalds */ 22591da177e4SLinus Torvalds for (i = 0; !locked && i < MAX_FEB_SIZE; i++) { 22601da177e4SLinus Torvalds if (p_s_tb->FEB[i]) { 2261bd4c625cSLinus Torvalds if (!clear_all_dirty_bits 2262bd4c625cSLinus Torvalds (p_s_tb->tb_sb, p_s_tb->FEB[i])) 22631da177e4SLinus Torvalds locked = p_s_tb->FEB[i]; 22641da177e4SLinus Torvalds } 22651da177e4SLinus Torvalds } 22661da177e4SLinus Torvalds 22671da177e4SLinus Torvalds if (locked) { 22681da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 22691da177e4SLinus Torvalds repeat_counter++; 22701da177e4SLinus Torvalds if ((repeat_counter % 10000) == 0) { 2271*45b03d5eSJeff Mahoney reiserfs_warning(p_s_tb->tb_sb, "reiserfs-8200", 2272*45b03d5eSJeff Mahoney "too many iterations waiting " 2273*45b03d5eSJeff Mahoney "for buffer to unlock " 22741da177e4SLinus Torvalds "(%b)", locked); 22751da177e4SLinus Torvalds 22761da177e4SLinus Torvalds /* Don't loop forever. Try to recover from possible error. */ 22771da177e4SLinus Torvalds 2278bd4c625cSLinus Torvalds return (FILESYSTEM_CHANGED_TB(p_s_tb)) ? 2279bd4c625cSLinus Torvalds REPEAT_SEARCH : CARRY_ON; 22801da177e4SLinus Torvalds } 22811da177e4SLinus Torvalds #endif 22821da177e4SLinus Torvalds __wait_on_buffer(locked); 22831da177e4SLinus Torvalds if (FILESYSTEM_CHANGED_TB(p_s_tb)) { 22841da177e4SLinus Torvalds return REPEAT_SEARCH; 22851da177e4SLinus Torvalds } 22861da177e4SLinus Torvalds } 22871da177e4SLinus Torvalds 22881da177e4SLinus Torvalds } while (locked); 22891da177e4SLinus Torvalds 22901da177e4SLinus Torvalds return CARRY_ON; 22911da177e4SLinus Torvalds } 22921da177e4SLinus Torvalds 22931da177e4SLinus Torvalds /* Prepare for balancing, that is 22941da177e4SLinus Torvalds * get all necessary parents, and neighbors; 22951da177e4SLinus Torvalds * analyze what and where should be moved; 22961da177e4SLinus Torvalds * get sufficient number of new nodes; 22971da177e4SLinus Torvalds * Balancing will start only after all resources will be collected at a time. 22981da177e4SLinus Torvalds * 22991da177e4SLinus Torvalds * When ported to SMP kernels, only at the last moment after all needed nodes 23001da177e4SLinus Torvalds * are collected in cache, will the resources be locked using the usual 23011da177e4SLinus Torvalds * textbook ordered lock acquisition algorithms. Note that ensuring that 23021da177e4SLinus Torvalds * this code neither write locks what it does not need to write lock nor locks out of order 23031da177e4SLinus Torvalds * will be a pain in the butt that could have been avoided. Grumble grumble. -Hans 23041da177e4SLinus Torvalds * 23051da177e4SLinus Torvalds * fix is meant in the sense of render unchanging 23061da177e4SLinus Torvalds * 23071da177e4SLinus Torvalds * Latency might be improved by first gathering a list of what buffers are needed 23081da177e4SLinus Torvalds * and then getting as many of them in parallel as possible? -Hans 23091da177e4SLinus Torvalds * 23101da177e4SLinus Torvalds * Parameters: 23111da177e4SLinus Torvalds * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append) 23121da177e4SLinus Torvalds * tb tree_balance structure; 23131da177e4SLinus Torvalds * inum item number in S[h]; 23141da177e4SLinus Torvalds * pos_in_item - comment this if you can 23151da177e4SLinus Torvalds * ins_ih & ins_sd are used when inserting 23161da177e4SLinus Torvalds * Returns: 1 - schedule occurred while the function worked; 23171da177e4SLinus Torvalds * 0 - schedule didn't occur while the function worked; 23181da177e4SLinus Torvalds * -1 - if no_disk_space 23191da177e4SLinus Torvalds */ 23201da177e4SLinus Torvalds 2321bd4c625cSLinus Torvalds int fix_nodes(int n_op_mode, struct tree_balance *p_s_tb, struct item_head *p_s_ins_ih, // item head of item being inserted 23221da177e4SLinus Torvalds const void *data // inserted item or data to be pasted 2323bd4c625cSLinus Torvalds ) 2324bd4c625cSLinus Torvalds { 2325bd4c625cSLinus Torvalds int n_ret_value, n_h, n_item_num = PATH_LAST_POSITION(p_s_tb->tb_path); 23261da177e4SLinus Torvalds int n_pos_in_item; 23271da177e4SLinus Torvalds 23281da177e4SLinus Torvalds /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared 23291da177e4SLinus Torvalds ** during wait_tb_buffers_run 23301da177e4SLinus Torvalds */ 23311da177e4SLinus Torvalds int wait_tb_buffers_run = 0; 23321da177e4SLinus Torvalds struct buffer_head *p_s_tbS0 = PATH_PLAST_BUFFER(p_s_tb->tb_path); 23331da177e4SLinus Torvalds 23341da177e4SLinus Torvalds ++REISERFS_SB(p_s_tb->tb_sb)->s_fix_nodes; 23351da177e4SLinus Torvalds 23361da177e4SLinus Torvalds n_pos_in_item = p_s_tb->tb_path->pos_in_item; 23371da177e4SLinus Torvalds 23381da177e4SLinus Torvalds p_s_tb->fs_gen = get_generation(p_s_tb->tb_sb); 23391da177e4SLinus Torvalds 23401da177e4SLinus Torvalds /* we prepare and log the super here so it will already be in the 23411da177e4SLinus Torvalds ** transaction when do_balance needs to change it. 23421da177e4SLinus Torvalds ** This way do_balance won't have to schedule when trying to prepare 23431da177e4SLinus Torvalds ** the super for logging 23441da177e4SLinus Torvalds */ 23451da177e4SLinus Torvalds reiserfs_prepare_for_journal(p_s_tb->tb_sb, 23461da177e4SLinus Torvalds SB_BUFFER_WITH_SB(p_s_tb->tb_sb), 1); 23471da177e4SLinus Torvalds journal_mark_dirty(p_s_tb->transaction_handle, p_s_tb->tb_sb, 23481da177e4SLinus Torvalds SB_BUFFER_WITH_SB(p_s_tb->tb_sb)); 23491da177e4SLinus Torvalds if (FILESYSTEM_CHANGED_TB(p_s_tb)) 23501da177e4SLinus Torvalds return REPEAT_SEARCH; 23511da177e4SLinus Torvalds 23521da177e4SLinus Torvalds /* if it possible in indirect_to_direct conversion */ 23531da177e4SLinus Torvalds if (buffer_locked(p_s_tbS0)) { 23541da177e4SLinus Torvalds __wait_on_buffer(p_s_tbS0); 23551da177e4SLinus Torvalds if (FILESYSTEM_CHANGED_TB(p_s_tb)) 23561da177e4SLinus Torvalds return REPEAT_SEARCH; 23571da177e4SLinus Torvalds } 23581da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 23591da177e4SLinus Torvalds if (cur_tb) { 23601da177e4SLinus Torvalds print_cur_tb("fix_nodes"); 2361bd4c625cSLinus Torvalds reiserfs_panic(p_s_tb->tb_sb, 2362bd4c625cSLinus Torvalds "PAP-8305: fix_nodes: there is pending do_balance"); 23631da177e4SLinus Torvalds } 23641da177e4SLinus Torvalds 23651da177e4SLinus Torvalds if (!buffer_uptodate(p_s_tbS0) || !B_IS_IN_TREE(p_s_tbS0)) { 2366bd4c625cSLinus Torvalds reiserfs_panic(p_s_tb->tb_sb, 2367bd4c625cSLinus Torvalds "PAP-8320: fix_nodes: S[0] (%b %z) is not uptodate " 2368bd4c625cSLinus Torvalds "at the beginning of fix_nodes or not in tree (mode %c)", 2369bd4c625cSLinus Torvalds p_s_tbS0, p_s_tbS0, n_op_mode); 23701da177e4SLinus Torvalds } 23711da177e4SLinus Torvalds 23721da177e4SLinus Torvalds /* Check parameters. */ 23731da177e4SLinus Torvalds switch (n_op_mode) { 23741da177e4SLinus Torvalds case M_INSERT: 23751da177e4SLinus Torvalds if (n_item_num <= 0 || n_item_num > B_NR_ITEMS(p_s_tbS0)) 2376bd4c625cSLinus Torvalds reiserfs_panic(p_s_tb->tb_sb, 2377bd4c625cSLinus Torvalds "PAP-8330: fix_nodes: Incorrect item number %d (in S0 - %d) in case of insert", 23781da177e4SLinus Torvalds n_item_num, B_NR_ITEMS(p_s_tbS0)); 23791da177e4SLinus Torvalds break; 23801da177e4SLinus Torvalds case M_PASTE: 23811da177e4SLinus Torvalds case M_DELETE: 23821da177e4SLinus Torvalds case M_CUT: 23831da177e4SLinus Torvalds if (n_item_num < 0 || n_item_num >= B_NR_ITEMS(p_s_tbS0)) { 23841da177e4SLinus Torvalds print_block(p_s_tbS0, 0, -1, -1); 2385bd4c625cSLinus Torvalds reiserfs_panic(p_s_tb->tb_sb, 2386bd4c625cSLinus Torvalds "PAP-8335: fix_nodes: Incorrect item number(%d); mode = %c insert_size = %d\n", 2387bd4c625cSLinus Torvalds n_item_num, n_op_mode, 2388bd4c625cSLinus Torvalds p_s_tb->insert_size[0]); 23891da177e4SLinus Torvalds } 23901da177e4SLinus Torvalds break; 23911da177e4SLinus Torvalds default: 2392bd4c625cSLinus Torvalds reiserfs_panic(p_s_tb->tb_sb, 2393bd4c625cSLinus Torvalds "PAP-8340: fix_nodes: Incorrect mode of operation"); 23941da177e4SLinus Torvalds } 23951da177e4SLinus Torvalds #endif 23961da177e4SLinus Torvalds 23971da177e4SLinus Torvalds if (get_mem_for_virtual_node(p_s_tb) == REPEAT_SEARCH) 23981da177e4SLinus Torvalds // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat 23991da177e4SLinus Torvalds return REPEAT_SEARCH; 24001da177e4SLinus Torvalds 24011da177e4SLinus Torvalds /* Starting from the leaf level; for all levels n_h of the tree. */ 24021da177e4SLinus Torvalds for (n_h = 0; n_h < MAX_HEIGHT && p_s_tb->insert_size[n_h]; n_h++) { 24031da177e4SLinus Torvalds if ((n_ret_value = get_direct_parent(p_s_tb, n_h)) != CARRY_ON) { 24041da177e4SLinus Torvalds goto repeat; 24051da177e4SLinus Torvalds } 24061da177e4SLinus Torvalds 2407bd4c625cSLinus Torvalds if ((n_ret_value = 2408bd4c625cSLinus Torvalds check_balance(n_op_mode, p_s_tb, n_h, n_item_num, 2409bd4c625cSLinus Torvalds n_pos_in_item, p_s_ins_ih, 2410bd4c625cSLinus Torvalds data)) != CARRY_ON) { 24111da177e4SLinus Torvalds if (n_ret_value == NO_BALANCING_NEEDED) { 24121da177e4SLinus Torvalds /* No balancing for higher levels needed. */ 2413bd4c625cSLinus Torvalds if ((n_ret_value = 2414bd4c625cSLinus Torvalds get_neighbors(p_s_tb, n_h)) != CARRY_ON) { 24151da177e4SLinus Torvalds goto repeat; 24161da177e4SLinus Torvalds } 24171da177e4SLinus Torvalds if (n_h != MAX_HEIGHT - 1) 24181da177e4SLinus Torvalds p_s_tb->insert_size[n_h + 1] = 0; 24191da177e4SLinus Torvalds /* ok, analysis and resource gathering are complete */ 24201da177e4SLinus Torvalds break; 24211da177e4SLinus Torvalds } 24221da177e4SLinus Torvalds goto repeat; 24231da177e4SLinus Torvalds } 24241da177e4SLinus Torvalds 24251da177e4SLinus Torvalds if ((n_ret_value = get_neighbors(p_s_tb, n_h)) != CARRY_ON) { 24261da177e4SLinus Torvalds goto repeat; 24271da177e4SLinus Torvalds } 24281da177e4SLinus Torvalds 24291da177e4SLinus Torvalds if ((n_ret_value = get_empty_nodes(p_s_tb, n_h)) != CARRY_ON) { 24301da177e4SLinus Torvalds goto repeat; /* No disk space, or schedule occurred and 24311da177e4SLinus Torvalds analysis may be invalid and needs to be redone. */ 24321da177e4SLinus Torvalds } 24331da177e4SLinus Torvalds 24341da177e4SLinus Torvalds if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h)) { 24351da177e4SLinus Torvalds /* We have a positive insert size but no nodes exist on this 24361da177e4SLinus Torvalds level, this means that we are creating a new root. */ 24371da177e4SLinus Torvalds 24381da177e4SLinus Torvalds RFALSE(p_s_tb->blknum[n_h] != 1, 24391da177e4SLinus Torvalds "PAP-8350: creating new empty root"); 24401da177e4SLinus Torvalds 24411da177e4SLinus Torvalds if (n_h < MAX_HEIGHT - 1) 24421da177e4SLinus Torvalds p_s_tb->insert_size[n_h + 1] = 0; 2443bd4c625cSLinus Torvalds } else if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1)) { 24441da177e4SLinus Torvalds if (p_s_tb->blknum[n_h] > 1) { 24451da177e4SLinus Torvalds /* The tree needs to be grown, so this node S[n_h] 24461da177e4SLinus Torvalds which is the root node is split into two nodes, 24471da177e4SLinus Torvalds and a new node (S[n_h+1]) will be created to 24481da177e4SLinus Torvalds become the root node. */ 24491da177e4SLinus Torvalds 24501da177e4SLinus Torvalds RFALSE(n_h == MAX_HEIGHT - 1, 24511da177e4SLinus Torvalds "PAP-8355: attempt to create too high of a tree"); 24521da177e4SLinus Torvalds 2453bd4c625cSLinus Torvalds p_s_tb->insert_size[n_h + 1] = 2454bd4c625cSLinus Torvalds (DC_SIZE + 2455bd4c625cSLinus Torvalds KEY_SIZE) * (p_s_tb->blknum[n_h] - 1) + 2456bd4c625cSLinus Torvalds DC_SIZE; 2457bd4c625cSLinus Torvalds } else if (n_h < MAX_HEIGHT - 1) 24581da177e4SLinus Torvalds p_s_tb->insert_size[n_h + 1] = 0; 2459bd4c625cSLinus Torvalds } else 2460bd4c625cSLinus Torvalds p_s_tb->insert_size[n_h + 1] = 2461bd4c625cSLinus Torvalds (DC_SIZE + KEY_SIZE) * (p_s_tb->blknum[n_h] - 1); 24621da177e4SLinus Torvalds } 24631da177e4SLinus Torvalds 24641da177e4SLinus Torvalds if ((n_ret_value = wait_tb_buffers_until_unlocked(p_s_tb)) == CARRY_ON) { 24651da177e4SLinus Torvalds if (FILESYSTEM_CHANGED_TB(p_s_tb)) { 24661da177e4SLinus Torvalds wait_tb_buffers_run = 1; 24671da177e4SLinus Torvalds n_ret_value = REPEAT_SEARCH; 24681da177e4SLinus Torvalds goto repeat; 24691da177e4SLinus Torvalds } else { 24701da177e4SLinus Torvalds return CARRY_ON; 24711da177e4SLinus Torvalds } 24721da177e4SLinus Torvalds } else { 24731da177e4SLinus Torvalds wait_tb_buffers_run = 1; 24741da177e4SLinus Torvalds goto repeat; 24751da177e4SLinus Torvalds } 24761da177e4SLinus Torvalds 24771da177e4SLinus Torvalds repeat: 24781da177e4SLinus Torvalds // fix_nodes was unable to perform its calculation due to 24791da177e4SLinus Torvalds // filesystem got changed under us, lack of free disk space or i/o 24801da177e4SLinus Torvalds // failure. If the first is the case - the search will be 24811da177e4SLinus Torvalds // repeated. For now - free all resources acquired so far except 24821da177e4SLinus Torvalds // for the new allocated nodes 24831da177e4SLinus Torvalds { 24841da177e4SLinus Torvalds int i; 24851da177e4SLinus Torvalds 24861da177e4SLinus Torvalds /* Release path buffers. */ 24871da177e4SLinus Torvalds if (wait_tb_buffers_run) { 24881da177e4SLinus Torvalds pathrelse_and_restore(p_s_tb->tb_sb, p_s_tb->tb_path); 24891da177e4SLinus Torvalds } else { 24901da177e4SLinus Torvalds pathrelse(p_s_tb->tb_path); 24911da177e4SLinus Torvalds } 24921da177e4SLinus Torvalds /* brelse all resources collected for balancing */ 24931da177e4SLinus Torvalds for (i = 0; i < MAX_HEIGHT; i++) { 24941da177e4SLinus Torvalds if (wait_tb_buffers_run) { 2495bd4c625cSLinus Torvalds reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, 2496bd4c625cSLinus Torvalds p_s_tb->L[i]); 2497bd4c625cSLinus Torvalds reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, 2498bd4c625cSLinus Torvalds p_s_tb->R[i]); 2499bd4c625cSLinus Torvalds reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, 2500bd4c625cSLinus Torvalds p_s_tb->FL[i]); 2501bd4c625cSLinus Torvalds reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, 2502bd4c625cSLinus Torvalds p_s_tb->FR[i]); 2503bd4c625cSLinus Torvalds reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, 2504bd4c625cSLinus Torvalds p_s_tb-> 2505bd4c625cSLinus Torvalds CFL[i]); 2506bd4c625cSLinus Torvalds reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, 2507bd4c625cSLinus Torvalds p_s_tb-> 2508bd4c625cSLinus Torvalds CFR[i]); 25091da177e4SLinus Torvalds } 25101da177e4SLinus Torvalds 2511bd4c625cSLinus Torvalds brelse(p_s_tb->L[i]); 2512bd4c625cSLinus Torvalds p_s_tb->L[i] = NULL; 2513bd4c625cSLinus Torvalds brelse(p_s_tb->R[i]); 2514bd4c625cSLinus Torvalds p_s_tb->R[i] = NULL; 2515bd4c625cSLinus Torvalds brelse(p_s_tb->FL[i]); 2516bd4c625cSLinus Torvalds p_s_tb->FL[i] = NULL; 2517bd4c625cSLinus Torvalds brelse(p_s_tb->FR[i]); 2518bd4c625cSLinus Torvalds p_s_tb->FR[i] = NULL; 2519bd4c625cSLinus Torvalds brelse(p_s_tb->CFL[i]); 2520bd4c625cSLinus Torvalds p_s_tb->CFL[i] = NULL; 2521bd4c625cSLinus Torvalds brelse(p_s_tb->CFR[i]); 2522bd4c625cSLinus Torvalds p_s_tb->CFR[i] = NULL; 25231da177e4SLinus Torvalds } 25241da177e4SLinus Torvalds 25251da177e4SLinus Torvalds if (wait_tb_buffers_run) { 25261da177e4SLinus Torvalds for (i = 0; i < MAX_FEB_SIZE; i++) { 25271da177e4SLinus Torvalds if (p_s_tb->FEB[i]) { 2528bd4c625cSLinus Torvalds reiserfs_restore_prepared_buffer 2529bd4c625cSLinus Torvalds (p_s_tb->tb_sb, p_s_tb->FEB[i]); 25301da177e4SLinus Torvalds } 25311da177e4SLinus Torvalds } 25321da177e4SLinus Torvalds } 25331da177e4SLinus Torvalds return n_ret_value; 25341da177e4SLinus Torvalds } 25351da177e4SLinus Torvalds 25361da177e4SLinus Torvalds } 25371da177e4SLinus Torvalds 25381da177e4SLinus Torvalds /* Anatoly will probably forgive me renaming p_s_tb to tb. I just 25391da177e4SLinus Torvalds wanted to make lines shorter */ 25401da177e4SLinus Torvalds void unfix_nodes(struct tree_balance *tb) 25411da177e4SLinus Torvalds { 25421da177e4SLinus Torvalds int i; 25431da177e4SLinus Torvalds 25441da177e4SLinus Torvalds /* Release path buffers. */ 25451da177e4SLinus Torvalds pathrelse_and_restore(tb->tb_sb, tb->tb_path); 25461da177e4SLinus Torvalds 25471da177e4SLinus Torvalds /* brelse all resources collected for balancing */ 25481da177e4SLinus Torvalds for (i = 0; i < MAX_HEIGHT; i++) { 25491da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]); 25501da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]); 25511da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]); 25521da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]); 25531da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]); 25541da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]); 25551da177e4SLinus Torvalds 25561da177e4SLinus Torvalds brelse(tb->L[i]); 25571da177e4SLinus Torvalds brelse(tb->R[i]); 25581da177e4SLinus Torvalds brelse(tb->FL[i]); 25591da177e4SLinus Torvalds brelse(tb->FR[i]); 25601da177e4SLinus Torvalds brelse(tb->CFL[i]); 25611da177e4SLinus Torvalds brelse(tb->CFR[i]); 25621da177e4SLinus Torvalds } 25631da177e4SLinus Torvalds 25641da177e4SLinus Torvalds /* deal with list of allocated (used and unused) nodes */ 25651da177e4SLinus Torvalds for (i = 0; i < MAX_FEB_SIZE; i++) { 25661da177e4SLinus Torvalds if (tb->FEB[i]) { 25671da177e4SLinus Torvalds b_blocknr_t blocknr = tb->FEB[i]->b_blocknr; 25681da177e4SLinus Torvalds /* de-allocated block which was not used by balancing and 25691da177e4SLinus Torvalds bforget about buffer for it */ 25701da177e4SLinus Torvalds brelse(tb->FEB[i]); 2571bd4c625cSLinus Torvalds reiserfs_free_block(tb->transaction_handle, NULL, 2572bd4c625cSLinus Torvalds blocknr, 0); 25731da177e4SLinus Torvalds } 25741da177e4SLinus Torvalds if (tb->used[i]) { 25751da177e4SLinus Torvalds /* release used as new nodes including a new root */ 25761da177e4SLinus Torvalds brelse(tb->used[i]); 25771da177e4SLinus Torvalds } 25781da177e4SLinus Torvalds } 25791da177e4SLinus Torvalds 2580d739b42bSPekka Enberg kfree(tb->vn_buf); 25811da177e4SLinus Torvalds 25821da177e4SLinus Torvalds } 2583