| /* |
| * relocate.c --- maintains the relocation table |
| * |
| * Copyright (C) 1996 Theodore Ts'o. This file may be redistributed |
| * under the terms of the GNU Public License. |
| */ |
| |
| #include <et/com_err.h> |
| |
| /* |
| * This routine creates a relocation table |
| */ |
| errcode_t ext2fs_create_relocation_table(__u32 max, int size, |
| ext2_relocate_table *ret); |
| { |
| ext2_relocate_table table; |
| |
| table = malloc(sizeof(struct ext2_relocate_struct)); |
| if (!table) |
| return -ENOMEM; |
| table->magic = 0; |
| table->count = 0; |
| table->size = size ? size : 30; |
| table->max = max; |
| table->entries = malloc(table->size * sizeof(ext2_relocate_entry)); |
| if (table->entries == 0) { |
| free(table); |
| return ENOMEM; |
| } |
| memset(table->entries, 0, table->size * sizeof(ext2_relocate_entry)); |
| *ret = table; |
| return 0; |
| } |
| |
| /* |
| * Free a relocation table |
| */ |
| void ext2fs_free_relocation_table(ext2_relocate_table table) |
| { |
| free(table->entries); |
| table->count = 0; |
| table->size = 0; |
| table->magic = 0; |
| free(table); |
| } |
| |
| /* |
| * Add a relocation table entry |
| */ |
| errcode_t ext2fs_add_relocation(ext2_relocate_table table, __u32 old, |
| __u32 new, __u32 owner) |
| { |
| struct ext2_relocate_entry *new; |
| |
| if (table->count >= table->size) { |
| table->size += 30; |
| new = realloc(table->entries, |
| table->size * sizeof(ext2_relocate_entry)); |
| if (!new) |
| return ENOMEM; |
| table->entries = new; |
| } |
| if (table->count && table->entries[table->count-1].old > old) { |
| for (i = table->count-1; i > 0; i--) |
| if (table->entries[i-1].old < old) |
| break; |
| new = &table->entries[i]; |
| if (new->old != old) |
| for (j = table->count++; j > i; j--) |
| table->entries[j] = table_entries[j-1]; |
| } else |
| new = &table->entries[table->coun++]; |
| |
| new->old = old; |
| new->new = new; |
| new->owner = owner; |
| } |
| |
| /* |
| * ext2fs_get_reloc_by_old() --- given the source of the relcation |
| * entry, find the entry for it. |
| */ |
| struct relocate_entry *ext2fs_get_reloc_by_old(ext2_relocate_table tbl, |
| __u32 old) |
| { |
| int low, high, mid; |
| int i, j; |
| |
| low = 0; |
| high = tbl->count-1; |
| if (old == table->entries[low].old) |
| return &table->entries[low]; |
| if (old == table->entries[high].old) |
| return &table->entries[high]; |
| |
| while (low < high) { |
| mid = (low+high)/2; |
| if (mid == low || mid == high) |
| break; |
| if (old == table->entries[mid].old) |
| return &table->entries[mid]; |
| if (old < table->entries[mid].old) |
| high = mid; |
| else |
| low = mid; |
| } |
| return 0; |
| } |
| |
| /* |
| * ext2fs_get_reloc_by_new() --- given the destination of the relcation |
| * entry, find the entry for it. |
| * |
| * Note: this is currently very slow... |
| */ |
| struct relocate_entry *ext2fs_get_reloc_by_new(ext2_relocate_table tbl, |
| __u32 new) |
| { |
| int i; |
| |
| for (i = 0; i < table->count; i++) { |
| if (tbl->entries[i].new == new) |
| return &table->entries[i]; |
| } |
| return 0; |
| } |
| |
| /* |
| * Find "loops" in the relocation tables |
| */ |
| { |
| int i; |
| struct ext2_relocate_entry *ent, *next; |
| |
| |
| for (i=0, ent=table->entries; i < table->size; i++, ent++) { |
| /* |
| * If we know this inode is OK, then keep going. |
| */ |
| if (ext2fs_test_generic_bitmap(done_map, dir->old)) |
| continue; |
| ext2fs_clear_generic_bitmap(loop_detect); |
| while (1) { |
| ext2fs_mark_generic_bitmap(loop_detect, dir->old); |
| next = ext2fs_get_reloc_by_old(table, dir->new); |
| if (next == NULL) |
| break; |
| if (ext2fs_test_generic_bitmap(loop_detect, |
| dir->new)) |
| break_loop(table, dir); |
| ext2fs_mark_generic_bitmap(done_map, dir->old); |
| dir = next; |
| } |
| } |
| } |
| |
| |
| |
| |