1 /* 2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README 3 */ 4 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 **/ 36 37 #include <linux/time.h> 38 #include <linux/slab.h> 39 #include <linux/string.h> 40 #include "reiserfs.h" 41 #include <linux/buffer_head.h> 42 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. */ 56 57 /* taking item number in virtual node, returns number of item, that it has in source buffer */ 58 static inline int old_item_num(int new_num, int affected_item_num, int mode) 59 { 60 if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num) 61 return new_num; 62 63 if (mode == M_INSERT) { 64 65 RFALSE(new_num == 0, 66 "vs-8005: for INSERT mode and item number of inserted item"); 67 68 return new_num - 1; 69 } 70 71 RFALSE(mode != M_DELETE, 72 "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'", 73 mode); 74 /* delete mode */ 75 return new_num + 1; 76 } 77 78 static void create_virtual_node(struct tree_balance *tb, int h) 79 { 80 struct item_head *ih; 81 struct virtual_node *vn = tb->tb_vn; 82 int new_num; 83 struct buffer_head *Sh; /* this comes from tb->S[h] */ 84 85 Sh = PATH_H_PBUFFER(tb->tb_path, h); 86 87 /* size of changed node */ 88 vn->vn_size = 89 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h]; 90 91 /* for internal nodes array if virtual items is not created */ 92 if (h) { 93 vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE); 94 return; 95 } 96 97 /* number of items in virtual node */ 98 vn->vn_nr_item = 99 B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) - 100 ((vn->vn_mode == M_DELETE) ? 1 : 0); 101 102 /* first virtual item */ 103 vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1); 104 memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item)); 105 vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item); 106 107 /* first item in the node */ 108 ih = B_N_PITEM_HEAD(Sh, 0); 109 110 /* define the mergeability for 0-th item (if it is not being deleted) */ 111 if (op_is_left_mergeable(&(ih->ih_key), Sh->b_size) 112 && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num)) 113 vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE; 114 115 /* go through all items those remain in the virtual node (except for the new (inserted) one) */ 116 for (new_num = 0; new_num < vn->vn_nr_item; new_num++) { 117 int j; 118 struct virtual_item *vi = vn->vn_vi + new_num; 119 int is_affected = 120 ((new_num != vn->vn_affected_item_num) ? 0 : 1); 121 122 if (is_affected && vn->vn_mode == M_INSERT) 123 continue; 124 125 /* get item number in source node */ 126 j = old_item_num(new_num, vn->vn_affected_item_num, 127 vn->vn_mode); 128 129 vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE; 130 vi->vi_ih = ih + j; 131 vi->vi_item = B_I_PITEM(Sh, ih + j); 132 vi->vi_uarea = vn->vn_free_ptr; 133 134 // FIXME: there is no check, that item operation did not 135 // consume too much memory 136 vn->vn_free_ptr += 137 op_create_vi(vn, vi, is_affected, tb->insert_size[0]); 138 if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr) 139 reiserfs_panic(tb->tb_sb, "vs-8030", 140 "virtual node space consumed"); 141 142 if (!is_affected) 143 /* this is not being changed */ 144 continue; 145 146 if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) { 147 vn->vn_vi[new_num].vi_item_len += tb->insert_size[0]; 148 vi->vi_new_data = vn->vn_data; // pointer to data which is going to be pasted 149 } 150 } 151 152 /* virtual inserted item is not defined yet */ 153 if (vn->vn_mode == M_INSERT) { 154 struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num; 155 156 RFALSE(vn->vn_ins_ih == NULL, 157 "vs-8040: item header of inserted item is not specified"); 158 vi->vi_item_len = tb->insert_size[0]; 159 vi->vi_ih = vn->vn_ins_ih; 160 vi->vi_item = vn->vn_data; 161 vi->vi_uarea = vn->vn_free_ptr; 162 163 op_create_vi(vn, vi, 0 /*not pasted or cut */ , 164 tb->insert_size[0]); 165 } 166 167 /* set right merge flag we take right delimiting key and check whether it is a mergeable item */ 168 if (tb->CFR[0]) { 169 struct reiserfs_key *key; 170 171 key = B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]); 172 if (op_is_left_mergeable(key, Sh->b_size) 173 && (vn->vn_mode != M_DELETE 174 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) 175 vn->vn_vi[vn->vn_nr_item - 1].vi_type |= 176 VI_TYPE_RIGHT_MERGEABLE; 177 178 #ifdef CONFIG_REISERFS_CHECK 179 if (op_is_left_mergeable(key, Sh->b_size) && 180 !(vn->vn_mode != M_DELETE 181 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) { 182 /* we delete last item and it could be merged with right neighbor's first item */ 183 if (! 184 (B_NR_ITEMS(Sh) == 1 185 && is_direntry_le_ih(B_N_PITEM_HEAD(Sh, 0)) 186 && I_ENTRY_COUNT(B_N_PITEM_HEAD(Sh, 0)) == 1)) { 187 /* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */ 188 print_block(Sh, 0, -1, -1); 189 reiserfs_panic(tb->tb_sb, "vs-8045", 190 "rdkey %k, affected item==%d " 191 "(mode==%c) Must be %c", 192 key, vn->vn_affected_item_num, 193 vn->vn_mode, M_DELETE); 194 } 195 } 196 #endif 197 198 } 199 } 200 201 /* using virtual node check, how many items can be shifted to left 202 neighbor */ 203 static void check_left(struct tree_balance *tb, int h, int cur_free) 204 { 205 int i; 206 struct virtual_node *vn = tb->tb_vn; 207 struct virtual_item *vi; 208 int d_size, ih_size; 209 210 RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free); 211 212 /* internal level */ 213 if (h > 0) { 214 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE); 215 return; 216 } 217 218 /* leaf level */ 219 220 if (!cur_free || !vn->vn_nr_item) { 221 /* no free space or nothing to move */ 222 tb->lnum[h] = 0; 223 tb->lbytes = -1; 224 return; 225 } 226 227 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0), 228 "vs-8055: parent does not exist or invalid"); 229 230 vi = vn->vn_vi; 231 if ((unsigned int)cur_free >= 232 (vn->vn_size - 233 ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) { 234 /* all contents of S[0] fits into L[0] */ 235 236 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE, 237 "vs-8055: invalid mode or balance condition failed"); 238 239 tb->lnum[0] = vn->vn_nr_item; 240 tb->lbytes = -1; 241 return; 242 } 243 244 d_size = 0, ih_size = IH_SIZE; 245 246 /* first item may be merge with last item in left neighbor */ 247 if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE) 248 d_size = -((int)IH_SIZE), ih_size = 0; 249 250 tb->lnum[0] = 0; 251 for (i = 0; i < vn->vn_nr_item; 252 i++, ih_size = IH_SIZE, d_size = 0, vi++) { 253 d_size += vi->vi_item_len; 254 if (cur_free >= d_size) { 255 /* the item can be shifted entirely */ 256 cur_free -= d_size; 257 tb->lnum[0]++; 258 continue; 259 } 260 261 /* the item cannot be shifted entirely, try to split it */ 262 /* check whether L[0] can hold ih and at least one byte of the item body */ 263 if (cur_free <= ih_size) { 264 /* cannot shift even a part of the current item */ 265 tb->lbytes = -1; 266 return; 267 } 268 cur_free -= ih_size; 269 270 tb->lbytes = op_check_left(vi, cur_free, 0, 0); 271 if (tb->lbytes != -1) 272 /* count partially shifted item */ 273 tb->lnum[0]++; 274 275 break; 276 } 277 278 return; 279 } 280 281 /* using virtual node check, how many items can be shifted to right 282 neighbor */ 283 static void check_right(struct tree_balance *tb, int h, int cur_free) 284 { 285 int i; 286 struct virtual_node *vn = tb->tb_vn; 287 struct virtual_item *vi; 288 int d_size, ih_size; 289 290 RFALSE(cur_free < 0, "vs-8070: cur_free < 0"); 291 292 /* internal level */ 293 if (h > 0) { 294 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE); 295 return; 296 } 297 298 /* leaf level */ 299 300 if (!cur_free || !vn->vn_nr_item) { 301 /* no free space */ 302 tb->rnum[h] = 0; 303 tb->rbytes = -1; 304 return; 305 } 306 307 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0), 308 "vs-8075: parent does not exist or invalid"); 309 310 vi = vn->vn_vi + vn->vn_nr_item - 1; 311 if ((unsigned int)cur_free >= 312 (vn->vn_size - 313 ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) { 314 /* all contents of S[0] fits into R[0] */ 315 316 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE, 317 "vs-8080: invalid mode or balance condition failed"); 318 319 tb->rnum[h] = vn->vn_nr_item; 320 tb->rbytes = -1; 321 return; 322 } 323 324 d_size = 0, ih_size = IH_SIZE; 325 326 /* last item may be merge with first item in right neighbor */ 327 if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) 328 d_size = -(int)IH_SIZE, ih_size = 0; 329 330 tb->rnum[0] = 0; 331 for (i = vn->vn_nr_item - 1; i >= 0; 332 i--, d_size = 0, ih_size = IH_SIZE, vi--) { 333 d_size += vi->vi_item_len; 334 if (cur_free >= d_size) { 335 /* the item can be shifted entirely */ 336 cur_free -= d_size; 337 tb->rnum[0]++; 338 continue; 339 } 340 341 /* check whether R[0] can hold ih and at least one byte of the item body */ 342 if (cur_free <= ih_size) { /* cannot shift even a part of the current item */ 343 tb->rbytes = -1; 344 return; 345 } 346 347 /* R[0] can hold the header of the item and at least one byte of its body */ 348 cur_free -= ih_size; /* cur_free is still > 0 */ 349 350 tb->rbytes = op_check_right(vi, cur_free); 351 if (tb->rbytes != -1) 352 /* count partially shifted item */ 353 tb->rnum[0]++; 354 355 break; 356 } 357 358 return; 359 } 360 361 /* 362 * from - number of items, which are shifted to left neighbor entirely 363 * to - number of item, which are shifted to right neighbor entirely 364 * from_bytes - number of bytes of boundary item (or directory entries) which are shifted to left neighbor 365 * to_bytes - number of bytes of boundary item (or directory entries) which are shifted to right neighbor */ 366 static int get_num_ver(int mode, struct tree_balance *tb, int h, 367 int from, int from_bytes, 368 int to, int to_bytes, short *snum012, int flow) 369 { 370 int i; 371 int cur_free; 372 // int bytes; 373 int units; 374 struct virtual_node *vn = tb->tb_vn; 375 // struct virtual_item * vi; 376 377 int total_node_size, max_node_size, current_item_size; 378 int needed_nodes; 379 int start_item, /* position of item we start filling node from */ 380 end_item, /* position of item we finish filling node by */ 381 start_bytes, /* number of first bytes (entries for directory) of start_item-th item 382 we do not include into node that is being filled */ 383 end_bytes; /* number of last bytes (entries for directory) of end_item-th item 384 we do node include into node that is being filled */ 385 int split_item_positions[2]; /* these are positions in virtual item of 386 items, that are split between S[0] and 387 S1new and S1new and S2new */ 388 389 split_item_positions[0] = -1; 390 split_item_positions[1] = -1; 391 392 /* We only create additional nodes if we are in insert or paste mode 393 or we are in replace mode at the internal level. If h is 0 and 394 the mode is M_REPLACE then in fix_nodes we change the mode to 395 paste or insert before we get here in the code. */ 396 RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE), 397 "vs-8100: insert_size < 0 in overflow"); 398 399 max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h)); 400 401 /* snum012 [0-2] - number of items, that lay 402 to S[0], first new node and second new node */ 403 snum012[3] = -1; /* s1bytes */ 404 snum012[4] = -1; /* s2bytes */ 405 406 /* internal level */ 407 if (h > 0) { 408 i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE); 409 if (i == max_node_size) 410 return 1; 411 return (i / max_node_size + 1); 412 } 413 414 /* leaf level */ 415 needed_nodes = 1; 416 total_node_size = 0; 417 cur_free = max_node_size; 418 419 // start from 'from'-th item 420 start_item = from; 421 // skip its first 'start_bytes' units 422 start_bytes = ((from_bytes != -1) ? from_bytes : 0); 423 424 // last included item is the 'end_item'-th one 425 end_item = vn->vn_nr_item - to - 1; 426 // do not count last 'end_bytes' units of 'end_item'-th item 427 end_bytes = (to_bytes != -1) ? to_bytes : 0; 428 429 /* go through all item beginning from the start_item-th item and ending by 430 the end_item-th item. Do not count first 'start_bytes' units of 431 'start_item'-th item and last 'end_bytes' of 'end_item'-th item */ 432 433 for (i = start_item; i <= end_item; i++) { 434 struct virtual_item *vi = vn->vn_vi + i; 435 int skip_from_end = ((i == end_item) ? end_bytes : 0); 436 437 RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed"); 438 439 /* get size of current item */ 440 current_item_size = vi->vi_item_len; 441 442 /* do not take in calculation head part (from_bytes) of from-th item */ 443 current_item_size -= 444 op_part_size(vi, 0 /*from start */ , start_bytes); 445 446 /* do not take in calculation tail part of last item */ 447 current_item_size -= 448 op_part_size(vi, 1 /*from end */ , skip_from_end); 449 450 /* if item fits into current node entierly */ 451 if (total_node_size + current_item_size <= max_node_size) { 452 snum012[needed_nodes - 1]++; 453 total_node_size += current_item_size; 454 start_bytes = 0; 455 continue; 456 } 457 458 if (current_item_size > max_node_size) { 459 /* virtual item length is longer, than max size of item in 460 a node. It is impossible for direct item */ 461 RFALSE(is_direct_le_ih(vi->vi_ih), 462 "vs-8110: " 463 "direct item length is %d. It can not be longer than %d", 464 current_item_size, max_node_size); 465 /* we will try to split it */ 466 flow = 1; 467 } 468 469 if (!flow) { 470 /* as we do not split items, take new node and continue */ 471 needed_nodes++; 472 i--; 473 total_node_size = 0; 474 continue; 475 } 476 // calculate number of item units which fit into node being 477 // filled 478 { 479 int free_space; 480 481 free_space = max_node_size - total_node_size - IH_SIZE; 482 units = 483 op_check_left(vi, free_space, start_bytes, 484 skip_from_end); 485 if (units == -1) { 486 /* nothing fits into current node, take new node and continue */ 487 needed_nodes++, i--, total_node_size = 0; 488 continue; 489 } 490 } 491 492 /* something fits into the current node */ 493 //if (snum012[3] != -1 || needed_nodes != 1) 494 // reiserfs_panic (tb->tb_sb, "vs-8115: get_num_ver: too many nodes required"); 495 //snum012[needed_nodes - 1 + 3] = op_unit_num (vi) - start_bytes - units; 496 start_bytes += units; 497 snum012[needed_nodes - 1 + 3] = units; 498 499 if (needed_nodes > 2) 500 reiserfs_warning(tb->tb_sb, "vs-8111", 501 "split_item_position is out of range"); 502 snum012[needed_nodes - 1]++; 503 split_item_positions[needed_nodes - 1] = i; 504 needed_nodes++; 505 /* continue from the same item with start_bytes != -1 */ 506 start_item = i; 507 i--; 508 total_node_size = 0; 509 } 510 511 // sum012[4] (if it is not -1) contains number of units of which 512 // are to be in S1new, snum012[3] - to be in S0. They are supposed 513 // to be S1bytes and S2bytes correspondingly, so recalculate 514 if (snum012[4] > 0) { 515 int split_item_num; 516 int bytes_to_r, bytes_to_l; 517 int bytes_to_S1new; 518 519 split_item_num = split_item_positions[1]; 520 bytes_to_l = 521 ((from == split_item_num 522 && from_bytes != -1) ? from_bytes : 0); 523 bytes_to_r = 524 ((end_item == split_item_num 525 && end_bytes != -1) ? end_bytes : 0); 526 bytes_to_S1new = 527 ((split_item_positions[0] == 528 split_item_positions[1]) ? snum012[3] : 0); 529 530 // s2bytes 531 snum012[4] = 532 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] - 533 bytes_to_r - bytes_to_l - bytes_to_S1new; 534 535 if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY && 536 vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT) 537 reiserfs_warning(tb->tb_sb, "vs-8115", 538 "not directory or indirect item"); 539 } 540 541 /* now we know S2bytes, calculate S1bytes */ 542 if (snum012[3] > 0) { 543 int split_item_num; 544 int bytes_to_r, bytes_to_l; 545 int bytes_to_S2new; 546 547 split_item_num = split_item_positions[0]; 548 bytes_to_l = 549 ((from == split_item_num 550 && from_bytes != -1) ? from_bytes : 0); 551 bytes_to_r = 552 ((end_item == split_item_num 553 && end_bytes != -1) ? end_bytes : 0); 554 bytes_to_S2new = 555 ((split_item_positions[0] == split_item_positions[1] 556 && snum012[4] != -1) ? snum012[4] : 0); 557 558 // s1bytes 559 snum012[3] = 560 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] - 561 bytes_to_r - bytes_to_l - bytes_to_S2new; 562 } 563 564 return needed_nodes; 565 } 566 567 568 /* Set parameters for balancing. 569 * Performs write of results of analysis of balancing into structure tb, 570 * where it will later be used by the functions that actually do the balancing. 571 * Parameters: 572 * tb tree_balance structure; 573 * h current level of the node; 574 * lnum number of items from S[h] that must be shifted to L[h]; 575 * rnum number of items from S[h] that must be shifted to R[h]; 576 * blk_num number of blocks that S[h] will be splitted into; 577 * s012 number of items that fall into splitted nodes. 578 * lbytes number of bytes which flow to the left neighbor from the item that is not 579 * not shifted entirely 580 * rbytes number of bytes which flow to the right neighbor from the item that is not 581 * not shifted entirely 582 * s1bytes number of bytes which flow to the first new node when S[0] splits (this number is contained in s012 array) 583 */ 584 585 static void set_parameters(struct tree_balance *tb, int h, int lnum, 586 int rnum, int blk_num, short *s012, int lb, int rb) 587 { 588 589 tb->lnum[h] = lnum; 590 tb->rnum[h] = rnum; 591 tb->blknum[h] = blk_num; 592 593 if (h == 0) { /* only for leaf level */ 594 if (s012 != NULL) { 595 tb->s0num = *s012++, 596 tb->s1num = *s012++, tb->s2num = *s012++; 597 tb->s1bytes = *s012++; 598 tb->s2bytes = *s012; 599 } 600 tb->lbytes = lb; 601 tb->rbytes = rb; 602 } 603 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum); 604 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum); 605 606 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb); 607 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb); 608 } 609 610 /* check, does node disappear if we shift tb->lnum[0] items to left 611 neighbor and tb->rnum[0] to the right one. */ 612 static int is_leaf_removable(struct tree_balance *tb) 613 { 614 struct virtual_node *vn = tb->tb_vn; 615 int to_left, to_right; 616 int size; 617 int remain_items; 618 619 /* number of items, that will be shifted to left (right) neighbor 620 entirely */ 621 to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0); 622 to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0); 623 remain_items = vn->vn_nr_item; 624 625 /* how many items remain in S[0] after shiftings to neighbors */ 626 remain_items -= (to_left + to_right); 627 628 if (remain_items < 1) { 629 /* all content of node can be shifted to neighbors */ 630 set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0, 631 NULL, -1, -1); 632 return 1; 633 } 634 635 if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1) 636 /* S[0] is not removable */ 637 return 0; 638 639 /* check, whether we can divide 1 remaining item between neighbors */ 640 641 /* get size of remaining item (in item units) */ 642 size = op_unit_num(&(vn->vn_vi[to_left])); 643 644 if (tb->lbytes + tb->rbytes >= size) { 645 set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL, 646 tb->lbytes, -1); 647 return 1; 648 } 649 650 return 0; 651 } 652 653 /* check whether L, S, R can be joined in one node */ 654 static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree) 655 { 656 struct virtual_node *vn = tb->tb_vn; 657 int ih_size; 658 struct buffer_head *S0; 659 660 S0 = PATH_H_PBUFFER(tb->tb_path, 0); 661 662 ih_size = 0; 663 if (vn->vn_nr_item) { 664 if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE) 665 ih_size += IH_SIZE; 666 667 if (vn->vn_vi[vn->vn_nr_item - 1]. 668 vi_type & VI_TYPE_RIGHT_MERGEABLE) 669 ih_size += IH_SIZE; 670 } else { 671 /* there was only one item and it will be deleted */ 672 struct item_head *ih; 673 674 RFALSE(B_NR_ITEMS(S0) != 1, 675 "vs-8125: item number must be 1: it is %d", 676 B_NR_ITEMS(S0)); 677 678 ih = B_N_PITEM_HEAD(S0, 0); 679 if (tb->CFR[0] 680 && !comp_short_le_keys(&(ih->ih_key), 681 B_N_PDELIM_KEY(tb->CFR[0], 682 tb->rkey[0]))) 683 if (is_direntry_le_ih(ih)) { 684 /* Directory must be in correct state here: that is 685 somewhere at the left side should exist first directory 686 item. But the item being deleted can not be that first 687 one because its right neighbor is item of the same 688 directory. (But first item always gets deleted in last 689 turn). So, neighbors of deleted item can be merged, so 690 we can save ih_size */ 691 ih_size = IH_SIZE; 692 693 /* we might check that left neighbor exists and is of the 694 same directory */ 695 RFALSE(le_ih_k_offset(ih) == DOT_OFFSET, 696 "vs-8130: first directory item can not be removed until directory is not empty"); 697 } 698 699 } 700 701 if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) { 702 set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1); 703 PROC_INFO_INC(tb->tb_sb, leaves_removable); 704 return 1; 705 } 706 return 0; 707 708 } 709 710 /* when we do not split item, lnum and rnum are numbers of entire items */ 711 #define SET_PAR_SHIFT_LEFT \ 712 if (h)\ 713 {\ 714 int to_l;\ 715 \ 716 to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\ 717 (MAX_NR_KEY(Sh) + 1 - lpar);\ 718 \ 719 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\ 720 }\ 721 else \ 722 {\ 723 if (lset==LEFT_SHIFT_FLOW)\ 724 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\ 725 tb->lbytes, -1);\ 726 else\ 727 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\ 728 -1, -1);\ 729 } 730 731 #define SET_PAR_SHIFT_RIGHT \ 732 if (h)\ 733 {\ 734 int to_r;\ 735 \ 736 to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\ 737 \ 738 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\ 739 }\ 740 else \ 741 {\ 742 if (rset==RIGHT_SHIFT_FLOW)\ 743 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\ 744 -1, tb->rbytes);\ 745 else\ 746 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\ 747 -1, -1);\ 748 } 749 750 static void free_buffers_in_tb(struct tree_balance *tb) 751 { 752 int i; 753 754 pathrelse(tb->tb_path); 755 756 for (i = 0; i < MAX_HEIGHT; i++) { 757 brelse(tb->L[i]); 758 brelse(tb->R[i]); 759 brelse(tb->FL[i]); 760 brelse(tb->FR[i]); 761 brelse(tb->CFL[i]); 762 brelse(tb->CFR[i]); 763 764 tb->L[i] = NULL; 765 tb->R[i] = NULL; 766 tb->FL[i] = NULL; 767 tb->FR[i] = NULL; 768 tb->CFL[i] = NULL; 769 tb->CFR[i] = NULL; 770 } 771 } 772 773 /* Get new buffers for storing new nodes that are created while balancing. 774 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked; 775 * CARRY_ON - schedule didn't occur while the function worked; 776 * NO_DISK_SPACE - no disk space. 777 */ 778 /* The function is NOT SCHEDULE-SAFE! */ 779 static int get_empty_nodes(struct tree_balance *tb, int h) 780 { 781 struct buffer_head *new_bh, 782 *Sh = PATH_H_PBUFFER(tb->tb_path, h); 783 b_blocknr_t *blocknr, blocknrs[MAX_AMOUNT_NEEDED] = { 0, }; 784 int counter, number_of_freeblk, amount_needed, /* number of needed empty blocks */ 785 retval = CARRY_ON; 786 struct super_block *sb = tb->tb_sb; 787 788 /* number_of_freeblk is the number of empty blocks which have been 789 acquired for use by the balancing algorithm minus the number of 790 empty blocks used in the previous levels of the analysis, 791 number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs 792 after empty blocks are acquired, and the balancing analysis is 793 then restarted, amount_needed is the number needed by this level 794 (h) of the balancing analysis. 795 796 Note that for systems with many processes writing, it would be 797 more layout optimal to calculate the total number needed by all 798 levels and then to run reiserfs_new_blocks to get all of them at once. */ 799 800 /* Initiate number_of_freeblk to the amount acquired prior to the restart of 801 the analysis or 0 if not restarted, then subtract the amount needed 802 by all of the levels of the tree below h. */ 803 /* blknum includes S[h], so we subtract 1 in this calculation */ 804 for (counter = 0, number_of_freeblk = tb->cur_blknum; 805 counter < h; counter++) 806 number_of_freeblk -= 807 (tb->blknum[counter]) ? (tb->blknum[counter] - 808 1) : 0; 809 810 /* Allocate missing empty blocks. */ 811 /* if Sh == 0 then we are getting a new root */ 812 amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1; 813 /* Amount_needed = the amount that we need more than the amount that we have. */ 814 if (amount_needed > number_of_freeblk) 815 amount_needed -= number_of_freeblk; 816 else /* If we have enough already then there is nothing to do. */ 817 return CARRY_ON; 818 819 /* No need to check quota - is not allocated for blocks used for formatted nodes */ 820 if (reiserfs_new_form_blocknrs(tb, blocknrs, 821 amount_needed) == NO_DISK_SPACE) 822 return NO_DISK_SPACE; 823 824 /* for each blocknumber we just got, get a buffer and stick it on FEB */ 825 for (blocknr = blocknrs, counter = 0; 826 counter < amount_needed; blocknr++, counter++) { 827 828 RFALSE(!*blocknr, 829 "PAP-8135: reiserfs_new_blocknrs failed when got new blocks"); 830 831 new_bh = sb_getblk(sb, *blocknr); 832 RFALSE(buffer_dirty(new_bh) || 833 buffer_journaled(new_bh) || 834 buffer_journal_dirty(new_bh), 835 "PAP-8140: journaled or dirty buffer %b for the new block", 836 new_bh); 837 838 /* Put empty buffers into the array. */ 839 RFALSE(tb->FEB[tb->cur_blknum], 840 "PAP-8141: busy slot for new buffer"); 841 842 set_buffer_journal_new(new_bh); 843 tb->FEB[tb->cur_blknum++] = new_bh; 844 } 845 846 if (retval == CARRY_ON && FILESYSTEM_CHANGED_TB(tb)) 847 retval = REPEAT_SEARCH; 848 849 return retval; 850 } 851 852 /* Get free space of the left neighbor, which is stored in the parent 853 * node of the left neighbor. */ 854 static int get_lfree(struct tree_balance *tb, int h) 855 { 856 struct buffer_head *l, *f; 857 int order; 858 859 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL || 860 (l = tb->FL[h]) == NULL) 861 return 0; 862 863 if (f == l) 864 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1; 865 else { 866 order = B_NR_ITEMS(l); 867 f = l; 868 } 869 870 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order))); 871 } 872 873 /* Get free space of the right neighbor, 874 * which is stored in the parent node of the right neighbor. 875 */ 876 static int get_rfree(struct tree_balance *tb, int h) 877 { 878 struct buffer_head *r, *f; 879 int order; 880 881 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL || 882 (r = tb->FR[h]) == NULL) 883 return 0; 884 885 if (f == r) 886 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1; 887 else { 888 order = 0; 889 f = r; 890 } 891 892 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order))); 893 894 } 895 896 /* Check whether left neighbor is in memory. */ 897 static int is_left_neighbor_in_cache(struct tree_balance *tb, int h) 898 { 899 struct buffer_head *father, *left; 900 struct super_block *sb = tb->tb_sb; 901 b_blocknr_t left_neighbor_blocknr; 902 int left_neighbor_position; 903 904 /* Father of the left neighbor does not exist. */ 905 if (!tb->FL[h]) 906 return 0; 907 908 /* Calculate father of the node to be balanced. */ 909 father = PATH_H_PBUFFER(tb->tb_path, h + 1); 910 911 RFALSE(!father || 912 !B_IS_IN_TREE(father) || 913 !B_IS_IN_TREE(tb->FL[h]) || 914 !buffer_uptodate(father) || 915 !buffer_uptodate(tb->FL[h]), 916 "vs-8165: F[h] (%b) or FL[h] (%b) is invalid", 917 father, tb->FL[h]); 918 919 /* Get position of the pointer to the left neighbor into the left father. */ 920 left_neighbor_position = (father == tb->FL[h]) ? 921 tb->lkey[h] : B_NR_ITEMS(tb->FL[h]); 922 /* Get left neighbor block number. */ 923 left_neighbor_blocknr = 924 B_N_CHILD_NUM(tb->FL[h], left_neighbor_position); 925 /* Look for the left neighbor in the cache. */ 926 if ((left = sb_find_get_block(sb, left_neighbor_blocknr))) { 927 928 RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left), 929 "vs-8170: left neighbor (%b %z) is not in the tree", 930 left, left); 931 put_bh(left); 932 return 1; 933 } 934 935 return 0; 936 } 937 938 #define LEFT_PARENTS 'l' 939 #define RIGHT_PARENTS 'r' 940 941 static void decrement_key(struct cpu_key *key) 942 { 943 // call item specific function for this key 944 item_ops[cpu_key_k_type(key)]->decrement_key(key); 945 } 946 947 /* Calculate far left/right parent of the left/right neighbor of the current node, that 948 * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h]. 949 * Calculate left/right common parent of the current node and L[h]/R[h]. 950 * Calculate left/right delimiting key position. 951 * Returns: PATH_INCORRECT - path in the tree is not correct; 952 SCHEDULE_OCCURRED - schedule occurred while the function worked; 953 * CARRY_ON - schedule didn't occur while the function worked; 954 */ 955 static int get_far_parent(struct tree_balance *tb, 956 int h, 957 struct buffer_head **pfather, 958 struct buffer_head **pcom_father, char c_lr_par) 959 { 960 struct buffer_head *parent; 961 INITIALIZE_PATH(s_path_to_neighbor_father); 962 struct treepath *path = tb->tb_path; 963 struct cpu_key s_lr_father_key; 964 int counter, 965 position = INT_MAX, 966 first_last_position = 0, 967 path_offset = PATH_H_PATH_OFFSET(path, h); 968 969 /* Starting from F[h] go upwards in the tree, and look for the common 970 ancestor of F[h], and its neighbor l/r, that should be obtained. */ 971 972 counter = path_offset; 973 974 RFALSE(counter < FIRST_PATH_ELEMENT_OFFSET, 975 "PAP-8180: invalid path length"); 976 977 for (; counter > FIRST_PATH_ELEMENT_OFFSET; counter--) { 978 /* Check whether parent of the current buffer in the path is really parent in the tree. */ 979 if (!B_IS_IN_TREE 980 (parent = PATH_OFFSET_PBUFFER(path, counter - 1))) 981 return REPEAT_SEARCH; 982 /* Check whether position in the parent is correct. */ 983 if ((position = 984 PATH_OFFSET_POSITION(path, 985 counter - 1)) > 986 B_NR_ITEMS(parent)) 987 return REPEAT_SEARCH; 988 /* Check whether parent at the path really points to the child. */ 989 if (B_N_CHILD_NUM(parent, position) != 990 PATH_OFFSET_PBUFFER(path, counter)->b_blocknr) 991 return REPEAT_SEARCH; 992 /* Return delimiting key if position in the parent is not equal to first/last one. */ 993 if (c_lr_par == RIGHT_PARENTS) 994 first_last_position = B_NR_ITEMS(parent); 995 if (position != first_last_position) { 996 *pcom_father = parent; 997 get_bh(*pcom_father); 998 /*(*pcom_father = parent)->b_count++; */ 999 break; 1000 } 1001 } 1002 1003 /* if we are in the root of the tree, then there is no common father */ 1004 if (counter == FIRST_PATH_ELEMENT_OFFSET) { 1005 /* Check whether first buffer in the path is the root of the tree. */ 1006 if (PATH_OFFSET_PBUFFER 1007 (tb->tb_path, 1008 FIRST_PATH_ELEMENT_OFFSET)->b_blocknr == 1009 SB_ROOT_BLOCK(tb->tb_sb)) { 1010 *pfather = *pcom_father = NULL; 1011 return CARRY_ON; 1012 } 1013 return REPEAT_SEARCH; 1014 } 1015 1016 RFALSE(B_LEVEL(*pcom_father) <= DISK_LEAF_NODE_LEVEL, 1017 "PAP-8185: (%b %z) level too small", 1018 *pcom_father, *pcom_father); 1019 1020 /* Check whether the common parent is locked. */ 1021 1022 if (buffer_locked(*pcom_father)) { 1023 1024 /* Release the write lock while the buffer is busy */ 1025 int depth = reiserfs_write_unlock_nested(tb->tb_sb); 1026 __wait_on_buffer(*pcom_father); 1027 reiserfs_write_lock_nested(tb->tb_sb, depth); 1028 if (FILESYSTEM_CHANGED_TB(tb)) { 1029 brelse(*pcom_father); 1030 return REPEAT_SEARCH; 1031 } 1032 } 1033 1034 /* So, we got common parent of the current node and its left/right neighbor. 1035 Now we are geting the parent of the left/right neighbor. */ 1036 1037 /* Form key to get parent of the left/right neighbor. */ 1038 le_key2cpu_key(&s_lr_father_key, 1039 B_N_PDELIM_KEY(*pcom_father, 1040 (c_lr_par == 1041 LEFT_PARENTS) ? (tb->lkey[h - 1] = 1042 position - 1043 1) : (tb->rkey[h - 1044 1] = 1045 position))); 1046 1047 if (c_lr_par == LEFT_PARENTS) 1048 decrement_key(&s_lr_father_key); 1049 1050 if (search_by_key 1051 (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father, 1052 h + 1) == IO_ERROR) 1053 // path is released 1054 return IO_ERROR; 1055 1056 if (FILESYSTEM_CHANGED_TB(tb)) { 1057 pathrelse(&s_path_to_neighbor_father); 1058 brelse(*pcom_father); 1059 return REPEAT_SEARCH; 1060 } 1061 1062 *pfather = PATH_PLAST_BUFFER(&s_path_to_neighbor_father); 1063 1064 RFALSE(B_LEVEL(*pfather) != h + 1, 1065 "PAP-8190: (%b %z) level too small", *pfather, *pfather); 1066 RFALSE(s_path_to_neighbor_father.path_length < 1067 FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small"); 1068 1069 s_path_to_neighbor_father.path_length--; 1070 pathrelse(&s_path_to_neighbor_father); 1071 return CARRY_ON; 1072 } 1073 1074 /* Get parents of neighbors of node in the path(S[path_offset]) and common parents of 1075 * S[path_offset] and L[path_offset]/R[path_offset]: F[path_offset], FL[path_offset], 1076 * FR[path_offset], CFL[path_offset], CFR[path_offset]. 1077 * Calculate numbers of left and right delimiting keys position: lkey[path_offset], rkey[path_offset]. 1078 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked; 1079 * CARRY_ON - schedule didn't occur while the function worked; 1080 */ 1081 static int get_parents(struct tree_balance *tb, int h) 1082 { 1083 struct treepath *path = tb->tb_path; 1084 int position, 1085 ret, 1086 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h); 1087 struct buffer_head *curf, *curcf; 1088 1089 /* Current node is the root of the tree or will be root of the tree */ 1090 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) { 1091 /* The root can not have parents. 1092 Release nodes which previously were obtained as parents of the current node neighbors. */ 1093 brelse(tb->FL[h]); 1094 brelse(tb->CFL[h]); 1095 brelse(tb->FR[h]); 1096 brelse(tb->CFR[h]); 1097 tb->FL[h] = NULL; 1098 tb->CFL[h] = NULL; 1099 tb->FR[h] = NULL; 1100 tb->CFR[h] = NULL; 1101 return CARRY_ON; 1102 } 1103 1104 /* Get parent FL[path_offset] of L[path_offset]. */ 1105 position = PATH_OFFSET_POSITION(path, path_offset - 1); 1106 if (position) { 1107 /* Current node is not the first child of its parent. */ 1108 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1); 1109 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1); 1110 get_bh(curf); 1111 get_bh(curf); 1112 tb->lkey[h] = position - 1; 1113 } else { 1114 /* Calculate current parent of L[path_offset], which is the left neighbor of the current node. 1115 Calculate current common parent of L[path_offset] and the current node. Note that 1116 CFL[path_offset] not equal FL[path_offset] and CFL[path_offset] not equal F[path_offset]. 1117 Calculate lkey[path_offset]. */ 1118 if ((ret = get_far_parent(tb, h + 1, &curf, 1119 &curcf, 1120 LEFT_PARENTS)) != CARRY_ON) 1121 return ret; 1122 } 1123 1124 brelse(tb->FL[h]); 1125 tb->FL[h] = curf; /* New initialization of FL[h]. */ 1126 brelse(tb->CFL[h]); 1127 tb->CFL[h] = curcf; /* New initialization of CFL[h]. */ 1128 1129 RFALSE((curf && !B_IS_IN_TREE(curf)) || 1130 (curcf && !B_IS_IN_TREE(curcf)), 1131 "PAP-8195: FL (%b) or CFL (%b) is invalid", curf, curcf); 1132 1133 /* Get parent FR[h] of R[h]. */ 1134 1135 /* Current node is the last child of F[h]. FR[h] != F[h]. */ 1136 if (position == B_NR_ITEMS(PATH_H_PBUFFER(path, h + 1))) { 1137 /* Calculate current parent of R[h], which is the right neighbor of F[h]. 1138 Calculate current common parent of R[h] and current node. Note that CFR[h] 1139 not equal FR[path_offset] and CFR[h] not equal F[h]. */ 1140 if ((ret = 1141 get_far_parent(tb, h + 1, &curf, &curcf, 1142 RIGHT_PARENTS)) != CARRY_ON) 1143 return ret; 1144 } else { 1145 /* Current node is not the last child of its parent F[h]. */ 1146 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1); 1147 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1); 1148 get_bh(curf); 1149 get_bh(curf); 1150 tb->rkey[h] = position; 1151 } 1152 1153 brelse(tb->FR[h]); 1154 /* New initialization of FR[path_offset]. */ 1155 tb->FR[h] = curf; 1156 1157 brelse(tb->CFR[h]); 1158 /* New initialization of CFR[path_offset]. */ 1159 tb->CFR[h] = curcf; 1160 1161 RFALSE((curf && !B_IS_IN_TREE(curf)) || 1162 (curcf && !B_IS_IN_TREE(curcf)), 1163 "PAP-8205: FR (%b) or CFR (%b) is invalid", curf, curcf); 1164 1165 return CARRY_ON; 1166 } 1167 1168 /* it is possible to remove node as result of shiftings to 1169 neighbors even when we insert or paste item. */ 1170 static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree, 1171 struct tree_balance *tb, int h) 1172 { 1173 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h); 1174 int levbytes = tb->insert_size[h]; 1175 struct item_head *ih; 1176 struct reiserfs_key *r_key = NULL; 1177 1178 ih = B_N_PITEM_HEAD(Sh, 0); 1179 if (tb->CFR[h]) 1180 r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]); 1181 1182 if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes 1183 /* shifting may merge items which might save space */ 1184 - 1185 ((!h 1186 && op_is_left_mergeable(&(ih->ih_key), Sh->b_size)) ? IH_SIZE : 0) 1187 - 1188 ((!h && r_key 1189 && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0) 1190 + ((h) ? KEY_SIZE : 0)) { 1191 /* node can not be removed */ 1192 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */ 1193 if (!h) 1194 tb->s0num = 1195 B_NR_ITEMS(Sh) + 1196 ((mode == M_INSERT) ? 1 : 0); 1197 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 1198 return NO_BALANCING_NEEDED; 1199 } 1200 } 1201 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]); 1202 return !NO_BALANCING_NEEDED; 1203 } 1204 1205 /* Check whether current node S[h] is balanced when increasing its size by 1206 * Inserting or Pasting. 1207 * Calculate parameters for balancing for current level h. 1208 * Parameters: 1209 * tb tree_balance structure; 1210 * h current level of the node; 1211 * inum item number in S[h]; 1212 * mode i - insert, p - paste; 1213 * Returns: 1 - schedule occurred; 1214 * 0 - balancing for higher levels needed; 1215 * -1 - no balancing for higher levels needed; 1216 * -2 - no disk space. 1217 */ 1218 /* ip means Inserting or Pasting */ 1219 static int ip_check_balance(struct tree_balance *tb, int h) 1220 { 1221 struct virtual_node *vn = tb->tb_vn; 1222 int levbytes, /* Number of bytes that must be inserted into (value 1223 is negative if bytes are deleted) buffer which 1224 contains node being balanced. The mnemonic is 1225 that the attempted change in node space used level 1226 is levbytes bytes. */ 1227 ret; 1228 1229 int lfree, sfree, rfree /* free space in L, S and R */ ; 1230 1231 /* nver is short for number of vertixes, and lnver is the number if 1232 we shift to the left, rnver is the number if we shift to the 1233 right, and lrnver is the number if we shift in both directions. 1234 The goal is to minimize first the number of vertixes, and second, 1235 the number of vertixes whose contents are changed by shifting, 1236 and third the number of uncached vertixes whose contents are 1237 changed by shifting and must be read from disk. */ 1238 int nver, lnver, rnver, lrnver; 1239 1240 /* used at leaf level only, S0 = S[0] is the node being balanced, 1241 sInum [ I = 0,1,2 ] is the number of items that will 1242 remain in node SI after balancing. S1 and S2 are new 1243 nodes that might be created. */ 1244 1245 /* we perform 8 calls to get_num_ver(). For each call we calculate five parameters. 1246 where 4th parameter is s1bytes and 5th - s2bytes 1247 */ 1248 short snum012[40] = { 0, }; /* s0num, s1num, s2num for 8 cases 1249 0,1 - do not shift and do not shift but bottle 1250 2 - shift only whole item to left 1251 3 - shift to left and bottle as much as possible 1252 4,5 - shift to right (whole items and as much as possible 1253 6,7 - shift to both directions (whole items and as much as possible) 1254 */ 1255 1256 /* Sh is the node whose balance is currently being checked */ 1257 struct buffer_head *Sh; 1258 1259 Sh = PATH_H_PBUFFER(tb->tb_path, h); 1260 levbytes = tb->insert_size[h]; 1261 1262 /* Calculate balance parameters for creating new root. */ 1263 if (!Sh) { 1264 if (!h) 1265 reiserfs_panic(tb->tb_sb, "vs-8210", 1266 "S[0] can not be 0"); 1267 switch (ret = get_empty_nodes(tb, h)) { 1268 case CARRY_ON: 1269 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 1270 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */ 1271 1272 case NO_DISK_SPACE: 1273 case REPEAT_SEARCH: 1274 return ret; 1275 default: 1276 reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect " 1277 "return value of get_empty_nodes"); 1278 } 1279 } 1280 1281 if ((ret = get_parents(tb, h)) != CARRY_ON) /* get parents of S[h] neighbors. */ 1282 return ret; 1283 1284 sfree = B_FREE_SPACE(Sh); 1285 1286 /* get free space of neighbors */ 1287 rfree = get_rfree(tb, h); 1288 lfree = get_lfree(tb, h); 1289 1290 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) == 1291 NO_BALANCING_NEEDED) 1292 /* and new item fits into node S[h] without any shifting */ 1293 return NO_BALANCING_NEEDED; 1294 1295 create_virtual_node(tb, h); 1296 1297 /* 1298 determine maximal number of items we can shift to the left neighbor (in tb structure) 1299 and the maximal number of bytes that can flow to the left neighbor 1300 from the left most liquid item that cannot be shifted from S[0] entirely (returned value) 1301 */ 1302 check_left(tb, h, lfree); 1303 1304 /* 1305 determine maximal number of items we can shift to the right neighbor (in tb structure) 1306 and the maximal number of bytes that can flow to the right neighbor 1307 from the right most liquid item that cannot be shifted from S[0] entirely (returned value) 1308 */ 1309 check_right(tb, h, rfree); 1310 1311 /* all contents of internal node S[h] can be moved into its 1312 neighbors, S[h] will be removed after balancing */ 1313 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) { 1314 int to_r; 1315 1316 /* Since we are working on internal nodes, and our internal 1317 nodes have fixed size entries, then we can balance by the 1318 number of items rather than the space they consume. In this 1319 routine we set the left node equal to the right node, 1320 allowing a difference of less than or equal to 1 child 1321 pointer. */ 1322 to_r = 1323 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] + 1324 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - 1325 tb->rnum[h]); 1326 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, 1327 -1, -1); 1328 return CARRY_ON; 1329 } 1330 1331 /* this checks balance condition, that any two neighboring nodes can not fit in one node */ 1332 RFALSE(h && 1333 (tb->lnum[h] >= vn->vn_nr_item + 1 || 1334 tb->rnum[h] >= vn->vn_nr_item + 1), 1335 "vs-8220: tree is not balanced on internal level"); 1336 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) || 1337 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))), 1338 "vs-8225: tree is not balanced on leaf level"); 1339 1340 /* all contents of S[0] can be moved into its neighbors 1341 S[0] will be removed after balancing. */ 1342 if (!h && is_leaf_removable(tb)) 1343 return CARRY_ON; 1344 1345 /* why do we perform this check here rather than earlier?? 1346 Answer: we can win 1 node in some cases above. Moreover we 1347 checked it above, when we checked, that S[0] is not removable 1348 in principle */ 1349 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */ 1350 if (!h) 1351 tb->s0num = vn->vn_nr_item; 1352 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 1353 return NO_BALANCING_NEEDED; 1354 } 1355 1356 { 1357 int lpar, rpar, nset, lset, rset, lrset; 1358 /* 1359 * regular overflowing of the node 1360 */ 1361 1362 /* get_num_ver works in 2 modes (FLOW & NO_FLOW) 1363 lpar, rpar - number of items we can shift to left/right neighbor (including splitting item) 1364 nset, lset, rset, lrset - shows, whether flowing items give better packing 1365 */ 1366 #define FLOW 1 1367 #define NO_FLOW 0 /* do not any splitting */ 1368 1369 /* we choose one the following */ 1370 #define NOTHING_SHIFT_NO_FLOW 0 1371 #define NOTHING_SHIFT_FLOW 5 1372 #define LEFT_SHIFT_NO_FLOW 10 1373 #define LEFT_SHIFT_FLOW 15 1374 #define RIGHT_SHIFT_NO_FLOW 20 1375 #define RIGHT_SHIFT_FLOW 25 1376 #define LR_SHIFT_NO_FLOW 30 1377 #define LR_SHIFT_FLOW 35 1378 1379 lpar = tb->lnum[h]; 1380 rpar = tb->rnum[h]; 1381 1382 /* calculate number of blocks S[h] must be split into when 1383 nothing is shifted to the neighbors, 1384 as well as number of items in each part of the split node (s012 numbers), 1385 and number of bytes (s1bytes) of the shared drop which flow to S1 if any */ 1386 nset = NOTHING_SHIFT_NO_FLOW; 1387 nver = get_num_ver(vn->vn_mode, tb, h, 1388 0, -1, h ? vn->vn_nr_item : 0, -1, 1389 snum012, NO_FLOW); 1390 1391 if (!h) { 1392 int nver1; 1393 1394 /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */ 1395 nver1 = get_num_ver(vn->vn_mode, tb, h, 1396 0, -1, 0, -1, 1397 snum012 + NOTHING_SHIFT_FLOW, FLOW); 1398 if (nver > nver1) 1399 nset = NOTHING_SHIFT_FLOW, nver = nver1; 1400 } 1401 1402 /* calculate number of blocks S[h] must be split into when 1403 l_shift_num first items and l_shift_bytes of the right most 1404 liquid item to be shifted are shifted to the left neighbor, 1405 as well as number of items in each part of the splitted node (s012 numbers), 1406 and number of bytes (s1bytes) of the shared drop which flow to S1 if any 1407 */ 1408 lset = LEFT_SHIFT_NO_FLOW; 1409 lnver = get_num_ver(vn->vn_mode, tb, h, 1410 lpar - ((h || tb->lbytes == -1) ? 0 : 1), 1411 -1, h ? vn->vn_nr_item : 0, -1, 1412 snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW); 1413 if (!h) { 1414 int lnver1; 1415 1416 lnver1 = get_num_ver(vn->vn_mode, tb, h, 1417 lpar - 1418 ((tb->lbytes != -1) ? 1 : 0), 1419 tb->lbytes, 0, -1, 1420 snum012 + LEFT_SHIFT_FLOW, FLOW); 1421 if (lnver > lnver1) 1422 lset = LEFT_SHIFT_FLOW, lnver = lnver1; 1423 } 1424 1425 /* calculate number of blocks S[h] must be split into when 1426 r_shift_num first items and r_shift_bytes of the left most 1427 liquid item to be shifted are shifted to the right neighbor, 1428 as well as number of items in each part of the splitted node (s012 numbers), 1429 and number of bytes (s1bytes) of the shared drop which flow to S1 if any 1430 */ 1431 rset = RIGHT_SHIFT_NO_FLOW; 1432 rnver = get_num_ver(vn->vn_mode, tb, h, 1433 0, -1, 1434 h ? (vn->vn_nr_item - rpar) : (rpar - 1435 ((tb-> 1436 rbytes != 1437 -1) ? 1 : 1438 0)), -1, 1439 snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW); 1440 if (!h) { 1441 int rnver1; 1442 1443 rnver1 = get_num_ver(vn->vn_mode, tb, h, 1444 0, -1, 1445 (rpar - 1446 ((tb->rbytes != -1) ? 1 : 0)), 1447 tb->rbytes, 1448 snum012 + RIGHT_SHIFT_FLOW, FLOW); 1449 1450 if (rnver > rnver1) 1451 rset = RIGHT_SHIFT_FLOW, rnver = rnver1; 1452 } 1453 1454 /* calculate number of blocks S[h] must be split into when 1455 items are shifted in both directions, 1456 as well as number of items in each part of the splitted node (s012 numbers), 1457 and number of bytes (s1bytes) of the shared drop which flow to S1 if any 1458 */ 1459 lrset = LR_SHIFT_NO_FLOW; 1460 lrnver = get_num_ver(vn->vn_mode, tb, h, 1461 lpar - ((h || tb->lbytes == -1) ? 0 : 1), 1462 -1, 1463 h ? (vn->vn_nr_item - rpar) : (rpar - 1464 ((tb-> 1465 rbytes != 1466 -1) ? 1 : 1467 0)), -1, 1468 snum012 + LR_SHIFT_NO_FLOW, NO_FLOW); 1469 if (!h) { 1470 int lrnver1; 1471 1472 lrnver1 = get_num_ver(vn->vn_mode, tb, h, 1473 lpar - 1474 ((tb->lbytes != -1) ? 1 : 0), 1475 tb->lbytes, 1476 (rpar - 1477 ((tb->rbytes != -1) ? 1 : 0)), 1478 tb->rbytes, 1479 snum012 + LR_SHIFT_FLOW, FLOW); 1480 if (lrnver > lrnver1) 1481 lrset = LR_SHIFT_FLOW, lrnver = lrnver1; 1482 } 1483 1484 /* Our general shifting strategy is: 1485 1) to minimized number of new nodes; 1486 2) to minimized number of neighbors involved in shifting; 1487 3) to minimized number of disk reads; */ 1488 1489 /* we can win TWO or ONE nodes by shifting in both directions */ 1490 if (lrnver < lnver && lrnver < rnver) { 1491 RFALSE(h && 1492 (tb->lnum[h] != 1 || 1493 tb->rnum[h] != 1 || 1494 lrnver != 1 || rnver != 2 || lnver != 2 1495 || h != 1), "vs-8230: bad h"); 1496 if (lrset == LR_SHIFT_FLOW) 1497 set_parameters(tb, h, tb->lnum[h], tb->rnum[h], 1498 lrnver, snum012 + lrset, 1499 tb->lbytes, tb->rbytes); 1500 else 1501 set_parameters(tb, h, 1502 tb->lnum[h] - 1503 ((tb->lbytes == -1) ? 0 : 1), 1504 tb->rnum[h] - 1505 ((tb->rbytes == -1) ? 0 : 1), 1506 lrnver, snum012 + lrset, -1, -1); 1507 1508 return CARRY_ON; 1509 } 1510 1511 /* if shifting doesn't lead to better packing then don't shift */ 1512 if (nver == lrnver) { 1513 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1, 1514 -1); 1515 return CARRY_ON; 1516 } 1517 1518 /* now we know that for better packing shifting in only one 1519 direction either to the left or to the right is required */ 1520 1521 /* if shifting to the left is better than shifting to the right */ 1522 if (lnver < rnver) { 1523 SET_PAR_SHIFT_LEFT; 1524 return CARRY_ON; 1525 } 1526 1527 /* if shifting to the right is better than shifting to the left */ 1528 if (lnver > rnver) { 1529 SET_PAR_SHIFT_RIGHT; 1530 return CARRY_ON; 1531 } 1532 1533 /* now shifting in either direction gives the same number 1534 of nodes and we can make use of the cached neighbors */ 1535 if (is_left_neighbor_in_cache(tb, h)) { 1536 SET_PAR_SHIFT_LEFT; 1537 return CARRY_ON; 1538 } 1539 1540 /* shift to the right independently on whether the right neighbor in cache or not */ 1541 SET_PAR_SHIFT_RIGHT; 1542 return CARRY_ON; 1543 } 1544 } 1545 1546 /* Check whether current node S[h] is balanced when Decreasing its size by 1547 * Deleting or Cutting for INTERNAL node of S+tree. 1548 * Calculate parameters for balancing for current level h. 1549 * Parameters: 1550 * tb tree_balance structure; 1551 * h current level of the node; 1552 * inum item number in S[h]; 1553 * mode i - insert, p - paste; 1554 * Returns: 1 - schedule occurred; 1555 * 0 - balancing for higher levels needed; 1556 * -1 - no balancing for higher levels needed; 1557 * -2 - no disk space. 1558 * 1559 * Note: Items of internal nodes have fixed size, so the balance condition for 1560 * the internal part of S+tree is as for the B-trees. 1561 */ 1562 static int dc_check_balance_internal(struct tree_balance *tb, int h) 1563 { 1564 struct virtual_node *vn = tb->tb_vn; 1565 1566 /* Sh is the node whose balance is currently being checked, 1567 and Fh is its father. */ 1568 struct buffer_head *Sh, *Fh; 1569 int maxsize, ret; 1570 int lfree, rfree /* free space in L and R */ ; 1571 1572 Sh = PATH_H_PBUFFER(tb->tb_path, h); 1573 Fh = PATH_H_PPARENT(tb->tb_path, h); 1574 1575 maxsize = MAX_CHILD_SIZE(Sh); 1576 1577 /* using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */ 1578 /* new_nr_item = number of items node would have if operation is */ 1579 /* performed without balancing (new_nr_item); */ 1580 create_virtual_node(tb, h); 1581 1582 if (!Fh) { /* S[h] is the root. */ 1583 if (vn->vn_nr_item > 0) { 1584 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 1585 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */ 1586 } 1587 /* new_nr_item == 0. 1588 * Current root will be deleted resulting in 1589 * decrementing the tree height. */ 1590 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1); 1591 return CARRY_ON; 1592 } 1593 1594 if ((ret = get_parents(tb, h)) != CARRY_ON) 1595 return ret; 1596 1597 /* get free space of neighbors */ 1598 rfree = get_rfree(tb, h); 1599 lfree = get_lfree(tb, h); 1600 1601 /* determine maximal number of items we can fit into neighbors */ 1602 check_left(tb, h, lfree); 1603 check_right(tb, h, rfree); 1604 1605 if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) { /* Balance condition for the internal node is valid. 1606 * In this case we balance only if it leads to better packing. */ 1607 if (vn->vn_nr_item == MIN_NR_KEY(Sh)) { /* Here we join S[h] with one of its neighbors, 1608 * which is impossible with greater values of new_nr_item. */ 1609 if (tb->lnum[h] >= vn->vn_nr_item + 1) { 1610 /* All contents of S[h] can be moved to L[h]. */ 1611 int n; 1612 int order_L; 1613 1614 order_L = 1615 ((n = 1616 PATH_H_B_ITEM_ORDER(tb->tb_path, 1617 h)) == 1618 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; 1619 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / 1620 (DC_SIZE + KEY_SIZE); 1621 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, 1622 -1); 1623 return CARRY_ON; 1624 } 1625 1626 if (tb->rnum[h] >= vn->vn_nr_item + 1) { 1627 /* All contents of S[h] can be moved to R[h]. */ 1628 int n; 1629 int order_R; 1630 1631 order_R = 1632 ((n = 1633 PATH_H_B_ITEM_ORDER(tb->tb_path, 1634 h)) == 1635 B_NR_ITEMS(Fh)) ? 0 : n + 1; 1636 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / 1637 (DC_SIZE + KEY_SIZE); 1638 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, 1639 -1); 1640 return CARRY_ON; 1641 } 1642 } 1643 1644 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) { 1645 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */ 1646 int to_r; 1647 1648 to_r = 1649 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - 1650 tb->rnum[h] + vn->vn_nr_item + 1) / 2 - 1651 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]); 1652 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 1653 0, NULL, -1, -1); 1654 return CARRY_ON; 1655 } 1656 1657 /* Balancing does not lead to better packing. */ 1658 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 1659 return NO_BALANCING_NEEDED; 1660 } 1661 1662 /* Current node contain insufficient number of items. Balancing is required. */ 1663 /* Check whether we can merge S[h] with left neighbor. */ 1664 if (tb->lnum[h] >= vn->vn_nr_item + 1) 1665 if (is_left_neighbor_in_cache(tb, h) 1666 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) { 1667 int n; 1668 int order_L; 1669 1670 order_L = 1671 ((n = 1672 PATH_H_B_ITEM_ORDER(tb->tb_path, 1673 h)) == 1674 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; 1675 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE + 1676 KEY_SIZE); 1677 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1); 1678 return CARRY_ON; 1679 } 1680 1681 /* Check whether we can merge S[h] with right neighbor. */ 1682 if (tb->rnum[h] >= vn->vn_nr_item + 1) { 1683 int n; 1684 int order_R; 1685 1686 order_R = 1687 ((n = 1688 PATH_H_B_ITEM_ORDER(tb->tb_path, 1689 h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1); 1690 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE + 1691 KEY_SIZE); 1692 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1); 1693 return CARRY_ON; 1694 } 1695 1696 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */ 1697 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) { 1698 int to_r; 1699 1700 to_r = 1701 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] + 1702 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - 1703 tb->rnum[h]); 1704 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, 1705 -1, -1); 1706 return CARRY_ON; 1707 } 1708 1709 /* For internal nodes try to borrow item from a neighbor */ 1710 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root"); 1711 1712 /* Borrow one or two items from caching neighbor */ 1713 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) { 1714 int from_l; 1715 1716 from_l = 1717 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item + 1718 1) / 2 - (vn->vn_nr_item + 1); 1719 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1); 1720 return CARRY_ON; 1721 } 1722 1723 set_parameters(tb, h, 0, 1724 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item + 1725 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1); 1726 return CARRY_ON; 1727 } 1728 1729 /* Check whether current node S[h] is balanced when Decreasing its size by 1730 * Deleting or Truncating for LEAF node of S+tree. 1731 * Calculate parameters for balancing for current level h. 1732 * Parameters: 1733 * tb tree_balance structure; 1734 * h current level of the node; 1735 * inum item number in S[h]; 1736 * mode i - insert, p - paste; 1737 * Returns: 1 - schedule occurred; 1738 * 0 - balancing for higher levels needed; 1739 * -1 - no balancing for higher levels needed; 1740 * -2 - no disk space. 1741 */ 1742 static int dc_check_balance_leaf(struct tree_balance *tb, int h) 1743 { 1744 struct virtual_node *vn = tb->tb_vn; 1745 1746 /* Number of bytes that must be deleted from 1747 (value is negative if bytes are deleted) buffer which 1748 contains node being balanced. The mnemonic is that the 1749 attempted change in node space used level is levbytes bytes. */ 1750 int levbytes; 1751 /* the maximal item size */ 1752 int maxsize, ret; 1753 /* S0 is the node whose balance is currently being checked, 1754 and F0 is its father. */ 1755 struct buffer_head *S0, *F0; 1756 int lfree, rfree /* free space in L and R */ ; 1757 1758 S0 = PATH_H_PBUFFER(tb->tb_path, 0); 1759 F0 = PATH_H_PPARENT(tb->tb_path, 0); 1760 1761 levbytes = tb->insert_size[h]; 1762 1763 maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */ 1764 1765 if (!F0) { /* S[0] is the root now. */ 1766 1767 RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0), 1768 "vs-8240: attempt to create empty buffer tree"); 1769 1770 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 1771 return NO_BALANCING_NEEDED; 1772 } 1773 1774 if ((ret = get_parents(tb, h)) != CARRY_ON) 1775 return ret; 1776 1777 /* get free space of neighbors */ 1778 rfree = get_rfree(tb, h); 1779 lfree = get_lfree(tb, h); 1780 1781 create_virtual_node(tb, h); 1782 1783 /* if 3 leaves can be merge to one, set parameters and return */ 1784 if (are_leaves_removable(tb, lfree, rfree)) 1785 return CARRY_ON; 1786 1787 /* determine maximal number of items we can shift to the left/right neighbor 1788 and the maximal number of bytes that can flow to the left/right neighbor 1789 from the left/right most liquid item that cannot be shifted from S[0] entirely 1790 */ 1791 check_left(tb, h, lfree); 1792 check_right(tb, h, rfree); 1793 1794 /* check whether we can merge S with left neighbor. */ 1795 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1) 1796 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 */ 1797 !tb->FR[h]) { 1798 1799 RFALSE(!tb->FL[h], 1800 "vs-8245: dc_check_balance_leaf: FL[h] must exist"); 1801 1802 /* set parameter to merge S[0] with its left neighbor */ 1803 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1); 1804 return CARRY_ON; 1805 } 1806 1807 /* check whether we can merge S[0] with right neighbor. */ 1808 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) { 1809 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1); 1810 return CARRY_ON; 1811 } 1812 1813 /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */ 1814 if (is_leaf_removable(tb)) 1815 return CARRY_ON; 1816 1817 /* Balancing is not required. */ 1818 tb->s0num = vn->vn_nr_item; 1819 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); 1820 return NO_BALANCING_NEEDED; 1821 } 1822 1823 /* Check whether current node S[h] is balanced when Decreasing its size by 1824 * Deleting or Cutting. 1825 * Calculate parameters for balancing for current level h. 1826 * Parameters: 1827 * tb tree_balance structure; 1828 * h current level of the node; 1829 * inum item number in S[h]; 1830 * mode d - delete, c - cut. 1831 * Returns: 1 - schedule occurred; 1832 * 0 - balancing for higher levels needed; 1833 * -1 - no balancing for higher levels needed; 1834 * -2 - no disk space. 1835 */ 1836 static int dc_check_balance(struct tree_balance *tb, int h) 1837 { 1838 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)), 1839 "vs-8250: S is not initialized"); 1840 1841 if (h) 1842 return dc_check_balance_internal(tb, h); 1843 else 1844 return dc_check_balance_leaf(tb, h); 1845 } 1846 1847 /* Check whether current node S[h] is balanced. 1848 * Calculate parameters for balancing for current level h. 1849 * Parameters: 1850 * 1851 * tb tree_balance structure: 1852 * 1853 * tb is a large structure that must be read about in the header file 1854 * at the same time as this procedure if the reader is to successfully 1855 * understand this procedure 1856 * 1857 * h current level of the node; 1858 * inum item number in S[h]; 1859 * mode i - insert, p - paste, d - delete, c - cut. 1860 * Returns: 1 - schedule occurred; 1861 * 0 - balancing for higher levels needed; 1862 * -1 - no balancing for higher levels needed; 1863 * -2 - no disk space. 1864 */ 1865 static int check_balance(int mode, 1866 struct tree_balance *tb, 1867 int h, 1868 int inum, 1869 int pos_in_item, 1870 struct item_head *ins_ih, const void *data) 1871 { 1872 struct virtual_node *vn; 1873 1874 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf); 1875 vn->vn_free_ptr = (char *)(tb->tb_vn + 1); 1876 vn->vn_mode = mode; 1877 vn->vn_affected_item_num = inum; 1878 vn->vn_pos_in_item = pos_in_item; 1879 vn->vn_ins_ih = ins_ih; 1880 vn->vn_data = data; 1881 1882 RFALSE(mode == M_INSERT && !vn->vn_ins_ih, 1883 "vs-8255: ins_ih can not be 0 in insert mode"); 1884 1885 if (tb->insert_size[h] > 0) 1886 /* Calculate balance parameters when size of node is increasing. */ 1887 return ip_check_balance(tb, h); 1888 1889 /* Calculate balance parameters when size of node is decreasing. */ 1890 return dc_check_balance(tb, h); 1891 } 1892 1893 /* Check whether parent at the path is the really parent of the current node.*/ 1894 static int get_direct_parent(struct tree_balance *tb, int h) 1895 { 1896 struct buffer_head *bh; 1897 struct treepath *path = tb->tb_path; 1898 int position, 1899 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h); 1900 1901 /* We are in the root or in the new root. */ 1902 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) { 1903 1904 RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET - 1, 1905 "PAP-8260: invalid offset in the path"); 1906 1907 if (PATH_OFFSET_PBUFFER(path, FIRST_PATH_ELEMENT_OFFSET)-> 1908 b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) { 1909 /* Root is not changed. */ 1910 PATH_OFFSET_PBUFFER(path, path_offset - 1) = NULL; 1911 PATH_OFFSET_POSITION(path, path_offset - 1) = 0; 1912 return CARRY_ON; 1913 } 1914 return REPEAT_SEARCH; /* Root is changed and we must recalculate the path. */ 1915 } 1916 1917 if (!B_IS_IN_TREE 1918 (bh = PATH_OFFSET_PBUFFER(path, path_offset - 1))) 1919 return REPEAT_SEARCH; /* Parent in the path is not in the tree. */ 1920 1921 if ((position = 1922 PATH_OFFSET_POSITION(path, 1923 path_offset - 1)) > B_NR_ITEMS(bh)) 1924 return REPEAT_SEARCH; 1925 1926 if (B_N_CHILD_NUM(bh, position) != 1927 PATH_OFFSET_PBUFFER(path, path_offset)->b_blocknr) 1928 /* Parent in the path is not parent of the current node in the tree. */ 1929 return REPEAT_SEARCH; 1930 1931 if (buffer_locked(bh)) { 1932 int depth = reiserfs_write_unlock_nested(tb->tb_sb); 1933 __wait_on_buffer(bh); 1934 reiserfs_write_lock_nested(tb->tb_sb, depth); 1935 if (FILESYSTEM_CHANGED_TB(tb)) 1936 return REPEAT_SEARCH; 1937 } 1938 1939 return CARRY_ON; /* Parent in the path is unlocked and really parent of the current node. */ 1940 } 1941 1942 /* Using lnum[h] and rnum[h] we should determine what neighbors 1943 * of S[h] we 1944 * need in order to balance S[h], and get them if necessary. 1945 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked; 1946 * CARRY_ON - schedule didn't occur while the function worked; 1947 */ 1948 static int get_neighbors(struct tree_balance *tb, int h) 1949 { 1950 int child_position, 1951 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1); 1952 unsigned long son_number; 1953 struct super_block *sb = tb->tb_sb; 1954 struct buffer_head *bh; 1955 int depth; 1956 1957 PROC_INFO_INC(sb, get_neighbors[h]); 1958 1959 if (tb->lnum[h]) { 1960 /* We need left neighbor to balance S[h]. */ 1961 PROC_INFO_INC(sb, need_l_neighbor[h]); 1962 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset); 1963 1964 RFALSE(bh == tb->FL[h] && 1965 !PATH_OFFSET_POSITION(tb->tb_path, path_offset), 1966 "PAP-8270: invalid position in the parent"); 1967 1968 child_position = 1969 (bh == 1970 tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb-> 1971 FL[h]); 1972 son_number = B_N_CHILD_NUM(tb->FL[h], child_position); 1973 depth = reiserfs_write_unlock_nested(tb->tb_sb); 1974 bh = sb_bread(sb, son_number); 1975 reiserfs_write_lock_nested(tb->tb_sb, depth); 1976 if (!bh) 1977 return IO_ERROR; 1978 if (FILESYSTEM_CHANGED_TB(tb)) { 1979 brelse(bh); 1980 PROC_INFO_INC(sb, get_neighbors_restart[h]); 1981 return REPEAT_SEARCH; 1982 } 1983 1984 RFALSE(!B_IS_IN_TREE(tb->FL[h]) || 1985 child_position > B_NR_ITEMS(tb->FL[h]) || 1986 B_N_CHILD_NUM(tb->FL[h], child_position) != 1987 bh->b_blocknr, "PAP-8275: invalid parent"); 1988 RFALSE(!B_IS_IN_TREE(bh), "PAP-8280: invalid child"); 1989 RFALSE(!h && 1990 B_FREE_SPACE(bh) != 1991 MAX_CHILD_SIZE(bh) - 1992 dc_size(B_N_CHILD(tb->FL[0], child_position)), 1993 "PAP-8290: invalid child size of left neighbor"); 1994 1995 brelse(tb->L[h]); 1996 tb->L[h] = bh; 1997 } 1998 1999 /* We need right neighbor to balance S[path_offset]. */ 2000 if (tb->rnum[h]) { /* We need right neighbor to balance S[path_offset]. */ 2001 PROC_INFO_INC(sb, need_r_neighbor[h]); 2002 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset); 2003 2004 RFALSE(bh == tb->FR[h] && 2005 PATH_OFFSET_POSITION(tb->tb_path, 2006 path_offset) >= 2007 B_NR_ITEMS(bh), 2008 "PAP-8295: invalid position in the parent"); 2009 2010 child_position = 2011 (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0; 2012 son_number = B_N_CHILD_NUM(tb->FR[h], child_position); 2013 depth = reiserfs_write_unlock_nested(tb->tb_sb); 2014 bh = sb_bread(sb, son_number); 2015 reiserfs_write_lock_nested(tb->tb_sb, depth); 2016 if (!bh) 2017 return IO_ERROR; 2018 if (FILESYSTEM_CHANGED_TB(tb)) { 2019 brelse(bh); 2020 PROC_INFO_INC(sb, get_neighbors_restart[h]); 2021 return REPEAT_SEARCH; 2022 } 2023 brelse(tb->R[h]); 2024 tb->R[h] = bh; 2025 2026 RFALSE(!h 2027 && B_FREE_SPACE(bh) != 2028 MAX_CHILD_SIZE(bh) - 2029 dc_size(B_N_CHILD(tb->FR[0], child_position)), 2030 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)", 2031 B_FREE_SPACE(bh), MAX_CHILD_SIZE(bh), 2032 dc_size(B_N_CHILD(tb->FR[0], child_position))); 2033 2034 } 2035 return CARRY_ON; 2036 } 2037 2038 static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh) 2039 { 2040 int max_num_of_items; 2041 int max_num_of_entries; 2042 unsigned long blocksize = sb->s_blocksize; 2043 2044 #define MIN_NAME_LEN 1 2045 2046 max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN); 2047 max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) / 2048 (DEH_SIZE + MIN_NAME_LEN); 2049 2050 return sizeof(struct virtual_node) + 2051 max(max_num_of_items * sizeof(struct virtual_item), 2052 sizeof(struct virtual_item) + sizeof(struct direntry_uarea) + 2053 (max_num_of_entries - 1) * sizeof(__u16)); 2054 } 2055 2056 /* maybe we should fail balancing we are going to perform when kmalloc 2057 fails several times. But now it will loop until kmalloc gets 2058 required memory */ 2059 static int get_mem_for_virtual_node(struct tree_balance *tb) 2060 { 2061 int check_fs = 0; 2062 int size; 2063 char *buf; 2064 2065 size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path)); 2066 2067 if (size > tb->vn_buf_size) { 2068 /* we have to allocate more memory for virtual node */ 2069 if (tb->vn_buf) { 2070 /* free memory allocated before */ 2071 kfree(tb->vn_buf); 2072 /* this is not needed if kfree is atomic */ 2073 check_fs = 1; 2074 } 2075 2076 /* virtual node requires now more memory */ 2077 tb->vn_buf_size = size; 2078 2079 /* get memory for virtual item */ 2080 buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN); 2081 if (!buf) { 2082 /* getting memory with GFP_KERNEL priority may involve 2083 balancing now (due to indirect_to_direct conversion on 2084 dcache shrinking). So, release path and collected 2085 resources here */ 2086 free_buffers_in_tb(tb); 2087 buf = kmalloc(size, GFP_NOFS); 2088 if (!buf) { 2089 tb->vn_buf_size = 0; 2090 } 2091 tb->vn_buf = buf; 2092 schedule(); 2093 return REPEAT_SEARCH; 2094 } 2095 2096 tb->vn_buf = buf; 2097 } 2098 2099 if (check_fs && FILESYSTEM_CHANGED_TB(tb)) 2100 return REPEAT_SEARCH; 2101 2102 return CARRY_ON; 2103 } 2104 2105 #ifdef CONFIG_REISERFS_CHECK 2106 static void tb_buffer_sanity_check(struct super_block *sb, 2107 struct buffer_head *bh, 2108 const char *descr, int level) 2109 { 2110 if (bh) { 2111 if (atomic_read(&(bh->b_count)) <= 0) 2112 2113 reiserfs_panic(sb, "jmacd-1", "negative or zero " 2114 "reference counter for buffer %s[%d] " 2115 "(%b)", descr, level, bh); 2116 2117 if (!buffer_uptodate(bh)) 2118 reiserfs_panic(sb, "jmacd-2", "buffer is not up " 2119 "to date %s[%d] (%b)", 2120 descr, level, bh); 2121 2122 if (!B_IS_IN_TREE(bh)) 2123 reiserfs_panic(sb, "jmacd-3", "buffer is not " 2124 "in tree %s[%d] (%b)", 2125 descr, level, bh); 2126 2127 if (bh->b_bdev != sb->s_bdev) 2128 reiserfs_panic(sb, "jmacd-4", "buffer has wrong " 2129 "device %s[%d] (%b)", 2130 descr, level, bh); 2131 2132 if (bh->b_size != sb->s_blocksize) 2133 reiserfs_panic(sb, "jmacd-5", "buffer has wrong " 2134 "blocksize %s[%d] (%b)", 2135 descr, level, bh); 2136 2137 if (bh->b_blocknr > SB_BLOCK_COUNT(sb)) 2138 reiserfs_panic(sb, "jmacd-6", "buffer block " 2139 "number too high %s[%d] (%b)", 2140 descr, level, bh); 2141 } 2142 } 2143 #else 2144 static void tb_buffer_sanity_check(struct super_block *sb, 2145 struct buffer_head *bh, 2146 const char *descr, int level) 2147 {; 2148 } 2149 #endif 2150 2151 static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh) 2152 { 2153 return reiserfs_prepare_for_journal(s, bh, 0); 2154 } 2155 2156 static int wait_tb_buffers_until_unlocked(struct tree_balance *tb) 2157 { 2158 struct buffer_head *locked; 2159 #ifdef CONFIG_REISERFS_CHECK 2160 int repeat_counter = 0; 2161 #endif 2162 int i; 2163 2164 do { 2165 2166 locked = NULL; 2167 2168 for (i = tb->tb_path->path_length; 2169 !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) { 2170 if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) { 2171 /* if I understand correctly, we can only be sure the last buffer 2172 ** in the path is in the tree --clm 2173 */ 2174 #ifdef CONFIG_REISERFS_CHECK 2175 if (PATH_PLAST_BUFFER(tb->tb_path) == 2176 PATH_OFFSET_PBUFFER(tb->tb_path, i)) 2177 tb_buffer_sanity_check(tb->tb_sb, 2178 PATH_OFFSET_PBUFFER 2179 (tb->tb_path, 2180 i), "S", 2181 tb->tb_path-> 2182 path_length - i); 2183 #endif 2184 if (!clear_all_dirty_bits(tb->tb_sb, 2185 PATH_OFFSET_PBUFFER 2186 (tb->tb_path, 2187 i))) { 2188 locked = 2189 PATH_OFFSET_PBUFFER(tb->tb_path, 2190 i); 2191 } 2192 } 2193 } 2194 2195 for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i]; 2196 i++) { 2197 2198 if (tb->lnum[i]) { 2199 2200 if (tb->L[i]) { 2201 tb_buffer_sanity_check(tb->tb_sb, 2202 tb->L[i], 2203 "L", i); 2204 if (!clear_all_dirty_bits 2205 (tb->tb_sb, tb->L[i])) 2206 locked = tb->L[i]; 2207 } 2208 2209 if (!locked && tb->FL[i]) { 2210 tb_buffer_sanity_check(tb->tb_sb, 2211 tb->FL[i], 2212 "FL", i); 2213 if (!clear_all_dirty_bits 2214 (tb->tb_sb, tb->FL[i])) 2215 locked = tb->FL[i]; 2216 } 2217 2218 if (!locked && tb->CFL[i]) { 2219 tb_buffer_sanity_check(tb->tb_sb, 2220 tb->CFL[i], 2221 "CFL", i); 2222 if (!clear_all_dirty_bits 2223 (tb->tb_sb, tb->CFL[i])) 2224 locked = tb->CFL[i]; 2225 } 2226 2227 } 2228 2229 if (!locked && (tb->rnum[i])) { 2230 2231 if (tb->R[i]) { 2232 tb_buffer_sanity_check(tb->tb_sb, 2233 tb->R[i], 2234 "R", i); 2235 if (!clear_all_dirty_bits 2236 (tb->tb_sb, tb->R[i])) 2237 locked = tb->R[i]; 2238 } 2239 2240 if (!locked && tb->FR[i]) { 2241 tb_buffer_sanity_check(tb->tb_sb, 2242 tb->FR[i], 2243 "FR", i); 2244 if (!clear_all_dirty_bits 2245 (tb->tb_sb, tb->FR[i])) 2246 locked = tb->FR[i]; 2247 } 2248 2249 if (!locked && tb->CFR[i]) { 2250 tb_buffer_sanity_check(tb->tb_sb, 2251 tb->CFR[i], 2252 "CFR", i); 2253 if (!clear_all_dirty_bits 2254 (tb->tb_sb, tb->CFR[i])) 2255 locked = tb->CFR[i]; 2256 } 2257 } 2258 } 2259 /* as far as I can tell, this is not required. The FEB list seems 2260 ** to be full of newly allocated nodes, which will never be locked, 2261 ** dirty, or anything else. 2262 ** To be safe, I'm putting in the checks and waits in. For the moment, 2263 ** they are needed to keep the code in journal.c from complaining 2264 ** about the buffer. That code is inside CONFIG_REISERFS_CHECK as well. 2265 ** --clm 2266 */ 2267 for (i = 0; !locked && i < MAX_FEB_SIZE; i++) { 2268 if (tb->FEB[i]) { 2269 if (!clear_all_dirty_bits 2270 (tb->tb_sb, tb->FEB[i])) 2271 locked = tb->FEB[i]; 2272 } 2273 } 2274 2275 if (locked) { 2276 int depth; 2277 #ifdef CONFIG_REISERFS_CHECK 2278 repeat_counter++; 2279 if ((repeat_counter % 10000) == 0) { 2280 reiserfs_warning(tb->tb_sb, "reiserfs-8200", 2281 "too many iterations waiting " 2282 "for buffer to unlock " 2283 "(%b)", locked); 2284 2285 /* Don't loop forever. Try to recover from possible error. */ 2286 2287 return (FILESYSTEM_CHANGED_TB(tb)) ? 2288 REPEAT_SEARCH : CARRY_ON; 2289 } 2290 #endif 2291 depth = reiserfs_write_unlock_nested(tb->tb_sb); 2292 __wait_on_buffer(locked); 2293 reiserfs_write_lock_nested(tb->tb_sb, depth); 2294 if (FILESYSTEM_CHANGED_TB(tb)) 2295 return REPEAT_SEARCH; 2296 } 2297 2298 } while (locked); 2299 2300 return CARRY_ON; 2301 } 2302 2303 /* Prepare for balancing, that is 2304 * get all necessary parents, and neighbors; 2305 * analyze what and where should be moved; 2306 * get sufficient number of new nodes; 2307 * Balancing will start only after all resources will be collected at a time. 2308 * 2309 * When ported to SMP kernels, only at the last moment after all needed nodes 2310 * are collected in cache, will the resources be locked using the usual 2311 * textbook ordered lock acquisition algorithms. Note that ensuring that 2312 * this code neither write locks what it does not need to write lock nor locks out of order 2313 * will be a pain in the butt that could have been avoided. Grumble grumble. -Hans 2314 * 2315 * fix is meant in the sense of render unchanging 2316 * 2317 * Latency might be improved by first gathering a list of what buffers are needed 2318 * and then getting as many of them in parallel as possible? -Hans 2319 * 2320 * Parameters: 2321 * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append) 2322 * tb tree_balance structure; 2323 * inum item number in S[h]; 2324 * pos_in_item - comment this if you can 2325 * ins_ih item head of item being inserted 2326 * data inserted item or data to be pasted 2327 * Returns: 1 - schedule occurred while the function worked; 2328 * 0 - schedule didn't occur while the function worked; 2329 * -1 - if no_disk_space 2330 */ 2331 2332 int fix_nodes(int op_mode, struct tree_balance *tb, 2333 struct item_head *ins_ih, const void *data) 2334 { 2335 int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path); 2336 int pos_in_item; 2337 2338 /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared 2339 ** during wait_tb_buffers_run 2340 */ 2341 int wait_tb_buffers_run = 0; 2342 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path); 2343 2344 ++REISERFS_SB(tb->tb_sb)->s_fix_nodes; 2345 2346 pos_in_item = tb->tb_path->pos_in_item; 2347 2348 tb->fs_gen = get_generation(tb->tb_sb); 2349 2350 /* we prepare and log the super here so it will already be in the 2351 ** transaction when do_balance needs to change it. 2352 ** This way do_balance won't have to schedule when trying to prepare 2353 ** the super for logging 2354 */ 2355 reiserfs_prepare_for_journal(tb->tb_sb, 2356 SB_BUFFER_WITH_SB(tb->tb_sb), 1); 2357 journal_mark_dirty(tb->transaction_handle, tb->tb_sb, 2358 SB_BUFFER_WITH_SB(tb->tb_sb)); 2359 if (FILESYSTEM_CHANGED_TB(tb)) 2360 return REPEAT_SEARCH; 2361 2362 /* if it possible in indirect_to_direct conversion */ 2363 if (buffer_locked(tbS0)) { 2364 int depth = reiserfs_write_unlock_nested(tb->tb_sb); 2365 __wait_on_buffer(tbS0); 2366 reiserfs_write_lock_nested(tb->tb_sb, depth); 2367 if (FILESYSTEM_CHANGED_TB(tb)) 2368 return REPEAT_SEARCH; 2369 } 2370 #ifdef CONFIG_REISERFS_CHECK 2371 if (REISERFS_SB(tb->tb_sb)->cur_tb) { 2372 print_cur_tb("fix_nodes"); 2373 reiserfs_panic(tb->tb_sb, "PAP-8305", 2374 "there is pending do_balance"); 2375 } 2376 2377 if (!buffer_uptodate(tbS0) || !B_IS_IN_TREE(tbS0)) 2378 reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is " 2379 "not uptodate at the beginning of fix_nodes " 2380 "or not in tree (mode %c)", 2381 tbS0, tbS0, op_mode); 2382 2383 /* Check parameters. */ 2384 switch (op_mode) { 2385 case M_INSERT: 2386 if (item_num <= 0 || item_num > B_NR_ITEMS(tbS0)) 2387 reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect " 2388 "item number %d (in S0 - %d) in case " 2389 "of insert", item_num, 2390 B_NR_ITEMS(tbS0)); 2391 break; 2392 case M_PASTE: 2393 case M_DELETE: 2394 case M_CUT: 2395 if (item_num < 0 || item_num >= B_NR_ITEMS(tbS0)) { 2396 print_block(tbS0, 0, -1, -1); 2397 reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect " 2398 "item number(%d); mode = %c " 2399 "insert_size = %d", 2400 item_num, op_mode, 2401 tb->insert_size[0]); 2402 } 2403 break; 2404 default: 2405 reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode " 2406 "of operation"); 2407 } 2408 #endif 2409 2410 if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH) 2411 // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat 2412 return REPEAT_SEARCH; 2413 2414 /* Starting from the leaf level; for all levels h of the tree. */ 2415 for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) { 2416 ret = get_direct_parent(tb, h); 2417 if (ret != CARRY_ON) 2418 goto repeat; 2419 2420 ret = check_balance(op_mode, tb, h, item_num, 2421 pos_in_item, ins_ih, data); 2422 if (ret != CARRY_ON) { 2423 if (ret == NO_BALANCING_NEEDED) { 2424 /* No balancing for higher levels needed. */ 2425 ret = get_neighbors(tb, h); 2426 if (ret != CARRY_ON) 2427 goto repeat; 2428 if (h != MAX_HEIGHT - 1) 2429 tb->insert_size[h + 1] = 0; 2430 /* ok, analysis and resource gathering are complete */ 2431 break; 2432 } 2433 goto repeat; 2434 } 2435 2436 ret = get_neighbors(tb, h); 2437 if (ret != CARRY_ON) 2438 goto repeat; 2439 2440 /* No disk space, or schedule occurred and analysis may be 2441 * invalid and needs to be redone. */ 2442 ret = get_empty_nodes(tb, h); 2443 if (ret != CARRY_ON) 2444 goto repeat; 2445 2446 if (!PATH_H_PBUFFER(tb->tb_path, h)) { 2447 /* We have a positive insert size but no nodes exist on this 2448 level, this means that we are creating a new root. */ 2449 2450 RFALSE(tb->blknum[h] != 1, 2451 "PAP-8350: creating new empty root"); 2452 2453 if (h < MAX_HEIGHT - 1) 2454 tb->insert_size[h + 1] = 0; 2455 } else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) { 2456 if (tb->blknum[h] > 1) { 2457 /* The tree needs to be grown, so this node S[h] 2458 which is the root node is split into two nodes, 2459 and a new node (S[h+1]) will be created to 2460 become the root node. */ 2461 2462 RFALSE(h == MAX_HEIGHT - 1, 2463 "PAP-8355: attempt to create too high of a tree"); 2464 2465 tb->insert_size[h + 1] = 2466 (DC_SIZE + 2467 KEY_SIZE) * (tb->blknum[h] - 1) + 2468 DC_SIZE; 2469 } else if (h < MAX_HEIGHT - 1) 2470 tb->insert_size[h + 1] = 0; 2471 } else 2472 tb->insert_size[h + 1] = 2473 (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1); 2474 } 2475 2476 ret = wait_tb_buffers_until_unlocked(tb); 2477 if (ret == CARRY_ON) { 2478 if (FILESYSTEM_CHANGED_TB(tb)) { 2479 wait_tb_buffers_run = 1; 2480 ret = REPEAT_SEARCH; 2481 goto repeat; 2482 } else { 2483 return CARRY_ON; 2484 } 2485 } else { 2486 wait_tb_buffers_run = 1; 2487 goto repeat; 2488 } 2489 2490 repeat: 2491 // fix_nodes was unable to perform its calculation due to 2492 // filesystem got changed under us, lack of free disk space or i/o 2493 // failure. If the first is the case - the search will be 2494 // repeated. For now - free all resources acquired so far except 2495 // for the new allocated nodes 2496 { 2497 int i; 2498 2499 /* Release path buffers. */ 2500 if (wait_tb_buffers_run) { 2501 pathrelse_and_restore(tb->tb_sb, tb->tb_path); 2502 } else { 2503 pathrelse(tb->tb_path); 2504 } 2505 /* brelse all resources collected for balancing */ 2506 for (i = 0; i < MAX_HEIGHT; i++) { 2507 if (wait_tb_buffers_run) { 2508 reiserfs_restore_prepared_buffer(tb->tb_sb, 2509 tb->L[i]); 2510 reiserfs_restore_prepared_buffer(tb->tb_sb, 2511 tb->R[i]); 2512 reiserfs_restore_prepared_buffer(tb->tb_sb, 2513 tb->FL[i]); 2514 reiserfs_restore_prepared_buffer(tb->tb_sb, 2515 tb->FR[i]); 2516 reiserfs_restore_prepared_buffer(tb->tb_sb, 2517 tb-> 2518 CFL[i]); 2519 reiserfs_restore_prepared_buffer(tb->tb_sb, 2520 tb-> 2521 CFR[i]); 2522 } 2523 2524 brelse(tb->L[i]); 2525 brelse(tb->R[i]); 2526 brelse(tb->FL[i]); 2527 brelse(tb->FR[i]); 2528 brelse(tb->CFL[i]); 2529 brelse(tb->CFR[i]); 2530 2531 tb->L[i] = NULL; 2532 tb->R[i] = NULL; 2533 tb->FL[i] = NULL; 2534 tb->FR[i] = NULL; 2535 tb->CFL[i] = NULL; 2536 tb->CFR[i] = NULL; 2537 } 2538 2539 if (wait_tb_buffers_run) { 2540 for (i = 0; i < MAX_FEB_SIZE; i++) { 2541 if (tb->FEB[i]) 2542 reiserfs_restore_prepared_buffer 2543 (tb->tb_sb, tb->FEB[i]); 2544 } 2545 } 2546 return ret; 2547 } 2548 2549 } 2550 2551 /* Anatoly will probably forgive me renaming tb to tb. I just 2552 wanted to make lines shorter */ 2553 void unfix_nodes(struct tree_balance *tb) 2554 { 2555 int i; 2556 2557 /* Release path buffers. */ 2558 pathrelse_and_restore(tb->tb_sb, tb->tb_path); 2559 2560 /* brelse all resources collected for balancing */ 2561 for (i = 0; i < MAX_HEIGHT; i++) { 2562 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]); 2563 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]); 2564 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]); 2565 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]); 2566 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]); 2567 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]); 2568 2569 brelse(tb->L[i]); 2570 brelse(tb->R[i]); 2571 brelse(tb->FL[i]); 2572 brelse(tb->FR[i]); 2573 brelse(tb->CFL[i]); 2574 brelse(tb->CFR[i]); 2575 } 2576 2577 /* deal with list of allocated (used and unused) nodes */ 2578 for (i = 0; i < MAX_FEB_SIZE; i++) { 2579 if (tb->FEB[i]) { 2580 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr; 2581 /* de-allocated block which was not used by balancing and 2582 bforget about buffer for it */ 2583 brelse(tb->FEB[i]); 2584 reiserfs_free_block(tb->transaction_handle, NULL, 2585 blocknr, 0); 2586 } 2587 if (tb->used[i]) { 2588 /* release used as new nodes including a new root */ 2589 brelse(tb->used[i]); 2590 } 2591 } 2592 2593 kfree(tb->vn_buf); 2594 2595 } 2596