fix_node.c

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

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

/**
 ** old_item_num
 ** old_entry_num
 ** set_entry_sizes
 ** create_virtual_node
 ** check_left
 ** check_right
 ** directory_part_size
 ** get_num_ver
 ** item_length
 ** set_parameters
 ** is_leaf_removable
 ** are_leaves_removable
 ** get_empty_nodes
 ** get_lfree
 ** get_rfree
 ** is_left_neighbor_in_cache
 ** decrement_key
 ** get_far_parent
 ** get_parents
 ** can_node_be_removed
 ** ip_check_balance
 ** dc_check_balance_internal
 ** dc_check_balance_leaf
 ** dc_check_balance
 ** check_balance
 ** get_direct_parent
 ** get_neighbors
 ** fix_nodes
 ** 
 ** 
 **/


#include "includes.h"


/* To make any changes in the tree we find a node, that contains item to be
   changed/deleted or position in the node we insert a new item to. We call
   this node S. To do balancing we need to decide what we will shift to
   left/right neighbor, or to a new node, where new item will be etc. To make
   this analysis simpler we build virtual node. Virtual node is an array of
   items, that will replace items of node S. (For instance if we are going to
   delete an item, virtual node does not contain it). Virtual node keeps
   information about item sizes and types, mergeability of first and last
   items, sizes of all entries in directory item. We use this array of items
   when calculating what we can shift to neighbors and how many nodes we have
   to have if we do not any shiftings, if we shift to left/right neighbor or
   to both. */


/* taking item number in virtual node, returns number of item, that it has in
   source buffer */
static inline int old_item_num (int new_num, int affected_item_num, int mode)
{
    if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
	return new_num;
    
    if (mode == M_INSERT)
	return new_num - 1;

    /* delete mode */
    return new_num + 1;
}


/* function returns old entry number in directory item in real node using new
   entry number in virtual item in virtual node */
static inline int old_entry_num (int new_num, int affected_item_num, int new_entry_num, int pos_in_item, int mode)
{
    if ( mode == M_INSERT || mode == M_DELETE)
	return new_entry_num;
    
    if (new_num != affected_item_num) {
	/* cut or paste is applied to another item */
	return new_entry_num;
    }
    
    if (new_entry_num < pos_in_item)
	return new_entry_num;
    
    if (mode == M_CUT)
	return new_entry_num + 1;
    
    return new_entry_num - 1;
}



/*
 * Create an array of sizes of directory entries for virtual item
 */
static void set_entry_sizes (struct tree_balance * tb,
			     int old_num, int new_num,
			     struct buffer_head * bh,
			     struct item_head * ih)
{
    struct virtual_node * vn = tb->tb_vn;
    int i;
    struct reiserfs_de_head * deh;
    struct virtual_item * vi;
  
    deh = B_I_DEH (bh, ih);

    /* seek to given virtual item in array of virtual items */
    vi = vn->vn_vi + new_num;

    /* virtual directory item have this amount of entry after */
    vi->vi_entry_count = get_ih_entry_count (ih) + 
	((old_num == vn->vn_affected_item_num) ? ((vn->vn_mode == M_CUT) ? -1 :
						  (vn->vn_mode == M_PASTE ? 1 : 0)) : 0);
    vi->vi_entry_sizes = (__u16 *)vn->vn_free_ptr;
    vn->vn_free_ptr += vi->vi_entry_count * sizeof (__u16);

    /* set sizes of old entries */
    for (i = 0; i < vi->vi_entry_count; i ++) {
	int j;
    
	j = old_entry_num (old_num, vn->vn_affected_item_num, i, vn->vn_pos_in_item, vn->vn_mode);
	vi->vi_entry_sizes[i] = entry_length (ih, &(deh[j]), j) + DEH_SIZE;
    }
  
    /* set size of pasted entry */
    if (old_num == vn->vn_affected_item_num && vn->vn_mode == M_PASTE)
	vi->vi_entry_sizes[vn->vn_pos_in_item] = tb->insert_size[0];
}


static void create_virtual_node (struct tree_balance * tb, int h)
{
    struct item_head * ih;
    struct virtual_node * vn = tb->tb_vn;
    int new_num;
    struct buffer_head * Sh;	/* this comes from tb->S[h] */

    Sh = PATH_H_PBUFFER (tb->tb_path, h);

    /* size of changed node */
    vn->vn_size = MAX_CHILD_SIZE (Sh->b_size) - get_blkh_free_space (B_BLK_HEAD (Sh)) + tb->insert_size[h];

    /* for internal nodes array if virtual items is not created */
    if (h) {
	vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
	return;
    }

    /* number of items in virtual node  */
    vn->vn_nr_item = B_NR_ITEMS (Sh) + ((vn->vn_mode == M_INSERT)? 1 : 0) - ((vn->vn_mode == M_DELETE)? 1 : 0);

    /* first virtual item */
    vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
    memset (vn->vn_vi, 0, vn->vn_nr_item * sizeof (struct virtual_item));
    vn->vn_free_ptr += vn->vn_nr_item * sizeof (struct virtual_item);


    /* first item in the node */
    ih = B_N_PITEM_HEAD (Sh, 0);

    /* define the mergeability for 0-th item (if it is not being deleted) */
    if (is_left_mergeable (tb->tb_fs, tb->tb_path) == 1 && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))
	vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;

    /* go through all items those remain in the virtual node (except for the new (inserted) one) */
    for (new_num = 0; new_num < vn->vn_nr_item; new_num ++) {
	int j;
    
	if (vn->vn_affected_item_num == new_num && vn->vn_mode == M_INSERT)
	    continue;
    
	/* get item number in source node */
	j = old_item_num (new_num, vn->vn_affected_item_num, vn->vn_mode);
    
	vn->vn_vi[new_num].vi_item_len += get_ih_item_len (&ih[j]) + IH_SIZE;
    
	if (I_IS_STAT_DATA_ITEM (ih + j)) {
	    vn->vn_vi[new_num].vi_type |= VI_TYPE_STAT_DATA;
	    continue;
	}

	/* set type of item */
	if (I_IS_DIRECT_ITEM (ih + j))
	    vn->vn_vi[new_num].vi_type |= VI_TYPE_DIRECT;
    
	if (I_IS_INDIRECT_ITEM (ih + j))
	    vn->vn_vi[new_num].vi_type |= VI_TYPE_INDIRECT;

	if (I_IS_DIRECTORY_ITEM (ih + j)) {
	    set_entry_sizes (tb, j, new_num, Sh, ih + j);
	    vn->vn_vi[new_num].vi_type |= VI_TYPE_DIRECTORY;
	    if (get_key_offset_v1 (&ih[j].ih_key) == DOT_OFFSET)
		vn->vn_vi[new_num].vi_type |= VI_TYPE_FIRST_DIRECTORY_ITEM;
	}
    
	vn->vn_vi[new_num].vi_item_offset = get_offset (&(ih + j)->ih_key);
	
	if (new_num != vn->vn_affected_item_num)
	    /* this is not being changed */
	    continue;
    
	if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT)
	    vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
    }
  
  
    /* virtual inserted item is not defined yet */
    if (vn->vn_mode == M_INSERT) {
	vn->vn_vi[vn->vn_affected_item_num].vi_item_len = tb->insert_size[0];
	vn->vn_vi[vn->vn_affected_item_num].vi_item_offset = get_offset (&vn->vn_ins_ih->ih_key);

	switch (get_type (&vn->vn_ins_ih->ih_key)) {
	case TYPE_STAT_DATA:
	    vn->vn_vi[vn->vn_affected_item_num].vi_type |= VI_TYPE_STAT_DATA;
	    break;
	case TYPE_DIRECT:
	    vn->vn_vi[vn->vn_affected_item_num].vi_type |= VI_TYPE_DIRECT;
	    break;
	case TYPE_INDIRECT:
	    vn->vn_vi[vn->vn_affected_item_num].vi_type |= VI_TYPE_INDIRECT;
	    break;
	default:
	    /* inseted item is directory (it must be item with "." and "..") */
	    vn->vn_vi[vn->vn_affected_item_num].vi_type |= 
		(VI_TYPE_DIRECTORY | VI_TYPE_FIRST_DIRECTORY_ITEM | VI_TYPE_INSERTED_DIRECTORY_ITEM);
      
	    /* this directory item can not be split, so do not set sizes of entries */
	    break;
	}
    }
  
    /* set right merge flag we take right delimiting key and check whether it is a mergeable item */
    if (tb->CFR[0]) {
	ih = (struct item_head *)B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0]);
	if (is_right_mergeable (tb->tb_fs, tb->tb_path) == 1 &&
		(vn->vn_mode != M_DELETE || vn->vn_affected_item_num != B_NR_ITEMS (Sh) - 1))
	    vn->vn_vi[vn->vn_nr_item-1].vi_type |= VI_TYPE_RIGHT_MERGEABLE;
    }
}


/* using virtual node check, how many items can be shifted to left
   neighbor */
static  int check_left (struct tree_balance * tb, int h, int cur_free)
{
    int i;
    struct virtual_node * vn = tb->tb_vn;
    int d_size, ih_size, bytes = -1;

    /* internal level */
    if (h > 0) {	
	if (!cur_free ) {
	    tb->lnum[h] = 0; 
	    return 0;
	}
	tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
	return -1;
    }

    /* leaf level */

    if (!cur_free || !vn->vn_nr_item) {
	/* no free space */
	tb->lnum[h] = 0;
	tb->lbytes = -1;
	return 0;
    }

    if ((unsigned int)cur_free >= (vn->vn_size - ((vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
	/* all contents of S[0] fits into L[0] */
	tb->lnum[0] = vn->vn_nr_item;
	tb->lbytes = -1;
	return -1;
    }
  
    d_size = 0, ih_size = IH_SIZE;

    /* first item may be merge with last item in left neighbor */
    if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
	d_size = -((int)IH_SIZE), ih_size = 0;

    tb->lnum[0] = 0;
    for (i = 0; i < vn->vn_nr_item; i ++, ih_size = IH_SIZE, d_size = 0) {
	d_size += vn->vn_vi[i].vi_item_len;
	if (cur_free >= d_size) {	
	    /* the item can be shifted entirely */
	    cur_free -= d_size;
	    tb->lnum[0] ++;
	    continue;
	}
      
	/* the item cannot be shifted entirely, try to split it */
	/* check whether L[0] can hold ih and at least one byte of the item body */
	if (cur_free <= ih_size) {
	    /* cannot shift even a part of the current item */
	    tb->lbytes = -1;
	    return -1;
	}
	cur_free -= ih_size;
    
	if (vn->vn_vi[i].vi_type & VI_TYPE_STAT_DATA ||
	    vn->vn_vi[i].vi_type & VI_TYPE_INSERTED_DIRECTORY_ITEM)	{
	    /* virtual item is a stat_data or empty directory body ("." and ".."), that is not split able */
	    tb->lbytes = -1;
	    return -1;
	}
    
	if (vn->vn_vi[i].vi_type & VI_TYPE_DIRECT) {
	    /* body of a direct item can be split by 8 bytes */
	    int align = 8 - (vn->vn_vi[i].vi_item_offset - 1) % 8;
//	    reiserfs_warning(stderr,"\nbalancing: cur_free (%d) ", cur_free);
	    tb->lbytes = bytes = (cur_free >= align) ? (align + ((cur_free - align) / 8 * 8)) : 0;
//	    reiserfs_warning(stderr,"offset (0x%Lx), move_left (%d), get offset (0x%Lx)",
//	    	vn->vn_vi[i].vi_item_offset, bytes, vn->vn_vi[i].vi_item_offset + bytes);
	}

	if (vn->vn_vi[i].vi_type & VI_TYPE_INDIRECT)
	    /* body of a indirect item can be split at unformatted pointer bound */
	    tb->lbytes = bytes = cur_free - cur_free % UNFM_P_SIZE;
    
	/* item is of directory type */     
	if (vn->vn_vi[i].vi_type & VI_TYPE_DIRECTORY) {
	    /* directory entries are the solid granules of the directory
	       item, they cannot be split in the middle */
      
	    /* calculate number of dir entries that can be shifted, and
	       their total size */
	    int j;
	    struct virtual_item * vi;
      
	    tb->lbytes = 0;
	    bytes = 0;
	    vi = &vn->vn_vi[i];
      
	    for (j = 0; j < vi->vi_entry_count; j ++) {
		if (vi->vi_entry_sizes[j] > cur_free)
		    /* j-th entry doesn't fit into L[0] */
		    break;
		  
		bytes += vi->vi_entry_sizes[j];
		cur_free -= vi->vi_entry_sizes[j];
		tb->lbytes ++;
	    }
	    /* "." can not be cut from first directory item */
	    if ((vn->vn_vi[i].vi_type & VI_TYPE_FIRST_DIRECTORY_ITEM) && tb->lbytes < 2)
		tb->lbytes = 0;
	}
    

	if (tb->lbytes <= 0) {
	    /* nothing can flow from the item */
	    tb->lbytes = -1;
	    return -1;
	}
    
	/* something can flow from the item */
	tb->lnum[0] ++;
	return bytes;	/* part of split item in bytes */
    }
  

    reiserfs_panic (0, "vs-8065: check_left: all items fit in the left neighbor");
    return 0;
}

	

/* using virtual node check, how many items can be shifted to right
   neighbor */
static int check_right (struct tree_balance * tb, int h, int cur_free)
{
    int i;
    struct virtual_node * vn = tb->tb_vn;
    int d_size, ih_size, bytes = -1;

    /* internal level */
    if (h > 0) {
	if (!cur_free) {
	    tb->rnum[h] = 0; 
	    return 0;
	}
	tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
	return -1;
    }
    
    /* leaf level */