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 | #ifndef _LINUX_DM_BITSET_H |
8 | #define _LINUX_DM_BITSET_H |
9 | |
10 | #include "dm-array.h" |
11 | |
12 | /*----------------------------------------------------------------*/ |
13 | |
14 | /* |
15 | * This bitset type is a thin wrapper round a dm_array of 64bit words. It |
16 | * uses a tiny, one word cache to reduce the number of array lookups and so |
17 | * increase performance. |
18 | * |
19 | * Like the dm-array that it's based on, the caller needs to keep track of |
20 | * the size of the bitset separately. The underlying dm-array implicitly |
21 | * knows how many words it's storing and will return -ENODATA if you try |
22 | * and access an out of bounds word. However, an out of bounds bit in the |
23 | * final word will _not_ be detected, you have been warned. |
24 | * |
25 | * Bits are indexed from zero. |
26 | |
27 | * Typical use: |
28 | * |
29 | * a) Initialise a dm_disk_bitset structure with dm_disk_bitset_init(). |
30 | * This describes the bitset and includes the cache. It's not called it |
31 | * dm_bitset_info in line with other data structures because it does |
32 | * include instance data. |
33 | * |
34 | * b) Get yourself a root. The root is the index of a block of data on the |
35 | * disk that holds a particular instance of an bitset. You may have a |
36 | * pre existing root in your metadata that you wish to use, or you may |
37 | * want to create a brand new, empty bitset with dm_bitset_empty(). |
38 | * |
39 | * Like the other data structures in this library, dm_bitset objects are |
40 | * immutable between transactions. Update functions will return you the |
41 | * root for a _new_ array. If you've incremented the old root, via |
42 | * dm_tm_inc(), before calling the update function you may continue to use |
43 | * it in parallel with the new root. |
44 | * |
45 | * Even read operations may trigger the cache to be flushed and as such |
46 | * return a root for a new, updated bitset. |
47 | * |
48 | * c) resize a bitset with dm_bitset_resize(). |
49 | * |
50 | * d) Set a bit with dm_bitset_set_bit(). |
51 | * |
52 | * e) Clear a bit with dm_bitset_clear_bit(). |
53 | * |
54 | * f) Test a bit with dm_bitset_test_bit(). |
55 | * |
56 | * g) Flush all updates from the cache with dm_bitset_flush(). |
57 | * |
58 | * h) Destroy the bitset with dm_bitset_del(). This tells the transaction |
59 | * manager that you're no longer using this data structure so it can |
60 | * recycle it's blocks. (dm_bitset_dec() would be a better name for it, |
61 | * but del is in keeping with dm_btree_del()). |
62 | */ |
63 | |
64 | /* |
65 | * Opaque object. Unlike dm_array_info, you should have one of these per |
66 | * bitset. Initialise with dm_disk_bitset_init(). |
67 | */ |
68 | struct dm_disk_bitset { |
69 | struct dm_array_info array_info; |
70 | |
71 | uint32_t current_index; |
72 | uint64_t current_bits; |
73 | |
74 | bool current_index_set:1; |
75 | bool dirty:1; |
76 | }; |
77 | |
78 | /* |
79 | * Sets up a dm_disk_bitset structure. You don't need to do anything with |
80 | * this structure when you finish using it. |
81 | * |
82 | * tm - the transaction manager that should supervise this structure |
83 | * info - the structure being initialised |
84 | */ |
85 | void dm_disk_bitset_init(struct dm_transaction_manager *tm, |
86 | struct dm_disk_bitset *info); |
87 | |
88 | /* |
89 | * Create an empty, zero length bitset. |
90 | * |
91 | * info - describes the bitset |
92 | * new_root - on success, points to the new root block |
93 | */ |
94 | int dm_bitset_empty(struct dm_disk_bitset *info, dm_block_t *new_root); |
95 | |
96 | /* |
97 | * Creates a new bitset populated with values provided by a callback |
98 | * function. This is more efficient than creating an empty bitset, |
99 | * resizing, and then setting values since that process incurs a lot of |
100 | * copying. |
101 | * |
102 | * info - describes the array |
103 | * root - the root block of the array on disk |
104 | * size - the number of entries in the array |
105 | * fn - the callback |
106 | * context - passed to the callback |
107 | */ |
108 | typedef int (*bit_value_fn)(uint32_t index, bool *value, void *context); |
109 | int dm_bitset_new(struct dm_disk_bitset *info, dm_block_t *root, |
110 | uint32_t size, bit_value_fn fn, void *context); |
111 | |
112 | /* |
113 | * Resize the bitset. |
114 | * |
115 | * info - describes the bitset |
116 | * old_root - the root block of the array on disk |
117 | * old_nr_entries - the number of bits in the old bitset |
118 | * new_nr_entries - the number of bits you want in the new bitset |
119 | * default_value - the value for any new bits |
120 | * new_root - on success, points to the new root block |
121 | */ |
122 | int dm_bitset_resize(struct dm_disk_bitset *info, dm_block_t old_root, |
123 | uint32_t old_nr_entries, uint32_t new_nr_entries, |
124 | bool default_value, dm_block_t *new_root); |
125 | |
126 | /* |
127 | * Frees the bitset. |
128 | */ |
129 | int dm_bitset_del(struct dm_disk_bitset *info, dm_block_t root); |
130 | |
131 | /* |
132 | * Set a bit. |
133 | * |
134 | * info - describes the bitset |
135 | * root - the root block of the bitset |
136 | * index - the bit index |
137 | * new_root - on success, points to the new root block |
138 | * |
139 | * -ENODATA will be returned if the index is out of bounds. |
140 | */ |
141 | int dm_bitset_set_bit(struct dm_disk_bitset *info, dm_block_t root, |
142 | uint32_t index, dm_block_t *new_root); |
143 | |
144 | /* |
145 | * Clears a bit. |
146 | * |
147 | * info - describes the bitset |
148 | * root - the root block of the bitset |
149 | * index - the bit index |
150 | * new_root - on success, points to the new root block |
151 | * |
152 | * -ENODATA will be returned if the index is out of bounds. |
153 | */ |
154 | int dm_bitset_clear_bit(struct dm_disk_bitset *info, dm_block_t root, |
155 | uint32_t index, dm_block_t *new_root); |
156 | |
157 | /* |
158 | * Tests a bit. |
159 | * |
160 | * info - describes the bitset |
161 | * root - the root block of the bitset |
162 | * index - the bit index |
163 | * new_root - on success, points to the new root block (cached values may have been written) |
164 | * result - the bit value you're after |
165 | * |
166 | * -ENODATA will be returned if the index is out of bounds. |
167 | */ |
168 | int dm_bitset_test_bit(struct dm_disk_bitset *info, dm_block_t root, |
169 | uint32_t index, dm_block_t *new_root, bool *result); |
170 | |
171 | /* |
172 | * Flush any cached changes to disk. |
173 | * |
174 | * info - describes the bitset |
175 | * root - the root block of the bitset |
176 | * new_root - on success, points to the new root block |
177 | */ |
178 | int dm_bitset_flush(struct dm_disk_bitset *info, dm_block_t root, |
179 | dm_block_t *new_root); |
180 | |
181 | struct dm_bitset_cursor { |
182 | struct dm_disk_bitset *info; |
183 | struct dm_array_cursor cursor; |
184 | |
185 | uint32_t entries_remaining; |
186 | uint32_t array_index; |
187 | uint32_t bit_index; |
188 | uint64_t current_bits; |
189 | }; |
190 | |
191 | /* |
192 | * Make sure you've flush any dm_disk_bitset and updated the root before |
193 | * using this. |
194 | */ |
195 | int dm_bitset_cursor_begin(struct dm_disk_bitset *info, |
196 | dm_block_t root, uint32_t nr_entries, |
197 | struct dm_bitset_cursor *c); |
198 | void dm_bitset_cursor_end(struct dm_bitset_cursor *c); |
199 | |
200 | int dm_bitset_cursor_next(struct dm_bitset_cursor *c); |
201 | int dm_bitset_cursor_skip(struct dm_bitset_cursor *c, uint32_t count); |
202 | bool dm_bitset_cursor_get_value(struct dm_bitset_cursor *c); |
203 | |
204 | /*----------------------------------------------------------------*/ |
205 | |
206 | #endif /* _LINUX_DM_BITSET_H */ |
207 | |