xfs_dir_leaf.c

来自「Linux Kernel 2.6.9 for OMAP1710」· C语言 代码 · 共 2,134 行 · 第 1/5 页

/*
 * Copyright (c) 2000-2003 Silicon Graphics, Inc.  All Rights Reserved.
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of version 2 of the GNU General Public License as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it would be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *
 * Further, this software is distributed without any warranty that it is
 * free of the rightful claim of any third person regarding infringement
 * or the like.  Any license provided herein, whether implied or
 * otherwise, applies only to this software file.  Patent licenses, if
 * any, provided herein do not apply to combinations of this program with
 * other software, or any other product whatsoever.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write the Free Software Foundation, Inc., 59
 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
 *
 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
 * Mountain View, CA  94043, or:
 *
 * http://www.sgi.com
 *
 * For further information regarding this notice, see:
 *
 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
 */

/*
 * xfs_dir_leaf.c
 *
 * GROT: figure out how to recover gracefully when bmap returns ENOSPC.
 */

#include "xfs.h"

#include "xfs_macros.h"
#include "xfs_types.h"
#include "xfs_inum.h"
#include "xfs_log.h"
#include "xfs_trans.h"
#include "xfs_sb.h"
#include "xfs_dir.h"
#include "xfs_dir2.h"
#include "xfs_dmapi.h"
#include "xfs_mount.h"
#include "xfs_alloc_btree.h"
#include "xfs_bmap_btree.h"
#include "xfs_ialloc_btree.h"
#include "xfs_alloc.h"
#include "xfs_btree.h"
#include "xfs_attr_sf.h"
#include "xfs_dir_sf.h"
#include "xfs_dir2_sf.h"
#include "xfs_dinode.h"
#include "xfs_inode_item.h"
#include "xfs_inode.h"
#include "xfs_bmap.h"
#include "xfs_da_btree.h"
#include "xfs_dir_leaf.h"
#include "xfs_error.h"

/*
 * xfs_dir_leaf.c
 *
 * Routines to implement leaf blocks of directories as Btrees of hashed names.
 */

/*========================================================================
 * Function prototypes for the kernel.
 *========================================================================*/

/*
 * Routines used for growing the Btree.
 */
STATIC void xfs_dir_leaf_add_work(xfs_dabuf_t *leaf_buffer, xfs_da_args_t *args,
					      int insertion_index,
					      int freemap_index);
STATIC int xfs_dir_leaf_compact(xfs_trans_t *trans, xfs_dabuf_t *leaf_buffer,
					    int musthave, int justcheck);
STATIC void xfs_dir_leaf_rebalance(xfs_da_state_t *state,
						  xfs_da_state_blk_t *blk1,
						  xfs_da_state_blk_t *blk2);
STATIC int xfs_dir_leaf_figure_balance(xfs_da_state_t *state,
					  xfs_da_state_blk_t *leaf_blk_1,
					  xfs_da_state_blk_t *leaf_blk_2,
					  int *number_entries_in_blk1,
					  int *number_namebytes_in_blk1);

/*
 * Utility routines.
 */
STATIC void xfs_dir_leaf_moveents(xfs_dir_leafblock_t *src_leaf,
					      int src_start,
					      xfs_dir_leafblock_t *dst_leaf,
					      int dst_start, int move_count,
					      xfs_mount_t *mp);


/*========================================================================
 * External routines when dirsize < XFS_IFORK_DSIZE(dp).
 *========================================================================*/


/*
 * Validate a given inode number.
 */
int
xfs_dir_ino_validate(xfs_mount_t *mp, xfs_ino_t ino)
{
	xfs_agblock_t	agblkno;
	xfs_agino_t	agino;
	xfs_agnumber_t	agno;
	int		ino_ok;
	int		ioff;

	agno = XFS_INO_TO_AGNO(mp, ino);
	agblkno = XFS_INO_TO_AGBNO(mp, ino);
	ioff = XFS_INO_TO_OFFSET(mp, ino);
	agino = XFS_OFFBNO_TO_AGINO(mp, agblkno, ioff);
	ino_ok =
		agno < mp->m_sb.sb_agcount &&
		agblkno < mp->m_sb.sb_agblocks &&
		agblkno != 0 &&
		ioff < (1 << mp->m_sb.sb_inopblog) &&
		XFS_AGINO_TO_INO(mp, agno, agino) == ino;
	if (unlikely(XFS_TEST_ERROR(!ino_ok, mp, XFS_ERRTAG_DIR_INO_VALIDATE,
			XFS_RANDOM_DIR_INO_VALIDATE))) {
		xfs_fs_cmn_err(CE_WARN, mp, "Invalid inode number 0x%Lx",
				(unsigned long long) ino);
		XFS_ERROR_REPORT("xfs_dir_ino_validate", XFS_ERRLEVEL_LOW, mp);
		return XFS_ERROR(EFSCORRUPTED);
	}
	return 0;
}

/*
 * Create the initial contents of a shortform directory.
 */
int
xfs_dir_shortform_create(xfs_da_args_t *args, xfs_ino_t parent)
{
	xfs_dir_sf_hdr_t *hdr;
	xfs_inode_t *dp;

	dp = args->dp;
	ASSERT(dp != NULL);
	ASSERT(dp->i_d.di_size == 0);
	if (dp->i_d.di_format == XFS_DINODE_FMT_EXTENTS) {
		dp->i_df.if_flags &= ~XFS_IFEXTENTS;	/* just in case */
		dp->i_d.di_format = XFS_DINODE_FMT_LOCAL;
		xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE);
		dp->i_df.if_flags |= XFS_IFINLINE;
	}
	ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
	ASSERT(dp->i_df.if_bytes == 0);
	xfs_idata_realloc(dp, sizeof(*hdr), XFS_DATA_FORK);
	hdr = (xfs_dir_sf_hdr_t *)dp->i_df.if_u1.if_data;
	XFS_DIR_SF_PUT_DIRINO_ARCH(&parent, &hdr->parent, ARCH_CONVERT);

	INT_ZERO(hdr->count, ARCH_CONVERT);
	dp->i_d.di_size = sizeof(*hdr);
	xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA);
	return(0);
}

/*
 * Add a name to the shortform directory structure.
 * Overflow from the inode has already been checked for.
 */
int
xfs_dir_shortform_addname(xfs_da_args_t *args)
{
	xfs_dir_shortform_t *sf;
	xfs_dir_sf_entry_t *sfe;
	int i, offset, size;
	xfs_inode_t *dp;

	dp = args->dp;
	ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
	/*
	 * Catch the case where the conversion from shortform to leaf
	 * failed part way through.
	 */
	if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
		ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
		return XFS_ERROR(EIO);
	}
	ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
	ASSERT(dp->i_df.if_u1.if_data != NULL);
	sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
	sfe = &sf->list[0];
	for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) {
		if (sfe->namelen == args->namelen &&
		    args->name[0] == sfe->name[0] &&
		    memcmp(args->name, sfe->name, args->namelen) == 0)
			return(XFS_ERROR(EEXIST));
		sfe = XFS_DIR_SF_NEXTENTRY(sfe);
	}

	offset = (int)((char *)sfe - (char *)sf);
	size = XFS_DIR_SF_ENTSIZE_BYNAME(args->namelen);
	xfs_idata_realloc(dp, size, XFS_DATA_FORK);
	sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
	sfe = (xfs_dir_sf_entry_t *)((char *)sf + offset);

	XFS_DIR_SF_PUT_DIRINO_ARCH(&args->inumber, &sfe->inumber, ARCH_CONVERT);
	sfe->namelen = args->namelen;
	memcpy(sfe->name, args->name, sfe->namelen);
	INT_MOD(sf->hdr.count, ARCH_CONVERT, +1);

	dp->i_d.di_size += size;
	xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA);

	return(0);
}

/*
 * Remove a name from the shortform directory structure.
 */
int
xfs_dir_shortform_removename(xfs_da_args_t *args)
{
	xfs_dir_shortform_t *sf;
	xfs_dir_sf_entry_t *sfe;
	int base, size = 0, i;
	xfs_inode_t *dp;

	dp = args->dp;
	ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
	/*
	 * Catch the case where the conversion from shortform to leaf
	 * failed part way through.
	 */
	if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
		ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
		return XFS_ERROR(EIO);
	}
	ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
	ASSERT(dp->i_df.if_u1.if_data != NULL);
	base = sizeof(xfs_dir_sf_hdr_t);
	sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
	sfe = &sf->list[0];
	for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) {
		size = XFS_DIR_SF_ENTSIZE_BYENTRY(sfe);
		if (sfe->namelen == args->namelen &&
		    sfe->name[0] == args->name[0] &&
		    memcmp(sfe->name, args->name, args->namelen) == 0)
			break;
		base += size;
		sfe = XFS_DIR_SF_NEXTENTRY(sfe);
	}
	if (i < 0) {
		ASSERT(args->oknoent);
		return(XFS_ERROR(ENOENT));
	}

	if ((base + size) != dp->i_d.di_size) {
		memmove(&((char *)sf)[base], &((char *)sf)[base+size],
					      dp->i_d.di_size - (base+size));
	}
	INT_MOD(sf->hdr.count, ARCH_CONVERT, -1);

	xfs_idata_realloc(dp, -size, XFS_DATA_FORK);
	dp->i_d.di_size -= size;
	xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA);

	return(0);
}

/*
 * Look up a name in a shortform directory structure.
 */
int
xfs_dir_shortform_lookup(xfs_da_args_t *args)
{
	xfs_dir_shortform_t *sf;
	xfs_dir_sf_entry_t *sfe;
	int i;
	xfs_inode_t *dp;

	dp = args->dp;
	ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
	/*
	 * Catch the case where the conversion from shortform to leaf
	 * failed part way through.
	 */
	if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
		ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
		return XFS_ERROR(EIO);
	}
	ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
	ASSERT(dp->i_df.if_u1.if_data != NULL);
	sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
	if (args->namelen == 2 &&
	    args->name[0] == '.' && args->name[1] == '.') {
		XFS_DIR_SF_GET_DIRINO_ARCH(&sf->hdr.parent, &args->inumber, ARCH_CONVERT);
		return(XFS_ERROR(EEXIST));
	}
	if (args->namelen == 1 && args->name[0] == '.') {
		args->inumber = dp->i_ino;
		return(XFS_ERROR(EEXIST));
	}
	sfe = &sf->list[0];
	for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) {
		if (sfe->namelen == args->namelen &&
		    sfe->name[0] == args->name[0] &&
		    memcmp(args->name, sfe->name, args->namelen) == 0) {
			XFS_DIR_SF_GET_DIRINO_ARCH(&sfe->inumber, &args->inumber, ARCH_CONVERT);
			return(XFS_ERROR(EEXIST));
		}
		sfe = XFS_DIR_SF_NEXTENTRY(sfe);
	}
	ASSERT(args->oknoent);
	return(XFS_ERROR(ENOENT));
}

/*
 * Convert from using the shortform to the leaf.
 */
int
xfs_dir_shortform_to_leaf(xfs_da_args_t *iargs)
{
	xfs_inode_t *dp;
	xfs_dir_shortform_t *sf;
	xfs_dir_sf_entry_t *sfe;
	xfs_da_args_t args;
	xfs_ino_t inumber;
	char *tmpbuffer;
	int retval, i, size;
	xfs_dablk_t blkno;
	xfs_dabuf_t *bp;

	dp = iargs->dp;
	/*
	 * Catch the case where the conversion from shortform to leaf
	 * failed part way through.
	 */
	if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
		ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
		return XFS_ERROR(EIO);
	}
	ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
	ASSERT(dp->i_df.if_u1.if_data != NULL);
	size = dp->i_df.if_bytes;
	tmpbuffer = kmem_alloc(size, KM_SLEEP);
	ASSERT(tmpbuffer != NULL);

	memcpy(tmpbuffer, dp->i_df.if_u1.if_data, size);

	sf = (xfs_dir_shortform_t *)tmpbuffer;
	XFS_DIR_SF_GET_DIRINO_ARCH(&sf->hdr.parent, &inumber, ARCH_CONVERT);

	xfs_idata_realloc(dp, -size, XFS_DATA_FORK);
	dp->i_d.di_size = 0;
	xfs_trans_log_inode(iargs->trans, dp, XFS_ILOG_CORE);
	retval = xfs_da_grow_inode(iargs, &blkno);
	if (retval)
		goto out;

	ASSERT(blkno == 0);
	retval = xfs_dir_leaf_create(iargs, blkno, &bp);
	if (retval)
		goto out;
	xfs_da_buf_done(bp);

	args.name = ".";
	args.namelen = 1;
	args.hashval = xfs_dir_hash_dot;
	args.inumber = dp->i_ino;
	args.dp = dp;
	args.firstblock = iargs->firstblock;
	args.flist = iargs->flist;
	args.total = iargs->total;
	args.whichfork = XFS_DATA_FORK;
	args.trans = iargs->trans;
	args.justcheck = 0;
	args.addname = args.oknoent = 1;
	retval = xfs_dir_leaf_addname(&args);
	if (retval)
		goto out;

	args.name = "..";
	args.namelen = 2;
	args.hashval = xfs_dir_hash_dotdot;
	args.inumber = inumber;
	retval = xfs_dir_leaf_addname(&args);
	if (retval)
		goto out;

	sfe = &sf->list[0];
	for (i = 0; i < INT_GET(sf->hdr.count, ARCH_CONVERT); i++) {
		args.name = (char *)(sfe->name);
		args.namelen = sfe->namelen;
		args.hashval = xfs_da_hashname((char *)(sfe->name),
					       sfe->namelen);
		XFS_DIR_SF_GET_DIRINO_ARCH(&sfe->inumber, &args.inumber, ARCH_CONVERT);
		retval = xfs_dir_leaf_addname(&args);
		if (retval)
			goto out;
		sfe = XFS_DIR_SF_NEXTENTRY(sfe);
	}
	retval = 0;

out:
	kmem_free(tmpbuffer, size);
	return(retval);
}

STATIC int
xfs_dir_shortform_compare(const void *a, const void *b)
{
	xfs_dir_sf_sort_t *sa, *sb;

	sa = (xfs_dir_sf_sort_t *)a;
	sb = (xfs_dir_sf_sort_t *)b;
	if (sa->hash < sb->hash)
		return -1;
	else if (sa->hash > sb->hash)
		return 1;
	else
		return sa->entno - sb->entno;
}