Theodore Ts'o | 052db4b | 1997-06-12 07:14:32 +0000 | [diff] [blame^] | 1 | /* |
| 2 | * inodemap.c --- ext2resizer indoe mapper |
| 3 | * |
| 4 | * Copyright (C) 1997 Theodore Ts'o |
| 5 | * |
| 6 | * %Begin-Header% |
| 7 | * All rights reserved. |
| 8 | * %End-Header% |
| 9 | */ |
| 10 | |
| 11 | #include "resize2fs.h" |
| 12 | |
| 13 | struct inode_map_entry { |
| 14 | ino_t old, new; |
| 15 | }; |
| 16 | |
| 17 | struct inode_map_struct { |
| 18 | struct inode_map_entry *list; |
| 19 | int size; |
| 20 | int num; |
| 21 | int sorted; |
| 22 | }; |
| 23 | |
| 24 | typedef struct inode_map_struct *inode_map; |
| 25 | |
| 26 | /* |
| 27 | * Create inode map table |
| 28 | */ |
| 29 | static errcode_t create_inode_map(inode_map *imap, int size) |
| 30 | { |
| 31 | inode_map new; |
| 32 | |
| 33 | new = malloc(sizeof(struct inode_map_struct)); |
| 34 | if (!new) |
| 35 | return ENOMEM; |
| 36 | memset(new, 0, sizeof(struct inode_map_struct)); |
| 37 | |
| 38 | new->size = size ? size : 50; |
| 39 | new->num = 0; |
| 40 | new->sorted = 1; |
| 41 | |
| 42 | new->list = malloc(sizeof(struct inode_map_struct) * new->size); |
| 43 | if (!new->list) { |
| 44 | free(new); |
| 45 | return ENOMEM; |
| 46 | } |
| 47 | *imap = new; |
| 48 | return 0; |
| 49 | } |
| 50 | |
| 51 | /* |
| 52 | * Add an entry to the inode table map |
| 53 | */ |
| 54 | static errcode_t add_inode_map_entry(inode_map imap, ino_t old, ino_t new) |
| 55 | { |
| 56 | struct inode_map_entry *p; |
| 57 | int newsize; |
| 58 | |
| 59 | if (imap->num >= imap->size) { |
| 60 | newsize = imap->size + 100; |
| 61 | p = realloc(imap->list, |
| 62 | sizeof(struct inode_map_struct) * newsize); |
| 63 | if (!p) |
| 64 | return ENOMEM; |
| 65 | imap->list = p; |
| 66 | imap->size = newsize; |
| 67 | } |
| 68 | if (imap->num) { |
| 69 | if (imap->list[imap->num-1].old > old) |
| 70 | imap->sorted = 0; |
| 71 | } |
| 72 | imap->list[imap->num].old = old; |
| 73 | imap->list[imap->num].new = new; |
| 74 | imap->num++; |
| 75 | return 0; |
| 76 | } |
| 77 | |
| 78 | /* |
| 79 | * Helper function for qsort |
| 80 | */ |
| 81 | static int inode_map_cmp(const void *a, const void *b) |
| 82 | { |
| 83 | const struct inode_map_entry *db_a = |
| 84 | (const struct inode_map_entry *) a; |
| 85 | const struct inode_map_entry *db_b = |
| 86 | (const struct inode_map_entry *) b; |
| 87 | |
| 88 | return (db_a->old - db_b->old); |
| 89 | } |
| 90 | |
| 91 | /* |
| 92 | * Given an inode map and inode number, look up the old inode number |
| 93 | * and return the new inode number |
| 94 | */ |
| 95 | static ino_t inode_map_translate(inode_map imap, ino_t old) |
| 96 | { |
| 97 | int low, high, mid; |
| 98 | ino_t lowval, highval; |
| 99 | float range; |
| 100 | |
| 101 | if (!imap->sorted) { |
| 102 | qsort(imap->list, imap->num, |
| 103 | sizeof(struct inode_map_entry), inode_map_cmp); |
| 104 | imap->sorted = 1; |
| 105 | } |
| 106 | low = 0; |
| 107 | high = imap->num-1; |
| 108 | while (low <= high) { |
| 109 | #if 0 |
| 110 | mid = (low+high)/2; |
| 111 | #else |
| 112 | if (low == high) |
| 113 | mid = low; |
| 114 | else { |
| 115 | /* Interpolate for efficiency */ |
| 116 | lowval = imap->list[low].old; |
| 117 | highval = imap->list[high].old; |
| 118 | |
| 119 | if (old < lowval) |
| 120 | range = 0; |
| 121 | else if (old > highval) |
| 122 | range = 1; |
| 123 | else |
| 124 | range = ((float) (old - lowval)) / |
| 125 | (highval - lowval); |
| 126 | mid = low + ((int) (range * (high-low))); |
| 127 | } |
| 128 | #endif |
| 129 | if (old == imap->list[mid].old) |
| 130 | return imap->list[mid].new; |
| 131 | if (old < imap->list[mid].old) |
| 132 | high = mid-1; |
| 133 | else |
| 134 | low = mid+1; |
| 135 | } |
| 136 | return 0; |
| 137 | } |
| 138 | |
| 139 | int check_and_change_inodes(ino_t dir, int entry, |
| 140 | struct ext2_dir_entry *dirent, int offset, |
| 141 | int blocksize, char *buf, void *private) |
| 142 | { |
| 143 | inode_map imap = private; |
| 144 | ino_t new; |
| 145 | |
| 146 | if (!dirent->inode) |
| 147 | return 0; |
| 148 | |
| 149 | new = inode_map_translate(imap, dirent->inode); |
| 150 | |
| 151 | if (!new) |
| 152 | return 0; |
| 153 | |
| 154 | printf("Inode translate (dir=%ld, name=%.*s, %ld->%ld)\n", |
| 155 | dir, dirent->name_len, dirent->name, dirent->inode, new); |
| 156 | |
| 157 | dirent->inode = new; |
| 158 | |
| 159 | return DIRENT_CHANGED; |
| 160 | } |
| 161 | |
| 162 | errcode_t ext2fs_inode_move(ext2_resize_t rfs) |
| 163 | { |
| 164 | ino_t ino, start, end, new; |
| 165 | struct ext2_inode inode; |
| 166 | ext2_inode_scan scan; |
| 167 | inode_map imap; |
| 168 | errcode_t retval; |
| 169 | int group; |
| 170 | |
| 171 | if (rfs->old_fs->group_desc_count <= |
| 172 | rfs->new_fs->group_desc_count) |
| 173 | return 0; |
| 174 | |
| 175 | retval = create_inode_map(&imap, 0); |
| 176 | if (retval) |
| 177 | return retval; |
| 178 | |
| 179 | retval = ext2fs_open_inode_scan(rfs->old_fs, 0, &scan); |
| 180 | if (retval) |
| 181 | return retval; |
| 182 | |
| 183 | retval = ext2fs_inode_scan_goto_blockgroup(scan, |
| 184 | rfs->new_fs->group_desc_count); |
| 185 | if (retval) { |
| 186 | ext2fs_close_inode_scan(scan); |
| 187 | return retval; |
| 188 | } |
| 189 | |
| 190 | new = EXT2_FIRST_INODE(rfs->new_fs->super); |
| 191 | |
| 192 | /* |
| 193 | * First, copy all of the inodes that need to be moved |
| 194 | * elsewhere in the inode table |
| 195 | */ |
| 196 | while (1) { |
| 197 | retval = ext2fs_get_next_inode(scan, &ino, &inode); |
| 198 | if (retval) |
| 199 | return retval; |
| 200 | if (!ino) |
| 201 | break; |
| 202 | |
| 203 | if (!ext2fs_test_inode_bitmap(rfs->old_fs->inode_map, ino)) |
| 204 | continue; |
| 205 | |
| 206 | /* |
| 207 | * Find a new inode |
| 208 | */ |
| 209 | while (1) { |
| 210 | if (!ext2fs_test_inode_bitmap(rfs->new_fs->inode_map, |
| 211 | new)) |
| 212 | break; |
| 213 | new++; |
| 214 | if (new > rfs->new_fs->super->s_inodes_count) |
| 215 | return ENOSPC; |
| 216 | } |
| 217 | ext2fs_mark_inode_bitmap(rfs->new_fs->inode_map, new); |
| 218 | retval = ext2fs_write_inode(rfs->old_fs, new, &inode); |
| 219 | if (retval) |
| 220 | return retval; |
| 221 | group = (new-1) / EXT2_INODES_PER_GROUP(rfs->new_fs->super); |
| 222 | if (LINUX_S_ISDIR(inode.i_mode)) |
| 223 | rfs->new_fs->group_desc[group].bg_used_dirs_count++; |
| 224 | |
| 225 | printf("inode %ld->%ld\n", ino, new); |
| 226 | |
| 227 | add_inode_map_entry(imap, ino, new); |
| 228 | } |
| 229 | /* |
| 230 | * Now, we iterate over all of the directories to update the |
| 231 | * inode references |
| 232 | */ |
| 233 | retval = ext2fs_dblist_dir_iterate(rfs->old_fs->dblist, 0, 0, |
| 234 | check_and_change_inodes, imap); |
| 235 | if (retval) |
| 236 | return retval; |
| 237 | |
| 238 | return 0; |
| 239 | } |
| 240 | |