e2fsck/extents.c

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