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 <fcntl.h>
   6 #include <inttypes.h>
   7 #include <limits.h>
   8 #include <sys/mman.h>
   9 #include <stdint.h>
  10 #include <errno.h>
  11 #include <string.h>
  12 #include <unistd.h>
  13
  14 #include <rte_common.h>
  15 #include <rte_log.h>
  16 #include <rte_errno.h>
  17 #include <rte_spinlock.h>
  18 #include <rte_tailq.h>
  19
  20 #include "eal_filesystem.h"
  21 #include "eal_private.h"
  22
  23 #include "rte_fbarray.h"
  24
  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)
  30
  31 /*
  32  * We use this to keep track of created/attached memory areas to prevent user
  33  * errors in API usage.
  34  */
  35 struct mem_area {
  36         TAILQ_ENTRY(mem_area) next;
  37         void *addr;
  38         size_t len;
  39         int fd;
  40 };
  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;
  46
  47 /*
  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.
  50  */
  51
  52 struct used_mask {
  53         unsigned int n_masks;
  54         uint64_t data[];
  55 };
  56
  57 static size_t
  58 calc_mask_size(unsigned int len)
  59 {
  60         /* mask must be multiple of MASK_ALIGN, even though length of array
  61          * itself may not be aligned on that boundary.
  62          */
  63         len = RTE_ALIGN_CEIL(len, MASK_ALIGN);
  64         return sizeof(struct used_mask) +
  65                         sizeof(uint64_t) * MASK_LEN_TO_IDX(len);
  66 }
  67
  68 static size_t
  69 calc_data_size(size_t page_sz, unsigned int elt_sz, unsigned int len)
  70 {
  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);
  74 }
  75
  76 static struct used_mask *
  77 get_used_mask(void *data, unsigned int elt_sz, unsigned int len)
  78 {
  79         return (struct used_mask *) RTE_PTR_ADD(data, elt_sz * len);
  80 }
  81
  82 static int
  83 resize_and_map(int fd, void *addr, size_t len)
  84 {
  85         char path[PATH_MAX];
  86         void *map_addr;
  87
  88         if (eal_file_truncate(fd, len)) {
  89                 RTE_LOG(ERR, EAL, "Cannot truncate %s\n", path);
  90                 return -1;
  91         }
  92
  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 */
  98                 rte_errno = errno;
  99                 return -1;
 100         }
 101         return 0;
 102 }
 103
 104 static int
 105 overlap(const struct mem_area *ma, const void *start, size_t len)
 106 {
 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);
 110
 111         /* start overlap? */
 112         if (start >= ma_start && start < ma_end)
 113                 return 1;
 114         /* end overlap? */
 115         if (end >= ma_start && end < ma_end)
 116                 return 1;
 117         return 0;
 118 }
 119
 120 static int
 121 find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
 122             bool used)
 123 {
 124         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 125                         arr->len);
 126         unsigned int msk_idx, lookahead_idx, first, first_mod;
 127         unsigned int last, last_mod;
 128         uint64_t last_msk, ignore_msk;
 129
 130         /*
 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.
 134          */
 135         first = MASK_LEN_TO_IDX(start);
 136         first_mod = MASK_LEN_TO_MOD(start);
 137         ignore_msk = ~((1ULL << first_mod) - 1);
 138
 139         /* array length may not be aligned, so calculate ignore mask for last
 140          * mask index.
 141          */
 142         last = MASK_LEN_TO_IDX(arr->len);
 143         last_mod = MASK_LEN_TO_MOD(arr->len);
 144         last_msk = ~(-1ULL << last_mod);
 145
 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;
 149                 bool found = false;
 150                 /*
 151                  * The process of getting n consecutive bits for arbitrary n is
 152                  * a bit involved, but here it is in a nutshell:
 153                  *
 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
 157                  *     our current mask
 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.
 168                  *
 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
 171                  * were looking for.
 172                  */
 173                 cur_msk = msk->data[msk_idx];
 174                 left = n;
 175
 176                 /* if we're looking for free spaces, invert the mask */
 177                 if (!used)
 178                         cur_msk = ~cur_msk;
 179
 180                 /* combine current ignore mask with last index ignore mask */
 181                 if (msk_idx == last)
 182                         ignore_msk |= last_msk;
 183
 184                 /* if we have an ignore mask, ignore once */
 185                 if (ignore_msk) {
 186                         cur_msk &= ignore_msk;
 187                         ignore_msk = 0;
 188                 }
 189
 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;
 193                         unsigned int s_idx;
 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 */
 197                         if (tmp_msk != 0) {
 198                                 run_start = __builtin_ctzll(tmp_msk);
 199                                 return MASK_GET_IDX(msk_idx, run_start);
 200                         }
 201                 }
 202
 203                 /*
 204                  * we didn't find our run within the mask, or n > MASK_ALIGN,
 205                  * so we're going for plan B.
 206                  */
 207
 208                 /* count leading zeroes on inverted mask */
 209                 if (~cur_msk == 0)
 210                         clz = sizeof(cur_msk) * 8;
 211                 else
 212                         clz = __builtin_clzll(~cur_msk);
 213
 214                 /* if there aren't any runs at the end either, just continue */
 215                 if (clz == 0)
 216                         continue;
 217
 218                 /* we have a partial run at the end, so try looking ahead */
 219                 run_start = MASK_ALIGN - clz;
 220                 left -= clz;
 221
 222                 for (lookahead_idx = msk_idx + 1; lookahead_idx < msk->n_masks;
 223                                 lookahead_idx++) {
 224                         unsigned int s_idx, need;
 225                         lookahead_msk = msk->data[lookahead_idx];
 226
 227                         /* if we're looking for free space, invert the mask */
 228                         if (!used)
 229                                 lookahead_msk = ~lookahead_msk;
 230
 231                         /* figure out how many consecutive bits we need here */
 232                         need = RTE_MIN(left, MASK_ALIGN);
 233
 234                         for (s_idx = 0; s_idx < need - 1; s_idx++)
 235                                 lookahead_msk &= lookahead_msk >> 1ULL;
 236
 237                         /* if first bit is not set, we've lost the run */
 238                         if ((lookahead_msk & 1) == 0) {
 239                                 /*
 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.
 243                                  */
 244                                 ignore_msk = ~((1ULL << need) - 1);
 245                                 msk_idx = lookahead_idx;
 246                                 break;
 247                         }
 248
 249                         left -= need;
 250
 251                         /* check if we've found what we were looking for */
 252                         if (left == 0) {
 253                                 found = true;
 254                                 break;
 255                         }
 256                 }
 257
 258                 /* we didn't find anything, so continue */
 259                 if (!found)
 260                         continue;
 261
 262                 return MASK_GET_IDX(msk_idx, run_start);
 263         }
 264         /* we didn't find anything */
 265         rte_errno = used ? ENOENT : ENOSPC;
 266         return -1;
 267 }
 268
 269 static int
 270 find_next(const struct rte_fbarray *arr, unsigned int start, bool used)
 271 {
 272         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 273                         arr->len);
 274         unsigned int idx, first, first_mod;
 275         unsigned int last, last_mod;
 276         uint64_t last_msk, ignore_msk;
 277
 278         /*
 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.
 282          */
 283         first = MASK_LEN_TO_IDX(start);
 284         first_mod = MASK_LEN_TO_MOD(start);
 285         ignore_msk = ~((1ULL << first_mod) - 1ULL);
 286
 287         /* array length may not be aligned, so calculate ignore mask for last
 288          * mask index.
 289          */
 290         last = MASK_LEN_TO_IDX(arr->len);
 291         last_mod = MASK_LEN_TO_MOD(arr->len);
 292         last_msk = ~(-(1ULL) << last_mod);
 293
 294         for (idx = first; idx < msk->n_masks; idx++) {
 295                 uint64_t cur = msk->data[idx];
 296                 int found;
 297
 298                 /* if we're looking for free entries, invert mask */
 299                 if (!used)
 300                         cur = ~cur;
 301
 302                 if (idx == last)
 303                         cur &= last_msk;
 304
 305                 /* ignore everything before start on first iteration */
 306                 if (idx == first)
 307                         cur &= ignore_msk;
 308
 309                 /* check if we have any entries */
 310                 if (cur == 0)
 311                         continue;
 312
 313                 /*
 314                  * find first set bit - that will correspond to whatever it is
 315                  * that we're looking for.
 316                  */
 317                 found = __builtin_ctzll(cur);
 318                 return MASK_GET_IDX(idx, found);
 319         }
 320         /* we didn't find anything */
 321         rte_errno = used ? ENOENT : ENOSPC;
 322         return -1;
 323 }
 324
 325 static int
 326 find_contig(const struct rte_fbarray *arr, unsigned int start, bool used)
 327 {
 328         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 329                         arr->len);
 330         unsigned int idx, first, first_mod;
 331         unsigned int last, last_mod;
 332         uint64_t last_msk;
 333         unsigned int need_len, result = 0;
 334
 335         /* array length may not be aligned, so calculate ignore mask for last
 336          * mask index.
 337          */
 338         last = MASK_LEN_TO_IDX(arr->len);
 339         last_mod = MASK_LEN_TO_MOD(arr->len);
 340         last_msk = ~(-(1ULL) << last_mod);
 341
 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;
 347
 348                 need_len = MASK_ALIGN;
 349
 350                 /* if we're looking for free entries, invert mask */
 351                 if (!used)
 352                         cur = ~cur;
 353
 354                 /* if this is last mask, ignore everything after last bit */
 355                 if (idx == last)
 356                         cur &= last_msk;
 357
 358                 /* ignore everything before start on first iteration */
 359                 if (idx == first) {
 360                         cur >>= first_mod;
 361                         /* at the start, we don't need the full mask len */
 362                         need_len -= first_mod;
 363                 }
 364
 365                 /* we will be looking for zeroes, so invert the mask */
 366                 cur = ~cur;
 367
 368                 /* if mask is zero, we have a complete run */
 369                 if (cur == 0)
 370                         continue;
 371
 372                 /*
 373                  * see if current run ends before mask end.
 374                  */
 375                 run_len = __builtin_ctzll(cur);
 376
 377                 /* add however many zeroes we've had in the last run and quit */
 378                 if (run_len < need_len) {
 379                         result += run_len;
 380                         break;
 381                 }
 382         }
 383         return result;
 384 }
 385
 386 static int
 387 find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
 388                 bool used)
 389 {
 390         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 391                         arr->len);
 392         unsigned int msk_idx, lookbehind_idx, first, first_mod;
 393         uint64_t ignore_msk;
 394
 395         /*
 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.
 399          */
 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));
 406
 407         /* go backwards, include zero */
 408         msk_idx = first;
 409         do {
 410                 uint64_t cur_msk, lookbehind_msk;
 411                 unsigned int run_start, run_end, ctz, left;
 412                 bool found = false;
 413                 /*
 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:
 416                  *
 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
 420                  *     our current mask
 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.
 431                  *
 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
 434                  * were looking for.
 435                  */
 436                 cur_msk = msk->data[msk_idx];
 437                 left = n;
 438
 439                 /* if we're looking for free spaces, invert the mask */
 440                 if (!used)
 441                         cur_msk = ~cur_msk;
 442
 443                 /* if we have an ignore mask, ignore once */
 444                 if (ignore_msk) {
 445                         cur_msk &= ignore_msk;
 446                         ignore_msk = 0;
 447                 }
 448
 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;
 452                         unsigned int s_idx;
 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 */
 456                         if (tmp_msk != 0) {
 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
 460                                  * would have been.
 461                                  */
 462                                 run_start = MASK_ALIGN -
 463                                                 __builtin_clzll(tmp_msk) - n;
 464                                 return MASK_GET_IDX(msk_idx, run_start);
 465                         }
 466                 }
 467
 468                 /*
 469                  * we didn't find our run within the mask, or n > MASK_ALIGN,
 470                  * so we're going for plan B.
 471                  */
 472
 473                 /* count trailing zeroes on inverted mask */
 474                 if (~cur_msk == 0)
 475                         ctz = sizeof(cur_msk) * 8;
 476                 else
 477                         ctz = __builtin_ctzll(~cur_msk);
 478
 479                 /* if there aren't any runs at the start either, just
 480                  * continue
 481                  */
 482                 if (ctz == 0)
 483                         continue;
 484
 485                 /* we have a partial run at the start, so try looking behind */
 486                 run_end = MASK_GET_IDX(msk_idx, ctz);
 487                 left -= ctz;
 488
 489                 /* go backwards, include zero */
 490                 lookbehind_idx = msk_idx - 1;
 491
 492                 /* we can't lookbehind as we've run out of masks, so stop */
 493                 if (msk_idx == 0)
 494                         break;
 495
 496                 do {
 497                         const uint64_t last_bit = 1ULL << (MASK_ALIGN - 1);
 498                         unsigned int s_idx, need;
 499
 500                         lookbehind_msk = msk->data[lookbehind_idx];
 501
 502                         /* if we're looking for free space, invert the mask */
 503                         if (!used)
 504                                 lookbehind_msk = ~lookbehind_msk;
 505
 506                         /* figure out how many consecutive bits we need here */
 507                         need = RTE_MIN(left, MASK_ALIGN);
 508
 509                         for (s_idx = 0; s_idx < need - 1; s_idx++)
 510                                 lookbehind_msk &= lookbehind_msk << 1ULL;
 511
 512                         /* if last bit is not set, we've lost the run */
 513                         if ((lookbehind_msk & last_bit) == 0) {
 514                                 /*
 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.
 518                                  */
 519                                 ignore_msk = -1ULL << need;
 520                                 msk_idx = lookbehind_idx;
 521                                 break;
 522                         }
 523
 524                         left -= need;
 525
 526                         /* check if we've found what we were looking for */
 527                         if (left == 0) {
 528                                 found = true;
 529                                 break;
 530                         }
 531                 } while ((lookbehind_idx--) != 0); /* decrement after check to
 532                                                     * include zero
 533                                                     */
 534
 535                 /* we didn't find anything, so continue */
 536                 if (!found)
 537                         continue;
 538
 539                 /* we've found what we were looking for, but we only know where
 540                  * the run ended, so calculate start position.
 541                  */
 542                 return run_end - n;
 543         } while (msk_idx-- != 0); /* decrement after check to include zero */
 544         /* we didn't find anything */
 545         rte_errno = used ? ENOENT : ENOSPC;
 546         return -1;
 547 }
 548
 549 static int
 550 find_prev(const struct rte_fbarray *arr, unsigned int start, bool used)
 551 {
 552         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 553                         arr->len);
 554         unsigned int idx, first, first_mod;
 555         uint64_t ignore_msk;
 556
 557         /*
 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.
 561          */
 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));
 568
 569         /* go backwards, include zero */
 570         idx = first;
 571         do {
 572                 uint64_t cur = msk->data[idx];
 573                 int found;
 574
 575                 /* if we're looking for free entries, invert mask */
 576                 if (!used)
 577                         cur = ~cur;
 578
 579                 /* ignore everything before start on first iteration */
 580                 if (idx == first)
 581                         cur &= ignore_msk;
 582
 583                 /* check if we have any entries */
 584                 if (cur == 0)
 585                         continue;
 586
 587                 /*
 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.
 592                  */
 593                 found = MASK_ALIGN - __builtin_clzll(cur) - 1;
 594
 595                 return MASK_GET_IDX(idx, found);
 596         } while (idx-- != 0); /* decrement after check  to include zero*/
 597
 598         /* we didn't find anything */
 599         rte_errno = used ? ENOENT : ENOSPC;
 600         return -1;
 601 }
 602
 603 static int
 604 find_rev_contig(const struct rte_fbarray *arr, unsigned int start, bool used)
 605 {
 606         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 607                         arr->len);
 608         unsigned int idx, first, first_mod;
 609         unsigned int need_len, result = 0;
 610
 611         first = MASK_LEN_TO_IDX(start);
 612         first_mod = MASK_LEN_TO_MOD(start);
 613
 614         /* go backwards, include zero */
 615         idx = first;
 616         do {
 617                 uint64_t cur = msk->data[idx];
 618                 unsigned int run_len;
 619
 620                 need_len = MASK_ALIGN;
 621
 622                 /* if we're looking for free entries, invert mask */
 623                 if (!used)
 624                         cur = ~cur;
 625
 626                 /* ignore everything after start on first iteration */
 627                 if (idx == first) {
 628                         unsigned int end_len = MASK_ALIGN - first_mod - 1;
 629                         cur <<= end_len;
 630                         /* at the start, we don't need the full mask len */
 631                         need_len -= end_len;
 632                 }
 633
 634                 /* we will be looking for zeroes, so invert the mask */
 635                 cur = ~cur;
 636
 637                 /* if mask is zero, we have a complete run */
 638                 if (cur == 0)
 639                         goto endloop;
 640
 641                 /*
 642                  * see where run ends, starting from the end.
 643                  */
 644                 run_len = __builtin_clzll(cur);
 645
 646                 /* add however many zeroes we've had in the last run and quit */
 647                 if (run_len < need_len) {
 648                         result += run_len;
 649                         break;
 650                 }
 651 endloop:
 652                 result += need_len;
 653         } while (idx-- != 0); /* decrement after check to include zero */
 654         return result;
 655 }
 656
 657 static int
 658 set_used(struct rte_fbarray *arr, unsigned int idx, bool used)
 659 {
 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);
 663         bool already_used;
 664         int ret = -1;
 665
 666         if (arr == NULL || idx >= arr->len) {
 667                 rte_errno = EINVAL;
 668                 return -1;
 669         }
 670         msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
 671         ret = 0;
 672
 673         /* prevent array from changing under us */
 674         rte_rwlock_write_lock(&arr->rwlock);
 675
 676         already_used = (msk->data[msk_idx] & msk_bit) != 0;
 677
 678         /* nothing to be done */
 679         if (used == already_used)
 680                 goto out;
 681
 682         if (used) {
 683                 msk->data[msk_idx] |= msk_bit;
 684                 arr->count++;
 685         } else {
 686                 msk->data[msk_idx] &= ~msk_bit;
 687                 arr->count--;
 688         }
 689 out:
 690         rte_rwlock_write_unlock(&arr->rwlock);
 691
 692         return ret;
 693 }
 694
 695 static int
 696 fully_validate(const char *name, unsigned int elt_sz, unsigned int len)
 697 {
 698         if (name == NULL || elt_sz == 0 || len == 0 || len > INT_MAX) {
 699                 rte_errno = EINVAL;
 700                 return -1;
 701         }
 702
 703         if (strnlen(name, RTE_FBARRAY_NAME_LEN) == RTE_FBARRAY_NAME_LEN) {
 704                 rte_errno = ENAMETOOLONG;
 705                 return -1;
 706         }
 707         return 0;
 708 }
 709
 710 int
 711 rte_fbarray_init(struct rte_fbarray *arr, const char *name, unsigned int len,
 712                 unsigned int elt_sz)
 713 {
 714         size_t page_sz, mmap_len;
 715         char path[PATH_MAX];
 716         struct used_mask *msk;
 717         struct mem_area *ma = NULL;
 718         void *data = NULL;
 719         int fd = -1;
 720
 721         if (arr == NULL) {
 722                 rte_errno = EINVAL;
 723                 return -1;
 724         }
 725
 726         if (fully_validate(name, elt_sz, len))
 727                 return -1;
 728
 729         /* allocate mem area before doing anything */
 730         ma = malloc(sizeof(*ma));
 731         if (ma == NULL) {
 732                 rte_errno = ENOMEM;
 733                 return -1;
 734         }
 735
 736         page_sz = sysconf(_SC_PAGESIZE);
 737         if (page_sz == (size_t)-1) {
 738                 free(ma);
 739                 return -1;
 740         }
 741
 742         /* calculate our memory limits */
 743         mmap_len = calc_data_size(page_sz, elt_sz, len);
 744
 745         data = eal_get_virtual_area(NULL, &mmap_len, page_sz, 0, 0);
 746         if (data == NULL) {
 747                 free(ma);
 748                 return -1;
 749         }
 750
 751         rte_spinlock_lock(&mem_area_lock);
 752
 753         fd = -1;
 754
 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));
 762                         goto fail;
 763                 }
 764         } else {
 765                 eal_get_fbarray_path(path, sizeof(path), name);
 766
 767                 /*
 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
 771                  * already.
 772                  */
 773                 fd = eal_file_open(path, EAL_OPEN_CREATE | EAL_OPEN_READWRITE);
 774                 if (fd < 0) {
 775                         RTE_LOG(DEBUG, EAL, "%s(): couldn't open %s: %s\n",
 776                                 __func__, path, rte_strerror(rte_errno));
 777                         goto fail;
 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));
 782                         rte_errno = EBUSY;
 783                         goto fail;
 784                 }
 785
 786                 /* take out a non-exclusive lock, so that other processes could
 787                  * still attach to it, but no other process could reinitialize
 788                  * it.
 789                  */
 790                 if (eal_file_lock(fd, EAL_FLOCK_SHARED, EAL_FLOCK_RETURN))
 791                         goto fail;
 792
 793                 if (resize_and_map(fd, data, mmap_len))
 794                         goto fail;
 795         }
 796         ma->addr = data;
 797         ma->len = mmap_len;
 798         ma->fd = fd;
 799
 800         /* do not close fd - keep it until detach/destroy */
 801         TAILQ_INSERT_TAIL(&mem_area_tailq, ma, next);
 802
 803         /* initialize the data */
 804         memset(data, 0, mmap_len);
 805
 806         /* populate data structure */
 807         strlcpy(arr->name, name, sizeof(arr->name));
 808         arr->data = data;
 809         arr->len = len;
 810         arr->elt_sz = elt_sz;
 811         arr->count = 0;
 812
 813         msk = get_used_mask(data, elt_sz, len);
 814         msk->n_masks = MASK_LEN_TO_IDX(RTE_ALIGN_CEIL(len, MASK_ALIGN));
 815
 816         rte_rwlock_init(&arr->rwlock);
 817
 818         rte_spinlock_unlock(&mem_area_lock);
 819
 820         return 0;
 821 fail:
 822         if (data)
 823                 munmap(data, mmap_len);
 824         if (fd >= 0)
 825                 close(fd);
 826         free(ma);
 827
 828         rte_spinlock_unlock(&mem_area_lock);
 829         return -1;
 830 }
 831
 832 int
 833 rte_fbarray_attach(struct rte_fbarray *arr)
 834 {
 835         struct mem_area *ma = NULL, *tmp = NULL;
 836         size_t page_sz, mmap_len;
 837         char path[PATH_MAX];
 838         void *data = NULL;
 839         int fd = -1;
 840
 841         if (arr == NULL) {
 842                 rte_errno = EINVAL;
 843                 return -1;
 844         }
 845
 846         /*
 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.
 850          */
 851
 852         if (fully_validate(arr->name, arr->elt_sz, arr->len))
 853                 return -1;
 854
 855         ma = malloc(sizeof(*ma));
 856         if (ma == NULL) {
 857                 rte_errno = ENOMEM;
 858                 return -1;
 859         }
 860
 861         page_sz = sysconf(_SC_PAGESIZE);
 862         if (page_sz == (size_t)-1) {
 863                 free(ma);
 864                 return -1;
 865         }
 866
 867         mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
 868
 869         /* check the tailq - maybe user has already mapped this address space */
 870         rte_spinlock_lock(&mem_area_lock);
 871
 872         TAILQ_FOREACH(tmp, &mem_area_tailq, next) {
 873                 if (overlap(tmp, arr->data, mmap_len)) {
 874                         rte_errno = EEXIST;
 875                         goto fail;
 876                 }
 877         }
 878
 879         /* we know this memory area is unique, so proceed */
 880
 881         data = eal_get_virtual_area(arr->data, &mmap_len, page_sz, 0, 0);
 882         if (data == NULL)
 883                 goto fail;
 884
 885         eal_get_fbarray_path(path, sizeof(path), arr->name);
 886
 887         fd = eal_file_open(path, EAL_OPEN_READWRITE);
 888         if (fd < 0) {
 889                 goto fail;
 890         }
 891
 892         /* lock the file, to let others know we're using it */
 893         if (eal_file_lock(fd, EAL_FLOCK_SHARED, EAL_FLOCK_RETURN))
 894                 goto fail;
 895
 896         if (resize_and_map(fd, data, mmap_len))
 897                 goto fail;
 898
 899         /* store our new memory area */
 900         ma->addr = data;
 901         ma->fd = fd; /* keep fd until detach/destroy */
 902         ma->len = mmap_len;
 903
 904         TAILQ_INSERT_TAIL(&mem_area_tailq, ma, next);
 905
 906         /* we're done */
 907
 908         rte_spinlock_unlock(&mem_area_lock);
 909         return 0;
 910 fail:
 911         if (data)
 912                 munmap(data, mmap_len);
 913         if (fd >= 0)
 914                 close(fd);
 915         free(ma);
 916         rte_spinlock_unlock(&mem_area_lock);
 917         return -1;
 918 }
 919
 920 int
 921 rte_fbarray_detach(struct rte_fbarray *arr)
 922 {
 923         struct mem_area *tmp = NULL;
 924         size_t mmap_len;
 925         int ret = -1;
 926
 927         if (arr == NULL) {
 928                 rte_errno = EINVAL;
 929                 return -1;
 930         }
 931
 932         /*
 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.
 938          */
 939
 940         size_t page_sz = sysconf(_SC_PAGESIZE);
 941
 942         if (page_sz == (size_t)-1)
 943                 return -1;
 944
 945         mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
 946
 947         /* does this area exist? */
 948         rte_spinlock_lock(&mem_area_lock);
 949
 950         TAILQ_FOREACH(tmp, &mem_area_tailq, next) {
 951                 if (tmp->addr == arr->data && tmp->len == mmap_len)
 952                         break;
 953         }
 954         if (tmp == NULL) {
 955                 rte_errno = ENOENT;
 956                 ret = -1;
 957                 goto out;
 958         }
 959
 960         munmap(arr->data, mmap_len);
 961
 962         /* area is unmapped, close fd and remove the tailq entry */
 963         if (tmp->fd >= 0)
 964                 close(tmp->fd);
 965         TAILQ_REMOVE(&mem_area_tailq, tmp, next);
 966         free(tmp);
 967
 968         ret = 0;
 969 out:
 970         rte_spinlock_unlock(&mem_area_lock);
 971         return ret;
 972 }
 973
 974 int
 975 rte_fbarray_destroy(struct rte_fbarray *arr)
 976 {
 977         struct mem_area *tmp = NULL;
 978         size_t mmap_len;
 979         int fd, ret;
 980         char path[PATH_MAX];
 981
 982         if (arr == NULL) {
 983                 rte_errno = EINVAL;
 984                 return -1;
 985         }
 986
 987         /*
 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.
 993          */
 994
 995         size_t page_sz = sysconf(_SC_PAGESIZE);
 996
 997         if (page_sz == (size_t)-1)
 998                 return -1;
 999
1000         mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
1001
1002         /* does this area exist? */
1003         rte_spinlock_lock(&mem_area_lock);
1004
1005         TAILQ_FOREACH(tmp, &mem_area_tailq, next) {
1006                 if (tmp->addr == arr->data && tmp->len == mmap_len)
1007                         break;
1008         }
1009         if (tmp == NULL) {
1010                 rte_errno = ENOENT;
1011                 ret = -1;
1012                 goto out;
1013         }
1014         /* with no shconf, there were never any files to begin with */
1015         if (!internal_config.no_shconf) {
1016                 /*
1017                  * attempt to get an exclusive lock on the file, to ensure it
1018                  * has been detached by all other processes
1019                  */
1020                 fd = tmp->fd;
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");
1023                         rte_errno = EBUSY;
1024                         ret = -1;
1025                         goto out;
1026                 }
1027
1028                 /* we're OK to destroy the file */
1029                 eal_get_fbarray_path(path, sizeof(path), arr->name);
1030                 if (unlink(path)) {
1031                         RTE_LOG(DEBUG, EAL, "Cannot unlink fbarray: %s\n",
1032                                 strerror(errno));
1033                         rte_errno = errno;
1034                         /*
1035                          * we're still holding an exclusive lock, so drop it to
1036                          * shared.
1037                          */
1038                         eal_file_lock(fd, EAL_FLOCK_SHARED, EAL_FLOCK_RETURN);
1039
1040                         ret = -1;
1041                         goto out;
1042                 }
1043                 close(fd);
1044         }
1045         munmap(arr->data, mmap_len);
1046
1047         /* area is unmapped, remove the tailq entry */
1048         TAILQ_REMOVE(&mem_area_tailq, tmp, next);
1049         free(tmp);
1050         ret = 0;
1051
1052         /* reset the fbarray structure */
1053         memset(arr, 0, sizeof(*arr));
1054 out:
1055         rte_spinlock_unlock(&mem_area_lock);
1056         return ret;
1057 }
1058
1059 void *
1060 rte_fbarray_get(const struct rte_fbarray *arr, unsigned int idx)
1061 {
1062         void *ret = NULL;
1063         if (arr == NULL) {
1064                 rte_errno = EINVAL;
1065                 return NULL;
1066         }
1067
1068         if (idx >= arr->len) {
1069                 rte_errno = EINVAL;
1070                 return NULL;
1071         }
1072
1073         ret = RTE_PTR_ADD(arr->data, idx * arr->elt_sz);
1074
1075         return ret;
1076 }
1077
1078 int
1079 rte_fbarray_set_used(struct rte_fbarray *arr, unsigned int idx)
1080 {
1081         return set_used(arr, idx, true);
1082 }
1083
1084 int
1085 rte_fbarray_set_free(struct rte_fbarray *arr, unsigned int idx)
1086 {
1087         return set_used(arr, idx, false);
1088 }
1089
1090 int
1091 rte_fbarray_is_used(struct rte_fbarray *arr, unsigned int idx)
1092 {
1093         struct used_mask *msk;
1094         int msk_idx;
1095         uint64_t msk_bit;
1096         int ret = -1;
1097
1098         if (arr == NULL || idx >= arr->len) {
1099                 rte_errno = EINVAL;
1100                 return -1;
1101         }
1102
1103         /* prevent array from changing under us */
1104         rte_rwlock_read_lock(&arr->rwlock);
1105
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);
1109
1110         ret = (msk->data[msk_idx] & msk_bit) != 0;
1111
1112         rte_rwlock_read_unlock(&arr->rwlock);
1113
1114         return ret;
1115 }
1116
1117 static int
1118 fbarray_find(struct rte_fbarray *arr, unsigned int start, bool next, bool used)
1119 {
1120         int ret = -1;
1121
1122         if (arr == NULL || start >= arr->len) {
1123                 rte_errno = EINVAL;
1124                 return -1;
1125         }
1126
1127         /* prevent array from changing under us */
1128         rte_rwlock_read_lock(&arr->rwlock);
1129
1130         /* cheap checks to prevent doing useless work */
1131         if (!used) {
1132                 if (arr->len == arr->count) {
1133                         rte_errno = ENOSPC;
1134                         goto out;
1135                 }
1136                 if (arr->count == 0) {
1137                         ret = start;
1138                         goto out;
1139                 }
1140         } else {
1141                 if (arr->count == 0) {
1142                         rte_errno = ENOENT;
1143                         goto out;
1144                 }
1145                 if (arr->len == arr->count) {
1146                         ret = start;
1147                         goto out;
1148                 }
1149         }
1150         if (next)
1151                 ret = find_next(arr, start, used);
1152         else
1153                 ret = find_prev(arr, start, used);
1154 out:
1155         rte_rwlock_read_unlock(&arr->rwlock);
1156         return ret;
1157 }
1158
1159 int
1160 rte_fbarray_find_next_free(struct rte_fbarray *arr, unsigned int start)
1161 {
1162         return fbarray_find(arr, start, true, false);
1163 }
1164
1165 int
1166 rte_fbarray_find_next_used(struct rte_fbarray *arr, unsigned int start)
1167 {
1168         return fbarray_find(arr, start, true, true);
1169 }
1170
1171 int
1172 rte_fbarray_find_prev_free(struct rte_fbarray *arr, unsigned int start)
1173 {
1174         return fbarray_find(arr, start, false, false);
1175 }
1176
1177 int
1178 rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start)
1179 {
1180         return fbarray_find(arr, start, false, true);
1181 }
1182
1183 static int
1184 fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n,
1185                 bool next, bool used)
1186 {
1187         int ret = -1;
1188
1189         if (arr == NULL || start >= arr->len || n > arr->len || n == 0) {
1190                 rte_errno = EINVAL;
1191                 return -1;
1192         }
1193         if (next && (arr->len - start) < n) {
1194                 rte_errno = used ? ENOENT : ENOSPC;
1195                 return -1;
1196         }
1197         if (!next && start < (n - 1)) {
1198                 rte_errno = used ? ENOENT : ENOSPC;
1199                 return -1;
1200         }
1201
1202         /* prevent array from changing under us */
1203         rte_rwlock_read_lock(&arr->rwlock);
1204
1205         /* cheap checks to prevent doing useless work */
1206         if (!used) {
1207                 if (arr->len == arr->count || arr->len - arr->count < n) {
1208                         rte_errno = ENOSPC;
1209                         goto out;
1210                 }
1211                 if (arr->count == 0) {
1212                         ret = next ? start : start - n + 1;
1213                         goto out;
1214                 }
1215         } else {
1216                 if (arr->count < n) {
1217                         rte_errno = ENOENT;
1218                         goto out;
1219                 }
1220                 if (arr->count == arr->len) {
1221                         ret = next ? start : start - n + 1;
1222                         goto out;
1223                 }
1224         }
1225
1226         if (next)
1227                 ret = find_next_n(arr, start, n, used);
1228         else
1229                 ret = find_prev_n(arr, start, n, used);
1230 out:
1231         rte_rwlock_read_unlock(&arr->rwlock);
1232         return ret;
1233 }
1234
1235 int
1236 rte_fbarray_find_next_n_free(struct rte_fbarray *arr, unsigned int start,
1237                 unsigned int n)
1238 {
1239         return fbarray_find_n(arr, start, n, true, false);
1240 }
1241
1242 int
1243 rte_fbarray_find_next_n_used(struct rte_fbarray *arr, unsigned int start,
1244                 unsigned int n)
1245 {
1246         return fbarray_find_n(arr, start, n, true, true);
1247 }
1248
1249 int
1250 rte_fbarray_find_prev_n_free(struct rte_fbarray *arr, unsigned int start,
1251                 unsigned int n)
1252 {
1253         return fbarray_find_n(arr, start, n, false, false);
1254 }
1255
1256 int
1257 rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start,
1258                 unsigned int n)
1259 {
1260         return fbarray_find_n(arr, start, n, false, true);
1261 }
1262
1263 static int
1264 fbarray_find_contig(struct rte_fbarray *arr, unsigned int start, bool next,
1265                 bool used)
1266 {
1267         int ret = -1;
1268
1269         if (arr == NULL || start >= arr->len) {
1270                 rte_errno = EINVAL;
1271                 return -1;
1272         }
1273
1274         /* prevent array from changing under us */
1275         rte_rwlock_read_lock(&arr->rwlock);
1276
1277         /* cheap checks to prevent doing useless work */
1278         if (used) {
1279                 if (arr->count == 0) {
1280                         ret = 0;
1281                         goto out;
1282                 }
1283                 if (next && arr->count == arr->len) {
1284                         ret = arr->len - start;
1285                         goto out;
1286                 }
1287                 if (!next && arr->count == arr->len) {
1288                         ret = start + 1;
1289                         goto out;
1290                 }
1291         } else {
1292                 if (arr->len == arr->count) {
1293                         ret = 0;
1294                         goto out;
1295                 }
1296                 if (next && arr->count == 0) {
1297                         ret = arr->len - start;
1298                         goto out;
1299                 }
1300                 if (!next && arr->count == 0) {
1301                         ret = start + 1;
1302                         goto out;
1303                 }
1304         }
1305
1306         if (next)
1307                 ret = find_contig(arr, start, used);
1308         else
1309                 ret = find_rev_contig(arr, start, used);
1310 out:
1311         rte_rwlock_read_unlock(&arr->rwlock);
1312         return ret;
1313 }
1314
1315 static int
1316 fbarray_find_biggest(struct rte_fbarray *arr, unsigned int start, bool used,
1317                 bool rev)
1318 {
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);
1323
1324         if (arr == NULL || start >= arr->len) {
1325                 rte_errno = EINVAL;
1326                 return -1;
1327         }
1328         /* the other API calls already do their fair share of cheap checks, so
1329          * no need to do them here.
1330          */
1331
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.
1335          */
1336         rte_rwlock_read_lock(&arr->rwlock);
1337
1338         /* pick out appropriate functions */
1339         if (used) {
1340                 if (rev) {
1341                         find_func = rte_fbarray_find_prev_used;
1342                         find_contig_func = rte_fbarray_find_rev_contig_used;
1343                 } else {
1344                         find_func = rte_fbarray_find_next_used;
1345                         find_contig_func = rte_fbarray_find_contig_used;
1346                 }
1347         } else {
1348                 if (rev) {
1349                         find_func = rte_fbarray_find_prev_free;
1350                         find_contig_func = rte_fbarray_find_rev_contig_free;
1351                 } else {
1352                         find_func = rte_fbarray_find_next_free;
1353                         find_contig_func = rte_fbarray_find_contig_free;
1354                 }
1355         }
1356
1357         cur_idx = start;
1358         biggest_idx = -1; /* default is error */
1359         biggest_len = 0;
1360         for (;;) {
1361                 cur_idx = find_func(arr, cur_idx);
1362
1363                 /* block found, check its length */
1364                 if (cur_idx >= 0) {
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;
1370
1371                         if (cur_len > biggest_len) {
1372                                 biggest_idx = cur_idx;
1373                                 biggest_len = cur_len;
1374                         }
1375                         cur_idx = next_idx;
1376                         /* in reverse mode, next_idx may be -1 if chunk started
1377                          * at array beginning. this means there's no more work
1378                          * to do.
1379                          */
1380                         if (cur_idx < 0)
1381                                 break;
1382                 } else {
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.
1386                          */
1387                         rte_errno = 0;
1388                         break;
1389                 }
1390         }
1391         /* if we didn't find anything at all, set rte_errno */
1392         if (biggest_idx < 0)
1393                 rte_errno = used ? ENOENT : ENOSPC;
1394
1395         rte_rwlock_read_unlock(&arr->rwlock);
1396         return biggest_idx;
1397 }
1398
1399 int
1400 rte_fbarray_find_biggest_free(struct rte_fbarray *arr, unsigned int start)
1401 {
1402         return fbarray_find_biggest(arr, start, false, false);
1403 }
1404
1405 int
1406 rte_fbarray_find_biggest_used(struct rte_fbarray *arr, unsigned int start)
1407 {
1408         return fbarray_find_biggest(arr, start, true, false);
1409 }
1410
1411 int
1412 rte_fbarray_find_rev_biggest_free(struct rte_fbarray *arr, unsigned int start)
1413 {
1414         return fbarray_find_biggest(arr, start, false, true);
1415 }
1416
1417 int
1418 rte_fbarray_find_rev_biggest_used(struct rte_fbarray *arr, unsigned int start)
1419 {
1420         return fbarray_find_biggest(arr, start, true, true);
1421 }
1422
1423
1424 int
1425 rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start)
1426 {
1427         return fbarray_find_contig(arr, start, true, false);
1428 }
1429
1430 int
1431 rte_fbarray_find_contig_used(struct rte_fbarray *arr, unsigned int start)
1432 {
1433         return fbarray_find_contig(arr, start, true, true);
1434 }
1435
1436 int
1437 rte_fbarray_find_rev_contig_free(struct rte_fbarray *arr, unsigned int start)
1438 {
1439         return fbarray_find_contig(arr, start, false, false);
1440 }
1441
1442 int
1443 rte_fbarray_find_rev_contig_used(struct rte_fbarray *arr, unsigned int start)
1444 {
1445         return fbarray_find_contig(arr, start, false, true);
1446 }
1447
1448 int
1449 rte_fbarray_find_idx(const struct rte_fbarray *arr, const void *elt)
1450 {
1451         void *end;
1452         int ret = -1;
1453
1454         /*
1455          * no need to synchronize as it doesn't matter if underlying data
1456          * changes - we're doing pointer arithmetic here.
1457          */
1458
1459         if (arr == NULL || elt == NULL) {
1460                 rte_errno = EINVAL;
1461                 return -1;
1462         }
1463         end = RTE_PTR_ADD(arr->data, arr->elt_sz * arr->len);
1464         if (elt < arr->data || elt >= end) {
1465                 rte_errno = EINVAL;
1466                 return -1;
1467         }
1468
1469         ret = RTE_PTR_DIFF(elt, arr->data) / arr->elt_sz;
1470
1471         return ret;
1472 }
1473
1474 void
1475 rte_fbarray_dump_metadata(struct rte_fbarray *arr, FILE *f)
1476 {
1477         struct used_mask *msk;
1478         unsigned int i;
1479
1480         if (arr == NULL || f == NULL) {
1481                 rte_errno = EINVAL;
1482                 return;
1483         }
1484
1485         if (fully_validate(arr->name, arr->elt_sz, arr->len)) {
1486                 fprintf(f, "Invalid file-backed array\n");
1487                 goto out;
1488         }
1489
1490         /* prevent array from changing under us */
1491         rte_rwlock_read_lock(&arr->rwlock);
1492
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);
1496
1497         msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
1498
1499         for (i = 0; i < msk->n_masks; i++)
1500                 fprintf(f, "msk idx %i: 0x%016" PRIx64 "\n", i, msk->data[i]);
1501 out:
1502         rte_rwlock_read_unlock(&arr->rwlock);
1503 }