内存分配算法

go runtime对不同大小的对象采取的分配算法有一些不同：主要目的是提高时间和空间效率。

极小对象分配

对于小于maxTinySize(16B)字节对象的内存分配请求。go采取了将小对象合并存储的解决方案。

每个线程在本地维护了专门的memory block来存储tiny object。每次分配时计算该block内是否可容纳该tiny object，如果可以，直接返回block的起始内存地址加上block内当前的使用偏移。如下图所示：

note:对于极小对象，其实际占用的内存起始地址按照一定的规则进行对其。对其规则如下：

1. 对于大于等于8B的对象，其内存地址按照8B对齐；
2. 对于小于8B大于等于4B的对象，其内存地址按照4B对齐；
3. 对于小于4B大于1B的对象，其内存地址按照2B对齐；
4. 对于1B对象，无对齐要求。

这种对齐要求可能会造成一定的内存浪费，然后却能带来内存访问效率的提升。

如果当前正在使用的memory block无法容纳当前申请的对象。则需要申请一个新的memory block。此时需要考虑的一个问题是原来的正在被使用的memory block是否需要被替换出去。这个留给读者自己思考吧。

大对象分配

对于超过_MaxSmallSize(32KB)的object，go并非使用上面这些复杂的内存分配机制，因为过于复杂，代价太大，得不偿失。

对于此类的大对象，go直接从heap上分配内存。分配算法：

1. 计算大对象占用的内存页面数；
2. 从heap的free mspan中查找具备合适页面数的mspan，如果找到进入步骤4；
3. 从heap的large mspan链表中采用best fit算法找到最合适的mspan；
4. 至此，找到合适的mspan，但是该mspan的空闲页面数可能超过申请的数量，此时需要将该mspan切割，给用户返回需求的页面数，剩余的页面数构成一个全新的mspan，继续放到heap的空闲mspan链表中。

上图中红色的mspan被分配出去部分memory page后，余下的空间作为一个新的mspan被插入到全新的链表free[M]。M为多少取决于该mspan剩余的memory page数量。

中等大小对象分配

中等大小的对象是go内部实现较为复杂的部分。主要问题存在：

1. Go需要根据对象的大小分配合适的内存块；
2. 为了提高分配性能，需要实现线程内存缓存，分配时优先从线程内缓存分配，不够时再从中央分配器分配来填充本地缓存。

从m的内存块cache中分配空闲内存块算法如下：

1. 根据对象大小和既定规则来计算需要分配的块大小级别，具体计算规则后面仔细描述；
2. 查找本地缓存中该级别的空闲内存块，如果为空，从中央分配器中分配一定数量的该级别的空闲内存块(可能分配一个span并切割)；
3. 从m的缓存中分配空闲内存块。

从中央分配器中分配空闲内存块算法如下：

1. 从请求的内存块大小的级别的mcentral中查找nonempty链表，不为空则直接分配，返回；
2. 扫描empty链表，看看是否有已经垃圾回收完(不确定??)的mspan,如果有，也可以分配出来;
3. 到此，说明需要向heap中再申请空闲mspan，将其按照既定块大小切割成小内存块，插入到nonempty链表中，再从该mspan种分配内存块即可。