1 #include <stdlib.h>
2 #include <libsystem/syscall.h>
3 #include <stddef.h>
4 #include <unistd.h>
5 #include <errno.h>
6 #include <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 = sbrk(0);
135         // printf("brk_base_addr=%#018lx\n", brk_base_addr);
136         brk_managed_addr = brk_base_addr;
137         brk_max_addr = brk_base_addr;
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 = sbrk((0));
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     memset(new_ck, 0, sizeof(malloc_mem_chunk_t));
160     new_ck->length = brk_max_addr - brk_managed_addr;
161     // 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);
162     new_ck->prev = NULL;
163     new_ck->next = NULL;
164     brk_managed_addr = brk_max_addr;
165 
166     malloc_insert_free_list(new_ck);
167 
168     return 0;
169 }
170 
171 /**
172  * @brief 合并空闲块
173  *
174  */
malloc_merge_free_chunk()175 static void malloc_merge_free_chunk()
176 {
177     if (malloc_free_list == NULL)
178         return;
179     malloc_mem_chunk_t *ptr = malloc_free_list->next;
180     while (ptr != NULL)
181     {
182         // 内存块连续
183         if (((uint64_t)(ptr->prev) + ptr->prev->length == (uint64_t)ptr))
184         {
185             // printf("merged %#018lx  and %#018lx\n", (uint64_t)ptr, (uint64_t)(ptr->prev));
186             // 将ptr与前面的空闲块合并
187             ptr->prev->length += ptr->length;
188             ptr->prev->next = ptr->next;
189             if (ptr->next == NULL)
190                 malloc_free_list_end = ptr->prev;
191             else
192                 ptr->next->prev = ptr->prev;
193             // 由于内存组成结构的原因，不需要free掉header
194             ptr = ptr->prev;
195         }
196         ptr = ptr->next;
197     }
198 }
199 
200 /**
201  * @brief 将块插入空闲链表
202  *
203  * @param ck 待插入的块
204  */
malloc_insert_free_list(malloc_mem_chunk_t * ck)205 static void malloc_insert_free_list(malloc_mem_chunk_t *ck)
206 {
207     if (malloc_free_list == NULL) // 空闲链表为空
208     {
209         malloc_free_list = ck;
210         malloc_free_list_end = ck;
211         ck->prev = ck->next = NULL;
212         return;
213     }
214     else
215     {
216 
217         malloc_mem_chunk_t *ptr = malloc_free_list;
218         while (ptr != NULL)
219         {
220             if ((uint64_t)ptr < (uint64_t)ck)
221             {
222                 if (ptr->next == NULL) // 当前是最后一个项
223                 {
224                     ptr->next = ck;
225                     ck->next = NULL;
226                     ck->prev = ptr;
227                     malloc_free_list_end = ck;
228                     break;
229                 }
230                 else if ((uint64_t)(ptr->next) > (uint64_t)ck)
231                 {
232                     ck->prev = ptr;
233                     ck->next = ptr->next;
234                     ptr->next = ck;
235                     ck->next->prev = ck;
236                     break;
237                 }
238             }
239             else // 在ptr之前插入
240             {
241 
242                 if (ptr->prev == NULL) // 是第一个项
243                 {
244                     malloc_free_list = ck;
245                     ck->prev = NULL;
246                     ck->next = ptr;
247                     ptr->prev = ck;
248                     break;
249                 }
250                 else
251                 {
252                     ck->prev = ptr->prev;
253                     ck->next = ptr;
254                     ck->prev->next = ck;
255                     ptr->prev = ck;
256                     break;
257                 }
258             }
259             ptr = ptr->next;
260         }
261     }
262 }
263 
264 /**
265  * @brief 获取一块堆内存
266  *
267  * @param size 内存大小
268  * @return void* 内存空间的指针
269  *
270  * 分配内存的时候，结点的prev next指针所占用的空间被当做空闲空间分配出去
271  */
malloc(ssize_t size)272 void *malloc(ssize_t size)
273 {
274     // printf("malloc\n");
275     // 计算需要分配的块的大小
276     if (size + sizeof(uint64_t) <= sizeof(malloc_mem_chunk_t))
277         size = sizeof(malloc_mem_chunk_t);
278     else
279         size += sizeof(uint64_t);
280 
281     // 采用best fit
282     malloc_mem_chunk_t *ck = malloc_query_free_chunk_bf(size);
283 
284     if (ck == NULL) // 没有空闲块
285     {
286 
287         // printf("no free blocks\n");
288         // 尝试合并空闲块
289         malloc_merge_free_chunk();
290         ck = malloc_query_free_chunk_bf(size);
291 
292         // 找到了合适的块
293         if (ck)
294             goto found;
295 
296         // printf("before enlarge\n");
297         // 找不到合适的块，扩容堆区域
298         if (malloc_enlarge(size) == -ENOMEM)
299             return (void *)-ENOMEM; // 内存不足
300 
301 
302         malloc_merge_free_chunk(); // 扩容后运行合并，否则会导致碎片
303 
304         // 扩容后再次尝试获取
305 
306         ck = malloc_query_free_chunk_bf(size);
307     }
308 found:;
309 
310     // printf("ck = %#018lx\n", (uint64_t)ck);
311     if (ck == NULL)
312         return (void *)-ENOMEM;
313     // printf("ck->prev=%#018lx ck->next=%#018lx\n", ck->prev, ck->next);
314     // 分配空闲块
315     // 从空闲链表取出
316     if (ck->prev == NULL) // 当前是链表的第一个块
317     {
318         malloc_free_list = ck->next;
319     }
320     else
321         ck->prev->next = ck->next;
322 
323     if (ck->next != NULL) // 当前不是最后一个块
324         ck->next->prev = ck->prev;
325     else
326         malloc_free_list_end = ck->prev;
327 
328     // 当前块剩余的空间还能容纳多一个结点的空间，则分裂当前块
329     if ((int64_t)(ck->length) - size > sizeof(malloc_mem_chunk_t))
330     {
331         // printf("seperate\n");
332         malloc_mem_chunk_t *new_ck = (malloc_mem_chunk_t *)(((uint64_t)ck) + size);
333         new_ck->length = ck->length - size;
334         new_ck->prev = new_ck->next = NULL;
335         // printf("new_ck=%#018lx, new_ck->length=%#010lx\n", (uint64_t)new_ck, new_ck->length);
336         ck->length = size;
337         malloc_insert_free_list(new_ck);
338     }
339     // printf("malloc done: %#018lx, length=%#018lx\n", ((uint64_t)ck + sizeof(uint64_t)), ck->length);
340     // 此时链表结点的指针的空间被分配出去
341     return (void *)((uint64_t)ck + sizeof(uint64_t));
342 }
343 
344 /**
345  * @brief 当堆顶空闲空间大于2个页的空间的时候，释放1个页
346  *
347  */
release_brk()348 static void release_brk()
349 {
350     // 先检测最顶上的块
351     // 由于块按照开始地址排列，因此找最后一个块
352     if (malloc_free_list_end == NULL)
353     {
354         printf("release(): free list end is null. \n");
355         return;
356     }
357     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))
358     {
359         int64_t delta = ((brk_max_addr - (uint64_t)malloc_free_list_end) & PAGE_2M_MASK) - PAGE_2M_SIZE;
360         // 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);
361         // printf("PAGE_2M_SIZE=%#018lx\n", PAGE_2M_SIZE);
362         // printf("tdfghgbdfggkmfn=%#018lx\n ", (brk_max_addr - (uint64_t)malloc_free_list_end) & PAGE_2M_MASK - PAGE_2M_SIZE);
363         // printf("delta=%#018lx\n ", delta);
364         if (delta <= 0) // 不用释放内存
365             return;
366         sbrk(-delta);
367         brk_max_addr = sbrk(0);
368         brk_managed_addr = brk_max_addr;
369 
370         malloc_free_list_end->length = brk_max_addr - (uint64_t)malloc_free_list_end;
371     }
372 }
373 /**
374  * @brief 释放一块堆内存
375  *
376  * @param ptr 堆内存的指针
377  */
free(void * ptr)378 void free(void *ptr)
379 {
380     // 找到结点（此时prev和next都处于未初始化的状态）
381     malloc_mem_chunk_t *ck = (malloc_mem_chunk_t *)((uint64_t)ptr - sizeof(uint64_t));
382     // printf("free(): addr = %#018lx\t len=%#018lx\n", (uint64_t)ck, ck->length);
383     count_last_free_size += ck->length;
384 
385     malloc_insert_free_list(ck);
386 
387     if (count_last_free_size > PAGE_2M_SIZE)
388     {
389         count_last_free_size = 0;
390         malloc_merge_free_chunk();
391         release_brk();
392     }
393 }
394