| blob | 6b0ddb2a9091aab48121ccb869ea0df2ba72fcf5 |
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 {
385 /* position of item we start filling node from */
388 /* position of item we finish filling node by */
391 /*
392 * number of first bytes (entries for directory) of start_item-th item
393 * we do not include into node that is being filled
394 */
397 /*
398 * number of last bytes (entries for directory) of end_item-th item
399 * we do node include into node that is being filled
400 */
403 /*
404 * these are positions in virtual item of items, that are split
405 * between S[0] and S1new and S1new and S2new
406 */
412 /*
413 * We only create additional nodes if we are in insert or paste mode
414 * or we are in replace mode at the internal level. If h is 0 and
415 * the mode is M_REPLACE then in fix_nodes we change the mode to
416 * paste or insert before we get here in the code.
417 */
423 /*
424 * snum012 [0-2] - number of items, that lay
425 * to S[0], first new node and second new node
426 */
430 /* internal level */
436 }
438 /* leaf level */
443 /* start from 'from'-th item */
445 /* skip its first 'start_bytes' units */
448 /* last included item is the 'end_item'-th one */
450 /* do not count last 'end_bytes' units of 'end_item'-th item */
453 /*
454 * go through all item beginning from the start_item-th item
455 * and ending by the end_item-th item. Do not count first
456 * 'start_bytes' units of 'start_item'-th item and last
457 * 'end_bytes' of 'end_item'-th item
458 */
465 /* get size of current item */
468 /*
469 * do not take in calculation head part (from_bytes)
470 * of from-th item
471 */
472 current_item_size -=
475 /* do not take in calculation tail part of last item */
476 current_item_size -=
479 /* if item fits into current node entierly */
485 }
487 /*
488 * virtual item length is longer, than max size of item in
489 * a node. It is impossible for direct item
490 */
493 "vs-8110: "
496 /* we will try to split it */
498 }
500 /* as we do not split items, take new node and continue */
502 needed_nodes++;
503 i--;
506 }
508 /*
509 * calculate number of item units which fit into node being
510 * filled
511 */
512 {
516 units =
518 skip_from_end);
519 /*
520 * nothing fits into current node, take new
521 * node and continue
522 */
526 }
527 }
529 /* something fits into the current node */
538 needed_nodes++;
539 /* continue from the same item with start_bytes != -1 */
541 i--;
543 }
545 /*
546 * sum012[4] (if it is not -1) contains number of units of which
547 * are to be in S1new, snum012[3] - to be in S0. They are supposed
548 * to be S1bytes and S2bytes correspondingly, so recalculate
549 */
556 bytes_to_l =
559 bytes_to_r =
562 bytes_to_S1new =
566 /* s2bytes */
575 }
577 /* now we know S2bytes, calculate S1bytes */
584 bytes_to_l =
587 bytes_to_r =
590 bytes_to_S2new =
594 /* s1bytes */
598 }
601 }
604 /*
605 * Set parameters for balancing.
606 * Performs write of results of analysis of balancing into structure tb,
607 * where it will later be used by the functions that actually do the balancing.
608 * Parameters:
609 * tb tree_balance structure;
610 * h current level of the node;
611 * lnum number of items from S[h] that must be shifted to L[h];
612 * rnum number of items from S[h] that must be shifted to R[h];
613 * blk_num number of blocks that S[h] will be splitted into;
614 * s012 number of items that fall into splitted nodes.
615 * lbytes number of bytes which flow to the left neighbor from the
616 * item that is not not shifted entirely
617 * rbytes number of bytes which flow to the right neighbor from the
618 * item that is not not shifted entirely
619 * s1bytes number of bytes which flow to the first new node when
620 * S[0] splits (this number is contained in s012 array)
621 */
625 {
631 /* only for leaf level */
639 }
642 }
648 }
650 /*
651 * check if node disappears if we shift tb->lnum[0] items to left
652 * neighbor and tb->rnum[0] to the right one.
653 */
655 {
661 /*
662 * number of items that will be shifted to left (right) neighbor
663 * entirely
664 */
669 /* how many items remain in S[0] after shiftings to neighbors */
672 /* all content of node can be shifted to neighbors */
677 }
679 /* S[0] is not removable */
683 /* check whether we can divide 1 remaining item between neighbors */
685 /* get size of remaining item (in item units) */
692 }
695 }
697 /* check whether L, S, R can be joined in one node */
699 {
715 /* there was only one item and it will be deleted */
727 /*
728 * Directory must be in correct state here: that is
729 * somewhere at the left side should exist first
730 * directory item. But the item being deleted can
731 * not be that first one because its right neighbor
732 * is item of the same directory. (But first item
733 * always gets deleted in last turn). So, neighbors
734 * of deleted item can be merged, so we can save
735 * ih_size
736 */
740 /*
741 * we might check that left neighbor exists
742 * and is of the same directory
743 */
746 }
748 }
754 }
757 }
759 /* when we do not split item, lnum and rnum are numbers of entire items */
760 #define SET_PAR_SHIFT_LEFT \
761 if (h)\
762 {\
763 int to_l;\
764 \
765 to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
766 (MAX_NR_KEY(Sh) + 1 - lpar);\
767 \
768 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
769 }\
770 else \
771 {\
772 if (lset==LEFT_SHIFT_FLOW)\
773 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
774 tb->lbytes, -1);\
775 else\
776 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
777 -1, -1);\
778 }
780 #define SET_PAR_SHIFT_RIGHT \
781 if (h)\
782 {\
783 int to_r;\
784 \
785 to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
786 \
787 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
788 }\
789 else \
790 {\
791 if (rset==RIGHT_SHIFT_FLOW)\
792 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
793 -1, tb->rbytes);\
794 else\
795 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
796 -1, -1);\
797 }
800 {
819 }
820 }
822 /*
823 * Get new buffers for storing new nodes that are created while balancing.
824 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
825 * CARRY_ON - schedule didn't occur while the function worked;
826 * NO_DISK_SPACE - no disk space.
827 */
828 /* The function is NOT SCHEDULE-SAFE! */
830 {
838 /*
839 * number_of_freeblk is the number of empty blocks which have been
840 * acquired for use by the balancing algorithm minus the number of
841 * empty blocks used in the previous levels of the analysis,
842 * number_of_freeblk = tb->cur_blknum can be non-zero if a schedule
843 * occurs after empty blocks are acquired, and the balancing analysis
844 * is then restarted, amount_needed is the number needed by this
845 * level (h) of the balancing analysis.
846 *
847 * Note that for systems with many processes writing, it would be
848 * more layout optimal to calculate the total number needed by all
849 * levels and then to run reiserfs_new_blocks to get all of them at
850 * once.
851 */
853 /*
854 * Initiate number_of_freeblk to the amount acquired prior to the
855 * restart of the analysis or 0 if not restarted, then subtract the
856 * amount needed by all of the levels of the tree below h.
857 */
858 /* blknum includes S[h], so we subtract 1 in this calculation */
861 number_of_freeblk -=
865 /* Allocate missing empty blocks. */
866 /* if Sh == 0 then we are getting a new root */
868 /*
869 * Amount_needed = the amount that we need more than the
870 * amount that we have.
871 */
877 /*
878 * No need to check quota - is not allocated for blocks used
879 * for formatted nodes
880 */
885 /* for each blocknumber we just got, get a buffer and stick it on FEB */
897 new_bh);
899 /* Put empty buffers into the array. */
905 }
911 }
913 /*
914 * Get free space of the left neighbor, which is stored in the parent
915 * node of the left neighbor.
916 */
918 {
931 }
934 }
936 /*
937 * Get free space of the right neighbor,
938 * which is stored in the parent node of the right neighbor.
939 */
941 {
954 }
958 }
960 /* Check whether left neighbor is in memory. */
962 {
965 b_blocknr_t left_neighbor_blocknr;
968 /* Father of the left neighbor does not exist. */
972 /* Calculate father of the node to be balanced. */
983 /*
984 * Get position of the pointer to the left neighbor
985 * into the left father.
986 */
989 /* Get left neighbor block number. */
990 left_neighbor_blocknr =
992 /* Look for the left neighbor in the cache. */
1000 }
1003 }
1009 {
1010 /* call item specific function for this key */
1012 }
1014 /*
1015 * Calculate far left/right parent of the left/right neighbor of the
1016 * current node, that is calculate the left/right (FL[h]/FR[h]) neighbor
1017 * of the parent F[h].
1018 * Calculate left/right common parent of the current node and L[h]/R[h].
1019 * Calculate left/right delimiting key position.
1020 * Returns: PATH_INCORRECT - path in the tree is not correct
1021 * SCHEDULE_OCCURRED - schedule occurred while the function worked
1022 * CARRY_ON - schedule didn't occur while the function
1023 * worked
1024 */
1029 {
1039 /*
1040 * Starting from F[h] go upwards in the tree, and look for the common
1041 * ancestor of F[h], and its neighbor l/r, that should be obtained.
1042 */
1050 /*
1051 * Check whether parent of the current buffer in the path
1052 * is really parent in the tree.
1053 */
1058 /* Check whether position in the parent is correct. */
1065 /*
1066 * Check whether parent at the path really points
1067 * to the child.
1068 */
1073 /*
1074 * Return delimiting key if position in the parent is not
1075 * equal to first/last one.
1076 */
1082 /*(*pcom_father = parent)->b_count++; */
1084 }
1085 }
1087 /* if we are in the root of the tree, then there is no common father */
1089 /*
1090 * Check whether first buffer in the path is the
1091 * root of the tree.
1092 */
1099 }
1101 }
1107 /* Check whether the common parent is locked. */
1111 /* Release the write lock while the buffer is busy */
1118 }
1119 }
1121 /*
1122 * So, we got common parent of the current node and its
1123 * left/right neighbor. Now we are getting the parent of the
1124 * left/right neighbor.
1125 */
1127 /* Form key to get parent of the left/right neighbor. */
1132 position -
1135 position)));
1143 /* path is released */
1150 }
1162 }
1164 /*
1165 * Get parents of neighbors of node in the path(S[path_offset]) and
1166 * common parents of S[path_offset] and L[path_offset]/R[path_offset]:
1167 * F[path_offset], FL[path_offset], FR[path_offset], CFL[path_offset],
1168 * CFR[path_offset].
1169 * Calculate numbers of left and right delimiting keys position:
1170 * lkey[path_offset], rkey[path_offset].
1171 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked
1172 * CARRY_ON - schedule didn't occur while the function worked
1173 */
1175 {
1178 ret,
1182 /* Current node is the root of the tree or will be root of the tree */
1184 /*
1185 * The root can not have parents.
1186 * Release nodes which previously were obtained as
1187 * parents of the current node neighbors.
1188 */
1198 }
1200 /* Get parent FL[path_offset] of L[path_offset]. */
1203 /* Current node is not the first child of its parent. */
1210 /*
1211 * Calculate current parent of L[path_offset], which is the
1212 * left neighbor of the current node. Calculate current
1213 * common parent of L[path_offset] and the current node.
1214 * Note that CFL[path_offset] not equal FL[path_offset] and
1215 * CFL[path_offset] not equal F[path_offset].
1216 * Calculate lkey[path_offset].
1217 */
1222 }
1233 /* Get parent FR[h] of R[h]. */
1235 /* Current node is the last child of F[h]. FR[h] != F[h]. */
1237 /*
1238 * Calculate current parent of R[h], which is the right
1239 * neighbor of F[h]. Calculate current common parent of
1240 * R[h] and current node. Note that CFR[h] not equal
1241 * FR[path_offset] and CFR[h] not equal F[h].
1242 */
1248 /* Current node is not the last child of its parent F[h]. */
1254 }
1257 /* New initialization of FR[path_offset]. */
1261 /* New initialization of CFR[path_offset]. */
1269 }
1271 /*
1272 * it is possible to remove node as result of shiftings to
1273 * neighbors even when we insert or paste item.
1274 */
1277 {
1288 /* shifting may merge items which might save space */
1289 -
1290 ((!h
1292 -
1296 /* node can not be removed */
1298 /* new item fits into node S[h] without any shifting */
1305 }
1306 }
1309 }
1311 /*
1312 * Check whether current node S[h] is balanced when increasing its size by
1313 * Inserting or Pasting.
1314 * Calculate parameters for balancing for current level h.
1315 * Parameters:
1316 * tb tree_balance structure;
1317 * h current level of the node;
1318 * inum item number in S[h];
1319 * mode i - insert, p - paste;
1320 * Returns: 1 - schedule occurred;
1321 * 0 - balancing for higher levels needed;
1322 * -1 - no balancing for higher levels needed;
1323 * -2 - no disk space.
1324 */
1325 /* ip means Inserting or Pasting */
1327 {
1329 /*
1330 * Number of bytes that must be inserted into (value is negative
1331 * if bytes are deleted) buffer which contains node being balanced.
1332 * The mnemonic is that the attempted change in node space used
1333 * level is levbytes bytes.
1334 */
1340 /*
1341 * nver is short for number of vertixes, and lnver is the number if
1342 * we shift to the left, rnver is the number if we shift to the
1343 * right, and lrnver is the number if we shift in both directions.
1344 * The goal is to minimize first the number of vertixes, and second,
1345 * the number of vertixes whose contents are changed by shifting,
1346 * and third the number of uncached vertixes whose contents are
1347 * changed by shifting and must be read from disk.
1348 */
1351 /*
1352 * used at leaf level only, S0 = S[0] is the node being balanced,
1353 * sInum [ I = 0,1,2 ] is the number of items that will
1354 * remain in node SI after balancing. S1 and S2 are new
1355 * nodes that might be created.
1356 */
1358 /*
1359 * we perform 8 calls to get_num_ver(). For each call we
1360 * calculate five parameters. where 4th parameter is s1bytes
1361 * and 5th - s2bytes
1362 *
1363 * s0num, s1num, s2num for 8 cases
1364 * 0,1 - do not shift and do not shift but bottle
1365 * 2 - shift only whole item to left
1366 * 3 - shift to left and bottle as much as possible
1367 * 4,5 - shift to right (whole items and as much as possible
1368 * 6,7 - shift to both directions (whole items and as much as possible)
1369 */
1372 /* Sh is the node whose balance is currently being checked */
1378 /* Calculate balance parameters for creating new root. */
1384 /* no balancing for higher levels needed */
1395 }
1396 }
1398 /* get parents of S[h] neighbors. */
1405 /* get free space of neighbors */
1409 /* and new item fits into node S[h] without any shifting */
1411 NO_BALANCING_NEEDED)
1416 /*
1417 * determine maximal number of items we can shift to the left
1418 * neighbor (in tb structure) and the maximal number of bytes
1419 * that can flow to the left neighbor from the left most liquid
1420 * item that cannot be shifted from S[0] entirely (returned value)
1421 */
1424 /*
1425 * determine maximal number of items we can shift to the right
1426 * neighbor (in tb structure) and the maximal number of bytes
1427 * that can flow to the right neighbor from the right most liquid
1428 * item that cannot be shifted from S[0] entirely (returned value)
1429 */
1432 /*
1433 * all contents of internal node S[h] can be moved into its
1434 * neighbors, S[h] will be removed after balancing
1435 */
1439 /*
1440 * Since we are working on internal nodes, and our internal
1441 * nodes have fixed size entries, then we can balance by the
1442 * number of items rather than the space they consume. In this
1443 * routine we set the left node equal to the right node,
1444 * allowing a difference of less than or equal to 1 child
1445 * pointer.
1446 */
1447 to_r =
1454 }
1456 /*
1457 * this checks balance condition, that any two neighboring nodes
1458 * can not fit in one node
1459 */
1468 /*
1469 * all contents of S[0] can be moved into its neighbors
1470 * S[0] will be removed after balancing.
1471 */
1475 /*
1476 * why do we perform this check here rather than earlier??
1477 * Answer: we can win 1 node in some cases above. Moreover we
1478 * checked it above, when we checked, that S[0] is not removable
1479 * in principle
1480 */
1482 /* new item fits into node S[h] without any shifting */
1488 }
1490 {
1492 /* regular overflowing of the node */
1494 /*
1495 * get_num_ver works in 2 modes (FLOW & NO_FLOW)
1496 * lpar, rpar - number of items we can shift to left/right
1497 * neighbor (including splitting item)
1498 * nset, lset, rset, lrset - shows, whether flowing items
1499 * give better packing
1500 */
1501 #define FLOW 1
1504 /* we choose one of the following */
1505 #define NOTHING_SHIFT_NO_FLOW 0
1506 #define NOTHING_SHIFT_FLOW 5
1507 #define LEFT_SHIFT_NO_FLOW 10
1508 #define LEFT_SHIFT_FLOW 15
1509 #define RIGHT_SHIFT_NO_FLOW 20
1510 #define RIGHT_SHIFT_FLOW 25
1511 #define LR_SHIFT_NO_FLOW 30
1512 #define LR_SHIFT_FLOW 35
1517 /*
1518 * calculate number of blocks S[h] must be split into when
1519 * nothing is shifted to the neighbors, as well as number of
1520 * items in each part of the split node (s012 numbers),
1521 * and number of bytes (s1bytes) of the shared drop which
1522 * flow to S1 if any
1523 */
1532 /*
1533 * note, that in this case we try to bottle
1534 * between S[0] and S1 (S1 - the first new node)
1535 */
1541 }
1543 /*
1544 * calculate number of blocks S[h] must be split into when
1545 * l_shift_num first items and l_shift_bytes of the right
1546 * most liquid item to be shifted are shifted to the left
1547 * neighbor, as well as number of items in each part of the
1548 * splitted node (s012 numbers), and number of bytes
1549 * (s1bytes) of the shared drop which flow to S1 if any
1550 */
1560 lpar -
1566 }
1568 /*
1569 * calculate number of blocks S[h] must be split into when
1570 * r_shift_num first items and r_shift_bytes of the left most
1571 * liquid item to be shifted are shifted to the right neighbor,
1572 * as well as number of items in each part of the splitted
1573 * node (s012 numbers), and number of bytes (s1bytes) of the
1574 * shared drop which flow to S1 if any
1575 */
1581 rbytes !=
1597 }
1599 /*
1600 * calculate number of blocks S[h] must be split into when
1601 * items are shifted in both directions, as well as number
1602 * of items in each part of the splitted node (s012 numbers),
1603 * and number of bytes (s1bytes) of the shared drop which
1604 * flow to S1 if any
1605 */
1612 rbytes !=
1620 lpar -
1629 }
1631 /*
1632 * Our general shifting strategy is:
1633 * 1) to minimized number of new nodes;
1634 * 2) to minimized number of neighbors involved in shifting;
1635 * 3) to minimized number of disk reads;
1636 */
1638 /* we can win TWO or ONE nodes by shifting in both directions */
1649 else
1658 }
1660 /*
1661 * if shifting doesn't lead to better packing
1662 * then don't shift
1663 */
1668 }
1670 /*
1671 * now we know that for better packing shifting in only one
1672 * direction either to the left or to the right is required
1673 */
1675 /*
1676 * if shifting to the left is better than
1677 * shifting to the right
1678 */
1680 SET_PAR_SHIFT_LEFT;
1682 }
1684 /*
1685 * if shifting to the right is better than
1686 * shifting to the left
1687 */
1689 SET_PAR_SHIFT_RIGHT;
1691 }
1693 /*
1694 * now shifting in either direction gives the same number
1695 * of nodes and we can make use of the cached neighbors
1696 */
1698 SET_PAR_SHIFT_LEFT;
1700 }
1702 /*
1703 * shift to the right independently on whether the
1704 * right neighbor in cache or not
1705 */
1706 SET_PAR_SHIFT_RIGHT;
1708 }
1709 }
1711 /*
1712 * Check whether current node S[h] is balanced when Decreasing its size by
1713 * Deleting or Cutting for INTERNAL node of S+tree.
1714 * Calculate parameters for balancing for current level h.
1715 * Parameters:
1716 * tb tree_balance structure;
1717 * h current level of the node;
1718 * inum item number in S[h];
1719 * mode i - insert, p - paste;
1720 * Returns: 1 - schedule occurred;
1721 * 0 - balancing for higher levels needed;
1722 * -1 - no balancing for higher levels needed;
1723 * -2 - no disk space.
1724 *
1725 * Note: Items of internal nodes have fixed size, so the balance condition for
1726 * the internal part of S+tree is as for the B-trees.
1727 */
1729 {
1732 /*
1733 * Sh is the node whose balance is currently being checked,
1734 * and Fh is its father.
1735 */
1745 /*
1746 * using tb->insert_size[h], which is negative in this case,
1747 * create_virtual_node calculates:
1748 * new_nr_item = number of items node would have if operation is
1749 * performed without balancing (new_nr_item);
1750 */
1754 /* no balancing for higher levels needed */
1758 }
1759 /*
1760 * new_nr_item == 0.
1761 * Current root will be deleted resulting in
1762 * decrementing the tree height.
1763 */
1766 }
1771 /* get free space of neighbors */
1775 /* determine maximal number of items we can fit into neighbors */
1779 /*
1780 * Balance condition for the internal node is valid.
1781 * In this case we balance only if it leads to better packing.
1782 */
1784 /*
1785 * Here we join S[h] with one of its neighbors,
1786 * which is impossible with greater values of new_nr_item.
1787 */
1789 /* All contents of S[h] can be moved to L[h]. */
1794 order_L =
1797 h)) ==
1804 }
1806 /* All contents of S[h] can be moved to R[h]. */
1811 order_R =
1814 h)) ==
1821 }
1822 }
1824 /*
1825 * All contents of S[h] can be moved to the neighbors
1826 * (L[h] & R[h]).
1827 */
1831 to_r =
1838 }
1840 /* Balancing does not lead to better packing. */
1843 }
1845 /*
1846 * Current node contain insufficient number of items.
1847 * Balancing is required.
1848 */
1849 /* Check whether we can merge S[h] with left neighbor. */
1856 order_L =
1859 h)) ==
1862 KEY_SIZE);
1865 }
1867 /* Check whether we can merge S[h] with right neighbor. */
1872 order_R =
1877 KEY_SIZE);
1880 }
1882 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1886 to_r =
1893 }
1895 /* For internal nodes try to borrow item from a neighbor */
1898 /* Borrow one or two items from caching neighbor */
1902 from_l =
1907 }
1913 }
1915 /*
1916 * Check whether current node S[h] is balanced when Decreasing its size by
1917 * Deleting or Truncating for LEAF node of S+tree.
1918 * Calculate parameters for balancing for current level h.
1919 * Parameters:
1920 * tb tree_balance structure;
1921 * h current level of the node;
1922 * inum item number in S[h];
1923 * mode i - insert, p - paste;
1924 * Returns: 1 - schedule occurred;
1925 * 0 - balancing for higher levels needed;
1926 * -1 - no balancing for higher levels needed;
1927 * -2 - no disk space.
1928 */
1930 {
1933 /*
1934 * Number of bytes that must be deleted from
1935 * (value is negative if bytes are deleted) buffer which
1936 * contains node being balanced. The mnemonic is that the
1937 * attempted change in node space used level is levbytes bytes.
1938 */
1941 /* the maximal item size */
1944 /*
1945 * S0 is the node whose balance is currently being checked,
1946 * and F0 is its father.
1947 */
1965 }
1970 /* get free space of neighbors */
1976 /* if 3 leaves can be merge to one, set parameters and return */
1980 /*
1981 * determine maximal number of items we can shift to the left/right
1982 * neighbor and the maximal number of bytes that can flow to the
1983 * left/right neighbor from the left/right most liquid item that
1984 * cannot be shifted from S[0] entirely
1985 */
1989 /* check whether we can merge S with left neighbor. */
1991 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 */
1997 /* set parameter to merge S[0] with its left neighbor */
2000 }
2002 /* check whether we can merge S[0] with right neighbor. */
2006 }
2008 /*
2009 * All contents of S[0] can be moved to the neighbors (L[0] & R[0]).
2010 * Set parameters and return
2011 */
2015 /* Balancing is not required. */
2019 }
2021 /*
2022 * Check whether current node S[h] is balanced when Decreasing its size by
2023 * Deleting or Cutting.
2024 * Calculate parameters for balancing for current level h.
2025 * Parameters:
2026 * tb tree_balance structure;
2027 * h current level of the node;
2028 * inum item number in S[h];
2029 * mode d - delete, c - cut.
2030 * Returns: 1 - schedule occurred;
2031 * 0 - balancing for higher levels needed;
2032 * -1 - no balancing for higher levels needed;
2033 * -2 - no disk space.
2034 */
2036 {
2042 else
2044 }
2046 /*
2047 * Check whether current node S[h] is balanced.
2048 * Calculate parameters for balancing for current level h.
2049 * Parameters:
2050 *
2051 * tb tree_balance structure:
2052 *
2053 * tb is a large structure that must be read about in the header
2054 * file at the same time as this procedure if the reader is
2055 * to successfully understand this procedure
2056 *
2057 * h current level of the node;
2058 * inum item number in S[h];
2059 * mode i - insert, p - paste, d - delete, c - cut.
2060 * Returns: 1 - schedule occurred;
2061 * 0 - balancing for higher levels needed;
2062 * -1 - no balancing for higher levels needed;
2063 * -2 - no disk space.
2064 */
2071 {
2085 /* Calculate balance parameters when size of node is increasing. */
2089 /* Calculate balance parameters when size of node is decreasing. */
2091 }
2093 /* Check whether parent at the path is the really parent of the current node.*/
2095 {
2101 /* We are in the root or in the new root. */
2109 /* Root is not changed. */
2113 }
2114 /* Root is changed and we must recalculate the path. */
2116 }
2118 /* Parent in the path is not in the tree. */
2128 /* Parent in the path is not parent of the current node in the tree. */
2139 }
2141 /*
2142 * Parent in the path is unlocked and really parent
2143 * of the current node.
2144 */
2146 }
2148 /*
2149 * Using lnum[h] and rnum[h] we should determine what neighbors
2150 * of S[h] we
2151 * need in order to balance S[h], and get them if necessary.
2152 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
2153 * CARRY_ON - schedule didn't occur while the function worked;
2154 */
2156 {
2167 /* We need left neighbor to balance S[h]. */
2175 child_position =
2189 }
2204 }
2206 /* We need right neighbor to balance S[path_offset]. */
2213 path_offset) >=
2217 child_position =
2229 }
2241 }
2243 }
2246 {
2251 #define MIN_NAME_LEN 1
2261 }
2263 /*
2264 * maybe we should fail balancing we are going to perform when kmalloc
2265 * fails several times. But now it will loop until kmalloc gets
2266 * required memory
2267 */
2269 {
2276 /* we have to allocate more memory for virtual node */
2279 /* free memory allocated before */
2281 /* this is not needed if kfree is atomic */
2283 }
2285 /* virtual node requires now more memory */
2288 /* get memory for virtual item */
2291 /*
2292 * getting memory with GFP_KERNEL priority may involve
2293 * balancing now (due to indirect_to_direct conversion
2294 * on dcache shrinking). So, release path and collected
2295 * resources here
2296 */
2301 }
2305 }
2308 }
2314 }
2316 #ifdef CONFIG_REISERFS_CHECK
2320 {
2325 "reference counter for buffer %s[%d] "
2352 }
2353 }
2354 #else
2358 {;
2359 }
2360 #endif
2363 {
2365 }
2368 {
2370 #ifdef CONFIG_REISERFS_CHECK
2372 #endif
2382 /*
2383 * if I understand correctly, we can only
2384 * be sure the last buffer in the path is
2385 * in the tree --clm
2386 */
2387 #ifdef CONFIG_REISERFS_CHECK
2391 PATH_OFFSET_PBUFFER
2396 #endif
2398 PATH_OFFSET_PBUFFER
2400 i))) {
2401 locked =
2403 i);
2404 }
2405 }
2406 }
2409 i++) {
2420 }
2429 }
2438 }
2440 }
2451 }
2460 }
2469 }
2470 }
2471 }
2473 /*
2474 * as far as I can tell, this is not required. The FEB list
2475 * seems to be full of newly allocated nodes, which will
2476 * never be locked, dirty, or anything else.
2477 * To be safe, I'm putting in the checks and waits in.
2478 * For the moment, they are needed to keep the code in
2479 * journal.c from complaining about the buffer.
2480 * That code is inside CONFIG_REISERFS_CHECK as well. --clm
2481 */
2487 }
2488 }
2492 #ifdef CONFIG_REISERFS_CHECK
2493 repeat_counter++;
2496 "too many iterations waiting "
2497 "for buffer to unlock "
2500 /* Don't loop forever. Try to recover from possible error. */
2504 }
2505 #endif
2511 }
2516 }
2518 /*
2519 * Prepare for balancing, that is
2520 * get all necessary parents, and neighbors;
2521 * analyze what and where should be moved;
2522 * get sufficient number of new nodes;
2523 * Balancing will start only after all resources will be collected at a time.
2524 *
2525 * When ported to SMP kernels, only at the last moment after all needed nodes
2526 * are collected in cache, will the resources be locked using the usual
2527 * textbook ordered lock acquisition algorithms. Note that ensuring that
2528 * this code neither write locks what it does not need to write lock nor locks
2529 * out of order will be a pain in the butt that could have been avoided.
2530 * Grumble grumble. -Hans
2531 *
2532 * fix is meant in the sense of render unchanging
2533 *
2534 * Latency might be improved by first gathering a list of what buffers
2535 * are needed and then getting as many of them in parallel as possible? -Hans
2536 *
2537 * Parameters:
2538 * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2539 * tb tree_balance structure;
2540 * inum item number in S[h];
2541 * pos_in_item - comment this if you can
2542 * ins_ih item head of item being inserted
2543 * data inserted item or data to be pasted
2544 * Returns: 1 - schedule occurred while the function worked;
2545 * 0 - schedule didn't occur while the function worked;
2546 * -1 - if no_disk_space
2547 */
2551 {
2555 /*
2556 * we set wait_tb_buffers_run when we have to restore any dirty
2557 * bits cleared during wait_tb_buffers_run
2558 */
2568 /*
2569 * we prepare and log the super here so it will already be in the
2570 * transaction when do_balance needs to change it.
2571 * This way do_balance won't have to schedule when trying to prepare
2572 * the super for logging
2573 */
2581 /* if it possible in indirect_to_direct conversion */
2588 }
2589 #ifdef CONFIG_REISERFS_CHECK
2594 }
2598 "not uptodate at the beginning of fix_nodes "
2602 /* Check parameters. */
2607 "item number %d (in S0 - %d) in case "
2617 "item number(%d); mode = %c "
2621 }
2626 }
2627 #endif
2630 /* FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat */
2633 /* Starting from the leaf level; for all levels h of the tree. */
2643 /* No balancing for higher levels needed. */
2649 /*
2650 * ok, analysis and resource gathering
2651 * are complete
2652 */
2654 }
2656 }
2662 /*
2663 * No disk space, or schedule occurred and analysis may be
2664 * invalid and needs to be redone.
2665 */
2670 /*
2671 * We have a positive insert size but no nodes exist on this
2672 * level, this means that we are creating a new root.
2673 */
2682 /*
2683 * The tree needs to be grown, so this node S[h]
2684 * which is the root node is split into two nodes,
2685 * and a new node (S[h+1]) will be created to
2686 * become the root node.
2687 */
2696 DC_SIZE;
2702 }
2712 }
2716 }
2718 repeat:
2719 /*
2720 * fix_nodes was unable to perform its calculation due to
2721 * filesystem got changed under us, lack of free disk space or i/o
2722 * failure. If the first is the case - the search will be
2723 * repeated. For now - free all resources acquired so far except
2724 * for the new allocated nodes
2725 */
2726 {
2729 /* Release path buffers. */
2734 }
2735 /* brelse all resources collected for balancing */
2747 tb->
2750 tb->
2752 }
2767 }
2772 reiserfs_restore_prepared_buffer
2774 }
2775 }
2777 }
2779 }
2782 {
2785 /* Release path buffers. */
2788 /* brelse all resources collected for balancing */
2803 }
2805 /* deal with list of allocated (used and unused) nodes */
2809 /*
2810 * de-allocated block which was not used by
2811 * balancing and bforget about buffer for it
2812 */
2816 }
2818 /* release used as new nodes including a new root */
2820 }
2821 }
2825 }