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_lblk
+ last
->e_len
== (__u64
) blockcnt
&&
175 last
->e_pblk
+ last
->e_len
== *blocknr
&&
176 end
< (1ULL << 32)) {
179 printf("R: ino=%d len=%u\n", list
->ino
, last
->e_len
);
185 /* Do we need to expand? */
186 if (list
->count
== list
->size
) {
187 unsigned int new_size
= (list
->size
+ NUM_EXTENTS
) *
188 sizeof(struct ext2fs_extent
);
189 list
->retval
= ext2fs_resize_mem(0, new_size
, &list
->extents
);
192 list
->size
+= NUM_EXTENTS
;
195 /* Add a new extent */
196 list
->extents
[list
->count
].e_pblk
= *blocknr
;
197 list
->extents
[list
->count
].e_lblk
= blockcnt
;
198 list
->extents
[list
->count
].e_len
= 1;
199 list
->extents
[list
->count
].e_flags
= 0;
201 printf("R: ino=%d pblk=%llu lblk=%llu len=%u\n", list
->ino
, *blocknr
,
209 static errcode_t
rebuild_extent_tree(e2fsck_t ctx
, struct extent_list
*list
,
212 struct ext2_inode_large inode
;
214 ext2_extent_handle_t handle
;
215 unsigned int i
, ext_written
;
216 struct ext2fs_extent
*ex
, extent
;
217 blk64_t start_val
, delta
;
220 list
->blocks_freed
= 0;
223 e2fsck_read_inode_full(ctx
, ino
, EXT2_INODE(&inode
), sizeof(inode
),
226 /* Skip deleted inodes and inline data files */
227 if (inode
.i_links_count
== 0 ||
228 inode
.i_flags
& EXT4_INLINE_DATA_FL
)
231 /* Collect lblk->pblk mappings */
232 if (inode
.i_flags
& EXT4_EXTENTS_FL
) {
233 retval
= load_extents(ctx
, list
);
239 retval
= ext2fs_block_iterate3(ctx
->fs
, ino
, BLOCK_FLAG_READ_ONLY
, 0,
244 retval
= list
->retval
;
249 /* Reset extent tree */
250 inode
.i_flags
&= ~EXT4_EXTENTS_FL
;
251 memset(inode
.i_block
, 0, sizeof(inode
.i_block
));
253 /* Make a note of freed blocks */
254 quota_data_sub(ctx
->qctx
, &inode
, ino
,
255 list
->blocks_freed
* ctx
->fs
->blocksize
);
256 retval
= ext2fs_iblk_sub_blocks(ctx
->fs
, EXT2_INODE(&inode
),
261 /* Now stuff extents into the file */
262 retval
= ext2fs_extent_open2(ctx
->fs
, ino
, EXT2_INODE(&inode
), &handle
);
267 start_val
= ext2fs_get_stat_i_blocks(ctx
->fs
, EXT2_INODE(&inode
));
268 for (i
= 0, ex
= list
->extents
; i
< list
->count
; i
++, ex
++) {
269 memcpy(&extent
, ex
, sizeof(struct ext2fs_extent
));
270 extent
.e_flags
&= EXT2_EXTENT_FLAGS_UNINIT
;
271 if (extent
.e_flags
& EXT2_EXTENT_FLAGS_UNINIT
) {
272 if (extent
.e_len
> EXT_UNINIT_MAX_LEN
) {
273 extent
.e_len
= EXT_UNINIT_MAX_LEN
;
274 ex
->e_pblk
+= EXT_UNINIT_MAX_LEN
;
275 ex
->e_lblk
+= EXT_UNINIT_MAX_LEN
;
276 ex
->e_len
-= EXT_UNINIT_MAX_LEN
;
281 if (extent
.e_len
> EXT_INIT_MAX_LEN
) {
282 extent
.e_len
= EXT_INIT_MAX_LEN
;
283 ex
->e_pblk
+= EXT_INIT_MAX_LEN
;
284 ex
->e_lblk
+= EXT_INIT_MAX_LEN
;
285 ex
->e_len
-= EXT_INIT_MAX_LEN
;
292 printf("W: ino=%d pblk=%llu lblk=%llu len=%u\n", ino
,
293 extent
.e_pblk
, extent
.e_lblk
, extent
.e_len
);
295 retval
= ext2fs_extent_insert(handle
, EXT2_EXTENT_INSERT_AFTER
,
299 retval
= ext2fs_extent_fix_parents(handle
);
305 delta
= ext2fs_get_stat_i_blocks(ctx
->fs
, EXT2_INODE(&inode
)) -
308 quota_data_add(ctx
->qctx
, &inode
, ino
, delta
<< 9);
310 #if defined(DEBUG) || defined(DEBUG_SUMMARY)
311 printf("rebuild: ino=%d extents=%d->%d\n", ino
, list
->ext_read
,
314 e2fsck_write_inode(ctx
, ino
, EXT2_INODE(&inode
), "rebuild_extents");
317 ext2fs_extent_free(handle
);
322 /* Rebuild the extents immediately */
323 static errcode_t
e2fsck_rebuild_extents(e2fsck_t ctx
, ext2_ino_t ino
)
325 struct extent_list list
;
328 if (!ext2fs_has_feature_extents(ctx
->fs
->super
) ||
329 (ctx
->options
& E2F_OPT_NO
) ||
330 (ino
!= EXT2_ROOT_INO
&& ino
< ctx
->fs
->super
->s_first_ino
))
333 e2fsck_read_bitmaps(ctx
);
334 memset(&list
, 0, sizeof(list
));
335 err
= ext2fs_get_mem(sizeof(struct ext2fs_extent
) * NUM_EXTENTS
,
339 list
.size
= NUM_EXTENTS
;
340 err
= rebuild_extent_tree(ctx
, &list
, ino
);
341 ext2fs_free_mem(&list
.extents
);
346 static void rebuild_extents(e2fsck_t ctx
, const char *pass_name
, int pr_header
)
348 struct problem_context pctx
;
349 #ifdef RESOURCE_TRACK
350 struct resource_track rtrack
;
352 struct extent_list list
;
357 if (!ext2fs_has_feature_extents(ctx
->fs
->super
) ||
358 !ext2fs_test_valid(ctx
->fs
) ||
359 ctx
->invalid_bitmaps
) {
360 if (ctx
->inodes_to_rebuild
)
361 ext2fs_free_inode_bitmap(ctx
->inodes_to_rebuild
);
362 ctx
->inodes_to_rebuild
= NULL
;
365 if (ctx
->inodes_to_rebuild
== NULL
)
368 init_resource_track(&rtrack
, ctx
->fs
->io
);
369 clear_problem_context(&pctx
);
370 e2fsck_read_bitmaps(ctx
);
372 memset(&list
, 0, sizeof(list
));
373 retval
= ext2fs_get_mem(sizeof(struct ext2fs_extent
) * NUM_EXTENTS
,
375 list
.size
= NUM_EXTENTS
;
377 retval
= ext2fs_find_first_set_inode_bitmap2(
378 ctx
->inodes_to_rebuild
, ino
+ 1,
379 ctx
->fs
->super
->s_inodes_count
, &ino
);
384 fix_problem(ctx
, pr_header
, &pctx
);
387 pctx
.errcode
= rebuild_extent_tree(ctx
, &list
, ino
);
389 end_problem_latch(ctx
, PR_LATCH_OPTIMIZE_EXT
);
390 fix_problem(ctx
, PR_1E_OPTIMIZE_EXT_ERR
, &pctx
);
392 if (ctx
->progress
&& !ctx
->progress_fd
)
393 e2fsck_simple_progress(ctx
, "Rebuilding extents",
394 100.0 * (float) ino
/
395 (float) ctx
->fs
->super
->s_inodes_count
,
398 end_problem_latch(ctx
, PR_LATCH_OPTIMIZE_EXT
);
400 ext2fs_free_inode_bitmap(ctx
->inodes_to_rebuild
);
401 ctx
->inodes_to_rebuild
= NULL
;
402 ext2fs_free_mem(&list
.extents
);
404 print_resource_track(ctx
, pass_name
, &rtrack
, ctx
->fs
->io
);
407 /* Scan a file to see if we should rebuild its extent tree */
408 errcode_t
e2fsck_check_rebuild_extents(e2fsck_t ctx
, ext2_ino_t ino
,
409 struct ext2_inode
*inode
,
410 struct problem_context
*pctx
)
412 struct extent_tree_info eti
;
413 struct ext2_extent_info info
, top_info
;
414 struct ext2fs_extent extent
;
415 ext2_extent_handle_t ehandle
;
416 ext2_filsys fs
= ctx
->fs
;
419 /* block map file and we want extent conversion */
420 if (!(inode
->i_flags
& EXT4_EXTENTS_FL
) &&
421 !(inode
->i_flags
& EXT4_INLINE_DATA_FL
) &&
422 (ctx
->options
& E2F_OPT_CONVERT_BMAP
)) {
423 return e2fsck_rebuild_extents_later(ctx
, ino
);
426 if (!(inode
->i_flags
& EXT4_EXTENTS_FL
))
428 memset(&eti
, 0, sizeof(eti
));
431 /* Otherwise, go scan the extent tree... */
432 retval
= ext2fs_extent_open2(fs
, ino
, inode
, &ehandle
);
436 retval
= ext2fs_extent_get_info(ehandle
, &top_info
);
440 /* Check maximum extent depth */
442 pctx
->blk
= top_info
.max_depth
;
443 pctx
->blk2
= ext2fs_max_extent_depth(ehandle
);
444 if (pctx
->blk2
< pctx
->blk
&&
445 fix_problem(ctx
, PR_1_EXTENT_BAD_MAX_DEPTH
, pctx
))
446 eti
.force_rebuild
= 1;
448 /* Can we collect extent tree level stats? */
449 pctx
->blk
= MAX_EXTENT_DEPTH_COUNT
;
450 if (pctx
->blk2
> pctx
->blk
)
451 fix_problem(ctx
, PR_1E_MAX_EXTENT_TREE_DEPTH
, pctx
);
453 /* We need to fix tree depth problems, but the scan isn't a fix. */
454 if (ctx
->options
& E2F_OPT_FIXES_ONLY
)
457 retval
= ext2fs_extent_get(ehandle
, EXT2_EXTENT_ROOT
, &extent
);
462 retval
= ext2fs_extent_get_info(ehandle
, &info
);
467 * If this is the first extent in an extent block that we
468 * haven't visited, collect stats on the block.
470 if (info
.curr_entry
== 1 &&
471 !(extent
.e_flags
& EXT2_EXTENT_FLAGS_SECOND_VISIT
) &&
472 !eti
.force_rebuild
) {
473 struct extent_tree_level
*etl
;
475 etl
= eti
.ext_info
+ info
.curr_level
;
476 etl
->num_extents
+= info
.num_entries
;
477 etl
->max_extents
+= info
.max_entries
;
479 * Implementation wart: Splitting extent blocks when
480 * appending will leave the old block with one free
481 * entry. Therefore unless the node is totally full,
482 * pretend that a non-root extent block can hold one
483 * fewer entry than it actually does, so that we don't
484 * repeatedly rebuild the extent tree.
486 if (info
.curr_level
&&
487 info
.num_entries
< info
.max_entries
)
491 /* Skip to the end of a block of leaf nodes */
492 if (extent
.e_flags
& EXT2_EXTENT_FLAGS_LEAF
) {
493 retval
= ext2fs_extent_get(ehandle
,
494 EXT2_EXTENT_LAST_SIB
,
500 retval
= ext2fs_extent_get(ehandle
, EXT2_EXTENT_NEXT
, &extent
);
501 } while (retval
== 0);
503 ext2fs_extent_free(ehandle
);
504 return e2fsck_should_rebuild_extents(ctx
, pctx
, &eti
, &top_info
);
507 /* Having scanned a file's extent tree, decide if we should rebuild it */
508 errcode_t
e2fsck_should_rebuild_extents(e2fsck_t ctx
,
509 struct problem_context
*pctx
,
510 struct extent_tree_info
*eti
,
511 struct ext2_extent_info
*info
)
513 struct extent_tree_level
*ei
;
515 unsigned int extents_per_block
;
517 if (eti
->force_rebuild
)
520 if (ctx
->options
& E2F_OPT_NOOPT_EXTENTS
)
523 extents_per_block
= (ctx
->fs
->blocksize
-
524 sizeof(struct ext3_extent_header
)) /
525 sizeof(struct ext3_extent
);
527 * If we can consolidate a level or shorten the tree, schedule the
528 * extent tree to be rebuilt.
530 for (i
= 0, ei
= eti
->ext_info
; i
< info
->max_depth
+ 1; i
++, ei
++) {
531 if (ei
->max_extents
- ei
->num_extents
> extents_per_block
) {
533 op
= PR_1E_CAN_NARROW_EXTENT_TREE
;
536 for (j
= 0; j
< i
; j
++) {
537 if (ei
->num_extents
< eti
->ext_info
[j
].max_extents
) {
539 op
= PR_1E_CAN_COLLAPSE_EXTENT_TREE
;
547 if (eti
->force_rebuild
|| fix_problem(ctx
, op
, pctx
))
548 return e2fsck_rebuild_extents_later(ctx
, eti
->ino
);
552 void e2fsck_pass1e(e2fsck_t ctx
)
554 rebuild_extents(ctx
, "Pass 1E", PR_1E_PASS_HEADER
);