2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
6 * Written by Anatoly P. Pinchuk pap@namesys.botik.ru
7 * Programm System Institute
8 * Pereslavl-Zalessky Russia
11 #include <linux/time.h>
12 #include <linux/string.h>
13 #include <linux/pagemap.h>
14 #include <linux/bio.h>
16 #include <linux/buffer_head.h>
17 #include <linux/quotaops.h>
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
)
23 RFALSE(B_LEVEL(bh
) > MAX_HEIGHT
,
24 "PAP-1010: block (%b) has too big level (%z)", bh
, bh
);
26 return (B_LEVEL(bh
) != FREE_LEVEL
);
29 /* to get item head in le form */
30 inline void copy_item_head(struct item_head
*to
,
31 const struct item_head
*from
)
33 memcpy(to
, from
, IH_SIZE
);
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
44 inline int comp_short_keys(const struct reiserfs_key
*le_key
,
45 const struct cpu_key
*cpu_key
)
48 n
= le32_to_cpu(le_key
->k_dir_id
);
49 if (n
< cpu_key
->on_disk_key
.k_dir_id
)
51 if (n
> cpu_key
->on_disk_key
.k_dir_id
)
53 n
= le32_to_cpu(le_key
->k_objectid
);
54 if (n
< cpu_key
->on_disk_key
.k_objectid
)
56 if (n
> cpu_key
->on_disk_key
.k_objectid
)
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
68 static inline int comp_keys(const struct reiserfs_key
*le_key
,
69 const struct cpu_key
*cpu_key
)
73 retval
= comp_short_keys(le_key
, cpu_key
);
76 if (le_key_k_offset(le_key_version(le_key
), le_key
) <
77 cpu_key_k_offset(cpu_key
))
79 if (le_key_k_offset(le_key_version(le_key
), le_key
) >
80 cpu_key_k_offset(cpu_key
))
83 if (cpu_key
->key_length
== 3)
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
))
91 if (le_key_k_type(le_key_version(le_key
), le_key
) >
92 cpu_key_k_type(cpu_key
))
98 inline int comp_short_le_keys(const struct reiserfs_key
*key1
,
99 const struct reiserfs_key
*key2
)
101 __u32
*k1_u32
, *k2_u32
;
102 int key_length
= REISERFS_SHORT_KEY_LEN
;
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
))
109 if (le32_to_cpu(*k1_u32
) > le32_to_cpu(*k2_u32
))
115 inline void le_key2cpu_key(struct cpu_key
*to
, const struct reiserfs_key
*from
)
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
);
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
);
129 * this does not say which one is bigger, it only returns 1 if keys
130 * are not equal, 0 otherwise
132 inline int comp_le_keys(const struct reiserfs_key
*k1
,
133 const struct reiserfs_key
*k2
)
135 return memcmp(k1
, k2
, sizeof(struct reiserfs_key
));
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 **************************************************************************/
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.
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. */
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
166 int *pos
/* Number of the searched for element. */
169 int rbound
, lbound
, j
;
171 for (j
= ((rbound
= num
- 1) + (lbound
= 0)) / 2;
172 lbound
<= rbound
; j
= (rbound
+ lbound
) / 2)
174 ((struct reiserfs_key
*)((char *)base
+ j
* width
),
175 (struct cpu_key
*)key
)) {
184 return ITEM_FOUND
; /* Key found in the array. */
188 * bin_search did not find given key, it returns position of key,
189 * that is minimal and greater than the given one.
192 return ITEM_NOT_FOUND
;
196 /* Minimal possible key. It is never in the tree. */
197 const struct reiserfs_key MIN_KEY
= { 0, 0, {{0, 0},} };
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)},}
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
215 static inline const struct reiserfs_key
*get_lkey(const struct treepath
*chk_path
,
216 const struct super_block
*sb
)
218 int position
, path_offset
= chk_path
->path_length
;
219 struct buffer_head
*parent
;
221 RFALSE(path_offset
< FIRST_PATH_ELEMENT_OFFSET
,
222 "PAP-5010: invalid offset in the path");
224 /* While not higher in path than first element. */
225 while (path_offset
-- > FIRST_PATH_ELEMENT_OFFSET
) {
227 RFALSE(!buffer_uptodate
228 (PATH_OFFSET_PBUFFER(chk_path
, path_offset
)),
229 "PAP-5020: parent is not uptodate");
231 /* Parent at the path is not in the tree now. */
234 PATH_OFFSET_PBUFFER(chk_path
, path_offset
)))
236 /* Check whether position in the parent is correct. */
238 PATH_OFFSET_POSITION(chk_path
,
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
)
248 * Return delimiting key if position in the parent
249 * is not equal to zero.
252 return internal_key(parent
, position
- 1);
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
))
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
)
265 int position
, path_offset
= chk_path
->path_length
;
266 struct buffer_head
*parent
;
268 RFALSE(path_offset
< FIRST_PATH_ELEMENT_OFFSET
,
269 "PAP-5030: invalid offset in the path");
271 while (path_offset
-- > FIRST_PATH_ELEMENT_OFFSET
) {
273 RFALSE(!buffer_uptodate
274 (PATH_OFFSET_PBUFFER(chk_path
, path_offset
)),
275 "PAP-5040: parent is not uptodate");
277 /* Parent at the path is not in the tree now. */
280 PATH_OFFSET_PBUFFER(chk_path
, path_offset
)))
282 /* Check whether position in the parent is correct. */
284 PATH_OFFSET_POSITION(chk_path
,
289 * Check whether parent at the path really points
292 if (B_N_CHILD_NUM(parent
, position
) !=
293 PATH_OFFSET_PBUFFER(chk_path
,
294 path_offset
+ 1)->b_blocknr
)
298 * Return delimiting key if position in the parent
299 * is not the last one.
301 if (position
!= B_NR_ITEMS(parent
))
302 return internal_key(parent
, position
);
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
))
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.
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
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");
337 if (comp_keys(get_lkey(chk_path
, sb
), key
) == 1)
338 /* left delimiting key is bigger, that the key we look for */
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 */
347 int reiserfs_check_path(struct treepath
*p
)
349 RFALSE(p
->path_length
!= ILLEGAL_PATH_ELEMENT_OFFSET
,
350 "path not properly relsed");
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()
359 void pathrelse_and_restore(struct super_block
*sb
,
360 struct treepath
*search_path
)
362 int path_offset
= search_path
->path_length
;
364 RFALSE(path_offset
< ILLEGAL_PATH_ELEMENT_OFFSET
,
365 "clm-4000: invalid path offset");
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
);
373 search_path
->path_length
= ILLEGAL_PATH_ELEMENT_OFFSET
;
376 /* Drop the reference to each buffer in a path */
377 void pathrelse(struct treepath
*search_path
)
379 int path_offset
= search_path
->path_length
;
381 RFALSE(path_offset
< ILLEGAL_PATH_ELEMENT_OFFSET
,
382 "PAP-5090: invalid path offset");
384 while (path_offset
> ILLEGAL_PATH_ELEMENT_OFFSET
)
385 brelse(PATH_OFFSET_PBUFFER(search_path
, path_offset
--));
387 search_path
->path_length
= ILLEGAL_PATH_ELEMENT_OFFSET
;
390 static int has_valid_deh_location(struct buffer_head
*bh
, struct item_head
*ih
)
392 struct reiserfs_de_head
*deh
;
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",
408 static int is_leaf(char *buf
, int blocksize
, struct buffer_head
*bh
)
410 struct block_head
*blkh
;
411 struct item_head
*ih
;
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");
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
);
431 ih
= (struct item_head
*)(buf
+ BLKH_SIZE
) + nr
- 1;
432 used_space
= BLKH_SIZE
+ IH_SIZE
* nr
+ (blocksize
- ih_location(ih
));
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
);
441 * FIXME: it is_leaf will hit performance too much - we may have
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",
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",
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",
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
);
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",
482 return has_valid_deh_location(bh
, ih
);
484 prev_location
= ih_location(ih
);
487 /* one may imagine many more checks */
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
)
494 struct block_head
*blkh
;
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");
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
);
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
);
522 /* one may imagine many more checks */
527 * make sure that bh contains formatted node of reiserfs tree of
530 static int is_tree_node(struct buffer_head
*bh
, int level
)
532 if (B_LEVEL(bh
) != level
) {
533 reiserfs_warning(NULL
, "reiserfs-5090", "node level %d does "
534 "not match to the expected one %d",
538 if (level
== DISK_LEAF_NODE_LEVEL
)
539 return is_leaf(bh
->b_data
, bh
->b_size
, bh
);
541 return is_internal(bh
->b_data
, bh
->b_size
, bh
);
544 #define SEARCH_BY_KEY_READA 16
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.
554 * @return depth of lock to be restored after read completes
556 static int search_by_key_reada(struct super_block
*s
,
557 struct buffer_head
**bh
,
558 b_blocknr_t
*b
, int num
)
563 for (i
= 0; i
< num
; i
++) {
564 bh
[i
] = sb_getblk(s
, b
[i
]);
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
573 for (j
= 0; j
< i
; j
++) {
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
579 if (!buffer_uptodate(bh
[j
])) {
581 depth
= reiserfs_write_unlock_nested(s
);
582 ll_rw_block(REQ_OP_READ
, REQ_RAHEAD
, 1, bh
+ j
);
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
605 * search_by_key - search for key (and item) in stree
607 * @key: pointer to key to search for
608 * @search_path: Allocated and initialized struct treepath; Returned filled
610 * @stop_level: How far down the tree to search, Use DISK_LEAF_NODE_LEVEL to
611 * stop at leaf level.
613 * The function is NOT SCHEDULE-SAFE!
615 int search_by_key(struct super_block
*sb
, const struct cpu_key
*key
,
616 struct treepath
*search_path
, int stop_level
)
618 b_blocknr_t block_number
;
620 struct buffer_head
*bh
;
621 struct path_element
*last_element
;
622 int node_level
, retval
;
624 struct buffer_head
*reada_bh
[SEARCH_BY_KEY_READA
];
625 b_blocknr_t reada_blocks
[SEARCH_BY_KEY_READA
];
628 #ifdef CONFIG_REISERFS_CHECK
629 int repeat_counter
= 0;
632 PROC_INFO_INC(sb
, search_by_key
);
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
641 pathrelse(search_path
);
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..
648 block_number
= SB_ROOT_BLOCK(sb
);
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
,
661 /* prep path to have another element added to it. */
663 PATH_OFFSET_PELEMENT(search_path
,
664 ++search_path
->path_length
);
665 fs_gen
= get_generation(sb
);
668 * Read the next tree node, and set the last element
669 * in the path to have a pointer to it.
671 if ((bh
= last_element
->pe_buffer
=
672 sb_getblk(sb
, block_number
))) {
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.
681 if (!buffer_uptodate(bh
) && reada_count
> 1)
682 depth
= search_by_key_reada(sb
, reada_bh
,
683 reada_blocks
, reada_count
);
685 if (!buffer_uptodate(bh
) && depth
== -1)
686 depth
= reiserfs_write_unlock_nested(sb
);
688 ll_rw_block(REQ_OP_READ
, 0, 1, &bh
);
692 reiserfs_write_lock_nested(sb
, depth
);
693 if (!buffer_uptodate(bh
))
697 search_path
->path_length
--;
698 pathrelse(search_path
);
702 if (expected_level
== -1)
703 expected_level
= SB_TREE_HEIGHT(sb
);
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
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
);
719 sbk_restarted
[expected_level
- 1]);
720 pathrelse(search_path
);
723 * Get the root block number so that we can
724 * repeat the search starting from the root.
726 block_number
= SB_ROOT_BLOCK(sb
);
729 /* repeat search from the root */
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.
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!");
750 * make sure, that the node contents look like a node of
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
);
761 /* ok, we have acquired next formatted node in the tree */
762 node_level
= B_LEVEL(bh
);
764 PROC_INFO_BH_STAT(sb
, bh
, node_level
- 1);
766 RFALSE(node_level
< stop_level
,
767 "vs-5152: tree level (%d) is less than stop level (%d)",
768 node_level
, stop_level
);
770 retval
= bin_search(key
, item_head(bh
, 0),
773 DISK_LEAF_NODE_LEVEL
) ? IH_SIZE
:
775 &last_element
->pe_position
);
776 if (node_level
== stop_level
) {
780 /* we are not in the stop level */
782 * item has been found, so we choose the pointer which
783 * is to the right of the found one
785 if (retval
== ITEM_FOUND
)
786 last_element
->pe_position
++;
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.
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.
800 B_N_CHILD_NUM(bh
, last_element
->pe_position
);
803 * if we are going to read leaf nodes, try for read
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
;
812 if (search_path
->reada
& PATH_READA_BACK
)
814 while (reada_count
< SEARCH_BY_KEY_READA
) {
817 reada_blocks
[reada_count
++] =
818 B_N_CHILD_NUM(bh
, pos
);
819 if (search_path
->reada
& PATH_READA_BACK
)
825 * check to make sure we're in the same object
827 le_key
= internal_key(bh
, pos
);
828 if (le32_to_cpu(le_key
->k_objectid
) !=
829 key
->on_disk_key
.k_objectid
) {
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
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.
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
)
860 struct item_head
*p_le_ih
; /* pointer to on-disk structure */
862 loff_t item_offset
, offset
;
863 struct reiserfs_dir_entry de
;
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
,
871 /* If not searching for directory entry. */
873 /* If item is found. */
874 retval
= search_item(sb
, p_cpu_key
, search_path
);
875 if (retval
== IO_ERROR
)
877 if (retval
== ITEM_FOUND
) {
881 (PATH_PLAST_BUFFER(search_path
),
882 PATH_LAST_POSITION(search_path
))),
883 "PAP-5165: item length equals zero");
885 pos_in_item(search_path
) = 0;
886 return POSITION_FOUND
;
889 RFALSE(!PATH_LAST_POSITION(search_path
),
890 "PAP-5170: position equals zero");
892 /* Item is not found. Set path to the previous item. */
894 item_head(PATH_PLAST_BUFFER(search_path
),
895 --PATH_LAST_POSITION(search_path
));
896 blk_size
= sb
->s_blocksize
;
898 if (comp_short_keys(&p_le_ih
->ih_key
, p_cpu_key
))
899 return FILE_NOT_FOUND
;
901 /* FIXME: quite ugly this far */
903 item_offset
= le_ih_k_offset(p_le_ih
);
904 offset
= cpu_key_k_offset(p_cpu_key
);
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
;
913 return POSITION_FOUND
;
917 * Needed byte is not contained in the item pointed to by the
918 * path. Set pos_in_item out of the item.
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
;
924 pos_in_item(search_path
) = ih_item_len(p_le_ih
);
926 return POSITION_NOT_FOUND
;
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
)
932 struct buffer_head
*bh
= PATH_PLAST_BUFFER(path
);
933 struct item_head
*ih
;
935 /* Last buffer at the path is not in the tree. */
936 if (!B_IS_IN_TREE(bh
))
939 /* Last path position is invalid. */
940 if (PATH_LAST_POSITION(path
) >= B_NR_ITEMS(bh
))
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
);
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
,
952 loff_t new_file_length
, int *cut_size
)
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
));
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. */
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
));
973 return M_CUT
; /* Cut from this item. */
976 /* old file: items may have any length */
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. */
983 /* Calculate first position and size for cutting from item. */
984 *cut_size
= -(ih_item_len(le_ih
) -
986 new_file_length
+ 1 - le_ih_k_offset(le_ih
)));
987 return M_CUT
; /* Cut from this item. */
990 static inline int prepare_for_direntry_item(struct treepath
*path
,
991 struct item_head
*le_ih
,
993 loff_t new_file_length
,
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. */
1005 if (ih_entry_count(le_ih
) == 1) {
1007 * Delete the directory item such as there is one record only
1010 *cut_size
= -(IH_SIZE
+ ih_item_len(le_ih
));
1014 /* Cut one record from the directory item. */
1017 entry_length(get_last_bh(path
), le_ih
, pos_in_item(path
)));
1021 #define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1)
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.
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
,
1039 * Number of unformatted nodes
1040 * which were removed from end
1045 /* MAX_KEY_OFFSET in case of delete. */
1046 unsigned long long new_file_length
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
);
1053 BUG_ON(!th
->t_trans_id
);
1055 /* Stat_data item. */
1056 if (is_statdata_le_ih(p_le_ih
)) {
1058 RFALSE(new_file_length
!= max_reiserfs_offset(inode
),
1059 "PAP-5210: mode must be M_DELETE");
1061 *cut_size
= -(IH_SIZE
+ ih_item_len(p_le_ih
));
1065 /* Directory item. */
1066 if (is_direntry_le_ih(p_le_ih
))
1067 return prepare_for_direntry_item(path
, p_le_ih
, inode
,
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
);
1076 /* Case of an indirect item. */
1078 int blk_size
= sb
->s_blocksize
;
1079 struct item_head s_ih
;
1085 if ( new_file_length
== max_reiserfs_offset (inode
) ) {
1087 * prepare_for_delete_or_cut() is called by
1088 * reiserfs_delete_item()
1090 new_file_length
= 0;
1097 bh
= PATH_PLAST_BUFFER(path
);
1098 copy_item_head(&s_ih
, tp_item_head(path
));
1099 pos
= I_UNFM_NUM(&s_ih
);
1101 while (le_ih_k_offset (&s_ih
) + (pos
- 1) * blk_size
> new_file_length
) {
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.
1111 if (!delete && (*cut_size
) != 0 &&
1112 reiserfs_transaction_free_space(th
) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD
)
1115 unfm
= (__le32
*)ih_item_body(bh
, &s_ih
) + pos
- 1;
1116 block
= get_block_num(unfm
, 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);
1125 reiserfs_cond_resched(sb
);
1127 if (item_moved (&s_ih
, path
)) {
1134 (*cut_size
) -= UNFM_P_SIZE
;
1137 (*cut_size
) -= IH_SIZE
;
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
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
;
1152 if (*cut_size
== 0) {
1154 * Nothing was cut. maybe convert last unformatted node to the
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
)
1167 struct item_head
*p_le_ih
= tp_item_head(tb
->tb_path
);
1169 if (is_statdata_le_ih(p_le_ih
))
1174 M_DELETE
) ? ih_item_len(p_le_ih
) : -tb
->insert_size
[0];
1175 if (is_direntry_le_ih(p_le_ih
)) {
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?
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
);
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
)
1196 BUG_ON(!th
->t_trans_id
);
1198 memset(tb
, '\0', sizeof(struct tree_balance
));
1199 tb
->transaction_handle
= th
;
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
;
1207 void padd_item(char *item
, int total_length
, int length
)
1211 for (i
= total_length
; i
> length
;)
1215 #ifdef REISERQUOTA_DEBUG
1216 char key2type(struct reiserfs_key
*ih
)
1218 if (is_direntry_le_key(2, ih
))
1220 if (is_direct_le_key(2, ih
))
1222 if (is_indirect_le_key(2, ih
))
1224 if (is_statdata_le_key(2, ih
))
1229 char head2type(struct item_head
*ih
)
1231 if (is_direntry_le_ih(ih
))
1233 if (is_direct_le_ih(ih
))
1235 if (is_indirect_le_ih(ih
))
1237 if (is_statdata_le_ih(ih
))
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
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
)
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
;
1263 #ifdef CONFIG_REISERFS_CHECK
1268 BUG_ON(!th
->t_trans_id
);
1270 init_tb_struct(th
, &s_del_balance
, sb
, path
,
1271 0 /*size is unknown */ );
1276 #ifdef CONFIG_REISERFS_CHECK
1280 prepare_for_delete_or_cut(th
, inode
, path
,
1283 max_reiserfs_offset(inode
));
1285 RFALSE(mode
!= M_DELETE
, "PAP-5320: mode must be M_DELETE");
1287 copy_item_head(&s_ih
, tp_item_head(path
));
1288 s_del_balance
.insert_size
[0] = del_size
;
1290 ret_value
= fix_nodes(M_DELETE
, &s_del_balance
, NULL
, NULL
);
1291 if (ret_value
!= REPEAT_SEARCH
)
1294 PROC_INFO_INC(sb
, delete_item_restarted
);
1296 /* file system changed, repeat search */
1298 search_for_position_by_key(sb
, item_key
, path
);
1299 if (ret_value
== IO_ERROR
)
1301 if (ret_value
== FILE_NOT_FOUND
) {
1302 reiserfs_warning(sb
, "vs-5340",
1303 "no items of the file %K found",
1309 if (ret_value
!= CARRY_ON
) {
1310 unfix_nodes(&s_del_balance
);
1314 /* reiserfs_delete_item returns item length when success */
1315 ret_value
= calc_deleted_bytes_number(&s_del_balance
, M_DELETE
);
1316 q_ih
= tp_item_head(path
);
1317 quota_cut_bytes
= ih_item_len(q_ih
);
1320 * hack so the quota code doesn't have to guess if the file has a
1321 * tail. On tail insert, we allocate quota for 1 unformatted node.
1322 * We test the offset because the tail might have been
1323 * split into multiple items, and we only want to decrement for
1324 * the unfm node once
1326 if (!S_ISLNK(inode
->i_mode
) && is_direct_le_ih(q_ih
)) {
1327 if ((le_ih_k_offset(q_ih
) & (sb
->s_blocksize
- 1)) == 1) {
1328 quota_cut_bytes
= sb
->s_blocksize
+ UNFM_P_SIZE
;
1330 quota_cut_bytes
= 0;
1339 * We are in direct2indirect conversion, so move tail contents
1340 * to the unformatted node
1343 * note, we do the copy before preparing the buffer because we
1344 * don't care about the contents of the unformatted node yet.
1345 * the only thing we really care about is the direct item's
1346 * data is in the unformatted node.
1348 * Otherwise, we would have to call
1349 * reiserfs_prepare_for_journal on the unformatted node,
1350 * which might schedule, meaning we'd have to loop all the
1351 * way back up to the start of the while loop.
1353 * The unformatted node must be dirtied later on. We can't be
1354 * sure here if the entire tail has been deleted yet.
1356 * un_bh is from the page cache (all unformatted nodes are
1357 * from the page cache) and might be a highmem page. So, we
1358 * can't use un_bh->b_data.
1362 data
= kmap_atomic(un_bh
->b_page
);
1363 off
= ((le_ih_k_offset(&s_ih
) - 1) & (PAGE_SIZE
- 1));
1365 ih_item_body(PATH_PLAST_BUFFER(path
), &s_ih
),
1367 kunmap_atomic(data
);
1370 /* Perform balancing after all resources have been collected at once. */
1371 do_balance(&s_del_balance
, NULL
, NULL
, M_DELETE
);
1373 #ifdef REISERQUOTA_DEBUG
1374 reiserfs_debug(sb
, REISERFS_DEBUG_CODE
,
1375 "reiserquota delete_item(): freeing %u, id=%u type=%c",
1376 quota_cut_bytes
, inode
->i_uid
, head2type(&s_ih
));
1378 depth
= reiserfs_write_unlock_nested(inode
->i_sb
);
1379 dquot_free_space_nodirty(inode
, quota_cut_bytes
);
1380 reiserfs_write_lock_nested(inode
->i_sb
, depth
);
1382 /* Return deleted body length */
1387 * Summary Of Mechanisms For Handling Collisions Between Processes:
1389 * deletion of the body of the object is performed by iput(), with the
1390 * result that if multiple processes are operating on a file, the
1391 * deletion of the body of the file is deferred until the last process
1392 * that has an open inode performs its iput().
1394 * writes and truncates are protected from collisions by use of
1397 * creates, linking, and mknod are protected from collisions with other
1398 * processes by making the reiserfs_add_entry() the last step in the
1399 * creation, and then rolling back all changes if there was a collision.
1403 /* this deletes item which never gets split */
1404 void reiserfs_delete_solid_item(struct reiserfs_transaction_handle
*th
,
1405 struct inode
*inode
, struct reiserfs_key
*key
)
1407 struct super_block
*sb
= th
->t_super
;
1408 struct tree_balance tb
;
1409 INITIALIZE_PATH(path
);
1412 struct cpu_key cpu_key
;
1414 int quota_cut_bytes
= 0;
1416 BUG_ON(!th
->t_trans_id
);
1418 le_key2cpu_key(&cpu_key
, key
);
1421 retval
= search_item(th
->t_super
, &cpu_key
, &path
);
1422 if (retval
== IO_ERROR
) {
1423 reiserfs_error(th
->t_super
, "vs-5350",
1424 "i/o failure occurred trying "
1425 "to delete %K", &cpu_key
);
1428 if (retval
!= ITEM_FOUND
) {
1431 * No need for a warning, if there is just no free
1432 * space to insert '..' item into the
1433 * newly-created subdir
1436 ((unsigned long long)
1437 GET_HASH_VALUE(le_key_k_offset
1438 (le_key_version(key
), key
)) == 0
1439 && (unsigned long long)
1440 GET_GENERATION_NUMBER(le_key_k_offset
1441 (le_key_version(key
),
1443 reiserfs_warning(th
->t_super
, "vs-5355",
1444 "%k not found", key
);
1449 item_len
= ih_item_len(tp_item_head(&path
));
1450 init_tb_struct(th
, &tb
, th
->t_super
, &path
,
1451 -(IH_SIZE
+ item_len
));
1453 quota_cut_bytes
= ih_item_len(tp_item_head(&path
));
1455 retval
= fix_nodes(M_DELETE
, &tb
, NULL
, NULL
);
1456 if (retval
== REPEAT_SEARCH
) {
1457 PROC_INFO_INC(th
->t_super
, delete_solid_item_restarted
);
1461 if (retval
== CARRY_ON
) {
1462 do_balance(&tb
, NULL
, NULL
, M_DELETE
);
1464 * Should we count quota for item? (we don't
1465 * count quotas for save-links)
1469 #ifdef REISERQUOTA_DEBUG
1470 reiserfs_debug(th
->t_super
, REISERFS_DEBUG_CODE
,
1471 "reiserquota delete_solid_item(): freeing %u id=%u type=%c",
1472 quota_cut_bytes
, inode
->i_uid
,
1475 depth
= reiserfs_write_unlock_nested(sb
);
1476 dquot_free_space_nodirty(inode
,
1478 reiserfs_write_lock_nested(sb
, depth
);
1483 /* IO_ERROR, NO_DISK_SPACE, etc */
1484 reiserfs_warning(th
->t_super
, "vs-5360",
1485 "could not delete %K due to fix_nodes failure",
1491 reiserfs_check_path(&path
);
1494 int reiserfs_delete_object(struct reiserfs_transaction_handle
*th
,
1495 struct inode
*inode
)
1499 BUG_ON(!th
->t_trans_id
);
1501 /* for directory this deletes item containing "." and ".." */
1503 reiserfs_do_truncate(th
, inode
, NULL
, 0 /*no timestamp updates */ );
1507 #if defined( USE_INODE_GENERATION_COUNTER )
1508 if (!old_format_only(th
->t_super
)) {
1509 __le32
*inode_generation
;
1512 &REISERFS_SB(th
->t_super
)->s_rs
->s_inode_generation
;
1513 le32_add_cpu(inode_generation
, 1);
1515 /* USE_INODE_GENERATION_COUNTER */
1517 reiserfs_delete_solid_item(th
, inode
, INODE_PKEY(inode
));
1522 static void unmap_buffers(struct page
*page
, loff_t pos
)
1524 struct buffer_head
*bh
;
1525 struct buffer_head
*head
;
1526 struct buffer_head
*next
;
1527 unsigned long tail_index
;
1528 unsigned long cur_index
;
1531 if (page_has_buffers(page
)) {
1532 tail_index
= pos
& (PAGE_SIZE
- 1);
1534 head
= page_buffers(page
);
1537 next
= bh
->b_this_page
;
1540 * we want to unmap the buffers that contain
1541 * the tail, and all the buffers after it
1542 * (since the tail must be at the end of the
1543 * file). We don't want to unmap file data
1544 * before the tail, since it might be dirty
1545 * and waiting to reach disk
1547 cur_index
+= bh
->b_size
;
1548 if (cur_index
> tail_index
) {
1549 reiserfs_unmap_buffer(bh
);
1552 } while (bh
!= head
);
1557 static int maybe_indirect_to_direct(struct reiserfs_transaction_handle
*th
,
1558 struct inode
*inode
,
1560 struct treepath
*path
,
1561 const struct cpu_key
*item_key
,
1562 loff_t new_file_size
, char *mode
)
1564 struct super_block
*sb
= inode
->i_sb
;
1565 int block_size
= sb
->s_blocksize
;
1567 BUG_ON(!th
->t_trans_id
);
1568 BUG_ON(new_file_size
!= inode
->i_size
);
1571 * the page being sent in could be NULL if there was an i/o error
1572 * reading in the last block. The user will hit problems trying to
1573 * read the file, but for now we just skip the indirect2direct
1575 if (atomic_read(&inode
->i_count
) > 1 ||
1576 !tail_has_to_be_packed(inode
) ||
1577 !page
|| (REISERFS_I(inode
)->i_flags
& i_nopack_mask
)) {
1578 /* leave tail in an unformatted node */
1579 *mode
= M_SKIP_BALANCING
;
1581 block_size
- (new_file_size
& (block_size
- 1));
1586 /* Perform the conversion to a direct_item. */
1587 return indirect2direct(th
, inode
, page
, path
, item_key
,
1588 new_file_size
, mode
);
1592 * we did indirect_to_direct conversion. And we have inserted direct
1593 * item successesfully, but there were no disk space to cut unfm
1594 * pointer being converted. Therefore we have to delete inserted
1597 static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle
*th
,
1598 struct inode
*inode
, struct treepath
*path
)
1600 struct cpu_key tail_key
;
1603 BUG_ON(!th
->t_trans_id
);
1605 make_cpu_key(&tail_key
, inode
, inode
->i_size
+ 1, TYPE_DIRECT
, 4);
1606 tail_key
.key_length
= 4;
1609 (cpu_key_k_offset(&tail_key
) & (inode
->i_sb
->s_blocksize
- 1)) - 1;
1611 /* look for the last byte of the tail */
1612 if (search_for_position_by_key(inode
->i_sb
, &tail_key
, path
) ==
1614 reiserfs_panic(inode
->i_sb
, "vs-5615",
1615 "found invalid item");
1616 RFALSE(path
->pos_in_item
!=
1617 ih_item_len(tp_item_head(path
)) - 1,
1618 "vs-5616: appended bytes found");
1619 PATH_LAST_POSITION(path
)--;
1622 reiserfs_delete_item(th
, path
, &tail_key
, inode
,
1623 NULL
/*unbh not needed */ );
1625 || removed
> tail_len
,
1626 "vs-5617: there was tail %d bytes, removed item length %d bytes",
1628 tail_len
-= removed
;
1629 set_cpu_key_k_offset(&tail_key
,
1630 cpu_key_k_offset(&tail_key
) - removed
);
1632 reiserfs_warning(inode
->i_sb
, "reiserfs-5091", "indirect_to_direct "
1633 "conversion has been rolled back due to "
1634 "lack of disk space");
1635 mark_inode_dirty(inode
);
1638 /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */
1639 int reiserfs_cut_from_item(struct reiserfs_transaction_handle
*th
,
1640 struct treepath
*path
,
1641 struct cpu_key
*item_key
,
1642 struct inode
*inode
,
1643 struct page
*page
, loff_t new_file_size
)
1645 struct super_block
*sb
= inode
->i_sb
;
1647 * Every function which is going to call do_balance must first
1648 * create a tree_balance structure. Then it must fill up this
1649 * structure by using the init_tb_struct and fix_nodes functions.
1650 * After that we can make tree balancing.
1652 struct tree_balance s_cut_balance
;
1653 struct item_head
*p_le_ih
;
1654 int cut_size
= 0; /* Amount to be cut. */
1655 int ret_value
= CARRY_ON
;
1656 int removed
= 0; /* Number of the removed unformatted nodes. */
1657 int is_inode_locked
= 0;
1658 char mode
; /* Mode of the balance. */
1660 int quota_cut_bytes
;
1661 loff_t tail_pos
= 0;
1664 BUG_ON(!th
->t_trans_id
);
1666 init_tb_struct(th
, &s_cut_balance
, inode
->i_sb
, path
,
1670 * Repeat this loop until we either cut the item without needing
1671 * to balance, or we fix_nodes without schedule occurring
1675 * Determine the balance mode, position of the first byte to
1676 * be cut, and size to be cut. In case of the indirect item
1677 * free unformatted nodes which are pointed to by the cut
1682 prepare_for_delete_or_cut(th
, inode
, path
,
1684 &cut_size
, new_file_size
);
1685 if (mode
== M_CONVERT
) {
1687 * convert last unformatted node to direct item or
1688 * leave tail in the unformatted node
1690 RFALSE(ret_value
!= CARRY_ON
,
1691 "PAP-5570: can not convert twice");
1694 maybe_indirect_to_direct(th
, inode
, page
,
1696 new_file_size
, &mode
);
1697 if (mode
== M_SKIP_BALANCING
)
1698 /* tail has been left in the unformatted node */
1701 is_inode_locked
= 1;
1704 * removing of last unformatted node will
1705 * change value we have to return to truncate.
1708 retval2
= ret_value
;
1711 * So, we have performed the first part of the
1713 * inserting the new direct item. Now we are
1714 * removing the last unformatted node pointer.
1715 * Set key to search for it.
1717 set_cpu_key_k_type(item_key
, TYPE_INDIRECT
);
1718 item_key
->key_length
= 4;
1720 (new_file_size
& (sb
->s_blocksize
- 1));
1721 tail_pos
= new_file_size
;
1722 set_cpu_key_k_offset(item_key
, new_file_size
+ 1);
1723 if (search_for_position_by_key
1725 path
) == POSITION_NOT_FOUND
) {
1726 print_block(PATH_PLAST_BUFFER(path
), 3,
1727 PATH_LAST_POSITION(path
) - 1,
1728 PATH_LAST_POSITION(path
) + 1);
1729 reiserfs_panic(sb
, "PAP-5580", "item to "
1730 "convert does not exist (%K)",
1735 if (cut_size
== 0) {
1740 s_cut_balance
.insert_size
[0] = cut_size
;
1742 ret_value
= fix_nodes(mode
, &s_cut_balance
, NULL
, NULL
);
1743 if (ret_value
!= REPEAT_SEARCH
)
1746 PROC_INFO_INC(sb
, cut_from_item_restarted
);
1749 search_for_position_by_key(sb
, item_key
, path
);
1750 if (ret_value
== POSITION_FOUND
)
1753 reiserfs_warning(sb
, "PAP-5610", "item %K not found",
1755 unfix_nodes(&s_cut_balance
);
1756 return (ret_value
== IO_ERROR
) ? -EIO
: -ENOENT
;
1759 /* check fix_nodes results (IO_ERROR or NO_DISK_SPACE) */
1760 if (ret_value
!= CARRY_ON
) {
1761 if (is_inode_locked
) {
1763 * FIXME: this seems to be not needed: we are always
1766 indirect_to_direct_roll_back(th
, inode
, path
);
1768 if (ret_value
== NO_DISK_SPACE
)
1769 reiserfs_warning(sb
, "reiserfs-5092",
1771 unfix_nodes(&s_cut_balance
);
1775 /* go ahead and perform balancing */
1777 RFALSE(mode
== M_PASTE
|| mode
== M_INSERT
, "invalid mode");
1779 /* Calculate number of bytes that need to be cut from the item. */
1782 M_DELETE
) ? ih_item_len(tp_item_head(path
)) : -s_cut_balance
.
1785 ret_value
= calc_deleted_bytes_number(&s_cut_balance
, mode
);
1787 ret_value
= retval2
;
1790 * For direct items, we only change the quota when deleting the last
1793 p_le_ih
= tp_item_head(s_cut_balance
.tb_path
);
1794 if (!S_ISLNK(inode
->i_mode
) && is_direct_le_ih(p_le_ih
)) {
1795 if (mode
== M_DELETE
&&
1796 (le_ih_k_offset(p_le_ih
) & (sb
->s_blocksize
- 1)) ==
1798 /* FIXME: this is to keep 3.5 happy */
1799 REISERFS_I(inode
)->i_first_direct_byte
= U32_MAX
;
1800 quota_cut_bytes
= sb
->s_blocksize
+ UNFM_P_SIZE
;
1802 quota_cut_bytes
= 0;
1805 #ifdef CONFIG_REISERFS_CHECK
1806 if (is_inode_locked
) {
1807 struct item_head
*le_ih
=
1808 tp_item_head(s_cut_balance
.tb_path
);
1810 * we are going to complete indirect2direct conversion. Make
1811 * sure, that we exactly remove last unformatted node pointer
1814 if (!is_indirect_le_ih(le_ih
))
1815 reiserfs_panic(sb
, "vs-5652",
1816 "item must be indirect %h", le_ih
);
1818 if (mode
== M_DELETE
&& ih_item_len(le_ih
) != UNFM_P_SIZE
)
1819 reiserfs_panic(sb
, "vs-5653", "completing "
1820 "indirect2direct conversion indirect "
1821 "item %h being deleted must be of "
1822 "4 byte long", le_ih
);
1825 && s_cut_balance
.insert_size
[0] != -UNFM_P_SIZE
) {
1826 reiserfs_panic(sb
, "vs-5654", "can not complete "
1827 "indirect2direct conversion of %h "
1828 "(CUT, insert_size==%d)",
1829 le_ih
, s_cut_balance
.insert_size
[0]);
1832 * it would be useful to make sure, that right neighboring
1833 * item is direct item of this file
1838 do_balance(&s_cut_balance
, NULL
, NULL
, mode
);
1839 if (is_inode_locked
) {
1841 * we've done an indirect->direct conversion. when the
1842 * data block was freed, it was removed from the list of
1843 * blocks that must be flushed before the transaction
1844 * commits, make sure to unmap and invalidate it
1846 unmap_buffers(page
, tail_pos
);
1847 REISERFS_I(inode
)->i_flags
&= ~i_pack_on_close_mask
;
1849 #ifdef REISERQUOTA_DEBUG
1850 reiserfs_debug(inode
->i_sb
, REISERFS_DEBUG_CODE
,
1851 "reiserquota cut_from_item(): freeing %u id=%u type=%c",
1852 quota_cut_bytes
, inode
->i_uid
, '?');
1854 depth
= reiserfs_write_unlock_nested(sb
);
1855 dquot_free_space_nodirty(inode
, quota_cut_bytes
);
1856 reiserfs_write_lock_nested(sb
, depth
);
1860 static void truncate_directory(struct reiserfs_transaction_handle
*th
,
1861 struct inode
*inode
)
1863 BUG_ON(!th
->t_trans_id
);
1865 reiserfs_error(inode
->i_sb
, "vs-5655", "link count != 0");
1867 set_le_key_k_offset(KEY_FORMAT_3_5
, INODE_PKEY(inode
), DOT_OFFSET
);
1868 set_le_key_k_type(KEY_FORMAT_3_5
, INODE_PKEY(inode
), TYPE_DIRENTRY
);
1869 reiserfs_delete_solid_item(th
, inode
, INODE_PKEY(inode
));
1870 reiserfs_update_sd(th
, inode
);
1871 set_le_key_k_offset(KEY_FORMAT_3_5
, INODE_PKEY(inode
), SD_OFFSET
);
1872 set_le_key_k_type(KEY_FORMAT_3_5
, INODE_PKEY(inode
), TYPE_STAT_DATA
);
1876 * Truncate file to the new size. Note, this must be called with a
1877 * transaction already started
1879 int reiserfs_do_truncate(struct reiserfs_transaction_handle
*th
,
1880 struct inode
*inode
, /* ->i_size contains new size */
1881 struct page
*page
, /* up to date for last block */
1883 * when it is called by file_release to convert
1884 * the tail - no timestamps should be updated
1886 int update_timestamps
1889 INITIALIZE_PATH(s_search_path
); /* Path to the current object item. */
1890 struct item_head
*p_le_ih
; /* Pointer to an item header. */
1892 /* Key to search for a previous file item. */
1893 struct cpu_key s_item_key
;
1894 loff_t file_size
, /* Old file size. */
1895 new_file_size
; /* New file size. */
1896 int deleted
; /* Number of deleted or truncated bytes. */
1900 BUG_ON(!th
->t_trans_id
);
1902 (S_ISREG(inode
->i_mode
) || S_ISDIR(inode
->i_mode
)
1903 || S_ISLNK(inode
->i_mode
)))
1906 /* deletion of directory - no need to update timestamps */
1907 if (S_ISDIR(inode
->i_mode
)) {
1908 truncate_directory(th
, inode
);
1912 /* Get new file size. */
1913 new_file_size
= inode
->i_size
;
1915 /* FIXME: note, that key type is unimportant here */
1916 make_cpu_key(&s_item_key
, inode
, max_reiserfs_offset(inode
),
1920 search_for_position_by_key(inode
->i_sb
, &s_item_key
,
1922 if (retval
== IO_ERROR
) {
1923 reiserfs_error(inode
->i_sb
, "vs-5657",
1924 "i/o failure occurred trying to truncate %K",
1929 if (retval
== POSITION_FOUND
|| retval
== FILE_NOT_FOUND
) {
1930 reiserfs_error(inode
->i_sb
, "PAP-5660",
1931 "wrong result %d of search for %K", retval
,
1938 s_search_path
.pos_in_item
--;
1940 /* Get real file size (total length of all file items) */
1941 p_le_ih
= tp_item_head(&s_search_path
);
1942 if (is_statdata_le_ih(p_le_ih
))
1945 loff_t offset
= le_ih_k_offset(p_le_ih
);
1947 op_bytes_number(p_le_ih
, inode
->i_sb
->s_blocksize
);
1950 * this may mismatch with real file size: if last direct item
1951 * had no padding zeros and last unformatted node had no free
1952 * space, this file would have this file size
1954 file_size
= offset
+ bytes
- 1;
1957 * are we doing a full truncate or delete, if so
1958 * kick in the reada code
1960 if (new_file_size
== 0)
1961 s_search_path
.reada
= PATH_READA
| PATH_READA_BACK
;
1963 if (file_size
== 0 || file_size
< new_file_size
) {
1964 goto update_and_out
;
1967 /* Update key to search for the last file item. */
1968 set_cpu_key_k_offset(&s_item_key
, file_size
);
1971 /* Cut or delete file item. */
1973 reiserfs_cut_from_item(th
, &s_search_path
, &s_item_key
,
1974 inode
, page
, new_file_size
);
1976 reiserfs_warning(inode
->i_sb
, "vs-5665",
1977 "reiserfs_cut_from_item failed");
1978 reiserfs_check_path(&s_search_path
);
1982 RFALSE(deleted
> file_size
,
1983 "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K",
1984 deleted
, file_size
, &s_item_key
);
1986 /* Change key to search the last file item. */
1987 file_size
-= deleted
;
1989 set_cpu_key_k_offset(&s_item_key
, file_size
);
1992 * While there are bytes to truncate and previous
1993 * file item is presented in the tree.
1997 * This loop could take a really long time, and could log
1998 * many more blocks than a transaction can hold. So, we do
1999 * a polite journal end here, and if the transaction needs
2000 * ending, we make sure the file is consistent before ending
2001 * the current trans and starting a new one
2003 if (journal_transaction_should_end(th
, 0) ||
2004 reiserfs_transaction_free_space(th
) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD
) {
2005 pathrelse(&s_search_path
);
2007 if (update_timestamps
) {
2008 inode
->i_mtime
= current_time(inode
);
2009 inode
->i_ctime
= current_time(inode
);
2011 reiserfs_update_sd(th
, inode
);
2013 err
= journal_end(th
);
2016 err
= journal_begin(th
, inode
->i_sb
,
2017 JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD
+ JOURNAL_PER_BALANCE_CNT
* 4) ;
2020 reiserfs_update_inode_transaction(inode
);
2022 } while (file_size
> ROUND_UP(new_file_size
) &&
2023 search_for_position_by_key(inode
->i_sb
, &s_item_key
,
2024 &s_search_path
) == POSITION_FOUND
);
2026 RFALSE(file_size
> ROUND_UP(new_file_size
),
2027 "PAP-5680: truncate did not finish: new_file_size %lld, current %lld, oid %d",
2028 new_file_size
, file_size
, s_item_key
.on_disk_key
.k_objectid
);
2031 if (update_timestamps
) {
2032 /* this is truncate, not file closing */
2033 inode
->i_mtime
= current_time(inode
);
2034 inode
->i_ctime
= current_time(inode
);
2036 reiserfs_update_sd(th
, inode
);
2039 pathrelse(&s_search_path
);
2043 #ifdef CONFIG_REISERFS_CHECK
2044 /* this makes sure, that we __append__, not overwrite or add holes */
2045 static void check_research_for_paste(struct treepath
*path
,
2046 const struct cpu_key
*key
)
2048 struct item_head
*found_ih
= tp_item_head(path
);
2050 if (is_direct_le_ih(found_ih
)) {
2051 if (le_ih_k_offset(found_ih
) +
2052 op_bytes_number(found_ih
,
2053 get_last_bh(path
)->b_size
) !=
2054 cpu_key_k_offset(key
)
2055 || op_bytes_number(found_ih
,
2056 get_last_bh(path
)->b_size
) !=
2058 reiserfs_panic(NULL
, "PAP-5720", "found direct item "
2059 "%h or position (%d) does not match "
2060 "to key %K", found_ih
,
2061 pos_in_item(path
), key
);
2063 if (is_indirect_le_ih(found_ih
)) {
2064 if (le_ih_k_offset(found_ih
) +
2065 op_bytes_number(found_ih
,
2066 get_last_bh(path
)->b_size
) !=
2067 cpu_key_k_offset(key
)
2068 || I_UNFM_NUM(found_ih
) != pos_in_item(path
)
2069 || get_ih_free_space(found_ih
) != 0)
2070 reiserfs_panic(NULL
, "PAP-5730", "found indirect "
2071 "item (%h) or position (%d) does not "
2072 "match to key (%K)",
2073 found_ih
, pos_in_item(path
), key
);
2076 #endif /* config reiserfs check */
2079 * Paste bytes to the existing item.
2080 * Returns bytes number pasted into the item.
2082 int reiserfs_paste_into_item(struct reiserfs_transaction_handle
*th
,
2083 /* Path to the pasted item. */
2084 struct treepath
*search_path
,
2085 /* Key to search for the needed item. */
2086 const struct cpu_key
*key
,
2087 /* Inode item belongs to */
2088 struct inode
*inode
,
2089 /* Pointer to the bytes to paste. */
2091 /* Size of pasted bytes. */
2094 struct super_block
*sb
= inode
->i_sb
;
2095 struct tree_balance s_paste_balance
;
2100 BUG_ON(!th
->t_trans_id
);
2102 fs_gen
= get_generation(inode
->i_sb
);
2104 #ifdef REISERQUOTA_DEBUG
2105 reiserfs_debug(inode
->i_sb
, REISERFS_DEBUG_CODE
,
2106 "reiserquota paste_into_item(): allocating %u id=%u type=%c",
2107 pasted_size
, inode
->i_uid
,
2108 key2type(&key
->on_disk_key
));
2111 depth
= reiserfs_write_unlock_nested(sb
);
2112 retval
= dquot_alloc_space_nodirty(inode
, pasted_size
);
2113 reiserfs_write_lock_nested(sb
, depth
);
2115 pathrelse(search_path
);
2118 init_tb_struct(th
, &s_paste_balance
, th
->t_super
, search_path
,
2120 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
2121 s_paste_balance
.key
= key
->on_disk_key
;
2124 /* DQUOT_* can schedule, must check before the fix_nodes */
2125 if (fs_changed(fs_gen
, inode
->i_sb
)) {
2130 fix_nodes(M_PASTE
, &s_paste_balance
, NULL
,
2131 body
)) == REPEAT_SEARCH
) {
2133 /* file system changed while we were in the fix_nodes */
2134 PROC_INFO_INC(th
->t_super
, paste_into_item_restarted
);
2136 search_for_position_by_key(th
->t_super
, key
,
2138 if (retval
== IO_ERROR
) {
2142 if (retval
== POSITION_FOUND
) {
2143 reiserfs_warning(inode
->i_sb
, "PAP-5710",
2144 "entry or pasted byte (%K) exists",
2149 #ifdef CONFIG_REISERFS_CHECK
2150 check_research_for_paste(search_path
, key
);
2155 * Perform balancing after all resources are collected by fix_nodes,
2156 * and accessing them will not risk triggering schedule.
2158 if (retval
== CARRY_ON
) {
2159 do_balance(&s_paste_balance
, NULL
/*ih */ , body
, M_PASTE
);
2162 retval
= (retval
== NO_DISK_SPACE
) ? -ENOSPC
: -EIO
;
2164 /* this also releases the path */
2165 unfix_nodes(&s_paste_balance
);
2166 #ifdef REISERQUOTA_DEBUG
2167 reiserfs_debug(inode
->i_sb
, REISERFS_DEBUG_CODE
,
2168 "reiserquota paste_into_item(): freeing %u id=%u type=%c",
2169 pasted_size
, inode
->i_uid
,
2170 key2type(&key
->on_disk_key
));
2172 depth
= reiserfs_write_unlock_nested(sb
);
2173 dquot_free_space_nodirty(inode
, pasted_size
);
2174 reiserfs_write_lock_nested(sb
, depth
);
2179 * Insert new item into the buffer at the path.
2180 * th - active transaction handle
2181 * path - path to the inserted item
2182 * ih - pointer to the item header to insert
2183 * body - pointer to the bytes to insert
2185 int reiserfs_insert_item(struct reiserfs_transaction_handle
*th
,
2186 struct treepath
*path
, const struct cpu_key
*key
,
2187 struct item_head
*ih
, struct inode
*inode
,
2190 struct tree_balance s_ins_balance
;
2193 int quota_bytes
= 0;
2195 BUG_ON(!th
->t_trans_id
);
2197 if (inode
) { /* Do we count quotas for item? */
2199 fs_gen
= get_generation(inode
->i_sb
);
2200 quota_bytes
= ih_item_len(ih
);
2203 * hack so the quota code doesn't have to guess
2204 * if the file has a tail, links are always tails,
2205 * so there's no guessing needed
2207 if (!S_ISLNK(inode
->i_mode
) && is_direct_le_ih(ih
))
2208 quota_bytes
= inode
->i_sb
->s_blocksize
+ UNFM_P_SIZE
;
2209 #ifdef REISERQUOTA_DEBUG
2210 reiserfs_debug(inode
->i_sb
, REISERFS_DEBUG_CODE
,
2211 "reiserquota insert_item(): allocating %u id=%u type=%c",
2212 quota_bytes
, inode
->i_uid
, head2type(ih
));
2215 * We can't dirty inode here. It would be immediately
2216 * written but appropriate stat item isn't inserted yet...
2218 depth
= reiserfs_write_unlock_nested(inode
->i_sb
);
2219 retval
= dquot_alloc_space_nodirty(inode
, quota_bytes
);
2220 reiserfs_write_lock_nested(inode
->i_sb
, depth
);
2226 init_tb_struct(th
, &s_ins_balance
, th
->t_super
, path
,
2227 IH_SIZE
+ ih_item_len(ih
));
2228 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
2229 s_ins_balance
.key
= key
->on_disk_key
;
2232 * DQUOT_* can schedule, must check to be sure calling
2235 if (inode
&& fs_changed(fs_gen
, inode
->i_sb
)) {
2240 fix_nodes(M_INSERT
, &s_ins_balance
, ih
,
2241 body
)) == REPEAT_SEARCH
) {
2243 /* file system changed while we were in the fix_nodes */
2244 PROC_INFO_INC(th
->t_super
, insert_item_restarted
);
2245 retval
= search_item(th
->t_super
, key
, path
);
2246 if (retval
== IO_ERROR
) {
2250 if (retval
== ITEM_FOUND
) {
2251 reiserfs_warning(th
->t_super
, "PAP-5760",
2252 "key %K already exists in the tree",
2259 /* make balancing after all resources will be collected at a time */
2260 if (retval
== CARRY_ON
) {
2261 do_balance(&s_ins_balance
, ih
, body
, M_INSERT
);
2265 retval
= (retval
== NO_DISK_SPACE
) ? -ENOSPC
: -EIO
;
2267 /* also releases the path */
2268 unfix_nodes(&s_ins_balance
);
2269 #ifdef REISERQUOTA_DEBUG
2271 reiserfs_debug(th
->t_super
, REISERFS_DEBUG_CODE
,
2272 "reiserquota insert_item(): freeing %u id=%u type=%c",
2273 quota_bytes
, inode
->i_uid
, head2type(ih
));
2276 int depth
= reiserfs_write_unlock_nested(inode
->i_sb
);
2277 dquot_free_space_nodirty(inode
, quota_bytes
);
2278 reiserfs_write_lock_nested(inode
->i_sb
, depth
);