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 cpu_to_le32(0xffffffff),
201 cpu_to_le32(0xffffffff),
202 {{cpu_to_le32(0xffffffff),
203 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 has_valid_deh_location(struct buffer_head *bh, struct item_head *ih)
391 struct reiserfs_de_head *deh;
394 deh = B_I_DEH(bh, ih);
395 for (i = 0; i < ih_entry_count(ih); i++) {
396 if (deh_location(&deh[i]) > ih_item_len(ih)) {
397 reiserfs_warning(NULL, "reiserfs-5094",
398 "directory entry location seems wrong %h",
407 static int is_leaf(char *buf, int blocksize, struct buffer_head *bh)
409 struct block_head *blkh;
410 struct item_head *ih;
416 blkh = (struct block_head *)buf;
417 if (blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) {
418 reiserfs_warning(NULL, "reiserfs-5080",
419 "this should be caught earlier");
423 nr = blkh_nr_item(blkh);
424 if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) {
425 /* item number is too big or too small */
426 reiserfs_warning(NULL, "reiserfs-5081",
427 "nr_item seems wrong: %z", bh);
430 ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1;
431 used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location(ih));
433 /* free space does not match to calculated amount of use space */
434 if (used_space != blocksize - blkh_free_space(blkh)) {
435 reiserfs_warning(NULL, "reiserfs-5082",
436 "free space seems wrong: %z", bh);
440 * FIXME: it is_leaf will hit performance too much - we may have
444 /* check tables of item heads */
445 ih = (struct item_head *)(buf + BLKH_SIZE);
446 prev_location = blocksize;
447 for (i = 0; i < nr; i++, ih++) {
448 if (le_ih_k_type(ih) == TYPE_ANY) {
449 reiserfs_warning(NULL, "reiserfs-5083",
450 "wrong item type for item %h",
454 if (ih_location(ih) >= blocksize
455 || ih_location(ih) < IH_SIZE * nr) {
456 reiserfs_warning(NULL, "reiserfs-5084",
457 "item location seems wrong: %h",
461 if (ih_item_len(ih) < 1
462 || ih_item_len(ih) > MAX_ITEM_LEN(blocksize)) {
463 reiserfs_warning(NULL, "reiserfs-5085",
464 "item length seems wrong: %h",
468 if (prev_location - ih_location(ih) != ih_item_len(ih)) {
469 reiserfs_warning(NULL, "reiserfs-5086",
470 "item location seems wrong "
471 "(second one): %h", ih);
474 if (is_direntry_le_ih(ih)) {
475 if (ih_item_len(ih) < (ih_entry_count(ih) * IH_SIZE)) {
476 reiserfs_warning(NULL, "reiserfs-5093",
477 "item entry count seems wrong %h",
481 return has_valid_deh_location(bh, ih);
483 prev_location = ih_location(ih);
486 /* one may imagine many more checks */
490 /* returns 1 if buf looks like an internal node, 0 otherwise */
491 static int is_internal(char *buf, int blocksize, struct buffer_head *bh)
493 struct block_head *blkh;
497 blkh = (struct block_head *)buf;
498 nr = blkh_level(blkh);
499 if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) {
500 /* this level is not possible for internal nodes */
501 reiserfs_warning(NULL, "reiserfs-5087",
502 "this should be caught earlier");
506 nr = blkh_nr_item(blkh);
507 /* for internal which is not root we might check min number of keys */
508 if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) {
509 reiserfs_warning(NULL, "reiserfs-5088",
510 "number of key seems wrong: %z", bh);
514 used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1);
515 if (used_space != blocksize - blkh_free_space(blkh)) {
516 reiserfs_warning(NULL, "reiserfs-5089",
517 "free space seems wrong: %z", bh);
521 /* one may imagine many more checks */
526 * make sure that bh contains formatted node of reiserfs tree of
529 static int is_tree_node(struct buffer_head *bh, int level)
531 if (B_LEVEL(bh) != level) {
532 reiserfs_warning(NULL, "reiserfs-5090", "node level %d does "
533 "not match to the expected one %d",
537 if (level == DISK_LEAF_NODE_LEVEL)
538 return is_leaf(bh->b_data, bh->b_size, bh);
540 return is_internal(bh->b_data, bh->b_size, bh);
543 #define SEARCH_BY_KEY_READA 16
546 * The function is NOT SCHEDULE-SAFE!
547 * It might unlock the write lock if we needed to wait for a block
548 * to be read. Note that in this case it won't recover the lock to avoid
549 * high contention resulting from too much lock requests, especially
550 * the caller (search_by_key) will perform other schedule-unsafe
551 * operations just after calling this function.
553 * @return depth of lock to be restored after read completes
555 static int search_by_key_reada(struct super_block *s,
556 struct buffer_head **bh,
557 b_blocknr_t *b, int num)
562 for (i = 0; i < num; i++) {
563 bh[i] = sb_getblk(s, b[i]);
566 * We are going to read some blocks on which we
567 * have a reference. It's safe, though we might be
568 * reading blocks concurrently changed if we release
569 * the lock. But it's still fine because we check later
570 * if the tree changed
572 for (j = 0; j < i; j++) {
574 * note, this needs attention if we are getting rid of the BKL
575 * you have to make sure the prepared bit isn't set on this
578 if (!buffer_uptodate(bh[j])) {
580 depth = reiserfs_write_unlock_nested(s);
581 ll_rw_block(READA, 1, bh + j);
589 * This function fills up the path from the root to the leaf as it
590 * descends the tree looking for the key. It uses reiserfs_bread to
591 * try to find buffers in the cache given their block number. If it
592 * does not find them in the cache it reads them from disk. For each
593 * node search_by_key finds using reiserfs_bread it then uses
594 * bin_search to look through that node. bin_search will find the
595 * position of the block_number of the next node if it is looking
596 * through an internal node. If it is looking through a leaf node
597 * bin_search will find the position of the item which has key either
598 * equal to given key, or which is the maximal key less than the given
599 * key. search_by_key returns a path that must be checked for the
600 * correctness of the top of the path but need not be checked for the
601 * correctness of the bottom of the path
604 * search_by_key - search for key (and item) in stree
606 * @key: pointer to key to search for
607 * @search_path: Allocated and initialized struct treepath; Returned filled
609 * @stop_level: How far down the tree to search, Use DISK_LEAF_NODE_LEVEL to
610 * stop at leaf level.
612 * The function is NOT SCHEDULE-SAFE!
614 int search_by_key(struct super_block *sb, const struct cpu_key *key,
615 struct treepath *search_path, int stop_level)
617 b_blocknr_t block_number;
619 struct buffer_head *bh;
620 struct path_element *last_element;
621 int node_level, retval;
622 int right_neighbor_of_leaf_node;
624 struct buffer_head *reada_bh[SEARCH_BY_KEY_READA];
625 b_blocknr_t reada_blocks[SEARCH_BY_KEY_READA];
628 #ifdef CONFIG_REISERFS_CHECK
629 int repeat_counter = 0;
632 PROC_INFO_INC(sb, search_by_key);
635 * As we add each node to a path we increase its count. This means
636 * that we must be careful to release all nodes in a path before we
637 * either discard the path struct or re-use the path struct, as we
641 pathrelse(search_path);
643 right_neighbor_of_leaf_node = 0;
646 * With each iteration of this loop we search through the items in the
647 * current node, and calculate the next current node(next path element)
648 * for the next iteration of this loop..
650 block_number = SB_ROOT_BLOCK(sb);
654 #ifdef CONFIG_REISERFS_CHECK
655 if (!(++repeat_counter % 50000))
656 reiserfs_warning(sb, "PAP-5100",
657 "%s: there were %d iterations of "
658 "while loop looking for key %K",
659 current->comm, repeat_counter,
663 /* prep path to have another element added to it. */
665 PATH_OFFSET_PELEMENT(search_path,
666 ++search_path->path_length);
667 fs_gen = get_generation(sb);
670 * Read the next tree node, and set the last element
671 * in the path to have a pointer to it.
673 if ((bh = last_element->pe_buffer =
674 sb_getblk(sb, block_number))) {
677 * We'll need to drop the lock if we encounter any
678 * buffers that need to be read. If all of them are
679 * already up to date, we don't need to drop the lock.
683 if (!buffer_uptodate(bh) && reada_count > 1)
684 depth = search_by_key_reada(sb, reada_bh,
685 reada_blocks, reada_count);
687 if (!buffer_uptodate(bh) && depth == -1)
688 depth = reiserfs_write_unlock_nested(sb);
690 ll_rw_block(READ, 1, &bh);
694 reiserfs_write_lock_nested(sb, depth);
695 if (!buffer_uptodate(bh))
699 search_path->path_length--;
700 pathrelse(search_path);
704 if (expected_level == -1)
705 expected_level = SB_TREE_HEIGHT(sb);
709 * It is possible that schedule occurred. We must check
710 * whether the key to search is still in the tree rooted
711 * from the current buffer. If not then repeat search
714 if (fs_changed(fs_gen, sb) &&
715 (!B_IS_IN_TREE(bh) ||
716 B_LEVEL(bh) != expected_level ||
717 !key_in_buffer(search_path, key, sb))) {
718 PROC_INFO_INC(sb, search_by_key_fs_changed);
719 PROC_INFO_INC(sb, search_by_key_restarted);
721 sbk_restarted[expected_level - 1]);
722 pathrelse(search_path);
725 * Get the root block number so that we can
726 * repeat the search starting from the root.
728 block_number = SB_ROOT_BLOCK(sb);
730 right_neighbor_of_leaf_node = 0;
732 /* repeat search from the root */
737 * only check that the key is in the buffer if key is not
738 * equal to the MAX_KEY. Latter case is only possible in
739 * "finish_unfinished()" processing during mount.
741 RFALSE(comp_keys(&MAX_KEY, key) &&
742 !key_in_buffer(search_path, key, sb),
743 "PAP-5130: key is not in the buffer");
744 #ifdef CONFIG_REISERFS_CHECK
745 if (REISERFS_SB(sb)->cur_tb) {
746 print_cur_tb("5140");
747 reiserfs_panic(sb, "PAP-5140",
748 "schedule occurred in do_balance!");
753 * make sure, that the node contents look like a node of
756 if (!is_tree_node(bh, expected_level)) {
757 reiserfs_error(sb, "vs-5150",
758 "invalid format found in block %ld. "
759 "Fsck?", bh->b_blocknr);
760 pathrelse(search_path);
764 /* ok, we have acquired next formatted node in the tree */
765 node_level = B_LEVEL(bh);
767 PROC_INFO_BH_STAT(sb, bh, node_level - 1);
769 RFALSE(node_level < stop_level,
770 "vs-5152: tree level (%d) is less than stop level (%d)",
771 node_level, stop_level);
773 retval = bin_search(key, item_head(bh, 0),
776 DISK_LEAF_NODE_LEVEL) ? IH_SIZE :
778 &last_element->pe_position);
779 if (node_level == stop_level) {
783 /* we are not in the stop level */
785 * item has been found, so we choose the pointer which
786 * is to the right of the found one
788 if (retval == ITEM_FOUND)
789 last_element->pe_position++;
792 * if item was not found we choose the position which is to
793 * the left of the found item. This requires no code,
794 * bin_search did it already.
798 * So we have chosen a position in the current node which is
799 * an internal node. Now we calculate child block number by
800 * position in the node.
803 B_N_CHILD_NUM(bh, last_element->pe_position);
806 * if we are going to read leaf nodes, try for read
809 if ((search_path->reada & PATH_READA) &&
810 node_level == DISK_LEAF_NODE_LEVEL + 1) {
811 int pos = last_element->pe_position;
812 int limit = B_NR_ITEMS(bh);
813 struct reiserfs_key *le_key;
815 if (search_path->reada & PATH_READA_BACK)
817 while (reada_count < SEARCH_BY_KEY_READA) {
820 reada_blocks[reada_count++] =
821 B_N_CHILD_NUM(bh, pos);
822 if (search_path->reada & PATH_READA_BACK)
828 * check to make sure we're in the same object
830 le_key = internal_key(bh, pos);
831 if (le32_to_cpu(le_key->k_objectid) !=
832 key->on_disk_key.k_objectid) {
841 * Form the path to an item and position in this item which contains
842 * file byte defined by key. If there is no such item
843 * corresponding to the key, we point the path to the item with
844 * maximal key less than key, and *pos_in_item is set to one
845 * past the last entry/byte in the item. If searching for entry in a
846 * directory item, and it is not found, *pos_in_item is set to one
847 * entry more than the entry with maximal key which is less than the
850 * Note that if there is no entry in this same node which is one more,
851 * then we point to an imaginary entry. for direct items, the
852 * position is in units of bytes, for indirect items the position is
853 * in units of blocknr entries, for directory items the position is in
854 * units of directory entries.
856 /* The function is NOT SCHEDULE-SAFE! */
857 int search_for_position_by_key(struct super_block *sb,
858 /* Key to search (cpu variable) */
859 const struct cpu_key *p_cpu_key,
860 /* Filled up by this function. */
861 struct treepath *search_path)
863 struct item_head *p_le_ih; /* pointer to on-disk structure */
865 loff_t item_offset, offset;
866 struct reiserfs_dir_entry de;
869 /* If searching for directory entry. */
870 if (is_direntry_cpu_key(p_cpu_key))
871 return search_by_entry_key(sb, p_cpu_key, search_path,
874 /* If not searching for directory entry. */
876 /* If item is found. */
877 retval = search_item(sb, p_cpu_key, search_path);
878 if (retval == IO_ERROR)
880 if (retval == ITEM_FOUND) {
884 (PATH_PLAST_BUFFER(search_path),
885 PATH_LAST_POSITION(search_path))),
886 "PAP-5165: item length equals zero");
888 pos_in_item(search_path) = 0;
889 return POSITION_FOUND;
892 RFALSE(!PATH_LAST_POSITION(search_path),
893 "PAP-5170: position equals zero");
895 /* Item is not found. Set path to the previous item. */
897 item_head(PATH_PLAST_BUFFER(search_path),
898 --PATH_LAST_POSITION(search_path));
899 blk_size = sb->s_blocksize;
901 if (comp_short_keys(&p_le_ih->ih_key, p_cpu_key))
902 return FILE_NOT_FOUND;
904 /* FIXME: quite ugly this far */
906 item_offset = le_ih_k_offset(p_le_ih);
907 offset = cpu_key_k_offset(p_cpu_key);
909 /* Needed byte is contained in the item pointed to by the path. */
910 if (item_offset <= offset &&
911 item_offset + op_bytes_number(p_le_ih, blk_size) > offset) {
912 pos_in_item(search_path) = offset - item_offset;
913 if (is_indirect_le_ih(p_le_ih)) {
914 pos_in_item(search_path) /= blk_size;
916 return POSITION_FOUND;
920 * Needed byte is not contained in the item pointed to by the
921 * path. Set pos_in_item out of the item.
923 if (is_indirect_le_ih(p_le_ih))
924 pos_in_item(search_path) =
925 ih_item_len(p_le_ih) / UNFM_P_SIZE;
927 pos_in_item(search_path) = ih_item_len(p_le_ih);
929 return POSITION_NOT_FOUND;
932 /* Compare given item and item pointed to by the path. */
933 int comp_items(const struct item_head *stored_ih, const struct treepath *path)
935 struct buffer_head *bh = PATH_PLAST_BUFFER(path);
936 struct item_head *ih;
938 /* Last buffer at the path is not in the tree. */
939 if (!B_IS_IN_TREE(bh))
942 /* Last path position is invalid. */
943 if (PATH_LAST_POSITION(path) >= B_NR_ITEMS(bh))
946 /* we need only to know, whether it is the same item */
947 ih = tp_item_head(path);
948 return memcmp(stored_ih, ih, IH_SIZE);
951 /* unformatted nodes are not logged anymore, ever. This is safe now */
952 #define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1)
954 /* block can not be forgotten as it is in I/O or held by someone */
955 #define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh)))
957 /* prepare for delete or cut of direct item */
958 static inline int prepare_for_direct_item(struct treepath *path,
959 struct item_head *le_ih,
961 loff_t new_file_length, int *cut_size)
965 if (new_file_length == max_reiserfs_offset(inode)) {
966 /* item has to be deleted */
967 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
970 /* new file gets truncated */
971 if (get_inode_item_key_version(inode) == KEY_FORMAT_3_6) {
972 round_len = ROUND_UP(new_file_length);
973 /* this was new_file_length < le_ih ... */
974 if (round_len < le_ih_k_offset(le_ih)) {
975 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
976 return M_DELETE; /* Delete this item. */
978 /* Calculate first position and size for cutting from item. */
979 pos_in_item(path) = round_len - (le_ih_k_offset(le_ih) - 1);
980 *cut_size = -(ih_item_len(le_ih) - pos_in_item(path));
982 return M_CUT; /* Cut from this item. */
985 /* old file: items may have any length */
987 if (new_file_length < le_ih_k_offset(le_ih)) {
988 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
989 return M_DELETE; /* Delete this item. */
992 /* Calculate first position and size for cutting from item. */
993 *cut_size = -(ih_item_len(le_ih) -
995 new_file_length + 1 - le_ih_k_offset(le_ih)));
996 return M_CUT; /* Cut from this item. */
999 static inline int prepare_for_direntry_item(struct treepath *path,
1000 struct item_head *le_ih,
1001 struct inode *inode,
1002 loff_t new_file_length,
1005 if (le_ih_k_offset(le_ih) == DOT_OFFSET &&
1006 new_file_length == max_reiserfs_offset(inode)) {
1007 RFALSE(ih_entry_count(le_ih) != 2,
1008 "PAP-5220: incorrect empty directory item (%h)", le_ih);
1009 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
1010 /* Delete the directory item containing "." and ".." entry. */
1014 if (ih_entry_count(le_ih) == 1) {
1016 * Delete the directory item such as there is one record only
1019 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
1023 /* Cut one record from the directory item. */
1026 entry_length(get_last_bh(path), le_ih, pos_in_item(path)));
1030 #define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1)
1033 * If the path points to a directory or direct item, calculate mode
1034 * and the size cut, for balance.
1035 * If the path points to an indirect item, remove some number of its
1036 * unformatted nodes.
1037 * In case of file truncate calculate whether this item must be
1038 * deleted/truncated or last unformatted node of this item will be
1039 * converted to a direct item.
1040 * This function returns a determination of what balance mode the
1041 * calling function should employ.
1043 static char prepare_for_delete_or_cut(struct reiserfs_transaction_handle *th,
1044 struct inode *inode,
1045 struct treepath *path,
1046 const struct cpu_key *item_key,
1048 * Number of unformatted nodes
1049 * which were removed from end
1054 /* MAX_KEY_OFFSET in case of delete. */
1055 unsigned long long new_file_length
1058 struct super_block *sb = inode->i_sb;
1059 struct item_head *p_le_ih = tp_item_head(path);
1060 struct buffer_head *bh = PATH_PLAST_BUFFER(path);
1062 BUG_ON(!th->t_trans_id);
1064 /* Stat_data item. */
1065 if (is_statdata_le_ih(p_le_ih)) {
1067 RFALSE(new_file_length != max_reiserfs_offset(inode),
1068 "PAP-5210: mode must be M_DELETE");
1070 *cut_size = -(IH_SIZE + ih_item_len(p_le_ih));
1074 /* Directory item. */
1075 if (is_direntry_le_ih(p_le_ih))
1076 return prepare_for_direntry_item(path, p_le_ih, inode,
1081 if (is_direct_le_ih(p_le_ih))
1082 return prepare_for_direct_item(path, p_le_ih, inode,
1083 new_file_length, cut_size);
1085 /* Case of an indirect item. */
1087 int blk_size = sb->s_blocksize;
1088 struct item_head s_ih;
1094 if ( new_file_length == max_reiserfs_offset (inode) ) {
1096 * prepare_for_delete_or_cut() is called by
1097 * reiserfs_delete_item()
1099 new_file_length = 0;
1106 bh = PATH_PLAST_BUFFER(path);
1107 copy_item_head(&s_ih, tp_item_head(path));
1108 pos = I_UNFM_NUM(&s_ih);
1110 while (le_ih_k_offset (&s_ih) + (pos - 1) * blk_size > new_file_length) {
1115 * Each unformatted block deletion may involve
1116 * one additional bitmap block into the transaction,
1117 * thereby the initial journal space reservation
1118 * might not be enough.
1120 if (!delete && (*cut_size) != 0 &&
1121 reiserfs_transaction_free_space(th) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD)
1124 unfm = (__le32 *)ih_item_body(bh, &s_ih) + pos - 1;
1125 block = get_block_num(unfm, 0);
1128 reiserfs_prepare_for_journal(sb, bh, 1);
1129 put_block_num(unfm, 0, 0);
1130 journal_mark_dirty(th, bh);
1131 reiserfs_free_block(th, inode, block, 1);
1134 reiserfs_cond_resched(sb);
1136 if (item_moved (&s_ih, path)) {
1143 (*cut_size) -= UNFM_P_SIZE;
1146 (*cut_size) -= IH_SIZE;
1152 * a trick. If the buffer has been logged, this will
1153 * do nothing. If we've broken the loop without logging
1154 * it, it will restore the buffer
1156 reiserfs_restore_prepared_buffer(sb, bh);
1157 } while (need_re_search &&
1158 search_for_position_by_key(sb, item_key, path) == POSITION_FOUND);
1159 pos_in_item(path) = pos * UNFM_P_SIZE;
1161 if (*cut_size == 0) {
1163 * Nothing was cut. maybe convert last unformatted node to the
1172 /* Calculate number of bytes which will be deleted or cut during balance */
1173 static int calc_deleted_bytes_number(struct tree_balance *tb, char mode)
1176 struct item_head *p_le_ih = tp_item_head(tb->tb_path);
1178 if (is_statdata_le_ih(p_le_ih))
1183 M_DELETE) ? ih_item_len(p_le_ih) : -tb->insert_size[0];
1184 if (is_direntry_le_ih(p_le_ih)) {
1186 * return EMPTY_DIR_SIZE; We delete emty directories only.
1187 * we can't use EMPTY_DIR_SIZE, as old format dirs have a
1188 * different empty size. ick. FIXME, is this right?
1193 if (is_indirect_le_ih(p_le_ih))
1194 del_size = (del_size / UNFM_P_SIZE) *
1195 (PATH_PLAST_BUFFER(tb->tb_path)->b_size);
1199 static void init_tb_struct(struct reiserfs_transaction_handle *th,
1200 struct tree_balance *tb,
1201 struct super_block *sb,
1202 struct treepath *path, int size)
1205 BUG_ON(!th->t_trans_id);
1207 memset(tb, '\0', sizeof(struct tree_balance));
1208 tb->transaction_handle = th;
1211 PATH_OFFSET_PBUFFER(path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL;
1212 PATH_OFFSET_POSITION(path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0;
1213 tb->insert_size[0] = size;
1216 void padd_item(char *item, int total_length, int length)
1220 for (i = total_length; i > length;)
1224 #ifdef REISERQUOTA_DEBUG
1225 char key2type(struct reiserfs_key *ih)
1227 if (is_direntry_le_key(2, ih))
1229 if (is_direct_le_key(2, ih))
1231 if (is_indirect_le_key(2, ih))
1233 if (is_statdata_le_key(2, ih))
1238 char head2type(struct item_head *ih)
1240 if (is_direntry_le_ih(ih))
1242 if (is_direct_le_ih(ih))
1244 if (is_indirect_le_ih(ih))
1246 if (is_statdata_le_ih(ih))
1253 * Delete object item.
1254 * th - active transaction handle
1255 * path - path to the deleted item
1256 * item_key - key to search for the deleted item
1257 * indode - used for updating i_blocks and quotas
1258 * un_bh - NULL or unformatted node pointer
1260 int reiserfs_delete_item(struct reiserfs_transaction_handle *th,
1261 struct treepath *path, const struct cpu_key *item_key,
1262 struct inode *inode, struct buffer_head *un_bh)
1264 struct super_block *sb = inode->i_sb;
1265 struct tree_balance s_del_balance;
1266 struct item_head s_ih;
1267 struct item_head *q_ih;
1268 int quota_cut_bytes;
1269 int ret_value, del_size, removed;
1272 #ifdef CONFIG_REISERFS_CHECK
1277 BUG_ON(!th->t_trans_id);
1279 init_tb_struct(th, &s_del_balance, sb, path,
1280 0 /*size is unknown */ );
1285 #ifdef CONFIG_REISERFS_CHECK
1289 prepare_for_delete_or_cut(th, inode, path,
1292 max_reiserfs_offset(inode));
1294 RFALSE(mode != M_DELETE, "PAP-5320: mode must be M_DELETE");
1296 copy_item_head(&s_ih, tp_item_head(path));
1297 s_del_balance.insert_size[0] = del_size;
1299 ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, NULL);
1300 if (ret_value != REPEAT_SEARCH)
1303 PROC_INFO_INC(sb, delete_item_restarted);
1305 /* file system changed, repeat search */
1307 search_for_position_by_key(sb, item_key, path);
1308 if (ret_value == IO_ERROR)
1310 if (ret_value == FILE_NOT_FOUND) {
1311 reiserfs_warning(sb, "vs-5340",
1312 "no items of the file %K found",
1318 if (ret_value != CARRY_ON) {
1319 unfix_nodes(&s_del_balance);
1323 /* reiserfs_delete_item returns item length when success */
1324 ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE);
1325 q_ih = tp_item_head(path);
1326 quota_cut_bytes = ih_item_len(q_ih);
1329 * hack so the quota code doesn't have to guess if the file has a
1330 * tail. On tail insert, we allocate quota for 1 unformatted node.
1331 * We test the offset because the tail might have been
1332 * split into multiple items, and we only want to decrement for
1333 * the unfm node once
1335 if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(q_ih)) {
1336 if ((le_ih_k_offset(q_ih) & (sb->s_blocksize - 1)) == 1) {
1337 quota_cut_bytes = sb->s_blocksize + UNFM_P_SIZE;
1339 quota_cut_bytes = 0;
1348 * We are in direct2indirect conversion, so move tail contents
1349 * to the unformatted node
1352 * note, we do the copy before preparing the buffer because we
1353 * don't care about the contents of the unformatted node yet.
1354 * the only thing we really care about is the direct item's
1355 * data is in the unformatted node.
1357 * Otherwise, we would have to call
1358 * reiserfs_prepare_for_journal on the unformatted node,
1359 * which might schedule, meaning we'd have to loop all the
1360 * way back up to the start of the while loop.
1362 * The unformatted node must be dirtied later on. We can't be
1363 * sure here if the entire tail has been deleted yet.
1365 * un_bh is from the page cache (all unformatted nodes are
1366 * from the page cache) and might be a highmem page. So, we
1367 * can't use un_bh->b_data.
1371 data = kmap_atomic(un_bh->b_page);
1372 off = ((le_ih_k_offset(&s_ih) - 1) & (PAGE_CACHE_SIZE - 1));
1374 ih_item_body(PATH_PLAST_BUFFER(path), &s_ih),
1376 kunmap_atomic(data);
1379 /* Perform balancing after all resources have been collected at once. */
1380 do_balance(&s_del_balance, NULL, NULL, M_DELETE);
1382 #ifdef REISERQUOTA_DEBUG
1383 reiserfs_debug(sb, REISERFS_DEBUG_CODE,
1384 "reiserquota delete_item(): freeing %u, id=%u type=%c",
1385 quota_cut_bytes, inode->i_uid, head2type(&s_ih));
1387 depth = reiserfs_write_unlock_nested(inode->i_sb);
1388 dquot_free_space_nodirty(inode, quota_cut_bytes);
1389 reiserfs_write_lock_nested(inode->i_sb, depth);
1391 /* Return deleted body length */
1396 * Summary Of Mechanisms For Handling Collisions Between Processes:
1398 * deletion of the body of the object is performed by iput(), with the
1399 * result that if multiple processes are operating on a file, the
1400 * deletion of the body of the file is deferred until the last process
1401 * that has an open inode performs its iput().
1403 * writes and truncates are protected from collisions by use of
1406 * creates, linking, and mknod are protected from collisions with other
1407 * processes by making the reiserfs_add_entry() the last step in the
1408 * creation, and then rolling back all changes if there was a collision.
1412 /* this deletes item which never gets split */
1413 void reiserfs_delete_solid_item(struct reiserfs_transaction_handle *th,
1414 struct inode *inode, struct reiserfs_key *key)
1416 struct super_block *sb = th->t_super;
1417 struct tree_balance tb;
1418 INITIALIZE_PATH(path);
1421 struct cpu_key cpu_key;
1423 int quota_cut_bytes = 0;
1425 BUG_ON(!th->t_trans_id);
1427 le_key2cpu_key(&cpu_key, key);
1430 retval = search_item(th->t_super, &cpu_key, &path);
1431 if (retval == IO_ERROR) {
1432 reiserfs_error(th->t_super, "vs-5350",
1433 "i/o failure occurred trying "
1434 "to delete %K", &cpu_key);
1437 if (retval != ITEM_FOUND) {
1440 * No need for a warning, if there is just no free
1441 * space to insert '..' item into the
1442 * newly-created subdir
1445 ((unsigned long long)
1446 GET_HASH_VALUE(le_key_k_offset
1447 (le_key_version(key), key)) == 0
1448 && (unsigned long long)
1449 GET_GENERATION_NUMBER(le_key_k_offset
1450 (le_key_version(key),
1452 reiserfs_warning(th->t_super, "vs-5355",
1453 "%k not found", key);
1458 item_len = ih_item_len(tp_item_head(&path));
1459 init_tb_struct(th, &tb, th->t_super, &path,
1460 -(IH_SIZE + item_len));
1462 quota_cut_bytes = ih_item_len(tp_item_head(&path));
1464 retval = fix_nodes(M_DELETE, &tb, NULL, NULL);
1465 if (retval == REPEAT_SEARCH) {
1466 PROC_INFO_INC(th->t_super, delete_solid_item_restarted);
1470 if (retval == CARRY_ON) {
1471 do_balance(&tb, NULL, NULL, M_DELETE);
1473 * Should we count quota for item? (we don't
1474 * count quotas for save-links)
1478 #ifdef REISERQUOTA_DEBUG
1479 reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE,
1480 "reiserquota delete_solid_item(): freeing %u id=%u type=%c",
1481 quota_cut_bytes, inode->i_uid,
1484 depth = reiserfs_write_unlock_nested(sb);
1485 dquot_free_space_nodirty(inode,
1487 reiserfs_write_lock_nested(sb, depth);
1492 /* IO_ERROR, NO_DISK_SPACE, etc */
1493 reiserfs_warning(th->t_super, "vs-5360",
1494 "could not delete %K due to fix_nodes failure",
1500 reiserfs_check_path(&path);
1503 int reiserfs_delete_object(struct reiserfs_transaction_handle *th,
1504 struct inode *inode)
1508 BUG_ON(!th->t_trans_id);
1510 /* for directory this deletes item containing "." and ".." */
1512 reiserfs_do_truncate(th, inode, NULL, 0 /*no timestamp updates */ );
1516 #if defined( USE_INODE_GENERATION_COUNTER )
1517 if (!old_format_only(th->t_super)) {
1518 __le32 *inode_generation;
1521 &REISERFS_SB(th->t_super)->s_rs->s_inode_generation;
1522 le32_add_cpu(inode_generation, 1);
1524 /* USE_INODE_GENERATION_COUNTER */
1526 reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode));
1531 static void unmap_buffers(struct page *page, loff_t pos)
1533 struct buffer_head *bh;
1534 struct buffer_head *head;
1535 struct buffer_head *next;
1536 unsigned long tail_index;
1537 unsigned long cur_index;
1540 if (page_has_buffers(page)) {
1541 tail_index = pos & (PAGE_CACHE_SIZE - 1);
1543 head = page_buffers(page);
1546 next = bh->b_this_page;
1549 * we want to unmap the buffers that contain
1550 * the tail, and all the buffers after it
1551 * (since the tail must be at the end of the
1552 * file). We don't want to unmap file data
1553 * before the tail, since it might be dirty
1554 * and waiting to reach disk
1556 cur_index += bh->b_size;
1557 if (cur_index > tail_index) {
1558 reiserfs_unmap_buffer(bh);
1561 } while (bh != head);
1566 static int maybe_indirect_to_direct(struct reiserfs_transaction_handle *th,
1567 struct inode *inode,
1569 struct treepath *path,
1570 const struct cpu_key *item_key,
1571 loff_t new_file_size, char *mode)
1573 struct super_block *sb = inode->i_sb;
1574 int block_size = sb->s_blocksize;
1576 BUG_ON(!th->t_trans_id);
1577 BUG_ON(new_file_size != inode->i_size);
1580 * the page being sent in could be NULL if there was an i/o error
1581 * reading in the last block. The user will hit problems trying to
1582 * read the file, but for now we just skip the indirect2direct
1584 if (atomic_read(&inode->i_count) > 1 ||
1585 !tail_has_to_be_packed(inode) ||
1586 !page || (REISERFS_I(inode)->i_flags & i_nopack_mask)) {
1587 /* leave tail in an unformatted node */
1588 *mode = M_SKIP_BALANCING;
1590 block_size - (new_file_size & (block_size - 1));
1595 /* Perform the conversion to a direct_item. */
1596 return indirect2direct(th, inode, page, path, item_key,
1597 new_file_size, mode);
1601 * we did indirect_to_direct conversion. And we have inserted direct
1602 * item successesfully, but there were no disk space to cut unfm
1603 * pointer being converted. Therefore we have to delete inserted
1606 static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle *th,
1607 struct inode *inode, struct treepath *path)
1609 struct cpu_key tail_key;
1612 BUG_ON(!th->t_trans_id);
1614 make_cpu_key(&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4);
1615 tail_key.key_length = 4;
1618 (cpu_key_k_offset(&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1;
1620 /* look for the last byte of the tail */
1621 if (search_for_position_by_key(inode->i_sb, &tail_key, path) ==
1623 reiserfs_panic(inode->i_sb, "vs-5615",
1624 "found invalid item");
1625 RFALSE(path->pos_in_item !=
1626 ih_item_len(tp_item_head(path)) - 1,
1627 "vs-5616: appended bytes found");
1628 PATH_LAST_POSITION(path)--;
1631 reiserfs_delete_item(th, path, &tail_key, inode,
1632 NULL /*unbh not needed */ );
1634 || removed > tail_len,
1635 "vs-5617: there was tail %d bytes, removed item length %d bytes",
1637 tail_len -= removed;
1638 set_cpu_key_k_offset(&tail_key,
1639 cpu_key_k_offset(&tail_key) - removed);
1641 reiserfs_warning(inode->i_sb, "reiserfs-5091", "indirect_to_direct "
1642 "conversion has been rolled back due to "
1643 "lack of disk space");
1644 mark_inode_dirty(inode);
1647 /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */
1648 int reiserfs_cut_from_item(struct reiserfs_transaction_handle *th,
1649 struct treepath *path,
1650 struct cpu_key *item_key,
1651 struct inode *inode,
1652 struct page *page, loff_t new_file_size)
1654 struct super_block *sb = inode->i_sb;
1656 * Every function which is going to call do_balance must first
1657 * create a tree_balance structure. Then it must fill up this
1658 * structure by using the init_tb_struct and fix_nodes functions.
1659 * After that we can make tree balancing.
1661 struct tree_balance s_cut_balance;
1662 struct item_head *p_le_ih;
1663 int cut_size = 0; /* Amount to be cut. */
1664 int ret_value = CARRY_ON;
1665 int removed = 0; /* Number of the removed unformatted nodes. */
1666 int is_inode_locked = 0;
1667 char mode; /* Mode of the balance. */
1669 int quota_cut_bytes;
1670 loff_t tail_pos = 0;
1673 BUG_ON(!th->t_trans_id);
1675 init_tb_struct(th, &s_cut_balance, inode->i_sb, path,
1679 * Repeat this loop until we either cut the item without needing
1680 * to balance, or we fix_nodes without schedule occurring
1684 * Determine the balance mode, position of the first byte to
1685 * be cut, and size to be cut. In case of the indirect item
1686 * free unformatted nodes which are pointed to by the cut
1691 prepare_for_delete_or_cut(th, inode, path,
1693 &cut_size, new_file_size);
1694 if (mode == M_CONVERT) {
1696 * convert last unformatted node to direct item or
1697 * leave tail in the unformatted node
1699 RFALSE(ret_value != CARRY_ON,
1700 "PAP-5570: can not convert twice");
1703 maybe_indirect_to_direct(th, inode, page,
1705 new_file_size, &mode);
1706 if (mode == M_SKIP_BALANCING)
1707 /* tail has been left in the unformatted node */
1710 is_inode_locked = 1;
1713 * removing of last unformatted node will
1714 * change value we have to return to truncate.
1717 retval2 = ret_value;
1720 * So, we have performed the first part of the
1722 * inserting the new direct item. Now we are
1723 * removing the last unformatted node pointer.
1724 * Set key to search for it.
1726 set_cpu_key_k_type(item_key, TYPE_INDIRECT);
1727 item_key->key_length = 4;
1729 (new_file_size & (sb->s_blocksize - 1));
1730 tail_pos = new_file_size;
1731 set_cpu_key_k_offset(item_key, new_file_size + 1);
1732 if (search_for_position_by_key
1734 path) == POSITION_NOT_FOUND) {
1735 print_block(PATH_PLAST_BUFFER(path), 3,
1736 PATH_LAST_POSITION(path) - 1,
1737 PATH_LAST_POSITION(path) + 1);
1738 reiserfs_panic(sb, "PAP-5580", "item to "
1739 "convert does not exist (%K)",
1744 if (cut_size == 0) {
1749 s_cut_balance.insert_size[0] = cut_size;
1751 ret_value = fix_nodes(mode, &s_cut_balance, NULL, NULL);
1752 if (ret_value != REPEAT_SEARCH)
1755 PROC_INFO_INC(sb, cut_from_item_restarted);
1758 search_for_position_by_key(sb, item_key, path);
1759 if (ret_value == POSITION_FOUND)
1762 reiserfs_warning(sb, "PAP-5610", "item %K not found",
1764 unfix_nodes(&s_cut_balance);
1765 return (ret_value == IO_ERROR) ? -EIO : -ENOENT;
1768 /* check fix_nodes results (IO_ERROR or NO_DISK_SPACE) */
1769 if (ret_value != CARRY_ON) {
1770 if (is_inode_locked) {
1772 * FIXME: this seems to be not needed: we are always
1775 indirect_to_direct_roll_back(th, inode, path);
1777 if (ret_value == NO_DISK_SPACE)
1778 reiserfs_warning(sb, "reiserfs-5092",
1780 unfix_nodes(&s_cut_balance);
1784 /* go ahead and perform balancing */
1786 RFALSE(mode == M_PASTE || mode == M_INSERT, "invalid mode");
1788 /* Calculate number of bytes that need to be cut from the item. */
1791 M_DELETE) ? ih_item_len(tp_item_head(path)) : -s_cut_balance.
1794 ret_value = calc_deleted_bytes_number(&s_cut_balance, mode);
1796 ret_value = retval2;
1799 * For direct items, we only change the quota when deleting the last
1802 p_le_ih = tp_item_head(s_cut_balance.tb_path);
1803 if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(p_le_ih)) {
1804 if (mode == M_DELETE &&
1805 (le_ih_k_offset(p_le_ih) & (sb->s_blocksize - 1)) ==
1807 /* FIXME: this is to keep 3.5 happy */
1808 REISERFS_I(inode)->i_first_direct_byte = U32_MAX;
1809 quota_cut_bytes = sb->s_blocksize + UNFM_P_SIZE;
1811 quota_cut_bytes = 0;
1814 #ifdef CONFIG_REISERFS_CHECK
1815 if (is_inode_locked) {
1816 struct item_head *le_ih =
1817 tp_item_head(s_cut_balance.tb_path);
1819 * we are going to complete indirect2direct conversion. Make
1820 * sure, that we exactly remove last unformatted node pointer
1823 if (!is_indirect_le_ih(le_ih))
1824 reiserfs_panic(sb, "vs-5652",
1825 "item must be indirect %h", le_ih);
1827 if (mode == M_DELETE && ih_item_len(le_ih) != UNFM_P_SIZE)
1828 reiserfs_panic(sb, "vs-5653", "completing "
1829 "indirect2direct conversion indirect "
1830 "item %h being deleted must be of "
1831 "4 byte long", le_ih);
1834 && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) {
1835 reiserfs_panic(sb, "vs-5654", "can not complete "
1836 "indirect2direct conversion of %h "
1837 "(CUT, insert_size==%d)",
1838 le_ih, s_cut_balance.insert_size[0]);
1841 * it would be useful to make sure, that right neighboring
1842 * item is direct item of this file
1847 do_balance(&s_cut_balance, NULL, NULL, mode);
1848 if (is_inode_locked) {
1850 * we've done an indirect->direct conversion. when the
1851 * data block was freed, it was removed from the list of
1852 * blocks that must be flushed before the transaction
1853 * commits, make sure to unmap and invalidate it
1855 unmap_buffers(page, tail_pos);
1856 REISERFS_I(inode)->i_flags &= ~i_pack_on_close_mask;
1858 #ifdef REISERQUOTA_DEBUG
1859 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
1860 "reiserquota cut_from_item(): freeing %u id=%u type=%c",
1861 quota_cut_bytes, inode->i_uid, '?');
1863 depth = reiserfs_write_unlock_nested(sb);
1864 dquot_free_space_nodirty(inode, quota_cut_bytes);
1865 reiserfs_write_lock_nested(sb, depth);
1869 static void truncate_directory(struct reiserfs_transaction_handle *th,
1870 struct inode *inode)
1872 BUG_ON(!th->t_trans_id);
1874 reiserfs_error(inode->i_sb, "vs-5655", "link count != 0");
1876 set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), DOT_OFFSET);
1877 set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_DIRENTRY);
1878 reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode));
1879 reiserfs_update_sd(th, inode);
1880 set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), SD_OFFSET);
1881 set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_STAT_DATA);
1885 * Truncate file to the new size. Note, this must be called with a
1886 * transaction already started
1888 int reiserfs_do_truncate(struct reiserfs_transaction_handle *th,
1889 struct inode *inode, /* ->i_size contains new size */
1890 struct page *page, /* up to date for last block */
1892 * when it is called by file_release to convert
1893 * the tail - no timestamps should be updated
1895 int update_timestamps
1898 INITIALIZE_PATH(s_search_path); /* Path to the current object item. */
1899 struct item_head *p_le_ih; /* Pointer to an item header. */
1901 /* Key to search for a previous file item. */
1902 struct cpu_key s_item_key;
1903 loff_t file_size, /* Old file size. */
1904 new_file_size; /* New file size. */
1905 int deleted; /* Number of deleted or truncated bytes. */
1909 BUG_ON(!th->t_trans_id);
1911 (S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode)
1912 || S_ISLNK(inode->i_mode)))
1915 /* deletion of directory - no need to update timestamps */
1916 if (S_ISDIR(inode->i_mode)) {
1917 truncate_directory(th, inode);
1921 /* Get new file size. */
1922 new_file_size = inode->i_size;
1924 /* FIXME: note, that key type is unimportant here */
1925 make_cpu_key(&s_item_key, inode, max_reiserfs_offset(inode),
1929 search_for_position_by_key(inode->i_sb, &s_item_key,
1931 if (retval == IO_ERROR) {
1932 reiserfs_error(inode->i_sb, "vs-5657",
1933 "i/o failure occurred trying to truncate %K",
1938 if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) {
1939 reiserfs_error(inode->i_sb, "PAP-5660",
1940 "wrong result %d of search for %K", retval,
1947 s_search_path.pos_in_item--;
1949 /* Get real file size (total length of all file items) */
1950 p_le_ih = tp_item_head(&s_search_path);
1951 if (is_statdata_le_ih(p_le_ih))
1954 loff_t offset = le_ih_k_offset(p_le_ih);
1956 op_bytes_number(p_le_ih, inode->i_sb->s_blocksize);
1959 * this may mismatch with real file size: if last direct item
1960 * had no padding zeros and last unformatted node had no free
1961 * space, this file would have this file size
1963 file_size = offset + bytes - 1;
1966 * are we doing a full truncate or delete, if so
1967 * kick in the reada code
1969 if (new_file_size == 0)
1970 s_search_path.reada = PATH_READA | PATH_READA_BACK;
1972 if (file_size == 0 || file_size < new_file_size) {
1973 goto update_and_out;
1976 /* Update key to search for the last file item. */
1977 set_cpu_key_k_offset(&s_item_key, file_size);
1980 /* Cut or delete file item. */
1982 reiserfs_cut_from_item(th, &s_search_path, &s_item_key,
1983 inode, page, new_file_size);
1985 reiserfs_warning(inode->i_sb, "vs-5665",
1986 "reiserfs_cut_from_item failed");
1987 reiserfs_check_path(&s_search_path);
1991 RFALSE(deleted > file_size,
1992 "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K",
1993 deleted, file_size, &s_item_key);
1995 /* Change key to search the last file item. */
1996 file_size -= deleted;
1998 set_cpu_key_k_offset(&s_item_key, file_size);
2001 * While there are bytes to truncate and previous
2002 * file item is presented in the tree.
2006 * This loop could take a really long time, and could log
2007 * many more blocks than a transaction can hold. So, we do
2008 * a polite journal end here, and if the transaction needs
2009 * ending, we make sure the file is consistent before ending
2010 * the current trans and starting a new one
2012 if (journal_transaction_should_end(th, 0) ||
2013 reiserfs_transaction_free_space(th) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) {
2014 pathrelse(&s_search_path);
2016 if (update_timestamps) {
2017 inode->i_mtime = CURRENT_TIME_SEC;
2018 inode->i_ctime = CURRENT_TIME_SEC;
2020 reiserfs_update_sd(th, inode);
2022 err = journal_end(th);
2025 err = journal_begin(th, inode->i_sb,
2026 JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD + JOURNAL_PER_BALANCE_CNT * 4) ;
2029 reiserfs_update_inode_transaction(inode);
2031 } while (file_size > ROUND_UP(new_file_size) &&
2032 search_for_position_by_key(inode->i_sb, &s_item_key,
2033 &s_search_path) == POSITION_FOUND);
2035 RFALSE(file_size > ROUND_UP(new_file_size),
2036 "PAP-5680: truncate did not finish: new_file_size %lld, current %lld, oid %d",
2037 new_file_size, file_size, s_item_key.on_disk_key.k_objectid);
2040 if (update_timestamps) {
2041 /* this is truncate, not file closing */
2042 inode->i_mtime = CURRENT_TIME_SEC;
2043 inode->i_ctime = CURRENT_TIME_SEC;
2045 reiserfs_update_sd(th, inode);
2048 pathrelse(&s_search_path);
2052 #ifdef CONFIG_REISERFS_CHECK
2053 /* this makes sure, that we __append__, not overwrite or add holes */
2054 static void check_research_for_paste(struct treepath *path,
2055 const struct cpu_key *key)
2057 struct item_head *found_ih = tp_item_head(path);
2059 if (is_direct_le_ih(found_ih)) {
2060 if (le_ih_k_offset(found_ih) +
2061 op_bytes_number(found_ih,
2062 get_last_bh(path)->b_size) !=
2063 cpu_key_k_offset(key)
2064 || op_bytes_number(found_ih,
2065 get_last_bh(path)->b_size) !=
2067 reiserfs_panic(NULL, "PAP-5720", "found direct item "
2068 "%h or position (%d) does not match "
2069 "to key %K", found_ih,
2070 pos_in_item(path), key);
2072 if (is_indirect_le_ih(found_ih)) {
2073 if (le_ih_k_offset(found_ih) +
2074 op_bytes_number(found_ih,
2075 get_last_bh(path)->b_size) !=
2076 cpu_key_k_offset(key)
2077 || I_UNFM_NUM(found_ih) != pos_in_item(path)
2078 || get_ih_free_space(found_ih) != 0)
2079 reiserfs_panic(NULL, "PAP-5730", "found indirect "
2080 "item (%h) or position (%d) does not "
2081 "match to key (%K)",
2082 found_ih, pos_in_item(path), key);
2085 #endif /* config reiserfs check */
2088 * Paste bytes to the existing item.
2089 * Returns bytes number pasted into the item.
2091 int reiserfs_paste_into_item(struct reiserfs_transaction_handle *th,
2092 /* Path to the pasted item. */
2093 struct treepath *search_path,
2094 /* Key to search for the needed item. */
2095 const struct cpu_key *key,
2096 /* Inode item belongs to */
2097 struct inode *inode,
2098 /* Pointer to the bytes to paste. */
2100 /* Size of pasted bytes. */
2103 struct super_block *sb = inode->i_sb;
2104 struct tree_balance s_paste_balance;
2109 BUG_ON(!th->t_trans_id);
2111 fs_gen = get_generation(inode->i_sb);
2113 #ifdef REISERQUOTA_DEBUG
2114 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
2115 "reiserquota paste_into_item(): allocating %u id=%u type=%c",
2116 pasted_size, inode->i_uid,
2117 key2type(&key->on_disk_key));
2120 depth = reiserfs_write_unlock_nested(sb);
2121 retval = dquot_alloc_space_nodirty(inode, pasted_size);
2122 reiserfs_write_lock_nested(sb, depth);
2124 pathrelse(search_path);
2127 init_tb_struct(th, &s_paste_balance, th->t_super, search_path,
2129 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
2130 s_paste_balance.key = key->on_disk_key;
2133 /* DQUOT_* can schedule, must check before the fix_nodes */
2134 if (fs_changed(fs_gen, inode->i_sb)) {
2139 fix_nodes(M_PASTE, &s_paste_balance, NULL,
2140 body)) == REPEAT_SEARCH) {
2142 /* file system changed while we were in the fix_nodes */
2143 PROC_INFO_INC(th->t_super, paste_into_item_restarted);
2145 search_for_position_by_key(th->t_super, key,
2147 if (retval == IO_ERROR) {
2151 if (retval == POSITION_FOUND) {
2152 reiserfs_warning(inode->i_sb, "PAP-5710",
2153 "entry or pasted byte (%K) exists",
2158 #ifdef CONFIG_REISERFS_CHECK
2159 check_research_for_paste(search_path, key);
2164 * Perform balancing after all resources are collected by fix_nodes,
2165 * and accessing them will not risk triggering schedule.
2167 if (retval == CARRY_ON) {
2168 do_balance(&s_paste_balance, NULL /*ih */ , body, M_PASTE);
2171 retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
2173 /* this also releases the path */
2174 unfix_nodes(&s_paste_balance);
2175 #ifdef REISERQUOTA_DEBUG
2176 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
2177 "reiserquota paste_into_item(): freeing %u id=%u type=%c",
2178 pasted_size, inode->i_uid,
2179 key2type(&key->on_disk_key));
2181 depth = reiserfs_write_unlock_nested(sb);
2182 dquot_free_space_nodirty(inode, pasted_size);
2183 reiserfs_write_lock_nested(sb, depth);
2188 * Insert new item into the buffer at the path.
2189 * th - active transaction handle
2190 * path - path to the inserted item
2191 * ih - pointer to the item header to insert
2192 * body - pointer to the bytes to insert
2194 int reiserfs_insert_item(struct reiserfs_transaction_handle *th,
2195 struct treepath *path, const struct cpu_key *key,
2196 struct item_head *ih, struct inode *inode,
2199 struct tree_balance s_ins_balance;
2202 int quota_bytes = 0;
2204 BUG_ON(!th->t_trans_id);
2206 if (inode) { /* Do we count quotas for item? */
2208 fs_gen = get_generation(inode->i_sb);
2209 quota_bytes = ih_item_len(ih);
2212 * hack so the quota code doesn't have to guess
2213 * if the file has a tail, links are always tails,
2214 * so there's no guessing needed
2216 if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(ih))
2217 quota_bytes = inode->i_sb->s_blocksize + UNFM_P_SIZE;
2218 #ifdef REISERQUOTA_DEBUG
2219 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
2220 "reiserquota insert_item(): allocating %u id=%u type=%c",
2221 quota_bytes, inode->i_uid, head2type(ih));
2224 * We can't dirty inode here. It would be immediately
2225 * written but appropriate stat item isn't inserted yet...
2227 depth = reiserfs_write_unlock_nested(inode->i_sb);
2228 retval = dquot_alloc_space_nodirty(inode, quota_bytes);
2229 reiserfs_write_lock_nested(inode->i_sb, depth);
2235 init_tb_struct(th, &s_ins_balance, th->t_super, path,
2236 IH_SIZE + ih_item_len(ih));
2237 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
2238 s_ins_balance.key = key->on_disk_key;
2241 * DQUOT_* can schedule, must check to be sure calling
2244 if (inode && fs_changed(fs_gen, inode->i_sb)) {
2249 fix_nodes(M_INSERT, &s_ins_balance, ih,
2250 body)) == REPEAT_SEARCH) {
2252 /* file system changed while we were in the fix_nodes */
2253 PROC_INFO_INC(th->t_super, insert_item_restarted);
2254 retval = search_item(th->t_super, key, path);
2255 if (retval == IO_ERROR) {
2259 if (retval == ITEM_FOUND) {
2260 reiserfs_warning(th->t_super, "PAP-5760",
2261 "key %K already exists in the tree",
2268 /* make balancing after all resources will be collected at a time */
2269 if (retval == CARRY_ON) {
2270 do_balance(&s_ins_balance, ih, body, M_INSERT);
2274 retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
2276 /* also releases the path */
2277 unfix_nodes(&s_ins_balance);
2278 #ifdef REISERQUOTA_DEBUG
2280 reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE,
2281 "reiserquota insert_item(): freeing %u id=%u type=%c",
2282 quota_bytes, inode->i_uid, head2type(ih));
2285 int depth = reiserfs_write_unlock_nested(inode->i_sb);
2286 dquot_free_space_nodirty(inode, quota_bytes);
2287 reiserfs_write_lock_nested(inode->i_sb, depth);