]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | /* SPDX-License-Identifier: BSD-3-Clause |
2 | * Copyright(c) 2010-2014 Intel Corporation | |
7c673cae FG |
3 | */ |
4 | ||
5 | #ifndef __INCLUDE_RTE_BITMAP_H__ | |
6 | #define __INCLUDE_RTE_BITMAP_H__ | |
7 | ||
8 | #ifdef __cplusplus | |
9 | extern "C" { | |
10 | #endif | |
11 | ||
12 | /** | |
13 | * @file | |
14 | * RTE Bitmap | |
15 | * | |
16 | * The bitmap component provides a mechanism to manage large arrays of bits | |
17 | * through bit get/set/clear and bit array scan operations. | |
18 | * | |
19 | * The bitmap scan operation is optimized for 64-bit CPUs using 64/128 byte cache | |
20 | * lines. The bitmap is hierarchically organized using two arrays (array1 and | |
21 | * array2), with each bit in array1 being associated with a full cache line | |
22 | * (512/1024 bits) of bitmap bits, which are stored in array2: the bit in array1 | |
23 | * is set only when there is at least one bit set within its associated array2 | |
24 | * bits, otherwise the bit in array1 is cleared. The read and write operations | |
25 | * for array1 and array2 are always done in slabs of 64 bits. | |
26 | * | |
27 | * This bitmap is not thread safe. For lock free operation on a specific bitmap | |
28 | * instance, a single writer thread performing bit set/clear operations is | |
29 | * allowed, only the writer thread can do bitmap scan operations, while there | |
30 | * can be several reader threads performing bit get operations in parallel with | |
31 | * the writer thread. When the use of locking primitives is acceptable, the | |
32 | * serialization of the bit set/clear and bitmap scan operations needs to be | |
33 | * enforced by the caller, while the bit get operation does not require locking | |
34 | * the bitmap. | |
35 | * | |
36 | ***/ | |
37 | ||
38 | #include <string.h> | |
39 | #include <rte_common.h> | |
11fdf7f2 | 40 | #include <rte_config.h> |
7c673cae FG |
41 | #include <rte_debug.h> |
42 | #include <rte_memory.h> | |
43 | #include <rte_branch_prediction.h> | |
44 | #include <rte_prefetch.h> | |
45 | ||
7c673cae FG |
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 | bmp->index1 = (bmp->index1 + 1) & (bmp->array1_size - 1); | |
82 | } | |
83 | ||
84 | static inline uint64_t | |
85 | __rte_bitmap_mask1_get(struct rte_bitmap *bmp) | |
86 | { | |
9f95a23c | 87 | return (~1llu) << bmp->offset1; |
7c673cae FG |
88 | } |
89 | ||
90 | static inline void | |
91 | __rte_bitmap_index2_set(struct rte_bitmap *bmp) | |
92 | { | |
93 | bmp->index2 = (((bmp->index1 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2) + bmp->offset1) << RTE_BITMAP_CL_SLAB_SIZE_LOG2); | |
94 | } | |
95 | ||
7c673cae FG |
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) | |
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 | 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; | |
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 | 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; | |
111 | ||
112 | if (array1_byte_offset) { | |
113 | *array1_byte_offset = n_slabs_context * (RTE_BITMAP_SLAB_BIT_SIZE / 8); | |
114 | } | |
115 | if (array1_slabs) { | |
116 | *array1_slabs = n_slabs_array1; | |
117 | } | |
118 | if (array2_byte_offset) { | |
119 | *array2_byte_offset = n_cache_lines_context_and_array1 * RTE_CACHE_LINE_SIZE; | |
120 | } | |
121 | if (array2_slabs) { | |
122 | *array2_slabs = n_cache_lines_array2 * RTE_BITMAP_CL_SLAB_SIZE; | |
123 | } | |
124 | ||
125 | return n_bytes_total; | |
126 | } | |
127 | ||
128 | static inline void | |
129 | __rte_bitmap_scan_init(struct rte_bitmap *bmp) | |
130 | { | |
131 | bmp->index1 = bmp->array1_size - 1; | |
132 | bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1; | |
133 | __rte_bitmap_index2_set(bmp); | |
134 | bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE; | |
135 | ||
136 | bmp->go2 = 0; | |
137 | } | |
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 | rte_bitmap_get_memory_footprint(uint32_t n_bits) { | |
149 | /* Check input arguments */ | |
150 | if (n_bits == 0) { | |
151 | return 0; | |
152 | } | |
153 | ||
154 | return __rte_bitmap_get_memory_footprint(n_bits, NULL, NULL, NULL, NULL); | |
155 | } | |
156 | ||
157 | /** | |
158 | * Bitmap initialization | |
159 | * | |
11fdf7f2 TL |
160 | * @param n_bits |
161 | * Number of pre-allocated bits in array2. | |
7c673cae FG |
162 | * @param mem |
163 | * Base address of array1 and array2. | |
11fdf7f2 TL |
164 | * @param mem_size |
165 | * Minimum expected size of bitmap. | |
7c673cae FG |
166 | * @return |
167 | * Handle to bitmap instance. | |
168 | */ | |
169 | static inline struct rte_bitmap * | |
170 | 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 | if (n_bits == 0) { | |
178 | return NULL; | |
179 | } | |
180 | ||
181 | if ((mem == NULL) || (((uintptr_t) mem) & RTE_CACHE_LINE_MASK)) { | |
182 | return NULL; | |
183 | } | |
184 | ||
185 | size = __rte_bitmap_get_memory_footprint(n_bits, | |
186 | &array1_byte_offset, &array1_slabs, | |
187 | &array2_byte_offset, &array2_slabs); | |
188 | if (size < mem_size) { | |
189 | return NULL; | |
190 | } | |
191 | ||
192 | /* Setup bitmap */ | |
193 | memset(mem, 0, size); | |
194 | bmp = (struct rte_bitmap *) mem; | |
195 | ||
196 | bmp->array1 = (uint64_t *) &mem[array1_byte_offset]; | |
197 | bmp->array1_size = array1_slabs; | |
198 | bmp->array2 = (uint64_t *) &mem[array2_byte_offset]; | |
199 | bmp->array2_size = array2_slabs; | |
200 | ||
201 | __rte_bitmap_scan_init(bmp); | |
202 | ||
203 | return bmp; | |
204 | } | |
205 | ||
206 | /** | |
207 | * Bitmap free | |
208 | * | |
209 | * @param bmp | |
210 | * Handle to bitmap instance | |
211 | * @return | |
212 | * 0 upon success, error code otherwise | |
213 | */ | |
214 | static inline int | |
215 | rte_bitmap_free(struct rte_bitmap *bmp) | |
216 | { | |
217 | /* Check input arguments */ | |
218 | if (bmp == NULL) { | |
219 | return -1; | |
220 | } | |
221 | ||
222 | return 0; | |
223 | } | |
224 | ||
225 | /** | |
226 | * Bitmap reset | |
227 | * | |
228 | * @param bmp | |
229 | * Handle to bitmap instance | |
230 | */ | |
231 | static inline void | |
232 | rte_bitmap_reset(struct rte_bitmap *bmp) | |
233 | { | |
234 | memset(bmp->array1, 0, bmp->array1_size * sizeof(uint64_t)); | |
235 | memset(bmp->array2, 0, bmp->array2_size * sizeof(uint64_t)); | |
236 | __rte_bitmap_scan_init(bmp); | |
237 | } | |
238 | ||
239 | /** | |
240 | * Bitmap location prefetch into CPU L1 cache | |
241 | * | |
242 | * @param bmp | |
243 | * Handle to bitmap instance | |
244 | * @param pos | |
245 | * Bit position | |
246 | * @return | |
247 | * 0 upon success, error code otherwise | |
248 | */ | |
249 | static inline void | |
250 | rte_bitmap_prefetch0(struct rte_bitmap *bmp, uint32_t pos) | |
251 | { | |
252 | uint64_t *slab2; | |
253 | uint32_t index2; | |
254 | ||
255 | index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2; | |
256 | slab2 = bmp->array2 + index2; | |
257 | rte_prefetch0((void *) slab2); | |
258 | } | |
259 | ||
260 | /** | |
261 | * Bitmap bit get | |
262 | * | |
263 | * @param bmp | |
264 | * Handle to bitmap instance | |
265 | * @param pos | |
266 | * Bit position | |
267 | * @return | |
268 | * 0 when bit is cleared, non-zero when bit is set | |
269 | */ | |
270 | static inline uint64_t | |
271 | rte_bitmap_get(struct rte_bitmap *bmp, uint32_t pos) | |
272 | { | |
273 | uint64_t *slab2; | |
274 | uint32_t index2, offset2; | |
275 | ||
276 | index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2; | |
277 | offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK; | |
278 | slab2 = bmp->array2 + index2; | |
9f95a23c | 279 | return (*slab2) & (1llu << offset2); |
7c673cae FG |
280 | } |
281 | ||
282 | /** | |
283 | * Bitmap bit set | |
284 | * | |
285 | * @param bmp | |
286 | * Handle to bitmap instance | |
287 | * @param pos | |
288 | * Bit position | |
289 | */ | |
290 | static inline void | |
291 | rte_bitmap_set(struct rte_bitmap *bmp, uint32_t pos) | |
292 | { | |
293 | uint64_t *slab1, *slab2; | |
294 | uint32_t index1, index2, offset1, offset2; | |
295 | ||
296 | /* Set bit in array2 slab and set bit in array1 slab */ | |
297 | index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2; | |
298 | offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK; | |
299 | index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2); | |
300 | offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK; | |
301 | slab2 = bmp->array2 + index2; | |
302 | slab1 = bmp->array1 + index1; | |
303 | ||
9f95a23c TL |
304 | *slab2 |= 1llu << offset2; |
305 | *slab1 |= 1llu << offset1; | |
7c673cae FG |
306 | } |
307 | ||
308 | /** | |
309 | * Bitmap slab set | |
310 | * | |
311 | * @param bmp | |
312 | * Handle to bitmap instance | |
313 | * @param pos | |
314 | * Bit position identifying the array2 slab | |
315 | * @param slab | |
316 | * Value to be assigned to the 64-bit slab in array2 | |
317 | */ | |
318 | static inline void | |
319 | rte_bitmap_set_slab(struct rte_bitmap *bmp, uint32_t pos, uint64_t slab) | |
320 | { | |
321 | uint64_t *slab1, *slab2; | |
322 | uint32_t index1, index2, offset1; | |
323 | ||
324 | /* Set bits in array2 slab and set bit in array1 slab */ | |
325 | index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2; | |
326 | index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2); | |
327 | offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK; | |
328 | slab2 = bmp->array2 + index2; | |
329 | slab1 = bmp->array1 + index1; | |
330 | ||
331 | *slab2 |= slab; | |
9f95a23c | 332 | *slab1 |= 1llu << offset1; |
7c673cae FG |
333 | } |
334 | ||
335 | static inline uint64_t | |
336 | __rte_bitmap_line_not_empty(uint64_t *slab2) | |
337 | { | |
338 | uint64_t v1, v2, v3, v4; | |
339 | ||
340 | v1 = slab2[0] | slab2[1]; | |
341 | v2 = slab2[2] | slab2[3]; | |
342 | v3 = slab2[4] | slab2[5]; | |
343 | v4 = slab2[6] | slab2[7]; | |
344 | v1 |= v2; | |
345 | v3 |= v4; | |
346 | ||
347 | return v1 | v3; | |
348 | } | |
349 | ||
350 | /** | |
351 | * Bitmap bit clear | |
352 | * | |
353 | * @param bmp | |
354 | * Handle to bitmap instance | |
355 | * @param pos | |
356 | * Bit position | |
357 | */ | |
358 | static inline void | |
359 | rte_bitmap_clear(struct rte_bitmap *bmp, uint32_t pos) | |
360 | { | |
361 | uint64_t *slab1, *slab2; | |
362 | uint32_t index1, index2, offset1, offset2; | |
363 | ||
364 | /* Clear bit in array2 slab */ | |
365 | index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2; | |
366 | offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK; | |
367 | slab2 = bmp->array2 + index2; | |
368 | ||
369 | /* Return if array2 slab is not all-zeros */ | |
9f95a23c | 370 | *slab2 &= ~(1llu << offset2); |
7c673cae FG |
371 | if (*slab2){ |
372 | return; | |
373 | } | |
374 | ||
375 | /* Check the entire cache line of array2 for all-zeros */ | |
376 | index2 &= ~ RTE_BITMAP_CL_SLAB_MASK; | |
377 | slab2 = bmp->array2 + index2; | |
378 | if (__rte_bitmap_line_not_empty(slab2)) { | |
379 | return; | |
380 | } | |
381 | ||
382 | /* The array2 cache line is all-zeros, so clear bit in array1 slab */ | |
383 | index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2); | |
384 | offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK; | |
385 | slab1 = bmp->array1 + index1; | |
9f95a23c | 386 | *slab1 &= ~(1llu << offset1); |
7c673cae FG |
387 | |
388 | return; | |
389 | } | |
390 | ||
391 | static inline int | |
392 | __rte_bitmap_scan_search(struct rte_bitmap *bmp) | |
393 | { | |
394 | uint64_t value1; | |
395 | uint32_t i; | |
396 | ||
397 | /* Check current array1 slab */ | |
398 | value1 = bmp->array1[bmp->index1]; | |
399 | value1 &= __rte_bitmap_mask1_get(bmp); | |
400 | ||
9f95a23c | 401 | if (rte_bsf64_safe(value1, &bmp->offset1)) |
7c673cae | 402 | return 1; |
7c673cae FG |
403 | |
404 | __rte_bitmap_index1_inc(bmp); | |
405 | bmp->offset1 = 0; | |
406 | ||
407 | /* Look for another array1 slab */ | |
408 | for (i = 0; i < bmp->array1_size; i ++, __rte_bitmap_index1_inc(bmp)) { | |
409 | value1 = bmp->array1[bmp->index1]; | |
410 | ||
9f95a23c | 411 | if (rte_bsf64_safe(value1, &bmp->offset1)) |
7c673cae | 412 | return 1; |
7c673cae FG |
413 | } |
414 | ||
415 | return 0; | |
416 | } | |
417 | ||
418 | static inline void | |
419 | __rte_bitmap_scan_read_init(struct rte_bitmap *bmp) | |
420 | { | |
421 | __rte_bitmap_index2_set(bmp); | |
422 | bmp->go2 = 1; | |
423 | rte_prefetch1((void *)(bmp->array2 + bmp->index2 + 8)); | |
424 | } | |
425 | ||
426 | static inline int | |
427 | __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) | |
428 | { | |
429 | uint64_t *slab2; | |
430 | ||
431 | slab2 = bmp->array2 + bmp->index2; | |
432 | for ( ; bmp->go2 ; bmp->index2 ++, slab2 ++, bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK) { | |
433 | if (*slab2) { | |
434 | *pos = bmp->index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2; | |
435 | *slab = *slab2; | |
436 | ||
437 | bmp->index2 ++; | |
438 | slab2 ++; | |
439 | bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK; | |
440 | return 1; | |
441 | } | |
442 | } | |
443 | ||
444 | return 0; | |
445 | } | |
446 | ||
447 | /** | |
448 | * Bitmap scan (with automatic wrap-around) | |
449 | * | |
450 | * @param bmp | |
451 | * Handle to bitmap instance | |
452 | * @param pos | |
453 | * When function call returns 1, pos contains the position of the next set | |
454 | * bit, otherwise not modified | |
455 | * @param slab | |
456 | * When function call returns 1, slab contains the value of the entire 64-bit | |
457 | * slab where the bit indicated by pos is located. Slabs are always 64-bit | |
458 | * aligned, so the position of the first bit of the slab (this bit is not | |
459 | * necessarily set) is pos / 64. Once a slab has been returned by the bitmap | |
460 | * scan operation, the internal pointers of the bitmap are updated to point | |
461 | * after this slab, so the same slab will not be returned again if it | |
462 | * contains more than one bit which is set. When function call returns 0, | |
463 | * slab is not modified. | |
464 | * @return | |
465 | * 0 if there is no bit set in the bitmap, 1 otherwise | |
466 | */ | |
467 | static inline int | |
468 | rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) | |
469 | { | |
470 | /* Return data from current array2 line if available */ | |
471 | if (__rte_bitmap_scan_read(bmp, pos, slab)) { | |
472 | return 1; | |
473 | } | |
474 | ||
475 | /* Look for non-empty array2 line */ | |
476 | if (__rte_bitmap_scan_search(bmp)) { | |
477 | __rte_bitmap_scan_read_init(bmp); | |
478 | __rte_bitmap_scan_read(bmp, pos, slab); | |
479 | return 1; | |
480 | } | |
481 | ||
482 | /* Empty bitmap */ | |
483 | return 0; | |
484 | } | |
485 | ||
486 | #ifdef __cplusplus | |
487 | } | |
488 | #endif | |
489 | ||
490 | #endif /* __INCLUDE_RTE_BITMAP_H__ */ |