do_balan.c

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

/*
 * Copyright 1996-2004 by Hans Reiser, licensing governed by 
 * reiserfsprogs/README
 */

/* Now we have all buffers that must be used in balancing of the tree 	*/
/* Further calculations can not cause schedule(), and thus the buffer 	*/
/* tree will be stable until the balancing will be finished 		*/
/* balance the tree according to the analysis made before,		*/
/* and using buffers obtained after all above.				*/


/**
 ** balance_leaf_when_delete
 ** balance_leaf
 ** do_balance
 **
 **/

#include "includes.h"

/* summary:
 if deleting something ( tb->insert_size[0] < 0 )
   return(balance_leaf_when_delete()); (flag d handled here)
 else
   if lnum is larger than 0 we put items into the left node
   if rnum is larger than 0 we put items into the right node
   if snum1 is larger than 0 we put items into the new node s1
   if snum2 is larger than 0 we put items into the new node s2 
Note that all *num* count new items being created.

It would be easier to read balance_leaf() if each of these summary
lines was a separate procedure rather than being inlined.  I think
that there are many passages here and in balance_leaf_when_delete() in
which two calls to one procedure can replace two passages, and it
might save cache space and improve software maintenance costs to do so.  

Vladimir made the perceptive comment that we should offload most of
the decision making in this function into fix_nodes/check_balance, and
then create some sort of structure in tb that says what actions should
be performed by do_balance.

-Hans */



/* Balance leaf node in case of delete or cut: insert_size[0] < 0
 *
 * lnum, rnum can have values >= -1
 *	-1 means that the neighbor must be joined with S
 *	 0 means that nothing should be done with the neighbor
 *	>0 means to shift entirely or partly the specified number of items to the neighbor
 */
static int balance_leaf_when_delete (/*struct reiserfs_transaction_handle *th,*/
				     struct tree_balance * tb, 
				     int flag)
{
    struct buffer_head * tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
    int item_pos = PATH_LAST_POSITION (tb->tb_path);
    int pos_in_item = tb->tb_path->pos_in_item;
    struct buffer_info bi;
    int n;
    struct item_head * ih;

    ih = B_N_PITEM_HEAD (tbS0, item_pos);

    /* Delete or truncate the item */

    switch (flag) {
    case M_DELETE:   /* delete item in 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_delete_items (tb->tb_fs, &bi, 0, item_pos, 1, -1);

	if ( ! item_pos ) {
	    // we have removed first item in the node - update left delimiting key
	    if ( B_NR_ITEMS(tbS0) ) {
		replace_key(tb->tb_fs, tb->CFL[0],tb->lkey[0],tbS0,0);
	    }
	    else {
		if ( ! PATH_H_POSITION (tb->tb_path, 1) )
		    replace_key(tb->tb_fs, tb->CFL[0],tb->lkey[0],PATH_H_PPARENT(tb->tb_path, 0),0);
	    }
	} 
    
	break;

    case M_CUT: {  /* cut item in 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);
	if (I_IS_DIRECTORY_ITEM (ih)) {
	    /* UFS unlink semantics are such that you can only delete
               one directory entry at a time. */
	    /* when we cut a directory tb->insert_size[0] means number
               of entries to be cut (always 1) */
	    tb->insert_size[0] = -1;
	    leaf_cut_from_buffer (tb->tb_fs, &bi, item_pos, pos_in_item, -tb->insert_size[0]);

	    if ( ! item_pos && ! pos_in_item ) {
		replace_key(tb->tb_fs, tb->CFL[0],tb->lkey[0],tbS0,0);
	    }
	} else {
	    leaf_cut_from_buffer (tb->tb_fs, &bi, item_pos, pos_in_item, -tb->insert_size[0]);
	}
	break;
    }

    default:
	print_tb(flag, item_pos, pos_in_item, tb,"when_del");
	reiserfs_panic ("PAP-12040: balance_leaf_when_delete: unexpectable mode: %s(%d)",
			(flag == M_PASTE) ? "PASTE" : ((flag == M_INSERT) ? "INSERT" : "UNKNOWN"), flag);
    }

    /* the rule is that no shifting occurs unless by shifting a node can be freed */
    n = B_NR_ITEMS(tbS0);
    if ( tb->lnum[0] )     /* L[0] takes part in balancing */
    {
	if ( tb->lnum[0] == -1 )    /* L[0] must be joined with S[0] */
	{
	    if ( tb->rnum[0] == -1 )    /* R[0] must be also joined with S[0] */
	    {			
		if ( tb->FR[0] == PATH_H_PPARENT(tb->tb_path, 0) )
		{
		    /* all contents of all the 3 buffers will be in L[0] */
		    if ( PATH_H_POSITION (tb->tb_path, 1) == 0 && 1 < B_NR_ITEMS(tb->FR[0]) )
			replace_key(tb->tb_fs, tb->CFL[0],tb->lkey[0],tb->FR[0],1);


		    leaf_move_items (LEAF_FROM_S_TO_L, tb, n, -1, 0);
		    leaf_move_items (LEAF_FROM_R_TO_L, tb, B_NR_ITEMS(tb->R[0]), -1, 0);

		    reiserfs_invalidate_buffer (tb, tbS0, 1/*do_free_block*/);
		    reiserfs_invalidate_buffer (tb, tb->R[0], 1/*do_free_block*/);

		    return 0;
		}
		/* all contents of all the 3 buffers will be in R[0] */
		leaf_move_items(LEAF_FROM_S_TO_R, tb, n, -1, 0);
		leaf_move_items(LEAF_FROM_L_TO_R, tb, B_NR_ITEMS(tb->L[0]), -1, 0);

		/* right_delimiting_key is correct in R[0] */
		replace_key(tb->tb_fs, tb->CFR[0],tb->rkey[0],tb->R[0],0);

		reiserfs_invalidate_buffer (tb, tbS0, 1/*do_free_block*/);
		reiserfs_invalidate_buffer (tb, tb->L[0], 1/*do_free_block*/);

		return -1;
	    }

	    /* all contents of L[0] and S[0] will be in L[0] */
	    leaf_shift_left(tb, n, -1);

	    reiserfs_invalidate_buffer (tb, tbS0, 1/*do_free_block*/);

	    return 0;
	}
	/* a part of contents of S[0] will be in L[0] and the rest part of S[0] will be in R[0] */

	leaf_shift_left (tb, tb->lnum[0], tb->lbytes);
	leaf_shift_right(tb, tb->rnum[0], tb->rbytes);

	reiserfs_invalidate_buffer (tb, tbS0, 1/*do_free_block*/);

	return 0;
    }

    if ( tb->rnum[0] == -1 ) {
	/* all contents of R[0] and S[0] will be in R[0] */
	leaf_shift_right(tb, n, -1);
	reiserfs_invalidate_buffer (tb, tbS0, 1/*do_free_block*/);
	return 0;
    }
    return 0;
}

static int balance_leaf(/*struct reiserfs_transaction_handle *th, */
			struct tree_balance * tb, /* see reiserfs_fs.h */
			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
							   (see comment to do_balance) */
			int zeros_number,		/* it is always 0 */
				
			struct item_head * insert_key,  /* 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 /* inserted node-ptrs for the next level */
    )
{
    int pos_in_item = tb->tb_path->pos_in_item; /* position in item, in bytes for direct and
						   indirect items, in entries for directories (for
						   which it is an index into the array of directory
						   entry headers.) */
    struct buffer_head * tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
/*  struct buffer_head * tbF0 = PATH_H_PPARENT (tb->tb_path, 0);
    int S0_b_item_order = PATH_H_B_ITEM_ORDER (tb->tb_path, 0);*/
    int item_pos = PATH_LAST_POSITION (tb->tb_path);	/*  index into the array of item headers in S[0] 
							    of the affected item */
    struct buffer_info bi;
    struct buffer_head *S_new[2];  /* new nodes allocated to hold what could not fit into S */
    int snum[2];			   /* number of items that will be placed into S_new (includes partially shifted items) */
    int sbytes[2];                   /* if an item is partially shifted into S_new then 
					if it is a directory item 
					it is the number of entries from the item that are shifted into S_new
					else
					it is the number of bytes from the item that are shifted into S_new
				     */
    int n, i;
    int ret_val;

    /* Make balance in case insert_size[0] < 0 */
    if ( tb->insert_size[0] < 0 )
	return balance_leaf_when_delete (/*th,*/ tb, flag);
  
    /* for indirect item pos_in_item is measured in unformatted node
       pointers. Recalculate to bytes */
    if (flag != M_INSERT && I_IS_INDIRECT_ITEM (B_N_PITEM_HEAD (tbS0, item_pos)))
	pos_in_item *= UNFM_P_SIZE;

    if ( tb->lnum[0] > 0 ) {
	/* Shift lnum[0] items from S[0] to the left neighbor L[0] */
	if ( item_pos < tb->lnum[0] ) {
	    /* new item or it part falls to L[0], shift it too */
	    n = B_NR_ITEMS(tb->L[0]);

	    switch (flag) {
	    case M_INSERT:   /* insert item into L[0] */

		if ( item_pos == tb->lnum[0] - 1 && tb->lbytes != -1 ) {
		    /* part of new item falls into L[0] */
		    int new_item_len;

		    ret_val = leaf_shift_left (/*th,*/ tb, tb->lnum[0]-1, -1);
		    /* Calculate item length to insert to S[0] */
		    new_item_len = get_ih_item_len (ih) - tb->lbytes;
		    /* Calculate and check item length to insert to L[0] */
		    set_ih_item_len (ih, get_ih_item_len (ih) - new_item_len);
		    /* Insert new item into L[0] */
		    bi.bi_bh = tb->L[0];
		    bi.bi_parent = tb->FL[0];
		    bi.bi_position = get_left_neighbor_position (tb, 0);
		    leaf_insert_into_buf (tb->tb_fs, &bi, n + item_pos - ret_val, ih, body,
					  zeros_number > get_ih_item_len (ih) ? get_ih_item_len (ih) : zeros_number);

		    /* Calculate key component, item length and body to insert into S[0] */
		    //ih->ih_key.k_offset += tb->lbytes;
		    set_offset (key_format (&ih->ih_key), &ih->ih_key, get_offset (&ih->ih_key) +
		    	tb->lbytes * (is_indirect_ih(ih) ? tb->tb_fs->fs_blocksize / UNFM_P_SIZE : 1) );
		    set_ih_item_len (ih, new_item_len);
		    if ( tb->lbytes >  zeros_number ) {
			body += (tb->lbytes - zeros_number);
			zeros_number = 0;
		    }
		    else
			zeros_number -= tb->lbytes;
		} else {
		    /* new item in whole falls into L[0] */
		    /* Shift lnum[0]-1 items to L[0] */
		    ret_val = leaf_shift_left(tb, tb->lnum[0]-1, tb->lbytes);

		    /* Insert new item into L[0] */
		    bi.bi_bh = tb->L[0];
		    bi.bi_parent = tb->FL[0];
		    bi.bi_position = get_left_neighbor_position (tb, 0);
		    leaf_insert_into_buf (tb->tb_fs, &bi, n + item_pos - ret_val, ih, body, zeros_number);

		    tb->insert_size[0] = 0;
		    zeros_number = 0;
		}
		break;

	    case M_PASTE:   /* append item in L[0] */

		if ( item_pos == tb->lnum[0] - 1 && tb->lbytes != -1 ) {
		    /* we must shift the part of the appended item */
		    if ( I_IS_DIRECTORY_ITEM (B_N_PITEM_HEAD (tbS0, item_pos))) {
			/* directory item */
			if ( tb->lbytes > pos_in_item ) {
			    /* new directory entry falls into L[0] */
			    struct item_head * pasted;
			    int l_pos_in_item = pos_in_item;
							  
			    /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 entries from given directory item */
			    ret_val = leaf_shift_left(tb, tb->lnum[0], tb->lbytes - 1);
			    if ( ret_val && ! item_pos ) {
				pasted =  B_N_PITEM_HEAD(tb->L[0],B_NR_ITEMS(tb->L[0])-1);
				l_pos_in_item += get_ih_entry_count(pasted) - (tb->lbytes-1);
			    }

			    /* Append given directory entry to directory item */
			    bi.bi_bh = tb->L[0];
			    bi.bi_parent = tb->FL[0];
			    bi.bi_position = get_left_neighbor_position (tb, 0);
			    leaf_paste_in_buffer (tb->tb_fs, &bi, n + item_pos - ret_val, l_pos_in_item,
						  tb->insert_size[0], body, zeros_number);

			    /* previous string prepared space for pasting new entry, following string pastes this entry */

			    /* when we have merge directory item, pos_in_item has been changed too */

			    /* paste new directory entry. 1 is entry number */
			    leaf_paste_entries (bi.bi_bh, n + item_pos - ret_val, l_pos_in_item, 1,
						(struct reiserfs_de_head *)body, 
						body + DEH_SIZE, tb->insert_size[0]
				);
			    tb->insert_size[0] = 0;
			} else {
			    /* new directory item doesn't fall into L[0] */
			    /* Shift lnum[0]-1 items in whole. Shift lbytes directory entries from directory item number lnum[0] */
			    leaf_shift_left (tb, tb->lnum[0], tb->lbytes);
			}
			/* Calculate new position to append in item body */
			pos_in_item -= tb->lbytes;
		    }
		    else {
			/* regular object */
			if ( tb->lbytes >= pos_in_item ) {
			    /* appended item will be in L[0] in whole */
			    int l_n, temp_n;
                            struct key * key;

			    /* this bytes number must be appended to the last item of L[h] */
			    l_n = tb->lbytes - pos_in_item;

			    /* Calculate new insert_size[0] */
			    tb->insert_size[0] -= l_n;

			    ret_val =  leaf_shift_left(tb, tb->lnum[0],
						       get_ih_item_len (B_N_PITEM_HEAD(tbS0,item_pos)));
			    /* Append to body of item in L[0] */
			    bi.bi_bh = tb->L[0];
			    bi.bi_parent = tb->FL[0];
			    bi.bi_position = get_left_neighbor_position (tb, 0);
			    leaf_paste_in_buffer(tb->tb_fs, 
						 &bi,n + item_pos - ret_val,
						 get_ih_item_len (B_N_PITEM_HEAD(tb->L[0],n+item_pos-ret_val)),
						 l_n,body, zeros_number > l_n ? l_n : zeros_number);


			    /* 0-th item in S0 can be only of DIRECT type when l_n != 0*/
			    //B_N_PKEY (tbS0, 0)->k_offset += l_n;z
			    key = B_N_PKEY (tbS0, 0);
                            temp_n = is_indirect_ih(B_N_PITEM_HEAD (tb->L[0], n + item_pos - ret_val)) ?
                                 (int)((l_n / UNFM_P_SIZE) * tb->tb_fs->fs_blocksize) : l_n;

			    set_offset (key_format (key), key, get_offset (key) + temp_n);

			    //B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0])->k_offset += l_n;
			    key = B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0]);
			    set_offset (key_format (key), key, get_offset (key) + temp_n);

			    /* Calculate new body, position in item and insert_size[0] */
			    if ( l_n > zeros_number ) {
				body += (l_n - zeros_number);
				zeros_number = 0;
			    }
			    else
				zeros_number -= l_n;
			    pos_in_item = 0;	
			}
			else {
			    /* only part of the appended item will be in L[0] */

			    /* Calculate position in item for append in S[0] */
			    pos_in_item -= tb->lbytes;

			    /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
			    leaf_shift_left(tb,tb->lnum[0],tb->lbytes);
			}
		    }
		} else {
		    /* appended item will be in L[0] in whole */
		    struct item_head * pasted;
		
		    if ( ! item_pos  && is_left_mergeable (tb->tb_fs, tb->tb_path) == 1 )
			{ /* if we paste into first item of S[0] and it is left mergable */
			    /* then increment pos_in_item by the size of the last item in L[0] */
			    pasted = B_N_PITEM_HEAD(tb->L[0],n-1);
			    if ( I_IS_DIRECTORY_ITEM(pasted) )
				pos_in_item += get_ih_entry_count (pasted);
			    else