lib/librte_eal/common/eal_common_fbarray.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2017-2018 Intel Corporation
   3  */
   4
   5 #include <inttypes.h>
   6 #include <sys/mman.h>
   7 #include <stdint.h>
   8 #include <errno.h>
   9 #include <sys/file.h>
  10 #include <string.h>
  11
  12 #include <rte_common.h>
  13 #include <rte_log.h>
  14 #include <rte_errno.h>
  15 #include <rte_spinlock.h>
  16 #include <rte_tailq.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 (1 << 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  * This is a mask that is always stored at the end of array, to provide fast
  31  * way of finding free/used spots without looping through each element.
  32  */
  33
  34 struct used_mask {
  35         int n_masks;
  36         uint64_t data[];
  37 };
  38
  39 static size_t
  40 calc_mask_size(int len)
  41 {
  42         /* mask must be multiple of MASK_ALIGN, even though length of array
  43          * itself may not be aligned on that boundary.
  44          */
  45         len = RTE_ALIGN_CEIL(len, MASK_ALIGN);
  46         return sizeof(struct used_mask) +
  47                         sizeof(uint64_t) * MASK_LEN_TO_IDX(len);
  48 }
  49
  50 static size_t
  51 calc_data_size(size_t page_sz, int elt_sz, int len)
  52 {
  53         size_t data_sz = elt_sz * len;
  54         size_t msk_sz = calc_mask_size(len);
  55         return RTE_ALIGN_CEIL(data_sz + msk_sz, page_sz);
  56 }
  57
  58 static struct used_mask *
  59 get_used_mask(void *data, int elt_sz, int len)
  60 {
  61         return (struct used_mask *) RTE_PTR_ADD(data, elt_sz * len);
  62 }
  63
  64 static int
  65 resize_and_map(int fd, void *addr, size_t len)
  66 {
  67         char path[PATH_MAX];
  68         void *map_addr;
  69
  70         if (ftruncate(fd, len)) {
  71                 RTE_LOG(ERR, EAL, "Cannot truncate %s\n", path);
  72                 /* pass errno up the chain */
  73                 rte_errno = errno;
  74                 return -1;
  75         }
  76
  77         map_addr = mmap(addr, len, PROT_READ | PROT_WRITE,
  78                         MAP_SHARED | MAP_FIXED, fd, 0);
  79         if (map_addr != addr) {
  80                 RTE_LOG(ERR, EAL, "mmap() failed: %s\n", strerror(errno));
  81                 /* pass errno up the chain */
  82                 rte_errno = errno;
  83                 return -1;
  84         }
  85         return 0;
  86 }
  87
  88 static int
  89 find_next_n(const struct rte_fbarray *arr, int start, int n, bool used)
  90 {
  91         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
  92                         arr->len);
  93         int msk_idx, lookahead_idx, first, first_mod;
  94         int last, last_mod, last_msk;
  95         uint64_t ignore_msk;
  96
  97         /*
  98          * mask only has granularity of MASK_ALIGN, but start may not be aligned
  99          * on that boundary, so construct a special mask to exclude anything we
 100          * don't want to see to avoid confusing ctz.
 101          */
 102         first = MASK_LEN_TO_IDX(start);
 103         first_mod = MASK_LEN_TO_MOD(start);
 104         ignore_msk = ~((1ULL << first_mod) - 1);
 105
 106         /* array length may not be aligned, so calculate ignore mask for last
 107          * mask index.
 108          */
 109         last = MASK_LEN_TO_IDX(arr->len);
 110         last_mod = MASK_LEN_TO_MOD(arr->len);
 111         last_msk = ~(-(1ULL) << last_mod);
 112
 113         for (msk_idx = first; msk_idx < msk->n_masks; msk_idx++) {
 114                 uint64_t cur_msk, lookahead_msk;
 115                 int run_start, clz, left;
 116                 bool found = false;
 117                 /*
 118                  * The process of getting n consecutive bits for arbitrary n is
 119                  * a bit involved, but here it is in a nutshell:
 120                  *
 121                  *  1. let n be the number of consecutive bits we're looking for
 122                  *  2. check if n can fit in one mask, and if so, do n-1
 123                  *     rshift-ands to see if there is an appropriate run inside
 124                  *     our current mask
 125                  *    2a. if we found a run, bail out early
 126                  *    2b. if we didn't find a run, proceed
 127                  *  3. invert the mask and count leading zeroes (that is, count
 128                  *     how many consecutive set bits we had starting from the
 129                  *     end of current mask) as k
 130                  *    3a. if k is 0, continue to next mask
 131                  *    3b. if k is not 0, we have a potential run
 132                  *  4. to satisfy our requirements, next mask must have n-k
 133                  *     consecutive set bits right at the start, so we will do
 134                  *     (n-k-1) rshift-ands and check if first bit is set.
 135                  *
 136                  * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until
 137                  * we either run out of masks, lose the run, or find what we
 138                  * were looking for.
 139                  */
 140                 cur_msk = msk->data[msk_idx];
 141                 left = n;
 142
 143                 /* if we're looking for free spaces, invert the mask */
 144                 if (!used)
 145                         cur_msk = ~cur_msk;
 146
 147                 /* combine current ignore mask with last index ignore mask */
 148                 if (msk_idx == last)
 149                         ignore_msk |= last_msk;
 150
 151                 /* if we have an ignore mask, ignore once */
 152                 if (ignore_msk) {
 153                         cur_msk &= ignore_msk;
 154                         ignore_msk = 0;
 155                 }
 156
 157                 /* if n can fit in within a single mask, do a search */
 158                 if (n <= MASK_ALIGN) {
 159                         uint64_t tmp_msk = cur_msk;
 160                         int s_idx;
 161                         for (s_idx = 0; s_idx < n - 1; s_idx++)
 162                                 tmp_msk &= tmp_msk >> 1ULL;
 163                         /* we found what we were looking for */
 164                         if (tmp_msk != 0) {
 165                                 run_start = __builtin_ctzll(tmp_msk);
 166                                 return MASK_GET_IDX(msk_idx, run_start);
 167                         }
 168                 }
 169
 170                 /*
 171                  * we didn't find our run within the mask, or n > MASK_ALIGN,
 172                  * so we're going for plan B.
 173                  */
 174
 175                 /* count leading zeroes on inverted mask */
 176                 if (~cur_msk == 0)
 177                         clz = sizeof(cur_msk) * 8;
 178                 else
 179                         clz = __builtin_clzll(~cur_msk);
 180
 181                 /* if there aren't any runs at the end either, just continue */
 182                 if (clz == 0)
 183                         continue;
 184
 185                 /* we have a partial run at the end, so try looking ahead */
 186                 run_start = MASK_ALIGN - clz;
 187                 left -= clz;
 188
 189                 for (lookahead_idx = msk_idx + 1; lookahead_idx < msk->n_masks;
 190                                 lookahead_idx++) {
 191                         int s_idx, need;
 192                         lookahead_msk = msk->data[lookahead_idx];
 193
 194                         /* if we're looking for free space, invert the mask */
 195                         if (!used)
 196                                 lookahead_msk = ~lookahead_msk;
 197
 198                         /* figure out how many consecutive bits we need here */
 199                         need = RTE_MIN(left, MASK_ALIGN);
 200
 201                         for (s_idx = 0; s_idx < need - 1; s_idx++)
 202                                 lookahead_msk &= lookahead_msk >> 1ULL;
 203
 204                         /* if first bit is not set, we've lost the run */
 205                         if ((lookahead_msk & 1) == 0) {
 206                                 /*
 207                                  * we've scanned this far, so we know there are
 208                                  * no runs in the space we've lookahead-scanned
 209                                  * as well, so skip that on next iteration.
 210                                  */
 211                                 ignore_msk = ~((1ULL << need) - 1);
 212                                 msk_idx = lookahead_idx;
 213                                 break;
 214                         }
 215
 216                         left -= need;
 217
 218                         /* check if we've found what we were looking for */
 219                         if (left == 0) {
 220                                 found = true;
 221                                 break;
 222                         }
 223                 }
 224
 225                 /* we didn't find anything, so continue */
 226                 if (!found)
 227                         continue;
 228
 229                 return MASK_GET_IDX(msk_idx, run_start);
 230         }
 231         /* we didn't find anything */
 232         rte_errno = used ? -ENOENT : -ENOSPC;
 233         return -1;
 234 }
 235
 236 static int
 237 find_next(const struct rte_fbarray *arr, int start, bool used)
 238 {
 239         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 240                         arr->len);
 241         int idx, first, first_mod;
 242         int last, last_mod, last_msk;
 243         uint64_t ignore_msk;
 244
 245         /*
 246          * mask only has granularity of MASK_ALIGN, but start may not be aligned
 247          * on that boundary, so construct a special mask to exclude anything we
 248          * don't want to see to avoid confusing ctz.
 249          */
 250         first = MASK_LEN_TO_IDX(start);
 251         first_mod = MASK_LEN_TO_MOD(start);
 252         ignore_msk = ~((1ULL << first_mod) - 1ULL);
 253
 254         /* array length may not be aligned, so calculate ignore mask for last
 255          * mask index.
 256          */
 257         last = MASK_LEN_TO_IDX(arr->len);
 258         last_mod = MASK_LEN_TO_MOD(arr->len);
 259         last_msk = ~(-(1ULL) << last_mod);
 260
 261         for (idx = first; idx < msk->n_masks; idx++) {
 262                 uint64_t cur = msk->data[idx];
 263                 int found;
 264
 265                 /* if we're looking for free entries, invert mask */
 266                 if (!used)
 267                         cur = ~cur;
 268
 269                 if (idx == last)
 270                         cur &= last_msk;
 271
 272                 /* ignore everything before start on first iteration */
 273                 if (idx == first)
 274                         cur &= ignore_msk;
 275
 276                 /* check if we have any entries */
 277                 if (cur == 0)
 278                         continue;
 279
 280                 /*
 281                  * find first set bit - that will correspond to whatever it is
 282                  * that we're looking for.
 283                  */
 284                 found = __builtin_ctzll(cur);
 285                 return MASK_GET_IDX(idx, found);
 286         }
 287         /* we didn't find anything */
 288         rte_errno = used ? -ENOENT : -ENOSPC;
 289         return -1;
 290 }
 291
 292 static int
 293 find_contig(const struct rte_fbarray *arr, int start, bool used)
 294 {
 295         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 296                         arr->len);
 297         int idx, first, first_mod;
 298         int last, last_mod, last_msk;
 299         int need_len, result = 0;
 300
 301         /* array length may not be aligned, so calculate ignore mask for last
 302          * mask index.
 303          */
 304         last = MASK_LEN_TO_IDX(arr->len);
 305         last_mod = MASK_LEN_TO_MOD(arr->len);
 306         last_msk = ~(-(1ULL) << last_mod);
 307
 308         first = MASK_LEN_TO_IDX(start);
 309         first_mod = MASK_LEN_TO_MOD(start);
 310         for (idx = first; idx < msk->n_masks; idx++, result += need_len) {
 311                 uint64_t cur = msk->data[idx];
 312                 int run_len;
 313
 314                 need_len = MASK_ALIGN;
 315
 316                 /* if we're looking for free entries, invert mask */
 317                 if (!used)
 318                         cur = ~cur;
 319
 320                 /* if this is last mask, ignore everything after last bit */
 321                 if (idx == last)
 322                         cur &= last_msk;
 323
 324                 /* ignore everything before start on first iteration */
 325                 if (idx == first) {
 326                         cur >>= first_mod;
 327                         /* at the start, we don't need the full mask len */
 328                         need_len -= first_mod;
 329                 }
 330
 331                 /* we will be looking for zeroes, so invert the mask */
 332                 cur = ~cur;
 333
 334                 /* if mask is zero, we have a complete run */
 335                 if (cur == 0)
 336                         continue;
 337
 338                 /*
 339                  * see if current run ends before mask end.
 340                  */
 341                 run_len = __builtin_ctzll(cur);
 342
 343                 /* add however many zeroes we've had in the last run and quit */
 344                 if (run_len < need_len) {
 345                         result += run_len;
 346                         break;
 347                 }
 348         }
 349         return result;
 350 }
 351
 352 static int
 353 set_used(struct rte_fbarray *arr, int idx, bool used)
 354 {
 355         struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
 356         uint64_t msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);
 357         int msk_idx = MASK_LEN_TO_IDX(idx);
 358         bool already_used;
 359         int ret = -1;
 360
 361         if (arr == NULL || idx < 0 || idx >= arr->len) {
 362                 rte_errno = EINVAL;
 363                 return -1;
 364         }
 365         ret = 0;
 366
 367         /* prevent array from changing under us */
 368         rte_rwlock_write_lock(&arr->rwlock);
 369
 370         already_used = (msk->data[msk_idx] & msk_bit) != 0;
 371
 372         /* nothing to be done */
 373         if (used == already_used)
 374                 goto out;
 375
 376         if (used) {
 377                 msk->data[msk_idx] |= msk_bit;
 378                 arr->count++;
 379         } else {
 380                 msk->data[msk_idx] &= ~msk_bit;
 381                 arr->count--;
 382         }
 383 out:
 384         rte_rwlock_write_unlock(&arr->rwlock);
 385
 386         return ret;
 387 }
 388
 389 static int
 390 fully_validate(const char *name, unsigned int elt_sz, unsigned int len)
 391 {
 392         if (name == NULL || elt_sz == 0 || len == 0) {
 393                 rte_errno = EINVAL;
 394                 return -1;
 395         }
 396
 397         if (strnlen(name, RTE_FBARRAY_NAME_LEN) == RTE_FBARRAY_NAME_LEN) {
 398                 rte_errno = ENAMETOOLONG;
 399                 return -1;
 400         }
 401         return 0;
 402 }
 403
 404 int __rte_experimental
 405 rte_fbarray_init(struct rte_fbarray *arr, const char *name, int len, int elt_sz)
 406 {
 407         size_t page_sz, mmap_len;
 408         char path[PATH_MAX];
 409         struct used_mask *msk;
 410         void *data = NULL;
 411         int fd = -1;
 412
 413         if (arr == NULL) {
 414                 rte_errno = EINVAL;
 415                 return -1;
 416         }
 417
 418         if (fully_validate(name, elt_sz, len))
 419                 return -1;
 420
 421         page_sz = sysconf(_SC_PAGESIZE);
 422
 423         /* calculate our memory limits */
 424         mmap_len = calc_data_size(page_sz, elt_sz, len);
 425
 426         data = eal_get_virtual_area(NULL, &mmap_len, page_sz, 0, 0);
 427         if (data == NULL)
 428                 goto fail;
 429
 430         eal_get_fbarray_path(path, sizeof(path), name);
 431
 432         /*
 433          * Each fbarray is unique to process namespace, i.e. the filename
 434          * depends on process prefix. Try to take out a lock and see if we
 435          * succeed. If we don't, someone else is using it already.
 436          */
 437         fd = open(path, O_CREAT | O_RDWR, 0600);
 438         if (fd < 0) {
 439                 RTE_LOG(DEBUG, EAL, "%s(): couldn't open %s: %s\n", __func__,
 440                                 path, strerror(errno));
 441                 rte_errno = errno;
 442                 goto fail;
 443         } else if (flock(fd, LOCK_EX | LOCK_NB)) {
 444                 RTE_LOG(DEBUG, EAL, "%s(): couldn't lock %s: %s\n", __func__,
 445                                 path, strerror(errno));
 446                 rte_errno = EBUSY;
 447                 goto fail;
 448         }
 449
 450         /* take out a non-exclusive lock, so that other processes could still
 451          * attach to it, but no other process could reinitialize it.
 452          */
 453         if (flock(fd, LOCK_SH | LOCK_NB)) {
 454                 rte_errno = errno;
 455                 goto fail;
 456         }
 457
 458         if (resize_and_map(fd, data, mmap_len))
 459                 goto fail;
 460
 461         /* we've mmap'ed the file, we can now close the fd */
 462         close(fd);
 463
 464         /* initialize the data */
 465         memset(data, 0, mmap_len);
 466
 467         /* populate data structure */
 468         snprintf(arr->name, sizeof(arr->name), "%s", name);
 469         arr->data = data;
 470         arr->len = len;
 471         arr->elt_sz = elt_sz;
 472         arr->count = 0;
 473
 474         msk = get_used_mask(data, elt_sz, len);
 475         msk->n_masks = MASK_LEN_TO_IDX(RTE_ALIGN_CEIL(len, MASK_ALIGN));
 476
 477         rte_rwlock_init(&arr->rwlock);
 478
 479         return 0;
 480 fail:
 481         if (data)
 482                 munmap(data, mmap_len);
 483         if (fd >= 0)
 484                 close(fd);
 485         return -1;
 486 }
 487
 488 int __rte_experimental
 489 rte_fbarray_attach(struct rte_fbarray *arr)
 490 {
 491         size_t page_sz, mmap_len;
 492         char path[PATH_MAX];
 493         void *data = NULL;
 494         int fd = -1;
 495
 496         if (arr == NULL) {
 497                 rte_errno = EINVAL;
 498                 return -1;
 499         }
 500
 501         /*
 502          * we don't need to synchronize attach as two values we need (element
 503          * size and array length) are constant for the duration of life of
 504          * the array, so the parts we care about will not race.
 505          */
 506
 507         if (fully_validate(arr->name, arr->elt_sz, arr->len))
 508                 return -1;
 509
 510         page_sz = sysconf(_SC_PAGESIZE);
 511
 512         mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
 513
 514         data = eal_get_virtual_area(arr->data, &mmap_len, page_sz, 0, 0);
 515         if (data == NULL)
 516                 goto fail;
 517
 518         eal_get_fbarray_path(path, sizeof(path), arr->name);
 519
 520         fd = open(path, O_RDWR);
 521         if (fd < 0) {
 522                 rte_errno = errno;
 523                 goto fail;
 524         }
 525
 526         /* lock the file, to let others know we're using it */
 527         if (flock(fd, LOCK_SH | LOCK_NB)) {
 528                 rte_errno = errno;
 529                 goto fail;
 530         }
 531
 532         if (resize_and_map(fd, data, mmap_len))
 533                 goto fail;
 534
 535         close(fd);
 536
 537         /* we're done */
 538
 539         return 0;
 540 fail:
 541         if (data)
 542                 munmap(data, mmap_len);
 543         if (fd >= 0)
 544                 close(fd);
 545         return -1;
 546 }
 547
 548 int __rte_experimental
 549 rte_fbarray_detach(struct rte_fbarray *arr)
 550 {
 551         if (arr == NULL) {
 552                 rte_errno = EINVAL;
 553                 return -1;
 554         }
 555
 556         /*
 557          * we don't need to synchronize detach as two values we need (element
 558          * size and total capacity) are constant for the duration of life of
 559          * the array, so the parts we care about will not race. if the user is
 560          * detaching while doing something else in the same process, we can't
 561          * really do anything about it, things will blow up either way.
 562          */
 563
 564         size_t page_sz = sysconf(_SC_PAGESIZE);
 565
 566         /* this may already be unmapped (e.g. repeated call from previously
 567          * failed destroy(), but this is on user, we can't (easily) know if this
 568          * is still mapped.
 569          */
 570         munmap(arr->data, calc_data_size(page_sz, arr->elt_sz, arr->len));
 571
 572         return 0;
 573 }
 574
 575 int __rte_experimental
 576 rte_fbarray_destroy(struct rte_fbarray *arr)
 577 {
 578         int fd, ret;
 579         char path[PATH_MAX];
 580
 581         ret = rte_fbarray_detach(arr);
 582         if (ret)
 583                 return ret;
 584
 585         /* try deleting the file */
 586         eal_get_fbarray_path(path, sizeof(path), arr->name);
 587
 588         fd = open(path, O_RDONLY);
 589         if (flock(fd, LOCK_EX | LOCK_NB)) {
 590                 RTE_LOG(DEBUG, EAL, "Cannot destroy fbarray - another process is using it\n");
 591                 rte_errno = EBUSY;
 592                 ret = -1;
 593         } else {
 594                 ret = 0;
 595                 unlink(path);
 596                 memset(arr, 0, sizeof(*arr));
 597         }
 598         close(fd);
 599
 600         return ret;
 601 }
 602
 603 void * __rte_experimental
 604 rte_fbarray_get(const struct rte_fbarray *arr, int idx)
 605 {
 606         void *ret = NULL;
 607         if (arr == NULL || idx < 0) {
 608                 rte_errno = EINVAL;
 609                 return NULL;
 610         }
 611
 612         if (idx >= arr->len) {
 613                 rte_errno = EINVAL;
 614                 return NULL;
 615         }
 616
 617         ret = RTE_PTR_ADD(arr->data, idx * arr->elt_sz);
 618
 619         return ret;
 620 }
 621
 622 int __rte_experimental
 623 rte_fbarray_set_used(struct rte_fbarray *arr, int idx)
 624 {
 625         return set_used(arr, idx, true);
 626 }
 627
 628 int __rte_experimental
 629 rte_fbarray_set_free(struct rte_fbarray *arr, int idx)
 630 {
 631         return set_used(arr, idx, false);
 632 }
 633
 634 int __rte_experimental
 635 rte_fbarray_is_used(struct rte_fbarray *arr, int idx)
 636 {
 637         struct used_mask *msk;
 638         int msk_idx;
 639         uint64_t msk_bit;
 640         int ret = -1;
 641
 642         if (arr == NULL || idx < 0 || idx >= arr->len) {
 643                 rte_errno = EINVAL;
 644                 return -1;
 645         }
 646
 647         /* prevent array from changing under us */
 648         rte_rwlock_read_lock(&arr->rwlock);
 649
 650         msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
 651         msk_idx = MASK_LEN_TO_IDX(idx);
 652         msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);
 653
 654         ret = (msk->data[msk_idx] & msk_bit) != 0;
 655
 656         rte_rwlock_read_unlock(&arr->rwlock);
 657
 658         return ret;
 659 }
 660
 661 int __rte_experimental
 662 rte_fbarray_find_next_free(struct rte_fbarray *arr, int start)
 663 {
 664         int ret = -1;
 665
 666         if (arr == NULL || start < 0 || start >= arr->len) {
 667                 rte_errno = EINVAL;
 668                 return -1;
 669         }
 670
 671         /* prevent array from changing under us */
 672         rte_rwlock_read_lock(&arr->rwlock);
 673
 674         if (arr->len == arr->count) {
 675                 rte_errno = ENOSPC;
 676                 goto out;
 677         }
 678
 679         ret = find_next(arr, start, false);
 680 out:
 681         rte_rwlock_read_unlock(&arr->rwlock);
 682         return ret;
 683 }
 684
 685 int __rte_experimental
 686 rte_fbarray_find_next_used(struct rte_fbarray *arr, int start)
 687 {
 688         int ret = -1;
 689
 690         if (arr == NULL || start < 0 || start >= arr->len) {
 691                 rte_errno = EINVAL;
 692                 return -1;
 693         }
 694
 695         /* prevent array from changing under us */
 696         rte_rwlock_read_lock(&arr->rwlock);
 697
 698         if (arr->count == 0) {
 699                 rte_errno = ENOENT;
 700                 goto out;
 701         }
 702
 703         ret = find_next(arr, start, true);
 704 out:
 705         rte_rwlock_read_unlock(&arr->rwlock);
 706         return ret;
 707 }
 708
 709 int __rte_experimental
 710 rte_fbarray_find_next_n_free(struct rte_fbarray *arr, int start, int n)
 711 {
 712         int ret = -1;
 713
 714         if (arr == NULL || start < 0 || start >= arr->len ||
 715                         n < 0 || n > arr->len) {
 716                 rte_errno = EINVAL;
 717                 return -1;
 718         }
 719
 720         /* prevent array from changing under us */
 721         rte_rwlock_read_lock(&arr->rwlock);
 722
 723         if (arr->len == arr->count || arr->len - arr->count < n) {
 724                 rte_errno = ENOSPC;
 725                 goto out;
 726         }
 727
 728         ret = find_next_n(arr, start, n, false);
 729 out:
 730         rte_rwlock_read_unlock(&arr->rwlock);
 731         return ret;
 732 }
 733
 734 int __rte_experimental
 735 rte_fbarray_find_next_n_used(struct rte_fbarray *arr, int start, int n)
 736 {
 737         int ret = -1;
 738
 739         if (arr == NULL || start < 0 || start >= arr->len ||
 740                         n < 0 || n > arr->len) {
 741                 rte_errno = EINVAL;
 742                 return -1;
 743         }
 744
 745         /* prevent array from changing under us */
 746         rte_rwlock_read_lock(&arr->rwlock);
 747
 748         if (arr->count < n) {
 749                 rte_errno = ENOENT;
 750                 goto out;
 751         }
 752
 753         ret = find_next_n(arr, start, n, true);
 754 out:
 755         rte_rwlock_read_unlock(&arr->rwlock);
 756         return ret;
 757 }
 758
 759 int __rte_experimental
 760 rte_fbarray_find_contig_free(struct rte_fbarray *arr, int start)
 761 {
 762         int ret = -1;
 763
 764         if (arr == NULL || start < 0 || start >= arr->len) {
 765                 rte_errno = EINVAL;
 766                 return -1;
 767         }
 768
 769         /* prevent array from changing under us */
 770         rte_rwlock_read_lock(&arr->rwlock);
 771
 772         if (arr->len == arr->count) {
 773                 rte_errno = ENOSPC;
 774                 goto out;
 775         }
 776
 777         if (arr->count == 0) {
 778                 ret = arr->len - start;
 779                 goto out;
 780         }
 781
 782         ret = find_contig(arr, start, false);
 783 out:
 784         rte_rwlock_read_unlock(&arr->rwlock);
 785         return ret;
 786 }
 787
 788 int __rte_experimental
 789 rte_fbarray_find_contig_used(struct rte_fbarray *arr, int start)
 790 {
 791         int ret = -1;
 792
 793         if (arr == NULL || start < 0 || start >= arr->len) {
 794                 rte_errno = EINVAL;
 795                 return -1;
 796         }
 797
 798         /* prevent array from changing under us */
 799         rte_rwlock_read_lock(&arr->rwlock);
 800
 801         ret = find_contig(arr, start, true);
 802
 803         rte_rwlock_read_unlock(&arr->rwlock);
 804         return ret;
 805 }
 806
 807 int __rte_experimental
 808 rte_fbarray_find_idx(const struct rte_fbarray *arr, const void *elt)
 809 {
 810         void *end;
 811         int ret = -1;
 812
 813         /*
 814          * no need to synchronize as it doesn't matter if underlying data
 815          * changes - we're doing pointer arithmetic here.
 816          */
 817
 818         if (arr == NULL || elt == NULL) {
 819                 rte_errno = EINVAL;
 820                 return -1;
 821         }
 822         end = RTE_PTR_ADD(arr->data, arr->elt_sz * arr->len);
 823         if (elt < arr->data || elt >= end) {
 824                 rte_errno = EINVAL;
 825                 return -1;
 826         }
 827
 828         ret = RTE_PTR_DIFF(elt, arr->data) / arr->elt_sz;
 829
 830         return ret;
 831 }
 832
 833 void __rte_experimental
 834 rte_fbarray_dump_metadata(struct rte_fbarray *arr, FILE *f)
 835 {
 836         struct used_mask *msk;
 837         int i;
 838
 839         if (arr == NULL || f == NULL) {
 840                 rte_errno = EINVAL;
 841                 return;
 842         }
 843
 844         if (fully_validate(arr->name, arr->elt_sz, arr->len)) {
 845                 fprintf(f, "Invalid file-backed array\n");
 846                 goto out;
 847         }
 848
 849         /* prevent array from changing under us */
 850         rte_rwlock_read_lock(&arr->rwlock);
 851
 852         fprintf(f, "File-backed array: %s\n", arr->name);
 853         fprintf(f, "size: %i occupied: %i elt_sz: %i\n",
 854                         arr->len, arr->count, arr->elt_sz);
 855
 856         msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
 857
 858         for (i = 0; i < msk->n_masks; i++)
 859                 fprintf(f, "msk idx %i: 0x%016" PRIx64 "\n", i, msk->data[i]);
 860 out:
 861         rte_rwlock_read_unlock(&arr->rwlock);
 862 }