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