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