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/*
28 * Really really *really* Q&D malloc() and free() implementations
29 * just to get going. Don't ever let anyone see this shit. :^)
30 */
31
32#include <AK/Assertions.h>
33#include <AK/Bitmap.h>
34#include <AK/Optional.h>
35#include <AK/Types.h>
36#include <Kernel/Arch/i386/CPU.h>
37#include <Kernel/Heap/kmalloc.h>
38#include <Kernel/KSyms.h>
39#include <Kernel/Process.h>
40#include <Kernel/Scheduler.h>
41#include <LibBareMetal/StdLib.h>
42
43#define SANITIZE_KMALLOC
44
45struct AllocationHeader {
46 size_t allocation_size_in_chunks;
47 u8 data[0];
48};
49
50#define BASE_PHYSICAL (0xc0000000 + (4 * MB))
51#define CHUNK_SIZE 32
52#define POOL_SIZE (3 * MB)
53
54#define ETERNAL_BASE_PHYSICAL (0xc0000000 + (2 * MB))
55#define ETERNAL_RANGE_SIZE (2 * MB)
56
57static u8 alloc_map[POOL_SIZE / CHUNK_SIZE / 8];
58
59volatile size_t sum_alloc = 0;
60volatile size_t sum_free = POOL_SIZE;
61volatile size_t kmalloc_sum_eternal = 0;
62
63u32 g_kmalloc_call_count;
64u32 g_kfree_call_count;
65bool g_dump_kmalloc_stacks;
66
67static u8* s_next_eternal_ptr;
68static u8* s_end_of_eternal_range;
69
70void kmalloc_init()
71{
72 memset(&alloc_map, 0, sizeof(alloc_map));
73 memset((void*)BASE_PHYSICAL, 0, POOL_SIZE);
74
75 kmalloc_sum_eternal = 0;
76 sum_alloc = 0;
77 sum_free = POOL_SIZE;
78
79 s_next_eternal_ptr = (u8*)ETERNAL_BASE_PHYSICAL;
80 s_end_of_eternal_range = s_next_eternal_ptr + ETERNAL_RANGE_SIZE;
81}
82
83void* kmalloc_eternal(size_t size)
84{
85 void* ptr = s_next_eternal_ptr;
86 s_next_eternal_ptr += size;
87 ASSERT(s_next_eternal_ptr < s_end_of_eternal_range);
88 kmalloc_sum_eternal += size;
89 return ptr;
90}
91
92void* kmalloc_aligned(size_t size, size_t alignment)
93{
94 void* ptr = kmalloc(size + alignment + sizeof(void*));
95 size_t max_addr = (size_t)ptr + alignment;
96 void* aligned_ptr = (void*)(max_addr - (max_addr % alignment));
97 ((void**)aligned_ptr)[-1] = ptr;
98 return aligned_ptr;
99}
100
101void kfree_aligned(void* ptr)
102{
103 kfree(((void**)ptr)[-1]);
104}
105
106void* kmalloc_page_aligned(size_t size)
107{
108 void* ptr = kmalloc_aligned(size, PAGE_SIZE);
109 size_t d = (size_t)ptr;
110 ASSERT((d & PAGE_MASK) == d);
111 return ptr;
112}
113
114inline void* kmalloc_allocate(size_t first_chunk, size_t chunks_needed)
115{
116 auto* a = (AllocationHeader*)(BASE_PHYSICAL + (first_chunk * CHUNK_SIZE));
117 u8* ptr = a->data;
118 a->allocation_size_in_chunks = chunks_needed;
119
120 Bitmap bitmap_wrapper = Bitmap::wrap(alloc_map, POOL_SIZE / CHUNK_SIZE);
121 bitmap_wrapper.set_range(first_chunk, chunks_needed, true);
122
123 sum_alloc += a->allocation_size_in_chunks * CHUNK_SIZE;
124 sum_free -= a->allocation_size_in_chunks * CHUNK_SIZE;
125#ifdef SANITIZE_KMALLOC
126 memset(ptr, KMALLOC_SCRUB_BYTE, (a->allocation_size_in_chunks * CHUNK_SIZE) - sizeof(AllocationHeader));
127#endif
128 return ptr;
129}
130
131void* kmalloc_impl(size_t size)
132{
133 Kernel::InterruptDisabler disabler;
134 ++g_kmalloc_call_count;
135
136 if (g_dump_kmalloc_stacks && Kernel::g_kernel_symbols_available) {
137 dbg() << "kmalloc(" << size << ")";
138 Kernel::dump_backtrace();
139 }
140
141 // We need space for the AllocationHeader at the head of the block.
142 size_t real_size = size + sizeof(AllocationHeader);
143
144 if (sum_free < real_size) {
145 Kernel::dump_backtrace();
146 klog() << "kmalloc(): PANIC! Out of memory (sucks, dude)\nsum_free=" << sum_free << ", real_size=" << real_size;
147 Kernel::hang();
148 }
149
150 size_t chunks_needed = (real_size + CHUNK_SIZE - 1) / CHUNK_SIZE;
151
152 Bitmap bitmap_wrapper = Bitmap::wrap(alloc_map, POOL_SIZE / CHUNK_SIZE);
153 Optional<size_t> first_chunk;
154
155 // Choose the right politic for allocation.
156 constexpr u32 best_fit_threshold = 128;
157 if (chunks_needed < best_fit_threshold) {
158 first_chunk = bitmap_wrapper.find_first_fit(chunks_needed);
159 } else {
160 first_chunk = bitmap_wrapper.find_best_fit(chunks_needed);
161 }
162
163 if (!first_chunk.has_value()) {
164 klog() << "kmalloc(): PANIC! Out of memory (no suitable block for size " << size << ")";
165 Kernel::dump_backtrace();
166 Kernel::hang();
167 }
168
169 return kmalloc_allocate(first_chunk.value(), chunks_needed);
170}
171
172void kfree(void* ptr)
173{
174 if (!ptr)
175 return;
176
177 Kernel::InterruptDisabler disabler;
178 ++g_kfree_call_count;
179
180 auto* a = (AllocationHeader*)((((u8*)ptr) - sizeof(AllocationHeader)));
181 FlatPtr start = ((FlatPtr)a - (FlatPtr)BASE_PHYSICAL) / CHUNK_SIZE;
182
183 Bitmap bitmap_wrapper = Bitmap::wrap(alloc_map, POOL_SIZE / CHUNK_SIZE);
184 bitmap_wrapper.set_range(start, a->allocation_size_in_chunks, false);
185
186 sum_alloc -= a->allocation_size_in_chunks * CHUNK_SIZE;
187 sum_free += a->allocation_size_in_chunks * CHUNK_SIZE;
188
189#ifdef SANITIZE_KMALLOC
190 memset(a, KFREE_SCRUB_BYTE, a->allocation_size_in_chunks * CHUNK_SIZE);
191#endif
192}
193
194void* krealloc(void* ptr, size_t new_size)
195{
196 if (!ptr)
197 return kmalloc(new_size);
198
199 Kernel::InterruptDisabler disabler;
200
201 auto* a = (AllocationHeader*)((((u8*)ptr) - sizeof(AllocationHeader)));
202 size_t old_size = a->allocation_size_in_chunks * CHUNK_SIZE;
203
204 if (old_size == new_size)
205 return ptr;
206
207 auto* new_ptr = kmalloc(new_size);
208 memcpy(new_ptr, ptr, min(old_size, new_size));
209 kfree(ptr);
210 return new_ptr;
211}
212
213void* operator new(size_t size)
214{
215 return kmalloc(size);
216}
217
218void* operator new[](size_t size)
219{
220 return kmalloc(size);
221}