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 = 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