[译] Ｃ程序员该知道的内存知识 (2)

[felix021]

感觉这篇文章可能是太干了，不过既然挖了坑，还是努力填。有任何问题都欢迎探讨。

---

续上篇：

• [译] Ｃ程序员该知道的内存知识 (1)

这是本系列的第二篇，预计还会有 2 篇，感兴趣的同学记得关注，以便接收推送，等不及的推荐阅读原文。

---

先放图镇楼：

来源：Linux 地址空间布局 - by Gustavo Duarte

关于图片的解释可参见上篇。

开始吧。

---

理解堆上的内存分配

工具箱：

• brk(), sbrk() - 修改数据段的大小
• malloc() 家族 - 可移植的 libc 内存分配器

堆上的内存分配，最简单的实现可以是修改 program break[2]（译注：参见上图中部右侧）的上界，申请对原位置和新位置之间内存的访问权限。如果就这么搞的话，堆上内存分配和栈上分配一样快（除了换页的开销，一般我们认为栈是被锁定在内存中；译注：指栈不会被换出到磁盘，可以用 mlock 限制 OS 对一段地址空间使用 swap ）。但这里还是有只猫（ cat ），我是说，有点毛病（ catch ），见鬼。（译 tu 注 cao：这个真难翻）

char *block = sbrk(1024 * sizeof(char));

• 我们无法回收不再使用的内存块
• 它也不是线程安全的，因为堆是在线程间共享的
• 这个接口（译注：sbrk ）也很难移植，因此库函数被禁止碰这个 break 。

man 3 sbrk — 各种系统的 sbrk 使用多种不同的参数类型，常见的包括 int, ssize_t, ptrdiff_t, intptr_t

由于这些问题，libc 要求实现统一的内存分配接口，具体实现有很多[3]（译注：例如 glibc，jemalloc，tcmalloc 等），但都给你提供了线程安全、支持任意尺寸的内存分配器……只是要付出点代价——延迟，因为得引入锁机制，以及用来维护已用 /可用内存的数据结构，和额外的内存开销。还有，堆也不是唯一的选项，在大块内存分配的情况下常常也会用内存映射段（ Memory Mapping Segment，MMS ）。

man 3 malloc —— 一般来说，malloc() 从堆上分配内存,  ... 当分配的内存块大于 MMAP_THRESHOLD 时，glibc 的 malloc() 实现使用私有匿名映射来分配内存。

（译注：Linux 下 mmap 的 flags 参数是个 bitmap，其中有两个 bit 分别为 MAP_PRIVATE 、MAP_ANONYMOUS，对应引用中提到的“私有”、“匿名”）

由于堆空间在 start_brk 和 brk （译注：即 heap 的下界和上界，建议对照图中右侧的标注）之间总是连续的（译注：这里指的是虚拟地址空间连续，但其中每一页都可能映射到任一物理页），因此你无法在中间打个洞来减少数据段的尺寸。比如这个场景：

char *truck = malloc(1024 * 1024 * sizeof(char));
char *bike  = malloc(sizeof(char));
free(truck);

堆分配器将会调大 brk，以便给 truck 腾出空间。对于 bike 也一样。但是当 truck 被释放后，brk 不能被调小，因为 bike 正占着高位的地址。结果是，你的进程可以重用 truck 的内存，但不能退还给 OS，除非 bike 也被释放。当然你也可以用 mmap 来分配 truck 所需的空间，不放在堆内存段里，就可以不影响 program break，但这仍然无法解决分配小块内存导致的空洞（换句话说就是“引起碎片化”）。

注意 free() 并不总是会缩小数据段，因为这是一个有很大潜在开销的操作（参见后文“对按需调页的解释”）。对于需要长时间运行的程序（例如守护进程）来说这会是个问题。有个叫  malloc_trim() 的 GNU 扩展可以用来从堆顶释放内存，但可能会慢得令人蛋疼，尤其对于大量小对象的情况，所以应该尽量少用。

什么时候应该使用自定义分配器

有一些实际场景中通用分配器有短板，例如大量分配固定尺寸的小内存。这看起来不像是典型的场景，但实际上出现得很频繁 。例如，用于查找的数据结构（典型如树、字典树）需要分配大量节点用于构造其层次结构。在这个场景下，不仅碎片化会是个问题，数据的局部性也是。cache 效率高的数据结构会将 key 放在一起（最好在同一个内存页），而不是和数据混在一起。默认的分配器不能保证下次分配时还在同一个 block，更糟的是分配小单元的额外空间开销。解决办法在此：

X

来源: Slab by wadem, on Flickr (CC-BY-SA)

（译注：原图无法打开了，另贴一张）

来源：IBM - Linux slab 分配器剖析

Slab 分配器

工具箱：

• posix_memalign() - 分配对齐的内存

Bonwick 为内核对象缓存写的这篇文章[4]介绍了 slab 分配器的原理，也可用于用户空间。Okay，我们对绑定在 CPU 上的 slab 不感兴趣 —— 就是你找分配器要一块内存，例如说一整页，然后切成很多固定大小的小块。如果每个小块都能保存至少一个指针或一个整数，你就可以把他们串成一个链表 ，表头指向第一个空闲元素。

/* Super-simple slab. */
struct slab {
	void **head;
};

/* Create page-aligned slab */
struct slab *slab = NULL;
posix_memalign(&slab, page_size, page_size);
slab->head = (void **)((char*)slab + sizeof(struct slab));

/* Create a NULL-terminated slab freelist */
char* item = (char*)slab->head;
for(unsigned i = 0; i < item_count; ++i) {
	*((void**)item) = item + item_size;
	item += item_size;
}
*((void**)item) = NULL;

译注：

1. 代码里用的二级指针可能让人有点晕，这是 Linus 推崇的链表实现，推荐阅读"linus torvalds answers your questions"5，在 favorite hack 这一节，是个很有趣的思维训练
2. 第 8 行 posix_memalign 分配了一页内存，并且对齐到页边界，这意味着正好拿到了一个物理页
3. 因为申请到的 slab 大小是一个 page，所以 item_count = page_size / item_size；其中 item_size 可以根据应用需要指定。

然后内存分配就简单到只要弹出链表的头结点就行了，内存释放则是插入头结点。这里还有个优雅的小技巧：既然 slab 对齐到了页边界，你只要将指针向下取整到 page_size 就能得到这个 slab 的指针。

/* Free an element */
struct slab *slab = (void *)((size_t)ptr & PAGESIZE_BITS);
*((void**)ptr) = (void*)slab->head;
slab->head = (void**)ptr;

/* Allocate an element */
if((item = slab->head)) {
	slab->head = (void**)*item;
} else {
	/* No elements left. */
}

译注：对于 page_size = 4KB 的页面，PAGESIZE_BITS = 0xFFFFF000，ptr & PAGESIZE_BITS 清零了低 12 位，正好是这一页的开始，也就是这个 slab 的起始地址。

太棒了，但是还有 binning （译注：应该是指按不同的长度分桶），变长存储，cache aliasing （译注：同一个物理地址中的数据出现在多个不同的缓存行中），咖啡因（译注：这应该是作者在逗逼了），...怎么办？可以看看我之前为 Knot DNS 写的代码[6]，或者其他实现了这些点的库。例如，（喘口气），glib 里有个很整齐的文档[7]，把它称为“memory slices”。

译注：slab 分配器适合大量小对象的分配，可以避免常见的碎片问题；在内核中的实现还可以支持硬件缓存对齐，从而提高缓存的利用率。

内存池

工具箱：

• obstack_alloc() - 从 object stack 中分配内存 （译注：指 GNU 的 obstack，用 stack 来保存 object 的内存池实现）

正如 slab 分配器一样，内存池比通用分配器好的地方在于，你每次申请一大块内存，然后像切蛋糕一样一小块一小块切出去，直到不够用了，然后你再申请一大块。还有，当你都处理完了以后，你就可以收工，一次性释放所有空间。

是不是特别傻瓜化？因为确实如此，但只是针对特定场景如此。你不需要考虑同步，也不需要考虑释放。再没有忘记回收的坑了，数据的局部性也更加符合预期，而且对于小对象的开销也几乎为 0 。

这个模式特别适合很多类型的任务，包括短生命周期的重复分配（例如网络请求处理），和长生命周期的不可变数据（例如 frozen set ；译注：创建后不再改变的集合）。你不再需要逐个释放对象（译注：可以最后批量释放）。如果你能合理推测出平均需要多少内存，你还可以将多余的内存释放，以便用于其他目的。这可以将内存分配问题简化成简单的指针运算。

而且你很走运 —— GNU libc 提供了，嗬，一整套 API 来干这事儿。这就是 obstacks，用栈来管理对象。它的 HTML 文档[8] 写得不咋地，不过抛开这些小缺陷，它允许你完成基于内存池的分配和回收（包括部分回收和全量回收）。

/* Define block allocator. */
#define obstack_chunk_alloc malloc
#define obstack_chunk_free free

/* Initialize obstack and allocate a bunch of animals. */
struct obstack animal_stack;
obstack_init (&animal_stack);
char *bob = obstack_alloc(&animal_stack, sizeof(animal));
char *fred = obstack_alloc(&animal_stack, sizeof(animal));
char *roger = obstack_alloc(&animal_stack, sizeof(animal));

/* Free everything after fred (i.e. fred and roger). */
obstack_free(&animal_stack, fred);

/* Free everything. */
obstack_free(&animal_stack, NULL);

译注：obstack 这些 api 实际都是宏；需要通过宏来指定找 OS 分配和回收整块内存用的方法，如上第 2 、3 行所示。由于对象使用栈的方式管理（先分配的最后释放），所以释放 fred 的时候，会把 fred 和在 fred 之后分配的对象（ roger ）一起释放掉。

还有个小技巧：你可以扩展栈顶的那个对象。例如带缓冲的输入，变长数组，或者用来替代 realloc()-strcpy() 模式（译注：重新分配内存，然后把原数据拷贝过去）：

/* This is wrong, I better cancel it. */
obstack_grow(&animal_stack, "long", 4);
obstack_grow(&animal_stack, "fred", 5);
obstack_free (&animal_stack, obstack_finish(&animal_stack));

/* This time for real. */
obstack_grow(&animal_stack, "long", 4);
obstack_grow(&animal_stack, "bob", 4);
char *result = obstack_finish(&animal_stack);
printf("%s\n", result); /* "longbob" */

译注：前三行是作者逗逼了，看后四行就行；用 obstack_grow 扩展栈顶元素占用的内存，扩展结束后调用 obstack_finish 结束扩展，并返回栈顶元素的地址。

对按需调页（ demand paging ）的解释

工具箱：

• mlock() - 锁定 /解锁内存（避免被换出到 swap ）
• madvise() - 给（内核）建议指定内存范围的处置方式

通用内存分配器不立即将内存返回给系统的原因之一是，这个操作开销很大。系统需要做两件事：(1) 建立虚拟页到真实（ real ）页的映射，和 (2) 给你一个清零的真实页。这个真实页被称为帧（ frame ），现在你知道它们的差别了。每一帧都必须被清空，毕竟你不希望 OS 泄漏其他进程的秘密，对吧。这里还有个小技巧，还记得 overcommit 吗？虚拟内存分配器只把这个交易刚开始的那部分当回事，然后就开始变魔术了 —— 页表里的大部分页面并不指向一个真实页，而是指向一个特殊的全 0 页面。

每次你想要访问这个页面时，就会触发一个 page fault，这意味着内核会暂停 进程的执行，分配一个真实页、更新页表，然后恢复进程，并假装什么也没发生。这是汇总在一句话里、我能做出的最好解释了，这里[9]还有更个详细的版本。这也被称作**“按需调页”（ demand paging ）** 或 “延迟加载”（ lazy loading ）。

斯波克船长说“人无法召唤未来”，但这里你可以操控它。

（译注：星际迷航，斯波克说“One man cannot summon the future.”，柯克说“But one man can change the present.”）

内存管理器不是先知，他只是保守地预测你访问内存的方式，而你自己也未必更清楚（你将会怎样访问内存）。（如果你知道）你可以将一段连续的内存块锁定在物理内存中，以避免后续的 page fault：

char *block = malloc(1024 * sizeof(char));
mlock(block, 1024 * sizeof(char));

（译注：访问被换出到 swap 的页面会触发 page fault，然后内存管理器会从磁盘中载入页面，这会导致较严重的性能问题；用 mlock 将这段区域锁定后，OS 就不会被操作系统换出到 swap ；例如，在允许的情况下，MySQL 会用 mlock 将索引保持在物理内存中）

注意：你还可以根据自己的内存使用模式，给内核提出建议

char *block = malloc(1024 * sizeof(block));
madvise(block, 1024 * sizeof(block), MADV_SEQUENTIAL);

对建议的解释是平台相关的，系统甚至可能选择忽略它，但大部分平台都处理得很好。但不是所有建议都有良好的支持，有些平台可能会改变建议的语义（如 MADV_FREE 移除私有脏页；译注：“脏页”，dirty page，是指分配以后有过写入，其中可能有未保存的数据），但是最常用的还是 MADV_SEQUENTIAL, MADV_WILLNEED, 和 MADV_DONTNEED 这神圣三人组（译注：holy trinity，圣经里的三位一体，作者用词太跳脱……）。

译注：还记得《踩坑记：go 服务内存暴涨》里对 MADV_DONTNEED 和 MADV_FREE 的解释吗？这里再回顾下

• MADV_DONTNEED：不再需要的页面，Linux 会立即回收
• MADV_FREE：不再需要的页面，Linux 会在需要时回收
• MADV_SEQUENTIAL：将会按顺序访问的页面，内核可以通过预读随后的页面来优化，已经访问过的页面也可以提前回收
• MADV_WILLNEED：很快将访问，建议内核提前加载

---

---

又到休息点，这篇暂时到这里。

下一篇会继续翻译下一节《 Fun with memory mapping 》，还有很多有意思的内容，敬请关注~

顺便再贴下之前推送的几篇文章，祝过个充实的五一假期~

• 《踩坑记：go 服务内存暴涨》

• 《TCP：学得越多越不懂》

• 《TCP#2: 西厢记和西厢计划》

• 《UTF-8：一些好像没什么用的冷知识》

• 《关于 RSA 的一些趣事》

• 《程序员面试指北：面试官视角》

欢迎关注

   ▄▄▄▄▄▄▄   ▄      ▄▄▄▄ ▄▄▄▄▄▄▄  
   █ ▄▄▄ █ ▄▀ ▄ ▀██▄ ▀█▄ █ ▄▄▄ █  
   █ ███ █  █  █  █▀▀▀█▀ █ ███ █  
   █▄▄▄▄▄█ ▄ █▀█ █▀█ ▄▀█ █▄▄▄▄▄█  
   ▄▄▄ ▄▄▄▄█  ▀▄█▀▀▀█ ▄█▄▄   ▄    
   ▄█▄▄▄▄▄▀▄▀▄██   ▀ ▄  █▀▄▄▀▄▄█  
   █ █▀▄▀▄▄▀▀█▄▀█▄▀█████▀█▀▀█ █▄  
    ▀▀  █▄██▄█▀  █ ▀█▀ ▀█▀ ▄▀▀▄█  
   █▀ ▀ ▄▄▄▄▄▄▀▄██  █ ▄████▀▀ █▄  
   ▄▀▄▄▄ ▄ ▀▀▄████▀█▀  ▀ █▄▄▄▀▄█  
   ▄▀▀██▄▄  █▀▄▀█▀▀ █▀ ▄▄▄██▀ ▀   
   ▄▄▄▄▄▄▄ █ █▀ ▀▀   ▄██ ▄ █▄▀██  
   █ ▄▄▄ █ █▄ ▀▄▀ ▀██  █▄▄▄█▄  ▀  
   █ ███ █ ▄ ███▀▀▀█▄ █▀▄ ██▄ ▀█  
   █▄▄▄▄▄█ ██ ▄█▀█  █ ▀██▄▄▄  █▄  

---

参考链接：

1. What a C programmer should know about memory

2. sbrk(2) - Linux man page

3. C Programming/stdlib.h/malloc

4. The Slab Allocator: An Object-Caching Kernel Memory Allocator

5. linus torvalds answers your questions

6. Knot DNS - slab.h

7. glib  - memory slices

1. GNU libc - Obstacks

2. How the kernel manages your memory

[teawithlife]

请教一下楼主：按照文章的说法，对于长期跑的 C++程序，是不是即使我用了各种智能指针，保证变量都能妥善的释放，但是由于“空洞”的存在，操作系统并不能回收这部分内存？虽然这部分内存，我的程序可以使用，但是由于每次申请的内存大小是不一样的，所以这些“空洞”会越来越多，最后的结果就是系统可用内存越来越少？
如果用其他语言，比如 golang，python，也会有这种问题吗，还是 gc 会自行解决这个问题？

[felix021]

@teawithlife 不是，文中说了，free/delete 以后得空洞，会被 madvise 调用通知 os，对应的 page 是可以回收的，建议再看一遍~

[felix021]

@teawithlife 正经的语言都会实现相应的逻辑(用 madvise 通知系统可以回收不再用的页面)，否则无法支撑需要长时间运行的任务。不够正经的，比如 php，你看 php fpm 的配置里面有个 max_requests，处理 n 个任务后就重启一次，避免占着茅坑不拉屎。

[teawithlife]

@felix021 #3 呃，那 C++算正经的语言吗？还是得自己手动调 madvise ？

[felix021]

@teawithlife 当然正经，free/delete 会在必要的时候调用 madvise 的，感兴趣的话可以去翻翻 glibc 的代码 __libc_free 的代码量不是很多

[teawithlife]

@felix021 #5 好的，非常感谢。期待下一篇！

[lostpg]

有意思，支持

[fixend]

glibc 的内存分配很慢，实际开发上都用 tcmalloc，jemalloc，也可以看看 go 的运行时 go/src/runtime/malloc.go

[felix021]

@fixend 嗯 我们这边用 jemalloc，不过有遇到 bug，会在某些场景导致 core

[fixend]

@felix021 tcmalloc 还算稳定，没遇过什么大问题。用了这些库，有一个不好的地方，就是堆内存越界，总是很久后才 core，并且 call stack 大部分情况下会是 tcmalloc 的代码。行为上变得跟栈越界一样难查。

[zhuyie]

文章是好文章，只是有点标题党。C 是跨平台的，大把程序员在 Windows 下写 C/C++程序（例如绝大部分主流游戏公司），32bit Windows 下的地址空间布局可不是这样的。

[felix021]

@zhuyie 嗯，所以在原文的开头作者就声明了是基于 Linux 下的 C99 写的

[r1ng0]

请叫个问题呢 slab 中的小对象 能跨页么？

[felix021]

@r1ng0 看实现，如果你一次申请 n 页（ n>1 ）作为一个 slab，那就可以跨页。