1 #include <libc/src/stdlib.h>
2 #include <libsystem/syscall.h>
3 #include <libc/src/stddef.h>
4 #include <libc/src/unistd.h>
5 #include <libc/src/errno.h>
6 #include <libc/src/stdio.h>
7
8 #define PAGE_4K_SHIFT 12
9 #define PAGE_2M_SHIFT 21
10 #define PAGE_1G_SHIFT 30
11 #define PAGE_GDT_SHIFT 39
12
13 // 不同大小的页的容量
14 #define PAGE_4K_SIZE (1UL << PAGE_4K_SHIFT)
15 #define PAGE_2M_SIZE (1UL << PAGE_2M_SHIFT)
16 #define PAGE_1G_SIZE (1UL << PAGE_1G_SHIFT)
17
18 // 屏蔽低于x的数值
19 #define PAGE_4K_MASK (~(PAGE_4K_SIZE - 1))
20 #define PAGE_2M_MASK (~(PAGE_2M_SIZE - 1))
21
22 // 将addr按照x的上边界对齐
23 #define PAGE_4K_ALIGN(addr) (((unsigned long)(addr) + PAGE_4K_SIZE - 1) & PAGE_4K_MASK)
24 #define PAGE_2M_ALIGN(addr) (((unsigned long)(addr) + PAGE_2M_SIZE - 1) & PAGE_2M_MASK)
25
26 /**
27 * @brief 显式链表的结点
28 *
29 */
30 typedef struct malloc_mem_chunk_t
31 {
32 uint64_t length; // 整个块所占用的内存区域的大小
33 struct malloc_mem_chunk_t *prev; // 上一个结点的指针
34 struct malloc_mem_chunk_t *next; // 下一个结点的指针
35 } malloc_mem_chunk_t;
36
37 static uint64_t brk_base_addr = 0; // 堆区域的内存基地址
38 static uint64_t brk_max_addr = 0; // 堆区域的内存最大地址
39 static uint64_t brk_managed_addr = 0; // 堆区域已经被管理的地址
40
41 // 空闲链表
42 // 按start_addr升序排序
43 static malloc_mem_chunk_t *malloc_free_list = NULL;
44 static malloc_mem_chunk_t *malloc_free_list_end = NULL; // 空闲链表的末尾结点
45
46 static uint64_t count_last_free_size = 0; // 统计距离上一次回收内存，已经free了多少内存
47
48 /**
49 * @brief 将块插入空闲链表
50 *
51 * @param ck 待插入的块
52 */
53 static void malloc_insert_free_list(malloc_mem_chunk_t *ck);
54
55 /**
56 * @brief 当堆顶空闲空间大于2个页的空间的时候，释放1个页
57 *
58 */
59 static void release_brk();
60
61 /**
62 * @brief 在链表中检索符合要求的空闲块（best fit）
63 *
64 * @param size 块的大小
65 * @return malloc_mem_chunk_t*
66 */
malloc_query_free_chunk_bf(uint64_t size)67 static malloc_mem_chunk_t *malloc_query_free_chunk_bf(uint64_t size)
68 {
69 // 在满足best fit的前提下，尽可能的使分配的内存在低地址
70 // 使得总的堆内存可以更快被释放
71
72 if (malloc_free_list == NULL)
73 {
74 return NULL;
75 }
76 malloc_mem_chunk_t *ptr = malloc_free_list;
77 malloc_mem_chunk_t *best = NULL;
78 // printf("query size=%d", size);
79 while (ptr != NULL)
80 {
81 // printf("ptr->length=%#010lx\n", ptr->length);
82 if (ptr->length == size)
83 {
84 best = ptr;
85 break;
86 }
87
88 if (ptr->length > size)
89 {
90 if (best == NULL)
91 best = ptr;
92 else if (best->length > ptr->length)
93 best = ptr;
94 }
95 ptr = ptr->next;
96 }
97
98 return best;
99 }
100
101 /**
102 * @brief 在链表中检索符合要求的空闲块（first fit）
103 *
104 * @param size
105 * @return malloc_mem_chunk_t*
106 */
malloc_query_free_chunk_ff(uint64_t size)107 static malloc_mem_chunk_t *malloc_query_free_chunk_ff(uint64_t size)
108 {
109 if (malloc_free_list == NULL)
110 return NULL;
111 malloc_mem_chunk_t *ptr = malloc_free_list;
112
113 while (ptr)
114 {
115 if (ptr->length >= size)
116 {
117 return ptr;
118 }
119 ptr = ptr->next;
120 }
121
122 return NULL;
123 }
124
125 /**
126 * @brief 扩容malloc管理的内存区域
127 *
128 * @param size 扩大的内存大小
129 */
malloc_enlarge(int64_t size)130 static int malloc_enlarge(int64_t size)
131 {
132 if (brk_base_addr == 0) // 第一次调用，需要初始化
133 {
134 brk_base_addr = brk(-1);
135 // printf("brk_base_addr=%#018lx\n", brk_base_addr);
136 brk_managed_addr = brk_base_addr;
137 brk_max_addr = brk(-2);
138 }
139
140 int64_t free_space = brk_max_addr - brk_managed_addr;
141 // printf("size=%ld\tfree_space=%ld\n", size, free_space);
142 if (free_space < size) // 现有堆空间不足
143 {
144 if (sbrk(size - free_space) != (void *)(-1))
145 brk_max_addr = brk((-2));
146 else
147 {
148 put_string("malloc_enlarge(): no_mem\n", COLOR_YELLOW, COLOR_BLACK);
149 return -ENOMEM;
150 }
151
152 // printf("brk max addr = %#018lx\n", brk_max_addr);
153 }
154
155 // 扩展管理的堆空间
156 // 在新分配的内存的底部放置header
157 // printf("managed addr = %#018lx\n", brk_managed_addr);
158 malloc_mem_chunk_t *new_ck = (malloc_mem_chunk_t *)brk_managed_addr;
159 new_ck->length = brk_max_addr - brk_managed_addr;
160 // printf("new_ck->start_addr=%#018lx\tbrk_max_addr=%#018lx\tbrk_managed_addr=%#018lx\n", (uint64_t)new_ck, brk_max_addr, brk_managed_addr);
161 new_ck->prev = NULL;
162 new_ck->next = NULL;
163 brk_managed_addr = brk_max_addr;
164
165 malloc_insert_free_list(new_ck);
166
167 return 0;
168 }
169
170 /**
171 * @brief 合并空闲块
172 *
173 */
malloc_merge_free_chunk()174 static void malloc_merge_free_chunk()
175 {
176 if (malloc_free_list == NULL)
177 return;
178 malloc_mem_chunk_t *ptr = malloc_free_list->next;
179 while (ptr != NULL)
180 {
181 // 内存块连续
182 if (((uint64_t)(ptr->prev) + ptr->prev->length == (uint64_t)ptr))
183 {
184 // printf("merged %#018lx and %#018lx\n", (uint64_t)ptr, (uint64_t)(ptr->prev));
185 // 将ptr与前面的空闲块合并
186 ptr->prev->length += ptr->length;
187 ptr->prev->next = ptr->next;
188 if (ptr->next == NULL)
189 malloc_free_list_end = ptr->prev;
190 else
191 ptr->next->prev = ptr->prev;
192 // 由于内存组成结构的原因，不需要free掉header
193 ptr = ptr->prev;
194 }
195 ptr = ptr->next;
196 }
197 }
198
199 /**
200 * @brief 将块插入空闲链表
201 *
202 * @param ck 待插入的块
203 */
malloc_insert_free_list(malloc_mem_chunk_t * ck)204 static void malloc_insert_free_list(malloc_mem_chunk_t *ck)
205 {
206 if (malloc_free_list == NULL) // 空闲链表为空
207 {
208 malloc_free_list = ck;
209 malloc_free_list_end = ck;
210 ck->prev = ck->next = NULL;
211 return;
212 }
213 else
214 {
215
216 malloc_mem_chunk_t *ptr = malloc_free_list;
217 while (ptr != NULL)
218 {
219 if ((uint64_t)ptr < (uint64_t)ck)
220 {
221 if (ptr->next == NULL) // 当前是最后一个项
222 {
223 ptr->next = ck;
224 ck->next = NULL;
225 ck->prev = ptr;
226 malloc_free_list_end = ck;
227 break;
228 }
229 else if ((uint64_t)(ptr->next) > (uint64_t)ck)
230 {
231 ck->prev = ptr;
232 ck->next = ptr->next;
233 ptr->next = ck;
234 ck->next->prev = ck;
235 break;
236 }
237 }
238 else // 在ptr之前插入
239 {
240
241 if (ptr->prev == NULL) // 是第一个项
242 {
243 malloc_free_list = ck;
244 ck->prev = NULL;
245 ck->next = ptr;
246 ptr->prev = ck;
247 break;
248 }
249 else
250 {
251 ck->prev = ptr->prev;
252 ck->next = ptr;
253 ck->prev->next = ck;
254 ptr->prev = ck;
255 break;
256 }
257 }
258 ptr = ptr->next;
259 }
260 }
261 }
262
263 /**
264 * @brief 获取一块堆内存
265 *
266 * @param size 内存大小
267 * @return void* 内存空间的指针
268 *
269 * 分配内存的时候，结点的prev next指针所占用的空间被当做空闲空间分配出去
270 */
malloc(ssize_t size)271 void *malloc(ssize_t size)
272 {
273 // printf("malloc\n");
274 // 计算需要分配的块的大小
275 if (size + sizeof(uint64_t) <= sizeof(malloc_mem_chunk_t))
276 size = sizeof(malloc_mem_chunk_t);
277 else
278 size += sizeof(uint64_t);
279
280 // 采用best fit
281 malloc_mem_chunk_t *ck = malloc_query_free_chunk_bf(size);
282
283 if (ck == NULL) // 没有空闲块
284 {
285
286 // printf("no free blocks\n");
287 // 尝试合并空闲块
288 malloc_merge_free_chunk();
289 ck = malloc_query_free_chunk_bf(size);
290
291 // 找到了合适的块
292 if (ck)
293 goto found;
294
295 // printf("before enlarge\n");
296 // 找不到合适的块，扩容堆区域
297 if (malloc_enlarge(size) == -ENOMEM)
298 return (void *)-ENOMEM; // 内存不足
299
300
301 malloc_merge_free_chunk(); // 扩容后运行合并，否则会导致碎片
302
303 // 扩容后再次尝试获取
304
305 ck = malloc_query_free_chunk_bf(size);
306 }
307 found:;
308
309 // printf("ck = %#018lx\n", (uint64_t)ck);
310 if (ck == NULL)
311 return (void *)-ENOMEM;
312 // printf("ck->prev=%#018lx ck->next=%#018lx\n", ck->prev, ck->next);
313 // 分配空闲块
314 // 从空闲链表取出
315 if (ck->prev == NULL) // 当前是链表的第一个块
316 {
317 malloc_free_list = ck->next;
318 }
319 else
320 ck->prev->next = ck->next;
321
322 if (ck->next != NULL) // 当前不是最后一个块
323 ck->next->prev = ck->prev;
324 else
325 malloc_free_list_end = ck->prev;
326
327 // 当前块剩余的空间还能容纳多一个结点的空间，则分裂当前块
328 if ((int64_t)(ck->length) - size > sizeof(malloc_mem_chunk_t))
329 {
330 // printf("seperate\n");
331 malloc_mem_chunk_t *new_ck = (malloc_mem_chunk_t *)(((uint64_t)ck) + size);
332 new_ck->length = ck->length - size;
333 new_ck->prev = new_ck->next = NULL;
334 // printf("new_ck=%#018lx, new_ck->length=%#010lx\n", (uint64_t)new_ck, new_ck->length);
335 ck->length = size;
336 malloc_insert_free_list(new_ck);
337 }
338 // printf("malloc done: %#018lx, length=%#018lx\n", ((uint64_t)ck + sizeof(uint64_t)), ck->length);
339 // 此时链表结点的指针的空间被分配出去
340 return (void *)((uint64_t)ck + sizeof(uint64_t));
341 }
342
343 /**
344 * @brief 当堆顶空闲空间大于2个页的空间的时候，释放1个页
345 *
346 */
release_brk()347 static void release_brk()
348 {
349 // 先检测最顶上的块
350 // 由于块按照开始地址排列，因此找最后一个块
351 if (malloc_free_list_end == NULL)
352 {
353 printf("release(): free list end is null. \n");
354 return;
355 }
356 if ((uint64_t)malloc_free_list_end + malloc_free_list_end->length == brk_max_addr && (uint64_t)malloc_free_list_end <= brk_max_addr - (PAGE_2M_SIZE << 1))
357 {
358 int64_t delta = ((brk_max_addr - (uint64_t)malloc_free_list_end) & PAGE_2M_MASK) - PAGE_2M_SIZE;
359 // printf("(brk_max_addr - (uint64_t)malloc_free_list_end) & PAGE_2M_MASK=%#018lx\n ", (brk_max_addr - (uint64_t)malloc_free_list_end) & PAGE_2M_MASK);
360 // printf("PAGE_2M_SIZE=%#018lx\n", PAGE_2M_SIZE);
361 // printf("tdfghgbdfggkmfn=%#018lx\n ", (brk_max_addr - (uint64_t)malloc_free_list_end) & PAGE_2M_MASK - PAGE_2M_SIZE);
362 // printf("delta=%#018lx\n ", delta);
363 if (delta <= 0) // 不用释放内存
364 return;
365 sbrk(-delta);
366 brk_max_addr = brk(-2);
367 brk_managed_addr = brk_max_addr;
368
369 malloc_free_list_end->length = brk_max_addr - (uint64_t)malloc_free_list_end;
370 }
371 }
372 /**
373 * @brief 释放一块堆内存
374 *
375 * @param ptr 堆内存的指针
376 */
free(void * ptr)377 void free(void *ptr)
378 {
379 // 找到结点（此时prev和next都处于未初始化的状态）
380 malloc_mem_chunk_t *ck = (malloc_mem_chunk_t *)((uint64_t)ptr - sizeof(uint64_t));
381 // printf("free(): addr = %#018lx\t len=%#018lx\n", (uint64_t)ck, ck->length);
382 count_last_free_size += ck->length;
383
384 malloc_insert_free_list(ck);
385
386 if (count_last_free_size > PAGE_2M_SIZE)
387 {
388 count_last_free_size = 0;
389 malloc_merge_free_chunk();
390 release_brk();
391 }
392 }
393