blob: 309724dba8b7dcbaa2c1f8620ecf9d6fb47efcfb [file] [log] [blame]
/*
* 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) + 1)
#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;
__le32 *sb_objectid_map;
size = reiserfs_super_block_size(fs->fs_ondisk_sb);
sb_objectid_map = (__le32 *) ((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;
__le32 * sb_objectid_map;
sb_size = reiserfs_super_block_size (fs->fs_ondisk_sb);
sb_objectid_map = (__le32 *)((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;
}
*/