xfs_btree.h 14.6 KB
Newer Older
L
Linus Torvalds 已提交
1
/*
2 3
 * Copyright (c) 2000-2001,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 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
 */
#ifndef __XFS_BTREE_H__
#define	__XFS_BTREE_H__

struct xfs_buf;
struct xfs_bmap_free;
struct xfs_inode;
struct xfs_mount;
struct xfs_trans;

/*
 * This nonsense is to make -wlint happy.
 */
#define	XFS_LOOKUP_EQ	((xfs_lookup_t)XFS_LOOKUP_EQi)
#define	XFS_LOOKUP_LE	((xfs_lookup_t)XFS_LOOKUP_LEi)
#define	XFS_LOOKUP_GE	((xfs_lookup_t)XFS_LOOKUP_GEi)

#define	XFS_BTNUM_BNO	((xfs_btnum_t)XFS_BTNUM_BNOi)
#define	XFS_BTNUM_CNT	((xfs_btnum_t)XFS_BTNUM_CNTi)
#define	XFS_BTNUM_BMAP	((xfs_btnum_t)XFS_BTNUM_BMAPi)
#define	XFS_BTNUM_INO	((xfs_btnum_t)XFS_BTNUM_INOi)

/*
 * Short form header: space allocation btrees.
 */
42 43 44 45 46 47
typedef struct xfs_btree_sblock {
	__be32		bb_magic;	/* magic number for block type */
	__be16		bb_level;	/* 0 is a leaf */
	__be16		bb_numrecs;	/* current # of data records */
	__be32		bb_leftsib;	/* left sibling block or NULLAGBLOCK */
	__be32		bb_rightsib;	/* right sibling block or NULLAGBLOCK */
L
Linus Torvalds 已提交
48 49 50 51 52
} xfs_btree_sblock_t;

/*
 * Long form header: bmap btrees.
 */
53 54 55 56 57 58
typedef struct xfs_btree_lblock {
	__be32		bb_magic;	/* magic number for block type */
	__be16		bb_level;	/* 0 is a leaf */
	__be16		bb_numrecs;	/* current # of data records */
	__be64		bb_leftsib;	/* left sibling block or NULLDFSBNO */
	__be64		bb_rightsib;	/* right sibling block or NULLDFSBNO */
L
Linus Torvalds 已提交
59 60 61 62 63 64 65
} xfs_btree_lblock_t;

/*
 * Combined header and structure, used by common code.
 */
typedef struct xfs_btree_hdr
{
66 67 68
	__be32		bb_magic;	/* magic number for block type */
	__be16		bb_level;	/* 0 is a leaf */
	__be16		bb_numrecs;	/* current # of data records */
L
Linus Torvalds 已提交
69 70
} xfs_btree_hdr_t;

71
typedef struct xfs_btree_block {
L
Linus Torvalds 已提交
72
	xfs_btree_hdr_t	bb_h;		/* header */
73 74 75 76 77
	union {
		struct {
			__be32		bb_leftsib;
			__be32		bb_rightsib;
		} s;			/* short form pointers */
L
Linus Torvalds 已提交
78
		struct	{
79 80 81 82
			__be64		bb_leftsib;
			__be64		bb_rightsib;
		} l;			/* long form pointers */
	} bb_u;				/* rest */
L
Linus Torvalds 已提交
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
} xfs_btree_block_t;

/*
 * For logging record fields.
 */
#define	XFS_BB_MAGIC		0x01
#define	XFS_BB_LEVEL		0x02
#define	XFS_BB_NUMRECS		0x04
#define	XFS_BB_LEFTSIB		0x08
#define	XFS_BB_RIGHTSIB		0x10
#define	XFS_BB_NUM_BITS		5
#define	XFS_BB_ALL_BITS		((1 << XFS_BB_NUM_BITS) - 1)

/*
 * Boolean to select which form of xfs_btree_block_t.bb_u to use.
 */
#define	XFS_BTREE_LONG_PTRS(btnum)	((btnum) == XFS_BTNUM_BMAP)

/*
 * Magic numbers for btree blocks.
 */
extern const __uint32_t	xfs_magics[];

/*
 * Maximum and minimum records in a btree block.
 * Given block size, type prefix, and leaf flag (0 or 1).
 * The divisor below is equivalent to lf ? (e1) : (e2) but that produces
 * compiler warnings.
 */
#define	XFS_BTREE_BLOCK_MAXRECS(bsz,t,lf)	\
	((int)(((bsz) - (uint)sizeof(t ## _block_t)) / \
	 (((lf) * (uint)sizeof(t ## _rec_t)) + \
	  ((1 - (lf)) * \
	   ((uint)sizeof(t ## _key_t) + (uint)sizeof(t ## _ptr_t))))))
#define	XFS_BTREE_BLOCK_MINRECS(bsz,t,lf)	\
	(XFS_BTREE_BLOCK_MAXRECS(bsz,t,lf) / 2)

/*
 * Record, key, and pointer address calculation macros.
 * Given block size, type prefix, block pointer, and index of requested entry
 * (first entry numbered 1).
 */
#define	XFS_BTREE_REC_ADDR(bsz,t,bb,i,mxr)	\
	((t ## _rec_t *)((char *)(bb) + sizeof(t ## _block_t) + \
	 ((i) - 1) * sizeof(t ## _rec_t)))
#define	XFS_BTREE_KEY_ADDR(bsz,t,bb,i,mxr)	\
	((t ## _key_t *)((char *)(bb) + sizeof(t ## _block_t) + \
	 ((i) - 1) * sizeof(t ## _key_t)))
#define	XFS_BTREE_PTR_ADDR(bsz,t,bb,i,mxr)	\
	((t ## _ptr_t *)((char *)(bb) + sizeof(t ## _block_t) + \
	 (mxr) * sizeof(t ## _key_t) + ((i) - 1) * sizeof(t ## _ptr_t)))

#define	XFS_BTREE_MAXLEVELS	8	/* max of all btrees */

/*
 * Btree cursor structure.
 * This collects all information needed by the btree code in one place.
 */
typedef struct xfs_btree_cur
{
	struct xfs_trans	*bc_tp;	/* transaction we're in, if any */
	struct xfs_mount	*bc_mp;	/* file system mount struct */
	union {
146
		xfs_alloc_rec_incore_t	a;
L
Linus Torvalds 已提交
147
		xfs_bmbt_irec_t		b;
148
		xfs_inobt_rec_incore_t	i;
L
Linus Torvalds 已提交
149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185
	}		bc_rec;		/* current insert/search record value */
	struct xfs_buf	*bc_bufs[XFS_BTREE_MAXLEVELS];	/* buf ptr per level */
	int		bc_ptrs[XFS_BTREE_MAXLEVELS];	/* key/record # */
	__uint8_t	bc_ra[XFS_BTREE_MAXLEVELS];	/* readahead bits */
#define	XFS_BTCUR_LEFTRA	1	/* left sibling has been read-ahead */
#define	XFS_BTCUR_RIGHTRA	2	/* right sibling has been read-ahead */
	__uint8_t	bc_nlevels;	/* number of levels in the tree */
	__uint8_t	bc_blocklog;	/* log2(blocksize) of btree blocks */
	xfs_btnum_t	bc_btnum;	/* identifies which btree type */
	union {
		struct {			/* needed for BNO, CNT */
			struct xfs_buf	*agbp;	/* agf buffer pointer */
			xfs_agnumber_t	agno;	/* ag number */
		} a;
		struct {			/* needed for BMAP */
			struct xfs_inode *ip;	/* pointer to our inode */
			struct xfs_bmap_free *flist;	/* list to free after */
			xfs_fsblock_t	firstblock;	/* 1st blk allocated */
			int		allocated;	/* count of alloced */
			short		forksize;	/* fork's inode space */
			char		whichfork;	/* data or attr fork */
			char		flags;		/* flags */
#define	XFS_BTCUR_BPRV_WASDEL	1			/* was delayed */
		} b;
		struct {			/* needed for INO */
			struct xfs_buf	*agbp;	/* agi buffer pointer */
			xfs_agnumber_t	agno;	/* ag number */
		} i;
	}		bc_private;	/* per-btree type data */
} xfs_btree_cur_t;

#define	XFS_BTREE_NOERROR	0
#define	XFS_BTREE_ERROR		1

/*
 * Convert from buffer to btree block header.
 */
186 187 188 189
#define	XFS_BUF_TO_BLOCK(bp)	((xfs_btree_block_t *)XFS_BUF_PTR(bp))
#define	XFS_BUF_TO_LBLOCK(bp)	((xfs_btree_lblock_t *)XFS_BUF_PTR(bp))
#define	XFS_BUF_TO_SBLOCK(bp)	((xfs_btree_sblock_t *)XFS_BUF_PTR(bp))

L
Linus Torvalds 已提交
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 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245

#ifdef __KERNEL__

#ifdef DEBUG
/*
 * Debug routine: check that block header is ok.
 */
void
xfs_btree_check_block(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	xfs_btree_block_t	*block,	/* generic btree block pointer */
	int			level,	/* level of the btree block */
	struct xfs_buf		*bp);	/* buffer containing block, if any */

/*
 * Debug routine: check that keys are in the right order.
 */
void
xfs_btree_check_key(
	xfs_btnum_t		btnum,	/* btree identifier */
	void			*ak1,	/* pointer to left (lower) key */
	void			*ak2);	/* pointer to right (higher) key */

/*
 * Debug routine: check that records are in the right order.
 */
void
xfs_btree_check_rec(
	xfs_btnum_t		btnum,	/* btree identifier */
	void			*ar1,	/* pointer to left (lower) record */
	void			*ar2);	/* pointer to right (higher) record */
#else
#define	xfs_btree_check_block(a,b,c,d)
#define	xfs_btree_check_key(a,b,c)
#define	xfs_btree_check_rec(a,b,c)
#endif	/* DEBUG */

/*
 * Checking routine: check that long form block header is ok.
 */
int					/* error (0 or EFSCORRUPTED) */
xfs_btree_check_lblock(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	xfs_btree_lblock_t	*block,	/* btree long form block pointer */
	int			level,	/* level of the btree block */
	struct xfs_buf		*bp);	/* buffer containing block, if any */

/*
 * Checking routine: check that (long) pointer is ok.
 */
int					/* error (0 or EFSCORRUPTED) */
xfs_btree_check_lptr(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	xfs_dfsbno_t		ptr,	/* btree block disk address */
	int			level);	/* btree block level */

246 247 248
#define xfs_btree_check_lptr_disk(cur, ptr, level) \
	xfs_btree_check_lptr(cur, INT_GET(ptr, ARCH_CONVERT), level)

L
Linus Torvalds 已提交
249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448
/*
 * Checking routine: check that short form block header is ok.
 */
int					/* error (0 or EFSCORRUPTED) */
xfs_btree_check_sblock(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	xfs_btree_sblock_t	*block,	/* btree short form block pointer */
	int			level,	/* level of the btree block */
	struct xfs_buf		*bp);	/* buffer containing block */

/*
 * Checking routine: check that (short) pointer is ok.
 */
int					/* error (0 or EFSCORRUPTED) */
xfs_btree_check_sptr(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	xfs_agblock_t		ptr,	/* btree block disk address */
	int			level);	/* btree block level */

/*
 * Delete the btree cursor.
 */
void
xfs_btree_del_cursor(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			error);	/* del because of error */

/*
 * Duplicate the btree cursor.
 * Allocate a new one, copy the record, re-get the buffers.
 */
int					/* error */
xfs_btree_dup_cursor(
	xfs_btree_cur_t		*cur,	/* input cursor */
	xfs_btree_cur_t		**ncur);/* output cursor */

/*
 * Change the cursor to point to the first record in the current block
 * at the given level.  Other levels are unaffected.
 */
int					/* success=1, failure=0 */
xfs_btree_firstrec(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			level);	/* level to change */

/*
 * Get a buffer for the block, return it with no data read.
 * Long-form addressing.
 */
struct xfs_buf *				/* buffer for fsbno */
xfs_btree_get_bufl(
	struct xfs_mount	*mp,	/* file system mount point */
	struct xfs_trans	*tp,	/* transaction pointer */
	xfs_fsblock_t		fsbno,	/* file system block number */
	uint			lock);	/* lock flags for get_buf */

/*
 * Get a buffer for the block, return it with no data read.
 * Short-form addressing.
 */
struct xfs_buf *				/* buffer for agno/agbno */
xfs_btree_get_bufs(
	struct xfs_mount	*mp,	/* file system mount point */
	struct xfs_trans	*tp,	/* transaction pointer */
	xfs_agnumber_t		agno,	/* allocation group number */
	xfs_agblock_t		agbno,	/* allocation group block number */
	uint			lock);	/* lock flags for get_buf */

/*
 * Allocate a new btree cursor.
 * The cursor is either for allocation (A) or bmap (B).
 */
xfs_btree_cur_t *			/* new btree cursor */
xfs_btree_init_cursor(
	struct xfs_mount	*mp,	/* file system mount point */
	struct xfs_trans	*tp,	/* transaction pointer */
	struct xfs_buf		*agbp,	/* (A only) buffer for agf structure */
	xfs_agnumber_t		agno,	/* (A only) allocation group number */
	xfs_btnum_t		btnum,	/* btree identifier */
	struct xfs_inode	*ip,	/* (B only) inode owning the btree */
	int			whichfork); /* (B only) data/attr fork */

/*
 * Check for the cursor referring to the last block at the given level.
 */
int					/* 1=is last block, 0=not last block */
xfs_btree_islastblock(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			level);	/* level to check */

/*
 * Change the cursor to point to the last record in the current block
 * at the given level.  Other levels are unaffected.
 */
int					/* success=1, failure=0 */
xfs_btree_lastrec(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			level);	/* level to change */

/*
 * Compute first and last byte offsets for the fields given.
 * Interprets the offsets table, which contains struct field offsets.
 */
void
xfs_btree_offsets(
	__int64_t		fields,	/* bitmask of fields */
	const short		*offsets,/* table of field offsets */
	int			nbits,	/* number of bits to inspect */
	int			*first,	/* output: first byte offset */
	int			*last);	/* output: last byte offset */

/*
 * Get a buffer for the block, return it read in.
 * Long-form addressing.
 */
int					/* error */
xfs_btree_read_bufl(
	struct xfs_mount	*mp,	/* file system mount point */
	struct xfs_trans	*tp,	/* transaction pointer */
	xfs_fsblock_t		fsbno,	/* file system block number */
	uint			lock,	/* lock flags for read_buf */
	struct xfs_buf		**bpp,	/* buffer for fsbno */
	int			refval);/* ref count value for buffer */

/*
 * Get a buffer for the block, return it read in.
 * Short-form addressing.
 */
int					/* error */
xfs_btree_read_bufs(
	struct xfs_mount	*mp,	/* file system mount point */
	struct xfs_trans	*tp,	/* transaction pointer */
	xfs_agnumber_t		agno,	/* allocation group number */
	xfs_agblock_t		agbno,	/* allocation group block number */
	uint			lock,	/* lock flags for read_buf */
	struct xfs_buf		**bpp,	/* buffer for agno/agbno */
	int			refval);/* ref count value for buffer */

/*
 * Read-ahead the block, don't wait for it, don't return a buffer.
 * Long-form addressing.
 */
void					/* error */
xfs_btree_reada_bufl(
	struct xfs_mount	*mp,	/* file system mount point */
	xfs_fsblock_t		fsbno,	/* file system block number */
	xfs_extlen_t		count);	/* count of filesystem blocks */

/*
 * Read-ahead the block, don't wait for it, don't return a buffer.
 * Short-form addressing.
 */
void					/* error */
xfs_btree_reada_bufs(
	struct xfs_mount	*mp,	/* file system mount point */
	xfs_agnumber_t		agno,	/* allocation group number */
	xfs_agblock_t		agbno,	/* allocation group block number */
	xfs_extlen_t		count);	/* count of filesystem blocks */

/*
 * Read-ahead btree blocks, at the given level.
 * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
 */
int					/* readahead block count */
xfs_btree_readahead_core(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			lev,	/* level in btree */
	int			lr);	/* left/right bits */

static inline int			/* readahead block count */
xfs_btree_readahead(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			lev,	/* level in btree */
	int			lr)	/* left/right bits */
{
	if ((cur->bc_ra[lev] | lr) == cur->bc_ra[lev])
		return 0;

	return xfs_btree_readahead_core(cur, lev, lr);
}


/*
 * Set the buffer for level "lev" in the cursor to bp, releasing
 * any previous buffer.
 */
void
xfs_btree_setbuf(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			lev,	/* level in btree */
	struct xfs_buf		*bp);	/* new buffer to set */

#endif	/* __KERNEL__ */


/*
 * Min and max functions for extlen, agblock, fileoff, and filblks types.
 */
#define	XFS_EXTLEN_MIN(a,b)	\
	((xfs_extlen_t)(a) < (xfs_extlen_t)(b) ? \
449
		(xfs_extlen_t)(a) : (xfs_extlen_t)(b))
L
Linus Torvalds 已提交
450 451
#define	XFS_EXTLEN_MAX(a,b)	\
	((xfs_extlen_t)(a) > (xfs_extlen_t)(b) ? \
452
		(xfs_extlen_t)(a) : (xfs_extlen_t)(b))
L
Linus Torvalds 已提交
453 454
#define	XFS_AGBLOCK_MIN(a,b)	\
	((xfs_agblock_t)(a) < (xfs_agblock_t)(b) ? \
455
		(xfs_agblock_t)(a) : (xfs_agblock_t)(b))
L
Linus Torvalds 已提交
456 457
#define	XFS_AGBLOCK_MAX(a,b)	\
	((xfs_agblock_t)(a) > (xfs_agblock_t)(b) ? \
458
		(xfs_agblock_t)(a) : (xfs_agblock_t)(b))
L
Linus Torvalds 已提交
459 460
#define	XFS_FILEOFF_MIN(a,b)	\
	((xfs_fileoff_t)(a) < (xfs_fileoff_t)(b) ? \
461
		(xfs_fileoff_t)(a) : (xfs_fileoff_t)(b))
L
Linus Torvalds 已提交
462 463
#define	XFS_FILEOFF_MAX(a,b)	\
	((xfs_fileoff_t)(a) > (xfs_fileoff_t)(b) ? \
464
		(xfs_fileoff_t)(a) : (xfs_fileoff_t)(b))
L
Linus Torvalds 已提交
465 466
#define	XFS_FILBLKS_MIN(a,b)	\
	((xfs_filblks_t)(a) < (xfs_filblks_t)(b) ? \
467
		(xfs_filblks_t)(a) : (xfs_filblks_t)(b))
L
Linus Torvalds 已提交
468 469
#define	XFS_FILBLKS_MAX(a,b)	\
	((xfs_filblks_t)(a) > (xfs_filblks_t)(b) ? \
470 471
		(xfs_filblks_t)(a) : (xfs_filblks_t)(b))

L
Linus Torvalds 已提交
472 473
#define	XFS_FSB_SANITY_CHECK(mp,fsb)	\
	(XFS_FSB_TO_AGNO(mp, fsb) < mp->m_sb.sb_agcount && \
474
		XFS_FSB_TO_AGBNO(mp, fsb) < mp->m_sb.sb_agblocks)
L
Linus Torvalds 已提交
475 476

#endif	/* __XFS_BTREE_H__ */