xref: /openbmc/linux/fs/reiserfs/stree.c (revision e868d61272caa648214046a096e5a6bfc068dc8c)
1 /*
2  *  Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3  */
4 
5 /*
6  *  Written by Anatoly P. Pinchuk pap@namesys.botik.ru
7  *  Programm System Institute
8  *  Pereslavl-Zalessky Russia
9  */
10 
11 /*
12  *  This file contains functions dealing with S+tree
13  *
14  * B_IS_IN_TREE
15  * copy_item_head
16  * comp_short_keys
17  * comp_keys
18  * comp_short_le_keys
19  * le_key2cpu_key
20  * comp_le_keys
21  * bin_search
22  * get_lkey
23  * get_rkey
24  * key_in_buffer
25  * decrement_bcount
26  * decrement_counters_in_path
27  * reiserfs_check_path
28  * pathrelse_and_restore
29  * pathrelse
30  * search_by_key_reada
31  * search_by_key
32  * search_for_position_by_key
33  * comp_items
34  * prepare_for_direct_item
35  * prepare_for_direntry_item
36  * prepare_for_delete_or_cut
37  * calc_deleted_bytes_number
38  * init_tb_struct
39  * padd_item
40  * reiserfs_delete_item
41  * reiserfs_delete_solid_item
42  * reiserfs_delete_object
43  * maybe_indirect_to_direct
44  * indirect_to_direct_roll_back
45  * reiserfs_cut_from_item
46  * truncate_directory
47  * reiserfs_do_truncate
48  * reiserfs_paste_into_item
49  * reiserfs_insert_item
50  */
51 
52 #include <linux/time.h>
53 #include <linux/string.h>
54 #include <linux/pagemap.h>
55 #include <linux/reiserfs_fs.h>
56 #include <linux/buffer_head.h>
57 #include <linux/quotaops.h>
58 
59 /* Does the buffer contain a disk block which is in the tree. */
60 inline int B_IS_IN_TREE(const struct buffer_head *p_s_bh)
61 {
62 
63 	RFALSE(B_LEVEL(p_s_bh) > MAX_HEIGHT,
64 	       "PAP-1010: block (%b) has too big level (%z)", p_s_bh, p_s_bh);
65 
66 	return (B_LEVEL(p_s_bh) != FREE_LEVEL);
67 }
68 
69 //
70 // to gets item head in le form
71 //
72 inline void copy_item_head(struct item_head *p_v_to,
73 			   const struct item_head *p_v_from)
74 {
75 	memcpy(p_v_to, p_v_from, IH_SIZE);
76 }
77 
78 /* k1 is pointer to on-disk structure which is stored in little-endian
79    form. k2 is pointer to cpu variable. For key of items of the same
80    object this returns 0.
81    Returns: -1 if key1 < key2
82    0 if key1 == key2
83    1 if key1 > key2 */
84 inline int comp_short_keys(const struct reiserfs_key *le_key,
85 			   const struct cpu_key *cpu_key)
86 {
87 	__u32 n;
88 	n = le32_to_cpu(le_key->k_dir_id);
89 	if (n < cpu_key->on_disk_key.k_dir_id)
90 		return -1;
91 	if (n > cpu_key->on_disk_key.k_dir_id)
92 		return 1;
93 	n = le32_to_cpu(le_key->k_objectid);
94 	if (n < cpu_key->on_disk_key.k_objectid)
95 		return -1;
96 	if (n > cpu_key->on_disk_key.k_objectid)
97 		return 1;
98 	return 0;
99 }
100 
101 /* k1 is pointer to on-disk structure which is stored in little-endian
102    form. k2 is pointer to cpu variable.
103    Compare keys using all 4 key fields.
104    Returns: -1 if key1 < key2 0
105    if key1 = key2 1 if key1 > key2 */
106 static inline int comp_keys(const struct reiserfs_key *le_key,
107 			    const struct cpu_key *cpu_key)
108 {
109 	int retval;
110 
111 	retval = comp_short_keys(le_key, cpu_key);
112 	if (retval)
113 		return retval;
114 	if (le_key_k_offset(le_key_version(le_key), le_key) <
115 	    cpu_key_k_offset(cpu_key))
116 		return -1;
117 	if (le_key_k_offset(le_key_version(le_key), le_key) >
118 	    cpu_key_k_offset(cpu_key))
119 		return 1;
120 
121 	if (cpu_key->key_length == 3)
122 		return 0;
123 
124 	/* this part is needed only when tail conversion is in progress */
125 	if (le_key_k_type(le_key_version(le_key), le_key) <
126 	    cpu_key_k_type(cpu_key))
127 		return -1;
128 
129 	if (le_key_k_type(le_key_version(le_key), le_key) >
130 	    cpu_key_k_type(cpu_key))
131 		return 1;
132 
133 	return 0;
134 }
135 
136 inline int comp_short_le_keys(const struct reiserfs_key *key1,
137 			      const struct reiserfs_key *key2)
138 {
139 	__u32 *p_s_1_u32, *p_s_2_u32;
140 	int n_key_length = REISERFS_SHORT_KEY_LEN;
141 
142 	p_s_1_u32 = (__u32 *) key1;
143 	p_s_2_u32 = (__u32 *) key2;
144 	for (; n_key_length--; ++p_s_1_u32, ++p_s_2_u32) {
145 		if (le32_to_cpu(*p_s_1_u32) < le32_to_cpu(*p_s_2_u32))
146 			return -1;
147 		if (le32_to_cpu(*p_s_1_u32) > le32_to_cpu(*p_s_2_u32))
148 			return 1;
149 	}
150 	return 0;
151 }
152 
153 inline void le_key2cpu_key(struct cpu_key *to, const struct reiserfs_key *from)
154 {
155 	int version;
156 	to->on_disk_key.k_dir_id = le32_to_cpu(from->k_dir_id);
157 	to->on_disk_key.k_objectid = le32_to_cpu(from->k_objectid);
158 
159 	// find out version of the key
160 	version = le_key_version(from);
161 	to->version = version;
162 	to->on_disk_key.k_offset = le_key_k_offset(version, from);
163 	to->on_disk_key.k_type = le_key_k_type(version, from);
164 }
165 
166 // this does not say which one is bigger, it only returns 1 if keys
167 // are not equal, 0 otherwise
168 inline int comp_le_keys(const struct reiserfs_key *k1,
169 			const struct reiserfs_key *k2)
170 {
171 	return memcmp(k1, k2, sizeof(struct reiserfs_key));
172 }
173 
174 /**************************************************************************
175  *  Binary search toolkit function                                        *
176  *  Search for an item in the array by the item key                       *
177  *  Returns:    1 if found,  0 if not found;                              *
178  *        *p_n_pos = number of the searched element if found, else the    *
179  *        number of the first element that is larger than p_v_key.        *
180  **************************************************************************/
181 /* For those not familiar with binary search: n_lbound is the leftmost item that it
182  could be, n_rbound the rightmost item that it could be.  We examine the item
183  halfway between n_lbound and n_rbound, and that tells us either that we can increase
184  n_lbound, or decrease n_rbound, or that we have found it, or if n_lbound <= n_rbound that
185  there are no possible items, and we have not found it. With each examination we
186  cut the number of possible items it could be by one more than half rounded down,
187  or we find it. */
188 static inline int bin_search(const void *p_v_key,	/* Key to search for.                   */
189 			     const void *p_v_base,	/* First item in the array.             */
190 			     int p_n_num,	/* Number of items in the array.        */
191 			     int p_n_width,	/* Item size in the array.
192 						   searched. Lest the reader be
193 						   confused, note that this is crafted
194 						   as a general function, and when it
195 						   is applied specifically to the array
196 						   of item headers in a node, p_n_width
197 						   is actually the item header size not
198 						   the item size.                      */
199 			     int *p_n_pos	/* Number of the searched for element. */
200     )
201 {
202 	int n_rbound, n_lbound, n_j;
203 
204 	for (n_j = ((n_rbound = p_n_num - 1) + (n_lbound = 0)) / 2;
205 	     n_lbound <= n_rbound; n_j = (n_rbound + n_lbound) / 2)
206 		switch (comp_keys
207 			((struct reiserfs_key *)((char *)p_v_base +
208 						 n_j * p_n_width),
209 			 (struct cpu_key *)p_v_key)) {
210 		case -1:
211 			n_lbound = n_j + 1;
212 			continue;
213 		case 1:
214 			n_rbound = n_j - 1;
215 			continue;
216 		case 0:
217 			*p_n_pos = n_j;
218 			return ITEM_FOUND;	/* Key found in the array.  */
219 		}
220 
221 	/* bin_search did not find given key, it returns position of key,
222 	   that is minimal and greater than the given one. */
223 	*p_n_pos = n_lbound;
224 	return ITEM_NOT_FOUND;
225 }
226 
227 #ifdef CONFIG_REISERFS_CHECK
228 extern struct tree_balance *cur_tb;
229 #endif
230 
231 /* Minimal possible key. It is never in the tree. */
232 const struct reiserfs_key MIN_KEY = { 0, 0, {{0, 0},} };
233 
234 /* Maximal possible key. It is never in the tree. */
235 static const struct reiserfs_key MAX_KEY = {
236 	__constant_cpu_to_le32(0xffffffff),
237 	__constant_cpu_to_le32(0xffffffff),
238 	{{__constant_cpu_to_le32(0xffffffff),
239 	  __constant_cpu_to_le32(0xffffffff)},}
240 };
241 
242 /* Get delimiting key of the buffer by looking for it in the buffers in the path, starting from the bottom
243    of the path, and going upwards.  We must check the path's validity at each step.  If the key is not in
244    the path, there is no delimiting key in the tree (buffer is first or last buffer in tree), and in this
245    case we return a special key, either MIN_KEY or MAX_KEY. */
246 static inline const struct reiserfs_key *get_lkey(const struct treepath
247 						  *p_s_chk_path,
248 						  const struct super_block
249 						  *p_s_sb)
250 {
251 	int n_position, n_path_offset = p_s_chk_path->path_length;
252 	struct buffer_head *p_s_parent;
253 
254 	RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET,
255 	       "PAP-5010: invalid offset in the path");
256 
257 	/* While not higher in path than first element. */
258 	while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {
259 
260 		RFALSE(!buffer_uptodate
261 		       (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)),
262 		       "PAP-5020: parent is not uptodate");
263 
264 		/* Parent at the path is not in the tree now. */
265 		if (!B_IS_IN_TREE
266 		    (p_s_parent =
267 		     PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)))
268 			return &MAX_KEY;
269 		/* Check whether position in the parent is correct. */
270 		if ((n_position =
271 		     PATH_OFFSET_POSITION(p_s_chk_path,
272 					  n_path_offset)) >
273 		    B_NR_ITEMS(p_s_parent))
274 			return &MAX_KEY;
275 		/* Check whether parent at the path really points to the child. */
276 		if (B_N_CHILD_NUM(p_s_parent, n_position) !=
277 		    PATH_OFFSET_PBUFFER(p_s_chk_path,
278 					n_path_offset + 1)->b_blocknr)
279 			return &MAX_KEY;
280 		/* Return delimiting key if position in the parent is not equal to zero. */
281 		if (n_position)
282 			return B_N_PDELIM_KEY(p_s_parent, n_position - 1);
283 	}
284 	/* Return MIN_KEY if we are in the root of the buffer tree. */
285 	if (PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->
286 	    b_blocknr == SB_ROOT_BLOCK(p_s_sb))
287 		return &MIN_KEY;
288 	return &MAX_KEY;
289 }
290 
291 /* Get delimiting key of the buffer at the path and its right neighbor. */
292 inline const struct reiserfs_key *get_rkey(const struct treepath *p_s_chk_path,
293 					   const struct super_block *p_s_sb)
294 {
295 	int n_position, n_path_offset = p_s_chk_path->path_length;
296 	struct buffer_head *p_s_parent;
297 
298 	RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET,
299 	       "PAP-5030: invalid offset in the path");
300 
301 	while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {
302 
303 		RFALSE(!buffer_uptodate
304 		       (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)),
305 		       "PAP-5040: parent is not uptodate");
306 
307 		/* Parent at the path is not in the tree now. */
308 		if (!B_IS_IN_TREE
309 		    (p_s_parent =
310 		     PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)))
311 			return &MIN_KEY;
312 		/* Check whether position in the parent is correct. */
313 		if ((n_position =
314 		     PATH_OFFSET_POSITION(p_s_chk_path,
315 					  n_path_offset)) >
316 		    B_NR_ITEMS(p_s_parent))
317 			return &MIN_KEY;
318 		/* Check whether parent at the path really points to the child. */
319 		if (B_N_CHILD_NUM(p_s_parent, n_position) !=
320 		    PATH_OFFSET_PBUFFER(p_s_chk_path,
321 					n_path_offset + 1)->b_blocknr)
322 			return &MIN_KEY;
323 		/* Return delimiting key if position in the parent is not the last one. */
324 		if (n_position != B_NR_ITEMS(p_s_parent))
325 			return B_N_PDELIM_KEY(p_s_parent, n_position);
326 	}
327 	/* Return MAX_KEY if we are in the root of the buffer tree. */
328 	if (PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->
329 	    b_blocknr == SB_ROOT_BLOCK(p_s_sb))
330 		return &MAX_KEY;
331 	return &MIN_KEY;
332 }
333 
334 /* Check whether a key is contained in the tree rooted from a buffer at a path. */
335 /* This works by looking at the left and right delimiting keys for the buffer in the last path_element in
336    the path.  These delimiting keys are stored at least one level above that buffer in the tree. If the
337    buffer is the first or last node in the tree order then one of the delimiting keys may be absent, and in
338    this case get_lkey and get_rkey return a special key which is MIN_KEY or MAX_KEY. */
339 static inline int key_in_buffer(struct treepath *p_s_chk_path,	/* Path which should be checked.  */
340 				const struct cpu_key *p_s_key,	/* Key which should be checked.   */
341 				struct super_block *p_s_sb	/* Super block pointer.           */
342     )
343 {
344 
345 	RFALSE(!p_s_key || p_s_chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET
346 	       || p_s_chk_path->path_length > MAX_HEIGHT,
347 	       "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)",
348 	       p_s_key, p_s_chk_path->path_length);
349 	RFALSE(!PATH_PLAST_BUFFER(p_s_chk_path)->b_bdev,
350 	       "PAP-5060: device must not be NODEV");
351 
352 	if (comp_keys(get_lkey(p_s_chk_path, p_s_sb), p_s_key) == 1)
353 		/* left delimiting key is bigger, that the key we look for */
354 		return 0;
355 	//  if ( comp_keys(p_s_key, get_rkey(p_s_chk_path, p_s_sb)) != -1 )
356 	if (comp_keys(get_rkey(p_s_chk_path, p_s_sb), p_s_key) != 1)
357 		/* p_s_key must be less than right delimitiing key */
358 		return 0;
359 	return 1;
360 }
361 
362 inline void decrement_bcount(struct buffer_head *p_s_bh)
363 {
364 	if (p_s_bh) {
365 		if (atomic_read(&(p_s_bh->b_count))) {
366 			put_bh(p_s_bh);
367 			return;
368 		}
369 		reiserfs_panic(NULL,
370 			       "PAP-5070: decrement_bcount: trying to free free buffer %b",
371 			       p_s_bh);
372 	}
373 }
374 
375 /* Decrement b_count field of the all buffers in the path. */
376 void decrement_counters_in_path(struct treepath *p_s_search_path)
377 {
378 	int n_path_offset = p_s_search_path->path_length;
379 
380 	RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET ||
381 	       n_path_offset > EXTENDED_MAX_HEIGHT - 1,
382 	       "PAP-5080: invalid path offset of %d", n_path_offset);
383 
384 	while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) {
385 		struct buffer_head *bh;
386 
387 		bh = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--);
388 		decrement_bcount(bh);
389 	}
390 	p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
391 }
392 
393 int reiserfs_check_path(struct treepath *p)
394 {
395 	RFALSE(p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET,
396 	       "path not properly relsed");
397 	return 0;
398 }
399 
400 /* Release all buffers in the path. Restore dirty bits clean
401 ** when preparing the buffer for the log
402 **
403 ** only called from fix_nodes()
404 */
405 void pathrelse_and_restore(struct super_block *s, struct treepath *p_s_search_path)
406 {
407 	int n_path_offset = p_s_search_path->path_length;
408 
409 	RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
410 	       "clm-4000: invalid path offset");
411 
412 	while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) {
413 		reiserfs_restore_prepared_buffer(s,
414 						 PATH_OFFSET_PBUFFER
415 						 (p_s_search_path,
416 						  n_path_offset));
417 		brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
418 	}
419 	p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
420 }
421 
422 /* Release all buffers in the path. */
423 void pathrelse(struct treepath *p_s_search_path)
424 {
425 	int n_path_offset = p_s_search_path->path_length;
426 
427 	RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
428 	       "PAP-5090: invalid path offset");
429 
430 	while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET)
431 		brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
432 
433 	p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
434 }
435 
436 static int is_leaf(char *buf, int blocksize, struct buffer_head *bh)
437 {
438 	struct block_head *blkh;
439 	struct item_head *ih;
440 	int used_space;
441 	int prev_location;
442 	int i;
443 	int nr;
444 
445 	blkh = (struct block_head *)buf;
446 	if (blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) {
447 		reiserfs_warning(NULL,
448 				 "is_leaf: this should be caught earlier");
449 		return 0;
450 	}
451 
452 	nr = blkh_nr_item(blkh);
453 	if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) {
454 		/* item number is too big or too small */
455 		reiserfs_warning(NULL, "is_leaf: nr_item seems wrong: %z", bh);
456 		return 0;
457 	}
458 	ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1;
459 	used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location(ih));
460 	if (used_space != blocksize - blkh_free_space(blkh)) {
461 		/* free space does not match to calculated amount of use space */
462 		reiserfs_warning(NULL, "is_leaf: free space seems wrong: %z",
463 				 bh);
464 		return 0;
465 	}
466 	// FIXME: it is_leaf will hit performance too much - we may have
467 	// return 1 here
468 
469 	/* check tables of item heads */
470 	ih = (struct item_head *)(buf + BLKH_SIZE);
471 	prev_location = blocksize;
472 	for (i = 0; i < nr; i++, ih++) {
473 		if (le_ih_k_type(ih) == TYPE_ANY) {
474 			reiserfs_warning(NULL,
475 					 "is_leaf: wrong item type for item %h",
476 					 ih);
477 			return 0;
478 		}
479 		if (ih_location(ih) >= blocksize
480 		    || ih_location(ih) < IH_SIZE * nr) {
481 			reiserfs_warning(NULL,
482 					 "is_leaf: item location seems wrong: %h",
483 					 ih);
484 			return 0;
485 		}
486 		if (ih_item_len(ih) < 1
487 		    || ih_item_len(ih) > MAX_ITEM_LEN(blocksize)) {
488 			reiserfs_warning(NULL,
489 					 "is_leaf: item length seems wrong: %h",
490 					 ih);
491 			return 0;
492 		}
493 		if (prev_location - ih_location(ih) != ih_item_len(ih)) {
494 			reiserfs_warning(NULL,
495 					 "is_leaf: item location seems wrong (second one): %h",
496 					 ih);
497 			return 0;
498 		}
499 		prev_location = ih_location(ih);
500 	}
501 
502 	// one may imagine much more checks
503 	return 1;
504 }
505 
506 /* returns 1 if buf looks like an internal node, 0 otherwise */
507 static int is_internal(char *buf, int blocksize, struct buffer_head *bh)
508 {
509 	struct block_head *blkh;
510 	int nr;
511 	int used_space;
512 
513 	blkh = (struct block_head *)buf;
514 	nr = blkh_level(blkh);
515 	if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) {
516 		/* this level is not possible for internal nodes */
517 		reiserfs_warning(NULL,
518 				 "is_internal: this should be caught earlier");
519 		return 0;
520 	}
521 
522 	nr = blkh_nr_item(blkh);
523 	if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) {
524 		/* for internal which is not root we might check min number of keys */
525 		reiserfs_warning(NULL,
526 				 "is_internal: number of key seems wrong: %z",
527 				 bh);
528 		return 0;
529 	}
530 
531 	used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1);
532 	if (used_space != blocksize - blkh_free_space(blkh)) {
533 		reiserfs_warning(NULL,
534 				 "is_internal: free space seems wrong: %z", bh);
535 		return 0;
536 	}
537 	// one may imagine much more checks
538 	return 1;
539 }
540 
541 // make sure that bh contains formatted node of reiserfs tree of
542 // 'level'-th level
543 static int is_tree_node(struct buffer_head *bh, int level)
544 {
545 	if (B_LEVEL(bh) != level) {
546 		reiserfs_warning(NULL,
547 				 "is_tree_node: node level %d does not match to the expected one %d",
548 				 B_LEVEL(bh), level);
549 		return 0;
550 	}
551 	if (level == DISK_LEAF_NODE_LEVEL)
552 		return is_leaf(bh->b_data, bh->b_size, bh);
553 
554 	return is_internal(bh->b_data, bh->b_size, bh);
555 }
556 
557 #define SEARCH_BY_KEY_READA 16
558 
559 /* The function is NOT SCHEDULE-SAFE! */
560 static void search_by_key_reada(struct super_block *s,
561 				struct buffer_head **bh,
562 				unsigned long *b, int num)
563 {
564 	int i, j;
565 
566 	for (i = 0; i < num; i++) {
567 		bh[i] = sb_getblk(s, b[i]);
568 	}
569 	for (j = 0; j < i; j++) {
570 		/*
571 		 * note, this needs attention if we are getting rid of the BKL
572 		 * you have to make sure the prepared bit isn't set on this buffer
573 		 */
574 		if (!buffer_uptodate(bh[j]))
575 			ll_rw_block(READA, 1, bh + j);
576 		brelse(bh[j]);
577 	}
578 }
579 
580 /**************************************************************************
581  * Algorithm   SearchByKey                                                *
582  *             look for item in the Disk S+Tree by its key                *
583  * Input:  p_s_sb   -  super block                                        *
584  *         p_s_key  - pointer to the key to search                        *
585  * Output: ITEM_FOUND, ITEM_NOT_FOUND or IO_ERROR                         *
586  *         p_s_search_path - path from the root to the needed leaf        *
587  **************************************************************************/
588 
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 */
602 /* The function is NOT SCHEDULE-SAFE! */
603 int search_by_key(struct super_block *p_s_sb, const struct cpu_key *p_s_key,	/* Key to search. */
604 		  struct treepath *p_s_search_path,/* This structure was
605 						   allocated and initialized
606 						   by the calling
607 						   function. It is filled up
608 						   by this function.  */
609 		  int n_stop_level	/* How far down the tree to search. To
610 					   stop at leaf level - set to
611 					   DISK_LEAF_NODE_LEVEL */
612     )
613 {
614 	int n_block_number;
615 	int expected_level;
616 	struct buffer_head *p_s_bh;
617 	struct path_element *p_s_last_element;
618 	int n_node_level, n_retval;
619 	int right_neighbor_of_leaf_node;
620 	int fs_gen;
621 	struct buffer_head *reada_bh[SEARCH_BY_KEY_READA];
622 	unsigned long reada_blocks[SEARCH_BY_KEY_READA];
623 	int reada_count = 0;
624 
625 #ifdef CONFIG_REISERFS_CHECK
626 	int n_repeat_counter = 0;
627 #endif
628 
629 	PROC_INFO_INC(p_s_sb, search_by_key);
630 
631 	/* As we add each node to a path we increase its count.  This means that
632 	   we must be careful to release all nodes in a path before we either
633 	   discard the path struct or re-use the path struct, as we do here. */
634 
635 	decrement_counters_in_path(p_s_search_path);
636 
637 	right_neighbor_of_leaf_node = 0;
638 
639 	/* With each iteration of this loop we search through the items in the
640 	   current node, and calculate the next current node(next path element)
641 	   for the next iteration of this loop.. */
642 	n_block_number = SB_ROOT_BLOCK(p_s_sb);
643 	expected_level = -1;
644 	while (1) {
645 
646 #ifdef CONFIG_REISERFS_CHECK
647 		if (!(++n_repeat_counter % 50000))
648 			reiserfs_warning(p_s_sb, "PAP-5100: search_by_key: %s:"
649 					 "there were %d iterations of while loop "
650 					 "looking for key %K",
651 					 current->comm, n_repeat_counter,
652 					 p_s_key);
653 #endif
654 
655 		/* prep path to have another element added to it. */
656 		p_s_last_element =
657 		    PATH_OFFSET_PELEMENT(p_s_search_path,
658 					 ++p_s_search_path->path_length);
659 		fs_gen = get_generation(p_s_sb);
660 
661 		/* Read the next tree node, and set the last element in the path to
662 		   have a pointer to it. */
663 		if ((p_s_bh = p_s_last_element->pe_buffer =
664 		     sb_getblk(p_s_sb, n_block_number))) {
665 			if (!buffer_uptodate(p_s_bh) && reada_count > 1) {
666 				search_by_key_reada(p_s_sb, reada_bh,
667 						    reada_blocks, reada_count);
668 			}
669 			ll_rw_block(READ, 1, &p_s_bh);
670 			wait_on_buffer(p_s_bh);
671 			if (!buffer_uptodate(p_s_bh))
672 				goto io_error;
673 		} else {
674 		      io_error:
675 			p_s_search_path->path_length--;
676 			pathrelse(p_s_search_path);
677 			return IO_ERROR;
678 		}
679 		reada_count = 0;
680 		if (expected_level == -1)
681 			expected_level = SB_TREE_HEIGHT(p_s_sb);
682 		expected_level--;
683 
684 		/* It is possible that schedule occurred. We must check whether the key
685 		   to search is still in the tree rooted from the current buffer. If
686 		   not then repeat search from the root. */
687 		if (fs_changed(fs_gen, p_s_sb) &&
688 		    (!B_IS_IN_TREE(p_s_bh) ||
689 		     B_LEVEL(p_s_bh) != expected_level ||
690 		     !key_in_buffer(p_s_search_path, p_s_key, p_s_sb))) {
691 			PROC_INFO_INC(p_s_sb, search_by_key_fs_changed);
692 			PROC_INFO_INC(p_s_sb, search_by_key_restarted);
693 			PROC_INFO_INC(p_s_sb,
694 				      sbk_restarted[expected_level - 1]);
695 			decrement_counters_in_path(p_s_search_path);
696 
697 			/* Get the root block number so that we can repeat the search
698 			   starting from the root. */
699 			n_block_number = SB_ROOT_BLOCK(p_s_sb);
700 			expected_level = -1;
701 			right_neighbor_of_leaf_node = 0;
702 
703 			/* repeat search from the root */
704 			continue;
705 		}
706 
707 		/* only check that the key is in the buffer if p_s_key is not
708 		   equal to the MAX_KEY. Latter case is only possible in
709 		   "finish_unfinished()" processing during mount. */
710 		RFALSE(comp_keys(&MAX_KEY, p_s_key) &&
711 		       !key_in_buffer(p_s_search_path, p_s_key, p_s_sb),
712 		       "PAP-5130: key is not in the buffer");
713 #ifdef CONFIG_REISERFS_CHECK
714 		if (cur_tb) {
715 			print_cur_tb("5140");
716 			reiserfs_panic(p_s_sb,
717 				       "PAP-5140: search_by_key: schedule occurred in do_balance!");
718 		}
719 #endif
720 
721 		// make sure, that the node contents look like a node of
722 		// certain level
723 		if (!is_tree_node(p_s_bh, expected_level)) {
724 			reiserfs_warning(p_s_sb, "vs-5150: search_by_key: "
725 					 "invalid format found in block %ld. Fsck?",
726 					 p_s_bh->b_blocknr);
727 			pathrelse(p_s_search_path);
728 			return IO_ERROR;
729 		}
730 
731 		/* ok, we have acquired next formatted node in the tree */
732 		n_node_level = B_LEVEL(p_s_bh);
733 
734 		PROC_INFO_BH_STAT(p_s_sb, p_s_bh, n_node_level - 1);
735 
736 		RFALSE(n_node_level < n_stop_level,
737 		       "vs-5152: tree level (%d) is less than stop level (%d)",
738 		       n_node_level, n_stop_level);
739 
740 		n_retval = bin_search(p_s_key, B_N_PITEM_HEAD(p_s_bh, 0),
741 				      B_NR_ITEMS(p_s_bh),
742 				      (n_node_level ==
743 				       DISK_LEAF_NODE_LEVEL) ? IH_SIZE :
744 				      KEY_SIZE,
745 				      &(p_s_last_element->pe_position));
746 		if (n_node_level == n_stop_level) {
747 			return n_retval;
748 		}
749 
750 		/* we are not in the stop level */
751 		if (n_retval == ITEM_FOUND)
752 			/* item has been found, so we choose the pointer which is to the right of the found one */
753 			p_s_last_element->pe_position++;
754 
755 		/* if item was not found we choose the position which is to
756 		   the left of the found item. This requires no code,
757 		   bin_search did it already. */
758 
759 		/* So we have chosen a position in the current node which is
760 		   an internal node.  Now we calculate child block number by
761 		   position in the node. */
762 		n_block_number =
763 		    B_N_CHILD_NUM(p_s_bh, p_s_last_element->pe_position);
764 
765 		/* if we are going to read leaf nodes, try for read ahead as well */
766 		if ((p_s_search_path->reada & PATH_READA) &&
767 		    n_node_level == DISK_LEAF_NODE_LEVEL + 1) {
768 			int pos = p_s_last_element->pe_position;
769 			int limit = B_NR_ITEMS(p_s_bh);
770 			struct reiserfs_key *le_key;
771 
772 			if (p_s_search_path->reada & PATH_READA_BACK)
773 				limit = 0;
774 			while (reada_count < SEARCH_BY_KEY_READA) {
775 				if (pos == limit)
776 					break;
777 				reada_blocks[reada_count++] =
778 				    B_N_CHILD_NUM(p_s_bh, pos);
779 				if (p_s_search_path->reada & PATH_READA_BACK)
780 					pos--;
781 				else
782 					pos++;
783 
784 				/*
785 				 * check to make sure we're in the same object
786 				 */
787 				le_key = B_N_PDELIM_KEY(p_s_bh, pos);
788 				if (le32_to_cpu(le_key->k_objectid) !=
789 				    p_s_key->on_disk_key.k_objectid) {
790 					break;
791 				}
792 			}
793 		}
794 	}
795 }
796 
797 /* Form the path to an item and position in this item which contains
798    file byte defined by p_s_key. If there is no such item
799    corresponding to the key, we point the path to the item with
800    maximal key less than p_s_key, and *p_n_pos_in_item is set to one
801    past the last entry/byte in the item.  If searching for entry in a
802    directory item, and it is not found, *p_n_pos_in_item is set to one
803    entry more than the entry with maximal key which is less than the
804    sought key.
805 
806    Note that if there is no entry in this same node which is one more,
807    then we point to an imaginary entry.  for direct items, the
808    position is in units of bytes, for indirect items the position is
809    in units of blocknr entries, for directory items the position is in
810    units of directory entries.  */
811 
812 /* The function is NOT SCHEDULE-SAFE! */
813 int search_for_position_by_key(struct super_block *p_s_sb,	/* Pointer to the super block.          */
814 			       const struct cpu_key *p_cpu_key,	/* Key to search (cpu variable)         */
815 			       struct treepath *p_s_search_path	/* Filled up by this function.          */
816     )
817 {
818 	struct item_head *p_le_ih;	/* pointer to on-disk structure */
819 	int n_blk_size;
820 	loff_t item_offset, offset;
821 	struct reiserfs_dir_entry de;
822 	int retval;
823 
824 	/* If searching for directory entry. */
825 	if (is_direntry_cpu_key(p_cpu_key))
826 		return search_by_entry_key(p_s_sb, p_cpu_key, p_s_search_path,
827 					   &de);
828 
829 	/* If not searching for directory entry. */
830 
831 	/* If item is found. */
832 	retval = search_item(p_s_sb, p_cpu_key, p_s_search_path);
833 	if (retval == IO_ERROR)
834 		return retval;
835 	if (retval == ITEM_FOUND) {
836 
837 		RFALSE(!ih_item_len
838 		       (B_N_PITEM_HEAD
839 			(PATH_PLAST_BUFFER(p_s_search_path),
840 			 PATH_LAST_POSITION(p_s_search_path))),
841 		       "PAP-5165: item length equals zero");
842 
843 		pos_in_item(p_s_search_path) = 0;
844 		return POSITION_FOUND;
845 	}
846 
847 	RFALSE(!PATH_LAST_POSITION(p_s_search_path),
848 	       "PAP-5170: position equals zero");
849 
850 	/* Item is not found. Set path to the previous item. */
851 	p_le_ih =
852 	    B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path),
853 			   --PATH_LAST_POSITION(p_s_search_path));
854 	n_blk_size = p_s_sb->s_blocksize;
855 
856 	if (comp_short_keys(&(p_le_ih->ih_key), p_cpu_key)) {
857 		return FILE_NOT_FOUND;
858 	}
859 	// FIXME: quite ugly this far
860 
861 	item_offset = le_ih_k_offset(p_le_ih);
862 	offset = cpu_key_k_offset(p_cpu_key);
863 
864 	/* Needed byte is contained in the item pointed to by the path. */
865 	if (item_offset <= offset &&
866 	    item_offset + op_bytes_number(p_le_ih, n_blk_size) > offset) {
867 		pos_in_item(p_s_search_path) = offset - item_offset;
868 		if (is_indirect_le_ih(p_le_ih)) {
869 			pos_in_item(p_s_search_path) /= n_blk_size;
870 		}
871 		return POSITION_FOUND;
872 	}
873 
874 	/* Needed byte is not contained in the item pointed to by the
875 	   path. Set pos_in_item out of the item. */
876 	if (is_indirect_le_ih(p_le_ih))
877 		pos_in_item(p_s_search_path) =
878 		    ih_item_len(p_le_ih) / UNFM_P_SIZE;
879 	else
880 		pos_in_item(p_s_search_path) = ih_item_len(p_le_ih);
881 
882 	return POSITION_NOT_FOUND;
883 }
884 
885 /* Compare given item and item pointed to by the path. */
886 int comp_items(const struct item_head *stored_ih, const struct treepath *p_s_path)
887 {
888 	struct buffer_head *p_s_bh;
889 	struct item_head *ih;
890 
891 	/* Last buffer at the path is not in the tree. */
892 	if (!B_IS_IN_TREE(p_s_bh = PATH_PLAST_BUFFER(p_s_path)))
893 		return 1;
894 
895 	/* Last path position is invalid. */
896 	if (PATH_LAST_POSITION(p_s_path) >= B_NR_ITEMS(p_s_bh))
897 		return 1;
898 
899 	/* we need only to know, whether it is the same item */
900 	ih = get_ih(p_s_path);
901 	return memcmp(stored_ih, ih, IH_SIZE);
902 }
903 
904 /* unformatted nodes are not logged anymore, ever.  This is safe
905 ** now
906 */
907 #define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1)
908 
909 // block can not be forgotten as it is in I/O or held by someone
910 #define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh)))
911 
912 // prepare for delete or cut of direct item
913 static inline int prepare_for_direct_item(struct treepath *path,
914 					  struct item_head *le_ih,
915 					  struct inode *inode,
916 					  loff_t new_file_length, int *cut_size)
917 {
918 	loff_t round_len;
919 
920 	if (new_file_length == max_reiserfs_offset(inode)) {
921 		/* item has to be deleted */
922 		*cut_size = -(IH_SIZE + ih_item_len(le_ih));
923 		return M_DELETE;
924 	}
925 	// new file gets truncated
926 	if (get_inode_item_key_version(inode) == KEY_FORMAT_3_6) {
927 		//
928 		round_len = ROUND_UP(new_file_length);
929 		/* this was n_new_file_length < le_ih ... */
930 		if (round_len < le_ih_k_offset(le_ih)) {
931 			*cut_size = -(IH_SIZE + ih_item_len(le_ih));
932 			return M_DELETE;	/* Delete this item. */
933 		}
934 		/* Calculate first position and size for cutting from item. */
935 		pos_in_item(path) = round_len - (le_ih_k_offset(le_ih) - 1);
936 		*cut_size = -(ih_item_len(le_ih) - pos_in_item(path));
937 
938 		return M_CUT;	/* Cut from this item. */
939 	}
940 
941 	// old file: items may have any length
942 
943 	if (new_file_length < le_ih_k_offset(le_ih)) {
944 		*cut_size = -(IH_SIZE + ih_item_len(le_ih));
945 		return M_DELETE;	/* Delete this item. */
946 	}
947 	/* Calculate first position and size for cutting from item. */
948 	*cut_size = -(ih_item_len(le_ih) -
949 		      (pos_in_item(path) =
950 		       new_file_length + 1 - le_ih_k_offset(le_ih)));
951 	return M_CUT;		/* Cut from this item. */
952 }
953 
954 static inline int prepare_for_direntry_item(struct treepath *path,
955 					    struct item_head *le_ih,
956 					    struct inode *inode,
957 					    loff_t new_file_length,
958 					    int *cut_size)
959 {
960 	if (le_ih_k_offset(le_ih) == DOT_OFFSET &&
961 	    new_file_length == max_reiserfs_offset(inode)) {
962 		RFALSE(ih_entry_count(le_ih) != 2,
963 		       "PAP-5220: incorrect empty directory item (%h)", le_ih);
964 		*cut_size = -(IH_SIZE + ih_item_len(le_ih));
965 		return M_DELETE;	/* Delete the directory item containing "." and ".." entry. */
966 	}
967 
968 	if (ih_entry_count(le_ih) == 1) {
969 		/* Delete the directory item such as there is one record only
970 		   in this item */
971 		*cut_size = -(IH_SIZE + ih_item_len(le_ih));
972 		return M_DELETE;
973 	}
974 
975 	/* Cut one record from the directory item. */
976 	*cut_size =
977 	    -(DEH_SIZE +
978 	      entry_length(get_last_bh(path), le_ih, pos_in_item(path)));
979 	return M_CUT;
980 }
981 
982 #define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1)
983 
984 /*  If the path points to a directory or direct item, calculate mode and the size cut, for balance.
985     If the path points to an indirect item, remove some number of its unformatted nodes.
986     In case of file truncate calculate whether this item must be deleted/truncated or last
987     unformatted node of this item will be converted to a direct item.
988     This function returns a determination of what balance mode the calling function should employ. */
989 static char prepare_for_delete_or_cut(struct reiserfs_transaction_handle *th, struct inode *inode, struct treepath *p_s_path, const struct cpu_key *p_s_item_key, int *p_n_removed,	/* Number of unformatted nodes which were removed
990 																						   from end of the file. */
991 				      int *p_n_cut_size, unsigned long long n_new_file_length	/* MAX_KEY_OFFSET in case of delete. */
992     )
993 {
994 	struct super_block *p_s_sb = inode->i_sb;
995 	struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_path);
996 	struct buffer_head *p_s_bh = PATH_PLAST_BUFFER(p_s_path);
997 
998 	BUG_ON(!th->t_trans_id);
999 
1000 	/* Stat_data item. */
1001 	if (is_statdata_le_ih(p_le_ih)) {
1002 
1003 		RFALSE(n_new_file_length != max_reiserfs_offset(inode),
1004 		       "PAP-5210: mode must be M_DELETE");
1005 
1006 		*p_n_cut_size = -(IH_SIZE + ih_item_len(p_le_ih));
1007 		return M_DELETE;
1008 	}
1009 
1010 	/* Directory item. */
1011 	if (is_direntry_le_ih(p_le_ih))
1012 		return prepare_for_direntry_item(p_s_path, p_le_ih, inode,
1013 						 n_new_file_length,
1014 						 p_n_cut_size);
1015 
1016 	/* Direct item. */
1017 	if (is_direct_le_ih(p_le_ih))
1018 		return prepare_for_direct_item(p_s_path, p_le_ih, inode,
1019 					       n_new_file_length, p_n_cut_size);
1020 
1021 	/* Case of an indirect item. */
1022 	{
1023 	    int blk_size = p_s_sb->s_blocksize;
1024 	    struct item_head s_ih;
1025 	    int need_re_search;
1026 	    int delete = 0;
1027 	    int result = M_CUT;
1028 	    int pos = 0;
1029 
1030 	    if ( n_new_file_length == max_reiserfs_offset (inode) ) {
1031 		/* prepare_for_delete_or_cut() is called by
1032 		 * reiserfs_delete_item() */
1033 		n_new_file_length = 0;
1034 		delete = 1;
1035 	    }
1036 
1037 	    do {
1038 		need_re_search = 0;
1039 		*p_n_cut_size = 0;
1040 		p_s_bh = PATH_PLAST_BUFFER(p_s_path);
1041 		copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
1042 		pos = I_UNFM_NUM(&s_ih);
1043 
1044 		while (le_ih_k_offset (&s_ih) + (pos - 1) * blk_size > n_new_file_length) {
1045 		    __u32 *unfm, block;
1046 
1047 		    /* Each unformatted block deletion may involve one additional
1048 		     * bitmap block into the transaction, thereby the initial
1049 		     * journal space reservation might not be enough. */
1050 		    if (!delete && (*p_n_cut_size) != 0 &&
1051 			reiserfs_transaction_free_space(th) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) {
1052 			break;
1053 		    }
1054 
1055 		    unfm = (__u32 *)B_I_PITEM(p_s_bh, &s_ih) + pos - 1;
1056 		    block = get_block_num(unfm, 0);
1057 
1058 		    if (block != 0) {
1059 			reiserfs_prepare_for_journal(p_s_sb, p_s_bh, 1);
1060 			put_block_num(unfm, 0, 0);
1061 			journal_mark_dirty (th, p_s_sb, p_s_bh);
1062 			reiserfs_free_block(th, inode, block, 1);
1063 		    }
1064 
1065 		    cond_resched();
1066 
1067 		    if (item_moved (&s_ih, p_s_path))  {
1068 			need_re_search = 1;
1069 			break;
1070 		    }
1071 
1072 		    pos --;
1073 		    (*p_n_removed) ++;
1074 		    (*p_n_cut_size) -= UNFM_P_SIZE;
1075 
1076 		    if (pos == 0) {
1077 			(*p_n_cut_size) -= IH_SIZE;
1078 			result = M_DELETE;
1079 			break;
1080 		    }
1081 		}
1082 		/* a trick.  If the buffer has been logged, this will do nothing.  If
1083 		** we've broken the loop without logging it, it will restore the
1084 		** buffer */
1085 		reiserfs_restore_prepared_buffer(p_s_sb, p_s_bh);
1086 	    } while (need_re_search &&
1087 		     search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path) == POSITION_FOUND);
1088 	    pos_in_item(p_s_path) = pos * UNFM_P_SIZE;
1089 
1090 	    if (*p_n_cut_size == 0) {
1091 		/* Nothing were cut. maybe convert last unformatted node to the
1092 		 * direct item? */
1093 		result = M_CONVERT;
1094 	    }
1095 	    return result;
1096 	}
1097 }
1098 
1099 /* Calculate number of bytes which will be deleted or cut during balance */
1100 static int calc_deleted_bytes_number(struct tree_balance *p_s_tb, char c_mode)
1101 {
1102 	int n_del_size;
1103 	struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_tb->tb_path);
1104 
1105 	if (is_statdata_le_ih(p_le_ih))
1106 		return 0;
1107 
1108 	n_del_size =
1109 	    (c_mode ==
1110 	     M_DELETE) ? ih_item_len(p_le_ih) : -p_s_tb->insert_size[0];
1111 	if (is_direntry_le_ih(p_le_ih)) {
1112 		// return EMPTY_DIR_SIZE; /* We delete emty directoris only. */
1113 		// we can't use EMPTY_DIR_SIZE, as old format dirs have a different
1114 		// empty size.  ick. FIXME, is this right?
1115 		//
1116 		return n_del_size;
1117 	}
1118 
1119 	if (is_indirect_le_ih(p_le_ih))
1120 		n_del_size = (n_del_size / UNFM_P_SIZE) * (PATH_PLAST_BUFFER(p_s_tb->tb_path)->b_size);	// - get_ih_free_space (p_le_ih);
1121 	return n_del_size;
1122 }
1123 
1124 static void init_tb_struct(struct reiserfs_transaction_handle *th,
1125 			   struct tree_balance *p_s_tb,
1126 			   struct super_block *p_s_sb,
1127 			   struct treepath *p_s_path, int n_size)
1128 {
1129 
1130 	BUG_ON(!th->t_trans_id);
1131 
1132 	memset(p_s_tb, '\0', sizeof(struct tree_balance));
1133 	p_s_tb->transaction_handle = th;
1134 	p_s_tb->tb_sb = p_s_sb;
1135 	p_s_tb->tb_path = p_s_path;
1136 	PATH_OFFSET_PBUFFER(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL;
1137 	PATH_OFFSET_POSITION(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0;
1138 	p_s_tb->insert_size[0] = n_size;
1139 }
1140 
1141 void padd_item(char *item, int total_length, int length)
1142 {
1143 	int i;
1144 
1145 	for (i = total_length; i > length;)
1146 		item[--i] = 0;
1147 }
1148 
1149 #ifdef REISERQUOTA_DEBUG
1150 char key2type(struct reiserfs_key *ih)
1151 {
1152 	if (is_direntry_le_key(2, ih))
1153 		return 'd';
1154 	if (is_direct_le_key(2, ih))
1155 		return 'D';
1156 	if (is_indirect_le_key(2, ih))
1157 		return 'i';
1158 	if (is_statdata_le_key(2, ih))
1159 		return 's';
1160 	return 'u';
1161 }
1162 
1163 char head2type(struct item_head *ih)
1164 {
1165 	if (is_direntry_le_ih(ih))
1166 		return 'd';
1167 	if (is_direct_le_ih(ih))
1168 		return 'D';
1169 	if (is_indirect_le_ih(ih))
1170 		return 'i';
1171 	if (is_statdata_le_ih(ih))
1172 		return 's';
1173 	return 'u';
1174 }
1175 #endif
1176 
1177 /* Delete object item. */
1178 int reiserfs_delete_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_path,	/* Path to the deleted item. */
1179 			 const struct cpu_key *p_s_item_key,	/* Key to search for the deleted item.  */
1180 			 struct inode *p_s_inode,	/* inode is here just to update i_blocks and quotas */
1181 			 struct buffer_head *p_s_un_bh)
1182 {				/* NULL or unformatted node pointer.    */
1183 	struct super_block *p_s_sb = p_s_inode->i_sb;
1184 	struct tree_balance s_del_balance;
1185 	struct item_head s_ih;
1186 	struct item_head *q_ih;
1187 	int quota_cut_bytes;
1188 	int n_ret_value, n_del_size, n_removed;
1189 
1190 #ifdef CONFIG_REISERFS_CHECK
1191 	char c_mode;
1192 	int n_iter = 0;
1193 #endif
1194 
1195 	BUG_ON(!th->t_trans_id);
1196 
1197 	init_tb_struct(th, &s_del_balance, p_s_sb, p_s_path,
1198 		       0 /*size is unknown */ );
1199 
1200 	while (1) {
1201 		n_removed = 0;
1202 
1203 #ifdef CONFIG_REISERFS_CHECK
1204 		n_iter++;
1205 		c_mode =
1206 #endif
1207 		    prepare_for_delete_or_cut(th, p_s_inode, p_s_path,
1208 					      p_s_item_key, &n_removed,
1209 					      &n_del_size,
1210 					      max_reiserfs_offset(p_s_inode));
1211 
1212 		RFALSE(c_mode != M_DELETE, "PAP-5320: mode must be M_DELETE");
1213 
1214 		copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
1215 		s_del_balance.insert_size[0] = n_del_size;
1216 
1217 		n_ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, NULL);
1218 		if (n_ret_value != REPEAT_SEARCH)
1219 			break;
1220 
1221 		PROC_INFO_INC(p_s_sb, delete_item_restarted);
1222 
1223 		// file system changed, repeat search
1224 		n_ret_value =
1225 		    search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path);
1226 		if (n_ret_value == IO_ERROR)
1227 			break;
1228 		if (n_ret_value == FILE_NOT_FOUND) {
1229 			reiserfs_warning(p_s_sb,
1230 					 "vs-5340: reiserfs_delete_item: "
1231 					 "no items of the file %K found",
1232 					 p_s_item_key);
1233 			break;
1234 		}
1235 	}			/* while (1) */
1236 
1237 	if (n_ret_value != CARRY_ON) {
1238 		unfix_nodes(&s_del_balance);
1239 		return 0;
1240 	}
1241 	// reiserfs_delete_item returns item length when success
1242 	n_ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE);
1243 	q_ih = get_ih(p_s_path);
1244 	quota_cut_bytes = ih_item_len(q_ih);
1245 
1246 	/* hack so the quota code doesn't have to guess if the file
1247 	 ** has a tail.  On tail insert, we allocate quota for 1 unformatted node.
1248 	 ** We test the offset because the tail might have been
1249 	 ** split into multiple items, and we only want to decrement for
1250 	 ** the unfm node once
1251 	 */
1252 	if (!S_ISLNK(p_s_inode->i_mode) && is_direct_le_ih(q_ih)) {
1253 		if ((le_ih_k_offset(q_ih) & (p_s_sb->s_blocksize - 1)) == 1) {
1254 			quota_cut_bytes = p_s_sb->s_blocksize + UNFM_P_SIZE;
1255 		} else {
1256 			quota_cut_bytes = 0;
1257 		}
1258 	}
1259 
1260 	if (p_s_un_bh) {
1261 		int off;
1262 		char *data;
1263 
1264 		/* We are in direct2indirect conversion, so move tail contents
1265 		   to the unformatted node */
1266 		/* note, we do the copy before preparing the buffer because we
1267 		 ** don't care about the contents of the unformatted node yet.
1268 		 ** the only thing we really care about is the direct item's data
1269 		 ** is in the unformatted node.
1270 		 **
1271 		 ** Otherwise, we would have to call reiserfs_prepare_for_journal on
1272 		 ** the unformatted node, which might schedule, meaning we'd have to
1273 		 ** loop all the way back up to the start of the while loop.
1274 		 **
1275 		 ** The unformatted node must be dirtied later on.  We can't be
1276 		 ** sure here if the entire tail has been deleted yet.
1277 		 **
1278 		 ** p_s_un_bh is from the page cache (all unformatted nodes are
1279 		 ** from the page cache) and might be a highmem page.  So, we
1280 		 ** can't use p_s_un_bh->b_data.
1281 		 ** -clm
1282 		 */
1283 
1284 		data = kmap_atomic(p_s_un_bh->b_page, KM_USER0);
1285 		off = ((le_ih_k_offset(&s_ih) - 1) & (PAGE_CACHE_SIZE - 1));
1286 		memcpy(data + off,
1287 		       B_I_PITEM(PATH_PLAST_BUFFER(p_s_path), &s_ih),
1288 		       n_ret_value);
1289 		kunmap_atomic(data, KM_USER0);
1290 	}
1291 	/* Perform balancing after all resources have been collected at once. */
1292 	do_balance(&s_del_balance, NULL, NULL, M_DELETE);
1293 
1294 #ifdef REISERQUOTA_DEBUG
1295 	reiserfs_debug(p_s_sb, REISERFS_DEBUG_CODE,
1296 		       "reiserquota delete_item(): freeing %u, id=%u type=%c",
1297 		       quota_cut_bytes, p_s_inode->i_uid, head2type(&s_ih));
1298 #endif
1299 	DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes);
1300 
1301 	/* Return deleted body length */
1302 	return n_ret_value;
1303 }
1304 
1305 /* Summary Of Mechanisms For Handling Collisions Between Processes:
1306 
1307  deletion of the body of the object is performed by iput(), with the
1308  result that if multiple processes are operating on a file, the
1309  deletion of the body of the file is deferred until the last process
1310  that has an open inode performs its iput().
1311 
1312  writes and truncates are protected from collisions by use of
1313  semaphores.
1314 
1315  creates, linking, and mknod are protected from collisions with other
1316  processes by making the reiserfs_add_entry() the last step in the
1317  creation, and then rolling back all changes if there was a collision.
1318  - Hans
1319 */
1320 
1321 /* this deletes item which never gets split */
1322 void reiserfs_delete_solid_item(struct reiserfs_transaction_handle *th,
1323 				struct inode *inode, struct reiserfs_key *key)
1324 {
1325 	struct tree_balance tb;
1326 	INITIALIZE_PATH(path);
1327 	int item_len = 0;
1328 	int tb_init = 0;
1329 	struct cpu_key cpu_key;
1330 	int retval;
1331 	int quota_cut_bytes = 0;
1332 
1333 	BUG_ON(!th->t_trans_id);
1334 
1335 	le_key2cpu_key(&cpu_key, key);
1336 
1337 	while (1) {
1338 		retval = search_item(th->t_super, &cpu_key, &path);
1339 		if (retval == IO_ERROR) {
1340 			reiserfs_warning(th->t_super,
1341 					 "vs-5350: reiserfs_delete_solid_item: "
1342 					 "i/o failure occurred trying to delete %K",
1343 					 &cpu_key);
1344 			break;
1345 		}
1346 		if (retval != ITEM_FOUND) {
1347 			pathrelse(&path);
1348 			// No need for a warning, if there is just no free space to insert '..' item into the newly-created subdir
1349 			if (!
1350 			    ((unsigned long long)
1351 			     GET_HASH_VALUE(le_key_k_offset
1352 					    (le_key_version(key), key)) == 0
1353 			     && (unsigned long long)
1354 			     GET_GENERATION_NUMBER(le_key_k_offset
1355 						   (le_key_version(key),
1356 						    key)) == 1))
1357 				reiserfs_warning(th->t_super,
1358 						 "vs-5355: reiserfs_delete_solid_item: %k not found",
1359 						 key);
1360 			break;
1361 		}
1362 		if (!tb_init) {
1363 			tb_init = 1;
1364 			item_len = ih_item_len(PATH_PITEM_HEAD(&path));
1365 			init_tb_struct(th, &tb, th->t_super, &path,
1366 				       -(IH_SIZE + item_len));
1367 		}
1368 		quota_cut_bytes = ih_item_len(PATH_PITEM_HEAD(&path));
1369 
1370 		retval = fix_nodes(M_DELETE, &tb, NULL, NULL);
1371 		if (retval == REPEAT_SEARCH) {
1372 			PROC_INFO_INC(th->t_super, delete_solid_item_restarted);
1373 			continue;
1374 		}
1375 
1376 		if (retval == CARRY_ON) {
1377 			do_balance(&tb, NULL, NULL, M_DELETE);
1378 			if (inode) {	/* Should we count quota for item? (we don't count quotas for save-links) */
1379 #ifdef REISERQUOTA_DEBUG
1380 				reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE,
1381 					       "reiserquota delete_solid_item(): freeing %u id=%u type=%c",
1382 					       quota_cut_bytes, inode->i_uid,
1383 					       key2type(key));
1384 #endif
1385 				DQUOT_FREE_SPACE_NODIRTY(inode,
1386 							 quota_cut_bytes);
1387 			}
1388 			break;
1389 		}
1390 		// IO_ERROR, NO_DISK_SPACE, etc
1391 		reiserfs_warning(th->t_super,
1392 				 "vs-5360: reiserfs_delete_solid_item: "
1393 				 "could not delete %K due to fix_nodes failure",
1394 				 &cpu_key);
1395 		unfix_nodes(&tb);
1396 		break;
1397 	}
1398 
1399 	reiserfs_check_path(&path);
1400 }
1401 
1402 int reiserfs_delete_object(struct reiserfs_transaction_handle *th,
1403 			   struct inode *inode)
1404 {
1405 	int err;
1406 	inode->i_size = 0;
1407 	BUG_ON(!th->t_trans_id);
1408 
1409 	/* for directory this deletes item containing "." and ".." */
1410 	err =
1411 	    reiserfs_do_truncate(th, inode, NULL, 0 /*no timestamp updates */ );
1412 	if (err)
1413 		return err;
1414 
1415 #if defined( USE_INODE_GENERATION_COUNTER )
1416 	if (!old_format_only(th->t_super)) {
1417 		__le32 *inode_generation;
1418 
1419 		inode_generation =
1420 		    &REISERFS_SB(th->t_super)->s_rs->s_inode_generation;
1421 		*inode_generation =
1422 		    cpu_to_le32(le32_to_cpu(*inode_generation) + 1);
1423 	}
1424 /* USE_INODE_GENERATION_COUNTER */
1425 #endif
1426 	reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode));
1427 
1428 	return err;
1429 }
1430 
1431 static void unmap_buffers(struct page *page, loff_t pos)
1432 {
1433 	struct buffer_head *bh;
1434 	struct buffer_head *head;
1435 	struct buffer_head *next;
1436 	unsigned long tail_index;
1437 	unsigned long cur_index;
1438 
1439 	if (page) {
1440 		if (page_has_buffers(page)) {
1441 			tail_index = pos & (PAGE_CACHE_SIZE - 1);
1442 			cur_index = 0;
1443 			head = page_buffers(page);
1444 			bh = head;
1445 			do {
1446 				next = bh->b_this_page;
1447 
1448 				/* we want to unmap the buffers that contain the tail, and
1449 				 ** all the buffers after it (since the tail must be at the
1450 				 ** end of the file).  We don't want to unmap file data
1451 				 ** before the tail, since it might be dirty and waiting to
1452 				 ** reach disk
1453 				 */
1454 				cur_index += bh->b_size;
1455 				if (cur_index > tail_index) {
1456 					reiserfs_unmap_buffer(bh);
1457 				}
1458 				bh = next;
1459 			} while (bh != head);
1460 			if (PAGE_SIZE == bh->b_size) {
1461 				cancel_dirty_page(page, PAGE_CACHE_SIZE);
1462 			}
1463 		}
1464 	}
1465 }
1466 
1467 static int maybe_indirect_to_direct(struct reiserfs_transaction_handle *th,
1468 				    struct inode *p_s_inode,
1469 				    struct page *page,
1470 				    struct treepath *p_s_path,
1471 				    const struct cpu_key *p_s_item_key,
1472 				    loff_t n_new_file_size, char *p_c_mode)
1473 {
1474 	struct super_block *p_s_sb = p_s_inode->i_sb;
1475 	int n_block_size = p_s_sb->s_blocksize;
1476 	int cut_bytes;
1477 	BUG_ON(!th->t_trans_id);
1478 	BUG_ON(n_new_file_size != p_s_inode->i_size);
1479 
1480 	/* the page being sent in could be NULL if there was an i/o error
1481 	 ** reading in the last block.  The user will hit problems trying to
1482 	 ** read the file, but for now we just skip the indirect2direct
1483 	 */
1484 	if (atomic_read(&p_s_inode->i_count) > 1 ||
1485 	    !tail_has_to_be_packed(p_s_inode) ||
1486 	    !page || (REISERFS_I(p_s_inode)->i_flags & i_nopack_mask)) {
1487 		// leave tail in an unformatted node
1488 		*p_c_mode = M_SKIP_BALANCING;
1489 		cut_bytes =
1490 		    n_block_size - (n_new_file_size & (n_block_size - 1));
1491 		pathrelse(p_s_path);
1492 		return cut_bytes;
1493 	}
1494 	/* Permorm the conversion to a direct_item. */
1495 	/*return indirect_to_direct (p_s_inode, p_s_path, p_s_item_key, n_new_file_size, p_c_mode); */
1496 	return indirect2direct(th, p_s_inode, page, p_s_path, p_s_item_key,
1497 			       n_new_file_size, p_c_mode);
1498 }
1499 
1500 /* we did indirect_to_direct conversion. And we have inserted direct
1501    item successesfully, but there were no disk space to cut unfm
1502    pointer being converted. Therefore we have to delete inserted
1503    direct item(s) */
1504 static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle *th,
1505 					 struct inode *inode, struct treepath *path)
1506 {
1507 	struct cpu_key tail_key;
1508 	int tail_len;
1509 	int removed;
1510 	BUG_ON(!th->t_trans_id);
1511 
1512 	make_cpu_key(&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4);	// !!!!
1513 	tail_key.key_length = 4;
1514 
1515 	tail_len =
1516 	    (cpu_key_k_offset(&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1;
1517 	while (tail_len) {
1518 		/* look for the last byte of the tail */
1519 		if (search_for_position_by_key(inode->i_sb, &tail_key, path) ==
1520 		    POSITION_NOT_FOUND)
1521 			reiserfs_panic(inode->i_sb,
1522 				       "vs-5615: indirect_to_direct_roll_back: found invalid item");
1523 		RFALSE(path->pos_in_item !=
1524 		       ih_item_len(PATH_PITEM_HEAD(path)) - 1,
1525 		       "vs-5616: appended bytes found");
1526 		PATH_LAST_POSITION(path)--;
1527 
1528 		removed =
1529 		    reiserfs_delete_item(th, path, &tail_key, inode,
1530 					 NULL /*unbh not needed */ );
1531 		RFALSE(removed <= 0
1532 		       || removed > tail_len,
1533 		       "vs-5617: there was tail %d bytes, removed item length %d bytes",
1534 		       tail_len, removed);
1535 		tail_len -= removed;
1536 		set_cpu_key_k_offset(&tail_key,
1537 				     cpu_key_k_offset(&tail_key) - removed);
1538 	}
1539 	reiserfs_warning(inode->i_sb,
1540 			 "indirect_to_direct_roll_back: indirect_to_direct conversion has been rolled back due to lack of disk space");
1541 	//mark_file_without_tail (inode);
1542 	mark_inode_dirty(inode);
1543 }
1544 
1545 /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */
1546 int reiserfs_cut_from_item(struct reiserfs_transaction_handle *th,
1547 			   struct treepath *p_s_path,
1548 			   struct cpu_key *p_s_item_key,
1549 			   struct inode *p_s_inode,
1550 			   struct page *page, loff_t n_new_file_size)
1551 {
1552 	struct super_block *p_s_sb = p_s_inode->i_sb;
1553 	/* Every function which is going to call do_balance must first
1554 	   create a tree_balance structure.  Then it must fill up this
1555 	   structure by using the init_tb_struct and fix_nodes functions.
1556 	   After that we can make tree balancing. */
1557 	struct tree_balance s_cut_balance;
1558 	struct item_head *p_le_ih;
1559 	int n_cut_size = 0,	/* Amount to be cut. */
1560 	    n_ret_value = CARRY_ON, n_removed = 0,	/* Number of the removed unformatted nodes. */
1561 	    n_is_inode_locked = 0;
1562 	char c_mode;		/* Mode of the balance. */
1563 	int retval2 = -1;
1564 	int quota_cut_bytes;
1565 	loff_t tail_pos = 0;
1566 
1567 	BUG_ON(!th->t_trans_id);
1568 
1569 	init_tb_struct(th, &s_cut_balance, p_s_inode->i_sb, p_s_path,
1570 		       n_cut_size);
1571 
1572 	/* Repeat this loop until we either cut the item without needing
1573 	   to balance, or we fix_nodes without schedule occurring */
1574 	while (1) {
1575 		/* Determine the balance mode, position of the first byte to
1576 		   be cut, and size to be cut.  In case of the indirect item
1577 		   free unformatted nodes which are pointed to by the cut
1578 		   pointers. */
1579 
1580 		c_mode =
1581 		    prepare_for_delete_or_cut(th, p_s_inode, p_s_path,
1582 					      p_s_item_key, &n_removed,
1583 					      &n_cut_size, n_new_file_size);
1584 		if (c_mode == M_CONVERT) {
1585 			/* convert last unformatted node to direct item or leave
1586 			   tail in the unformatted node */
1587 			RFALSE(n_ret_value != CARRY_ON,
1588 			       "PAP-5570: can not convert twice");
1589 
1590 			n_ret_value =
1591 			    maybe_indirect_to_direct(th, p_s_inode, page,
1592 						     p_s_path, p_s_item_key,
1593 						     n_new_file_size, &c_mode);
1594 			if (c_mode == M_SKIP_BALANCING)
1595 				/* tail has been left in the unformatted node */
1596 				return n_ret_value;
1597 
1598 			n_is_inode_locked = 1;
1599 
1600 			/* removing of last unformatted node will change value we
1601 			   have to return to truncate. Save it */
1602 			retval2 = n_ret_value;
1603 			/*retval2 = p_s_sb->s_blocksize - (n_new_file_size & (p_s_sb->s_blocksize - 1)); */
1604 
1605 			/* So, we have performed the first part of the conversion:
1606 			   inserting the new direct item.  Now we are removing the
1607 			   last unformatted node pointer. Set key to search for
1608 			   it. */
1609 			set_cpu_key_k_type(p_s_item_key, TYPE_INDIRECT);
1610 			p_s_item_key->key_length = 4;
1611 			n_new_file_size -=
1612 			    (n_new_file_size & (p_s_sb->s_blocksize - 1));
1613 			tail_pos = n_new_file_size;
1614 			set_cpu_key_k_offset(p_s_item_key, n_new_file_size + 1);
1615 			if (search_for_position_by_key
1616 			    (p_s_sb, p_s_item_key,
1617 			     p_s_path) == POSITION_NOT_FOUND) {
1618 				print_block(PATH_PLAST_BUFFER(p_s_path), 3,
1619 					    PATH_LAST_POSITION(p_s_path) - 1,
1620 					    PATH_LAST_POSITION(p_s_path) + 1);
1621 				reiserfs_panic(p_s_sb,
1622 					       "PAP-5580: reiserfs_cut_from_item: item to convert does not exist (%K)",
1623 					       p_s_item_key);
1624 			}
1625 			continue;
1626 		}
1627 		if (n_cut_size == 0) {
1628 			pathrelse(p_s_path);
1629 			return 0;
1630 		}
1631 
1632 		s_cut_balance.insert_size[0] = n_cut_size;
1633 
1634 		n_ret_value = fix_nodes(c_mode, &s_cut_balance, NULL, NULL);
1635 		if (n_ret_value != REPEAT_SEARCH)
1636 			break;
1637 
1638 		PROC_INFO_INC(p_s_sb, cut_from_item_restarted);
1639 
1640 		n_ret_value =
1641 		    search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path);
1642 		if (n_ret_value == POSITION_FOUND)
1643 			continue;
1644 
1645 		reiserfs_warning(p_s_sb,
1646 				 "PAP-5610: reiserfs_cut_from_item: item %K not found",
1647 				 p_s_item_key);
1648 		unfix_nodes(&s_cut_balance);
1649 		return (n_ret_value == IO_ERROR) ? -EIO : -ENOENT;
1650 	}			/* while */
1651 
1652 	// check fix_nodes results (IO_ERROR or NO_DISK_SPACE)
1653 	if (n_ret_value != CARRY_ON) {
1654 		if (n_is_inode_locked) {
1655 			// FIXME: this seems to be not needed: we are always able
1656 			// to cut item
1657 			indirect_to_direct_roll_back(th, p_s_inode, p_s_path);
1658 		}
1659 		if (n_ret_value == NO_DISK_SPACE)
1660 			reiserfs_warning(p_s_sb, "NO_DISK_SPACE");
1661 		unfix_nodes(&s_cut_balance);
1662 		return -EIO;
1663 	}
1664 
1665 	/* go ahead and perform balancing */
1666 
1667 	RFALSE(c_mode == M_PASTE || c_mode == M_INSERT, "invalid mode");
1668 
1669 	/* Calculate number of bytes that need to be cut from the item. */
1670 	quota_cut_bytes =
1671 	    (c_mode ==
1672 	     M_DELETE) ? ih_item_len(get_ih(p_s_path)) : -s_cut_balance.
1673 	    insert_size[0];
1674 	if (retval2 == -1)
1675 		n_ret_value = calc_deleted_bytes_number(&s_cut_balance, c_mode);
1676 	else
1677 		n_ret_value = retval2;
1678 
1679 	/* For direct items, we only change the quota when deleting the last
1680 	 ** item.
1681 	 */
1682 	p_le_ih = PATH_PITEM_HEAD(s_cut_balance.tb_path);
1683 	if (!S_ISLNK(p_s_inode->i_mode) && is_direct_le_ih(p_le_ih)) {
1684 		if (c_mode == M_DELETE &&
1685 		    (le_ih_k_offset(p_le_ih) & (p_s_sb->s_blocksize - 1)) ==
1686 		    1) {
1687 			// FIXME: this is to keep 3.5 happy
1688 			REISERFS_I(p_s_inode)->i_first_direct_byte = U32_MAX;
1689 			quota_cut_bytes = p_s_sb->s_blocksize + UNFM_P_SIZE;
1690 		} else {
1691 			quota_cut_bytes = 0;
1692 		}
1693 	}
1694 #ifdef CONFIG_REISERFS_CHECK
1695 	if (n_is_inode_locked) {
1696 		struct item_head *le_ih =
1697 		    PATH_PITEM_HEAD(s_cut_balance.tb_path);
1698 		/* we are going to complete indirect2direct conversion. Make
1699 		   sure, that we exactly remove last unformatted node pointer
1700 		   of the item */
1701 		if (!is_indirect_le_ih(le_ih))
1702 			reiserfs_panic(p_s_sb,
1703 				       "vs-5652: reiserfs_cut_from_item: "
1704 				       "item must be indirect %h", le_ih);
1705 
1706 		if (c_mode == M_DELETE && ih_item_len(le_ih) != UNFM_P_SIZE)
1707 			reiserfs_panic(p_s_sb,
1708 				       "vs-5653: reiserfs_cut_from_item: "
1709 				       "completing indirect2direct conversion indirect item %h "
1710 				       "being deleted must be of 4 byte long",
1711 				       le_ih);
1712 
1713 		if (c_mode == M_CUT
1714 		    && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) {
1715 			reiserfs_panic(p_s_sb,
1716 				       "vs-5654: reiserfs_cut_from_item: "
1717 				       "can not complete indirect2direct conversion of %h (CUT, insert_size==%d)",
1718 				       le_ih, s_cut_balance.insert_size[0]);
1719 		}
1720 		/* it would be useful to make sure, that right neighboring
1721 		   item is direct item of this file */
1722 	}
1723 #endif
1724 
1725 	do_balance(&s_cut_balance, NULL, NULL, c_mode);
1726 	if (n_is_inode_locked) {
1727 		/* we've done an indirect->direct conversion.  when the data block
1728 		 ** was freed, it was removed from the list of blocks that must
1729 		 ** be flushed before the transaction commits, make sure to
1730 		 ** unmap and invalidate it
1731 		 */
1732 		unmap_buffers(page, tail_pos);
1733 		REISERFS_I(p_s_inode)->i_flags &= ~i_pack_on_close_mask;
1734 	}
1735 #ifdef REISERQUOTA_DEBUG
1736 	reiserfs_debug(p_s_inode->i_sb, REISERFS_DEBUG_CODE,
1737 		       "reiserquota cut_from_item(): freeing %u id=%u type=%c",
1738 		       quota_cut_bytes, p_s_inode->i_uid, '?');
1739 #endif
1740 	DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes);
1741 	return n_ret_value;
1742 }
1743 
1744 static void truncate_directory(struct reiserfs_transaction_handle *th,
1745 			       struct inode *inode)
1746 {
1747 	BUG_ON(!th->t_trans_id);
1748 	if (inode->i_nlink)
1749 		reiserfs_warning(inode->i_sb,
1750 				 "vs-5655: truncate_directory: link count != 0");
1751 
1752 	set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), DOT_OFFSET);
1753 	set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_DIRENTRY);
1754 	reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode));
1755 	reiserfs_update_sd(th, inode);
1756 	set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), SD_OFFSET);
1757 	set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_STAT_DATA);
1758 }
1759 
1760 /* Truncate file to the new size. Note, this must be called with a transaction
1761    already started */
1762 int reiserfs_do_truncate(struct reiserfs_transaction_handle *th, struct inode *p_s_inode,	/* ->i_size contains new
1763 												   size */
1764 			 struct page *page,	/* up to date for last block */
1765 			 int update_timestamps	/* when it is called by
1766 						   file_release to convert
1767 						   the tail - no timestamps
1768 						   should be updated */
1769     )
1770 {
1771 	INITIALIZE_PATH(s_search_path);	/* Path to the current object item. */
1772 	struct item_head *p_le_ih;	/* Pointer to an item header. */
1773 	struct cpu_key s_item_key;	/* Key to search for a previous file item. */
1774 	loff_t n_file_size,	/* Old file size. */
1775 	 n_new_file_size;	/* New file size. */
1776 	int n_deleted;		/* Number of deleted or truncated bytes. */
1777 	int retval;
1778 	int err = 0;
1779 
1780 	BUG_ON(!th->t_trans_id);
1781 	if (!
1782 	    (S_ISREG(p_s_inode->i_mode) || S_ISDIR(p_s_inode->i_mode)
1783 	     || S_ISLNK(p_s_inode->i_mode)))
1784 		return 0;
1785 
1786 	if (S_ISDIR(p_s_inode->i_mode)) {
1787 		// deletion of directory - no need to update timestamps
1788 		truncate_directory(th, p_s_inode);
1789 		return 0;
1790 	}
1791 
1792 	/* Get new file size. */
1793 	n_new_file_size = p_s_inode->i_size;
1794 
1795 	// FIXME: note, that key type is unimportant here
1796 	make_cpu_key(&s_item_key, p_s_inode, max_reiserfs_offset(p_s_inode),
1797 		     TYPE_DIRECT, 3);
1798 
1799 	retval =
1800 	    search_for_position_by_key(p_s_inode->i_sb, &s_item_key,
1801 				       &s_search_path);
1802 	if (retval == IO_ERROR) {
1803 		reiserfs_warning(p_s_inode->i_sb,
1804 				 "vs-5657: reiserfs_do_truncate: "
1805 				 "i/o failure occurred trying to truncate %K",
1806 				 &s_item_key);
1807 		err = -EIO;
1808 		goto out;
1809 	}
1810 	if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) {
1811 		reiserfs_warning(p_s_inode->i_sb,
1812 				 "PAP-5660: reiserfs_do_truncate: "
1813 				 "wrong result %d of search for %K", retval,
1814 				 &s_item_key);
1815 
1816 		err = -EIO;
1817 		goto out;
1818 	}
1819 
1820 	s_search_path.pos_in_item--;
1821 
1822 	/* Get real file size (total length of all file items) */
1823 	p_le_ih = PATH_PITEM_HEAD(&s_search_path);
1824 	if (is_statdata_le_ih(p_le_ih))
1825 		n_file_size = 0;
1826 	else {
1827 		loff_t offset = le_ih_k_offset(p_le_ih);
1828 		int bytes =
1829 		    op_bytes_number(p_le_ih, p_s_inode->i_sb->s_blocksize);
1830 
1831 		/* this may mismatch with real file size: if last direct item
1832 		   had no padding zeros and last unformatted node had no free
1833 		   space, this file would have this file size */
1834 		n_file_size = offset + bytes - 1;
1835 	}
1836 	/*
1837 	 * are we doing a full truncate or delete, if so
1838 	 * kick in the reada code
1839 	 */
1840 	if (n_new_file_size == 0)
1841 		s_search_path.reada = PATH_READA | PATH_READA_BACK;
1842 
1843 	if (n_file_size == 0 || n_file_size < n_new_file_size) {
1844 		goto update_and_out;
1845 	}
1846 
1847 	/* Update key to search for the last file item. */
1848 	set_cpu_key_k_offset(&s_item_key, n_file_size);
1849 
1850 	do {
1851 		/* Cut or delete file item. */
1852 		n_deleted =
1853 		    reiserfs_cut_from_item(th, &s_search_path, &s_item_key,
1854 					   p_s_inode, page, n_new_file_size);
1855 		if (n_deleted < 0) {
1856 			reiserfs_warning(p_s_inode->i_sb,
1857 					 "vs-5665: reiserfs_do_truncate: reiserfs_cut_from_item failed");
1858 			reiserfs_check_path(&s_search_path);
1859 			return 0;
1860 		}
1861 
1862 		RFALSE(n_deleted > n_file_size,
1863 		       "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K",
1864 		       n_deleted, n_file_size, &s_item_key);
1865 
1866 		/* Change key to search the last file item. */
1867 		n_file_size -= n_deleted;
1868 
1869 		set_cpu_key_k_offset(&s_item_key, n_file_size);
1870 
1871 		/* While there are bytes to truncate and previous file item is presented in the tree. */
1872 
1873 		/*
1874 		 ** This loop could take a really long time, and could log
1875 		 ** many more blocks than a transaction can hold.  So, we do a polite
1876 		 ** journal end here, and if the transaction needs ending, we make
1877 		 ** sure the file is consistent before ending the current trans
1878 		 ** and starting a new one
1879 		 */
1880 		if (journal_transaction_should_end(th, 0) ||
1881 		    reiserfs_transaction_free_space(th) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) {
1882 			int orig_len_alloc = th->t_blocks_allocated;
1883 			decrement_counters_in_path(&s_search_path);
1884 
1885 			if (update_timestamps) {
1886 				p_s_inode->i_mtime = p_s_inode->i_ctime =
1887 				    CURRENT_TIME_SEC;
1888 			}
1889 			reiserfs_update_sd(th, p_s_inode);
1890 
1891 			err = journal_end(th, p_s_inode->i_sb, orig_len_alloc);
1892 			if (err)
1893 				goto out;
1894 			err = journal_begin(th, p_s_inode->i_sb,
1895 					    JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD + JOURNAL_PER_BALANCE_CNT * 4) ;
1896 			if (err)
1897 				goto out;
1898 			reiserfs_update_inode_transaction(p_s_inode);
1899 		}
1900 	} while (n_file_size > ROUND_UP(n_new_file_size) &&
1901 		 search_for_position_by_key(p_s_inode->i_sb, &s_item_key,
1902 					    &s_search_path) == POSITION_FOUND);
1903 
1904 	RFALSE(n_file_size > ROUND_UP(n_new_file_size),
1905 	       "PAP-5680: truncate did not finish: new_file_size %Ld, current %Ld, oid %d",
1906 	       n_new_file_size, n_file_size, s_item_key.on_disk_key.k_objectid);
1907 
1908       update_and_out:
1909 	if (update_timestamps) {
1910 		// this is truncate, not file closing
1911 		p_s_inode->i_mtime = p_s_inode->i_ctime = CURRENT_TIME_SEC;
1912 	}
1913 	reiserfs_update_sd(th, p_s_inode);
1914 
1915       out:
1916 	pathrelse(&s_search_path);
1917 	return err;
1918 }
1919 
1920 #ifdef CONFIG_REISERFS_CHECK
1921 // this makes sure, that we __append__, not overwrite or add holes
1922 static void check_research_for_paste(struct treepath *path,
1923 				     const struct cpu_key *p_s_key)
1924 {
1925 	struct item_head *found_ih = get_ih(path);
1926 
1927 	if (is_direct_le_ih(found_ih)) {
1928 		if (le_ih_k_offset(found_ih) +
1929 		    op_bytes_number(found_ih,
1930 				    get_last_bh(path)->b_size) !=
1931 		    cpu_key_k_offset(p_s_key)
1932 		    || op_bytes_number(found_ih,
1933 				       get_last_bh(path)->b_size) !=
1934 		    pos_in_item(path))
1935 			reiserfs_panic(NULL,
1936 				       "PAP-5720: check_research_for_paste: "
1937 				       "found direct item %h or position (%d) does not match to key %K",
1938 				       found_ih, pos_in_item(path), p_s_key);
1939 	}
1940 	if (is_indirect_le_ih(found_ih)) {
1941 		if (le_ih_k_offset(found_ih) +
1942 		    op_bytes_number(found_ih,
1943 				    get_last_bh(path)->b_size) !=
1944 		    cpu_key_k_offset(p_s_key)
1945 		    || I_UNFM_NUM(found_ih) != pos_in_item(path)
1946 		    || get_ih_free_space(found_ih) != 0)
1947 			reiserfs_panic(NULL,
1948 				       "PAP-5730: check_research_for_paste: "
1949 				       "found indirect item (%h) or position (%d) does not match to key (%K)",
1950 				       found_ih, pos_in_item(path), p_s_key);
1951 	}
1952 }
1953 #endif				/* config reiserfs check */
1954 
1955 /* Paste bytes to the existing item. Returns bytes number pasted into the item. */
1956 int reiserfs_paste_into_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_search_path,	/* Path to the pasted item.          */
1957 			     const struct cpu_key *p_s_key,	/* Key to search for the needed item. */
1958 			     struct inode *inode,	/* Inode item belongs to */
1959 			     const char *p_c_body,	/* Pointer to the bytes to paste.    */
1960 			     int n_pasted_size)
1961 {				/* Size of pasted bytes.             */
1962 	struct tree_balance s_paste_balance;
1963 	int retval;
1964 	int fs_gen;
1965 
1966 	BUG_ON(!th->t_trans_id);
1967 
1968 	fs_gen = get_generation(inode->i_sb);
1969 
1970 #ifdef REISERQUOTA_DEBUG
1971 	reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
1972 		       "reiserquota paste_into_item(): allocating %u id=%u type=%c",
1973 		       n_pasted_size, inode->i_uid,
1974 		       key2type(&(p_s_key->on_disk_key)));
1975 #endif
1976 
1977 	if (DQUOT_ALLOC_SPACE_NODIRTY(inode, n_pasted_size)) {
1978 		pathrelse(p_s_search_path);
1979 		return -EDQUOT;
1980 	}
1981 	init_tb_struct(th, &s_paste_balance, th->t_super, p_s_search_path,
1982 		       n_pasted_size);
1983 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
1984 	s_paste_balance.key = p_s_key->on_disk_key;
1985 #endif
1986 
1987 	/* DQUOT_* can schedule, must check before the fix_nodes */
1988 	if (fs_changed(fs_gen, inode->i_sb)) {
1989 		goto search_again;
1990 	}
1991 
1992 	while ((retval =
1993 		fix_nodes(M_PASTE, &s_paste_balance, NULL,
1994 			  p_c_body)) == REPEAT_SEARCH) {
1995 	      search_again:
1996 		/* file system changed while we were in the fix_nodes */
1997 		PROC_INFO_INC(th->t_super, paste_into_item_restarted);
1998 		retval =
1999 		    search_for_position_by_key(th->t_super, p_s_key,
2000 					       p_s_search_path);
2001 		if (retval == IO_ERROR) {
2002 			retval = -EIO;
2003 			goto error_out;
2004 		}
2005 		if (retval == POSITION_FOUND) {
2006 			reiserfs_warning(inode->i_sb,
2007 					 "PAP-5710: reiserfs_paste_into_item: entry or pasted byte (%K) exists",
2008 					 p_s_key);
2009 			retval = -EEXIST;
2010 			goto error_out;
2011 		}
2012 #ifdef CONFIG_REISERFS_CHECK
2013 		check_research_for_paste(p_s_search_path, p_s_key);
2014 #endif
2015 	}
2016 
2017 	/* Perform balancing after all resources are collected by fix_nodes, and
2018 	   accessing them will not risk triggering schedule. */
2019 	if (retval == CARRY_ON) {
2020 		do_balance(&s_paste_balance, NULL /*ih */ , p_c_body, M_PASTE);
2021 		return 0;
2022 	}
2023 	retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
2024       error_out:
2025 	/* this also releases the path */
2026 	unfix_nodes(&s_paste_balance);
2027 #ifdef REISERQUOTA_DEBUG
2028 	reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
2029 		       "reiserquota paste_into_item(): freeing %u id=%u type=%c",
2030 		       n_pasted_size, inode->i_uid,
2031 		       key2type(&(p_s_key->on_disk_key)));
2032 #endif
2033 	DQUOT_FREE_SPACE_NODIRTY(inode, n_pasted_size);
2034 	return retval;
2035 }
2036 
2037 /* Insert new item into the buffer at the path. */
2038 int reiserfs_insert_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_path,	/* Path to the inserteded item.         */
2039 			 const struct cpu_key *key, struct item_head *p_s_ih,	/* Pointer to the item header to insert. */
2040 			 struct inode *inode, const char *p_c_body)
2041 {				/* Pointer to the bytes to insert.      */
2042 	struct tree_balance s_ins_balance;
2043 	int retval;
2044 	int fs_gen = 0;
2045 	int quota_bytes = 0;
2046 
2047 	BUG_ON(!th->t_trans_id);
2048 
2049 	if (inode) {		/* Do we count quotas for item? */
2050 		fs_gen = get_generation(inode->i_sb);
2051 		quota_bytes = ih_item_len(p_s_ih);
2052 
2053 		/* hack so the quota code doesn't have to guess if the file has
2054 		 ** a tail, links are always tails, so there's no guessing needed
2055 		 */
2056 		if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(p_s_ih)) {
2057 			quota_bytes = inode->i_sb->s_blocksize + UNFM_P_SIZE;
2058 		}
2059 #ifdef REISERQUOTA_DEBUG
2060 		reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
2061 			       "reiserquota insert_item(): allocating %u id=%u type=%c",
2062 			       quota_bytes, inode->i_uid, head2type(p_s_ih));
2063 #endif
2064 		/* We can't dirty inode here. It would be immediately written but
2065 		 * appropriate stat item isn't inserted yet... */
2066 		if (DQUOT_ALLOC_SPACE_NODIRTY(inode, quota_bytes)) {
2067 			pathrelse(p_s_path);
2068 			return -EDQUOT;
2069 		}
2070 	}
2071 	init_tb_struct(th, &s_ins_balance, th->t_super, p_s_path,
2072 		       IH_SIZE + ih_item_len(p_s_ih));
2073 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
2074 	s_ins_balance.key = key->on_disk_key;
2075 #endif
2076 	/* DQUOT_* can schedule, must check to be sure calling fix_nodes is safe */
2077 	if (inode && fs_changed(fs_gen, inode->i_sb)) {
2078 		goto search_again;
2079 	}
2080 
2081 	while ((retval =
2082 		fix_nodes(M_INSERT, &s_ins_balance, p_s_ih,
2083 			  p_c_body)) == REPEAT_SEARCH) {
2084 	      search_again:
2085 		/* file system changed while we were in the fix_nodes */
2086 		PROC_INFO_INC(th->t_super, insert_item_restarted);
2087 		retval = search_item(th->t_super, key, p_s_path);
2088 		if (retval == IO_ERROR) {
2089 			retval = -EIO;
2090 			goto error_out;
2091 		}
2092 		if (retval == ITEM_FOUND) {
2093 			reiserfs_warning(th->t_super,
2094 					 "PAP-5760: reiserfs_insert_item: "
2095 					 "key %K already exists in the tree",
2096 					 key);
2097 			retval = -EEXIST;
2098 			goto error_out;
2099 		}
2100 	}
2101 
2102 	/* make balancing after all resources will be collected at a time */
2103 	if (retval == CARRY_ON) {
2104 		do_balance(&s_ins_balance, p_s_ih, p_c_body, M_INSERT);
2105 		return 0;
2106 	}
2107 
2108 	retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
2109       error_out:
2110 	/* also releases the path */
2111 	unfix_nodes(&s_ins_balance);
2112 #ifdef REISERQUOTA_DEBUG
2113 	reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE,
2114 		       "reiserquota insert_item(): freeing %u id=%u type=%c",
2115 		       quota_bytes, inode->i_uid, head2type(p_s_ih));
2116 #endif
2117 	if (inode)
2118 		DQUOT_FREE_SPACE_NODIRTY(inode, quota_bytes);
2119 	return retval;
2120 }
2121