]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*- |
2 | * BSD LICENSE | |
3 | * | |
4 | * Copyright (c) Intel Corporation. | |
5 | * All rights reserved. | |
6 | * | |
7 | * Redistribution and use in source and binary forms, with or without | |
8 | * modification, are permitted provided that the following conditions | |
9 | * are met: | |
10 | * | |
11 | * * Redistributions of source code must retain the above copyright | |
12 | * notice, this list of conditions and the following disclaimer. | |
13 | * * Redistributions in binary form must reproduce the above copyright | |
14 | * notice, this list of conditions and the following disclaimer in | |
15 | * the documentation and/or other materials provided with the | |
16 | * distribution. | |
17 | * * Neither the name of Intel Corporation nor the names of its | |
18 | * contributors may be used to endorse or promote products derived | |
19 | * from this software without specific prior written permission. | |
20 | * | |
21 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
22 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
23 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
24 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
25 | * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
26 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
27 | * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
28 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
29 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
30 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
31 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
32 | */ | |
33 | ||
11fdf7f2 TL |
34 | #include "spdk/stdinc.h" |
35 | ||
7c673cae FG |
36 | #include "spdk/bit_array.h" |
37 | #include "spdk/env.h" | |
38 | ||
7c673cae FG |
39 | #include "spdk/likely.h" |
40 | #include "spdk/util.h" | |
41 | ||
42 | typedef uint64_t spdk_bit_array_word; | |
43 | #define SPDK_BIT_ARRAY_WORD_TZCNT(x) (__builtin_ctzll(x)) | |
11fdf7f2 | 44 | #define SPDK_BIT_ARRAY_WORD_POPCNT(x) (__builtin_popcountll(x)) |
7c673cae FG |
45 | #define SPDK_BIT_ARRAY_WORD_C(x) ((spdk_bit_array_word)(x)) |
46 | #define SPDK_BIT_ARRAY_WORD_BYTES sizeof(spdk_bit_array_word) | |
47 | #define SPDK_BIT_ARRAY_WORD_BITS (SPDK_BIT_ARRAY_WORD_BYTES * 8) | |
48 | #define SPDK_BIT_ARRAY_WORD_INDEX_SHIFT spdk_u32log2(SPDK_BIT_ARRAY_WORD_BITS) | |
49 | #define SPDK_BIT_ARRAY_WORD_INDEX_MASK ((1u << SPDK_BIT_ARRAY_WORD_INDEX_SHIFT) - 1) | |
50 | ||
51 | struct spdk_bit_array { | |
52 | uint32_t bit_count; | |
53 | spdk_bit_array_word words[]; | |
54 | }; | |
55 | ||
56 | struct spdk_bit_array * | |
57 | spdk_bit_array_create(uint32_t num_bits) | |
58 | { | |
59 | struct spdk_bit_array *ba = NULL; | |
60 | ||
61 | spdk_bit_array_resize(&ba, num_bits); | |
62 | ||
63 | return ba; | |
64 | } | |
65 | ||
66 | void | |
67 | spdk_bit_array_free(struct spdk_bit_array **bap) | |
68 | { | |
69 | struct spdk_bit_array *ba; | |
70 | ||
71 | if (!bap) { | |
72 | return; | |
73 | } | |
74 | ||
75 | ba = *bap; | |
76 | *bap = NULL; | |
9f95a23c | 77 | spdk_free(ba); |
7c673cae FG |
78 | } |
79 | ||
80 | static inline uint32_t | |
f67539c2 | 81 | bit_array_word_count(uint32_t num_bits) |
7c673cae FG |
82 | { |
83 | return (num_bits + SPDK_BIT_ARRAY_WORD_BITS - 1) >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT; | |
84 | } | |
85 | ||
86 | static inline spdk_bit_array_word | |
f67539c2 | 87 | bit_array_word_mask(uint32_t num_bits) |
7c673cae FG |
88 | { |
89 | assert(num_bits < SPDK_BIT_ARRAY_WORD_BITS); | |
90 | return (SPDK_BIT_ARRAY_WORD_C(1) << num_bits) - 1; | |
91 | } | |
92 | ||
93 | int | |
94 | spdk_bit_array_resize(struct spdk_bit_array **bap, uint32_t num_bits) | |
95 | { | |
96 | struct spdk_bit_array *new_ba; | |
97 | uint32_t old_word_count, new_word_count; | |
98 | size_t new_size; | |
99 | ||
11fdf7f2 TL |
100 | /* |
101 | * Max number of bits allowed is UINT32_MAX - 1, because we use UINT32_MAX to denote | |
102 | * when a set or cleared bit cannot be found. | |
103 | */ | |
104 | if (!bap || num_bits == UINT32_MAX) { | |
7c673cae FG |
105 | return -EINVAL; |
106 | } | |
107 | ||
f67539c2 | 108 | new_word_count = bit_array_word_count(num_bits); |
7c673cae FG |
109 | new_size = offsetof(struct spdk_bit_array, words) + new_word_count * SPDK_BIT_ARRAY_WORD_BYTES; |
110 | ||
111 | /* | |
112 | * Always keep one extra word with a 0 and a 1 past the actual required size so that the | |
113 | * find_first functions can just keep going until they match. | |
114 | */ | |
115 | new_size += SPDK_BIT_ARRAY_WORD_BYTES; | |
116 | ||
9f95a23c | 117 | new_ba = (struct spdk_bit_array *)spdk_realloc(*bap, new_size, 64); |
7c673cae FG |
118 | if (!new_ba) { |
119 | return -ENOMEM; | |
120 | } | |
121 | ||
122 | /* | |
123 | * Set up special extra word (see above comment about find_first_clear). | |
124 | * | |
125 | * This is set to 0b10 so that find_first_clear will find a 0 at the very first | |
126 | * bit past the end of the buffer, and find_first_set will find a 1 at the next bit | |
127 | * past that. | |
128 | */ | |
129 | new_ba->words[new_word_count] = 0x2; | |
130 | ||
131 | if (*bap == NULL) { | |
132 | old_word_count = 0; | |
133 | new_ba->bit_count = 0; | |
134 | } else { | |
f67539c2 | 135 | old_word_count = bit_array_word_count(new_ba->bit_count); |
7c673cae FG |
136 | } |
137 | ||
138 | if (new_word_count > old_word_count) { | |
139 | /* Zero out new entries */ | |
140 | memset(&new_ba->words[old_word_count], 0, | |
141 | (new_word_count - old_word_count) * SPDK_BIT_ARRAY_WORD_BYTES); | |
142 | } else if (new_word_count == old_word_count && num_bits < new_ba->bit_count) { | |
143 | /* Make sure any existing partial last word is cleared beyond the new num_bits. */ | |
144 | uint32_t last_word_bits; | |
145 | spdk_bit_array_word mask; | |
146 | ||
147 | last_word_bits = num_bits & SPDK_BIT_ARRAY_WORD_INDEX_MASK; | |
f67539c2 | 148 | mask = bit_array_word_mask(last_word_bits); |
7c673cae FG |
149 | new_ba->words[old_word_count - 1] &= mask; |
150 | } | |
151 | ||
152 | new_ba->bit_count = num_bits; | |
153 | *bap = new_ba; | |
154 | return 0; | |
155 | } | |
156 | ||
157 | uint32_t | |
158 | spdk_bit_array_capacity(const struct spdk_bit_array *ba) | |
159 | { | |
160 | return ba->bit_count; | |
161 | } | |
162 | ||
163 | static inline int | |
f67539c2 TL |
164 | bit_array_get_word(const struct spdk_bit_array *ba, uint32_t bit_index, |
165 | uint32_t *word_index, uint32_t *word_bit_index) | |
7c673cae FG |
166 | { |
167 | if (spdk_unlikely(bit_index >= ba->bit_count)) { | |
168 | return -EINVAL; | |
169 | } | |
170 | ||
171 | *word_index = bit_index >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT; | |
172 | *word_bit_index = bit_index & SPDK_BIT_ARRAY_WORD_INDEX_MASK; | |
173 | ||
174 | return 0; | |
175 | } | |
176 | ||
177 | bool | |
178 | spdk_bit_array_get(const struct spdk_bit_array *ba, uint32_t bit_index) | |
179 | { | |
180 | uint32_t word_index, word_bit_index; | |
181 | ||
f67539c2 | 182 | if (bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) { |
7c673cae FG |
183 | return false; |
184 | } | |
185 | ||
186 | return (ba->words[word_index] >> word_bit_index) & 1U; | |
187 | } | |
188 | ||
189 | int | |
190 | spdk_bit_array_set(struct spdk_bit_array *ba, uint32_t bit_index) | |
191 | { | |
192 | uint32_t word_index, word_bit_index; | |
193 | ||
f67539c2 | 194 | if (bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) { |
7c673cae FG |
195 | return -EINVAL; |
196 | } | |
197 | ||
198 | ba->words[word_index] |= (SPDK_BIT_ARRAY_WORD_C(1) << word_bit_index); | |
199 | return 0; | |
200 | } | |
201 | ||
202 | void | |
203 | spdk_bit_array_clear(struct spdk_bit_array *ba, uint32_t bit_index) | |
204 | { | |
205 | uint32_t word_index, word_bit_index; | |
206 | ||
f67539c2 | 207 | if (bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) { |
7c673cae FG |
208 | /* |
209 | * Clearing past the end of the bit array is a no-op, since bit past the end | |
210 | * are implicitly 0. | |
211 | */ | |
212 | return; | |
213 | } | |
214 | ||
215 | ba->words[word_index] &= ~(SPDK_BIT_ARRAY_WORD_C(1) << word_bit_index); | |
216 | } | |
217 | ||
218 | static inline uint32_t | |
f67539c2 TL |
219 | bit_array_find_first(const struct spdk_bit_array *ba, uint32_t start_bit_index, |
220 | spdk_bit_array_word xor_mask) | |
7c673cae FG |
221 | { |
222 | uint32_t word_index, first_word_bit_index; | |
223 | spdk_bit_array_word word, first_word_mask; | |
224 | const spdk_bit_array_word *words, *cur_word; | |
225 | ||
226 | if (spdk_unlikely(start_bit_index >= ba->bit_count)) { | |
227 | return ba->bit_count; | |
228 | } | |
229 | ||
230 | word_index = start_bit_index >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT; | |
231 | words = ba->words; | |
232 | cur_word = &words[word_index]; | |
233 | ||
234 | /* | |
235 | * Special case for first word: skip start_bit_index % SPDK_BIT_ARRAY_WORD_BITS bits | |
236 | * within the first word. | |
237 | */ | |
238 | first_word_bit_index = start_bit_index & SPDK_BIT_ARRAY_WORD_INDEX_MASK; | |
f67539c2 | 239 | first_word_mask = bit_array_word_mask(first_word_bit_index); |
7c673cae FG |
240 | |
241 | word = (*cur_word ^ xor_mask) & ~first_word_mask; | |
242 | ||
243 | /* | |
244 | * spdk_bit_array_resize() guarantees that an extra word with a 1 and a 0 will always be | |
245 | * at the end of the words[] array, so just keep going until a word matches. | |
246 | */ | |
247 | while (word == 0) { | |
248 | word = *++cur_word ^ xor_mask; | |
249 | } | |
250 | ||
251 | return ((uintptr_t)cur_word - (uintptr_t)words) * 8 + SPDK_BIT_ARRAY_WORD_TZCNT(word); | |
252 | } | |
253 | ||
254 | ||
255 | uint32_t | |
256 | spdk_bit_array_find_first_set(const struct spdk_bit_array *ba, uint32_t start_bit_index) | |
257 | { | |
258 | uint32_t bit_index; | |
259 | ||
f67539c2 | 260 | bit_index = bit_array_find_first(ba, start_bit_index, 0); |
7c673cae FG |
261 | |
262 | /* | |
263 | * If we ran off the end of the array and found the 1 bit in the extra word, | |
264 | * return UINT32_MAX to indicate no actual 1 bits were found. | |
265 | */ | |
266 | if (bit_index >= ba->bit_count) { | |
267 | bit_index = UINT32_MAX; | |
268 | } | |
269 | ||
270 | return bit_index; | |
271 | } | |
272 | ||
273 | uint32_t | |
274 | spdk_bit_array_find_first_clear(const struct spdk_bit_array *ba, uint32_t start_bit_index) | |
275 | { | |
11fdf7f2 TL |
276 | uint32_t bit_index; |
277 | ||
f67539c2 | 278 | bit_index = bit_array_find_first(ba, start_bit_index, SPDK_BIT_ARRAY_WORD_C(-1)); |
11fdf7f2 TL |
279 | |
280 | /* | |
281 | * If we ran off the end of the array and found the 0 bit in the extra word, | |
282 | * return UINT32_MAX to indicate no actual 0 bits were found. | |
283 | */ | |
284 | if (bit_index >= ba->bit_count) { | |
285 | bit_index = UINT32_MAX; | |
286 | } | |
287 | ||
288 | return bit_index; | |
289 | } | |
290 | ||
291 | uint32_t | |
292 | spdk_bit_array_count_set(const struct spdk_bit_array *ba) | |
293 | { | |
294 | const spdk_bit_array_word *cur_word = ba->words; | |
f67539c2 | 295 | uint32_t word_count = bit_array_word_count(ba->bit_count); |
11fdf7f2 TL |
296 | uint32_t set_count = 0; |
297 | ||
298 | while (word_count--) { | |
299 | /* | |
300 | * No special treatment is needed for the last (potentially partial) word, since | |
301 | * spdk_bit_array_resize() makes sure the bits past bit_count are cleared. | |
302 | */ | |
303 | set_count += SPDK_BIT_ARRAY_WORD_POPCNT(*cur_word++); | |
304 | } | |
305 | ||
306 | return set_count; | |
307 | } | |
308 | ||
309 | uint32_t | |
310 | spdk_bit_array_count_clear(const struct spdk_bit_array *ba) | |
311 | { | |
312 | return ba->bit_count - spdk_bit_array_count_set(ba); | |
7c673cae | 313 | } |
9f95a23c TL |
314 | |
315 | void | |
316 | spdk_bit_array_store_mask(const struct spdk_bit_array *ba, void *mask) | |
317 | { | |
318 | uint32_t size, i; | |
319 | uint32_t num_bits = spdk_bit_array_capacity(ba); | |
320 | ||
321 | size = num_bits / CHAR_BIT; | |
322 | memcpy(mask, ba->words, size); | |
323 | ||
324 | for (i = 0; i < num_bits % CHAR_BIT; i++) { | |
325 | if (spdk_bit_array_get(ba, i + size * CHAR_BIT)) { | |
326 | ((uint8_t *)mask)[size] |= (1U << i); | |
327 | } else { | |
328 | ((uint8_t *)mask)[size] &= ~(1U << i); | |
329 | } | |
330 | } | |
331 | } | |
332 | ||
333 | void | |
334 | spdk_bit_array_load_mask(struct spdk_bit_array *ba, const void *mask) | |
335 | { | |
336 | uint32_t size, i; | |
337 | uint32_t num_bits = spdk_bit_array_capacity(ba); | |
338 | ||
339 | size = num_bits / CHAR_BIT; | |
340 | memcpy(ba->words, mask, size); | |
341 | ||
342 | for (i = 0; i < num_bits % CHAR_BIT; i++) { | |
343 | if (((uint8_t *)mask)[size] & (1U << i)) { | |
344 | spdk_bit_array_set(ba, i + size * CHAR_BIT); | |
345 | } else { | |
346 | spdk_bit_array_clear(ba, i + size * CHAR_BIT); | |
347 | } | |
348 | } | |
349 | } | |
350 | ||
351 | void | |
352 | spdk_bit_array_clear_mask(struct spdk_bit_array *ba) | |
353 | { | |
354 | uint32_t size, i; | |
355 | uint32_t num_bits = spdk_bit_array_capacity(ba); | |
356 | ||
357 | size = num_bits / CHAR_BIT; | |
358 | memset(ba->words, 0, size); | |
359 | ||
360 | for (i = 0; i < num_bits % CHAR_BIT; i++) { | |
361 | spdk_bit_array_clear(ba, i + size * CHAR_BIT); | |
362 | } | |
363 | } |