1 /* SPDX-License-Identifier: GPL-2.0-only */
2 /*
3  * Copyright (C) 2011 Red Hat, Inc.
4  *
5  * This file is released under the GPL.
6  */
7 
8 #ifndef DM_BTREE_INTERNAL_H
9 #define DM_BTREE_INTERNAL_H
10 
11 #include "dm-btree.h"
12 
13 /*----------------------------------------------------------------*/
14 
15 /*
16  * We'll need 2 accessor functions for n->csum and n->blocknr
17  * to support dm-btree-spine.c in that case.
18  */
19 
20 enum node_flags {
21 	INTERNAL_NODE = 1,
22 	LEAF_NODE = 1 << 1
23 };
24 
25 /*
26  * Every btree node begins with this structure.  Make sure it's a multiple
27  * of 8-bytes in size, otherwise the 64bit keys will be mis-aligned.
28  */
29 struct node_header {
30 	__le32 csum;
31 	__le32 flags;
32 	__le64 blocknr; /* Block this node is supposed to live in. */
33 
34 	__le32 nr_entries;
35 	__le32 max_entries;
36 	__le32 value_size;
37 	__le32 padding;
38 } __packed __aligned(8);
39 
40 struct btree_node {
41 	struct node_header header;
42 	__le64 keys[];
43 } __packed __aligned(8);
44 
45 
46 /*
47  * Locks a block using the btree node validator.
48  */
49 int bn_read_lock(struct dm_btree_info *info, dm_block_t b,
50 		 struct dm_block **result);
51 
52 void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
53 		  struct dm_btree_value_type *vt);
54 
55 int new_block(struct dm_btree_info *info, struct dm_block **result);
56 void unlock_block(struct dm_btree_info *info, struct dm_block *b);
57 
58 /*
59  * Spines keep track of the rolling locks.  There are 2 variants, read-only
60  * and one that uses shadowing.  These are separate structs to allow the
61  * type checker to spot misuse, for example accidentally calling read_lock
62  * on a shadow spine.
63  */
64 struct ro_spine {
65 	struct dm_btree_info *info;
66 
67 	int count;
68 	struct dm_block *nodes[2];
69 };
70 
71 void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
72 void exit_ro_spine(struct ro_spine *s);
73 int ro_step(struct ro_spine *s, dm_block_t new_child);
74 void ro_pop(struct ro_spine *s);
75 struct btree_node *ro_node(struct ro_spine *s);
76 
77 struct shadow_spine {
78 	struct dm_btree_info *info;
79 
80 	int count;
81 	struct dm_block *nodes[2];
82 
83 	dm_block_t root;
84 };
85 
86 void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
87 void exit_shadow_spine(struct shadow_spine *s);
88 
89 int shadow_step(struct shadow_spine *s, dm_block_t b,
90 		struct dm_btree_value_type *vt);
91 
92 /*
93  * The spine must have at least one entry before calling this.
94  */
95 struct dm_block *shadow_current(struct shadow_spine *s);
96 
97 /*
98  * The spine must have at least two entries before calling this.
99  */
100 struct dm_block *shadow_parent(struct shadow_spine *s);
101 
102 int shadow_has_parent(struct shadow_spine *s);
103 
104 dm_block_t shadow_root(struct shadow_spine *s);
105 
106 /*
107  * Some inlines.
108  */
109 static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
110 {
111 	return n->keys + index;
112 }
113 
114 static inline void *value_base(struct btree_node *n)
115 {
116 	return &n->keys[le32_to_cpu(n->header.max_entries)];
117 }
118 
119 static inline void *value_ptr(struct btree_node *n, uint32_t index)
120 {
121 	uint32_t value_size = le32_to_cpu(n->header.value_size);
122 
123 	return value_base(n) + (value_size * index);
124 }
125 
126 /*
127  * Assumes the values are suitably-aligned and converts to core format.
128  */
129 static inline uint64_t value64(struct btree_node *n, uint32_t index)
130 {
131 	__le64 *values_le = value_base(n);
132 
133 	return le64_to_cpu(values_le[index]);
134 }
135 
136 /*
137  * Searching for a key within a single node.
138  */
139 int lower_bound(struct btree_node *n, uint64_t key);
140 
141 extern struct dm_block_validator btree_node_validator;
142 
143 /*
144  * Value type for upper levels of multi-level btrees.
145  */
146 extern void init_le64_type(struct dm_transaction_manager *tm,
147 			   struct dm_btree_value_type *vt);
148 
149 /*
150  * This returns a shadowed btree leaf that you may modify.  In practise
151  * this means overwrites only, since an insert could cause a node to
152  * be split.  Useful if you need access to the old value to calculate the
153  * new one.
154  *
155  * This only works with single level btrees.  The given key must be present in
156  * the tree, otherwise -EINVAL will be returned.
157  */
158 int btree_get_overwrite_leaf(struct dm_btree_info *info, dm_block_t root,
159 			     uint64_t key, int *index,
160 			     dm_block_t *new_root, struct dm_block **leaf);
161 
162 #endif	/* DM_BTREE_INTERNAL_H */
163