/* 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 tarball for details.
 */

#ifndef _GNU_SOURCE
#define _GNU_SOURCE 1 /* get strnlen() */
#endif

#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 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 = 0;
        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;
}