aboutsummaryrefslogtreecommitdiff
path: root/lib/alloc/arena_alloc.c
blob: eceb5b932a946b9845385fb287894ca0650a4605 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <sys/mman.h>

#include <errno.h>
#include <stdckdint.h>
#include <stdlib.h>

#include "_attrs.h"
#include "alloc.h"
#include "macros.h"

#define IS_POW_2(n) ((n) != 0 && ((n) & ((n) - 1)) == 0)

[[_mlib_pure, _mlib_inline]] static size_t pad(size_t, size_t);
static struct _region *mkregion(size_t);

size_t
pad(size_t len, size_t align)
{
	return (len + align - 1) & ~(align - 1);
}

struct _region *
mkregion(size_t cap)
{
	struct _region *r = malloc(sizeof(struct _region));
	if (r == nullptr)
		return nullptr;
	*r = (struct _region){
		.cap = cap,
		.data = mmap(nullptr, cap, PROT_READ | PROT_WRITE,
	                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0),
	};
	if (r->data == MAP_FAILED) {
		free(r);
		return nullptr;
	}
	return r;
}

void *
arena_alloc(arena *a, size_t sz, size_t n, size_t align)
{
	ASSUME(a != nullptr);
	ASSUME(IS_POW_2(align));

	if (ckd_mul(&sz, sz, n)) {
		errno = EOVERFLOW;
		return nullptr;
	}

	for (struct _region *r = a->_head; r != nullptr; r = r->next) {
		size_t nlen, off = pad(r->len, align);

		/* Technically there are other ways to solve this… but at this point you
		   might as well just fail */
		if (ckd_add(&nlen, off, sz)) {
			errno = EOVERFLOW;
			return nullptr;
		}

		if (nlen <= r->cap) {
			void *ret = (char *)r->data + off;
			r->len = nlen;
			return ret;
		}
	}

	/* No page exists with enough space */
	struct _region *r = mkregion(MAX(sz, a->_init));
	if (r == nullptr)
		return nullptr;
	r->next = a->_head;
	r->len = sz;
	a->_head = r;
	return r->data;
}