xfs_da_btree.c

linux 内核源代码

			blk->index++;
			blkno = be32_to_cpu(node->btree[blk->index].before);
			break;
		} else if (!forward && (blk->index > 0)) {
			blk->index--;
			blkno = be32_to_cpu(node->btree[blk->index].before);
			break;
		}
	}
	if (level < 0) {
		*result = XFS_ERROR(ENOENT);	/* we're out of our tree */
		ASSERT(args->oknoent);
		return(0);
	}

	/*
	 * Roll down the edge of the subtree until we reach the
	 * same depth we were at originally.
	 */
	for (blk++, level++; level < path->active; blk++, level++) {
		/*
		 * Release the old block.
		 * (if it's dirty, trans won't actually let go)
		 */
		if (release)
			xfs_da_brelse(args->trans, blk->bp);

		/*
		 * Read the next child block.
		 */
		blk->blkno = blkno;
		error = xfs_da_read_buf(args->trans, args->dp, blkno, -1,
						     &blk->bp, args->whichfork);
		if (error)
			return(error);
		ASSERT(blk->bp != NULL);
		info = blk->bp->data;
		ASSERT(be16_to_cpu(info->magic) == XFS_DA_NODE_MAGIC ||
		       be16_to_cpu(info->magic) == XFS_DIR2_LEAFN_MAGIC ||
		       be16_to_cpu(info->magic) == XFS_ATTR_LEAF_MAGIC);
		blk->magic = be16_to_cpu(info->magic);
		if (blk->magic == XFS_DA_NODE_MAGIC) {
			node = (xfs_da_intnode_t *)info;
			blk->hashval = be32_to_cpu(node->btree[be16_to_cpu(node->hdr.count)-1].hashval);
			if (forward)
				blk->index = 0;
			else
				blk->index = be16_to_cpu(node->hdr.count)-1;
			blkno = be32_to_cpu(node->btree[blk->index].before);
		} else {
			ASSERT(level == path->active-1);
			blk->index = 0;
			switch(blk->magic) {
			case XFS_ATTR_LEAF_MAGIC:
				blk->hashval = xfs_attr_leaf_lasthash(blk->bp,
								      NULL);
				break;
			case XFS_DIR2_LEAFN_MAGIC:
				blk->hashval = xfs_dir2_leafn_lasthash(blk->bp,
								       NULL);
				break;
			default:
				ASSERT(blk->magic == XFS_ATTR_LEAF_MAGIC ||
				       blk->magic == XFS_DIR2_LEAFN_MAGIC);
				break;
			}
		}
	}
	*result = 0;
	return(0);
}


/*========================================================================
 * Utility routines.
 *========================================================================*/

/*
 * Implement a simple hash on a character string.
 * Rotate the hash value by 7 bits, then XOR each character in.
 * This is implemented with some source-level loop unrolling.
 */
xfs_dahash_t
xfs_da_hashname(const uchar_t *name, int namelen)
{
	xfs_dahash_t hash;

	/*
	 * Do four characters at a time as long as we can.
	 */
	for (hash = 0; namelen >= 4; namelen -= 4, name += 4)
		hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
		       (name[3] << 0) ^ rol32(hash, 7 * 4);

	/*
	 * Now do the rest of the characters.
	 */
	switch (namelen) {
	case 3:
		return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
		       rol32(hash, 7 * 3);
	case 2:
		return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);
	case 1:
		return (name[0] << 0) ^ rol32(hash, 7 * 1);
	default: /* case 0: */
		return hash;
	}
}

/*
 * Add a block to the btree ahead of the file.
 * Return the new block number to the caller.
 */
int
xfs_da_grow_inode(xfs_da_args_t *args, xfs_dablk_t *new_blkno)
{
	xfs_fileoff_t bno, b;
	xfs_bmbt_irec_t map;
	xfs_bmbt_irec_t	*mapp;
	xfs_inode_t *dp;
	int nmap, error, w, count, c, got, i, mapi;
	xfs_trans_t *tp;
	xfs_mount_t *mp;

	dp = args->dp;
	mp = dp->i_mount;
	w = args->whichfork;
	tp = args->trans;
	/*
	 * For new directories adjust the file offset and block count.
	 */
	if (w == XFS_DATA_FORK) {
		bno = mp->m_dirleafblk;
		count = mp->m_dirblkfsbs;
	} else {
		bno = 0;
		count = 1;
	}
	/*
	 * Find a spot in the file space to put the new block.
	 */
	if ((error = xfs_bmap_first_unused(tp, dp, count, &bno, w)))
		return error;
	if (w == XFS_DATA_FORK)
		ASSERT(bno >= mp->m_dirleafblk && bno < mp->m_dirfreeblk);
	/*
	 * Try mapping it in one filesystem block.
	 */
	nmap = 1;
	ASSERT(args->firstblock != NULL);
	if ((error = xfs_bmapi(tp, dp, bno, count,
			XFS_BMAPI_AFLAG(w)|XFS_BMAPI_WRITE|XFS_BMAPI_METADATA|
			XFS_BMAPI_CONTIG,
			args->firstblock, args->total, &map, &nmap,
			args->flist, NULL))) {
		return error;
	}
	ASSERT(nmap <= 1);
	if (nmap == 1) {
		mapp = &map;
		mapi = 1;
	}
	/*
	 * If we didn't get it and the block might work if fragmented,
	 * try without the CONTIG flag.  Loop until we get it all.
	 */
	else if (nmap == 0 && count > 1) {
		mapp = kmem_alloc(sizeof(*mapp) * count, KM_SLEEP);
		for (b = bno, mapi = 0; b < bno + count; ) {
			nmap = MIN(XFS_BMAP_MAX_NMAP, count);
			c = (int)(bno + count - b);
			if ((error = xfs_bmapi(tp, dp, b, c,
					XFS_BMAPI_AFLAG(w)|XFS_BMAPI_WRITE|
					XFS_BMAPI_METADATA,
					args->firstblock, args->total,
					&mapp[mapi], &nmap, args->flist,
					NULL))) {
				kmem_free(mapp, sizeof(*mapp) * count);
				return error;
			}
			if (nmap < 1)
				break;
			mapi += nmap;
			b = mapp[mapi - 1].br_startoff +
			    mapp[mapi - 1].br_blockcount;
		}
	} else {
		mapi = 0;
		mapp = NULL;
	}
	/*
	 * Count the blocks we got, make sure it matches the total.
	 */
	for (i = 0, got = 0; i < mapi; i++)
		got += mapp[i].br_blockcount;
	if (got != count || mapp[0].br_startoff != bno ||
	    mapp[mapi - 1].br_startoff + mapp[mapi - 1].br_blockcount !=
	    bno + count) {
		if (mapp != &map)
			kmem_free(mapp, sizeof(*mapp) * count);
		return XFS_ERROR(ENOSPC);
	}
	if (mapp != &map)
		kmem_free(mapp, sizeof(*mapp) * count);
	*new_blkno = (xfs_dablk_t)bno;
	return 0;
}

/*
 * Ick.  We need to always be able to remove a btree block, even
 * if there's no space reservation because the filesystem is full.
 * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
 * It swaps the target block with the last block in the file.  The
 * last block in the file can always be removed since it can't cause
 * a bmap btree split to do that.
 */
STATIC int
xfs_da_swap_lastblock(xfs_da_args_t *args, xfs_dablk_t *dead_blknop,
		      xfs_dabuf_t **dead_bufp)
{
	xfs_dablk_t dead_blkno, last_blkno, sib_blkno, par_blkno;
	xfs_dabuf_t *dead_buf, *last_buf, *sib_buf, *par_buf;
	xfs_fileoff_t lastoff;
	xfs_inode_t *ip;
	xfs_trans_t *tp;
	xfs_mount_t *mp;
	int error, w, entno, level, dead_level;
	xfs_da_blkinfo_t *dead_info, *sib_info;
	xfs_da_intnode_t *par_node, *dead_node;
	xfs_dir2_leaf_t *dead_leaf2;
	xfs_dahash_t dead_hash;

	dead_buf = *dead_bufp;
	dead_blkno = *dead_blknop;
	tp = args->trans;
	ip = args->dp;
	w = args->whichfork;
	ASSERT(w == XFS_DATA_FORK);
	mp = ip->i_mount;
	lastoff = mp->m_dirfreeblk;
	error = xfs_bmap_last_before(tp, ip, &lastoff, w);
	if (error)
		return error;
	if (unlikely(lastoff == 0)) {
		XFS_ERROR_REPORT("xfs_da_swap_lastblock(1)", XFS_ERRLEVEL_LOW,
				 mp);
		return XFS_ERROR(EFSCORRUPTED);
	}
	/*
	 * Read the last block in the btree space.
	 */
	last_blkno = (xfs_dablk_t)lastoff - mp->m_dirblkfsbs;
	if ((error = xfs_da_read_buf(tp, ip, last_blkno, -1, &last_buf, w)))
		return error;
	/*
	 * Copy the last block into the dead buffer and log it.
	 */
	memcpy(dead_buf->data, last_buf->data, mp->m_dirblksize);
	xfs_da_log_buf(tp, dead_buf, 0, mp->m_dirblksize - 1);
	dead_info = dead_buf->data;
	/*
	 * Get values from the moved block.
	 */
	if (be16_to_cpu(dead_info->magic) == XFS_DIR2_LEAFN_MAGIC) {
		dead_leaf2 = (xfs_dir2_leaf_t *)dead_info;
		dead_level = 0;
		dead_hash = be32_to_cpu(dead_leaf2->ents[be16_to_cpu(dead_leaf2->hdr.count) - 1].hashval);
	} else {
		ASSERT(be16_to_cpu(dead_info->magic) == XFS_DA_NODE_MAGIC);
		dead_node = (xfs_da_intnode_t *)dead_info;
		dead_level = be16_to_cpu(dead_node->hdr.level);
		dead_hash = be32_to_cpu(dead_node->btree[be16_to_cpu(dead_node->hdr.count) - 1].hashval);
	}
	sib_buf = par_buf = NULL;
	/*
	 * If the moved block has a left sibling, fix up the pointers.
	 */
	if ((sib_blkno = be32_to_cpu(dead_info->back))) {
		if ((error = xfs_da_read_buf(tp, ip, sib_blkno, -1, &sib_buf, w)))
			goto done;
		sib_info = sib_buf->data;
		if (unlikely(
		    be32_to_cpu(sib_info->forw) != last_blkno ||
		    sib_info->magic != dead_info->magic)) {
			XFS_ERROR_REPORT("xfs_da_swap_lastblock(2)",
					 XFS_ERRLEVEL_LOW, mp);
			error = XFS_ERROR(EFSCORRUPTED);
			goto done;
		}
		sib_info->forw = cpu_to_be32(dead_blkno);
		xfs_da_log_buf(tp, sib_buf,
			XFS_DA_LOGRANGE(sib_info, &sib_info->forw,
					sizeof(sib_info->forw)));
		xfs_da_buf_done(sib_buf);
		sib_buf = NULL;
	}
	/*
	 * If the moved block has a right sibling, fix up the pointers.
	 */
	if ((sib_blkno = be32_to_cpu(dead_info->forw))) {
		if ((error = xfs_da_read_buf(tp, ip, sib_blkno, -1, &sib_buf, w)))
			goto done;
		sib_info = sib_buf->data;
		if (unlikely(
		       be32_to_cpu(sib_info->back) != last_blkno ||
		       sib_info->magic != dead_info->magic)) {
			XFS_ERROR_REPORT("xfs_da_swap_lastblock(3)",
					 XFS_ERRLEVEL_LOW, mp);
			error = XFS_ERROR(EFSCORRUPTED);
			goto done;
		}
		sib_info->back = cpu_to_be32(dead_blkno);
		xfs_da_log_buf(tp, sib_buf,
			XFS_DA_LOGRANGE(sib_info, &sib_info->back,
					sizeof(sib_info->back)));
		xfs_da_buf_done(sib_buf);
		sib_buf = NULL;
	}
	par_blkno = mp->m_dirleafblk;
	level = -1;
	/*
	 * Walk down the tree looking for the parent of the moved block.
	 */
	for (;;) {
		if ((error = xfs_da_read_buf(tp, ip, par_blkno, -1, &par_buf, w)))
			goto done;
		par_node = par_buf->data;
		if (unlikely(
		    be16_to_cpu(par_node->hdr.info.magic) != XFS_DA_NODE_MAGIC ||
		    (level >= 0 && level != be16_to_cpu(par_node->hdr.level) + 1))) {
			XFS_ERROR_REPORT("xfs_da_swap_lastblock(4)",
					 XFS_ERRLEVEL_LOW, mp);
			error = XFS_ERROR(EFSCORRUPTED);
			goto done;
		}
		level = be16_to_cpu(par_node->hdr.level);
		for (entno = 0;
		     entno < be16_to_cpu(par_node->hdr.count) &&
		     be32_to_cpu(par_node->btree[entno].hashval) < dead_hash;
		     entno++)
			continue;
		if (unlikely(entno == be16_to_cpu(par_node->hdr.count))) {
			XFS_ERROR_REPORT("xfs_da_swap_lastblock(5)",
					 XFS_ERRLEVEL_LOW, mp);
			error = XFS_ERROR(EFSCORRUPTED);
			goto done;
		}
		par_blkno = be32_to_cpu(par_node->btree[entno].before);
		if (level == dead_level + 1)
			break;
		xfs_da_brelse(tp, par_buf);
		par_buf = NULL;
	}
	/*
	 * We're in the right parent block.
	 * Look for the right entry.
	 */
	for (;;) {
		for (;
		     entno < be16_to_cpu(par_node->hdr.count) &&
		     be32_to_cpu(par_node->btree[entno].before) != last_blkno;
		     entno++)
			continue;
		if (entno < be16_to_cpu(par_node->hdr.count))
			break;
		par_blkno = be32_to_cpu(par_node->hdr.info.forw);
		xfs_da_brelse(tp, par_buf);
		par_buf = NULL;
		if (unlikely(par_blkno == 0)) {
			XFS_ERROR_REPORT("xfs_da_swap_lastblock(6)",
					 XFS_ERRLEVEL_LOW, mp);
			error = XFS_ERROR(EFSCORRUPTED);
			goto done;
		}
		if ((error = xfs_da_read_buf(tp, ip, par_blkno, -1, &par_buf, w)))
			goto done;
		par_node = par_buf->data;
		if (unlikely(
		    be16_to_cpu(par_node->hdr.level) != level ||
		    be16_to_cpu(par_node->hdr.info.magic) != XFS_DA_NODE_MAGIC)) {
			XFS_ERROR_REPORT("xfs_da_swap_lastblock(7)",
					 XFS_ERRLEVEL_LOW, mp);
			error = XFS_ERROR(EFSCORRUPTED);
			goto done;
		}
		entno = 0;
	}
	/*
	 * Update the parent entry pointing to the moved block.
	 */
	par_node->btree[entno].before = cpu_to_be32(dead_blkno);
	xfs_da_log_buf(tp, par_buf,
		XFS_DA_LOGRANGE(par_node, &par_node->btree[entno].before,
				sizeof(par_node->btree[entno].before)));
	xfs_da_buf_done(par_buf);
	xfs_da_buf_done(dead_buf);
	*dead_blknop = last_blkno;
	*dead_bufp = last_buf;
	return 0;
done:
	if (par_buf)
		xfs_da_brelse(tp, par_buf);
	if (sib_buf)
		xfs_da_brelse(tp, sib_buf);
	xfs_da_brelse(tp, last_buf);
	return error;
}

/*
 * Remove a btree block from a directory or attribute.
 */
int
xfs_da_shrink_inode(xfs_da_args_t *args, xfs_dablk_t dead_blkno,
		    xfs_dabuf_t *dead_buf)
{
	xfs_inode_t *dp;
	int done, error, w, count;
	xfs_trans_t *tp;
	xfs_mount_t *mp;

	dp = args->dp;
	w = args->whichfork;
	tp = args->trans;
	mp = dp->i_mount;
	if (w == XFS_DATA_FORK)
		count = mp->m_dirblkfsbs;
	else
		count = 1;
	for (;;) {
		/*
		 * Remove extents.  If we get ENOSPC for a dir we have to move
		 * the last block to the place we want to kill.
		 */
		if ((error = xfs_bunmapi(tp, dp, dead_blkno, count,
				XFS_BMAPI_AFLAG(w)|XFS_BMAPI_METADATA,
				0, args->firstblock, args->flist, NULL,
				&done)) == ENOSPC) {
			if (w != XFS_DATA_FORK)
				break;
			if ((error = xfs_da_swap_lastblock(args, &dead_blkno,
					&dead_buf)))
				break;
		} else {
			break;
		}
	}
	xfs_da_binval(tp, dead_buf);
	return error;
}

/*
 * See if the mapping(s) for this btree block are valid, i.e.
 * don't contain holes, are logically contiguous, and cover the whole range.
 */
STATIC int
xfs_da_map_covers_blocks(
	int		nmap,
	xfs_bmbt_irec_t	*mapp,
	xfs_dablk_t	bno,
	int		count)
{
	int		i;
	xfs_fileoff_t	off;

	for (i = 0, off = bno; i < nmap; i++) {
		if (mapp[i].br_startblock == HOLESTARTBLOCK ||
		    mapp[i].br_startblock == DELAYSTARTBLOCK) {
			return 0;
		}
		if (off != mapp[i].br_startoff) {
			return 0;
		}
		off += mapp[i].br_blockcount;