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