pass1.c

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

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

#include "fsck.h"

reiserfs_bitmap_t * bad_unfm_in_tree_once_bitmap;


//int step = 0; // 0 - find stat_data or any item ; 1 - find item ; 2 - already found


/* allocates buffer head and copy buffer content */
struct buffer_head * make_buffer (int dev, unsigned long blocknr, int size, char * data)
{
    struct buffer_head * bh;
    
    bh = getblk (dev, blocknr, size);
    if (buffer_uptodate (bh))
	return bh;
//    die ("make_buffer: uptodate buffer found");
    memcpy (bh->b_data, data, size);
    misc_set_bit (BH_Uptodate, (char *)&bh->b_state);
    return bh;
}


int find_not_of_one_file(struct key * to_find, struct key * key) {
    if ((get_key_objectid (to_find) != ~(__u32)0) &&
        (get_key_objectid (to_find) != get_key_objectid (key)))
        return 1;
    if ((get_key_dirid (to_find) != ~(__u32)0) &&
        (get_key_dirid (to_find) != get_key_dirid (key)))
        return 1;
    return 0;
}


int is_item_reachable (struct item_head * ih)
{
    return ih_reachable (ih) ? 1 : 0;
}


void mark_item_unreachable (struct item_head * ih)
{
    clean_ih_flags (ih);
    mark_ih_unreachable (ih);

    if (is_indirect_ih (ih))
	set_ih_free_space (ih, 0);
}


void mark_item_reachable (struct item_head * ih, struct buffer_head * bh)
{
    mark_ih_reachable (ih);
    mark_buffer_dirty (bh);
}

static void stat_data_in_tree (struct buffer_head *bh,
			       struct item_head * ih)
{
#if 0
    __u32 objectid;
    
    objectid = get_key_objectid (&ih->ih_key);
    
    if (mark_objectid_really_used (proper_id_map (fs), objectid)) {
	stat_shared_objectid_found (fs);
	mark_objectid_really_used (shared_id_map (fs), objectid);
    }
#endif
    
    zero_nlink (ih, B_I_PITEM (bh, ih));
}

static char *still_bad_unfm_ptr_to_string (int val) {
    switch (val) {
	case 1:
	    return "a leaf";
	case 2:
	    return "shared between a few files";
	case 3:
	    return "not a data block";
	case 4:
	    return "not used in on-disk bitmap";
	case 5:
	    return "out of partition boundary";
    }
    return "";
}

/* this just marks blocks pointed by an indirect item as used in the
   new bitmap */
static void indirect_in_tree (struct buffer_head * bh,
			      struct item_head * ih)
{
    unsigned int i;
    __u32 * unp;
    __u32 unfm_ptr;
    int ret;

    unp = (__u32 *)B_I_PITEM (bh, ih);
    
    for (i = 0; i < I_UNFM_NUM (ih); i ++) {
	unfm_ptr = d32_get (unp, i);
	if (unfm_ptr == 0)
	    continue;
	if ((ret = still_bad_unfm_ptr_1 (unfm_ptr)))
	    reiserfs_panic ("%s: block %lu: The file %k points to the block (%u) which is %s", 
		__FUNCTION__, bh->b_blocknr, &ih->ih_key, unfm_ptr, still_bad_unfm_ptr_to_string(ret));

	mark_block_used (unfm_ptr, 1);
    }
}


static void leaf_is_in_tree_now (struct buffer_head * bh)
{
    item_action_t actions[] = {stat_data_in_tree, indirect_in_tree, 0, 0};

    mark_block_used ((bh)->b_blocknr, 1);

    for_every_item (bh, mark_item_unreachable, actions);

    pass_1_stat (fs)->inserted_leaves ++;

    mark_buffer_dirty (bh);
}


static void insert_pointer (struct buffer_head * bh, struct path * path)
{
    struct item_head * ih;
    char * body;
    int retval;
    struct tree_balance tb;
    
    init_tb_struct (&tb, fs, path, 0x7fff);

    /* fix_nodes & do_balance must work for internal nodes only */
    ih = 0;

    retval = fix_nodes (/*tb.transaction_handle,*/ M_INTERNAL, &tb, ih);
    if (retval != CARRY_ON)
	die ("insert_pointer: fix_nodes failed with retval == %d", retval);
    
    /* child_pos: we insert after position child_pos: this feature of the insert_child */
    /* there is special case: we insert pointer after
       (-1)-st key (before 0-th key) in the parent */
    if (PATH_LAST_POSITION (path) == 0 && path->pos_in_item == 0)
	PATH_H_B_ITEM_ORDER (path, 0) = -1;
    else {
	if (PATH_H_PPARENT (path, 0) == 0)
	    PATH_H_B_ITEM_ORDER (path, 0) = 0;
/*    PATH_H_B_ITEM_ORDER (path, 0) = PATH_H_PPARENT (path, 0) ? PATH_H_B_ITEM_ORDER (path, 0) : 0;*/
    }
    
    ih = 0;
    body = (char *)bh;
    //memmode = 0;

    do_balance (&tb, ih, body, M_INTERNAL, 0);

    leaf_is_in_tree_now (bh);
}


/* return 1 if left and right can be joined. 0 otherwise */
int balance_condition_fails (struct buffer_head * left, struct buffer_head * right)
{
    if (B_FREE_SPACE (left) >= B_CHILD_SIZE (right) -
	(are_items_mergeable (B_N_PITEM_HEAD (left, B_NR_ITEMS (left) - 1), B_N_PITEM_HEAD (right, 0), left->b_size) ? IH_SIZE : 0))
	return 1;
    return 0;
}


/* return 1 if new can be joined with last node on the path or with
   its right neighbor, 0 otherwise */
int balance_condition_2_fails (struct buffer_head * new, struct path * path)
{
    struct buffer_head * bh;
    struct key * right_dkey;
    int pos, used_space;
    
    bh = PATH_PLAST_BUFFER (path);
    

    if (balance_condition_fails (bh, new))
	/* new node can be joined with last buffer on the path */
	return 1;
    
    /* new node can not be joined with its left neighbor */
    
    right_dkey = uget_rkey (path);
    if (right_dkey == 0)
	/* there is no right neighbor */
	return 0;
    
    pos = PATH_H_POSITION (path, 1);
    if (pos == B_NR_ITEMS (bh = PATH_H_PBUFFER (path, 1))) {
	/* we have to read parent of right neighbor. For simplicity we
	   call search_by_key, which will read right neighbor as well */
	INITIALIZE_PATH(path_to_right_neighbor);
	
	if (reiserfs_search_by_key_4 (fs, right_dkey, &path_to_right_neighbor) != ITEM_FOUND)
	    reiserfs_panic ("%s: block %lu, pointer %d: The left delimiting key %k of the block (%lu) is wrong,"
		"the item cannot be found", __FUNCTION__, PATH_H_PBUFFER(path, 1)->b_blocknr, pos, 
		right_dkey, get_dc_child_blocknr(B_N_CHILD (bh, pos + 1)));

	used_space =  B_CHILD_SIZE (PATH_PLAST_BUFFER (&path_to_right_neighbor));
	pathrelse (&path_to_right_neighbor);
    }
    else
	used_space = get_dc_child_size (B_N_CHILD (bh, pos + 1));
    
    if (B_FREE_SPACE (new) >= used_space -
	(are_items_mergeable (B_N_PITEM_HEAD (new, B_NR_ITEMS (new) - 1), (struct item_head *)right_dkey, new->b_size) ? IH_SIZE : 0))
	return 1;

    return 0;
}


static void get_max_buffer_key (struct buffer_head * bh, struct key * key)
{
    struct item_head * ih;

    ih = B_N_PITEM_HEAD (bh, B_NR_ITEMS (bh) - 1);
    copy_key (key, &(ih->ih_key));

    if (is_direntry_key (key)) {
	/* copy deh_offset 3-rd and 4-th key components of the last entry */
	set_offset (KEY_FORMAT_1, key, 
		    get_deh_offset (B_I_DEH (bh, ih) + get_ih_entry_count (ih) - 1));

    } else if (!is_stat_data_key (key))
	/* get key of the last byte, which is contained in the item */
	set_offset (key_format (key), key, get_offset (key) + get_bytes_number (ih, bh->b_size) - 1);
}


int tree_is_empty (void)
{
    return (get_sb_root_block (fs->fs_ondisk_sb) == ~(__u32)0 || 
	    get_sb_root_block (fs->fs_ondisk_sb) == 0) ? 1 : 0;
}


void make_single_leaf_tree (struct buffer_head * bh)
{
    /* tree is empty, make tree root */
    set_sb_root_block (fs->fs_ondisk_sb, bh->b_blocknr);
    set_sb_tree_height (fs->fs_ondisk_sb, 2);
    mark_buffer_dirty (fs->fs_super_bh);
    leaf_is_in_tree_now (bh);
}


/* inserts pointer to leaf into tree if possible. If not, marks node as
   uninsertable in special bitmap */
static void try_to_insert_pointer_to_leaf (struct buffer_head * new_bh)
{
    INITIALIZE_PATH (path);
    struct buffer_head * bh;			/* last path buffer */
    struct key * first_bh_key, last_bh_key;	/* first and last keys of new buffer */
    struct key last_path_buffer_last_key, * right_dkey;
    int ret_value;

    if (tree_is_empty () == 1) {
	make_single_leaf_tree (new_bh);
	return;
    }

    first_bh_key = B_N_PKEY (new_bh, 0);
    
    /* try to find place in the tree for the first key of the coming node */
    ret_value = reiserfs_search_by_key_4 (fs, first_bh_key, &path);
    if (ret_value == ITEM_FOUND)
	goto cannot_insert;

    /* get max key in the new node */
    get_max_buffer_key (new_bh, &last_bh_key);

    bh = PATH_PLAST_BUFFER (&path);
    if (comp_keys (B_N_PKEY (bh, 0), &last_bh_key) == 1/* first is greater*/) {
	/* new buffer falls before the leftmost leaf */
	if (balance_condition_fails (new_bh, bh))
	    goto cannot_insert;
	
	if (uget_lkey (&path) != 0 || PATH_LAST_POSITION (&path) != 0)
	    die ("try_to_insert_pointer_to_leaf: bad search result");
	
	path.pos_in_item = 0;
	goto insert;
    }
    
    /* get max key of buffer, that is in tree */
    get_max_buffer_key (bh, &last_path_buffer_last_key);
    if (comp_keys (&last_path_buffer_last_key, first_bh_key) != -1/* second is greater */)
	/* first key of new buffer falls in the middle of node that is in tree */
	goto cannot_insert;
    
    right_dkey = uget_rkey (&path);
    if (right_dkey && comp_keys (right_dkey, &last_bh_key) != 1 /* first is greater */)
	goto cannot_insert;
    
    if (balance_condition_2_fails (new_bh, &path))
	goto cannot_insert;


 insert:
    insert_pointer (new_bh, &path);
    goto out;
    
 cannot_insert:
    /* statistic */

    mark_block_uninsertable (new_bh->b_blocknr);
    
 out:
    pathrelse (&path);
    return;
}



/* everything should be correct already in the leaf but contents of indirect
   items. So we only
   1. zero slots pointing to a leaf
   2. zero pointers to blocks which are pointed already
   3. what we should do with directory entries hashed by another hash?
   they are deleted for now
*/
static void pass1_correct_leaf (reiserfs_filsys_t * fs,
				struct buffer_head * bh)
{
    unsigned int i, j;
    struct item_head * ih;
    __u32 * ind_item;
    __u32 unfm_ptr;
    int dirty = 0;


    ih = B_N_PITEM_HEAD (bh, 0);
    for (i = 0; i < B_NR_ITEMS (bh); i ++, ih ++) {
	if (is_direntry_ih (ih)) {
	    struct reiserfs_de_head * deh;
	    __u32 offset;
	    char * name;
	    int name_len;
	    unsigned int hash_code;

	    deh = B_I_DEH (bh, ih);
	    offset = 0;
	    for (j = 0; j < get_ih_entry_count (ih); j ++) {
		name = name_in_entry (deh + j, j);
		name_len = name_in_entry_length (ih, deh + j, j);

		if ((j == 0 && is_dot (name, name_len)) ||
		    (j == 1 && is_dot_dot (name, name_len))) {
		    continue;
		}

		hash_code = find_hash_in_use (name, name_len, get_deh_offset (deh + j),
					      get_sb_hash_code (fs->fs_ondisk_sb));
		if (hash_code != get_sb_hash_code (fs->fs_ondisk_sb)) {
		    fsck_log ("pass1: block %lu, item %d, entry %d: The entry \"%.*s\" of the %k is hashed with %s "
			"whereas proper hash is %s", bh->b_blocknr, i, j, name_len, name, &ih->ih_key,
			      code2name (hash_code), code2name (get_sb_hash_code (fs->fs_ondisk_sb)));
		    if (get_ih_entry_count (ih) == 1) {
			delete_item (fs, bh, i);
			fsck_log(" - the only entry - item was deleted\n");
			i --;
			ih --;
			break;
		    } else {
			cut_entry (fs, bh, i, j, 1);
			fsck_log(" - deleted\n");
			j --;
			deh = B_I_DEH (bh, ih);
			continue;
		    }
		}

		if (j && offset >= get_deh_offset (deh + j)) {
		    fsck_log ("pass1: block %lu, item %d, entry %d: The entry "
			      "\"%.*s\" of the %k has hash offset %lu not "
			      "larger smaller than the previous one %lu. The "
			      "entry is deleted.\n", bh->b_blocknr, 
			      i, j, name_len, name, &ih->ih_key, 
			      get_deh_offset(deh + j), offset);
		    cut_entry (fs, bh, i, j, 1);
		    j --;
		    deh = B_I_DEH (bh, ih);
		    continue;
		}

		offset = get_deh_offset (deh + j);
	    }
	    continue;
	}


	if (!is_indirect_ih (ih))
	    continue;

	/* correct indirect items */