Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2017-2018 Intel Corporation
3 : : */
4 : :
5 : : #include <inttypes.h>
6 : : #include <limits.h>
7 : : #include <stdint.h>
8 : : #include <errno.h>
9 : : #include <string.h>
10 : : #include <unistd.h>
11 : :
12 : : #include <rte_common.h>
13 : : #include <rte_eal_paging.h>
14 : : #include <rte_errno.h>
15 : : #include <rte_log.h>
16 : : #include <rte_spinlock.h>
17 : :
18 : : #include <eal_export.h>
19 : : #include "eal_filesystem.h"
20 : : #include "eal_private.h"
21 : :
22 : : #include "rte_fbarray.h"
23 : :
24 : : #define MASK_SHIFT 6ULL
25 : : #define MASK_ALIGN (1ULL << MASK_SHIFT)
26 : : #define MASK_LEN_TO_IDX(x) ((x) >> MASK_SHIFT)
27 : : #define MASK_LEN_TO_MOD(x) ((x) - RTE_ALIGN_FLOOR(x, MASK_ALIGN))
28 : : #define MASK_GET_IDX(idx, mod) ((idx << MASK_SHIFT) + mod)
29 : :
30 : : /*
31 : : * We use this to keep track of created/attached memory areas to prevent user
32 : : * errors in API usage.
33 : : */
34 : : struct mem_area {
35 : : TAILQ_ENTRY(mem_area) next;
36 : : void *addr;
37 : : size_t len;
38 : : int fd;
39 : : };
40 : : TAILQ_HEAD(mem_area_head, mem_area);
41 : : /* local per-process tailq */
42 : : static struct mem_area_head mem_area_tailq =
43 : : TAILQ_HEAD_INITIALIZER(mem_area_tailq);
44 : : static rte_spinlock_t mem_area_lock = RTE_SPINLOCK_INITIALIZER;
45 : :
46 : : /*
47 : : * This is a mask that is always stored at the end of array, to provide fast
48 : : * way of finding free/used spots without looping through each element.
49 : : */
50 : :
51 : : struct used_mask {
52 : : unsigned int n_masks;
53 : : uint64_t data[];
54 : : };
55 : :
56 : : static size_t
57 : : calc_mask_size(unsigned int len)
58 : : {
59 : : /* mask must be multiple of MASK_ALIGN, even though length of array
60 : : * itself may not be aligned on that boundary.
61 : : */
62 : 2130 : len = RTE_ALIGN_CEIL(len, MASK_ALIGN);
63 : 2130 : return sizeof(struct used_mask) +
64 : : sizeof(uint64_t) * MASK_LEN_TO_IDX(len);
65 : : }
66 : :
67 : : static size_t
68 : : calc_data_size(size_t page_sz, unsigned int elt_sz, unsigned int len)
69 : : {
70 : 2130 : size_t data_sz = elt_sz * len;
71 : : size_t msk_sz = calc_mask_size(len);
72 : 2130 : return RTE_ALIGN_CEIL(data_sz + msk_sz, page_sz);
73 : : }
74 : :
75 : : static struct used_mask *
76 : : get_used_mask(void *data, unsigned int elt_sz, unsigned int len)
77 : : {
78 : 48482996 : return (struct used_mask *) RTE_PTR_ADD(data, elt_sz * len);
79 : : }
80 : :
81 : : static int
82 : 1128 : resize_and_map(int fd, const char *path, void *addr, size_t len)
83 : : {
84 : : void *map_addr;
85 : :
86 [ - + ]: 1128 : if (eal_file_truncate(fd, len)) {
87 : 0 : EAL_LOG(ERR, "Cannot truncate %s", path);
88 : 0 : return -1;
89 : : }
90 : :
91 : 1128 : map_addr = rte_mem_map(addr, len, RTE_PROT_READ | RTE_PROT_WRITE,
92 : : RTE_MAP_SHARED | RTE_MAP_FORCE_ADDRESS, fd, 0);
93 [ - + ]: 1128 : if (map_addr != addr) {
94 : 0 : return -1;
95 : : }
96 : : return 0;
97 : : }
98 : :
99 : : static int
100 : : overlap(const struct mem_area *ma, const void *start, size_t len)
101 : : {
102 : 937 : const void *end = RTE_PTR_ADD(start, len);
103 : 937 : const void *ma_start = ma->addr;
104 : 937 : const void *ma_end = RTE_PTR_ADD(ma->addr, ma->len);
105 : :
106 : : /* start overlap? */
107 : 937 : if (start >= ma_start && start < ma_end)
108 : : return 1;
109 : : /* end overlap? */
110 [ + - ]: 937 : if (end > ma_start && end < ma_end)
111 : : return 1;
112 : : return 0;
113 : : }
114 : :
115 : : static int
116 : 5159 : find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
117 : : bool used)
118 : : {
119 : 5159 : const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
120 : 5159 : arr->len);
121 : : unsigned int msk_idx, first, first_mod;
122 : : unsigned int last, last_mod;
123 : : uint64_t last_msk, first_msk;
124 : : unsigned int run_start, left = 0;
125 : : bool run_started = false;
126 : :
127 : : /*
128 : : * mask only has granularity of MASK_ALIGN, but start may not be aligned
129 : : * on that boundary, so construct a special mask to exclude anything we
130 : : * don't want to see to avoid confusing ctz.
131 : : */
132 : 5159 : first = MASK_LEN_TO_IDX(start);
133 : 5159 : first_mod = MASK_LEN_TO_MOD(start);
134 : 5159 : first_msk = ~((1ULL << first_mod) - 1);
135 : :
136 : : /* array length may not be aligned, so calculate ignore mask for last
137 : : * mask index.
138 : : */
139 : 5159 : last = MASK_LEN_TO_IDX(arr->len);
140 : 5159 : last_mod = MASK_LEN_TO_MOD(arr->len);
141 : 5159 : last_msk = ~(UINT64_MAX << last_mod);
142 : :
143 : : left = n;
144 : :
145 [ + + ]: 7208 : for (msk_idx = first; msk_idx < msk->n_masks; msk_idx++) {
146 : : unsigned int s_idx, clz, need;
147 : : uint64_t cur_msk, tmp_msk;
148 : :
149 : : /*
150 : : * In order to find N consecutive bits for arbitrary N, we need
151 : : * to be aware of the following:
152 : : *
153 : : * 1. To find N number of consecutive bits within a mask, we
154 : : * need to do N-1 rshift-ands and see if we still have set
155 : : * bits anywhere in the mask
156 : : * 2. N may be larger than mask size, in which case we need to
157 : : * do a search in multiple consecutive masks
158 : : * 3. For multi-mask search to be meaningful, we need to anchor
159 : : * our searches, i.e. first we find a run of M bits at the
160 : : * end of current mask, then we look for N-M bits at the
161 : : * beginning of next mask (or multiple masks)
162 : : *
163 : : * With all of the above, the algorithm looks as follows:
164 : : *
165 : : * 1. let N be the number of consecutive bits we're looking for
166 : : * 2. if we already started a run, check if we can continue it
167 : : * by looking for remainder of N at the beginning of current
168 : : * mask
169 : : * 3. if we lost a run or if we never had a run, we look for N
170 : : * bits anywhere within the current mask (up to mask size,
171 : : * we can finish this run in the next mask if N > mask size)
172 : : * 4. if we didn't find anything up to this point, check if any
173 : : * topmost bits of the mask are set (meaning we can start a
174 : : * run and finish it in the next mask)
175 : : * 5. at any point in steps 2-4, we may do an early exit due to
176 : : * finding what we were looking for, or continue searching
177 : : * further
178 : : */
179 : 7207 : cur_msk = msk->data[msk_idx];
180 : :
181 : : /* if we're looking for free spaces, invert the mask */
182 [ + + ]: 7207 : if (!used)
183 : 5488 : cur_msk = ~cur_msk;
184 : :
185 : : /* first and last mask may not be aligned */
186 [ + + ]: 7207 : if (msk_idx == first)
187 : 5159 : cur_msk &= first_msk;
188 [ + + ]: 7207 : if (msk_idx == last)
189 : 120 : cur_msk &= last_msk;
190 : :
191 : : /* do we have an active previous run? */
192 [ + + ]: 7207 : if (run_started) {
193 : : /* figure out how many consecutive bits we need here */
194 : 2043 : need = RTE_MIN(left, MASK_ALIGN);
195 : :
196 : : /* see if we get a run of needed length */
197 : : tmp_msk = cur_msk;
198 [ + + ]: 112980 : for (s_idx = 0; s_idx < need - 1; s_idx++)
199 : 110937 : tmp_msk &= tmp_msk >> 1ULL;
200 : :
201 : : /* if first bit is set, we keep the run */
202 [ + + ]: 2043 : if (tmp_msk & 1) {
203 : 2041 : left -= need;
204 : :
205 : : /* did we find what we were looking for? */
206 [ + + ]: 2041 : if (left == 0)
207 : 1302 : return run_start;
208 : :
209 : : /* keep looking */
210 : 739 : continue;
211 : : }
212 : : /* we lost the run, reset */
213 : : run_started = false;
214 : : left = n;
215 : : }
216 : :
217 : : /* if we're here, we either lost the run or never had it */
218 : :
219 : : /* figure out how many consecutive bits we need here */
220 : 5166 : need = RTE_MIN(left, MASK_ALIGN);
221 : :
222 : : /* do a search */
223 : : tmp_msk = cur_msk;
224 [ + + ]: 113451 : for (s_idx = 0; s_idx < need - 1; s_idx++)
225 : 108285 : tmp_msk &= tmp_msk >> 1ULL;
226 : :
227 : : /* have we found something? */
228 [ + + ]: 5166 : if (tmp_msk != 0) {
229 : : /* figure out where the run started */
230 [ + + ]: 3871 : run_start = MASK_GET_IDX(msk_idx, rte_ctz64(tmp_msk));
231 : : run_started = true;
232 : 3871 : left -= need;
233 : :
234 : : /* do we need to look further? */
235 [ + + ]: 3871 : if (left == 0)
236 : 3856 : return run_start;
237 : :
238 : : /* we need to keep looking */
239 : 15 : continue;
240 : : }
241 : :
242 : : /* we didn't find our run within current mask, go for plan B. */
243 : :
244 : : /* count leading zeroes on inverted mask */
245 [ + + ]: 1295 : clz = rte_clz64(~cur_msk);
246 : :
247 : : /* if there aren't any set bits at the end, just continue */
248 [ + + ]: 1295 : if (clz == 0)
249 : 6 : continue;
250 : :
251 : : /* we have a partial run at the end */
252 : 1289 : run_start = MASK_GET_IDX(msk_idx, MASK_ALIGN - clz);
253 : : run_started = true;
254 : 1289 : left -= clz;
255 : :
256 : : /* we'll figure this out in the next iteration */
257 : : }
258 : : /* we didn't find anything */
259 [ - + ]: 1 : rte_errno = used ? ENOENT : ENOSPC;
260 : 1 : return -1;
261 : : }
262 : :
263 : : static int
264 : 610795 : find_next(const struct rte_fbarray *arr, unsigned int start, bool used)
265 : : {
266 : 610795 : const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
267 : 610795 : arr->len);
268 : : unsigned int idx, first, first_mod;
269 : : unsigned int last, last_mod;
270 : : uint64_t last_msk, ignore_msk;
271 : :
272 : : /*
273 : : * mask only has granularity of MASK_ALIGN, but start may not be aligned
274 : : * on that boundary, so construct a special mask to exclude anything we
275 : : * don't want to see to avoid confusing ctz.
276 : : */
277 : 610795 : first = MASK_LEN_TO_IDX(start);
278 : 610795 : first_mod = MASK_LEN_TO_MOD(start);
279 : 610795 : ignore_msk = ~((1ULL << first_mod) - 1ULL);
280 : :
281 : : /* array length may not be aligned, so calculate ignore mask for last
282 : : * mask index.
283 : : */
284 : 610795 : last = MASK_LEN_TO_IDX(arr->len);
285 : 610795 : last_mod = MASK_LEN_TO_MOD(arr->len);
286 : 610795 : last_msk = ~(-(1ULL) << last_mod);
287 : :
288 [ + + ]: 873663 : for (idx = first; idx < msk->n_masks; idx++) {
289 : 867298 : uint64_t cur = msk->data[idx];
290 : : int found;
291 : :
292 : : /* if we're looking for free entries, invert mask */
293 [ + + ]: 867298 : if (!used)
294 : 15126 : cur = ~cur;
295 : :
296 [ + + ]: 867298 : if (idx == last)
297 : 64 : cur &= last_msk;
298 : :
299 : : /* ignore everything before start on first iteration */
300 [ + + ]: 867298 : if (idx == first)
301 : 610795 : cur &= ignore_msk;
302 : :
303 : : /* check if we have any entries */
304 [ + + ]: 867298 : if (cur == 0)
305 : : continue;
306 : :
307 : : /*
308 : : * find first set bit - that will correspond to whatever it is
309 : : * that we're looking for.
310 : : */
311 : : found = rte_ctz64(cur);
312 : 604430 : return MASK_GET_IDX(idx, found);
313 : : }
314 : : /* we didn't find anything */
315 [ + + ]: 6365 : rte_errno = used ? ENOENT : ENOSPC;
316 : 6365 : return -1;
317 : : }
318 : :
319 : : static int
320 : 2561 : find_contig(const struct rte_fbarray *arr, unsigned int start, bool used)
321 : : {
322 : 2561 : const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
323 : 2561 : arr->len);
324 : : unsigned int idx, first, first_mod;
325 : : unsigned int last, last_mod;
326 : : uint64_t last_msk;
327 : : unsigned int need_len, result = 0;
328 : :
329 : : /* array length may not be aligned, so calculate ignore mask for last
330 : : * mask index.
331 : : */
332 : 2561 : last = MASK_LEN_TO_IDX(arr->len);
333 : 2561 : last_mod = MASK_LEN_TO_MOD(arr->len);
334 : 2561 : last_msk = ~(-(1ULL) << last_mod);
335 : :
336 : 2561 : first = MASK_LEN_TO_IDX(start);
337 : 2561 : first_mod = MASK_LEN_TO_MOD(start);
338 [ + + ]: 12960 : for (idx = first; idx < msk->n_masks; idx++, result += need_len) {
339 : 11663 : uint64_t cur = msk->data[idx];
340 : : unsigned int run_len;
341 : :
342 : : need_len = MASK_ALIGN;
343 : :
344 : : /* if we're looking for free entries, invert mask */
345 [ + + ]: 11663 : if (!used)
346 : 10319 : cur = ~cur;
347 : :
348 : : /* if this is last mask, ignore everything after last bit */
349 [ + + ]: 11663 : if (idx == last)
350 : 66 : cur &= last_msk;
351 : :
352 : : /* ignore everything before start on first iteration */
353 [ + + ]: 11663 : if (idx == first) {
354 : 2561 : cur >>= first_mod;
355 : : /* at the start, we don't need the full mask len */
356 : 2561 : need_len -= first_mod;
357 : : }
358 : :
359 : : /* we will be looking for zeroes, so invert the mask */
360 : 11663 : cur = ~cur;
361 : :
362 : : /* if mask is zero, we have a complete run */
363 [ + + ]: 11663 : if (cur == 0)
364 : 8307 : continue;
365 : :
366 : : /*
367 : : * see if current run ends before mask end.
368 : : */
369 : : run_len = rte_ctz64(cur);
370 : :
371 : : /* add however many zeroes we've had in the last run and quit */
372 [ + + ]: 3356 : if (run_len < need_len) {
373 : 1264 : result += run_len;
374 : 1264 : break;
375 : : }
376 : : }
377 : 2561 : return result;
378 : : }
379 : :
380 : : static int
381 : 2368 : find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
382 : : bool used)
383 : : {
384 : 2368 : const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
385 : 2368 : arr->len);
386 : : /* we're going backwards so we need negative space */
387 : : int64_t msk_idx;
388 : : unsigned int first, first_mod;
389 : : uint64_t first_msk;
390 : : unsigned int run_end, left;
391 : : bool run_started = false;
392 : :
393 : : /*
394 : : * mask only has granularity of MASK_ALIGN, but start may not be aligned
395 : : * on that boundary, so construct a special mask to exclude anything we
396 : : * don't want to see to avoid confusing clz. this "first" mask is
397 : : * actually our last because we're going backwards, so no second mask
398 : : * is required like in find_next_n case.
399 : : */
400 : 2368 : first = MASK_LEN_TO_IDX(start);
401 : 2368 : first_mod = MASK_LEN_TO_MOD(start);
402 : : /* we're going backwards, so mask must start from the top */
403 : : first_msk = first_mod == MASK_ALIGN - 1 ?
404 [ + + ]: 2368 : UINT64_MAX : /* prevent overflow */
405 : 899 : ~(UINT64_MAX << (first_mod + 1));
406 : :
407 : : left = n;
408 : :
409 : : /* go backwards, include zero */
410 [ + - ]: 4406 : for (msk_idx = first; msk_idx >= 0; msk_idx--) {
411 : : unsigned int s_idx, ctz, need;
412 : : uint64_t cur_msk, tmp_msk;
413 : :
414 : : /*
415 : : * In order to find N consecutive bits for arbitrary N, we need
416 : : * to be aware of the following:
417 : : *
418 : : * 1. To find N number of consecutive bits within a mask, we
419 : : * need to do N-1 lshift-ands and see if we still have set
420 : : * bits anywhere in the mask
421 : : * 2. N may be larger than mask size, in which case we need to
422 : : * do a search in multiple consecutive masks
423 : : * 3. For multi-mask search to be meaningful, we need to anchor
424 : : * our searches, i.e. first we find a run of M bits at the
425 : : * beginning of current mask, then we look for N-M bits at
426 : : * the end of previous mask (or multiple masks)
427 : : *
428 : : * With all of the above, the algorithm looks as follows:
429 : : *
430 : : * 1. let N be the number of consecutive bits we're looking for
431 : : * 2. if we already started a run, check if we can continue it
432 : : * by looking for remainder of N at the end of current mask
433 : : * 3. if we lost a run or if we never had a run, we look for N
434 : : * bits anywhere within the current mask (up to mask size,
435 : : * we can finish this run in the previous mask if N > mask
436 : : * size)
437 : : * 4. if we didn't find anything up to this point, check if any
438 : : * first bits of the mask are set (meaning we can start a
439 : : * run and finish it in the previous mask)
440 : : * 5. at any point in steps 2-4, we may do an early exit due to
441 : : * finding what we were looking for, or continue searching
442 : : * further
443 : : */
444 : 4406 : cur_msk = msk->data[msk_idx];
445 : :
446 : : /* if we're looking for free spaces, invert the mask */
447 [ + + ]: 4406 : if (!used)
448 : 3292 : cur_msk = ~cur_msk;
449 : :
450 : : /* first mask may not be aligned */
451 [ + + ]: 4406 : if (msk_idx == first)
452 : 2368 : cur_msk &= first_msk;
453 : :
454 : : /* do we have an active previous run? */
455 [ + + ]: 4406 : if (run_started) {
456 : : uint64_t last_bit = 0x1ULL << (MASK_ALIGN - 1);
457 : :
458 : : /* figure out how many consecutive bits we need here */
459 : 2032 : need = RTE_MIN(left, MASK_ALIGN);
460 : :
461 : : /* see if we get a run of needed length */
462 : : tmp_msk = cur_msk;
463 [ + + ]: 88175 : for (s_idx = 0; s_idx < need - 1; s_idx++)
464 : 86143 : tmp_msk &= tmp_msk << 1ULL;
465 : :
466 : : /* if last bit is set, we keep the run */
467 [ + + ]: 2032 : if (tmp_msk & last_bit) {
468 : 2030 : left -= need;
469 : :
470 : : /* did we find what we were looking for? */
471 [ + + ]: 2030 : if (left == 0)
472 : 1291 : return run_end - n;
473 : :
474 : : /* keep looking */
475 : 739 : continue;
476 : : }
477 : : /* we lost the run, reset */
478 : : run_started = false;
479 : : left = n;
480 : : }
481 : :
482 : : /* if we're here, we either lost the run or never had it */
483 : :
484 : : /* figure out how many consecutive bits we need here */
485 : 2376 : need = RTE_MIN(left, MASK_ALIGN);
486 : :
487 : : /* do a search */
488 : : tmp_msk = cur_msk;
489 [ + + ]: 110005 : for (s_idx = 0; s_idx < need - 1; s_idx++)
490 : 107629 : tmp_msk &= tmp_msk << 1ULL;
491 : :
492 : : /* have we found something? */
493 [ + + ]: 2376 : if (tmp_msk != 0) {
494 : : /* figure out where the run started */
495 [ + + ]: 1800 : run_end = MASK_GET_IDX(msk_idx, MASK_ALIGN - rte_clz64(tmp_msk));
496 : : run_started = true;
497 : 1800 : left -= need;
498 : :
499 : : /* do we need to look further? */
500 [ + + ]: 1800 : if (left == 0)
501 : 1077 : return run_end - n;
502 : :
503 : : /* we need to keep looking */
504 : 723 : continue;
505 : : }
506 : :
507 : : /* we didn't find our run within current mask, go for plan B. */
508 : :
509 : : /* count trailing zeroes on inverted mask */
510 [ + + ]: 576 : ctz = rte_ctz64(~cur_msk);
511 : :
512 : : /* if there aren't any set bits at the beginning, just continue */
513 [ + + ]: 576 : if (ctz == 0)
514 : 6 : continue;
515 : :
516 : : /* we have a partial run at the beginning */
517 : 570 : run_end = MASK_GET_IDX(msk_idx, ctz);
518 : : run_started = true;
519 : 570 : left -= ctz;
520 : :
521 : : /* we'll figure this out in the next iteration */
522 : : }
523 : : /* we didn't find anything */
524 [ # # ]: 0 : rte_errno = used ? ENOENT : ENOSPC;
525 : 0 : return -1;
526 : : }
527 : :
528 : : static int
529 : 2413 : find_prev(const struct rte_fbarray *arr, unsigned int start, bool used)
530 : : {
531 : 2413 : const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
532 : 2413 : arr->len);
533 : : unsigned int idx, first, first_mod;
534 : : uint64_t ignore_msk;
535 : :
536 : : /*
537 : : * mask only has granularity of MASK_ALIGN, but start may not be aligned
538 : : * on that boundary, so construct a special mask to exclude anything we
539 : : * don't want to see to avoid confusing clz.
540 : : */
541 : 2413 : first = MASK_LEN_TO_IDX(start);
542 : 2413 : first_mod = MASK_LEN_TO_MOD(start);
543 : : /* we're going backwards, so mask must start from the top */
544 : : ignore_msk = first_mod == MASK_ALIGN - 1 ?
545 [ + + ]: 2413 : UINT64_MAX : /* prevent overflow */
546 : 2348 : ~(UINT64_MAX << (first_mod + 1));
547 : :
548 : : /* go backwards, include zero */
549 : : idx = first;
550 : : do {
551 : 2454 : uint64_t cur = msk->data[idx];
552 : : int found;
553 : :
554 : : /* if we're looking for free entries, invert mask */
555 [ + + ]: 2454 : if (!used)
556 : 1801 : cur = ~cur;
557 : :
558 : : /* ignore everything before start on first iteration */
559 [ + + ]: 2454 : if (idx == first)
560 : 2413 : cur &= ignore_msk;
561 : :
562 : : /* check if we have any entries */
563 [ + + ]: 2454 : if (cur == 0)
564 : : continue;
565 : :
566 : : /*
567 : : * find last set bit - that will correspond to whatever it is
568 : : * that we're looking for. we're counting trailing zeroes, thus
569 : : * the value we get is counted from end of mask, so calculate
570 : : * position from start of mask.
571 : : */
572 : 2401 : found = MASK_ALIGN - rte_clz64(cur) - 1;
573 : :
574 : 2401 : return MASK_GET_IDX(idx, found);
575 [ + + ]: 53 : } while (idx-- != 0); /* decrement after check to include zero*/
576 : :
577 : : /* we didn't find anything */
578 [ + + ]: 12 : rte_errno = used ? ENOENT : ENOSPC;
579 : 12 : return -1;
580 : : }
581 : :
582 : : static int
583 : 4794 : find_rev_contig(const struct rte_fbarray *arr, unsigned int start, bool used)
584 : : {
585 : 4794 : const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
586 : 4794 : arr->len);
587 : : unsigned int idx, first, first_mod;
588 : : unsigned int need_len, result = 0;
589 : :
590 : 4794 : first = MASK_LEN_TO_IDX(start);
591 : : first_mod = MASK_LEN_TO_MOD(start);
592 : :
593 : : /* go backwards, include zero */
594 : : idx = first;
595 : : do {
596 : 11864 : uint64_t cur = msk->data[idx];
597 : : unsigned int run_len;
598 : :
599 : : need_len = MASK_ALIGN;
600 : :
601 : : /* if we're looking for free entries, invert mask */
602 [ + + ]: 11864 : if (!used)
603 : 9147 : cur = ~cur;
604 : :
605 : : /* ignore everything after start on first iteration */
606 [ + + ]: 11864 : if (idx == first) {
607 : : unsigned int end_len = MASK_ALIGN - first_mod - 1;
608 : 4794 : cur <<= end_len;
609 : : /* at the start, we don't need the full mask len */
610 : 4794 : need_len -= end_len;
611 : : }
612 : :
613 : : /* we will be looking for zeroes, so invert the mask */
614 : 11864 : cur = ~cur;
615 : :
616 : : /* if mask is zero, we have a complete run */
617 [ + + ]: 11864 : if (cur == 0)
618 : 5604 : goto endloop;
619 : :
620 : : /*
621 : : * see where run ends, starting from the end.
622 : : */
623 : : run_len = rte_clz64(cur);
624 : :
625 : : /* add however many zeroes we've had in the last run and quit */
626 [ + + ]: 6260 : if (run_len < need_len) {
627 : 3388 : result += run_len;
628 : 3388 : break;
629 : : }
630 : 2872 : endloop:
631 : 8476 : result += need_len;
632 [ + + ]: 8476 : } while (idx-- != 0); /* decrement after check to include zero */
633 : 4794 : return result;
634 : : }
635 : :
636 : : static int
637 : 47853966 : set_used(struct rte_fbarray *arr, unsigned int idx, bool used)
638 : : {
639 : : struct used_mask *msk;
640 : 47853966 : uint64_t msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);
641 : 47853966 : unsigned int msk_idx = MASK_LEN_TO_IDX(idx);
642 : : bool already_used;
643 : : int ret = -1;
644 : :
645 [ + + + + ]: 47853966 : if (arr == NULL || idx >= arr->len) {
646 : 4 : rte_errno = EINVAL;
647 : 4 : return -1;
648 : : }
649 : 47853962 : msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
650 : : ret = 0;
651 : :
652 : : /* prevent array from changing under us */
653 : 47853962 : rte_rwlock_write_lock(&arr->rwlock);
654 : :
655 : 47853962 : already_used = (msk->data[msk_idx] & msk_bit) != 0;
656 : :
657 : : /* nothing to be done */
658 [ + + ]: 47853962 : if (used == already_used)
659 : 2776 : goto out;
660 : :
661 [ + + ]: 47851186 : if (used) {
662 : 47843230 : msk->data[msk_idx] |= msk_bit;
663 : 47843230 : arr->count++;
664 : : } else {
665 : 7956 : msk->data[msk_idx] &= ~msk_bit;
666 : 7956 : arr->count--;
667 : : }
668 : 47853962 : out:
669 : : rte_rwlock_write_unlock(&arr->rwlock);
670 : :
671 : 47853962 : return ret;
672 : : }
673 : :
674 : : static int
675 : 1179 : fully_validate(const char *name, unsigned int elt_sz, unsigned int len)
676 : : {
677 [ + + + + ]: 1179 : if (name == NULL || elt_sz == 0 || len == 0 || len > INT_MAX) {
678 : 4 : rte_errno = EINVAL;
679 : 4 : return -1;
680 : : }
681 : :
682 [ - + ]: 1175 : if (strnlen(name, RTE_FBARRAY_NAME_LEN) == RTE_FBARRAY_NAME_LEN) {
683 : 0 : rte_errno = ENAMETOOLONG;
684 : 0 : return -1;
685 : : }
686 : : return 0;
687 : : }
688 : :
689 : : RTE_EXPORT_SYMBOL(rte_fbarray_init)
690 : : int
691 : 944 : rte_fbarray_init(struct rte_fbarray *arr, const char *name, unsigned int len,
692 : : unsigned int elt_sz)
693 : : {
694 : : size_t page_sz, mmap_len;
695 : : char path[PATH_MAX];
696 : : struct used_mask *msk;
697 : : struct mem_area *ma = NULL;
698 : : void *data = NULL;
699 : : int fd = -1;
700 : : const struct internal_config *internal_conf =
701 : 944 : eal_get_internal_configuration();
702 : :
703 [ + + ]: 944 : if (arr == NULL) {
704 : 1 : rte_errno = EINVAL;
705 : 1 : return -1;
706 : : }
707 : :
708 [ + + ]: 943 : if (fully_validate(name, elt_sz, len))
709 : : return -1;
710 : :
711 : : /* allocate mem area before doing anything */
712 : 939 : ma = malloc(sizeof(*ma));
713 [ - + ]: 939 : if (ma == NULL) {
714 : 0 : rte_errno = ENOMEM;
715 : 0 : return -1;
716 : : }
717 : :
718 : 939 : page_sz = rte_mem_page_size();
719 [ - + ]: 939 : if (page_sz == (size_t)-1) {
720 : 0 : free(ma);
721 : 0 : return -1;
722 : : }
723 : :
724 : : /* calculate our memory limits */
725 : 939 : mmap_len = calc_data_size(page_sz, elt_sz, len);
726 : :
727 : 939 : data = eal_get_virtual_area(NULL, &mmap_len, page_sz, 0, 0);
728 [ - + ]: 939 : if (data == NULL) {
729 : 0 : free(ma);
730 : 0 : return -1;
731 : : }
732 : :
733 : : rte_spinlock_lock(&mem_area_lock);
734 : :
735 : : fd = -1;
736 : :
737 [ + + ]: 939 : if (internal_conf->no_shconf) {
738 : : /* remap virtual area as writable */
739 : : static const int flags = RTE_MAP_FORCE_ADDRESS |
740 : : RTE_MAP_PRIVATE | RTE_MAP_ANONYMOUS;
741 : 47 : void *new_data = rte_mem_map(data, mmap_len,
742 : : RTE_PROT_READ | RTE_PROT_WRITE, flags, fd, 0);
743 [ - + ]: 47 : if (new_data == NULL) {
744 : 0 : EAL_LOG(DEBUG, "%s(): couldn't remap anonymous memory: %s",
745 : : __func__, rte_strerror(rte_errno));
746 : 0 : goto fail;
747 : : }
748 : : } else {
749 : 892 : eal_get_fbarray_path(path, sizeof(path), name);
750 : :
751 : : /*
752 : : * Each fbarray is unique to process namespace, i.e. the
753 : : * filename depends on process prefix. Try to take out a lock
754 : : * and see if we succeed. If we don't, someone else is using it
755 : : * already.
756 : : */
757 : 892 : fd = eal_file_open(path, EAL_OPEN_CREATE | EAL_OPEN_READWRITE);
758 [ - + ]: 892 : if (fd < 0) {
759 : 0 : EAL_LOG(DEBUG, "%s(): couldn't open %s: %s",
760 : : __func__, path, rte_strerror(rte_errno));
761 : 0 : goto fail;
762 [ - + ]: 892 : } else if (eal_file_lock(
763 : : fd, EAL_FLOCK_EXCLUSIVE, EAL_FLOCK_RETURN)) {
764 : 0 : EAL_LOG(DEBUG, "%s(): couldn't lock %s: %s",
765 : : __func__, path, rte_strerror(rte_errno));
766 : 0 : rte_errno = EBUSY;
767 : 0 : goto fail;
768 : : }
769 : :
770 : : /* take out a non-exclusive lock, so that other processes could
771 : : * still attach to it, but no other process could reinitialize
772 : : * it.
773 : : */
774 [ - + ]: 892 : if (eal_file_lock(fd, EAL_FLOCK_SHARED, EAL_FLOCK_RETURN))
775 : 0 : goto fail;
776 : :
777 [ - + ]: 892 : if (resize_and_map(fd, path, data, mmap_len))
778 : 0 : goto fail;
779 : : }
780 : 939 : ma->addr = data;
781 : 939 : ma->len = mmap_len;
782 : 939 : ma->fd = fd;
783 : :
784 : : /* do not close fd - keep it until detach/destroy */
785 : 939 : TAILQ_INSERT_TAIL(&mem_area_tailq, ma, next);
786 : :
787 : : /* initialize the data */
788 : : memset(data, 0, mmap_len);
789 : :
790 : : /* populate data structure */
791 : 939 : strlcpy(arr->name, name, sizeof(arr->name));
792 : 939 : arr->data = data;
793 : 939 : arr->len = len;
794 : 939 : arr->elt_sz = elt_sz;
795 : 939 : arr->count = 0;
796 : :
797 : : msk = get_used_mask(data, elt_sz, len);
798 : 939 : msk->n_masks = MASK_LEN_TO_IDX(RTE_ALIGN_CEIL(len, MASK_ALIGN));
799 : :
800 : : rte_rwlock_init(&arr->rwlock);
801 : :
802 : : rte_spinlock_unlock(&mem_area_lock);
803 : :
804 : 939 : return 0;
805 : 0 : fail:
806 : : if (data)
807 : 0 : rte_mem_unmap(data, mmap_len);
808 [ # # ]: 0 : if (fd >= 0)
809 : 0 : close(fd);
810 : 0 : free(ma);
811 : :
812 : : rte_spinlock_unlock(&mem_area_lock);
813 : 0 : return -1;
814 : : }
815 : :
816 : : RTE_EXPORT_SYMBOL(rte_fbarray_attach)
817 : : int
818 : 237 : rte_fbarray_attach(struct rte_fbarray *arr)
819 : : {
820 : : struct mem_area *ma = NULL, *tmp = NULL;
821 : : size_t page_sz, mmap_len;
822 : : char path[PATH_MAX];
823 : : void *data = NULL;
824 : : int fd = -1;
825 : :
826 [ + + ]: 237 : if (arr == NULL) {
827 : 1 : rte_errno = EINVAL;
828 : 1 : return -1;
829 : : }
830 : :
831 : : /*
832 : : * we don't need to synchronize attach as two values we need (element
833 : : * size and array length) are constant for the duration of life of
834 : : * the array, so the parts we care about will not race.
835 : : */
836 : :
837 [ + - ]: 236 : if (fully_validate(arr->name, arr->elt_sz, arr->len))
838 : : return -1;
839 : :
840 : 236 : ma = malloc(sizeof(*ma));
841 [ - + ]: 236 : if (ma == NULL) {
842 : 0 : rte_errno = ENOMEM;
843 : 0 : return -1;
844 : : }
845 : :
846 : 236 : page_sz = rte_mem_page_size();
847 [ - + ]: 236 : if (page_sz == (size_t)-1) {
848 : 0 : free(ma);
849 : 0 : return -1;
850 : : }
851 : :
852 : 236 : mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
853 : :
854 : : /* check the tailq - maybe user has already mapped this address space */
855 : : rte_spinlock_lock(&mem_area_lock);
856 : :
857 [ + + ]: 1173 : TAILQ_FOREACH(tmp, &mem_area_tailq, next) {
858 [ + - ]: 937 : if (overlap(tmp, arr->data, mmap_len)) {
859 : 0 : rte_errno = EEXIST;
860 : 0 : goto fail;
861 : : }
862 : : }
863 : :
864 : : /* we know this memory area is unique, so proceed */
865 : :
866 : 236 : data = eal_get_virtual_area(arr->data, &mmap_len, page_sz, 0, 0);
867 [ - + ]: 236 : if (data == NULL)
868 : 0 : goto fail;
869 : :
870 : 236 : eal_get_fbarray_path(path, sizeof(path), arr->name);
871 : :
872 : 236 : fd = eal_file_open(path, EAL_OPEN_READWRITE);
873 [ - + ]: 236 : if (fd < 0) {
874 : 0 : goto fail;
875 : : }
876 : :
877 : : /* lock the file, to let others know we're using it */
878 [ - + ]: 236 : if (eal_file_lock(fd, EAL_FLOCK_SHARED, EAL_FLOCK_RETURN))
879 : 0 : goto fail;
880 : :
881 [ - + ]: 236 : if (resize_and_map(fd, path, data, mmap_len))
882 : 0 : goto fail;
883 : :
884 : : /* store our new memory area */
885 : 236 : ma->addr = data;
886 : 236 : ma->fd = fd; /* keep fd until detach/destroy */
887 : 236 : ma->len = mmap_len;
888 : :
889 : 236 : TAILQ_INSERT_TAIL(&mem_area_tailq, ma, next);
890 : :
891 : : /* we're done */
892 : :
893 : : rte_spinlock_unlock(&mem_area_lock);
894 : 236 : return 0;
895 : 0 : fail:
896 [ # # ]: 0 : if (data)
897 : 0 : rte_mem_unmap(data, mmap_len);
898 [ # # ]: 0 : if (fd >= 0)
899 : 0 : close(fd);
900 : 0 : free(ma);
901 : : rte_spinlock_unlock(&mem_area_lock);
902 : 0 : return -1;
903 : : }
904 : :
905 : : RTE_EXPORT_SYMBOL(rte_fbarray_detach)
906 : : int
907 : 728 : rte_fbarray_detach(struct rte_fbarray *arr)
908 : : {
909 : : struct mem_area *tmp = NULL;
910 : : size_t mmap_len;
911 : : int ret = -1;
912 : :
913 [ + + ]: 728 : if (arr == NULL) {
914 : 1 : rte_errno = EINVAL;
915 : 1 : return -1;
916 : : }
917 : :
918 : : /*
919 : : * we don't need to synchronize detach as two values we need (element
920 : : * size and total capacity) are constant for the duration of life of
921 : : * the array, so the parts we care about will not race. if the user is
922 : : * detaching while doing something else in the same process, we can't
923 : : * really do anything about it, things will blow up either way.
924 : : */
925 : :
926 : 727 : size_t page_sz = rte_mem_page_size();
927 [ + - ]: 727 : if (page_sz == (size_t)-1)
928 : : return -1;
929 : :
930 : 727 : mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
931 : :
932 : : /* does this area exist? */
933 : : rte_spinlock_lock(&mem_area_lock);
934 : :
935 [ + - ]: 1454 : TAILQ_FOREACH(tmp, &mem_area_tailq, next) {
936 [ + + - + ]: 1454 : if (tmp->addr == arr->data && tmp->len == mmap_len)
937 : : break;
938 : : }
939 [ - + ]: 727 : if (tmp == NULL) {
940 : 0 : rte_errno = ENOENT;
941 : : ret = -1;
942 : 0 : goto out;
943 : : }
944 : :
945 : 727 : rte_mem_unmap(arr->data, mmap_len);
946 : :
947 : : /* area is unmapped, close fd and remove the tailq entry */
948 [ + + ]: 727 : if (tmp->fd >= 0)
949 : 723 : close(tmp->fd);
950 [ + + ]: 727 : TAILQ_REMOVE(&mem_area_tailq, tmp, next);
951 : 727 : free(tmp);
952 : :
953 : : ret = 0;
954 : 727 : out:
955 : : rte_spinlock_unlock(&mem_area_lock);
956 : 727 : return ret;
957 : : }
958 : :
959 : : RTE_EXPORT_SYMBOL(rte_fbarray_destroy)
960 : : int
961 : 229 : rte_fbarray_destroy(struct rte_fbarray *arr)
962 : : {
963 : : struct mem_area *tmp = NULL;
964 : : size_t mmap_len;
965 : : int fd, ret;
966 : : char path[PATH_MAX];
967 : : const struct internal_config *internal_conf =
968 : 229 : eal_get_internal_configuration();
969 : :
970 [ + + ]: 229 : if (arr == NULL) {
971 : 1 : rte_errno = EINVAL;
972 : 1 : return -1;
973 : : }
974 : :
975 : : /*
976 : : * we don't need to synchronize detach as two values we need (element
977 : : * size and total capacity) are constant for the duration of life of
978 : : * the array, so the parts we care about will not race. if the user is
979 : : * detaching while doing something else in the same process, we can't
980 : : * really do anything about it, things will blow up either way.
981 : : */
982 : :
983 : 228 : size_t page_sz = rte_mem_page_size();
984 [ + - ]: 228 : if (page_sz == (size_t)-1)
985 : : return -1;
986 : :
987 : 228 : mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
988 : :
989 : : /* does this area exist? */
990 : : rte_spinlock_lock(&mem_area_lock);
991 : :
992 [ + - ]: 2156 : TAILQ_FOREACH(tmp, &mem_area_tailq, next) {
993 [ + + - + ]: 2156 : if (tmp->addr == arr->data && tmp->len == mmap_len)
994 : : break;
995 : : }
996 [ - + ]: 228 : if (tmp == NULL) {
997 : 0 : rte_errno = ENOENT;
998 : : ret = -1;
999 : 0 : goto out;
1000 : : }
1001 : : /* with no shconf, there were never any files to begin with */
1002 [ + - ]: 228 : if (!internal_conf->no_shconf) {
1003 : : /*
1004 : : * attempt to get an exclusive lock on the file, to ensure it
1005 : : * has been detached by all other processes
1006 : : */
1007 : 228 : fd = tmp->fd;
1008 [ - + ]: 228 : if (eal_file_lock(fd, EAL_FLOCK_EXCLUSIVE, EAL_FLOCK_RETURN)) {
1009 : 0 : EAL_LOG(DEBUG, "Cannot destroy fbarray - another process is using it");
1010 : 0 : rte_errno = EBUSY;
1011 : : ret = -1;
1012 : 0 : goto out;
1013 : : }
1014 : :
1015 : : /* we're OK to destroy the file */
1016 : 228 : eal_get_fbarray_path(path, sizeof(path), arr->name);
1017 [ - + ]: 228 : if (unlink(path)) {
1018 : 0 : EAL_LOG(DEBUG, "Cannot unlink fbarray: %s",
1019 : : strerror(errno));
1020 : 0 : rte_errno = errno;
1021 : : /*
1022 : : * we're still holding an exclusive lock, so drop it to
1023 : : * shared.
1024 : : */
1025 : 0 : eal_file_lock(fd, EAL_FLOCK_SHARED, EAL_FLOCK_RETURN);
1026 : :
1027 : : ret = -1;
1028 : 0 : goto out;
1029 : : }
1030 : 228 : close(fd);
1031 : : }
1032 : 228 : rte_mem_unmap(arr->data, mmap_len);
1033 : :
1034 : : /* area is unmapped, remove the tailq entry */
1035 [ + + ]: 228 : TAILQ_REMOVE(&mem_area_tailq, tmp, next);
1036 : 228 : free(tmp);
1037 : : ret = 0;
1038 : :
1039 : : /* reset the fbarray structure */
1040 : : memset(arr, 0, sizeof(*arr));
1041 : 228 : out:
1042 : : rte_spinlock_unlock(&mem_area_lock);
1043 : 228 : return ret;
1044 : : }
1045 : :
1046 : : RTE_EXPORT_SYMBOL(rte_fbarray_get)
1047 : : void *
1048 : 146311617 : rte_fbarray_get(const struct rte_fbarray *arr, unsigned int idx)
1049 : : {
1050 : : void *ret = NULL;
1051 [ + + ]: 146311617 : if (arr == NULL) {
1052 : 1 : rte_errno = EINVAL;
1053 : 1 : return NULL;
1054 : : }
1055 : :
1056 [ + + ]: 146311616 : if (idx >= arr->len) {
1057 : 1 : rte_errno = EINVAL;
1058 : 1 : return NULL;
1059 : : }
1060 : :
1061 : 146311615 : ret = RTE_PTR_ADD(arr->data, idx * arr->elt_sz);
1062 : :
1063 : 146311615 : return ret;
1064 : : }
1065 : :
1066 : : RTE_EXPORT_SYMBOL(rte_fbarray_set_used)
1067 : : int
1068 : 47843232 : rte_fbarray_set_used(struct rte_fbarray *arr, unsigned int idx)
1069 : : {
1070 : 47843232 : return set_used(arr, idx, true);
1071 : : }
1072 : :
1073 : : RTE_EXPORT_SYMBOL(rte_fbarray_set_free)
1074 : : int
1075 : 10734 : rte_fbarray_set_free(struct rte_fbarray *arr, unsigned int idx)
1076 : : {
1077 : 10734 : return set_used(arr, idx, false);
1078 : : }
1079 : :
1080 : : RTE_EXPORT_SYMBOL(rte_fbarray_is_used)
1081 : : int
1082 : 7 : rte_fbarray_is_used(struct rte_fbarray *arr, unsigned int idx)
1083 : : {
1084 : : struct used_mask *msk;
1085 : : int msk_idx;
1086 : : uint64_t msk_bit;
1087 : : int ret = -1;
1088 : :
1089 [ + + + + ]: 7 : if (arr == NULL || idx >= arr->len) {
1090 : 2 : rte_errno = EINVAL;
1091 : 2 : return -1;
1092 : : }
1093 : :
1094 : : /* prevent array from changing under us */
1095 : 5 : rte_rwlock_read_lock(&arr->rwlock);
1096 : :
1097 : 5 : msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
1098 : 5 : msk_idx = MASK_LEN_TO_IDX(idx);
1099 : 5 : msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);
1100 : :
1101 : 5 : ret = (msk->data[msk_idx] & msk_bit) != 0;
1102 : :
1103 : : rte_rwlock_read_unlock(&arr->rwlock);
1104 : :
1105 : 5 : return ret;
1106 : : }
1107 : :
1108 : : static int
1109 : 48449339 : fbarray_find(struct rte_fbarray *arr, unsigned int start, bool next, bool used)
1110 : : {
1111 : : int ret = -1;
1112 : :
1113 [ + + + + ]: 48449339 : if (arr == NULL || start >= arr->len) {
1114 : 271 : rte_errno = EINVAL;
1115 : 271 : return -1;
1116 : : }
1117 : :
1118 : : /* prevent array from changing under us */
1119 : 48449068 : rte_rwlock_read_lock(&arr->rwlock);
1120 : :
1121 : : /* cheap checks to prevent doing useless work */
1122 [ + + ]: 48449068 : if (!used) {
1123 [ + + ]: 10221 : if (arr->len == arr->count) {
1124 : 8 : rte_errno = ENOSPC;
1125 : 8 : goto out;
1126 : : }
1127 [ + + ]: 10213 : if (arr->count == 0) {
1128 : 691 : ret = start;
1129 : 691 : goto out;
1130 : : }
1131 : : } else {
1132 [ + + ]: 48438847 : if (arr->count == 0) {
1133 : 313 : rte_errno = ENOENT;
1134 : 313 : goto out;
1135 : : }
1136 [ + + ]: 48438534 : if (arr->len == arr->count) {
1137 : 47834848 : ret = start;
1138 : 47834848 : goto out;
1139 : : }
1140 : : }
1141 [ + + ]: 613208 : if (next)
1142 : 610795 : ret = find_next(arr, start, used);
1143 : : else
1144 : 2413 : ret = find_prev(arr, start, used);
1145 : 48449068 : out:
1146 : : rte_rwlock_read_unlock(&arr->rwlock);
1147 : 48449068 : return ret;
1148 : : }
1149 : :
1150 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_next_free)
1151 : : int
1152 : 8233 : rte_fbarray_find_next_free(struct rte_fbarray *arr, unsigned int start)
1153 : : {
1154 : 8233 : return fbarray_find(arr, start, true, false);
1155 : : }
1156 : :
1157 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_next_used)
1158 : : int
1159 : 48438103 : rte_fbarray_find_next_used(struct rte_fbarray *arr, unsigned int start)
1160 : : {
1161 : 48438103 : return fbarray_find(arr, start, true, true);
1162 : : }
1163 : :
1164 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_prev_free)
1165 : : int
1166 : 2052 : rte_fbarray_find_prev_free(struct rte_fbarray *arr, unsigned int start)
1167 : : {
1168 : 2052 : return fbarray_find(arr, start, false, false);
1169 : : }
1170 : :
1171 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_prev_used)
1172 : : int
1173 : 951 : rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start)
1174 : : {
1175 : 951 : return fbarray_find(arr, start, false, true);
1176 : : }
1177 : :
1178 : : static int
1179 : 9317 : fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n,
1180 : : bool next, bool used)
1181 : : {
1182 : : int ret = -1;
1183 : :
1184 [ + + + + : 9317 : if (arr == NULL || start >= arr->len || n > arr->len || n == 0) {
+ + + + ]
1185 : 16 : rte_errno = EINVAL;
1186 : 16 : return -1;
1187 : : }
1188 [ + + - + ]: 9301 : if (next && (arr->len - start) < n) {
1189 [ # # ]: 0 : rte_errno = used ? ENOENT : ENOSPC;
1190 : 0 : return -1;
1191 : : }
1192 [ + + - + ]: 9301 : if (!next && start < (n - 1)) {
1193 [ # # ]: 0 : rte_errno = used ? ENOENT : ENOSPC;
1194 : 0 : return -1;
1195 : : }
1196 : :
1197 : : /* prevent array from changing under us */
1198 : 9301 : rte_rwlock_read_lock(&arr->rwlock);
1199 : :
1200 : : /* cheap checks to prevent doing useless work */
1201 [ + + ]: 9301 : if (!used) {
1202 [ + - - + ]: 6521 : if (arr->len == arr->count || arr->len - arr->count < n) {
1203 : 0 : rte_errno = ENOSPC;
1204 : 0 : goto out;
1205 : : }
1206 [ + + ]: 6521 : if (arr->count == 0) {
1207 [ + + ]: 822 : ret = next ? start : start - n + 1;
1208 : 822 : goto out;
1209 : : }
1210 : : } else {
1211 [ + + ]: 2780 : if (arr->count < n) {
1212 : 4 : rte_errno = ENOENT;
1213 : 4 : goto out;
1214 : : }
1215 [ + + ]: 2776 : if (arr->count == arr->len) {
1216 [ + + ]: 948 : ret = next ? start : start - n + 1;
1217 : 948 : goto out;
1218 : : }
1219 : : }
1220 : :
1221 [ + + ]: 7527 : if (next)
1222 : 5159 : ret = find_next_n(arr, start, n, used);
1223 : : else
1224 : 2368 : ret = find_prev_n(arr, start, n, used);
1225 : 9301 : out:
1226 : : rte_rwlock_read_unlock(&arr->rwlock);
1227 : 9301 : return ret;
1228 : : }
1229 : :
1230 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_next_n_free)
1231 : : int
1232 : 4507 : rte_fbarray_find_next_n_free(struct rte_fbarray *arr, unsigned int start,
1233 : : unsigned int n)
1234 : : {
1235 : 4507 : return fbarray_find_n(arr, start, n, true, false);
1236 : : }
1237 : :
1238 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_next_n_used)
1239 : : int
1240 : 1856 : rte_fbarray_find_next_n_used(struct rte_fbarray *arr, unsigned int start,
1241 : : unsigned int n)
1242 : : {
1243 : 1856 : return fbarray_find_n(arr, start, n, true, true);
1244 : : }
1245 : :
1246 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_prev_n_free)
1247 : : int
1248 : 2022 : rte_fbarray_find_prev_n_free(struct rte_fbarray *arr, unsigned int start,
1249 : : unsigned int n)
1250 : : {
1251 : 2022 : return fbarray_find_n(arr, start, n, false, false);
1252 : : }
1253 : :
1254 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_prev_n_used)
1255 : : int
1256 : 932 : rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start,
1257 : : unsigned int n)
1258 : : {
1259 : 932 : return fbarray_find_n(arr, start, n, false, true);
1260 : : }
1261 : :
1262 : : static int
1263 : 9286 : fbarray_find_contig(struct rte_fbarray *arr, unsigned int start, bool next,
1264 : : bool used)
1265 : : {
1266 : : int ret = -1;
1267 : :
1268 [ + + + + ]: 9286 : if (arr == NULL || start >= arr->len) {
1269 : 9 : rte_errno = EINVAL;
1270 : 9 : return -1;
1271 : : }
1272 : :
1273 : : /* prevent array from changing under us */
1274 : 9277 : rte_rwlock_read_lock(&arr->rwlock);
1275 : :
1276 : : /* cheap checks to prevent doing useless work */
1277 [ + + ]: 9277 : if (used) {
1278 [ + + ]: 3011 : if (arr->count == 0) {
1279 : : ret = 0;
1280 : 30 : goto out;
1281 : : }
1282 [ + + + + ]: 2981 : if (next && arr->count == arr->len) {
1283 : 420 : ret = arr->len - start;
1284 : 420 : goto out;
1285 : : }
1286 [ + + + + ]: 2561 : if (!next && arr->count == arr->len) {
1287 : 634 : ret = start + 1;
1288 : 634 : goto out;
1289 : : }
1290 : : } else {
1291 [ - + ]: 6266 : if (arr->len == arr->count) {
1292 : : ret = 0;
1293 : 0 : goto out;
1294 : : }
1295 [ + + + + ]: 6266 : if (next && arr->count == 0) {
1296 : 318 : ret = arr->len - start;
1297 : 318 : goto out;
1298 : : }
1299 [ + + + + ]: 5948 : if (!next && arr->count == 0) {
1300 : 520 : ret = start + 1;
1301 : 520 : goto out;
1302 : : }
1303 : : }
1304 : :
1305 [ + + ]: 7355 : if (next)
1306 : 2561 : ret = find_contig(arr, start, used);
1307 : : else
1308 : 4794 : ret = find_rev_contig(arr, start, used);
1309 : 9277 : out:
1310 : : rte_rwlock_read_unlock(&arr->rwlock);
1311 : 9277 : return ret;
1312 : : }
1313 : :
1314 : : static int
1315 : 90 : fbarray_find_biggest(struct rte_fbarray *arr, unsigned int start, bool used,
1316 : : bool rev)
1317 : : {
1318 : : int cur_idx, next_idx, cur_len, biggest_idx, biggest_len;
1319 : : /* don't stack if conditions, use function pointers instead */
1320 : : int (*find_func)(struct rte_fbarray *, unsigned int);
1321 : : int (*find_contig_func)(struct rte_fbarray *, unsigned int);
1322 : :
1323 [ + - - + ]: 90 : if (arr == NULL || start >= arr->len) {
1324 : 0 : rte_errno = EINVAL;
1325 : 0 : return -1;
1326 : : }
1327 : : /* the other API calls already do their fair share of cheap checks, so
1328 : : * no need to do them here.
1329 : : */
1330 : :
1331 : : /* the API's called are thread-safe, but something may still happen
1332 : : * between the API calls, so lock the fbarray. all other API's are
1333 : : * read-locking the fbarray, so read lock here is OK.
1334 : : */
1335 : 90 : rte_rwlock_read_lock(&arr->rwlock);
1336 : :
1337 : : /* pick out appropriate functions */
1338 [ + + ]: 90 : if (used) {
1339 [ + + ]: 26 : if (rev) {
1340 : : find_func = rte_fbarray_find_prev_used;
1341 : : find_contig_func = rte_fbarray_find_rev_contig_used;
1342 : : } else {
1343 : : find_func = rte_fbarray_find_next_used;
1344 : : find_contig_func = rte_fbarray_find_contig_used;
1345 : : }
1346 : : } else {
1347 [ + + ]: 64 : if (rev) {
1348 : : find_func = rte_fbarray_find_prev_free;
1349 : : find_contig_func = rte_fbarray_find_rev_contig_free;
1350 : : } else {
1351 : : find_func = rte_fbarray_find_next_free;
1352 : : find_contig_func = rte_fbarray_find_contig_free;
1353 : : }
1354 : : }
1355 : :
1356 : 90 : cur_idx = start;
1357 : : biggest_idx = -1; /* default is error */
1358 : : biggest_len = 0;
1359 : : for (;;) {
1360 : 160 : cur_idx = find_func(arr, cur_idx);
1361 : :
1362 : : /* block found, check its length */
1363 [ + + ]: 160 : if (cur_idx >= 0) {
1364 : 91 : cur_len = find_contig_func(arr, cur_idx);
1365 : : /* decide where we go next */
1366 [ + + ]: 91 : next_idx = rev ? cur_idx - cur_len : cur_idx + cur_len;
1367 : : /* move current index to start of chunk */
1368 [ + + ]: 91 : cur_idx = rev ? next_idx + 1 : cur_idx;
1369 : :
1370 [ + + ]: 91 : if (cur_len > biggest_len) {
1371 : : biggest_idx = cur_idx;
1372 : : biggest_len = cur_len;
1373 : : }
1374 : : cur_idx = next_idx;
1375 : : /* in reverse mode, next_idx may be -1 if chunk started
1376 : : * at array beginning. this means there's no more work
1377 : : * to do.
1378 : : */
1379 [ + + ]: 91 : if (cur_idx < 0)
1380 : : break;
1381 : : } else {
1382 : : /* nothing more to find, stop. however, a failed API
1383 : : * call has set rte_errno, which we want to ignore, as
1384 : : * reaching the end of fbarray is not an error.
1385 : : */
1386 : 69 : rte_errno = 0;
1387 : 69 : break;
1388 : : }
1389 : : }
1390 : : /* if we didn't find anything at all, set rte_errno */
1391 [ + + ]: 90 : if (biggest_idx < 0)
1392 [ + + ]: 24 : rte_errno = used ? ENOENT : ENOSPC;
1393 : :
1394 : : rte_rwlock_read_unlock(&arr->rwlock);
1395 : 90 : return biggest_idx;
1396 : : }
1397 : :
1398 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_biggest_free)
1399 : : int
1400 : 39 : rte_fbarray_find_biggest_free(struct rte_fbarray *arr, unsigned int start)
1401 : : {
1402 : 39 : return fbarray_find_biggest(arr, start, false, false);
1403 : : }
1404 : :
1405 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_biggest_used)
1406 : : int
1407 : 13 : rte_fbarray_find_biggest_used(struct rte_fbarray *arr, unsigned int start)
1408 : : {
1409 : 13 : return fbarray_find_biggest(arr, start, true, false);
1410 : : }
1411 : :
1412 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_rev_biggest_free)
1413 : : int
1414 : 25 : rte_fbarray_find_rev_biggest_free(struct rte_fbarray *arr, unsigned int start)
1415 : : {
1416 : 25 : return fbarray_find_biggest(arr, start, false, true);
1417 : : }
1418 : :
1419 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_rev_biggest_used)
1420 : : int
1421 : 13 : rte_fbarray_find_rev_biggest_used(struct rte_fbarray *arr, unsigned int start)
1422 : : {
1423 : 13 : return fbarray_find_biggest(arr, start, true, true);
1424 : : }
1425 : :
1426 : :
1427 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_contig_free)
1428 : : int
1429 : 2183 : rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start)
1430 : : {
1431 : 2183 : return fbarray_find_contig(arr, start, true, false);
1432 : : }
1433 : :
1434 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_contig_used)
1435 : : int
1436 : 1149 : rte_fbarray_find_contig_used(struct rte_fbarray *arr, unsigned int start)
1437 : : {
1438 : 1149 : return fbarray_find_contig(arr, start, true, true);
1439 : : }
1440 : :
1441 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_rev_contig_free)
1442 : : int
1443 : 4087 : rte_fbarray_find_rev_contig_free(struct rte_fbarray *arr, unsigned int start)
1444 : : {
1445 : 4087 : return fbarray_find_contig(arr, start, false, false);
1446 : : }
1447 : :
1448 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_rev_contig_used)
1449 : : int
1450 : 1867 : rte_fbarray_find_rev_contig_used(struct rte_fbarray *arr, unsigned int start)
1451 : : {
1452 : 1867 : return fbarray_find_contig(arr, start, false, true);
1453 : : }
1454 : :
1455 : : RTE_EXPORT_SYMBOL(rte_fbarray_find_idx)
1456 : : int
1457 : 6279 : rte_fbarray_find_idx(const struct rte_fbarray *arr, const void *elt)
1458 : : {
1459 : : void *end;
1460 : : int ret = -1;
1461 : :
1462 : : /*
1463 : : * no need to synchronize as it doesn't matter if underlying data
1464 : : * changes - we're doing pointer arithmetic here.
1465 : : */
1466 : :
1467 [ + + ]: 6279 : if (arr == NULL || elt == NULL) {
1468 : 2 : rte_errno = EINVAL;
1469 : 2 : return -1;
1470 : : }
1471 : 6277 : end = RTE_PTR_ADD(arr->data, arr->elt_sz * arr->len);
1472 [ + - - + ]: 6277 : if (elt < arr->data || elt >= end) {
1473 : 0 : rte_errno = EINVAL;
1474 : 0 : return -1;
1475 : : }
1476 : :
1477 : 6277 : ret = RTE_PTR_DIFF(elt, arr->data) / arr->elt_sz;
1478 : :
1479 : 6277 : return ret;
1480 : : }
1481 : :
1482 : : RTE_EXPORT_SYMBOL(rte_fbarray_dump_metadata)
1483 : : void
1484 : 0 : rte_fbarray_dump_metadata(struct rte_fbarray *arr, FILE *f)
1485 : : {
1486 : : struct used_mask *msk;
1487 : : unsigned int i;
1488 : :
1489 [ # # ]: 0 : if (arr == NULL || f == NULL) {
1490 : 0 : rte_errno = EINVAL;
1491 : 0 : return;
1492 : : }
1493 : :
1494 [ # # ]: 0 : if (fully_validate(arr->name, arr->elt_sz, arr->len)) {
1495 : : fprintf(f, "Invalid file-backed array\n");
1496 : 0 : return;
1497 : : }
1498 : :
1499 : : /* prevent array from changing under us */
1500 : 0 : rte_rwlock_read_lock(&arr->rwlock);
1501 : :
1502 : : fprintf(f, "File-backed array: %s\n", arr->name);
1503 : 0 : fprintf(f, "size: %i occupied: %i elt_sz: %i\n",
1504 : : arr->len, arr->count, arr->elt_sz);
1505 : :
1506 : 0 : msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
1507 : :
1508 [ # # ]: 0 : for (i = 0; i < msk->n_masks; i++)
1509 : 0 : fprintf(f, "msk idx %i: 0x%016" PRIx64 "\n", i, msk->data[i]);
1510 : : rte_rwlock_read_unlock(&arr->rwlock);
1511 : : }
|
