5 #ifndef __INCLUDE_RTE_BITMAP_H__ 6 #define __INCLUDE_RTE_BITMAP_H__ 40 #include <rte_config.h> 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) 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) 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) 79 __rte_bitmap_index1_inc(
struct rte_bitmap *bmp)
84 static inline uint64_t
91 __rte_bitmap_index2_set(
struct rte_bitmap *bmp)
93 bmp->
index2 = (((bmp->
index1 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2) + bmp->
offset1) << RTE_BITMAP_CL_SLAB_SIZE_LOG2);
96 static inline uint32_t
97 __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)
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;
105 n_cache_lines_array2 = (n_bits + RTE_BITMAP_CL_BIT_SIZE - 1) / RTE_BITMAP_CL_BIT_SIZE;
106 n_slabs_array1 = (n_cache_lines_array2 + RTE_BITMAP_SLAB_BIT_SIZE - 1) / RTE_BITMAP_SLAB_BIT_SIZE;
108 n_slabs_context = (
sizeof(
struct rte_bitmap) + (RTE_BITMAP_SLAB_BIT_SIZE / 8) - 1) / (RTE_BITMAP_SLAB_BIT_SIZE / 8);
109 n_cache_lines_context_and_array1 = (n_slabs_context + n_slabs_array1 + RTE_BITMAP_CL_SLAB_SIZE - 1) / RTE_BITMAP_CL_SLAB_SIZE;
110 n_bytes_total = (n_cache_lines_context_and_array1 + n_cache_lines_array2) * RTE_CACHE_LINE_SIZE;
112 if (array1_byte_offset) {
113 *array1_byte_offset = n_slabs_context * (RTE_BITMAP_SLAB_BIT_SIZE / 8);
116 *array1_slabs = n_slabs_array1;
118 if (array2_byte_offset) {
119 *array2_byte_offset = n_cache_lines_context_and_array1 * RTE_CACHE_LINE_SIZE;
122 *array2_slabs = n_cache_lines_array2 * RTE_BITMAP_CL_SLAB_SIZE;
125 return n_bytes_total;
129 __rte_bitmap_scan_init(
struct rte_bitmap *bmp)
132 bmp->
offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1;
133 __rte_bitmap_index2_set(bmp);
134 bmp->
index2 += RTE_BITMAP_CL_SLAB_SIZE;
147 static inline uint32_t
154 return __rte_bitmap_get_memory_footprint(n_bits, NULL, NULL, NULL, NULL);
173 uint32_t array1_byte_offset, array1_slabs, array2_byte_offset, array2_slabs;
185 size = __rte_bitmap_get_memory_footprint(n_bits,
186 &array1_byte_offset, &array1_slabs,
187 &array2_byte_offset, &array2_slabs);
192 memset(mem, 0, size);
195 bmp->
array1 = (uint64_t *) &mem[array1_byte_offset];
197 bmp->
array2 = (uint64_t *) &mem[array2_byte_offset];
200 __rte_bitmap_scan_init(bmp);
220 uint32_t index = pos / RTE_BITMAP_SLAB_BIT_SIZE;
221 uint32_t offset = pos & RTE_BITMAP_SLAB_BIT_MASK;
224 for (i = offset; i < RTE_BITMAP_SLAB_BIT_SIZE; i++)
225 slabs[index] &= ~(1llu << i);
228 if (index < slab_size)
229 memset(&slabs[index], 0,
sizeof(slabs[0]) *
230 (slab_size - index));
249 uint32_t array1_byte_offset, array1_slabs;
250 uint32_t array2_byte_offset, array2_slabs;
257 size = __rte_bitmap_get_memory_footprint(n_bits,
258 &array1_byte_offset, &array1_slabs,
259 &array2_byte_offset, &array2_slabs);
265 bmp->
array1 = (uint64_t *) &mem[array1_byte_offset];
267 bmp->
array2 = (uint64_t *) &mem[array2_byte_offset];
270 __rte_bitmap_scan_init(bmp);
312 __rte_bitmap_scan_init(bmp);
329 index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
344 static inline uint64_t
350 index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
351 offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
353 return (*slab2) & (1llu << offset2);
367 uint64_t *slab1, *slab2;
371 index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
372 offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
373 index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
374 offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
378 *slab2 |= 1llu << offset2;
395 uint64_t *slab1, *slab2;
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;
409 #if RTE_BITMAP_CL_SLAB_SIZE == 8 410 static inline uint64_t
411 __rte_bitmap_line_not_empty(uint64_t *slab2)
413 uint64_t v1, v2, v3, v4;
415 v1 = slab2[0] | slab2[1];
416 v2 = slab2[2] | slab2[3];
417 v3 = slab2[4] | slab2[5];
418 v4 = slab2[6] | slab2[7];
425 #elif RTE_BITMAP_CL_SLAB_SIZE == 16 426 static inline uint64_t
427 __rte_bitmap_line_not_empty(uint64_t *slab2)
429 uint64_t v1, v2, v3, v4, v5, v6, v7, v8;
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];
444 return v1 | v3 | v5 | v7;
460 uint64_t *slab1, *slab2;
464 index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
465 offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
469 *slab2 &= ~(1llu << offset2);
475 index2 &= ~ RTE_BITMAP_CL_SLAB_MASK;
477 if (__rte_bitmap_line_not_empty(slab2)) {
482 index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
483 offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
491 __rte_bitmap_scan_search(
struct rte_bitmap *bmp)
498 value1 &= __rte_bitmap_mask1_get(bmp);
503 __rte_bitmap_index1_inc(bmp);
507 for (i = 0; i < bmp->
array1_size; i ++, __rte_bitmap_index1_inc(bmp)) {
518 __rte_bitmap_scan_read_init(
struct rte_bitmap *bmp)
520 __rte_bitmap_index2_set(bmp);
526 __rte_bitmap_scan_read(
struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
531 for ( ; bmp->
go2 ; bmp->
index2 ++, slab2 ++, bmp->
go2 = bmp->
index2 & RTE_BITMAP_CL_SLAB_MASK) {
533 *pos = bmp->
index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
538 bmp->
go2 = bmp->
index2 & RTE_BITMAP_CL_SLAB_MASK;
570 if (__rte_bitmap_scan_read(bmp, pos, slab)) {
575 if (__rte_bitmap_scan_search(bmp)) {
576 __rte_bitmap_scan_read_init(bmp);
577 __rte_bitmap_scan_read(bmp, pos, slab);
static int rte_bitmap_free(struct rte_bitmap *bmp)
static void rte_bitmap_set_slab(struct rte_bitmap *bmp, uint32_t pos, uint64_t slab)
static void rte_bitmap_set(struct rte_bitmap *bmp, uint32_t pos)
static void rte_bitmap_reset(struct rte_bitmap *bmp)
static struct rte_bitmap * rte_bitmap_init_with_all_set(uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
static void __rte_bitmap_clear_slab_overhead_bits(uint64_t *slabs, uint32_t slab_size, uint32_t pos)
static void rte_bitmap_clear(struct rte_bitmap *bmp, uint32_t pos)
static struct rte_bitmap * rte_bitmap_init(uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
static uint32_t rte_align32pow2(uint32_t x)
static uint32_t rte_bitmap_get_memory_footprint(uint32_t n_bits)
static int rte_bsf64_safe(uint64_t v, uint32_t *pos)
static uint64_t rte_bitmap_get(struct rte_bitmap *bmp, uint32_t pos)
static void rte_bitmap_prefetch0(struct rte_bitmap *bmp, uint32_t pos)
static void rte_prefetch1(const volatile void *p)
#define RTE_CACHE_LINE_MASK
static int rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
static void rte_prefetch0(const volatile void *p)