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