lib/librte_eal/common/eal_common_fbarray.c

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