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