1 /* 2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README 3 */ 4 5 /* 6 * Written by Anatoly P. Pinchuk pap@namesys.botik.ru 7 * Programm System Institute 8 * Pereslavl-Zalessky Russia 9 */ 10 11 #include <linux/time.h> 12 #include <linux/string.h> 13 #include <linux/pagemap.h> 14 #include <linux/bio.h> 15 #include "reiserfs.h" 16 #include <linux/buffer_head.h> 17 #include <linux/quotaops.h> 18 19 /* Does the buffer contain a disk block which is in the tree. */ 20 inline int B_IS_IN_TREE(const struct buffer_head *bh) 21 { 22 23 RFALSE(B_LEVEL(bh) > MAX_HEIGHT, 24 "PAP-1010: block (%b) has too big level (%z)", bh, bh); 25 26 return (B_LEVEL(bh) != FREE_LEVEL); 27 } 28 29 /* to get item head in le form */ 30 inline void copy_item_head(struct item_head *to, 31 const struct item_head *from) 32 { 33 memcpy(to, from, IH_SIZE); 34 } 35 36 /* 37 * k1 is pointer to on-disk structure which is stored in little-endian 38 * form. k2 is pointer to cpu variable. For key of items of the same 39 * object this returns 0. 40 * Returns: -1 if key1 < key2 41 * 0 if key1 == key2 42 * 1 if key1 > key2 43 */ 44 inline int comp_short_keys(const struct reiserfs_key *le_key, 45 const struct cpu_key *cpu_key) 46 { 47 __u32 n; 48 n = le32_to_cpu(le_key->k_dir_id); 49 if (n < cpu_key->on_disk_key.k_dir_id) 50 return -1; 51 if (n > cpu_key->on_disk_key.k_dir_id) 52 return 1; 53 n = le32_to_cpu(le_key->k_objectid); 54 if (n < cpu_key->on_disk_key.k_objectid) 55 return -1; 56 if (n > cpu_key->on_disk_key.k_objectid) 57 return 1; 58 return 0; 59 } 60 61 /* 62 * k1 is pointer to on-disk structure which is stored in little-endian 63 * form. k2 is pointer to cpu variable. 64 * Compare keys using all 4 key fields. 65 * Returns: -1 if key1 < key2 0 66 * if key1 = key2 1 if key1 > key2 67 */ 68 static inline int comp_keys(const struct reiserfs_key *le_key, 69 const struct cpu_key *cpu_key) 70 { 71 int retval; 72 73 retval = comp_short_keys(le_key, cpu_key); 74 if (retval) 75 return retval; 76 if (le_key_k_offset(le_key_version(le_key), le_key) < 77 cpu_key_k_offset(cpu_key)) 78 return -1; 79 if (le_key_k_offset(le_key_version(le_key), le_key) > 80 cpu_key_k_offset(cpu_key)) 81 return 1; 82 83 if (cpu_key->key_length == 3) 84 return 0; 85 86 /* this part is needed only when tail conversion is in progress */ 87 if (le_key_k_type(le_key_version(le_key), le_key) < 88 cpu_key_k_type(cpu_key)) 89 return -1; 90 91 if (le_key_k_type(le_key_version(le_key), le_key) > 92 cpu_key_k_type(cpu_key)) 93 return 1; 94 95 return 0; 96 } 97 98 inline int comp_short_le_keys(const struct reiserfs_key *key1, 99 const struct reiserfs_key *key2) 100 { 101 __u32 *k1_u32, *k2_u32; 102 int key_length = REISERFS_SHORT_KEY_LEN; 103 104 k1_u32 = (__u32 *) key1; 105 k2_u32 = (__u32 *) key2; 106 for (; key_length--; ++k1_u32, ++k2_u32) { 107 if (le32_to_cpu(*k1_u32) < le32_to_cpu(*k2_u32)) 108 return -1; 109 if (le32_to_cpu(*k1_u32) > le32_to_cpu(*k2_u32)) 110 return 1; 111 } 112 return 0; 113 } 114 115 inline void le_key2cpu_key(struct cpu_key *to, const struct reiserfs_key *from) 116 { 117 int version; 118 to->on_disk_key.k_dir_id = le32_to_cpu(from->k_dir_id); 119 to->on_disk_key.k_objectid = le32_to_cpu(from->k_objectid); 120 121 /* find out version of the key */ 122 version = le_key_version(from); 123 to->version = version; 124 to->on_disk_key.k_offset = le_key_k_offset(version, from); 125 to->on_disk_key.k_type = le_key_k_type(version, from); 126 } 127 128 /* 129 * this does not say which one is bigger, it only returns 1 if keys 130 * are not equal, 0 otherwise 131 */ 132 inline int comp_le_keys(const struct reiserfs_key *k1, 133 const struct reiserfs_key *k2) 134 { 135 return memcmp(k1, k2, sizeof(struct reiserfs_key)); 136 } 137 138 /************************************************************************** 139 * Binary search toolkit function * 140 * Search for an item in the array by the item key * 141 * Returns: 1 if found, 0 if not found; * 142 * *pos = number of the searched element if found, else the * 143 * number of the first element that is larger than key. * 144 **************************************************************************/ 145 /* 146 * For those not familiar with binary search: lbound is the leftmost item 147 * that it could be, rbound the rightmost item that it could be. We examine 148 * the item halfway between lbound and rbound, and that tells us either 149 * that we can increase lbound, or decrease rbound, or that we have found it, 150 * or if lbound <= rbound that there are no possible items, and we have not 151 * found it. With each examination we cut the number of possible items it 152 * could be by one more than half rounded down, or we find it. 153 */ 154 static inline int bin_search(const void *key, /* Key to search for. */ 155 const void *base, /* First item in the array. */ 156 int num, /* Number of items in the array. */ 157 /* 158 * Item size in the array. searched. Lest the 159 * reader be confused, note that this is crafted 160 * as a general function, and when it is applied 161 * specifically to the array of item headers in a 162 * node, width is actually the item header size 163 * not the item size. 164 */ 165 int width, 166 int *pos /* Number of the searched for element. */ 167 ) 168 { 169 int rbound, lbound, j; 170 171 for (j = ((rbound = num - 1) + (lbound = 0)) / 2; 172 lbound <= rbound; j = (rbound + lbound) / 2) 173 switch (comp_keys 174 ((struct reiserfs_key *)((char *)base + j * width), 175 (struct cpu_key *)key)) { 176 case -1: 177 lbound = j + 1; 178 continue; 179 case 1: 180 rbound = j - 1; 181 continue; 182 case 0: 183 *pos = j; 184 return ITEM_FOUND; /* Key found in the array. */ 185 } 186 187 /* 188 * bin_search did not find given key, it returns position of key, 189 * that is minimal and greater than the given one. 190 */ 191 *pos = lbound; 192 return ITEM_NOT_FOUND; 193 } 194 195 196 /* Minimal possible key. It is never in the tree. */ 197 const struct reiserfs_key MIN_KEY = { 0, 0, {{0, 0},} }; 198 199 /* Maximal possible key. It is never in the tree. */ 200 static const struct reiserfs_key MAX_KEY = { 201 cpu_to_le32(0xffffffff), 202 cpu_to_le32(0xffffffff), 203 {{cpu_to_le32(0xffffffff), 204 cpu_to_le32(0xffffffff)},} 205 }; 206 207 /* 208 * Get delimiting key of the buffer by looking for it in the buffers in the 209 * path, starting from the bottom of the path, and going upwards. We must 210 * check the path's validity at each step. If the key is not in the path, 211 * there is no delimiting key in the tree (buffer is first or last buffer 212 * in tree), and in this case we return a special key, either MIN_KEY or 213 * MAX_KEY. 214 */ 215 static inline const struct reiserfs_key *get_lkey(const struct treepath *chk_path, 216 const struct super_block *sb) 217 { 218 int position, path_offset = chk_path->path_length; 219 struct buffer_head *parent; 220 221 RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET, 222 "PAP-5010: invalid offset in the path"); 223 224 /* While not higher in path than first element. */ 225 while (path_offset-- > FIRST_PATH_ELEMENT_OFFSET) { 226 227 RFALSE(!buffer_uptodate 228 (PATH_OFFSET_PBUFFER(chk_path, path_offset)), 229 "PAP-5020: parent is not uptodate"); 230 231 /* Parent at the path is not in the tree now. */ 232 if (!B_IS_IN_TREE 233 (parent = 234 PATH_OFFSET_PBUFFER(chk_path, path_offset))) 235 return &MAX_KEY; 236 /* Check whether position in the parent is correct. */ 237 if ((position = 238 PATH_OFFSET_POSITION(chk_path, 239 path_offset)) > 240 B_NR_ITEMS(parent)) 241 return &MAX_KEY; 242 /* Check whether parent at the path really points to the child. */ 243 if (B_N_CHILD_NUM(parent, position) != 244 PATH_OFFSET_PBUFFER(chk_path, 245 path_offset + 1)->b_blocknr) 246 return &MAX_KEY; 247 /* 248 * Return delimiting key if position in the parent 249 * is not equal to zero. 250 */ 251 if (position) 252 return internal_key(parent, position - 1); 253 } 254 /* Return MIN_KEY if we are in the root of the buffer tree. */ 255 if (PATH_OFFSET_PBUFFER(chk_path, FIRST_PATH_ELEMENT_OFFSET)-> 256 b_blocknr == SB_ROOT_BLOCK(sb)) 257 return &MIN_KEY; 258 return &MAX_KEY; 259 } 260 261 /* Get delimiting key of the buffer at the path and its right neighbor. */ 262 inline const struct reiserfs_key *get_rkey(const struct treepath *chk_path, 263 const struct super_block *sb) 264 { 265 int position, path_offset = chk_path->path_length; 266 struct buffer_head *parent; 267 268 RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET, 269 "PAP-5030: invalid offset in the path"); 270 271 while (path_offset-- > FIRST_PATH_ELEMENT_OFFSET) { 272 273 RFALSE(!buffer_uptodate 274 (PATH_OFFSET_PBUFFER(chk_path, path_offset)), 275 "PAP-5040: parent is not uptodate"); 276 277 /* Parent at the path is not in the tree now. */ 278 if (!B_IS_IN_TREE 279 (parent = 280 PATH_OFFSET_PBUFFER(chk_path, path_offset))) 281 return &MIN_KEY; 282 /* Check whether position in the parent is correct. */ 283 if ((position = 284 PATH_OFFSET_POSITION(chk_path, 285 path_offset)) > 286 B_NR_ITEMS(parent)) 287 return &MIN_KEY; 288 /* 289 * Check whether parent at the path really points 290 * to the child. 291 */ 292 if (B_N_CHILD_NUM(parent, position) != 293 PATH_OFFSET_PBUFFER(chk_path, 294 path_offset + 1)->b_blocknr) 295 return &MIN_KEY; 296 297 /* 298 * Return delimiting key if position in the parent 299 * is not the last one. 300 */ 301 if (position != B_NR_ITEMS(parent)) 302 return internal_key(parent, position); 303 } 304 305 /* Return MAX_KEY if we are in the root of the buffer tree. */ 306 if (PATH_OFFSET_PBUFFER(chk_path, FIRST_PATH_ELEMENT_OFFSET)-> 307 b_blocknr == SB_ROOT_BLOCK(sb)) 308 return &MAX_KEY; 309 return &MIN_KEY; 310 } 311 312 /* 313 * Check whether a key is contained in the tree rooted from a buffer at a path. 314 * This works by looking at the left and right delimiting keys for the buffer 315 * in the last path_element in the path. These delimiting keys are stored 316 * at least one level above that buffer in the tree. If the buffer is the 317 * first or last node in the tree order then one of the delimiting keys may 318 * be absent, and in this case get_lkey and get_rkey return a special key 319 * which is MIN_KEY or MAX_KEY. 320 */ 321 static inline int key_in_buffer( 322 /* Path which should be checked. */ 323 struct treepath *chk_path, 324 /* Key which should be checked. */ 325 const struct cpu_key *key, 326 struct super_block *sb 327 ) 328 { 329 330 RFALSE(!key || chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET 331 || chk_path->path_length > MAX_HEIGHT, 332 "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)", 333 key, chk_path->path_length); 334 RFALSE(!PATH_PLAST_BUFFER(chk_path)->b_bdev, 335 "PAP-5060: device must not be NODEV"); 336 337 if (comp_keys(get_lkey(chk_path, sb), key) == 1) 338 /* left delimiting key is bigger, that the key we look for */ 339 return 0; 340 /* if ( comp_keys(key, get_rkey(chk_path, sb)) != -1 ) */ 341 if (comp_keys(get_rkey(chk_path, sb), key) != 1) 342 /* key must be less than right delimitiing key */ 343 return 0; 344 return 1; 345 } 346 347 int reiserfs_check_path(struct treepath *p) 348 { 349 RFALSE(p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET, 350 "path not properly relsed"); 351 return 0; 352 } 353 354 /* 355 * Drop the reference to each buffer in a path and restore 356 * dirty bits clean when preparing the buffer for the log. 357 * This version should only be called from fix_nodes() 358 */ 359 void pathrelse_and_restore(struct super_block *sb, 360 struct treepath *search_path) 361 { 362 int path_offset = search_path->path_length; 363 364 RFALSE(path_offset < ILLEGAL_PATH_ELEMENT_OFFSET, 365 "clm-4000: invalid path offset"); 366 367 while (path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) { 368 struct buffer_head *bh; 369 bh = PATH_OFFSET_PBUFFER(search_path, path_offset--); 370 reiserfs_restore_prepared_buffer(sb, bh); 371 brelse(bh); 372 } 373 search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; 374 } 375 376 /* Drop the reference to each buffer in a path */ 377 void pathrelse(struct treepath *search_path) 378 { 379 int path_offset = search_path->path_length; 380 381 RFALSE(path_offset < ILLEGAL_PATH_ELEMENT_OFFSET, 382 "PAP-5090: invalid path offset"); 383 384 while (path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) 385 brelse(PATH_OFFSET_PBUFFER(search_path, path_offset--)); 386 387 search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; 388 } 389 390 static int is_leaf(char *buf, int blocksize, struct buffer_head *bh) 391 { 392 struct block_head *blkh; 393 struct item_head *ih; 394 int used_space; 395 int prev_location; 396 int i; 397 int nr; 398 399 blkh = (struct block_head *)buf; 400 if (blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) { 401 reiserfs_warning(NULL, "reiserfs-5080", 402 "this should be caught earlier"); 403 return 0; 404 } 405 406 nr = blkh_nr_item(blkh); 407 if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) { 408 /* item number is too big or too small */ 409 reiserfs_warning(NULL, "reiserfs-5081", 410 "nr_item seems wrong: %z", bh); 411 return 0; 412 } 413 ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1; 414 used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location(ih)); 415 416 /* free space does not match to calculated amount of use space */ 417 if (used_space != blocksize - blkh_free_space(blkh)) { 418 reiserfs_warning(NULL, "reiserfs-5082", 419 "free space seems wrong: %z", bh); 420 return 0; 421 } 422 /* 423 * FIXME: it is_leaf will hit performance too much - we may have 424 * return 1 here 425 */ 426 427 /* check tables of item heads */ 428 ih = (struct item_head *)(buf + BLKH_SIZE); 429 prev_location = blocksize; 430 for (i = 0; i < nr; i++, ih++) { 431 if (le_ih_k_type(ih) == TYPE_ANY) { 432 reiserfs_warning(NULL, "reiserfs-5083", 433 "wrong item type for item %h", 434 ih); 435 return 0; 436 } 437 if (ih_location(ih) >= blocksize 438 || ih_location(ih) < IH_SIZE * nr) { 439 reiserfs_warning(NULL, "reiserfs-5084", 440 "item location seems wrong: %h", 441 ih); 442 return 0; 443 } 444 if (ih_item_len(ih) < 1 445 || ih_item_len(ih) > MAX_ITEM_LEN(blocksize)) { 446 reiserfs_warning(NULL, "reiserfs-5085", 447 "item length seems wrong: %h", 448 ih); 449 return 0; 450 } 451 if (prev_location - ih_location(ih) != ih_item_len(ih)) { 452 reiserfs_warning(NULL, "reiserfs-5086", 453 "item location seems wrong " 454 "(second one): %h", ih); 455 return 0; 456 } 457 if (is_direntry_le_ih(ih) && (ih_item_len(ih) < (ih_entry_count(ih) * IH_SIZE))) { 458 reiserfs_warning(NULL, "reiserfs-5093", 459 "item entry count seems wrong %h", 460 ih); 461 return 0; 462 } 463 prev_location = ih_location(ih); 464 } 465 466 /* one may imagine many more checks */ 467 return 1; 468 } 469 470 /* returns 1 if buf looks like an internal node, 0 otherwise */ 471 static int is_internal(char *buf, int blocksize, struct buffer_head *bh) 472 { 473 struct block_head *blkh; 474 int nr; 475 int used_space; 476 477 blkh = (struct block_head *)buf; 478 nr = blkh_level(blkh); 479 if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) { 480 /* this level is not possible for internal nodes */ 481 reiserfs_warning(NULL, "reiserfs-5087", 482 "this should be caught earlier"); 483 return 0; 484 } 485 486 nr = blkh_nr_item(blkh); 487 /* for internal which is not root we might check min number of keys */ 488 if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) { 489 reiserfs_warning(NULL, "reiserfs-5088", 490 "number of key seems wrong: %z", bh); 491 return 0; 492 } 493 494 used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1); 495 if (used_space != blocksize - blkh_free_space(blkh)) { 496 reiserfs_warning(NULL, "reiserfs-5089", 497 "free space seems wrong: %z", bh); 498 return 0; 499 } 500 501 /* one may imagine many more checks */ 502 return 1; 503 } 504 505 /* 506 * make sure that bh contains formatted node of reiserfs tree of 507 * 'level'-th level 508 */ 509 static int is_tree_node(struct buffer_head *bh, int level) 510 { 511 if (B_LEVEL(bh) != level) { 512 reiserfs_warning(NULL, "reiserfs-5090", "node level %d does " 513 "not match to the expected one %d", 514 B_LEVEL(bh), level); 515 return 0; 516 } 517 if (level == DISK_LEAF_NODE_LEVEL) 518 return is_leaf(bh->b_data, bh->b_size, bh); 519 520 return is_internal(bh->b_data, bh->b_size, bh); 521 } 522 523 #define SEARCH_BY_KEY_READA 16 524 525 /* 526 * The function is NOT SCHEDULE-SAFE! 527 * It might unlock the write lock if we needed to wait for a block 528 * to be read. Note that in this case it won't recover the lock to avoid 529 * high contention resulting from too much lock requests, especially 530 * the caller (search_by_key) will perform other schedule-unsafe 531 * operations just after calling this function. 532 * 533 * @return depth of lock to be restored after read completes 534 */ 535 static int search_by_key_reada(struct super_block *s, 536 struct buffer_head **bh, 537 b_blocknr_t *b, int num) 538 { 539 int i, j; 540 int depth = -1; 541 542 for (i = 0; i < num; i++) { 543 bh[i] = sb_getblk(s, b[i]); 544 } 545 /* 546 * We are going to read some blocks on which we 547 * have a reference. It's safe, though we might be 548 * reading blocks concurrently changed if we release 549 * the lock. But it's still fine because we check later 550 * if the tree changed 551 */ 552 for (j = 0; j < i; j++) { 553 /* 554 * note, this needs attention if we are getting rid of the BKL 555 * you have to make sure the prepared bit isn't set on this 556 * buffer 557 */ 558 if (!buffer_uptodate(bh[j])) { 559 if (depth == -1) 560 depth = reiserfs_write_unlock_nested(s); 561 ll_rw_block(REQ_OP_READ, REQ_RAHEAD, 1, bh + j); 562 } 563 brelse(bh[j]); 564 } 565 return depth; 566 } 567 568 /* 569 * This function fills up the path from the root to the leaf as it 570 * descends the tree looking for the key. It uses reiserfs_bread to 571 * try to find buffers in the cache given their block number. If it 572 * does not find them in the cache it reads them from disk. For each 573 * node search_by_key finds using reiserfs_bread it then uses 574 * bin_search to look through that node. bin_search will find the 575 * position of the block_number of the next node if it is looking 576 * through an internal node. If it is looking through a leaf node 577 * bin_search will find the position of the item which has key either 578 * equal to given key, or which is the maximal key less than the given 579 * key. search_by_key returns a path that must be checked for the 580 * correctness of the top of the path but need not be checked for the 581 * correctness of the bottom of the path 582 */ 583 /* 584 * search_by_key - search for key (and item) in stree 585 * @sb: superblock 586 * @key: pointer to key to search for 587 * @search_path: Allocated and initialized struct treepath; Returned filled 588 * on success. 589 * @stop_level: How far down the tree to search, Use DISK_LEAF_NODE_LEVEL to 590 * stop at leaf level. 591 * 592 * The function is NOT SCHEDULE-SAFE! 593 */ 594 int search_by_key(struct super_block *sb, const struct cpu_key *key, 595 struct treepath *search_path, int stop_level) 596 { 597 b_blocknr_t block_number; 598 int expected_level; 599 struct buffer_head *bh; 600 struct path_element *last_element; 601 int node_level, retval; 602 int fs_gen; 603 struct buffer_head *reada_bh[SEARCH_BY_KEY_READA]; 604 b_blocknr_t reada_blocks[SEARCH_BY_KEY_READA]; 605 int reada_count = 0; 606 607 #ifdef CONFIG_REISERFS_CHECK 608 int repeat_counter = 0; 609 #endif 610 611 PROC_INFO_INC(sb, search_by_key); 612 613 /* 614 * As we add each node to a path we increase its count. This means 615 * that we must be careful to release all nodes in a path before we 616 * either discard the path struct or re-use the path struct, as we 617 * do here. 618 */ 619 620 pathrelse(search_path); 621 622 /* 623 * With each iteration of this loop we search through the items in the 624 * current node, and calculate the next current node(next path element) 625 * for the next iteration of this loop.. 626 */ 627 block_number = SB_ROOT_BLOCK(sb); 628 expected_level = -1; 629 while (1) { 630 631 #ifdef CONFIG_REISERFS_CHECK 632 if (!(++repeat_counter % 50000)) 633 reiserfs_warning(sb, "PAP-5100", 634 "%s: there were %d iterations of " 635 "while loop looking for key %K", 636 current->comm, repeat_counter, 637 key); 638 #endif 639 640 /* prep path to have another element added to it. */ 641 last_element = 642 PATH_OFFSET_PELEMENT(search_path, 643 ++search_path->path_length); 644 fs_gen = get_generation(sb); 645 646 /* 647 * Read the next tree node, and set the last element 648 * in the path to have a pointer to it. 649 */ 650 if ((bh = last_element->pe_buffer = 651 sb_getblk(sb, block_number))) { 652 653 /* 654 * We'll need to drop the lock if we encounter any 655 * buffers that need to be read. If all of them are 656 * already up to date, we don't need to drop the lock. 657 */ 658 int depth = -1; 659 660 if (!buffer_uptodate(bh) && reada_count > 1) 661 depth = search_by_key_reada(sb, reada_bh, 662 reada_blocks, reada_count); 663 664 if (!buffer_uptodate(bh) && depth == -1) 665 depth = reiserfs_write_unlock_nested(sb); 666 667 ll_rw_block(REQ_OP_READ, 0, 1, &bh); 668 wait_on_buffer(bh); 669 670 if (depth != -1) 671 reiserfs_write_lock_nested(sb, depth); 672 if (!buffer_uptodate(bh)) 673 goto io_error; 674 } else { 675 io_error: 676 search_path->path_length--; 677 pathrelse(search_path); 678 return IO_ERROR; 679 } 680 reada_count = 0; 681 if (expected_level == -1) 682 expected_level = SB_TREE_HEIGHT(sb); 683 expected_level--; 684 685 /* 686 * It is possible that schedule occurred. We must check 687 * whether the key to search is still in the tree rooted 688 * from the current buffer. If not then repeat search 689 * from the root. 690 */ 691 if (fs_changed(fs_gen, sb) && 692 (!B_IS_IN_TREE(bh) || 693 B_LEVEL(bh) != expected_level || 694 !key_in_buffer(search_path, key, sb))) { 695 PROC_INFO_INC(sb, search_by_key_fs_changed); 696 PROC_INFO_INC(sb, search_by_key_restarted); 697 PROC_INFO_INC(sb, 698 sbk_restarted[expected_level - 1]); 699 pathrelse(search_path); 700 701 /* 702 * Get the root block number so that we can 703 * repeat the search starting from the root. 704 */ 705 block_number = SB_ROOT_BLOCK(sb); 706 expected_level = -1; 707 708 /* repeat search from the root */ 709 continue; 710 } 711 712 /* 713 * only check that the key is in the buffer if key is not 714 * equal to the MAX_KEY. Latter case is only possible in 715 * "finish_unfinished()" processing during mount. 716 */ 717 RFALSE(comp_keys(&MAX_KEY, key) && 718 !key_in_buffer(search_path, key, sb), 719 "PAP-5130: key is not in the buffer"); 720 #ifdef CONFIG_REISERFS_CHECK 721 if (REISERFS_SB(sb)->cur_tb) { 722 print_cur_tb("5140"); 723 reiserfs_panic(sb, "PAP-5140", 724 "schedule occurred in do_balance!"); 725 } 726 #endif 727 728 /* 729 * make sure, that the node contents look like a node of 730 * certain level 731 */ 732 if (!is_tree_node(bh, expected_level)) { 733 reiserfs_error(sb, "vs-5150", 734 "invalid format found in block %ld. " 735 "Fsck?", bh->b_blocknr); 736 pathrelse(search_path); 737 return IO_ERROR; 738 } 739 740 /* ok, we have acquired next formatted node in the tree */ 741 node_level = B_LEVEL(bh); 742 743 PROC_INFO_BH_STAT(sb, bh, node_level - 1); 744 745 RFALSE(node_level < stop_level, 746 "vs-5152: tree level (%d) is less than stop level (%d)", 747 node_level, stop_level); 748 749 retval = bin_search(key, item_head(bh, 0), 750 B_NR_ITEMS(bh), 751 (node_level == 752 DISK_LEAF_NODE_LEVEL) ? IH_SIZE : 753 KEY_SIZE, 754 &last_element->pe_position); 755 if (node_level == stop_level) { 756 return retval; 757 } 758 759 /* we are not in the stop level */ 760 /* 761 * item has been found, so we choose the pointer which 762 * is to the right of the found one 763 */ 764 if (retval == ITEM_FOUND) 765 last_element->pe_position++; 766 767 /* 768 * if item was not found we choose the position which is to 769 * the left of the found item. This requires no code, 770 * bin_search did it already. 771 */ 772 773 /* 774 * So we have chosen a position in the current node which is 775 * an internal node. Now we calculate child block number by 776 * position in the node. 777 */ 778 block_number = 779 B_N_CHILD_NUM(bh, last_element->pe_position); 780 781 /* 782 * if we are going to read leaf nodes, try for read 783 * ahead as well 784 */ 785 if ((search_path->reada & PATH_READA) && 786 node_level == DISK_LEAF_NODE_LEVEL + 1) { 787 int pos = last_element->pe_position; 788 int limit = B_NR_ITEMS(bh); 789 struct reiserfs_key *le_key; 790 791 if (search_path->reada & PATH_READA_BACK) 792 limit = 0; 793 while (reada_count < SEARCH_BY_KEY_READA) { 794 if (pos == limit) 795 break; 796 reada_blocks[reada_count++] = 797 B_N_CHILD_NUM(bh, pos); 798 if (search_path->reada & PATH_READA_BACK) 799 pos--; 800 else 801 pos++; 802 803 /* 804 * check to make sure we're in the same object 805 */ 806 le_key = internal_key(bh, pos); 807 if (le32_to_cpu(le_key->k_objectid) != 808 key->on_disk_key.k_objectid) { 809 break; 810 } 811 } 812 } 813 } 814 } 815 816 /* 817 * Form the path to an item and position in this item which contains 818 * file byte defined by key. If there is no such item 819 * corresponding to the key, we point the path to the item with 820 * maximal key less than key, and *pos_in_item is set to one 821 * past the last entry/byte in the item. If searching for entry in a 822 * directory item, and it is not found, *pos_in_item is set to one 823 * entry more than the entry with maximal key which is less than the 824 * sought key. 825 * 826 * Note that if there is no entry in this same node which is one more, 827 * then we point to an imaginary entry. for direct items, the 828 * position is in units of bytes, for indirect items the position is 829 * in units of blocknr entries, for directory items the position is in 830 * units of directory entries. 831 */ 832 /* The function is NOT SCHEDULE-SAFE! */ 833 int search_for_position_by_key(struct super_block *sb, 834 /* Key to search (cpu variable) */ 835 const struct cpu_key *p_cpu_key, 836 /* Filled up by this function. */ 837 struct treepath *search_path) 838 { 839 struct item_head *p_le_ih; /* pointer to on-disk structure */ 840 int blk_size; 841 loff_t item_offset, offset; 842 struct reiserfs_dir_entry de; 843 int retval; 844 845 /* If searching for directory entry. */ 846 if (is_direntry_cpu_key(p_cpu_key)) 847 return search_by_entry_key(sb, p_cpu_key, search_path, 848 &de); 849 850 /* If not searching for directory entry. */ 851 852 /* If item is found. */ 853 retval = search_item(sb, p_cpu_key, search_path); 854 if (retval == IO_ERROR) 855 return retval; 856 if (retval == ITEM_FOUND) { 857 858 RFALSE(!ih_item_len 859 (item_head 860 (PATH_PLAST_BUFFER(search_path), 861 PATH_LAST_POSITION(search_path))), 862 "PAP-5165: item length equals zero"); 863 864 pos_in_item(search_path) = 0; 865 return POSITION_FOUND; 866 } 867 868 RFALSE(!PATH_LAST_POSITION(search_path), 869 "PAP-5170: position equals zero"); 870 871 /* Item is not found. Set path to the previous item. */ 872 p_le_ih = 873 item_head(PATH_PLAST_BUFFER(search_path), 874 --PATH_LAST_POSITION(search_path)); 875 blk_size = sb->s_blocksize; 876 877 if (comp_short_keys(&p_le_ih->ih_key, p_cpu_key)) 878 return FILE_NOT_FOUND; 879 880 /* FIXME: quite ugly this far */ 881 882 item_offset = le_ih_k_offset(p_le_ih); 883 offset = cpu_key_k_offset(p_cpu_key); 884 885 /* Needed byte is contained in the item pointed to by the path. */ 886 if (item_offset <= offset && 887 item_offset + op_bytes_number(p_le_ih, blk_size) > offset) { 888 pos_in_item(search_path) = offset - item_offset; 889 if (is_indirect_le_ih(p_le_ih)) { 890 pos_in_item(search_path) /= blk_size; 891 } 892 return POSITION_FOUND; 893 } 894 895 /* 896 * Needed byte is not contained in the item pointed to by the 897 * path. Set pos_in_item out of the item. 898 */ 899 if (is_indirect_le_ih(p_le_ih)) 900 pos_in_item(search_path) = 901 ih_item_len(p_le_ih) / UNFM_P_SIZE; 902 else 903 pos_in_item(search_path) = ih_item_len(p_le_ih); 904 905 return POSITION_NOT_FOUND; 906 } 907 908 /* Compare given item and item pointed to by the path. */ 909 int comp_items(const struct item_head *stored_ih, const struct treepath *path) 910 { 911 struct buffer_head *bh = PATH_PLAST_BUFFER(path); 912 struct item_head *ih; 913 914 /* Last buffer at the path is not in the tree. */ 915 if (!B_IS_IN_TREE(bh)) 916 return 1; 917 918 /* Last path position is invalid. */ 919 if (PATH_LAST_POSITION(path) >= B_NR_ITEMS(bh)) 920 return 1; 921 922 /* we need only to know, whether it is the same item */ 923 ih = tp_item_head(path); 924 return memcmp(stored_ih, ih, IH_SIZE); 925 } 926 927 /* prepare for delete or cut of direct item */ 928 static inline int prepare_for_direct_item(struct treepath *path, 929 struct item_head *le_ih, 930 struct inode *inode, 931 loff_t new_file_length, int *cut_size) 932 { 933 loff_t round_len; 934 935 if (new_file_length == max_reiserfs_offset(inode)) { 936 /* item has to be deleted */ 937 *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 938 return M_DELETE; 939 } 940 /* new file gets truncated */ 941 if (get_inode_item_key_version(inode) == KEY_FORMAT_3_6) { 942 round_len = ROUND_UP(new_file_length); 943 /* this was new_file_length < le_ih ... */ 944 if (round_len < le_ih_k_offset(le_ih)) { 945 *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 946 return M_DELETE; /* Delete this item. */ 947 } 948 /* Calculate first position and size for cutting from item. */ 949 pos_in_item(path) = round_len - (le_ih_k_offset(le_ih) - 1); 950 *cut_size = -(ih_item_len(le_ih) - pos_in_item(path)); 951 952 return M_CUT; /* Cut from this item. */ 953 } 954 955 /* old file: items may have any length */ 956 957 if (new_file_length < le_ih_k_offset(le_ih)) { 958 *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 959 return M_DELETE; /* Delete this item. */ 960 } 961 962 /* Calculate first position and size for cutting from item. */ 963 *cut_size = -(ih_item_len(le_ih) - 964 (pos_in_item(path) = 965 new_file_length + 1 - le_ih_k_offset(le_ih))); 966 return M_CUT; /* Cut from this item. */ 967 } 968 969 static inline int prepare_for_direntry_item(struct treepath *path, 970 struct item_head *le_ih, 971 struct inode *inode, 972 loff_t new_file_length, 973 int *cut_size) 974 { 975 if (le_ih_k_offset(le_ih) == DOT_OFFSET && 976 new_file_length == max_reiserfs_offset(inode)) { 977 RFALSE(ih_entry_count(le_ih) != 2, 978 "PAP-5220: incorrect empty directory item (%h)", le_ih); 979 *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 980 /* Delete the directory item containing "." and ".." entry. */ 981 return M_DELETE; 982 } 983 984 if (ih_entry_count(le_ih) == 1) { 985 /* 986 * Delete the directory item such as there is one record only 987 * in this item 988 */ 989 *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 990 return M_DELETE; 991 } 992 993 /* Cut one record from the directory item. */ 994 *cut_size = 995 -(DEH_SIZE + 996 entry_length(get_last_bh(path), le_ih, pos_in_item(path))); 997 return M_CUT; 998 } 999 1000 #define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1) 1001 1002 /* 1003 * If the path points to a directory or direct item, calculate mode 1004 * and the size cut, for balance. 1005 * If the path points to an indirect item, remove some number of its 1006 * unformatted nodes. 1007 * In case of file truncate calculate whether this item must be 1008 * deleted/truncated or last unformatted node of this item will be 1009 * converted to a direct item. 1010 * This function returns a determination of what balance mode the 1011 * calling function should employ. 1012 */ 1013 static char prepare_for_delete_or_cut(struct reiserfs_transaction_handle *th, 1014 struct inode *inode, 1015 struct treepath *path, 1016 const struct cpu_key *item_key, 1017 /* 1018 * Number of unformatted nodes 1019 * which were removed from end 1020 * of the file. 1021 */ 1022 int *removed, 1023 int *cut_size, 1024 /* MAX_KEY_OFFSET in case of delete. */ 1025 unsigned long long new_file_length 1026 ) 1027 { 1028 struct super_block *sb = inode->i_sb; 1029 struct item_head *p_le_ih = tp_item_head(path); 1030 struct buffer_head *bh = PATH_PLAST_BUFFER(path); 1031 1032 BUG_ON(!th->t_trans_id); 1033 1034 /* Stat_data item. */ 1035 if (is_statdata_le_ih(p_le_ih)) { 1036 1037 RFALSE(new_file_length != max_reiserfs_offset(inode), 1038 "PAP-5210: mode must be M_DELETE"); 1039 1040 *cut_size = -(IH_SIZE + ih_item_len(p_le_ih)); 1041 return M_DELETE; 1042 } 1043 1044 /* Directory item. */ 1045 if (is_direntry_le_ih(p_le_ih)) 1046 return prepare_for_direntry_item(path, p_le_ih, inode, 1047 new_file_length, 1048 cut_size); 1049 1050 /* Direct item. */ 1051 if (is_direct_le_ih(p_le_ih)) 1052 return prepare_for_direct_item(path, p_le_ih, inode, 1053 new_file_length, cut_size); 1054 1055 /* Case of an indirect item. */ 1056 { 1057 int blk_size = sb->s_blocksize; 1058 struct item_head s_ih; 1059 int need_re_search; 1060 int delete = 0; 1061 int result = M_CUT; 1062 int pos = 0; 1063 1064 if ( new_file_length == max_reiserfs_offset (inode) ) { 1065 /* 1066 * prepare_for_delete_or_cut() is called by 1067 * reiserfs_delete_item() 1068 */ 1069 new_file_length = 0; 1070 delete = 1; 1071 } 1072 1073 do { 1074 need_re_search = 0; 1075 *cut_size = 0; 1076 bh = PATH_PLAST_BUFFER(path); 1077 copy_item_head(&s_ih, tp_item_head(path)); 1078 pos = I_UNFM_NUM(&s_ih); 1079 1080 while (le_ih_k_offset (&s_ih) + (pos - 1) * blk_size > new_file_length) { 1081 __le32 *unfm; 1082 __u32 block; 1083 1084 /* 1085 * Each unformatted block deletion may involve 1086 * one additional bitmap block into the transaction, 1087 * thereby the initial journal space reservation 1088 * might not be enough. 1089 */ 1090 if (!delete && (*cut_size) != 0 && 1091 reiserfs_transaction_free_space(th) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) 1092 break; 1093 1094 unfm = (__le32 *)ih_item_body(bh, &s_ih) + pos - 1; 1095 block = get_block_num(unfm, 0); 1096 1097 if (block != 0) { 1098 reiserfs_prepare_for_journal(sb, bh, 1); 1099 put_block_num(unfm, 0, 0); 1100 journal_mark_dirty(th, bh); 1101 reiserfs_free_block(th, inode, block, 1); 1102 } 1103 1104 reiserfs_cond_resched(sb); 1105 1106 if (item_moved (&s_ih, path)) { 1107 need_re_search = 1; 1108 break; 1109 } 1110 1111 pos --; 1112 (*removed)++; 1113 (*cut_size) -= UNFM_P_SIZE; 1114 1115 if (pos == 0) { 1116 (*cut_size) -= IH_SIZE; 1117 result = M_DELETE; 1118 break; 1119 } 1120 } 1121 /* 1122 * a trick. If the buffer has been logged, this will 1123 * do nothing. If we've broken the loop without logging 1124 * it, it will restore the buffer 1125 */ 1126 reiserfs_restore_prepared_buffer(sb, bh); 1127 } while (need_re_search && 1128 search_for_position_by_key(sb, item_key, path) == POSITION_FOUND); 1129 pos_in_item(path) = pos * UNFM_P_SIZE; 1130 1131 if (*cut_size == 0) { 1132 /* 1133 * Nothing was cut. maybe convert last unformatted node to the 1134 * direct item? 1135 */ 1136 result = M_CONVERT; 1137 } 1138 return result; 1139 } 1140 } 1141 1142 /* Calculate number of bytes which will be deleted or cut during balance */ 1143 static int calc_deleted_bytes_number(struct tree_balance *tb, char mode) 1144 { 1145 int del_size; 1146 struct item_head *p_le_ih = tp_item_head(tb->tb_path); 1147 1148 if (is_statdata_le_ih(p_le_ih)) 1149 return 0; 1150 1151 del_size = 1152 (mode == 1153 M_DELETE) ? ih_item_len(p_le_ih) : -tb->insert_size[0]; 1154 if (is_direntry_le_ih(p_le_ih)) { 1155 /* 1156 * return EMPTY_DIR_SIZE; We delete emty directories only. 1157 * we can't use EMPTY_DIR_SIZE, as old format dirs have a 1158 * different empty size. ick. FIXME, is this right? 1159 */ 1160 return del_size; 1161 } 1162 1163 if (is_indirect_le_ih(p_le_ih)) 1164 del_size = (del_size / UNFM_P_SIZE) * 1165 (PATH_PLAST_BUFFER(tb->tb_path)->b_size); 1166 return del_size; 1167 } 1168 1169 static void init_tb_struct(struct reiserfs_transaction_handle *th, 1170 struct tree_balance *tb, 1171 struct super_block *sb, 1172 struct treepath *path, int size) 1173 { 1174 1175 BUG_ON(!th->t_trans_id); 1176 1177 memset(tb, '\0', sizeof(struct tree_balance)); 1178 tb->transaction_handle = th; 1179 tb->tb_sb = sb; 1180 tb->tb_path = path; 1181 PATH_OFFSET_PBUFFER(path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL; 1182 PATH_OFFSET_POSITION(path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0; 1183 tb->insert_size[0] = size; 1184 } 1185 1186 void padd_item(char *item, int total_length, int length) 1187 { 1188 int i; 1189 1190 for (i = total_length; i > length;) 1191 item[--i] = 0; 1192 } 1193 1194 #ifdef REISERQUOTA_DEBUG 1195 char key2type(struct reiserfs_key *ih) 1196 { 1197 if (is_direntry_le_key(2, ih)) 1198 return 'd'; 1199 if (is_direct_le_key(2, ih)) 1200 return 'D'; 1201 if (is_indirect_le_key(2, ih)) 1202 return 'i'; 1203 if (is_statdata_le_key(2, ih)) 1204 return 's'; 1205 return 'u'; 1206 } 1207 1208 char head2type(struct item_head *ih) 1209 { 1210 if (is_direntry_le_ih(ih)) 1211 return 'd'; 1212 if (is_direct_le_ih(ih)) 1213 return 'D'; 1214 if (is_indirect_le_ih(ih)) 1215 return 'i'; 1216 if (is_statdata_le_ih(ih)) 1217 return 's'; 1218 return 'u'; 1219 } 1220 #endif 1221 1222 /* 1223 * Delete object item. 1224 * th - active transaction handle 1225 * path - path to the deleted item 1226 * item_key - key to search for the deleted item 1227 * indode - used for updating i_blocks and quotas 1228 * un_bh - NULL or unformatted node pointer 1229 */ 1230 int reiserfs_delete_item(struct reiserfs_transaction_handle *th, 1231 struct treepath *path, const struct cpu_key *item_key, 1232 struct inode *inode, struct buffer_head *un_bh) 1233 { 1234 struct super_block *sb = inode->i_sb; 1235 struct tree_balance s_del_balance; 1236 struct item_head s_ih; 1237 struct item_head *q_ih; 1238 int quota_cut_bytes; 1239 int ret_value, del_size, removed; 1240 int depth; 1241 1242 #ifdef CONFIG_REISERFS_CHECK 1243 char mode; 1244 int iter = 0; 1245 #endif 1246 1247 BUG_ON(!th->t_trans_id); 1248 1249 init_tb_struct(th, &s_del_balance, sb, path, 1250 0 /*size is unknown */ ); 1251 1252 while (1) { 1253 removed = 0; 1254 1255 #ifdef CONFIG_REISERFS_CHECK 1256 iter++; 1257 mode = 1258 #endif 1259 prepare_for_delete_or_cut(th, inode, path, 1260 item_key, &removed, 1261 &del_size, 1262 max_reiserfs_offset(inode)); 1263 1264 RFALSE(mode != M_DELETE, "PAP-5320: mode must be M_DELETE"); 1265 1266 copy_item_head(&s_ih, tp_item_head(path)); 1267 s_del_balance.insert_size[0] = del_size; 1268 1269 ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, NULL); 1270 if (ret_value != REPEAT_SEARCH) 1271 break; 1272 1273 PROC_INFO_INC(sb, delete_item_restarted); 1274 1275 /* file system changed, repeat search */ 1276 ret_value = 1277 search_for_position_by_key(sb, item_key, path); 1278 if (ret_value == IO_ERROR) 1279 break; 1280 if (ret_value == FILE_NOT_FOUND) { 1281 reiserfs_warning(sb, "vs-5340", 1282 "no items of the file %K found", 1283 item_key); 1284 break; 1285 } 1286 } /* while (1) */ 1287 1288 if (ret_value != CARRY_ON) { 1289 unfix_nodes(&s_del_balance); 1290 return 0; 1291 } 1292 1293 /* reiserfs_delete_item returns item length when success */ 1294 ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE); 1295 q_ih = tp_item_head(path); 1296 quota_cut_bytes = ih_item_len(q_ih); 1297 1298 /* 1299 * hack so the quota code doesn't have to guess if the file has a 1300 * tail. On tail insert, we allocate quota for 1 unformatted node. 1301 * We test the offset because the tail might have been 1302 * split into multiple items, and we only want to decrement for 1303 * the unfm node once 1304 */ 1305 if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(q_ih)) { 1306 if ((le_ih_k_offset(q_ih) & (sb->s_blocksize - 1)) == 1) { 1307 quota_cut_bytes = sb->s_blocksize + UNFM_P_SIZE; 1308 } else { 1309 quota_cut_bytes = 0; 1310 } 1311 } 1312 1313 if (un_bh) { 1314 int off; 1315 char *data; 1316 1317 /* 1318 * We are in direct2indirect conversion, so move tail contents 1319 * to the unformatted node 1320 */ 1321 /* 1322 * note, we do the copy before preparing the buffer because we 1323 * don't care about the contents of the unformatted node yet. 1324 * the only thing we really care about is the direct item's 1325 * data is in the unformatted node. 1326 * 1327 * Otherwise, we would have to call 1328 * reiserfs_prepare_for_journal on the unformatted node, 1329 * which might schedule, meaning we'd have to loop all the 1330 * way back up to the start of the while loop. 1331 * 1332 * The unformatted node must be dirtied later on. We can't be 1333 * sure here if the entire tail has been deleted yet. 1334 * 1335 * un_bh is from the page cache (all unformatted nodes are 1336 * from the page cache) and might be a highmem page. So, we 1337 * can't use un_bh->b_data. 1338 * -clm 1339 */ 1340 1341 data = kmap_atomic(un_bh->b_page); 1342 off = ((le_ih_k_offset(&s_ih) - 1) & (PAGE_SIZE - 1)); 1343 memcpy(data + off, 1344 ih_item_body(PATH_PLAST_BUFFER(path), &s_ih), 1345 ret_value); 1346 kunmap_atomic(data); 1347 } 1348 1349 /* Perform balancing after all resources have been collected at once. */ 1350 do_balance(&s_del_balance, NULL, NULL, M_DELETE); 1351 1352 #ifdef REISERQUOTA_DEBUG 1353 reiserfs_debug(sb, REISERFS_DEBUG_CODE, 1354 "reiserquota delete_item(): freeing %u, id=%u type=%c", 1355 quota_cut_bytes, inode->i_uid, head2type(&s_ih)); 1356 #endif 1357 depth = reiserfs_write_unlock_nested(inode->i_sb); 1358 dquot_free_space_nodirty(inode, quota_cut_bytes); 1359 reiserfs_write_lock_nested(inode->i_sb, depth); 1360 1361 /* Return deleted body length */ 1362 return ret_value; 1363 } 1364 1365 /* 1366 * Summary Of Mechanisms For Handling Collisions Between Processes: 1367 * 1368 * deletion of the body of the object is performed by iput(), with the 1369 * result that if multiple processes are operating on a file, the 1370 * deletion of the body of the file is deferred until the last process 1371 * that has an open inode performs its iput(). 1372 * 1373 * writes and truncates are protected from collisions by use of 1374 * semaphores. 1375 * 1376 * creates, linking, and mknod are protected from collisions with other 1377 * processes by making the reiserfs_add_entry() the last step in the 1378 * creation, and then rolling back all changes if there was a collision. 1379 * - Hans 1380 */ 1381 1382 /* this deletes item which never gets split */ 1383 void reiserfs_delete_solid_item(struct reiserfs_transaction_handle *th, 1384 struct inode *inode, struct reiserfs_key *key) 1385 { 1386 struct super_block *sb = th->t_super; 1387 struct tree_balance tb; 1388 INITIALIZE_PATH(path); 1389 int item_len = 0; 1390 int tb_init = 0; 1391 struct cpu_key cpu_key; 1392 int retval; 1393 int quota_cut_bytes = 0; 1394 1395 BUG_ON(!th->t_trans_id); 1396 1397 le_key2cpu_key(&cpu_key, key); 1398 1399 while (1) { 1400 retval = search_item(th->t_super, &cpu_key, &path); 1401 if (retval == IO_ERROR) { 1402 reiserfs_error(th->t_super, "vs-5350", 1403 "i/o failure occurred trying " 1404 "to delete %K", &cpu_key); 1405 break; 1406 } 1407 if (retval != ITEM_FOUND) { 1408 pathrelse(&path); 1409 /* 1410 * No need for a warning, if there is just no free 1411 * space to insert '..' item into the 1412 * newly-created subdir 1413 */ 1414 if (! 1415 ((unsigned long long) 1416 GET_HASH_VALUE(le_key_k_offset 1417 (le_key_version(key), key)) == 0 1418 && (unsigned long long) 1419 GET_GENERATION_NUMBER(le_key_k_offset 1420 (le_key_version(key), 1421 key)) == 1)) 1422 reiserfs_warning(th->t_super, "vs-5355", 1423 "%k not found", key); 1424 break; 1425 } 1426 if (!tb_init) { 1427 tb_init = 1; 1428 item_len = ih_item_len(tp_item_head(&path)); 1429 init_tb_struct(th, &tb, th->t_super, &path, 1430 -(IH_SIZE + item_len)); 1431 } 1432 quota_cut_bytes = ih_item_len(tp_item_head(&path)); 1433 1434 retval = fix_nodes(M_DELETE, &tb, NULL, NULL); 1435 if (retval == REPEAT_SEARCH) { 1436 PROC_INFO_INC(th->t_super, delete_solid_item_restarted); 1437 continue; 1438 } 1439 1440 if (retval == CARRY_ON) { 1441 do_balance(&tb, NULL, NULL, M_DELETE); 1442 /* 1443 * Should we count quota for item? (we don't 1444 * count quotas for save-links) 1445 */ 1446 if (inode) { 1447 int depth; 1448 #ifdef REISERQUOTA_DEBUG 1449 reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE, 1450 "reiserquota delete_solid_item(): freeing %u id=%u type=%c", 1451 quota_cut_bytes, inode->i_uid, 1452 key2type(key)); 1453 #endif 1454 depth = reiserfs_write_unlock_nested(sb); 1455 dquot_free_space_nodirty(inode, 1456 quota_cut_bytes); 1457 reiserfs_write_lock_nested(sb, depth); 1458 } 1459 break; 1460 } 1461 1462 /* IO_ERROR, NO_DISK_SPACE, etc */ 1463 reiserfs_warning(th->t_super, "vs-5360", 1464 "could not delete %K due to fix_nodes failure", 1465 &cpu_key); 1466 unfix_nodes(&tb); 1467 break; 1468 } 1469 1470 reiserfs_check_path(&path); 1471 } 1472 1473 int reiserfs_delete_object(struct reiserfs_transaction_handle *th, 1474 struct inode *inode) 1475 { 1476 int err; 1477 inode->i_size = 0; 1478 BUG_ON(!th->t_trans_id); 1479 1480 /* for directory this deletes item containing "." and ".." */ 1481 err = 1482 reiserfs_do_truncate(th, inode, NULL, 0 /*no timestamp updates */ ); 1483 if (err) 1484 return err; 1485 1486 #if defined( USE_INODE_GENERATION_COUNTER ) 1487 if (!old_format_only(th->t_super)) { 1488 __le32 *inode_generation; 1489 1490 inode_generation = 1491 &REISERFS_SB(th->t_super)->s_rs->s_inode_generation; 1492 le32_add_cpu(inode_generation, 1); 1493 } 1494 /* USE_INODE_GENERATION_COUNTER */ 1495 #endif 1496 reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode)); 1497 1498 return err; 1499 } 1500 1501 static void unmap_buffers(struct page *page, loff_t pos) 1502 { 1503 struct buffer_head *bh; 1504 struct buffer_head *head; 1505 struct buffer_head *next; 1506 unsigned long tail_index; 1507 unsigned long cur_index; 1508 1509 if (page) { 1510 if (page_has_buffers(page)) { 1511 tail_index = pos & (PAGE_SIZE - 1); 1512 cur_index = 0; 1513 head = page_buffers(page); 1514 bh = head; 1515 do { 1516 next = bh->b_this_page; 1517 1518 /* 1519 * we want to unmap the buffers that contain 1520 * the tail, and all the buffers after it 1521 * (since the tail must be at the end of the 1522 * file). We don't want to unmap file data 1523 * before the tail, since it might be dirty 1524 * and waiting to reach disk 1525 */ 1526 cur_index += bh->b_size; 1527 if (cur_index > tail_index) { 1528 reiserfs_unmap_buffer(bh); 1529 } 1530 bh = next; 1531 } while (bh != head); 1532 } 1533 } 1534 } 1535 1536 static int maybe_indirect_to_direct(struct reiserfs_transaction_handle *th, 1537 struct inode *inode, 1538 struct page *page, 1539 struct treepath *path, 1540 const struct cpu_key *item_key, 1541 loff_t new_file_size, char *mode) 1542 { 1543 struct super_block *sb = inode->i_sb; 1544 int block_size = sb->s_blocksize; 1545 int cut_bytes; 1546 BUG_ON(!th->t_trans_id); 1547 BUG_ON(new_file_size != inode->i_size); 1548 1549 /* 1550 * the page being sent in could be NULL if there was an i/o error 1551 * reading in the last block. The user will hit problems trying to 1552 * read the file, but for now we just skip the indirect2direct 1553 */ 1554 if (atomic_read(&inode->i_count) > 1 || 1555 !tail_has_to_be_packed(inode) || 1556 !page || (REISERFS_I(inode)->i_flags & i_nopack_mask)) { 1557 /* leave tail in an unformatted node */ 1558 *mode = M_SKIP_BALANCING; 1559 cut_bytes = 1560 block_size - (new_file_size & (block_size - 1)); 1561 pathrelse(path); 1562 return cut_bytes; 1563 } 1564 1565 /* Perform the conversion to a direct_item. */ 1566 return indirect2direct(th, inode, page, path, item_key, 1567 new_file_size, mode); 1568 } 1569 1570 /* 1571 * we did indirect_to_direct conversion. And we have inserted direct 1572 * item successesfully, but there were no disk space to cut unfm 1573 * pointer being converted. Therefore we have to delete inserted 1574 * direct item(s) 1575 */ 1576 static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle *th, 1577 struct inode *inode, struct treepath *path) 1578 { 1579 struct cpu_key tail_key; 1580 int tail_len; 1581 int removed; 1582 BUG_ON(!th->t_trans_id); 1583 1584 make_cpu_key(&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4); 1585 tail_key.key_length = 4; 1586 1587 tail_len = 1588 (cpu_key_k_offset(&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1; 1589 while (tail_len) { 1590 /* look for the last byte of the tail */ 1591 if (search_for_position_by_key(inode->i_sb, &tail_key, path) == 1592 POSITION_NOT_FOUND) 1593 reiserfs_panic(inode->i_sb, "vs-5615", 1594 "found invalid item"); 1595 RFALSE(path->pos_in_item != 1596 ih_item_len(tp_item_head(path)) - 1, 1597 "vs-5616: appended bytes found"); 1598 PATH_LAST_POSITION(path)--; 1599 1600 removed = 1601 reiserfs_delete_item(th, path, &tail_key, inode, 1602 NULL /*unbh not needed */ ); 1603 RFALSE(removed <= 0 1604 || removed > tail_len, 1605 "vs-5617: there was tail %d bytes, removed item length %d bytes", 1606 tail_len, removed); 1607 tail_len -= removed; 1608 set_cpu_key_k_offset(&tail_key, 1609 cpu_key_k_offset(&tail_key) - removed); 1610 } 1611 reiserfs_warning(inode->i_sb, "reiserfs-5091", "indirect_to_direct " 1612 "conversion has been rolled back due to " 1613 "lack of disk space"); 1614 mark_inode_dirty(inode); 1615 } 1616 1617 /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */ 1618 int reiserfs_cut_from_item(struct reiserfs_transaction_handle *th, 1619 struct treepath *path, 1620 struct cpu_key *item_key, 1621 struct inode *inode, 1622 struct page *page, loff_t new_file_size) 1623 { 1624 struct super_block *sb = inode->i_sb; 1625 /* 1626 * Every function which is going to call do_balance must first 1627 * create a tree_balance structure. Then it must fill up this 1628 * structure by using the init_tb_struct and fix_nodes functions. 1629 * After that we can make tree balancing. 1630 */ 1631 struct tree_balance s_cut_balance; 1632 struct item_head *p_le_ih; 1633 int cut_size = 0; /* Amount to be cut. */ 1634 int ret_value = CARRY_ON; 1635 int removed = 0; /* Number of the removed unformatted nodes. */ 1636 int is_inode_locked = 0; 1637 char mode; /* Mode of the balance. */ 1638 int retval2 = -1; 1639 int quota_cut_bytes; 1640 loff_t tail_pos = 0; 1641 int depth; 1642 1643 BUG_ON(!th->t_trans_id); 1644 1645 init_tb_struct(th, &s_cut_balance, inode->i_sb, path, 1646 cut_size); 1647 1648 /* 1649 * Repeat this loop until we either cut the item without needing 1650 * to balance, or we fix_nodes without schedule occurring 1651 */ 1652 while (1) { 1653 /* 1654 * Determine the balance mode, position of the first byte to 1655 * be cut, and size to be cut. In case of the indirect item 1656 * free unformatted nodes which are pointed to by the cut 1657 * pointers. 1658 */ 1659 1660 mode = 1661 prepare_for_delete_or_cut(th, inode, path, 1662 item_key, &removed, 1663 &cut_size, new_file_size); 1664 if (mode == M_CONVERT) { 1665 /* 1666 * convert last unformatted node to direct item or 1667 * leave tail in the unformatted node 1668 */ 1669 RFALSE(ret_value != CARRY_ON, 1670 "PAP-5570: can not convert twice"); 1671 1672 ret_value = 1673 maybe_indirect_to_direct(th, inode, page, 1674 path, item_key, 1675 new_file_size, &mode); 1676 if (mode == M_SKIP_BALANCING) 1677 /* tail has been left in the unformatted node */ 1678 return ret_value; 1679 1680 is_inode_locked = 1; 1681 1682 /* 1683 * removing of last unformatted node will 1684 * change value we have to return to truncate. 1685 * Save it 1686 */ 1687 retval2 = ret_value; 1688 1689 /* 1690 * So, we have performed the first part of the 1691 * conversion: 1692 * inserting the new direct item. Now we are 1693 * removing the last unformatted node pointer. 1694 * Set key to search for it. 1695 */ 1696 set_cpu_key_k_type(item_key, TYPE_INDIRECT); 1697 item_key->key_length = 4; 1698 new_file_size -= 1699 (new_file_size & (sb->s_blocksize - 1)); 1700 tail_pos = new_file_size; 1701 set_cpu_key_k_offset(item_key, new_file_size + 1); 1702 if (search_for_position_by_key 1703 (sb, item_key, 1704 path) == POSITION_NOT_FOUND) { 1705 print_block(PATH_PLAST_BUFFER(path), 3, 1706 PATH_LAST_POSITION(path) - 1, 1707 PATH_LAST_POSITION(path) + 1); 1708 reiserfs_panic(sb, "PAP-5580", "item to " 1709 "convert does not exist (%K)", 1710 item_key); 1711 } 1712 continue; 1713 } 1714 if (cut_size == 0) { 1715 pathrelse(path); 1716 return 0; 1717 } 1718 1719 s_cut_balance.insert_size[0] = cut_size; 1720 1721 ret_value = fix_nodes(mode, &s_cut_balance, NULL, NULL); 1722 if (ret_value != REPEAT_SEARCH) 1723 break; 1724 1725 PROC_INFO_INC(sb, cut_from_item_restarted); 1726 1727 ret_value = 1728 search_for_position_by_key(sb, item_key, path); 1729 if (ret_value == POSITION_FOUND) 1730 continue; 1731 1732 reiserfs_warning(sb, "PAP-5610", "item %K not found", 1733 item_key); 1734 unfix_nodes(&s_cut_balance); 1735 return (ret_value == IO_ERROR) ? -EIO : -ENOENT; 1736 } /* while */ 1737 1738 /* check fix_nodes results (IO_ERROR or NO_DISK_SPACE) */ 1739 if (ret_value != CARRY_ON) { 1740 if (is_inode_locked) { 1741 /* 1742 * FIXME: this seems to be not needed: we are always 1743 * able to cut item 1744 */ 1745 indirect_to_direct_roll_back(th, inode, path); 1746 } 1747 if (ret_value == NO_DISK_SPACE) 1748 reiserfs_warning(sb, "reiserfs-5092", 1749 "NO_DISK_SPACE"); 1750 unfix_nodes(&s_cut_balance); 1751 return -EIO; 1752 } 1753 1754 /* go ahead and perform balancing */ 1755 1756 RFALSE(mode == M_PASTE || mode == M_INSERT, "invalid mode"); 1757 1758 /* Calculate number of bytes that need to be cut from the item. */ 1759 quota_cut_bytes = 1760 (mode == 1761 M_DELETE) ? ih_item_len(tp_item_head(path)) : -s_cut_balance. 1762 insert_size[0]; 1763 if (retval2 == -1) 1764 ret_value = calc_deleted_bytes_number(&s_cut_balance, mode); 1765 else 1766 ret_value = retval2; 1767 1768 /* 1769 * For direct items, we only change the quota when deleting the last 1770 * item. 1771 */ 1772 p_le_ih = tp_item_head(s_cut_balance.tb_path); 1773 if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(p_le_ih)) { 1774 if (mode == M_DELETE && 1775 (le_ih_k_offset(p_le_ih) & (sb->s_blocksize - 1)) == 1776 1) { 1777 /* FIXME: this is to keep 3.5 happy */ 1778 REISERFS_I(inode)->i_first_direct_byte = U32_MAX; 1779 quota_cut_bytes = sb->s_blocksize + UNFM_P_SIZE; 1780 } else { 1781 quota_cut_bytes = 0; 1782 } 1783 } 1784 #ifdef CONFIG_REISERFS_CHECK 1785 if (is_inode_locked) { 1786 struct item_head *le_ih = 1787 tp_item_head(s_cut_balance.tb_path); 1788 /* 1789 * we are going to complete indirect2direct conversion. Make 1790 * sure, that we exactly remove last unformatted node pointer 1791 * of the item 1792 */ 1793 if (!is_indirect_le_ih(le_ih)) 1794 reiserfs_panic(sb, "vs-5652", 1795 "item must be indirect %h", le_ih); 1796 1797 if (mode == M_DELETE && ih_item_len(le_ih) != UNFM_P_SIZE) 1798 reiserfs_panic(sb, "vs-5653", "completing " 1799 "indirect2direct conversion indirect " 1800 "item %h being deleted must be of " 1801 "4 byte long", le_ih); 1802 1803 if (mode == M_CUT 1804 && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) { 1805 reiserfs_panic(sb, "vs-5654", "can not complete " 1806 "indirect2direct conversion of %h " 1807 "(CUT, insert_size==%d)", 1808 le_ih, s_cut_balance.insert_size[0]); 1809 } 1810 /* 1811 * it would be useful to make sure, that right neighboring 1812 * item is direct item of this file 1813 */ 1814 } 1815 #endif 1816 1817 do_balance(&s_cut_balance, NULL, NULL, mode); 1818 if (is_inode_locked) { 1819 /* 1820 * we've done an indirect->direct conversion. when the 1821 * data block was freed, it was removed from the list of 1822 * blocks that must be flushed before the transaction 1823 * commits, make sure to unmap and invalidate it 1824 */ 1825 unmap_buffers(page, tail_pos); 1826 REISERFS_I(inode)->i_flags &= ~i_pack_on_close_mask; 1827 } 1828 #ifdef REISERQUOTA_DEBUG 1829 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 1830 "reiserquota cut_from_item(): freeing %u id=%u type=%c", 1831 quota_cut_bytes, inode->i_uid, '?'); 1832 #endif 1833 depth = reiserfs_write_unlock_nested(sb); 1834 dquot_free_space_nodirty(inode, quota_cut_bytes); 1835 reiserfs_write_lock_nested(sb, depth); 1836 return ret_value; 1837 } 1838 1839 static void truncate_directory(struct reiserfs_transaction_handle *th, 1840 struct inode *inode) 1841 { 1842 BUG_ON(!th->t_trans_id); 1843 if (inode->i_nlink) 1844 reiserfs_error(inode->i_sb, "vs-5655", "link count != 0"); 1845 1846 set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), DOT_OFFSET); 1847 set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_DIRENTRY); 1848 reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode)); 1849 reiserfs_update_sd(th, inode); 1850 set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), SD_OFFSET); 1851 set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_STAT_DATA); 1852 } 1853 1854 /* 1855 * Truncate file to the new size. Note, this must be called with a 1856 * transaction already started 1857 */ 1858 int reiserfs_do_truncate(struct reiserfs_transaction_handle *th, 1859 struct inode *inode, /* ->i_size contains new size */ 1860 struct page *page, /* up to date for last block */ 1861 /* 1862 * when it is called by file_release to convert 1863 * the tail - no timestamps should be updated 1864 */ 1865 int update_timestamps 1866 ) 1867 { 1868 INITIALIZE_PATH(s_search_path); /* Path to the current object item. */ 1869 struct item_head *p_le_ih; /* Pointer to an item header. */ 1870 1871 /* Key to search for a previous file item. */ 1872 struct cpu_key s_item_key; 1873 loff_t file_size, /* Old file size. */ 1874 new_file_size; /* New file size. */ 1875 int deleted; /* Number of deleted or truncated bytes. */ 1876 int retval; 1877 int err = 0; 1878 1879 BUG_ON(!th->t_trans_id); 1880 if (! 1881 (S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) 1882 || S_ISLNK(inode->i_mode))) 1883 return 0; 1884 1885 /* deletion of directory - no need to update timestamps */ 1886 if (S_ISDIR(inode->i_mode)) { 1887 truncate_directory(th, inode); 1888 return 0; 1889 } 1890 1891 /* Get new file size. */ 1892 new_file_size = inode->i_size; 1893 1894 /* FIXME: note, that key type is unimportant here */ 1895 make_cpu_key(&s_item_key, inode, max_reiserfs_offset(inode), 1896 TYPE_DIRECT, 3); 1897 1898 retval = 1899 search_for_position_by_key(inode->i_sb, &s_item_key, 1900 &s_search_path); 1901 if (retval == IO_ERROR) { 1902 reiserfs_error(inode->i_sb, "vs-5657", 1903 "i/o failure occurred trying to truncate %K", 1904 &s_item_key); 1905 err = -EIO; 1906 goto out; 1907 } 1908 if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) { 1909 reiserfs_error(inode->i_sb, "PAP-5660", 1910 "wrong result %d of search for %K", retval, 1911 &s_item_key); 1912 1913 err = -EIO; 1914 goto out; 1915 } 1916 1917 s_search_path.pos_in_item--; 1918 1919 /* Get real file size (total length of all file items) */ 1920 p_le_ih = tp_item_head(&s_search_path); 1921 if (is_statdata_le_ih(p_le_ih)) 1922 file_size = 0; 1923 else { 1924 loff_t offset = le_ih_k_offset(p_le_ih); 1925 int bytes = 1926 op_bytes_number(p_le_ih, inode->i_sb->s_blocksize); 1927 1928 /* 1929 * this may mismatch with real file size: if last direct item 1930 * had no padding zeros and last unformatted node had no free 1931 * space, this file would have this file size 1932 */ 1933 file_size = offset + bytes - 1; 1934 } 1935 /* 1936 * are we doing a full truncate or delete, if so 1937 * kick in the reada code 1938 */ 1939 if (new_file_size == 0) 1940 s_search_path.reada = PATH_READA | PATH_READA_BACK; 1941 1942 if (file_size == 0 || file_size < new_file_size) { 1943 goto update_and_out; 1944 } 1945 1946 /* Update key to search for the last file item. */ 1947 set_cpu_key_k_offset(&s_item_key, file_size); 1948 1949 do { 1950 /* Cut or delete file item. */ 1951 deleted = 1952 reiserfs_cut_from_item(th, &s_search_path, &s_item_key, 1953 inode, page, new_file_size); 1954 if (deleted < 0) { 1955 reiserfs_warning(inode->i_sb, "vs-5665", 1956 "reiserfs_cut_from_item failed"); 1957 reiserfs_check_path(&s_search_path); 1958 return 0; 1959 } 1960 1961 RFALSE(deleted > file_size, 1962 "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K", 1963 deleted, file_size, &s_item_key); 1964 1965 /* Change key to search the last file item. */ 1966 file_size -= deleted; 1967 1968 set_cpu_key_k_offset(&s_item_key, file_size); 1969 1970 /* 1971 * While there are bytes to truncate and previous 1972 * file item is presented in the tree. 1973 */ 1974 1975 /* 1976 * This loop could take a really long time, and could log 1977 * many more blocks than a transaction can hold. So, we do 1978 * a polite journal end here, and if the transaction needs 1979 * ending, we make sure the file is consistent before ending 1980 * the current trans and starting a new one 1981 */ 1982 if (journal_transaction_should_end(th, 0) || 1983 reiserfs_transaction_free_space(th) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) { 1984 pathrelse(&s_search_path); 1985 1986 if (update_timestamps) { 1987 inode->i_mtime = current_time(inode); 1988 inode->i_ctime = current_time(inode); 1989 } 1990 reiserfs_update_sd(th, inode); 1991 1992 err = journal_end(th); 1993 if (err) 1994 goto out; 1995 err = journal_begin(th, inode->i_sb, 1996 JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD + JOURNAL_PER_BALANCE_CNT * 4) ; 1997 if (err) 1998 goto out; 1999 reiserfs_update_inode_transaction(inode); 2000 } 2001 } while (file_size > ROUND_UP(new_file_size) && 2002 search_for_position_by_key(inode->i_sb, &s_item_key, 2003 &s_search_path) == POSITION_FOUND); 2004 2005 RFALSE(file_size > ROUND_UP(new_file_size), 2006 "PAP-5680: truncate did not finish: new_file_size %lld, current %lld, oid %d", 2007 new_file_size, file_size, s_item_key.on_disk_key.k_objectid); 2008 2009 update_and_out: 2010 if (update_timestamps) { 2011 /* this is truncate, not file closing */ 2012 inode->i_mtime = current_time(inode); 2013 inode->i_ctime = current_time(inode); 2014 } 2015 reiserfs_update_sd(th, inode); 2016 2017 out: 2018 pathrelse(&s_search_path); 2019 return err; 2020 } 2021 2022 #ifdef CONFIG_REISERFS_CHECK 2023 /* this makes sure, that we __append__, not overwrite or add holes */ 2024 static void check_research_for_paste(struct treepath *path, 2025 const struct cpu_key *key) 2026 { 2027 struct item_head *found_ih = tp_item_head(path); 2028 2029 if (is_direct_le_ih(found_ih)) { 2030 if (le_ih_k_offset(found_ih) + 2031 op_bytes_number(found_ih, 2032 get_last_bh(path)->b_size) != 2033 cpu_key_k_offset(key) 2034 || op_bytes_number(found_ih, 2035 get_last_bh(path)->b_size) != 2036 pos_in_item(path)) 2037 reiserfs_panic(NULL, "PAP-5720", "found direct item " 2038 "%h or position (%d) does not match " 2039 "to key %K", found_ih, 2040 pos_in_item(path), key); 2041 } 2042 if (is_indirect_le_ih(found_ih)) { 2043 if (le_ih_k_offset(found_ih) + 2044 op_bytes_number(found_ih, 2045 get_last_bh(path)->b_size) != 2046 cpu_key_k_offset(key) 2047 || I_UNFM_NUM(found_ih) != pos_in_item(path) 2048 || get_ih_free_space(found_ih) != 0) 2049 reiserfs_panic(NULL, "PAP-5730", "found indirect " 2050 "item (%h) or position (%d) does not " 2051 "match to key (%K)", 2052 found_ih, pos_in_item(path), key); 2053 } 2054 } 2055 #endif /* config reiserfs check */ 2056 2057 /* 2058 * Paste bytes to the existing item. 2059 * Returns bytes number pasted into the item. 2060 */ 2061 int reiserfs_paste_into_item(struct reiserfs_transaction_handle *th, 2062 /* Path to the pasted item. */ 2063 struct treepath *search_path, 2064 /* Key to search for the needed item. */ 2065 const struct cpu_key *key, 2066 /* Inode item belongs to */ 2067 struct inode *inode, 2068 /* Pointer to the bytes to paste. */ 2069 const char *body, 2070 /* Size of pasted bytes. */ 2071 int pasted_size) 2072 { 2073 struct super_block *sb = inode->i_sb; 2074 struct tree_balance s_paste_balance; 2075 int retval; 2076 int fs_gen; 2077 int depth; 2078 2079 BUG_ON(!th->t_trans_id); 2080 2081 fs_gen = get_generation(inode->i_sb); 2082 2083 #ifdef REISERQUOTA_DEBUG 2084 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 2085 "reiserquota paste_into_item(): allocating %u id=%u type=%c", 2086 pasted_size, inode->i_uid, 2087 key2type(&key->on_disk_key)); 2088 #endif 2089 2090 depth = reiserfs_write_unlock_nested(sb); 2091 retval = dquot_alloc_space_nodirty(inode, pasted_size); 2092 reiserfs_write_lock_nested(sb, depth); 2093 if (retval) { 2094 pathrelse(search_path); 2095 return retval; 2096 } 2097 init_tb_struct(th, &s_paste_balance, th->t_super, search_path, 2098 pasted_size); 2099 #ifdef DISPLACE_NEW_PACKING_LOCALITIES 2100 s_paste_balance.key = key->on_disk_key; 2101 #endif 2102 2103 /* DQUOT_* can schedule, must check before the fix_nodes */ 2104 if (fs_changed(fs_gen, inode->i_sb)) { 2105 goto search_again; 2106 } 2107 2108 while ((retval = 2109 fix_nodes(M_PASTE, &s_paste_balance, NULL, 2110 body)) == REPEAT_SEARCH) { 2111 search_again: 2112 /* file system changed while we were in the fix_nodes */ 2113 PROC_INFO_INC(th->t_super, paste_into_item_restarted); 2114 retval = 2115 search_for_position_by_key(th->t_super, key, 2116 search_path); 2117 if (retval == IO_ERROR) { 2118 retval = -EIO; 2119 goto error_out; 2120 } 2121 if (retval == POSITION_FOUND) { 2122 reiserfs_warning(inode->i_sb, "PAP-5710", 2123 "entry or pasted byte (%K) exists", 2124 key); 2125 retval = -EEXIST; 2126 goto error_out; 2127 } 2128 #ifdef CONFIG_REISERFS_CHECK 2129 check_research_for_paste(search_path, key); 2130 #endif 2131 } 2132 2133 /* 2134 * Perform balancing after all resources are collected by fix_nodes, 2135 * and accessing them will not risk triggering schedule. 2136 */ 2137 if (retval == CARRY_ON) { 2138 do_balance(&s_paste_balance, NULL /*ih */ , body, M_PASTE); 2139 return 0; 2140 } 2141 retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO; 2142 error_out: 2143 /* this also releases the path */ 2144 unfix_nodes(&s_paste_balance); 2145 #ifdef REISERQUOTA_DEBUG 2146 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 2147 "reiserquota paste_into_item(): freeing %u id=%u type=%c", 2148 pasted_size, inode->i_uid, 2149 key2type(&key->on_disk_key)); 2150 #endif 2151 depth = reiserfs_write_unlock_nested(sb); 2152 dquot_free_space_nodirty(inode, pasted_size); 2153 reiserfs_write_lock_nested(sb, depth); 2154 return retval; 2155 } 2156 2157 /* 2158 * Insert new item into the buffer at the path. 2159 * th - active transaction handle 2160 * path - path to the inserted item 2161 * ih - pointer to the item header to insert 2162 * body - pointer to the bytes to insert 2163 */ 2164 int reiserfs_insert_item(struct reiserfs_transaction_handle *th, 2165 struct treepath *path, const struct cpu_key *key, 2166 struct item_head *ih, struct inode *inode, 2167 const char *body) 2168 { 2169 struct tree_balance s_ins_balance; 2170 int retval; 2171 int fs_gen = 0; 2172 int quota_bytes = 0; 2173 2174 BUG_ON(!th->t_trans_id); 2175 2176 if (inode) { /* Do we count quotas for item? */ 2177 int depth; 2178 fs_gen = get_generation(inode->i_sb); 2179 quota_bytes = ih_item_len(ih); 2180 2181 /* 2182 * hack so the quota code doesn't have to guess 2183 * if the file has a tail, links are always tails, 2184 * so there's no guessing needed 2185 */ 2186 if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(ih)) 2187 quota_bytes = inode->i_sb->s_blocksize + UNFM_P_SIZE; 2188 #ifdef REISERQUOTA_DEBUG 2189 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 2190 "reiserquota insert_item(): allocating %u id=%u type=%c", 2191 quota_bytes, inode->i_uid, head2type(ih)); 2192 #endif 2193 /* 2194 * We can't dirty inode here. It would be immediately 2195 * written but appropriate stat item isn't inserted yet... 2196 */ 2197 depth = reiserfs_write_unlock_nested(inode->i_sb); 2198 retval = dquot_alloc_space_nodirty(inode, quota_bytes); 2199 reiserfs_write_lock_nested(inode->i_sb, depth); 2200 if (retval) { 2201 pathrelse(path); 2202 return retval; 2203 } 2204 } 2205 init_tb_struct(th, &s_ins_balance, th->t_super, path, 2206 IH_SIZE + ih_item_len(ih)); 2207 #ifdef DISPLACE_NEW_PACKING_LOCALITIES 2208 s_ins_balance.key = key->on_disk_key; 2209 #endif 2210 /* 2211 * DQUOT_* can schedule, must check to be sure calling 2212 * fix_nodes is safe 2213 */ 2214 if (inode && fs_changed(fs_gen, inode->i_sb)) { 2215 goto search_again; 2216 } 2217 2218 while ((retval = 2219 fix_nodes(M_INSERT, &s_ins_balance, ih, 2220 body)) == REPEAT_SEARCH) { 2221 search_again: 2222 /* file system changed while we were in the fix_nodes */ 2223 PROC_INFO_INC(th->t_super, insert_item_restarted); 2224 retval = search_item(th->t_super, key, path); 2225 if (retval == IO_ERROR) { 2226 retval = -EIO; 2227 goto error_out; 2228 } 2229 if (retval == ITEM_FOUND) { 2230 reiserfs_warning(th->t_super, "PAP-5760", 2231 "key %K already exists in the tree", 2232 key); 2233 retval = -EEXIST; 2234 goto error_out; 2235 } 2236 } 2237 2238 /* make balancing after all resources will be collected at a time */ 2239 if (retval == CARRY_ON) { 2240 do_balance(&s_ins_balance, ih, body, M_INSERT); 2241 return 0; 2242 } 2243 2244 retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO; 2245 error_out: 2246 /* also releases the path */ 2247 unfix_nodes(&s_ins_balance); 2248 #ifdef REISERQUOTA_DEBUG 2249 if (inode) 2250 reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE, 2251 "reiserquota insert_item(): freeing %u id=%u type=%c", 2252 quota_bytes, inode->i_uid, head2type(ih)); 2253 #endif 2254 if (inode) { 2255 int depth = reiserfs_write_unlock_nested(inode->i_sb); 2256 dquot_free_space_nodirty(inode, quota_bytes); 2257 reiserfs_write_lock_nested(inode->i_sb, depth); 2258 } 2259 return retval; 2260 } 2261