fix_node.c

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

     more layout optimal to calculate the total number needed by all
     levels and then to run reiserfs_new_blocks to get all of them at once.  */

  /* Initiate number_of_freeblk to the amount acquired prior to the restart of
     the analysis or 0 if not restarted, then subtract the amount needed
     by all of the levels of the tree below n_h. */
  /* blknum includes S[n_h], so we subtract 1 in this calculation */
  for ( n_counter = 0, n_number_of_freeblk = p_s_tb->cur_blknum; n_counter < n_h; n_counter++ )
    n_number_of_freeblk -= ( p_s_tb->blknum[n_counter] ) ? (p_s_tb->blknum[n_counter] - 1) : 0;

  /* Allocate missing empty blocks. */
  /* if p_s_Sh == 0  then we are getting a new root */
  n_amount_needed = ( p_s_Sh ) ? (p_s_tb->blknum[n_h] - 1) : 1;
  /*  Amount_needed = the amount that we need more than the amount that we have. */
  if ( n_amount_needed > n_number_of_freeblk )
    n_amount_needed -= n_number_of_freeblk;
  else /* If we have enough already then there is nothing to do. */
    return CARRY_ON;

  if ( reiserfs_new_blocknrs (p_s_tb->transaction_handle, a_n_blocknrs,
			      PATH_PLAST_BUFFER(p_s_tb->tb_path)->b_blocknr, n_amount_needed) == NO_DISK_SPACE )
    return NO_DISK_SPACE;

  /* for each blocknumber we just got, get a buffer and stick it on FEB */
  for ( p_n_blocknr = a_n_blocknrs, n_counter = 0; n_counter < n_amount_needed;
	p_n_blocknr++, n_counter++ ) { 

    RFALSE( ! *p_n_blocknr,
	    "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");

    p_s_new_bh = getblk(p_s_sb->s_dev, *p_n_blocknr, p_s_sb->s_blocksize);
    if (atomic_read (&(p_s_new_bh->b_count)) > 1) {
/*&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&*/
/*
      reiserfs_warning ("waiting for buffer %b, iput inode pid = %d, this pid %d, mode %c, %h\n",
			p_s_new_bh, put_inode_pid, current->pid, p_s_tb->tb_vn->vn_mode, p_s_tb->tb_vn->vn_ins_ih);
      print_tb (0, 0, 0, p_s_tb, "tb");
*/
/*&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&*/
      if (atomic_read(&(p_s_new_bh->b_count)) > 2 || 
          !(buffer_journaled(p_s_new_bh) || buffer_journal_dirty(p_s_new_bh))) {
	n_retval = REPEAT_SEARCH ;
	free_buffers_in_tb (p_s_tb);
	wait_buffer_until_released (p_s_new_bh);
      }
    }
    RFALSE( (atomic_read (&(p_s_new_bh->b_count)) != 1 || 
	     buffer_dirty (p_s_new_bh)) && 
	    (atomic_read(&(p_s_new_bh->b_count)) > 2 || 
	     !(buffer_journaled(p_s_new_bh) || 
	       buffer_journal_dirty(p_s_new_bh))),
	    "PAP-8140: not free or dirty buffer %b for the new block", 
	    p_s_new_bh);
    
    /* Put empty buffers into the array. */
    if (p_s_tb->FEB[p_s_tb->cur_blknum])
      BUG();

    mark_buffer_journal_new(p_s_new_bh) ;
    p_s_tb->FEB[p_s_tb->cur_blknum++] = p_s_new_bh;
  }

  if ( n_retval == CARRY_ON && FILESYSTEM_CHANGED_TB (p_s_tb) )
    n_retval = REPEAT_SEARCH ;

  return n_retval;
}


/* Get free space of the left neighbor, which is stored in the parent
 * node of the left neighbor.  */
static int get_lfree (struct tree_balance * tb, int h)
{
    struct buffer_head * l, * f;
    int order;

    if ((f = PATH_H_PPARENT (tb->tb_path, h)) == 0 || (l = tb->FL[h]) == 0)
	return 0;

    if (f == l)
	order = PATH_H_B_ITEM_ORDER (tb->tb_path, h) - 1;
    else {
	order = B_NR_ITEMS (l);
	f = l;
    }

    return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f,order)));
}


/* Get free space of the right neighbor,
 * which is stored in the parent node of the right neighbor.
 */
static int get_rfree (struct tree_balance * tb, int h)
{
  struct buffer_head * r, * f;
  int order;

  if ((f = PATH_H_PPARENT (tb->tb_path, h)) == 0 || (r = tb->FR[h]) == 0)
    return 0;

  if (f == r)
      order = PATH_H_B_ITEM_ORDER (tb->tb_path, h) + 1;
  else {
      order = 0;
      f = r;
  }

  return (MAX_CHILD_SIZE(f) - dc_size( B_N_CHILD(f,order)));

}


/* Check whether left neighbor is in memory. */
static int  is_left_neighbor_in_cache(
              struct tree_balance * p_s_tb,
              int                   n_h
            ) {
  struct buffer_head  * p_s_father, * left;
  struct super_block  * p_s_sb = p_s_tb->tb_sb;
  unsigned long         n_left_neighbor_blocknr;
  int                   n_left_neighbor_position;

  if ( ! p_s_tb->FL[n_h] ) /* Father of the left neighbor does not exist. */
    return 0;

  /* Calculate father of the node to be balanced. */
  p_s_father = PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1);

  RFALSE( ! p_s_father || 
	  ! B_IS_IN_TREE (p_s_father) || 
	  ! B_IS_IN_TREE (p_s_tb->FL[n_h]) ||
	  ! buffer_uptodate (p_s_father) || 
	  ! buffer_uptodate (p_s_tb->FL[n_h]),
	  "vs-8165: F[h] (%b) or FL[h] (%b) is invalid", 
	  p_s_father, p_s_tb->FL[n_h]);


  /* Get position of the pointer to the left neighbor into the left father. */
  n_left_neighbor_position = ( p_s_father == p_s_tb->FL[n_h] ) ?
                      p_s_tb->lkey[n_h] : B_NR_ITEMS (p_s_tb->FL[n_h]);
  /* Get left neighbor block number. */
  n_left_neighbor_blocknr = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_left_neighbor_position);
  /* Look for the left neighbor in the cache. */
  if ( (left = sb_get_hash_table(p_s_sb, n_left_neighbor_blocknr)) ) {

    RFALSE( buffer_uptodate (left) && ! B_IS_IN_TREE(left),
	    "vs-8170: left neighbor (%b %z) is not in the tree", left, left);
    put_bh(left) ;
    return 1;
  }

  return 0;
}


#define LEFT_PARENTS  'l'
#define RIGHT_PARENTS 'r'


static void decrement_key (struct cpu_key * p_s_key)
{
    // call item specific function for this key
    item_ops[cpu_key_k_type (p_s_key)]->decrement_key (p_s_key);
}




/* Calculate far left/right parent of the left/right neighbor of the current node, that
 * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h].
 * Calculate left/right common parent of the current node and L[h]/R[h].
 * Calculate left/right delimiting key position.
 * Returns:	PATH_INCORRECT   - path in the tree is not correct;
 		SCHEDULE_OCCURRED - schedule occurred while the function worked;
 *	        CARRY_ON         - schedule didn't occur while the function worked;
 */
static int  get_far_parent (struct tree_balance *   p_s_tb,
			    int                     n_h,
			    struct buffer_head  **  pp_s_father,
			    struct buffer_head  **  pp_s_com_father,
			    char                    c_lr_par) 
{
    struct buffer_head  * p_s_parent;
    INITIALIZE_PATH (s_path_to_neighbor_father);
    struct path * p_s_path = p_s_tb->tb_path;
    struct cpu_key	s_lr_father_key;
    int                   n_counter,
	n_position = INT_MAX,
	n_first_last_position = 0,
	n_path_offset = PATH_H_PATH_OFFSET(p_s_path, n_h);

    /* Starting from F[n_h] go upwards in the tree, and look for the common
      ancestor of F[n_h], and its neighbor l/r, that should be obtained. */

    n_counter = n_path_offset;

    RFALSE( n_counter < FIRST_PATH_ELEMENT_OFFSET,
	    "PAP-8180: invalid path length");

  
    for ( ; n_counter > FIRST_PATH_ELEMENT_OFFSET; n_counter--  )  {
	/* Check whether parent of the current buffer in the path is really parent in the tree. */
	if ( ! B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_path, n_counter - 1)) )
	    return REPEAT_SEARCH;
	/* Check whether position in the parent is correct. */
	if ( (n_position = PATH_OFFSET_POSITION(p_s_path, n_counter - 1)) > B_NR_ITEMS(p_s_parent) )
	    return REPEAT_SEARCH;
	/* Check whether parent at the path really points to the child. */
	if ( B_N_CHILD_NUM(p_s_parent, n_position) !=
	     PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr )
	    return REPEAT_SEARCH;
	/* Return delimiting key if position in the parent is not equal to first/last one. */
	if ( c_lr_par == RIGHT_PARENTS )
	    n_first_last_position = B_NR_ITEMS (p_s_parent);
	if ( n_position != n_first_last_position ) {
	    *pp_s_com_father = p_s_parent;
	    get_bh(*pp_s_com_father) ;
	    /*(*pp_s_com_father = p_s_parent)->b_count++;*/
	    break;
	}
    }

    /* if we are in the root of the tree, then there is no common father */
    if ( n_counter == FIRST_PATH_ELEMENT_OFFSET ) {
	/* Check whether first buffer in the path is the root of the tree. */
	if ( PATH_OFFSET_PBUFFER(p_s_tb->tb_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
	     SB_ROOT_BLOCK (p_s_tb->tb_sb) ) {
	    *pp_s_father = *pp_s_com_father = NULL;
	    return CARRY_ON;
	}
	return REPEAT_SEARCH;
    }

    RFALSE( B_LEVEL (*pp_s_com_father) <= DISK_LEAF_NODE_LEVEL,
	    "PAP-8185: (%b %z) level too small", 
	    *pp_s_com_father, *pp_s_com_father);

    /* Check whether the common parent is locked. */

    if ( buffer_locked (*pp_s_com_father) ) {
	__wait_on_buffer(*pp_s_com_father);
	if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) {
	    decrement_bcount(*pp_s_com_father);
	    return REPEAT_SEARCH;
	}
    }

    /* So, we got common parent of the current node and its left/right neighbor.
     Now we are geting the parent of the left/right neighbor. */

    /* Form key to get parent of the left/right neighbor. */
    le_key2cpu_key (&s_lr_father_key, B_N_PDELIM_KEY(*pp_s_com_father, ( c_lr_par == LEFT_PARENTS ) ?
						     (p_s_tb->lkey[n_h - 1] = n_position - 1) : (p_s_tb->rkey[n_h - 1] = n_position)));


    if ( c_lr_par == LEFT_PARENTS )
	decrement_key(&s_lr_father_key);

    if (search_by_key(p_s_tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father, n_h + 1) == IO_ERROR)
	// path is released
	return IO_ERROR;

    if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) {
	decrement_counters_in_path(&s_path_to_neighbor_father);
	decrement_bcount(*pp_s_com_father);
	return REPEAT_SEARCH;
    }

    *pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);

    RFALSE( B_LEVEL (*pp_s_father) != n_h + 1,
	    "PAP-8190: (%b %z) level too small", *pp_s_father, *pp_s_father);
    RFALSE( s_path_to_neighbor_father.path_length < FIRST_PATH_ELEMENT_OFFSET,
	    "PAP-8192: path length is too small");

    s_path_to_neighbor_father.path_length--;
    decrement_counters_in_path(&s_path_to_neighbor_father);
    return CARRY_ON;
}


/* Get parents of neighbors of node in the path(S[n_path_offset]) and common parents of
 * S[n_path_offset] and L[n_path_offset]/R[n_path_offset]: F[n_path_offset], FL[n_path_offset],
 * FR[n_path_offset], CFL[n_path_offset], CFR[n_path_offset].
 * Calculate numbers of left and right delimiting keys position: lkey[n_path_offset], rkey[n_path_offset].
 * Returns:	SCHEDULE_OCCURRED - schedule occurred while the function worked;
 *	        CARRY_ON - schedule didn't occur while the function worked;
 */
static int  get_parents (struct tree_balance * p_s_tb, int n_h)
{
    struct path         * p_s_path = p_s_tb->tb_path;
    int                   n_position,
	n_ret_value,
	n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
    struct buffer_head  * p_s_curf,
	* p_s_curcf;

    /* Current node is the root of the tree or will be root of the tree */
    if ( n_path_offset <= FIRST_PATH_ELEMENT_OFFSET ) {
	/* The root can not have parents.
	   Release nodes which previously were obtained as parents of the current node neighbors. */
	decrement_bcount(p_s_tb->FL[n_h]);
	decrement_bcount(p_s_tb->CFL[n_h]);
	decrement_bcount(p_s_tb->FR[n_h]);
	decrement_bcount(p_s_tb->CFR[n_h]);
	p_s_tb->FL[n_h] = p_s_tb->CFL[n_h] = p_s_tb->FR[n_h] = p_s_tb->CFR[n_h] = NULL;
	return CARRY_ON;
    }
  
    /* Get parent FL[n_path_offset] of L[n_path_offset]. */
    if ( (n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1)) )  {
	/* Current node is not the first child of its parent. */
	/*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2;*/
	p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
	get_bh(p_s_curf) ;
	get_bh(p_s_curf) ;
	p_s_tb->lkey[n_h] = n_position - 1;
    }
    else  {
	/* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node.
	   Calculate current common parent of L[n_path_offset] and the current node. Note that
	   CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset].
	   Calculate lkey[n_path_offset]. */
	if ( (n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf,
					   &p_s_curcf, LEFT_PARENTS)) != CARRY_ON )
	    return n_ret_value;
    }

    decrement_bcount(p_s_tb->FL[n_h]);
    p_s_tb->FL[n_h] = p_s_curf; /* New initialization of FL[n_h]. */
    decrement_bcount(p_s_tb->CFL[n_h]);
    p_s_tb->CFL[n_h] = p_s_curcf; /* New initialization of CFL[n_h]. */

    RFALSE( (p_s_curf && !B_IS_IN_TREE (p_s_curf)) || 
	    (p_s_curcf && !B_IS_IN_TREE (p_s_curcf)),
	    "PAP-8195: FL (%b) or CFL (%b) is invalid", p_s_curf, p_s_curcf);

/* Get parent FR[n_h] of R[n_h]. */

/* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */
    if ( n_position == B_NR_ITEMS (PATH_H_PBUFFER(p_s_path, n_h + 1)) ) {
/* Calculate current parent of R[n_h], which is the right neighbor of F[n_h].
   Calculate current common parent of R[n_h] and current node. Note that CFR[n_h]
   not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */
	if ( (n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf,  &p_s_curcf, RIGHT_PARENTS)) != CARRY_ON )
	    return n_ret_value;
    }
    else {
/* Current node is not the last child of its parent F[n_h]. */
	/*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2;*/
	p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
	get_bh(p_s_curf) ;
	get_bh(p_s_curf) ;
	p_s_tb->rkey[n_h] = n_position;
    }	

    decrement_bcount(p_s_tb->FR[n_h]);
    p_s_tb->FR[n_h] = p_s_curf; /* New initialization of FR[n_path_offset]. */
    
    decrement_bcount(p_s_tb->CFR[n_h]);
    p_s_tb->CFR[n_h] = p_s_curcf; /* New initialization of CFR[n_path_offset]. */

    RFALSE( (p_s_curf && !B_IS_IN_TREE (p_s_curf)) ||
            (p_s_curcf && !B_IS_IN_TREE (p_s_curcf)),
	    "PAP-8205: FR (%b) or CFR (%b) is invalid", p_s_curf, p_s_curcf);

    return CARRY_ON;
}


/* it is possible to remove node as result of shiftings to
   neighbors even when we insert or paste item. */
static inline int can_node_be_removed (int mode, int lfree, int sfree, int rfree, struct tree_balance * tb, int h)
{
    struct buffer_head * Sh = PATH_H_PBUFFER (tb->tb_path, h);
    int levbytes = tb->insert_size[h];
    struct item_head * ih;
    struct key * r_key = NULL;

    ih = B_N_PITEM_HEAD (Sh, 0);
    if ( tb->CFR[h] )
	r_key = B_N_PDELIM_KEY(tb->CFR[h],tb->rkey[h]);
  
    if (
	lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
	/* shifting may merge items which might save space */
	- (( ! h && op_is_left_mergeable (&(ih->ih_key), Sh->b_size) ) ? IH_SIZE : 0)
	- (( ! h && r_key && op_is_left_mergeable (r_key, Sh->b_size) ) ? IH_SIZE : 0)