lbalance.c

linux 内核源代码

			if (is_direct_le_ih(ih)) {
				set_le_ih_k_offset(&n_ih,
						   le_ih_k_offset(ih) +
						   ih_item_len(ih) - cpy_bytes);
				set_le_ih_k_type(&n_ih, TYPE_DIRECT);
				set_ih_free_space(&n_ih, MAX_US_INT);
			} else {
				/* indirect item */
				RFALSE(!cpy_bytes && get_ih_free_space(ih),
				       "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended");
				set_le_ih_k_offset(&n_ih,
						   le_ih_k_offset(ih) +
						   (ih_item_len(ih) -
						    cpy_bytes) / UNFM_P_SIZE *
						   dest->b_size);
				set_le_ih_k_type(&n_ih, TYPE_INDIRECT);
				set_ih_free_space(&n_ih, get_ih_free_space(ih));
			}

			/* set item length */
			put_ih_item_len(&n_ih, cpy_bytes);

			n_ih.ih_version = ih->ih_version;	/* JDM Endian safe, both le */

			leaf_insert_into_buf(dest_bi, 0, &n_ih,
					     B_N_PITEM(src,
						       item_num) +
					     ih_item_len(ih) - cpy_bytes, 0);
		}
	}
}

/* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST.
   If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST.
   From last item copy cpy_num bytes for regular item and cpy_num directory entries for
   directory item. */
static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src,
			   int last_first, int cpy_num, int cpy_bytes)
{
	struct buffer_head *dest;
	int pos, i, src_nr_item, bytes;

	dest = dest_bi->bi_bh;
	RFALSE(!dest || !src, "vs-10210: !dest || !src");
	RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
	       "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST");
	RFALSE(B_NR_ITEMS(src) < cpy_num,
	       "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src),
	       cpy_num);
	RFALSE(cpy_num < 0, "vs-10240: cpy_num < 0 (%d)", cpy_num);

	if (cpy_num == 0)
		return 0;

	if (last_first == FIRST_TO_LAST) {
		/* copy items to left */
		pos = 0;
		if (cpy_num == 1)
			bytes = cpy_bytes;
		else
			bytes = -1;

		/* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */
		i = leaf_copy_boundary_item(dest_bi, src, FIRST_TO_LAST, bytes);
		cpy_num -= i;
		if (cpy_num == 0)
			return i;
		pos += i;
		if (cpy_bytes == -1)
			/* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */
			leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
						 pos, cpy_num);
		else {
			/* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */
			leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
						 pos, cpy_num - 1);

			/* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */
			leaf_item_bottle(dest_bi, src, FIRST_TO_LAST,
					 cpy_num + pos - 1, cpy_bytes);
		}
	} else {
		/* copy items to right */
		src_nr_item = B_NR_ITEMS(src);
		if (cpy_num == 1)
			bytes = cpy_bytes;
		else
			bytes = -1;

		/* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */
		i = leaf_copy_boundary_item(dest_bi, src, LAST_TO_FIRST, bytes);

		cpy_num -= i;
		if (cpy_num == 0)
			return i;

		pos = src_nr_item - cpy_num - i;
		if (cpy_bytes == -1) {
			/* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */
			leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
						 pos, cpy_num);
		} else {
			/* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */
			leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
						 pos + 1, cpy_num - 1);

			/* copy part of the item which number is pos to the begin of the DEST */
			leaf_item_bottle(dest_bi, src, LAST_TO_FIRST, pos,
					 cpy_bytes);
		}
	}
	return i;
}

/* there are types of coping: from S[0] to L[0], from S[0] to R[0],
   from R[0] to L[0]. for each of these we have to define parent and
   positions of destination and source buffers */
static void leaf_define_dest_src_infos(int shift_mode, struct tree_balance *tb,
				       struct buffer_info *dest_bi,
				       struct buffer_info *src_bi,
				       int *first_last,
				       struct buffer_head *Snew)
{
	memset(dest_bi, 0, sizeof(struct buffer_info));
	memset(src_bi, 0, sizeof(struct buffer_info));

	/* define dest, src, dest parent, dest position */
	switch (shift_mode) {
	case LEAF_FROM_S_TO_L:	/* it is used in leaf_shift_left */
		src_bi->tb = tb;
		src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
		src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
		src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);	/* src->b_item_order */
		dest_bi->tb = tb;
		dest_bi->bi_bh = tb->L[0];
		dest_bi->bi_parent = tb->FL[0];
		dest_bi->bi_position = get_left_neighbor_position(tb, 0);
		*first_last = FIRST_TO_LAST;
		break;

	case LEAF_FROM_S_TO_R:	/* it is used in leaf_shift_right */
		src_bi->tb = tb;
		src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
		src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
		src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
		dest_bi->tb = tb;
		dest_bi->bi_bh = tb->R[0];
		dest_bi->bi_parent = tb->FR[0];
		dest_bi->bi_position = get_right_neighbor_position(tb, 0);
		*first_last = LAST_TO_FIRST;
		break;

	case LEAF_FROM_R_TO_L:	/* it is used in balance_leaf_when_delete */
		src_bi->tb = tb;
		src_bi->bi_bh = tb->R[0];
		src_bi->bi_parent = tb->FR[0];
		src_bi->bi_position = get_right_neighbor_position(tb, 0);
		dest_bi->tb = tb;
		dest_bi->bi_bh = tb->L[0];
		dest_bi->bi_parent = tb->FL[0];
		dest_bi->bi_position = get_left_neighbor_position(tb, 0);
		*first_last = FIRST_TO_LAST;
		break;

	case LEAF_FROM_L_TO_R:	/* it is used in balance_leaf_when_delete */
		src_bi->tb = tb;
		src_bi->bi_bh = tb->L[0];
		src_bi->bi_parent = tb->FL[0];
		src_bi->bi_position = get_left_neighbor_position(tb, 0);
		dest_bi->tb = tb;
		dest_bi->bi_bh = tb->R[0];
		dest_bi->bi_parent = tb->FR[0];
		dest_bi->bi_position = get_right_neighbor_position(tb, 0);
		*first_last = LAST_TO_FIRST;
		break;

	case LEAF_FROM_S_TO_SNEW:
		src_bi->tb = tb;
		src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
		src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
		src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
		dest_bi->tb = tb;
		dest_bi->bi_bh = Snew;
		dest_bi->bi_parent = NULL;
		dest_bi->bi_position = 0;
		*first_last = LAST_TO_FIRST;
		break;

	default:
		reiserfs_panic(NULL,
			       "vs-10250: leaf_define_dest_src_infos: shift type is unknown (%d)",
			       shift_mode);
	}
	RFALSE(src_bi->bi_bh == 0 || dest_bi->bi_bh == 0,
	       "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
	       shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
}

/* copy mov_num items and mov_bytes of the (mov_num-1)th item to
   neighbor. Delete them from source */
int leaf_move_items(int shift_mode, struct tree_balance *tb, int mov_num,
		    int mov_bytes, struct buffer_head *Snew)
{
	int ret_value;
	struct buffer_info dest_bi, src_bi;
	int first_last;

	leaf_define_dest_src_infos(shift_mode, tb, &dest_bi, &src_bi,
				   &first_last, Snew);

	ret_value =
	    leaf_copy_items(&dest_bi, src_bi.bi_bh, first_last, mov_num,
			    mov_bytes);

	leaf_delete_items(&src_bi, first_last,
			  (first_last ==
			   FIRST_TO_LAST) ? 0 : (B_NR_ITEMS(src_bi.bi_bh) -
						 mov_num), mov_num, mov_bytes);

	return ret_value;
}

/* Shift shift_num items (and shift_bytes of last shifted item if shift_bytes != -1)
   from S[0] to L[0] and replace the delimiting key */
int leaf_shift_left(struct tree_balance *tb, int shift_num, int shift_bytes)
{
	struct buffer_head *S0 = PATH_PLAST_BUFFER(tb->tb_path);
	int i;

	/* move shift_num (and shift_bytes bytes) items from S[0] to left neighbor L[0] */
	i = leaf_move_items(LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, NULL);

	if (shift_num) {
		if (B_NR_ITEMS(S0) == 0) {	/* number of items in S[0] == 0 */

			RFALSE(shift_bytes != -1,
			       "vs-10270: S0 is empty now, but shift_bytes != -1 (%d)",
			       shift_bytes);
#ifdef CONFIG_REISERFS_CHECK
			if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) {
				print_cur_tb("vs-10275");
				reiserfs_panic(tb->tb_sb,
					       "vs-10275: leaf_shift_left: balance condition corrupted (%c)",
					       tb->tb_mode);
			}
#endif

			if (PATH_H_POSITION(tb->tb_path, 1) == 0)
				replace_key(tb, tb->CFL[0], tb->lkey[0],
					    PATH_H_PPARENT(tb->tb_path, 0), 0);

		} else {
			/* replace lkey in CFL[0] by 0-th key from S[0]; */
			replace_key(tb, tb->CFL[0], tb->lkey[0], S0, 0);

			RFALSE((shift_bytes != -1 &&
				!(is_direntry_le_ih(B_N_PITEM_HEAD(S0, 0))
				  && !I_ENTRY_COUNT(B_N_PITEM_HEAD(S0, 0)))) &&
			       (!op_is_left_mergeable
				(B_N_PKEY(S0, 0), S0->b_size)),
			       "vs-10280: item must be mergeable");
		}
	}

	return i;
}

/* CLEANING STOPPED HERE */

/* Shift shift_num (shift_bytes) items from S[0] to the right neighbor, and replace the delimiting key */
int leaf_shift_right(struct tree_balance *tb, int shift_num, int shift_bytes)
{
	//  struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path);
	int ret_value;

	/* move shift_num (and shift_bytes) items from S[0] to right neighbor R[0] */
	ret_value =
	    leaf_move_items(LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, NULL);

	/* replace rkey in CFR[0] by the 0-th key from R[0] */
	if (shift_num) {
		replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);

	}

	return ret_value;
}

static void leaf_delete_items_entirely(struct buffer_info *bi,
				       int first, int del_num);
/*  If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR.
    If not. 
    If last_first == 0. Starting from position 'first' delete del_num-1 items in whole. Delete part of body of
    the first item. Part defined by del_bytes. Don't delete first item header
    If last_first == 1. Starting from position 'first+1' delete del_num-1 items in whole. Delete part of body of
    the last item . Part defined by del_bytes. Don't delete last item header.
*/
void leaf_delete_items(struct buffer_info *cur_bi, int last_first,
		       int first, int del_num, int del_bytes)
{
	struct buffer_head *bh;
	int item_amount = B_NR_ITEMS(bh = cur_bi->bi_bh);

	RFALSE(!bh, "10155: bh is not defined");
	RFALSE(del_num < 0, "10160: del_num can not be < 0. del_num==%d",
	       del_num);
	RFALSE(first < 0
	       || first + del_num > item_amount,
	       "10165: invalid number of first item to be deleted (%d) or "
	       "no so much items (%d) to delete (only %d)", first,
	       first + del_num, item_amount);

	if (del_num == 0)
		return;

	if (first == 0 && del_num == item_amount && del_bytes == -1) {
		make_empty_node(cur_bi);
		do_balance_mark_leaf_dirty(cur_bi->tb, bh, 0);
		return;
	}

	if (del_bytes == -1)
		/* delete del_num items beginning from item in position first */
		leaf_delete_items_entirely(cur_bi, first, del_num);
	else {
		if (last_first == FIRST_TO_LAST) {
			/* delete del_num-1 items beginning from item in position first  */
			leaf_delete_items_entirely(cur_bi, first, del_num - 1);

			/* delete the part of the first item of the bh
			   do not delete item header
			 */
			leaf_cut_from_buffer(cur_bi, 0, 0, del_bytes);
		} else {
			struct item_head *ih;
			int len;

			/* delete del_num-1 items beginning from item in position first+1  */
			leaf_delete_items_entirely(cur_bi, first + 1,
						   del_num - 1);

			if (is_direntry_le_ih
			    (ih = B_N_PITEM_HEAD(bh, B_NR_ITEMS(bh) - 1)))
				/* the last item is directory  */
				/* len = numbers of directory entries in this item */
				len = ih_entry_count(ih);
			else
				/* len = body len of item */
				len = ih_item_len(ih);

			/* delete the part of the last item of the bh 
			   do not delete item header
			 */
			leaf_cut_from_buffer(cur_bi, B_NR_ITEMS(bh) - 1,
					     len - del_bytes, del_bytes);
		}
	}
}

/* insert item into the leaf node in position before */
void leaf_insert_into_buf(struct buffer_info *bi, int before,
			  struct item_head *inserted_item_ih,
			  const char *inserted_item_body, int zeros_number)
{
	struct buffer_head *bh = bi->bi_bh;
	int nr, free_space;
	struct block_head *blkh;
	struct item_head *ih;
	int i;
	int last_loc, unmoved_loc;
	char *to;

	blkh = B_BLK_HEAD(bh);
	nr = blkh_nr_item(blkh);
	free_space = blkh_free_space(blkh);

	/* check free space */
	RFALSE(free_space < ih_item_len(inserted_item_ih) + IH_SIZE,
	       "vs-10170: not enough free space in block %z, new item %h",
	       bh, inserted_item_ih);
	RFALSE(zeros_number > ih_item_len(inserted_item_ih),
	       "vs-10172: zero number == %d, item length == %d",
	       zeros_number, ih_item_len(inserted_item_ih));

	/* get item new item must be inserted before */
	ih = B_N_PITEM_HEAD(bh, before);

	/* prepare space for the body of new item */
	last_loc = nr ? ih_location(&(ih[nr - before - 1])) : bh->b_size;
	unmoved_loc = before ? ih_location(ih - 1) : bh->b_size;

	memmove(bh->b_data + last_loc - ih_item_len(inserted_item_ih),
		bh->b_data + last_loc, unmoved_loc - last_loc);

	to = bh->b_data + unmoved_loc - ih_item_len(inserted_item_ih);
	memset(to, 0, zeros_number);
	to += zeros_number;

	/* copy body to prepared space */
	if (inserted_item_body)
		memmove(to, inserted_item_body,
			ih_item_len(inserted_item_ih) - zeros_number);
	else
		memset(to, '\0', ih_item_len(inserted_item_ih) - zeros_number);

	/* insert item header */
	memmove(ih + 1, ih, IH_SIZE * (nr - before));
	memmove(ih, inserted_item_ih, IH_SIZE);

	/* change locations */
	for (i = before; i < nr + 1; i++) {
		unmoved_loc -= ih_item_len(&(ih[i - before]));
		put_ih_location(&(ih[i - before]), unmoved_loc);
	}

	/* sizes, free space, item number */
	set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
	set_blkh_free_space(blkh,
			    free_space - (IH_SIZE +
					  ih_item_len(inserted_item_ih)));
	do_balance_mark_leaf_dirty(bi->tb, bh, 1);

	if (bi->bi_parent) {
		struct disk_child *t_dc;
		t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
		put_dc_size(t_dc,
			    dc_size(t_dc) + (IH_SIZE +
					     ih_item_len(inserted_item_ih)));
		do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
	}
}

/* paste paste_size bytes to affected_item_num-th item.