Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2010-2014 Intel Corporation
3 : : */
4 : :
5 : : #ifndef __INCLUDE_RTE_BITMAP_H__
6 : : #define __INCLUDE_RTE_BITMAP_H__
7 : :
8 : : /**
9 : : * @file
10 : : * RTE Bitmap
11 : : *
12 : : * The bitmap component provides a mechanism to manage large arrays of bits
13 : : * through bit get/set/clear and bit array scan operations.
14 : : *
15 : : * The bitmap scan operation is optimized for 64-bit CPUs using 64/128 byte cache
16 : : * lines. The bitmap is hierarchically organized using two arrays (array1 and
17 : : * array2), with each bit in array1 being associated with a full cache line
18 : : * (512/1024 bits) of bitmap bits, which are stored in array2: the bit in array1
19 : : * is set only when there is at least one bit set within its associated array2
20 : : * bits, otherwise the bit in array1 is cleared. The read and write operations
21 : : * for array1 and array2 are always done in slabs of 64 bits.
22 : : *
23 : : * This bitmap is not thread safe. For lock free operation on a specific bitmap
24 : : * instance, a single writer thread performing bit set/clear operations is
25 : : * allowed, only the writer thread can do bitmap scan operations, while there
26 : : * can be several reader threads performing bit get operations in parallel with
27 : : * the writer thread. When the use of locking primitives is acceptable, the
28 : : * serialization of the bit set/clear and bitmap scan operations needs to be
29 : : * enforced by the caller, while the bit get operation does not require locking
30 : : * the bitmap.
31 : : */
32 : :
33 : : #include <string.h>
34 : :
35 : : #include <rte_common.h>
36 : : #include <rte_config.h>
37 : : #include <rte_debug.h>
38 : : #include <rte_memory.h>
39 : : #include <rte_branch_prediction.h>
40 : : #include <rte_prefetch.h>
41 : :
42 : : #ifdef __cplusplus
43 : : extern "C" {
44 : : #endif
45 : :
46 : : /* Slab */
47 : : #define RTE_BITMAP_SLAB_BIT_SIZE 64
48 : : #define RTE_BITMAP_SLAB_BIT_SIZE_LOG2 6
49 : : #define RTE_BITMAP_SLAB_BIT_MASK (RTE_BITMAP_SLAB_BIT_SIZE - 1)
50 : :
51 : : /* Cache line (CL) */
52 : : #define RTE_BITMAP_CL_BIT_SIZE (RTE_CACHE_LINE_SIZE * 8)
53 : : #define RTE_BITMAP_CL_BIT_SIZE_LOG2 (RTE_CACHE_LINE_SIZE_LOG2 + 3)
54 : : #define RTE_BITMAP_CL_BIT_MASK (RTE_BITMAP_CL_BIT_SIZE - 1)
55 : :
56 : : #define RTE_BITMAP_CL_SLAB_SIZE (RTE_BITMAP_CL_BIT_SIZE / RTE_BITMAP_SLAB_BIT_SIZE)
57 : : #define RTE_BITMAP_CL_SLAB_SIZE_LOG2 (RTE_BITMAP_CL_BIT_SIZE_LOG2 - RTE_BITMAP_SLAB_BIT_SIZE_LOG2)
58 : : #define RTE_BITMAP_CL_SLAB_MASK (RTE_BITMAP_CL_SLAB_SIZE - 1)
59 : :
60 : : /** Bitmap data structure */
61 : : struct rte_bitmap {
62 : : /* Context for array1 and array2 */
63 : : uint64_t *array1; /**< Bitmap array1 */
64 : : uint64_t *array2; /**< Bitmap array2 */
65 : : uint32_t array1_size; /**< Number of 64-bit slabs in array1 that are actually used */
66 : : uint32_t array2_size; /**< Number of 64-bit slabs in array2 */
67 : :
68 : : /* Context for the "scan next" operation */
69 : : uint32_t index1; /**< Bitmap scan: Index of current array1 slab */
70 : : uint32_t offset1; /**< Bitmap scan: Offset of current bit within current array1 slab */
71 : : uint32_t index2; /**< Bitmap scan: Index of current array2 slab */
72 : : uint32_t go2; /**< Bitmap scan: Go/stop condition for current array2 cache line */
73 : :
74 : : /* Storage space for array1 and array2 */
75 : : uint8_t memory[];
76 : : };
77 : :
78 : : static inline void
79 : : __rte_bitmap_index1_inc(struct rte_bitmap *bmp)
80 : : {
81 : 159 : bmp->index1 = (bmp->index1 + 1) & (bmp->array1_size - 1);
82 : 2 : }
83 : :
84 : : static inline uint64_t
85 : : __rte_bitmap_mask1_get(struct rte_bitmap *bmp)
86 : : {
87 : 222 : return (~1llu) << bmp->offset1;
88 : : }
89 : :
90 : : static inline void
91 : : __rte_bitmap_index2_set(struct rte_bitmap *bmp)
92 : : {
93 : 230 : bmp->index2 = (((bmp->index1 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2) + bmp->offset1) << RTE_BITMAP_CL_SLAB_SIZE_LOG2);
94 : : }
95 : :
96 : : static inline uint32_t
97 : 3 : __rte_bitmap_get_memory_footprint(uint32_t n_bits,
98 : : uint32_t *array1_byte_offset, uint32_t *array1_slabs,
99 : : uint32_t *array2_byte_offset, uint32_t *array2_slabs)
100 : : {
101 : : uint32_t n_slabs_context, n_slabs_array1, n_cache_lines_context_and_array1;
102 : : uint32_t n_cache_lines_array2;
103 : : uint32_t n_bytes_total;
104 : :
105 : 11 : n_cache_lines_array2 = (n_bits + RTE_BITMAP_CL_BIT_SIZE - 1) / RTE_BITMAP_CL_BIT_SIZE;
106 [ + - ]: 11 : n_slabs_array1 = (n_cache_lines_array2 + RTE_BITMAP_SLAB_BIT_SIZE - 1) / RTE_BITMAP_SLAB_BIT_SIZE;
107 : : n_slabs_array1 = rte_align32pow2(n_slabs_array1);
108 : : n_slabs_context = (sizeof(struct rte_bitmap) + (RTE_BITMAP_SLAB_BIT_SIZE / 8) - 1) / (RTE_BITMAP_SLAB_BIT_SIZE / 8);
109 : 11 : n_cache_lines_context_and_array1 = (n_slabs_context + n_slabs_array1 + RTE_BITMAP_CL_SLAB_SIZE - 1) / RTE_BITMAP_CL_SLAB_SIZE;
110 : 11 : n_bytes_total = (n_cache_lines_context_and_array1 + n_cache_lines_array2) * RTE_CACHE_LINE_SIZE;
111 : :
112 [ + - ]: 3 : if (array1_byte_offset) {
113 : 3 : *array1_byte_offset = n_slabs_context * (RTE_BITMAP_SLAB_BIT_SIZE / 8);
114 : : }
115 [ + - ]: 3 : if (array1_slabs) {
116 : 3 : *array1_slabs = n_slabs_array1;
117 : : }
118 [ + - ]: 3 : if (array2_byte_offset) {
119 : 3 : *array2_byte_offset = n_cache_lines_context_and_array1 * RTE_CACHE_LINE_SIZE;
120 : : }
121 [ + - ]: 3 : if (array2_slabs) {
122 : 3 : *array2_slabs = n_cache_lines_array2 * RTE_BITMAP_CL_SLAB_SIZE;
123 : : }
124 : :
125 : 3 : return n_bytes_total;
126 : : }
127 : :
128 : : static inline void
129 : : __rte_bitmap_scan_init(struct rte_bitmap *bmp)
130 : : {
131 : 10 : bmp->index1 = bmp->array1_size - 1;
132 : 10 : bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1;
133 : : __rte_bitmap_index2_set(bmp);
134 : 10 : bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE;
135 : :
136 [ # # ]: 3 : bmp->go2 = 0;
137 : 0 : }
138 : :
139 : : /**
140 : : * Bitmap memory footprint calculation
141 : : *
142 : : * @param n_bits
143 : : * Number of bits in the bitmap
144 : : * @return
145 : : * Bitmap memory footprint measured in bytes on success, 0 on error
146 : : */
147 : : static inline uint32_t
148 : 8 : rte_bitmap_get_memory_footprint(uint32_t n_bits) {
149 : : /* Check input arguments */
150 [ + - ]: 8 : if (n_bits == 0) {
151 : : return 0;
152 : : }
153 : :
154 : 8 : return __rte_bitmap_get_memory_footprint(n_bits, NULL, NULL, NULL, NULL);
155 : : }
156 : :
157 : : /**
158 : : * Bitmap initialization
159 : : *
160 : : * @param n_bits
161 : : * Number of pre-allocated bits in array2.
162 : : * @param mem
163 : : * Base address of array1 and array2.
164 : : * @param mem_size
165 : : * Minimum expected size of bitmap.
166 : : * @return
167 : : * Handle to bitmap instance.
168 : : */
169 : : static inline struct rte_bitmap *
170 : 2 : rte_bitmap_init(uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
171 : : {
172 : : struct rte_bitmap *bmp;
173 : : uint32_t array1_byte_offset, array1_slabs, array2_byte_offset, array2_slabs;
174 : : uint32_t size;
175 : :
176 : : /* Check input arguments */
177 [ + - ]: 2 : if (n_bits == 0) {
178 : : return NULL;
179 : : }
180 : :
181 [ + - + - ]: 2 : if ((mem == NULL) || (((uintptr_t) mem) & RTE_CACHE_LINE_MASK)) {
182 : : return NULL;
183 : : }
184 : :
185 : 2 : size = __rte_bitmap_get_memory_footprint(n_bits,
186 : : &array1_byte_offset, &array1_slabs,
187 : : &array2_byte_offset, &array2_slabs);
188 [ + - ]: 2 : if (size > mem_size)
189 : : return NULL;
190 : :
191 : : /* Setup bitmap */
192 : 2 : memset(mem, 0, size);
193 : : bmp = (struct rte_bitmap *) mem;
194 : :
195 : 2 : bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
196 : 2 : bmp->array1_size = array1_slabs;
197 : 2 : bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
198 : 2 : bmp->array2_size = array2_slabs;
199 : :
200 : : __rte_bitmap_scan_init(bmp);
201 : :
202 : 2 : return bmp;
203 : : }
204 : :
205 : : /**
206 : : * Bitmap clear slab overhead bits.
207 : : *
208 : : * @param slabs
209 : : * Slab array.
210 : : * @param slab_size
211 : : * Number of 64-bit slabs in the slabs array.
212 : : * @param pos
213 : : * The start bit position in the slabs to be cleared.
214 : : */
215 : : static inline void
216 : 2 : __rte_bitmap_clear_slab_overhead_bits(uint64_t *slabs, uint32_t slab_size,
217 : : uint32_t pos)
218 : : {
219 : : uint32_t i;
220 : 2 : uint32_t index = pos / RTE_BITMAP_SLAB_BIT_SIZE;
221 : 2 : uint32_t offset = pos & RTE_BITMAP_SLAB_BIT_MASK;
222 : :
223 [ + - ]: 2 : if (offset) {
224 [ + + ]: 88 : for (i = offset; i < RTE_BITMAP_SLAB_BIT_SIZE; i++)
225 : 86 : slabs[index] &= ~(1llu << i);
226 : 2 : index++;
227 : : }
228 [ - + ]: 2 : if (index < slab_size)
229 : 0 : memset(&slabs[index], 0, sizeof(slabs[0]) *
230 : 0 : (slab_size - index));
231 : 2 : }
232 : :
233 : : /**
234 : : * Bitmap initialization with all bits set
235 : : *
236 : : * @param n_bits
237 : : * Number of pre-allocated bits in array2.
238 : : * @param mem
239 : : * Base address of array1 and array2.
240 : : * @param mem_size
241 : : * Minimum expected size of bitmap.
242 : : * @return
243 : : * Handle to bitmap instance.
244 : : */
245 : : static inline struct rte_bitmap *
246 : 1 : rte_bitmap_init_with_all_set(uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
247 : : {
248 : : struct rte_bitmap *bmp;
249 : : uint32_t array1_byte_offset, array1_slabs;
250 : : uint32_t array2_byte_offset, array2_slabs;
251 : : uint32_t size;
252 : :
253 : : /* Check input arguments */
254 [ + - + - ]: 1 : if (!n_bits || !mem || (((uintptr_t) mem) & RTE_CACHE_LINE_MASK))
255 : : return NULL;
256 : :
257 : 1 : size = __rte_bitmap_get_memory_footprint(n_bits,
258 : : &array1_byte_offset, &array1_slabs,
259 : : &array2_byte_offset, &array2_slabs);
260 [ + - ]: 1 : if (size < mem_size)
261 : : return NULL;
262 : :
263 : : /* Setup bitmap */
264 : : bmp = (struct rte_bitmap *) mem;
265 : 1 : bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
266 : 1 : bmp->array1_size = array1_slabs;
267 : 1 : bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
268 : 1 : bmp->array2_size = array2_slabs;
269 : :
270 : : __rte_bitmap_scan_init(bmp);
271 : :
272 : 1 : memset(bmp->array1, 0xff, bmp->array1_size * sizeof(bmp->array1[0]));
273 : 1 : memset(bmp->array2, 0xff, bmp->array2_size * sizeof(bmp->array2[0]));
274 : : /* Clear overhead bits. */
275 : 1 : __rte_bitmap_clear_slab_overhead_bits(bmp->array1, bmp->array1_size,
276 : 1 : bmp->array2_size >> RTE_BITMAP_CL_SLAB_SIZE_LOG2);
277 : 1 : __rte_bitmap_clear_slab_overhead_bits(bmp->array2, bmp->array2_size,
278 : : n_bits);
279 : 1 : return bmp;
280 : : }
281 : :
282 : : /**
283 : : * Bitmap free
284 : : *
285 : : * @param bmp
286 : : * Handle to bitmap instance
287 : : * @return
288 : : * 0 upon success, error code otherwise
289 : : */
290 : : static inline int
291 : : rte_bitmap_free(struct rte_bitmap *bmp)
292 : : {
293 : : /* Check input arguments */
294 : : if (bmp == NULL) {
295 : : return -1;
296 : : }
297 : :
298 : : return 0;
299 : : }
300 : :
301 : : /**
302 : : * Bitmap reset
303 : : *
304 : : * @param bmp
305 : : * Handle to bitmap instance
306 : : */
307 : : static inline void
308 : 5 : rte_bitmap_reset(struct rte_bitmap *bmp)
309 : : {
310 : 5 : memset(bmp->array1, 0, bmp->array1_size * sizeof(uint64_t));
311 : 5 : memset(bmp->array2, 0, bmp->array2_size * sizeof(uint64_t));
312 : : __rte_bitmap_scan_init(bmp);
313 : 5 : }
314 : :
315 : : /**
316 : : * Bitmap location prefetch into CPU L1 cache
317 : : *
318 : : * @param bmp
319 : : * Handle to bitmap instance
320 : : * @param pos
321 : : * Bit position
322 : : */
323 : : static inline void
324 : : rte_bitmap_prefetch0(struct rte_bitmap *bmp, uint32_t pos)
325 : : {
326 : : uint64_t *slab2;
327 : : uint32_t index2;
328 : :
329 : 11 : index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
330 : 11 : slab2 = bmp->array2 + index2;
331 : : rte_prefetch0((void *) slab2);
332 : : }
333 : :
334 : : /**
335 : : * Bitmap bit get
336 : : *
337 : : * @param bmp
338 : : * Handle to bitmap instance
339 : : * @param pos
340 : : * Bit position
341 : : * @return
342 : : * 0 when bit is cleared, non-zero when bit is set
343 : : */
344 : : static inline uint64_t
345 : : rte_bitmap_get(struct rte_bitmap *bmp, uint32_t pos)
346 : : {
347 : : uint64_t *slab2;
348 : : uint32_t index2, offset2;
349 : :
350 : 3000 : index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
351 : 3000 : offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
352 : 3000 : slab2 = bmp->array2 + index2;
353 [ - + - + : 3000 : return (*slab2) & (1llu << offset2);
+ + # # #
# # # # #
# # # # #
# ]
354 : : }
355 : :
356 : : /**
357 : : * Bitmap bit set
358 : : *
359 : : * @param bmp
360 : : * Handle to bitmap instance
361 : : * @param pos
362 : : * Bit position
363 : : */
364 : : static inline void
365 : 2994 : rte_bitmap_set(struct rte_bitmap *bmp, uint32_t pos)
366 : : {
367 : : uint64_t *slab1, *slab2;
368 : : uint32_t index1, index2, offset1, offset2;
369 : :
370 : : /* Set bit in array2 slab and set bit in array1 slab */
371 : 2994 : index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
372 : 2994 : offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
373 : 2994 : index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
374 : 2994 : offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
375 : 2994 : slab2 = bmp->array2 + index2;
376 : 2994 : slab1 = bmp->array1 + index1;
377 : :
378 : 2994 : *slab2 |= 1llu << offset2;
379 : 2994 : *slab1 |= 1llu << offset1;
380 : 2994 : }
381 : :
382 : : /**
383 : : * Bitmap slab set
384 : : *
385 : : * @param bmp
386 : : * Handle to bitmap instance
387 : : * @param pos
388 : : * Bit position identifying the array2 slab
389 : : * @param slab
390 : : * Value to be assigned to the 64-bit slab in array2
391 : : */
392 : : static inline void
393 : : rte_bitmap_set_slab(struct rte_bitmap *bmp, uint32_t pos, uint64_t slab)
394 : : {
395 : : uint64_t *slab1, *slab2;
396 : : uint32_t index1, index2, offset1;
397 : :
398 : : /* Set bits in array2 slab and set bit in array1 slab */
399 : : index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
400 : : index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
401 : : offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
402 : 2 : slab2 = bmp->array2 + index2;
403 : 2 : slab1 = bmp->array1 + index1;
404 : :
405 : 2 : *slab2 |= slab;
406 : 2 : *slab1 |= 1llu << offset1;
407 : : }
408 : :
409 : : #if RTE_BITMAP_CL_SLAB_SIZE == 8
410 : : static inline uint64_t
411 : : __rte_bitmap_line_not_empty(uint64_t *slab2)
412 : : {
413 : : uint64_t v1, v2, v3, v4;
414 : :
415 : 37 : v1 = slab2[0] | slab2[1];
416 : 37 : v2 = slab2[2] | slab2[3];
417 : 37 : v3 = slab2[4] | slab2[5];
418 : 37 : v4 = slab2[6] | slab2[7];
419 : 37 : v1 |= v2;
420 : 37 : v3 |= v4;
421 : :
422 : 37 : return v1 | v3;
423 : : }
424 : :
425 : : #elif RTE_BITMAP_CL_SLAB_SIZE == 16
426 : : static inline uint64_t
427 : : __rte_bitmap_line_not_empty(uint64_t *slab2)
428 : : {
429 : : uint64_t v1, v2, v3, v4, v5, v6, v7, v8;
430 : :
431 : : v1 = slab2[0] | slab2[1];
432 : : v2 = slab2[2] | slab2[3];
433 : : v3 = slab2[4] | slab2[5];
434 : : v4 = slab2[6] | slab2[7];
435 : : v5 = slab2[8] | slab2[9];
436 : : v6 = slab2[10] | slab2[11];
437 : : v7 = slab2[12] | slab2[13];
438 : : v8 = slab2[14] | slab2[15];
439 : : v1 |= v2;
440 : : v3 |= v4;
441 : : v5 |= v6;
442 : : v7 |= v8;
443 : :
444 : : return v1 | v3 | v5 | v7;
445 : : }
446 : :
447 : : #endif /* RTE_BITMAP_CL_SLAB_SIZE */
448 : :
449 : : /**
450 : : * Bitmap bit clear
451 : : *
452 : : * @param bmp
453 : : * Handle to bitmap instance
454 : : * @param pos
455 : : * Bit position
456 : : */
457 : : static inline void
458 : 2257 : rte_bitmap_clear(struct rte_bitmap *bmp, uint32_t pos)
459 : : {
460 : : uint64_t *slab1, *slab2;
461 : : uint32_t index1, index2, offset1, offset2;
462 : :
463 : : /* Clear bit in array2 slab */
464 : 2257 : index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
465 : 2257 : offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
466 : 2257 : slab2 = bmp->array2 + index2;
467 : :
468 : : /* Return if array2 slab is not all-zeros */
469 : 2257 : *slab2 &= ~(1llu << offset2);
470 [ + + ]: 2257 : if (*slab2){
471 : : return;
472 : : }
473 : :
474 : : /* Check the entire cache line of array2 for all-zeros */
475 : 37 : index2 &= ~ RTE_BITMAP_CL_SLAB_MASK;
476 : 37 : slab2 = bmp->array2 + index2;
477 [ + + ]: 37 : if (__rte_bitmap_line_not_empty(slab2)) {
478 : : return;
479 : : }
480 : :
481 : : /* The array2 cache line is all-zeros, so clear bit in array1 slab */
482 : 5 : index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
483 : 5 : offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
484 : 5 : slab1 = bmp->array1 + index1;
485 : 5 : *slab1 &= ~(1llu << offset1);
486 : :
487 : 5 : return;
488 : : }
489 : :
490 : : static inline int
491 : 222 : __rte_bitmap_scan_search(struct rte_bitmap *bmp)
492 : : {
493 : : uint64_t value1;
494 : : uint32_t i;
495 : :
496 : : /* Check current array1 slab */
497 : 222 : value1 = bmp->array1[bmp->index1];
498 [ + + ]: 222 : value1 &= __rte_bitmap_mask1_get(bmp);
499 : :
500 : : if (rte_bsf64_safe(value1, &bmp->offset1))
501 : 65 : return 1;
502 : :
503 : : __rte_bitmap_index1_inc(bmp);
504 : 157 : bmp->offset1 = 0;
505 : :
506 : : /* Look for another array1 slab */
507 [ + + ]: 159 : for (i = 0; i < bmp->array1_size; i ++, __rte_bitmap_index1_inc(bmp)) {
508 [ + + ]: 157 : value1 = bmp->array1[bmp->index1];
509 : :
510 : : if (rte_bsf64_safe(value1, &bmp->offset1))
511 : 155 : return 1;
512 : : }
513 : :
514 : : return 0;
515 : : }
516 : :
517 : : static inline void
518 : : __rte_bitmap_scan_read_init(struct rte_bitmap *bmp)
519 : : {
520 : : __rte_bitmap_index2_set(bmp);
521 : 220 : bmp->go2 = 1;
522 : 220 : rte_prefetch1((void *)(bmp->array2 + bmp->index2 + 8));
523 : : }
524 : :
525 : : static inline int
526 : 1239 : __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
527 : : {
528 : : uint64_t *slab2;
529 : :
530 : 1325 : slab2 = bmp->array2 + bmp->index2;
531 [ + + + - ]: 1958 : for ( ; bmp->go2 ; bmp->index2 ++, slab2 ++, bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK) {
532 [ + + + - ]: 1736 : if (*slab2) {
533 : 1103 : *pos = bmp->index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
534 : 1103 : *slab = *slab2;
535 : :
536 : 1103 : bmp->index2 ++;
537 : : slab2 ++;
538 : 1103 : bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK;
539 : 1103 : return 1;
540 : : }
541 : : }
542 : :
543 : : return 0;
544 : : }
545 : :
546 : : /**
547 : : * Bitmap scan (with automatic wrap-around)
548 : : *
549 : : * @param bmp
550 : : * Handle to bitmap instance
551 : : * @param pos
552 : : * When function call returns 1, pos contains the position of the next set
553 : : * bit, otherwise not modified
554 : : * @param slab
555 : : * When function call returns 1, slab contains the value of the entire 64-bit
556 : : * slab where the bit indicated by pos is located. Slabs are always 64-bit
557 : : * aligned, so the position of the first bit of the slab (this bit is not
558 : : * necessarily set) is pos / 64. Once a slab has been returned by the bitmap
559 : : * scan operation, the internal pointers of the bitmap are updated to point
560 : : * after this slab, so the same slab will not be returned again if it
561 : : * contains more than one bit which is set. When function call returns 0,
562 : : * slab is not modified.
563 : : * @return
564 : : * 0 if there is no bit set in the bitmap, 1 otherwise
565 : : */
566 : : static inline int
567 : 1105 : rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
568 : : {
569 : : /* Return data from current array2 line if available */
570 [ + + ]: 1019 : if (__rte_bitmap_scan_read(bmp, pos, slab)) {
571 : 0 : return 1;
572 : : }
573 : :
574 : : /* Look for non-empty array2 line */
575 [ + + ]: 222 : if (__rte_bitmap_scan_search(bmp)) {
576 : : __rte_bitmap_scan_read_init(bmp);
577 : 220 : __rte_bitmap_scan_read(bmp, pos, slab);
578 : 220 : return 1;
579 : : }
580 : :
581 : : /* Empty bitmap */
582 : : return 0;
583 : : }
584 : :
585 : : #ifdef __cplusplus
586 : : }
587 : : #endif
588 : :
589 : : #endif /* __INCLUDE_RTE_BITMAP_H__ */
|
