do_balan.c

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

			    /* new directory entry falls into S_new[i] */
		  
			    /* Shift snum[i]-1 items in whole. Shift sbytes[i] directory entries from directory item number snum[i] */
			    leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i]-1, S_new[i]);

			    /* Paste given directory entry to directory item */
			    bi.bi_bh = S_new[i];
			    bi.bi_parent = 0;
			    bi.bi_position = 0;
			    leaf_paste_in_buffer (tb->tb_fs, &bi, 0, pos_in_item - entry_count + sbytes[i] - 1,
						  tb->insert_size[0], body,zeros_number);
			    /* paste new directory entry */
			    leaf_paste_entries (
				bi.bi_bh, 0, pos_in_item - entry_count + sbytes[i] - 1,
				1, (struct reiserfs_de_head *)body, body + DEH_SIZE,
				tb->insert_size[0]
				);
			    tb->insert_size[0] = 0;
			    pos_in_item++;
			} else { /* new directory entry doesn't fall into S_new[i] */
			    leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i], S_new[i]);
			}
		    }
		    else /* regular object */
		    {
			int n_shift, n_rem, r_zeros_number;
			const char * r_body;
			struct item_head * tmp;

			/* Calculate number of bytes which must be shifted from appended item */
			n_shift = sbytes[i] - tb->insert_size[0];
			if ( n_shift < 0 )
			    n_shift = 0;
			leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], n_shift, S_new[i]);

			/* Calculate number of bytes which must remain in body after append to S_new[i] */
			n_rem = tb->insert_size[0] - sbytes[i];
			if ( n_rem < 0 )
			    n_rem = 0;
			/* Append part of body into S_new[0] */
			bi.bi_bh = S_new[i];
			bi.bi_parent = 0;
			bi.bi_position = 0;

			if ( n_rem > zeros_number ) {
			    r_zeros_number = 0;
			    r_body = body + n_rem - zeros_number;
			}
			else {
			    r_body = body;
			    r_zeros_number = zeros_number - n_rem;
			    zeros_number -= r_zeros_number;
			}

			leaf_paste_in_buffer(tb->tb_fs, &bi, 0, n_shift, tb->insert_size[0]-n_rem, r_body,r_zeros_number);
			tmp = B_N_PITEM_HEAD (S_new[i], 0);
			if (I_IS_INDIRECT_ITEM(tmp)) {
/*			
			    if (n_rem)
				reiserfs_panic ("PAP-12230: balance_leaf: "
						"invalid action with indirect item");
			    set_ih_free_space (tmp, 0);
*/
			    set_ih_free_space (tmp, 0);
			    set_offset( key_format (&tmp->ih_key), &tmp->ih_key, get_offset(&tmp->ih_key) +
				(n_rem / UNFM_P_SIZE) * tb->tb_fs->fs_blocksize);
			} else
				set_offset (key_format (&tmp->ih_key), &tmp->ih_key, get_offset (&tmp->ih_key) + n_rem);

			//B_N_PKEY(S_new[i],0)->k_offset += n_rem;
//			

			tb->insert_size[0] = n_rem;
			if ( ! n_rem )
			    pos_in_item++;
		    }
		}
		else
		    /* item falls wholly into S_new[i] */
		{
		    struct item_head * pasted;
		
		    leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i], S_new[i]);
		    /* paste into item */
		    bi.bi_bh = S_new[i];
		    bi.bi_parent = 0;
		    bi.bi_position = 0;
		    leaf_paste_in_buffer(tb->tb_fs, &bi, item_pos - n + snum[i], pos_in_item, tb->insert_size[0], body, zeros_number);

		    pasted = B_N_PITEM_HEAD(S_new[i], item_pos - n + snum[i]);
		    if (I_IS_DIRECTORY_ITEM (pasted)) {
			leaf_paste_entries (bi.bi_bh, item_pos - n + snum[i], pos_in_item, 1, 
					    (struct reiserfs_de_head *)body, body + DEH_SIZE, tb->insert_size[0]);
		    }

		    /* if we paste to indirect item update ih_free_space */
		    if (I_IS_INDIRECT_ITEM (pasted))
			set_ih_free_space (pasted, 0);
		    zeros_number = tb->insert_size[0] = 0;
		}
	    } else {
		/* pasted item doesn't fall into S_new[i] */
		leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i], S_new[i]);
	    }
	    break;

	default:    /* cases d and t */
	    reiserfs_panic ("PAP-12245: balance_leaf: blknum > 2: unexpectable mode: %s(%d)",
			    (flag == M_DELETE) ? "DELETE" : ((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
	}

	memcpy (insert_key + i,B_N_PKEY(S_new[i],0),KEY_SIZE);
	insert_ptr[i] = S_new[i];
    }

    /* if the affected item was not wholly shifted then we perform all
       necessary operations on that part or whole of the affected item which
       remains in S */
    if ( 0 <= item_pos && item_pos < tb->s0num ) {
	/* if we must insert or append into buffer S[0] */

	switch (flag) {
	case M_INSERT:   /* insert item into S[0] */
	    bi.bi_bh = tbS0;
	    bi.bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
	    bi.bi_position = PATH_H_POSITION (tb->tb_path, 1);
	    leaf_insert_into_buf (tb->tb_fs, &bi, item_pos, ih, body, zeros_number);

	    /* If we insert the first key change the delimiting key */
	    if( item_pos == 0 ) {
		if (tb->CFL[0]) /* can be 0 in reiserfsck */
		    replace_key (tb->tb_fs, tb->CFL[0], tb->lkey[0],tbS0,0);
	    }
	    break;

	case M_PASTE: {  /* append item in S[0] */
	    struct item_head * pasted;

	    pasted = B_N_PITEM_HEAD (tbS0, item_pos);
	    /* when directory, may be new entry already pasted */
	    if (I_IS_DIRECTORY_ITEM (pasted)) {
		if ( pos_in_item >= 0 && pos_in_item <= get_ih_entry_count (pasted) ) {
		    /* prepare space */
		    bi.bi_bh = tbS0;
		    bi.bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
		    bi.bi_position = PATH_H_POSITION (tb->tb_path, 1);
		    leaf_paste_in_buffer(tb->tb_fs, &bi, item_pos, pos_in_item, tb->insert_size[0], body, zeros_number);

		    /* paste entry */
		    leaf_paste_entries (bi.bi_bh, item_pos, pos_in_item, 1, (struct reiserfs_de_head *)body,
					body + DEH_SIZE, tb->insert_size[0]);
		    if ( ! item_pos && ! pos_in_item ) {
			if (tb->CFL[0])  // can be 0 in reiserfsck
			    replace_key(tb->tb_fs, tb->CFL[0], tb->lkey[0],tbS0,0);
		    }
		    tb->insert_size[0] = 0;
		}
	    } else { /* regular object */
		if ( pos_in_item == get_ih_item_len (pasted) ) {
		    bi.bi_bh = tbS0;
		    bi.bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
		    bi.bi_position = PATH_H_POSITION (tb->tb_path, 1);
		    leaf_paste_in_buffer (tb->tb_fs, &bi, item_pos, pos_in_item, tb->insert_size[0], body, zeros_number);

		    if (I_IS_INDIRECT_ITEM (pasted)) {
			set_ih_free_space (pasted, 0);
		    }
		    tb->insert_size[0] = 0;
		}
	    }
	} /* case M_PASTE: */
	}
    }

    return 0;
} /* Leaf level of the tree is balanced (end of balance_leaf) */


void make_empty_leaf (struct buffer_head * bh)
{
    set_blkh_nr_items (B_BLK_HEAD (bh), 0);
    set_blkh_free_space (B_BLK_HEAD (bh), MAX_FREE_SPACE (bh->b_size));
    set_blkh_level (B_BLK_HEAD (bh), DISK_LEAF_NODE_LEVEL);
}


/* Make empty node */
void make_empty_node (struct buffer_info * bi)
{
    make_empty_leaf (bi->bi_bh);

    if (bi->bi_parent)
	set_dc_child_size (B_N_CHILD (bi->bi_parent, bi->bi_position), 0);
}


/* Get first empty buffer */
struct buffer_head * get_FEB (struct tree_balance * tb)
{
    int i;
    struct buffer_head * first_b;
    struct buffer_info bi;

    for (i = 0; i < MAX_FEB_SIZE; i ++)
	if (tb->FEB[i] != 0)
	    break;

    if (i == MAX_FEB_SIZE)
	reiserfs_panic("vs-12300: get_FEB: FEB list is empty");

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

    tb->FEB[i] = 0;
    tb->used[i] = first_b;

    return(first_b);
}


/* Replace n_dest'th key in buffer dest by n_src'th key of buffer src.*/
void replace_key (reiserfs_filsys_t * fs,
		  struct buffer_head * dest, int n_dest,
		  struct buffer_head * src, int n_src)
{
    if (dest) {
	if (is_leaf_node (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);
	
	mark_buffer_dirty(dest);
    }
}


void reiserfs_invalidate_buffer (struct tree_balance * tb, struct buffer_head * bh, int do_free_block)
{
    set_blkh_level (B_BLK_HEAD (bh), FREE_LEVEL);
    misc_clear_bit(BH_Dirty, &bh->b_state);

    if (do_free_block) {
	struct buffer_head * to_be_forgotten;

	to_be_forgotten = find_buffer (bh->b_dev, bh->b_blocknr, bh->b_size);
	if (to_be_forgotten) {
	    to_be_forgotten->b_count ++;
	    bforget (to_be_forgotten);
	}

	reiserfs_free_block (tb->tb_fs, bh->b_blocknr);
    }
}


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

  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);

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

/* 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....

*/

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 zeros_num)
{
    //int pos_in_item = tb->tb_path->pos_in_item;
    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 */

    /* if we have no real work to do  */
    if ( ! tb->insert_size[0] ) {
	unfix_nodes(/*th,*/ tb);
	return;
    }

    if (flag == M_INTERNAL) {
	insert_ptr[0] = (struct buffer_head *)body;
	/* we must prepare insert_key */

	if (PATH_H_B_ITEM_ORDER (tb->tb_path, 0)/*LAST_POSITION (tb->tb_path)*//*item_pos*/ == -1) {
		/* get delimiting key from buffer in tree */
		copy_key (&insert_key[0].ih_key, B_N_PKEY (PATH_PLAST_BUFFER (tb->tb_path), 0));
		/*insert_ptr[0]->b_item_order = 0;*/
	} else {
	    /* get delimiting key from new buffer */
	    copy_key (&insert_key[0].ih_key, B_N_PKEY((struct buffer_head *)body,0));
	    /*insert_ptr[0]->b_item_order = item_pos;*/
	}
      
	/* and insert_ptr instead of balance_leaf */
	child_pos = PATH_H_B_ITEM_ORDER (tb->tb_path, 0)/*item_pos*/;
    } else
	/* 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 (/*th,*/ tb/*, pos_in_item*/, ih, body, flag, zeros_num, insert_key, insert_ptr);

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

    /* Release all (except for S[0]) non NULL buffers fixed by fix_nodes() */
    unfix_nodes(/*th,*/ tb);
}