Line data Source code
1 : /* SPDX-License-Identifier: BSD-3-Clause
2 : * Copyright (C) 2016 Intel Corporation.
3 : * All rights reserved.
4 : */
5 :
6 : #include "spdk/stdinc.h"
7 :
8 : #include "spdk/bit_array.h"
9 : #include "spdk/bit_pool.h"
10 : #include "spdk/env.h"
11 :
12 : #include "spdk/likely.h"
13 : #include "spdk/util.h"
14 :
15 : typedef uint64_t spdk_bit_array_word;
16 : #define SPDK_BIT_ARRAY_WORD_TZCNT(x) (__builtin_ctzll(x))
17 : #define SPDK_BIT_ARRAY_WORD_POPCNT(x) (__builtin_popcountll(x))
18 : #define SPDK_BIT_ARRAY_WORD_C(x) ((spdk_bit_array_word)(x))
19 : #define SPDK_BIT_ARRAY_WORD_BYTES sizeof(spdk_bit_array_word)
20 : #define SPDK_BIT_ARRAY_WORD_BITS (SPDK_BIT_ARRAY_WORD_BYTES * 8)
21 : #define SPDK_BIT_ARRAY_WORD_INDEX_SHIFT spdk_u32log2(SPDK_BIT_ARRAY_WORD_BITS)
22 : #define SPDK_BIT_ARRAY_WORD_INDEX_MASK ((1u << SPDK_BIT_ARRAY_WORD_INDEX_SHIFT) - 1)
23 :
24 : struct spdk_bit_array {
25 : uint32_t bit_count;
26 : spdk_bit_array_word words[];
27 : };
28 :
29 : struct spdk_bit_array *
30 4040 : spdk_bit_array_create(uint32_t num_bits)
31 : {
32 4040 : struct spdk_bit_array *ba = NULL;
33 :
34 4040 : spdk_bit_array_resize(&ba, num_bits);
35 :
36 4040 : return ba;
37 : }
38 :
39 : void
40 4058 : spdk_bit_array_free(struct spdk_bit_array **bap)
41 : {
42 : struct spdk_bit_array *ba;
43 :
44 4058 : if (!bap) {
45 1 : return;
46 : }
47 :
48 4057 : ba = *bap;
49 4057 : *bap = NULL;
50 4057 : spdk_free(ba);
51 4058 : }
52 :
53 : static inline uint32_t
54 12858 : bit_array_word_count(uint32_t num_bits)
55 : {
56 12858 : return (num_bits + SPDK_BIT_ARRAY_WORD_BITS - 1) >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT;
57 : }
58 :
59 : static inline spdk_bit_array_word
60 18388 : bit_array_word_mask(uint32_t num_bits)
61 : {
62 18388 : assert(num_bits < SPDK_BIT_ARRAY_WORD_BITS);
63 18388 : return (SPDK_BIT_ARRAY_WORD_C(1) << num_bits) - 1;
64 : }
65 :
66 : int
67 7746 : spdk_bit_array_resize(struct spdk_bit_array **bap, uint32_t num_bits)
68 : {
69 : struct spdk_bit_array *new_ba;
70 : uint32_t old_word_count, new_word_count;
71 : size_t new_size;
72 :
73 : /*
74 : * Max number of bits allowed is UINT32_MAX - 1, because we use UINT32_MAX to denote
75 : * when a set or cleared bit cannot be found.
76 : */
77 7746 : if (!bap || num_bits == UINT32_MAX) {
78 1 : return -EINVAL;
79 : }
80 :
81 7745 : new_word_count = bit_array_word_count(num_bits);
82 7745 : new_size = offsetof(struct spdk_bit_array, words) + new_word_count * SPDK_BIT_ARRAY_WORD_BYTES;
83 :
84 : /*
85 : * Always keep one extra word with a 0 and a 1 past the actual required size so that the
86 : * find_first functions can just keep going until they match.
87 : */
88 7745 : new_size += SPDK_BIT_ARRAY_WORD_BYTES;
89 :
90 7745 : new_ba = (struct spdk_bit_array *)spdk_realloc(*bap, new_size, 64);
91 7745 : if (!new_ba) {
92 0 : return -ENOMEM;
93 : }
94 :
95 : /*
96 : * Set up special extra word (see above comment about find_first_clear).
97 : *
98 : * This is set to 0b10 so that find_first_clear will find a 0 at the very first
99 : * bit past the end of the buffer, and find_first_set will find a 1 at the next bit
100 : * past that.
101 : */
102 7745 : new_ba->words[new_word_count] = 0x2;
103 :
104 7745 : if (*bap == NULL) {
105 4040 : old_word_count = 0;
106 4040 : new_ba->bit_count = 0;
107 4040 : } else {
108 3705 : old_word_count = bit_array_word_count(new_ba->bit_count);
109 : }
110 :
111 7745 : if (new_word_count > old_word_count) {
112 : /* Zero out new entries */
113 8298 : memset(&new_ba->words[old_word_count], 0,
114 4149 : (new_word_count - old_word_count) * SPDK_BIT_ARRAY_WORD_BYTES);
115 7745 : } else if (new_word_count == old_word_count && num_bits < new_ba->bit_count) {
116 : /* Make sure any existing partial last word is cleared beyond the new num_bits. */
117 : uint32_t last_word_bits;
118 : spdk_bit_array_word mask;
119 :
120 6 : last_word_bits = num_bits & SPDK_BIT_ARRAY_WORD_INDEX_MASK;
121 6 : mask = bit_array_word_mask(last_word_bits);
122 6 : new_ba->words[old_word_count - 1] &= mask;
123 6 : }
124 :
125 7745 : new_ba->bit_count = num_bits;
126 7745 : *bap = new_ba;
127 7745 : return 0;
128 7746 : }
129 :
130 : uint32_t
131 17043 : spdk_bit_array_capacity(const struct spdk_bit_array *ba)
132 : {
133 17043 : return ba->bit_count;
134 : }
135 :
136 : static inline int
137 173386 : bit_array_get_word(const struct spdk_bit_array *ba, uint32_t bit_index,
138 : uint32_t *word_index, uint32_t *word_bit_index)
139 : {
140 173386 : if (spdk_unlikely(bit_index >= ba->bit_count)) {
141 142 : return -EINVAL;
142 : }
143 :
144 173244 : *word_index = bit_index >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT;
145 173244 : *word_bit_index = bit_index & SPDK_BIT_ARRAY_WORD_INDEX_MASK;
146 :
147 173244 : return 0;
148 173386 : }
149 :
150 : bool
151 57964 : spdk_bit_array_get(const struct spdk_bit_array *ba, uint32_t bit_index)
152 : {
153 : uint32_t word_index, word_bit_index;
154 :
155 57964 : if (bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) {
156 140 : return false;
157 : }
158 :
159 57824 : return (ba->words[word_index] >> word_bit_index) & 1U;
160 57964 : }
161 :
162 : int
163 103200 : spdk_bit_array_set(struct spdk_bit_array *ba, uint32_t bit_index)
164 : {
165 : uint32_t word_index, word_bit_index;
166 :
167 103200 : if (bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) {
168 1 : return -EINVAL;
169 : }
170 :
171 103199 : ba->words[word_index] |= (SPDK_BIT_ARRAY_WORD_C(1) << word_bit_index);
172 103199 : return 0;
173 103200 : }
174 :
175 : void
176 12222 : spdk_bit_array_clear(struct spdk_bit_array *ba, uint32_t bit_index)
177 : {
178 : uint32_t word_index, word_bit_index;
179 :
180 12222 : if (bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) {
181 : /*
182 : * Clearing past the end of the bit array is a no-op, since bit past the end
183 : * are implicitly 0.
184 : */
185 1 : return;
186 : }
187 :
188 12221 : ba->words[word_index] &= ~(SPDK_BIT_ARRAY_WORD_C(1) << word_bit_index);
189 12222 : }
190 :
191 : static inline uint32_t
192 18385 : bit_array_find_first(const struct spdk_bit_array *ba, uint32_t start_bit_index,
193 : spdk_bit_array_word xor_mask)
194 : {
195 : uint32_t word_index, first_word_bit_index;
196 : spdk_bit_array_word word, first_word_mask;
197 : const spdk_bit_array_word *words, *cur_word;
198 :
199 18385 : if (spdk_unlikely(start_bit_index >= ba->bit_count)) {
200 3 : return ba->bit_count;
201 : }
202 :
203 18382 : word_index = start_bit_index >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT;
204 18382 : words = ba->words;
205 18382 : cur_word = &words[word_index];
206 :
207 : /*
208 : * Special case for first word: skip start_bit_index % SPDK_BIT_ARRAY_WORD_BITS bits
209 : * within the first word.
210 : */
211 18382 : first_word_bit_index = start_bit_index & SPDK_BIT_ARRAY_WORD_INDEX_MASK;
212 18382 : first_word_mask = bit_array_word_mask(first_word_bit_index);
213 :
214 18382 : word = (*cur_word ^ xor_mask) & ~first_word_mask;
215 :
216 : /*
217 : * spdk_bit_array_resize() guarantees that an extra word with a 1 and a 0 will always be
218 : * at the end of the words[] array, so just keep going until a word matches.
219 : */
220 24041 : while (word == 0) {
221 5659 : word = *++cur_word ^ xor_mask;
222 : }
223 :
224 18382 : return ((uintptr_t)cur_word - (uintptr_t)words) * 8 + SPDK_BIT_ARRAY_WORD_TZCNT(word);
225 18385 : }
226 :
227 :
228 : uint32_t
229 1726 : spdk_bit_array_find_first_set(const struct spdk_bit_array *ba, uint32_t start_bit_index)
230 : {
231 : uint32_t bit_index;
232 :
233 1726 : bit_index = bit_array_find_first(ba, start_bit_index, 0);
234 :
235 : /*
236 : * If we ran off the end of the array and found the 1 bit in the extra word,
237 : * return UINT32_MAX to indicate no actual 1 bits were found.
238 : */
239 1726 : if (bit_index >= ba->bit_count) {
240 373 : bit_index = UINT32_MAX;
241 373 : }
242 :
243 1726 : return bit_index;
244 : }
245 :
246 : uint32_t
247 16659 : spdk_bit_array_find_first_clear(const struct spdk_bit_array *ba, uint32_t start_bit_index)
248 : {
249 : uint32_t bit_index;
250 :
251 16659 : bit_index = bit_array_find_first(ba, start_bit_index, SPDK_BIT_ARRAY_WORD_C(-1));
252 :
253 : /*
254 : * If we ran off the end of the array and found the 0 bit in the extra word,
255 : * return UINT32_MAX to indicate no actual 0 bits were found.
256 : */
257 16659 : if (bit_index >= ba->bit_count) {
258 512 : bit_index = UINT32_MAX;
259 512 : }
260 :
261 16659 : return bit_index;
262 : }
263 :
264 : uint32_t
265 1408 : spdk_bit_array_count_set(const struct spdk_bit_array *ba)
266 : {
267 1408 : const spdk_bit_array_word *cur_word = ba->words;
268 1408 : uint32_t word_count = bit_array_word_count(ba->bit_count);
269 1408 : uint32_t set_count = 0;
270 :
271 13036 : while (word_count--) {
272 : /*
273 : * No special treatment is needed for the last (potentially partial) word, since
274 : * spdk_bit_array_resize() makes sure the bits past bit_count are cleared.
275 : */
276 11628 : set_count += SPDK_BIT_ARRAY_WORD_POPCNT(*cur_word++);
277 : }
278 :
279 1408 : return set_count;
280 : }
281 :
282 : uint32_t
283 1244 : spdk_bit_array_count_clear(const struct spdk_bit_array *ba)
284 : {
285 1244 : return ba->bit_count - spdk_bit_array_count_set(ba);
286 : }
287 :
288 : void
289 2845 : spdk_bit_array_store_mask(const struct spdk_bit_array *ba, void *mask)
290 : {
291 : uint32_t size, i;
292 2845 : uint32_t num_bits = spdk_bit_array_capacity(ba);
293 :
294 2845 : size = num_bits / CHAR_BIT;
295 2845 : memcpy(mask, ba->words, size);
296 :
297 2910 : for (i = 0; i < num_bits % CHAR_BIT; i++) {
298 65 : if (spdk_bit_array_get(ba, i + size * CHAR_BIT)) {
299 6 : ((uint8_t *)mask)[size] |= (1U << i);
300 6 : } else {
301 59 : ((uint8_t *)mask)[size] &= ~(1U << i);
302 : }
303 65 : }
304 2845 : }
305 :
306 : void
307 662 : spdk_bit_array_load_mask(struct spdk_bit_array *ba, const void *mask)
308 : {
309 : uint32_t size, i;
310 662 : uint32_t num_bits = spdk_bit_array_capacity(ba);
311 :
312 662 : size = num_bits / CHAR_BIT;
313 662 : memcpy(ba->words, mask, size);
314 :
315 667 : for (i = 0; i < num_bits % CHAR_BIT; i++) {
316 5 : if (((uint8_t *)mask)[size] & (1U << i)) {
317 1 : spdk_bit_array_set(ba, i + size * CHAR_BIT);
318 1 : } else {
319 4 : spdk_bit_array_clear(ba, i + size * CHAR_BIT);
320 : }
321 5 : }
322 662 : }
323 :
324 : void
325 1 : spdk_bit_array_clear_mask(struct spdk_bit_array *ba)
326 : {
327 : uint32_t size, i;
328 1 : uint32_t num_bits = spdk_bit_array_capacity(ba);
329 :
330 1 : size = num_bits / CHAR_BIT;
331 1 : memset(ba->words, 0, size);
332 :
333 6 : for (i = 0; i < num_bits % CHAR_BIT; i++) {
334 5 : spdk_bit_array_clear(ba, i + size * CHAR_BIT);
335 5 : }
336 1 : }
337 :
338 : struct spdk_bit_pool {
339 : struct spdk_bit_array *array;
340 : uint32_t lowest_free_bit;
341 : uint32_t free_count;
342 : };
343 :
344 : struct spdk_bit_pool *
345 10 : spdk_bit_pool_create(uint32_t num_bits)
346 : {
347 10 : struct spdk_bit_pool *pool = NULL;
348 : struct spdk_bit_array *array;
349 :
350 10 : array = spdk_bit_array_create(num_bits);
351 10 : if (array == NULL) {
352 0 : return NULL;
353 : }
354 :
355 10 : pool = calloc(1, sizeof(*pool));
356 10 : if (pool == NULL) {
357 0 : spdk_bit_array_free(&array);
358 0 : return NULL;
359 : }
360 :
361 10 : pool->array = array;
362 10 : pool->lowest_free_bit = 0;
363 10 : pool->free_count = num_bits;
364 :
365 10 : return pool;
366 10 : }
367 :
368 : struct spdk_bit_pool *
369 943 : spdk_bit_pool_create_from_array(struct spdk_bit_array *array)
370 : {
371 943 : struct spdk_bit_pool *pool = NULL;
372 :
373 943 : pool = calloc(1, sizeof(*pool));
374 943 : if (pool == NULL) {
375 0 : return NULL;
376 : }
377 :
378 943 : pool->array = array;
379 943 : pool->lowest_free_bit = spdk_bit_array_find_first_clear(array, 0);
380 943 : pool->free_count = spdk_bit_array_count_clear(array);
381 :
382 943 : return pool;
383 943 : }
384 :
385 : void
386 1008 : spdk_bit_pool_free(struct spdk_bit_pool **ppool)
387 : {
388 : struct spdk_bit_pool *pool;
389 :
390 1008 : if (!ppool) {
391 0 : return;
392 : }
393 :
394 1008 : pool = *ppool;
395 1008 : *ppool = NULL;
396 1008 : if (pool != NULL) {
397 953 : spdk_bit_array_free(&pool->array);
398 953 : free(pool);
399 953 : }
400 1008 : }
401 :
402 : int
403 0 : spdk_bit_pool_resize(struct spdk_bit_pool **ppool, uint32_t num_bits)
404 : {
405 : struct spdk_bit_pool *pool;
406 : int rc;
407 :
408 0 : assert(ppool != NULL);
409 :
410 0 : pool = *ppool;
411 0 : rc = spdk_bit_array_resize(&pool->array, num_bits);
412 0 : if (rc) {
413 0 : return rc;
414 : }
415 :
416 0 : pool->lowest_free_bit = spdk_bit_array_find_first_clear(pool->array, 0);
417 0 : pool->free_count = spdk_bit_array_count_clear(pool->array);
418 :
419 0 : return 0;
420 0 : }
421 :
422 : uint32_t
423 3860 : spdk_bit_pool_capacity(const struct spdk_bit_pool *pool)
424 : {
425 3860 : return spdk_bit_array_capacity(pool->array);
426 : }
427 :
428 : bool
429 20515 : spdk_bit_pool_is_allocated(const struct spdk_bit_pool *pool, uint32_t bit_index)
430 : {
431 20515 : return spdk_bit_array_get(pool->array, bit_index);
432 : }
433 :
434 : uint32_t
435 10283 : spdk_bit_pool_allocate_bit(struct spdk_bit_pool *pool)
436 : {
437 10283 : uint32_t bit_index = pool->lowest_free_bit;
438 :
439 10283 : if (bit_index == UINT32_MAX) {
440 0 : return UINT32_MAX;
441 : }
442 :
443 10283 : spdk_bit_array_set(pool->array, bit_index);
444 10283 : pool->lowest_free_bit = spdk_bit_array_find_first_clear(pool->array, bit_index);
445 10283 : pool->free_count--;
446 10283 : return bit_index;
447 10283 : }
448 :
449 : void
450 2996 : spdk_bit_pool_free_bit(struct spdk_bit_pool *pool, uint32_t bit_index)
451 : {
452 2996 : assert(spdk_bit_array_get(pool->array, bit_index) == true);
453 :
454 2996 : spdk_bit_array_clear(pool->array, bit_index);
455 2996 : if (pool->lowest_free_bit > bit_index) {
456 1584 : pool->lowest_free_bit = bit_index;
457 1584 : }
458 2996 : pool->free_count++;
459 2996 : }
460 :
461 : uint32_t
462 0 : spdk_bit_pool_count_allocated(const struct spdk_bit_pool *pool)
463 : {
464 0 : return spdk_bit_array_capacity(pool->array) - pool->free_count;
465 : }
466 :
467 : uint32_t
468 10 : spdk_bit_pool_count_free(const struct spdk_bit_pool *pool)
469 : {
470 10 : return pool->free_count;
471 : }
472 :
473 : void
474 829 : spdk_bit_pool_store_mask(const struct spdk_bit_pool *pool, void *mask)
475 : {
476 829 : spdk_bit_array_store_mask(pool->array, mask);
477 829 : }
478 :
479 : void
480 10 : spdk_bit_pool_load_mask(struct spdk_bit_pool *pool, const void *mask)
481 : {
482 10 : spdk_bit_array_load_mask(pool->array, mask);
483 10 : pool->lowest_free_bit = spdk_bit_array_find_first_clear(pool->array, 0);
484 10 : pool->free_count = spdk_bit_array_count_clear(pool->array);
485 10 : }
486 :
487 : void
488 0 : spdk_bit_pool_free_all_bits(struct spdk_bit_pool *pool)
489 : {
490 0 : spdk_bit_array_clear_mask(pool->array);
491 0 : pool->lowest_free_bit = 0;
492 0 : pool->free_count = spdk_bit_array_capacity(pool->array);
493 0 : }
|
