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 * We use this to keep track of created/attached memory areas to prevent user
33 * errors in API usage.
36 TAILQ_ENTRY(mem_area) next;
41 TAILQ_HEAD(mem_area_head, mem_area);
42 /* local per-process tailq */
43 static struct mem_area_head mem_area_tailq =
44 TAILQ_HEAD_INITIALIZER(mem_area_tailq);
45 static rte_spinlock_t mem_area_lock = RTE_SPINLOCK_INITIALIZER;
48 * This is a mask that is always stored at the end of array, to provide fast
49 * way of finding free/used spots without looping through each element.
58 calc_mask_size(unsigned int len)
60 /* mask must be multiple of MASK_ALIGN, even though length of array
61 * itself may not be aligned on that boundary.
63 len = RTE_ALIGN_CEIL(len, MASK_ALIGN);
64 return sizeof(struct used_mask) +
65 sizeof(uint64_t) * MASK_LEN_TO_IDX(len);
69 calc_data_size(size_t page_sz, unsigned int elt_sz, unsigned int len)
71 size_t data_sz = elt_sz * len;
72 size_t msk_sz = calc_mask_size(len);
73 return RTE_ALIGN_CEIL(data_sz + msk_sz, page_sz);
76 static struct used_mask *
77 get_used_mask(void *data, unsigned int elt_sz, unsigned int len)
79 return (struct used_mask *) RTE_PTR_ADD(data, elt_sz * len);
83 resize_and_map(int fd, void *addr, size_t len)
88 if (eal_file_truncate(fd, len)) {
89 RTE_LOG(ERR, EAL, "Cannot truncate %s\n", path);
93 map_addr = mmap(addr, len, PROT_READ | PROT_WRITE,
94 MAP_SHARED | MAP_FIXED, fd, 0);
95 if (map_addr != addr) {
96 RTE_LOG(ERR, EAL, "mmap() failed: %s\n", strerror(errno));
97 /* pass errno up the chain */
105 overlap(const struct mem_area *ma, const void *start, size_t len)
107 const void *end = RTE_PTR_ADD(start, len);
108 const void *ma_start = ma->addr;
109 const void *ma_end = RTE_PTR_ADD(ma->addr, ma->len);
112 if (start >= ma_start && start < ma_end)
115 if (end >= ma_start && end < ma_end)
121 find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
124 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
126 unsigned int msk_idx, lookahead_idx, first, first_mod;
127 unsigned int last, last_mod;
128 uint64_t last_msk, ignore_msk;
131 * mask only has granularity of MASK_ALIGN, but start may not be aligned
132 * on that boundary, so construct a special mask to exclude anything we
133 * don't want to see to avoid confusing ctz.
135 first = MASK_LEN_TO_IDX(start);
136 first_mod = MASK_LEN_TO_MOD(start);
137 ignore_msk = ~((1ULL << first_mod) - 1);
139 /* array length may not be aligned, so calculate ignore mask for last
142 last = MASK_LEN_TO_IDX(arr->len);
143 last_mod = MASK_LEN_TO_MOD(arr->len);
144 last_msk = ~(-1ULL << last_mod);
146 for (msk_idx = first; msk_idx < msk->n_masks; msk_idx++) {
147 uint64_t cur_msk, lookahead_msk;
148 unsigned int run_start, clz, left;
151 * The process of getting n consecutive bits for arbitrary n is
152 * a bit involved, but here it is in a nutshell:
154 * 1. let n be the number of consecutive bits we're looking for
155 * 2. check if n can fit in one mask, and if so, do n-1
156 * rshift-ands to see if there is an appropriate run inside
158 * 2a. if we found a run, bail out early
159 * 2b. if we didn't find a run, proceed
160 * 3. invert the mask and count leading zeroes (that is, count
161 * how many consecutive set bits we had starting from the
162 * end of current mask) as k
163 * 3a. if k is 0, continue to next mask
164 * 3b. if k is not 0, we have a potential run
165 * 4. to satisfy our requirements, next mask must have n-k
166 * consecutive set bits right at the start, so we will do
167 * (n-k-1) rshift-ands and check if first bit is set.
169 * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until
170 * we either run out of masks, lose the run, or find what we
173 cur_msk = msk->data[msk_idx];
176 /* if we're looking for free spaces, invert the mask */
180 /* combine current ignore mask with last index ignore mask */
182 ignore_msk |= last_msk;
184 /* if we have an ignore mask, ignore once */
186 cur_msk &= ignore_msk;
190 /* if n can fit in within a single mask, do a search */
191 if (n <= MASK_ALIGN) {
192 uint64_t tmp_msk = cur_msk;
194 for (s_idx = 0; s_idx < n - 1; s_idx++)
195 tmp_msk &= tmp_msk >> 1ULL;
196 /* we found what we were looking for */
198 run_start = __builtin_ctzll(tmp_msk);
199 return MASK_GET_IDX(msk_idx, run_start);
204 * we didn't find our run within the mask, or n > MASK_ALIGN,
205 * so we're going for plan B.
208 /* count leading zeroes on inverted mask */
210 clz = sizeof(cur_msk) * 8;
212 clz = __builtin_clzll(~cur_msk);
214 /* if there aren't any runs at the end either, just continue */
218 /* we have a partial run at the end, so try looking ahead */
219 run_start = MASK_ALIGN - clz;
222 for (lookahead_idx = msk_idx + 1; lookahead_idx < msk->n_masks;
224 unsigned int s_idx, need;
225 lookahead_msk = msk->data[lookahead_idx];
227 /* if we're looking for free space, invert the mask */
229 lookahead_msk = ~lookahead_msk;
231 /* figure out how many consecutive bits we need here */
232 need = RTE_MIN(left, MASK_ALIGN);
234 for (s_idx = 0; s_idx < need - 1; s_idx++)
235 lookahead_msk &= lookahead_msk >> 1ULL;
237 /* if first bit is not set, we've lost the run */
238 if ((lookahead_msk & 1) == 0) {
240 * we've scanned this far, so we know there are
241 * no runs in the space we've lookahead-scanned
242 * as well, so skip that on next iteration.
244 ignore_msk = ~((1ULL << need) - 1);
245 msk_idx = lookahead_idx;
251 /* check if we've found what we were looking for */
258 /* we didn't find anything, so continue */
262 return MASK_GET_IDX(msk_idx, run_start);
264 /* we didn't find anything */
265 rte_errno = used ? ENOENT : ENOSPC;
270 find_next(const struct rte_fbarray *arr, unsigned int start, bool used)
272 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
274 unsigned int idx, first, first_mod;
275 unsigned int last, last_mod;
276 uint64_t last_msk, ignore_msk;
279 * mask only has granularity of MASK_ALIGN, but start may not be aligned
280 * on that boundary, so construct a special mask to exclude anything we
281 * don't want to see to avoid confusing ctz.
283 first = MASK_LEN_TO_IDX(start);
284 first_mod = MASK_LEN_TO_MOD(start);
285 ignore_msk = ~((1ULL << first_mod) - 1ULL);
287 /* array length may not be aligned, so calculate ignore mask for last
290 last = MASK_LEN_TO_IDX(arr->len);
291 last_mod = MASK_LEN_TO_MOD(arr->len);
292 last_msk = ~(-(1ULL) << last_mod);
294 for (idx = first; idx < msk->n_masks; idx++) {
295 uint64_t cur = msk->data[idx];
298 /* if we're looking for free entries, invert mask */
305 /* ignore everything before start on first iteration */
309 /* check if we have any entries */
314 * find first set bit - that will correspond to whatever it is
315 * that we're looking for.
317 found = __builtin_ctzll(cur);
318 return MASK_GET_IDX(idx, found);
320 /* we didn't find anything */
321 rte_errno = used ? ENOENT : ENOSPC;
326 find_contig(const struct rte_fbarray *arr, unsigned int start, bool used)
328 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
330 unsigned int idx, first, first_mod;
331 unsigned int last, last_mod;
333 unsigned int need_len, result = 0;
335 /* array length may not be aligned, so calculate ignore mask for last
338 last = MASK_LEN_TO_IDX(arr->len);
339 last_mod = MASK_LEN_TO_MOD(arr->len);
340 last_msk = ~(-(1ULL) << last_mod);
342 first = MASK_LEN_TO_IDX(start);
343 first_mod = MASK_LEN_TO_MOD(start);
344 for (idx = first; idx < msk->n_masks; idx++, result += need_len) {
345 uint64_t cur = msk->data[idx];
346 unsigned int run_len;
348 need_len = MASK_ALIGN;
350 /* if we're looking for free entries, invert mask */
354 /* if this is last mask, ignore everything after last bit */
358 /* ignore everything before start on first iteration */
361 /* at the start, we don't need the full mask len */
362 need_len -= first_mod;
365 /* we will be looking for zeroes, so invert the mask */
368 /* if mask is zero, we have a complete run */
373 * see if current run ends before mask end.
375 run_len = __builtin_ctzll(cur);
377 /* add however many zeroes we've had in the last run and quit */
378 if (run_len < need_len) {
387 find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
390 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
392 unsigned int msk_idx, lookbehind_idx, first, first_mod;
396 * mask only has granularity of MASK_ALIGN, but start may not be aligned
397 * on that boundary, so construct a special mask to exclude anything we
398 * don't want to see to avoid confusing ctz.
400 first = MASK_LEN_TO_IDX(start);
401 first_mod = MASK_LEN_TO_MOD(start);
402 /* we're going backwards, so mask must start from the top */
403 ignore_msk = first_mod == MASK_ALIGN - 1 ?
404 -1ULL : /* prevent overflow */
405 ~(-1ULL << (first_mod + 1));
407 /* go backwards, include zero */
410 uint64_t cur_msk, lookbehind_msk;
411 unsigned int run_start, run_end, ctz, left;
414 * The process of getting n consecutive bits from the top for
415 * arbitrary n is a bit involved, but here it is in a nutshell:
417 * 1. let n be the number of consecutive bits we're looking for
418 * 2. check if n can fit in one mask, and if so, do n-1
419 * lshift-ands to see if there is an appropriate run inside
421 * 2a. if we found a run, bail out early
422 * 2b. if we didn't find a run, proceed
423 * 3. invert the mask and count trailing zeroes (that is, count
424 * how many consecutive set bits we had starting from the
425 * start of current mask) as k
426 * 3a. if k is 0, continue to next mask
427 * 3b. if k is not 0, we have a potential run
428 * 4. to satisfy our requirements, next mask must have n-k
429 * consecutive set bits at the end, so we will do (n-k-1)
430 * lshift-ands and check if last bit is set.
432 * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until
433 * we either run out of masks, lose the run, or find what we
436 cur_msk = msk->data[msk_idx];
439 /* if we're looking for free spaces, invert the mask */
443 /* if we have an ignore mask, ignore once */
445 cur_msk &= ignore_msk;
449 /* if n can fit in within a single mask, do a search */
450 if (n <= MASK_ALIGN) {
451 uint64_t tmp_msk = cur_msk;
453 for (s_idx = 0; s_idx < n - 1; s_idx++)
454 tmp_msk &= tmp_msk << 1ULL;
455 /* we found what we were looking for */
457 /* clz will give us offset from end of mask, and
458 * we only get the end of our run, not start,
459 * so adjust result to point to where start
462 run_start = MASK_ALIGN -
463 __builtin_clzll(tmp_msk) - n;
464 return MASK_GET_IDX(msk_idx, run_start);
469 * we didn't find our run within the mask, or n > MASK_ALIGN,
470 * so we're going for plan B.
473 /* count trailing zeroes on inverted mask */
475 ctz = sizeof(cur_msk) * 8;
477 ctz = __builtin_ctzll(~cur_msk);
479 /* if there aren't any runs at the start either, just
485 /* we have a partial run at the start, so try looking behind */
486 run_end = MASK_GET_IDX(msk_idx, ctz);
489 /* go backwards, include zero */
490 lookbehind_idx = msk_idx - 1;
492 /* we can't lookbehind as we've run out of masks, so stop */
497 const uint64_t last_bit = 1ULL << (MASK_ALIGN - 1);
498 unsigned int s_idx, need;
500 lookbehind_msk = msk->data[lookbehind_idx];
502 /* if we're looking for free space, invert the mask */
504 lookbehind_msk = ~lookbehind_msk;
506 /* figure out how many consecutive bits we need here */
507 need = RTE_MIN(left, MASK_ALIGN);
509 for (s_idx = 0; s_idx < need - 1; s_idx++)
510 lookbehind_msk &= lookbehind_msk << 1ULL;
512 /* if last bit is not set, we've lost the run */
513 if ((lookbehind_msk & last_bit) == 0) {
515 * we've scanned this far, so we know there are
516 * no runs in the space we've lookbehind-scanned
517 * as well, so skip that on next iteration.
519 ignore_msk = -1ULL << need;
520 msk_idx = lookbehind_idx;
526 /* check if we've found what we were looking for */
531 } while ((lookbehind_idx--) != 0); /* decrement after check to
535 /* we didn't find anything, so continue */
539 /* we've found what we were looking for, but we only know where
540 * the run ended, so calculate start position.
543 } while (msk_idx-- != 0); /* decrement after check to include zero */
544 /* we didn't find anything */
545 rte_errno = used ? ENOENT : ENOSPC;
550 find_prev(const struct rte_fbarray *arr, unsigned int start, bool used)
552 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
554 unsigned int idx, first, first_mod;
558 * mask only has granularity of MASK_ALIGN, but start may not be aligned
559 * on that boundary, so construct a special mask to exclude anything we
560 * don't want to see to avoid confusing clz.
562 first = MASK_LEN_TO_IDX(start);
563 first_mod = MASK_LEN_TO_MOD(start);
564 /* we're going backwards, so mask must start from the top */
565 ignore_msk = first_mod == MASK_ALIGN - 1 ?
566 -1ULL : /* prevent overflow */
567 ~(-1ULL << (first_mod + 1));
569 /* go backwards, include zero */
572 uint64_t cur = msk->data[idx];
575 /* if we're looking for free entries, invert mask */
579 /* ignore everything before start on first iteration */
583 /* check if we have any entries */
588 * find last set bit - that will correspond to whatever it is
589 * that we're looking for. we're counting trailing zeroes, thus
590 * the value we get is counted from end of mask, so calculate
591 * position from start of mask.
593 found = MASK_ALIGN - __builtin_clzll(cur) - 1;
595 return MASK_GET_IDX(idx, found);
596 } while (idx-- != 0); /* decrement after check to include zero*/
598 /* we didn't find anything */
599 rte_errno = used ? ENOENT : ENOSPC;
604 find_rev_contig(const struct rte_fbarray *arr, unsigned int start, bool used)
606 const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
608 unsigned int idx, first, first_mod;
609 unsigned int need_len, result = 0;
611 first = MASK_LEN_TO_IDX(start);
612 first_mod = MASK_LEN_TO_MOD(start);
614 /* go backwards, include zero */
617 uint64_t cur = msk->data[idx];
618 unsigned int run_len;
620 need_len = MASK_ALIGN;
622 /* if we're looking for free entries, invert mask */
626 /* ignore everything after start on first iteration */
628 unsigned int end_len = MASK_ALIGN - first_mod - 1;
630 /* at the start, we don't need the full mask len */
634 /* we will be looking for zeroes, so invert the mask */
637 /* if mask is zero, we have a complete run */
642 * see where run ends, starting from the end.
644 run_len = __builtin_clzll(cur);
646 /* add however many zeroes we've had in the last run and quit */
647 if (run_len < need_len) {
653 } while (idx-- != 0); /* decrement after check to include zero */
658 set_used(struct rte_fbarray *arr, unsigned int idx, bool used)
660 struct used_mask *msk;
661 uint64_t msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);
662 unsigned int msk_idx = MASK_LEN_TO_IDX(idx);
666 if (arr == NULL || idx >= arr->len) {
670 msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
673 /* prevent array from changing under us */
674 rte_rwlock_write_lock(&arr->rwlock);
676 already_used = (msk->data[msk_idx] & msk_bit) != 0;
678 /* nothing to be done */
679 if (used == already_used)
683 msk->data[msk_idx] |= msk_bit;
686 msk->data[msk_idx] &= ~msk_bit;
690 rte_rwlock_write_unlock(&arr->rwlock);
696 fully_validate(const char *name, unsigned int elt_sz, unsigned int len)
698 if (name == NULL || elt_sz == 0 || len == 0 || len > INT_MAX) {
703 if (strnlen(name, RTE_FBARRAY_NAME_LEN) == RTE_FBARRAY_NAME_LEN) {
704 rte_errno = ENAMETOOLONG;
711 rte_fbarray_init(struct rte_fbarray *arr, const char *name, unsigned int len,
714 size_t page_sz, mmap_len;
716 struct used_mask *msk;
717 struct mem_area *ma = NULL;
726 if (fully_validate(name, elt_sz, len))
729 /* allocate mem area before doing anything */
730 ma = malloc(sizeof(*ma));
736 page_sz = sysconf(_SC_PAGESIZE);
737 if (page_sz == (size_t)-1) {
742 /* calculate our memory limits */
743 mmap_len = calc_data_size(page_sz, elt_sz, len);
745 data = eal_get_virtual_area(NULL, &mmap_len, page_sz, 0, 0);
751 rte_spinlock_lock(&mem_area_lock);
755 if (internal_config.no_shconf) {
756 /* remap virtual area as writable */
757 void *new_data = mmap(data, mmap_len, PROT_READ | PROT_WRITE,
758 MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, fd, 0);
759 if (new_data == MAP_FAILED) {
760 RTE_LOG(DEBUG, EAL, "%s(): couldn't remap anonymous memory: %s\n",
761 __func__, strerror(errno));
765 eal_get_fbarray_path(path, sizeof(path), name);
768 * Each fbarray is unique to process namespace, i.e. the
769 * filename depends on process prefix. Try to take out a lock
770 * and see if we succeed. If we don't, someone else is using it
773 fd = eal_file_open(path, EAL_OPEN_CREATE | EAL_OPEN_READWRITE);
775 RTE_LOG(DEBUG, EAL, "%s(): couldn't open %s: %s\n",
776 __func__, path, rte_strerror(rte_errno));
778 } else if (eal_file_lock(
779 fd, EAL_FLOCK_EXCLUSIVE, EAL_FLOCK_RETURN)) {
780 RTE_LOG(DEBUG, EAL, "%s(): couldn't lock %s: %s\n",
781 __func__, path, rte_strerror(rte_errno));
786 /* take out a non-exclusive lock, so that other processes could
787 * still attach to it, but no other process could reinitialize
790 if (eal_file_lock(fd, EAL_FLOCK_SHARED, EAL_FLOCK_RETURN))
793 if (resize_and_map(fd, data, mmap_len))
800 /* do not close fd - keep it until detach/destroy */
801 TAILQ_INSERT_TAIL(&mem_area_tailq, ma, next);
803 /* initialize the data */
804 memset(data, 0, mmap_len);
806 /* populate data structure */
807 strlcpy(arr->name, name, sizeof(arr->name));
810 arr->elt_sz = elt_sz;
813 msk = get_used_mask(data, elt_sz, len);
814 msk->n_masks = MASK_LEN_TO_IDX(RTE_ALIGN_CEIL(len, MASK_ALIGN));
816 rte_rwlock_init(&arr->rwlock);
818 rte_spinlock_unlock(&mem_area_lock);
823 munmap(data, mmap_len);
828 rte_spinlock_unlock(&mem_area_lock);
833 rte_fbarray_attach(struct rte_fbarray *arr)
835 struct mem_area *ma = NULL, *tmp = NULL;
836 size_t page_sz, mmap_len;
847 * we don't need to synchronize attach as two values we need (element
848 * size and array length) are constant for the duration of life of
849 * the array, so the parts we care about will not race.
852 if (fully_validate(arr->name, arr->elt_sz, arr->len))
855 ma = malloc(sizeof(*ma));
861 page_sz = sysconf(_SC_PAGESIZE);
862 if (page_sz == (size_t)-1) {
867 mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
869 /* check the tailq - maybe user has already mapped this address space */
870 rte_spinlock_lock(&mem_area_lock);
872 TAILQ_FOREACH(tmp, &mem_area_tailq, next) {
873 if (overlap(tmp, arr->data, mmap_len)) {
879 /* we know this memory area is unique, so proceed */
881 data = eal_get_virtual_area(arr->data, &mmap_len, page_sz, 0, 0);
885 eal_get_fbarray_path(path, sizeof(path), arr->name);
887 fd = eal_file_open(path, EAL_OPEN_READWRITE);
892 /* lock the file, to let others know we're using it */
893 if (eal_file_lock(fd, EAL_FLOCK_SHARED, EAL_FLOCK_RETURN))
896 if (resize_and_map(fd, data, mmap_len))
899 /* store our new memory area */
901 ma->fd = fd; /* keep fd until detach/destroy */
904 TAILQ_INSERT_TAIL(&mem_area_tailq, ma, next);
908 rte_spinlock_unlock(&mem_area_lock);
912 munmap(data, mmap_len);
916 rte_spinlock_unlock(&mem_area_lock);
921 rte_fbarray_detach(struct rte_fbarray *arr)
923 struct mem_area *tmp = NULL;
933 * we don't need to synchronize detach as two values we need (element
934 * size and total capacity) are constant for the duration of life of
935 * the array, so the parts we care about will not race. if the user is
936 * detaching while doing something else in the same process, we can't
937 * really do anything about it, things will blow up either way.
940 size_t page_sz = sysconf(_SC_PAGESIZE);
942 if (page_sz == (size_t)-1)
945 mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
947 /* does this area exist? */
948 rte_spinlock_lock(&mem_area_lock);
950 TAILQ_FOREACH(tmp, &mem_area_tailq, next) {
951 if (tmp->addr == arr->data && tmp->len == mmap_len)
960 munmap(arr->data, mmap_len);
962 /* area is unmapped, close fd and remove the tailq entry */
965 TAILQ_REMOVE(&mem_area_tailq, tmp, next);
970 rte_spinlock_unlock(&mem_area_lock);
975 rte_fbarray_destroy(struct rte_fbarray *arr)
977 struct mem_area *tmp = NULL;
988 * we don't need to synchronize detach as two values we need (element
989 * size and total capacity) are constant for the duration of life of
990 * the array, so the parts we care about will not race. if the user is
991 * detaching while doing something else in the same process, we can't
992 * really do anything about it, things will blow up either way.
995 size_t page_sz = sysconf(_SC_PAGESIZE);
997 if (page_sz == (size_t)-1)
1000 mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
1002 /* does this area exist? */
1003 rte_spinlock_lock(&mem_area_lock);
1005 TAILQ_FOREACH(tmp, &mem_area_tailq, next) {
1006 if (tmp->addr == arr->data && tmp->len == mmap_len)
1014 /* with no shconf, there were never any files to begin with */
1015 if (!internal_config.no_shconf) {
1017 * attempt to get an exclusive lock on the file, to ensure it
1018 * has been detached by all other processes
1021 if (eal_file_lock(fd, EAL_FLOCK_EXCLUSIVE, EAL_FLOCK_RETURN)) {
1022 RTE_LOG(DEBUG, EAL, "Cannot destroy fbarray - another process is using it\n");
1028 /* we're OK to destroy the file */
1029 eal_get_fbarray_path(path, sizeof(path), arr->name);
1031 RTE_LOG(DEBUG, EAL, "Cannot unlink fbarray: %s\n",
1035 * we're still holding an exclusive lock, so drop it to
1038 eal_file_lock(fd, EAL_FLOCK_SHARED, EAL_FLOCK_RETURN);
1045 munmap(arr->data, mmap_len);
1047 /* area is unmapped, remove the tailq entry */
1048 TAILQ_REMOVE(&mem_area_tailq, tmp, next);
1052 /* reset the fbarray structure */
1053 memset(arr, 0, sizeof(*arr));
1055 rte_spinlock_unlock(&mem_area_lock);
1060 rte_fbarray_get(const struct rte_fbarray *arr, unsigned int idx)
1068 if (idx >= arr->len) {
1073 ret = RTE_PTR_ADD(arr->data, idx * arr->elt_sz);
1079 rte_fbarray_set_used(struct rte_fbarray *arr, unsigned int idx)
1081 return set_used(arr, idx, true);
1085 rte_fbarray_set_free(struct rte_fbarray *arr, unsigned int idx)
1087 return set_used(arr, idx, false);
1091 rte_fbarray_is_used(struct rte_fbarray *arr, unsigned int idx)
1093 struct used_mask *msk;
1098 if (arr == NULL || idx >= arr->len) {
1103 /* prevent array from changing under us */
1104 rte_rwlock_read_lock(&arr->rwlock);
1106 msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
1107 msk_idx = MASK_LEN_TO_IDX(idx);
1108 msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);
1110 ret = (msk->data[msk_idx] & msk_bit) != 0;
1112 rte_rwlock_read_unlock(&arr->rwlock);
1118 fbarray_find(struct rte_fbarray *arr, unsigned int start, bool next, bool used)
1122 if (arr == NULL || start >= arr->len) {
1127 /* prevent array from changing under us */
1128 rte_rwlock_read_lock(&arr->rwlock);
1130 /* cheap checks to prevent doing useless work */
1132 if (arr->len == arr->count) {
1136 if (arr->count == 0) {
1141 if (arr->count == 0) {
1145 if (arr->len == arr->count) {
1151 ret = find_next(arr, start, used);
1153 ret = find_prev(arr, start, used);
1155 rte_rwlock_read_unlock(&arr->rwlock);
1160 rte_fbarray_find_next_free(struct rte_fbarray *arr, unsigned int start)
1162 return fbarray_find(arr, start, true, false);
1166 rte_fbarray_find_next_used(struct rte_fbarray *arr, unsigned int start)
1168 return fbarray_find(arr, start, true, true);
1172 rte_fbarray_find_prev_free(struct rte_fbarray *arr, unsigned int start)
1174 return fbarray_find(arr, start, false, false);
1178 rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start)
1180 return fbarray_find(arr, start, false, true);
1184 fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n,
1185 bool next, bool used)
1189 if (arr == NULL || start >= arr->len || n > arr->len || n == 0) {
1193 if (next && (arr->len - start) < n) {
1194 rte_errno = used ? ENOENT : ENOSPC;
1197 if (!next && start < (n - 1)) {
1198 rte_errno = used ? ENOENT : ENOSPC;
1202 /* prevent array from changing under us */
1203 rte_rwlock_read_lock(&arr->rwlock);
1205 /* cheap checks to prevent doing useless work */
1207 if (arr->len == arr->count || arr->len - arr->count < n) {
1211 if (arr->count == 0) {
1212 ret = next ? start : start - n + 1;
1216 if (arr->count < n) {
1220 if (arr->count == arr->len) {
1221 ret = next ? start : start - n + 1;
1227 ret = find_next_n(arr, start, n, used);
1229 ret = find_prev_n(arr, start, n, used);
1231 rte_rwlock_read_unlock(&arr->rwlock);
1236 rte_fbarray_find_next_n_free(struct rte_fbarray *arr, unsigned int start,
1239 return fbarray_find_n(arr, start, n, true, false);
1243 rte_fbarray_find_next_n_used(struct rte_fbarray *arr, unsigned int start,
1246 return fbarray_find_n(arr, start, n, true, true);
1250 rte_fbarray_find_prev_n_free(struct rte_fbarray *arr, unsigned int start,
1253 return fbarray_find_n(arr, start, n, false, false);
1257 rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start,
1260 return fbarray_find_n(arr, start, n, false, true);
1264 fbarray_find_contig(struct rte_fbarray *arr, unsigned int start, bool next,
1269 if (arr == NULL || start >= arr->len) {
1274 /* prevent array from changing under us */
1275 rte_rwlock_read_lock(&arr->rwlock);
1277 /* cheap checks to prevent doing useless work */
1279 if (arr->count == 0) {
1283 if (next && arr->count == arr->len) {
1284 ret = arr->len - start;
1287 if (!next && arr->count == arr->len) {
1292 if (arr->len == arr->count) {
1296 if (next && arr->count == 0) {
1297 ret = arr->len - start;
1300 if (!next && arr->count == 0) {
1307 ret = find_contig(arr, start, used);
1309 ret = find_rev_contig(arr, start, used);
1311 rte_rwlock_read_unlock(&arr->rwlock);
1316 fbarray_find_biggest(struct rte_fbarray *arr, unsigned int start, bool used,
1319 int cur_idx, next_idx, cur_len, biggest_idx, biggest_len;
1320 /* don't stack if conditions, use function pointers instead */
1321 int (*find_func)(struct rte_fbarray *, unsigned int);
1322 int (*find_contig_func)(struct rte_fbarray *, unsigned int);
1324 if (arr == NULL || start >= arr->len) {
1328 /* the other API calls already do their fair share of cheap checks, so
1329 * no need to do them here.
1332 /* the API's called are thread-safe, but something may still happen
1333 * between the API calls, so lock the fbarray. all other API's are
1334 * read-locking the fbarray, so read lock here is OK.
1336 rte_rwlock_read_lock(&arr->rwlock);
1338 /* pick out appropriate functions */
1341 find_func = rte_fbarray_find_prev_used;
1342 find_contig_func = rte_fbarray_find_rev_contig_used;
1344 find_func = rte_fbarray_find_next_used;
1345 find_contig_func = rte_fbarray_find_contig_used;
1349 find_func = rte_fbarray_find_prev_free;
1350 find_contig_func = rte_fbarray_find_rev_contig_free;
1352 find_func = rte_fbarray_find_next_free;
1353 find_contig_func = rte_fbarray_find_contig_free;
1358 biggest_idx = -1; /* default is error */
1361 cur_idx = find_func(arr, cur_idx);
1363 /* block found, check its length */
1365 cur_len = find_contig_func(arr, cur_idx);
1366 /* decide where we go next */
1367 next_idx = rev ? cur_idx - cur_len : cur_idx + cur_len;
1368 /* move current index to start of chunk */
1369 cur_idx = rev ? next_idx + 1 : cur_idx;
1371 if (cur_len > biggest_len) {
1372 biggest_idx = cur_idx;
1373 biggest_len = cur_len;
1376 /* in reverse mode, next_idx may be -1 if chunk started
1377 * at array beginning. this means there's no more work
1383 /* nothing more to find, stop. however, a failed API
1384 * call has set rte_errno, which we want to ignore, as
1385 * reaching the end of fbarray is not an error.
1391 /* if we didn't find anything at all, set rte_errno */
1392 if (biggest_idx < 0)
1393 rte_errno = used ? ENOENT : ENOSPC;
1395 rte_rwlock_read_unlock(&arr->rwlock);
1400 rte_fbarray_find_biggest_free(struct rte_fbarray *arr, unsigned int start)
1402 return fbarray_find_biggest(arr, start, false, false);
1406 rte_fbarray_find_biggest_used(struct rte_fbarray *arr, unsigned int start)
1408 return fbarray_find_biggest(arr, start, true, false);
1412 rte_fbarray_find_rev_biggest_free(struct rte_fbarray *arr, unsigned int start)
1414 return fbarray_find_biggest(arr, start, false, true);
1418 rte_fbarray_find_rev_biggest_used(struct rte_fbarray *arr, unsigned int start)
1420 return fbarray_find_biggest(arr, start, true, true);
1425 rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start)
1427 return fbarray_find_contig(arr, start, true, false);
1431 rte_fbarray_find_contig_used(struct rte_fbarray *arr, unsigned int start)
1433 return fbarray_find_contig(arr, start, true, true);
1437 rte_fbarray_find_rev_contig_free(struct rte_fbarray *arr, unsigned int start)
1439 return fbarray_find_contig(arr, start, false, false);
1443 rte_fbarray_find_rev_contig_used(struct rte_fbarray *arr, unsigned int start)
1445 return fbarray_find_contig(arr, start, false, true);
1449 rte_fbarray_find_idx(const struct rte_fbarray *arr, const void *elt)
1455 * no need to synchronize as it doesn't matter if underlying data
1456 * changes - we're doing pointer arithmetic here.
1459 if (arr == NULL || elt == NULL) {
1463 end = RTE_PTR_ADD(arr->data, arr->elt_sz * arr->len);
1464 if (elt < arr->data || elt >= end) {
1469 ret = RTE_PTR_DIFF(elt, arr->data) / arr->elt_sz;
1475 rte_fbarray_dump_metadata(struct rte_fbarray *arr, FILE *f)
1477 struct used_mask *msk;
1480 if (arr == NULL || f == NULL) {
1485 if (fully_validate(arr->name, arr->elt_sz, arr->len)) {
1486 fprintf(f, "Invalid file-backed array\n");
1490 /* prevent array from changing under us */
1491 rte_rwlock_read_lock(&arr->rwlock);
1493 fprintf(f, "File-backed array: %s\n", arr->name);
1494 fprintf(f, "size: %i occupied: %i elt_sz: %i\n",
1495 arr->len, arr->count, arr->elt_sz);
1497 msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
1499 for (i = 0; i < msk->n_masks; i++)
1500 fprintf(f, "msk idx %i: 0x%016" PRIx64 "\n", i, msk->data[i]);
1502 rte_rwlock_read_unlock(&arr->rwlock);