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