2 * extents.c --- rebuild extent tree
4 * Copyright (C) 2014 Oracle.
7 * This file may be redistributed under the terms of the GNU Public
23 #define NUM_EXTENTS 341 /* about one ETB' worth of extents */
25 static errcode_t
e2fsck_rebuild_extents(e2fsck_t ctx
, ext2_ino_t ino
);
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
)
32 if (!ext2fs_has_feature_extents(ctx
->fs
->super
) ||
33 (ctx
->options
& E2F_OPT_NO
) ||
34 (ino
!= EXT2_ROOT_INO
&& ino
< ctx
->fs
->super
->s_first_ino
))
37 if (ctx
->flags
& E2F_FLAG_ALLOC_OK
)
38 return e2fsck_rebuild_extents(ctx
, ino
);
40 if (!ctx
->inodes_to_rebuild
)
41 retval
= e2fsck_allocate_inode_bitmap(ctx
->fs
,
42 _("extent rebuild inode map"),
45 &ctx
->inodes_to_rebuild
);
49 ext2fs_mark_inode_bitmap2(ctx
->inodes_to_rebuild
, ino
);
53 /* Ask if an inode will have its extents rebuilt during pass 1E. */
54 int e2fsck_ino_will_be_rebuilt(e2fsck_t ctx
, ext2_ino_t ino
)
56 if (!ctx
->inodes_to_rebuild
)
58 return ext2fs_test_inode_bitmap2(ctx
->inodes_to_rebuild
, ino
);
63 struct ext2fs_extent
*extents
;
66 unsigned int ext_read
;
71 static errcode_t
load_extents(e2fsck_t ctx
, struct extent_list
*list
)
73 ext2_filsys fs
= ctx
->fs
;
74 ext2_extent_handle_t handle
;
75 struct ext2fs_extent extent
;
78 retval
= ext2fs_extent_open(fs
, list
->ino
, &handle
);
82 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_ROOT
, &extent
);
87 if (extent
.e_flags
& EXT2_EXTENT_FLAGS_SECOND_VISIT
)
90 /* Internal node; free it and we'll re-allocate it later */
91 if (!(extent
.e_flags
& EXT2_EXTENT_FLAGS_LEAF
)) {
92 #if defined(DEBUG) || defined(DEBUG_FREE)
93 printf("ino=%d free=%llu bf=%llu\n", list
->ino
,
94 extent
.e_pblk
, list
->blocks_freed
+ 1);
97 ext2fs_block_alloc_stats2(fs
, extent
.e_pblk
, -1);
102 /* Can we attach it to the previous extent? */
104 struct ext2fs_extent
*last
= list
->extents
+
106 blk64_t end
= last
->e_len
+ extent
.e_len
;
108 if (last
->e_pblk
+ last
->e_len
== extent
.e_pblk
&&
109 last
->e_lblk
+ last
->e_len
== extent
.e_lblk
&&
110 (last
->e_flags
& EXT2_EXTENT_FLAGS_UNINIT
) ==
111 (extent
.e_flags
& EXT2_EXTENT_FLAGS_UNINIT
) &&
112 end
< (1ULL << 32)) {
113 last
->e_len
+= extent
.e_len
;
115 printf("R: ino=%d len=%u\n", list
->ino
,
122 /* Do we need to expand? */
123 if (list
->count
== list
->size
) {
124 unsigned int new_size
= (list
->size
+ NUM_EXTENTS
) *
125 sizeof(struct ext2fs_extent
);
126 retval
= ext2fs_resize_mem(0, new_size
, &list
->extents
);
129 list
->size
+= NUM_EXTENTS
;
132 /* Add a new extent */
133 memcpy(list
->extents
+ list
->count
, &extent
, sizeof(extent
));
135 printf("R: ino=%d pblk=%llu lblk=%llu len=%u\n", list
->ino
,
136 extent
.e_pblk
, extent
.e_lblk
, extent
.e_len
);
140 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_NEXT
, &extent
);
141 } while (retval
== 0);
144 /* Ok if we run off the end */
145 if (retval
== EXT2_ET_EXTENT_NO_NEXT
)
147 ext2fs_extent_free(handle
);
151 static int find_blocks(ext2_filsys fs
, blk64_t
*blocknr
, e2_blkcnt_t blockcnt
,
152 blk64_t ref_blk
EXT2FS_ATTR((unused
)),
153 int ref_offset
EXT2FS_ATTR((unused
)), void *priv_data
)
155 struct extent_list
*list
= priv_data
;
159 #if defined(DEBUG) || defined(DEBUG_FREE)
160 printf("ino=%d free=%llu bf=%llu\n", list
->ino
, *blocknr
,
161 list
->blocks_freed
+ 1);
163 list
->blocks_freed
++;
164 ext2fs_block_alloc_stats2(fs
, *blocknr
, -1);
168 /* Can we attach it to the previous extent? */
170 struct ext2fs_extent
*last
= list
->extents
+
172 blk64_t end
= last
->e_len
+ 1;
174 if (last
->e_pblk
+ last
->e_len
== *blocknr
&&
175 end
< (1ULL << 32)) {
178 printf("R: ino=%d len=%u\n", list
->ino
, last
->e_len
);
184 /* Do we need to expand? */
185 if (list
->count
== list
->size
) {
186 unsigned int new_size
= (list
->size
+ NUM_EXTENTS
) *
187 sizeof(struct ext2fs_extent
);
188 list
->retval
= ext2fs_resize_mem(0, new_size
, &list
->extents
);
191 list
->size
+= NUM_EXTENTS
;
194 /* Add a new extent */
195 list
->extents
[list
->count
].e_pblk
= *blocknr
;
196 list
->extents
[list
->count
].e_lblk
= blockcnt
;
197 list
->extents
[list
->count
].e_len
= 1;
198 list
->extents
[list
->count
].e_flags
= 0;
200 printf("R: ino=%d pblk=%llu lblk=%llu len=%u\n", list
->ino
, *blocknr
,
208 static errcode_t
rebuild_extent_tree(e2fsck_t ctx
, struct extent_list
*list
,
211 struct ext2_inode inode
;
213 ext2_extent_handle_t handle
;
214 unsigned int i
, ext_written
;
215 struct ext2fs_extent
*ex
, extent
;
218 list
->blocks_freed
= 0;
221 e2fsck_read_inode(ctx
, ino
, &inode
, "rebuild_extents");
223 /* Skip deleted inodes and inline data files */
224 if (inode
.i_links_count
== 0 ||
225 inode
.i_flags
& EXT4_INLINE_DATA_FL
)
228 /* Collect lblk->pblk mappings */
229 if (inode
.i_flags
& EXT4_EXTENTS_FL
) {
230 retval
= load_extents(ctx
, list
);
236 retval
= ext2fs_block_iterate3(ctx
->fs
, ino
, BLOCK_FLAG_READ_ONLY
, 0,
241 retval
= list
->retval
;
246 /* Reset extent tree */
247 inode
.i_flags
&= ~EXT4_EXTENTS_FL
;
248 memset(inode
.i_block
, 0, sizeof(inode
.i_block
));
250 /* Make a note of freed blocks */
251 retval
= ext2fs_iblk_sub_blocks(ctx
->fs
, &inode
, list
->blocks_freed
);
255 /* Now stuff extents into the file */
256 retval
= ext2fs_extent_open2(ctx
->fs
, ino
, &inode
, &handle
);
261 for (i
= 0, ex
= list
->extents
; i
< list
->count
; i
++, ex
++) {
262 memcpy(&extent
, ex
, sizeof(struct ext2fs_extent
));
263 extent
.e_flags
&= EXT2_EXTENT_FLAGS_UNINIT
;
264 if (extent
.e_flags
& EXT2_EXTENT_FLAGS_UNINIT
) {
265 if (extent
.e_len
> EXT_UNINIT_MAX_LEN
) {
266 extent
.e_len
= EXT_UNINIT_MAX_LEN
;
267 ex
->e_pblk
+= EXT_UNINIT_MAX_LEN
;
268 ex
->e_lblk
+= EXT_UNINIT_MAX_LEN
;
269 ex
->e_len
-= EXT_UNINIT_MAX_LEN
;
274 if (extent
.e_len
> EXT_INIT_MAX_LEN
) {
275 extent
.e_len
= EXT_INIT_MAX_LEN
;
276 ex
->e_pblk
+= EXT_INIT_MAX_LEN
;
277 ex
->e_lblk
+= EXT_INIT_MAX_LEN
;
278 ex
->e_len
-= EXT_INIT_MAX_LEN
;
285 printf("W: ino=%d pblk=%llu lblk=%llu len=%u\n", ino
,
286 extent
.e_pblk
, extent
.e_lblk
, extent
.e_len
);
288 retval
= ext2fs_extent_insert(handle
, EXT2_EXTENT_INSERT_AFTER
,
292 retval
= ext2fs_extent_fix_parents(handle
);
298 #if defined(DEBUG) || defined(DEBUG_SUMMARY)
299 printf("rebuild: ino=%d extents=%d->%d\n", ino
, list
->ext_read
,
302 e2fsck_write_inode(ctx
, ino
, &inode
, "rebuild_extents");
305 ext2fs_extent_free(handle
);
310 /* Rebuild the extents immediately */
311 static errcode_t
e2fsck_rebuild_extents(e2fsck_t ctx
, ext2_ino_t ino
)
313 struct extent_list list
;
316 if (!ext2fs_has_feature_extents(ctx
->fs
->super
) ||
317 (ctx
->options
& E2F_OPT_NO
) ||
318 (ino
!= EXT2_ROOT_INO
&& ino
< ctx
->fs
->super
->s_first_ino
))
321 e2fsck_read_bitmaps(ctx
);
322 memset(&list
, 0, sizeof(list
));
323 err
= ext2fs_get_mem(sizeof(struct ext2fs_extent
) * NUM_EXTENTS
,
327 list
.size
= NUM_EXTENTS
;
328 err
= rebuild_extent_tree(ctx
, &list
, ino
);
329 ext2fs_free_mem(&list
.extents
);
334 static void rebuild_extents(e2fsck_t ctx
, const char *pass_name
, int pr_header
)
336 struct problem_context pctx
;
337 #ifdef RESOURCE_TRACK
338 struct resource_track rtrack
;
340 struct extent_list list
;
345 if (!ext2fs_has_feature_extents(ctx
->fs
->super
) ||
346 !ext2fs_test_valid(ctx
->fs
) ||
347 ctx
->invalid_bitmaps
) {
348 if (ctx
->inodes_to_rebuild
)
349 ext2fs_free_inode_bitmap(ctx
->inodes_to_rebuild
);
350 ctx
->inodes_to_rebuild
= NULL
;
353 if (ctx
->inodes_to_rebuild
== NULL
)
356 init_resource_track(&rtrack
, ctx
->fs
->io
);
357 clear_problem_context(&pctx
);
358 e2fsck_read_bitmaps(ctx
);
360 memset(&list
, 0, sizeof(list
));
361 retval
= ext2fs_get_mem(sizeof(struct ext2fs_extent
) * NUM_EXTENTS
,
363 list
.size
= NUM_EXTENTS
;
365 retval
= ext2fs_find_first_set_inode_bitmap2(
366 ctx
->inodes_to_rebuild
, ino
+ 1,
367 ctx
->fs
->super
->s_inodes_count
, &ino
);
372 fix_problem(ctx
, pr_header
, &pctx
);
375 pctx
.errcode
= rebuild_extent_tree(ctx
, &list
, ino
);
377 end_problem_latch(ctx
, PR_LATCH_OPTIMIZE_EXT
);
378 fix_problem(ctx
, PR_1E_OPTIMIZE_EXT_ERR
, &pctx
);
380 if (ctx
->progress
&& !ctx
->progress_fd
)
381 e2fsck_simple_progress(ctx
, "Rebuilding extents",
382 100.0 * (float) ino
/
383 (float) ctx
->fs
->super
->s_inodes_count
,
386 end_problem_latch(ctx
, PR_LATCH_OPTIMIZE_EXT
);
388 ext2fs_free_inode_bitmap(ctx
->inodes_to_rebuild
);
389 ctx
->inodes_to_rebuild
= NULL
;
390 ext2fs_free_mem(&list
.extents
);
392 print_resource_track(ctx
, pass_name
, &rtrack
, ctx
->fs
->io
);
395 /* Scan a file to see if we should rebuild its extent tree */
396 errcode_t
e2fsck_check_rebuild_extents(e2fsck_t ctx
, ext2_ino_t ino
,
397 struct ext2_inode
*inode
,
398 struct problem_context
*pctx
)
400 struct extent_tree_info eti
;
401 struct ext2_extent_info info
, top_info
;
402 struct ext2fs_extent extent
;
403 ext2_extent_handle_t ehandle
;
404 ext2_filsys fs
= ctx
->fs
;
407 /* block map file and we want extent conversion */
408 if (!(inode
->i_flags
& EXT4_EXTENTS_FL
) &&
409 !(inode
->i_flags
& EXT4_INLINE_DATA_FL
) &&
410 (ctx
->options
& E2F_OPT_CONVERT_BMAP
)) {
411 return e2fsck_rebuild_extents_later(ctx
, ino
);
414 if (!(inode
->i_flags
& EXT4_EXTENTS_FL
))
416 memset(&eti
, 0, sizeof(eti
));
419 /* Otherwise, go scan the extent tree... */
420 retval
= ext2fs_extent_open2(fs
, ino
, inode
, &ehandle
);
424 retval
= ext2fs_extent_get_info(ehandle
, &top_info
);
428 /* Check maximum extent depth */
430 pctx
->blk
= top_info
.max_depth
;
431 pctx
->blk2
= ext2fs_max_extent_depth(ehandle
);
432 if (pctx
->blk2
< pctx
->blk
&&
433 fix_problem(ctx
, PR_1_EXTENT_BAD_MAX_DEPTH
, pctx
))
434 eti
.force_rebuild
= 1;
436 /* Can we collect extent tree level stats? */
437 pctx
->blk
= MAX_EXTENT_DEPTH_COUNT
;
438 if (pctx
->blk2
> pctx
->blk
)
439 fix_problem(ctx
, PR_1E_MAX_EXTENT_TREE_DEPTH
, pctx
);
441 /* We need to fix tree depth problems, but the scan isn't a fix. */
442 if (ctx
->options
& E2F_OPT_FIXES_ONLY
)
445 retval
= ext2fs_extent_get(ehandle
, EXT2_EXTENT_ROOT
, &extent
);
450 retval
= ext2fs_extent_get_info(ehandle
, &info
);
455 * If this is the first extent in an extent block that we
456 * haven't visited, collect stats on the block.
458 if (info
.curr_entry
== 1 &&
459 !(extent
.e_flags
& EXT2_EXTENT_FLAGS_SECOND_VISIT
) &&
460 !eti
.force_rebuild
) {
461 struct extent_tree_level
*etl
;
463 etl
= eti
.ext_info
+ info
.curr_level
;
464 etl
->num_extents
+= info
.num_entries
;
465 etl
->max_extents
+= info
.max_entries
;
467 * Implementation wart: Splitting extent blocks when
468 * appending will leave the old block with one free
469 * entry. Therefore unless the node is totally full,
470 * pretend that a non-root extent block can hold one
471 * fewer entry than it actually does, so that we don't
472 * repeatedly rebuild the extent tree.
474 if (info
.curr_level
&&
475 info
.num_entries
< info
.max_entries
)
479 /* Skip to the end of a block of leaf nodes */
480 if (extent
.e_flags
& EXT2_EXTENT_FLAGS_LEAF
) {
481 retval
= ext2fs_extent_get(ehandle
,
482 EXT2_EXTENT_LAST_SIB
,
488 retval
= ext2fs_extent_get(ehandle
, EXT2_EXTENT_NEXT
, &extent
);
489 } while (retval
== 0);
491 ext2fs_extent_free(ehandle
);
492 return e2fsck_should_rebuild_extents(ctx
, pctx
, &eti
, &top_info
);
495 /* Having scanned a file's extent tree, decide if we should rebuild it */
496 errcode_t
e2fsck_should_rebuild_extents(e2fsck_t ctx
,
497 struct problem_context
*pctx
,
498 struct extent_tree_info
*eti
,
499 struct ext2_extent_info
*info
)
501 struct extent_tree_level
*ei
;
503 unsigned int extents_per_block
;
505 if (eti
->force_rebuild
)
508 extents_per_block
= (ctx
->fs
->blocksize
-
509 sizeof(struct ext3_extent_header
)) /
510 sizeof(struct ext3_extent
);
512 * If we can consolidate a level or shorten the tree, schedule the
513 * extent tree to be rebuilt.
515 for (i
= 0, ei
= eti
->ext_info
; i
< info
->max_depth
+ 1; i
++, ei
++) {
516 if (ei
->max_extents
- ei
->num_extents
> extents_per_block
) {
518 op
= PR_1E_CAN_NARROW_EXTENT_TREE
;
521 for (j
= 0; j
< i
; j
++) {
522 if (ei
->num_extents
< eti
->ext_info
[j
].max_extents
) {
524 op
= PR_1E_CAN_COLLAPSE_EXTENT_TREE
;
532 if (eti
->force_rebuild
|| fix_problem(ctx
, op
, pctx
))
533 return e2fsck_rebuild_extents_later(ctx
, eti
->ino
);
537 void e2fsck_pass1e(e2fsck_t ctx
)
539 rebuild_extents(ctx
, "Pass 1E", PR_1E_PASS_HEADER
);