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