| blob | 1170922241111c6278b04c61ac78f6584ae3826f |
1 /*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
5 #include <linux/time.h>
6 #include <linux/slab.h>
7 #include <linux/string.h>
9 #include <linux/buffer_head.h>
11 /*
12 * To make any changes in the tree we find a node that contains item
13 * to be changed/deleted or position in the node we insert a new item
14 * to. We call this node S. To do balancing we need to decide what we
15 * will shift to left/right neighbor, or to a new node, where new item
16 * will be etc. To make this analysis simpler we build virtual
17 * node. Virtual node is an array of items, that will replace items of
18 * node S. (For instance if we are going to delete an item, virtual
19 * node does not contain it). Virtual node keeps information about
20 * item sizes and types, mergeability of first and last items, sizes
21 * of all entries in directory item. We use this array of items when
22 * calculating what we can shift to neighbors and how many nodes we
23 * have to have if we do not any shiftings, if we shift to left/right
24 * neighbor or to both.
25 */
27 /*
28 * Takes item number in virtual node, returns number of item
29 * that it has in source buffer
30 */
32 {
42 }
46 mode);
47 /* delete mode */
49 }
52 {
60 /* size of changed node */
64 /* for internal nodes array if virtual items is not created */
68 }
70 /* number of items in virtual node */
75 /* first virtual item */
80 /* first item in the node */
83 /* define the mergeability for 0-th item (if it is not being deleted) */
88 /*
89 * go through all items that remain in the virtual
90 * node (except for the new (inserted) one)
91 */
101 /* get item number in source node */
110 /*
111 * FIXME: there is no check that item operation did not
112 * consume too much memory
113 */
121 /* this is not being changed */
126 /* pointer to data which is going to be pasted */
128 }
129 }
131 /* virtual inserted item is not defined yet */
144 }
146 /*
147 * set right merge flag we take right delimiting key and
148 * check whether it is a mergeable item
149 */
158 VI_TYPE_RIGHT_MERGEABLE;
160 #ifdef CONFIG_REISERFS_CHECK
164 /*
165 * we delete last item and it could be merged
166 * with right neighbor's first item
167 */
172 /*
173 * node contains more than 1 item, or item
174 * is not directory item, or this item
175 * contains more than 1 entry
176 */
179 "rdkey %k, affected item==%d "
183 }
184 }
185 #endif
187 }
188 }
190 /*
191 * Using virtual node check, how many items can be
192 * shifted to left neighbor
193 */
195 {
203 /* internal level */
207 }
209 /* leaf level */
212 /* no free space or nothing to move */
216 }
225 /* all contents of S[0] fits into L[0] */
233 }
237 /* first item may be merge with last item in left neighbor */
246 /* the item can be shifted entirely */
250 }
252 /* the item cannot be shifted entirely, try to split it */
253 /*
254 * check whether L[0] can hold ih and at least one byte
255 * of the item body
256 */
258 /* cannot shift even a part of the current item */
262 }
267 /* count partially shifted item */
271 }
274 }
276 /*
277 * Using virtual node check, how many items can be
278 * shifted to right neighbor
279 */
281 {
289 /* internal level */
293 }
295 /* leaf level */
298 /* no free space */
302 }
311 /* all contents of S[0] fits into R[0] */
319 }
323 /* last item may be merge with first item in right neighbor */
332 /* the item can be shifted entirely */
336 }
338 /*
339 * check whether R[0] can hold ih and at least one
340 * byte of the item body
341 */
343 /* cannot shift even a part of the current item */
347 }
349 /*
350 * R[0] can hold the header of the item and at least
351 * one byte of its body
352 */
357 /* count partially shifted item */
361 }
364 }
366 /*
367 * from - number of items, which are shifted to left neighbor entirely
368 * to - number of item, which are shifted to right neighbor entirely
369 * from_bytes - number of bytes of boundary item (or directory entries)
370 * which are shifted to left neighbor
371 * to_bytes - number of bytes of boundary item (or directory entries)
372 * which are shifted to right neighbor
373 */
377 {
384 /* position of item we start filling node from */
387 /* position of item we finish filling node by */
390 /*
391 * number of first bytes (entries for directory) of start_item-th item
392 * we do not include into node that is being filled
393 */
396 /*
397 * number of last bytes (entries for directory) of end_item-th item
398 * we do node include into node that is being filled
399 */
402 /*
403 * these are positions in virtual item of items, that are split
404 * between S[0] and S1new and S1new and S2new
405 */
411 /*
412 * We only create additional nodes if we are in insert or paste mode
413 * or we are in replace mode at the internal level. If h is 0 and
414 * the mode is M_REPLACE then in fix_nodes we change the mode to
415 * paste or insert before we get here in the code.
416 */
422 /*
423 * snum012 [0-2] - number of items, that lay
424 * to S[0], first new node and second new node
425 */
429 /* internal level */
435 }
437 /* leaf level */
441 /* start from 'from'-th item */
443 /* skip its first 'start_bytes' units */
446 /* last included item is the 'end_item'-th one */
448 /* do not count last 'end_bytes' units of 'end_item'-th item */
451 /*
452 * go through all item beginning from the start_item-th item
453 * and ending by the end_item-th item. Do not count first
454 * 'start_bytes' units of 'start_item'-th item and last
455 * 'end_bytes' of 'end_item'-th item
456 */
463 /* get size of current item */
466 /*
467 * do not take in calculation head part (from_bytes)
468 * of from-th item
469 */
470 current_item_size -=
473 /* do not take in calculation tail part of last item */
474 current_item_size -=
477 /* if item fits into current node entierly */
483 }
485 /*
486 * virtual item length is longer, than max size of item in
487 * a node. It is impossible for direct item
488 */
491 "vs-8110: "
494 /* we will try to split it */
496 }
498 /* as we do not split items, take new node and continue */
500 needed_nodes++;
501 i--;
504 }
506 /*
507 * calculate number of item units which fit into node being
508 * filled
509 */
510 {
514 units =
516 skip_from_end);
517 /*
518 * nothing fits into current node, take new
519 * node and continue
520 */
524 }
525 }
527 /* something fits into the current node */
536 needed_nodes++;
537 /* continue from the same item with start_bytes != -1 */
539 i--;
541 }
543 /*
544 * sum012[4] (if it is not -1) contains number of units of which
545 * are to be in S1new, snum012[3] - to be in S0. They are supposed
546 * to be S1bytes and S2bytes correspondingly, so recalculate
547 */
554 bytes_to_l =
557 bytes_to_r =
560 bytes_to_S1new =
564 /* s2bytes */
573 }
575 /* now we know S2bytes, calculate S1bytes */
582 bytes_to_l =
585 bytes_to_r =
588 bytes_to_S2new =
592 /* s1bytes */
596 }
599 }
602 /*
603 * Set parameters for balancing.
604 * Performs write of results of analysis of balancing into structure tb,
605 * where it will later be used by the functions that actually do the balancing.
606 * Parameters:
607 * tb tree_balance structure;
608 * h current level of the node;
609 * lnum number of items from S[h] that must be shifted to L[h];
610 * rnum number of items from S[h] that must be shifted to R[h];
611 * blk_num number of blocks that S[h] will be splitted into;
612 * s012 number of items that fall into splitted nodes.
613 * lbytes number of bytes which flow to the left neighbor from the
614 * item that is not not shifted entirely
615 * rbytes number of bytes which flow to the right neighbor from the
616 * item that is not not shifted entirely
617 * s1bytes number of bytes which flow to the first new node when
618 * S[0] splits (this number is contained in s012 array)
619 */
623 {
629 /* only for leaf level */
637 }
640 }
646 }
648 /*
649 * check if node disappears if we shift tb->lnum[0] items to left
650 * neighbor and tb->rnum[0] to the right one.
651 */
653 {
659 /*
660 * number of items that will be shifted to left (right) neighbor
661 * entirely
662 */
667 /* how many items remain in S[0] after shiftings to neighbors */
670 /* all content of node can be shifted to neighbors */
675 }
677 /* S[0] is not removable */
681 /* check whether we can divide 1 remaining item between neighbors */
683 /* get size of remaining item (in item units) */
690 }
693 }
695 /* check whether L, S, R can be joined in one node */
697 {
713 /* there was only one item and it will be deleted */
725 /*
726 * Directory must be in correct state here: that is
727 * somewhere at the left side should exist first
728 * directory item. But the item being deleted can
729 * not be that first one because its right neighbor
730 * is item of the same directory. (But first item
731 * always gets deleted in last turn). So, neighbors
732 * of deleted item can be merged, so we can save
733 * ih_size
734 */
738 /*
739 * we might check that left neighbor exists
740 * and is of the same directory
741 */
744 }
746 }
752 }
755 }
757 /* when we do not split item, lnum and rnum are numbers of entire items */
758 #define SET_PAR_SHIFT_LEFT \
759 if (h)\
760 {\
761 int to_l;\
762 \
763 to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
764 (MAX_NR_KEY(Sh) + 1 - lpar);\
765 \
766 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
767 }\
768 else \
769 {\
770 if (lset==LEFT_SHIFT_FLOW)\
771 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
772 tb->lbytes, -1);\
773 else\
774 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
775 -1, -1);\
776 }
778 #define SET_PAR_SHIFT_RIGHT \
779 if (h)\
780 {\
781 int to_r;\
782 \
783 to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
784 \
785 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
786 }\
787 else \
788 {\
789 if (rset==RIGHT_SHIFT_FLOW)\
790 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
791 -1, tb->rbytes);\
792 else\
793 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
794 -1, -1);\
795 }
798 {
817 }
818 }
820 /*
821 * Get new buffers for storing new nodes that are created while balancing.
822 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
823 * CARRY_ON - schedule didn't occur while the function worked;
824 * NO_DISK_SPACE - no disk space.
825 */
826 /* The function is NOT SCHEDULE-SAFE! */
828 {
836 /*
837 * number_of_freeblk is the number of empty blocks which have been
838 * acquired for use by the balancing algorithm minus the number of
839 * empty blocks used in the previous levels of the analysis,
840 * number_of_freeblk = tb->cur_blknum can be non-zero if a schedule
841 * occurs after empty blocks are acquired, and the balancing analysis
842 * is then restarted, amount_needed is the number needed by this
843 * level (h) of the balancing analysis.
844 *
845 * Note that for systems with many processes writing, it would be
846 * more layout optimal to calculate the total number needed by all
847 * levels and then to run reiserfs_new_blocks to get all of them at
848 * once.
849 */
851 /*
852 * Initiate number_of_freeblk to the amount acquired prior to the
853 * restart of the analysis or 0 if not restarted, then subtract the
854 * amount needed by all of the levels of the tree below h.
855 */
856 /* blknum includes S[h], so we subtract 1 in this calculation */
859 number_of_freeblk -=
863 /* Allocate missing empty blocks. */
864 /* if Sh == 0 then we are getting a new root */
866 /*
867 * Amount_needed = the amount that we need more than the
868 * amount that we have.
869 */
875 /*
876 * No need to check quota - is not allocated for blocks used
877 * for formatted nodes
878 */
883 /* for each blocknumber we just got, get a buffer and stick it on FEB */
895 new_bh);
897 /* Put empty buffers into the array. */
903 }
909 }
911 /*
912 * Get free space of the left neighbor, which is stored in the parent
913 * node of the left neighbor.
914 */
916 {
929 }
932 }
934 /*
935 * Get free space of the right neighbor,
936 * which is stored in the parent node of the right neighbor.
937 */
939 {
952 }
956 }
958 /* Check whether left neighbor is in memory. */
960 {
963 b_blocknr_t left_neighbor_blocknr;
966 /* Father of the left neighbor does not exist. */
970 /* Calculate father of the node to be balanced. */
981 /*
982 * Get position of the pointer to the left neighbor
983 * into the left father.
984 */
987 /* Get left neighbor block number. */
988 left_neighbor_blocknr =
990 /* Look for the left neighbor in the cache. */
998 }
1001 }
1007 {
1008 /* call item specific function for this key */
1010 }
1012 /*
1013 * Calculate far left/right parent of the left/right neighbor of the
1014 * current node, that is calculate the left/right (FL[h]/FR[h]) neighbor
1015 * of the parent F[h].
1016 * Calculate left/right common parent of the current node and L[h]/R[h].
1017 * Calculate left/right delimiting key position.
1018 * Returns: PATH_INCORRECT - path in the tree is not correct
1019 * SCHEDULE_OCCURRED - schedule occurred while the function worked
1020 * CARRY_ON - schedule didn't occur while the function
1021 * worked
1022 */
1027 {
1037 /*
1038 * Starting from F[h] go upwards in the tree, and look for the common
1039 * ancestor of F[h], and its neighbor l/r, that should be obtained.
1040 */
1048 /*
1049 * Check whether parent of the current buffer in the path
1050 * is really parent in the tree.
1051 */
1056 /* Check whether position in the parent is correct. */
1063 /*
1064 * Check whether parent at the path really points
1065 * to the child.
1066 */
1071 /*
1072 * Return delimiting key if position in the parent is not
1073 * equal to first/last one.
1074 */
1080 /*(*pcom_father = parent)->b_count++; */
1082 }
1083 }
1085 /* if we are in the root of the tree, then there is no common father */
1087 /*
1088 * Check whether first buffer in the path is the
1089 * root of the tree.
1090 */
1097 }
1099 }
1105 /* Check whether the common parent is locked. */
1109 /* Release the write lock while the buffer is busy */
1116 }
1117 }
1119 /*
1120 * So, we got common parent of the current node and its
1121 * left/right neighbor. Now we are getting the parent of the
1122 * left/right neighbor.
1123 */
1125 /* Form key to get parent of the left/right neighbor. */
1130 position -
1133 position)));
1141 /* path is released */
1148 }
1160 }
1162 /*
1163 * Get parents of neighbors of node in the path(S[path_offset]) and
1164 * common parents of S[path_offset] and L[path_offset]/R[path_offset]:
1165 * F[path_offset], FL[path_offset], FR[path_offset], CFL[path_offset],
1166 * CFR[path_offset].
1167 * Calculate numbers of left and right delimiting keys position:
1168 * lkey[path_offset], rkey[path_offset].
1169 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked
1170 * CARRY_ON - schedule didn't occur while the function worked
1171 */
1173 {
1176 ret,
1180 /* Current node is the root of the tree or will be root of the tree */
1182 /*
1183 * The root can not have parents.
1184 * Release nodes which previously were obtained as
1185 * parents of the current node neighbors.
1186 */
1196 }
1198 /* Get parent FL[path_offset] of L[path_offset]. */
1201 /* Current node is not the first child of its parent. */
1208 /*
1209 * Calculate current parent of L[path_offset], which is the
1210 * left neighbor of the current node. Calculate current
1211 * common parent of L[path_offset] and the current node.
1212 * Note that CFL[path_offset] not equal FL[path_offset] and
1213 * CFL[path_offset] not equal F[path_offset].
1214 * Calculate lkey[path_offset].
1215 */
1220 }
1231 /* Get parent FR[h] of R[h]. */
1233 /* Current node is the last child of F[h]. FR[h] != F[h]. */
1235 /*
1236 * Calculate current parent of R[h], which is the right
1237 * neighbor of F[h]. Calculate current common parent of
1238 * R[h] and current node. Note that CFR[h] not equal
1239 * FR[path_offset] and CFR[h] not equal F[h].
1240 */
1246 /* Current node is not the last child of its parent F[h]. */
1252 }
1255 /* New initialization of FR[path_offset]. */
1259 /* New initialization of CFR[path_offset]. */
1267 }
1269 /*
1270 * it is possible to remove node as result of shiftings to
1271 * neighbors even when we insert or paste item.
1272 */
1275 {
1286 /* shifting may merge items which might save space */
1287 -
1288 ((!h
1290 -
1294 /* node can not be removed */
1296 /* new item fits into node S[h] without any shifting */
1303 }
1304 }
1307 }
1309 /*
1310 * Check whether current node S[h] is balanced when increasing its size by
1311 * Inserting or Pasting.
1312 * Calculate parameters for balancing for current level h.
1313 * Parameters:
1314 * tb tree_balance structure;
1315 * h current level of the node;
1316 * inum item number in S[h];
1317 * mode i - insert, p - paste;
1318 * Returns: 1 - schedule occurred;
1319 * 0 - balancing for higher levels needed;
1320 * -1 - no balancing for higher levels needed;
1321 * -2 - no disk space.
1322 */
1323 /* ip means Inserting or Pasting */
1325 {
1327 /*
1328 * Number of bytes that must be inserted into (value is negative
1329 * if bytes are deleted) buffer which contains node being balanced.
1330 * The mnemonic is that the attempted change in node space used
1331 * level is levbytes bytes.
1332 */
1338 /*
1339 * nver is short for number of vertixes, and lnver is the number if
1340 * we shift to the left, rnver is the number if we shift to the
1341 * right, and lrnver is the number if we shift in both directions.
1342 * The goal is to minimize first the number of vertixes, and second,
1343 * the number of vertixes whose contents are changed by shifting,
1344 * and third the number of uncached vertixes whose contents are
1345 * changed by shifting and must be read from disk.
1346 */
1349 /*
1350 * used at leaf level only, S0 = S[0] is the node being balanced,
1351 * sInum [ I = 0,1,2 ] is the number of items that will
1352 * remain in node SI after balancing. S1 and S2 are new
1353 * nodes that might be created.
1354 */
1356 /*
1357 * we perform 8 calls to get_num_ver(). For each call we
1358 * calculate five parameters. where 4th parameter is s1bytes
1359 * and 5th - s2bytes
1360 *
1361 * s0num, s1num, s2num for 8 cases
1362 * 0,1 - do not shift and do not shift but bottle
1363 * 2 - shift only whole item to left
1364 * 3 - shift to left and bottle as much as possible
1365 * 4,5 - shift to right (whole items and as much as possible
1366 * 6,7 - shift to both directions (whole items and as much as possible)
1367 */
1370 /* Sh is the node whose balance is currently being checked */
1376 /* Calculate balance parameters for creating new root. */
1382 /* no balancing for higher levels needed */
1393 }
1394 }
1396 /* get parents of S[h] neighbors. */
1403 /* get free space of neighbors */
1407 /* and new item fits into node S[h] without any shifting */
1409 NO_BALANCING_NEEDED)
1414 /*
1415 * determine maximal number of items we can shift to the left
1416 * neighbor (in tb structure) and the maximal number of bytes
1417 * that can flow to the left neighbor from the left most liquid
1418 * item that cannot be shifted from S[0] entirely (returned value)
1419 */
1422 /*
1423 * determine maximal number of items we can shift to the right
1424 * neighbor (in tb structure) and the maximal number of bytes
1425 * that can flow to the right neighbor from the right most liquid
1426 * item that cannot be shifted from S[0] entirely (returned value)
1427 */
1430 /*
1431 * all contents of internal node S[h] can be moved into its
1432 * neighbors, S[h] will be removed after balancing
1433 */
1437 /*
1438 * Since we are working on internal nodes, and our internal
1439 * nodes have fixed size entries, then we can balance by the
1440 * number of items rather than the space they consume. In this
1441 * routine we set the left node equal to the right node,
1442 * allowing a difference of less than or equal to 1 child
1443 * pointer.
1444 */
1445 to_r =
1452 }
1454 /*
1455 * this checks balance condition, that any two neighboring nodes
1456 * can not fit in one node
1457 */
1466 /*
1467 * all contents of S[0] can be moved into its neighbors
1468 * S[0] will be removed after balancing.
1469 */
1473 /*
1474 * why do we perform this check here rather than earlier??
1475 * Answer: we can win 1 node in some cases above. Moreover we
1476 * checked it above, when we checked, that S[0] is not removable
1477 * in principle
1478 */
1480 /* new item fits into node S[h] without any shifting */
1486 }
1488 {
1490 /* regular overflowing of the node */
1492 /*
1493 * get_num_ver works in 2 modes (FLOW & NO_FLOW)
1494 * lpar, rpar - number of items we can shift to left/right
1495 * neighbor (including splitting item)
1496 * nset, lset, rset, lrset - shows, whether flowing items
1497 * give better packing
1498 */
1499 #define FLOW 1
1502 /* we choose one of the following */
1503 #define NOTHING_SHIFT_NO_FLOW 0
1504 #define NOTHING_SHIFT_FLOW 5
1505 #define LEFT_SHIFT_NO_FLOW 10
1506 #define LEFT_SHIFT_FLOW 15
1507 #define RIGHT_SHIFT_NO_FLOW 20
1508 #define RIGHT_SHIFT_FLOW 25
1509 #define LR_SHIFT_NO_FLOW 30
1510 #define LR_SHIFT_FLOW 35
1515 /*
1516 * calculate number of blocks S[h] must be split into when
1517 * nothing is shifted to the neighbors, as well as number of
1518 * items in each part of the split node (s012 numbers),
1519 * and number of bytes (s1bytes) of the shared drop which
1520 * flow to S1 if any
1521 */
1530 /*
1531 * note, that in this case we try to bottle
1532 * between S[0] and S1 (S1 - the first new node)
1533 */
1539 }
1541 /*
1542 * calculate number of blocks S[h] must be split into when
1543 * l_shift_num first items and l_shift_bytes of the right
1544 * most liquid item to be shifted are shifted to the left
1545 * neighbor, as well as number of items in each part of the
1546 * splitted node (s012 numbers), and number of bytes
1547 * (s1bytes) of the shared drop which flow to S1 if any
1548 */
1558 lpar -
1564 }
1566 /*
1567 * calculate number of blocks S[h] must be split into when
1568 * r_shift_num first items and r_shift_bytes of the left most
1569 * liquid item to be shifted are shifted to the right neighbor,
1570 * as well as number of items in each part of the splitted
1571 * node (s012 numbers), and number of bytes (s1bytes) of the
1572 * shared drop which flow to S1 if any
1573 */
1579 rbytes !=
1595 }
1597 /*
1598 * calculate number of blocks S[h] must be split into when
1599 * items are shifted in both directions, as well as number
1600 * of items in each part of the splitted node (s012 numbers),
1601 * and number of bytes (s1bytes) of the shared drop which
1602 * flow to S1 if any
1603 */
1610 rbytes !=
1618 lpar -
1627 }
1629 /*
1630 * Our general shifting strategy is:
1631 * 1) to minimized number of new nodes;
1632 * 2) to minimized number of neighbors involved in shifting;
1633 * 3) to minimized number of disk reads;
1634 */
1636 /* we can win TWO or ONE nodes by shifting in both directions */
1647 else
1656 }
1658 /*
1659 * if shifting doesn't lead to better packing
1660 * then don't shift
1661 */
1666 }
1668 /*
1669 * now we know that for better packing shifting in only one
1670 * direction either to the left or to the right is required
1671 */
1673 /*
1674 * if shifting to the left is better than
1675 * shifting to the right
1676 */
1678 SET_PAR_SHIFT_LEFT;
1680 }
1682 /*
1683 * if shifting to the right is better than
1684 * shifting to the left
1685 */
1687 SET_PAR_SHIFT_RIGHT;
1689 }
1691 /*
1692 * now shifting in either direction gives the same number
1693 * of nodes and we can make use of the cached neighbors
1694 */
1696 SET_PAR_SHIFT_LEFT;
1698 }
1700 /*
1701 * shift to the right independently on whether the
1702 * right neighbor in cache or not
1703 */
1704 SET_PAR_SHIFT_RIGHT;
1706 }
1707 }
1709 /*
1710 * Check whether current node S[h] is balanced when Decreasing its size by
1711 * Deleting or Cutting for INTERNAL node of S+tree.
1712 * Calculate parameters for balancing for current level h.
1713 * Parameters:
1714 * tb tree_balance structure;
1715 * h current level of the node;
1716 * inum item number in S[h];
1717 * mode i - insert, p - paste;
1718 * Returns: 1 - schedule occurred;
1719 * 0 - balancing for higher levels needed;
1720 * -1 - no balancing for higher levels needed;
1721 * -2 - no disk space.
1722 *
1723 * Note: Items of internal nodes have fixed size, so the balance condition for
1724 * the internal part of S+tree is as for the B-trees.
1725 */
1727 {
1730 /*
1731 * Sh is the node whose balance is currently being checked,
1732 * and Fh is its father.
1733 */
1741 /*
1742 * using tb->insert_size[h], which is negative in this case,
1743 * create_virtual_node calculates:
1744 * new_nr_item = number of items node would have if operation is
1745 * performed without balancing (new_nr_item);
1746 */
1750 /* no balancing for higher levels needed */
1754 }
1755 /*
1756 * new_nr_item == 0.
1757 * Current root will be deleted resulting in
1758 * decrementing the tree height.
1759 */
1762 }
1767 /* get free space of neighbors */
1771 /* determine maximal number of items we can fit into neighbors */
1775 /*
1776 * Balance condition for the internal node is valid.
1777 * In this case we balance only if it leads to better packing.
1778 */
1780 /*
1781 * Here we join S[h] with one of its neighbors,
1782 * which is impossible with greater values of new_nr_item.
1783 */
1785 /* All contents of S[h] can be moved to L[h]. */
1790 order_L =
1793 h)) ==
1800 }
1802 /* All contents of S[h] can be moved to R[h]. */
1807 order_R =
1810 h)) ==
1817 }
1818 }
1820 /*
1821 * All contents of S[h] can be moved to the neighbors
1822 * (L[h] & R[h]).
1823 */
1827 to_r =
1834 }
1836 /* Balancing does not lead to better packing. */
1839 }
1841 /*
1842 * Current node contain insufficient number of items.
1843 * Balancing is required.
1844 */
1845 /* Check whether we can merge S[h] with left neighbor. */
1852 order_L =
1855 h)) ==
1858 KEY_SIZE);
1861 }
1863 /* Check whether we can merge S[h] with right neighbor. */
1868 order_R =
1873 KEY_SIZE);
1876 }
1878 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1882 to_r =
1889 }
1891 /* For internal nodes try to borrow item from a neighbor */
1894 /* Borrow one or two items from caching neighbor */
1898 from_l =
1903 }
1909 }
1911 /*
1912 * Check whether current node S[h] is balanced when Decreasing its size by
1913 * Deleting or Truncating for LEAF node of S+tree.
1914 * Calculate parameters for balancing for current level h.
1915 * Parameters:
1916 * tb tree_balance structure;
1917 * h current level of the node;
1918 * inum item number in S[h];
1919 * mode i - insert, p - paste;
1920 * Returns: 1 - schedule occurred;
1921 * 0 - balancing for higher levels needed;
1922 * -1 - no balancing for higher levels needed;
1923 * -2 - no disk space.
1924 */
1926 {
1929 /*
1930 * Number of bytes that must be deleted from
1931 * (value is negative if bytes are deleted) buffer which
1932 * contains node being balanced. The mnemonic is that the
1933 * attempted change in node space used level is levbytes bytes.
1934 */
1937 /* the maximal item size */
1940 /*
1941 * S0 is the node whose balance is currently being checked,
1942 * and F0 is its father.
1943 */
1961 }
1966 /* get free space of neighbors */
1972 /* if 3 leaves can be merge to one, set parameters and return */
1976 /*
1977 * determine maximal number of items we can shift to the left/right
1978 * neighbor and the maximal number of bytes that can flow to the
1979 * left/right neighbor from the left/right most liquid item that
1980 * cannot be shifted from S[0] entirely
1981 */
1985 /* check whether we can merge S with left neighbor. */
1987 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 */
1993 /* set parameter to merge S[0] with its left neighbor */
1996 }
1998 /* check whether we can merge S[0] with right neighbor. */
2002 }
2004 /*
2005 * All contents of S[0] can be moved to the neighbors (L[0] & R[0]).
2006 * Set parameters and return
2007 */
2011 /* Balancing is not required. */
2015 }
2017 /*
2018 * Check whether current node S[h] is balanced when Decreasing its size by
2019 * Deleting or Cutting.
2020 * Calculate parameters for balancing for current level h.
2021 * Parameters:
2022 * tb tree_balance structure;
2023 * h current level of the node;
2024 * inum item number in S[h];
2025 * mode d - delete, c - cut.
2026 * Returns: 1 - schedule occurred;
2027 * 0 - balancing for higher levels needed;
2028 * -1 - no balancing for higher levels needed;
2029 * -2 - no disk space.
2030 */
2032 {
2038 else
2040 }
2042 /*
2043 * Check whether current node S[h] is balanced.
2044 * Calculate parameters for balancing for current level h.
2045 * Parameters:
2046 *
2047 * tb tree_balance structure:
2048 *
2049 * tb is a large structure that must be read about in the header
2050 * file at the same time as this procedure if the reader is
2051 * to successfully understand this procedure
2052 *
2053 * h current level of the node;
2054 * inum item number in S[h];
2055 * mode i - insert, p - paste, d - delete, c - cut.
2056 * Returns: 1 - schedule occurred;
2057 * 0 - balancing for higher levels needed;
2058 * -1 - no balancing for higher levels needed;
2059 * -2 - no disk space.
2060 */
2067 {
2081 /* Calculate balance parameters when size of node is increasing. */
2085 /* Calculate balance parameters when size of node is decreasing. */
2087 }
2089 /* Check whether parent at the path is the really parent of the current node.*/
2091 {
2097 /* We are in the root or in the new root. */
2105 /* Root is not changed. */
2109 }
2110 /* Root is changed and we must recalculate the path. */
2112 }
2114 /* Parent in the path is not in the tree. */
2124 /* Parent in the path is not parent of the current node in the tree. */
2135 }
2137 /*
2138 * Parent in the path is unlocked and really parent
2139 * of the current node.
2140 */
2142 }
2144 /*
2145 * Using lnum[h] and rnum[h] we should determine what neighbors
2146 * of S[h] we
2147 * need in order to balance S[h], and get them if necessary.
2148 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
2149 * CARRY_ON - schedule didn't occur while the function worked;
2150 */
2152 {
2163 /* We need left neighbor to balance S[h]. */
2171 child_position =
2185 }
2200 }
2202 /* We need right neighbor to balance S[path_offset]. */
2209 path_offset) >=
2213 child_position =
2225 }
2237 }
2239 }
2242 {
2247 #define MIN_NAME_LEN 1
2257 }
2259 /*
2260 * maybe we should fail balancing we are going to perform when kmalloc
2261 * fails several times. But now it will loop until kmalloc gets
2262 * required memory
2263 */
2265 {
2272 /* we have to allocate more memory for virtual node */
2275 /* free memory allocated before */
2277 /* this is not needed if kfree is atomic */
2279 }
2281 /* virtual node requires now more memory */
2284 /* get memory for virtual item */
2287 /*
2288 * getting memory with GFP_KERNEL priority may involve
2289 * balancing now (due to indirect_to_direct conversion
2290 * on dcache shrinking). So, release path and collected
2291 * resources here
2292 */
2297 }
2301 }
2304 }
2310 }
2312 #ifdef CONFIG_REISERFS_CHECK
2316 {
2321 "reference counter for buffer %s[%d] "
2348 }
2349 }
2350 #else
2354 {;
2355 }
2356 #endif
2359 {
2361 }
2364 {
2366 #ifdef CONFIG_REISERFS_CHECK
2368 #endif
2378 /*
2379 * if I understand correctly, we can only
2380 * be sure the last buffer in the path is
2381 * in the tree --clm
2382 */
2383 #ifdef CONFIG_REISERFS_CHECK
2387 PATH_OFFSET_PBUFFER
2392 #endif
2394 PATH_OFFSET_PBUFFER
2396 i))) {
2397 locked =
2399 i);
2400 }
2401 }
2402 }
2405 i++) {
2416 }
2425 }
2434 }
2436 }
2447 }
2456 }
2465 }
2466 }
2467 }
2469 /*
2470 * as far as I can tell, this is not required. The FEB list
2471 * seems to be full of newly allocated nodes, which will
2472 * never be locked, dirty, or anything else.
2473 * To be safe, I'm putting in the checks and waits in.
2474 * For the moment, they are needed to keep the code in
2475 * journal.c from complaining about the buffer.
2476 * That code is inside CONFIG_REISERFS_CHECK as well. --clm
2477 */
2483 }
2484 }
2488 #ifdef CONFIG_REISERFS_CHECK
2489 repeat_counter++;
2492 "too many iterations waiting "
2493 "for buffer to unlock "
2496 /* Don't loop forever. Try to recover from possible error. */
2500 }
2501 #endif
2507 }
2512 }
2514 /*
2515 * Prepare for balancing, that is
2516 * get all necessary parents, and neighbors;
2517 * analyze what and where should be moved;
2518 * get sufficient number of new nodes;
2519 * Balancing will start only after all resources will be collected at a time.
2520 *
2521 * When ported to SMP kernels, only at the last moment after all needed nodes
2522 * are collected in cache, will the resources be locked using the usual
2523 * textbook ordered lock acquisition algorithms. Note that ensuring that
2524 * this code neither write locks what it does not need to write lock nor locks
2525 * out of order will be a pain in the butt that could have been avoided.
2526 * Grumble grumble. -Hans
2527 *
2528 * fix is meant in the sense of render unchanging
2529 *
2530 * Latency might be improved by first gathering a list of what buffers
2531 * are needed and then getting as many of them in parallel as possible? -Hans
2532 *
2533 * Parameters:
2534 * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2535 * tb tree_balance structure;
2536 * inum item number in S[h];
2537 * pos_in_item - comment this if you can
2538 * ins_ih item head of item being inserted
2539 * data inserted item or data to be pasted
2540 * Returns: 1 - schedule occurred while the function worked;
2541 * 0 - schedule didn't occur while the function worked;
2542 * -1 - if no_disk_space
2543 */
2547 {
2551 /*
2552 * we set wait_tb_buffers_run when we have to restore any dirty
2553 * bits cleared during wait_tb_buffers_run
2554 */
2564 /*
2565 * we prepare and log the super here so it will already be in the
2566 * transaction when do_balance needs to change it.
2567 * This way do_balance won't have to schedule when trying to prepare
2568 * the super for logging
2569 */
2577 /* if it possible in indirect_to_direct conversion */
2584 }
2585 #ifdef CONFIG_REISERFS_CHECK
2590 }
2594 "not uptodate at the beginning of fix_nodes "
2598 /* Check parameters. */
2603 "item number %d (in S0 - %d) in case "
2613 "item number(%d); mode = %c "
2617 }
2622 }
2623 #endif
2626 /* FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat */
2629 /* Starting from the leaf level; for all levels h of the tree. */
2639 /* No balancing for higher levels needed. */
2645 /*
2646 * ok, analysis and resource gathering
2647 * are complete
2648 */
2650 }
2652 }
2658 /*
2659 * No disk space, or schedule occurred and analysis may be
2660 * invalid and needs to be redone.
2661 */
2666 /*
2667 * We have a positive insert size but no nodes exist on this
2668 * level, this means that we are creating a new root.
2669 */
2678 /*
2679 * The tree needs to be grown, so this node S[h]
2680 * which is the root node is split into two nodes,
2681 * and a new node (S[h+1]) will be created to
2682 * become the root node.
2683 */
2692 DC_SIZE;
2698 }
2708 }
2712 }
2714 repeat:
2715 /*
2716 * fix_nodes was unable to perform its calculation due to
2717 * filesystem got changed under us, lack of free disk space or i/o
2718 * failure. If the first is the case - the search will be
2719 * repeated. For now - free all resources acquired so far except
2720 * for the new allocated nodes
2721 */
2722 {
2725 /* Release path buffers. */
2730 }
2731 /* brelse all resources collected for balancing */
2743 tb->
2746 tb->
2748 }
2763 }
2768 reiserfs_restore_prepared_buffer
2770 }
2771 }
2773 }
2775 }
2778 {
2781 /* Release path buffers. */
2784 /* brelse all resources collected for balancing */
2799 }
2801 /* deal with list of allocated (used and unused) nodes */
2805 /*
2806 * de-allocated block which was not used by
2807 * balancing and bforget about buffer for it
2808 */
2812 }
2814 /* release used as new nodes including a new root */
2816 }
2817 }
2821 }