fix_node.c

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

    
    if (!cur_free || !vn->vn_nr_item) {
	/* no free space  */
	tb->rnum[h] = 0;
	tb->rbytes = -1;
	return 0;
    }
  
    if ((unsigned int)cur_free >= (vn->vn_size - ((vn->vn_vi[vn->vn_nr_item-1].vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0)))
    {
	/* all contents of S[0] fits into R[0] */
	tb->rnum[h] = vn->vn_nr_item;
	tb->rbytes = -1;
	return -1;
    }
    
    d_size = 0, ih_size = IH_SIZE;
    
    /* last item may be merge with first item in right neighbor */
    if (vn->vn_vi[vn->vn_nr_item - 1].vi_type & VI_TYPE_RIGHT_MERGEABLE)
	d_size = -(int)IH_SIZE, ih_size = 0;
    
    tb->rnum[0] = 0;
    for (i = vn->vn_nr_item - 1; i >= 0; i --, d_size = 0, ih_size = IH_SIZE) {
	d_size += vn->vn_vi[i].vi_item_len;
	if (cur_free >= d_size)	{	
	    /* the item can be shifted entirely */
	    cur_free -= d_size;
	    tb->rnum[0] ++;
	    continue;
	}

	/* the item cannot be shifted entirely, try to split it */
	if (vn->vn_vi[i].vi_type & VI_TYPE_STAT_DATA || vn->vn_vi[i].vi_type & VI_TYPE_INSERTED_DIRECTORY_ITEM) {
	    /* virtual item is a stat_data or empty directory body ("." and
               "..), that is not split able */
	    tb->rbytes = -1;
	    return -1;
	}
	
	/* check whether R[0] can hold ih and at least one byte of the item
           body */
	if ( cur_free <= ih_size ) {
	    /* cannot shift even a part of the current item */
	    tb->rbytes = -1;
	    return -1;
	}
	
	/* R[0] can hold the header of the item and at least one byte of its
           body */
	cur_free -= ih_size;	/* cur_free is still > 0 */
	
	/* item is of direct type */
	if (vn->vn_vi[i].vi_type & VI_TYPE_DIRECT) {
	    /* body of a direct item can be split by 8 bytes */
	    int align = vn->vn_vi[i].vi_item_len % 8;
//	    reiserfs_warning(stderr,"\nbalancing: cur_free (%d) ", cur_free);
	    tb->rbytes = bytes = (cur_free >= align) ? (align + ((cur_free - align) / 8 * 8)) : 0;
//	    reiserfs_warning(stderr, "offset (0x%Lx) len (%d), move right (%d), get offset (0x%Lx)",
//	    	vn->vn_vi[i].vi_item_offset, vn->vn_vi[i].vi_item_len, bytes,
//	    	vn->vn_vi[i].vi_item_offset + vn->vn_vi[i].vi_item_len - bytes);
	}
	
	/* item is of indirect type */
	if (vn->vn_vi[i].vi_type & VI_TYPE_INDIRECT)
	    /* an unformatted node pointer (having size long) is a solid
               granule of the item */
	    tb->rbytes = bytes = cur_free - cur_free % UNFM_P_SIZE;
	
	/* item is of directory type */
	if (vn->vn_vi[i].vi_type & VI_TYPE_DIRECTORY) {
	    int j;
	    struct virtual_item * vi;
	    
	    tb->rbytes = 0;
	    bytes = 0;
	    vi = &vn->vn_vi[i];
	  
	    for (j = vi->vi_entry_count - 1; j >= 0; j --) {
		if (vi->vi_entry_sizes[j] > cur_free)
		    /* j-th entry doesn't fit into L[0] */
		    break;
	      
		bytes += vi->vi_entry_sizes[j];
		cur_free -= vi->vi_entry_sizes[j];
		tb->rbytes ++;
	    }
	    
	    /* ".." can not be cut from first directory item */
	    if ((vn->vn_vi[i].vi_type & VI_TYPE_FIRST_DIRECTORY_ITEM) && tb->rbytes > vi->vi_entry_count - 2)
		tb->rbytes = vi->vi_entry_count - 2;
	}
	
	if ( tb->rbytes <= 0 ) {
	    /* nothing can flow from the item */
	    tb->rbytes = -1;
	    return -1;
	}
	
	
	/* something can flow from the item */
	tb->rnum[0] ++;
	return bytes;	/* part of split item in bytes */
    }
    
    reiserfs_panic ("vs-8095: check_right: all items fit in the left neighbor");
    return 0;
}


/* sum of entry sizes between from-th and to-th entries including both edges */
static int directory_part_size (struct virtual_item * vi, int from, int to)
{
    int i, retval;
    
    retval = 0;
    for (i = from; i <= to; i ++)
	retval += vi->vi_entry_sizes[i];
    
    return retval;
}


/*
 * from - number of items, which are shifted to left neighbor entirely
 * to - number of item, which are shifted to right neighbor entirely
 * from_bytes - number of bytes of boundary item (or directory entries) which
 * are shifted to left neighbor
 * to_bytes - number of bytes of boundary item (or directory entries) which
 * are shifted to right neighbor */

static int get_num_ver (int mode, struct tree_balance * tb, int h,
			int from, int from_bytes,
			int to,   int to_bytes,
			short * snum012, int flow
			)
{
    int i;
    int bytes;
    struct virtual_node * vn = tb->tb_vn;
    struct virtual_item * vi;
    
    int total_node_size, max_node_size, current_item_size;
    int needed_nodes;
    int start_item, 	/* position of item we start filling node from */
	end_item,	/* position of item we finish filling node by */
	start_bytes,/* number of first bytes (entries for directory) of start_item-th item 
		       we do not include into node that is being filled */
	end_bytes;	/* number of last bytes (entries for directory) of end_item-th item 
			   we do node include into node that is being filled */
    int splitted_item_positions[2];	/* these are positions in virtual item of items, 
					   that are splitted between S[0] and S1new and S1new and S2new */

    max_node_size = MAX_CHILD_SIZE (tb->tb_fs->fs_blocksize);
    
    /* snum012 [0-2] - number of items, that lay to S[0], first new node and
       second new node */
    snum012[3] = -1;	/* s1bytes */
    snum012[4] = -1;	/* s2bytes */
    

    /* internal level */
    if (h > 0) {
	i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
	if (i == max_node_size)
	    return 1;
	return (i / max_node_size + 1);
    }
    

    /* leaf level */
    needed_nodes = 1;
    total_node_size = 0;
    
    start_item = from;
    start_bytes = from_bytes;
    end_item = vn->vn_nr_item - to - 1;
    end_bytes = to_bytes;
    
    /* go through all items begining from the start_item-th item and ending by
       the end_item-th item. If start_bytes != -1 we skip first start_bytes
       item units (entries in case of directory). If end_bytes != -1 we skip
       end_bytes units of the end_item-th item. */
    for (i = start_item; i <= end_item; i ++) {
	/* get size of current item */
	current_item_size = (vi = &vn->vn_vi[i])->vi_item_len;
	
	/* do not take in calculation head part (from_bytes) of from-th item */
	if (i == start_item && start_bytes != -1) {
	    if (vi->vi_type & VI_TYPE_DIRECTORY)
		current_item_size -= directory_part_size (vi, 0, start_bytes - 1);
	    else
		current_item_size -= start_bytes;
	}
	
	/* do not take in calculation tail part of (to-1)-th item */
	if (i == end_item && end_bytes != -1) {
	    if (vi->vi_type & VI_TYPE_DIRECTORY)
		/* first entry, that is not included */
		current_item_size -= directory_part_size (vi, vi->vi_entry_count - end_bytes, vi->vi_entry_count - 1);
	    else
		current_item_size -= end_bytes;
	}
	
	/* if item fits into current node entirely */
	if (total_node_size + current_item_size <= max_node_size) {
	    snum012[needed_nodes - 1] ++;
	    total_node_size += current_item_size;
	    continue;
	}
	
	if (current_item_size > max_node_size)
	    /* virtual item length is longer, than max size of item in a
               node. It is impossible for direct item */
	    /* we will try to split it */
	    flow = 1;
	
	
	if (!flow) {
	    /* as we do not split items, take new node and continue */
	    needed_nodes ++; i --; total_node_size = 0;
	    continue;
	}
	
	if (total_node_size + (int)IH_SIZE >= max_node_size) {
	    /* even minimal item does not fit into current node, take new node
               and continue */
	    needed_nodes ++, i--, total_node_size = 0;
	    continue;
	}
	if (vi->vi_type & VI_TYPE_STAT_DATA) {
	    /* stat data can not be split */
	    needed_nodes ++, i--, total_node_size = 0;
	    continue;
	}
	
	/*bytes is free space in filled node*/
	bytes = max_node_size - total_node_size - IH_SIZE;
	
	if (vi->vi_type & VI_TYPE_DIRECT) {
	    /* body of a direct item can be split by 8 bytes. */
	    int align = 8 - (vn->vn_vi[i].vi_item_offset - 1) % 8;
//	    reiserfs_warning(stderr,"\nbalancing: cur_free (%d) ", bytes);
//	    reiserfs_warning(stderr,"offset (0x%Lx), move (%d), get offset (0x%Lx)",
//	    	vn->vn_vi[i].vi_item_offset, (bytes - align) / 8 * 8,
//	    	vn->vn_vi[i].vi_item_offset + ((bytes - align) / 8 * 8));
	    bytes = (bytes >= align) ? (align + ((bytes - align) / 8 * 8)) : 0;
	}


	/* item is of indirect type */
	if (vi->vi_type & VI_TYPE_INDIRECT)
	    /* an unformatted node pointer (having size long) is a solid
	       granule of the item. bytes of unformatted node pointers fits
	       into free space of filled node */
	    bytes -= (bytes) % UNFM_P_SIZE;
	
	/* S1bytes or S2bytes. It depends from needed_nodes */
	snum012[needed_nodes - 1 + 3] = bytes;
	
	/* item is of directory type */
	if (vi->vi_type & VI_TYPE_DIRECTORY) {
	    /* calculate, how many entries can be put into current node */
	    int j;
	    int end_entry;
	    
	    snum012[needed_nodes - 1 + 3] = 0;

	    total_node_size += IH_SIZE;
	    if (start_bytes == -1 || i != start_item)
		start_bytes = 0;
	    
	    end_entry = vi->vi_entry_count - ((i == end_item && end_bytes != -1) ? end_bytes : 0);
	    for (j = start_bytes; j < end_entry; j ++) {
		/* j-th entry doesn't fit into current node */
		if (total_node_size + vi->vi_entry_sizes[j] > max_node_size)
		    break;
		snum012[needed_nodes - 1 + 3] ++;
		bytes += vi->vi_entry_sizes[j];
		total_node_size += vi->vi_entry_sizes[j];
	    }
	    /* "." can not be cut from first directory item */
	    if (start_bytes == 0 && (vn->vn_vi[i].vi_type & VI_TYPE_FIRST_DIRECTORY_ITEM) && 
		snum012[needed_nodes - 1 + 3] < 2)
		snum012[needed_nodes - 1 + 3] = 0;
	}
	
	if (snum012[needed_nodes-1+3] <= 0 ) {
	    /* nothing fits into current node, take new node and continue */
	    needed_nodes ++, i--, total_node_size = 0;
	    continue;
	}
	
	/* something fits into the current node */
	if (vi->vi_type & VI_TYPE_DIRECTORY)
	    start_bytes += snum012[needed_nodes - 1 + 3];
	else
	    start_bytes = bytes;
	
	snum012[needed_nodes - 1] ++;
	splitted_item_positions[needed_nodes - 1] = i;

	needed_nodes ++;
	/* continue from the same item with start_bytes != -1 */
	start_item = i;
	i --;
	total_node_size = 0;
    }

    
    /* snum012[3] and snum012[4] contain how many bytes (entries) of split
       item can be in S[0] and S1new. s1bytes and s2bytes are how many bytes
       (entries) can be in S1new and S2new. Recalculate it */
    
    if (snum012[4] > 0) {	/* s2bytes */
	/* get number of item that is split between S1new and S2new */
	int split_item_num;
	int bytes_to_r, bytes_to_l;
    
	split_item_num = splitted_item_positions[1];
	bytes_to_l = ((from == split_item_num && from_bytes != -1) ? from_bytes : 0);
	bytes_to_r = ((end_item == split_item_num && end_bytes != -1) ? end_bytes : 0);
	if (vn->vn_vi[split_item_num].vi_type & VI_TYPE_DIRECTORY) {
	    int entries_to_S2new;
	    
	    /* calculate number of entries fit into S2new */
	    entries_to_S2new =  vn->vn_vi[split_item_num].vi_entry_count - snum012[4] - bytes_to_r - bytes_to_l;
	    if (snum012[3] != -1 && snum012[1] == 1) {
		/* directory split into 3 nodes */
		int entries_to_S1new;
		
		entries_to_S2new -= snum012[3];
		entries_to_S1new = snum012[4];
		snum012[3] = entries_to_S1new;
		snum012[4] = entries_to_S2new;
		return needed_nodes;
	    }
	    snum012[4] = entries_to_S2new;
	} else {
	    /* item is not of directory type */
	    int bytes_to_S2new;
	    
	    bytes_to_S2new = vn->vn_vi[split_item_num].vi_item_len - IH_SIZE - snum012[4] - bytes_to_r - bytes_to_l;
	    snum012[4] = bytes_to_S2new;
	}
    }
    
    /* now we know S2bytes, calculate S1bytes */
    if (snum012[3] > 0) {	/* s1bytes */
	/* get number of item that is split between S0 and S1new */
	int split_item_num;
	int bytes_to_r, bytes_to_l;
	
	split_item_num = splitted_item_positions[0];
	bytes_to_l = ((from == split_item_num && from_bytes != -1) ? from_bytes : 0);
	bytes_to_r = ((end_item == split_item_num && end_bytes != -1) ? end_bytes : 0);
	if (vn->vn_vi[split_item_num].vi_type & VI_TYPE_DIRECTORY) {
	    /* entries, who go to S1new node */
	    snum012[3] =  vn->vn_vi[split_item_num].vi_entry_count - snum012[3] - bytes_to_r - bytes_to_l;
	} else
	    /* bytes, who go to S1new node (not including HI_SIZE) */
	    snum012[3] = vn->vn_vi[split_item_num].vi_item_len - IH_SIZE - snum012[3] - bytes_to_r - bytes_to_l;
    }
    
    return needed_nodes;
}

/* size of item_num-th item in bytes when regular and in entries when item is
   directory */
static int item_length (struct tree_balance * tb, int item_num)
{
    struct virtual_node * vn = tb->tb_vn;

    if (vn->vn_vi[item_num].vi_type & VI_TYPE_DIRECTORY)
	return vn->vn_vi[item_num].vi_entry_count;

    return vn->vn_vi[item_num].vi_item_len - IH_SIZE;
}


/* Set parameters for balancing.
 * Performs write of results of analysis of balancing into structure tb,
 * where it will later be used by the functions that actually do the balancing. 
 * Parameters:
 *	tb	tree_balance structure;
 *	h	current level of the node;
 *	lnum	number of items from S[h] that must be shifted to L[h];
 *	rnum	number of items from S[h] that must be shifted to R[h];
 *	blk_num	number of blocks that S[h] will be splitted into;