/* SPDX-License-Identifier: GPL-2.0 */ /* * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc. * All Rights Reserved. */ #ifndef __XFS_BTREE_H__ #define __XFS_BTREE_H__ struct xfs_buf; struct xfs_inode; struct xfs_mount; struct xfs_trans; struct xfs_ifork; struct xfs_perag; /* * 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. */ xfs_btree_ptr; /* * 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. */ xfs_btree_key; xfs_btree_rec; /* * This nonsense is to make -wlint happy. */ #define XFS_LOOKUP_EQ … #define XFS_LOOKUP_LE … #define XFS_LOOKUP_GE … struct xfs_btree_ops; uint32_t xfs_btree_magic(struct xfs_mount *mp, const struct xfs_btree_ops *ops); /* * For logging record fields. */ #define XFS_BB_MAGIC … #define XFS_BB_LEVEL … #define XFS_BB_NUMRECS … #define XFS_BB_LEFTSIB … #define XFS_BB_RIGHTSIB … #define XFS_BB_BLKNO … #define XFS_BB_LSN … #define XFS_BB_UUID … #define XFS_BB_OWNER … #define XFS_BB_NUM_BITS … #define XFS_BB_ALL_BITS … #define XFS_BB_NUM_BITS_CRC … #define XFS_BB_ALL_BITS_CRC … /* * Generic stats interface */ #define XFS_BTREE_STATS_INC(cur, stat) … #define XFS_BTREE_STATS_ADD(cur, stat, val) … enum xbtree_key_contig { … }; /* * Decide if these two numeric btree key fields are contiguous, overlapping, * or if there's a gap between them. @x should be the field from the high * key and @y should be the field from the low key. */ static inline enum xbtree_key_contig xbtree_key_contig(uint64_t x, uint64_t y) { … } #define XFS_BTREE_LONG_PTR_LEN … #define XFS_BTREE_SHORT_PTR_LEN … enum xfs_btree_type { … }; struct xfs_btree_ops { … }; /* btree geometry flags */ #define XFS_BTGEO_OVERLAPPING … xfs_btree_irec; struct xfs_btree_level { … }; /* * Btree cursor structure. * This collects all information needed by the btree code in one place. */ struct xfs_btree_cur { … }; /* * Compute the size of a btree cursor that can handle a btree of a given * height. The bc_levels array handles node and leaf blocks, so its size * is exactly nlevels. */ static inline size_t xfs_btree_cur_sizeof(unsigned int nlevels) { … } /* cursor state flags */ /* * 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 … /* We are converting a delalloc reservation (only for bmbt btrees) */ #define XFS_BTREE_BMBT_WASDEL … /* For extent swap, ignore owner check in verifier (only for bmbt btrees) */ #define XFS_BTREE_BMBT_INVALID_OWNER … /* Cursor is active (only for allocbt btrees) */ #define XFS_BTREE_ALLOCBT_ACTIVE … #define XFS_BTREE_NOERROR … #define XFS_BTREE_ERROR … /* * Convert from buffer to btree block header. */ #define XFS_BUF_TO_BLOCK(bp) … xfs_failaddr_t __xfs_btree_check_block(struct xfs_btree_cur *cur, struct xfs_btree_block *block, int level, struct xfs_buf *bp); int __xfs_btree_check_ptr(struct xfs_btree_cur *cur, const union xfs_btree_ptr *ptr, int index, int level); /* * Check that block header is ok. */ int xfs_btree_check_block( struct xfs_btree_cur *cur, /* btree cursor */ struct xfs_btree_block *block, /* generic btree block pointer */ int level, /* level of the btree block */ struct xfs_buf *bp); /* buffer containing block, if any */ /* * Delete the btree cursor. */ void xfs_btree_del_cursor( struct xfs_btree_cur *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( struct xfs_btree_cur *cur, /* input cursor */ struct xfs_btree_cur **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( uint32_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 */ /* * Initialise a new btree block header */ void xfs_btree_init_buf(struct xfs_mount *mp, struct xfs_buf *bp, const struct xfs_btree_ops *ops, __u16 level, __u16 numrecs, __u64 owner); void xfs_btree_init_block(struct xfs_mount *mp, struct xfs_btree_block *buf, const struct xfs_btree_ops *ops, __u16 level, __u16 numrecs, __u64 owner); /* * Common btree core entry points. */ int xfs_btree_increment(struct xfs_btree_cur *, int, int *); int xfs_btree_decrement(struct xfs_btree_cur *, int, int *); int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *); int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *); int xfs_btree_new_iroot(struct xfs_btree_cur *, int *, int *); int xfs_btree_insert(struct xfs_btree_cur *, int *); int xfs_btree_delete(struct xfs_btree_cur *, int *); int xfs_btree_get_rec(struct xfs_btree_cur *, union xfs_btree_rec **, int *); int xfs_btree_change_owner(struct xfs_btree_cur *cur, uint64_t new_owner, struct list_head *buffer_list); /* * btree block CRC helpers */ void xfs_btree_fsblock_calc_crc(struct xfs_buf *); bool xfs_btree_fsblock_verify_crc(struct xfs_buf *); void xfs_btree_agblock_calc_crc(struct xfs_buf *); bool xfs_btree_agblock_verify_crc(struct xfs_buf *); /* * Internal btree helpers also used by xfs_bmap.c. */ void xfs_btree_log_block(struct xfs_btree_cur *, struct xfs_buf *, uint32_t); void xfs_btree_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int, int); /* * Helpers. */ static inline int xfs_btree_get_numrecs(const struct xfs_btree_block *block) { … } static inline void xfs_btree_set_numrecs(struct xfs_btree_block *block, uint16_t numrecs) { … } static inline int xfs_btree_get_level(const struct xfs_btree_block *block) { … } /* * Min and max functions for extlen, agblock, fileoff, and filblks types. */ #define XFS_EXTLEN_MIN(a,b) … #define XFS_EXTLEN_MAX(a,b) … #define XFS_AGBLOCK_MIN(a,b) … #define XFS_AGBLOCK_MAX(a,b) … #define XFS_FILEOFF_MIN(a,b) … #define XFS_FILEOFF_MAX(a,b) … #define XFS_FILBLKS_MIN(a,b) … #define XFS_FILBLKS_MAX(a,b) … xfs_failaddr_t xfs_btree_agblock_v5hdr_verify(struct xfs_buf *bp); xfs_failaddr_t xfs_btree_agblock_verify(struct xfs_buf *bp, unsigned int max_recs); xfs_failaddr_t xfs_btree_fsblock_v5hdr_verify(struct xfs_buf *bp, uint64_t owner); xfs_failaddr_t xfs_btree_fsblock_verify(struct xfs_buf *bp, unsigned int max_recs); xfs_failaddr_t xfs_btree_memblock_verify(struct xfs_buf *bp, unsigned int max_recs); unsigned int xfs_btree_compute_maxlevels(const unsigned int *limits, unsigned long long records); unsigned long long xfs_btree_calc_size(const unsigned int *limits, unsigned long long records); unsigned int xfs_btree_space_to_height(const unsigned int *limits, unsigned long long blocks); /* * 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. */ xfs_btree_query_range_fn; int xfs_btree_query_range(struct xfs_btree_cur *cur, const union xfs_btree_irec *low_rec, const union xfs_btree_irec *high_rec, xfs_btree_query_range_fn fn, void *priv); int xfs_btree_query_all(struct xfs_btree_cur *cur, xfs_btree_query_range_fn fn, void *priv); xfs_btree_visit_blocks_fn; /* Visit record blocks. */ #define XFS_BTREE_VISIT_RECORDS … /* Visit leaf blocks. */ #define XFS_BTREE_VISIT_LEAVES … /* Visit all blocks. */ #define XFS_BTREE_VISIT_ALL … int xfs_btree_visit_blocks(struct xfs_btree_cur *cur, xfs_btree_visit_blocks_fn fn, unsigned int flags, void *data); int xfs_btree_count_blocks(struct xfs_btree_cur *cur, xfs_extlen_t *blocks); 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, const 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); bool xfs_btree_ptr_is_null(struct xfs_btree_cur *cur, const 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); 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); xfs_btree_key_gap_fn; int xfs_btree_has_records(struct xfs_btree_cur *cur, const union xfs_btree_irec *low, const union xfs_btree_irec *high, const union xfs_btree_key *mask, enum xbtree_recpacking *outcome); bool xfs_btree_has_more_records(struct xfs_btree_cur *cur); struct xfs_ifork *xfs_btree_ifork_ptr(struct xfs_btree_cur *cur); /* Key comparison helpers */ static inline bool xfs_btree_keycmp_lt( struct xfs_btree_cur *cur, const union xfs_btree_key *key1, const union xfs_btree_key *key2) { … } static inline bool xfs_btree_keycmp_gt( struct xfs_btree_cur *cur, const union xfs_btree_key *key1, const union xfs_btree_key *key2) { … } static inline bool xfs_btree_keycmp_eq( struct xfs_btree_cur *cur, const union xfs_btree_key *key1, const union xfs_btree_key *key2) { … } static inline bool xfs_btree_keycmp_le( struct xfs_btree_cur *cur, const union xfs_btree_key *key1, const union xfs_btree_key *key2) { … } static inline bool xfs_btree_keycmp_ge( struct xfs_btree_cur *cur, const union xfs_btree_key *key1, const union xfs_btree_key *key2) { … } static inline bool xfs_btree_keycmp_ne( struct xfs_btree_cur *cur, const union xfs_btree_key *key1, const union xfs_btree_key *key2) { … } /* Masked key comparison helpers */ 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) { … } 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) { … } 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) { … } /* Does this cursor point to the last block in the given level? */ static inline bool xfs_btree_islastblock( struct xfs_btree_cur *cur, int level) { … } 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, const union xfs_btree_ptr *ptr, struct xfs_btree_block **block, struct xfs_buf **bpp); int xfs_btree_read_buf_block(struct xfs_btree_cur *cur, const union xfs_btree_ptr *ptr, int flags, struct xfs_btree_block **block, struct xfs_buf **bpp); void xfs_btree_set_sibling(struct xfs_btree_cur *cur, struct xfs_btree_block *block, const 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, const union xfs_btree_key *src_key, int numkeys); void xfs_btree_init_ptr_from_cur(struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr); static inline struct xfs_btree_cur * xfs_btree_alloc_cursor( struct xfs_mount *mp, struct xfs_trans *tp, const struct xfs_btree_ops *ops, uint8_t maxlevels, struct kmem_cache *cache) { … } int __init xfs_btree_init_cur_caches(void); void xfs_btree_destroy_cur_caches(void); int xfs_btree_goto_left_edge(struct xfs_btree_cur *cur); /* Does this level of the cursor point to the inode root (and not a block)? */ static inline bool xfs_btree_at_iroot( const struct xfs_btree_cur *cur, int level) { … } #endif /* __XFS_BTREE_H__ */
Codebase Browser
linux