do_balan.c

linux 内核源代码

							     n + item_pos -
							     ret_val,
							     ih_item_len
							     (B_N_PITEM_HEAD
							      (tb->L[0],
							       n + item_pos -
							       ret_val)), l_n,
							     body,
							     zeros_num >
							     l_n ? l_n :
							     zeros_num);
							/* 0-th item in S0 can be only of DIRECT type when l_n != 0 */
							{
								int version;
								int temp_l =
								    l_n;

								RFALSE
								    (ih_item_len
								     (B_N_PITEM_HEAD
								      (tbS0,
								       0)),
								     "PAP-12106: item length must be 0");
								RFALSE
								    (comp_short_le_keys
								     (B_N_PKEY
								      (tbS0, 0),
								      B_N_PKEY
								      (tb->L[0],
								       n +
								       item_pos
								       -
								       ret_val)),
								     "PAP-12107: items must be of the same file");
								if (is_indirect_le_ih(B_N_PITEM_HEAD(tb->L[0], n + item_pos - ret_val))) {
									temp_l =
									    l_n
									    <<
									    (tb->
									     tb_sb->
									     s_blocksize_bits
									     -
									     UNFM_P_SHIFT);
								}
								/* update key of first item in S0 */
								version =
								    ih_version
								    (B_N_PITEM_HEAD
								     (tbS0, 0));
								set_le_key_k_offset
								    (version,
								     B_N_PKEY
								     (tbS0, 0),
								     le_key_k_offset
								     (version,
								      B_N_PKEY
								      (tbS0,
								       0)) +
								     temp_l);
								/* update left delimiting key */
								set_le_key_k_offset
								    (version,
								     B_N_PDELIM_KEY
								     (tb->
								      CFL[0],
								      tb->
								      lkey[0]),
								     le_key_k_offset
								     (version,
								      B_N_PDELIM_KEY
								      (tb->
								       CFL[0],
								       tb->
								       lkey[0]))
								     + temp_l);
							}

							/* Calculate new body, position in item and insert_size[0] */
							if (l_n > zeros_num) {
								body +=
								    (l_n -
								     zeros_num);
								zeros_num = 0;
							} else
								zeros_num -=
								    l_n;
							pos_in_item = 0;

							RFALSE
							    (comp_short_le_keys
							     (B_N_PKEY(tbS0, 0),
							      B_N_PKEY(tb->L[0],
								       B_NR_ITEMS
								       (tb->
									L[0]) -
								       1))
							     ||
							     !op_is_left_mergeable
							     (B_N_PKEY(tbS0, 0),
							      tbS0->b_size)
							     ||
							     !op_is_left_mergeable
							     (B_N_PDELIM_KEY
							      (tb->CFL[0],
							       tb->lkey[0]),
							      tbS0->b_size),
							     "PAP-12120: item must be merge-able with left neighboring item");
						} else {	/* only part of the appended item will be in L[0] */

							/* Calculate position in item for append in S[0] */
							pos_in_item -=
							    tb->lbytes;

							RFALSE(pos_in_item <= 0,
							       "PAP-12125: no place for paste. pos_in_item=%d",
							       pos_in_item);

							/* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
							leaf_shift_left(tb,
									tb->
									lnum[0],
									tb->
									lbytes);
						}
					}
				} else {	/* appended item will be in L[0] in whole */

					struct item_head *pasted;

					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 */
						/* then increment pos_in_item by the size of the last item in L[0] */
						pasted =
						    B_N_PITEM_HEAD(tb->L[0],
								   n - 1);
						if (is_direntry_le_ih(pasted))
							pos_in_item +=
							    ih_entry_count
							    (pasted);
						else
							pos_in_item +=
							    ih_item_len(pasted);
					}

					/* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
					ret_val =
					    leaf_shift_left(tb, tb->lnum[0],
							    tb->lbytes);
					/* Append to body of item in L[0] */
					bi.tb = tb;
					bi.bi_bh = tb->L[0];
					bi.bi_parent = tb->FL[0];
					bi.bi_position =
					    get_left_neighbor_position(tb, 0);
					leaf_paste_in_buffer(&bi,
							     n + item_pos -
							     ret_val,
							     pos_in_item,
							     tb->insert_size[0],
							     body, zeros_num);

					/* if appended item is directory, paste entry */
					pasted =
					    B_N_PITEM_HEAD(tb->L[0],
							   n + item_pos -
							   ret_val);
					if (is_direntry_le_ih(pasted))
						leaf_paste_entries(bi.bi_bh,
								   n +
								   item_pos -
								   ret_val,
								   pos_in_item,
								   1,
								   (struct
								    reiserfs_de_head
								    *)body,
								   body +
								   DEH_SIZE,
								   tb->
								   insert_size
								   [0]
						    );
					/* if appended item is indirect item, put unformatted node into un list */
					if (is_indirect_le_ih(pasted))
						set_ih_free_space(pasted, 0);
					tb->insert_size[0] = 0;
					zeros_num = 0;
				}
				break;
			default:	/* cases d and t */
				reiserfs_panic(tb->tb_sb,
					       "PAP-12130: balance_leaf: lnum > 0: unexpectable mode: %s(%d)",
					       (flag ==
						M_DELETE) ? "DELETE" : ((flag ==
									 M_CUT)
									? "CUT"
									:
									"UNKNOWN"),
					       flag);
			}
		} else {
			/* new item doesn't fall into L[0] */
			leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
		}
	}

	/* tb->lnum[0] > 0 */
	/* Calculate new item position */
	item_pos -= (tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0));

	if (tb->rnum[0] > 0) {
		/* shift rnum[0] items from S[0] to the right neighbor R[0] */
		n = B_NR_ITEMS(tbS0);
		switch (flag) {

		case M_INSERT:	/* insert item */
			if (n - tb->rnum[0] < item_pos) {	/* new item or its part falls to R[0] */
				if (item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1) {	/* part of new item falls into R[0] */
					loff_t old_key_comp, old_len,
					    r_zeros_number;
					const char *r_body;
					int version;
					loff_t offset;

					leaf_shift_right(tb, tb->rnum[0] - 1,
							 -1);

					version = ih_version(ih);
					/* Remember key component and item length */
					old_key_comp = le_ih_k_offset(ih);
					old_len = ih_item_len(ih);

					/* Calculate key component and item length to insert into R[0] */
					offset =
					    le_ih_k_offset(ih) +
					    ((old_len -
					      tb->
					      rbytes) << (is_indirect_le_ih(ih)
							  ? tb->tb_sb->
							  s_blocksize_bits -
							  UNFM_P_SHIFT : 0));
					set_le_ih_k_offset(ih, offset);
					put_ih_item_len(ih, tb->rbytes);
					/* Insert part of the item into R[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);
					if ((old_len - tb->rbytes) > zeros_num) {
						r_zeros_number = 0;
						r_body =
						    body + (old_len -
							    tb->rbytes) -
						    zeros_num;
					} else {
						r_body = body;
						r_zeros_number =
						    zeros_num - (old_len -
								 tb->rbytes);
						zeros_num -= r_zeros_number;
					}

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

					/* Replace right delimiting key by first key in R[0] */
					replace_key(tb, tb->CFR[0], tb->rkey[0],
						    tb->R[0], 0);

					/* Calculate key component and item length to insert into S[0] */
					set_le_ih_k_offset(ih, old_key_comp);
					put_ih_item_len(ih,
							old_len - tb->rbytes);

					tb->insert_size[0] -= tb->rbytes;

				} else {	/* whole new item falls into R[0] */

					/* Shift rnum[0]-1 items to R[0] */
					ret_val =
					    leaf_shift_right(tb,
							     tb->rnum[0] - 1,
							     tb->rbytes);
					/* Insert new item into R[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_insert_into_buf(&bi,
							     item_pos - n +
							     tb->rnum[0] - 1,
							     ih, body,
							     zeros_num);

					if (item_pos - n + tb->rnum[0] - 1 == 0) {
						replace_key(tb, tb->CFR[0],
							    tb->rkey[0],
							    tb->R[0], 0);

					}
					zeros_num = tb->insert_size[0] = 0;
				}
			} else {	/* new item or part of it doesn't fall into R[0] */

				leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
			}
			break;

		case M_PASTE:	/* append item */

			if (n - tb->rnum[0] <= item_pos) {	/* pasted item or part of it falls to R[0] */
				if (item_pos == n - tb->rnum[0] && tb->rbytes != -1) {	/* we must shift the part of the appended item */
					if (is_direntry_le_ih(B_N_PITEM_HEAD(tbS0, item_pos))) {	/* we append to directory item */
						int entry_count;

						RFALSE(zeros_num,
						       "PAP-12145: invalid parameter in case of a directory");
						entry_count =
						    I_ENTRY_COUNT(B_N_PITEM_HEAD
								  (tbS0,
								   item_pos));
						if (entry_count - tb->rbytes <
						    pos_in_item)
							/* new directory entry falls into R[0] */
						{
							int paste_entry_position;

							RFALSE(tb->rbytes - 1 >=
							       entry_count
							       || !tb->
							       insert_size[0],
							       "PAP-12150: no enough of entries to shift to R[0]: rbytes=%d, entry_count=%d",
							       tb->rbytes,
							       entry_count);
							/* Shift rnum[0]-1 items in whole. Shift rbytes-1 directory entries from directory item number rnum[0] */
							leaf_shift_right(tb,
									 tb->
									 rnum
									 [0],
									 tb->
									 rbytes
									 - 1);
							/* Paste given directory entry to directory item */
							paste_entry_position =
							    pos_in_item -
							    entry_count +
							    tb->rbytes - 1;
							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, 0,
							     paste_entry_position,
							     tb->insert_size[0],
							     body, zeros_num);
							/* paste entry */
							leaf_paste_entries(bi.
									   bi_bh,
									   0,
									   paste_entry_position,
									   1,
									   (struct
									    reiserfs_de_head
									    *)
									   body,
									   body
									   +
									   DEH_SIZE,
									   tb->
									   insert_size
									   [0]
							    );

							if (paste_entry_position
							    == 0) {
								/* change delimiting keys */
								replace_key(tb,
									    tb->
									    CFR
									    [0],
									    tb->
									    rkey
									    [0],
									    tb->
									    R
									    [0],
									    0);
							}

							tb->insert_size[0] = 0;
							pos_in_item++;
						} else {	/* new directory entry doesn't fall into R[0] */

							leaf_shift_right(tb,
									 tb->
									 rnum
									 [0],
									 tb->
									 rbytes);
						}
					} else {	/* regular object */

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

						/* Calculate number of bytes which must be shifted from appended item */
						if ((n_shift =
						     tb->rbytes -
						     tb->insert_size[0]) < 0)
							n_shift = 0;

						RFALSE(pos_in_item !=
						       ih_item_len
						       (B_N_PITEM_HEAD
							(tbS0, item_pos)),
						       "PAP-12155: invalid position to paste. ih_item_len=%d, pos_in_item=%d",
						       pos_in_item,
						       ih_item_len
						       (B_N_PITEM_HEAD
							(tbS0, item_pos)));

						leaf_shift_right(tb,
								 tb->rnum[0],
								 n_shift);
						/* Calculate number of bytes which must remain in body after appending to R[0] */
						if ((n_rem =
						     tb->insert_size[0] -
						     tb->rbytes) < 0)
							n_rem = 0;

						{
							int version;
							unsigned long temp_rem =
							    n_rem;

							version =
							    ih_version
							    (B_N_PITEM_HEAD
							     (tb->R[0], 0));
							if (is_indirect_le_key
							    (version,
							     B_N_PKEY(tb->R[0],
								      0))) {
								temp_rem =
								    n_rem <<
								    (tb->tb_sb->
								     s_blocksize_bits
								     -
								     UNFM_P_SHIFT);
							}
							set_le_key_k_offset
							    (version,
							     B_N_PKEY(tb->R[0],
								      0),
							     le_key_k_offset
							     (version,
							      B_N_PKEY(tb->R[0],
								       0)) +
							     temp_rem);
							set_le_key_k_offset
							    (version,
							     B_N_PDELIM_KEY(tb->
									    CFR
									    [0],
									    tb->
									    rkey
									    [0]),
							     le_key_k_offset
							     (version,
							      B_N_PDELIM_KEY
							      (tb->CFR[0],
							       tb->rkey[0])) +
							     temp_rem);
						}
/*		  k_offset (B_N_PKEY(tb->R[0],0)) += n_rem;
		  k_offset (B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])) += n_rem;*/
						do_balance_mark_internal_dirty
						    (tb, tb->CFR[0], 0);

						/* Append part of body into R[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);
						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);

						if (is_indirect_le_ih
						    (B_N_PITEM_HEAD
						     (tb->R[0], 0))) {
#if 0
							RFALSE(n_rem,
							       "PAP-12160: paste more than one unformatted node pointer");
#endif
							set_ih_free_space
							    (B_N_PITEM_HEAD
							     (tb->R[0], 0), 0);
						}
						tb->insert_size[0] = n_rem;
						if (!n_rem)
							pos_in_item++;
					}
				} else {	/* pasted item in whole falls into R[0] */

					struct item_head *pasted;

					ret_val =
					    leaf_shift_right(tb, tb->rnum[0],