The Hardware Software Interface Section 10 Memory Allocation

课程主页: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库
1
2
#include <stdlib.h>
void *malloc(size_t size)
  • 成功:
    • 返回一个指向内存块的指针,大小至少为size(向8对齐)字节
    • 如果size == 0,则返回NULL
  • 不成功:返回NULL,设置errno
1
void free(void *p)
  • 将p指向的块返回到可用内存池中
  • p必须来自之前对malloc或realloc的调用

其他函数

  • calloc:将分配的块初始化为零的malloc版本。
  • realloc:改变先前分配的块大小。
  • sbrk:由分配器内部使用,用于增大或缩小堆
Malloc例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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:

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

      1
      2
      3
      4
      5
      p = heap_start; 
      while ((p < end) && \\ not passed end
      ((*p & 1) || \\ already allocated
      (*p <= len))) \\ too small
      p = p + (*p & -2); \\ goto next block
    • 1
      2
      3
      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慢
隐式链表:在空闲块中分配
  • 空闲块分配:拆分

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

    • 1
      2
      3
      4
      5
      6
      7
      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
隐式链表:释放块
  • 最简单的实现:

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

      1
      void free_block(ptr p) { *p = *p & -2 }
    • 但会导致“虚假碎片”

    • 如果运行malloc(5)

      • 那么有足够的空闲空间,但分配器无法找到它
隐式链表:合并
  • 连接(合并)下一个/上一个块(如果它们是空闲的)

    • 与下一个块合并

      1
      2
      3
      4
      5
      6
      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()扫描空闲链表时合并
      • 当外部碎片达到一定阈值时合并

垃圾回收

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

    1
    2
    3
    4
    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():返回所有根节点
标记和回收(续)

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

1
2
3
4
5
6
7
8
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;
}

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

1
2
3
4
5
6
7
8
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错误

    1
    2
    3
    4
    5
    int val;

    ...

    scanf(“%d”, val);
  • 将导致scanf将val的内容解释为地址!

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    /* 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;
    }
覆盖内存
  • 分配(可能)尺寸错误的对象

    1
    2
    3
    4
    5
    6
    7
    int **p;

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

    for (i=0; i<N; i++) {
    p[i] = (int *)malloc( M * sizeof(int) );
    }
  • off-by-one错误

    1
    2
    3
    4
    5
    6
    7
    int **p;

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

    for (i=0; i<=N; i++) {
    p[i] = (int *)malloc( M * sizeof(int) );
    }
  • 没有检查最大字符串大小

    1
    2
    3
    4
    char s[8];
    int i;

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

    1
    2
    3
    4
    5
    6
    7
    8
    int *search(int *p, int val) {

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

    return p;
    }
  • 引用指针而不是它指向的对象

    1
    2
    3
    4
    5
    6
    7
    8
    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);
    }
    • —和*运算符具有相同的优先级,并且从右到左关联,因此—首先发生!
引用不存在的变量
  • 忘记当函数返回时局部变量消失

    1
    2
    3
    4
    5
    int *foo () {
    int val;

    return &val;
    }
多次释放块
1
2
3
4
5
6
7
8
x = (int *)malloc( N * sizeof(int) );
<manipulate x>
free(x);
...

y = (int *)malloc( M * sizeof(int) );
free(x);
<manipulate y>
引用释放的块
1
2
3
4
5
6
7
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]++;
无法释放块(内存泄露)
1
2
3
4
5
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时检测所有错误
    • 也可以在运行时检查每个引用
      • 错误的指针
      • 覆写
      • 在分配的块之外引用

本文标题:The Hardware Software Interface Section 10 Memory Allocation

文章作者:Doraemonzzz

发布时间:2020年09月15日 - 23:31:00

最后更新:2020年09月20日 - 13:20:41

原始链接:http://doraemonzzz.com/2020/09/15/The Hardware Software Interface Section 10 Memory Allocation/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。