1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
   4 * Copyright (c) 2013 Red Hat, Inc.
   5 * All Rights Reserved.
 
 
 
 
 
 
 
 
 
 
 
 
 
   6 */
   7#include "xfs.h"
   8#include "xfs_fs.h"
   9#include "xfs_shared.h"
  10#include "xfs_format.h"
  11#include "xfs_log_format.h"
  12#include "xfs_trans_resv.h"
  13#include "xfs_mount.h"
 
 
  14#include "xfs_inode.h"
  15#include "xfs_bmap.h"
  16#include "xfs_dir2.h"
  17#include "xfs_dir2_priv.h"
  18#include "xfs_error.h"
  19#include "xfs_trace.h"
  20#include "xfs_trans.h"
  21#include "xfs_buf_item.h"
 
 
  22
  23/*
  24 * Local function declarations.
  25 */
  26static int xfs_dir2_leaf_lookup_int(xfs_da_args_t *args, struct xfs_buf **lbpp,
  27				    int *indexp, struct xfs_buf **dbpp,
  28				    struct xfs_dir3_icleaf_hdr *leafhdr);
  29static void xfs_dir3_leaf_log_bests(struct xfs_da_args *args,
  30				    struct xfs_buf *bp, int first, int last);
  31static void xfs_dir3_leaf_log_tail(struct xfs_da_args *args,
  32				   struct xfs_buf *bp);
  33
  34void
  35xfs_dir2_leaf_hdr_from_disk(
  36	struct xfs_mount		*mp,
  37	struct xfs_dir3_icleaf_hdr	*to,
  38	struct xfs_dir2_leaf		*from)
  39{
  40	if (xfs_has_crc(mp)) {
  41		struct xfs_dir3_leaf *from3 = (struct xfs_dir3_leaf *)from;
  42
  43		to->forw = be32_to_cpu(from3->hdr.info.hdr.forw);
  44		to->back = be32_to_cpu(from3->hdr.info.hdr.back);
  45		to->magic = be16_to_cpu(from3->hdr.info.hdr.magic);
  46		to->count = be16_to_cpu(from3->hdr.count);
  47		to->stale = be16_to_cpu(from3->hdr.stale);
  48		to->ents = from3->__ents;
  49
  50		ASSERT(to->magic == XFS_DIR3_LEAF1_MAGIC ||
  51		       to->magic == XFS_DIR3_LEAFN_MAGIC);
  52	} else {
  53		to->forw = be32_to_cpu(from->hdr.info.forw);
  54		to->back = be32_to_cpu(from->hdr.info.back);
  55		to->magic = be16_to_cpu(from->hdr.info.magic);
  56		to->count = be16_to_cpu(from->hdr.count);
  57		to->stale = be16_to_cpu(from->hdr.stale);
  58		to->ents = from->__ents;
  59
  60		ASSERT(to->magic == XFS_DIR2_LEAF1_MAGIC ||
  61		       to->magic == XFS_DIR2_LEAFN_MAGIC);
  62	}
  63}
  64
  65void
  66xfs_dir2_leaf_hdr_to_disk(
  67	struct xfs_mount		*mp,
  68	struct xfs_dir2_leaf		*to,
  69	struct xfs_dir3_icleaf_hdr	*from)
  70{
  71	if (xfs_has_crc(mp)) {
  72		struct xfs_dir3_leaf *to3 = (struct xfs_dir3_leaf *)to;
  73
  74		ASSERT(from->magic == XFS_DIR3_LEAF1_MAGIC ||
  75		       from->magic == XFS_DIR3_LEAFN_MAGIC);
  76
  77		to3->hdr.info.hdr.forw = cpu_to_be32(from->forw);
  78		to3->hdr.info.hdr.back = cpu_to_be32(from->back);
  79		to3->hdr.info.hdr.magic = cpu_to_be16(from->magic);
  80		to3->hdr.count = cpu_to_be16(from->count);
  81		to3->hdr.stale = cpu_to_be16(from->stale);
  82	} else {
  83		ASSERT(from->magic == XFS_DIR2_LEAF1_MAGIC ||
  84		       from->magic == XFS_DIR2_LEAFN_MAGIC);
  85
  86		to->hdr.info.forw = cpu_to_be32(from->forw);
  87		to->hdr.info.back = cpu_to_be32(from->back);
  88		to->hdr.info.magic = cpu_to_be16(from->magic);
  89		to->hdr.count = cpu_to_be16(from->count);
  90		to->hdr.stale = cpu_to_be16(from->stale);
  91	}
  92}
  93
  94/*
  95 * Check the internal consistency of a leaf1 block.
  96 * Pop an assert if something is wrong.
  97 */
  98#ifdef DEBUG
  99static xfs_failaddr_t
 
 
 
 
 
 
 100xfs_dir3_leaf1_check(
 101	struct xfs_inode	*dp,
 102	struct xfs_buf		*bp)
 103{
 104	struct xfs_dir2_leaf	*leaf = bp->b_addr;
 105	struct xfs_dir3_icleaf_hdr leafhdr;
 106
 107	xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf);
 108
 109	if (leafhdr.magic == XFS_DIR3_LEAF1_MAGIC) {
 110		struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
 111		if (be64_to_cpu(leaf3->info.blkno) != xfs_buf_daddr(bp))
 112			return __this_address;
 113	} else if (leafhdr.magic != XFS_DIR2_LEAF1_MAGIC)
 114		return __this_address;
 115
 116	return xfs_dir3_leaf_check_int(dp->i_mount, &leafhdr, leaf, false);
 117}
 118
 119static inline void
 120xfs_dir3_leaf_check(
 121	struct xfs_inode	*dp,
 122	struct xfs_buf		*bp)
 123{
 124	xfs_failaddr_t		fa;
 125
 126	fa = xfs_dir3_leaf1_check(dp, bp);
 127	if (!fa)
 128		return;
 129	xfs_corruption_error(__func__, XFS_ERRLEVEL_LOW, dp->i_mount,
 130			bp->b_addr, BBTOB(bp->b_length), __FILE__, __LINE__,
 131			fa);
 132	ASSERT(0);
 133}
 134#else
 135#define	xfs_dir3_leaf_check(dp, bp)
 136#endif
 137
 138xfs_failaddr_t
 139xfs_dir3_leaf_check_int(
 140	struct xfs_mount		*mp,
 141	struct xfs_dir3_icleaf_hdr	*hdr,
 142	struct xfs_dir2_leaf		*leaf,
 143	bool				expensive_checking)
 144{
 145	struct xfs_da_geometry		*geo = mp->m_dir_geo;
 146	xfs_dir2_leaf_tail_t		*ltp;
 147	int				stale;
 148	int				i;
 149	bool				isleaf1 = (hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
 150						   hdr->magic == XFS_DIR3_LEAF1_MAGIC);
 
 
 
 
 
 
 
 
 
 
 
 
 151
 
 152	ltp = xfs_dir2_leaf_tail_p(geo, leaf);
 153
 154	/*
 155	 * XXX (dgc): This value is not restrictive enough.
 156	 * Should factor in the size of the bests table as well.
 157	 * We can deduce a value for that from i_disk_size.
 158	 */
 159	if (hdr->count > geo->leaf_max_ents)
 160		return __this_address;
 161
 162	/* Leaves and bests don't overlap in leaf format. */
 163	if (isleaf1 &&
 164	    (char *)&hdr->ents[hdr->count] > (char *)xfs_dir2_leaf_bests_p(ltp))
 165		return __this_address;
 166
 167	if (!expensive_checking)
 168		return NULL;
 169
 170	/* Check hash value order, count stale entries.  */
 171	for (i = stale = 0; i < hdr->count; i++) {
 172		if (i + 1 < hdr->count) {
 173			if (be32_to_cpu(hdr->ents[i].hashval) >
 174					be32_to_cpu(hdr->ents[i + 1].hashval))
 175				return __this_address;
 176		}
 177		if (hdr->ents[i].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
 178			stale++;
 179		if (isleaf1 && xfs_dir2_dataptr_to_db(geo,
 180				be32_to_cpu(hdr->ents[i].address)) >=
 181				be32_to_cpu(ltp->bestcount))
 182			return __this_address;
 183	}
 184	if (hdr->stale != stale)
 185		return __this_address;
 186	return NULL;
 187}
 188
 189/*
 190 * We verify the magic numbers before decoding the leaf header so that on debug
 191 * kernels we don't get assertion failures in xfs_dir3_leaf_hdr_from_disk() due
 192 * to incorrect magic numbers.
 193 */
 194static xfs_failaddr_t
 195xfs_dir3_leaf_verify(
 196	struct xfs_buf			*bp)
 
 197{
 198	struct xfs_mount		*mp = bp->b_mount;
 199	struct xfs_dir3_icleaf_hdr	leafhdr;
 200	xfs_failaddr_t			fa;
 201
 202	fa = xfs_da3_blkinfo_verify(bp, bp->b_addr);
 203	if (fa)
 204		return fa;
 
 
 
 
 205
 206	xfs_dir2_leaf_hdr_from_disk(mp, &leafhdr, bp->b_addr);
 207	return xfs_dir3_leaf_check_int(mp, &leafhdr, bp->b_addr, true);
 
 
 
 
 
 
 
 
 
 
 
 
 208}
 209
 210static void
 211xfs_dir3_leaf_read_verify(
 212	struct xfs_buf  *bp)
 
 213{
 214	struct xfs_mount	*mp = bp->b_mount;
 215	xfs_failaddr_t		fa;
 216
 217	if (xfs_has_crc(mp) &&
 218	     !xfs_buf_verify_cksum(bp, XFS_DIR3_LEAF_CRC_OFF))
 219		xfs_verifier_error(bp, -EFSBADCRC, __this_address);
 220	else {
 221		fa = xfs_dir3_leaf_verify(bp);
 222		if (fa)
 223			xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 224	}
 225}
 226
 227static void
 228xfs_dir3_leaf_write_verify(
 229	struct xfs_buf  *bp)
 
 230{
 231	struct xfs_mount	*mp = bp->b_mount;
 232	struct xfs_buf_log_item	*bip = bp->b_log_item;
 233	struct xfs_dir3_leaf_hdr *hdr3 = bp->b_addr;
 234	xfs_failaddr_t		fa;
 235
 236	fa = xfs_dir3_leaf_verify(bp);
 237	if (fa) {
 238		xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 239		return;
 240	}
 241
 242	if (!xfs_has_crc(mp))
 243		return;
 244
 245	if (bip)
 246		hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
 247
 248	xfs_buf_update_cksum(bp, XFS_DIR3_LEAF_CRC_OFF);
 249}
 250
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 251const struct xfs_buf_ops xfs_dir3_leaf1_buf_ops = {
 252	.name = "xfs_dir3_leaf1",
 253	.magic16 = { cpu_to_be16(XFS_DIR2_LEAF1_MAGIC),
 254		     cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) },
 255	.verify_read = xfs_dir3_leaf_read_verify,
 256	.verify_write = xfs_dir3_leaf_write_verify,
 257	.verify_struct = xfs_dir3_leaf_verify,
 258};
 259
 260const struct xfs_buf_ops xfs_dir3_leafn_buf_ops = {
 261	.name = "xfs_dir3_leafn",
 262	.magic16 = { cpu_to_be16(XFS_DIR2_LEAFN_MAGIC),
 263		     cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) },
 264	.verify_read = xfs_dir3_leaf_read_verify,
 265	.verify_write = xfs_dir3_leaf_write_verify,
 266	.verify_struct = xfs_dir3_leaf_verify,
 267};
 268
 269int
 270xfs_dir3_leaf_read(
 271	struct xfs_trans	*tp,
 272	struct xfs_inode	*dp,
 273	xfs_dablk_t		fbno,
 
 274	struct xfs_buf		**bpp)
 275{
 276	int			err;
 277
 278	err = xfs_da_read_buf(tp, dp, fbno, 0, bpp, XFS_DATA_FORK,
 279			&xfs_dir3_leaf1_buf_ops);
 280	if (!err && tp && *bpp)
 281		xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAF1_BUF);
 282	return err;
 283}
 284
 285int
 286xfs_dir3_leafn_read(
 287	struct xfs_trans	*tp,
 288	struct xfs_inode	*dp,
 289	xfs_dablk_t		fbno,
 
 290	struct xfs_buf		**bpp)
 291{
 292	int			err;
 293
 294	err = xfs_da_read_buf(tp, dp, fbno, 0, bpp, XFS_DATA_FORK,
 295			&xfs_dir3_leafn_buf_ops);
 296	if (!err && tp && *bpp)
 297		xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAFN_BUF);
 298	return err;
 299}
 300
 301/*
 302 * Initialize a new leaf block, leaf1 or leafn magic accepted.
 303 */
 304static void
 305xfs_dir3_leaf_init(
 306	struct xfs_mount	*mp,
 307	struct xfs_trans	*tp,
 308	struct xfs_buf		*bp,
 309	xfs_ino_t		owner,
 310	uint16_t		type)
 311{
 312	struct xfs_dir2_leaf	*leaf = bp->b_addr;
 313
 314	ASSERT(type == XFS_DIR2_LEAF1_MAGIC || type == XFS_DIR2_LEAFN_MAGIC);
 315
 316	if (xfs_has_crc(mp)) {
 317		struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
 318
 319		memset(leaf3, 0, sizeof(*leaf3));
 320
 321		leaf3->info.hdr.magic = (type == XFS_DIR2_LEAF1_MAGIC)
 322					 ? cpu_to_be16(XFS_DIR3_LEAF1_MAGIC)
 323					 : cpu_to_be16(XFS_DIR3_LEAFN_MAGIC);
 324		leaf3->info.blkno = cpu_to_be64(xfs_buf_daddr(bp));
 325		leaf3->info.owner = cpu_to_be64(owner);
 326		uuid_copy(&leaf3->info.uuid, &mp->m_sb.sb_meta_uuid);
 327	} else {
 328		memset(leaf, 0, sizeof(*leaf));
 329		leaf->hdr.info.magic = cpu_to_be16(type);
 330	}
 331
 332	/*
 333	 * If it's a leaf-format directory initialize the tail.
 334	 * Caller is responsible for initialising the bests table.
 335	 */
 336	if (type == XFS_DIR2_LEAF1_MAGIC) {
 337		struct xfs_dir2_leaf_tail *ltp;
 338
 339		ltp = xfs_dir2_leaf_tail_p(mp->m_dir_geo, leaf);
 340		ltp->bestcount = 0;
 341		bp->b_ops = &xfs_dir3_leaf1_buf_ops;
 342		xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAF1_BUF);
 343	} else {
 344		bp->b_ops = &xfs_dir3_leafn_buf_ops;
 345		xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
 346	}
 347}
 348
 349int
 350xfs_dir3_leaf_get_buf(
 351	xfs_da_args_t		*args,
 352	xfs_dir2_db_t		bno,
 353	struct xfs_buf		**bpp,
 354	uint16_t		magic)
 355{
 356	struct xfs_inode	*dp = args->dp;
 357	struct xfs_trans	*tp = args->trans;
 358	struct xfs_mount	*mp = dp->i_mount;
 359	struct xfs_buf		*bp;
 360	int			error;
 361
 362	ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC);
 363	ASSERT(bno >= xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET) &&
 364	       bno < xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET));
 365
 366	error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(args->geo, bno),
 367			       &bp, XFS_DATA_FORK);
 368	if (error)
 369		return error;
 370
 371	xfs_dir3_leaf_init(mp, tp, bp, dp->i_ino, magic);
 372	xfs_dir3_leaf_log_header(args, bp);
 373	if (magic == XFS_DIR2_LEAF1_MAGIC)
 374		xfs_dir3_leaf_log_tail(args, bp);
 375	*bpp = bp;
 376	return 0;
 377}
 378
 379/*
 380 * Convert a block form directory to a leaf form directory.
 381 */
 382int						/* error */
 383xfs_dir2_block_to_leaf(
 384	xfs_da_args_t		*args,		/* operation arguments */
 385	struct xfs_buf		*dbp)		/* input block's buffer */
 386{
 387	__be16			*bestsp;	/* leaf's bestsp entries */
 388	xfs_dablk_t		blkno;		/* leaf block's bno */
 389	xfs_dir2_data_hdr_t	*hdr;		/* block header */
 390	xfs_dir2_leaf_entry_t	*blp;		/* block's leaf entries */
 391	xfs_dir2_block_tail_t	*btp;		/* block's tail */
 392	xfs_inode_t		*dp;		/* incore directory inode */
 393	int			error;		/* error return code */
 394	struct xfs_buf		*lbp;		/* leaf block's buffer */
 395	xfs_dir2_db_t		ldb;		/* leaf block's bno */
 396	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
 397	xfs_dir2_leaf_tail_t	*ltp;		/* leaf's tail */
 398	int			needlog;	/* need to log block header */
 399	int			needscan;	/* need to rescan bestfree */
 400	xfs_trans_t		*tp;		/* transaction pointer */
 401	struct xfs_dir2_data_free *bf;
 
 402	struct xfs_dir3_icleaf_hdr leafhdr;
 403
 404	trace_xfs_dir2_block_to_leaf(args);
 405
 406	dp = args->dp;
 407	tp = args->trans;
 408	/*
 409	 * Add the leaf block to the inode.
 410	 * This interface will only put blocks in the leaf/node range.
 411	 * Since that's empty now, we'll get the root (block 0 in range).
 412	 */
 413	if ((error = xfs_da_grow_inode(args, &blkno))) {
 414		return error;
 415	}
 416	ldb = xfs_dir2_da_to_db(args->geo, blkno);
 417	ASSERT(ldb == xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET));
 418	/*
 419	 * Initialize the leaf block, get a buffer for it.
 420	 */
 421	error = xfs_dir3_leaf_get_buf(args, ldb, &lbp, XFS_DIR2_LEAF1_MAGIC);
 422	if (error)
 423		return error;
 424
 425	leaf = lbp->b_addr;
 426	hdr = dbp->b_addr;
 427	xfs_dir3_data_check(dp, dbp);
 428	btp = xfs_dir2_block_tail_p(args->geo, hdr);
 429	blp = xfs_dir2_block_leaf_p(btp);
 430	bf = xfs_dir2_data_bestfree_p(dp->i_mount, hdr);
 
 431
 432	/*
 433	 * Set the counts in the leaf header.
 434	 */
 435	xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf);
 436	leafhdr.count = be32_to_cpu(btp->count);
 437	leafhdr.stale = be32_to_cpu(btp->stale);
 438	xfs_dir2_leaf_hdr_to_disk(dp->i_mount, leaf, &leafhdr);
 439	xfs_dir3_leaf_log_header(args, lbp);
 440
 441	/*
 442	 * Could compact these but I think we always do the conversion
 443	 * after squeezing out stale entries.
 444	 */
 445	memcpy(leafhdr.ents, blp,
 446		be32_to_cpu(btp->count) * sizeof(struct xfs_dir2_leaf_entry));
 447	xfs_dir3_leaf_log_ents(args, &leafhdr, lbp, 0, leafhdr.count - 1);
 448	needscan = 0;
 449	needlog = 1;
 450	/*
 451	 * Make the space formerly occupied by the leaf entries and block
 452	 * tail be free.
 453	 */
 454	xfs_dir2_data_make_free(args, dbp,
 455		(xfs_dir2_data_aoff_t)((char *)blp - (char *)hdr),
 456		(xfs_dir2_data_aoff_t)((char *)hdr + args->geo->blksize -
 457				       (char *)blp),
 458		&needlog, &needscan);
 459	/*
 460	 * Fix up the block header, make it a data block.
 461	 */
 462	dbp->b_ops = &xfs_dir3_data_buf_ops;
 463	xfs_trans_buf_set_type(tp, dbp, XFS_BLFT_DIR_DATA_BUF);
 464	if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC))
 465		hdr->magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC);
 466	else
 467		hdr->magic = cpu_to_be32(XFS_DIR3_DATA_MAGIC);
 468
 469	if (needscan)
 470		xfs_dir2_data_freescan(dp->i_mount, hdr, &needlog);
 471	/*
 472	 * Set up leaf tail and bests table.
 473	 */
 474	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
 475	ltp->bestcount = cpu_to_be32(1);
 476	bestsp = xfs_dir2_leaf_bests_p(ltp);
 477	bestsp[0] =  bf[0].length;
 478	/*
 479	 * Log the data header and leaf bests table.
 480	 */
 481	if (needlog)
 482		xfs_dir2_data_log_header(args, dbp);
 483	xfs_dir3_leaf_check(dp, lbp);
 484	xfs_dir3_data_check(dp, dbp);
 485	xfs_dir3_leaf_log_bests(args, lbp, 0, 0);
 486	return 0;
 487}
 488
 489STATIC void
 490xfs_dir3_leaf_find_stale(
 491	struct xfs_dir3_icleaf_hdr *leafhdr,
 492	struct xfs_dir2_leaf_entry *ents,
 493	int			index,
 494	int			*lowstale,
 495	int			*highstale)
 496{
 497	/*
 498	 * Find the first stale entry before our index, if any.
 499	 */
 500	for (*lowstale = index - 1; *lowstale >= 0; --*lowstale) {
 501		if (ents[*lowstale].address ==
 502		    cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
 503			break;
 504	}
 505
 506	/*
 507	 * Find the first stale entry at or after our index, if any.
 508	 * Stop if the result would require moving more entries than using
 509	 * lowstale.
 510	 */
 511	for (*highstale = index; *highstale < leafhdr->count; ++*highstale) {
 512		if (ents[*highstale].address ==
 513		    cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
 514			break;
 515		if (*lowstale >= 0 && index - *lowstale <= *highstale - index)
 516			break;
 517	}
 518}
 519
 520struct xfs_dir2_leaf_entry *
 521xfs_dir3_leaf_find_entry(
 522	struct xfs_dir3_icleaf_hdr *leafhdr,
 523	struct xfs_dir2_leaf_entry *ents,
 524	int			index,		/* leaf table position */
 525	int			compact,	/* need to compact leaves */
 526	int			lowstale,	/* index of prev stale leaf */
 527	int			highstale,	/* index of next stale leaf */
 528	int			*lfloglow,	/* low leaf logging index */
 529	int			*lfloghigh)	/* high leaf logging index */
 530{
 531	if (!leafhdr->stale) {
 532		xfs_dir2_leaf_entry_t	*lep;	/* leaf entry table pointer */
 533
 534		/*
 535		 * Now we need to make room to insert the leaf entry.
 536		 *
 537		 * If there are no stale entries, just insert a hole at index.
 538		 */
 539		lep = &ents[index];
 540		if (index < leafhdr->count)
 541			memmove(lep + 1, lep,
 542				(leafhdr->count - index) * sizeof(*lep));
 543
 544		/*
 545		 * Record low and high logging indices for the leaf.
 546		 */
 547		*lfloglow = index;
 548		*lfloghigh = leafhdr->count++;
 549		return lep;
 550	}
 551
 552	/*
 553	 * There are stale entries.
 554	 *
 555	 * We will use one of them for the new entry.  It's probably not at
 556	 * the right location, so we'll have to shift some up or down first.
 557	 *
 558	 * If we didn't compact before, we need to find the nearest stale
 559	 * entries before and after our insertion point.
 560	 */
 561	if (compact == 0)
 562		xfs_dir3_leaf_find_stale(leafhdr, ents, index,
 563					 &lowstale, &highstale);
 564
 565	/*
 566	 * If the low one is better, use it.
 567	 */
 568	if (lowstale >= 0 &&
 569	    (highstale == leafhdr->count ||
 570	     index - lowstale - 1 < highstale - index)) {
 571		ASSERT(index - lowstale - 1 >= 0);
 572		ASSERT(ents[lowstale].address ==
 573		       cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
 574
 575		/*
 576		 * Copy entries up to cover the stale entry and make room
 577		 * for the new entry.
 578		 */
 579		if (index - lowstale - 1 > 0) {
 580			memmove(&ents[lowstale], &ents[lowstale + 1],
 581				(index - lowstale - 1) *
 582					sizeof(xfs_dir2_leaf_entry_t));
 583		}
 584		*lfloglow = min(lowstale, *lfloglow);
 585		*lfloghigh = max(index - 1, *lfloghigh);
 586		leafhdr->stale--;
 587		return &ents[index - 1];
 588	}
 589
 590	/*
 591	 * The high one is better, so use that one.
 592	 */
 593	ASSERT(highstale - index >= 0);
 594	ASSERT(ents[highstale].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
 595
 596	/*
 597	 * Copy entries down to cover the stale entry and make room for the
 598	 * new entry.
 599	 */
 600	if (highstale - index > 0) {
 601		memmove(&ents[index + 1], &ents[index],
 602			(highstale - index) * sizeof(xfs_dir2_leaf_entry_t));
 603	}
 604	*lfloglow = min(index, *lfloglow);
 605	*lfloghigh = max(highstale, *lfloghigh);
 606	leafhdr->stale--;
 607	return &ents[index];
 608}
 609
 610/*
 611 * Add an entry to a leaf form directory.
 612 */
 613int						/* error */
 614xfs_dir2_leaf_addname(
 615	struct xfs_da_args	*args)		/* operation arguments */
 616{
 617	struct xfs_dir3_icleaf_hdr leafhdr;
 618	struct xfs_trans	*tp = args->trans;
 619	__be16			*bestsp;	/* freespace table in leaf */
 620	__be16			*tagp;		/* end of data entry */
 621	struct xfs_buf		*dbp;		/* data block buffer */
 622	struct xfs_buf		*lbp;		/* leaf's buffer */
 623	struct xfs_dir2_leaf	*leaf;		/* leaf structure */
 624	struct xfs_inode	*dp = args->dp;	/* incore directory inode */
 625	struct xfs_dir2_data_hdr *hdr;		/* data block header */
 626	struct xfs_dir2_data_entry *dep;	/* data block entry */
 627	struct xfs_dir2_leaf_entry *lep;	/* leaf entry table pointer */
 628	struct xfs_dir2_leaf_entry *ents;
 629	struct xfs_dir2_data_unused *dup;	/* data unused entry */
 630	struct xfs_dir2_leaf_tail *ltp;		/* leaf tail pointer */
 631	struct xfs_dir2_data_free *bf;		/* bestfree table */
 632	int			compact;	/* need to compact leaves */
 
 
 
 
 
 633	int			error;		/* error return value */
 634	int			grown;		/* allocated new data block */
 635	int			highstale = 0;	/* index of next stale leaf */
 636	int			i;		/* temporary, index */
 637	int			index;		/* leaf table position */
 
 
 638	int			length;		/* length of new entry */
 
 639	int			lfloglow;	/* low leaf logging index */
 640	int			lfloghigh;	/* high leaf logging index */
 641	int			lowstale = 0;	/* index of prev stale leaf */
 
 642	int			needbytes;	/* leaf block bytes needed */
 643	int			needlog;	/* need to log data header */
 644	int			needscan;	/* need to rescan data free */
 
 
 645	xfs_dir2_db_t		use_block;	/* data block number */
 
 
 
 646
 647	trace_xfs_dir2_leaf_addname(args);
 648
 649	error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, &lbp);
 
 
 
 650	if (error)
 651		return error;
 652
 653	/*
 654	 * Look up the entry by hash value and name.
 655	 * We know it's not there, our caller has already done a lookup.
 656	 * So the index is of the entry to insert in front of.
 657	 * But if there are dup hash values the index is of the first of those.
 658	 */
 659	index = xfs_dir2_leaf_search_hash(args, lbp);
 660	leaf = lbp->b_addr;
 661	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
 662	xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf);
 663	ents = leafhdr.ents;
 664	bestsp = xfs_dir2_leaf_bests_p(ltp);
 665	length = xfs_dir2_data_entsize(dp->i_mount, args->namelen);
 666
 667	/*
 668	 * See if there are any entries with the same hash value
 669	 * and space in their block for the new entry.
 670	 * This is good because it puts multiple same-hash value entries
 671	 * in a data block, improving the lookup of those entries.
 672	 */
 673	for (use_block = -1, lep = &ents[index];
 674	     index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
 675	     index++, lep++) {
 676		if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
 677			continue;
 678		i = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address));
 679		ASSERT(i < be32_to_cpu(ltp->bestcount));
 680		ASSERT(bestsp[i] != cpu_to_be16(NULLDATAOFF));
 681		if (be16_to_cpu(bestsp[i]) >= length) {
 682			use_block = i;
 683			break;
 684		}
 685	}
 686	/*
 687	 * Didn't find a block yet, linear search all the data blocks.
 688	 */
 689	if (use_block == -1) {
 690		for (i = 0; i < be32_to_cpu(ltp->bestcount); i++) {
 691			/*
 692			 * Remember a block we see that's missing.
 693			 */
 694			if (bestsp[i] == cpu_to_be16(NULLDATAOFF) &&
 695			    use_block == -1)
 696				use_block = i;
 697			else if (be16_to_cpu(bestsp[i]) >= length) {
 698				use_block = i;
 699				break;
 700			}
 701		}
 702	}
 703	/*
 704	 * How many bytes do we need in the leaf block?
 705	 */
 706	needbytes = 0;
 707	if (!leafhdr.stale)
 708		needbytes += sizeof(xfs_dir2_leaf_entry_t);
 709	if (use_block == -1)
 710		needbytes += sizeof(xfs_dir2_data_off_t);
 711
 712	/*
 713	 * Now kill use_block if it refers to a missing block, so we
 714	 * can use it as an indication of allocation needed.
 715	 */
 716	if (use_block != -1 && bestsp[use_block] == cpu_to_be16(NULLDATAOFF))
 717		use_block = -1;
 718	/*
 719	 * If we don't have enough free bytes but we can make enough
 720	 * by compacting out stale entries, we'll do that.
 721	 */
 722	if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes &&
 723	    leafhdr.stale > 1)
 724		compact = 1;
 725
 726	/*
 727	 * Otherwise if we don't have enough free bytes we need to
 728	 * convert to node form.
 729	 */
 730	else if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes) {
 731		/*
 732		 * Just checking or no space reservation, give up.
 733		 */
 734		if ((args->op_flags & XFS_DA_OP_JUSTCHECK) ||
 735							args->total == 0) {
 736			xfs_trans_brelse(tp, lbp);
 737			return -ENOSPC;
 738		}
 739		/*
 740		 * Convert to node form.
 741		 */
 742		error = xfs_dir2_leaf_to_node(args, lbp);
 743		if (error)
 744			return error;
 745		/*
 746		 * Then add the new entry.
 747		 */
 748		return xfs_dir2_node_addname(args);
 749	}
 750	/*
 751	 * Otherwise it will fit without compaction.
 752	 */
 753	else
 754		compact = 0;
 755	/*
 756	 * If just checking, then it will fit unless we needed to allocate
 757	 * a new data block.
 758	 */
 759	if (args->op_flags & XFS_DA_OP_JUSTCHECK) {
 760		xfs_trans_brelse(tp, lbp);
 761		return use_block == -1 ? -ENOSPC : 0;
 762	}
 763	/*
 764	 * If no allocations are allowed, return now before we've
 765	 * changed anything.
 766	 */
 767	if (args->total == 0 && use_block == -1) {
 768		xfs_trans_brelse(tp, lbp);
 769		return -ENOSPC;
 770	}
 771	/*
 772	 * Need to compact the leaf entries, removing stale ones.
 773	 * Leave one stale entry behind - the one closest to our
 774	 * insertion index - and we'll shift that one to our insertion
 775	 * point later.
 776	 */
 777	if (compact) {
 778		xfs_dir3_leaf_compact_x1(&leafhdr, ents, &index, &lowstale,
 779			&highstale, &lfloglow, &lfloghigh);
 780	}
 781	/*
 782	 * There are stale entries, so we'll need log-low and log-high
 783	 * impossibly bad values later.
 784	 */
 785	else if (leafhdr.stale) {
 786		lfloglow = leafhdr.count;
 787		lfloghigh = -1;
 788	}
 789	/*
 790	 * If there was no data block space found, we need to allocate
 791	 * a new one.
 792	 */
 793	if (use_block == -1) {
 794		/*
 795		 * Add the new data block.
 796		 */
 797		if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE,
 798				&use_block))) {
 799			xfs_trans_brelse(tp, lbp);
 800			return error;
 801		}
 802		/*
 803		 * Initialize the block.
 804		 */
 805		if ((error = xfs_dir3_data_init(args, use_block, &dbp))) {
 806			xfs_trans_brelse(tp, lbp);
 807			return error;
 808		}
 809		/*
 810		 * If we're adding a new data block on the end we need to
 811		 * extend the bests table.  Copy it up one entry.
 812		 */
 813		if (use_block >= be32_to_cpu(ltp->bestcount)) {
 814			bestsp--;
 815			memmove(&bestsp[0], &bestsp[1],
 816				be32_to_cpu(ltp->bestcount) * sizeof(bestsp[0]));
 817			be32_add_cpu(&ltp->bestcount, 1);
 818			xfs_dir3_leaf_log_tail(args, lbp);
 819			xfs_dir3_leaf_log_bests(args, lbp, 0,
 820						be32_to_cpu(ltp->bestcount) - 1);
 821		}
 822		/*
 823		 * If we're filling in a previously empty block just log it.
 824		 */
 825		else
 826			xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block);
 827		hdr = dbp->b_addr;
 828		bf = xfs_dir2_data_bestfree_p(dp->i_mount, hdr);
 829		bestsp[use_block] = bf[0].length;
 830		grown = 1;
 831	} else {
 832		/*
 833		 * Already had space in some data block.
 834		 * Just read that one in.
 835		 */
 836		error = xfs_dir3_data_read(tp, dp,
 837				   xfs_dir2_db_to_da(args->geo, use_block),
 838				   0, &dbp);
 839		if (error) {
 840			xfs_trans_brelse(tp, lbp);
 841			return error;
 842		}
 843		hdr = dbp->b_addr;
 844		bf = xfs_dir2_data_bestfree_p(dp->i_mount, hdr);
 845		grown = 0;
 846	}
 847	/*
 848	 * Point to the biggest freespace in our data block.
 849	 */
 850	dup = (xfs_dir2_data_unused_t *)
 851	      ((char *)hdr + be16_to_cpu(bf[0].offset));
 
 852	needscan = needlog = 0;
 853	/*
 854	 * Mark the initial part of our freespace in use for the new entry.
 855	 */
 856	error = xfs_dir2_data_use_free(args, dbp, dup,
 857			(xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr),
 858			length, &needlog, &needscan);
 859	if (error) {
 860		xfs_trans_brelse(tp, lbp);
 861		return error;
 862	}
 863	/*
 864	 * Initialize our new entry (at last).
 865	 */
 866	dep = (xfs_dir2_data_entry_t *)dup;
 867	dep->inumber = cpu_to_be64(args->inumber);
 868	dep->namelen = args->namelen;
 869	memcpy(dep->name, args->name, dep->namelen);
 870	xfs_dir2_data_put_ftype(dp->i_mount, dep, args->filetype);
 871	tagp = xfs_dir2_data_entry_tag_p(dp->i_mount, dep);
 872	*tagp = cpu_to_be16((char *)dep - (char *)hdr);
 873	/*
 874	 * Need to scan fix up the bestfree table.
 875	 */
 876	if (needscan)
 877		xfs_dir2_data_freescan(dp->i_mount, hdr, &needlog);
 878	/*
 879	 * Need to log the data block's header.
 880	 */
 881	if (needlog)
 882		xfs_dir2_data_log_header(args, dbp);
 883	xfs_dir2_data_log_entry(args, dbp, dep);
 884	/*
 885	 * If the bests table needs to be changed, do it.
 886	 * Log the change unless we've already done that.
 887	 */
 888	if (be16_to_cpu(bestsp[use_block]) != be16_to_cpu(bf[0].length)) {
 889		bestsp[use_block] = bf[0].length;
 890		if (!grown)
 891			xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block);
 892	}
 893
 894	lep = xfs_dir3_leaf_find_entry(&leafhdr, ents, index, compact, lowstale,
 895				       highstale, &lfloglow, &lfloghigh);
 896
 897	/*
 898	 * Fill in the new leaf entry.
 899	 */
 900	lep->hashval = cpu_to_be32(args->hashval);
 901	lep->address = cpu_to_be32(
 902				xfs_dir2_db_off_to_dataptr(args->geo, use_block,
 903				be16_to_cpu(*tagp)));
 904	/*
 905	 * Log the leaf fields and give up the buffers.
 906	 */
 907	xfs_dir2_leaf_hdr_to_disk(dp->i_mount, leaf, &leafhdr);
 908	xfs_dir3_leaf_log_header(args, lbp);
 909	xfs_dir3_leaf_log_ents(args, &leafhdr, lbp, lfloglow, lfloghigh);
 910	xfs_dir3_leaf_check(dp, lbp);
 911	xfs_dir3_data_check(dp, dbp);
 912	return 0;
 913}
 914
 915/*
 916 * Compact out any stale entries in the leaf.
 917 * Log the header and changed leaf entries, if any.
 918 */
 919void
 920xfs_dir3_leaf_compact(
 921	xfs_da_args_t	*args,		/* operation arguments */
 922	struct xfs_dir3_icleaf_hdr *leafhdr,
 923	struct xfs_buf	*bp)		/* leaf buffer */
 924{
 925	int		from;		/* source leaf index */
 926	xfs_dir2_leaf_t	*leaf;		/* leaf structure */
 927	int		loglow;		/* first leaf entry to log */
 928	int		to;		/* target leaf index */
 
 929	struct xfs_inode *dp = args->dp;
 930
 931	leaf = bp->b_addr;
 932	if (!leafhdr->stale)
 933		return;
 934
 935	/*
 936	 * Compress out the stale entries in place.
 937	 */
 
 938	for (from = to = 0, loglow = -1; from < leafhdr->count; from++) {
 939		if (leafhdr->ents[from].address ==
 940		    cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
 941			continue;
 942		/*
 943		 * Only actually copy the entries that are different.
 944		 */
 945		if (from > to) {
 946			if (loglow == -1)
 947				loglow = to;
 948			leafhdr->ents[to] = leafhdr->ents[from];
 949		}
 950		to++;
 951	}
 952	/*
 953	 * Update and log the header, log the leaf entries.
 954	 */
 955	ASSERT(leafhdr->stale == from - to);
 956	leafhdr->count -= leafhdr->stale;
 957	leafhdr->stale = 0;
 958
 959	xfs_dir2_leaf_hdr_to_disk(dp->i_mount, leaf, leafhdr);
 960	xfs_dir3_leaf_log_header(args, bp);
 961	if (loglow != -1)
 962		xfs_dir3_leaf_log_ents(args, leafhdr, bp, loglow, to - 1);
 963}
 964
 965/*
 966 * Compact the leaf entries, removing stale ones.
 967 * Leave one stale entry behind - the one closest to our
 968 * insertion index - and the caller will shift that one to our insertion
 969 * point later.
 970 * Return new insertion index, where the remaining stale entry is,
 971 * and leaf logging indices.
 972 */
 973void
 974xfs_dir3_leaf_compact_x1(
 975	struct xfs_dir3_icleaf_hdr *leafhdr,
 976	struct xfs_dir2_leaf_entry *ents,
 977	int		*indexp,	/* insertion index */
 978	int		*lowstalep,	/* out: stale entry before us */
 979	int		*highstalep,	/* out: stale entry after us */
 980	int		*lowlogp,	/* out: low log index */
 981	int		*highlogp)	/* out: high log index */
 982{
 983	int		from;		/* source copy index */
 984	int		highstale;	/* stale entry at/after index */
 985	int		index;		/* insertion index */
 986	int		keepstale;	/* source index of kept stale */
 987	int		lowstale;	/* stale entry before index */
 988	int		newindex=0;	/* new insertion index */
 989	int		to;		/* destination copy index */
 990
 991	ASSERT(leafhdr->stale > 1);
 992	index = *indexp;
 993
 994	xfs_dir3_leaf_find_stale(leafhdr, ents, index, &lowstale, &highstale);
 995
 996	/*
 997	 * Pick the better of lowstale and highstale.
 998	 */
 999	if (lowstale >= 0 &&
1000	    (highstale == leafhdr->count ||
1001	     index - lowstale <= highstale - index))
1002		keepstale = lowstale;
1003	else
1004		keepstale = highstale;
1005	/*
1006	 * Copy the entries in place, removing all the stale entries
1007	 * except keepstale.
1008	 */
1009	for (from = to = 0; from < leafhdr->count; from++) {
1010		/*
1011		 * Notice the new value of index.
1012		 */
1013		if (index == from)
1014			newindex = to;
1015		if (from != keepstale &&
1016		    ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) {
1017			if (from == to)
1018				*lowlogp = to;
1019			continue;
1020		}
1021		/*
1022		 * Record the new keepstale value for the insertion.
1023		 */
1024		if (from == keepstale)
1025			lowstale = highstale = to;
1026		/*
1027		 * Copy only the entries that have moved.
1028		 */
1029		if (from > to)
1030			ents[to] = ents[from];
1031		to++;
1032	}
1033	ASSERT(from > to);
1034	/*
1035	 * If the insertion point was past the last entry,
1036	 * set the new insertion point accordingly.
1037	 */
1038	if (index == from)
1039		newindex = to;
1040	*indexp = newindex;
1041	/*
1042	 * Adjust the leaf header values.
1043	 */
1044	leafhdr->count -= from - to;
1045	leafhdr->stale = 1;
1046	/*
1047	 * Remember the low/high stale value only in the "right"
1048	 * direction.
1049	 */
1050	if (lowstale >= newindex)
1051		lowstale = -1;
1052	else
1053		highstale = leafhdr->count;
1054	*highlogp = leafhdr->count - 1;
1055	*lowstalep = lowstale;
1056	*highstalep = highstale;
1057}
1058
1059/*
1060 * Log the bests entries indicated from a leaf1 block.
1061 */
1062static void
1063xfs_dir3_leaf_log_bests(
1064	struct xfs_da_args	*args,
1065	struct xfs_buf		*bp,		/* leaf buffer */
1066	int			first,		/* first entry to log */
1067	int			last)		/* last entry to log */
1068{
1069	__be16			*firstb;	/* pointer to first entry */
1070	__be16			*lastb;		/* pointer to last entry */
1071	struct xfs_dir2_leaf	*leaf = bp->b_addr;
1072	xfs_dir2_leaf_tail_t	*ltp;		/* leaf tail structure */
1073
1074	ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1075	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC));
1076
1077	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
1078	firstb = xfs_dir2_leaf_bests_p(ltp) + first;
1079	lastb = xfs_dir2_leaf_bests_p(ltp) + last;
1080	xfs_trans_log_buf(args->trans, bp,
1081		(uint)((char *)firstb - (char *)leaf),
1082		(uint)((char *)lastb - (char *)leaf + sizeof(*lastb) - 1));
1083}
1084
1085/*
1086 * Log the leaf entries indicated from a leaf1 or leafn block.
1087 */
1088void
1089xfs_dir3_leaf_log_ents(
1090	struct xfs_da_args	*args,
1091	struct xfs_dir3_icleaf_hdr *hdr,
1092	struct xfs_buf		*bp,
1093	int			first,
1094	int			last)
1095{
1096	xfs_dir2_leaf_entry_t	*firstlep;	/* pointer to first entry */
1097	xfs_dir2_leaf_entry_t	*lastlep;	/* pointer to last entry */
1098	struct xfs_dir2_leaf	*leaf = bp->b_addr;
 
1099
1100	ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1101	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1102	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1103	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1104
1105	firstlep = &hdr->ents[first];
1106	lastlep = &hdr->ents[last];
 
1107	xfs_trans_log_buf(args->trans, bp,
1108		(uint)((char *)firstlep - (char *)leaf),
1109		(uint)((char *)lastlep - (char *)leaf + sizeof(*lastlep) - 1));
1110}
1111
1112/*
1113 * Log the header of the leaf1 or leafn block.
1114 */
1115void
1116xfs_dir3_leaf_log_header(
1117	struct xfs_da_args	*args,
1118	struct xfs_buf		*bp)
1119{
1120	struct xfs_dir2_leaf	*leaf = bp->b_addr;
1121
1122	ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1123	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1124	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1125	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1126
1127	xfs_trans_log_buf(args->trans, bp,
1128			  (uint)((char *)&leaf->hdr - (char *)leaf),
1129			  args->geo->leaf_hdr_size - 1);
1130}
1131
1132/*
1133 * Log the tail of the leaf1 block.
1134 */
1135STATIC void
1136xfs_dir3_leaf_log_tail(
1137	struct xfs_da_args	*args,
1138	struct xfs_buf		*bp)
1139{
1140	struct xfs_dir2_leaf	*leaf = bp->b_addr;
1141	xfs_dir2_leaf_tail_t	*ltp;		/* leaf tail structure */
1142
1143	ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1144	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1145	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1146	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1147
1148	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
1149	xfs_trans_log_buf(args->trans, bp, (uint)((char *)ltp - (char *)leaf),
1150		(uint)(args->geo->blksize - 1));
1151}
1152
1153/*
1154 * Look up the entry referred to by args in the leaf format directory.
1155 * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which
1156 * is also used by the node-format code.
1157 */
1158int
1159xfs_dir2_leaf_lookup(
1160	xfs_da_args_t		*args)		/* operation arguments */
1161{
1162	struct xfs_buf		*dbp;		/* data block buffer */
1163	xfs_dir2_data_entry_t	*dep;		/* data block entry */
1164	xfs_inode_t		*dp;		/* incore directory inode */
1165	int			error;		/* error return code */
1166	int			index;		/* found entry index */
1167	struct xfs_buf		*lbp;		/* leaf buffer */
 
1168	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
1169	xfs_trans_t		*tp;		/* transaction pointer */
1170	struct xfs_dir3_icleaf_hdr leafhdr;
1171
1172	trace_xfs_dir2_leaf_lookup(args);
1173
1174	/*
1175	 * Look up name in the leaf block, returning both buffers and index.
1176	 */
1177	error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp, &leafhdr);
1178	if (error)
1179		return error;
1180
1181	tp = args->trans;
1182	dp = args->dp;
1183	xfs_dir3_leaf_check(dp, lbp);
1184
 
1185	/*
1186	 * Get to the leaf entry and contained data entry address.
1187	 */
1188	lep = &leafhdr.ents[index];
1189
1190	/*
1191	 * Point to the data entry.
1192	 */
1193	dep = (xfs_dir2_data_entry_t *)
1194	      ((char *)dbp->b_addr +
1195	       xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
1196	/*
1197	 * Return the found inode number & CI name if appropriate
1198	 */
1199	args->inumber = be64_to_cpu(dep->inumber);
1200	args->filetype = xfs_dir2_data_get_ftype(dp->i_mount, dep);
1201	error = xfs_dir_cilookup_result(args, dep->name, dep->namelen);
1202	xfs_trans_brelse(tp, dbp);
1203	xfs_trans_brelse(tp, lbp);
1204	return error;
1205}
1206
1207/*
1208 * Look up name/hash in the leaf block.
1209 * Fill in indexp with the found index, and dbpp with the data buffer.
1210 * If not found dbpp will be NULL, and ENOENT comes back.
1211 * lbpp will always be filled in with the leaf buffer unless there's an error.
1212 */
1213static int					/* error */
1214xfs_dir2_leaf_lookup_int(
1215	xfs_da_args_t		*args,		/* operation arguments */
1216	struct xfs_buf		**lbpp,		/* out: leaf buffer */
1217	int			*indexp,	/* out: index in leaf block */
1218	struct xfs_buf		**dbpp,		/* out: data buffer */
1219	struct xfs_dir3_icleaf_hdr *leafhdr)
1220{
1221	xfs_dir2_db_t		curdb = -1;	/* current data block number */
1222	struct xfs_buf		*dbp = NULL;	/* data buffer */
1223	xfs_dir2_data_entry_t	*dep;		/* data entry */
1224	xfs_inode_t		*dp;		/* incore directory inode */
1225	int			error;		/* error return code */
1226	int			index;		/* index in leaf block */
1227	struct xfs_buf		*lbp;		/* leaf buffer */
1228	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
1229	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
1230	xfs_mount_t		*mp;		/* filesystem mount point */
1231	xfs_dir2_db_t		newdb;		/* new data block number */
1232	xfs_trans_t		*tp;		/* transaction pointer */
1233	xfs_dir2_db_t		cidb = -1;	/* case match data block no. */
1234	enum xfs_dacmp		cmp;		/* name compare result */
 
 
1235
1236	dp = args->dp;
1237	tp = args->trans;
1238	mp = dp->i_mount;
1239
1240	error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, &lbp);
1241	if (error)
1242		return error;
1243
1244	*lbpp = lbp;
1245	leaf = lbp->b_addr;
1246	xfs_dir3_leaf_check(dp, lbp);
1247	xfs_dir2_leaf_hdr_from_disk(mp, leafhdr, leaf);
 
1248
1249	/*
1250	 * Look for the first leaf entry with our hash value.
1251	 */
1252	index = xfs_dir2_leaf_search_hash(args, lbp);
1253	/*
1254	 * Loop over all the entries with the right hash value
1255	 * looking to match the name.
1256	 */
1257	for (lep = &leafhdr->ents[index];
1258	     index < leafhdr->count &&
1259			be32_to_cpu(lep->hashval) == args->hashval;
1260	     lep++, index++) {
1261		/*
1262		 * Skip over stale leaf entries.
1263		 */
1264		if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
1265			continue;
1266		/*
1267		 * Get the new data block number.
1268		 */
1269		newdb = xfs_dir2_dataptr_to_db(args->geo,
1270					       be32_to_cpu(lep->address));
1271		/*
1272		 * If it's not the same as the old data block number,
1273		 * need to pitch the old one and read the new one.
1274		 */
1275		if (newdb != curdb) {
1276			if (dbp)
1277				xfs_trans_brelse(tp, dbp);
1278			error = xfs_dir3_data_read(tp, dp,
1279					   xfs_dir2_db_to_da(args->geo, newdb),
1280					   0, &dbp);
1281			if (error) {
1282				xfs_trans_brelse(tp, lbp);
1283				return error;
1284			}
1285			curdb = newdb;
1286		}
1287		/*
1288		 * Point to the data entry.
1289		 */
1290		dep = (xfs_dir2_data_entry_t *)((char *)dbp->b_addr +
1291			xfs_dir2_dataptr_to_off(args->geo,
1292						be32_to_cpu(lep->address)));
1293		/*
1294		 * Compare name and if it's an exact match, return the index
1295		 * and buffer. If it's the first case-insensitive match, store
1296		 * the index and buffer and continue looking for an exact match.
1297		 */
1298		cmp = xfs_dir2_compname(args, dep->name, dep->namelen);
1299		if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {
1300			args->cmpresult = cmp;
1301			*indexp = index;
1302			/* case exact match: return the current buffer. */
1303			if (cmp == XFS_CMP_EXACT) {
1304				*dbpp = dbp;
1305				return 0;
1306			}
1307			cidb = curdb;
1308		}
1309	}
1310	ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
1311	/*
1312	 * Here, we can only be doing a lookup (not a rename or remove).
1313	 * If a case-insensitive match was found earlier, re-read the
1314	 * appropriate data block if required and return it.
1315	 */
1316	if (args->cmpresult == XFS_CMP_CASE) {
1317		ASSERT(cidb != -1);
1318		if (cidb != curdb) {
1319			xfs_trans_brelse(tp, dbp);
1320			error = xfs_dir3_data_read(tp, dp,
1321					   xfs_dir2_db_to_da(args->geo, cidb),
1322					   0, &dbp);
1323			if (error) {
1324				xfs_trans_brelse(tp, lbp);
1325				return error;
1326			}
1327		}
1328		*dbpp = dbp;
1329		return 0;
1330	}
1331	/*
1332	 * No match found, return -ENOENT.
1333	 */
1334	ASSERT(cidb == -1);
1335	if (dbp)
1336		xfs_trans_brelse(tp, dbp);
1337	xfs_trans_brelse(tp, lbp);
1338	return -ENOENT;
1339}
1340
1341/*
1342 * Remove an entry from a leaf format directory.
1343 */
1344int						/* error */
1345xfs_dir2_leaf_removename(
1346	xfs_da_args_t		*args)		/* operation arguments */
1347{
1348	struct xfs_da_geometry	*geo = args->geo;
1349	__be16			*bestsp;	/* leaf block best freespace */
1350	xfs_dir2_data_hdr_t	*hdr;		/* data block header */
1351	xfs_dir2_db_t		db;		/* data block number */
1352	struct xfs_buf		*dbp;		/* data block buffer */
1353	xfs_dir2_data_entry_t	*dep;		/* data entry structure */
1354	xfs_inode_t		*dp;		/* incore directory inode */
1355	int			error;		/* error return code */
1356	xfs_dir2_db_t		i;		/* temporary data block # */
1357	int			index;		/* index into leaf entries */
1358	struct xfs_buf		*lbp;		/* leaf buffer */
1359	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
1360	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
1361	xfs_dir2_leaf_tail_t	*ltp;		/* leaf tail structure */
1362	int			needlog;	/* need to log data header */
1363	int			needscan;	/* need to rescan data frees */
1364	xfs_dir2_data_off_t	oldbest;	/* old value of best free */
1365	struct xfs_dir2_data_free *bf;		/* bestfree table */
 
1366	struct xfs_dir3_icleaf_hdr leafhdr;
1367
1368	trace_xfs_dir2_leaf_removename(args);
1369
1370	/*
1371	 * Lookup the leaf entry, get the leaf and data blocks read in.
1372	 */
1373	error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp, &leafhdr);
1374	if (error)
1375		return error;
1376
1377	dp = args->dp;
1378	leaf = lbp->b_addr;
1379	hdr = dbp->b_addr;
1380	xfs_dir3_data_check(dp, dbp);
1381	bf = xfs_dir2_data_bestfree_p(dp->i_mount, hdr);
1382
 
1383	/*
1384	 * Point to the leaf entry, use that to point to the data entry.
1385	 */
1386	lep = &leafhdr.ents[index];
1387	db = xfs_dir2_dataptr_to_db(geo, be32_to_cpu(lep->address));
1388	dep = (xfs_dir2_data_entry_t *)((char *)hdr +
1389		xfs_dir2_dataptr_to_off(geo, be32_to_cpu(lep->address)));
1390	needscan = needlog = 0;
1391	oldbest = be16_to_cpu(bf[0].length);
1392	ltp = xfs_dir2_leaf_tail_p(geo, leaf);
1393	bestsp = xfs_dir2_leaf_bests_p(ltp);
1394	if (be16_to_cpu(bestsp[db]) != oldbest) {
1395		xfs_buf_mark_corrupt(lbp);
1396		return -EFSCORRUPTED;
1397	}
1398	/*
1399	 * Mark the former data entry unused.
1400	 */
1401	xfs_dir2_data_make_free(args, dbp,
1402		(xfs_dir2_data_aoff_t)((char *)dep - (char *)hdr),
1403		xfs_dir2_data_entsize(dp->i_mount, dep->namelen), &needlog,
1404		&needscan);
1405	/*
1406	 * We just mark the leaf entry stale by putting a null in it.
1407	 */
1408	leafhdr.stale++;
1409	xfs_dir2_leaf_hdr_to_disk(dp->i_mount, leaf, &leafhdr);
1410	xfs_dir3_leaf_log_header(args, lbp);
1411
1412	lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
1413	xfs_dir3_leaf_log_ents(args, &leafhdr, lbp, index, index);
1414
1415	/*
1416	 * Scan the freespace in the data block again if necessary,
1417	 * log the data block header if necessary.
1418	 */
1419	if (needscan)
1420		xfs_dir2_data_freescan(dp->i_mount, hdr, &needlog);
1421	if (needlog)
1422		xfs_dir2_data_log_header(args, dbp);
1423	/*
1424	 * If the longest freespace in the data block has changed,
1425	 * put the new value in the bests table and log that.
1426	 */
1427	if (be16_to_cpu(bf[0].length) != oldbest) {
1428		bestsp[db] = bf[0].length;
1429		xfs_dir3_leaf_log_bests(args, lbp, db, db);
1430	}
1431	xfs_dir3_data_check(dp, dbp);
1432	/*
1433	 * If the data block is now empty then get rid of the data block.
1434	 */
1435	if (be16_to_cpu(bf[0].length) ==
1436	    geo->blksize - geo->data_entry_offset) {
1437		ASSERT(db != geo->datablk);
1438		if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1439			/*
1440			 * Nope, can't get rid of it because it caused
1441			 * allocation of a bmap btree block to do so.
1442			 * Just go on, returning success, leaving the
1443			 * empty block in place.
1444			 */
1445			if (error == -ENOSPC && args->total == 0)
1446				error = 0;
1447			xfs_dir3_leaf_check(dp, lbp);
1448			return error;
1449		}
1450		dbp = NULL;
1451		/*
1452		 * If this is the last data block then compact the
1453		 * bests table by getting rid of entries.
1454		 */
1455		if (db == be32_to_cpu(ltp->bestcount) - 1) {
1456			/*
1457			 * Look for the last active entry (i).
1458			 */
1459			for (i = db - 1; i > 0; i--) {
1460				if (bestsp[i] != cpu_to_be16(NULLDATAOFF))
1461					break;
1462			}
1463			/*
1464			 * Copy the table down so inactive entries at the
1465			 * end are removed.
1466			 */
1467			memmove(&bestsp[db - i], bestsp,
1468				(be32_to_cpu(ltp->bestcount) - (db - i)) * sizeof(*bestsp));
1469			be32_add_cpu(&ltp->bestcount, -(db - i));
1470			xfs_dir3_leaf_log_tail(args, lbp);
1471			xfs_dir3_leaf_log_bests(args, lbp, 0,
1472						be32_to_cpu(ltp->bestcount) - 1);
1473		} else
1474			bestsp[db] = cpu_to_be16(NULLDATAOFF);
1475	}
1476	/*
1477	 * If the data block was not the first one, drop it.
1478	 */
1479	else if (db != geo->datablk)
1480		dbp = NULL;
1481
1482	xfs_dir3_leaf_check(dp, lbp);
1483	/*
1484	 * See if we can convert to block form.
1485	 */
1486	return xfs_dir2_leaf_to_block(args, lbp, dbp);
1487}
1488
1489/*
1490 * Replace the inode number in a leaf format directory entry.
1491 */
1492int						/* error */
1493xfs_dir2_leaf_replace(
1494	xfs_da_args_t		*args)		/* operation arguments */
1495{
1496	struct xfs_buf		*dbp;		/* data block buffer */
1497	xfs_dir2_data_entry_t	*dep;		/* data block entry */
1498	xfs_inode_t		*dp;		/* incore directory inode */
1499	int			error;		/* error return code */
1500	int			index;		/* index of leaf entry */
1501	struct xfs_buf		*lbp;		/* leaf buffer */
 
1502	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
1503	xfs_trans_t		*tp;		/* transaction pointer */
1504	struct xfs_dir3_icleaf_hdr leafhdr;
1505
1506	trace_xfs_dir2_leaf_replace(args);
1507
1508	/*
1509	 * Look up the entry.
1510	 */
1511	error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp, &leafhdr);
1512	if (error)
1513		return error;
1514
1515	dp = args->dp;
 
 
1516	/*
1517	 * Point to the leaf entry, get data address from it.
1518	 */
1519	lep = &leafhdr.ents[index];
1520	/*
1521	 * Point to the data entry.
1522	 */
1523	dep = (xfs_dir2_data_entry_t *)
1524	      ((char *)dbp->b_addr +
1525	       xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
1526	ASSERT(args->inumber != be64_to_cpu(dep->inumber));
1527	/*
1528	 * Put the new inode number in, log it.
1529	 */
1530	dep->inumber = cpu_to_be64(args->inumber);
1531	xfs_dir2_data_put_ftype(dp->i_mount, dep, args->filetype);
1532	tp = args->trans;
1533	xfs_dir2_data_log_entry(args, dbp, dep);
1534	xfs_dir3_leaf_check(dp, lbp);
1535	xfs_trans_brelse(tp, lbp);
1536	return 0;
1537}
1538
1539/*
1540 * Return index in the leaf block (lbp) which is either the first
1541 * one with this hash value, or if there are none, the insert point
1542 * for that hash value.
1543 */
1544int						/* index value */
1545xfs_dir2_leaf_search_hash(
1546	xfs_da_args_t		*args,		/* operation arguments */
1547	struct xfs_buf		*lbp)		/* leaf buffer */
1548{
1549	xfs_dahash_t		hash=0;		/* hash from this entry */
1550	xfs_dahash_t		hashwant;	/* hash value looking for */
1551	int			high;		/* high leaf index */
1552	int			low;		/* low leaf index */
 
1553	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
1554	int			mid=0;		/* current leaf index */
 
1555	struct xfs_dir3_icleaf_hdr leafhdr;
1556
1557	xfs_dir2_leaf_hdr_from_disk(args->dp->i_mount, &leafhdr, lbp->b_addr);
 
 
1558
1559	/*
1560	 * Note, the table cannot be empty, so we have to go through the loop.
1561	 * Binary search the leaf entries looking for our hash value.
1562	 */
1563	for (lep = leafhdr.ents, low = 0, high = leafhdr.count - 1,
1564		hashwant = args->hashval;
1565	     low <= high; ) {
1566		mid = (low + high) >> 1;
1567		if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant)
1568			break;
1569		if (hash < hashwant)
1570			low = mid + 1;
1571		else
1572			high = mid - 1;
1573	}
1574	/*
1575	 * Found one, back up through all the equal hash values.
1576	 */
1577	if (hash == hashwant) {
1578		while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant) {
1579			mid--;
1580		}
1581	}
1582	/*
1583	 * Need to point to an entry higher than ours.
1584	 */
1585	else if (hash < hashwant)
1586		mid++;
1587	return mid;
1588}
1589
1590/*
1591 * Trim off a trailing data block.  We know it's empty since the leaf
1592 * freespace table says so.
1593 */
1594int						/* error */
1595xfs_dir2_leaf_trim_data(
1596	xfs_da_args_t		*args,		/* operation arguments */
1597	struct xfs_buf		*lbp,		/* leaf buffer */
1598	xfs_dir2_db_t		db)		/* data block number */
1599{
1600	struct xfs_da_geometry	*geo = args->geo;
1601	__be16			*bestsp;	/* leaf bests table */
1602	struct xfs_buf		*dbp;		/* data block buffer */
1603	xfs_inode_t		*dp;		/* incore directory inode */
1604	int			error;		/* error return value */
1605	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
1606	xfs_dir2_leaf_tail_t	*ltp;		/* leaf tail structure */
1607	xfs_trans_t		*tp;		/* transaction pointer */
1608
1609	dp = args->dp;
1610	tp = args->trans;
1611	/*
1612	 * Read the offending data block.  We need its buffer.
1613	 */
1614	error = xfs_dir3_data_read(tp, dp, xfs_dir2_db_to_da(geo, db), 0, &dbp);
 
1615	if (error)
1616		return error;
1617
1618	leaf = lbp->b_addr;
1619	ltp = xfs_dir2_leaf_tail_p(geo, leaf);
1620
1621#ifdef DEBUG
1622{
1623	struct xfs_dir2_data_hdr *hdr = dbp->b_addr;
1624	struct xfs_dir2_data_free *bf =
1625		xfs_dir2_data_bestfree_p(dp->i_mount, hdr);
1626
1627	ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
1628	       hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC));
1629	ASSERT(be16_to_cpu(bf[0].length) ==
1630	       geo->blksize - geo->data_entry_offset);
1631	ASSERT(db == be32_to_cpu(ltp->bestcount) - 1);
1632}
1633#endif
1634
1635	/*
1636	 * Get rid of the data block.
1637	 */
1638	if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1639		ASSERT(error != -ENOSPC);
1640		xfs_trans_brelse(tp, dbp);
1641		return error;
1642	}
1643	/*
1644	 * Eliminate the last bests entry from the table.
1645	 */
1646	bestsp = xfs_dir2_leaf_bests_p(ltp);
1647	be32_add_cpu(&ltp->bestcount, -1);
1648	memmove(&bestsp[1], &bestsp[0], be32_to_cpu(ltp->bestcount) * sizeof(*bestsp));
1649	xfs_dir3_leaf_log_tail(args, lbp);
1650	xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
1651	return 0;
1652}
1653
1654static inline size_t
1655xfs_dir3_leaf_size(
1656	struct xfs_dir3_icleaf_hdr	*hdr,
1657	int				counts)
1658{
1659	int	entries;
1660	int	hdrsize;
1661
1662	entries = hdr->count - hdr->stale;
1663	if (hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
1664	    hdr->magic == XFS_DIR2_LEAFN_MAGIC)
1665		hdrsize = sizeof(struct xfs_dir2_leaf_hdr);
1666	else
1667		hdrsize = sizeof(struct xfs_dir3_leaf_hdr);
1668
1669	return hdrsize + entries * sizeof(xfs_dir2_leaf_entry_t)
1670	               + counts * sizeof(xfs_dir2_data_off_t)
1671		       + sizeof(xfs_dir2_leaf_tail_t);
1672}
1673
1674/*
1675 * Convert node form directory to leaf form directory.
1676 * The root of the node form dir needs to already be a LEAFN block.
1677 * Just return if we can't do anything.
1678 */
1679int						/* error */
1680xfs_dir2_node_to_leaf(
1681	xfs_da_state_t		*state)		/* directory operation state */
1682{
1683	xfs_da_args_t		*args;		/* operation arguments */
1684	xfs_inode_t		*dp;		/* incore directory inode */
1685	int			error;		/* error return code */
1686	struct xfs_buf		*fbp;		/* buffer for freespace block */
1687	xfs_fileoff_t		fo;		/* freespace file offset */
 
1688	struct xfs_buf		*lbp;		/* buffer for leaf block */
1689	xfs_dir2_leaf_tail_t	*ltp;		/* tail of leaf structure */
1690	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
1691	xfs_mount_t		*mp;		/* filesystem mount point */
1692	int			rval;		/* successful free trim? */
1693	xfs_trans_t		*tp;		/* transaction pointer */
1694	struct xfs_dir3_icleaf_hdr leafhdr;
1695	struct xfs_dir3_icfree_hdr freehdr;
1696
1697	/*
1698	 * There's more than a leaf level in the btree, so there must
1699	 * be multiple leafn blocks.  Give up.
1700	 */
1701	if (state->path.active > 1)
1702		return 0;
1703	args = state->args;
1704
1705	trace_xfs_dir2_node_to_leaf(args);
1706
1707	mp = state->mp;
1708	dp = args->dp;
1709	tp = args->trans;
1710	/*
1711	 * Get the last offset in the file.
1712	 */
1713	if ((error = xfs_bmap_last_offset(dp, &fo, XFS_DATA_FORK))) {
1714		return error;
1715	}
1716	fo -= args->geo->fsbcount;
1717	/*
1718	 * If there are freespace blocks other than the first one,
1719	 * take this opportunity to remove trailing empty freespace blocks
1720	 * that may have been left behind during no-space-reservation
1721	 * operations.
1722	 */
1723	while (fo > args->geo->freeblk) {
1724		if ((error = xfs_dir2_node_trim_free(args, fo, &rval))) {
1725			return error;
1726		}
1727		if (rval)
1728			fo -= args->geo->fsbcount;
1729		else
1730			return 0;
1731	}
1732	/*
1733	 * Now find the block just before the freespace block.
1734	 */
1735	if ((error = xfs_bmap_last_before(tp, dp, &fo, XFS_DATA_FORK))) {
1736		return error;
1737	}
1738	/*
1739	 * If it's not the single leaf block, give up.
1740	 */
1741	if (XFS_FSB_TO_B(mp, fo) > XFS_DIR2_LEAF_OFFSET + args->geo->blksize)
1742		return 0;
1743	lbp = state->path.blk[0].bp;
1744	leaf = lbp->b_addr;
1745	xfs_dir2_leaf_hdr_from_disk(mp, &leafhdr, leaf);
1746
1747	ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
1748	       leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
1749
1750	/*
1751	 * Read the freespace block.
1752	 */
1753	error = xfs_dir2_free_read(tp, dp,  args->geo->freeblk, &fbp);
1754	if (error)
1755		return error;
1756	xfs_dir2_free_hdr_from_disk(mp, &freehdr, fbp->b_addr);
 
1757
1758	ASSERT(!freehdr.firstdb);
1759
1760	/*
1761	 * Now see if the leafn and free data will fit in a leaf1.
1762	 * If not, release the buffer and give up.
1763	 */
1764	if (xfs_dir3_leaf_size(&leafhdr, freehdr.nvalid) > args->geo->blksize) {
1765		xfs_trans_brelse(tp, fbp);
1766		return 0;
1767	}
1768
1769	/*
1770	 * If the leaf has any stale entries in it, compress them out.
1771	 */
1772	if (leafhdr.stale)
1773		xfs_dir3_leaf_compact(args, &leafhdr, lbp);
1774
1775	lbp->b_ops = &xfs_dir3_leaf1_buf_ops;
1776	xfs_trans_buf_set_type(tp, lbp, XFS_BLFT_DIR_LEAF1_BUF);
1777	leafhdr.magic = (leafhdr.magic == XFS_DIR2_LEAFN_MAGIC)
1778					? XFS_DIR2_LEAF1_MAGIC
1779					: XFS_DIR3_LEAF1_MAGIC;
1780
1781	/*
1782	 * Set up the leaf tail from the freespace block.
1783	 */
1784	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
1785	ltp->bestcount = cpu_to_be32(freehdr.nvalid);
1786
1787	/*
1788	 * Set up the leaf bests table.
1789	 */
1790	memcpy(xfs_dir2_leaf_bests_p(ltp), freehdr.bests,
1791		freehdr.nvalid * sizeof(xfs_dir2_data_off_t));
1792
1793	xfs_dir2_leaf_hdr_to_disk(mp, leaf, &leafhdr);
1794	xfs_dir3_leaf_log_header(args, lbp);
1795	xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
1796	xfs_dir3_leaf_log_tail(args, lbp);
1797	xfs_dir3_leaf_check(dp, lbp);
1798
1799	/*
1800	 * Get rid of the freespace block.
1801	 */
1802	error = xfs_dir2_shrink_inode(args,
1803			xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET),
1804			fbp);
1805	if (error) {
1806		/*
1807		 * This can't fail here because it can only happen when
1808		 * punching out the middle of an extent, and this is an
1809		 * isolated block.
1810		 */
1811		ASSERT(error != -ENOSPC);
1812		return error;
1813	}
1814	fbp = NULL;
1815	/*
1816	 * Now see if we can convert the single-leaf directory
1817	 * down to a block form directory.
1818	 * This routine always kills the dabuf for the leaf, so
1819	 * eliminate it from the path.
1820	 */
1821	error = xfs_dir2_leaf_to_block(args, lbp, NULL);
1822	state->path.blk[0].bp = NULL;
1823	return error;
1824}