1 | // SPDX-License-Identifier: GPL-2.0-only |
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: &info->array_info, tm, vt: &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: &info->array_info, root); |
40 | } |
41 | EXPORT_SYMBOL_GPL(dm_bitset_empty); |
42 | |
43 | struct packer_context { |
44 | bit_value_fn fn; |
45 | unsigned int 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 int 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(nr: bit, addr: (unsigned long *) &word); |
64 | else |
65 | clear_bit(nr: bit, addr: (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 | |
78 | p.fn = fn; |
79 | p.nr_bits = size; |
80 | p.context = context; |
81 | |
82 | return dm_array_new(info: &info->array_info, root, dm_div_up(size, 64), fn: pack_bits, context: &p); |
83 | } |
84 | EXPORT_SYMBOL_GPL(dm_bitset_new); |
85 | |
86 | int dm_bitset_resize(struct dm_disk_bitset *info, dm_block_t root, |
87 | uint32_t old_nr_entries, uint32_t new_nr_entries, |
88 | bool default_value, dm_block_t *new_root) |
89 | { |
90 | uint32_t old_blocks = dm_div_up(old_nr_entries, BITS_PER_ARRAY_ENTRY); |
91 | uint32_t new_blocks = dm_div_up(new_nr_entries, BITS_PER_ARRAY_ENTRY); |
92 | __le64 value = default_value ? cpu_to_le64(~0) : cpu_to_le64(0); |
93 | |
94 | __dm_bless_for_disk(&value); |
95 | return dm_array_resize(info: &info->array_info, root, old_size: old_blocks, new_size: new_blocks, |
96 | value: &value, new_root); |
97 | } |
98 | EXPORT_SYMBOL_GPL(dm_bitset_resize); |
99 | |
100 | int dm_bitset_del(struct dm_disk_bitset *info, dm_block_t root) |
101 | { |
102 | return dm_array_del(info: &info->array_info, root); |
103 | } |
104 | EXPORT_SYMBOL_GPL(dm_bitset_del); |
105 | |
106 | int dm_bitset_flush(struct dm_disk_bitset *info, dm_block_t root, |
107 | dm_block_t *new_root) |
108 | { |
109 | int r; |
110 | __le64 value; |
111 | |
112 | if (!info->current_index_set || !info->dirty) |
113 | return 0; |
114 | |
115 | value = cpu_to_le64(info->current_bits); |
116 | |
117 | __dm_bless_for_disk(&value); |
118 | r = dm_array_set_value(info: &info->array_info, root, index: info->current_index, |
119 | value: &value, new_root); |
120 | if (r) |
121 | return r; |
122 | |
123 | info->current_index_set = false; |
124 | info->dirty = false; |
125 | |
126 | return 0; |
127 | } |
128 | EXPORT_SYMBOL_GPL(dm_bitset_flush); |
129 | |
130 | static int read_bits(struct dm_disk_bitset *info, dm_block_t root, |
131 | uint32_t array_index) |
132 | { |
133 | int r; |
134 | __le64 value; |
135 | |
136 | r = dm_array_get_value(info: &info->array_info, root, index: array_index, value: &value); |
137 | if (r) |
138 | return r; |
139 | |
140 | info->current_bits = le64_to_cpu(value); |
141 | info->current_index_set = true; |
142 | info->current_index = array_index; |
143 | info->dirty = false; |
144 | |
145 | return 0; |
146 | } |
147 | |
148 | static int get_array_entry(struct dm_disk_bitset *info, dm_block_t root, |
149 | uint32_t index, dm_block_t *new_root) |
150 | { |
151 | int r; |
152 | unsigned int array_index = index / BITS_PER_ARRAY_ENTRY; |
153 | |
154 | if (info->current_index_set) { |
155 | if (info->current_index == array_index) |
156 | return 0; |
157 | |
158 | r = dm_bitset_flush(info, root, new_root); |
159 | if (r) |
160 | return r; |
161 | } |
162 | |
163 | return read_bits(info, root, array_index); |
164 | } |
165 | |
166 | int dm_bitset_set_bit(struct dm_disk_bitset *info, dm_block_t root, |
167 | uint32_t index, dm_block_t *new_root) |
168 | { |
169 | int r; |
170 | unsigned int b = index % BITS_PER_ARRAY_ENTRY; |
171 | |
172 | r = get_array_entry(info, root, index, new_root); |
173 | if (r) |
174 | return r; |
175 | |
176 | set_bit(nr: b, addr: (unsigned long *) &info->current_bits); |
177 | info->dirty = true; |
178 | |
179 | return 0; |
180 | } |
181 | EXPORT_SYMBOL_GPL(dm_bitset_set_bit); |
182 | |
183 | int dm_bitset_clear_bit(struct dm_disk_bitset *info, dm_block_t root, |
184 | uint32_t index, dm_block_t *new_root) |
185 | { |
186 | int r; |
187 | unsigned int b = index % BITS_PER_ARRAY_ENTRY; |
188 | |
189 | r = get_array_entry(info, root, index, new_root); |
190 | if (r) |
191 | return r; |
192 | |
193 | clear_bit(nr: b, addr: (unsigned long *) &info->current_bits); |
194 | info->dirty = true; |
195 | |
196 | return 0; |
197 | } |
198 | EXPORT_SYMBOL_GPL(dm_bitset_clear_bit); |
199 | |
200 | int dm_bitset_test_bit(struct dm_disk_bitset *info, dm_block_t root, |
201 | uint32_t index, dm_block_t *new_root, bool *result) |
202 | { |
203 | int r; |
204 | unsigned int b = index % BITS_PER_ARRAY_ENTRY; |
205 | |
206 | r = get_array_entry(info, root, index, new_root); |
207 | if (r) |
208 | return r; |
209 | |
210 | *result = test_bit(b, (unsigned long *) &info->current_bits); |
211 | return 0; |
212 | } |
213 | EXPORT_SYMBOL_GPL(dm_bitset_test_bit); |
214 | |
215 | static int cursor_next_array_entry(struct dm_bitset_cursor *c) |
216 | { |
217 | int r; |
218 | __le64 *value; |
219 | |
220 | r = dm_array_cursor_next(c: &c->cursor); |
221 | if (r) |
222 | return r; |
223 | |
224 | dm_array_cursor_get_value(c: &c->cursor, value_le: (void **) &value); |
225 | c->array_index++; |
226 | c->bit_index = 0; |
227 | c->current_bits = le64_to_cpu(*value); |
228 | return 0; |
229 | } |
230 | |
231 | int dm_bitset_cursor_begin(struct dm_disk_bitset *info, |
232 | dm_block_t root, uint32_t nr_entries, |
233 | struct dm_bitset_cursor *c) |
234 | { |
235 | int r; |
236 | __le64 *value; |
237 | |
238 | if (!nr_entries) |
239 | return -ENODATA; |
240 | |
241 | c->info = info; |
242 | c->entries_remaining = nr_entries; |
243 | |
244 | r = dm_array_cursor_begin(info: &info->array_info, root, c: &c->cursor); |
245 | if (r) |
246 | return r; |
247 | |
248 | dm_array_cursor_get_value(c: &c->cursor, value_le: (void **) &value); |
249 | c->array_index = 0; |
250 | c->bit_index = 0; |
251 | c->current_bits = le64_to_cpu(*value); |
252 | |
253 | return r; |
254 | } |
255 | EXPORT_SYMBOL_GPL(dm_bitset_cursor_begin); |
256 | |
257 | void dm_bitset_cursor_end(struct dm_bitset_cursor *c) |
258 | { |
259 | return dm_array_cursor_end(c: &c->cursor); |
260 | } |
261 | EXPORT_SYMBOL_GPL(dm_bitset_cursor_end); |
262 | |
263 | int dm_bitset_cursor_next(struct dm_bitset_cursor *c) |
264 | { |
265 | int r = 0; |
266 | |
267 | if (!c->entries_remaining) |
268 | return -ENODATA; |
269 | |
270 | c->entries_remaining--; |
271 | if (++c->bit_index > 63) |
272 | r = cursor_next_array_entry(c); |
273 | |
274 | return r; |
275 | } |
276 | EXPORT_SYMBOL_GPL(dm_bitset_cursor_next); |
277 | |
278 | int dm_bitset_cursor_skip(struct dm_bitset_cursor *c, uint32_t count) |
279 | { |
280 | int r; |
281 | __le64 *value; |
282 | uint32_t nr_array_skip; |
283 | uint32_t remaining_in_word = 64 - c->bit_index; |
284 | |
285 | if (c->entries_remaining < count) |
286 | return -ENODATA; |
287 | |
288 | if (count < remaining_in_word) { |
289 | c->bit_index += count; |
290 | c->entries_remaining -= count; |
291 | return 0; |
292 | |
293 | } else { |
294 | c->entries_remaining -= remaining_in_word; |
295 | count -= remaining_in_word; |
296 | } |
297 | |
298 | nr_array_skip = (count / 64) + 1; |
299 | r = dm_array_cursor_skip(c: &c->cursor, count: nr_array_skip); |
300 | if (r) |
301 | return r; |
302 | |
303 | dm_array_cursor_get_value(c: &c->cursor, value_le: (void **) &value); |
304 | c->entries_remaining -= count; |
305 | c->array_index += nr_array_skip; |
306 | c->bit_index = count & 63; |
307 | c->current_bits = le64_to_cpu(*value); |
308 | |
309 | return 0; |
310 | } |
311 | EXPORT_SYMBOL_GPL(dm_bitset_cursor_skip); |
312 | |
313 | bool dm_bitset_cursor_get_value(struct dm_bitset_cursor *c) |
314 | { |
315 | return test_bit(c->bit_index, (unsigned long *) &c->current_bits); |
316 | } |
317 | EXPORT_SYMBOL_GPL(dm_bitset_cursor_get_value); |
318 | |
319 | /*----------------------------------------------------------------*/ |
320 | |