1 /* 2 * dirinfo.c --- maintains the directory information table for e2fsck. 3 * 4 * Copyright (C) 1993 Theodore Ts'o. This file may be redistributed 5 * under the terms of the GNU Public License. 6 */ 7 8 #undef DIRINFO_DEBUG 9 10 #include "e2fsck.h" 11 #include <sys/stat.h> 12 #include <fcntl.h> 13 #include "uuid/uuid.h" 14 15 #include <ext2fs/tdb.h> 16 17 struct dir_info_db { 18 int count; 19 int size; 20 struct dir_info *array; 21 struct dir_info *last_lookup; 22 char *tdb_fn; 23 TDB_CONTEXT *tdb; 24 }; 25 26 struct dir_info_iter { 27 int i; 28 TDB_DATA tdb_iter; 29 }; 30 31 struct dir_info_ent { 32 ext2_ino_t dotdot; /* Parent according to '..' */ 33 ext2_ino_t parent; /* Parent according to treewalk */ 34 }; 35 36 37 static void e2fsck_put_dir_info(e2fsck_t ctx, struct dir_info *dir); 38 39 static void setup_tdb(e2fsck_t ctx, ext2_ino_t num_dirs) 40 { 41 struct dir_info_db *db = ctx->dir_info; 42 unsigned int threshold; 43 errcode_t retval; 44 char *tdb_dir, uuid[40]; 45 int fd, enable; 46 47 profile_get_string(ctx->profile, "scratch_files", "directory", 0, 0, 48 &tdb_dir); 49 profile_get_uint(ctx->profile, "scratch_files", 50 "numdirs_threshold", 0, 0, &threshold); 51 profile_get_boolean(ctx->profile, "scratch_files", 52 "dirinfo", 0, 1, &enable); 53 54 if (!enable || !tdb_dir || access(tdb_dir, W_OK) || 55 (threshold && num_dirs <= threshold)) 56 return; 57 58 retval = ext2fs_get_mem(strlen(tdb_dir) + 64, &db->tdb_fn); 59 if (retval) 60 return; 61 62 uuid_unparse(ctx->fs->super->s_uuid, uuid); 63 sprintf(db->tdb_fn, "%s/%s-dirinfo-XXXXXX", tdb_dir, uuid); 64 fd = mkstemp(db->tdb_fn); 65 db->tdb = tdb_open(db->tdb_fn, 0, TDB_CLEAR_IF_FIRST, 66 O_RDWR | O_CREAT | O_TRUNC, 0600); 67 close(fd); 68 } 69 70 static void setup_db(e2fsck_t ctx) 71 { 72 struct dir_info_db *db; 73 ext2_ino_t num_dirs; 74 errcode_t retval; 75 76 db = (struct dir_info_db *) 77 e2fsck_allocate_memory(ctx, sizeof(struct dir_info_db), 78 "directory map db"); 79 db->count = db->size = 0; 80 db->array = 0; 81 82 ctx->dir_info = db; 83 84 retval = ext2fs_get_num_dirs(ctx->fs, &num_dirs); 85 if (retval) 86 num_dirs = 1024; /* Guess */ 87 88 setup_tdb(ctx, num_dirs); 89 90 if (db->tdb) { 91 #ifdef DIRINFO_DEBUG 92 printf("Note: using tdb!\n"); 93 #endif 94 return; 95 } 96 97 db->size = num_dirs + 10; 98 db->array = (struct dir_info *) 99 e2fsck_allocate_memory(ctx, db->size 100 * sizeof (struct dir_info), 101 "directory map"); 102 } 103 104 /* 105 * This subroutine is called during pass1 to create a directory info 106 * entry. During pass1, the passed-in parent is 0; it will get filled 107 * in during pass2. 108 */ 109 void e2fsck_add_dir_info(e2fsck_t ctx, ext2_ino_t ino, ext2_ino_t parent) 110 { 111 struct dir_info_db *db; 112 struct dir_info *dir, ent; 113 int i, j; 114 errcode_t retval; 115 unsigned long old_size; 116 117 #ifdef DIRINFO_DEBUG 118 printf("add_dir_info for inode (%lu, %lu)...\n", ino, parent); 119 #endif 120 if (!ctx->dir_info) 121 setup_db(ctx); 122 db = ctx->dir_info; 123 124 if (ctx->dir_info->count >= ctx->dir_info->size) { 125 old_size = ctx->dir_info->size * sizeof(struct dir_info); 126 ctx->dir_info->size += 10; 127 retval = ext2fs_resize_mem(old_size, ctx->dir_info->size * 128 sizeof(struct dir_info), 129 &ctx->dir_info->array); 130 if (retval) { 131 ctx->dir_info->size -= 10; 132 return; 133 } 134 } 135 136 ent.ino = ino; 137 ent.parent = parent; 138 ent.dotdot = parent; 139 140 if (db->tdb) { 141 e2fsck_put_dir_info(ctx, &ent); 142 return; 143 } 144 145 /* 146 * Normally, add_dir_info is called with each inode in 147 * sequential order; but once in a while (like when pass 3 148 * needs to recreate the root directory or lost+found 149 * directory) it is called out of order. In those cases, we 150 * need to move the dir_info entries down to make room, since 151 * the dir_info array needs to be sorted by inode number for 152 * get_dir_info()'s sake. 153 */ 154 if (ctx->dir_info->count && 155 ctx->dir_info->array[ctx->dir_info->count-1].ino >= ino) { 156 for (i = ctx->dir_info->count-1; i > 0; i--) 157 if (ctx->dir_info->array[i-1].ino < ino) 158 break; 159 dir = &ctx->dir_info->array[i]; 160 if (dir->ino != ino) 161 for (j = ctx->dir_info->count++; j > i; j--) 162 ctx->dir_info->array[j] = ctx->dir_info->array[j-1]; 163 } else 164 dir = &ctx->dir_info->array[ctx->dir_info->count++]; 165 166 dir->ino = ino; 167 dir->dotdot = parent; 168 dir->parent = parent; 169 } 170 171 /* 172 * get_dir_info() --- given an inode number, try to find the directory 173 * information entry for it. 174 */ 175 static struct dir_info *e2fsck_get_dir_info(e2fsck_t ctx, ext2_ino_t ino) 176 { 177 struct dir_info_db *db = ctx->dir_info; 178 int low, high, mid; 179 struct dir_info_ent *buf; 180 static struct dir_info ret_dir_info; 181 182 if (!db) 183 return 0; 184 185 #ifdef DIRINFO_DEBUG 186 printf("e2fsck_get_dir_info %d...", ino); 187 #endif 188 189 if (db->tdb) { 190 TDB_DATA key, data; 191 192 key.dptr = (unsigned char *) &ino; 193 key.dsize = sizeof(ext2_ino_t); 194 195 data = tdb_fetch(db->tdb, key); 196 if (!data.dptr) { 197 if (tdb_error(db->tdb) != TDB_ERR_NOEXIST) 198 printf("fetch failed: %s\n", 199 tdb_errorstr(db->tdb)); 200 return 0; 201 } 202 203 buf = (struct dir_info_ent *) data.dptr; 204 ret_dir_info.ino = ino; 205 ret_dir_info.dotdot = buf->dotdot; 206 ret_dir_info.parent = buf->parent; 207 #ifdef DIRINFO_DEBUG 208 printf("(%d,%d,%d)\n", ino, buf->dotdot, buf->parent); 209 #endif 210 free(data.dptr); 211 return &ret_dir_info; 212 } 213 214 if (db->last_lookup && db->last_lookup->ino == ino) 215 return db->last_lookup; 216 217 low = 0; 218 high = ctx->dir_info->count-1; 219 if (ino == ctx->dir_info->array[low].ino) { 220 #ifdef DIRINFO_DEBUG 221 printf("(%d,%d,%d)\n", ino, 222 ctx->dir_info->array[low].dotdot, 223 ctx->dir_info->array[low].parent); 224 #endif 225 return &ctx->dir_info->array[low]; 226 } 227 if (ino == ctx->dir_info->array[high].ino) { 228 #ifdef DIRINFO_DEBUG 229 printf("(%d,%d,%d)\n", ino, 230 ctx->dir_info->array[high].dotdot, 231 ctx->dir_info->array[high].parent); 232 #endif 233 return &ctx->dir_info->array[high]; 234 } 235 236 while (low < high) { 237 mid = (low+high)/2; 238 if (mid == low || mid == high) 239 break; 240 if (ino == ctx->dir_info->array[mid].ino) { 241 #ifdef DIRINFO_DEBUG 242 printf("(%d,%d,%d)\n", ino, 243 ctx->dir_info->array[mid].dotdot, 244 ctx->dir_info->array[mid].parent); 245 #endif 246 return &ctx->dir_info->array[mid]; 247 } 248 if (ino < ctx->dir_info->array[mid].ino) 249 high = mid; 250 else 251 low = mid; 252 } 253 return 0; 254 } 255 256 static void e2fsck_put_dir_info(e2fsck_t ctx, struct dir_info *dir) 257 { 258 struct dir_info_db *db = ctx->dir_info; 259 struct dir_info_ent buf; 260 TDB_DATA key, data; 261 262 #ifdef DIRINFO_DEBUG 263 printf("e2fsck_put_dir_info (%d, %d, %d)...", dir->ino, dir->dotdot, 264 dir->parent); 265 #endif 266 267 if (!db->tdb) 268 return; 269 270 buf.parent = dir->parent; 271 buf.dotdot = dir->dotdot; 272 273 key.dptr = (unsigned char *) &dir->ino; 274 key.dsize = sizeof(ext2_ino_t); 275 data.dptr = (unsigned char *) &buf; 276 data.dsize = sizeof(buf); 277 278 if (tdb_store(db->tdb, key, data, TDB_REPLACE) == -1) { 279 printf("store failed: %s\n", tdb_errorstr(db->tdb)); 280 } 281 return; 282 } 283 284 /* 285 * Free the dir_info structure when it isn't needed any more. 286 */ 287 void e2fsck_free_dir_info(e2fsck_t ctx) 288 { 289 if (ctx->dir_info) { 290 if (ctx->dir_info->tdb) 291 tdb_close(ctx->dir_info->tdb); 292 if (ctx->dir_info->tdb_fn) { 293 unlink(ctx->dir_info->tdb_fn); 294 free(ctx->dir_info->tdb_fn); 295 } 296 if (ctx->dir_info->array) 297 ext2fs_free_mem(&ctx->dir_info->array); 298 ctx->dir_info->array = 0; 299 ctx->dir_info->size = 0; 300 ctx->dir_info->count = 0; 301 ext2fs_free_mem(&ctx->dir_info); 302 ctx->dir_info = 0; 303 } 304 } 305 306 /* 307 * Return the count of number of directories in the dir_info structure 308 */ 309 int e2fsck_get_num_dirinfo(e2fsck_t ctx) 310 { 311 return ctx->dir_info ? ctx->dir_info->count : 0; 312 } 313 314 extern struct dir_info_iter *e2fsck_dir_info_iter_begin(e2fsck_t ctx) 315 { 316 struct dir_info_iter *iter; 317 struct dir_info_db *db = ctx->dir_info; 318 319 iter = e2fsck_allocate_memory(ctx, sizeof(struct dir_info_iter), 320 "dir_info iterator"); 321 memset(iter, 0, sizeof(iter)); 322 323 if (db->tdb) 324 iter->tdb_iter = tdb_firstkey(db->tdb); 325 326 return iter; 327 } 328 329 extern void e2fsck_dir_info_iter_end(e2fsck_t ctx EXT2FS_ATTR((unused)), 330 struct dir_info_iter *iter) 331 { 332 free(iter->tdb_iter.dptr); 333 ext2fs_free_mem(&iter); 334 } 335 336 /* 337 * A simple interator function 338 */ 339 struct dir_info *e2fsck_dir_info_iter(e2fsck_t ctx, struct dir_info_iter *iter) 340 { 341 TDB_DATA data, key; 342 struct dir_info_db *db = ctx->dir_info; 343 struct dir_info_ent *buf; 344 static struct dir_info ret_dir_info; 345 346 if (!ctx->dir_info || !iter) 347 return 0; 348 349 if (db->tdb) { 350 if (iter->tdb_iter.dptr == 0) 351 return 0; 352 key = iter->tdb_iter; 353 data = tdb_fetch(db->tdb, key); 354 if (!data.dptr) { 355 printf("iter fetch failed: %s\n", 356 tdb_errorstr(db->tdb)); 357 return 0; 358 } 359 buf = (struct dir_info_ent *) data.dptr; 360 ret_dir_info.ino = *((ext2_ino_t *) iter->tdb_iter.dptr); 361 ret_dir_info.dotdot = buf->dotdot; 362 ret_dir_info.parent = buf->parent; 363 iter->tdb_iter = tdb_nextkey(db->tdb, key); 364 free(key.dptr); 365 free(data.dptr); 366 return &ret_dir_info; 367 } 368 369 if (iter->i >= ctx->dir_info->count) 370 return 0; 371 372 #ifdef DIRINFO_DEBUG 373 printf("iter(%d, %d, %d)...", ctx->dir_info->array[iter->i].ino, 374 ctx->dir_info->array[iter->i].dotdot, 375 ctx->dir_info->array[iter->i].parent); 376 #endif 377 ctx->dir_info->last_lookup = ctx->dir_info->array + iter->i++; 378 return(ctx->dir_info->last_lookup); 379 } 380 381 /* 382 * This function only sets the parent pointer, and requires that 383 * dirinfo structure has already been created. 384 */ 385 int e2fsck_dir_info_set_parent(e2fsck_t ctx, ext2_ino_t ino, 386 ext2_ino_t parent) 387 { 388 struct dir_info *p; 389 390 p = e2fsck_get_dir_info(ctx, ino); 391 if (!p) 392 return 1; 393 p->parent = parent; 394 e2fsck_put_dir_info(ctx, p); 395 return 0; 396 } 397 398 /* 399 * This function only sets the dot dot pointer, and requires that 400 * dirinfo structure has already been created. 401 */ 402 int e2fsck_dir_info_set_dotdot(e2fsck_t ctx, ext2_ino_t ino, 403 ext2_ino_t dotdot) 404 { 405 struct dir_info *p; 406 407 p = e2fsck_get_dir_info(ctx, ino); 408 if (!p) 409 return 1; 410 p->dotdot = dotdot; 411 e2fsck_put_dir_info(ctx, p); 412 return 0; 413 } 414 415 /* 416 * This function only sets the parent pointer, and requires that 417 * dirinfo structure has already been created. 418 */ 419 int e2fsck_dir_info_get_parent(e2fsck_t ctx, ext2_ino_t ino, 420 ext2_ino_t *parent) 421 { 422 struct dir_info *p; 423 424 p = e2fsck_get_dir_info(ctx, ino); 425 if (!p) 426 return 1; 427 *parent = p->parent; 428 return 0; 429 } 430 431 /* 432 * This function only sets the dot dot pointer, and requires that 433 * dirinfo structure has already been created. 434 */ 435 int e2fsck_dir_info_get_dotdot(e2fsck_t ctx, ext2_ino_t ino, 436 ext2_ino_t *dotdot) 437 { 438 struct dir_info *p; 439 440 p = e2fsck_get_dir_info(ctx, ino); 441 if (!p) 442 return 1; 443 *dotdot = p->dotdot; 444 return 0; 445 } 446 447
