xfs_btree.h 17.5 KB
Newer Older
1
/* SPDX-License-Identifier: GPL-2.0 */
Linus Torvalds's avatar
Linus Torvalds committed
2
/*
3 4
 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
 * All Rights Reserved.
Linus Torvalds's avatar
Linus Torvalds committed
5 6 7 8 9 10 11 12
 */
#ifndef __XFS_BTREE_H__
#define	__XFS_BTREE_H__

struct xfs_buf;
struct xfs_inode;
struct xfs_mount;
struct xfs_trans;
13
struct xfs_ifork;
Linus Torvalds's avatar
Linus Torvalds committed
14

15 16
extern kmem_zone_t	*xfs_btree_cur_zone;

17 18 19 20 21 22 23 24 25 26 27
/*
 * Generic key, ptr and record wrapper structures.
 *
 * These are disk format structures, and are converted where necessary
 * by the btree specific code that needs to interpret them.
 */
union xfs_btree_ptr {
	__be32			s;	/* short form ptr */
	__be64			l;	/* long form ptr */
};

28
/*
29 30 31
 * The in-core btree key.  Overlapping btrees actually store two keys
 * per pointer, so we reserve enough memory to hold both.  The __*bigkey
 * items should never be accessed directly.
32
 */
33
union xfs_btree_key {
34 35 36 37
	struct xfs_bmbt_key		bmbt;
	xfs_bmdr_key_t			bmbr;	/* bmbt root block */
	xfs_alloc_key_t			alloc;
	struct xfs_inobt_key		inobt;
38 39
	struct xfs_rmap_key		rmap;
	struct xfs_rmap_key		__rmap_bigkey[2];
40
	struct xfs_refcount_key		refc;
41 42
};

43
union xfs_btree_rec {
44 45 46 47 48
	struct xfs_bmbt_rec		bmbt;
	xfs_bmdr_rec_t			bmbr;	/* bmbt root block */
	struct xfs_alloc_rec		alloc;
	struct xfs_inobt_rec		inobt;
	struct xfs_rmap_rec		rmap;
49
	struct xfs_refcount_rec		refc;
50 51
};

52 53 54 55 56 57 58 59 60 61 62
/*
 * 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)
63
#define	XFS_BTNUM_FINO	((xfs_btnum_t)XFS_BTNUM_FINOi)
64
#define	XFS_BTNUM_RMAP	((xfs_btnum_t)XFS_BTNUM_RMAPi)
65
#define	XFS_BTNUM_REFC	((xfs_btnum_t)XFS_BTNUM_REFCi)
66

67
uint32_t xfs_btree_magic(int crc, xfs_btnum_t btnum);
68

Linus Torvalds's avatar
Linus Torvalds committed
69 70 71
/*
 * For logging record fields.
 */
72 73 74 75 76 77 78 79 80
#define	XFS_BB_MAGIC		(1 << 0)
#define	XFS_BB_LEVEL		(1 << 1)
#define	XFS_BB_NUMRECS		(1 << 2)
#define	XFS_BB_LEFTSIB		(1 << 3)
#define	XFS_BB_RIGHTSIB		(1 << 4)
#define	XFS_BB_BLKNO		(1 << 5)
#define	XFS_BB_LSN		(1 << 6)
#define	XFS_BB_UUID		(1 << 7)
#define	XFS_BB_OWNER		(1 << 8)
Linus Torvalds's avatar
Linus Torvalds committed
81 82
#define	XFS_BB_NUM_BITS		5
#define	XFS_BB_ALL_BITS		((1 << XFS_BB_NUM_BITS) - 1)
83
#define	XFS_BB_NUM_BITS_CRC	9
84
#define	XFS_BB_ALL_BITS_CRC	((1 << XFS_BB_NUM_BITS_CRC) - 1)
Linus Torvalds's avatar
Linus Torvalds committed
85

86 87 88
/*
 * Generic stats interface
 */
89
#define XFS_BTREE_STATS_INC(cur, stat)	\
90 91 92
	XFS_STATS_INC_OFF((cur)->bc_mp, (cur)->bc_statoff + __XBTS_ ## stat)
#define XFS_BTREE_STATS_ADD(cur, stat, val)	\
	XFS_STATS_ADD_OFF((cur)->bc_mp, (cur)->bc_statoff + __XBTS_ ## stat, val)
Linus Torvalds's avatar
Linus Torvalds committed
93

94
#define	XFS_BTREE_MAXLEVELS	9	/* max of all btrees */
Linus Torvalds's avatar
Linus Torvalds committed
95

96
struct xfs_btree_ops {
97 98 99 100
	/* size of the key and record structures */
	size_t	key_len;
	size_t	rec_len;

101 102
	/* cursor operations */
	struct xfs_btree_cur *(*dup_cursor)(struct xfs_btree_cur *);
103 104
	void	(*update_cursor)(struct xfs_btree_cur *src,
				 struct xfs_btree_cur *dst);
105

106 107
	/* update btree root pointer */
	void	(*set_root)(struct xfs_btree_cur *cur,
108
			    union xfs_btree_ptr *nptr, int level_change);
109

110 111 112 113
	/* block allocation / freeing */
	int	(*alloc_block)(struct xfs_btree_cur *cur,
			       union xfs_btree_ptr *start_bno,
			       union xfs_btree_ptr *new_bno,
114
			       int *stat);
115
	int	(*free_block)(struct xfs_btree_cur *cur, struct xfs_buf *bp);
116

117 118 119 120 121 122
	/* update last record information */
	void	(*update_lastrec)(struct xfs_btree_cur *cur,
				  struct xfs_btree_block *block,
				  union xfs_btree_rec *rec,
				  int ptr, int reason);

123
	/* records in block/level */
124
	int	(*get_minrecs)(struct xfs_btree_cur *cur, int level);
125 126
	int	(*get_maxrecs)(struct xfs_btree_cur *cur, int level);

127 128 129
	/* records on disk.  Matter for the root in inode case. */
	int	(*get_dmaxrecs)(struct xfs_btree_cur *cur, int level);

130 131 132
	/* init values of btree structures */
	void	(*init_key_from_rec)(union xfs_btree_key *key,
				     union xfs_btree_rec *rec);
133 134
	void	(*init_rec_from_cur)(struct xfs_btree_cur *cur,
				     union xfs_btree_rec *rec);
135 136
	void	(*init_ptr_from_cur)(struct xfs_btree_cur *cur,
				     union xfs_btree_ptr *ptr);
137 138
	void	(*init_high_key_from_rec)(union xfs_btree_key *key,
					  union xfs_btree_rec *rec);
139 140

	/* difference between key value and cursor value */
141
	int64_t (*key_diff)(struct xfs_btree_cur *cur,
142 143
			      union xfs_btree_key *key);

144 145 146 147
	/*
	 * Difference between key2 and key1 -- positive if key1 > key2,
	 * negative if key1 < key2, and zero if equal.
	 */
148
	int64_t (*diff_two_keys)(struct xfs_btree_cur *cur,
149 150 151
				   union xfs_btree_key *key1,
				   union xfs_btree_key *key2);

152
	const struct xfs_buf_ops	*buf_ops;
153

154 155 156 157 158 159 160 161 162
	/* check that k1 is lower than k2 */
	int	(*keys_inorder)(struct xfs_btree_cur *cur,
				union xfs_btree_key *k1,
				union xfs_btree_key *k2);

	/* check that r1 is lower than r2 */
	int	(*recs_inorder)(struct xfs_btree_cur *cur,
				union xfs_btree_rec *r1,
				union xfs_btree_rec *r2);
163 164
};

165 166 167 168
/*
 * Reasons for the update_lastrec method to be called.
 */
#define LASTREC_UPDATE	0
169
#define LASTREC_INSREC	1
170
#define LASTREC_DELREC	2
171 172


173 174 175 176
union xfs_btree_irec {
	struct xfs_alloc_rec_incore	a;
	struct xfs_bmbt_irec		b;
	struct xfs_inobt_rec_incore	i;
177
	struct xfs_rmap_irec		r;
178 179 180
	struct xfs_refcount_irec	rc;
};

181 182
/* Per-AG btree information. */
struct xfs_btree_cur_ag {
183 184 185 186
	union {
		struct xfs_buf		*agbp;
		struct xbtree_afakeroot	*afake;	/* for staging cursor */
	};
187 188 189 190 191 192 193 194 195 196
	xfs_agnumber_t		agno;
	union {
		struct {
			unsigned long nr_ops;	/* # record updates */
			int	shape_changes;	/* # of extent splits */
		} refc;
		struct {
			bool	active;		/* allocation cursor state */
		} abt;
	};
197 198 199 200 201
};

/* Btree-in-inode cursor information */
struct xfs_btree_cur_ino {
	struct xfs_inode		*ip;
202
	struct xbtree_ifakeroot		*ifake;	/* for staging cursor */
203 204 205 206 207 208 209 210 211 212 213
	int				allocated;
	short				forksize;
	char				whichfork;
	char				flags;
/* We are converting a delalloc reservation */
#define	XFS_BTCUR_BMBT_WASDEL		(1 << 0)

/* For extent swap, ignore owner check in verifier */
#define	XFS_BTCUR_BMBT_INVALID_OWNER	(1 << 1)
};

Linus Torvalds's avatar
Linus Torvalds committed
214 215 216 217 218 219 220 221
/*
 * 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 */
222
	const struct xfs_btree_ops *bc_ops;
223
	uint			bc_flags; /* btree features - below */
224
	union xfs_btree_irec	bc_rec;	/* current insert/search record value */
Linus Torvalds's avatar
Linus Torvalds committed
225 226
	struct xfs_buf	*bc_bufs[XFS_BTREE_MAXLEVELS];	/* buf ptr per level */
	int		bc_ptrs[XFS_BTREE_MAXLEVELS];	/* key/record # */
227
	uint8_t		bc_ra[XFS_BTREE_MAXLEVELS];	/* readahead bits */
Linus Torvalds's avatar
Linus Torvalds committed
228 229
#define	XFS_BTCUR_LEFTRA	1	/* left sibling has been read-ahead */
#define	XFS_BTCUR_RIGHTRA	2	/* right sibling has been read-ahead */
230 231
	uint8_t		bc_nlevels;	/* number of levels in the tree */
	uint8_t		bc_blocklog;	/* log2(blocksize) of btree blocks */
Linus Torvalds's avatar
Linus Torvalds committed
232
	xfs_btnum_t	bc_btnum;	/* identifies which btree type */
233
	int		bc_statoff;	/* offset of btre stats array */
Linus Torvalds's avatar
Linus Torvalds committed
234
	union {
235 236 237
		struct xfs_btree_cur_ag	bc_ag;
		struct xfs_btree_cur_ino bc_ino;
	};
Linus Torvalds's avatar
Linus Torvalds committed
238 239
} xfs_btree_cur_t;

240
/* cursor flags */
241
#define XFS_BTREE_LONG_PTRS		(1<<0)	/* pointers are 64bits long */
242
#define XFS_BTREE_ROOT_IN_INODE		(1<<1)	/* root may be variable size */
243
#define XFS_BTREE_LASTREC_UPDATE	(1<<2)	/* track last rec externally */
244
#define XFS_BTREE_CRC_BLOCKS		(1<<3)	/* uses extended btree blocks */
245
#define XFS_BTREE_OVERLAPPING		(1<<4)	/* overlapping intervals */
246 247 248 249 250 251
/*
 * The root of this btree is a fakeroot structure so that we can stage a btree
 * rebuild without leaving it accessible via primary metadata.  The ops struct
 * is dynamically allocated and must be freed when the cursor is deleted.
 */
#define XFS_BTREE_STAGING		(1<<5)
252 253


Linus Torvalds's avatar
Linus Torvalds committed
254 255 256 257 258 259
#define	XFS_BTREE_NOERROR	0
#define	XFS_BTREE_ERROR		1

/*
 * Convert from buffer to btree block header.
 */
260
#define	XFS_BUF_TO_BLOCK(bp)	((struct xfs_btree_block *)((bp)->b_addr))
Linus Torvalds's avatar
Linus Torvalds committed
261

262 263 264 265 266 267 268 269
/*
 * Internal long and short btree block checks.  They return NULL if the
 * block is ok or the address of the failed check otherwise.
 */
xfs_failaddr_t __xfs_btree_check_lblock(struct xfs_btree_cur *cur,
		struct xfs_btree_block *block, int level, struct xfs_buf *bp);
xfs_failaddr_t __xfs_btree_check_sblock(struct xfs_btree_cur *cur,
		struct xfs_btree_block *block, int level, struct xfs_buf *bp);
Linus Torvalds's avatar
Linus Torvalds committed
270 271

/*
272
 * Check that block header is ok.
Linus Torvalds's avatar
Linus Torvalds committed
273
 */
274 275 276 277
int
xfs_btree_check_block(
	struct xfs_btree_cur	*cur,	/* btree cursor */
	struct xfs_btree_block	*block,	/* generic btree block pointer */
Linus Torvalds's avatar
Linus Torvalds committed
278 279 280 281
	int			level,	/* level of the btree block */
	struct xfs_buf		*bp);	/* buffer containing block, if any */

/*
282
 * Check that (long) pointer is ok.
Linus Torvalds's avatar
Linus Torvalds committed
283
 */
284
bool					/* error (0 or EFSCORRUPTED) */
Linus Torvalds's avatar
Linus Torvalds committed
285
xfs_btree_check_lptr(
286
	struct xfs_btree_cur	*cur,	/* btree cursor */
287 288 289 290 291 292 293 294 295 296
	xfs_fsblock_t		fsbno,	/* btree block disk address */
	int			level);	/* btree block level */

/*
 * Check that (short) pointer is ok.
 */
bool					/* error (0 or EFSCORRUPTED) */
xfs_btree_check_sptr(
	struct xfs_btree_cur	*cur,	/* btree cursor */
	xfs_agblock_t		agbno,	/* btree block disk address */
Linus Torvalds's avatar
Linus Torvalds committed
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
	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 */

/*
 * Compute first and last byte offsets for the fields given.
 * Interprets the offsets table, which contains struct field offsets.
 */
void
xfs_btree_offsets(
322
	int64_t			fields,	/* bitmask of fields */
Linus Torvalds's avatar
Linus Torvalds committed
323 324 325 326 327 328 329 330 331 332 333 334 335 336 337
	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 */
	struct xfs_buf		**bpp,	/* buffer for fsbno */
338
	int			refval,	/* ref count value for buffer */
339
	const struct xfs_buf_ops *ops);
Linus Torvalds's avatar
Linus Torvalds committed
340 341 342 343 344 345 346 347 348

/*
 * 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 */
349
	xfs_extlen_t		count,	/* count of filesystem blocks */
350
	const struct xfs_buf_ops *ops);
Linus Torvalds's avatar
Linus Torvalds committed
351 352 353 354 355 356 357 358 359 360

/*
 * 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 */
361
	xfs_extlen_t		count,	/* count of filesystem blocks */
362
	const struct xfs_buf_ops *ops);
Linus Torvalds's avatar
Linus Torvalds committed
363

364 365 366 367 368 369 370
/*
 * Initialise a new btree block header
 */
void
xfs_btree_init_block(
	struct xfs_mount *mp,
	struct xfs_buf	*bp,
371
	xfs_btnum_t	btnum,
372 373
	__u16		level,
	__u16		numrecs,
374
	__u64		owner);
375

376 377 378 379 380
void
xfs_btree_init_block_int(
	struct xfs_mount	*mp,
	struct xfs_btree_block	*buf,
	xfs_daddr_t		blkno,
381
	xfs_btnum_t		btnum,
382 383 384 385 386
	__u16			level,
	__u16			numrecs,
	__u64			owner,
	unsigned int		flags);

387 388 389 390
/*
 * Common btree core entry points.
 */
int xfs_btree_increment(struct xfs_btree_cur *, int, int *);
391
int xfs_btree_decrement(struct xfs_btree_cur *, int, int *);
392
int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *);
393
int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *);
394
int xfs_btree_new_iroot(struct xfs_btree_cur *, int *, int *);
395
int xfs_btree_insert(struct xfs_btree_cur *, int *);
396
int xfs_btree_delete(struct xfs_btree_cur *, int *);
397
int xfs_btree_get_rec(struct xfs_btree_cur *, union xfs_btree_rec **, int *);
398
int xfs_btree_change_owner(struct xfs_btree_cur *cur, uint64_t new_owner,
399
			   struct list_head *buffer_list);
400

401 402 403 404 405 406 407 408
/*
 * btree block CRC helpers
 */
void xfs_btree_lblock_calc_crc(struct xfs_buf *);
bool xfs_btree_lblock_verify_crc(struct xfs_buf *);
void xfs_btree_sblock_calc_crc(struct xfs_buf *);
bool xfs_btree_sblock_verify_crc(struct xfs_buf *);

409 410 411 412 413 414
/*
 * Internal btree helpers also used by xfs_bmap.c.
 */
void xfs_btree_log_block(struct xfs_btree_cur *, struct xfs_buf *, int);
void xfs_btree_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int, int);

415 416 417
/*
 * Helpers.
 */
418 419 420 421 422
static inline int xfs_btree_get_numrecs(struct xfs_btree_block *block)
{
	return be16_to_cpu(block->bb_numrecs);
}

423
static inline void xfs_btree_set_numrecs(struct xfs_btree_block *block,
424
		uint16_t numrecs)
425 426 427 428
{
	block->bb_numrecs = cpu_to_be16(numrecs);
}

429 430 431 432 433
static inline int xfs_btree_get_level(struct xfs_btree_block *block)
{
	return be16_to_cpu(block->bb_level);
}

Linus Torvalds's avatar
Linus Torvalds committed
434 435 436 437

/*
 * Min and max functions for extlen, agblock, fileoff, and filblks types.
 */
438 439 440 441 442 443 444 445
#define	XFS_EXTLEN_MIN(a,b)	min_t(xfs_extlen_t, (a), (b))
#define	XFS_EXTLEN_MAX(a,b)	max_t(xfs_extlen_t, (a), (b))
#define	XFS_AGBLOCK_MIN(a,b)	min_t(xfs_agblock_t, (a), (b))
#define	XFS_AGBLOCK_MAX(a,b)	max_t(xfs_agblock_t, (a), (b))
#define	XFS_FILEOFF_MIN(a,b)	min_t(xfs_fileoff_t, (a), (b))
#define	XFS_FILEOFF_MAX(a,b)	max_t(xfs_fileoff_t, (a), (b))
#define	XFS_FILBLKS_MIN(a,b)	min_t(xfs_filblks_t, (a), (b))
#define	XFS_FILBLKS_MAX(a,b)	max_t(xfs_filblks_t, (a), (b))
446

447 448 449 450 451 452 453
xfs_failaddr_t xfs_btree_sblock_v5hdr_verify(struct xfs_buf *bp);
xfs_failaddr_t xfs_btree_sblock_verify(struct xfs_buf *bp,
		unsigned int max_recs);
xfs_failaddr_t xfs_btree_lblock_v5hdr_verify(struct xfs_buf *bp,
		uint64_t owner);
xfs_failaddr_t xfs_btree_lblock_verify(struct xfs_buf *bp,
		unsigned int max_recs);
454

455
uint xfs_btree_compute_maxlevels(uint *limits, unsigned long len);
456
unsigned long long xfs_btree_calc_size(uint *limits, unsigned long long len);
457

458 459 460 461 462 463 464
/*
 * Return codes for the query range iterator function are 0 to continue
 * iterating, and non-zero to stop iterating.  Any non-zero value will be
 * passed up to the _query_range caller.  The special value -ECANCELED can be
 * used to stop iteration, because _query_range never generates that error
 * code on its own.
 */
465 466 467 468 469 470
typedef int (*xfs_btree_query_range_fn)(struct xfs_btree_cur *cur,
		union xfs_btree_rec *rec, void *priv);

int xfs_btree_query_range(struct xfs_btree_cur *cur,
		union xfs_btree_irec *low_rec, union xfs_btree_irec *high_rec,
		xfs_btree_query_range_fn fn, void *priv);
471 472
int xfs_btree_query_all(struct xfs_btree_cur *cur, xfs_btree_query_range_fn fn,
		void *priv);
473

474 475
typedef int (*xfs_btree_visit_blocks_fn)(struct xfs_btree_cur *cur, int level,
		void *data);
476 477 478 479 480 481 482
/* Visit record blocks. */
#define XFS_BTREE_VISIT_RECORDS		(1 << 0)
/* Visit leaf blocks. */
#define XFS_BTREE_VISIT_LEAVES		(1 << 1)
/* Visit all blocks. */
#define XFS_BTREE_VISIT_ALL		(XFS_BTREE_VISIT_RECORDS | \
					 XFS_BTREE_VISIT_LEAVES)
483
int xfs_btree_visit_blocks(struct xfs_btree_cur *cur,
484
		xfs_btree_visit_blocks_fn fn, unsigned int flags, void *data);
485

486 487
int xfs_btree_count_blocks(struct xfs_btree_cur *cur, xfs_extlen_t *blocks);

488 489 490 491 492 493 494 495 496 497 498 499
union xfs_btree_rec *xfs_btree_rec_addr(struct xfs_btree_cur *cur, int n,
		struct xfs_btree_block *block);
union xfs_btree_key *xfs_btree_key_addr(struct xfs_btree_cur *cur, int n,
		struct xfs_btree_block *block);
union xfs_btree_key *xfs_btree_high_key_addr(struct xfs_btree_cur *cur, int n,
		struct xfs_btree_block *block);
union xfs_btree_ptr *xfs_btree_ptr_addr(struct xfs_btree_cur *cur, int n,
		struct xfs_btree_block *block);
int xfs_btree_lookup_get_block(struct xfs_btree_cur *cur, int level,
		union xfs_btree_ptr *pp, struct xfs_btree_block **blkp);
struct xfs_btree_block *xfs_btree_get_block(struct xfs_btree_cur *cur,
		int level, struct xfs_buf **bpp);
500 501 502 503 504 505 506
bool xfs_btree_ptr_is_null(struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr);
int64_t xfs_btree_diff_two_ptrs(struct xfs_btree_cur *cur,
				const union xfs_btree_ptr *a,
				const union xfs_btree_ptr *b);
void xfs_btree_get_sibling(struct xfs_btree_cur *cur,
			   struct xfs_btree_block *block,
			   union xfs_btree_ptr *ptr, int lr);
507 508 509 510
void xfs_btree_get_keys(struct xfs_btree_cur *cur,
		struct xfs_btree_block *block, union xfs_btree_key *key);
union xfs_btree_key *xfs_btree_high_key_from_key(struct xfs_btree_cur *cur,
		union xfs_btree_key *key);
511 512
int xfs_btree_has_record(struct xfs_btree_cur *cur, union xfs_btree_irec *low,
		union xfs_btree_irec *high, bool *exists);
513
bool xfs_btree_has_more_records(struct xfs_btree_cur *cur);
514
struct xfs_ifork *xfs_btree_ifork_ptr(struct xfs_btree_cur *cur);
515

516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532
/* Does this cursor point to the last block in the given level? */
static inline bool
xfs_btree_islastblock(
	xfs_btree_cur_t		*cur,
	int			level)
{
	struct xfs_btree_block	*block;
	struct xfs_buf		*bp;

	block = xfs_btree_get_block(cur, level, &bp);
	ASSERT(block && xfs_btree_check_block(cur, block, level, bp) == 0);

	if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
		return block->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK);
	return block->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK);
}

533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548
void xfs_btree_set_ptr_null(struct xfs_btree_cur *cur,
		union xfs_btree_ptr *ptr);
int xfs_btree_get_buf_block(struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr,
		struct xfs_btree_block **block, struct xfs_buf **bpp);
void xfs_btree_set_sibling(struct xfs_btree_cur *cur,
		struct xfs_btree_block *block, union xfs_btree_ptr *ptr,
		int lr);
void xfs_btree_init_block_cur(struct xfs_btree_cur *cur,
		struct xfs_buf *bp, int level, int numrecs);
void xfs_btree_copy_ptrs(struct xfs_btree_cur *cur,
		union xfs_btree_ptr *dst_ptr,
		const union xfs_btree_ptr *src_ptr, int numptrs);
void xfs_btree_copy_keys(struct xfs_btree_cur *cur,
		union xfs_btree_key *dst_key, union xfs_btree_key *src_key,
		int numkeys);

Linus Torvalds's avatar
Linus Torvalds committed
549
#endif	/* __XFS_BTREE_H__ */