do_balan.c

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

    bi.bi_bh = first_b = tb->FEB[i];
    bi.bi_parent = 0;
    bi.bi_position = 0;
    make_empty_node (&bi);
    set_bit(BH_Uptodate, &first_b->b_state);
    tb->FEB[i] = 0;
    tb->used[i] = first_b;

    return(first_b);
}


/* This is now used because reiserfs_free_block has to be able to
** schedule.
*/
static void store_thrown (struct tree_balance * tb, struct buffer_head * bh)
{
    int i;

    if (buffer_dirty (bh))
      printk ("store_thrown deals with dirty buffer\n");
    for (i = 0; i < sizeof (tb->thrown)/sizeof (tb->thrown[0]); i ++)
	if (!tb->thrown[i]) {
	    tb->thrown[i] = bh;
	    get_bh(bh) ; /* free_thrown puts this */
	    return;
	}
    reiserfs_warning ("store_thrown: too many thrown buffers\n");
}

static void free_thrown(struct tree_balance *tb) {
    int i ;
    unsigned long blocknr ;
    for (i = 0; i < sizeof (tb->thrown)/sizeof (tb->thrown[0]); i++) {
	if (tb->thrown[i]) {
	    blocknr = tb->thrown[i]->b_blocknr ;
	    if (buffer_dirty (tb->thrown[i]))
	      printk ("free_thrown deals with dirty buffer %ld\n", blocknr);
	    brelse(tb->thrown[i]) ; /* incremented in store_thrown */
	    reiserfs_free_block (tb->transaction_handle, blocknr);
	}
    }
}

void reiserfs_invalidate_buffer (struct tree_balance * tb, struct buffer_head * bh)
{
    struct block_head *blkh;
    blkh = B_BLK_HEAD(bh);
    set_blkh_level( blkh, FREE_LEVEL );
    set_blkh_nr_item( blkh, 0 );
    
    mark_buffer_clean (bh);
    /* reiserfs_free_block is no longer schedule safe 
    reiserfs_free_block (tb->transaction_handle, tb->tb_sb, bh->b_blocknr);
    */

    store_thrown (tb, bh);
}

/* Replace n_dest'th key in buffer dest by n_src'th key of buffer src.*/
void replace_key (struct tree_balance * tb, struct buffer_head * dest, int n_dest,
		  struct buffer_head * src, int n_src)
{

    RFALSE( dest == NULL || src == NULL,
	    "vs-12305: source or destination buffer is 0 (src=%p, dest=%p)",
	    src, dest);
    RFALSE( ! B_IS_KEYS_LEVEL (dest),
	    "vs-12310: invalid level (%z) for destination buffer. dest must be leaf",
	    dest);
    RFALSE( n_dest < 0 || n_src < 0,
	    "vs-12315: src(%d) or dest(%d) key number < 0", n_src, n_dest);
    RFALSE( n_dest >= B_NR_ITEMS(dest) || n_src >= B_NR_ITEMS(src),
	    "vs-12320: src(%d(%d)) or dest(%d(%d)) key number is too big",
	    n_src, B_NR_ITEMS(src), n_dest, B_NR_ITEMS(dest));
   
    if (B_IS_ITEMS_LEVEL (src))
	/* source buffer contains leaf node */
	memcpy (B_N_PDELIM_KEY(dest,n_dest), B_N_PITEM_HEAD(src,n_src), KEY_SIZE);
    else
	memcpy (B_N_PDELIM_KEY(dest,n_dest), B_N_PDELIM_KEY(src,n_src), KEY_SIZE);

    do_balance_mark_internal_dirty (tb, dest, 0);
}


int get_left_neighbor_position (
				struct tree_balance * tb, 
				int h
				)
{
  int Sh_position = PATH_H_POSITION (tb->tb_path, h + 1);

  RFALSE( PATH_H_PPARENT (tb->tb_path, h) == 0 || tb->FL[h] == 0,
	  "vs-12325: FL[%d](%p) or F[%d](%p) does not exist", 
	  h, tb->FL[h], h, PATH_H_PPARENT (tb->tb_path, h));

  if (Sh_position == 0)
    return B_NR_ITEMS (tb->FL[h]);
  else
    return Sh_position - 1;
}


int get_right_neighbor_position (struct tree_balance * tb, int h)
{
  int Sh_position = PATH_H_POSITION (tb->tb_path, h + 1);

  RFALSE( PATH_H_PPARENT (tb->tb_path, h) == 0 || tb->FR[h] == 0,
	  "vs-12330: F[%d](%p) or FR[%d](%p) does not exist", 
	  h, PATH_H_PPARENT (tb->tb_path, h), h, tb->FR[h]);

  if (Sh_position == B_NR_ITEMS (PATH_H_PPARENT (tb->tb_path, h)))
    return 0;
  else
    return Sh_position + 1;
}


#ifdef CONFIG_REISERFS_CHECK

int is_reusable (struct super_block * s, unsigned long block, int bit_value);
static void check_internal_node (struct super_block * s, struct buffer_head * bh, char * mes)
{
  struct disk_child * dc;
  int i;

  RFALSE( !bh, "PAP-12336: bh == 0");

  if (!bh || !B_IS_IN_TREE (bh))
    return;
 
  RFALSE( !buffer_dirty (bh) && 
	  !(buffer_journaled(bh) || buffer_journal_dirty(bh)),
	  "PAP-12337: buffer (%b) must be dirty", bh);
  dc = B_N_CHILD (bh, 0);

  for (i = 0; i <= B_NR_ITEMS (bh); i ++, dc ++) {
    if (!is_reusable (s, dc_block_number(dc), 1) ) {
      print_cur_tb (mes);
      reiserfs_panic (s, "PAP-12338: check_internal_node: invalid child pointer %y in %b", dc, bh);
    }
  }
}


static int locked_or_not_in_tree (struct buffer_head * bh, char * which)
{
  if ( buffer_locked (bh) || !B_IS_IN_TREE (bh) ) {
    reiserfs_warning ("vs-12339: locked_or_not_in_tree: %s (%b)\n", which, bh);
    return 1;
  } 
  return 0;
}


static int check_before_balancing (struct tree_balance * tb)
{
  int retval = 0;	

  if ( cur_tb ) {
    reiserfs_panic (tb->tb_sb, "vs-12335: check_before_balancing: "
		    "suspect that schedule occurred based on cur_tb not being null at this point in code. "
		    "do_balance cannot properly handle schedule occuring while it runs.");
  }
  
  /* double check that buffers that we will modify are unlocked. (fix_nodes should already have
     prepped all of these for us). */
  if ( tb->lnum[0] ) {
    retval |= locked_or_not_in_tree (tb->L[0], "L[0]");
    retval |= locked_or_not_in_tree (tb->FL[0], "FL[0]");
    retval |= locked_or_not_in_tree (tb->CFL[0], "CFL[0]");
    check_leaf (tb->L[0]);
  }
  if ( tb->rnum[0] ) {
    retval |= locked_or_not_in_tree (tb->R[0], "R[0]");
    retval |= locked_or_not_in_tree (tb->FR[0], "FR[0]");
    retval |= locked_or_not_in_tree (tb->CFR[0], "CFR[0]");
    check_leaf (tb->R[0]);
  }
  retval |= locked_or_not_in_tree (PATH_PLAST_BUFFER (tb->tb_path), "S[0]");
  check_leaf (PATH_PLAST_BUFFER (tb->tb_path));

  return retval;
}


void check_after_balance_leaf (struct tree_balance * tb)
{
    if (tb->lnum[0]) {
	if (B_FREE_SPACE (tb->L[0]) != 
	    MAX_CHILD_SIZE (tb->L[0]) - dc_size(B_N_CHILD (tb->FL[0], get_left_neighbor_position (tb, 0)))) {
	    print_cur_tb ("12221");
	    reiserfs_panic (tb->tb_sb, "PAP-12355: check_after_balance_leaf: shift to left was incorrect");
	}
    }
    if (tb->rnum[0]) {
	if (B_FREE_SPACE (tb->R[0]) != 
	    MAX_CHILD_SIZE (tb->R[0]) - dc_size(B_N_CHILD (tb->FR[0], get_right_neighbor_position (tb, 0)))) {
	    print_cur_tb ("12222");
	    reiserfs_panic (tb->tb_sb, "PAP-12360: check_after_balance_leaf: shift to right was incorrect");
	}
    }
    if (PATH_H_PBUFFER(tb->tb_path,1) &&
	(B_FREE_SPACE (PATH_H_PBUFFER(tb->tb_path,0)) != 
		    (MAX_CHILD_SIZE (PATH_H_PBUFFER(tb->tb_path,0)) -
		    dc_size(B_N_CHILD (PATH_H_PBUFFER(tb->tb_path,1),
		    PATH_H_POSITION (tb->tb_path, 1)))) )) {
	int left = B_FREE_SPACE (PATH_H_PBUFFER(tb->tb_path,0));
	int right = (MAX_CHILD_SIZE (PATH_H_PBUFFER(tb->tb_path,0)) -
		    dc_size(B_N_CHILD (PATH_H_PBUFFER(tb->tb_path,1),
			PATH_H_POSITION (tb->tb_path, 1))));
	print_cur_tb ("12223");
	reiserfs_warning(
	    "B_FREE_SPACE (PATH_H_PBUFFER(tb->tb_path,0)) = %d; "
    	    "MAX_CHILD_SIZE (%d) - dc_size( %y, %d ) [%d] = %d\n",
	    left,
	    MAX_CHILD_SIZE (PATH_H_PBUFFER(tb->tb_path,0)),
	    PATH_H_PBUFFER(tb->tb_path,1),
	    PATH_H_POSITION (tb->tb_path, 1),
	    dc_size(B_N_CHILD (PATH_H_PBUFFER(tb->tb_path,1), PATH_H_POSITION (tb->tb_path, 1 )) ),
	    right );
	reiserfs_panic (tb->tb_sb, "PAP-12365: check_after_balance_leaf: S is incorrect");
    }
}


void check_leaf_level (struct tree_balance * tb)
{
  check_leaf (tb->L[0]);
  check_leaf (tb->R[0]);
  check_leaf (PATH_PLAST_BUFFER (tb->tb_path));
}

void check_internal_levels (struct tree_balance * tb)
{
  int h;

  /* check all internal nodes */
  for (h = 1; tb->insert_size[h]; h ++) {
    check_internal_node (tb->tb_sb, PATH_H_PBUFFER (tb->tb_path, h), "BAD BUFFER ON PATH");
    if (tb->lnum[h])
      check_internal_node (tb->tb_sb, tb->L[h], "BAD L");
    if (tb->rnum[h])
      check_internal_node (tb->tb_sb, tb->R[h], "BAD R");
  }

}

#endif






/* Now we have all of the buffers that must be used in balancing of
   the tree.  We rely on the assumption that schedule() will not occur
   while do_balance works. ( Only interrupt handlers are acceptable.)
   We balance the tree according to the analysis made before this,
   using buffers already obtained.  For SMP support it will someday be
   necessary to add ordered locking of tb. */

/* Some interesting rules of balancing:

   we delete a maximum of two nodes per level per balancing: we never
   delete R, when we delete two of three nodes L, S, R then we move
   them into R.

   we only delete L if we are deleting two nodes, if we delete only
   one node we delete S

   if we shift leaves then we shift as much as we can: this is a
   deliberate policy of extremism in node packing which results in
   higher average utilization after repeated random balance operations
   at the cost of more memory copies and more balancing as a result of
   small insertions to full nodes.

   if we shift internal nodes we try to evenly balance the node
   utilization, with consequent less balancing at the cost of lower
   utilization.

   one could argue that the policy for directories in leaves should be
   that of internal nodes, but we will wait until another day to
   evaluate this....  It would be nice to someday measure and prove
   these assumptions as to what is optimal....

*/

static inline void do_balance_starts (struct tree_balance *tb)
{
    /* use print_cur_tb() to see initial state of struct
       tree_balance */

    /* store_print_tb (tb); */

    /* do not delete, just comment it out */
/*    print_tb(flag, PATH_LAST_POSITION(tb->tb_path), tb->tb_path->pos_in_item, tb, 
	     "check");*/
    RFALSE( check_before_balancing (tb), "PAP-12340: locked buffers in TB");
#ifdef CONFIG_REISERFS_CHECK
    cur_tb = tb;
#endif
}


static inline void do_balance_completed (struct tree_balance * tb)
{
    
#ifdef CONFIG_REISERFS_CHECK
    check_leaf_level (tb);
    check_internal_levels (tb);
    cur_tb = NULL;
#endif

    /* reiserfs_free_block is no longer schedule safe.  So, we need to
    ** put the buffers we want freed on the thrown list during do_balance,
    ** and then free them now
    */

    tb->tb_sb->u.reiserfs_sb.s_do_balance ++;


    /* release all nodes hold to perform the balancing */
    unfix_nodes(tb);

    free_thrown(tb) ;
}





void do_balance (struct tree_balance * tb, /* tree_balance structure */
		 struct item_head * ih,	   /* item header of inserted item */
		 const char * body,  /* body  of inserted item or bytes to paste */
		 int flag)  /* i - insert, d - delete
			       c - cut, p - paste
						      
			       Cut means delete part of an item
			       (includes removing an entry from a
			       directory).
						      
			       Delete means delete whole item.
						      
			       Insert means add a new item into the
			       tree.
						      						      
			       Paste means to append to the end of an
			       existing file or to insert a directory
			       entry.  */
{
    int child_pos, /* position of a child node in its parent */
	h;	   /* level of the tree being processed */
    struct item_head insert_key[2]; /* in our processing of one level
				       we sometimes determine what
				       must be inserted into the next
				       higher level.  This insertion
				       consists of a key or two keys
				       and their corresponding
				       pointers */
    struct buffer_head *insert_ptr[2]; /* inserted node-ptrs for the next
					  level */

    tb->tb_mode = flag;
    tb->need_balance_dirty = 0;

    if (FILESYSTEM_CHANGED_TB(tb)) {
        reiserfs_panic(tb->tb_sb, "clm-6000: do_balance, fs generation has changed\n") ;
    }
    /* if we have no real work to do  */
    if ( ! tb->insert_size[0] ) {
	reiserfs_warning ("PAP-12350: do_balance: insert_size == 0, mode == %c",
			  flag);
	unfix_nodes(tb);
	return;
    }

    atomic_inc (&(fs_generation (tb->tb_sb)));
    do_balance_starts (tb);
    
	/* balance leaf returns 0 except if combining L R and S into
	   one node.  see balance_internal() for explanation of this
	   line of code.*/
	child_pos = PATH_H_B_ITEM_ORDER (tb->tb_path, 0) +
	  balance_leaf (tb, ih, body, flag, insert_key, insert_ptr);

#ifdef CONFIG_REISERFS_CHECK
    check_after_balance_leaf (tb);
#endif

    /* Balance internal level of the tree. */
    for ( h = 1; h < MAX_HEIGHT && tb->insert_size[h]; h++ )
	child_pos = balance_internal (tb, h, child_pos, insert_key, insert_ptr);


    do_balance_completed (tb);

}