e2fsck.c

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

	    } 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 = malloc(sizeof(dnode_t));

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

/*
 * 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