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>
15 #include <linux/buffer_head.h>
16 #include <linux/quotaops.h>
18 /* Does the buffer contain a disk block which is in the tree. */
19 inline int B_IS_IN_TREE(const struct buffer_head
*bh
)
22 RFALSE(B_LEVEL(bh
) > MAX_HEIGHT
,
23 "PAP-1010: block (%b) has too big level (%z)", bh
, bh
);
25 return (B_LEVEL(bh
) != FREE_LEVEL
);
28 /* to get item head in le form */
29 inline void copy_item_head(struct item_head
*to
,
30 const struct item_head
*from
)
32 memcpy(to
, from
, IH_SIZE
);
36 * k1 is pointer to on-disk structure which is stored in little-endian
37 * form. k2 is pointer to cpu variable. For key of items of the same
38 * object this returns 0.
39 * Returns: -1 if key1 < key2
43 inline int comp_short_keys(const struct reiserfs_key
*le_key
,
44 const struct cpu_key
*cpu_key
)
47 n
= le32_to_cpu(le_key
->k_dir_id
);
48 if (n
< cpu_key
->on_disk_key
.k_dir_id
)
50 if (n
> cpu_key
->on_disk_key
.k_dir_id
)
52 n
= le32_to_cpu(le_key
->k_objectid
);
53 if (n
< cpu_key
->on_disk_key
.k_objectid
)
55 if (n
> cpu_key
->on_disk_key
.k_objectid
)
61 * k1 is pointer to on-disk structure which is stored in little-endian
62 * form. k2 is pointer to cpu variable.
63 * Compare keys using all 4 key fields.
64 * Returns: -1 if key1 < key2 0
65 * if key1 = key2 1 if key1 > key2
67 static inline int comp_keys(const struct reiserfs_key
*le_key
,
68 const struct cpu_key
*cpu_key
)
72 retval
= comp_short_keys(le_key
, cpu_key
);
75 if (le_key_k_offset(le_key_version(le_key
), le_key
) <
76 cpu_key_k_offset(cpu_key
))
78 if (le_key_k_offset(le_key_version(le_key
), le_key
) >
79 cpu_key_k_offset(cpu_key
))
82 if (cpu_key
->key_length
== 3)
85 /* this part is needed only when tail conversion is in progress */
86 if (le_key_k_type(le_key_version(le_key
), le_key
) <
87 cpu_key_k_type(cpu_key
))
90 if (le_key_k_type(le_key_version(le_key
), le_key
) >
91 cpu_key_k_type(cpu_key
))
97 inline int comp_short_le_keys(const struct reiserfs_key
*key1
,
98 const struct reiserfs_key
*key2
)
100 __u32
*k1_u32
, *k2_u32
;
101 int key_length
= REISERFS_SHORT_KEY_LEN
;
103 k1_u32
= (__u32
*) key1
;
104 k2_u32
= (__u32
*) key2
;
105 for (; key_length
--; ++k1_u32
, ++k2_u32
) {
106 if (le32_to_cpu(*k1_u32
) < le32_to_cpu(*k2_u32
))
108 if (le32_to_cpu(*k1_u32
) > le32_to_cpu(*k2_u32
))
114 inline void le_key2cpu_key(struct cpu_key
*to
, const struct reiserfs_key
*from
)
117 to
->on_disk_key
.k_dir_id
= le32_to_cpu(from
->k_dir_id
);
118 to
->on_disk_key
.k_objectid
= le32_to_cpu(from
->k_objectid
);
120 /* find out version of the key */
121 version
= le_key_version(from
);
122 to
->version
= version
;
123 to
->on_disk_key
.k_offset
= le_key_k_offset(version
, from
);
124 to
->on_disk_key
.k_type
= le_key_k_type(version
, from
);
128 * this does not say which one is bigger, it only returns 1 if keys
129 * are not equal, 0 otherwise
131 inline int comp_le_keys(const struct reiserfs_key
*k1
,
132 const struct reiserfs_key
*k2
)
134 return memcmp(k1
, k2
, sizeof(struct reiserfs_key
));
137 /**************************************************************************
138 * Binary search toolkit function *
139 * Search for an item in the array by the item key *
140 * Returns: 1 if found, 0 if not found; *
141 * *pos = number of the searched element if found, else the *
142 * number of the first element that is larger than key. *
143 **************************************************************************/
145 * For those not familiar with binary search: lbound is the leftmost item
146 * that it could be, rbound the rightmost item that it could be. We examine
147 * the item halfway between lbound and rbound, and that tells us either
148 * that we can increase lbound, or decrease rbound, or that we have found it,
149 * or if lbound <= rbound that there are no possible items, and we have not
150 * found it. With each examination we cut the number of possible items it
151 * could be by one more than half rounded down, or we find it.
153 static inline int bin_search(const void *key
, /* Key to search for. */
154 const void *base
, /* First item in the array. */
155 int num
, /* Number of items in the array. */
157 * Item size in the array. searched. Lest the
158 * reader be confused, note that this is crafted
159 * as a general function, and when it is applied
160 * specifically to the array of item headers in a
161 * node, width is actually the item header size
165 int *pos
/* Number of the searched for element. */
168 int rbound
, lbound
, j
;
170 for (j
= ((rbound
= num
- 1) + (lbound
= 0)) / 2;
171 lbound
<= rbound
; j
= (rbound
+ lbound
) / 2)
173 ((struct reiserfs_key
*)((char *)base
+ j
* width
),
174 (struct cpu_key
*)key
)) {
183 return ITEM_FOUND
; /* Key found in the array. */
187 * bin_search did not find given key, it returns position of key,
188 * that is minimal and greater than the given one.
191 return ITEM_NOT_FOUND
;
195 /* Minimal possible key. It is never in the tree. */
196 const struct reiserfs_key MIN_KEY
= { 0, 0, {{0, 0},} };
198 /* Maximal possible key. It is never in the tree. */
199 static const struct reiserfs_key MAX_KEY
= {
200 __constant_cpu_to_le32(0xffffffff),
201 __constant_cpu_to_le32(0xffffffff),
202 {{__constant_cpu_to_le32(0xffffffff),
203 __constant_cpu_to_le32(0xffffffff)},}
207 * Get delimiting key of the buffer by looking for it in the buffers in the
208 * path, starting from the bottom of the path, and going upwards. We must
209 * check the path's validity at each step. If the key is not in the path,
210 * there is no delimiting key in the tree (buffer is first or last buffer
211 * in tree), and in this case we return a special key, either MIN_KEY or
214 static inline const struct reiserfs_key
*get_lkey(const struct treepath
*chk_path
,
215 const struct super_block
*sb
)
217 int position
, path_offset
= chk_path
->path_length
;
218 struct buffer_head
*parent
;
220 RFALSE(path_offset
< FIRST_PATH_ELEMENT_OFFSET
,
221 "PAP-5010: invalid offset in the path");
223 /* While not higher in path than first element. */
224 while (path_offset
-- > FIRST_PATH_ELEMENT_OFFSET
) {
226 RFALSE(!buffer_uptodate
227 (PATH_OFFSET_PBUFFER(chk_path
, path_offset
)),
228 "PAP-5020: parent is not uptodate");
230 /* Parent at the path is not in the tree now. */
233 PATH_OFFSET_PBUFFER(chk_path
, path_offset
)))
235 /* Check whether position in the parent is correct. */
237 PATH_OFFSET_POSITION(chk_path
,
241 /* Check whether parent at the path really points to the child. */
242 if (B_N_CHILD_NUM(parent
, position
) !=
243 PATH_OFFSET_PBUFFER(chk_path
,
244 path_offset
+ 1)->b_blocknr
)
247 * Return delimiting key if position in the parent
248 * is not equal to zero.
251 return internal_key(parent
, position
- 1);
253 /* Return MIN_KEY if we are in the root of the buffer tree. */
254 if (PATH_OFFSET_PBUFFER(chk_path
, FIRST_PATH_ELEMENT_OFFSET
)->
255 b_blocknr
== SB_ROOT_BLOCK(sb
))
260 /* Get delimiting key of the buffer at the path and its right neighbor. */
261 inline const struct reiserfs_key
*get_rkey(const struct treepath
*chk_path
,
262 const struct super_block
*sb
)
264 int position
, path_offset
= chk_path
->path_length
;
265 struct buffer_head
*parent
;
267 RFALSE(path_offset
< FIRST_PATH_ELEMENT_OFFSET
,
268 "PAP-5030: invalid offset in the path");
270 while (path_offset
-- > FIRST_PATH_ELEMENT_OFFSET
) {
272 RFALSE(!buffer_uptodate
273 (PATH_OFFSET_PBUFFER(chk_path
, path_offset
)),
274 "PAP-5040: parent is not uptodate");
276 /* Parent at the path is not in the tree now. */
279 PATH_OFFSET_PBUFFER(chk_path
, path_offset
)))
281 /* Check whether position in the parent is correct. */
283 PATH_OFFSET_POSITION(chk_path
,
288 * Check whether parent at the path really points
291 if (B_N_CHILD_NUM(parent
, position
) !=
292 PATH_OFFSET_PBUFFER(chk_path
,
293 path_offset
+ 1)->b_blocknr
)
297 * Return delimiting key if position in the parent
298 * is not the last one.
300 if (position
!= B_NR_ITEMS(parent
))
301 return internal_key(parent
, position
);
304 /* Return MAX_KEY if we are in the root of the buffer tree. */
305 if (PATH_OFFSET_PBUFFER(chk_path
, FIRST_PATH_ELEMENT_OFFSET
)->
306 b_blocknr
== SB_ROOT_BLOCK(sb
))
312 * Check whether a key is contained in the tree rooted from a buffer at a path.
313 * This works by looking at the left and right delimiting keys for the buffer
314 * in the last path_element in the path. These delimiting keys are stored
315 * at least one level above that buffer in the tree. If the buffer is the
316 * first or last node in the tree order then one of the delimiting keys may
317 * be absent, and in this case get_lkey and get_rkey return a special key
318 * which is MIN_KEY or MAX_KEY.
320 static inline int key_in_buffer(
321 /* Path which should be checked. */
322 struct treepath
*chk_path
,
323 /* Key which should be checked. */
324 const struct cpu_key
*key
,
325 struct super_block
*sb
329 RFALSE(!key
|| chk_path
->path_length
< FIRST_PATH_ELEMENT_OFFSET
330 || chk_path
->path_length
> MAX_HEIGHT
,
331 "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)",
332 key
, chk_path
->path_length
);
333 RFALSE(!PATH_PLAST_BUFFER(chk_path
)->b_bdev
,
334 "PAP-5060: device must not be NODEV");
336 if (comp_keys(get_lkey(chk_path
, sb
), key
) == 1)
337 /* left delimiting key is bigger, that the key we look for */
339 /* if ( comp_keys(key, get_rkey(chk_path, sb)) != -1 ) */
340 if (comp_keys(get_rkey(chk_path
, sb
), key
) != 1)
341 /* key must be less than right delimitiing key */
346 int reiserfs_check_path(struct treepath
*p
)
348 RFALSE(p
->path_length
!= ILLEGAL_PATH_ELEMENT_OFFSET
,
349 "path not properly relsed");
354 * Drop the reference to each buffer in a path and restore
355 * dirty bits clean when preparing the buffer for the log.
356 * This version should only be called from fix_nodes()
358 void pathrelse_and_restore(struct super_block
*sb
,
359 struct treepath
*search_path
)
361 int path_offset
= search_path
->path_length
;
363 RFALSE(path_offset
< ILLEGAL_PATH_ELEMENT_OFFSET
,
364 "clm-4000: invalid path offset");
366 while (path_offset
> ILLEGAL_PATH_ELEMENT_OFFSET
) {
367 struct buffer_head
*bh
;
368 bh
= PATH_OFFSET_PBUFFER(search_path
, path_offset
--);
369 reiserfs_restore_prepared_buffer(sb
, bh
);
372 search_path
->path_length
= ILLEGAL_PATH_ELEMENT_OFFSET
;
375 /* Drop the reference to each buffer in a path */
376 void pathrelse(struct treepath
*search_path
)
378 int path_offset
= search_path
->path_length
;
380 RFALSE(path_offset
< ILLEGAL_PATH_ELEMENT_OFFSET
,
381 "PAP-5090: invalid path offset");
383 while (path_offset
> ILLEGAL_PATH_ELEMENT_OFFSET
)
384 brelse(PATH_OFFSET_PBUFFER(search_path
, path_offset
--));
386 search_path
->path_length
= ILLEGAL_PATH_ELEMENT_OFFSET
;
389 static int is_leaf(char *buf
, int blocksize
, struct buffer_head
*bh
)
391 struct block_head
*blkh
;
392 struct item_head
*ih
;
398 blkh
= (struct block_head
*)buf
;
399 if (blkh_level(blkh
) != DISK_LEAF_NODE_LEVEL
) {
400 reiserfs_warning(NULL
, "reiserfs-5080",
401 "this should be caught earlier");
405 nr
= blkh_nr_item(blkh
);
406 if (nr
< 1 || nr
> ((blocksize
- BLKH_SIZE
) / (IH_SIZE
+ MIN_ITEM_LEN
))) {
407 /* item number is too big or too small */
408 reiserfs_warning(NULL
, "reiserfs-5081",
409 "nr_item seems wrong: %z", bh
);
412 ih
= (struct item_head
*)(buf
+ BLKH_SIZE
) + nr
- 1;
413 used_space
= BLKH_SIZE
+ IH_SIZE
* nr
+ (blocksize
- ih_location(ih
));
415 /* free space does not match to calculated amount of use space */
416 if (used_space
!= blocksize
- blkh_free_space(blkh
)) {
417 reiserfs_warning(NULL
, "reiserfs-5082",
418 "free space seems wrong: %z", bh
);
422 * FIXME: it is_leaf will hit performance too much - we may have
426 /* check tables of item heads */
427 ih
= (struct item_head
*)(buf
+ BLKH_SIZE
);
428 prev_location
= blocksize
;
429 for (i
= 0; i
< nr
; i
++, ih
++) {
430 if (le_ih_k_type(ih
) == TYPE_ANY
) {
431 reiserfs_warning(NULL
, "reiserfs-5083",
432 "wrong item type for item %h",
436 if (ih_location(ih
) >= blocksize
437 || ih_location(ih
) < IH_SIZE
* nr
) {
438 reiserfs_warning(NULL
, "reiserfs-5084",
439 "item location seems wrong: %h",
443 if (ih_item_len(ih
) < 1
444 || ih_item_len(ih
) > MAX_ITEM_LEN(blocksize
)) {
445 reiserfs_warning(NULL
, "reiserfs-5085",
446 "item length seems wrong: %h",
450 if (prev_location
- ih_location(ih
) != ih_item_len(ih
)) {
451 reiserfs_warning(NULL
, "reiserfs-5086",
452 "item location seems wrong "
453 "(second one): %h", ih
);
456 prev_location
= ih_location(ih
);
459 /* one may imagine many more checks */
463 /* returns 1 if buf looks like an internal node, 0 otherwise */
464 static int is_internal(char *buf
, int blocksize
, struct buffer_head
*bh
)
466 struct block_head
*blkh
;
470 blkh
= (struct block_head
*)buf
;
471 nr
= blkh_level(blkh
);
472 if (nr
<= DISK_LEAF_NODE_LEVEL
|| nr
> MAX_HEIGHT
) {
473 /* this level is not possible for internal nodes */
474 reiserfs_warning(NULL
, "reiserfs-5087",
475 "this should be caught earlier");
479 nr
= blkh_nr_item(blkh
);
480 /* for internal which is not root we might check min number of keys */
481 if (nr
> (blocksize
- BLKH_SIZE
- DC_SIZE
) / (KEY_SIZE
+ DC_SIZE
)) {
482 reiserfs_warning(NULL
, "reiserfs-5088",
483 "number of key seems wrong: %z", bh
);
487 used_space
= BLKH_SIZE
+ KEY_SIZE
* nr
+ DC_SIZE
* (nr
+ 1);
488 if (used_space
!= blocksize
- blkh_free_space(blkh
)) {
489 reiserfs_warning(NULL
, "reiserfs-5089",
490 "free space seems wrong: %z", bh
);
494 /* one may imagine many more checks */
499 * make sure that bh contains formatted node of reiserfs tree of
502 static int is_tree_node(struct buffer_head
*bh
, int level
)
504 if (B_LEVEL(bh
) != level
) {
505 reiserfs_warning(NULL
, "reiserfs-5090", "node level %d does "
506 "not match to the expected one %d",
510 if (level
== DISK_LEAF_NODE_LEVEL
)
511 return is_leaf(bh
->b_data
, bh
->b_size
, bh
);
513 return is_internal(bh
->b_data
, bh
->b_size
, bh
);
516 #define SEARCH_BY_KEY_READA 16
519 * The function is NOT SCHEDULE-SAFE!
520 * It might unlock the write lock if we needed to wait for a block
521 * to be read. Note that in this case it won't recover the lock to avoid
522 * high contention resulting from too much lock requests, especially
523 * the caller (search_by_key) will perform other schedule-unsafe
524 * operations just after calling this function.
526 * @return depth of lock to be restored after read completes
528 static int search_by_key_reada(struct super_block
*s
,
529 struct buffer_head
**bh
,
530 b_blocknr_t
*b
, int num
)
535 for (i
= 0; i
< num
; i
++) {
536 bh
[i
] = sb_getblk(s
, b
[i
]);
539 * We are going to read some blocks on which we
540 * have a reference. It's safe, though we might be
541 * reading blocks concurrently changed if we release
542 * the lock. But it's still fine because we check later
543 * if the tree changed
545 for (j
= 0; j
< i
; j
++) {
547 * note, this needs attention if we are getting rid of the BKL
548 * you have to make sure the prepared bit isn't set on this
551 if (!buffer_uptodate(bh
[j
])) {
553 depth
= reiserfs_write_unlock_nested(s
);
554 ll_rw_block(READA
, 1, bh
+ j
);
562 * This function fills up the path from the root to the leaf as it
563 * descends the tree looking for the key. It uses reiserfs_bread to
564 * try to find buffers in the cache given their block number. If it
565 * does not find them in the cache it reads them from disk. For each
566 * node search_by_key finds using reiserfs_bread it then uses
567 * bin_search to look through that node. bin_search will find the
568 * position of the block_number of the next node if it is looking
569 * through an internal node. If it is looking through a leaf node
570 * bin_search will find the position of the item which has key either
571 * equal to given key, or which is the maximal key less than the given
572 * key. search_by_key returns a path that must be checked for the
573 * correctness of the top of the path but need not be checked for the
574 * correctness of the bottom of the path
577 * search_by_key - search for key (and item) in stree
579 * @key: pointer to key to search for
580 * @search_path: Allocated and initialized struct treepath; Returned filled
582 * @stop_level: How far down the tree to search, Use DISK_LEAF_NODE_LEVEL to
583 * stop at leaf level.
585 * The function is NOT SCHEDULE-SAFE!
587 int search_by_key(struct super_block
*sb
, const struct cpu_key
*key
,
588 struct treepath
*search_path
, int stop_level
)
590 b_blocknr_t block_number
;
592 struct buffer_head
*bh
;
593 struct path_element
*last_element
;
594 int node_level
, retval
;
595 int right_neighbor_of_leaf_node
;
597 struct buffer_head
*reada_bh
[SEARCH_BY_KEY_READA
];
598 b_blocknr_t reada_blocks
[SEARCH_BY_KEY_READA
];
601 #ifdef CONFIG_REISERFS_CHECK
602 int repeat_counter
= 0;
605 PROC_INFO_INC(sb
, search_by_key
);
608 * As we add each node to a path we increase its count. This means
609 * that we must be careful to release all nodes in a path before we
610 * either discard the path struct or re-use the path struct, as we
614 pathrelse(search_path
);
616 right_neighbor_of_leaf_node
= 0;
619 * With each iteration of this loop we search through the items in the
620 * current node, and calculate the next current node(next path element)
621 * for the next iteration of this loop..
623 block_number
= SB_ROOT_BLOCK(sb
);
627 #ifdef CONFIG_REISERFS_CHECK
628 if (!(++repeat_counter
% 50000))
629 reiserfs_warning(sb
, "PAP-5100",
630 "%s: there were %d iterations of "
631 "while loop looking for key %K",
632 current
->comm
, repeat_counter
,
636 /* prep path to have another element added to it. */
638 PATH_OFFSET_PELEMENT(search_path
,
639 ++search_path
->path_length
);
640 fs_gen
= get_generation(sb
);
643 * Read the next tree node, and set the last element
644 * in the path to have a pointer to it.
646 if ((bh
= last_element
->pe_buffer
=
647 sb_getblk(sb
, block_number
))) {
650 * We'll need to drop the lock if we encounter any
651 * buffers that need to be read. If all of them are
652 * already up to date, we don't need to drop the lock.
656 if (!buffer_uptodate(bh
) && reada_count
> 1)
657 depth
= search_by_key_reada(sb
, reada_bh
,
658 reada_blocks
, reada_count
);
660 if (!buffer_uptodate(bh
) && depth
== -1)
661 depth
= reiserfs_write_unlock_nested(sb
);
663 ll_rw_block(READ
, 1, &bh
);
667 reiserfs_write_lock_nested(sb
, depth
);
668 if (!buffer_uptodate(bh
))
672 search_path
->path_length
--;
673 pathrelse(search_path
);
677 if (expected_level
== -1)
678 expected_level
= SB_TREE_HEIGHT(sb
);
682 * It is possible that schedule occurred. We must check
683 * whether the key to search is still in the tree rooted
684 * from the current buffer. If not then repeat search
687 if (fs_changed(fs_gen
, sb
) &&
688 (!B_IS_IN_TREE(bh
) ||
689 B_LEVEL(bh
) != expected_level
||
690 !key_in_buffer(search_path
, key
, sb
))) {
691 PROC_INFO_INC(sb
, search_by_key_fs_changed
);
692 PROC_INFO_INC(sb
, search_by_key_restarted
);
694 sbk_restarted
[expected_level
- 1]);
695 pathrelse(search_path
);
698 * Get the root block number so that we can
699 * repeat the search starting from the root.
701 block_number
= SB_ROOT_BLOCK(sb
);
703 right_neighbor_of_leaf_node
= 0;
705 /* repeat search from the root */
710 * only check that the key is in the buffer if key is not
711 * equal to the MAX_KEY. Latter case is only possible in
712 * "finish_unfinished()" processing during mount.
714 RFALSE(comp_keys(&MAX_KEY
, key
) &&
715 !key_in_buffer(search_path
, key
, sb
),
716 "PAP-5130: key is not in the buffer");
717 #ifdef CONFIG_REISERFS_CHECK
718 if (REISERFS_SB(sb
)->cur_tb
) {
719 print_cur_tb("5140");
720 reiserfs_panic(sb
, "PAP-5140",
721 "schedule occurred in do_balance!");
726 * make sure, that the node contents look like a node of
729 if (!is_tree_node(bh
, expected_level
)) {
730 reiserfs_error(sb
, "vs-5150",
731 "invalid format found in block %ld. "
732 "Fsck?", bh
->b_blocknr
);
733 pathrelse(search_path
);
737 /* ok, we have acquired next formatted node in the tree */
738 node_level
= B_LEVEL(bh
);
740 PROC_INFO_BH_STAT(sb
, bh
, node_level
- 1);
742 RFALSE(node_level
< stop_level
,
743 "vs-5152: tree level (%d) is less than stop level (%d)",
744 node_level
, stop_level
);
746 retval
= bin_search(key
, item_head(bh
, 0),
749 DISK_LEAF_NODE_LEVEL
) ? IH_SIZE
:
751 &(last_element
->pe_position
));
752 if (node_level
== stop_level
) {
756 /* we are not in the stop level */
758 * item has been found, so we choose the pointer which
759 * is to the right of the found one
761 if (retval
== ITEM_FOUND
)
762 last_element
->pe_position
++;
765 * if item was not found we choose the position which is to
766 * the left of the found item. This requires no code,
767 * bin_search did it already.
771 * So we have chosen a position in the current node which is
772 * an internal node. Now we calculate child block number by
773 * position in the node.
776 B_N_CHILD_NUM(bh
, last_element
->pe_position
);
779 * if we are going to read leaf nodes, try for read
782 if ((search_path
->reada
& PATH_READA
) &&
783 node_level
== DISK_LEAF_NODE_LEVEL
+ 1) {
784 int pos
= last_element
->pe_position
;
785 int limit
= B_NR_ITEMS(bh
);
786 struct reiserfs_key
*le_key
;
788 if (search_path
->reada
& PATH_READA_BACK
)
790 while (reada_count
< SEARCH_BY_KEY_READA
) {
793 reada_blocks
[reada_count
++] =
794 B_N_CHILD_NUM(bh
, pos
);
795 if (search_path
->reada
& PATH_READA_BACK
)
801 * check to make sure we're in the same object
803 le_key
= internal_key(bh
, pos
);
804 if (le32_to_cpu(le_key
->k_objectid
) !=
805 key
->on_disk_key
.k_objectid
) {
814 * Form the path to an item and position in this item which contains
815 * file byte defined by key. If there is no such item
816 * corresponding to the key, we point the path to the item with
817 * maximal key less than key, and *pos_in_item is set to one
818 * past the last entry/byte in the item. If searching for entry in a
819 * directory item, and it is not found, *pos_in_item is set to one
820 * entry more than the entry with maximal key which is less than the
823 * Note that if there is no entry in this same node which is one more,
824 * then we point to an imaginary entry. for direct items, the
825 * position is in units of bytes, for indirect items the position is
826 * in units of blocknr entries, for directory items the position is in
827 * units of directory entries.
829 /* The function is NOT SCHEDULE-SAFE! */
830 int search_for_position_by_key(struct super_block
*sb
,
831 /* Key to search (cpu variable) */
832 const struct cpu_key
*p_cpu_key
,
833 /* Filled up by this function. */
834 struct treepath
*search_path
)
836 struct item_head
*p_le_ih
; /* pointer to on-disk structure */
838 loff_t item_offset
, offset
;
839 struct reiserfs_dir_entry de
;
842 /* If searching for directory entry. */
843 if (is_direntry_cpu_key(p_cpu_key
))
844 return search_by_entry_key(sb
, p_cpu_key
, search_path
,
847 /* If not searching for directory entry. */
849 /* If item is found. */
850 retval
= search_item(sb
, p_cpu_key
, search_path
);
851 if (retval
== IO_ERROR
)
853 if (retval
== ITEM_FOUND
) {
857 (PATH_PLAST_BUFFER(search_path
),
858 PATH_LAST_POSITION(search_path
))),
859 "PAP-5165: item length equals zero");
861 pos_in_item(search_path
) = 0;
862 return POSITION_FOUND
;
865 RFALSE(!PATH_LAST_POSITION(search_path
),
866 "PAP-5170: position equals zero");
868 /* Item is not found. Set path to the previous item. */
870 item_head(PATH_PLAST_BUFFER(search_path
),
871 --PATH_LAST_POSITION(search_path
));
872 blk_size
= sb
->s_blocksize
;
874 if (comp_short_keys(&(p_le_ih
->ih_key
), p_cpu_key
)) {
875 return FILE_NOT_FOUND
;
878 /* FIXME: quite ugly this far */
880 item_offset
= le_ih_k_offset(p_le_ih
);
881 offset
= cpu_key_k_offset(p_cpu_key
);
883 /* Needed byte is contained in the item pointed to by the path. */
884 if (item_offset
<= offset
&&
885 item_offset
+ op_bytes_number(p_le_ih
, blk_size
) > offset
) {
886 pos_in_item(search_path
) = offset
- item_offset
;
887 if (is_indirect_le_ih(p_le_ih
)) {
888 pos_in_item(search_path
) /= blk_size
;
890 return POSITION_FOUND
;
894 * Needed byte is not contained in the item pointed to by the
895 * path. Set pos_in_item out of the item.
897 if (is_indirect_le_ih(p_le_ih
))
898 pos_in_item(search_path
) =
899 ih_item_len(p_le_ih
) / UNFM_P_SIZE
;
901 pos_in_item(search_path
) = ih_item_len(p_le_ih
);
903 return POSITION_NOT_FOUND
;
906 /* Compare given item and item pointed to by the path. */
907 int comp_items(const struct item_head
*stored_ih
, const struct treepath
*path
)
909 struct buffer_head
*bh
= PATH_PLAST_BUFFER(path
);
910 struct item_head
*ih
;
912 /* Last buffer at the path is not in the tree. */
913 if (!B_IS_IN_TREE(bh
))
916 /* Last path position is invalid. */
917 if (PATH_LAST_POSITION(path
) >= B_NR_ITEMS(bh
))
920 /* we need only to know, whether it is the same item */
921 ih
= tp_item_head(path
);
922 return memcmp(stored_ih
, ih
, IH_SIZE
);
925 /* unformatted nodes are not logged anymore, ever. This is safe now */
926 #define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1)
928 /* block can not be forgotten as it is in I/O or held by someone */
929 #define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh)))
931 /* prepare for delete or cut of direct item */
932 static inline int prepare_for_direct_item(struct treepath
*path
,
933 struct item_head
*le_ih
,
935 loff_t new_file_length
, int *cut_size
)
939 if (new_file_length
== max_reiserfs_offset(inode
)) {
940 /* item has to be deleted */
941 *cut_size
= -(IH_SIZE
+ ih_item_len(le_ih
));
944 /* new file gets truncated */
945 if (get_inode_item_key_version(inode
) == KEY_FORMAT_3_6
) {
946 round_len
= ROUND_UP(new_file_length
);
947 /* this was new_file_length < le_ih ... */
948 if (round_len
< le_ih_k_offset(le_ih
)) {
949 *cut_size
= -(IH_SIZE
+ ih_item_len(le_ih
));
950 return M_DELETE
; /* Delete this item. */
952 /* Calculate first position and size for cutting from item. */
953 pos_in_item(path
) = round_len
- (le_ih_k_offset(le_ih
) - 1);
954 *cut_size
= -(ih_item_len(le_ih
) - pos_in_item(path
));
956 return M_CUT
; /* Cut from this item. */
959 /* old file: items may have any length */
961 if (new_file_length
< le_ih_k_offset(le_ih
)) {
962 *cut_size
= -(IH_SIZE
+ ih_item_len(le_ih
));
963 return M_DELETE
; /* Delete this item. */
966 /* Calculate first position and size for cutting from item. */
967 *cut_size
= -(ih_item_len(le_ih
) -
969 new_file_length
+ 1 - le_ih_k_offset(le_ih
)));
970 return M_CUT
; /* Cut from this item. */
973 static inline int prepare_for_direntry_item(struct treepath
*path
,
974 struct item_head
*le_ih
,
976 loff_t new_file_length
,
979 if (le_ih_k_offset(le_ih
) == DOT_OFFSET
&&
980 new_file_length
== max_reiserfs_offset(inode
)) {
981 RFALSE(ih_entry_count(le_ih
) != 2,
982 "PAP-5220: incorrect empty directory item (%h)", le_ih
);
983 *cut_size
= -(IH_SIZE
+ ih_item_len(le_ih
));
984 /* Delete the directory item containing "." and ".." entry. */
988 if (ih_entry_count(le_ih
) == 1) {
990 * Delete the directory item such as there is one record only
993 *cut_size
= -(IH_SIZE
+ ih_item_len(le_ih
));
997 /* Cut one record from the directory item. */
1000 entry_length(get_last_bh(path
), le_ih
, pos_in_item(path
)));
1004 #define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1)
1007 * If the path points to a directory or direct item, calculate mode
1008 * and the size cut, for balance.
1009 * If the path points to an indirect item, remove some number of its
1010 * unformatted nodes.
1011 * In case of file truncate calculate whether this item must be
1012 * deleted/truncated or last unformatted node of this item will be
1013 * converted to a direct item.
1014 * This function returns a determination of what balance mode the
1015 * calling function should employ.
1017 static char prepare_for_delete_or_cut(struct reiserfs_transaction_handle
*th
,
1018 struct inode
*inode
,
1019 struct treepath
*path
,
1020 const struct cpu_key
*item_key
,
1022 * Number of unformatted nodes
1023 * which were removed from end
1028 /* MAX_KEY_OFFSET in case of delete. */
1029 unsigned long long new_file_length
1032 struct super_block
*sb
= inode
->i_sb
;
1033 struct item_head
*p_le_ih
= tp_item_head(path
);
1034 struct buffer_head
*bh
= PATH_PLAST_BUFFER(path
);
1036 BUG_ON(!th
->t_trans_id
);
1038 /* Stat_data item. */
1039 if (is_statdata_le_ih(p_le_ih
)) {
1041 RFALSE(new_file_length
!= max_reiserfs_offset(inode
),
1042 "PAP-5210: mode must be M_DELETE");
1044 *cut_size
= -(IH_SIZE
+ ih_item_len(p_le_ih
));
1048 /* Directory item. */
1049 if (is_direntry_le_ih(p_le_ih
))
1050 return prepare_for_direntry_item(path
, p_le_ih
, inode
,
1055 if (is_direct_le_ih(p_le_ih
))
1056 return prepare_for_direct_item(path
, p_le_ih
, inode
,
1057 new_file_length
, cut_size
);
1059 /* Case of an indirect item. */
1061 int blk_size
= sb
->s_blocksize
;
1062 struct item_head s_ih
;
1068 if ( new_file_length
== max_reiserfs_offset (inode
) ) {
1070 * prepare_for_delete_or_cut() is called by
1071 * reiserfs_delete_item()
1073 new_file_length
= 0;
1080 bh
= PATH_PLAST_BUFFER(path
);
1081 copy_item_head(&s_ih
, tp_item_head(path
));
1082 pos
= I_UNFM_NUM(&s_ih
);
1084 while (le_ih_k_offset (&s_ih
) + (pos
- 1) * blk_size
> new_file_length
) {
1089 * Each unformatted block deletion may involve
1090 * one additional bitmap block into the transaction,
1091 * thereby the initial journal space reservation
1092 * might not be enough.
1094 if (!delete && (*cut_size
) != 0 &&
1095 reiserfs_transaction_free_space(th
) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD
)
1098 unfm
= (__le32
*)ih_item_body(bh
, &s_ih
) + pos
- 1;
1099 block
= get_block_num(unfm
, 0);
1102 reiserfs_prepare_for_journal(sb
, bh
, 1);
1103 put_block_num(unfm
, 0, 0);
1104 journal_mark_dirty(th
, sb
, bh
);
1105 reiserfs_free_block(th
, inode
, block
, 1);
1108 reiserfs_cond_resched(sb
);
1110 if (item_moved (&s_ih
, path
)) {
1117 (*cut_size
) -= UNFM_P_SIZE
;
1120 (*cut_size
) -= IH_SIZE
;
1126 * a trick. If the buffer has been logged, this will
1127 * do nothing. If we've broken the loop without logging
1128 * it, it will restore the buffer
1130 reiserfs_restore_prepared_buffer(sb
, bh
);
1131 } while (need_re_search
&&
1132 search_for_position_by_key(sb
, item_key
, path
) == POSITION_FOUND
);
1133 pos_in_item(path
) = pos
* UNFM_P_SIZE
;
1135 if (*cut_size
== 0) {
1137 * Nothing was cut. maybe convert last unformatted node to the
1146 /* Calculate number of bytes which will be deleted or cut during balance */
1147 static int calc_deleted_bytes_number(struct tree_balance
*tb
, char mode
)
1150 struct item_head
*p_le_ih
= tp_item_head(tb
->tb_path
);
1152 if (is_statdata_le_ih(p_le_ih
))
1157 M_DELETE
) ? ih_item_len(p_le_ih
) : -tb
->insert_size
[0];
1158 if (is_direntry_le_ih(p_le_ih
)) {
1160 * return EMPTY_DIR_SIZE; We delete emty directories only.
1161 * we can't use EMPTY_DIR_SIZE, as old format dirs have a
1162 * different empty size. ick. FIXME, is this right?
1167 if (is_indirect_le_ih(p_le_ih
))
1168 del_size
= (del_size
/ UNFM_P_SIZE
) *
1169 (PATH_PLAST_BUFFER(tb
->tb_path
)->b_size
);
1173 static void init_tb_struct(struct reiserfs_transaction_handle
*th
,
1174 struct tree_balance
*tb
,
1175 struct super_block
*sb
,
1176 struct treepath
*path
, int size
)
1179 BUG_ON(!th
->t_trans_id
);
1181 memset(tb
, '\0', sizeof(struct tree_balance
));
1182 tb
->transaction_handle
= th
;
1185 PATH_OFFSET_PBUFFER(path
, ILLEGAL_PATH_ELEMENT_OFFSET
) = NULL
;
1186 PATH_OFFSET_POSITION(path
, ILLEGAL_PATH_ELEMENT_OFFSET
) = 0;
1187 tb
->insert_size
[0] = size
;
1190 void padd_item(char *item
, int total_length
, int length
)
1194 for (i
= total_length
; i
> length
;)
1198 #ifdef REISERQUOTA_DEBUG
1199 char key2type(struct reiserfs_key
*ih
)
1201 if (is_direntry_le_key(2, ih
))
1203 if (is_direct_le_key(2, ih
))
1205 if (is_indirect_le_key(2, ih
))
1207 if (is_statdata_le_key(2, ih
))
1212 char head2type(struct item_head
*ih
)
1214 if (is_direntry_le_ih(ih
))
1216 if (is_direct_le_ih(ih
))
1218 if (is_indirect_le_ih(ih
))
1220 if (is_statdata_le_ih(ih
))
1227 * Delete object item.
1228 * th - active transaction handle
1229 * path - path to the deleted item
1230 * item_key - key to search for the deleted item
1231 * indode - used for updating i_blocks and quotas
1232 * un_bh - NULL or unformatted node pointer
1234 int reiserfs_delete_item(struct reiserfs_transaction_handle
*th
,
1235 struct treepath
*path
, const struct cpu_key
*item_key
,
1236 struct inode
*inode
, struct buffer_head
*un_bh
)
1238 struct super_block
*sb
= inode
->i_sb
;
1239 struct tree_balance s_del_balance
;
1240 struct item_head s_ih
;
1241 struct item_head
*q_ih
;
1242 int quota_cut_bytes
;
1243 int ret_value
, del_size
, removed
;
1246 #ifdef CONFIG_REISERFS_CHECK
1251 BUG_ON(!th
->t_trans_id
);
1253 init_tb_struct(th
, &s_del_balance
, sb
, path
,
1254 0 /*size is unknown */ );
1259 #ifdef CONFIG_REISERFS_CHECK
1263 prepare_for_delete_or_cut(th
, inode
, path
,
1266 max_reiserfs_offset(inode
));
1268 RFALSE(mode
!= M_DELETE
, "PAP-5320: mode must be M_DELETE");
1270 copy_item_head(&s_ih
, tp_item_head(path
));
1271 s_del_balance
.insert_size
[0] = del_size
;
1273 ret_value
= fix_nodes(M_DELETE
, &s_del_balance
, NULL
, NULL
);
1274 if (ret_value
!= REPEAT_SEARCH
)
1277 PROC_INFO_INC(sb
, delete_item_restarted
);
1279 /* file system changed, repeat search */
1281 search_for_position_by_key(sb
, item_key
, path
);
1282 if (ret_value
== IO_ERROR
)
1284 if (ret_value
== FILE_NOT_FOUND
) {
1285 reiserfs_warning(sb
, "vs-5340",
1286 "no items of the file %K found",
1292 if (ret_value
!= CARRY_ON
) {
1293 unfix_nodes(&s_del_balance
);
1297 /* reiserfs_delete_item returns item length when success */
1298 ret_value
= calc_deleted_bytes_number(&s_del_balance
, M_DELETE
);
1299 q_ih
= tp_item_head(path
);
1300 quota_cut_bytes
= ih_item_len(q_ih
);
1303 * hack so the quota code doesn't have to guess if the file has a
1304 * tail. On tail insert, we allocate quota for 1 unformatted node.
1305 * We test the offset because the tail might have been
1306 * split into multiple items, and we only want to decrement for
1307 * the unfm node once
1309 if (!S_ISLNK(inode
->i_mode
) && is_direct_le_ih(q_ih
)) {
1310 if ((le_ih_k_offset(q_ih
) & (sb
->s_blocksize
- 1)) == 1) {
1311 quota_cut_bytes
= sb
->s_blocksize
+ UNFM_P_SIZE
;
1313 quota_cut_bytes
= 0;
1322 * We are in direct2indirect conversion, so move tail contents
1323 * to the unformatted node
1326 * note, we do the copy before preparing the buffer because we
1327 * don't care about the contents of the unformatted node yet.
1328 * the only thing we really care about is the direct item's
1329 * data is in the unformatted node.
1331 * Otherwise, we would have to call
1332 * reiserfs_prepare_for_journal on the unformatted node,
1333 * which might schedule, meaning we'd have to loop all the
1334 * way back up to the start of the while loop.
1336 * The unformatted node must be dirtied later on. We can't be
1337 * sure here if the entire tail has been deleted yet.
1339 * un_bh is from the page cache (all unformatted nodes are
1340 * from the page cache) and might be a highmem page. So, we
1341 * can't use un_bh->b_data.
1345 data
= kmap_atomic(un_bh
->b_page
);
1346 off
= ((le_ih_k_offset(&s_ih
) - 1) & (PAGE_CACHE_SIZE
- 1));
1348 ih_item_body(PATH_PLAST_BUFFER(path
), &s_ih
),
1350 kunmap_atomic(data
);
1353 /* Perform balancing after all resources have been collected at once. */
1354 do_balance(&s_del_balance
, NULL
, NULL
, M_DELETE
);
1356 #ifdef REISERQUOTA_DEBUG
1357 reiserfs_debug(sb
, REISERFS_DEBUG_CODE
,
1358 "reiserquota delete_item(): freeing %u, id=%u type=%c",
1359 quota_cut_bytes
, inode
->i_uid
, head2type(&s_ih
));
1361 depth
= reiserfs_write_unlock_nested(inode
->i_sb
);
1362 dquot_free_space_nodirty(inode
, quota_cut_bytes
);
1363 reiserfs_write_lock_nested(inode
->i_sb
, depth
);
1365 /* Return deleted body length */
1370 * Summary Of Mechanisms For Handling Collisions Between Processes:
1372 * deletion of the body of the object is performed by iput(), with the
1373 * result that if multiple processes are operating on a file, the
1374 * deletion of the body of the file is deferred until the last process
1375 * that has an open inode performs its iput().
1377 * writes and truncates are protected from collisions by use of
1380 * creates, linking, and mknod are protected from collisions with other
1381 * processes by making the reiserfs_add_entry() the last step in the
1382 * creation, and then rolling back all changes if there was a collision.
1386 /* this deletes item which never gets split */
1387 void reiserfs_delete_solid_item(struct reiserfs_transaction_handle
*th
,
1388 struct inode
*inode
, struct reiserfs_key
*key
)
1390 struct super_block
*sb
= th
->t_super
;
1391 struct tree_balance tb
;
1392 INITIALIZE_PATH(path
);
1395 struct cpu_key cpu_key
;
1397 int quota_cut_bytes
= 0;
1399 BUG_ON(!th
->t_trans_id
);
1401 le_key2cpu_key(&cpu_key
, key
);
1404 retval
= search_item(th
->t_super
, &cpu_key
, &path
);
1405 if (retval
== IO_ERROR
) {
1406 reiserfs_error(th
->t_super
, "vs-5350",
1407 "i/o failure occurred trying "
1408 "to delete %K", &cpu_key
);
1411 if (retval
!= ITEM_FOUND
) {
1414 * No need for a warning, if there is just no free
1415 * space to insert '..' item into the
1416 * newly-created subdir
1419 ((unsigned long long)
1420 GET_HASH_VALUE(le_key_k_offset
1421 (le_key_version(key
), key
)) == 0
1422 && (unsigned long long)
1423 GET_GENERATION_NUMBER(le_key_k_offset
1424 (le_key_version(key
),
1426 reiserfs_warning(th
->t_super
, "vs-5355",
1427 "%k not found", key
);
1432 item_len
= ih_item_len(tp_item_head(&path
));
1433 init_tb_struct(th
, &tb
, th
->t_super
, &path
,
1434 -(IH_SIZE
+ item_len
));
1436 quota_cut_bytes
= ih_item_len(tp_item_head(&path
));
1438 retval
= fix_nodes(M_DELETE
, &tb
, NULL
, NULL
);
1439 if (retval
== REPEAT_SEARCH
) {
1440 PROC_INFO_INC(th
->t_super
, delete_solid_item_restarted
);
1444 if (retval
== CARRY_ON
) {
1445 do_balance(&tb
, NULL
, NULL
, M_DELETE
);
1447 * Should we count quota for item? (we don't
1448 * count quotas for save-links)
1452 #ifdef REISERQUOTA_DEBUG
1453 reiserfs_debug(th
->t_super
, REISERFS_DEBUG_CODE
,
1454 "reiserquota delete_solid_item(): freeing %u id=%u type=%c",
1455 quota_cut_bytes
, inode
->i_uid
,
1458 depth
= reiserfs_write_unlock_nested(sb
);
1459 dquot_free_space_nodirty(inode
,
1461 reiserfs_write_lock_nested(sb
, depth
);
1466 /* IO_ERROR, NO_DISK_SPACE, etc */
1467 reiserfs_warning(th
->t_super
, "vs-5360",
1468 "could not delete %K due to fix_nodes failure",
1474 reiserfs_check_path(&path
);
1477 int reiserfs_delete_object(struct reiserfs_transaction_handle
*th
,
1478 struct inode
*inode
)
1482 BUG_ON(!th
->t_trans_id
);
1484 /* for directory this deletes item containing "." and ".." */
1486 reiserfs_do_truncate(th
, inode
, NULL
, 0 /*no timestamp updates */ );
1490 #if defined( USE_INODE_GENERATION_COUNTER )
1491 if (!old_format_only(th
->t_super
)) {
1492 __le32
*inode_generation
;
1495 &REISERFS_SB(th
->t_super
)->s_rs
->s_inode_generation
;
1496 le32_add_cpu(inode_generation
, 1);
1498 /* USE_INODE_GENERATION_COUNTER */
1500 reiserfs_delete_solid_item(th
, inode
, INODE_PKEY(inode
));
1505 static void unmap_buffers(struct page
*page
, loff_t pos
)
1507 struct buffer_head
*bh
;
1508 struct buffer_head
*head
;
1509 struct buffer_head
*next
;
1510 unsigned long tail_index
;
1511 unsigned long cur_index
;
1514 if (page_has_buffers(page
)) {
1515 tail_index
= pos
& (PAGE_CACHE_SIZE
- 1);
1517 head
= page_buffers(page
);
1520 next
= bh
->b_this_page
;
1523 * we want to unmap the buffers that contain
1524 * the tail, and all the buffers after it
1525 * (since the tail must be at the end of the
1526 * file). We don't want to unmap file data
1527 * before the tail, since it might be dirty
1528 * and waiting to reach disk
1530 cur_index
+= bh
->b_size
;
1531 if (cur_index
> tail_index
) {
1532 reiserfs_unmap_buffer(bh
);
1535 } while (bh
!= head
);
1540 static int maybe_indirect_to_direct(struct reiserfs_transaction_handle
*th
,
1541 struct inode
*inode
,
1543 struct treepath
*path
,
1544 const struct cpu_key
*item_key
,
1545 loff_t new_file_size
, char *mode
)
1547 struct super_block
*sb
= inode
->i_sb
;
1548 int block_size
= sb
->s_blocksize
;
1550 BUG_ON(!th
->t_trans_id
);
1551 BUG_ON(new_file_size
!= inode
->i_size
);
1554 * the page being sent in could be NULL if there was an i/o error
1555 * reading in the last block. The user will hit problems trying to
1556 * read the file, but for now we just skip the indirect2direct
1558 if (atomic_read(&inode
->i_count
) > 1 ||
1559 !tail_has_to_be_packed(inode
) ||
1560 !page
|| (REISERFS_I(inode
)->i_flags
& i_nopack_mask
)) {
1561 /* leave tail in an unformatted node */
1562 *mode
= M_SKIP_BALANCING
;
1564 block_size
- (new_file_size
& (block_size
- 1));
1569 /* Perform the conversion to a direct_item. */
1570 return indirect2direct(th
, inode
, page
, path
, item_key
,
1571 new_file_size
, mode
);
1575 * we did indirect_to_direct conversion. And we have inserted direct
1576 * item successesfully, but there were no disk space to cut unfm
1577 * pointer being converted. Therefore we have to delete inserted
1580 static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle
*th
,
1581 struct inode
*inode
, struct treepath
*path
)
1583 struct cpu_key tail_key
;
1586 BUG_ON(!th
->t_trans_id
);
1588 make_cpu_key(&tail_key
, inode
, inode
->i_size
+ 1, TYPE_DIRECT
, 4);
1589 tail_key
.key_length
= 4;
1592 (cpu_key_k_offset(&tail_key
) & (inode
->i_sb
->s_blocksize
- 1)) - 1;
1594 /* look for the last byte of the tail */
1595 if (search_for_position_by_key(inode
->i_sb
, &tail_key
, path
) ==
1597 reiserfs_panic(inode
->i_sb
, "vs-5615",
1598 "found invalid item");
1599 RFALSE(path
->pos_in_item
!=
1600 ih_item_len(tp_item_head(path
)) - 1,
1601 "vs-5616: appended bytes found");
1602 PATH_LAST_POSITION(path
)--;
1605 reiserfs_delete_item(th
, path
, &tail_key
, inode
,
1606 NULL
/*unbh not needed */ );
1608 || removed
> tail_len
,
1609 "vs-5617: there was tail %d bytes, removed item length %d bytes",
1611 tail_len
-= removed
;
1612 set_cpu_key_k_offset(&tail_key
,
1613 cpu_key_k_offset(&tail_key
) - removed
);
1615 reiserfs_warning(inode
->i_sb
, "reiserfs-5091", "indirect_to_direct "
1616 "conversion has been rolled back due to "
1617 "lack of disk space");
1618 mark_inode_dirty(inode
);
1621 /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */
1622 int reiserfs_cut_from_item(struct reiserfs_transaction_handle
*th
,
1623 struct treepath
*path
,
1624 struct cpu_key
*item_key
,
1625 struct inode
*inode
,
1626 struct page
*page
, loff_t new_file_size
)
1628 struct super_block
*sb
= inode
->i_sb
;
1630 * Every function which is going to call do_balance must first
1631 * create a tree_balance structure. Then it must fill up this
1632 * structure by using the init_tb_struct and fix_nodes functions.
1633 * After that we can make tree balancing.
1635 struct tree_balance s_cut_balance
;
1636 struct item_head
*p_le_ih
;
1637 int cut_size
= 0; /* Amount to be cut. */
1638 int ret_value
= CARRY_ON
;
1639 int removed
= 0; /* Number of the removed unformatted nodes. */
1640 int is_inode_locked
= 0;
1641 char mode
; /* Mode of the balance. */
1643 int quota_cut_bytes
;
1644 loff_t tail_pos
= 0;
1647 BUG_ON(!th
->t_trans_id
);
1649 init_tb_struct(th
, &s_cut_balance
, inode
->i_sb
, path
,
1653 * Repeat this loop until we either cut the item without needing
1654 * to balance, or we fix_nodes without schedule occurring
1658 * Determine the balance mode, position of the first byte to
1659 * be cut, and size to be cut. In case of the indirect item
1660 * free unformatted nodes which are pointed to by the cut
1665 prepare_for_delete_or_cut(th
, inode
, path
,
1667 &cut_size
, new_file_size
);
1668 if (mode
== M_CONVERT
) {
1670 * convert last unformatted node to direct item or
1671 * leave tail in the unformatted node
1673 RFALSE(ret_value
!= CARRY_ON
,
1674 "PAP-5570: can not convert twice");
1677 maybe_indirect_to_direct(th
, inode
, page
,
1679 new_file_size
, &mode
);
1680 if (mode
== M_SKIP_BALANCING
)
1681 /* tail has been left in the unformatted node */
1684 is_inode_locked
= 1;
1687 * removing of last unformatted node will
1688 * change value we have to return to truncate.
1691 retval2
= ret_value
;
1694 * So, we have performed the first part of the
1696 * inserting the new direct item. Now we are
1697 * removing the last unformatted node pointer.
1698 * Set key to search for it.
1700 set_cpu_key_k_type(item_key
, TYPE_INDIRECT
);
1701 item_key
->key_length
= 4;
1703 (new_file_size
& (sb
->s_blocksize
- 1));
1704 tail_pos
= new_file_size
;
1705 set_cpu_key_k_offset(item_key
, new_file_size
+ 1);
1706 if (search_for_position_by_key
1708 path
) == POSITION_NOT_FOUND
) {
1709 print_block(PATH_PLAST_BUFFER(path
), 3,
1710 PATH_LAST_POSITION(path
) - 1,
1711 PATH_LAST_POSITION(path
) + 1);
1712 reiserfs_panic(sb
, "PAP-5580", "item to "
1713 "convert does not exist (%K)",
1718 if (cut_size
== 0) {
1723 s_cut_balance
.insert_size
[0] = cut_size
;
1725 ret_value
= fix_nodes(mode
, &s_cut_balance
, NULL
, NULL
);
1726 if (ret_value
!= REPEAT_SEARCH
)
1729 PROC_INFO_INC(sb
, cut_from_item_restarted
);
1732 search_for_position_by_key(sb
, item_key
, path
);
1733 if (ret_value
== POSITION_FOUND
)
1736 reiserfs_warning(sb
, "PAP-5610", "item %K not found",
1738 unfix_nodes(&s_cut_balance
);
1739 return (ret_value
== IO_ERROR
) ? -EIO
: -ENOENT
;
1742 /* check fix_nodes results (IO_ERROR or NO_DISK_SPACE) */
1743 if (ret_value
!= CARRY_ON
) {
1744 if (is_inode_locked
) {
1746 * FIXME: this seems to be not needed: we are always
1749 indirect_to_direct_roll_back(th
, inode
, path
);
1751 if (ret_value
== NO_DISK_SPACE
)
1752 reiserfs_warning(sb
, "reiserfs-5092",
1754 unfix_nodes(&s_cut_balance
);
1758 /* go ahead and perform balancing */
1760 RFALSE(mode
== M_PASTE
|| mode
== M_INSERT
, "invalid mode");
1762 /* Calculate number of bytes that need to be cut from the item. */
1765 M_DELETE
) ? ih_item_len(tp_item_head(path
)) : -s_cut_balance
.
1768 ret_value
= calc_deleted_bytes_number(&s_cut_balance
, mode
);
1770 ret_value
= retval2
;
1773 * For direct items, we only change the quota when deleting the last
1776 p_le_ih
= tp_item_head(s_cut_balance
.tb_path
);
1777 if (!S_ISLNK(inode
->i_mode
) && is_direct_le_ih(p_le_ih
)) {
1778 if (mode
== M_DELETE
&&
1779 (le_ih_k_offset(p_le_ih
) & (sb
->s_blocksize
- 1)) ==
1781 /* FIXME: this is to keep 3.5 happy */
1782 REISERFS_I(inode
)->i_first_direct_byte
= U32_MAX
;
1783 quota_cut_bytes
= sb
->s_blocksize
+ UNFM_P_SIZE
;
1785 quota_cut_bytes
= 0;
1788 #ifdef CONFIG_REISERFS_CHECK
1789 if (is_inode_locked
) {
1790 struct item_head
*le_ih
=
1791 tp_item_head(s_cut_balance
.tb_path
);
1793 * we are going to complete indirect2direct conversion. Make
1794 * sure, that we exactly remove last unformatted node pointer
1797 if (!is_indirect_le_ih(le_ih
))
1798 reiserfs_panic(sb
, "vs-5652",
1799 "item must be indirect %h", le_ih
);
1801 if (mode
== M_DELETE
&& ih_item_len(le_ih
) != UNFM_P_SIZE
)
1802 reiserfs_panic(sb
, "vs-5653", "completing "
1803 "indirect2direct conversion indirect "
1804 "item %h being deleted must be of "
1805 "4 byte long", le_ih
);
1808 && s_cut_balance
.insert_size
[0] != -UNFM_P_SIZE
) {
1809 reiserfs_panic(sb
, "vs-5654", "can not complete "
1810 "indirect2direct conversion of %h "
1811 "(CUT, insert_size==%d)",
1812 le_ih
, s_cut_balance
.insert_size
[0]);
1815 * it would be useful to make sure, that right neighboring
1816 * item is direct item of this file
1821 do_balance(&s_cut_balance
, NULL
, NULL
, mode
);
1822 if (is_inode_locked
) {
1824 * we've done an indirect->direct conversion. when the
1825 * data block was freed, it was removed from the list of
1826 * blocks that must be flushed before the transaction
1827 * commits, make sure to unmap and invalidate it
1829 unmap_buffers(page
, tail_pos
);
1830 REISERFS_I(inode
)->i_flags
&= ~i_pack_on_close_mask
;
1832 #ifdef REISERQUOTA_DEBUG
1833 reiserfs_debug(inode
->i_sb
, REISERFS_DEBUG_CODE
,
1834 "reiserquota cut_from_item(): freeing %u id=%u type=%c",
1835 quota_cut_bytes
, inode
->i_uid
, '?');
1837 depth
= reiserfs_write_unlock_nested(sb
);
1838 dquot_free_space_nodirty(inode
, quota_cut_bytes
);
1839 reiserfs_write_lock_nested(sb
, depth
);
1843 static void truncate_directory(struct reiserfs_transaction_handle
*th
,
1844 struct inode
*inode
)
1846 BUG_ON(!th
->t_trans_id
);
1848 reiserfs_error(inode
->i_sb
, "vs-5655", "link count != 0");
1850 set_le_key_k_offset(KEY_FORMAT_3_5
, INODE_PKEY(inode
), DOT_OFFSET
);
1851 set_le_key_k_type(KEY_FORMAT_3_5
, INODE_PKEY(inode
), TYPE_DIRENTRY
);
1852 reiserfs_delete_solid_item(th
, inode
, INODE_PKEY(inode
));
1853 reiserfs_update_sd(th
, inode
);
1854 set_le_key_k_offset(KEY_FORMAT_3_5
, INODE_PKEY(inode
), SD_OFFSET
);
1855 set_le_key_k_type(KEY_FORMAT_3_5
, INODE_PKEY(inode
), TYPE_STAT_DATA
);
1859 * Truncate file to the new size. Note, this must be called with a
1860 * transaction already started
1862 int reiserfs_do_truncate(struct reiserfs_transaction_handle
*th
,
1863 struct inode
*inode
, /* ->i_size contains new size */
1864 struct page
*page
, /* up to date for last block */
1866 * when it is called by file_release to convert
1867 * the tail - no timestamps should be updated
1869 int update_timestamps
1872 INITIALIZE_PATH(s_search_path
); /* Path to the current object item. */
1873 struct item_head
*p_le_ih
; /* Pointer to an item header. */
1875 /* Key to search for a previous file item. */
1876 struct cpu_key s_item_key
;
1877 loff_t file_size
, /* Old file size. */
1878 new_file_size
; /* New file size. */
1879 int deleted
; /* Number of deleted or truncated bytes. */
1883 BUG_ON(!th
->t_trans_id
);
1885 (S_ISREG(inode
->i_mode
) || S_ISDIR(inode
->i_mode
)
1886 || S_ISLNK(inode
->i_mode
)))
1889 /* deletion of directory - no need to update timestamps */
1890 if (S_ISDIR(inode
->i_mode
)) {
1891 truncate_directory(th
, inode
);
1895 /* Get new file size. */
1896 new_file_size
= inode
->i_size
;
1898 /* FIXME: note, that key type is unimportant here */
1899 make_cpu_key(&s_item_key
, inode
, max_reiserfs_offset(inode
),
1903 search_for_position_by_key(inode
->i_sb
, &s_item_key
,
1905 if (retval
== IO_ERROR
) {
1906 reiserfs_error(inode
->i_sb
, "vs-5657",
1907 "i/o failure occurred trying to truncate %K",
1912 if (retval
== POSITION_FOUND
|| retval
== FILE_NOT_FOUND
) {
1913 reiserfs_error(inode
->i_sb
, "PAP-5660",
1914 "wrong result %d of search for %K", retval
,
1921 s_search_path
.pos_in_item
--;
1923 /* Get real file size (total length of all file items) */
1924 p_le_ih
= tp_item_head(&s_search_path
);
1925 if (is_statdata_le_ih(p_le_ih
))
1928 loff_t offset
= le_ih_k_offset(p_le_ih
);
1930 op_bytes_number(p_le_ih
, inode
->i_sb
->s_blocksize
);
1933 * this may mismatch with real file size: if last direct item
1934 * had no padding zeros and last unformatted node had no free
1935 * space, this file would have this file size
1937 file_size
= offset
+ bytes
- 1;
1940 * are we doing a full truncate or delete, if so
1941 * kick in the reada code
1943 if (new_file_size
== 0)
1944 s_search_path
.reada
= PATH_READA
| PATH_READA_BACK
;
1946 if (file_size
== 0 || file_size
< new_file_size
) {
1947 goto update_and_out
;
1950 /* Update key to search for the last file item. */
1951 set_cpu_key_k_offset(&s_item_key
, file_size
);
1954 /* Cut or delete file item. */
1956 reiserfs_cut_from_item(th
, &s_search_path
, &s_item_key
,
1957 inode
, page
, new_file_size
);
1959 reiserfs_warning(inode
->i_sb
, "vs-5665",
1960 "reiserfs_cut_from_item failed");
1961 reiserfs_check_path(&s_search_path
);
1965 RFALSE(deleted
> file_size
,
1966 "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K",
1967 deleted
, file_size
, &s_item_key
);
1969 /* Change key to search the last file item. */
1970 file_size
-= deleted
;
1972 set_cpu_key_k_offset(&s_item_key
, file_size
);
1975 * While there are bytes to truncate and previous
1976 * file item is presented in the tree.
1980 * This loop could take a really long time, and could log
1981 * many more blocks than a transaction can hold. So, we do
1982 * a polite journal end here, and if the transaction needs
1983 * ending, we make sure the file is consistent before ending
1984 * the current trans and starting a new one
1986 if (journal_transaction_should_end(th
, 0) ||
1987 reiserfs_transaction_free_space(th
) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD
) {
1988 pathrelse(&s_search_path
);
1990 if (update_timestamps
) {
1991 inode
->i_mtime
= CURRENT_TIME_SEC
;
1992 inode
->i_ctime
= CURRENT_TIME_SEC
;
1994 reiserfs_update_sd(th
, inode
);
1996 err
= journal_end(th
, inode
->i_sb
);
1999 err
= journal_begin(th
, inode
->i_sb
,
2000 JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD
+ JOURNAL_PER_BALANCE_CNT
* 4) ;
2003 reiserfs_update_inode_transaction(inode
);
2005 } while (file_size
> ROUND_UP(new_file_size
) &&
2006 search_for_position_by_key(inode
->i_sb
, &s_item_key
,
2007 &s_search_path
) == POSITION_FOUND
);
2009 RFALSE(file_size
> ROUND_UP(new_file_size
),
2010 "PAP-5680: truncate did not finish: new_file_size %Ld, current %Ld, oid %d",
2011 new_file_size
, file_size
, s_item_key
.on_disk_key
.k_objectid
);
2014 if (update_timestamps
) {
2015 /* this is truncate, not file closing */
2016 inode
->i_mtime
= CURRENT_TIME_SEC
;
2017 inode
->i_ctime
= CURRENT_TIME_SEC
;
2019 reiserfs_update_sd(th
, inode
);
2022 pathrelse(&s_search_path
);
2026 #ifdef CONFIG_REISERFS_CHECK
2027 /* this makes sure, that we __append__, not overwrite or add holes */
2028 static void check_research_for_paste(struct treepath
*path
,
2029 const struct cpu_key
*key
)
2031 struct item_head
*found_ih
= tp_item_head(path
);
2033 if (is_direct_le_ih(found_ih
)) {
2034 if (le_ih_k_offset(found_ih
) +
2035 op_bytes_number(found_ih
,
2036 get_last_bh(path
)->b_size
) !=
2037 cpu_key_k_offset(key
)
2038 || op_bytes_number(found_ih
,
2039 get_last_bh(path
)->b_size
) !=
2041 reiserfs_panic(NULL
, "PAP-5720", "found direct item "
2042 "%h or position (%d) does not match "
2043 "to key %K", found_ih
,
2044 pos_in_item(path
), key
);
2046 if (is_indirect_le_ih(found_ih
)) {
2047 if (le_ih_k_offset(found_ih
) +
2048 op_bytes_number(found_ih
,
2049 get_last_bh(path
)->b_size
) !=
2050 cpu_key_k_offset(key
)
2051 || I_UNFM_NUM(found_ih
) != pos_in_item(path
)
2052 || get_ih_free_space(found_ih
) != 0)
2053 reiserfs_panic(NULL
, "PAP-5730", "found indirect "
2054 "item (%h) or position (%d) does not "
2055 "match to key (%K)",
2056 found_ih
, pos_in_item(path
), key
);
2059 #endif /* config reiserfs check */
2062 * Paste bytes to the existing item.
2063 * Returns bytes number pasted into the item.
2065 int reiserfs_paste_into_item(struct reiserfs_transaction_handle
*th
,
2066 /* Path to the pasted item. */
2067 struct treepath
*search_path
,
2068 /* Key to search for the needed item. */
2069 const struct cpu_key
*key
,
2070 /* Inode item belongs to */
2071 struct inode
*inode
,
2072 /* Pointer to the bytes to paste. */
2074 /* Size of pasted bytes. */
2077 struct super_block
*sb
= inode
->i_sb
;
2078 struct tree_balance s_paste_balance
;
2083 BUG_ON(!th
->t_trans_id
);
2085 fs_gen
= get_generation(inode
->i_sb
);
2087 #ifdef REISERQUOTA_DEBUG
2088 reiserfs_debug(inode
->i_sb
, REISERFS_DEBUG_CODE
,
2089 "reiserquota paste_into_item(): allocating %u id=%u type=%c",
2090 pasted_size
, inode
->i_uid
,
2091 key2type(&(key
->on_disk_key
)));
2094 depth
= reiserfs_write_unlock_nested(sb
);
2095 retval
= dquot_alloc_space_nodirty(inode
, pasted_size
);
2096 reiserfs_write_lock_nested(sb
, depth
);
2098 pathrelse(search_path
);
2101 init_tb_struct(th
, &s_paste_balance
, th
->t_super
, search_path
,
2103 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
2104 s_paste_balance
.key
= key
->on_disk_key
;
2107 /* DQUOT_* can schedule, must check before the fix_nodes */
2108 if (fs_changed(fs_gen
, inode
->i_sb
)) {
2113 fix_nodes(M_PASTE
, &s_paste_balance
, NULL
,
2114 body
)) == REPEAT_SEARCH
) {
2116 /* file system changed while we were in the fix_nodes */
2117 PROC_INFO_INC(th
->t_super
, paste_into_item_restarted
);
2119 search_for_position_by_key(th
->t_super
, key
,
2121 if (retval
== IO_ERROR
) {
2125 if (retval
== POSITION_FOUND
) {
2126 reiserfs_warning(inode
->i_sb
, "PAP-5710",
2127 "entry or pasted byte (%K) exists",
2132 #ifdef CONFIG_REISERFS_CHECK
2133 check_research_for_paste(search_path
, key
);
2138 * Perform balancing after all resources are collected by fix_nodes,
2139 * and accessing them will not risk triggering schedule.
2141 if (retval
== CARRY_ON
) {
2142 do_balance(&s_paste_balance
, NULL
/*ih */ , body
, M_PASTE
);
2145 retval
= (retval
== NO_DISK_SPACE
) ? -ENOSPC
: -EIO
;
2147 /* this also releases the path */
2148 unfix_nodes(&s_paste_balance
);
2149 #ifdef REISERQUOTA_DEBUG
2150 reiserfs_debug(inode
->i_sb
, REISERFS_DEBUG_CODE
,
2151 "reiserquota paste_into_item(): freeing %u id=%u type=%c",
2152 pasted_size
, inode
->i_uid
,
2153 key2type(&(key
->on_disk_key
)));
2155 depth
= reiserfs_write_unlock_nested(sb
);
2156 dquot_free_space_nodirty(inode
, pasted_size
);
2157 reiserfs_write_lock_nested(sb
, depth
);
2162 * Insert new item into the buffer at the path.
2163 * th - active transaction handle
2164 * path - path to the inserted item
2165 * ih - pointer to the item header to insert
2166 * body - pointer to the bytes to insert
2168 int reiserfs_insert_item(struct reiserfs_transaction_handle
*th
,
2169 struct treepath
*path
, const struct cpu_key
*key
,
2170 struct item_head
*ih
, struct inode
*inode
,
2173 struct tree_balance s_ins_balance
;
2176 int quota_bytes
= 0;
2178 BUG_ON(!th
->t_trans_id
);
2180 if (inode
) { /* Do we count quotas for item? */
2182 fs_gen
= get_generation(inode
->i_sb
);
2183 quota_bytes
= ih_item_len(ih
);
2186 * hack so the quota code doesn't have to guess
2187 * if the file has a tail, links are always tails,
2188 * so there's no guessing needed
2190 if (!S_ISLNK(inode
->i_mode
) && is_direct_le_ih(ih
))
2191 quota_bytes
= inode
->i_sb
->s_blocksize
+ UNFM_P_SIZE
;
2192 #ifdef REISERQUOTA_DEBUG
2193 reiserfs_debug(inode
->i_sb
, REISERFS_DEBUG_CODE
,
2194 "reiserquota insert_item(): allocating %u id=%u type=%c",
2195 quota_bytes
, inode
->i_uid
, head2type(ih
));
2198 * We can't dirty inode here. It would be immediately
2199 * written but appropriate stat item isn't inserted yet...
2201 depth
= reiserfs_write_unlock_nested(inode
->i_sb
);
2202 retval
= dquot_alloc_space_nodirty(inode
, quota_bytes
);
2203 reiserfs_write_lock_nested(inode
->i_sb
, depth
);
2209 init_tb_struct(th
, &s_ins_balance
, th
->t_super
, path
,
2210 IH_SIZE
+ ih_item_len(ih
));
2211 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
2212 s_ins_balance
.key
= key
->on_disk_key
;
2215 * DQUOT_* can schedule, must check to be sure calling
2218 if (inode
&& fs_changed(fs_gen
, inode
->i_sb
)) {
2223 fix_nodes(M_INSERT
, &s_ins_balance
, ih
,
2224 body
)) == REPEAT_SEARCH
) {
2226 /* file system changed while we were in the fix_nodes */
2227 PROC_INFO_INC(th
->t_super
, insert_item_restarted
);
2228 retval
= search_item(th
->t_super
, key
, path
);
2229 if (retval
== IO_ERROR
) {
2233 if (retval
== ITEM_FOUND
) {
2234 reiserfs_warning(th
->t_super
, "PAP-5760",
2235 "key %K already exists in the tree",
2242 /* make balancing after all resources will be collected at a time */
2243 if (retval
== CARRY_ON
) {
2244 do_balance(&s_ins_balance
, ih
, body
, M_INSERT
);
2248 retval
= (retval
== NO_DISK_SPACE
) ? -ENOSPC
: -EIO
;
2250 /* also releases the path */
2251 unfix_nodes(&s_ins_balance
);
2252 #ifdef REISERQUOTA_DEBUG
2253 reiserfs_debug(th
->t_super
, REISERFS_DEBUG_CODE
,
2254 "reiserquota insert_item(): freeing %u id=%u type=%c",
2255 quota_bytes
, inode
->i_uid
, head2type(ih
));
2258 int depth
= reiserfs_write_unlock_nested(inode
->i_sb
);
2259 dquot_free_space_nodirty(inode
, quota_bytes
);
2260 reiserfs_write_lock_nested(inode
->i_sb
, depth
);