Orange Pi5 kernel

^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  1) /* SPDX-License-Identifier: GPL-2.0+ */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  3)  * btree.h - NILFS B-tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  4)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  5)  * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  6)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  7)  * Written by Koji Sato.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  8)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  9) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #ifndef _NILFS_BTREE_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) #define _NILFS_BTREE_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) #include <linux/types.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) #include <linux/buffer_head.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) #include <linux/list.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) #include <linux/nilfs2_ondisk.h>	/* nilfs_btree_node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) #include "btnode.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) #include "bmap.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21)  * struct nilfs_btree_path - A path on which B-tree operations are executed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22)  * @bp_bh: buffer head of node block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23)  * @bp_sib_bh: buffer head of sibling node block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24)  * @bp_index: index of child node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25)  * @bp_oldreq: ptr end request for old ptr
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26)  * @bp_newreq: ptr alloc request for new ptr
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27)  * @bp_op: rebalance operation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) struct nilfs_btree_path {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) 	struct buffer_head *bp_bh;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) 	struct buffer_head *bp_sib_bh;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) 	int bp_index;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) 	union nilfs_bmap_ptr_req bp_oldreq;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) 	union nilfs_bmap_ptr_req bp_newreq;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) 	struct nilfs_btnode_chkey_ctxt bp_ctxt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) 	void (*bp_op)(struct nilfs_bmap *, struct nilfs_btree_path *,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) 		      int, __u64 *, __u64 *);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) #define NILFS_BTREE_ROOT_SIZE		NILFS_BMAP_SIZE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) #define NILFS_BTREE_ROOT_NCHILDREN_MAX					\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) 	((NILFS_BTREE_ROOT_SIZE - sizeof(struct nilfs_btree_node)) /	\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) 	 (sizeof(__le64 /* dkey */) + sizeof(__le64 /* dptr */)))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) #define NILFS_BTREE_ROOT_NCHILDREN_MIN	0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) #define NILFS_BTREE_NODE_EXTRA_PAD_SIZE	(sizeof(__le64))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) #define NILFS_BTREE_NODE_NCHILDREN_MAX(nodesize)			\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) 	(((nodesize) - sizeof(struct nilfs_btree_node) -		\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) 		NILFS_BTREE_NODE_EXTRA_PAD_SIZE) /			\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) 	 (sizeof(__le64 /* dkey */) + sizeof(__le64 /* dptr */)))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) #define NILFS_BTREE_NODE_NCHILDREN_MIN(nodesize)			\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) 	((NILFS_BTREE_NODE_NCHILDREN_MAX(nodesize) - 1) / 2 + 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) #define NILFS_BTREE_KEY_MIN	((__u64)0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) #define NILFS_BTREE_KEY_MAX	(~(__u64)0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) extern struct kmem_cache *nilfs_btree_path_cache;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) int nilfs_btree_init(struct nilfs_bmap *);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) int nilfs_btree_convert_and_insert(struct nilfs_bmap *, __u64, __u64,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) 				   const __u64 *, const __u64 *, int);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) void nilfs_btree_init_gc(struct nilfs_bmap *);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) int nilfs_btree_broken_node_block(struct buffer_head *bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) #endif	/* _NILFS_BTREE_H */