fix_node.c

ARM 嵌入式 系统 设计与实例开发 实验教材 二源码

    max_node_size = MAX_CHILD_SIZE (PATH_H_PBUFFER (tb->tb_path, h));

    /* snum012 [0-2] - number of items, that lay
       to S[0], first new node and second new node */
    snum012[3] = -1;	/* s1bytes */
    snum012[4] = -1;	/* s2bytes */

    /* internal level */
    if (h > 0) {
	i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
	if (i == max_node_size)
	    return 1;
	return (i / max_node_size + 1);
    }

    /* leaf level */
    needed_nodes = 1;
    total_node_size = 0;
    cur_free = max_node_size;

    // start from 'from'-th item
    start_item = from;
    // skip its first 'start_bytes' units
    start_bytes = ((from_bytes != -1) ? from_bytes : 0);

    // last included item is the 'end_item'-th one
    end_item = vn->vn_nr_item - to - 1;
    // do not count last 'end_bytes' units of 'end_item'-th item
    end_bytes = (to_bytes != -1) ? to_bytes : 0;

    /* go through all item beginning from the start_item-th item and ending by
       the end_item-th item. Do not count first 'start_bytes' units of
       'start_item'-th item and last 'end_bytes' of 'end_item'-th item */
    
    for (i = start_item; i <= end_item; i ++) {
	struct virtual_item * vi = vn->vn_vi + i;
	int skip_from_end = ((i == end_item) ? end_bytes : 0);

	RFALSE( needed_nodes > 3, "vs-8105: too many nodes are needed");

	/* get size of current item */
	current_item_size = vi->vi_item_len;

	/* do not take in calculation head part (from_bytes) of from-th item */
	current_item_size -= op_part_size (vi, 0/*from start*/, start_bytes);

	/* do not take in calculation tail part of last item */
	current_item_size -= op_part_size (vi, 1/*from end*/, skip_from_end);

	/* if item fits into current node entierly */
	if (total_node_size + current_item_size <= max_node_size) {
	    snum012[needed_nodes - 1] ++;
	    total_node_size += current_item_size;
	    start_bytes = 0;
	    continue;
	}

	if (current_item_size > max_node_size) {
	    /* virtual item length is longer, than max size of item in
               a node. It is impossible for direct item */
	    RFALSE( is_direct_le_ih (vi->vi_ih),
		    "vs-8110: "
		    "direct item length is %d. It can not be longer than %d",
		    current_item_size, max_node_size);
	    /* we will try to split it */
	    flow = 1;
	}

	if (!flow) {
	    /* as we do not split items, take new node and continue */
	    needed_nodes ++; i --; total_node_size = 0;
	    continue;
	}

	// calculate number of item units which fit into node being
	// filled
	{
	    int free_space;

	    free_space = max_node_size - total_node_size - IH_SIZE;
	    units = op_check_left (vi, free_space, start_bytes, skip_from_end);
	    if (units == -1) {
		/* nothing fits into current node, take new node and continue */
		needed_nodes ++, i--, total_node_size = 0;
		continue;
	    }
	}

	/* something fits into the current node */
	//if (snum012[3] != -1 || needed_nodes != 1)
	//  reiserfs_panic (tb->tb_sb, "vs-8115: get_num_ver: too many nodes required");
	//snum012[needed_nodes - 1 + 3] = op_unit_num (vi) - start_bytes - units;
	start_bytes += units;
	snum012[needed_nodes - 1 + 3] = units;

	if (needed_nodes > 2)
	    reiserfs_warning ("vs-8111: get_num_ver: split_item_position is out of boundary\n");
	snum012[needed_nodes - 1] ++;
	split_item_positions[needed_nodes - 1] = i;
	needed_nodes ++;
	/* continue from the same item with start_bytes != -1 */
	start_item = i;
	i --;
	total_node_size = 0;
    }

    // sum012[4] (if it is not -1) contains number of units of which
    // are to be in S1new, snum012[3] - to be in S0. They are supposed
    // to be S1bytes and S2bytes correspondingly, so recalculate
    if (snum012[4] > 0) {
	int split_item_num;
	int bytes_to_r, bytes_to_l;
	int bytes_to_S1new;
    
	split_item_num = split_item_positions[1];
	bytes_to_l = ((from == split_item_num && from_bytes != -1) ? from_bytes : 0);
	bytes_to_r = ((end_item == split_item_num && end_bytes != -1) ? end_bytes : 0);
	bytes_to_S1new = ((split_item_positions[0] == split_item_positions[1]) ? snum012[3] : 0);

	// s2bytes
	snum012[4] = op_unit_num (&vn->vn_vi[split_item_num]) - snum012[4] - bytes_to_r - bytes_to_l - bytes_to_S1new;

	if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY)
	    reiserfs_warning ("vs-8115: get_num_ver: not directory item\n");
    }

    /* now we know S2bytes, calculate S1bytes */
    if (snum012[3] > 0) {
	int split_item_num;
	int bytes_to_r, bytes_to_l;
	int bytes_to_S2new;
    
	split_item_num = split_item_positions[0];
	bytes_to_l = ((from == split_item_num && from_bytes != -1) ? from_bytes : 0);
	bytes_to_r = ((end_item == split_item_num && end_bytes != -1) ? end_bytes : 0);
	bytes_to_S2new = ((split_item_positions[0] == split_item_positions[1] && snum012[4] != -1) ? snum012[4] : 0);

	// s1bytes
	snum012[3] = op_unit_num (&vn->vn_vi[split_item_num]) - snum012[3] - bytes_to_r - bytes_to_l - bytes_to_S2new;
    }
    
    return needed_nodes;
}


#ifdef CONFIG_REISERFS_CHECK
extern struct tree_balance * cur_tb;
#endif


/* Set parameters for balancing.
 * Performs write of results of analysis of balancing into structure tb,
 * where it will later be used by the functions that actually do the balancing. 
 * Parameters:
 *	tb	tree_balance structure;
 *	h	current level of the node;
 *	lnum	number of items from S[h] that must be shifted to L[h];
 *	rnum	number of items from S[h] that must be shifted to R[h];
 *	blk_num	number of blocks that S[h] will be splitted into;
 *	s012	number of items that fall into splitted nodes.
 *	lbytes	number of bytes which flow to the left neighbor from the item that is not
 *		not shifted entirely
 *	rbytes	number of bytes which flow to the right neighbor from the item that is not
 *		not shifted entirely
 *	s1bytes	number of bytes which flow to the first  new node when S[0] splits (this number is contained in s012 array)
 */

static void set_parameters (struct tree_balance * tb, int h, int lnum,
			    int rnum, int blk_num, short * s012, int lb, int rb)
{

  tb->lnum[h] = lnum;
  tb->rnum[h] = rnum;
  tb->blknum[h] = blk_num;

  if (h == 0)
    {  /* only for leaf level */
      if (s012 != NULL)
	{
	  tb->s0num = * s012 ++,
	  tb->s1num = * s012 ++,
	  tb->s2num = * s012 ++;
	  tb->s1bytes = * s012 ++;
	  tb->s2bytes = * s012;
	}
      tb->lbytes = lb;
      tb->rbytes = rb;
    }
  PROC_INFO_ADD( tb -> tb_sb, lnum[ h ], lnum );
  PROC_INFO_ADD( tb -> tb_sb, rnum[ h ], rnum );

  PROC_INFO_ADD( tb -> tb_sb, lbytes[ h ], lb );
  PROC_INFO_ADD( tb -> tb_sb, rbytes[ h ], rb );
}



/* check, does node disappear if we shift tb->lnum[0] items to left
   neighbor and tb->rnum[0] to the right one. */
static int is_leaf_removable (struct tree_balance * tb)
{
  struct virtual_node * vn = tb->tb_vn;
  int to_left, to_right;
  int size;
  int remain_items;

  /* number of items, that will be shifted to left (right) neighbor
     entirely */
  to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
  to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
  remain_items = vn->vn_nr_item;

  /* how many items remain in S[0] after shiftings to neighbors */
  remain_items -= (to_left + to_right);

  if (remain_items < 1) {
    /* all content of node can be shifted to neighbors */
    set_parameters (tb, 0, to_left, vn->vn_nr_item - to_left, 0, NULL, -1, -1);    
    return 1;
  }
  
  if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
    /* S[0] is not removable */
    return 0;

  /* check, whether we can divide 1 remaining item between neighbors */

  /* get size of remaining item (in item units) */
  size = op_unit_num (&(vn->vn_vi[to_left]));

  if (tb->lbytes + tb->rbytes >= size) {
    set_parameters (tb, 0, to_left + 1, to_right + 1, 0, NULL, tb->lbytes, -1);
    return 1;
  }

  return 0;
}


/* check whether L, S, R can be joined in one node */
static int are_leaves_removable (struct tree_balance * tb, int lfree, int rfree)
{
  struct virtual_node * vn = tb->tb_vn;
  int ih_size;
  struct buffer_head *S0;

  S0 = PATH_H_PBUFFER (tb->tb_path, 0);

  ih_size = 0;
  if (vn->vn_nr_item) {
    if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
      ih_size += IH_SIZE;
    
	if (vn->vn_vi[vn->vn_nr_item-1].vi_type & VI_TYPE_RIGHT_MERGEABLE)
	    ih_size += IH_SIZE;
    } else {
	/* there was only one item and it will be deleted */
	struct item_head * ih;
    
    RFALSE( B_NR_ITEMS (S0) != 1,
	    "vs-8125: item number must be 1: it is %d", B_NR_ITEMS(S0));

    ih = B_N_PITEM_HEAD (S0, 0);
    if (tb->CFR[0] && !comp_short_le_keys (&(ih->ih_key), B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0])))
	if (is_direntry_le_ih (ih)) {
	    /* Directory must be in correct state here: that is
	       somewhere at the left side should exist first directory
	       item. But the item being deleted can not be that first
	       one because its right neighbor is item of the same
	       directory. (But first item always gets deleted in last
	       turn). So, neighbors of deleted item can be merged, so
	       we can save ih_size */
	    ih_size = IH_SIZE;
	    
	    /* we might check that left neighbor exists and is of the
	       same directory */
	    RFALSE(le_ih_k_offset (ih) == DOT_OFFSET,
		"vs-8130: first directory item can not be removed until directory is not empty");
      }
    
  }

  if (MAX_CHILD_SIZE (S0) + vn->vn_size <= rfree + lfree + ih_size) {
    set_parameters (tb, 0, -1, -1, -1, NULL, -1, -1);
    PROC_INFO_INC( tb -> tb_sb, leaves_removable );
    return 1;  
  }
  return 0;
  
}



/* when we do not split item, lnum and rnum are numbers of entire items */
#define SET_PAR_SHIFT_LEFT \
if (h)\
{\
   int to_l;\
   \
   to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
	      (MAX_NR_KEY(Sh) + 1 - lpar);\
	      \
	      set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
}\
else \
{\
   if (lset==LEFT_SHIFT_FLOW)\
     set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
		     tb->lbytes, -1);\
   else\
     set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
		     -1, -1);\
}


#define SET_PAR_SHIFT_RIGHT \
if (h)\
{\
   int to_r;\
   \
   to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
   \
   set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
}\
else \
{\
   if (rset==RIGHT_SHIFT_FLOW)\
     set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
		  -1, tb->rbytes);\
   else\
     set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
		  -1, -1);\
}


void free_buffers_in_tb (
		       struct tree_balance * p_s_tb
		       ) {
  int n_counter;

  decrement_counters_in_path(p_s_tb->tb_path);
  
  for ( n_counter = 0; n_counter < MAX_HEIGHT; n_counter++ ) {
    decrement_bcount(p_s_tb->L[n_counter]);
    p_s_tb->L[n_counter] = NULL;
    decrement_bcount(p_s_tb->R[n_counter]);
    p_s_tb->R[n_counter] = NULL;
    decrement_bcount(p_s_tb->FL[n_counter]);
    p_s_tb->FL[n_counter] = NULL;
    decrement_bcount(p_s_tb->FR[n_counter]);
    p_s_tb->FR[n_counter] = NULL;
    decrement_bcount(p_s_tb->CFL[n_counter]);
    p_s_tb->CFL[n_counter] = NULL;
    decrement_bcount(p_s_tb->CFR[n_counter]);
    p_s_tb->CFR[n_counter] = NULL;
  }
}


/* Get new buffers for storing new nodes that are created while balancing.
 * Returns:	SCHEDULE_OCCURRED - schedule occurred while the function worked;
 *	        CARRY_ON - schedule didn't occur while the function worked;
 *	        NO_DISK_SPACE - no disk space.
 */
/* The function is NOT SCHEDULE-SAFE! */
static int  get_empty_nodes(
              struct tree_balance * p_s_tb,
              int n_h
            ) {
  struct buffer_head  * p_s_new_bh,
    		      *	p_s_Sh = PATH_H_PBUFFER (p_s_tb->tb_path, n_h);
  unsigned long	      *	p_n_blocknr,
    			a_n_blocknrs[MAX_AMOUNT_NEEDED] = {0, };
  int       		n_counter,
   			n_number_of_freeblk,
                	n_amount_needed,/* number of needed empty blocks */
			n_retval = CARRY_ON;
  struct super_block *	p_s_sb = p_s_tb->tb_sb;


  /* number_of_freeblk is the number of empty blocks which have been
     acquired for use by the balancing algorithm minus the number of
     empty blocks used in the previous levels of the analysis,
     number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs
     after empty blocks are acquired, and the balancing analysis is
     then restarted, amount_needed is the number needed by this level
     (n_h) of the balancing analysis.
			    
     Note that for systems with many processes writing, it would be