jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this
9 * list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
21 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
22 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
23 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include <AK/Bitmap.h>
28#include <AK/InlineLinkedList.h>
29#include <AK/ScopedValueRollback.h>
30#include <AK/Vector.h>
31#include <LibThread/Lock.h>
32#include <assert.h>
33#include <mallocdefs.h>
34#include <serenity.h>
35#include <stdio.h>
36#include <stdlib.h>
37#include <sys/mman.h>
38
39// FIXME: Thread safety.
40
41//#define MALLOC_DEBUG
42#define RECYCLE_BIG_ALLOCATIONS
43
44#define MAGIC_PAGE_HEADER 0x42657274
45#define MAGIC_BIGALLOC_HEADER 0x42697267
46#define PAGE_ROUND_UP(x) ((((size_t)(x)) + PAGE_SIZE - 1) & (~(PAGE_SIZE - 1)))
47
48static LibThread::Lock& malloc_lock()
49{
50 static u32 lock_storage[sizeof(LibThread::Lock) / sizeof(u32)];
51 return *reinterpret_cast<LibThread::Lock*>(&lock_storage);
52}
53
54constexpr int number_of_chunked_blocks_to_keep_around_per_size_class = 4;
55constexpr int number_of_big_blocks_to_keep_around_per_size_class = 8;
56
57static bool s_log_malloc = false;
58static bool s_scrub_malloc = true;
59static bool s_scrub_free = true;
60static bool s_profiling = false;
61static unsigned short size_classes[] = { 8, 16, 32, 64, 128, 252, 508, 1016, 2036, 4090, 8188, 16376, 32756, 0 };
62static constexpr size_t num_size_classes = sizeof(size_classes) / sizeof(unsigned short);
63
64constexpr size_t block_size = 64 * KB;
65constexpr size_t block_mask = ~(block_size - 1);
66
67struct CommonHeader {
68 size_t m_magic;
69 size_t m_size;
70};
71
72struct BigAllocationBlock : public CommonHeader {
73 BigAllocationBlock(size_t size)
74 {
75 m_magic = MAGIC_BIGALLOC_HEADER;
76 m_size = size;
77 }
78 unsigned char* m_slot[0];
79};
80
81struct FreelistEntry {
82 FreelistEntry* next;
83};
84
85struct ChunkedBlock
86 : public CommonHeader
87 , public InlineLinkedListNode<ChunkedBlock> {
88
89 ChunkedBlock(size_t bytes_per_chunk)
90 {
91 m_magic = MAGIC_PAGE_HEADER;
92 m_size = bytes_per_chunk;
93 m_free_chunks = chunk_capacity();
94 m_freelist = (FreelistEntry*)chunk(0);
95 for (size_t i = 0; i < chunk_capacity(); ++i) {
96 auto* entry = (FreelistEntry*)chunk(i);
97 if (i != chunk_capacity() - 1)
98 entry->next = (FreelistEntry*)chunk(i + 1);
99 else
100 entry->next = nullptr;
101 }
102 }
103
104 ChunkedBlock* m_prev { nullptr };
105 ChunkedBlock* m_next { nullptr };
106 FreelistEntry* m_freelist { nullptr };
107 unsigned short m_free_chunks { 0 };
108 unsigned char m_slot[0];
109
110 void* chunk(int index)
111 {
112 return &m_slot[index * m_size];
113 }
114 bool is_full() const { return m_free_chunks == 0; }
115 size_t bytes_per_chunk() const { return m_size; }
116 size_t free_chunks() const { return m_free_chunks; }
117 size_t used_chunks() const { return chunk_capacity() - m_free_chunks; }
118 size_t chunk_capacity() const { return (block_size - sizeof(ChunkedBlock)) / m_size; }
119};
120
121struct Allocator {
122 size_t size { 0 };
123 size_t block_count { 0 };
124 size_t empty_block_count { 0 };
125 ChunkedBlock* empty_blocks[number_of_chunked_blocks_to_keep_around_per_size_class] { nullptr };
126 InlineLinkedList<ChunkedBlock> usable_blocks;
127 InlineLinkedList<ChunkedBlock> full_blocks;
128};
129
130struct BigAllocator {
131 Vector<BigAllocationBlock*, number_of_big_blocks_to_keep_around_per_size_class> blocks;
132};
133
134// Allocators will be initialized in __malloc_init.
135// We can not rely on global constructors to initialize them,
136// because they must be initialized before other global constructors
137// are run. Similarly, we can not allow global destructors to destruct
138// them. We could have used AK::NeverDestoyed to prevent the latter,
139// but it would have not helped with the former.
140static u8 g_allocators_storage[sizeof(Allocator) * num_size_classes];
141static u8 g_big_allocators_storage[sizeof(BigAllocator)];
142
143static inline Allocator (&allocators())[num_size_classes]
144{
145 return reinterpret_cast<Allocator(&)[num_size_classes]>(g_allocators_storage);
146}
147
148static inline BigAllocator (&big_allocators())[1]
149{
150 return reinterpret_cast<BigAllocator(&)[1]>(g_big_allocators_storage);
151}
152
153static Allocator* allocator_for_size(size_t size, size_t& good_size)
154{
155 for (int i = 0; size_classes[i]; ++i) {
156 if (size <= size_classes[i]) {
157 good_size = size_classes[i];
158 return &allocators()[i];
159 }
160 }
161 good_size = PAGE_ROUND_UP(size);
162 return nullptr;
163}
164
165static BigAllocator* big_allocator_for_size(size_t size)
166{
167 if (size == 65536)
168 return &big_allocators()[0];
169 return nullptr;
170}
171
172extern "C" {
173
174size_t malloc_good_size(size_t size)
175{
176 for (int i = 0; size_classes[i]; ++i) {
177 if (size < size_classes[i])
178 return size_classes[i];
179 }
180 return PAGE_ROUND_UP(size);
181}
182
183static void* os_alloc(size_t size, const char* name)
184{
185 auto* ptr = serenity_mmap(nullptr, size, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE | MAP_PURGEABLE, 0, 0, block_size, name);
186 ASSERT(ptr != MAP_FAILED);
187 return ptr;
188}
189
190static void os_free(void* ptr, size_t size)
191{
192 int rc = munmap(ptr, size);
193 assert(rc == 0);
194}
195
196static void* malloc_impl(size_t size)
197{
198 LOCKER(malloc_lock());
199
200 if (s_log_malloc)
201 dbgprintf("LibC: malloc(%zu)\n", size);
202
203 if (!size)
204 return nullptr;
205
206 size_t good_size;
207 auto* allocator = allocator_for_size(size, good_size);
208
209 if (!allocator) {
210 size_t real_size = round_up_to_power_of_two(sizeof(BigAllocationBlock) + size, block_size);
211#ifdef RECYCLE_BIG_ALLOCATIONS
212 if (auto* allocator = big_allocator_for_size(real_size)) {
213 if (!allocator->blocks.is_empty()) {
214 auto* block = allocator->blocks.take_last();
215 int rc = madvise(block, real_size, MADV_SET_NONVOLATILE);
216 bool this_block_was_purged = rc == 1;
217 if (rc < 0) {
218 perror("madvise");
219 ASSERT_NOT_REACHED();
220 }
221 if (mprotect(block, real_size, PROT_READ | PROT_WRITE) < 0) {
222 perror("mprotect");
223 ASSERT_NOT_REACHED();
224 }
225 if (this_block_was_purged)
226 new (block) BigAllocationBlock(real_size);
227 return &block->m_slot[0];
228 }
229 }
230#endif
231 auto* block = (BigAllocationBlock*)os_alloc(real_size, "malloc: BigAllocationBlock");
232 new (block) BigAllocationBlock(real_size);
233 return &block->m_slot[0];
234 }
235
236 ChunkedBlock* block = nullptr;
237
238 for (block = allocator->usable_blocks.head(); block; block = block->next()) {
239 if (block->free_chunks())
240 break;
241 }
242
243 if (!block && allocator->empty_block_count) {
244 block = allocator->empty_blocks[--allocator->empty_block_count];
245 int rc = madvise(block, block_size, MADV_SET_NONVOLATILE);
246 bool this_block_was_purged = rc == 1;
247 if (rc < 0) {
248 perror("madvise");
249 ASSERT_NOT_REACHED();
250 }
251 rc = mprotect(block, block_size, PROT_READ | PROT_WRITE);
252 if (rc < 0) {
253 perror("mprotect");
254 ASSERT_NOT_REACHED();
255 }
256 if (this_block_was_purged)
257 new (block) ChunkedBlock(good_size);
258 allocator->usable_blocks.append(block);
259 }
260
261 if (!block) {
262 char buffer[64];
263 snprintf(buffer, sizeof(buffer), "malloc: ChunkedBlock(%zu)", good_size);
264 block = (ChunkedBlock*)os_alloc(block_size, buffer);
265 new (block) ChunkedBlock(good_size);
266 allocator->usable_blocks.append(block);
267 ++allocator->block_count;
268 }
269
270 --block->m_free_chunks;
271 void* ptr = block->m_freelist;
272 block->m_freelist = block->m_freelist->next;
273 if (block->is_full()) {
274#ifdef MALLOC_DEBUG
275 dbgprintf("Block %p is now full in size class %zu\n", block, good_size);
276#endif
277 allocator->usable_blocks.remove(block);
278 allocator->full_blocks.append(block);
279 }
280#ifdef MALLOC_DEBUG
281 dbgprintf("LibC: allocated %p (chunk in block %p, size %zu)\n", ptr, block, block->bytes_per_chunk());
282#endif
283 if (s_scrub_malloc)
284 memset(ptr, MALLOC_SCRUB_BYTE, block->m_size);
285 return ptr;
286}
287
288static void free_impl(void* ptr)
289{
290 ScopedValueRollback rollback(errno);
291
292 if (!ptr)
293 return;
294
295 LOCKER(malloc_lock());
296
297 void* block_base = (void*)((uintptr_t)ptr & block_mask);
298 size_t magic = *(size_t*)block_base;
299
300 if (magic == MAGIC_BIGALLOC_HEADER) {
301 auto* block = (BigAllocationBlock*)block_base;
302#ifdef RECYCLE_BIG_ALLOCATIONS
303 if (auto* allocator = big_allocator_for_size(block->m_size)) {
304 if (allocator->blocks.size() < number_of_big_blocks_to_keep_around_per_size_class) {
305 allocator->blocks.append(block);
306 if (mprotect(block, block->m_size, PROT_NONE) < 0) {
307 perror("mprotect");
308 ASSERT_NOT_REACHED();
309 }
310 if (madvise(block, block->m_size, MADV_SET_VOLATILE) != 0) {
311 perror("madvise");
312 ASSERT_NOT_REACHED();
313 }
314 return;
315 }
316 }
317#endif
318 os_free(block, block->m_size);
319 return;
320 }
321
322 assert(magic == MAGIC_PAGE_HEADER);
323 auto* block = (ChunkedBlock*)block_base;
324
325#ifdef MALLOC_DEBUG
326 dbgprintf("LibC: freeing %p in allocator %p (size=%u, used=%u)\n", ptr, block, block->bytes_per_chunk(), block->used_chunks());
327#endif
328
329 if (s_scrub_free)
330 memset(ptr, FREE_SCRUB_BYTE, block->bytes_per_chunk());
331
332 auto* entry = (FreelistEntry*)ptr;
333 entry->next = block->m_freelist;
334 block->m_freelist = entry;
335
336 if (block->is_full()) {
337 size_t good_size;
338 auto* allocator = allocator_for_size(block->m_size, good_size);
339#ifdef MALLOC_DEBUG
340 dbgprintf("Block %p no longer full in size class %u\n", block, good_size);
341#endif
342 allocator->full_blocks.remove(block);
343 allocator->usable_blocks.prepend(block);
344 }
345
346 ++block->m_free_chunks;
347
348 if (!block->used_chunks()) {
349 size_t good_size;
350 auto* allocator = allocator_for_size(block->m_size, good_size);
351 if (allocator->block_count < number_of_chunked_blocks_to_keep_around_per_size_class) {
352#ifdef MALLOC_DEBUG
353 dbgprintf("Keeping block %p around for size class %u\n", block, good_size);
354#endif
355 allocator->usable_blocks.remove(block);
356 allocator->empty_blocks[allocator->empty_block_count++] = block;
357 mprotect(block, block_size, PROT_NONE);
358 madvise(block, block_size, MADV_SET_VOLATILE);
359 return;
360 }
361#ifdef MALLOC_DEBUG
362 dbgprintf("Releasing block %p for size class %u\n", block, good_size);
363#endif
364 allocator->usable_blocks.remove(block);
365 --allocator->block_count;
366 os_free(block, block_size);
367 }
368}
369
370void* malloc(size_t size)
371{
372 void* ptr = malloc_impl(size);
373 if (s_profiling)
374 perf_event(PERF_EVENT_MALLOC, size, reinterpret_cast<uintptr_t>(ptr));
375 return ptr;
376}
377
378void free(void* ptr)
379{
380 if (s_profiling)
381 perf_event(PERF_EVENT_FREE, reinterpret_cast<uintptr_t>(ptr), 0);
382 free_impl(ptr);
383}
384
385void* calloc(size_t count, size_t size)
386{
387 size_t new_size = count * size;
388 auto* ptr = malloc(new_size);
389 memset(ptr, 0, new_size);
390 return ptr;
391}
392
393size_t malloc_size(void* ptr)
394{
395 if (!ptr)
396 return 0;
397 LOCKER(malloc_lock());
398 void* page_base = (void*)((uintptr_t)ptr & block_mask);
399 auto* header = (const CommonHeader*)page_base;
400 auto size = header->m_size;
401 if (header->m_magic == MAGIC_BIGALLOC_HEADER)
402 size -= sizeof(CommonHeader);
403 return size;
404}
405
406void* realloc(void* ptr, size_t size)
407{
408 if (!ptr)
409 return malloc(size);
410 LOCKER(malloc_lock());
411 auto existing_allocation_size = malloc_size(ptr);
412 if (size <= existing_allocation_size)
413 return ptr;
414 auto* new_ptr = malloc(size);
415 memcpy(new_ptr, ptr, min(existing_allocation_size, size));
416 free(ptr);
417 return new_ptr;
418}
419
420void __malloc_init()
421{
422 new (&malloc_lock()) LibThread::Lock();
423 if (getenv("LIBC_NOSCRUB_MALLOC"))
424 s_scrub_malloc = false;
425 if (getenv("LIBC_NOSCRUB_FREE"))
426 s_scrub_free = false;
427 if (getenv("LIBC_LOG_MALLOC"))
428 s_log_malloc = true;
429 if (getenv("LIBC_PROFILE_MALLOC"))
430 s_profiling = true;
431
432 for (size_t i = 0; i < num_size_classes; ++i) {
433 new (&allocators()[i]) Allocator();
434 allocators()[i].size = size_classes[i];
435 }
436
437 new (&big_allocators()[0])(BigAllocator);
438}
439}