1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2016-2020 Intel Corporation
3 */
4
5 #ifndef __DLB2_OSDEP_BITMAP_H
6 #define __DLB2_OSDEP_BITMAP_H
7
8 #include <stdint.h>
9 #include <stdbool.h>
10 #include <stdio.h>
11 #include <unistd.h>
12 #include <rte_bitmap.h>
13 #include <rte_string_fns.h>
14 #include <rte_malloc.h>
15 #include <rte_errno.h>
16 #include "../dlb2_main.h"
17
18 /*************************/
19 /*** Bitmap operations ***/
20 /*************************/
21 struct dlb2_bitmap {
22 struct rte_bitmap *map;
23 unsigned int len;
24 };
25
26 /**
27 * dlb2_bitmap_alloc() - alloc a bitmap data structure
28 * @bitmap: pointer to dlb2_bitmap structure pointer.
29 * @len: number of entries in the bitmap.
30 *
31 * This function allocates a bitmap and initializes it with length @len. All
32 * entries are initially zero.
33 *
34 * Return:
35 * Returns 0 upon success, < 0 otherwise.
36 *
37 * Errors:
38 * EINVAL - bitmap is NULL or len is 0.
39 * ENOMEM - could not allocate memory for the bitmap data structure.
40 */
dlb2_bitmap_alloc(struct dlb2_bitmap ** bitmap,unsigned int len)41 static inline int dlb2_bitmap_alloc(struct dlb2_bitmap **bitmap,
42 unsigned int len)
43 {
44 struct dlb2_bitmap *bm;
45 void *mem;
46 uint32_t alloc_size;
47 uint32_t nbits = (uint32_t)len;
48
49 if (bitmap == NULL || nbits == 0)
50 return -EINVAL;
51
52 /* Allocate DLB2 bitmap control struct */
53 bm = rte_malloc("DLB2_PF",
54 sizeof(struct dlb2_bitmap),
55 RTE_CACHE_LINE_SIZE);
56
57 if (bm == NULL)
58 return -ENOMEM;
59
60 /* Allocate bitmap memory */
61 alloc_size = rte_bitmap_get_memory_footprint(nbits);
62 mem = rte_malloc("DLB2_PF_BITMAP", alloc_size, RTE_CACHE_LINE_SIZE);
63 if (mem == NULL) {
64 rte_free(bm);
65 return -ENOMEM;
66 }
67
68 bm->map = rte_bitmap_init(len, mem, alloc_size);
69 if (bm->map == NULL) {
70 rte_free(mem);
71 rte_free(bm);
72 return -ENOMEM;
73 }
74
75 bm->len = len;
76
77 *bitmap = bm;
78
79 return 0;
80 }
81
82 /**
83 * dlb2_bitmap_free() - free a previously allocated bitmap data structure
84 * @bitmap: pointer to dlb2_bitmap structure.
85 *
86 * This function frees a bitmap that was allocated with dlb2_bitmap_alloc().
87 */
dlb2_bitmap_free(struct dlb2_bitmap * bitmap)88 static inline void dlb2_bitmap_free(struct dlb2_bitmap *bitmap)
89 {
90 if (bitmap == NULL)
91 return;
92
93 rte_free(bitmap->map);
94 rte_free(bitmap);
95 }
96
97 /**
98 * dlb2_bitmap_fill() - fill a bitmap with all 1s
99 * @bitmap: pointer to dlb2_bitmap structure.
100 *
101 * This function sets all bitmap values to 1.
102 *
103 * Return:
104 * Returns 0 upon success, < 0 otherwise.
105 *
106 * Errors:
107 * EINVAL - bitmap is NULL or is uninitialized.
108 */
dlb2_bitmap_fill(struct dlb2_bitmap * bitmap)109 static inline int dlb2_bitmap_fill(struct dlb2_bitmap *bitmap)
110 {
111 unsigned int i;
112
113 if (bitmap == NULL || bitmap->map == NULL)
114 return -EINVAL;
115
116 for (i = 0; i != bitmap->len; i++)
117 rte_bitmap_set(bitmap->map, i);
118
119 return 0;
120 }
121
122 /**
123 * dlb2_bitmap_fill() - fill a bitmap with all 0s
124 * @bitmap: pointer to dlb2_bitmap structure.
125 *
126 * This function sets all bitmap values to 0.
127 *
128 * Return:
129 * Returns 0 upon success, < 0 otherwise.
130 *
131 * Errors:
132 * EINVAL - bitmap is NULL or is uninitialized.
133 */
dlb2_bitmap_zero(struct dlb2_bitmap * bitmap)134 static inline int dlb2_bitmap_zero(struct dlb2_bitmap *bitmap)
135 {
136 if (bitmap == NULL || bitmap->map == NULL)
137 return -EINVAL;
138
139 rte_bitmap_reset(bitmap->map);
140
141 return 0;
142 }
143
144 /**
145 * dlb2_bitmap_set() - set a bitmap entry
146 * @bitmap: pointer to dlb2_bitmap structure.
147 * @bit: bit index.
148 *
149 * Return:
150 * Returns 0 upon success, < 0 otherwise.
151 *
152 * Errors:
153 * EINVAL - bitmap is NULL or is uninitialized, or bit is larger than the
154 * bitmap length.
155 */
dlb2_bitmap_set(struct dlb2_bitmap * bitmap,unsigned int bit)156 static inline int dlb2_bitmap_set(struct dlb2_bitmap *bitmap,
157 unsigned int bit)
158 {
159 if (bitmap == NULL || bitmap->map == NULL)
160 return -EINVAL;
161
162 if (bitmap->len <= bit)
163 return -EINVAL;
164
165 rte_bitmap_set(bitmap->map, bit);
166
167 return 0;
168 }
169
170 /**
171 * dlb2_bitmap_set_range() - set a range of bitmap entries
172 * @bitmap: pointer to dlb2_bitmap structure.
173 * @bit: starting bit index.
174 * @len: length of the range.
175 *
176 * Return:
177 * Returns 0 upon success, < 0 otherwise.
178 *
179 * Errors:
180 * EINVAL - bitmap is NULL or is uninitialized, or the range exceeds the bitmap
181 * length.
182 */
dlb2_bitmap_set_range(struct dlb2_bitmap * bitmap,unsigned int bit,unsigned int len)183 static inline int dlb2_bitmap_set_range(struct dlb2_bitmap *bitmap,
184 unsigned int bit,
185 unsigned int len)
186 {
187 unsigned int i;
188
189 if (bitmap == NULL || bitmap->map == NULL)
190 return -EINVAL;
191
192 if (bitmap->len <= bit)
193 return -EINVAL;
194
195 for (i = 0; i != len; i++)
196 rte_bitmap_set(bitmap->map, bit + i);
197
198 return 0;
199 }
200
201 /**
202 * dlb2_bitmap_clear() - clear a bitmap entry
203 * @bitmap: pointer to dlb2_bitmap structure.
204 * @bit: bit index.
205 *
206 * Return:
207 * Returns 0 upon success, < 0 otherwise.
208 *
209 * Errors:
210 * EINVAL - bitmap is NULL or is uninitialized, or bit is larger than the
211 * bitmap length.
212 */
dlb2_bitmap_clear(struct dlb2_bitmap * bitmap,unsigned int bit)213 static inline int dlb2_bitmap_clear(struct dlb2_bitmap *bitmap,
214 unsigned int bit)
215 {
216 if (bitmap == NULL || bitmap->map == NULL)
217 return -EINVAL;
218
219 if (bitmap->len <= bit)
220 return -EINVAL;
221
222 rte_bitmap_clear(bitmap->map, bit);
223
224 return 0;
225 }
226
227 /**
228 * dlb2_bitmap_clear_range() - clear a range of bitmap entries
229 * @bitmap: pointer to dlb2_bitmap structure.
230 * @bit: starting bit index.
231 * @len: length of the range.
232 *
233 * Return:
234 * Returns 0 upon success, < 0 otherwise.
235 *
236 * Errors:
237 * EINVAL - bitmap is NULL or is uninitialized, or the range exceeds the bitmap
238 * length.
239 */
dlb2_bitmap_clear_range(struct dlb2_bitmap * bitmap,unsigned int bit,unsigned int len)240 static inline int dlb2_bitmap_clear_range(struct dlb2_bitmap *bitmap,
241 unsigned int bit,
242 unsigned int len)
243 {
244 unsigned int i;
245
246 if (bitmap == NULL || bitmap->map == NULL)
247 return -EINVAL;
248
249 if (bitmap->len <= bit)
250 return -EINVAL;
251
252 for (i = 0; i != len; i++)
253 rte_bitmap_clear(bitmap->map, bit + i);
254
255 return 0;
256 }
257
258 /**
259 * dlb2_bitmap_find_set_bit_range() - find an range of set bits
260 * @bitmap: pointer to dlb2_bitmap structure.
261 * @len: length of the range.
262 *
263 * This function looks for a range of set bits of length @len.
264 *
265 * Return:
266 * Returns the base bit index upon success, < 0 otherwise.
267 *
268 * Errors:
269 * ENOENT - unable to find a length *len* range of set bits.
270 * EINVAL - bitmap is NULL or is uninitialized, or len is invalid.
271 */
dlb2_bitmap_find_set_bit_range(struct dlb2_bitmap * bitmap,unsigned int len)272 static inline int dlb2_bitmap_find_set_bit_range(struct dlb2_bitmap *bitmap,
273 unsigned int len)
274 {
275 unsigned int i, j = 0;
276
277 if (bitmap == NULL || bitmap->map == NULL || len == 0)
278 return -EINVAL;
279
280 if (bitmap->len < len)
281 return -ENOENT;
282
283 for (i = 0; i != bitmap->len; i++) {
284 if (rte_bitmap_get(bitmap->map, i)) {
285 if (++j == len)
286 return i - j + 1;
287 } else {
288 j = 0;
289 }
290 }
291
292 /* No set bit range of length len? */
293 return -ENOENT;
294 }
295
296 /**
297 * dlb2_bitmap_find_set_bit() - find an range of set bits
298 * @bitmap: pointer to dlb2_bitmap structure.
299 *
300 * This function looks for a single set bit.
301 *
302 * Return:
303 * Returns the base bit index upon success, -1 if not found, <-1 otherwise.
304 *
305 * Errors:
306 * EINVAL - bitmap is NULL or is uninitialized, or len is invalid.
307 */
dlb2_bitmap_find_set_bit(struct dlb2_bitmap * bitmap)308 static inline int dlb2_bitmap_find_set_bit(struct dlb2_bitmap *bitmap)
309 {
310 unsigned int i;
311
312 if (bitmap == NULL)
313 return -EINVAL;
314
315 if (bitmap->map == NULL)
316 return -EINVAL;
317
318 for (i = 0; i != bitmap->len; i++) {
319 if (rte_bitmap_get(bitmap->map, i))
320 return i;
321 }
322
323 return -ENOENT;
324 }
325
326 /**
327 * dlb2_bitmap_count() - returns the number of set bits
328 * @bitmap: pointer to dlb2_bitmap structure.
329 *
330 * This function looks for a single set bit.
331 *
332 * Return:
333 * Returns the number of set bits upon success, <0 otherwise.
334 *
335 * Errors:
336 * EINVAL - bitmap is NULL or is uninitialized.
337 */
dlb2_bitmap_count(struct dlb2_bitmap * bitmap)338 static inline int dlb2_bitmap_count(struct dlb2_bitmap *bitmap)
339 {
340 int weight = 0;
341 unsigned int i;
342
343 if (bitmap == NULL)
344 return -EINVAL;
345
346 if (bitmap->map == NULL)
347 return -EINVAL;
348
349 for (i = 0; i != bitmap->len; i++) {
350 if (rte_bitmap_get(bitmap->map, i))
351 weight++;
352 }
353 return weight;
354 }
355
356 /**
357 * dlb2_bitmap_longest_set_range() - returns longest contiguous range of set
358 * bits
359 * @bitmap: pointer to dlb2_bitmap structure.
360 *
361 * Return:
362 * Returns the bitmap's longest contiguous range of set bits upon success,
363 * <0 otherwise.
364 *
365 * Errors:
366 * EINVAL - bitmap is NULL or is uninitialized.
367 */
dlb2_bitmap_longest_set_range(struct dlb2_bitmap * bitmap)368 static inline int dlb2_bitmap_longest_set_range(struct dlb2_bitmap *bitmap)
369 {
370 int max_len = 0, len = 0;
371 unsigned int i;
372
373 if (bitmap == NULL)
374 return -EINVAL;
375
376 if (bitmap->map == NULL)
377 return -EINVAL;
378
379 for (i = 0; i != bitmap->len; i++) {
380 if (rte_bitmap_get(bitmap->map, i)) {
381 len++;
382 } else {
383 if (len > max_len)
384 max_len = len;
385 len = 0;
386 }
387 }
388
389 if (len > max_len)
390 max_len = len;
391
392 return max_len;
393 }
394
395 /**
396 * dlb2_bitmap_or() - store the logical 'or' of two bitmaps into a third
397 * @dest: pointer to dlb2_bitmap structure, which will contain the results of
398 * the 'or' of src1 and src2.
399 * @src1: pointer to dlb2_bitmap structure, will be 'or'ed with src2.
400 * @src2: pointer to dlb2_bitmap structure, will be 'or'ed with src1.
401 *
402 * This function 'or's two bitmaps together and stores the result in a third
403 * bitmap. The source and destination bitmaps can be the same.
404 *
405 * Return:
406 * Returns the number of set bits upon success, <0 otherwise.
407 *
408 * Errors:
409 * EINVAL - One of the bitmaps is NULL or is uninitialized.
410 */
dlb2_bitmap_or(struct dlb2_bitmap * dest,struct dlb2_bitmap * src1,struct dlb2_bitmap * src2)411 static inline int dlb2_bitmap_or(struct dlb2_bitmap *dest,
412 struct dlb2_bitmap *src1,
413 struct dlb2_bitmap *src2)
414 {
415 unsigned int i, min;
416 int numset = 0;
417
418 if (dest == NULL || dest->map == NULL ||
419 src1 == NULL || src1->map == NULL ||
420 src2 == NULL || src2->map == NULL)
421 return -EINVAL;
422
423 min = dest->len;
424 min = (min > src1->len) ? src1->len : min;
425 min = (min > src2->len) ? src2->len : min;
426
427 for (i = 0; i != min; i++) {
428 if (rte_bitmap_get(src1->map, i) ||
429 rte_bitmap_get(src2->map, i)) {
430 rte_bitmap_set(dest->map, i);
431 numset++;
432 } else {
433 rte_bitmap_clear(dest->map, i);
434 }
435 }
436
437 return numset;
438 }
439
440 #endif /* __DLB2_OSDEP_BITMAP_H */
441