node_formats.c

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

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

#include "includes.h"

int leaf_count_ih(char * buf, int blocksize) {
    struct item_head * ih;
    int prev_location;
    int nr;

    /* look at the table of item head */
    prev_location = blocksize;
    ih = (struct item_head *)(buf + BLKH_SIZE);
    nr = 0;
    while (1) {
	if (get_ih_location (ih) + get_ih_item_len (ih) != prev_location)
	    break;
	if (get_ih_location (ih) < IH_SIZE * (nr + 1) + BLKH_SIZE)
	    break;
	if (get_ih_item_len (ih) > MAX_ITEM_LEN (blocksize))
	    break;
	prev_location = get_ih_location (ih);
	ih ++;
	nr ++;
    }
    
    return nr;
}

int leaf_free_space_estimate(char * buf, int blocksize) {
    struct block_head * blkh;
    struct item_head * ih;
    int nr;
    
    blkh = (struct block_head *)buf;
    nr = get_blkh_nr_items(blkh);    
    ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1;
    
    return (nr ? get_ih_location (ih) : blocksize) - BLKH_SIZE - IH_SIZE * nr;
}

static int leaf_blkh_correct(char * buf, int blocksize) {
    struct block_head * blkh;
    unsigned int nr;

    blkh = (struct block_head *)buf;
    if (!is_leaf_block_head (buf))
	return 0;

    nr = get_blkh_nr_items(blkh);
    if (nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN)))
	/* item number is too big or too small */
	return 0;

    return leaf_free_space_estimate(buf, blocksize) == get_blkh_free_space (blkh);
}

int is_a_leaf(char * buf, int blocksize) {
    struct block_head * blkh;
    int counted;
    
    blkh = (struct block_head *)buf;
    if (!is_leaf_block_head (buf))
	return 0;

    counted = leaf_count_ih(buf, blocksize);
    
    /* if leaf block header is ok, check item count also. */
    if (leaf_blkh_correct(buf, blocksize))
	return counted >= get_blkh_nr_items (blkh) ? THE_LEAF : HAS_IH_ARRAY;
    
    /* leaf block header is corrupted, it is ih_array if some items were detected.*/
    return counted ? HAS_IH_ARRAY : 0;
}

int leaf_item_number_estimate(struct buffer_head * bh) {
    struct block_head * blkh;
    int nr;
    
    nr = leaf_count_ih(bh->b_data, bh->b_size);
    blkh = (struct block_head *)bh->b_data;

    return nr >= get_blkh_nr_items (blkh) ? get_blkh_nr_items (blkh) : nr;
}

#if 0
/* this only checks block header and item head array (ih_location-s
   and ih_item_len-s). Item internals are not checked */
int does_node_look_like_a_leaf (char * buf, int blocksize)
{
    struct block_head * blkh;
    struct item_head * ih;
    int used_space;
    int prev_location;
    int i;
    int nr;

    blkh = (struct block_head *)buf;
    if (!is_leaf_block_head (buf))
	return 0;

    nr = get_blkh_nr_items (blkh);
    if (nr < 0 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN)))
	/* item number is too big or too small */
	return 0;

    ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1;
    used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - (nr ? get_ih_location (ih) : blocksize));

    if (used_space != blocksize - get_blkh_free_space (blkh))
	/* free space does not match to calculated amount of use space */
	return 0;

    // FIXME: it is_leaf will hit performance too much - we may have
    // return 1 here

    /* check tables of item heads */
    ih = (struct item_head *)(buf + BLKH_SIZE);
    prev_location = blocksize;
    for (i = 0; i < nr; i ++, ih ++) {
	/* items of zero length are allowed - they may exist for short time
           during balancing */
	if (get_ih_location (ih) > blocksize || get_ih_location (ih) < IH_SIZE * nr)
	    return 0;
	if (/*ih_item_len (ih) < 1 ||*/ get_ih_item_len (ih) > MAX_ITEM_LEN (blocksize))
	    return 0;
	if (prev_location - get_ih_location (ih) != get_ih_item_len (ih))
	    return 0;
	prev_location = get_ih_location (ih);
    }

    // one may imagine much more checks
    return 1;
}

/* check ih_item_len and ih_location. Should be useful when block head is
   corrupted */
static int does_node_have_ih_array (char * buf, int blocksize)
{
    struct item_head * ih;
    int prev_location;
    int nr;

    /* look at the table of item head */
    prev_location = blocksize;
    ih = (struct item_head *)(buf + BLKH_SIZE);
    nr = 0;
    while (1) {
	if (get_ih_location (ih) + get_ih_item_len (ih) != prev_location)
	    break;

	prev_location = get_ih_location (ih);
	ih ++;
	nr ++;
    }
    if (nr < 2)
	return 0;
    return nr;
}
#endif

/* returns 1 if buf looks like an internal node, 0 otherwise */
static int is_correct_internal (char * buf, int blocksize)
{
    struct block_head * blkh;
    unsigned int nr;
    int used_space;

    blkh = (struct block_head *)buf;

    if (!is_internal_block_head (buf))
	return 0;
    
    nr = get_blkh_nr_items (blkh);
    if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE))
	/* for internal which is not root we might check min number of keys */
	return 0;

    used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1);
    if (used_space != blocksize - get_blkh_free_space (blkh))
	return 0;

    // one may imagine much more checks
    return 1;
}


// make sure that bh contains formatted node of reiserfs tree of
// 'level'-th level
int is_tree_node (struct buffer_head * bh, int level)
{
    if (B_LEVEL (bh) != level)
	return 0;
    if (is_leaf_node (bh))
	return is_a_leaf(bh->b_data, bh->b_size);

    return is_correct_internal (bh->b_data, bh->b_size);
}


static int is_desc_block (char * buf, unsigned long buf_size)
{
    struct reiserfs_journal_desc *desc = (struct reiserfs_journal_desc *)buf;
    if (!memcmp(buf + buf_size - 12, JOURNAL_DESC_MAGIC, 8) &&
	le32_to_cpu (desc->j2_len) > 0)
	return 1;
    return 0;
}


int is_reiserfs_3_5_magic_string (struct reiserfs_super_block * rs)
{
    return (!strncmp (rs->s_v1.s_magic, REISERFS_3_5_SUPER_MAGIC_STRING, 
		      strlen ( REISERFS_3_5_SUPER_MAGIC_STRING)));
}


int is_reiserfs_3_6_magic_string (struct reiserfs_super_block * rs)
{
    return (!strncmp (rs->s_v1.s_magic, REISERFS_3_6_SUPER_MAGIC_STRING, 
		      strlen ( REISERFS_3_6_SUPER_MAGIC_STRING)));
}


int is_reiserfs_jr_magic_string (struct reiserfs_super_block * rs)
{
    return (!strncmp (rs->s_v1.s_magic, REISERFS_JR_SUPER_MAGIC_STRING, 
		      strlen ( REISERFS_JR_SUPER_MAGIC_STRING)));
}


int is_any_reiserfs_magic_string (struct reiserfs_super_block * rs)
{
    if (is_reiserfs_3_5_magic_string (rs) ||
	is_reiserfs_3_6_magic_string (rs) ||
	is_reiserfs_jr_magic_string (rs))
	return 1;
    return 0;
}


int get_reiserfs_format (struct reiserfs_super_block * sb)
{
    /* after conversion to 3.6 format we change magic correctly, 
       but do not change sb_format. When we create non-standard journal 
       field format in sb get adjusted correctly. Thereby, for standard 
       journal we should rely on magic and for non-standard - on format */
    if (is_reiserfs_3_5_magic_string (sb) ||
	(is_reiserfs_jr_magic_string (sb) && 
	 get_sb_version (sb) == REISERFS_FORMAT_3_5))
	return REISERFS_FORMAT_3_5;

    if (is_reiserfs_3_6_magic_string (sb) ||
	(is_reiserfs_jr_magic_string (sb) &&
	 get_sb_version (sb) == REISERFS_FORMAT_3_6))
	return REISERFS_FORMAT_3_6;

    return REISERFS_FORMAT_UNKNOWN;
}



int reiserfs_super_block_size (struct reiserfs_super_block * sb)
{
    switch (get_reiserfs_format (sb)) {
    case REISERFS_FORMAT_3_5:
	return SB_SIZE_V1;
    case REISERFS_FORMAT_3_6:
	return SB_SIZE;
    }
    reiserfs_panic ("Unknown format found");
    return 0;
}

/* this one had signature in different place of the super_block
   structure */
int is_prejournaled_reiserfs (struct reiserfs_super_block * rs)
{
    return (!strncmp((char*)rs + REISERFS_SUPER_MAGIC_STRING_OFFSET_NJ,
		     REISERFS_3_5_SUPER_MAGIC_STRING,
		     strlen(REISERFS_3_5_SUPER_MAGIC_STRING)));
}

int does_look_like_super_block (struct reiserfs_super_block * sb) {
    if (!is_any_reiserfs_magic_string (sb))
    	return 0;
    
    if (!is_blocksize_correct(get_sb_block_size (sb)))
	return 0;
	
    return 1;
}


/* returns code of reiserfs metadata block (leaf, internal, super
   block, journal descriptor), unformatted */
int who_is_this (char * buf, int blocksize)
{
    int res;
    
    /* super block? */
    if (does_look_like_super_block ((void *)buf))
	return THE_SUPER;

    if ((res = is_a_leaf(buf, blocksize)))
	/* if block head and item head array seem matching (node level, free
           space, item number, item locations and length), then it is THE_LEAF,
	  otherwise, it is HAS_IH_ARRAY */
	return res;

    if (is_correct_internal (buf, blocksize))
	return THE_INTERNAL;


    /* journal descriptor block? */
    if (is_desc_block (buf, blocksize))
	return THE_JDESC;

    /* contents of buf does not look like reiserfs metadata. Bitmaps
       are possible here */
    return THE_UNKNOWN;
}


char * which_block (int code)
{
    static char * leaf = "leaf";
    static char * broken_leaf = "broken leaf";
    static char * internal = "internal";
    static char * other = "unknown";

    switch (code) {
    case THE_LEAF:
	return leaf;
    case HAS_IH_ARRAY:
	return broken_leaf;
    case THE_INTERNAL:
	return internal;
    }
    return other;
}


/** */
int block_of_journal (reiserfs_filsys_t * fs, unsigned long block) {
    if (!is_reiserfs_jr_magic_string (fs->fs_ondisk_sb)) {
	/* standard journal */
	if (block >= get_journal_start_must (fs) &&
	    block <= get_journal_start_must (fs) + get_jp_journal_size (sb_jp (fs->fs_ondisk_sb)))
	    return 1;
	return 0;
    }
    
    if (get_sb_reserved_for_journal (fs->fs_ondisk_sb))
	/* there is space reserved for the journal on the host device */
	if (block >= get_journal_start_must (fs) && 
	    block < get_journal_start_must (fs) + get_sb_reserved_for_journal (fs->fs_ondisk_sb))
	    return 1;

    return 0;
}


int block_of_bitmap (reiserfs_filsys_t * fs, unsigned long block)
{
    if (spread_bitmaps (fs)) {
	if (!(block % (fs->fs_blocksize * 8)))
	    /* bitmap block */
	    return 1;
	return (block == (REISERFS_DISK_OFFSET_IN_BYTES / fs->fs_blocksize + 1)) ;
    } else {
	/* bitmap in */
	return (block > 2ul && block < 3ul + get_sb_bmap_nr(fs->fs_ondisk_sb)) ? 1 : 0;
    }
    return 0;
}


/* check whether 'block' can be pointed to by an indirect item */
int not_data_block (reiserfs_filsys_t * fs, unsigned long block)
{
    if (block_of_bitmap (fs, block))
	/* it is one of bitmap blocks */
	return 1;

    if (block_of_journal (fs, block))
	/* block of journal area */
	return 1;

    if (block <= fs->fs_super_bh->b_blocknr)
	/* either super block or a block from skipped area at the
           beginning of filesystem */
	return 1;

    return 0;
}


/* check whether 'block' can be logged */
int not_journalable (reiserfs_filsys_t * fs, unsigned long block)
{   
    /* we should not update SB with journal copy during fsck */
    if (block < fs->fs_super_bh->b_blocknr)
	return 1;

    if (block_of_journal (fs, block))
	return 1;

    if (block >= get_sb_block_count (fs->fs_ondisk_sb))
	return 1;

    return 0;
}

// in reiserfs version 0 (undistributed bitmap)
// FIXME: what if number of bitmaps is 15?
unsigned int get_journal_old_start_must (reiserfs_filsys_t * fs) {
    return (REISERFS_OLD_DISK_OFFSET_IN_BYTES / fs->fs_blocksize) + 1 + 
	get_sb_bmap_nr (fs->fs_ondisk_sb);
}

unsigned int get_journal_new_start_must (reiserfs_filsys_t * fs)
{
    return (REISERFS_DISK_OFFSET_IN_BYTES / fs->fs_blocksize) + 2;
}

unsigned int get_journal_start_must(reiserfs_filsys_t * fs) {
    if (is_old_sb_location(fs->fs_super_bh->b_blocknr, fs->fs_blocksize))
    	return get_journal_old_start_must (fs);

    return get_journal_new_start_must(fs);
}

__u32 get_bytes_number (struct item_head * ih, int blocksize) {