xfs_dir2_node.c 62.4 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
Linus Torvalds's avatar
Linus Torvalds committed
2
/*
3
 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
4
 * Copyright (c) 2013 Red Hat, Inc.
5
 * All Rights Reserved.
Linus Torvalds's avatar
Linus Torvalds committed
6 7
 */
#include "xfs.h"
8
#include "xfs_fs.h"
9
#include "xfs_shared.h"
10
#include "xfs_format.h"
11 12
#include "xfs_log_format.h"
#include "xfs_trans_resv.h"
Linus Torvalds's avatar
Linus Torvalds committed
13 14 15
#include "xfs_mount.h"
#include "xfs_inode.h"
#include "xfs_bmap.h"
16
#include "xfs_dir2.h"
17
#include "xfs_dir2_priv.h"
Linus Torvalds's avatar
Linus Torvalds committed
18
#include "xfs_error.h"
19
#include "xfs_trace.h"
20
#include "xfs_trans.h"
21
#include "xfs_buf_item.h"
22
#include "xfs_log.h"
Linus Torvalds's avatar
Linus Torvalds committed
23 24 25 26

/*
 * Function declarations.
 */
27 28
static int xfs_dir2_leafn_add(struct xfs_buf *bp, xfs_da_args_t *args,
			      int index);
Linus Torvalds's avatar
Linus Torvalds committed
29 30 31
static void xfs_dir2_leafn_rebalance(xfs_da_state_t *state,
				     xfs_da_state_blk_t *blk1,
				     xfs_da_state_blk_t *blk2);
32
static int xfs_dir2_leafn_remove(xfs_da_args_t *args, struct xfs_buf *bp,
Linus Torvalds's avatar
Linus Torvalds committed
33 34 35
				 int index, xfs_da_state_blk_t *dblk,
				 int *rval);

36 37 38 39
/*
 * Check internal consistency of a leafn block.
 */
#ifdef DEBUG
40
static xfs_failaddr_t
41
xfs_dir3_leafn_check(
42
	struct xfs_inode	*dp,
43 44 45 46 47
	struct xfs_buf		*bp)
{
	struct xfs_dir2_leaf	*leaf = bp->b_addr;
	struct xfs_dir3_icleaf_hdr leafhdr;

48
	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
49 50 51 52

	if (leafhdr.magic == XFS_DIR3_LEAFN_MAGIC) {
		struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
		if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn)
53
			return __this_address;
54
	} else if (leafhdr.magic != XFS_DIR2_LEAFN_MAGIC)
55
		return __this_address;
56

57
	return xfs_dir3_leaf_check_int(dp->i_mount, dp, &leafhdr, leaf);
58
}
59 60 61 62 63 64 65 66 67 68 69 70

static inline void
xfs_dir3_leaf_check(
	struct xfs_inode	*dp,
	struct xfs_buf		*bp)
{
	xfs_failaddr_t		fa;

	fa = xfs_dir3_leafn_check(dp, bp);
	if (!fa)
		return;
	xfs_corruption_error(__func__, XFS_ERRLEVEL_LOW, dp->i_mount,
71 72
			bp->b_addr, BBTOB(bp->b_length), __FILE__, __LINE__,
			fa);
73 74
	ASSERT(0);
}
75
#else
76
#define	xfs_dir3_leaf_check(dp, bp)
77 78
#endif

79
static xfs_failaddr_t
80
xfs_dir3_free_verify(
81 82
	struct xfs_buf		*bp)
{
83
	struct xfs_mount	*mp = bp->b_mount;
84 85
	struct xfs_dir2_free_hdr *hdr = bp->b_addr;

86 87 88
	if (!xfs_verify_magic(bp, hdr->magic))
		return __this_address;

89 90 91
	if (xfs_sb_version_hascrc(&mp->m_sb)) {
		struct xfs_dir3_blk_hdr *hdr3 = bp->b_addr;

92
		if (!uuid_equal(&hdr3->uuid, &mp->m_sb.sb_meta_uuid))
93
			return __this_address;
94
		if (be64_to_cpu(hdr3->blkno) != bp->b_bn)
95
			return __this_address;
96
		if (!xfs_log_check_lsn(mp, be64_to_cpu(hdr3->lsn)))
97
			return __this_address;
98
	}
99 100 101

	/* XXX: should bounds check the xfs_dir3_icfree_hdr here */

102
	return NULL;
103
}
104

105
static void
106
xfs_dir3_free_read_verify(
107 108
	struct xfs_buf	*bp)
{
109
	struct xfs_mount	*mp = bp->b_mount;
110
	xfs_failaddr_t		fa;
111

112 113
	if (xfs_sb_version_hascrc(&mp->m_sb) &&
	    !xfs_buf_verify_cksum(bp, XFS_DIR3_FREE_CRC_OFF))
114 115 116 117 118 119
		xfs_verifier_error(bp, -EFSBADCRC, __this_address);
	else {
		fa = xfs_dir3_free_verify(bp);
		if (fa)
			xfs_verifier_error(bp, -EFSCORRUPTED, fa);
	}
120 121
}

122
static void
123
xfs_dir3_free_write_verify(
124 125
	struct xfs_buf	*bp)
{
126
	struct xfs_mount	*mp = bp->b_mount;
127
	struct xfs_buf_log_item	*bip = bp->b_log_item;
128
	struct xfs_dir3_blk_hdr	*hdr3 = bp->b_addr;
129
	xfs_failaddr_t		fa;
130

131 132 133
	fa = xfs_dir3_free_verify(bp);
	if (fa) {
		xfs_verifier_error(bp, -EFSCORRUPTED, fa);
134 135 136 137 138 139 140 141 142
		return;
	}

	if (!xfs_sb_version_hascrc(&mp->m_sb))
		return;

	if (bip)
		hdr3->lsn = cpu_to_be64(bip->bli_item.li_lsn);

143
	xfs_buf_update_cksum(bp, XFS_DIR3_FREE_CRC_OFF);
144 145
}

146
const struct xfs_buf_ops xfs_dir3_free_buf_ops = {
147
	.name = "xfs_dir3_free",
148 149
	.magic = { cpu_to_be32(XFS_DIR2_FREE_MAGIC),
		   cpu_to_be32(XFS_DIR3_FREE_MAGIC) },
150 151
	.verify_read = xfs_dir3_free_read_verify,
	.verify_write = xfs_dir3_free_write_verify,
152
	.verify_struct = xfs_dir3_free_verify,
153 154
};

155
/* Everything ok in the free block header? */
156
static xfs_failaddr_t
157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
xfs_dir3_free_header_check(
	struct xfs_inode	*dp,
	xfs_dablk_t		fbno,
	struct xfs_buf		*bp)
{
	struct xfs_mount	*mp = dp->i_mount;
	unsigned int		firstdb;
	int			maxbests;

	maxbests = dp->d_ops->free_max_bests(mp->m_dir_geo);
	firstdb = (xfs_dir2_da_to_db(mp->m_dir_geo, fbno) -
		   xfs_dir2_byte_to_db(mp->m_dir_geo, XFS_DIR2_FREE_OFFSET)) *
			maxbests;
	if (xfs_sb_version_hascrc(&mp->m_sb)) {
		struct xfs_dir3_free_hdr *hdr3 = bp->b_addr;

		if (be32_to_cpu(hdr3->firstdb) != firstdb)
174
			return __this_address;
175
		if (be32_to_cpu(hdr3->nvalid) > maxbests)
176
			return __this_address;
177
		if (be32_to_cpu(hdr3->nvalid) < be32_to_cpu(hdr3->nused))
178
			return __this_address;
179 180 181 182
	} else {
		struct xfs_dir2_free_hdr *hdr = bp->b_addr;

		if (be32_to_cpu(hdr->firstdb) != firstdb)
183
			return __this_address;
184
		if (be32_to_cpu(hdr->nvalid) > maxbests)
185
			return __this_address;
186
		if (be32_to_cpu(hdr->nvalid) < be32_to_cpu(hdr->nused))
187
			return __this_address;
188
	}
189
	return NULL;
190
}
191

192
static int
193
__xfs_dir3_free_read(
194 195 196 197 198 199
	struct xfs_trans	*tp,
	struct xfs_inode	*dp,
	xfs_dablk_t		fbno,
	xfs_daddr_t		mappedbno,
	struct xfs_buf		**bpp)
{
200
	xfs_failaddr_t		fa;
201 202 203
	int			err;

	err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
204
				XFS_DATA_FORK, &xfs_dir3_free_buf_ops);
205 206 207 208
	if (err || !*bpp)
		return err;

	/* Check things that we can't do in the verifier. */
209 210 211
	fa = xfs_dir3_free_header_check(dp, fbno, *bpp);
	if (fa) {
		xfs_verifier_error(*bpp, -EFSCORRUPTED, fa);
212 213 214
		xfs_trans_brelse(tp, *bpp);
		return -EFSCORRUPTED;
	}
215 216

	/* try read returns without an error or *bpp if it lands in a hole */
217
	if (tp)
218
		xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_FREE_BUF);
219 220

	return 0;
221 222 223 224 225 226 227 228 229
}

int
xfs_dir2_free_read(
	struct xfs_trans	*tp,
	struct xfs_inode	*dp,
	xfs_dablk_t		fbno,
	struct xfs_buf		**bpp)
{
230
	return __xfs_dir3_free_read(tp, dp, fbno, -1, bpp);
231 232 233 234 235 236 237 238 239
}

static int
xfs_dir2_free_try_read(
	struct xfs_trans	*tp,
	struct xfs_inode	*dp,
	xfs_dablk_t		fbno,
	struct xfs_buf		**bpp)
{
240 241 242 243 244
	return __xfs_dir3_free_read(tp, dp, fbno, -2, bpp);
}

static int
xfs_dir3_free_get_buf(
245
	xfs_da_args_t		*args,
246 247 248
	xfs_dir2_db_t		fbno,
	struct xfs_buf		**bpp)
{
249 250
	struct xfs_trans	*tp = args->trans;
	struct xfs_inode	*dp = args->dp;
251 252 253 254 255
	struct xfs_mount	*mp = dp->i_mount;
	struct xfs_buf		*bp;
	int			error;
	struct xfs_dir3_icfree_hdr hdr;

256
	error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(args->geo, fbno),
257 258 259 260
				   -1, &bp, XFS_DATA_FORK);
	if (error)
		return error;

261
	xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_FREE_BUF);
262 263 264 265 266 267
	bp->b_ops = &xfs_dir3_free_buf_ops;

	/*
	 * Initialize the new block to be empty, and remember
	 * its first slot as our empty slot.
	 */
268 269 270
	memset(bp->b_addr, 0, sizeof(struct xfs_dir3_free_hdr));
	memset(&hdr, 0, sizeof(hdr));

271 272 273 274
	if (xfs_sb_version_hascrc(&mp->m_sb)) {
		struct xfs_dir3_free_hdr *hdr3 = bp->b_addr;

		hdr.magic = XFS_DIR3_FREE_MAGIC;
275

276 277
		hdr3->hdr.blkno = cpu_to_be64(bp->b_bn);
		hdr3->hdr.owner = cpu_to_be64(dp->i_ino);
278
		uuid_copy(&hdr3->hdr.uuid, &mp->m_sb.sb_meta_uuid);
279 280
	} else
		hdr.magic = XFS_DIR2_FREE_MAGIC;
281
	dp->d_ops->free_hdr_to_disk(bp->b_addr, &hdr);
282 283
	*bpp = bp;
	return 0;
284 285
}

Linus Torvalds's avatar
Linus Torvalds committed
286 287 288
/*
 * Log entries from a freespace block.
 */
289
STATIC void
Linus Torvalds's avatar
Linus Torvalds committed
290
xfs_dir2_free_log_bests(
291
	struct xfs_da_args	*args,
292
	struct xfs_buf		*bp,
Linus Torvalds's avatar
Linus Torvalds committed
293 294 295 296
	int			first,		/* first entry to log */
	int			last)		/* last entry to log */
{
	xfs_dir2_free_t		*free;		/* freespace structure */
297
	__be16			*bests;
Linus Torvalds's avatar
Linus Torvalds committed
298

299
	free = bp->b_addr;
300
	bests = args->dp->d_ops->free_bests_p(free);
301 302
	ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC) ||
	       free->hdr.magic == cpu_to_be32(XFS_DIR3_FREE_MAGIC));
303
	xfs_trans_log_buf(args->trans, bp,
304 305 306
		(uint)((char *)&bests[first] - (char *)free),
		(uint)((char *)&bests[last] - (char *)free +
		       sizeof(bests[0]) - 1));
Linus Torvalds's avatar
Linus Torvalds committed
307 308 309 310 311 312 313
}

/*
 * Log header from a freespace block.
 */
static void
xfs_dir2_free_log_header(
314
	struct xfs_da_args	*args,
315
	struct xfs_buf		*bp)
Linus Torvalds's avatar
Linus Torvalds committed
316
{
317
#ifdef DEBUG
Linus Torvalds's avatar
Linus Torvalds committed
318 319
	xfs_dir2_free_t		*free;		/* freespace structure */

320
	free = bp->b_addr;
321 322
	ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC) ||
	       free->hdr.magic == cpu_to_be32(XFS_DIR3_FREE_MAGIC));
323
#endif
324 325
	xfs_trans_log_buf(args->trans, bp, 0,
			  args->dp->d_ops->free_hdr_size - 1);
Linus Torvalds's avatar
Linus Torvalds committed
326 327 328 329 330 331 332 333 334 335
}

/*
 * Convert a leaf-format directory to a node-format directory.
 * We need to change the magic number of the leaf block, and copy
 * the freespace table out of the leaf block into its own block.
 */
int						/* error */
xfs_dir2_leaf_to_node(
	xfs_da_args_t		*args,		/* operation arguments */
336
	struct xfs_buf		*lbp)		/* leaf buffer */
Linus Torvalds's avatar
Linus Torvalds committed
337 338 339
{
	xfs_inode_t		*dp;		/* incore directory inode */
	int			error;		/* error return value */
340
	struct xfs_buf		*fbp;		/* freespace buffer */
Linus Torvalds's avatar
Linus Torvalds committed
341 342
	xfs_dir2_db_t		fdb;		/* freespace block number */
	xfs_dir2_free_t		*free;		/* freespace structure */
343
	__be16			*from;		/* pointer to freespace entry */
Linus Torvalds's avatar
Linus Torvalds committed
344 345 346 347 348
	int			i;		/* leaf freespace index */
	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
	xfs_dir2_leaf_tail_t	*ltp;		/* leaf tail structure */
	int			n;		/* count of live freespc ents */
	xfs_dir2_data_off_t	off;		/* freespace entry value */
349
	__be16			*to;		/* pointer to freespace entry */
Linus Torvalds's avatar
Linus Torvalds committed
350
	xfs_trans_t		*tp;		/* transaction pointer */
351
	struct xfs_dir3_icfree_hdr freehdr;
Linus Torvalds's avatar
Linus Torvalds committed
352

353 354
	trace_xfs_dir2_leaf_to_node(args);

Linus Torvalds's avatar
Linus Torvalds committed
355 356 357 358 359 360 361 362
	dp = args->dp;
	tp = args->trans;
	/*
	 * Add a freespace block to the directory.
	 */
	if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE, &fdb))) {
		return error;
	}
363
	ASSERT(fdb == xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET));
Linus Torvalds's avatar
Linus Torvalds committed
364 365 366
	/*
	 * Get the buffer for the new freespace block.
	 */
367
	error = xfs_dir3_free_get_buf(args, fdb, &fbp);
368
	if (error)
Linus Torvalds's avatar
Linus Torvalds committed
369
		return error;
370

371
	free = fbp->b_addr;
372
	dp->d_ops->free_hdr_from_disk(&freehdr, free);
373
	leaf = lbp->b_addr;
374
	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
375
	if (be32_to_cpu(ltp->bestcount) >
376 377
				(uint)dp->i_d.di_size / args->geo->blksize) {
		xfs_buf_corruption_error(lbp);
378
		return -EFSCORRUPTED;
379
	}
380

Linus Torvalds's avatar
Linus Torvalds committed
381 382 383 384
	/*
	 * Copy freespace entries from the leaf block to the new block.
	 * Count active entries.
	 */
385
	from = xfs_dir2_leaf_bests_p(ltp);
386
	to = dp->d_ops->free_bests_p(free);
387
	for (i = n = 0; i < be32_to_cpu(ltp->bestcount); i++, from++, to++) {
388
		if ((off = be16_to_cpu(*from)) != NULLDATAOFF)
Linus Torvalds's avatar
Linus Torvalds committed
389
			n++;
390
		*to = cpu_to_be16(off);
Linus Torvalds's avatar
Linus Torvalds committed
391
	}
392

Linus Torvalds's avatar
Linus Torvalds committed
393
	/*
394
	 * Now initialize the freespace block header.
Linus Torvalds's avatar
Linus Torvalds committed
395
	 */
396 397 398
	freehdr.nused = n;
	freehdr.nvalid = be32_to_cpu(ltp->bestcount);

399
	dp->d_ops->free_hdr_to_disk(fbp->b_addr, &freehdr);
400 401
	xfs_dir2_free_log_bests(args, fbp, 0, freehdr.nvalid - 1);
	xfs_dir2_free_log_header(args, fbp);
402

403 404 405 406 407 408 409 410 411 412 413
	/*
	 * Converting the leaf to a leafnode is just a matter of changing the
	 * magic number and the ops. Do the change directly to the buffer as
	 * it's less work (and less code) than decoding the header to host
	 * format and back again.
	 */
	if (leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC))
		leaf->hdr.info.magic = cpu_to_be16(XFS_DIR2_LEAFN_MAGIC);
	else
		leaf->hdr.info.magic = cpu_to_be16(XFS_DIR3_LEAFN_MAGIC);
	lbp->b_ops = &xfs_dir3_leafn_buf_ops;
414
	xfs_trans_buf_set_type(tp, lbp, XFS_BLFT_DIR_LEAFN_BUF);
415
	xfs_dir3_leaf_log_header(args, lbp);
416
	xfs_dir3_leaf_check(dp, lbp);
Linus Torvalds's avatar
Linus Torvalds committed
417 418 419 420 421 422 423 424 425
	return 0;
}

/*
 * Add a leaf entry to a leaf block in a node-form directory.
 * The other work necessary is done from the caller.
 */
static int					/* error */
xfs_dir2_leafn_add(
426
	struct xfs_buf		*bp,		/* leaf buffer */
427
	struct xfs_da_args	*args,		/* operation arguments */
Linus Torvalds's avatar
Linus Torvalds committed
428 429
	int			index)		/* insertion pt for new entry */
{
430 431 432 433 434
	struct xfs_dir3_icleaf_hdr leafhdr;
	struct xfs_inode	*dp = args->dp;
	struct xfs_dir2_leaf	*leaf = bp->b_addr;
	struct xfs_dir2_leaf_entry *lep;
	struct xfs_dir2_leaf_entry *ents;
Linus Torvalds's avatar
Linus Torvalds committed
435
	int			compact;	/* compacting stale leaves */
436
	int			highstale = 0;	/* next stale entry */
Linus Torvalds's avatar
Linus Torvalds committed
437 438
	int			lfloghigh;	/* high leaf entry logging */
	int			lfloglow;	/* low leaf entry logging */
439
	int			lowstale = 0;	/* previous stale entry */
Linus Torvalds's avatar
Linus Torvalds committed
440

441 442
	trace_xfs_dir2_leafn_add(args, index);

443
	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
444
	ents = dp->d_ops->leaf_ents_p(leaf);
Linus Torvalds's avatar
Linus Torvalds committed
445 446 447 448 449

	/*
	 * Quick check just to make sure we are not going to index
	 * into other peoples memory
	 */
450 451
	if (index < 0) {
		xfs_buf_corruption_error(bp);
452
		return -EFSCORRUPTED;
453
	}
Linus Torvalds's avatar
Linus Torvalds committed
454 455 456 457 458 459 460 461

	/*
	 * If there are already the maximum number of leaf entries in
	 * the block, if there are no stale entries it won't fit.
	 * Caller will do a split.  If there are stale entries we'll do
	 * a compact.
	 */

462
	if (leafhdr.count == dp->d_ops->leaf_max_ents(args->geo)) {
463
		if (!leafhdr.stale)
464
			return -ENOSPC;
465
		compact = leafhdr.stale > 1;
Linus Torvalds's avatar
Linus Torvalds committed
466 467
	} else
		compact = 0;
468 469 470
	ASSERT(index == 0 || be32_to_cpu(ents[index - 1].hashval) <= args->hashval);
	ASSERT(index == leafhdr.count ||
	       be32_to_cpu(ents[index].hashval) >= args->hashval);
Linus Torvalds's avatar
Linus Torvalds committed
471

472
	if (args->op_flags & XFS_DA_OP_JUSTCHECK)
Linus Torvalds's avatar
Linus Torvalds committed
473 474 475 476 477 478
		return 0;

	/*
	 * Compact out all but one stale leaf entry.  Leaves behind
	 * the entry closest to index.
	 */
479 480 481 482 483 484 485 486
	if (compact)
		xfs_dir3_leaf_compact_x1(&leafhdr, ents, &index, &lowstale,
					 &highstale, &lfloglow, &lfloghigh);
	else if (leafhdr.stale) {
		/*
		 * Set impossible logging indices for this case.
		 */
		lfloglow = leafhdr.count;
Linus Torvalds's avatar
Linus Torvalds committed
487 488
		lfloghigh = -1;
	}
489

Linus Torvalds's avatar
Linus Torvalds committed
490 491 492
	/*
	 * Insert the new entry, log everything.
	 */
493
	lep = xfs_dir3_leaf_find_entry(&leafhdr, ents, index, compact, lowstale,
494 495
				       highstale, &lfloglow, &lfloghigh);

496
	lep->hashval = cpu_to_be32(args->hashval);
497
	lep->address = cpu_to_be32(xfs_dir2_db_off_to_dataptr(args->geo,
498
				args->blkno, args->index));
499

500
	dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
501 502
	xfs_dir3_leaf_log_header(args, bp);
	xfs_dir3_leaf_log_ents(args, bp, lfloglow, lfloghigh);
503
	xfs_dir3_leaf_check(dp, bp);
Linus Torvalds's avatar
Linus Torvalds committed
504 505 506 507
	return 0;
}

#ifdef DEBUG
508 509
static void
xfs_dir2_free_hdr_check(
510
	struct xfs_inode *dp,
511 512 513 514 515
	struct xfs_buf	*bp,
	xfs_dir2_db_t	db)
{
	struct xfs_dir3_icfree_hdr hdr;

516
	dp->d_ops->free_hdr_from_disk(&hdr, bp->b_addr);
517

518 519
	ASSERT((hdr.firstdb %
		dp->d_ops->free_max_bests(dp->i_mount->m_dir_geo)) == 0);
520 521 522 523
	ASSERT(hdr.firstdb <= db);
	ASSERT(db < hdr.firstdb + hdr.nvalid);
}
#else
524
#define xfs_dir2_free_hdr_check(dp, bp, db)
Linus Torvalds's avatar
Linus Torvalds committed
525 526 527 528 529 530 531
#endif	/* DEBUG */

/*
 * Return the last hash value in the leaf.
 * Stale entries are ok.
 */
xfs_dahash_t					/* hash value */
532
xfs_dir2_leaf_lasthash(
533
	struct xfs_inode *dp,
534
	struct xfs_buf	*bp,			/* leaf buffer */
Linus Torvalds's avatar
Linus Torvalds committed
535 536
	int		*count)			/* count of entries in leaf */
{
537 538 539 540
	struct xfs_dir2_leaf	*leaf = bp->b_addr;
	struct xfs_dir2_leaf_entry *ents;
	struct xfs_dir3_icleaf_hdr leafhdr;

541
	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
542 543

	ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
544 545 546
	       leafhdr.magic == XFS_DIR3_LEAFN_MAGIC ||
	       leafhdr.magic == XFS_DIR2_LEAF1_MAGIC ||
	       leafhdr.magic == XFS_DIR3_LEAF1_MAGIC);
Linus Torvalds's avatar
Linus Torvalds committed
547 548

	if (count)
549 550
		*count = leafhdr.count;
	if (!leafhdr.count)
Linus Torvalds's avatar
Linus Torvalds committed
551
		return 0;
552

553
	ents = dp->d_ops->leaf_ents_p(leaf);
554
	return be32_to_cpu(ents[leafhdr.count - 1].hashval);
Linus Torvalds's avatar
Linus Torvalds committed
555 556 557
}

/*
558 559
 * Look up a leaf entry for space to add a name in a node-format leaf block.
 * The extrablk in state is a freespace block.
Linus Torvalds's avatar
Linus Torvalds committed
560
 */
561 562
STATIC int
xfs_dir2_leafn_lookup_for_addname(
563
	struct xfs_buf		*bp,		/* leaf buffer */
Linus Torvalds's avatar
Linus Torvalds committed
564 565 566 567
	xfs_da_args_t		*args,		/* operation arguments */
	int			*indexp,	/* out: leaf entry index */
	xfs_da_state_t		*state)		/* state to fill in */
{
568
	struct xfs_buf		*curbp = NULL;	/* current data/free buffer */
569 570
	xfs_dir2_db_t		curdb = -1;	/* current data block number */
	xfs_dir2_db_t		curfdb = -1;	/* current free block number */
Linus Torvalds's avatar
Linus Torvalds committed
571 572 573
	xfs_inode_t		*dp;		/* incore directory inode */
	int			error;		/* error return value */
	int			fi;		/* free entry index */
574
	xfs_dir2_free_t		*free = NULL;	/* free block structure */
Linus Torvalds's avatar
Linus Torvalds committed
575 576
	int			index;		/* leaf entry index */
	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
577
	int			length;		/* length of new data entry */
Linus Torvalds's avatar
Linus Torvalds committed
578 579 580 581 582
	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
	xfs_mount_t		*mp;		/* filesystem mount point */
	xfs_dir2_db_t		newdb;		/* new data block number */
	xfs_dir2_db_t		newfdb;		/* new free block number */
	xfs_trans_t		*tp;		/* transaction pointer */
583 584
	struct xfs_dir2_leaf_entry *ents;
	struct xfs_dir3_icleaf_hdr leafhdr;
Linus Torvalds's avatar
Linus Torvalds committed
585 586 587 588

	dp = args->dp;
	tp = args->trans;
	mp = dp->i_mount;
589
	leaf = bp->b_addr;
590
	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
591
	ents = dp->d_ops->leaf_ents_p(leaf);
592

593
	xfs_dir3_leaf_check(dp, bp);
594 595
	ASSERT(leafhdr.count > 0);

Linus Torvalds's avatar
Linus Torvalds committed
596 597 598 599 600 601 602
	/*
	 * Look up the hash value in the leaf entries.
	 */
	index = xfs_dir2_leaf_search_hash(args, bp);
	/*
	 * Do we have a buffer coming in?
	 */
603 604
	if (state->extravalid) {
		/* If so, it's a free block buffer, get the block number. */
Linus Torvalds's avatar
Linus Torvalds committed
605
		curbp = state->extrablk.bp;
606
		curfdb = state->extrablk.blkno;
607
		free = curbp->b_addr;
608 609
		ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC) ||
		       free->hdr.magic == cpu_to_be32(XFS_DIR3_FREE_MAGIC));
Linus Torvalds's avatar
Linus Torvalds committed
610
	}
611
	length = dp->d_ops->data_entsize(args->namelen);
Linus Torvalds's avatar
Linus Torvalds committed
612 613 614
	/*
	 * Loop over leaf entries with the right hash value.
	 */
615 616 617
	for (lep = &ents[index];
	     index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
	     lep++, index++) {
Linus Torvalds's avatar
Linus Torvalds committed
618 619 620
		/*
		 * Skip stale leaf entries.
		 */
621
		if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
Linus Torvalds's avatar
Linus Torvalds committed
622 623 624 625
			continue;
		/*
		 * Pull the data block number from the entry.
		 */
626 627
		newdb = xfs_dir2_dataptr_to_db(args->geo,
					       be32_to_cpu(lep->address));
Linus Torvalds's avatar
Linus Torvalds committed
628 629 630 631
		/*
		 * For addname, we're looking for a place to put the new entry.
		 * We want to use a data block with an entry of equal
		 * hash value to ours if there is one with room.
632 633 634
		 *
		 * If this block isn't the data block we already have
		 * in hand, take a look at it.
Linus Torvalds's avatar
Linus Torvalds committed
635
		 */
636
		if (newdb != curdb) {
637 638
			__be16 *bests;

639
			curdb = newdb;
Linus Torvalds's avatar
Linus Torvalds committed
640
			/*
641 642
			 * Convert the data block to the free block
			 * holding its freespace information.
Linus Torvalds's avatar
Linus Torvalds committed
643
			 */
644
			newfdb = dp->d_ops->db_to_fdb(args->geo, newdb);
Linus Torvalds's avatar
Linus Torvalds committed
645
			/*
646
			 * If it's not the one we have in hand, read it in.
Linus Torvalds's avatar
Linus Torvalds committed
647
			 */
648
			if (newfdb != curfdb) {
Linus Torvalds's avatar
Linus Torvalds committed
649
				/*
650
				 * If we had one before, drop it.
Linus Torvalds's avatar
Linus Torvalds committed
651 652
				 */
				if (curbp)
653
					xfs_trans_brelse(tp, curbp);
654 655

				error = xfs_dir2_free_read(tp, dp,
656 657
						xfs_dir2_db_to_da(args->geo,
								  newfdb),
658
						&curbp);
659
				if (error)
Linus Torvalds's avatar
Linus Torvalds committed
660
					return error;
661
				free = curbp->b_addr;
662

663
				xfs_dir2_free_hdr_check(dp, curbp, curdb);
Linus Torvalds's avatar
Linus Torvalds committed
664 665
			}
			/*
666
			 * Get the index for our entry.
Linus Torvalds's avatar
Linus Torvalds committed
667
			 */
668
			fi = dp->d_ops->db_to_fdindex(args->geo, curdb);
Linus Torvalds's avatar
Linus Torvalds committed
669
			/*
670
			 * If it has room, return it.
Linus Torvalds's avatar
Linus Torvalds committed
671
			 */
672
			bests = dp->d_ops->free_bests_p(free);
673
			if (unlikely(bests[fi] == cpu_to_be16(NULLDATAOFF))) {
674 675 676
				XFS_ERROR_REPORT("xfs_dir2_leafn_lookup_int",
							XFS_ERRLEVEL_LOW, mp);
				if (curfdb != newfdb)
677
					xfs_trans_brelse(tp, curbp);
678
				return -EFSCORRUPTED;
Linus Torvalds's avatar
Linus Torvalds committed
679
			}
680
			curfdb = newfdb;
681
			if (be16_to_cpu(bests[fi]) >= length)
682
				goto out;
Linus Torvalds's avatar
Linus Torvalds committed
683 684
		}
	}
685 686 687
	/* Didn't find any space */
	fi = -1;
out:
688
	ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
689 690 691 692 693 694
	if (curbp) {
		/* Giving back a free block. */
		state->extravalid = 1;
		state->extrablk.bp = curbp;
		state->extrablk.index = fi;
		state->extrablk.blkno = curfdb;
695 696 697 698 699 700

		/*
		 * Important: this magic number is not in the buffer - it's for
		 * buffer type information and therefore only the free/data type
		 * matters here, not whether CRCs are enabled or not.
		 */
701 702 703 704
		state->extrablk.magic = XFS_DIR2_FREE_MAGIC;
	} else {
		state->extravalid = 0;
	}
Linus Torvalds's avatar
Linus Torvalds committed
705
	/*
706
	 * Return the index, that will be the insertion point.
Linus Torvalds's avatar
Linus Torvalds committed
707
	 */
708
	*indexp = index;
709
	return -ENOENT;
710 711 712 713 714 715 716 717
}

/*
 * Look up a leaf entry in a node-format leaf block.
 * The extrablk in state a data block.
 */
STATIC int
xfs_dir2_leafn_lookup_for_entry(
718
	struct xfs_buf		*bp,		/* leaf buffer */
719 720 721 722
	xfs_da_args_t		*args,		/* operation arguments */
	int			*indexp,	/* out: leaf entry index */
	xfs_da_state_t		*state)		/* state to fill in */
{
723
	struct xfs_buf		*curbp = NULL;	/* current data/free buffer */
724 725 726 727 728 729 730 731 732 733
	xfs_dir2_db_t		curdb = -1;	/* current data block number */
	xfs_dir2_data_entry_t	*dep;		/* data block entry */
	xfs_inode_t		*dp;		/* incore directory inode */
	int			error;		/* error return value */
	int			index;		/* leaf entry index */
	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
	xfs_mount_t		*mp;		/* filesystem mount point */
	xfs_dir2_db_t		newdb;		/* new data block number */
	xfs_trans_t		*tp;		/* transaction pointer */
734
	enum xfs_dacmp		cmp;		/* comparison result */
735 736
	struct xfs_dir2_leaf_entry *ents;
	struct xfs_dir3_icleaf_hdr leafhdr;
737 738 739 740

	dp = args->dp;
	tp = args->trans;
	mp = dp->i_mount;
741
	leaf = bp->b_addr;
742
	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
743
	ents = dp->d_ops->leaf_ents_p(leaf);
744

745
	xfs_dir3_leaf_check(dp, bp);
746 747
	if (leafhdr.count <= 0) {
		xfs_buf_corruption_error(bp);
748
		return -EFSCORRUPTED;
749
	}
750

751 752 753 754 755 756 757 758 759 760 761 762 763 764
	/*
	 * Look up the hash value in the leaf entries.
	 */
	index = xfs_dir2_leaf_search_hash(args, bp);
	/*
	 * Do we have a buffer coming in?
	 */
	if (state->extravalid) {
		curbp = state->extrablk.bp;
		curdb = state->extrablk.blkno;
	}
	/*
	 * Loop over leaf entries with the right hash value.
	 */
765 766 767
	for (lep = &ents[index];
	     index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
	     lep++, index++) {
768 769 770 771 772
		/*
		 * Skip stale leaf entries.
		 */
		if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
			continue;
Linus Torvalds's avatar
Linus Torvalds committed
773
		/*
774 775
		 * Pull the data block number from the entry.
		 */
776 777
		newdb = xfs_dir2_dataptr_to_db(args->geo,
					       be32_to_cpu(lep->address));
778 779 780 781 782
		/*
		 * Not adding a new entry, so we really want to find
		 * the name given to us.
		 *
		 * If it's a different data block, go get it.
Linus Torvalds's avatar
Linus Torvalds committed
783
		 */
784 785
		if (newdb != curdb) {
			/*
786 787
			 * If we had a block before that we aren't saving
			 * for a CI name, drop it
788
			 */
789 790
			if (curbp && (args->cmpresult == XFS_CMP_DIFFERENT ||
						curdb != state->extrablk.blkno))
791
				xfs_trans_brelse(tp, curbp);
792
			/*
793 794
			 * If needing the block that is saved with a CI match,
			 * use it otherwise read in the new data block.
795
			 */
796 797 798 799 800
			if (args->cmpresult != XFS_CMP_DIFFERENT &&
					newdb == state->extrablk.blkno) {
				ASSERT(state->extravalid);
				curbp = state->extrablk.bp;
			} else {
801
				error = xfs_dir3_data_read(tp, dp,
802 803
						xfs_dir2_db_to_da(args->geo,
								  newdb),
804
						-1, &curbp);
805 806 807
				if (error)
					return error;
			}
808
			xfs_dir3_data_check(dp, curbp);
809
			curdb = newdb;
Linus Torvalds's avatar
Linus Torvalds committed
810 811
		}
		/*
812
		 * Point to the data entry.
Linus Torvalds's avatar
Linus Torvalds committed
813
		 */
814
		dep = (xfs_dir2_data_entry_t *)((char *)curbp->b_addr +
815 816
			xfs_dir2_dataptr_to_off(args->geo,
						be32_to_cpu(lep->address)));
817
		/*
818 819
		 * Compare the entry and if it's an exact match, return
		 * EEXIST immediately. If it's the first case-insensitive
820
		 * match, store the block & inode number and continue looking.
821
		 */
822 823
		cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen);
		if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {
824 825 826
			/* If there is a CI match block, drop it */
			if (args->cmpresult != XFS_CMP_DIFFERENT &&
						curdb != state->extrablk.blkno)
827
				xfs_trans_brelse(tp, state->extrablk.bp);
828
			args->cmpresult = cmp;
829
			args->inumber = be64_to_cpu(dep->inumber);
830
			args->filetype = dp->d_ops->data_get_ftype(dep);
831 832 833 834 835
			*indexp = index;
			state->extravalid = 1;
			state->extrablk.bp = curbp;
			state->extrablk.blkno = curdb;
			state->extrablk.index = (int)((char *)dep -
836
							(char *)curbp->b_addr);
837
			state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
838
			curbp->b_ops = &xfs_dir3_data_buf_ops;
839
			xfs_trans_buf_set_type(tp, curbp, XFS_BLFT_DIR_DATA_BUF);
840
			if (cmp == XFS_CMP_EXACT)
841
				return -EEXIST;
Linus Torvalds's avatar
Linus Torvalds committed
842 843
		}
	}
844
	ASSERT(index == leafhdr.count || (args->op_flags & XFS_DA_OP_OKNOENT));
845
	if (curbp) {
846 847 848 849 850 851 852
		if (args->cmpresult == XFS_CMP_DIFFERENT) {
			/* Giving back last used data block. */
			state->extravalid = 1;
			state->extrablk.bp = curbp;
			state->extrablk.index = -1;
			state->extrablk.blkno = curdb;
			state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
853
			curbp->b_ops = &xfs_dir3_data_buf_ops;
854
			xfs_trans_buf_set_type(tp, curbp, XFS_BLFT_DIR_DATA_BUF);
855 856 857
		} else {
			/* If the curbp is not the CI match block, drop it */
			if (state->extrablk.bp != curbp)
858
				xfs_trans_brelse(tp, curbp);
859
		}
860 861 862
	} else {
		state->extravalid = 0;
	}
Linus Torvalds's avatar
Linus Torvalds committed
863
	*indexp = index;
864
	return -ENOENT;
865 866 867 868 869 870 871 872 873
}

/*
 * Look up a leaf entry in a node-format leaf block.
 * If this is an addname then the extrablk in state is a freespace block,
 * otherwise it's a data block.
 */
int
xfs_dir2_leafn_lookup_int(
874
	struct xfs_buf		*bp,		/* leaf buffer */
875 876 877 878
	xfs_da_args_t		*args,		/* operation arguments */
	int			*indexp,	/* out: leaf entry index */
	xfs_da_state_t		*state)		/* state to fill in */
{
879
	if (args->op_flags & XFS_DA_OP_ADDNAME)
880 881 882
		return xfs_dir2_leafn_lookup_for_addname(bp, args, indexp,
							state);
	return xfs_dir2_leafn_lookup_for_entry(bp, args, indexp, state);
Linus Torvalds's avatar
Linus Torvalds committed
883 884 885 886 887 888 889
}

/*
 * Move count leaf entries from source to destination leaf.
 * Log entries and headers.  Stale entries are preserved.
 */
static void
890 891 892 893 894 895 896 897 898 899 900
xfs_dir3_leafn_moveents(
	xfs_da_args_t			*args,	/* operation arguments */
	struct xfs_buf			*bp_s,	/* source */
	struct xfs_dir3_icleaf_hdr	*shdr,
	struct xfs_dir2_leaf_entry	*sents,
	int				start_s,/* source leaf index */
	struct xfs_buf			*bp_d,	/* destination */
	struct xfs_dir3_icleaf_hdr	*dhdr,
	struct xfs_dir2_leaf_entry	*dents,
	int				start_d,/* destination leaf index */
	int				count)	/* count of leaves to copy */
Linus Torvalds's avatar
Linus Torvalds committed
901
{
902
	int				stale;	/* count stale leaves copied */
Linus Torvalds's avatar
Linus Torvalds committed
903

904 905
	trace_xfs_dir2_leafn_moveents(args, start_s, start_d, count);

Linus Torvalds's avatar
Linus Torvalds committed
906 907 908
	/*
	 * Silently return if nothing to do.
	 */
909
	if (count == 0)
Linus Torvalds's avatar
Linus Torvalds committed
910
		return;
911

Linus Torvalds's avatar
Linus Torvalds committed
912 913 914 915 916
	/*
	 * If the destination index is not the end of the current
	 * destination leaf entries, open up a hole in the destination
	 * to hold the new entries.
	 */
917 918 919
	if (start_d < dhdr->count) {
		memmove(&dents[start_d + count], &dents[start_d],
			(dhdr->count - start_d) * sizeof(xfs_dir2_leaf_entry_t));
920
		xfs_dir3_leaf_log_ents(args, bp_d, start_d + count,
921
				       count + dhdr->count - 1);
Linus Torvalds's avatar
Linus Torvalds committed
922 923 924 925 926
	}
	/*
	 * If the source has stale leaves, count the ones in the copy range
	 * so we can update the header correctly.
	 */
927
	if (shdr->stale) {
Linus Torvalds's avatar
Linus Torvalds committed
928 929 930
		int	i;			/* temp leaf index */

		for (i = start_s, stale = 0; i < start_s + count; i++) {
931 932
			if (sents[i].address ==
					cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
Linus Torvalds's avatar
Linus Torvalds committed
933 934 935 936 937 938 939
				stale++;
		}
	} else
		stale = 0;
	/*
	 * Copy the leaf entries from source to destination.
	 */
940
	memcpy(&dents[start_d], &sents[start_s],
Linus Torvalds's avatar
Linus Torvalds committed
941
		count * sizeof(xfs_dir2_leaf_entry_t));
942
	xfs_dir3_leaf_log_ents(args, bp_d, start_d, start_d + count - 1);
943

Linus Torvalds's avatar
Linus Torvalds committed
944 945 946 947
	/*
	 * If there are source entries after the ones we copied,
	 * delete the ones we copied by sliding the next ones down.
	 */
948 949
	if (start_s + count < shdr->count) {
		memmove(&sents[start_s], &sents[start_s + count],
Linus Torvalds's avatar
Linus Torvalds committed
950
			count * sizeof(xfs_dir2_leaf_entry_t));
951
		xfs_dir3_leaf_log_ents(args, bp_s, start_s, start_s + count - 1);
Linus Torvalds's avatar
Linus Torvalds committed
952
	}
953

Linus Torvalds's avatar
Linus Torvalds committed
954 955 956
	/*
	 * Update the headers and log them.
	 */
957 958 959 960
	shdr->count -= count;
	shdr->stale -= stale;
	dhdr->count += count;
	dhdr->stale += stale;
Linus Torvalds's avatar
Linus Torvalds committed
961 962 963 964 965 966 967 968
}

/*
 * Determine the sort order of two leaf blocks.
 * Returns 1 if both are valid and leaf2 should be before leaf1, else 0.
 */
int						/* sort order */
xfs_dir2_leafn_order(
969
	struct xfs_inode	*dp,
970 971
	struct xfs_buf		*leaf1_bp,		/* leaf1 buffer */
	struct xfs_buf		*leaf2_bp)		/* leaf2 buffer */
Linus Torvalds's avatar
Linus Torvalds committed
972
{
973 974 975 976 977 978 979
	struct xfs_dir2_leaf	*leaf1 = leaf1_bp->b_addr;
	struct xfs_dir2_leaf	*leaf2 = leaf2_bp->b_addr;
	struct xfs_dir2_leaf_entry *ents1;
	struct xfs_dir2_leaf_entry *ents2;
	struct xfs_dir3_icleaf_hdr hdr1;
	struct xfs_dir3_icleaf_hdr hdr2;

980 981
	dp->d_ops->leaf_hdr_from_disk(&hdr1, leaf1);
	dp->d_ops->leaf_hdr_from_disk(&hdr2, leaf2);
982 983
	ents1 = dp->d_ops->leaf_ents_p(leaf1);
	ents2 = dp->d_ops->leaf_ents_p(leaf2);
984 985 986 987 988

	if (hdr1.count > 0 && hdr2.count > 0 &&
	    (be32_to_cpu(ents2[0].hashval) < be32_to_cpu(ents1[0].hashval) ||
	     be32_to_cpu(ents2[hdr2.count - 1].hashval) <
				be32_to_cpu(ents1[hdr1.count - 1].hashval)))
Linus Torvalds's avatar
Linus Torvalds committed
989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011
		return 1;
	return 0;
}

/*
 * Rebalance leaf entries between two leaf blocks.
 * This is actually only called when the second block is new,
 * though the code deals with the general case.
 * A new entry will be inserted in one of the blocks, and that
 * entry is taken into account when balancing.
 */
static void
xfs_dir2_leafn_rebalance(
	xfs_da_state_t		*state,		/* btree cursor */
	xfs_da_state_blk_t	*blk1,		/* first btree block */
	xfs_da_state_blk_t	*blk2)		/* second btree block */
{
	xfs_da_args_t		*args;		/* operation arguments */
	int			count;		/* count (& direction) leaves */
	int			isleft;		/* new goes in left leaf */
	xfs_dir2_leaf_t		*leaf1;		/* first leaf structure */
	xfs_dir2_leaf_t		*leaf2;		/* second leaf structure */
	int			mid;		/* midpoint leaf index */
1012
#if defined(DEBUG) || defined(XFS_WARN)
Linus Torvalds's avatar
Linus Torvalds committed
1013 1014 1015
	int			oldstale;	/* old count of stale leaves */
#endif
	int			oldsum;		/* old total leaf count */
1016
	int			swap_blocks;	/* swapped leaf blocks */
1017 1018 1019 1020
	struct xfs_dir2_leaf_entry *ents1;
	struct xfs_dir2_leaf_entry *ents2;
	struct xfs_dir3_icleaf_hdr hdr1;
	struct xfs_dir3_icleaf_hdr hdr2;
1021
	struct xfs_inode	*dp = state->args->dp;
Linus Torvalds's avatar
Linus Torvalds committed
1022 1023 1024 1025 1026

	args = state->args;
	/*
	 * If the block order is wrong, swap the arguments.
	 */
1027 1028 1029
	swap_blocks = xfs_dir2_leafn_order(dp, blk1->bp, blk2->bp);
	if (swap_blocks)
		swap(blk1, blk2);
Linus Torvalds's avatar
Linus Torvalds committed
1030

1031 1032
	leaf1 = blk1->bp->b_addr;
	leaf2 = blk2->bp->b_addr;
1033 1034
	dp->d_ops->leaf_hdr_from_disk(&hdr1, leaf1);
	dp->d_ops->leaf_hdr_from_disk(&hdr2, leaf2);
1035 1036
	ents1 = dp->d_ops->leaf_ents_p(leaf1);
	ents2 = dp->d_ops->leaf_ents_p(leaf2);
1037 1038

	oldsum = hdr1.count + hdr2.count;
1039
#if defined(DEBUG) || defined(XFS_WARN)
1040
	oldstale = hdr1.stale + hdr2.stale;
Linus Torvalds's avatar
Linus Torvalds committed
1041 1042
#endif
	mid = oldsum >> 1;
1043

Linus Torvalds's avatar
Linus Torvalds committed
1044 1045 1046 1047 1048 1049 1050
	/*
	 * If the old leaf count was odd then the new one will be even,
	 * so we need to divide the new count evenly.
	 */
	if (oldsum & 1) {
		xfs_dahash_t	midhash;	/* middle entry hash value */

1051 1052
		if (mid >= hdr1.count)
			midhash = be32_to_cpu(ents2[mid - hdr1.count].hashval);
Linus Torvalds's avatar
Linus Torvalds committed
1053
		else
1054
			midhash = be32_to_cpu(ents1[mid].hashval);
Linus Torvalds's avatar
Linus Torvalds committed
1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067
		isleft = args->hashval <= midhash;
	}
	/*
	 * If the old count is even then the new count is odd, so there's
	 * no preferred side for the new entry.
	 * Pick the left one.
	 */
	else
		isleft = 1;
	/*
	 * Calculate moved entry count.  Positive means left-to-right,
	 * negative means right-to-left.  Then move the entries.
	 */
1068
	count = hdr1.count - mid + (isleft == 0);
Linus Torvalds's avatar
Linus Torvalds committed
1069
	if (count > 0)
1070 1071 1072
		xfs_dir3_leafn_moveents(args, blk1->bp, &hdr1, ents1,
					hdr1.count - count, blk2->bp,
					&hdr2, ents2, 0, count);
Linus Torvalds's avatar
Linus Torvalds committed
1073
	else if (count < 0)
1074 1075 1076 1077 1078 1079 1080 1081
		xfs_dir3_leafn_moveents(args, blk2->bp, &hdr2, ents2, 0,
					blk1->bp, &hdr1, ents1,
					hdr1.count, count);

	ASSERT(hdr1.count + hdr2.count == oldsum);
	ASSERT(hdr1.stale + hdr2.stale == oldstale);

	/* log the changes made when moving the entries */
1082 1083
	dp->d_ops->leaf_hdr_to_disk(leaf1, &hdr1);
	dp->d_ops->leaf_hdr_to_disk(leaf2, &hdr2);
1084 1085
	xfs_dir3_leaf_log_header(args, blk1->bp);
	xfs_dir3_leaf_log_header(args, blk2->bp);
1086

1087 1088
	xfs_dir3_leaf_check(dp, blk1->bp);
	xfs_dir3_leaf_check(dp, blk2->bp);
1089

Linus Torvalds's avatar
Linus Torvalds committed
1090 1091 1092
	/*
	 * Mark whether we're inserting into the old or new leaf.
	 */
1093
	if (hdr1.count < hdr2.count)
1094
		state->inleaf = swap_blocks;
1095
	else if (hdr1.count > hdr2.count)
1096
		state->inleaf = !swap_blocks;
Linus Torvalds's avatar
Linus Torvalds committed
1097
	else
1098
		state->inleaf = swap_blocks ^ (blk1->index <= hdr1.count);
Linus Torvalds's avatar
Linus Torvalds committed
1099 1100 1101 1102
	/*
	 * Adjust the expected index for insertion.
	 */
	if (!state->inleaf)
1103
		blk2->index = blk1->index - hdr1.count;
1104 1105 1106 1107

	/*
	 * Finally sanity check just to make sure we are not returning a
	 * negative index
Linus Torvalds's avatar
Linus Torvalds committed
1108
	 */
1109
	if (blk2->index < 0) {
Linus Torvalds's avatar
Linus Torvalds committed
1110 1111
		state->inleaf = 1;
		blk2->index = 0;
1112
		xfs_alert(dp->i_mount,
1113
	"%s: picked the wrong leaf? reverting original leaf: blk1->index %d",
1114
			__func__, blk1->index);
Linus Torvalds's avatar
Linus Torvalds committed
1115 1116 1117
	}
}

1118
static int
1119
xfs_dir3_data_block_free(
1120 1121 1122 1123 1124 1125 1126 1127 1128
	xfs_da_args_t		*args,
	struct xfs_dir2_data_hdr *hdr,
	struct xfs_dir2_free	*free,
	xfs_dir2_db_t		fdb,
	int			findex,
	struct xfs_buf		*fbp,
	int			longest)
{
	int			logfree = 0;
1129 1130
	__be16			*bests;
	struct xfs_dir3_icfree_hdr freehdr;
1131
	struct xfs_inode	*dp = args->dp;
1132

1133
	dp->d_ops->free_hdr_from_disk(&freehdr, free);
1134
	bests = dp->d_ops->free_bests_p(free);
1135
	if (hdr) {
1136
		/*
1137 1138
		 * Data block is not empty, just set the free entry to the new
		 * value.
1139
		 */
1140
		bests[findex] = cpu_to_be16(longest);
1141
		xfs_dir2_free_log_bests(args, fbp, findex, findex);
1142 1143
		return 0;
	}
1144

1145 1146
	/* One less used entry in the free table. */
	freehdr.nused--;
1147

1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158
	/*
	 * If this was the last entry in the table, we can trim the table size
	 * back.  There might be other entries at the end referring to
	 * non-existent data blocks, get those too.
	 */
	if (findex == freehdr.nvalid - 1) {
		int	i;		/* free entry index */

		for (i = findex - 1; i >= 0; i--) {
			if (bests[i] != cpu_to_be16(NULLDATAOFF))
				break;
1159
		}
1160 1161
		freehdr.nvalid = i + 1;
		logfree = 0;
1162
	} else {
1163 1164 1165 1166 1167
		/* Not the last entry, just punch it out.  */
		bests[findex] = cpu_to_be16(NULLDATAOFF);
		logfree = 1;
	}

1168
	dp->d_ops->free_hdr_to_disk(free, &freehdr);
1169
	xfs_dir2_free_log_header(args, fbp);
1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181

	/*
	 * If there are no useful entries left in the block, get rid of the
	 * block if we can.
	 */
	if (!freehdr.nused) {
		int error;

		error = xfs_dir2_shrink_inode(args, fdb, fbp);
		if (error == 0) {
			fbp = NULL;
			logfree = 0;
1182
		} else if (error != -ENOSPC || args->total != 0)
1183
			return error;
1184
		/*
1185 1186 1187
		 * It's possible to get ENOSPC if there is no
		 * space reservation.  In this case some one
		 * else will eventually get rid of this block.
1188 1189 1190 1191 1192
		 */
	}

	/* Log the free entry that changed, unless we got rid of it.  */
	if (logfree)
1193
		xfs_dir2_free_log_bests(args, fbp, findex, findex);
1194 1195 1196
	return 0;
}

Linus Torvalds's avatar
Linus Torvalds committed
1197 1198 1199 1200 1201 1202 1203 1204
/*
 * Remove an entry from a node directory.
 * This removes the leaf entry and the data entry,
 * and updates the free block if necessary.
 */
static int					/* error */
xfs_dir2_leafn_remove(
	xfs_da_args_t		*args,		/* operation arguments */
1205
	struct xfs_buf		*bp,		/* leaf buffer */
Linus Torvalds's avatar
Linus Torvalds committed
1206 1207 1208 1209
	int			index,		/* leaf entry index */
	xfs_da_state_blk_t	*dblk,		/* data block */
	int			*rval)		/* resulting block needs join */
{
1210
	xfs_dir2_data_hdr_t	*hdr;		/* data block header */
Linus Torvalds's avatar
Linus Torvalds committed
1211
	xfs_dir2_db_t		db;		/* data block number */
1212
	struct xfs_buf		*dbp;		/* data block buffer */
Linus Torvalds's avatar
Linus Torvalds committed
1213 1214 1215 1216 1217 1218 1219 1220 1221
	xfs_dir2_data_entry_t	*dep;		/* data block entry */
	xfs_inode_t		*dp;		/* incore directory inode */
	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
	int			longest;	/* longest data free entry */
	int			off;		/* data block entry offset */
	int			needlog;	/* need to log data header */
	int			needscan;	/* need to rescan data frees */
	xfs_trans_t		*tp;		/* transaction pointer */
1222
	struct xfs_dir2_data_free *bf;		/* bestfree table */
1223 1224
	struct xfs_dir3_icleaf_hdr leafhdr;
	struct xfs_dir2_leaf_entry *ents;
Linus Torvalds's avatar
Linus Torvalds committed
1225

1226 1227
	trace_xfs_dir2_leafn_remove(args, index);

Linus Torvalds's avatar
Linus Torvalds committed
1228 1229
	dp = args->dp;
	tp = args->trans;
1230
	leaf = bp->b_addr;
1231
	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
1232
	ents = dp->d_ops->leaf_ents_p(leaf);
1233

Linus Torvalds's avatar
Linus Torvalds committed
1234 1235 1236
	/*
	 * Point to the entry we're removing.
	 */
1237 1238
	lep = &ents[index];

Linus Torvalds's avatar
Linus Torvalds committed
1239 1240 1241
	/*
	 * Extract the data block and offset from the entry.
	 */
1242
	db = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address));
Linus Torvalds's avatar
Linus Torvalds committed
1243
	ASSERT(dblk->blkno == db);
1244
	off = xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address));
Linus Torvalds's avatar
Linus Torvalds committed
1245
	ASSERT(dblk->index == off);
1246

Linus Torvalds's avatar
Linus Torvalds committed
1247 1248 1249 1250
	/*
	 * Kill the leaf entry by marking it stale.
	 * Log the leaf block changes.
	 */
1251
	leafhdr.stale++;
1252
	dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
1253
	xfs_dir3_leaf_log_header(args, bp);
1254

1255
	lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
1256
	xfs_dir3_leaf_log_ents(args, bp, index, index);
1257

Linus Torvalds's avatar
Linus Torvalds committed
1258 1259 1260 1261 1262
	/*
	 * Make the data entry free.  Keep track of the longest freespace
	 * in the data block in case it changes.
	 */
	dbp = dblk->bp;
1263
	hdr = dbp->b_addr;
1264
	dep = (xfs_dir2_data_entry_t *)((char *)hdr + off);
1265
	bf = dp->d_ops->data_bestfree_p(hdr);
1266
	longest = be16_to_cpu(bf[0].length);
Linus Torvalds's avatar
Linus Torvalds committed
1267
	needlog = needscan = 0;
1268
	xfs_dir2_data_make_free(args, dbp, off,
1269
		dp->d_ops->data_entsize(dep->namelen), &needlog, &needscan);
Linus Torvalds's avatar
Linus Torvalds committed
1270 1271 1272 1273 1274
	/*
	 * Rescan the data block freespaces for bestfree.
	 * Log the data block header if needed.
	 */
	if (needscan)
1275
		xfs_dir2_data_freescan(dp, hdr, &needlog);
Linus Torvalds's avatar
Linus Torvalds committed
1276
	if (needlog)
1277
		xfs_dir2_data_log_header(args, dbp);
1278
	xfs_dir3_data_check(dp, dbp);
Linus Torvalds's avatar
Linus Torvalds committed
1279 1280 1281 1282
	/*
	 * If the longest data block freespace changes, need to update
	 * the corresponding freeblock entry.
	 */
1283
	if (longest < be16_to_cpu(bf[0].length)) {
Linus Torvalds's avatar
Linus Torvalds committed
1284
		int		error;		/* error return value */
1285
		struct xfs_buf	*fbp;		/* freeblock buffer */
Linus Torvalds's avatar
Linus Torvalds committed
1286 1287 1288 1289 1290 1291 1292 1293
		xfs_dir2_db_t	fdb;		/* freeblock block number */
		int		findex;		/* index in freeblock entries */
		xfs_dir2_free_t	*free;		/* freeblock structure */

		/*
		 * Convert the data block number to a free block,
		 * read in the free block.
		 */
1294
		fdb = dp->d_ops->db_to_fdb(args->geo, db);
1295 1296
		error = xfs_dir2_free_read(tp, dp,
					   xfs_dir2_db_to_da(args->geo, fdb),
1297
					   &fbp);
1298
		if (error)
Linus Torvalds's avatar
Linus Torvalds committed
1299
			return error;
1300
		free = fbp->b_addr;
1301 1302 1303
#ifdef DEBUG
	{
		struct xfs_dir3_icfree_hdr freehdr;
1304
		dp->d_ops->free_hdr_from_disk(&freehdr, free);
1305
		ASSERT(freehdr.firstdb == dp->d_ops->free_max_bests(args->geo) *
1306 1307
			(fdb - xfs_dir2_byte_to_db(args->geo,
						   XFS_DIR2_FREE_OFFSET)));
1308 1309
	}
#endif
Linus Torvalds's avatar
Linus Torvalds committed
1310 1311 1312
		/*
		 * Calculate which entry we need to fix.
		 */
1313
		findex = dp->d_ops->db_to_fdindex(args->geo, db);
1314
		longest = be16_to_cpu(bf[0].length);
Linus Torvalds's avatar
Linus Torvalds committed
1315 1316 1317 1318
		/*
		 * If the data block is now empty we can get rid of it
		 * (usually).
		 */
1319
		if (longest == args->geo->blksize -
1320
			       dp->d_ops->data_entry_offset) {
Linus Torvalds's avatar
Linus Torvalds committed
1321 1322 1323 1324 1325 1326
			/*
			 * Try to punch out the data block.
			 */
			error = xfs_dir2_shrink_inode(args, db, dbp);
			if (error == 0) {
				dblk->bp = NULL;
1327
				hdr = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
1328 1329 1330 1331 1332 1333
			}
			/*
			 * We can get ENOSPC if there's no space reservation.
			 * In this case just drop the buffer and some one else
			 * will eventually get rid of the empty block.
			 */
1334
			else if (!(error == -ENOSPC && args->total == 0))
Linus Torvalds's avatar
Linus Torvalds committed
1335 1336 1337 1338 1339 1340
				return error;
		}
		/*
		 * If we got rid of the data block, we can eliminate that entry
		 * in the free block.
		 */
1341
		error = xfs_dir3_data_block_free(args, hdr, free,
1342 1343 1344
						 fdb, findex, fbp, longest);
		if (error)
			return error;
Linus Torvalds's avatar
Linus Torvalds committed
1345
	}
1346

1347
	xfs_dir3_leaf_check(dp, bp);
Linus Torvalds's avatar
Linus Torvalds committed
1348
	/*
Malcolm Parsons's avatar
Malcolm Parsons committed
1349
	 * Return indication of whether this leaf block is empty enough
Linus Torvalds's avatar
Linus Torvalds committed
1350 1351
	 * to justify trying to join it with a neighbor.
	 */
1352
	*rval = (dp->d_ops->leaf_hdr_size +
1353
		 (uint)sizeof(ents[0]) * (leafhdr.count - leafhdr.stale)) <
1354
		args->geo->magicpct;
Linus Torvalds's avatar
Linus Torvalds committed
1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369
	return 0;
}

/*
 * Split the leaf entries in the old block into old and new blocks.
 */
int						/* error */
xfs_dir2_leafn_split(
	xfs_da_state_t		*state,		/* btree cursor */
	xfs_da_state_blk_t	*oldblk,	/* original block */
	xfs_da_state_blk_t	*newblk)	/* newly created block */
{
	xfs_da_args_t		*args;		/* operation arguments */
	xfs_dablk_t		blkno;		/* new leaf block number */
	int			error;		/* error return value */
1370
	struct xfs_inode	*dp;
Linus Torvalds's avatar
Linus Torvalds committed
1371 1372 1373 1374 1375

	/*
	 * Allocate space for a new leaf node.
	 */
	args = state->args;
1376
	dp = args->dp;
Linus Torvalds's avatar
Linus Torvalds committed
1377 1378 1379 1380 1381 1382 1383 1384
	ASSERT(oldblk->magic == XFS_DIR2_LEAFN_MAGIC);
	error = xfs_da_grow_inode(args, &blkno);
	if (error) {
		return error;
	}
	/*
	 * Initialize the new leaf block.
	 */
1385
	error = xfs_dir3_leaf_get_buf(args, xfs_dir2_da_to_db(args->geo, blkno),
1386 1387
				      &newblk->bp, XFS_DIR2_LEAFN_MAGIC);
	if (error)
Linus Torvalds's avatar
Linus Torvalds committed
1388
		return error;
1389

Linus Torvalds's avatar
Linus Torvalds committed
1390 1391 1392 1393 1394 1395 1396
	newblk->blkno = blkno;
	newblk->magic = XFS_DIR2_LEAFN_MAGIC;
	/*
	 * Rebalance the entries across the two leaves, link the new
	 * block into the leaves.
	 */
	xfs_dir2_leafn_rebalance(state, oldblk, newblk);
1397
	error = xfs_da3_blk_link(state, oldblk, newblk);
Linus Torvalds's avatar
Linus Torvalds committed
1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410
	if (error) {
		return error;
	}
	/*
	 * Insert the new entry in the correct block.
	 */
	if (state->inleaf)
		error = xfs_dir2_leafn_add(oldblk->bp, args, oldblk->index);
	else
		error = xfs_dir2_leafn_add(newblk->bp, args, newblk->index);
	/*
	 * Update last hashval in each block since we added the name.
	 */
1411 1412
	oldblk->hashval = xfs_dir2_leaf_lasthash(dp, oldblk->bp, NULL);
	newblk->hashval = xfs_dir2_leaf_lasthash(dp, newblk->bp, NULL);
1413 1414
	xfs_dir3_leaf_check(dp, oldblk->bp);
	xfs_dir3_leaf_check(dp, newblk->bp);
Linus Torvalds's avatar
Linus Torvalds committed
1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433
	return error;
}

/*
 * Check a leaf block and its neighbors to see if the block should be
 * collapsed into one or the other neighbor.  Always keep the block
 * with the smaller block number.
 * If the current block is over 50% full, don't try to join it, return 0.
 * If the block is empty, fill in the state structure and return 2.
 * If it can be collapsed, fill in the state structure and return 1.
 * If nothing can be done, return 0.
 */
int						/* error */
xfs_dir2_leafn_toosmall(
	xfs_da_state_t		*state,		/* btree cursor */
	int			*action)	/* resulting action to take */
{
	xfs_da_state_blk_t	*blk;		/* leaf block */
	xfs_dablk_t		blkno;		/* leaf block number */
1434
	struct xfs_buf		*bp;		/* leaf buffer */
Linus Torvalds's avatar
Linus Torvalds committed
1435 1436 1437 1438 1439 1440 1441
	int			bytes;		/* bytes in use */
	int			count;		/* leaf live entry count */
	int			error;		/* error return value */
	int			forward;	/* sibling block direction */
	int			i;		/* sibling counter */
	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
	int			rval;		/* result from path_shift */
1442 1443
	struct xfs_dir3_icleaf_hdr leafhdr;
	struct xfs_dir2_leaf_entry *ents;
1444
	struct xfs_inode	*dp = state->args->dp;
Linus Torvalds's avatar
Linus Torvalds committed
1445 1446 1447 1448 1449 1450 1451

	/*
	 * Check for the degenerate case of the block being over 50% full.
	 * If so, it's not worth even looking to see if we might be able
	 * to coalesce with a sibling.
	 */
	blk = &state->path.blk[state->path.active - 1];
1452
	leaf = blk->bp->b_addr;
1453
	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
1454 1455
	ents = dp->d_ops->leaf_ents_p(leaf);
	xfs_dir3_leaf_check(dp, blk->bp);
1456 1457

	count = leafhdr.count - leafhdr.stale;
1458
	bytes = dp->d_ops->leaf_hdr_size + count * sizeof(ents[0]);
1459
	if (bytes > (state->args->geo->blksize >> 1)) {
Linus Torvalds's avatar
Linus Torvalds committed
1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476
		/*
		 * Blk over 50%, don't try to join.
		 */
		*action = 0;
		return 0;
	}
	/*
	 * Check for the degenerate case of the block being empty.
	 * If the block is empty, we'll simply delete it, no need to
	 * coalesce it with a sibling block.  We choose (arbitrarily)
	 * to merge with the forward block unless it is NULL.
	 */
	if (count == 0) {
		/*
		 * Make altpath point to the block we want to keep and
		 * path point to the block we want to drop (this one).
		 */
1477
		forward = (leafhdr.forw != 0);
Linus Torvalds's avatar
Linus Torvalds committed
1478
		memcpy(&state->altpath, &state->path, sizeof(state->path));
1479
		error = xfs_da3_path_shift(state, &state->altpath, forward, 0,
Linus Torvalds's avatar
Linus Torvalds committed
1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492
			&rval);
		if (error)
			return error;
		*action = rval ? 2 : 0;
		return 0;
	}
	/*
	 * Examine each sibling block to see if we can coalesce with
	 * at least 25% free space to spare.  We need to figure out
	 * whether to merge with the forward or the backward block.
	 * We prefer coalescing with the lower numbered sibling so as
	 * to shrink a directory over time.
	 */
1493
	forward = leafhdr.forw < leafhdr.back;
Linus Torvalds's avatar
Linus Torvalds committed
1494
	for (i = 0, bp = NULL; i < 2; forward = !forward, i++) {
1495 1496 1497
		struct xfs_dir3_icleaf_hdr hdr2;

		blkno = forward ? leafhdr.forw : leafhdr.back;
Linus Torvalds's avatar
Linus Torvalds committed
1498 1499 1500 1501 1502
		if (blkno == 0)
			continue;
		/*
		 * Read the sibling leaf block.
		 */
1503
		error = xfs_dir3_leafn_read(state->args->trans, dp,
Dave Chinner's avatar
Dave Chinner committed
1504
					    blkno, -1, &bp);
1505
		if (error)
Linus Torvalds's avatar
Linus Torvalds committed
1506
			return error;
Dave Chinner's avatar
Dave Chinner committed
1507

Linus Torvalds's avatar
Linus Torvalds committed
1508 1509 1510
		/*
		 * Count bytes in the two blocks combined.
		 */
1511
		count = leafhdr.count - leafhdr.stale;
1512 1513
		bytes = state->args->geo->blksize -
			(state->args->geo->blksize >> 2);
1514

1515
		leaf = bp->b_addr;
1516
		dp->d_ops->leaf_hdr_from_disk(&hdr2, leaf);
1517
		ents = dp->d_ops->leaf_ents_p(leaf);
1518 1519 1520
		count += hdr2.count - hdr2.stale;
		bytes -= count * sizeof(ents[0]);

Linus Torvalds's avatar
Linus Torvalds committed
1521 1522 1523 1524 1525
		/*
		 * Fits with at least 25% to spare.
		 */
		if (bytes >= 0)
			break;
1526
		xfs_trans_brelse(state->args->trans, bp);
Linus Torvalds's avatar
Linus Torvalds committed
1527 1528 1529 1530 1531 1532 1533 1534
	}
	/*
	 * Didn't like either block, give up.
	 */
	if (i >= 2) {
		*action = 0;
		return 0;
	}
1535

Linus Torvalds's avatar
Linus Torvalds committed
1536 1537 1538 1539 1540 1541
	/*
	 * Make altpath point to the block we want to keep (the lower
	 * numbered block) and path point to the block we want to drop.
	 */
	memcpy(&state->altpath, &state->path, sizeof(state->path));
	if (blkno < blk->blkno)
1542
		error = xfs_da3_path_shift(state, &state->altpath, forward, 0,
Linus Torvalds's avatar
Linus Torvalds committed
1543 1544
			&rval);
	else
1545
		error = xfs_da3_path_shift(state, &state->path, forward, 0,
Linus Torvalds's avatar
Linus Torvalds committed
1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566
			&rval);
	if (error) {
		return error;
	}
	*action = rval ? 0 : 1;
	return 0;
}

/*
 * Move all the leaf entries from drop_blk to save_blk.
 * This is done as part of a join operation.
 */
void
xfs_dir2_leafn_unbalance(
	xfs_da_state_t		*state,		/* cursor */
	xfs_da_state_blk_t	*drop_blk,	/* dead block */
	xfs_da_state_blk_t	*save_blk)	/* surviving block */
{
	xfs_da_args_t		*args;		/* operation arguments */
	xfs_dir2_leaf_t		*drop_leaf;	/* dead leaf structure */
	xfs_dir2_leaf_t		*save_leaf;	/* surviving leaf structure */
1567 1568 1569 1570
	struct xfs_dir3_icleaf_hdr savehdr;
	struct xfs_dir3_icleaf_hdr drophdr;
	struct xfs_dir2_leaf_entry *sents;
	struct xfs_dir2_leaf_entry *dents;
1571
	struct xfs_inode	*dp = state->args->dp;
Linus Torvalds's avatar
Linus Torvalds committed
1572 1573 1574 1575

	args = state->args;
	ASSERT(drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
	ASSERT(save_blk->magic == XFS_DIR2_LEAFN_MAGIC);
1576 1577
	drop_leaf = drop_blk->bp->b_addr;
	save_leaf = save_blk->bp->b_addr;
1578

1579 1580 1581 1582
	dp->d_ops->leaf_hdr_from_disk(&savehdr, save_leaf);
	dp->d_ops->leaf_hdr_from_disk(&drophdr, drop_leaf);
	sents = dp->d_ops->leaf_ents_p(save_leaf);
	dents = dp->d_ops->leaf_ents_p(drop_leaf);
1583

Linus Torvalds's avatar
Linus Torvalds committed
1584 1585 1586 1587
	/*
	 * If there are any stale leaf entries, take this opportunity
	 * to purge them.
	 */
1588 1589 1590 1591 1592
	if (drophdr.stale)
		xfs_dir3_leaf_compact(args, &drophdr, drop_blk->bp);
	if (savehdr.stale)
		xfs_dir3_leaf_compact(args, &savehdr, save_blk->bp);

Linus Torvalds's avatar
Linus Torvalds committed
1593 1594 1595
	/*
	 * Move the entries from drop to the appropriate end of save.
	 */
1596
	drop_blk->hashval = be32_to_cpu(dents[drophdr.count - 1].hashval);
1597
	if (xfs_dir2_leafn_order(dp, save_blk->bp, drop_blk->bp))
1598 1599 1600
		xfs_dir3_leafn_moveents(args, drop_blk->bp, &drophdr, dents, 0,
					save_blk->bp, &savehdr, sents, 0,
					drophdr.count);
Linus Torvalds's avatar
Linus Torvalds committed
1601
	else
1602 1603 1604 1605 1606 1607
		xfs_dir3_leafn_moveents(args, drop_blk->bp, &drophdr, dents, 0,
					save_blk->bp, &savehdr, sents,
					savehdr.count, drophdr.count);
	save_blk->hashval = be32_to_cpu(sents[savehdr.count - 1].hashval);

	/* log the changes made when moving the entries */
1608 1609
	dp->d_ops->leaf_hdr_to_disk(save_leaf, &savehdr);
	dp->d_ops->leaf_hdr_to_disk(drop_leaf, &drophdr);
1610 1611
	xfs_dir3_leaf_log_header(args, save_blk->bp);
	xfs_dir3_leaf_log_header(args, drop_blk->bp);
1612

1613 1614
	xfs_dir3_leaf_check(dp, save_blk->bp);
	xfs_dir3_leaf_check(dp, drop_blk->bp);
Linus Torvalds's avatar
Linus Torvalds committed
1615 1616
}

1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643
/*
 * Add a new data block to the directory at the free space index that the caller
 * has specified.
 */
static int
xfs_dir2_node_add_datablk(
	struct xfs_da_args	*args,
	struct xfs_da_state_blk	*fblk,
	xfs_dir2_db_t		*dbno,
	struct xfs_buf		**dbpp,
	struct xfs_buf		**fbpp,
	int			*findex)
{
	struct xfs_inode	*dp = args->dp;
	struct xfs_trans	*tp = args->trans;
	struct xfs_mount	*mp = dp->i_mount;
	struct xfs_dir3_icfree_hdr freehdr;
	struct xfs_dir2_data_free *bf;
	struct xfs_dir2_data_hdr *hdr;
	struct xfs_dir2_free	*free = NULL;
	xfs_dir2_db_t		fbno;
	struct xfs_buf		*fbp;
	struct xfs_buf		*dbp;
	__be16			*bests = NULL;
	int			error;

	/* Not allowed to allocate, return failure. */
1644
	if (args->total == 0)
1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739
		return -ENOSPC;

	/* Allocate and initialize the new data block.  */
	error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE, dbno);
	if (error)
		return error;
	error = xfs_dir3_data_init(args, *dbno, &dbp);
	if (error)
		return error;

	/*
	 * Get the freespace block corresponding to the data block
	 * that was just allocated.
	 */
	fbno = dp->d_ops->db_to_fdb(args->geo, *dbno);
	error = xfs_dir2_free_try_read(tp, dp,
			       xfs_dir2_db_to_da(args->geo, fbno), &fbp);
	if (error)
		return error;

	/*
	 * If there wasn't a freespace block, the read will
	 * return a NULL fbp.  Allocate and initialize a new one.
	 */
	if (!fbp) {
		error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE, &fbno);
		if (error)
			return error;

		if (dp->d_ops->db_to_fdb(args->geo, *dbno) != fbno) {
			xfs_alert(mp,
"%s: dir ino %llu needed freesp block %lld for data block %lld, got %lld",
				__func__, (unsigned long long)dp->i_ino,
				(long long)dp->d_ops->db_to_fdb(args->geo, *dbno),
				(long long)*dbno, (long long)fbno);
			if (fblk) {
				xfs_alert(mp,
			" fblk "PTR_FMT" blkno %llu index %d magic 0x%x",
					fblk, (unsigned long long)fblk->blkno,
					fblk->index, fblk->magic);
			} else {
				xfs_alert(mp, " ... fblk is NULL");
			}
			XFS_ERROR_REPORT(__func__, XFS_ERRLEVEL_LOW, mp);
			return -EFSCORRUPTED;
		}

		/* Get a buffer for the new block. */
		error = xfs_dir3_free_get_buf(args, fbno, &fbp);
		if (error)
			return error;
		free = fbp->b_addr;
		bests = dp->d_ops->free_bests_p(free);
		dp->d_ops->free_hdr_from_disk(&freehdr, free);

		/* Remember the first slot as our empty slot. */
		freehdr.firstdb = (fbno - xfs_dir2_byte_to_db(args->geo,
							XFS_DIR2_FREE_OFFSET)) *
				dp->d_ops->free_max_bests(args->geo);
	} else {
		free = fbp->b_addr;
		bests = dp->d_ops->free_bests_p(free);
		dp->d_ops->free_hdr_from_disk(&freehdr, free);
	}

	/* Set the freespace block index from the data block number. */
	*findex = dp->d_ops->db_to_fdindex(args->geo, *dbno);

	/* Extend the freespace table if the new data block is off the end. */
	if (*findex >= freehdr.nvalid) {
		ASSERT(*findex < dp->d_ops->free_max_bests(args->geo));
		freehdr.nvalid = *findex + 1;
		bests[*findex] = cpu_to_be16(NULLDATAOFF);
	}

	/*
	 * If this entry was for an empty data block (this should always be
	 * true) then update the header.
	 */
	if (bests[*findex] == cpu_to_be16(NULLDATAOFF)) {
		freehdr.nused++;
		dp->d_ops->free_hdr_to_disk(fbp->b_addr, &freehdr);
		xfs_dir2_free_log_header(args, fbp);
	}

	/* Update the freespace value for the new block in the table. */
	hdr = dbp->b_addr;
	bf = dp->d_ops->data_bestfree_p(hdr);
	bests[*findex] = bf[0].length;

	*dbpp = dbp;
	*fbpp = fbp;
	return 0;
}

1740 1741 1742 1743 1744 1745 1746 1747
static int
xfs_dir2_node_find_freeblk(
	struct xfs_da_args	*args,
	struct xfs_da_state_blk	*fblk,
	xfs_dir2_db_t		*dbnop,
	struct xfs_buf		**fbpp,
	int			*findexp,
	int			length)
Linus Torvalds's avatar
Linus Torvalds committed
1748
{
1749
	struct xfs_dir3_icfree_hdr freehdr;
1750 1751 1752 1753
	struct xfs_dir2_free	*free = NULL;
	struct xfs_inode	*dp = args->dp;
	struct xfs_trans	*tp = args->trans;
	struct xfs_buf		*fbp = NULL;
1754
	xfs_dir2_db_t		firstfbno;
1755 1756 1757
	xfs_dir2_db_t		lastfbno;
	xfs_dir2_db_t		ifbno = -1;
	xfs_dir2_db_t		dbno = -1;
1758
	xfs_dir2_db_t		fbno;
1759
	xfs_fileoff_t		fo;
1760 1761
	__be16			*bests = NULL;
	int			findex = 0;
1762
	int			error;
Linus Torvalds's avatar
Linus Torvalds committed
1763 1764 1765 1766 1767 1768 1769 1770

	/*
	 * If we came in with a freespace block that means that lookup
	 * found an entry with our hash value.  This is the freespace
	 * block for that data entry.
	 */
	if (fblk) {
		fbp = fblk->bp;
1771
		free = fbp->b_addr;
Linus Torvalds's avatar
Linus Torvalds committed
1772 1773
		findex = fblk->index;
		if (findex >= 0) {
1774 1775 1776 1777
			/* caller already found the freespace for us. */
			bests = dp->d_ops->free_bests_p(free);
			dp->d_ops->free_hdr_from_disk(&freehdr, free);

1778 1779 1780 1781
			ASSERT(findex < freehdr.nvalid);
			ASSERT(be16_to_cpu(bests[findex]) != NULLDATAOFF);
			ASSERT(be16_to_cpu(bests[findex]) >= length);
			dbno = freehdr.firstdb + findex;
1782
			goto found_block;
Linus Torvalds's avatar
Linus Torvalds committed
1783
		}
1784

1785
		/*
1786 1787
		 * The data block looked at didn't have enough room.
		 * We'll start at the beginning of the freespace entries.
1788
		 */
1789
		ifbno = fblk->blkno;
1790 1791 1792
		xfs_trans_brelse(tp, fbp);
		fbp = NULL;
		fblk->bp = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
1793
	}
1794

Linus Torvalds's avatar
Linus Torvalds committed
1795
	/*
1796
	 * If we don't have a data block yet, we're going to scan the freespace
1797
	 * data for a data block with enough free space in it.
Linus Torvalds's avatar
Linus Torvalds committed
1798
	 */
1799 1800 1801 1802
	error = xfs_bmap_last_offset(dp, &fo, XFS_DATA_FORK);
	if (error)
		return error;
	lastfbno = xfs_dir2_da_to_db(args->geo, (xfs_dablk_t)fo);
1803
	firstfbno = xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET);
1804

1805
	for (fbno = lastfbno - 1; fbno >= firstfbno; fbno--) {
1806 1807 1808 1809
		/* If it's ifbno we already looked at it. */
		if (fbno == ifbno)
			continue;

Linus Torvalds's avatar
Linus Torvalds committed
1810
		/*
1811 1812 1813
		 * Read the block.  There can be holes in the freespace blocks,
		 * so this might not succeed.  This should be really rare, so
		 * there's no reason to avoid it.
Linus Torvalds's avatar
Linus Torvalds committed
1814
		 */
1815 1816 1817 1818 1819 1820 1821 1822 1823
		error = xfs_dir2_free_try_read(tp, dp,
				xfs_dir2_db_to_da(args->geo, fbno),
				&fbp);
		if (error)
			return error;
		if (!fbp)
			continue;

		free = fbp->b_addr;
1824
		bests = dp->d_ops->free_bests_p(free);
1825
		dp->d_ops->free_hdr_from_disk(&freehdr, free);
1826 1827

		/* Scan the free entry array for a large enough free space. */
1828
		for (findex = freehdr.nvalid - 1; findex >= 0; findex--) {
1829 1830 1831 1832
			if (be16_to_cpu(bests[findex]) != NULLDATAOFF &&
			    be16_to_cpu(bests[findex]) >= length) {
				dbno = freehdr.firstdb + findex;
				goto found_block;
Linus Torvalds's avatar
Linus Torvalds committed
1833 1834
			}
		}
1835 1836 1837

		/* Didn't find free space, go on to next free block */
		xfs_trans_brelse(tp, fbp);
Linus Torvalds's avatar
Linus Torvalds committed
1838
	}
1839

1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892
found_block:
	*dbnop = dbno;
	*fbpp = fbp;
	*findexp = findex;
	return 0;
}


/*
 * Add the data entry for a node-format directory name addition.
 * The leaf entry is added in xfs_dir2_leafn_add.
 * We may enter with a freespace block that the lookup found.
 */
static int
xfs_dir2_node_addname_int(
	struct xfs_da_args	*args,		/* operation arguments */
	struct xfs_da_state_blk	*fblk)		/* optional freespace block */
{
	struct xfs_dir2_data_unused *dup;	/* data unused entry pointer */
	struct xfs_dir2_data_entry *dep;	/* data entry pointer */
	struct xfs_dir2_data_hdr *hdr;		/* data block header */
	struct xfs_dir2_data_free *bf;
	struct xfs_dir2_free	*free = NULL;	/* freespace block structure */
	struct xfs_trans	*tp = args->trans;
	struct xfs_inode	*dp = args->dp;
	struct xfs_buf		*dbp;		/* data block buffer */
	struct xfs_buf		*fbp;		/* freespace buffer */
	xfs_dir2_data_aoff_t	aoff;
	xfs_dir2_db_t		dbno;		/* data block number */
	int			error;		/* error return value */
	int			findex;		/* freespace entry index */
	int			length;		/* length of the new entry */
	int			logfree = 0;	/* need to log free entry */
	int			needlog = 0;	/* need to log data header */
	int			needscan = 0;	/* need to rescan data frees */
	__be16			*tagp;		/* data entry tag pointer */
	__be16			*bests;

	length = dp->d_ops->data_entsize(args->namelen);
	error = xfs_dir2_node_find_freeblk(args, fblk, &dbno, &fbp, &findex,
					   length);
	if (error)
		return error;

	/*
	 * Now we know if we must allocate blocks, so if we are checking whether
	 * we can insert without allocation then we can return now.
	 */
	if (args->op_flags & XFS_DA_OP_JUSTCHECK) {
		if (dbno == -1)
			return -ENOSPC;
		return 0;
	}
1893

Linus Torvalds's avatar
Linus Torvalds committed
1894 1895 1896 1897
	/*
	 * If we don't have a data block, we need to allocate one and make
	 * the freespace entries refer to it.
	 */
1898 1899
	if (dbno == -1) {
		/* we're going to have to log the free block index later */
Linus Torvalds's avatar
Linus Torvalds committed
1900
		logfree = 1;
1901 1902
		error = xfs_dir2_node_add_datablk(args, fblk, &dbno, &dbp, &fbp,
						  &findex);
1903 1904
	} else {
		/* Read the data block in. */
1905 1906
		error = xfs_dir3_data_read(tp, dp,
					   xfs_dir2_db_to_da(args->geo, dbno),
1907
					   -1, &dbp);
Linus Torvalds's avatar
Linus Torvalds committed
1908
	}
1909 1910
	if (error)
		return error;
1911 1912 1913 1914

	/* setup for data block up now */
	hdr = dbp->b_addr;
	bf = dp->d_ops->data_bestfree_p(hdr);
1915
	ASSERT(be16_to_cpu(bf[0].length) >= length);
1916 1917

	/* Point to the existing unused space. */
Linus Torvalds's avatar
Linus Torvalds committed
1918
	dup = (xfs_dir2_data_unused_t *)
1919
	      ((char *)hdr + be16_to_cpu(bf[0].offset));
1920 1921

	/* Mark the first part of the unused space, inuse for us. */
1922 1923 1924 1925 1926 1927 1928
	aoff = (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr);
	error = xfs_dir2_data_use_free(args, dbp, dup, aoff, length,
			&needlog, &needscan);
	if (error) {
		xfs_trans_brelse(tp, dbp);
		return error;
	}
1929 1930

	/* Fill in the new entry and log it. */
Linus Torvalds's avatar
Linus Torvalds committed
1931
	dep = (xfs_dir2_data_entry_t *)dup;
1932
	dep->inumber = cpu_to_be64(args->inumber);
Linus Torvalds's avatar
Linus Torvalds committed
1933 1934
	dep->namelen = args->namelen;
	memcpy(dep->name, args->name, dep->namelen);
1935 1936
	dp->d_ops->data_put_ftype(dep, args->filetype);
	tagp = dp->d_ops->data_entry_tag_p(dep);
1937
	*tagp = cpu_to_be16((char *)dep - (char *)hdr);
1938
	xfs_dir2_data_log_entry(args, dbp, dep);
1939 1940

	/* Rescan the freespace and log the data block if needed. */
Linus Torvalds's avatar
Linus Torvalds committed
1941
	if (needscan)
1942
		xfs_dir2_data_freescan(dp, hdr, &needlog);
Linus Torvalds's avatar
Linus Torvalds committed
1943
	if (needlog)
1944
		xfs_dir2_data_log_header(args, dbp);
1945 1946

	/* If the freespace block entry is now wrong, update it. */
1947
	free = fbp->b_addr;
1948 1949
	bests = dp->d_ops->free_bests_p(free);
	if (bests[findex] != bf[0].length) {
1950
		bests[findex] = bf[0].length;
Linus Torvalds's avatar
Linus Torvalds committed
1951 1952
		logfree = 1;
	}
1953 1954

	/* Log the freespace entry if needed. */
Linus Torvalds's avatar
Linus Torvalds committed
1955
	if (logfree)
1956
		xfs_dir2_free_log_bests(args, fbp, findex, findex);
1957 1958

	/* Return the data block and offset in args. */
Linus Torvalds's avatar
Linus Torvalds committed
1959
	args->blkno = (xfs_dablk_t)dbno;
1960
	args->index = be16_to_cpu(*tagp);
Linus Torvalds's avatar
Linus Torvalds committed
1961 1962 1963
	return 0;
}

1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032
/*
 * Top-level node form directory addname routine.
 */
int						/* error */
xfs_dir2_node_addname(
	xfs_da_args_t		*args)		/* operation arguments */
{
	xfs_da_state_blk_t	*blk;		/* leaf block for insert */
	int			error;		/* error return value */
	int			rval;		/* sub-return value */
	xfs_da_state_t		*state;		/* btree cursor */

	trace_xfs_dir2_node_addname(args);

	/*
	 * Allocate and initialize the state (btree cursor).
	 */
	state = xfs_da_state_alloc();
	state->args = args;
	state->mp = args->dp->i_mount;
	/*
	 * Look up the name.  We're not supposed to find it, but
	 * this gives us the insertion point.
	 */
	error = xfs_da3_node_lookup_int(state, &rval);
	if (error)
		rval = error;
	if (rval != -ENOENT) {
		goto done;
	}
	/*
	 * Add the data entry to a data block.
	 * Extravalid is set to a freeblock found by lookup.
	 */
	rval = xfs_dir2_node_addname_int(args,
		state->extravalid ? &state->extrablk : NULL);
	if (rval) {
		goto done;
	}
	blk = &state->path.blk[state->path.active - 1];
	ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
	/*
	 * Add the new leaf entry.
	 */
	rval = xfs_dir2_leafn_add(blk->bp, args, blk->index);
	if (rval == 0) {
		/*
		 * It worked, fix the hash values up the btree.
		 */
		if (!(args->op_flags & XFS_DA_OP_JUSTCHECK))
			xfs_da3_fixhashpath(state, &state->path);
	} else {
		/*
		 * It didn't work, we need to split the leaf block.
		 */
		if (args->total == 0) {
			ASSERT(rval == -ENOSPC);
			goto done;
		}
		/*
		 * Split the leaf block and insert the new entry.
		 */
		rval = xfs_da3_split(state);
	}
done:
	xfs_da_state_free(state);
	return rval;
}

Linus Torvalds's avatar
Linus Torvalds committed
2033 2034
/*
 * Lookup an entry in a node-format directory.
2035
 * All the real work happens in xfs_da3_node_lookup_int.
Linus Torvalds's avatar
Linus Torvalds committed
2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046
 * The only real output is the inode number of the entry.
 */
int						/* error */
xfs_dir2_node_lookup(
	xfs_da_args_t	*args)			/* operation arguments */
{
	int		error;			/* error return value */
	int		i;			/* btree level */
	int		rval;			/* operation return value */
	xfs_da_state_t	*state;			/* btree cursor */

2047 2048
	trace_xfs_dir2_node_lookup(args);

Linus Torvalds's avatar
Linus Torvalds committed
2049 2050 2051 2052 2053 2054 2055 2056 2057
	/*
	 * Allocate and initialize the btree cursor.
	 */
	state = xfs_da_state_alloc();
	state->args = args;
	state->mp = args->dp->i_mount;
	/*
	 * Fill in the path to the entry in the cursor.
	 */
2058
	error = xfs_da3_node_lookup_int(state, &rval);
Linus Torvalds's avatar
Linus Torvalds committed
2059 2060
	if (error)
		rval = error;
2061 2062
	else if (rval == -ENOENT && args->cmpresult == XFS_CMP_CASE) {
		/* If a CI match, dup the actual name and return -EEXIST */
2063 2064
		xfs_dir2_data_entry_t	*dep;

2065 2066 2067
		dep = (xfs_dir2_data_entry_t *)
			((char *)state->extrablk.bp->b_addr +
						 state->extrablk.index);
2068 2069
		rval = xfs_dir_cilookup_result(args, dep->name, dep->namelen);
	}
Linus Torvalds's avatar
Linus Torvalds committed
2070 2071 2072 2073
	/*
	 * Release the btree blocks and leaf block.
	 */
	for (i = 0; i < state->path.active; i++) {
2074
		xfs_trans_brelse(args->trans, state->path.blk[i].bp);
Linus Torvalds's avatar
Linus Torvalds committed
2075 2076 2077 2078 2079 2080
		state->path.blk[i].bp = NULL;
	}
	/*
	 * Release the data block if we have it.
	 */
	if (state->extravalid && state->extrablk.bp) {
2081
		xfs_trans_brelse(args->trans, state->extrablk.bp);
Linus Torvalds's avatar
Linus Torvalds committed
2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092
		state->extrablk.bp = NULL;
	}
	xfs_da_state_free(state);
	return rval;
}

/*
 * Remove an entry from a node-format directory.
 */
int						/* error */
xfs_dir2_node_removename(
2093
	struct xfs_da_args	*args)		/* operation arguments */
Linus Torvalds's avatar
Linus Torvalds committed
2094
{
2095
	struct xfs_da_state_blk	*blk;		/* leaf block */
Linus Torvalds's avatar
Linus Torvalds committed
2096 2097
	int			error;		/* error return value */
	int			rval;		/* operation return value */
2098
	struct xfs_da_state	*state;		/* btree cursor */
Linus Torvalds's avatar
Linus Torvalds committed
2099

2100 2101
	trace_xfs_dir2_node_removename(args);

Linus Torvalds's avatar
Linus Torvalds committed
2102 2103 2104 2105 2106 2107
	/*
	 * Allocate and initialize the btree cursor.
	 */
	state = xfs_da_state_alloc();
	state->args = args;
	state->mp = args->dp->i_mount;
2108 2109

	/* Look up the entry we're deleting, set up the cursor. */
2110
	error = xfs_da3_node_lookup_int(state, &rval);
2111
	if (error)
2112 2113 2114
		goto out_free;

	/* Didn't find it, upper layer screwed up. */
2115
	if (rval != -EEXIST) {
2116 2117
		error = rval;
		goto out_free;
Linus Torvalds's avatar
Linus Torvalds committed
2118
	}
2119

Linus Torvalds's avatar
Linus Torvalds committed
2120 2121 2122 2123 2124 2125 2126 2127 2128
	blk = &state->path.blk[state->path.active - 1];
	ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
	ASSERT(state->extravalid);
	/*
	 * Remove the leaf and data entries.
	 * Extrablk refers to the data block.
	 */
	error = xfs_dir2_leafn_remove(args, blk->bp, blk->index,
		&state->extrablk, &rval);
2129
	if (error)
2130
		goto out_free;
Linus Torvalds's avatar
Linus Torvalds committed
2131 2132 2133
	/*
	 * Fix the hash values up the btree.
	 */
2134
	xfs_da3_fixhashpath(state, &state->path);
Linus Torvalds's avatar
Linus Torvalds committed
2135 2136 2137 2138
	/*
	 * If we need to join leaf blocks, do it.
	 */
	if (rval && state->path.active > 1)
2139
		error = xfs_da3_join(state);
Linus Torvalds's avatar
Linus Torvalds committed
2140 2141 2142 2143 2144
	/*
	 * If no errors so far, try conversion to leaf format.
	 */
	if (!error)
		error = xfs_dir2_node_to_leaf(state);
2145
out_free:
Linus Torvalds's avatar
Linus Torvalds committed
2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157
	xfs_da_state_free(state);
	return error;
}

/*
 * Replace an entry's inode number in a node-format directory.
 */
int						/* error */
xfs_dir2_node_replace(
	xfs_da_args_t		*args)		/* operation arguments */
{
	xfs_da_state_blk_t	*blk;		/* leaf block */
2158
	xfs_dir2_data_hdr_t	*hdr;		/* data block header */
Linus Torvalds's avatar
Linus Torvalds committed
2159 2160 2161 2162
	xfs_dir2_data_entry_t	*dep;		/* data entry changed */
	int			error;		/* error return value */
	int			i;		/* btree level */
	xfs_ino_t		inum;		/* new inode number */
2163
	int			ftype;		/* new file type */
Linus Torvalds's avatar
Linus Torvalds committed
2164 2165 2166 2167 2168
	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry being changed */
	int			rval;		/* internal return value */
	xfs_da_state_t		*state;		/* btree cursor */

2169 2170
	trace_xfs_dir2_node_replace(args);

Linus Torvalds's avatar
Linus Torvalds committed
2171 2172 2173 2174 2175 2176
	/*
	 * Allocate and initialize the btree cursor.
	 */
	state = xfs_da_state_alloc();
	state->args = args;
	state->mp = args->dp->i_mount;
2177 2178 2179 2180 2181

	/*
	 * We have to save new inode number and ftype since
	 * xfs_da3_node_lookup_int() is going to overwrite them
	 */
Linus Torvalds's avatar
Linus Torvalds committed
2182
	inum = args->inumber;
2183 2184
	ftype = args->filetype;

Linus Torvalds's avatar
Linus Torvalds committed
2185 2186 2187
	/*
	 * Lookup the entry to change in the btree.
	 */
2188
	error = xfs_da3_node_lookup_int(state, &rval);
Linus Torvalds's avatar
Linus Torvalds committed
2189 2190 2191 2192 2193 2194 2195
	if (error) {
		rval = error;
	}
	/*
	 * It should be found, since the vnodeops layer has looked it up
	 * and locked it.  But paranoia is good.
	 */
2196
	if (rval == -EEXIST) {
2197
		struct xfs_dir2_leaf_entry *ents;
Linus Torvalds's avatar
Linus Torvalds committed
2198 2199 2200 2201 2202
		/*
		 * Find the leaf entry.
		 */
		blk = &state->path.blk[state->path.active - 1];
		ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
2203
		leaf = blk->bp->b_addr;
2204
		ents = args->dp->d_ops->leaf_ents_p(leaf);
2205
		lep = &ents[blk->index];
Linus Torvalds's avatar
Linus Torvalds committed
2206 2207 2208 2209
		ASSERT(state->extravalid);
		/*
		 * Point to the data entry.
		 */
2210
		hdr = state->extrablk.bp->b_addr;
2211 2212
		ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
		       hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC));
Linus Torvalds's avatar
Linus Torvalds committed
2213
		dep = (xfs_dir2_data_entry_t *)
2214
		      ((char *)hdr +
2215 2216
		       xfs_dir2_dataptr_to_off(args->geo,
					       be32_to_cpu(lep->address)));
2217
		ASSERT(inum != be64_to_cpu(dep->inumber));
Linus Torvalds's avatar
Linus Torvalds committed
2218 2219 2220
		/*
		 * Fill in the new inode number and log the entry.
		 */
2221
		dep->inumber = cpu_to_be64(inum);
2222
		args->dp->d_ops->data_put_ftype(dep, ftype);
2223
		xfs_dir2_data_log_entry(args, state->extrablk.bp, dep);
Linus Torvalds's avatar
Linus Torvalds committed
2224 2225 2226 2227 2228 2229
		rval = 0;
	}
	/*
	 * Didn't find it, and we're holding a data block.  Drop it.
	 */
	else if (state->extravalid) {
2230
		xfs_trans_brelse(args->trans, state->extrablk.bp);
Linus Torvalds's avatar
Linus Torvalds committed
2231 2232 2233 2234 2235 2236
		state->extrablk.bp = NULL;
	}
	/*
	 * Release all the buffers in the cursor.
	 */
	for (i = 0; i < state->path.active; i++) {
2237
		xfs_trans_brelse(args->trans, state->path.blk[i].bp);
Linus Torvalds's avatar
Linus Torvalds committed
2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253
		state->path.blk[i].bp = NULL;
	}
	xfs_da_state_free(state);
	return rval;
}

/*
 * Trim off a trailing empty freespace block.
 * Return (in rvalp) 1 if we did it, 0 if not.
 */
int						/* error */
xfs_dir2_node_trim_free(
	xfs_da_args_t		*args,		/* operation arguments */
	xfs_fileoff_t		fo,		/* free block number */
	int			*rvalp)		/* out: did something */
{
2254
	struct xfs_buf		*bp;		/* freespace buffer */
Linus Torvalds's avatar
Linus Torvalds committed
2255 2256 2257 2258
	xfs_inode_t		*dp;		/* incore directory inode */
	int			error;		/* error return code */
	xfs_dir2_free_t		*free;		/* freespace structure */
	xfs_trans_t		*tp;		/* transaction pointer */
2259
	struct xfs_dir3_icfree_hdr freehdr;
Linus Torvalds's avatar
Linus Torvalds committed
2260 2261 2262

	dp = args->dp;
	tp = args->trans;
2263 2264 2265

	*rvalp = 0;

Linus Torvalds's avatar
Linus Torvalds committed
2266 2267 2268
	/*
	 * Read the freespace block.
	 */
2269
	error = xfs_dir2_free_try_read(tp, dp, fo, &bp);
2270
	if (error)
Linus Torvalds's avatar
Linus Torvalds committed
2271 2272 2273 2274 2275
		return error;
	/*
	 * There can be holes in freespace.  If fo is a hole, there's
	 * nothing to do.
	 */
2276
	if (!bp)
Linus Torvalds's avatar
Linus Torvalds committed
2277
		return 0;
2278
	free = bp->b_addr;
2279
	dp->d_ops->free_hdr_from_disk(&freehdr, free);
2280

Linus Torvalds's avatar
Linus Torvalds committed
2281 2282 2283
	/*
	 * If there are used entries, there's nothing to do.
	 */
2284
	if (freehdr.nused > 0) {
2285
		xfs_trans_brelse(tp, bp);
Linus Torvalds's avatar
Linus Torvalds committed
2286 2287 2288 2289 2290
		return 0;
	}
	/*
	 * Blow the block away.
	 */
2291 2292 2293
	error = xfs_dir2_shrink_inode(args,
			xfs_dir2_da_to_db(args->geo, (xfs_dablk_t)fo), bp);
	if (error) {
Linus Torvalds's avatar
Linus Torvalds committed
2294 2295 2296 2297 2298
		/*
		 * Can't fail with ENOSPC since that only happens with no
		 * space reservation, when breaking up an extent into two
		 * pieces.  This is the last block of an extent.
		 */
2299
		ASSERT(error != -ENOSPC);
2300
		xfs_trans_brelse(tp, bp);
Linus Torvalds's avatar
Linus Torvalds committed
2301 2302 2303 2304 2305 2306 2307 2308
		return error;
	}
	/*
	 * Return that we succeeded.
	 */
	*rvalp = 1;
	return 0;
}