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