写在前面：
其实没想着在这个动态分配上浪费太多时间优化什么的，没必要，主要还是想更清楚heap怎么工作，因此下面我自己的方案其实最后没怎么参考，基本是自己对着glibc 2.23 malloc.c的源码写的。所以也没什么参考价值。本来目标也是能过就行，主要是借这个机会有看了看libc源码。
对于本lab的要求，请参考https://arthals.ink/posts/experience/malloc-lab .
介绍和要求：
我们要在mm.c中实现自己的动态内存分配函数, 他们的原型如下：
这四个函数的功能如下：
mm_init: 一切必要的堆初始化。正常返回0有错误返回-1.
mm_malloc: 类比malloc()，返回一个堆块指针，同时要求8字节对齐
mm_free: 类比free()，不返回，只有传入的是先前通过malloc或realloc分配的指针时才工作
mm_realloc: 重新修改堆块。如果传入NULL指针则功能等于malloc。如果传入非空指针（堆指针），则返回一个新块的地址。将旧的块修改为新的大小。
看起来就不好搞。。没有系统概念
同时，实验已经给我们写好了一些操作接口：
void* mem_heap_lo(void): 返回指向堆第一个字节的指针
void* mem_heap_hi(void): 返回指向堆最后一个字节的指针
size_t mem_heapsize(void): 返回当前堆大小（字节）
size_t mem_pagesize(void): 返回系统的页大小，linux上是4k
另外，实验不允许任何全局或静态数据结构（结构体、数组等）的定义。同时我们可能还要写一个检查器来检查释放、合并、空闲列表完整性、是否有overlapping、是否指针失效等等。光是看着就觉得离谱了。这个lab参考了这篇100分的通关blog ，感谢北大佬arthal的博客。
内容
这部分CSAPP上讲的非常少，而且对于优化的实现方式没有给出实例（只给了最简单的隐式空闲链表的实现），我们要想做一个能满分过关的肯定是要用和ptmalloc类似的那种分离空闲链表的实现方式的。而且根据CSAPP的描述：
对分离空闲链表的简单的首次适配搜索，其内存利用率近似于对整个堆的最佳适配搜索的内存利用率
因此肯定是分离空闲链表+首次适配的管理方式。
数据结构设计以及一个总体的堆观念
我们不需要像ptmalloc那么复杂的机制，但是chunk的数据结构是可以参考的。大概回顾一下ptmalloc2的chunk数据结构：
1 2 3 4 5 6 7 8 9 10 11 12 struct malloc_chunk { INTERNAL_SIZE_T prev_size; INTERNAL_SIZE_T size; struct malloc_chunk * fd ; struct malloc_chunk * bk ; struct malloc_chunk * fd_nextsize ; struct malloc_chunk * bk_nextsize ; };
由于size是8字节对齐的，所以低三位被设置了标志位。
我们不需要那么高的性能也不用考虑生产场景，因此large bin的两个指针不需要，然后makefile使用了m32参数，那堆的大小肯定不会超过$2^{32}$，4字节的size就够用了。但是ptmalloc中prev_size是可以复用的，参考实现中是在chunk末尾添加了脚部的元数据信息方便合并获取，这里我们就直接按照ptmalloc的来。其实本质是一样的，下一个chunk的开头加一个字段和上一个的结尾加一个字段没啥区别。
那我们的chunk，一个字段的32位低3位用2位表示inuse和prev_inuse就行了（其实是冗余的，只需要prev_inuse就够用了，第一个chunk永远将这一位置1就行）。mmap和main_arena的事不用考虑。后来考虑到冗余，加了一位IS_TOP。
最后我们的chunk数据结构如下：
1 2 3 4 5 6 struct malloc_chunk { size_t prev_size; size_t size; struct malloc_chunk * fd ; struct malloc_chunk * bk ; }
然后考虑我们这个堆的排布。回顾一下ptmalloc的bin管理，对于大小小于80字节的块，不清空他们的prev_inuse位然后用单向链表链到fastbin里。fastbin的实现就类似于我们今天的这个分离式空闲链表，指针数组连续存储指定大小（范围）的chunk链表的头指针，用一个获取下标的操作返回对应的位置，回顾struct malloc_state main_arena的内容。我们这里相当于实现了一个smallbin。然后将Bins放在堆的起始位置，不设置序言chunk。
然后，为了搞一个四不像，我也学ptmalloc，操作系统第一次是分配一个topchunk供分配器去使用，我也学，第一次初始化的时候扩展brk直接给一个topchunk，用全局变量存（这个正常是存在av->top）。开始分配的时候按照bin->topchunk->sbrk的顺序去分配。这里会导致空间利用率严重的低（最后我只有1%），所以无所谓了。
机制就是大概这样，后续具体部分会再写，然后我们有了这个堆的实现架构：
申请的时候，第一次的话就初始化堆，在start_brk处放一个指针数组，开始置空。同时分一个topchunk，不要太大，我们后面要实现相对完整的malloc就得有top chunk的重新分配环节。
如果不是第一次，那首先搜索bin。bin是一个类smallbin的指针数组，通过调用get_index返回下标然后遍历看有没有大小合适的，有就unlink后返回。
bin没有的话就得从top chunk切，切了更新top。
top chunk也不够一个最小chunk的话就调用sbrk，同时联系house of orange攻击这里也一样把旧的top直接free掉
free操作就是先合并然后链接就行了。
PS：放弃了进一步的优化，因为显然在后面的代码中prev_size是多余的foot…
我们应该干什么？
宏
先写宏，那些在后面会频繁使用的宏，做成函数是不现实的，太浪费时间了。参考前辈blog与glibc定义的那些宏，大概写一写：
1 2 3 4 5 #define PREV_INUSE 0x1 #define IS_INUSE 0x2 #define IS_TOP 0x4
然后，操作已分配chunk的一些操作（读），包括取标志位，取大小，以及将请求的大小通过对齐和增加元数据返回一个正确大小的req2size等。第一次编译报错了，记得括号加全不然运算顺序得翻车。
1 2 3 4 5 6 7 #define chunksize(p) ((size_t)(((malloc_chunk*)(p))->size) & (~0x7)) #define request2size(req) (ALIGN((req) + (SIZE_T_SIZE))) #define prev_inuse(p) ((size_t)(((malloc_chunk*)(p))->size) & PREV_INUSE) #define inuse(p) ((size_t)(((malloc_chunk*)(p))->size) & IS_INUSE) #define is_top(p) ((size_t)(((malloc_chunk*)(p))->size) & IS_TOP)
写操作，修改元数据，包括置位、清空、写入size等操作。大部分用位运算|=实现。
1 2 3 4 5 6 7 8 9 #define set_inuse(p) (((malloc_chunk*)(p))->size |= IS_INUSE) #define set_prev_inuse(p) (((malloc_chunk*)(p))->size |= PREV_INUSE) #define set_size(p, s) (((malloc_chunk*)(p))->size = (((malloc_chunk*)(p))->size & (IS_TOP | IS_INUSE | PREV_INUSE)) | (s)) #define set_foot(p, s) (((malloc_chunk*) ((char *) (p) + (s)))->prev_size = (s)) #define set_top(p) (((malloc_chunk*)(p))->size |= IS_TOP) #define clear_inuse(p) (((malloc_chunk*)(p))->size &= ~IS_INUSE) #define clear_prev_inuse(p) (((malloc_chunk*)(p))->size &= ~PREV_INUSE)
指针操作，定位前后chunk或者偏移地址的chunk，先转char*进行计算最后转回malloc_chunk*
1 2 3 4 #define next_chunk(p) ((malloc_chunk*)((char*)(p) + chunksize(p))) #define prev_chunk(p) ((malloc_chunk*)((char*)(p) - ((p)->prev_size))) #define chunk_at_offset(p, s) ((malloc_chunk*)((char*)(p) + s))
操作空闲chunk的宏，next_bin事实上被get_index函数代替了没有用到。这里面有经典的unlink操作，ptmalloc的版本更复杂也只是多了一些检查什么的而已。这个取出链表的操作让我们在能修改p->fd和p->bk的前提下做出一些恶搞。如果没有任何检查，只要有能劫持fd的机会应该就能实现任意地址写。
1 2 3 4 5 6 7 8 9 10 11 12 #define NBINS 16 #define next_bin(b) ((malloc_chunk*)((char*)(b)+ (sizeof(malloc_chunk*)<<1))) #define unlink(P,FD,BK) {\ FD = (P)->fd;\ BK = (P)->bk;\ FD->bk = BK;\ BK->fd = FD;\ }
top和bins的全局变量以及写入和真实chunk的地址转换，lab评测估计用不到
1 2 3 4 5 6 7 8 #define writeable(p) ((malloc_chunk*)((char*)(p)+8)) #define real(p) ((malloc_chunk*)((char*)(p)-8)) static malloc_chunk* top=NULL ;static malloc_chunk** Bins;#define prev_free(p) ((malloc_chunk*)(p)->bk) #define next_free(p) ((malloc_chunk*)(p)->fd)
最后没用到，一个检查的宏
1 2 #define check_size(size) (((size >= MAX_HEAP)||size==0) ? 0 : 1)
mm_init
调用时机的问题参考mm_malloc部分.
这个函数就是初始化top和bin用的，借助memlib中给我们的函数实现。mem_init()调用了真正的malloc分配了MAX_HEAP(20M)空间给我们，同时设置了brk，另外这个brk是private的，说明出题人期望我们仅通过接口访问，我们也就不要人为修改了。
通过一个循环设置好Bins指针数组（在堆的开头），同时用sbrk直接返回一个topchunk，并且设置元数据。topchunk是地址最高的那块，任何相邻它的空闲chunk都会被直接合并
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 int mm_init (void ) { mem_init(); Bins = mem_heap_lo(); for (int i = 0 ; i < NBINS; i++){ if (mem_sbrk(sizeof (malloc_chunk*)) == (void *)-1 ) return -1 ; Bins[i] = NULL ; } size_t size= request2size(MAX_HEAP>>4 ); malloc_chunk* top_chunk = mem_sbrk(size); if (top_chunk == (void *)-1 ) return -1 ; top_chunk->prev_size = 0xffffffff ; clear_inuse(top_chunk); set_top(top_chunk); set_prev_inuse(top_chunk); set_size(top_chunk, size); top=top_chunk; return 0 ; }
mm_malloc
偷的get_index()。我们的bins青春版其实就是维护了一个smallbin。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 static inline size_t get_index (size_t size) { if (size <= 24 ) return 1 ; if (size <= 32 ) return 2 ; if (size <= 64 ) return 3 ; if (size <= 80 ) return 4 ; if (size <= 120 ) return 5 ; if (size <= 240 ) return 6 ; if (size <= 480 ) return 7 ; if (size <= 960 ) return 8 ; if (size <= 1920 ) return 9 ; if (size <= 3840 ) return 10 ; if (size <= 7680 ) return 11 ; if (size <= 15360 ) return 12 ; if (size <= 30720 ) return 13 ; if (size <= 61440 ) return 14 ; else return 15 ; }
下面是自己的构式malloc，判断是否已经初始化看的是top指针有没有设置。然后按照Bins->Topchunk->sbrk的顺序依次进行检查和分配chunk。在ptmalloc中，放入对应bin的操作反而是在malloc里实现的，这种设计思路可能有助于优化。下面的malloc也是遵循这种逐级查找的思路。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 void *mm_malloc (size_t size) { if (!check_size(size)){ printf ("size out of range or null\n" ); return NULL ; } int newsize = request2size(size); if (top==NULL ) mm_init(); size_t index = get_index(newsize); malloc_chunk* p = Bins[index]; malloc_chunk *FD, *BK; short flag=0 ; while (p!=NULL &&!flag){ if (chunksize(p)>=newsize){ unlink(p, FD, BK); set_size(p,newsize); set_inuse(p); set_foot(p, newsize); return writeable(p); } p = next_free(p); if (p==Bins[index]) flag=1 ; } p = top; size_t top_size = chunksize(p); int remainder_size = top_size - newsize; if (remainder_size <= 24 ) { p->size &= ~IS_TOP; free (p); top = mem_sbrk(newsize+top_size); if (top == (void *)-1 ) return NULL ; p=top; } malloc_chunk* remainder= chunk_at_offset(p, newsize); set_size(p, newsize); set_foot(p, newsize); set_inuse(p); set_size(remainder, remainder_size); set_inuse(remainder); set_top(remainder); set_prev_inuse(remainder); top = remainder; return writeable(p); }
mm_free
ptmalloc中free是直接按fastbin和非fastbin处理的，不是fastbin直接放到unsorted等下次malloc调用的时候触发合并整理。这里我不会写所以放弃了。这个free函数的功能（包括核心部分的代码逻辑、判断控制流）基本上和ptmalloc的free是一样的：先合并再放入bin。
合并操作先看低地址合并，用prevsize定位后unlink掉p。检查高地址的时候观察是否挨着top，挨着top直接放进去。然后看是否在使用，没有的话再合并。合并完后按照__int_free中放入unsortedbin的代码大概抄一下，双向链表insert。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 void mm_free (void *ptr) { if (ptr == NULL ) return ; malloc_chunk* p=real(ptr); clear_inuse(p); clear_prev_inuse(next_chunk(p)); malloc_chunk* next = next_chunk(p); malloc_chunk* prev = prev_chunk(p); malloc_chunk* FD; malloc_chunk* BK; size_t size= chunksize(p); if (!prev_inuse(p)){ size_t prev_size = chunksize(prev); size+=prev_size; p=prev; unlink(p, FD, BK); } if (next!=top) { if (inuse(next)!=IS_INUSE){ unlink(next, FD, BK); size+=chunksize(next); } else { clear_inuse(p); clear_prev_inuse(next); } set_size(p, size); set_foot(p, size); malloc_chunk* header=Bins[get_index(size)]; if (header==NULL ){ Bins[get_index(size)]=p; p->fd=p; p->bk=p; } else { BK=header; FD=BK->fd; p->fd=FD; p->bk=BK; BK->fd=p; FD->bk=p; } } else { size+=chunksize(next); set_top(p); set_inuse(p); set_size(p, size); top=p; } }
mm_realloc
默认实现就够了感觉，realloc是调用free和malloc实现的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void *mm_realloc (void *ptr, size_t size) { void *oldp = ptr; void *p; size_t copySize; p = mm_malloc(size); if (p == NULL ) return NULL ; copySize = ((malloc_chunk*)oldp)->size-8 ; if (size < copySize) copySize = size; memcpy (p, oldp, copySize); mm_free(oldp); return p; }
看一下幽默得分
1 2 3 4 5 6 7 8 9 10 11 12 13 Team Name:nothing Member 1 :Zj_W1nD:123123 Member 2 :123:123 Using default tracefiles in ./ Measuring performance with gettimeofday(). Results for mm malloc: trace valid util ops secs Kops 0 yes 1% 32 0.000009 3441 1 yes 1% 12 0.000014 857 Total 1% 44 0.000023 1888 Perf index = 1 (util) + 40 (thru) = 41/100
写在最后：
这个lab给我的感觉很糟糕，动态内存分配凹分的意义并不是很大，我也是大部分时间放在了看源码上。blog也不想多写没什么内容和心得好说。本来还想着试着能不能攻击一下我自己的堆分配器，但是实在懒得搞了，下次想玩了再说。
