C|内存管理|Memory Allocation

本文续上文，其中提到new在malloc之外做了额外的工作。在这里我们继续深入malloc/free。

从某种意义上来说，heap和stack很接近，也有一个sbrk标识堆顶。在没有free的情况下，sbrk的行为和rsp很接近，每次申请一块内存，sbrk增大，增大的部分作为分配的内存。然而，由于free由用户控制，释放内存不像栈一样始终在栈顶，这就造成了复杂度。新分配的内存可能在sbrk附近，也有可能在已经被释放的内存上。因此，我们malloc时会先寻找是否有已经存在的被释放的内存，如果没有，再增加sbrk。

Fragmentation

External Fragmentation

释放了五个单位的空间，又申请了四个单位的空间，则原空间只能分配一个单位，而不能被更大的分配需求利用。

Internal Fragmentation

记录的额外空间或者内存对齐，导致零碎的空间产生。

Mechanism

我们把每一个分配的区块以及其中的信息称为一个chunk,在表头我们需要记录这些信息

记录分配空间的大小: size（word）

记录是否被分配： allocation bit（由于size后三位必定为0（word对齐）,因此可以放在size末位）

分配时额外的信息：payload

通过head指针和offset可以计算出下一个chunk，因此堆实际上是隐式链表。通过遍历并求其中的allocation bit，我们可以获得其中未被分配的内存。

Starategy

First Fit

从头开始，第一个空间足够的chunk直接分配:

缺陷： 头部碎片化

Next Fit

从上次搜索的地址开始，第一个空间足够的chunk直接分配：

缺陷: 效率更糟糕

Best Fit

整个列表中空间足够且最小的chunk分配。

缺陷：固定的线性时间

Free

假设我们free了一块内存，由于malloc造成的碎片化，因此我们需要在free时进行反碎片化，例如附近有未分配的空间，我们应该把未分配的空间合并到一起。由于存储了size，我们很容易后遍历，但是向前遍历就难了。

因此，我们需要额外的信息，让他成为双向链表，在chunk的最后也存储一份size+allocation的信息，这样下一个chunk头的前一个word就能反查上一个chunk了。

需要注意的是，这里是不需要考虑循环的，因为free本身保证了free的空间连续，因此只需要考虑上下一块即可。（参见数学归纳）

如果free的内存在sbrk附近（表尾），那么直接收缩堆。

Malloc

遍历寻找可分配的chunk，然后找到size大于需求的，直接修改size+allocation bit即可。这时我们要注意，分配完之后，剩余的空间可能能容纳一个chunk，也可能不能，如果不能的话，我们直接把整块空间都给malloc，以充分利用空间。

Extension

很明显，为了避免碎片化，Best Fit是最好的，但是线性遍历开销太大。那么我们自然地想到了查找的数据结构，hash。我们可以把free chunk根据size映射到不同的链表，每次free都插入表头，下次malloc时根据size直接能查到。如此一来，查找的时间变为常数。

不过，由于不再是彼此连续的chunk，原本的size之外又得存储指针，这也算是典型的时空交换了。