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