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 | #include "dm-btree-internal.h" |
9 | #include "dm-transaction-manager.h" |
10 | |
11 | #include <linux/device-mapper.h> |
12 | |
13 | #define DM_MSG_PREFIX "btree spine" |
14 | |
15 | /*----------------------------------------------------------------*/ |
16 | |
17 | #define BTREE_CSUM_XOR 121107 |
18 | |
19 | static void node_prepare_for_write(struct dm_block_validator *v, |
20 | struct dm_block *b, |
21 | size_t block_size) |
22 | { |
23 | struct btree_node *n = dm_block_data(b); |
24 | struct node_header *h = &n->header; |
25 | |
26 | h->blocknr = cpu_to_le64(dm_block_location(b)); |
27 | h->csum = cpu_to_le32(dm_bm_checksum(&h->flags, |
28 | block_size - sizeof(__le32), |
29 | BTREE_CSUM_XOR)); |
30 | } |
31 | |
32 | static int node_check(struct dm_block_validator *v, |
33 | struct dm_block *b, |
34 | size_t block_size) |
35 | { |
36 | struct btree_node *n = dm_block_data(b); |
37 | struct node_header *h = &n->header; |
38 | size_t value_size; |
39 | __le32 csum_disk; |
40 | uint32_t flags, nr_entries, max_entries; |
41 | |
42 | if (dm_block_location(b) != le64_to_cpu(h->blocknr)) { |
43 | DMERR_LIMIT("%s failed: blocknr %llu != wanted %llu" , __func__, |
44 | le64_to_cpu(h->blocknr), dm_block_location(b)); |
45 | return -ENOTBLK; |
46 | } |
47 | |
48 | csum_disk = cpu_to_le32(dm_bm_checksum(&h->flags, |
49 | block_size - sizeof(__le32), |
50 | BTREE_CSUM_XOR)); |
51 | if (csum_disk != h->csum) { |
52 | DMERR_LIMIT("%s failed: csum %u != wanted %u" , __func__, |
53 | le32_to_cpu(csum_disk), le32_to_cpu(h->csum)); |
54 | return -EILSEQ; |
55 | } |
56 | |
57 | nr_entries = le32_to_cpu(h->nr_entries); |
58 | max_entries = le32_to_cpu(h->max_entries); |
59 | value_size = le32_to_cpu(h->value_size); |
60 | |
61 | if (sizeof(struct node_header) + |
62 | (sizeof(__le64) + value_size) * max_entries > block_size) { |
63 | DMERR_LIMIT("%s failed: max_entries too large" , __func__); |
64 | return -EILSEQ; |
65 | } |
66 | |
67 | if (nr_entries > max_entries) { |
68 | DMERR_LIMIT("%s failed: too many entries" , __func__); |
69 | return -EILSEQ; |
70 | } |
71 | |
72 | /* |
73 | * The node must be either INTERNAL or LEAF. |
74 | */ |
75 | flags = le32_to_cpu(h->flags); |
76 | if (!(flags & INTERNAL_NODE) && !(flags & LEAF_NODE)) { |
77 | DMERR_LIMIT("%s failed: node is neither INTERNAL or LEAF" , __func__); |
78 | return -EILSEQ; |
79 | } |
80 | |
81 | return 0; |
82 | } |
83 | |
84 | struct dm_block_validator btree_node_validator = { |
85 | .name = "btree_node" , |
86 | .prepare_for_write = node_prepare_for_write, |
87 | .check = node_check |
88 | }; |
89 | |
90 | /*----------------------------------------------------------------*/ |
91 | |
92 | int bn_read_lock(struct dm_btree_info *info, dm_block_t b, |
93 | struct dm_block **result) |
94 | { |
95 | return dm_tm_read_lock(tm: info->tm, b, v: &btree_node_validator, result); |
96 | } |
97 | |
98 | static int bn_shadow(struct dm_btree_info *info, dm_block_t orig, |
99 | struct dm_btree_value_type *vt, |
100 | struct dm_block **result) |
101 | { |
102 | int r, inc; |
103 | |
104 | r = dm_tm_shadow_block(tm: info->tm, orig, v: &btree_node_validator, |
105 | result, inc_children: &inc); |
106 | if (!r && inc) |
107 | inc_children(tm: info->tm, n: dm_block_data(b: *result), vt); |
108 | |
109 | return r; |
110 | } |
111 | |
112 | int new_block(struct dm_btree_info *info, struct dm_block **result) |
113 | { |
114 | return dm_tm_new_block(tm: info->tm, v: &btree_node_validator, result); |
115 | } |
116 | |
117 | void unlock_block(struct dm_btree_info *info, struct dm_block *b) |
118 | { |
119 | dm_tm_unlock(tm: info->tm, b); |
120 | } |
121 | |
122 | /*----------------------------------------------------------------*/ |
123 | |
124 | void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info) |
125 | { |
126 | s->info = info; |
127 | s->count = 0; |
128 | s->nodes[0] = NULL; |
129 | s->nodes[1] = NULL; |
130 | } |
131 | |
132 | void exit_ro_spine(struct ro_spine *s) |
133 | { |
134 | int i; |
135 | |
136 | for (i = 0; i < s->count; i++) |
137 | unlock_block(info: s->info, b: s->nodes[i]); |
138 | } |
139 | |
140 | int ro_step(struct ro_spine *s, dm_block_t new_child) |
141 | { |
142 | int r; |
143 | |
144 | if (s->count == 2) { |
145 | unlock_block(info: s->info, b: s->nodes[0]); |
146 | s->nodes[0] = s->nodes[1]; |
147 | s->count--; |
148 | } |
149 | |
150 | r = bn_read_lock(info: s->info, b: new_child, result: s->nodes + s->count); |
151 | if (!r) |
152 | s->count++; |
153 | |
154 | return r; |
155 | } |
156 | |
157 | void ro_pop(struct ro_spine *s) |
158 | { |
159 | BUG_ON(!s->count); |
160 | --s->count; |
161 | unlock_block(info: s->info, b: s->nodes[s->count]); |
162 | } |
163 | |
164 | struct btree_node *ro_node(struct ro_spine *s) |
165 | { |
166 | struct dm_block *block; |
167 | |
168 | BUG_ON(!s->count); |
169 | block = s->nodes[s->count - 1]; |
170 | |
171 | return dm_block_data(b: block); |
172 | } |
173 | |
174 | /*----------------------------------------------------------------*/ |
175 | |
176 | void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info) |
177 | { |
178 | s->info = info; |
179 | s->count = 0; |
180 | } |
181 | |
182 | void exit_shadow_spine(struct shadow_spine *s) |
183 | { |
184 | int i; |
185 | |
186 | for (i = 0; i < s->count; i++) |
187 | unlock_block(info: s->info, b: s->nodes[i]); |
188 | } |
189 | |
190 | int shadow_step(struct shadow_spine *s, dm_block_t b, |
191 | struct dm_btree_value_type *vt) |
192 | { |
193 | int r; |
194 | |
195 | if (s->count == 2) { |
196 | unlock_block(info: s->info, b: s->nodes[0]); |
197 | s->nodes[0] = s->nodes[1]; |
198 | s->count--; |
199 | } |
200 | |
201 | r = bn_shadow(info: s->info, orig: b, vt, result: s->nodes + s->count); |
202 | if (!r) { |
203 | if (!s->count) |
204 | s->root = dm_block_location(b: s->nodes[0]); |
205 | |
206 | s->count++; |
207 | } |
208 | |
209 | return r; |
210 | } |
211 | |
212 | struct dm_block *shadow_current(struct shadow_spine *s) |
213 | { |
214 | BUG_ON(!s->count); |
215 | |
216 | return s->nodes[s->count - 1]; |
217 | } |
218 | |
219 | struct dm_block *shadow_parent(struct shadow_spine *s) |
220 | { |
221 | BUG_ON(s->count != 2); |
222 | |
223 | return s->count == 2 ? s->nodes[0] : NULL; |
224 | } |
225 | |
226 | int shadow_has_parent(struct shadow_spine *s) |
227 | { |
228 | return s->count >= 2; |
229 | } |
230 | |
231 | dm_block_t shadow_root(struct shadow_spine *s) |
232 | { |
233 | return s->root; |
234 | } |
235 | |
236 | static void le64_inc(void *context, const void *value_le, unsigned int count) |
237 | { |
238 | dm_tm_with_runs(tm: context, value_le, count, fn: dm_tm_inc_range); |
239 | } |
240 | |
241 | static void le64_dec(void *context, const void *value_le, unsigned int count) |
242 | { |
243 | dm_tm_with_runs(tm: context, value_le, count, fn: dm_tm_dec_range); |
244 | } |
245 | |
246 | static int le64_equal(void *context, const void *value1_le, const void *value2_le) |
247 | { |
248 | __le64 v1_le, v2_le; |
249 | |
250 | memcpy(&v1_le, value1_le, sizeof(v1_le)); |
251 | memcpy(&v2_le, value2_le, sizeof(v2_le)); |
252 | return v1_le == v2_le; |
253 | } |
254 | |
255 | void init_le64_type(struct dm_transaction_manager *tm, |
256 | struct dm_btree_value_type *vt) |
257 | { |
258 | vt->context = tm; |
259 | vt->size = sizeof(__le64); |
260 | vt->inc = le64_inc; |
261 | vt->dec = le64_dec; |
262 | vt->equal = le64_equal; |
263 | } |
264 | |