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 is_leaf(char *buf
, int blocksize
, struct buffer_head
*bh
)
392 struct block_head
*blkh
;
393 struct item_head
*ih
;
399 blkh
= (struct block_head
*)buf
;
400 if (blkh_level(blkh
) != DISK_LEAF_NODE_LEVEL
) {
401 reiserfs_warning(NULL
, "reiserfs-5080",
402 "this should be caught earlier");
406 nr
= blkh_nr_item(blkh
);
407 if (nr
< 1 || nr
> ((blocksize
- BLKH_SIZE
) / (IH_SIZE
+ MIN_ITEM_LEN
))) {
408 /* item number is too big or too small */
409 reiserfs_warning(NULL
, "reiserfs-5081",
410 "nr_item seems wrong: %z", bh
);
413 ih
= (struct item_head
*)(buf
+ BLKH_SIZE
) + nr
- 1;
414 used_space
= BLKH_SIZE
+ IH_SIZE
* nr
+ (blocksize
- ih_location(ih
));
416 /* free space does not match to calculated amount of use space */
417 if (used_space
!= blocksize
- blkh_free_space(blkh
)) {
418 reiserfs_warning(NULL
, "reiserfs-5082",
419 "free space seems wrong: %z", bh
);
423 * FIXME: it is_leaf will hit performance too much - we may have
427 /* check tables of item heads */
428 ih
= (struct item_head
*)(buf
+ BLKH_SIZE
);
429 prev_location
= blocksize
;
430 for (i
= 0; i
< nr
; i
++, ih
++) {
431 if (le_ih_k_type(ih
) == TYPE_ANY
) {
432 reiserfs_warning(NULL
, "reiserfs-5083",
433 "wrong item type for item %h",
437 if (ih_location(ih
) >= blocksize
438 || ih_location(ih
) < IH_SIZE
* nr
) {
439 reiserfs_warning(NULL
, "reiserfs-5084",
440 "item location seems wrong: %h",
444 if (ih_item_len(ih
) < 1
445 || ih_item_len(ih
) > MAX_ITEM_LEN(blocksize
)) {
446 reiserfs_warning(NULL
, "reiserfs-5085",
447 "item length seems wrong: %h",
451 if (prev_location
- ih_location(ih
) != ih_item_len(ih
)) {
452 reiserfs_warning(NULL
, "reiserfs-5086",
453 "item location seems wrong "
454 "(second one): %h", ih
);
457 if (is_direntry_le_ih(ih
) && (ih_item_len(ih
) < (ih_entry_count(ih
) * IH_SIZE
))) {
458 reiserfs_warning(NULL
, "reiserfs-5093",
459 "item entry count seems wrong %h",
463 prev_location
= ih_location(ih
);
466 /* one may imagine many more checks */
470 /* returns 1 if buf looks like an internal node, 0 otherwise */
471 static int is_internal(char *buf
, int blocksize
, struct buffer_head
*bh
)
473 struct block_head
*blkh
;
477 blkh
= (struct block_head
*)buf
;
478 nr
= blkh_level(blkh
);
479 if (nr
<= DISK_LEAF_NODE_LEVEL
|| nr
> MAX_HEIGHT
) {
480 /* this level is not possible for internal nodes */
481 reiserfs_warning(NULL
, "reiserfs-5087",
482 "this should be caught earlier");
486 nr
= blkh_nr_item(blkh
);
487 /* for internal which is not root we might check min number of keys */
488 if (nr
> (blocksize
- BLKH_SIZE
- DC_SIZE
) / (KEY_SIZE
+ DC_SIZE
)) {
489 reiserfs_warning(NULL
, "reiserfs-5088",
490 "number of key seems wrong: %z", bh
);
494 used_space
= BLKH_SIZE
+ KEY_SIZE
* nr
+ DC_SIZE
* (nr
+ 1);
495 if (used_space
!= blocksize
- blkh_free_space(blkh
)) {
496 reiserfs_warning(NULL
, "reiserfs-5089",
497 "free space seems wrong: %z", bh
);
501 /* one may imagine many more checks */
506 * make sure that bh contains formatted node of reiserfs tree of
509 static int is_tree_node(struct buffer_head
*bh
, int level
)
511 if (B_LEVEL(bh
) != level
) {
512 reiserfs_warning(NULL
, "reiserfs-5090", "node level %d does "
513 "not match to the expected one %d",
517 if (level
== DISK_LEAF_NODE_LEVEL
)
518 return is_leaf(bh
->b_data
, bh
->b_size
, bh
);
520 return is_internal(bh
->b_data
, bh
->b_size
, bh
);
523 #define SEARCH_BY_KEY_READA 16
526 * The function is NOT SCHEDULE-SAFE!
527 * It might unlock the write lock if we needed to wait for a block
528 * to be read. Note that in this case it won't recover the lock to avoid
529 * high contention resulting from too much lock requests, especially
530 * the caller (search_by_key) will perform other schedule-unsafe
531 * operations just after calling this function.
533 * @return depth of lock to be restored after read completes
535 static int search_by_key_reada(struct super_block
*s
,
536 struct buffer_head
**bh
,
537 b_blocknr_t
*b
, int num
)
542 for (i
= 0; i
< num
; i
++) {
543 bh
[i
] = sb_getblk(s
, b
[i
]);
546 * We are going to read some blocks on which we
547 * have a reference. It's safe, though we might be
548 * reading blocks concurrently changed if we release
549 * the lock. But it's still fine because we check later
550 * if the tree changed
552 for (j
= 0; j
< i
; j
++) {
554 * note, this needs attention if we are getting rid of the BKL
555 * you have to make sure the prepared bit isn't set on this
558 if (!buffer_uptodate(bh
[j
])) {
560 depth
= reiserfs_write_unlock_nested(s
);
561 ll_rw_block(REQ_OP_READ
, REQ_RAHEAD
, 1, bh
+ j
);
569 * This function fills up the path from the root to the leaf as it
570 * descends the tree looking for the key. It uses reiserfs_bread to
571 * try to find buffers in the cache given their block number. If it
572 * does not find them in the cache it reads them from disk. For each
573 * node search_by_key finds using reiserfs_bread it then uses
574 * bin_search to look through that node. bin_search will find the
575 * position of the block_number of the next node if it is looking
576 * through an internal node. If it is looking through a leaf node
577 * bin_search will find the position of the item which has key either
578 * equal to given key, or which is the maximal key less than the given
579 * key. search_by_key returns a path that must be checked for the
580 * correctness of the top of the path but need not be checked for the
581 * correctness of the bottom of the path
584 * search_by_key - search for key (and item) in stree
586 * @key: pointer to key to search for
587 * @search_path: Allocated and initialized struct treepath; Returned filled
589 * @stop_level: How far down the tree to search, Use DISK_LEAF_NODE_LEVEL to
590 * stop at leaf level.
592 * The function is NOT SCHEDULE-SAFE!
594 int search_by_key(struct super_block
*sb
, const struct cpu_key
*key
,
595 struct treepath
*search_path
, int stop_level
)
597 b_blocknr_t block_number
;
599 struct buffer_head
*bh
;
600 struct path_element
*last_element
;
601 int node_level
, retval
;
603 struct buffer_head
*reada_bh
[SEARCH_BY_KEY_READA
];
604 b_blocknr_t reada_blocks
[SEARCH_BY_KEY_READA
];
607 #ifdef CONFIG_REISERFS_CHECK
608 int repeat_counter
= 0;
611 PROC_INFO_INC(sb
, search_by_key
);
614 * As we add each node to a path we increase its count. This means
615 * that we must be careful to release all nodes in a path before we
616 * either discard the path struct or re-use the path struct, as we
620 pathrelse(search_path
);
623 * With each iteration of this loop we search through the items in the
624 * current node, and calculate the next current node(next path element)
625 * for the next iteration of this loop..
627 block_number
= SB_ROOT_BLOCK(sb
);
631 #ifdef CONFIG_REISERFS_CHECK
632 if (!(++repeat_counter
% 50000))
633 reiserfs_warning(sb
, "PAP-5100",
634 "%s: there were %d iterations of "
635 "while loop looking for key %K",
636 current
->comm
, repeat_counter
,
640 /* prep path to have another element added to it. */
642 PATH_OFFSET_PELEMENT(search_path
,
643 ++search_path
->path_length
);
644 fs_gen
= get_generation(sb
);
647 * Read the next tree node, and set the last element
648 * in the path to have a pointer to it.
650 if ((bh
= last_element
->pe_buffer
=
651 sb_getblk(sb
, block_number
))) {
654 * We'll need to drop the lock if we encounter any
655 * buffers that need to be read. If all of them are
656 * already up to date, we don't need to drop the lock.
660 if (!buffer_uptodate(bh
) && reada_count
> 1)
661 depth
= search_by_key_reada(sb
, reada_bh
,
662 reada_blocks
, reada_count
);
664 if (!buffer_uptodate(bh
) && depth
== -1)
665 depth
= reiserfs_write_unlock_nested(sb
);
667 ll_rw_block(REQ_OP_READ
, 0, 1, &bh
);
671 reiserfs_write_lock_nested(sb
, depth
);
672 if (!buffer_uptodate(bh
))
676 search_path
->path_length
--;
677 pathrelse(search_path
);
681 if (expected_level
== -1)
682 expected_level
= SB_TREE_HEIGHT(sb
);
686 * It is possible that schedule occurred. We must check
687 * whether the key to search is still in the tree rooted
688 * from the current buffer. If not then repeat search
691 if (fs_changed(fs_gen
, sb
) &&
692 (!B_IS_IN_TREE(bh
) ||
693 B_LEVEL(bh
) != expected_level
||
694 !key_in_buffer(search_path
, key
, sb
))) {
695 PROC_INFO_INC(sb
, search_by_key_fs_changed
);
696 PROC_INFO_INC(sb
, search_by_key_restarted
);
698 sbk_restarted
[expected_level
- 1]);
699 pathrelse(search_path
);
702 * Get the root block number so that we can
703 * repeat the search starting from the root.
705 block_number
= SB_ROOT_BLOCK(sb
);
708 /* repeat search from the root */
713 * only check that the key is in the buffer if key is not
714 * equal to the MAX_KEY. Latter case is only possible in
715 * "finish_unfinished()" processing during mount.
717 RFALSE(comp_keys(&MAX_KEY
, key
) &&
718 !key_in_buffer(search_path
, key
, sb
),
719 "PAP-5130: key is not in the buffer");
720 #ifdef CONFIG_REISERFS_CHECK
721 if (REISERFS_SB(sb
)->cur_tb
) {
722 print_cur_tb("5140");
723 reiserfs_panic(sb
, "PAP-5140",
724 "schedule occurred in do_balance!");
729 * make sure, that the node contents look like a node of
732 if (!is_tree_node(bh
, expected_level
)) {
733 reiserfs_error(sb
, "vs-5150",
734 "invalid format found in block %ld. "
735 "Fsck?", bh
->b_blocknr
);
736 pathrelse(search_path
);
740 /* ok, we have acquired next formatted node in the tree */
741 node_level
= B_LEVEL(bh
);
743 PROC_INFO_BH_STAT(sb
, bh
, node_level
- 1);
745 RFALSE(node_level
< stop_level
,
746 "vs-5152: tree level (%d) is less than stop level (%d)",
747 node_level
, stop_level
);
749 retval
= bin_search(key
, item_head(bh
, 0),
752 DISK_LEAF_NODE_LEVEL
) ? IH_SIZE
:
754 &last_element
->pe_position
);
755 if (node_level
== stop_level
) {
759 /* we are not in the stop level */
761 * item has been found, so we choose the pointer which
762 * is to the right of the found one
764 if (retval
== ITEM_FOUND
)
765 last_element
->pe_position
++;
768 * if item was not found we choose the position which is to
769 * the left of the found item. This requires no code,
770 * bin_search did it already.
774 * So we have chosen a position in the current node which is
775 * an internal node. Now we calculate child block number by
776 * position in the node.
779 B_N_CHILD_NUM(bh
, last_element
->pe_position
);
782 * if we are going to read leaf nodes, try for read
785 if ((search_path
->reada
& PATH_READA
) &&
786 node_level
== DISK_LEAF_NODE_LEVEL
+ 1) {
787 int pos
= last_element
->pe_position
;
788 int limit
= B_NR_ITEMS(bh
);
789 struct reiserfs_key
*le_key
;
791 if (search_path
->reada
& PATH_READA_BACK
)
793 while (reada_count
< SEARCH_BY_KEY_READA
) {
796 reada_blocks
[reada_count
++] =
797 B_N_CHILD_NUM(bh
, pos
);
798 if (search_path
->reada
& PATH_READA_BACK
)
804 * check to make sure we're in the same object
806 le_key
= internal_key(bh
, pos
);
807 if (le32_to_cpu(le_key
->k_objectid
) !=
808 key
->on_disk_key
.k_objectid
) {
817 * Form the path to an item and position in this item which contains
818 * file byte defined by key. If there is no such item
819 * corresponding to the key, we point the path to the item with
820 * maximal key less than key, and *pos_in_item is set to one
821 * past the last entry/byte in the item. If searching for entry in a
822 * directory item, and it is not found, *pos_in_item is set to one
823 * entry more than the entry with maximal key which is less than the
826 * Note that if there is no entry in this same node which is one more,
827 * then we point to an imaginary entry. for direct items, the
828 * position is in units of bytes, for indirect items the position is
829 * in units of blocknr entries, for directory items the position is in
830 * units of directory entries.
832 /* The function is NOT SCHEDULE-SAFE! */
833 int search_for_position_by_key(struct super_block
*sb
,
834 /* Key to search (cpu variable) */
835 const struct cpu_key
*p_cpu_key
,
836 /* Filled up by this function. */
837 struct treepath
*search_path
)
839 struct item_head
*p_le_ih
; /* pointer to on-disk structure */
841 loff_t item_offset
, offset
;
842 struct reiserfs_dir_entry de
;
845 /* If searching for directory entry. */
846 if (is_direntry_cpu_key(p_cpu_key
))
847 return search_by_entry_key(sb
, p_cpu_key
, search_path
,
850 /* If not searching for directory entry. */
852 /* If item is found. */
853 retval
= search_item(sb
, p_cpu_key
, search_path
);
854 if (retval
== IO_ERROR
)
856 if (retval
== ITEM_FOUND
) {
860 (PATH_PLAST_BUFFER(search_path
),
861 PATH_LAST_POSITION(search_path
))),
862 "PAP-5165: item length equals zero");
864 pos_in_item(search_path
) = 0;
865 return POSITION_FOUND
;
868 RFALSE(!PATH_LAST_POSITION(search_path
),
869 "PAP-5170: position equals zero");
871 /* Item is not found. Set path to the previous item. */
873 item_head(PATH_PLAST_BUFFER(search_path
),
874 --PATH_LAST_POSITION(search_path
));
875 blk_size
= sb
->s_blocksize
;
877 if (comp_short_keys(&p_le_ih
->ih_key
, p_cpu_key
))
878 return FILE_NOT_FOUND
;
880 /* FIXME: quite ugly this far */
882 item_offset
= le_ih_k_offset(p_le_ih
);
883 offset
= cpu_key_k_offset(p_cpu_key
);
885 /* Needed byte is contained in the item pointed to by the path. */
886 if (item_offset
<= offset
&&
887 item_offset
+ op_bytes_number(p_le_ih
, blk_size
) > offset
) {
888 pos_in_item(search_path
) = offset
- item_offset
;
889 if (is_indirect_le_ih(p_le_ih
)) {
890 pos_in_item(search_path
) /= blk_size
;
892 return POSITION_FOUND
;
896 * Needed byte is not contained in the item pointed to by the
897 * path. Set pos_in_item out of the item.
899 if (is_indirect_le_ih(p_le_ih
))
900 pos_in_item(search_path
) =
901 ih_item_len(p_le_ih
) / UNFM_P_SIZE
;
903 pos_in_item(search_path
) = ih_item_len(p_le_ih
);
905 return POSITION_NOT_FOUND
;
908 /* Compare given item and item pointed to by the path. */
909 int comp_items(const struct item_head
*stored_ih
, const struct treepath
*path
)
911 struct buffer_head
*bh
= PATH_PLAST_BUFFER(path
);
912 struct item_head
*ih
;
914 /* Last buffer at the path is not in the tree. */
915 if (!B_IS_IN_TREE(bh
))
918 /* Last path position is invalid. */
919 if (PATH_LAST_POSITION(path
) >= B_NR_ITEMS(bh
))
922 /* we need only to know, whether it is the same item */
923 ih
= tp_item_head(path
);
924 return memcmp(stored_ih
, ih
, IH_SIZE
);
927 /* prepare for delete or cut of direct item */
928 static inline int prepare_for_direct_item(struct treepath
*path
,
929 struct item_head
*le_ih
,
931 loff_t new_file_length
, int *cut_size
)
935 if (new_file_length
== max_reiserfs_offset(inode
)) {
936 /* item has to be deleted */
937 *cut_size
= -(IH_SIZE
+ ih_item_len(le_ih
));
940 /* new file gets truncated */
941 if (get_inode_item_key_version(inode
) == KEY_FORMAT_3_6
) {
942 round_len
= ROUND_UP(new_file_length
);
943 /* this was new_file_length < le_ih ... */
944 if (round_len
< le_ih_k_offset(le_ih
)) {
945 *cut_size
= -(IH_SIZE
+ ih_item_len(le_ih
));
946 return M_DELETE
; /* Delete this item. */
948 /* Calculate first position and size for cutting from item. */
949 pos_in_item(path
) = round_len
- (le_ih_k_offset(le_ih
) - 1);
950 *cut_size
= -(ih_item_len(le_ih
) - pos_in_item(path
));
952 return M_CUT
; /* Cut from this item. */
955 /* old file: items may have any length */
957 if (new_file_length
< le_ih_k_offset(le_ih
)) {
958 *cut_size
= -(IH_SIZE
+ ih_item_len(le_ih
));
959 return M_DELETE
; /* Delete this item. */
962 /* Calculate first position and size for cutting from item. */
963 *cut_size
= -(ih_item_len(le_ih
) -
965 new_file_length
+ 1 - le_ih_k_offset(le_ih
)));
966 return M_CUT
; /* Cut from this item. */
969 static inline int prepare_for_direntry_item(struct treepath
*path
,
970 struct item_head
*le_ih
,
972 loff_t new_file_length
,
975 if (le_ih_k_offset(le_ih
) == DOT_OFFSET
&&
976 new_file_length
== max_reiserfs_offset(inode
)) {
977 RFALSE(ih_entry_count(le_ih
) != 2,
978 "PAP-5220: incorrect empty directory item (%h)", le_ih
);
979 *cut_size
= -(IH_SIZE
+ ih_item_len(le_ih
));
980 /* Delete the directory item containing "." and ".." entry. */
984 if (ih_entry_count(le_ih
) == 1) {
986 * Delete the directory item such as there is one record only
989 *cut_size
= -(IH_SIZE
+ ih_item_len(le_ih
));
993 /* Cut one record from the directory item. */
996 entry_length(get_last_bh(path
), le_ih
, pos_in_item(path
)));
1000 #define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1)
1003 * If the path points to a directory or direct item, calculate mode
1004 * and the size cut, for balance.
1005 * If the path points to an indirect item, remove some number of its
1006 * unformatted nodes.
1007 * In case of file truncate calculate whether this item must be
1008 * deleted/truncated or last unformatted node of this item will be
1009 * converted to a direct item.
1010 * This function returns a determination of what balance mode the
1011 * calling function should employ.
1013 static char prepare_for_delete_or_cut(struct reiserfs_transaction_handle
*th
,
1014 struct inode
*inode
,
1015 struct treepath
*path
,
1016 const struct cpu_key
*item_key
,
1018 * Number of unformatted nodes
1019 * which were removed from end
1024 /* MAX_KEY_OFFSET in case of delete. */
1025 unsigned long long new_file_length
1028 struct super_block
*sb
= inode
->i_sb
;
1029 struct item_head
*p_le_ih
= tp_item_head(path
);
1030 struct buffer_head
*bh
= PATH_PLAST_BUFFER(path
);
1032 BUG_ON(!th
->t_trans_id
);
1034 /* Stat_data item. */
1035 if (is_statdata_le_ih(p_le_ih
)) {
1037 RFALSE(new_file_length
!= max_reiserfs_offset(inode
),
1038 "PAP-5210: mode must be M_DELETE");
1040 *cut_size
= -(IH_SIZE
+ ih_item_len(p_le_ih
));
1044 /* Directory item. */
1045 if (is_direntry_le_ih(p_le_ih
))
1046 return prepare_for_direntry_item(path
, p_le_ih
, inode
,
1051 if (is_direct_le_ih(p_le_ih
))
1052 return prepare_for_direct_item(path
, p_le_ih
, inode
,
1053 new_file_length
, cut_size
);
1055 /* Case of an indirect item. */
1057 int blk_size
= sb
->s_blocksize
;
1058 struct item_head s_ih
;
1064 if ( new_file_length
== max_reiserfs_offset (inode
) ) {
1066 * prepare_for_delete_or_cut() is called by
1067 * reiserfs_delete_item()
1069 new_file_length
= 0;
1076 bh
= PATH_PLAST_BUFFER(path
);
1077 copy_item_head(&s_ih
, tp_item_head(path
));
1078 pos
= I_UNFM_NUM(&s_ih
);
1080 while (le_ih_k_offset (&s_ih
) + (pos
- 1) * blk_size
> new_file_length
) {
1085 * Each unformatted block deletion may involve
1086 * one additional bitmap block into the transaction,
1087 * thereby the initial journal space reservation
1088 * might not be enough.
1090 if (!delete && (*cut_size
) != 0 &&
1091 reiserfs_transaction_free_space(th
) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD
)
1094 unfm
= (__le32
*)ih_item_body(bh
, &s_ih
) + pos
- 1;
1095 block
= get_block_num(unfm
, 0);
1098 reiserfs_prepare_for_journal(sb
, bh
, 1);
1099 put_block_num(unfm
, 0, 0);
1100 journal_mark_dirty(th
, bh
);
1101 reiserfs_free_block(th
, inode
, block
, 1);
1104 reiserfs_cond_resched(sb
);
1106 if (item_moved (&s_ih
, path
)) {
1113 (*cut_size
) -= UNFM_P_SIZE
;
1116 (*cut_size
) -= IH_SIZE
;
1122 * a trick. If the buffer has been logged, this will
1123 * do nothing. If we've broken the loop without logging
1124 * it, it will restore the buffer
1126 reiserfs_restore_prepared_buffer(sb
, bh
);
1127 } while (need_re_search
&&
1128 search_for_position_by_key(sb
, item_key
, path
) == POSITION_FOUND
);
1129 pos_in_item(path
) = pos
* UNFM_P_SIZE
;
1131 if (*cut_size
== 0) {
1133 * Nothing was cut. maybe convert last unformatted node to the
1142 /* Calculate number of bytes which will be deleted or cut during balance */
1143 static int calc_deleted_bytes_number(struct tree_balance
*tb
, char mode
)
1146 struct item_head
*p_le_ih
= tp_item_head(tb
->tb_path
);
1148 if (is_statdata_le_ih(p_le_ih
))
1153 M_DELETE
) ? ih_item_len(p_le_ih
) : -tb
->insert_size
[0];
1154 if (is_direntry_le_ih(p_le_ih
)) {
1156 * return EMPTY_DIR_SIZE; We delete emty directories only.
1157 * we can't use EMPTY_DIR_SIZE, as old format dirs have a
1158 * different empty size. ick. FIXME, is this right?
1163 if (is_indirect_le_ih(p_le_ih
))
1164 del_size
= (del_size
/ UNFM_P_SIZE
) *
1165 (PATH_PLAST_BUFFER(tb
->tb_path
)->b_size
);
1169 static void init_tb_struct(struct reiserfs_transaction_handle
*th
,
1170 struct tree_balance
*tb
,
1171 struct super_block
*sb
,
1172 struct treepath
*path
, int size
)
1175 BUG_ON(!th
->t_trans_id
);
1177 memset(tb
, '\0', sizeof(struct tree_balance
));
1178 tb
->transaction_handle
= th
;
1181 PATH_OFFSET_PBUFFER(path
, ILLEGAL_PATH_ELEMENT_OFFSET
) = NULL
;
1182 PATH_OFFSET_POSITION(path
, ILLEGAL_PATH_ELEMENT_OFFSET
) = 0;
1183 tb
->insert_size
[0] = size
;
1186 void padd_item(char *item
, int total_length
, int length
)
1190 for (i
= total_length
; i
> length
;)
1194 #ifdef REISERQUOTA_DEBUG
1195 char key2type(struct reiserfs_key
*ih
)
1197 if (is_direntry_le_key(2, ih
))
1199 if (is_direct_le_key(2, ih
))
1201 if (is_indirect_le_key(2, ih
))
1203 if (is_statdata_le_key(2, ih
))
1208 char head2type(struct item_head
*ih
)
1210 if (is_direntry_le_ih(ih
))
1212 if (is_direct_le_ih(ih
))
1214 if (is_indirect_le_ih(ih
))
1216 if (is_statdata_le_ih(ih
))
1223 * Delete object item.
1224 * th - active transaction handle
1225 * path - path to the deleted item
1226 * item_key - key to search for the deleted item
1227 * indode - used for updating i_blocks and quotas
1228 * un_bh - NULL or unformatted node pointer
1230 int reiserfs_delete_item(struct reiserfs_transaction_handle
*th
,
1231 struct treepath
*path
, const struct cpu_key
*item_key
,
1232 struct inode
*inode
, struct buffer_head
*un_bh
)
1234 struct super_block
*sb
= inode
->i_sb
;
1235 struct tree_balance s_del_balance
;
1236 struct item_head s_ih
;
1237 struct item_head
*q_ih
;
1238 int quota_cut_bytes
;
1239 int ret_value
, del_size
, removed
;
1242 #ifdef CONFIG_REISERFS_CHECK
1247 BUG_ON(!th
->t_trans_id
);
1249 init_tb_struct(th
, &s_del_balance
, sb
, path
,
1250 0 /*size is unknown */ );
1255 #ifdef CONFIG_REISERFS_CHECK
1259 prepare_for_delete_or_cut(th
, inode
, path
,
1262 max_reiserfs_offset(inode
));
1264 RFALSE(mode
!= M_DELETE
, "PAP-5320: mode must be M_DELETE");
1266 copy_item_head(&s_ih
, tp_item_head(path
));
1267 s_del_balance
.insert_size
[0] = del_size
;
1269 ret_value
= fix_nodes(M_DELETE
, &s_del_balance
, NULL
, NULL
);
1270 if (ret_value
!= REPEAT_SEARCH
)
1273 PROC_INFO_INC(sb
, delete_item_restarted
);
1275 /* file system changed, repeat search */
1277 search_for_position_by_key(sb
, item_key
, path
);
1278 if (ret_value
== IO_ERROR
)
1280 if (ret_value
== FILE_NOT_FOUND
) {
1281 reiserfs_warning(sb
, "vs-5340",
1282 "no items of the file %K found",
1288 if (ret_value
!= CARRY_ON
) {
1289 unfix_nodes(&s_del_balance
);
1293 /* reiserfs_delete_item returns item length when success */
1294 ret_value
= calc_deleted_bytes_number(&s_del_balance
, M_DELETE
);
1295 q_ih
= tp_item_head(path
);
1296 quota_cut_bytes
= ih_item_len(q_ih
);
1299 * hack so the quota code doesn't have to guess if the file has a
1300 * tail. On tail insert, we allocate quota for 1 unformatted node.
1301 * We test the offset because the tail might have been
1302 * split into multiple items, and we only want to decrement for
1303 * the unfm node once
1305 if (!S_ISLNK(inode
->i_mode
) && is_direct_le_ih(q_ih
)) {
1306 if ((le_ih_k_offset(q_ih
) & (sb
->s_blocksize
- 1)) == 1) {
1307 quota_cut_bytes
= sb
->s_blocksize
+ UNFM_P_SIZE
;
1309 quota_cut_bytes
= 0;
1318 * We are in direct2indirect conversion, so move tail contents
1319 * to the unformatted node
1322 * note, we do the copy before preparing the buffer because we
1323 * don't care about the contents of the unformatted node yet.
1324 * the only thing we really care about is the direct item's
1325 * data is in the unformatted node.
1327 * Otherwise, we would have to call
1328 * reiserfs_prepare_for_journal on the unformatted node,
1329 * which might schedule, meaning we'd have to loop all the
1330 * way back up to the start of the while loop.
1332 * The unformatted node must be dirtied later on. We can't be
1333 * sure here if the entire tail has been deleted yet.
1335 * un_bh is from the page cache (all unformatted nodes are
1336 * from the page cache) and might be a highmem page. So, we
1337 * can't use un_bh->b_data.
1341 data
= kmap_atomic(un_bh
->b_page
);
1342 off
= ((le_ih_k_offset(&s_ih
) - 1) & (PAGE_SIZE
- 1));
1344 ih_item_body(PATH_PLAST_BUFFER(path
), &s_ih
),
1346 kunmap_atomic(data
);
1349 /* Perform balancing after all resources have been collected at once. */
1350 do_balance(&s_del_balance
, NULL
, NULL
, M_DELETE
);
1352 #ifdef REISERQUOTA_DEBUG
1353 reiserfs_debug(sb
, REISERFS_DEBUG_CODE
,
1354 "reiserquota delete_item(): freeing %u, id=%u type=%c",
1355 quota_cut_bytes
, inode
->i_uid
, head2type(&s_ih
));
1357 depth
= reiserfs_write_unlock_nested(inode
->i_sb
);
1358 dquot_free_space_nodirty(inode
, quota_cut_bytes
);
1359 reiserfs_write_lock_nested(inode
->i_sb
, depth
);
1361 /* Return deleted body length */
1366 * Summary Of Mechanisms For Handling Collisions Between Processes:
1368 * deletion of the body of the object is performed by iput(), with the
1369 * result that if multiple processes are operating on a file, the
1370 * deletion of the body of the file is deferred until the last process
1371 * that has an open inode performs its iput().
1373 * writes and truncates are protected from collisions by use of
1376 * creates, linking, and mknod are protected from collisions with other
1377 * processes by making the reiserfs_add_entry() the last step in the
1378 * creation, and then rolling back all changes if there was a collision.
1382 /* this deletes item which never gets split */
1383 void reiserfs_delete_solid_item(struct reiserfs_transaction_handle
*th
,
1384 struct inode
*inode
, struct reiserfs_key
*key
)
1386 struct super_block
*sb
= th
->t_super
;
1387 struct tree_balance tb
;
1388 INITIALIZE_PATH(path
);
1391 struct cpu_key cpu_key
;
1393 int quota_cut_bytes
= 0;
1395 BUG_ON(!th
->t_trans_id
);
1397 le_key2cpu_key(&cpu_key
, key
);
1400 retval
= search_item(th
->t_super
, &cpu_key
, &path
);
1401 if (retval
== IO_ERROR
) {
1402 reiserfs_error(th
->t_super
, "vs-5350",
1403 "i/o failure occurred trying "
1404 "to delete %K", &cpu_key
);
1407 if (retval
!= ITEM_FOUND
) {
1410 * No need for a warning, if there is just no free
1411 * space to insert '..' item into the
1412 * newly-created subdir
1415 ((unsigned long long)
1416 GET_HASH_VALUE(le_key_k_offset
1417 (le_key_version(key
), key
)) == 0
1418 && (unsigned long long)
1419 GET_GENERATION_NUMBER(le_key_k_offset
1420 (le_key_version(key
),
1422 reiserfs_warning(th
->t_super
, "vs-5355",
1423 "%k not found", key
);
1428 item_len
= ih_item_len(tp_item_head(&path
));
1429 init_tb_struct(th
, &tb
, th
->t_super
, &path
,
1430 -(IH_SIZE
+ item_len
));
1432 quota_cut_bytes
= ih_item_len(tp_item_head(&path
));
1434 retval
= fix_nodes(M_DELETE
, &tb
, NULL
, NULL
);
1435 if (retval
== REPEAT_SEARCH
) {
1436 PROC_INFO_INC(th
->t_super
, delete_solid_item_restarted
);
1440 if (retval
== CARRY_ON
) {
1441 do_balance(&tb
, NULL
, NULL
, M_DELETE
);
1443 * Should we count quota for item? (we don't
1444 * count quotas for save-links)
1448 #ifdef REISERQUOTA_DEBUG
1449 reiserfs_debug(th
->t_super
, REISERFS_DEBUG_CODE
,
1450 "reiserquota delete_solid_item(): freeing %u id=%u type=%c",
1451 quota_cut_bytes
, inode
->i_uid
,
1454 depth
= reiserfs_write_unlock_nested(sb
);
1455 dquot_free_space_nodirty(inode
,
1457 reiserfs_write_lock_nested(sb
, depth
);
1462 /* IO_ERROR, NO_DISK_SPACE, etc */
1463 reiserfs_warning(th
->t_super
, "vs-5360",
1464 "could not delete %K due to fix_nodes failure",
1470 reiserfs_check_path(&path
);
1473 int reiserfs_delete_object(struct reiserfs_transaction_handle
*th
,
1474 struct inode
*inode
)
1478 BUG_ON(!th
->t_trans_id
);
1480 /* for directory this deletes item containing "." and ".." */
1482 reiserfs_do_truncate(th
, inode
, NULL
, 0 /*no timestamp updates */ );
1486 #if defined( USE_INODE_GENERATION_COUNTER )
1487 if (!old_format_only(th
->t_super
)) {
1488 __le32
*inode_generation
;
1491 &REISERFS_SB(th
->t_super
)->s_rs
->s_inode_generation
;
1492 le32_add_cpu(inode_generation
, 1);
1494 /* USE_INODE_GENERATION_COUNTER */
1496 reiserfs_delete_solid_item(th
, inode
, INODE_PKEY(inode
));
1501 static void unmap_buffers(struct page
*page
, loff_t pos
)
1503 struct buffer_head
*bh
;
1504 struct buffer_head
*head
;
1505 struct buffer_head
*next
;
1506 unsigned long tail_index
;
1507 unsigned long cur_index
;
1510 if (page_has_buffers(page
)) {
1511 tail_index
= pos
& (PAGE_SIZE
- 1);
1513 head
= page_buffers(page
);
1516 next
= bh
->b_this_page
;
1519 * we want to unmap the buffers that contain
1520 * the tail, and all the buffers after it
1521 * (since the tail must be at the end of the
1522 * file). We don't want to unmap file data
1523 * before the tail, since it might be dirty
1524 * and waiting to reach disk
1526 cur_index
+= bh
->b_size
;
1527 if (cur_index
> tail_index
) {
1528 reiserfs_unmap_buffer(bh
);
1531 } while (bh
!= head
);
1536 static int maybe_indirect_to_direct(struct reiserfs_transaction_handle
*th
,
1537 struct inode
*inode
,
1539 struct treepath
*path
,
1540 const struct cpu_key
*item_key
,
1541 loff_t new_file_size
, char *mode
)
1543 struct super_block
*sb
= inode
->i_sb
;
1544 int block_size
= sb
->s_blocksize
;
1546 BUG_ON(!th
->t_trans_id
);
1547 BUG_ON(new_file_size
!= inode
->i_size
);
1550 * the page being sent in could be NULL if there was an i/o error
1551 * reading in the last block. The user will hit problems trying to
1552 * read the file, but for now we just skip the indirect2direct
1554 if (atomic_read(&inode
->i_count
) > 1 ||
1555 !tail_has_to_be_packed(inode
) ||
1556 !page
|| (REISERFS_I(inode
)->i_flags
& i_nopack_mask
)) {
1557 /* leave tail in an unformatted node */
1558 *mode
= M_SKIP_BALANCING
;
1560 block_size
- (new_file_size
& (block_size
- 1));
1565 /* Perform the conversion to a direct_item. */
1566 return indirect2direct(th
, inode
, page
, path
, item_key
,
1567 new_file_size
, mode
);
1571 * we did indirect_to_direct conversion. And we have inserted direct
1572 * item successesfully, but there were no disk space to cut unfm
1573 * pointer being converted. Therefore we have to delete inserted
1576 static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle
*th
,
1577 struct inode
*inode
, struct treepath
*path
)
1579 struct cpu_key tail_key
;
1582 BUG_ON(!th
->t_trans_id
);
1584 make_cpu_key(&tail_key
, inode
, inode
->i_size
+ 1, TYPE_DIRECT
, 4);
1585 tail_key
.key_length
= 4;
1588 (cpu_key_k_offset(&tail_key
) & (inode
->i_sb
->s_blocksize
- 1)) - 1;
1590 /* look for the last byte of the tail */
1591 if (search_for_position_by_key(inode
->i_sb
, &tail_key
, path
) ==
1593 reiserfs_panic(inode
->i_sb
, "vs-5615",
1594 "found invalid item");
1595 RFALSE(path
->pos_in_item
!=
1596 ih_item_len(tp_item_head(path
)) - 1,
1597 "vs-5616: appended bytes found");
1598 PATH_LAST_POSITION(path
)--;
1601 reiserfs_delete_item(th
, path
, &tail_key
, inode
,
1602 NULL
/*unbh not needed */ );
1604 || removed
> tail_len
,
1605 "vs-5617: there was tail %d bytes, removed item length %d bytes",
1607 tail_len
-= removed
;
1608 set_cpu_key_k_offset(&tail_key
,
1609 cpu_key_k_offset(&tail_key
) - removed
);
1611 reiserfs_warning(inode
->i_sb
, "reiserfs-5091", "indirect_to_direct "
1612 "conversion has been rolled back due to "
1613 "lack of disk space");
1614 mark_inode_dirty(inode
);
1617 /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */
1618 int reiserfs_cut_from_item(struct reiserfs_transaction_handle
*th
,
1619 struct treepath
*path
,
1620 struct cpu_key
*item_key
,
1621 struct inode
*inode
,
1622 struct page
*page
, loff_t new_file_size
)
1624 struct super_block
*sb
= inode
->i_sb
;
1626 * Every function which is going to call do_balance must first
1627 * create a tree_balance structure. Then it must fill up this
1628 * structure by using the init_tb_struct and fix_nodes functions.
1629 * After that we can make tree balancing.
1631 struct tree_balance s_cut_balance
;
1632 struct item_head
*p_le_ih
;
1633 int cut_size
= 0; /* Amount to be cut. */
1634 int ret_value
= CARRY_ON
;
1635 int removed
= 0; /* Number of the removed unformatted nodes. */
1636 int is_inode_locked
= 0;
1637 char mode
; /* Mode of the balance. */
1639 int quota_cut_bytes
;
1640 loff_t tail_pos
= 0;
1643 BUG_ON(!th
->t_trans_id
);
1645 init_tb_struct(th
, &s_cut_balance
, inode
->i_sb
, path
,
1649 * Repeat this loop until we either cut the item without needing
1650 * to balance, or we fix_nodes without schedule occurring
1654 * Determine the balance mode, position of the first byte to
1655 * be cut, and size to be cut. In case of the indirect item
1656 * free unformatted nodes which are pointed to by the cut
1661 prepare_for_delete_or_cut(th
, inode
, path
,
1663 &cut_size
, new_file_size
);
1664 if (mode
== M_CONVERT
) {
1666 * convert last unformatted node to direct item or
1667 * leave tail in the unformatted node
1669 RFALSE(ret_value
!= CARRY_ON
,
1670 "PAP-5570: can not convert twice");
1673 maybe_indirect_to_direct(th
, inode
, page
,
1675 new_file_size
, &mode
);
1676 if (mode
== M_SKIP_BALANCING
)
1677 /* tail has been left in the unformatted node */
1680 is_inode_locked
= 1;
1683 * removing of last unformatted node will
1684 * change value we have to return to truncate.
1687 retval2
= ret_value
;
1690 * So, we have performed the first part of the
1692 * inserting the new direct item. Now we are
1693 * removing the last unformatted node pointer.
1694 * Set key to search for it.
1696 set_cpu_key_k_type(item_key
, TYPE_INDIRECT
);
1697 item_key
->key_length
= 4;
1699 (new_file_size
& (sb
->s_blocksize
- 1));
1700 tail_pos
= new_file_size
;
1701 set_cpu_key_k_offset(item_key
, new_file_size
+ 1);
1702 if (search_for_position_by_key
1704 path
) == POSITION_NOT_FOUND
) {
1705 print_block(PATH_PLAST_BUFFER(path
), 3,
1706 PATH_LAST_POSITION(path
) - 1,
1707 PATH_LAST_POSITION(path
) + 1);
1708 reiserfs_panic(sb
, "PAP-5580", "item to "
1709 "convert does not exist (%K)",
1714 if (cut_size
== 0) {
1719 s_cut_balance
.insert_size
[0] = cut_size
;
1721 ret_value
= fix_nodes(mode
, &s_cut_balance
, NULL
, NULL
);
1722 if (ret_value
!= REPEAT_SEARCH
)
1725 PROC_INFO_INC(sb
, cut_from_item_restarted
);
1728 search_for_position_by_key(sb
, item_key
, path
);
1729 if (ret_value
== POSITION_FOUND
)
1732 reiserfs_warning(sb
, "PAP-5610", "item %K not found",
1734 unfix_nodes(&s_cut_balance
);
1735 return (ret_value
== IO_ERROR
) ? -EIO
: -ENOENT
;
1738 /* check fix_nodes results (IO_ERROR or NO_DISK_SPACE) */
1739 if (ret_value
!= CARRY_ON
) {
1740 if (is_inode_locked
) {
1742 * FIXME: this seems to be not needed: we are always
1745 indirect_to_direct_roll_back(th
, inode
, path
);
1747 if (ret_value
== NO_DISK_SPACE
)
1748 reiserfs_warning(sb
, "reiserfs-5092",
1750 unfix_nodes(&s_cut_balance
);
1754 /* go ahead and perform balancing */
1756 RFALSE(mode
== M_PASTE
|| mode
== M_INSERT
, "invalid mode");
1758 /* Calculate number of bytes that need to be cut from the item. */
1761 M_DELETE
) ? ih_item_len(tp_item_head(path
)) : -s_cut_balance
.
1764 ret_value
= calc_deleted_bytes_number(&s_cut_balance
, mode
);
1766 ret_value
= retval2
;
1769 * For direct items, we only change the quota when deleting the last
1772 p_le_ih
= tp_item_head(s_cut_balance
.tb_path
);
1773 if (!S_ISLNK(inode
->i_mode
) && is_direct_le_ih(p_le_ih
)) {
1774 if (mode
== M_DELETE
&&
1775 (le_ih_k_offset(p_le_ih
) & (sb
->s_blocksize
- 1)) ==
1777 /* FIXME: this is to keep 3.5 happy */
1778 REISERFS_I(inode
)->i_first_direct_byte
= U32_MAX
;
1779 quota_cut_bytes
= sb
->s_blocksize
+ UNFM_P_SIZE
;
1781 quota_cut_bytes
= 0;
1784 #ifdef CONFIG_REISERFS_CHECK
1785 if (is_inode_locked
) {
1786 struct item_head
*le_ih
=
1787 tp_item_head(s_cut_balance
.tb_path
);
1789 * we are going to complete indirect2direct conversion. Make
1790 * sure, that we exactly remove last unformatted node pointer
1793 if (!is_indirect_le_ih(le_ih
))
1794 reiserfs_panic(sb
, "vs-5652",
1795 "item must be indirect %h", le_ih
);
1797 if (mode
== M_DELETE
&& ih_item_len(le_ih
) != UNFM_P_SIZE
)
1798 reiserfs_panic(sb
, "vs-5653", "completing "
1799 "indirect2direct conversion indirect "
1800 "item %h being deleted must be of "
1801 "4 byte long", le_ih
);
1804 && s_cut_balance
.insert_size
[0] != -UNFM_P_SIZE
) {
1805 reiserfs_panic(sb
, "vs-5654", "can not complete "
1806 "indirect2direct conversion of %h "
1807 "(CUT, insert_size==%d)",
1808 le_ih
, s_cut_balance
.insert_size
[0]);
1811 * it would be useful to make sure, that right neighboring
1812 * item is direct item of this file
1817 do_balance(&s_cut_balance
, NULL
, NULL
, mode
);
1818 if (is_inode_locked
) {
1820 * we've done an indirect->direct conversion. when the
1821 * data block was freed, it was removed from the list of
1822 * blocks that must be flushed before the transaction
1823 * commits, make sure to unmap and invalidate it
1825 unmap_buffers(page
, tail_pos
);
1826 REISERFS_I(inode
)->i_flags
&= ~i_pack_on_close_mask
;
1828 #ifdef REISERQUOTA_DEBUG
1829 reiserfs_debug(inode
->i_sb
, REISERFS_DEBUG_CODE
,
1830 "reiserquota cut_from_item(): freeing %u id=%u type=%c",
1831 quota_cut_bytes
, inode
->i_uid
, '?');
1833 depth
= reiserfs_write_unlock_nested(sb
);
1834 dquot_free_space_nodirty(inode
, quota_cut_bytes
);
1835 reiserfs_write_lock_nested(sb
, depth
);
1839 static void truncate_directory(struct reiserfs_transaction_handle
*th
,
1840 struct inode
*inode
)
1842 BUG_ON(!th
->t_trans_id
);
1844 reiserfs_error(inode
->i_sb
, "vs-5655", "link count != 0");
1846 set_le_key_k_offset(KEY_FORMAT_3_5
, INODE_PKEY(inode
), DOT_OFFSET
);
1847 set_le_key_k_type(KEY_FORMAT_3_5
, INODE_PKEY(inode
), TYPE_DIRENTRY
);
1848 reiserfs_delete_solid_item(th
, inode
, INODE_PKEY(inode
));
1849 reiserfs_update_sd(th
, inode
);
1850 set_le_key_k_offset(KEY_FORMAT_3_5
, INODE_PKEY(inode
), SD_OFFSET
);
1851 set_le_key_k_type(KEY_FORMAT_3_5
, INODE_PKEY(inode
), TYPE_STAT_DATA
);
1855 * Truncate file to the new size. Note, this must be called with a
1856 * transaction already started
1858 int reiserfs_do_truncate(struct reiserfs_transaction_handle
*th
,
1859 struct inode
*inode
, /* ->i_size contains new size */
1860 struct page
*page
, /* up to date for last block */
1862 * when it is called by file_release to convert
1863 * the tail - no timestamps should be updated
1865 int update_timestamps
1868 INITIALIZE_PATH(s_search_path
); /* Path to the current object item. */
1869 struct item_head
*p_le_ih
; /* Pointer to an item header. */
1871 /* Key to search for a previous file item. */
1872 struct cpu_key s_item_key
;
1873 loff_t file_size
, /* Old file size. */
1874 new_file_size
; /* New file size. */
1875 int deleted
; /* Number of deleted or truncated bytes. */
1879 BUG_ON(!th
->t_trans_id
);
1881 (S_ISREG(inode
->i_mode
) || S_ISDIR(inode
->i_mode
)
1882 || S_ISLNK(inode
->i_mode
)))
1885 /* deletion of directory - no need to update timestamps */
1886 if (S_ISDIR(inode
->i_mode
)) {
1887 truncate_directory(th
, inode
);
1891 /* Get new file size. */
1892 new_file_size
= inode
->i_size
;
1894 /* FIXME: note, that key type is unimportant here */
1895 make_cpu_key(&s_item_key
, inode
, max_reiserfs_offset(inode
),
1899 search_for_position_by_key(inode
->i_sb
, &s_item_key
,
1901 if (retval
== IO_ERROR
) {
1902 reiserfs_error(inode
->i_sb
, "vs-5657",
1903 "i/o failure occurred trying to truncate %K",
1908 if (retval
== POSITION_FOUND
|| retval
== FILE_NOT_FOUND
) {
1909 reiserfs_error(inode
->i_sb
, "PAP-5660",
1910 "wrong result %d of search for %K", retval
,
1917 s_search_path
.pos_in_item
--;
1919 /* Get real file size (total length of all file items) */
1920 p_le_ih
= tp_item_head(&s_search_path
);
1921 if (is_statdata_le_ih(p_le_ih
))
1924 loff_t offset
= le_ih_k_offset(p_le_ih
);
1926 op_bytes_number(p_le_ih
, inode
->i_sb
->s_blocksize
);
1929 * this may mismatch with real file size: if last direct item
1930 * had no padding zeros and last unformatted node had no free
1931 * space, this file would have this file size
1933 file_size
= offset
+ bytes
- 1;
1936 * are we doing a full truncate or delete, if so
1937 * kick in the reada code
1939 if (new_file_size
== 0)
1940 s_search_path
.reada
= PATH_READA
| PATH_READA_BACK
;
1942 if (file_size
== 0 || file_size
< new_file_size
) {
1943 goto update_and_out
;
1946 /* Update key to search for the last file item. */
1947 set_cpu_key_k_offset(&s_item_key
, file_size
);
1950 /* Cut or delete file item. */
1952 reiserfs_cut_from_item(th
, &s_search_path
, &s_item_key
,
1953 inode
, page
, new_file_size
);
1955 reiserfs_warning(inode
->i_sb
, "vs-5665",
1956 "reiserfs_cut_from_item failed");
1957 reiserfs_check_path(&s_search_path
);
1961 RFALSE(deleted
> file_size
,
1962 "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K",
1963 deleted
, file_size
, &s_item_key
);
1965 /* Change key to search the last file item. */
1966 file_size
-= deleted
;
1968 set_cpu_key_k_offset(&s_item_key
, file_size
);
1971 * While there are bytes to truncate and previous
1972 * file item is presented in the tree.
1976 * This loop could take a really long time, and could log
1977 * many more blocks than a transaction can hold. So, we do
1978 * a polite journal end here, and if the transaction needs
1979 * ending, we make sure the file is consistent before ending
1980 * the current trans and starting a new one
1982 if (journal_transaction_should_end(th
, 0) ||
1983 reiserfs_transaction_free_space(th
) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD
) {
1984 pathrelse(&s_search_path
);
1986 if (update_timestamps
) {
1987 inode
->i_mtime
= current_time(inode
);
1988 inode
->i_ctime
= current_time(inode
);
1990 reiserfs_update_sd(th
, inode
);
1992 err
= journal_end(th
);
1995 err
= journal_begin(th
, inode
->i_sb
,
1996 JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD
+ JOURNAL_PER_BALANCE_CNT
* 4) ;
1999 reiserfs_update_inode_transaction(inode
);
2001 } while (file_size
> ROUND_UP(new_file_size
) &&
2002 search_for_position_by_key(inode
->i_sb
, &s_item_key
,
2003 &s_search_path
) == POSITION_FOUND
);
2005 RFALSE(file_size
> ROUND_UP(new_file_size
),
2006 "PAP-5680: truncate did not finish: new_file_size %lld, current %lld, oid %d",
2007 new_file_size
, file_size
, s_item_key
.on_disk_key
.k_objectid
);
2010 if (update_timestamps
) {
2011 /* this is truncate, not file closing */
2012 inode
->i_mtime
= current_time(inode
);
2013 inode
->i_ctime
= current_time(inode
);
2015 reiserfs_update_sd(th
, inode
);
2018 pathrelse(&s_search_path
);
2022 #ifdef CONFIG_REISERFS_CHECK
2023 /* this makes sure, that we __append__, not overwrite or add holes */
2024 static void check_research_for_paste(struct treepath
*path
,
2025 const struct cpu_key
*key
)
2027 struct item_head
*found_ih
= tp_item_head(path
);
2029 if (is_direct_le_ih(found_ih
)) {
2030 if (le_ih_k_offset(found_ih
) +
2031 op_bytes_number(found_ih
,
2032 get_last_bh(path
)->b_size
) !=
2033 cpu_key_k_offset(key
)
2034 || op_bytes_number(found_ih
,
2035 get_last_bh(path
)->b_size
) !=
2037 reiserfs_panic(NULL
, "PAP-5720", "found direct item "
2038 "%h or position (%d) does not match "
2039 "to key %K", found_ih
,
2040 pos_in_item(path
), key
);
2042 if (is_indirect_le_ih(found_ih
)) {
2043 if (le_ih_k_offset(found_ih
) +
2044 op_bytes_number(found_ih
,
2045 get_last_bh(path
)->b_size
) !=
2046 cpu_key_k_offset(key
)
2047 || I_UNFM_NUM(found_ih
) != pos_in_item(path
)
2048 || get_ih_free_space(found_ih
) != 0)
2049 reiserfs_panic(NULL
, "PAP-5730", "found indirect "
2050 "item (%h) or position (%d) does not "
2051 "match to key (%K)",
2052 found_ih
, pos_in_item(path
), key
);
2055 #endif /* config reiserfs check */
2058 * Paste bytes to the existing item.
2059 * Returns bytes number pasted into the item.
2061 int reiserfs_paste_into_item(struct reiserfs_transaction_handle
*th
,
2062 /* Path to the pasted item. */
2063 struct treepath
*search_path
,
2064 /* Key to search for the needed item. */
2065 const struct cpu_key
*key
,
2066 /* Inode item belongs to */
2067 struct inode
*inode
,
2068 /* Pointer to the bytes to paste. */
2070 /* Size of pasted bytes. */
2073 struct super_block
*sb
= inode
->i_sb
;
2074 struct tree_balance s_paste_balance
;
2079 BUG_ON(!th
->t_trans_id
);
2081 fs_gen
= get_generation(inode
->i_sb
);
2083 #ifdef REISERQUOTA_DEBUG
2084 reiserfs_debug(inode
->i_sb
, REISERFS_DEBUG_CODE
,
2085 "reiserquota paste_into_item(): allocating %u id=%u type=%c",
2086 pasted_size
, inode
->i_uid
,
2087 key2type(&key
->on_disk_key
));
2090 depth
= reiserfs_write_unlock_nested(sb
);
2091 retval
= dquot_alloc_space_nodirty(inode
, pasted_size
);
2092 reiserfs_write_lock_nested(sb
, depth
);
2094 pathrelse(search_path
);
2097 init_tb_struct(th
, &s_paste_balance
, th
->t_super
, search_path
,
2099 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
2100 s_paste_balance
.key
= key
->on_disk_key
;
2103 /* DQUOT_* can schedule, must check before the fix_nodes */
2104 if (fs_changed(fs_gen
, inode
->i_sb
)) {
2109 fix_nodes(M_PASTE
, &s_paste_balance
, NULL
,
2110 body
)) == REPEAT_SEARCH
) {
2112 /* file system changed while we were in the fix_nodes */
2113 PROC_INFO_INC(th
->t_super
, paste_into_item_restarted
);
2115 search_for_position_by_key(th
->t_super
, key
,
2117 if (retval
== IO_ERROR
) {
2121 if (retval
== POSITION_FOUND
) {
2122 reiserfs_warning(inode
->i_sb
, "PAP-5710",
2123 "entry or pasted byte (%K) exists",
2128 #ifdef CONFIG_REISERFS_CHECK
2129 check_research_for_paste(search_path
, key
);
2134 * Perform balancing after all resources are collected by fix_nodes,
2135 * and accessing them will not risk triggering schedule.
2137 if (retval
== CARRY_ON
) {
2138 do_balance(&s_paste_balance
, NULL
/*ih */ , body
, M_PASTE
);
2141 retval
= (retval
== NO_DISK_SPACE
) ? -ENOSPC
: -EIO
;
2143 /* this also releases the path */
2144 unfix_nodes(&s_paste_balance
);
2145 #ifdef REISERQUOTA_DEBUG
2146 reiserfs_debug(inode
->i_sb
, REISERFS_DEBUG_CODE
,
2147 "reiserquota paste_into_item(): freeing %u id=%u type=%c",
2148 pasted_size
, inode
->i_uid
,
2149 key2type(&key
->on_disk_key
));
2151 depth
= reiserfs_write_unlock_nested(sb
);
2152 dquot_free_space_nodirty(inode
, pasted_size
);
2153 reiserfs_write_lock_nested(sb
, depth
);
2158 * Insert new item into the buffer at the path.
2159 * th - active transaction handle
2160 * path - path to the inserted item
2161 * ih - pointer to the item header to insert
2162 * body - pointer to the bytes to insert
2164 int reiserfs_insert_item(struct reiserfs_transaction_handle
*th
,
2165 struct treepath
*path
, const struct cpu_key
*key
,
2166 struct item_head
*ih
, struct inode
*inode
,
2169 struct tree_balance s_ins_balance
;
2172 int quota_bytes
= 0;
2174 BUG_ON(!th
->t_trans_id
);
2176 if (inode
) { /* Do we count quotas for item? */
2178 fs_gen
= get_generation(inode
->i_sb
);
2179 quota_bytes
= ih_item_len(ih
);
2182 * hack so the quota code doesn't have to guess
2183 * if the file has a tail, links are always tails,
2184 * so there's no guessing needed
2186 if (!S_ISLNK(inode
->i_mode
) && is_direct_le_ih(ih
))
2187 quota_bytes
= inode
->i_sb
->s_blocksize
+ UNFM_P_SIZE
;
2188 #ifdef REISERQUOTA_DEBUG
2189 reiserfs_debug(inode
->i_sb
, REISERFS_DEBUG_CODE
,
2190 "reiserquota insert_item(): allocating %u id=%u type=%c",
2191 quota_bytes
, inode
->i_uid
, head2type(ih
));
2194 * We can't dirty inode here. It would be immediately
2195 * written but appropriate stat item isn't inserted yet...
2197 depth
= reiserfs_write_unlock_nested(inode
->i_sb
);
2198 retval
= dquot_alloc_space_nodirty(inode
, quota_bytes
);
2199 reiserfs_write_lock_nested(inode
->i_sb
, depth
);
2205 init_tb_struct(th
, &s_ins_balance
, th
->t_super
, path
,
2206 IH_SIZE
+ ih_item_len(ih
));
2207 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
2208 s_ins_balance
.key
= key
->on_disk_key
;
2211 * DQUOT_* can schedule, must check to be sure calling
2214 if (inode
&& fs_changed(fs_gen
, inode
->i_sb
)) {
2219 fix_nodes(M_INSERT
, &s_ins_balance
, ih
,
2220 body
)) == REPEAT_SEARCH
) {
2222 /* file system changed while we were in the fix_nodes */
2223 PROC_INFO_INC(th
->t_super
, insert_item_restarted
);
2224 retval
= search_item(th
->t_super
, key
, path
);
2225 if (retval
== IO_ERROR
) {
2229 if (retval
== ITEM_FOUND
) {
2230 reiserfs_warning(th
->t_super
, "PAP-5760",
2231 "key %K already exists in the tree",
2238 /* make balancing after all resources will be collected at a time */
2239 if (retval
== CARRY_ON
) {
2240 do_balance(&s_ins_balance
, ih
, body
, M_INSERT
);
2244 retval
= (retval
== NO_DISK_SPACE
) ? -ENOSPC
: -EIO
;
2246 /* also releases the path */
2247 unfix_nodes(&s_ins_balance
);
2248 #ifdef REISERQUOTA_DEBUG
2250 reiserfs_debug(th
->t_super
, REISERFS_DEBUG_CODE
,
2251 "reiserquota insert_item(): freeing %u id=%u type=%c",
2252 quota_bytes
, inode
->i_uid
, head2type(ih
));
2255 int depth
= reiserfs_write_unlock_nested(inode
->i_sb
);
2256 dquot_free_space_nodirty(inode
, quota_bytes
);
2257 reiserfs_write_lock_nested(inode
->i_sb
, depth
);