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
12 * This file contains functions dealing with S+tree
30 * decrement_counters_in_path
32 * pathrelse_and_restore
36 * search_for_position_by_key
38 * prepare_for_direct_item
39 * prepare_for_direntry_item
40 * prepare_for_delete_or_cut
41 * calc_deleted_bytes_number
44 * reiserfs_delete_item
45 * reiserfs_delete_solid_item
46 * reiserfs_delete_object
47 * maybe_indirect_to_direct
48 * indirect_to_direct_roll_back
49 * reiserfs_cut_from_item
51 * reiserfs_do_truncate
52 * reiserfs_paste_into_item
53 * reiserfs_insert_item
56 #include <linux/config.h>
57 #include <linux/time.h>
58 #include <linux/string.h>
59 #include <linux/pagemap.h>
60 #include <linux/reiserfs_fs.h>
61 #include <linux/smp_lock.h>
62 #include <linux/buffer_head.h>
63 #include <linux/quotaops.h>
65 /* Does the buffer contain a disk block which is in the tree. */
66 inline int B_IS_IN_TREE (const struct buffer_head * p_s_bh)
69 RFALSE( B_LEVEL (p_s_bh) > MAX_HEIGHT,
70 "PAP-1010: block (%b) has too big level (%z)", p_s_bh, p_s_bh);
72 return ( B_LEVEL (p_s_bh) != FREE_LEVEL );
75 inline void copy_short_key (void * to, const void * from)
77 memcpy (to, from, SHORT_KEY_SIZE);
81 // to gets item head in le form
83 inline void copy_item_head(struct item_head * p_v_to,
84 const struct item_head * p_v_from)
86 memcpy (p_v_to, p_v_from, IH_SIZE);
90 /* k1 is pointer to on-disk structure which is stored in little-endian
91 form. k2 is pointer to cpu variable. For key of items of the same
92 object this returns 0.
93 Returns: -1 if key1 < key2
96 inline int comp_short_keys (const struct reiserfs_key * le_key,
97 const struct cpu_key * cpu_key)
99 __u32 * p_s_le_u32, * p_s_cpu_u32;
100 int n_key_length = REISERFS_SHORT_KEY_LEN;
102 p_s_le_u32 = (__u32 *)le_key;
103 p_s_cpu_u32 = (__u32 *)&cpu_key->on_disk_key;
104 for( ; n_key_length--; ++p_s_le_u32, ++p_s_cpu_u32 ) {
105 if ( le32_to_cpu (*p_s_le_u32) < *p_s_cpu_u32 )
107 if ( le32_to_cpu (*p_s_le_u32) > *p_s_cpu_u32 )
115 /* k1 is pointer to on-disk structure which is stored in little-endian
116 form. k2 is pointer to cpu variable.
117 Compare keys using all 4 key fields.
118 Returns: -1 if key1 < key2 0
119 if key1 = key2 1 if key1 > key2 */
120 inline int comp_keys (const struct reiserfs_key * le_key, const struct cpu_key * cpu_key)
124 retval = comp_short_keys (le_key, cpu_key);
127 if (le_key_k_offset (le_key_version(le_key), le_key) < cpu_key_k_offset (cpu_key))
129 if (le_key_k_offset (le_key_version(le_key), le_key) > cpu_key_k_offset (cpu_key))
132 if (cpu_key->key_length == 3)
135 /* this part is needed only when tail conversion is in progress */
136 if (le_key_k_type (le_key_version(le_key), le_key) < cpu_key_k_type (cpu_key))
139 if (le_key_k_type (le_key_version(le_key), le_key) > cpu_key_k_type (cpu_key))
147 // FIXME: not used yet
149 inline int comp_cpu_keys (const struct cpu_key * key1,
150 const struct cpu_key * key2)
152 if (key1->on_disk_key.k_dir_id < key2->on_disk_key.k_dir_id)
154 if (key1->on_disk_key.k_dir_id > key2->on_disk_key.k_dir_id)
157 if (key1->on_disk_key.k_objectid < key2->on_disk_key.k_objectid)
159 if (key1->on_disk_key.k_objectid > key2->on_disk_key.k_objectid)
162 if (cpu_key_k_offset (key1) < cpu_key_k_offset (key2))
164 if (cpu_key_k_offset (key1) > cpu_key_k_offset (key2))
167 reiserfs_warning (NULL, "comp_cpu_keys: type are compared for %K and %K",
170 if (cpu_key_k_type (key1) < cpu_key_k_type (key2))
172 if (cpu_key_k_type (key1) > cpu_key_k_type (key2))
177 inline int comp_short_le_keys (const struct reiserfs_key * key1, const struct reiserfs_key * key2)
179 __u32 * p_s_1_u32, * p_s_2_u32;
180 int n_key_length = REISERFS_SHORT_KEY_LEN;
182 p_s_1_u32 = (__u32 *)key1;
183 p_s_2_u32 = (__u32 *)key2;
184 for( ; n_key_length--; ++p_s_1_u32, ++p_s_2_u32 ) {
185 if ( le32_to_cpu (*p_s_1_u32) < le32_to_cpu (*p_s_2_u32) )
187 if ( le32_to_cpu (*p_s_1_u32) > le32_to_cpu (*p_s_2_u32) )
193 inline int comp_short_cpu_keys (const struct cpu_key * key1,
194 const struct cpu_key * key2)
196 __u32 * p_s_1_u32, * p_s_2_u32;
197 int n_key_length = REISERFS_SHORT_KEY_LEN;
199 p_s_1_u32 = (__u32 *)key1;
200 p_s_2_u32 = (__u32 *)key2;
202 for( ; n_key_length--; ++p_s_1_u32, ++p_s_2_u32 ) {
203 if ( *p_s_1_u32 < *p_s_2_u32 )
205 if ( *p_s_1_u32 > *p_s_2_u32 )
213 inline void cpu_key2cpu_key (struct cpu_key * to, const struct cpu_key * from)
215 memcpy (to, from, sizeof (struct cpu_key));
219 inline void le_key2cpu_key (struct cpu_key * to, const struct reiserfs_key * from)
221 to->on_disk_key.k_dir_id = le32_to_cpu (from->k_dir_id);
222 to->on_disk_key.k_objectid = le32_to_cpu (from->k_objectid);
224 // find out version of the key
225 to->version = le_key_version (from);
226 if (to->version == KEY_FORMAT_3_5) {
227 to->on_disk_key.u.k_offset_v1.k_offset = le32_to_cpu (from->u.k_offset_v1.k_offset);
228 to->on_disk_key.u.k_offset_v1.k_uniqueness = le32_to_cpu (from->u.k_offset_v1.k_uniqueness);
230 to->on_disk_key.u.k_offset_v2.k_offset = offset_v2_k_offset(&from->u.k_offset_v2);
231 to->on_disk_key.u.k_offset_v2.k_type = offset_v2_k_type(&from->u.k_offset_v2);
237 // this does not say which one is bigger, it only returns 1 if keys
238 // are not equal, 0 otherwise
239 inline int comp_le_keys (const struct reiserfs_key * k1, const struct reiserfs_key * k2)
241 return memcmp (k1, k2, sizeof (struct reiserfs_key));
244 /**************************************************************************
245 * Binary search toolkit function *
246 * Search for an item in the array by the item key *
247 * Returns: 1 if found, 0 if not found; *
248 * *p_n_pos = number of the searched element if found, else the *
249 * number of the first element that is larger than p_v_key. *
250 **************************************************************************/
251 /* For those not familiar with binary search: n_lbound is the leftmost item that it
252 could be, n_rbound the rightmost item that it could be. We examine the item
253 halfway between n_lbound and n_rbound, and that tells us either that we can increase
254 n_lbound, or decrease n_rbound, or that we have found it, or if n_lbound <= n_rbound that
255 there are no possible items, and we have not found it. With each examination we
256 cut the number of possible items it could be by one more than half rounded down,
258 inline int bin_search (
259 const void * p_v_key, /* Key to search for. */
260 const void * p_v_base,/* First item in the array. */
261 int p_n_num, /* Number of items in the array. */
262 int p_n_width, /* Item size in the array.
263 searched. Lest the reader be
264 confused, note that this is crafted
265 as a general function, and when it
266 is applied specifically to the array
267 of item headers in a node, p_n_width
268 is actually the item header size not
270 int * p_n_pos /* Number of the searched for element. */
272 int n_rbound, n_lbound, n_j;
274 for ( n_j = ((n_rbound = p_n_num - 1) + (n_lbound = 0))/2; n_lbound <= n_rbound; n_j = (n_rbound + n_lbound)/2 )
275 switch( COMP_KEYS((struct reiserfs_key *)((char * )p_v_base + n_j * p_n_width), (struct cpu_key *)p_v_key) ) {
276 case -1: n_lbound = n_j + 1; continue;
277 case 1: n_rbound = n_j - 1; continue;
278 case 0: *p_n_pos = n_j; return ITEM_FOUND; /* Key found in the array. */
281 /* bin_search did not find given key, it returns position of key,
282 that is minimal and greater than the given one. */
284 return ITEM_NOT_FOUND;
287 #ifdef CONFIG_REISERFS_CHECK
288 extern struct tree_balance * cur_tb;
293 /* Minimal possible key. It is never in the tree. */
294 const struct reiserfs_key MIN_KEY = {0, 0, {{0, 0},}};
296 /* Maximal possible key. It is never in the tree. */
297 const struct reiserfs_key MAX_KEY = {0xffffffff, 0xffffffff, {{0xffffffff, 0xffffffff},}};
300 /* Get delimiting key of the buffer by looking for it in the buffers in the path, starting from the bottom
301 of the path, and going upwards. We must check the path's validity at each step. If the key is not in
302 the path, there is no delimiting key in the tree (buffer is first or last buffer in tree), and in this
303 case we return a special key, either MIN_KEY or MAX_KEY. */
304 inline const struct reiserfs_key * get_lkey (
305 const struct path * p_s_chk_path,
306 const struct super_block * p_s_sb
308 int n_position, n_path_offset = p_s_chk_path->path_length;
309 struct buffer_head * p_s_parent;
311 RFALSE( n_path_offset < FIRST_PATH_ELEMENT_OFFSET,
312 "PAP-5010: invalid offset in the path");
314 /* While not higher in path than first element. */
315 while ( n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET ) {
317 RFALSE( ! buffer_uptodate(PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)),
318 "PAP-5020: parent is not uptodate");
320 /* Parent at the path is not in the tree now. */
321 if ( ! B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)) )
323 /* Check whether position in the parent is correct. */
324 if ( (n_position = PATH_OFFSET_POSITION(p_s_chk_path, n_path_offset)) > B_NR_ITEMS(p_s_parent) )
326 /* Check whether parent at the path really points to the child. */
327 if ( B_N_CHILD_NUM(p_s_parent, n_position) !=
328 PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset + 1)->b_blocknr )
330 /* Return delimiting key if position in the parent is not equal to zero. */
332 return B_N_PDELIM_KEY(p_s_parent, n_position - 1);
334 /* Return MIN_KEY if we are in the root of the buffer tree. */
335 if ( PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
336 SB_ROOT_BLOCK (p_s_sb) )
342 /* Get delimiting key of the buffer at the path and its right neighbor. */
343 inline const struct reiserfs_key * get_rkey (
344 const struct path * p_s_chk_path,
345 const struct super_block * p_s_sb
348 n_path_offset = p_s_chk_path->path_length;
349 struct buffer_head * p_s_parent;
351 RFALSE( n_path_offset < FIRST_PATH_ELEMENT_OFFSET,
352 "PAP-5030: invalid offset in the path");
354 while ( n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET ) {
356 RFALSE( ! buffer_uptodate(PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)),
357 "PAP-5040: parent is not uptodate");
359 /* Parent at the path is not in the tree now. */
360 if ( ! B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)) )
362 /* Check whether position in the parent is correct. */
363 if ( (n_position = PATH_OFFSET_POSITION(p_s_chk_path, n_path_offset)) > B_NR_ITEMS(p_s_parent) )
365 /* Check whether parent at the path really points to the child. */
366 if ( B_N_CHILD_NUM(p_s_parent, n_position) !=
367 PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset + 1)->b_blocknr )
369 /* Return delimiting key if position in the parent is not the last one. */
370 if ( n_position != B_NR_ITEMS(p_s_parent) )
371 return B_N_PDELIM_KEY(p_s_parent, n_position);
373 /* Return MAX_KEY if we are in the root of the buffer tree. */
374 if ( PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
375 SB_ROOT_BLOCK (p_s_sb) )
381 /* Check whether a key is contained in the tree rooted from a buffer at a path. */
382 /* This works by looking at the left and right delimiting keys for the buffer in the last path_element in
383 the path. These delimiting keys are stored at least one level above that buffer in the tree. If the
384 buffer is the first or last node in the tree order then one of the delimiting keys may be absent, and in
385 this case get_lkey and get_rkey return a special key which is MIN_KEY or MAX_KEY. */
386 static inline int key_in_buffer (
387 struct path * p_s_chk_path, /* Path which should be checked. */
388 const struct cpu_key * p_s_key, /* Key which should be checked. */
389 struct super_block * p_s_sb /* Super block pointer. */
392 RFALSE( ! p_s_key || p_s_chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET ||
393 p_s_chk_path->path_length > MAX_HEIGHT,
394 "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)",
395 p_s_key, p_s_chk_path->path_length);
396 RFALSE( !PATH_PLAST_BUFFER(p_s_chk_path)->b_bdev,
397 "PAP-5060: device must not be NODEV");
399 if ( COMP_KEYS(get_lkey(p_s_chk_path, p_s_sb), p_s_key) == 1 )
400 /* left delimiting key is bigger, that the key we look for */
402 // if ( COMP_KEYS(p_s_key, get_rkey(p_s_chk_path, p_s_sb)) != -1 )
403 if ( COMP_KEYS(get_rkey(p_s_chk_path, p_s_sb), p_s_key) != 1 )
404 /* p_s_key must be less than right delimitiing key */
410 inline void decrement_bcount(
411 struct buffer_head * p_s_bh
414 if ( atomic_read (&(p_s_bh->b_count)) ) {
418 reiserfs_panic(NULL, "PAP-5070: decrement_bcount: trying to free free buffer %b", p_s_bh);
423 /* Decrement b_count field of the all buffers in the path. */
424 void decrement_counters_in_path (
425 struct path * p_s_search_path
427 int n_path_offset = p_s_search_path->path_length;
429 RFALSE( n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET ||
430 n_path_offset > EXTENDED_MAX_HEIGHT - 1,
431 "PAP-5080: invalid path offset of %d", n_path_offset);
433 while ( n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET ) {
434 struct buffer_head * bh;
436 bh = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--);
437 decrement_bcount (bh);
439 p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
443 int reiserfs_check_path(struct path *p) {
444 RFALSE( p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET,
445 "path not properly relsed") ;
450 /* Release all buffers in the path. Restore dirty bits clean
451 ** when preparing the buffer for the log
453 ** only called from fix_nodes()
455 void pathrelse_and_restore (
456 struct super_block *s,
457 struct path * p_s_search_path
459 int n_path_offset = p_s_search_path->path_length;
461 RFALSE( n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
462 "clm-4000: invalid path offset");
464 while ( n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET ) {
465 reiserfs_restore_prepared_buffer(s, PATH_OFFSET_PBUFFER(p_s_search_path,
467 brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
469 p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
472 /* Release all buffers in the path. */
474 struct path * p_s_search_path
476 int n_path_offset = p_s_search_path->path_length;
478 RFALSE( n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
479 "PAP-5090: invalid path offset");
481 while ( n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET )
482 brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
484 p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
489 static int is_leaf (char * buf, int blocksize, struct buffer_head * bh)
491 struct block_head * blkh;
492 struct item_head * ih;
498 blkh = (struct block_head *)buf;
499 if ( blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) {
500 reiserfs_warning (NULL, "is_leaf: this should be caught earlier");
504 nr = blkh_nr_item(blkh);
505 if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) {
506 /* item number is too big or too small */
507 reiserfs_warning (NULL, "is_leaf: nr_item seems wrong: %z", bh);
510 ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1;
511 used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location (ih));
512 if (used_space != blocksize - blkh_free_space(blkh)) {
513 /* free space does not match to calculated amount of use space */
514 reiserfs_warning (NULL, "is_leaf: free space seems wrong: %z", bh);
518 // FIXME: it is_leaf will hit performance too much - we may have
521 /* check tables of item heads */
522 ih = (struct item_head *)(buf + BLKH_SIZE);
523 prev_location = blocksize;
524 for (i = 0; i < nr; i ++, ih ++) {
525 if ( le_ih_k_type(ih) == TYPE_ANY) {
526 reiserfs_warning (NULL, "is_leaf: wrong item type for item %h",ih);
529 if (ih_location (ih) >= blocksize || ih_location (ih) < IH_SIZE * nr) {
530 reiserfs_warning (NULL, "is_leaf: item location seems wrong: %h", ih);
533 if (ih_item_len (ih) < 1 || ih_item_len (ih) > MAX_ITEM_LEN (blocksize)) {
534 reiserfs_warning (NULL, "is_leaf: item length seems wrong: %h", ih);
537 if (prev_location - ih_location (ih) != ih_item_len (ih)) {
538 reiserfs_warning (NULL, "is_leaf: item location seems wrong (second one): %h", ih);
541 prev_location = ih_location (ih);
544 // one may imagine much more checks
549 /* returns 1 if buf looks like an internal node, 0 otherwise */
550 static int is_internal (char * buf, int blocksize, struct buffer_head * bh)
552 struct block_head * blkh;
556 blkh = (struct block_head *)buf;
557 nr = blkh_level(blkh);
558 if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) {
559 /* this level is not possible for internal nodes */
560 reiserfs_warning (NULL, "is_internal: this should be caught earlier");
564 nr = blkh_nr_item(blkh);
565 if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) {
566 /* for internal which is not root we might check min number of keys */
567 reiserfs_warning (NULL, "is_internal: number of key seems wrong: %z", bh);
571 used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1);
572 if (used_space != blocksize - blkh_free_space(blkh)) {
573 reiserfs_warning (NULL, "is_internal: free space seems wrong: %z", bh);
577 // one may imagine much more checks
582 // make sure that bh contains formatted node of reiserfs tree of
584 static int is_tree_node (struct buffer_head * bh, int level)
586 if (B_LEVEL (bh) != level) {
587 reiserfs_warning (NULL, "is_tree_node: node level %d does not match to the expected one %d",
588 B_LEVEL (bh), level);
591 if (level == DISK_LEAF_NODE_LEVEL)
592 return is_leaf (bh->b_data, bh->b_size, bh);
594 return is_internal (bh->b_data, bh->b_size, bh);
599 #define SEARCH_BY_KEY_READA 16
601 /* The function is NOT SCHEDULE-SAFE! */
602 static void search_by_key_reada (struct super_block * s,
603 struct buffer_head **bh,
604 unsigned long *b, int num)
608 for (i = 0 ; i < num ; i++) {
609 bh[i] = sb_getblk (s, b[i]);
611 for (j = 0 ; j < i ; j++) {
613 * note, this needs attention if we are getting rid of the BKL
614 * you have to make sure the prepared bit isn't set on this buffer
616 if (!buffer_uptodate(bh[j]))
617 ll_rw_block(READA, 1, bh + j);
622 /**************************************************************************
623 * Algorithm SearchByKey *
624 * look for item in the Disk S+Tree by its key *
625 * Input: p_s_sb - super block *
626 * p_s_key - pointer to the key to search *
627 * Output: ITEM_FOUND, ITEM_NOT_FOUND or IO_ERROR *
628 * p_s_search_path - path from the root to the needed leaf *
629 **************************************************************************/
631 /* This function fills up the path from the root to the leaf as it
632 descends the tree looking for the key. It uses reiserfs_bread to
633 try to find buffers in the cache given their block number. If it
634 does not find them in the cache it reads them from disk. For each
635 node search_by_key finds using reiserfs_bread it then uses
636 bin_search to look through that node. bin_search will find the
637 position of the block_number of the next node if it is looking
638 through an internal node. If it is looking through a leaf node
639 bin_search will find the position of the item which has key either
640 equal to given key, or which is the maximal key less than the given
641 key. search_by_key returns a path that must be checked for the
642 correctness of the top of the path but need not be checked for the
643 correctness of the bottom of the path */
644 /* The function is NOT SCHEDULE-SAFE! */
645 int search_by_key (struct super_block * p_s_sb,
646 const struct cpu_key * p_s_key, /* Key to search. */
647 struct path * p_s_search_path, /* This structure was
648 allocated and initialized
650 function. It is filled up
652 int n_stop_level /* How far down the tree to search. To
653 stop at leaf level - set to
654 DISK_LEAF_NODE_LEVEL */
658 struct buffer_head * p_s_bh;
659 struct path_element * p_s_last_element;
660 int n_node_level, n_retval;
661 int right_neighbor_of_leaf_node;
663 struct buffer_head *reada_bh[SEARCH_BY_KEY_READA];
664 unsigned long reada_blocks[SEARCH_BY_KEY_READA];
667 #ifdef CONFIG_REISERFS_CHECK
668 int n_repeat_counter = 0;
671 PROC_INFO_INC( p_s_sb, search_by_key );
673 /* As we add each node to a path we increase its count. This means that
674 we must be careful to release all nodes in a path before we either
675 discard the path struct or re-use the path struct, as we do here. */
677 decrement_counters_in_path(p_s_search_path);
679 right_neighbor_of_leaf_node = 0;
681 /* With each iteration of this loop we search through the items in the
682 current node, and calculate the next current node(next path element)
683 for the next iteration of this loop.. */
684 n_block_number = SB_ROOT_BLOCK (p_s_sb);
688 #ifdef CONFIG_REISERFS_CHECK
689 if ( !(++n_repeat_counter % 50000) )
690 reiserfs_warning (p_s_sb, "PAP-5100: search_by_key: %s:"
691 "there were %d iterations of while loop "
692 "looking for key %K",
693 current->comm, n_repeat_counter, p_s_key);
696 /* prep path to have another element added to it. */
697 p_s_last_element = PATH_OFFSET_PELEMENT(p_s_search_path, ++p_s_search_path->path_length);
698 fs_gen = get_generation (p_s_sb);
700 /* Read the next tree node, and set the last element in the path to
701 have a pointer to it. */
702 if ((p_s_bh = p_s_last_element->pe_buffer =
703 sb_getblk(p_s_sb, n_block_number)) ) {
704 if (!buffer_uptodate(p_s_bh) && reada_count > 1) {
705 search_by_key_reada (p_s_sb, reada_bh,
706 reada_blocks, reada_count);
708 ll_rw_block(READ, 1, &p_s_bh);
709 wait_on_buffer(p_s_bh);
710 if (!buffer_uptodate(p_s_bh))
714 p_s_search_path->path_length --;
715 pathrelse(p_s_search_path);
719 if (expected_level == -1)
720 expected_level = SB_TREE_HEIGHT (p_s_sb);
723 /* It is possible that schedule occurred. We must check whether the key
724 to search is still in the tree rooted from the current buffer. If
725 not then repeat search from the root. */
726 if ( fs_changed (fs_gen, p_s_sb) &&
727 (!B_IS_IN_TREE (p_s_bh) ||
728 B_LEVEL(p_s_bh) != expected_level ||
729 !key_in_buffer(p_s_search_path, p_s_key, p_s_sb))) {
730 PROC_INFO_INC( p_s_sb, search_by_key_fs_changed );
731 PROC_INFO_INC( p_s_sb, search_by_key_restarted );
732 PROC_INFO_INC( p_s_sb, sbk_restarted[ expected_level - 1 ] );
733 decrement_counters_in_path(p_s_search_path);
735 /* Get the root block number so that we can repeat the search
736 starting from the root. */
737 n_block_number = SB_ROOT_BLOCK (p_s_sb);
739 right_neighbor_of_leaf_node = 0;
741 /* repeat search from the root */
745 /* only check that the key is in the buffer if p_s_key is not
746 equal to the MAX_KEY. Latter case is only possible in
747 "finish_unfinished()" processing during mount. */
748 RFALSE( COMP_KEYS( &MAX_KEY, p_s_key ) &&
749 ! key_in_buffer(p_s_search_path, p_s_key, p_s_sb),
750 "PAP-5130: key is not in the buffer");
751 #ifdef CONFIG_REISERFS_CHECK
753 print_cur_tb ("5140");
754 reiserfs_panic(p_s_sb, "PAP-5140: search_by_key: schedule occurred in do_balance!");
758 // make sure, that the node contents look like a node of
760 if (!is_tree_node (p_s_bh, expected_level)) {
761 reiserfs_warning (p_s_sb, "vs-5150: search_by_key: "
762 "invalid format found in block %ld. Fsck?",
764 pathrelse (p_s_search_path);
768 /* ok, we have acquired next formatted node in the tree */
769 n_node_level = B_LEVEL (p_s_bh);
771 PROC_INFO_BH_STAT( p_s_sb, p_s_bh, n_node_level - 1 );
773 RFALSE( n_node_level < n_stop_level,
774 "vs-5152: tree level (%d) is less than stop level (%d)",
775 n_node_level, n_stop_level);
777 n_retval = bin_search( p_s_key, B_N_PITEM_HEAD(p_s_bh, 0),
779 ( n_node_level == DISK_LEAF_NODE_LEVEL ) ? IH_SIZE : KEY_SIZE,
780 &(p_s_last_element->pe_position));
781 if (n_node_level == n_stop_level) {
785 /* we are not in the stop level */
786 if (n_retval == ITEM_FOUND)
787 /* item has been found, so we choose the pointer which is to the right of the found one */
788 p_s_last_element->pe_position++;
790 /* if item was not found we choose the position which is to
791 the left of the found item. This requires no code,
792 bin_search did it already.*/
794 /* So we have chosen a position in the current node which is
795 an internal node. Now we calculate child block number by
796 position in the node. */
797 n_block_number = B_N_CHILD_NUM(p_s_bh, p_s_last_element->pe_position);
799 /* if we are going to read leaf nodes, try for read ahead as well */
800 if ((p_s_search_path->reada & PATH_READA) &&
801 n_node_level == DISK_LEAF_NODE_LEVEL + 1)
803 int pos = p_s_last_element->pe_position;
804 int limit = B_NR_ITEMS(p_s_bh);
805 struct reiserfs_key *le_key;
807 if (p_s_search_path->reada & PATH_READA_BACK)
809 while(reada_count < SEARCH_BY_KEY_READA) {
812 reada_blocks[reada_count++] = B_N_CHILD_NUM(p_s_bh, pos);
813 if (p_s_search_path->reada & PATH_READA_BACK)
819 * check to make sure we're in the same object
821 le_key = B_N_PDELIM_KEY(p_s_bh, pos);
822 if (le32_to_cpu(le_key->k_objectid) !=
823 p_s_key->on_disk_key.k_objectid)
833 /* Form the path to an item and position in this item which contains
834 file byte defined by p_s_key. If there is no such item
835 corresponding to the key, we point the path to the item with
836 maximal key less than p_s_key, and *p_n_pos_in_item is set to one
837 past the last entry/byte in the item. If searching for entry in a
838 directory item, and it is not found, *p_n_pos_in_item is set to one
839 entry more than the entry with maximal key which is less than the
842 Note that if there is no entry in this same node which is one more,
843 then we point to an imaginary entry. for direct items, the
844 position is in units of bytes, for indirect items the position is
845 in units of blocknr entries, for directory items the position is in
846 units of directory entries. */
848 /* The function is NOT SCHEDULE-SAFE! */
849 int search_for_position_by_key (struct super_block * p_s_sb, /* Pointer to the super block. */
850 const struct cpu_key * p_cpu_key, /* Key to search (cpu variable) */
851 struct path * p_s_search_path /* Filled up by this function. */
853 struct item_head * p_le_ih; /* pointer to on-disk structure */
855 loff_t item_offset, offset;
856 struct reiserfs_dir_entry de;
859 /* If searching for directory entry. */
860 if ( is_direntry_cpu_key (p_cpu_key) )
861 return search_by_entry_key (p_s_sb, p_cpu_key, p_s_search_path, &de);
863 /* If not searching for directory entry. */
865 /* If item is found. */
866 retval = search_item (p_s_sb, p_cpu_key, p_s_search_path);
867 if (retval == IO_ERROR)
869 if ( retval == ITEM_FOUND ) {
871 RFALSE( ! ih_item_len(
872 B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path),
873 PATH_LAST_POSITION(p_s_search_path))),
874 "PAP-5165: item length equals zero");
876 pos_in_item(p_s_search_path) = 0;
877 return POSITION_FOUND;
880 RFALSE( ! PATH_LAST_POSITION(p_s_search_path),
881 "PAP-5170: position equals zero");
883 /* Item is not found. Set path to the previous item. */
884 p_le_ih = B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path), --PATH_LAST_POSITION(p_s_search_path));
885 n_blk_size = p_s_sb->s_blocksize;
887 if (comp_short_keys (&(p_le_ih->ih_key), p_cpu_key)) {
888 return FILE_NOT_FOUND;
891 // FIXME: quite ugly this far
893 item_offset = le_ih_k_offset (p_le_ih);
894 offset = cpu_key_k_offset (p_cpu_key);
896 /* Needed byte is contained in the item pointed to by the path.*/
897 if (item_offset <= offset &&
898 item_offset + op_bytes_number (p_le_ih, n_blk_size) > offset) {
899 pos_in_item (p_s_search_path) = offset - item_offset;
900 if ( is_indirect_le_ih(p_le_ih) ) {
901 pos_in_item (p_s_search_path) /= n_blk_size;
903 return POSITION_FOUND;
906 /* Needed byte is not contained in the item pointed to by the
907 path. Set pos_in_item out of the item. */
908 if ( is_indirect_le_ih (p_le_ih) )
909 pos_in_item (p_s_search_path) = ih_item_len(p_le_ih) / UNFM_P_SIZE;
911 pos_in_item (p_s_search_path) = ih_item_len( p_le_ih );
913 return POSITION_NOT_FOUND;
917 /* Compare given item and item pointed to by the path. */
918 int comp_items (const struct item_head * stored_ih, const struct path * p_s_path)
920 struct buffer_head * p_s_bh;
921 struct item_head * ih;
923 /* Last buffer at the path is not in the tree. */
924 if ( ! B_IS_IN_TREE(p_s_bh = PATH_PLAST_BUFFER(p_s_path)) )
927 /* Last path position is invalid. */
928 if ( PATH_LAST_POSITION(p_s_path) >= B_NR_ITEMS(p_s_bh) )
931 /* we need only to know, whether it is the same item */
932 ih = get_ih (p_s_path);
933 return memcmp (stored_ih, ih, IH_SIZE);
937 /* unformatted nodes are not logged anymore, ever. This is safe
940 #define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1)
942 // block can not be forgotten as it is in I/O or held by someone
943 #define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh)))
947 // prepare for delete or cut of direct item
948 static inline int prepare_for_direct_item (struct path * path,
949 struct item_head * le_ih,
950 struct inode * inode,
951 loff_t new_file_length,
957 if ( new_file_length == max_reiserfs_offset (inode) ) {
958 /* item has to be deleted */
959 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
963 // new file gets truncated
964 if (get_inode_item_key_version (inode) == KEY_FORMAT_3_6) {
966 round_len = ROUND_UP (new_file_length);
967 /* this was n_new_file_length < le_ih ... */
968 if ( round_len < le_ih_k_offset (le_ih) ) {
969 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
970 return M_DELETE; /* Delete this item. */
972 /* Calculate first position and size for cutting from item. */
973 pos_in_item (path) = round_len - (le_ih_k_offset (le_ih) - 1);
974 *cut_size = -(ih_item_len(le_ih) - pos_in_item(path));
976 return M_CUT; /* Cut from this item. */
980 // old file: items may have any length
982 if ( new_file_length < le_ih_k_offset (le_ih) ) {
983 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
984 return M_DELETE; /* Delete this item. */
986 /* Calculate first position and size for cutting from item. */
987 *cut_size = -(ih_item_len(le_ih) -
988 (pos_in_item (path) = new_file_length + 1 - le_ih_k_offset (le_ih)));
989 return M_CUT; /* Cut from this item. */
993 static inline int prepare_for_direntry_item (struct path * path,
994 struct item_head * le_ih,
995 struct inode * inode,
996 loff_t new_file_length,
999 if (le_ih_k_offset (le_ih) == DOT_OFFSET &&
1000 new_file_length == max_reiserfs_offset (inode)) {
1001 RFALSE( ih_entry_count (le_ih) != 2,
1002 "PAP-5220: incorrect empty directory item (%h)", le_ih);
1003 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
1004 return M_DELETE; /* Delete the directory item containing "." and ".." entry. */
1007 if ( ih_entry_count (le_ih) == 1 ) {
1008 /* Delete the directory item such as there is one record only
1010 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
1014 /* Cut one record from the directory item. */
1015 *cut_size = -(DEH_SIZE + entry_length (get_last_bh (path), le_ih, pos_in_item (path)));
1020 /* If the path points to a directory or direct item, calculate mode and the size cut, for balance.
1021 If the path points to an indirect item, remove some number of its unformatted nodes.
1022 In case of file truncate calculate whether this item must be deleted/truncated or last
1023 unformatted node of this item will be converted to a direct item.
1024 This function returns a determination of what balance mode the calling function should employ. */
1025 static char prepare_for_delete_or_cut(
1026 struct reiserfs_transaction_handle *th,
1027 struct inode * inode,
1028 struct path * p_s_path,
1029 const struct cpu_key * p_s_item_key,
1030 int * p_n_removed, /* Number of unformatted nodes which were removed
1031 from end of the file. */
1033 unsigned long long n_new_file_length /* MAX_KEY_OFFSET in case of delete. */
1035 struct super_block * p_s_sb = inode->i_sb;
1036 struct item_head * p_le_ih = PATH_PITEM_HEAD(p_s_path);
1037 struct buffer_head * p_s_bh = PATH_PLAST_BUFFER(p_s_path);
1039 BUG_ON (!th->t_trans_id);
1041 /* Stat_data item. */
1042 if ( is_statdata_le_ih (p_le_ih) ) {
1044 RFALSE( n_new_file_length != max_reiserfs_offset (inode),
1045 "PAP-5210: mode must be M_DELETE");
1047 *p_n_cut_size = -(IH_SIZE + ih_item_len(p_le_ih));
1052 /* Directory item. */
1053 if ( is_direntry_le_ih (p_le_ih) )
1054 return prepare_for_direntry_item (p_s_path, p_le_ih, inode, n_new_file_length, p_n_cut_size);
1057 if ( is_direct_le_ih (p_le_ih) )
1058 return prepare_for_direct_item (p_s_path, p_le_ih, inode, n_new_file_length, p_n_cut_size);
1061 /* Case of an indirect item. */
1063 int n_unfm_number, /* Number of the item unformatted nodes. */
1066 __u32 * p_n_unfm_pointer; /* Pointer to the unformatted node number. */
1068 struct item_head s_ih; /* Item header. */
1069 char c_mode; /* Returned mode of the balance. */
1073 n_blk_size = p_s_sb->s_blocksize;
1075 /* Search for the needed object indirect item until there are no unformatted nodes to be removed. */
1078 p_s_bh = PATH_PLAST_BUFFER(p_s_path);
1079 /* Copy indirect item header to a temp variable. */
1080 copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
1081 /* Calculate number of unformatted nodes in this item. */
1082 n_unfm_number = I_UNFM_NUM(&s_ih);
1084 RFALSE( ! is_indirect_le_ih(&s_ih) || ! n_unfm_number ||
1085 pos_in_item (p_s_path) + 1 != n_unfm_number,
1086 "PAP-5240: invalid item %h "
1087 "n_unfm_number = %d *p_n_pos_in_item = %d",
1088 &s_ih, n_unfm_number, pos_in_item (p_s_path));
1090 /* Calculate balance mode and position in the item to remove unformatted nodes. */
1091 if ( n_new_file_length == max_reiserfs_offset (inode) ) {/* Case of delete. */
1092 pos_in_item (p_s_path) = 0;
1093 *p_n_cut_size = -(IH_SIZE + ih_item_len(&s_ih));
1096 else { /* Case of truncate. */
1097 if ( n_new_file_length < le_ih_k_offset (&s_ih) ) {
1098 pos_in_item (p_s_path) = 0;
1099 *p_n_cut_size = -(IH_SIZE + ih_item_len(&s_ih));
1100 c_mode = M_DELETE; /* Delete this item. */
1103 /* indirect item must be truncated starting from *p_n_pos_in_item-th position */
1104 pos_in_item (p_s_path) = (n_new_file_length + n_blk_size - le_ih_k_offset (&s_ih) ) >> p_s_sb->s_blocksize_bits;
1106 RFALSE( pos_in_item (p_s_path) > n_unfm_number,
1107 "PAP-5250: invalid position in the item");
1109 /* Either convert last unformatted node of indirect item to direct item or increase
1111 if ( pos_in_item (p_s_path) == n_unfm_number ) {
1112 *p_n_cut_size = 0; /* Nothing to cut. */
1113 return M_CONVERT; /* Maybe convert last unformatted node to the direct item. */
1115 /* Calculate size to cut. */
1116 *p_n_cut_size = -(ih_item_len(&s_ih) - pos_in_item(p_s_path) * UNFM_P_SIZE);
1118 c_mode = M_CUT; /* Cut from this indirect item. */
1122 RFALSE( n_unfm_number <= pos_in_item (p_s_path),
1123 "PAP-5260: invalid position in the indirect item");
1125 /* pointers to be cut */
1126 n_unfm_number -= pos_in_item (p_s_path);
1127 /* Set pointer to the last unformatted node pointer that is to be cut. */
1128 p_n_unfm_pointer = (__u32 *)B_I_PITEM(p_s_bh, &s_ih) + I_UNFM_NUM(&s_ih) - 1 - *p_n_removed;
1131 /* We go through the unformatted nodes pointers of the indirect
1132 item and look for the unformatted nodes in the cache. If we
1133 found some of them we free it, zero corresponding indirect item
1134 entry and log buffer containing that indirect item. For this we
1135 need to prepare last path element for logging. If some
1136 unformatted node has b_count > 1 we must not free this
1137 unformatted node since it is in use. */
1138 reiserfs_prepare_for_journal(p_s_sb, p_s_bh, 1);
1139 // note: path could be changed, first line in for loop takes care
1142 for (n_counter = *p_n_removed;
1143 n_counter < n_unfm_number; n_counter++, p_n_unfm_pointer-- ) {
1146 if (item_moved (&s_ih, p_s_path)) {
1150 RFALSE( p_n_unfm_pointer < (__u32 *)B_I_PITEM(p_s_bh, &s_ih) ||
1151 p_n_unfm_pointer > (__u32 *)B_I_PITEM(p_s_bh, &s_ih) + I_UNFM_NUM(&s_ih) - 1,
1152 "vs-5265: pointer out of range");
1154 /* Hole, nothing to remove. */
1155 if ( ! get_block_num(p_n_unfm_pointer,0) ) {
1162 tmp = get_block_num(p_n_unfm_pointer,0);
1163 put_block_num(p_n_unfm_pointer, 0, 0);
1164 journal_mark_dirty (th, p_s_sb, p_s_bh);
1165 reiserfs_free_block(th, inode, tmp, 1);
1166 if ( item_moved (&s_ih, p_s_path) ) {
1172 /* a trick. If the buffer has been logged, this
1173 ** will do nothing. If we've broken the loop without
1174 ** logging it, it will restore the buffer
1177 reiserfs_restore_prepared_buffer(p_s_sb, p_s_bh);
1179 /* This loop can be optimized. */
1180 } while ( (*p_n_removed < n_unfm_number || need_research) &&
1181 search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path) == POSITION_FOUND );
1183 RFALSE( *p_n_removed < n_unfm_number,
1184 "PAP-5310: indirect item is not found");
1185 RFALSE( item_moved (&s_ih, p_s_path),
1186 "after while, comp failed, retry") ;
1188 if (c_mode == M_CUT)
1189 pos_in_item (p_s_path) *= UNFM_P_SIZE;
1194 /* Calculate number of bytes which will be deleted or cut during balance */
1195 int calc_deleted_bytes_number(
1196 struct tree_balance * p_s_tb,
1200 struct item_head * p_le_ih = PATH_PITEM_HEAD(p_s_tb->tb_path);
1202 if ( is_statdata_le_ih (p_le_ih) )
1205 n_del_size = ( c_mode == M_DELETE ) ? ih_item_len(p_le_ih) : -p_s_tb->insert_size[0];
1206 if ( is_direntry_le_ih (p_le_ih) ) {
1207 // return EMPTY_DIR_SIZE; /* We delete emty directoris only. */
1208 // we can't use EMPTY_DIR_SIZE, as old format dirs have a different
1209 // empty size. ick. FIXME, is this right?
1214 if ( is_indirect_le_ih (p_le_ih) )
1215 n_del_size = (n_del_size/UNFM_P_SIZE)*
1216 (PATH_PLAST_BUFFER(p_s_tb->tb_path)->b_size);// - get_ih_free_space (p_le_ih);
1220 static void init_tb_struct(
1221 struct reiserfs_transaction_handle *th,
1222 struct tree_balance * p_s_tb,
1223 struct super_block * p_s_sb,
1224 struct path * p_s_path,
1228 BUG_ON (!th->t_trans_id);
1230 memset (p_s_tb,'\0',sizeof(struct tree_balance));
1231 p_s_tb->transaction_handle = th ;
1232 p_s_tb->tb_sb = p_s_sb;
1233 p_s_tb->tb_path = p_s_path;
1234 PATH_OFFSET_PBUFFER(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL;
1235 PATH_OFFSET_POSITION(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0;
1236 p_s_tb->insert_size[0] = n_size;
1241 void padd_item (char * item, int total_length, int length)
1245 for (i = total_length; i > length; )
1249 #ifdef REISERQUOTA_DEBUG
1250 char key2type(struct reiserfs_key *ih)
1252 if (is_direntry_le_key(2, ih))
1254 if (is_direct_le_key(2, ih))
1256 if (is_indirect_le_key(2, ih))
1258 if (is_statdata_le_key(2, ih))
1263 char head2type(struct item_head *ih)
1265 if (is_direntry_le_ih(ih))
1267 if (is_direct_le_ih(ih))
1269 if (is_indirect_le_ih(ih))
1271 if (is_statdata_le_ih(ih))
1277 /* Delete object item. */
1278 int reiserfs_delete_item (struct reiserfs_transaction_handle *th,
1279 struct path * p_s_path, /* Path to the deleted item. */
1280 const struct cpu_key * p_s_item_key, /* Key to search for the deleted item. */
1281 struct inode * p_s_inode,/* inode is here just to update i_blocks and quotas */
1282 struct buffer_head * p_s_un_bh) /* NULL or unformatted node pointer. */
1284 struct super_block * p_s_sb = p_s_inode->i_sb;
1285 struct tree_balance s_del_balance;
1286 struct item_head s_ih;
1287 struct item_head *q_ih;
1288 int quota_cut_bytes;
1293 #ifdef CONFIG_REISERFS_CHECK
1298 BUG_ON (!th->t_trans_id);
1300 init_tb_struct(th, &s_del_balance, p_s_sb, p_s_path, 0/*size is unknown*/);
1305 #ifdef CONFIG_REISERFS_CHECK
1309 prepare_for_delete_or_cut(th, p_s_inode, p_s_path, p_s_item_key, &n_removed, &n_del_size, max_reiserfs_offset (p_s_inode));
1311 RFALSE( c_mode != M_DELETE, "PAP-5320: mode must be M_DELETE");
1313 copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
1314 s_del_balance.insert_size[0] = n_del_size;
1316 n_ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, NULL);
1317 if ( n_ret_value != REPEAT_SEARCH )
1320 PROC_INFO_INC( p_s_sb, delete_item_restarted );
1322 // file system changed, repeat search
1323 n_ret_value = search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path);
1324 if (n_ret_value == IO_ERROR)
1326 if (n_ret_value == FILE_NOT_FOUND) {
1327 reiserfs_warning (p_s_sb, "vs-5340: reiserfs_delete_item: "
1328 "no items of the file %K found", p_s_item_key);
1333 if ( n_ret_value != CARRY_ON ) {
1334 unfix_nodes(&s_del_balance);
1338 // reiserfs_delete_item returns item length when success
1339 n_ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE);
1340 q_ih = get_ih(p_s_path) ;
1341 quota_cut_bytes = ih_item_len(q_ih) ;
1343 /* hack so the quota code doesn't have to guess if the file
1344 ** has a tail. On tail insert, we allocate quota for 1 unformatted node.
1345 ** We test the offset because the tail might have been
1346 ** split into multiple items, and we only want to decrement for
1347 ** the unfm node once
1349 if (!S_ISLNK (p_s_inode->i_mode) && is_direct_le_ih(q_ih)) {
1350 if ((le_ih_k_offset(q_ih) & (p_s_sb->s_blocksize - 1)) == 1) {
1351 quota_cut_bytes = p_s_sb->s_blocksize + UNFM_P_SIZE;
1353 quota_cut_bytes = 0 ;
1361 /* We are in direct2indirect conversion, so move tail contents
1362 to the unformatted node */
1363 /* note, we do the copy before preparing the buffer because we
1364 ** don't care about the contents of the unformatted node yet.
1365 ** the only thing we really care about is the direct item's data
1366 ** is in the unformatted node.
1368 ** Otherwise, we would have to call reiserfs_prepare_for_journal on
1369 ** the unformatted node, which might schedule, meaning we'd have to
1370 ** loop all the way back up to the start of the while loop.
1372 ** The unformatted node must be dirtied later on. We can't be
1373 ** sure here if the entire tail has been deleted yet.
1375 ** p_s_un_bh is from the page cache (all unformatted nodes are
1376 ** from the page cache) and might be a highmem page. So, we
1377 ** can't use p_s_un_bh->b_data.
1381 data = kmap_atomic(p_s_un_bh->b_page, KM_USER0);
1382 off = ((le_ih_k_offset (&s_ih) - 1) & (PAGE_CACHE_SIZE - 1));
1384 B_I_PITEM(PATH_PLAST_BUFFER(p_s_path), &s_ih), n_ret_value);
1385 kunmap_atomic(data, KM_USER0);
1387 /* Perform balancing after all resources have been collected at once. */
1388 do_balance(&s_del_balance, NULL, NULL, M_DELETE);
1390 #ifdef REISERQUOTA_DEBUG
1391 reiserfs_debug (p_s_sb, "reiserquota delete_item(): freeing %u, id=%u type=%c", quota_cut_bytes, p_s_inode->i_uid, head2type(&s_ih));
1393 DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes);
1395 /* Return deleted body length */
1400 /* Summary Of Mechanisms For Handling Collisions Between Processes:
1402 deletion of the body of the object is performed by iput(), with the
1403 result that if multiple processes are operating on a file, the
1404 deletion of the body of the file is deferred until the last process
1405 that has an open inode performs its iput().
1407 writes and truncates are protected from collisions by use of
1410 creates, linking, and mknod are protected from collisions with other
1411 processes by making the reiserfs_add_entry() the last step in the
1412 creation, and then rolling back all changes if there was a collision.
1417 /* this deletes item which never gets split */
1418 void reiserfs_delete_solid_item (struct reiserfs_transaction_handle *th,
1419 struct inode *inode,
1420 struct reiserfs_key * key)
1422 struct tree_balance tb;
1423 INITIALIZE_PATH (path);
1426 struct cpu_key cpu_key;
1428 int quota_cut_bytes = 0;
1430 BUG_ON (!th->t_trans_id);
1432 le_key2cpu_key (&cpu_key, key);
1435 retval = search_item (th->t_super, &cpu_key, &path);
1436 if (retval == IO_ERROR) {
1437 reiserfs_warning (th->t_super,
1438 "vs-5350: reiserfs_delete_solid_item: "
1439 "i/o failure occurred trying to delete %K",
1443 if (retval != ITEM_FOUND) {
1445 // No need for a warning, if there is just no free space to insert '..' item into the newly-created subdir
1446 if ( !( (unsigned long long) GET_HASH_VALUE (le_key_k_offset (le_key_version (key), key)) == 0 && \
1447 (unsigned long long) GET_GENERATION_NUMBER (le_key_k_offset (le_key_version (key), key)) == 1 ) )
1448 reiserfs_warning (th->t_super, "vs-5355: reiserfs_delete_solid_item: %k not found", key);
1453 item_len = ih_item_len( PATH_PITEM_HEAD(&path) );
1454 init_tb_struct (th, &tb, th->t_super, &path, - (IH_SIZE + item_len));
1456 quota_cut_bytes = ih_item_len(PATH_PITEM_HEAD(&path)) ;
1458 retval = fix_nodes (M_DELETE, &tb, NULL, NULL);
1459 if (retval == REPEAT_SEARCH) {
1460 PROC_INFO_INC( th -> t_super, delete_solid_item_restarted );
1464 if (retval == CARRY_ON) {
1465 do_balance (&tb, NULL, NULL, M_DELETE);
1466 if (inode) { /* Should we count quota for item? (we don't count quotas for save-links) */
1467 #ifdef REISERQUOTA_DEBUG
1468 reiserfs_debug (th->t_super, "reiserquota delete_solid_item(): freeing %u id=%u type=%c", quota_cut_bytes, inode->i_uid, key2type(key));
1470 DQUOT_FREE_SPACE_NODIRTY(inode, quota_cut_bytes);
1475 // IO_ERROR, NO_DISK_SPACE, etc
1476 reiserfs_warning (th->t_super, "vs-5360: reiserfs_delete_solid_item: "
1477 "could not delete %K due to fix_nodes failure", &cpu_key);
1482 reiserfs_check_path(&path) ;
1486 int reiserfs_delete_object (struct reiserfs_transaction_handle *th, struct inode * inode)
1490 BUG_ON (!th->t_trans_id);
1492 /* for directory this deletes item containing "." and ".." */
1493 err = reiserfs_do_truncate (th, inode, NULL, 0/*no timestamp updates*/);
1497 #if defined( USE_INODE_GENERATION_COUNTER )
1498 if( !old_format_only ( th -> t_super ) )
1500 __u32 *inode_generation;
1503 &REISERFS_SB(th -> t_super) -> s_rs -> s_inode_generation;
1504 *inode_generation = cpu_to_le32( le32_to_cpu( *inode_generation ) + 1 );
1506 /* USE_INODE_GENERATION_COUNTER */
1508 reiserfs_delete_solid_item (th, inode, INODE_PKEY (inode));
1514 unmap_buffers(struct page *page, loff_t pos) {
1515 struct buffer_head *bh ;
1516 struct buffer_head *head ;
1517 struct buffer_head *next ;
1518 unsigned long tail_index ;
1519 unsigned long cur_index ;
1522 if (page_has_buffers(page)) {
1523 tail_index = pos & (PAGE_CACHE_SIZE - 1) ;
1525 head = page_buffers(page) ;
1528 next = bh->b_this_page ;
1530 /* we want to unmap the buffers that contain the tail, and
1531 ** all the buffers after it (since the tail must be at the
1532 ** end of the file). We don't want to unmap file data
1533 ** before the tail, since it might be dirty and waiting to
1536 cur_index += bh->b_size ;
1537 if (cur_index > tail_index) {
1538 reiserfs_unmap_buffer(bh) ;
1541 } while (bh != head) ;
1542 if ( PAGE_SIZE == bh->b_size ) {
1543 clear_page_dirty(page);
1549 static int maybe_indirect_to_direct (struct reiserfs_transaction_handle *th,
1550 struct inode * p_s_inode,
1552 struct path * p_s_path,
1553 const struct cpu_key * p_s_item_key,
1554 loff_t n_new_file_size,
1557 struct super_block * p_s_sb = p_s_inode->i_sb;
1558 int n_block_size = p_s_sb->s_blocksize;
1560 BUG_ON (!th->t_trans_id);
1562 if (n_new_file_size != p_s_inode->i_size)
1565 /* the page being sent in could be NULL if there was an i/o error
1566 ** reading in the last block. The user will hit problems trying to
1567 ** read the file, but for now we just skip the indirect2direct
1569 if (atomic_read(&p_s_inode->i_count) > 1 ||
1570 !tail_has_to_be_packed (p_s_inode) ||
1571 !page || (REISERFS_I(p_s_inode)->i_flags & i_nopack_mask)) {
1572 // leave tail in an unformatted node
1573 *p_c_mode = M_SKIP_BALANCING;
1574 cut_bytes = n_block_size - (n_new_file_size & (n_block_size - 1));
1575 pathrelse(p_s_path);
1578 /* Permorm the conversion to a direct_item. */
1579 /*return indirect_to_direct (p_s_inode, p_s_path, p_s_item_key, n_new_file_size, p_c_mode);*/
1580 return indirect2direct (th, p_s_inode, page, p_s_path, p_s_item_key, n_new_file_size, p_c_mode);
1584 /* we did indirect_to_direct conversion. And we have inserted direct
1585 item successesfully, but there were no disk space to cut unfm
1586 pointer being converted. Therefore we have to delete inserted
1588 static void indirect_to_direct_roll_back (struct reiserfs_transaction_handle *th, struct inode * inode, struct path * path)
1590 struct cpu_key tail_key;
1593 BUG_ON (!th->t_trans_id);
1595 make_cpu_key (&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4);// !!!!
1596 tail_key.key_length = 4;
1598 tail_len = (cpu_key_k_offset (&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1;
1600 /* look for the last byte of the tail */
1601 if (search_for_position_by_key (inode->i_sb, &tail_key, path) == POSITION_NOT_FOUND)
1602 reiserfs_panic (inode->i_sb, "vs-5615: indirect_to_direct_roll_back: found invalid item");
1603 RFALSE( path->pos_in_item != ih_item_len(PATH_PITEM_HEAD (path)) - 1,
1604 "vs-5616: appended bytes found");
1605 PATH_LAST_POSITION (path) --;
1607 removed = reiserfs_delete_item (th, path, &tail_key, inode, NULL/*unbh not needed*/);
1608 RFALSE( removed <= 0 || 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, cpu_key_k_offset (&tail_key) - removed);
1614 reiserfs_warning (inode->i_sb, "indirect_to_direct_roll_back: indirect_to_direct conversion has been rolled back due to lack of disk space");
1615 //mark_file_without_tail (inode);
1616 mark_inode_dirty (inode);
1620 /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */
1621 int reiserfs_cut_from_item (struct reiserfs_transaction_handle *th,
1622 struct path * p_s_path,
1623 struct cpu_key * p_s_item_key,
1624 struct inode * p_s_inode,
1626 loff_t n_new_file_size)
1628 struct super_block * p_s_sb = p_s_inode->i_sb;
1629 /* Every function which is going to call do_balance must first
1630 create a tree_balance structure. Then it must fill up this
1631 structure by using the init_tb_struct and fix_nodes functions.
1632 After that we can make tree balancing. */
1633 struct tree_balance s_cut_balance;
1634 struct item_head *p_le_ih;
1635 int n_cut_size = 0, /* Amount to be cut. */
1636 n_ret_value = CARRY_ON,
1637 n_removed = 0, /* Number of the removed unformatted nodes. */
1638 n_is_inode_locked = 0;
1639 char c_mode; /* Mode of the balance. */
1641 int quota_cut_bytes;
1642 loff_t tail_pos = 0;
1644 BUG_ON (!th->t_trans_id);
1646 init_tb_struct(th, &s_cut_balance, p_s_inode->i_sb, p_s_path, n_cut_size);
1649 /* Repeat this loop until we either cut the item without needing
1650 to balance, or we fix_nodes without schedule occurring */
1652 /* Determine the balance mode, position of the first byte to
1653 be cut, and size to be cut. In case of the indirect item
1654 free unformatted nodes which are pointed to by the cut
1657 c_mode = prepare_for_delete_or_cut(th, p_s_inode, p_s_path, p_s_item_key, &n_removed,
1658 &n_cut_size, n_new_file_size);
1659 if ( c_mode == M_CONVERT ) {
1660 /* convert last unformatted node to direct item or leave
1661 tail in the unformatted node */
1662 RFALSE( n_ret_value != CARRY_ON, "PAP-5570: can not convert twice");
1664 n_ret_value = maybe_indirect_to_direct (th, p_s_inode, page, p_s_path, p_s_item_key,
1665 n_new_file_size, &c_mode);
1666 if ( c_mode == M_SKIP_BALANCING )
1667 /* tail has been left in the unformatted node */
1670 n_is_inode_locked = 1;
1672 /* removing of last unformatted node will change value we
1673 have to return to truncate. Save it */
1674 retval2 = n_ret_value;
1675 /*retval2 = p_s_sb->s_blocksize - (n_new_file_size & (p_s_sb->s_blocksize - 1));*/
1677 /* So, we have performed the first part of the conversion:
1678 inserting the new direct item. Now we are removing the
1679 last unformatted node pointer. Set key to search for
1681 set_cpu_key_k_type (p_s_item_key, TYPE_INDIRECT);
1682 p_s_item_key->key_length = 4;
1683 n_new_file_size -= (n_new_file_size & (p_s_sb->s_blocksize - 1));
1684 tail_pos = n_new_file_size;
1685 set_cpu_key_k_offset (p_s_item_key, n_new_file_size + 1);
1686 if ( search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path) == POSITION_NOT_FOUND ){
1687 print_block (PATH_PLAST_BUFFER (p_s_path), 3, PATH_LAST_POSITION (p_s_path) - 1, PATH_LAST_POSITION (p_s_path) + 1);
1688 reiserfs_panic(p_s_sb, "PAP-5580: reiserfs_cut_from_item: item to convert does not exist (%K)", p_s_item_key);
1692 if (n_cut_size == 0) {
1693 pathrelse (p_s_path);
1697 s_cut_balance.insert_size[0] = n_cut_size;
1699 n_ret_value = fix_nodes(c_mode, &s_cut_balance, NULL, NULL);
1700 if ( n_ret_value != REPEAT_SEARCH )
1703 PROC_INFO_INC( p_s_sb, cut_from_item_restarted );
1705 n_ret_value = search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path);
1706 if (n_ret_value == POSITION_FOUND)
1709 reiserfs_warning (p_s_sb, "PAP-5610: reiserfs_cut_from_item: item %K not found", p_s_item_key);
1710 unfix_nodes (&s_cut_balance);
1711 return (n_ret_value == IO_ERROR) ? -EIO : -ENOENT;
1714 // check fix_nodes results (IO_ERROR or NO_DISK_SPACE)
1715 if ( n_ret_value != CARRY_ON ) {
1716 if ( n_is_inode_locked ) {
1717 // FIXME: this seems to be not needed: we are always able
1719 indirect_to_direct_roll_back (th, p_s_inode, p_s_path);
1721 if (n_ret_value == NO_DISK_SPACE)
1722 reiserfs_warning (p_s_sb, "NO_DISK_SPACE");
1723 unfix_nodes (&s_cut_balance);
1727 /* go ahead and perform balancing */
1729 RFALSE( c_mode == M_PASTE || c_mode == M_INSERT, "invalid mode");
1731 /* Calculate number of bytes that need to be cut from the item. */
1732 quota_cut_bytes = ( c_mode == M_DELETE ) ? ih_item_len(get_ih(p_s_path)) : -s_cut_balance.insert_size[0];
1734 n_ret_value = calc_deleted_bytes_number(&s_cut_balance, c_mode);
1736 n_ret_value = retval2;
1739 /* For direct items, we only change the quota when deleting the last
1742 p_le_ih = PATH_PITEM_HEAD (s_cut_balance.tb_path);
1743 if (!S_ISLNK (p_s_inode->i_mode) && is_direct_le_ih(p_le_ih)) {
1744 if (c_mode == M_DELETE &&
1745 (le_ih_k_offset (p_le_ih) & (p_s_sb->s_blocksize - 1)) == 1 ) {
1746 // FIXME: this is to keep 3.5 happy
1747 REISERFS_I(p_s_inode)->i_first_direct_byte = U32_MAX;
1748 quota_cut_bytes = p_s_sb->s_blocksize + UNFM_P_SIZE ;
1750 quota_cut_bytes = 0 ;
1753 #ifdef CONFIG_REISERFS_CHECK
1754 if (n_is_inode_locked) {
1755 struct item_head * le_ih = PATH_PITEM_HEAD (s_cut_balance.tb_path);
1756 /* we are going to complete indirect2direct conversion. Make
1757 sure, that we exactly remove last unformatted node pointer
1759 if (!is_indirect_le_ih (le_ih))
1760 reiserfs_panic (p_s_sb, "vs-5652: reiserfs_cut_from_item: "
1761 "item must be indirect %h", le_ih);
1763 if (c_mode == M_DELETE && ih_item_len(le_ih) != UNFM_P_SIZE)
1764 reiserfs_panic (p_s_sb, "vs-5653: reiserfs_cut_from_item: "
1765 "completing indirect2direct conversion indirect item %h "
1766 "being deleted must be of 4 byte long", le_ih);
1768 if (c_mode == M_CUT && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) {
1769 reiserfs_panic (p_s_sb, "vs-5654: reiserfs_cut_from_item: "
1770 "can not complete indirect2direct conversion of %h (CUT, insert_size==%d)",
1771 le_ih, s_cut_balance.insert_size[0]);
1773 /* it would be useful to make sure, that right neighboring
1774 item is direct item of this file */
1778 do_balance(&s_cut_balance, NULL, NULL, c_mode);
1779 if ( n_is_inode_locked ) {
1780 /* we've done an indirect->direct conversion. when the data block
1781 ** was freed, it was removed from the list of blocks that must
1782 ** be flushed before the transaction commits, make sure to
1783 ** unmap and invalidate it
1785 unmap_buffers(page, tail_pos);
1786 REISERFS_I(p_s_inode)->i_flags &= ~i_pack_on_close_mask ;
1788 #ifdef REISERQUOTA_DEBUG
1789 reiserfs_debug (p_s_inode->i_sb, "reiserquota cut_from_item(): freeing %u id=%u type=%c", quota_cut_bytes, p_s_inode->i_uid, '?');
1791 DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes);
1795 static void truncate_directory (struct reiserfs_transaction_handle *th, struct inode * inode)
1797 BUG_ON (!th->t_trans_id);
1799 reiserfs_warning (inode->i_sb,
1800 "vs-5655: truncate_directory: link count != 0");
1802 set_le_key_k_offset (KEY_FORMAT_3_5, INODE_PKEY (inode), DOT_OFFSET);
1803 set_le_key_k_type (KEY_FORMAT_3_5, INODE_PKEY (inode), TYPE_DIRENTRY);
1804 reiserfs_delete_solid_item (th, inode, INODE_PKEY (inode));
1805 reiserfs_update_sd(th, inode) ;
1806 set_le_key_k_offset (KEY_FORMAT_3_5, INODE_PKEY (inode), SD_OFFSET);
1807 set_le_key_k_type (KEY_FORMAT_3_5, INODE_PKEY (inode), TYPE_STAT_DATA);
1813 /* Truncate file to the new size. Note, this must be called with a transaction
1815 int reiserfs_do_truncate (struct reiserfs_transaction_handle *th,
1816 struct inode * p_s_inode, /* ->i_size contains new
1818 struct page *page, /* up to date for last block */
1819 int update_timestamps /* when it is called by
1820 file_release to convert
1821 the tail - no timestamps
1822 should be updated */
1824 INITIALIZE_PATH (s_search_path); /* Path to the current object item. */
1825 struct item_head * p_le_ih; /* Pointer to an item header. */
1826 struct cpu_key s_item_key; /* Key to search for a previous file item. */
1827 loff_t n_file_size, /* Old file size. */
1828 n_new_file_size;/* New file size. */
1829 int n_deleted; /* Number of deleted or truncated bytes. */
1833 BUG_ON (!th->t_trans_id);
1834 if ( ! (S_ISREG(p_s_inode->i_mode) || S_ISDIR(p_s_inode->i_mode) || S_ISLNK(p_s_inode->i_mode)) )
1837 if (S_ISDIR(p_s_inode->i_mode)) {
1838 // deletion of directory - no need to update timestamps
1839 truncate_directory (th, p_s_inode);
1843 /* Get new file size. */
1844 n_new_file_size = p_s_inode->i_size;
1846 // FIXME: note, that key type is unimportant here
1847 make_cpu_key (&s_item_key, p_s_inode, max_reiserfs_offset (p_s_inode), TYPE_DIRECT, 3);
1849 retval = search_for_position_by_key(p_s_inode->i_sb, &s_item_key, &s_search_path);
1850 if (retval == IO_ERROR) {
1851 reiserfs_warning (p_s_inode->i_sb, "vs-5657: reiserfs_do_truncate: "
1852 "i/o failure occurred trying to truncate %K", &s_item_key);
1856 if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) {
1857 reiserfs_warning (p_s_inode->i_sb, "PAP-5660: reiserfs_do_truncate: "
1858 "wrong result %d of search for %K", retval, &s_item_key);
1864 s_search_path.pos_in_item --;
1866 /* Get real file size (total length of all file items) */
1867 p_le_ih = PATH_PITEM_HEAD(&s_search_path);
1868 if ( is_statdata_le_ih (p_le_ih) )
1871 loff_t offset = le_ih_k_offset (p_le_ih);
1872 int bytes = op_bytes_number (p_le_ih,p_s_inode->i_sb->s_blocksize);
1874 /* this may mismatch with real file size: if last direct item
1875 had no padding zeros and last unformatted node had no free
1876 space, this file would have this file size */
1877 n_file_size = offset + bytes - 1;
1880 * are we doing a full truncate or delete, if so
1881 * kick in the reada code
1883 if (n_new_file_size == 0)
1884 s_search_path.reada = PATH_READA | PATH_READA_BACK;
1886 if ( n_file_size == 0 || n_file_size < n_new_file_size ) {
1887 goto update_and_out ;
1890 /* Update key to search for the last file item. */
1891 set_cpu_key_k_offset (&s_item_key, n_file_size);
1894 /* Cut or delete file item. */
1895 n_deleted = reiserfs_cut_from_item(th, &s_search_path, &s_item_key, p_s_inode, page, n_new_file_size);
1896 if (n_deleted < 0) {
1897 reiserfs_warning (p_s_inode->i_sb, "vs-5665: reiserfs_do_truncate: reiserfs_cut_from_item failed");
1898 reiserfs_check_path(&s_search_path) ;
1902 RFALSE( n_deleted > n_file_size,
1903 "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K",
1904 n_deleted, n_file_size, &s_item_key);
1906 /* Change key to search the last file item. */
1907 n_file_size -= n_deleted;
1909 set_cpu_key_k_offset (&s_item_key, n_file_size);
1911 /* While there are bytes to truncate and previous file item is presented in the tree. */
1914 ** This loop could take a really long time, and could log
1915 ** many more blocks than a transaction can hold. So, we do a polite
1916 ** journal end here, and if the transaction needs ending, we make
1917 ** sure the file is consistent before ending the current trans
1918 ** and starting a new one
1920 if (journal_transaction_should_end(th, th->t_blocks_allocated)) {
1921 int orig_len_alloc = th->t_blocks_allocated ;
1922 decrement_counters_in_path(&s_search_path) ;
1924 if (update_timestamps) {
1925 p_s_inode->i_mtime = p_s_inode->i_ctime = CURRENT_TIME;
1927 reiserfs_update_sd(th, p_s_inode) ;
1929 err = journal_end(th, p_s_inode->i_sb, orig_len_alloc) ;
1932 err = journal_begin (th, p_s_inode->i_sb,
1933 JOURNAL_PER_BALANCE_CNT * 6);
1936 reiserfs_update_inode_transaction(p_s_inode) ;
1938 } while ( n_file_size > ROUND_UP (n_new_file_size) &&
1939 search_for_position_by_key(p_s_inode->i_sb, &s_item_key, &s_search_path) == POSITION_FOUND ) ;
1941 RFALSE( n_file_size > ROUND_UP (n_new_file_size),
1942 "PAP-5680: truncate did not finish: new_file_size %Ld, current %Ld, oid %d",
1943 n_new_file_size, n_file_size, s_item_key.on_disk_key.k_objectid);
1946 if (update_timestamps) {
1947 // this is truncate, not file closing
1948 p_s_inode->i_mtime = p_s_inode->i_ctime = CURRENT_TIME;
1950 reiserfs_update_sd (th, p_s_inode);
1953 pathrelse(&s_search_path) ;
1958 #ifdef CONFIG_REISERFS_CHECK
1959 // this makes sure, that we __append__, not overwrite or add holes
1960 static void check_research_for_paste (struct path * path,
1961 const struct cpu_key * p_s_key)
1963 struct item_head * found_ih = get_ih (path);
1965 if (is_direct_le_ih (found_ih)) {
1966 if (le_ih_k_offset (found_ih) + op_bytes_number (found_ih, get_last_bh (path)->b_size) !=
1967 cpu_key_k_offset (p_s_key) ||
1968 op_bytes_number (found_ih, get_last_bh (path)->b_size) != pos_in_item (path))
1969 reiserfs_panic (NULL, "PAP-5720: check_research_for_paste: "
1970 "found direct item %h or position (%d) does not match to key %K",
1971 found_ih, pos_in_item (path), p_s_key);
1973 if (is_indirect_le_ih (found_ih)) {
1974 if (le_ih_k_offset (found_ih) + op_bytes_number (found_ih, get_last_bh (path)->b_size) != cpu_key_k_offset (p_s_key) ||
1975 I_UNFM_NUM (found_ih) != pos_in_item (path) ||
1976 get_ih_free_space (found_ih) != 0)
1977 reiserfs_panic (NULL, "PAP-5730: check_research_for_paste: "
1978 "found indirect item (%h) or position (%d) does not match to key (%K)",
1979 found_ih, pos_in_item (path), p_s_key);
1982 #endif /* config reiserfs check */
1985 /* Paste bytes to the existing item. Returns bytes number pasted into the item. */
1986 int reiserfs_paste_into_item (struct reiserfs_transaction_handle *th,
1987 struct path * p_s_search_path, /* Path to the pasted item. */
1988 const struct cpu_key * p_s_key, /* Key to search for the needed item.*/
1989 struct inode * inode, /* Inode item belongs to */
1990 const char * p_c_body, /* Pointer to the bytes to paste. */
1991 int n_pasted_size) /* Size of pasted bytes. */
1993 struct tree_balance s_paste_balance;
1997 BUG_ON (!th->t_trans_id);
1999 fs_gen = get_generation(inode->i_sb) ;
2001 #ifdef REISERQUOTA_DEBUG
2002 reiserfs_debug (inode->i_sb, "reiserquota paste_into_item(): allocating %u id=%u type=%c", n_pasted_size, inode->i_uid, key2type(&(p_s_key->on_disk_key)));
2005 if (DQUOT_ALLOC_SPACE_NODIRTY(inode, n_pasted_size)) {
2006 pathrelse(p_s_search_path);
2009 init_tb_struct(th, &s_paste_balance, th->t_super, p_s_search_path, n_pasted_size);
2010 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
2011 s_paste_balance.key = p_s_key->on_disk_key;
2014 /* DQUOT_* can schedule, must check before the fix_nodes */
2015 if (fs_changed(fs_gen, inode->i_sb)) {
2019 while ((retval = fix_nodes(M_PASTE, &s_paste_balance, NULL, p_c_body)) ==
2022 /* file system changed while we were in the fix_nodes */
2023 PROC_INFO_INC( th -> t_super, paste_into_item_restarted );
2024 retval = search_for_position_by_key (th->t_super, p_s_key, p_s_search_path);
2025 if (retval == IO_ERROR) {
2029 if (retval == POSITION_FOUND) {
2030 reiserfs_warning (inode->i_sb, "PAP-5710: reiserfs_paste_into_item: entry or pasted byte (%K) exists", p_s_key);
2035 #ifdef CONFIG_REISERFS_CHECK
2036 check_research_for_paste (p_s_search_path, p_s_key);
2040 /* Perform balancing after all resources are collected by fix_nodes, and
2041 accessing them will not risk triggering schedule. */
2042 if ( retval == CARRY_ON ) {
2043 do_balance(&s_paste_balance, NULL/*ih*/, p_c_body, M_PASTE);
2046 retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
2048 /* this also releases the path */
2049 unfix_nodes(&s_paste_balance);
2050 #ifdef REISERQUOTA_DEBUG
2051 reiserfs_debug (inode->i_sb, "reiserquota paste_into_item(): freeing %u id=%u type=%c", n_pasted_size, inode->i_uid, key2type(&(p_s_key->on_disk_key)));
2053 DQUOT_FREE_SPACE_NODIRTY(inode, n_pasted_size);
2058 /* Insert new item into the buffer at the path. */
2059 int reiserfs_insert_item(struct reiserfs_transaction_handle *th,
2060 struct path * p_s_path, /* Path to the inserteded item. */
2061 const struct cpu_key * key,
2062 struct item_head * p_s_ih, /* Pointer to the item header to insert.*/
2063 struct inode * inode,
2064 const char * p_c_body) /* Pointer to the bytes to insert. */
2066 struct tree_balance s_ins_balance;
2069 int quota_bytes = 0 ;
2071 BUG_ON (!th->t_trans_id);
2073 if (inode) { /* Do we count quotas for item? */
2074 fs_gen = get_generation(inode->i_sb);
2075 quota_bytes = ih_item_len(p_s_ih);
2077 /* hack so the quota code doesn't have to guess if the file has
2078 ** a tail, links are always tails, so there's no guessing needed
2080 if (!S_ISLNK (inode->i_mode) && is_direct_le_ih(p_s_ih)) {
2081 quota_bytes = inode->i_sb->s_blocksize + UNFM_P_SIZE ;
2083 #ifdef REISERQUOTA_DEBUG
2084 reiserfs_debug (inode->i_sb, "reiserquota insert_item(): allocating %u id=%u type=%c", quota_bytes, inode->i_uid, head2type(p_s_ih));
2086 /* We can't dirty inode here. It would be immediately written but
2087 * appropriate stat item isn't inserted yet... */
2088 if (DQUOT_ALLOC_SPACE_NODIRTY(inode, quota_bytes)) {
2089 pathrelse(p_s_path);
2093 init_tb_struct(th, &s_ins_balance, th->t_super, p_s_path, IH_SIZE + ih_item_len(p_s_ih));
2094 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
2095 s_ins_balance.key = key->on_disk_key;
2097 /* DQUOT_* can schedule, must check to be sure calling fix_nodes is safe */
2098 if (inode && fs_changed(fs_gen, inode->i_sb)) {
2102 while ( (retval = fix_nodes(M_INSERT, &s_ins_balance, p_s_ih, p_c_body)) == REPEAT_SEARCH) {
2104 /* file system changed while we were in the fix_nodes */
2105 PROC_INFO_INC( th -> t_super, insert_item_restarted );
2106 retval = search_item (th->t_super, key, p_s_path);
2107 if (retval == IO_ERROR) {
2111 if (retval == ITEM_FOUND) {
2112 reiserfs_warning (th->t_super, "PAP-5760: reiserfs_insert_item: "
2113 "key %K already exists in the tree", key);
2119 /* make balancing after all resources will be collected at a time */
2120 if ( retval == CARRY_ON ) {
2121 do_balance (&s_ins_balance, p_s_ih, p_c_body, M_INSERT);
2125 retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
2127 /* also releases the path */
2128 unfix_nodes(&s_ins_balance);
2129 #ifdef REISERQUOTA_DEBUG
2130 reiserfs_debug (th->t_super, "reiserquota insert_item(): freeing %u id=%u type=%c", quota_bytes, inode->i_uid, head2type(p_s_ih));
2133 DQUOT_FREE_SPACE_NODIRTY(inode, quota_bytes) ;