课程主页：https://courses.cs.washington.edu/courses/cse351/16sp/

课程资料：

实验部分：https://github.com/vuquangtrong/HW-SW_Interface_Course

实验说明：https://courses.cs.washington.edu/courses/cse351/13sp/lab-0.html

课件：http://academictorrents.com/details/b63a566df824b39740eb9754e4fe4c0140306f4b

课程视频：https://www.bilibili.com/video/BV1Zt411s7Gg?from=search&seid=8781593976070799647

这次回顾第十部分，这部分介绍了内存分配。

第10节：内存分配主题

备注：这一讲单词和字都是指word。

这一节主要有以下主题：

  • 动态内存分配
    • 数据结构的大小/数量只能在运行时才能知道
    • 需要在堆上分配空间
    • 需要释放未使用的内存，以便可以重新分配
  • 实现
    • 隐式空闲链表
    • 显式空闲链表
    • 独立空闲列表
  • 垃圾回收
  • C程序常见内存bug

动态内存分配

  • 程序员使用动态内存分配器（如malloc）在运行时获取内存。

    • 对于大小仅在运行时才知道的数据结构。

  • 动态内存分配器管理称为堆的进程虚拟内存区域。

  • 分配器将堆作为可变大小块的集合来维护，这些块可以是已分配的，也可以是空闲的

    • 分配器请求堆区域中的空间； VM硬件和内核将这些页分配给进程
    • 应用程序对象通常比页小，因此分配器管理页内的块

  • 分配器类型

    • 显式分配器：应用程序分配和释放空间
      • 例如：C中的malloc和free
    • 隐式分配器：应用程序分配，但不释放空间
      • 如Java、ML、Lisp中的垃圾回收
malloc库
#include <stdlib.h>
void *malloc(size_t size)
  • 成功：
    • 返回一个指向内存块的指针，大小至少为size(向8对齐)字节
    • 如果size == 0，则返回NULL
  • 不成功：返回NULL，设置errno
void free(void *p)
  • 将p指向的块返回到可用内存池中
  • p必须来自之前对malloc或realloc的调用

其他函数

  • calloc：将分配的块初始化为零的malloc版本。
  • realloc：改变先前分配的块大小。
  • sbrk：由分配器内部使用，用于增大或缩小堆
Malloc例子
void foo(int n, int m) {
  int i, *p;
  
  /* allocate a block of n ints */
  p = (int *)malloc(n * sizeof(int));
  if (p == NULL) {
    perror("malloc");
    exit(0);
  }
  for (i=0; i<n; i++) p[i] = i;

  /* add space for m ints to end of p block */
  if ((p = (int *)realloc(p, (n+m) * sizeof(int))) == NULL) {
    perror("realloc");
    exit(0);
  }
  for (i=n; i < n+m; i++) p[i] = i;

  /* print new array */  
  for (i=0; i<n+m; i++)
    printf("%d\n", p[i]);

  free(p); /* return p to available memory pool */
}
这节的假设
  • 内存是字地址（每个字可以容纳一个指针）
    • 块大小是字的倍数

分配例子

分配器需要跟踪哪些信息？

限制
  • 应用程序
    • 可以发出任意的malloc()和free()请求序列
    • free()请求必须只针对先前的malloc()块
  • 分配器
    • 无法控制已分配块的数量或大小
    • 必须立即响应malloc()请求
      • 即不能重新排序或缓冲请求
    • 必须从可用内存中分配块
      • 即，块不能重叠
    • 必须对齐块，以便它们满足所有对齐要求
      • Linux上GNU Malloc(libc Malloc) 8字节对齐
    • 一旦分配的块被malloc()，就无法分配它们
      • 文件合并是不允许的。
性能目标：最大化内存利用率

  • 给定一些malloc和free请求的序列：

  • 目标：最大化吞吐率和峰值内存利用率

    • 这些目标常常是矛盾的

  • 吞吐率：

    • 单位时间完成的请求数
    • 例：
      • 在10秒内进行5,000个malloc()调用和5,000个free()调用
      • 吞吐量为每秒1,000次操作

  • 定义：累计有效载荷$P_k$

    • malloc(p)产生有效载荷为$p$字节的块
    • 在请求$R_k$完成之后，累计有效载荷$P_k$是当前有效载荷的总和

  • 定义：当前堆大小$=H_k$

    • 假设$H_k$是单调非递减的
      • 分配器可以使用sbrk()增加堆的大小

  • 定义：$k$个请求后内存利用率峰值

    • $U_k=(\max_{i<k} P_i)/H_k$
    • 目标：最大化$k$次请求的内存利用率。
    • 为什么这么难？吞吐量会怎样呢？
碎片
  • 内存利用率低是由于碎片造成的
    • 内部碎片
    • 外部碎片
内部碎片

  • 对于给定的块，如果有效载荷小于块大小，就会发生内部碎片

  • 问题原因

    • 维护堆数据结构的开销（块内、外部有效载荷）
    • 用于对齐目的的填充
    • 明确的策略决策（例如，返回大块以满足小请求）

  • 只取决于先前请求的模式

    • 因此，易于测量
外部碎片

  • 当堆的总内存足够大，但没有一个空闲块足够大时发生

  • 取决于未来请求的模式

    • 因此，很难测量

实现

实现的问题
  • 给定一个指针，我们如何知道有多少内存应该释放？
  • 我们如何跟踪空闲块？
  • 我们如何选择块来分配（当许多块可能适合时）？
  • 当分配一个比它所放置的空闲块小的结构时，我们如何处理额外的空间？
  • 如何将释放的块重新插入到堆中？
知道释放多少
  • 标准方法
    • 在块前面的单词记录单词的长度
      • 这个词通常被称为头字段或头
    • 每个分配的块都需要一个额外的单词

跟踪空闲块

  • 方法一：使用带长度的隐式链表链接所有块

  • 方法二：显式链表链接所有空闲块

  • 方式三：分离空闲链表

    • 不同大小类别的空闲链表

  • 方法四：按大小排序

    • 可以使用平衡二叉树（例如红黑树），每个空闲块内都有指针，长度用作键
隐式空闲
隐式空闲链表

  • 对于每个块，我们需要：大小，是否分配？

    • 可以用两个词来存储这些信息，但这有些浪费

  • 标准技巧

    • 如果块对齐，一些低阶的位总是0

    • 与其存储0位，不如将其用作分配/空闲标志

    • 当读取尺寸时，一定要遮住这比特

隐式空闲例子

堆中块的序列：2/0,4/1,8/0,4/1（大小/是否已分配）

  • 8字节对齐
    • 可能需要初始未使用的单词
    • 导致一些内部碎片
  • 一个单词（0/1）标记列表结尾
隐式链表：找到空闲块

  • First fit：

    • 从开始搜索链表，选择第一个适合的空闲块：

      p = heap_start; 
while ((p < end) &&     \\ not passed end
       ((*p & 1) ||     \\ already allocated
       (*p <= len)))    \\ too small 
  p = p + (*p & -2);    \\ goto next block

    • ```
      p gets the block header
      p & 1 extracts the allocated bit p & -2 masks the allocated bit, gets just the size

      
  - 关于总块数（已分配和空闲）是线性时间

  - 在实际中，它会在链表的开头造成“碎片”

- Next fit：

  - 类似first-fit，但是搜索链表从上一次搜索完成的位置开始
  - 通常应比first-fit快：避免重新扫描无用块
  - 一些研究表明碎片化更严重

- Best fit：

  - 搜索链表，选择最好的空闲块：匹配，并且剩余字节最少
  - 保持碎片较小通常有助于解决碎片化
  - 通常会比first-fit慢



###### 隐式链表：在空闲块中分配

- 空闲块分配：拆分

  - 由于分配的空间可能小于可用空间，因此我们可能要拆分块

    ![](https://github.com/Doraemonzzz/md-photo/blob/master/Hardware%20Software%20Interface/Section10/2020091512.jpg?raw=true)

  - ```c
    void addblock(ptr p, int len) {
      int newsize = ((len + 1) >> 1) << 1;  // round up to even
      int oldsize = *p & -2;                // mask out low bit
      *p = newsize | 1;                     // set new length + allocated
      if (newsize < oldsize)
        *(p+newsize) = oldsize - newsize;   // set length in remaining
    }                                       //   part of block
隐式链表：释放块

  • 最简单的实现：

    • 只需清除“已分配”标志

      void free_block(ptr p) { *p = *p & -2 }

    • 但会导致“虚假碎片”

    • 如果运行malloc(5)

      • 那么有足够的空闲空间，但分配器无法找到它
隐式链表：合并

  • 连接（合并）下一个/上一个块（如果它们是空闲的）

    • 与下一个块合并

      void free_block(ptr p) {
	*p = *p & -2;          // clear allocated bit
	next = p + *p;         // find next block
	if ((*next & 1) == 0)      
		*p = *p + *next;   // add to this block if                        						    //    not allocated
}

    • 但是我们如何与前一个块合并？

隐式链表：双向合并
  • 边界标签[Knuth73]
    • 在空闲块的“底部”（末尾）复制大小/分配的字
    • 允许我们向后遍历“列表”，但需要额外的空间
    • 重要而通用的技巧！

隐式空闲链表：总结
  • 实现：非常简单
  • 分配成本：
    • 最坏情况下，线性时间（关于块总数）
  • 释放成本：
    • 最坏情况下常数复杂度
    • 即使使用合并
  • 内存利用率：
    • 将取决于放置策略
    • first-fit, next-fit, best-fit
  • 由于线性时间分配，所以在malloc()/free()中未使用
    • 在特殊场合下会使用
  • 拆分和边界标记合并的概念对所有分配器都是通用的
显式空闲
显式空闲链表

  • 维护空闲链表块，而不是所有块
    • 下一个空闲块可以在堆中的任何地方
      • 所以我们需要存储前/后指针，而不仅仅是大小
    • 幸运的是，我们只跟踪空闲块，所以我们可以使用有效载荷区域作为指针
    • 仍然需要边界标记进行合并

  • 逻辑上（双向链表）：

  • 物理上：块可以任意顺序

从显式空闲链表分配

使用显式空闲链表释放

  • 插入策略：在空闲链表中，把新释放的块放在哪？

    • 后进先出策略

      • 在空闲链表的开头插入已释放的块
      • 优点：简单、常数时间
      • 缺点：研究表明，碎片化程度比地址顺序策略更糟糕

    • 地址排序策略

      • 插入已释放的块，使可用链表块始终按地址顺序排列：

      • 缺点：释放块时需要进行线性时间搜索

      • 优点：研究表明碎片程度比后进先出法低

使用LIFO策略释放(情形1)

使用LIFO策略释放(情形2)

使用LIFO策略释放(情形3)

使用LIFO策略释放(情形4)

显式链表总结
  • 与隐式链表的比较：
    • 分配关于空闲块数是线性时间，而不是所有块数
      • 当大部分内存都已满时，速度要快得多
    • 分配和释放要稍微复杂一些，因为需要在链表内和链表外拼接块
    • 一些额外的空间用于链接（每个块需要2个额外的单词）
      • 可能会增加最小块大小，导致更多的内部碎片
  • 显式链表最常用的用法是与独立自由链表结合使用
    • 保留不同大小类的多个链表：用于不同类型的对象
独立空闲链表

  • 每个大小的块类都有自己的空闲链表

  • 经常为每一个小尺寸的设置单独的类

  • 对于较大尺寸：每双倍尺寸一个类

Seglist分配器
  • 给定一个空闲链表数组，每个空闲链表用于某个大小的类
  • 要分配大小为$n$的块：
    • 搜索适当的空闲链表以查找大小$m>n$的块
    • 如果找到合适的块：
      • 拆分块并将片段放在适当的链表中（可选）
    • 如果没有找到块，请尝试下一个更大的类
    • 重复执行，直到找到块
  • 如果没有找到块：
    • 从操作系统请求额外的堆内存（使用sbrk(）)
    • 从新内存中分配$n$个字节的块
    • 将剩余部分作为最大大小类的单个空闲块放置
  • 要释放块：
    • 合并并放在适当的链表上（可选）
  • seglist分配器的优点
    • 更高的吞吐量
    • 更好的内存利用率
      • 独立空闲链表的first-fit搜索结果接近于整个堆上的best-fit
      • 极端情况：给定块的大小类等同于best-fit。
关键分配器策略总结
  • Placement策略：
    • first-fit, next-fit, best-fit等。
    • 降低的吞吐量以减少碎片
    • 观察：独立空闲链表近似于best-fit策略，而无需搜索整个空闲链表
  • 划分策略：
    • 什么时候划分空闲块？
    • 愿意容忍多少内部划分？
  • 合并策略：
    • 立即合并：每次调用free()时合并
    • 延迟合并：直到有需要时才合并，以提高free()的性能，例子：
      • 为malloc()扫描空闲链表时合并
      • 当外部碎片达到一定阈值时合并

垃圾回收

隐式内存分配：垃圾回收

  • 垃圾回收：自动回收分配给堆的存储——应用程序无需释放

    void foo() {
   int *p = (int *)malloc(128);
   return;  /* p block is now garbage */
}

  • 在函数式语言，脚本语言和现代面向对象的语言中常见：

    • Lisp，ML，Java，Perl，Mathematica

  • C和C++中不同（“保守”垃圾回收器）

    • 不一定回收所有垃圾
垃圾回收
  • 内存分配器如何知道何时可以释放内存？
    • 通常，我们不知道将来将使用什么，因为它取决于条件
    • 但是，我们可以说，如果某些块没有指针指向他们，则无法使用
  • 因此，内存分配器需要知道什么是指针，什么不是指针。如何做到这一点？
  • 我们将对指针进行一些假设：
    • 内存分配器可以区分指针和非指针
    • 所有指针都指向堆中块的开始
    • 应用程序无法隐藏指针（例如，将其强制为int，然后再次返回）
经典GC(垃圾回收)算法
  • 标记和扫描回收（McCarthy，1960）
    • 不移动块（除非“压缩”）
  • 引用计数（Collins，1960年）
    • 不移动块（不讨论）
  • 复制回收（Minsky，1963年）
    • 移动块（不讨论）
  • Generational回收（Lieberman and Hewitt，1983）
    • 根据寿命收集
      • 大多数分配很快就会变成垃圾
      • 因此，将回收工作集中在最近分配的内存区域上
  • 有关更多信息：Jones和Lin，“垃圾回收：自动动态内存算法”，John Wiley＆Sons，1996年。
将内存视为图
  • 我们将内存视为有向图
    • 每个分配的堆块都是图中的一个节点
    • 每个指针都是图中的一条边
    • 不在堆中的包含指向堆的指针的位置称为根节点（例如寄存器，堆栈上的位置，全局变量）

  • 如果存在从任何根到该节点的路径，则一个节点（块）是可到达的
  • 不可访问的节点是垃圾（应用程序不需要）
标记和扫描回收
  • 可以建立在malloc/free库之上
    • 使用malloc分配，直到“空间不足”
  • 空间不足时：
    • 在每个块的开头使用额外的标记位
    • 标记：从根节点开始，并在每个可到达的块上设置标记位
    • 扫描：扫描所有未标记的块和空闲块

简单实现的假设
  • 应用程序可以使用以下函数：
    • new(n)：返回指向新块的指针，该块的所有位置都清除了
    • read(b, i)：将块b的位置i读入寄存器
      • b[i]
    • write(b,i,v)：将v写入块b的位置i
      • b[i] = v
  • 每个块都有一个头字
    • b[-1]
  • 垃圾回收器使用的函数：
    • is_ptr(p)：确定p是否是指向块的指针
    • length(p)：返回p指向的块的长度，不包括头
    • get_roots()：返回所有根节点
标记和回收（续）

使用内存图的深度优先遍历进行标记

ptr mark(ptr p) {                 // p: some word in a heap block
   if (!is_ptr(p)) return;        // do nothing if not pointer
   if (markBitSet(p)) return;     // check if already marked
       setMarkBit(p);             // set the mark bit
   for (i=0; i < length(p); i++)  // recursively call mark on
       mark(p[i]); 		    	 //   all words in the block
   return;
}

使用长度进行扫描以查找下一个块

ptr sweep(ptr p, ptr end) {        // ptrs to start & end of heap
   while (p < end) {		      // while not at end of heap
      if markBitSet(p)             // check if block is marked         
          clearMarkBit();          // if so, reset mark bit
      else if (allocateBitSet(p))  // if not marked, but allocated
          free(p);                 // free the block
      p += length(p);              // adjust pointer to next block
}
C语言中的保守标记和扫描

  • 可以在C语言中进行标记和清除工作吗？

    • is_ptr()（上一张幻灯片）通过检查单词是否指向已分配的内存块来确定单词是否为指针

    • 但是在C语言中，指针可以指向已分配块的中间（在Java中不是）

      • 难以在标记阶段找到所有分配的块

    • 有一些方法可以再C中解决/避免该问题问题，但是生成的垃圾回收器是保守的：

      • 每个可到达节点正确地标识为可到达，但是某些不可达节点可能被错误地标记为可到达

C程序中与内存相关的常见错误

内存相关的风险和陷阱
  • 取消引用错误的指针
  • 读取未初始化的内存
  • 覆盖内存
  • 引用不存在的变量
  • 释放块多次
  • 引用释放的块
  • 无法释放块
取消引用错误的指针

  • 经典scanf错误

    int val;

...

scanf(“%d”, val);

  • 将导致scanf将val的内容解释为地址！

    • 最佳情况：程序由于分段错误而立即终止
    • 最坏的情况：val的内容对应于虚拟内存的某个有效读/写区域，从而导致scanf覆盖该内存，从而在程序执行的后期产生灾难性和令人困惑的后果
读取未初始化的内存

  • 假设堆数据初始化为零

    /* return y = Ax */
int *matvec(int **A, int *x) { 
   int *y = (int *)malloc( N * sizeof(int) );
   int i, j;

   for (i=0; i<N; i++) {
      for (j=0; j<N; j++) {
         y[i] += A[i][j] * x[j];
      }
   }
   return y;
}
覆盖内存

  • 分配（可能）尺寸错误的对象

    int **p;

p = (int **)malloc( N * sizeof(int) );

for (i=0; i<N; i++) {
   p[i] = (int *)malloc( M * sizeof(int) );
}

  • off-by-one错误

    int **p;

p = (int **)malloc( N * sizeof(int *) );

for (i=0; i<=N; i++) {
   p[i] = (int *)malloc( M * sizeof(int) );
}

  • 没有检查最大字符串大小

    char s[8];
int i;

gets(s);  /* reads “123456789” from stdin */
    • 经典缓冲区溢出攻击的基础

  • 误解指针运算

    int *search(int *p, int val) {
   
   while (p && *p != val)
      p += sizeof(int);
      //should be p++

   return p;
}

  • 引用指针而不是它指向的对象

    int *getPacket(int **packets, int *size) {
   int *packet;
   packet = packets[0];
   packets[0] = packets[*size - 1];
   *size--;   // what is happening here?
   reorderPackets(packets, *size);
   return(packet);
}
    • —和*运算符具有相同的优先级，并且从右到左关联，因此—首先发生！
引用不存在的变量

  • 忘记当函数返回时局部变量消失

    int *foo () {
   int val;

   return &val;
}
多次释放块
x = (int *)malloc( N * sizeof(int) );
        <manipulate x>
free(x);
...

y = (int *)malloc( M * sizeof(int) );
free(x);
        <manipulate y>
引用释放的块
x = (int *)malloc( N * sizeof(int) );
  <manipulate x>
free(x);
   ...
y = (int *)malloc( M * sizeof(int) );
for (i=0; i<M; i++)
   y[i] = x[i]++;
无法释放块（内存泄露）
foo() {
   int *x = (int *)malloc(N*sizeof(int));
   ...
   return;
}
处理内存错误
  • 常规调试器（gdb）
    • 非常适合查找糟糕的指针取消引用
    • 难以发现其他内存错误
  • 调试malloc（UToronto CSRI malloc）
    • 围绕常规malloc的包装
    • 检测malloc和free边界处的内存错误
      • 损坏堆结构的内存覆盖
      • 多次释放块的某些情况
      • 内存泄漏
    • 无法检测到所有内存错误
      • 覆盖已分配块的中间
      • 释放两次已在中间重新分配的块
      • 引用释放的块
  • 一些malloc实现包含检查代码
    • Linux glibc malloc: setenv,MALLOC_CHECK_ 2
    • FreeBSD: setenv,MALLOC_OPTIONS,AJR
  • 二进制翻译器：valgrind(Linux)，Purify
    • 强大的调试和分析技术
    • 重写可执行文件的文本部分
    • 可以在调试malloc时检测所有错误
    • 也可以在运行时检查每个引用
      • 错误的指针
      • 覆写
      • 在分配的块之外引用