1/*
   2 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
 
   3 * All Rights Reserved.
   4 *
   5 * This program is free software; you can redistribute it and/or
   6 * modify it under the terms of the GNU General Public License as
   7 * published by the Free Software Foundation.
   8 *
   9 * This program is distributed in the hope that it would be useful,
  10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 * GNU General Public License for more details.
  13 *
  14 * You should have received a copy of the GNU General Public License
  15 * along with this program; if not, write the Free Software Foundation,
  16 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17 */
  18#include "xfs.h"
  19#include "xfs_fs.h"
  20#include "xfs_types.h"
 
 
 
  21#include "xfs_bit.h"
  22#include "xfs_log.h"
  23#include "xfs_trans.h"
  24#include "xfs_sb.h"
  25#include "xfs_ag.h"
  26#include "xfs_mount.h"
 
  27#include "xfs_da_btree.h"
  28#include "xfs_bmap_btree.h"
  29#include "xfs_dir2.h"
  30#include "xfs_dir2_format.h"
  31#include "xfs_dir2_priv.h"
  32#include "xfs_dinode.h"
  33#include "xfs_inode.h"
 
  34#include "xfs_inode_item.h"
  35#include "xfs_alloc.h"
  36#include "xfs_bmap.h"
  37#include "xfs_attr.h"
  38#include "xfs_attr_leaf.h"
  39#include "xfs_error.h"
  40#include "xfs_trace.h"
 
 
  41
  42/*
  43 * xfs_da_btree.c
  44 *
  45 * Routines to implement directories as Btrees of hashed names.
  46 */
  47
  48/*========================================================================
  49 * Function prototypes for the kernel.
  50 *========================================================================*/
  51
  52/*
  53 * Routines used for growing the Btree.
  54 */
  55STATIC int xfs_da_root_split(xfs_da_state_t *state,
  56					    xfs_da_state_blk_t *existing_root,
  57					    xfs_da_state_blk_t *new_child);
  58STATIC int xfs_da_node_split(xfs_da_state_t *state,
  59					    xfs_da_state_blk_t *existing_blk,
  60					    xfs_da_state_blk_t *split_blk,
  61					    xfs_da_state_blk_t *blk_to_add,
  62					    int treelevel,
  63					    int *result);
  64STATIC void xfs_da_node_rebalance(xfs_da_state_t *state,
  65					 xfs_da_state_blk_t *node_blk_1,
  66					 xfs_da_state_blk_t *node_blk_2);
  67STATIC void xfs_da_node_add(xfs_da_state_t *state,
  68				   xfs_da_state_blk_t *old_node_blk,
  69				   xfs_da_state_blk_t *new_node_blk);
  70
  71/*
  72 * Routines used for shrinking the Btree.
  73 */
  74STATIC int xfs_da_root_join(xfs_da_state_t *state,
  75					   xfs_da_state_blk_t *root_blk);
  76STATIC int xfs_da_node_toosmall(xfs_da_state_t *state, int *retval);
  77STATIC void xfs_da_node_remove(xfs_da_state_t *state,
  78					      xfs_da_state_blk_t *drop_blk);
  79STATIC void xfs_da_node_unbalance(xfs_da_state_t *state,
  80					 xfs_da_state_blk_t *src_node_blk,
  81					 xfs_da_state_blk_t *dst_node_blk);
  82
  83/*
  84 * Utility routines.
  85 */
  86STATIC uint	xfs_da_node_lasthash(xfs_dabuf_t *bp, int *count);
  87STATIC int	xfs_da_node_order(xfs_dabuf_t *node1_bp, xfs_dabuf_t *node2_bp);
  88STATIC xfs_dabuf_t *xfs_da_buf_make(int nbuf, xfs_buf_t **bps);
  89STATIC int	xfs_da_blk_unlink(xfs_da_state_t *state,
  90				  xfs_da_state_blk_t *drop_blk,
  91				  xfs_da_state_blk_t *save_blk);
  92STATIC void	xfs_da_state_kill_altpath(xfs_da_state_t *state);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  93
  94/*========================================================================
  95 * Routines used for growing the Btree.
  96 *========================================================================*/
  97
  98/*
  99 * Create the initial contents of an intermediate node.
 100 */
 101int
 102xfs_da_node_create(xfs_da_args_t *args, xfs_dablk_t blkno, int level,
 103				 xfs_dabuf_t **bpp, int whichfork)
 
 
 
 
 104{
 105	xfs_da_intnode_t *node;
 106	xfs_dabuf_t *bp;
 107	int error;
 108	xfs_trans_t *tp;
 
 
 
 109
 110	trace_xfs_da_node_create(args);
 
 111
 112	tp = args->trans;
 113	error = xfs_da_get_buf(tp, args->dp, blkno, -1, &bp, whichfork);
 114	if (error)
 115		return(error);
 116	ASSERT(bp != NULL);
 117	node = bp->data;
 118	node->hdr.info.forw = 0;
 119	node->hdr.info.back = 0;
 120	node->hdr.info.magic = cpu_to_be16(XFS_DA_NODE_MAGIC);
 121	node->hdr.info.pad = 0;
 122	node->hdr.count = 0;
 123	node->hdr.level = cpu_to_be16(level);
 
 
 
 
 
 
 
 124
 125	xfs_da_log_buf(tp, bp,
 126		XFS_DA_LOGRANGE(node, &node->hdr, sizeof(node->hdr)));
 
 127
 128	*bpp = bp;
 129	return(0);
 130}
 131
 132/*
 133 * Split a leaf node, rebalance, then possibly split
 134 * intermediate nodes, rebalance, etc.
 135 */
 136int							/* error */
 137xfs_da_split(xfs_da_state_t *state)
 
 138{
 139	xfs_da_state_blk_t *oldblk, *newblk, *addblk;
 140	xfs_da_intnode_t *node;
 141	xfs_dabuf_t *bp;
 142	int max, action, error, i;
 
 
 
 
 
 143
 144	trace_xfs_da_split(state->args);
 145
 146	/*
 147	 * Walk back up the tree splitting/inserting/adjusting as necessary.
 148	 * If we need to insert and there isn't room, split the node, then
 149	 * decide which fragment to insert the new block from below into.
 150	 * Note that we may split the root this way, but we need more fixup.
 151	 */
 152	max = state->path.active - 1;
 153	ASSERT((max >= 0) && (max < XFS_DA_NODE_MAXDEPTH));
 154	ASSERT(state->path.blk[max].magic == XFS_ATTR_LEAF_MAGIC ||
 155	       state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
 156
 157	addblk = &state->path.blk[max];		/* initial dummy value */
 158	for (i = max; (i >= 0) && addblk; state->path.active--, i--) {
 159		oldblk = &state->path.blk[i];
 160		newblk = &state->altpath.blk[i];
 161
 162		/*
 163		 * If a leaf node then
 164		 *     Allocate a new leaf node, then rebalance across them.
 165		 * else if an intermediate node then
 166		 *     We split on the last layer, must we split the node?
 167		 */
 168		switch (oldblk->magic) {
 169		case XFS_ATTR_LEAF_MAGIC:
 170			error = xfs_attr_leaf_split(state, oldblk, newblk);
 171			if ((error != 0) && (error != ENOSPC)) {
 172				return(error);	/* GROT: attr is inconsistent */
 173			}
 174			if (!error) {
 175				addblk = newblk;
 176				break;
 177			}
 178			/*
 179			 * Entry wouldn't fit, split the leaf again.
 180			 */
 181			state->extravalid = 1;
 182			if (state->inleaf) {
 183				state->extraafter = 0;	/* before newblk */
 184				trace_xfs_attr_leaf_split_before(state->args);
 185				error = xfs_attr_leaf_split(state, oldblk,
 186							    &state->extrablk);
 187			} else {
 188				state->extraafter = 1;	/* after newblk */
 189				trace_xfs_attr_leaf_split_after(state->args);
 190				error = xfs_attr_leaf_split(state, newblk,
 191							    &state->extrablk);
 192			}
 193			if (error)
 194				return(error);	/* GROT: attr inconsistent */
 195			addblk = newblk;
 196			break;
 197		case XFS_DIR2_LEAFN_MAGIC:
 198			error = xfs_dir2_leafn_split(state, oldblk, newblk);
 199			if (error)
 200				return error;
 201			addblk = newblk;
 202			break;
 203		case XFS_DA_NODE_MAGIC:
 204			error = xfs_da_node_split(state, oldblk, newblk, addblk,
 205							 max - i, &action);
 206			xfs_da_buf_done(addblk->bp);
 207			addblk->bp = NULL;
 208			if (error)
 209				return(error);	/* GROT: dir is inconsistent */
 210			/*
 211			 * Record the newly split block for the next time thru?
 212			 */
 213			if (action)
 214				addblk = newblk;
 215			else
 216				addblk = NULL;
 217			break;
 218		}
 219
 220		/*
 221		 * Update the btree to show the new hashval for this child.
 222		 */
 223		xfs_da_fixhashpath(state, &state->path);
 224		/*
 225		 * If we won't need this block again, it's getting dropped
 226		 * from the active path by the loop control, so we need
 227		 * to mark it done now.
 228		 */
 229		if (i > 0 || !addblk)
 230			xfs_da_buf_done(oldblk->bp);
 231	}
 232	if (!addblk)
 233		return(0);
 234
 235	/*
 236	 * Split the root node.
 237	 */
 238	ASSERT(state->path.active == 0);
 239	oldblk = &state->path.blk[0];
 240	error = xfs_da_root_split(state, oldblk, addblk);
 241	if (error) {
 242		xfs_da_buf_done(oldblk->bp);
 243		xfs_da_buf_done(addblk->bp);
 244		addblk->bp = NULL;
 245		return(error);	/* GROT: dir is inconsistent */
 246	}
 247
 248	/*
 249	 * Update pointers to the node which used to be block 0 and
 250	 * just got bumped because of the addition of a new root node.
 251	 * There might be three blocks involved if a double split occurred,
 252	 * and the original block 0 could be at any position in the list.
 
 
 
 
 
 253	 */
 254
 255	node = oldblk->bp->data;
 256	if (node->hdr.info.forw) {
 257		if (be32_to_cpu(node->hdr.info.forw) == addblk->blkno) {
 258			bp = addblk->bp;
 259		} else {
 260			ASSERT(state->extravalid);
 261			bp = state->extrablk.bp;
 262		}
 263		node = bp->data;
 264		node->hdr.info.back = cpu_to_be32(oldblk->blkno);
 265		xfs_da_log_buf(state->args->trans, bp,
 266		    XFS_DA_LOGRANGE(node, &node->hdr.info,
 267		    sizeof(node->hdr.info)));
 268	}
 269	node = oldblk->bp->data;
 270	if (node->hdr.info.back) {
 271		if (be32_to_cpu(node->hdr.info.back) == addblk->blkno) {
 272			bp = addblk->bp;
 273		} else {
 274			ASSERT(state->extravalid);
 275			bp = state->extrablk.bp;
 276		}
 277		node = bp->data;
 278		node->hdr.info.forw = cpu_to_be32(oldblk->blkno);
 279		xfs_da_log_buf(state->args->trans, bp,
 280		    XFS_DA_LOGRANGE(node, &node->hdr.info,
 281		    sizeof(node->hdr.info)));
 282	}
 283	xfs_da_buf_done(oldblk->bp);
 284	xfs_da_buf_done(addblk->bp);
 285	addblk->bp = NULL;
 286	return(0);
 287}
 288
 289/*
 290 * Split the root.  We have to create a new root and point to the two
 291 * parts (the split old root) that we just created.  Copy block zero to
 292 * the EOF, extending the inode in process.
 293 */
 294STATIC int						/* error */
 295xfs_da_root_split(xfs_da_state_t *state, xfs_da_state_blk_t *blk1,
 296				 xfs_da_state_blk_t *blk2)
 297{
 298	xfs_da_intnode_t *node, *oldroot;
 299	xfs_da_args_t *args;
 300	xfs_dablk_t blkno;
 301	xfs_dabuf_t *bp;
 302	int error, size;
 303	xfs_inode_t *dp;
 304	xfs_trans_t *tp;
 305	xfs_mount_t *mp;
 306	xfs_dir2_leaf_t *leaf;
 
 
 
 
 
 
 
 307
 308	trace_xfs_da_root_split(state->args);
 309
 310	/*
 311	 * Copy the existing (incorrect) block from the root node position
 312	 * to a free space somewhere.
 313	 */
 314	args = state->args;
 315	ASSERT(args != NULL);
 316	error = xfs_da_grow_inode(args, &blkno);
 317	if (error)
 318		return(error);
 
 319	dp = args->dp;
 320	tp = args->trans;
 321	mp = state->mp;
 322	error = xfs_da_get_buf(tp, dp, blkno, -1, &bp, args->whichfork);
 323	if (error)
 324		return(error);
 325	ASSERT(bp != NULL);
 326	node = bp->data;
 327	oldroot = blk1->bp->data;
 328	if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC)) {
 329		size = (int)((char *)&oldroot->btree[be16_to_cpu(oldroot->hdr.count)] -
 330			     (char *)oldroot);
 
 
 
 
 
 
 
 
 
 
 331	} else {
 332		ASSERT(oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
 
 
 333		leaf = (xfs_dir2_leaf_t *)oldroot;
 334		size = (int)((char *)&leaf->ents[be16_to_cpu(leaf->hdr.count)] -
 335			     (char *)leaf);
 
 
 
 
 
 
 
 
 
 
 
 336	}
 
 
 
 
 
 
 
 337	memcpy(node, oldroot, size);
 338	xfs_da_log_buf(tp, bp, 0, size - 1);
 339	xfs_da_buf_done(blk1->bp);
 
 
 
 
 
 
 
 
 340	blk1->bp = bp;
 341	blk1->blkno = blkno;
 342
 343	/*
 344	 * Set up the new root node.
 345	 */
 346	error = xfs_da_node_create(args,
 347		(args->whichfork == XFS_DATA_FORK) ? mp->m_dirleafblk : 0,
 348		be16_to_cpu(node->hdr.level) + 1, &bp, args->whichfork);
 349	if (error)
 350		return(error);
 351	node = bp->data;
 352	node->btree[0].hashval = cpu_to_be32(blk1->hashval);
 353	node->btree[0].before = cpu_to_be32(blk1->blkno);
 354	node->btree[1].hashval = cpu_to_be32(blk2->hashval);
 355	node->btree[1].before = cpu_to_be32(blk2->blkno);
 356	node->hdr.count = cpu_to_be16(2);
 
 
 
 
 357
 358#ifdef DEBUG
 359	if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC)) {
 
 360		ASSERT(blk1->blkno >= mp->m_dirleafblk &&
 361		       blk1->blkno < mp->m_dirfreeblk);
 362		ASSERT(blk2->blkno >= mp->m_dirleafblk &&
 363		       blk2->blkno < mp->m_dirfreeblk);
 364	}
 365#endif
 366
 367	/* Header is already logged by xfs_da_node_create */
 368	xfs_da_log_buf(tp, bp,
 369		XFS_DA_LOGRANGE(node, node->btree,
 370			sizeof(xfs_da_node_entry_t) * 2));
 371	xfs_da_buf_done(bp);
 372
 373	return(0);
 374}
 375
 376/*
 377 * Split the node, rebalance, then add the new entry.
 378 */
 379STATIC int						/* error */
 380xfs_da_node_split(xfs_da_state_t *state, xfs_da_state_blk_t *oldblk,
 381				 xfs_da_state_blk_t *newblk,
 382				 xfs_da_state_blk_t *addblk,
 383				 int treelevel, int *result)
 384{
 385	xfs_da_intnode_t *node;
 386	xfs_dablk_t blkno;
 387	int newcount, error;
 388	int useextra;
 
 
 
 
 
 
 389
 390	trace_xfs_da_node_split(state->args);
 391
 392	node = oldblk->bp->data;
 393	ASSERT(node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
 394
 395	/*
 396	 * With V2 dirs the extra block is data or freespace.
 397	 */
 398	useextra = state->extravalid && state->args->whichfork == XFS_ATTR_FORK;
 399	newcount = 1 + useextra;
 400	/*
 401	 * Do we have to split the node?
 402	 */
 403	if ((be16_to_cpu(node->hdr.count) + newcount) > state->node_ents) {
 404		/*
 405		 * Allocate a new node, add to the doubly linked chain of
 406		 * nodes, then move some of our excess entries into it.
 407		 */
 408		error = xfs_da_grow_inode(state->args, &blkno);
 409		if (error)
 410			return(error);	/* GROT: dir is inconsistent */
 411
 412		error = xfs_da_node_create(state->args, blkno, treelevel,
 413					   &newblk->bp, state->args->whichfork);
 414		if (error)
 415			return(error);	/* GROT: dir is inconsistent */
 416		newblk->blkno = blkno;
 417		newblk->magic = XFS_DA_NODE_MAGIC;
 418		xfs_da_node_rebalance(state, oldblk, newblk);
 419		error = xfs_da_blk_link(state, oldblk, newblk);
 420		if (error)
 421			return(error);
 422		*result = 1;
 423	} else {
 424		*result = 0;
 425	}
 426
 427	/*
 428	 * Insert the new entry(s) into the correct block
 429	 * (updating last hashval in the process).
 430	 *
 431	 * xfs_da_node_add() inserts BEFORE the given index,
 432	 * and as a result of using node_lookup_int() we always
 433	 * point to a valid entry (not after one), but a split
 434	 * operation always results in a new block whose hashvals
 435	 * FOLLOW the current block.
 436	 *
 437	 * If we had double-split op below us, then add the extra block too.
 438	 */
 439	node = oldblk->bp->data;
 440	if (oldblk->index <= be16_to_cpu(node->hdr.count)) {
 
 441		oldblk->index++;
 442		xfs_da_node_add(state, oldblk, addblk);
 443		if (useextra) {
 444			if (state->extraafter)
 445				oldblk->index++;
 446			xfs_da_node_add(state, oldblk, &state->extrablk);
 447			state->extravalid = 0;
 448		}
 449	} else {
 450		newblk->index++;
 451		xfs_da_node_add(state, newblk, addblk);
 452		if (useextra) {
 453			if (state->extraafter)
 454				newblk->index++;
 455			xfs_da_node_add(state, newblk, &state->extrablk);
 456			state->extravalid = 0;
 457		}
 458	}
 459
 460	return(0);
 461}
 462
 463/*
 464 * Balance the btree elements between two intermediate nodes,
 465 * usually one full and one empty.
 466 *
 467 * NOTE: if blk2 is empty, then it will get the upper half of blk1.
 468 */
 469STATIC void
 470xfs_da_node_rebalance(xfs_da_state_t *state, xfs_da_state_blk_t *blk1,
 471				     xfs_da_state_blk_t *blk2)
 472{
 473	xfs_da_intnode_t *node1, *node2, *tmpnode;
 474	xfs_da_node_entry_t *btree_s, *btree_d;
 475	int count, tmp;
 476	xfs_trans_t *tp;
 
 
 
 
 
 
 
 
 
 
 
 
 477
 478	trace_xfs_da_node_rebalance(state->args);
 479
 480	node1 = blk1->bp->data;
 481	node2 = blk2->bp->data;
 
 
 
 
 
 482	/*
 483	 * Figure out how many entries need to move, and in which direction.
 484	 * Swap the nodes around if that makes it simpler.
 485	 */
 486	if ((be16_to_cpu(node1->hdr.count) > 0) && (be16_to_cpu(node2->hdr.count) > 0) &&
 487	    ((be32_to_cpu(node2->btree[0].hashval) < be32_to_cpu(node1->btree[0].hashval)) ||
 488	     (be32_to_cpu(node2->btree[be16_to_cpu(node2->hdr.count)-1].hashval) <
 489	      be32_to_cpu(node1->btree[be16_to_cpu(node1->hdr.count)-1].hashval)))) {
 490		tmpnode = node1;
 491		node1 = node2;
 492		node2 = tmpnode;
 
 
 
 
 
 493	}
 494	ASSERT(node1->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
 495	ASSERT(node2->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
 496	count = (be16_to_cpu(node1->hdr.count) - be16_to_cpu(node2->hdr.count)) / 2;
 497	if (count == 0)
 498		return;
 499	tp = state->args->trans;
 500	/*
 501	 * Two cases: high-to-low and low-to-high.
 502	 */
 503	if (count > 0) {
 504		/*
 505		 * Move elements in node2 up to make a hole.
 506		 */
 507		if ((tmp = be16_to_cpu(node2->hdr.count)) > 0) {
 
 508			tmp *= (uint)sizeof(xfs_da_node_entry_t);
 509			btree_s = &node2->btree[0];
 510			btree_d = &node2->btree[count];
 511			memmove(btree_d, btree_s, tmp);
 512		}
 513
 514		/*
 515		 * Move the req'd B-tree elements from high in node1 to
 516		 * low in node2.
 517		 */
 518		be16_add_cpu(&node2->hdr.count, count);
 519		tmp = count * (uint)sizeof(xfs_da_node_entry_t);
 520		btree_s = &node1->btree[be16_to_cpu(node1->hdr.count) - count];
 521		btree_d = &node2->btree[0];
 522		memcpy(btree_d, btree_s, tmp);
 523		be16_add_cpu(&node1->hdr.count, -count);
 524	} else {
 525		/*
 526		 * Move the req'd B-tree elements from low in node2 to
 527		 * high in node1.
 528		 */
 529		count = -count;
 530		tmp = count * (uint)sizeof(xfs_da_node_entry_t);
 531		btree_s = &node2->btree[0];
 532		btree_d = &node1->btree[be16_to_cpu(node1->hdr.count)];
 533		memcpy(btree_d, btree_s, tmp);
 534		be16_add_cpu(&node1->hdr.count, count);
 535		xfs_da_log_buf(tp, blk1->bp,
 
 536			XFS_DA_LOGRANGE(node1, btree_d, tmp));
 537
 538		/*
 539		 * Move elements in node2 down to fill the hole.
 540		 */
 541		tmp  = be16_to_cpu(node2->hdr.count) - count;
 542		tmp *= (uint)sizeof(xfs_da_node_entry_t);
 543		btree_s = &node2->btree[count];
 544		btree_d = &node2->btree[0];
 545		memmove(btree_d, btree_s, tmp);
 546		be16_add_cpu(&node2->hdr.count, -count);
 547	}
 548
 549	/*
 550	 * Log header of node 1 and all current bits of node 2.
 551	 */
 552	xfs_da_log_buf(tp, blk1->bp,
 553		XFS_DA_LOGRANGE(node1, &node1->hdr, sizeof(node1->hdr)));
 554	xfs_da_log_buf(tp, blk2->bp,
 
 
 
 555		XFS_DA_LOGRANGE(node2, &node2->hdr,
 556			sizeof(node2->hdr) +
 557			sizeof(node2->btree[0]) * be16_to_cpu(node2->hdr.count)));
 558
 559	/*
 560	 * Record the last hashval from each block for upward propagation.
 561	 * (note: don't use the swapped node pointers)
 562	 */
 563	node1 = blk1->bp->data;
 564	node2 = blk2->bp->data;
 565	blk1->hashval = be32_to_cpu(node1->btree[be16_to_cpu(node1->hdr.count)-1].hashval);
 566	blk2->hashval = be32_to_cpu(node2->btree[be16_to_cpu(node2->hdr.count)-1].hashval);
 
 
 
 
 
 
 567
 568	/*
 569	 * Adjust the expected index for insertion.
 570	 */
 571	if (blk1->index >= be16_to_cpu(node1->hdr.count)) {
 572		blk2->index = blk1->index - be16_to_cpu(node1->hdr.count);
 573		blk1->index = be16_to_cpu(node1->hdr.count) + 1;	/* make it invalid */
 574	}
 575}
 576
 577/*
 578 * Add a new entry to an intermediate node.
 579 */
 580STATIC void
 581xfs_da_node_add(xfs_da_state_t *state, xfs_da_state_blk_t *oldblk,
 582			       xfs_da_state_blk_t *newblk)
 583{
 584	xfs_da_intnode_t *node;
 585	xfs_da_node_entry_t *btree;
 586	int tmp;
 
 
 
 
 587
 588	trace_xfs_da_node_add(state->args);
 589
 590	node = oldblk->bp->data;
 591	ASSERT(node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
 592	ASSERT((oldblk->index >= 0) && (oldblk->index <= be16_to_cpu(node->hdr.count)));
 
 
 593	ASSERT(newblk->blkno != 0);
 594	if (state->args->whichfork == XFS_DATA_FORK)
 595		ASSERT(newblk->blkno >= state->mp->m_dirleafblk &&
 596		       newblk->blkno < state->mp->m_dirfreeblk);
 597
 598	/*
 599	 * We may need to make some room before we insert the new node.
 600	 */
 601	tmp = 0;
 602	btree = &node->btree[ oldblk->index ];
 603	if (oldblk->index < be16_to_cpu(node->hdr.count)) {
 604		tmp = (be16_to_cpu(node->hdr.count) - oldblk->index) * (uint)sizeof(*btree);
 605		memmove(btree + 1, btree, tmp);
 606	}
 607	btree->hashval = cpu_to_be32(newblk->hashval);
 608	btree->before = cpu_to_be32(newblk->blkno);
 609	xfs_da_log_buf(state->args->trans, oldblk->bp,
 610		XFS_DA_LOGRANGE(node, btree, tmp + sizeof(*btree)));
 611	be16_add_cpu(&node->hdr.count, 1);
 612	xfs_da_log_buf(state->args->trans, oldblk->bp,
 613		XFS_DA_LOGRANGE(node, &node->hdr, sizeof(node->hdr)));
 
 
 614
 615	/*
 616	 * Copy the last hash value from the oldblk to propagate upwards.
 617	 */
 618	oldblk->hashval = be32_to_cpu(node->btree[be16_to_cpu(node->hdr.count)-1 ].hashval);
 619}
 620
 621/*========================================================================
 622 * Routines used for shrinking the Btree.
 623 *========================================================================*/
 624
 625/*
 626 * Deallocate an empty leaf node, remove it from its parent,
 627 * possibly deallocating that block, etc...
 628 */
 629int
 630xfs_da_join(xfs_da_state_t *state)
 
 631{
 632	xfs_da_state_blk_t *drop_blk, *save_blk;
 633	int action, error;
 
 
 634
 635	trace_xfs_da_join(state->args);
 636
 637	action = 0;
 638	drop_blk = &state->path.blk[ state->path.active-1 ];
 639	save_blk = &state->altpath.blk[ state->path.active-1 ];
 640	ASSERT(state->path.blk[0].magic == XFS_DA_NODE_MAGIC);
 641	ASSERT(drop_blk->magic == XFS_ATTR_LEAF_MAGIC ||
 642	       drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
 643
 644	/*
 645	 * Walk back up the tree joining/deallocating as necessary.
 646	 * When we stop dropping blocks, break out.
 647	 */
 648	for (  ; state->path.active >= 2; drop_blk--, save_blk--,
 649		 state->path.active--) {
 650		/*
 651		 * See if we can combine the block with a neighbor.
 652		 *   (action == 0) => no options, just leave
 653		 *   (action == 1) => coalesce, then unlink
 654		 *   (action == 2) => block empty, unlink it
 655		 */
 656		switch (drop_blk->magic) {
 657		case XFS_ATTR_LEAF_MAGIC:
 658			error = xfs_attr_leaf_toosmall(state, &action);
 659			if (error)
 660				return(error);
 661			if (action == 0)
 662				return(0);
 663			xfs_attr_leaf_unbalance(state, drop_blk, save_blk);
 664			break;
 665		case XFS_DIR2_LEAFN_MAGIC:
 666			error = xfs_dir2_leafn_toosmall(state, &action);
 667			if (error)
 668				return error;
 669			if (action == 0)
 670				return 0;
 671			xfs_dir2_leafn_unbalance(state, drop_blk, save_blk);
 672			break;
 673		case XFS_DA_NODE_MAGIC:
 674			/*
 675			 * Remove the offending node, fixup hashvals,
 676			 * check for a toosmall neighbor.
 677			 */
 678			xfs_da_node_remove(state, drop_blk);
 679			xfs_da_fixhashpath(state, &state->path);
 680			error = xfs_da_node_toosmall(state, &action);
 681			if (error)
 682				return(error);
 683			if (action == 0)
 684				return 0;
 685			xfs_da_node_unbalance(state, drop_blk, save_blk);
 686			break;
 687		}
 688		xfs_da_fixhashpath(state, &state->altpath);
 689		error = xfs_da_blk_unlink(state, drop_blk, save_blk);
 690		xfs_da_state_kill_altpath(state);
 691		if (error)
 692			return(error);
 693		error = xfs_da_shrink_inode(state->args, drop_blk->blkno,
 694							 drop_blk->bp);
 695		drop_blk->bp = NULL;
 696		if (error)
 697			return(error);
 698	}
 699	/*
 700	 * We joined all the way to the top.  If it turns out that
 701	 * we only have one entry in the root, make the child block
 702	 * the new root.
 703	 */
 704	xfs_da_node_remove(state, drop_blk);
 705	xfs_da_fixhashpath(state, &state->path);
 706	error = xfs_da_root_join(state, &state->path.blk[0]);
 707	return(error);
 708}
 709
 710#ifdef	DEBUG
 711static void
 712xfs_da_blkinfo_onlychild_validate(struct xfs_da_blkinfo *blkinfo, __u16 level)
 713{
 714	__be16	magic = blkinfo->magic;
 715
 716	if (level == 1) {
 717		ASSERT(magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
 718		       magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC));
 719	} else
 720		ASSERT(magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
 
 
 
 
 721	ASSERT(!blkinfo->forw);
 722	ASSERT(!blkinfo->back);
 723}
 724#else	/* !DEBUG */
 725#define	xfs_da_blkinfo_onlychild_validate(blkinfo, level)
 726#endif	/* !DEBUG */
 727
 728/*
 729 * We have only one entry in the root.  Copy the only remaining child of
 730 * the old root to block 0 as the new root node.
 731 */
 732STATIC int
 733xfs_da_root_join(xfs_da_state_t *state, xfs_da_state_blk_t *root_blk)
 734{
 735	xfs_da_intnode_t *oldroot;
 736	xfs_da_args_t *args;
 737	xfs_dablk_t child;
 738	xfs_dabuf_t *bp;
 739	int error;
 
 
 
 
 
 740
 741	trace_xfs_da_root_join(state->args);
 742
 743	args = state->args;
 744	ASSERT(args != NULL);
 745	ASSERT(root_blk->magic == XFS_DA_NODE_MAGIC);
 746	oldroot = root_blk->bp->data;
 747	ASSERT(oldroot->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
 748	ASSERT(!oldroot->hdr.info.forw);
 749	ASSERT(!oldroot->hdr.info.back);
 
 
 750
 751	/*
 752	 * If the root has more than one child, then don't do anything.
 753	 */
 754	if (be16_to_cpu(oldroot->hdr.count) > 1)
 755		return(0);
 756
 757	/*
 758	 * Read in the (only) child block, then copy those bytes into
 759	 * the root block's buffer and free the original child block.
 760	 */
 761	child = be32_to_cpu(oldroot->btree[0].before);
 
 762	ASSERT(child != 0);
 763	error = xfs_da_read_buf(args->trans, args->dp, child, -1, &bp,
 764					     args->whichfork);
 765	if (error)
 766		return(error);
 767	ASSERT(bp != NULL);
 768	xfs_da_blkinfo_onlychild_validate(bp->data,
 769					be16_to_cpu(oldroot->hdr.level));
 770
 771	memcpy(root_blk->bp->data, bp->data, state->blocksize);
 772	xfs_da_log_buf(args->trans, root_blk->bp, 0, state->blocksize - 1);
 
 
 
 
 
 
 
 
 
 
 
 
 
 773	error = xfs_da_shrink_inode(args, child, bp);
 774	return(error);
 775}
 776
 777/*
 778 * Check a node block and its neighbors to see if the block should be
 779 * collapsed into one or the other neighbor.  Always keep the block
 780 * with the smaller block number.
 781 * If the current block is over 50% full, don't try to join it, return 0.
 782 * If the block is empty, fill in the state structure and return 2.
 783 * If it can be collapsed, fill in the state structure and return 1.
 784 * If nothing can be done, return 0.
 785 */
 786STATIC int
 787xfs_da_node_toosmall(xfs_da_state_t *state, int *action)
 788{
 789	xfs_da_intnode_t *node;
 790	xfs_da_state_blk_t *blk;
 791	xfs_da_blkinfo_t *info;
 792	int count, forward, error, retval, i;
 793	xfs_dablk_t blkno;
 794	xfs_dabuf_t *bp;
 
 
 
 
 
 
 
 
 
 
 795
 796	/*
 797	 * Check for the degenerate case of the block being over 50% full.
 798	 * If so, it's not worth even looking to see if we might be able
 799	 * to coalesce with a sibling.
 800	 */
 801	blk = &state->path.blk[ state->path.active-1 ];
 802	info = blk->bp->data;
 803	ASSERT(info->magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
 804	node = (xfs_da_intnode_t *)info;
 805	count = be16_to_cpu(node->hdr.count);
 806	if (count > (state->node_ents >> 1)) {
 807		*action = 0;	/* blk over 50%, don't try to join */
 808		return(0);	/* blk over 50%, don't try to join */
 809	}
 810
 811	/*
 812	 * Check for the degenerate case of the block being empty.
 813	 * If the block is empty, we'll simply delete it, no need to
 814	 * coalesce it with a sibling block.  We choose (arbitrarily)
 815	 * to merge with the forward block unless it is NULL.
 816	 */
 817	if (count == 0) {
 818		/*
 819		 * Make altpath point to the block we want to keep and
 820		 * path point to the block we want to drop (this one).
 821		 */
 822		forward = (info->forw != 0);
 823		memcpy(&state->altpath, &state->path, sizeof(state->path));
 824		error = xfs_da_path_shift(state, &state->altpath, forward,
 825						 0, &retval);
 826		if (error)
 827			return(error);
 828		if (retval) {
 829			*action = 0;
 830		} else {
 831			*action = 2;
 832		}
 833		return(0);
 834	}
 835
 836	/*
 837	 * Examine each sibling block to see if we can coalesce with
 838	 * at least 25% free space to spare.  We need to figure out
 839	 * whether to merge with the forward or the backward block.
 840	 * We prefer coalescing with the lower numbered sibling so as
 841	 * to shrink a directory over time.
 842	 */
 
 
 
 
 843	/* start with smaller blk num */
 844	forward = (be32_to_cpu(info->forw) < be32_to_cpu(info->back));
 845	for (i = 0; i < 2; forward = !forward, i++) {
 
 846		if (forward)
 847			blkno = be32_to_cpu(info->forw);
 848		else
 849			blkno = be32_to_cpu(info->back);
 850		if (blkno == 0)
 851			continue;
 852		error = xfs_da_read_buf(state->args->trans, state->args->dp,
 853					blkno, -1, &bp, state->args->whichfork);
 854		if (error)
 855			return(error);
 856		ASSERT(bp != NULL);
 857
 858		node = (xfs_da_intnode_t *)info;
 859		count  = state->node_ents;
 860		count -= state->node_ents >> 2;
 861		count -= be16_to_cpu(node->hdr.count);
 862		node = bp->data;
 863		ASSERT(node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
 864		count -= be16_to_cpu(node->hdr.count);
 865		xfs_da_brelse(state->args->trans, bp);
 866		if (count >= 0)
 867			break;	/* fits with at least 25% to spare */
 868	}
 869	if (i >= 2) {
 870		*action = 0;
 871		return(0);
 872	}
 873
 874	/*
 875	 * Make altpath point to the block we want to keep (the lower
 876	 * numbered block) and path point to the block we want to drop.
 877	 */
 878	memcpy(&state->altpath, &state->path, sizeof(state->path));
 879	if (blkno < blk->blkno) {
 880		error = xfs_da_path_shift(state, &state->altpath, forward,
 881						 0, &retval);
 882		if (error) {
 883			return(error);
 884		}
 885		if (retval) {
 886			*action = 0;
 887			return(0);
 888		}
 889	} else {
 890		error = xfs_da_path_shift(state, &state->path, forward,
 891						 0, &retval);
 892		if (error) {
 893			return(error);
 894		}
 895		if (retval) {
 896			*action = 0;
 897			return(0);
 898		}
 899	}
 900	*action = 1;
 901	return(0);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 902}
 903
 904/*
 905 * Walk back up the tree adjusting hash values as necessary,
 906 * when we stop making changes, return.
 907 */
 908void
 909xfs_da_fixhashpath(xfs_da_state_t *state, xfs_da_state_path_t *path)
 910{
 911	xfs_da_state_blk_t *blk;
 912	xfs_da_intnode_t *node;
 913	xfs_da_node_entry_t *btree;
 914	xfs_dahash_t lasthash=0;
 915	int level, count;
 
 
 
 
 
 
 916
 917	level = path->active-1;
 918	blk = &path->blk[ level ];
 919	switch (blk->magic) {
 920	case XFS_ATTR_LEAF_MAGIC:
 921		lasthash = xfs_attr_leaf_lasthash(blk->bp, &count);
 922		if (count == 0)
 923			return;
 924		break;
 925	case XFS_DIR2_LEAFN_MAGIC:
 926		lasthash = xfs_dir2_leafn_lasthash(blk->bp, &count);
 927		if (count == 0)
 928			return;
 929		break;
 930	case XFS_DA_NODE_MAGIC:
 931		lasthash = xfs_da_node_lasthash(blk->bp, &count);
 932		if (count == 0)
 933			return;
 934		break;
 935	}
 936	for (blk--, level--; level >= 0; blk--, level--) {
 937		node = blk->bp->data;
 938		ASSERT(node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
 939		btree = &node->btree[ blk->index ];
 940		if (be32_to_cpu(btree->hashval) == lasthash)
 
 
 941			break;
 942		blk->hashval = lasthash;
 943		btree->hashval = cpu_to_be32(lasthash);
 944		xfs_da_log_buf(state->args->trans, blk->bp,
 945				  XFS_DA_LOGRANGE(node, btree, sizeof(*btree)));
 
 946
 947		lasthash = be32_to_cpu(node->btree[be16_to_cpu(node->hdr.count)-1].hashval);
 948	}
 949}
 950
 951/*
 952 * Remove an entry from an intermediate node.
 953 */
 954STATIC void
 955xfs_da_node_remove(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk)
 956{
 957	xfs_da_intnode_t *node;
 958	xfs_da_node_entry_t *btree;
 959	int tmp;
 
 
 
 
 
 960
 961	trace_xfs_da_node_remove(state->args);
 962
 963	node = drop_blk->bp->data;
 964	ASSERT(drop_blk->index < be16_to_cpu(node->hdr.count));
 
 965	ASSERT(drop_blk->index >= 0);
 966
 967	/*
 968	 * Copy over the offending entry, or just zero it out.
 969	 */
 970	btree = &node->btree[drop_blk->index];
 971	if (drop_blk->index < (be16_to_cpu(node->hdr.count)-1)) {
 972		tmp  = be16_to_cpu(node->hdr.count) - drop_blk->index - 1;
 
 973		tmp *= (uint)sizeof(xfs_da_node_entry_t);
 974		memmove(btree, btree + 1, tmp);
 975		xfs_da_log_buf(state->args->trans, drop_blk->bp,
 976		    XFS_DA_LOGRANGE(node, btree, tmp));
 977		btree = &node->btree[be16_to_cpu(node->hdr.count)-1];
 978	}
 979	memset((char *)btree, 0, sizeof(xfs_da_node_entry_t));
 980	xfs_da_log_buf(state->args->trans, drop_blk->bp,
 981	    XFS_DA_LOGRANGE(node, btree, sizeof(*btree)));
 982	be16_add_cpu(&node->hdr.count, -1);
 983	xfs_da_log_buf(state->args->trans, drop_blk->bp,
 984	    XFS_DA_LOGRANGE(node, &node->hdr, sizeof(node->hdr)));
 
 985
 986	/*
 987	 * Copy the last hash value from the block to propagate upwards.
 988	 */
 989	btree--;
 990	drop_blk->hashval = be32_to_cpu(btree->hashval);
 991}
 992
 993/*
 994 * Unbalance the btree elements between two intermediate nodes,
 995 * move all Btree elements from one node into another.
 996 */
 997STATIC void
 998xfs_da_node_unbalance(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk,
 999				     xfs_da_state_blk_t *save_blk)
1000{
1001	xfs_da_intnode_t *drop_node, *save_node;
1002	xfs_da_node_entry_t *btree;
1003	int tmp;
1004	xfs_trans_t *tp;
 
 
 
 
 
 
 
 
1005
1006	trace_xfs_da_node_unbalance(state->args);
1007
1008	drop_node = drop_blk->bp->data;
1009	save_node = save_blk->bp->data;
1010	ASSERT(drop_node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
1011	ASSERT(save_node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
 
 
1012	tp = state->args->trans;
1013
1014	/*
1015	 * If the dying block has lower hashvals, then move all the
1016	 * elements in the remaining block up to make a hole.
1017	 */
1018	if ((be32_to_cpu(drop_node->btree[0].hashval) < be32_to_cpu(save_node->btree[ 0 ].hashval)) ||
1019	    (be32_to_cpu(drop_node->btree[be16_to_cpu(drop_node->hdr.count)-1].hashval) <
1020	     be32_to_cpu(save_node->btree[be16_to_cpu(save_node->hdr.count)-1].hashval)))
1021	{
1022		btree = &save_node->btree[be16_to_cpu(drop_node->hdr.count)];
1023		tmp = be16_to_cpu(save_node->hdr.count) * (uint)sizeof(xfs_da_node_entry_t);
1024		memmove(btree, &save_node->btree[0], tmp);
1025		btree = &save_node->btree[0];
1026		xfs_da_log_buf(tp, save_blk->bp,
1027			XFS_DA_LOGRANGE(save_node, btree,
1028				(be16_to_cpu(save_node->hdr.count) + be16_to_cpu(drop_node->hdr.count)) *
1029				sizeof(xfs_da_node_entry_t)));
 
1030	} else {
1031		btree = &save_node->btree[be16_to_cpu(save_node->hdr.count)];
1032		xfs_da_log_buf(tp, save_blk->bp,
1033			XFS_DA_LOGRANGE(save_node, btree,
1034				be16_to_cpu(drop_node->hdr.count) *
1035				sizeof(xfs_da_node_entry_t)));
1036	}
1037
1038	/*
1039	 * Move all the B-tree elements from drop_blk to save_blk.
1040	 */
1041	tmp = be16_to_cpu(drop_node->hdr.count) * (uint)sizeof(xfs_da_node_entry_t);
1042	memcpy(btree, &drop_node->btree[0], tmp);
1043	be16_add_cpu(&save_node->hdr.count, be16_to_cpu(drop_node->hdr.count));
1044
1045	xfs_da_log_buf(tp, save_blk->bp,
 
1046		XFS_DA_LOGRANGE(save_node, &save_node->hdr,
1047			sizeof(save_node->hdr)));
1048
1049	/*
1050	 * Save the last hashval in the remaining block for upward propagation.
1051	 */
1052	save_blk->hashval = be32_to_cpu(save_node->btree[be16_to_cpu(save_node->hdr.count)-1].hashval);
1053}
1054
1055/*========================================================================
1056 * Routines used for finding things in the Btree.
1057 *========================================================================*/
1058
1059/*
1060 * Walk down the Btree looking for a particular filename, filling
1061 * in the state structure as we go.
1062 *
1063 * We will set the state structure to point to each of the elements
1064 * in each of the nodes where either the hashval is or should be.
1065 *
1066 * We support duplicate hashval's so for each entry in the current
1067 * node that could contain the desired hashval, descend.  This is a
1068 * pruned depth-first tree search.
1069 */
1070int							/* error */
1071xfs_da_node_lookup_int(xfs_da_state_t *state, int *result)
1072{
1073	xfs_da_state_blk_t *blk;
1074	xfs_da_blkinfo_t *curr;
1075	xfs_da_intnode_t *node;
1076	xfs_da_node_entry_t *btree;
1077	xfs_dablk_t blkno;
1078	int probe, span, max, error, retval;
1079	xfs_dahash_t hashval, btreehashval;
1080	xfs_da_args_t *args;
 
 
 
 
 
 
 
 
 
1081
1082	args = state->args;
1083
1084	/*
1085	 * Descend thru the B-tree searching each level for the right
1086	 * node to use, until the right hashval is found.
1087	 */
1088	blkno = (args->whichfork == XFS_DATA_FORK)? state->mp->m_dirleafblk : 0;
1089	for (blk = &state->path.blk[0], state->path.active = 1;
1090			 state->path.active <= XFS_DA_NODE_MAXDEPTH;
1091			 blk++, state->path.active++) {
1092		/*
1093		 * Read the next node down in the tree.
1094		 */
1095		blk->blkno = blkno;
1096		error = xfs_da_read_buf(args->trans, args->dp, blkno,
1097					-1, &blk->bp, args->whichfork);
1098		if (error) {
1099			blk->blkno = 0;
1100			state->path.active--;
1101			return(error);
1102		}
1103		curr = blk->bp->data;
1104		blk->magic = be16_to_cpu(curr->magic);
1105		ASSERT(blk->magic == XFS_DA_NODE_MAGIC ||
1106		       blk->magic == XFS_DIR2_LEAFN_MAGIC ||
1107		       blk->magic == XFS_ATTR_LEAF_MAGIC);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1108
1109		/*
1110		 * Search an intermediate node for a match.
1111		 */
1112		if (blk->magic == XFS_DA_NODE_MAGIC) {
1113			node = blk->bp->data;
1114			max = be16_to_cpu(node->hdr.count);
1115			blk->hashval = be32_to_cpu(node->btree[max-1].hashval);
1116
1117			/*
1118			 * Binary search.  (note: small blocks will skip loop)
1119			 */
1120			probe = span = max / 2;
1121			hashval = args->hashval;
1122			for (btree = &node->btree[probe]; span > 4;
1123				   btree = &node->btree[probe]) {
1124				span /= 2;
1125				btreehashval = be32_to_cpu(btree->hashval);
1126				if (btreehashval < hashval)
1127					probe += span;
1128				else if (btreehashval > hashval)
1129					probe -= span;
1130				else
1131					break;
1132			}
1133			ASSERT((probe >= 0) && (probe < max));
1134			ASSERT((span <= 4) || (be32_to_cpu(btree->hashval) == hashval));
1135
1136			/*
1137			 * Since we may have duplicate hashval's, find the first
1138			 * matching hashval in the node.
1139			 */
1140			while ((probe > 0) && (be32_to_cpu(btree->hashval) >= hashval)) {
1141				btree--;
1142				probe--;
1143			}
1144			while ((probe < max) && (be32_to_cpu(btree->hashval) < hashval)) {
1145				btree++;
1146				probe++;
1147			}
 
 
 
 
 
 
1148
1149			/*
1150			 * Pick the right block to descend on.
1151			 */
1152			if (probe == max) {
1153				blk->index = max-1;
1154				blkno = be32_to_cpu(node->btree[max-1].before);
1155			} else {
1156				blk->index = probe;
1157				blkno = be32_to_cpu(btree->before);
1158			}
1159		} else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
1160			blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
1161			break;
1162		} else if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {
1163			blk->hashval = xfs_dir2_leafn_lasthash(blk->bp, NULL);
1164			break;
 
 
 
 
 
 
1165		}
1166	}
1167
1168	/*
1169	 * A leaf block that ends in the hashval that we are interested in
1170	 * (final hashval == search hashval) means that the next block may
1171	 * contain more entries with the same hashval, shift upward to the
1172	 * next leaf and keep searching.
1173	 */
1174	for (;;) {
1175		if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {
1176			retval = xfs_dir2_leafn_lookup_int(blk->bp, args,
1177							&blk->index, state);
1178		} else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
1179			retval = xfs_attr_leaf_lookup_int(blk->bp, args);
1180			blk->index = args->index;
1181			args->blkno = blk->blkno;
1182		} else {
1183			ASSERT(0);
1184			return XFS_ERROR(EFSCORRUPTED);
1185		}
1186		if (((retval == ENOENT) || (retval == ENOATTR)) &&
1187		    (blk->hashval == args->hashval)) {
1188			error = xfs_da_path_shift(state, &state->path, 1, 1,
1189							 &retval);
1190			if (error)
1191				return(error);
1192			if (retval == 0) {
1193				continue;
1194			} else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
1195				/* path_shift() gives ENOENT */
1196				retval = XFS_ERROR(ENOATTR);
1197			}
1198		}
1199		break;
1200	}
1201	*result = retval;
1202	return(0);
1203}
1204
1205/*========================================================================
1206 * Utility routines.
1207 *========================================================================*/
1208
1209/*
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1210 * Link a new block into a doubly linked list of blocks (of whatever type).
1211 */
1212int							/* error */
1213xfs_da_blk_link(xfs_da_state_t *state, xfs_da_state_blk_t *old_blk,
1214			       xfs_da_state_blk_t *new_blk)
1215{
1216	xfs_da_blkinfo_t *old_info, *new_info, *tmp_info;
1217	xfs_da_args_t *args;
1218	int before=0, error;
1219	xfs_dabuf_t *bp;
 
 
 
 
 
 
1220
1221	/*
1222	 * Set up environment.
1223	 */
1224	args = state->args;
1225	ASSERT(args != NULL);
1226	old_info = old_blk->bp->data;
1227	new_info = new_blk->bp->data;
1228	ASSERT(old_blk->magic == XFS_DA_NODE_MAGIC ||
1229	       old_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
1230	       old_blk->magic == XFS_ATTR_LEAF_MAGIC);
1231	ASSERT(old_blk->magic == be16_to_cpu(old_info->magic));
1232	ASSERT(new_blk->magic == be16_to_cpu(new_info->magic));
1233	ASSERT(old_blk->magic == new_blk->magic);
1234
1235	switch (old_blk->magic) {
1236	case XFS_ATTR_LEAF_MAGIC:
1237		before = xfs_attr_leaf_order(old_blk->bp, new_blk->bp);
1238		break;
1239	case XFS_DIR2_LEAFN_MAGIC:
1240		before = xfs_dir2_leafn_order(old_blk->bp, new_blk->bp);
1241		break;
1242	case XFS_DA_NODE_MAGIC:
1243		before = xfs_da_node_order(old_blk->bp, new_blk->bp);
1244		break;
1245	}
1246
1247	/*
1248	 * Link blocks in appropriate order.
1249	 */
1250	if (before) {
1251		/*
1252		 * Link new block in before existing block.
1253		 */
1254		trace_xfs_da_link_before(args);
1255		new_info->forw = cpu_to_be32(old_blk->blkno);
1256		new_info->back = old_info->back;
1257		if (old_info->back) {
1258			error = xfs_da_read_buf(args->trans, args->dp,
1259						be32_to_cpu(old_info->back),
1260						-1, &bp, args->whichfork);
1261			if (error)
1262				return(error);
1263			ASSERT(bp != NULL);
1264			tmp_info = bp->data;
1265			ASSERT(be16_to_cpu(tmp_info->magic) == be16_to_cpu(old_info->magic));
1266			ASSERT(be32_to_cpu(tmp_info->forw) == old_blk->blkno);
1267			tmp_info->forw = cpu_to_be32(new_blk->blkno);
1268			xfs_da_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
1269			xfs_da_buf_done(bp);
1270		}
1271		old_info->back = cpu_to_be32(new_blk->blkno);
1272	} else {
1273		/*
1274		 * Link new block in after existing block.
1275		 */
1276		trace_xfs_da_link_after(args);
1277		new_info->forw = old_info->forw;
1278		new_info->back = cpu_to_be32(old_blk->blkno);
1279		if (old_info->forw) {
1280			error = xfs_da_read_buf(args->trans, args->dp,
1281						be32_to_cpu(old_info->forw),
1282						-1, &bp, args->whichfork);
1283			if (error)
1284				return(error);
1285			ASSERT(bp != NULL);
1286			tmp_info = bp->data;
1287			ASSERT(tmp_info->magic == old_info->magic);
1288			ASSERT(be32_to_cpu(tmp_info->back) == old_blk->blkno);
1289			tmp_info->back = cpu_to_be32(new_blk->blkno);
1290			xfs_da_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
1291			xfs_da_buf_done(bp);
1292		}
1293		old_info->forw = cpu_to_be32(new_blk->blkno);
1294	}
1295
1296	xfs_da_log_buf(args->trans, old_blk->bp, 0, sizeof(*tmp_info) - 1);
1297	xfs_da_log_buf(args->trans, new_blk->bp, 0, sizeof(*tmp_info) - 1);
1298	return(0);
1299}
1300
1301/*
1302 * Compare two intermediate nodes for "order".
1303 */
1304STATIC int
1305xfs_da_node_order(xfs_dabuf_t *node1_bp, xfs_dabuf_t *node2_bp)
1306{
1307	xfs_da_intnode_t *node1, *node2;
1308
1309	node1 = node1_bp->data;
1310	node2 = node2_bp->data;
1311	ASSERT(node1->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC) &&
1312	       node2->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
1313	if ((be16_to_cpu(node1->hdr.count) > 0) && (be16_to_cpu(node2->hdr.count) > 0) &&
1314	    ((be32_to_cpu(node2->btree[0].hashval) <
1315	      be32_to_cpu(node1->btree[0].hashval)) ||
1316	     (be32_to_cpu(node2->btree[be16_to_cpu(node2->hdr.count)-1].hashval) <
1317	      be32_to_cpu(node1->btree[be16_to_cpu(node1->hdr.count)-1].hashval)))) {
1318		return(1);
1319	}
1320	return(0);
1321}
1322
1323/*
1324 * Pick up the last hashvalue from an intermediate node.
1325 */
1326STATIC uint
1327xfs_da_node_lasthash(xfs_dabuf_t *bp, int *count)
1328{
1329	xfs_da_intnode_t *node;
1330
1331	node = bp->data;
1332	ASSERT(node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
1333	if (count)
1334		*count = be16_to_cpu(node->hdr.count);
1335	if (!node->hdr.count)
1336		return(0);
1337	return be32_to_cpu(node->btree[be16_to_cpu(node->hdr.count)-1].hashval);
1338}
1339
1340/*
1341 * Unlink a block from a doubly linked list of blocks.
1342 */
1343STATIC int						/* error */
1344xfs_da_blk_unlink(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk,
1345				 xfs_da_state_blk_t *save_blk)
1346{
1347	xfs_da_blkinfo_t *drop_info, *save_info, *tmp_info;
1348	xfs_da_args_t *args;
1349	xfs_dabuf_t *bp;
1350	int error;
 
 
 
 
1351
1352	/*
1353	 * Set up environment.
1354	 */
1355	args = state->args;
1356	ASSERT(args != NULL);
1357	save_info = save_blk->bp->data;
1358	drop_info = drop_blk->bp->data;
1359	ASSERT(save_blk->magic == XFS_DA_NODE_MAGIC ||
1360	       save_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
1361	       save_blk->magic == XFS_ATTR_LEAF_MAGIC);
1362	ASSERT(save_blk->magic == be16_to_cpu(save_info->magic));
1363	ASSERT(drop_blk->magic == be16_to_cpu(drop_info->magic));
1364	ASSERT(save_blk->magic == drop_blk->magic);
1365	ASSERT((be32_to_cpu(save_info->forw) == drop_blk->blkno) ||
1366	       (be32_to_cpu(save_info->back) == drop_blk->blkno));
1367	ASSERT((be32_to_cpu(drop_info->forw) == save_blk->blkno) ||
1368	       (be32_to_cpu(drop_info->back) == save_blk->blkno));
1369
1370	/*
1371	 * Unlink the leaf block from the doubly linked chain of leaves.
1372	 */
1373	if (be32_to_cpu(save_info->back) == drop_blk->blkno) {
1374		trace_xfs_da_unlink_back(args);
1375		save_info->back = drop_info->back;
1376		if (drop_info->back) {
1377			error = xfs_da_read_buf(args->trans, args->dp,
1378						be32_to_cpu(drop_info->back),
1379						-1, &bp, args->whichfork);
1380			if (error)
1381				return(error);
1382			ASSERT(bp != NULL);
1383			tmp_info = bp->data;
1384			ASSERT(tmp_info->magic == save_info->magic);
1385			ASSERT(be32_to_cpu(tmp_info->forw) == drop_blk->blkno);
1386			tmp_info->forw = cpu_to_be32(save_blk->blkno);
1387			xfs_da_log_buf(args->trans, bp, 0,
1388						    sizeof(*tmp_info) - 1);
1389			xfs_da_buf_done(bp);
1390		}
1391	} else {
1392		trace_xfs_da_unlink_forward(args);
1393		save_info->forw = drop_info->forw;
1394		if (drop_info->forw) {
1395			error = xfs_da_read_buf(args->trans, args->dp,
1396						be32_to_cpu(drop_info->forw),
1397						-1, &bp, args->whichfork);
1398			if (error)
1399				return(error);
1400			ASSERT(bp != NULL);
1401			tmp_info = bp->data;
1402			ASSERT(tmp_info->magic == save_info->magic);
1403			ASSERT(be32_to_cpu(tmp_info->back) == drop_blk->blkno);
1404			tmp_info->back = cpu_to_be32(save_blk->blkno);
1405			xfs_da_log_buf(args->trans, bp, 0,
1406						    sizeof(*tmp_info) - 1);
1407			xfs_da_buf_done(bp);
1408		}
1409	}
1410
1411	xfs_da_log_buf(args->trans, save_blk->bp, 0, sizeof(*save_info) - 1);
1412	return(0);
1413}
1414
1415/*
1416 * Move a path "forward" or "!forward" one block at the current level.
1417 *
1418 * This routine will adjust a "path" to point to the next block
1419 * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
1420 * Btree, including updating pointers to the intermediate nodes between
1421 * the new bottom and the root.
1422 */
1423int							/* error */
1424xfs_da_path_shift(xfs_da_state_t *state, xfs_da_state_path_t *path,
1425				 int forward, int release, int *result)
1426{
1427	xfs_da_state_blk_t *blk;
1428	xfs_da_blkinfo_t *info;
1429	xfs_da_intnode_t *node;
1430	xfs_da_args_t *args;
1431	xfs_dablk_t blkno=0;
1432	int level, error;
 
 
 
 
 
 
 
 
 
 
1433
1434	/*
1435	 * Roll up the Btree looking for the first block where our
1436	 * current index is not at the edge of the block.  Note that
1437	 * we skip the bottom layer because we want the sibling block.
1438	 */
1439	args = state->args;
1440	ASSERT(args != NULL);
1441	ASSERT(path != NULL);
1442	ASSERT((path->active > 0) && (path->active < XFS_DA_NODE_MAXDEPTH));
1443	level = (path->active-1) - 1;	/* skip bottom layer in path */
1444	for (blk = &path->blk[level]; level >= 0; blk--, level--) {
1445		ASSERT(blk->bp != NULL);
1446		node = blk->bp->data;
1447		ASSERT(node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
1448		if (forward && (blk->index < be16_to_cpu(node->hdr.count)-1)) {
 
1449			blk->index++;
1450			blkno = be32_to_cpu(node->btree[blk->index].before);
1451			break;
1452		} else if (!forward && (blk->index > 0)) {
1453			blk->index--;
1454			blkno = be32_to_cpu(node->btree[blk->index].before);
1455			break;
1456		}
1457	}
1458	if (level < 0) {
1459		*result = XFS_ERROR(ENOENT);	/* we're out of our tree */
1460		ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
1461		return(0);
1462	}
1463
1464	/*
1465	 * Roll down the edge of the subtree until we reach the
1466	 * same depth we were at originally.
1467	 */
1468	for (blk++, level++; level < path->active; blk++, level++) {
1469		/*
1470		 * Release the old block.
1471		 * (if it's dirty, trans won't actually let go)
1472		 */
1473		if (release)
1474			xfs_da_brelse(args->trans, blk->bp);
1475
1476		/*
1477		 * Read the next child block.
1478		 */
1479		blk->blkno = blkno;
1480		error = xfs_da_read_buf(args->trans, args->dp, blkno, -1,
1481						     &blk->bp, args->whichfork);
1482		if (error)
1483			return(error);
1484		ASSERT(blk->bp != NULL);
1485		info = blk->bp->data;
1486		ASSERT(info->magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
 
1487		       info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1488		       info->magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC));
1489		blk->magic = be16_to_cpu(info->magic);
1490		if (blk->magic == XFS_DA_NODE_MAGIC) {
 
 
 
 
 
 
 
 
 
 
1491			node = (xfs_da_intnode_t *)info;
1492			blk->hashval = be32_to_cpu(node->btree[be16_to_cpu(node->hdr.count)-1].hashval);
 
 
1493			if (forward)
1494				blk->index = 0;
1495			else
1496				blk->index = be16_to_cpu(node->hdr.count)-1;
1497			blkno = be32_to_cpu(node->btree[blk->index].before);
1498		} else {
 
 
 
1499			ASSERT(level == path->active-1);
1500			blk->index = 0;
1501			switch(blk->magic) {
1502			case XFS_ATTR_LEAF_MAGIC:
1503				blk->hashval = xfs_attr_leaf_lasthash(blk->bp,
1504								      NULL);
1505				break;
1506			case XFS_DIR2_LEAFN_MAGIC:
1507				blk->hashval = xfs_dir2_leafn_lasthash(blk->bp,
1508								       NULL);
1509				break;
1510			default:
1511				ASSERT(blk->magic == XFS_ATTR_LEAF_MAGIC ||
1512				       blk->magic == XFS_DIR2_LEAFN_MAGIC);
1513				break;
1514			}
1515		}
1516	}
1517	*result = 0;
1518	return(0);
1519}
1520
1521
1522/*========================================================================
1523 * Utility routines.
1524 *========================================================================*/
1525
1526/*
1527 * Implement a simple hash on a character string.
1528 * Rotate the hash value by 7 bits, then XOR each character in.
1529 * This is implemented with some source-level loop unrolling.
1530 */
1531xfs_dahash_t
1532xfs_da_hashname(const __uint8_t *name, int namelen)
1533{
1534	xfs_dahash_t hash;
1535
1536	/*
1537	 * Do four characters at a time as long as we can.
1538	 */
1539	for (hash = 0; namelen >= 4; namelen -= 4, name += 4)
1540		hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
1541		       (name[3] << 0) ^ rol32(hash, 7 * 4);
1542
1543	/*
1544	 * Now do the rest of the characters.
1545	 */
1546	switch (namelen) {
1547	case 3:
1548		return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
1549		       rol32(hash, 7 * 3);
1550	case 2:
1551		return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);
1552	case 1:
1553		return (name[0] << 0) ^ rol32(hash, 7 * 1);
1554	default: /* case 0: */
1555		return hash;
1556	}
1557}
1558
1559enum xfs_dacmp
1560xfs_da_compname(
1561	struct xfs_da_args *args,
1562	const unsigned char *name,
1563	int		len)
1564{
1565	return (args->namelen == len && memcmp(args->name, name, len) == 0) ?
1566					XFS_CMP_EXACT : XFS_CMP_DIFFERENT;
1567}
1568
1569static xfs_dahash_t
1570xfs_default_hashname(
1571	struct xfs_name	*name)
1572{
1573	return xfs_da_hashname(name->name, name->len);
1574}
1575
1576const struct xfs_nameops xfs_default_nameops = {
1577	.hashname	= xfs_default_hashname,
1578	.compname	= xfs_da_compname
1579};
1580
1581int
1582xfs_da_grow_inode_int(
1583	struct xfs_da_args	*args,
1584	xfs_fileoff_t		*bno,
1585	int			count)
1586{
1587	struct xfs_trans	*tp = args->trans;
1588	struct xfs_inode	*dp = args->dp;
1589	int			w = args->whichfork;
1590	xfs_drfsbno_t		nblks = dp->i_d.di_nblocks;
1591	struct xfs_bmbt_irec	map, *mapp;
1592	int			nmap, error, got, i, mapi;
1593
1594	/*
1595	 * Find a spot in the file space to put the new block.
1596	 */
1597	error = xfs_bmap_first_unused(tp, dp, count, bno, w);
1598	if (error)
1599		return error;
1600
1601	/*
1602	 * Try mapping it in one filesystem block.
1603	 */
1604	nmap = 1;
1605	ASSERT(args->firstblock != NULL);
1606	error = xfs_bmapi_write(tp, dp, *bno, count,
1607			xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA|XFS_BMAPI_CONTIG,
1608			args->firstblock, args->total, &map, &nmap,
1609			args->flist);
1610	if (error)
1611		return error;
1612
1613	ASSERT(nmap <= 1);
1614	if (nmap == 1) {
1615		mapp = &map;
1616		mapi = 1;
1617	} else if (nmap == 0 && count > 1) {
1618		xfs_fileoff_t		b;
1619		int			c;
1620
1621		/*
1622		 * If we didn't get it and the block might work if fragmented,
1623		 * try without the CONTIG flag.  Loop until we get it all.
1624		 */
1625		mapp = kmem_alloc(sizeof(*mapp) * count, KM_SLEEP);
1626		for (b = *bno, mapi = 0; b < *bno + count; ) {
1627			nmap = MIN(XFS_BMAP_MAX_NMAP, count);
1628			c = (int)(*bno + count - b);
1629			error = xfs_bmapi_write(tp, dp, b, c,
1630					xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
1631					args->firstblock, args->total,
1632					&mapp[mapi], &nmap, args->flist);
1633			if (error)
1634				goto out_free_map;
1635			if (nmap < 1)
1636				break;
1637			mapi += nmap;
1638			b = mapp[mapi - 1].br_startoff +
1639			    mapp[mapi - 1].br_blockcount;
1640		}
1641	} else {
1642		mapi = 0;
1643		mapp = NULL;
1644	}
1645
1646	/*
1647	 * Count the blocks we got, make sure it matches the total.
1648	 */
1649	for (i = 0, got = 0; i < mapi; i++)
1650		got += mapp[i].br_blockcount;
1651	if (got != count || mapp[0].br_startoff != *bno ||
1652	    mapp[mapi - 1].br_startoff + mapp[mapi - 1].br_blockcount !=
1653	    *bno + count) {
1654		error = XFS_ERROR(ENOSPC);
1655		goto out_free_map;
1656	}
1657
1658	/* account for newly allocated blocks in reserved blocks total */
1659	args->total -= dp->i_d.di_nblocks - nblks;
1660
1661out_free_map:
1662	if (mapp != &map)
1663		kmem_free(mapp);
1664	return error;
1665}
1666
1667/*
1668 * Add a block to the btree ahead of the file.
1669 * Return the new block number to the caller.
1670 */
1671int
1672xfs_da_grow_inode(
1673	struct xfs_da_args	*args,
1674	xfs_dablk_t		*new_blkno)
1675{
1676	xfs_fileoff_t		bno;
1677	int			count;
1678	int			error;
1679
1680	trace_xfs_da_grow_inode(args);
1681
1682	if (args->whichfork == XFS_DATA_FORK) {
1683		bno = args->dp->i_mount->m_dirleafblk;
1684		count = args->dp->i_mount->m_dirblkfsbs;
1685	} else {
1686		bno = 0;
1687		count = 1;
1688	}
1689
1690	error = xfs_da_grow_inode_int(args, &bno, count);
1691	if (!error)
1692		*new_blkno = (xfs_dablk_t)bno;
1693	return error;
1694}
1695
1696/*
1697 * Ick.  We need to always be able to remove a btree block, even
1698 * if there's no space reservation because the filesystem is full.
1699 * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
1700 * It swaps the target block with the last block in the file.  The
1701 * last block in the file can always be removed since it can't cause
1702 * a bmap btree split to do that.
1703 */
1704STATIC int
1705xfs_da_swap_lastblock(xfs_da_args_t *args, xfs_dablk_t *dead_blknop,
1706		      xfs_dabuf_t **dead_bufp)
 
 
1707{
1708	xfs_dablk_t dead_blkno, last_blkno, sib_blkno, par_blkno;
1709	xfs_dabuf_t *dead_buf, *last_buf, *sib_buf, *par_buf;
1710	xfs_fileoff_t lastoff;
1711	xfs_inode_t *ip;
1712	xfs_trans_t *tp;
1713	xfs_mount_t *mp;
1714	int error, w, entno, level, dead_level;
1715	xfs_da_blkinfo_t *dead_info, *sib_info;
1716	xfs_da_intnode_t *par_node, *dead_node;
1717	xfs_dir2_leaf_t *dead_leaf2;
1718	xfs_dahash_t dead_hash;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1719
1720	trace_xfs_da_swap_lastblock(args);
1721
1722	dead_buf = *dead_bufp;
1723	dead_blkno = *dead_blknop;
1724	tp = args->trans;
1725	ip = args->dp;
1726	w = args->whichfork;
1727	ASSERT(w == XFS_DATA_FORK);
1728	mp = ip->i_mount;
1729	lastoff = mp->m_dirfreeblk;
1730	error = xfs_bmap_last_before(tp, ip, &lastoff, w);
1731	if (error)
1732		return error;
1733	if (unlikely(lastoff == 0)) {
1734		XFS_ERROR_REPORT("xfs_da_swap_lastblock(1)", XFS_ERRLEVEL_LOW,
1735				 mp);
1736		return XFS_ERROR(EFSCORRUPTED);
1737	}
1738	/*
1739	 * Read the last block in the btree space.
1740	 */
1741	last_blkno = (xfs_dablk_t)lastoff - mp->m_dirblkfsbs;
1742	if ((error = xfs_da_read_buf(tp, ip, last_blkno, -1, &last_buf, w)))
 
1743		return error;
1744	/*
1745	 * Copy the last block into the dead buffer and log it.
1746	 */
1747	memcpy(dead_buf->data, last_buf->data, mp->m_dirblksize);
1748	xfs_da_log_buf(tp, dead_buf, 0, mp->m_dirblksize - 1);
1749	dead_info = dead_buf->data;
1750	/*
1751	 * Get values from the moved block.
1752	 */
1753	if (dead_info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC)) {
 
 
 
 
1754		dead_leaf2 = (xfs_dir2_leaf_t *)dead_info;
 
 
1755		dead_level = 0;
1756		dead_hash = be32_to_cpu(dead_leaf2->ents[be16_to_cpu(dead_leaf2->hdr.count) - 1].hashval);
1757	} else {
1758		ASSERT(dead_info->magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
 
1759		dead_node = (xfs_da_intnode_t *)dead_info;
1760		dead_level = be16_to_cpu(dead_node->hdr.level);
1761		dead_hash = be32_to_cpu(dead_node->btree[be16_to_cpu(dead_node->hdr.count) - 1].hashval);
 
 
1762	}
1763	sib_buf = par_buf = NULL;
1764	/*
1765	 * If the moved block has a left sibling, fix up the pointers.
1766	 */
1767	if ((sib_blkno = be32_to_cpu(dead_info->back))) {
1768		if ((error = xfs_da_read_buf(tp, ip, sib_blkno, -1, &sib_buf, w)))
 
1769			goto done;
1770		sib_info = sib_buf->data;
1771		if (unlikely(
1772		    be32_to_cpu(sib_info->forw) != last_blkno ||
1773		    sib_info->magic != dead_info->magic)) {
1774			XFS_ERROR_REPORT("xfs_da_swap_lastblock(2)",
1775					 XFS_ERRLEVEL_LOW, mp);
1776			error = XFS_ERROR(EFSCORRUPTED);
1777			goto done;
1778		}
1779		sib_info->forw = cpu_to_be32(dead_blkno);
1780		xfs_da_log_buf(tp, sib_buf,
1781			XFS_DA_LOGRANGE(sib_info, &sib_info->forw,
1782					sizeof(sib_info->forw)));
1783		xfs_da_buf_done(sib_buf);
1784		sib_buf = NULL;
1785	}
1786	/*
1787	 * If the moved block has a right sibling, fix up the pointers.
1788	 */
1789	if ((sib_blkno = be32_to_cpu(dead_info->forw))) {
1790		if ((error = xfs_da_read_buf(tp, ip, sib_blkno, -1, &sib_buf, w)))
 
1791			goto done;
1792		sib_info = sib_buf->data;
1793		if (unlikely(
1794		       be32_to_cpu(sib_info->back) != last_blkno ||
1795		       sib_info->magic != dead_info->magic)) {
1796			XFS_ERROR_REPORT("xfs_da_swap_lastblock(3)",
1797					 XFS_ERRLEVEL_LOW, mp);
1798			error = XFS_ERROR(EFSCORRUPTED);
1799			goto done;
1800		}
1801		sib_info->back = cpu_to_be32(dead_blkno);
1802		xfs_da_log_buf(tp, sib_buf,
1803			XFS_DA_LOGRANGE(sib_info, &sib_info->back,
1804					sizeof(sib_info->back)));
1805		xfs_da_buf_done(sib_buf);
1806		sib_buf = NULL;
1807	}
1808	par_blkno = mp->m_dirleafblk;
1809	level = -1;
1810	/*
1811	 * Walk down the tree looking for the parent of the moved block.
1812	 */
1813	for (;;) {
1814		if ((error = xfs_da_read_buf(tp, ip, par_blkno, -1, &par_buf, w)))
 
1815			goto done;
1816		par_node = par_buf->data;
1817		if (unlikely(par_node->hdr.info.magic !=
1818		    cpu_to_be16(XFS_DA_NODE_MAGIC) ||
1819		    (level >= 0 && level != be16_to_cpu(par_node->hdr.level) + 1))) {
1820			XFS_ERROR_REPORT("xfs_da_swap_lastblock(4)",
1821					 XFS_ERRLEVEL_LOW, mp);
1822			error = XFS_ERROR(EFSCORRUPTED);
1823			goto done;
1824		}
1825		level = be16_to_cpu(par_node->hdr.level);
 
1826		for (entno = 0;
1827		     entno < be16_to_cpu(par_node->hdr.count) &&
1828		     be32_to_cpu(par_node->btree[entno].hashval) < dead_hash;
1829		     entno++)
1830			continue;
1831		if (unlikely(entno == be16_to_cpu(par_node->hdr.count))) {
1832			XFS_ERROR_REPORT("xfs_da_swap_lastblock(5)",
1833					 XFS_ERRLEVEL_LOW, mp);
1834			error = XFS_ERROR(EFSCORRUPTED);
1835			goto done;
1836		}
1837		par_blkno = be32_to_cpu(par_node->btree[entno].before);
1838		if (level == dead_level + 1)
1839			break;
1840		xfs_da_brelse(tp, par_buf);
1841		par_buf = NULL;
1842	}
1843	/*
1844	 * We're in the right parent block.
1845	 * Look for the right entry.
1846	 */
1847	for (;;) {
1848		for (;
1849		     entno < be16_to_cpu(par_node->hdr.count) &&
1850		     be32_to_cpu(par_node->btree[entno].before) != last_blkno;
1851		     entno++)
1852			continue;
1853		if (entno < be16_to_cpu(par_node->hdr.count))
1854			break;
1855		par_blkno = be32_to_cpu(par_node->hdr.info.forw);
1856		xfs_da_brelse(tp, par_buf);
1857		par_buf = NULL;
1858		if (unlikely(par_blkno == 0)) {
1859			XFS_ERROR_REPORT("xfs_da_swap_lastblock(6)",
1860					 XFS_ERRLEVEL_LOW, mp);
1861			error = XFS_ERROR(EFSCORRUPTED);
1862			goto done;
1863		}
1864		if ((error = xfs_da_read_buf(tp, ip, par_blkno, -1, &par_buf, w)))
 
1865			goto done;
1866		par_node = par_buf->data;
1867		if (unlikely(
1868		    be16_to_cpu(par_node->hdr.level) != level ||
1869		    par_node->hdr.info.magic != cpu_to_be16(XFS_DA_NODE_MAGIC))) {
1870			XFS_ERROR_REPORT("xfs_da_swap_lastblock(7)",
1871					 XFS_ERRLEVEL_LOW, mp);
1872			error = XFS_ERROR(EFSCORRUPTED);
1873			goto done;
1874		}
 
1875		entno = 0;
1876	}
1877	/*
1878	 * Update the parent entry pointing to the moved block.
1879	 */
1880	par_node->btree[entno].before = cpu_to_be32(dead_blkno);
1881	xfs_da_log_buf(tp, par_buf,
1882		XFS_DA_LOGRANGE(par_node, &par_node->btree[entno].before,
1883				sizeof(par_node->btree[entno].before)));
1884	xfs_da_buf_done(par_buf);
1885	xfs_da_buf_done(dead_buf);
1886	*dead_blknop = last_blkno;
1887	*dead_bufp = last_buf;
1888	return 0;
1889done:
1890	if (par_buf)
1891		xfs_da_brelse(tp, par_buf);
1892	if (sib_buf)
1893		xfs_da_brelse(tp, sib_buf);
1894	xfs_da_brelse(tp, last_buf);
1895	return error;
1896}
1897
1898/*
1899 * Remove a btree block from a directory or attribute.
1900 */
1901int
1902xfs_da_shrink_inode(xfs_da_args_t *args, xfs_dablk_t dead_blkno,
1903		    xfs_dabuf_t *dead_buf)
 
 
1904{
1905	xfs_inode_t *dp;
1906	int done, error, w, count;
1907	xfs_trans_t *tp;
1908	xfs_mount_t *mp;
1909
1910	trace_xfs_da_shrink_inode(args);
1911
1912	dp = args->dp;
1913	w = args->whichfork;
1914	tp = args->trans;
1915	mp = dp->i_mount;
1916	if (w == XFS_DATA_FORK)
1917		count = mp->m_dirblkfsbs;
1918	else
1919		count = 1;
1920	for (;;) {
1921		/*
1922		 * Remove extents.  If we get ENOSPC for a dir we have to move
1923		 * the last block to the place we want to kill.
1924		 */
1925		if ((error = xfs_bunmapi(tp, dp, dead_blkno, count,
1926				xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
1927				0, args->firstblock, args->flist,
1928				&done)) == ENOSPC) {
1929			if (w != XFS_DATA_FORK)
1930				break;
1931			if ((error = xfs_da_swap_lastblock(args, &dead_blkno,
1932					&dead_buf)))
 
1933				break;
1934		} else {
1935			break;
1936		}
1937	}
1938	xfs_da_binval(tp, dead_buf);
1939	return error;
1940}
1941
1942/*
1943 * See if the mapping(s) for this btree block are valid, i.e.
1944 * don't contain holes, are logically contiguous, and cover the whole range.
1945 */
1946STATIC int
1947xfs_da_map_covers_blocks(
1948	int		nmap,
1949	xfs_bmbt_irec_t	*mapp,
1950	xfs_dablk_t	bno,
1951	int		count)
1952{
1953	int		i;
1954	xfs_fileoff_t	off;
1955
1956	for (i = 0, off = bno; i < nmap; i++) {
1957		if (mapp[i].br_startblock == HOLESTARTBLOCK ||
1958		    mapp[i].br_startblock == DELAYSTARTBLOCK) {
1959			return 0;
1960		}
1961		if (off != mapp[i].br_startoff) {
1962			return 0;
1963		}
1964		off += mapp[i].br_blockcount;
1965	}
1966	return off == bno + count;
1967}
1968
1969/*
1970 * Make a dabuf.
1971 * Used for get_buf, read_buf, read_bufr, and reada_buf.
1972 */
1973STATIC int
1974xfs_da_do_buf(
1975	xfs_trans_t	*trans,
1976	xfs_inode_t	*dp,
1977	xfs_dablk_t	bno,
1978	xfs_daddr_t	*mappedbnop,
1979	xfs_dabuf_t	**bpp,
1980	int		whichfork,
1981	int		caller)
1982{
1983	xfs_buf_t	*bp = NULL;
1984	xfs_buf_t	**bplist;
1985	int		error=0;
1986	int		i;
1987	xfs_bmbt_irec_t	map;
1988	xfs_bmbt_irec_t	*mapp;
1989	xfs_daddr_t	mappedbno;
1990	xfs_mount_t	*mp;
1991	int		nbplist=0;
1992	int		nfsb;
1993	int		nmap;
1994	xfs_dabuf_t	*rbp;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1995
1996	mp = dp->i_mount;
1997	nfsb = (whichfork == XFS_DATA_FORK) ? mp->m_dirblkfsbs : 1;
1998	mappedbno = *mappedbnop;
1999	/*
2000	 * Caller doesn't have a mapping.  -2 means don't complain
2001	 * if we land in a hole.
2002	 */
2003	if (mappedbno == -1 || mappedbno == -2) {
2004		/*
2005		 * Optimize the one-block case.
2006		 */
2007		if (nfsb == 1)
2008			mapp = &map;
2009		else
2010			mapp = kmem_alloc(sizeof(*mapp) * nfsb, KM_SLEEP);
2011
2012		nmap = nfsb;
2013		error = xfs_bmapi_read(dp, (xfs_fileoff_t)bno, nfsb, mapp,
2014				       &nmap, xfs_bmapi_aflag(whichfork));
2015		if (error)
2016			goto exit0;
2017	} else {
2018		map.br_startblock = XFS_DADDR_TO_FSB(mp, mappedbno);
2019		map.br_startoff = (xfs_fileoff_t)bno;
2020		map.br_blockcount = nfsb;
2021		mapp = &map;
2022		nmap = 1;
2023	}
2024	if (!xfs_da_map_covers_blocks(nmap, mapp, bno, nfsb)) {
2025		error = mappedbno == -2 ? 0 : XFS_ERROR(EFSCORRUPTED);
 
2026		if (unlikely(error == EFSCORRUPTED)) {
2027			if (xfs_error_level >= XFS_ERRLEVEL_LOW) {
 
2028				xfs_alert(mp, "%s: bno %lld dir: inode %lld",
2029					__func__, (long long)bno,
2030					(long long)dp->i_ino);
2031				for (i = 0; i < nmap; i++) {
2032					xfs_alert(mp,
2033"[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d",
2034						i,
2035						(long long)mapp[i].br_startoff,
2036						(long long)mapp[i].br_startblock,
2037						(long long)mapp[i].br_blockcount,
2038						mapp[i].br_state);
2039				}
2040			}
2041			XFS_ERROR_REPORT("xfs_da_do_buf(1)",
2042					 XFS_ERRLEVEL_LOW, mp);
2043		}
2044		goto exit0;
2045	}
2046	if (caller != 3 && nmap > 1) {
2047		bplist = kmem_alloc(sizeof(*bplist) * nmap, KM_SLEEP);
2048		nbplist = 0;
2049	} else
2050		bplist = NULL;
2051	/*
2052	 * Turn the mapping(s) into buffer(s).
2053	 */
2054	for (i = 0; i < nmap; i++) {
2055		int	nmapped;
2056
2057		mappedbno = XFS_FSB_TO_DADDR(mp, mapp[i].br_startblock);
2058		if (i == 0)
2059			*mappedbnop = mappedbno;
2060		nmapped = (int)XFS_FSB_TO_BB(mp, mapp[i].br_blockcount);
2061		switch (caller) {
2062		case 0:
2063			bp = xfs_trans_get_buf(trans, mp->m_ddev_targp,
2064				mappedbno, nmapped, 0);
2065			error = bp ? bp->b_error : XFS_ERROR(EIO);
2066			break;
2067		case 1:
2068		case 2:
2069			bp = NULL;
2070			error = xfs_trans_read_buf(mp, trans, mp->m_ddev_targp,
2071				mappedbno, nmapped, 0, &bp);
2072			break;
2073		case 3:
2074			xfs_buf_readahead(mp->m_ddev_targp, mappedbno, nmapped);
2075			error = 0;
2076			bp = NULL;
2077			break;
2078		}
2079		if (error) {
2080			if (bp)
2081				xfs_trans_brelse(trans, bp);
2082			goto exit1;
2083		}
2084		if (!bp)
2085			continue;
2086		if (caller == 1) {
2087			if (whichfork == XFS_ATTR_FORK)
2088				xfs_buf_set_ref(bp, XFS_ATTR_BTREE_REF);
2089			else
2090				xfs_buf_set_ref(bp, XFS_DIR_BTREE_REF);
2091		}
2092		if (bplist) {
2093			bplist[nbplist++] = bp;
2094		}
2095	}
2096	/*
2097	 * Build a dabuf structure.
2098	 */
2099	if (bplist) {
2100		rbp = xfs_da_buf_make(nbplist, bplist);
2101	} else if (bp)
2102		rbp = xfs_da_buf_make(1, &bp);
2103	else
2104		rbp = NULL;
2105	/*
2106	 * For read_buf, check the magic number.
2107	 */
2108	if (caller == 1) {
2109		xfs_dir2_data_hdr_t	*hdr = rbp->data;
2110		xfs_dir2_free_t		*free = rbp->data;
2111		xfs_da_blkinfo_t	*info = rbp->data;
2112		uint			magic, magic1;
2113
2114		magic = be16_to_cpu(info->magic);
2115		magic1 = be32_to_cpu(hdr->magic);
2116		if (unlikely(
2117		    XFS_TEST_ERROR((magic != XFS_DA_NODE_MAGIC) &&
2118				   (magic != XFS_ATTR_LEAF_MAGIC) &&
2119				   (magic != XFS_DIR2_LEAF1_MAGIC) &&
2120				   (magic != XFS_DIR2_LEAFN_MAGIC) &&
2121				   (magic1 != XFS_DIR2_BLOCK_MAGIC) &&
2122				   (magic1 != XFS_DIR2_DATA_MAGIC) &&
2123				   (free->hdr.magic != cpu_to_be32(XFS_DIR2_FREE_MAGIC)),
2124				mp, XFS_ERRTAG_DA_READ_BUF,
2125				XFS_RANDOM_DA_READ_BUF))) {
2126			trace_xfs_da_btree_corrupt(rbp->bps[0], _RET_IP_);
2127			XFS_CORRUPTION_ERROR("xfs_da_do_buf(2)",
2128					     XFS_ERRLEVEL_LOW, mp, info);
2129			error = XFS_ERROR(EFSCORRUPTED);
2130			xfs_da_brelse(trans, rbp);
2131			nbplist = 0;
2132			goto exit1;
2133		}
2134	}
2135	if (bplist) {
2136		kmem_free(bplist);
2137	}
2138	if (mapp != &map) {
2139		kmem_free(mapp);
2140	}
2141	if (bpp)
2142		*bpp = rbp;
2143	return 0;
2144exit1:
2145	if (bplist) {
2146		for (i = 0; i < nbplist; i++)
2147			xfs_trans_brelse(trans, bplist[i]);
2148		kmem_free(bplist);
2149	}
2150exit0:
2151	if (mapp != &map)
2152		kmem_free(mapp);
2153	if (bpp)
2154		*bpp = NULL;
2155	return error;
2156}
2157
2158/*
2159 * Get a buffer for the dir/attr block.
2160 */
2161int
2162xfs_da_get_buf(
2163	xfs_trans_t	*trans,
2164	xfs_inode_t	*dp,
2165	xfs_dablk_t	bno,
2166	xfs_daddr_t		mappedbno,
2167	xfs_dabuf_t	**bpp,
2168	int		whichfork)
2169{
2170	return xfs_da_do_buf(trans, dp, bno, &mappedbno, bpp, whichfork, 0);
2171}
2172
2173/*
2174 * Get a buffer for the dir/attr block, fill in the contents.
2175 */
2176int
2177xfs_da_read_buf(
2178	xfs_trans_t	*trans,
2179	xfs_inode_t	*dp,
2180	xfs_dablk_t	bno,
2181	xfs_daddr_t		mappedbno,
2182	xfs_dabuf_t	**bpp,
2183	int		whichfork)
2184{
2185	return xfs_da_do_buf(trans, dp, bno, &mappedbno, bpp, whichfork, 1);
2186}
2187
2188/*
2189 * Readahead the dir/attr block.
2190 */
2191xfs_daddr_t
2192xfs_da_reada_buf(
2193	xfs_trans_t	*trans,
2194	xfs_inode_t	*dp,
2195	xfs_dablk_t	bno,
2196	int		whichfork)
2197{
2198	xfs_daddr_t		rval;
2199
2200	rval = -1;
2201	if (xfs_da_do_buf(trans, dp, bno, &rval, NULL, whichfork, 3))
2202		return -1;
2203	else
2204		return rval;
2205}
 
 
 
 
 
2206
2207kmem_zone_t *xfs_da_state_zone;	/* anchor for state struct zone */
2208kmem_zone_t *xfs_dabuf_zone;		/* dabuf zone */
 
 
 
 
 
2209
2210/*
2211 * Allocate a dir-state structure.
2212 * We don't put them on the stack since they're large.
2213 */
2214xfs_da_state_t *
2215xfs_da_state_alloc(void)
2216{
2217	return kmem_zone_zalloc(xfs_da_state_zone, KM_NOFS);
2218}
2219
2220/*
2221 * Kill the altpath contents of a da-state structure.
2222 */
2223STATIC void
2224xfs_da_state_kill_altpath(xfs_da_state_t *state)
2225{
2226	int	i;
2227
2228	for (i = 0; i < state->altpath.active; i++) {
2229		if (state->altpath.blk[i].bp) {
2230			if (state->altpath.blk[i].bp != state->path.blk[i].bp)
2231				xfs_da_buf_done(state->altpath.blk[i].bp);
2232			state->altpath.blk[i].bp = NULL;
2233		}
2234	}
2235	state->altpath.active = 0;
2236}
2237
2238/*
2239 * Free a da-state structure.
2240 */
2241void
2242xfs_da_state_free(xfs_da_state_t *state)
2243{
2244	int	i;
 
 
 
 
 
 
 
 
 
 
 
2245
2246	xfs_da_state_kill_altpath(state);
2247	for (i = 0; i < state->path.active; i++) {
2248		if (state->path.blk[i].bp)
2249			xfs_da_buf_done(state->path.blk[i].bp);
 
 
 
 
 
 
2250	}
2251	if (state->extravalid && state->extrablk.bp)
2252		xfs_da_buf_done(state->extrablk.bp);
2253#ifdef DEBUG
2254	memset((char *)state, 0, sizeof(*state));
2255#endif /* DEBUG */
2256	kmem_zone_free(xfs_da_state_zone, state);
2257}
2258
2259/*
2260 * Create a dabuf.
2261 */
2262/* ARGSUSED */
2263STATIC xfs_dabuf_t *
2264xfs_da_buf_make(int nbuf, xfs_buf_t **bps)
2265{
2266	xfs_buf_t	*bp;
2267	xfs_dabuf_t	*dabuf;
2268	int		i;
2269	int		off;
2270
2271	if (nbuf == 1)
2272		dabuf = kmem_zone_alloc(xfs_dabuf_zone, KM_NOFS);
2273	else
2274		dabuf = kmem_alloc(XFS_DA_BUF_SIZE(nbuf), KM_NOFS);
2275	dabuf->dirty = 0;
2276	if (nbuf == 1) {
2277		dabuf->nbuf = 1;
2278		bp = bps[0];
2279		dabuf->bbcount = bp->b_length;
2280		dabuf->data = bp->b_addr;
2281		dabuf->bps[0] = bp;
2282	} else {
2283		dabuf->nbuf = nbuf;
2284		for (i = 0, dabuf->bbcount = 0; i < nbuf; i++) {
2285			dabuf->bps[i] = bp = bps[i];
2286			dabuf->bbcount += bp->b_length;
2287		}
2288		dabuf->data = kmem_alloc(BBTOB(dabuf->bbcount), KM_SLEEP);
2289		for (i = off = 0; i < nbuf; i++, off += BBTOB(bp->b_length)) {
2290			bp = bps[i];
2291			memcpy((char *)dabuf->data + off, bp->b_addr,
2292				BBTOB(bp->b_length));
2293		}
2294	}
2295	return dabuf;
2296}
2297
2298/*
2299 * Un-dirty a dabuf.
2300 */
2301STATIC void
2302xfs_da_buf_clean(xfs_dabuf_t *dabuf)
2303{
2304	xfs_buf_t	*bp;
2305	int		i;
2306	int		off;
 
2307
2308	if (dabuf->dirty) {
2309		ASSERT(dabuf->nbuf > 1);
2310		dabuf->dirty = 0;
2311		for (i = off = 0; i < dabuf->nbuf;
2312				i++, off += BBTOB(bp->b_length)) {
2313			bp = dabuf->bps[i];
2314			memcpy(bp->b_addr, dabuf->data + off,
2315						BBTOB(bp->b_length));
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2316		}
2317	}
2318}
2319
2320/*
2321 * Release a dabuf.
2322 */
2323void
2324xfs_da_buf_done(xfs_dabuf_t *dabuf)
2325{
2326	ASSERT(dabuf);
2327	ASSERT(dabuf->nbuf && dabuf->data && dabuf->bbcount && dabuf->bps[0]);
2328	if (dabuf->dirty)
2329		xfs_da_buf_clean(dabuf);
2330	if (dabuf->nbuf > 1) {
2331		kmem_free(dabuf->data);
2332		kmem_free(dabuf);
2333	} else {
2334		kmem_zone_free(xfs_dabuf_zone, dabuf);
2335	}
2336}
2337
2338/*
2339 * Log transaction from a dabuf.
2340 */
2341void
2342xfs_da_log_buf(xfs_trans_t *tp, xfs_dabuf_t *dabuf, uint first, uint last)
2343{
2344	xfs_buf_t	*bp;
2345	uint		f;
2346	int		i;
2347	uint		l;
2348	int		off;
2349
2350	ASSERT(dabuf->nbuf && dabuf->data && dabuf->bbcount && dabuf->bps[0]);
2351	if (dabuf->nbuf == 1) {
2352		ASSERT(dabuf->data == dabuf->bps[0]->b_addr);
2353		xfs_trans_log_buf(tp, dabuf->bps[0], first, last);
2354		return;
2355	}
2356	dabuf->dirty = 1;
2357	ASSERT(first <= last);
2358	for (i = off = 0; i < dabuf->nbuf; i++, off += BBTOB(bp->b_length)) {
2359		bp = dabuf->bps[i];
2360		f = off;
2361		l = f + BBTOB(bp->b_length) - 1;
2362		if (f < first)
2363			f = first;
2364		if (l > last)
2365			l = last;
2366		if (f <= l)
2367			xfs_trans_log_buf(tp, bp, f - off, l - off);
2368		/*
2369		 * B_DONE is set by xfs_trans_log buf.
2370		 * If we don't set it on a new buffer (get not read)
2371		 * then if we don't put anything in the buffer it won't
2372		 * be set, and at commit it it released into the cache,
2373		 * and then a read will fail.
2374		 */
2375		else if (!(XFS_BUF_ISDONE(bp)))
2376		  XFS_BUF_DONE(bp);
2377	}
2378	ASSERT(last < off);
2379}
2380
2381/*
2382 * Release dabuf from a transaction.
2383 * Have to free up the dabuf before the buffers are released,
2384 * since the synchronization on the dabuf is really the lock on the buffer.
2385 */
2386void
2387xfs_da_brelse(xfs_trans_t *tp, xfs_dabuf_t *dabuf)
 
 
 
 
 
 
2388{
2389	xfs_buf_t	*bp;
2390	xfs_buf_t	**bplist;
2391	int		i;
2392	int		nbuf;
2393
2394	ASSERT(dabuf->nbuf && dabuf->data && dabuf->bbcount && dabuf->bps[0]);
2395	if ((nbuf = dabuf->nbuf) == 1) {
2396		bplist = &bp;
2397		bp = dabuf->bps[0];
2398	} else {
2399		bplist = kmem_alloc(nbuf * sizeof(*bplist), KM_SLEEP);
2400		memcpy(bplist, dabuf->bps, nbuf * sizeof(*bplist));
 
 
2401	}
2402	xfs_da_buf_done(dabuf);
2403	for (i = 0; i < nbuf; i++)
2404		xfs_trans_brelse(tp, bplist[i]);
2405	if (bplist != &bp)
2406		kmem_free(bplist);
2407}
2408
2409/*
2410 * Invalidate dabuf from a transaction.
2411 */
2412void
2413xfs_da_binval(xfs_trans_t *tp, xfs_dabuf_t *dabuf)
2414{
2415	xfs_buf_t	*bp;
2416	xfs_buf_t	**bplist;
2417	int		i;
2418	int		nbuf;
2419
2420	ASSERT(dabuf->nbuf && dabuf->data && dabuf->bbcount && dabuf->bps[0]);
2421	if ((nbuf = dabuf->nbuf) == 1) {
2422		bplist = &bp;
2423		bp = dabuf->bps[0];
2424	} else {
2425		bplist = kmem_alloc(nbuf * sizeof(*bplist), KM_SLEEP);
2426		memcpy(bplist, dabuf->bps, nbuf * sizeof(*bplist));
2427	}
2428	xfs_da_buf_done(dabuf);
2429	for (i = 0; i < nbuf; i++)
2430		xfs_trans_binval(tp, bplist[i]);
2431	if (bplist != &bp)
2432		kmem_free(bplist);
2433}
2434
2435/*
2436 * Get the first daddr from a dabuf.
2437 */
2438xfs_daddr_t
2439xfs_da_blkno(xfs_dabuf_t *dabuf)
2440{
2441	ASSERT(dabuf->nbuf);
2442	ASSERT(dabuf->data);
2443	return XFS_BUF_ADDR(dabuf->bps[0]);
2444}