Branch data Line data Source code
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 : : */
41 : 0 : 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 [ # # ]: 0 : if (bitmap == NULL || nbits == 0)
50 : : return -EINVAL;
51 : :
52 : : /* Allocate DLB2 bitmap control struct */
53 : 0 : bm = rte_malloc("DLB2_PF",
54 : : sizeof(struct dlb2_bitmap),
55 : : RTE_CACHE_LINE_SIZE);
56 : :
57 [ # # ]: 0 : if (bm == NULL)
58 : : return -ENOMEM;
59 : :
60 : : /* Allocate bitmap memory */
61 : 0 : alloc_size = rte_bitmap_get_memory_footprint(nbits);
62 : 0 : mem = rte_malloc("DLB2_PF_BITMAP", alloc_size, RTE_CACHE_LINE_SIZE);
63 [ # # ]: 0 : if (mem == NULL) {
64 : 0 : rte_free(bm);
65 : 0 : return -ENOMEM;
66 : : }
67 : :
68 : 0 : bm->map = rte_bitmap_init(len, mem, alloc_size);
69 [ # # ]: 0 : if (bm->map == NULL) {
70 : 0 : rte_free(mem);
71 : 0 : rte_free(bm);
72 : 0 : return -ENOMEM;
73 : : }
74 : :
75 : 0 : bm->len = len;
76 : :
77 : 0 : *bitmap = bm;
78 : :
79 : 0 : 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 : : */
88 : 0 : static inline void dlb2_bitmap_free(struct dlb2_bitmap *bitmap)
89 : : {
90 [ # # ]: 0 : if (bitmap == NULL)
91 : : return;
92 : :
93 : 0 : rte_free(bitmap->map);
94 : 0 : 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 : : */
109 : 0 : static inline int dlb2_bitmap_fill(struct dlb2_bitmap *bitmap)
110 : : {
111 : : unsigned int i;
112 : :
113 [ # # # # ]: 0 : if (bitmap == NULL || bitmap->map == NULL)
114 : : return -EINVAL;
115 : :
116 [ # # ]: 0 : for (i = 0; i != bitmap->len; i++)
117 : 0 : 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 : : */
134 : : static inline int dlb2_bitmap_zero(struct dlb2_bitmap *bitmap)
135 : : {
136 [ # # # # ]: 0 : if (bitmap == NULL || bitmap->map == NULL)
137 : : return -EINVAL;
138 : :
139 : 0 : 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 : : */
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 : : */
183 : 0 : 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 [ # # # # ]: 0 : if (bitmap == NULL || bitmap->map == NULL)
190 : : return -EINVAL;
191 : :
192 [ # # ]: 0 : if (bitmap->len <= bit)
193 : : return -EINVAL;
194 : :
195 [ # # ]: 0 : for (i = 0; i != len; i++)
196 : 0 : 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 : : */
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 : : */
240 : 0 : 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 [ # # # # ]: 0 : if (bitmap == NULL || bitmap->map == NULL)
247 : : return -EINVAL;
248 : :
249 [ # # ]: 0 : if (bitmap->len <= bit)
250 : : return -EINVAL;
251 : :
252 [ # # ]: 0 : for (i = 0; i != len; i++)
253 : 0 : 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 : : */
272 : 0 : 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 [ # # # # : 0 : if (bitmap == NULL || bitmap->map == NULL || len == 0)
# # ]
278 : : return -EINVAL;
279 : :
280 [ # # ]: 0 : if (bitmap->len < len)
281 : : return -ENOENT;
282 : :
283 [ # # ]: 0 : for (i = 0; i != bitmap->len; i++) {
284 [ # # ]: 0 : if (rte_bitmap_get(bitmap->map, i)) {
285 [ # # ]: 0 : if (++j == len)
286 : 0 : 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 : : */
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 : : */
338 : 0 : static inline int dlb2_bitmap_count(struct dlb2_bitmap *bitmap)
339 : : {
340 : : int weight = 0;
341 : : unsigned int i;
342 : :
343 [ # # ]: 0 : if (bitmap == NULL)
344 : : return -EINVAL;
345 : :
346 [ # # ]: 0 : if (bitmap->map == NULL)
347 : : return -EINVAL;
348 : :
349 [ # # ]: 0 : for (i = 0; i != bitmap->len; i++) {
350 [ # # ]: 0 : if (rte_bitmap_get(bitmap->map, i))
351 : 0 : 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 : : */
368 : 0 : 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 [ # # ]: 0 : if (bitmap == NULL)
374 : : return -EINVAL;
375 : :
376 [ # # ]: 0 : if (bitmap->map == NULL)
377 : : return -EINVAL;
378 : :
379 [ # # ]: 0 : for (i = 0; i != bitmap->len; i++) {
380 [ # # ]: 0 : if (rte_bitmap_get(bitmap->map, i)) {
381 : 0 : 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 : : */
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 */
|