lbalance.c

linux 内核源代码

   When item is a directory, this only prepare space for new entries */
void leaf_paste_in_buffer(struct buffer_info *bi, int affected_item_num,
			  int pos_in_item, int paste_size,
			  const char *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;

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

	/* check free space */
	RFALSE(free_space < paste_size,
	       "vs-10175: not enough free space: needed %d, available %d",
	       paste_size, free_space);

#ifdef CONFIG_REISERFS_CHECK
	if (zeros_number > paste_size) {
		print_cur_tb("10177");
		reiserfs_panic(NULL,
			       "vs-10177: leaf_paste_in_buffer: ero number == %d, paste_size == %d",
			       zeros_number, paste_size);
	}
#endif				/* CONFIG_REISERFS_CHECK */

	/* item to be appended */
	ih = B_N_PITEM_HEAD(bh, affected_item_num);

	last_loc = ih_location(&(ih[nr - affected_item_num - 1]));
	unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size;

	/* prepare space */
	memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
		unmoved_loc - last_loc);

	/* change locations */
	for (i = affected_item_num; i < nr; i++)
		put_ih_location(&(ih[i - affected_item_num]),
				ih_location(&(ih[i - affected_item_num])) -
				paste_size);

	if (body) {
		if (!is_direntry_le_ih(ih)) {
			if (!pos_in_item) {
				/* shift data to right */
				memmove(bh->b_data + ih_location(ih) +
					paste_size,
					bh->b_data + ih_location(ih),
					ih_item_len(ih));
				/* paste data in the head of item */
				memset(bh->b_data + ih_location(ih), 0,
				       zeros_number);
				memcpy(bh->b_data + ih_location(ih) +
				       zeros_number, body,
				       paste_size - zeros_number);
			} else {
				memset(bh->b_data + unmoved_loc - paste_size, 0,
				       zeros_number);
				memcpy(bh->b_data + unmoved_loc - paste_size +
				       zeros_number, body,
				       paste_size - zeros_number);
			}
		}
	} else
		memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size);

	put_ih_item_len(ih, ih_item_len(ih) + paste_size);

	/* change free space */
	set_blkh_free_space(blkh, free_space - paste_size);

	do_balance_mark_leaf_dirty(bi->tb, bh, 0);

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

/* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
   does not have free space, so it moves DEHs and remaining records as
   necessary. Return value is size of removed part of directory item
   in bytes. */
static int leaf_cut_entries(struct buffer_head *bh,
			    struct item_head *ih, int from, int del_count)
{
	char *item;
	struct reiserfs_de_head *deh;
	int prev_record_offset;	/* offset of record, that is (from-1)th */
	char *prev_record;	/* */
	int cut_records_len;	/* length of all removed records */
	int i;

	/* make sure, that item is directory and there are enough entries to
	   remove */
	RFALSE(!is_direntry_le_ih(ih), "10180: item is not directory item");
	RFALSE(I_ENTRY_COUNT(ih) < from + del_count,
	       "10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d",
	       I_ENTRY_COUNT(ih), from, del_count);

	if (del_count == 0)
		return 0;

	/* first byte of item */
	item = bh->b_data + ih_location(ih);

	/* entry head array */
	deh = B_I_DEH(bh, ih);

	/* first byte of remaining entries, those are BEFORE cut entries
	   (prev_record) and length of all removed records (cut_records_len) */
	prev_record_offset =
	    (from ? deh_location(&(deh[from - 1])) : ih_item_len(ih));
	cut_records_len = prev_record_offset /*from_record */  -
	    deh_location(&(deh[from + del_count - 1]));
	prev_record = item + prev_record_offset;

	/* adjust locations of remaining entries */
	for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i--)
		put_deh_location(&(deh[i]),
				 deh_location(&deh[i]) -
				 (DEH_SIZE * del_count));

	for (i = 0; i < from; i++)
		put_deh_location(&(deh[i]),
				 deh_location(&deh[i]) - (DEH_SIZE * del_count +
							  cut_records_len));

	put_ih_entry_count(ih, ih_entry_count(ih) - del_count);

	/* shift entry head array and entries those are AFTER removed entries */
	memmove((char *)(deh + from),
		deh + from + del_count,
		prev_record - cut_records_len - (char *)(deh + from +
							 del_count));

	/* shift records, those are BEFORE removed entries */
	memmove(prev_record - cut_records_len - DEH_SIZE * del_count,
		prev_record, item + ih_item_len(ih) - prev_record);

	return DEH_SIZE * del_count + cut_records_len;
}

/*  when cut item is part of regular file
        pos_in_item - first byte that must be cut
        cut_size - number of bytes to be cut beginning from pos_in_item
 
   when cut item is part of directory
        pos_in_item - number of first deleted entry
        cut_size - count of deleted entries
    */
void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num,
			  int pos_in_item, int cut_size)
{
	int nr;
	struct buffer_head *bh = bi->bi_bh;
	struct block_head *blkh;
	struct item_head *ih;
	int last_loc, unmoved_loc;
	int i;

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

	/* item head of truncated item */
	ih = B_N_PITEM_HEAD(bh, cut_item_num);

	if (is_direntry_le_ih(ih)) {
		/* first cut entry () */
		cut_size = leaf_cut_entries(bh, ih, pos_in_item, cut_size);
		if (pos_in_item == 0) {
			/* change key */
			RFALSE(cut_item_num,
			       "when 0-th enrty of item is cut, that item must be first in the node, not %d-th",
			       cut_item_num);
			/* change item key by key of first entry in the item */
			set_le_ih_k_offset(ih, deh_offset(B_I_DEH(bh, ih)));
			/*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE); */
		}
	} else {
		/* item is direct or indirect */
		RFALSE(is_statdata_le_ih(ih), "10195: item is stat data");
		RFALSE(pos_in_item && pos_in_item + cut_size != ih_item_len(ih),
		       "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)",
		       (long unsigned)pos_in_item, (long unsigned)cut_size,
		       (long unsigned)ih_item_len(ih));

		/* shift item body to left if cut is from the head of item */
		if (pos_in_item == 0) {
			memmove(bh->b_data + ih_location(ih),
				bh->b_data + ih_location(ih) + cut_size,
				ih_item_len(ih) - cut_size);

			/* change key of item */
			if (is_direct_le_ih(ih))
				set_le_ih_k_offset(ih,
						   le_ih_k_offset(ih) +
						   cut_size);
			else {
				set_le_ih_k_offset(ih,
						   le_ih_k_offset(ih) +
						   (cut_size / UNFM_P_SIZE) *
						   bh->b_size);
				RFALSE(ih_item_len(ih) == cut_size
				       && get_ih_free_space(ih),
				       "10205: invalid ih_free_space (%h)", ih);
			}
		}
	}

	/* location of the last item */
	last_loc = ih_location(&(ih[nr - cut_item_num - 1]));

	/* location of the item, which is remaining at the same place */
	unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size;

	/* shift */
	memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
		unmoved_loc - last_loc - cut_size);

	/* change item length */
	put_ih_item_len(ih, ih_item_len(ih) - cut_size);

	if (is_indirect_le_ih(ih)) {
		if (pos_in_item)
			set_ih_free_space(ih, 0);
	}

	/* change locations */
	for (i = cut_item_num; i < nr; i++)
		put_ih_location(&(ih[i - cut_item_num]),
				ih_location(&ih[i - cut_item_num]) + cut_size);

	/* size, free space */
	set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size);

	do_balance_mark_leaf_dirty(bi->tb, bh, 0);

	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) - cut_size);
		do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
	}
}

/* delete del_num items from buffer starting from the first'th item */
static void leaf_delete_items_entirely(struct buffer_info *bi,
				       int first, int del_num)
{
	struct buffer_head *bh = bi->bi_bh;
	int nr;
	int i, j;
	int last_loc, last_removed_loc;
	struct block_head *blkh;
	struct item_head *ih;

	RFALSE(bh == NULL, "10210: buffer is 0");
	RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num);

	if (del_num == 0)
		return;

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

	RFALSE(first < 0 || first + del_num > nr,
	       "10220: first=%d, number=%d, there is %d items", first, del_num,
	       nr);

	if (first == 0 && del_num == nr) {
		/* this does not work */
		make_empty_node(bi);

		do_balance_mark_leaf_dirty(bi->tb, bh, 0);
		return;
	}

	ih = B_N_PITEM_HEAD(bh, first);

	/* location of unmovable item */
	j = (first == 0) ? bh->b_size : ih_location(ih - 1);

	/* delete items */
	last_loc = ih_location(&(ih[nr - 1 - first]));
	last_removed_loc = ih_location(&(ih[del_num - 1]));

	memmove(bh->b_data + last_loc + j - last_removed_loc,
		bh->b_data + last_loc, last_removed_loc - last_loc);

	/* delete item headers */
	memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE);

	/* change item location */
	for (i = first; i < nr - del_num; i++)
		put_ih_location(&(ih[i - first]),
				ih_location(&(ih[i - first])) + (j -
								 last_removed_loc));

	/* sizes, item number */
	set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
	set_blkh_free_space(blkh,
			    blkh_free_space(blkh) + (j - last_removed_loc +
						     IH_SIZE * del_num));

	do_balance_mark_leaf_dirty(bi->tb, bh, 0);

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

/* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
void leaf_paste_entries(struct buffer_head *bh,
			int item_num,
			int before,
			int new_entry_count,
			struct reiserfs_de_head *new_dehs,
			const char *records, int paste_size)
{
	struct item_head *ih;
	char *item;
	struct reiserfs_de_head *deh;
	char *insert_point;
	int i, old_entry_num;

	if (new_entry_count == 0)
		return;

	ih = B_N_PITEM_HEAD(bh, item_num);

	/* make sure, that item is directory, and there are enough records in it */
	RFALSE(!is_direntry_le_ih(ih), "10225: item is not directory item");
	RFALSE(I_ENTRY_COUNT(ih) < before,
	       "10230: there are no entry we paste entries before. entry_count = %d, before = %d",
	       I_ENTRY_COUNT(ih), before);

	/* first byte of dest item */
	item = bh->b_data + ih_location(ih);

	/* entry head array */
	deh = B_I_DEH(bh, ih);

	/* new records will be pasted at this point */
	insert_point =
	    item +
	    (before ? deh_location(&(deh[before - 1]))
	     : (ih_item_len(ih) - paste_size));

	/* adjust locations of records that will be AFTER new records */
	for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i--)
		put_deh_location(&(deh[i]),
				 deh_location(&(deh[i])) +
				 (DEH_SIZE * new_entry_count));

	/* adjust locations of records that will be BEFORE new records */
	for (i = 0; i < before; i++)
		put_deh_location(&(deh[i]),
				 deh_location(&(deh[i])) + paste_size);

	old_entry_num = I_ENTRY_COUNT(ih);
	put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count);

	/* prepare space for pasted records */
	memmove(insert_point + paste_size, insert_point,
		item + (ih_item_len(ih) - paste_size) - insert_point);

	/* copy new records */
	memcpy(insert_point + DEH_SIZE * new_entry_count, records,
	       paste_size - DEH_SIZE * new_entry_count);

	/* prepare space for new entry heads */
	deh += before;
	memmove((char *)(deh + new_entry_count), deh,
		insert_point - (char *)deh);

	/* copy new entry heads */
	deh = (struct reiserfs_de_head *)((char *)deh);
	memcpy(deh, new_dehs, DEH_SIZE * new_entry_count);

	/* set locations of new records */
	for (i = 0; i < new_entry_count; i++) {
		put_deh_location(&(deh[i]),
				 deh_location(&(deh[i])) +
				 (-deh_location
				  (&(new_dehs[new_entry_count - 1])) +
				  insert_point + DEH_SIZE * new_entry_count -
				  item));
	}

	/* change item key if necessary (when we paste before 0-th entry */
	if (!before) {
		set_le_ih_k_offset(ih, deh_offset(new_dehs));
/*      memcpy (&ih->ih_key.k_offset, 
		       &new_dehs->deh_offset, SHORT_KEY_SIZE);*/
	}
#ifdef CONFIG_REISERFS_CHECK
	{
		int prev, next;
		/* check record locations */
		deh = B_I_DEH(bh, ih);
		for (i = 0; i < I_ENTRY_COUNT(ih); i++) {
			next =
			    (i <
			     I_ENTRY_COUNT(ih) -
			     1) ? deh_location(&(deh[i + 1])) : 0;
			prev = (i != 0) ? deh_location(&(deh[i - 1])) : 0;

			if (prev && prev <= deh_location(&(deh[i])))
				reiserfs_warning(NULL,
						 "vs-10240: leaf_paste_entries: directory item (%h) corrupted (prev %a, cur(%d) %a)",
						 ih, deh + i - 1, i, deh + i);
			if (next && next >= deh_location(&(deh[i])))
				reiserfs_warning(NULL,
						 "vs-10250: leaf_paste_entries: directory item (%h) corrupted (cur(%d) %a, next %a)",
						 ih, i, deh + i, deh + i + 1);
		}
	}
#endif

}