fix_node.c

嵌入式系统设计与实验教材二源码linux内核移植与编译

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

/**
 ** old_item_num
 ** old_entry_num
 ** set_entry_sizes
 ** create_virtual_node
 ** check_left
 ** check_right
 ** directory_part_size
 ** get_num_ver
 ** 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 <linux/config.h>
#include <linux/sched.h>
#include <linux/string.h>
#include <linux/locks.h>
#include <linux/reiserfs_fs.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) {

    RFALSE( new_num == 0, 
	    "vs-8005: for INSERT mode and item number of inserted item");

    return new_num - 1;
  }

  RFALSE( mode != M_DELETE,
	  "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'", mode);
  /* delete mode */
  return new_num + 1;
}

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_FREE_SPACE (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 (op_is_left_mergeable (&(ih->ih_key), Sh->b_size) && (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;
	struct virtual_item * vi = vn->vn_vi + new_num;
	int is_affected = ((new_num != vn->vn_affected_item_num) ? 0 : 1);
    

	if (is_affected && 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);
    
	vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
	vi->vi_ih = ih + j;
	vi->vi_item = B_I_PITEM (Sh, ih + j);
	vi->vi_uarea = vn->vn_free_ptr;

	// FIXME: there is no check, that item operation did not
	// consume too much memory
	vn->vn_free_ptr += op_create_vi (vn, vi, is_affected, tb->insert_size [0]);
	if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
	    reiserfs_panic (tb->tb_sb, "vs-8030: create_virtual_node: "
			    "virtual node space consumed");

	if (!is_affected)
	    /* 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];
	    vi->vi_new_data = vn->vn_data; // pointer to data which is going to be pasted
	}
    }

  
    /* virtual inserted item is not defined yet */
    if (vn->vn_mode == M_INSERT) {
	struct virtual_item * vi = vn->vn_vi + vn->vn_affected_item_num;
      
	RFALSE( vn->vn_ins_ih == 0,
		"vs-8040: item header of inserted item is not specified");
	vi->vi_item_len = tb->insert_size[0];
	vi->vi_ih = vn->vn_ins_ih;
	vi->vi_item = vn->vn_data;
	vi->vi_uarea = vn->vn_free_ptr;
	
	op_create_vi (vn, vi, 0/*not pasted or cut*/, tb->insert_size [0]);
    }
  
    /* set right merge flag we take right delimiting key and check whether it is a mergeable item */
    if (tb->CFR[0]) {
	struct key * key;

	key = B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0]);
	if (op_is_left_mergeable (key, Sh->b_size) && (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;

#ifdef CONFIG_REISERFS_CHECK
	if (op_is_left_mergeable (key, Sh->b_size) &&
	    !(vn->vn_mode != M_DELETE || vn->vn_affected_item_num != B_NR_ITEMS (Sh) - 1) ) {
	    /* we delete last item and it could be merged with right neighbor's first item */
	    if (!(B_NR_ITEMS (Sh) == 1 && is_direntry_le_ih (B_N_PITEM_HEAD (Sh, 0)) &&
		  I_ENTRY_COUNT (B_N_PITEM_HEAD (Sh, 0)) == 1)) {
		/* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */
		print_block (Sh, 0, -1, -1);
		reiserfs_panic (tb->tb_sb, "vs-8045: create_virtual_node: rdkey %k, affected item==%d (mode==%c) Must be %c", 
				key, vn->vn_affected_item_num, vn->vn_mode, M_DELETE);
	    } else
		/* we can delete directory item, that has only one directory entry in it */
		;
	}
#endif
    
    }
}


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

    RFALSE( cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);

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

    /* leaf level */

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

    RFALSE( !PATH_H_PPARENT (tb->tb_path, 0),
	    "vs-8055: parent does not exist or invalid");

    vi = vn->vn_vi;
    if ((unsigned int)cur_free >= (vn->vn_size - ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
	/* all contents of S[0] fits into L[0] */

	RFALSE( vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
		"vs-8055: invalid mode or balance condition failed");

	tb->lnum[0] = vn->vn_nr_item;
	tb->lbytes = -1;
	return;
    }
  

    d_size = 0, ih_size = IH_SIZE;

    /* first item may be merge with last item in left neighbor */
    if (vi->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, vi ++) {
	d_size += vi->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;
	}
	cur_free -= ih_size;
    
	tb->lbytes = op_check_left (vi, cur_free, 0, 0);
	if (tb->lbytes != -1)
	    /* count partially shifted item */
	    tb->lnum[0] ++;
    
	break;
    }
  
    return;
}


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

    RFALSE( cur_free < 0, "vs-8070: cur_free < 0");
    
    /* internal level */
    if (h > 0) {
	tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
	return;
    }
    
    /* leaf level */
    
    if (!cur_free || !vn->vn_nr_item) {
	/* no free space  */
	tb->rnum[h] = 0;
	tb->rbytes = -1;
	return;
    }
  
    RFALSE( !PATH_H_PPARENT (tb->tb_path, 0),
	    "vs-8075: parent does not exist or invalid");
  
    vi = vn->vn_vi + vn->vn_nr_item - 1;
    if ((unsigned int)cur_free >= (vn->vn_size - ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
	/* all contents of S[0] fits into R[0] */
	
	RFALSE( vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
		"vs-8080: invalid mode or balance condition failed");

	tb->rnum[h] = vn->vn_nr_item;
	tb->rbytes = -1;
	return;
    }
    
    d_size = 0, ih_size = IH_SIZE;
    
    /* last item may be merge with first item in right neighbor */
    if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)
	d_size = -(int)IH_SIZE, ih_size = 0;

    tb->rnum[0] = 0;
    for (i = vn->vn_nr_item - 1; i >= 0; i --, d_size = 0, ih_size = IH_SIZE, vi --) {
	d_size += vi->vi_item_len;
	if (cur_free >= d_size) {	
	    /* the item can be shifted entirely */
	    cur_free -= d_size;
	    tb->rnum[0] ++;
	    continue;
	}
	
	/* check whether R[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->rbytes = -1;
	    return;
	}
	
	/* R[0] can hold the header of the item and at least one byte of its body */
	cur_free -= ih_size;	/* cur_free is still > 0 */

	tb->rbytes = op_check_right (vi, cur_free);
	if (tb->rbytes != -1)
	    /* count partially shifted item */
	    tb->rnum[0] ++;
    
	break;
    }
	
  return;
}


/*
 * from - number of items, which are shifted to left neighbor entirely
 * to - number of item, which are shifted to right neighbor entirely
 * from_bytes - number of bytes of boundary item (or directory entries) which are shifted to left neighbor
 * to_bytes - number of bytes of boundary item (or directory entries) which are shifted to right neighbor */
static int get_num_ver (int mode, struct tree_balance * tb, int h,
			int from, int from_bytes,
			int to,   int to_bytes,
			short * snum012, int flow
    )
{
    int i;
    int cur_free;
    //    int bytes;
    int units;
    struct virtual_node * vn = tb->tb_vn;
    //    struct virtual_item * vi;

    int total_node_size, max_node_size, current_item_size;
    int needed_nodes;
    int start_item, 	/* position of item we start filling node from */
	end_item,	/* position of item we finish filling node by */
	start_bytes,/* number of first bytes (entries for directory) of start_item-th item 
		       we do not include into node that is being filled */
	end_bytes;	/* number of last bytes (entries for directory) of end_item-th item 
			   we do node include into node that is being filled */
    int split_item_positions[2]; /* these are positions in virtual item of
				    items, that are split between S[0] and
				    S1new and S1new and S2new */

    split_item_positions[0] = -1;
    split_item_positions[1] = -1;

    /* We only create additional nodes if we are in insert or paste mode
       or we are in replace mode at the internal level. If h is 0 and
       the mode is M_REPLACE then in fix_nodes we change the mode to
       paste or insert before we get here in the code.  */
    RFALSE( tb->insert_size[h] < 0  || (mode != M_INSERT && mode != M_PASTE),
	    "vs-8100: insert_size < 0 in overflow");