课程主页: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时检测所有错误
    • 也可以在运行时检查每个引用
      • 错误的指针
      • 覆写
      • 在分配的块之外引用