]>
Commit | Line | Data |
---|---|---|
e228d700 DW |
1 | /* |
2 | * extents.c --- rebuild extent tree | |
3 | * | |
4 | * Copyright (C) 2014 Oracle. | |
5 | * | |
6 | * %Begin-Header% | |
7 | * This file may be redistributed under the terms of the GNU Public | |
8 | * License, version 2. | |
9 | * %End-Header% | |
10 | */ | |
11 | ||
12 | #include "config.h" | |
13 | #include <string.h> | |
14 | #include <ctype.h> | |
15 | #include <errno.h> | |
16 | #include "e2fsck.h" | |
17 | #include "problem.h" | |
18 | ||
19 | #undef DEBUG | |
20 | #undef DEBUG_SUMMARY | |
21 | #undef DEBUG_FREE | |
22 | ||
23 | #define NUM_EXTENTS 341 /* about one ETB' worth of extents */ | |
24 | ||
25 | static errcode_t e2fsck_rebuild_extents(e2fsck_t ctx, ext2_ino_t ino); | |
26 | ||
27 | /* Schedule an inode to have its extent tree rebuilt during pass 1E. */ | |
28 | errcode_t e2fsck_rebuild_extents_later(e2fsck_t ctx, ext2_ino_t ino) | |
29 | { | |
30 | if (!EXT2_HAS_INCOMPAT_FEATURE(ctx->fs->super, | |
31 | EXT3_FEATURE_INCOMPAT_EXTENTS) || | |
32 | (ctx->options & E2F_OPT_NO) || | |
33 | (ino != EXT2_ROOT_INO && ino < ctx->fs->super->s_first_ino)) | |
34 | return 0; | |
35 | ||
36 | if (ctx->flags & E2F_FLAG_ALLOC_OK) | |
37 | return e2fsck_rebuild_extents(ctx, ino); | |
38 | ||
39 | if (!ctx->inodes_to_rebuild) | |
40 | e2fsck_allocate_inode_bitmap(ctx->fs, | |
41 | _("extent rebuild inode map"), | |
42 | EXT2FS_BMAP64_RBTREE, | |
43 | "inodes_to_rebuild", | |
44 | &ctx->inodes_to_rebuild); | |
45 | if (ctx->inodes_to_rebuild) | |
46 | ext2fs_mark_inode_bitmap2(ctx->inodes_to_rebuild, ino); | |
47 | return 0; | |
48 | } | |
49 | ||
50 | /* Ask if an inode will have its extents rebuilt during pass 1E. */ | |
51 | int e2fsck_ino_will_be_rebuilt(e2fsck_t ctx, ext2_ino_t ino) | |
52 | { | |
53 | if (!ctx->inodes_to_rebuild) | |
54 | return 0; | |
55 | return ext2fs_test_inode_bitmap2(ctx->inodes_to_rebuild, ino); | |
56 | } | |
57 | ||
58 | struct extent_list { | |
59 | blk64_t blocks_freed; | |
60 | struct ext2fs_extent *extents; | |
61 | unsigned int count; | |
62 | unsigned int size; | |
63 | unsigned int ext_read; | |
64 | errcode_t retval; | |
65 | ext2_ino_t ino; | |
66 | }; | |
67 | ||
68 | static errcode_t load_extents(e2fsck_t ctx, struct extent_list *list) | |
69 | { | |
70 | ext2_filsys fs = ctx->fs; | |
71 | ext2_extent_handle_t handle; | |
72 | struct ext2fs_extent extent; | |
73 | errcode_t retval; | |
74 | ||
75 | retval = ext2fs_extent_open(fs, list->ino, &handle); | |
76 | if (retval) | |
77 | return retval; | |
78 | ||
79 | retval = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent); | |
80 | if (retval) | |
81 | goto out; | |
82 | ||
83 | do { | |
84 | if (extent.e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT) | |
85 | goto next; | |
86 | ||
87 | /* Internal node; free it and we'll re-allocate it later */ | |
88 | if (!(extent.e_flags & EXT2_EXTENT_FLAGS_LEAF)) { | |
89 | #if defined(DEBUG) || defined(DEBUG_FREE) | |
90 | printf("ino=%d free=%llu bf=%llu\n", list->ino, | |
91 | extent.e_pblk, list->blocks_freed + 1); | |
92 | #endif | |
93 | list->blocks_freed++; | |
94 | ext2fs_block_alloc_stats2(fs, extent.e_pblk, -1); | |
95 | goto next; | |
96 | } | |
97 | ||
98 | list->ext_read++; | |
99 | /* Can we attach it to the previous extent? */ | |
100 | if (list->count) { | |
101 | struct ext2fs_extent *last = list->extents + | |
102 | list->count - 1; | |
103 | blk64_t end = last->e_len + extent.e_len; | |
104 | ||
105 | if (last->e_pblk + last->e_len == extent.e_pblk && | |
106 | last->e_lblk + last->e_len == extent.e_lblk && | |
107 | (last->e_flags & EXT2_EXTENT_FLAGS_UNINIT) == | |
108 | (extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) && | |
109 | end < (1ULL << 32)) { | |
110 | last->e_len += extent.e_len; | |
111 | #ifdef DEBUG | |
112 | printf("R: ino=%d len=%u\n", list->ino, | |
113 | last->e_len); | |
114 | #endif | |
115 | goto next; | |
116 | } | |
117 | } | |
118 | ||
119 | /* Do we need to expand? */ | |
120 | if (list->count == list->size) { | |
121 | unsigned int new_size = (list->size + NUM_EXTENTS) * | |
122 | sizeof(struct ext2fs_extent); | |
123 | retval = ext2fs_resize_mem(0, new_size, &list->extents); | |
124 | if (retval) | |
125 | goto out; | |
126 | list->size += NUM_EXTENTS; | |
127 | } | |
128 | ||
129 | /* Add a new extent */ | |
130 | memcpy(list->extents + list->count, &extent, sizeof(extent)); | |
131 | #ifdef DEBUG | |
132 | printf("R: ino=%d pblk=%llu lblk=%llu len=%u\n", list->ino, | |
133 | extent.e_pblk, extent.e_lblk, extent.e_len); | |
134 | #endif | |
135 | list->count++; | |
136 | next: | |
137 | retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT, &extent); | |
138 | } while (retval == 0); | |
139 | ||
140 | out: | |
141 | /* Ok if we run off the end */ | |
142 | if (retval == EXT2_ET_EXTENT_NO_NEXT) | |
143 | retval = 0; | |
144 | ext2fs_extent_free(handle); | |
145 | return retval; | |
146 | } | |
147 | ||
148 | static int find_blocks(ext2_filsys fs, blk64_t *blocknr, e2_blkcnt_t blockcnt, | |
149 | blk64_t ref_blk EXT2FS_ATTR((unused)), | |
150 | int ref_offset EXT2FS_ATTR((unused)), void *priv_data) | |
151 | { | |
152 | struct extent_list *list = priv_data; | |
153 | ||
154 | /* Internal node? */ | |
155 | if (blockcnt < 0) { | |
156 | #if defined(DEBUG) || defined(DEBUG_FREE) | |
157 | printf("ino=%d free=%llu bf=%llu\n", list->ino, *blocknr, | |
158 | list->blocks_freed + 1); | |
159 | #endif | |
160 | list->blocks_freed++; | |
161 | ext2fs_block_alloc_stats2(fs, *blocknr, -1); | |
162 | return 0; | |
163 | } | |
164 | ||
165 | /* Can we attach it to the previous extent? */ | |
166 | if (list->count) { | |
167 | struct ext2fs_extent *last = list->extents + | |
168 | list->count - 1; | |
169 | blk64_t end = last->e_len + 1; | |
170 | ||
171 | if (last->e_pblk + last->e_len == *blocknr && | |
172 | end < (1ULL << 32)) { | |
173 | last->e_len++; | |
174 | #ifdef DEBUG | |
175 | printf("R: ino=%d len=%u\n", list->ino, last->e_len); | |
176 | #endif | |
177 | return 0; | |
178 | } | |
179 | } | |
180 | ||
181 | /* Do we need to expand? */ | |
182 | if (list->count == list->size) { | |
183 | unsigned int new_size = (list->size + NUM_EXTENTS) * | |
184 | sizeof(struct ext2fs_extent); | |
185 | list->retval = ext2fs_resize_mem(0, new_size, &list->extents); | |
186 | if (list->retval) | |
187 | return BLOCK_ABORT; | |
188 | list->size += NUM_EXTENTS; | |
189 | } | |
190 | ||
191 | /* Add a new extent */ | |
192 | list->extents[list->count].e_pblk = *blocknr; | |
193 | list->extents[list->count].e_lblk = blockcnt; | |
194 | list->extents[list->count].e_len = 1; | |
195 | list->extents[list->count].e_flags = 0; | |
196 | #ifdef DEBUG | |
197 | printf("R: ino=%d pblk=%llu lblk=%llu len=%u\n", list->ino, *blocknr, | |
198 | blockcnt, 1); | |
199 | #endif | |
200 | list->count++; | |
201 | ||
202 | return 0; | |
203 | } | |
204 | ||
205 | static errcode_t rebuild_extent_tree(e2fsck_t ctx, struct extent_list *list, | |
206 | ext2_ino_t ino) | |
207 | { | |
208 | struct ext2_inode inode; | |
209 | errcode_t retval; | |
210 | ext2_extent_handle_t handle; | |
211 | unsigned int i, ext_written; | |
212 | struct ext2fs_extent *ex, extent; | |
213 | ||
214 | list->count = 0; | |
215 | list->blocks_freed = 0; | |
216 | list->ino = ino; | |
217 | list->ext_read = 0; | |
218 | e2fsck_read_inode(ctx, ino, &inode, "rebuild_extents"); | |
219 | ||
220 | /* Skip deleted inodes and inline data files */ | |
221 | if (inode.i_links_count == 0 || | |
222 | inode.i_flags & EXT4_INLINE_DATA_FL) | |
223 | return 0; | |
224 | ||
225 | /* Collect lblk->pblk mappings */ | |
226 | if (inode.i_flags & EXT4_EXTENTS_FL) { | |
227 | retval = load_extents(ctx, list); | |
228 | goto extents_loaded; | |
229 | } | |
230 | ||
231 | retval = ext2fs_block_iterate3(ctx->fs, ino, BLOCK_FLAG_READ_ONLY, 0, | |
232 | find_blocks, list); | |
233 | if (retval) | |
234 | goto err; | |
235 | if (list->retval) { | |
236 | retval = list->retval; | |
237 | goto err; | |
238 | } | |
239 | ||
240 | extents_loaded: | |
241 | /* Reset extent tree */ | |
242 | inode.i_flags &= ~EXT4_EXTENTS_FL; | |
243 | memset(inode.i_block, 0, sizeof(inode.i_block)); | |
244 | ||
245 | /* Make a note of freed blocks */ | |
246 | retval = ext2fs_iblk_sub_blocks(ctx->fs, &inode, list->blocks_freed); | |
247 | if (retval) | |
248 | goto err; | |
249 | ||
250 | /* Now stuff extents into the file */ | |
251 | retval = ext2fs_extent_open2(ctx->fs, ino, &inode, &handle); | |
252 | if (retval) | |
253 | goto err; | |
254 | ||
255 | ext_written = 0; | |
256 | for (i = 0, ex = list->extents; i < list->count; i++, ex++) { | |
257 | memcpy(&extent, ex, sizeof(struct ext2fs_extent)); | |
258 | extent.e_flags &= EXT2_EXTENT_FLAGS_UNINIT; | |
259 | if (extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) { | |
260 | if (extent.e_len > EXT_UNINIT_MAX_LEN) { | |
261 | extent.e_len = EXT_UNINIT_MAX_LEN; | |
262 | ex->e_pblk += EXT_UNINIT_MAX_LEN; | |
263 | ex->e_lblk += EXT_UNINIT_MAX_LEN; | |
264 | ex->e_len -= EXT_UNINIT_MAX_LEN; | |
265 | ex--; | |
266 | i--; | |
267 | } | |
268 | } else { | |
269 | if (extent.e_len > EXT_INIT_MAX_LEN) { | |
270 | extent.e_len = EXT_INIT_MAX_LEN; | |
271 | ex->e_pblk += EXT_INIT_MAX_LEN; | |
272 | ex->e_lblk += EXT_INIT_MAX_LEN; | |
273 | ex->e_len -= EXT_INIT_MAX_LEN; | |
274 | ex--; | |
275 | i--; | |
276 | } | |
277 | } | |
278 | ||
279 | #ifdef DEBUG | |
280 | printf("W: ino=%d pblk=%llu lblk=%llu len=%u\n", ino, | |
281 | extent.e_pblk, extent.e_lblk, extent.e_len); | |
282 | #endif | |
283 | retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER, | |
284 | &extent); | |
285 | if (retval) | |
286 | goto err2; | |
287 | retval = ext2fs_extent_fix_parents(handle); | |
288 | if (retval) | |
289 | goto err2; | |
290 | ext_written++; | |
291 | } | |
292 | ||
293 | #if defined(DEBUG) || defined(DEBUG_SUMMARY) | |
294 | printf("rebuild: ino=%d extents=%d->%d\n", ino, list->ext_read, | |
295 | ext_written); | |
296 | #endif | |
297 | e2fsck_write_inode(ctx, ino, &inode, "rebuild_extents"); | |
298 | ||
299 | err2: | |
300 | ext2fs_extent_free(handle); | |
301 | err: | |
302 | return retval; | |
303 | } | |
304 | ||
305 | /* Rebuild the extents immediately */ | |
306 | static errcode_t e2fsck_rebuild_extents(e2fsck_t ctx, ext2_ino_t ino) | |
307 | { | |
308 | struct extent_list list; | |
309 | errcode_t err; | |
310 | ||
311 | if (!EXT2_HAS_INCOMPAT_FEATURE(ctx->fs->super, | |
312 | EXT3_FEATURE_INCOMPAT_EXTENTS) || | |
313 | (ctx->options & E2F_OPT_NO) || | |
314 | (ino != EXT2_ROOT_INO && ino < ctx->fs->super->s_first_ino)) | |
315 | return 0; | |
316 | ||
317 | e2fsck_read_bitmaps(ctx); | |
318 | memset(&list, 0, sizeof(list)); | |
319 | err = ext2fs_get_mem(sizeof(struct ext2fs_extent) * NUM_EXTENTS, | |
320 | &list.extents); | |
321 | if (err) | |
322 | return err; | |
323 | list.size = NUM_EXTENTS; | |
324 | err = rebuild_extent_tree(ctx, &list, ino); | |
325 | ext2fs_free_mem(&list.extents); | |
326 | ||
327 | return err; | |
328 | } | |
329 | ||
330 | static void rebuild_extents(e2fsck_t ctx, const char *pass_name, int pr_header) | |
331 | { | |
332 | struct problem_context pctx; | |
333 | #ifdef RESOURCE_TRACK | |
334 | struct resource_track rtrack; | |
335 | #endif | |
336 | struct extent_list list; | |
337 | int first = 1; | |
338 | ext2_ino_t ino = 0; | |
339 | errcode_t retval; | |
340 | ||
341 | if (!EXT2_HAS_INCOMPAT_FEATURE(ctx->fs->super, | |
342 | EXT3_FEATURE_INCOMPAT_EXTENTS) || | |
343 | !ext2fs_test_valid(ctx->fs) || | |
344 | ctx->invalid_bitmaps) { | |
345 | if (ctx->inodes_to_rebuild) | |
346 | ext2fs_free_inode_bitmap(ctx->inodes_to_rebuild); | |
347 | ctx->inodes_to_rebuild = NULL; | |
348 | } | |
349 | ||
350 | if (ctx->inodes_to_rebuild == NULL) | |
351 | return; | |
352 | ||
353 | init_resource_track(&rtrack, ctx->fs->io); | |
354 | clear_problem_context(&pctx); | |
355 | e2fsck_read_bitmaps(ctx); | |
356 | ||
357 | memset(&list, 0, sizeof(list)); | |
358 | retval = ext2fs_get_mem(sizeof(struct ext2fs_extent) * NUM_EXTENTS, | |
359 | &list.extents); | |
360 | list.size = NUM_EXTENTS; | |
361 | while (1) { | |
362 | retval = ext2fs_find_first_set_inode_bitmap2( | |
363 | ctx->inodes_to_rebuild, ino + 1, | |
364 | ctx->fs->super->s_inodes_count, &ino); | |
365 | if (retval) | |
366 | break; | |
367 | pctx.ino = ino; | |
368 | if (first) { | |
369 | fix_problem(ctx, pr_header, &pctx); | |
370 | first = 0; | |
371 | } | |
372 | pctx.errcode = rebuild_extent_tree(ctx, &list, ino); | |
373 | if (pctx.errcode) { | |
374 | end_problem_latch(ctx, PR_LATCH_OPTIMIZE_EXT); | |
375 | fix_problem(ctx, PR_1E_OPTIMIZE_EXT_ERR, &pctx); | |
376 | } | |
377 | if (ctx->progress && !ctx->progress_fd) | |
378 | e2fsck_simple_progress(ctx, "Rebuilding extents", | |
379 | 100.0 * (float) ino / | |
380 | (float) ctx->fs->super->s_inodes_count, | |
381 | ino); | |
382 | } | |
383 | end_problem_latch(ctx, PR_LATCH_OPTIMIZE_EXT); | |
384 | ||
385 | ext2fs_free_inode_bitmap(ctx->inodes_to_rebuild); | |
386 | ctx->inodes_to_rebuild = NULL; | |
387 | ext2fs_free_mem(&list.extents); | |
388 | ||
389 | print_resource_track(ctx, pass_name, &rtrack, ctx->fs->io); | |
390 | } | |
391 | ||
392 | /* Scan a file to see if we should rebuild its extent tree */ | |
393 | errcode_t e2fsck_check_rebuild_extents(e2fsck_t ctx, ext2_ino_t ino, | |
394 | struct ext2_inode *inode, | |
395 | struct problem_context *pctx) | |
396 | { | |
397 | struct extent_tree_info eti; | |
398 | struct ext2_extent_info info, top_info; | |
399 | struct ext2fs_extent extent; | |
400 | ext2_extent_handle_t ehandle; | |
401 | ext2_filsys fs = ctx->fs; | |
402 | errcode_t retval; | |
403 | ||
404 | /* block map file and we want extent conversion */ | |
405 | if (!(inode->i_flags & EXT4_EXTENTS_FL) && | |
406 | !(inode->i_flags & EXT4_INLINE_DATA_FL) && | |
407 | (ctx->options & E2F_OPT_CONVERT_BMAP)) { | |
408 | return e2fsck_rebuild_extents_later(ctx, ino); | |
409 | } | |
410 | ||
411 | if (!(inode->i_flags & EXT4_EXTENTS_FL)) | |
412 | return 0; | |
413 | memset(&eti, 0, sizeof(eti)); | |
414 | eti.ino = ino; | |
415 | ||
416 | /* Otherwise, go scan the extent tree... */ | |
417 | retval = ext2fs_extent_open2(fs, ino, inode, &ehandle); | |
418 | if (retval) | |
419 | return 0; | |
420 | ||
421 | retval = ext2fs_extent_get_info(ehandle, &top_info); | |
422 | if (retval) | |
423 | goto out; | |
424 | ||
425 | /* Check maximum extent depth */ | |
426 | pctx->ino = ino; | |
427 | pctx->blk = top_info.max_depth; | |
428 | pctx->blk2 = ext2fs_max_extent_depth(ehandle); | |
429 | if (pctx->blk2 < pctx->blk && | |
430 | fix_problem(ctx, PR_1_EXTENT_BAD_MAX_DEPTH, pctx)) | |
431 | eti.force_rebuild = 1; | |
432 | ||
433 | /* Can we collect extent tree level stats? */ | |
434 | pctx->blk = MAX_EXTENT_DEPTH_COUNT; | |
435 | if (pctx->blk2 > pctx->blk) | |
436 | fix_problem(ctx, PR_1E_MAX_EXTENT_TREE_DEPTH, pctx); | |
437 | ||
438 | /* We need to fix tree depth problems, but the scan isn't a fix. */ | |
439 | if (ctx->options & E2F_OPT_FIXES_ONLY) | |
440 | goto out; | |
441 | ||
442 | retval = ext2fs_extent_get(ehandle, EXT2_EXTENT_ROOT, &extent); | |
443 | if (retval) | |
444 | goto out; | |
445 | ||
446 | do { | |
447 | retval = ext2fs_extent_get_info(ehandle, &info); | |
448 | if (retval) | |
449 | break; | |
450 | ||
451 | /* | |
452 | * If this is the first extent in an extent block that we | |
453 | * haven't visited, collect stats on the block. | |
454 | */ | |
455 | if (info.curr_entry == 1 && | |
456 | !(extent.e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT) && | |
457 | !eti.force_rebuild) { | |
458 | struct extent_tree_level *etl; | |
459 | ||
460 | etl = eti.ext_info + info.curr_level; | |
461 | etl->num_extents += info.num_entries; | |
462 | etl->max_extents += info.max_entries; | |
463 | /* | |
464 | * Implementation wart: Splitting extent blocks when | |
465 | * appending will leave the old block with one free | |
466 | * entry. Therefore unless the node is totally full, | |
467 | * pretend that a non-root extent block can hold one | |
468 | * fewer entry than it actually does, so that we don't | |
469 | * repeatedly rebuild the extent tree. | |
470 | */ | |
471 | if (info.curr_level && | |
472 | info.num_entries < info.max_entries) | |
473 | etl->max_extents--; | |
474 | } | |
475 | ||
476 | /* Skip to the end of a block of leaf nodes */ | |
477 | if (extent.e_flags & EXT2_EXTENT_FLAGS_LEAF) { | |
478 | retval = ext2fs_extent_get(ehandle, | |
479 | EXT2_EXTENT_LAST_SIB, | |
480 | &extent); | |
481 | if (retval) | |
482 | break; | |
483 | } | |
484 | ||
485 | retval = ext2fs_extent_get(ehandle, EXT2_EXTENT_NEXT, &extent); | |
486 | } while (retval == 0); | |
487 | out: | |
488 | ext2fs_extent_free(ehandle); | |
489 | return e2fsck_should_rebuild_extents(ctx, pctx, &eti, &top_info); | |
490 | } | |
491 | ||
492 | /* Having scanned a file's extent tree, decide if we should rebuild it */ | |
493 | errcode_t e2fsck_should_rebuild_extents(e2fsck_t ctx, | |
494 | struct problem_context *pctx, | |
495 | struct extent_tree_info *eti, | |
496 | struct ext2_extent_info *info) | |
497 | { | |
498 | struct extent_tree_level *ei; | |
499 | int i, j, op; | |
500 | unsigned int extents_per_block; | |
501 | ||
502 | if (eti->force_rebuild) | |
503 | goto rebuild; | |
504 | ||
505 | extents_per_block = (ctx->fs->blocksize - | |
506 | sizeof(struct ext3_extent_header)) / | |
507 | sizeof(struct ext3_extent); | |
508 | /* | |
509 | * If we can consolidate a level or shorten the tree, schedule the | |
510 | * extent tree to be rebuilt. | |
511 | */ | |
512 | for (i = 0, ei = eti->ext_info; i < info->max_depth + 1; i++, ei++) { | |
513 | if (ei->max_extents - ei->num_extents > extents_per_block) { | |
514 | pctx->blk = i; | |
515 | op = PR_1E_CAN_NARROW_EXTENT_TREE; | |
516 | goto rebuild; | |
517 | } | |
518 | for (j = 0; j < i; j++) { | |
519 | if (ei->num_extents < eti->ext_info[j].max_extents) { | |
520 | pctx->blk = i; | |
521 | op = PR_1E_CAN_COLLAPSE_EXTENT_TREE; | |
522 | goto rebuild; | |
523 | } | |
524 | } | |
525 | } | |
526 | return 0; | |
527 | ||
528 | rebuild: | |
529 | if (eti->force_rebuild || fix_problem(ctx, op, pctx)) | |
530 | return e2fsck_rebuild_extents_later(ctx, eti->ino); | |
531 | return 0; | |
532 | } | |
533 | ||
534 | void e2fsck_pass1e(e2fsck_t ctx) | |
535 | { | |
536 | rebuild_extents(ctx, "Pass 1E", PR_1E_PASS_HEADER); | |
537 | } |