lbalance.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>

/* these are used in do_balance.c */

/* leaf_move_items
   leaf_shift_left
   leaf_shift_right
   leaf_delete_items
   leaf_insert_into_buf
   leaf_paste_in_buffer
   leaf_cut_from_buffer
   leaf_paste_entries
   */

/* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */
static void leaf_copy_dir_entries(struct buffer_info *dest_bi,
				  struct buffer_head *source, int last_first,
				  int item_num, int from, int copy_count)
{
	struct buffer_head *dest = dest_bi->bi_bh;
	int item_num_in_dest;	/* either the number of target item,
				   or if we must create a new item,
				   the number of the item we will
				   create it next to */
	struct item_head *ih;
	struct reiserfs_de_head *deh;
	int copy_records_len;	/* length of all records in item to be copied */
	char *records;

	ih = B_N_PITEM_HEAD(source, item_num);

	RFALSE(!is_direntry_le_ih(ih), "vs-10000: item must be directory item");

	/* length of all record to be copied and first byte of the last of them */
	deh = B_I_DEH(source, ih);
	if (copy_count) {
		copy_records_len = (from ? deh_location(&(deh[from - 1])) :
				    ih_item_len(ih)) -
		    deh_location(&(deh[from + copy_count - 1]));
		records =
		    source->b_data + ih_location(ih) +
		    deh_location(&(deh[from + copy_count - 1]));
	} else {
		copy_records_len = 0;
		records = NULL;
	}

	/* when copy last to first, dest buffer can contain 0 items */
	item_num_in_dest =
	    (last_first ==
	     LAST_TO_FIRST) ? ((B_NR_ITEMS(dest)) ? 0 : -1) : (B_NR_ITEMS(dest)
							       - 1);

	/* if there are no items in dest or the first/last item in dest is not item of the same directory */
	if ((item_num_in_dest == -1) ||
	    (last_first == FIRST_TO_LAST && le_ih_k_offset(ih) == DOT_OFFSET) ||
	    (last_first == LAST_TO_FIRST
	     && comp_short_le_keys /*COMP_SHORT_KEYS */ (&ih->ih_key,
							 B_N_PKEY(dest,
								  item_num_in_dest))))
	{
		/* create new item in dest */
		struct item_head new_ih;

		/* form item header */
		memcpy(&new_ih.ih_key, &ih->ih_key, KEY_SIZE);
		put_ih_version(&new_ih, KEY_FORMAT_3_5);
		/* calculate item len */
		put_ih_item_len(&new_ih,
				DEH_SIZE * copy_count + copy_records_len);
		put_ih_entry_count(&new_ih, 0);

		if (last_first == LAST_TO_FIRST) {
			/* form key by the following way */
			if (from < I_ENTRY_COUNT(ih)) {
				set_le_ih_k_offset(&new_ih,
						   deh_offset(&(deh[from])));
				/*memcpy (&new_ih.ih_key.k_offset, &deh[from].deh_offset, SHORT_KEY_SIZE); */
			} else {
				/* no entries will be copied to this item in this function */
				set_le_ih_k_offset(&new_ih, U32_MAX);
				/* this item is not yet valid, but we want I_IS_DIRECTORY_ITEM to return 1 for it, so we -1 */
			}
			set_le_key_k_type(KEY_FORMAT_3_5, &(new_ih.ih_key),
					  TYPE_DIRENTRY);
		}

		/* insert item into dest buffer */
		leaf_insert_into_buf(dest_bi,
				     (last_first ==
				      LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest),
				     &new_ih, NULL, 0);
	} else {
		/* prepare space for entries */
		leaf_paste_in_buffer(dest_bi,
				     (last_first ==
				      FIRST_TO_LAST) ? (B_NR_ITEMS(dest) -
							1) : 0, MAX_US_INT,
				     DEH_SIZE * copy_count + copy_records_len,
				     records, 0);
	}

	item_num_in_dest =
	    (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0;

	leaf_paste_entries(dest_bi->bi_bh, item_num_in_dest,
			   (last_first ==
			    FIRST_TO_LAST) ? I_ENTRY_COUNT(B_N_PITEM_HEAD(dest,
									  item_num_in_dest))
			   : 0, copy_count, deh + from, records,
			   DEH_SIZE * copy_count + copy_records_len);
}

/* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or 
   part of it or nothing (see the return 0 below) from SOURCE to the end 
   (if last_first) or beginning (!last_first) of the DEST */
/* returns 1 if anything was copied, else 0 */
static int leaf_copy_boundary_item(struct buffer_info *dest_bi,
				   struct buffer_head *src, int last_first,
				   int bytes_or_entries)
{
	struct buffer_head *dest = dest_bi->bi_bh;
	int dest_nr_item, src_nr_item;	/* number of items in the source and destination buffers */
	struct item_head *ih;
	struct item_head *dih;

	dest_nr_item = B_NR_ITEMS(dest);

	if (last_first == FIRST_TO_LAST) {
		/* if ( DEST is empty or first item of SOURCE and last item of DEST are the items of different objects
		   or of different types ) then there is no need to treat this item differently from the other items
		   that we copy, so we return */
		ih = B_N_PITEM_HEAD(src, 0);
		dih = B_N_PITEM_HEAD(dest, dest_nr_item - 1);
		if (!dest_nr_item
		    || (!op_is_left_mergeable(&(ih->ih_key), src->b_size)))
			/* there is nothing to merge */
			return 0;

		RFALSE(!ih_item_len(ih),
		       "vs-10010: item can not have empty length");

		if (is_direntry_le_ih(ih)) {
			if (bytes_or_entries == -1)
				/* copy all entries to dest */
				bytes_or_entries = ih_entry_count(ih);
			leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST, 0, 0,
					      bytes_or_entries);
			return 1;
		}

		/* copy part of the body of the first item of SOURCE to the end of the body of the last item of the DEST
		   part defined by 'bytes_or_entries'; if bytes_or_entries == -1 copy whole body; don't create new item header
		 */
		if (bytes_or_entries == -1)
			bytes_or_entries = ih_item_len(ih);

#ifdef CONFIG_REISERFS_CHECK
		else {
			if (bytes_or_entries == ih_item_len(ih)
			    && is_indirect_le_ih(ih))
				if (get_ih_free_space(ih))
					reiserfs_panic(NULL,
						       "vs-10020: leaf_copy_boundary_item: "
						       "last unformatted node must be filled entirely (%h)",
						       ih);
		}
#endif

		/* merge first item (or its part) of src buffer with the last
		   item of dest buffer. Both are of the same file */
		leaf_paste_in_buffer(dest_bi,
				     dest_nr_item - 1, ih_item_len(dih),
				     bytes_or_entries, B_I_PITEM(src, ih), 0);

		if (is_indirect_le_ih(dih)) {
			RFALSE(get_ih_free_space(dih),
			       "vs-10030: merge to left: last unformatted node of non-last indirect item %h must have zerto free space",
			       ih);
			if (bytes_or_entries == ih_item_len(ih))
				set_ih_free_space(dih, get_ih_free_space(ih));
		}

		return 1;
	}

	/* copy boundary item to right (last_first == LAST_TO_FIRST) */

	/* ( DEST is empty or last item of SOURCE and first item of DEST
	   are the items of different object or of different types )
	 */
	src_nr_item = B_NR_ITEMS(src);
	ih = B_N_PITEM_HEAD(src, src_nr_item - 1);
	dih = B_N_PITEM_HEAD(dest, 0);

	if (!dest_nr_item || !op_is_left_mergeable(&(dih->ih_key), src->b_size))
		return 0;

	if (is_direntry_le_ih(ih)) {
		if (bytes_or_entries == -1)
			/* bytes_or_entries = entries number in last item body of SOURCE */
			bytes_or_entries = ih_entry_count(ih);

		leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
				      src_nr_item - 1,
				      ih_entry_count(ih) - bytes_or_entries,
				      bytes_or_entries);
		return 1;
	}

	/* copy part of the body of the last item of SOURCE to the begin of the body of the first item of the DEST;
	   part defined by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body; change first item key of the DEST;
	   don't create new item header
	 */

	RFALSE(is_indirect_le_ih(ih) && get_ih_free_space(ih),
	       "vs-10040: merge to right: last unformatted node of non-last indirect item must be filled entirely (%h)",
	       ih);

	if (bytes_or_entries == -1) {
		/* bytes_or_entries = length of last item body of SOURCE */
		bytes_or_entries = ih_item_len(ih);

		RFALSE(le_ih_k_offset(dih) !=
		       le_ih_k_offset(ih) + op_bytes_number(ih, src->b_size),
		       "vs-10050: items %h and %h do not match", ih, dih);

		/* change first item key of the DEST */
		set_le_ih_k_offset(dih, le_ih_k_offset(ih));

		/* item becomes non-mergeable */
		/* or mergeable if left item was */
		set_le_ih_k_type(dih, le_ih_k_type(ih));
	} else {
		/* merge to right only part of item */
		RFALSE(ih_item_len(ih) <= bytes_or_entries,
		       "vs-10060: no so much bytes %lu (needed %lu)",
		       (unsigned long)ih_item_len(ih),
		       (unsigned long)bytes_or_entries);

		/* change first item key of the DEST */
		if (is_direct_le_ih(dih)) {
			RFALSE(le_ih_k_offset(dih) <=
			       (unsigned long)bytes_or_entries,
			       "vs-10070: dih %h, bytes_or_entries(%d)", dih,
			       bytes_or_entries);
			set_le_ih_k_offset(dih,
					   le_ih_k_offset(dih) -
					   bytes_or_entries);
		} else {
			RFALSE(le_ih_k_offset(dih) <=
			       (bytes_or_entries / UNFM_P_SIZE) * dest->b_size,
			       "vs-10080: dih %h, bytes_or_entries(%d)",
			       dih,
			       (bytes_or_entries / UNFM_P_SIZE) * dest->b_size);
			set_le_ih_k_offset(dih,
					   le_ih_k_offset(dih) -
					   ((bytes_or_entries / UNFM_P_SIZE) *
					    dest->b_size));
		}
	}

	leaf_paste_in_buffer(dest_bi, 0, 0, bytes_or_entries,
			     B_I_PITEM(src,
				       ih) + ih_item_len(ih) - bytes_or_entries,
			     0);
	return 1;
}

/* copy cpy_mun items from buffer src to buffer dest
 * last_first == FIRST_TO_LAST means, that we copy cpy_num  items beginning from first-th item in src to tail of dest
 * last_first == LAST_TO_FIRST means, that we copy cpy_num  items beginning from first-th item in src to head of dest
 */
static void leaf_copy_items_entirely(struct buffer_info *dest_bi,
				     struct buffer_head *src, int last_first,
				     int first, int cpy_num)
{
	struct buffer_head *dest;
	int nr, free_space;
	int dest_before;
	int last_loc, last_inserted_loc, location;
	int i, j;
	struct block_head *blkh;
	struct item_head *ih;

	RFALSE(last_first != LAST_TO_FIRST && last_first != FIRST_TO_LAST,
	       "vs-10090: bad last_first parameter %d", last_first);
	RFALSE(B_NR_ITEMS(src) - first < cpy_num,
	       "vs-10100: too few items in source %d, required %d from %d",
	       B_NR_ITEMS(src), cpy_num, first);
	RFALSE(cpy_num < 0, "vs-10110: can not copy negative amount of items");
	RFALSE(!dest_bi, "vs-10120: can not copy negative amount of items");

	dest = dest_bi->bi_bh;

	RFALSE(!dest, "vs-10130: can not copy negative amount of items");

	if (cpy_num == 0)
		return;

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

	/* we will insert items before 0-th or nr-th item in dest buffer. It depends of last_first parameter */
	dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr;

	/* location of head of first new item */
	ih = B_N_PITEM_HEAD(dest, dest_before);

	RFALSE(blkh_free_space(blkh) < cpy_num * IH_SIZE,
	       "vs-10140: not enough free space for headers %d (needed %d)",
	       B_FREE_SPACE(dest), cpy_num * IH_SIZE);

	/* prepare space for headers */
	memmove(ih + cpy_num, ih, (nr - dest_before) * IH_SIZE);

	/* copy item headers */
	memcpy(ih, B_N_PITEM_HEAD(src, first), cpy_num * IH_SIZE);

	free_space -= (IH_SIZE * cpy_num);
	set_blkh_free_space(blkh, free_space);

	/* location of unmovable item */
	j = location = (dest_before == 0) ? dest->b_size : ih_location(ih - 1);
	for (i = dest_before; i < nr + cpy_num; i++) {
		location -= ih_item_len(ih + i - dest_before);
		put_ih_location(ih + i - dest_before, location);
	}

	/* prepare space for items */
	last_loc = ih_location(&(ih[nr + cpy_num - 1 - dest_before]));
	last_inserted_loc = ih_location(&(ih[cpy_num - 1]));

	/* check free space */
	RFALSE(free_space < j - last_inserted_loc,
	       "vs-10150: not enough free space for items %d (needed %d)",
	       free_space, j - last_inserted_loc);

	memmove(dest->b_data + last_loc,
		dest->b_data + last_loc + j - last_inserted_loc,
		last_inserted_loc - last_loc);

	/* copy items */
	memcpy(dest->b_data + last_inserted_loc,
	       B_N_PITEM(src, (first + cpy_num - 1)), j - last_inserted_loc);

	/* sizes, item number */
	set_blkh_nr_item(blkh, nr + cpy_num);
	set_blkh_free_space(blkh, free_space - (j - last_inserted_loc));

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

	if (dest_bi->bi_parent) {
		struct disk_child *t_dc;
		t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
		RFALSE(dc_block_number(t_dc) != dest->b_blocknr,
		       "vs-10160: block number in bh does not match to field in disk_child structure %lu and %lu",
		       (long unsigned)dest->b_blocknr,
		       (long unsigned)dc_block_number(t_dc));
		put_dc_size(t_dc,
			    dc_size(t_dc) + (j - last_inserted_loc +
					     IH_SIZE * cpy_num));

		do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
					       0);
	}
}

/* This function splits the (liquid) item into two items (useful when
   shifting part of an item into another node.) */
static void leaf_item_bottle(struct buffer_info *dest_bi,
			     struct buffer_head *src, int last_first,
			     int item_num, int cpy_bytes)
{
	struct buffer_head *dest = dest_bi->bi_bh;
	struct item_head *ih;

	RFALSE(cpy_bytes == -1,
	       "vs-10170: bytes == - 1 means: do not split item");

	if (last_first == FIRST_TO_LAST) {
		/* if ( if item in position item_num in buffer SOURCE is directory item ) */
		if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
			leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST,
					      item_num, 0, cpy_bytes);
		else {
			struct item_head n_ih;

			/* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST 
			   part defined by 'cpy_bytes'; create new item header; change old item_header (????);
			   n_ih = new item_header;
			 */
			memcpy(&n_ih, ih, IH_SIZE);
			put_ih_item_len(&n_ih, cpy_bytes);
			if (is_indirect_le_ih(ih)) {
				RFALSE(cpy_bytes == ih_item_len(ih)
				       && get_ih_free_space(ih),
				       "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)",
				       (long unsigned)get_ih_free_space(ih));
				set_ih_free_space(&n_ih, 0);
			}

			RFALSE(op_is_left_mergeable(&(ih->ih_key), src->b_size),
			       "vs-10190: bad mergeability of item %h", ih);
			n_ih.ih_version = ih->ih_version;	/* JDM Endian safe, both le */
			leaf_insert_into_buf(dest_bi, B_NR_ITEMS(dest), &n_ih,
					     B_N_PITEM(src, item_num), 0);
		}
	} else {
		/*  if ( if item in position item_num in buffer SOURCE is directory item ) */
		if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
			leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
					      item_num,
					      I_ENTRY_COUNT(ih) - cpy_bytes,
					      cpy_bytes);
		else {
			struct item_head n_ih;

			/* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST 
			   part defined by 'cpy_bytes'; create new item header;
			   n_ih = new item_header;
			 */
			memcpy(&n_ih, ih, SHORT_KEY_SIZE);

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