relocate/relocate.c

   1 /*
   2  * relocate.c --- maintains the relocation table
   3  *
   4  * Copyright (C) 1996 Theodore Ts'o.  This file may be redistributed
   5  * under the terms of the GNU Public License.
   6  */
   7
   8 #include <et/com_err.h>
   9
  10 /*
  11  * This routine creates a relocation table
  12  */
  13 errcode_t ext2fs_create_relocation_table(__u32 max, int size,
  14                                          ext2_relocate_table *ret);
  15 {
  16         ext2_relocate_table table;
  17
  18         table = malloc(sizeof(struct ext2_relocate_struct));
  19         if (!table)
  20                 return -ENOMEM;
  21         table->magic = 0;
  22         table->count = 0;
  23         table->size = size ? size : 30;
  24         table->max = max;
  25         table->entries = malloc(table->size * sizeof(ext2_relocate_entry));
  26         if (table->entries == 0) {
  27                 free(table);
  28                 return ENOMEM;
  29         }
  30         memset(table->entries, 0, table->size * sizeof(ext2_relocate_entry));
  31         *ret = table;
  32         return 0;
  33 }
  34
  35 /*
  36  * Free a relocation table
  37  */
  38 void ext2fs_free_relocation_table(ext2_relocate_table table)
  39 {
  40         free(table->entries);
  41         table->count = 0;
  42         table->size = 0;
  43         table->magic = 0;
  44         free(table);
  45 }
  46
  47 /*
  48  * Add a relocation table entry
  49  */
  50 errcode_t ext2fs_add_relocation(ext2_relocate_table table, __u32 old,
  51                                 __u32 new, __u32 owner)
  52 {
  53         struct ext2_relocate_entry *new;
  54
  55         if (table->count >= table->size) {
  56                 table->size += 30;
  57                 new = realloc(table->entries,
  58                               table->size * sizeof(ext2_relocate_entry));
  59                 if (!new)
  60                         return ENOMEM;
  61                 table->entries = new;
  62         }
  63         if (table->count && table->entries[table->count-1].old > old) {
  64                 for (i = table->count-1; i > 0; i--)
  65                         if (table->entries[i-1].old < old)
  66                                 break;
  67                 new = &table->entries[i];
  68                 if (new->old != old)
  69                         for (j = table->count++; j > i; j--)
  70                                 table->entries[j] = table_entries[j-1];
  71         } else
  72                 new = &table->entries[table->coun++];
  73
  74         new->old = old;
  75         new->new = new;
  76         new->owner = owner;
  77 }
  78
  79 /*
  80  * ext2fs_get_reloc_by_old() --- given the source of the relcation
  81  * entry, find the entry for it.
  82  */
  83 struct relocate_entry *ext2fs_get_reloc_by_old(ext2_relocate_table tbl,
  84                                                __u32 old)
  85 {
  86         int     low, high, mid;
  87         int     i, j;
  88
  89         low = 0;
  90         high = tbl->count-1;
  91         if (old == table->entries[low].old)
  92                 return &table->entries[low];
  93         if  (old == table->entries[high].old)
  94                 return &table->entries[high];
  95
  96         while (low < high) {
  97                 mid = (low+high)/2;
  98                 if (mid == low || mid == high)
  99                         break;
 100                 if (old == table->entries[mid].old)
 101                         return &table->entries[mid];
 102                 if (old < table->entries[mid].old)
 103                         high = mid;
 104                 else
 105                         low = mid;
 106         }
 107         return 0;
 108 }
 109
 110 /*
 111  * ext2fs_get_reloc_by_new() --- given the destination of the relcation
 112  * entry, find the entry for it.
 113  *
 114  * Note: this is currently very slow...
 115  */
 116 struct relocate_entry *ext2fs_get_reloc_by_new(ext2_relocate_table tbl,
 117                                                __u32 new)
 118 {
 119         int     i;
 120
 121         for (i = 0; i < table->count; i++) {
 122                 if (tbl->entries[i].new == new)
 123                         return &table->entries[i];
 124         }
 125         return 0;
 126 }
 127
 128 /*
 129  * Find "loops" in the relocation tables
 130  */
 131 {
 132         int     i;
 133         struct ext2_relocate_entry *ent, *next;
 134
 135
 136         for (i=0, ent=table->entries; i < table->size; i++, ent++) {
 137                 /*
 138                  * If we know this inode is OK, then keep going.
 139                  */
 140                 if (ext2fs_test_generic_bitmap(done_map, dir->old))
 141                         continue;
 142                 ext2fs_clear_generic_bitmap(loop_detect);
 143                 while (1) {
 144                         ext2fs_mark_generic_bitmap(loop_detect, dir->old);
 145                         next = ext2fs_get_reloc_by_old(table, dir->new);
 146                         if (next == NULL)
 147                                 break;
 148                         if (ext2fs_test_generic_bitmap(loop_detect,
 149                                                        dir->new))
 150                                 break_loop(table, dir);
 151                         ext2fs_mark_generic_bitmap(done_map, dir->old);
 152                         dir = next;
 153                 }
 154         }
 155 }
 156
 157
 158
 159