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_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 */
 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
 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 */
 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 */
 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
 553 void e2fsck_pass1e(e2fsck_t ctx)
 554 {
 555         rebuild_extents(ctx, "Pass 1E", PR_1E_PASS_HEADER);
 556 }