1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2017-2018 Intel Corporation
14 #include <rte_common.h>
16 #include <rte_errno.h>
17 #include <rte_spinlock.h>
18 #include <rte_tailq.h>
20 #include "eal_filesystem.h"
21 #include "eal_private.h"
23 #include "rte_fbarray.h"
25 #define MASK_SHIFT 6ULL
26 #define MASK_ALIGN (1ULL << MASK_SHIFT)
27 #define MASK_LEN_TO_IDX(x) ((x) >> MASK_SHIFT)
28 #define MASK_LEN_TO_MOD(x) ((x) - RTE_ALIGN_FLOOR(x, MASK_ALIGN))
29 #define MASK_GET_IDX(idx, mod) ((idx << MASK_SHIFT) + mod)
32 * This is a mask that is always stored at the end of array, to provide fast
33 * way of finding free/used spots without looping through each element.
42 calc_mask_size(unsigned int len)
44 /* mask must be multiple of MASK_ALIGN, even though length of array
45 * itself may not be aligned on that boundary.
47 len = RTE_ALIGN_CEIL(len, MASK_ALIGN);
48 return sizeof(struct used_mask) +
49 sizeof(uint64_t) * MASK_LEN_TO_IDX(len);
53 calc_data_size(size_t page_sz, unsigned int elt_sz, unsigned int len)
55 size_t data_sz = elt_sz * len;
56 size_t msk_sz = calc_mask_size(len);
57 return RTE_ALIGN_CEIL(data_sz + msk_sz, page_sz);
60 static struct used_mask *
61 get_used_mask(void *data, unsigned int elt_sz, unsigned int len)
63 return (struct used_mask *) RTE_PTR_ADD(data, elt_sz * len);
67 resize_and_map(int fd, void *addr, size_t len)
72 if (ftruncate(fd, len)) {
73 RTE_LOG(ERR, EAL, "Cannot truncate %s\n", path);
74 /* pass errno up the chain */
79 map_addr = mmap(addr, len, PROT_READ | PROT_WRITE,
80 MAP_SHARED | MAP_FIXED, fd, 0);
81 if (map_addr != addr) {
82 RTE_LOG(ERR, EAL, "mmap() failed: %s\n", strerror(errno));
83 /* pass errno up the chain */
91 find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
94 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
96 unsigned int msk_idx, lookahead_idx, first, first_mod;
97 unsigned int last, last_mod;
98 uint64_t last_msk, ignore_msk;
101 * mask only has granularity of MASK_ALIGN, but start may not be aligned
102 * on that boundary, so construct a special mask to exclude anything we
103 * don't want to see to avoid confusing ctz.
105 first = MASK_LEN_TO_IDX(start);
106 first_mod = MASK_LEN_TO_MOD(start);
107 ignore_msk = ~((1ULL << first_mod) - 1);
109 /* array length may not be aligned, so calculate ignore mask for last
112 last = MASK_LEN_TO_IDX(arr->len);
113 last_mod = MASK_LEN_TO_MOD(arr->len);
114 last_msk = ~(-1ULL << last_mod);
116 for (msk_idx = first; msk_idx < msk->n_masks; msk_idx++) {
117 uint64_t cur_msk, lookahead_msk;
118 unsigned int run_start, clz, left;
121 * The process of getting n consecutive bits for arbitrary n is
122 * a bit involved, but here it is in a nutshell:
124 * 1. let n be the number of consecutive bits we're looking for
125 * 2. check if n can fit in one mask, and if so, do n-1
126 * rshift-ands to see if there is an appropriate run inside
128 * 2a. if we found a run, bail out early
129 * 2b. if we didn't find a run, proceed
130 * 3. invert the mask and count leading zeroes (that is, count
131 * how many consecutive set bits we had starting from the
132 * end of current mask) as k
133 * 3a. if k is 0, continue to next mask
134 * 3b. if k is not 0, we have a potential run
135 * 4. to satisfy our requirements, next mask must have n-k
136 * consecutive set bits right at the start, so we will do
137 * (n-k-1) rshift-ands and check if first bit is set.
139 * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until
140 * we either run out of masks, lose the run, or find what we
143 cur_msk = msk->data[msk_idx];
146 /* if we're looking for free spaces, invert the mask */
150 /* combine current ignore mask with last index ignore mask */
152 ignore_msk |= last_msk;
154 /* if we have an ignore mask, ignore once */
156 cur_msk &= ignore_msk;
160 /* if n can fit in within a single mask, do a search */
161 if (n <= MASK_ALIGN) {
162 uint64_t tmp_msk = cur_msk;
164 for (s_idx = 0; s_idx < n - 1; s_idx++)
165 tmp_msk &= tmp_msk >> 1ULL;
166 /* we found what we were looking for */
168 run_start = __builtin_ctzll(tmp_msk);
169 return MASK_GET_IDX(msk_idx, run_start);
174 * we didn't find our run within the mask, or n > MASK_ALIGN,
175 * so we're going for plan B.
178 /* count leading zeroes on inverted mask */
180 clz = sizeof(cur_msk) * 8;
182 clz = __builtin_clzll(~cur_msk);
184 /* if there aren't any runs at the end either, just continue */
188 /* we have a partial run at the end, so try looking ahead */
189 run_start = MASK_ALIGN - clz;
192 for (lookahead_idx = msk_idx + 1; lookahead_idx < msk->n_masks;
194 unsigned int s_idx, need;
195 lookahead_msk = msk->data[lookahead_idx];
197 /* if we're looking for free space, invert the mask */
199 lookahead_msk = ~lookahead_msk;
201 /* figure out how many consecutive bits we need here */
202 need = RTE_MIN(left, MASK_ALIGN);
204 for (s_idx = 0; s_idx < need - 1; s_idx++)
205 lookahead_msk &= lookahead_msk >> 1ULL;
207 /* if first bit is not set, we've lost the run */
208 if ((lookahead_msk & 1) == 0) {
210 * we've scanned this far, so we know there are
211 * no runs in the space we've lookahead-scanned
212 * as well, so skip that on next iteration.
214 ignore_msk = ~((1ULL << need) - 1);
215 msk_idx = lookahead_idx;
221 /* check if we've found what we were looking for */
228 /* we didn't find anything, so continue */
232 return MASK_GET_IDX(msk_idx, run_start);
234 /* we didn't find anything */
235 rte_errno = used ? ENOENT : ENOSPC;
240 find_next(const struct rte_fbarray *arr, unsigned int start, bool used)
242 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
244 unsigned int idx, first, first_mod;
245 unsigned int last, last_mod;
246 uint64_t last_msk, ignore_msk;
249 * mask only has granularity of MASK_ALIGN, but start may not be aligned
250 * on that boundary, so construct a special mask to exclude anything we
251 * don't want to see to avoid confusing ctz.
253 first = MASK_LEN_TO_IDX(start);
254 first_mod = MASK_LEN_TO_MOD(start);
255 ignore_msk = ~((1ULL << first_mod) - 1ULL);
257 /* array length may not be aligned, so calculate ignore mask for last
260 last = MASK_LEN_TO_IDX(arr->len);
261 last_mod = MASK_LEN_TO_MOD(arr->len);
262 last_msk = ~(-(1ULL) << last_mod);
264 for (idx = first; idx < msk->n_masks; idx++) {
265 uint64_t cur = msk->data[idx];
268 /* if we're looking for free entries, invert mask */
275 /* ignore everything before start on first iteration */
279 /* check if we have any entries */
284 * find first set bit - that will correspond to whatever it is
285 * that we're looking for.
287 found = __builtin_ctzll(cur);
288 return MASK_GET_IDX(idx, found);
290 /* we didn't find anything */
291 rte_errno = used ? ENOENT : ENOSPC;
296 find_contig(const struct rte_fbarray *arr, unsigned int start, bool used)
298 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
300 unsigned int idx, first, first_mod;
301 unsigned int last, last_mod;
303 unsigned int need_len, result = 0;
305 /* array length may not be aligned, so calculate ignore mask for last
308 last = MASK_LEN_TO_IDX(arr->len);
309 last_mod = MASK_LEN_TO_MOD(arr->len);
310 last_msk = ~(-(1ULL) << last_mod);
312 first = MASK_LEN_TO_IDX(start);
313 first_mod = MASK_LEN_TO_MOD(start);
314 for (idx = first; idx < msk->n_masks; idx++, result += need_len) {
315 uint64_t cur = msk->data[idx];
316 unsigned int run_len;
318 need_len = MASK_ALIGN;
320 /* if we're looking for free entries, invert mask */
324 /* if this is last mask, ignore everything after last bit */
328 /* ignore everything before start on first iteration */
331 /* at the start, we don't need the full mask len */
332 need_len -= first_mod;
335 /* we will be looking for zeroes, so invert the mask */
338 /* if mask is zero, we have a complete run */
343 * see if current run ends before mask end.
345 run_len = __builtin_ctzll(cur);
347 /* add however many zeroes we've had in the last run and quit */
348 if (run_len < need_len) {
357 find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
360 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
362 unsigned int msk_idx, lookbehind_idx, first, first_mod;
366 * mask only has granularity of MASK_ALIGN, but start may not be aligned
367 * on that boundary, so construct a special mask to exclude anything we
368 * don't want to see to avoid confusing ctz.
370 first = MASK_LEN_TO_IDX(start);
371 first_mod = MASK_LEN_TO_MOD(start);
372 /* we're going backwards, so mask must start from the top */
373 ignore_msk = first_mod == MASK_ALIGN - 1 ?
374 -1ULL : /* prevent overflow */
375 ~(-1ULL << (first_mod + 1));
377 /* go backwards, include zero */
380 uint64_t cur_msk, lookbehind_msk;
381 unsigned int run_start, run_end, ctz, left;
384 * The process of getting n consecutive bits from the top for
385 * arbitrary n is a bit involved, but here it is in a nutshell:
387 * 1. let n be the number of consecutive bits we're looking for
388 * 2. check if n can fit in one mask, and if so, do n-1
389 * lshift-ands to see if there is an appropriate run inside
391 * 2a. if we found a run, bail out early
392 * 2b. if we didn't find a run, proceed
393 * 3. invert the mask and count trailing zeroes (that is, count
394 * how many consecutive set bits we had starting from the
395 * start of current mask) as k
396 * 3a. if k is 0, continue to next mask
397 * 3b. if k is not 0, we have a potential run
398 * 4. to satisfy our requirements, next mask must have n-k
399 * consecutive set bits at the end, so we will do (n-k-1)
400 * lshift-ands and check if last bit is set.
402 * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until
403 * we either run out of masks, lose the run, or find what we
406 cur_msk = msk->data[msk_idx];
409 /* if we're looking for free spaces, invert the mask */
413 /* if we have an ignore mask, ignore once */
415 cur_msk &= ignore_msk;
419 /* if n can fit in within a single mask, do a search */
420 if (n <= MASK_ALIGN) {
421 uint64_t tmp_msk = cur_msk;
423 for (s_idx = 0; s_idx < n - 1; s_idx++)
424 tmp_msk &= tmp_msk << 1ULL;
425 /* we found what we were looking for */
427 /* clz will give us offset from end of mask, and
428 * we only get the end of our run, not start,
429 * so adjust result to point to where start
432 run_start = MASK_ALIGN -
433 __builtin_clzll(tmp_msk) - n;
434 return MASK_GET_IDX(msk_idx, run_start);
439 * we didn't find our run within the mask, or n > MASK_ALIGN,
440 * so we're going for plan B.
443 /* count trailing zeroes on inverted mask */
445 ctz = sizeof(cur_msk) * 8;
447 ctz = __builtin_ctzll(~cur_msk);
449 /* if there aren't any runs at the start either, just
455 /* we have a partial run at the start, so try looking behind */
456 run_end = MASK_GET_IDX(msk_idx, ctz);
459 /* go backwards, include zero */
460 lookbehind_idx = msk_idx - 1;
462 /* we can't lookbehind as we've run out of masks, so stop */
467 const uint64_t last_bit = 1ULL << (MASK_ALIGN - 1);
468 unsigned int s_idx, need;
470 lookbehind_msk = msk->data[lookbehind_idx];
472 /* if we're looking for free space, invert the mask */
474 lookbehind_msk = ~lookbehind_msk;
476 /* figure out how many consecutive bits we need here */
477 need = RTE_MIN(left, MASK_ALIGN);
479 for (s_idx = 0; s_idx < need - 1; s_idx++)
480 lookbehind_msk &= lookbehind_msk << 1ULL;
482 /* if last bit is not set, we've lost the run */
483 if ((lookbehind_msk & last_bit) == 0) {
485 * we've scanned this far, so we know there are
486 * no runs in the space we've lookbehind-scanned
487 * as well, so skip that on next iteration.
489 ignore_msk = -1ULL << need;
490 msk_idx = lookbehind_idx;
496 /* check if we've found what we were looking for */
501 } while ((lookbehind_idx--) != 0); /* decrement after check to
505 /* we didn't find anything, so continue */
509 /* we've found what we were looking for, but we only know where
510 * the run ended, so calculate start position.
513 } while (msk_idx-- != 0); /* decrement after check to include zero */
514 /* we didn't find anything */
515 rte_errno = used ? ENOENT : ENOSPC;
520 find_prev(const struct rte_fbarray *arr, unsigned int start, bool used)
522 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
524 unsigned int idx, first, first_mod;
528 * mask only has granularity of MASK_ALIGN, but start may not be aligned
529 * on that boundary, so construct a special mask to exclude anything we
530 * don't want to see to avoid confusing clz.
532 first = MASK_LEN_TO_IDX(start);
533 first_mod = MASK_LEN_TO_MOD(start);
534 /* we're going backwards, so mask must start from the top */
535 ignore_msk = first_mod == MASK_ALIGN - 1 ?
536 -1ULL : /* prevent overflow */
537 ~(-1ULL << (first_mod + 1));
539 /* go backwards, include zero */
542 uint64_t cur = msk->data[idx];
545 /* if we're looking for free entries, invert mask */
549 /* ignore everything before start on first iteration */
553 /* check if we have any entries */
558 * find last set bit - that will correspond to whatever it is
559 * that we're looking for. we're counting trailing zeroes, thus
560 * the value we get is counted from end of mask, so calculate
561 * position from start of mask.
563 found = MASK_ALIGN - __builtin_clzll(cur) - 1;
565 return MASK_GET_IDX(idx, found);
566 } while (idx-- != 0); /* decrement after check to include zero*/
568 /* we didn't find anything */
569 rte_errno = used ? ENOENT : ENOSPC;
574 find_rev_contig(const struct rte_fbarray *arr, unsigned int start, bool used)
576 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
578 unsigned int idx, first, first_mod;
579 unsigned int need_len, result = 0;
581 first = MASK_LEN_TO_IDX(start);
582 first_mod = MASK_LEN_TO_MOD(start);
584 /* go backwards, include zero */
587 uint64_t cur = msk->data[idx];
588 unsigned int run_len;
590 need_len = MASK_ALIGN;
592 /* if we're looking for free entries, invert mask */
596 /* ignore everything after start on first iteration */
598 unsigned int end_len = MASK_ALIGN - first_mod - 1;
600 /* at the start, we don't need the full mask len */
604 /* we will be looking for zeroes, so invert the mask */
607 /* if mask is zero, we have a complete run */
612 * see where run ends, starting from the end.
614 run_len = __builtin_clzll(cur);
616 /* add however many zeroes we've had in the last run and quit */
617 if (run_len < need_len) {
623 } while (idx-- != 0); /* decrement after check to include zero */
628 set_used(struct rte_fbarray *arr, unsigned int idx, bool used)
630 struct used_mask *msk;
631 uint64_t msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);
632 unsigned int msk_idx = MASK_LEN_TO_IDX(idx);
636 if (arr == NULL || idx >= arr->len) {
640 msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
643 /* prevent array from changing under us */
644 rte_rwlock_write_lock(&arr->rwlock);
646 already_used = (msk->data[msk_idx] & msk_bit) != 0;
648 /* nothing to be done */
649 if (used == already_used)
653 msk->data[msk_idx] |= msk_bit;
656 msk->data[msk_idx] &= ~msk_bit;
660 rte_rwlock_write_unlock(&arr->rwlock);
666 fully_validate(const char *name, unsigned int elt_sz, unsigned int len)
668 if (name == NULL || elt_sz == 0 || len == 0 || len > INT_MAX) {
673 if (strnlen(name, RTE_FBARRAY_NAME_LEN) == RTE_FBARRAY_NAME_LEN) {
674 rte_errno = ENAMETOOLONG;
680 int __rte_experimental
681 rte_fbarray_init(struct rte_fbarray *arr, const char *name, unsigned int len,
684 size_t page_sz, mmap_len;
686 struct used_mask *msk;
695 if (fully_validate(name, elt_sz, len))
698 page_sz = sysconf(_SC_PAGESIZE);
699 if (page_sz == (size_t)-1)
702 /* calculate our memory limits */
703 mmap_len = calc_data_size(page_sz, elt_sz, len);
705 data = eal_get_virtual_area(NULL, &mmap_len, page_sz, 0, 0);
709 if (internal_config.no_shconf) {
710 /* remap virtual area as writable */
711 void *new_data = mmap(data, mmap_len, PROT_READ | PROT_WRITE,
712 MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
713 if (new_data == MAP_FAILED) {
714 RTE_LOG(DEBUG, EAL, "%s(): couldn't remap anonymous memory: %s\n",
715 __func__, strerror(errno));
719 eal_get_fbarray_path(path, sizeof(path), name);
722 * Each fbarray is unique to process namespace, i.e. the
723 * filename depends on process prefix. Try to take out a lock
724 * and see if we succeed. If we don't, someone else is using it
727 fd = open(path, O_CREAT | O_RDWR, 0600);
729 RTE_LOG(DEBUG, EAL, "%s(): couldn't open %s: %s\n",
730 __func__, path, strerror(errno));
733 } else if (flock(fd, LOCK_EX | LOCK_NB)) {
734 RTE_LOG(DEBUG, EAL, "%s(): couldn't lock %s: %s\n",
735 __func__, path, strerror(errno));
740 /* take out a non-exclusive lock, so that other processes could
741 * still attach to it, but no other process could reinitialize
744 if (flock(fd, LOCK_SH | LOCK_NB)) {
749 if (resize_and_map(fd, data, mmap_len))
752 /* we've mmap'ed the file, we can now close the fd */
756 /* initialize the data */
757 memset(data, 0, mmap_len);
759 /* populate data structure */
760 strlcpy(arr->name, name, sizeof(arr->name));
763 arr->elt_sz = elt_sz;
766 msk = get_used_mask(data, elt_sz, len);
767 msk->n_masks = MASK_LEN_TO_IDX(RTE_ALIGN_CEIL(len, MASK_ALIGN));
769 rte_rwlock_init(&arr->rwlock);
774 munmap(data, mmap_len);
780 int __rte_experimental
781 rte_fbarray_attach(struct rte_fbarray *arr)
783 size_t page_sz, mmap_len;
794 * we don't need to synchronize attach as two values we need (element
795 * size and array length) are constant for the duration of life of
796 * the array, so the parts we care about will not race.
799 if (fully_validate(arr->name, arr->elt_sz, arr->len))
802 page_sz = sysconf(_SC_PAGESIZE);
803 if (page_sz == (size_t)-1)
806 mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
808 data = eal_get_virtual_area(arr->data, &mmap_len, page_sz, 0, 0);
812 eal_get_fbarray_path(path, sizeof(path), arr->name);
814 fd = open(path, O_RDWR);
820 /* lock the file, to let others know we're using it */
821 if (flock(fd, LOCK_SH | LOCK_NB)) {
826 if (resize_and_map(fd, data, mmap_len))
836 munmap(data, mmap_len);
842 int __rte_experimental
843 rte_fbarray_detach(struct rte_fbarray *arr)
851 * we don't need to synchronize detach as two values we need (element
852 * size and total capacity) are constant for the duration of life of
853 * the array, so the parts we care about will not race. if the user is
854 * detaching while doing something else in the same process, we can't
855 * really do anything about it, things will blow up either way.
858 size_t page_sz = sysconf(_SC_PAGESIZE);
860 if (page_sz == (size_t)-1)
863 /* this may already be unmapped (e.g. repeated call from previously
864 * failed destroy(), but this is on user, we can't (easily) know if this
867 munmap(arr->data, calc_data_size(page_sz, arr->elt_sz, arr->len));
872 int __rte_experimental
873 rte_fbarray_destroy(struct rte_fbarray *arr)
878 ret = rte_fbarray_detach(arr);
882 /* with no shconf, there were never any files to begin with */
883 if (internal_config.no_shconf)
886 /* try deleting the file */
887 eal_get_fbarray_path(path, sizeof(path), arr->name);
889 fd = open(path, O_RDONLY);
891 RTE_LOG(ERR, EAL, "Could not open fbarray file: %s\n",
895 if (flock(fd, LOCK_EX | LOCK_NB)) {
896 RTE_LOG(DEBUG, EAL, "Cannot destroy fbarray - another process is using it\n");
902 memset(arr, 0, sizeof(*arr));
909 void * __rte_experimental
910 rte_fbarray_get(const struct rte_fbarray *arr, unsigned int idx)
918 if (idx >= arr->len) {
923 ret = RTE_PTR_ADD(arr->data, idx * arr->elt_sz);
928 int __rte_experimental
929 rte_fbarray_set_used(struct rte_fbarray *arr, unsigned int idx)
931 return set_used(arr, idx, true);
934 int __rte_experimental
935 rte_fbarray_set_free(struct rte_fbarray *arr, unsigned int idx)
937 return set_used(arr, idx, false);
940 int __rte_experimental
941 rte_fbarray_is_used(struct rte_fbarray *arr, unsigned int idx)
943 struct used_mask *msk;
948 if (arr == NULL || idx >= arr->len) {
953 /* prevent array from changing under us */
954 rte_rwlock_read_lock(&arr->rwlock);
956 msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
957 msk_idx = MASK_LEN_TO_IDX(idx);
958 msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);
960 ret = (msk->data[msk_idx] & msk_bit) != 0;
962 rte_rwlock_read_unlock(&arr->rwlock);
968 fbarray_find(struct rte_fbarray *arr, unsigned int start, bool next, bool used)
972 if (arr == NULL || start >= arr->len) {
977 /* prevent array from changing under us */
978 rte_rwlock_read_lock(&arr->rwlock);
980 /* cheap checks to prevent doing useless work */
982 if (arr->len == arr->count) {
986 if (arr->count == 0) {
991 if (arr->count == 0) {
995 if (arr->len == arr->count) {
1001 ret = find_next(arr, start, used);
1003 ret = find_prev(arr, start, used);
1005 rte_rwlock_read_unlock(&arr->rwlock);
1009 int __rte_experimental
1010 rte_fbarray_find_next_free(struct rte_fbarray *arr, unsigned int start)
1012 return fbarray_find(arr, start, true, false);
1015 int __rte_experimental
1016 rte_fbarray_find_next_used(struct rte_fbarray *arr, unsigned int start)
1018 return fbarray_find(arr, start, true, true);
1021 int __rte_experimental
1022 rte_fbarray_find_prev_free(struct rte_fbarray *arr, unsigned int start)
1024 return fbarray_find(arr, start, false, false);
1027 int __rte_experimental
1028 rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start)
1030 return fbarray_find(arr, start, false, true);
1034 fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n,
1035 bool next, bool used)
1039 if (arr == NULL || start >= arr->len || n > arr->len || n == 0) {
1043 if (next && (arr->len - start) < n) {
1044 rte_errno = used ? ENOENT : ENOSPC;
1047 if (!next && start < (n - 1)) {
1048 rte_errno = used ? ENOENT : ENOSPC;
1052 /* prevent array from changing under us */
1053 rte_rwlock_read_lock(&arr->rwlock);
1055 /* cheap checks to prevent doing useless work */
1057 if (arr->len == arr->count || arr->len - arr->count < n) {
1061 if (arr->count == 0) {
1062 ret = next ? start : start - n + 1;
1066 if (arr->count < n) {
1070 if (arr->count == arr->len) {
1071 ret = next ? start : start - n + 1;
1077 ret = find_next_n(arr, start, n, used);
1079 ret = find_prev_n(arr, start, n, used);
1081 rte_rwlock_read_unlock(&arr->rwlock);
1085 int __rte_experimental
1086 rte_fbarray_find_next_n_free(struct rte_fbarray *arr, unsigned int start,
1089 return fbarray_find_n(arr, start, n, true, false);
1092 int __rte_experimental
1093 rte_fbarray_find_next_n_used(struct rte_fbarray *arr, unsigned int start,
1096 return fbarray_find_n(arr, start, n, true, true);
1099 int __rte_experimental
1100 rte_fbarray_find_prev_n_free(struct rte_fbarray *arr, unsigned int start,
1103 return fbarray_find_n(arr, start, n, false, false);
1106 int __rte_experimental
1107 rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start,
1110 return fbarray_find_n(arr, start, n, false, true);
1114 fbarray_find_contig(struct rte_fbarray *arr, unsigned int start, bool next,
1119 if (arr == NULL || start >= arr->len) {
1124 /* prevent array from changing under us */
1125 rte_rwlock_read_lock(&arr->rwlock);
1127 /* cheap checks to prevent doing useless work */
1129 if (arr->count == 0) {
1133 if (next && arr->count == arr->len) {
1134 ret = arr->len - start;
1137 if (!next && arr->count == arr->len) {
1142 if (arr->len == arr->count) {
1146 if (next && arr->count == 0) {
1147 ret = arr->len - start;
1150 if (!next && arr->count == 0) {
1157 ret = find_contig(arr, start, used);
1159 ret = find_rev_contig(arr, start, used);
1161 rte_rwlock_read_unlock(&arr->rwlock);
1165 int __rte_experimental
1166 rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start)
1168 return fbarray_find_contig(arr, start, true, false);
1171 int __rte_experimental
1172 rte_fbarray_find_contig_used(struct rte_fbarray *arr, unsigned int start)
1174 return fbarray_find_contig(arr, start, true, true);
1177 int __rte_experimental
1178 rte_fbarray_find_rev_contig_free(struct rte_fbarray *arr, unsigned int start)
1180 return fbarray_find_contig(arr, start, false, false);
1183 int __rte_experimental
1184 rte_fbarray_find_rev_contig_used(struct rte_fbarray *arr, unsigned int start)
1186 return fbarray_find_contig(arr, start, false, true);
1189 int __rte_experimental
1190 rte_fbarray_find_idx(const struct rte_fbarray *arr, const void *elt)
1196 * no need to synchronize as it doesn't matter if underlying data
1197 * changes - we're doing pointer arithmetic here.
1200 if (arr == NULL || elt == NULL) {
1204 end = RTE_PTR_ADD(arr->data, arr->elt_sz * arr->len);
1205 if (elt < arr->data || elt >= end) {
1210 ret = RTE_PTR_DIFF(elt, arr->data) / arr->elt_sz;
1215 void __rte_experimental
1216 rte_fbarray_dump_metadata(struct rte_fbarray *arr, FILE *f)
1218 struct used_mask *msk;
1221 if (arr == NULL || f == NULL) {
1226 if (fully_validate(arr->name, arr->elt_sz, arr->len)) {
1227 fprintf(f, "Invalid file-backed array\n");
1231 /* prevent array from changing under us */
1232 rte_rwlock_read_lock(&arr->rwlock);
1234 fprintf(f, "File-backed array: %s\n", arr->name);
1235 fprintf(f, "size: %i occupied: %i elt_sz: %i\n",
1236 arr->len, arr->count, arr->elt_sz);
1238 msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
1240 for (i = 0; i < msk->n_masks; i++)
1241 fprintf(f, "msk idx %i: 0x%016" PRIx64 "\n", i, msk->data[i]);
1243 rte_rwlock_read_unlock(&arr->rwlock);