uobjectid.c

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

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

#include "fsck.h"


/* when --check fsck builds a map of objectids of files it finds in the tree
   when --rebuild-tree - fsck builds map of objectids it inserts into tree */

#define ALLOC_SIZE			1024
#define MAX_ID				(~(__u32)0)

/* 2 bytes for the counter */
#define BM_SIZE				(ALLOC_SIZE - sizeof(__u16))
#define BM_INTERVAL			(BM_SIZE * 8)
#define INDEX_COUNT			(MAX_ID / BM_INTERVAL)

#define id_map_interval(map, id)	(map->index + (id / BM_INTERVAL))

#define id_map_local_count(interval)	(interval + BM_SIZE)

/*
typedef struct sb_id_map {
    __u32 * m_begin;
    __u32 m_size, m_used_slot_count;
} sb_id_map_t;
*/

id_map_t *id_map_init() {
    id_map_t *map;
    __u32 i;
 
    map = getmem(sizeof(id_map_t));
    map->index = mem_alloc(INDEX_COUNT * sizeof(void *));

    for (i = 0; i < INDEX_COUNT; i++) {
	if (map->index[i] != (void *)0)
	    map->index[i] = (void *)0;
    }

    id_map_mark(map, 0);
    id_map_mark(map, 1);

    /* id == 0 should not be there, just for convinient usage */
    map->count--;
    
    return map;
}

void id_map_free(id_map_t *map) {
    __u32 i;
 
    for (i = 0; i < INDEX_COUNT; i++) {
	if (map->index[i] != (void *)0 && map->index[i] != (void *)1)
	    freemem(map->index[i]);
    }
    
    freemem(map->index);
    freemem(map);
}

int id_map_test(id_map_t *map, __u32 id) {
    void **interval = id_map_interval(map, id);

    if (*interval == (void *)0)
	return 0;
    
    if (*interval == (void *)1)
	return 1;
    
    return misc_test_bit(id % BM_INTERVAL, *interval);
}

int id_map_mark(id_map_t *map, __u32 id) {
    void **interval = id_map_interval(map, id);

    if (*interval == (void *)0)
	*interval = getmem(ALLOC_SIZE);

    if (*interval == (void *)1)
	return 1;

    if (misc_test_bit(id % BM_INTERVAL, *interval))
	return 1;
	
    misc_set_bit(id % BM_INTERVAL, *interval);
    
    (*(__u16 *)id_map_local_count(*interval))++;
    map->count++;

    if ((*(__u16 *)id_map_local_count(*interval)) == BM_INTERVAL) {
	/* Dealloc fully used bitmap */
	freemem(*interval);
	*interval = (void *)1;
    }

    if (map->last_used < (id / BM_INTERVAL))
	map->last_used = id / BM_INTERVAL;
    
    return 0;
}

/* call this for proper_id_map only!! */
__u32 id_map_alloc(id_map_t *map) {
    __u32 i, zero_count;
    __u32 id = 0, first = ~(__u32)0;

    for (i = 0, zero_count = 0; zero_count < 10 && i < INDEX_COUNT - 1; i++) {
	if (map->index[i] == (void *)0) {
	    if (zero_count == 0)
		first = i;
	    
	    zero_count++;
	} else if (map->index[i] != (void *)1)
	    break;
    }

    if (map->index[i] != (void *)1 && map->index[i] != (void *)0) {
	id = misc_find_first_zero_bit(map->index[i], BM_INTERVAL);
	if (id >= BM_INTERVAL)
	    die ("Id is out of interval size, interval looks corrupted.");
	
	id += i * BM_INTERVAL;
    } else if (first != ~(__u32)0) {
	id = first * BM_INTERVAL;
	if (id == 0) 
	    id = 2;
    } else 
	die ("%s: No more free objectid is available.", __FUNCTION__);

    id_map_mark(map, id);

    return id;
}

/* this could be used if some more sofisticated flushing will be needed. */
/*
static void sb_id_map_pack(sb_id_map_t *map) {
    map->m_begin[1] = map->m_begin[map->m_used_slot_count - 1];
    memset(map->m_begin + 2, 0, map->m_used_slot_count - 2);
    map->m_used_slot_count = 2;
}*/

static __u32 id_map_next_bound(id_map_t *map, __u32 start) {
    __u32 index = start / BM_INTERVAL;
    __u32 offset = start % BM_INTERVAL;
    int look_for;
    
    if (map->index[index] == (void *)0)
	look_for = 1;
    else if (map->index[index] == (void *)1)
	look_for = 0;
    else 
	look_for = !misc_test_bit(offset, map->index[index]);

    offset++;

start_again:
    
    if (look_for) {	
	while (index < INDEX_COUNT && map->index[index] == (void *)0)
	    index++;
	
	if (index == INDEX_COUNT)
	    return 0;
	
	if (map->index[index] == (void *)1)
	    return index * BM_INTERVAL;
	
	offset = misc_find_next_set_bit(map->index[index], BM_INTERVAL, offset);

	if (offset >= BM_INTERVAL) {
	    offset = 0;
	    index++;
	    goto start_again;
	}
	
	return index * BM_INTERVAL + offset;
    } else {
	while (index < INDEX_COUNT && map->index[index] == (void *)1)
	    index++;
	
	if (index == INDEX_COUNT)
	    return 0;
	
	if (map->index[index] == (void *)0)
	    return index * BM_INTERVAL;

	offset = misc_find_next_zero_bit(map->index[index], BM_INTERVAL, offset);
	
	if (offset >= BM_INTERVAL) {
	    offset = 0;
	    index++;
	    goto start_again;
	}
	
	return index * BM_INTERVAL + offset;
    }
}

void id_map_flush(struct id_map * map, reiserfs_filsys_t * fs) {
    int size, max, i;
    __u32 id, prev_id;
    __u32 * sb_objectid_map;

    size = reiserfs_super_block_size (fs->fs_ondisk_sb);
    sb_objectid_map = (__u32 *)((char *)(fs->fs_ondisk_sb) + size);

    max = ((fs->fs_blocksize - size) >> 3 << 1);
    set_sb_oid_maxsize (fs->fs_ondisk_sb, max);
    
    id = 1;
    sb_objectid_map[0] = cpu_to_le32(1);

    for (i = 1; i < max - 1; i++) {
	id = id_map_next_bound(map, id);
	sb_objectid_map[i] = cpu_to_le32(id);
	if (id == 0) {
	    if (i % 2)
		die ("%s: Used interval is not closed on flushing.", __FUNCTION__);
	    break;
	}
    }

    if (map->index[map->last_used] == (void *)0)
	die ("Object id map looks corrupted - last used interval cannot be zeroed.");
    
    i++;
    
    if (i == max) {
	if (id == 0)
	    die ("Objectid interval does not contain any set bit what is expected.");
	
	if (map->index[map->last_used] == (void *)1) {
	    prev_id = BM_INTERVAL - 1;
	} else {	    
	    prev_id = ~(__u32)0;
	    
	    if (id < map->last_used * BM_INTERVAL)
		id = 0;
	    else 
		id %= BM_INTERVAL;
	    
	    if (misc_test_bit(id, map->index[map->last_used]))
		prev_id = id;
	    
	    while ((id = misc_find_next_set_bit(map->index[map->last_used], 
		BM_INTERVAL, (id + 1))) != BM_INTERVAL) 
	    {
		prev_id = id;
	    }

	    if (prev_id == ~(__u32)0)
		die ("Objectid interval does not contain any set bit what is expected.");

	    prev_id++;
	}
	
	sb_objectid_map[max - 1] = cpu_to_le32(prev_id + map->last_used * BM_INTERVAL);
    } else { 
	i--;
	memset(sb_objectid_map + i, 0, (max - i) * sizeof (__u32));
    }

    set_sb_oid_cursize (fs->fs_ondisk_sb, i);
}

/* FIXME: these 3 methods must be implemented also.

void fetch_objectid_map (struct id_map * map, reiserfs_filsys_t * fs)
{
    int sb_size;
    __u32 * sb_objectid_map;

    sb_size = reiserfs_super_block_size (fs->fs_ondisk_sb);
    sb_objectid_map = (__u32 *)((char *)(fs->fs_ondisk_sb) + sb_size);

    if (map->m_page_count != 1)
	die ("fetch_objectid_map: can not fetch long map");
    
    make_id_space(map, 0);
    memcpy (map->m_begin, sb_objectid_map, get_sb_oid_cursize (fs->fs_ondisk_sb) * sizeof (__u32));
    map->m_used_slot_count = get_sb_oid_cursize (fs->fs_ondisk_sb);
}

#define OBJMAP_START_MAGIC 375331
#define OBJMAP_END_MAGIC 7700472

void reiserfs_objectid_map_save (FILE * fp, struct id_map * id_map)
{
    __u32 v;
    int i;

    v = OBJMAP_START_MAGIC;
    fwrite (&v, 4, 1, fp);

    v = id_map->m_used_slot_count;
    fwrite (&v, 4, 1, fp);

    for (i = 0; i < id_map->m_page_count - 1; i++) {
	fwrite ((char *)id_map->m_begin + MAP_SIZE * i, 4, 1, fp);
    }

    for (i = 0; i < id_map->m_used_slot_count * sizeof(__u32) - (id_map->m_page_count - 1) * MAP_SIZE; i++) {
	fwrite ((char *)id_map->m_begin + MAP_SIZE * (id_map->m_page_count - 1) + i, 4, 1, fp);
    }

    v = OBJMAP_END_MAGIC;
    fwrite (&v, 4, 1, fp);
}

struct id_map * reiserfs_objectid_map_load (FILE * fp)
{
    __u32 v;
    int i;
    struct id_map * id_map;

    fread (&v, 4, 1, fp);
    if (v != OBJMAP_START_MAGIC) {
	reiserfs_warning (stderr, "reiserfs_objectid_map_load: no objectid map begin magic found");
	return 0;
    }
	
    // read bit size of objectid map 
    fread (&v, 4, 1, fp);

    id_map = init_id_map (MAP_NOT_PACKED);

    id_map->m_used_slot_count = v;
    id_map->m_page_count = v / MAP_SIZE + 1;

    id_map->m_begin = expandmem (id_map->m_begin, 0, id_map->m_page_count * MAP_SIZE);

    for (i = 0; i < id_map->m_page_count - 1; i++) {
	fread ((char *)id_map->m_begin + MAP_SIZE * i, 4, 1, fp);
    }

    for (i = 0; i < id_map->m_used_slot_count * sizeof(__u32) - (id_map->m_page_count - 1) * MAP_SIZE; i++) {
	fread ((char *)id_map->m_begin + MAP_SIZE * (id_map->m_page_count - 1) + i, 4, 1, fp);
    }

    fread (&v, 4, 1, fp);

    if (v != OBJMAP_END_MAGIC) {
	reiserfs_warning (stderr, "reiserfs_objectid_map_load: no objectid map end magic found");
	return 0;
    }

    fflush (stderr);
    return id_map;
}
*/