1 /* SPDX-License-Identifier: GPL-2.0 */
2 /*
3  * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
4  * All Rights Reserved.
5  */
6 #ifndef __XFS_BTREE_H__
7 #define	__XFS_BTREE_H__
8 
9 struct xfs_buf;
10 struct xfs_inode;
11 struct xfs_mount;
12 struct xfs_trans;
13 struct xfs_ifork;
14 struct xfs_perag;
15 
16 /*
17  * Generic key, ptr and record wrapper structures.
18  *
19  * These are disk format structures, and are converted where necessary
20  * by the btree specific code that needs to interpret them.
21  */
22 union xfs_btree_ptr {
23 	__be32			s;	/* short form ptr */
24 	__be64			l;	/* long form ptr */
25 };
26 
27 /*
28  * The in-core btree key.  Overlapping btrees actually store two keys
29  * per pointer, so we reserve enough memory to hold both.  The __*bigkey
30  * items should never be accessed directly.
31  */
32 union xfs_btree_key {
33 	struct xfs_bmbt_key		bmbt;
34 	xfs_bmdr_key_t			bmbr;	/* bmbt root block */
35 	xfs_alloc_key_t			alloc;
36 	struct xfs_inobt_key		inobt;
37 	struct xfs_rmap_key		rmap;
38 	struct xfs_rmap_key		__rmap_bigkey[2];
39 	struct xfs_refcount_key		refc;
40 };
41 
42 union xfs_btree_rec {
43 	struct xfs_bmbt_rec		bmbt;
44 	xfs_bmdr_rec_t			bmbr;	/* bmbt root block */
45 	struct xfs_alloc_rec		alloc;
46 	struct xfs_inobt_rec		inobt;
47 	struct xfs_rmap_rec		rmap;
48 	struct xfs_refcount_rec		refc;
49 };
50 
51 /*
52  * This nonsense is to make -wlint happy.
53  */
54 #define	XFS_LOOKUP_EQ	((xfs_lookup_t)XFS_LOOKUP_EQi)
55 #define	XFS_LOOKUP_LE	((xfs_lookup_t)XFS_LOOKUP_LEi)
56 #define	XFS_LOOKUP_GE	((xfs_lookup_t)XFS_LOOKUP_GEi)
57 
58 #define	XFS_BTNUM_BNO	((xfs_btnum_t)XFS_BTNUM_BNOi)
59 #define	XFS_BTNUM_CNT	((xfs_btnum_t)XFS_BTNUM_CNTi)
60 #define	XFS_BTNUM_BMAP	((xfs_btnum_t)XFS_BTNUM_BMAPi)
61 #define	XFS_BTNUM_INO	((xfs_btnum_t)XFS_BTNUM_INOi)
62 #define	XFS_BTNUM_FINO	((xfs_btnum_t)XFS_BTNUM_FINOi)
63 #define	XFS_BTNUM_RMAP	((xfs_btnum_t)XFS_BTNUM_RMAPi)
64 #define	XFS_BTNUM_REFC	((xfs_btnum_t)XFS_BTNUM_REFCi)
65 
66 uint32_t xfs_btree_magic(int crc, xfs_btnum_t btnum);
67 
68 /*
69  * For logging record fields.
70  */
71 #define	XFS_BB_MAGIC		(1u << 0)
72 #define	XFS_BB_LEVEL		(1u << 1)
73 #define	XFS_BB_NUMRECS		(1u << 2)
74 #define	XFS_BB_LEFTSIB		(1u << 3)
75 #define	XFS_BB_RIGHTSIB		(1u << 4)
76 #define	XFS_BB_BLKNO		(1u << 5)
77 #define	XFS_BB_LSN		(1u << 6)
78 #define	XFS_BB_UUID		(1u << 7)
79 #define	XFS_BB_OWNER		(1u << 8)
80 #define	XFS_BB_NUM_BITS		5
81 #define	XFS_BB_ALL_BITS		((1u << XFS_BB_NUM_BITS) - 1)
82 #define	XFS_BB_NUM_BITS_CRC	9
83 #define	XFS_BB_ALL_BITS_CRC	((1u << XFS_BB_NUM_BITS_CRC) - 1)
84 
85 /*
86  * Generic stats interface
87  */
88 #define XFS_BTREE_STATS_INC(cur, stat)	\
89 	XFS_STATS_INC_OFF((cur)->bc_mp, (cur)->bc_statoff + __XBTS_ ## stat)
90 #define XFS_BTREE_STATS_ADD(cur, stat, val)	\
91 	XFS_STATS_ADD_OFF((cur)->bc_mp, (cur)->bc_statoff + __XBTS_ ## stat, val)
92 
93 enum xbtree_key_contig {
94 	XBTREE_KEY_GAP = 0,
95 	XBTREE_KEY_CONTIGUOUS,
96 	XBTREE_KEY_OVERLAP,
97 };
98 
99 /*
100  * Decide if these two numeric btree key fields are contiguous, overlapping,
101  * or if there's a gap between them.  @x should be the field from the high
102  * key and @y should be the field from the low key.
103  */
xbtree_key_contig(uint64_t x,uint64_t y)104 static inline enum xbtree_key_contig xbtree_key_contig(uint64_t x, uint64_t y)
105 {
106 	x++;
107 	if (x < y)
108 		return XBTREE_KEY_GAP;
109 	if (x == y)
110 		return XBTREE_KEY_CONTIGUOUS;
111 	return XBTREE_KEY_OVERLAP;
112 }
113 
114 struct xfs_btree_ops {
115 	/* size of the key and record structures */
116 	size_t	key_len;
117 	size_t	rec_len;
118 
119 	/* cursor operations */
120 	struct xfs_btree_cur *(*dup_cursor)(struct xfs_btree_cur *);
121 	void	(*update_cursor)(struct xfs_btree_cur *src,
122 				 struct xfs_btree_cur *dst);
123 
124 	/* update btree root pointer */
125 	void	(*set_root)(struct xfs_btree_cur *cur,
126 			    const union xfs_btree_ptr *nptr, int level_change);
127 
128 	/* block allocation / freeing */
129 	int	(*alloc_block)(struct xfs_btree_cur *cur,
130 			       const union xfs_btree_ptr *start_bno,
131 			       union xfs_btree_ptr *new_bno,
132 			       int *stat);
133 	int	(*free_block)(struct xfs_btree_cur *cur, struct xfs_buf *bp);
134 
135 	/* update last record information */
136 	void	(*update_lastrec)(struct xfs_btree_cur *cur,
137 				  const struct xfs_btree_block *block,
138 				  const union xfs_btree_rec *rec,
139 				  int ptr, int reason);
140 
141 	/* records in block/level */
142 	int	(*get_minrecs)(struct xfs_btree_cur *cur, int level);
143 	int	(*get_maxrecs)(struct xfs_btree_cur *cur, int level);
144 
145 	/* records on disk.  Matter for the root in inode case. */
146 	int	(*get_dmaxrecs)(struct xfs_btree_cur *cur, int level);
147 
148 	/* init values of btree structures */
149 	void	(*init_key_from_rec)(union xfs_btree_key *key,
150 				     const union xfs_btree_rec *rec);
151 	void	(*init_rec_from_cur)(struct xfs_btree_cur *cur,
152 				     union xfs_btree_rec *rec);
153 	void	(*init_ptr_from_cur)(struct xfs_btree_cur *cur,
154 				     union xfs_btree_ptr *ptr);
155 	void	(*init_high_key_from_rec)(union xfs_btree_key *key,
156 					  const union xfs_btree_rec *rec);
157 
158 	/* difference between key value and cursor value */
159 	int64_t (*key_diff)(struct xfs_btree_cur *cur,
160 			    const union xfs_btree_key *key);
161 
162 	/*
163 	 * Difference between key2 and key1 -- positive if key1 > key2,
164 	 * negative if key1 < key2, and zero if equal.  If the @mask parameter
165 	 * is non NULL, each key field to be used in the comparison must
166 	 * contain a nonzero value.
167 	 */
168 	int64_t (*diff_two_keys)(struct xfs_btree_cur *cur,
169 				 const union xfs_btree_key *key1,
170 				 const union xfs_btree_key *key2,
171 				 const union xfs_btree_key *mask);
172 
173 	const struct xfs_buf_ops	*buf_ops;
174 
175 	/* check that k1 is lower than k2 */
176 	int	(*keys_inorder)(struct xfs_btree_cur *cur,
177 				const union xfs_btree_key *k1,
178 				const union xfs_btree_key *k2);
179 
180 	/* check that r1 is lower than r2 */
181 	int	(*recs_inorder)(struct xfs_btree_cur *cur,
182 				const union xfs_btree_rec *r1,
183 				const union xfs_btree_rec *r2);
184 
185 	/*
186 	 * Are these two btree keys immediately adjacent?
187 	 *
188 	 * Given two btree keys @key1 and @key2, decide if it is impossible for
189 	 * there to be a third btree key K satisfying the relationship
190 	 * @key1 < K < @key2.  To determine if two btree records are
191 	 * immediately adjacent, @key1 should be the high key of the first
192 	 * record and @key2 should be the low key of the second record.
193 	 * If the @mask parameter is non NULL, each key field to be used in the
194 	 * comparison must contain a nonzero value.
195 	 */
196 	enum xbtree_key_contig (*keys_contiguous)(struct xfs_btree_cur *cur,
197 			       const union xfs_btree_key *key1,
198 			       const union xfs_btree_key *key2,
199 			       const union xfs_btree_key *mask);
200 };
201 
202 /*
203  * Reasons for the update_lastrec method to be called.
204  */
205 #define LASTREC_UPDATE	0
206 #define LASTREC_INSREC	1
207 #define LASTREC_DELREC	2
208 
209 
210 union xfs_btree_irec {
211 	struct xfs_alloc_rec_incore	a;
212 	struct xfs_bmbt_irec		b;
213 	struct xfs_inobt_rec_incore	i;
214 	struct xfs_rmap_irec		r;
215 	struct xfs_refcount_irec	rc;
216 };
217 
218 /* Per-AG btree information. */
219 struct xfs_btree_cur_ag {
220 	struct xfs_perag		*pag;
221 	union {
222 		struct xfs_buf		*agbp;
223 		struct xbtree_afakeroot	*afake;	/* for staging cursor */
224 	};
225 	union {
226 		struct {
227 			unsigned int	nr_ops;	/* # record updates */
228 			unsigned int	shape_changes;	/* # of extent splits */
229 		} refc;
230 		struct {
231 			bool		active;	/* allocation cursor state */
232 		} abt;
233 	};
234 };
235 
236 /* Btree-in-inode cursor information */
237 struct xfs_btree_cur_ino {
238 	struct xfs_inode		*ip;
239 	struct xbtree_ifakeroot		*ifake;	/* for staging cursor */
240 	int				allocated;
241 	short				forksize;
242 	char				whichfork;
243 	char				flags;
244 /* We are converting a delalloc reservation */
245 #define	XFS_BTCUR_BMBT_WASDEL		(1 << 0)
246 
247 /* For extent swap, ignore owner check in verifier */
248 #define	XFS_BTCUR_BMBT_INVALID_OWNER	(1 << 1)
249 };
250 
251 struct xfs_btree_level {
252 	/* buffer pointer */
253 	struct xfs_buf		*bp;
254 
255 	/* key/record number */
256 	uint16_t		ptr;
257 
258 	/* readahead info */
259 #define XFS_BTCUR_LEFTRA	(1 << 0) /* left sibling has been read-ahead */
260 #define XFS_BTCUR_RIGHTRA	(1 << 1) /* right sibling has been read-ahead */
261 	uint16_t		ra;
262 };
263 
264 /*
265  * Btree cursor structure.
266  * This collects all information needed by the btree code in one place.
267  */
268 struct xfs_btree_cur
269 {
270 	struct xfs_trans	*bc_tp;	/* transaction we're in, if any */
271 	struct xfs_mount	*bc_mp;	/* file system mount struct */
272 	const struct xfs_btree_ops *bc_ops;
273 	struct kmem_cache	*bc_cache; /* cursor cache */
274 	unsigned int		bc_flags; /* btree features - below */
275 	xfs_btnum_t		bc_btnum; /* identifies which btree type */
276 	union xfs_btree_irec	bc_rec;	/* current insert/search record value */
277 	uint8_t			bc_nlevels; /* number of levels in the tree */
278 	uint8_t			bc_maxlevels; /* maximum levels for this btree type */
279 	int			bc_statoff; /* offset of btree stats array */
280 
281 	/*
282 	 * Short btree pointers need an agno to be able to turn the pointers
283 	 * into physical addresses for IO, so the btree cursor switches between
284 	 * bc_ino and bc_ag based on whether XFS_BTREE_LONG_PTRS is set for the
285 	 * cursor.
286 	 */
287 	union {
288 		struct xfs_btree_cur_ag	bc_ag;
289 		struct xfs_btree_cur_ino bc_ino;
290 	};
291 
292 	/* Must be at the end of the struct! */
293 	struct xfs_btree_level	bc_levels[];
294 };
295 
296 /*
297  * Compute the size of a btree cursor that can handle a btree of a given
298  * height.  The bc_levels array handles node and leaf blocks, so its size
299  * is exactly nlevels.
300  */
301 static inline size_t
xfs_btree_cur_sizeof(unsigned int nlevels)302 xfs_btree_cur_sizeof(unsigned int nlevels)
303 {
304 	return struct_size_t(struct xfs_btree_cur, bc_levels, nlevels);
305 }
306 
307 /* cursor flags */
308 #define XFS_BTREE_LONG_PTRS		(1<<0)	/* pointers are 64bits long */
309 #define XFS_BTREE_ROOT_IN_INODE		(1<<1)	/* root may be variable size */
310 #define XFS_BTREE_LASTREC_UPDATE	(1<<2)	/* track last rec externally */
311 #define XFS_BTREE_CRC_BLOCKS		(1<<3)	/* uses extended btree blocks */
312 #define XFS_BTREE_OVERLAPPING		(1<<4)	/* overlapping intervals */
313 /*
314  * The root of this btree is a fakeroot structure so that we can stage a btree
315  * rebuild without leaving it accessible via primary metadata.  The ops struct
316  * is dynamically allocated and must be freed when the cursor is deleted.
317  */
318 #define XFS_BTREE_STAGING		(1<<5)
319 
320 #define	XFS_BTREE_NOERROR	0
321 #define	XFS_BTREE_ERROR		1
322 
323 /*
324  * Convert from buffer to btree block header.
325  */
326 #define	XFS_BUF_TO_BLOCK(bp)	((struct xfs_btree_block *)((bp)->b_addr))
327 
328 /*
329  * Internal long and short btree block checks.  They return NULL if the
330  * block is ok or the address of the failed check otherwise.
331  */
332 xfs_failaddr_t __xfs_btree_check_lblock(struct xfs_btree_cur *cur,
333 		struct xfs_btree_block *block, int level, struct xfs_buf *bp);
334 xfs_failaddr_t __xfs_btree_check_sblock(struct xfs_btree_cur *cur,
335 		struct xfs_btree_block *block, int level, struct xfs_buf *bp);
336 
337 /*
338  * Check that block header is ok.
339  */
340 int
341 xfs_btree_check_block(
342 	struct xfs_btree_cur	*cur,	/* btree cursor */
343 	struct xfs_btree_block	*block,	/* generic btree block pointer */
344 	int			level,	/* level of the btree block */
345 	struct xfs_buf		*bp);	/* buffer containing block, if any */
346 
347 /*
348  * Check that (long) pointer is ok.
349  */
350 bool					/* error (0 or EFSCORRUPTED) */
351 xfs_btree_check_lptr(
352 	struct xfs_btree_cur	*cur,	/* btree cursor */
353 	xfs_fsblock_t		fsbno,	/* btree block disk address */
354 	int			level);	/* btree block level */
355 
356 /*
357  * Check that (short) pointer is ok.
358  */
359 bool					/* error (0 or EFSCORRUPTED) */
360 xfs_btree_check_sptr(
361 	struct xfs_btree_cur	*cur,	/* btree cursor */
362 	xfs_agblock_t		agbno,	/* btree block disk address */
363 	int			level);	/* btree block level */
364 
365 /*
366  * Delete the btree cursor.
367  */
368 void
369 xfs_btree_del_cursor(
370 	struct xfs_btree_cur	*cur,	/* btree cursor */
371 	int			error);	/* del because of error */
372 
373 /*
374  * Duplicate the btree cursor.
375  * Allocate a new one, copy the record, re-get the buffers.
376  */
377 int					/* error */
378 xfs_btree_dup_cursor(
379 	struct xfs_btree_cur		*cur,	/* input cursor */
380 	struct xfs_btree_cur		**ncur);/* output cursor */
381 
382 /*
383  * Compute first and last byte offsets for the fields given.
384  * Interprets the offsets table, which contains struct field offsets.
385  */
386 void
387 xfs_btree_offsets(
388 	uint32_t		fields,	/* bitmask of fields */
389 	const short		*offsets,/* table of field offsets */
390 	int			nbits,	/* number of bits to inspect */
391 	int			*first,	/* output: first byte offset */
392 	int			*last);	/* output: last byte offset */
393 
394 /*
395  * Get a buffer for the block, return it read in.
396  * Long-form addressing.
397  */
398 int					/* error */
399 xfs_btree_read_bufl(
400 	struct xfs_mount	*mp,	/* file system mount point */
401 	struct xfs_trans	*tp,	/* transaction pointer */
402 	xfs_fsblock_t		fsbno,	/* file system block number */
403 	struct xfs_buf		**bpp,	/* buffer for fsbno */
404 	int			refval,	/* ref count value for buffer */
405 	const struct xfs_buf_ops *ops);
406 
407 /*
408  * Read-ahead the block, don't wait for it, don't return a buffer.
409  * Long-form addressing.
410  */
411 void					/* error */
412 xfs_btree_reada_bufl(
413 	struct xfs_mount	*mp,	/* file system mount point */
414 	xfs_fsblock_t		fsbno,	/* file system block number */
415 	xfs_extlen_t		count,	/* count of filesystem blocks */
416 	const struct xfs_buf_ops *ops);
417 
418 /*
419  * Read-ahead the block, don't wait for it, don't return a buffer.
420  * Short-form addressing.
421  */
422 void					/* error */
423 xfs_btree_reada_bufs(
424 	struct xfs_mount	*mp,	/* file system mount point */
425 	xfs_agnumber_t		agno,	/* allocation group number */
426 	xfs_agblock_t		agbno,	/* allocation group block number */
427 	xfs_extlen_t		count,	/* count of filesystem blocks */
428 	const struct xfs_buf_ops *ops);
429 
430 /*
431  * Initialise a new btree block header
432  */
433 void
434 xfs_btree_init_block(
435 	struct xfs_mount *mp,
436 	struct xfs_buf	*bp,
437 	xfs_btnum_t	btnum,
438 	__u16		level,
439 	__u16		numrecs,
440 	__u64		owner);
441 
442 void
443 xfs_btree_init_block_int(
444 	struct xfs_mount	*mp,
445 	struct xfs_btree_block	*buf,
446 	xfs_daddr_t		blkno,
447 	xfs_btnum_t		btnum,
448 	__u16			level,
449 	__u16			numrecs,
450 	__u64			owner,
451 	unsigned int		flags);
452 
453 /*
454  * Common btree core entry points.
455  */
456 int xfs_btree_increment(struct xfs_btree_cur *, int, int *);
457 int xfs_btree_decrement(struct xfs_btree_cur *, int, int *);
458 int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *);
459 int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *);
460 int xfs_btree_new_iroot(struct xfs_btree_cur *, int *, int *);
461 int xfs_btree_insert(struct xfs_btree_cur *, int *);
462 int xfs_btree_delete(struct xfs_btree_cur *, int *);
463 int xfs_btree_get_rec(struct xfs_btree_cur *, union xfs_btree_rec **, int *);
464 int xfs_btree_change_owner(struct xfs_btree_cur *cur, uint64_t new_owner,
465 			   struct list_head *buffer_list);
466 
467 /*
468  * btree block CRC helpers
469  */
470 void xfs_btree_lblock_calc_crc(struct xfs_buf *);
471 bool xfs_btree_lblock_verify_crc(struct xfs_buf *);
472 void xfs_btree_sblock_calc_crc(struct xfs_buf *);
473 bool xfs_btree_sblock_verify_crc(struct xfs_buf *);
474 
475 /*
476  * Internal btree helpers also used by xfs_bmap.c.
477  */
478 void xfs_btree_log_block(struct xfs_btree_cur *, struct xfs_buf *, uint32_t);
479 void xfs_btree_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int, int);
480 
481 /*
482  * Helpers.
483  */
xfs_btree_get_numrecs(const struct xfs_btree_block * block)484 static inline int xfs_btree_get_numrecs(const struct xfs_btree_block *block)
485 {
486 	return be16_to_cpu(block->bb_numrecs);
487 }
488 
xfs_btree_set_numrecs(struct xfs_btree_block * block,uint16_t numrecs)489 static inline void xfs_btree_set_numrecs(struct xfs_btree_block *block,
490 		uint16_t numrecs)
491 {
492 	block->bb_numrecs = cpu_to_be16(numrecs);
493 }
494 
xfs_btree_get_level(const struct xfs_btree_block * block)495 static inline int xfs_btree_get_level(const struct xfs_btree_block *block)
496 {
497 	return be16_to_cpu(block->bb_level);
498 }
499 
500 
501 /*
502  * Min and max functions for extlen, agblock, fileoff, and filblks types.
503  */
504 #define	XFS_EXTLEN_MIN(a,b)	min_t(xfs_extlen_t, (a), (b))
505 #define	XFS_EXTLEN_MAX(a,b)	max_t(xfs_extlen_t, (a), (b))
506 #define	XFS_AGBLOCK_MIN(a,b)	min_t(xfs_agblock_t, (a), (b))
507 #define	XFS_AGBLOCK_MAX(a,b)	max_t(xfs_agblock_t, (a), (b))
508 #define	XFS_FILEOFF_MIN(a,b)	min_t(xfs_fileoff_t, (a), (b))
509 #define	XFS_FILEOFF_MAX(a,b)	max_t(xfs_fileoff_t, (a), (b))
510 #define	XFS_FILBLKS_MIN(a,b)	min_t(xfs_filblks_t, (a), (b))
511 #define	XFS_FILBLKS_MAX(a,b)	max_t(xfs_filblks_t, (a), (b))
512 
513 xfs_failaddr_t xfs_btree_sblock_v5hdr_verify(struct xfs_buf *bp);
514 xfs_failaddr_t xfs_btree_sblock_verify(struct xfs_buf *bp,
515 		unsigned int max_recs);
516 xfs_failaddr_t xfs_btree_lblock_v5hdr_verify(struct xfs_buf *bp,
517 		uint64_t owner);
518 xfs_failaddr_t xfs_btree_lblock_verify(struct xfs_buf *bp,
519 		unsigned int max_recs);
520 
521 unsigned int xfs_btree_compute_maxlevels(const unsigned int *limits,
522 		unsigned long long records);
523 unsigned long long xfs_btree_calc_size(const unsigned int *limits,
524 		unsigned long long records);
525 unsigned int xfs_btree_space_to_height(const unsigned int *limits,
526 		unsigned long long blocks);
527 
528 /*
529  * Return codes for the query range iterator function are 0 to continue
530  * iterating, and non-zero to stop iterating.  Any non-zero value will be
531  * passed up to the _query_range caller.  The special value -ECANCELED can be
532  * used to stop iteration, because _query_range never generates that error
533  * code on its own.
534  */
535 typedef int (*xfs_btree_query_range_fn)(struct xfs_btree_cur *cur,
536 		const union xfs_btree_rec *rec, void *priv);
537 
538 int xfs_btree_query_range(struct xfs_btree_cur *cur,
539 		const union xfs_btree_irec *low_rec,
540 		const union xfs_btree_irec *high_rec,
541 		xfs_btree_query_range_fn fn, void *priv);
542 int xfs_btree_query_all(struct xfs_btree_cur *cur, xfs_btree_query_range_fn fn,
543 		void *priv);
544 
545 typedef int (*xfs_btree_visit_blocks_fn)(struct xfs_btree_cur *cur, int level,
546 		void *data);
547 /* Visit record blocks. */
548 #define XFS_BTREE_VISIT_RECORDS		(1 << 0)
549 /* Visit leaf blocks. */
550 #define XFS_BTREE_VISIT_LEAVES		(1 << 1)
551 /* Visit all blocks. */
552 #define XFS_BTREE_VISIT_ALL		(XFS_BTREE_VISIT_RECORDS | \
553 					 XFS_BTREE_VISIT_LEAVES)
554 int xfs_btree_visit_blocks(struct xfs_btree_cur *cur,
555 		xfs_btree_visit_blocks_fn fn, unsigned int flags, void *data);
556 
557 int xfs_btree_count_blocks(struct xfs_btree_cur *cur, xfs_extlen_t *blocks);
558 
559 union xfs_btree_rec *xfs_btree_rec_addr(struct xfs_btree_cur *cur, int n,
560 		struct xfs_btree_block *block);
561 union xfs_btree_key *xfs_btree_key_addr(struct xfs_btree_cur *cur, int n,
562 		struct xfs_btree_block *block);
563 union xfs_btree_key *xfs_btree_high_key_addr(struct xfs_btree_cur *cur, int n,
564 		struct xfs_btree_block *block);
565 union xfs_btree_ptr *xfs_btree_ptr_addr(struct xfs_btree_cur *cur, int n,
566 		struct xfs_btree_block *block);
567 int xfs_btree_lookup_get_block(struct xfs_btree_cur *cur, int level,
568 		const union xfs_btree_ptr *pp, struct xfs_btree_block **blkp);
569 struct xfs_btree_block *xfs_btree_get_block(struct xfs_btree_cur *cur,
570 		int level, struct xfs_buf **bpp);
571 bool xfs_btree_ptr_is_null(struct xfs_btree_cur *cur,
572 		const union xfs_btree_ptr *ptr);
573 int64_t xfs_btree_diff_two_ptrs(struct xfs_btree_cur *cur,
574 				const union xfs_btree_ptr *a,
575 				const union xfs_btree_ptr *b);
576 void xfs_btree_get_sibling(struct xfs_btree_cur *cur,
577 			   struct xfs_btree_block *block,
578 			   union xfs_btree_ptr *ptr, int lr);
579 void xfs_btree_get_keys(struct xfs_btree_cur *cur,
580 		struct xfs_btree_block *block, union xfs_btree_key *key);
581 union xfs_btree_key *xfs_btree_high_key_from_key(struct xfs_btree_cur *cur,
582 		union xfs_btree_key *key);
583 typedef bool (*xfs_btree_key_gap_fn)(struct xfs_btree_cur *cur,
584 		const union xfs_btree_key *key1,
585 		const union xfs_btree_key *key2);
586 
587 int xfs_btree_has_records(struct xfs_btree_cur *cur,
588 		const union xfs_btree_irec *low,
589 		const union xfs_btree_irec *high,
590 		const union xfs_btree_key *mask,
591 		enum xbtree_recpacking *outcome);
592 
593 bool xfs_btree_has_more_records(struct xfs_btree_cur *cur);
594 struct xfs_ifork *xfs_btree_ifork_ptr(struct xfs_btree_cur *cur);
595 
596 /* Key comparison helpers */
597 static inline bool
xfs_btree_keycmp_lt(struct xfs_btree_cur * cur,const union xfs_btree_key * key1,const union xfs_btree_key * key2)598 xfs_btree_keycmp_lt(
599 	struct xfs_btree_cur		*cur,
600 	const union xfs_btree_key	*key1,
601 	const union xfs_btree_key	*key2)
602 {
603 	return cur->bc_ops->diff_two_keys(cur, key1, key2, NULL) < 0;
604 }
605 
606 static inline bool
xfs_btree_keycmp_gt(struct xfs_btree_cur * cur,const union xfs_btree_key * key1,const union xfs_btree_key * key2)607 xfs_btree_keycmp_gt(
608 	struct xfs_btree_cur		*cur,
609 	const union xfs_btree_key	*key1,
610 	const union xfs_btree_key	*key2)
611 {
612 	return cur->bc_ops->diff_two_keys(cur, key1, key2, NULL) > 0;
613 }
614 
615 static inline bool
xfs_btree_keycmp_eq(struct xfs_btree_cur * cur,const union xfs_btree_key * key1,const union xfs_btree_key * key2)616 xfs_btree_keycmp_eq(
617 	struct xfs_btree_cur		*cur,
618 	const union xfs_btree_key	*key1,
619 	const union xfs_btree_key	*key2)
620 {
621 	return cur->bc_ops->diff_two_keys(cur, key1, key2, NULL) == 0;
622 }
623 
624 static inline bool
xfs_btree_keycmp_le(struct xfs_btree_cur * cur,const union xfs_btree_key * key1,const union xfs_btree_key * key2)625 xfs_btree_keycmp_le(
626 	struct xfs_btree_cur		*cur,
627 	const union xfs_btree_key	*key1,
628 	const union xfs_btree_key	*key2)
629 {
630 	return !xfs_btree_keycmp_gt(cur, key1, key2);
631 }
632 
633 static inline bool
xfs_btree_keycmp_ge(struct xfs_btree_cur * cur,const union xfs_btree_key * key1,const union xfs_btree_key * key2)634 xfs_btree_keycmp_ge(
635 	struct xfs_btree_cur		*cur,
636 	const union xfs_btree_key	*key1,
637 	const union xfs_btree_key	*key2)
638 {
639 	return !xfs_btree_keycmp_lt(cur, key1, key2);
640 }
641 
642 static inline bool
xfs_btree_keycmp_ne(struct xfs_btree_cur * cur,const union xfs_btree_key * key1,const union xfs_btree_key * key2)643 xfs_btree_keycmp_ne(
644 	struct xfs_btree_cur		*cur,
645 	const union xfs_btree_key	*key1,
646 	const union xfs_btree_key	*key2)
647 {
648 	return !xfs_btree_keycmp_eq(cur, key1, key2);
649 }
650 
651 /* Masked key comparison helpers */
652 static inline bool
xfs_btree_masked_keycmp_lt(struct xfs_btree_cur * cur,const union xfs_btree_key * key1,const union xfs_btree_key * key2,const union xfs_btree_key * mask)653 xfs_btree_masked_keycmp_lt(
654 	struct xfs_btree_cur		*cur,
655 	const union xfs_btree_key	*key1,
656 	const union xfs_btree_key	*key2,
657 	const union xfs_btree_key	*mask)
658 {
659 	return cur->bc_ops->diff_two_keys(cur, key1, key2, mask) < 0;
660 }
661 
662 static inline bool
xfs_btree_masked_keycmp_gt(struct xfs_btree_cur * cur,const union xfs_btree_key * key1,const union xfs_btree_key * key2,const union xfs_btree_key * mask)663 xfs_btree_masked_keycmp_gt(
664 	struct xfs_btree_cur		*cur,
665 	const union xfs_btree_key	*key1,
666 	const union xfs_btree_key	*key2,
667 	const union xfs_btree_key	*mask)
668 {
669 	return cur->bc_ops->diff_two_keys(cur, key1, key2, mask) > 0;
670 }
671 
672 static inline bool
xfs_btree_masked_keycmp_ge(struct xfs_btree_cur * cur,const union xfs_btree_key * key1,const union xfs_btree_key * key2,const union xfs_btree_key * mask)673 xfs_btree_masked_keycmp_ge(
674 	struct xfs_btree_cur		*cur,
675 	const union xfs_btree_key	*key1,
676 	const union xfs_btree_key	*key2,
677 	const union xfs_btree_key	*mask)
678 {
679 	return !xfs_btree_masked_keycmp_lt(cur, key1, key2, mask);
680 }
681 
682 /* Does this cursor point to the last block in the given level? */
683 static inline bool
xfs_btree_islastblock(struct xfs_btree_cur * cur,int level)684 xfs_btree_islastblock(
685 	struct xfs_btree_cur	*cur,
686 	int			level)
687 {
688 	struct xfs_btree_block	*block;
689 	struct xfs_buf		*bp;
690 
691 	block = xfs_btree_get_block(cur, level, &bp);
692 
693 	if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
694 		return block->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK);
695 	return block->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK);
696 }
697 
698 void xfs_btree_set_ptr_null(struct xfs_btree_cur *cur,
699 		union xfs_btree_ptr *ptr);
700 int xfs_btree_get_buf_block(struct xfs_btree_cur *cur,
701 		const union xfs_btree_ptr *ptr, struct xfs_btree_block **block,
702 		struct xfs_buf **bpp);
703 void xfs_btree_set_sibling(struct xfs_btree_cur *cur,
704 		struct xfs_btree_block *block, const union xfs_btree_ptr *ptr,
705 		int lr);
706 void xfs_btree_init_block_cur(struct xfs_btree_cur *cur,
707 		struct xfs_buf *bp, int level, int numrecs);
708 void xfs_btree_copy_ptrs(struct xfs_btree_cur *cur,
709 		union xfs_btree_ptr *dst_ptr,
710 		const union xfs_btree_ptr *src_ptr, int numptrs);
711 void xfs_btree_copy_keys(struct xfs_btree_cur *cur,
712 		union xfs_btree_key *dst_key,
713 		const union xfs_btree_key *src_key, int numkeys);
714 
715 static inline struct xfs_btree_cur *
xfs_btree_alloc_cursor(struct xfs_mount * mp,struct xfs_trans * tp,xfs_btnum_t btnum,uint8_t maxlevels,struct kmem_cache * cache)716 xfs_btree_alloc_cursor(
717 	struct xfs_mount	*mp,
718 	struct xfs_trans	*tp,
719 	xfs_btnum_t		btnum,
720 	uint8_t			maxlevels,
721 	struct kmem_cache	*cache)
722 {
723 	struct xfs_btree_cur	*cur;
724 
725 	cur = kmem_cache_zalloc(cache, GFP_NOFS | __GFP_NOFAIL);
726 	cur->bc_tp = tp;
727 	cur->bc_mp = mp;
728 	cur->bc_btnum = btnum;
729 	cur->bc_maxlevels = maxlevels;
730 	cur->bc_cache = cache;
731 
732 	return cur;
733 }
734 
735 int __init xfs_btree_init_cur_caches(void);
736 void xfs_btree_destroy_cur_caches(void);
737 
738 #endif	/* __XFS_BTREE_H__ */
739