ibalance.c

linux 内核源代码

/*
 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
 */

#include <asm/uaccess.h>
#include <linux/string.h>
#include <linux/time.h>
#include <linux/reiserfs_fs.h>
#include <linux/buffer_head.h>

/* this is one and only function that is used outside (do_balance.c) */
int balance_internal(struct tree_balance *,
		     int, int, struct item_head *, struct buffer_head **);

/* modes of internal_shift_left, internal_shift_right and internal_insert_childs */
#define INTERNAL_SHIFT_FROM_S_TO_L 0
#define INTERNAL_SHIFT_FROM_R_TO_S 1
#define INTERNAL_SHIFT_FROM_L_TO_S 2
#define INTERNAL_SHIFT_FROM_S_TO_R 3
#define INTERNAL_INSERT_TO_S 4
#define INTERNAL_INSERT_TO_L 5
#define INTERNAL_INSERT_TO_R 6

static void internal_define_dest_src_infos(int shift_mode,
					   struct tree_balance *tb,
					   int h,
					   struct buffer_info *dest_bi,
					   struct buffer_info *src_bi,
					   int *d_key, struct buffer_head **cf)
{
	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 INTERNAL_SHIFT_FROM_S_TO_L:	/* used in internal_shift_left */
		src_bi->tb = tb;
		src_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
		src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
		src_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
		dest_bi->tb = tb;
		dest_bi->bi_bh = tb->L[h];
		dest_bi->bi_parent = tb->FL[h];
		dest_bi->bi_position = get_left_neighbor_position(tb, h);
		*d_key = tb->lkey[h];
		*cf = tb->CFL[h];
		break;
	case INTERNAL_SHIFT_FROM_L_TO_S:
		src_bi->tb = tb;
		src_bi->bi_bh = tb->L[h];
		src_bi->bi_parent = tb->FL[h];
		src_bi->bi_position = get_left_neighbor_position(tb, h);
		dest_bi->tb = tb;
		dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
		dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
		dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);	/* dest position is analog of dest->b_item_order */
		*d_key = tb->lkey[h];
		*cf = tb->CFL[h];
		break;

	case INTERNAL_SHIFT_FROM_R_TO_S:	/* used in internal_shift_left */
		src_bi->tb = tb;
		src_bi->bi_bh = tb->R[h];
		src_bi->bi_parent = tb->FR[h];
		src_bi->bi_position = get_right_neighbor_position(tb, h);
		dest_bi->tb = tb;
		dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
		dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
		dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
		*d_key = tb->rkey[h];
		*cf = tb->CFR[h];
		break;

	case INTERNAL_SHIFT_FROM_S_TO_R:
		src_bi->tb = tb;
		src_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
		src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
		src_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
		dest_bi->tb = tb;
		dest_bi->bi_bh = tb->R[h];
		dest_bi->bi_parent = tb->FR[h];
		dest_bi->bi_position = get_right_neighbor_position(tb, h);
		*d_key = tb->rkey[h];
		*cf = tb->CFR[h];
		break;

	case INTERNAL_INSERT_TO_L:
		dest_bi->tb = tb;
		dest_bi->bi_bh = tb->L[h];
		dest_bi->bi_parent = tb->FL[h];
		dest_bi->bi_position = get_left_neighbor_position(tb, h);
		break;

	case INTERNAL_INSERT_TO_S:
		dest_bi->tb = tb;
		dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
		dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
		dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
		break;

	case INTERNAL_INSERT_TO_R:
		dest_bi->tb = tb;
		dest_bi->bi_bh = tb->R[h];
		dest_bi->bi_parent = tb->FR[h];
		dest_bi->bi_position = get_right_neighbor_position(tb, h);
		break;

	default:
		reiserfs_panic(tb->tb_sb,
			       "internal_define_dest_src_infos: shift type is unknown (%d)",
			       shift_mode);
	}
}

/* Insert count node pointers into buffer cur before position to + 1.
 * Insert count items into buffer cur before position to.
 * Items and node pointers are specified by inserted and bh respectively.
 */
static void internal_insert_childs(struct buffer_info *cur_bi,
				   int to, int count,
				   struct item_head *inserted,
				   struct buffer_head **bh)
{
	struct buffer_head *cur = cur_bi->bi_bh;
	struct block_head *blkh;
	int nr;
	struct reiserfs_key *ih;
	struct disk_child new_dc[2];
	struct disk_child *dc;
	int i;

	if (count <= 0)
		return;

	blkh = B_BLK_HEAD(cur);
	nr = blkh_nr_item(blkh);

	RFALSE(count > 2, "too many children (%d) are to be inserted", count);
	RFALSE(B_FREE_SPACE(cur) < count * (KEY_SIZE + DC_SIZE),
	       "no enough free space (%d), needed %d bytes",
	       B_FREE_SPACE(cur), count * (KEY_SIZE + DC_SIZE));

	/* prepare space for count disk_child */
	dc = B_N_CHILD(cur, to + 1);

	memmove(dc + count, dc, (nr + 1 - (to + 1)) * DC_SIZE);

	/* copy to_be_insert disk children */
	for (i = 0; i < count; i++) {
		put_dc_size(&(new_dc[i]),
			    MAX_CHILD_SIZE(bh[i]) - B_FREE_SPACE(bh[i]));
		put_dc_block_number(&(new_dc[i]), bh[i]->b_blocknr);
	}
	memcpy(dc, new_dc, DC_SIZE * count);

	/* prepare space for count items  */
	ih = B_N_PDELIM_KEY(cur, ((to == -1) ? 0 : to));

	memmove(ih + count, ih,
		(nr - to) * KEY_SIZE + (nr + 1 + count) * DC_SIZE);

	/* copy item headers (keys) */
	memcpy(ih, inserted, KEY_SIZE);
	if (count > 1)
		memcpy(ih + 1, inserted + 1, KEY_SIZE);

	/* sizes, item number */
	set_blkh_nr_item(blkh, blkh_nr_item(blkh) + count);
	set_blkh_free_space(blkh,
			    blkh_free_space(blkh) - count * (DC_SIZE +
							     KEY_SIZE));

	do_balance_mark_internal_dirty(cur_bi->tb, cur, 0);

	/*&&&&&&&&&&&&&&&&&&&&&&&& */
	check_internal(cur);
	/*&&&&&&&&&&&&&&&&&&&&&&&& */

	if (cur_bi->bi_parent) {
		struct disk_child *t_dc =
		    B_N_CHILD(cur_bi->bi_parent, cur_bi->bi_position);
		put_dc_size(t_dc,
			    dc_size(t_dc) + (count * (DC_SIZE + KEY_SIZE)));
		do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent,
					       0);

		/*&&&&&&&&&&&&&&&&&&&&&&&& */
		check_internal(cur_bi->bi_parent);
		/*&&&&&&&&&&&&&&&&&&&&&&&& */
	}

}

/* Delete del_num items and node pointers from buffer cur starting from *
 * the first_i'th item and first_p'th pointers respectively.		*/
static void internal_delete_pointers_items(struct buffer_info *cur_bi,
					   int first_p,
					   int first_i, int del_num)
{
	struct buffer_head *cur = cur_bi->bi_bh;
	int nr;
	struct block_head *blkh;
	struct reiserfs_key *key;
	struct disk_child *dc;

	RFALSE(cur == NULL, "buffer is 0");
	RFALSE(del_num < 0,
	       "negative number of items (%d) can not be deleted", del_num);
	RFALSE(first_p < 0 || first_p + del_num > B_NR_ITEMS(cur) + 1
	       || first_i < 0,
	       "first pointer order (%d) < 0 or "
	       "no so many pointers (%d), only (%d) or "
	       "first key order %d < 0", first_p, first_p + del_num,
	       B_NR_ITEMS(cur) + 1, first_i);
	if (del_num == 0)
		return;

	blkh = B_BLK_HEAD(cur);
	nr = blkh_nr_item(blkh);

	if (first_p == 0 && del_num == nr + 1) {
		RFALSE(first_i != 0,
		       "1st deleted key must have order 0, not %d", first_i);
		make_empty_node(cur_bi);
		return;
	}

	RFALSE(first_i + del_num > B_NR_ITEMS(cur),
	       "first_i = %d del_num = %d "
	       "no so many keys (%d) in the node (%b)(%z)",
	       first_i, del_num, first_i + del_num, cur, cur);

	/* deleting */
	dc = B_N_CHILD(cur, first_p);

	memmove(dc, dc + del_num, (nr + 1 - first_p - del_num) * DC_SIZE);
	key = B_N_PDELIM_KEY(cur, first_i);
	memmove(key, key + del_num,
		(nr - first_i - del_num) * KEY_SIZE + (nr + 1 -
						       del_num) * DC_SIZE);

	/* sizes, item number */
	set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
	set_blkh_free_space(blkh,
			    blkh_free_space(blkh) +
			    (del_num * (KEY_SIZE + DC_SIZE)));

	do_balance_mark_internal_dirty(cur_bi->tb, cur, 0);
	/*&&&&&&&&&&&&&&&&&&&&&&& */
	check_internal(cur);
	/*&&&&&&&&&&&&&&&&&&&&&&& */

	if (cur_bi->bi_parent) {
		struct disk_child *t_dc;
		t_dc = B_N_CHILD(cur_bi->bi_parent, cur_bi->bi_position);
		put_dc_size(t_dc,
			    dc_size(t_dc) - (del_num * (KEY_SIZE + DC_SIZE)));

		do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent,
					       0);
		/*&&&&&&&&&&&&&&&&&&&&&&&& */
		check_internal(cur_bi->bi_parent);
		/*&&&&&&&&&&&&&&&&&&&&&&&& */
	}
}

/* delete n node pointers and items starting from given position */
static void internal_delete_childs(struct buffer_info *cur_bi, int from, int n)
{
	int i_from;

	i_from = (from == 0) ? from : from - 1;

	/* delete n pointers starting from `from' position in CUR;
	   delete n keys starting from 'i_from' position in CUR;
	 */
	internal_delete_pointers_items(cur_bi, from, i_from, n);
}

/* copy cpy_num node pointers and cpy_num - 1 items from buffer src to buffer dest
* last_first == FIRST_TO_LAST means, that we copy first items from src to tail of dest
 * last_first == LAST_TO_FIRST means, that we copy last items from src to head of dest 
 */
static void internal_copy_pointers_items(struct buffer_info *dest_bi,
					 struct buffer_head *src,
					 int last_first, int cpy_num)
{
	/* ATTENTION! Number of node pointers in DEST is equal to number of items in DEST *
	 * as delimiting key have already inserted to buffer dest.*/
	struct buffer_head *dest = dest_bi->bi_bh;
	int nr_dest, nr_src;
	int dest_order, src_order;
	struct block_head *blkh;
	struct reiserfs_key *key;
	struct disk_child *dc;

	nr_src = B_NR_ITEMS(src);

	RFALSE(dest == NULL || src == NULL,
	       "src (%p) or dest (%p) buffer is 0", src, dest);
	RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
	       "invalid last_first parameter (%d)", last_first);
	RFALSE(nr_src < cpy_num - 1,
	       "no so many items (%d) in src (%d)", cpy_num, nr_src);
	RFALSE(cpy_num < 0, "cpy_num less than 0 (%d)", cpy_num);
	RFALSE(cpy_num - 1 + B_NR_ITEMS(dest) > (int)MAX_NR_KEY(dest),
	       "cpy_num (%d) + item number in dest (%d) can not be > MAX_NR_KEY(%d)",
	       cpy_num, B_NR_ITEMS(dest), MAX_NR_KEY(dest));

	if (cpy_num == 0)
		return;

	/* coping */
	blkh = B_BLK_HEAD(dest);
	nr_dest = blkh_nr_item(blkh);

	/*dest_order = (last_first == LAST_TO_FIRST) ? 0 : nr_dest; */
	/*src_order = (last_first == LAST_TO_FIRST) ? (nr_src - cpy_num + 1) : 0; */
	(last_first == LAST_TO_FIRST) ? (dest_order = 0, src_order =
					 nr_src - cpy_num + 1) : (dest_order =
								  nr_dest,
								  src_order =
								  0);

	/* prepare space for cpy_num pointers */
	dc = B_N_CHILD(dest, dest_order);

	memmove(dc + cpy_num, dc, (nr_dest - dest_order) * DC_SIZE);

	/* insert pointers */
	memcpy(dc, B_N_CHILD(src, src_order), DC_SIZE * cpy_num);

	/* prepare space for cpy_num - 1 item headers */
	key = B_N_PDELIM_KEY(dest, dest_order);
	memmove(key + cpy_num - 1, key,
		KEY_SIZE * (nr_dest - dest_order) + DC_SIZE * (nr_dest +
							       cpy_num));

	/* insert headers */
	memcpy(key, B_N_PDELIM_KEY(src, src_order), KEY_SIZE * (cpy_num - 1));

	/* sizes, item number */
	set_blkh_nr_item(blkh, blkh_nr_item(blkh) + (cpy_num - 1));
	set_blkh_free_space(blkh,
			    blkh_free_space(blkh) - (KEY_SIZE * (cpy_num - 1) +
						     DC_SIZE * cpy_num));

	do_balance_mark_internal_dirty(dest_bi->tb, dest, 0);

	/*&&&&&&&&&&&&&&&&&&&&&&&& */
	check_internal(dest);
	/*&&&&&&&&&&&&&&&&&&&&&&&& */

	if (dest_bi->bi_parent) {
		struct disk_child *t_dc;
		t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
		put_dc_size(t_dc,
			    dc_size(t_dc) + (KEY_SIZE * (cpy_num - 1) +
					     DC_SIZE * cpy_num));

		do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
					       0);
		/*&&&&&&&&&&&&&&&&&&&&&&&& */
		check_internal(dest_bi->bi_parent);
		/*&&&&&&&&&&&&&&&&&&&&&&&& */