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. */
  20inline 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 */
 
 
  30inline 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 */
  44inline 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 */
  68static 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(le_key_version(le_key), le_key) <
  77	    cpu_key_k_offset(cpu_key))
  78		return -1;
  79	if (le_key_k_offset(le_key_version(le_key), le_key) >
  80	    cpu_key_k_offset(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(le_key_version(le_key), le_key) <
  88	    cpu_key_k_type(cpu_key))
  89		return -1;
  90
  91	if (le_key_k_type(le_key_version(le_key), le_key) >
  92	    cpu_key_k_type(cpu_key))
  93		return 1;
  94
  95	return 0;
  96}
  97
  98inline 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
 115inline 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(from);
 123	to->version = version;
 124	to->on_disk_key.k_offset = le_key_k_offset(version, from);
 125	to->on_disk_key.k_type = le_key_k_type(version, 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 */
 132inline int comp_le_keys(const struct reiserfs_key *k1,
 133			const struct reiserfs_key *k2)
 134{
 135	return memcmp(k1, k2, 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 */
 154static 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			((struct reiserfs_key *)((char *)base + j * width),
 175			 (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. */
 197const struct reiserfs_key MIN_KEY = { 0, 0, {{0, 0},} };
 198
 199/* Maximal possible key. It is never in the tree. */
 200static 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 */
 215static 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		    (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(parent, 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. */
 262inline 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		    (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(parent, 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 */
 321static 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(get_lkey(chk_path, sb), 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(get_rkey(chk_path, sb), key) != 1)
 342		/* key must be less than right delimitiing key */
 343		return 0;
 344	return 1;
 345}
 346
 347int 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 */
 359void 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 */
 377void 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
 390static 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
 408static 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 */
 492static 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 */
 530static 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(bh->b_data, bh->b_size, bh);
 540
 541	return is_internal(bh->b_data, 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 */
 556static 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(s, 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[j])) {
 580			if (depth == -1)
 581				depth = reiserfs_write_unlock_nested(s);
 582			bh_readahead(bh[j], REQ_RAHEAD);
 583		}
 584		brelse(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 */
 615int 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_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(sb, reada_bh,
 683						    reada_blocks, reada_count);
 684
 685			if (!buffer_uptodate(bh) && depth == -1)
 686				depth = reiserfs_write_unlock_nested(sb);
 687
 688			bh_read_nowait(bh, 0);
 689			wait_on_buffer(bh);
 690
 691			if (depth != -1)
 692				reiserfs_write_lock_nested(sb, depth);
 693			if (!buffer_uptodate(bh))
 694				goto io_error;
 695		} else {
 696io_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(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("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, 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, item_head(bh, 0),
 771				      B_NR_ITEMS(bh),
 772				      (node_level ==
 773				       DISK_LEAF_NODE_LEVEL) ? IH_SIZE :
 774				      KEY_SIZE,
 775				      &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, 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! */
 854int 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, p_cpu_key, search_path,
 869					   &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			   --PATH_LAST_POSITION(search_path));
 896	blk_size = sb->s_blocksize;
 897
 898	if (comp_short_keys(&p_le_ih->ih_key, p_cpu_key))
 899		return FILE_NOT_FOUND;
 900
 901	/* FIXME: quite ugly this far */
 902
 903	item_offset = le_ih_k_offset(p_le_ih);
 904	offset = cpu_key_k_offset(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(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(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. */
 930int 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(stored_ih, ih, IH_SIZE);
 946}
 947
 948/* prepare for delete or cut of direct item */
 
 
 
 
 
 
 
 
 949static 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(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(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(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(le_ih)));
 987	return M_CUT;		/* Cut from this item. */
 988}
 989
 990static 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(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), 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 */
1034static 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(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(p_le_ih))
1067		return prepare_for_direntry_item(path, p_le_ih, inode,
1068						 new_file_length,
1069						 cut_size);
1070
1071	/* Direct item. */
1072	if (is_direct_le_ih(p_le_ih))
1073		return prepare_for_direct_item(path, 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(&s_ih, tp_item_head(path));
1099		pos = I_UNFM_NUM(&s_ih);
1100
1101		while (le_ih_k_offset (&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, &s_ih) + pos - 1;
1116		    block = get_block_num(unfm, 0);
1117
1118		    if (block != 0) {
1119			reiserfs_prepare_for_journal(sb, bh, 1);
1120			put_block_num(unfm, 0, 0);
1121			journal_mark_dirty(th, bh);
1122			reiserfs_free_block(th, inode, block, 1);
1123		    }
1124
1125		    reiserfs_cond_resched(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, item_key, 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 */
1164static 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(tb->tb_path);
1168
1169	if (is_statdata_le_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(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(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
1190static 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
1207void 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
1216char 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
1229char 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 */
1251int 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, &s_del_balance, sb, path,
1270		       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,
1280					      &del_size,
1281					      max_reiserfs_offset(inode));
1282
1283		RFALSE(mode != M_DELETE, "PAP-5320: mode must be M_DELETE");
1284
1285		copy_item_head(&s_ih, tp_item_head(path));
1286		s_del_balance.insert_size[0] = del_size;
1287
1288		ret_value = fix_nodes(M_DELETE, &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, item_key, 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(&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(q_ih)) {
1325		if ((le_ih_k_offset(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(un_bh->b_page);
1361		off = ((le_ih_k_offset(&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(&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(inode->i_sb);
1377	dquot_free_space_nodirty(inode, quota_cut_bytes);
1378	reiserfs_write_lock_nested(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 */
1402void 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(&cpu_key, 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(&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, th->t_super, &path,
1449				       -(IH_SIZE + item_len));
1450		}
1451		quota_cut_bytes = ih_item_len(tp_item_head(&path));
1452
1453		retval = fix_nodes(M_DELETE, &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, 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(sb);
1474				dquot_free_space_nodirty(inode,
1475							 quota_cut_bytes);
1476				reiserfs_write_lock_nested(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(&path);
1490}
1491
1492int 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, 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(th->t_super)->s_rs->s_inode_generation;
1511		le32_add_cpu(inode_generation, 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
1520static 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
1555static 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(&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(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 */
1595static 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(&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4);
1604	tail_key.key_length = 4;
1605
1606	tail_len =
1607	    (cpu_key_k_offset(&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(inode->i_sb, &tail_key, 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, &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(&tail_key,
1628				     cpu_key_k_offset(&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 */
1637int 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, &s_cut_balance, inode->i_sb, path,
1665		       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,
1682					      &cut_size, 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);
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(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(item_key, new_file_size + 1);
1721			if (search_for_position_by_key
1722			    (sb, item_key,
1723			     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(path);
1735			return 0;
1736		}
1737
1738		s_cut_balance.insert_size[0] = cut_size;
1739
1740		ret_value = fix_nodes(mode, &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, item_key, 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(&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(s_cut_balance.tb_path);
1792	if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(p_le_ih)) {
1793		if (mode == M_DELETE &&
1794		    (le_ih_k_offset(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(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(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(&s_cut_balance, NULL, NULL, 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, 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(sb);
1853	dquot_free_space_nodirty(inode, quota_cut_bytes);
1854	reiserfs_write_lock_nested(sb, depth);
1855	return ret_value;
1856}
1857
1858static 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 */
1877int 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(&s_item_key, inode, max_reiserfs_offset(inode),
1915		     TYPE_DIRECT, 3);
1916
1917	retval =
1918	    search_for_position_by_key(inode->i_sb, &s_item_key,
1919				       &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(&s_search_path);
1940	if (is_statdata_le_ih(p_le_ih))
1941		file_size = 0;
1942	else {
1943		loff_t offset = le_ih_k_offset(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(&s_item_key, file_size);
1967
1968	do {
1969		/* Cut or delete file item. */
1970		deleted =
1971		    reiserfs_cut_from_item(th, &s_search_path, &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(&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(&s_item_key, 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(&s_search_path);
2004
2005			if (update_timestamps) {
2006				inode_set_mtime_to_ts(inode,
2007						      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, 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(inode->i_sb, &s_item_key,
2023					    &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
2029update_and_out:
2030	if (update_timestamps) {
2031		/* this is truncate, not file closing */
2032		inode_set_mtime_to_ts(inode, current_time(inode));
2033		inode_set_ctime_current(inode);
2034	}
2035	reiserfs_update_sd(th, inode);
2036
2037out:
2038	pathrelse(&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 */
2044static 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(found_ih)) {
2050		if (le_ih_k_offset(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(found_ih)) {
2063		if (le_ih_k_offset(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 */
2081int 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(sb);
2111	retval = dquot_alloc_space_nodirty(inode, pasted_size);
2112	reiserfs_write_lock_nested(sb, depth);
2113	if (retval) {
2114		pathrelse(search_path);
2115		return retval;
2116	}
2117	init_tb_struct(th, &s_paste_balance, th->t_super, search_path,
2118		       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, &s_paste_balance, NULL,
2130			  body)) == REPEAT_SEARCH) {
2131search_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(th->t_super, 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(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(&s_paste_balance, NULL /*ih */ , body, M_PASTE);
2159		return 0;
2160	}
2161	retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
2162error_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(sb);
2172	dquot_free_space_nodirty(inode, pasted_size);
2173	reiserfs_write_lock_nested(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 */
2184int 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(inode->i_sb);
2218		retval = dquot_alloc_space_nodirty(inode, quota_bytes);
2219		reiserfs_write_lock_nested(inode->i_sb, depth);
2220		if (retval) {
2221			pathrelse(path);
2222			return retval;
2223		}
2224	}
2225	init_tb_struct(th, &s_ins_balance, 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, &s_ins_balance, ih,
2240			  body)) == REPEAT_SEARCH) {
2241search_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(&s_ins_balance, ih, body, M_INSERT);
2261		return 0;
2262	}
2263
2264	retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
2265error_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(inode->i_sb);
2276		dquot_free_space_nodirty(inode, quota_bytes);
2277		reiserfs_write_lock_nested(inode->i_sb, depth);
2278	}
2279	return retval;
2280}