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