lbalance.c

reiserfsprogs-3.6.19.tar.gz 源码 给有需要的人！

/*
 * Copyright 1996-2004 by Hans Reiser, licensing governed by 
 * reiserfsprogs/README
 */

#include "includes.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
   */


extern struct tree_balance init_tb;
extern int init_item_pos;
extern int init_pos_in_item;
extern int init_mode;



/* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */
static void leaf_copy_dir_entries (reiserfs_filsys_t * fs,
			           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);

    /* 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 ? get_deh_location (&deh[from - 1]) : get_ih_item_len (ih)) - 
	    get_deh_location (&deh[from + copy_count - 1]);
	records = source->b_data + get_ih_location (ih) + get_deh_location (&deh[from + copy_count - 1]);
    } else {
	copy_records_len = 0;
	records = 0;
    }

    /* 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 && are_items_mergeable (B_N_PITEM_HEAD (dest, item_num_in_dest), ih, dest->b_size) == 0) ||
	 (last_first == LAST_TO_FIRST && are_items_mergeable (ih, B_N_PITEM_HEAD (dest, item_num_in_dest), dest->b_size) == 0)) {
	/* create new item in dest */
	struct item_head new_ih;

	/* form item header */
	memcpy (&new_ih.ih_key, &ih->ih_key, KEY_SIZE);

	/* calculate item len */
	set_ih_item_len (&new_ih, DEH_SIZE * copy_count + copy_records_len);
	set_ih_entry_count (&new_ih, 0);
    
	if (last_first == LAST_TO_FIRST) {
	    /* form key by the following way */
	    if (from < get_ih_entry_count (ih)) {
		set_key_offset_v1 (&new_ih.ih_key, get_deh_offset (&deh[from]));
	    } else {
		/* no entries will be copied to this item in this function */
		set_key_offset_v1 (&new_ih.ih_key, MAX_KEY1_OFFSET);
	    }
	    set_key_uniqueness (&new_ih.ih_key, DIRENTRY_UNIQUENESS);
	}
	set_ih_key_format (&new_ih, get_ih_key_format (ih));
	set_ih_flags (&new_ih, get_ih_flags (ih));
    
	/* insert item into dest buffer */
	leaf_insert_into_buf (fs, 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 (fs, dest_bi, (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0, 0xffff /*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) ? get_ih_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 (reiserfs_filsys_t * fs,
                                    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 || (are_items_mergeable (dih, ih, src->b_size) == 0))
	    /* there is nothing to merge */
	    return 0;
      
	if ( I_IS_DIRECTORY_ITEM(ih) ) {
	    if ( bytes_or_entries == -1 )
		/* copy all entries to dest */
		bytes_or_entries = get_ih_entry_count(ih);
	    leaf_copy_dir_entries (fs, 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 = get_ih_item_len (ih);

	/* 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 (fs, dest_bi, dest_nr_item - 1, get_ih_item_len (dih),
		bytes_or_entries, B_I_PITEM(src,ih), 0);
      
	if (I_IS_INDIRECT_ITEM(dih)) {
	    if (bytes_or_entries == get_ih_item_len (ih))
		//dih->u.ih_free_space = ih->u.ih_free_space;
		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 || are_items_mergeable (ih, dih, src->b_size) == 0)
	return 0;
  
    if ( I_IS_DIRECTORY_ITEM(ih)) {
	if ( bytes_or_entries == -1 )
	    /* bytes_or_entries = entries number in last item body of SOURCE */
	    bytes_or_entries = get_ih_entry_count(ih);
    
	leaf_copy_dir_entries (fs, dest_bi, src, LAST_TO_FIRST, src_nr_item - 1, get_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
    */
  
    if ( bytes_or_entries == -1 ) {
	/* bytes_or_entries = length of last item body of SOURCE */
	bytes_or_entries = get_ih_item_len (ih);

	/* change first item key of the DEST */
	//dih->ih_key.k_offset = ih->ih_key.k_offset;
	set_offset (key_format (&dih->ih_key), &dih->ih_key, get_offset (&ih->ih_key));

	/* item becomes non-mergeable */
	/* or mergeable if left item was */
	//dih->ih_key.k_uniqueness = ih->ih_key.k_uniqueness;
	set_type (key_format (&dih->ih_key), &dih->ih_key, get_type (&ih->ih_key));
    } else {
	/* merge to right only part of item */
	/* change first item key of the DEST */
	if ( I_IS_DIRECT_ITEM(dih) ) {
	    //dih->ih_key.k_offset -= bytes_or_entries;
	    set_offset (key_format (&dih->ih_key), &dih->ih_key, get_offset (&dih->ih_key) - bytes_or_entries);
	} else {
	    //dih->ih_key.k_offset -= ((bytes_or_entries/UNFM_P_SIZE)*dest->b_size);
	    set_offset (key_format (&dih->ih_key), &dih->ih_key, 
			get_offset (&dih->ih_key) - ((bytes_or_entries/UNFM_P_SIZE)*dest->b_size));
	}
    }
  
    leaf_paste_in_buffer (fs, dest_bi, 0, 0, bytes_or_entries, B_I_PITEM(src,ih) + get_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 (reiserfs_filsys_t * fs, struct buffer_info * dest_bi, 
                                      struct buffer_head * src, int last_first,
				      int first, int cpy_num)
{
    struct buffer_head * dest;
    int nr;
    int dest_before;
    int last_loc, last_inserted_loc, location;
    int i, j;
    struct block_head * blkh;
    struct item_head * ih;

    dest = dest_bi->bi_bh;

    if (cpy_num == 0)
	return;

    blkh = B_BLK_HEAD(dest);
    nr = get_blkh_nr_items (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);

    /* 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);

    set_blkh_free_space (blkh, get_blkh_free_space (blkh) - IH_SIZE * cpy_num);

    /* location of unmovable item */
    j = location = (dest_before == 0) ? dest->b_size : get_ih_location (ih-1);
    for (i = dest_before; i < nr + cpy_num; i ++) {
	location -= get_ih_item_len (&ih[i-dest_before]);
	set_ih_location (&ih[i-dest_before], location);
    }

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

    /* check free space */
    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_items (blkh, get_blkh_nr_items (blkh) + cpy_num);
    set_blkh_free_space (blkh, 
			 get_blkh_free_space (blkh) - (j - last_inserted_loc));
  
    mark_buffer_dirty (dest);

    if (dest_bi->bi_parent) {
	struct disk_child * dc;
	dc = B_N_CHILD (dest_bi->bi_parent, dest_bi->bi_position);
	set_dc_child_size (dc, get_dc_child_size (dc) + j - last_inserted_loc + IH_SIZE * cpy_num);
	mark_buffer_dirty(dest_bi->bi_parent);
    }
}


/* This function splits the (liquid) item into two items (useful when
   shifting part of an item into another node.) */
static void leaf_item_bottle (reiserfs_filsys_t * fs,
			      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;
  
    if ( last_first == FIRST_TO_LAST ) {
	/* if ( if item in position item_num in buffer SOURCE is directory item ) */
	if (I_IS_DIRECTORY_ITEM(ih = B_N_PITEM_HEAD(src,item_num)))
	    leaf_copy_dir_entries (fs, 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);
	    set_ih_item_len (&n_ih, cpy_bytes);
	    if (I_IS_INDIRECT_ITEM(ih)) {
		//n_ih.u.ih_free_space = 0;
		set_ih_free_space (&n_ih, 0);;
	    }

	    //n_ih.ih_version = ih->ih_version;
	    set_ih_key_format (&n_ih, get_ih_key_format (ih));
	    set_ih_flags (&n_ih, get_ih_flags (ih));
	    leaf_insert_into_buf (fs, 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 (I_IS_DIRECTORY_ITEM(ih = B_N_PITEM_HEAD (src, item_num)))
	    leaf_copy_dir_entries (fs, dest_bi, src, LAST_TO_FIRST, item_num, get_ih_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);
      
	    if (I_IS_DIRECT_ITEM(ih)) {
		//n_ih.ih_key.k_offset = ih->ih_key.k_offset + ih->ih_item_len - cpy_bytes;
		set_offset (key_format (&ih->ih_key), &n_ih.ih_key, get_offset (&ih->ih_key) + get_ih_item_len (ih) - cpy_bytes);
		//n_ih.ih_key.k_uniqueness = TYPE_DIRECT;
		set_type (key_format (&ih->ih_key), &n_ih.ih_key, TYPE_DIRECT);
		//n_ih.u.ih_free_space = USHRT_MAX;
		set_ih_free_space (&n_ih, USHRT_MAX);
	    } else {
		/* indirect item */
		//n_ih.ih_key.k_offset = ih->ih_key.k_offset + (ih->ih_item_len - cpy_bytes) / UNFM_P_SIZE * dest->b_size;
		set_offset (key_format (&ih->ih_key), &n_ih.ih_key,
			    get_offset (&ih->ih_key) + (get_ih_item_len (ih) - cpy_bytes) / UNFM_P_SIZE * dest->b_size);
		//n_ih.ih_key.k_uniqueness = TYPE_INDIRECT;
		set_type (key_format (&ih->ih_key), &n_ih.ih_key, TYPE_INDIRECT);
		//n_ih.u.ih_free_space = ih->u.ih_free_space;
		set_ih_free_space (&n_ih, get_ih_free_space (ih));
	    }
      
	    /* set item length */
	    set_ih_item_len (&n_ih, cpy_bytes);
	    //n_ih.ih_version = ih->ih_version;
	    set_ih_key_format (&n_ih, get_ih_key_format (ih));
	    set_ih_flags (&n_ih, get_ih_flags (ih));
	    leaf_insert_into_buf (fs, dest_bi, 0, &n_ih, B_N_PITEM(src,item_num) + get_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 (reiserfs_filsys_t * fs,
                            struct buffer_info * dest_bi, struct buffer_head * src,
			    int last_first, int cpy_num,
			    int cpy_bytes)
{
    struct buffer_head * dest;