Debian Codegraph @

rt/malloc.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 // This is a simple memory allocator, based on
5 // Appel, Andrew W., and David A. Naumann. "Verified sequential malloc/free"
6 // but with logarithmic bin sizing and additional safety checks. Not thread-safe
7
8 // Size of the header/footer for allocations.
9 def META: size = size(size);
10
11 // Alignment for pointers returned by malloc.
12 // XXX: arch
13 def ALIGN: size = 16;
14
15 // Allocation granularity for large allocs. Only used to allow verifying large
16 // heap pointers, doesn't necessarily need to match system page size.
17 def PAGESZ: size = 4096;
18
19 // Amount of memory to allocate at a time for chunks (2MiB).
20 def CHUNKSZ: size = 1 << 21;
21
22 // Byte to fill allocations with while they're not in use.
23 def POISON: u8 = 0x69;
24
25 // Allocates n bytes of memory and returns a pointer to them, or null if there
26 // is insufficient memory.
27 export fn malloc(n: size) nullable *opaque = {
28 if (n == 0) return null;
29 if (size_islarge(n)) {
30 // Round up to PAGESZ and just use mmap directly
31 n = realsz(n);
32 let m = match (segmalloc(n + ALIGN + META)) {
33 case null =>
34 return null;
35 case let p: *opaque =>
36 yield (p: uintptr + ALIGN - META): *meta;
37 };
38
39 m.sz = n;
40 *(&m.user[n]: *size) = n; // For out-of-bounds write detection
41 heap.cur_allocs += 1;
42 return &m.user;
43 };
44
45 let bin = size_getbin(n), sz = bin_getsize(bin);
46 let m = match (heap.bins[bin]) {
47 case null =>
48 if (heap.cur_chunk.1 + META + sz + META > CHUNKSZ) {
49 // No space left in this chunk, allocate a new one
50 match (segmalloc(CHUNKSZ)) {
51 case null =>
52 return null;
53 case let p: *opaque =>
54 heap.cur_chunk = (p: *chunk, size(size));
55 };
56 };
57
58 // Allocate a new block from the currently-active chunk
59 let m = &heap.cur_chunk.0.data[heap.cur_chunk.1]: *meta;
60 heap.cur_chunk.1 += META + sz;
61 m.sz = sz;
62 *(&m.user[sz]: *size) = sz;
63 yield m;
64 case let m: *meta =>
65 // Pop a block off the freelist
66 heap.bins[bin] = meta_next(m);
67 checkpoison(m, sz);
68 m.sz = sz;
69 yield m;
70 };
71
72 heap.cur_allocs += 1;
73 return &m.user;
74 };
75
76 // Frees an allocation returned by [[malloc]]. Freeing any other pointer, or
77 // freeing a pointer that's already been freed, will cause an abort.
78 export @symbol("rt.free") fn free_(p: nullable *opaque) void = {
79 let m = match (p) {
80 case null =>
81 return;
82 case let p: *opaque =>
83 yield getmeta(p);
84 };
85 heap.cur_allocs -= 1;
86
87 if (size_islarge(m.sz)) {
88 // Pass through to munmap
89 segfree((p: uintptr - ALIGN): *opaque, m.sz + ALIGN + META);
90 return;
91 };
92
93 // Push onto freelist
94 let bin = size_getbin(m.sz);
95 m.user[..m.sz] = [POISON...];
96 m.next = heap.bins[bin]: uintptr | 0b1;
97 heap.bins[bin] = m;
98 };
99
100 // Changes the allocation size of a pointer to n bytes. If n is smaller than
101 // the prior allocation, it is truncated; otherwise the allocation is expanded
102 // and the values of the new bytes are undefined. May return a different pointer
103 // than the one given if there is insufficient space to expand the pointer
104 // in-place. Returns null if there is insufficient memory to support the
105 // request.
106 export fn realloc(p: nullable *opaque, n: size) nullable *opaque = {
107 if (n == 0) {
108 free(p);
109 return null;
110 };
111 let m = match (p) {
112 case null =>
113 return malloc(n);
114 case let p: *opaque =>
115 yield getmeta(p);
116 };
117 if (realsz(n) == m.sz) return p;
118
119 let new = match (malloc(n)) {
120 case null =>
121 return null;
122 case let new: *opaque =>
123 yield new;
124 };
125 memcpy(new, &m.user, if (n < m.sz) n else m.sz);
126 free(p);
127 return new;
128 };
129
130 // Gets the metadata for a given allocation. The provided pointer must have been
131 // returned by [[malloc]] or [[realloc]] and must not have been freed.
132 export fn getmeta(p: *opaque) *meta = {
133 let m = (p: uintptr - META): *meta;
134 validatemeta(m, false);
135 assert(m.sz & 0b1 == 0,
136 "tried to get metadata for already-freed pointer (double free?)");
137 return m;
138 };
139
140
141 // Find the maximum allocation size for a given bin.
142 fn bin_getsize(bin: size) size = {
143 // Would need to have bin 0 be ALIGN rather than 0 in this case
144 static assert(ALIGN != META);
145
146 // Space bins logarithmically
147 let sz = if (bin == 0) 0z else 1 << (bin - 1);
148
149 // And make sure that (bin_getsize(n) + META) % ALIGN == 0, while erring on
150 // the side of bin sizes slightly larger than powers of two
151 return sz * ALIGN + ALIGN - META;
152 };
153
154 // Find the bin for a given allocation size.
155 fn size_getbin(sz: size) size = {
156 // Undo alignment fudging. Equivalent to
157 // ceil((sz - ALIGN + META) / ALIGN)
158 sz = (sz + META - 1) / ALIGN;
159
160 // Then undo exponentiation
161 if (sz == 0) return 0;
162 let ret = 0z;
163 for (1 << ret < sz; ret += 1) void;
164 return ret + 1;
165 };
166
167 // Returns true if a given allocation size should use mmap directly.
168 fn size_islarge(sz: size) bool = sz > bin_getsize(len(heap.bins) - 1);
169
170 // Gets the next block on the freelist.
171 fn meta_next(m: *meta) nullable *meta = {
172 assert(m.next & 0b1 == 0b1,
173 "expected metadata on freelist to be marked as free (heap corruption?)");
174 return (m.next & ~0b1): nullable *meta;
175 };
176
177 // Round a user-requested allocation size up to the next-smallest size we can
178 // allocate.
179 fn realsz(sz: size) size = {
180 if (size_islarge(sz)) {
181 sz += ALIGN + META;
182 if (sz % PAGESZ != 0) sz += PAGESZ - sz % PAGESZ;
183 return sz - ALIGN - META;
184 };
185
186 return bin_getsize(size_getbin(sz));
187 };
188
189
190 // Check for memory errors related to a given block of memory.
191 fn validatemeta(m: *meta, shallow: bool) void = {
192 assert(&m.user: uintptr % ALIGN == 0,
193 "invalid alignment for metadata pointer (heap corruption?)");
194 // If we were recursively called to check a next pointer, the block
195 // needs to be marked as free, abort in meta_next() if it's not
196 if (m.sz & 0b1 == 0b1 || shallow == true) {
197 // Block is currently free, verify that it points to a valid
198 // next block
199 match (meta_next(m)) {
200 case null => void;
201 case let next: *meta =>
202 assert(next: uintptr % ALIGN == META,
203 "invalid metadata for small allocation on freelist (heap corruption?)");
204 if (!shallow) validatemeta(next, true);
205 };
206 return;
207 };
208
209 // Block is currently allocated, verify that its size is valid
210 let second = &m.user[m.sz]: *meta;
211 if (size_islarge(m.sz)) {
212 assert((&m.user: uintptr - ALIGN) % PAGESZ == 0,
213 "invalid large allocation address (non-heap pointer?)");
214 assert((m.sz + ALIGN + META) % PAGESZ == 0,
215 "invalid metadata for large allocation (non-heap pointer?)");
216 assert(second.sz == m.sz,
217 "invalid secondary metadata for large allocation (out-of-bounds write?)");
218 return;
219 };
220
221 assert(bin_getsize(size_getbin(m.sz)) == m.sz,
222 "invalid metadata for small allocation (non-heap pointer?)");
223 if (second.sz & 0b1 == 0b1) {
224 // Next block after it in the chunk is free, recursively verify
225 // that it's valid
226 validatemeta(second, false);
227 return;
228 };
229
230 // Note that we can't recurse here because the "next block" might
231 // actually be the extra metadata at the end of the chunk (which is
232 // never marked as being on the freelist
233 assert(!size_islarge(second.sz),
234 "invalid secondary metadata for small allocation (out-of-bounds write?)");
235 assert(bin_getsize(size_getbin(second.sz)) == second.sz,
236 "invalid secondary metadata for small allocation (out-of-bounds write?)");
237 };
238
239 // Verify that a pointer on a free list hasn't been touched since it was added.
240 fn checkpoison(m: *meta, sz: size) void = {
241 match (meta_next(m)) {
242 case null => void;
243 case let next: *meta =>
244 validatemeta(next, false);
245 };
246 for (let i = 0z; i < sz; i += 1) {
247 assert(m.user[i] == POISON, "invalid poison data on freelist (use after free?)");
248 };
249 };
250
251 @fini fn checkleaks() void = {
252 for (let i = 0z; i < len(heap.bins); i += 1) {
253 for (let m = heap.bins[i]; m != null; m = meta_next(m as *meta)) {
254 checkpoison(m as *meta, bin_getsize(i));
255 };
256 };
257 // TODO: Need a debugging malloc that tracks backtraces for
258 // currently-active allocations in order to help with finding leaks
259 // before we enable this by default. Also need to make sure that this is
260 // run after the rest of @fini in order to guarantee that we see all
261 // frees
262 //assert(heap.cur_allocs == 0, "memory leak");
263 };