check_tree.c

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

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

#include "fsck.h"

#if 0
struct check_relocated {
    __u32 old_dir_id;
    __u32 old_objectid;
    /*mode_t mode;*/
    struct check_relocated * next;
};

static struct check_relocated * relocated_list;

void to_be_relocated (struct key * key)
{
    struct check_relocated * cur, * prev, * new_relocated;

    cur = relocated_list;
    prev = 0;

    while (cur && comp_short_keys(key, (struct key *)cur) != 1) {
	if (comp_short_keys (key, (struct key *)cur) == 0)
	    return;
	prev = cur;
        cur = cur->next;
    }
        
    new_relocated = getmem (sizeof (struct check_relocated));
    copy_short_key ((struct key *)new_relocated, key);
             
    if (prev) {
        new_relocated->next = prev->next;
        prev->next = new_relocated;
    } else {
        new_relocated->next = relocated_list;
        relocated_list = new_relocated;
    }
}

int should_be_relocated (struct key * key)
{
    struct check_relocated *cur, *prev;
    int ret = 0;

    if (!key)
	return 0;
    
    cur = relocated_list;

    prev = NULL;
    while (cur && comp_short_keys(key, (struct key *)cur) != 1) {
	if (comp_short_keys (key, (struct key *)cur) == 0) {
	    ret = 1;
	    break;
	}
	prev = cur;
	cur = cur->next;
    }
 
    if (ret) {
	/* cur is found */
	if (prev) /* not the first */
	    prev->next = cur->next;
	else /* first */
	    relocated_list = cur->next;
	freemem (cur);
    }
 
    return ret;    
}

void clear_relocated_list() {
    struct check_relocated *next;

    while (relocated_list) {
        next = relocated_list->next;
        freemem (relocated_list);
        relocated_list = next;
    }
}

#endif

//
//
//
// check_fs_tree stops and recommends to run fsck --rebuild-tree when:
// 1. read fails
// 2. node of wrong level found in the tree
// 3. something in the tree points to wrong block number
//      out of filesystem boundary is pointed by tree
//      to block marked as free in bitmap
//      the same block is pointed from more than one place
//      not data blocks (journal area, super block, bitmaps)
// 4. bad formatted node found
// 5. delimiting keys are incorrect
//      



/* mark every block we see in the tree in control bitmap, so, when to make
   sure, that no blocks are pointed to from more than one place we use
   additional bitmap (control_bitmap). If we see pointer to a block we set
   corresponding bit to 1. If it is set already - run fsck with --rebuild-tree */
static reiserfs_bitmap_t * control_bitmap;
static reiserfs_bitmap_t * source_bitmap;

static int tree_scanning_failed = 0;


/* 1 if block is not marked as used in the bitmap */
static int is_block_free (reiserfs_filsys_t * fs, unsigned long block)
{
    return !reiserfs_bitmap_test_bit (source_bitmap, block);
}


/*static int hits = 0;*/

/* we have seen this block in the tree, mark corresponding bit in the
   control bitmap */
static void we_met_it (unsigned long block)
{
    reiserfs_bitmap_set_bit (control_bitmap, block);
    /*hits ++;*/
}


/* have we seen this block somewhere in the tree before? */
static int did_we_meet_it (unsigned long block)
{
    return reiserfs_bitmap_test_bit (control_bitmap, block);
}


static void init_control_bitmap (reiserfs_filsys_t * fs)
{
    unsigned int i;
    unsigned long block;
    unsigned long reserved;
    

    control_bitmap = reiserfs_create_bitmap(get_sb_block_count(fs->fs_ondisk_sb));
    if (!control_bitmap)
	die ("init_control_bitmap: Failed to allocate a control bitmap.");

    /*printf ("Initially number of zeros in control bitmap %d\n", 
	      reiserfs_bitmap_zeros (control_bitmap));*/

    /* skipped and super block */
    for (i = 0; i <= fs->fs_super_bh->b_blocknr; i ++)
    	we_met_it (i);

    /*printf ("SKIPPED: %d blocks marked used (%d)\n", hits, 
              reiserfs_bitmap_zeros (control_bitmap));
      hits = 0;*/

    /* bitmaps */
    block = fs->fs_super_bh->b_blocknr + 1;
    for (i = 0; i < get_sb_bmap_nr (fs->fs_ondisk_sb); i ++) {
        we_met_it (block);

	if (spread_bitmaps (fs))
	    block = (block / (fs->fs_blocksize * 8) + 1) * 
		    (fs->fs_blocksize * 8);
	else
	    block ++;	
    }
    
    /*printf ("BITMAPS: %d blocks marked used (%d)\n", hits, 
	      reiserfs_bitmap_zeros (control_bitmap));
	      
      hits = 0;*/
    
    /* mark as used area of the main device either containing a journal or
       reserved to hold it */

    reserved = get_size_of_journal_or_reserved_area (fs->fs_ondisk_sb);
    
    /* where does journal area (or reserved journal area) start from */

    if (!is_new_sb_location (fs->fs_super_bh->b_blocknr, fs->fs_blocksize) &&
    	!is_old_sb_location (fs->fs_super_bh->b_blocknr, fs->fs_blocksize))
	die ("init_control_bitmap: Wrong super block location. You must run "
	     "--rebuild-sb.");

    block = get_journal_start_must (fs);

    for (i = block; i < reserved + block; i ++)
	we_met_it (i);

    if (fs->fs_badblocks_bm)
	for (i = 0; i < get_sb_block_count (fs->fs_ondisk_sb); i ++) {
	    if (reiserfs_bitmap_test_bit (fs->fs_badblocks_bm, i))
	    	we_met_it (i);	
	}
}


/* if we managed to complete tree scanning and if control bitmap and/or proper
   amount of free blocks mismatch with bitmap on disk and super block's
   s_free_blocks - we can fix that */
static void handle_bitmaps (reiserfs_filsys_t * fs)
{
    int problem = 0;

    if (tree_scanning_failed) {
	fsck_progress ("Could not scan the internal tree. --rebuild-tree "
		       "is required\n");
	return;
    }

    fsck_progress ("Comparing bitmaps..");

    /* check free block counter */
    if (get_sb_free_blocks (fs->fs_ondisk_sb) != 
	reiserfs_bitmap_zeros (control_bitmap)) 
    {
/*	fsck_log ("vpf-10630: The count of free blocks in the on-disk bitmap "
		  "(%lu) mismatches with the correct one (%lu).\n",  
		  get_sb_free_blocks (fs->fs_ondisk_sb),
		  reiserfs_bitmap_zeros (control_bitmap));
*/
	problem++;
    }

    if (reiserfs_bitmap_compare (source_bitmap, control_bitmap))
	problem++;    

    if (problem) {
        if (fsck_mode (fs) == FSCK_FIX_FIXABLE) {
	    fsck_log ("vpf-10630: The on-disk and the correct bitmaps differs. "
		"Will be fixed later.\n");
//            fsck_progress ("Trying to fix bitmap ..\n");
            /* mark blocks as used in source bitmap if they are used in 
	       control bitmap */
            reiserfs_bitmap_disjunction (source_bitmap, control_bitmap);
            /* change used blocks count accordinly source bitmap, copy bitmap 
	       changes to on_disk bitmap */
            set_sb_free_blocks (fs->fs_ondisk_sb, 
				reiserfs_bitmap_zeros(source_bitmap));
            reiserfs_bitmap_copy (fs->fs_bitmap2, source_bitmap);
            mark_buffer_dirty (fs->fs_super_bh);
/*
            // check again 
            if ((diff = reiserfs_bitmap_compare(source_bitmap, 
						control_bitmap)) != 0)  
	    {
                // do not mark them as fatal or fixable because one can live 
		// with leaked space. So this is not a fatal corruption, and 
		// fix-fixable cannot fix it 
                fsck_progress (" bitmaps were not recovered.\n\tYou can either "
		"run rebuild-tree or live with %d leaked blocks\n", diff);
            } else {
                fsck_progress ("finished\n");
            }
*/
        } else if (problem) {
	    fsck_log ("vpf-10640: The on-disk and the correct bitmaps differs.\n");
            while (problem) {
                /* fixable corruptions because we can try to recover them 
		   without rebuilding the tree */
        	one_more_corruption (fs, FIXABLE); 
        	problem --;
            }
        }
    } else 
        fsck_progress ("finished\n");
        
    return;
}

static int auto_handle_bitmaps (reiserfs_filsys_t *fs) {
    unsigned long i;
    
    if (source_bitmap->bm_byte_size != control_bitmap->bm_byte_size)
	return -1;
    
    for (i = 0; i < source_bitmap->bm_byte_size; i ++) {
	if (control_bitmap->bm_map[i] & ~source_bitmap->bm_map[i]) {
	    return 1;
	}
    }
    
    return 0;
}


/* is this block legal to be pointed to by some place of the tree? */
static int bad_block_number (reiserfs_filsys_t * fs, unsigned long block)
{
    if (block >= get_sb_block_count (fs->fs_ondisk_sb) ||
	not_data_block (fs, block)) {
	/* block has value which can not be used as a pointer in a tree */
	
	return 1;
/*
	if (is_unfm_pointer) {
	    // unformatted node pointer will be zeroed
	    one_more_corruption (fs, fixable);
	    return 1;
	}

	// internal nodes can not have wrong pointer
	one_more_corruption (fs, fatal);
	return 1;
*/

    }

    if (is_block_free (fs, block)) {
	/* block is marked free - bitmap problems will be handled later */
	//one_more_corruption (fs, fixable);
    }

    return 0;
}


static int got_already (reiserfs_filsys_t * fs, unsigned long block)
{
    if (did_we_meet_it (block)) {
	/* block is in tree at least twice */
    	return 1;
    }
    we_met_it (block);
    return 0;
}

/* 1 if it does not look like reasonable stat data */
static int bad_stat_data (reiserfs_filsys_t * fs, 
			  struct buffer_head * bh, 
			  struct item_head * ih)
{
    unsigned long objectid;
//    __u32 links;

    objectid = get_key_objectid (&ih->ih_key);
    if (!is_objectid_used (fs, objectid)) {
	/* FIXME: this could be cured right here */
	fsck_log ("bad_stat_data: The objectid (%lu) is marked free, but used "
		  "by an object %k\n", objectid, &ih->ih_key);

        /* if it is FIX_FIXABLE we flush objectid map at the end
           no way to call one_less_corruption later
        */
	if (fsck_mode (fs) != FSCK_FIX_FIXABLE)
	    one_more_corruption (fs, FIXABLE);
    }

    if (id_map_mark(proper_id_map (fs), objectid)) {
	fsck_log ("bad_stat_data: The objectid (%lu) is shared by at least two "
		  "files. Can be fixed with --rebuild-tree only.\n", objectid);
#if 0
	to_be_relocated (&ih->ih_key);
//	one_more_corruption (fs, FIXABLE);	
#endif
    }

    return 0;
/* Check this on semantic_check pass.    

    sd = (struct stat_data *)B_I_PITEM(bh,ih);
    get_sd_nlink (ih, sd, &links);
    if (S_ISDIR(sd->sd_mode)) {
        if (links < 2) {
            fsck_log ("%s: block %lu: The directory StatData %k has bad nlink number (%u)\n",
                __FUNCTION__, bh->b_blocknr, &ih->ih_key, links);
            one_more_corruption (fs, fatal);
        }
    } else {
        if (links == 0) {
            fsck_log ("%s: block %lu: The StatData %k has bad nlink number (%u)\n",
                __FUNCTION__, bh->b_blocknr, &ih->ih_key);
            one_more_corruption (fs, fatal);
        }
    }
*/    
}


/* it looks like we can check item length only */
static int bad_direct_item (reiserfs_filsys_t * fs, 
			    struct buffer_head * bh, 
			    struct item_head * ih)
{
    return 0;
}