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