~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/reiserfs/stree.c

Version: ~ [ linux-5.8-rc5 ] ~ [ linux-5.7.8 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.51 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.132 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.188 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.230 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.230 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp