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