]> git.ipfire.org Git - thirdparty/e2fsprogs.git/blob - e2fsck/rehash.c
projects / thirdparty / e2fsprogs.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Update ext4 encryption format to final v4.1 version
[thirdparty/e2fsprogs.git] / e2fsck / rehash.c
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 struct fill_dir_struct {
75 char *buf;
76 struct ext2_inode *inode;
77 ext2_ino_t ino;
78 errcode_t err;
79 e2fsck_t ctx;
80 struct hash_entry *harray;
81 int max_array, num_array;
82 unsigned int dir_size;
83 int compress;
84 ino_t parent;
85 ext2_ino_t dir;
86 };
87
88 struct hash_entry {
89 ext2_dirhash_t hash;
90 ext2_dirhash_t minor_hash;
91 ino_t ino;
92 struct ext2_dir_entry *dir;
93 };
94
95 struct out_dir {
96 int num;
97 int max;
98 char *buf;
99 ext2_dirhash_t *hashes;
100 };
101
102 static int fill_dir_block(ext2_filsys fs,
103 blk64_t *block_nr,
104 e2_blkcnt_t blockcnt,
105 blk64_t ref_block EXT2FS_ATTR((unused)),
106 int ref_offset EXT2FS_ATTR((unused)),
107 void *priv_data)
108 {
109 struct fill_dir_struct *fd = (struct fill_dir_struct *) priv_data;
110 struct hash_entry *new_array, *ent;
111 struct ext2_dir_entry *dirent;
112 char *dir;
113 unsigned int offset, dir_offset, rec_len, name_len;
114 int hash_alg;
115
116 if (blockcnt < 0)
117 return 0;
118
119 offset = blockcnt * fs->blocksize;
120 if (offset + fs->blocksize > fd->inode->i_size) {
121 fd->err = EXT2_ET_DIR_CORRUPTED;
122 return BLOCK_ABORT;
123 }
124
125 dir = (fd->buf+offset);
126 if (*block_nr == 0) {
127 memset(dir, 0, fs->blocksize);
128 dirent = (struct ext2_dir_entry *) dir;
129 (void) ext2fs_set_rec_len(fs, fs->blocksize, dirent);
130 } else {
131 int flags = fs->flags;
132 fs->flags |= EXT2_FLAG_IGNORE_CSUM_ERRORS;
133 fd->err = ext2fs_read_dir_block4(fs, *block_nr, dir, 0,
134 fd->dir);
135 fs->flags = (flags & EXT2_FLAG_IGNORE_CSUM_ERRORS) |
136 (fs->flags & ~EXT2_FLAG_IGNORE_CSUM_ERRORS);
137 if (fd->err)
138 return BLOCK_ABORT;
139 }
140 hash_alg = fs->super->s_def_hash_version;
141 if ((hash_alg <= EXT2_HASH_TEA) &&
142 (fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH))
143 hash_alg += 3;
144 /* While the directory block is "hot", index it. */
145 dir_offset = 0;
146 while (dir_offset < fs->blocksize) {
147 dirent = (struct ext2_dir_entry *) (dir + dir_offset);
148 (void) ext2fs_get_rec_len(fs, dirent, &rec_len);
149 name_len = ext2fs_dirent_name_len(dirent);
150 if (((dir_offset + rec_len) > fs->blocksize) ||
151 (rec_len < 8) ||
152 ((rec_len % 4) != 0) ||
153 (name_len + 8 > rec_len)) {
154 fd->err = EXT2_ET_DIR_CORRUPTED;
155 return BLOCK_ABORT;
156 }
157 dir_offset += rec_len;
158 if (dirent->inode == 0)
159 continue;
160 if (!fd->compress && (name_len == 1) &&
161 (dirent->name[0] == '.'))
162 continue;
163 if (!fd->compress && (name_len == 2) &&
164 (dirent->name[0] == '.') && (dirent->name[1] == '.')) {
165 fd->parent = dirent->inode;
166 continue;
167 }
168 if (fd->num_array >= fd->max_array) {
169 new_array = realloc(fd->harray,
170 sizeof(struct hash_entry) * (fd->max_array+500));
171 if (!new_array) {
172 fd->err = ENOMEM;
173 return BLOCK_ABORT;
174 }
175 fd->harray = new_array;
176 fd->max_array += 500;
177 }
178 ent = fd->harray + fd->num_array++;
179 ent->dir = dirent;
180 fd->dir_size += EXT2_DIR_REC_LEN(name_len);
181 ent->ino = dirent->inode;
182 if (fd->compress)
183 ent->hash = ent->minor_hash = 0;
184 else {
185 fd->err = ext2fs_dirhash(hash_alg, dirent->name,
186 name_len,
187 fs->super->s_hash_seed,
188 &ent->hash, &ent->minor_hash);
189 if (fd->err)
190 return BLOCK_ABORT;
191 }
192 }
193
194 return 0;
195 }
196
197 /* Used for sorting the hash entry */
198 static EXT2_QSORT_TYPE ino_cmp(const void *a, const void *b)
199 {
200 const struct hash_entry *he_a = (const struct hash_entry *) a;
201 const struct hash_entry *he_b = (const struct hash_entry *) b;
202
203 return (he_a->ino - he_b->ino);
204 }
205
206 /* Used for sorting the hash entry */
207 static EXT2_QSORT_TYPE name_cmp(const void *a, const void *b)
208 {
209 const struct hash_entry *he_a = (const struct hash_entry *) a;
210 const struct hash_entry *he_b = (const struct hash_entry *) b;
211 unsigned int he_a_len, he_b_len;
212 int ret;
213 int min_len;
214
215 he_a_len = ext2fs_dirent_name_len(he_a->dir);
216 he_b_len = ext2fs_dirent_name_len(he_b->dir);
217 min_len = he_a_len;
218 if (min_len > he_b_len)
219 min_len = he_b_len;
220
221 ret = strncmp(he_a->dir->name, he_b->dir->name, min_len);
222 if (ret == 0) {
223 if (he_a_len > he_b_len)
224 ret = 1;
225 else if (he_a_len < he_b_len)
226 ret = -1;
227 else
228 ret = he_b->dir->inode - he_a->dir->inode;
229 }
230 return ret;
231 }
232
233 /* Used for sorting the hash entry */
234 static EXT2_QSORT_TYPE hash_cmp(const void *a, const void *b)
235 {
236 const struct hash_entry *he_a = (const struct hash_entry *) a;
237 const struct hash_entry *he_b = (const struct hash_entry *) b;
238 int ret;
239
240 if (he_a->hash > he_b->hash)
241 ret = 1;
242 else if (he_a->hash < he_b->hash)
243 ret = -1;
244 else {
245 if (he_a->minor_hash > he_b->minor_hash)
246 ret = 1;
247 else if (he_a->minor_hash < he_b->minor_hash)
248 ret = -1;
249 else
250 ret = name_cmp(a, b);
251 }
252 return ret;
253 }
254
255 static errcode_t alloc_size_dir(ext2_filsys fs, struct out_dir *outdir,
256 int blocks)
257 {
258 void *new_mem;
259
260 if (outdir->max) {
261 new_mem = realloc(outdir->buf, blocks * fs->blocksize);
262 if (!new_mem)
263 return ENOMEM;
264 outdir->buf = new_mem;
265 new_mem = realloc(outdir->hashes,
266 blocks * sizeof(ext2_dirhash_t));
267 if (!new_mem)
268 return ENOMEM;
269 outdir->hashes = new_mem;
270 } else {
271 outdir->buf = malloc(blocks * fs->blocksize);
272 outdir->hashes = malloc(blocks * sizeof(ext2_dirhash_t));
273 outdir->num = 0;
274 }
275 outdir->max = blocks;
276 return 0;
277 }
278
279 static void free_out_dir(struct out_dir *outdir)
280 {
281 free(outdir->buf);
282 free(outdir->hashes);
283 outdir->max = 0;
284 outdir->num =0;
285 }
286
287 static errcode_t get_next_block(ext2_filsys fs, struct out_dir *outdir,
288 char ** ret)
289 {
290 errcode_t retval;
291
292 if (outdir->num >= outdir->max) {
293 retval = alloc_size_dir(fs, outdir, outdir->max + 50);
294 if (retval)
295 return retval;
296 }
297 *ret = outdir->buf + (outdir->num++ * fs->blocksize);
298 memset(*ret, 0, fs->blocksize);
299 return 0;
300 }
301
302 /*
303 * This function is used to make a unique filename. We do this by
304 * appending ~0, and then incrementing the number. However, we cannot
305 * expand the length of the filename beyond the padding available in
306 * the directory entry.
307 */
308 static void mutate_name(char *str, unsigned int *len)
309 {
310 int i;
311 unsigned int l = *len;
312
313 /*
314 * First check to see if it looks the name has been mutated
315 * already
316 */
317 for (i = l-1; i > 0; i--) {
318 if (!isdigit(str[i]))
319 break;
320 }
321 if ((i == l-1) || (str[i] != '~')) {
322 if (((l-1) & 3) < 2)
323 l += 2;
324 else
325 l = (l+3) & ~3;
326 str[l-2] = '~';
327 str[l-1] = '0';
328 *len = l;
329 return;
330 }
331 for (i = l-1; i >= 0; i--) {
332 if (isdigit(str[i])) {
333 if (str[i] == '9')
334 str[i] = '0';
335 else {
336 str[i]++;
337 return;
338 }
339 continue;
340 }
341 if (i == 1) {
342 if (str[0] == 'z')
343 str[0] = 'A';
344 else if (str[0] == 'Z') {
345 str[0] = '~';
346 str[1] = '0';
347 } else
348 str[0]++;
349 } else if (i > 0) {
350 str[i] = '1';
351 str[i-1] = '~';
352 } else {
353 if (str[0] == '~')
354 str[0] = 'a';
355 else
356 str[0]++;
357 }
358 break;
359 }
360 }
361
362 static int duplicate_search_and_fix(e2fsck_t ctx, ext2_filsys fs,
363 ext2_ino_t ino,
364 struct fill_dir_struct *fd)
365 {
366 struct problem_context pctx;
367 struct hash_entry *ent, *prev;
368 int i, j;
369 int fixed = 0;
370 char new_name[256];
371 unsigned int new_len;
372 int hash_alg;
373
374 clear_problem_context(&pctx);
375 pctx.ino = ino;
376
377 hash_alg = fs->super->s_def_hash_version;
378 if ((hash_alg <= EXT2_HASH_TEA) &&
379 (fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH))
380 hash_alg += 3;
381
382 for (i=1; i < fd->num_array; i++) {
383 ent = fd->harray + i;
384 prev = ent - 1;
385 if (!ent->dir->inode ||
386 (ext2fs_dirent_name_len(ent->dir) !=
387 ext2fs_dirent_name_len(prev->dir)) ||
388 strncmp(ent->dir->name, prev->dir->name,
389 ext2fs_dirent_name_len(ent->dir)))
390 continue;
391 pctx.dirent = ent->dir;
392 if ((ent->dir->inode == prev->dir->inode) &&
393 fix_problem(ctx, PR_2_DUPLICATE_DIRENT, &pctx)) {
394 e2fsck_adjust_inode_count(ctx, ent->dir->inode, -1);
395 ent->dir->inode = 0;
396 fixed++;
397 continue;
398 }
399 new_len = ext2fs_dirent_name_len(ent->dir);
400 memcpy(new_name, ent->dir->name, new_len);
401 mutate_name(new_name, &new_len);
402 for (j=0; j < fd->num_array; j++) {
403 if ((i==j) ||
404 (new_len !=
405 ext2fs_dirent_name_len(fd->harray[j].dir)) ||
406 strncmp(new_name, fd->harray[j].dir->name, new_len))
407 continue;
408 mutate_name(new_name, &new_len);
409
410 j = -1;
411 }
412 new_name[new_len] = 0;
413 pctx.str = new_name;
414 if (fix_problem(ctx, PR_2_NON_UNIQUE_FILE, &pctx)) {
415 memcpy(ent->dir->name, new_name, new_len);
416 ext2fs_dirent_set_name_len(ent->dir, new_len);
417 ext2fs_dirhash(hash_alg, new_name, new_len,
418 fs->super->s_hash_seed,
419 &ent->hash, &ent->minor_hash);
420 fixed++;
421 }
422 }
423 return fixed;
424 }
425
426
427 static errcode_t copy_dir_entries(e2fsck_t ctx,
428 struct fill_dir_struct *fd,
429 struct out_dir *outdir)
430 {
431 ext2_filsys fs = ctx->fs;
432 errcode_t retval;
433 char *block_start;
434 struct hash_entry *ent;
435 struct ext2_dir_entry *dirent;
436 unsigned int rec_len, prev_rec_len, left, slack, offset;
437 int i;
438 ext2_dirhash_t prev_hash;
439 int csum_size = 0;
440 struct ext2_dir_entry_tail *t;
441
442 if (ctx->htree_slack_percentage == 255) {
443 profile_get_uint(ctx->profile, "options",
444 "indexed_dir_slack_percentage",
445 0, 20,
446 &ctx->htree_slack_percentage);
447 if (ctx->htree_slack_percentage > 100)
448 ctx->htree_slack_percentage = 20;
449 }
450
451 if (EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
452 EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
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 (fs->super->s_feature_incompat & EXT2_FEATURE_INCOMPAT_FILETYPE)
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 (EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
573 EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
574 csum_size = sizeof(struct ext2_dx_tail);
575
576 limits = (struct ext2_dx_countlimit *) (buf+32);
577 limits->limit = (fs->blocksize - (32 + csum_size)) /
578 sizeof(struct ext2_dx_entry);
579 limits->count = 0;
580
581 return root;
582 }
583
584
585 static struct ext2_dx_entry *set_int_node(ext2_filsys fs, char *buf)
586 {
587 struct ext2_dir_entry *dir;
588 struct ext2_dx_countlimit *limits;
589 int csum_size = 0;
590
591 memset(buf, 0, fs->blocksize);
592 dir = (struct ext2_dir_entry *) buf;
593 dir->inode = 0;
594 (void) ext2fs_set_rec_len(fs, fs->blocksize, dir);
595
596 if (EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
597 EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
598 csum_size = sizeof(struct ext2_dx_tail);
599
600 limits = (struct ext2_dx_countlimit *) (buf+8);
601 limits->limit = (fs->blocksize - (8 + csum_size)) /
602 sizeof(struct ext2_dx_entry);
603 limits->count = 0;
604
605 return (struct ext2_dx_entry *) limits;
606 }
607
608 /*
609 * This function takes the leaf nodes which have been written in
610 * outdir, and populates the root node and any necessary interior nodes.
611 */
612 static errcode_t calculate_tree(ext2_filsys fs,
613 struct out_dir *outdir,
614 ext2_ino_t ino,
615 ext2_ino_t parent)
616 {
617 struct ext2_dx_root_info *root_info;
618 struct ext2_dx_entry *root, *dx_ent = 0;
619 struct ext2_dx_countlimit *root_limit, *limit;
620 errcode_t retval;
621 char * block_start;
622 int i, c1, c2, nblks;
623 int limit_offset, root_offset;
624
625 root_info = set_root_node(fs, outdir->buf, ino, parent);
626 root_offset = limit_offset = ((char *) root_info - outdir->buf) +
627 root_info->info_length;
628 root_limit = (struct ext2_dx_countlimit *) (outdir->buf + limit_offset);
629 c1 = root_limit->limit;
630 nblks = outdir->num;
631
632 /* Write out the pointer blocks */
633 if (nblks-1 <= c1) {
634 /* Just write out the root block, and we're done */
635 root = (struct ext2_dx_entry *) (outdir->buf + root_offset);
636 for (i=1; i < nblks; i++) {
637 root->block = ext2fs_cpu_to_le32(i);
638 if (i != 1)
639 root->hash =
640 ext2fs_cpu_to_le32(outdir->hashes[i]);
641 root++;
642 c1--;
643 }
644 } else {
645 c2 = 0;
646 limit = 0;
647 root_info->indirect_levels = 1;
648 for (i=1; i < nblks; i++) {
649 if (c1 == 0)
650 return ENOSPC;
651 if (c2 == 0) {
652 if (limit)
653 limit->limit = limit->count =
654 ext2fs_cpu_to_le16(limit->limit);
655 root = (struct ext2_dx_entry *)
656 (outdir->buf + root_offset);
657 root->block = ext2fs_cpu_to_le32(outdir->num);
658 if (i != 1)
659 root->hash =
660 ext2fs_cpu_to_le32(outdir->hashes[i]);
661 if ((retval = get_next_block(fs, outdir,
662 &block_start)))
663 return retval;
664 dx_ent = set_int_node(fs, block_start);
665 limit = (struct ext2_dx_countlimit *) dx_ent;
666 c2 = limit->limit;
667 root_offset += sizeof(struct ext2_dx_entry);
668 c1--;
669 }
670 dx_ent->block = ext2fs_cpu_to_le32(i);
671 if (c2 != limit->limit)
672 dx_ent->hash =
673 ext2fs_cpu_to_le32(outdir->hashes[i]);
674 dx_ent++;
675 c2--;
676 }
677 limit->count = ext2fs_cpu_to_le16(limit->limit - c2);
678 limit->limit = ext2fs_cpu_to_le16(limit->limit);
679 }
680 root_limit = (struct ext2_dx_countlimit *) (outdir->buf + limit_offset);
681 root_limit->count = ext2fs_cpu_to_le16(root_limit->limit - c1);
682 root_limit->limit = ext2fs_cpu_to_le16(root_limit->limit);
683
684 return 0;
685 }
686
687 struct write_dir_struct {
688 struct out_dir *outdir;
689 errcode_t err;
690 e2fsck_t ctx;
691 blk64_t cleared;
692 ext2_ino_t dir;
693 };
694
695 /*
696 * Helper function which writes out a directory block.
697 */
698 static int write_dir_block(ext2_filsys fs,
699 blk64_t *block_nr,
700 e2_blkcnt_t blockcnt,
701 blk64_t ref_block EXT2FS_ATTR((unused)),
702 int ref_offset EXT2FS_ATTR((unused)),
703 void *priv_data)
704 {
705 struct write_dir_struct *wd = (struct write_dir_struct *) priv_data;
706 blk64_t blk;
707 char *dir, *buf = 0;
708
709 if (*block_nr == 0)
710 return 0;
711 if (blockcnt < 0)
712 return 0;
713 if (blockcnt < wd->outdir->num)
714 dir = wd->outdir->buf + (blockcnt * fs->blocksize);
715 else if (wd->ctx->lost_and_found == wd->dir) {
716 /* Don't release any extra directory blocks for lost+found */
717 wd->err = ext2fs_new_dir_block(fs, 0, 0, &buf);
718 if (wd->err)
719 return BLOCK_ABORT;
720 dir = buf;
721 wd->outdir->num++;
722 } else {
723 /* We don't need this block, so release it */
724 e2fsck_read_bitmaps(wd->ctx);
725 blk = *block_nr;
726 /*
727 * In theory, we only release blocks from the end of the
728 * directory file, so it's fine to clobber a whole cluster at
729 * once.
730 */
731 if (blk % EXT2FS_CLUSTER_RATIO(fs) == 0) {
732 ext2fs_block_alloc_stats2(fs, blk, -1);
733 wd->cleared++;
734 }
735 *block_nr = 0;
736 return BLOCK_CHANGED;
737 }
738
739 wd->err = ext2fs_write_dir_block4(fs, *block_nr, dir, 0, wd->dir);
740 if (buf)
741 ext2fs_free_mem(&buf);
742
743 if (wd->err)
744 return BLOCK_ABORT;
745 return 0;
746 }
747
748 static errcode_t write_directory(e2fsck_t ctx, ext2_filsys fs,
749 struct out_dir *outdir,
750 ext2_ino_t ino, struct ext2_inode *inode,
751 int compress)
752 {
753 struct write_dir_struct wd;
754 errcode_t retval;
755
756 retval = e2fsck_expand_directory(ctx, ino, -1, outdir->num);
757 if (retval)
758 return retval;
759
760 wd.outdir = outdir;
761 wd.err = 0;
762 wd.ctx = ctx;
763 wd.cleared = 0;
764 wd.dir = ino;
765
766 retval = ext2fs_block_iterate3(fs, ino, 0, 0,
767 write_dir_block, &wd);
768 if (retval)
769 return retval;
770 if (wd.err)
771 return wd.err;
772
773 e2fsck_read_inode(ctx, ino, inode, "rehash_dir");
774 if (compress)
775 inode->i_flags &= ~EXT2_INDEX_FL;
776 else
777 inode->i_flags |= EXT2_INDEX_FL;
778 retval = ext2fs_inode_size_set(fs, inode,
779 outdir->num * fs->blocksize);
780 if (retval)
781 return retval;
782 ext2fs_iblk_sub_blocks(fs, inode, wd.cleared);
783 e2fsck_write_inode(ctx, ino, inode, "rehash_dir");
784
785 return 0;
786 }
787
788 errcode_t e2fsck_rehash_dir(e2fsck_t ctx, ext2_ino_t ino,
789 struct problem_context *pctx)
790 {
791 ext2_filsys fs = ctx->fs;
792 errcode_t retval;
793 struct ext2_inode inode;
794 char *dir_buf = 0;
795 struct fill_dir_struct fd;
796 struct out_dir outdir;
797
798 outdir.max = outdir.num = 0;
799 outdir.buf = 0;
800 outdir.hashes = 0;
801 e2fsck_read_inode(ctx, ino, &inode, "rehash_dir");
802
803 if (EXT2_HAS_INCOMPAT_FEATURE(fs->super,
804 EXT4_FEATURE_INCOMPAT_INLINE_DATA) &&
805 (inode.i_flags & EXT4_INLINE_DATA_FL))
806 return 0;
807
808 retval = ENOMEM;
809 fd.harray = 0;
810 dir_buf = malloc(inode.i_size);
811 if (!dir_buf)
812 goto errout;
813
814 fd.max_array = inode.i_size / 32;
815 fd.num_array = 0;
816 fd.harray = malloc(fd.max_array * sizeof(struct hash_entry));
817 if (!fd.harray)
818 goto errout;
819
820 fd.ctx = ctx;
821 fd.buf = dir_buf;
822 fd.inode = &inode;
823 fd.ino = ino;
824 fd.err = 0;
825 fd.dir_size = 0;
826 fd.compress = 0;
827 fd.dir = ino;
828 if (!(fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_DIR_INDEX) ||
829 (inode.i_size / fs->blocksize) < 2)
830 fd.compress = 1;
831 fd.parent = 0;
832
833 retry_nohash:
834 /* Read in the entire directory into memory */
835 retval = ext2fs_block_iterate3(fs, ino, 0, 0,
836 fill_dir_block, &fd);
837 if (fd.err) {
838 retval = fd.err;
839 goto errout;
840 }
841
842 /*
843 * If the entries read are less than a block, then don't index
844 * the directory
845 */
846 if (!fd.compress && (fd.dir_size < (fs->blocksize - 24))) {
847 fd.compress = 1;
848 fd.dir_size = 0;
849 fd.num_array = 0;
850 goto retry_nohash;
851 }
852
853 #if 0
854 printf("%d entries (%d bytes) found in inode %d\n",
855 fd.num_array, fd.dir_size, ino);
856 #endif
857
858 /* Sort the list */
859 resort:
860 if (fd.compress && fd.num_array > 1)
861 qsort(fd.harray+2, fd.num_array-2, sizeof(struct hash_entry),
862 hash_cmp);
863 else
864 qsort(fd.harray, fd.num_array, sizeof(struct hash_entry),
865 hash_cmp);
866
867 /*
868 * Look for duplicates
869 */
870 if (duplicate_search_and_fix(ctx, fs, ino, &fd))
871 goto resort;
872
873 if (ctx->options & E2F_OPT_NO) {
874 retval = 0;
875 goto errout;
876 }
877
878 /* Sort non-hashed directories by inode number */
879 if (fd.compress && fd.num_array > 1)
880 qsort(fd.harray+2, fd.num_array-2,
881 sizeof(struct hash_entry), ino_cmp);
882
883 /*
884 * Copy the directory entries. In a htree directory these
885 * will become the leaf nodes.
886 */
887 retval = copy_dir_entries(ctx, &fd, &outdir);
888 if (retval)
889 goto errout;
890
891 free(dir_buf); dir_buf = 0;
892
893 if (!fd.compress) {
894 /* Calculate the interior nodes */
895 retval = calculate_tree(fs, &outdir, ino, fd.parent);
896 if (retval)
897 goto errout;
898 }
899
900 retval = write_directory(ctx, fs, &outdir, ino, &inode, fd.compress);
901 if (retval)
902 goto errout;
903
904 if (ctx->options & E2F_OPT_CONVERT_BMAP)
905 retval = e2fsck_rebuild_extents_later(ctx, ino);
906 else
907 retval = e2fsck_check_rebuild_extents(ctx, ino, &inode, pctx);
908 errout:
909 free(dir_buf);
910 free(fd.harray);
911
912 free_out_dir(&outdir);
913 return retval;
914 }
915
916 void e2fsck_rehash_directories(e2fsck_t ctx)
917 {
918 struct problem_context pctx;
919 #ifdef RESOURCE_TRACK
920 struct resource_track rtrack;
921 #endif
922 struct dir_info *dir;
923 ext2_u32_iterate iter;
924 struct dir_info_iter * dirinfo_iter = 0;
925 ext2_ino_t ino;
926 errcode_t retval;
927 int cur, max, all_dirs, first = 1;
928
929 init_resource_track(&rtrack, ctx->fs->io);
930 all_dirs = ctx->options & E2F_OPT_COMPRESS_DIRS;
931
932 if (!ctx->dirs_to_hash && !all_dirs)
933 return;
934
935 (void) e2fsck_get_lost_and_found(ctx, 0);
936
937 clear_problem_context(&pctx);
938
939 cur = 0;
940 if (all_dirs) {
941 dirinfo_iter = e2fsck_dir_info_iter_begin(ctx);
942 max = e2fsck_get_num_dirinfo(ctx);
943 } else {
944 retval = ext2fs_u32_list_iterate_begin(ctx->dirs_to_hash,
945 &iter);
946 if (retval) {
947 pctx.errcode = retval;
948 fix_problem(ctx, PR_3A_OPTIMIZE_ITER, &pctx);
949 return;
950 }
951 max = ext2fs_u32_list_count(ctx->dirs_to_hash);
952 }
953 while (1) {
954 if (all_dirs) {
955 if ((dir = e2fsck_dir_info_iter(ctx,
956 dirinfo_iter)) == 0)
957 break;
958 ino = dir->ino;
959 } else {
960 if (!ext2fs_u32_list_iterate(iter, &ino))
961 break;
962 }
963
964 pctx.dir = ino;
965 if (first) {
966 fix_problem(ctx, PR_3A_PASS_HEADER, &pctx);
967 first = 0;
968 }
969 #if 0
970 fix_problem(ctx, PR_3A_OPTIMIZE_DIR, &pctx);
971 #endif
972 pctx.errcode = e2fsck_rehash_dir(ctx, ino, &pctx);
973 if (pctx.errcode) {
974 end_problem_latch(ctx, PR_LATCH_OPTIMIZE_DIR);
975 fix_problem(ctx, PR_3A_OPTIMIZE_DIR_ERR, &pctx);
976 }
977 if (ctx->progress && !ctx->progress_fd)
978 e2fsck_simple_progress(ctx, "Rebuilding directory",
979 100.0 * (float) (++cur) / (float) max, ino);
980 }
981 end_problem_latch(ctx, PR_LATCH_OPTIMIZE_DIR);
982 if (all_dirs)
983 e2fsck_dir_info_iter_end(ctx, dirinfo_iter);
984 else
985 ext2fs_u32_list_iterate_end(iter);
986
987 if (ctx->dirs_to_hash)
988 ext2fs_u32_list_free(ctx->dirs_to_hash);
989 ctx->dirs_to_hash = 0;
990
991 print_resource_track(ctx, "Pass 3A", &rtrack, ctx->fs->io);
992 }
Unnamed repository; edit this file 'description' to name the repository.