| blob | 2706e2adffab2df85da09f8884f68f38d5b9a747 |
1 /*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
5 /**
6 ** old_item_num
7 ** old_entry_num
8 ** set_entry_sizes
9 ** create_virtual_node
10 ** check_left
11 ** check_right
12 ** directory_part_size
13 ** get_num_ver
14 ** set_parameters
15 ** is_leaf_removable
16 ** are_leaves_removable
17 ** get_empty_nodes
18 ** get_lfree
19 ** get_rfree
20 ** is_left_neighbor_in_cache
21 ** decrement_key
22 ** get_far_parent
23 ** get_parents
24 ** can_node_be_removed
25 ** ip_check_balance
26 ** dc_check_balance_internal
27 ** dc_check_balance_leaf
28 ** dc_check_balance
29 ** check_balance
30 ** get_direct_parent
31 ** get_neighbors
32 ** fix_nodes
33 **
34 **
35 **/
37 #include <linux/config.h>
38 #include <linux/time.h>
39 #include <linux/string.h>
40 #include <linux/reiserfs_fs.h>
41 #include <linux/buffer_head.h>
43 /* To make any changes in the tree we find a node, that contains item
44 to be changed/deleted or position in the node we insert a new item
45 to. We call this node S. To do balancing we need to decide what we
46 will shift to left/right neighbor, or to a new node, where new item
47 will be etc. To make this analysis simpler we build virtual
48 node. Virtual node is an array of items, that will replace items of
49 node S. (For instance if we are going to delete an item, virtual
50 node does not contain it). Virtual node keeps information about
51 item sizes and types, mergeability of first and last items, sizes
52 of all entries in directory item. We use this array of items when
53 calculating what we can shift to neighbors and how many nodes we
54 have to have if we do not any shiftings, if we shift to left/right
55 neighbor or to both. */
57 /* taking item number in virtual node, returns number of item, that it has in source buffer */
59 {
69 }
73 mode);
74 /* delete mode */
76 }
79 {
87 /* size of changed node */
91 /* for internal nodes array if virtual items is not created */
95 }
97 /* number of items in virtual node */
102 /* first virtual item */
107 /* first item in the node */
110 /* define the mergeability for 0-th item (if it is not being deleted) */
115 /* go through all items those remain in the virtual node (except for the new (inserted) one) */
125 /* get item number in source node */
134 // FIXME: there is no check, that item operation did not
135 // consume too much memory
140 "vs-8030: create_virtual_node: "
144 /* this is not being changed */
150 }
151 }
153 /* virtual inserted item is not defined yet */
166 }
168 /* set right merge flag we take right delimiting key and check whether it is a mergeable item */
177 VI_TYPE_RIGHT_MERGEABLE;
179 #ifdef CONFIG_REISERFS_CHECK
183 /* we delete last item and it could be merged with right neighbor's first item */
188 /* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */
195 /* we can delete directory item, that has only one directory entry in it */
196 ;
197 }
198 #endif
200 }
201 }
203 /* using virtual node check, how many items can be shifted to left
204 neighbor */
206 {
214 /* internal level */
218 }
220 /* leaf level */
223 /* no free space or nothing to move */
227 }
236 /* all contents of S[0] fits into L[0] */
244 }
248 /* first item may be merge with last item in left neighbor */
257 /* the item can be shifted entirely */
261 }
263 /* the item cannot be shifted entirely, try to split it */
264 /* check whether L[0] can hold ih and at least one byte of the item body */
266 /* cannot shift even a part of the current item */
269 }
274 /* count partially shifted item */
278 }
281 }
283 /* using virtual node check, how many items can be shifted to right
284 neighbor */
286 {
294 /* internal level */
298 }
300 /* leaf level */
303 /* no free space */
307 }
316 /* all contents of S[0] fits into R[0] */
324 }
328 /* last item may be merge with first item in right neighbor */
337 /* the item can be shifted entirely */
341 }
343 /* check whether R[0] can hold ih and at least one byte of the item body */
347 }
349 /* R[0] can hold the header of the item and at least one byte of its body */
354 /* count partially shifted item */
358 }
361 }
363 /*
364 * from - number of items, which are shifted to left neighbor entirely
365 * to - number of item, which are shifted to right neighbor entirely
366 * from_bytes - number of bytes of boundary item (or directory entries) which are shifted to left neighbor
367 * to_bytes - number of bytes of boundary item (or directory entries) which are shifted to right neighbor */
371 {
374 // int bytes;
377 // struct virtual_item * vi;
384 we do not include into node that is being filled */
386 we do node include into node that is being filled */
388 items, that are split between S[0] and
389 S1new and S1new and S2new */
394 /* We only create additional nodes if we are in insert or paste mode
395 or we are in replace mode at the internal level. If h is 0 and
396 the mode is M_REPLACE then in fix_nodes we change the mode to
397 paste or insert before we get here in the code. */
403 /* snum012 [0-2] - number of items, that lay
404 to S[0], first new node and second new node */
408 /* internal level */
414 }
416 /* leaf level */
421 // start from 'from'-th item
423 // skip its first 'start_bytes' units
426 // last included item is the 'end_item'-th one
428 // do not count last 'end_bytes' units of 'end_item'-th item
431 /* go through all item beginning from the start_item-th item and ending by
432 the end_item-th item. Do not count first 'start_bytes' units of
433 'start_item'-th item and last 'end_bytes' of 'end_item'-th item */
441 /* get size of current item */
444 /* do not take in calculation head part (from_bytes) of from-th item */
445 current_item_size -=
448 /* do not take in calculation tail part of last item */
449 current_item_size -=
452 /* if item fits into current node entierly */
458 }
461 /* virtual item length is longer, than max size of item in
462 a node. It is impossible for direct item */
464 "vs-8110: "
467 /* we will try to split it */
469 }
472 /* as we do not split items, take new node and continue */
473 needed_nodes++;
474 i--;
477 }
478 // calculate number of item units which fit into node being
479 // filled
480 {
484 units =
486 skip_from_end);
488 /* nothing fits into current node, take new node and continue */
491 }
492 }
494 /* something fits into the current node */
495 //if (snum012[3] != -1 || needed_nodes != 1)
496 // reiserfs_panic (tb->tb_sb, "vs-8115: get_num_ver: too many nodes required");
497 //snum012[needed_nodes - 1 + 3] = op_unit_num (vi) - start_bytes - units;
506 needed_nodes++;
507 /* continue from the same item with start_bytes != -1 */
509 i--;
511 }
513 // sum012[4] (if it is not -1) contains number of units of which
514 // are to be in S1new, snum012[3] - to be in S0. They are supposed
515 // to be S1bytes and S2bytes correspondingly, so recalculate
522 bytes_to_l =
525 bytes_to_r =
528 bytes_to_S1new =
532 // s2bytes
541 }
543 /* now we know S2bytes, calculate S1bytes */
550 bytes_to_l =
553 bytes_to_r =
556 bytes_to_S2new =
560 // s1bytes
564 }
567 }
569 #ifdef CONFIG_REISERFS_CHECK
571 #endif
573 /* Set parameters for balancing.
574 * Performs write of results of analysis of balancing into structure tb,
575 * where it will later be used by the functions that actually do the balancing.
576 * Parameters:
577 * tb tree_balance structure;
578 * h current level of the node;
579 * lnum number of items from S[h] that must be shifted to L[h];
580 * rnum number of items from S[h] that must be shifted to R[h];
581 * blk_num number of blocks that S[h] will be splitted into;
582 * s012 number of items that fall into splitted nodes.
583 * lbytes number of bytes which flow to the left neighbor from the item that is not
584 * not shifted entirely
585 * rbytes number of bytes which flow to the right neighbor from the item that is not
586 * not shifted entirely
587 * s1bytes number of bytes which flow to the first new node when S[0] splits (this number is contained in s012 array)
588 */
592 {
604 }
607 }
613 }
615 /* check, does node disappear if we shift tb->lnum[0] items to left
616 neighbor and tb->rnum[0] to the right one. */
618 {
624 /* number of items, that will be shifted to left (right) neighbor
625 entirely */
630 /* how many items remain in S[0] after shiftings to neighbors */
634 /* all content of node can be shifted to neighbors */
638 }
641 /* S[0] is not removable */
644 /* check, whether we can divide 1 remaining item between neighbors */
646 /* get size of remaining item (in item units) */
653 }
656 }
658 /* check whether L, S, R can be joined in one node */
660 {
676 /* there was only one item and it will be deleted */
689 /* Directory must be in correct state here: that is
690 somewhere at the left side should exist first directory
691 item. But the item being deleted can not be that first
692 one because its right neighbor is item of the same
693 directory. (But first item always gets deleted in last
694 turn). So, neighbors of deleted item can be merged, so
695 we can save ih_size */
698 /* we might check that left neighbor exists and is of the
699 same directory */
702 }
704 }
710 }
713 }
715 /* when we do not split item, lnum and rnum are numbers of entire items */
716 #define SET_PAR_SHIFT_LEFT \
717 if (h)\
718 {\
719 int to_l;\
720 \
721 to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
722 (MAX_NR_KEY(Sh) + 1 - lpar);\
723 \
724 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
725 }\
726 else \
727 {\
728 if (lset==LEFT_SHIFT_FLOW)\
729 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
730 tb->lbytes, -1);\
731 else\
732 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
733 -1, -1);\
734 }
736 #define SET_PAR_SHIFT_RIGHT \
737 if (h)\
738 {\
739 int to_r;\
740 \
741 to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
742 \
743 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
744 }\
745 else \
746 {\
747 if (rset==RIGHT_SHIFT_FLOW)\
748 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
749 -1, tb->rbytes);\
750 else\
751 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
752 -1, -1);\
753 }
756 {
774 }
775 }
777 /* Get new buffers for storing new nodes that are created while balancing.
778 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
779 * CARRY_ON - schedule didn't occur while the function worked;
780 * NO_DISK_SPACE - no disk space.
781 */
782 /* The function is NOT SCHEDULE-SAFE! */
784 {
792 /* number_of_freeblk is the number of empty blocks which have been
793 acquired for use by the balancing algorithm minus the number of
794 empty blocks used in the previous levels of the analysis,
795 number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs
796 after empty blocks are acquired, and the balancing analysis is
797 then restarted, amount_needed is the number needed by this level
798 (n_h) of the balancing analysis.
800 Note that for systems with many processes writing, it would be
801 more layout optimal to calculate the total number needed by all
802 levels and then to run reiserfs_new_blocks to get all of them at once. */
804 /* Initiate number_of_freeblk to the amount acquired prior to the restart of
805 the analysis or 0 if not restarted, then subtract the amount needed
806 by all of the levels of the tree below n_h. */
807 /* blknum includes S[n_h], so we subtract 1 in this calculation */
810 n_number_of_freeblk -=
814 /* Allocate missing empty blocks. */
815 /* if p_s_Sh == 0 then we are getting a new root */
817 /* Amount_needed = the amount that we need more than the amount that we have. */
823 /* No need to check quota - is not allocated for blocks used for formatted nodes */
828 /* for each blocknumber we just got, get a buffer and stick it on FEB */
840 p_s_new_bh);
842 /* Put empty buffers into the array. */
848 }
854 }
856 /* Get free space of the left neighbor, which is stored in the parent
857 * node of the left neighbor. */
859 {
871 }
874 }
876 /* Get free space of the right neighbor,
877 * which is stored in the parent node of the right neighbor.
878 */
880 {
892 }
896 }
898 /* Check whether left neighbor is in memory. */
900 {
903 b_blocknr_t n_left_neighbor_blocknr;
909 /* Calculate father of the node to be balanced. */
920 /* Get position of the pointer to the left neighbor into the left father. */
923 /* Get left neighbor block number. */
924 n_left_neighbor_blocknr =
926 /* Look for the left neighbor in the cache. */
934 }
937 }
943 {
944 // call item specific function for this key
946 }
948 /* Calculate far left/right parent of the left/right neighbor of the current node, that
949 * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h].
950 * Calculate left/right common parent of the current node and L[h]/R[h].
951 * Calculate left/right delimiting key position.
952 * Returns: PATH_INCORRECT - path in the tree is not correct;
953 SCHEDULE_OCCURRED - schedule occurred while the function worked;
954 * CARRY_ON - schedule didn't occur while the function worked;
955 */
960 {
970 /* Starting from F[n_h] go upwards in the tree, and look for the common
971 ancestor of F[n_h], and its neighbor l/r, that should be obtained. */
979 /* Check whether parent of the current buffer in the path is really parent in the tree. */
983 /* Check whether position in the parent is correct. */
989 /* Check whether parent at the path really points to the child. */
993 /* Return delimiting key if position in the parent is not equal to first/last one. */
999 /*(*pp_s_com_father = p_s_parent)->b_count++; */
1001 }
1002 }
1004 /* if we are in the root of the tree, then there is no common father */
1006 /* Check whether first buffer in the path is the root of the tree. */
1013 }
1015 }
1021 /* Check whether the common parent is locked. */
1028 }
1029 }
1031 /* So, we got common parent of the current node and its left/right neighbor.
1032 Now we are geting the parent of the left/right neighbor. */
1034 /* Form key to get parent of the left/right neighbor. */
1039 n_position -
1042 n_position)));
1050 // path is released
1057 }
1069 }
1071 /* Get parents of neighbors of node in the path(S[n_path_offset]) and common parents of
1072 * S[n_path_offset] and L[n_path_offset]/R[n_path_offset]: F[n_path_offset], FL[n_path_offset],
1073 * FR[n_path_offset], CFL[n_path_offset], CFR[n_path_offset].
1074 * Calculate numbers of left and right delimiting keys position: lkey[n_path_offset], rkey[n_path_offset].
1075 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1076 * CARRY_ON - schedule didn't occur while the function worked;
1077 */
1079 {
1082 n_ret_value,
1086 /* Current node is the root of the tree or will be root of the tree */
1088 /* The root can not have parents.
1089 Release nodes which previously were obtained as parents of the current node neighbors. */
1097 }
1099 /* Get parent FL[n_path_offset] of L[n_path_offset]. */
1101 /* Current node is not the first child of its parent. */
1102 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1109 /* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node.
1110 Calculate current common parent of L[n_path_offset] and the current node. Note that
1111 CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset].
1112 Calculate lkey[n_path_offset]. */
1117 }
1128 /* Get parent FR[n_h] of R[n_h]. */
1130 /* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */
1132 /* Calculate current parent of R[n_h], which is the right neighbor of F[n_h].
1133 Calculate current common parent of R[n_h] and current node. Note that CFR[n_h]
1134 not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */
1140 /* Current node is not the last child of its parent F[n_h]. */
1141 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1147 }
1160 }
1162 /* it is possible to remove node as result of shiftings to
1163 neighbors even when we insert or paste item. */
1166 {
1177 /* shifting may merge items which might save space */
1178 -
1179 ((!h
1181 -
1185 /* node can not be removed */
1193 }
1194 }
1197 }
1199 /* Check whether current node S[h] is balanced when increasing its size by
1200 * Inserting or Pasting.
1201 * Calculate parameters for balancing for current level h.
1202 * Parameters:
1203 * tb tree_balance structure;
1204 * h current level of the node;
1205 * inum item number in S[h];
1206 * mode i - insert, p - paste;
1207 * Returns: 1 - schedule occurred;
1208 * 0 - balancing for higher levels needed;
1209 * -1 - no balancing for higher levels needed;
1210 * -2 - no disk space.
1211 */
1212 /* ip means Inserting or Pasting */
1214 {
1217 is negative if bytes are deleted) buffer which
1218 contains node being balanced. The mnemonic is
1219 that the attempted change in node space used level
1220 is levbytes bytes. */
1221 n_ret_value;
1225 /* nver is short for number of vertixes, and lnver is the number if
1226 we shift to the left, rnver is the number if we shift to the
1227 right, and lrnver is the number if we shift in both directions.
1228 The goal is to minimize first the number of vertixes, and second,
1229 the number of vertixes whose contents are changed by shifting,
1230 and third the number of uncached vertixes whose contents are
1231 changed by shifting and must be read from disk. */
1234 /* used at leaf level only, S0 = S[0] is the node being balanced,
1235 sInum [ I = 0,1,2 ] is the number of items that will
1236 remain in node SI after balancing. S1 and S2 are new
1237 nodes that might be created. */
1239 /* we perform 8 calls to get_num_ver(). For each call we calculate five parameters.
1240 where 4th parameter is s1bytes and 5th - s2bytes
1241 */
1243 0,1 - do not shift and do not shift but bottle
1244 2 - shift only whole item to left
1245 3 - shift to left and bottle as much as possible
1246 4,5 - shift to right (whole items and as much as possible
1247 6,7 - shift to both directions (whole items and as much as possible)
1248 */
1250 /* Sh is the node whose balance is currently being checked */
1256 /* Calculate balance parameters for creating new root. */
1272 }
1273 }
1280 /* get free space of neighbors */
1285 NO_BALANCING_NEEDED)
1286 /* and new item fits into node S[h] without any shifting */
1291 /*
1292 determine maximal number of items we can shift to the left neighbor (in tb structure)
1293 and the maximal number of bytes that can flow to the left neighbor
1294 from the left most liquid item that cannot be shifted from S[0] entirely (returned value)
1295 */
1298 /*
1299 determine maximal number of items we can shift to the right neighbor (in tb structure)
1300 and the maximal number of bytes that can flow to the right neighbor
1301 from the right most liquid item that cannot be shifted from S[0] entirely (returned value)
1302 */
1305 /* all contents of internal node S[h] can be moved into its
1306 neighbors, S[h] will be removed after balancing */
1310 /* Since we are working on internal nodes, and our internal
1311 nodes have fixed size entries, then we can balance by the
1312 number of items rather than the space they consume. In this
1313 routine we set the left node equal to the right node,
1314 allowing a difference of less than or equal to 1 child
1315 pointer. */
1316 to_r =
1323 }
1325 /* this checks balance condition, that any two neighboring nodes can not fit in one node */
1334 /* all contents of S[0] can be moved into its neighbors
1335 S[0] will be removed after balancing. */
1339 /* why do we perform this check here rather than earlier??
1340 Answer: we can win 1 node in some cases above. Moreover we
1341 checked it above, when we checked, that S[0] is not removable
1342 in principle */
1348 }
1350 {
1352 /*
1353 * regular overflowing of the node
1354 */
1356 /* get_num_ver works in 2 modes (FLOW & NO_FLOW)
1357 lpar, rpar - number of items we can shift to left/right neighbor (including splitting item)
1358 nset, lset, rset, lrset - shows, whether flowing items give better packing
1359 */
1360 #define FLOW 1
1363 /* we choose one the following */
1364 #define NOTHING_SHIFT_NO_FLOW 0
1365 #define NOTHING_SHIFT_FLOW 5
1366 #define LEFT_SHIFT_NO_FLOW 10
1367 #define LEFT_SHIFT_FLOW 15
1368 #define RIGHT_SHIFT_NO_FLOW 20
1369 #define RIGHT_SHIFT_FLOW 25
1370 #define LR_SHIFT_NO_FLOW 30
1371 #define LR_SHIFT_FLOW 35
1376 /* calculate number of blocks S[h] must be split into when
1377 nothing is shifted to the neighbors,
1378 as well as number of items in each part of the split node (s012 numbers),
1379 and number of bytes (s1bytes) of the shared drop which flow to S1 if any */
1388 /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */
1394 }
1396 /* calculate number of blocks S[h] must be split into when
1397 l_shift_num first items and l_shift_bytes of the right most
1398 liquid item to be shifted are shifted to the left neighbor,
1399 as well as number of items in each part of the splitted node (s012 numbers),
1400 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1401 */
1411 lpar -
1417 }
1419 /* calculate number of blocks S[h] must be split into when
1420 r_shift_num first items and r_shift_bytes of the left most
1421 liquid item to be shifted are shifted to the right neighbor,
1422 as well as number of items in each part of the splitted node (s012 numbers),
1423 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1424 */
1430 rbytes !=
1446 }
1448 /* calculate number of blocks S[h] must be split into when
1449 items are shifted in both directions,
1450 as well as number of items in each part of the splitted node (s012 numbers),
1451 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1452 */
1459 rbytes !=
1467 lpar -
1476 }
1478 /* Our general shifting strategy is:
1479 1) to minimized number of new nodes;
1480 2) to minimized number of neighbors involved in shifting;
1481 3) to minimized number of disk reads; */
1483 /* we can win TWO or ONE nodes by shifting in both directions */
1494 else
1503 }
1505 /* if shifting doesn't lead to better packing then don't shift */
1510 }
1512 /* now we know that for better packing shifting in only one
1513 direction either to the left or to the right is required */
1515 /* if shifting to the left is better than shifting to the right */
1517 SET_PAR_SHIFT_LEFT;
1519 }
1521 /* if shifting to the right is better than shifting to the left */
1523 SET_PAR_SHIFT_RIGHT;
1525 }
1527 /* now shifting in either direction gives the same number
1528 of nodes and we can make use of the cached neighbors */
1530 SET_PAR_SHIFT_LEFT;
1532 }
1534 /* shift to the right independently on whether the right neighbor in cache or not */
1535 SET_PAR_SHIFT_RIGHT;
1537 }
1538 }
1540 /* Check whether current node S[h] is balanced when Decreasing its size by
1541 * Deleting or Cutting for INTERNAL node of S+tree.
1542 * Calculate parameters for balancing for current level h.
1543 * Parameters:
1544 * tb tree_balance structure;
1545 * h current level of the node;
1546 * inum item number in S[h];
1547 * mode i - insert, p - paste;
1548 * Returns: 1 - schedule occurred;
1549 * 0 - balancing for higher levels needed;
1550 * -1 - no balancing for higher levels needed;
1551 * -2 - no disk space.
1552 *
1553 * Note: Items of internal nodes have fixed size, so the balance condition for
1554 * the internal part of S+tree is as for the B-trees.
1555 */
1557 {
1560 /* Sh is the node whose balance is currently being checked,
1561 and Fh is its father. */
1571 /* using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */
1572 /* new_nr_item = number of items node would have if operation is */
1573 /* performed without balancing (new_nr_item); */
1580 }
1581 /* new_nr_item == 0.
1582 * Current root will be deleted resulting in
1583 * decrementing the tree height. */
1586 }
1591 /* get free space of neighbors */
1595 /* determine maximal number of items we can fit into neighbors */
1600 * In this case we balance only if it leads to better packing. */
1602 * which is impossible with greater values of new_nr_item. */
1604 /* All contents of S[h] can be moved to L[h]. */
1608 order_L =
1611 h)) ==
1618 }
1621 /* All contents of S[h] can be moved to R[h]. */
1625 order_R =
1628 h)) ==
1635 }
1636 }
1639 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1642 to_r =
1649 }
1651 /* Balancing does not lead to better packing. */
1654 }
1656 /* Current node contain insufficient number of items. Balancing is required. */
1657 /* Check whether we can merge S[h] with left neighbor. */
1664 order_L =
1667 h)) ==
1670 KEY_SIZE);
1673 }
1675 /* Check whether we can merge S[h] with right neighbor. */
1680 order_R =
1685 KEY_SIZE);
1688 }
1690 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1694 to_r =
1701 }
1703 /* For internal nodes try to borrow item from a neighbor */
1706 /* Borrow one or two items from caching neighbor */
1710 from_l =
1715 }
1721 }
1723 /* Check whether current node S[h] is balanced when Decreasing its size by
1724 * Deleting or Truncating for LEAF node of S+tree.
1725 * Calculate parameters for balancing for current level h.
1726 * Parameters:
1727 * tb tree_balance structure;
1728 * h current level of the node;
1729 * inum item number in S[h];
1730 * mode i - insert, p - paste;
1731 * Returns: 1 - schedule occurred;
1732 * 0 - balancing for higher levels needed;
1733 * -1 - no balancing for higher levels needed;
1734 * -2 - no disk space.
1735 */
1737 {
1740 /* Number of bytes that must be deleted from
1741 (value is negative if bytes are deleted) buffer which
1742 contains node being balanced. The mnemonic is that the
1743 attempted change in node space used level is levbytes bytes. */
1745 /* the maximal item size */
1747 /* S0 is the node whose balance is currently being checked,
1748 and F0 is its father. */
1766 }
1771 /* get free space of neighbors */
1777 /* if 3 leaves can be merge to one, set parameters and return */
1781 /* determine maximal number of items we can shift to the left/right neighbor
1782 and the maximal number of bytes that can flow to the left/right neighbor
1783 from the left/right most liquid item that cannot be shifted from S[0] entirely
1784 */
1788 /* check whether we can merge S with left neighbor. */
1790 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 */
1796 /* set parameter to merge S[0] with its left neighbor */
1799 }
1801 /* check whether we can merge S[0] with right neighbor. */
1805 }
1807 /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
1811 /* Balancing is not required. */
1815 }
1817 /* Check whether current node S[h] is balanced when Decreasing its size by
1818 * Deleting or Cutting.
1819 * Calculate parameters for balancing for current level h.
1820 * Parameters:
1821 * tb tree_balance structure;
1822 * h current level of the node;
1823 * inum item number in S[h];
1824 * mode d - delete, c - cut.
1825 * Returns: 1 - schedule occurred;
1826 * 0 - balancing for higher levels needed;
1827 * -1 - no balancing for higher levels needed;
1828 * -2 - no disk space.
1829 */
1831 {
1837 else
1839 }
1841 /* Check whether current node S[h] is balanced.
1842 * Calculate parameters for balancing for current level h.
1843 * Parameters:
1844 *
1845 * tb tree_balance structure:
1846 *
1847 * tb is a large structure that must be read about in the header file
1848 * at the same time as this procedure if the reader is to successfully
1849 * understand this procedure
1850 *
1851 * h current level of the node;
1852 * inum item number in S[h];
1853 * mode i - insert, p - paste, d - delete, c - cut.
1854 * Returns: 1 - schedule occurred;
1855 * 0 - balancing for higher levels needed;
1856 * -1 - no balancing for higher levels needed;
1857 * -2 - no disk space.
1858 */
1865 {
1880 /* Calculate balance parameters when size of node is increasing. */
1883 /* Calculate balance parameters when size of node is decreasing. */
1885 }
1887 /* Check whether parent at the path is the really parent of the current node.*/
1889 {
1895 /* We are in the root or in the new root. */
1903 /* Root is not changed. */
1907 }
1909 }
1922 /* Parent in the path is not parent of the current node in the tree. */
1929 }
1932 }
1934 /* Using lnum[n_h] and rnum[n_h] we should determine what neighbors
1935 * of S[n_h] we
1936 * need in order to balance S[n_h], and get them if necessary.
1937 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1938 * CARRY_ON - schedule didn't occur while the function worked;
1939 */
1941 {
1951 /* We need left neighbor to balance S[n_h]. */
1959 n_child_position =
1971 }
1986 }
1994 n_path_offset) >=
1998 n_child_position =
2008 }
2020 }
2022 }
2024 #ifdef CONFIG_REISERFS_CHECK
2026 {
2038 }
2039 }
2041 }
2044 {
2053 }
2054 #endif
2057 {
2062 #define MIN_NAME_LEN 1
2072 }
2074 /* maybe we should fail balancing we are going to perform when kmalloc
2075 fails several times. But now it will loop until kmalloc gets
2076 required memory */
2078 {
2086 /* we have to allocate more memory for virtual node */
2088 /* free memory allocated before */
2090 /* this is not needed if kfree is atomic */
2092 }
2094 /* virtual node requires now more memory */
2097 /* get memory for virtual item */
2098 buf =
2102 /* getting memory with GFP_KERNEL priority may involve
2103 balancing now (due to indirect_to_direct conversion on
2104 dcache shrinking). So, release path and collected
2105 resources here */
2109 #ifdef CONFIG_REISERFS_CHECK
2111 "vs-8345: get_mem_for_virtual_node: "
2114 s_kmallocs);
2115 #endif
2117 }
2121 }
2124 }
2130 }
2132 #ifdef CONFIG_REISERFS_CHECK
2136 {
2141 "jmacd-1: tb_buffer_sanity_check(): negative or zero reference counter for buffer %s[%d] (%b)\n",
2143 }
2149 }
2155 }
2161 }
2167 }
2173 }
2174 }
2175 }
2176 #else
2180 {;
2181 }
2182 #endif
2185 {
2187 }
2190 {
2192 #ifdef CONFIG_REISERFS_CHECK
2194 #endif
2204 /* if I understand correctly, we can only be sure the last buffer
2205 ** in the path is in the tree --clm
2206 */
2207 #ifdef CONFIG_REISERFS_CHECK
2211 PATH_OFFSET_PBUFFER
2216 }
2217 #endif
2219 PATH_OFFSET_PBUFFER
2221 i))) {
2222 locked =
2224 i);
2225 }
2226 }
2227 }
2230 i++) {
2241 }
2250 }
2259 }
2261 }
2272 }
2281 }
2290 }
2291 }
2292 }
2293 /* as far as I can tell, this is not required. The FEB list seems
2294 ** to be full of newly allocated nodes, which will never be locked,
2295 ** dirty, or anything else.
2296 ** To be safe, I'm putting in the checks and waits in. For the moment,
2297 ** they are needed to keep the code in journal.c from complaining
2298 ** about the buffer. That code is inside CONFIG_REISERFS_CHECK as well.
2299 ** --clm
2300 */
2306 }
2307 }
2310 #ifdef CONFIG_REISERFS_CHECK
2311 repeat_counter++;
2314 "wait_tb_buffers_until_released(): too many "
2315 "iterations waiting for buffer to unlock "
2318 /* Don't loop forever. Try to recover from possible error. */
2322 }
2323 #endif
2327 }
2328 }
2333 }
2335 /* Prepare for balancing, that is
2336 * get all necessary parents, and neighbors;
2337 * analyze what and where should be moved;
2338 * get sufficient number of new nodes;
2339 * Balancing will start only after all resources will be collected at a time.
2340 *
2341 * When ported to SMP kernels, only at the last moment after all needed nodes
2342 * are collected in cache, will the resources be locked using the usual
2343 * textbook ordered lock acquisition algorithms. Note that ensuring that
2344 * this code neither write locks what it does not need to write lock nor locks out of order
2345 * will be a pain in the butt that could have been avoided. Grumble grumble. -Hans
2346 *
2347 * fix is meant in the sense of render unchanging
2348 *
2349 * Latency might be improved by first gathering a list of what buffers are needed
2350 * and then getting as many of them in parallel as possible? -Hans
2351 *
2352 * Parameters:
2353 * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2354 * tb tree_balance structure;
2355 * inum item number in S[h];
2356 * pos_in_item - comment this if you can
2357 * ins_ih & ins_sd are used when inserting
2358 * Returns: 1 - schedule occurred while the function worked;
2359 * 0 - schedule didn't occur while the function worked;
2360 * -1 - if no_disk_space
2361 */
2363 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
2365 )
2366 {
2370 /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared
2371 ** during wait_tb_buffers_run
2372 */
2382 /* we prepare and log the super here so it will already be in the
2383 ** transaction when do_balance needs to change it.
2384 ** This way do_balance won't have to schedule when trying to prepare
2385 ** the super for logging
2386 */
2394 /* if it possible in indirect_to_direct conversion */
2399 }
2400 #ifdef CONFIG_REISERFS_CHECK
2405 }
2409 "PAP-8320: fix_nodes: S[0] (%b %z) is not uptodate "
2412 }
2414 /* Check parameters. */
2431 }
2436 }
2437 #endif
2440 // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat
2443 /* Starting from the leaf level; for all levels n_h of the tree. */
2447 }
2454 /* No balancing for higher levels needed. */
2458 }
2461 /* ok, analysis and resource gathering are complete */
2463 }
2465 }
2469 }
2473 analysis may be invalid and needs to be redone. */
2474 }
2477 /* We have a positive insert size but no nodes exist on this
2478 level, this means that we are creating a new root. */
2487 /* The tree needs to be grown, so this node S[n_h]
2488 which is the root node is split into two nodes,
2489 and a new node (S[n_h+1]) will be created to
2490 become the root node. */
2498 DC_SIZE;
2504 }
2513 }
2517 }
2519 repeat:
2520 // fix_nodes was unable to perform its calculation due to
2521 // filesystem got changed under us, lack of free disk space or i/o
2522 // failure. If the first is the case - the search will be
2523 // repeated. For now - free all resources acquired so far except
2524 // for the new allocated nodes
2525 {
2528 /* Release path buffers. */
2533 }
2534 /* brelse all resources collected for balancing */
2546 p_s_tb->
2549 p_s_tb->
2551 }
2565 }
2570 reiserfs_restore_prepared_buffer
2572 }
2573 }
2574 }
2576 }
2578 }
2580 /* Anatoly will probably forgive me renaming p_s_tb to tb. I just
2581 wanted to make lines shorter */
2583 {
2586 /* Release path buffers. */
2589 /* brelse all resources collected for balancing */
2604 }
2606 /* deal with list of allocated (used and unused) nodes */
2610 /* de-allocated block which was not used by balancing and
2611 bforget about buffer for it */
2615 }
2617 /* release used as new nodes including a new root */
2619 }
2620 }
2625 }