do_balan.c

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

	reiserfs_invalidate_buffer(tb,tbS0);									
	return 0;
    }


    /* Fill new nodes that appear in place of S[0] */

    /* I am told that this copying is because we need an array to enable
       the looping code. -Hans */
    snum[0] = tb->s1num,
	snum[1] = tb->s2num;
    sbytes[0] = tb->s1bytes;
    sbytes[1] = tb->s2bytes;
    for( i = tb->blknum[0] - 2; i >= 0; i-- ) {

	RFALSE( !snum[i], "PAP-12200: snum[%d] == %d. Must be > 0", i, snum[i]);

	/* here we shift from S to S_new nodes */

	S_new[i] = get_FEB(tb);

	/* initialized block type and tree level */
        set_blkh_level( B_BLK_HEAD(S_new[i]), DISK_LEAF_NODE_LEVEL );


	n = B_NR_ITEMS(tbS0);
	
	switch (flag) {
	case M_INSERT:   /* insert item */

	    if ( n - snum[i] < item_pos )
	    { /* new item or it's part falls to first new node S_new[i]*/
		if ( item_pos == n - snum[i] + 1 && sbytes[i] != -1 )
		{ /* part of new item falls into S_new[i] */
		    int old_key_comp, old_len, r_zeros_number;
		    const char * r_body;
		    int version;

		    RFALSE( !is_direct_le_ih(ih),
			/* The items which can be inserted are:
			   Stat_data item, direct item, indirect item and directory item which consist of only two entries "." and "..".
			   These items must not be broken except for a direct one. */
			    "PAP-12205: non-direct item can not be broken when inserting");

		    /* Move snum[i]-1 items from S[0] to S_new[i] */
		    leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i] - 1, -1, S_new[i]);
		    /* Remember key component and item length */
		    version = ih_version (ih);
                    old_key_comp = le_ih_k_offset( ih );
		    old_len = ih_item_len(ih);

		    /* Calculate key component and item length to insert into S_new[i] */
                    set_le_ih_k_offset( ih,
                                le_ih_k_offset(ih) + (old_len - sbytes[i] ) );

		    put_ih_item_len( ih, sbytes[i] );

		    /* Insert part of the item into S_new[i] before 0-th item */
		    bi.tb = tb;
		    bi.bi_bh = S_new[i];
		    bi.bi_parent = 0;
		    bi.bi_position = 0;

		    if ( le_ih_k_offset (ih) - old_key_comp > zeros_num ) {
			r_zeros_number = 0;
			r_body = body + (le_ih_k_offset(ih) - old_key_comp) - zeros_num;
		    }
		    else {
			r_body = body;
			r_zeros_number = zeros_num - (le_ih_k_offset (ih) - old_key_comp);
			zeros_num -= r_zeros_number;
		    }

		    leaf_insert_into_buf (&bi, 0, ih, r_body, r_zeros_number);

		    /* Calculate key component and item length to insert into S[i] */
                    set_le_ih_k_offset( ih, old_key_comp );
		    put_ih_item_len( ih, old_len - sbytes[i] );
		    tb->insert_size[0] -= sbytes[i];
		}
		else /* whole new item falls into S_new[i] */
		{
		    /* Shift snum[0] - 1 items to S_new[i] (sbytes[i] of split item) */
		    leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i] - 1, sbytes[i], S_new[i]);

		    /* Insert new item into S_new[i] */
		    bi.tb = tb;
		    bi.bi_bh = S_new[i];
		    bi.bi_parent = 0;
		    bi.bi_position = 0;
		    leaf_insert_into_buf (&bi, item_pos - n + snum[i] - 1, ih, body, zeros_num);

		    zeros_num = tb->insert_size[0] = 0;
		}
	    }

	    else /* new item or it part don't falls into S_new[i] */
	    {
		leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i], S_new[i]);
	    }
	    break;

	case M_PASTE:   /* append item */

	    if ( n - snum[i] <= item_pos )  /* pasted item or part if it falls to S_new[i] */
	    {
		if ( item_pos == n - snum[i] && sbytes[i] != -1 )
		{ /* we must shift part of the appended item */
		    struct item_head * aux_ih;

		    RFALSE( ih, "PAP-12210: ih must be 0");

		    if ( is_direntry_le_ih (aux_ih = B_N_PITEM_HEAD(tbS0,item_pos))) {
			/* we append to directory item */

			int entry_count;
		
			entry_count = ih_entry_count(aux_ih);

			if ( entry_count - sbytes[i] < pos_in_item  && pos_in_item <= entry_count ) {
			    /* new directory entry falls into S_new[i] */
		  
			    RFALSE( ! tb->insert_size[0],
				    "PAP-12215: insert_size is already 0");
			    RFALSE( sbytes[i] - 1 >= entry_count,
				    "PAP-12220: there are no so much entries (%d), only %d",
				    sbytes[i] - 1, entry_count);

			    /* 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.tb = tb;
			    bi.bi_bh = S_new[i];
			    bi.bi_parent = 0;
			    bi.bi_position = 0;
			    leaf_paste_in_buffer (&bi, 0, pos_in_item - entry_count + sbytes[i] - 1,
						  tb->insert_size[0], body,zeros_num);
			    /* 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;

			RFALSE( pos_in_item != ih_item_len(B_N_PITEM_HEAD(tbS0,item_pos)) ||
			        tb->insert_size[0] <= 0,
			        "PAP-12225: item too short or insert_size <= 0");

			/* 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.tb = tb;
			bi.bi_bh = S_new[i];
			bi.bi_parent = 0;
			bi.bi_position = 0;

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

			leaf_paste_in_buffer(&bi, 0, n_shift, tb->insert_size[0]-n_rem, r_body,r_zeros_number);
			{
			    struct item_head * tmp;

			    tmp = B_N_PITEM_HEAD(S_new[i],0);
			    if (is_indirect_le_ih (tmp)) {
				if (n_rem)
				    reiserfs_panic (tb->tb_sb, "PAP-12230: balance_leaf: invalid action with indirect item");
				set_ih_free_space (tmp, ((struct unfm_nodeinfo*)body)->unfm_freespace);
			    }
                            set_le_ih_k_offset( tmp, le_ih_k_offset(tmp) + n_rem );
			}

			tb->insert_size[0] = n_rem;
			if ( ! n_rem )
			    pos_in_item++;
		    }
		}
		else
		    /* item falls wholly into S_new[i] */
		{
		    int ret_val;
		    struct item_head * pasted;

#ifdef CONFIG_REISERFS_CHECK
		    struct item_head * ih = B_N_PITEM_HEAD(tbS0,item_pos);

		    if ( ! is_direntry_le_ih(ih) && (pos_in_item != ih_item_len(ih) ||
						     tb->insert_size[0] <= 0) )
			reiserfs_panic (tb->tb_sb, "PAP-12235: balance_leaf: pos_in_item must be equal to ih_item_len");
#endif /* CONFIG_REISERFS_CHECK */

		    ret_val = leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i], S_new[i]);

		    RFALSE( ret_val,
			    "PAP-12240: unexpected value returned by leaf_move_items (%d)",
			    ret_val);

		    /* paste into item */
		    bi.tb = tb;
		    bi.bi_bh = S_new[i];
		    bi.bi_parent = 0;
		    bi.bi_position = 0;
		    leaf_paste_in_buffer(&bi, item_pos - n + snum[i], pos_in_item, tb->insert_size[0], body, zeros_num);

		    pasted = B_N_PITEM_HEAD(S_new[i], item_pos - n + snum[i]);
		    if (is_direntry_le_ih (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 (is_indirect_le_ih (pasted))
			set_ih_free_space (pasted, ((struct unfm_nodeinfo*)body)->unfm_freespace);
		    zeros_num = 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 (tb->tb_sb, "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];

	RFALSE( (atomic_read (&(S_new[i]->b_count)) != 1) &&
		(atomic_read(&(S_new[i]->b_count)) != 2 ||
		 !(buffer_journaled(S_new[i]) || 
		   buffer_journal_dirty(S_new[i]))), 
		"PAP-12247: S_new[%d] : (%b)\n", 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.tb = tb;
	    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 (&bi, item_pos, ih, body, zeros_num);

	    /* 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->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 (is_direntry_le_ih (pasted)) {
		if ( pos_in_item >= 0 &&
		    pos_in_item <= ih_entry_count(pasted) ) {

		    RFALSE( ! tb->insert_size[0], 
			    "PAP-12260: insert_size is 0 already");

		    /* prepare space */
		    bi.tb = tb;
		    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(&bi, item_pos, pos_in_item, tb->insert_size[0], body, zeros_num);

		    /* 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 ) {
			RFALSE( !tb->CFL[0] || !tb->L[0], 
				"PAP-12270: CFL[0]/L[0] must be specified");
			if (tb->CFL[0]) {
			    replace_key(tb, tb->CFL[0], tb->lkey[0],tbS0,0);

			}
		    }
		    tb->insert_size[0] = 0;
		}
	    } else { /* regular object */
		if ( pos_in_item == ih_item_len(pasted) ) {

		    RFALSE( tb->insert_size[0] <= 0,
			    "PAP-12275: insert size must not be %d",
                            tb->insert_size[0]);
		    bi.tb = tb;
		    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 (&bi, item_pos, pos_in_item, tb->insert_size[0], body, zeros_num);

		    if (is_indirect_le_ih (pasted)) {

			RFALSE( tb->insert_size[0] != UNFM_P_SIZE,
				"PAP-12280: insert_size for indirect item must be %d, not %d",
				UNFM_P_SIZE, tb->insert_size[0]);
			set_ih_free_space (pasted, ((struct unfm_nodeinfo*)body)->unfm_freespace);
		    }
		    tb->insert_size[0] = 0;
		}

#ifdef CONFIG_REISERFS_CHECK
		else {
		    if ( tb->insert_size[0] ) {
			print_cur_tb ("12285");
			reiserfs_panic (tb->tb_sb, "PAP-12285: balance_leaf: insert_size must be 0 (%d)", tb->insert_size[0]);
		    }
		}
#endif /* CONFIG_REISERFS_CHECK */
	    
	    }
	} /* case M_PASTE: */
	}
    }

#ifdef CONFIG_REISERFS_CHECK
    if ( flag == M_PASTE && tb->insert_size[0] ) {
	print_cur_tb ("12290");
	reiserfs_panic (tb->tb_sb, "PAP-12290: balance_leaf: insert_size is still not 0 (%d)", tb->insert_size[0]);
    }
#endif /* CONFIG_REISERFS_CHECK */

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



/* Make empty node */
void make_empty_node (struct buffer_info * bi)
{
    struct block_head * blkh;

    RFALSE( bi->bi_bh == NULL, "PAP-12295: pointer to the buffer is NULL");

    blkh = B_BLK_HEAD(bi->bi_bh);
    set_blkh_nr_item( blkh, 0 );
    set_blkh_free_space( blkh, MAX_CHILD_SIZE(bi->bi_bh) );

    if (bi->bi_parent)
	B_N_CHILD (bi->bi_parent, bi->bi_position)->dc_size = 0; /* Endian safe if 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(tb->tb_sb, "vs-12300: get_FEB: FEB list is empty");

    bi.tb = tb;