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