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 (!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. */
  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
  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
 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_lblk + last->e_len == blockcnt &&
 175                     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_large inode;
 213         errcode_t               retval;
 214         ext2_extent_handle_t    handle;
 215         unsigned int            i, ext_written;
 216         struct ext2fs_extent    *ex, extent;
 217         blk64_t                 start_val, delta;
 218
 219         list->count = 0;
 220         list->blocks_freed = 0;
 221         list->ino = ino;
 222         list->ext_read = 0;
 223         e2fsck_read_inode_full(ctx, ino, EXT2_INODE(&inode), sizeof(inode),
 224                                "rebuild_extents");
 225
 226         /* Skip deleted inodes and inline data files */
 227         if (inode.i_links_count == 0 ||
 228             inode.i_flags & EXT4_INLINE_DATA_FL)
 229                 return 0;
 230
 231         /* Collect lblk->pblk mappings */
 232         if (inode.i_flags & EXT4_EXTENTS_FL) {
 233                 retval = load_extents(ctx, list);
 234                 if (retval)
 235                         goto err;
 236                 goto extents_loaded;
 237         }
 238
 239         retval = ext2fs_block_iterate3(ctx->fs, ino, BLOCK_FLAG_READ_ONLY, 0,
 240                                        find_blocks, list);
 241         if (retval)
 242                 goto err;
 243         if (list->retval) {
 244                 retval = list->retval;
 245                 goto err;
 246         }
 247
 248 extents_loaded:
 249         /* Reset extent tree */
 250         inode.i_flags &= ~EXT4_EXTENTS_FL;
 251         memset(inode.i_block, 0, sizeof(inode.i_block));
 252
 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),
 257                                         list->blocks_freed);
 258         if (retval)
 259                 goto err;
 260
 261         /* Now stuff extents into the file */
 262         retval = ext2fs_extent_open2(ctx->fs, ino, EXT2_INODE(&inode), &handle);
 263         if (retval)
 264                 goto err;
 265
 266         ext_written = 0;
 267         start_val = ext2fs_inode_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;
 277                                 ex--;
 278                                 i--;
 279                         }
 280                 } else {
 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;
 286                                 ex--;
 287                                 i--;
 288                         }
 289                 }
 290
 291 #ifdef DEBUG
 292                 printf("W: ino=%d pblk=%llu lblk=%llu len=%u\n", ino,
 293                                 extent.e_pblk, extent.e_lblk, extent.e_len);
 294 #endif
 295                 retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER,
 296                                               &extent);
 297                 if (retval)
 298                         goto err2;
 299                 retval = ext2fs_extent_fix_parents(handle);
 300                 if (retval)
 301                         goto err2;
 302                 ext_written++;
 303         }
 304
 305         delta = ext2fs_inode_i_blocks(ctx->fs, EXT2_INODE(&inode)) - start_val;
 306         if (delta) {
 307                 if (!ext2fs_has_feature_huge_file(ctx->fs->super) ||
 308                     !(inode.i_flags & EXT4_HUGE_FILE_FL))
 309                         delta <<= 9;
 310                 else
 311                         delta *= ctx->fs->blocksize;
 312                 quota_data_add(ctx->qctx, &inode, ino, delta);
 313         }
 314
 315 #if defined(DEBUG) || defined(DEBUG_SUMMARY)
 316         printf("rebuild: ino=%d extents=%d->%d\n", ino, list->ext_read,
 317                ext_written);
 318 #endif
 319         e2fsck_write_inode(ctx, ino, EXT2_INODE(&inode), "rebuild_extents");
 320
 321 err2:
 322         ext2fs_extent_free(handle);
 323 err:
 324         return retval;
 325 }
 326
 327 /* Rebuild the extents immediately */
 328 static errcode_t e2fsck_rebuild_extents(e2fsck_t ctx, ext2_ino_t ino)
 329 {
 330         struct extent_list      list;
 331         errcode_t err;
 332
 333         if (!ext2fs_has_feature_extents(ctx->fs->super) ||
 334             (ctx->options & E2F_OPT_NO) ||
 335             (ino != EXT2_ROOT_INO && ino < ctx->fs->super->s_first_ino))
 336                 return 0;
 337
 338         e2fsck_read_bitmaps(ctx);
 339         memset(&list, 0, sizeof(list));
 340         err = ext2fs_get_mem(sizeof(struct ext2fs_extent) * NUM_EXTENTS,
 341                                 &list.extents);
 342         if (err)
 343                 return err;
 344         list.size = NUM_EXTENTS;
 345         err = rebuild_extent_tree(ctx, &list, ino);
 346         ext2fs_free_mem(&list.extents);
 347
 348         return err;
 349 }
 350
 351 static void rebuild_extents(e2fsck_t ctx, const char *pass_name, int pr_header)
 352 {
 353         struct problem_context  pctx;
 354 #ifdef RESOURCE_TRACK
 355         struct resource_track   rtrack;
 356 #endif
 357         struct extent_list      list;
 358         int                     first = 1;
 359         ext2_ino_t              ino = 0;
 360         errcode_t               retval;
 361
 362         if (!ext2fs_has_feature_extents(ctx->fs->super) ||
 363             !ext2fs_test_valid(ctx->fs) ||
 364             ctx->invalid_bitmaps) {
 365                 if (ctx->inodes_to_rebuild)
 366                         ext2fs_free_inode_bitmap(ctx->inodes_to_rebuild);
 367                 ctx->inodes_to_rebuild = NULL;
 368         }
 369
 370         if (ctx->inodes_to_rebuild == NULL)
 371                 return;
 372
 373         init_resource_track(&rtrack, ctx->fs->io);
 374         clear_problem_context(&pctx);
 375         e2fsck_read_bitmaps(ctx);
 376
 377         memset(&list, 0, sizeof(list));
 378         retval = ext2fs_get_mem(sizeof(struct ext2fs_extent) * NUM_EXTENTS,
 379                                 &list.extents);
 380         list.size = NUM_EXTENTS;
 381         while (1) {
 382                 retval = ext2fs_find_first_set_inode_bitmap2(
 383                                 ctx->inodes_to_rebuild, ino + 1,
 384                                 ctx->fs->super->s_inodes_count, &ino);
 385                 if (retval)
 386                         break;
 387                 pctx.ino = ino;
 388                 if (first) {
 389                         fix_problem(ctx, pr_header, &pctx);
 390                         first = 0;
 391                 }
 392                 pctx.errcode = rebuild_extent_tree(ctx, &list, ino);
 393                 if (pctx.errcode) {
 394                         end_problem_latch(ctx, PR_LATCH_OPTIMIZE_EXT);
 395                         fix_problem(ctx, PR_1E_OPTIMIZE_EXT_ERR, &pctx);
 396                 }
 397                 if (ctx->progress && !ctx->progress_fd)
 398                         e2fsck_simple_progress(ctx, "Rebuilding extents",
 399                                         100.0 * (float) ino /
 400                                         (float) ctx->fs->super->s_inodes_count,
 401                                         ino);
 402         }
 403         end_problem_latch(ctx, PR_LATCH_OPTIMIZE_EXT);
 404
 405         ext2fs_free_inode_bitmap(ctx->inodes_to_rebuild);
 406         ctx->inodes_to_rebuild = NULL;
 407         ext2fs_free_mem(&list.extents);
 408
 409         print_resource_track(ctx, pass_name, &rtrack, ctx->fs->io);
 410 }
 411
 412 /* Scan a file to see if we should rebuild its extent tree */
 413 errcode_t e2fsck_check_rebuild_extents(e2fsck_t ctx, ext2_ino_t ino,
 414                                   struct ext2_inode *inode,
 415                                   struct problem_context *pctx)
 416 {
 417         struct extent_tree_info eti;
 418         struct ext2_extent_info info, top_info;
 419         struct ext2fs_extent    extent;
 420         ext2_extent_handle_t    ehandle;
 421         ext2_filsys             fs = ctx->fs;
 422         errcode_t               retval;
 423
 424         /* block map file and we want extent conversion */
 425         if (!(inode->i_flags & EXT4_EXTENTS_FL) &&
 426             !(inode->i_flags & EXT4_INLINE_DATA_FL) &&
 427             (ctx->options & E2F_OPT_CONVERT_BMAP)) {
 428                 return e2fsck_rebuild_extents_later(ctx, ino);
 429         }
 430
 431         if (!(inode->i_flags & EXT4_EXTENTS_FL))
 432                 return 0;
 433         memset(&eti, 0, sizeof(eti));
 434         eti.ino = ino;
 435
 436         /* Otherwise, go scan the extent tree... */
 437         retval = ext2fs_extent_open2(fs, ino, inode, &ehandle);
 438         if (retval)
 439                 return 0;
 440
 441         retval = ext2fs_extent_get_info(ehandle, &top_info);
 442         if (retval)
 443                 goto out;
 444
 445         /* Check maximum extent depth */
 446         pctx->ino = ino;
 447         pctx->blk = top_info.max_depth;
 448         pctx->blk2 = ext2fs_max_extent_depth(ehandle);
 449         if (pctx->blk2 < pctx->blk &&
 450             fix_problem(ctx, PR_1_EXTENT_BAD_MAX_DEPTH, pctx))
 451                 eti.force_rebuild = 1;
 452
 453         /* Can we collect extent tree level stats? */
 454         pctx->blk = MAX_EXTENT_DEPTH_COUNT;
 455         if (pctx->blk2 > pctx->blk)
 456                 fix_problem(ctx, PR_1E_MAX_EXTENT_TREE_DEPTH, pctx);
 457
 458         /* We need to fix tree depth problems, but the scan isn't a fix. */
 459         if (ctx->options & E2F_OPT_FIXES_ONLY)
 460                 goto out;
 461
 462         retval = ext2fs_extent_get(ehandle, EXT2_EXTENT_ROOT, &extent);
 463         if (retval)
 464                 goto out;
 465
 466         do {
 467                 retval = ext2fs_extent_get_info(ehandle, &info);
 468                 if (retval)
 469                         break;
 470
 471                 /*
 472                  * If this is the first extent in an extent block that we
 473                  * haven't visited, collect stats on the block.
 474                  */
 475                 if (info.curr_entry == 1 &&
 476                     !(extent.e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT) &&
 477                     !eti.force_rebuild) {
 478                         struct extent_tree_level *etl;
 479
 480                         etl = eti.ext_info + info.curr_level;
 481                         etl->num_extents += info.num_entries;
 482                         etl->max_extents += info.max_entries;
 483                         /*
 484                          * Implementation wart: Splitting extent blocks when
 485                          * appending will leave the old block with one free
 486                          * entry.  Therefore unless the node is totally full,
 487                          * pretend that a non-root extent block can hold one
 488                          * fewer entry than it actually does, so that we don't
 489                          * repeatedly rebuild the extent tree.
 490                          */
 491                         if (info.curr_level &&
 492                             info.num_entries < info.max_entries)
 493                                 etl->max_extents--;
 494                 }
 495
 496                 /* Skip to the end of a block of leaf nodes */
 497                 if (extent.e_flags & EXT2_EXTENT_FLAGS_LEAF) {
 498                         retval = ext2fs_extent_get(ehandle,
 499                                                     EXT2_EXTENT_LAST_SIB,
 500                                                     &extent);
 501                         if (retval)
 502                                 break;
 503                 }
 504
 505                 retval = ext2fs_extent_get(ehandle, EXT2_EXTENT_NEXT, &extent);
 506         } while (retval == 0);
 507 out:
 508         ext2fs_extent_free(ehandle);
 509         return e2fsck_should_rebuild_extents(ctx, pctx, &eti, &top_info);
 510 }
 511
 512 /* Having scanned a file's extent tree, decide if we should rebuild it */
 513 errcode_t e2fsck_should_rebuild_extents(e2fsck_t ctx,
 514                                    struct problem_context *pctx,
 515                                    struct extent_tree_info *eti,
 516                                    struct ext2_extent_info *info)
 517 {
 518         struct extent_tree_level *ei;
 519         int i, j, op;
 520         unsigned int extents_per_block;
 521
 522         if (eti->force_rebuild)
 523                 goto rebuild;
 524
 525         if (ctx->options & E2F_OPT_NOOPT_EXTENTS)
 526                 return 0;
 527
 528         extents_per_block = (ctx->fs->blocksize -
 529                              sizeof(struct ext3_extent_header)) /
 530                             sizeof(struct ext3_extent);
 531         /*
 532          * If we can consolidate a level or shorten the tree, schedule the
 533          * extent tree to be rebuilt.
 534          */
 535         for (i = 0, ei = eti->ext_info; i < info->max_depth + 1; i++, ei++) {
 536                 if (ei->max_extents - ei->num_extents > extents_per_block) {
 537                         pctx->blk = i;
 538                         op = PR_1E_CAN_NARROW_EXTENT_TREE;
 539                         goto rebuild;
 540                 }
 541                 for (j = 0; j < i; j++) {
 542                         if (ei->num_extents < eti->ext_info[j].max_extents) {
 543                                 pctx->blk = i;
 544                                 op = PR_1E_CAN_COLLAPSE_EXTENT_TREE;
 545                                 goto rebuild;
 546                         }
 547                 }
 548         }
 549         return 0;
 550
 551 rebuild:
 552         if (eti->force_rebuild || fix_problem(ctx, op, pctx))
 553                 return e2fsck_rebuild_extents_later(ctx, eti->ino);
 554         return 0;
 555 }
 556
 557 void e2fsck_pass1e(e2fsck_t ctx)
 558 {
 559         rebuild_extents(ctx, "Pass 1E", PR_1E_PASS_HEADER);
 560 }