busybox-1.19.3/e2fsprogs/old_e2fsprogs/e2fsck.c

/* vi: set sw=4 ts=4: */
/*
 * e2fsck
 *
 * Copyright (C) 1993, 1994, 1995, 1996, 1997 Theodore Ts'o.
 * Copyright (C) 2006 Garrett Kajmowicz
 *
 * Dictionary Abstract Data Type
 * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
 * Free Software License:
 * All rights are reserved by the author, with the following exceptions:
 * Permission is granted to freely reproduce and distribute this software,
 * possibly in exchange for a fee, provided that this copyright notice appears
 * intact. Permission is also granted to adapt this software to produce
 * derivative works, as long as the modified versions carry this copyright
 * notice and additional notices stating that the work has been modified.
 * This source code may be translated into executable form and incorporated
 * into proprietary software; there is no requirement for such software to
 * contain a copyright notice related to this source.
 *
 * linux/fs/recovery  and linux/fs/revoke
 * Written by Stephen C. Tweedie <sct@redhat.com>, 1999
 *
 * Copyright 1999-2000 Red Hat Software --- All Rights Reserved
 *
 * Journal recovery routines for the generic filesystem journaling code;
 * part of the ext2fs journaling system.
 *
 * Licensed under GPLv2 or later, see file LICENSE in this source tree.
 */

/*
//usage:#define e2fsck_trivial_usage
//usage:       "[-panyrcdfvstDFSV] [-b superblock] [-B blocksize] "
//usage:       "[-I inode_buffer_blocks] [-P process_inode_size] "
//usage:       "[-l|-L bad_blocks_file] [-C fd] [-j external_journal] "
//usage:       "[-E extended-options] device"
//usage:#define e2fsck_full_usage "\n\n"
//usage:       "Check ext2/ext3 file system\n"
//usage:     "\n	-p		Automatic repair (no questions)"
//usage:     "\n	-n		Make no changes to the filesystem"
//usage:     "\n	-y		Assume 'yes' to all questions"
//usage:     "\n	-c		Check for bad blocks and add them to the badblock list"
//usage:     "\n	-f		Force checking even if filesystem is marked clean"
//usage:     "\n	-v		Verbose"
//usage:     "\n	-b superblock	Use alternative superblock"
//usage:     "\n	-B blocksize	Force blocksize when looking for superblock"
//usage:     "\n	-j journal	Set location of the external journal"
//usage:     "\n	-l file		Add to badblocks list"
//usage:     "\n	-L file		Set badblocks list"
*/

#include "e2fsck.h"	/*Put all of our defines here to clean things up*/

#define _(x) x
#define N_(x) x

/*
 * Procedure declarations
 */

static void e2fsck_pass1_dupblocks(e2fsck_t ctx, char *block_buf);

/* pass1.c */
static void e2fsck_use_inode_shortcuts(e2fsck_t ctx, int bool);

/* pass2.c */
static int e2fsck_process_bad_inode(e2fsck_t ctx, ext2_ino_t dir,
				    ext2_ino_t ino, char *buf);

/* pass3.c */
static int e2fsck_reconnect_file(e2fsck_t ctx, ext2_ino_t inode);
static errcode_t e2fsck_expand_directory(e2fsck_t ctx, ext2_ino_t dir,
					 int num, int gauranteed_size);
static ext2_ino_t e2fsck_get_lost_and_found(e2fsck_t ctx, int fix);
static errcode_t e2fsck_adjust_inode_count(e2fsck_t ctx, ext2_ino_t ino,
					   int adj);

/* rehash.c */
static void e2fsck_rehash_directories(e2fsck_t ctx);

/* util.c */
static void *e2fsck_allocate_memory(e2fsck_t ctx, unsigned int size,
				    const char *description);
static int ask(e2fsck_t ctx, const char * string, int def);
static void e2fsck_read_bitmaps(e2fsck_t ctx);
static void preenhalt(e2fsck_t ctx);
static void e2fsck_read_inode(e2fsck_t ctx, unsigned long ino,
			      struct ext2_inode * inode, const char * proc);
static void e2fsck_write_inode(e2fsck_t ctx, unsigned long ino,
			       struct ext2_inode * inode, const char * proc);
static blk_t get_backup_sb(e2fsck_t ctx, ext2_filsys fs,
			   const char *name, io_manager manager);

/* unix.c */
static void e2fsck_clear_progbar(e2fsck_t ctx);
static int e2fsck_simple_progress(e2fsck_t ctx, const char *label,
				  float percent, unsigned int dpynum);


/*
 * problem.h --- e2fsck problem error codes
 */

typedef __u32 problem_t;

struct problem_context {
	errcode_t       errcode;
	ext2_ino_t      ino, ino2, dir;
	struct ext2_inode *inode;
	struct ext2_dir_entry *dirent;
	blk_t           blk, blk2;
	e2_blkcnt_t     blkcount;
	int             group;
	__u64           num;
	const char      *str;
};


/*
 * Function declarations
 */
static int fix_problem(e2fsck_t ctx, problem_t code, struct problem_context *pctx);
static int end_problem_latch(e2fsck_t ctx, int mask);
static int set_latch_flags(int mask, int setflags, int clearflags);
static void clear_problem_context(struct problem_context *ctx);

/*
 * Dictionary Abstract Data Type
 * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
 *
 * dict.h v 1.22.2.6 2000/11/13 01:36:44 kaz
 * kazlib_1_20
 */

#ifndef DICT_H
#define DICT_H

/*
 * Blurb for inclusion into C++ translation units
 */

typedef unsigned long dictcount_t;
#define DICTCOUNT_T_MAX ULONG_MAX

/*
 * The dictionary is implemented as a red-black tree
 */

typedef enum { dnode_red, dnode_black } dnode_color_t;

typedef struct dnode_t {
	struct dnode_t *dict_left;
	struct dnode_t *dict_right;
	struct dnode_t *dict_parent;
	dnode_color_t dict_color;
	const void *dict_key;
	void *dict_data;
} dnode_t;

typedef int (*dict_comp_t)(const void *, const void *);
typedef void (*dnode_free_t)(dnode_t *);

typedef struct dict_t {
	dnode_t dict_nilnode;
	dictcount_t dict_nodecount;
	dictcount_t dict_maxcount;
	dict_comp_t dict_compare;
	dnode_free_t dict_freenode;
	int dict_dupes;
} dict_t;

typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *);

typedef struct dict_load_t {
	dict_t *dict_dictptr;
	dnode_t dict_nilnode;
} dict_load_t;

#define dict_count(D) ((D)->dict_nodecount)
#define dnode_get(N) ((N)->dict_data)
#define dnode_getkey(N) ((N)->dict_key)

#endif

/*
 * Compatibility header file for e2fsck which should be included
 * instead of linux/jfs.h
 *
 * Copyright (C) 2000 Stephen C. Tweedie
 */

/*
 * Pull in the definition of the e2fsck context structure
 */

struct buffer_head {
	char            b_data[8192];
	e2fsck_t        b_ctx;
	io_channel      b_io;
	int             b_size;
	blk_t           b_blocknr;
	int             b_dirty;
	int             b_uptodate;
	int             b_err;
};


#define K_DEV_FS        1
#define K_DEV_JOURNAL   2

#define lock_buffer(bh) do {} while (0)
#define unlock_buffer(bh) do {} while (0)
#define buffer_req(bh) 1
#define do_readahead(journal, start) do {} while (0)

static e2fsck_t e2fsck_global_ctx;  /* Try your very best not to use this! */

typedef struct {
	int     object_length;
} kmem_cache_t;

#define kmem_cache_alloc(cache,flags) malloc((cache)->object_length)

/*
 * We use the standard libext2fs portability tricks for inline
 * functions.
 */

static kmem_cache_t * do_cache_create(int len)
{
	kmem_cache_t *new_cache;

	new_cache = xmalloc(sizeof(*new_cache));
	new_cache->object_length = len;
	return new_cache;
}

static void do_cache_destroy(kmem_cache_t *cache)
{
	free(cache);
}


/*
 * Dictionary Abstract Data Type
 */


/*
 * These macros provide short convenient names for structure members,
 * which are embellished with dict_ prefixes so that they are
 * properly confined to the documented namespace. It's legal for a
 * program which uses dict to define, for instance, a macro called ``parent''.
 * Such a macro would interfere with the dnode_t struct definition.
 * In general, highly portable and reusable C modules which expose their
 * structures need to confine structure member names to well-defined spaces.
 * The resulting identifiers aren't necessarily convenient to use, nor
 * readable, in the implementation, however!
 */

#define left dict_left
#define right dict_right
#define parent dict_parent
#define color dict_color
#define key dict_key
#define data dict_data

#define nilnode dict_nilnode
#define maxcount dict_maxcount
#define compare dict_compare
#define dupes dict_dupes

#define dict_root(D) ((D)->nilnode.left)
#define dict_nil(D) (&(D)->nilnode)

static void dnode_free(dnode_t *node);

/*
 * Perform a ``left rotation'' adjustment on the tree.  The given node P and
 * its right child C are rearranged so that the P instead becomes the left
 * child of C.   The left subtree of C is inherited as the new right subtree
 * for P.  The ordering of the keys within the tree is thus preserved.
 */

static void rotate_left(dnode_t *upper)
{
	dnode_t *lower, *lowleft, *upparent;

	lower = upper->right;
	upper->right = lowleft = lower->left;
	lowleft->parent = upper;

	lower->parent = upparent = upper->parent;

	/* don't need to check for root node here because root->parent is
	   the sentinel nil node, and root->parent->left points back to root */

	if (upper == upparent->left) {
		upparent->left = lower;
	} else {
		assert (upper == upparent->right);
		upparent->right = lower;
	}

	lower->left = upper;
	upper->parent = lower;
}

/*
 * This operation is the ``mirror'' image of rotate_left. It is
 * the same procedure, but with left and right interchanged.
 */

static void rotate_right(dnode_t *upper)
{
	dnode_t *lower, *lowright, *upparent;

	lower = upper->left;
	upper->left = lowright = lower->right;
	lowright->parent = upper;

	lower->parent = upparent = upper->parent;

	if (upper == upparent->right) {
		upparent->right = lower;
	} else {
		assert (upper == upparent->left);
		upparent->left = lower;
	}

	lower->right = upper;
	upper->parent = lower;
}

/*
 * Do a postorder traversal of the tree rooted at the specified
 * node and free everything under it.  Used by dict_free().
 */

static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
{
	if (node == nil)
		return;
	free_nodes(dict, node->left, nil);
	free_nodes(dict, node->right, nil);
	dict->dict_freenode(node);
}

/*
 * Verify that the tree contains the given node. This is done by
 * traversing all of the nodes and comparing their pointers to the
 * given pointer. Returns 1 if the node is found, otherwise
 * returns zero. It is intended for debugging purposes.
 */

static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)
{
	if (root != nil) {
		return root == node
			|| verify_dict_has_node(nil, root->left, node)
			|| verify_dict_has_node(nil, root->right, node);
	}
	return 0;
}


/*
 * Select a different set of node allocator routines.
 */

static void dict_set_allocator(dict_t *dict, dnode_free_t fr)
{
	assert(dict_count(dict) == 0);
	dict->dict_freenode = fr;
}

/*
 * Free all the nodes in the dictionary by using the dictionary's
 * installed free routine. The dictionary is emptied.
 */

static void dict_free_nodes(dict_t *dict)
{
	dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
	free_nodes(dict, root, nil);
	dict->dict_nodecount = 0;
	dict->nilnode.left = &dict->nilnode;
	dict->nilnode.right = &dict->nilnode;
}

/*
 * Initialize a user-supplied dictionary object.
 */

static dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp)
{
	dict->compare = comp;
	dict->dict_freenode = dnode_free;
	dict->dict_nodecount = 0;
	dict->maxcount = maxcount;
	dict->nilnode.left = &dict->nilnode;
	dict->nilnode.right = &dict->nilnode;
	dict->nilnode.parent = &dict->nilnode;
	dict->nilnode.color = dnode_black;
	dict->dupes = 0;
	return dict;
}

/*
 * Locate a node in the dictionary having the given key.
 * If the node is not found, a null a pointer is returned (rather than
 * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
 * located node is returned.
 */

static dnode_t *dict_lookup(dict_t *dict, const void *key)
{
	dnode_t *root = dict_root(dict);
	dnode_t *nil = dict_nil(dict);
	dnode_t *saved;
	int result;

	/* simple binary search adapted for trees that contain duplicate keys */

	while (root != nil) {
		result = dict->compare(key, root->key);
		if (result < 0)
			root = root->left;
		else if (result > 0)
			root = root->right;
		else {
			if (!dict->dupes) { /* no duplicates, return match          */
				return root;
			} else {            /* could be dupes, find leftmost one    */
				do {
					saved = root;
					root = root->left;
					while (root != nil && dict->compare(key, root->key))
						root = root->right;
				} while (root != nil);
				return saved;
			}
		}
	}

	return NULL;
}

/*
 * Insert a node into the dictionary. The node should have been
 * initialized with a data field. All other fields are ignored.
 * The behavior is undefined if the user attempts to insert into
 * a dictionary that is already full (for which the dict_isfull()
 * function returns true).
 */

static void dict_insert(dict_t *dict, dnode_t *node, const void *key)
{
	dnode_t *where = dict_root(dict), *nil = dict_nil(dict);
	dnode_t *parent = nil, *uncle, *grandpa;
	int result = -1;

	node->key = key;

	/* basic binary tree insert */

	while (where != nil) {
		parent = where;
		result = dict->compare(key, where->key);
		/* trap attempts at duplicate key insertion unless it's explicitly allowed */
		assert(dict->dupes || result != 0);
		if (result < 0)
			where = where->left;
		else
			where = where->right;
	}

	assert(where == nil);

	if (result < 0)
		parent->left = node;
	else
		parent->right = node;

	node->parent = parent;
	node->left = nil;
	node->right = nil;

	dict->dict_nodecount++;

	/* red black adjustments */

	node->color = dnode_red;

	while (parent->color == dnode_red) {
		grandpa = parent->parent;
		if (parent == grandpa->left) {
			uncle = grandpa->right;
			if (uncle->color == dnode_red) {    /* red parent, red uncle */
				parent->color = dnode_black;
				uncle->color = dnode_black;
				grandpa->color = dnode_red;
				node = grandpa;
				parent = grandpa->parent;
			} else {                            /* red parent, black uncle */
				if (node == parent->right) {
					rotate_left(parent);
					parent = node;
					assert (grandpa == parent->parent);
					/* rotation between parent and child preserves grandpa */
				}
				parent->color = dnode_black;
				grandpa->color = dnode_red;
				rotate_right(grandpa);
				break;
			}
		} else {        /* symmetric cases: parent == parent->parent->right */
			uncle = grandpa->left;
			if (uncle->color == dnode_red) {
				parent->color = dnode_black;
				uncle->color = dnode_black;
				grandpa->color = dnode_red;
				node = grandpa;
				parent = grandpa->parent;
			} else {
				if (node == parent->left) {
					rotate_right(parent);
					parent = node;
					assert (grandpa == parent->parent);
				}
				parent->color = dnode_black;
				grandpa->color = dnode_red;
				rotate_left(grandpa);
				break;
			}
		}
	}

	dict_root(dict)->color = dnode_black;
}

/*
 * Allocate a node using the dictionary's allocator routine, give it
 * the data item.
 */

static dnode_t *dnode_init(dnode_t *dnode, void *data)
{
	dnode->data = data;
	dnode->parent = NULL;
	dnode->left = NULL;
	dnode->right = NULL;
	return dnode;
}

static int dict_alloc_insert(dict_t *dict, const void *key, void *data)
{
	dnode_t *node = xmalloc(sizeof(dnode_t));

	dnode_init(node, data);
	dict_insert(dict, node, key);
	return 1;
}

/*
 * Return the node with the lowest (leftmost) key. If the dictionary is empty
 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
 */

static dnode_t *dict_first(dict_t *dict)
{
	dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;

	if (root != nil)
		while ((left = root->left) != nil)
			root = left;

	return (root == nil) ? NULL : root;
}

/*
 * Return the given node's successor node---the node which has the
 * next key in the left to right ordering. If the node has
 * no successor, a null pointer is returned rather than a pointer to
 * the nil node.
 */

static dnode_t *dict_next(dict_t *dict, dnode_t *curr)
{
	dnode_t *nil = dict_nil(dict), *parent, *left;

	if (curr->right != nil) {
		curr = curr->right;
		while ((left = curr->left) != nil)
			curr = left;
		return curr;
	}

	parent = curr->parent;

	while (parent != nil && curr == parent->right) {
		curr = parent;
		parent = curr->parent;
	}

	return (parent == nil) ? NULL : parent;
}


static void dnode_free(dnode_t *node)
{
	free(node);
}


#undef left
#undef right
#undef parent
#undef color
#undef key
#undef data

#undef nilnode
#undef maxcount
#undef compare
#undef dupes


/*
 * dirinfo.c --- maintains the directory information table for e2fsck.
 */

/*
 * This subroutine is called during pass1 to create a directory info
 * entry.  During pass1, the passed-in parent is 0; it will get filled
 * in during pass2.
 */
static void e2fsck_add_dir_info(e2fsck_t ctx, ext2_ino_t ino, ext2_ino_t parent)
{
	struct dir_info *dir;
	int             i, j;
	ext2_ino_t      num_dirs;
	errcode_t       retval;
	unsigned long   old_size;

	if (!ctx->dir_info) {
		ctx->dir_info_count = 0;
		retval = ext2fs_get_num_dirs(ctx->fs, &num_dirs);
		if (retval)
			num_dirs = 1024;        /* Guess */
		ctx->dir_info_size = num_dirs + 10;
		ctx->dir_info  = (struct dir_info *)
			e2fsck_allocate_memory(ctx, ctx->dir_info_size
					       * sizeof (struct dir_info),
					       "directory map");
	}

	if (ctx->dir_info_count >= ctx->dir_info_size) {
		old_size = ctx->dir_info_size * sizeof(struct dir_info);
		ctx->dir_info_size += 10;
		retval = ext2fs_resize_mem(old_size, ctx->dir_info_size *
					   sizeof(struct dir_info),
					   &ctx->dir_info);
		if (retval) {
			ctx->dir_info_size -= 10;
			return;
		}
	}

	/*
	 * Normally, add_dir_info is called with each inode in
	 * sequential order; but once in a while (like when pass 3
	 * needs to recreate the root directory or lost+found
	 * directory) it is called out of order.  In those cases, we
	 * need to move the dir_info entries down to make room, since
	 * the dir_info array needs to be sorted by inode number for
	 * get_dir_info()'s sake.
	 */
	if (ctx->dir_info_count &&
	    ctx->dir_info[ctx->dir_info_count-1].ino >= ino) {
		for (i = ctx->dir_info_count-1; i > 0; i--)
			if (ctx->dir_info[i-1].ino < ino)
				break;
		dir = &ctx->dir_info[i];
		if (dir->ino != ino)
			for (j = ctx->dir_info_count++; j > i; j--)
				ctx->dir_info[j] = ctx->dir_info[j-1];
	} else
		dir = &ctx->dir_info[ctx->dir_info_count++];

	dir->ino = ino;
	dir->dotdot = parent;
	dir->parent = parent;
}

/*
 * get_dir_info() --- given an inode number, try to find the directory
 * information entry for it.
 */
static struct dir_info *e2fsck_get_dir_info(e2fsck_t ctx, ext2_ino_t ino)
{
	int     low, high, mid;

	low = 0;
	high = ctx->dir_info_count-1;
	if (!ctx->dir_info)
		return 0;
	if (ino == ctx->dir_info[low].ino)
		return &ctx->dir_info[low];
	if  (ino == ctx->dir_info[high].ino)
		return &ctx->dir_info[high];

	while (low < high) {
		mid = (low+high)/2;
		if (mid == low || mid == high)
			break;
		if (ino == ctx->dir_info[mid].ino)
			return &ctx->dir_info[mid];
		if (ino < ctx->dir_info[mid].ino)
			high = mid;
		else
			low = mid;
	}
	return 0;
}

/*
 * Free the dir_info structure when it isn't needed any more.
 */
static void e2fsck_free_dir_info(e2fsck_t ctx)
{
	ext2fs_free_mem(&ctx->dir_info);
	ctx->dir_info_size = 0;
	ctx->dir_info_count = 0;
}

/*
 * Return the count of number of directories in the dir_info structure
 */
static int e2fsck_get_num_dirinfo(e2fsck_t ctx)
{
	return ctx->dir_info_count;
}

/*
 * A simple interator function
 */
static struct dir_info *e2fsck_dir_info_iter(e2fsck_t ctx, int *control)
{
	if (*control >= ctx->dir_info_count)
		return 0;

	return ctx->dir_info + (*control)++;
}

/*
 * dirinfo.c --- maintains the directory information table for e2fsck.
 *
 */

#ifdef ENABLE_HTREE

/*
 * This subroutine is called during pass1 to create a directory info
 * entry.  During pass1, the passed-in parent is 0; it will get filled
 * in during pass2.
 */
static void e2fsck_add_dx_dir(e2fsck_t ctx, ext2_ino_t ino, int num_blocks)
{
	struct dx_dir_info *dir;
	int             i, j;
	errcode_t       retval;
	unsigned long   old_size;

	if (!ctx->dx_dir_info) {
		ctx->dx_dir_info_count = 0;
		ctx->dx_dir_info_size = 100; /* Guess */
		ctx->dx_dir_info  = (struct dx_dir_info *)
			e2fsck_allocate_memory(ctx, ctx->dx_dir_info_size
					       * sizeof (struct dx_dir_info),
					       "directory map");
	}

	if (ctx->dx_dir_info_count >= ctx->dx_dir_info_size) {
		old_size = ctx->dx_dir_info_size * sizeof(struct dx_dir_info);
		ctx->dx_dir_info_size += 10;
		retval = ext2fs_resize_mem(old_size, ctx->dx_dir_info_size *
					   sizeof(struct dx_dir_info),
					   &ctx->dx_dir_info);
		if (retval) {
			ctx->dx_dir_info_size -= 10;
			return;
		}
	}

	/*
	 * Normally, add_dx_dir_info is called with each inode in
	 * sequential order; but once in a while (like when pass 3
	 * needs to recreate the root directory or lost+found
	 * directory) it is called out of order.  In those cases, we
	 * need to move the dx_dir_info entries down to make room, since
	 * the dx_dir_info array needs to be sorted by inode number for
	 * get_dx_dir_info()'s sake.
	 */
	if (ctx->dx_dir_info_count &&
	    ctx->dx_dir_info[ctx->dx_dir_info_count-1].ino >= ino) {
		for (i = ctx->dx_dir_info_count-1; i > 0; i--)
			if (ctx->dx_dir_info[i-1].ino < ino)
				break;
		dir = &ctx->dx_dir_info[i];
		if (dir->ino != ino)
			for (j = ctx->dx_dir_info_count++; j > i; j--)
				ctx->dx_dir_info[j] = ctx->dx_dir_info[j-1];
	} else
		dir = &ctx->dx_dir_info[ctx->dx_dir_info_count++];

	dir->ino = ino;
	dir->numblocks = num_blocks;
	dir->hashversion = 0;
	dir->dx_block = e2fsck_allocate_memory(ctx, num_blocks
				       * sizeof (struct dx_dirblock_info),
				       "dx_block info array");
}

/*
 * get_dx_dir_info() --- given an inode number, try to find the directory
 * information entry for it.
 */
static struct dx_dir_info *e2fsck_get_dx_dir_info(e2fsck_t ctx, ext2_ino_t ino)
{
	int     low, high, mid;

	low = 0;
	high = ctx->dx_dir_info_count-1;
	if (!ctx->dx_dir_info)
		return 0;
	if (ino == ctx->dx_dir_info[low].ino)
		return &ctx->dx_dir_info[low];
	if  (ino == ctx->dx_dir_info[high].ino)
		return &ctx->dx_dir_info[high];

	while (low < high) {
		mid = (low+high)/2;
		if (mid == low || mid == high)
			break;
		if (ino == ctx->dx_dir_info[mid].ino)
			return &ctx->dx_dir_info[mid];
		if (ino < ctx->dx_dir_info[mid].ino)
			high = mid;
		else
			low = mid;
	}
	return 0;
}

/*
 * Free the dx_dir_info structure when it isn't needed any more.
 */
static void e2fsck_free_dx_dir_info(e2fsck_t ctx)
{
	int     i;
	struct dx_dir_info *dir;

	if (ctx->dx_dir_info) {
		dir = ctx->dx_dir_info;
		for (i=0; i < ctx->dx_dir_info_count; i++) {
			ext2fs_free_mem(&dir->dx_block);
		}
		ext2fs_free_mem(&ctx->dx_dir_info);
	}
	ctx->dx_dir_info_size = 0;
	ctx->dx_dir_info_count = 0;
}

/*
 * A simple interator function
 */
static struct dx_dir_info *e2fsck_dx_dir_info_iter(e2fsck_t ctx, int *control)
{
	if (*control >= ctx->dx_dir_info_count)
		return 0;

	return ctx->dx_dir_info + (*control)++;
}

#endif /* ENABLE_HTREE */
/*
 * e2fsck.c - a consistency checker for the new extended file system.
 *
 */

/*
 * This function allocates an e2fsck context
 */
static errcode_t e2fsck_allocate_context(e2fsck_t *ret)
{
	e2fsck_t        context;
	errcode_t       retval;

	retval = ext2fs_get_mem(sizeof(struct e2fsck_struct), &context);
	if (retval)
		return retval;

	memset(context, 0, sizeof(struct e2fsck_struct));

	context->process_inode_size = 256;
	context->ext_attr_ver = 2;

	*ret = context;
	return 0;
}

struct ea_refcount_el {
	blk_t   ea_blk;
	int     ea_count;
};

struct ea_refcount {
	blk_t           count;
	blk_t           size;
	blk_t           cursor;
	struct ea_refcount_el   *list;
};

static void ea_refcount_free(ext2_refcount_t refcount)
{
	if (!refcount)
		return;

	ext2fs_free_mem(&refcount->list);
	ext2fs_free_mem(&refcount);
}

/*
 * This function resets an e2fsck context; it is called when e2fsck
 * needs to be restarted.
 */
static errcode_t e2fsck_reset_context(e2fsck_t ctx)
{
	ctx->flags = 0;
	ctx->lost_and_found = 0;
	ctx->bad_lost_and_found = 0;
	ext2fs_free_inode_bitmap(ctx->inode_used_map);
	ctx->inode_used_map = 0;
	ext2fs_free_inode_bitmap(ctx->inode_dir_map);
	ctx->inode_dir_map = 0;
	ext2fs_free_inode_bitmap(ctx->inode_reg_map);
	ctx->inode_reg_map = 0;
	ext2fs_free_block_bitmap(ctx->block_found_map);
	ctx->block_found_map = 0;
	ext2fs_free_icount(ctx->inode_link_info);
	ctx->inode_link_info = 0;
	if (ctx->journal_io) {
		if (ctx->fs && ctx->fs->io != ctx->journal_io)
			io_channel_close(ctx->journal_io);
		ctx->journal_io = 0;
	}
	if (ctx->fs) {
		ext2fs_free_dblist(ctx->fs->dblist);
		ctx->fs->dblist = 0;
	}
	e2fsck_free_dir_info(ctx);
#ifdef ENABLE_HTREE
	e2fsck_free_dx_dir_info(ctx);
#endif
	ea_refcount_free(ctx->refcount);
	ctx->refcount = 0;
	ea_refcount_free(ctx->refcount_extra);
	ctx->refcount_extra = 0;
	ext2fs_free_block_bitmap(ctx->block_dup_map);
	ctx->block_dup_map = 0;
	ext2fs_free_block_bitmap(ctx->block_ea_map);
	ctx->block_ea_map = 0;
	ext2fs_free_inode_bitmap(ctx->inode_bad_map);
	ctx->inode_bad_map = 0;
	ext2fs_free_inode_bitmap(ctx->inode_imagic_map);
	ctx->inode_imagic_map = 0;
	ext2fs_u32_list_free(ctx->dirs_to_hash);
	ctx->dirs_to_hash = 0;

	/*
	 * Clear the array of invalid meta-data flags
	 */
	ext2fs_free_mem(&ctx->invalid_inode_bitmap_flag);
	ext2fs_free_mem(&ctx->invalid_block_bitmap_flag);
	ext2fs_free_mem(&ctx->invalid_inode_table_flag);

	/* Clear statistic counters */
	ctx->fs_directory_count = 0;
	ctx->fs_regular_count = 0;
	ctx->fs_blockdev_count = 0;
	ctx->fs_chardev_count = 0;
	ctx->fs_links_count = 0;
	ctx->fs_symlinks_count = 0;
	ctx->fs_fast_symlinks_count = 0;
	ctx->fs_fifo_count = 0;
	ctx->fs_total_count = 0;
	ctx->fs_sockets_count = 0;
	ctx->fs_ind_count = 0;
	ctx->fs_dind_count = 0;
	ctx->fs_tind_count = 0;
	ctx->fs_fragmented = 0;
	ctx->large_files = 0;

	/* Reset the superblock to the user's requested value */
	ctx->superblock = ctx->use_superblock;

	return 0;
}

static void e2fsck_free_context(e2fsck_t ctx)
{
	if (!ctx)
		return;

	e2fsck_reset_context(ctx);
	if (ctx->blkid)
		blkid_put_cache(ctx->blkid);

	ext2fs_free_mem(&ctx);
}

/*
 * ea_refcount.c
 */

/*
 * The strategy we use for keeping track of EA refcounts is as
 * follows.  We keep a sorted array of first EA blocks and its
 * reference counts.  Once the refcount has dropped to zero, it is
 * removed from the array to save memory space.  Once the EA block is
 * checked, its bit is set in the block_ea_map bitmap.
 */


static errcode_t ea_refcount_create(int size, ext2_refcount_t *ret)
{
	ext2_refcount_t refcount;
	errcode_t       retval;
	size_t          bytes;

	retval = ext2fs_get_mem(sizeof(struct ea_refcount), &refcount);
	if (retval)
		return retval;
	memset(refcount, 0, sizeof(struct ea_refcount));

	if (!size)
		size = 500;
	refcount->size = size;
	bytes = (size_t) (size * sizeof(struct ea_refcount_el));
#ifdef DEBUG
	printf("Refcount allocated %d entries, %d bytes.\n",
	       refcount->size, bytes);
#endif
	retval = ext2fs_get_mem(bytes, &refcount->list);
	if (retval)
		goto errout;
	memset(refcount->list, 0, bytes);

	refcount->count = 0;
	refcount->cursor = 0;

	*ret = refcount;
	return 0;

errout:
	ea_refcount_free(refcount);
	return retval;
}

/*
 * collapse_refcount() --- go through the refcount array, and get rid
 * of any count == zero entries
 */
static void refcount_collapse(ext2_refcount_t refcount)
{
	unsigned int    i, j;
	struct ea_refcount_el   *list;

	list = refcount->list;
	for (i = 0, j = 0; i < refcount->count; i++) {
		if (list[i].ea_count) {
			if (i != j)
				list[j] = list[i];
			j++;
		}
	}
#if defined(DEBUG) || defined(TEST_PROGRAM)
	printf("Refcount_collapse: size was %d, now %d\n",
	       refcount->count, j);
#endif
	refcount->count = j;
}


/*
 * insert_refcount_el() --- Insert a new entry into the sorted list at a
 *      specified position.
 */
static struct ea_refcount_el *insert_refcount_el(ext2_refcount_t refcount,
						 blk_t blk, int pos)
{
	struct ea_refcount_el   *el;
	errcode_t               retval;
	blk_t                   new_size = 0;
	int                     num;

	if (refcount->count >= refcount->size) {
		new_size = refcount->size + 100;
#ifdef DEBUG
		printf("Reallocating refcount %d entries...\n", new_size);
#endif
		retval = ext2fs_resize_mem((size_t) refcount->size *
					   sizeof(struct ea_refcount_el),
					   (size_t) new_size *
					   sizeof(struct ea_refcount_el),
					   &refcount->list);
		if (retval)
			return 0;
		refcount->size = new_size;
	}
	num = (int) refcount->count - pos;
	if (num < 0)
		return 0;       /* should never happen */
	if (num) {
		memmove(&refcount->list[pos+1], &refcount->list[pos],
			sizeof(struct ea_refcount_el) * num);
	}
	refcount->count++;
	el = &refcount->list[pos];
	el->ea_count = 0;
	el->ea_blk = blk;
	return el;
}


/*
 * get_refcount_el() --- given an block number, try to find refcount
 *      information in the sorted list.  If the create flag is set,
 *      and we can't find an entry, create one in the sorted list.
 */
static struct ea_refcount_el *get_refcount_el(ext2_refcount_t refcount,
					      blk_t blk, int create)
{
	float   range;
	int     low, high, mid;
	blk_t   lowval, highval;

	if (!refcount || !refcount->list)
		return 0;
retry:
	low = 0;
	high = (int) refcount->count-1;
	if (create && ((refcount->count == 0) ||
		       (blk > refcount->list[high].ea_blk))) {
		if (refcount->count >= refcount->size)
			refcount_collapse(refcount);

		return insert_refcount_el(refcount, blk,
					  (unsigned) refcount->count);
	}
	if (refcount->count == 0)
		return 0;

	if (refcount->cursor >= refcount->count)
		refcount->cursor = 0;
	if (blk == refcount->list[refcount->cursor].ea_blk)
		return &refcount->list[refcount->cursor++];
#ifdef DEBUG
	printf("Non-cursor get_refcount_el: %u\n", blk);
#endif
	while (low <= high) {
		if (low == high)
			mid = low;
		else {
			/* Interpolate for efficiency */
			lowval = refcount->list[low].ea_blk;
			highval = refcount->list[high].ea_blk;

			if (blk < lowval)
				range = 0;
			else if (blk > highval)
				range = 1;
			else
				range = ((float) (blk - lowval)) /
					(highval - lowval);
			mid = low + ((int) (range * (high-low)));
		}

		if (blk == refcount->list[mid].ea_blk) {
			refcount->cursor = mid+1;
			return &refcount->list[mid];
		}
		if (blk < refcount->list[mid].ea_blk)
			high = mid-1;
		else
			low = mid+1;
	}
	/*
	 * If we need to create a new entry, it should be right at
	 * low (where high will be left at low-1).
	 */
	if (create) {
		if (refcount->count >= refcount->size) {
			refcount_collapse(refcount);
			if (refcount->count < refcount->size)
				goto retry;
		}
		return insert_refcount_el(refcount, blk, low);
	}
	return 0;
}

static errcode_t
ea_refcount_increment(ext2_refcount_t refcount, blk_t blk, int *ret)
{
	struct ea_refcount_el   *el;

	el = get_refcount_el(refcount, blk, 1);
	if (!el)
		return EXT2_ET_NO_MEMORY;
	el->ea_count++;

	if (ret)
		*ret = el->ea_count;
	return 0;
}

static errcode_t
ea_refcount_decrement(ext2_refcount_t refcount, blk_t blk, int *ret)
{
	struct ea_refcount_el   *el;

	el = get_refcount_el(refcount, blk, 0);
	if (!el || el->ea_count == 0)
		return EXT2_ET_INVALID_ARGUMENT;

	el->ea_count--;

	if (ret)
		*ret = el->ea_count;
	return 0;
}

static errcode_t
ea_refcount_store(ext2_refcount_t refcount, blk_t blk, int count)
{
	struct ea_refcount_el   *el;

	/*
	 * Get the refcount element
	 */
	el = get_refcount_el(refcount, blk, count ? 1 : 0);
	if (!el)
		return count ? EXT2_ET_NO_MEMORY : 0;
	el->ea_count = count;
	return 0;
}

static inline void ea_refcount_intr_begin(ext2_refcount_t refcount)
{
	refcount->cursor = 0;
}


static blk_t ea_refcount_intr_next(ext2_refcount_t refcount, int *ret)
{
	struct ea_refcount_el   *list;

	while (1) {
		if (refcount->cursor >= refcount->count)
			return 0;
		list = refcount->list;
		if (list[refcount->cursor].ea_count) {
			if (ret)
				*ret = list[refcount->cursor].ea_count;
			return list[refcount->cursor++].ea_blk;
		}
		refcount->cursor++;
	}
}


/*
 * ehandler.c --- handle bad block errors which come up during the
 *      course of an e2fsck session.
 */


static const char *operation;

static errcode_t
e2fsck_handle_read_error(io_channel channel, unsigned long block, int count,
			 void *data, size_t size FSCK_ATTR((unused)),
			 int actual FSCK_ATTR((unused)), errcode_t error)
{
	int     i;
	char    *p;
	ext2_filsys fs = (ext2_filsys) channel->app_data;
	e2fsck_t ctx;

	ctx = (e2fsck_t) fs->priv_data;

	/*
	 * If more than one block was read, try reading each block
	 * separately.  We could use the actual bytes read to figure
	 * out where to start, but we don't bother.
	 */
	if (count > 1) {
		p = (char *) data;
		for (i=0; i < count; i++, p += channel->block_size, block++) {
			error = io_channel_read_blk(channel, block,
						    1, p);
			if (error)
				return error;
		}
		return 0;
	}
	if (operation)
		printf(_("Error reading block %lu (%s) while %s.  "), block,
		       error_message(error), operation);
	else
		printf(_("Error reading block %lu (%s).  "), block,
		       error_message(error));
	preenhalt(ctx);
	if (ask(ctx, _("Ignore error"), 1)) {
		if (ask(ctx, _("Force rewrite"), 1))
			io_channel_write_blk(channel, block, 1, data);
		return 0;
	}

	return error;
}

static errcode_t
e2fsck_handle_write_error(io_channel channel, unsigned long block, int count,
			const void *data, size_t size FSCK_ATTR((unused)),
			int actual FSCK_ATTR((unused)), errcode_t error)
{
	int             i;
	const char      *p;
	ext2_filsys fs = (ext2_filsys) channel->app_data;
	e2fsck_t ctx;

	ctx = (e2fsck_t) fs->priv_data;

	/*
	 * If more than one block was written, try writing each block
	 * separately.  We could use the actual bytes read to figure
	 * out where to start, but we don't bother.
	 */
	if (count > 1) {
		p = (const char *) data;
		for (i=0; i < count; i++, p += channel->block_size, block++) {
			error = io_channel_write_blk(channel, block,
						     1, p);
			if (error)
				return error;
		}
		return 0;
	}

	if (operation)
		printf(_("Error writing block %lu (%s) while %s.  "), block,
		       error_message(error), operation);
	else
		printf(_("Error writing block %lu (%s).  "), block,
		       error_message(error));
	preenhalt(ctx);
	if (ask(ctx, _("Ignore error"), 1))
		return 0;

	return error;
}

static const char *ehandler_operation(const char *op)
{
	const char *ret = operation;

	operation = op;
	return ret;
}

static void ehandler_init(io_channel channel)
{
	channel->read_error = e2fsck_handle_read_error;
	channel->write_error = e2fsck_handle_write_error;
}

/*
 * journal.c --- code for handling the "ext3" journal
 *
 * Copyright (C) 2000 Andreas Dilger
 * Copyright (C) 2000 Theodore Ts'o
 *
 * Parts of the code are based on fs/jfs/journal.c by Stephen C. Tweedie
 * Copyright (C) 1999 Red Hat Software
 *
 * This file may be redistributed under the terms of the
 * GNU General Public License version 2 or at your discretion
 * any later version.
 */

/*
 * Define USE_INODE_IO to use the inode_io.c / fileio.c codepaths.
 * This creates a larger static binary, and a smaller binary using
 * shared libraries.  It's also probably slightly less CPU-efficient,
 * which is why it's not on by default.  But, it's a good way of
 * testing the functions in inode_io.c and fileio.c.
 */
#undef USE_INODE_IO

/* Kernel compatibility functions for handling the journal.  These allow us
 * to use the recovery.c file virtually unchanged from the kernel, so we
 * don't have to do much to keep kernel and user recovery in sync.
 */
static int journal_bmap(journal_t *journal, blk_t block, unsigned long *phys)
{
#ifdef USE_INODE_IO
	*phys = block;
	return 0;
#else
	struct inode    *inode = journal->j_inode;
	errcode_t       retval;
	blk_t           pblk;

	if (!inode) {
		*phys = block;
		return 0;
	}

	retval= ext2fs_bmap(inode->i_ctx->fs, inode->i_ino,
			    &inode->i_ext2, NULL, 0, block, &pblk);
	*phys = pblk;
	return retval;
#endif
}

static struct buffer_head *getblk(kdev_t kdev, blk_t blocknr, int blocksize)
{
	struct buffer_head *bh;

	bh = e2fsck_allocate_memory(kdev->k_ctx, sizeof(*bh), "block buffer");
	if (!bh)
		return NULL;

	bh->b_ctx = kdev->k_ctx;
	if (kdev->k_dev == K_DEV_FS)
		bh->b_io = kdev->k_ctx->fs->io;
	else
		bh->b_io = kdev->k_ctx->journal_io;
	bh->b_size = blocksize;
	bh->b_blocknr = blocknr;

	return bh;
}

static void sync_blockdev(kdev_t kdev)
{
	io_channel      io;

	if (kdev->k_dev == K_DEV_FS)
		io = kdev->k_ctx->fs->io;
	else
		io = kdev->k_ctx->journal_io;

	io_channel_flush(io);
}

static void ll_rw_block(int rw, int nr, struct buffer_head *bhp[])
{
	int retval;
	struct buffer_head *bh;

	for (; nr > 0; --nr) {
		bh = *bhp++;
		if (rw == READ && !bh->b_uptodate) {
			retval = io_channel_read_blk(bh->b_io,
						     bh->b_blocknr,
						     1, bh->b_data);
			if (retval) {
				bb_error_msg("while reading block %lu",
					(unsigned long) bh->b_blocknr);
				bh->b_err = retval;
				continue;
			}
			bh->b_uptodate = 1;
		} else if (rw == WRITE && bh->b_dirty) {
			retval = io_channel_write_blk(bh->b_io,
						      bh->b_blocknr,
						      1, bh->b_data);
			if (retval) {
				bb_error_msg("while writing block %lu",
					(unsigned long) bh->b_blocknr);
				bh->b_err = retval;
				continue;
			}
			bh->b_dirty = 0;
			bh->b_uptodate = 1;
		}
	}
}

static void mark_buffer_dirty(struct buffer_head *bh)
{
	bh->b_dirty = 1;
}

static inline void mark_buffer_clean(struct buffer_head * bh)
{
	bh->b_dirty = 0;
}

static void brelse(struct buffer_head *bh)
{
	if (bh->b_dirty)
		ll_rw_block(WRITE, 1, &bh);
	ext2fs_free_mem(&bh);
}

static int buffer_uptodate(struct buffer_head *bh)
{
	return bh->b_uptodate;
}

static inline void mark_buffer_uptodate(struct buffer_head *bh, int val)
{
	bh->b_uptodate = val;
}

static void wait_on_buffer(struct buffer_head *bh)
{
	if (!bh->b_uptodate)
		ll_rw_block(READ, 1, &bh);
}


static void e2fsck_clear_recover(e2fsck_t ctx, int error)
{
	ctx->fs->super->s_feature_incompat &= ~EXT3_FEATURE_INCOMPAT_RECOVER;

	/* if we had an error doing journal recovery, we need a full fsck */
	if (error)
		ctx->fs->super->s_state &= ~EXT2_VALID_FS;
	ext2fs_mark_super_dirty(ctx->fs);
}

static errcode_t e2fsck_get_journal(e2fsck_t ctx, journal_t **ret_journal)
{
	struct ext2_super_block *sb = ctx->fs->super;
	struct ext2_super_block jsuper;
	struct problem_context  pctx;
	struct buffer_head      *bh;
	struct inode            *j_inode = NULL;
	struct kdev_s           *dev_fs = NULL, *dev_journal;
	const char              *journal_name = NULL;
	journal_t               *journal = NULL;
	errcode_t               retval = 0;
	io_manager              io_ptr = 0;
	unsigned long           start = 0;
	blk_t                   blk;
	int                     ext_journal = 0;
	int                     tried_backup_jnl = 0;
	int                     i;

	clear_problem_context(&pctx);

	journal = e2fsck_allocate_memory(ctx, sizeof(journal_t), "journal");
	if (!journal) {
		return EXT2_ET_NO_MEMORY;
	}

	dev_fs = e2fsck_allocate_memory(ctx, 2*sizeof(struct kdev_s), "kdev");
	if (!dev_fs) {
		retval = EXT2_ET_NO_MEMORY;
		goto errout;
	}
	dev_journal = dev_fs+1;

	dev_fs->k_ctx = dev_journal->k_ctx = ctx;
	dev_fs->k_dev = K_DEV_FS;
	dev_journal->k_dev = K_DEV_JOURNAL;

	journal->j_dev = dev_journal;
	journal->j_fs_dev = dev_fs;
	journal->j_inode = NULL;
	journal->j_blocksize = ctx->fs->blocksize;

	if (uuid_is_null(sb->s_journal_uuid)) {
		if (!sb->s_journal_inum)
			return EXT2_ET_BAD_INODE_NUM;
		j_inode = e2fsck_allocate_memory(ctx, sizeof(*j_inode),
						 "journal inode");
		if (!j_inode) {
			retval = EXT2_ET_NO_MEMORY;
			goto errout;
		}

		j_inode->i_ctx = ctx;
		j_inode->i_ino = sb->s_journal_inum;

		if ((retval = ext2fs_read_inode(ctx->fs,
						sb->s_journal_inum,
						&j_inode->i_ext2))) {
		try_backup_journal:
			if (sb->s_jnl_backup_type != EXT3_JNL_BACKUP_BLOCKS ||
			    tried_backup_jnl)
				goto errout;
			memset(&j_inode->i_ext2, 0, sizeof(struct ext2_inode));
			memcpy(&j_inode->i_ext2.i_block[0], sb->s_jnl_blocks,
			       EXT2_N_BLOCKS*4);
			j_inode->i_ext2.i_size = sb->s_jnl_blocks[16];
			j_inode->i_ext2.i_links_count = 1;
			j_inode->i_ext2.i_mode = LINUX_S_IFREG | 0600;
			tried_backup_jnl++;
		}
		if (!j_inode->i_ext2.i_links_count ||
		    !LINUX_S_ISREG(j_inode->i_ext2.i_mode)) {
			retval = EXT2_ET_NO_JOURNAL;
			goto try_backup_journal;
		}
		if (j_inode->i_ext2.i_size / journal->j_blocksize <
		    JFS_MIN_JOURNAL_BLOCKS) {
			retval = EXT2_ET_JOURNAL_TOO_SMALL;
			goto try_backup_journal;
		}
		for (i=0; i < EXT2_N_BLOCKS; i++) {
			blk = j_inode->i_ext2.i_block[i];
			if (!blk) {
				if (i < EXT2_NDIR_BLOCKS) {
					retval = EXT2_ET_JOURNAL_TOO_SMALL;
					goto try_backup_journal;
				}
				continue;
			}
			if (blk < sb->s_first_data_block ||
			    blk >= sb->s_blocks_count) {
				retval = EXT2_ET_BAD_BLOCK_NUM;
				goto try_backup_journal;
			}
		}
		journal->j_maxlen = j_inode->i_ext2.i_size / journal->j_blocksize;

#ifdef USE_INODE_IO
		retval = ext2fs_inode_io_intern2(ctx->fs, sb->s_journal_inum,
						 &j_inode->i_ext2,
						 &journal_name);
		if (retval)
			goto errout;

		io_ptr = inode_io_manager;
#else
		journal->j_inode = j_inode;
		ctx->journal_io = ctx->fs->io;
		if ((retval = journal_bmap(journal, 0, &start)) != 0)
			goto errout;
#endif
	} else {
		ext_journal = 1;
		if (!ctx->journal_name) {
			char uuid[37];

			uuid_unparse(sb->s_journal_uuid, uuid);
			ctx->journal_name = blkid_get_devname(ctx->blkid,
							      "UUID", uuid);
			if (!ctx->journal_name)
				ctx->journal_name = blkid_devno_to_devname(sb->s_journal_dev);
		}
		journal_name = ctx->journal_name;

		if (!journal_name) {
			fix_problem(ctx, PR_0_CANT_FIND_JOURNAL, &pctx);
			return EXT2_ET_LOAD_EXT_JOURNAL;
		}

		io_ptr = unix_io_manager;
	}

#ifndef USE_INODE_IO
	if (ext_journal)
#endif
		retval = io_ptr->open(journal_name, IO_FLAG_RW,
				      &ctx->journal_io);
	if (retval)
		goto errout;

	io_channel_set_blksize(ctx->journal_io, ctx->fs->blocksize);

	if (ext_journal) {
		if (ctx->fs->blocksize == 1024)
			start = 1;
		bh = getblk(dev_journal, start, ctx->fs->blocksize);
		if (!bh) {
			retval = EXT2_ET_NO_MEMORY;
			goto errout;
		}
		ll_rw_block(READ, 1, &bh);
		if ((retval = bh->b_err) != 0)
			goto errout;
		memcpy(&jsuper, start ? bh->b_data :  bh->b_data + 1024,
		       sizeof(jsuper));
		brelse(bh);
#if BB_BIG_ENDIAN
		if (jsuper.s_magic == ext2fs_swab16(EXT2_SUPER_MAGIC))
			ext2fs_swap_super(&jsuper);
#endif
		if (jsuper.s_magic != EXT2_SUPER_MAGIC ||
		    !(jsuper.s_feature_incompat & EXT3_FEATURE_INCOMPAT_JOURNAL_DEV)) {
			fix_problem(ctx, PR_0_EXT_JOURNAL_BAD_SUPER, &pctx);
			retval = EXT2_ET_LOAD_EXT_JOURNAL;
			goto errout;
		}
		/* Make sure the journal UUID is correct */
		if (memcmp(jsuper.s_uuid, ctx->fs->super->s_journal_uuid,
			   sizeof(jsuper.s_uuid))) {
			fix_problem(ctx, PR_0_JOURNAL_BAD_UUID, &pctx);
			retval = EXT2_ET_LOAD_EXT_JOURNAL;
			goto errout;
		}

		journal->j_maxlen = jsuper.s_blocks_count;
		start++;
	}

	if (!(bh = getblk(dev_journal, start, journal->j_blocksize))) {
		retval = EXT2_ET_NO_MEMORY;
		goto errout;
	}

	journal->j_sb_buffer = bh;
	journal->j_superblock = (journal_superblock_t *)bh->b_data;

#ifdef USE_INODE_IO
	ext2fs_free_mem(&j_inode);
#endif

	*ret_journal = journal;
	return 0;

errout:
	ext2fs_free_mem(&dev_fs);
	ext2fs_free_mem(&j_inode);
	ext2fs_free_mem(&journal);
	return retval;
}

static errcode_t e2fsck_journal_fix_bad_inode(e2fsck_t ctx,
					      struct problem_context *pctx)
{
	struct ext2_super_block *sb = ctx->fs->super;
	int recover = ctx->fs->super->s_feature_incompat &
		EXT3_FEATURE_INCOMPAT_RECOVER;
	int has_journal = ctx->fs->super->s_feature_compat &
		EXT3_FEATURE_COMPAT_HAS_JOURNAL;

	if (has_journal || sb->s_journal_inum) {
		/* The journal inode is bogus, remove and force full fsck */
		pctx->ino = sb->s_journal_inum;
		if (fix_problem(ctx, PR_0_JOURNAL_BAD_INODE, pctx)) {
			if (has_journal && sb->s_journal_inum)
				printf("*** ext3 journal has been deleted - "
				       "filesystem is now ext2 only ***\n\n");
			sb->s_feature_compat &= ~EXT3_FEATURE_COMPAT_HAS_JOURNAL;
			sb->s_journal_inum = 0;
			ctx->flags |= E2F_FLAG_JOURNAL_INODE; /* FIXME: todo */
			e2fsck_clear_recover(ctx, 1);
			return 0;
		}
		return EXT2_ET_BAD_INODE_NUM;
	} else if (recover) {
		if (fix_problem(ctx, PR_0_JOURNAL_RECOVER_SET, pctx)) {
			e2fsck_clear_recover(ctx, 1);
			return 0;
		}
		return EXT2_ET_UNSUPP_FEATURE;
	}
	return 0;
}

#define V1_SB_SIZE      0x0024
static void clear_v2_journal_fields(journal_t *journal)
{
	e2fsck_t ctx = journal->j_dev->k_ctx;
	struct problem_context pctx;

	clear_problem_context(&pctx);

	if (!fix_problem(ctx, PR_0_CLEAR_V2_JOURNAL, &pctx))
		return;

	memset(((char *) journal->j_superblock) + V1_SB_SIZE, 0,
	       ctx->fs->blocksize-V1_SB_SIZE);
	mark_buffer_dirty(journal->j_sb_buffer);
}


static errcode_t e2fsck_journal_load(journal_t *journal)
{
	e2fsck_t ctx = journal->j_dev->k_ctx;
	journal_superblock_t *jsb;
	struct buffer_head *jbh = journal->j_sb_buffer;
	struct problem_context pctx;

	clear_problem_context(&pctx);

	ll_rw_block(READ, 1, &jbh);
	if (jbh->b_err) {
		bb_error_msg(_("reading journal superblock"));
		return jbh->b_err;
	}

	jsb = journal->j_superblock;
	/* If we don't even have JFS_MAGIC, we probably have a wrong inode */
	if (jsb->s_header.h_magic != htonl(JFS_MAGIC_NUMBER))
		return e2fsck_journal_fix_bad_inode(ctx, &pctx);

	switch (ntohl(jsb->s_header.h_blocktype)) {
	case JFS_SUPERBLOCK_V1:
		journal->j_format_version = 1;
		if (jsb->s_feature_compat ||
		    jsb->s_feature_incompat ||
		    jsb->s_feature_ro_compat ||
		    jsb->s_nr_users)
			clear_v2_journal_fields(journal);
		break;

	case JFS_SUPERBLOCK_V2:
		journal->j_format_version = 2;
		if (ntohl(jsb->s_nr_users) > 1 &&
		    uuid_is_null(ctx->fs->super->s_journal_uuid))
			clear_v2_journal_fields(journal);
		if (ntohl(jsb->s_nr_users) > 1) {
			fix_problem(ctx, PR_0_JOURNAL_UNSUPP_MULTIFS, &pctx);
			return EXT2_ET_JOURNAL_UNSUPP_VERSION;
		}
		break;

	/*
	 * These should never appear in a journal super block, so if
	 * they do, the journal is badly corrupted.
	 */
	case JFS_DESCRIPTOR_BLOCK:
	case JFS_COMMIT_BLOCK:
	case JFS_REVOKE_BLOCK:
		return EXT2_ET_CORRUPT_SUPERBLOCK;

	/* If we don't understand the superblock major type, but there
	 * is a magic number, then it is likely to be a new format we
	 * just don't understand, so leave it alone. */
	default:
		return EXT2_ET_JOURNAL_UNSUPP_VERSION;
	}

	if (JFS_HAS_INCOMPAT_FEATURE(journal, ~JFS_KNOWN_INCOMPAT_FEATURES))
		return EXT2_ET_UNSUPP_FEATURE;

	if (JFS_HAS_RO_COMPAT_FEATURE(journal, ~JFS_KNOWN_ROCOMPAT_FEATURES))
		return EXT2_ET_RO_UNSUPP_FEATURE;

	/* We have now checked whether we know enough about the journal
	 * format to be able to proceed safely, so any other checks that
	 * fail we should attempt to recover from. */
	if (jsb->s_blocksize != htonl(journal->j_blocksize)) {
		bb_error_msg(_("%s: no valid journal superblock found"),
			ctx->device_name);
		return EXT2_ET_CORRUPT_SUPERBLOCK;
	}

	if (ntohl(jsb->s_maxlen) < journal->j_maxlen)
		journal->j_maxlen = ntohl(jsb->s_maxlen);
	else if (ntohl(jsb->s_maxlen) > journal->j_maxlen) {
		bb_error_msg(_("%s: journal too short"),
			ctx->device_name);
		return EXT2_ET_CORRUPT_SUPERBLOCK;
	}

	journal->j_tail_sequence = ntohl(jsb->s_sequence);
	journal->j_transaction_sequence = journal->j_tail_sequence;
	journal->j_tail = ntohl(jsb->s_start);
	journal->j_first = ntohl(jsb->s_first);
	journal->j_last = ntohl(jsb->s_maxlen);

	return 0;
}

static void e2fsck_journal_reset_super(e2fsck_t ctx, journal_superblock_t *jsb,
				       journal_t *journal)
{
	char *p;
	union {
		uuid_t uuid;
		__u32 val[4];
	} u;
	__u32 new_seq = 0;
	int i;

	/* Leave a valid existing V1 superblock signature alone.
	 * Anything unrecognizable we overwrite with a new V2
	 * signature. */

	if (jsb->s_header.h_magic != htonl(JFS_MAGIC_NUMBER) ||
	    jsb->s_header.h_blocktype != htonl(JFS_SUPERBLOCK_V1)) {
		jsb->s_header.h_magic = htonl(JFS_MAGIC_NUMBER);
		jsb->s_header.h_blocktype = htonl(JFS_SUPERBLOCK_V2);
	}

	/* Zero out everything else beyond the superblock header */

	p = ((char *) jsb) + sizeof(journal_header_t);
	memset (p, 0, ctx->fs->blocksize-sizeof(journal_header_t));

	jsb->s_blocksize = htonl(ctx->fs->blocksize);
	jsb->s_maxlen = htonl(journal->j_maxlen);
	jsb->s_first = htonl(1);

	/* Initialize the journal sequence number so that there is "no"
	 * chance we will find old "valid" transactions in the journal.
	 * This avoids the need to zero the whole journal (slow to do,
	 * and risky when we are just recovering the filesystem).
	 */
	uuid_generate(u.uuid);
	for (i = 0; i < 4; i ++)
		new_seq ^= u.val[i];
	jsb->s_sequence = htonl(new_seq);

	mark_buffer_dirty(journal->j_sb_buffer);
	ll_rw_block(WRITE, 1, &journal->j_sb_buffer);
}

static errcode_t e2fsck_journal_fix_corrupt_super(e2fsck_t ctx,
						  journal_t *journal,
						  struct problem_context *pctx)
{
	struct ext2_super_block *sb = ctx->fs->super;
	int recover = ctx->fs->super->s_feature_incompat &
		EXT3_FEATURE_INCOMPAT_RECOVER;

	if (sb->s_feature_compat & EXT3_FEATURE_COMPAT_HAS_JOURNAL) {
		if (fix_problem(ctx, PR_0_JOURNAL_BAD_SUPER, pctx)) {
			e2fsck_journal_reset_super(ctx, journal->j_superblock,
						   journal);
			journal->j_transaction_sequence = 1;
			e2fsck_clear_recover(ctx, recover);
			return 0;
		}
		return EXT2_ET_CORRUPT_SUPERBLOCK;
	} else if (e2fsck_journal_fix_bad_inode(ctx, pctx))
		return EXT2_ET_CORRUPT_SUPERBLOCK;

	return 0;
}

static void e2fsck_journal_release(e2fsck_t ctx, journal_t *journal,
				   int reset, int drop)
{
	journal_superblock_t *jsb;

	if (drop)
		mark_buffer_clean(journal->j_sb_buffer);
	else if (!(ctx->options & E2F_OPT_READONLY)) {
		jsb = journal->j_superblock;
		jsb->s_sequence = htonl(journal->j_transaction_sequence);
		if (reset)
			jsb->s_start = 0; /* this marks the journal as empty */
		mark_buffer_dirty(journal->j_sb_buffer);
	}
	brelse(journal->j_sb_buffer);

	if (ctx->journal_io) {
		if (ctx->fs && ctx->fs->io != ctx->journal_io)
			io_channel_close(ctx->journal_io);
		ctx->journal_io = 0;
	}

#ifndef USE_INODE_IO
	ext2fs_free_mem(&journal->j_inode);
#endif
	ext2fs_free_mem(&journal->j_fs_dev);
	ext2fs_free_mem(&journal);
}

/*
 * This function makes sure that the superblock fields regarding the
 * journal are consistent.
 */
static int e2fsck_check_ext3_journal(e2fsck_t ctx)
{
	struct ext2_super_block *sb = ctx->fs->super;
	journal_t *journal;
	int recover = ctx->fs->super->s_feature_incompat &
		EXT3_FEATURE_INCOMPAT_RECOVER;
	struct problem_context pctx;
	problem_t problem;
	int reset = 0, force_fsck = 0;
	int retval;

	/* If we don't have any journal features, don't do anything more */
	if (!(sb->s_feature_compat & EXT3_FEATURE_COMPAT_HAS_JOURNAL) &&
	    !recover && sb->s_journal_inum == 0 && sb->s_journal_dev == 0 &&
	    uuid_is_null(sb->s_journal_uuid))
		return 0;

	clear_problem_context(&pctx);
	pctx.num = sb->s_journal_inum;

	retval = e2fsck_get_journal(ctx, &journal);
	if (retval) {
		if ((retval == EXT2_ET_BAD_INODE_NUM) ||
		    (retval == EXT2_ET_BAD_BLOCK_NUM) ||
		    (retval == EXT2_ET_JOURNAL_TOO_SMALL) ||
		    (retval == EXT2_ET_NO_JOURNAL))
			return e2fsck_journal_fix_bad_inode(ctx, &pctx);
		return retval;
	}

	retval = e2fsck_journal_load(journal);
	if (retval) {
		if ((retval == EXT2_ET_CORRUPT_SUPERBLOCK) ||
		    ((retval == EXT2_ET_UNSUPP_FEATURE) &&
		    (!fix_problem(ctx, PR_0_JOURNAL_UNSUPP_INCOMPAT,
				  &pctx))) ||
		    ((retval == EXT2_ET_RO_UNSUPP_FEATURE) &&
		    (!fix_problem(ctx, PR_0_JOURNAL_UNSUPP_ROCOMPAT,
				  &pctx))) ||
		    ((retval == EXT2_ET_JOURNAL_UNSUPP_VERSION) &&
		    (!fix_problem(ctx, PR_0_JOURNAL_UNSUPP_VERSION, &pctx))))
			retval = e2fsck_journal_fix_corrupt_super(ctx, journal,
								  &pctx);
		e2fsck_journal_release(ctx, journal, 0, 1);
		return retval;
	}

	/*
	 * We want to make the flags consistent here.  We will not leave with
	 * needs_recovery set but has_journal clear.  We can't get in a loop
	 * with -y, -n, or -p, only if a user isn't making up their mind.
	 */
no_has_journal:
	if (!(sb->s_feature_compat & EXT3_FEATURE_COMPAT_HAS_JOURNAL)) {
		recover = sb->s_feature_incompat & EXT3_FEATURE_INCOMPAT_RECOVER;
		pctx.str = "inode";
		if (fix_problem(ctx, PR_0_JOURNAL_HAS_JOURNAL, &pctx)) {
			if (recover &&
			    !fix_problem(ctx, PR_0_JOURNAL_RECOVER_SET, &pctx))
				goto no_has_journal;
			/*
			 * Need a full fsck if we are releasing a
			 * journal stored on a reserved inode.
			 */
			force_fsck = recover ||
				(sb->s_journal_inum < EXT2_FIRST_INODE(sb));
			/* Clear all of the journal fields */
			sb->s_journal_inum = 0;
			sb->s_journal_dev = 0;
			memset(sb->s_journal_uuid, 0,
			       sizeof(sb->s_journal_uuid));
			e2fsck_clear_recover(ctx, force_fsck);
		} else if (!(ctx->options & E2F_OPT_READONLY)) {
			sb->s_feature_compat |= EXT3_FEATURE_COMPAT_HAS_JOURNAL;
			ext2fs_mark_super_dirty(ctx->fs);
		}
	}

	if (sb->s_feature_compat & EXT3_FEATURE_COMPAT_HAS_JOURNAL &&
	    !(sb->s_feature_incompat & EXT3_FEATURE_INCOMPAT_RECOVER) &&
	    journal->j_superblock->s_start != 0) {
		/* Print status information */
		fix_problem(ctx, PR_0_JOURNAL_RECOVERY_CLEAR, &pctx);
		if (ctx->superblock)
			problem = PR_0_JOURNAL_RUN_DEFAULT;
		else
			problem = PR_0_JOURNAL_RUN;
		if (fix_problem(ctx, problem, &pctx)) {
			ctx->options |= E2F_OPT_FORCE;
			sb->s_feature_incompat |=
				EXT3_FEATURE_INCOMPAT_RECOVER;
			ext2fs_mark_super_dirty(ctx->fs);
		} else if (fix_problem(ctx,
				       PR_0_JOURNAL_RESET_JOURNAL, &pctx)) {
			reset = 1;
			sb->s_state &= ~EXT2_VALID_FS;
			ext2fs_mark_super_dirty(ctx->fs);
		}
		/*
		 * If the user answers no to the above question, we
		 * ignore the fact that journal apparently has data;
		 * accidentally replaying over valid data would be far
		 * worse than skipping a questionable recovery.
		 *
		 * XXX should we abort with a fatal error here?  What
		 * will the ext3 kernel code do if a filesystem with
		 * !NEEDS_RECOVERY but with a non-zero
		 * journal->j_superblock->s_start is mounted?
		 */
	}

	e2fsck_journal_release(ctx, journal, reset, 0);
	return retval;
}

static errcode_t recover_ext3_journal(e2fsck_t ctx)
{
	journal_t *journal;
	int retval;

	journal_init_revoke_caches();
	retval = e2fsck_get_journal(ctx, &journal);
	if (retval)
		return retval;

	retval = e2fsck_journal_load(journal);
	if (retval)
		goto errout;

	retval = journal_init_revoke(journal, 1024);
	if (retval)
		goto errout;

	retval = -journal_recover(journal);
	if (retval)
		goto errout;

	if (journal->j_superblock->s_errno) {
		ctx->fs->super->s_state |= EXT2_ERROR_FS;
		ext2fs_mark_super_dirty(ctx->fs);
		journal->j_superblock->s_errno = 0;
		mark_buffer_dirty(journal->j_sb_buffer);
	}

errout:
	journal_destroy_revoke(journal);
	journal_destroy_revoke_caches();
	e2fsck_journal_release(ctx, journal, 1, 0);
	return retval;
}

static int e2fsck_run_ext3_journal(e2fsck_t ctx)
{
	io_manager io_ptr = ctx->fs->io->manager;
	int blocksize = ctx->fs->blocksize;
	errcode_t       retval, recover_retval;

	printf(_("%s: recovering journal\n"), ctx->device_name);
	if (ctx->options & E2F_OPT_READONLY) {
		printf(_("%s: won't do journal recovery while read-only\n"),
		       ctx->device_name);
		return EXT2_ET_FILE_RO;
	}

	if (ctx->fs->flags & EXT2_FLAG_DIRTY)
		ext2fs_flush(ctx->fs);  /* Force out any modifications */

	recover_retval = recover_ext3_journal(ctx);

	/*
	 * Reload the filesystem context to get up-to-date data from disk
	 * because journal recovery will change the filesystem under us.
	 */
	ext2fs_close(ctx->fs);
	retval = ext2fs_open(ctx->filesystem_name, EXT2_FLAG_RW,
			     ctx->superblock, blocksize, io_ptr,
			     &ctx->fs);

	if (retval) {
		bb_error_msg(_("while trying to re-open %s"),
			ctx->device_name);
		bb_error_msg_and_die(0);
	}
	ctx->fs->priv_data = ctx;

	/* Set the superblock flags */
	e2fsck_clear_recover(ctx, recover_retval);
	return recover_retval;
}

/*
 * This function will move the journal inode from a visible file in
 * the filesystem directory hierarchy to the reserved inode if necessary.
 */
static const char *const journal_names[] = {
	".journal", "journal", ".journal.dat", "journal.dat", 0 };

static void e2fsck_move_ext3_journal(e2fsck_t ctx)
{
	struct ext2_super_block *sb = ctx->fs->super;
	struct problem_context  pctx;
	struct ext2_inode       inode;
	ext2_filsys             fs = ctx->fs;
	ext2_ino_t              ino;
	errcode_t               retval;
	const char *const *    cpp;
	int                     group, mount_flags;

	clear_problem_context(&pctx);

	/*
	 * If the filesystem is opened read-only, or there is no
	 * journal, then do nothing.
	 */
	if ((ctx->options & E2F_OPT_READONLY) ||
	    (sb->s_journal_inum == 0) ||
	    !(sb->s_feature_compat & EXT3_FEATURE_COMPAT_HAS_JOURNAL))
		return;

	/*
	 * Read in the journal inode
	 */
	if (ext2fs_read_inode(fs, sb->s_journal_inum, &inode) != 0)
		return;

	/*
	 * If it's necessary to backup the journal inode, do so.
	 */
	if ((sb->s_jnl_backup_type == 0) ||
	    ((sb->s_jnl_backup_type == EXT3_JNL_BACKUP_BLOCKS) &&
	     memcmp(inode.i_block, sb->s_jnl_blocks, EXT2_N_BLOCKS*4))) {
		if (fix_problem(ctx, PR_0_BACKUP_JNL, &pctx)) {
			memcpy(sb->s_jnl_blocks, inode.i_block,
			       EXT2_N_BLOCKS*4);
			sb->s_jnl_blocks[16] = inode.i_size;
			sb->s_jnl_backup_type = EXT3_JNL_BACKUP_BLOCKS;
			ext2fs_mark_super_dirty(fs);
			fs->flags &= ~EXT2_FLAG_MASTER_SB_ONLY;
		}
	}

	/*
	 * If the journal is already the hidden inode, then do nothing
	 */
	if (sb->s_journal_inum == EXT2_JOURNAL_INO)
		return;

	/*
	 * The journal inode had better have only one link and not be readable.
	 */
	if (inode.i_links_count != 1)
		return;

	/*
	 * If the filesystem is mounted, or we can't tell whether
	 * or not it's mounted, do nothing.
	 */
	retval = ext2fs_check_if_mounted(ctx->filesystem_name, &mount_flags);
	if (retval || (mount_flags & EXT2_MF_MOUNTED))
		return;

	/*
	 * If we can't find the name of the journal inode, then do
	 * nothing.
	 */
	for (cpp = journal_names; *cpp; cpp++) {
		retval = ext2fs_lookup(fs, EXT2_ROOT_INO, *cpp,
				       strlen(*cpp), 0, &ino);
		if ((retval == 0) && (ino == sb->s_journal_inum))
			break;
	}
	if (*cpp == 0)
		return;

	/* We need the inode bitmap to be loaded */
	retval = ext2fs_read_bitmaps(fs);
	if (retval)
		return;

	pctx.str = *cpp;
	if (!fix_problem(ctx, PR_0_MOVE_JOURNAL, &pctx))
		return;

	/*
	 * OK, we've done all the checks, let's actually move the
	 * journal inode.  Errors at this point mean we need to force
	 * an ext2 filesystem check.
	 */
	if ((retval = ext2fs_unlink(fs, EXT2_ROOT_INO, *cpp, ino, 0)) != 0)
		goto err_out;
	if ((retval = ext2fs_write_inode(fs, EXT2_JOURNAL_INO, &inode)) != 0)
		goto err_out;
	sb->s_journal_inum = EXT2_JOURNAL_INO;
	ext2fs_mark_super_dirty(fs);
	fs->flags &= ~EXT2_FLAG_MASTER_SB_ONLY;
	inode.i_links_count = 0;
	inode.i_dtime = time(NULL);
	if ((retval = ext2fs_write_inode(fs, ino, &inode)) != 0)
		goto err_out;

	group = ext2fs_group_of_ino(fs, ino);
	ext2fs_unmark_inode_bitmap(fs->inode_map, ino);
	ext2fs_mark_ib_dirty(fs);
	fs->group_desc[group].bg_free_inodes_count++;
	fs->super->s_free_inodes_count++;
	return;

err_out:
	pctx.errcode = retval;
	fix_problem(ctx, PR_0_ERR_MOVE_JOURNAL, &pctx);
	fs->super->s_state &= ~EXT2_VALID_FS;
	ext2fs_mark_super_dirty(fs);
}

/*
 * message.c --- print e2fsck messages (with compression)
 *
 * print_e2fsck_message() prints a message to the user, using
 * compression techniques and expansions of abbreviations.
 *
 * The following % expansions are supported:
 *
 *      %b      <blk>                   block number
 *      %B      <blkcount>              integer
 *      %c      <blk2>                  block number
 *      %Di     <dirent>->ino           inode number
 *      %Dn     <dirent>->name          string
 *      %Dr     <dirent>->rec_len
 *      %Dl     <dirent>->name_len
 *      %Dt     <dirent>->filetype
 *      %d      <dir>                   inode number
 *      %g      <group>                 integer
 *      %i      <ino>                   inode number
 *      %Is     <inode> -> i_size
 *      %IS     <inode> -> i_extra_isize
 *      %Ib     <inode> -> i_blocks
 *      %Il     <inode> -> i_links_count
 *      %Im     <inode> -> i_mode
 *      %IM     <inode> -> i_mtime
 *      %IF     <inode> -> i_faddr
 *      %If     <inode> -> i_file_acl
 *      %Id     <inode> -> i_dir_acl
 *      %Iu     <inode> -> i_uid
 *      %Ig     <inode> -> i_gid
 *      %j      <ino2>                  inode number
 *      %m      <com_err error message>
 *      %N      <num>
 *      %p      ext2fs_get_pathname of directory <ino>
 *      %P      ext2fs_get_pathname of <dirent>->ino with <ino2> as
 *                      the containing directory.  (If dirent is NULL
 *                      then return the pathname of directory <ino2>)
 *      %q      ext2fs_get_pathname of directory <dir>
 *      %Q      ext2fs_get_pathname of directory <ino> with <dir> as
 *                      the containing directory.
 *      %s      <str>                   miscellaneous string
 *      %S      backup superblock
 *      %X      <num> hexadecimal format
 *
 * The following '@' expansions are supported:
 *
 *      @a      extended attribute
 *      @A      error allocating
 *      @b      block
 *      @B      bitmap
 *      @c      compress
 *      @C      conflicts with some other fs block
 *      @D      deleted
 *      @d      directory
 *      @e      entry
 *      @E      Entry '%Dn' in %p (%i)
 *      @f      filesystem
 *      @F      for @i %i (%Q) is
 *      @g      group
 *      @h      HTREE directory inode
 *      @i      inode
 *      @I      illegal
 *      @j      journal
 *      @l      lost+found
 *      @L      is a link
 *      @m      multiply-claimed
 *      @n      invalid
 *      @o      orphaned
 *      @p      problem in
 *      @r      root inode
 *      @s      should be
 *      @S      superblock
 *      @u      unattached
 *      @v      device
 *      @z      zero-length
 */


/*
 * This structure defines the abbreviations used by the text strings
 * below.  The first character in the string is the index letter.  An
 * abbreviation of the form '@<i>' is expanded by looking up the index
 * letter <i> in the table below.
 */
static const char *const abbrevs[] = {
	N_("aextended attribute"),
	N_("Aerror allocating"),
	N_("bblock"),
	N_("Bbitmap"),
	N_("ccompress"),
	N_("Cconflicts with some other fs @b"),
	N_("iinode"),
	N_("Iillegal"),
	N_("jjournal"),
	N_("Ddeleted"),
	N_("ddirectory"),
	N_("eentry"),
	N_("E@e '%Dn' in %p (%i)"),
	N_("ffilesystem"),
	N_("Ffor @i %i (%Q) is"),
	N_("ggroup"),
	N_("hHTREE @d @i"),
	N_("llost+found"),
	N_("Lis a link"),
	N_("mmultiply-claimed"),
	N_("ninvalid"),
	N_("oorphaned"),
	N_("pproblem in"),
	N_("rroot @i"),
	N_("sshould be"),
	N_("Ssuper@b"),
	N_("uunattached"),
	N_("vdevice"),
	N_("zzero-length"),
	"@@",
	0
	};

/*
 * Give more user friendly names to the "special" inodes.
 */
#define num_special_inodes      11
static const char *const special_inode_name[] =
{
	N_("<The NULL inode>"),                 /* 0 */
	N_("<The bad blocks inode>"),           /* 1 */
	"/",                                    /* 2 */
	N_("<The ACL index inode>"),            /* 3 */
	N_("<The ACL data inode>"),             /* 4 */
	N_("<The boot loader inode>"),          /* 5 */
	N_("<The undelete directory inode>"),   /* 6 */
	N_("<The group descriptor inode>"),     /* 7 */
	N_("<The journal inode>"),              /* 8 */
	N_("<Reserved inode 9>"),               /* 9 */
	N_("<Reserved inode 10>"),              /* 10 */
};

/*
 * This function does "safe" printing.  It will convert non-printable
 * ASCII characters using '^' and M- notation.
 */
static void safe_print(const char *cp, int len)
{
	unsigned char   ch;

	if (len < 0)
		len = strlen(cp);

	while (len--) {
		ch = *cp++;
		if (ch > 128) {
			fputs("M-", stdout);
			ch -= 128;
		}
		if ((ch < 32) || (ch == 0x7f)) {
			bb_putchar('^');
			ch ^= 0x40; /* ^@, ^A, ^B; ^? for DEL */
		}
		bb_putchar(ch);
	}
}


/*
 * This function prints a pathname, using the ext2fs_get_pathname
 * function
 */
static void print_pathname(ext2_filsys fs, ext2_ino_t dir, ext2_ino_t ino)
{
	errcode_t       retval;
	char            *path;

	if (!dir && (ino < num_special_inodes)) {
		fputs(_(special_inode_name[ino]), stdout);
		return;
	}

	retval = ext2fs_get_pathname(fs, dir, ino, &path);
	if (retval)
		fputs("???", stdout);
	else {
		safe_print(path, -1);
		ext2fs_free_mem(&path);
	}
}

static void print_e2fsck_message(e2fsck_t ctx, const char *msg,
			  struct problem_context *pctx, int first);
/*
 * This function handles the '@' expansion.  We allow recursive
 * expansion; an @ expression can contain further '@' and '%'
 * expressions.
 */
static void expand_at_expression(e2fsck_t ctx, char ch,
					  struct problem_context *pctx,
					  int *first)
{
	const char *const *cpp;
	const char *str;

	/* Search for the abbreviation */
	for (cpp = abbrevs; *cpp; cpp++) {
		if (ch == *cpp[0])
			break;
	}
	if (*cpp) {
		str = _(*cpp) + 1;
		if (*first && islower(*str)) {
			*first = 0;
			bb_putchar(toupper(*str++));
		}
		print_e2fsck_message(ctx, str, pctx, *first);
	} else
		printf("@%c", ch);
}

/*
 * This function expands '%IX' expressions
 */
static void expand_inode_expression(char ch,
					     struct problem_context *ctx)
{
	struct ext2_inode       *inode;
	struct ext2_inode_large *large_inode;
	char *                  time_str;
	time_t                  t;
	int                     do_gmt = -1;

	if (!ctx || !ctx->inode)
		goto no_inode;

	inode = ctx->inode;
	large_inode = (struct ext2_inode_large *) inode;

	switch (ch) {
	case 's':
		if (LINUX_S_ISDIR(inode->i_mode))
			printf("%u", inode->i_size);
		else {
			printf("%"PRIu64, (inode->i_size |
					((uint64_t) inode->i_size_high << 32)));
		}
		break;
	case 'S':
		printf("%u", large_inode->i_extra_isize);
		break;
	case 'b':
		printf("%u", inode->i_blocks);
		break;
	case 'l':
		printf("%d", inode->i_links_count);
		break;
	case 'm':
		printf("0%o", inode->i_mode);
		break;
	case 'M':
		/* The diet libc doesn't respect the TZ environemnt variable */
		if (do_gmt == -1) {
			time_str = getenv("TZ");
			if (!time_str)
				time_str = "";
			do_gmt = !strcmp(time_str, "GMT");
		}
		t = inode->i_mtime;
		time_str = asctime(do_gmt ? gmtime(&t) : localtime(&t));
		printf("%.24s", time_str);
		break;
	case 'F':
		printf("%u", inode->i_faddr);
		break;
	case 'f':
		printf("%u", inode->i_file_acl);
		break;
	case 'd':
		printf("%u", (LINUX_S_ISDIR(inode->i_mode) ?
			      inode->i_dir_acl : 0));
		break;
	case 'u':
		printf("%d", (inode->i_uid |
			      (inode->osd2.linux2.l_i_uid_high << 16)));
		break;
	case 'g':
		printf("%d", (inode->i_gid |
			      (inode->osd2.linux2.l_i_gid_high << 16)));
		break;
	default:
	no_inode:
		printf("%%I%c", ch);
		break;
	}
}

/*
 * This function expands '%dX' expressions
 */
static void expand_dirent_expression(char ch,
					      struct problem_context *ctx)
{
	struct ext2_dir_entry   *dirent;
	int     len;

	if (!ctx || !ctx->dirent)
		goto no_dirent;

	dirent = ctx->dirent;

	switch (ch) {
	case 'i':
		printf("%u", dirent->inode);
		break;
	case 'n':
		len = dirent->name_len & 0xFF;
		if (len > EXT2_NAME_LEN)
			len = EXT2_NAME_LEN;
		if (len > dirent->rec_len)
			len = dirent->rec_len;
		safe_print(dirent->name, len);
		break;
	case 'r':
		printf("%u", dirent->rec_len);
		break;
	case 'l':
		printf("%u", dirent->name_len & 0xFF);
		break;
	case 't':
		printf("%u", dirent->name_len >> 8);
		break;
	default:
	no_dirent:
		printf("%%D%c", ch);
		break;
	}
}

static void expand_percent_expression(ext2_filsys fs, char ch,
					       struct problem_context *ctx)
{
	if (!ctx)
		goto no_context;

	switch (ch) {
	case '%':
		bb_putchar('%');
		break;
	case 'b':
		printf("%u", ctx->blk);
		break;
	case 'B':
		printf("%"PRIi64, ctx->blkcount);
		break;
	case 'c':
		printf("%u", ctx->blk2);
		break;
	case 'd':
		printf("%u", ctx->dir);
		break;
	case 'g':
		printf("%d", ctx->group);
		break;
	case 'i':
		printf("%u", ctx->ino);
		break;
	case 'j':
		printf("%u", ctx->ino2);
		break;
	case 'm':
		fputs(error_message(ctx->errcode), stdout);
		break;
	case 'N':
		printf("%"PRIi64, ctx->num);
		break;
	case 'p':
		print_pathname(fs, ctx->ino, 0);
		break;
	case 'P':
		print_pathname(fs, ctx->ino2,
			       ctx->dirent ? ctx->dirent->inode : 0);
		break;
	case 'q':
		print_pathname(fs, ctx->dir, 0);
		break;
	case 'Q':
		print_pathname(fs, ctx->dir, ctx->ino);
		break;
	case 'S':
		printf("%d", get_backup_sb(NULL, fs, NULL, NULL));
		break;
	case 's':
		fputs((ctx->str ? ctx->str : "NULL"), stdout);
		break;
	case 'X':
		printf("0x%"PRIi64, ctx->num);
		break;
	default:
	no_context:
		printf("%%%c", ch);
		break;
	}
}


static void print_e2fsck_message(e2fsck_t ctx, const char *msg,
			  struct problem_context *pctx, int first)
{
	ext2_filsys fs = ctx->fs;
	const char *    cp;
	int             i;

	e2fsck_clear_progbar(ctx);
	for (cp = msg; *cp; cp++) {
		if (cp[0] == '@') {
			cp++;
			expand_at_expression(ctx, *cp, pctx, &first);
		} else if (cp[0] == '%' && cp[1] == 'I') {
			cp += 2;
			expand_inode_expression(*cp, pctx);
		} else if (cp[0] == '%' && cp[1] == 'D') {
			cp += 2;
			expand_dirent_expression(*cp, pctx);
		} else if ((cp[0] == '%')) {
			cp++;
			expand_percent_expression(fs, *cp, pctx);
		} else {
			for (i=0; cp[i]; i++)
				if ((cp[i] == '@') || cp[i] == '%')
					break;
			printf("%.*s", i, cp);
			cp += i-1;
		}
		first = 0;
	}
}


/*
 * region.c --- code which manages allocations within a region.
 */

struct region_el {
	region_addr_t   start;
	region_addr_t   end;
	struct region_el *next;
};

struct region_struct {
	region_addr_t   min;
	region_addr_t   max;
	struct region_el *allocated;
};

static region_t region_create(region_addr_t min, region_addr_t max)
{
	region_t        region;

	region = xzalloc(sizeof(struct region_struct));
	region->min = min;
	region->max = max;
	return region;
}

static void region_free(region_t region)
{
	struct region_el        *r, *next;

	for (r = region->allocated; r; r = next) {
		next = r->next;
		free(r);
	}
	memset(region, 0, sizeof(struct region_struct));
	free(region);
}

static int region_allocate(region_t region, region_addr_t start, int n)
{
	struct region_el        *r, *new_region, *prev, *next;
	region_addr_t end;

	end = start+n;
	if ((start < region->min) || (end > region->max))
		return -1;
	if (n == 0)
		return 1;

	/*
	 * Search through the linked list.  If we find that it
	 * conflicts witih something that's already allocated, return
	 * 1; if we can find an existing region which we can grow, do
	 * so.  Otherwise, stop when we find the appropriate place
	 * insert a new region element into the linked list.
	 */
	for (r = region->allocated, prev=NULL; r; prev = r, r = r->next) {
		if (((start >= r->start) && (start < r->end)) ||
		    ((end > r->start) && (end <= r->end)) ||
		    ((start <= r->start) && (end >= r->end)))
			return 1;
		if (end == r->start) {
			r->start = start;
			return 0;
		}
		if (start == r->end) {
			if ((next = r->next)) {
				if (end > next->start)
					return 1;
				if (end == next->start) {
					r->end = next->end;
					r->next = next->next;
					free(next);
					return 0;
				}
			}
			r->end = end;
			return 0;
		}
		if (start < r->start)
			break;
	}
	/*
	 * Insert a new region element structure into the linked list
	 */
	new_region = xmalloc(sizeof(struct region_el));
	new_region->start = start;
	new_region->end = start + n;
	new_region->next = r;
	if (prev)
		prev->next = new_region;
	else
		region->allocated = new_region;
	return 0;
}

/*
 * pass1.c -- pass #1 of e2fsck: sequential scan of the inode table
 *
 * Pass 1 of e2fsck iterates over all the inodes in the filesystems,
 * and applies the following tests to each inode:
 *
 *      - The mode field of the inode must be legal.
 *      - The size and block count fields of the inode are correct.
 *      - A data block must not be used by another inode
 *
 * Pass 1 also gathers the collects the following information:
 *
 *      - A bitmap of which inodes are in use.          (inode_used_map)
 *      - A bitmap of which inodes are directories.     (inode_dir_map)
 *      - A bitmap of which inodes are regular files.   (inode_reg_map)
 *      - A bitmap of which inodes have bad fields.     (inode_bad_map)
 *      - A bitmap of which inodes are imagic inodes.   (inode_imagic_map)
 *      - A bitmap of which blocks are in use.          (block_found_map)
 *      - A bitmap of which blocks are in use by two inodes     (block_dup_map)
 *      - The data blocks of the directory inodes.      (dir_map)
 *
 * Pass 1 is designed to stash away enough information so that the
 * other passes should not need to read in the inode information
 * during the normal course of a filesystem check.  (Althogh if an
 * inconsistency is detected, other passes may need to read in an
 * inode to fix it.)
 *
 * Note that pass 1B will be invoked if there are any duplicate blocks
 * found.
 */


static int process_block(ext2_filsys fs, blk_t  *blocknr,
			 e2_blkcnt_t blockcnt, blk_t ref_blk,
			 int ref_offset, void *priv_data);
static int process_bad_block(ext2_filsys fs, blk_t *block_nr,
			     e2_blkcnt_t blockcnt, blk_t ref_blk,
			     int ref_offset, void *priv_data);
static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
			 char *block_buf);
static void mark_table_blocks(e2fsck_t ctx);
static void alloc_imagic_map(e2fsck_t ctx);
static void mark_inode_bad(e2fsck_t ctx, ino_t ino);
static void handle_fs_bad_blocks(e2fsck_t ctx);
static void process_inodes(e2fsck_t ctx, char *block_buf);
static int process_inode_cmp(const void *a, const void *b);
static errcode_t scan_callback(ext2_filsys fs,
				  dgrp_t group, void * priv_data);
static void adjust_extattr_refcount(e2fsck_t ctx, ext2_refcount_t refcount,
				    char *block_buf, int adjust_sign);
/* static char *describe_illegal_block(ext2_filsys fs, blk_t block); */

static void e2fsck_write_inode_full(e2fsck_t ctx, unsigned long ino,
			       struct ext2_inode * inode, int bufsize,
			       const char *proc);

struct process_block_struct_1 {
	ext2_ino_t      ino;
	unsigned        is_dir:1, is_reg:1, clear:1, suppress:1,
				fragmented:1, compressed:1, bbcheck:1;
	blk_t           num_blocks;
	blk_t           max_blocks;
	e2_blkcnt_t     last_block;
	int             num_illegal_blocks;
	blk_t           previous_block;
	struct ext2_inode *inode;
	struct problem_context *pctx;
	ext2fs_block_bitmap fs_meta_blocks;
	e2fsck_t        ctx;
};

struct process_inode_block {
	ext2_ino_t ino;
	struct ext2_inode inode;
};

struct scan_callback_struct {
	e2fsck_t        ctx;
	char            *block_buf;
};

/*
 * For the inodes to process list.
 */
static struct process_inode_block *inodes_to_process;
static int process_inode_count;

static __u64 ext2_max_sizes[EXT2_MAX_BLOCK_LOG_SIZE -
			    EXT2_MIN_BLOCK_LOG_SIZE + 1];

/*
 * Free all memory allocated by pass1 in preparation for restarting
 * things.
 */
static void unwind_pass1(void)
{
	ext2fs_free_mem(&inodes_to_process);
}

/*
 * Check to make sure a device inode is real.  Returns 1 if the device
 * checks out, 0 if not.
 *
 * Note: this routine is now also used to check FIFO's and Sockets,
 * since they have the same requirement; the i_block fields should be
 * zero.
 */
static int
e2fsck_pass1_check_device_inode(ext2_filsys fs, struct ext2_inode *inode)
{
	int     i;

	/*
	 * If i_blocks is non-zero, or the index flag is set, then
	 * this is a bogus device/fifo/socket
	 */
	if ((ext2fs_inode_data_blocks(fs, inode) != 0) ||
	    (inode->i_flags & EXT2_INDEX_FL))
		return 0;

	/*
	 * We should be able to do the test below all the time, but
	 * because the kernel doesn't forcibly clear the device
	 * inode's additional i_block fields, there are some rare
	 * occasions when a legitimate device inode will have non-zero
	 * additional i_block fields.  So for now, we only complain
	 * when the immutable flag is set, which should never happen
	 * for devices.  (And that's when the problem is caused, since
	 * you can't set or clear immutable flags for devices.)  Once
	 * the kernel has been fixed we can change this...
	 */
	if (inode->i_flags & (EXT2_IMMUTABLE_FL | EXT2_APPEND_FL)) {
		for (i=4; i < EXT2_N_BLOCKS; i++)
			if (inode->i_block[i])
				return 0;
	}
	return 1;
}

/*
 * Check to make sure a symlink inode is real.  Returns 1 if the symlink
 * checks out, 0 if not.
 */
static int
e2fsck_pass1_check_symlink(ext2_filsys fs, struct ext2_inode *inode, char *buf)
{
	unsigned int len;
	int i;
	blk_t   blocks;

	if ((inode->i_size_high || inode->i_size == 0) ||
	    (inode->i_flags & EXT2_INDEX_FL))
		return 0;

	blocks = ext2fs_inode_data_blocks(fs, inode);
	if (blocks) {
		if ((inode->i_size >= fs->blocksize) ||
		    (blocks != fs->blocksize >> 9) ||
		    (inode->i_block[0] < fs->super->s_first_data_block) ||
		    (inode->i_block[0] >= fs->super->s_blocks_count))
			return 0;

		for (i = 1; i < EXT2_N_BLOCKS; i++)
			if (inode->i_block[i])
				return 0;

		if (io_channel_read_blk(fs->io, inode->i_block[0], 1, buf))
			return 0;

		len = strnlen(buf, fs->blocksize);
		if (len == fs->blocksize)
			return 0;
	} else {
		if (inode->i_size >= sizeof(inode->i_block))
			return 0;

		len = strnlen((char *)inode->i_block, sizeof(inode->i_block));
		if (len == sizeof(inode->i_block))
			return 0;
	}
	if (len != inode->i_size)
		return 0;
	return 1;
}

/*
 * If the immutable (or append-only) flag is set on the inode, offer
 * to clear it.
 */
#define BAD_SPECIAL_FLAGS (EXT2_IMMUTABLE_FL | EXT2_APPEND_FL)
static void check_immutable(e2fsck_t ctx, struct problem_context *pctx)
{
	if (!(pctx->inode->i_flags & BAD_SPECIAL_FLAGS))
		return;

	if (!fix_problem(ctx, PR_1_SET_IMMUTABLE, pctx))
		return;

	pctx->inode->i_flags &= ~BAD_SPECIAL_FLAGS;
	e2fsck_write_inode(ctx, pctx->ino, pctx->inode, "pass1");
}

/*
 * If device, fifo or socket, check size is zero -- if not offer to
 * clear it
 */
static void check_size(e2fsck_t ctx, struct problem_context *pctx)
{
	struct ext2_inode *inode = pctx->inode;

	if ((inode->i_size == 0) && (inode->i_size_high == 0))
		return;

	if (!fix_problem(ctx, PR_1_SET_NONZSIZE, pctx))
		return;

	inode->i_size = 0;
	inode->i_size_high = 0;
	e2fsck_write_inode(ctx, pctx->ino, pctx->inode, "pass1");
}

static void check_ea_in_inode(e2fsck_t ctx, struct problem_context *pctx)
{
	struct ext2_super_block *sb = ctx->fs->super;
	struct ext2_inode_large *inode;
	struct ext2_ext_attr_entry *entry;
	char *start, *end;
	int storage_size, remain, offs;
	int problem = 0;

	inode = (struct ext2_inode_large *) pctx->inode;
	storage_size = EXT2_INODE_SIZE(ctx->fs->super) - EXT2_GOOD_OLD_INODE_SIZE -
		inode->i_extra_isize;
	start = ((char *) inode) + EXT2_GOOD_OLD_INODE_SIZE +
		inode->i_extra_isize + sizeof(__u32);
	end = (char *) inode + EXT2_INODE_SIZE(ctx->fs->super);
	entry = (struct ext2_ext_attr_entry *) start;

	/* scan all entry's headers first */

	/* take finish entry 0UL into account */
	remain = storage_size - sizeof(__u32);
	offs = end - start;

	while (!EXT2_EXT_IS_LAST_ENTRY(entry)) {

		/* header eats this space */
		remain -= sizeof(struct ext2_ext_attr_entry);

		/* is attribute name valid? */
		if (EXT2_EXT_ATTR_SIZE(entry->e_name_len) > remain) {
			pctx->num = entry->e_name_len;
			problem = PR_1_ATTR_NAME_LEN;
			goto fix;
		}

		/* attribute len eats this space */
		remain -= EXT2_EXT_ATTR_SIZE(entry->e_name_len);

		/* check value size */
		if (entry->e_value_size == 0 || entry->e_value_size > remain) {
			pctx->num = entry->e_value_size;
			problem = PR_1_ATTR_VALUE_SIZE;
			goto fix;
		}

		/* check value placement */
		if (entry->e_value_offs +
		    EXT2_XATTR_SIZE(entry->e_value_size) != offs) {
			printf("(entry->e_value_offs + entry->e_value_size: %d, offs: %d)\n", entry->e_value_offs + entry->e_value_size, offs);
			pctx->num = entry->e_value_offs;
			problem = PR_1_ATTR_VALUE_OFFSET;
			goto fix;
		}

		/* e_value_block must be 0 in inode's ea */
		if (entry->e_value_block != 0) {
			pctx->num = entry->e_value_block;
			problem = PR_1_ATTR_VALUE_BLOCK;
			goto fix;
		}