stree.c 66.1 KB
Newer Older
L
Linus Torvalds 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
/*
 *  Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
 */

/*
 *  Written by Anatoly P. Pinchuk pap@namesys.botik.ru
 *  Programm System Institute
 *  Pereslavl-Zalessky Russia
 */

/*
 *  This file contains functions dealing with S+tree
 *
 * B_IS_IN_TREE
 * copy_item_head
 * comp_short_keys
 * comp_keys
 * comp_short_le_keys
 * le_key2cpu_key
 * comp_le_keys
 * bin_search
 * get_lkey
 * get_rkey
 * key_in_buffer
 * decrement_bcount
 * decrement_counters_in_path
 * reiserfs_check_path
 * pathrelse_and_restore
 * pathrelse
 * search_by_key_reada
 * search_by_key
 * search_for_position_by_key
 * comp_items
 * prepare_for_direct_item
 * prepare_for_direntry_item
 * prepare_for_delete_or_cut
 * calc_deleted_bytes_number
 * init_tb_struct
 * padd_item
 * reiserfs_delete_item
 * reiserfs_delete_solid_item
 * reiserfs_delete_object
 * maybe_indirect_to_direct
 * indirect_to_direct_roll_back
 * reiserfs_cut_from_item
 * truncate_directory
 * reiserfs_do_truncate
 * reiserfs_paste_into_item
 * reiserfs_insert_item
 */

#include <linux/time.h>
#include <linux/string.h>
#include <linux/pagemap.h>
#include <linux/reiserfs_fs.h>
#include <linux/buffer_head.h>
#include <linux/quotaops.h>

/* 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)
L
Linus Torvalds 已提交
61 62
{

63 64
	RFALSE(B_LEVEL(p_s_bh) > MAX_HEIGHT,
	       "PAP-1010: block (%b) has too big level (%z)", p_s_bh, p_s_bh);
L
Linus Torvalds 已提交
65

66
	return (B_LEVEL(p_s_bh) != FREE_LEVEL);
L
Linus Torvalds 已提交
67 68 69 70 71
}

//
// to gets item head in le form
//
72 73
inline void copy_item_head(struct item_head *p_v_to,
			   const struct item_head *p_v_from)
L
Linus Torvalds 已提交
74
{
75
	memcpy(p_v_to, p_v_from, IH_SIZE);
L
Linus Torvalds 已提交
76 77 78 79 80 81 82 83
}

/* k1 is pointer to on-disk structure which is stored in little-endian
   form. k2 is pointer to cpu variable. For key of items of the same
   object this returns 0.
   Returns: -1 if key1 < key2 
   0 if key1 == key2
   1 if key1 > key2 */
84 85
inline int comp_short_keys(const struct reiserfs_key *le_key,
			   const struct cpu_key *cpu_key)
L
Linus Torvalds 已提交
86
{
87 88 89 90 91 92 93 94 95 96 97 98
	__u32 n;
	n = le32_to_cpu(le_key->k_dir_id);
	if (n < cpu_key->on_disk_key.k_dir_id)
		return -1;
	if (n > cpu_key->on_disk_key.k_dir_id)
		return 1;
	n = le32_to_cpu(le_key->k_objectid);
	if (n < cpu_key->on_disk_key.k_objectid)
		return -1;
	if (n > cpu_key->on_disk_key.k_objectid)
		return 1;
	return 0;
L
Linus Torvalds 已提交
99 100 101 102 103 104 105
}

/* k1 is pointer to on-disk structure which is stored in little-endian
   form. k2 is pointer to cpu variable.
   Compare keys using all 4 key fields.
   Returns: -1 if key1 < key2 0
   if key1 = key2 1 if key1 > key2 */
106 107
static inline int comp_keys(const struct reiserfs_key *le_key,
			    const struct cpu_key *cpu_key)
L
Linus Torvalds 已提交
108
{
109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131
	int retval;

	retval = comp_short_keys(le_key, cpu_key);
	if (retval)
		return retval;
	if (le_key_k_offset(le_key_version(le_key), le_key) <
	    cpu_key_k_offset(cpu_key))
		return -1;
	if (le_key_k_offset(le_key_version(le_key), le_key) >
	    cpu_key_k_offset(cpu_key))
		return 1;

	if (cpu_key->key_length == 3)
		return 0;

	/* this part is needed only when tail conversion is in progress */
	if (le_key_k_type(le_key_version(le_key), le_key) <
	    cpu_key_k_type(cpu_key))
		return -1;

	if (le_key_k_type(le_key_version(le_key), le_key) >
	    cpu_key_k_type(cpu_key))
		return 1;
L
Linus Torvalds 已提交
132

133
	return 0;
L
Linus Torvalds 已提交
134 135
}

136 137
inline int comp_short_le_keys(const struct reiserfs_key *key1,
			      const struct reiserfs_key *key2)
L
Linus Torvalds 已提交
138
{
139 140 141 142 143 144 145 146 147 148 149 150
	__u32 *p_s_1_u32, *p_s_2_u32;
	int n_key_length = REISERFS_SHORT_KEY_LEN;

	p_s_1_u32 = (__u32 *) key1;
	p_s_2_u32 = (__u32 *) key2;
	for (; n_key_length--; ++p_s_1_u32, ++p_s_2_u32) {
		if (le32_to_cpu(*p_s_1_u32) < le32_to_cpu(*p_s_2_u32))
			return -1;
		if (le32_to_cpu(*p_s_1_u32) > le32_to_cpu(*p_s_2_u32))
			return 1;
	}
	return 0;
L
Linus Torvalds 已提交
151 152
}

153
inline void le_key2cpu_key(struct cpu_key *to, const struct reiserfs_key *from)
L
Linus Torvalds 已提交
154
{
155 156 157 158 159 160 161 162 163
	int version;
	to->on_disk_key.k_dir_id = le32_to_cpu(from->k_dir_id);
	to->on_disk_key.k_objectid = le32_to_cpu(from->k_objectid);

	// find out version of the key
	version = le_key_version(from);
	to->version = version;
	to->on_disk_key.k_offset = le_key_k_offset(version, from);
	to->on_disk_key.k_type = le_key_k_type(version, from);
L
Linus Torvalds 已提交
164 165 166 167
}

// this does not say which one is bigger, it only returns 1 if keys
// are not equal, 0 otherwise
168 169
inline int comp_le_keys(const struct reiserfs_key *k1,
			const struct reiserfs_key *k2)
L
Linus Torvalds 已提交
170
{
171
	return memcmp(k1, k2, sizeof(struct reiserfs_key));
L
Linus Torvalds 已提交
172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
}

/**************************************************************************
 *  Binary search toolkit function                                        *
 *  Search for an item in the array by the item key                       *
 *  Returns:    1 if found,  0 if not found;                              *
 *        *p_n_pos = number of the searched element if found, else the    *
 *        number of the first element that is larger than p_v_key.        *
 **************************************************************************/
/* For those not familiar with binary search: n_lbound is the leftmost item that it
 could be, n_rbound the rightmost item that it could be.  We examine the item
 halfway between n_lbound and n_rbound, and that tells us either that we can increase
 n_lbound, or decrease n_rbound, or that we have found it, or if n_lbound <= n_rbound that
 there are no possible items, and we have not found it. With each examination we
 cut the number of possible items it could be by one more than half rounded down,
 or we find it. */
188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
static inline int bin_search(const void *p_v_key,	/* Key to search for.                   */
			     const void *p_v_base,	/* First item in the array.             */
			     int p_n_num,	/* Number of items in the array.        */
			     int p_n_width,	/* Item size in the array.
						   searched. Lest the reader be
						   confused, note that this is crafted
						   as a general function, and when it
						   is applied specifically to the array
						   of item headers in a node, p_n_width
						   is actually the item header size not
						   the item size.                      */
			     int *p_n_pos	/* Number of the searched for element. */
    )
{
	int n_rbound, n_lbound, n_j;

	for (n_j = ((n_rbound = p_n_num - 1) + (n_lbound = 0)) / 2;
	     n_lbound <= n_rbound; n_j = (n_rbound + n_lbound) / 2)
		switch (comp_keys
			((struct reiserfs_key *)((char *)p_v_base +
						 n_j * p_n_width),
			 (struct cpu_key *)p_v_key)) {
		case -1:
			n_lbound = n_j + 1;
			continue;
		case 1:
			n_rbound = n_j - 1;
			continue;
		case 0:
			*p_n_pos = n_j;
			return ITEM_FOUND;	/* Key found in the array.  */
		}

	/* bin_search did not find given key, it returns position of key,
	   that is minimal and greater than the given one. */
	*p_n_pos = n_lbound;
	return ITEM_NOT_FOUND;
L
Linus Torvalds 已提交
225 226 227
}

#ifdef CONFIG_REISERFS_CHECK
228
extern struct tree_balance *cur_tb;
L
Linus Torvalds 已提交
229 230 231
#endif

/* Minimal possible key. It is never in the tree. */
232
const struct reiserfs_key MIN_KEY = { 0, 0, {{0, 0},} };
L
Linus Torvalds 已提交
233 234

/* Maximal possible key. It is never in the tree. */
235
static const struct reiserfs_key MAX_KEY = {
236 237 238
	__constant_cpu_to_le32(0xffffffff),
	__constant_cpu_to_le32(0xffffffff),
	{{__constant_cpu_to_le32(0xffffffff),
239
	  __constant_cpu_to_le32(0xffffffff)},}
240
};
L
Linus Torvalds 已提交
241 242 243 244 245

/* Get delimiting key of the buffer by looking for it in the buffers in the path, starting from the bottom
   of the path, and going upwards.  We must check the path's validity at each step.  If the key is not in
   the path, there is no delimiting key in the tree (buffer is first or last buffer in tree), and in this
   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 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288
						  *p_s_chk_path,
						  const struct super_block
						  *p_s_sb)
{
	int n_position, n_path_offset = p_s_chk_path->path_length;
	struct buffer_head *p_s_parent;

	RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET,
	       "PAP-5010: invalid offset in the path");

	/* While not higher in path than first element. */
	while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {

		RFALSE(!buffer_uptodate
		       (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)),
		       "PAP-5020: parent is not uptodate");

		/* Parent at the path is not in the tree now. */
		if (!B_IS_IN_TREE
		    (p_s_parent =
		     PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)))
			return &MAX_KEY;
		/* Check whether position in the parent is correct. */
		if ((n_position =
		     PATH_OFFSET_POSITION(p_s_chk_path,
					  n_path_offset)) >
		    B_NR_ITEMS(p_s_parent))
			return &MAX_KEY;
		/* Check whether parent at the path really points to the child. */
		if (B_N_CHILD_NUM(p_s_parent, n_position) !=
		    PATH_OFFSET_PBUFFER(p_s_chk_path,
					n_path_offset + 1)->b_blocknr)
			return &MAX_KEY;
		/* Return delimiting key if position in the parent is not equal to zero. */
		if (n_position)
			return B_N_PDELIM_KEY(p_s_parent, n_position - 1);
	}
	/* Return MIN_KEY if we are in the root of the buffer tree. */
	if (PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->
	    b_blocknr == SB_ROOT_BLOCK(p_s_sb))
		return &MIN_KEY;
	return &MAX_KEY;
L
Linus Torvalds 已提交
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 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331
					   const struct super_block *p_s_sb)
{
	int n_position, n_path_offset = p_s_chk_path->path_length;
	struct buffer_head *p_s_parent;

	RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET,
	       "PAP-5030: invalid offset in the path");

	while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {

		RFALSE(!buffer_uptodate
		       (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)),
		       "PAP-5040: parent is not uptodate");

		/* Parent at the path is not in the tree now. */
		if (!B_IS_IN_TREE
		    (p_s_parent =
		     PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)))
			return &MIN_KEY;
		/* Check whether position in the parent is correct. */
		if ((n_position =
		     PATH_OFFSET_POSITION(p_s_chk_path,
					  n_path_offset)) >
		    B_NR_ITEMS(p_s_parent))
			return &MIN_KEY;
		/* Check whether parent at the path really points to the child. */
		if (B_N_CHILD_NUM(p_s_parent, n_position) !=
		    PATH_OFFSET_PBUFFER(p_s_chk_path,
					n_path_offset + 1)->b_blocknr)
			return &MIN_KEY;
		/* Return delimiting key if position in the parent is not the last one. */
		if (n_position != B_NR_ITEMS(p_s_parent))
			return B_N_PDELIM_KEY(p_s_parent, n_position);
	}
	/* Return MAX_KEY if we are in the root of the buffer tree. */
	if (PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->
	    b_blocknr == SB_ROOT_BLOCK(p_s_sb))
		return &MAX_KEY;
	return &MIN_KEY;
L
Linus Torvalds 已提交
332 333 334 335 336 337 338
}

/* Check whether a key is contained in the tree rooted from a buffer at a path. */
/* This works by looking at the left and right delimiting keys for the buffer in the last path_element in
   the path.  These delimiting keys are stored at least one level above that buffer in the tree. If the
   buffer is the first or last node in the tree order then one of the delimiting keys may be absent, and in
   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 341 342 343
				const struct cpu_key *p_s_key,	/* Key which should be checked.   */
				struct super_block *p_s_sb	/* Super block pointer.           */
    )
{
L
Linus Torvalds 已提交
344

345 346 347 348 349 350 351 352 353 354 355 356 357 358 359
	RFALSE(!p_s_key || p_s_chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET
	       || p_s_chk_path->path_length > MAX_HEIGHT,
	       "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)",
	       p_s_key, p_s_chk_path->path_length);
	RFALSE(!PATH_PLAST_BUFFER(p_s_chk_path)->b_bdev,
	       "PAP-5060: device must not be NODEV");

	if (comp_keys(get_lkey(p_s_chk_path, p_s_sb), p_s_key) == 1)
		/* left delimiting key is bigger, that the key we look for */
		return 0;
	//  if ( comp_keys(p_s_key, get_rkey(p_s_chk_path, p_s_sb)) != -1 )
	if (comp_keys(get_rkey(p_s_chk_path, p_s_sb), p_s_key) != 1)
		/* p_s_key must be less than right delimitiing key */
		return 0;
	return 1;
L
Linus Torvalds 已提交
360 361
}

362 363 364 365 366 367 368
inline void decrement_bcount(struct buffer_head *p_s_bh)
{
	if (p_s_bh) {
		if (atomic_read(&(p_s_bh->b_count))) {
			put_bh(p_s_bh);
			return;
		}
J
Jeff Mahoney 已提交
369 370
		reiserfs_panic(NULL, "PAP-5070",
			       "trying to free free buffer %b", p_s_bh);
371 372
	}
}
L
Linus Torvalds 已提交
373 374

/* Decrement b_count field of the all buffers in the path. */
375
void decrement_counters_in_path(struct treepath *p_s_search_path)
376 377 378 379 380 381
{
	int n_path_offset = p_s_search_path->path_length;

	RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET ||
	       n_path_offset > EXTENDED_MAX_HEIGHT - 1,
	       "PAP-5080: invalid path offset of %d", n_path_offset);
L
Linus Torvalds 已提交
382

383 384
	while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) {
		struct buffer_head *bh;
L
Linus Torvalds 已提交
385

386 387 388 389
		bh = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--);
		decrement_bcount(bh);
	}
	p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
L
Linus Torvalds 已提交
390 391
}

392
int reiserfs_check_path(struct treepath *p)
393 394 395 396 397
{
	RFALSE(p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET,
	       "path not properly relsed");
	return 0;
}
L
Linus Torvalds 已提交
398 399 400 401 402 403

/* Release all buffers in the path. Restore dirty bits clean
** when preparing the buffer for the log
**
** only called from fix_nodes()
*/
404
void pathrelse_and_restore(struct super_block *s, struct treepath *p_s_search_path)
405 406 407 408 409 410 411 412 413 414 415 416 417 418
{
	int n_path_offset = p_s_search_path->path_length;

	RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
	       "clm-4000: invalid path offset");

	while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) {
		reiserfs_restore_prepared_buffer(s,
						 PATH_OFFSET_PBUFFER
						 (p_s_search_path,
						  n_path_offset));
		brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
	}
	p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
L
Linus Torvalds 已提交
419 420 421
}

/* Release all buffers in the path. */
422
void pathrelse(struct treepath *p_s_search_path)
423 424
{
	int n_path_offset = p_s_search_path->path_length;
L
Linus Torvalds 已提交
425

426 427
	RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
	       "PAP-5090: invalid path offset");
L
Linus Torvalds 已提交
428

429 430
	while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET)
		brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
L
Linus Torvalds 已提交
431

432 433
	p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
}
L
Linus Torvalds 已提交
434

435 436 437 438 439 440 441 442 443 444 445
static int is_leaf(char *buf, int blocksize, struct buffer_head *bh)
{
	struct block_head *blkh;
	struct item_head *ih;
	int used_space;
	int prev_location;
	int i;
	int nr;

	blkh = (struct block_head *)buf;
	if (blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) {
J
Jeff Mahoney 已提交
446 447
		reiserfs_warning(NULL, "reiserfs-5080",
				 "this should be caught earlier");
448
		return 0;
L
Linus Torvalds 已提交
449
	}
450 451 452 453

	nr = blkh_nr_item(blkh);
	if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) {
		/* item number is too big or too small */
J
Jeff Mahoney 已提交
454 455
		reiserfs_warning(NULL, "reiserfs-5081",
				 "nr_item seems wrong: %z", bh);
456
		return 0;
L
Linus Torvalds 已提交
457
	}
458 459 460 461
	ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1;
	used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location(ih));
	if (used_space != blocksize - blkh_free_space(blkh)) {
		/* free space does not match to calculated amount of use space */
J
Jeff Mahoney 已提交
462 463
		reiserfs_warning(NULL, "reiserfs-5082",
				 "free space seems wrong: %z", bh);
464
		return 0;
L
Linus Torvalds 已提交
465
	}
466 467 468 469 470 471 472 473
	// FIXME: it is_leaf will hit performance too much - we may have
	// return 1 here

	/* check tables of item heads */
	ih = (struct item_head *)(buf + BLKH_SIZE);
	prev_location = blocksize;
	for (i = 0; i < nr; i++, ih++) {
		if (le_ih_k_type(ih) == TYPE_ANY) {
J
Jeff Mahoney 已提交
474 475
			reiserfs_warning(NULL, "reiserfs-5083",
					 "wrong item type for item %h",
476 477 478 479 480
					 ih);
			return 0;
		}
		if (ih_location(ih) >= blocksize
		    || ih_location(ih) < IH_SIZE * nr) {
J
Jeff Mahoney 已提交
481 482
			reiserfs_warning(NULL, "reiserfs-5084",
					 "item location seems wrong: %h",
483 484 485 486 487
					 ih);
			return 0;
		}
		if (ih_item_len(ih) < 1
		    || ih_item_len(ih) > MAX_ITEM_LEN(blocksize)) {
J
Jeff Mahoney 已提交
488 489
			reiserfs_warning(NULL, "reiserfs-5085",
					 "item length seems wrong: %h",
490 491 492 493
					 ih);
			return 0;
		}
		if (prev_location - ih_location(ih) != ih_item_len(ih)) {
J
Jeff Mahoney 已提交
494 495 496
			reiserfs_warning(NULL, "reiserfs-5086",
					 "item location seems wrong "
					 "(second one): %h", ih);
497 498 499
			return 0;
		}
		prev_location = ih_location(ih);
L
Linus Torvalds 已提交
500 501
	}

502 503
	// one may imagine much more checks
	return 1;
L
Linus Torvalds 已提交
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)
L
Linus Torvalds 已提交
508
{
509 510 511 512 513 514 515 516
	struct block_head *blkh;
	int nr;
	int used_space;

	blkh = (struct block_head *)buf;
	nr = blkh_level(blkh);
	if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) {
		/* this level is not possible for internal nodes */
J
Jeff Mahoney 已提交
517 518
		reiserfs_warning(NULL, "reiserfs-5087",
				 "this should be caught earlier");
519 520
		return 0;
	}
L
Linus Torvalds 已提交
521

522 523 524
	nr = blkh_nr_item(blkh);
	if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) {
		/* for internal which is not root we might check min number of keys */
J
Jeff Mahoney 已提交
525 526
		reiserfs_warning(NULL, "reiserfs-5088",
				 "number of key seems wrong: %z", bh);
527 528
		return 0;
	}
L
Linus Torvalds 已提交
529

530 531
	used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1);
	if (used_space != blocksize - blkh_free_space(blkh)) {
J
Jeff Mahoney 已提交
532 533
		reiserfs_warning(NULL, "reiserfs-5089",
				 "free space seems wrong: %z", bh);
534 535 536 537
		return 0;
	}
	// one may imagine much more checks
	return 1;
L
Linus Torvalds 已提交
538 539 540 541
}

// make sure that bh contains formatted node of reiserfs tree of
// 'level'-th level
542
static int is_tree_node(struct buffer_head *bh, int level)
L
Linus Torvalds 已提交
543
{
544
	if (B_LEVEL(bh) != level) {
J
Jeff Mahoney 已提交
545 546
		reiserfs_warning(NULL, "reiserfs-5090", "node level %d does "
				 "not match to the expected one %d",
547 548 549 550 551
				 B_LEVEL(bh), level);
		return 0;
	}
	if (level == DISK_LEAF_NODE_LEVEL)
		return is_leaf(bh->b_data, bh->b_size, bh);
L
Linus Torvalds 已提交
552

553
	return is_internal(bh->b_data, bh->b_size, bh);
L
Linus Torvalds 已提交
554 555 556 557 558
}

#define SEARCH_BY_KEY_READA 16

/* The function is NOT SCHEDULE-SAFE! */
559 560
static void search_by_key_reada(struct super_block *s,
				struct buffer_head **bh,
561
				b_blocknr_t *b, int num)
L
Linus Torvalds 已提交
562
{
563 564 565 566 567 568 569 570 571 572 573 574 575 576
	int i, j;

	for (i = 0; i < num; i++) {
		bh[i] = sb_getblk(s, b[i]);
	}
	for (j = 0; j < i; j++) {
		/*
		 * note, this needs attention if we are getting rid of the BKL
		 * you have to make sure the prepared bit isn't set on this buffer
		 */
		if (!buffer_uptodate(bh[j]))
			ll_rw_block(READA, 1, bh + j);
		brelse(bh[j]);
	}
L
Linus Torvalds 已提交
577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601
}

/**************************************************************************
 * Algorithm   SearchByKey                                                *
 *             look for item in the Disk S+Tree by its key                *
 * Input:  p_s_sb   -  super block                                        *
 *         p_s_key  - pointer to the key to search                        *
 * Output: ITEM_FOUND, ITEM_NOT_FOUND or IO_ERROR                         *
 *         p_s_search_path - path from the root to the needed leaf        *
 **************************************************************************/

/* This function fills up the path from the root to the leaf as it
   descends the tree looking for the key.  It uses reiserfs_bread to
   try to find buffers in the cache given their block number.  If it
   does not find them in the cache it reads them from disk.  For each
   node search_by_key finds using reiserfs_bread it then uses
   bin_search to look through that node.  bin_search will find the
   position of the block_number of the next node if it is looking
   through an internal node.  If it is looking through a leaf node
   bin_search will find the position of the item which has key either
   equal to given key, or which is the maximal key less than the given
   key.  search_by_key returns a path that must be checked for the
   correctness of the top of the path but need not be checked for the
   correctness of the bottom of the path */
/* The function is NOT SCHEDULE-SAFE! */
602
int search_by_key(struct super_block *p_s_sb, const struct cpu_key *p_s_key,	/* Key to search. */
603
		  struct treepath *p_s_search_path,/* This structure was
604 605 606 607 608 609 610 611 612
						   allocated and initialized
						   by the calling
						   function. It is filled up
						   by this function.  */
		  int n_stop_level	/* How far down the tree to search. To
					   stop at leaf level - set to
					   DISK_LEAF_NODE_LEVEL */
    )
{
613
	b_blocknr_t n_block_number;
614 615 616 617 618 619 620
	int expected_level;
	struct buffer_head *p_s_bh;
	struct path_element *p_s_last_element;
	int n_node_level, n_retval;
	int right_neighbor_of_leaf_node;
	int fs_gen;
	struct buffer_head *reada_bh[SEARCH_BY_KEY_READA];
621
	b_blocknr_t reada_blocks[SEARCH_BY_KEY_READA];
622
	int reada_count = 0;
L
Linus Torvalds 已提交
623 624

#ifdef CONFIG_REISERFS_CHECK
625
	int n_repeat_counter = 0;
L
Linus Torvalds 已提交
626 627
#endif

628 629 630 631 632
	PROC_INFO_INC(p_s_sb, search_by_key);

	/* As we add each node to a path we increase its count.  This means that
	   we must be careful to release all nodes in a path before we either
	   discard the path struct or re-use the path struct, as we do here. */
L
Linus Torvalds 已提交
633

634
	decrement_counters_in_path(p_s_search_path);
L
Linus Torvalds 已提交
635

636 637 638 639 640 641 642 643
	right_neighbor_of_leaf_node = 0;

	/* With each iteration of this loop we search through the items in the
	   current node, and calculate the next current node(next path element)
	   for the next iteration of this loop.. */
	n_block_number = SB_ROOT_BLOCK(p_s_sb);
	expected_level = -1;
	while (1) {
L
Linus Torvalds 已提交
644 645

#ifdef CONFIG_REISERFS_CHECK
646
		if (!(++n_repeat_counter % 50000))
J
Jeff Mahoney 已提交
647 648 649
			reiserfs_warning(p_s_sb, "PAP-5100",
					 "%s: there were %d iterations of "
					 "while loop looking for key %K",
650 651
					 current->comm, n_repeat_counter,
					 p_s_key);
L
Linus Torvalds 已提交
652 653
#endif

654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704
		/* prep path to have another element added to it. */
		p_s_last_element =
		    PATH_OFFSET_PELEMENT(p_s_search_path,
					 ++p_s_search_path->path_length);
		fs_gen = get_generation(p_s_sb);

		/* Read the next tree node, and set the last element in the path to
		   have a pointer to it. */
		if ((p_s_bh = p_s_last_element->pe_buffer =
		     sb_getblk(p_s_sb, n_block_number))) {
			if (!buffer_uptodate(p_s_bh) && reada_count > 1) {
				search_by_key_reada(p_s_sb, reada_bh,
						    reada_blocks, reada_count);
			}
			ll_rw_block(READ, 1, &p_s_bh);
			wait_on_buffer(p_s_bh);
			if (!buffer_uptodate(p_s_bh))
				goto io_error;
		} else {
		      io_error:
			p_s_search_path->path_length--;
			pathrelse(p_s_search_path);
			return IO_ERROR;
		}
		reada_count = 0;
		if (expected_level == -1)
			expected_level = SB_TREE_HEIGHT(p_s_sb);
		expected_level--;

		/* It is possible that schedule occurred. We must check whether the key
		   to search is still in the tree rooted from the current buffer. If
		   not then repeat search from the root. */
		if (fs_changed(fs_gen, p_s_sb) &&
		    (!B_IS_IN_TREE(p_s_bh) ||
		     B_LEVEL(p_s_bh) != expected_level ||
		     !key_in_buffer(p_s_search_path, p_s_key, p_s_sb))) {
			PROC_INFO_INC(p_s_sb, search_by_key_fs_changed);
			PROC_INFO_INC(p_s_sb, search_by_key_restarted);
			PROC_INFO_INC(p_s_sb,
				      sbk_restarted[expected_level - 1]);
			decrement_counters_in_path(p_s_search_path);

			/* Get the root block number so that we can repeat the search
			   starting from the root. */
			n_block_number = SB_ROOT_BLOCK(p_s_sb);
			expected_level = -1;
			right_neighbor_of_leaf_node = 0;

			/* repeat search from the root */
			continue;
		}
L
Linus Torvalds 已提交
705

706 707 708 709 710 711
		/* only check that the key is in the buffer if p_s_key is not
		   equal to the MAX_KEY. Latter case is only possible in
		   "finish_unfinished()" processing during mount. */
		RFALSE(comp_keys(&MAX_KEY, p_s_key) &&
		       !key_in_buffer(p_s_search_path, p_s_key, p_s_sb),
		       "PAP-5130: key is not in the buffer");
L
Linus Torvalds 已提交
712
#ifdef CONFIG_REISERFS_CHECK
713 714
		if (cur_tb) {
			print_cur_tb("5140");
J
Jeff Mahoney 已提交
715 716
			reiserfs_panic(p_s_sb, "PAP-5140",
				       "schedule occurred in do_balance!");
717
		}
L
Linus Torvalds 已提交
718 719
#endif

720 721 722
		// make sure, that the node contents look like a node of
		// certain level
		if (!is_tree_node(p_s_bh, expected_level)) {
J
Jeff Mahoney 已提交
723 724 725
			reiserfs_error(p_s_sb, "vs-5150",
				       "invalid format found in block %ld. "
				       "Fsck?", p_s_bh->b_blocknr);
726 727 728
			pathrelse(p_s_search_path);
			return IO_ERROR;
		}
L
Linus Torvalds 已提交
729

730 731
		/* ok, we have acquired next formatted node in the tree */
		n_node_level = B_LEVEL(p_s_bh);
L
Linus Torvalds 已提交
732

733
		PROC_INFO_BH_STAT(p_s_sb, p_s_bh, n_node_level - 1);
L
Linus Torvalds 已提交
734

735 736 737
		RFALSE(n_node_level < n_stop_level,
		       "vs-5152: tree level (%d) is less than stop level (%d)",
		       n_node_level, n_stop_level);
L
Linus Torvalds 已提交
738

739 740 741 742 743 744 745 746 747
		n_retval = bin_search(p_s_key, B_N_PITEM_HEAD(p_s_bh, 0),
				      B_NR_ITEMS(p_s_bh),
				      (n_node_level ==
				       DISK_LEAF_NODE_LEVEL) ? IH_SIZE :
				      KEY_SIZE,
				      &(p_s_last_element->pe_position));
		if (n_node_level == n_stop_level) {
			return n_retval;
		}
L
Linus Torvalds 已提交
748

749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791
		/* we are not in the stop level */
		if (n_retval == ITEM_FOUND)
			/* item has been found, so we choose the pointer which is to the right of the found one */
			p_s_last_element->pe_position++;

		/* if item was not found we choose the position which is to
		   the left of the found item. This requires no code,
		   bin_search did it already. */

		/* So we have chosen a position in the current node which is
		   an internal node.  Now we calculate child block number by
		   position in the node. */
		n_block_number =
		    B_N_CHILD_NUM(p_s_bh, p_s_last_element->pe_position);

		/* if we are going to read leaf nodes, try for read ahead as well */
		if ((p_s_search_path->reada & PATH_READA) &&
		    n_node_level == DISK_LEAF_NODE_LEVEL + 1) {
			int pos = p_s_last_element->pe_position;
			int limit = B_NR_ITEMS(p_s_bh);
			struct reiserfs_key *le_key;

			if (p_s_search_path->reada & PATH_READA_BACK)
				limit = 0;
			while (reada_count < SEARCH_BY_KEY_READA) {
				if (pos == limit)
					break;
				reada_blocks[reada_count++] =
				    B_N_CHILD_NUM(p_s_bh, pos);
				if (p_s_search_path->reada & PATH_READA_BACK)
					pos--;
				else
					pos++;

				/*
				 * check to make sure we're in the same object
				 */
				le_key = B_N_PDELIM_KEY(p_s_bh, pos);
				if (le32_to_cpu(le_key->k_objectid) !=
				    p_s_key->on_disk_key.k_objectid) {
					break;
				}
			}
L
Linus Torvalds 已提交
792
		}
793
	}
L
Linus Torvalds 已提交
794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811
}

/* Form the path to an item and position in this item which contains
   file byte defined by p_s_key. If there is no such item
   corresponding to the key, we point the path to the item with
   maximal key less than p_s_key, and *p_n_pos_in_item is set to one
   past the last entry/byte in the item.  If searching for entry in a
   directory item, and it is not found, *p_n_pos_in_item is set to one
   entry more than the entry with maximal key which is less than the
   sought key.

   Note that if there is no entry in this same node which is one more,
   then we point to an imaginary entry.  for direct items, the
   position is in units of bytes, for indirect items the position is
   in units of blocknr entries, for directory items the position is in
   units of directory entries.  */

/* The function is NOT SCHEDULE-SAFE! */
812 813
int search_for_position_by_key(struct super_block *p_s_sb,	/* Pointer to the super block.          */
			       const struct cpu_key *p_cpu_key,	/* Key to search (cpu variable)         */
814
			       struct treepath *p_s_search_path	/* Filled up by this function.          */
815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834
    )
{
	struct item_head *p_le_ih;	/* pointer to on-disk structure */
	int n_blk_size;
	loff_t item_offset, offset;
	struct reiserfs_dir_entry de;
	int retval;

	/* If searching for directory entry. */
	if (is_direntry_cpu_key(p_cpu_key))
		return search_by_entry_key(p_s_sb, p_cpu_key, p_s_search_path,
					   &de);

	/* If not searching for directory entry. */

	/* If item is found. */
	retval = search_item(p_s_sb, p_cpu_key, p_s_search_path);
	if (retval == IO_ERROR)
		return retval;
	if (retval == ITEM_FOUND) {
L
Linus Torvalds 已提交
835

836 837 838 839 840
		RFALSE(!ih_item_len
		       (B_N_PITEM_HEAD
			(PATH_PLAST_BUFFER(p_s_search_path),
			 PATH_LAST_POSITION(p_s_search_path))),
		       "PAP-5165: item length equals zero");
L
Linus Torvalds 已提交
841

842 843 844
		pos_in_item(p_s_search_path) = 0;
		return POSITION_FOUND;
	}
L
Linus Torvalds 已提交
845

846 847
	RFALSE(!PATH_LAST_POSITION(p_s_search_path),
	       "PAP-5170: position equals zero");
L
Linus Torvalds 已提交
848

849 850 851 852 853
	/* Item is not found. Set path to the previous item. */
	p_le_ih =
	    B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path),
			   --PATH_LAST_POSITION(p_s_search_path));
	n_blk_size = p_s_sb->s_blocksize;
L
Linus Torvalds 已提交
854

855 856 857 858
	if (comp_short_keys(&(p_le_ih->ih_key), p_cpu_key)) {
		return FILE_NOT_FOUND;
	}
	// FIXME: quite ugly this far
L
Linus Torvalds 已提交
859

860 861
	item_offset = le_ih_k_offset(p_le_ih);
	offset = cpu_key_k_offset(p_cpu_key);
L
Linus Torvalds 已提交
862

863 864 865 866 867 868 869 870
	/* Needed byte is contained in the item pointed to by the path. */
	if (item_offset <= offset &&
	    item_offset + op_bytes_number(p_le_ih, n_blk_size) > offset) {
		pos_in_item(p_s_search_path) = offset - item_offset;
		if (is_indirect_le_ih(p_le_ih)) {
			pos_in_item(p_s_search_path) /= n_blk_size;
		}
		return POSITION_FOUND;
L
Linus Torvalds 已提交
871 872
	}

873 874 875 876 877 878 879 880 881 882
	/* Needed byte is not contained in the item pointed to by the
	   path. Set pos_in_item out of the item. */
	if (is_indirect_le_ih(p_le_ih))
		pos_in_item(p_s_search_path) =
		    ih_item_len(p_le_ih) / UNFM_P_SIZE;
	else
		pos_in_item(p_s_search_path) = ih_item_len(p_le_ih);

	return POSITION_NOT_FOUND;
}
L
Linus Torvalds 已提交
883 884

/* Compare given item and item pointed to by the path. */
885
int comp_items(const struct item_head *stored_ih, const struct treepath *p_s_path)
L
Linus Torvalds 已提交
886
{
887 888
	struct buffer_head *p_s_bh;
	struct item_head *ih;
L
Linus Torvalds 已提交
889

890 891 892
	/* Last buffer at the path is not in the tree. */
	if (!B_IS_IN_TREE(p_s_bh = PATH_PLAST_BUFFER(p_s_path)))
		return 1;
L
Linus Torvalds 已提交
893

894 895 896
	/* Last path position is invalid. */
	if (PATH_LAST_POSITION(p_s_path) >= B_NR_ITEMS(p_s_bh))
		return 1;
L
Linus Torvalds 已提交
897

898 899 900
	/* we need only to know, whether it is the same item */
	ih = get_ih(p_s_path);
	return memcmp(stored_ih, ih, IH_SIZE);
L
Linus Torvalds 已提交
901 902 903 904 905 906 907 908 909 910 911
}

/* unformatted nodes are not logged anymore, ever.  This is safe
** now
*/
#define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1)

// block can not be forgotten as it is in I/O or held by someone
#define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh)))

// prepare for delete or cut of direct item
912
static inline int prepare_for_direct_item(struct treepath *path,
913 914 915
					  struct item_head *le_ih,
					  struct inode *inode,
					  loff_t new_file_length, int *cut_size)
L
Linus Torvalds 已提交
916
{
917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944
	loff_t round_len;

	if (new_file_length == max_reiserfs_offset(inode)) {
		/* item has to be deleted */
		*cut_size = -(IH_SIZE + ih_item_len(le_ih));
		return M_DELETE;
	}
	// new file gets truncated
	if (get_inode_item_key_version(inode) == KEY_FORMAT_3_6) {
		// 
		round_len = ROUND_UP(new_file_length);
		/* this was n_new_file_length < le_ih ... */
		if (round_len < le_ih_k_offset(le_ih)) {
			*cut_size = -(IH_SIZE + ih_item_len(le_ih));
			return M_DELETE;	/* Delete this item. */
		}
		/* Calculate first position and size for cutting from item. */
		pos_in_item(path) = round_len - (le_ih_k_offset(le_ih) - 1);
		*cut_size = -(ih_item_len(le_ih) - pos_in_item(path));

		return M_CUT;	/* Cut from this item. */
	}

	// old file: items may have any length

	if (new_file_length < le_ih_k_offset(le_ih)) {
		*cut_size = -(IH_SIZE + ih_item_len(le_ih));
		return M_DELETE;	/* Delete this item. */
L
Linus Torvalds 已提交
945 946
	}
	/* Calculate first position and size for cutting from item. */
947 948 949 950
	*cut_size = -(ih_item_len(le_ih) -
		      (pos_in_item(path) =
		       new_file_length + 1 - le_ih_k_offset(le_ih)));
	return M_CUT;		/* Cut from this item. */
L
Linus Torvalds 已提交
951 952
}

953
static inline int prepare_for_direntry_item(struct treepath *path,
954 955 956 957
					    struct item_head *le_ih,
					    struct inode *inode,
					    loff_t new_file_length,
					    int *cut_size)
L
Linus Torvalds 已提交
958
{
959 960 961 962 963 964 965
	if (le_ih_k_offset(le_ih) == DOT_OFFSET &&
	    new_file_length == max_reiserfs_offset(inode)) {
		RFALSE(ih_entry_count(le_ih) != 2,
		       "PAP-5220: incorrect empty directory item (%h)", le_ih);
		*cut_size = -(IH_SIZE + ih_item_len(le_ih));
		return M_DELETE;	/* Delete the directory item containing "." and ".." entry. */
	}
L
Linus Torvalds 已提交
966

967 968 969 970 971 972 973 974 975 976 977 978 979
	if (ih_entry_count(le_ih) == 1) {
		/* Delete the directory item such as there is one record only
		   in this item */
		*cut_size = -(IH_SIZE + ih_item_len(le_ih));
		return M_DELETE;
	}

	/* Cut one record from the directory item. */
	*cut_size =
	    -(DEH_SIZE +
	      entry_length(get_last_bh(path), le_ih, pos_in_item(path)));
	return M_CUT;
}
L
Linus Torvalds 已提交
980

981 982
#define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1)

L
Linus Torvalds 已提交
983 984 985 986 987
/*  If the path points to a directory or direct item, calculate mode and the size cut, for balance.
    If the path points to an indirect item, remove some number of its unformatted nodes.
    In case of file truncate calculate whether this item must be deleted/truncated or last
    unformatted node of this item will be converted to a direct item.
    This function returns a determination of what balance mode the calling function should employ. */
988
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
989 990 991 992 993 994 995
																						   from end of the file. */
				      int *p_n_cut_size, unsigned long long n_new_file_length	/* MAX_KEY_OFFSET in case of delete. */
    )
{
	struct super_block *p_s_sb = inode->i_sb;
	struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_path);
	struct buffer_head *p_s_bh = PATH_PLAST_BUFFER(p_s_path);
L
Linus Torvalds 已提交
996

997
	BUG_ON(!th->t_trans_id);
L
Linus Torvalds 已提交
998

999 1000
	/* Stat_data item. */
	if (is_statdata_le_ih(p_le_ih)) {
L
Linus Torvalds 已提交
1001

1002 1003
		RFALSE(n_new_file_length != max_reiserfs_offset(inode),
		       "PAP-5210: mode must be M_DELETE");
L
Linus Torvalds 已提交
1004

1005 1006 1007
		*p_n_cut_size = -(IH_SIZE + ih_item_len(p_le_ih));
		return M_DELETE;
	}
L
Linus Torvalds 已提交
1008

1009 1010 1011 1012 1013
	/* Directory item. */
	if (is_direntry_le_ih(p_le_ih))
		return prepare_for_direntry_item(p_s_path, p_le_ih, inode,
						 n_new_file_length,
						 p_n_cut_size);
L
Linus Torvalds 已提交
1014

1015 1016 1017 1018 1019 1020 1021
	/* Direct item. */
	if (is_direct_le_ih(p_le_ih))
		return prepare_for_direct_item(p_s_path, p_le_ih, inode,
					       n_new_file_length, p_n_cut_size);

	/* Case of an indirect item. */
	{
1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041
	    int blk_size = p_s_sb->s_blocksize;
	    struct item_head s_ih;
	    int need_re_search;
	    int delete = 0;
	    int result = M_CUT;
	    int pos = 0;

	    if ( n_new_file_length == max_reiserfs_offset (inode) ) {
		/* prepare_for_delete_or_cut() is called by
		 * reiserfs_delete_item() */
		n_new_file_length = 0;
		delete = 1;
	    }

	    do {
		need_re_search = 0;
		*p_n_cut_size = 0;
		p_s_bh = PATH_PLAST_BUFFER(p_s_path);
		copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
		pos = I_UNFM_NUM(&s_ih);
1042

1043
		while (le_ih_k_offset (&s_ih) + (pos - 1) * blk_size > n_new_file_length) {
A
Al Viro 已提交
1044 1045
		    __le32 *unfm;
		    __u32 block;
1046

1047 1048 1049 1050 1051 1052 1053
		    /* Each unformatted block deletion may involve one additional
		     * bitmap block into the transaction, thereby the initial
		     * journal space reservation might not be enough. */
		    if (!delete && (*p_n_cut_size) != 0 &&
			reiserfs_transaction_free_space(th) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) {
			break;
		    }
1054

A
Al Viro 已提交
1055
		    unfm = (__le32 *)B_I_PITEM(p_s_bh, &s_ih) + pos - 1;
1056
		    block = get_block_num(unfm, 0);
1057

1058 1059 1060 1061 1062 1063
		    if (block != 0) {
			reiserfs_prepare_for_journal(p_s_sb, p_s_bh, 1);
			put_block_num(unfm, 0, 0);
			journal_mark_dirty (th, p_s_sb, p_s_bh);
			reiserfs_free_block(th, inode, block, 1);
		    }
1064

1065
		    cond_resched();
1066

1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095
		    if (item_moved (&s_ih, p_s_path))  {
			need_re_search = 1;
			break;
		    }

		    pos --;
		    (*p_n_removed) ++;
		    (*p_n_cut_size) -= UNFM_P_SIZE;

		    if (pos == 0) {
			(*p_n_cut_size) -= IH_SIZE;
			result = M_DELETE;
			break;
		    }
		}
		/* a trick.  If the buffer has been logged, this will do nothing.  If
		** we've broken the loop without logging it, it will restore the
		** buffer */
		reiserfs_restore_prepared_buffer(p_s_sb, p_s_bh);
	    } while (need_re_search &&
		     search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path) == POSITION_FOUND);
	    pos_in_item(p_s_path) = pos * UNFM_P_SIZE;

	    if (*p_n_cut_size == 0) {
		/* Nothing were cut. maybe convert last unformatted node to the
		 * direct item? */
		result = M_CONVERT;
	    }
	    return result;
1096
	}
L
Linus Torvalds 已提交
1097 1098 1099
}

/* Calculate number of bytes which will be deleted or cut during balance */
1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117
static int calc_deleted_bytes_number(struct tree_balance *p_s_tb, char c_mode)
{
	int n_del_size;
	struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_tb->tb_path);

	if (is_statdata_le_ih(p_le_ih))
		return 0;

	n_del_size =
	    (c_mode ==
	     M_DELETE) ? ih_item_len(p_le_ih) : -p_s_tb->insert_size[0];
	if (is_direntry_le_ih(p_le_ih)) {
		// return EMPTY_DIR_SIZE; /* We delete emty directoris only. */
		// we can't use EMPTY_DIR_SIZE, as old format dirs have a different
		// empty size.  ick. FIXME, is this right?
		//
		return n_del_size;
	}
L
Linus Torvalds 已提交
1118

1119 1120 1121
	if (is_indirect_le_ih(p_le_ih))
		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);
	return n_del_size;
L
Linus Torvalds 已提交
1122 1123
}

1124 1125 1126
static void init_tb_struct(struct reiserfs_transaction_handle *th,
			   struct tree_balance *p_s_tb,
			   struct super_block *p_s_sb,
1127
			   struct treepath *p_s_path, int n_size)
1128
{
L
Linus Torvalds 已提交
1129

1130
	BUG_ON(!th->t_trans_id);
L
Linus Torvalds 已提交
1131

1132 1133 1134 1135 1136 1137 1138 1139
	memset(p_s_tb, '\0', sizeof(struct tree_balance));
	p_s_tb->transaction_handle = th;
	p_s_tb->tb_sb = p_s_sb;
	p_s_tb->tb_path = p_s_path;
	PATH_OFFSET_PBUFFER(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL;
	PATH_OFFSET_POSITION(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0;
	p_s_tb->insert_size[0] = n_size;
}
L
Linus Torvalds 已提交
1140

1141
void padd_item(char *item, int total_length, int length)
L
Linus Torvalds 已提交
1142
{
1143
	int i;
L
Linus Torvalds 已提交
1144

1145 1146
	for (i = total_length; i > length;)
		item[--i] = 0;
L
Linus Torvalds 已提交
1147 1148 1149 1150 1151
}

#ifdef REISERQUOTA_DEBUG
char key2type(struct reiserfs_key *ih)
{
1152 1153 1154 1155 1156 1157 1158 1159 1160
	if (is_direntry_le_key(2, ih))
		return 'd';
	if (is_direct_le_key(2, ih))
		return 'D';
	if (is_indirect_le_key(2, ih))
		return 'i';
	if (is_statdata_le_key(2, ih))
		return 's';
	return 'u';
L
Linus Torvalds 已提交
1161 1162 1163 1164
}

char head2type(struct item_head *ih)
{
1165 1166 1167 1168 1169 1170 1171 1172 1173
	if (is_direntry_le_ih(ih))
		return 'd';
	if (is_direct_le_ih(ih))
		return 'D';
	if (is_indirect_le_ih(ih))
		return 'i';
	if (is_statdata_le_ih(ih))
		return 's';
	return 'u';
L
Linus Torvalds 已提交
1174 1175 1176 1177
}
#endif

/* Delete object item. */
1178
int reiserfs_delete_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_path,	/* Path to the deleted item. */
1179 1180 1181 1182 1183 1184 1185 1186 1187 1188
			 const struct cpu_key *p_s_item_key,	/* Key to search for the deleted item.  */
			 struct inode *p_s_inode,	/* inode is here just to update i_blocks and quotas */
			 struct buffer_head *p_s_un_bh)
{				/* NULL or unformatted node pointer.    */
	struct super_block *p_s_sb = p_s_inode->i_sb;
	struct tree_balance s_del_balance;
	struct item_head s_ih;
	struct item_head *q_ih;
	int quota_cut_bytes;
	int n_ret_value, n_del_size, n_removed;
L
Linus Torvalds 已提交
1189 1190

#ifdef CONFIG_REISERFS_CHECK
1191 1192
	char c_mode;
	int n_iter = 0;
L
Linus Torvalds 已提交
1193 1194
#endif

1195
	BUG_ON(!th->t_trans_id);
L
Linus Torvalds 已提交
1196

1197 1198
	init_tb_struct(th, &s_del_balance, p_s_sb, p_s_path,
		       0 /*size is unknown */ );
L
Linus Torvalds 已提交
1199

1200 1201
	while (1) {
		n_removed = 0;
L
Linus Torvalds 已提交
1202 1203

#ifdef CONFIG_REISERFS_CHECK
1204 1205
		n_iter++;
		c_mode =
L
Linus Torvalds 已提交
1206
#endif
1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228
		    prepare_for_delete_or_cut(th, p_s_inode, p_s_path,
					      p_s_item_key, &n_removed,
					      &n_del_size,
					      max_reiserfs_offset(p_s_inode));

		RFALSE(c_mode != M_DELETE, "PAP-5320: mode must be M_DELETE");

		copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
		s_del_balance.insert_size[0] = n_del_size;

		n_ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, NULL);
		if (n_ret_value != REPEAT_SEARCH)
			break;

		PROC_INFO_INC(p_s_sb, delete_item_restarted);

		// file system changed, repeat search
		n_ret_value =
		    search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path);
		if (n_ret_value == IO_ERROR)
			break;
		if (n_ret_value == FILE_NOT_FOUND) {
J
Jeff Mahoney 已提交
1229
			reiserfs_warning(p_s_sb, "vs-5340",
1230 1231 1232 1233 1234
					 "no items of the file %K found",
					 p_s_item_key);
			break;
		}
	}			/* while (1) */
L
Linus Torvalds 已提交
1235

1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256
	if (n_ret_value != CARRY_ON) {
		unfix_nodes(&s_del_balance);
		return 0;
	}
	// reiserfs_delete_item returns item length when success
	n_ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE);
	q_ih = get_ih(p_s_path);
	quota_cut_bytes = ih_item_len(q_ih);

	/* hack so the quota code doesn't have to guess if the file
	 ** has a tail.  On tail insert, we allocate quota for 1 unformatted node.
	 ** We test the offset because the tail might have been
	 ** split into multiple items, and we only want to decrement for
	 ** the unfm node once
	 */
	if (!S_ISLNK(p_s_inode->i_mode) && is_direct_le_ih(q_ih)) {
		if ((le_ih_k_offset(q_ih) & (p_s_sb->s_blocksize - 1)) == 1) {
			quota_cut_bytes = p_s_sb->s_blocksize + UNFM_P_SIZE;
		} else {
			quota_cut_bytes = 0;
		}
L
Linus Torvalds 已提交
1257 1258
	}

1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288
	if (p_s_un_bh) {
		int off;
		char *data;

		/* We are in direct2indirect conversion, so move tail contents
		   to the unformatted node */
		/* note, we do the copy before preparing the buffer because we
		 ** don't care about the contents of the unformatted node yet.
		 ** the only thing we really care about is the direct item's data
		 ** is in the unformatted node.
		 **
		 ** Otherwise, we would have to call reiserfs_prepare_for_journal on
		 ** the unformatted node, which might schedule, meaning we'd have to
		 ** loop all the way back up to the start of the while loop.
		 **
		 ** The unformatted node must be dirtied later on.  We can't be
		 ** sure here if the entire tail has been deleted yet.
		 **
		 ** p_s_un_bh is from the page cache (all unformatted nodes are
		 ** from the page cache) and might be a highmem page.  So, we
		 ** can't use p_s_un_bh->b_data.
		 ** -clm
		 */

		data = kmap_atomic(p_s_un_bh->b_page, KM_USER0);
		off = ((le_ih_k_offset(&s_ih) - 1) & (PAGE_CACHE_SIZE - 1));
		memcpy(data + off,
		       B_I_PITEM(PATH_PLAST_BUFFER(p_s_path), &s_ih),
		       n_ret_value);
		kunmap_atomic(data, KM_USER0);
L
Linus Torvalds 已提交
1289
	}
1290 1291
	/* Perform balancing after all resources have been collected at once. */
	do_balance(&s_del_balance, NULL, NULL, M_DELETE);
L
Linus Torvalds 已提交
1292 1293

#ifdef REISERQUOTA_DEBUG
1294 1295 1296
	reiserfs_debug(p_s_sb, REISERFS_DEBUG_CODE,
		       "reiserquota delete_item(): freeing %u, id=%u type=%c",
		       quota_cut_bytes, p_s_inode->i_uid, head2type(&s_ih));
L
Linus Torvalds 已提交
1297
#endif
1298
	DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes);
L
Linus Torvalds 已提交
1299

1300 1301
	/* Return deleted body length */
	return n_ret_value;
L
Linus Torvalds 已提交
1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320
}

/* Summary Of Mechanisms For Handling Collisions Between Processes:

 deletion of the body of the object is performed by iput(), with the
 result that if multiple processes are operating on a file, the
 deletion of the body of the file is deferred until the last process
 that has an open inode performs its iput().

 writes and truncates are protected from collisions by use of
 semaphores.

 creates, linking, and mknod are protected from collisions with other
 processes by making the reiserfs_add_entry() the last step in the
 creation, and then rolling back all changes if there was a collision.
 - Hans
*/

/* this deletes item which never gets split */
1321 1322
void reiserfs_delete_solid_item(struct reiserfs_transaction_handle *th,
				struct inode *inode, struct reiserfs_key *key)
L
Linus Torvalds 已提交
1323
{
1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338
	struct tree_balance tb;
	INITIALIZE_PATH(path);
	int item_len = 0;
	int tb_init = 0;
	struct cpu_key cpu_key;
	int retval;
	int quota_cut_bytes = 0;

	BUG_ON(!th->t_trans_id);

	le_key2cpu_key(&cpu_key, key);

	while (1) {
		retval = search_item(th->t_super, &cpu_key, &path);
		if (retval == IO_ERROR) {
J
Jeff Mahoney 已提交
1339 1340 1341
			reiserfs_error(th->t_super, "vs-5350",
				       "i/o failure occurred trying "
				       "to delete %K", &cpu_key);
1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354
			break;
		}
		if (retval != ITEM_FOUND) {
			pathrelse(&path);
			// No need for a warning, if there is just no free space to insert '..' item into the newly-created subdir
			if (!
			    ((unsigned long long)
			     GET_HASH_VALUE(le_key_k_offset
					    (le_key_version(key), key)) == 0
			     && (unsigned long long)
			     GET_GENERATION_NUMBER(le_key_k_offset
						   (le_key_version(key),
						    key)) == 1))
J
Jeff Mahoney 已提交
1355 1356
				reiserfs_warning(th->t_super, "vs-5355",
						 "%k not found", key);
1357 1358 1359 1360 1361 1362 1363 1364 1365
			break;
		}
		if (!tb_init) {
			tb_init = 1;
			item_len = ih_item_len(PATH_PITEM_HEAD(&path));
			init_tb_struct(th, &tb, th->t_super, &path,
				       -(IH_SIZE + item_len));
		}
		quota_cut_bytes = ih_item_len(PATH_PITEM_HEAD(&path));
L
Linus Torvalds 已提交
1366

1367 1368 1369 1370 1371
		retval = fix_nodes(M_DELETE, &tb, NULL, NULL);
		if (retval == REPEAT_SEARCH) {
			PROC_INFO_INC(th->t_super, delete_solid_item_restarted);
			continue;
		}
L
Linus Torvalds 已提交
1372

1373 1374 1375
		if (retval == CARRY_ON) {
			do_balance(&tb, NULL, NULL, M_DELETE);
			if (inode) {	/* Should we count quota for item? (we don't count quotas for save-links) */
L
Linus Torvalds 已提交
1376
#ifdef REISERQUOTA_DEBUG
1377 1378 1379 1380
				reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE,
					       "reiserquota delete_solid_item(): freeing %u id=%u type=%c",
					       quota_cut_bytes, inode->i_uid,
					       key2type(key));
L
Linus Torvalds 已提交
1381
#endif
1382 1383 1384 1385 1386 1387
				DQUOT_FREE_SPACE_NODIRTY(inode,
							 quota_cut_bytes);
			}
			break;
		}
		// IO_ERROR, NO_DISK_SPACE, etc
J
Jeff Mahoney 已提交
1388
		reiserfs_warning(th->t_super, "vs-5360",
1389 1390 1391 1392
				 "could not delete %K due to fix_nodes failure",
				 &cpu_key);
		unfix_nodes(&tb);
		break;
L
Linus Torvalds 已提交
1393 1394
	}

1395
	reiserfs_check_path(&path);
L
Linus Torvalds 已提交
1396 1397
}

1398 1399
int reiserfs_delete_object(struct reiserfs_transaction_handle *th,
			   struct inode *inode)
L
Linus Torvalds 已提交
1400
{
1401 1402 1403 1404 1405 1406 1407 1408 1409 1410
	int err;
	inode->i_size = 0;
	BUG_ON(!th->t_trans_id);

	/* for directory this deletes item containing "." and ".." */
	err =
	    reiserfs_do_truncate(th, inode, NULL, 0 /*no timestamp updates */ );
	if (err)
		return err;

L
Linus Torvalds 已提交
1411
#if defined( USE_INODE_GENERATION_COUNTER )
1412 1413 1414 1415 1416
	if (!old_format_only(th->t_super)) {
		__le32 *inode_generation;

		inode_generation =
		    &REISERFS_SB(th->t_super)->s_rs->s_inode_generation;
1417
		le32_add_cpu(inode_generation, 1);
1418
	}
L
Linus Torvalds 已提交
1419 1420
/* USE_INODE_GENERATION_COUNTER */
#endif
1421
	reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode));
L
Linus Torvalds 已提交
1422

1423
	return err;
L
Linus Torvalds 已提交
1424 1425
}

1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454
static void unmap_buffers(struct page *page, loff_t pos)
{
	struct buffer_head *bh;
	struct buffer_head *head;
	struct buffer_head *next;
	unsigned long tail_index;
	unsigned long cur_index;

	if (page) {
		if (page_has_buffers(page)) {
			tail_index = pos & (PAGE_CACHE_SIZE - 1);
			cur_index = 0;
			head = page_buffers(page);
			bh = head;
			do {
				next = bh->b_this_page;

				/* we want to unmap the buffers that contain the tail, and
				 ** all the buffers after it (since the tail must be at the
				 ** end of the file).  We don't want to unmap file data
				 ** before the tail, since it might be dirty and waiting to
				 ** reach disk
				 */
				cur_index += bh->b_size;
				if (cur_index > tail_index) {
					reiserfs_unmap_buffer(bh);
				}
				bh = next;
			} while (bh != head);
L
Linus Torvalds 已提交
1455 1456 1457 1458
		}
	}
}

1459 1460 1461
static int maybe_indirect_to_direct(struct reiserfs_transaction_handle *th,
				    struct inode *p_s_inode,
				    struct page *page,
1462
				    struct treepath *p_s_path,
1463 1464 1465 1466 1467 1468 1469
				    const struct cpu_key *p_s_item_key,
				    loff_t n_new_file_size, char *p_c_mode)
{
	struct super_block *p_s_sb = p_s_inode->i_sb;
	int n_block_size = p_s_sb->s_blocksize;
	int cut_bytes;
	BUG_ON(!th->t_trans_id);
1470
	BUG_ON(n_new_file_size != p_s_inode->i_size);
L
Linus Torvalds 已提交
1471

1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490
	/* the page being sent in could be NULL if there was an i/o error
	 ** reading in the last block.  The user will hit problems trying to
	 ** read the file, but for now we just skip the indirect2direct
	 */
	if (atomic_read(&p_s_inode->i_count) > 1 ||
	    !tail_has_to_be_packed(p_s_inode) ||
	    !page || (REISERFS_I(p_s_inode)->i_flags & i_nopack_mask)) {
		// leave tail in an unformatted node    
		*p_c_mode = M_SKIP_BALANCING;
		cut_bytes =
		    n_block_size - (n_new_file_size & (n_block_size - 1));
		pathrelse(p_s_path);
		return cut_bytes;
	}
	/* Permorm the conversion to a direct_item. */
	/*return indirect_to_direct (p_s_inode, p_s_path, p_s_item_key, n_new_file_size, p_c_mode); */
	return indirect2direct(th, p_s_inode, page, p_s_path, p_s_item_key,
			       n_new_file_size, p_c_mode);
}
L
Linus Torvalds 已提交
1491 1492 1493 1494 1495

/* we did indirect_to_direct conversion. And we have inserted direct
   item successesfully, but there were no disk space to cut unfm
   pointer being converted. Therefore we have to delete inserted
   direct item(s) */
1496
static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle *th,
1497
					 struct inode *inode, struct treepath *path)
L
Linus Torvalds 已提交
1498
{
1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512
	struct cpu_key tail_key;
	int tail_len;
	int removed;
	BUG_ON(!th->t_trans_id);

	make_cpu_key(&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4);	// !!!!
	tail_key.key_length = 4;

	tail_len =
	    (cpu_key_k_offset(&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1;
	while (tail_len) {
		/* look for the last byte of the tail */
		if (search_for_position_by_key(inode->i_sb, &tail_key, path) ==
		    POSITION_NOT_FOUND)
J
Jeff Mahoney 已提交
1513 1514
			reiserfs_panic(inode->i_sb, "vs-5615",
				       "found invalid item");
1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530
		RFALSE(path->pos_in_item !=
		       ih_item_len(PATH_PITEM_HEAD(path)) - 1,
		       "vs-5616: appended bytes found");
		PATH_LAST_POSITION(path)--;

		removed =
		    reiserfs_delete_item(th, path, &tail_key, inode,
					 NULL /*unbh not needed */ );
		RFALSE(removed <= 0
		       || removed > tail_len,
		       "vs-5617: there was tail %d bytes, removed item length %d bytes",
		       tail_len, removed);
		tail_len -= removed;
		set_cpu_key_k_offset(&tail_key,
				     cpu_key_k_offset(&tail_key) - removed);
	}
J
Jeff Mahoney 已提交
1531 1532 1533
	reiserfs_warning(inode->i_sb, "reiserfs-5091", "indirect_to_direct "
			 "conversion has been rolled back due to "
			 "lack of disk space");
1534 1535
	//mark_file_without_tail (inode);
	mark_inode_dirty(inode);
L
Linus Torvalds 已提交
1536 1537 1538
}

/* (Truncate or cut entry) or delete object item. Returns < 0 on failure */
1539
int reiserfs_cut_from_item(struct reiserfs_transaction_handle *th,
1540
			   struct treepath *p_s_path,
1541 1542 1543
			   struct cpu_key *p_s_item_key,
			   struct inode *p_s_inode,
			   struct page *page, loff_t n_new_file_size)
L
Linus Torvalds 已提交
1544
{
1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613
	struct super_block *p_s_sb = p_s_inode->i_sb;
	/* Every function which is going to call do_balance must first
	   create a tree_balance structure.  Then it must fill up this
	   structure by using the init_tb_struct and fix_nodes functions.
	   After that we can make tree balancing. */
	struct tree_balance s_cut_balance;
	struct item_head *p_le_ih;
	int n_cut_size = 0,	/* Amount to be cut. */
	    n_ret_value = CARRY_ON, n_removed = 0,	/* Number of the removed unformatted nodes. */
	    n_is_inode_locked = 0;
	char c_mode;		/* Mode of the balance. */
	int retval2 = -1;
	int quota_cut_bytes;
	loff_t tail_pos = 0;

	BUG_ON(!th->t_trans_id);

	init_tb_struct(th, &s_cut_balance, p_s_inode->i_sb, p_s_path,
		       n_cut_size);

	/* Repeat this loop until we either cut the item without needing
	   to balance, or we fix_nodes without schedule occurring */
	while (1) {
		/* Determine the balance mode, position of the first byte to
		   be cut, and size to be cut.  In case of the indirect item
		   free unformatted nodes which are pointed to by the cut
		   pointers. */

		c_mode =
		    prepare_for_delete_or_cut(th, p_s_inode, p_s_path,
					      p_s_item_key, &n_removed,
					      &n_cut_size, n_new_file_size);
		if (c_mode == M_CONVERT) {
			/* convert last unformatted node to direct item or leave
			   tail in the unformatted node */
			RFALSE(n_ret_value != CARRY_ON,
			       "PAP-5570: can not convert twice");

			n_ret_value =
			    maybe_indirect_to_direct(th, p_s_inode, page,
						     p_s_path, p_s_item_key,
						     n_new_file_size, &c_mode);
			if (c_mode == M_SKIP_BALANCING)
				/* tail has been left in the unformatted node */
				return n_ret_value;

			n_is_inode_locked = 1;

			/* removing of last unformatted node will change value we
			   have to return to truncate. Save it */
			retval2 = n_ret_value;
			/*retval2 = p_s_sb->s_blocksize - (n_new_file_size & (p_s_sb->s_blocksize - 1)); */

			/* So, we have performed the first part of the conversion:
			   inserting the new direct item.  Now we are removing the
			   last unformatted node pointer. Set key to search for
			   it. */
			set_cpu_key_k_type(p_s_item_key, TYPE_INDIRECT);
			p_s_item_key->key_length = 4;
			n_new_file_size -=
			    (n_new_file_size & (p_s_sb->s_blocksize - 1));
			tail_pos = n_new_file_size;
			set_cpu_key_k_offset(p_s_item_key, n_new_file_size + 1);
			if (search_for_position_by_key
			    (p_s_sb, p_s_item_key,
			     p_s_path) == POSITION_NOT_FOUND) {
				print_block(PATH_PLAST_BUFFER(p_s_path), 3,
					    PATH_LAST_POSITION(p_s_path) - 1,
					    PATH_LAST_POSITION(p_s_path) + 1);
J
Jeff Mahoney 已提交
1614 1615
				reiserfs_panic(p_s_sb, "PAP-5580", "item to "
					       "convert does not exist (%K)",
1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636
					       p_s_item_key);
			}
			continue;
		}
		if (n_cut_size == 0) {
			pathrelse(p_s_path);
			return 0;
		}

		s_cut_balance.insert_size[0] = n_cut_size;

		n_ret_value = fix_nodes(c_mode, &s_cut_balance, NULL, NULL);
		if (n_ret_value != REPEAT_SEARCH)
			break;

		PROC_INFO_INC(p_s_sb, cut_from_item_restarted);

		n_ret_value =
		    search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path);
		if (n_ret_value == POSITION_FOUND)
			continue;
L
Linus Torvalds 已提交
1637

J
Jeff Mahoney 已提交
1638
		reiserfs_warning(p_s_sb, "PAP-5610", "item %K not found",
1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651
				 p_s_item_key);
		unfix_nodes(&s_cut_balance);
		return (n_ret_value == IO_ERROR) ? -EIO : -ENOENT;
	}			/* while */

	// check fix_nodes results (IO_ERROR or NO_DISK_SPACE)
	if (n_ret_value != CARRY_ON) {
		if (n_is_inode_locked) {
			// FIXME: this seems to be not needed: we are always able
			// to cut item
			indirect_to_direct_roll_back(th, p_s_inode, p_s_path);
		}
		if (n_ret_value == NO_DISK_SPACE)
J
Jeff Mahoney 已提交
1652 1653
			reiserfs_warning(p_s_sb, "reiserfs-5092",
					 "NO_DISK_SPACE");
1654 1655
		unfix_nodes(&s_cut_balance);
		return -EIO;
L
Linus Torvalds 已提交
1656
	}
1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685

	/* go ahead and perform balancing */

	RFALSE(c_mode == M_PASTE || c_mode == M_INSERT, "invalid mode");

	/* Calculate number of bytes that need to be cut from the item. */
	quota_cut_bytes =
	    (c_mode ==
	     M_DELETE) ? ih_item_len(get_ih(p_s_path)) : -s_cut_balance.
	    insert_size[0];
	if (retval2 == -1)
		n_ret_value = calc_deleted_bytes_number(&s_cut_balance, c_mode);
	else
		n_ret_value = retval2;

	/* For direct items, we only change the quota when deleting the last
	 ** item.
	 */
	p_le_ih = PATH_PITEM_HEAD(s_cut_balance.tb_path);
	if (!S_ISLNK(p_s_inode->i_mode) && is_direct_le_ih(p_le_ih)) {
		if (c_mode == M_DELETE &&
		    (le_ih_k_offset(p_le_ih) & (p_s_sb->s_blocksize - 1)) ==
		    1) {
			// FIXME: this is to keep 3.5 happy
			REISERFS_I(p_s_inode)->i_first_direct_byte = U32_MAX;
			quota_cut_bytes = p_s_sb->s_blocksize + UNFM_P_SIZE;
		} else {
			quota_cut_bytes = 0;
		}
L
Linus Torvalds 已提交
1686 1687
	}
#ifdef CONFIG_REISERFS_CHECK
1688 1689 1690 1691 1692 1693 1694
	if (n_is_inode_locked) {
		struct item_head *le_ih =
		    PATH_PITEM_HEAD(s_cut_balance.tb_path);
		/* we are going to complete indirect2direct conversion. Make
		   sure, that we exactly remove last unformatted node pointer
		   of the item */
		if (!is_indirect_le_ih(le_ih))
J
Jeff Mahoney 已提交
1695
			reiserfs_panic(p_s_sb, "vs-5652",
1696 1697 1698
				       "item must be indirect %h", le_ih);

		if (c_mode == M_DELETE && ih_item_len(le_ih) != UNFM_P_SIZE)
J
Jeff Mahoney 已提交
1699 1700 1701 1702
			reiserfs_panic(p_s_sb, "vs-5653", "completing "
				       "indirect2direct conversion indirect "
				       "item %h being deleted must be of "
				       "4 byte long", le_ih);
1703 1704 1705

		if (c_mode == M_CUT
		    && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) {
J
Jeff Mahoney 已提交
1706 1707 1708
			reiserfs_panic(p_s_sb, "vs-5654", "can not complete "
				       "indirect2direct conversion of %h "
				       "(CUT, insert_size==%d)",
1709 1710 1711 1712
				       le_ih, s_cut_balance.insert_size[0]);
		}
		/* it would be useful to make sure, that right neighboring
		   item is direct item of this file */
L
Linus Torvalds 已提交
1713 1714
	}
#endif
1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725

	do_balance(&s_cut_balance, NULL, NULL, c_mode);
	if (n_is_inode_locked) {
		/* we've done an indirect->direct conversion.  when the data block
		 ** was freed, it was removed from the list of blocks that must
		 ** be flushed before the transaction commits, make sure to
		 ** unmap and invalidate it
		 */
		unmap_buffers(page, tail_pos);
		REISERFS_I(p_s_inode)->i_flags &= ~i_pack_on_close_mask;
	}
L
Linus Torvalds 已提交
1726
#ifdef REISERQUOTA_DEBUG
1727 1728 1729
	reiserfs_debug(p_s_inode->i_sb, REISERFS_DEBUG_CODE,
		       "reiserquota cut_from_item(): freeing %u id=%u type=%c",
		       quota_cut_bytes, p_s_inode->i_uid, '?');
L
Linus Torvalds 已提交
1730
#endif
1731 1732
	DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes);
	return n_ret_value;
L
Linus Torvalds 已提交
1733 1734
}

1735 1736
static void truncate_directory(struct reiserfs_transaction_handle *th,
			       struct inode *inode)
L
Linus Torvalds 已提交
1737
{
1738 1739
	BUG_ON(!th->t_trans_id);
	if (inode->i_nlink)
J
Jeff Mahoney 已提交
1740
		reiserfs_error(inode->i_sb, "vs-5655", "link count != 0");
1741 1742 1743 1744 1745 1746 1747

	set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), DOT_OFFSET);
	set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_DIRENTRY);
	reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode));
	reiserfs_update_sd(th, inode);
	set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), SD_OFFSET);
	set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_STAT_DATA);
L
Linus Torvalds 已提交
1748 1749
}

1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780
/* Truncate file to the new size. Note, this must be called with a transaction
   already started */
int reiserfs_do_truncate(struct reiserfs_transaction_handle *th, struct inode *p_s_inode,	/* ->i_size contains new
												   size */
			 struct page *page,	/* up to date for last block */
			 int update_timestamps	/* when it is called by
						   file_release to convert
						   the tail - no timestamps
						   should be updated */
    )
{
	INITIALIZE_PATH(s_search_path);	/* Path to the current object item. */
	struct item_head *p_le_ih;	/* Pointer to an item header. */
	struct cpu_key s_item_key;	/* Key to search for a previous file item. */
	loff_t n_file_size,	/* Old file size. */
	 n_new_file_size;	/* New file size. */
	int n_deleted;		/* Number of deleted or truncated bytes. */
	int retval;
	int err = 0;

	BUG_ON(!th->t_trans_id);
	if (!
	    (S_ISREG(p_s_inode->i_mode) || S_ISDIR(p_s_inode->i_mode)
	     || S_ISLNK(p_s_inode->i_mode)))
		return 0;

	if (S_ISDIR(p_s_inode->i_mode)) {
		// deletion of directory - no need to update timestamps
		truncate_directory(th, p_s_inode);
		return 0;
	}
L
Linus Torvalds 已提交
1781

1782 1783
	/* Get new file size. */
	n_new_file_size = p_s_inode->i_size;
L
Linus Torvalds 已提交
1784

1785 1786 1787
	// FIXME: note, that key type is unimportant here
	make_cpu_key(&s_item_key, p_s_inode, max_reiserfs_offset(p_s_inode),
		     TYPE_DIRECT, 3);
L
Linus Torvalds 已提交
1788

1789 1790 1791 1792
	retval =
	    search_for_position_by_key(p_s_inode->i_sb, &s_item_key,
				       &s_search_path);
	if (retval == IO_ERROR) {
J
Jeff Mahoney 已提交
1793 1794 1795
		reiserfs_error(p_s_inode->i_sb, "vs-5657",
			       "i/o failure occurred trying to truncate %K",
			       &s_item_key);
1796 1797 1798 1799
		err = -EIO;
		goto out;
	}
	if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) {
J
Jeff Mahoney 已提交
1800 1801 1802
		reiserfs_error(p_s_inode->i_sb, "PAP-5660",
			       "wrong result %d of search for %K", retval,
			       &s_item_key);
1803 1804 1805 1806

		err = -EIO;
		goto out;
	}
L
Linus Torvalds 已提交
1807

1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832
	s_search_path.pos_in_item--;

	/* Get real file size (total length of all file items) */
	p_le_ih = PATH_PITEM_HEAD(&s_search_path);
	if (is_statdata_le_ih(p_le_ih))
		n_file_size = 0;
	else {
		loff_t offset = le_ih_k_offset(p_le_ih);
		int bytes =
		    op_bytes_number(p_le_ih, p_s_inode->i_sb->s_blocksize);

		/* this may mismatch with real file size: if last direct item
		   had no padding zeros and last unformatted node had no free
		   space, this file would have this file size */
		n_file_size = offset + bytes - 1;
	}
	/*
	 * are we doing a full truncate or delete, if so
	 * kick in the reada code
	 */
	if (n_new_file_size == 0)
		s_search_path.reada = PATH_READA | PATH_READA_BACK;

	if (n_file_size == 0 || n_file_size < n_new_file_size) {
		goto update_and_out;
L
Linus Torvalds 已提交
1833 1834
	}

1835 1836 1837 1838 1839 1840 1841 1842 1843
	/* Update key to search for the last file item. */
	set_cpu_key_k_offset(&s_item_key, n_file_size);

	do {
		/* Cut or delete file item. */
		n_deleted =
		    reiserfs_cut_from_item(th, &s_search_path, &s_item_key,
					   p_s_inode, page, n_new_file_size);
		if (n_deleted < 0) {
J
Jeff Mahoney 已提交
1844 1845
			reiserfs_warning(p_s_inode->i_sb, "vs-5665",
					 "reiserfs_cut_from_item failed");
1846 1847 1848
			reiserfs_check_path(&s_search_path);
			return 0;
		}
L
Linus Torvalds 已提交
1849

1850 1851 1852
		RFALSE(n_deleted > n_file_size,
		       "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K",
		       n_deleted, n_file_size, &s_item_key);
L
Linus Torvalds 已提交
1853

1854 1855
		/* Change key to search the last file item. */
		n_file_size -= n_deleted;
L
Linus Torvalds 已提交
1856

1857
		set_cpu_key_k_offset(&s_item_key, n_file_size);
L
Linus Torvalds 已提交
1858

1859 1860 1861 1862 1863 1864 1865 1866 1867
		/* While there are bytes to truncate and previous file item is presented in the tree. */

		/*
		 ** This loop could take a really long time, and could log 
		 ** many more blocks than a transaction can hold.  So, we do a polite
		 ** journal end here, and if the transaction needs ending, we make
		 ** sure the file is consistent before ending the current trans
		 ** and starting a new one
		 */
1868 1869
		if (journal_transaction_should_end(th, 0) ||
		    reiserfs_transaction_free_space(th) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) {
1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882
			int orig_len_alloc = th->t_blocks_allocated;
			decrement_counters_in_path(&s_search_path);

			if (update_timestamps) {
				p_s_inode->i_mtime = p_s_inode->i_ctime =
				    CURRENT_TIME_SEC;
			}
			reiserfs_update_sd(th, p_s_inode);

			err = journal_end(th, p_s_inode->i_sb, orig_len_alloc);
			if (err)
				goto out;
			err = journal_begin(th, p_s_inode->i_sb,
1883
					    JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD + JOURNAL_PER_BALANCE_CNT * 4) ;
1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899
			if (err)
				goto out;
			reiserfs_update_inode_transaction(p_s_inode);
		}
	} while (n_file_size > ROUND_UP(n_new_file_size) &&
		 search_for_position_by_key(p_s_inode->i_sb, &s_item_key,
					    &s_search_path) == POSITION_FOUND);

	RFALSE(n_file_size > ROUND_UP(n_new_file_size),
	       "PAP-5680: truncate did not finish: new_file_size %Ld, current %Ld, oid %d",
	       n_new_file_size, n_file_size, s_item_key.on_disk_key.k_objectid);

      update_and_out:
	if (update_timestamps) {
		// this is truncate, not file closing
		p_s_inode->i_mtime = p_s_inode->i_ctime = CURRENT_TIME_SEC;
L
Linus Torvalds 已提交
1900
	}
1901
	reiserfs_update_sd(th, p_s_inode);
L
Linus Torvalds 已提交
1902

1903 1904 1905 1906
      out:
	pathrelse(&s_search_path);
	return err;
}
L
Linus Torvalds 已提交
1907 1908 1909

#ifdef CONFIG_REISERFS_CHECK
// this makes sure, that we __append__, not overwrite or add holes
1910
static void check_research_for_paste(struct treepath *path,
1911
				     const struct cpu_key *p_s_key)
L
Linus Torvalds 已提交
1912
{
1913 1914 1915 1916 1917 1918 1919 1920 1921 1922
	struct item_head *found_ih = get_ih(path);

	if (is_direct_le_ih(found_ih)) {
		if (le_ih_k_offset(found_ih) +
		    op_bytes_number(found_ih,
				    get_last_bh(path)->b_size) !=
		    cpu_key_k_offset(p_s_key)
		    || op_bytes_number(found_ih,
				       get_last_bh(path)->b_size) !=
		    pos_in_item(path))
J
Jeff Mahoney 已提交
1923 1924 1925 1926
			reiserfs_panic(NULL, "PAP-5720", "found direct item "
				       "%h or position (%d) does not match "
				       "to key %K", found_ih,
				       pos_in_item(path), p_s_key);
1927 1928 1929 1930 1931 1932 1933 1934
	}
	if (is_indirect_le_ih(found_ih)) {
		if (le_ih_k_offset(found_ih) +
		    op_bytes_number(found_ih,
				    get_last_bh(path)->b_size) !=
		    cpu_key_k_offset(p_s_key)
		    || I_UNFM_NUM(found_ih) != pos_in_item(path)
		    || get_ih_free_space(found_ih) != 0)
J
Jeff Mahoney 已提交
1935 1936 1937
			reiserfs_panic(NULL, "PAP-5730", "found indirect "
				       "item (%h) or position (%d) does not "
				       "match to key (%K)",
1938 1939
				       found_ih, pos_in_item(path), p_s_key);
	}
L
Linus Torvalds 已提交
1940
}
1941
#endif				/* config reiserfs check */
L
Linus Torvalds 已提交
1942 1943

/* Paste bytes to the existing item. Returns bytes number pasted into the item. */
1944
int reiserfs_paste_into_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_search_path,	/* Path to the pasted item.          */
1945 1946 1947 1948 1949 1950 1951 1952 1953 1954
			     const struct cpu_key *p_s_key,	/* Key to search for the needed item. */
			     struct inode *inode,	/* Inode item belongs to */
			     const char *p_c_body,	/* Pointer to the bytes to paste.    */
			     int n_pasted_size)
{				/* Size of pasted bytes.             */
	struct tree_balance s_paste_balance;
	int retval;
	int fs_gen;

	BUG_ON(!th->t_trans_id);
L
Linus Torvalds 已提交
1955

1956
	fs_gen = get_generation(inode->i_sb);
L
Linus Torvalds 已提交
1957 1958

#ifdef REISERQUOTA_DEBUG
1959 1960 1961 1962
	reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
		       "reiserquota paste_into_item(): allocating %u id=%u type=%c",
		       n_pasted_size, inode->i_uid,
		       key2type(&(p_s_key->on_disk_key)));
L
Linus Torvalds 已提交
1963 1964
#endif

1965 1966 1967 1968 1969 1970
	if (DQUOT_ALLOC_SPACE_NODIRTY(inode, n_pasted_size)) {
		pathrelse(p_s_search_path);
		return -EDQUOT;
	}
	init_tb_struct(th, &s_paste_balance, th->t_super, p_s_search_path,
		       n_pasted_size);
L
Linus Torvalds 已提交
1971
#ifdef DISPLACE_NEW_PACKING_LOCALITIES
1972
	s_paste_balance.key = p_s_key->on_disk_key;
L
Linus Torvalds 已提交
1973 1974
#endif

1975 1976 1977
	/* DQUOT_* can schedule, must check before the fix_nodes */
	if (fs_changed(fs_gen, inode->i_sb)) {
		goto search_again;
L
Linus Torvalds 已提交
1978
	}
1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993

	while ((retval =
		fix_nodes(M_PASTE, &s_paste_balance, NULL,
			  p_c_body)) == REPEAT_SEARCH) {
	      search_again:
		/* file system changed while we were in the fix_nodes */
		PROC_INFO_INC(th->t_super, paste_into_item_restarted);
		retval =
		    search_for_position_by_key(th->t_super, p_s_key,
					       p_s_search_path);
		if (retval == IO_ERROR) {
			retval = -EIO;
			goto error_out;
		}
		if (retval == POSITION_FOUND) {
J
Jeff Mahoney 已提交
1994 1995
			reiserfs_warning(inode->i_sb, "PAP-5710",
					 "entry or pasted byte (%K) exists",
1996 1997 1998 1999
					 p_s_key);
			retval = -EEXIST;
			goto error_out;
		}
L
Linus Torvalds 已提交
2000
#ifdef CONFIG_REISERFS_CHECK
2001
		check_research_for_paste(p_s_search_path, p_s_key);
L
Linus Torvalds 已提交
2002
#endif
2003
	}
L
Linus Torvalds 已提交
2004

2005 2006 2007 2008 2009 2010 2011 2012 2013 2014
	/* Perform balancing after all resources are collected by fix_nodes, and
	   accessing them will not risk triggering schedule. */
	if (retval == CARRY_ON) {
		do_balance(&s_paste_balance, NULL /*ih */ , p_c_body, M_PASTE);
		return 0;
	}
	retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
      error_out:
	/* this also releases the path */
	unfix_nodes(&s_paste_balance);
L
Linus Torvalds 已提交
2015
#ifdef REISERQUOTA_DEBUG
2016 2017 2018 2019
	reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
		       "reiserquota paste_into_item(): freeing %u id=%u type=%c",
		       n_pasted_size, inode->i_uid,
		       key2type(&(p_s_key->on_disk_key)));
L
Linus Torvalds 已提交
2020
#endif
2021 2022
	DQUOT_FREE_SPACE_NODIRTY(inode, n_pasted_size);
	return retval;
L
Linus Torvalds 已提交
2023 2024 2025
}

/* Insert new item into the buffer at the path. */
2026
int reiserfs_insert_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_path,	/* Path to the inserteded item.         */
2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046
			 const struct cpu_key *key, struct item_head *p_s_ih,	/* Pointer to the item header to insert. */
			 struct inode *inode, const char *p_c_body)
{				/* Pointer to the bytes to insert.      */
	struct tree_balance s_ins_balance;
	int retval;
	int fs_gen = 0;
	int quota_bytes = 0;

	BUG_ON(!th->t_trans_id);

	if (inode) {		/* Do we count quotas for item? */
		fs_gen = get_generation(inode->i_sb);
		quota_bytes = ih_item_len(p_s_ih);

		/* hack so the quota code doesn't have to guess if the file has
		 ** a tail, links are always tails, so there's no guessing needed
		 */
		if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(p_s_ih)) {
			quota_bytes = inode->i_sb->s_blocksize + UNFM_P_SIZE;
		}
L
Linus Torvalds 已提交
2047
#ifdef REISERQUOTA_DEBUG
2048 2049 2050
		reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
			       "reiserquota insert_item(): allocating %u id=%u type=%c",
			       quota_bytes, inode->i_uid, head2type(p_s_ih));
L
Linus Torvalds 已提交
2051
#endif
2052 2053 2054 2055 2056 2057
		/* We can't dirty inode here. It would be immediately written but
		 * appropriate stat item isn't inserted yet... */
		if (DQUOT_ALLOC_SPACE_NODIRTY(inode, quota_bytes)) {
			pathrelse(p_s_path);
			return -EDQUOT;
		}
L
Linus Torvalds 已提交
2058
	}
2059 2060
	init_tb_struct(th, &s_ins_balance, th->t_super, p_s_path,
		       IH_SIZE + ih_item_len(p_s_ih));
L
Linus Torvalds 已提交
2061
#ifdef DISPLACE_NEW_PACKING_LOCALITIES
2062
	s_ins_balance.key = key->on_disk_key;
L
Linus Torvalds 已提交
2063
#endif
2064 2065 2066
	/* DQUOT_* can schedule, must check to be sure calling fix_nodes is safe */
	if (inode && fs_changed(fs_gen, inode->i_sb)) {
		goto search_again;
L
Linus Torvalds 已提交
2067
	}
2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080

	while ((retval =
		fix_nodes(M_INSERT, &s_ins_balance, p_s_ih,
			  p_c_body)) == REPEAT_SEARCH) {
	      search_again:
		/* file system changed while we were in the fix_nodes */
		PROC_INFO_INC(th->t_super, insert_item_restarted);
		retval = search_item(th->t_super, key, p_s_path);
		if (retval == IO_ERROR) {
			retval = -EIO;
			goto error_out;
		}
		if (retval == ITEM_FOUND) {
J
Jeff Mahoney 已提交
2081
			reiserfs_warning(th->t_super, "PAP-5760",
2082 2083 2084 2085 2086
					 "key %K already exists in the tree",
					 key);
			retval = -EEXIST;
			goto error_out;
		}
L
Linus Torvalds 已提交
2087 2088
	}

2089 2090 2091 2092 2093
	/* make balancing after all resources will be collected at a time */
	if (retval == CARRY_ON) {
		do_balance(&s_ins_balance, p_s_ih, p_c_body, M_INSERT);
		return 0;
	}
L
Linus Torvalds 已提交
2094

2095 2096 2097 2098
	retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
      error_out:
	/* also releases the path */
	unfix_nodes(&s_ins_balance);
L
Linus Torvalds 已提交
2099
#ifdef REISERQUOTA_DEBUG
2100 2101 2102
	reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE,
		       "reiserquota insert_item(): freeing %u id=%u type=%c",
		       quota_bytes, inode->i_uid, head2type(p_s_ih));
L
Linus Torvalds 已提交
2103
#endif
2104 2105 2106
	if (inode)
		DQUOT_FREE_SPACE_NODIRTY(inode, quota_bytes);
	return retval;
L
Linus Torvalds 已提交
2107
}