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