e2fsck.c

busybox最新版的源码:学习和应用的好东东,多的不说了,大家看后再说吧

/* 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 <[e-mail]>
 * 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 <[e-mail]>, 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 <[e-mail]>
 *
 * 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 = malloc(sizeof(*new_cache));
	if (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;