do_balan.c

linux 内核源代码

							     tb->rbytes);
					/* append item in R[0] */
					if (pos_in_item >= 0) {
						bi.tb = tb;
						bi.bi_bh = tb->R[0];
						bi.bi_parent = tb->FR[0];
						bi.bi_position =
						    get_right_neighbor_position
						    (tb, 0);
						leaf_paste_in_buffer(&bi,
								     item_pos -
								     n +
								     tb->
								     rnum[0],
								     pos_in_item,
								     tb->
								     insert_size
								     [0], body,
								     zeros_num);
					}

					/* paste new entry, if item is directory item */
					pasted =
					    B_N_PITEM_HEAD(tb->R[0],
							   item_pos - n +
							   tb->rnum[0]);
					if (is_direntry_le_ih(pasted)
					    && pos_in_item >= 0) {
						leaf_paste_entries(bi.bi_bh,
								   item_pos -
								   n +
								   tb->rnum[0],
								   pos_in_item,
								   1,
								   (struct
								    reiserfs_de_head
								    *)body,
								   body +
								   DEH_SIZE,
								   tb->
								   insert_size
								   [0]
						    );
						if (!pos_in_item) {

							RFALSE(item_pos - n +
							       tb->rnum[0],
							       "PAP-12165: directory item must be first item of node when pasting is in 0th position");

							/* update delimiting keys */
							replace_key(tb,
								    tb->CFR[0],
								    tb->rkey[0],
								    tb->R[0],
								    0);
						}
					}

					if (is_indirect_le_ih(pasted))
						set_ih_free_space(pasted, 0);
					zeros_num = tb->insert_size[0] = 0;
				}
			} else {	/* new item doesn't fall into R[0] */

				leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
			}
			break;
		default:	/* cases d and t */
			reiserfs_panic(tb->tb_sb,
				       "PAP-12175: balance_leaf: rnum > 0: unexpectable mode: %s(%d)",
				       (flag ==
					M_DELETE) ? "DELETE" : ((flag ==
								 M_CUT) ? "CUT"
								: "UNKNOWN"),
				       flag);
		}

	}

	/* tb->rnum[0] > 0 */
	RFALSE(tb->blknum[0] > 3,
	       "PAP-12180: blknum can not be %d. It must be <= 3",
	       tb->blknum[0]);
	RFALSE(tb->blknum[0] < 0,
	       "PAP-12185: blknum can not be %d. It must be >= 0",
	       tb->blknum[0]);

	/* if while adding to a node we discover that it is possible to split
	   it in two, and merge the left part into the left neighbor and the
	   right part into the right neighbor, eliminating the node */
	if (tb->blknum[0] == 0) {	/* node S[0] is empty now */

		RFALSE(!tb->lnum[0] || !tb->rnum[0],
		       "PAP-12190: lnum and rnum must not be zero");
		/* if insertion was done before 0-th position in R[0], right
		   delimiting key of the tb->L[0]'s and left delimiting key are
		   not set correctly */
		if (tb->CFL[0]) {
			if (!tb->CFR[0])
				reiserfs_panic(tb->tb_sb,
					       "vs-12195: balance_leaf: CFR not initialized");
			copy_key(B_N_PDELIM_KEY(tb->CFL[0], tb->lkey[0]),
				 B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]));
			do_balance_mark_internal_dirty(tb, tb->CFL[0], 0);
		}

		reiserfs_invalidate_buffer(tb, tbS0);
		return 0;
	}

	/* Fill new nodes that appear in place of S[0] */

	/* I am told that this copying is because we need an array to enable
	   the looping code. -Hans */
	snum[0] = tb->s1num, snum[1] = tb->s2num;
	sbytes[0] = tb->s1bytes;
	sbytes[1] = tb->s2bytes;
	for (i = tb->blknum[0] - 2; i >= 0; i--) {

		RFALSE(!snum[i], "PAP-12200: snum[%d] == %d. Must be > 0", i,
		       snum[i]);

		/* here we shift from S to S_new nodes */

		S_new[i] = get_FEB(tb);

		/* initialized block type and tree level */
		set_blkh_level(B_BLK_HEAD(S_new[i]), DISK_LEAF_NODE_LEVEL);

		n = B_NR_ITEMS(tbS0);

		switch (flag) {
		case M_INSERT:	/* insert item */

			if (n - snum[i] < item_pos) {	/* new item or it's part falls to first new node S_new[i] */
				if (item_pos == n - snum[i] + 1 && sbytes[i] != -1) {	/* part of new item falls into S_new[i] */
					int old_key_comp, old_len,
					    r_zeros_number;
					const char *r_body;
					int version;

					/* Move snum[i]-1 items from S[0] to S_new[i] */
					leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
							snum[i] - 1, -1,
							S_new[i]);
					/* Remember key component and item length */
					version = ih_version(ih);
					old_key_comp = le_ih_k_offset(ih);
					old_len = ih_item_len(ih);

					/* Calculate key component and item length to insert into S_new[i] */
					set_le_ih_k_offset(ih,
							   le_ih_k_offset(ih) +
							   ((old_len -
							     sbytes[i]) <<
							    (is_indirect_le_ih
							     (ih) ? tb->tb_sb->
							     s_blocksize_bits -
							     UNFM_P_SHIFT :
							     0)));

					put_ih_item_len(ih, sbytes[i]);

					/* Insert part of the item into S_new[i] before 0-th item */
					bi.tb = tb;
					bi.bi_bh = S_new[i];
					bi.bi_parent = NULL;
					bi.bi_position = 0;

					if ((old_len - sbytes[i]) > zeros_num) {
						r_zeros_number = 0;
						r_body =
						    body + (old_len -
							    sbytes[i]) -
						    zeros_num;
					} else {
						r_body = body;
						r_zeros_number =
						    zeros_num - (old_len -
								 sbytes[i]);
						zeros_num -= r_zeros_number;
					}

					leaf_insert_into_buf(&bi, 0, ih, r_body,
							     r_zeros_number);

					/* Calculate key component and item length to insert into S[i] */
					set_le_ih_k_offset(ih, old_key_comp);
					put_ih_item_len(ih,
							old_len - sbytes[i]);
					tb->insert_size[0] -= sbytes[i];
				} else {	/* whole new item falls into S_new[i] */

					/* Shift snum[0] - 1 items to S_new[i] (sbytes[i] of split item) */
					leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
							snum[i] - 1, sbytes[i],
							S_new[i]);

					/* Insert new item into S_new[i] */
					bi.tb = tb;
					bi.bi_bh = S_new[i];
					bi.bi_parent = NULL;
					bi.bi_position = 0;
					leaf_insert_into_buf(&bi,
							     item_pos - n +
							     snum[i] - 1, ih,
							     body, zeros_num);

					zeros_num = tb->insert_size[0] = 0;
				}
			}

			else {	/* new item or it part don't falls into S_new[i] */

				leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
						snum[i], sbytes[i], S_new[i]);
			}
			break;

		case M_PASTE:	/* append item */

			if (n - snum[i] <= item_pos) {	/* pasted item or part if it falls to S_new[i] */
				if (item_pos == n - snum[i] && sbytes[i] != -1) {	/* we must shift part of the appended item */
					struct item_head *aux_ih;

					RFALSE(ih, "PAP-12210: ih must be 0");

					if (is_direntry_le_ih
					    (aux_ih =
					     B_N_PITEM_HEAD(tbS0, item_pos))) {
						/* we append to directory item */

						int entry_count;

						entry_count =
						    ih_entry_count(aux_ih);

						if (entry_count - sbytes[i] <
						    pos_in_item
						    && pos_in_item <=
						    entry_count) {
							/* new directory entry falls into S_new[i] */

							RFALSE(!tb->
							       insert_size[0],
							       "PAP-12215: insert_size is already 0");
							RFALSE(sbytes[i] - 1 >=
							       entry_count,
							       "PAP-12220: there are no so much entries (%d), only %d",
							       sbytes[i] - 1,
							       entry_count);

							/* Shift snum[i]-1 items in whole. Shift sbytes[i] directory entries from directory item number snum[i] */
							leaf_move_items
							    (LEAF_FROM_S_TO_SNEW,
							     tb, snum[i],
							     sbytes[i] - 1,
							     S_new[i]);
							/* Paste given directory entry to directory item */
							bi.tb = tb;
							bi.bi_bh = S_new[i];
							bi.bi_parent = NULL;
							bi.bi_position = 0;
							leaf_paste_in_buffer
							    (&bi, 0,
							     pos_in_item -
							     entry_count +
							     sbytes[i] - 1,
							     tb->insert_size[0],
							     body, zeros_num);
							/* paste new directory entry */
							leaf_paste_entries(bi.
									   bi_bh,
									   0,
									   pos_in_item
									   -
									   entry_count
									   +
									   sbytes
									   [i] -
									   1, 1,
									   (struct
									    reiserfs_de_head
									    *)
									   body,
									   body
									   +
									   DEH_SIZE,
									   tb->
									   insert_size
									   [0]
							    );
							tb->insert_size[0] = 0;
							pos_in_item++;
						} else {	/* new directory entry doesn't fall into S_new[i] */
							leaf_move_items
							    (LEAF_FROM_S_TO_SNEW,
							     tb, snum[i],
							     sbytes[i],
							     S_new[i]);
						}
					} else {	/* regular object */

						int n_shift, n_rem,
						    r_zeros_number;
						const char *r_body;

						RFALSE(pos_in_item !=
						       ih_item_len
						       (B_N_PITEM_HEAD
							(tbS0, item_pos))
						       || tb->insert_size[0] <=
						       0,
						       "PAP-12225: item too short or insert_size <= 0");

						/* Calculate number of bytes which must be shifted from appended item */
						n_shift =
						    sbytes[i] -
						    tb->insert_size[0];
						if (n_shift < 0)
							n_shift = 0;
						leaf_move_items
						    (LEAF_FROM_S_TO_SNEW, tb,
						     snum[i], n_shift,
						     S_new[i]);

						/* Calculate number of bytes which must remain in body after append to S_new[i] */
						n_rem =
						    tb->insert_size[0] -
						    sbytes[i];
						if (n_rem < 0)
							n_rem = 0;
						/* Append part of body into S_new[0] */
						bi.tb = tb;
						bi.bi_bh = S_new[i];
						bi.bi_parent = NULL;
						bi.bi_position = 0;

						if (n_rem > zeros_num) {
							r_zeros_number = 0;
							r_body =
							    body + n_rem -
							    zeros_num;
						} else {
							r_body = body;
							r_zeros_number =
							    zeros_num - n_rem;
							zeros_num -=
							    r_zeros_number;
						}

						leaf_paste_in_buffer(&bi, 0,
								     n_shift,
								     tb->
								     insert_size
								     [0] -
								     n_rem,
								     r_body,
								     r_zeros_number);
						{
							struct item_head *tmp;

							tmp =
							    B_N_PITEM_HEAD(S_new
									   [i],
									   0);
							if (is_indirect_le_ih
							    (tmp)) {
								set_ih_free_space
								    (tmp, 0);
								set_le_ih_k_offset
								    (tmp,
								     le_ih_k_offset
								     (tmp) +
								     (n_rem <<
								      (tb->
								       tb_sb->
								       s_blocksize_bits
								       -
								       UNFM_P_SHIFT)));
							} else {
								set_le_ih_k_offset
								    (tmp,
								     le_ih_k_offset
								     (tmp) +
								     n_rem);
							}
						}

						tb->insert_size[0] = n_rem;
						if (!n_rem)
							pos_in_item++;
					}
				} else
					/* item falls wholly into S_new[i] */
				{
					int ret_val;
					struct item_head *pasted;

#ifdef CONFIG_REISERFS_CHECK
					struct item_head *ih =
					    B_N_PITEM_HEAD(tbS0, item_pos);

					if (!is_direntry_le_ih(ih)
					    && (pos_in_item != ih_item_len(ih)
						|| tb->insert_size[0] <= 0))
						reiserfs_panic(tb->tb_sb,
							       "PAP-12235: balance_leaf: pos_in_item must be equal to ih_item_len");
#endif				/* CONFIG_REISERFS_CHECK */

					ret_val =
					    leaf_move_items(LEAF_FROM_S_TO_SNEW,
							    tb, snum[i],
							    sbytes[i],
							    S_new[i]);

					RFALSE(ret_val,
					       "PAP-12240: unexpected value returned by leaf_move_items (%d)",
					       ret_val);

					/* paste into item */
					bi.tb = tb;
					bi.bi_bh = S_new[i];
					bi.bi_parent = NULL;
					bi.bi_position = 0;
					leaf_paste_in_buffer(&bi,
							     item_pos - n +
							     snum[i],
							     pos_in_item,
							     tb->insert_size[0],
							     body, zeros_num);

					pasted =
					    B_N_PITEM_HEAD(S_new[i],
							   item_pos - n +
							   snum[i]);
					if (is_direntry_le_ih(pasted)) {
						leaf_paste_entries(bi.bi_bh,
								   item_pos -
								   n + snum[i],
								   pos_in_item,
								   1,
								   (struct
								    reiserfs_de_head
								    *)body,
								   body +
								   DEH_SIZE,
								   tb->
								   insert_size
								   [0]
						    );
					}

					/* if we paste to indirect item update ih_free_space */
					if (is_indirect_le_ih(pasted))
						set_ih_free_space(pasted, 0);
					zeros_num = tb->insert_size[0] = 0;
				}
			}

			else {	/* pasted item doesn't fall into S_new[i] */

				leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
						snum[i], sbytes[i], S_new[i]);
			}
			break;
		default:	/* cases d and t */
			reiserfs_panic(tb->tb_sb,
				       "PAP-12245: balance_leaf: blknum > 2: unexpectable mode: %s(%d)",
				       (flag ==
					M_DELETE) ? "DELETE" : ((flag ==
								 M_CUT) ? "CUT"
								: "UNKNOWN"),
				       flag);
		}

		memcpy(insert_key + i, B_N_PKEY(S_new[i], 0), KEY_SIZE);
		insert_ptr[i] = S_new[i];

		RFALSE(!buffer_journaled(S_new[i])
		       || buffer_journal_dirty(S_new[i])
		       || buffer_dirty(S_new[i]), "PAP-12247: S_new[%d] : (%b)",
		       i, S_new[i]);
	}

	/* if the affected item was not wholly shifted then we perform all necessary operations on that part or whole of the
	   affected item which remains in S */
	if (0 <= item_pos && item_pos < tb->s0num) {	/* if we must insert or append into buffer S[0] */

		switch (flag) {
		case M_INSERT:	/* insert item into S[0] */
			bi.tb = tb;
			bi.bi_bh = tbS0;
			bi.bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
			bi.bi_position = PATH_H_POSITION(tb->tb_path, 1);
			leaf_insert_into_buf(&bi, item_pos, ih, body,
					     zeros_num);

			/* If we insert the first key change the delimiting key */
			if (item_pos == 0) {
				if (tb->CFL[0])	/* can be 0 in reiserfsck */
					replace_key(tb, tb->CFL[0], tb->lkey[0],
						    tbS0, 0);

			}
			break;

		case M_PASTE:{	/* append item in S[0] */
				struct item_head *pasted;

				pasted = B_N_PITEM_HEAD(tbS0, item_pos);
				/* when directory, may be new entry already pasted */
				if (is_direntry_le_ih(pasted)) {
					if (pos_in_item >= 0 &&
					    pos_in_item <=
					    ih_entry_count(pasted)) {

						RFALSE(!tb->insert_size[0],
						       "PAP-12260: insert_size is 0 already");

						/* prepare space */
						bi.tb = tb;
						bi.bi_bh = tbS0;
						bi.bi_parent =
						    PATH_H_PPARENT(tb->tb_path,
								   0);
						bi.bi_position =
						    PATH_H_POSITION(tb->tb_path,
								    1);
						leaf_paste_in_buffer(&bi,
								     item_pos,
								     pos_in_item,
								     tb->
								     insert_size
								     [0], body,