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