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