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