src/rseq-mempool.c

   1 // SPDX-License-Identifier: MIT
   2 // SPDX-FileCopyrightText: 2024 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   3
   4 #include <rseq/mempool.h>
   5 #include <sys/mman.h>
   6 #include <assert.h>
   7 #include <string.h>
   8 #include <pthread.h>
   9 #include <unistd.h>
  10 #include <stdlib.h>
  11 #include <rseq/compiler.h>
  12 #include <errno.h>
  13 #include <stdint.h>
  14 #include <stdbool.h>
  15 #include <stdio.h>
  16
  17 #ifdef HAVE_LIBNUMA
  18 # include <numa.h>
  19 # include <numaif.h>
  20 #endif
  21
  22 #include "rseq-utils.h"
  23
  24 /*
  25  * rseq-mempool.c: rseq CPU-Local Storage (CLS) memory allocator.
  26  *
  27  * The rseq per-CPU memory allocator allows the application the request
  28  * memory pools of CPU-Local memory each of containing objects of a
  29  * given size (rounded to next power of 2), reserving a given virtual
  30  * address size per CPU, for a given maximum number of CPUs.
  31  *
  32  * The per-CPU memory allocator is analogous to TLS (Thread-Local
  33  * Storage) memory: TLS is Thread-Local Storage, whereas the per-CPU
  34  * memory allocator provides CPU-Local Storage.
  35  */
  36
  37 /*
  38  * Use high bits of per-CPU addresses to index the pool.
  39  * This leaves the low bits of available to the application for pointer
  40  * tagging (based on next power of 2 alignment of the allocations).
  41  */
  42 #if RSEQ_BITS_PER_LONG == 64
  43 # define POOL_INDEX_BITS        16
  44 #else
  45 # define POOL_INDEX_BITS        8
  46 #endif
  47 #define MAX_NR_POOLS            (1UL << POOL_INDEX_BITS)
  48 #define POOL_INDEX_SHIFT        (RSEQ_BITS_PER_LONG - POOL_INDEX_BITS)
  49 #define MAX_POOL_LEN            (1UL << POOL_INDEX_SHIFT)
  50 #define MAX_POOL_LEN_MASK       (MAX_POOL_LEN - 1)
  51
  52 #define POOL_SET_NR_ENTRIES     POOL_INDEX_SHIFT
  53
  54 /*
  55  * Smallest allocation should hold enough space for a free list pointer.
  56  */
  57 #if RSEQ_BITS_PER_LONG == 64
  58 # define POOL_SET_MIN_ENTRY     3       /* Smallest item_len=8 */
  59 #else
  60 # define POOL_SET_MIN_ENTRY     2       /* Smallest item_len=4 */
  61 #endif
  62
  63 /*
  64  * Skip pool index 0 to ensure allocated entries at index 0 do not match
  65  * a NULL pointer.
  66  */
  67 #define FIRST_POOL              1
  68
  69 #define BIT_PER_ULONG           (8 * sizeof(unsigned long))
  70
  71 #define MOVE_PAGES_BATCH_SIZE   4096
  72
  73 struct free_list_node;
  74
  75 struct free_list_node {
  76         struct free_list_node *next;
  77 };
  78
  79 /* This lock protects pool create/destroy. */
  80 static pthread_mutex_t pool_lock = PTHREAD_MUTEX_INITIALIZER;
  81
  82 struct rseq_pool_attr {
  83         bool mmap_set;
  84         void *(*mmap_func)(void *priv, size_t len);
  85         int (*munmap_func)(void *priv, void *ptr, size_t len);
  86         void *mmap_priv;
  87
  88         bool robust_set;
  89 };
  90
  91 struct rseq_percpu_pool_range;
  92
  93 struct rseq_percpu_pool_range {
  94         struct rseq_percpu_pool_range *next;
  95         struct rseq_percpu_pool *pool;  /* Backward ref. to container pool. */
  96         void *base;
  97         size_t next_unused;
  98         /* Track alloc/free. */
  99         unsigned long *alloc_bitmap;
 100 };
 101
 102 struct rseq_percpu_pool {
 103         /* Linked-list of ranges. */
 104         struct rseq_percpu_pool_range *ranges;
 105
 106         unsigned int index;
 107         size_t item_len;
 108         size_t percpu_stride;
 109         int item_order;
 110         int max_nr_cpus;
 111
 112         /*
 113          * The free list chains freed items on the CPU 0 address range.
 114          * We should rethink this decision if false sharing between
 115          * malloc/free from other CPUs and data accesses from CPU 0
 116          * becomes an issue. This is a NULL-terminated singly-linked
 117          * list.
 118          */
 119         struct free_list_node *free_list_head;
 120
 121         /* This lock protects allocation/free within the pool. */
 122         pthread_mutex_t lock;
 123
 124         struct rseq_pool_attr attr;
 125         char *name;
 126 };
 127
 128 //TODO: the array of pools should grow dynamically on create.
 129 static struct rseq_percpu_pool rseq_percpu_pool[MAX_NR_POOLS];
 130
 131 /*
 132  * Pool set entries are indexed by item_len rounded to the next power of
 133  * 2. A pool set can contain NULL pool entries, in which case the next
 134  * large enough entry will be used for allocation.
 135  */
 136 struct rseq_percpu_pool_set {
 137         /* This lock protects add vs malloc/zmalloc within the pool set. */
 138         pthread_mutex_t lock;
 139         struct rseq_percpu_pool *entries[POOL_SET_NR_ENTRIES];
 140 };
 141
 142 static
 143 void *__rseq_pool_percpu_ptr(struct rseq_percpu_pool *pool, int cpu,
 144                 uintptr_t item_offset, size_t stride)
 145 {
 146         /* TODO: Implement multi-ranges support. */
 147         return pool->ranges->base + (stride * cpu) + item_offset;
 148 }
 149
 150 void *__rseq_percpu_ptr(void __rseq_percpu *_ptr, int cpu, size_t stride)
 151 {
 152         uintptr_t ptr = (uintptr_t) _ptr;
 153         uintptr_t item_offset = ptr & MAX_POOL_LEN_MASK;
 154         uintptr_t pool_index = ptr >> POOL_INDEX_SHIFT;
 155         struct rseq_percpu_pool *pool = &rseq_percpu_pool[pool_index];
 156
 157         assert(cpu >= 0);
 158         return __rseq_pool_percpu_ptr(pool, cpu, item_offset, stride);
 159 }
 160
 161 static
 162 void rseq_percpu_zero_item(struct rseq_percpu_pool *pool, uintptr_t item_offset)
 163 {
 164         int i;
 165
 166         for (i = 0; i < pool->max_nr_cpus; i++) {
 167                 char *p = __rseq_pool_percpu_ptr(pool, i,
 168                                 item_offset, pool->percpu_stride);
 169                 memset(p, 0, pool->item_len);
 170         }
 171 }
 172
 173 //TODO: this will need to be reimplemented for ranges,
 174 //which cannot use __rseq_pool_percpu_ptr.
 175 #if 0 //#ifdef HAVE_LIBNUMA
 176 static
 177 int rseq_percpu_pool_range_init_numa(struct rseq_percpu_pool *pool, struct rseq_percpu_pool_range *range, int numa_flags)
 178 {
 179         unsigned long nr_pages, page_len;
 180         long ret;
 181         int cpu;
 182
 183         if (!numa_flags)
 184                 return 0;
 185         page_len = rseq_get_page_len();
 186         nr_pages = pool->percpu_stride >> rseq_get_count_order_ulong(page_len);
 187         for (cpu = 0; cpu < pool->max_nr_cpus; cpu++) {
 188
 189                 int status[MOVE_PAGES_BATCH_SIZE];
 190                 int nodes[MOVE_PAGES_BATCH_SIZE];
 191                 void *pages[MOVE_PAGES_BATCH_SIZE];
 192
 193                 nodes[0] = numa_node_of_cpu(cpu);
 194                 for (size_t k = 1; k < RSEQ_ARRAY_SIZE(nodes); ++k) {
 195                         nodes[k] = nodes[0];
 196                 }
 197
 198                 for (unsigned long page = 0; page < nr_pages;) {
 199
 200                         size_t max_k = RSEQ_ARRAY_SIZE(pages);
 201                         size_t left = nr_pages - page;
 202
 203                         if (left < max_k) {
 204                                 max_k = left;
 205                         }
 206
 207                         for (size_t k = 0; k < max_k; ++k, ++page) {
 208                                 pages[k] = __rseq_pool_percpu_ptr(pool, cpu, page * page_len);
 209                                 status[k] = -EPERM;
 210                         }
 211
 212                         ret = move_pages(0, max_k, pages, nodes, status, numa_flags);
 213
 214                         if (ret < 0)
 215                                 return ret;
 216
 217                         if (ret > 0) {
 218                                 fprintf(stderr, "%lu pages were not migrated\n", ret);
 219                                 for (size_t k = 0; k < max_k; ++k) {
 220                                         if (status[k] < 0)
 221                                                 fprintf(stderr,
 222                                                         "Error while moving page %p to numa node %d: %u\n",
 223                                                         pages[k], nodes[k], -status[k]);
 224                                 }
 225                         }
 226                 }
 227         }
 228         return 0;
 229 }
 230
 231 int rseq_percpu_pool_init_numa(struct rseq_percpu_pool *pool, int numa_flags)
 232 {
 233         struct rseq_percpu_pool_range *range;
 234         int ret;
 235
 236         if (!numa_flags)
 237                 return 0;
 238         for (range = pool->ranges; range; range = range->next) {
 239                 ret = rseq_percpu_pool_range_init_numa(pool, range, numa_flags);
 240                 if (ret)
 241                         return ret;
 242         }
 243         return 0;
 244 }
 245 #else
 246 int rseq_percpu_pool_init_numa(struct rseq_percpu_pool *pool __attribute__((unused)),
 247                 int numa_flags __attribute__((unused)))
 248 {
 249         return 0;
 250 }
 251 #endif
 252
 253 static
 254 void *default_mmap_func(void *priv __attribute__((unused)), size_t len)
 255 {
 256         void *base;
 257
 258         base = mmap(NULL, len, PROT_READ | PROT_WRITE,
 259                         MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
 260         if (base == MAP_FAILED)
 261                 return NULL;
 262         return base;
 263 }
 264
 265 static
 266 int default_munmap_func(void *priv __attribute__((unused)), void *ptr, size_t len)
 267 {
 268         return munmap(ptr, len);
 269 }
 270
 271 static
 272 int create_alloc_bitmap(struct rseq_percpu_pool *pool, struct rseq_percpu_pool_range *range)
 273 {
 274         size_t count;
 275
 276         count = ((pool->percpu_stride >> pool->item_order) + BIT_PER_ULONG - 1) / BIT_PER_ULONG;
 277
 278         /*
 279          * Not being able to create the validation bitmap is an error
 280          * that needs to be reported.
 281          */
 282         range->alloc_bitmap = calloc(count, sizeof(unsigned long));
 283         if (!range->alloc_bitmap)
 284                 return -1;
 285         return 0;
 286 }
 287
 288 static
 289 const char *get_pool_name(const struct rseq_percpu_pool *pool)
 290 {
 291         return pool->name ? : "<anonymous>";
 292 }
 293
 294 static
 295 bool addr_in_pool(const struct rseq_percpu_pool *pool, void *addr)
 296 {
 297         struct rseq_percpu_pool_range *range;
 298
 299         for (range = pool->ranges; range; range = range->next) {
 300                 if (addr >= range->base && addr < range->base + range->next_unused)
 301                         return true;
 302         }
 303         return false;
 304 }
 305
 306 /* Always inline for __builtin_return_address(0). */
 307 static inline __attribute__((always_inline))
 308 void check_free_list(const struct rseq_percpu_pool *pool)
 309 {
 310         size_t total_item = 0, total_never_allocated = 0, total_freed = 0,
 311                 max_list_traversal = 0, traversal_iteration = 0;
 312         struct rseq_percpu_pool_range *range;
 313
 314         if (!pool->attr.robust_set)
 315                 return;
 316
 317         for (range = pool->ranges; range; range = range->next) {
 318                 total_item += pool->percpu_stride >> pool->item_order;
 319                 total_never_allocated += (pool->percpu_stride - range->next_unused) >> pool->item_order;
 320         }
 321         max_list_traversal = total_item - total_never_allocated;
 322
 323         for (struct free_list_node *node = pool->free_list_head, *prev = NULL;
 324              node;
 325              prev = node,
 326              node = node->next) {
 327
 328                 void *node_addr = node;
 329
 330                 if (traversal_iteration >= max_list_traversal) {
 331                         fprintf(stderr, "%s: Corrupted free-list; Possibly infinite loop in pool \"%s\" (%p), caller %p.\n",
 332                                 __func__, get_pool_name(pool), pool, __builtin_return_address(0));
 333                         abort();
 334                 }
 335
 336                 /* Node is out of range. */
 337                 if (!addr_in_pool(pool, node_addr)) {
 338                         if (prev)
 339                                 fprintf(stderr, "%s: Corrupted free-list node %p -> [out-of-range %p] in pool \"%s\" (%p), caller %p.\n",
 340                                         __func__, prev, node, get_pool_name(pool), pool, __builtin_return_address(0));
 341                         else
 342                                 fprintf(stderr, "%s: Corrupted free-list node [out-of-range %p] in pool \"%s\" (%p), caller %p.\n",
 343                                         __func__, node, get_pool_name(pool), pool, __builtin_return_address(0));
 344                         abort();
 345                 }
 346
 347                 traversal_iteration++;
 348                 total_freed++;
 349         }
 350
 351         if (total_never_allocated + total_freed != total_item) {
 352                 fprintf(stderr, "%s: Corrupted free-list in pool \"%s\" (%p); total-item: %zu total-never-used: %zu total-freed: %zu, caller %p.\n",
 353                         __func__, get_pool_name(pool), pool, total_item, total_never_allocated, total_freed, __builtin_return_address(0));
 354                 abort();
 355         }
 356 }
 357
 358 /* Always inline for __builtin_return_address(0). */
 359 static inline __attribute__((always_inline))
 360 void destroy_alloc_bitmap(struct rseq_percpu_pool *pool, struct rseq_percpu_pool_range *range)
 361 {
 362         unsigned long *bitmap = range->alloc_bitmap;
 363         size_t count, total_leaks = 0;
 364
 365         if (!bitmap)
 366                 return;
 367
 368         count = ((pool->percpu_stride >> pool->item_order) + BIT_PER_ULONG - 1) / BIT_PER_ULONG;
 369
 370         /* Assert that all items in the pool were freed. */
 371         for (size_t k = 0; k < count; ++k)
 372                 total_leaks += rseq_hweight_ulong(bitmap[k]);
 373         if (total_leaks) {
 374                 fprintf(stderr, "%s: Pool \"%s\" (%p) has %zu leaked items on destroy, caller: %p.\n",
 375                         __func__, get_pool_name(pool), pool, total_leaks, (void *) __builtin_return_address(0));
 376                 abort();
 377         }
 378
 379         free(bitmap);
 380 }
 381
 382 /* Always inline for __builtin_return_address(0). */
 383 static inline __attribute__((always_inline))
 384 int rseq_percpu_pool_range_destroy(struct rseq_percpu_pool *pool,
 385                 struct rseq_percpu_pool_range *range)
 386 {
 387         destroy_alloc_bitmap(pool, range);
 388         /* range is a header located one page before the aligned mapping. */
 389         return pool->attr.munmap_func(pool->attr.mmap_priv, range,
 390                         (pool->percpu_stride * pool->max_nr_cpus) + rseq_get_page_len());
 391 }
 392
 393 /*
 394  * Allocate a memory mapping aligned on @alignment, with an optional
 395  * @pre_header before the mapping.
 396  */
 397 static
 398 void *aligned_mmap_anonymous(struct rseq_percpu_pool *pool,
 399                 size_t page_size, size_t len, size_t alignment,
 400                 void **pre_header, size_t pre_header_len)
 401 {
 402         size_t minimum_page_count, page_count, extra, total_allocate = 0;
 403         int page_order;
 404         void *ptr;
 405
 406         if (len < page_size || alignment < page_size ||
 407                         !is_pow2(len) || !is_pow2(alignment)) {
 408                 errno = EINVAL;
 409                 return NULL;
 410         }
 411         page_order = rseq_get_count_order_ulong(page_size);
 412         if (page_order < 0) {
 413                 errno = EINVAL;
 414                 return NULL;
 415         }
 416         if (pre_header_len && (pre_header_len & (page_size - 1))) {
 417                 errno = EINVAL;
 418                 return NULL;
 419         }
 420
 421         minimum_page_count = (pre_header_len + len) >> page_order;
 422         page_count = (pre_header_len + len + alignment - page_size) >> page_order;
 423
 424         assert(page_count >= minimum_page_count);
 425
 426         ptr = pool->attr.mmap_func(pool->attr.mmap_priv, page_count << page_order);
 427         if (!ptr)
 428                 goto alloc_error;
 429
 430         total_allocate = page_count << page_order;
 431
 432         if (!(((uintptr_t) ptr + pre_header_len) & (alignment - 1))) {
 433                 /* Pointer is already aligned. ptr points to pre_header. */
 434                 goto out;
 435         }
 436
 437         /* Unmap extra before. */
 438         extra = offset_align((uintptr_t) ptr + pre_header_len, alignment);
 439         assert(!(extra & (page_size - 1)));
 440         if (pool->attr.munmap_func(pool->attr.mmap_priv, ptr, extra)) {
 441                 perror("munmap");
 442                 abort();
 443         }
 444         total_allocate -= extra;
 445         ptr += extra;   /* ptr points to pre_header */
 446         page_count -= extra >> page_order;
 447 out:
 448         assert(page_count >= minimum_page_count);
 449
 450         if (page_count > minimum_page_count) {
 451                 void *extra_ptr;
 452
 453                 /* Unmap extra after. */
 454                 extra_ptr = ptr + (minimum_page_count << page_order);
 455                 extra = (page_count - minimum_page_count) << page_order;
 456                 if (pool->attr.munmap_func(pool->attr.mmap_priv, extra_ptr, extra)) {
 457                         perror("munmap");
 458                         abort();
 459                 }
 460                 total_allocate -= extra;
 461         }
 462
 463         assert(!(((uintptr_t)ptr + pre_header_len) & (alignment - 1)));
 464         assert(total_allocate == len + pre_header_len);
 465
 466 alloc_error:
 467         if (ptr) {
 468                 if (pre_header)
 469                         *pre_header = ptr;
 470                 ptr += pre_header_len;
 471         }
 472         return ptr;
 473 }
 474
 475 static
 476 struct rseq_percpu_pool_range *rseq_percpu_pool_range_create(struct rseq_percpu_pool *pool)
 477 {
 478         struct rseq_percpu_pool_range *range;
 479         unsigned long page_size;
 480         void *base;
 481
 482         page_size = rseq_get_page_len();
 483
 484         base = aligned_mmap_anonymous(pool, page_size,
 485                         pool->percpu_stride * pool->max_nr_cpus,
 486                         pool->percpu_stride,
 487                         (void **) &range, page_size);
 488         if (!base)
 489                 return NULL;
 490         range->pool = pool;
 491         range->base = base;
 492         if (pool->attr.robust_set) {
 493                 if (create_alloc_bitmap(pool, range))
 494                         goto error_alloc;
 495         }
 496         return range;
 497
 498 error_alloc:
 499         (void) rseq_percpu_pool_range_destroy(pool, range);
 500         return NULL;
 501 }
 502
 503 /* Always inline for __builtin_return_address(0). */
 504 static inline __attribute__((always_inline))
 505 int __rseq_percpu_pool_destroy(struct rseq_percpu_pool *pool)
 506 {
 507         struct rseq_percpu_pool_range *range, *next_range;
 508         int ret = 0;
 509
 510         if (!pool->ranges) {
 511                 errno = ENOENT;
 512                 ret = -1;
 513                 goto end;
 514         }
 515         check_free_list(pool);
 516         /* Iteration safe against removal. */
 517         for (range = pool->ranges; range && (next_range = range->next, 1); range = next_range) {
 518                 if (rseq_percpu_pool_range_destroy(pool, range))
 519                         goto end;
 520                 /* Update list head to keep list coherent in case of partial failure. */
 521                 pool->ranges = next_range;
 522         }
 523         pthread_mutex_destroy(&pool->lock);
 524         free(pool->name);
 525         memset(pool, 0, sizeof(*pool));
 526 end:
 527         return ret;
 528 }
 529
 530 int rseq_percpu_pool_destroy(struct rseq_percpu_pool *pool)
 531 {
 532         int ret;
 533
 534         pthread_mutex_lock(&pool_lock);
 535         ret = __rseq_percpu_pool_destroy(pool);
 536         pthread_mutex_unlock(&pool_lock);
 537         return ret;
 538 }
 539
 540 struct rseq_percpu_pool *rseq_percpu_pool_create(const char *pool_name,
 541                 size_t item_len, size_t percpu_stride, int max_nr_cpus,
 542                 const struct rseq_pool_attr *_attr)
 543 {
 544         struct rseq_percpu_pool *pool;
 545         struct rseq_pool_attr attr = {};
 546         unsigned int i;
 547         int order;
 548
 549         /* Make sure each item is large enough to contain free list pointers. */
 550         if (item_len < sizeof(void *))
 551                 item_len = sizeof(void *);
 552
 553         /* Align item_len on next power of two. */
 554         order = rseq_get_count_order_ulong(item_len);
 555         if (order < 0) {
 556                 errno = EINVAL;
 557                 return NULL;
 558         }
 559         item_len = 1UL << order;
 560
 561         if (!percpu_stride)
 562                 percpu_stride = RSEQ_PERCPU_STRIDE;     /* Use default */
 563
 564         if (max_nr_cpus < 0 || item_len > percpu_stride ||
 565                         percpu_stride > (UINTPTR_MAX >> POOL_INDEX_BITS) ||
 566                         percpu_stride < (size_t) rseq_get_page_len() ||
 567                         !is_pow2(percpu_stride)) {
 568                 errno = EINVAL;
 569                 return NULL;
 570         }
 571
 572         if (_attr)
 573                 memcpy(&attr, _attr, sizeof(attr));
 574         if (!attr.mmap_set) {
 575                 attr.mmap_func = default_mmap_func;
 576                 attr.munmap_func = default_munmap_func;
 577                 attr.mmap_priv = NULL;
 578         }
 579
 580         pthread_mutex_lock(&pool_lock);
 581         /* Linear scan in array of pools to find empty spot. */
 582         for (i = FIRST_POOL; i < MAX_NR_POOLS; i++) {
 583                 pool = &rseq_percpu_pool[i];
 584                 if (!pool->ranges)
 585                         goto found_empty;
 586         }
 587         errno = ENOMEM;
 588         pool = NULL;
 589         goto end;
 590
 591 found_empty:
 592         memcpy(&pool->attr, &attr, sizeof(attr));
 593         pthread_mutex_init(&pool->lock, NULL);
 594         pool->percpu_stride = percpu_stride;
 595         pool->max_nr_cpus = max_nr_cpus;
 596         pool->index = i;
 597         pool->item_len = item_len;
 598         pool->item_order = order;
 599
 600         //TODO: implement multi-range support.
 601         pool->ranges = rseq_percpu_pool_range_create(pool);
 602         if (!pool->ranges)
 603                 goto error_alloc;
 604
 605         if (pool_name) {
 606                 pool->name = strdup(pool_name);
 607                 if (!pool->name)
 608                         goto error_alloc;
 609         }
 610 end:
 611         pthread_mutex_unlock(&pool_lock);
 612         return pool;
 613
 614 error_alloc:
 615         __rseq_percpu_pool_destroy(pool);
 616         pthread_mutex_unlock(&pool_lock);
 617         errno = ENOMEM;
 618         return NULL;
 619 }
 620
 621 /* Always inline for __builtin_return_address(0). */
 622 static inline __attribute__((always_inline))
 623 void set_alloc_slot(struct rseq_percpu_pool *pool, size_t item_offset)
 624 {
 625         unsigned long *bitmap = pool->ranges->alloc_bitmap;
 626         size_t item_index = item_offset >> pool->item_order;
 627         unsigned long mask;
 628         size_t k;
 629
 630         if (!bitmap)
 631                 return;
 632
 633         k = item_index / BIT_PER_ULONG;
 634         mask = 1ULL << (item_index % BIT_PER_ULONG);
 635
 636         /* Print error if bit is already set. */
 637         if (bitmap[k] & mask) {
 638                 fprintf(stderr, "%s: Allocator corruption detected for pool: \"%s\" (%p), item offset: %zu, caller: %p.\n",
 639                         __func__, get_pool_name(pool), pool, item_offset, (void *) __builtin_return_address(0));
 640                 abort();
 641         }
 642         bitmap[k] |= mask;
 643 }
 644
 645 static
 646 void __rseq_percpu *__rseq_percpu_malloc(struct rseq_percpu_pool *pool, bool zeroed)
 647 {
 648         struct free_list_node *node;
 649         uintptr_t item_offset;
 650         void __rseq_percpu *addr;
 651
 652         pthread_mutex_lock(&pool->lock);
 653         /* Get first entry from free list. */
 654         node = pool->free_list_head;
 655         if (node != NULL) {
 656                 /* Remove node from free list (update head). */
 657                 pool->free_list_head = node->next;
 658                 item_offset = (uintptr_t) ((void *) node - pool->ranges->base);
 659                 addr = (void *) (((uintptr_t) pool->index << POOL_INDEX_SHIFT) | item_offset);
 660                 goto end;
 661         }
 662         if (pool->ranges->next_unused + pool->item_len > pool->percpu_stride) {
 663                 errno = ENOMEM;
 664                 addr = NULL;
 665                 goto end;
 666         }
 667         item_offset = pool->ranges->next_unused;
 668         addr = (void *) (((uintptr_t) pool->index << POOL_INDEX_SHIFT) | item_offset);
 669         pool->ranges->next_unused += pool->item_len;
 670 end:
 671         if (addr)
 672                 set_alloc_slot(pool, item_offset);
 673         pthread_mutex_unlock(&pool->lock);
 674         if (zeroed && addr)
 675                 rseq_percpu_zero_item(pool, item_offset);
 676         return addr;
 677 }
 678
 679 void __rseq_percpu *rseq_percpu_malloc(struct rseq_percpu_pool *pool)
 680 {
 681         return __rseq_percpu_malloc(pool, false);
 682 }
 683
 684 void __rseq_percpu *rseq_percpu_zmalloc(struct rseq_percpu_pool *pool)
 685 {
 686         return __rseq_percpu_malloc(pool, true);
 687 }
 688
 689 /* Always inline for __builtin_return_address(0). */
 690 static inline __attribute__((always_inline))
 691 void clear_alloc_slot(struct rseq_percpu_pool *pool, size_t item_offset)
 692 {
 693         unsigned long *bitmap = pool->ranges->alloc_bitmap;
 694         size_t item_index = item_offset >> pool->item_order;
 695         unsigned long mask;
 696         size_t k;
 697
 698         if (!bitmap)
 699                 return;
 700
 701         k = item_index / BIT_PER_ULONG;
 702         mask = 1ULL << (item_index % BIT_PER_ULONG);
 703
 704         /* Print error if bit is not set. */
 705         if (!(bitmap[k] & mask)) {
 706                 fprintf(stderr, "%s: Double-free detected for pool: \"%s\" (%p), item offset: %zu, caller: %p.\n",
 707                         __func__, get_pool_name(pool), pool, item_offset,
 708                         (void *) __builtin_return_address(0));
 709                 abort();
 710         }
 711         bitmap[k] &= ~mask;
 712 }
 713
 714 void __rseq_percpu_free(void __rseq_percpu *_ptr, size_t percpu_stride)
 715 {
 716         uintptr_t ptr = (uintptr_t) _ptr;
 717         uintptr_t item_offset = ptr & MAX_POOL_LEN_MASK;
 718         uintptr_t pool_index = ptr >> POOL_INDEX_SHIFT;
 719         struct rseq_percpu_pool *pool = &rseq_percpu_pool[pool_index];
 720         struct free_list_node *head, *item;
 721
 722         pthread_mutex_lock(&pool->lock);
 723         clear_alloc_slot(pool, item_offset);
 724         /* Add ptr to head of free list */
 725         head = pool->free_list_head;
 726         /* Free-list is in CPU 0 range. */
 727         item = (struct free_list_node *)__rseq_pool_percpu_ptr(pool, 0, item_offset, percpu_stride);
 728         item->next = head;
 729         pool->free_list_head = item;
 730         pthread_mutex_unlock(&pool->lock);
 731 }
 732
 733 struct rseq_percpu_pool_set *rseq_percpu_pool_set_create(void)
 734 {
 735         struct rseq_percpu_pool_set *pool_set;
 736
 737         pool_set = calloc(1, sizeof(struct rseq_percpu_pool_set));
 738         if (!pool_set)
 739                 return NULL;
 740         pthread_mutex_init(&pool_set->lock, NULL);
 741         return pool_set;
 742 }
 743
 744 int rseq_percpu_pool_set_destroy(struct rseq_percpu_pool_set *pool_set)
 745 {
 746         int order, ret;
 747
 748         for (order = POOL_SET_MIN_ENTRY; order < POOL_SET_NR_ENTRIES; order++) {
 749                 struct rseq_percpu_pool *pool = pool_set->entries[order];
 750
 751                 if (!pool)
 752                         continue;
 753                 ret = rseq_percpu_pool_destroy(pool);
 754                 if (ret)
 755                         return ret;
 756                 pool_set->entries[order] = NULL;
 757         }
 758         pthread_mutex_destroy(&pool_set->lock);
 759         free(pool_set);
 760         return 0;
 761 }
 762
 763 /* Ownership of pool is handed over to pool set on success. */
 764 int rseq_percpu_pool_set_add_pool(struct rseq_percpu_pool_set *pool_set, struct rseq_percpu_pool *pool)
 765 {
 766         size_t item_order = pool->item_order;
 767         int ret = 0;
 768
 769         pthread_mutex_lock(&pool_set->lock);
 770         if (pool_set->entries[item_order]) {
 771                 errno = EBUSY;
 772                 ret = -1;
 773                 goto end;
 774         }
 775         pool_set->entries[pool->item_order] = pool;
 776 end:
 777         pthread_mutex_unlock(&pool_set->lock);
 778         return ret;
 779 }
 780
 781 static
 782 void __rseq_percpu *__rseq_percpu_pool_set_malloc(struct rseq_percpu_pool_set *pool_set, size_t len, bool zeroed)
 783 {
 784         int order, min_order = POOL_SET_MIN_ENTRY;
 785         struct rseq_percpu_pool *pool;
 786         void __rseq_percpu *addr;
 787
 788         order = rseq_get_count_order_ulong(len);
 789         if (order > POOL_SET_MIN_ENTRY)
 790                 min_order = order;
 791 again:
 792         pthread_mutex_lock(&pool_set->lock);
 793         /* First smallest present pool where @len fits. */
 794         for (order = min_order; order < POOL_SET_NR_ENTRIES; order++) {
 795                 pool = pool_set->entries[order];
 796
 797                 if (!pool)
 798                         continue;
 799                 if (pool->item_len >= len)
 800                         goto found;
 801         }
 802         pool = NULL;
 803 found:
 804         pthread_mutex_unlock(&pool_set->lock);
 805         if (pool) {
 806                 addr = __rseq_percpu_malloc(pool, zeroed);
 807                 if (addr == NULL && errno == ENOMEM) {
 808                         /*
 809                          * If the allocation failed, try again with a
 810                          * larger pool.
 811                          */
 812                         min_order = order + 1;
 813                         goto again;
 814                 }
 815         } else {
 816                 /* Not found. */
 817                 errno = ENOMEM;
 818                 addr = NULL;
 819         }
 820         return addr;
 821 }
 822
 823 void __rseq_percpu *rseq_percpu_pool_set_malloc(struct rseq_percpu_pool_set *pool_set, size_t len)
 824 {
 825         return __rseq_percpu_pool_set_malloc(pool_set, len, false);
 826 }
 827
 828 void __rseq_percpu *rseq_percpu_pool_set_zmalloc(struct rseq_percpu_pool_set *pool_set, size_t len)
 829 {
 830         return __rseq_percpu_pool_set_malloc(pool_set, len, true);
 831 }
 832
 833 struct rseq_pool_attr *rseq_pool_attr_create(void)
 834 {
 835         return calloc(1, sizeof(struct rseq_pool_attr));
 836 }
 837
 838 void rseq_pool_attr_destroy(struct rseq_pool_attr *attr)
 839 {
 840         free(attr);
 841 }
 842
 843 int rseq_pool_attr_set_mmap(struct rseq_pool_attr *attr,
 844                 void *(*mmap_func)(void *priv, size_t len),
 845                 int (*munmap_func)(void *priv, void *ptr, size_t len),
 846                 void *mmap_priv)
 847 {
 848         if (!attr) {
 849                 errno = EINVAL;
 850                 return -1;
 851         }
 852         attr->mmap_set = true;
 853         attr->mmap_func = mmap_func;
 854         attr->munmap_func = munmap_func;
 855         attr->mmap_priv = mmap_priv;
 856         return 0;
 857 }
 858
 859 int rseq_pool_attr_set_robust(struct rseq_pool_attr *attr)
 860 {
 861         if (!attr) {
 862                 errno = EINVAL;
 863                 return -1;
 864         }
 865         attr->robust_set = true;
 866         return 0;
 867 }