day9 内核的malloc和free

今天看了下内核使用的malloc和free，受益颇丰，现在回想起来以前看golang的runtime中内存的管理部分感觉清晰了很多。linux0.11部分内核的方法名也叫malloc，之后的版本为了和用户程序的区分改成了kmalloc，但分桶思想大概相同

首先明确几个变量和数据结构

1. free_bucket_desc 这个是当前未使用的桶描述符的链表
2. _bucket_dir，通描述符目录，每个大小的通描述符的目录，其中size记录了桶的大小，bucket_desc是指向桶描述符的指针。每个bucket_desc都有next指针来组成一个链表
3. bucket_desc，关键对象，一个描述符被第一次使用的时候，会申请一页地址，并且根据该描述符所在的大小将该页切割成不同的块，每个块初始化的时候前4个字节都会被写入后一个块的地址（这样在页内其实就形成了一个隐式的链表），并把第一个块的地址放入bucket_desc的freeptr字段中，每申请一个，该字段就取当前块的指针所对应的块的地址（有点绕，注意体会）存入freeptr。

malloc流程

1. 遍历bucket_dir寻找一个能容纳当前块的桶目录，找不到就报错
2. 找到桶目录后遍历该桶的描述符，如果找到一个描述符的freeptr是有效的桶则进入第5步
3. 没找到的话说明需要申请一个新描述符了，首先去free_bucket_desc取一个，取不到则调用init_bucket_desc方法申请一页内存，并按照bucket_desc大小切分该页，初始化他们next字段组成链表加入到free_bucket_desc中，然后取出来一个
4. 取出的这个描述符我们改变他的next，让他从free中删去，加入我们对应大小的桶目录中，初始化描述符的引用次数，块大小字段，然后调用get_free_page申请一页内存，把返回的地址存入page和freeptr字段
5. 对新申请的页初始化，按照当前描述符大小切割页面，并给切割后的块前4个字节写入下一个块的地址组成链表

image.png

free

free其实没啥可说的，最有意思的还是指针的退还，假如一页分配了1，2，3，4，5，6，7，8，9，0，0，0
当前描述符的freeptr指向第一个0也就是没用过的地方，这时候假如free(4)，就会把4这个快标记为未使用，也就是让描述符的freeptr指向4，并把4的内容抹去，然后前4个字节写入9后面那个0，这样下次申请的时候还是申请4这个位置！