1/*
   2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
   3 */
   4
   5/* Now we have all buffers that must be used in balancing of the tree 	*/
   6/* Further calculations can not cause schedule(), and thus the buffer 	*/
   7/* tree will be stable until the balancing will be finished 		*/
   8/* balance the tree according to the analysis made before,		*/
   9/* and using buffers obtained after all above.				*/
  10
  11/**
  12 ** balance_leaf_when_delete
  13 ** balance_leaf
  14 ** do_balance
  15 **
  16 **/
  17
  18#include <asm/uaccess.h>
  19#include <linux/time.h>
  20#include <linux/reiserfs_fs.h>
  21#include <linux/buffer_head.h>
  22#include <linux/kernel.h>
  23
  24static inline void buffer_info_init_left(struct tree_balance *tb,
  25                                         struct buffer_info *bi)
  26{
  27	bi->tb          = tb;
  28	bi->bi_bh       = tb->L[0];
  29	bi->bi_parent   = tb->FL[0];
  30	bi->bi_position = get_left_neighbor_position(tb, 0);
  31}
  32
  33static inline void buffer_info_init_right(struct tree_balance *tb,
  34                                          struct buffer_info *bi)
  35{
  36	bi->tb          = tb;
  37	bi->bi_bh       = tb->R[0];
  38	bi->bi_parent   = tb->FR[0];
  39	bi->bi_position = get_right_neighbor_position(tb, 0);
  40}
  41
  42static inline void buffer_info_init_tbS0(struct tree_balance *tb,
  43                                         struct buffer_info *bi)
  44{
  45	bi->tb          = tb;
  46	bi->bi_bh        = PATH_PLAST_BUFFER(tb->tb_path);
  47	bi->bi_parent   = PATH_H_PPARENT(tb->tb_path, 0);
  48	bi->bi_position = PATH_H_POSITION(tb->tb_path, 1);
  49}
  50
  51static inline void buffer_info_init_bh(struct tree_balance *tb,
  52                                       struct buffer_info *bi,
  53                                       struct buffer_head *bh)
  54{
  55	bi->tb          = tb;
  56	bi->bi_bh       = bh;
  57	bi->bi_parent   = NULL;
  58	bi->bi_position = 0;
  59}
  60
  61inline void do_balance_mark_leaf_dirty(struct tree_balance *tb,
  62				       struct buffer_head *bh, int flag)
  63{
  64	journal_mark_dirty(tb->transaction_handle,
  65			   tb->transaction_handle->t_super, bh);
  66}
  67
  68#define do_balance_mark_internal_dirty do_balance_mark_leaf_dirty
  69#define do_balance_mark_sb_dirty do_balance_mark_leaf_dirty
  70
  71/* summary:
  72 if deleting something ( tb->insert_size[0] < 0 )
  73   return(balance_leaf_when_delete()); (flag d handled here)
  74 else
  75   if lnum is larger than 0 we put items into the left node
  76   if rnum is larger than 0 we put items into the right node
  77   if snum1 is larger than 0 we put items into the new node s1
  78   if snum2 is larger than 0 we put items into the new node s2
  79Note that all *num* count new items being created.
  80
  81It would be easier to read balance_leaf() if each of these summary
  82lines was a separate procedure rather than being inlined.  I think
  83that there are many passages here and in balance_leaf_when_delete() in
  84which two calls to one procedure can replace two passages, and it
  85might save cache space and improve software maintenance costs to do so.
  86
  87Vladimir made the perceptive comment that we should offload most of
  88the decision making in this function into fix_nodes/check_balance, and
  89then create some sort of structure in tb that says what actions should
  90be performed by do_balance.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  91
  92-Hans */
 
  93
  94/* Balance leaf node in case of delete or cut: insert_size[0] < 0
 
  95 *
  96 * lnum, rnum can have values >= -1
  97 *	-1 means that the neighbor must be joined with S
  98 *	 0 means that nothing should be done with the neighbor
  99 *	>0 means to shift entirely or partly the specified number of items to the neighbor
 
 100 */
 101static int balance_leaf_when_delete(struct tree_balance *tb, int flag)
 102{
 103	struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
 104	int item_pos = PATH_LAST_POSITION(tb->tb_path);
 105	int pos_in_item = tb->tb_path->pos_in_item;
 106	struct buffer_info bi;
 107	int n;
 108	struct item_head *ih;
 109
 110	RFALSE(tb->FR[0] && B_LEVEL(tb->FR[0]) != DISK_LEAF_NODE_LEVEL + 1,
 111	       "vs- 12000: level: wrong FR %z", tb->FR[0]);
 112	RFALSE(tb->blknum[0] > 1,
 113	       "PAP-12005: tb->blknum == %d, can not be > 1", tb->blknum[0]);
 114	RFALSE(!tb->blknum[0] && !PATH_H_PPARENT(tb->tb_path, 0),
 115	       "PAP-12010: tree can not be empty");
 116
 117	ih = B_N_PITEM_HEAD(tbS0, item_pos);
 118	buffer_info_init_tbS0(tb, &bi);
 119
 120	/* Delete or truncate the item */
 121
 122	switch (flag) {
 123	case M_DELETE:		/* delete item in S[0] */
 
 
 
 124
 125		RFALSE(ih_item_len(ih) + IH_SIZE != -tb->insert_size[0],
 126		       "vs-12013: mode Delete, insert size %d, ih to be deleted %h",
 127		       -tb->insert_size[0], ih);
 128
 129		leaf_delete_items(&bi, 0, item_pos, 1, -1);
 130
 131		if (!item_pos && tb->CFL[0]) {
 132			if (B_NR_ITEMS(tbS0)) {
 133				replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0,
 134					    0);
 135			} else {
 136				if (!PATH_H_POSITION(tb->tb_path, 1))
 137					replace_key(tb, tb->CFL[0], tb->lkey[0],
 138						    PATH_H_PPARENT(tb->tb_path,
 139								   0), 0);
 140			}
 141		}
 142
 143		RFALSE(!item_pos && !tb->CFL[0],
 144		       "PAP-12020: tb->CFL[0]==%p, tb->L[0]==%p", tb->CFL[0],
 145		       tb->L[0]);
 146
 147		break;
 148
 149	case M_CUT:{		/* cut item in S[0] */
 150			if (is_direntry_le_ih(ih)) {
 151
 152				/* UFS unlink semantics are such that you can only delete one directory entry at a time. */
 153				/* when we cut a directory tb->insert_size[0] means number of entries to be cut (always 1) */
 154				tb->insert_size[0] = -1;
 155				leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
 156						     -tb->insert_size[0]);
 157
 158				RFALSE(!item_pos && !pos_in_item && !tb->CFL[0],
 159				       "PAP-12030: can not change delimiting key. CFL[0]=%p",
 160				       tb->CFL[0]);
 161
 162				if (!item_pos && !pos_in_item && tb->CFL[0]) {
 163					replace_key(tb, tb->CFL[0], tb->lkey[0],
 164						    tbS0, 0);
 165				}
 166			} else {
 167				leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
 168						     -tb->insert_size[0]);
 169
 170				RFALSE(!ih_item_len(ih),
 171				       "PAP-12035: cut must leave non-zero dynamic length of item");
 172			}
 173			break;
 174		}
 175
 176	default:
 177		print_cur_tb("12040");
 178		reiserfs_panic(tb->tb_sb, "PAP-12040",
 179			       "unexpected mode: %s(%d)",
 180			       (flag ==
 181				M_PASTE) ? "PASTE" : ((flag ==
 182						       M_INSERT) ? "INSERT" :
 183						      "UNKNOWN"), flag);
 
 184	}
 185
 186	/* the rule is that no shifting occurs unless by shifting a node can be freed */
 187	n = B_NR_ITEMS(tbS0);
 188	if (tb->lnum[0]) {	/* L[0] takes part in balancing */
 189		if (tb->lnum[0] == -1) {	/* L[0] must be joined with S[0] */
 190			if (tb->rnum[0] == -1) {	/* R[0] must be also joined with S[0] */
 191				if (tb->FR[0] == PATH_H_PPARENT(tb->tb_path, 0)) {
 192					/* all contents of all the 3 buffers will be in L[0] */
 193					if (PATH_H_POSITION(tb->tb_path, 1) == 0
 194					    && 1 < B_NR_ITEMS(tb->FR[0]))
 195						replace_key(tb, tb->CFL[0],
 196							    tb->lkey[0],
 197							    tb->FR[0], 1);
 198
 199					leaf_move_items(LEAF_FROM_S_TO_L, tb, n,
 200							-1, NULL);
 201					leaf_move_items(LEAF_FROM_R_TO_L, tb,
 202							B_NR_ITEMS(tb->R[0]),
 203							-1, NULL);
 204
 205					reiserfs_invalidate_buffer(tb, tbS0);
 206					reiserfs_invalidate_buffer(tb,
 207								   tb->R[0]);
 208
 209					return 0;
 210				}
 211				/* all contents of all the 3 buffers will be in R[0] */
 212				leaf_move_items(LEAF_FROM_S_TO_R, tb, n, -1,
 213						NULL);
 214				leaf_move_items(LEAF_FROM_L_TO_R, tb,
 215						B_NR_ITEMS(tb->L[0]), -1, NULL);
 216
 217				/* right_delimiting_key is correct in R[0] */
 218				replace_key(tb, tb->CFR[0], tb->rkey[0],
 219					    tb->R[0], 0);
 
 
 
 
 
 220
 221				reiserfs_invalidate_buffer(tb, tbS0);
 222				reiserfs_invalidate_buffer(tb, tb->L[0]);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 223
 224				return -1;
 225			}
 226
 227			RFALSE(tb->rnum[0] != 0,
 228			       "PAP-12045: rnum must be 0 (%d)", tb->rnum[0]);
 229			/* all contents of L[0] and S[0] will be in L[0] */
 230			leaf_shift_left(tb, n, -1);
 
 
 
 
 
 
 
 
 
 
 
 
 231
 232			reiserfs_invalidate_buffer(tb, tbS0);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 233
 234			return 0;
 235		}
 236		/* a part of contents of S[0] will be in L[0] and the rest part of S[0] will be in R[0] */
 237
 238		RFALSE((tb->lnum[0] + tb->rnum[0] < n) ||
 239		       (tb->lnum[0] + tb->rnum[0] > n + 1),
 240		       "PAP-12050: rnum(%d) and lnum(%d) and item number(%d) in S[0] are not consistent",
 241		       tb->rnum[0], tb->lnum[0], n);
 242		RFALSE((tb->lnum[0] + tb->rnum[0] == n) &&
 243		       (tb->lbytes != -1 || tb->rbytes != -1),
 244		       "PAP-12055: bad rbytes (%d)/lbytes (%d) parameters when items are not split",
 245		       tb->rbytes, tb->lbytes);
 246		RFALSE((tb->lnum[0] + tb->rnum[0] == n + 1) &&
 247		       (tb->lbytes < 1 || tb->rbytes != -1),
 248		       "PAP-12060: bad rbytes (%d)/lbytes (%d) parameters when items are split",
 249		       tb->rbytes, tb->lbytes);
 
 250
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 251		leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
 252		leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
 
 
 253
 254		reiserfs_invalidate_buffer(tb, tbS0);
 255
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 256		return 0;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 257	}
 258
 259	if (tb->rnum[0] == -1) {
 260		/* all contents of R[0] and S[0] will be in R[0] */
 261		leaf_shift_right(tb, n, -1);
 262		reiserfs_invalidate_buffer(tb, tbS0);
 263		return 0;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 264	}
 
 265
 266	RFALSE(tb->rnum[0],
 267	       "PAP-12065: bad rnum parameter must be 0 (%d)", tb->rnum[0]);
 268	return 0;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 269}
 270
 271static int balance_leaf(struct tree_balance *tb, struct item_head *ih,	/* item header of inserted item (this is on little endian) */
 272			const char *body,	/* body  of inserted item or bytes to paste */
 273			int flag,	/* i - insert, d - delete, c - cut, p - paste
 274					   (see comment to do_balance) */
 275			struct item_head *insert_key,	/* in our processing of one level we sometimes determine what
 276							   must be inserted into the next higher level.  This insertion
 277							   consists of a key or two keys and their corresponding
 278							   pointers */
 279			struct buffer_head **insert_ptr	/* inserted node-ptrs for the next level */
 280    )
 281{
 282	struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
 283	int item_pos = PATH_LAST_POSITION(tb->tb_path);	/*  index into the array of item headers in S[0]
 284							   of the affected item */
 
 285	struct buffer_info bi;
 286	struct buffer_head *S_new[2];	/* new nodes allocated to hold what could not fit into S */
 287	int snum[2];		/* number of items that will be placed
 288				   into S_new (includes partially shifted
 289				   items) */
 290	int sbytes[2];		/* if an item is partially shifted into S_new then
 291				   if it is a directory item
 292				   it is the number of entries from the item that are shifted into S_new
 293				   else
 294				   it is the number of bytes from the item that are shifted into S_new
 295				 */
 296	int n, i;
 297	int ret_val;
 298	int pos_in_item;
 299	int zeros_num;
 300
 301	PROC_INFO_INC(tb->tb_sb, balance_at[0]);
 
 
 
 
 302
 303	/* Make balance in case insert_size[0] < 0 */
 304	if (tb->insert_size[0] < 0)
 305		return balance_leaf_when_delete(tb, flag);
 306
 307	zeros_num = 0;
 308	if (flag == M_INSERT && !body)
 309		zeros_num = ih_item_len(ih);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 310
 311	pos_in_item = tb->tb_path->pos_in_item;
 312	/* for indirect item pos_in_item is measured in unformatted node
 313	   pointers. Recalculate to bytes */
 314	if (flag != M_INSERT
 315	    && is_indirect_le_ih(B_N_PITEM_HEAD(tbS0, item_pos)))
 316		pos_in_item *= UNFM_P_SIZE;
 317
 318	if (tb->lnum[0] > 0) {
 319		/* Shift lnum[0] items from S[0] to the left neighbor L[0] */
 320		if (item_pos < tb->lnum[0]) {
 321			/* new item or it part falls to L[0], shift it too */
 322			n = B_NR_ITEMS(tb->L[0]);
 323
 324			switch (flag) {
 325			case M_INSERT:	/* insert item into L[0] */
 326
 327				if (item_pos == tb->lnum[0] - 1
 328				    && tb->lbytes != -1) {
 329					/* part of new item falls into L[0] */
 330					int new_item_len;
 331					int version;
 332
 333					ret_val =
 334					    leaf_shift_left(tb, tb->lnum[0] - 1,
 335							    -1);
 336
 337					/* Calculate item length to insert to S[0] */
 338					new_item_len =
 339					    ih_item_len(ih) - tb->lbytes;
 340					/* Calculate and check item length to insert to L[0] */
 341					put_ih_item_len(ih,
 342							ih_item_len(ih) -
 343							new_item_len);
 344
 345					RFALSE(ih_item_len(ih) <= 0,
 346					       "PAP-12080: there is nothing to insert into L[0]: ih_item_len=%d",
 347					       ih_item_len(ih));
 348
 349					/* Insert new item into L[0] */
 350					buffer_info_init_left(tb, &bi);
 351					leaf_insert_into_buf(&bi,
 352							     n + item_pos -
 353							     ret_val, ih, body,
 354							     zeros_num >
 355							     ih_item_len(ih) ?
 356							     ih_item_len(ih) :
 357							     zeros_num);
 358
 359					version = ih_version(ih);
 360
 361					/* Calculate key component, item length and body to insert into S[0] */
 362					set_le_ih_k_offset(ih,
 363							   le_ih_k_offset(ih) +
 364							   (tb->
 365							    lbytes <<
 366							    (is_indirect_le_ih
 367							     (ih) ? tb->tb_sb->
 368							     s_blocksize_bits -
 369							     UNFM_P_SHIFT :
 370							     0)));
 371
 372					put_ih_item_len(ih, new_item_len);
 373					if (tb->lbytes > zeros_num) {
 374						body +=
 375						    (tb->lbytes - zeros_num);
 376						zeros_num = 0;
 377					} else
 378						zeros_num -= tb->lbytes;
 379
 380					RFALSE(ih_item_len(ih) <= 0,
 381					       "PAP-12085: there is nothing to insert into S[0]: ih_item_len=%d",
 382					       ih_item_len(ih));
 383				} else {
 384					/* new item in whole falls into L[0] */
 385					/* Shift lnum[0]-1 items to L[0] */
 386					ret_val =
 387					    leaf_shift_left(tb, tb->lnum[0] - 1,
 388							    tb->lbytes);
 389					/* Insert new item into L[0] */
 390					buffer_info_init_left(tb, &bi);
 391					leaf_insert_into_buf(&bi,
 392							     n + item_pos -
 393							     ret_val, ih, body,
 394							     zeros_num);
 395					tb->insert_size[0] = 0;
 396					zeros_num = 0;
 397				}
 398				break;
 399
 400			case M_PASTE:	/* append item in L[0] */
 401
 402				if (item_pos == tb->lnum[0] - 1
 403				    && tb->lbytes != -1) {
 404					/* we must shift the part of the appended item */
 405					if (is_direntry_le_ih
 406					    (B_N_PITEM_HEAD(tbS0, item_pos))) {
 407
 408						RFALSE(zeros_num,
 409						       "PAP-12090: invalid parameter in case of a directory");
 410						/* directory item */
 411						if (tb->lbytes > pos_in_item) {
 412							/* new directory entry falls into L[0] */
 413							struct item_head
 414							    *pasted;
 415							int l_pos_in_item =
 416							    pos_in_item;
 417
 418							/* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 entries from given directory item */
 419							ret_val =
 420							    leaf_shift_left(tb,
 421									    tb->
 422									    lnum
 423									    [0],
 424									    tb->
 425									    lbytes
 426									    -
 427									    1);
 428							if (ret_val
 429							    && !item_pos) {
 430								pasted =
 431								    B_N_PITEM_HEAD
 432								    (tb->L[0],
 433								     B_NR_ITEMS
 434								     (tb->
 435								      L[0]) -
 436								     1);
 437								l_pos_in_item +=
 438								    I_ENTRY_COUNT
 439								    (pasted) -
 440								    (tb->
 441								     lbytes -
 442								     1);
 443							}
 444
 445							/* Append given directory entry to directory item */
 446							buffer_info_init_left(tb, &bi);
 447							leaf_paste_in_buffer
 448							    (&bi,
 449							     n + item_pos -
 450							     ret_val,
 451							     l_pos_in_item,
 452							     tb->insert_size[0],
 453							     body, zeros_num);
 454
 455							/* previous string prepared space for pasting new entry, following string pastes this entry */
 456
 457							/* when we have merge directory item, pos_in_item has been changed too */
 458
 459							/* paste new directory entry. 1 is entry number */
 460							leaf_paste_entries(&bi,
 461									   n +
 462									   item_pos
 463									   -
 464									   ret_val,
 465									   l_pos_in_item,
 466									   1,
 467									   (struct
 468									    reiserfs_de_head
 469									    *)
 470									   body,
 471									   body
 472									   +
 473									   DEH_SIZE,
 474									   tb->
 475									   insert_size
 476									   [0]
 477							    );
 478							tb->insert_size[0] = 0;
 479						} else {
 480							/* new directory item doesn't fall into L[0] */
 481							/* Shift lnum[0]-1 items in whole. Shift lbytes directory entries from directory item number lnum[0] */
 482							leaf_shift_left(tb,
 483									tb->
 484									lnum[0],
 485									tb->
 486									lbytes);
 487						}
 488						/* Calculate new position to append in item body */
 489						pos_in_item -= tb->lbytes;
 490					} else {
 491						/* regular object */
 492						RFALSE(tb->lbytes <= 0,
 493						       "PAP-12095: there is nothing to shift to L[0]. lbytes=%d",
 494						       tb->lbytes);
 495						RFALSE(pos_in_item !=
 496						       ih_item_len
 497						       (B_N_PITEM_HEAD
 498							(tbS0, item_pos)),
 499						       "PAP-12100: incorrect position to paste: item_len=%d, pos_in_item=%d",
 500						       ih_item_len
 501						       (B_N_PITEM_HEAD
 502							(tbS0, item_pos)),
 503						       pos_in_item);
 504
 505						if (tb->lbytes >= pos_in_item) {
 506							/* appended item will be in L[0] in whole */
 507							int l_n;
 508
 509							/* this bytes number must be appended to the last item of L[h] */
 510							l_n =
 511							    tb->lbytes -
 512							    pos_in_item;
 513
 514							/* Calculate new insert_size[0] */
 515							tb->insert_size[0] -=
 516							    l_n;
 517
 518							RFALSE(tb->
 519							       insert_size[0] <=
 520							       0,
 521							       "PAP-12105: there is nothing to paste into L[0]. insert_size=%d",
 522							       tb->
 523							       insert_size[0]);
 524							ret_val =
 525							    leaf_shift_left(tb,
 526									    tb->
 527									    lnum
 528									    [0],
 529									    ih_item_len
 530									    (B_N_PITEM_HEAD
 531									     (tbS0,
 532									      item_pos)));
 533							/* Append to body of item in L[0] */
 534							buffer_info_init_left(tb, &bi);
 535							leaf_paste_in_buffer
 536							    (&bi,
 537							     n + item_pos -
 538							     ret_val,
 539							     ih_item_len
 540							     (B_N_PITEM_HEAD
 541							      (tb->L[0],
 542							       n + item_pos -
 543							       ret_val)), l_n,
 544							     body,
 545							     zeros_num >
 546							     l_n ? l_n :
 547							     zeros_num);
 548							/* 0-th item in S0 can be only of DIRECT type when l_n != 0 */
 549							{
 550								int version;
 551								int temp_l =
 552								    l_n;
 553
 554								RFALSE
 555								    (ih_item_len
 556								     (B_N_PITEM_HEAD
 557								      (tbS0,
 558								       0)),
 559								     "PAP-12106: item length must be 0");
 560								RFALSE
 561								    (comp_short_le_keys
 562								     (B_N_PKEY
 563								      (tbS0, 0),
 564								      B_N_PKEY
 565								      (tb->L[0],
 566								       n +
 567								       item_pos
 568								       -
 569								       ret_val)),
 570								     "PAP-12107: items must be of the same file");
 571								if (is_indirect_le_ih(B_N_PITEM_HEAD(tb->L[0], n + item_pos - ret_val))) {
 572									temp_l =
 573									    l_n
 574									    <<
 575									    (tb->
 576									     tb_sb->
 577									     s_blocksize_bits
 578									     -
 579									     UNFM_P_SHIFT);
 580								}
 581								/* update key of first item in S0 */
 582								version =
 583								    ih_version
 584								    (B_N_PITEM_HEAD
 585								     (tbS0, 0));
 586								set_le_key_k_offset
 587								    (version,
 588								     B_N_PKEY
 589								     (tbS0, 0),
 590								     le_key_k_offset
 591								     (version,
 592								      B_N_PKEY
 593								      (tbS0,
 594								       0)) +
 595								     temp_l);
 596								/* update left delimiting key */
 597								set_le_key_k_offset
 598								    (version,
 599								     B_N_PDELIM_KEY
 600								     (tb->
 601								      CFL[0],
 602								      tb->
 603								      lkey[0]),
 604								     le_key_k_offset
 605								     (version,
 606								      B_N_PDELIM_KEY
 607								      (tb->
 608								       CFL[0],
 609								       tb->
 610								       lkey[0]))
 611								     + temp_l);
 612							}
 613
 614							/* Calculate new body, position in item and insert_size[0] */
 615							if (l_n > zeros_num) {
 616								body +=
 617								    (l_n -
 618								     zeros_num);
 619								zeros_num = 0;
 620							} else
 621								zeros_num -=
 622								    l_n;
 623							pos_in_item = 0;
 624
 625							RFALSE
 626							    (comp_short_le_keys
 627							     (B_N_PKEY(tbS0, 0),
 628							      B_N_PKEY(tb->L[0],
 629								       B_NR_ITEMS
 630								       (tb->
 631									L[0]) -
 632								       1))
 633							     ||
 634							     !op_is_left_mergeable
 635							     (B_N_PKEY(tbS0, 0),
 636							      tbS0->b_size)
 637							     ||
 638							     !op_is_left_mergeable
 639							     (B_N_PDELIM_KEY
 640							      (tb->CFL[0],
 641							       tb->lkey[0]),
 642							      tbS0->b_size),
 643							     "PAP-12120: item must be merge-able with left neighboring item");
 644						} else {	/* only part of the appended item will be in L[0] */
 645
 646							/* Calculate position in item for append in S[0] */
 647							pos_in_item -=
 648							    tb->lbytes;
 649
 650							RFALSE(pos_in_item <= 0,
 651							       "PAP-12125: no place for paste. pos_in_item=%d",
 652							       pos_in_item);
 653
 654							/* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
 655							leaf_shift_left(tb,
 656									tb->
 657									lnum[0],
 658									tb->
 659									lbytes);
 660						}
 661					}
 662				} else {	/* appended item will be in L[0] in whole */
 663
 664					struct item_head *pasted;
 665
 666					if (!item_pos && op_is_left_mergeable(B_N_PKEY(tbS0, 0), tbS0->b_size)) {	/* if we paste into first item of S[0] and it is left mergable */
 667						/* then increment pos_in_item by the size of the last item in L[0] */
 668						pasted =
 669						    B_N_PITEM_HEAD(tb->L[0],
 670								   n - 1);
 671						if (is_direntry_le_ih(pasted))
 672							pos_in_item +=
 673							    ih_entry_count
 674							    (pasted);
 675						else
 676							pos_in_item +=
 677							    ih_item_len(pasted);
 678					}
 679
 680					/* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
 681					ret_val =
 682					    leaf_shift_left(tb, tb->lnum[0],
 683							    tb->lbytes);
 684					/* Append to body of item in L[0] */
 685					buffer_info_init_left(tb, &bi);
 686					leaf_paste_in_buffer(&bi,
 687							     n + item_pos -
 688							     ret_val,
 689							     pos_in_item,
 690							     tb->insert_size[0],
 691							     body, zeros_num);
 692
 693					/* if appended item is directory, paste entry */
 694					pasted =
 695					    B_N_PITEM_HEAD(tb->L[0],
 696							   n + item_pos -
 697							   ret_val);
 698					if (is_direntry_le_ih(pasted))
 699						leaf_paste_entries(&bi,
 700								   n +
 701								   item_pos -
 702								   ret_val,
 703								   pos_in_item,
 704								   1,
 705								   (struct
 706								    reiserfs_de_head
 707								    *)body,
 708								   body +
 709								   DEH_SIZE,
 710								   tb->
 711								   insert_size
 712								   [0]
 713						    );
 714					/* if appended item is indirect item, put unformatted node into un list */
 715					if (is_indirect_le_ih(pasted))
 716						set_ih_free_space(pasted, 0);
 717					tb->insert_size[0] = 0;
 718					zeros_num = 0;
 719				}
 720				break;
 721			default:	/* cases d and t */
 722				reiserfs_panic(tb->tb_sb, "PAP-12130",
 723					       "lnum > 0: unexpected mode: "
 724					       " %s(%d)",
 725					       (flag ==
 726						M_DELETE) ? "DELETE" : ((flag ==
 727									 M_CUT)
 728									? "CUT"
 729									:
 730									"UNKNOWN"),
 731					       flag);
 732			}
 733		} else {
 734			/* new item doesn't fall into L[0] */
 735			leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
 736		}
 737	}
 738
 739	/* tb->lnum[0] > 0 */
 740	/* Calculate new item position */
 741	item_pos -= (tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0));
 742
 743	if (tb->rnum[0] > 0) {
 744		/* shift rnum[0] items from S[0] to the right neighbor R[0] */
 745		n = B_NR_ITEMS(tbS0);
 746		switch (flag) {
 747
 748		case M_INSERT:	/* insert item */
 749			if (n - tb->rnum[0] < item_pos) {	/* new item or its part falls to R[0] */
 750				if (item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1) {	/* part of new item falls into R[0] */
 751					loff_t old_key_comp, old_len,
 752					    r_zeros_number;
 753					const char *r_body;
 754					int version;
 755					loff_t offset;
 756
 757					leaf_shift_right(tb, tb->rnum[0] - 1,
 758							 -1);
 759
 760					version = ih_version(ih);
 761					/* Remember key component and item length */
 762					old_key_comp = le_ih_k_offset(ih);
 763					old_len = ih_item_len(ih);
 764
 765					/* Calculate key component and item length to insert into R[0] */
 766					offset =
 767					    le_ih_k_offset(ih) +
 768					    ((old_len -
 769					      tb->
 770					      rbytes) << (is_indirect_le_ih(ih)
 771							  ? tb->tb_sb->
 772							  s_blocksize_bits -
 773							  UNFM_P_SHIFT : 0));
 774					set_le_ih_k_offset(ih, offset);
 775					put_ih_item_len(ih, tb->rbytes);
 776					/* Insert part of the item into R[0] */
 777					buffer_info_init_right(tb, &bi);
 778					if ((old_len - tb->rbytes) > zeros_num) {
 779						r_zeros_number = 0;
 780						r_body =
 781						    body + (old_len -
 782							    tb->rbytes) -
 783						    zeros_num;
 784					} else {
 785						r_body = body;
 786						r_zeros_number =
 787						    zeros_num - (old_len -
 788								 tb->rbytes);
 789						zeros_num -= r_zeros_number;
 790					}
 791
 792					leaf_insert_into_buf(&bi, 0, ih, r_body,
 793							     r_zeros_number);
 794
 795					/* Replace right delimiting key by first key in R[0] */
 796					replace_key(tb, tb->CFR[0], tb->rkey[0],
 797						    tb->R[0], 0);
 798
 799					/* Calculate key component and item length to insert into S[0] */
 800					set_le_ih_k_offset(ih, old_key_comp);
 801					put_ih_item_len(ih,
 802							old_len - tb->rbytes);
 803
 804					tb->insert_size[0] -= tb->rbytes;
 805
 806				} else {	/* whole new item falls into R[0] */
 807
 808					/* Shift rnum[0]-1 items to R[0] */
 809					ret_val =
 810					    leaf_shift_right(tb,
 811							     tb->rnum[0] - 1,
 812							     tb->rbytes);
 813					/* Insert new item into R[0] */
 814					buffer_info_init_right(tb, &bi);
 815					leaf_insert_into_buf(&bi,
 816							     item_pos - n +
 817							     tb->rnum[0] - 1,
 818							     ih, body,
 819							     zeros_num);
 820
 821					if (item_pos - n + tb->rnum[0] - 1 == 0) {
 822						replace_key(tb, tb->CFR[0],
 823							    tb->rkey[0],
 824							    tb->R[0], 0);
 825
 826					}
 827					zeros_num = tb->insert_size[0] = 0;
 828				}
 829			} else {	/* new item or part of it doesn't fall into R[0] */
 830
 831				leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
 832			}
 833			break;
 
 
 
 
 
 
 
 
 
 
 834
 835		case M_PASTE:	/* append item */
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 836
 837			if (n - tb->rnum[0] <= item_pos) {	/* pasted item or part of it falls to R[0] */
 838				if (item_pos == n - tb->rnum[0] && tb->rbytes != -1) {	/* we must shift the part of the appended item */
 839					if (is_direntry_le_ih(B_N_PITEM_HEAD(tbS0, item_pos))) {	/* we append to directory item */
 840						int entry_count;
 841
 842						RFALSE(zeros_num,
 843						       "PAP-12145: invalid parameter in case of a directory");
 844						entry_count =
 845						    I_ENTRY_COUNT(B_N_PITEM_HEAD
 846								  (tbS0,
 847								   item_pos));
 848						if (entry_count - tb->rbytes <
 849						    pos_in_item)
 850							/* new directory entry falls into R[0] */
 851						{
 852							int paste_entry_position;
 853
 854							RFALSE(tb->rbytes - 1 >=
 855							       entry_count
 856							       || !tb->
 857							       insert_size[0],
 858							       "PAP-12150: no enough of entries to shift to R[0]: rbytes=%d, entry_count=%d",
 859							       tb->rbytes,
 860							       entry_count);
 861							/* Shift rnum[0]-1 items in whole. Shift rbytes-1 directory entries from directory item number rnum[0] */
 862							leaf_shift_right(tb,
 863									 tb->
 864									 rnum
 865									 [0],
 866									 tb->
 867									 rbytes
 868									 - 1);
 869							/* Paste given directory entry to directory item */
 870							paste_entry_position =
 871							    pos_in_item -
 872							    entry_count +
 873							    tb->rbytes - 1;
 874							buffer_info_init_right(tb, &bi);
 875							leaf_paste_in_buffer
 876							    (&bi, 0,
 877							     paste_entry_position,
 878							     tb->insert_size[0],
 879							     body, zeros_num);
 880							/* paste entry */
 881							leaf_paste_entries(&bi,
 882									   0,
 883									   paste_entry_position,
 884									   1,
 885									   (struct
 886									    reiserfs_de_head
 887									    *)
 888									   body,
 889									   body
 890									   +
 891									   DEH_SIZE,
 892									   tb->
 893									   insert_size
 894									   [0]
 895							    );
 896
 897							if (paste_entry_position
 898							    == 0) {
 899								/* change delimiting keys */
 900								replace_key(tb,
 901									    tb->
 902									    CFR
 903									    [0],
 904									    tb->
 905									    rkey
 906									    [0],
 907									    tb->
 908									    R
 909									    [0],
 910									    0);
 911							}
 912
 913							tb->insert_size[0] = 0;
 914							pos_in_item++;
 915						} else {	/* new directory entry doesn't fall into R[0] */
 916
 917							leaf_shift_right(tb,
 918									 tb->
 919									 rnum
 920									 [0],
 921									 tb->
 922									 rbytes);
 923						}
 924					} else {	/* regular object */
 925
 926						int n_shift, n_rem,
 927						    r_zeros_number;
 928						const char *r_body;
 929
 930						/* Calculate number of bytes which must be shifted from appended item */
 931						if ((n_shift =
 932						     tb->rbytes -
 933						     tb->insert_size[0]) < 0)
 934							n_shift = 0;
 935
 936						RFALSE(pos_in_item !=
 937						       ih_item_len
 938						       (B_N_PITEM_HEAD
 939							(tbS0, item_pos)),
 940						       "PAP-12155: invalid position to paste. ih_item_len=%d, pos_in_item=%d",
 941						       pos_in_item,
 942						       ih_item_len
 943						       (B_N_PITEM_HEAD
 944							(tbS0, item_pos)));
 945
 946						leaf_shift_right(tb,
 947								 tb->rnum[0],
 948								 n_shift);
 949						/* Calculate number of bytes which must remain in body after appending to R[0] */
 950						if ((n_rem =
 951						     tb->insert_size[0] -
 952						     tb->rbytes) < 0)
 953							n_rem = 0;
 954
 955						{
 956							int version;
 957							unsigned long temp_rem =
 958							    n_rem;
 959
 960							version =
 961							    ih_version
 962							    (B_N_PITEM_HEAD
 963							     (tb->R[0], 0));
 964							if (is_indirect_le_key
 965							    (version,
 966							     B_N_PKEY(tb->R[0],
 967								      0))) {
 968								temp_rem =
 969								    n_rem <<
 970								    (tb->tb_sb->
 971								     s_blocksize_bits
 972								     -
 973								     UNFM_P_SHIFT);
 974							}
 975							set_le_key_k_offset
 976							    (version,
 977							     B_N_PKEY(tb->R[0],
 978								      0),
 979							     le_key_k_offset
 980							     (version,
 981							      B_N_PKEY(tb->R[0],
 982								       0)) +
 983							     temp_rem);
 984							set_le_key_k_offset
 985							    (version,
 986							     B_N_PDELIM_KEY(tb->
 987									    CFR
 988									    [0],
 989									    tb->
 990									    rkey
 991									    [0]),
 992							     le_key_k_offset
 993							     (version,
 994							      B_N_PDELIM_KEY
 995							      (tb->CFR[0],
 996							       tb->rkey[0])) +
 997							     temp_rem);
 998						}
 999/*		  k_offset (B_N_PKEY(tb->R[0],0)) += n_rem;
1000		  k_offset (B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])) += n_rem;*/
1001						do_balance_mark_internal_dirty
1002						    (tb, tb->CFR[0], 0);
1003
1004						/* Append part of body into R[0] */
1005						buffer_info_init_right(tb, &bi);
1006						if (n_rem > zeros_num) {
1007							r_zeros_number = 0;
1008							r_body =
1009							    body + n_rem -
1010							    zeros_num;
1011						} else {
1012							r_body = body;
1013							r_zeros_number =
1014							    zeros_num - n_rem;
1015							zeros_num -=
1016							    r_zeros_number;
1017						}
1018
1019						leaf_paste_in_buffer(&bi, 0,
1020								     n_shift,
1021								     tb->
1022								     insert_size
1023								     [0] -
1024								     n_rem,
1025								     r_body,
1026								     r_zeros_number);
1027
1028						if (is_indirect_le_ih
1029						    (B_N_PITEM_HEAD
1030						     (tb->R[0], 0))) {
1031#if 0
1032							RFALSE(n_rem,
1033							       "PAP-12160: paste more than one unformatted node pointer");
1034#endif
1035							set_ih_free_space
1036							    (B_N_PITEM_HEAD
1037							     (tb->R[0], 0), 0);
1038						}
1039						tb->insert_size[0] = n_rem;
1040						if (!n_rem)
1041							pos_in_item++;
1042					}
1043				} else {	/* pasted item in whole falls into R[0] */
1044
1045					struct item_head *pasted;
1046
1047					ret_val =
1048					    leaf_shift_right(tb, tb->rnum[0],
1049							     tb->rbytes);
1050					/* append item in R[0] */
1051					if (pos_in_item >= 0) {
1052						buffer_info_init_right(tb, &bi);
1053						leaf_paste_in_buffer(&bi,
1054								     item_pos -
1055								     n +
1056								     tb->
1057								     rnum[0],
1058								     pos_in_item,
1059								     tb->
1060								     insert_size
1061								     [0], body,
1062								     zeros_num);
1063					}
1064
1065					/* paste new entry, if item is directory item */
1066					pasted =
1067					    B_N_PITEM_HEAD(tb->R[0],
1068							   item_pos - n +
1069							   tb->rnum[0]);
1070					if (is_direntry_le_ih(pasted)
1071					    && pos_in_item >= 0) {
1072						leaf_paste_entries(&bi,
1073								   item_pos -
1074								   n +
1075								   tb->rnum[0],
1076								   pos_in_item,
1077								   1,
1078								   (struct
1079								    reiserfs_de_head
1080								    *)body,
1081								   body +
1082								   DEH_SIZE,
1083								   tb->
1084								   insert_size
1085								   [0]
1086						    );
1087						if (!pos_in_item) {
1088
1089							RFALSE(item_pos - n +
1090							       tb->rnum[0],
1091							       "PAP-12165: directory item must be first item of node when pasting is in 0th position");
1092
1093							/* update delimiting keys */
1094							replace_key(tb,
1095								    tb->CFR[0],
1096								    tb->rkey[0],
1097								    tb->R[0],
1098								    0);
1099						}
1100					}
1101
1102					if (is_indirect_le_ih(pasted))
1103						set_ih_free_space(pasted, 0);
1104					zeros_num = tb->insert_size[0] = 0;
1105				}
1106			} else {	/* new item doesn't fall into R[0] */
1107
1108				leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
1109			}
1110			break;
1111		default:	/* cases d and t */
1112			reiserfs_panic(tb->tb_sb, "PAP-12175",
1113				       "rnum > 0: unexpected mode: %s(%d)",
1114				       (flag ==
1115					M_DELETE) ? "DELETE" : ((flag ==
1116								 M_CUT) ? "CUT"
1117								: "UNKNOWN"),
1118				       flag);
 
 
 
 
 
 
 
 
 
 
 
 
 
1119		}
 
1120
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1121	}
1122
1123	/* tb->rnum[0] > 0 */
1124	RFALSE(tb->blknum[0] > 3,
1125	       "PAP-12180: blknum can not be %d. It must be <= 3",
1126	       tb->blknum[0]);
1127	RFALSE(tb->blknum[0] < 0,
1128	       "PAP-12185: blknum can not be %d. It must be >= 0",
1129	       tb->blknum[0]);
1130
1131	/* if while adding to a node we discover that it is possible to split
1132	   it in two, and merge the left part into the left neighbor and the
1133	   right part into the right neighbor, eliminating the node */
1134	if (tb->blknum[0] == 0) {	/* node S[0] is empty now */
 
 
 
1135
1136		RFALSE(!tb->lnum[0] || !tb->rnum[0],
1137		       "PAP-12190: lnum and rnum must not be zero");
1138		/* if insertion was done before 0-th position in R[0], right
1139		   delimiting key of the tb->L[0]'s and left delimiting key are
1140		   not set correctly */
1141		if (tb->CFL[0]) {
1142			if (!tb->CFR[0])
1143				reiserfs_panic(tb->tb_sb, "vs-12195",
1144					       "CFR not initialized");
1145			copy_key(B_N_PDELIM_KEY(tb->CFL[0], tb->lkey[0]),
1146				 B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]));
1147			do_balance_mark_internal_dirty(tb, tb->CFL[0], 0);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1148		}
1149
1150		reiserfs_invalidate_buffer(tb, tbS0);
1151		return 0;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1152	}
1153
1154	/* Fill new nodes that appear in place of S[0] */
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1155
1156	/* I am told that this copying is because we need an array to enable
1157	   the looping code. -Hans */
1158	snum[0] = tb->s1num, snum[1] = tb->s2num;
1159	sbytes[0] = tb->s1bytes;
1160	sbytes[1] = tb->s2bytes;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1161	for (i = tb->blknum[0] - 2; i >= 0; i--) {
 
1162
1163		RFALSE(!snum[i], "PAP-12200: snum[%d] == %d. Must be > 0", i,
1164		       snum[i]);
 
1165
1166		/* here we shift from S to S_new nodes */
1167
1168		S_new[i] = get_FEB(tb);
1169
1170		/* initialized block type and tree level */
1171		set_blkh_level(B_BLK_HEAD(S_new[i]), DISK_LEAF_NODE_LEVEL);
1172
1173		n = B_NR_ITEMS(tbS0);
 
 
 
 
 
1174
1175		switch (flag) {
1176		case M_INSERT:	/* insert item */
1177
1178			if (n - snum[i] < item_pos) {	/* new item or it's part falls to first new node S_new[i] */
1179				if (item_pos == n - snum[i] + 1 && sbytes[i] != -1) {	/* part of new item falls into S_new[i] */
1180					int old_key_comp, old_len,
1181					    r_zeros_number;
1182					const char *r_body;
1183					int version;
1184
1185					/* Move snum[i]-1 items from S[0] to S_new[i] */
1186					leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1187							snum[i] - 1, -1,
1188							S_new[i]);
1189					/* Remember key component and item length */
1190					version = ih_version(ih);
1191					old_key_comp = le_ih_k_offset(ih);
1192					old_len = ih_item_len(ih);
1193
1194					/* Calculate key component and item length to insert into S_new[i] */
1195					set_le_ih_k_offset(ih,
1196							   le_ih_k_offset(ih) +
1197							   ((old_len -
1198							     sbytes[i]) <<
1199							    (is_indirect_le_ih
1200							     (ih) ? tb->tb_sb->
1201							     s_blocksize_bits -
1202							     UNFM_P_SHIFT :
1203							     0)));
1204
1205					put_ih_item_len(ih, sbytes[i]);
1206
1207					/* Insert part of the item into S_new[i] before 0-th item */
1208					buffer_info_init_bh(tb, &bi, S_new[i]);
1209
1210					if ((old_len - sbytes[i]) > zeros_num) {
1211						r_zeros_number = 0;
1212						r_body =
1213						    body + (old_len -
1214							    sbytes[i]) -
1215						    zeros_num;
1216					} else {
1217						r_body = body;
1218						r_zeros_number =
1219						    zeros_num - (old_len -
1220								 sbytes[i]);
1221						zeros_num -= r_zeros_number;
1222					}
1223
1224					leaf_insert_into_buf(&bi, 0, ih, r_body,
1225							     r_zeros_number);
1226
1227					/* Calculate key component and item length to insert into S[i] */
1228					set_le_ih_k_offset(ih, old_key_comp);
1229					put_ih_item_len(ih,
1230							old_len - sbytes[i]);
1231					tb->insert_size[0] -= sbytes[i];
1232				} else {	/* whole new item falls into S_new[i] */
1233
1234					/* Shift snum[0] - 1 items to S_new[i] (sbytes[i] of split item) */
1235					leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1236							snum[i] - 1, sbytes[i],
1237							S_new[i]);
1238
1239					/* Insert new item into S_new[i] */
1240					buffer_info_init_bh(tb, &bi, S_new[i]);
1241					leaf_insert_into_buf(&bi,
1242							     item_pos - n +
1243							     snum[i] - 1, ih,
1244							     body, zeros_num);
1245
1246					zeros_num = tb->insert_size[0] = 0;
1247				}
1248			}
 
 
 
 
 
1249
1250			else {	/* new item or it part don't falls into S_new[i] */
 
 
 
1251
1252				leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1253						snum[i], sbytes[i], S_new[i]);
1254			}
1255			break;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1256
1257		case M_PASTE:	/* append item */
 
 
 
 
 
 
1258
1259			if (n - snum[i] <= item_pos) {	/* pasted item or part if it falls to S_new[i] */
1260				if (item_pos == n - snum[i] && sbytes[i] != -1) {	/* we must shift part of the appended item */
1261					struct item_head *aux_ih;
1262
1263					RFALSE(ih, "PAP-12210: ih must be 0");
1264
1265					aux_ih = B_N_PITEM_HEAD(tbS0, item_pos);
1266					if (is_direntry_le_ih(aux_ih)) {
1267						/* we append to directory item */
1268
1269						int entry_count;
1270
1271						entry_count =
1272						    ih_entry_count(aux_ih);
1273
1274						if (entry_count - sbytes[i] <
1275						    pos_in_item
1276						    && pos_in_item <=
1277						    entry_count) {
1278							/* new directory entry falls into S_new[i] */
1279
1280							RFALSE(!tb->
1281							       insert_size[0],
1282							       "PAP-12215: insert_size is already 0");
1283							RFALSE(sbytes[i] - 1 >=
1284							       entry_count,
1285							       "PAP-12220: there are no so much entries (%d), only %d",
1286							       sbytes[i] - 1,
1287							       entry_count);
1288
1289							/* Shift snum[i]-1 items in whole. Shift sbytes[i] directory entries from directory item number snum[i] */
1290							leaf_move_items
1291							    (LEAF_FROM_S_TO_SNEW,
1292							     tb, snum[i],
1293							     sbytes[i] - 1,
1294							     S_new[i]);
1295							/* Paste given directory entry to directory item */
1296							buffer_info_init_bh(tb, &bi, S_new[i]);
1297							leaf_paste_in_buffer
1298							    (&bi, 0,
1299							     pos_in_item -
1300							     entry_count +
1301							     sbytes[i] - 1,
1302							     tb->insert_size[0],
1303							     body, zeros_num);
1304							/* paste new directory entry */
1305							leaf_paste_entries(&bi,
1306									   0,
1307									   pos_in_item
1308									   -
1309									   entry_count
1310									   +
1311									   sbytes
1312									   [i] -
1313									   1, 1,
1314									   (struct
1315									    reiserfs_de_head
1316									    *)
1317									   body,
1318									   body
1319									   +
1320									   DEH_SIZE,
1321									   tb->
1322									   insert_size
1323									   [0]
1324							    );
1325							tb->insert_size[0] = 0;
1326							pos_in_item++;
1327						} else {	/* new directory entry doesn't fall into S_new[i] */
1328							leaf_move_items
1329							    (LEAF_FROM_S_TO_SNEW,
1330							     tb, snum[i],
1331							     sbytes[i],
1332							     S_new[i]);
1333						}
1334					} else {	/* regular object */
1335
1336						int n_shift, n_rem,
1337						    r_zeros_number;
1338						const char *r_body;
1339
1340						RFALSE(pos_in_item !=
1341						       ih_item_len
1342						       (B_N_PITEM_HEAD
1343							(tbS0, item_pos))
1344						       || tb->insert_size[0] <=
1345						       0,
1346						       "PAP-12225: item too short or insert_size <= 0");
1347
1348						/* Calculate number of bytes which must be shifted from appended item */
1349						n_shift =
1350						    sbytes[i] -
1351						    tb->insert_size[0];
1352						if (n_shift < 0)
1353							n_shift = 0;
1354						leaf_move_items
1355						    (LEAF_FROM_S_TO_SNEW, tb,
1356						     snum[i], n_shift,
1357						     S_new[i]);
1358
1359						/* Calculate number of bytes which must remain in body after append to S_new[i] */
1360						n_rem =
1361						    tb->insert_size[0] -
1362						    sbytes[i];
1363						if (n_rem < 0)
1364							n_rem = 0;
1365						/* Append part of body into S_new[0] */
1366						buffer_info_init_bh(tb, &bi, S_new[i]);
1367						if (n_rem > zeros_num) {
1368							r_zeros_number = 0;
1369							r_body =
1370							    body + n_rem -
1371							    zeros_num;
1372						} else {
1373							r_body = body;
1374							r_zeros_number =
1375							    zeros_num - n_rem;
1376							zeros_num -=
1377							    r_zeros_number;
1378						}
1379
1380						leaf_paste_in_buffer(&bi, 0,
1381								     n_shift,
1382								     tb->
1383								     insert_size
1384								     [0] -
1385								     n_rem,
1386								     r_body,
1387								     r_zeros_number);
1388						{
1389							struct item_head *tmp;
1390
1391							tmp =
1392							    B_N_PITEM_HEAD(S_new
1393									   [i],
1394									   0);
1395							if (is_indirect_le_ih
1396							    (tmp)) {
1397								set_ih_free_space
1398								    (tmp, 0);
1399								set_le_ih_k_offset
1400								    (tmp,
1401								     le_ih_k_offset
1402								     (tmp) +
1403								     (n_rem <<
1404								      (tb->
1405								       tb_sb->
1406								       s_blocksize_bits
1407								       -
1408								       UNFM_P_SHIFT)));
1409							} else {
1410								set_le_ih_k_offset
1411								    (tmp,
1412								     le_ih_k_offset
1413								     (tmp) +
1414								     n_rem);
1415							}
1416						}
1417
1418						tb->insert_size[0] = n_rem;
1419						if (!n_rem)
1420							pos_in_item++;
1421					}
1422				} else
1423					/* item falls wholly into S_new[i] */
1424				{
1425					int leaf_mi;
1426					struct item_head *pasted;
1427
 
 
 
 
 
1428#ifdef CONFIG_REISERFS_CHECK
1429					struct item_head *ih_check =
1430					    B_N_PITEM_HEAD(tbS0, item_pos);
 
 
 
 
 
1431
1432					if (!is_direntry_le_ih(ih_check)
1433					    && (pos_in_item != ih_item_len(ih_check)
1434						|| tb->insert_size[0] <= 0))
1435						reiserfs_panic(tb->tb_sb,
1436							     "PAP-12235",
1437							     "pos_in_item "
1438							     "must be equal "
1439							     "to ih_item_len");
1440#endif				/* CONFIG_REISERFS_CHECK */
1441
1442					leaf_mi =
1443					    leaf_move_items(LEAF_FROM_S_TO_SNEW,
1444							    tb, snum[i],
1445							    sbytes[i],
1446							    S_new[i]);
1447
1448					RFALSE(leaf_mi,
1449					       "PAP-12240: unexpected value returned by leaf_move_items (%d)",
1450					       leaf_mi);
1451
1452					/* paste into item */
1453					buffer_info_init_bh(tb, &bi, S_new[i]);
1454					leaf_paste_in_buffer(&bi,
1455							     item_pos - n +
1456							     snum[i],
1457							     pos_in_item,
1458							     tb->insert_size[0],
1459							     body, zeros_num);
1460
1461					pasted =
1462					    B_N_PITEM_HEAD(S_new[i],
1463							   item_pos - n +
1464							   snum[i]);
1465					if (is_direntry_le_ih(pasted)) {
1466						leaf_paste_entries(&bi,
1467								   item_pos -
1468								   n + snum[i],
1469								   pos_in_item,
1470								   1,
1471								   (struct
1472								    reiserfs_de_head
1473								    *)body,
1474								   body +
1475								   DEH_SIZE,
1476								   tb->
1477								   insert_size
1478								   [0]
1479						    );
1480					}
1481
1482					/* if we paste to indirect item update ih_free_space */
1483					if (is_indirect_le_ih(pasted))
1484						set_ih_free_space(pasted, 0);
1485					zeros_num = tb->insert_size[0] = 0;
1486				}
1487			}
1488
1489			else {	/* pasted item doesn't fall into S_new[i] */
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1490
1491				leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1492						snum[i], sbytes[i], S_new[i]);
1493			}
1494			break;
1495		default:	/* cases d and t */
1496			reiserfs_panic(tb->tb_sb, "PAP-12245",
1497				       "blknum > 2: unexpected mode: %s(%d)",
1498				       (flag ==
1499					M_DELETE) ? "DELETE" : ((flag ==
1500								 M_CUT) ? "CUT"
1501								: "UNKNOWN"),
1502				       flag);
1503		}
1504
1505		memcpy(insert_key + i, B_N_PKEY(S_new[i], 0), KEY_SIZE);
1506		insert_ptr[i] = S_new[i];
 
1507
1508		RFALSE(!buffer_journaled(S_new[i])
1509		       || buffer_journal_dirty(S_new[i])
1510		       || buffer_dirty(S_new[i]), "PAP-12247: S_new[%d] : (%b)",
1511		       i, S_new[i]);
1512	}
1513
1514	/* if the affected item was not wholly shifted then we perform all necessary operations on that part or whole of the
1515	   affected item which remains in S */
1516	if (0 <= item_pos && item_pos < tb->s0num) {	/* if we must insert or append into buffer S[0] */
1517
1518		switch (flag) {
1519		case M_INSERT:	/* insert item into S[0] */
1520			buffer_info_init_tbS0(tb, &bi);
1521			leaf_insert_into_buf(&bi, item_pos, ih, body,
1522					     zeros_num);
1523
1524			/* If we insert the first key change the delimiting key */
1525			if (item_pos == 0) {
1526				if (tb->CFL[0])	/* can be 0 in reiserfsck */
1527					replace_key(tb, tb->CFL[0], tb->lkey[0],
1528						    tbS0, 0);
1529
1530			}
1531			break;
 
 
 
 
 
1532
1533		case M_PASTE:{	/* append item in S[0] */
1534				struct item_head *pasted;
1535
1536				pasted = B_N_PITEM_HEAD(tbS0, item_pos);
1537				/* when directory, may be new entry already pasted */
1538				if (is_direntry_le_ih(pasted)) {
1539					if (pos_in_item >= 0 &&
1540					    pos_in_item <=
1541					    ih_entry_count(pasted)) {
1542
1543						RFALSE(!tb->insert_size[0],
1544						       "PAP-12260: insert_size is 0 already");
1545
1546						/* prepare space */
1547						buffer_info_init_tbS0(tb, &bi);
1548						leaf_paste_in_buffer(&bi,
1549								     item_pos,
1550								     pos_in_item,
1551								     tb->
1552								     insert_size
1553								     [0], body,
1554								     zeros_num);
1555
1556						/* paste entry */
1557						leaf_paste_entries(&bi,
1558								   item_pos,
1559								   pos_in_item,
1560								   1,
1561								   (struct
1562								    reiserfs_de_head
1563								    *)body,
1564								   body +
1565								   DEH_SIZE,
1566								   tb->
1567								   insert_size
1568								   [0]
1569						    );
1570						if (!item_pos && !pos_in_item) {
1571							RFALSE(!tb->CFL[0]
1572							       || !tb->L[0],
1573							       "PAP-12270: CFL[0]/L[0] must be specified");
1574							if (tb->CFL[0]) {
1575								replace_key(tb,
1576									    tb->
1577									    CFL
1578									    [0],
1579									    tb->
1580									    lkey
1581									    [0],
1582									    tbS0,
1583									    0);
1584
1585							}
1586						}
1587						tb->insert_size[0] = 0;
1588					}
1589				} else {	/* regular object */
1590					if (pos_in_item == ih_item_len(pasted)) {
1591
1592						RFALSE(tb->insert_size[0] <= 0,
1593						       "PAP-12275: insert size must not be %d",
1594						       tb->insert_size[0]);
1595						buffer_info_init_tbS0(tb, &bi);
1596						leaf_paste_in_buffer(&bi,
1597								     item_pos,
1598								     pos_in_item,
1599								     tb->
1600								     insert_size
1601								     [0], body,
1602								     zeros_num);
1603
1604						if (is_indirect_le_ih(pasted)) {
1605#if 0
1606							RFALSE(tb->
1607							       insert_size[0] !=
1608							       UNFM_P_SIZE,
1609							       "PAP-12280: insert_size for indirect item must be %d, not %d",
1610							       UNFM_P_SIZE,
1611							       tb->
1612							       insert_size[0]);
1613#endif
1614							set_ih_free_space
1615							    (pasted, 0);
1616						}
1617						tb->insert_size[0] = 0;
1618					}
1619#ifdef CONFIG_REISERFS_CHECK
1620					else {
1621						if (tb->insert_size[0]) {
1622							print_cur_tb("12285");
1623							reiserfs_panic(tb->
1624								       tb_sb,
1625							    "PAP-12285",
1626							    "insert_size "
1627							    "must be 0 "
1628							    "(%d)",
1629							    tb->insert_size[0]);
1630						}
1631					}
1632#endif				/* CONFIG_REISERFS_CHECK */
1633
1634				}
1635			}	/* case M_PASTE: */
 
 
 
 
 
 
 
 
 
 
 
 
1636		}
 
 
 
1637	}
 
 
 
 
 
1638#ifdef CONFIG_REISERFS_CHECK
1639	if (flag == M_PASTE && tb->insert_size[0]) {
1640		print_cur_tb("12290");
1641		reiserfs_panic(tb->tb_sb,
1642			       "PAP-12290", "insert_size is still not 0 (%d)",
1643			       tb->insert_size[0]);
1644	}
1645#endif				/* CONFIG_REISERFS_CHECK */
 
 
1646	return 0;
1647}				/* Leaf level of the tree is balanced (end of balance_leaf) */
1648
1649/* Make empty node */
1650void make_empty_node(struct buffer_info *bi)
1651{
1652	struct block_head *blkh;
1653
1654	RFALSE(bi->bi_bh == NULL, "PAP-12295: pointer to the buffer is NULL");
1655
1656	blkh = B_BLK_HEAD(bi->bi_bh);
1657	set_blkh_nr_item(blkh, 0);
1658	set_blkh_free_space(blkh, MAX_CHILD_SIZE(bi->bi_bh));
1659
1660	if (bi->bi_parent)
1661		B_N_CHILD(bi->bi_parent, bi->bi_position)->dc_size = 0;	/* Endian safe if 0 */
1662}
1663
1664/* Get first empty buffer */
1665struct buffer_head *get_FEB(struct tree_balance *tb)
1666{
1667	int i;
1668	struct buffer_info bi;
1669
1670	for (i = 0; i < MAX_FEB_SIZE; i++)
1671		if (tb->FEB[i] != NULL)
1672			break;
1673
1674	if (i == MAX_FEB_SIZE)
1675		reiserfs_panic(tb->tb_sb, "vs-12300", "FEB list is empty");
1676
1677	buffer_info_init_bh(tb, &bi, tb->FEB[i]);
1678	make_empty_node(&bi);
1679	set_buffer_uptodate(tb->FEB[i]);
1680	tb->used[i] = tb->FEB[i];
1681	tb->FEB[i] = NULL;
1682
1683	return tb->used[i];
1684}
1685
1686/* This is now used because reiserfs_free_block has to be able to
1687** schedule.
1688*/
1689static void store_thrown(struct tree_balance *tb, struct buffer_head *bh)
1690{
1691	int i;
1692
1693	if (buffer_dirty(bh))
1694		reiserfs_warning(tb->tb_sb, "reiserfs-12320",
1695				 "called with dirty buffer");
1696	for (i = 0; i < ARRAY_SIZE(tb->thrown); i++)
1697		if (!tb->thrown[i]) {
1698			tb->thrown[i] = bh;
1699			get_bh(bh);	/* free_thrown puts this */
1700			return;
1701		}
1702	reiserfs_warning(tb->tb_sb, "reiserfs-12321",
1703			 "too many thrown buffers");
1704}
1705
1706static void free_thrown(struct tree_balance *tb)
1707{
1708	int i;
1709	b_blocknr_t blocknr;
1710	for (i = 0; i < ARRAY_SIZE(tb->thrown); i++) {
1711		if (tb->thrown[i]) {
1712			blocknr = tb->thrown[i]->b_blocknr;
1713			if (buffer_dirty(tb->thrown[i]))
1714				reiserfs_warning(tb->tb_sb, "reiserfs-12322",
1715						 "called with dirty buffer %d",
1716						 blocknr);
1717			brelse(tb->thrown[i]);	/* incremented in store_thrown */
1718			reiserfs_free_block(tb->transaction_handle, NULL,
1719					    blocknr, 0);
1720		}
1721	}
1722}
1723
1724void reiserfs_invalidate_buffer(struct tree_balance *tb, struct buffer_head *bh)
1725{
1726	struct block_head *blkh;
1727	blkh = B_BLK_HEAD(bh);
1728	set_blkh_level(blkh, FREE_LEVEL);
1729	set_blkh_nr_item(blkh, 0);
1730
1731	clear_buffer_dirty(bh);
1732	store_thrown(tb, bh);
1733}
1734
1735/* Replace n_dest'th key in buffer dest by n_src'th key of buffer src.*/
1736void replace_key(struct tree_balance *tb, struct buffer_head *dest, int n_dest,
1737		 struct buffer_head *src, int n_src)
1738{
1739
1740	RFALSE(dest == NULL || src == NULL,
1741	       "vs-12305: source or destination buffer is 0 (src=%p, dest=%p)",
1742	       src, dest);
1743	RFALSE(!B_IS_KEYS_LEVEL(dest),
1744	       "vs-12310: invalid level (%z) for destination buffer. dest must be leaf",
1745	       dest);
1746	RFALSE(n_dest < 0 || n_src < 0,
1747	       "vs-12315: src(%d) or dest(%d) key number < 0", n_src, n_dest);
1748	RFALSE(n_dest >= B_NR_ITEMS(dest) || n_src >= B_NR_ITEMS(src),
1749	       "vs-12320: src(%d(%d)) or dest(%d(%d)) key number is too big",
1750	       n_src, B_NR_ITEMS(src), n_dest, B_NR_ITEMS(dest));
1751
1752	if (B_IS_ITEMS_LEVEL(src))
1753		/* source buffer contains leaf node */
1754		memcpy(B_N_PDELIM_KEY(dest, n_dest), B_N_PITEM_HEAD(src, n_src),
1755		       KEY_SIZE);
1756	else
1757		memcpy(B_N_PDELIM_KEY(dest, n_dest), B_N_PDELIM_KEY(src, n_src),
1758		       KEY_SIZE);
1759
1760	do_balance_mark_internal_dirty(tb, dest, 0);
1761}
1762
1763int get_left_neighbor_position(struct tree_balance *tb, int h)
1764{
1765	int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
1766
1767	RFALSE(PATH_H_PPARENT(tb->tb_path, h) == NULL || tb->FL[h] == NULL,
1768	       "vs-12325: FL[%d](%p) or F[%d](%p) does not exist",
1769	       h, tb->FL[h], h, PATH_H_PPARENT(tb->tb_path, h));
1770
1771	if (Sh_position == 0)
1772		return B_NR_ITEMS(tb->FL[h]);
1773	else
1774		return Sh_position - 1;
1775}
1776
1777int get_right_neighbor_position(struct tree_balance *tb, int h)
1778{
1779	int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
1780
1781	RFALSE(PATH_H_PPARENT(tb->tb_path, h) == NULL || tb->FR[h] == NULL,
1782	       "vs-12330: F[%d](%p) or FR[%d](%p) does not exist",
1783	       h, PATH_H_PPARENT(tb->tb_path, h), h, tb->FR[h]);
1784
1785	if (Sh_position == B_NR_ITEMS(PATH_H_PPARENT(tb->tb_path, h)))
1786		return 0;
1787	else
1788		return Sh_position + 1;
1789}
1790
1791#ifdef CONFIG_REISERFS_CHECK
1792
1793int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value);
1794static void check_internal_node(struct super_block *s, struct buffer_head *bh,
1795				char *mes)
1796{
1797	struct disk_child *dc;
1798	int i;
1799
1800	RFALSE(!bh, "PAP-12336: bh == 0");
1801
1802	if (!bh || !B_IS_IN_TREE(bh))
1803		return;
1804
1805	RFALSE(!buffer_dirty(bh) &&
1806	       !(buffer_journaled(bh) || buffer_journal_dirty(bh)),
1807	       "PAP-12337: buffer (%b) must be dirty", bh);
1808	dc = B_N_CHILD(bh, 0);
1809
1810	for (i = 0; i <= B_NR_ITEMS(bh); i++, dc++) {
1811		if (!is_reusable(s, dc_block_number(dc), 1)) {
1812			print_cur_tb(mes);
1813			reiserfs_panic(s, "PAP-12338",
1814				       "invalid child pointer %y in %b",
1815				       dc, bh);
1816		}
1817	}
1818}
1819
1820static int locked_or_not_in_tree(struct tree_balance *tb,
1821				  struct buffer_head *bh, char *which)
1822{
1823	if ((!buffer_journal_prepared(bh) && buffer_locked(bh)) ||
1824	    !B_IS_IN_TREE(bh)) {
1825		reiserfs_warning(tb->tb_sb, "vs-12339", "%s (%b)", which, bh);
1826		return 1;
1827	}
1828	return 0;
1829}
1830
1831static int check_before_balancing(struct tree_balance *tb)
1832{
1833	int retval = 0;
1834
1835	if (REISERFS_SB(tb->tb_sb)->cur_tb) {
1836		reiserfs_panic(tb->tb_sb, "vs-12335", "suspect that schedule "
1837			       "occurred based on cur_tb not being null at "
1838			       "this point in code. do_balance cannot properly "
1839			       "handle concurrent tree accesses on a same "
1840			       "mount point.");
1841	}
1842
1843	/* double check that buffers that we will modify are unlocked. (fix_nodes should already have
1844	   prepped all of these for us). */
 
 
1845	if (tb->lnum[0]) {
1846		retval |= locked_or_not_in_tree(tb, tb->L[0], "L[0]");
1847		retval |= locked_or_not_in_tree(tb, tb->FL[0], "FL[0]");
1848		retval |= locked_or_not_in_tree(tb, tb->CFL[0], "CFL[0]");
1849		check_leaf(tb->L[0]);
1850	}
1851	if (tb->rnum[0]) {
1852		retval |= locked_or_not_in_tree(tb, tb->R[0], "R[0]");
1853		retval |= locked_or_not_in_tree(tb, tb->FR[0], "FR[0]");
1854		retval |= locked_or_not_in_tree(tb, tb->CFR[0], "CFR[0]");
1855		check_leaf(tb->R[0]);
1856	}
1857	retval |= locked_or_not_in_tree(tb, PATH_PLAST_BUFFER(tb->tb_path),
1858					"S[0]");
1859	check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
1860
1861	return retval;
1862}
1863
1864static void check_after_balance_leaf(struct tree_balance *tb)
1865{
1866	if (tb->lnum[0]) {
1867		if (B_FREE_SPACE(tb->L[0]) !=
1868		    MAX_CHILD_SIZE(tb->L[0]) -
1869		    dc_size(B_N_CHILD
1870			    (tb->FL[0], get_left_neighbor_position(tb, 0)))) {
1871			print_cur_tb("12221");
1872			reiserfs_panic(tb->tb_sb, "PAP-12355",
1873				       "shift to left was incorrect");
1874		}
1875	}
1876	if (tb->rnum[0]) {
1877		if (B_FREE_SPACE(tb->R[0]) !=
1878		    MAX_CHILD_SIZE(tb->R[0]) -
1879		    dc_size(B_N_CHILD
1880			    (tb->FR[0], get_right_neighbor_position(tb, 0)))) {
1881			print_cur_tb("12222");
1882			reiserfs_panic(tb->tb_sb, "PAP-12360",
1883				       "shift to right was incorrect");
1884		}
1885	}
1886	if (PATH_H_PBUFFER(tb->tb_path, 1) &&
1887	    (B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0)) !=
1888	     (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
1889	      dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
1890				PATH_H_POSITION(tb->tb_path, 1)))))) {
1891		int left = B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0));
1892		int right = (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
1893			     dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
1894					       PATH_H_POSITION(tb->tb_path,
1895							       1))));
1896		print_cur_tb("12223");
1897		reiserfs_warning(tb->tb_sb, "reiserfs-12363",
1898				 "B_FREE_SPACE (PATH_H_PBUFFER(tb->tb_path,0)) = %d; "
1899				 "MAX_CHILD_SIZE (%d) - dc_size( %y, %d ) [%d] = %d",
1900				 left,
1901				 MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)),
1902				 PATH_H_PBUFFER(tb->tb_path, 1),
1903				 PATH_H_POSITION(tb->tb_path, 1),
1904				 dc_size(B_N_CHILD
1905					 (PATH_H_PBUFFER(tb->tb_path, 1),
1906					  PATH_H_POSITION(tb->tb_path, 1))),
1907				 right);
1908		reiserfs_panic(tb->tb_sb, "PAP-12365", "S is incorrect");
1909	}
1910}
1911
1912static void check_leaf_level(struct tree_balance *tb)
1913{
1914	check_leaf(tb->L[0]);
1915	check_leaf(tb->R[0]);
1916	check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
1917}
1918
1919static void check_internal_levels(struct tree_balance *tb)
1920{
1921	int h;
1922
1923	/* check all internal nodes */
1924	for (h = 1; tb->insert_size[h]; h++) {
1925		check_internal_node(tb->tb_sb, PATH_H_PBUFFER(tb->tb_path, h),
1926				    "BAD BUFFER ON PATH");
1927		if (tb->lnum[h])
1928			check_internal_node(tb->tb_sb, tb->L[h], "BAD L");
1929		if (tb->rnum[h])
1930			check_internal_node(tb->tb_sb, tb->R[h], "BAD R");
1931	}
1932
1933}
1934
1935#endif
1936
1937/* Now we have all of the buffers that must be used in balancing of
1938   the tree.  We rely on the assumption that schedule() will not occur
1939   while do_balance works. ( Only interrupt handlers are acceptable.)
1940   We balance the tree according to the analysis made before this,
1941   using buffers already obtained.  For SMP support it will someday be
1942   necessary to add ordered locking of tb. */
1943
1944/* Some interesting rules of balancing:
1945
1946   we delete a maximum of two nodes per level per balancing: we never
1947   delete R, when we delete two of three nodes L, S, R then we move
1948   them into R.
1949
1950   we only delete L if we are deleting two nodes, if we delete only
1951   one node we delete S
1952
1953   if we shift leaves then we shift as much as we can: this is a
1954   deliberate policy of extremism in node packing which results in
1955   higher average utilization after repeated random balance operations
1956   at the cost of more memory copies and more balancing as a result of
1957   small insertions to full nodes.
1958
1959   if we shift internal nodes we try to evenly balance the node
1960   utilization, with consequent less balancing at the cost of lower
1961   utilization.
1962
1963   one could argue that the policy for directories in leaves should be
1964   that of internal nodes, but we will wait until another day to
1965   evaluate this....  It would be nice to someday measure and prove
1966   these assumptions as to what is optimal....
1967
1968*/
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1969
1970static inline void do_balance_starts(struct tree_balance *tb)
1971{
1972	/* use print_cur_tb() to see initial state of struct
1973	   tree_balance */
1974
1975	/* store_print_tb (tb); */
1976
1977	/* do not delete, just comment it out */
1978/*    print_tb(flag, PATH_LAST_POSITION(tb->tb_path), tb->tb_path->pos_in_item, tb,
1979	     "check");*/
 
 
1980	RFALSE(check_before_balancing(tb), "PAP-12340: locked buffers in TB");
1981#ifdef CONFIG_REISERFS_CHECK
1982	REISERFS_SB(tb->tb_sb)->cur_tb = tb;
1983#endif
1984}
1985
1986static inline void do_balance_completed(struct tree_balance *tb)
1987{
1988
1989#ifdef CONFIG_REISERFS_CHECK
1990	check_leaf_level(tb);
1991	check_internal_levels(tb);
1992	REISERFS_SB(tb->tb_sb)->cur_tb = NULL;
1993#endif
1994
1995	/* reiserfs_free_block is no longer schedule safe.  So, we need to
1996	 ** put the buffers we want freed on the thrown list during do_balance,
1997	 ** and then free them now
 
1998	 */
1999
2000	REISERFS_SB(tb->tb_sb)->s_do_balance++;
2001
2002	/* release all nodes hold to perform the balancing */
2003	unfix_nodes(tb);
2004
2005	free_thrown(tb);
2006}
2007
2008void do_balance(struct tree_balance *tb,	/* tree_balance structure */
2009		struct item_head *ih,	/* item header of inserted item */
2010		const char *body,	/* body  of inserted item or bytes to paste */
2011		int flag)
2012{				/* i - insert, d - delete
2013				   c - cut, p - paste
2014
2015				   Cut means delete part of an item
2016				   (includes removing an entry from a
2017				   directory).
2018
2019				   Delete means delete whole item.
2020
2021				   Insert means add a new item into the
2022				   tree.
2023
2024				   Paste means to append to the end of an
2025				   existing file or to insert a directory
2026				   entry.  */
2027	int child_pos,		/* position of a child node in its parent */
2028	 h;			/* level of the tree being processed */
2029	struct item_head insert_key[2];	/* in our processing of one level
2030					   we sometimes determine what
2031					   must be inserted into the next
2032					   higher level.  This insertion
2033					   consists of a key or two keys
2034					   and their corresponding
2035					   pointers */
2036	struct buffer_head *insert_ptr[2];	/* inserted node-ptrs for the next
2037						   level */
 
 
 
 
2038
2039	tb->tb_mode = flag;
2040	tb->need_balance_dirty = 0;
2041
2042	if (FILESYSTEM_CHANGED_TB(tb)) {
2043		reiserfs_panic(tb->tb_sb, "clm-6000", "fs generation has "
2044			       "changed");
2045	}
2046	/* if we have no real work to do  */
2047	if (!tb->insert_size[0]) {
2048		reiserfs_warning(tb->tb_sb, "PAP-12350",
2049				 "insert_size == 0, mode == %c", flag);
2050		unfix_nodes(tb);
2051		return;
2052	}
2053
2054	atomic_inc(&(fs_generation(tb->tb_sb)));
2055	do_balance_starts(tb);
2056
2057	/* balance leaf returns 0 except if combining L R and S into
2058	   one node.  see balance_internal() for explanation of this
2059	   line of code. */
 
 
2060	child_pos = PATH_H_B_ITEM_ORDER(tb->tb_path, 0) +
2061	    balance_leaf(tb, ih, body, flag, insert_key, insert_ptr);
2062
2063#ifdef CONFIG_REISERFS_CHECK
2064	check_after_balance_leaf(tb);
2065#endif
2066
2067	/* Balance internal level of the tree. */
2068	for (h = 1; h < MAX_HEIGHT && tb->insert_size[h]; h++)
2069		child_pos =
2070		    balance_internal(tb, h, child_pos, insert_key, insert_ptr);
2071
2072	do_balance_completed(tb);
2073
2074}