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