1/*
   2 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
   3 * Copyright (c) 2013 Red Hat, Inc.
   4 * All Rights Reserved.
   5 *
   6 * This program is free software; you can redistribute it and/or
   7 * modify it under the terms of the GNU General Public License as
   8 * published by the Free Software Foundation.
   9 *
  10 * This program is distributed in the hope that it would be useful,
  11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 * GNU General Public License for more details.
  14 *
  15 * You should have received a copy of the GNU General Public License
  16 * along with this program; if not, write the Free Software Foundation,
  17 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  18 */
  19#include "xfs.h"
  20#include "xfs_fs.h"
  21#include "xfs_format.h"
  22#include "xfs_log_format.h"
  23#include "xfs_trans_resv.h"
  24#include "xfs_mount.h"
  25#include "xfs_da_format.h"
  26#include "xfs_da_btree.h"
  27#include "xfs_inode.h"
  28#include "xfs_bmap.h"
  29#include "xfs_dir2.h"
  30#include "xfs_dir2_priv.h"
  31#include "xfs_error.h"
  32#include "xfs_trace.h"
  33#include "xfs_trans.h"
  34#include "xfs_buf_item.h"
  35#include "xfs_cksum.h"
  36#include "xfs_log.h"
  37
  38/*
  39 * Function declarations.
  40 */
  41static int xfs_dir2_leafn_add(struct xfs_buf *bp, xfs_da_args_t *args,
  42			      int index);
  43static void xfs_dir2_leafn_rebalance(xfs_da_state_t *state,
  44				     xfs_da_state_blk_t *blk1,
  45				     xfs_da_state_blk_t *blk2);
  46static int xfs_dir2_leafn_remove(xfs_da_args_t *args, struct xfs_buf *bp,
  47				 int index, xfs_da_state_blk_t *dblk,
  48				 int *rval);
  49static int xfs_dir2_node_addname_int(xfs_da_args_t *args,
  50				     xfs_da_state_blk_t *fblk);
  51
  52/*
  53 * Check internal consistency of a leafn block.
  54 */
  55#ifdef DEBUG
  56static xfs_failaddr_t
 
 
 
 
 
 
  57xfs_dir3_leafn_check(
  58	struct xfs_inode	*dp,
  59	struct xfs_buf		*bp)
  60{
  61	struct xfs_dir2_leaf	*leaf = bp->b_addr;
  62	struct xfs_dir3_icleaf_hdr leafhdr;
  63
  64	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  65
  66	if (leafhdr.magic == XFS_DIR3_LEAFN_MAGIC) {
  67		struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
  68		if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn)
  69			return __this_address;
  70	} else if (leafhdr.magic != XFS_DIR2_LEAFN_MAGIC)
  71		return __this_address;
  72
  73	return xfs_dir3_leaf_check_int(dp->i_mount, dp, &leafhdr, leaf);
  74}
  75
  76static inline void
  77xfs_dir3_leaf_check(
  78	struct xfs_inode	*dp,
  79	struct xfs_buf		*bp)
  80{
  81	xfs_failaddr_t		fa;
  82
  83	fa = xfs_dir3_leafn_check(dp, bp);
  84	if (!fa)
  85		return;
  86	xfs_corruption_error(__func__, XFS_ERRLEVEL_LOW, dp->i_mount,
  87			bp->b_addr, __FILE__, __LINE__, fa);
  88	ASSERT(0);
  89}
  90#else
  91#define	xfs_dir3_leaf_check(dp, bp)
  92#endif
  93
  94static xfs_failaddr_t
  95xfs_dir3_free_verify(
  96	struct xfs_buf		*bp)
  97{
  98	struct xfs_mount	*mp = bp->b_target->bt_mount;
  99	struct xfs_dir2_free_hdr *hdr = bp->b_addr;
 100
 101	if (xfs_sb_version_hascrc(&mp->m_sb)) {
 102		struct xfs_dir3_blk_hdr *hdr3 = bp->b_addr;
 103
 104		if (hdr3->magic != cpu_to_be32(XFS_DIR3_FREE_MAGIC))
 105			return __this_address;
 106		if (!uuid_equal(&hdr3->uuid, &mp->m_sb.sb_meta_uuid))
 107			return __this_address;
 108		if (be64_to_cpu(hdr3->blkno) != bp->b_bn)
 109			return __this_address;
 110		if (!xfs_log_check_lsn(mp, be64_to_cpu(hdr3->lsn)))
 111			return __this_address;
 112	} else {
 113		if (hdr->magic != cpu_to_be32(XFS_DIR2_FREE_MAGIC))
 114			return __this_address;
 115	}
 116
 117	/* XXX: should bounds check the xfs_dir3_icfree_hdr here */
 118
 119	return NULL;
 120}
 121
 122static void
 123xfs_dir3_free_read_verify(
 124	struct xfs_buf	*bp)
 125{
 126	struct xfs_mount	*mp = bp->b_target->bt_mount;
 127	xfs_failaddr_t		fa;
 128
 129	if (xfs_sb_version_hascrc(&mp->m_sb) &&
 130	    !xfs_buf_verify_cksum(bp, XFS_DIR3_FREE_CRC_OFF))
 131		xfs_verifier_error(bp, -EFSBADCRC, __this_address);
 132	else {
 133		fa = xfs_dir3_free_verify(bp);
 134		if (fa)
 135			xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 136	}
 137}
 138
 139static void
 140xfs_dir3_free_write_verify(
 141	struct xfs_buf	*bp)
 142{
 143	struct xfs_mount	*mp = bp->b_target->bt_mount;
 144	struct xfs_buf_log_item	*bip = bp->b_log_item;
 145	struct xfs_dir3_blk_hdr	*hdr3 = bp->b_addr;
 146	xfs_failaddr_t		fa;
 147
 148	fa = xfs_dir3_free_verify(bp);
 149	if (fa) {
 150		xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 151		return;
 152	}
 153
 154	if (!xfs_sb_version_hascrc(&mp->m_sb))
 155		return;
 156
 157	if (bip)
 158		hdr3->lsn = cpu_to_be64(bip->bli_item.li_lsn);
 159
 160	xfs_buf_update_cksum(bp, XFS_DIR3_FREE_CRC_OFF);
 161}
 162
 163const struct xfs_buf_ops xfs_dir3_free_buf_ops = {
 164	.name = "xfs_dir3_free",
 165	.verify_read = xfs_dir3_free_read_verify,
 166	.verify_write = xfs_dir3_free_write_verify,
 167	.verify_struct = xfs_dir3_free_verify,
 168};
 169
 170/* Everything ok in the free block header? */
 171static xfs_failaddr_t
 172xfs_dir3_free_header_check(
 173	struct xfs_inode	*dp,
 174	xfs_dablk_t		fbno,
 175	struct xfs_buf		*bp)
 176{
 177	struct xfs_mount	*mp = dp->i_mount;
 178	unsigned int		firstdb;
 179	int			maxbests;
 180
 181	maxbests = dp->d_ops->free_max_bests(mp->m_dir_geo);
 182	firstdb = (xfs_dir2_da_to_db(mp->m_dir_geo, fbno) -
 183		   xfs_dir2_byte_to_db(mp->m_dir_geo, XFS_DIR2_FREE_OFFSET)) *
 184			maxbests;
 185	if (xfs_sb_version_hascrc(&mp->m_sb)) {
 186		struct xfs_dir3_free_hdr *hdr3 = bp->b_addr;
 187
 188		if (be32_to_cpu(hdr3->firstdb) != firstdb)
 189			return __this_address;
 190		if (be32_to_cpu(hdr3->nvalid) > maxbests)
 191			return __this_address;
 192		if (be32_to_cpu(hdr3->nvalid) < be32_to_cpu(hdr3->nused))
 193			return __this_address;
 194	} else {
 195		struct xfs_dir2_free_hdr *hdr = bp->b_addr;
 196
 197		if (be32_to_cpu(hdr->firstdb) != firstdb)
 198			return __this_address;
 199		if (be32_to_cpu(hdr->nvalid) > maxbests)
 200			return __this_address;
 201		if (be32_to_cpu(hdr->nvalid) < be32_to_cpu(hdr->nused))
 202			return __this_address;
 203	}
 204	return NULL;
 205}
 206
 207static int
 208__xfs_dir3_free_read(
 209	struct xfs_trans	*tp,
 210	struct xfs_inode	*dp,
 211	xfs_dablk_t		fbno,
 212	xfs_daddr_t		mappedbno,
 213	struct xfs_buf		**bpp)
 214{
 215	xfs_failaddr_t		fa;
 216	int			err;
 217
 218	err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
 219				XFS_DATA_FORK, &xfs_dir3_free_buf_ops);
 220	if (err || !*bpp)
 221		return err;
 222
 223	/* Check things that we can't do in the verifier. */
 224	fa = xfs_dir3_free_header_check(dp, fbno, *bpp);
 225	if (fa) {
 226		xfs_verifier_error(*bpp, -EFSCORRUPTED, fa);
 227		xfs_trans_brelse(tp, *bpp);
 228		return -EFSCORRUPTED;
 229	}
 230
 231	/* try read returns without an error or *bpp if it lands in a hole */
 232	if (tp)
 233		xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_FREE_BUF);
 234
 235	return 0;
 236}
 237
 238int
 239xfs_dir2_free_read(
 240	struct xfs_trans	*tp,
 241	struct xfs_inode	*dp,
 242	xfs_dablk_t		fbno,
 243	struct xfs_buf		**bpp)
 244{
 245	return __xfs_dir3_free_read(tp, dp, fbno, -1, bpp);
 246}
 247
 248static int
 249xfs_dir2_free_try_read(
 250	struct xfs_trans	*tp,
 251	struct xfs_inode	*dp,
 252	xfs_dablk_t		fbno,
 253	struct xfs_buf		**bpp)
 254{
 255	return __xfs_dir3_free_read(tp, dp, fbno, -2, bpp);
 256}
 257
 258static int
 259xfs_dir3_free_get_buf(
 260	xfs_da_args_t		*args,
 261	xfs_dir2_db_t		fbno,
 262	struct xfs_buf		**bpp)
 263{
 264	struct xfs_trans	*tp = args->trans;
 265	struct xfs_inode	*dp = args->dp;
 266	struct xfs_mount	*mp = dp->i_mount;
 267	struct xfs_buf		*bp;
 268	int			error;
 269	struct xfs_dir3_icfree_hdr hdr;
 270
 271	error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(args->geo, fbno),
 272				   -1, &bp, XFS_DATA_FORK);
 273	if (error)
 274		return error;
 275
 276	xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_FREE_BUF);
 277	bp->b_ops = &xfs_dir3_free_buf_ops;
 278
 279	/*
 280	 * Initialize the new block to be empty, and remember
 281	 * its first slot as our empty slot.
 282	 */
 283	memset(bp->b_addr, 0, sizeof(struct xfs_dir3_free_hdr));
 284	memset(&hdr, 0, sizeof(hdr));
 285
 286	if (xfs_sb_version_hascrc(&mp->m_sb)) {
 287		struct xfs_dir3_free_hdr *hdr3 = bp->b_addr;
 288
 289		hdr.magic = XFS_DIR3_FREE_MAGIC;
 290
 291		hdr3->hdr.blkno = cpu_to_be64(bp->b_bn);
 292		hdr3->hdr.owner = cpu_to_be64(dp->i_ino);
 293		uuid_copy(&hdr3->hdr.uuid, &mp->m_sb.sb_meta_uuid);
 294	} else
 295		hdr.magic = XFS_DIR2_FREE_MAGIC;
 296	dp->d_ops->free_hdr_to_disk(bp->b_addr, &hdr);
 297	*bpp = bp;
 298	return 0;
 299}
 300
 301/*
 302 * Log entries from a freespace block.
 303 */
 304STATIC void
 305xfs_dir2_free_log_bests(
 306	struct xfs_da_args	*args,
 307	struct xfs_buf		*bp,
 308	int			first,		/* first entry to log */
 309	int			last)		/* last entry to log */
 310{
 311	xfs_dir2_free_t		*free;		/* freespace structure */
 312	__be16			*bests;
 313
 314	free = bp->b_addr;
 315	bests = args->dp->d_ops->free_bests_p(free);
 316	ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC) ||
 317	       free->hdr.magic == cpu_to_be32(XFS_DIR3_FREE_MAGIC));
 318	xfs_trans_log_buf(args->trans, bp,
 319		(uint)((char *)&bests[first] - (char *)free),
 320		(uint)((char *)&bests[last] - (char *)free +
 321		       sizeof(bests[0]) - 1));
 322}
 323
 324/*
 325 * Log header from a freespace block.
 326 */
 327static void
 328xfs_dir2_free_log_header(
 329	struct xfs_da_args	*args,
 330	struct xfs_buf		*bp)
 331{
 332#ifdef DEBUG
 333	xfs_dir2_free_t		*free;		/* freespace structure */
 334
 335	free = bp->b_addr;
 336	ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC) ||
 337	       free->hdr.magic == cpu_to_be32(XFS_DIR3_FREE_MAGIC));
 338#endif
 339	xfs_trans_log_buf(args->trans, bp, 0,
 340			  args->dp->d_ops->free_hdr_size - 1);
 341}
 342
 343/*
 344 * Convert a leaf-format directory to a node-format directory.
 345 * We need to change the magic number of the leaf block, and copy
 346 * the freespace table out of the leaf block into its own block.
 347 */
 348int						/* error */
 349xfs_dir2_leaf_to_node(
 350	xfs_da_args_t		*args,		/* operation arguments */
 351	struct xfs_buf		*lbp)		/* leaf buffer */
 352{
 353	xfs_inode_t		*dp;		/* incore directory inode */
 354	int			error;		/* error return value */
 355	struct xfs_buf		*fbp;		/* freespace buffer */
 356	xfs_dir2_db_t		fdb;		/* freespace block number */
 357	xfs_dir2_free_t		*free;		/* freespace structure */
 358	__be16			*from;		/* pointer to freespace entry */
 359	int			i;		/* leaf freespace index */
 360	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
 361	xfs_dir2_leaf_tail_t	*ltp;		/* leaf tail structure */
 362	int			n;		/* count of live freespc ents */
 363	xfs_dir2_data_off_t	off;		/* freespace entry value */
 364	__be16			*to;		/* pointer to freespace entry */
 365	xfs_trans_t		*tp;		/* transaction pointer */
 366	struct xfs_dir3_icfree_hdr freehdr;
 367
 368	trace_xfs_dir2_leaf_to_node(args);
 369
 370	dp = args->dp;
 371	tp = args->trans;
 372	/*
 373	 * Add a freespace block to the directory.
 374	 */
 375	if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE, &fdb))) {
 376		return error;
 377	}
 378	ASSERT(fdb == xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET));
 379	/*
 380	 * Get the buffer for the new freespace block.
 381	 */
 382	error = xfs_dir3_free_get_buf(args, fdb, &fbp);
 383	if (error)
 384		return error;
 385
 386	free = fbp->b_addr;
 387	dp->d_ops->free_hdr_from_disk(&freehdr, free);
 388	leaf = lbp->b_addr;
 389	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
 390	if (be32_to_cpu(ltp->bestcount) >
 391				(uint)dp->i_d.di_size / args->geo->blksize)
 392		return -EFSCORRUPTED;
 393
 394	/*
 395	 * Copy freespace entries from the leaf block to the new block.
 396	 * Count active entries.
 397	 */
 398	from = xfs_dir2_leaf_bests_p(ltp);
 399	to = dp->d_ops->free_bests_p(free);
 400	for (i = n = 0; i < be32_to_cpu(ltp->bestcount); i++, from++, to++) {
 401		if ((off = be16_to_cpu(*from)) != NULLDATAOFF)
 402			n++;
 403		*to = cpu_to_be16(off);
 404	}
 405
 406	/*
 407	 * Now initialize the freespace block header.
 408	 */
 409	freehdr.nused = n;
 410	freehdr.nvalid = be32_to_cpu(ltp->bestcount);
 411
 412	dp->d_ops->free_hdr_to_disk(fbp->b_addr, &freehdr);
 413	xfs_dir2_free_log_bests(args, fbp, 0, freehdr.nvalid - 1);
 414	xfs_dir2_free_log_header(args, fbp);
 415
 416	/*
 417	 * Converting the leaf to a leafnode is just a matter of changing the
 418	 * magic number and the ops. Do the change directly to the buffer as
 419	 * it's less work (and less code) than decoding the header to host
 420	 * format and back again.
 421	 */
 422	if (leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC))
 423		leaf->hdr.info.magic = cpu_to_be16(XFS_DIR2_LEAFN_MAGIC);
 424	else
 425		leaf->hdr.info.magic = cpu_to_be16(XFS_DIR3_LEAFN_MAGIC);
 426	lbp->b_ops = &xfs_dir3_leafn_buf_ops;
 427	xfs_trans_buf_set_type(tp, lbp, XFS_BLFT_DIR_LEAFN_BUF);
 428	xfs_dir3_leaf_log_header(args, lbp);
 429	xfs_dir3_leaf_check(dp, lbp);
 430	return 0;
 431}
 432
 433/*
 434 * Add a leaf entry to a leaf block in a node-form directory.
 435 * The other work necessary is done from the caller.
 436 */
 437static int					/* error */
 438xfs_dir2_leafn_add(
 439	struct xfs_buf		*bp,		/* leaf buffer */
 440	xfs_da_args_t		*args,		/* operation arguments */
 441	int			index)		/* insertion pt for new entry */
 442{
 443	int			compact;	/* compacting stale leaves */
 444	xfs_inode_t		*dp;		/* incore directory inode */
 445	int			highstale;	/* next stale entry */
 446	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
 447	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
 448	int			lfloghigh;	/* high leaf entry logging */
 449	int			lfloglow;	/* low leaf entry logging */
 450	int			lowstale;	/* previous stale entry */
 451	struct xfs_dir3_icleaf_hdr leafhdr;
 452	struct xfs_dir2_leaf_entry *ents;
 453
 454	trace_xfs_dir2_leafn_add(args, index);
 455
 456	dp = args->dp;
 457	leaf = bp->b_addr;
 458	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
 459	ents = dp->d_ops->leaf_ents_p(leaf);
 460
 461	/*
 462	 * Quick check just to make sure we are not going to index
 463	 * into other peoples memory
 464	 */
 465	if (index < 0)
 466		return -EFSCORRUPTED;
 467
 468	/*
 469	 * If there are already the maximum number of leaf entries in
 470	 * the block, if there are no stale entries it won't fit.
 471	 * Caller will do a split.  If there are stale entries we'll do
 472	 * a compact.
 473	 */
 474
 475	if (leafhdr.count == dp->d_ops->leaf_max_ents(args->geo)) {
 476		if (!leafhdr.stale)
 477			return -ENOSPC;
 478		compact = leafhdr.stale > 1;
 479	} else
 480		compact = 0;
 481	ASSERT(index == 0 || be32_to_cpu(ents[index - 1].hashval) <= args->hashval);
 482	ASSERT(index == leafhdr.count ||
 483	       be32_to_cpu(ents[index].hashval) >= args->hashval);
 484
 485	if (args->op_flags & XFS_DA_OP_JUSTCHECK)
 486		return 0;
 487
 488	/*
 489	 * Compact out all but one stale leaf entry.  Leaves behind
 490	 * the entry closest to index.
 491	 */
 492	if (compact)
 493		xfs_dir3_leaf_compact_x1(&leafhdr, ents, &index, &lowstale,
 494					 &highstale, &lfloglow, &lfloghigh);
 495	else if (leafhdr.stale) {
 496		/*
 497		 * Set impossible logging indices for this case.
 498		 */
 499		lfloglow = leafhdr.count;
 500		lfloghigh = -1;
 501	}
 502
 503	/*
 504	 * Insert the new entry, log everything.
 505	 */
 506	lep = xfs_dir3_leaf_find_entry(&leafhdr, ents, index, compact, lowstale,
 507				       highstale, &lfloglow, &lfloghigh);
 508
 509	lep->hashval = cpu_to_be32(args->hashval);
 510	lep->address = cpu_to_be32(xfs_dir2_db_off_to_dataptr(args->geo,
 511				args->blkno, args->index));
 512
 513	dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
 514	xfs_dir3_leaf_log_header(args, bp);
 515	xfs_dir3_leaf_log_ents(args, bp, lfloglow, lfloghigh);
 516	xfs_dir3_leaf_check(dp, bp);
 517	return 0;
 518}
 519
 520#ifdef DEBUG
 521static void
 522xfs_dir2_free_hdr_check(
 523	struct xfs_inode *dp,
 524	struct xfs_buf	*bp,
 525	xfs_dir2_db_t	db)
 526{
 527	struct xfs_dir3_icfree_hdr hdr;
 528
 529	dp->d_ops->free_hdr_from_disk(&hdr, bp->b_addr);
 530
 531	ASSERT((hdr.firstdb %
 532		dp->d_ops->free_max_bests(dp->i_mount->m_dir_geo)) == 0);
 533	ASSERT(hdr.firstdb <= db);
 534	ASSERT(db < hdr.firstdb + hdr.nvalid);
 535}
 536#else
 537#define xfs_dir2_free_hdr_check(dp, bp, db)
 538#endif	/* DEBUG */
 539
 540/*
 541 * Return the last hash value in the leaf.
 542 * Stale entries are ok.
 543 */
 544xfs_dahash_t					/* hash value */
 545xfs_dir2_leaf_lasthash(
 546	struct xfs_inode *dp,
 547	struct xfs_buf	*bp,			/* leaf buffer */
 548	int		*count)			/* count of entries in leaf */
 549{
 550	struct xfs_dir2_leaf	*leaf = bp->b_addr;
 551	struct xfs_dir2_leaf_entry *ents;
 552	struct xfs_dir3_icleaf_hdr leafhdr;
 553
 554	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
 555
 556	ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
 557	       leafhdr.magic == XFS_DIR3_LEAFN_MAGIC ||
 558	       leafhdr.magic == XFS_DIR2_LEAF1_MAGIC ||
 559	       leafhdr.magic == XFS_DIR3_LEAF1_MAGIC);
 560
 561	if (count)
 562		*count = leafhdr.count;
 563	if (!leafhdr.count)
 564		return 0;
 565
 566	ents = dp->d_ops->leaf_ents_p(leaf);
 567	return be32_to_cpu(ents[leafhdr.count - 1].hashval);
 568}
 569
 570/*
 571 * Look up a leaf entry for space to add a name in a node-format leaf block.
 572 * The extrablk in state is a freespace block.
 573 */
 574STATIC int
 575xfs_dir2_leafn_lookup_for_addname(
 576	struct xfs_buf		*bp,		/* leaf buffer */
 577	xfs_da_args_t		*args,		/* operation arguments */
 578	int			*indexp,	/* out: leaf entry index */
 579	xfs_da_state_t		*state)		/* state to fill in */
 580{
 581	struct xfs_buf		*curbp = NULL;	/* current data/free buffer */
 582	xfs_dir2_db_t		curdb = -1;	/* current data block number */
 583	xfs_dir2_db_t		curfdb = -1;	/* current free block number */
 584	xfs_inode_t		*dp;		/* incore directory inode */
 585	int			error;		/* error return value */
 586	int			fi;		/* free entry index */
 587	xfs_dir2_free_t		*free = NULL;	/* free block structure */
 588	int			index;		/* leaf entry index */
 589	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
 590	int			length;		/* length of new data entry */
 591	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
 592	xfs_mount_t		*mp;		/* filesystem mount point */
 593	xfs_dir2_db_t		newdb;		/* new data block number */
 594	xfs_dir2_db_t		newfdb;		/* new free block number */
 595	xfs_trans_t		*tp;		/* transaction pointer */
 596	struct xfs_dir2_leaf_entry *ents;
 597	struct xfs_dir3_icleaf_hdr leafhdr;
 598
 599	dp = args->dp;
 600	tp = args->trans;
 601	mp = dp->i_mount;
 602	leaf = bp->b_addr;
 603	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
 604	ents = dp->d_ops->leaf_ents_p(leaf);
 605
 606	xfs_dir3_leaf_check(dp, bp);
 607	ASSERT(leafhdr.count > 0);
 608
 609	/*
 610	 * Look up the hash value in the leaf entries.
 611	 */
 612	index = xfs_dir2_leaf_search_hash(args, bp);
 613	/*
 614	 * Do we have a buffer coming in?
 615	 */
 616	if (state->extravalid) {
 617		/* If so, it's a free block buffer, get the block number. */
 618		curbp = state->extrablk.bp;
 619		curfdb = state->extrablk.blkno;
 620		free = curbp->b_addr;
 621		ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC) ||
 622		       free->hdr.magic == cpu_to_be32(XFS_DIR3_FREE_MAGIC));
 623	}
 624	length = dp->d_ops->data_entsize(args->namelen);
 625	/*
 626	 * Loop over leaf entries with the right hash value.
 627	 */
 628	for (lep = &ents[index];
 629	     index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
 630	     lep++, index++) {
 631		/*
 632		 * Skip stale leaf entries.
 633		 */
 634		if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
 635			continue;
 636		/*
 637		 * Pull the data block number from the entry.
 638		 */
 639		newdb = xfs_dir2_dataptr_to_db(args->geo,
 640					       be32_to_cpu(lep->address));
 641		/*
 642		 * For addname, we're looking for a place to put the new entry.
 643		 * We want to use a data block with an entry of equal
 644		 * hash value to ours if there is one with room.
 645		 *
 646		 * If this block isn't the data block we already have
 647		 * in hand, take a look at it.
 648		 */
 649		if (newdb != curdb) {
 650			__be16 *bests;
 651
 652			curdb = newdb;
 653			/*
 654			 * Convert the data block to the free block
 655			 * holding its freespace information.
 656			 */
 657			newfdb = dp->d_ops->db_to_fdb(args->geo, newdb);
 658			/*
 659			 * If it's not the one we have in hand, read it in.
 660			 */
 661			if (newfdb != curfdb) {
 662				/*
 663				 * If we had one before, drop it.
 664				 */
 665				if (curbp)
 666					xfs_trans_brelse(tp, curbp);
 667
 668				error = xfs_dir2_free_read(tp, dp,
 669						xfs_dir2_db_to_da(args->geo,
 670								  newfdb),
 671						&curbp);
 672				if (error)
 673					return error;
 674				free = curbp->b_addr;
 675
 676				xfs_dir2_free_hdr_check(dp, curbp, curdb);
 677			}
 678			/*
 679			 * Get the index for our entry.
 680			 */
 681			fi = dp->d_ops->db_to_fdindex(args->geo, curdb);
 682			/*
 683			 * If it has room, return it.
 684			 */
 685			bests = dp->d_ops->free_bests_p(free);
 686			if (unlikely(bests[fi] == cpu_to_be16(NULLDATAOFF))) {
 687				XFS_ERROR_REPORT("xfs_dir2_leafn_lookup_int",
 688							XFS_ERRLEVEL_LOW, mp);
 689				if (curfdb != newfdb)
 690					xfs_trans_brelse(tp, curbp);
 691				return -EFSCORRUPTED;
 692			}
 693			curfdb = newfdb;
 694			if (be16_to_cpu(bests[fi]) >= length)
 695				goto out;
 696		}
 697	}
 698	/* Didn't find any space */
 699	fi = -1;
 700out:
 701	ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
 702	if (curbp) {
 703		/* Giving back a free block. */
 704		state->extravalid = 1;
 705		state->extrablk.bp = curbp;
 706		state->extrablk.index = fi;
 707		state->extrablk.blkno = curfdb;
 708
 709		/*
 710		 * Important: this magic number is not in the buffer - it's for
 711		 * buffer type information and therefore only the free/data type
 712		 * matters here, not whether CRCs are enabled or not.
 713		 */
 714		state->extrablk.magic = XFS_DIR2_FREE_MAGIC;
 715	} else {
 716		state->extravalid = 0;
 717	}
 718	/*
 719	 * Return the index, that will be the insertion point.
 720	 */
 721	*indexp = index;
 722	return -ENOENT;
 723}
 724
 725/*
 726 * Look up a leaf entry in a node-format leaf block.
 727 * The extrablk in state a data block.
 728 */
 729STATIC int
 730xfs_dir2_leafn_lookup_for_entry(
 731	struct xfs_buf		*bp,		/* leaf buffer */
 732	xfs_da_args_t		*args,		/* operation arguments */
 733	int			*indexp,	/* out: leaf entry index */
 734	xfs_da_state_t		*state)		/* state to fill in */
 735{
 736	struct xfs_buf		*curbp = NULL;	/* current data/free buffer */
 737	xfs_dir2_db_t		curdb = -1;	/* current data block number */
 738	xfs_dir2_data_entry_t	*dep;		/* data block entry */
 739	xfs_inode_t		*dp;		/* incore directory inode */
 740	int			error;		/* error return value */
 741	int			index;		/* leaf entry index */
 742	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
 743	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
 744	xfs_mount_t		*mp;		/* filesystem mount point */
 745	xfs_dir2_db_t		newdb;		/* new data block number */
 746	xfs_trans_t		*tp;		/* transaction pointer */
 747	enum xfs_dacmp		cmp;		/* comparison result */
 748	struct xfs_dir2_leaf_entry *ents;
 749	struct xfs_dir3_icleaf_hdr leafhdr;
 750
 751	dp = args->dp;
 752	tp = args->trans;
 753	mp = dp->i_mount;
 754	leaf = bp->b_addr;
 755	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
 756	ents = dp->d_ops->leaf_ents_p(leaf);
 757
 758	xfs_dir3_leaf_check(dp, bp);
 759	ASSERT(leafhdr.count > 0);
 760
 761	/*
 762	 * Look up the hash value in the leaf entries.
 763	 */
 764	index = xfs_dir2_leaf_search_hash(args, bp);
 765	/*
 766	 * Do we have a buffer coming in?
 767	 */
 768	if (state->extravalid) {
 769		curbp = state->extrablk.bp;
 770		curdb = state->extrablk.blkno;
 771	}
 772	/*
 773	 * Loop over leaf entries with the right hash value.
 774	 */
 775	for (lep = &ents[index];
 776	     index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
 777	     lep++, index++) {
 778		/*
 779		 * Skip stale leaf entries.
 780		 */
 781		if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
 782			continue;
 783		/*
 784		 * Pull the data block number from the entry.
 785		 */
 786		newdb = xfs_dir2_dataptr_to_db(args->geo,
 787					       be32_to_cpu(lep->address));
 788		/*
 789		 * Not adding a new entry, so we really want to find
 790		 * the name given to us.
 791		 *
 792		 * If it's a different data block, go get it.
 793		 */
 794		if (newdb != curdb) {
 795			/*
 796			 * If we had a block before that we aren't saving
 797			 * for a CI name, drop it
 798			 */
 799			if (curbp && (args->cmpresult == XFS_CMP_DIFFERENT ||
 800						curdb != state->extrablk.blkno))
 801				xfs_trans_brelse(tp, curbp);
 802			/*
 803			 * If needing the block that is saved with a CI match,
 804			 * use it otherwise read in the new data block.
 805			 */
 806			if (args->cmpresult != XFS_CMP_DIFFERENT &&
 807					newdb == state->extrablk.blkno) {
 808				ASSERT(state->extravalid);
 809				curbp = state->extrablk.bp;
 810			} else {
 811				error = xfs_dir3_data_read(tp, dp,
 812						xfs_dir2_db_to_da(args->geo,
 813								  newdb),
 814						-1, &curbp);
 815				if (error)
 816					return error;
 817			}
 818			xfs_dir3_data_check(dp, curbp);
 819			curdb = newdb;
 820		}
 821		/*
 822		 * Point to the data entry.
 823		 */
 824		dep = (xfs_dir2_data_entry_t *)((char *)curbp->b_addr +
 825			xfs_dir2_dataptr_to_off(args->geo,
 826						be32_to_cpu(lep->address)));
 827		/*
 828		 * Compare the entry and if it's an exact match, return
 829		 * EEXIST immediately. If it's the first case-insensitive
 830		 * match, store the block & inode number and continue looking.
 831		 */
 832		cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen);
 833		if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {
 834			/* If there is a CI match block, drop it */
 835			if (args->cmpresult != XFS_CMP_DIFFERENT &&
 836						curdb != state->extrablk.blkno)
 837				xfs_trans_brelse(tp, state->extrablk.bp);
 838			args->cmpresult = cmp;
 839			args->inumber = be64_to_cpu(dep->inumber);
 840			args->filetype = dp->d_ops->data_get_ftype(dep);
 841			*indexp = index;
 842			state->extravalid = 1;
 843			state->extrablk.bp = curbp;
 844			state->extrablk.blkno = curdb;
 845			state->extrablk.index = (int)((char *)dep -
 846							(char *)curbp->b_addr);
 847			state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
 848			curbp->b_ops = &xfs_dir3_data_buf_ops;
 849			xfs_trans_buf_set_type(tp, curbp, XFS_BLFT_DIR_DATA_BUF);
 850			if (cmp == XFS_CMP_EXACT)
 851				return -EEXIST;
 852		}
 853	}
 854	ASSERT(index == leafhdr.count || (args->op_flags & XFS_DA_OP_OKNOENT));
 855	if (curbp) {
 856		if (args->cmpresult == XFS_CMP_DIFFERENT) {
 857			/* Giving back last used data block. */
 858			state->extravalid = 1;
 859			state->extrablk.bp = curbp;
 860			state->extrablk.index = -1;
 861			state->extrablk.blkno = curdb;
 862			state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
 863			curbp->b_ops = &xfs_dir3_data_buf_ops;
 864			xfs_trans_buf_set_type(tp, curbp, XFS_BLFT_DIR_DATA_BUF);
 865		} else {
 866			/* If the curbp is not the CI match block, drop it */
 867			if (state->extrablk.bp != curbp)
 868				xfs_trans_brelse(tp, curbp);
 869		}
 870	} else {
 871		state->extravalid = 0;
 872	}
 873	*indexp = index;
 874	return -ENOENT;
 875}
 876
 877/*
 878 * Look up a leaf entry in a node-format leaf block.
 879 * If this is an addname then the extrablk in state is a freespace block,
 880 * otherwise it's a data block.
 881 */
 882int
 883xfs_dir2_leafn_lookup_int(
 884	struct xfs_buf		*bp,		/* leaf buffer */
 885	xfs_da_args_t		*args,		/* operation arguments */
 886	int			*indexp,	/* out: leaf entry index */
 887	xfs_da_state_t		*state)		/* state to fill in */
 888{
 889	if (args->op_flags & XFS_DA_OP_ADDNAME)
 890		return xfs_dir2_leafn_lookup_for_addname(bp, args, indexp,
 891							state);
 892	return xfs_dir2_leafn_lookup_for_entry(bp, args, indexp, state);
 893}
 894
 895/*
 896 * Move count leaf entries from source to destination leaf.
 897 * Log entries and headers.  Stale entries are preserved.
 898 */
 899static void
 900xfs_dir3_leafn_moveents(
 901	xfs_da_args_t			*args,	/* operation arguments */
 902	struct xfs_buf			*bp_s,	/* source */
 903	struct xfs_dir3_icleaf_hdr	*shdr,
 904	struct xfs_dir2_leaf_entry	*sents,
 905	int				start_s,/* source leaf index */
 906	struct xfs_buf			*bp_d,	/* destination */
 907	struct xfs_dir3_icleaf_hdr	*dhdr,
 908	struct xfs_dir2_leaf_entry	*dents,
 909	int				start_d,/* destination leaf index */
 910	int				count)	/* count of leaves to copy */
 911{
 912	int				stale;	/* count stale leaves copied */
 913
 914	trace_xfs_dir2_leafn_moveents(args, start_s, start_d, count);
 915
 916	/*
 917	 * Silently return if nothing to do.
 918	 */
 919	if (count == 0)
 920		return;
 921
 922	/*
 923	 * If the destination index is not the end of the current
 924	 * destination leaf entries, open up a hole in the destination
 925	 * to hold the new entries.
 926	 */
 927	if (start_d < dhdr->count) {
 928		memmove(&dents[start_d + count], &dents[start_d],
 929			(dhdr->count - start_d) * sizeof(xfs_dir2_leaf_entry_t));
 930		xfs_dir3_leaf_log_ents(args, bp_d, start_d + count,
 931				       count + dhdr->count - 1);
 932	}
 933	/*
 934	 * If the source has stale leaves, count the ones in the copy range
 935	 * so we can update the header correctly.
 936	 */
 937	if (shdr->stale) {
 938		int	i;			/* temp leaf index */
 939
 940		for (i = start_s, stale = 0; i < start_s + count; i++) {
 941			if (sents[i].address ==
 942					cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
 943				stale++;
 944		}
 945	} else
 946		stale = 0;
 947	/*
 948	 * Copy the leaf entries from source to destination.
 949	 */
 950	memcpy(&dents[start_d], &sents[start_s],
 951		count * sizeof(xfs_dir2_leaf_entry_t));
 952	xfs_dir3_leaf_log_ents(args, bp_d, start_d, start_d + count - 1);
 953
 954	/*
 955	 * If there are source entries after the ones we copied,
 956	 * delete the ones we copied by sliding the next ones down.
 957	 */
 958	if (start_s + count < shdr->count) {
 959		memmove(&sents[start_s], &sents[start_s + count],
 960			count * sizeof(xfs_dir2_leaf_entry_t));
 961		xfs_dir3_leaf_log_ents(args, bp_s, start_s, start_s + count - 1);
 962	}
 963
 964	/*
 965	 * Update the headers and log them.
 966	 */
 967	shdr->count -= count;
 968	shdr->stale -= stale;
 969	dhdr->count += count;
 970	dhdr->stale += stale;
 971}
 972
 973/*
 974 * Determine the sort order of two leaf blocks.
 975 * Returns 1 if both are valid and leaf2 should be before leaf1, else 0.
 976 */
 977int						/* sort order */
 978xfs_dir2_leafn_order(
 979	struct xfs_inode	*dp,
 980	struct xfs_buf		*leaf1_bp,		/* leaf1 buffer */
 981	struct xfs_buf		*leaf2_bp)		/* leaf2 buffer */
 982{
 983	struct xfs_dir2_leaf	*leaf1 = leaf1_bp->b_addr;
 984	struct xfs_dir2_leaf	*leaf2 = leaf2_bp->b_addr;
 985	struct xfs_dir2_leaf_entry *ents1;
 986	struct xfs_dir2_leaf_entry *ents2;
 987	struct xfs_dir3_icleaf_hdr hdr1;
 988	struct xfs_dir3_icleaf_hdr hdr2;
 989
 990	dp->d_ops->leaf_hdr_from_disk(&hdr1, leaf1);
 991	dp->d_ops->leaf_hdr_from_disk(&hdr2, leaf2);
 992	ents1 = dp->d_ops->leaf_ents_p(leaf1);
 993	ents2 = dp->d_ops->leaf_ents_p(leaf2);
 994
 995	if (hdr1.count > 0 && hdr2.count > 0 &&
 996	    (be32_to_cpu(ents2[0].hashval) < be32_to_cpu(ents1[0].hashval) ||
 997	     be32_to_cpu(ents2[hdr2.count - 1].hashval) <
 998				be32_to_cpu(ents1[hdr1.count - 1].hashval)))
 999		return 1;
1000	return 0;
1001}
1002
1003/*
1004 * Rebalance leaf entries between two leaf blocks.
1005 * This is actually only called when the second block is new,
1006 * though the code deals with the general case.
1007 * A new entry will be inserted in one of the blocks, and that
1008 * entry is taken into account when balancing.
1009 */
1010static void
1011xfs_dir2_leafn_rebalance(
1012	xfs_da_state_t		*state,		/* btree cursor */
1013	xfs_da_state_blk_t	*blk1,		/* first btree block */
1014	xfs_da_state_blk_t	*blk2)		/* second btree block */
1015{
1016	xfs_da_args_t		*args;		/* operation arguments */
1017	int			count;		/* count (& direction) leaves */
1018	int			isleft;		/* new goes in left leaf */
1019	xfs_dir2_leaf_t		*leaf1;		/* first leaf structure */
1020	xfs_dir2_leaf_t		*leaf2;		/* second leaf structure */
1021	int			mid;		/* midpoint leaf index */
1022#if defined(DEBUG) || defined(XFS_WARN)
1023	int			oldstale;	/* old count of stale leaves */
1024#endif
1025	int			oldsum;		/* old total leaf count */
1026	int			swap;		/* swapped leaf blocks */
1027	struct xfs_dir2_leaf_entry *ents1;
1028	struct xfs_dir2_leaf_entry *ents2;
1029	struct xfs_dir3_icleaf_hdr hdr1;
1030	struct xfs_dir3_icleaf_hdr hdr2;
1031	struct xfs_inode	*dp = state->args->dp;
1032
1033	args = state->args;
1034	/*
1035	 * If the block order is wrong, swap the arguments.
1036	 */
1037	if ((swap = xfs_dir2_leafn_order(dp, blk1->bp, blk2->bp))) {
1038		xfs_da_state_blk_t	*tmp;	/* temp for block swap */
1039
1040		tmp = blk1;
1041		blk1 = blk2;
1042		blk2 = tmp;
1043	}
1044	leaf1 = blk1->bp->b_addr;
1045	leaf2 = blk2->bp->b_addr;
1046	dp->d_ops->leaf_hdr_from_disk(&hdr1, leaf1);
1047	dp->d_ops->leaf_hdr_from_disk(&hdr2, leaf2);
1048	ents1 = dp->d_ops->leaf_ents_p(leaf1);
1049	ents2 = dp->d_ops->leaf_ents_p(leaf2);
1050
1051	oldsum = hdr1.count + hdr2.count;
1052#if defined(DEBUG) || defined(XFS_WARN)
1053	oldstale = hdr1.stale + hdr2.stale;
1054#endif
1055	mid = oldsum >> 1;
1056
1057	/*
1058	 * If the old leaf count was odd then the new one will be even,
1059	 * so we need to divide the new count evenly.
1060	 */
1061	if (oldsum & 1) {
1062		xfs_dahash_t	midhash;	/* middle entry hash value */
1063
1064		if (mid >= hdr1.count)
1065			midhash = be32_to_cpu(ents2[mid - hdr1.count].hashval);
1066		else
1067			midhash = be32_to_cpu(ents1[mid].hashval);
1068		isleft = args->hashval <= midhash;
1069	}
1070	/*
1071	 * If the old count is even then the new count is odd, so there's
1072	 * no preferred side for the new entry.
1073	 * Pick the left one.
1074	 */
1075	else
1076		isleft = 1;
1077	/*
1078	 * Calculate moved entry count.  Positive means left-to-right,
1079	 * negative means right-to-left.  Then move the entries.
1080	 */
1081	count = hdr1.count - mid + (isleft == 0);
1082	if (count > 0)
1083		xfs_dir3_leafn_moveents(args, blk1->bp, &hdr1, ents1,
1084					hdr1.count - count, blk2->bp,
1085					&hdr2, ents2, 0, count);
1086	else if (count < 0)
1087		xfs_dir3_leafn_moveents(args, blk2->bp, &hdr2, ents2, 0,
1088					blk1->bp, &hdr1, ents1,
1089					hdr1.count, count);
1090
1091	ASSERT(hdr1.count + hdr2.count == oldsum);
1092	ASSERT(hdr1.stale + hdr2.stale == oldstale);
1093
1094	/* log the changes made when moving the entries */
1095	dp->d_ops->leaf_hdr_to_disk(leaf1, &hdr1);
1096	dp->d_ops->leaf_hdr_to_disk(leaf2, &hdr2);
1097	xfs_dir3_leaf_log_header(args, blk1->bp);
1098	xfs_dir3_leaf_log_header(args, blk2->bp);
1099
1100	xfs_dir3_leaf_check(dp, blk1->bp);
1101	xfs_dir3_leaf_check(dp, blk2->bp);
1102
1103	/*
1104	 * Mark whether we're inserting into the old or new leaf.
1105	 */
1106	if (hdr1.count < hdr2.count)
1107		state->inleaf = swap;
1108	else if (hdr1.count > hdr2.count)
1109		state->inleaf = !swap;
1110	else
1111		state->inleaf = swap ^ (blk1->index <= hdr1.count);
1112	/*
1113	 * Adjust the expected index for insertion.
1114	 */
1115	if (!state->inleaf)
1116		blk2->index = blk1->index - hdr1.count;
1117
1118	/*
1119	 * Finally sanity check just to make sure we are not returning a
1120	 * negative index
1121	 */
1122	if (blk2->index < 0) {
1123		state->inleaf = 1;
1124		blk2->index = 0;
1125		xfs_alert(dp->i_mount,
1126	"%s: picked the wrong leaf? reverting original leaf: blk1->index %d",
1127			__func__, blk1->index);
1128	}
1129}
1130
1131static int
1132xfs_dir3_data_block_free(
1133	xfs_da_args_t		*args,
1134	struct xfs_dir2_data_hdr *hdr,
1135	struct xfs_dir2_free	*free,
1136	xfs_dir2_db_t		fdb,
1137	int			findex,
1138	struct xfs_buf		*fbp,
1139	int			longest)
1140{
1141	int			logfree = 0;
1142	__be16			*bests;
1143	struct xfs_dir3_icfree_hdr freehdr;
1144	struct xfs_inode	*dp = args->dp;
1145
1146	dp->d_ops->free_hdr_from_disk(&freehdr, free);
1147	bests = dp->d_ops->free_bests_p(free);
1148	if (hdr) {
1149		/*
1150		 * Data block is not empty, just set the free entry to the new
1151		 * value.
1152		 */
1153		bests[findex] = cpu_to_be16(longest);
1154		xfs_dir2_free_log_bests(args, fbp, findex, findex);
1155		return 0;
1156	}
1157
1158	/* One less used entry in the free table. */
1159	freehdr.nused--;
1160
1161	/*
1162	 * If this was the last entry in the table, we can trim the table size
1163	 * back.  There might be other entries at the end referring to
1164	 * non-existent data blocks, get those too.
1165	 */
1166	if (findex == freehdr.nvalid - 1) {
1167		int	i;		/* free entry index */
1168
1169		for (i = findex - 1; i >= 0; i--) {
1170			if (bests[i] != cpu_to_be16(NULLDATAOFF))
1171				break;
1172		}
1173		freehdr.nvalid = i + 1;
1174		logfree = 0;
1175	} else {
1176		/* Not the last entry, just punch it out.  */
1177		bests[findex] = cpu_to_be16(NULLDATAOFF);
1178		logfree = 1;
1179	}
1180
1181	dp->d_ops->free_hdr_to_disk(free, &freehdr);
1182	xfs_dir2_free_log_header(args, fbp);
1183
1184	/*
1185	 * If there are no useful entries left in the block, get rid of the
1186	 * block if we can.
1187	 */
1188	if (!freehdr.nused) {
1189		int error;
1190
1191		error = xfs_dir2_shrink_inode(args, fdb, fbp);
1192		if (error == 0) {
1193			fbp = NULL;
1194			logfree = 0;
1195		} else if (error != -ENOSPC || args->total != 0)
1196			return error;
1197		/*
1198		 * It's possible to get ENOSPC if there is no
1199		 * space reservation.  In this case some one
1200		 * else will eventually get rid of this block.
1201		 */
1202	}
1203
1204	/* Log the free entry that changed, unless we got rid of it.  */
1205	if (logfree)
1206		xfs_dir2_free_log_bests(args, fbp, findex, findex);
1207	return 0;
1208}
1209
1210/*
1211 * Remove an entry from a node directory.
1212 * This removes the leaf entry and the data entry,
1213 * and updates the free block if necessary.
1214 */
1215static int					/* error */
1216xfs_dir2_leafn_remove(
1217	xfs_da_args_t		*args,		/* operation arguments */
1218	struct xfs_buf		*bp,		/* leaf buffer */
1219	int			index,		/* leaf entry index */
1220	xfs_da_state_blk_t	*dblk,		/* data block */
1221	int			*rval)		/* resulting block needs join */
1222{
1223	xfs_dir2_data_hdr_t	*hdr;		/* data block header */
1224	xfs_dir2_db_t		db;		/* data block number */
1225	struct xfs_buf		*dbp;		/* data block buffer */
1226	xfs_dir2_data_entry_t	*dep;		/* data block entry */
1227	xfs_inode_t		*dp;		/* incore directory inode */
1228	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
1229	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
1230	int			longest;	/* longest data free entry */
1231	int			off;		/* data block entry offset */
1232	int			needlog;	/* need to log data header */
1233	int			needscan;	/* need to rescan data frees */
1234	xfs_trans_t		*tp;		/* transaction pointer */
1235	struct xfs_dir2_data_free *bf;		/* bestfree table */
1236	struct xfs_dir3_icleaf_hdr leafhdr;
1237	struct xfs_dir2_leaf_entry *ents;
1238
1239	trace_xfs_dir2_leafn_remove(args, index);
1240
1241	dp = args->dp;
1242	tp = args->trans;
1243	leaf = bp->b_addr;
1244	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
1245	ents = dp->d_ops->leaf_ents_p(leaf);
1246
1247	/*
1248	 * Point to the entry we're removing.
1249	 */
1250	lep = &ents[index];
1251
1252	/*
1253	 * Extract the data block and offset from the entry.
1254	 */
1255	db = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address));
1256	ASSERT(dblk->blkno == db);
1257	off = xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address));
1258	ASSERT(dblk->index == off);
1259
1260	/*
1261	 * Kill the leaf entry by marking it stale.
1262	 * Log the leaf block changes.
1263	 */
1264	leafhdr.stale++;
1265	dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
1266	xfs_dir3_leaf_log_header(args, bp);
1267
1268	lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
1269	xfs_dir3_leaf_log_ents(args, bp, index, index);
1270
1271	/*
1272	 * Make the data entry free.  Keep track of the longest freespace
1273	 * in the data block in case it changes.
1274	 */
1275	dbp = dblk->bp;
1276	hdr = dbp->b_addr;
1277	dep = (xfs_dir2_data_entry_t *)((char *)hdr + off);
1278	bf = dp->d_ops->data_bestfree_p(hdr);
1279	longest = be16_to_cpu(bf[0].length);
1280	needlog = needscan = 0;
1281	xfs_dir2_data_make_free(args, dbp, off,
1282		dp->d_ops->data_entsize(dep->namelen), &needlog, &needscan);
1283	/*
1284	 * Rescan the data block freespaces for bestfree.
1285	 * Log the data block header if needed.
1286	 */
1287	if (needscan)
1288		xfs_dir2_data_freescan(dp, hdr, &needlog);
1289	if (needlog)
1290		xfs_dir2_data_log_header(args, dbp);
1291	xfs_dir3_data_check(dp, dbp);
1292	/*
1293	 * If the longest data block freespace changes, need to update
1294	 * the corresponding freeblock entry.
1295	 */
1296	if (longest < be16_to_cpu(bf[0].length)) {
1297		int		error;		/* error return value */
1298		struct xfs_buf	*fbp;		/* freeblock buffer */
1299		xfs_dir2_db_t	fdb;		/* freeblock block number */
1300		int		findex;		/* index in freeblock entries */
1301		xfs_dir2_free_t	*free;		/* freeblock structure */
1302
1303		/*
1304		 * Convert the data block number to a free block,
1305		 * read in the free block.
1306		 */
1307		fdb = dp->d_ops->db_to_fdb(args->geo, db);
1308		error = xfs_dir2_free_read(tp, dp,
1309					   xfs_dir2_db_to_da(args->geo, fdb),
1310					   &fbp);
1311		if (error)
1312			return error;
1313		free = fbp->b_addr;
1314#ifdef DEBUG
1315	{
1316		struct xfs_dir3_icfree_hdr freehdr;
1317		dp->d_ops->free_hdr_from_disk(&freehdr, free);
1318		ASSERT(freehdr.firstdb == dp->d_ops->free_max_bests(args->geo) *
1319			(fdb - xfs_dir2_byte_to_db(args->geo,
1320						   XFS_DIR2_FREE_OFFSET)));
1321	}
1322#endif
1323		/*
1324		 * Calculate which entry we need to fix.
1325		 */
1326		findex = dp->d_ops->db_to_fdindex(args->geo, db);
1327		longest = be16_to_cpu(bf[0].length);
1328		/*
1329		 * If the data block is now empty we can get rid of it
1330		 * (usually).
1331		 */
1332		if (longest == args->geo->blksize -
1333			       dp->d_ops->data_entry_offset) {
1334			/*
1335			 * Try to punch out the data block.
1336			 */
1337			error = xfs_dir2_shrink_inode(args, db, dbp);
1338			if (error == 0) {
1339				dblk->bp = NULL;
1340				hdr = NULL;
1341			}
1342			/*
1343			 * We can get ENOSPC if there's no space reservation.
1344			 * In this case just drop the buffer and some one else
1345			 * will eventually get rid of the empty block.
1346			 */
1347			else if (!(error == -ENOSPC && args->total == 0))
1348				return error;
1349		}
1350		/*
1351		 * If we got rid of the data block, we can eliminate that entry
1352		 * in the free block.
1353		 */
1354		error = xfs_dir3_data_block_free(args, hdr, free,
1355						 fdb, findex, fbp, longest);
1356		if (error)
1357			return error;
1358	}
1359
1360	xfs_dir3_leaf_check(dp, bp);
1361	/*
1362	 * Return indication of whether this leaf block is empty enough
1363	 * to justify trying to join it with a neighbor.
1364	 */
1365	*rval = (dp->d_ops->leaf_hdr_size +
1366		 (uint)sizeof(ents[0]) * (leafhdr.count - leafhdr.stale)) <
1367		args->geo->magicpct;
1368	return 0;
1369}
1370
1371/*
1372 * Split the leaf entries in the old block into old and new blocks.
1373 */
1374int						/* error */
1375xfs_dir2_leafn_split(
1376	xfs_da_state_t		*state,		/* btree cursor */
1377	xfs_da_state_blk_t	*oldblk,	/* original block */
1378	xfs_da_state_blk_t	*newblk)	/* newly created block */
1379{
1380	xfs_da_args_t		*args;		/* operation arguments */
1381	xfs_dablk_t		blkno;		/* new leaf block number */
1382	int			error;		/* error return value */
1383	struct xfs_inode	*dp;
1384
1385	/*
1386	 * Allocate space for a new leaf node.
1387	 */
1388	args = state->args;
1389	dp = args->dp;
1390	ASSERT(oldblk->magic == XFS_DIR2_LEAFN_MAGIC);
1391	error = xfs_da_grow_inode(args, &blkno);
1392	if (error) {
1393		return error;
1394	}
1395	/*
1396	 * Initialize the new leaf block.
1397	 */
1398	error = xfs_dir3_leaf_get_buf(args, xfs_dir2_da_to_db(args->geo, blkno),
1399				      &newblk->bp, XFS_DIR2_LEAFN_MAGIC);
1400	if (error)
1401		return error;
1402
1403	newblk->blkno = blkno;
1404	newblk->magic = XFS_DIR2_LEAFN_MAGIC;
1405	/*
1406	 * Rebalance the entries across the two leaves, link the new
1407	 * block into the leaves.
1408	 */
1409	xfs_dir2_leafn_rebalance(state, oldblk, newblk);
1410	error = xfs_da3_blk_link(state, oldblk, newblk);
1411	if (error) {
1412		return error;
1413	}
1414	/*
1415	 * Insert the new entry in the correct block.
1416	 */
1417	if (state->inleaf)
1418		error = xfs_dir2_leafn_add(oldblk->bp, args, oldblk->index);
1419	else
1420		error = xfs_dir2_leafn_add(newblk->bp, args, newblk->index);
1421	/*
1422	 * Update last hashval in each block since we added the name.
1423	 */
1424	oldblk->hashval = xfs_dir2_leaf_lasthash(dp, oldblk->bp, NULL);
1425	newblk->hashval = xfs_dir2_leaf_lasthash(dp, newblk->bp, NULL);
1426	xfs_dir3_leaf_check(dp, oldblk->bp);
1427	xfs_dir3_leaf_check(dp, newblk->bp);
1428	return error;
1429}
1430
1431/*
1432 * Check a leaf block and its neighbors to see if the block should be
1433 * collapsed into one or the other neighbor.  Always keep the block
1434 * with the smaller block number.
1435 * If the current block is over 50% full, don't try to join it, return 0.
1436 * If the block is empty, fill in the state structure and return 2.
1437 * If it can be collapsed, fill in the state structure and return 1.
1438 * If nothing can be done, return 0.
1439 */
1440int						/* error */
1441xfs_dir2_leafn_toosmall(
1442	xfs_da_state_t		*state,		/* btree cursor */
1443	int			*action)	/* resulting action to take */
1444{
1445	xfs_da_state_blk_t	*blk;		/* leaf block */
1446	xfs_dablk_t		blkno;		/* leaf block number */
1447	struct xfs_buf		*bp;		/* leaf buffer */
1448	int			bytes;		/* bytes in use */
1449	int			count;		/* leaf live entry count */
1450	int			error;		/* error return value */
1451	int			forward;	/* sibling block direction */
1452	int			i;		/* sibling counter */
1453	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
1454	int			rval;		/* result from path_shift */
1455	struct xfs_dir3_icleaf_hdr leafhdr;
1456	struct xfs_dir2_leaf_entry *ents;
1457	struct xfs_inode	*dp = state->args->dp;
1458
1459	/*
1460	 * Check for the degenerate case of the block being over 50% full.
1461	 * If so, it's not worth even looking to see if we might be able
1462	 * to coalesce with a sibling.
1463	 */
1464	blk = &state->path.blk[state->path.active - 1];
1465	leaf = blk->bp->b_addr;
1466	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
1467	ents = dp->d_ops->leaf_ents_p(leaf);
1468	xfs_dir3_leaf_check(dp, blk->bp);
1469
1470	count = leafhdr.count - leafhdr.stale;
1471	bytes = dp->d_ops->leaf_hdr_size + count * sizeof(ents[0]);
1472	if (bytes > (state->args->geo->blksize >> 1)) {
1473		/*
1474		 * Blk over 50%, don't try to join.
1475		 */
1476		*action = 0;
1477		return 0;
1478	}
1479	/*
1480	 * Check for the degenerate case of the block being empty.
1481	 * If the block is empty, we'll simply delete it, no need to
1482	 * coalesce it with a sibling block.  We choose (arbitrarily)
1483	 * to merge with the forward block unless it is NULL.
1484	 */
1485	if (count == 0) {
1486		/*
1487		 * Make altpath point to the block we want to keep and
1488		 * path point to the block we want to drop (this one).
1489		 */
1490		forward = (leafhdr.forw != 0);
1491		memcpy(&state->altpath, &state->path, sizeof(state->path));
1492		error = xfs_da3_path_shift(state, &state->altpath, forward, 0,
1493			&rval);
1494		if (error)
1495			return error;
1496		*action = rval ? 2 : 0;
1497		return 0;
1498	}
1499	/*
1500	 * Examine each sibling block to see if we can coalesce with
1501	 * at least 25% free space to spare.  We need to figure out
1502	 * whether to merge with the forward or the backward block.
1503	 * We prefer coalescing with the lower numbered sibling so as
1504	 * to shrink a directory over time.
1505	 */
1506	forward = leafhdr.forw < leafhdr.back;
1507	for (i = 0, bp = NULL; i < 2; forward = !forward, i++) {
1508		struct xfs_dir3_icleaf_hdr hdr2;
1509
1510		blkno = forward ? leafhdr.forw : leafhdr.back;
1511		if (blkno == 0)
1512			continue;
1513		/*
1514		 * Read the sibling leaf block.
1515		 */
1516		error = xfs_dir3_leafn_read(state->args->trans, dp,
1517					    blkno, -1, &bp);
1518		if (error)
1519			return error;
1520
1521		/*
1522		 * Count bytes in the two blocks combined.
1523		 */
1524		count = leafhdr.count - leafhdr.stale;
1525		bytes = state->args->geo->blksize -
1526			(state->args->geo->blksize >> 2);
1527
1528		leaf = bp->b_addr;
1529		dp->d_ops->leaf_hdr_from_disk(&hdr2, leaf);
1530		ents = dp->d_ops->leaf_ents_p(leaf);
1531		count += hdr2.count - hdr2.stale;
1532		bytes -= count * sizeof(ents[0]);
1533
1534		/*
1535		 * Fits with at least 25% to spare.
1536		 */
1537		if (bytes >= 0)
1538			break;
1539		xfs_trans_brelse(state->args->trans, bp);
1540	}
1541	/*
1542	 * Didn't like either block, give up.
1543	 */
1544	if (i >= 2) {
1545		*action = 0;
1546		return 0;
1547	}
1548
1549	/*
1550	 * Make altpath point to the block we want to keep (the lower
1551	 * numbered block) and path point to the block we want to drop.
1552	 */
1553	memcpy(&state->altpath, &state->path, sizeof(state->path));
1554	if (blkno < blk->blkno)
1555		error = xfs_da3_path_shift(state, &state->altpath, forward, 0,
1556			&rval);
1557	else
1558		error = xfs_da3_path_shift(state, &state->path, forward, 0,
1559			&rval);
1560	if (error) {
1561		return error;
1562	}
1563	*action = rval ? 0 : 1;
1564	return 0;
1565}
1566
1567/*
1568 * Move all the leaf entries from drop_blk to save_blk.
1569 * This is done as part of a join operation.
1570 */
1571void
1572xfs_dir2_leafn_unbalance(
1573	xfs_da_state_t		*state,		/* cursor */
1574	xfs_da_state_blk_t	*drop_blk,	/* dead block */
1575	xfs_da_state_blk_t	*save_blk)	/* surviving block */
1576{
1577	xfs_da_args_t		*args;		/* operation arguments */
1578	xfs_dir2_leaf_t		*drop_leaf;	/* dead leaf structure */
1579	xfs_dir2_leaf_t		*save_leaf;	/* surviving leaf structure */
1580	struct xfs_dir3_icleaf_hdr savehdr;
1581	struct xfs_dir3_icleaf_hdr drophdr;
1582	struct xfs_dir2_leaf_entry *sents;
1583	struct xfs_dir2_leaf_entry *dents;
1584	struct xfs_inode	*dp = state->args->dp;
1585
1586	args = state->args;
1587	ASSERT(drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
1588	ASSERT(save_blk->magic == XFS_DIR2_LEAFN_MAGIC);
1589	drop_leaf = drop_blk->bp->b_addr;
1590	save_leaf = save_blk->bp->b_addr;
1591
1592	dp->d_ops->leaf_hdr_from_disk(&savehdr, save_leaf);
1593	dp->d_ops->leaf_hdr_from_disk(&drophdr, drop_leaf);
1594	sents = dp->d_ops->leaf_ents_p(save_leaf);
1595	dents = dp->d_ops->leaf_ents_p(drop_leaf);
1596
1597	/*
1598	 * If there are any stale leaf entries, take this opportunity
1599	 * to purge them.
1600	 */
1601	if (drophdr.stale)
1602		xfs_dir3_leaf_compact(args, &drophdr, drop_blk->bp);
1603	if (savehdr.stale)
1604		xfs_dir3_leaf_compact(args, &savehdr, save_blk->bp);
1605
1606	/*
1607	 * Move the entries from drop to the appropriate end of save.
1608	 */
1609	drop_blk->hashval = be32_to_cpu(dents[drophdr.count - 1].hashval);
1610	if (xfs_dir2_leafn_order(dp, save_blk->bp, drop_blk->bp))
1611		xfs_dir3_leafn_moveents(args, drop_blk->bp, &drophdr, dents, 0,
1612					save_blk->bp, &savehdr, sents, 0,
1613					drophdr.count);
1614	else
1615		xfs_dir3_leafn_moveents(args, drop_blk->bp, &drophdr, dents, 0,
1616					save_blk->bp, &savehdr, sents,
1617					savehdr.count, drophdr.count);
1618	save_blk->hashval = be32_to_cpu(sents[savehdr.count - 1].hashval);
1619
1620	/* log the changes made when moving the entries */
1621	dp->d_ops->leaf_hdr_to_disk(save_leaf, &savehdr);
1622	dp->d_ops->leaf_hdr_to_disk(drop_leaf, &drophdr);
1623	xfs_dir3_leaf_log_header(args, save_blk->bp);
1624	xfs_dir3_leaf_log_header(args, drop_blk->bp);
1625
1626	xfs_dir3_leaf_check(dp, save_blk->bp);
1627	xfs_dir3_leaf_check(dp, drop_blk->bp);
1628}
1629
1630/*
1631 * Top-level node form directory addname routine.
1632 */
1633int						/* error */
1634xfs_dir2_node_addname(
1635	xfs_da_args_t		*args)		/* operation arguments */
1636{
1637	xfs_da_state_blk_t	*blk;		/* leaf block for insert */
1638	int			error;		/* error return value */
1639	int			rval;		/* sub-return value */
1640	xfs_da_state_t		*state;		/* btree cursor */
1641
1642	trace_xfs_dir2_node_addname(args);
1643
1644	/*
1645	 * Allocate and initialize the state (btree cursor).
1646	 */
1647	state = xfs_da_state_alloc();
1648	state->args = args;
1649	state->mp = args->dp->i_mount;
1650	/*
1651	 * Look up the name.  We're not supposed to find it, but
1652	 * this gives us the insertion point.
1653	 */
1654	error = xfs_da3_node_lookup_int(state, &rval);
1655	if (error)
1656		rval = error;
1657	if (rval != -ENOENT) {
1658		goto done;
1659	}
1660	/*
1661	 * Add the data entry to a data block.
1662	 * Extravalid is set to a freeblock found by lookup.
1663	 */
1664	rval = xfs_dir2_node_addname_int(args,
1665		state->extravalid ? &state->extrablk : NULL);
1666	if (rval) {
1667		goto done;
1668	}
1669	blk = &state->path.blk[state->path.active - 1];
1670	ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
1671	/*
1672	 * Add the new leaf entry.
1673	 */
1674	rval = xfs_dir2_leafn_add(blk->bp, args, blk->index);
1675	if (rval == 0) {
1676		/*
1677		 * It worked, fix the hash values up the btree.
1678		 */
1679		if (!(args->op_flags & XFS_DA_OP_JUSTCHECK))
1680			xfs_da3_fixhashpath(state, &state->path);
1681	} else {
1682		/*
1683		 * It didn't work, we need to split the leaf block.
1684		 */
1685		if (args->total == 0) {
1686			ASSERT(rval == -ENOSPC);
1687			goto done;
1688		}
1689		/*
1690		 * Split the leaf block and insert the new entry.
1691		 */
1692		rval = xfs_da3_split(state);
1693	}
1694done:
1695	xfs_da_state_free(state);
1696	return rval;
1697}
1698
1699/*
1700 * Add the data entry for a node-format directory name addition.
1701 * The leaf entry is added in xfs_dir2_leafn_add.
1702 * We may enter with a freespace block that the lookup found.
1703 */
1704static int					/* error */
1705xfs_dir2_node_addname_int(
1706	xfs_da_args_t		*args,		/* operation arguments */
1707	xfs_da_state_blk_t	*fblk)		/* optional freespace block */
1708{
1709	xfs_dir2_data_hdr_t	*hdr;		/* data block header */
1710	xfs_dir2_db_t		dbno;		/* data block number */
1711	struct xfs_buf		*dbp;		/* data block buffer */
1712	xfs_dir2_data_entry_t	*dep;		/* data entry pointer */
1713	xfs_inode_t		*dp;		/* incore directory inode */
1714	xfs_dir2_data_unused_t	*dup;		/* data unused entry pointer */
1715	int			error;		/* error return value */
1716	xfs_dir2_db_t		fbno;		/* freespace block number */
1717	struct xfs_buf		*fbp;		/* freespace buffer */
1718	int			findex;		/* freespace entry index */
1719	xfs_dir2_free_t		*free=NULL;	/* freespace block structure */
1720	xfs_dir2_db_t		ifbno;		/* initial freespace block no */
1721	xfs_dir2_db_t		lastfbno=0;	/* highest freespace block no */
1722	int			length;		/* length of the new entry */
1723	int			logfree;	/* need to log free entry */
1724	xfs_mount_t		*mp;		/* filesystem mount point */
1725	int			needlog;	/* need to log data header */
1726	int			needscan;	/* need to rescan data frees */
1727	__be16			*tagp;		/* data entry tag pointer */
1728	xfs_trans_t		*tp;		/* transaction pointer */
1729	__be16			*bests;
1730	struct xfs_dir3_icfree_hdr freehdr;
1731	struct xfs_dir2_data_free *bf;
1732	xfs_dir2_data_aoff_t	aoff;
1733
1734	dp = args->dp;
1735	mp = dp->i_mount;
1736	tp = args->trans;
1737	length = dp->d_ops->data_entsize(args->namelen);
1738	/*
1739	 * If we came in with a freespace block that means that lookup
1740	 * found an entry with our hash value.  This is the freespace
1741	 * block for that data entry.
1742	 */
1743	if (fblk) {
1744		fbp = fblk->bp;
1745		/*
1746		 * Remember initial freespace block number.
1747		 */
1748		ifbno = fblk->blkno;
1749		free = fbp->b_addr;
1750		findex = fblk->index;
1751		bests = dp->d_ops->free_bests_p(free);
1752		dp->d_ops->free_hdr_from_disk(&freehdr, free);
1753
1754		/*
1755		 * This means the free entry showed that the data block had
1756		 * space for our entry, so we remembered it.
1757		 * Use that data block.
1758		 */
1759		if (findex >= 0) {
1760			ASSERT(findex < freehdr.nvalid);
1761			ASSERT(be16_to_cpu(bests[findex]) != NULLDATAOFF);
1762			ASSERT(be16_to_cpu(bests[findex]) >= length);
1763			dbno = freehdr.firstdb + findex;
1764		} else {
1765			/*
1766			 * The data block looked at didn't have enough room.
1767			 * We'll start at the beginning of the freespace entries.
1768			 */
1769			dbno = -1;
1770			findex = 0;
1771		}
1772	} else {
1773		/*
1774		 * Didn't come in with a freespace block, so no data block.
1775		 */
1776		ifbno = dbno = -1;
1777		fbp = NULL;
1778		findex = 0;
1779	}
1780
1781	/*
1782	 * If we don't have a data block yet, we're going to scan the
1783	 * freespace blocks looking for one.  Figure out what the
1784	 * highest freespace block number is.
1785	 */
1786	if (dbno == -1) {
1787		xfs_fileoff_t	fo;		/* freespace block number */
1788
1789		if ((error = xfs_bmap_last_offset(dp, &fo, XFS_DATA_FORK)))
1790			return error;
1791		lastfbno = xfs_dir2_da_to_db(args->geo, (xfs_dablk_t)fo);
1792		fbno = ifbno;
1793	}
1794	/*
1795	 * While we haven't identified a data block, search the freeblock
1796	 * data for a good data block.  If we find a null freeblock entry,
1797	 * indicating a hole in the data blocks, remember that.
1798	 */
1799	while (dbno == -1) {
1800		/*
1801		 * If we don't have a freeblock in hand, get the next one.
1802		 */
1803		if (fbp == NULL) {
1804			/*
1805			 * Happens the first time through unless lookup gave
1806			 * us a freespace block to start with.
1807			 */
1808			if (++fbno == 0)
1809				fbno = xfs_dir2_byte_to_db(args->geo,
1810							XFS_DIR2_FREE_OFFSET);
1811			/*
1812			 * If it's ifbno we already looked at it.
1813			 */
1814			if (fbno == ifbno)
1815				fbno++;
1816			/*
1817			 * If it's off the end we're done.
1818			 */
1819			if (fbno >= lastfbno)
1820				break;
1821			/*
1822			 * Read the block.  There can be holes in the
1823			 * freespace blocks, so this might not succeed.
1824			 * This should be really rare, so there's no reason
1825			 * to avoid it.
1826			 */
1827			error = xfs_dir2_free_try_read(tp, dp,
1828					xfs_dir2_db_to_da(args->geo, fbno),
1829					&fbp);
1830			if (error)
1831				return error;
1832			if (!fbp)
1833				continue;
1834			free = fbp->b_addr;
1835			findex = 0;
1836		}
1837		/*
1838		 * Look at the current free entry.  Is it good enough?
1839		 *
1840		 * The bests initialisation should be where the bufer is read in
1841		 * the above branch. But gcc is too stupid to realise that bests
1842		 * and the freehdr are actually initialised if they are placed
1843		 * there, so we have to do it here to avoid warnings. Blech.
1844		 */
1845		bests = dp->d_ops->free_bests_p(free);
1846		dp->d_ops->free_hdr_from_disk(&freehdr, free);
1847		if (be16_to_cpu(bests[findex]) != NULLDATAOFF &&
1848		    be16_to_cpu(bests[findex]) >= length)
1849			dbno = freehdr.firstdb + findex;
1850		else {
1851			/*
1852			 * Are we done with the freeblock?
1853			 */
1854			if (++findex == freehdr.nvalid) {
1855				/*
1856				 * Drop the block.
1857				 */
1858				xfs_trans_brelse(tp, fbp);
1859				fbp = NULL;
1860				if (fblk && fblk->bp)
1861					fblk->bp = NULL;
1862			}
1863		}
1864	}
1865	/*
1866	 * If we don't have a data block, we need to allocate one and make
1867	 * the freespace entries refer to it.
1868	 */
1869	if (unlikely(dbno == -1)) {
1870		/*
1871		 * Not allowed to allocate, return failure.
1872		 */
1873		if ((args->op_flags & XFS_DA_OP_JUSTCHECK) || args->total == 0)
1874			return -ENOSPC;
1875
1876		/*
1877		 * Allocate and initialize the new data block.
1878		 */
1879		if (unlikely((error = xfs_dir2_grow_inode(args,
1880							 XFS_DIR2_DATA_SPACE,
1881							 &dbno)) ||
1882		    (error = xfs_dir3_data_init(args, dbno, &dbp))))
1883			return error;
1884
1885		/*
1886		 * If (somehow) we have a freespace block, get rid of it.
1887		 */
1888		if (fbp)
1889			xfs_trans_brelse(tp, fbp);
1890		if (fblk && fblk->bp)
1891			fblk->bp = NULL;
1892
1893		/*
1894		 * Get the freespace block corresponding to the data block
1895		 * that was just allocated.
1896		 */
1897		fbno = dp->d_ops->db_to_fdb(args->geo, dbno);
1898		error = xfs_dir2_free_try_read(tp, dp,
1899				       xfs_dir2_db_to_da(args->geo, fbno),
1900				       &fbp);
1901		if (error)
1902			return error;
1903
1904		/*
1905		 * If there wasn't a freespace block, the read will
1906		 * return a NULL fbp.  Allocate and initialize a new one.
1907		 */
1908		if (!fbp) {
1909			error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE,
1910						    &fbno);
1911			if (error)
1912				return error;
1913
1914			if (dp->d_ops->db_to_fdb(args->geo, dbno) != fbno) {
1915				xfs_alert(mp,
1916"%s: dir ino %llu needed freesp block %lld for data block %lld, got %lld ifbno %llu lastfbno %d",
1917					__func__, (unsigned long long)dp->i_ino,
1918					(long long)dp->d_ops->db_to_fdb(
1919								args->geo, dbno),
1920					(long long)dbno, (long long)fbno,
1921					(unsigned long long)ifbno, lastfbno);
1922				if (fblk) {
1923					xfs_alert(mp,
1924				" fblk "PTR_FMT" blkno %llu index %d magic 0x%x",
1925						fblk,
1926						(unsigned long long)fblk->blkno,
1927						fblk->index,
1928						fblk->magic);
1929				} else {
1930					xfs_alert(mp, " ... fblk is NULL");
1931				}
1932				XFS_ERROR_REPORT("xfs_dir2_node_addname_int",
1933						 XFS_ERRLEVEL_LOW, mp);
1934				return -EFSCORRUPTED;
1935			}
1936
1937			/*
1938			 * Get a buffer for the new block.
1939			 */
1940			error = xfs_dir3_free_get_buf(args, fbno, &fbp);
1941			if (error)
1942				return error;
1943			free = fbp->b_addr;
1944			bests = dp->d_ops->free_bests_p(free);
1945			dp->d_ops->free_hdr_from_disk(&freehdr, free);
1946
1947			/*
1948			 * Remember the first slot as our empty slot.
1949			 */
1950			freehdr.firstdb =
1951				(fbno - xfs_dir2_byte_to_db(args->geo,
1952							XFS_DIR2_FREE_OFFSET)) *
1953					dp->d_ops->free_max_bests(args->geo);
1954		} else {
1955			free = fbp->b_addr;
1956			bests = dp->d_ops->free_bests_p(free);
1957			dp->d_ops->free_hdr_from_disk(&freehdr, free);
1958		}
1959
1960		/*
1961		 * Set the freespace block index from the data block number.
1962		 */
1963		findex = dp->d_ops->db_to_fdindex(args->geo, dbno);
1964		/*
1965		 * If it's after the end of the current entries in the
1966		 * freespace block, extend that table.
1967		 */
1968		if (findex >= freehdr.nvalid) {
1969			ASSERT(findex < dp->d_ops->free_max_bests(args->geo));
1970			freehdr.nvalid = findex + 1;
1971			/*
1972			 * Tag new entry so nused will go up.
1973			 */
1974			bests[findex] = cpu_to_be16(NULLDATAOFF);
1975		}
1976		/*
1977		 * If this entry was for an empty data block
1978		 * (this should always be true) then update the header.
1979		 */
1980		if (bests[findex] == cpu_to_be16(NULLDATAOFF)) {
1981			freehdr.nused++;
1982			dp->d_ops->free_hdr_to_disk(fbp->b_addr, &freehdr);
1983			xfs_dir2_free_log_header(args, fbp);
1984		}
1985		/*
1986		 * Update the real value in the table.
1987		 * We haven't allocated the data entry yet so this will
1988		 * change again.
1989		 */
1990		hdr = dbp->b_addr;
1991		bf = dp->d_ops->data_bestfree_p(hdr);
1992		bests[findex] = bf[0].length;
1993		logfree = 1;
1994	}
1995	/*
1996	 * We had a data block so we don't have to make a new one.
1997	 */
1998	else {
1999		/*
2000		 * If just checking, we succeeded.
2001		 */
2002		if (args->op_flags & XFS_DA_OP_JUSTCHECK)
2003			return 0;
2004
2005		/*
2006		 * Read the data block in.
2007		 */
2008		error = xfs_dir3_data_read(tp, dp,
2009					   xfs_dir2_db_to_da(args->geo, dbno),
2010					   -1, &dbp);
2011		if (error)
2012			return error;
2013		hdr = dbp->b_addr;
2014		bf = dp->d_ops->data_bestfree_p(hdr);
2015		logfree = 0;
2016	}
2017	ASSERT(be16_to_cpu(bf[0].length) >= length);
2018	/*
2019	 * Point to the existing unused space.
2020	 */
2021	dup = (xfs_dir2_data_unused_t *)
2022	      ((char *)hdr + be16_to_cpu(bf[0].offset));
2023	needscan = needlog = 0;
2024	/*
2025	 * Mark the first part of the unused space, inuse for us.
2026	 */
2027	aoff = (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr);
2028	error = xfs_dir2_data_use_free(args, dbp, dup, aoff, length,
2029			&needlog, &needscan);
2030	if (error) {
2031		xfs_trans_brelse(tp, dbp);
2032		return error;
2033	}
2034	/*
2035	 * Fill in the new entry and log it.
2036	 */
2037	dep = (xfs_dir2_data_entry_t *)dup;
2038	dep->inumber = cpu_to_be64(args->inumber);
2039	dep->namelen = args->namelen;
2040	memcpy(dep->name, args->name, dep->namelen);
2041	dp->d_ops->data_put_ftype(dep, args->filetype);
2042	tagp = dp->d_ops->data_entry_tag_p(dep);
2043	*tagp = cpu_to_be16((char *)dep - (char *)hdr);
2044	xfs_dir2_data_log_entry(args, dbp, dep);
2045	/*
2046	 * Rescan the block for bestfree if needed.
2047	 */
2048	if (needscan)
2049		xfs_dir2_data_freescan(dp, hdr, &needlog);
2050	/*
2051	 * Log the data block header if needed.
2052	 */
2053	if (needlog)
2054		xfs_dir2_data_log_header(args, dbp);
2055	/*
2056	 * If the freespace entry is now wrong, update it.
2057	 */
2058	bests = dp->d_ops->free_bests_p(free); /* gcc is so stupid */
2059	if (be16_to_cpu(bests[findex]) != be16_to_cpu(bf[0].length)) {
2060		bests[findex] = bf[0].length;
2061		logfree = 1;
2062	}
2063	/*
2064	 * Log the freespace entry if needed.
2065	 */
2066	if (logfree)
2067		xfs_dir2_free_log_bests(args, fbp, findex, findex);
2068	/*
2069	 * Return the data block and offset in args, then drop the data block.
2070	 */
2071	args->blkno = (xfs_dablk_t)dbno;
2072	args->index = be16_to_cpu(*tagp);
2073	return 0;
2074}
2075
2076/*
2077 * Lookup an entry in a node-format directory.
2078 * All the real work happens in xfs_da3_node_lookup_int.
2079 * The only real output is the inode number of the entry.
2080 */
2081int						/* error */
2082xfs_dir2_node_lookup(
2083	xfs_da_args_t	*args)			/* operation arguments */
2084{
2085	int		error;			/* error return value */
2086	int		i;			/* btree level */
2087	int		rval;			/* operation return value */
2088	xfs_da_state_t	*state;			/* btree cursor */
2089
2090	trace_xfs_dir2_node_lookup(args);
2091
2092	/*
2093	 * Allocate and initialize the btree cursor.
2094	 */
2095	state = xfs_da_state_alloc();
2096	state->args = args;
2097	state->mp = args->dp->i_mount;
2098	/*
2099	 * Fill in the path to the entry in the cursor.
2100	 */
2101	error = xfs_da3_node_lookup_int(state, &rval);
2102	if (error)
2103		rval = error;
2104	else if (rval == -ENOENT && args->cmpresult == XFS_CMP_CASE) {
2105		/* If a CI match, dup the actual name and return -EEXIST */
2106		xfs_dir2_data_entry_t	*dep;
2107
2108		dep = (xfs_dir2_data_entry_t *)
2109			((char *)state->extrablk.bp->b_addr +
2110						 state->extrablk.index);
2111		rval = xfs_dir_cilookup_result(args, dep->name, dep->namelen);
2112	}
2113	/*
2114	 * Release the btree blocks and leaf block.
2115	 */
2116	for (i = 0; i < state->path.active; i++) {
2117		xfs_trans_brelse(args->trans, state->path.blk[i].bp);
2118		state->path.blk[i].bp = NULL;
2119	}
2120	/*
2121	 * Release the data block if we have it.
2122	 */
2123	if (state->extravalid && state->extrablk.bp) {
2124		xfs_trans_brelse(args->trans, state->extrablk.bp);
2125		state->extrablk.bp = NULL;
2126	}
2127	xfs_da_state_free(state);
2128	return rval;
2129}
2130
2131/*
2132 * Remove an entry from a node-format directory.
2133 */
2134int						/* error */
2135xfs_dir2_node_removename(
2136	struct xfs_da_args	*args)		/* operation arguments */
2137{
2138	struct xfs_da_state_blk	*blk;		/* leaf block */
2139	int			error;		/* error return value */
2140	int			rval;		/* operation return value */
2141	struct xfs_da_state	*state;		/* btree cursor */
2142
2143	trace_xfs_dir2_node_removename(args);
2144
2145	/*
2146	 * Allocate and initialize the btree cursor.
2147	 */
2148	state = xfs_da_state_alloc();
2149	state->args = args;
2150	state->mp = args->dp->i_mount;
2151
2152	/* Look up the entry we're deleting, set up the cursor. */
2153	error = xfs_da3_node_lookup_int(state, &rval);
2154	if (error)
2155		goto out_free;
2156
2157	/* Didn't find it, upper layer screwed up. */
2158	if (rval != -EEXIST) {
2159		error = rval;
2160		goto out_free;
2161	}
2162
2163	blk = &state->path.blk[state->path.active - 1];
2164	ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
2165	ASSERT(state->extravalid);
2166	/*
2167	 * Remove the leaf and data entries.
2168	 * Extrablk refers to the data block.
2169	 */
2170	error = xfs_dir2_leafn_remove(args, blk->bp, blk->index,
2171		&state->extrablk, &rval);
2172	if (error)
2173		goto out_free;
2174	/*
2175	 * Fix the hash values up the btree.
2176	 */
2177	xfs_da3_fixhashpath(state, &state->path);
2178	/*
2179	 * If we need to join leaf blocks, do it.
2180	 */
2181	if (rval && state->path.active > 1)
2182		error = xfs_da3_join(state);
2183	/*
2184	 * If no errors so far, try conversion to leaf format.
2185	 */
2186	if (!error)
2187		error = xfs_dir2_node_to_leaf(state);
2188out_free:
2189	xfs_da_state_free(state);
2190	return error;
2191}
2192
2193/*
2194 * Replace an entry's inode number in a node-format directory.
2195 */
2196int						/* error */
2197xfs_dir2_node_replace(
2198	xfs_da_args_t		*args)		/* operation arguments */
2199{
2200	xfs_da_state_blk_t	*blk;		/* leaf block */
2201	xfs_dir2_data_hdr_t	*hdr;		/* data block header */
2202	xfs_dir2_data_entry_t	*dep;		/* data entry changed */
2203	int			error;		/* error return value */
2204	int			i;		/* btree level */
2205	xfs_ino_t		inum;		/* new inode number */
2206	int			ftype;		/* new file type */
2207	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
2208	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry being changed */
2209	int			rval;		/* internal return value */
2210	xfs_da_state_t		*state;		/* btree cursor */
2211
2212	trace_xfs_dir2_node_replace(args);
2213
2214	/*
2215	 * Allocate and initialize the btree cursor.
2216	 */
2217	state = xfs_da_state_alloc();
2218	state->args = args;
2219	state->mp = args->dp->i_mount;
2220
2221	/*
2222	 * We have to save new inode number and ftype since
2223	 * xfs_da3_node_lookup_int() is going to overwrite them
2224	 */
2225	inum = args->inumber;
2226	ftype = args->filetype;
2227
2228	/*
2229	 * Lookup the entry to change in the btree.
2230	 */
2231	error = xfs_da3_node_lookup_int(state, &rval);
2232	if (error) {
2233		rval = error;
2234	}
2235	/*
2236	 * It should be found, since the vnodeops layer has looked it up
2237	 * and locked it.  But paranoia is good.
2238	 */
2239	if (rval == -EEXIST) {
2240		struct xfs_dir2_leaf_entry *ents;
2241		/*
2242		 * Find the leaf entry.
2243		 */
2244		blk = &state->path.blk[state->path.active - 1];
2245		ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
2246		leaf = blk->bp->b_addr;
2247		ents = args->dp->d_ops->leaf_ents_p(leaf);
2248		lep = &ents[blk->index];
2249		ASSERT(state->extravalid);
2250		/*
2251		 * Point to the data entry.
2252		 */
2253		hdr = state->extrablk.bp->b_addr;
2254		ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
2255		       hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC));
2256		dep = (xfs_dir2_data_entry_t *)
2257		      ((char *)hdr +
2258		       xfs_dir2_dataptr_to_off(args->geo,
2259					       be32_to_cpu(lep->address)));
2260		ASSERT(inum != be64_to_cpu(dep->inumber));
2261		/*
2262		 * Fill in the new inode number and log the entry.
2263		 */
2264		dep->inumber = cpu_to_be64(inum);
2265		args->dp->d_ops->data_put_ftype(dep, ftype);
2266		xfs_dir2_data_log_entry(args, state->extrablk.bp, dep);
2267		rval = 0;
2268	}
2269	/*
2270	 * Didn't find it, and we're holding a data block.  Drop it.
2271	 */
2272	else if (state->extravalid) {
2273		xfs_trans_brelse(args->trans, state->extrablk.bp);
2274		state->extrablk.bp = NULL;
2275	}
2276	/*
2277	 * Release all the buffers in the cursor.
2278	 */
2279	for (i = 0; i < state->path.active; i++) {
2280		xfs_trans_brelse(args->trans, state->path.blk[i].bp);
2281		state->path.blk[i].bp = NULL;
2282	}
2283	xfs_da_state_free(state);
2284	return rval;
2285}
2286
2287/*
2288 * Trim off a trailing empty freespace block.
2289 * Return (in rvalp) 1 if we did it, 0 if not.
2290 */
2291int						/* error */
2292xfs_dir2_node_trim_free(
2293	xfs_da_args_t		*args,		/* operation arguments */
2294	xfs_fileoff_t		fo,		/* free block number */
2295	int			*rvalp)		/* out: did something */
2296{
2297	struct xfs_buf		*bp;		/* freespace buffer */
2298	xfs_inode_t		*dp;		/* incore directory inode */
2299	int			error;		/* error return code */
2300	xfs_dir2_free_t		*free;		/* freespace structure */
2301	xfs_trans_t		*tp;		/* transaction pointer */
2302	struct xfs_dir3_icfree_hdr freehdr;
2303
2304	dp = args->dp;
2305	tp = args->trans;
2306
2307	*rvalp = 0;
2308
2309	/*
2310	 * Read the freespace block.
2311	 */
2312	error = xfs_dir2_free_try_read(tp, dp, fo, &bp);
2313	if (error)
2314		return error;
2315	/*
2316	 * There can be holes in freespace.  If fo is a hole, there's
2317	 * nothing to do.
2318	 */
2319	if (!bp)
2320		return 0;
2321	free = bp->b_addr;
2322	dp->d_ops->free_hdr_from_disk(&freehdr, free);
2323
2324	/*
2325	 * If there are used entries, there's nothing to do.
2326	 */
2327	if (freehdr.nused > 0) {
2328		xfs_trans_brelse(tp, bp);
2329		return 0;
2330	}
2331	/*
2332	 * Blow the block away.
2333	 */
2334	error = xfs_dir2_shrink_inode(args,
2335			xfs_dir2_da_to_db(args->geo, (xfs_dablk_t)fo), bp);
2336	if (error) {
2337		/*
2338		 * Can't fail with ENOSPC since that only happens with no
2339		 * space reservation, when breaking up an extent into two
2340		 * pieces.  This is the last block of an extent.
2341		 */
2342		ASSERT(error != -ENOSPC);
2343		xfs_trans_brelse(tp, bp);
2344		return error;
2345	}
2346	/*
2347	 * Return that we succeeded.
2348	 */
2349	*rvalp = 1;
2350	return 0;
2351}