fsck/check_tree.c

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

#include "fsck.h"

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;
    }
}

//
//
//
// 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\n", objectid);
	if (fsck_mode (fs) == FSCK_FIX_FIXABLE) 
            to_be_relocated (&ih->ih_key);
	    
//	one_more_corruption (fs, FIXABLE);	
    }

    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;
}


inline void handle_one_pointer (reiserfs_filsys_t * fs, struct buffer_head * bh, __u32 * ptr) {
    if (fsck_mode (fs) == FSCK_FIX_FIXABLE) {
	fsck_log (" - zeroed");
	*ptr = 0;
	mark_buffer_dirty (bh);
    } else {
	one_more_corruption (fs, FIXABLE);
    }
}

/*
static int bad_badblocks_item (reiserfs_filsys_t * fs, struct buffer_head * bh,
			      struct item_head * ih) {
    int i;
    __u32 * ind = (__u32 *)B_I_PITEM (bh, ih);

    if (get_ih_item_len (ih) % 4) {
	fsck_log ("%s: block %lu: item (%H) has bad length\n", __FUNCTION__,
		  bh->b_blocknr, ih);
	one_more_corruption (fs, fatal);
	return 1;
    }

    for (i = 0; i < I_UNFM_NUM (ih); i ++) {
//	__u32 unfm_ptr;

//	unfm_ptr = le32_to_cpu (ind [i]);
	if (!le32_to_cpu (ind [i])) {
	    fsck_log ("%s: block %lu: badblocks item (%H) has zero pointer.");
	    fsck_log ("Not an error, but could be deleted with --fix-fixable\n",
	    		__FUNCTION__, bh->b_blocknr, ih);
	    continue;
	}

	// check list of badblocks pointers
	if (le32_to_cpu (ind [i]) >= get_sb_block_count (fs->fs_ondisk_sb)) {
	    fsck_log ("%s: badblock pointer (block %lu) points out of disk spase (%lu)",
			__FUNCTION__, bh->b_blocknr, le32_to_cpu (ind [i]));
	    handle_one_pointer (fs, bh, &ind[i]);
	    fsck_log ("\n");
	}

	if (did_we_meet_it (le32_to_cpu (ind [i]))) {
	    // it can be
	    // 1. not_data_block
	    // 		delete pointer
	    // 2. ind [i] or internal/leaf	       		
	    //    advice to run fix-fixable if there is no fatal errors
	    //    with list of badblocks, say that it could fix it.
	
	    if (not_data_block (fs, le32_to_cpu (ind [i]))) {
		fsck_log ("%s: badblock pointer (block %lu) points on fs metadata (%lu)",
			__FUNCTION__, bh->b_blocknr, le32_to_cpu (ind [i]));
		handle_one_pointer (fs, bh, &ind[i]);
		fsck_log ("\n");
	    } else {
	        one_more_corruption (fs, badblocks);
	        fsck_log ("%s: badblock item points to a block"
	        	  " which in the tree already. Use --badblock-file option"
	        	  " to fix the problem\n", __FUNCTION__);
	    }
	} else {
	    we_met_it (le32_to_cpu (ind [i]));
	}
    }

    return 0;
}
*/

/* for each unformatted node pointer: make sure it points to data area and
   that it is not in the tree yet */
static int bad_indirect_item (reiserfs_filsys_t * fs, struct buffer_head * bh,
			      struct item_head * ih)
{
    __u32 * ind = (__u32 *)B_I_PITEM (bh, ih);
    unsigned int i;

    if (get_ih_item_len (ih) % 4) {
	fsck_log ("%s: block %lu: The item (%H) has the bad length (%u)\n",
	    __FUNCTION__, bh->b_blocknr, ih, get_ih_item_len (ih));
	one_more_corruption (fs, FATAL);
	return 1;
    }

    for (i = 0; i < I_UNFM_NUM (ih); i ++) {
//	__u32 unfm_ptr;

	fsck_check_stat (fs)->unfm_pointers ++;
//	unfm_ptr = le32_to_cpu (ind [i]);
	if (!le32_to_cpu (ind [i])) {
	    fsck_check_stat (fs)->zero_unfm_pointers ++;
	    continue;
	}

	/* check unformatted node pointer and mark it used in the
           control bitmap */
	if (bad_block_number (fs, le32_to_cpu (ind [i]))) {
	    fsck_log ("%s: block %lu: The item %k has the bad pointer (%d) to the block (%lu)",
		      __FUNCTION__, bh->b_blocknr, &ih->ih_key, i, le32_to_cpu (ind [i]));
	    handle_one_pointer (fs, bh, &ind[i]);
	    fsck_log ("\n");
	    continue;
	}

        if (got_already (fs, le32_to_cpu (ind [i]))) {
	    fsck_log ("%s: block %lu: The item (%H) has the bad pointer (%d) to the block (%lu), "
		"which is in tree already", __FUNCTION__, bh->b_blocknr, ih, i, le32_to_cpu (ind [i]));
	    handle_one_pointer (fs, bh, &ind [i]);
	    fsck_log ("\n");
            continue;
	}
    }

#if 0
    /* delete this check for 3.6 */
    if (get_ih_free_space (ih) > fs->fs_blocksize - 1) {
        if (fsck_mode (fs) == FSCK_FIX_FIXABLE) {
            /*FIXME: fix it if needed*/
        } else {
            fsck_log ("bad_indirect_item: %H has wrong ih_free_space\n", ih);
            one_more_corruption (fs, fixable);
        }
    }
#endif

    return 0;
}


/* FIXME: this was is_bad_directory from pass0.c */
static int bad_directory_item (reiserfs_filsys_t * fs, struct buffer_head * bh, struct item_head * ih)
{
    char * name;
    int namelen;
    unsigned int count, i;
    struct reiserfs_de_head * deh = B_I_DEH (bh, ih);
    int min_entry_size = 1;/* We have no way to understand whether the
                              filesystem was created in 3.6 format or
                              converted to it. So, we assume that minimal name
                              length is 1 */
    __u16 state;

    count = get_ih_entry_count (ih);

    if (count == 0) {
	one_more_corruption (fs, FATAL);	
	return 1;
    }
    
    /* make sure item looks like a directory */
    if (get_ih_item_len (ih) / (DEH_SIZE + min_entry_size) < count) {
	/* entry count can not be that big */
	fsck_log ("%s: block %lu: The directory item %k has the exsessively big entry count (%u)\n",
	    __FUNCTION__, bh->b_blocknr, &ih->ih_key, count);
	one_more_corruption (fs, FATAL);	
	return 1;
    }

    if (get_deh_location (&deh[count - 1]) != DEH_SIZE * count) {
	/* last entry should start right after array of dir entry headers */
	fsck_log ("%s: block %lu: The directory item %k has the corrupted entry structure\n",
	    __FUNCTION__, bh->b_blocknr, &ih->ih_key);
	one_more_corruption (fs, FATAL);
	return 1;
    }
    
    /* check name hashing */
    for (i = 0; i < count; i ++, deh ++) {
	namelen = name_in_entry_length (ih, deh, i);
	name = name_in_entry (deh, i);
	if (!is_properly_hashed (fs, name, namelen, get_deh_offset (deh))) {
	    fsck_log ("%s: block %lu: The directory item %k has a not properly hashed entry (%d)\n",
			__FUNCTION__, bh->b_blocknr, &ih->ih_key, i);
	    one_more_corruption (fs, FATAL);	
	    return 1;
	}
    }

    deh = B_I_DEH (bh, ih);
    state = (1 << DEH_Visible2);
    /* ok, items looks like a directory */
    for (i = 0; i < count; i ++, deh ++) {
	if (get_deh_state (deh) != state) {
	    fsck_log ("bad_directory_item: block %lu: The directory item %k has the entry (%d) "
		      "\"%.*s\" with a not legal state (%o), (%o) expected",
		      bh->b_blocknr, &ih->ih_key, i, name_in_entry_length (ih, deh, i),
		      name_in_entry (deh, i), get_deh_state (deh), state);
	    if (fsck_mode (fs) == FSCK_FIX_FIXABLE) {
		set_deh_state (deh, 1 << DEH_Visible2);
		mark_buffer_dirty (bh);
		fsck_log (" - corrected\n");
	    } else 
		one_more_corruption (fs, FIXABLE);
	    
	    fsck_log ("\n");
	}
    }

    return 0;
}


static int bad_item (reiserfs_filsys_t * fs, struct buffer_head * bh, int num)
{
    struct item_head * ih;
    int format;

    ih = B_N_PITEM_HEAD (bh, num);

    if ((get_ih_flags(ih)) != 0) {
	if (fsck_mode(fs) != FSCK_FIX_FIXABLE) {
	    one_more_corruption (fs, FIXABLE);
	    fsck_log ("%s: vpf-10570: block %lu: The item header (%d) has not cleaned flags.\n", 
		__FUNCTION__, bh->b_blocknr, num);
	} else {
	    fsck_log ("%s: vpf-10580: block %lu: Flags in the item header (%d) were cleaned\n",
		__FUNCTION__, bh->b_blocknr, num);
	    clean_ih_flags(ih);
	    mark_buffer_dirty(bh);
	}
    }

    
    if (is_stat_data_ih(ih) && get_ih_item_len(ih) == SD_SIZE)
	format = KEY_FORMAT_2;
    else if (is_stat_data_ih(ih) && get_ih_item_len(ih) == SD_V1_SIZE)
	format = KEY_FORMAT_1;
    else 
	format = key_format(&ih->ih_key);
    
    if (format != get_ih_key_format(ih)) {
	if (fsck_mode(fs) != FSCK_FIX_FIXABLE) {
	    one_more_corruption (fs, FIXABLE);
	    fsck_log ("%s: vpf-10710: block %lu: The format (%d) specified in the item header (%d) "
		"differs from the key format (%d).\n", __FUNCTION__, bh->b_blocknr, 
		get_ih_key_format(ih), num, format);
	} else {
	    fsck_log ("%s: vpf-10720: block %lu: The format (%d) specified in the item header (%d) "
		"was fixed to the key format (%d).\n", __FUNCTION__, bh->b_blocknr, 
		get_ih_key_format(ih), num, format);

	    set_ih_key_format(ih, format);
	    mark_buffer_dirty(bh);
	}
    }

    if (get_key_dirid (&ih->ih_key) == (__u32)-1) {
	if (get_key_objectid (&ih->ih_key) != (__u32)-1) {
	    /*  safe link can be
		-1 object_id           0x1	INDIRECT (truncate) or
		-1 object_id   blocksize+1	DIRECT   (unlink)
	    */

	    if (is_direct_ih(ih))
		if (get_offset(&ih->ih_key) == fs->fs_blocksize + 1)
		    if (get_ih_item_len (ih) == 4) {
			/*fsck_log("vpf-00010: safe link found %k\n", &ih->ih_key);*/
			fsck_check_stat(fs)->safe ++;
			return 0;
		    }

	    if (is_indirect_ih(ih))
		if(get_offset(&ih->ih_key) == 0x1)
		    if (get_ih_item_len (ih) == 4) {
			/*fsck_log("vpf-00020: safe link found %k\n", &ih->ih_key);*/
			fsck_check_stat(fs)->safe ++;
			return 0;
		    }
	
	    /* it does not look like safe link */

	    /* dir_id == -1 can be used only by safe links */
	    one_more_corruption (fs, FATAL);
	    fsck_log ("%s: vpf-10290: block %lu, item %d: The item has a wrong key %k\n", 
		__FUNCTION__, num, bh->b_blocknr, &ih->ih_key);
	    return 1;
	} else {

/*              BAD BLOCK LIST SUPPORT
            if (is_indirect_ih (ih)) {
	    // it looks like badblocks item
	    if (fs->fs_badblocks_bm)
	    	return 0;
	    else
		return bad_badblocks_item (fs, bh, ih);
	} else  {*/

	    one_more_corruption (fs, FATAL);
	    fsck_log ("%s: vpf-10300: block %lu, item %d: The item has a wrong key %k\n", 
		__FUNCTION__, num, bh->b_blocknr, &ih->ih_key);
	    return 1;
	}
    } else if (get_key_objectid (&ih->ih_key) == (__u32)-1) {
	one_more_corruption (fs, FATAL);
	fsck_log ("%s: vpf-10310: block %lu, item %d: The item has a wrong key %k\n", 
	    __FUNCTION__, num, bh->b_blocknr, &ih->ih_key);
	return 1;
    }

    if (is_stat_data_ih (ih))
	return bad_stat_data (fs, bh, ih);

    if (is_direct_ih (ih))
	return bad_direct_item (fs, bh, ih);

    if (is_indirect_ih(ih))
	return bad_indirect_item (fs, bh, ih);
    
    return bad_directory_item (fs, bh, ih);
}


/* 1 if i-th and (i-1)-th items can not be neighbors in a leaf */
int bad_pair (reiserfs_filsys_t * fs, struct buffer_head * bh, int pos)
{
    struct item_head * ih;

    ih = B_N_PITEM_HEAD (bh, pos);

    if (comp_keys (&((ih - 1)->ih_key), &ih->ih_key) != -1) {
	if (fsck_mode (fs) != FSCK_REBUILD)
	    one_more_corruption (fs, FATAL);	
	return 1;
    }

    if (is_stat_data_ih (ih))
	/* left item must be of another object */
	if (comp_short_keys (&((ih - 1)->ih_key), &ih->ih_key) != -1) {
	    if (fsck_mode (fs) != FSCK_REBUILD)
		one_more_corruption (fs, FATAL);	
	    return 1;
	}

    if (get_key_dirid (&ih->ih_key) == (__u32)-1) {
    	if (get_key_objectid (&ih->ih_key) == (__u32)-1) {
/*              BAD BLOCK LIST SUPPORT
    	    if (is_indirect_ih (ih) && comp_short_keys (&((ih - 1)->ih_key), &ih->ih_key) != 0)
		return 0; // badblocks item
*/
	    /* it does not look like badblocks item */
    	} else {
    	    /* safe link ? */
	    if (comp_short_keys (&((ih - 1)->ih_key), &ih->ih_key) == 0) {
		if (is_indirect_ih (ih - 1) && is_direct_ih(ih))
		    return 0; /* safe link */
		/* they do not look like safe links */
	    } else {
		if (is_indirect_ih (ih) || is_direct_ih(ih))
		    return 0; /* safe link */
		/* it does not look like safe link */
	    }
    	}
    }

    if (is_direct_ih(ih)) {
	/* left item must be indirect or stat data item of the same
	   file */
	if (not_of_one_file (&((ih - 1)->ih_key), &ih->ih_key)) {
	    if (fsck_mode (fs) != FSCK_REBUILD)
		one_more_corruption (fs, FATAL);
	    return 1;
	}

	if (!((is_stat_data_ih (ih - 1) && get_offset (&ih->ih_key) == 1) ||
	      (is_indirect_ih (ih - 1) &&	
	       get_offset (&(ih - 1)->ih_key) + get_bytes_number (ih-1, bh->b_size) ==
	       get_offset (&ih->ih_key)))) {
	    if (fsck_mode (fs) != FSCK_REBUILD)
		one_more_corruption (fs, FATAL);
	    return 1;
	}
    }

    if (is_indirect_ih (ih) || is_direntry_ih (ih)) {
	/* left item must be stat data of the same object */
	if (not_of_one_file (&((ih - 1)->ih_key), &ih->ih_key) ||
	    !is_stat_data_ih (ih - 1)) {
	    if (fsck_mode (fs) != FSCK_REBUILD)
		one_more_corruption (fs, FATAL);
	    return 1;
	}
    }

    return 0;
}

/* 1 if block head or any of items is bad */
static int bad_leaf (reiserfs_filsys_t * fs, struct buffer_head * bh)
{
    int i;

    if (leaf_structure_check(fs, bh))
	return 1;
    
    for (i = 0; i < B_NR_ITEMS (bh); i ++) {
	if (bad_item (fs, bh, i)) {
	    fsck_log ("bad_leaf: block %lu, item %d: The corrupted item found (%H)\n",
		bh->b_blocknr, i, B_N_PITEM_HEAD (bh, i));
	}

	if (i && bad_pair (fs, bh, i)) {
	    fsck_log ("bad_leaf: block %lu, items %d and %d: The wrong order of items: %k, %k\n",
		bh->b_blocknr, i-1, i, &B_N_PITEM_HEAD (bh, i-1)->ih_key, 
		&B_N_PITEM_HEAD (bh, i)->ih_key);
	}
    }
    return 0;
}

/* 1 if bh does not look like internal node */
static int bad_internal (reiserfs_filsys_t * fs, struct buffer_head * bh)
{
    int i;

    for (i = 0; i <= B_NR_ITEMS (bh); i ++) {
        if (i != B_NR_ITEMS (bh) && i != B_NR_ITEMS (bh) - 1)
	    /* make sure that keys are in increasing order */
            if (comp_keys (B_N_PDELIM_KEY (bh, i), B_N_PDELIM_KEY (bh, i + 1)) != -1) {
		fsck_log ("%s: vpf-10320: block %lu, items %d and %d: The wrong order "
		    "of items: %k, %k\n", __FUNCTION__, bh->b_blocknr, i, i+1, 
		    B_N_PDELIM_KEY (bh, i), B_N_PDELIM_KEY (bh, i + 1));
		one_more_corruption (fs, FATAL);
                return 1;
	    }

	/* make sure that the child is correct */
        if (bad_block_number (fs, get_dc_child_blocknr (B_N_CHILD (bh,i)))) {
	    fsck_log ("%s: vpf-10330: block %lu, item %d: The internal item points to the "
		"not legal block (%lu)\n", __FUNCTION__, bh->b_blocknr, i, 
		get_dc_child_blocknr (B_N_CHILD (bh,i)));
            one_more_corruption (fs, FATAL);
            return 1;
	}
    }
    return 0;
}


/* h == 0 for root level. block head's level == 1 for leaf level  */
static inline int h_to_level (reiserfs_filsys_t * fs, int h)
{
    return get_sb_tree_height (fs->fs_ondisk_sb) - h - 1;
}


/* bh must be formatted node. blk_level must be tree_height - h + 1 */
static int bad_node (reiserfs_filsys_t * fs, struct buffer_head ** path, int h)
{
    struct buffer_head ** pbh = &path[h];

    if (B_LEVEL (*pbh) != h_to_level (fs, h)) {
       	fsck_log ("block %lu: The level of the node (%d) is not correct, (%d) expected\n",
	    (*pbh)->b_blocknr, B_LEVEL (*pbh), h_to_level (fs, h));
	one_more_corruption (fs, FATAL);
        return 1;
    }

    if (bad_block_number (fs, (*pbh)->b_blocknr)) {
	one_more_corruption (fs, FATAL);
	fsck_log ("%s: vpf-10340: The node in the wrong block number (%lu) found in the tree\n",
	      __FUNCTION__, (*pbh)->b_blocknr);
	return 1;
    }

    if (got_already (fs, (*pbh)->b_blocknr)) {
	fsck_log ("%s: vpf-10350: The block (%lu) is used more than once in the tree.\n",
	      __FUNCTION__, (*pbh)->b_blocknr);
	one_more_corruption (fs, FATAL);
        return 1;
    }
    
    if (is_leaf_node (*pbh)) {
	fsck_check_stat (fs)->leaves ++;
	return bad_leaf (fs, *pbh);
    }
    
    fsck_check_stat (fs)->internals ++;
    return bad_internal (fs, *pbh);
}


/* internal node bh must point to block */
static int get_pos (struct buffer_head * bh, unsigned long block)
{
    int i;

    for (i = 0; i <= B_NR_ITEMS (bh); i ++) {
	if (get_dc_child_blocknr (B_N_CHILD (bh, i)) == block)
	    return i;
    }
    die ("An internal pointer to the block (%lu) cannot be found in the node (%lu)", 
	block, bh->b_blocknr);
    return 0;
}


/* path[h] - leaf node */
static struct key * lkey (struct buffer_head ** path, int h)
{
    int pos;

    while (h > 0) {
       pos = get_pos (path[h - 1], path[h]->b_blocknr);
       if (pos)
           return B_N_PDELIM_KEY(path[h - 1], pos - 1);
       h --;
    }
    return 0;
}


/* path[h] - leaf node */
static struct key * rkey (struct buffer_head ** path, int h)
{
    int pos;

    while (h > 0) {
       pos = get_pos (path[h - 1], path[h]->b_blocknr);
       if (pos != B_NR_ITEMS (path[h - 1]))
           return B_N_PDELIM_KEY (path[h - 1], pos);
       h --;
    }
    return 0;
}


/* are all delimiting keys correct */
static int bad_path (reiserfs_filsys_t * fs, struct buffer_head ** path, int h1)
{
    int h = 0;
    struct key * dk;
    int pos = 0;

    while (path[h])
	h ++;

    h--;
    
    // path[h] is leaf
    if (h != h1)
	die ("bad_path: The leaf is expected as the last element in the path");

    if (h)
	pos = get_pos (path[h - 1], path[h]->b_blocknr);

    dk = lkey (path, h);
    if (dk && comp_keys (dk, B_N_PKEY (path[h], 0))) {
	/* left delimiting key must be equal to the key of 0-th item in the
	   node */
	fsck_log ("bad_path: The left delimiting key %k of the node (%lu) must "
	    "be equal to the first element's key %k within the node.\n", dk, 
	    path[h]->b_blocknr, B_N_PKEY (path[h], 0));
	one_more_corruption (fs, FATAL);
	return 1;
    }
    
    dk = rkey (path, h);
    if (dk && comp_keys (dk, B_N_PKEY (path[h],
       get_blkh_nr_items (B_BLK_HEAD (path[h])) - 1)) != 1) {
	/* right delimiting key must be greater than the key of the last item in the node */
	fsck_log ("bad_path: The right delimiting key %k of the node (%lu) must "
	    "be greater than the last (%d) element's key %k within the node.\n", 
	    dk, path[h]->b_blocknr, get_blkh_nr_items (B_BLK_HEAD (path[h])) - 1, 
	    B_N_PKEY (path[h], get_blkh_nr_items (B_BLK_HEAD (path[h])) - 1));
	one_more_corruption (fs, FATAL);
	return 1;
    }

    if (h && (get_dc_child_size (B_N_CHILD(path[h-1],pos)) +
    	get_blkh_free_space ((struct block_head *)path[h]->b_data) +
    	BLKH_SIZE != path[h]->b_size))
    {
	/* wrong dc_size */
	fsck_log ("bad_path: block %lu, pointer %d: The used space (%d) of the "
	    "child block (%lu)", path[h-1]->b_blocknr, pos, 
	    get_dc_child_size(B_N_CHILD(path[h-1],pos)), path[h]->b_blocknr);
	fsck_log (" is not equal to the (blocksize (4096) - free space (%d) - "
	    "header size (%u))", 
	    get_blkh_free_space((struct block_head *)path[h]->b_data), BLKH_SIZE);
	
	if (fsck_mode (fs) == FSCK_FIX_FIXABLE) {
	    set_dc_child_size (B_N_CHILD(path[h-1],pos), path[h]->b_size -
	    		get_blkh_free_space ((struct block_head *)path[h]->b_data) - BLKH_SIZE);
	    fsck_log (" - corrected to (%lu)\n", get_dc_child_size (B_N_CHILD(path[h-1],pos)));
	    mark_buffer_dirty (path[h-1]);
	} else {
	    one_more_corruption (fs, FIXABLE);
	    fsck_log ("\n");
	    return 1;
	}
    }

    return 0;
}

static void before_check_fs_tree (reiserfs_filsys_t * fs) {
    init_control_bitmap (fs);

    source_bitmap = reiserfs_create_bitmap (get_sb_block_count (fs->fs_ondisk_sb));
    reiserfs_bitmap_copy (source_bitmap, fs->fs_bitmap2);

    proper_id_map (fs) = id_map_init();
}

static void after_check_fs_tree (reiserfs_filsys_t * fs) {
    if (fsck_mode(fs) == FSCK_FIX_FIXABLE) {
        reiserfs_flush_to_ondisk_bitmap (fs->fs_bitmap2, fs);
        reiserfs_flush (fs);
        fs->fs_dirt = 1;
	reiserfs_bitmap_delta (source_bitmap, control_bitmap);
	fsck_deallocate_bitmap(fs) = source_bitmap;
    } else 
	reiserfs_delete_bitmap (source_bitmap);
    
    reiserfs_delete_bitmap (control_bitmap);
    flush_buffers (fs->fs_dev);
}

/* pass internal tree of filesystem */
void check_fs_tree (reiserfs_filsys_t * fs)
{
    before_check_fs_tree (fs);
    
    fsck_progress ("Checking internal tree..");
    pass_through_tree (fs, bad_node, bad_path, fsck_mode(fs) == FSCK_AUTO ? 2 : -1);
    /* internal tree is correct (including all objects have correct
       sequences of items) */
    fsck_progress ("finished\n");
    
    /* compare created bitmap with the original */
    if (fsck_mode(fs) == FSCK_AUTO) {
	if (auto_handle_bitmaps(fs)) {
	    fprintf(stderr, "The on-disk bitmap looks corrupted.");
	    one_more_corruption(fs, FIXABLE);
	}
	id_map_free(proper_id_map(fs));
    } else
	handle_bitmaps (fs);
    
    after_check_fs_tree (fs);
}

static int clean_attributes_handler (reiserfs_filsys_t * fs, struct buffer_head ** path, int h) {
    struct buffer_head * bh = path[h];
    int i;

    if (B_LEVEL (bh) != h_to_level (fs, h)) {
       	reiserfs_panic ("The node (%lu) with wrong level (%d) found in the tree, (%d) expected\n",
		  bh->b_blocknr, B_LEVEL (bh), h_to_level (fs, h));
    }

    if (!is_leaf_node (bh))
        return 0;

    for (i = 0; i < B_NR_ITEMS (bh); i ++) {
        if (is_stat_data_ih (B_N_PITEM_HEAD (bh, i)) &&
            get_ih_item_len (B_N_PITEM_HEAD (bh, i)) == SD_SIZE) {
	    set_sd_v2_sd_attrs((struct stat_data *)B_N_PITEM(bh, i), 0);
	    mark_buffer_dirty (bh);
	}
    }

    return 0;
}

void do_clean_attributes (reiserfs_filsys_t * fs) {
    pass_through_tree (fs, clean_attributes_handler, NULL, -1);
    set_sb_v2_flag (fs->fs_ondisk_sb, reiserfs_attrs_cleared);
    mark_buffer_dirty (fs->fs_super_bh);
}