1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2017-2018 Intel Corporation
13 #include <rte_common.h>
15 #include <rte_errno.h>
16 #include <rte_spinlock.h>
17 #include <rte_tailq.h>
19 #include "eal_filesystem.h"
20 #include "eal_private.h"
22 #include "rte_fbarray.h"
24 #define MASK_SHIFT 6ULL
25 #define MASK_ALIGN (1ULL << MASK_SHIFT)
26 #define MASK_LEN_TO_IDX(x) ((x) >> MASK_SHIFT)
27 #define MASK_LEN_TO_MOD(x) ((x) - RTE_ALIGN_FLOOR(x, MASK_ALIGN))
28 #define MASK_GET_IDX(idx, mod) ((idx << MASK_SHIFT) + mod)
31 * This is a mask that is always stored at the end of array, to provide fast
32 * way of finding free/used spots without looping through each element.
41 calc_mask_size(unsigned int len)
43 /* mask must be multiple of MASK_ALIGN, even though length of array
44 * itself may not be aligned on that boundary.
46 len = RTE_ALIGN_CEIL(len, MASK_ALIGN);
47 return sizeof(struct used_mask) +
48 sizeof(uint64_t) * MASK_LEN_TO_IDX(len);
52 calc_data_size(size_t page_sz, unsigned int elt_sz, unsigned int len)
54 size_t data_sz = elt_sz * len;
55 size_t msk_sz = calc_mask_size(len);
56 return RTE_ALIGN_CEIL(data_sz + msk_sz, page_sz);
59 static struct used_mask *
60 get_used_mask(void *data, unsigned int elt_sz, unsigned int len)
62 return (struct used_mask *) RTE_PTR_ADD(data, elt_sz * len);
66 resize_and_map(int fd, void *addr, size_t len)
71 if (ftruncate(fd, len)) {
72 RTE_LOG(ERR, EAL, "Cannot truncate %s\n", path);
73 /* pass errno up the chain */
78 map_addr = mmap(addr, len, PROT_READ | PROT_WRITE,
79 MAP_SHARED | MAP_FIXED, fd, 0);
80 if (map_addr != addr) {
81 RTE_LOG(ERR, EAL, "mmap() failed: %s\n", strerror(errno));
82 /* pass errno up the chain */
90 find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
93 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
95 unsigned int msk_idx, lookahead_idx, first, first_mod;
96 unsigned int last, last_mod;
97 uint64_t last_msk, ignore_msk;
100 * mask only has granularity of MASK_ALIGN, but start may not be aligned
101 * on that boundary, so construct a special mask to exclude anything we
102 * don't want to see to avoid confusing ctz.
104 first = MASK_LEN_TO_IDX(start);
105 first_mod = MASK_LEN_TO_MOD(start);
106 ignore_msk = ~((1ULL << first_mod) - 1);
108 /* array length may not be aligned, so calculate ignore mask for last
111 last = MASK_LEN_TO_IDX(arr->len);
112 last_mod = MASK_LEN_TO_MOD(arr->len);
113 last_msk = ~(-1ULL << last_mod);
115 for (msk_idx = first; msk_idx < msk->n_masks; msk_idx++) {
116 uint64_t cur_msk, lookahead_msk;
117 unsigned int run_start, clz, left;
120 * The process of getting n consecutive bits for arbitrary n is
121 * a bit involved, but here it is in a nutshell:
123 * 1. let n be the number of consecutive bits we're looking for
124 * 2. check if n can fit in one mask, and if so, do n-1
125 * rshift-ands to see if there is an appropriate run inside
127 * 2a. if we found a run, bail out early
128 * 2b. if we didn't find a run, proceed
129 * 3. invert the mask and count leading zeroes (that is, count
130 * how many consecutive set bits we had starting from the
131 * end of current mask) as k
132 * 3a. if k is 0, continue to next mask
133 * 3b. if k is not 0, we have a potential run
134 * 4. to satisfy our requirements, next mask must have n-k
135 * consecutive set bits right at the start, so we will do
136 * (n-k-1) rshift-ands and check if first bit is set.
138 * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until
139 * we either run out of masks, lose the run, or find what we
142 cur_msk = msk->data[msk_idx];
145 /* if we're looking for free spaces, invert the mask */
149 /* combine current ignore mask with last index ignore mask */
151 ignore_msk |= last_msk;
153 /* if we have an ignore mask, ignore once */
155 cur_msk &= ignore_msk;
159 /* if n can fit in within a single mask, do a search */
160 if (n <= MASK_ALIGN) {
161 uint64_t tmp_msk = cur_msk;
163 for (s_idx = 0; s_idx < n - 1; s_idx++)
164 tmp_msk &= tmp_msk >> 1ULL;
165 /* we found what we were looking for */
167 run_start = __builtin_ctzll(tmp_msk);
168 return MASK_GET_IDX(msk_idx, run_start);
173 * we didn't find our run within the mask, or n > MASK_ALIGN,
174 * so we're going for plan B.
177 /* count leading zeroes on inverted mask */
179 clz = sizeof(cur_msk) * 8;
181 clz = __builtin_clzll(~cur_msk);
183 /* if there aren't any runs at the end either, just continue */
187 /* we have a partial run at the end, so try looking ahead */
188 run_start = MASK_ALIGN - clz;
191 for (lookahead_idx = msk_idx + 1; lookahead_idx < msk->n_masks;
193 unsigned int s_idx, need;
194 lookahead_msk = msk->data[lookahead_idx];
196 /* if we're looking for free space, invert the mask */
198 lookahead_msk = ~lookahead_msk;
200 /* figure out how many consecutive bits we need here */
201 need = RTE_MIN(left, MASK_ALIGN);
203 for (s_idx = 0; s_idx < need - 1; s_idx++)
204 lookahead_msk &= lookahead_msk >> 1ULL;
206 /* if first bit is not set, we've lost the run */
207 if ((lookahead_msk & 1) == 0) {
209 * we've scanned this far, so we know there are
210 * no runs in the space we've lookahead-scanned
211 * as well, so skip that on next iteration.
213 ignore_msk = ~((1ULL << need) - 1);
214 msk_idx = lookahead_idx;
220 /* check if we've found what we were looking for */
227 /* we didn't find anything, so continue */
231 return MASK_GET_IDX(msk_idx, run_start);
233 /* we didn't find anything */
234 rte_errno = used ? ENOENT : ENOSPC;
239 find_next(const struct rte_fbarray *arr, unsigned int start, bool used)
241 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
243 unsigned int idx, first, first_mod;
244 unsigned int last, last_mod;
245 uint64_t last_msk, ignore_msk;
248 * mask only has granularity of MASK_ALIGN, but start may not be aligned
249 * on that boundary, so construct a special mask to exclude anything we
250 * don't want to see to avoid confusing ctz.
252 first = MASK_LEN_TO_IDX(start);
253 first_mod = MASK_LEN_TO_MOD(start);
254 ignore_msk = ~((1ULL << first_mod) - 1ULL);
256 /* array length may not be aligned, so calculate ignore mask for last
259 last = MASK_LEN_TO_IDX(arr->len);
260 last_mod = MASK_LEN_TO_MOD(arr->len);
261 last_msk = ~(-(1ULL) << last_mod);
263 for (idx = first; idx < msk->n_masks; idx++) {
264 uint64_t cur = msk->data[idx];
267 /* if we're looking for free entries, invert mask */
274 /* ignore everything before start on first iteration */
278 /* check if we have any entries */
283 * find first set bit - that will correspond to whatever it is
284 * that we're looking for.
286 found = __builtin_ctzll(cur);
287 return MASK_GET_IDX(idx, found);
289 /* we didn't find anything */
290 rte_errno = used ? ENOENT : ENOSPC;
295 find_contig(const struct rte_fbarray *arr, unsigned int start, bool used)
297 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
299 unsigned int idx, first, first_mod;
300 unsigned int last, last_mod;
302 unsigned int need_len, result = 0;
304 /* array length may not be aligned, so calculate ignore mask for last
307 last = MASK_LEN_TO_IDX(arr->len);
308 last_mod = MASK_LEN_TO_MOD(arr->len);
309 last_msk = ~(-(1ULL) << last_mod);
311 first = MASK_LEN_TO_IDX(start);
312 first_mod = MASK_LEN_TO_MOD(start);
313 for (idx = first; idx < msk->n_masks; idx++, result += need_len) {
314 uint64_t cur = msk->data[idx];
315 unsigned int run_len;
317 need_len = MASK_ALIGN;
319 /* if we're looking for free entries, invert mask */
323 /* if this is last mask, ignore everything after last bit */
327 /* ignore everything before start on first iteration */
330 /* at the start, we don't need the full mask len */
331 need_len -= first_mod;
334 /* we will be looking for zeroes, so invert the mask */
337 /* if mask is zero, we have a complete run */
342 * see if current run ends before mask end.
344 run_len = __builtin_ctzll(cur);
346 /* add however many zeroes we've had in the last run and quit */
347 if (run_len < need_len) {
356 find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
359 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
361 unsigned int msk_idx, lookbehind_idx, first, first_mod;
365 * mask only has granularity of MASK_ALIGN, but start may not be aligned
366 * on that boundary, so construct a special mask to exclude anything we
367 * don't want to see to avoid confusing ctz.
369 first = MASK_LEN_TO_IDX(start);
370 first_mod = MASK_LEN_TO_MOD(start);
371 /* we're going backwards, so mask must start from the top */
372 ignore_msk = first_mod == MASK_ALIGN - 1 ?
373 -1ULL : /* prevent overflow */
374 ~(-1ULL << (first_mod + 1));
376 /* go backwards, include zero */
379 uint64_t cur_msk, lookbehind_msk;
380 unsigned int run_start, run_end, ctz, left;
383 * The process of getting n consecutive bits from the top for
384 * arbitrary n is a bit involved, but here it is in a nutshell:
386 * 1. let n be the number of consecutive bits we're looking for
387 * 2. check if n can fit in one mask, and if so, do n-1
388 * lshift-ands to see if there is an appropriate run inside
390 * 2a. if we found a run, bail out early
391 * 2b. if we didn't find a run, proceed
392 * 3. invert the mask and count trailing zeroes (that is, count
393 * how many consecutive set bits we had starting from the
394 * start of current mask) as k
395 * 3a. if k is 0, continue to next mask
396 * 3b. if k is not 0, we have a potential run
397 * 4. to satisfy our requirements, next mask must have n-k
398 * consecutive set bits at the end, so we will do (n-k-1)
399 * lshift-ands and check if last bit is set.
401 * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until
402 * we either run out of masks, lose the run, or find what we
405 cur_msk = msk->data[msk_idx];
408 /* if we're looking for free spaces, invert the mask */
412 /* if we have an ignore mask, ignore once */
414 cur_msk &= ignore_msk;
418 /* if n can fit in within a single mask, do a search */
419 if (n <= MASK_ALIGN) {
420 uint64_t tmp_msk = cur_msk;
422 for (s_idx = 0; s_idx < n - 1; s_idx++)
423 tmp_msk &= tmp_msk << 1ULL;
424 /* we found what we were looking for */
426 /* clz will give us offset from end of mask, and
427 * we only get the end of our run, not start,
428 * so adjust result to point to where start
431 run_start = MASK_ALIGN -
432 __builtin_clzll(tmp_msk) - n;
433 return MASK_GET_IDX(msk_idx, run_start);
438 * we didn't find our run within the mask, or n > MASK_ALIGN,
439 * so we're going for plan B.
442 /* count trailing zeroes on inverted mask */
444 ctz = sizeof(cur_msk) * 8;
446 ctz = __builtin_ctzll(~cur_msk);
448 /* if there aren't any runs at the start either, just
454 /* we have a partial run at the start, so try looking behind */
455 run_end = MASK_GET_IDX(msk_idx, ctz);
458 /* go backwards, include zero */
459 lookbehind_idx = msk_idx - 1;
461 /* we can't lookbehind as we've run out of masks, so stop */
466 const uint64_t last_bit = 1ULL << (MASK_ALIGN - 1);
467 unsigned int s_idx, need;
469 lookbehind_msk = msk->data[lookbehind_idx];
471 /* if we're looking for free space, invert the mask */
473 lookbehind_msk = ~lookbehind_msk;
475 /* figure out how many consecutive bits we need here */
476 need = RTE_MIN(left, MASK_ALIGN);
478 for (s_idx = 0; s_idx < need - 1; s_idx++)
479 lookbehind_msk &= lookbehind_msk << 1ULL;
481 /* if last bit is not set, we've lost the run */
482 if ((lookbehind_msk & last_bit) == 0) {
484 * we've scanned this far, so we know there are
485 * no runs in the space we've lookbehind-scanned
486 * as well, so skip that on next iteration.
488 ignore_msk = -1ULL << need;
489 msk_idx = lookbehind_idx;
495 /* check if we've found what we were looking for */
500 } while ((lookbehind_idx--) != 0); /* decrement after check to
504 /* we didn't find anything, so continue */
508 /* we've found what we were looking for, but we only know where
509 * the run ended, so calculate start position.
512 } while (msk_idx-- != 0); /* decrement after check to include zero */
513 /* we didn't find anything */
514 rte_errno = used ? ENOENT : ENOSPC;
519 find_prev(const struct rte_fbarray *arr, unsigned int start, bool used)
521 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
523 unsigned int idx, first, first_mod;
527 * mask only has granularity of MASK_ALIGN, but start may not be aligned
528 * on that boundary, so construct a special mask to exclude anything we
529 * don't want to see to avoid confusing clz.
531 first = MASK_LEN_TO_IDX(start);
532 first_mod = MASK_LEN_TO_MOD(start);
533 /* we're going backwards, so mask must start from the top */
534 ignore_msk = first_mod == MASK_ALIGN - 1 ?
535 -1ULL : /* prevent overflow */
536 ~(-1ULL << (first_mod + 1));
538 /* go backwards, include zero */
541 uint64_t cur = msk->data[idx];
544 /* if we're looking for free entries, invert mask */
548 /* ignore everything before start on first iteration */
552 /* check if we have any entries */
557 * find last set bit - that will correspond to whatever it is
558 * that we're looking for. we're counting trailing zeroes, thus
559 * the value we get is counted from end of mask, so calculate
560 * position from start of mask.
562 found = MASK_ALIGN - __builtin_clzll(cur) - 1;
564 return MASK_GET_IDX(idx, found);
565 } while (idx-- != 0); /* decrement after check to include zero*/
567 /* we didn't find anything */
568 rte_errno = used ? ENOENT : ENOSPC;
573 find_rev_contig(const struct rte_fbarray *arr, unsigned int start, bool used)
575 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
577 unsigned int idx, first, first_mod;
578 unsigned int need_len, result = 0;
580 first = MASK_LEN_TO_IDX(start);
581 first_mod = MASK_LEN_TO_MOD(start);
583 /* go backwards, include zero */
586 uint64_t cur = msk->data[idx];
587 unsigned int run_len;
589 need_len = MASK_ALIGN;
591 /* if we're looking for free entries, invert mask */
595 /* ignore everything after start on first iteration */
597 unsigned int end_len = MASK_ALIGN - first_mod - 1;
599 /* at the start, we don't need the full mask len */
603 /* we will be looking for zeroes, so invert the mask */
606 /* if mask is zero, we have a complete run */
611 * see where run ends, starting from the end.
613 run_len = __builtin_clzll(cur);
615 /* add however many zeroes we've had in the last run and quit */
616 if (run_len < need_len) {
622 } while (idx-- != 0); /* decrement after check to include zero */
627 set_used(struct rte_fbarray *arr, unsigned int idx, bool used)
629 struct used_mask *msk;
630 uint64_t msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);
631 unsigned int msk_idx = MASK_LEN_TO_IDX(idx);
635 if (arr == NULL || idx >= arr->len) {
639 msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
642 /* prevent array from changing under us */
643 rte_rwlock_write_lock(&arr->rwlock);
645 already_used = (msk->data[msk_idx] & msk_bit) != 0;
647 /* nothing to be done */
648 if (used == already_used)
652 msk->data[msk_idx] |= msk_bit;
655 msk->data[msk_idx] &= ~msk_bit;
659 rte_rwlock_write_unlock(&arr->rwlock);
665 fully_validate(const char *name, unsigned int elt_sz, unsigned int len)
667 if (name == NULL || elt_sz == 0 || len == 0 || len > INT_MAX) {
672 if (strnlen(name, RTE_FBARRAY_NAME_LEN) == RTE_FBARRAY_NAME_LEN) {
673 rte_errno = ENAMETOOLONG;
679 int __rte_experimental
680 rte_fbarray_init(struct rte_fbarray *arr, const char *name, unsigned int len,
683 size_t page_sz, mmap_len;
685 struct used_mask *msk;
694 if (fully_validate(name, elt_sz, len))
697 page_sz = sysconf(_SC_PAGESIZE);
698 if (page_sz == (size_t)-1)
701 /* calculate our memory limits */
702 mmap_len = calc_data_size(page_sz, elt_sz, len);
704 data = eal_get_virtual_area(NULL, &mmap_len, page_sz, 0, 0);
708 if (internal_config.no_shconf) {
709 /* remap virtual area as writable */
710 void *new_data = mmap(data, mmap_len, PROT_READ | PROT_WRITE,
711 MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
712 if (new_data == MAP_FAILED) {
713 RTE_LOG(DEBUG, EAL, "%s(): couldn't remap anonymous memory: %s\n",
714 __func__, strerror(errno));
718 eal_get_fbarray_path(path, sizeof(path), name);
721 * Each fbarray is unique to process namespace, i.e. the
722 * filename depends on process prefix. Try to take out a lock
723 * and see if we succeed. If we don't, someone else is using it
726 fd = open(path, O_CREAT | O_RDWR, 0600);
728 RTE_LOG(DEBUG, EAL, "%s(): couldn't open %s: %s\n",
729 __func__, path, strerror(errno));
732 } else if (flock(fd, LOCK_EX | LOCK_NB)) {
733 RTE_LOG(DEBUG, EAL, "%s(): couldn't lock %s: %s\n",
734 __func__, path, strerror(errno));
739 /* take out a non-exclusive lock, so that other processes could
740 * still attach to it, but no other process could reinitialize
743 if (flock(fd, LOCK_SH | LOCK_NB)) {
748 if (resize_and_map(fd, data, mmap_len))
751 /* we've mmap'ed the file, we can now close the fd */
755 /* initialize the data */
756 memset(data, 0, mmap_len);
758 /* populate data structure */
759 strlcpy(arr->name, name, sizeof(arr->name));
762 arr->elt_sz = elt_sz;
765 msk = get_used_mask(data, elt_sz, len);
766 msk->n_masks = MASK_LEN_TO_IDX(RTE_ALIGN_CEIL(len, MASK_ALIGN));
768 rte_rwlock_init(&arr->rwlock);
773 munmap(data, mmap_len);
779 int __rte_experimental
780 rte_fbarray_attach(struct rte_fbarray *arr)
782 size_t page_sz, mmap_len;
793 * we don't need to synchronize attach as two values we need (element
794 * size and array length) are constant for the duration of life of
795 * the array, so the parts we care about will not race.
798 if (fully_validate(arr->name, arr->elt_sz, arr->len))
801 page_sz = sysconf(_SC_PAGESIZE);
802 if (page_sz == (size_t)-1)
805 mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
807 data = eal_get_virtual_area(arr->data, &mmap_len, page_sz, 0, 0);
811 eal_get_fbarray_path(path, sizeof(path), arr->name);
813 fd = open(path, O_RDWR);
819 /* lock the file, to let others know we're using it */
820 if (flock(fd, LOCK_SH | LOCK_NB)) {
825 if (resize_and_map(fd, data, mmap_len))
835 munmap(data, mmap_len);
841 int __rte_experimental
842 rte_fbarray_detach(struct rte_fbarray *arr)
850 * we don't need to synchronize detach as two values we need (element
851 * size and total capacity) are constant for the duration of life of
852 * the array, so the parts we care about will not race. if the user is
853 * detaching while doing something else in the same process, we can't
854 * really do anything about it, things will blow up either way.
857 size_t page_sz = sysconf(_SC_PAGESIZE);
859 if (page_sz == (size_t)-1)
862 /* this may already be unmapped (e.g. repeated call from previously
863 * failed destroy(), but this is on user, we can't (easily) know if this
866 munmap(arr->data, calc_data_size(page_sz, arr->elt_sz, arr->len));
871 int __rte_experimental
872 rte_fbarray_destroy(struct rte_fbarray *arr)
877 ret = rte_fbarray_detach(arr);
881 /* with no shconf, there were never any files to begin with */
882 if (internal_config.no_shconf)
885 /* try deleting the file */
886 eal_get_fbarray_path(path, sizeof(path), arr->name);
888 fd = open(path, O_RDONLY);
890 RTE_LOG(ERR, EAL, "Could not open fbarray file: %s\n",
894 if (flock(fd, LOCK_EX | LOCK_NB)) {
895 RTE_LOG(DEBUG, EAL, "Cannot destroy fbarray - another process is using it\n");
901 memset(arr, 0, sizeof(*arr));
908 void * __rte_experimental
909 rte_fbarray_get(const struct rte_fbarray *arr, unsigned int idx)
917 if (idx >= arr->len) {
922 ret = RTE_PTR_ADD(arr->data, idx * arr->elt_sz);
927 int __rte_experimental
928 rte_fbarray_set_used(struct rte_fbarray *arr, unsigned int idx)
930 return set_used(arr, idx, true);
933 int __rte_experimental
934 rte_fbarray_set_free(struct rte_fbarray *arr, unsigned int idx)
936 return set_used(arr, idx, false);
939 int __rte_experimental
940 rte_fbarray_is_used(struct rte_fbarray *arr, unsigned int idx)
942 struct used_mask *msk;
947 if (arr == NULL || idx >= arr->len) {
952 /* prevent array from changing under us */
953 rte_rwlock_read_lock(&arr->rwlock);
955 msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
956 msk_idx = MASK_LEN_TO_IDX(idx);
957 msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);
959 ret = (msk->data[msk_idx] & msk_bit) != 0;
961 rte_rwlock_read_unlock(&arr->rwlock);
967 fbarray_find(struct rte_fbarray *arr, unsigned int start, bool next, bool used)
971 if (arr == NULL || start >= arr->len) {
976 /* prevent array from changing under us */
977 rte_rwlock_read_lock(&arr->rwlock);
979 /* cheap checks to prevent doing useless work */
981 if (arr->len == arr->count) {
985 if (arr->count == 0) {
990 if (arr->count == 0) {
994 if (arr->len == arr->count) {
1000 ret = find_next(arr, start, used);
1002 ret = find_prev(arr, start, used);
1004 rte_rwlock_read_unlock(&arr->rwlock);
1008 int __rte_experimental
1009 rte_fbarray_find_next_free(struct rte_fbarray *arr, unsigned int start)
1011 return fbarray_find(arr, start, true, false);
1014 int __rte_experimental
1015 rte_fbarray_find_next_used(struct rte_fbarray *arr, unsigned int start)
1017 return fbarray_find(arr, start, true, true);
1020 int __rte_experimental
1021 rte_fbarray_find_prev_free(struct rte_fbarray *arr, unsigned int start)
1023 return fbarray_find(arr, start, false, false);
1026 int __rte_experimental
1027 rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start)
1029 return fbarray_find(arr, start, false, true);
1033 fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n,
1034 bool next, bool used)
1038 if (arr == NULL || start >= arr->len || n > arr->len || n == 0) {
1042 if (next && (arr->len - start) < n) {
1043 rte_errno = used ? ENOENT : ENOSPC;
1046 if (!next && start < (n - 1)) {
1047 rte_errno = used ? ENOENT : ENOSPC;
1051 /* prevent array from changing under us */
1052 rte_rwlock_read_lock(&arr->rwlock);
1054 /* cheap checks to prevent doing useless work */
1056 if (arr->len == arr->count || arr->len - arr->count < n) {
1060 if (arr->count == 0) {
1061 ret = next ? start : start - n + 1;
1065 if (arr->count < n) {
1069 if (arr->count == arr->len) {
1070 ret = next ? start : start - n + 1;
1076 ret = find_next_n(arr, start, n, used);
1078 ret = find_prev_n(arr, start, n, used);
1080 rte_rwlock_read_unlock(&arr->rwlock);
1084 int __rte_experimental
1085 rte_fbarray_find_next_n_free(struct rte_fbarray *arr, unsigned int start,
1088 return fbarray_find_n(arr, start, n, true, false);
1091 int __rte_experimental
1092 rte_fbarray_find_next_n_used(struct rte_fbarray *arr, unsigned int start,
1095 return fbarray_find_n(arr, start, n, true, true);
1098 int __rte_experimental
1099 rte_fbarray_find_prev_n_free(struct rte_fbarray *arr, unsigned int start,
1102 return fbarray_find_n(arr, start, n, false, false);
1105 int __rte_experimental
1106 rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start,
1109 return fbarray_find_n(arr, start, n, false, true);
1113 fbarray_find_contig(struct rte_fbarray *arr, unsigned int start, bool next,
1118 if (arr == NULL || start >= arr->len) {
1123 /* prevent array from changing under us */
1124 rte_rwlock_read_lock(&arr->rwlock);
1126 /* cheap checks to prevent doing useless work */
1128 if (arr->count == 0) {
1132 if (next && arr->count == arr->len) {
1133 ret = arr->len - start;
1136 if (!next && arr->count == arr->len) {
1141 if (arr->len == arr->count) {
1145 if (next && arr->count == 0) {
1146 ret = arr->len - start;
1149 if (!next && arr->count == 0) {
1156 ret = find_contig(arr, start, used);
1158 ret = find_rev_contig(arr, start, used);
1160 rte_rwlock_read_unlock(&arr->rwlock);
1164 int __rte_experimental
1165 rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start)
1167 return fbarray_find_contig(arr, start, true, false);
1170 int __rte_experimental
1171 rte_fbarray_find_contig_used(struct rte_fbarray *arr, unsigned int start)
1173 return fbarray_find_contig(arr, start, true, true);
1176 int __rte_experimental
1177 rte_fbarray_find_rev_contig_free(struct rte_fbarray *arr, unsigned int start)
1179 return fbarray_find_contig(arr, start, false, false);
1182 int __rte_experimental
1183 rte_fbarray_find_rev_contig_used(struct rte_fbarray *arr, unsigned int start)
1185 return fbarray_find_contig(arr, start, false, true);
1188 int __rte_experimental
1189 rte_fbarray_find_idx(const struct rte_fbarray *arr, const void *elt)
1195 * no need to synchronize as it doesn't matter if underlying data
1196 * changes - we're doing pointer arithmetic here.
1199 if (arr == NULL || elt == NULL) {
1203 end = RTE_PTR_ADD(arr->data, arr->elt_sz * arr->len);
1204 if (elt < arr->data || elt >= end) {
1209 ret = RTE_PTR_DIFF(elt, arr->data) / arr->elt_sz;
1214 void __rte_experimental
1215 rte_fbarray_dump_metadata(struct rte_fbarray *arr, FILE *f)
1217 struct used_mask *msk;
1220 if (arr == NULL || f == NULL) {
1225 if (fully_validate(arr->name, arr->elt_sz, arr->len)) {
1226 fprintf(f, "Invalid file-backed array\n");
1230 /* prevent array from changing under us */
1231 rte_rwlock_read_lock(&arr->rwlock);
1233 fprintf(f, "File-backed array: %s\n", arr->name);
1234 fprintf(f, "size: %i occupied: %i elt_sz: %i\n",
1235 arr->len, arr->count, arr->elt_sz);
1237 msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
1239 for (i = 0; i < msk->n_masks; i++)
1240 fprintf(f, "msk idx %i: 0x%016" PRIx64 "\n", i, msk->data[i]);
1242 rte_rwlock_read_unlock(&arr->rwlock);