pass0.c

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

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

#include "fsck.h"



/* 
 * Pass0 scans the used part of the partition. It creates two maps which will 
 * be used on the pass 1. These are a map of nodes looking like leaves and 
 * a map of "bad" unformatted nodes. After pass 0 we can detect unformatted 
 * node pointers pointing to leaves. 
 */


/* leaves */
reiserfs_bitmap_t * leaves_bitmap;
#define pass0_is_leaf(block) __is_marked (leaves, block)
#define pass0_mark_leaf(block) __mark (leaves, block)

/* nodes which are referred to from only one indirect item */
reiserfs_bitmap_t * good_unfm_bitmap;
#define pass0_is_good_unfm(block) __is_marked (good_unfm, block)
#define pass0_mark_good_unfm(block) __mark (good_unfm, block)
#define pass0_unmark_good_unfm(block) __unmark (good_unfm, block)

/* nodes which are referred to from more than one indirect item */
reiserfs_bitmap_t * bad_unfm_bitmap;
#define pass0_is_bad_unfm(block) __is_marked (bad_unfm, block)
#define pass0_mark_bad_unfm(block) __mark (bad_unfm, block)
#define pass0_unmark_bad_unfm(block) __unmark (bad_unfm, block)

static int correct_direct_item_offset (__u64 offset, int format) {
    if (format == KEY_FORMAT_2) {
        return (offset && ((offset - 1) % 8 == 0));
    } else {
	return (offset);
    }
    return 0;
}

/* bitmaps which are built on pass 0 and are used on pass 1 */
static void make_aux_bitmaps (reiserfs_filsys_t * fs)
{
    struct reiserfs_super_block * sb;

    sb = fs->fs_ondisk_sb;

    /* bitmap of leaves found on the device */
    leaves_bitmap = reiserfs_create_bitmap (get_sb_block_count (sb));

    good_unfm_bitmap = reiserfs_create_bitmap (get_sb_block_count (sb));

    bad_unfm_bitmap = reiserfs_create_bitmap (get_sb_block_count (sb));
}


void delete_aux_bitmaps (void)
{
    reiserfs_delete_bitmap (leaves_bitmap);
    reiserfs_delete_bitmap (good_unfm_bitmap);
    reiserfs_delete_bitmap (bad_unfm_bitmap);
}


/* register block some indirect item points to */
static void register_unfm (unsigned long block)
{
    if (!pass0_is_good_unfm (block) && !pass0_is_bad_unfm (block)) {
	/* this block was not pointed by other indirect items yet */
	pass0_mark_good_unfm (block);
	return;
    }

    if (pass0_is_good_unfm (block)) {
	/* block was pointed once already, unmark it in bitmap of good
           unformatted nodes and mark in bitmap of bad pointers */
	pass0_unmark_good_unfm (block);
	pass0_mark_bad_unfm (block);
	return;
    }

    assert (pass0_is_bad_unfm (block));
}


/* 'upper' item is correct if 'upper + 2' exists and its key is greater than
   key of 'upper' */
static int upper_correct (struct buffer_head * bh, struct item_head * upper,
			  int upper_item_num)
{
    if (upper_item_num + 2 < B_NR_ITEMS (bh)) {
	if (comp_keys (&upper->ih_key, &(upper + 2)->ih_key) != -1)
	    /* item-num's item is out of order of order */
	    return 0;
	return 1;
    }
    
    /* there is no item above the "bad pair" */
    return 2;
}


/* 'lower' item is correct if 'lower - 2' exists and its key is smaller than
   key of 'lower' */
static int lower_correct (struct buffer_head * bh, struct item_head * lower,
			  int lower_item_num)
{
    if (lower_item_num - 2 >= 0) {
	if (comp_keys (&(lower - 2)->ih_key, &lower->ih_key) != -1)
	    return 0;
	return 1;
    }
    return 2;
}


/* return 1 if something was changed */
static int correct_key_format (struct item_head * ih, int symlink)
{
    int dirty = 0;

    if (is_stat_data_ih (ih)) {
	/* for stat data we have no way to check whether key format in item
	   head matches to the key format found from the key directly */
	if (get_ih_item_len (ih) == SD_V1_SIZE) {
	    if (get_ih_key_format (ih) != KEY_FORMAT_1) {
		/*fsck_log ("correct_key_format: ih_key_format of (%H) is set to format 1\n",
		  ih);*/
		set_ih_key_format (ih, KEY_FORMAT_1);
		return 1;
	    }
	    return 0;
	}
	if (get_ih_item_len (ih) == SD_SIZE) {
	    if (get_ih_key_format (ih) != KEY_FORMAT_2) {
		/*fsck_log ("correct_key_format: ih_key_format of (%H) is set to format 2\n",
		  ih);*/
		set_ih_key_format (ih, KEY_FORMAT_2);
		return 1;
	    }
	    return 0;
	}
	
	die ("stat_data item of the wrong length");
    }
    
    if (symlink && is_direct_ih(ih) && (key_format(&ih->ih_key) != KEY_FORMAT_1)) {	
	/* All symlinks are of 3.5 format */
	/*fsck_log ("correct_key_format: Symlink keys should be of 3.5 format. %k - fixed.\n", &ih->ih_key); */
	set_type_and_offset(KEY_FORMAT_1, &ih->ih_key, get_offset(&ih->ih_key), get_type(&ih->ih_key));
    }
	
    if (key_format (&ih->ih_key) != get_ih_key_format (ih)) {
	/*fsck_log ("correct_key_format: ih_key_format of (%H) is set to format found in the key\n",
	  ih);*/
	set_ih_key_format (ih, key_format (&ih->ih_key));
	dirty = 1;
    }
    
    if (is_direct_ih (ih) && get_offset (&ih->ih_key) > fs->fs_blocksize * 4) {
	/*fsck_log ("correct_key_format: %H made of indirect type\n", ih);*/
	set_type (key_format (&ih->ih_key), &ih->ih_key, TYPE_INDIRECT);
	if (get_offset (&ih->ih_key) % fs->fs_blocksize != 1)
	    fsck_log ("correct_key_format: Item header's key has the wrong offset %H\n", ih);
	dirty = 1;
    }
    
    return dirty;
}

#if 0
/* fixme: we might try all available hashes */
static int prob_name (reiserfs_filsys_t * fs,
		      char ** name, int max_len, __u32 deh_offset)
{
    int start; /* */
    int len;

    for (start = 0; start < max_len; start ++) {
	for (len = 0; len < max_len - start; len ++) {
	    if (is_properly_hashed (fs, *name + start, len + 1, deh_offset)) {
		*name = *name + start;
		return len + 1;
	    }
	}
    }
    return 0;
}
#endif


static void hash_hits_init (reiserfs_filsys_t * fs)
{
    fsck_data (fs)->rebuild.hash_amount = known_hashes ();
    fsck_data (fs)->rebuild.hash_hits = getmem (sizeof (unsigned long) * fsck_data (fs)->rebuild.hash_amount);
    return;
}


static void add_hash_hit (reiserfs_filsys_t * fs, int hash_code)
{
    fsck_data (fs)->rebuild.hash_hits [hash_code] ++;
}


/* deh_location look reasonable, try to find name length. return 0 if
   we failed */
static int try_to_get_name_length (struct item_head * ih, struct reiserfs_de_head * deh,
				int i)
{
    int len;

    if (i == 0 || !de_bad_location (deh - 1)) {
	len = name_in_entry_length (ih, deh, i);
	return (len > 0) ? len : 0;
    }

    /* previous entry had bad location so we had no way to find
       name length */
    return 0;
}



/* define this if you are using -t to debug recovering of corrupted directory
   item */
#define DEBUG_VERIFY_DENTRY
#undef DEBUG_VERIFY_DENTRY


/* check directory item and try to recover something */
static int verify_directory_item (reiserfs_filsys_t * fs, struct buffer_head * bh,
				  int item_num)
{
    struct item_head * ih;
    struct item_head tmp;
    char * item;
    struct reiserfs_de_head * deh;
    char * name;
    int name_len;
    int bad, lost_found;
    int i, j;
    char buf[4096];
    int dirty;
    int hash_code;
    int bad_locations;
    int min_entry_size = 1;

#ifdef DEBUG_VERIFY_DENTRY
    char * direntries;
#endif


    ih = B_N_PITEM_HEAD (bh, item_num);
    item = B_I_PITEM (bh,ih);
    deh = (struct reiserfs_de_head *)item;

    dirty = 0;
    bad_locations = 0;
 
    if ( (get_ih_entry_count (ih) > (get_ih_item_len(ih) / (DEH_SIZE + min_entry_size))) ||
          (get_ih_entry_count (ih) == 0))
    {
        set_ih_entry_count (ih, (int)get_ih_item_len(ih) / (DEH_SIZE + min_entry_size));
        mark_buffer_dirty (bh);
    }

    if (get_ih_entry_count (ih) == 0) {
	delete_item (fs, bh, item_num);
	return -1;
    }


    /* check deh_location */
    for (i = 0; i < get_ih_entry_count (ih); i ++) {
	/* silently fix deh_state */
	if (get_deh_state (deh + i) != (1 << DEH_Visible2)) {
	    set_deh_state (deh + i, (1 << DEH_Visible2));
	    mark_buffer_dirty (bh);
	}
	if (dir_entry_bad_location (deh + i, ih, !i))
	    mark_de_bad_location (deh + i);
    }    

#ifdef DEBUG_VERIFY_DENTRY
    direntries = getmem (ih_entry_count (ih) * sizeof (int));

    printf ("Entries with bad locations within the directory: ");
    for (i = 0; i < ih_entry_count (ih); i ++) {
	if (de_bad_location (deh + i))
	    printf ("%d ", i);
    }
    printf ("\n");
#endif /* DEBUG_VERIFY_DENTRY */


    /* find entries names in which have mismatching deh_offset */
    for (i = get_ih_entry_count (ih) - 1; i >= 0; i --) {
	if (de_bad (deh + i))
	    /* bad location */
	    continue;

	if (i) {
	    if (get_deh_location (deh + i - 1) < get_deh_location (deh + i))
		mark_de_bad_location (deh + i - 1);
	}

	name = name_in_entry (deh + i, i);
	/* Although we found a name, we not always can get its length as
           it depends on deh_location of previous entry. */
	name_len = try_to_get_name_length (ih, deh + i, i);

#ifdef DEBUG_VERIFY_DENTRY
	if (name_len == 0)
	    printf ("Trying to find the name length for %d-th entry\n", i);
#endif /* DEBUG_VERIFY_DENTRY */
	if (is_dot (name, name_len)) {
	    if (i != 0)
		fsck_log ("block %lu: item %d: \".\" must be the first entry, but it is the %d-th entry\n",
			  bh->b_blocknr, item_num, i);
	    /* check and fix "." */
	    
	    if (get_deh_offset (deh + i) != DOT_OFFSET) {
		set_deh_offset (deh + i, DOT_OFFSET);
		mark_buffer_dirty (bh);
	    }
	    /* "." must point to the directory it is in */
/*
	    if (not_of_one_file (&(deh[i].deh2_dir_id), &(ih->ih_key))) {
		fsck_log ("verify_direntry: block %lu, item %H has entry \".\" "
			  "pointing to (%K) instead of (%K)\n", 
			  bh->b_blocknr, ih,
			  &(deh[i].deh2_dir_id), &(ih->ih_key));
		set_deh_dirid (deh + i, get_key_dirid (&ih->ih_key));
		set_deh_objectid (deh + i, get_key_objectid (&ih->ih_key));
		mark_buffer_dirty (bh);
	    }
*/
	} else if (is_dot_dot (name, name_len)) {
	    if (i != 1)
		fsck_log ("block %lu: item %d: \"..\" is %d-th entry\n",
			  bh->b_blocknr, item_num, i);
	    
	    /* check and fix ".." */
	    if (get_deh_offset (deh + i) != DOT_DOT_OFFSET) {
		set_deh_offset (deh + i, DOT_DOT_OFFSET);
		mark_buffer_dirty (bh);
	    }
	} else {
	    int min_length, max_length;

	    /* check other name */

	    if (name_len == 0) {
		/* we do not know the length of name - we will try to find it */
		min_length = 1;
		max_length = item + get_ih_item_len (ih) - name;
	    } else
		/* we kow name length, so we will try only one name length */
		min_length = max_length = name_len;

	    hash_code = 0;

	    for (j = min_length; j <= max_length; j ++) {
		hash_code = find_hash_in_use (name, j, get_deh_offset (deh + i),
					      get_sb_hash_code (fs->fs_ondisk_sb));
/*		add_hash_hit (fs, hash_code);*/
		if (code2func (hash_code) != 0) {
		    /* deh_offset matches to some hash of the name */
		    if (fsck_hash_defined (fs) && 
			hash_code != func2code (fs->fs_hash_function)) {
			/* wrong hash selected - so we can skip this leaf */
			return 1;
		    }

		    if (!name_len) {
			fsck_log ("%s: block %lu, item %H: Found a name \"%.*s\" for %d-th entry "
				  "matching to the hash %u.\n", __FUNCTION__,
				  bh->b_blocknr, ih, j, name, i, get_deh_offset (deh + i));
			/* FIXME: if next byte is 0 we think that the name is aligned to 8 byte boundary */
			if (i) {
			    set_deh_location (&deh[i - 1], get_deh_location (deh + i) +
					    ((name[j] || fs->fs_format == REISERFS_FORMAT_3_5) ? j : ROUND_UP (j)));
			    mark_de_good_location (deh + i - 1);
			    mark_buffer_dirty (bh);
			}
		    }
		    break;
		}