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