Commit | Line | Data |
---|---|---|
3bd94003 | 1 | // SPDX-License-Identifier: GPL-2.0-only |
7a87edfe JT |
2 | /* |
3 | * Copyright (C) 2012 Red Hat, Inc. | |
4 | * | |
5 | * This file is released under the GPL. | |
6 | */ | |
7 | ||
8 | #include "dm-bitset.h" | |
9 | #include "dm-transaction-manager.h" | |
10 | ||
11 | #include <linux/export.h> | |
12 | #include <linux/device-mapper.h> | |
13 | ||
14 | #define DM_MSG_PREFIX "bitset" | |
15 | #define BITS_PER_ARRAY_ENTRY 64 | |
16 | ||
17 | /*----------------------------------------------------------------*/ | |
18 | ||
19 | static struct dm_btree_value_type bitset_bvt = { | |
20 | .context = NULL, | |
21 | .size = sizeof(__le64), | |
22 | .inc = NULL, | |
23 | .dec = NULL, | |
24 | .equal = NULL, | |
25 | }; | |
26 | ||
27 | /*----------------------------------------------------------------*/ | |
28 | ||
29 | void dm_disk_bitset_init(struct dm_transaction_manager *tm, | |
30 | struct dm_disk_bitset *info) | |
31 | { | |
32 | dm_array_info_init(&info->array_info, tm, &bitset_bvt); | |
33 | info->current_index_set = false; | |
34 | } | |
35 | EXPORT_SYMBOL_GPL(dm_disk_bitset_init); | |
36 | ||
37 | int dm_bitset_empty(struct dm_disk_bitset *info, dm_block_t *root) | |
38 | { | |
39 | return dm_array_empty(&info->array_info, root); | |
40 | } | |
41 | EXPORT_SYMBOL_GPL(dm_bitset_empty); | |
42 | ||
2151249e JT |
43 | struct packer_context { |
44 | bit_value_fn fn; | |
45 | unsigned nr_bits; | |
46 | void *context; | |
47 | }; | |
48 | ||
49 | static int pack_bits(uint32_t index, void *value, void *context) | |
50 | { | |
51 | int r; | |
52 | struct packer_context *p = context; | |
53 | unsigned bit, nr = min(64u, p->nr_bits - (index * 64)); | |
54 | uint64_t word = 0; | |
55 | bool bv; | |
56 | ||
57 | for (bit = 0; bit < nr; bit++) { | |
58 | r = p->fn(index * 64 + bit, &bv, p->context); | |
59 | if (r) | |
60 | return r; | |
61 | ||
62 | if (bv) | |
63 | set_bit(bit, (unsigned long *) &word); | |
64 | else | |
65 | clear_bit(bit, (unsigned long *) &word); | |
66 | } | |
67 | ||
68 | *((__le64 *) value) = cpu_to_le64(word); | |
69 | ||
70 | return 0; | |
71 | } | |
72 | ||
73 | int dm_bitset_new(struct dm_disk_bitset *info, dm_block_t *root, | |
74 | uint32_t size, bit_value_fn fn, void *context) | |
75 | { | |
76 | struct packer_context p; | |
77 | p.fn = fn; | |
78 | p.nr_bits = size; | |
79 | p.context = context; | |
80 | ||
81 | return dm_array_new(&info->array_info, root, dm_div_up(size, 64), pack_bits, &p); | |
82 | } | |
83 | EXPORT_SYMBOL_GPL(dm_bitset_new); | |
84 | ||
7a87edfe JT |
85 | int dm_bitset_resize(struct dm_disk_bitset *info, dm_block_t root, |
86 | uint32_t old_nr_entries, uint32_t new_nr_entries, | |
87 | bool default_value, dm_block_t *new_root) | |
88 | { | |
89 | uint32_t old_blocks = dm_div_up(old_nr_entries, BITS_PER_ARRAY_ENTRY); | |
90 | uint32_t new_blocks = dm_div_up(new_nr_entries, BITS_PER_ARRAY_ENTRY); | |
91 | __le64 value = default_value ? cpu_to_le64(~0) : cpu_to_le64(0); | |
92 | ||
93 | __dm_bless_for_disk(&value); | |
94 | return dm_array_resize(&info->array_info, root, old_blocks, new_blocks, | |
95 | &value, new_root); | |
96 | } | |
97 | EXPORT_SYMBOL_GPL(dm_bitset_resize); | |
98 | ||
99 | int dm_bitset_del(struct dm_disk_bitset *info, dm_block_t root) | |
100 | { | |
101 | return dm_array_del(&info->array_info, root); | |
102 | } | |
103 | EXPORT_SYMBOL_GPL(dm_bitset_del); | |
104 | ||
105 | int dm_bitset_flush(struct dm_disk_bitset *info, dm_block_t root, | |
106 | dm_block_t *new_root) | |
107 | { | |
108 | int r; | |
109 | __le64 value; | |
110 | ||
428e4698 | 111 | if (!info->current_index_set || !info->dirty) |
7a87edfe JT |
112 | return 0; |
113 | ||
114 | value = cpu_to_le64(info->current_bits); | |
115 | ||
116 | __dm_bless_for_disk(&value); | |
117 | r = dm_array_set_value(&info->array_info, root, info->current_index, | |
118 | &value, new_root); | |
119 | if (r) | |
120 | return r; | |
121 | ||
122 | info->current_index_set = false; | |
428e4698 JT |
123 | info->dirty = false; |
124 | ||
7a87edfe JT |
125 | return 0; |
126 | } | |
127 | EXPORT_SYMBOL_GPL(dm_bitset_flush); | |
128 | ||
129 | static int read_bits(struct dm_disk_bitset *info, dm_block_t root, | |
130 | uint32_t array_index) | |
131 | { | |
132 | int r; | |
133 | __le64 value; | |
134 | ||
135 | r = dm_array_get_value(&info->array_info, root, array_index, &value); | |
136 | if (r) | |
137 | return r; | |
138 | ||
139 | info->current_bits = le64_to_cpu(value); | |
140 | info->current_index_set = true; | |
141 | info->current_index = array_index; | |
428e4698 JT |
142 | info->dirty = false; |
143 | ||
7a87edfe JT |
144 | return 0; |
145 | } | |
146 | ||
147 | static int get_array_entry(struct dm_disk_bitset *info, dm_block_t root, | |
148 | uint32_t index, dm_block_t *new_root) | |
149 | { | |
150 | int r; | |
151 | unsigned array_index = index / BITS_PER_ARRAY_ENTRY; | |
152 | ||
153 | if (info->current_index_set) { | |
154 | if (info->current_index == array_index) | |
155 | return 0; | |
156 | ||
157 | r = dm_bitset_flush(info, root, new_root); | |
158 | if (r) | |
159 | return r; | |
160 | } | |
161 | ||
162 | return read_bits(info, root, array_index); | |
163 | } | |
164 | ||
165 | int dm_bitset_set_bit(struct dm_disk_bitset *info, dm_block_t root, | |
166 | uint32_t index, dm_block_t *new_root) | |
167 | { | |
168 | int r; | |
169 | unsigned b = index % BITS_PER_ARRAY_ENTRY; | |
170 | ||
171 | r = get_array_entry(info, root, index, new_root); | |
172 | if (r) | |
173 | return r; | |
174 | ||
175 | set_bit(b, (unsigned long *) &info->current_bits); | |
428e4698 JT |
176 | info->dirty = true; |
177 | ||
7a87edfe JT |
178 | return 0; |
179 | } | |
180 | EXPORT_SYMBOL_GPL(dm_bitset_set_bit); | |
181 | ||
182 | int dm_bitset_clear_bit(struct dm_disk_bitset *info, dm_block_t root, | |
183 | uint32_t index, dm_block_t *new_root) | |
184 | { | |
185 | int r; | |
186 | unsigned b = index % BITS_PER_ARRAY_ENTRY; | |
187 | ||
188 | r = get_array_entry(info, root, index, new_root); | |
189 | if (r) | |
190 | return r; | |
191 | ||
192 | clear_bit(b, (unsigned long *) &info->current_bits); | |
428e4698 JT |
193 | info->dirty = true; |
194 | ||
7a87edfe JT |
195 | return 0; |
196 | } | |
197 | EXPORT_SYMBOL_GPL(dm_bitset_clear_bit); | |
198 | ||
199 | int dm_bitset_test_bit(struct dm_disk_bitset *info, dm_block_t root, | |
200 | uint32_t index, dm_block_t *new_root, bool *result) | |
201 | { | |
202 | int r; | |
203 | unsigned b = index % BITS_PER_ARRAY_ENTRY; | |
204 | ||
205 | r = get_array_entry(info, root, index, new_root); | |
206 | if (r) | |
207 | return r; | |
208 | ||
209 | *result = test_bit(b, (unsigned long *) &info->current_bits); | |
210 | return 0; | |
211 | } | |
212 | EXPORT_SYMBOL_GPL(dm_bitset_test_bit); | |
213 | ||
6fe28dbf JT |
214 | static int cursor_next_array_entry(struct dm_bitset_cursor *c) |
215 | { | |
216 | int r; | |
217 | __le64 *value; | |
218 | ||
219 | r = dm_array_cursor_next(&c->cursor); | |
220 | if (r) | |
221 | return r; | |
222 | ||
223 | dm_array_cursor_get_value(&c->cursor, (void **) &value); | |
224 | c->array_index++; | |
225 | c->bit_index = 0; | |
226 | c->current_bits = le64_to_cpu(*value); | |
227 | return 0; | |
228 | } | |
229 | ||
230 | int dm_bitset_cursor_begin(struct dm_disk_bitset *info, | |
231 | dm_block_t root, uint32_t nr_entries, | |
232 | struct dm_bitset_cursor *c) | |
233 | { | |
234 | int r; | |
235 | __le64 *value; | |
236 | ||
237 | if (!nr_entries) | |
238 | return -ENODATA; | |
239 | ||
240 | c->info = info; | |
241 | c->entries_remaining = nr_entries; | |
242 | ||
243 | r = dm_array_cursor_begin(&info->array_info, root, &c->cursor); | |
244 | if (r) | |
245 | return r; | |
246 | ||
247 | dm_array_cursor_get_value(&c->cursor, (void **) &value); | |
248 | c->array_index = 0; | |
249 | c->bit_index = 0; | |
250 | c->current_bits = le64_to_cpu(*value); | |
251 | ||
252 | return r; | |
253 | } | |
254 | EXPORT_SYMBOL_GPL(dm_bitset_cursor_begin); | |
255 | ||
256 | void dm_bitset_cursor_end(struct dm_bitset_cursor *c) | |
257 | { | |
258 | return dm_array_cursor_end(&c->cursor); | |
259 | } | |
260 | EXPORT_SYMBOL_GPL(dm_bitset_cursor_end); | |
261 | ||
262 | int dm_bitset_cursor_next(struct dm_bitset_cursor *c) | |
263 | { | |
264 | int r = 0; | |
265 | ||
266 | if (!c->entries_remaining) | |
267 | return -ENODATA; | |
268 | ||
269 | c->entries_remaining--; | |
270 | if (++c->bit_index > 63) | |
271 | r = cursor_next_array_entry(c); | |
272 | ||
273 | return r; | |
274 | } | |
275 | EXPORT_SYMBOL_GPL(dm_bitset_cursor_next); | |
276 | ||
9b696229 JT |
277 | int dm_bitset_cursor_skip(struct dm_bitset_cursor *c, uint32_t count) |
278 | { | |
279 | int r; | |
280 | __le64 *value; | |
281 | uint32_t nr_array_skip; | |
282 | uint32_t remaining_in_word = 64 - c->bit_index; | |
283 | ||
284 | if (c->entries_remaining < count) | |
285 | return -ENODATA; | |
286 | ||
287 | if (count < remaining_in_word) { | |
288 | c->bit_index += count; | |
289 | c->entries_remaining -= count; | |
290 | return 0; | |
291 | ||
292 | } else { | |
293 | c->entries_remaining -= remaining_in_word; | |
294 | count -= remaining_in_word; | |
295 | } | |
296 | ||
297 | nr_array_skip = (count / 64) + 1; | |
298 | r = dm_array_cursor_skip(&c->cursor, nr_array_skip); | |
299 | if (r) | |
300 | return r; | |
301 | ||
302 | dm_array_cursor_get_value(&c->cursor, (void **) &value); | |
303 | c->entries_remaining -= count; | |
304 | c->array_index += nr_array_skip; | |
305 | c->bit_index = count & 63; | |
306 | c->current_bits = le64_to_cpu(*value); | |
307 | ||
308 | return 0; | |
309 | } | |
310 | EXPORT_SYMBOL_GPL(dm_bitset_cursor_skip); | |
311 | ||
6fe28dbf JT |
312 | bool dm_bitset_cursor_get_value(struct dm_bitset_cursor *c) |
313 | { | |
314 | return test_bit(c->bit_index, (unsigned long *) &c->current_bits); | |
315 | } | |
316 | EXPORT_SYMBOL_GPL(dm_bitset_cursor_get_value); | |
317 | ||
7a87edfe | 318 | /*----------------------------------------------------------------*/ |