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 ctx->dir_info->size = 0; 297 ctx->dir_info->count = 0; 298 ext2fs_free_mem(&ctx->dir_info); 299 ctx->dir_info = 0; 300 } 301 } 302 303 /* 304 * Return the count of number of directories in the dir_info structure 305 */ 306 int e2fsck_get_num_dirinfo(e2fsck_t ctx) 307 { 308 return ctx->dir_info ? ctx->dir_info->count : 0; 309 } 310 311 extern struct dir_info_iter *e2fsck_dir_info_iter_begin(e2fsck_t ctx) 312 { 313 struct dir_info_iter *iter; 314 struct dir_info_db *db = ctx->dir_info; 315 316 iter = e2fsck_allocate_memory(ctx, sizeof(struct dir_info_iter), 317 "dir_info iterator"); 318 memset(iter, 0, sizeof(iter)); 319 320 if (db->tdb) 321 iter->tdb_iter = tdb_firstkey(db->tdb); 322 323 return iter; 324 } 325 326 extern void e2fsck_dir_info_iter_end(e2fsck_t ctx EXT2FS_ATTR((unused)), 327 struct dir_info_iter *iter) 328 { 329 if (iter->tdb_iter.dptr) 330 free(iter->tdb_iter.dptr); 331 ext2fs_free_mem(&iter); 332 } 333 334 /* 335 * A simple interator function 336 */ 337 struct dir_info *e2fsck_dir_info_iter(e2fsck_t ctx, struct dir_info_iter *iter) 338 { 339 TDB_DATA data, key; 340 struct dir_info_db *db = ctx->dir_info; 341 struct dir_info_ent *buf; 342 static struct dir_info ret_dir_info; 343 344 if (!ctx->dir_info || !iter) 345 return 0; 346 347 if (db->tdb) { 348 if (iter->tdb_iter.dptr == 0) 349 return 0; 350 key = iter->tdb_iter; 351 data = tdb_fetch(db->tdb, key); 352 if (!data.dptr) { 353 printf("iter fetch failed: %s\n", 354 tdb_errorstr(db->tdb)); 355 return 0; 356 } 357 buf = (struct dir_info_ent *) data.dptr; 358 ret_dir_info.ino = *((ext2_ino_t *) iter->tdb_iter.dptr); 359 ret_dir_info.dotdot = buf->dotdot; 360 ret_dir_info.parent = buf->parent; 361 iter->tdb_iter = tdb_nextkey(db->tdb, key); 362 free(key.dptr); 363 free(data.dptr); 364 return &ret_dir_info; 365 } 366 367 if (iter->i >= ctx->dir_info->count) 368 return 0; 369 370 #ifdef DIRINFO_DEBUG 371 printf("iter(%d, %d, %d)...", ctx->dir_info->array[iter->i].ino, 372 ctx->dir_info->array[iter->i].dotdot, 373 ctx->dir_info->array[iter->i].parent); 374 #endif 375 ctx->dir_info->last_lookup = ctx->dir_info->array + iter->i++; 376 return(ctx->dir_info->last_lookup); 377 } 378 379 /* 380 * This function only sets the parent pointer, and requires that 381 * dirinfo structure has already been created. 382 */ 383 int e2fsck_dir_info_set_parent(e2fsck_t ctx, ext2_ino_t ino, 384 ext2_ino_t parent) 385 { 386 struct dir_info *p; 387 388 p = e2fsck_get_dir_info(ctx, ino); 389 if (!p) 390 return 1; 391 p->parent = parent; 392 e2fsck_put_dir_info(ctx, p); 393 return 0; 394 } 395 396 /* 397 * This function only sets the dot dot pointer, and requires that 398 * dirinfo structure has already been created. 399 */ 400 int e2fsck_dir_info_set_dotdot(e2fsck_t ctx, ext2_ino_t ino, 401 ext2_ino_t dotdot) 402 { 403 struct dir_info *p; 404 405 p = e2fsck_get_dir_info(ctx, ino); 406 if (!p) 407 return 1; 408 p->dotdot = dotdot; 409 e2fsck_put_dir_info(ctx, p); 410 return 0; 411 } 412 413 /* 414 * This function only sets the parent pointer, and requires that 415 * dirinfo structure has already been created. 416 */ 417 int e2fsck_dir_info_get_parent(e2fsck_t ctx, ext2_ino_t ino, 418 ext2_ino_t *parent) 419 { 420 struct dir_info *p; 421 422 p = e2fsck_get_dir_info(ctx, ino); 423 if (!p) 424 return 1; 425 *parent = p->parent; 426 return 0; 427 } 428 429 /* 430 * This function only sets the dot dot pointer, and requires that 431 * dirinfo structure has already been created. 432 */ 433 int e2fsck_dir_info_get_dotdot(e2fsck_t ctx, ext2_ino_t ino, 434 ext2_ino_t *dotdot) 435 { 436 struct dir_info *p; 437 438 p = e2fsck_get_dir_info(ctx, ino); 439 if (!p) 440 return 1; 441 *dotdot = p->dotdot; 442 return 0; 443 } 444 445