]>
Commit | Line | Data |
---|---|---|
b7a00563 TT |
1 | /* |
2 | * rehash.c --- rebuild hash tree directories | |
efc6f628 | 3 | * |
b7a00563 TT |
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% | |
efc6f628 | 10 | * |
b7a00563 TT |
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 | |
efc6f628 | 39 | * |
b7a00563 TT |
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 | ||
d1154eb4 | 48 | #include "config.h" |
520ead37 TT |
49 | #include <string.h> |
50 | #include <ctype.h> | |
b7a00563 TT |
51 | #include <errno.h> |
52 | #include "e2fsck.h" | |
53 | #include "problem.h" | |
54 | ||
55 | struct fill_dir_struct { | |
56 | char *buf; | |
57 | struct ext2_inode *inode; | |
974d57d3 | 58 | errcode_t err; |
b7a00563 TT |
59 | e2fsck_t ctx; |
60 | struct hash_entry *harray; | |
61 | int max_array, num_array; | |
68477355 | 62 | unsigned int dir_size; |
850d05e9 | 63 | int compress; |
b7a00563 TT |
64 | ino_t parent; |
65 | }; | |
66 | ||
67 | struct hash_entry { | |
68 | ext2_dirhash_t hash; | |
69 | ext2_dirhash_t minor_hash; | |
d66c3832 | 70 | ino_t ino; |
b7a00563 TT |
71 | struct ext2_dir_entry *dir; |
72 | }; | |
73 | ||
74 | struct out_dir { | |
75 | int num; | |
76 | int max; | |
77 | char *buf; | |
78 | ext2_dirhash_t *hashes; | |
79 | }; | |
80 | ||
81 | static int fill_dir_block(ext2_filsys fs, | |
6dc64392 | 82 | blk64_t *block_nr, |
b7a00563 | 83 | e2_blkcnt_t blockcnt, |
6dc64392 | 84 | blk64_t ref_block EXT2FS_ATTR((unused)), |
54434927 | 85 | int ref_offset EXT2FS_ATTR((unused)), |
b7a00563 TT |
86 | void *priv_data) |
87 | { | |
88 | struct fill_dir_struct *fd = (struct fill_dir_struct *) priv_data; | |
89 | struct hash_entry *new_array, *ent; | |
90 | struct ext2_dir_entry *dirent; | |
91 | char *dir; | |
8a480350 TT |
92 | unsigned int offset, dir_offset, rec_len; |
93 | int hash_alg; | |
efc6f628 | 94 | |
b7a00563 TT |
95 | if (blockcnt < 0) |
96 | return 0; | |
97 | ||
98 | offset = blockcnt * fs->blocksize; | |
99 | if (offset + fs->blocksize > fd->inode->i_size) { | |
100 | fd->err = EXT2_ET_DIR_CORRUPTED; | |
101 | return BLOCK_ABORT; | |
102 | } | |
103 | dir = (fd->buf+offset); | |
104 | if (HOLE_BLKADDR(*block_nr)) { | |
105 | memset(dir, 0, fs->blocksize); | |
106 | dirent = (struct ext2_dir_entry *) dir; | |
8a480350 | 107 | (void) ext2fs_set_rec_len(fs, fs->blocksize, dirent); |
b7a00563 | 108 | } else { |
6dc64392 | 109 | fd->err = ext2fs_read_dir_block3(fs, *block_nr, dir, 0); |
b7a00563 TT |
110 | if (fd->err) |
111 | return BLOCK_ABORT; | |
112 | } | |
f77704e4 TT |
113 | hash_alg = fs->super->s_def_hash_version; |
114 | if ((hash_alg <= EXT2_HASH_TEA) && | |
115 | (fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH)) | |
116 | hash_alg += 3; | |
b7a00563 TT |
117 | /* While the directory block is "hot", index it. */ |
118 | dir_offset = 0; | |
119 | while (dir_offset < fs->blocksize) { | |
120 | dirent = (struct ext2_dir_entry *) (dir + dir_offset); | |
8a480350 | 121 | (void) ext2fs_get_rec_len(fs, dirent, &rec_len); |
5dd77dbe TT |
122 | if (((dir_offset + rec_len) > fs->blocksize) || |
123 | (rec_len < 8) || | |
124 | ((rec_len % 4) != 0) || | |
68477355 | 125 | (((dirent->name_len & 0xFF)+8U) > rec_len)) { |
b7a00563 TT |
126 | fd->err = EXT2_ET_DIR_CORRUPTED; |
127 | return BLOCK_ABORT; | |
128 | } | |
5dd77dbe | 129 | dir_offset += rec_len; |
b7a00563 | 130 | if (dirent->inode == 0) |
850d05e9 TT |
131 | continue; |
132 | if (!fd->compress && ((dirent->name_len&0xFF) == 1) && | |
133 | (dirent->name[0] == '.')) | |
134 | continue; | |
135 | if (!fd->compress && ((dirent->name_len&0xFF) == 2) && | |
b7a00563 TT |
136 | (dirent->name[0] == '.') && (dirent->name[1] == '.')) { |
137 | fd->parent = dirent->inode; | |
850d05e9 | 138 | continue; |
b7a00563 TT |
139 | } |
140 | if (fd->num_array >= fd->max_array) { | |
141 | new_array = realloc(fd->harray, | |
142 | sizeof(struct hash_entry) * (fd->max_array+500)); | |
143 | if (!new_array) { | |
144 | fd->err = ENOMEM; | |
145 | return BLOCK_ABORT; | |
146 | } | |
147 | fd->harray = new_array; | |
148 | fd->max_array += 500; | |
149 | } | |
850d05e9 | 150 | ent = fd->harray + fd->num_array++; |
b7a00563 | 151 | ent->dir = dirent; |
b7a00563 | 152 | fd->dir_size += EXT2_DIR_REC_LEN(dirent->name_len & 0xFF); |
d66c3832 | 153 | ent->ino = dirent->inode; |
850d05e9 TT |
154 | if (fd->compress) |
155 | ent->hash = ent->minor_hash = 0; | |
156 | else { | |
f77704e4 | 157 | fd->err = ext2fs_dirhash(hash_alg, dirent->name, |
850d05e9 TT |
158 | dirent->name_len & 0xFF, |
159 | fs->super->s_hash_seed, | |
160 | &ent->hash, &ent->minor_hash); | |
161 | if (fd->err) | |
162 | return BLOCK_ABORT; | |
163 | } | |
b7a00563 | 164 | } |
efc6f628 | 165 | |
b7a00563 TT |
166 | return 0; |
167 | } | |
168 | ||
d66c3832 TT |
169 | /* Used for sorting the hash entry */ |
170 | static EXT2_QSORT_TYPE ino_cmp(const void *a, const void *b) | |
171 | { | |
172 | const struct hash_entry *he_a = (const struct hash_entry *) a; | |
173 | const struct hash_entry *he_b = (const struct hash_entry *) b; | |
174 | ||
175 | return (he_a->ino - he_b->ino); | |
176 | } | |
177 | ||
b7a00563 | 178 | /* Used for sorting the hash entry */ |
b0700a1b | 179 | static EXT2_QSORT_TYPE name_cmp(const void *a, const void *b) |
b7a00563 TT |
180 | { |
181 | const struct hash_entry *he_a = (const struct hash_entry *) a; | |
182 | const struct hash_entry *he_b = (const struct hash_entry *) b; | |
183 | int ret; | |
b0700a1b TT |
184 | int min_len; |
185 | ||
186 | min_len = he_a->dir->name_len; | |
187 | if (min_len > he_b->dir->name_len) | |
188 | min_len = he_b->dir->name_len; | |
189 | ||
190 | ret = strncmp(he_a->dir->name, he_b->dir->name, min_len); | |
191 | if (ret == 0) { | |
192 | if (he_a->dir->name_len > he_b->dir->name_len) | |
b7a00563 | 193 | ret = 1; |
b0700a1b | 194 | else if (he_a->dir->name_len < he_b->dir->name_len) |
b7a00563 TT |
195 | ret = -1; |
196 | else | |
12dd69f5 | 197 | ret = he_b->dir->inode - he_a->dir->inode; |
b7a00563 TT |
198 | } |
199 | return ret; | |
200 | } | |
201 | ||
850d05e9 | 202 | /* Used for sorting the hash entry */ |
b0700a1b | 203 | static EXT2_QSORT_TYPE hash_cmp(const void *a, const void *b) |
850d05e9 TT |
204 | { |
205 | const struct hash_entry *he_a = (const struct hash_entry *) a; | |
206 | const struct hash_entry *he_b = (const struct hash_entry *) b; | |
207 | int ret; | |
efc6f628 | 208 | |
b0700a1b TT |
209 | if (he_a->hash > he_b->hash) |
210 | ret = 1; | |
211 | else if (he_a->hash < he_b->hash) | |
212 | ret = -1; | |
213 | else { | |
214 | if (he_a->minor_hash > he_b->minor_hash) | |
850d05e9 | 215 | ret = 1; |
b0700a1b | 216 | else if (he_a->minor_hash < he_b->minor_hash) |
850d05e9 TT |
217 | ret = -1; |
218 | else | |
b0700a1b | 219 | ret = name_cmp(a, b); |
850d05e9 TT |
220 | } |
221 | return ret; | |
222 | } | |
223 | ||
efc6f628 | 224 | static errcode_t alloc_size_dir(ext2_filsys fs, struct out_dir *outdir, |
b7a00563 TT |
225 | int blocks) |
226 | { | |
227 | void *new_mem; | |
228 | ||
229 | if (outdir->max) { | |
230 | new_mem = realloc(outdir->buf, blocks * fs->blocksize); | |
231 | if (!new_mem) | |
232 | return ENOMEM; | |
233 | outdir->buf = new_mem; | |
234 | new_mem = realloc(outdir->hashes, | |
235 | blocks * sizeof(ext2_dirhash_t)); | |
236 | if (!new_mem) | |
237 | return ENOMEM; | |
238 | outdir->hashes = new_mem; | |
239 | } else { | |
240 | outdir->buf = malloc(blocks * fs->blocksize); | |
241 | outdir->hashes = malloc(blocks * sizeof(ext2_dirhash_t)); | |
242 | outdir->num = 0; | |
243 | } | |
244 | outdir->max = blocks; | |
245 | return 0; | |
246 | } | |
247 | ||
248 | static void free_out_dir(struct out_dir *outdir) | |
249 | { | |
45e338f5 JM |
250 | free(outdir->buf); |
251 | free(outdir->hashes); | |
b7a00563 TT |
252 | outdir->max = 0; |
253 | outdir->num =0; | |
254 | } | |
255 | ||
850d05e9 | 256 | static errcode_t get_next_block(ext2_filsys fs, struct out_dir *outdir, |
b7a00563 TT |
257 | char ** ret) |
258 | { | |
259 | errcode_t retval; | |
260 | ||
261 | if (outdir->num >= outdir->max) { | |
262 | retval = alloc_size_dir(fs, outdir, outdir->max + 50); | |
263 | if (retval) | |
264 | return retval; | |
265 | } | |
266 | *ret = outdir->buf + (outdir->num++ * fs->blocksize); | |
850d05e9 | 267 | memset(*ret, 0, fs->blocksize); |
b7a00563 TT |
268 | return 0; |
269 | } | |
270 | ||
b0700a1b TT |
271 | /* |
272 | * This function is used to make a unique filename. We do this by | |
273 | * appending ~0, and then incrementing the number. However, we cannot | |
274 | * expand the length of the filename beyond the padding available in | |
275 | * the directory entry. | |
276 | */ | |
277 | static void mutate_name(char *str, __u16 *len) | |
278 | { | |
279 | int i; | |
280 | __u16 l = *len & 0xFF, h = *len & 0xff00; | |
efc6f628 | 281 | |
b0700a1b TT |
282 | /* |
283 | * First check to see if it looks the name has been mutated | |
284 | * already | |
285 | */ | |
286 | for (i = l-1; i > 0; i--) { | |
287 | if (!isdigit(str[i])) | |
288 | break; | |
289 | } | |
290 | if ((i == l-1) || (str[i] != '~')) { | |
291 | if (((l-1) & 3) < 2) | |
292 | l += 2; | |
293 | else | |
294 | l = (l+3) & ~3; | |
295 | str[l-2] = '~'; | |
296 | str[l-1] = '0'; | |
297 | *len = l | h; | |
298 | return; | |
299 | } | |
300 | for (i = l-1; i >= 0; i--) { | |
301 | if (isdigit(str[i])) { | |
302 | if (str[i] == '9') | |
303 | str[i] = '0'; | |
304 | else { | |
305 | str[i]++; | |
306 | return; | |
307 | } | |
308 | continue; | |
309 | } | |
310 | if (i == 1) { | |
311 | if (str[0] == 'z') | |
312 | str[0] = 'A'; | |
313 | else if (str[0] == 'Z') { | |
314 | str[0] = '~'; | |
315 | str[1] = '0'; | |
316 | } else | |
317 | str[0]++; | |
318 | } else if (i > 0) { | |
319 | str[i] = '1'; | |
320 | str[i-1] = '~'; | |
321 | } else { | |
322 | if (str[0] == '~') | |
323 | str[0] = 'a'; | |
efc6f628 | 324 | else |
b0700a1b TT |
325 | str[0]++; |
326 | } | |
327 | break; | |
328 | } | |
329 | } | |
330 | ||
331 | static int duplicate_search_and_fix(e2fsck_t ctx, ext2_filsys fs, | |
332 | ext2_ino_t ino, | |
333 | struct fill_dir_struct *fd) | |
334 | { | |
335 | struct problem_context pctx; | |
336 | struct hash_entry *ent, *prev; | |
337 | int i, j; | |
338 | int fixed = 0; | |
339 | char new_name[256]; | |
340 | __u16 new_len; | |
f77704e4 | 341 | int hash_alg; |
efc6f628 | 342 | |
b0700a1b TT |
343 | clear_problem_context(&pctx); |
344 | pctx.ino = ino; | |
345 | ||
f77704e4 TT |
346 | hash_alg = fs->super->s_def_hash_version; |
347 | if ((hash_alg <= EXT2_HASH_TEA) && | |
348 | (fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH)) | |
349 | hash_alg += 3; | |
350 | ||
b0700a1b TT |
351 | for (i=1; i < fd->num_array; i++) { |
352 | ent = fd->harray + i; | |
353 | prev = ent - 1; | |
354 | if (!ent->dir->inode || | |
355 | ((ent->dir->name_len & 0xFF) != | |
356 | (prev->dir->name_len & 0xFF)) || | |
357 | (strncmp(ent->dir->name, prev->dir->name, | |
358 | ent->dir->name_len & 0xFF))) | |
359 | continue; | |
360 | pctx.dirent = ent->dir; | |
361 | if ((ent->dir->inode == prev->dir->inode) && | |
362 | fix_problem(ctx, PR_2_DUPLICATE_DIRENT, &pctx)) { | |
363 | e2fsck_adjust_inode_count(ctx, ent->dir->inode, -1); | |
364 | ent->dir->inode = 0; | |
365 | fixed++; | |
366 | continue; | |
367 | } | |
368 | memcpy(new_name, ent->dir->name, ent->dir->name_len & 0xFF); | |
369 | new_len = ent->dir->name_len; | |
370 | mutate_name(new_name, &new_len); | |
371 | for (j=0; j < fd->num_array; j++) { | |
372 | if ((i==j) || | |
32d4eb2b | 373 | ((new_len & 0xFF) != |
b0700a1b TT |
374 | (fd->harray[j].dir->name_len & 0xFF)) || |
375 | (strncmp(new_name, fd->harray[j].dir->name, | |
376 | new_len & 0xFF))) | |
377 | continue; | |
378 | mutate_name(new_name, &new_len); | |
efc6f628 | 379 | |
b0700a1b TT |
380 | j = -1; |
381 | } | |
382 | new_name[new_len & 0xFF] = 0; | |
383 | pctx.str = new_name; | |
384 | if (fix_problem(ctx, PR_2_NON_UNIQUE_FILE, &pctx)) { | |
385 | memcpy(ent->dir->name, new_name, new_len & 0xFF); | |
386 | ent->dir->name_len = new_len; | |
f77704e4 | 387 | ext2fs_dirhash(hash_alg, ent->dir->name, |
b0700a1b TT |
388 | ent->dir->name_len & 0xFF, |
389 | fs->super->s_hash_seed, | |
390 | &ent->hash, &ent->minor_hash); | |
391 | fixed++; | |
392 | } | |
393 | } | |
394 | return fixed; | |
395 | } | |
396 | ||
b7a00563 | 397 | |
7dca4c88 | 398 | static errcode_t copy_dir_entries(e2fsck_t ctx, |
850d05e9 TT |
399 | struct fill_dir_struct *fd, |
400 | struct out_dir *outdir) | |
401 | { | |
7dca4c88 | 402 | ext2_filsys fs = ctx->fs; |
850d05e9 TT |
403 | errcode_t retval; |
404 | char *block_start; | |
405 | struct hash_entry *ent; | |
406 | struct ext2_dir_entry *dirent; | |
68477355 TT |
407 | unsigned int rec_len, prev_rec_len, left, slack, offset; |
408 | int i; | |
850d05e9 | 409 | ext2_dirhash_t prev_hash; |
7dca4c88 TT |
410 | |
411 | if (ctx->htree_slack_percentage == 255) { | |
412 | profile_get_uint(ctx->profile, "options", | |
413 | "indexed_dir_slack_percentage", | |
414 | 0, 20, | |
415 | &ctx->htree_slack_percentage); | |
416 | if (ctx->htree_slack_percentage > 100) | |
417 | ctx->htree_slack_percentage = 20; | |
418 | } | |
efc6f628 | 419 | |
850d05e9 TT |
420 | outdir->max = 0; |
421 | retval = alloc_size_dir(fs, outdir, | |
422 | (fd->dir_size / fs->blocksize) + 2); | |
423 | if (retval) | |
424 | return retval; | |
425 | outdir->num = fd->compress ? 0 : 1; | |
426 | offset = 0; | |
427 | outdir->hashes[0] = 0; | |
428 | prev_hash = 1; | |
429 | if ((retval = get_next_block(fs, outdir, &block_start))) | |
430 | return retval; | |
431 | dirent = (struct ext2_dir_entry *) block_start; | |
8a480350 | 432 | prev_rec_len = 0; |
cf5301d7 | 433 | rec_len = 0; |
850d05e9 | 434 | left = fs->blocksize; |
7dca4c88 TT |
435 | slack = fd->compress ? 12 : |
436 | (fs->blocksize * ctx->htree_slack_percentage)/100; | |
437 | if (slack < 12) | |
438 | slack = 12; | |
cf5301d7 | 439 | for (i = 0; i < fd->num_array; i++) { |
850d05e9 | 440 | ent = fd->harray + i; |
b0700a1b TT |
441 | if (ent->dir->inode == 0) |
442 | continue; | |
850d05e9 | 443 | rec_len = EXT2_DIR_REC_LEN(ent->dir->name_len & 0xFF); |
850d05e9 | 444 | if (rec_len > left) { |
8a480350 TT |
445 | if (left) { |
446 | left += prev_rec_len; | |
447 | retval = ext2fs_set_rec_len(fs, left, dirent); | |
448 | if (retval) | |
449 | return retval; | |
450 | } | |
850d05e9 TT |
451 | if ((retval = get_next_block(fs, outdir, |
452 | &block_start))) | |
453 | return retval; | |
fe5b72d1 | 454 | offset = 0; |
850d05e9 | 455 | } |
fe5b72d1 TT |
456 | left = fs->blocksize - offset; |
457 | dirent = (struct ext2_dir_entry *) (block_start + offset); | |
850d05e9 TT |
458 | if (offset == 0) { |
459 | if (ent->hash == prev_hash) | |
460 | outdir->hashes[outdir->num-1] = ent->hash | 1; | |
461 | else | |
462 | outdir->hashes[outdir->num-1] = ent->hash; | |
463 | } | |
464 | dirent->inode = ent->dir->inode; | |
465 | dirent->name_len = ent->dir->name_len; | |
8a480350 TT |
466 | retval = ext2fs_set_rec_len(fs, rec_len, dirent); |
467 | if (retval) | |
468 | return retval; | |
469 | prev_rec_len = rec_len; | |
850d05e9 TT |
470 | memcpy(dirent->name, ent->dir->name, dirent->name_len & 0xFF); |
471 | offset += rec_len; | |
472 | left -= rec_len; | |
7dca4c88 | 473 | if (left < slack) { |
8a480350 TT |
474 | prev_rec_len += left; |
475 | retval = ext2fs_set_rec_len(fs, prev_rec_len, dirent); | |
476 | if (retval) | |
477 | return retval; | |
850d05e9 | 478 | offset += left; |
cf3909ed | 479 | left = 0; |
850d05e9 TT |
480 | } |
481 | prev_hash = ent->hash; | |
482 | } | |
483 | if (left) | |
8a480350 | 484 | retval = ext2fs_set_rec_len(fs, rec_len + left, dirent); |
850d05e9 | 485 | |
8a480350 | 486 | return retval; |
850d05e9 TT |
487 | } |
488 | ||
489 | ||
490 | static struct ext2_dx_root_info *set_root_node(ext2_filsys fs, char *buf, | |
b7a00563 TT |
491 | ext2_ino_t ino, ext2_ino_t parent) |
492 | { | |
493 | struct ext2_dir_entry *dir; | |
494 | struct ext2_dx_root_info *root; | |
495 | struct ext2_dx_countlimit *limits; | |
850d05e9 | 496 | int filetype = 0; |
b7a00563 TT |
497 | |
498 | if (fs->super->s_feature_incompat & EXT2_FEATURE_INCOMPAT_FILETYPE) | |
499 | filetype = EXT2_FT_DIR << 8; | |
efc6f628 | 500 | |
b7a00563 TT |
501 | memset(buf, 0, fs->blocksize); |
502 | dir = (struct ext2_dir_entry *) buf; | |
503 | dir->inode = ino; | |
504 | dir->name[0] = '.'; | |
505 | dir->name_len = 1 | filetype; | |
506 | dir->rec_len = 12; | |
507 | dir = (struct ext2_dir_entry *) (buf + 12); | |
508 | dir->inode = parent; | |
509 | dir->name[0] = '.'; | |
510 | dir->name[1] = '.'; | |
511 | dir->name_len = 2 | filetype; | |
512 | dir->rec_len = fs->blocksize - 12; | |
efc6f628 | 513 | |
b7a00563 TT |
514 | root = (struct ext2_dx_root_info *) (buf+24); |
515 | root->reserved_zero = 0; | |
516 | root->hash_version = fs->super->s_def_hash_version; | |
517 | root->info_length = 8; | |
518 | root->indirect_levels = 0; | |
519 | root->unused_flags = 0; | |
520 | ||
521 | limits = (struct ext2_dx_countlimit *) (buf+32); | |
522 | limits->limit = (fs->blocksize - 32) / sizeof(struct ext2_dx_entry); | |
523 | limits->count = 0; | |
524 | ||
525 | return root; | |
526 | } | |
527 | ||
528 | ||
850d05e9 | 529 | static struct ext2_dx_entry *set_int_node(ext2_filsys fs, char *buf) |
b7a00563 TT |
530 | { |
531 | struct ext2_dir_entry *dir; | |
532 | struct ext2_dx_countlimit *limits; | |
533 | ||
534 | memset(buf, 0, fs->blocksize); | |
535 | dir = (struct ext2_dir_entry *) buf; | |
536 | dir->inode = 0; | |
8a480350 | 537 | (void) ext2fs_set_rec_len(fs, fs->blocksize, dir); |
efc6f628 | 538 | |
b7a00563 TT |
539 | limits = (struct ext2_dx_countlimit *) (buf+8); |
540 | limits->limit = (fs->blocksize - 8) / sizeof(struct ext2_dx_entry); | |
541 | limits->count = 0; | |
542 | ||
543 | return (struct ext2_dx_entry *) limits; | |
544 | } | |
545 | ||
850d05e9 TT |
546 | /* |
547 | * This function takes the leaf nodes which have been written in | |
548 | * outdir, and populates the root node and any necessary interior nodes. | |
549 | */ | |
550 | static errcode_t calculate_tree(ext2_filsys fs, | |
551 | struct out_dir *outdir, | |
552 | ext2_ino_t ino, | |
553 | ext2_ino_t parent) | |
554 | { | |
555 | struct ext2_dx_root_info *root_info; | |
556 | struct ext2_dx_entry *root, *dx_ent = 0; | |
557 | struct ext2_dx_countlimit *root_limit, *limit; | |
558 | errcode_t retval; | |
559 | char * block_start; | |
560 | int i, c1, c2, nblks; | |
561 | int limit_offset, root_offset; | |
efc6f628 | 562 | |
850d05e9 TT |
563 | root_info = set_root_node(fs, outdir->buf, ino, parent); |
564 | root_offset = limit_offset = ((char *) root_info - outdir->buf) + | |
565 | root_info->info_length; | |
566 | root_limit = (struct ext2_dx_countlimit *) (outdir->buf + limit_offset); | |
567 | c1 = root_limit->limit; | |
568 | nblks = outdir->num; | |
569 | ||
570 | /* Write out the pointer blocks */ | |
571 | if (nblks-1 <= c1) { | |
572 | /* Just write out the root block, and we're done */ | |
573 | root = (struct ext2_dx_entry *) (outdir->buf + root_offset); | |
574 | for (i=1; i < nblks; i++) { | |
575 | root->block = ext2fs_cpu_to_le32(i); | |
576 | if (i != 1) | |
577 | root->hash = | |
578 | ext2fs_cpu_to_le32(outdir->hashes[i]); | |
579 | root++; | |
580 | c1--; | |
581 | } | |
582 | } else { | |
583 | c2 = 0; | |
584 | limit = 0; | |
585 | root_info->indirect_levels = 1; | |
586 | for (i=1; i < nblks; i++) { | |
587 | if (c1 == 0) | |
588 | return ENOSPC; | |
589 | if (c2 == 0) { | |
590 | if (limit) | |
efc6f628 | 591 | limit->limit = limit->count = |
850d05e9 TT |
592 | ext2fs_cpu_to_le16(limit->limit); |
593 | root = (struct ext2_dx_entry *) | |
594 | (outdir->buf + root_offset); | |
595 | root->block = ext2fs_cpu_to_le32(outdir->num); | |
596 | if (i != 1) | |
597 | root->hash = | |
598 | ext2fs_cpu_to_le32(outdir->hashes[i]); | |
599 | if ((retval = get_next_block(fs, outdir, | |
600 | &block_start))) | |
601 | return retval; | |
602 | dx_ent = set_int_node(fs, block_start); | |
603 | limit = (struct ext2_dx_countlimit *) dx_ent; | |
604 | c2 = limit->limit; | |
605 | root_offset += sizeof(struct ext2_dx_entry); | |
606 | c1--; | |
607 | } | |
608 | dx_ent->block = ext2fs_cpu_to_le32(i); | |
609 | if (c2 != limit->limit) | |
610 | dx_ent->hash = | |
611 | ext2fs_cpu_to_le32(outdir->hashes[i]); | |
612 | dx_ent++; | |
613 | c2--; | |
614 | } | |
615 | limit->count = ext2fs_cpu_to_le16(limit->limit - c2); | |
616 | limit->limit = ext2fs_cpu_to_le16(limit->limit); | |
617 | } | |
618 | root_limit = (struct ext2_dx_countlimit *) (outdir->buf + limit_offset); | |
619 | root_limit->count = ext2fs_cpu_to_le16(root_limit->limit - c1); | |
620 | root_limit->limit = ext2fs_cpu_to_le16(root_limit->limit); | |
621 | ||
622 | return 0; | |
623 | } | |
b7a00563 TT |
624 | |
625 | struct write_dir_struct { | |
626 | struct out_dir *outdir; | |
627 | errcode_t err; | |
628 | e2fsck_t ctx; | |
4dbfd79d | 629 | blk64_t cleared; |
b7a00563 TT |
630 | }; |
631 | ||
632 | /* | |
850d05e9 | 633 | * Helper function which writes out a directory block. |
b7a00563 TT |
634 | */ |
635 | static int write_dir_block(ext2_filsys fs, | |
6dc64392 | 636 | blk64_t *block_nr, |
b7a00563 | 637 | e2_blkcnt_t blockcnt, |
6dc64392 | 638 | blk64_t ref_block EXT2FS_ATTR((unused)), |
efc6f628 | 639 | int ref_offset EXT2FS_ATTR((unused)), |
b7a00563 TT |
640 | void *priv_data) |
641 | { | |
642 | struct write_dir_struct *wd = (struct write_dir_struct *) priv_data; | |
6dc64392 | 643 | blk64_t blk; |
b7a00563 | 644 | char *dir; |
b7a00563 TT |
645 | |
646 | if (*block_nr == 0) | |
647 | return 0; | |
648 | if (blockcnt >= wd->outdir->num) { | |
649 | e2fsck_read_bitmaps(wd->ctx); | |
650 | blk = *block_nr; | |
5797cb01 DW |
651 | /* |
652 | * In theory, we only release blocks from the end of the | |
653 | * directory file, so it's fine to clobber a whole cluster at | |
654 | * once. | |
655 | */ | |
656 | if (blk % EXT2FS_CLUSTER_RATIO(fs) == 0) { | |
657 | ext2fs_unmark_block_bitmap2(wd->ctx->block_found_map, | |
658 | blk); | |
659 | ext2fs_block_alloc_stats2(fs, blk, -1); | |
660 | wd->cleared++; | |
661 | } | |
b7a00563 | 662 | *block_nr = 0; |
b7a00563 TT |
663 | return BLOCK_CHANGED; |
664 | } | |
665 | if (blockcnt < 0) | |
666 | return 0; | |
667 | ||
668 | dir = wd->outdir->buf + (blockcnt * fs->blocksize); | |
6dc64392 | 669 | wd->err = ext2fs_write_dir_block3(fs, *block_nr, dir, 0); |
b7a00563 TT |
670 | if (wd->err) |
671 | return BLOCK_ABORT; | |
672 | return 0; | |
673 | } | |
674 | ||
b7a00563 | 675 | static errcode_t write_directory(e2fsck_t ctx, ext2_filsys fs, |
850d05e9 TT |
676 | struct out_dir *outdir, |
677 | ext2_ino_t ino, int compress) | |
b7a00563 TT |
678 | { |
679 | struct write_dir_struct wd; | |
680 | errcode_t retval; | |
681 | struct ext2_inode inode; | |
682 | ||
683 | retval = e2fsck_expand_directory(ctx, ino, -1, outdir->num); | |
684 | if (retval) | |
685 | return retval; | |
686 | ||
687 | wd.outdir = outdir; | |
688 | wd.err = 0; | |
689 | wd.ctx = ctx; | |
690 | wd.cleared = 0; | |
691 | ||
6dc64392 | 692 | retval = ext2fs_block_iterate3(fs, ino, 0, 0, |
b7a00563 TT |
693 | write_dir_block, &wd); |
694 | if (retval) | |
695 | return retval; | |
696 | if (wd.err) | |
697 | return wd.err; | |
698 | ||
699 | e2fsck_read_inode(ctx, ino, &inode, "rehash_dir"); | |
e70ae99e TT |
700 | if (compress) |
701 | inode.i_flags &= ~EXT2_INDEX_FL; | |
702 | else | |
850d05e9 | 703 | inode.i_flags |= EXT2_INDEX_FL; |
b7a00563 | 704 | inode.i_size = outdir->num * fs->blocksize; |
1ca1059f | 705 | ext2fs_iblk_sub_blocks(fs, &inode, wd.cleared); |
b7a00563 TT |
706 | e2fsck_write_inode(ctx, ino, &inode, "rehash_dir"); |
707 | ||
708 | return 0; | |
709 | } | |
710 | ||
711 | errcode_t e2fsck_rehash_dir(e2fsck_t ctx, ext2_ino_t ino) | |
712 | { | |
713 | ext2_filsys fs = ctx->fs; | |
714 | errcode_t retval; | |
715 | struct ext2_inode inode; | |
850d05e9 | 716 | char *dir_buf = 0; |
b7a00563 | 717 | struct fill_dir_struct fd; |
b7a00563 | 718 | struct out_dir outdir; |
efc6f628 | 719 | |
1d2eef42 TT |
720 | outdir.max = outdir.num = 0; |
721 | outdir.buf = 0; | |
722 | outdir.hashes = 0; | |
b7a00563 | 723 | e2fsck_read_inode(ctx, ino, &inode, "rehash_dir"); |
b7a00563 TT |
724 | |
725 | retval = ENOMEM; | |
726 | fd.harray = 0; | |
727 | dir_buf = malloc(inode.i_size); | |
728 | if (!dir_buf) | |
729 | goto errout; | |
730 | ||
731 | fd.max_array = inode.i_size / 32; | |
732 | fd.num_array = 0; | |
733 | fd.harray = malloc(fd.max_array * sizeof(struct hash_entry)); | |
734 | if (!fd.harray) | |
735 | goto errout; | |
736 | ||
737 | fd.ctx = ctx; | |
738 | fd.buf = dir_buf; | |
739 | fd.inode = &inode; | |
740 | fd.err = 0; | |
741 | fd.dir_size = 0; | |
850d05e9 TT |
742 | fd.compress = 0; |
743 | if (!(fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_DIR_INDEX) || | |
e70ae99e | 744 | (inode.i_size / fs->blocksize) < 2) |
850d05e9 | 745 | fd.compress = 1; |
b7a00563 TT |
746 | fd.parent = 0; |
747 | ||
f4e14505 | 748 | retry_nohash: |
b7a00563 | 749 | /* Read in the entire directory into memory */ |
6dc64392 | 750 | retval = ext2fs_block_iterate3(fs, ino, 0, 0, |
b7a00563 TT |
751 | fill_dir_block, &fd); |
752 | if (fd.err) { | |
753 | retval = fd.err; | |
754 | goto errout; | |
755 | } | |
756 | ||
f4e14505 TT |
757 | /* |
758 | * If the entries read are less than a block, then don't index | |
759 | * the directory | |
760 | */ | |
761 | if (!fd.compress && (fd.dir_size < (fs->blocksize - 24))) { | |
762 | fd.compress = 1; | |
763 | fd.dir_size = 0; | |
764 | fd.num_array = 0; | |
765 | goto retry_nohash; | |
766 | } | |
767 | ||
b7a00563 TT |
768 | #if 0 |
769 | printf("%d entries (%d bytes) found in inode %d\n", | |
770 | fd.num_array, fd.dir_size, ino); | |
771 | #endif | |
772 | ||
850d05e9 | 773 | /* Sort the list */ |
b0700a1b | 774 | resort: |
53fbfb2b TT |
775 | if (fd.compress) |
776 | qsort(fd.harray+2, fd.num_array-2, sizeof(struct hash_entry), | |
777 | hash_cmp); | |
778 | else | |
779 | qsort(fd.harray, fd.num_array, sizeof(struct hash_entry), | |
780 | hash_cmp); | |
850d05e9 | 781 | |
b0700a1b TT |
782 | /* |
783 | * Look for duplicates | |
784 | */ | |
785 | if (duplicate_search_and_fix(ctx, fs, ino, &fd)) | |
786 | goto resort; | |
787 | ||
1d2eef42 TT |
788 | if (ctx->options & E2F_OPT_NO) { |
789 | retval = 0; | |
790 | goto errout; | |
791 | } | |
792 | ||
b71e0183 TT |
793 | /* Sort non-hashed directories by inode number */ |
794 | if (fd.compress) | |
795 | qsort(fd.harray+2, fd.num_array-2, | |
796 | sizeof(struct hash_entry), ino_cmp); | |
797 | ||
850d05e9 TT |
798 | /* |
799 | * Copy the directory entries. In a htree directory these | |
800 | * will become the leaf nodes. | |
801 | */ | |
7dca4c88 | 802 | retval = copy_dir_entries(ctx, &fd, &outdir); |
b7a00563 TT |
803 | if (retval) |
804 | goto errout; | |
efc6f628 | 805 | |
b7a00563 TT |
806 | free(dir_buf); dir_buf = 0; |
807 | ||
850d05e9 TT |
808 | if (!fd.compress) { |
809 | /* Calculate the interior nodes */ | |
810 | retval = calculate_tree(fs, &outdir, ino, fd.parent); | |
811 | if (retval) | |
812 | goto errout; | |
b7a00563 | 813 | } |
efc6f628 | 814 | |
850d05e9 | 815 | retval = write_directory(ctx, fs, &outdir, ino, fd.compress); |
b7a00563 TT |
816 | if (retval) |
817 | goto errout; | |
818 | ||
819 | errout: | |
45e338f5 JM |
820 | free(dir_buf); |
821 | free(fd.harray); | |
850d05e9 | 822 | |
b7a00563 TT |
823 | free_out_dir(&outdir); |
824 | return retval; | |
825 | } | |
826 | ||
827 | void e2fsck_rehash_directories(e2fsck_t ctx) | |
828 | { | |
b7a00563 | 829 | struct problem_context pctx; |
850d05e9 TT |
830 | #ifdef RESOURCE_TRACK |
831 | struct resource_track rtrack; | |
832 | #endif | |
833 | struct dir_info *dir; | |
834 | ext2_u32_iterate iter; | |
28db82a8 | 835 | struct dir_info_iter * dirinfo_iter = 0; |
850d05e9 TT |
836 | ext2_ino_t ino; |
837 | errcode_t retval; | |
e3507739 | 838 | int cur, max, all_dirs, first = 1; |
850d05e9 | 839 | |
6d96b00d | 840 | init_resource_track(&rtrack, ctx->fs->io); |
850d05e9 TT |
841 | all_dirs = ctx->options & E2F_OPT_COMPRESS_DIRS; |
842 | ||
843 | if (!ctx->dirs_to_hash && !all_dirs) | |
b7a00563 TT |
844 | return; |
845 | ||
850d05e9 | 846 | e2fsck_get_lost_and_found(ctx, 0); |
efc6f628 | 847 | |
b7a00563 | 848 | clear_problem_context(&pctx); |
850d05e9 | 849 | |
b0700a1b TT |
850 | cur = 0; |
851 | if (all_dirs) { | |
28db82a8 | 852 | dirinfo_iter = e2fsck_dir_info_iter_begin(ctx); |
b0700a1b TT |
853 | max = e2fsck_get_num_dirinfo(ctx); |
854 | } else { | |
efc6f628 | 855 | retval = ext2fs_u32_list_iterate_begin(ctx->dirs_to_hash, |
850d05e9 TT |
856 | &iter); |
857 | if (retval) { | |
858 | pctx.errcode = retval; | |
859 | fix_problem(ctx, PR_3A_OPTIMIZE_ITER, &pctx); | |
860 | return; | |
861 | } | |
b0700a1b | 862 | max = ext2fs_u32_list_count(ctx->dirs_to_hash); |
b7a00563 | 863 | } |
850d05e9 TT |
864 | while (1) { |
865 | if (all_dirs) { | |
efc6f628 | 866 | if ((dir = e2fsck_dir_info_iter(ctx, |
28db82a8 | 867 | dirinfo_iter)) == 0) |
850d05e9 TT |
868 | break; |
869 | ino = dir->ino; | |
870 | } else { | |
871 | if (!ext2fs_u32_list_iterate(iter, &ino)) | |
872 | break; | |
873 | } | |
874 | if (ino == ctx->lost_and_found) | |
b7a00563 TT |
875 | continue; |
876 | pctx.dir = ino; | |
877 | if (first) { | |
878 | fix_problem(ctx, PR_3A_PASS_HEADER, &pctx); | |
879 | first = 0; | |
880 | } | |
b0700a1b | 881 | #if 0 |
850d05e9 | 882 | fix_problem(ctx, PR_3A_OPTIMIZE_DIR, &pctx); |
b0700a1b | 883 | #endif |
b7a00563 TT |
884 | pctx.errcode = e2fsck_rehash_dir(ctx, ino); |
885 | if (pctx.errcode) { | |
850d05e9 TT |
886 | end_problem_latch(ctx, PR_LATCH_OPTIMIZE_DIR); |
887 | fix_problem(ctx, PR_3A_OPTIMIZE_DIR_ERR, &pctx); | |
b7a00563 | 888 | } |
52734dc5 TT |
889 | if (ctx->progress && !ctx->progress_fd) |
890 | e2fsck_simple_progress(ctx, "Rebuilding directory", | |
1d2eef42 | 891 | 100.0 * (float) (++cur) / (float) max, ino); |
b7a00563 | 892 | } |
850d05e9 | 893 | end_problem_latch(ctx, PR_LATCH_OPTIMIZE_DIR); |
28db82a8 TT |
894 | if (all_dirs) |
895 | e2fsck_dir_info_iter_end(ctx, dirinfo_iter); | |
896 | else | |
850d05e9 | 897 | ext2fs_u32_list_iterate_end(iter); |
efc6f628 | 898 | |
850d05e9 TT |
899 | if (ctx->dirs_to_hash) |
900 | ext2fs_u32_list_free(ctx->dirs_to_hash); | |
b7a00563 | 901 | ctx->dirs_to_hash = 0; |
850d05e9 | 902 | |
9facd076 | 903 | print_resource_track(ctx, "Pass 3A", &rtrack, ctx->fs->io); |
b7a00563 | 904 | } |