1 /* 2 * rehash.c --- rebuild hash tree directories 3 * 4 * Copyright (C) 2002 Theodore Ts'o 5 * 6 * %Begin-Header% 7 * This file may be redistributed under the terms of the GNU Public 8 * License. 9 * %End-Header% 10 * 11 * This algorithm is designed for simplicity of implementation and to 12 * pack the directory as much as possible. It however requires twice 13 * as much memory as the size of the directory. The maximum size 14 * directory supported using a 4k blocksize is roughly a gigabyte, and 15 * so there may very well be problems with machines that don't have 16 * virtual memory, and obscenely large directories. 17 * 18 * An alternate algorithm which is much more disk intensive could be 19 * written, and probably will need to be written in the future. The 20 * design goals of such an algorithm are: (a) use (roughly) constant 21 * amounts of memory, no matter how large the directory, (b) the 22 * directory must be safe at all times, even if e2fsck is interrupted 23 * in the middle, (c) we must use minimal amounts of extra disk 24 * blocks. This pretty much requires an incremental approach, where 25 * we are reading from one part of the directory, and inserting into 26 * the front half. So the algorithm will have to keep track of a 27 * moving block boundary between the new tree and the old tree, and 28 * files will need to be moved from the old directory and inserted 29 * into the new tree. If the new directory requires space which isn't 30 * yet available, blocks from the beginning part of the old directory 31 * may need to be moved to the end of the directory to make room for 32 * the new tree: 33 * 34 * -------------------------------------------------------- 35 * | new tree | | old tree | 36 * -------------------------------------------------------- 37 * ^ ptr ^ptr 38 * tail new head old 39 * 40 * This is going to be a pain in the tuckus to implement, and will 41 * require a lot more disk accesses. So I'm going to skip it for now; 42 * it's only really going to be an issue for really, really big 43 * filesystems (when we reach the level of tens of millions of files 44 * in a single directory). It will probably be easier to simply 45 * require that e2fsck use VM first. 46 */ 47 48 #include "config.h" 49 #include <string.h> 50 #include <ctype.h> 51 #include <errno.h> 52 #include "e2fsck.h" 53 #include "problem.h" 54 55 /* Schedule a dir to be rebuilt during pass 3A. */ 56 void e2fsck_rehash_dir_later(e2fsck_t ctx, ext2_ino_t ino) 57 { 58 if (!ctx->dirs_to_hash) 59 ext2fs_u32_list_create(&ctx->dirs_to_hash, 50); 60 if (ctx->dirs_to_hash) 61 ext2fs_u32_list_add(ctx->dirs_to_hash, ino); 62 } 63 64 /* Ask if a dir will be rebuilt during pass 3A. */ 65 int e2fsck_dir_will_be_rehashed(e2fsck_t ctx, ext2_ino_t ino) 66 { 67 if (ctx->options & E2F_OPT_COMPRESS_DIRS) 68 return 1; 69 if (!ctx->dirs_to_hash) 70 return 0; 71 return ext2fs_u32_list_test(ctx->dirs_to_hash, ino); 72 } 73 74 #undef REHASH_DEBUG 75 76 struct fill_dir_struct { 77 char *buf; 78 struct ext2_inode *inode; 79 ext2_ino_t ino; 80 errcode_t err; 81 e2fsck_t ctx; 82 struct hash_entry *harray; 83 int max_array, num_array; 84 unsigned int dir_size; 85 int compress; 86 ino_t parent; 87 ext2_ino_t dir; 88 }; 89 90 struct hash_entry { 91 ext2_dirhash_t hash; 92 ext2_dirhash_t minor_hash; 93 ino_t ino; 94 struct ext2_dir_entry *dir; 95 }; 96 97 struct out_dir { 98 int num; 99 int max; 100 char *buf; 101 ext2_dirhash_t *hashes; 102 }; 103 104 static int fill_dir_block(ext2_filsys fs, 105 blk64_t *block_nr, 106 e2_blkcnt_t blockcnt, 107 blk64_t ref_block EXT2FS_ATTR((unused)), 108 int ref_offset EXT2FS_ATTR((unused)), 109 void *priv_data) 110 { 111 struct fill_dir_struct *fd = (struct fill_dir_struct *) priv_data; 112 struct hash_entry *new_array, *ent; 113 struct ext2_dir_entry *dirent; 114 char *dir; 115 unsigned int offset, dir_offset, rec_len, name_len; 116 int hash_alg; 117 118 if (blockcnt < 0) 119 return 0; 120 121 offset = blockcnt * fs->blocksize; 122 if (offset + fs->blocksize > fd->inode->i_size) { 123 fd->err = EXT2_ET_DIR_CORRUPTED; 124 return BLOCK_ABORT; 125 } 126 127 dir = (fd->buf+offset); 128 if (*block_nr == 0) { 129 memset(dir, 0, fs->blocksize); 130 dirent = (struct ext2_dir_entry *) dir; 131 (void) ext2fs_set_rec_len(fs, fs->blocksize, dirent); 132 } else { 133 int flags = fs->flags; 134 fs->flags |= EXT2_FLAG_IGNORE_CSUM_ERRORS; 135 fd->err = ext2fs_read_dir_block4(fs, *block_nr, dir, 0, 136 fd->dir); 137 fs->flags = (flags & EXT2_FLAG_IGNORE_CSUM_ERRORS) | 138 (fs->flags & ~EXT2_FLAG_IGNORE_CSUM_ERRORS); 139 if (fd->err) 140 return BLOCK_ABORT; 141 } 142 hash_alg = fs->super->s_def_hash_version; 143 if ((hash_alg <= EXT2_HASH_TEA) && 144 (fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH)) 145 hash_alg += 3; 146 /* While the directory block is "hot", index it. */ 147 dir_offset = 0; 148 while (dir_offset < fs->blocksize) { 149 dirent = (struct ext2_dir_entry *) (dir + dir_offset); 150 (void) ext2fs_get_rec_len(fs, dirent, &rec_len); 151 name_len = ext2fs_dirent_name_len(dirent); 152 if (((dir_offset + rec_len) > fs->blocksize) || 153 (rec_len < 8) || 154 ((rec_len % 4) != 0) || 155 (name_len + 8 > rec_len)) { 156 fd->err = EXT2_ET_DIR_CORRUPTED; 157 return BLOCK_ABORT; 158 } 159 dir_offset += rec_len; 160 if (dirent->inode == 0) 161 continue; 162 if (!fd->compress && (name_len == 1) && 163 (dirent->name[0] == '.')) 164 continue; 165 if (!fd->compress && (name_len == 2) && 166 (dirent->name[0] == '.') && (dirent->name[1] == '.')) { 167 fd->parent = dirent->inode; 168 continue; 169 } 170 if (fd->num_array >= fd->max_array) { 171 new_array = realloc(fd->harray, 172 sizeof(struct hash_entry) * (fd->max_array+500)); 173 if (!new_array) { 174 fd->err = ENOMEM; 175 return BLOCK_ABORT; 176 } 177 fd->harray = new_array; 178 fd->max_array += 500; 179 } 180 ent = fd->harray + fd->num_array++; 181 ent->dir = dirent; 182 fd->dir_size += EXT2_DIR_REC_LEN(name_len); 183 ent->ino = dirent->inode; 184 if (fd->compress) 185 ent->hash = ent->minor_hash = 0; 186 else { 187 fd->err = ext2fs_dirhash(hash_alg, dirent->name, 188 name_len, 189 fs->super->s_hash_seed, 190 &ent->hash, &ent->minor_hash); 191 if (fd->err) 192 return BLOCK_ABORT; 193 } 194 } 195 196 return 0; 197 } 198 199 /* Used for sorting the hash entry */ 200 static EXT2_QSORT_TYPE ino_cmp(const void *a, const void *b) 201 { 202 const struct hash_entry *he_a = (const struct hash_entry *) a; 203 const struct hash_entry *he_b = (const struct hash_entry *) b; 204 205 return (he_a->ino - he_b->ino); 206 } 207 208 /* Used for sorting the hash entry */ 209 static EXT2_QSORT_TYPE name_cmp(const void *a, const void *b) 210 { 211 const struct hash_entry *he_a = (const struct hash_entry *) a; 212 const struct hash_entry *he_b = (const struct hash_entry *) b; 213 unsigned int he_a_len, he_b_len, min_len; 214 int ret; 215 216 he_a_len = ext2fs_dirent_name_len(he_a->dir); 217 he_b_len = ext2fs_dirent_name_len(he_b->dir); 218 min_len = he_a_len; 219 if (min_len > he_b_len) 220 min_len = he_b_len; 221 222 ret = strncmp(he_a->dir->name, he_b->dir->name, min_len); 223 if (ret == 0) { 224 if (he_a_len > he_b_len) 225 ret = 1; 226 else if (he_a_len < he_b_len) 227 ret = -1; 228 else 229 ret = he_b->dir->inode - he_a->dir->inode; 230 } 231 return ret; 232 } 233 234 /* Used for sorting the hash entry */ 235 static EXT2_QSORT_TYPE hash_cmp(const void *a, const void *b) 236 { 237 const struct hash_entry *he_a = (const struct hash_entry *) a; 238 const struct hash_entry *he_b = (const struct hash_entry *) b; 239 int ret; 240 241 if (he_a->hash > he_b->hash) 242 ret = 1; 243 else if (he_a->hash < he_b->hash) 244 ret = -1; 245 else { 246 if (he_a->minor_hash > he_b->minor_hash) 247 ret = 1; 248 else if (he_a->minor_hash < he_b->minor_hash) 249 ret = -1; 250 else 251 ret = name_cmp(a, b); 252 } 253 return ret; 254 } 255 256 static errcode_t alloc_size_dir(ext2_filsys fs, struct out_dir *outdir, 257 int blocks) 258 { 259 void *new_mem; 260 261 if (outdir->max) { 262 new_mem = realloc(outdir->buf, blocks * fs->blocksize); 263 if (!new_mem) 264 return ENOMEM; 265 outdir->buf = new_mem; 266 new_mem = realloc(outdir->hashes, 267 blocks * sizeof(ext2_dirhash_t)); 268 if (!new_mem) 269 return ENOMEM; 270 outdir->hashes = new_mem; 271 } else { 272 outdir->buf = malloc(blocks * fs->blocksize); 273 outdir->hashes = malloc(blocks * sizeof(ext2_dirhash_t)); 274 outdir->num = 0; 275 } 276 outdir->max = blocks; 277 return 0; 278 } 279 280 static void free_out_dir(struct out_dir *outdir) 281 { 282 free(outdir->buf); 283 free(outdir->hashes); 284 outdir->max = 0; 285 outdir->num =0; 286 } 287 288 static errcode_t get_next_block(ext2_filsys fs, struct out_dir *outdir, 289 char ** ret) 290 { 291 errcode_t retval; 292 293 if (outdir->num >= outdir->max) { 294 retval = alloc_size_dir(fs, outdir, outdir->max + 50); 295 if (retval) 296 return retval; 297 } 298 *ret = outdir->buf + (outdir->num++ * fs->blocksize); 299 memset(*ret, 0, fs->blocksize); 300 return 0; 301 } 302 303 /* 304 * This function is used to make a unique filename. We do this by 305 * appending ~0, and then incrementing the number. However, we cannot 306 * expand the length of the filename beyond the padding available in 307 * the directory entry. 308 */ 309 static void mutate_name(char *str, unsigned int *len) 310 { 311 int i; 312 unsigned int l = *len; 313 314 /* 315 * First check to see if it looks the name has been mutated 316 * already 317 */ 318 for (i = l-1; i > 0; i--) { 319 if (!isdigit(str[i])) 320 break; 321 } 322 if ((i == (int)l - 1) || (str[i] != '~')) { 323 if (((l-1) & 3) < 2) 324 l += 2; 325 else 326 l = (l+3) & ~3; 327 str[l-2] = '~'; 328 str[l-1] = '0'; 329 *len = l; 330 return; 331 } 332 for (i = l-1; i >= 0; i--) { 333 if (isdigit(str[i])) { 334 if (str[i] == '9') 335 str[i] = '0'; 336 else { 337 str[i]++; 338 return; 339 } 340 continue; 341 } 342 if (i == 1) { 343 if (str[0] == 'z') 344 str[0] = 'A'; 345 else if (str[0] == 'Z') { 346 str[0] = '~'; 347 str[1] = '0'; 348 } else 349 str[0]++; 350 } else if (i > 0) { 351 str[i] = '1'; 352 str[i-1] = '~'; 353 } else { 354 if (str[0] == '~') 355 str[0] = 'a'; 356 else 357 str[0]++; 358 } 359 break; 360 } 361 } 362 363 static int duplicate_search_and_fix(e2fsck_t ctx, ext2_filsys fs, 364 ext2_ino_t ino, 365 struct fill_dir_struct *fd) 366 { 367 struct problem_context pctx; 368 struct hash_entry *ent, *prev; 369 int i, j; 370 int fixed = 0; 371 char new_name[256]; 372 unsigned int new_len; 373 int hash_alg; 374 375 clear_problem_context(&pctx); 376 pctx.ino = ino; 377 378 hash_alg = fs->super->s_def_hash_version; 379 if ((hash_alg <= EXT2_HASH_TEA) && 380 (fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH)) 381 hash_alg += 3; 382 383 for (i=1; i < fd->num_array; i++) { 384 ent = fd->harray + i; 385 prev = ent - 1; 386 if (!ent->dir->inode || 387 (ext2fs_dirent_name_len(ent->dir) != 388 ext2fs_dirent_name_len(prev->dir)) || 389 strncmp(ent->dir->name, prev->dir->name, 390 ext2fs_dirent_name_len(ent->dir))) 391 continue; 392 pctx.dirent = ent->dir; 393 if ((ent->dir->inode == prev->dir->inode) && 394 fix_problem(ctx, PR_2_DUPLICATE_DIRENT, &pctx)) { 395 e2fsck_adjust_inode_count(ctx, ent->dir->inode, -1); 396 ent->dir->inode = 0; 397 fixed++; 398 continue; 399 } 400 new_len = ext2fs_dirent_name_len(ent->dir); 401 memcpy(new_name, ent->dir->name, new_len); 402 mutate_name(new_name, &new_len); 403 for (j=0; j < fd->num_array; j++) { 404 if ((i==j) || 405 (new_len != 406 (unsigned) ext2fs_dirent_name_len(fd->harray[j].dir)) || 407 strncmp(new_name, fd->harray[j].dir->name, new_len)) 408 continue; 409 mutate_name(new_name, &new_len); 410 411 j = -1; 412 } 413 new_name[new_len] = 0; 414 pctx.str = new_name; 415 if (fix_problem(ctx, PR_2_NON_UNIQUE_FILE, &pctx)) { 416 memcpy(ent->dir->name, new_name, new_len); 417 ext2fs_dirent_set_name_len(ent->dir, new_len); 418 ext2fs_dirhash(hash_alg, new_name, new_len, 419 fs->super->s_hash_seed, 420 &ent->hash, &ent->minor_hash); 421 fixed++; 422 } 423 } 424 return fixed; 425 } 426 427 428 static errcode_t copy_dir_entries(e2fsck_t ctx, 429 struct fill_dir_struct *fd, 430 struct out_dir *outdir) 431 { 432 ext2_filsys fs = ctx->fs; 433 errcode_t retval; 434 char *block_start; 435 struct hash_entry *ent; 436 struct ext2_dir_entry *dirent; 437 unsigned int rec_len, prev_rec_len, left, slack, offset; 438 int i; 439 ext2_dirhash_t prev_hash; 440 int csum_size = 0; 441 struct ext2_dir_entry_tail *t; 442 443 if (ctx->htree_slack_percentage == 255) { 444 profile_get_uint(ctx->profile, "options", 445 "indexed_dir_slack_percentage", 446 0, 20, 447 &ctx->htree_slack_percentage); 448 if (ctx->htree_slack_percentage > 100) 449 ctx->htree_slack_percentage = 20; 450 } 451 452 if (ext2fs_has_feature_metadata_csum(fs->super)) 453 csum_size = sizeof(struct ext2_dir_entry_tail); 454 455 outdir->max = 0; 456 retval = alloc_size_dir(fs, outdir, 457 (fd->dir_size / fs->blocksize) + 2); 458 if (retval) 459 return retval; 460 outdir->num = fd->compress ? 0 : 1; 461 offset = 0; 462 outdir->hashes[0] = 0; 463 prev_hash = 1; 464 if ((retval = get_next_block(fs, outdir, &block_start))) 465 return retval; 466 dirent = (struct ext2_dir_entry *) block_start; 467 prev_rec_len = 0; 468 rec_len = 0; 469 left = fs->blocksize - csum_size; 470 slack = fd->compress ? 12 : 471 ((fs->blocksize - csum_size) * ctx->htree_slack_percentage)/100; 472 if (slack < 12) 473 slack = 12; 474 for (i = 0; i < fd->num_array; i++) { 475 ent = fd->harray + i; 476 if (ent->dir->inode == 0) 477 continue; 478 rec_len = EXT2_DIR_REC_LEN(ext2fs_dirent_name_len(ent->dir)); 479 if (rec_len > left) { 480 if (left) { 481 left += prev_rec_len; 482 retval = ext2fs_set_rec_len(fs, left, dirent); 483 if (retval) 484 return retval; 485 } 486 if (csum_size) { 487 t = EXT2_DIRENT_TAIL(block_start, 488 fs->blocksize); 489 ext2fs_initialize_dirent_tail(fs, t); 490 } 491 if ((retval = get_next_block(fs, outdir, 492 &block_start))) 493 return retval; 494 offset = 0; 495 } 496 left = (fs->blocksize - csum_size) - offset; 497 dirent = (struct ext2_dir_entry *) (block_start + offset); 498 if (offset == 0) { 499 if (ent->hash == prev_hash) 500 outdir->hashes[outdir->num-1] = ent->hash | 1; 501 else 502 outdir->hashes[outdir->num-1] = ent->hash; 503 } 504 dirent->inode = ent->dir->inode; 505 ext2fs_dirent_set_name_len(dirent, 506 ext2fs_dirent_name_len(ent->dir)); 507 ext2fs_dirent_set_file_type(dirent, 508 ext2fs_dirent_file_type(ent->dir)); 509 retval = ext2fs_set_rec_len(fs, rec_len, dirent); 510 if (retval) 511 return retval; 512 prev_rec_len = rec_len; 513 memcpy(dirent->name, ent->dir->name, 514 ext2fs_dirent_name_len(dirent)); 515 offset += rec_len; 516 left -= rec_len; 517 if (left < slack) { 518 prev_rec_len += left; 519 retval = ext2fs_set_rec_len(fs, prev_rec_len, dirent); 520 if (retval) 521 return retval; 522 offset += left; 523 left = 0; 524 } 525 prev_hash = ent->hash; 526 } 527 if (left) 528 retval = ext2fs_set_rec_len(fs, rec_len + left, dirent); 529 if (csum_size) { 530 t = EXT2_DIRENT_TAIL(block_start, fs->blocksize); 531 ext2fs_initialize_dirent_tail(fs, t); 532 } 533 534 return retval; 535 } 536 537 538 static struct ext2_dx_root_info *set_root_node(ext2_filsys fs, char *buf, 539 ext2_ino_t ino, ext2_ino_t parent) 540 { 541 struct ext2_dir_entry *dir; 542 struct ext2_dx_root_info *root; 543 struct ext2_dx_countlimit *limits; 544 int filetype = 0; 545 int csum_size = 0; 546 547 if (ext2fs_has_feature_filetype(fs->super)) 548 filetype = EXT2_FT_DIR; 549 550 memset(buf, 0, fs->blocksize); 551 dir = (struct ext2_dir_entry *) buf; 552 dir->inode = ino; 553 dir->name[0] = '.'; 554 ext2fs_dirent_set_name_len(dir, 1); 555 ext2fs_dirent_set_file_type(dir, filetype); 556 dir->rec_len = 12; 557 dir = (struct ext2_dir_entry *) (buf + 12); 558 dir->inode = parent; 559 dir->name[0] = '.'; 560 dir->name[1] = '.'; 561 ext2fs_dirent_set_name_len(dir, 2); 562 ext2fs_dirent_set_file_type(dir, filetype); 563 dir->rec_len = fs->blocksize - 12; 564 565 root = (struct ext2_dx_root_info *) (buf+24); 566 root->reserved_zero = 0; 567 root->hash_version = fs->super->s_def_hash_version; 568 root->info_length = 8; 569 root->indirect_levels = 0; 570 root->unused_flags = 0; 571 572 if (ext2fs_has_feature_metadata_csum(fs->super)) 573 csum_size = sizeof(struct ext2_dx_tail); 574 575 limits = (struct ext2_dx_countlimit *) (buf+32); 576 limits->limit = (fs->blocksize - (32 + csum_size)) / 577 sizeof(struct ext2_dx_entry); 578 limits->count = 0; 579 580 return root; 581 } 582 583 584 static struct ext2_dx_entry *set_int_node(ext2_filsys fs, char *buf) 585 { 586 struct ext2_dir_entry *dir; 587 struct ext2_dx_countlimit *limits; 588 int csum_size = 0; 589 590 memset(buf, 0, fs->blocksize); 591 dir = (struct ext2_dir_entry *) buf; 592 dir->inode = 0; 593 (void) ext2fs_set_rec_len(fs, fs->blocksize, dir); 594 595 if (ext2fs_has_feature_metadata_csum(fs->super)) 596 csum_size = sizeof(struct ext2_dx_tail); 597 598 limits = (struct ext2_dx_countlimit *) (buf+8); 599 limits->limit = (fs->blocksize - (8 + csum_size)) / 600 sizeof(struct ext2_dx_entry); 601 limits->count = 0; 602 603 return (struct ext2_dx_entry *) limits; 604 } 605 606 /* 607 * This function takes the leaf nodes which have been written in 608 * outdir, and populates the root node and any necessary interior nodes. 609 */ 610 static errcode_t calculate_tree(ext2_filsys fs, 611 struct out_dir *outdir, 612 ext2_ino_t ino, 613 ext2_ino_t parent) 614 { 615 struct ext2_dx_root_info *root_info; 616 struct ext2_dx_entry *root, *dx_ent = 0; 617 struct ext2_dx_countlimit *root_limit, *limit; 618 errcode_t retval; 619 char * block_start; 620 int i, c1, c2, nblks; 621 int limit_offset, root_offset; 622 623 root_info = set_root_node(fs, outdir->buf, ino, parent); 624 root_offset = limit_offset = ((char *) root_info - outdir->buf) + 625 root_info->info_length; 626 root_limit = (struct ext2_dx_countlimit *) (outdir->buf + limit_offset); 627 c1 = root_limit->limit; 628 nblks = outdir->num; 629 630 /* Write out the pointer blocks */ 631 if (nblks-1 <= c1) { 632 /* Just write out the root block, and we're done */ 633 root = (struct ext2_dx_entry *) (outdir->buf + root_offset); 634 for (i=1; i < nblks; i++) { 635 root->block = ext2fs_cpu_to_le32(i); 636 if (i != 1) 637 root->hash = 638 ext2fs_cpu_to_le32(outdir->hashes[i]); 639 root++; 640 c1--; 641 } 642 } else { 643 c2 = 0; 644 limit = 0; 645 root_info->indirect_levels = 1; 646 for (i=1; i < nblks; i++) { 647 if (c1 == 0) 648 return ENOSPC; 649 if (c2 == 0) { 650 if (limit) 651 limit->limit = limit->count = 652 ext2fs_cpu_to_le16(limit->limit); 653 root = (struct ext2_dx_entry *) 654 (outdir->buf + root_offset); 655 root->block = ext2fs_cpu_to_le32(outdir->num); 656 if (i != 1) 657 root->hash = 658 ext2fs_cpu_to_le32(outdir->hashes[i]); 659 if ((retval = get_next_block(fs, outdir, 660 &block_start))) 661 return retval; 662 dx_ent = set_int_node(fs, block_start); 663 limit = (struct ext2_dx_countlimit *) dx_ent; 664 c2 = limit->limit; 665 root_offset += sizeof(struct ext2_dx_entry); 666 c1--; 667 } 668 dx_ent->block = ext2fs_cpu_to_le32(i); 669 if (c2 != limit->limit) 670 dx_ent->hash = 671 ext2fs_cpu_to_le32(outdir->hashes[i]); 672 dx_ent++; 673 c2--; 674 } 675 limit->count = ext2fs_cpu_to_le16(limit->limit - c2); 676 limit->limit = ext2fs_cpu_to_le16(limit->limit); 677 } 678 root_limit = (struct ext2_dx_countlimit *) (outdir->buf + limit_offset); 679 root_limit->count = ext2fs_cpu_to_le16(root_limit->limit - c1); 680 root_limit->limit = ext2fs_cpu_to_le16(root_limit->limit); 681 682 return 0; 683 } 684 685 struct write_dir_struct { 686 struct out_dir *outdir; 687 errcode_t err; 688 ext2_ino_t ino; 689 e2fsck_t ctx; 690 ext2_ino_t dir; 691 }; 692 693 /* 694 * Helper function which writes out a directory block. 695 */ 696 static int write_dir_block(ext2_filsys fs, 697 blk64_t *block_nr, 698 e2_blkcnt_t blockcnt, 699 blk64_t ref_block EXT2FS_ATTR((unused)), 700 int ref_offset EXT2FS_ATTR((unused)), 701 void *priv_data) 702 { 703 struct write_dir_struct *wd = (struct write_dir_struct *) priv_data; 704 char *dir, *buf = 0; 705 706 #ifdef REHASH_DEBUG 707 printf("%u: write_dir_block %lld:%lld", wd->ino, blockcnt, *block_nr); 708 #endif 709 if ((*block_nr == 0) || (blockcnt < 0)) { 710 #ifdef REHASH_DEBUG 711 printf(" - skip\n"); 712 #endif 713 return 0; 714 } 715 if (blockcnt < wd->outdir->num) 716 dir = wd->outdir->buf + (blockcnt * fs->blocksize); 717 else if (wd->ctx->lost_and_found == wd->dir) { 718 /* Don't release any extra directory blocks for lost+found */ 719 wd->err = ext2fs_new_dir_block(fs, 0, 0, &buf); 720 if (wd->err) 721 return BLOCK_ABORT; 722 dir = buf; 723 wd->outdir->num++; 724 } else { 725 /* Don't free blocks at the end of the directory, they 726 * will be truncated by the caller. */ 727 #ifdef REHASH_DEBUG 728 printf(" - not freed\n"); 729 #endif 730 return 0; 731 } 732 wd->err = ext2fs_write_dir_block4(fs, *block_nr, dir, 0, wd->dir); 733 if (buf) 734 ext2fs_free_mem(&buf); 735 736 #ifdef REHASH_DEBUG 737 printf(" - write (%d)\n", wd->err); 738 #endif 739 if (wd->err) 740 return BLOCK_ABORT; 741 return 0; 742 } 743 744 static errcode_t write_directory(e2fsck_t ctx, ext2_filsys fs, 745 struct out_dir *outdir, 746 ext2_ino_t ino, struct ext2_inode *inode, 747 int compress) 748 { 749 struct write_dir_struct wd; 750 errcode_t retval; 751 752 retval = e2fsck_expand_directory(ctx, ino, -1, outdir->num); 753 if (retval) 754 return retval; 755 756 wd.outdir = outdir; 757 wd.err = 0; 758 wd.ino = ino; 759 wd.ctx = ctx; 760 wd.dir = ino; 761 762 retval = ext2fs_block_iterate3(fs, ino, 0, NULL, 763 write_dir_block, &wd); 764 if (retval) 765 return retval; 766 if (wd.err) 767 return wd.err; 768 769 e2fsck_read_inode(ctx, ino, inode, "rehash_dir"); 770 if (compress) 771 inode->i_flags &= ~EXT2_INDEX_FL; 772 else 773 inode->i_flags |= EXT2_INDEX_FL; 774 #ifdef REHASH_DEBUG 775 printf("%u: set inode size to %u blocks = %u bytes\n", 776 ino, outdir->num, outdir->num * fs->blocksize); 777 #endif 778 retval = ext2fs_inode_size_set(fs, inode, (ext2_off64_t)outdir->num * 779 fs->blocksize); 780 if (retval) 781 return retval; 782 783 /* ext2fs_punch() calls ext2fs_write_inode() which writes the size */ 784 return ext2fs_punch(fs, ino, inode, NULL, outdir->num, ~0ULL); 785 } 786 787 errcode_t e2fsck_rehash_dir(e2fsck_t ctx, ext2_ino_t ino, 788 struct problem_context *pctx) 789 { 790 ext2_filsys fs = ctx->fs; 791 errcode_t retval; 792 struct ext2_inode inode; 793 char *dir_buf = 0; 794 struct fill_dir_struct fd = { NULL, NULL, 0, 0, 0, NULL, 795 0, 0, 0, 0, 0, 0 }; 796 struct out_dir outdir = { 0, 0, 0, 0 }; 797 798 e2fsck_read_inode(ctx, ino, &inode, "rehash_dir"); 799 800 if (ext2fs_has_feature_inline_data(fs->super) && 801 (inode.i_flags & EXT4_INLINE_DATA_FL)) 802 return 0; 803 804 retval = ENOMEM; 805 dir_buf = malloc(inode.i_size); 806 if (!dir_buf) 807 goto errout; 808 809 fd.max_array = inode.i_size / 32; 810 fd.harray = malloc(fd.max_array * sizeof(struct hash_entry)); 811 if (!fd.harray) 812 goto errout; 813 814 fd.ino = ino; 815 fd.ctx = ctx; 816 fd.buf = dir_buf; 817 fd.inode = &inode; 818 fd.dir = ino; 819 if (!ext2fs_has_feature_dir_index(fs->super) || 820 (inode.i_size / fs->blocksize) < 2) 821 fd.compress = 1; 822 fd.parent = 0; 823 824 retry_nohash: 825 /* Read in the entire directory into memory */ 826 retval = ext2fs_block_iterate3(fs, ino, 0, 0, 827 fill_dir_block, &fd); 828 if (fd.err) { 829 retval = fd.err; 830 goto errout; 831 } 832 833 /* 834 * If the entries read are less than a block, then don't index 835 * the directory 836 */ 837 if (!fd.compress && (fd.dir_size < (fs->blocksize - 24))) { 838 fd.compress = 1; 839 fd.dir_size = 0; 840 fd.num_array = 0; 841 goto retry_nohash; 842 } 843 844 #if 0 845 printf("%d entries (%d bytes) found in inode %d\n", 846 fd.num_array, fd.dir_size, ino); 847 #endif 848 849 /* Sort the list */ 850 resort: 851 if (fd.compress && fd.num_array > 1) 852 qsort(fd.harray+2, fd.num_array-2, sizeof(struct hash_entry), 853 hash_cmp); 854 else 855 qsort(fd.harray, fd.num_array, sizeof(struct hash_entry), 856 hash_cmp); 857 858 /* 859 * Look for duplicates 860 */ 861 if (duplicate_search_and_fix(ctx, fs, ino, &fd)) 862 goto resort; 863 864 if (ctx->options & E2F_OPT_NO) { 865 retval = 0; 866 goto errout; 867 } 868 869 /* Sort non-hashed directories by inode number */ 870 if (fd.compress && fd.num_array > 1) 871 qsort(fd.harray+2, fd.num_array-2, 872 sizeof(struct hash_entry), ino_cmp); 873 874 /* 875 * Copy the directory entries. In a htree directory these 876 * will become the leaf nodes. 877 */ 878 retval = copy_dir_entries(ctx, &fd, &outdir); 879 if (retval) 880 goto errout; 881 882 free(dir_buf); dir_buf = 0; 883 884 if (!fd.compress) { 885 /* Calculate the interior nodes */ 886 retval = calculate_tree(fs, &outdir, ino, fd.parent); 887 if (retval) 888 goto errout; 889 } 890 891 retval = write_directory(ctx, fs, &outdir, ino, &inode, fd.compress); 892 if (retval) 893 goto errout; 894 895 if (ctx->options & E2F_OPT_CONVERT_BMAP) 896 retval = e2fsck_rebuild_extents_later(ctx, ino); 897 else 898 retval = e2fsck_check_rebuild_extents(ctx, ino, &inode, pctx); 899 errout: 900 free(dir_buf); 901 free(fd.harray); 902 903 free_out_dir(&outdir); 904 return retval; 905 } 906 907 void e2fsck_rehash_directories(e2fsck_t ctx) 908 { 909 struct problem_context pctx; 910 #ifdef RESOURCE_TRACK 911 struct resource_track rtrack; 912 #endif 913 struct dir_info *dir; 914 ext2_u32_iterate iter; 915 struct dir_info_iter * dirinfo_iter = 0; 916 ext2_ino_t ino; 917 errcode_t retval; 918 int cur, max, all_dirs, first = 1; 919 920 init_resource_track(&rtrack, ctx->fs->io); 921 all_dirs = ctx->options & E2F_OPT_COMPRESS_DIRS; 922 923 if (!ctx->dirs_to_hash && !all_dirs) 924 return; 925 926 (void) e2fsck_get_lost_and_found(ctx, 0); 927 928 clear_problem_context(&pctx); 929 930 cur = 0; 931 if (all_dirs) { 932 dirinfo_iter = e2fsck_dir_info_iter_begin(ctx); 933 max = e2fsck_get_num_dirinfo(ctx); 934 } else { 935 retval = ext2fs_u32_list_iterate_begin(ctx->dirs_to_hash, 936 &iter); 937 if (retval) { 938 pctx.errcode = retval; 939 fix_problem(ctx, PR_3A_OPTIMIZE_ITER, &pctx); 940 return; 941 } 942 max = ext2fs_u32_list_count(ctx->dirs_to_hash); 943 } 944 while (1) { 945 if (all_dirs) { 946 if ((dir = e2fsck_dir_info_iter(ctx, 947 dirinfo_iter)) == 0) 948 break; 949 ino = dir->ino; 950 } else { 951 if (!ext2fs_u32_list_iterate(iter, &ino)) 952 break; 953 } 954 955 pctx.dir = ino; 956 if (first) { 957 fix_problem(ctx, PR_3A_PASS_HEADER, &pctx); 958 first = 0; 959 } 960 #if 0 961 fix_problem(ctx, PR_3A_OPTIMIZE_DIR, &pctx); 962 #endif 963 pctx.errcode = e2fsck_rehash_dir(ctx, ino, &pctx); 964 if (pctx.errcode) { 965 end_problem_latch(ctx, PR_LATCH_OPTIMIZE_DIR); 966 fix_problem(ctx, PR_3A_OPTIMIZE_DIR_ERR, &pctx); 967 } 968 if (ctx->progress && !ctx->progress_fd) 969 e2fsck_simple_progress(ctx, "Rebuilding directory", 970 100.0 * (float) (++cur) / (float) max, ino); 971 } 972 end_problem_latch(ctx, PR_LATCH_OPTIMIZE_DIR); 973 if (all_dirs) 974 e2fsck_dir_info_iter_end(ctx, dirinfo_iter); 975 else 976 ext2fs_u32_list_iterate_end(iter); 977 978 if (ctx->dirs_to_hash) 979 ext2fs_u32_list_free(ctx->dirs_to_hash); 980 ctx->dirs_to_hash = 0; 981 982 print_resource_track(ctx, "Pass 3A", &rtrack, ctx->fs->io); 983 } 984
