fs/reiserfs/stree.c

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