[librseq.git] / src / rseq-percpu-alloc.c

// SPDX-License-Identifier: MIT
// SPDX-FileCopyrightText: 2024 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

#include <rseq/percpu-alloc.h>
#include <sys/mman.h>
#include <assert.h>
#include <string.h>
#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
#include <rseq/compiler.h>
#include <errno.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>

#ifdef HAVE_LIBNUMA
# include <numa.h>
# include <numaif.h>
#endif

#include "rseq-alloc-utils.h"

/*
 * rseq-percpu-alloc.c: rseq CPU-Local Storage (CLS) memory allocator.
 *
 * The rseq per-CPU memory allocator allows the application the request
 * memory pools of CPU-Local memory each of containing objects of a
 * given size (rounded to next power of 2), reserving a given virtual
 * address size per CPU, for a given maximum number of CPUs.
 *
 * The per-CPU memory allocator is analogous to TLS (Thread-Local
 * Storage) memory: TLS is Thread-Local Storage, whereas the per-CPU
 * memory allocator provides CPU-Local Storage.
 */

/*
 * Use high bits of per-CPU addresses to index the pool.
 * This leaves the low bits of available to the application for pointer
 * tagging (based on next power of 2 alignment of the allocations).
 */
#if RSEQ_BITS_PER_LONG == 64
# define POOL_INDEX_BITS	16
#else
# define POOL_INDEX_BITS	8
#endif
#define MAX_NR_POOLS		(1UL << POOL_INDEX_BITS)
#define POOL_INDEX_SHIFT	(RSEQ_BITS_PER_LONG - POOL_INDEX_BITS)
#define MAX_POOL_LEN		(1UL << POOL_INDEX_SHIFT)
#define MAX_POOL_LEN_MASK	(MAX_POOL_LEN - 1)

#define POOL_SET_NR_ENTRIES	POOL_INDEX_SHIFT

/*
 * Smallest allocation should hold enough space for a free list pointer.
 */
#if RSEQ_BITS_PER_LONG == 64
# define POOL_SET_MIN_ENTRY	3	/* Smallest item_len=8 */
#else
# define POOL_SET_MIN_ENTRY	2	/* Smallest item_len=4 */
#endif

/*
 * Skip pool index 0 to ensure allocated entries at index 0 do not match
 * a NULL pointer.
 */
#define FIRST_POOL		1

#define RSEQ_POOL_FLAGS		(RSEQ_POOL_ROBUST)

#define BIT_PER_ULONG		(8 * sizeof(unsigned long))

struct free_list_node;

struct free_list_node {
	struct free_list_node *next;
};

/* This lock protects pool create/destroy. */
static pthread_mutex_t pool_lock = PTHREAD_MUTEX_INITIALIZER;

struct rseq_mmap_attr {
	void *(*mmap_func)(void *priv, size_t len);
	int (*munmap_func)(void *priv, void *ptr, size_t len);
	void *mmap_priv;
};

struct rseq_percpu_pool {
	void *base;
	unsigned int index;
	size_t item_len;
	size_t percpu_len;
	int item_order;
	int max_nr_cpus;

	/*
	 * The free list chains freed items on the CPU 0 address range.
	 * We should rethink this decision if false sharing between
	 * malloc/free from other CPUs and data accesses from CPU 0
	 * becomes an issue. This is a NULL-terminated singly-linked
	 * list.
	 */
	struct free_list_node *free_list_head;
	size_t next_unused;
	/* This lock protects allocation/free within the pool. */
	pthread_mutex_t lock;

	struct rseq_mmap_attr mmap_attr;

	/* Track alloc/free. */
	unsigned long *alloc_bitmap;
};

//TODO: the array of pools should grow dynamically on create.
static struct rseq_percpu_pool rseq_percpu_pool[MAX_NR_POOLS];

/*
 * Pool set entries are indexed by item_len rounded to the next power of
 * 2. A pool set can contain NULL pool entries, in which case the next
 * large enough entry will be used for allocation.
 */
struct rseq_percpu_pool_set {
	/* This lock protects add vs malloc/zmalloc within the pool set. */
	pthread_mutex_t lock;
	struct rseq_percpu_pool *entries[POOL_SET_NR_ENTRIES];
};

static
void *__rseq_pool_percpu_ptr(struct rseq_percpu_pool *pool, int cpu, uintptr_t item_offset)
{
	return pool->base + (pool->percpu_len * cpu) + item_offset;
}

void *__rseq_percpu_ptr(void __rseq_percpu *_ptr, int cpu)
{
	uintptr_t ptr = (uintptr_t) _ptr;
	uintptr_t item_offset = ptr & MAX_POOL_LEN_MASK;
	uintptr_t pool_index = ptr >> POOL_INDEX_SHIFT;
	struct rseq_percpu_pool *pool = &rseq_percpu_pool[pool_index];

	assert(cpu >= 0);
	return __rseq_pool_percpu_ptr(pool, cpu, item_offset);
}

static
void rseq_percpu_zero_item(struct rseq_percpu_pool *pool, uintptr_t item_offset)
{
	int i;

	for (i = 0; i < pool->max_nr_cpus; i++) {
		char *p = __rseq_pool_percpu_ptr(pool, i, item_offset);
		memset(p, 0, pool->item_len);
	}
}

#ifdef HAVE_LIBNUMA
int rseq_percpu_pool_init_numa(struct rseq_percpu_pool *pool, int numa_flags)
{
	unsigned long nr_pages, page;
	long ret, page_len;
	int cpu;

	if (!numa_flags)
		return 0;
	page_len = rseq_get_page_len();
	nr_pages = pool->percpu_len >> rseq_get_count_order_ulong(page_len);
	for (cpu = 0; cpu < pool->max_nr_cpus; cpu++) {
		int node = numa_node_of_cpu(cpu);

		/* TODO: batch move_pages() call with an array of pages. */
		for (page = 0; page < nr_pages; page++) {
			void *pageptr = __rseq_pool_percpu_ptr(pool, cpu, page * page_len);
			int status = -EPERM;

			ret = move_pages(0, 1, &pageptr, &node, &status, numa_flags);
			if (ret)
				return ret;
		}
	}
	return 0;
}
#else
void rseq_percpu_pool_init_numa(struct rseq_percpu_pool *pool __attribute__((unused)),
		int numa_flags __attribute__((unused)))
{
	return 0;
}
#endif

static
void *default_mmap_func(void *priv __attribute__((unused)), size_t len)
{
	void *base;

	base = mmap(NULL, len, PROT_READ | PROT_WRITE,
			MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
	if (base == MAP_FAILED)
		return NULL;
	return base;
}

static
int default_munmap_func(void *priv __attribute__((unused)), void *ptr, size_t len)
{
	return munmap(ptr, len);
}

static
int create_alloc_bitmap(struct rseq_percpu_pool *pool)
{
	size_t count;

	count = ((pool->percpu_len >> pool->item_order) + BIT_PER_ULONG - 1) / BIT_PER_ULONG;

	/*
	 * Not being able to create the validation bitmap is an error
	 * that needs to be reported.
	 */
	pool->alloc_bitmap = calloc(count, sizeof(unsigned long));
	if (!pool->alloc_bitmap)
		return -1;
	return 0;
}

static
void destroy_alloc_bitmap(struct rseq_percpu_pool *pool)
{
	unsigned long *bitmap = pool->alloc_bitmap;
	size_t item_len = pool->item_len;
	size_t count, total_leaks = 0;

	if (!bitmap)
		return;

	count = (item_len + BIT_PER_ULONG - 1) / BIT_PER_ULONG;

	/* Assert that all items in the pool were freed. */
	for (size_t k = 0; k < count; ++k)
		total_leaks += rseq_hweight_ulong(bitmap[k]);
	if (total_leaks) {
		fprintf(stderr, "%s: Pool has %zu leaked items on destroy.\n", __func__,
			total_leaks);
		abort();
	}

	free(bitmap);
}

static
int __rseq_percpu_pool_destroy(struct rseq_percpu_pool *pool)
{
	int ret;

	if (!pool->base) {
		errno = ENOENT;
		ret = -1;
		goto end;
	}
	ret = pool->mmap_attr.munmap_func(pool->mmap_attr.mmap_priv, pool->base,
			pool->percpu_len * pool->max_nr_cpus);
	if (ret)
		goto end;
	pthread_mutex_destroy(&pool->lock);
	destroy_alloc_bitmap(pool);
	memset(pool, 0, sizeof(*pool));
end:
	return 0;
}

int rseq_percpu_pool_destroy(struct rseq_percpu_pool *pool)
{
	int ret;

	pthread_mutex_lock(&pool_lock);
	ret = __rseq_percpu_pool_destroy(pool);
	pthread_mutex_unlock(&pool_lock);
	return ret;
}

struct rseq_percpu_pool *rseq_percpu_pool_create(size_t item_len,
		size_t percpu_len, int max_nr_cpus,
		const struct rseq_mmap_attr *mmap_attr,
		int flags)
{
	void *(*mmap_func)(void *priv, size_t len);
	int (*munmap_func)(void *priv, void *ptr, size_t len);
	void *mmap_priv;
	struct rseq_percpu_pool *pool;
	void *base;
	unsigned int i;
	int order;

	if (flags & ~RSEQ_POOL_FLAGS) {
		errno = EINVAL;
		return NULL;
	}

	/* Make sure each item is large enough to contain free list pointers. */
	if (item_len < sizeof(void *))
		item_len = sizeof(void *);

	/* Align item_len on next power of two. */
	order = rseq_get_count_order_ulong(item_len);
	if (order < 0) {
		errno = EINVAL;
		return NULL;
	}
	item_len = 1UL << order;

	/* Align percpu_len on page size. */
	percpu_len = rseq_align(percpu_len, rseq_get_page_len());

	if (max_nr_cpus < 0 || item_len > percpu_len ||
			percpu_len > (UINTPTR_MAX >> POOL_INDEX_BITS)) {
		errno = EINVAL;
		return NULL;
	}

	if (mmap_attr) {
		mmap_func = mmap_attr->mmap_func;
		munmap_func = mmap_attr->munmap_func;
		mmap_priv = mmap_attr->mmap_priv;
	} else {
		mmap_func = default_mmap_func;
		munmap_func = default_munmap_func;
		mmap_priv = NULL;
	}
	pthread_mutex_lock(&pool_lock);
	/* Linear scan in array of pools to find empty spot. */
	for (i = FIRST_POOL; i < MAX_NR_POOLS; i++) {
		pool = &rseq_percpu_pool[i];
		if (!pool->base)
			goto found_empty;
	}
	errno = ENOMEM;
	pool = NULL;
	goto end;

found_empty:
	base = mmap_func(mmap_priv, percpu_len * max_nr_cpus);
	if (!base)
		goto error_alloc;
	pthread_mutex_init(&pool->lock, NULL);
	pool->base = base;
	pool->percpu_len = percpu_len;
	pool->max_nr_cpus = max_nr_cpus;
	pool->index = i;
	pool->item_len = item_len;
	pool->item_order = order;
	pool->mmap_attr.mmap_func = mmap_func;
	pool->mmap_attr.munmap_func = munmap_func;
	pool->mmap_attr.mmap_priv = mmap_priv;

	if (RSEQ_POOL_ROBUST & flags) {
		if (create_alloc_bitmap(pool))
			goto error_alloc;
	}
end:
	pthread_mutex_unlock(&pool_lock);
	return pool;

error_alloc:
	__rseq_percpu_pool_destroy(pool);
	pthread_mutex_unlock(&pool_lock);
	errno = ENOMEM;
	return NULL;
}

static
void set_alloc_slot(struct rseq_percpu_pool *pool, size_t item_offset)
{
	unsigned long *bitmap = pool->alloc_bitmap;
	size_t item_index = item_offset >> pool->item_order;
	unsigned long mask;
	size_t k;

	if (!bitmap)
		return;

	k = item_index / BIT_PER_ULONG;
	mask = 1ULL << (item_index % BIT_PER_ULONG);

	/* Print error if bit is already set. */
	if (bitmap[k] & mask) {
		fprintf(stderr, "%s: Allocator corruption detected for pool %p, item offset %zu.",
			__func__, pool, item_offset);
		abort();
	}
	bitmap[k] |= mask;
}

static
void __rseq_percpu *__rseq_percpu_malloc(struct rseq_percpu_pool *pool, bool zeroed)
{
	struct free_list_node *node;
	uintptr_t item_offset;
	void __rseq_percpu *addr;

	pthread_mutex_lock(&pool->lock);
	/* Get first entry from free list. */
	node = pool->free_list_head;
	if (node != NULL) {
		/* Remove node from free list (update head). */
		pool->free_list_head = node->next;
		item_offset = (uintptr_t) ((void *) node - pool->base);
		addr = (void *) (((uintptr_t) pool->index << POOL_INDEX_SHIFT) | item_offset);
		goto end;
	}
	if (pool->next_unused + pool->item_len > pool->percpu_len) {
		errno = ENOMEM;
		addr = NULL;
		goto end;
	}
	item_offset = pool->next_unused;
	addr = (void *) (((uintptr_t) pool->index << POOL_INDEX_SHIFT) | item_offset);
	pool->next_unused += pool->item_len;
	set_alloc_slot(pool, item_offset);
end:
	pthread_mutex_unlock(&pool->lock);
	if (zeroed && addr)
		rseq_percpu_zero_item(pool, item_offset);
	return addr;
}

void __rseq_percpu *rseq_percpu_malloc(struct rseq_percpu_pool *pool)
{
	return __rseq_percpu_malloc(pool, false);
}

void __rseq_percpu *rseq_percpu_zmalloc(struct rseq_percpu_pool *pool)
{
	return __rseq_percpu_malloc(pool, true);
}

static
void clear_alloc_slot(struct rseq_percpu_pool *pool, size_t item_offset)
{
	unsigned long *bitmap = pool->alloc_bitmap;
	size_t item_index = item_offset >> pool->item_order;
	unsigned long mask;
	size_t k;

	if (!bitmap)
		return;

	k = item_index / BIT_PER_ULONG;
	mask = 1ULL << (item_index % BIT_PER_ULONG);

	/* Print error if bit is not set. */
	if (!(bitmap[k] & mask)) {
		fprintf(stderr, "%s: Double-free detected for pool %p, item offset %zu.",
			__func__, pool, item_offset);
		abort();
	}
	bitmap[k] &= ~mask;
}

void rseq_percpu_free(void __rseq_percpu *_ptr)
{
	uintptr_t ptr = (uintptr_t) _ptr;
	uintptr_t item_offset = ptr & MAX_POOL_LEN_MASK;
	uintptr_t pool_index = ptr >> POOL_INDEX_SHIFT;
	struct rseq_percpu_pool *pool = &rseq_percpu_pool[pool_index];
	struct free_list_node *head, *item;

	pthread_mutex_lock(&pool->lock);
	clear_alloc_slot(pool, item_offset);
	/* Add ptr to head of free list */
	head = pool->free_list_head;
	/* Free-list is in CPU 0 range. */
	item = (struct free_list_node *)__rseq_pool_percpu_ptr(pool, 0, item_offset);
	item->next = head;
	pool->free_list_head = item;
	pthread_mutex_unlock(&pool->lock);
}

struct rseq_percpu_pool_set *rseq_percpu_pool_set_create(void)
{
	struct rseq_percpu_pool_set *pool_set;

	pool_set = calloc(1, sizeof(struct rseq_percpu_pool_set));
	if (!pool_set)
		return NULL;
	pthread_mutex_init(&pool_set->lock, NULL);
	return pool_set;
}

int rseq_percpu_pool_set_destroy(struct rseq_percpu_pool_set *pool_set)
{
	int order, ret;

	for (order = POOL_SET_MIN_ENTRY; order < POOL_SET_NR_ENTRIES; order++) {
		struct rseq_percpu_pool *pool = pool_set->entries[order];

		if (!pool)
			continue;
		ret = rseq_percpu_pool_destroy(pool);
		if (ret)
			return ret;
		pool_set->entries[order] = NULL;
	}
	pthread_mutex_destroy(&pool_set->lock);
	free(pool_set);
	return 0;
}

/* Ownership of pool is handed over to pool set on success. */
int rseq_percpu_pool_set_add_pool(struct rseq_percpu_pool_set *pool_set, struct rseq_percpu_pool *pool)
{
	size_t item_order = pool->item_order;
	int ret = 0;

	pthread_mutex_lock(&pool_set->lock);
	if (pool_set->entries[item_order]) {
		errno = EBUSY;
		ret = -1;
		goto end;
	}
	pool_set->entries[pool->item_order] = pool;
end:
	pthread_mutex_unlock(&pool_set->lock);
	return ret;
}

static
void __rseq_percpu *__rseq_percpu_pool_set_malloc(struct rseq_percpu_pool_set *pool_set, size_t len, bool zeroed)
{
	int order, min_order = POOL_SET_MIN_ENTRY;
	struct rseq_percpu_pool *pool;
	void __rseq_percpu *addr;

	order = rseq_get_count_order_ulong(len);
	if (order > POOL_SET_MIN_ENTRY)
		min_order = order;
again:
	pthread_mutex_lock(&pool_set->lock);
	/* First smallest present pool where @len fits. */
	for (order = min_order; order < POOL_SET_NR_ENTRIES; order++) {
		pool = pool_set->entries[order];

		if (!pool)
			continue;
		if (pool->item_len >= len)
			goto found;
	}
	pool = NULL;
found:
	pthread_mutex_unlock(&pool_set->lock);
	if (pool) {
		addr = __rseq_percpu_malloc(pool, zeroed);
		if (addr == NULL && errno == ENOMEM) {
			/*
			 * If the allocation failed, try again with a
			 * larger pool.
			 */
			min_order = order + 1;
			goto again;
		}
	} else {
		/* Not found. */
		errno = ENOMEM;
		addr = NULL;
	}
	return addr;
}

void __rseq_percpu *rseq_percpu_pool_set_malloc(struct rseq_percpu_pool_set *pool_set, size_t len)
{
	return __rseq_percpu_pool_set_malloc(pool_set, len, false);
}

void __rseq_percpu *rseq_percpu_pool_set_zmalloc(struct rseq_percpu_pool_set *pool_set, size_t len)
{
	return __rseq_percpu_pool_set_malloc(pool_set, len, true);
}

struct rseq_mmap_attr *rseq_mmap_attr_create(void *(*mmap_func)(void *priv, size_t len),
		int (*munmap_func)(void *priv, void *ptr, size_t len),
		void *mmap_priv)
{
	struct rseq_mmap_attr *attr = calloc(1, sizeof(struct rseq_mmap_attr));

	if (!attr)
		return NULL;
	attr->mmap_func = mmap_func;
	attr->munmap_func = munmap_func;
	attr->mmap_priv = mmap_priv;
	return attr;
}

void rseq_mmap_attr_destroy(struct rseq_mmap_attr *attr)
{
	free(attr);
}
Commit	Line	Data
ef6695f1 MD	1	// SPDX-License-Identifier: MIT
	2	// SPDX-FileCopyrightText: 2024 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
	3
	4	#include <rseq/percpu-alloc.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>
367e559c MD	15	#include <stdio.h>
	16
	17	#ifdef HAVE_LIBNUMA
	18	# include <numa.h>
	19	# include <numaif.h>
	20	#endif
ef6695f1	21
19be9217 MD	22	#include "rseq-alloc-utils.h"
19be9217 MD	23
ef6695f1	24	/*
8ab16a24	25	* rseq-percpu-alloc.c: rseq CPU-Local Storage (CLS) memory allocator.
ef6695f1	26	*
8ab16a24 MD	27	* The rseq per-CPU memory allocator allows the application the request
8ab16a24 MD	28	* memory pools of CPU-Local memory each of containing objects of a
8aa1462d MD	29	* given size (rounded to next power of 2), reserving a given virtual
8aa1462d MD	30	* address size per CPU, for a given maximum number of CPUs.
8ab16a24 MD	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.
ef6695f1 MD	35	*/
ef6695f1 MD	36
72b100a1	37	/*
8ab16a24	38	* Use high bits of per-CPU addresses to index the pool.
72b100a1 MD	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	*/
ef6695f1	42	#if RSEQ_BITS_PER_LONG == 64
72b100a1	43	# define POOL_INDEX_BITS 16
ef6695f1	44	#else
72b100a1	45	# define POOL_INDEX_BITS 8
ef6695f1	46	#endif
72b100a1 MD	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)
ef6695f1	51
72b100a1	52	#define POOL_SET_NR_ENTRIES POOL_INDEX_SHIFT
ef6695f1	53
72b100a1 MD	54	/*
	55	* Smallest allocation should hold enough space for a free list pointer.
	56	*/
ef6695f1 MD	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
bb1552e2 MD	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
0fdf7a4c OD	69	#define RSEQ_POOL_FLAGS (RSEQ_POOL_ROBUST)
	70
	71	#define BIT_PER_ULONG (8 * sizeof(unsigned long))
	72
ef6695f1 MD	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
9bd07c29 MD	82	struct rseq_mmap_attr {
	83	void (mmap_func)(void *priv, size_t len);
	84	int (munmap_func)(void priv, void *ptr, size_t len);
	85	void *mmap_priv;
	86	};
	87
ef6695f1 MD	88	struct rseq_percpu_pool {
	89	void *base;
	90	unsigned int index;
	91	size_t item_len;
	92	size_t percpu_len;
	93	int item_order;
	94	int max_nr_cpus;
	95
	96	/*
8ab16a24	97	* The free list chains freed items on the CPU 0 address range.
ef6695f1	98	* We should rethink this decision if false sharing between
8ab16a24	99	* malloc/free from other CPUs and data accesses from CPU 0
ef6695f1 MD	100	* becomes an issue. This is a NULL-terminated singly-linked
	101	* list.
	102	*/
	103	struct free_list_node *free_list_head;
	104	size_t next_unused;
	105	/* This lock protects allocation/free within the pool. */
	106	pthread_mutex_t lock;
9bd07c29 MD	107
9bd07c29 MD	108	struct rseq_mmap_attr mmap_attr;
0fdf7a4c	109
9649c7ee MD	110	/* Track alloc/free. */
9649c7ee MD	111	unsigned long *alloc_bitmap;
ef6695f1 MD	112	};
	113
	114	//TODO: the array of pools should grow dynamically on create.
	115	static struct rseq_percpu_pool rseq_percpu_pool[MAX_NR_POOLS];
	116
	117	/*
	118	* Pool set entries are indexed by item_len rounded to the next power of
	119	* 2. A pool set can contain NULL pool entries, in which case the next
	120	* large enough entry will be used for allocation.
	121	*/
	122	struct rseq_percpu_pool_set {
	123	/* This lock protects add vs malloc/zmalloc within the pool set. */
	124	pthread_mutex_t lock;
	125	struct rseq_percpu_pool *entries[POOL_SET_NR_ENTRIES];
	126	};
	127
367e559c MD	128	static
	129	void __rseq_pool_percpu_ptr(struct rseq_percpu_pool pool, int cpu, uintptr_t item_offset)
	130	{
	131	return pool->base + (pool->percpu_len * cpu) + item_offset;
	132	}
	133
d24ee051	134	void __rseq_percpu_ptr(void __rseq_percpu _ptr, int cpu)
367e559c MD	135	{
367e559c MD	136	uintptr_t ptr = (uintptr_t) _ptr;
72b100a1 MD	137	uintptr_t item_offset = ptr & MAX_POOL_LEN_MASK;
72b100a1 MD	138	uintptr_t pool_index = ptr >> POOL_INDEX_SHIFT;
367e559c MD	139	struct rseq_percpu_pool *pool = &rseq_percpu_pool[pool_index];
	140
	141	assert(cpu >= 0);
	142	return __rseq_pool_percpu_ptr(pool, cpu, item_offset);
	143	}
	144
	145	static
	146	void rseq_percpu_zero_item(struct rseq_percpu_pool *pool, uintptr_t item_offset)
	147	{
	148	int i;
	149
	150	for (i = 0; i < pool->max_nr_cpus; i++) {
	151	char *p = __rseq_pool_percpu_ptr(pool, i, item_offset);
	152	memset(p, 0, pool->item_len);
	153	}
	154	}
	155
	156	#ifdef HAVE_LIBNUMA
9bd07c29	157	int rseq_percpu_pool_init_numa(struct rseq_percpu_pool *pool, int numa_flags)
367e559c MD	158	{
	159	unsigned long nr_pages, page;
	160	long ret, page_len;
	161	int cpu;
	162
	163	if (!numa_flags)
9bd07c29	164	return 0;
367e559c	165	page_len = rseq_get_page_len();
19be9217	166	nr_pages = pool->percpu_len >> rseq_get_count_order_ulong(page_len);
367e559c MD	167	for (cpu = 0; cpu < pool->max_nr_cpus; cpu++) {
	168	int node = numa_node_of_cpu(cpu);
	169
	170	/* TODO: batch move_pages() call with an array of pages. */
	171	for (page = 0; page < nr_pages; page++) {
	172	void pageptr = __rseq_pool_percpu_ptr(pool, cpu, page page_len);
	173	int status = -EPERM;
	174
	175	ret = move_pages(0, 1, &pageptr, &node, &status, numa_flags);
9bd07c29 MD	176	if (ret)
9bd07c29 MD	177	return ret;
367e559c MD	178	}
367e559c MD	179	}
9bd07c29	180	return 0;
367e559c MD	181	}
367e559c MD	182	#else
367e559c MD	183	void rseq_percpu_pool_init_numa(struct rseq_percpu_pool *pool __attribute__((unused)),
	184	int numa_flags __attribute__((unused)))
	185	{
9bd07c29	186	return 0;
367e559c MD	187	}
	188	#endif
	189
9bd07c29 MD	190	static
	191	void default_mmap_func(void priv __attribute__((unused)), size_t len)
	192	{
	193	void *base;
	194
	195	base = mmap(NULL, len, PROT_READ \| PROT_WRITE,
	196	MAP_ANONYMOUS \| MAP_PRIVATE, -1, 0);
	197	if (base == MAP_FAILED)
	198	return NULL;
	199	return base;
	200	}
	201
	202	static
	203	int default_munmap_func(void priv __attribute__((unused)), void ptr, size_t len)
	204	{
	205	return munmap(ptr, len);
	206	}
	207
0fdf7a4c	208	static
9649c7ee	209	int create_alloc_bitmap(struct rseq_percpu_pool *pool)
0fdf7a4c OD	210	{
	211	size_t count;
	212
9649c7ee	213	count = ((pool->percpu_len >> pool->item_order) + BIT_PER_ULONG - 1) / BIT_PER_ULONG;
0fdf7a4c OD	214
0fdf7a4c OD	215	/*
9649c7ee MD	216	* Not being able to create the validation bitmap is an error
9649c7ee MD	217	* that needs to be reported.
0fdf7a4c	218	*/
9649c7ee MD	219	pool->alloc_bitmap = calloc(count, sizeof(unsigned long));
	220	if (!pool->alloc_bitmap)
	221	return -1;
	222	return 0;
0fdf7a4c OD	223	}
	224
	225	static
9649c7ee	226	void destroy_alloc_bitmap(struct rseq_percpu_pool *pool)
0fdf7a4c	227	{
9649c7ee MD	228	unsigned long *bitmap = pool->alloc_bitmap;
	229	size_t item_len = pool->item_len;
	230	size_t count, total_leaks = 0;
0fdf7a4c	231
9649c7ee	232	if (!bitmap)
0fdf7a4c	233	return;
0fdf7a4c OD	234
	235	count = (item_len + BIT_PER_ULONG - 1) / BIT_PER_ULONG;
	236
	237	/* Assert that all items in the pool were freed. */
9649c7ee MD	238	for (size_t k = 0; k < count; ++k)
	239	total_leaks += rseq_hweight_ulong(bitmap[k]);
	240	if (total_leaks) {
	241	fprintf(stderr, "%s: Pool has %zu leaked items on destroy.\n", __func__,
	242	total_leaks);
	243	abort();
0fdf7a4c OD	244	}
	245
	246	free(bitmap);
	247	}
	248
9649c7ee MD	249	static
	250	int __rseq_percpu_pool_destroy(struct rseq_percpu_pool *pool)
	251	{
	252	int ret;
	253
	254	if (!pool->base) {
	255	errno = ENOENT;
	256	ret = -1;
	257	goto end;
	258	}
	259	ret = pool->mmap_attr.munmap_func(pool->mmap_attr.mmap_priv, pool->base,
	260	pool->percpu_len * pool->max_nr_cpus);
	261	if (ret)
	262	goto end;
	263	pthread_mutex_destroy(&pool->lock);
	264	destroy_alloc_bitmap(pool);
	265	memset(pool, 0, sizeof(*pool));
	266	end:
	267	return 0;
	268	}
	269
	270	int rseq_percpu_pool_destroy(struct rseq_percpu_pool *pool)
	271	{
	272	int ret;
	273
	274	pthread_mutex_lock(&pool_lock);
	275	ret = __rseq_percpu_pool_destroy(pool);
	276	pthread_mutex_unlock(&pool_lock);
	277	return ret;
	278	}
	279
ef6695f1 MD	280	struct rseq_percpu_pool *rseq_percpu_pool_create(size_t item_len,
ef6695f1 MD	281	size_t percpu_len, int max_nr_cpus,
6b30db4e MD	282	const struct rseq_mmap_attr *mmap_attr,
6b30db4e MD	283	int flags)
ef6695f1	284	{
9bd07c29 MD	285	void (mmap_func)(void *priv, size_t len);
	286	int (munmap_func)(void priv, void *ptr, size_t len);
	287	void *mmap_priv;
ef6695f1 MD	288	struct rseq_percpu_pool *pool;
	289	void *base;
	290	unsigned int i;
	291	int order;
ef6695f1	292
0fdf7a4c	293	if (flags & ~RSEQ_POOL_FLAGS) {
6b30db4e MD	294	errno = EINVAL;
	295	return NULL;
	296	}
	297
ef6695f1 MD	298	/* Make sure each item is large enough to contain free list pointers. */
	299	if (item_len < sizeof(void *))
	300	item_len = sizeof(void *);
	301
	302	/* Align item_len on next power of two. */
19be9217	303	order = rseq_get_count_order_ulong(item_len);
ef6695f1 MD	304	if (order < 0) {
	305	errno = EINVAL;
	306	return NULL;
	307	}
	308	item_len = 1UL << order;
	309
	310	/* Align percpu_len on page size. */
367e559c	311	percpu_len = rseq_align(percpu_len, rseq_get_page_len());
ef6695f1 MD	312
ef6695f1 MD	313	if (max_nr_cpus < 0 \|\| item_len > percpu_len \|\|
72b100a1	314	percpu_len > (UINTPTR_MAX >> POOL_INDEX_BITS)) {
ef6695f1 MD	315	errno = EINVAL;
	316	return NULL;
	317	}
	318
9bd07c29 MD	319	if (mmap_attr) {
	320	mmap_func = mmap_attr->mmap_func;
	321	munmap_func = mmap_attr->munmap_func;
	322	mmap_priv = mmap_attr->mmap_priv;
	323	} else {
	324	mmap_func = default_mmap_func;
	325	munmap_func = default_munmap_func;
	326	mmap_priv = NULL;
	327	}
ef6695f1 MD	328	pthread_mutex_lock(&pool_lock);
ef6695f1 MD	329	/* Linear scan in array of pools to find empty spot. */
bb1552e2	330	for (i = FIRST_POOL; i < MAX_NR_POOLS; i++) {
ef6695f1 MD	331	pool = &rseq_percpu_pool[i];
	332	if (!pool->base)
	333	goto found_empty;
	334	}
	335	errno = ENOMEM;
	336	pool = NULL;
	337	goto end;
	338
	339	found_empty:
9bd07c29	340	base = mmap_func(mmap_priv, percpu_len * max_nr_cpus);
9649c7ee MD	341	if (!base)
9649c7ee MD	342	goto error_alloc;
ef6695f1 MD	343	pthread_mutex_init(&pool->lock, NULL);
	344	pool->base = base;
	345	pool->percpu_len = percpu_len;
	346	pool->max_nr_cpus = max_nr_cpus;
	347	pool->index = i;
	348	pool->item_len = item_len;
	349	pool->item_order = order;
9bd07c29 MD	350	pool->mmap_attr.mmap_func = mmap_func;
	351	pool->mmap_attr.munmap_func = munmap_func;
	352	pool->mmap_attr.mmap_priv = mmap_priv;
0fdf7a4c OD	353
0fdf7a4c OD	354	if (RSEQ_POOL_ROBUST & flags) {
9649c7ee MD	355	if (create_alloc_bitmap(pool))
9649c7ee MD	356	goto error_alloc;
0fdf7a4c	357	}
ef6695f1 MD	358	end:
	359	pthread_mutex_unlock(&pool_lock);
	360	return pool;
ef6695f1	361
9649c7ee MD	362	error_alloc:
9649c7ee MD	363	__rseq_percpu_pool_destroy(pool);
ef6695f1	364	pthread_mutex_unlock(&pool_lock);
9649c7ee MD	365	errno = ENOMEM;
9649c7ee MD	366	return NULL;
ef6695f1 MD	367	}
ef6695f1 MD	368
0fdf7a4c	369	static
9649c7ee	370	void set_alloc_slot(struct rseq_percpu_pool *pool, size_t item_offset)
0fdf7a4c	371	{
9649c7ee MD	372	unsigned long *bitmap = pool->alloc_bitmap;
9649c7ee MD	373	size_t item_index = item_offset >> pool->item_order;
0fdf7a4c OD	374	unsigned long mask;
	375	size_t k;
	376
9649c7ee	377	if (!bitmap)
0fdf7a4c	378	return;
0fdf7a4c	379
9649c7ee	380	k = item_index / BIT_PER_ULONG;
0fdf7a4c OD	381	mask = 1ULL << (item_index % BIT_PER_ULONG);
0fdf7a4c OD	382
9649c7ee MD	383	/* Print error if bit is already set. */
	384	if (bitmap[k] & mask) {
	385	fprintf(stderr, "%s: Allocator corruption detected for pool %p, item offset %zu.",
	386	__func__, pool, item_offset);
	387	abort();
	388	}
0fdf7a4c OD	389	bitmap[k] \|= mask;
	390	}
	391
ef6695f1	392	static
d24ee051	393	void __rseq_percpu __rseq_percpu_malloc(struct rseq_percpu_pool pool, bool zeroed)
ef6695f1 MD	394	{
	395	struct free_list_node *node;
	396	uintptr_t item_offset;
d24ee051	397	void __rseq_percpu *addr;
ef6695f1 MD	398
	399	pthread_mutex_lock(&pool->lock);
	400	/* Get first entry from free list. */
	401	node = pool->free_list_head;
	402	if (node != NULL) {
	403	/* Remove node from free list (update head). */
	404	pool->free_list_head = node->next;
	405	item_offset = (uintptr_t) ((void *) node - pool->base);
72b100a1	406	addr = (void *) (((uintptr_t) pool->index << POOL_INDEX_SHIFT) \| item_offset);
ef6695f1 MD	407	goto end;
	408	}
	409	if (pool->next_unused + pool->item_len > pool->percpu_len) {
ea1a3ada	410	errno = ENOMEM;
ef6695f1 MD	411	addr = NULL;
	412	goto end;
	413	}
	414	item_offset = pool->next_unused;
72b100a1	415	addr = (void *) (((uintptr_t) pool->index << POOL_INDEX_SHIFT) \| item_offset);
ef6695f1	416	pool->next_unused += pool->item_len;
9649c7ee	417	set_alloc_slot(pool, item_offset);
ef6695f1 MD	418	end:
	419	pthread_mutex_unlock(&pool->lock);
	420	if (zeroed && addr)
	421	rseq_percpu_zero_item(pool, item_offset);
	422	return addr;
	423	}
	424
d24ee051	425	void __rseq_percpu rseq_percpu_malloc(struct rseq_percpu_pool pool)
ef6695f1 MD	426	{
	427	return __rseq_percpu_malloc(pool, false);
	428	}
	429
d24ee051	430	void __rseq_percpu rseq_percpu_zmalloc(struct rseq_percpu_pool pool)
ef6695f1 MD	431	{
	432	return __rseq_percpu_malloc(pool, true);
	433	}
	434
0fdf7a4c	435	static
9649c7ee	436	void clear_alloc_slot(struct rseq_percpu_pool *pool, size_t item_offset)
0fdf7a4c	437	{
9649c7ee MD	438	unsigned long *bitmap = pool->alloc_bitmap;
9649c7ee MD	439	size_t item_index = item_offset >> pool->item_order;
0fdf7a4c OD	440	unsigned long mask;
	441	size_t k;
	442
9649c7ee	443	if (!bitmap)
0fdf7a4c	444	return;
0fdf7a4c	445
9649c7ee MD	446	k = item_index / BIT_PER_ULONG;
9649c7ee MD	447	mask = 1ULL << (item_index % BIT_PER_ULONG);
0fdf7a4c	448
9649c7ee MD	449	/* Print error if bit is not set. */
	450	if (!(bitmap[k] & mask)) {
	451	fprintf(stderr, "%s: Double-free detected for pool %p, item offset %zu.",
	452	__func__, pool, item_offset);
	453	abort();
	454	}
0fdf7a4c OD	455	bitmap[k] &= ~mask;
	456	}
	457
d24ee051	458	void rseq_percpu_free(void __rseq_percpu *_ptr)
ef6695f1 MD	459	{
ef6695f1 MD	460	uintptr_t ptr = (uintptr_t) _ptr;
72b100a1 MD	461	uintptr_t item_offset = ptr & MAX_POOL_LEN_MASK;
72b100a1 MD	462	uintptr_t pool_index = ptr >> POOL_INDEX_SHIFT;
ef6695f1 MD	463	struct rseq_percpu_pool *pool = &rseq_percpu_pool[pool_index];
	464	struct free_list_node head, item;
	465
	466	pthread_mutex_lock(&pool->lock);
9649c7ee	467	clear_alloc_slot(pool, item_offset);
ef6695f1 MD	468	/* Add ptr to head of free list */
ef6695f1 MD	469	head = pool->free_list_head;
8ab16a24	470	/* Free-list is in CPU 0 range. */
ef6695f1 MD	471	item = (struct free_list_node *)__rseq_pool_percpu_ptr(pool, 0, item_offset);
	472	item->next = head;
	473	pool->free_list_head = item;
	474	pthread_mutex_unlock(&pool->lock);
	475	}
	476
	477	struct rseq_percpu_pool_set *rseq_percpu_pool_set_create(void)
	478	{
	479	struct rseq_percpu_pool_set *pool_set;
	480
	481	pool_set = calloc(1, sizeof(struct rseq_percpu_pool_set));
	482	if (!pool_set)
	483	return NULL;
	484	pthread_mutex_init(&pool_set->lock, NULL);
	485	return pool_set;
	486	}
	487
	488	int rseq_percpu_pool_set_destroy(struct rseq_percpu_pool_set *pool_set)
	489	{
	490	int order, ret;
	491
	492	for (order = POOL_SET_MIN_ENTRY; order < POOL_SET_NR_ENTRIES; order++) {
	493	struct rseq_percpu_pool *pool = pool_set->entries[order];
	494
	495	if (!pool)
	496	continue;
	497	ret = rseq_percpu_pool_destroy(pool);
	498	if (ret)
	499	return ret;
	500	pool_set->entries[order] = NULL;
	501	}
	502	pthread_mutex_destroy(&pool_set->lock);
	503	free(pool_set);
	504	return 0;
	505	}
	506
	507	/* Ownership of pool is handed over to pool set on success. */
	508	int rseq_percpu_pool_set_add_pool(struct rseq_percpu_pool_set pool_set, struct rseq_percpu_pool pool)
	509	{
	510	size_t item_order = pool->item_order;
	511	int ret = 0;
	512
	513	pthread_mutex_lock(&pool_set->lock);
	514	if (pool_set->entries[item_order]) {
	515	errno = EBUSY;
	516	ret = -1;
	517	goto end;
	518	}
	519	pool_set->entries[pool->item_order] = pool;
	520	end:
	521	pthread_mutex_unlock(&pool_set->lock);
	522	return ret;
	523	}
	524
	525	static
d24ee051	526	void __rseq_percpu __rseq_percpu_pool_set_malloc(struct rseq_percpu_pool_set pool_set, size_t len, bool zeroed)
ef6695f1 MD	527	{
	528	int order, min_order = POOL_SET_MIN_ENTRY;
	529	struct rseq_percpu_pool *pool;
d24ee051	530	void __rseq_percpu *addr;
ef6695f1	531
d06f5cf5 MD	532	order = rseq_get_count_order_ulong(len);
	533	if (order > POOL_SET_MIN_ENTRY)
	534	min_order = order;
ef6695f1 MD	535	again:
	536	pthread_mutex_lock(&pool_set->lock);
	537	/* First smallest present pool where @len fits. */
	538	for (order = min_order; order < POOL_SET_NR_ENTRIES; order++) {
	539	pool = pool_set->entries[order];
	540
	541	if (!pool)
	542	continue;
	543	if (pool->item_len >= len)
	544	goto found;
	545	}
	546	pool = NULL;
	547	found:
	548	pthread_mutex_unlock(&pool_set->lock);
	549	if (pool) {
	550	addr = __rseq_percpu_malloc(pool, zeroed);
	551	if (addr == NULL && errno == ENOMEM) {
	552	/*
	553	* If the allocation failed, try again with a
	554	* larger pool.
	555	*/
	556	min_order = order + 1;
	557	goto again;
	558	}
	559	} else {
	560	/* Not found. */
	561	errno = ENOMEM;
	562	addr = NULL;
	563	}
	564	return addr;
	565	}
	566
d24ee051	567	void __rseq_percpu rseq_percpu_pool_set_malloc(struct rseq_percpu_pool_set pool_set, size_t len)
ef6695f1 MD	568	{
	569	return __rseq_percpu_pool_set_malloc(pool_set, len, false);
	570	}
	571
d24ee051	572	void __rseq_percpu rseq_percpu_pool_set_zmalloc(struct rseq_percpu_pool_set pool_set, size_t len)
ef6695f1 MD	573	{
	574	return __rseq_percpu_pool_set_malloc(pool_set, len, true);
	575	}
9bd07c29 MD	576
	577	struct rseq_mmap_attr rseq_mmap_attr_create(void (mmap_func)(void priv, size_t len),
	578	int (munmap_func)(void priv, void *ptr, size_t len),
	579	void *mmap_priv)
	580	{
	581	struct rseq_mmap_attr *attr = calloc(1, sizeof(struct rseq_mmap_attr));
	582
	583	if (!attr)
	584	return NULL;
	585	attr->mmap_func = mmap_func;
	586	attr->munmap_func = munmap_func;
	587	attr->mmap_priv = mmap_priv;
	588	return attr;
	589	}
	590
	591	void rseq_mmap_attr_destroy(struct rseq_mmap_attr *attr)
	592	{
	593	free(attr);
	594	}