xfs_dir2_data.c 25.9 KB
Newer Older
L
Linus Torvalds 已提交
1
/*
2 3
 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
 * All Rights Reserved.
L
Linus Torvalds 已提交
4
 *
5 6
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
L
Linus Torvalds 已提交
7 8
 * published by the Free Software Foundation.
 *
9 10 11 12
 * This program is distributed in the hope that it would be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
L
Linus Torvalds 已提交
13
 *
14 15 16
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write the Free Software Foundation,
 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
L
Linus Torvalds 已提交
17 18
 */
#include "xfs.h"
19
#include "xfs_fs.h"
L
Linus Torvalds 已提交
20 21 22 23
#include "xfs_types.h"
#include "xfs_log.h"
#include "xfs_trans.h"
#include "xfs_sb.h"
24
#include "xfs_ag.h"
L
Linus Torvalds 已提交
25
#include "xfs_mount.h"
26
#include "xfs_da_btree.h"
L
Linus Torvalds 已提交
27 28 29
#include "xfs_bmap_btree.h"
#include "xfs_dinode.h"
#include "xfs_inode.h"
C
Christoph Hellwig 已提交
30 31
#include "xfs_dir2_format.h"
#include "xfs_dir2_priv.h"
L
Linus Torvalds 已提交
32 33
#include "xfs_error.h"

34 35 36
STATIC xfs_dir2_data_free_t *
xfs_dir2_data_freefind(xfs_dir2_data_hdr_t *hdr, xfs_dir2_data_unused_t *dup);

L
Linus Torvalds 已提交
37 38 39
/*
 * Check the consistency of the data block.
 * The input can also be a block-format directory.
40
 * Return 0 is the buffer is good, otherwise an error.
L
Linus Torvalds 已提交
41
 */
42 43
int
__xfs_dir2_data_check(
44 45
	struct xfs_inode	*dp,		/* incore inode pointer */
	struct xfs_buf		*bp)		/* data block's buffer */
L
Linus Torvalds 已提交
46 47 48 49 50
{
	xfs_dir2_dataptr_t	addr;		/* addr for leaf lookup */
	xfs_dir2_data_free_t	*bf;		/* bestfree table */
	xfs_dir2_block_tail_t	*btp=NULL;	/* block tail */
	int			count;		/* count of entries found */
51
	xfs_dir2_data_hdr_t	*hdr;		/* data block header */
L
Linus Torvalds 已提交
52 53 54 55 56 57 58 59 60 61 62 63
	xfs_dir2_data_entry_t	*dep;		/* data entry */
	xfs_dir2_data_free_t	*dfp;		/* bestfree entry */
	xfs_dir2_data_unused_t	*dup;		/* unused entry */
	char			*endp;		/* end of useful data */
	int			freeseen;	/* mask of bestfrees seen */
	xfs_dahash_t		hash;		/* hash of current name */
	int			i;		/* leaf index */
	int			lastfree;	/* last entry was unused */
	xfs_dir2_leaf_entry_t	*lep=NULL;	/* block leaf entries */
	xfs_mount_t		*mp;		/* filesystem mount point */
	char			*p;		/* current data position */
	int			stale;		/* count of stale leaves */
64
	struct xfs_name		name;
L
Linus Torvalds 已提交
65

66
	mp = bp->b_target->bt_mount;
67
	hdr = bp->b_addr;
68
	bf = hdr->bestfree;
69
	p = (char *)(hdr + 1);
70

71 72
	switch (hdr->magic) {
	case cpu_to_be32(XFS_DIR2_BLOCK_MAGIC):
73
		btp = xfs_dir2_block_tail_p(mp, hdr);
74
		lep = xfs_dir2_block_leaf_p(btp);
L
Linus Torvalds 已提交
75
		endp = (char *)lep;
76 77
		break;
	case cpu_to_be32(XFS_DIR2_DATA_MAGIC):
78
		endp = (char *)hdr + mp->m_dirblksize;
79 80 81 82
		break;
	default:
		XFS_ERROR_REPORT("Bad Magic", XFS_ERRLEVEL_LOW, mp);
		return EFSCORRUPTED;
83 84
	}

L
Linus Torvalds 已提交
85 86 87 88 89
	count = lastfree = freeseen = 0;
	/*
	 * Account for zero bestfree entries.
	 */
	if (!bf[0].length) {
90
		XFS_WANT_CORRUPTED_RETURN(!bf[0].offset);
L
Linus Torvalds 已提交
91 92 93
		freeseen |= 1 << 0;
	}
	if (!bf[1].length) {
94
		XFS_WANT_CORRUPTED_RETURN(!bf[1].offset);
L
Linus Torvalds 已提交
95 96 97
		freeseen |= 1 << 1;
	}
	if (!bf[2].length) {
98
		XFS_WANT_CORRUPTED_RETURN(!bf[2].offset);
L
Linus Torvalds 已提交
99 100
		freeseen |= 1 << 2;
	}
101 102 103 104 105

	XFS_WANT_CORRUPTED_RETURN(be16_to_cpu(bf[0].length) >=
						be16_to_cpu(bf[1].length));
	XFS_WANT_CORRUPTED_RETURN(be16_to_cpu(bf[1].length) >=
						be16_to_cpu(bf[2].length));
L
Linus Torvalds 已提交
106 107 108 109 110 111 112 113 114 115
	/*
	 * Loop over the data/unused entries.
	 */
	while (p < endp) {
		dup = (xfs_dir2_data_unused_t *)p;
		/*
		 * If it's unused, look for the space in the bestfree table.
		 * If we find it, account for that, else make sure it
		 * doesn't need to be there.
		 */
116
		if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
117 118 119 120
			XFS_WANT_CORRUPTED_RETURN(lastfree == 0);
			XFS_WANT_CORRUPTED_RETURN(
				be16_to_cpu(*xfs_dir2_data_unused_tag_p(dup)) ==
					       (char *)dup - (char *)hdr);
121
			dfp = xfs_dir2_data_freefind(hdr, dup);
L
Linus Torvalds 已提交
122 123
			if (dfp) {
				i = (int)(dfp - bf);
124 125
				XFS_WANT_CORRUPTED_RETURN(
					(freeseen & (1 << i)) == 0);
L
Linus Torvalds 已提交
126
				freeseen |= 1 << i;
127
			} else {
128 129 130
				XFS_WANT_CORRUPTED_RETURN(
					be16_to_cpu(dup->length) <=
						be16_to_cpu(bf[2].length));
131
			}
132
			p += be16_to_cpu(dup->length);
L
Linus Torvalds 已提交
133 134 135 136 137 138 139 140 141 142
			lastfree = 1;
			continue;
		}
		/*
		 * It's a real entry.  Validate the fields.
		 * If this is a block directory then make sure it's
		 * in the leaf section of the block.
		 * The linear search is crude but this is DEBUG code.
		 */
		dep = (xfs_dir2_data_entry_t *)p;
143 144 145 146 147 148
		XFS_WANT_CORRUPTED_RETURN(dep->namelen != 0);
		XFS_WANT_CORRUPTED_RETURN(
			!xfs_dir_ino_validate(mp, be64_to_cpu(dep->inumber)));
		XFS_WANT_CORRUPTED_RETURN(
			be16_to_cpu(*xfs_dir2_data_entry_tag_p(dep)) ==
					       (char *)dep - (char *)hdr);
L
Linus Torvalds 已提交
149 150
		count++;
		lastfree = 0;
151
		if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC)) {
152
			addr = xfs_dir2_db_off_to_dataptr(mp, mp->m_dirdatablk,
L
Linus Torvalds 已提交
153
				(xfs_dir2_data_aoff_t)
154
				((char *)dep - (char *)hdr));
155 156 157
			name.name = dep->name;
			name.len = dep->namelen;
			hash = mp->m_dirnameops->hashname(&name);
158
			for (i = 0; i < be32_to_cpu(btp->count); i++) {
159 160
				if (be32_to_cpu(lep[i].address) == addr &&
				    be32_to_cpu(lep[i].hashval) == hash)
L
Linus Torvalds 已提交
161 162
					break;
			}
163
			XFS_WANT_CORRUPTED_RETURN(i < be32_to_cpu(btp->count));
L
Linus Torvalds 已提交
164
		}
165
		p += xfs_dir2_data_entsize(dep->namelen);
L
Linus Torvalds 已提交
166 167 168 169
	}
	/*
	 * Need to have seen all the entries and all the bestfree slots.
	 */
170
	XFS_WANT_CORRUPTED_RETURN(freeseen == 7);
171
	if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC)) {
172
		for (i = stale = 0; i < be32_to_cpu(btp->count); i++) {
173 174
			if (lep[i].address ==
			    cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
L
Linus Torvalds 已提交
175 176
				stale++;
			if (i > 0)
177 178 179
				XFS_WANT_CORRUPTED_RETURN(
					be32_to_cpu(lep[i].hashval) >=
						be32_to_cpu(lep[i - 1].hashval));
L
Linus Torvalds 已提交
180
		}
181 182 183
		XFS_WANT_CORRUPTED_RETURN(count ==
			be32_to_cpu(btp->count) - be32_to_cpu(btp->stale));
		XFS_WANT_CORRUPTED_RETURN(stale == be32_to_cpu(btp->stale));
L
Linus Torvalds 已提交
184
	}
185
	return 0;
L
Linus Torvalds 已提交
186 187
}

188
void
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219
xfs_dir2_data_verify(
	struct xfs_buf		*bp)
{
	struct xfs_mount	*mp = bp->b_target->bt_mount;
	struct xfs_dir2_data_hdr *hdr = bp->b_addr;
	int			block_ok = 0;

	block_ok = hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC);
	block_ok = block_ok && __xfs_dir2_data_check(NULL, bp) == 0;

	if (!block_ok) {
		XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, hdr);
		xfs_buf_ioerror(bp, EFSCORRUPTED);
	}

	bp->b_iodone = NULL;
	xfs_buf_ioend(bp, 0);
}

int
xfs_dir2_data_read(
	struct xfs_trans	*tp,
	struct xfs_inode	*dp,
	xfs_dablk_t		bno,
	xfs_daddr_t		mapped_bno,
	struct xfs_buf		**bpp)
{
	return xfs_da_read_buf(tp, dp, bno, mapped_bno, bpp,
					XFS_DATA_FORK, xfs_dir2_data_verify);
}

220 221 222 223 224 225 226 227 228 229 230
int
xfs_dir2_data_readahead(
	struct xfs_trans	*tp,
	struct xfs_inode	*dp,
	xfs_dablk_t		bno,
	xfs_daddr_t		mapped_bno)
{
	return xfs_da_reada_buf(tp, dp, bno, mapped_bno,
					XFS_DATA_FORK, xfs_dir2_data_verify);
}

L
Linus Torvalds 已提交
231 232 233 234
/*
 * Given a data block and an unused entry from that block,
 * return the bestfree entry if any that corresponds to it.
 */
235
STATIC xfs_dir2_data_free_t *
L
Linus Torvalds 已提交
236
xfs_dir2_data_freefind(
237
	xfs_dir2_data_hdr_t	*hdr,		/* data block */
L
Linus Torvalds 已提交
238 239 240 241 242 243 244 245 246
	xfs_dir2_data_unused_t	*dup)		/* data unused entry */
{
	xfs_dir2_data_free_t	*dfp;		/* bestfree entry */
	xfs_dir2_data_aoff_t	off;		/* offset value needed */
#if defined(DEBUG) && defined(__KERNEL__)
	int			matched;	/* matched the value */
	int			seenzero;	/* saw a 0 bestfree entry */
#endif

247
	off = (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr);
L
Linus Torvalds 已提交
248 249 250 251 252 253
#if defined(DEBUG) && defined(__KERNEL__)
	/*
	 * Validate some consistency in the bestfree table.
	 * Check order, non-overlapping entries, and if we find the
	 * one we're looking for it has to be exact.
	 */
254 255
	ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
	       hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
256 257
	for (dfp = &hdr->bestfree[0], seenzero = matched = 0;
	     dfp < &hdr->bestfree[XFS_DIR2_DATA_FD_COUNT];
L
Linus Torvalds 已提交
258 259 260 261 262 263 264
	     dfp++) {
		if (!dfp->offset) {
			ASSERT(!dfp->length);
			seenzero = 1;
			continue;
		}
		ASSERT(seenzero == 0);
265
		if (be16_to_cpu(dfp->offset) == off) {
L
Linus Torvalds 已提交
266
			matched = 1;
267
			ASSERT(dfp->length == dup->length);
268
		} else if (off < be16_to_cpu(dfp->offset))
269
			ASSERT(off + be16_to_cpu(dup->length) <= be16_to_cpu(dfp->offset));
L
Linus Torvalds 已提交
270
		else
271
			ASSERT(be16_to_cpu(dfp->offset) + be16_to_cpu(dfp->length) <= off);
272
		ASSERT(matched || be16_to_cpu(dfp->length) >= be16_to_cpu(dup->length));
273
		if (dfp > &hdr->bestfree[0])
274
			ASSERT(be16_to_cpu(dfp[-1].length) >= be16_to_cpu(dfp[0].length));
L
Linus Torvalds 已提交
275 276 277 278 279 280
	}
#endif
	/*
	 * If this is smaller than the smallest bestfree entry,
	 * it can't be there since they're sorted.
	 */
281
	if (be16_to_cpu(dup->length) <
282
	    be16_to_cpu(hdr->bestfree[XFS_DIR2_DATA_FD_COUNT - 1].length))
L
Linus Torvalds 已提交
283 284 285 286
		return NULL;
	/*
	 * Look at the three bestfree entries for our guy.
	 */
287 288
	for (dfp = &hdr->bestfree[0];
	     dfp < &hdr->bestfree[XFS_DIR2_DATA_FD_COUNT];
L
Linus Torvalds 已提交
289 290 291
	     dfp++) {
		if (!dfp->offset)
			return NULL;
292
		if (be16_to_cpu(dfp->offset) == off)
L
Linus Torvalds 已提交
293 294 295 296 297 298 299 300 301 302 303 304 305
			return dfp;
	}
	/*
	 * Didn't find it.  This only happens if there are duplicate lengths.
	 */
	return NULL;
}

/*
 * Insert an unused-space entry into the bestfree table.
 */
xfs_dir2_data_free_t *				/* entry inserted */
xfs_dir2_data_freeinsert(
306
	xfs_dir2_data_hdr_t	*hdr,		/* data block pointer */
L
Linus Torvalds 已提交
307 308 309 310 311 312 313
	xfs_dir2_data_unused_t	*dup,		/* unused space */
	int			*loghead)	/* log the data header (out) */
{
	xfs_dir2_data_free_t	*dfp;		/* bestfree table pointer */
	xfs_dir2_data_free_t	new;		/* new bestfree entry */

#ifdef __KERNEL__
314 315
	ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
	       hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
L
Linus Torvalds 已提交
316
#endif
317
	dfp = hdr->bestfree;
318
	new.length = dup->length;
319 320
	new.offset = cpu_to_be16((char *)dup - (char *)hdr);

L
Linus Torvalds 已提交
321 322 323
	/*
	 * Insert at position 0, 1, or 2; or not at all.
	 */
324
	if (be16_to_cpu(new.length) > be16_to_cpu(dfp[0].length)) {
L
Linus Torvalds 已提交
325 326 327 328 329 330
		dfp[2] = dfp[1];
		dfp[1] = dfp[0];
		dfp[0] = new;
		*loghead = 1;
		return &dfp[0];
	}
331
	if (be16_to_cpu(new.length) > be16_to_cpu(dfp[1].length)) {
L
Linus Torvalds 已提交
332 333 334 335 336
		dfp[2] = dfp[1];
		dfp[1] = new;
		*loghead = 1;
		return &dfp[1];
	}
337
	if (be16_to_cpu(new.length) > be16_to_cpu(dfp[2].length)) {
L
Linus Torvalds 已提交
338 339 340 341 342 343 344 345 346 347
		dfp[2] = new;
		*loghead = 1;
		return &dfp[2];
	}
	return NULL;
}

/*
 * Remove a bestfree entry from the table.
 */
348
STATIC void
L
Linus Torvalds 已提交
349
xfs_dir2_data_freeremove(
350
	xfs_dir2_data_hdr_t	*hdr,		/* data block header */
L
Linus Torvalds 已提交
351 352 353 354
	xfs_dir2_data_free_t	*dfp,		/* bestfree entry pointer */
	int			*loghead)	/* out: log data header */
{
#ifdef __KERNEL__
355 356
	ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
	       hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
L
Linus Torvalds 已提交
357 358 359 360
#endif
	/*
	 * It's the first entry, slide the next 2 up.
	 */
361 362 363
	if (dfp == &hdr->bestfree[0]) {
		hdr->bestfree[0] = hdr->bestfree[1];
		hdr->bestfree[1] = hdr->bestfree[2];
L
Linus Torvalds 已提交
364 365 366 367
	}
	/*
	 * It's the second entry, slide the 3rd entry up.
	 */
368 369
	else if (dfp == &hdr->bestfree[1])
		hdr->bestfree[1] = hdr->bestfree[2];
L
Linus Torvalds 已提交
370 371 372 373
	/*
	 * Must be the last entry.
	 */
	else
374
		ASSERT(dfp == &hdr->bestfree[2]);
L
Linus Torvalds 已提交
375 376 377
	/*
	 * Clear the 3rd entry, must be zero now.
	 */
378 379
	hdr->bestfree[2].length = 0;
	hdr->bestfree[2].offset = 0;
L
Linus Torvalds 已提交
380 381 382 383 384 385 386 387 388
	*loghead = 1;
}

/*
 * Given a data block, reconstruct its bestfree map.
 */
void
xfs_dir2_data_freescan(
	xfs_mount_t		*mp,		/* filesystem mount point */
389
	xfs_dir2_data_hdr_t	*hdr,		/* data block header */
390
	int			*loghead)	/* out: log data header */
L
Linus Torvalds 已提交
391 392 393 394 395 396 397 398
{
	xfs_dir2_block_tail_t	*btp;		/* block tail */
	xfs_dir2_data_entry_t	*dep;		/* active data entry */
	xfs_dir2_data_unused_t	*dup;		/* unused data entry */
	char			*endp;		/* end of block's data */
	char			*p;		/* current entry pointer */

#ifdef __KERNEL__
399 400
	ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
	       hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
L
Linus Torvalds 已提交
401 402 403 404
#endif
	/*
	 * Start by clearing the table.
	 */
405
	memset(hdr->bestfree, 0, sizeof(hdr->bestfree));
L
Linus Torvalds 已提交
406 407 408 409
	*loghead = 1;
	/*
	 * Set up pointers.
	 */
410
	p = (char *)(hdr + 1);
411
	if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC)) {
412
		btp = xfs_dir2_block_tail_p(mp, hdr);
413
		endp = (char *)xfs_dir2_block_leaf_p(btp);
L
Linus Torvalds 已提交
414
	} else
415
		endp = (char *)hdr + mp->m_dirblksize;
L
Linus Torvalds 已提交
416 417 418 419 420 421 422 423
	/*
	 * Loop over the block's entries.
	 */
	while (p < endp) {
		dup = (xfs_dir2_data_unused_t *)p;
		/*
		 * If it's a free entry, insert it.
		 */
424
		if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
425
			ASSERT((char *)dup - (char *)hdr ==
426
			       be16_to_cpu(*xfs_dir2_data_unused_tag_p(dup)));
427
			xfs_dir2_data_freeinsert(hdr, dup, loghead);
428
			p += be16_to_cpu(dup->length);
L
Linus Torvalds 已提交
429 430 431 432 433 434
		}
		/*
		 * For active entries, check their tags and skip them.
		 */
		else {
			dep = (xfs_dir2_data_entry_t *)p;
435
			ASSERT((char *)dep - (char *)hdr ==
436 437
			       be16_to_cpu(*xfs_dir2_data_entry_tag_p(dep)));
			p += xfs_dir2_data_entsize(dep->namelen);
L
Linus Torvalds 已提交
438 439 440 441 442 443 444 445 446 447 448 449
		}
	}
}

/*
 * Initialize a data block at the given block number in the directory.
 * Give back the buffer for the created block.
 */
int						/* error */
xfs_dir2_data_init(
	xfs_da_args_t		*args,		/* directory operation args */
	xfs_dir2_db_t		blkno,		/* logical dir block number */
450
	struct xfs_buf		**bpp)		/* output block buffer */
L
Linus Torvalds 已提交
451
{
452
	struct xfs_buf		*bp;		/* block buffer */
453
	xfs_dir2_data_hdr_t	*hdr;		/* data block header */
L
Linus Torvalds 已提交
454 455 456 457 458 459 460 461 462 463 464 465 466 467
	xfs_inode_t		*dp;		/* incore directory inode */
	xfs_dir2_data_unused_t	*dup;		/* unused entry pointer */
	int			error;		/* error return value */
	int			i;		/* bestfree index */
	xfs_mount_t		*mp;		/* filesystem mount point */
	xfs_trans_t		*tp;		/* transaction pointer */
	int                     t;              /* temp */

	dp = args->dp;
	mp = dp->i_mount;
	tp = args->trans;
	/*
	 * Get the buffer set up for the block.
	 */
468
	error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(mp, blkno), -1, &bp,
L
Linus Torvalds 已提交
469 470 471 472 473
		XFS_DATA_FORK);
	if (error) {
		return error;
	}
	ASSERT(bp != NULL);
474

L
Linus Torvalds 已提交
475 476 477
	/*
	 * Initialize the header.
	 */
478
	hdr = bp->b_addr;
479 480
	hdr->magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC);
	hdr->bestfree[0].offset = cpu_to_be16(sizeof(*hdr));
L
Linus Torvalds 已提交
481
	for (i = 1; i < XFS_DIR2_DATA_FD_COUNT; i++) {
482 483
		hdr->bestfree[i].length = 0;
		hdr->bestfree[i].offset = 0;
L
Linus Torvalds 已提交
484
	}
485

L
Linus Torvalds 已提交
486 487 488
	/*
	 * Set up an unused entry for the block's body.
	 */
489
	dup = (xfs_dir2_data_unused_t *)(hdr + 1);
490
	dup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
L
Linus Torvalds 已提交
491

492 493
	t = mp->m_dirblksize - (uint)sizeof(*hdr);
	hdr->bestfree[0].length = cpu_to_be16(t);
494
	dup->length = cpu_to_be16(t);
495
	*xfs_dir2_data_unused_tag_p(dup) = cpu_to_be16((char *)dup - (char *)hdr);
L
Linus Torvalds 已提交
496 497 498 499 500 501 502 503 504 505 506 507 508 509
	/*
	 * Log it and return it.
	 */
	xfs_dir2_data_log_header(tp, bp);
	xfs_dir2_data_log_unused(tp, bp, dup);
	*bpp = bp;
	return 0;
}

/*
 * Log an active data entry from the block.
 */
void
xfs_dir2_data_log_entry(
510 511
	struct xfs_trans	*tp,
	struct xfs_buf		*bp,
L
Linus Torvalds 已提交
512 513
	xfs_dir2_data_entry_t	*dep)		/* data entry pointer */
{
514
	xfs_dir2_data_hdr_t	*hdr = bp->b_addr;
L
Linus Torvalds 已提交
515

516 517
	ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
	       hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
518

519
	xfs_trans_log_buf(tp, bp, (uint)((char *)dep - (char *)hdr),
520
		(uint)((char *)(xfs_dir2_data_entry_tag_p(dep) + 1) -
521
		       (char *)hdr - 1));
L
Linus Torvalds 已提交
522 523 524 525 526 527 528
}

/*
 * Log a data block header.
 */
void
xfs_dir2_data_log_header(
529 530
	struct xfs_trans	*tp,
	struct xfs_buf		*bp)
L
Linus Torvalds 已提交
531
{
532
	xfs_dir2_data_hdr_t	*hdr = bp->b_addr;
L
Linus Torvalds 已提交
533

534 535
	ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
	       hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
536

537
	xfs_trans_log_buf(tp, bp, 0, sizeof(*hdr) - 1);
L
Linus Torvalds 已提交
538 539 540 541 542 543 544
}

/*
 * Log a data unused entry.
 */
void
xfs_dir2_data_log_unused(
545 546
	struct xfs_trans	*tp,
	struct xfs_buf		*bp,
L
Linus Torvalds 已提交
547 548
	xfs_dir2_data_unused_t	*dup)		/* data unused pointer */
{
549
	xfs_dir2_data_hdr_t	*hdr = bp->b_addr;
550

551 552
	ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
	       hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
L
Linus Torvalds 已提交
553 554 555 556

	/*
	 * Log the first part of the unused entry.
	 */
557
	xfs_trans_log_buf(tp, bp, (uint)((char *)dup - (char *)hdr),
L
Linus Torvalds 已提交
558
		(uint)((char *)&dup->length + sizeof(dup->length) -
559
		       1 - (char *)hdr));
L
Linus Torvalds 已提交
560 561 562
	/*
	 * Log the end (tag) of the unused entry.
	 */
563
	xfs_trans_log_buf(tp, bp,
564 565
		(uint)((char *)xfs_dir2_data_unused_tag_p(dup) - (char *)hdr),
		(uint)((char *)xfs_dir2_data_unused_tag_p(dup) - (char *)hdr +
L
Linus Torvalds 已提交
566 567 568 569 570 571 572 573 574
		       sizeof(xfs_dir2_data_off_t) - 1));
}

/*
 * Make a byte range in the data block unused.
 * Its current contents are unimportant.
 */
void
xfs_dir2_data_make_free(
575 576
	struct xfs_trans	*tp,
	struct xfs_buf		*bp,
L
Linus Torvalds 已提交
577 578 579 580 581
	xfs_dir2_data_aoff_t	offset,		/* starting byte offset */
	xfs_dir2_data_aoff_t	len,		/* length in bytes */
	int			*needlogp,	/* out: log header */
	int			*needscanp)	/* out: regen bestfree */
{
582
	xfs_dir2_data_hdr_t	*hdr;		/* data block pointer */
L
Linus Torvalds 已提交
583 584 585 586 587 588 589 590 591
	xfs_dir2_data_free_t	*dfp;		/* bestfree pointer */
	char			*endptr;	/* end of data area */
	xfs_mount_t		*mp;		/* filesystem mount point */
	int			needscan;	/* need to regen bestfree */
	xfs_dir2_data_unused_t	*newdup;	/* new unused entry */
	xfs_dir2_data_unused_t	*postdup;	/* unused entry after us */
	xfs_dir2_data_unused_t	*prevdup;	/* unused entry before us */

	mp = tp->t_mountp;
592
	hdr = bp->b_addr;
593

L
Linus Torvalds 已提交
594 595 596
	/*
	 * Figure out where the end of the data area is.
	 */
597
	if (hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC))
598
		endptr = (char *)hdr + mp->m_dirblksize;
L
Linus Torvalds 已提交
599 600 601
	else {
		xfs_dir2_block_tail_t	*btp;	/* block tail */

602
		ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
603
		btp = xfs_dir2_block_tail_p(mp, hdr);
604
		endptr = (char *)xfs_dir2_block_leaf_p(btp);
L
Linus Torvalds 已提交
605 606 607 608 609
	}
	/*
	 * If this isn't the start of the block, then back up to
	 * the previous entry and see if it's free.
	 */
610
	if (offset > sizeof(*hdr)) {
611
		__be16			*tagp;	/* tag just before us */
L
Linus Torvalds 已提交
612

613 614
		tagp = (__be16 *)((char *)hdr + offset) - 1;
		prevdup = (xfs_dir2_data_unused_t *)((char *)hdr + be16_to_cpu(*tagp));
615
		if (be16_to_cpu(prevdup->freetag) != XFS_DIR2_DATA_FREE_TAG)
L
Linus Torvalds 已提交
616 617 618 619 620 621 622
			prevdup = NULL;
	} else
		prevdup = NULL;
	/*
	 * If this isn't the end of the block, see if the entry after
	 * us is free.
	 */
623
	if ((char *)hdr + offset + len < endptr) {
L
Linus Torvalds 已提交
624
		postdup =
625
			(xfs_dir2_data_unused_t *)((char *)hdr + offset + len);
626
		if (be16_to_cpu(postdup->freetag) != XFS_DIR2_DATA_FREE_TAG)
L
Linus Torvalds 已提交
627 628 629 630 631 632 633 634 635 636 637 638 639 640 641
			postdup = NULL;
	} else
		postdup = NULL;
	ASSERT(*needscanp == 0);
	needscan = 0;
	/*
	 * Previous and following entries are both free,
	 * merge everything into a single free entry.
	 */
	if (prevdup && postdup) {
		xfs_dir2_data_free_t	*dfp2;	/* another bestfree pointer */

		/*
		 * See if prevdup and/or postdup are in bestfree table.
		 */
642 643
		dfp = xfs_dir2_data_freefind(hdr, prevdup);
		dfp2 = xfs_dir2_data_freefind(hdr, postdup);
L
Linus Torvalds 已提交
644 645 646 647 648 649
		/*
		 * We need a rescan unless there are exactly 2 free entries
		 * namely our two.  Then we know what's happening, otherwise
		 * since the third bestfree is there, there might be more
		 * entries.
		 */
650
		needscan = (hdr->bestfree[2].length != 0);
L
Linus Torvalds 已提交
651 652 653
		/*
		 * Fix up the new big freespace.
		 */
654
		be16_add_cpu(&prevdup->length, len + be16_to_cpu(postdup->length));
655
		*xfs_dir2_data_unused_tag_p(prevdup) =
656
			cpu_to_be16((char *)prevdup - (char *)hdr);
L
Linus Torvalds 已提交
657 658 659 660 661 662 663 664 665
		xfs_dir2_data_log_unused(tp, bp, prevdup);
		if (!needscan) {
			/*
			 * Has to be the case that entries 0 and 1 are
			 * dfp and dfp2 (don't know which is which), and
			 * entry 2 is empty.
			 * Remove entry 1 first then entry 0.
			 */
			ASSERT(dfp && dfp2);
666 667
			if (dfp == &hdr->bestfree[1]) {
				dfp = &hdr->bestfree[0];
L
Linus Torvalds 已提交
668
				ASSERT(dfp2 == dfp);
669
				dfp2 = &hdr->bestfree[1];
L
Linus Torvalds 已提交
670
			}
671 672
			xfs_dir2_data_freeremove(hdr, dfp2, needlogp);
			xfs_dir2_data_freeremove(hdr, dfp, needlogp);
L
Linus Torvalds 已提交
673 674 675
			/*
			 * Now insert the new entry.
			 */
676 677
			dfp = xfs_dir2_data_freeinsert(hdr, prevdup, needlogp);
			ASSERT(dfp == &hdr->bestfree[0]);
678
			ASSERT(dfp->length == prevdup->length);
L
Linus Torvalds 已提交
679 680 681 682 683 684 685 686
			ASSERT(!dfp[1].length);
			ASSERT(!dfp[2].length);
		}
	}
	/*
	 * The entry before us is free, merge with it.
	 */
	else if (prevdup) {
687
		dfp = xfs_dir2_data_freefind(hdr, prevdup);
688
		be16_add_cpu(&prevdup->length, len);
689
		*xfs_dir2_data_unused_tag_p(prevdup) =
690
			cpu_to_be16((char *)prevdup - (char *)hdr);
L
Linus Torvalds 已提交
691 692 693 694 695 696 697
		xfs_dir2_data_log_unused(tp, bp, prevdup);
		/*
		 * If the previous entry was in the table, the new entry
		 * is longer, so it will be in the table too.  Remove
		 * the old one and add the new one.
		 */
		if (dfp) {
698 699
			xfs_dir2_data_freeremove(hdr, dfp, needlogp);
			xfs_dir2_data_freeinsert(hdr, prevdup, needlogp);
L
Linus Torvalds 已提交
700 701 702 703
		}
		/*
		 * Otherwise we need a scan if the new entry is big enough.
		 */
704
		else {
705
			needscan = be16_to_cpu(prevdup->length) >
706
				   be16_to_cpu(hdr->bestfree[2].length);
707
		}
L
Linus Torvalds 已提交
708 709 710 711 712
	}
	/*
	 * The following entry is free, merge with it.
	 */
	else if (postdup) {
713 714
		dfp = xfs_dir2_data_freefind(hdr, postdup);
		newdup = (xfs_dir2_data_unused_t *)((char *)hdr + offset);
715 716
		newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
		newdup->length = cpu_to_be16(len + be16_to_cpu(postdup->length));
717
		*xfs_dir2_data_unused_tag_p(newdup) =
718
			cpu_to_be16((char *)newdup - (char *)hdr);
L
Linus Torvalds 已提交
719 720 721 722 723 724 725
		xfs_dir2_data_log_unused(tp, bp, newdup);
		/*
		 * If the following entry was in the table, the new entry
		 * is longer, so it will be in the table too.  Remove
		 * the old one and add the new one.
		 */
		if (dfp) {
726 727
			xfs_dir2_data_freeremove(hdr, dfp, needlogp);
			xfs_dir2_data_freeinsert(hdr, newdup, needlogp);
L
Linus Torvalds 已提交
728 729 730 731
		}
		/*
		 * Otherwise we need a scan if the new entry is big enough.
		 */
732
		else {
733
			needscan = be16_to_cpu(newdup->length) >
734
				   be16_to_cpu(hdr->bestfree[2].length);
735
		}
L
Linus Torvalds 已提交
736 737 738 739 740
	}
	/*
	 * Neither neighbor is free.  Make a new entry.
	 */
	else {
741
		newdup = (xfs_dir2_data_unused_t *)((char *)hdr + offset);
742 743
		newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
		newdup->length = cpu_to_be16(len);
744
		*xfs_dir2_data_unused_tag_p(newdup) =
745
			cpu_to_be16((char *)newdup - (char *)hdr);
L
Linus Torvalds 已提交
746
		xfs_dir2_data_log_unused(tp, bp, newdup);
747
		xfs_dir2_data_freeinsert(hdr, newdup, needlogp);
L
Linus Torvalds 已提交
748 749 750 751 752 753 754 755 756
	}
	*needscanp = needscan;
}

/*
 * Take a byte range out of an existing unused space and make it un-free.
 */
void
xfs_dir2_data_use_free(
757 758
	struct xfs_trans	*tp,
	struct xfs_buf		*bp,
L
Linus Torvalds 已提交
759 760 761 762 763 764
	xfs_dir2_data_unused_t	*dup,		/* unused entry */
	xfs_dir2_data_aoff_t	offset,		/* starting offset to use */
	xfs_dir2_data_aoff_t	len,		/* length to use */
	int			*needlogp,	/* out: need to log header */
	int			*needscanp)	/* out: need regen bestfree */
{
765
	xfs_dir2_data_hdr_t	*hdr;		/* data block header */
L
Linus Torvalds 已提交
766 767 768 769 770 771 772 773
	xfs_dir2_data_free_t	*dfp;		/* bestfree pointer */
	int			matchback;	/* matches end of freespace */
	int			matchfront;	/* matches start of freespace */
	int			needscan;	/* need to regen bestfree */
	xfs_dir2_data_unused_t	*newdup;	/* new unused entry */
	xfs_dir2_data_unused_t	*newdup2;	/* another new unused entry */
	int			oldlen;		/* old unused entry's length */

774
	hdr = bp->b_addr;
775 776
	ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
	       hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
777
	ASSERT(be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG);
778 779 780
	ASSERT(offset >= (char *)dup - (char *)hdr);
	ASSERT(offset + len <= (char *)dup + be16_to_cpu(dup->length) - (char *)hdr);
	ASSERT((char *)dup - (char *)hdr == be16_to_cpu(*xfs_dir2_data_unused_tag_p(dup)));
L
Linus Torvalds 已提交
781 782 783
	/*
	 * Look up the entry in the bestfree table.
	 */
784
	dfp = xfs_dir2_data_freefind(hdr, dup);
785
	oldlen = be16_to_cpu(dup->length);
786
	ASSERT(dfp || oldlen <= be16_to_cpu(hdr->bestfree[2].length));
L
Linus Torvalds 已提交
787 788 789
	/*
	 * Check for alignment with front and back of the entry.
	 */
790 791
	matchfront = (char *)dup - (char *)hdr == offset;
	matchback = (char *)dup + oldlen - (char *)hdr == offset + len;
L
Linus Torvalds 已提交
792 793 794 795 796 797 798 799
	ASSERT(*needscanp == 0);
	needscan = 0;
	/*
	 * If we matched it exactly we just need to get rid of it from
	 * the bestfree table.
	 */
	if (matchfront && matchback) {
		if (dfp) {
800
			needscan = (hdr->bestfree[2].offset != 0);
L
Linus Torvalds 已提交
801
			if (!needscan)
802
				xfs_dir2_data_freeremove(hdr, dfp, needlogp);
L
Linus Torvalds 已提交
803 804 805 806 807 808 809
		}
	}
	/*
	 * We match the first part of the entry.
	 * Make a new entry with the remaining freespace.
	 */
	else if (matchfront) {
810
		newdup = (xfs_dir2_data_unused_t *)((char *)hdr + offset + len);
811 812
		newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
		newdup->length = cpu_to_be16(oldlen - len);
813
		*xfs_dir2_data_unused_tag_p(newdup) =
814
			cpu_to_be16((char *)newdup - (char *)hdr);
L
Linus Torvalds 已提交
815 816 817 818 819
		xfs_dir2_data_log_unused(tp, bp, newdup);
		/*
		 * If it was in the table, remove it and add the new one.
		 */
		if (dfp) {
820 821
			xfs_dir2_data_freeremove(hdr, dfp, needlogp);
			dfp = xfs_dir2_data_freeinsert(hdr, newdup, needlogp);
L
Linus Torvalds 已提交
822
			ASSERT(dfp != NULL);
823
			ASSERT(dfp->length == newdup->length);
824
			ASSERT(be16_to_cpu(dfp->offset) == (char *)newdup - (char *)hdr);
L
Linus Torvalds 已提交
825 826 827 828 829
			/*
			 * If we got inserted at the last slot,
			 * that means we don't know if there was a better
			 * choice for the last slot, or not.  Rescan.
			 */
830
			needscan = dfp == &hdr->bestfree[2];
L
Linus Torvalds 已提交
831 832 833 834 835 836 837 838
		}
	}
	/*
	 * We match the last part of the entry.
	 * Trim the allocated space off the tail of the entry.
	 */
	else if (matchback) {
		newdup = dup;
839
		newdup->length = cpu_to_be16(((char *)hdr + offset) - (char *)newdup);
840
		*xfs_dir2_data_unused_tag_p(newdup) =
841
			cpu_to_be16((char *)newdup - (char *)hdr);
L
Linus Torvalds 已提交
842 843 844 845 846
		xfs_dir2_data_log_unused(tp, bp, newdup);
		/*
		 * If it was in the table, remove it and add the new one.
		 */
		if (dfp) {
847 848
			xfs_dir2_data_freeremove(hdr, dfp, needlogp);
			dfp = xfs_dir2_data_freeinsert(hdr, newdup, needlogp);
L
Linus Torvalds 已提交
849
			ASSERT(dfp != NULL);
850
			ASSERT(dfp->length == newdup->length);
851
			ASSERT(be16_to_cpu(dfp->offset) == (char *)newdup - (char *)hdr);
L
Linus Torvalds 已提交
852 853 854 855 856
			/*
			 * If we got inserted at the last slot,
			 * that means we don't know if there was a better
			 * choice for the last slot, or not.  Rescan.
			 */
857
			needscan = dfp == &hdr->bestfree[2];
L
Linus Torvalds 已提交
858 859 860 861 862 863 864 865
		}
	}
	/*
	 * Poking out the middle of an entry.
	 * Make two new entries.
	 */
	else {
		newdup = dup;
866
		newdup->length = cpu_to_be16(((char *)hdr + offset) - (char *)newdup);
867
		*xfs_dir2_data_unused_tag_p(newdup) =
868
			cpu_to_be16((char *)newdup - (char *)hdr);
L
Linus Torvalds 已提交
869
		xfs_dir2_data_log_unused(tp, bp, newdup);
870
		newdup2 = (xfs_dir2_data_unused_t *)((char *)hdr + offset + len);
871 872
		newdup2->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
		newdup2->length = cpu_to_be16(oldlen - len - be16_to_cpu(newdup->length));
873
		*xfs_dir2_data_unused_tag_p(newdup2) =
874
			cpu_to_be16((char *)newdup2 - (char *)hdr);
L
Linus Torvalds 已提交
875 876 877 878 879 880 881 882 883 884
		xfs_dir2_data_log_unused(tp, bp, newdup2);
		/*
		 * If the old entry was in the table, we need to scan
		 * if the 3rd entry was valid, since these entries
		 * are smaller than the old one.
		 * If we don't need to scan that means there were 1 or 2
		 * entries in the table, and removing the old and adding
		 * the 2 new will work.
		 */
		if (dfp) {
885
			needscan = (hdr->bestfree[2].length != 0);
L
Linus Torvalds 已提交
886
			if (!needscan) {
887 888 889 890
				xfs_dir2_data_freeremove(hdr, dfp, needlogp);
				xfs_dir2_data_freeinsert(hdr, newdup, needlogp);
				xfs_dir2_data_freeinsert(hdr, newdup2,
							 needlogp);
L
Linus Torvalds 已提交
891 892 893 894 895
			}
		}
	}
	*needscanp = needscan;
}