CSAPP动态内存分配

动态内存分配器维护着一个进程的虚拟内存区域，称为堆。 比如说 malloc，我们用malloc来申请一段虚拟内存的时候，操作系统分配给我们的是一段 block ，但这个block和之前提到的page、cache中的block是不一样的，这边每个block的大小是不一样的。

分配过来的blocks，有两种。

• 一种是allocated也就是被分配的，已分配的块显式地保留 供应用程序使用
  • 一个已分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显式执行的，要么是内存分配器自身隐式执行的。
• 还有一种是free，也就是没有被分配的，因此可以用来分配。

分配器也有两种：显式的分配器和隐式的分配器

• 显式分配器：比如说 C语言中的malloc和free，C++当中的new和delete
• 隐式分配器：比如说 Java语言中的垃圾回收系统。

显式分配器

现在我们主要讨论显式分配器的设计与实现。

malloc和free函数

malloc

#include<stdlib.h>
void *malloc(size_t size);

malloc函数返回一个指针。执行完需要进行判断，因为不一定每次申请分配内存都能成功。如果申请不成功就返回一个空指针，并设置一个errno；若申请成功就返回一个大小至少为size字节的内存块，还有可能比size更大,因为给我们的块会为可能包含在这个块内的任何数据对象类型做对齐。在64位模式中，malloc返回的块的地址总是16的倍数。

free

void free(void *p);

free适合malloc对应的，我们可以利用这个函数来回收之前分配的内存。注意，这个 * p 一定要是 malloc，calloc和realloc这三个函数的返回值，否则会报错。

sbrk

sbrk 函数通过将内核的brk 指针增加incr 来扩展和收缩堆。

#include <unistd.h>
void *sbrk(intptr_t incr)

下面是malloc和free函数实际使用例子：

首先我们用malloc申请一个长度为n的数值类型为long的数组。然后对数组进行一个赋值以及后续操作。最后在程序结束时将其free

#include <stdio.h> #include <stdlib.h>
void foo(long n) {
	long i, *p;
	/* Allocate a block of n longs */
	p = (long *) malloc(n * sizeof(long)); 
	if (p == NULL) {
		perror("malloc"); 
		exit(0);
	}
	/* Initialize allocated block */
    for (i=0; i<n; i++)
   		p[i] = i;
    /* Do something with p */
    . . .
    /* Return allocated block to the heap */
    free(p);
}

malloc 和free 实现管理堆

假设下面是一个堆的模型，我们定义两条规则：

• Show 8-byte words as squares 没一格子代表了一个 word

• Allocations are double-word aligned. 双字对齐

#define SIZ sizeof(size_t)

• 我们一开始申请4倍的SIZ ,于是就有了黄色的4个格子
• 紧接着我们申请5倍的SIZ，因为要双字对齐，因此我们要划出6个格子来。
• 我们申请6倍的SIZ,malloc 就从空闲块的前部切出一个6字的块
• 调用free后，会释放掉第二部申请的5*SIZ 的块。
• 程序请求一个2字的块。在这种情况中，malloc分配在前一步中被释放的那个块的一部分并返回一个指向这个新块的指针。

一些分配和回收时的约束

• 处理任意请求序列。一个应用可以有任意的分配请求和释放请求序列，只要满足约束条件：每个释放请求必须对应于一个当前已分配块，这个块是由一个以前的分配请求获得的。因此，分配器不可以假设分配和释放请求的顺序。例如，分配器不能假设所有的分配请求都有相匹配的释放请求，或者有相匹配的分配和空闲请求是嵌套的。
• 立即响应请求。分配器必须立即响应分配请求。因此，不允许分配器为了提髙性能重新排列或者缓冲请求。不能是异步的
• 只使用堆。为了使分配器是可扩展的，分配器使用的任何非标量数据结构都必须保存在堆里。
• 对齐块（对齐要求）。分配器必须对齐块，使得它们可以保存任何类型的数据对象。
• 不修改已分配的块。分配器只能操作或者改变空闲块。特别是，一旦块被分配了，就不允许修改或者移动它了。因此，诸如压缩已分配块这样的技术是不允许使用的。(就是把中间的空的blocks压出来，这种是不可以的)

衡量分配器性能的一些指数：

吞吐率

现在我们假设 假定n 个分配和释放请求的某种序列 $R0,R_1,\cdots,R_k,\cdots ,R{n-1}$；我们希望一个分配器的吞吐率最大化,吞吐率的定义就是每个单位时间里完成的请求数。

例如，如果一个分配器在1 秒内完成500 个分配请求和500 个释放请求，那么它的吞吐率就是每秒1000 次操作

内存利用率

我们要知道内存虚拟内存是一个有限的空间，我们不能一直向他申请blocks，因此我们必须高效地使用虚拟内存。对于可能被要求分配和释放大块内存的动态内存分配器来说，尤其如此。

峰值利用率

对于n 个分配和释放请求的某种序列 $R0,R_1,\cdots,R_k,\cdots ,R{n-1}$

如果说一个应用程序请求一个 p 字节的块，那么得到的已分配块地payload 是 p字节。

在请求 $R_k$ 完成之后，aggregate payload(聚集有效载荷) 表示为 $P_k$,即当前已分配的块地有效载荷之和。

$H_k$表示堆地当前的大小(单调非递减)

那么，前面 k+1 个请求得峰值利用率，表示为 $Uk$, $U_k = \frac{max{i\leq k}P_i}{H_k}$

我们看到，分配器的目标就是在整个序列中使 $U_{n-1}$ 最大化。但是最大化吞吐率和最大化利用率之间是相互牵制的。

当我们以堆利用率为代价时 ，很容易编写出吞吐率最大化的分配器。

Fragmentation

碎片即分配内存时产生的额外开销，它也是造成堆利用率很低的主要原因

有两种形式的碎片：内部碎片(internal fragmentation)和外部碎片（external fragmentation)

internal fragmentation

内部碎片就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间

占有这些区域或页面的进程并不使用这个存储块。而在进程占有这块存储块时，系统无法利用它。直到进程释放它，或进程结束时，系统才有可能利用这个存储块。

当一个已分配块(allocated block) 比有效载荷(payload) 大的时候，内部碎片就会发生

external fragmentation

外部碎片是位于任何两个 操作系统分配的用于装载进程的内存区域 或页面之间的空闲区域

外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。

外部碎片是处于任何两个已分配区域或页面之间的空闲存储块。这些存储块的总和可以满足当前申请的长度要求，但是由于它们的地址不连续或其他原因，使得系统无法满足当前申请。

比如说对于第五个请求，heap中明明有8个格子，但是却无法给7*SIZ分配空间

实现一个分配器

要实现一个分配器，我们必须要解决这样几个问题

• How do we know how much memory to free given just a pointer?

  • 给free一个指针，那么分配器要怎么知道释放多少大小的内存空间？

• 空闲块组织：How do we keep track of the free blocks?

  • 我们怎么知道那些blocks是空的呢？怎么知道这一块空的区域的大小呢？
• 分割：What do we do with the extra space when allocating a structure that is smaller than the free block it is placed in?
  • 当分配一个比它所在的空闲块还小的结构时，我们如何处理额外的空间 (比如说6块空的分配掉4块，那么剩下两块怎么标记？)
• 放置：How do we pick a block to use for allocation — many might fit?
  • 如果我有多个满足条件的空间，我应该选择哪一个进行分配
• 合并：How do we reuse a block that has been freed?
  • 释放出来后的内存空间我怎么重新利用？比如前面也是空的，后面也是空的，我要不要将他们合并在一起？

隐式空闲链表

因为像放置、分割以及合并这样的基本技术贯穿在许多不同的空闲块组织中，所以我们将在一种叫做隐式空闲链表的简单空闲块组织结构中来介绍它们。

隐式分配器：会自动回收用户使用的存储空间，简单来说就是带GC功能，如Java使用的就是隐式的堆分配器

显式分配器：要求用户显示的分配/释放堆空间，如C/C++用的就是显式的堆分配器

释放多少大小的内存空间

如果我们要知道在释放时应该是放多少空间，那么我们可以在每一块block的前面放一个word来记录这个block的大小。比如说我这里申请了4个SIZ，分配了6个SIZ，那么就在一个word中记录这个block的大小：即48.

前面的word是这个block的header；后面的多余的空格即这个block的Padding(填充物)

1.0 Keeping Track of Free Blocks

对于隐式的链表来说：

我们知道，每一个payload开始的位置必须是偶数个word，但是上面说了，每一个block的第一个word记录了这个block的大小。因此在堆的一开始我们必须空出来一个word。

此外还有三种方法：

将一个block放大，我们可以看到这样的结构：

也就是说一个block 是由一个字的header、payload 以及一些padding组成的。header编码了这个块的大小，以及这个块是已分配的还是空闲的。如果我们强加一个双字的对齐约束条件，那么块大小就总是8 的倍数，且块大小的最低3 位总是零。(因为这是一个二进制数，因此只要满足后三位总是0，那么前面29位所表达的块的大小 就始终是8的倍数)因此，我们只需要内存大小的29 个高位，释放剩余的3 位来编码其他信息。

我们用3位中的最低位a来指明这个块是分配的还是空闲的。那么这个头部的大小计算公式就是：

block->header = size|alloc;

比如说一个分配的块的大小是24字节，那么它的头部就等于

0x00000018|0x1 = 0x00000019

一个块大小为40(0x28) 字节的空闲块具有如下的头部

0x00000028|0x0 = 0x00000028

假设块的格式如上图所示，我们可以将堆组织为一个连续的已分配块和空闲块的序列

我们称这种结构为隐式空闲链表，是因为空闲块是通过头部中的大小字段隐含地连接着的。分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。

注意，我们需要某种特殊标记的结束块，在这个示例中，就是一个设置了已分配位而大小为零的终止头部(end block)

隐式空闲链表的优点是简单。显著的缺点是任何操作的开销，例如放置分配的块，要求对空闲链表进行搜索，该搜索所需时间与堆中已分配块和空闲块的总数呈线性关系。

很重要的一点就是意识到系统对齐要求和分配器对块格式的选择会对分配器上的最小块大小有强制的要求。没有已分配块或者空闲块可以比这个最小值还小。例如，如果我们假设一个双字的对齐要求，那么每个块的大小都必须是双字（8 字节）的倍数。因此,9-35的块格式就导致最小的块大小为两个字：一个字作头，另一个字维持对齐要求。即使应用只请求一字节，分配器也仍然需要创建一个两字的块。

放置策略(placement policy)

当一个应用请求一个k字节的块的时候，分配器就会搜索空闲列表来查找一个足够大的可以放置所请求块的空闲块。我们有很多种放置策略：

首次适配

首次适配即从链表头开始查找，选择第一个合适的空闲块。

优点就是它趋向于将大的空闲块保留在链表后面

缺点是它趋向于在靠近链表起始处留下小空闲块的“碎片”，这就增加了对较大块的搜索时间

下一次适配

下一次适配和首次适配相似，只不过不是从链表的起始处开始搜索，而是从上一次查询结束的地方开始

下一次适配比首次适配运行起来明显要快一些。但是内存利用率要比首次适配低得多。

最佳适配

最佳适配是检査每个空闲块，选择适合所需请求大小的最小空闲块

最佳适配比首次是配合下一次适配的利用率都要高一点，但在简单空闲链表组织结构(如隐式空闲链表)当中，使用最佳适配的缺点就是它要求对堆进行彻底的搜索。

分割空闲块

当我们找到一个匹配的空闲块之后，我们就需要分配这个空闲块中的空间。

我们自然可以选用整个空闲块，但是这样就会造成很多内部碎片。但如果放置策略趋向于产生较好的匹配，那么额外的内部碎片也是可以接受的。

但是如果匹配得不太好，那么分配器就通常会选择将这个空闲块分割为两部分。第一部分变成分配块，剩下的空间形成一个新的空闲块。

比如说上图，我们在size = 48的空闲块中插入一个size = 32的block，这时候空间块就会被拆成一个长为32的分配块、一个长为16的空闲块

释放、合并空闲块

在释放块是时，我们不需要对被释放的块的header进行修改。我们只需要跳过这个block，将前一个header指向下下个block的header即可。

上面所说的是和后面的block相连，但是如果想要和前一个block相连，那么事情就变得复杂起来了。因为如果我们的模型只是一个带头部的隐式空闲链表，就没有一个指针指向前面一个block。那么我们只能是搜索整个链表，同时记住前面块的位置。那么如果这样操作，我们会发现每次调用free所需要的时间都和堆的大小成线性关系。即使使用更复杂更精细的空闲链表，搜索时间也不会是常数。

2.0 带边界标记的合并

于是我们可以将刚才提出的模型进行一个修改。这个修改是knuth提出来的。对于一个free block(空闲的块)，我们可以把这个块的结尾处改成一个footer。其中，footer是header的一个副本。这个设计十分巧妙，如果每个块都包括这样一个footer，那么分配器就可以通过检查它的footer，来判断前面一个块的起始位置和状态。

那么当分配器释放当前块的时候，可能存在有以下四种情况

1) 前面的块和后面的块都是已分配的

对于这种情况，我们只要将中间这个空闲块的header和footer的占用位从1改成0即可。

2) 前面的块是已分配的，后面的块是空闲的

对于这种情况，新的header的和就等于释放的这一块的header+它后面那块free block的header，然后对footer也进行相应的修改。并将二者的占用位改成0

3) 前面的块是空闲的，后面的块是已分配的

这种情况和2一样。

4) 前面的和后面的块都是空闲的

对于前面的块和后面的块都是free block的情况，我们需要修改前面的块的header和后面的块的footer。其大小就是将三个块的大小相加。对于中间这些数据，都被跳过了，不用去修改它们。

于是整个模型如下图所示：

我们发现最前面和最后面的两块空间是利用不起来的。因为malloc返回的地址并不是header的起始地址，而是payload的起始地址。而payload的起始地址必须是偶数对齐的，因此必须要有一个word空出来的。

因为heap是自底向上生长的，因此我们定义Dummy footer是在第一个block之前的；Dummy header是在最后一个block之后的。而且他们都要被标记成已分配，这是因为他们不能和block进行合并操作。

3.0 No Boundary Tag for Allocated Blocks

对于已经分配了的blocks来说，如果要有footer，由于对齐的原因，有可能要多两个字节来存放。因此，我们可以对分配了的block进行一些修改：

我们可以进一步地用2位来表示状态，多出来的一位可以用来表示前一个block是满的还是空的。这样，我们仅仅用一位就能节省额外地footer，分配了的block仅保留一个header。但是对于payload为空的块，我们还是保留footer。

那么上面所说的4种情况就要发生一些细小的改变了：

1) 前面的块和后面的块都是已分配的

2) 前面的块是已分配的，后面的块是空闲的

3) 前面的块是空闲的，后面的块是已分配的

4) 前面的和后面的块都是空闲的

隐式空闲链表总结

• Implementation 实现是比较简单的
• Allocate cost：
  • Linear time worst case 最差情况下分配时间是线性的
• Free cost：
  • constant time worst case 最差情况下也是常数时间
  • even with coalescing
• Memory overhead
  • will depend on placement policy 时间复杂的决定于放置策略
  • First-fit ,next-fit ,best-fit 有三种放置策略
• Not used in practice for malloc/free because of linear time allocation
  • used in many special purpose applications
• However ,the concepts of splitting and boundary tag coalescing are general to all allocators

显式空闲链表

显示链表是说我并不需要管理分配的空间，而是要管好那些空闲的空间. 因为块分配与堆块的总数呈线性关系，所以对于通用的分配器，隐式空闲链表是不适合的。

一种更好的方法是将空闲块组织为某种形式的显式数据结构。因为根据定义，程序不需要一个空闲块的主体，所以实现这个数据结构的指针可以存放在这些空闲块的主体里面。例如，堆可以组织成一个双向空闲链表，在每个空闲块中，都包含一个pred(前驱）和succ(后继指针)

使用双向链表而不是隐式空闲链表，使首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。不过，释放一个块的时间可以是线性的，也可能是个常数，这取决于我们所选择的空闲链表中块的排序策略。