brintos / linux-shallow public Read only

1// SPDX-License-Identifier: GPL-2.02/*3 * Copyright (c) 2000-2005 Silicon Graphics, Inc.4 * Copyright (c) 2013 Red Hat, Inc.5 * All Rights Reserved.6 */7#include "xfs.h"8#include "xfs_fs.h"9#include "xfs_shared.h"10#include "xfs_format.h"11#include "xfs_log_format.h"12#include "xfs_trans_resv.h"13#include "xfs_bit.h"14#include "xfs_mount.h"15#include "xfs_inode.h"16#include "xfs_dir2.h"17#include "xfs_dir2_priv.h"18#include "xfs_trans.h"19#include "xfs_bmap.h"20#include "xfs_attr_leaf.h"21#include "xfs_error.h"22#include "xfs_trace.h"23#include "xfs_buf_item.h"24#include "xfs_log.h"25#include "xfs_errortag.h"26#include "xfs_health.h"27 28/*29 * xfs_da_btree.c30 *31 * Routines to implement directories as Btrees of hashed names.32 */33 34/*========================================================================35 * Function prototypes for the kernel.36 *========================================================================*/37 38/*39 * Routines used for growing the Btree.40 */41STATIC int xfs_da3_root_split(xfs_da_state_t *state,42					    xfs_da_state_blk_t *existing_root,43					    xfs_da_state_blk_t *new_child);44STATIC int xfs_da3_node_split(xfs_da_state_t *state,45					    xfs_da_state_blk_t *existing_blk,46					    xfs_da_state_blk_t *split_blk,47					    xfs_da_state_blk_t *blk_to_add,48					    int treelevel,49					    int *result);50STATIC void xfs_da3_node_rebalance(xfs_da_state_t *state,51					 xfs_da_state_blk_t *node_blk_1,52					 xfs_da_state_blk_t *node_blk_2);53STATIC void xfs_da3_node_add(xfs_da_state_t *state,54				   xfs_da_state_blk_t *old_node_blk,55				   xfs_da_state_blk_t *new_node_blk);56 57/*58 * Routines used for shrinking the Btree.59 */60STATIC int xfs_da3_root_join(xfs_da_state_t *state,61					   xfs_da_state_blk_t *root_blk);62STATIC int xfs_da3_node_toosmall(xfs_da_state_t *state, int *retval);63STATIC void xfs_da3_node_remove(xfs_da_state_t *state,64					      xfs_da_state_blk_t *drop_blk);65STATIC void xfs_da3_node_unbalance(xfs_da_state_t *state,66					 xfs_da_state_blk_t *src_node_blk,67					 xfs_da_state_blk_t *dst_node_blk);68 69/*70 * Utility routines.71 */72STATIC int	xfs_da3_blk_unlink(xfs_da_state_t *state,73				  xfs_da_state_blk_t *drop_blk,74				  xfs_da_state_blk_t *save_blk);75 76 77struct kmem_cache	*xfs_da_state_cache;	/* anchor for dir/attr state */78 79/*80 * Allocate a dir-state structure.81 * We don't put them on the stack since they're large.82 */83struct xfs_da_state *84xfs_da_state_alloc(85	struct xfs_da_args	*args)86{87	struct xfs_da_state	*state;88 89	state = kmem_cache_zalloc(xfs_da_state_cache,90			GFP_KERNEL | __GFP_NOLOCKDEP | __GFP_NOFAIL);91	state->args = args;92	state->mp = args->dp->i_mount;93	return state;94}95 96/*97 * Kill the altpath contents of a da-state structure.98 */99STATIC void100xfs_da_state_kill_altpath(xfs_da_state_t *state)101{102	int	i;103 104	for (i = 0; i < state->altpath.active; i++)105		state->altpath.blk[i].bp = NULL;106	state->altpath.active = 0;107}108 109/*110 * Free a da-state structure.111 */112void113xfs_da_state_free(xfs_da_state_t *state)114{115	xfs_da_state_kill_altpath(state);116#ifdef DEBUG117	memset((char *)state, 0, sizeof(*state));118#endif /* DEBUG */119	kmem_cache_free(xfs_da_state_cache, state);120}121 122void123xfs_da_state_reset(124	struct xfs_da_state	*state,125	struct xfs_da_args	*args)126{127	xfs_da_state_kill_altpath(state);128	memset(state, 0, sizeof(struct xfs_da_state));129	state->args = args;130	state->mp = state->args->dp->i_mount;131}132 133static inline int xfs_dabuf_nfsb(struct xfs_mount *mp, int whichfork)134{135	if (whichfork == XFS_DATA_FORK)136		return mp->m_dir_geo->fsbcount;137	return mp->m_attr_geo->fsbcount;138}139 140void141xfs_da3_node_hdr_from_disk(142	struct xfs_mount		*mp,143	struct xfs_da3_icnode_hdr	*to,144	struct xfs_da_intnode		*from)145{146	if (xfs_has_crc(mp)) {147		struct xfs_da3_intnode	*from3 = (struct xfs_da3_intnode *)from;148 149		to->forw = be32_to_cpu(from3->hdr.info.hdr.forw);150		to->back = be32_to_cpu(from3->hdr.info.hdr.back);151		to->magic = be16_to_cpu(from3->hdr.info.hdr.magic);152		to->count = be16_to_cpu(from3->hdr.__count);153		to->level = be16_to_cpu(from3->hdr.__level);154		to->btree = from3->__btree;155		ASSERT(to->magic == XFS_DA3_NODE_MAGIC);156	} else {157		to->forw = be32_to_cpu(from->hdr.info.forw);158		to->back = be32_to_cpu(from->hdr.info.back);159		to->magic = be16_to_cpu(from->hdr.info.magic);160		to->count = be16_to_cpu(from->hdr.__count);161		to->level = be16_to_cpu(from->hdr.__level);162		to->btree = from->__btree;163		ASSERT(to->magic == XFS_DA_NODE_MAGIC);164	}165}166 167void168xfs_da3_node_hdr_to_disk(169	struct xfs_mount		*mp,170	struct xfs_da_intnode		*to,171	struct xfs_da3_icnode_hdr	*from)172{173	if (xfs_has_crc(mp)) {174		struct xfs_da3_intnode	*to3 = (struct xfs_da3_intnode *)to;175 176		ASSERT(from->magic == XFS_DA3_NODE_MAGIC);177		to3->hdr.info.hdr.forw = cpu_to_be32(from->forw);178		to3->hdr.info.hdr.back = cpu_to_be32(from->back);179		to3->hdr.info.hdr.magic = cpu_to_be16(from->magic);180		to3->hdr.__count = cpu_to_be16(from->count);181		to3->hdr.__level = cpu_to_be16(from->level);182	} else {183		ASSERT(from->magic == XFS_DA_NODE_MAGIC);184		to->hdr.info.forw = cpu_to_be32(from->forw);185		to->hdr.info.back = cpu_to_be32(from->back);186		to->hdr.info.magic = cpu_to_be16(from->magic);187		to->hdr.__count = cpu_to_be16(from->count);188		to->hdr.__level = cpu_to_be16(from->level);189	}190}191 192/*193 * Verify an xfs_da3_blkinfo structure. Note that the da3 fields are only194 * accessible on v5 filesystems. This header format is common across da node,195 * attr leaf and dir leaf blocks.196 */197xfs_failaddr_t198xfs_da3_blkinfo_verify(199	struct xfs_buf		*bp,200	struct xfs_da3_blkinfo	*hdr3)201{202	struct xfs_mount	*mp = bp->b_mount;203	struct xfs_da_blkinfo	*hdr = &hdr3->hdr;204 205	if (!xfs_verify_magic16(bp, hdr->magic))206		return __this_address;207 208	if (xfs_has_crc(mp)) {209		if (!uuid_equal(&hdr3->uuid, &mp->m_sb.sb_meta_uuid))210			return __this_address;211		if (be64_to_cpu(hdr3->blkno) != xfs_buf_daddr(bp))212			return __this_address;213		if (!xfs_log_check_lsn(mp, be64_to_cpu(hdr3->lsn)))214			return __this_address;215	}216 217	return NULL;218}219 220static xfs_failaddr_t221xfs_da3_node_verify(222	struct xfs_buf		*bp)223{224	struct xfs_mount	*mp = bp->b_mount;225	struct xfs_da_intnode	*hdr = bp->b_addr;226	struct xfs_da3_icnode_hdr ichdr;227	xfs_failaddr_t		fa;228 229	xfs_da3_node_hdr_from_disk(mp, &ichdr, hdr);230 231	fa = xfs_da3_blkinfo_verify(bp, bp->b_addr);232	if (fa)233		return fa;234 235	if (ichdr.level == 0)236		return __this_address;237	if (ichdr.level > XFS_DA_NODE_MAXDEPTH)238		return __this_address;239	if (ichdr.count == 0)240		return __this_address;241 242	/*243	 * we don't know if the node is for and attribute or directory tree,244	 * so only fail if the count is outside both bounds245	 */246	if (ichdr.count > mp->m_dir_geo->node_ents &&247	    ichdr.count > mp->m_attr_geo->node_ents)248		return __this_address;249 250	/* XXX: hash order check? */251 252	return NULL;253}254 255xfs_failaddr_t256xfs_da3_node_header_check(257	struct xfs_buf		*bp,258	xfs_ino_t		owner)259{260	struct xfs_mount	*mp = bp->b_mount;261 262	if (xfs_has_crc(mp)) {263		struct xfs_da3_blkinfo *hdr3 = bp->b_addr;264 265		if (hdr3->hdr.magic != cpu_to_be16(XFS_DA3_NODE_MAGIC))266			return __this_address;267 268		if (be64_to_cpu(hdr3->owner) != owner)269			return __this_address;270	}271 272	return NULL;273}274 275xfs_failaddr_t276xfs_da3_header_check(277	struct xfs_buf		*bp,278	xfs_ino_t		owner)279{280	struct xfs_mount	*mp = bp->b_mount;281	struct xfs_da_blkinfo	*hdr = bp->b_addr;282 283	if (!xfs_has_crc(mp))284		return NULL;285 286	switch (hdr->magic) {287	case cpu_to_be16(XFS_ATTR3_LEAF_MAGIC):288		return xfs_attr3_leaf_header_check(bp, owner);289	case cpu_to_be16(XFS_DA3_NODE_MAGIC):290		return xfs_da3_node_header_check(bp, owner);291	case cpu_to_be16(XFS_DIR3_LEAF1_MAGIC):292	case cpu_to_be16(XFS_DIR3_LEAFN_MAGIC):293		return xfs_dir3_leaf_header_check(bp, owner);294	}295 296	ASSERT(0);297	return NULL;298}299 300static void301xfs_da3_node_write_verify(302	struct xfs_buf	*bp)303{304	struct xfs_mount	*mp = bp->b_mount;305	struct xfs_buf_log_item	*bip = bp->b_log_item;306	struct xfs_da3_node_hdr *hdr3 = bp->b_addr;307	xfs_failaddr_t		fa;308 309	fa = xfs_da3_node_verify(bp);310	if (fa) {311		xfs_verifier_error(bp, -EFSCORRUPTED, fa);312		return;313	}314 315	if (!xfs_has_crc(mp))316		return;317 318	if (bip)319		hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);320 321	xfs_buf_update_cksum(bp, XFS_DA3_NODE_CRC_OFF);322}323 324/*325 * leaf/node format detection on trees is sketchy, so a node read can be done on326 * leaf level blocks when detection identifies the tree as a node format tree327 * incorrectly. In this case, we need to swap the verifier to match the correct328 * format of the block being read.329 */330static void331xfs_da3_node_read_verify(332	struct xfs_buf		*bp)333{334	struct xfs_da_blkinfo	*info = bp->b_addr;335	xfs_failaddr_t		fa;336 337	switch (be16_to_cpu(info->magic)) {338		case XFS_DA3_NODE_MAGIC:339			if (!xfs_buf_verify_cksum(bp, XFS_DA3_NODE_CRC_OFF)) {340				xfs_verifier_error(bp, -EFSBADCRC,341						__this_address);342				break;343			}344			fallthrough;345		case XFS_DA_NODE_MAGIC:346			fa = xfs_da3_node_verify(bp);347			if (fa)348				xfs_verifier_error(bp, -EFSCORRUPTED, fa);349			return;350		case XFS_ATTR_LEAF_MAGIC:351		case XFS_ATTR3_LEAF_MAGIC:352			bp->b_ops = &xfs_attr3_leaf_buf_ops;353			bp->b_ops->verify_read(bp);354			return;355		case XFS_DIR2_LEAFN_MAGIC:356		case XFS_DIR3_LEAFN_MAGIC:357			bp->b_ops = &xfs_dir3_leafn_buf_ops;358			bp->b_ops->verify_read(bp);359			return;360		default:361			xfs_verifier_error(bp, -EFSCORRUPTED, __this_address);362			break;363	}364}365 366/* Verify the structure of a da3 block. */367static xfs_failaddr_t368xfs_da3_node_verify_struct(369	struct xfs_buf		*bp)370{371	struct xfs_da_blkinfo	*info = bp->b_addr;372 373	switch (be16_to_cpu(info->magic)) {374	case XFS_DA3_NODE_MAGIC:375	case XFS_DA_NODE_MAGIC:376		return xfs_da3_node_verify(bp);377	case XFS_ATTR_LEAF_MAGIC:378	case XFS_ATTR3_LEAF_MAGIC:379		bp->b_ops = &xfs_attr3_leaf_buf_ops;380		return bp->b_ops->verify_struct(bp);381	case XFS_DIR2_LEAFN_MAGIC:382	case XFS_DIR3_LEAFN_MAGIC:383		bp->b_ops = &xfs_dir3_leafn_buf_ops;384		return bp->b_ops->verify_struct(bp);385	default:386		return __this_address;387	}388}389 390const struct xfs_buf_ops xfs_da3_node_buf_ops = {391	.name = "xfs_da3_node",392	.magic16 = { cpu_to_be16(XFS_DA_NODE_MAGIC),393		     cpu_to_be16(XFS_DA3_NODE_MAGIC) },394	.verify_read = xfs_da3_node_read_verify,395	.verify_write = xfs_da3_node_write_verify,396	.verify_struct = xfs_da3_node_verify_struct,397};398 399static int400xfs_da3_node_set_type(401	struct xfs_trans	*tp,402	struct xfs_inode	*dp,403	int			whichfork,404	struct xfs_buf		*bp)405{406	struct xfs_da_blkinfo	*info = bp->b_addr;407 408	switch (be16_to_cpu(info->magic)) {409	case XFS_DA_NODE_MAGIC:410	case XFS_DA3_NODE_MAGIC:411		xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);412		return 0;413	case XFS_ATTR_LEAF_MAGIC:414	case XFS_ATTR3_LEAF_MAGIC:415		xfs_trans_buf_set_type(tp, bp, XFS_BLFT_ATTR_LEAF_BUF);416		return 0;417	case XFS_DIR2_LEAFN_MAGIC:418	case XFS_DIR3_LEAFN_MAGIC:419		xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);420		return 0;421	default:422		XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, tp->t_mountp,423				info, sizeof(*info));424		xfs_trans_brelse(tp, bp);425		xfs_dirattr_mark_sick(dp, whichfork);426		return -EFSCORRUPTED;427	}428}429 430int431xfs_da3_node_read(432	struct xfs_trans	*tp,433	struct xfs_inode	*dp,434	xfs_dablk_t		bno,435	struct xfs_buf		**bpp,436	int			whichfork)437{438	int			error;439 440	error = xfs_da_read_buf(tp, dp, bno, 0, bpp, whichfork,441			&xfs_da3_node_buf_ops);442	if (error || !*bpp || !tp)443		return error;444	return xfs_da3_node_set_type(tp, dp, whichfork, *bpp);445}446 447int448xfs_da3_node_read_mapped(449	struct xfs_trans	*tp,450	struct xfs_inode	*dp,451	xfs_daddr_t		mappedbno,452	struct xfs_buf		**bpp,453	int			whichfork)454{455	struct xfs_mount	*mp = dp->i_mount;456	int			error;457 458	error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, mappedbno,459			XFS_FSB_TO_BB(mp, xfs_dabuf_nfsb(mp, whichfork)), 0,460			bpp, &xfs_da3_node_buf_ops);461	if (xfs_metadata_is_sick(error))462		xfs_dirattr_mark_sick(dp, whichfork);463	if (error || !*bpp)464		return error;465 466	if (whichfork == XFS_ATTR_FORK)467		xfs_buf_set_ref(*bpp, XFS_ATTR_BTREE_REF);468	else469		xfs_buf_set_ref(*bpp, XFS_DIR_BTREE_REF);470 471	if (!tp)472		return 0;473	return xfs_da3_node_set_type(tp, dp, whichfork, *bpp);474}475 476/*477 * Copy src directory/attr leaf/node buffer to the dst.478 * For v5 file systems make sure the right blkno is stamped in.479 */480void481xfs_da_buf_copy(482	struct xfs_buf *dst,483	struct xfs_buf *src,484	size_t size)485{486	struct xfs_da3_blkinfo *da3 = dst->b_addr;487 488	memcpy(dst->b_addr, src->b_addr, size);489	dst->b_ops = src->b_ops;490	xfs_trans_buf_copy_type(dst, src);491	if (xfs_has_crc(dst->b_mount))492		da3->blkno = cpu_to_be64(xfs_buf_daddr(dst));493}494 495/*========================================================================496 * Routines used for growing the Btree.497 *========================================================================*/498 499/*500 * Create the initial contents of an intermediate node.501 */502int503xfs_da3_node_create(504	struct xfs_da_args	*args,505	xfs_dablk_t		blkno,506	int			level,507	struct xfs_buf		**bpp,508	int			whichfork)509{510	struct xfs_da_intnode	*node;511	struct xfs_trans	*tp = args->trans;512	struct xfs_mount	*mp = tp->t_mountp;513	struct xfs_da3_icnode_hdr ichdr = {0};514	struct xfs_buf		*bp;515	int			error;516	struct xfs_inode	*dp = args->dp;517 518	trace_xfs_da_node_create(args);519	ASSERT(level <= XFS_DA_NODE_MAXDEPTH);520 521	error = xfs_da_get_buf(tp, dp, blkno, &bp, whichfork);522	if (error)523		return error;524	bp->b_ops = &xfs_da3_node_buf_ops;525	xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);526	node = bp->b_addr;527 528	if (xfs_has_crc(mp)) {529		struct xfs_da3_node_hdr *hdr3 = bp->b_addr;530 531		memset(hdr3, 0, sizeof(struct xfs_da3_node_hdr));532		ichdr.magic = XFS_DA3_NODE_MAGIC;533		hdr3->info.blkno = cpu_to_be64(xfs_buf_daddr(bp));534		hdr3->info.owner = cpu_to_be64(args->owner);535		uuid_copy(&hdr3->info.uuid, &mp->m_sb.sb_meta_uuid);536	} else {537		ichdr.magic = XFS_DA_NODE_MAGIC;538	}539	ichdr.level = level;540 541	xfs_da3_node_hdr_to_disk(dp->i_mount, node, &ichdr);542	xfs_trans_log_buf(tp, bp,543		XFS_DA_LOGRANGE(node, &node->hdr, args->geo->node_hdr_size));544 545	*bpp = bp;546	return 0;547}548 549/*550 * Split a leaf node, rebalance, then possibly split551 * intermediate nodes, rebalance, etc.552 */553int							/* error */554xfs_da3_split(555	struct xfs_da_state	*state)556{557	struct xfs_da_state_blk	*oldblk;558	struct xfs_da_state_blk	*newblk;559	struct xfs_da_state_blk	*addblk;560	struct xfs_da_intnode	*node;561	int			max;562	int			action = 0;563	int			error;564	int			i;565 566	trace_xfs_da_split(state->args);567 568	if (XFS_TEST_ERROR(false, state->mp, XFS_ERRTAG_DA_LEAF_SPLIT))569		return -EIO;570 571	/*572	 * Walk back up the tree splitting/inserting/adjusting as necessary.573	 * If we need to insert and there isn't room, split the node, then574	 * decide which fragment to insert the new block from below into.575	 * Note that we may split the root this way, but we need more fixup.576	 */577	max = state->path.active - 1;578	ASSERT((max >= 0) && (max < XFS_DA_NODE_MAXDEPTH));579	ASSERT(state->path.blk[max].magic == XFS_ATTR_LEAF_MAGIC ||580	       state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);581 582	addblk = &state->path.blk[max];		/* initial dummy value */583	for (i = max; (i >= 0) && addblk; state->path.active--, i--) {584		oldblk = &state->path.blk[i];585		newblk = &state->altpath.blk[i];586 587		/*588		 * If a leaf node then589		 *     Allocate a new leaf node, then rebalance across them.590		 * else if an intermediate node then591		 *     We split on the last layer, must we split the node?592		 */593		switch (oldblk->magic) {594		case XFS_ATTR_LEAF_MAGIC:595			error = xfs_attr3_leaf_split(state, oldblk, newblk);596			if (error < 0)597				return error;	/* GROT: attr is inconsistent */598			if (!error) {599				addblk = newblk;600				break;601			}602			/*603			 * Entry wouldn't fit, split the leaf again. The new604			 * extrablk will be consumed by xfs_da3_node_split if605			 * the node is split.606			 */607			state->extravalid = 1;608			if (state->inleaf) {609				state->extraafter = 0;	/* before newblk */610				trace_xfs_attr_leaf_split_before(state->args);611				error = xfs_attr3_leaf_split(state, oldblk,612							    &state->extrablk);613			} else {614				state->extraafter = 1;	/* after newblk */615				trace_xfs_attr_leaf_split_after(state->args);616				error = xfs_attr3_leaf_split(state, newblk,617							    &state->extrablk);618			}619			if (error == 1)620				return -ENOSPC;621			if (error)622				return error;	/* GROT: attr inconsistent */623			addblk = newblk;624			break;625		case XFS_DIR2_LEAFN_MAGIC:626			error = xfs_dir2_leafn_split(state, oldblk, newblk);627			if (error)628				return error;629			addblk = newblk;630			break;631		case XFS_DA_NODE_MAGIC:632			error = xfs_da3_node_split(state, oldblk, newblk, addblk,633							 max - i, &action);634			addblk->bp = NULL;635			if (error)636				return error;	/* GROT: dir is inconsistent */637			/*638			 * Record the newly split block for the next time thru?639			 */640			if (action)641				addblk = newblk;642			else643				addblk = NULL;644			break;645		}646 647		/*648		 * Update the btree to show the new hashval for this child.649		 */650		xfs_da3_fixhashpath(state, &state->path);651	}652	if (!addblk)653		return 0;654 655	/*656	 * xfs_da3_node_split() should have consumed any extra blocks we added657	 * during a double leaf split in the attr fork. This is guaranteed as658	 * we can't be here if the attr fork only has a single leaf block.659	 */660	ASSERT(state->extravalid == 0 ||661	       state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);662 663	/*664	 * Split the root node.665	 */666	ASSERT(state->path.active == 0);667	oldblk = &state->path.blk[0];668	error = xfs_da3_root_split(state, oldblk, addblk);669	if (error)670		goto out;671 672	/*673	 * Update pointers to the node which used to be block 0 and just got674	 * bumped because of the addition of a new root node.  Note that the675	 * original block 0 could be at any position in the list of blocks in676	 * the tree.677	 *678	 * Note: the magic numbers and sibling pointers are in the same physical679	 * place for both v2 and v3 headers (by design). Hence it doesn't matter680	 * which version of the xfs_da_intnode structure we use here as the681	 * result will be the same using either structure.682	 */683	node = oldblk->bp->b_addr;684	if (node->hdr.info.forw) {685		if (be32_to_cpu(node->hdr.info.forw) != addblk->blkno) {686			xfs_buf_mark_corrupt(oldblk->bp);687			xfs_da_mark_sick(state->args);688			error = -EFSCORRUPTED;689			goto out;690		}691		node = addblk->bp->b_addr;692		node->hdr.info.back = cpu_to_be32(oldblk->blkno);693		xfs_trans_log_buf(state->args->trans, addblk->bp,694				  XFS_DA_LOGRANGE(node, &node->hdr.info,695				  sizeof(node->hdr.info)));696	}697	node = oldblk->bp->b_addr;698	if (node->hdr.info.back) {699		if (be32_to_cpu(node->hdr.info.back) != addblk->blkno) {700			xfs_buf_mark_corrupt(oldblk->bp);701			xfs_da_mark_sick(state->args);702			error = -EFSCORRUPTED;703			goto out;704		}705		node = addblk->bp->b_addr;706		node->hdr.info.forw = cpu_to_be32(oldblk->blkno);707		xfs_trans_log_buf(state->args->trans, addblk->bp,708				  XFS_DA_LOGRANGE(node, &node->hdr.info,709				  sizeof(node->hdr.info)));710	}711out:712	addblk->bp = NULL;713	return error;714}715 716/*717 * Split the root.  We have to create a new root and point to the two718 * parts (the split old root) that we just created.  Copy block zero to719 * the EOF, extending the inode in process.720 */721STATIC int						/* error */722xfs_da3_root_split(723	struct xfs_da_state	*state,724	struct xfs_da_state_blk	*blk1,725	struct xfs_da_state_blk	*blk2)726{727	struct xfs_da_intnode	*node;728	struct xfs_da_intnode	*oldroot;729	struct xfs_da_node_entry *btree;730	struct xfs_da3_icnode_hdr nodehdr;731	struct xfs_da_args	*args;732	struct xfs_buf		*bp;733	struct xfs_inode	*dp;734	struct xfs_trans	*tp;735	struct xfs_dir2_leaf	*leaf;736	xfs_dablk_t		blkno;737	int			level;738	int			error;739	int			size;740 741	trace_xfs_da_root_split(state->args);742 743	/*744	 * Copy the existing (incorrect) block from the root node position745	 * to a free space somewhere.746	 */747	args = state->args;748	error = xfs_da_grow_inode(args, &blkno);749	if (error)750		return error;751 752	dp = args->dp;753	tp = args->trans;754	error = xfs_da_get_buf(tp, dp, blkno, &bp, args->whichfork);755	if (error)756		return error;757	node = bp->b_addr;758	oldroot = blk1->bp->b_addr;759	if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||760	    oldroot->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC)) {761		struct xfs_da3_icnode_hdr icnodehdr;762 763		xfs_da3_node_hdr_from_disk(dp->i_mount, &icnodehdr, oldroot);764		btree = icnodehdr.btree;765		size = (int)((char *)&btree[icnodehdr.count] - (char *)oldroot);766		level = icnodehdr.level;767	} else {768		struct xfs_dir3_icleaf_hdr leafhdr;769 770		leaf = (xfs_dir2_leaf_t *)oldroot;771		xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf);772 773		ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||774		       leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);775		size = (int)((char *)&leafhdr.ents[leafhdr.count] -776			(char *)leaf);777		level = 0;778	}779 780	/*781	 * Copy old root to new buffer and log it.782	 */783	xfs_da_buf_copy(bp, blk1->bp, size);784	xfs_trans_log_buf(tp, bp, 0, size - 1);785 786	/*787	 * Update blk1 to point to new buffer.788	 */789	blk1->bp = bp;790	blk1->blkno = blkno;791 792	/*793	 * Set up the new root node.794	 */795	error = xfs_da3_node_create(args,796		(args->whichfork == XFS_DATA_FORK) ? args->geo->leafblk : 0,797		level + 1, &bp, args->whichfork);798	if (error)799		return error;800 801	node = bp->b_addr;802	xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);803	btree = nodehdr.btree;804	btree[0].hashval = cpu_to_be32(blk1->hashval);805	btree[0].before = cpu_to_be32(blk1->blkno);806	btree[1].hashval = cpu_to_be32(blk2->hashval);807	btree[1].before = cpu_to_be32(blk2->blkno);808	nodehdr.count = 2;809	xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);810 811#ifdef DEBUG812	if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||813	    oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {814		ASSERT(blk1->blkno >= args->geo->leafblk &&815		       blk1->blkno < args->geo->freeblk);816		ASSERT(blk2->blkno >= args->geo->leafblk &&817		       blk2->blkno < args->geo->freeblk);818	}819#endif820 821	/* Header is already logged by xfs_da_node_create */822	xfs_trans_log_buf(tp, bp,823		XFS_DA_LOGRANGE(node, btree, sizeof(xfs_da_node_entry_t) * 2));824 825	return 0;826}827 828/*829 * Split the node, rebalance, then add the new entry.830 */831STATIC int						/* error */832xfs_da3_node_split(833	struct xfs_da_state	*state,834	struct xfs_da_state_blk	*oldblk,835	struct xfs_da_state_blk	*newblk,836	struct xfs_da_state_blk	*addblk,837	int			treelevel,838	int			*result)839{840	struct xfs_da_intnode	*node;841	struct xfs_da3_icnode_hdr nodehdr;842	xfs_dablk_t		blkno;843	int			newcount;844	int			error;845	int			useextra;846	struct xfs_inode	*dp = state->args->dp;847 848	trace_xfs_da_node_split(state->args);849 850	node = oldblk->bp->b_addr;851	xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);852 853	/*854	 * With V2 dirs the extra block is data or freespace.855	 */856	useextra = state->extravalid && state->args->whichfork == XFS_ATTR_FORK;857	newcount = 1 + useextra;858	/*859	 * Do we have to split the node?860	 */861	if (nodehdr.count + newcount > state->args->geo->node_ents) {862		/*863		 * Allocate a new node, add to the doubly linked chain of864		 * nodes, then move some of our excess entries into it.865		 */866		error = xfs_da_grow_inode(state->args, &blkno);867		if (error)868			return error;	/* GROT: dir is inconsistent */869 870		error = xfs_da3_node_create(state->args, blkno, treelevel,871					   &newblk->bp, state->args->whichfork);872		if (error)873			return error;	/* GROT: dir is inconsistent */874		newblk->blkno = blkno;875		newblk->magic = XFS_DA_NODE_MAGIC;876		xfs_da3_node_rebalance(state, oldblk, newblk);877		error = xfs_da3_blk_link(state, oldblk, newblk);878		if (error)879			return error;880		*result = 1;881	} else {882		*result = 0;883	}884 885	/*886	 * Insert the new entry(s) into the correct block887	 * (updating last hashval in the process).888	 *889	 * xfs_da3_node_add() inserts BEFORE the given index,890	 * and as a result of using node_lookup_int() we always891	 * point to a valid entry (not after one), but a split892	 * operation always results in a new block whose hashvals893	 * FOLLOW the current block.894	 *895	 * If we had double-split op below us, then add the extra block too.896	 */897	node = oldblk->bp->b_addr;898	xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);899	if (oldblk->index <= nodehdr.count) {900		oldblk->index++;901		xfs_da3_node_add(state, oldblk, addblk);902		if (useextra) {903			if (state->extraafter)904				oldblk->index++;905			xfs_da3_node_add(state, oldblk, &state->extrablk);906			state->extravalid = 0;907		}908	} else {909		newblk->index++;910		xfs_da3_node_add(state, newblk, addblk);911		if (useextra) {912			if (state->extraafter)913				newblk->index++;914			xfs_da3_node_add(state, newblk, &state->extrablk);915			state->extravalid = 0;916		}917	}918 919	return 0;920}921 922/*923 * Balance the btree elements between two intermediate nodes,924 * usually one full and one empty.925 *926 * NOTE: if blk2 is empty, then it will get the upper half of blk1.927 */928STATIC void929xfs_da3_node_rebalance(930	struct xfs_da_state	*state,931	struct xfs_da_state_blk	*blk1,932	struct xfs_da_state_blk	*blk2)933{934	struct xfs_da_intnode	*node1;935	struct xfs_da_intnode	*node2;936	struct xfs_da_node_entry *btree1;937	struct xfs_da_node_entry *btree2;938	struct xfs_da_node_entry *btree_s;939	struct xfs_da_node_entry *btree_d;940	struct xfs_da3_icnode_hdr nodehdr1;941	struct xfs_da3_icnode_hdr nodehdr2;942	struct xfs_trans	*tp;943	int			count;944	int			tmp;945	int			swap = 0;946	struct xfs_inode	*dp = state->args->dp;947 948	trace_xfs_da_node_rebalance(state->args);949 950	node1 = blk1->bp->b_addr;951	node2 = blk2->bp->b_addr;952	xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);953	xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);954	btree1 = nodehdr1.btree;955	btree2 = nodehdr2.btree;956 957	/*958	 * Figure out how many entries need to move, and in which direction.959	 * Swap the nodes around if that makes it simpler.960	 */961	if (nodehdr1.count > 0 && nodehdr2.count > 0 &&962	    ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||963	     (be32_to_cpu(btree2[nodehdr2.count - 1].hashval) <964			be32_to_cpu(btree1[nodehdr1.count - 1].hashval)))) {965		swap(node1, node2);966		xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);967		xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);968		btree1 = nodehdr1.btree;969		btree2 = nodehdr2.btree;970		swap = 1;971	}972 973	count = (nodehdr1.count - nodehdr2.count) / 2;974	if (count == 0)975		return;976	tp = state->args->trans;977	/*978	 * Two cases: high-to-low and low-to-high.979	 */980	if (count > 0) {981		/*982		 * Move elements in node2 up to make a hole.983		 */984		tmp = nodehdr2.count;985		if (tmp > 0) {986			tmp *= (uint)sizeof(xfs_da_node_entry_t);987			btree_s = &btree2[0];988			btree_d = &btree2[count];989			memmove(btree_d, btree_s, tmp);990		}991 992		/*993		 * Move the req'd B-tree elements from high in node1 to994		 * low in node2.995		 */996		nodehdr2.count += count;997		tmp = count * (uint)sizeof(xfs_da_node_entry_t);998		btree_s = &btree1[nodehdr1.count - count];999		btree_d = &btree2[0];1000		memcpy(btree_d, btree_s, tmp);1001		nodehdr1.count -= count;1002	} else {1003		/*1004		 * Move the req'd B-tree elements from low in node2 to1005		 * high in node1.1006		 */1007		count = -count;1008		tmp = count * (uint)sizeof(xfs_da_node_entry_t);1009		btree_s = &btree2[0];1010		btree_d = &btree1[nodehdr1.count];1011		memcpy(btree_d, btree_s, tmp);1012		nodehdr1.count += count;1013 1014		xfs_trans_log_buf(tp, blk1->bp,1015			XFS_DA_LOGRANGE(node1, btree_d, tmp));1016 1017		/*1018		 * Move elements in node2 down to fill the hole.1019		 */1020		tmp  = nodehdr2.count - count;1021		tmp *= (uint)sizeof(xfs_da_node_entry_t);1022		btree_s = &btree2[count];1023		btree_d = &btree2[0];1024		memmove(btree_d, btree_s, tmp);1025		nodehdr2.count -= count;1026	}1027 1028	/*1029	 * Log header of node 1 and all current bits of node 2.1030	 */1031	xfs_da3_node_hdr_to_disk(dp->i_mount, node1, &nodehdr1);1032	xfs_trans_log_buf(tp, blk1->bp,1033		XFS_DA_LOGRANGE(node1, &node1->hdr,1034				state->args->geo->node_hdr_size));1035 1036	xfs_da3_node_hdr_to_disk(dp->i_mount, node2, &nodehdr2);1037	xfs_trans_log_buf(tp, blk2->bp,1038		XFS_DA_LOGRANGE(node2, &node2->hdr,1039				state->args->geo->node_hdr_size +1040				(sizeof(btree2[0]) * nodehdr2.count)));1041 1042	/*1043	 * Record the last hashval from each block for upward propagation.1044	 * (note: don't use the swapped node pointers)1045	 */1046	if (swap) {1047		node1 = blk1->bp->b_addr;1048		node2 = blk2->bp->b_addr;1049		xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);1050		xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);1051		btree1 = nodehdr1.btree;1052		btree2 = nodehdr2.btree;1053	}1054	blk1->hashval = be32_to_cpu(btree1[nodehdr1.count - 1].hashval);1055	blk2->hashval = be32_to_cpu(btree2[nodehdr2.count - 1].hashval);1056 1057	/*1058	 * Adjust the expected index for insertion.1059	 */1060	if (blk1->index >= nodehdr1.count) {1061		blk2->index = blk1->index - nodehdr1.count;1062		blk1->index = nodehdr1.count + 1;	/* make it invalid */1063	}1064}1065 1066/*1067 * Add a new entry to an intermediate node.1068 */1069STATIC void1070xfs_da3_node_add(1071	struct xfs_da_state	*state,1072	struct xfs_da_state_blk	*oldblk,1073	struct xfs_da_state_blk	*newblk)1074{1075	struct xfs_da_intnode	*node;1076	struct xfs_da3_icnode_hdr nodehdr;1077	struct xfs_da_node_entry *btree;1078	int			tmp;1079	struct xfs_inode	*dp = state->args->dp;1080 1081	trace_xfs_da_node_add(state->args);1082 1083	node = oldblk->bp->b_addr;1084	xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);1085	btree = nodehdr.btree;1086 1087	ASSERT(oldblk->index >= 0 && oldblk->index <= nodehdr.count);1088	ASSERT(newblk->blkno != 0);1089	if (state->args->whichfork == XFS_DATA_FORK)1090		ASSERT(newblk->blkno >= state->args->geo->leafblk &&1091		       newblk->blkno < state->args->geo->freeblk);1092 1093	/*1094	 * We may need to make some room before we insert the new node.1095	 */1096	tmp = 0;1097	if (oldblk->index < nodehdr.count) {1098		tmp = (nodehdr.count - oldblk->index) * (uint)sizeof(*btree);1099		memmove(&btree[oldblk->index + 1], &btree[oldblk->index], tmp);1100	}1101	btree[oldblk->index].hashval = cpu_to_be32(newblk->hashval);1102	btree[oldblk->index].before = cpu_to_be32(newblk->blkno);1103	xfs_trans_log_buf(state->args->trans, oldblk->bp,1104		XFS_DA_LOGRANGE(node, &btree[oldblk->index],1105				tmp + sizeof(*btree)));1106 1107	nodehdr.count += 1;1108	xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);1109	xfs_trans_log_buf(state->args->trans, oldblk->bp,1110		XFS_DA_LOGRANGE(node, &node->hdr,1111				state->args->geo->node_hdr_size));1112 1113	/*1114	 * Copy the last hash value from the oldblk to propagate upwards.1115	 */1116	oldblk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);1117}1118 1119/*========================================================================1120 * Routines used for shrinking the Btree.1121 *========================================================================*/1122 1123/*1124 * Deallocate an empty leaf node, remove it from its parent,1125 * possibly deallocating that block, etc...1126 */1127int1128xfs_da3_join(1129	struct xfs_da_state	*state)1130{1131	struct xfs_da_state_blk	*drop_blk;1132	struct xfs_da_state_blk	*save_blk;1133	int			action = 0;1134	int			error;1135 1136	trace_xfs_da_join(state->args);1137 1138	drop_blk = &state->path.blk[ state->path.active-1 ];1139	save_blk = &state->altpath.blk[ state->path.active-1 ];1140	ASSERT(state->path.blk[0].magic == XFS_DA_NODE_MAGIC);1141	ASSERT(drop_blk->magic == XFS_ATTR_LEAF_MAGIC ||1142	       drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);1143 1144	/*1145	 * Walk back up the tree joining/deallocating as necessary.1146	 * When we stop dropping blocks, break out.1147	 */1148	for (  ; state->path.active >= 2; drop_blk--, save_blk--,1149		 state->path.active--) {1150		/*1151		 * See if we can combine the block with a neighbor.1152		 *   (action == 0) => no options, just leave1153		 *   (action == 1) => coalesce, then unlink1154		 *   (action == 2) => block empty, unlink it1155		 */1156		switch (drop_blk->magic) {1157		case XFS_ATTR_LEAF_MAGIC:1158			error = xfs_attr3_leaf_toosmall(state, &action);1159			if (error)1160				return error;1161			if (action == 0)1162				return 0;1163			xfs_attr3_leaf_unbalance(state, drop_blk, save_blk);1164			break;1165		case XFS_DIR2_LEAFN_MAGIC:1166			error = xfs_dir2_leafn_toosmall(state, &action);1167			if (error)1168				return error;1169			if (action == 0)1170				return 0;1171			xfs_dir2_leafn_unbalance(state, drop_blk, save_blk);1172			break;1173		case XFS_DA_NODE_MAGIC:1174			/*1175			 * Remove the offending node, fixup hashvals,1176			 * check for a toosmall neighbor.1177			 */1178			xfs_da3_node_remove(state, drop_blk);1179			xfs_da3_fixhashpath(state, &state->path);1180			error = xfs_da3_node_toosmall(state, &action);1181			if (error)1182				return error;1183			if (action == 0)1184				return 0;1185			xfs_da3_node_unbalance(state, drop_blk, save_blk);1186			break;1187		}1188		xfs_da3_fixhashpath(state, &state->altpath);1189		error = xfs_da3_blk_unlink(state, drop_blk, save_blk);1190		xfs_da_state_kill_altpath(state);1191		if (error)1192			return error;1193		error = xfs_da_shrink_inode(state->args, drop_blk->blkno,1194							 drop_blk->bp);1195		drop_blk->bp = NULL;1196		if (error)1197			return error;1198	}1199	/*1200	 * We joined all the way to the top.  If it turns out that1201	 * we only have one entry in the root, make the child block1202	 * the new root.1203	 */1204	xfs_da3_node_remove(state, drop_blk);1205	xfs_da3_fixhashpath(state, &state->path);1206	error = xfs_da3_root_join(state, &state->path.blk[0]);1207	return error;1208}1209 1210#ifdef	DEBUG1211static void1212xfs_da_blkinfo_onlychild_validate(struct xfs_da_blkinfo *blkinfo, __u16 level)1213{1214	__be16	magic = blkinfo->magic;1215 1216	if (level == 1) {1217		ASSERT(magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||1218		       magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||1219		       magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||1220		       magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));1221	} else {1222		ASSERT(magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||1223		       magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));1224	}1225	ASSERT(!blkinfo->forw);1226	ASSERT(!blkinfo->back);1227}1228#else	/* !DEBUG */1229#define	xfs_da_blkinfo_onlychild_validate(blkinfo, level)1230#endif	/* !DEBUG */1231 1232/*1233 * We have only one entry in the root.  Copy the only remaining child of1234 * the old root to block 0 as the new root node.1235 */1236STATIC int1237xfs_da3_root_join(1238	struct xfs_da_state	*state,1239	struct xfs_da_state_blk	*root_blk)1240{1241	struct xfs_da_intnode	*oldroot;1242	struct xfs_da_args	*args;1243	xfs_dablk_t		child;1244	struct xfs_buf		*bp;1245	struct xfs_da3_icnode_hdr oldroothdr;1246	int			error;1247	struct xfs_inode	*dp = state->args->dp;1248	xfs_failaddr_t		fa;1249 1250	trace_xfs_da_root_join(state->args);1251 1252	ASSERT(root_blk->magic == XFS_DA_NODE_MAGIC);1253 1254	args = state->args;1255	oldroot = root_blk->bp->b_addr;1256	xfs_da3_node_hdr_from_disk(dp->i_mount, &oldroothdr, oldroot);1257	ASSERT(oldroothdr.forw == 0);1258	ASSERT(oldroothdr.back == 0);1259 1260	/*1261	 * If the root has more than one child, then don't do anything.1262	 */1263	if (oldroothdr.count > 1)1264		return 0;1265 1266	/*1267	 * Read in the (only) child block, then copy those bytes into1268	 * the root block's buffer and free the original child block.1269	 */1270	child = be32_to_cpu(oldroothdr.btree[0].before);1271	ASSERT(child != 0);1272	error = xfs_da3_node_read(args->trans, dp, child, &bp, args->whichfork);1273	if (error)1274		return error;1275	fa = xfs_da3_header_check(bp, args->owner);1276	if (fa) {1277		__xfs_buf_mark_corrupt(bp, fa);1278		xfs_trans_brelse(args->trans, bp);1279		xfs_da_mark_sick(args);1280		return -EFSCORRUPTED;1281	}1282	xfs_da_blkinfo_onlychild_validate(bp->b_addr, oldroothdr.level);1283 1284	/*1285	 * Copy child to root buffer and log it.1286	 */1287	xfs_da_buf_copy(root_blk->bp, bp, args->geo->blksize);1288	xfs_trans_log_buf(args->trans, root_blk->bp, 0,1289			  args->geo->blksize - 1);1290	/*1291	 * Now we can drop the child buffer.1292	 */1293	error = xfs_da_shrink_inode(args, child, bp);1294	return error;1295}1296 1297/*1298 * Check a node block and its neighbors to see if the block should be1299 * collapsed into one or the other neighbor.  Always keep the block1300 * with the smaller block number.1301 * If the current block is over 50% full, don't try to join it, return 0.1302 * If the block is empty, fill in the state structure and return 2.1303 * If it can be collapsed, fill in the state structure and return 1.1304 * If nothing can be done, return 0.1305 */1306STATIC int1307xfs_da3_node_toosmall(1308	struct xfs_da_state	*state,1309	int			*action)1310{1311	struct xfs_da_intnode	*node;1312	struct xfs_da_state_blk	*blk;1313	struct xfs_da_blkinfo	*info;1314	xfs_dablk_t		blkno;1315	struct xfs_buf		*bp;1316	xfs_failaddr_t		fa;1317	struct xfs_da3_icnode_hdr nodehdr;1318	int			count;1319	int			forward;1320	int			error;1321	int			retval;1322	int			i;1323	struct xfs_inode	*dp = state->args->dp;1324 1325	trace_xfs_da_node_toosmall(state->args);1326 1327	/*1328	 * Check for the degenerate case of the block being over 50% full.1329	 * If so, it's not worth even looking to see if we might be able1330	 * to coalesce with a sibling.1331	 */1332	blk = &state->path.blk[ state->path.active-1 ];1333	info = blk->bp->b_addr;1334	node = (xfs_da_intnode_t *)info;1335	xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);1336	if (nodehdr.count > (state->args->geo->node_ents >> 1)) {1337		*action = 0;	/* blk over 50%, don't try to join */1338		return 0;	/* blk over 50%, don't try to join */1339	}1340 1341	/*1342	 * Check for the degenerate case of the block being empty.1343	 * If the block is empty, we'll simply delete it, no need to1344	 * coalesce it with a sibling block.  We choose (arbitrarily)1345	 * to merge with the forward block unless it is NULL.1346	 */1347	if (nodehdr.count == 0) {1348		/*1349		 * Make altpath point to the block we want to keep and1350		 * path point to the block we want to drop (this one).1351		 */1352		forward = (info->forw != 0);1353		memcpy(&state->altpath, &state->path, sizeof(state->path));1354		error = xfs_da3_path_shift(state, &state->altpath, forward,1355						 0, &retval);1356		if (error)1357			return error;1358		if (retval) {1359			*action = 0;1360		} else {1361			*action = 2;1362		}1363		return 0;1364	}1365 1366	/*1367	 * Examine each sibling block to see if we can coalesce with1368	 * at least 25% free space to spare.  We need to figure out1369	 * whether to merge with the forward or the backward block.1370	 * We prefer coalescing with the lower numbered sibling so as1371	 * to shrink a directory over time.1372	 */1373	count  = state->args->geo->node_ents;1374	count -= state->args->geo->node_ents >> 2;1375	count -= nodehdr.count;1376 1377	/* start with smaller blk num */1378	forward = nodehdr.forw < nodehdr.back;1379	for (i = 0; i < 2; forward = !forward, i++) {1380		struct xfs_da3_icnode_hdr thdr;1381		if (forward)1382			blkno = nodehdr.forw;1383		else1384			blkno = nodehdr.back;1385		if (blkno == 0)1386			continue;1387		error = xfs_da3_node_read(state->args->trans, dp, blkno, &bp,1388				state->args->whichfork);1389		if (error)1390			return error;1391		fa = xfs_da3_node_header_check(bp, state->args->owner);1392		if (fa) {1393			__xfs_buf_mark_corrupt(bp, fa);1394			xfs_trans_brelse(state->args->trans, bp);1395			xfs_da_mark_sick(state->args);1396			return -EFSCORRUPTED;1397		}1398 1399		node = bp->b_addr;1400		xfs_da3_node_hdr_from_disk(dp->i_mount, &thdr, node);1401		xfs_trans_brelse(state->args->trans, bp);1402 1403		if (count - thdr.count >= 0)1404			break;	/* fits with at least 25% to spare */1405	}1406	if (i >= 2) {1407		*action = 0;1408		return 0;1409	}1410 1411	/*1412	 * Make altpath point to the block we want to keep (the lower1413	 * numbered block) and path point to the block we want to drop.1414	 */1415	memcpy(&state->altpath, &state->path, sizeof(state->path));1416	if (blkno < blk->blkno) {1417		error = xfs_da3_path_shift(state, &state->altpath, forward,1418						 0, &retval);1419	} else {1420		error = xfs_da3_path_shift(state, &state->path, forward,1421						 0, &retval);1422	}1423	if (error)1424		return error;1425	if (retval) {1426		*action = 0;1427		return 0;1428	}1429	*action = 1;1430	return 0;1431}1432 1433/*1434 * Pick up the last hashvalue from an intermediate node.1435 */1436STATIC uint1437xfs_da3_node_lasthash(1438	struct xfs_inode	*dp,1439	struct xfs_buf		*bp,1440	int			*count)1441{1442	struct xfs_da3_icnode_hdr nodehdr;1443 1444	xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, bp->b_addr);1445	if (count)1446		*count = nodehdr.count;1447	if (!nodehdr.count)1448		return 0;1449	return be32_to_cpu(nodehdr.btree[nodehdr.count - 1].hashval);1450}1451 1452/*1453 * Walk back up the tree adjusting hash values as necessary,1454 * when we stop making changes, return.1455 */1456void1457xfs_da3_fixhashpath(1458	struct xfs_da_state	*state,1459	struct xfs_da_state_path *path)1460{1461	struct xfs_da_state_blk	*blk;1462	struct xfs_da_intnode	*node;1463	struct xfs_da_node_entry *btree;1464	xfs_dahash_t		lasthash=0;1465	int			level;1466	int			count;1467	struct xfs_inode	*dp = state->args->dp;1468 1469	trace_xfs_da_fixhashpath(state->args);1470 1471	level = path->active-1;1472	blk = &path->blk[ level ];1473	switch (blk->magic) {1474	case XFS_ATTR_LEAF_MAGIC:1475		lasthash = xfs_attr_leaf_lasthash(blk->bp, &count);1476		if (count == 0)1477			return;1478		break;1479	case XFS_DIR2_LEAFN_MAGIC:1480		lasthash = xfs_dir2_leaf_lasthash(dp, blk->bp, &count);1481		if (count == 0)1482			return;1483		break;1484	case XFS_DA_NODE_MAGIC:1485		lasthash = xfs_da3_node_lasthash(dp, blk->bp, &count);1486		if (count == 0)1487			return;1488		break;1489	}1490	for (blk--, level--; level >= 0; blk--, level--) {1491		struct xfs_da3_icnode_hdr nodehdr;1492 1493		node = blk->bp->b_addr;1494		xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);1495		btree = nodehdr.btree;1496		if (be32_to_cpu(btree[blk->index].hashval) == lasthash)1497			break;1498		blk->hashval = lasthash;1499		btree[blk->index].hashval = cpu_to_be32(lasthash);1500		xfs_trans_log_buf(state->args->trans, blk->bp,1501				  XFS_DA_LOGRANGE(node, &btree[blk->index],1502						  sizeof(*btree)));1503 1504		lasthash = be32_to_cpu(btree[nodehdr.count - 1].hashval);1505	}1506}1507 1508/*1509 * Remove an entry from an intermediate node.1510 */1511STATIC void1512xfs_da3_node_remove(1513	struct xfs_da_state	*state,1514	struct xfs_da_state_blk	*drop_blk)1515{1516	struct xfs_da_intnode	*node;1517	struct xfs_da3_icnode_hdr nodehdr;1518	struct xfs_da_node_entry *btree;1519	int			index;1520	int			tmp;1521	struct xfs_inode	*dp = state->args->dp;1522 1523	trace_xfs_da_node_remove(state->args);1524 1525	node = drop_blk->bp->b_addr;1526	xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);1527	ASSERT(drop_blk->index < nodehdr.count);1528	ASSERT(drop_blk->index >= 0);1529 1530	/*1531	 * Copy over the offending entry, or just zero it out.1532	 */1533	index = drop_blk->index;1534	btree = nodehdr.btree;1535	if (index < nodehdr.count - 1) {1536		tmp  = nodehdr.count - index - 1;1537		tmp *= (uint)sizeof(xfs_da_node_entry_t);1538		memmove(&btree[index], &btree[index + 1], tmp);1539		xfs_trans_log_buf(state->args->trans, drop_blk->bp,1540		    XFS_DA_LOGRANGE(node, &btree[index], tmp));1541		index = nodehdr.count - 1;1542	}1543	memset(&btree[index], 0, sizeof(xfs_da_node_entry_t));1544	xfs_trans_log_buf(state->args->trans, drop_blk->bp,1545	    XFS_DA_LOGRANGE(node, &btree[index], sizeof(btree[index])));1546	nodehdr.count -= 1;1547	xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);1548	xfs_trans_log_buf(state->args->trans, drop_blk->bp,1549	    XFS_DA_LOGRANGE(node, &node->hdr, state->args->geo->node_hdr_size));1550 1551	/*1552	 * Copy the last hash value from the block to propagate upwards.1553	 */1554	drop_blk->hashval = be32_to_cpu(btree[index - 1].hashval);1555}1556 1557/*1558 * Unbalance the elements between two intermediate nodes,1559 * move all Btree elements from one node into another.1560 */1561STATIC void1562xfs_da3_node_unbalance(1563	struct xfs_da_state	*state,1564	struct xfs_da_state_blk	*drop_blk,1565	struct xfs_da_state_blk	*save_blk)1566{1567	struct xfs_da_intnode	*drop_node;1568	struct xfs_da_intnode	*save_node;1569	struct xfs_da_node_entry *drop_btree;1570	struct xfs_da_node_entry *save_btree;1571	struct xfs_da3_icnode_hdr drop_hdr;1572	struct xfs_da3_icnode_hdr save_hdr;1573	struct xfs_trans	*tp;1574	int			sindex;1575	int			tmp;1576	struct xfs_inode	*dp = state->args->dp;1577 1578	trace_xfs_da_node_unbalance(state->args);1579 1580	drop_node = drop_blk->bp->b_addr;1581	save_node = save_blk->bp->b_addr;1582	xfs_da3_node_hdr_from_disk(dp->i_mount, &drop_hdr, drop_node);1583	xfs_da3_node_hdr_from_disk(dp->i_mount, &save_hdr, save_node);1584	drop_btree = drop_hdr.btree;1585	save_btree = save_hdr.btree;1586	tp = state->args->trans;1587 1588	/*1589	 * If the dying block has lower hashvals, then move all the1590	 * elements in the remaining block up to make a hole.1591	 */1592	if ((be32_to_cpu(drop_btree[0].hashval) <1593			be32_to_cpu(save_btree[0].hashval)) ||1594	    (be32_to_cpu(drop_btree[drop_hdr.count - 1].hashval) <1595			be32_to_cpu(save_btree[save_hdr.count - 1].hashval))) {1596		/* XXX: check this - is memmove dst correct? */1597		tmp = save_hdr.count * sizeof(xfs_da_node_entry_t);1598		memmove(&save_btree[drop_hdr.count], &save_btree[0], tmp);1599 1600		sindex = 0;1601		xfs_trans_log_buf(tp, save_blk->bp,1602			XFS_DA_LOGRANGE(save_node, &save_btree[0],1603				(save_hdr.count + drop_hdr.count) *1604						sizeof(xfs_da_node_entry_t)));1605	} else {1606		sindex = save_hdr.count;1607		xfs_trans_log_buf(tp, save_blk->bp,1608			XFS_DA_LOGRANGE(save_node, &save_btree[sindex],1609				drop_hdr.count * sizeof(xfs_da_node_entry_t)));1610	}1611 1612	/*1613	 * Move all the B-tree elements from drop_blk to save_blk.1614	 */1615	tmp = drop_hdr.count * (uint)sizeof(xfs_da_node_entry_t);1616	memcpy(&save_btree[sindex], &drop_btree[0], tmp);1617	save_hdr.count += drop_hdr.count;1618 1619	xfs_da3_node_hdr_to_disk(dp->i_mount, save_node, &save_hdr);1620	xfs_trans_log_buf(tp, save_blk->bp,1621		XFS_DA_LOGRANGE(save_node, &save_node->hdr,1622				state->args->geo->node_hdr_size));1623 1624	/*1625	 * Save the last hashval in the remaining block for upward propagation.1626	 */1627	save_blk->hashval = be32_to_cpu(save_btree[save_hdr.count - 1].hashval);1628}1629 1630/*========================================================================1631 * Routines used for finding things in the Btree.1632 *========================================================================*/1633 1634/*1635 * Walk down the Btree looking for a particular filename, filling1636 * in the state structure as we go.1637 *1638 * We will set the state structure to point to each of the elements1639 * in each of the nodes where either the hashval is or should be.1640 *1641 * We support duplicate hashval's so for each entry in the current1642 * node that could contain the desired hashval, descend.  This is a1643 * pruned depth-first tree search.1644 */1645int							/* error */1646xfs_da3_node_lookup_int(1647	struct xfs_da_state	*state,1648	int			*result)1649{1650	struct xfs_da_state_blk	*blk;1651	struct xfs_da_blkinfo	*curr;1652	struct xfs_da_intnode	*node;1653	struct xfs_da_node_entry *btree;1654	struct xfs_da3_icnode_hdr nodehdr;1655	struct xfs_da_args	*args;1656	xfs_failaddr_t		fa;1657	xfs_dablk_t		blkno;1658	xfs_dahash_t		hashval;1659	xfs_dahash_t		btreehashval;1660	int			probe;1661	int			span;1662	int			max;1663	int			error;1664	int			retval;1665	unsigned int		expected_level = 0;1666	uint16_t		magic;1667	struct xfs_inode	*dp = state->args->dp;1668 1669	args = state->args;1670 1671	/*1672	 * Descend thru the B-tree searching each level for the right1673	 * node to use, until the right hashval is found.1674	 */1675	blkno = args->geo->leafblk;1676	for (blk = &state->path.blk[0], state->path.active = 1;1677			 state->path.active <= XFS_DA_NODE_MAXDEPTH;1678			 blk++, state->path.active++) {1679		/*1680		 * Read the next node down in the tree.1681		 */1682		blk->blkno = blkno;1683		error = xfs_da3_node_read(args->trans, args->dp, blkno,1684					&blk->bp, args->whichfork);1685		if (error) {1686			blk->blkno = 0;1687			state->path.active--;1688			return error;1689		}1690		curr = blk->bp->b_addr;1691		magic = be16_to_cpu(curr->magic);1692 1693		if (magic == XFS_ATTR_LEAF_MAGIC ||1694		    magic == XFS_ATTR3_LEAF_MAGIC) {1695			fa = xfs_attr3_leaf_header_check(blk->bp, args->owner);1696			if (fa) {1697				__xfs_buf_mark_corrupt(blk->bp, fa);1698				xfs_da_mark_sick(args);1699				return -EFSCORRUPTED;1700			}1701			blk->magic = XFS_ATTR_LEAF_MAGIC;1702			blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);1703			break;1704		}1705 1706		if (magic == XFS_DIR2_LEAFN_MAGIC ||1707		    magic == XFS_DIR3_LEAFN_MAGIC) {1708			fa = xfs_dir3_leaf_header_check(blk->bp, args->owner);1709			if (fa) {1710				__xfs_buf_mark_corrupt(blk->bp, fa);1711				xfs_da_mark_sick(args);1712				return -EFSCORRUPTED;1713			}1714			blk->magic = XFS_DIR2_LEAFN_MAGIC;1715			blk->hashval = xfs_dir2_leaf_lasthash(args->dp,1716							      blk->bp, NULL);1717			break;1718		}1719 1720		if (magic != XFS_DA_NODE_MAGIC && magic != XFS_DA3_NODE_MAGIC) {1721			xfs_buf_mark_corrupt(blk->bp);1722			xfs_da_mark_sick(args);1723			return -EFSCORRUPTED;1724		}1725 1726		fa = xfs_da3_node_header_check(blk->bp, args->owner);1727		if (fa) {1728			__xfs_buf_mark_corrupt(blk->bp, fa);1729			xfs_da_mark_sick(args);1730			return -EFSCORRUPTED;1731		}1732 1733		blk->magic = XFS_DA_NODE_MAGIC;1734 1735		/*1736		 * Search an intermediate node for a match.1737		 */1738		node = blk->bp->b_addr;1739		xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);1740		btree = nodehdr.btree;1741 1742		/* Tree taller than we can handle; bail out! */1743		if (nodehdr.level >= XFS_DA_NODE_MAXDEPTH) {1744			xfs_buf_mark_corrupt(blk->bp);1745			xfs_da_mark_sick(args);1746			return -EFSCORRUPTED;1747		}1748 1749		/* Check the level from the root. */1750		if (blkno == args->geo->leafblk)1751			expected_level = nodehdr.level - 1;1752		else if (expected_level != nodehdr.level) {1753			xfs_buf_mark_corrupt(blk->bp);1754			xfs_da_mark_sick(args);1755			return -EFSCORRUPTED;1756		} else1757			expected_level--;1758 1759		max = nodehdr.count;1760		blk->hashval = be32_to_cpu(btree[max - 1].hashval);1761 1762		/*1763		 * Binary search.  (note: small blocks will skip loop)1764		 */1765		probe = span = max / 2;1766		hashval = args->hashval;1767		while (span > 4) {1768			span /= 2;1769			btreehashval = be32_to_cpu(btree[probe].hashval);1770			if (btreehashval < hashval)1771				probe += span;1772			else if (btreehashval > hashval)1773				probe -= span;1774			else1775				break;1776		}1777		ASSERT((probe >= 0) && (probe < max));1778		ASSERT((span <= 4) ||1779			(be32_to_cpu(btree[probe].hashval) == hashval));1780 1781		/*1782		 * Since we may have duplicate hashval's, find the first1783		 * matching hashval in the node.1784		 */1785		while (probe > 0 &&1786		       be32_to_cpu(btree[probe].hashval) >= hashval) {1787			probe--;1788		}1789		while (probe < max &&1790		       be32_to_cpu(btree[probe].hashval) < hashval) {1791			probe++;1792		}1793 1794		/*1795		 * Pick the right block to descend on.1796		 */1797		if (probe == max) {1798			blk->index = max - 1;1799			blkno = be32_to_cpu(btree[max - 1].before);1800		} else {1801			blk->index = probe;1802			blkno = be32_to_cpu(btree[probe].before);1803		}1804 1805		/* We can't point back to the root. */1806		if (XFS_IS_CORRUPT(dp->i_mount, blkno == args->geo->leafblk)) {1807			xfs_da_mark_sick(args);1808			return -EFSCORRUPTED;1809		}1810	}1811 1812	if (XFS_IS_CORRUPT(dp->i_mount, expected_level != 0)) {1813		xfs_da_mark_sick(args);1814		return -EFSCORRUPTED;1815	}1816 1817	/*1818	 * A leaf block that ends in the hashval that we are interested in1819	 * (final hashval == search hashval) means that the next block may1820	 * contain more entries with the same hashval, shift upward to the1821	 * next leaf and keep searching.1822	 */1823	for (;;) {1824		if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {1825			retval = xfs_dir2_leafn_lookup_int(blk->bp, args,1826							&blk->index, state);1827		} else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {1828			retval = xfs_attr3_leaf_lookup_int(blk->bp, args);1829			blk->index = args->index;1830			args->blkno = blk->blkno;1831		} else {1832			ASSERT(0);1833			xfs_da_mark_sick(args);1834			return -EFSCORRUPTED;1835		}1836		if (((retval == -ENOENT) || (retval == -ENOATTR)) &&1837		    (blk->hashval == args->hashval)) {1838			error = xfs_da3_path_shift(state, &state->path, 1, 1,1839							 &retval);1840			if (error)1841				return error;1842			if (retval == 0) {1843				continue;1844			} else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {1845				/* path_shift() gives ENOENT */1846				retval = -ENOATTR;1847			}1848		}1849		break;1850	}1851	*result = retval;1852	return 0;1853}1854 1855/*========================================================================1856 * Utility routines.1857 *========================================================================*/1858 1859/*1860 * Compare two intermediate nodes for "order".1861 */1862STATIC int1863xfs_da3_node_order(1864	struct xfs_inode *dp,1865	struct xfs_buf	*node1_bp,1866	struct xfs_buf	*node2_bp)1867{1868	struct xfs_da_intnode	*node1;1869	struct xfs_da_intnode	*node2;1870	struct xfs_da_node_entry *btree1;1871	struct xfs_da_node_entry *btree2;1872	struct xfs_da3_icnode_hdr node1hdr;1873	struct xfs_da3_icnode_hdr node2hdr;1874 1875	node1 = node1_bp->b_addr;1876	node2 = node2_bp->b_addr;1877	xfs_da3_node_hdr_from_disk(dp->i_mount, &node1hdr, node1);1878	xfs_da3_node_hdr_from_disk(dp->i_mount, &node2hdr, node2);1879	btree1 = node1hdr.btree;1880	btree2 = node2hdr.btree;1881 1882	if (node1hdr.count > 0 && node2hdr.count > 0 &&1883	    ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||1884	     (be32_to_cpu(btree2[node2hdr.count - 1].hashval) <1885	      be32_to_cpu(btree1[node1hdr.count - 1].hashval)))) {1886		return 1;1887	}1888	return 0;1889}1890 1891/*1892 * Link a new block into a doubly linked list of blocks (of whatever type).1893 */1894int							/* error */1895xfs_da3_blk_link(1896	struct xfs_da_state	*state,1897	struct xfs_da_state_blk	*old_blk,1898	struct xfs_da_state_blk	*new_blk)1899{1900	struct xfs_da_blkinfo	*old_info;1901	struct xfs_da_blkinfo	*new_info;1902	struct xfs_da_blkinfo	*tmp_info;1903	struct xfs_da_args	*args;1904	struct xfs_buf		*bp;1905	xfs_failaddr_t		fa;1906	int			before = 0;1907	int			error;1908	struct xfs_inode	*dp = state->args->dp;1909 1910	/*1911	 * Set up environment.1912	 */1913	args = state->args;1914	ASSERT(args != NULL);1915	old_info = old_blk->bp->b_addr;1916	new_info = new_blk->bp->b_addr;1917	ASSERT(old_blk->magic == XFS_DA_NODE_MAGIC ||1918	       old_blk->magic == XFS_DIR2_LEAFN_MAGIC ||1919	       old_blk->magic == XFS_ATTR_LEAF_MAGIC);1920 1921	switch (old_blk->magic) {1922	case XFS_ATTR_LEAF_MAGIC:1923		before = xfs_attr_leaf_order(old_blk->bp, new_blk->bp);1924		break;1925	case XFS_DIR2_LEAFN_MAGIC:1926		before = xfs_dir2_leafn_order(dp, old_blk->bp, new_blk->bp);1927		break;1928	case XFS_DA_NODE_MAGIC:1929		before = xfs_da3_node_order(dp, old_blk->bp, new_blk->bp);1930		break;1931	}1932 1933	/*1934	 * Link blocks in appropriate order.1935	 */1936	if (before) {1937		/*1938		 * Link new block in before existing block.1939		 */1940		trace_xfs_da_link_before(args);1941		new_info->forw = cpu_to_be32(old_blk->blkno);1942		new_info->back = old_info->back;1943		if (old_info->back) {1944			error = xfs_da3_node_read(args->trans, dp,1945						be32_to_cpu(old_info->back),1946						&bp, args->whichfork);1947			if (error)1948				return error;1949			fa = xfs_da3_header_check(bp, args->owner);1950			if (fa) {1951				__xfs_buf_mark_corrupt(bp, fa);1952				xfs_trans_brelse(args->trans, bp);1953				xfs_da_mark_sick(args);1954				return -EFSCORRUPTED;1955			}1956			ASSERT(bp != NULL);1957			tmp_info = bp->b_addr;1958			ASSERT(tmp_info->magic == old_info->magic);1959			ASSERT(be32_to_cpu(tmp_info->forw) == old_blk->blkno);1960			tmp_info->forw = cpu_to_be32(new_blk->blkno);1961			xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);1962		}1963		old_info->back = cpu_to_be32(new_blk->blkno);1964	} else {1965		/*1966		 * Link new block in after existing block.1967		 */1968		trace_xfs_da_link_after(args);1969		new_info->forw = old_info->forw;1970		new_info->back = cpu_to_be32(old_blk->blkno);1971		if (old_info->forw) {1972			error = xfs_da3_node_read(args->trans, dp,1973						be32_to_cpu(old_info->forw),1974						&bp, args->whichfork);1975			if (error)1976				return error;1977			fa = xfs_da3_header_check(bp, args->owner);1978			if (fa) {1979				__xfs_buf_mark_corrupt(bp, fa);1980				xfs_trans_brelse(args->trans, bp);1981				xfs_da_mark_sick(args);1982				return -EFSCORRUPTED;1983			}1984			ASSERT(bp != NULL);1985			tmp_info = bp->b_addr;1986			ASSERT(tmp_info->magic == old_info->magic);1987			ASSERT(be32_to_cpu(tmp_info->back) == old_blk->blkno);1988			tmp_info->back = cpu_to_be32(new_blk->blkno);1989			xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);1990		}1991		old_info->forw = cpu_to_be32(new_blk->blkno);1992	}1993 1994	xfs_trans_log_buf(args->trans, old_blk->bp, 0, sizeof(*tmp_info) - 1);1995	xfs_trans_log_buf(args->trans, new_blk->bp, 0, sizeof(*tmp_info) - 1);1996	return 0;1997}1998 1999/*2000 * Unlink a block from a doubly linked list of blocks.2001 */2002STATIC int						/* error */2003xfs_da3_blk_unlink(2004	struct xfs_da_state	*state,2005	struct xfs_da_state_blk	*drop_blk,2006	struct xfs_da_state_blk	*save_blk)2007{2008	struct xfs_da_blkinfo	*drop_info;2009	struct xfs_da_blkinfo	*save_info;2010	struct xfs_da_blkinfo	*tmp_info;2011	struct xfs_da_args	*args;2012	struct xfs_buf		*bp;2013	xfs_failaddr_t		fa;2014	int			error;2015 2016	/*2017	 * Set up environment.2018	 */2019	args = state->args;2020	ASSERT(args != NULL);2021	save_info = save_blk->bp->b_addr;2022	drop_info = drop_blk->bp->b_addr;2023	ASSERT(save_blk->magic == XFS_DA_NODE_MAGIC ||2024	       save_blk->magic == XFS_DIR2_LEAFN_MAGIC ||2025	       save_blk->magic == XFS_ATTR_LEAF_MAGIC);2026	ASSERT(save_blk->magic == drop_blk->magic);2027	ASSERT((be32_to_cpu(save_info->forw) == drop_blk->blkno) ||2028	       (be32_to_cpu(save_info->back) == drop_blk->blkno));2029	ASSERT((be32_to_cpu(drop_info->forw) == save_blk->blkno) ||2030	       (be32_to_cpu(drop_info->back) == save_blk->blkno));2031 2032	/*2033	 * Unlink the leaf block from the doubly linked chain of leaves.2034	 */2035	if (be32_to_cpu(save_info->back) == drop_blk->blkno) {2036		trace_xfs_da_unlink_back(args);2037		save_info->back = drop_info->back;2038		if (drop_info->back) {2039			error = xfs_da3_node_read(args->trans, args->dp,2040						be32_to_cpu(drop_info->back),2041						&bp, args->whichfork);2042			if (error)2043				return error;2044			fa = xfs_da3_header_check(bp, args->owner);2045			if (fa) {2046				__xfs_buf_mark_corrupt(bp, fa);2047				xfs_trans_brelse(args->trans, bp);2048				xfs_da_mark_sick(args);2049				return -EFSCORRUPTED;2050			}2051			ASSERT(bp != NULL);2052			tmp_info = bp->b_addr;2053			ASSERT(tmp_info->magic == save_info->magic);2054			ASSERT(be32_to_cpu(tmp_info->forw) == drop_blk->blkno);2055			tmp_info->forw = cpu_to_be32(save_blk->blkno);2056			xfs_trans_log_buf(args->trans, bp, 0,2057						    sizeof(*tmp_info) - 1);2058		}2059	} else {2060		trace_xfs_da_unlink_forward(args);2061		save_info->forw = drop_info->forw;2062		if (drop_info->forw) {2063			error = xfs_da3_node_read(args->trans, args->dp,2064						be32_to_cpu(drop_info->forw),2065						&bp, args->whichfork);2066			if (error)2067				return error;2068			fa = xfs_da3_header_check(bp, args->owner);2069			if (fa) {2070				__xfs_buf_mark_corrupt(bp, fa);2071				xfs_trans_brelse(args->trans, bp);2072				xfs_da_mark_sick(args);2073				return -EFSCORRUPTED;2074			}2075			ASSERT(bp != NULL);2076			tmp_info = bp->b_addr;2077			ASSERT(tmp_info->magic == save_info->magic);2078			ASSERT(be32_to_cpu(tmp_info->back) == drop_blk->blkno);2079			tmp_info->back = cpu_to_be32(save_blk->blkno);2080			xfs_trans_log_buf(args->trans, bp, 0,2081						    sizeof(*tmp_info) - 1);2082		}2083	}2084 2085	xfs_trans_log_buf(args->trans, save_blk->bp, 0, sizeof(*save_info) - 1);2086	return 0;2087}2088 2089/*2090 * Move a path "forward" or "!forward" one block at the current level.2091 *2092 * This routine will adjust a "path" to point to the next block2093 * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the2094 * Btree, including updating pointers to the intermediate nodes between2095 * the new bottom and the root.2096 */2097int							/* error */2098xfs_da3_path_shift(2099	struct xfs_da_state	*state,2100	struct xfs_da_state_path *path,2101	int			forward,2102	int			release,2103	int			*result)2104{2105	struct xfs_da_state_blk	*blk;2106	struct xfs_da_blkinfo	*info;2107	struct xfs_da_args	*args;2108	struct xfs_da_node_entry *btree;2109	struct xfs_da3_icnode_hdr nodehdr;2110	struct xfs_buf		*bp;2111	xfs_failaddr_t		fa;2112	xfs_dablk_t		blkno = 0;2113	int			level;2114	int			error;2115	struct xfs_inode	*dp = state->args->dp;2116 2117	trace_xfs_da_path_shift(state->args);2118 2119	/*2120	 * Roll up the Btree looking for the first block where our2121	 * current index is not at the edge of the block.  Note that2122	 * we skip the bottom layer because we want the sibling block.2123	 */2124	args = state->args;2125	ASSERT(args != NULL);2126	ASSERT(path != NULL);2127	ASSERT((path->active > 0) && (path->active < XFS_DA_NODE_MAXDEPTH));2128	level = (path->active-1) - 1;	/* skip bottom layer in path */2129	for (; level >= 0; level--) {2130		blk = &path->blk[level];2131		xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr,2132					   blk->bp->b_addr);2133 2134		if (forward && (blk->index < nodehdr.count - 1)) {2135			blk->index++;2136			blkno = be32_to_cpu(nodehdr.btree[blk->index].before);2137			break;2138		} else if (!forward && (blk->index > 0)) {2139			blk->index--;2140			blkno = be32_to_cpu(nodehdr.btree[blk->index].before);2141			break;2142		}2143	}2144	if (level < 0) {2145		*result = -ENOENT;	/* we're out of our tree */2146		ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);2147		return 0;2148	}2149 2150	/*2151	 * Roll down the edge of the subtree until we reach the2152	 * same depth we were at originally.2153	 */2154	for (blk++, level++; level < path->active; blk++, level++) {2155		/*2156		 * Read the next child block into a local buffer.2157		 */2158		error = xfs_da3_node_read(args->trans, dp, blkno, &bp,2159					  args->whichfork);2160		if (error)2161			return error;2162 2163		/*2164		 * Release the old block (if it's dirty, the trans doesn't2165		 * actually let go) and swap the local buffer into the path2166		 * structure. This ensures failure of the above read doesn't set2167		 * a NULL buffer in an active slot in the path.2168		 */2169		if (release)2170			xfs_trans_brelse(args->trans, blk->bp);2171		blk->blkno = blkno;2172		blk->bp = bp;2173 2174		info = blk->bp->b_addr;2175		ASSERT(info->magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||2176		       info->magic == cpu_to_be16(XFS_DA3_NODE_MAGIC) ||2177		       info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||2178		       info->magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||2179		       info->magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||2180		       info->magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));2181 2182 2183		/*2184		 * Note: we flatten the magic number to a single type so we2185		 * don't have to compare against crc/non-crc types elsewhere.2186		 */2187		switch (be16_to_cpu(info->magic)) {2188		case XFS_DA_NODE_MAGIC:2189		case XFS_DA3_NODE_MAGIC:2190			fa = xfs_da3_node_header_check(blk->bp, args->owner);2191			if (fa) {2192				__xfs_buf_mark_corrupt(blk->bp, fa);2193				xfs_da_mark_sick(args);2194				return -EFSCORRUPTED;2195			}2196			blk->magic = XFS_DA_NODE_MAGIC;2197			xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr,2198						   bp->b_addr);2199			btree = nodehdr.btree;2200			blk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);2201			if (forward)2202				blk->index = 0;2203			else2204				blk->index = nodehdr.count - 1;2205			blkno = be32_to_cpu(btree[blk->index].before);2206			break;2207		case XFS_ATTR_LEAF_MAGIC:2208		case XFS_ATTR3_LEAF_MAGIC:2209			fa = xfs_attr3_leaf_header_check(blk->bp, args->owner);2210			if (fa) {2211				__xfs_buf_mark_corrupt(blk->bp, fa);2212				xfs_da_mark_sick(args);2213				return -EFSCORRUPTED;2214			}2215			blk->magic = XFS_ATTR_LEAF_MAGIC;2216			ASSERT(level == path->active-1);2217			blk->index = 0;2218			blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);2219			break;2220		case XFS_DIR2_LEAFN_MAGIC:2221		case XFS_DIR3_LEAFN_MAGIC:2222			fa = xfs_dir3_leaf_header_check(blk->bp, args->owner);2223			if (fa) {2224				__xfs_buf_mark_corrupt(blk->bp, fa);2225				xfs_da_mark_sick(args);2226				return -EFSCORRUPTED;2227			}2228			blk->magic = XFS_DIR2_LEAFN_MAGIC;2229			ASSERT(level == path->active-1);2230			blk->index = 0;2231			blk->hashval = xfs_dir2_leaf_lasthash(args->dp,2232							      blk->bp, NULL);2233			break;2234		default:2235			ASSERT(0);2236			break;2237		}2238	}2239	*result = 0;2240	return 0;2241}2242 2243 2244/*========================================================================2245 * Utility routines.2246 *========================================================================*/2247 2248/*2249 * Implement a simple hash on a character string.2250 * Rotate the hash value by 7 bits, then XOR each character in.2251 * This is implemented with some source-level loop unrolling.2252 */2253xfs_dahash_t2254xfs_da_hashname(const uint8_t *name, int namelen)2255{2256	xfs_dahash_t hash;2257 2258	/*2259	 * Do four characters at a time as long as we can.2260	 */2261	for (hash = 0; namelen >= 4; namelen -= 4, name += 4)2262		hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^2263		       (name[3] << 0) ^ rol32(hash, 7 * 4);2264 2265	/*2266	 * Now do the rest of the characters.2267	 */2268	switch (namelen) {2269	case 3:2270		return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^2271		       rol32(hash, 7 * 3);2272	case 2:2273		return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);2274	case 1:2275		return (name[0] << 0) ^ rol32(hash, 7 * 1);2276	default: /* case 0: */2277		return hash;2278	}2279}2280 2281enum xfs_dacmp2282xfs_da_compname(2283	struct xfs_da_args *args,2284	const unsigned char *name,2285	int		len)2286{2287	return (args->namelen == len && memcmp(args->name, name, len) == 0) ?2288					XFS_CMP_EXACT : XFS_CMP_DIFFERENT;2289}2290 2291int2292xfs_da_grow_inode_int(2293	struct xfs_da_args	*args,2294	xfs_fileoff_t		*bno,2295	int			count)2296{2297	struct xfs_trans	*tp = args->trans;2298	struct xfs_inode	*dp = args->dp;2299	int			w = args->whichfork;2300	xfs_rfsblock_t		nblks = dp->i_nblocks;2301	struct xfs_bmbt_irec	map, *mapp = &map;2302	int			nmap, error, got, i, mapi = 1;2303 2304	/*2305	 * Find a spot in the file space to put the new block.2306	 */2307	error = xfs_bmap_first_unused(tp, dp, count, bno, w);2308	if (error)2309		return error;2310 2311	/*2312	 * Try mapping it in one filesystem block.2313	 */2314	nmap = 1;2315	error = xfs_bmapi_write(tp, dp, *bno, count,2316			xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA|XFS_BMAPI_CONTIG,2317			args->total, &map, &nmap);2318	if (error == -ENOSPC && count > 1) {2319		xfs_fileoff_t		b;2320		int			c;2321 2322		/*2323		 * If we didn't get it and the block might work if fragmented,2324		 * try without the CONTIG flag.  Loop until we get it all.2325		 */2326		mapp = kmalloc(sizeof(*mapp) * count,2327				GFP_KERNEL | __GFP_NOFAIL);2328		for (b = *bno, mapi = 0; b < *bno + count; ) {2329			c = (int)(*bno + count - b);2330			nmap = min(XFS_BMAP_MAX_NMAP, c);2331			error = xfs_bmapi_write(tp, dp, b, c,2332					xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,2333					args->total, &mapp[mapi], &nmap);2334			if (error)2335				goto out_free_map;2336			mapi += nmap;2337			b = mapp[mapi - 1].br_startoff +2338			    mapp[mapi - 1].br_blockcount;2339		}2340	}2341	if (error)2342		goto out_free_map;2343 2344	/*2345	 * Count the blocks we got, make sure it matches the total.2346	 */2347	for (i = 0, got = 0; i < mapi; i++)2348		got += mapp[i].br_blockcount;2349	if (got != count || mapp[0].br_startoff != *bno ||2350	    mapp[mapi - 1].br_startoff + mapp[mapi - 1].br_blockcount !=2351	    *bno + count) {2352		error = -ENOSPC;2353		goto out_free_map;2354	}2355 2356	/* account for newly allocated blocks in reserved blocks total */2357	args->total -= dp->i_nblocks - nblks;2358 2359out_free_map:2360	if (mapp != &map)2361		kfree(mapp);2362	return error;2363}2364 2365/*2366 * Add a block to the btree ahead of the file.2367 * Return the new block number to the caller.2368 */2369int2370xfs_da_grow_inode(2371	struct xfs_da_args	*args,2372	xfs_dablk_t		*new_blkno)2373{2374	xfs_fileoff_t		bno;2375	int			error;2376 2377	trace_xfs_da_grow_inode(args);2378 2379	bno = args->geo->leafblk;2380	error = xfs_da_grow_inode_int(args, &bno, args->geo->fsbcount);2381	if (!error)2382		*new_blkno = (xfs_dablk_t)bno;2383	return error;2384}2385 2386/*2387 * Ick.  We need to always be able to remove a btree block, even2388 * if there's no space reservation because the filesystem is full.2389 * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.2390 * It swaps the target block with the last block in the file.  The2391 * last block in the file can always be removed since it can't cause2392 * a bmap btree split to do that.2393 */2394STATIC int2395xfs_da3_swap_lastblock(2396	struct xfs_da_args	*args,2397	xfs_dablk_t		*dead_blknop,2398	struct xfs_buf		**dead_bufp)2399{2400	struct xfs_da_blkinfo	*dead_info;2401	struct xfs_da_blkinfo	*sib_info;2402	struct xfs_da_intnode	*par_node;2403	struct xfs_da_intnode	*dead_node;2404	struct xfs_dir2_leaf	*dead_leaf2;2405	struct xfs_da_node_entry *btree;2406	struct xfs_da3_icnode_hdr par_hdr;2407	struct xfs_inode	*dp;2408	struct xfs_trans	*tp;2409	struct xfs_mount	*mp;2410	struct xfs_buf		*dead_buf;2411	struct xfs_buf		*last_buf;2412	struct xfs_buf		*sib_buf;2413	struct xfs_buf		*par_buf;2414	xfs_failaddr_t		fa;2415	xfs_dahash_t		dead_hash;2416	xfs_fileoff_t		lastoff;2417	xfs_dablk_t		dead_blkno;2418	xfs_dablk_t		last_blkno;2419	xfs_dablk_t		sib_blkno;2420	xfs_dablk_t		par_blkno;2421	int			error;2422	int			w;2423	int			entno;2424	int			level;2425	int			dead_level;2426 2427	trace_xfs_da_swap_lastblock(args);2428 2429	dead_buf = *dead_bufp;2430	dead_blkno = *dead_blknop;2431	tp = args->trans;2432	dp = args->dp;2433	w = args->whichfork;2434	ASSERT(w == XFS_DATA_FORK);2435	mp = dp->i_mount;2436	lastoff = args->geo->freeblk;2437	error = xfs_bmap_last_before(tp, dp, &lastoff, w);2438	if (error)2439		return error;2440	if (XFS_IS_CORRUPT(mp, lastoff == 0)) {2441		xfs_da_mark_sick(args);2442		return -EFSCORRUPTED;2443	}2444	/*2445	 * Read the last block in the btree space.2446	 */2447	last_blkno = (xfs_dablk_t)lastoff - args->geo->fsbcount;2448	error = xfs_da3_node_read(tp, dp, last_blkno, &last_buf, w);2449	if (error)2450		return error;2451	fa = xfs_da3_header_check(last_buf, args->owner);2452	if (fa) {2453		__xfs_buf_mark_corrupt(last_buf, fa);2454		xfs_trans_brelse(tp, last_buf);2455		xfs_da_mark_sick(args);2456		return -EFSCORRUPTED;2457	}2458 2459	/*2460	 * Copy the last block into the dead buffer and log it.2461	 */2462	xfs_da_buf_copy(dead_buf, last_buf, args->geo->blksize);2463	xfs_trans_log_buf(tp, dead_buf, 0, args->geo->blksize - 1);2464	dead_info = dead_buf->b_addr;2465 2466	/*2467	 * Get values from the moved block.2468	 */2469	if (dead_info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||2470	    dead_info->magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {2471		struct xfs_dir3_icleaf_hdr leafhdr;2472		struct xfs_dir2_leaf_entry *ents;2473 2474		dead_leaf2 = (xfs_dir2_leaf_t *)dead_info;2475		xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr,2476					    dead_leaf2);2477		ents = leafhdr.ents;2478		dead_level = 0;2479		dead_hash = be32_to_cpu(ents[leafhdr.count - 1].hashval);2480	} else {2481		struct xfs_da3_icnode_hdr deadhdr;2482 2483		dead_node = (xfs_da_intnode_t *)dead_info;2484		xfs_da3_node_hdr_from_disk(dp->i_mount, &deadhdr, dead_node);2485		btree = deadhdr.btree;2486		dead_level = deadhdr.level;2487		dead_hash = be32_to_cpu(btree[deadhdr.count - 1].hashval);2488	}2489	sib_buf = par_buf = NULL;2490	/*2491	 * If the moved block has a left sibling, fix up the pointers.2492	 */2493	if ((sib_blkno = be32_to_cpu(dead_info->back))) {2494		error = xfs_da3_node_read(tp, dp, sib_blkno, &sib_buf, w);2495		if (error)2496			goto done;2497		fa = xfs_da3_header_check(sib_buf, args->owner);2498		if (fa) {2499			__xfs_buf_mark_corrupt(sib_buf, fa);2500			xfs_da_mark_sick(args);2501			error = -EFSCORRUPTED;2502			goto done;2503		}2504		sib_info = sib_buf->b_addr;2505		if (XFS_IS_CORRUPT(mp,2506				   be32_to_cpu(sib_info->forw) != last_blkno ||2507				   sib_info->magic != dead_info->magic)) {2508			xfs_da_mark_sick(args);2509			error = -EFSCORRUPTED;2510			goto done;2511		}2512		sib_info->forw = cpu_to_be32(dead_blkno);2513		xfs_trans_log_buf(tp, sib_buf,2514			XFS_DA_LOGRANGE(sib_info, &sib_info->forw,2515					sizeof(sib_info->forw)));2516		sib_buf = NULL;2517	}2518	/*2519	 * If the moved block has a right sibling, fix up the pointers.2520	 */2521	if ((sib_blkno = be32_to_cpu(dead_info->forw))) {2522		error = xfs_da3_node_read(tp, dp, sib_blkno, &sib_buf, w);2523		if (error)2524			goto done;2525		fa = xfs_da3_header_check(sib_buf, args->owner);2526		if (fa) {2527			__xfs_buf_mark_corrupt(sib_buf, fa);2528			xfs_da_mark_sick(args);2529			error = -EFSCORRUPTED;2530			goto done;2531		}2532		sib_info = sib_buf->b_addr;2533		if (XFS_IS_CORRUPT(mp,2534				   be32_to_cpu(sib_info->back) != last_blkno ||2535				   sib_info->magic != dead_info->magic)) {2536			xfs_da_mark_sick(args);2537			error = -EFSCORRUPTED;2538			goto done;2539		}2540		sib_info->back = cpu_to_be32(dead_blkno);2541		xfs_trans_log_buf(tp, sib_buf,2542			XFS_DA_LOGRANGE(sib_info, &sib_info->back,2543					sizeof(sib_info->back)));2544		sib_buf = NULL;2545	}2546	par_blkno = args->geo->leafblk;2547	level = -1;2548	/*2549	 * Walk down the tree looking for the parent of the moved block.2550	 */2551	for (;;) {2552		error = xfs_da3_node_read(tp, dp, par_blkno, &par_buf, w);2553		if (error)2554			goto done;2555		fa = xfs_da3_node_header_check(par_buf, args->owner);2556		if (fa) {2557			__xfs_buf_mark_corrupt(par_buf, fa);2558			xfs_da_mark_sick(args);2559			error = -EFSCORRUPTED;2560			goto done;2561		}2562		par_node = par_buf->b_addr;2563		xfs_da3_node_hdr_from_disk(dp->i_mount, &par_hdr, par_node);2564		if (XFS_IS_CORRUPT(mp,2565				   level >= 0 && level != par_hdr.level + 1)) {2566			xfs_da_mark_sick(args);2567			error = -EFSCORRUPTED;2568			goto done;2569		}2570		level = par_hdr.level;2571		btree = par_hdr.btree;2572		for (entno = 0;2573		     entno < par_hdr.count &&2574		     be32_to_cpu(btree[entno].hashval) < dead_hash;2575		     entno++)2576			continue;2577		if (XFS_IS_CORRUPT(mp, entno == par_hdr.count)) {2578			xfs_da_mark_sick(args);2579			error = -EFSCORRUPTED;2580			goto done;2581		}2582		par_blkno = be32_to_cpu(btree[entno].before);2583		if (level == dead_level + 1)2584			break;2585		xfs_trans_brelse(tp, par_buf);2586		par_buf = NULL;2587	}2588	/*2589	 * We're in the right parent block.2590	 * Look for the right entry.2591	 */2592	for (;;) {2593		for (;2594		     entno < par_hdr.count &&2595		     be32_to_cpu(btree[entno].before) != last_blkno;2596		     entno++)2597			continue;2598		if (entno < par_hdr.count)2599			break;2600		par_blkno = par_hdr.forw;2601		xfs_trans_brelse(tp, par_buf);2602		par_buf = NULL;2603		if (XFS_IS_CORRUPT(mp, par_blkno == 0)) {2604			xfs_da_mark_sick(args);2605			error = -EFSCORRUPTED;2606			goto done;2607		}2608		error = xfs_da3_node_read(tp, dp, par_blkno, &par_buf, w);2609		if (error)2610			goto done;2611		fa = xfs_da3_node_header_check(par_buf, args->owner);2612		if (fa) {2613			__xfs_buf_mark_corrupt(par_buf, fa);2614			xfs_da_mark_sick(args);2615			error = -EFSCORRUPTED;2616			goto done;2617		}2618		par_node = par_buf->b_addr;2619		xfs_da3_node_hdr_from_disk(dp->i_mount, &par_hdr, par_node);2620		if (XFS_IS_CORRUPT(mp, par_hdr.level != level)) {2621			xfs_da_mark_sick(args);2622			error = -EFSCORRUPTED;2623			goto done;2624		}2625		btree = par_hdr.btree;2626		entno = 0;2627	}2628	/*2629	 * Update the parent entry pointing to the moved block.2630	 */2631	btree[entno].before = cpu_to_be32(dead_blkno);2632	xfs_trans_log_buf(tp, par_buf,2633		XFS_DA_LOGRANGE(par_node, &btree[entno].before,2634				sizeof(btree[entno].before)));2635	*dead_blknop = last_blkno;2636	*dead_bufp = last_buf;2637	return 0;2638done:2639	if (par_buf)2640		xfs_trans_brelse(tp, par_buf);2641	if (sib_buf)2642		xfs_trans_brelse(tp, sib_buf);2643	xfs_trans_brelse(tp, last_buf);2644	return error;2645}2646 2647/*2648 * Remove a btree block from a directory or attribute.2649 */2650int2651xfs_da_shrink_inode(2652	struct xfs_da_args	*args,2653	xfs_dablk_t		dead_blkno,2654	struct xfs_buf		*dead_buf)2655{2656	struct xfs_inode	*dp;2657	int			done, error, w, count;2658	struct xfs_trans	*tp;2659 2660	trace_xfs_da_shrink_inode(args);2661 2662	dp = args->dp;2663	w = args->whichfork;2664	tp = args->trans;2665	count = args->geo->fsbcount;2666	for (;;) {2667		/*2668		 * Remove extents.  If we get ENOSPC for a dir we have to move2669		 * the last block to the place we want to kill.2670		 */2671		error = xfs_bunmapi(tp, dp, dead_blkno, count,2672				    xfs_bmapi_aflag(w), 0, &done);2673		if (error == -ENOSPC) {2674			if (w != XFS_DATA_FORK)2675				break;2676			error = xfs_da3_swap_lastblock(args, &dead_blkno,2677						      &dead_buf);2678			if (error)2679				break;2680		} else {2681			break;2682		}2683	}2684	xfs_trans_binval(tp, dead_buf);2685	return error;2686}2687 2688static int2689xfs_dabuf_map(2690	struct xfs_inode	*dp,2691	xfs_dablk_t		bno,2692	unsigned int		flags,2693	int			whichfork,2694	struct xfs_buf_map	**mapp,2695	int			*nmaps)2696{2697	struct xfs_mount	*mp = dp->i_mount;2698	int			nfsb = xfs_dabuf_nfsb(mp, whichfork);2699	struct xfs_bmbt_irec	irec, *irecs = &irec;2700	struct xfs_buf_map	*map = *mapp;2701	xfs_fileoff_t		off = bno;2702	int			error = 0, nirecs, i;2703 2704	if (nfsb > 1)2705		irecs = kzalloc(sizeof(irec) * nfsb,2706				GFP_KERNEL | __GFP_NOLOCKDEP | __GFP_NOFAIL);2707 2708	nirecs = nfsb;2709	error = xfs_bmapi_read(dp, bno, nfsb, irecs, &nirecs,2710			xfs_bmapi_aflag(whichfork));2711	if (error)2712		goto out_free_irecs;2713 2714	/*2715	 * Use the caller provided map for the single map case, else allocate a2716	 * larger one that needs to be free by the caller.2717	 */2718	if (nirecs > 1) {2719		map = kzalloc(nirecs * sizeof(struct xfs_buf_map),2720				GFP_KERNEL | __GFP_NOLOCKDEP | __GFP_NOFAIL);2721		if (!map) {2722			error = -ENOMEM;2723			goto out_free_irecs;2724		}2725		*mapp = map;2726	}2727 2728	for (i = 0; i < nirecs; i++) {2729		if (irecs[i].br_startblock == HOLESTARTBLOCK ||2730		    irecs[i].br_startblock == DELAYSTARTBLOCK)2731			goto invalid_mapping;2732		if (off != irecs[i].br_startoff)2733			goto invalid_mapping;2734 2735		map[i].bm_bn = XFS_FSB_TO_DADDR(mp, irecs[i].br_startblock);2736		map[i].bm_len = XFS_FSB_TO_BB(mp, irecs[i].br_blockcount);2737		off += irecs[i].br_blockcount;2738	}2739 2740	if (off != bno + nfsb)2741		goto invalid_mapping;2742 2743	*nmaps = nirecs;2744out_free_irecs:2745	if (irecs != &irec)2746		kfree(irecs);2747	return error;2748 2749invalid_mapping:2750	/* Caller ok with no mapping. */2751	if (XFS_IS_CORRUPT(mp, !(flags & XFS_DABUF_MAP_HOLE_OK))) {2752		xfs_dirattr_mark_sick(dp, whichfork);2753		error = -EFSCORRUPTED;2754		if (xfs_error_level >= XFS_ERRLEVEL_LOW) {2755			xfs_alert(mp, "%s: bno %u inode %llu",2756					__func__, bno, dp->i_ino);2757 2758			for (i = 0; i < nirecs; i++) {2759				xfs_alert(mp,2760"[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d",2761					i, irecs[i].br_startoff,2762					irecs[i].br_startblock,2763					irecs[i].br_blockcount,2764					irecs[i].br_state);2765			}2766		}2767	} else {2768		*nmaps = 0;2769	}2770	goto out_free_irecs;2771}2772 2773/*2774 * Get a buffer for the dir/attr block.2775 */2776int2777xfs_da_get_buf(2778	struct xfs_trans	*tp,2779	struct xfs_inode	*dp,2780	xfs_dablk_t		bno,2781	struct xfs_buf		**bpp,2782	int			whichfork)2783{2784	struct xfs_mount	*mp = dp->i_mount;2785	struct xfs_buf		*bp;2786	struct xfs_buf_map	map, *mapp = &map;2787	int			nmap = 1;2788	int			error;2789 2790	*bpp = NULL;2791	error = xfs_dabuf_map(dp, bno, 0, whichfork, &mapp, &nmap);2792	if (error || nmap == 0)2793		goto out_free;2794 2795	error = xfs_trans_get_buf_map(tp, mp->m_ddev_targp, mapp, nmap, 0, &bp);2796	if (error)2797		goto out_free;2798 2799	*bpp = bp;2800 2801out_free:2802	if (mapp != &map)2803		kfree(mapp);2804 2805	return error;2806}2807 2808/*2809 * Get a buffer for the dir/attr block, fill in the contents.2810 */2811int2812xfs_da_read_buf(2813	struct xfs_trans	*tp,2814	struct xfs_inode	*dp,2815	xfs_dablk_t		bno,2816	unsigned int		flags,2817	struct xfs_buf		**bpp,2818	int			whichfork,2819	const struct xfs_buf_ops *ops)2820{2821	struct xfs_mount	*mp = dp->i_mount;2822	struct xfs_buf		*bp;2823	struct xfs_buf_map	map, *mapp = &map;2824	int			nmap = 1;2825	int			error;2826 2827	*bpp = NULL;2828	error = xfs_dabuf_map(dp, bno, flags, whichfork, &mapp, &nmap);2829	if (error || !nmap)2830		goto out_free;2831 2832	error = xfs_trans_read_buf_map(mp, tp, mp->m_ddev_targp, mapp, nmap, 0,2833			&bp, ops);2834	if (xfs_metadata_is_sick(error))2835		xfs_dirattr_mark_sick(dp, whichfork);2836	if (error)2837		goto out_free;2838 2839	if (whichfork == XFS_ATTR_FORK)2840		xfs_buf_set_ref(bp, XFS_ATTR_BTREE_REF);2841	else2842		xfs_buf_set_ref(bp, XFS_DIR_BTREE_REF);2843	*bpp = bp;2844out_free:2845	if (mapp != &map)2846		kfree(mapp);2847 2848	return error;2849}2850 2851/*2852 * Readahead the dir/attr block.2853 */2854int2855xfs_da_reada_buf(2856	struct xfs_inode	*dp,2857	xfs_dablk_t		bno,2858	unsigned int		flags,2859	int			whichfork,2860	const struct xfs_buf_ops *ops)2861{2862	struct xfs_buf_map	map;2863	struct xfs_buf_map	*mapp;2864	int			nmap;2865	int			error;2866 2867	mapp = &map;2868	nmap = 1;2869	error = xfs_dabuf_map(dp, bno, flags, whichfork, &mapp, &nmap);2870	if (error || !nmap)2871		goto out_free;2872 2873	xfs_buf_readahead_map(dp->i_mount->m_ddev_targp, mapp, nmap, ops);2874 2875out_free:2876	if (mapp != &map)2877		kfree(mapp);2878 2879	return error;2880}2881