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 : : * This function does nothing in current implementation.
286 : : *
287 : : * @param bmp
288 : : * Handle to bitmap instance
289 : : */
290 : : static inline void
291 : : rte_bitmap_free(struct rte_bitmap *bmp)
292 : : {
293 : : RTE_SET_USED(bmp);
294 : 0 : }
295 : :
296 : : /**
297 : : * Bitmap reset
298 : : *
299 : : * @param bmp
300 : : * Handle to bitmap instance
301 : : */
302 : : static inline void
303 : 5 : rte_bitmap_reset(struct rte_bitmap *bmp)
304 : : {
305 : 5 : memset(bmp->array1, 0, bmp->array1_size * sizeof(uint64_t));
306 : 5 : memset(bmp->array2, 0, bmp->array2_size * sizeof(uint64_t));
307 : : __rte_bitmap_scan_init(bmp);
308 : 5 : }
309 : :
310 : : /**
311 : : * Bitmap location prefetch into CPU L1 cache
312 : : *
313 : : * @param bmp
314 : : * Handle to bitmap instance
315 : : * @param pos
316 : : * Bit position
317 : : */
318 : : static inline void
319 : : rte_bitmap_prefetch0(struct rte_bitmap *bmp, uint32_t pos)
320 : : {
321 : : uint64_t *slab2;
322 : : uint32_t index2;
323 : :
324 : 11 : index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
325 : 11 : slab2 = bmp->array2 + index2;
326 : : rte_prefetch0((void *) slab2);
327 : : }
328 : :
329 : : /**
330 : : * Bitmap bit get
331 : : *
332 : : * @param bmp
333 : : * Handle to bitmap instance
334 : : * @param pos
335 : : * Bit position
336 : : * @return
337 : : * 0 when bit is cleared, non-zero when bit is set
338 : : */
339 : : static inline uint64_t
340 : : rte_bitmap_get(struct rte_bitmap *bmp, uint32_t pos)
341 : : {
342 : : uint64_t *slab2;
343 : : uint32_t index2, offset2;
344 : :
345 : 3000 : index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
346 : 3000 : offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
347 : 3000 : slab2 = bmp->array2 + index2;
348 [ - + - + : 3000 : return (*slab2) & (1llu << offset2);
+ + # # #
# # # # #
# # # # #
# ]
349 : : }
350 : :
351 : : /**
352 : : * Bitmap bit set
353 : : *
354 : : * @param bmp
355 : : * Handle to bitmap instance
356 : : * @param pos
357 : : * Bit position
358 : : */
359 : : static inline void
360 : 2994 : rte_bitmap_set(struct rte_bitmap *bmp, uint32_t pos)
361 : : {
362 : : uint64_t *slab1, *slab2;
363 : : uint32_t index1, index2, offset1, offset2;
364 : :
365 : : /* Set bit in array2 slab and set bit in array1 slab */
366 : 2994 : index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
367 : 2994 : offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
368 : 2994 : index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
369 : 2994 : offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
370 : 2994 : slab2 = bmp->array2 + index2;
371 : 2994 : slab1 = bmp->array1 + index1;
372 : :
373 : 2994 : *slab2 |= 1llu << offset2;
374 : 2994 : *slab1 |= 1llu << offset1;
375 : 2994 : }
376 : :
377 : : /**
378 : : * Bitmap slab set
379 : : *
380 : : * @param bmp
381 : : * Handle to bitmap instance
382 : : * @param pos
383 : : * Bit position identifying the array2 slab
384 : : * @param slab
385 : : * Value to be assigned to the 64-bit slab in array2
386 : : */
387 : : static inline void
388 : : rte_bitmap_set_slab(struct rte_bitmap *bmp, uint32_t pos, uint64_t slab)
389 : : {
390 : : uint64_t *slab1, *slab2;
391 : : uint32_t index1, index2, offset1;
392 : :
393 : : /* Set bits in array2 slab and set bit in array1 slab */
394 : : index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
395 : : index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
396 : : offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
397 : 2 : slab2 = bmp->array2 + index2;
398 : 2 : slab1 = bmp->array1 + index1;
399 : :
400 : 2 : *slab2 |= slab;
401 : 2 : *slab1 |= 1llu << offset1;
402 : : }
403 : :
404 : : #if RTE_BITMAP_CL_SLAB_SIZE == 8
405 : : static inline uint64_t
406 : : __rte_bitmap_line_not_empty(uint64_t *slab2)
407 : : {
408 : : uint64_t v1, v2, v3, v4;
409 : :
410 : 37 : v1 = slab2[0] | slab2[1];
411 : 37 : v2 = slab2[2] | slab2[3];
412 : 37 : v3 = slab2[4] | slab2[5];
413 : 37 : v4 = slab2[6] | slab2[7];
414 : 37 : v1 |= v2;
415 : 37 : v3 |= v4;
416 : :
417 : 37 : return v1 | v3;
418 : : }
419 : :
420 : : #elif RTE_BITMAP_CL_SLAB_SIZE == 16
421 : : static inline uint64_t
422 : : __rte_bitmap_line_not_empty(uint64_t *slab2)
423 : : {
424 : : uint64_t v1, v2, v3, v4, v5, v6, v7, v8;
425 : :
426 : : v1 = slab2[0] | slab2[1];
427 : : v2 = slab2[2] | slab2[3];
428 : : v3 = slab2[4] | slab2[5];
429 : : v4 = slab2[6] | slab2[7];
430 : : v5 = slab2[8] | slab2[9];
431 : : v6 = slab2[10] | slab2[11];
432 : : v7 = slab2[12] | slab2[13];
433 : : v8 = slab2[14] | slab2[15];
434 : : v1 |= v2;
435 : : v3 |= v4;
436 : : v5 |= v6;
437 : : v7 |= v8;
438 : :
439 : : return v1 | v3 | v5 | v7;
440 : : }
441 : :
442 : : #endif /* RTE_BITMAP_CL_SLAB_SIZE */
443 : :
444 : : /**
445 : : * Bitmap bit clear
446 : : *
447 : : * @param bmp
448 : : * Handle to bitmap instance
449 : : * @param pos
450 : : * Bit position
451 : : */
452 : : static inline void
453 : 2257 : rte_bitmap_clear(struct rte_bitmap *bmp, uint32_t pos)
454 : : {
455 : : uint64_t *slab1, *slab2;
456 : : uint32_t index1, index2, offset1, offset2;
457 : :
458 : : /* Clear bit in array2 slab */
459 : 2257 : index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
460 : 2257 : offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
461 : 2257 : slab2 = bmp->array2 + index2;
462 : :
463 : : /* Return if array2 slab is not all-zeros */
464 : 2257 : *slab2 &= ~(1llu << offset2);
465 [ + + ]: 2257 : if (*slab2){
466 : : return;
467 : : }
468 : :
469 : : /* Check the entire cache line of array2 for all-zeros */
470 : 37 : index2 &= ~ RTE_BITMAP_CL_SLAB_MASK;
471 : 37 : slab2 = bmp->array2 + index2;
472 [ + + ]: 37 : if (__rte_bitmap_line_not_empty(slab2)) {
473 : : return;
474 : : }
475 : :
476 : : /* The array2 cache line is all-zeros, so clear bit in array1 slab */
477 : 5 : index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
478 : 5 : offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
479 : 5 : slab1 = bmp->array1 + index1;
480 : 5 : *slab1 &= ~(1llu << offset1);
481 : :
482 : 5 : return;
483 : : }
484 : :
485 : : static inline int
486 : 222 : __rte_bitmap_scan_search(struct rte_bitmap *bmp)
487 : : {
488 : : uint64_t value1;
489 : : uint32_t i;
490 : :
491 : : /* Check current array1 slab */
492 : 222 : value1 = bmp->array1[bmp->index1];
493 [ + + ]: 222 : value1 &= __rte_bitmap_mask1_get(bmp);
494 : :
495 : : if (rte_bsf64_safe(value1, &bmp->offset1))
496 : 65 : return 1;
497 : :
498 : : __rte_bitmap_index1_inc(bmp);
499 : 157 : bmp->offset1 = 0;
500 : :
501 : : /* Look for another array1 slab */
502 [ + + ]: 159 : for (i = 0; i < bmp->array1_size; i ++, __rte_bitmap_index1_inc(bmp)) {
503 [ + + ]: 157 : value1 = bmp->array1[bmp->index1];
504 : :
505 : : if (rte_bsf64_safe(value1, &bmp->offset1))
506 : 155 : return 1;
507 : : }
508 : :
509 : : return 0;
510 : : }
511 : :
512 : : static inline void
513 : : __rte_bitmap_scan_read_init(struct rte_bitmap *bmp)
514 : : {
515 : : __rte_bitmap_index2_set(bmp);
516 : 220 : bmp->go2 = 1;
517 : 220 : rte_prefetch1((void *)(bmp->array2 + bmp->index2 + 8));
518 : : }
519 : :
520 : : static inline int
521 : 1239 : __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
522 : : {
523 : : uint64_t *slab2;
524 : :
525 : 1325 : slab2 = bmp->array2 + bmp->index2;
526 [ + + + - ]: 1958 : for ( ; bmp->go2 ; bmp->index2 ++, slab2 ++, bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK) {
527 [ + + + - ]: 1736 : if (*slab2) {
528 : 1103 : *pos = bmp->index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
529 : 1103 : *slab = *slab2;
530 : :
531 : 1103 : bmp->index2 ++;
532 : : slab2 ++;
533 : 1103 : bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK;
534 : 1103 : return 1;
535 : : }
536 : : }
537 : :
538 : : return 0;
539 : : }
540 : :
541 : : /**
542 : : * Bitmap scan (with automatic wrap-around)
543 : : *
544 : : * @param bmp
545 : : * Handle to bitmap instance
546 : : * @param pos
547 : : * When function call returns 1, pos contains the position of the next set
548 : : * bit, otherwise not modified
549 : : * @param slab
550 : : * When function call returns 1, slab contains the value of the entire 64-bit
551 : : * slab where the bit indicated by pos is located. Slabs are always 64-bit
552 : : * aligned, so the position of the first bit of the slab (this bit is not
553 : : * necessarily set) is pos / 64. Once a slab has been returned by the bitmap
554 : : * scan operation, the internal pointers of the bitmap are updated to point
555 : : * after this slab, so the same slab will not be returned again if it
556 : : * contains more than one bit which is set. When function call returns 0,
557 : : * slab is not modified.
558 : : * @return
559 : : * 0 if there is no bit set in the bitmap, 1 otherwise
560 : : */
561 : : static inline int
562 : 1105 : rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
563 : : {
564 : : /* Return data from current array2 line if available */
565 [ + + ]: 1019 : if (__rte_bitmap_scan_read(bmp, pos, slab)) {
566 : 0 : return 1;
567 : : }
568 : :
569 : : /* Look for non-empty array2 line */
570 [ + + ]: 222 : if (__rte_bitmap_scan_search(bmp)) {
571 : : __rte_bitmap_scan_read_init(bmp);
572 : 220 : __rte_bitmap_scan_read(bmp, pos, slab);
573 : 220 : return 1;
574 : : }
575 : :
576 : : /* Empty bitmap */
577 : : return 0;
578 : : }
579 : :
580 : : #ifdef __cplusplus
581 : : }
582 : : #endif
583 : :
584 : : #endif /* __INCLUDE_RTE_BITMAP_H__ */
|
