DPDK  17.02.1
rte_bitmap.h
Go to the documentation of this file.
1 /*-
2  * BSD LICENSE
3  *
4  * Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  * notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  * notice, this list of conditions and the following disclaimer in
15  * the documentation and/or other materials provided with the
16  * distribution.
17  * * Neither the name of Intel Corporation nor the names of its
18  * contributors may be used to endorse or promote products derived
19  * from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  */
33 
34 #ifndef __INCLUDE_RTE_BITMAP_H__
35 #define __INCLUDE_RTE_BITMAP_H__
36 
37 #ifdef __cplusplus
38 extern "C" {
39 #endif
40 
67 #include <string.h>
68 #include <rte_common.h>
69 #include <rte_debug.h>
70 #include <rte_memory.h>
71 #include <rte_branch_prediction.h>
72 #include <rte_prefetch.h>
73 
74 #ifndef RTE_BITMAP_OPTIMIZATIONS
75 #define RTE_BITMAP_OPTIMIZATIONS 1
76 #endif
77 
78 /* Slab */
79 #define RTE_BITMAP_SLAB_BIT_SIZE 64
80 #define RTE_BITMAP_SLAB_BIT_SIZE_LOG2 6
81 #define RTE_BITMAP_SLAB_BIT_MASK (RTE_BITMAP_SLAB_BIT_SIZE - 1)
82 
83 /* Cache line (CL) */
84 #define RTE_BITMAP_CL_BIT_SIZE (RTE_CACHE_LINE_SIZE * 8)
85 #define RTE_BITMAP_CL_BIT_SIZE_LOG2 (RTE_CACHE_LINE_SIZE_LOG2 + 3)
86 #define RTE_BITMAP_CL_BIT_MASK (RTE_BITMAP_CL_BIT_SIZE - 1)
87 
88 #define RTE_BITMAP_CL_SLAB_SIZE (RTE_BITMAP_CL_BIT_SIZE / RTE_BITMAP_SLAB_BIT_SIZE)
89 #define RTE_BITMAP_CL_SLAB_SIZE_LOG2 (RTE_BITMAP_CL_BIT_SIZE_LOG2 - RTE_BITMAP_SLAB_BIT_SIZE_LOG2)
90 #define RTE_BITMAP_CL_SLAB_MASK (RTE_BITMAP_CL_SLAB_SIZE - 1)
91 
93 struct rte_bitmap {
94  /* Context for array1 and array2 */
95  uint64_t *array1;
96  uint64_t *array2;
97  uint32_t array1_size;
98  uint32_t array2_size;
100  /* Context for the "scan next" operation */
101  uint32_t index1;
102  uint32_t offset1;
103  uint32_t index2;
104  uint32_t go2;
106  /* Storage space for array1 and array2 */
107  uint8_t memory[];
108 };
109 
110 static inline void
111 __rte_bitmap_index1_inc(struct rte_bitmap *bmp)
112 {
113  bmp->index1 = (bmp->index1 + 1) & (bmp->array1_size - 1);
114 }
115 
116 static inline uint64_t
117 __rte_bitmap_mask1_get(struct rte_bitmap *bmp)
118 {
119  return (~1lu) << bmp->offset1;
120 }
121 
122 static inline void
123 __rte_bitmap_index2_set(struct rte_bitmap *bmp)
124 {
125  bmp->index2 = (((bmp->index1 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2) + bmp->offset1) << RTE_BITMAP_CL_SLAB_SIZE_LOG2);
126 }
127 
128 #if RTE_BITMAP_OPTIMIZATIONS
129 
130 static inline int
131 rte_bsf64(uint64_t slab, uint32_t *pos)
132 {
133  if (likely(slab == 0)) {
134  return 0;
135  }
136 
137  *pos = __builtin_ctzll(slab);
138  return 1;
139 }
140 
141 #else
142 
143 static inline int
144 rte_bsf64(uint64_t slab, uint32_t *pos)
145 {
146  uint64_t mask;
147  uint32_t i;
148 
149  if (likely(slab == 0)) {
150  return 0;
151  }
152 
153  for (i = 0, mask = 1; i < RTE_BITMAP_SLAB_BIT_SIZE; i ++, mask <<= 1) {
154  if (unlikely(slab & mask)) {
155  *pos = i;
156  return 1;
157  }
158  }
159 
160  return 0;
161 }
162 
163 #endif
164 
165 static inline uint32_t
166 __rte_bitmap_get_memory_footprint(uint32_t n_bits,
167  uint32_t *array1_byte_offset, uint32_t *array1_slabs,
168  uint32_t *array2_byte_offset, uint32_t *array2_slabs)
169 {
170  uint32_t n_slabs_context, n_slabs_array1, n_cache_lines_context_and_array1;
171  uint32_t n_cache_lines_array2;
172  uint32_t n_bytes_total;
173 
174  n_cache_lines_array2 = (n_bits + RTE_BITMAP_CL_BIT_SIZE - 1) / RTE_BITMAP_CL_BIT_SIZE;
175  n_slabs_array1 = (n_cache_lines_array2 + RTE_BITMAP_SLAB_BIT_SIZE - 1) / RTE_BITMAP_SLAB_BIT_SIZE;
176  n_slabs_array1 = rte_align32pow2(n_slabs_array1);
177  n_slabs_context = (sizeof(struct rte_bitmap) + (RTE_BITMAP_SLAB_BIT_SIZE / 8) - 1) / (RTE_BITMAP_SLAB_BIT_SIZE / 8);
178  n_cache_lines_context_and_array1 = (n_slabs_context + n_slabs_array1 + RTE_BITMAP_CL_SLAB_SIZE - 1) / RTE_BITMAP_CL_SLAB_SIZE;
179  n_bytes_total = (n_cache_lines_context_and_array1 + n_cache_lines_array2) * RTE_CACHE_LINE_SIZE;
180 
181  if (array1_byte_offset) {
182  *array1_byte_offset = n_slabs_context * (RTE_BITMAP_SLAB_BIT_SIZE / 8);
183  }
184  if (array1_slabs) {
185  *array1_slabs = n_slabs_array1;
186  }
187  if (array2_byte_offset) {
188  *array2_byte_offset = n_cache_lines_context_and_array1 * RTE_CACHE_LINE_SIZE;
189  }
190  if (array2_slabs) {
191  *array2_slabs = n_cache_lines_array2 * RTE_BITMAP_CL_SLAB_SIZE;
192  }
193 
194  return n_bytes_total;
195 }
196 
197 static inline void
198 __rte_bitmap_scan_init(struct rte_bitmap *bmp)
199 {
200  bmp->index1 = bmp->array1_size - 1;
201  bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1;
202  __rte_bitmap_index2_set(bmp);
203  bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE;
204 
205  bmp->go2 = 0;
206 }
207 
216 static inline uint32_t
218  /* Check input arguments */
219  if (n_bits == 0) {
220  return 0;
221  }
222 
223  return __rte_bitmap_get_memory_footprint(n_bits, NULL, NULL, NULL, NULL);
224 }
225 
238 static inline struct rte_bitmap *
239 rte_bitmap_init(uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
240 {
241  struct rte_bitmap *bmp;
242  uint32_t array1_byte_offset, array1_slabs, array2_byte_offset, array2_slabs;
243  uint32_t size;
244 
245  /* Check input arguments */
246  if (n_bits == 0) {
247  return NULL;
248  }
249 
250  if ((mem == NULL) || (((uintptr_t) mem) & RTE_CACHE_LINE_MASK)) {
251  return NULL;
252  }
253 
254  size = __rte_bitmap_get_memory_footprint(n_bits,
255  &array1_byte_offset, &array1_slabs,
256  &array2_byte_offset, &array2_slabs);
257  if (size < mem_size) {
258  return NULL;
259  }
260 
261  /* Setup bitmap */
262  memset(mem, 0, size);
263  bmp = (struct rte_bitmap *) mem;
264 
265  bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
266  bmp->array1_size = array1_slabs;
267  bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
268  bmp->array2_size = array2_slabs;
269 
270  __rte_bitmap_scan_init(bmp);
271 
272  return bmp;
273 }
274 
283 static inline int
285 {
286  /* Check input arguments */
287  if (bmp == NULL) {
288  return -1;
289  }
290 
291  return 0;
292 }
293 
300 static inline void
302 {
303  memset(bmp->array1, 0, bmp->array1_size * sizeof(uint64_t));
304  memset(bmp->array2, 0, bmp->array2_size * sizeof(uint64_t));
305  __rte_bitmap_scan_init(bmp);
306 }
307 
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  index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
325  slab2 = bmp->array2 + index2;
326  rte_prefetch0((void *) slab2);
327 }
328 
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  index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
346  offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
347  slab2 = bmp->array2 + index2;
348  return (*slab2) & (1lu << offset2);
349 }
350 
359 static inline void
360 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  index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
367  offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
368  index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
369  offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
370  slab2 = bmp->array2 + index2;
371  slab1 = bmp->array1 + index1;
372 
373  *slab2 |= 1lu << offset2;
374  *slab1 |= 1lu << offset1;
375 }
376 
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  slab2 = bmp->array2 + index2;
398  slab1 = bmp->array1 + index1;
399 
400  *slab2 |= slab;
401  *slab1 |= 1lu << offset1;
402 }
403 
404 static inline uint64_t
405 __rte_bitmap_line_not_empty(uint64_t *slab2)
406 {
407  uint64_t v1, v2, v3, v4;
408 
409  v1 = slab2[0] | slab2[1];
410  v2 = slab2[2] | slab2[3];
411  v3 = slab2[4] | slab2[5];
412  v4 = slab2[6] | slab2[7];
413  v1 |= v2;
414  v3 |= v4;
415 
416  return v1 | v3;
417 }
418 
427 static inline void
428 rte_bitmap_clear(struct rte_bitmap *bmp, uint32_t pos)
429 {
430  uint64_t *slab1, *slab2;
431  uint32_t index1, index2, offset1, offset2;
432 
433  /* Clear bit in array2 slab */
434  index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
435  offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
436  slab2 = bmp->array2 + index2;
437 
438  /* Return if array2 slab is not all-zeros */
439  *slab2 &= ~(1lu << offset2);
440  if (*slab2){
441  return;
442  }
443 
444  /* Check the entire cache line of array2 for all-zeros */
445  index2 &= ~ RTE_BITMAP_CL_SLAB_MASK;
446  slab2 = bmp->array2 + index2;
447  if (__rte_bitmap_line_not_empty(slab2)) {
448  return;
449  }
450 
451  /* The array2 cache line is all-zeros, so clear bit in array1 slab */
452  index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
453  offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
454  slab1 = bmp->array1 + index1;
455  *slab1 &= ~(1lu << offset1);
456 
457  return;
458 }
459 
460 static inline int
461 __rte_bitmap_scan_search(struct rte_bitmap *bmp)
462 {
463  uint64_t value1;
464  uint32_t i;
465 
466  /* Check current array1 slab */
467  value1 = bmp->array1[bmp->index1];
468  value1 &= __rte_bitmap_mask1_get(bmp);
469 
470  if (rte_bsf64(value1, &bmp->offset1)) {
471  return 1;
472  }
473 
474  __rte_bitmap_index1_inc(bmp);
475  bmp->offset1 = 0;
476 
477  /* Look for another array1 slab */
478  for (i = 0; i < bmp->array1_size; i ++, __rte_bitmap_index1_inc(bmp)) {
479  value1 = bmp->array1[bmp->index1];
480 
481  if (rte_bsf64(value1, &bmp->offset1)) {
482  return 1;
483  }
484  }
485 
486  return 0;
487 }
488 
489 static inline void
490 __rte_bitmap_scan_read_init(struct rte_bitmap *bmp)
491 {
492  __rte_bitmap_index2_set(bmp);
493  bmp->go2 = 1;
494  rte_prefetch1((void *)(bmp->array2 + bmp->index2 + 8));
495 }
496 
497 static inline int
498 __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
499 {
500  uint64_t *slab2;
501 
502  slab2 = bmp->array2 + bmp->index2;
503  for ( ; bmp->go2 ; bmp->index2 ++, slab2 ++, bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK) {
504  if (*slab2) {
505  *pos = bmp->index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
506  *slab = *slab2;
507 
508  bmp->index2 ++;
509  slab2 ++;
510  bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK;
511  return 1;
512  }
513  }
514 
515  return 0;
516 }
517 
538 static inline int
539 rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
540 {
541  /* Return data from current array2 line if available */
542  if (__rte_bitmap_scan_read(bmp, pos, slab)) {
543  return 1;
544  }
545 
546  /* Look for non-empty array2 line */
547  if (__rte_bitmap_scan_search(bmp)) {
548  __rte_bitmap_scan_read_init(bmp);
549  __rte_bitmap_scan_read(bmp, pos, slab);
550  return 1;
551  }
552 
553  /* Empty bitmap */
554  return 0;
555 }
556 
557 #ifdef __cplusplus
558 }
559 #endif
560 
561 #endif /* __INCLUDE_RTE_BITMAP_H__ */