scan.c

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

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

#include "debugreiserfs.h"
#include <regex.h>
#include <obstack.h>
#include <search.h>

#define obstack_chunk_alloc malloc
#define obstack_chunk_free free


/* -n pattern scans the area (on-disk bitmap, or all the device or extern
   bitmap) and looks for every name matching the pattern. All those names get
   stored in 'name_store' and are indexed by name (name_index) and by a key
   they point to (key_index) */

struct obstack name_store;
struct obstack item_store;

int saved_names;
int saved_items;
int skipped_names;
void * key_index;
void * name_index;

regex_t pattern;

struct saved_name {
    unsigned int dirid; /* pointed object */
    unsigned int objectid;
    struct saved_name * first_name; /* pointer to name which points to the
                                       same object and contains list of file
                                       items */

    unsigned int parent_dirid; /* parent directory */
    unsigned int parent_objectid;
    unsigned long block; /* where we saw the name for the first time */
    unsigned short count; /* how many times the name appeared */

    void * items;
    struct saved_name * name_next; /* list of identical names */

    unsigned short name_len;
    char name[1];
};



/* attach item to every name in the list */
static void store_item (struct saved_name * name, struct buffer_head * bh,
			struct item_head * ih, int pos)
{
    struct saved_item * new;
    void * vp;
    struct saved_item * item_in;

    new = obstack_alloc (&item_store, sizeof (struct saved_item));
    new->si_ih = *ih;
    new->si_block = bh->b_blocknr;
    new->si_item_num = ih - B_N_PITEM_HEAD (bh, 0);
    new->si_next = 0;
    new->si_entry_pos = pos;
    
    vp = tfind (new, &name->items, comp_keys);
    if (vp) {
	item_in = *(void **)vp;
	/* add item to the end of list of items having this key */
	while (1) {
	    if (!item_in->si_next) {
		item_in->si_next = new;
		break;
	    }
	    item_in = item_in->si_next;
	}
    } else
	tsearch (new, &name->items, comp_keys);

    saved_items ++;
}


static int comp_names (const void * p1, const void * p2)
{
    struct saved_name * name1, * name2;

    name1 = (struct saved_name *)p1;
    name2 = (struct saved_name *)p2;

    return strcmp (name1->name, name2->name);
}


static int comp_pointed (const void * p1, const void * p2)
{
    struct saved_name * name1, * name2;

    name1 = (struct saved_name *)p1;
    name2 = (struct saved_name *)p2;

    return comp_short_keys (&name1->dirid, &name2->dirid);
}


/* we consider name found only if it points to the same object and from the
   same directory */
static int name_found (struct saved_name * name, struct saved_name ** name_in)
{
    void * vp;
    struct saved_name * cur;

    vp = tfind (name, &name_index, comp_names);
    if (!vp) {
	*name_in = 0;
	return 0;
    }

    *name_in =  *(void **)vp;

    /* check every name in the list */
    cur = *name_in;
    while (cur) {
	if (!not_of_one_file (&name->dirid, &cur->dirid) &&
	    !not_of_one_file (&name->parent_dirid, &cur->parent_dirid)) 
	{
	    cur->count ++;
	    *name_in = cur;
	    return 1;
	}
	cur = cur->name_next;
    }
    
    return 0;
}


/* add key name is pointing to to the index of keys. If there was already name
   pointing to this key - add pointer to that name */
static void add_key (struct saved_name * name)
{
    void * vp;
  
    vp = tfind (name, &key_index, comp_pointed);
    if (vp) {
	/* */
	name->first_name = *(void **)vp;
    } else {
	tsearch (name, &key_index, comp_pointed);
    }
}


static void add_name (struct saved_name * name, struct saved_name * name_in)
{
    if (name_in) {
	/* add name to the end of list of identical names */
	while (1) {
	    if (!name_in->name_next) {
		name_in->name_next = name;
		break;
	    }
	    name_in = name_in->name_next;
	}
    } else {
	/* add name into name index */
	tsearch (name, &name_index, comp_names);
    }
}


/* take each name matching to a given pattern, */
static void scan_for_name (struct buffer_head * bh)
{
    int i, j, i_num;
    struct item_head * ih;
    struct reiserfs_de_head * deh;
    int namelen;
    char * name;
    struct saved_name * new, *name_in;
    char ch;
    int retval;
    int min_entry_size = 1;
    int ih_entry_count = 0;

    ih = B_N_PITEM_HEAD (bh, 0);
    i_num = leaf_item_number_estimate(bh);
    for (i = 0; i < i_num; i ++, ih ++) {
	if (!is_direntry_ih (ih))
	    continue;
	if (is_it_bad_item (fs, ih, B_I_PITEM (bh, ih), 0, 1))
	    continue;

	deh = B_I_DEH (bh, ih);
	
        if ( (get_ih_entry_count (ih) > (get_ih_item_len(ih) / (DEH_SIZE + min_entry_size))) ||
            (get_ih_entry_count (ih) == 0))
            ih_entry_count = get_ih_item_len(ih) / (DEH_SIZE + min_entry_size);
        else 
            ih_entry_count = get_ih_entry_count (ih);
	
	for (j = 0; j < ih_entry_count; j ++, deh ++) {
	    name = name_in_entry (deh, j);
	    namelen = name_in_entry_length (ih, deh, j);
	    ch = name[namelen];
	    name[namelen] = 0;
	    retval = regexec (&pattern, name, 0, NULL, 0);
	    name[namelen] = ch;	    
	    if (retval != 0)
		continue;

	    /* name matching given pattern found */

	    new = obstack_alloc (&name_store, sizeof (struct saved_name) + namelen);

	    /* pointed object */
	    new->dirid = get_deh_dirid (deh);
	    new->objectid = get_deh_objectid (deh);

	    /* pointer to first name which points the same key */
	    new->first_name = 0;

	    /* where this name is from */
	    new->parent_dirid = get_key_dirid (&ih->ih_key);
	    new->parent_objectid = get_key_objectid (&ih->ih_key);
	    new->block = bh->b_blocknr;

	    new->count = 1;
	    new->items = 0;

	    /* name */
	    new->name_len = namelen;
	    memcpy (new->name, name, namelen);
	    new->name [namelen] = 0;
	    new->name_next = 0;

	    /*
	    reiserfs_warning (stdout, "\n(%K):%s-->(%K) - ", &new->parent_dirid,
			      new->name, &new->dirid);
	    */
	    if (name_found (new, &name_in)) {
		/* there was already exactly this name */
		obstack_free (&name_store, new);
		continue;
	    }

	    saved_names ++;
	    add_name (new, name_in);		
	    add_key (new);
	} /* for each entry */
    } /* for each item */

    return;
}

static struct saved_name *scan_for_key(struct key *key) {
	char *name;
	struct saved_name * new, *name_in;

	asprintf (&name, "%u_%u", get_key_dirid (key), get_key_objectid (key));
	new = obstack_alloc (&name_store, sizeof (struct saved_name) + strlen(name));

	/* pointed object */
	new->dirid = get_key_dirid (key);
	new->objectid = get_key_objectid (key);

	/* pointer to first name which points the same key */
	new->first_name = 0;

	/* where this name is from */

	new->parent_dirid = 0;
	new->parent_objectid = 0;
	new->block = 0;
	new->count = 1;
	new->items = 0;

	/* name */
	new->name_len = strlen(name);
	memcpy (new->name, name, new->name_len);
	new->name [new->name_len] = 0;
	new->name_next = 0;

	free(name);
	
	if (name_found (new, &name_in)) {
		/* there was already exactly this name */
		obstack_free (&name_store, new);
		return name_in;
	}

	saved_names ++;
	add_name (new, name_in);

	return new;
}

static int comp_token_key(struct buffer_head *bh, struct item_head *ih, struct key *key) {
    struct reiserfs_de_head * deh;
    int j, ih_entry_count = 0;
    int min_entry_size = 1;
    
    if ((get_key_dirid(&ih->ih_key) == get_key_dirid(key) || 
	 get_key_dirid(key) == ~(__u32)0) &&
	(get_key_objectid(&ih->ih_key) == get_key_objectid(key) || 
	 get_key_objectid(key) == ~(__u32)0))
	return -1;

    if (!is_direntry_ih (ih))
	return 0;
	
    deh = B_I_DEH (bh, ih);

    if ( (get_ih_entry_count (ih) > (get_ih_item_len(ih) / (DEH_SIZE + min_entry_size))) ||
	 (get_ih_entry_count (ih) == 0))
	 ih_entry_count = get_ih_item_len(ih) / (DEH_SIZE + min_entry_size);
    else 
	 ih_entry_count = get_ih_entry_count (ih);

	
    for (j = 0; j < ih_entry_count; j ++, deh ++) {
	if ((get_deh_dirid (deh) == get_key_dirid (key) || (int)get_key_dirid (key) == -1) &&
	    (get_deh_objectid (deh) == get_key_objectid (key) || (int)get_key_objectid (key) == -1)) 
	{
	    return j;
	}
    }

    return 0;
}

/* take every item, look for its key in the key index, if it is found - store
   item in the sorted list of items of a file */
static void scan_items (struct buffer_head * bh, struct key *key) {
    int i, i_num, pos;
    struct item_head * ih;
    struct saved_name * name_in_store;
    void * res;


    ih = B_N_PITEM_HEAD (bh, 0);
    i_num = leaf_item_number_estimate(bh);
    for (i = 0; i < i_num; i ++, ih ++) {
	if (key) {
	    if (!(pos = comp_token_key(bh, ih, key)))
		    continue;

	    name_in_store = scan_for_key(&ih->ih_key);
	} else {
	    if (!(res = tfind (&ih->ih_key, &key_index, comp_pointed)))
		continue;

	    /* name pointing to this key found */
	    name_in_store = *(struct saved_name **)res;
	    pos = -1;
	}

	store_item (name_in_store, bh, ih, pos);
    }
}


/* FIXME: does not work for long files */
struct version {
    int flag; /* direct or indirect */
    int len;
    __u32 from;
    int count;
    void * data;
};


struct tail {
    __u32 offset;
    int len;
    char * data;
};


struct file_map {
    int head_len; /* number of unfm pointers */
    void * head;

    int tail_nr; /* number of tails found */
    struct tail * tails;
    
    int version_nr;
    void * versions; /* list of range versions */
};


struct file_map map;


static int have_to_append (struct item_head * ih)
{
    loff_t off = get_offset (&ih->ih_key);

    if (is_indirect_ih (ih)) {
	if (map.head_len * fs->fs_blocksize + 1 <= off)
	    return 1;
	return 0;
    } else if (is_direct_ih (ih)) {
	int i;
	__u32 tail_start;
	
	tail_start = (off & ~(fs->fs_blocksize - 1)) + 1;

	// find correct tail first 
	for (i = 0; i < map.tail_nr; i ++) {
	    if (map.tails[i].offset == tail_start) {
		if (map.tails[i].offset + map.tails[i].len <= off)
		    return 1;
		return 0;
	    }
	}
	// there was no this tail yet 
	return 1;
    }
    return 0;
}


static void do_append (struct item_head * ih, void * data)
{
    int i;
    int padd;
    unsigned long long off = get_offset (&ih->ih_key);

    if (is_indirect_ih (ih)) {

	padd = (off - 1) / fs->fs_blocksize - map.head_len;
	map.head = realloc (map.head, (map.head_len + padd + I_UNFM_NUM (ih)) * 4);
	if (!map.head)
	    reiserfs_panic ("realloc failed");
	memset ((char *)map.head + map.head_len * 4, 0, padd * 4);
	memcpy ((char *)map.head + (map.head_len + padd) * 4, data,
		get_ih_item_len (ih));
	map.head_len += (padd + I_UNFM_NUM (ih));

    } else if (is_direct_ih (ih)) {
	unsigned int tail_start, skip;
	
	// find correct tail first 
	tail_start = (off & ~(fs->fs_blocksize - 1)) + 1;
	skip = (off - 1) & (fs->fs_blocksize - 1);
	for (i = 0; i < map.tail_nr; i ++) {
	    if (map.tails[i].offset == tail_start) {
		map.tails[i].data = realloc (map.tails[i].data,
					     off - tail_start + get_ih_item_len (ih));
		if (!map.tails[i].data)
		    reiserfs_panic ("realloc failed");
		padd = skip - map.tails[i].len;
		memset (map.tails[i].data + map.tails[i].len, 0, padd);
		memcpy (map.tails[i].data + map.tails[i].len + padd, data, get_ih_item_len (ih));
		map.tails[i].len += (padd + get_ih_item_len (ih));
		return;
	    }
	}
	// allocate memory for new tail 
	map.tails = realloc (map.tails, (map.tail_nr + 1) * sizeof (struct tail));
	if (!map.tails)
	    reiserfs_panic ("realloc failed");

	map.tails[map.tail_nr].offset = off;
	map.tails[map.tail_nr].len = skip + get_ih_item_len (ih);
	map.tails[map.tail_nr].data = malloc (map.tails[map.tail_nr].len);
	memset (map.tails[map.tail_nr].data, 0, skip);
	memcpy (map.tails[map.tail_nr].data + skip, data, get_ih_item_len (ih));
	map.tail_nr ++;		    
    }
}


// map contains 
static void do_overwrite (struct item_head * ih, void * data)
{
    unsigned long long off, skip;
    int to_compare, to_append;
    struct item_head tmp_ih;
    char * p;
    
    off = get_offset (&ih->ih_key);
    
    if (is_indirect_ih (ih)) {

	skip = (off - 1) / fs->fs_blocksize;
	to_compare = (map.head_len - skip > I_UNFM_NUM (ih)) ? 
	    I_UNFM_NUM (ih) : (map.head_len - skip);
	to_append = I_UNFM_NUM (ih) - to_compare;
	
	p = (char *)map.head + skip * 4;

	if (memcmp (p, data, to_compare * 4))
	    reiserfs_warning (stderr, "overwrite (indirect): %H contains different data\n", ih);

	if (to_append) {
	    tmp_ih = *ih;
	    set_ih_item_len (&tmp_ih, get_ih_item_len (ih) - to_compare * 4);
	    set_offset (key_format (&ih->ih_key), &tmp_ih.ih_key, off + to_compare * fs->fs_blocksize);
	    do_append (&tmp_ih, (char *)data + to_compare * 4);
	}

    } else if (is_direct_ih (ih)) {
	unsigned int tail_start;
	int i;

	// find correct tail first 
	tail_start = (off & ~(fs->fs_blocksize - 1)) + 1;
	for (i = 0; i < map.tail_nr; i ++) {
	    if (map.tails[i].offset == tail_start) {
		// ih is a part of this tail 
		skip = (off - 1) & (fs->fs_blocksize - 1);
		to_compare = (map.tails[i].len - skip > get_ih_item_len (ih) ? get_ih_item_len (ih) :
		    map.tails[i].len - skip);
		to_append = get_ih_item_len (ih) - to_compare;

		p = (char *)map.tails[i].data + skip;

		if (memcmp (p, data, to_compare))
		    reiserfs_warning (stderr, "overwrite (direct): %H contains different data\n", ih);
		
		if (to_append) {
		    tmp_ih = *ih;
		    set_ih_item_len (&tmp_ih, get_ih_item_len (ih) - to_compare);
		    set_offset (key_format (&ih->ih_key), &tmp_ih.ih_key, off + to_compare);
		    do_append (&tmp_ih, (char *)data + to_compare);
		}
		return;
	    }
	}
	reiserfs_panic ("no appropriate tail found");
    }
}


static void map_one_item (struct saved_item * item)
{
    struct buffer_head * bh;
    struct item_head * ih;
    void * data;