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