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