lib/librte_eal/common/eal_common_fbarray.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2017-2018 Intel Corporation
   3  */
   4
   5 #include <inttypes.h>
   6 #include <limits.h>
   7 #include <sys/mman.h>
   8 #include <stdint.h>
   9 #include <errno.h>
  10 #include <sys/file.h>
  11 #include <string.h>
  12
  13 #include <rte_common.h>
  14 #include <rte_log.h>
  15 #include <rte_errno.h>
  16 #include <rte_spinlock.h>
  17 #include <rte_tailq.h>
  18
  19 #include "eal_filesystem.h"
  20 #include "eal_private.h"
  21
  22 #include "rte_fbarray.h"
  23
  24 #define MASK_SHIFT 6ULL
  25 #define MASK_ALIGN (1ULL << MASK_SHIFT)
  26 #define MASK_LEN_TO_IDX(x) ((x) >> MASK_SHIFT)
  27 #define MASK_LEN_TO_MOD(x) ((x) - RTE_ALIGN_FLOOR(x, MASK_ALIGN))
  28 #define MASK_GET_IDX(idx, mod) ((idx << MASK_SHIFT) + mod)
  29
  30 /*
  31  * This is a mask that is always stored at the end of array, to provide fast
  32  * way of finding free/used spots without looping through each element.
  33  */
  34
  35 struct used_mask {
  36         unsigned int n_masks;
  37         uint64_t data[];
  38 };
  39
  40 static size_t
  41 calc_mask_size(unsigned int len)
  42 {
  43         /* mask must be multiple of MASK_ALIGN, even though length of array
  44          * itself may not be aligned on that boundary.
  45          */
  46         len = RTE_ALIGN_CEIL(len, MASK_ALIGN);
  47         return sizeof(struct used_mask) +
  48                         sizeof(uint64_t) * MASK_LEN_TO_IDX(len);
  49 }
  50
  51 static size_t
  52 calc_data_size(size_t page_sz, unsigned int elt_sz, unsigned int len)
  53 {
  54         size_t data_sz = elt_sz * len;
  55         size_t msk_sz = calc_mask_size(len);
  56         return RTE_ALIGN_CEIL(data_sz + msk_sz, page_sz);
  57 }
  58
  59 static struct used_mask *
  60 get_used_mask(void *data, unsigned int elt_sz, unsigned int len)
  61 {
  62         return (struct used_mask *) RTE_PTR_ADD(data, elt_sz * len);
  63 }
  64
  65 static int
  66 resize_and_map(int fd, void *addr, size_t len)
  67 {
  68         char path[PATH_MAX];
  69         void *map_addr;
  70
  71         if (ftruncate(fd, len)) {
  72                 RTE_LOG(ERR, EAL, "Cannot truncate %s\n", path);
  73                 /* pass errno up the chain */
  74                 rte_errno = errno;
  75                 return -1;
  76         }
  77
  78         map_addr = mmap(addr, len, PROT_READ | PROT_WRITE,
  79                         MAP_SHARED | MAP_FIXED, fd, 0);
  80         if (map_addr != addr) {
  81                 RTE_LOG(ERR, EAL, "mmap() failed: %s\n", strerror(errno));
  82                 /* pass errno up the chain */
  83                 rte_errno = errno;
  84                 return -1;
  85         }
  86         return 0;
  87 }
  88
  89 static int
  90 find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
  91             bool used)
  92 {
  93         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
  94                         arr->len);
  95         unsigned int msk_idx, lookahead_idx, first, first_mod;
  96         unsigned int last, last_mod;
  97         uint64_t last_msk, ignore_msk;
  98
  99         /*
 100          * mask only has granularity of MASK_ALIGN, but start may not be aligned
 101          * on that boundary, so construct a special mask to exclude anything we
 102          * don't want to see to avoid confusing ctz.
 103          */
 104         first = MASK_LEN_TO_IDX(start);
 105         first_mod = MASK_LEN_TO_MOD(start);
 106         ignore_msk = ~((1ULL << first_mod) - 1);
 107
 108         /* array length may not be aligned, so calculate ignore mask for last
 109          * mask index.
 110          */
 111         last = MASK_LEN_TO_IDX(arr->len);
 112         last_mod = MASK_LEN_TO_MOD(arr->len);
 113         last_msk = ~(-1ULL << last_mod);
 114
 115         for (msk_idx = first; msk_idx < msk->n_masks; msk_idx++) {
 116                 uint64_t cur_msk, lookahead_msk;
 117                 unsigned int run_start, clz, left;
 118                 bool found = false;
 119                 /*
 120                  * The process of getting n consecutive bits for arbitrary n is
 121                  * a bit involved, but here it is in a nutshell:
 122                  *
 123                  *  1. let n be the number of consecutive bits we're looking for
 124                  *  2. check if n can fit in one mask, and if so, do n-1
 125                  *     rshift-ands to see if there is an appropriate run inside
 126                  *     our current mask
 127                  *    2a. if we found a run, bail out early
 128                  *    2b. if we didn't find a run, proceed
 129                  *  3. invert the mask and count leading zeroes (that is, count
 130                  *     how many consecutive set bits we had starting from the
 131                  *     end of current mask) as k
 132                  *    3a. if k is 0, continue to next mask
 133                  *    3b. if k is not 0, we have a potential run
 134                  *  4. to satisfy our requirements, next mask must have n-k
 135                  *     consecutive set bits right at the start, so we will do
 136                  *     (n-k-1) rshift-ands and check if first bit is set.
 137                  *
 138                  * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until
 139                  * we either run out of masks, lose the run, or find what we
 140                  * were looking for.
 141                  */
 142                 cur_msk = msk->data[msk_idx];
 143                 left = n;
 144
 145                 /* if we're looking for free spaces, invert the mask */
 146                 if (!used)
 147                         cur_msk = ~cur_msk;
 148
 149                 /* combine current ignore mask with last index ignore mask */
 150                 if (msk_idx == last)
 151                         ignore_msk |= last_msk;
 152
 153                 /* if we have an ignore mask, ignore once */
 154                 if (ignore_msk) {
 155                         cur_msk &= ignore_msk;
 156                         ignore_msk = 0;
 157                 }
 158
 159                 /* if n can fit in within a single mask, do a search */
 160                 if (n <= MASK_ALIGN) {
 161                         uint64_t tmp_msk = cur_msk;
 162                         unsigned int s_idx;
 163                         for (s_idx = 0; s_idx < n - 1; s_idx++)
 164                                 tmp_msk &= tmp_msk >> 1ULL;
 165                         /* we found what we were looking for */
 166                         if (tmp_msk != 0) {
 167                                 run_start = __builtin_ctzll(tmp_msk);
 168                                 return MASK_GET_IDX(msk_idx, run_start);
 169                         }
 170                 }
 171
 172                 /*
 173                  * we didn't find our run within the mask, or n > MASK_ALIGN,
 174                  * so we're going for plan B.
 175                  */
 176
 177                 /* count leading zeroes on inverted mask */
 178                 if (~cur_msk == 0)
 179                         clz = sizeof(cur_msk) * 8;
 180                 else
 181                         clz = __builtin_clzll(~cur_msk);
 182
 183                 /* if there aren't any runs at the end either, just continue */
 184                 if (clz == 0)
 185                         continue;
 186
 187                 /* we have a partial run at the end, so try looking ahead */
 188                 run_start = MASK_ALIGN - clz;
 189                 left -= clz;
 190
 191                 for (lookahead_idx = msk_idx + 1; lookahead_idx < msk->n_masks;
 192                                 lookahead_idx++) {
 193                         unsigned int s_idx, need;
 194                         lookahead_msk = msk->data[lookahead_idx];
 195
 196                         /* if we're looking for free space, invert the mask */
 197                         if (!used)
 198                                 lookahead_msk = ~lookahead_msk;
 199
 200                         /* figure out how many consecutive bits we need here */
 201                         need = RTE_MIN(left, MASK_ALIGN);
 202
 203                         for (s_idx = 0; s_idx < need - 1; s_idx++)
 204                                 lookahead_msk &= lookahead_msk >> 1ULL;
 205
 206                         /* if first bit is not set, we've lost the run */
 207                         if ((lookahead_msk & 1) == 0) {
 208                                 /*
 209                                  * we've scanned this far, so we know there are
 210                                  * no runs in the space we've lookahead-scanned
 211                                  * as well, so skip that on next iteration.
 212                                  */
 213                                 ignore_msk = ~((1ULL << need) - 1);
 214                                 msk_idx = lookahead_idx;
 215                                 break;
 216                         }
 217
 218                         left -= need;
 219
 220                         /* check if we've found what we were looking for */
 221                         if (left == 0) {
 222                                 found = true;
 223                                 break;
 224                         }
 225                 }
 226
 227                 /* we didn't find anything, so continue */
 228                 if (!found)
 229                         continue;
 230
 231                 return MASK_GET_IDX(msk_idx, run_start);
 232         }
 233         /* we didn't find anything */
 234         rte_errno = used ? ENOENT : ENOSPC;
 235         return -1;
 236 }
 237
 238 static int
 239 find_next(const struct rte_fbarray *arr, unsigned int start, bool used)
 240 {
 241         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 242                         arr->len);
 243         unsigned int idx, first, first_mod;
 244         unsigned int last, last_mod;
 245         uint64_t last_msk, ignore_msk;
 246
 247         /*
 248          * mask only has granularity of MASK_ALIGN, but start may not be aligned
 249          * on that boundary, so construct a special mask to exclude anything we
 250          * don't want to see to avoid confusing ctz.
 251          */
 252         first = MASK_LEN_TO_IDX(start);
 253         first_mod = MASK_LEN_TO_MOD(start);
 254         ignore_msk = ~((1ULL << first_mod) - 1ULL);
 255
 256         /* array length may not be aligned, so calculate ignore mask for last
 257          * mask index.
 258          */
 259         last = MASK_LEN_TO_IDX(arr->len);
 260         last_mod = MASK_LEN_TO_MOD(arr->len);
 261         last_msk = ~(-(1ULL) << last_mod);
 262
 263         for (idx = first; idx < msk->n_masks; idx++) {
 264                 uint64_t cur = msk->data[idx];
 265                 int found;
 266
 267                 /* if we're looking for free entries, invert mask */
 268                 if (!used)
 269                         cur = ~cur;
 270
 271                 if (idx == last)
 272                         cur &= last_msk;
 273
 274                 /* ignore everything before start on first iteration */
 275                 if (idx == first)
 276                         cur &= ignore_msk;
 277
 278                 /* check if we have any entries */
 279                 if (cur == 0)
 280                         continue;
 281
 282                 /*
 283                  * find first set bit - that will correspond to whatever it is
 284                  * that we're looking for.
 285                  */
 286                 found = __builtin_ctzll(cur);
 287                 return MASK_GET_IDX(idx, found);
 288         }
 289         /* we didn't find anything */
 290         rte_errno = used ? ENOENT : ENOSPC;
 291         return -1;
 292 }
 293
 294 static int
 295 find_contig(const struct rte_fbarray *arr, unsigned int start, bool used)
 296 {
 297         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 298                         arr->len);
 299         unsigned int idx, first, first_mod;
 300         unsigned int last, last_mod;
 301         uint64_t last_msk;
 302         unsigned int need_len, result = 0;
 303
 304         /* array length may not be aligned, so calculate ignore mask for last
 305          * mask index.
 306          */
 307         last = MASK_LEN_TO_IDX(arr->len);
 308         last_mod = MASK_LEN_TO_MOD(arr->len);
 309         last_msk = ~(-(1ULL) << last_mod);
 310
 311         first = MASK_LEN_TO_IDX(start);
 312         first_mod = MASK_LEN_TO_MOD(start);
 313         for (idx = first; idx < msk->n_masks; idx++, result += need_len) {
 314                 uint64_t cur = msk->data[idx];
 315                 unsigned int run_len;
 316
 317                 need_len = MASK_ALIGN;
 318
 319                 /* if we're looking for free entries, invert mask */
 320                 if (!used)
 321                         cur = ~cur;
 322
 323                 /* if this is last mask, ignore everything after last bit */
 324                 if (idx == last)
 325                         cur &= last_msk;
 326
 327                 /* ignore everything before start on first iteration */
 328                 if (idx == first) {
 329                         cur >>= first_mod;
 330                         /* at the start, we don't need the full mask len */
 331                         need_len -= first_mod;
 332                 }
 333
 334                 /* we will be looking for zeroes, so invert the mask */
 335                 cur = ~cur;
 336
 337                 /* if mask is zero, we have a complete run */
 338                 if (cur == 0)
 339                         continue;
 340
 341                 /*
 342                  * see if current run ends before mask end.
 343                  */
 344                 run_len = __builtin_ctzll(cur);
 345
 346                 /* add however many zeroes we've had in the last run and quit */
 347                 if (run_len < need_len) {
 348                         result += run_len;
 349                         break;
 350                 }
 351         }
 352         return result;
 353 }
 354
 355 static int
 356 find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
 357                 bool used)
 358 {
 359         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 360                         arr->len);
 361         unsigned int msk_idx, lookbehind_idx, first, first_mod;
 362         uint64_t ignore_msk;
 363
 364         /*
 365          * mask only has granularity of MASK_ALIGN, but start may not be aligned
 366          * on that boundary, so construct a special mask to exclude anything we
 367          * don't want to see to avoid confusing ctz.
 368          */
 369         first = MASK_LEN_TO_IDX(start);
 370         first_mod = MASK_LEN_TO_MOD(start);
 371         /* we're going backwards, so mask must start from the top */
 372         ignore_msk = first_mod == MASK_ALIGN - 1 ?
 373                                 -1ULL : /* prevent overflow */
 374                                 ~(-1ULL << (first_mod + 1));
 375
 376         /* go backwards, include zero */
 377         msk_idx = first;
 378         do {
 379                 uint64_t cur_msk, lookbehind_msk;
 380                 unsigned int run_start, run_end, ctz, left;
 381                 bool found = false;
 382                 /*
 383                  * The process of getting n consecutive bits from the top for
 384                  * arbitrary n is a bit involved, but here it is in a nutshell:
 385                  *
 386                  *  1. let n be the number of consecutive bits we're looking for
 387                  *  2. check if n can fit in one mask, and if so, do n-1
 388                  *     lshift-ands to see if there is an appropriate run inside
 389                  *     our current mask
 390                  *    2a. if we found a run, bail out early
 391                  *    2b. if we didn't find a run, proceed
 392                  *  3. invert the mask and count trailing zeroes (that is, count
 393                  *     how many consecutive set bits we had starting from the
 394                  *     start of current mask) as k
 395                  *    3a. if k is 0, continue to next mask
 396                  *    3b. if k is not 0, we have a potential run
 397                  *  4. to satisfy our requirements, next mask must have n-k
 398                  *     consecutive set bits at the end, so we will do (n-k-1)
 399                  *     lshift-ands and check if last bit is set.
 400                  *
 401                  * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until
 402                  * we either run out of masks, lose the run, or find what we
 403                  * were looking for.
 404                  */
 405                 cur_msk = msk->data[msk_idx];
 406                 left = n;
 407
 408                 /* if we're looking for free spaces, invert the mask */
 409                 if (!used)
 410                         cur_msk = ~cur_msk;
 411
 412                 /* if we have an ignore mask, ignore once */
 413                 if (ignore_msk) {
 414                         cur_msk &= ignore_msk;
 415                         ignore_msk = 0;
 416                 }
 417
 418                 /* if n can fit in within a single mask, do a search */
 419                 if (n <= MASK_ALIGN) {
 420                         uint64_t tmp_msk = cur_msk;
 421                         unsigned int s_idx;
 422                         for (s_idx = 0; s_idx < n - 1; s_idx++)
 423                                 tmp_msk &= tmp_msk << 1ULL;
 424                         /* we found what we were looking for */
 425                         if (tmp_msk != 0) {
 426                                 /* clz will give us offset from end of mask, and
 427                                  * we only get the end of our run, not start,
 428                                  * so adjust result to point to where start
 429                                  * would have been.
 430                                  */
 431                                 run_start = MASK_ALIGN -
 432                                                 __builtin_clzll(tmp_msk) - n;
 433                                 return MASK_GET_IDX(msk_idx, run_start);
 434                         }
 435                 }
 436
 437                 /*
 438                  * we didn't find our run within the mask, or n > MASK_ALIGN,
 439                  * so we're going for plan B.
 440                  */
 441
 442                 /* count trailing zeroes on inverted mask */
 443                 if (~cur_msk == 0)
 444                         ctz = sizeof(cur_msk) * 8;
 445                 else
 446                         ctz = __builtin_ctzll(~cur_msk);
 447
 448                 /* if there aren't any runs at the start either, just
 449                  * continue
 450                  */
 451                 if (ctz == 0)
 452                         continue;
 453
 454                 /* we have a partial run at the start, so try looking behind */
 455                 run_end = MASK_GET_IDX(msk_idx, ctz);
 456                 left -= ctz;
 457
 458                 /* go backwards, include zero */
 459                 lookbehind_idx = msk_idx - 1;
 460
 461                 /* we can't lookbehind as we've run out of masks, so stop */
 462                 if (msk_idx == 0)
 463                         break;
 464
 465                 do {
 466                         const uint64_t last_bit = 1ULL << (MASK_ALIGN - 1);
 467                         unsigned int s_idx, need;
 468
 469                         lookbehind_msk = msk->data[lookbehind_idx];
 470
 471                         /* if we're looking for free space, invert the mask */
 472                         if (!used)
 473                                 lookbehind_msk = ~lookbehind_msk;
 474
 475                         /* figure out how many consecutive bits we need here */
 476                         need = RTE_MIN(left, MASK_ALIGN);
 477
 478                         for (s_idx = 0; s_idx < need - 1; s_idx++)
 479                                 lookbehind_msk &= lookbehind_msk << 1ULL;
 480
 481                         /* if last bit is not set, we've lost the run */
 482                         if ((lookbehind_msk & last_bit) == 0) {
 483                                 /*
 484                                  * we've scanned this far, so we know there are
 485                                  * no runs in the space we've lookbehind-scanned
 486                                  * as well, so skip that on next iteration.
 487                                  */
 488                                 ignore_msk = -1ULL << need;
 489                                 msk_idx = lookbehind_idx;
 490                                 break;
 491                         }
 492
 493                         left -= need;
 494
 495                         /* check if we've found what we were looking for */
 496                         if (left == 0) {
 497                                 found = true;
 498                                 break;
 499                         }
 500                 } while ((lookbehind_idx--) != 0); /* decrement after check to
 501                                                     * include zero
 502                                                     */
 503
 504                 /* we didn't find anything, so continue */
 505                 if (!found)
 506                         continue;
 507
 508                 /* we've found what we were looking for, but we only know where
 509                  * the run ended, so calculate start position.
 510                  */
 511                 return run_end - n;
 512         } while (msk_idx-- != 0); /* decrement after check to include zero */
 513         /* we didn't find anything */
 514         rte_errno = used ? ENOENT : ENOSPC;
 515         return -1;
 516 }
 517
 518 static int
 519 find_prev(const struct rte_fbarray *arr, unsigned int start, bool used)
 520 {
 521         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 522                         arr->len);
 523         unsigned int idx, first, first_mod;
 524         uint64_t ignore_msk;
 525
 526         /*
 527          * mask only has granularity of MASK_ALIGN, but start may not be aligned
 528          * on that boundary, so construct a special mask to exclude anything we
 529          * don't want to see to avoid confusing clz.
 530          */
 531         first = MASK_LEN_TO_IDX(start);
 532         first_mod = MASK_LEN_TO_MOD(start);
 533         /* we're going backwards, so mask must start from the top */
 534         ignore_msk = first_mod == MASK_ALIGN - 1 ?
 535                                 -1ULL : /* prevent overflow */
 536                                 ~(-1ULL << (first_mod + 1));
 537
 538         /* go backwards, include zero */
 539         idx = first;
 540         do {
 541                 uint64_t cur = msk->data[idx];
 542                 int found;
 543
 544                 /* if we're looking for free entries, invert mask */
 545                 if (!used)
 546                         cur = ~cur;
 547
 548                 /* ignore everything before start on first iteration */
 549                 if (idx == first)
 550                         cur &= ignore_msk;
 551
 552                 /* check if we have any entries */
 553                 if (cur == 0)
 554                         continue;
 555
 556                 /*
 557                  * find last set bit - that will correspond to whatever it is
 558                  * that we're looking for. we're counting trailing zeroes, thus
 559                  * the value we get is counted from end of mask, so calculate
 560                  * position from start of mask.
 561                  */
 562                 found = MASK_ALIGN - __builtin_clzll(cur) - 1;
 563
 564                 return MASK_GET_IDX(idx, found);
 565         } while (idx-- != 0); /* decrement after check  to include zero*/
 566
 567         /* we didn't find anything */
 568         rte_errno = used ? ENOENT : ENOSPC;
 569         return -1;
 570 }
 571
 572 static int
 573 find_rev_contig(const struct rte_fbarray *arr, unsigned int start, bool used)
 574 {
 575         const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
 576                         arr->len);
 577         unsigned int idx, first, first_mod;
 578         unsigned int need_len, result = 0;
 579
 580         first = MASK_LEN_TO_IDX(start);
 581         first_mod = MASK_LEN_TO_MOD(start);
 582
 583         /* go backwards, include zero */
 584         idx = first;
 585         do {
 586                 uint64_t cur = msk->data[idx];
 587                 unsigned int run_len;
 588
 589                 need_len = MASK_ALIGN;
 590
 591                 /* if we're looking for free entries, invert mask */
 592                 if (!used)
 593                         cur = ~cur;
 594
 595                 /* ignore everything after start on first iteration */
 596                 if (idx == first) {
 597                         unsigned int end_len = MASK_ALIGN - first_mod - 1;
 598                         cur <<= end_len;
 599                         /* at the start, we don't need the full mask len */
 600                         need_len -= end_len;
 601                 }
 602
 603                 /* we will be looking for zeroes, so invert the mask */
 604                 cur = ~cur;
 605
 606                 /* if mask is zero, we have a complete run */
 607                 if (cur == 0)
 608                         goto endloop;
 609
 610                 /*
 611                  * see where run ends, starting from the end.
 612                  */
 613                 run_len = __builtin_clzll(cur);
 614
 615                 /* add however many zeroes we've had in the last run and quit */
 616                 if (run_len < need_len) {
 617                         result += run_len;
 618                         break;
 619                 }
 620 endloop:
 621                 result += need_len;
 622         } while (idx-- != 0); /* decrement after check to include zero */
 623         return result;
 624 }
 625
 626 static int
 627 set_used(struct rte_fbarray *arr, unsigned int idx, bool used)
 628 {
 629         struct used_mask *msk;
 630         uint64_t msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);
 631         unsigned int msk_idx = MASK_LEN_TO_IDX(idx);
 632         bool already_used;
 633         int ret = -1;
 634
 635         if (arr == NULL || idx >= arr->len) {
 636                 rte_errno = EINVAL;
 637                 return -1;
 638         }
 639         msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
 640         ret = 0;
 641
 642         /* prevent array from changing under us */
 643         rte_rwlock_write_lock(&arr->rwlock);
 644
 645         already_used = (msk->data[msk_idx] & msk_bit) != 0;
 646
 647         /* nothing to be done */
 648         if (used == already_used)
 649                 goto out;
 650
 651         if (used) {
 652                 msk->data[msk_idx] |= msk_bit;
 653                 arr->count++;
 654         } else {
 655                 msk->data[msk_idx] &= ~msk_bit;
 656                 arr->count--;
 657         }
 658 out:
 659         rte_rwlock_write_unlock(&arr->rwlock);
 660
 661         return ret;
 662 }
 663
 664 static int
 665 fully_validate(const char *name, unsigned int elt_sz, unsigned int len)
 666 {
 667         if (name == NULL || elt_sz == 0 || len == 0 || len > INT_MAX) {
 668                 rte_errno = EINVAL;
 669                 return -1;
 670         }
 671
 672         if (strnlen(name, RTE_FBARRAY_NAME_LEN) == RTE_FBARRAY_NAME_LEN) {
 673                 rte_errno = ENAMETOOLONG;
 674                 return -1;
 675         }
 676         return 0;
 677 }
 678
 679 int __rte_experimental
 680 rte_fbarray_init(struct rte_fbarray *arr, const char *name, unsigned int len,
 681                 unsigned int elt_sz)
 682 {
 683         size_t page_sz, mmap_len;
 684         char path[PATH_MAX];
 685         struct used_mask *msk;
 686         void *data = NULL;
 687         int fd = -1;
 688
 689         if (arr == NULL) {
 690                 rte_errno = EINVAL;
 691                 return -1;
 692         }
 693
 694         if (fully_validate(name, elt_sz, len))
 695                 return -1;
 696
 697         page_sz = sysconf(_SC_PAGESIZE);
 698         if (page_sz == (size_t)-1)
 699                 goto fail;
 700
 701         /* calculate our memory limits */
 702         mmap_len = calc_data_size(page_sz, elt_sz, len);
 703
 704         data = eal_get_virtual_area(NULL, &mmap_len, page_sz, 0, 0);
 705         if (data == NULL)
 706                 goto fail;
 707
 708         if (internal_config.no_shconf) {
 709                 /* remap virtual area as writable */
 710                 void *new_data = mmap(data, mmap_len, PROT_READ | PROT_WRITE,
 711                                 MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
 712                 if (new_data == MAP_FAILED) {
 713                         RTE_LOG(DEBUG, EAL, "%s(): couldn't remap anonymous memory: %s\n",
 714                                         __func__, strerror(errno));
 715                         goto fail;
 716                 }
 717         } else {
 718                 eal_get_fbarray_path(path, sizeof(path), name);
 719
 720                 /*
 721                  * Each fbarray is unique to process namespace, i.e. the
 722                  * filename depends on process prefix. Try to take out a lock
 723                  * and see if we succeed. If we don't, someone else is using it
 724                  * already.
 725                  */
 726                 fd = open(path, O_CREAT | O_RDWR, 0600);
 727                 if (fd < 0) {
 728                         RTE_LOG(DEBUG, EAL, "%s(): couldn't open %s: %s\n",
 729                                         __func__, path, strerror(errno));
 730                         rte_errno = errno;
 731                         goto fail;
 732                 } else if (flock(fd, LOCK_EX | LOCK_NB)) {
 733                         RTE_LOG(DEBUG, EAL, "%s(): couldn't lock %s: %s\n",
 734                                         __func__, path, strerror(errno));
 735                         rte_errno = EBUSY;
 736                         goto fail;
 737                 }
 738
 739                 /* take out a non-exclusive lock, so that other processes could
 740                  * still attach to it, but no other process could reinitialize
 741                  * it.
 742                  */
 743                 if (flock(fd, LOCK_SH | LOCK_NB)) {
 744                         rte_errno = errno;
 745                         goto fail;
 746                 }
 747
 748                 if (resize_and_map(fd, data, mmap_len))
 749                         goto fail;
 750
 751                 /* we've mmap'ed the file, we can now close the fd */
 752                 close(fd);
 753         }
 754
 755         /* initialize the data */
 756         memset(data, 0, mmap_len);
 757
 758         /* populate data structure */
 759         strlcpy(arr->name, name, sizeof(arr->name));
 760         arr->data = data;
 761         arr->len = len;
 762         arr->elt_sz = elt_sz;
 763         arr->count = 0;
 764
 765         msk = get_used_mask(data, elt_sz, len);
 766         msk->n_masks = MASK_LEN_TO_IDX(RTE_ALIGN_CEIL(len, MASK_ALIGN));
 767
 768         rte_rwlock_init(&arr->rwlock);
 769
 770         return 0;
 771 fail:
 772         if (data)
 773                 munmap(data, mmap_len);
 774         if (fd >= 0)
 775                 close(fd);
 776         return -1;
 777 }
 778
 779 int __rte_experimental
 780 rte_fbarray_attach(struct rte_fbarray *arr)
 781 {
 782         size_t page_sz, mmap_len;
 783         char path[PATH_MAX];
 784         void *data = NULL;
 785         int fd = -1;
 786
 787         if (arr == NULL) {
 788                 rte_errno = EINVAL;
 789                 return -1;
 790         }
 791
 792         /*
 793          * we don't need to synchronize attach as two values we need (element
 794          * size and array length) are constant for the duration of life of
 795          * the array, so the parts we care about will not race.
 796          */
 797
 798         if (fully_validate(arr->name, arr->elt_sz, arr->len))
 799                 return -1;
 800
 801         page_sz = sysconf(_SC_PAGESIZE);
 802         if (page_sz == (size_t)-1)
 803                 goto fail;
 804
 805         mmap_len = calc_data_size(page_sz, arr->elt_sz, arr->len);
 806
 807         data = eal_get_virtual_area(arr->data, &mmap_len, page_sz, 0, 0);
 808         if (data == NULL)
 809                 goto fail;
 810
 811         eal_get_fbarray_path(path, sizeof(path), arr->name);
 812
 813         fd = open(path, O_RDWR);
 814         if (fd < 0) {
 815                 rte_errno = errno;
 816                 goto fail;
 817         }
 818
 819         /* lock the file, to let others know we're using it */
 820         if (flock(fd, LOCK_SH | LOCK_NB)) {
 821                 rte_errno = errno;
 822                 goto fail;
 823         }
 824
 825         if (resize_and_map(fd, data, mmap_len))
 826                 goto fail;
 827
 828         close(fd);
 829
 830         /* we're done */
 831
 832         return 0;
 833 fail:
 834         if (data)
 835                 munmap(data, mmap_len);
 836         if (fd >= 0)
 837                 close(fd);
 838         return -1;
 839 }
 840
 841 int __rte_experimental
 842 rte_fbarray_detach(struct rte_fbarray *arr)
 843 {
 844         if (arr == NULL) {
 845                 rte_errno = EINVAL;
 846                 return -1;
 847         }
 848
 849         /*
 850          * we don't need to synchronize detach as two values we need (element
 851          * size and total capacity) are constant for the duration of life of
 852          * the array, so the parts we care about will not race. if the user is
 853          * detaching while doing something else in the same process, we can't
 854          * really do anything about it, things will blow up either way.
 855          */
 856
 857         size_t page_sz = sysconf(_SC_PAGESIZE);
 858
 859         if (page_sz == (size_t)-1)
 860                 return -1;
 861
 862         /* this may already be unmapped (e.g. repeated call from previously
 863          * failed destroy(), but this is on user, we can't (easily) know if this
 864          * is still mapped.
 865          */
 866         munmap(arr->data, calc_data_size(page_sz, arr->elt_sz, arr->len));
 867
 868         return 0;
 869 }
 870
 871 int __rte_experimental
 872 rte_fbarray_destroy(struct rte_fbarray *arr)
 873 {
 874         int fd, ret;
 875         char path[PATH_MAX];
 876
 877         ret = rte_fbarray_detach(arr);
 878         if (ret)
 879                 return ret;
 880
 881         /* try deleting the file */
 882         eal_get_fbarray_path(path, sizeof(path), arr->name);
 883
 884         fd = open(path, O_RDONLY);
 885         if (fd < 0) {
 886                 RTE_LOG(ERR, EAL, "Could not open fbarray file: %s\n",
 887                         strerror(errno));
 888                 return -1;
 889         }
 890         if (flock(fd, LOCK_EX | LOCK_NB)) {
 891                 RTE_LOG(DEBUG, EAL, "Cannot destroy fbarray - another process is using it\n");
 892                 rte_errno = EBUSY;
 893                 ret = -1;
 894         } else {
 895                 ret = 0;
 896                 unlink(path);
 897                 memset(arr, 0, sizeof(*arr));
 898         }
 899         close(fd);
 900
 901         return ret;
 902 }
 903
 904 void * __rte_experimental
 905 rte_fbarray_get(const struct rte_fbarray *arr, unsigned int idx)
 906 {
 907         void *ret = NULL;
 908         if (arr == NULL) {
 909                 rte_errno = EINVAL;
 910                 return NULL;
 911         }
 912
 913         if (idx >= arr->len) {
 914                 rte_errno = EINVAL;
 915                 return NULL;
 916         }
 917
 918         ret = RTE_PTR_ADD(arr->data, idx * arr->elt_sz);
 919
 920         return ret;
 921 }
 922
 923 int __rte_experimental
 924 rte_fbarray_set_used(struct rte_fbarray *arr, unsigned int idx)
 925 {
 926         return set_used(arr, idx, true);
 927 }
 928
 929 int __rte_experimental
 930 rte_fbarray_set_free(struct rte_fbarray *arr, unsigned int idx)
 931 {
 932         return set_used(arr, idx, false);
 933 }
 934
 935 int __rte_experimental
 936 rte_fbarray_is_used(struct rte_fbarray *arr, unsigned int idx)
 937 {
 938         struct used_mask *msk;
 939         int msk_idx;
 940         uint64_t msk_bit;
 941         int ret = -1;
 942
 943         if (arr == NULL || idx >= arr->len) {
 944                 rte_errno = EINVAL;
 945                 return -1;
 946         }
 947
 948         /* prevent array from changing under us */
 949         rte_rwlock_read_lock(&arr->rwlock);
 950
 951         msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
 952         msk_idx = MASK_LEN_TO_IDX(idx);
 953         msk_bit = 1ULL << MASK_LEN_TO_MOD(idx);
 954
 955         ret = (msk->data[msk_idx] & msk_bit) != 0;
 956
 957         rte_rwlock_read_unlock(&arr->rwlock);
 958
 959         return ret;
 960 }
 961
 962 static int
 963 fbarray_find(struct rte_fbarray *arr, unsigned int start, bool next, bool used)
 964 {
 965         int ret = -1;
 966
 967         if (arr == NULL || start >= arr->len) {
 968                 rte_errno = EINVAL;
 969                 return -1;
 970         }
 971
 972         /* prevent array from changing under us */
 973         rte_rwlock_read_lock(&arr->rwlock);
 974
 975         /* cheap checks to prevent doing useless work */
 976         if (!used) {
 977                 if (arr->len == arr->count) {
 978                         rte_errno = ENOSPC;
 979                         goto out;
 980                 }
 981                 if (arr->count == 0) {
 982                         ret = start;
 983                         goto out;
 984                 }
 985         } else {
 986                 if (arr->count == 0) {
 987                         rte_errno = ENOENT;
 988                         goto out;
 989                 }
 990                 if (arr->len == arr->count) {
 991                         ret = start;
 992                         goto out;
 993                 }
 994         }
 995         if (next)
 996                 ret = find_next(arr, start, used);
 997         else
 998                 ret = find_prev(arr, start, used);
 999 out:
1000         rte_rwlock_read_unlock(&arr->rwlock);
1001         return ret;
1002 }
1003
1004 int __rte_experimental
1005 rte_fbarray_find_next_free(struct rte_fbarray *arr, unsigned int start)
1006 {
1007         return fbarray_find(arr, start, true, false);
1008 }
1009
1010 int __rte_experimental
1011 rte_fbarray_find_next_used(struct rte_fbarray *arr, unsigned int start)
1012 {
1013         return fbarray_find(arr, start, true, true);
1014 }
1015
1016 int __rte_experimental
1017 rte_fbarray_find_prev_free(struct rte_fbarray *arr, unsigned int start)
1018 {
1019         return fbarray_find(arr, start, false, false);
1020 }
1021
1022 int __rte_experimental
1023 rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start)
1024 {
1025         return fbarray_find(arr, start, false, true);
1026 }
1027
1028 static int
1029 fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n,
1030                 bool next, bool used)
1031 {
1032         int ret = -1;
1033
1034         if (arr == NULL || start >= arr->len || n > arr->len || n == 0) {
1035                 rte_errno = EINVAL;
1036                 return -1;
1037         }
1038         if (next && (arr->len - start) < n) {
1039                 rte_errno = used ? ENOENT : ENOSPC;
1040                 return -1;
1041         }
1042         if (!next && start < (n - 1)) {
1043                 rte_errno = used ? ENOENT : ENOSPC;
1044                 return -1;
1045         }
1046
1047         /* prevent array from changing under us */
1048         rte_rwlock_read_lock(&arr->rwlock);
1049
1050         /* cheap checks to prevent doing useless work */
1051         if (!used) {
1052                 if (arr->len == arr->count || arr->len - arr->count < n) {
1053                         rte_errno = ENOSPC;
1054                         goto out;
1055                 }
1056                 if (arr->count == 0) {
1057                         ret = next ? start : start - n + 1;
1058                         goto out;
1059                 }
1060         } else {
1061                 if (arr->count < n) {
1062                         rte_errno = ENOENT;
1063                         goto out;
1064                 }
1065                 if (arr->count == arr->len) {
1066                         ret = next ? start : start - n + 1;
1067                         goto out;
1068                 }
1069         }
1070
1071         if (next)
1072                 ret = find_next_n(arr, start, n, used);
1073         else
1074                 ret = find_prev_n(arr, start, n, used);
1075 out:
1076         rte_rwlock_read_unlock(&arr->rwlock);
1077         return ret;
1078 }
1079
1080 int __rte_experimental
1081 rte_fbarray_find_next_n_free(struct rte_fbarray *arr, unsigned int start,
1082                 unsigned int n)
1083 {
1084         return fbarray_find_n(arr, start, n, true, false);
1085 }
1086
1087 int __rte_experimental
1088 rte_fbarray_find_next_n_used(struct rte_fbarray *arr, unsigned int start,
1089                 unsigned int n)
1090 {
1091         return fbarray_find_n(arr, start, n, true, true);
1092 }
1093
1094 int __rte_experimental
1095 rte_fbarray_find_prev_n_free(struct rte_fbarray *arr, unsigned int start,
1096                 unsigned int n)
1097 {
1098         return fbarray_find_n(arr, start, n, false, false);
1099 }
1100
1101 int __rte_experimental
1102 rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start,
1103                 unsigned int n)
1104 {
1105         return fbarray_find_n(arr, start, n, false, true);
1106 }
1107
1108 static int
1109 fbarray_find_contig(struct rte_fbarray *arr, unsigned int start, bool next,
1110                 bool used)
1111 {
1112         int ret = -1;
1113
1114         if (arr == NULL || start >= arr->len) {
1115                 rte_errno = EINVAL;
1116                 return -1;
1117         }
1118
1119         /* prevent array from changing under us */
1120         rte_rwlock_read_lock(&arr->rwlock);
1121
1122         /* cheap checks to prevent doing useless work */
1123         if (used) {
1124                 if (arr->count == 0) {
1125                         ret = 0;
1126                         goto out;
1127                 }
1128                 if (next && arr->count == arr->len) {
1129                         ret = arr->len - start;
1130                         goto out;
1131                 }
1132                 if (!next && arr->count == arr->len) {
1133                         ret = start + 1;
1134                         goto out;
1135                 }
1136         } else {
1137                 if (arr->len == arr->count) {
1138                         ret = 0;
1139                         goto out;
1140                 }
1141                 if (next && arr->count == 0) {
1142                         ret = arr->len - start;
1143                         goto out;
1144                 }
1145                 if (!next && arr->count == 0) {
1146                         ret = start + 1;
1147                         goto out;
1148                 }
1149         }
1150
1151         if (next)
1152                 ret = find_contig(arr, start, used);
1153         else
1154                 ret = find_rev_contig(arr, start, used);
1155 out:
1156         rte_rwlock_read_unlock(&arr->rwlock);
1157         return ret;
1158 }
1159
1160 int __rte_experimental
1161 rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start)
1162 {
1163         return fbarray_find_contig(arr, start, true, false);
1164 }
1165
1166 int __rte_experimental
1167 rte_fbarray_find_contig_used(struct rte_fbarray *arr, unsigned int start)
1168 {
1169         return fbarray_find_contig(arr, start, true, true);
1170 }
1171
1172 int __rte_experimental
1173 rte_fbarray_find_rev_contig_free(struct rte_fbarray *arr, unsigned int start)
1174 {
1175         return fbarray_find_contig(arr, start, false, false);
1176 }
1177
1178 int __rte_experimental
1179 rte_fbarray_find_rev_contig_used(struct rte_fbarray *arr, unsigned int start)
1180 {
1181         return fbarray_find_contig(arr, start, false, true);
1182 }
1183
1184 int __rte_experimental
1185 rte_fbarray_find_idx(const struct rte_fbarray *arr, const void *elt)
1186 {
1187         void *end;
1188         int ret = -1;
1189
1190         /*
1191          * no need to synchronize as it doesn't matter if underlying data
1192          * changes - we're doing pointer arithmetic here.
1193          */
1194
1195         if (arr == NULL || elt == NULL) {
1196                 rte_errno = EINVAL;
1197                 return -1;
1198         }
1199         end = RTE_PTR_ADD(arr->data, arr->elt_sz * arr->len);
1200         if (elt < arr->data || elt >= end) {
1201                 rte_errno = EINVAL;
1202                 return -1;
1203         }
1204
1205         ret = RTE_PTR_DIFF(elt, arr->data) / arr->elt_sz;
1206
1207         return ret;
1208 }
1209
1210 void __rte_experimental
1211 rte_fbarray_dump_metadata(struct rte_fbarray *arr, FILE *f)
1212 {
1213         struct used_mask *msk;
1214         unsigned int i;
1215
1216         if (arr == NULL || f == NULL) {
1217                 rte_errno = EINVAL;
1218                 return;
1219         }
1220
1221         if (fully_validate(arr->name, arr->elt_sz, arr->len)) {
1222                 fprintf(f, "Invalid file-backed array\n");
1223                 goto out;
1224         }
1225
1226         /* prevent array from changing under us */
1227         rte_rwlock_read_lock(&arr->rwlock);
1228
1229         fprintf(f, "File-backed array: %s\n", arr->name);
1230         fprintf(f, "size: %i occupied: %i elt_sz: %i\n",
1231                         arr->len, arr->count, arr->elt_sz);
1232
1233         msk = get_used_mask(arr->data, arr->elt_sz, arr->len);
1234
1235         for (i = 0; i < msk->n_masks; i++)
1236                 fprintf(f, "msk idx %i: 0x%016" PRIx64 "\n", i, msk->data[i]);
1237 out:
1238         rte_rwlock_read_unlock(&arr->rwlock);
1239 }