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 { |
30 | __le32 ; |
31 | __le32 ; |
32 | __le64 ; /* Block this node is supposed to live in. */ |
33 | |
34 | __le32 ; |
35 | __le32 ; |
36 | __le32 ; |
37 | __le32 ; |
38 | } __packed __aligned(8); |
39 | |
40 | struct btree_node { |
41 | struct node_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 | |