[thirdparty/e2fsprogs.git] / e2fsck / extents.c

/*
 * extents.c --- rebuild extent tree
 *
 * Copyright (C) 2014 Oracle.
 *
 * %Begin-Header%
 * This file may be redistributed under the terms of the GNU Public
 * License, version 2.
 * %End-Header%
 */

#include "config.h"
#include <string.h>
#include <ctype.h>
#include <errno.h>
#include "e2fsck.h"
#include "problem.h"

#undef DEBUG
#undef DEBUG_SUMMARY
#undef DEBUG_FREE

#define NUM_EXTENTS	341	/* about one ETB' worth of extents */

static errcode_t e2fsck_rebuild_extents(e2fsck_t ctx, ext2_ino_t ino);

/* Schedule an inode to have its extent tree rebuilt during pass 1E. */
errcode_t e2fsck_rebuild_extents_later(e2fsck_t ctx, ext2_ino_t ino)
{
	errcode_t retval = 0;

	if (!ext2fs_has_feature_extents(ctx->fs->super) ||
	    (ctx->options & E2F_OPT_NO) ||
	    (ino != EXT2_ROOT_INO && ino < ctx->fs->super->s_first_ino))
		return 0;

	if (ctx->flags & E2F_FLAG_ALLOC_OK)
		return e2fsck_rebuild_extents(ctx, ino);

	if (!ctx->inodes_to_rebuild)
		retval = e2fsck_allocate_inode_bitmap(ctx->fs,
					     _("extent rebuild inode map"),
					     EXT2FS_BMAP64_RBTREE,
					     "inodes_to_rebuild",
					     &ctx->inodes_to_rebuild);
	if (retval)
		return retval;

	ext2fs_mark_inode_bitmap2(ctx->inodes_to_rebuild, ino);
	return 0;
}

/* Ask if an inode will have its extents rebuilt during pass 1E. */
int e2fsck_ino_will_be_rebuilt(e2fsck_t ctx, ext2_ino_t ino)
{
	if (!ctx->inodes_to_rebuild)
		return 0;
	return ext2fs_test_inode_bitmap2(ctx->inodes_to_rebuild, ino);
}

static errcode_t load_extents(e2fsck_t ctx, struct extent_list *list)
{
	ext2_filsys		fs = ctx->fs;
	ext2_extent_handle_t	handle;
	struct ext2fs_extent	extent;
	errcode_t		retval;

	retval = ext2fs_extent_open(fs, list->ino, &handle);
	if (retval)
		return retval;

	retval = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent);
	if (retval)
		goto out;

	do {
		if (extent.e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT)
			goto next;

		/* Internal node; free it and we'll re-allocate it later */
		if (!(extent.e_flags & EXT2_EXTENT_FLAGS_LEAF)) {
#if defined(DEBUG) || defined(DEBUG_FREE)
			printf("ino=%d free=%llu bf=%llu\n", list->ino,
					extent.e_pblk, list->blocks_freed + 1);
#endif
			list->blocks_freed++;
			ext2fs_block_alloc_stats2(fs, extent.e_pblk, -1);
			goto next;
		}

		list->ext_read++;
		/* Can we attach it to the previous extent? */
		if (list->count) {
			struct ext2fs_extent *last = list->extents +
						     list->count - 1;
			blk64_t end = last->e_len + extent.e_len;

			if (last->e_pblk + last->e_len == extent.e_pblk &&
			    last->e_lblk + last->e_len == extent.e_lblk &&
			    (last->e_flags & EXT2_EXTENT_FLAGS_UNINIT) ==
			    (extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) &&
			    end < (1ULL << 32)) {
				last->e_len += extent.e_len;
#ifdef DEBUG
				printf("R: ino=%d len=%u\n", list->ino,
						last->e_len);
#endif
				goto next;
			}
		}

		/* Do we need to expand? */
		if (list->count == list->size) {
			unsigned int new_size = (list->size + NUM_EXTENTS) *
						sizeof(struct ext2fs_extent);
			retval = ext2fs_resize_mem(0, new_size, &list->extents);
			if (retval)
				goto out;
			list->size += NUM_EXTENTS;
		}

		/* Add a new extent */
		memcpy(list->extents + list->count, &extent, sizeof(extent));
#ifdef DEBUG
		printf("R: ino=%d pblk=%llu lblk=%llu len=%u\n", list->ino,
				extent.e_pblk, extent.e_lblk, extent.e_len);
#endif
		list->count++;
next:
		retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT, &extent);
	} while (retval == 0);

out:
	/* Ok if we run off the end */
	if (retval == EXT2_ET_EXTENT_NO_NEXT)
		retval = 0;
	ext2fs_extent_free(handle);
	return retval;
}

static int find_blocks(ext2_filsys fs, blk64_t *blocknr, e2_blkcnt_t blockcnt,
		       blk64_t ref_blk EXT2FS_ATTR((unused)),
		       int ref_offset EXT2FS_ATTR((unused)), void *priv_data)
{
	struct extent_list *list = priv_data;

	/* Internal node? */
	if (blockcnt < 0) {
#if defined(DEBUG) || defined(DEBUG_FREE)
		printf("ino=%d free=%llu bf=%llu\n", list->ino, *blocknr,
				list->blocks_freed + 1);
#endif
		list->blocks_freed++;
		ext2fs_block_alloc_stats2(fs, *blocknr, -1);
		return 0;
	}

	/* Can we attach it to the previous extent? */
	if (list->count) {
		struct ext2fs_extent *last = list->extents +
					     list->count - 1;
		blk64_t end = last->e_len + 1;

		if (last->e_lblk + last->e_len == (__u64) blockcnt &&
		    last->e_pblk + last->e_len == *blocknr &&
		    end < (1ULL << 32)) {
			last->e_len++;
#ifdef DEBUG
			printf("R: ino=%d len=%u\n", list->ino, last->e_len);
#endif
			return 0;
		}
	}

	/* Do we need to expand? */
	if (list->count == list->size) {
		unsigned int new_size = (list->size + NUM_EXTENTS) *
					sizeof(struct ext2fs_extent);
		list->retval = ext2fs_resize_mem(0, new_size, &list->extents);
		if (list->retval)
			return BLOCK_ABORT;
		list->size += NUM_EXTENTS;
	}

	/* Add a new extent */
	list->extents[list->count].e_pblk = *blocknr;
	list->extents[list->count].e_lblk = blockcnt;
	list->extents[list->count].e_len = 1;
	list->extents[list->count].e_flags = 0;
#ifdef DEBUG
	printf("R: ino=%d pblk=%llu lblk=%llu len=%u\n", list->ino, *blocknr,
			blockcnt, 1);
#endif
	list->count++;

	return 0;
}

errcode_t rewrite_extent_replay(e2fsck_t ctx, struct extent_list *list,
				       struct ext2_inode_large *inode)
{
	errcode_t		retval;
	ext2_extent_handle_t	handle;
	unsigned int		i, ext_written;
	struct ext2fs_extent	*ex, extent;
	blk64_t			start_val, delta, blkcount;

	/* Reset extent tree */
	inode->i_flags &= ~EXT4_EXTENTS_FL;
	memset(inode->i_block, 0, sizeof(inode->i_block));

	/* Make a note of freed blocks */
	quota_data_sub(ctx->qctx, inode, list->ino,
		       list->blocks_freed * ctx->fs->blocksize);
	retval = ext2fs_iblk_sub_blocks(ctx->fs, EXT2_INODE(inode),
					list->blocks_freed);
	if (retval)
		return retval;

	/* Now stuff extents into the file */
	retval = ext2fs_extent_open2(ctx->fs, list->ino, EXT2_INODE(inode),
					&handle);
	if (retval)
		return retval;

	ext_written = 0;

	start_val = ext2fs_get_stat_i_blocks(ctx->fs, EXT2_INODE(inode));

	for (i = 0, ex = list->extents; i < list->count; i++, ex++) {
		if (ex->e_len == 0)
			continue;
		memcpy(&extent, ex, sizeof(struct ext2fs_extent));
		extent.e_flags &= EXT2_EXTENT_FLAGS_UNINIT;
		if (extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) {
			if (extent.e_len > EXT_UNINIT_MAX_LEN) {
				extent.e_len = EXT_UNINIT_MAX_LEN;
				ex->e_pblk += EXT_UNINIT_MAX_LEN;
				ex->e_lblk += EXT_UNINIT_MAX_LEN;
				ex->e_len -= EXT_UNINIT_MAX_LEN;
				ex--;
				i--;
			}
		} else {
			if (extent.e_len > EXT_INIT_MAX_LEN) {
				extent.e_len = EXT_INIT_MAX_LEN;
				ex->e_pblk += EXT_INIT_MAX_LEN;
				ex->e_lblk += EXT_INIT_MAX_LEN;
				ex->e_len -= EXT_INIT_MAX_LEN;
				ex--;
				i--;
			}
		}

#ifdef DEBUG
		printf("W: ino=%d pblk=%llu lblk=%llu len=%u\n", list->ino,
				extent.e_pblk, extent.e_lblk, extent.e_len);
#endif
		retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER,
					      &extent);
		if (retval)
			goto err;
		retval = ext2fs_extent_fix_parents(handle);
		if (retval)
			goto err;
		ext_written++;
	}

	delta = ext2fs_get_stat_i_blocks(ctx->fs, EXT2_INODE(inode)) -
		start_val;
	if (delta)
		quota_data_add(ctx->qctx, inode, list->ino, delta << 9);

#if defined(DEBUG) || defined(DEBUG_SUMMARY)
	printf("rebuild: ino=%d extents=%d->%d\n", ino, list->ext_read,
	       ext_written);
#endif
	e2fsck_write_inode(ctx, list->ino, EXT2_INODE(inode),
				"rebuild_extents");

err:
	ext2fs_extent_free(handle);
	return retval;
}

errcode_t e2fsck_rewrite_extent_tree(e2fsck_t ctx, struct extent_list *list)
{
	struct ext2_inode_large inode;
	blk64_t blk_count;
	errcode_t err;

	memset(&inode, 0, sizeof(inode));
	ext2fs_read_inode_full(ctx->fs, list->ino, EXT2_INODE(&inode),
				sizeof(inode));

	/* Skip deleted inodes and inline data files */
	if (inode.i_flags & EXT4_INLINE_DATA_FL)
		return 0;

	err = rewrite_extent_replay(ctx, list, &inode);
	if (err)
		return err;

	err = ext2fs_count_blocks(ctx->fs, list->ino, EXT2_INODE(&inode),
				  &blk_count);
	if (err)
		return err;
	ext2fs_iblk_set(ctx->fs, EXT2_INODE(&inode), blk_count);
	ext2fs_write_inode_full(ctx->fs, list->ino, EXT2_INODE(&inode),
		sizeof(inode));

	return 0;
}

errcode_t e2fsck_read_extents(e2fsck_t ctx, struct extent_list *extents)
{
	struct ext2_inode_large	inode;
	errcode_t		retval;

	extents->extents = NULL;
	extents->count = 0;
	extents->blocks_freed = 0;
	extents->ext_read = 0;
	extents->size = NUM_EXTENTS;
	retval = ext2fs_get_array(NUM_EXTENTS, sizeof(struct ext2fs_extent),
				  &extents->extents);
	if (retval)
		return -ENOMEM;

	retval = ext2fs_read_inode(ctx->fs, extents->ino, EXT2_INODE(&inode));
	if (retval)
		goto err_out;

	retval = load_extents(ctx, extents);
	if (!retval)
		return 0;
err_out:
	ext2fs_free_mem(&extents->extents);
	extents->size = 0;
	extents->count = 0;
	return retval;
}

static errcode_t rebuild_extent_tree(e2fsck_t ctx, struct extent_list *list,
				     ext2_ino_t ino)
{
	struct ext2_inode_large	inode;
	errcode_t		retval;

	list->count = 0;
	list->blocks_freed = 0;
	list->ino = ino;
	list->ext_read = 0;
	e2fsck_read_inode_full(ctx, ino, EXT2_INODE(&inode), sizeof(inode),
			       "rebuild_extents");

	/* Skip deleted inodes and inline data files */
	if (inode.i_links_count == 0 ||
	    inode.i_flags & EXT4_INLINE_DATA_FL)
		return 0;

	/* Collect lblk->pblk mappings */
	if (inode.i_flags & EXT4_EXTENTS_FL) {
		retval = load_extents(ctx, list);
		if (retval)
			return retval;
		return rewrite_extent_replay(ctx, list, &inode);
	}

	retval = ext2fs_block_iterate3(ctx->fs, ino, BLOCK_FLAG_READ_ONLY, 0,
				       find_blocks, list);

	return retval || list->retval ||
		rewrite_extent_replay(ctx, list, &inode);
}

/* Rebuild the extents immediately */
static errcode_t e2fsck_rebuild_extents(e2fsck_t ctx, ext2_ino_t ino)
{
	struct extent_list list = { 0 };
	errcode_t err;

	if (!ext2fs_has_feature_extents(ctx->fs->super) ||
	    (ctx->options & E2F_OPT_NO) ||
	    (ino != EXT2_ROOT_INO && ino < ctx->fs->super->s_first_ino))
		return 0;

	e2fsck_read_bitmaps(ctx);
	err = ext2fs_get_array(NUM_EXTENTS, sizeof(struct ext2fs_extent),
			       &list.extents);
	if (err)
		return err;
	list.size = NUM_EXTENTS;
	err = rebuild_extent_tree(ctx, &list, ino);
	ext2fs_free_mem(&list.extents);

	return err;
}

static void rebuild_extents(e2fsck_t ctx, const char *pass_name, int pr_header)
{
	struct problem_context	pctx;
#ifdef RESOURCE_TRACK
	struct resource_track	rtrack;
#endif
	struct extent_list	list = { 0 };
	int			first = 1;
	ext2_ino_t		ino = 0;
	errcode_t		retval;

	if (!ext2fs_has_feature_extents(ctx->fs->super) ||
	    !ext2fs_test_valid(ctx->fs) ||
	    ctx->invalid_bitmaps) {
		if (ctx->inodes_to_rebuild)
			ext2fs_free_inode_bitmap(ctx->inodes_to_rebuild);
		ctx->inodes_to_rebuild = NULL;
	}

	if (ctx->inodes_to_rebuild == NULL)
		return;

	init_resource_track(&rtrack, ctx->fs->io);
	clear_problem_context(&pctx);
	e2fsck_read_bitmaps(ctx);

	list.size = NUM_EXTENTS;
	retval = ext2fs_get_array(sizeof(struct ext2fs_extent),
				  list.size, &list.extents);
	if (retval)
		return;
	while (1) {
		retval = ext2fs_find_first_set_inode_bitmap2(
				ctx->inodes_to_rebuild, ino + 1,
				ctx->fs->super->s_inodes_count, &ino);
		if (retval)
			break;
		pctx.ino = ino;
		if (first) {
			fix_problem(ctx, pr_header, &pctx);
			first = 0;
		}
		pctx.errcode = rebuild_extent_tree(ctx, &list, ino);
		if (pctx.errcode) {
			end_problem_latch(ctx, PR_LATCH_OPTIMIZE_EXT);
			fix_problem(ctx, PR_1E_OPTIMIZE_EXT_ERR, &pctx);
		}
		if (ctx->progress && !ctx->progress_fd)
			e2fsck_simple_progress(ctx, "Rebuilding extents",
					100.0 * (float) ino /
					(float) ctx->fs->super->s_inodes_count,
					ino);
	}
	end_problem_latch(ctx, PR_LATCH_OPTIMIZE_EXT);

	ext2fs_free_inode_bitmap(ctx->inodes_to_rebuild);
	ctx->inodes_to_rebuild = NULL;
	ext2fs_free_mem(&list.extents);

	print_resource_track(ctx, pass_name, &rtrack, ctx->fs->io);
}

/* Scan a file to see if we should rebuild its extent tree */
errcode_t e2fsck_check_rebuild_extents(e2fsck_t ctx, ext2_ino_t ino,
				  struct ext2_inode *inode,
				  struct problem_context *pctx)
{
	struct extent_tree_info	eti;
	struct ext2_extent_info	info, top_info;
	struct ext2fs_extent	extent;
	ext2_extent_handle_t	ehandle;
	ext2_filsys		fs = ctx->fs;
	errcode_t		retval;

	/* block map file and we want extent conversion */
	if (!(inode->i_flags & EXT4_EXTENTS_FL) &&
	    !(inode->i_flags & EXT4_INLINE_DATA_FL) &&
	    (ctx->options & E2F_OPT_CONVERT_BMAP)) {
		return e2fsck_rebuild_extents_later(ctx, ino);
	}

	if (!(inode->i_flags & EXT4_EXTENTS_FL))
		return 0;
	memset(&eti, 0, sizeof(eti));
	eti.ino = ino;

	/* Otherwise, go scan the extent tree... */
	retval = ext2fs_extent_open2(fs, ino, inode, &ehandle);
	if (retval)
		return 0;

	retval = ext2fs_extent_get_info(ehandle, &top_info);
	if (retval)
		goto out;

	/* Check maximum extent depth */
	pctx->ino = ino;
	pctx->blk = top_info.max_depth;
	pctx->blk2 = ext2fs_max_extent_depth(ehandle);
	if (pctx->blk2 < pctx->blk &&
	    fix_problem(ctx, PR_1_EXTENT_BAD_MAX_DEPTH, pctx))
		eti.force_rebuild = 1;

	/* Can we collect extent tree level stats? */
	pctx->blk = MAX_EXTENT_DEPTH_COUNT;
	if (pctx->blk2 > pctx->blk)
		fix_problem(ctx, PR_1E_MAX_EXTENT_TREE_DEPTH, pctx);

	/* We need to fix tree depth problems, but the scan isn't a fix. */
	if (ctx->options & E2F_OPT_FIXES_ONLY)
		goto out;

	retval = ext2fs_extent_get(ehandle, EXT2_EXTENT_ROOT, &extent);
	if (retval)
		goto out;

	do {
		retval = ext2fs_extent_get_info(ehandle, &info);
		if (retval)
			break;

		/*
		 * If this is the first extent in an extent block that we
		 * haven't visited, collect stats on the block.
		 */
		if (info.curr_entry == 1 &&
		    !(extent.e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT) &&
		    !eti.force_rebuild) {
			struct extent_tree_level *etl;

			etl = eti.ext_info + info.curr_level;
			etl->num_extents += info.num_entries;
			etl->max_extents += info.max_entries;
			/*
			 * Implementation wart: Splitting extent blocks when
			 * appending will leave the old block with one free
			 * entry.  Therefore unless the node is totally full,
			 * pretend that a non-root extent block can hold one
			 * fewer entry than it actually does, so that we don't
			 * repeatedly rebuild the extent tree.
			 */
			if (info.curr_level &&
			    info.num_entries < info.max_entries)
				etl->max_extents--;
		}

		/* Skip to the end of a block of leaf nodes */
		if (extent.e_flags & EXT2_EXTENT_FLAGS_LEAF) {
			retval = ext2fs_extent_get(ehandle,
						    EXT2_EXTENT_LAST_SIB,
						    &extent);
			if (retval)
				break;
		}

		retval = ext2fs_extent_get(ehandle, EXT2_EXTENT_NEXT, &extent);
	} while (retval == 0);
out:
	ext2fs_extent_free(ehandle);
	return e2fsck_should_rebuild_extents(ctx, pctx, &eti, &top_info);
}

/* Having scanned a file's extent tree, decide if we should rebuild it */
errcode_t e2fsck_should_rebuild_extents(e2fsck_t ctx,
				   struct problem_context *pctx,
				   struct extent_tree_info *eti,
				   struct ext2_extent_info *info)
{
	struct extent_tree_level *ei;
	int i, j, op;
	unsigned int extents_per_block;

	if (eti->force_rebuild)
		goto rebuild;

	if (ctx->options & E2F_OPT_NOOPT_EXTENTS)
		return 0;

	extents_per_block = (ctx->fs->blocksize -
			     sizeof(struct ext3_extent_header)) /
			    sizeof(struct ext3_extent);
	/*
	 * If we can consolidate a level or shorten the tree, schedule the
	 * extent tree to be rebuilt.
	 */
	for (i = 0, ei = eti->ext_info; i < info->max_depth + 1; i++, ei++) {
		if (ei->max_extents - ei->num_extents > extents_per_block) {
			pctx->blk = i;
			op = PR_1E_CAN_NARROW_EXTENT_TREE;
			goto rebuild;
		}
		for (j = 0; j < i; j++) {
			if (ei->num_extents < eti->ext_info[j].max_extents) {
				pctx->blk = i;
				op = PR_1E_CAN_COLLAPSE_EXTENT_TREE;
				goto rebuild;
			}
		}
	}
	return 0;

rebuild:
	if (eti->force_rebuild || fix_problem(ctx, op, pctx))
		return e2fsck_rebuild_extents_later(ctx, eti->ino);
	return 0;
}

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