memory-allocator
0x00 Introduce
我们知道用户的程序所能访问的内存就是虚拟内存，虚拟内存的布局一般分为如下几个部分：
- 内核空间
- 用户栈
- 共享库内存映射区域
- 堆空间
- 读写数据区域
- 只读代码和数据区域
一般我们关心的就是栈和堆。 >栈的申请和释放是由编译器来管理的，当调用函数的时候从栈上开辟一段内存空间，当函数退出的时候栈销毁，主要是通过移动栈指针来完成。 >堆的申请和释放就需要用户自己来管理。但是heap的申请和释放也是通过一个类似栈指针的指针来完成，这个被称为program break（brk)指针来完成 本质上 堆栈的申请和释放都是通过移动指针来完成，一个由编译器来管理，一个由用户来管理
内存可以看成是一个连续的数组，通过指针来操作(申请和释放)只能伸缩的方式
也就说用户申请内存只能申请连续的内存，释放也是释放连续的内存，这就造成如下图
在heap上申请了a1,a2,a3,a4,a5,a6 这6个变量，现在a2,a4,a5不在需要(需要释放)，因为heap的唯一操作方式就移动brk指针来完成，但是删除a5,a4,a2,势必需要经过a2,a6这两个不能删除的对象。
另外一个问题，用户操作指针也是非常不方便的, 另外频繁的调用syscall的开销也是非常大的。
总结基于上面的一些列的问题，就需要一个内存分配器来帮用户做这些事情, 因此内存分配器主要解决如下的问题：
- 帮用户管理内存(申请/释放)
- 减少内存碎片(如上图当释放了a2,a4,a5, 如何将这三小块的内存整合起来以满足更大内存分配的需求)
- …
0x01 内存分配器的一个基本实现
memory allocator的一个基本实现是通过freelist的一个单链表将分配过的chunk保存下来，
因为内存是连续的，用户程序对heap有着绝对的控制，为了方式在释放的时候误删了其他的chunk(也就说allocator在删除的时候需要知道它要删除多大的内存？),因此需要在chunk里面保存每个对应chunk的大小是多少，以及chunk对应的下一个节点是什么? —–这些元数据需要保存(保存在哪？一个简单的做法是保存在chunk自身里面，另外一个做法是单独划分一块内存区域，专门用来保存这些元数据–大部分现代内存分配器也是这么做的)
eg: 当用户申请4byte大小内存的时候，这个时候allocator调用sbrk(sizeof(heaer)+4byte)这个系统调用，获取heap对应的内存地址，然后吧这个地址返回给用户的同时也放入到freelist 里面。
在这种模式下有如下问题，当内存heap空间满了以后如何释放内存，如下图
objX 都是inused， aX 都是不在使用的，极端情况下，heap满了该如何处理？ 释放aX—–由于内存是连续的，释放是很难的一件事情，大部分allocator都实现了内存复用，当aX 不在使用的时候，将他们标记为infree, 当再有申请内存的时候，可以直接从infree里面取出一个给用户。
，因此在chunk的元数据里面在添加一个字段来标识chunk是处于inuse状态还是处于unsed状态
一个典型的chunk模型如下
1 | |---------------------------------| |
为了达到内存复用目的,当申请内存的时候直接从freelist里面找一个空闲的内存给用户要快的多(这个例子里面allocator只是个玩具，真正的allocator设计的要好得多)
内存释放
正如上面所讲，内存是连续的，并且删除内存唯一方式就是调用sbrk()—这就会造成误删和一些跳不过去的内存块， 因此简单的方式就是只删除能删除的(能删除意思是需要删除的对象正好处于program break 边缘，在这种情况下只需要执行sbrk(size(需要删除的内存)))就可以，如果不能释放的就将其标记为infree，以供重复使用,
0x02 总结
一个简易的内存分配器基本工作逻辑如下
1 | 申请内存 |