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