| blob | 9a3c68cf6026ae0405ef91c07f3ec9ef02854f1a |
1 /*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
5 /* Now we have all buffers that must be used in balancing of the tree */
6 /* Further calculations can not cause schedule(), and thus the buffer */
7 /* tree will be stable until the balancing will be finished */
8 /* balance the tree according to the analysis made before, */
9 /* and using buffers obtained after all above. */
11 /**
12 ** balance_leaf_when_delete
13 ** balance_leaf
14 ** do_balance
15 **
16 **/
18 #include <asm/uaccess.h>
19 #include <linux/time.h>
21 #include <linux/buffer_head.h>
22 #include <linux/kernel.h>
26 {
31 }
35 {
40 }
44 {
49 }
54 {
59 }
63 {
66 }
68 #define do_balance_mark_internal_dirty do_balance_mark_leaf_dirty
69 #define do_balance_mark_sb_dirty do_balance_mark_leaf_dirty
71 /* summary:
72 if deleting something ( tb->insert_size[0] < 0 )
73 return(balance_leaf_when_delete()); (flag d handled here)
74 else
75 if lnum is larger than 0 we put items into the left node
76 if rnum is larger than 0 we put items into the right node
77 if snum1 is larger than 0 we put items into the new node s1
78 if snum2 is larger than 0 we put items into the new node s2
79 Note that all *num* count new items being created.
81 It would be easier to read balance_leaf() if each of these summary
82 lines was a separate procedure rather than being inlined. I think
83 that there are many passages here and in balance_leaf_when_delete() in
84 which two calls to one procedure can replace two passages, and it
85 might save cache space and improve software maintenance costs to do so.
87 Vladimir made the perceptive comment that we should offload most of
88 the decision making in this function into fix_nodes/check_balance, and
89 then create some sort of structure in tb that says what actions should
90 be performed by do_balance.
92 -Hans */
94 /* Balance leaf node in case of delete or cut: insert_size[0] < 0
95 *
96 * lnum, rnum can have values >= -1
97 * -1 means that the neighbor must be joined with S
98 * 0 means that nothing should be done with the neighbor
99 * >0 means to shift entirely or partly the specified number of items to the neighbor
100 */
102 {
120 /* Delete or truncate the item */
140 }
141 }
152 /* UFS unlink semantics are such that you can only delete one directory entry at a time. */
153 /* when we cut a directory tb->insert_size[0] means number of entries to be cut (always 1) */
165 }
172 }
174 }
184 }
186 /* the rule is that no shifting occurs unless by shifting a node can be freed */
192 /* all contents of all the 3 buffers will be in L[0] */
210 }
211 /* all contents of all the 3 buffers will be in R[0] */
213 NULL);
217 /* right_delimiting_key is correct in R[0] */
225 }
229 /* all contents of L[0] and S[0] will be in L[0] */
235 }
236 /* a part of contents of S[0] will be in L[0] and the rest part of S[0] will be in R[0] */
257 }
260 /* all contents of R[0] and S[0] will be in R[0] */
264 }
269 }
271 static int balance_leaf(struct tree_balance *tb, struct item_head *ih, /* item header of inserted item (this is on little endian) */
274 (see comment to do_balance) */
276 must be inserted into the next higher level. This insertion
277 consists of a key or two keys and their corresponding
278 pointers */
280 )
281 {
284 of the affected item */
288 into S_new (includes partially shifted
289 items) */
291 if it is a directory item
292 it is the number of entries from the item that are shifted into S_new
293 else
294 it is the number of bytes from the item that are shifted into S_new
295 */
303 /* Make balance in case insert_size[0] < 0 */
312 /* for indirect item pos_in_item is measured in unformatted node
313 pointers. Recalculate to bytes */
319 /* Shift lnum[0] items from S[0] to the left neighbor L[0] */
321 /* new item or it part falls to L[0], shift it too */
328 /* part of new item falls into L[0] */
334 /* Calculate item length to insert to S[0] */
336 /* Calculate and check item length to insert to L[0] */
343 /* Insert new item into L[0] */
351 /* Calculate key component, item length and body to insert into S[0] */
366 /* new item in whole falls into L[0] */
367 /* Shift lnum[0]-1 items to L[0] */
369 /* Insert new item into L[0] */
374 }
380 /* we must shift the part of the appended item */
385 /* directory item */
387 /* new directory entry falls into L[0] */
391 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 entries from given directory item */
396 }
398 /* Append given directory entry to directory item */
400 leaf_paste_in_buffer(&bi, n + item_pos - ret_val, l_pos_in_item, tb->insert_size[0], body, zeros_num);
402 /* previous string prepared space for pasting new entry, following string pastes this entry */
404 /* when we have merge directory item, pos_in_item has been changed too */
406 /* paste new directory entry. 1 is entry number */
412 /* new directory item doesn't fall into L[0] */
413 /* Shift lnum[0]-1 items in whole. Shift lbytes directory entries from directory item number lnum[0] */
415 }
416 /* Calculate new position to append in item body */
419 /* regular object */
426 /* appended item will be in L[0] in whole */
429 /* this bytes number must be appended to the last item of L[h] */
432 /* Calculate new insert_size[0] */
440 /* Append to body of item in L[0] */
442 leaf_paste_in_buffer
447 /* 0-th item in S0 can be only of DIRECT type when l_n != 0 */
448 {
459 }
460 /* update key of first item in S0 */
464 /* update left delimiting key */
467 }
469 /* Calculate new body, position in item and insert_size[0] */
483 /* Calculate position in item for append in S[0] */
488 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
490 }
491 }
496 if (!item_pos && op_is_left_mergeable(B_N_PKEY(tbS0, 0), tbS0->b_size)) { /* if we paste into first item of S[0] and it is left mergable */
497 /* then increment pos_in_item by the size of the last item in L[0] */
501 else
503 }
505 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
507 /* Append to body of item in L[0] */
510 pos_in_item,
514 /* if appended item is directory, paste entry */
522 /* if appended item is indirect item, put unformatted node into un list */
527 }
531 "lnum > 0: unexpected mode: "
534 }
536 /* new item doesn't fall into L[0] */
538 }
539 }
541 /* tb->lnum[0] > 0 */
542 /* Calculate new item position */
546 /* shift rnum[0] items from S[0] to the right neighbor R[0] */
552 if (item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1) { /* part of new item falls into R[0] */
556 loff_t offset;
561 /* Remember key component and item length */
565 /* Calculate key component and item length to insert into R[0] */
566 offset = le_ih_k_offset(ih) + ((old_len - tb->rbytes) << (is_indirect_le_ih(ih) ? tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT : 0));
569 /* Insert part of the item into R[0] */
578 }
581 r_zeros_number);
583 /* Replace right delimiting key by first key in R[0] */
587 /* Calculate key component and item length to insert into S[0] */
595 /* Shift rnum[0]-1 items to R[0] */
597 /* Insert new item into R[0] */
607 }
609 }
613 }
619 if (item_pos == n - tb->rnum[0] && tb->rbytes != -1) { /* we must shift the part of the appended item */
628 pos_in_item)
629 /* new directory entry falls into R[0] */
630 {
636 /* Shift rnum[0]-1 items in whole. Shift rbytes-1 directory entries from directory item number rnum[0] */
638 /* Paste given directory entry to directory item */
642 /* paste entry */
648 /* change delimiting keys */
650 }
653 pos_in_item++;
657 }
663 /* Calculate number of bytes which must be shifted from appended item */
670 pos_in_item, ih_item_len
674 /* Calculate number of bytes which must remain in body after appending to R[0] */
678 {
685 }
690 }
691 /* k_offset (B_N_PKEY(tb->R[0],0)) += n_rem;
692 k_offset (B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])) += n_rem;*/
695 /* Append part of body into R[0] */
704 }
711 #if 0
714 #endif
716 }
719 pos_in_item++;
720 }
726 /* append item in R[0] */
731 }
733 /* paste new entry, if item is directory item */
745 /* update delimiting keys */
747 }
748 }
753 }
757 }
763 }
765 }
767 /* tb->rnum[0] > 0 */
773 /* if while adding to a node we discover that it is possible to split
774 it in two, and merge the left part into the left neighbor and the
775 right part into the right neighbor, eliminating the node */
780 /* if insertion was done before 0-th position in R[0], right
781 delimiting key of the tb->L[0]'s and left delimiting key are
782 not set correctly */
790 }
794 }
796 /* Fill new nodes that appear in place of S[0] */
798 /* I am told that this copying is because we need an array to enable
799 the looping code. -Hans */
808 /* here we shift from S to S_new nodes */
812 /* initialized block type and tree level */
821 if (item_pos == n - snum[i] + 1 && sbytes[i] != -1) { /* part of new item falls into S_new[i] */
826 /* Move snum[i]-1 items from S[0] to S_new[i] */
830 /* Remember key component and item length */
835 /* Calculate key component and item length to insert into S_new[i] */
837 ((old_len - sbytes[i]) << (is_indirect_le_ih(ih) ? tb->tb_sb-> s_blocksize_bits - UNFM_P_SHIFT : 0)));
841 /* Insert part of the item into S_new[i] before 0-th item */
851 }
855 /* Calculate key component and item length to insert into S[i] */
861 /* Shift snum[0] - 1 items to S_new[i] (sbytes[i] of split item) */
865 /* Insert new item into S_new[i] */
871 }
872 }
878 }
891 /* we append to directory item */
898 /* new directory entry falls into S_new[i] */
905 /* Shift snum[i]-1 items in whole. Shift sbytes[i] directory entries from directory item number snum[i] */
907 /* Paste given directory entry to directory item */
911 /* paste new directory entry */
916 pos_in_item++;
919 }
928 /* Calculate number of bytes which must be shifted from appended item */
934 /* Calculate number of bytes which must remain in body after append to S_new[i] */
938 /* Append part of body into S_new[0] */
947 }
952 {
959 set_le_ih_k_offset(tmp, le_ih_k_offset(tmp) + (n_rem << (tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT)));
962 }
963 }
967 pos_in_item++;
968 }
970 /* item falls wholly into S_new[i] */
971 {
975 #ifdef CONFIG_REISERFS_CHECK
983 "pos_in_item "
984 "must be equal "
995 leaf_mi);
997 /* paste into item */
1001 pos_in_item,
1013 );
1014 }
1016 /* if we paste to indirect item update ih_free_space */
1020 }
1021 }
1027 }
1033 }
1042 }
1044 /* if the affected item was not wholly shifted then we perform all necessary operations on that part or whole of the
1045 affected item which remains in S */
1046 if (0 <= item_pos && item_pos < tb->s0num) { /* if we must insert or append into buffer S[0] */
1052 zeros_num);
1054 /* If we insert the first key change the delimiting key */
1058 }
1065 /* when directory, may be new entry already pasted */
1072 /* prepare space */
1076 zeros_num);
1078 /* paste entry */
1088 }
1090 }
1102 #if 0
1105 UNFM_P_SIZE,
1107 UNFM_P_SIZE,
1108 tb->
1110 #endif
1112 }
1114 }
1115 #ifdef CONFIG_REISERFS_CHECK
1121 "insert_size "
1122 "must be 0 "
1125 }
1126 }
1129 }
1131 }
1132 }
1133 #ifdef CONFIG_REISERFS_CHECK
1139 }
1144 /* Make empty node */
1146 {
1157 }
1159 /* Get first empty buffer */
1161 {
1179 }
1181 /* This is now used because reiserfs_free_block has to be able to
1182 ** schedule.
1183 */
1185 {
1196 }
1199 }
1202 {
1204 b_blocknr_t blocknr;
1211 blocknr);
1215 }
1216 }
1217 }
1220 {
1228 }
1230 /* Replace n_dest'th key in buffer dest by n_src'th key of buffer src.*/
1233 {
1240 dest);
1248 /* source buffer contains leaf node */
1250 KEY_SIZE);
1251 else
1253 KEY_SIZE);
1256 }
1259 {
1268 else
1270 }
1273 {
1282 else
1284 }
1286 #ifdef CONFIG_REISERFS_CHECK
1291 {
1311 }
1312 }
1313 }
1317 {
1322 }
1324 }
1327 {
1332 "occurred based on cur_tb not being null at "
1333 "this point in code. do_balance cannot properly "
1334 "handle concurrent tree accesses on a same "
1336 }
1338 /* double check that buffers that we will modify are unlocked. (fix_nodes should already have
1339 prepped all of these for us). */
1345 }
1351 }
1357 }
1360 {
1369 }
1370 }
1379 }
1380 }
1393 "B_FREE_SPACE (PATH_H_PBUFFER(tb->tb_path,0)) = %d; "
1395 left,
1402 right);
1404 }
1405 }
1408 {
1412 }
1415 {
1418 /* check all internal nodes */
1426 }
1428 }
1430 #endif
1432 /* Now we have all of the buffers that must be used in balancing of
1433 the tree. We rely on the assumption that schedule() will not occur
1434 while do_balance works. ( Only interrupt handlers are acceptable.)
1435 We balance the tree according to the analysis made before this,
1436 using buffers already obtained. For SMP support it will someday be
1437 necessary to add ordered locking of tb. */
1439 /* Some interesting rules of balancing:
1441 we delete a maximum of two nodes per level per balancing: we never
1442 delete R, when we delete two of three nodes L, S, R then we move
1443 them into R.
1445 we only delete L if we are deleting two nodes, if we delete only
1446 one node we delete S
1448 if we shift leaves then we shift as much as we can: this is a
1449 deliberate policy of extremism in node packing which results in
1450 higher average utilization after repeated random balance operations
1451 at the cost of more memory copies and more balancing as a result of
1452 small insertions to full nodes.
1454 if we shift internal nodes we try to evenly balance the node
1455 utilization, with consequent less balancing at the cost of lower
1456 utilization.
1458 one could argue that the policy for directories in leaves should be
1459 that of internal nodes, but we will wait until another day to
1460 evaluate this.... It would be nice to someday measure and prove
1461 these assumptions as to what is optimal....
1463 */
1466 {
1467 /* use print_cur_tb() to see initial state of struct
1468 tree_balance */
1470 /* store_print_tb (tb); */
1472 /* do not delete, just comment it out */
1473 /* print_tb(flag, PATH_LAST_POSITION(tb->tb_path), tb->tb_path->pos_in_item, tb,
1474 "check");*/
1476 #ifdef CONFIG_REISERFS_CHECK
1478 #endif
1479 }
1482 {
1484 #ifdef CONFIG_REISERFS_CHECK
1488 #endif
1490 /* reiserfs_free_block is no longer schedule safe. So, we need to
1491 ** put the buffers we want freed on the thrown list during do_balance,
1492 ** and then free them now
1493 */
1497 /* release all nodes hold to perform the balancing */
1501 }
1508 c - cut, p - paste
1510 Cut means delete part of an item
1511 (includes removing an entry from a
1512 directory).
1514 Delete means delete whole item.
1516 Insert means add a new item into the
1517 tree.
1519 Paste means to append to the end of an
1520 existing file or to insert a directory
1521 entry. */
1525 we sometimes determine what
1526 must be inserted into the next
1527 higher level. This insertion
1528 consists of a key or two keys
1529 and their corresponding
1530 pointers */
1532 level */
1540 }
1541 /* if we have no real work to do */
1547 }
1552 /* balance leaf returns 0 except if combining L R and S into
1553 one node. see balance_internal() for explanation of this
1554 line of code. */
1558 #ifdef CONFIG_REISERFS_CHECK
1560 #endif
1562 /* Balance internal level of the tree. */
1564 child_pos =
1569 }