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