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