V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
felix021
V2EX  ›  程序员

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

  •  
  •   felix021 ·
    felix021 · 2020-05-05 11:16:56 +08:00 · 2324 次点击
    这是一个创建于 536 天前的主题,其中的信息可能已经有所发展或是发生改变。

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


    续上篇:

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


    先放图镇楼:

    linuxFlexibleAddressSpaceLayout.png

    来源: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)

    (译注:原图无法打开了,另贴一张)

    slab.gif

    来源: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 》,还有很多有意思的内容,敬请关注~

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

    欢迎关注

    weixin2s.png

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

    参考链接:

    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

    14 条回复    2020-05-11 11:56:22 +08:00
    teawithlife
        1
    teawithlife   2020-05-05 11:51:13 +08:00
    请教一下楼主:按照文章的说法,对于长期跑的 C++程序,是不是即使我用了各种智能指针,保证变量都能妥善的释放,但是由于“空洞”的存在,操作系统并不能回收这部分内存?虽然这部分内存,我的程序可以使用,但是由于每次申请的内存大小是不一样的,所以这些“空洞”会越来越多,最后的结果就是系统可用内存越来越少?
    如果用其他语言,比如 golang,python,也会有这种问题吗,还是 gc 会自行解决这个问题?
    felix021
        2
    felix021   2020-05-05 11:54:17 +08:00 via Android
    @teawithlife 不是,文中说了,free/delete 以后得空洞,会被 madvise 调用通知 os,对应的 page 是可以回收的,建议再看一遍~
    felix021
        3
    felix021   2020-05-05 11:57:14 +08:00 via Android   ❤️ 1
    @teawithlife 正经的语言都会实现相应的逻辑(用 madvise 通知系统可以回收不再用的页面),否则无法支撑需要长时间运行的任务。不够正经的,比如 php,你看 php fpm 的配置里面有个 max_requests,处理 n 个任务后就重启一次,避免占着茅坑不拉屎。
    teawithlife
        4
    teawithlife   2020-05-05 12:05:13 +08:00
    @felix021 #3 呃,那 C++算正经的语言吗?还是得自己手动调 madvise ?
    felix021
        5
    felix021   2020-05-05 12:09:22 +08:00 via Android   ❤️ 1
    @teawithlife 当然正经,free/delete 会在必要的时候调用 madvise 的,感兴趣的话可以去翻翻 glibc 的代码 __libc_free 的代码量不是很多
    teawithlife
        6
    teawithlife   2020-05-05 12:13:49 +08:00
    @felix021 #5 好的,非常感谢。期待下一篇!
    lostpg
        7
    lostpg   2020-05-05 12:19:13 +08:00 via Android
    有意思,支持
    fixend
        8
    fixend   2020-05-05 12:44:56 +08:00 via Android
    glibc 的内存分配很慢,实际开发上都用 tcmalloc,jemalloc,也可以看看 go 的运行时 go/src/runtime/malloc.go
    felix021
        9
    felix021   2020-05-05 12:51:33 +08:00 via Android
    @fixend 嗯 我们这边用 jemalloc,不过有遇到 bug,会在某些场景导致 core
    fixend
        10
    fixend   2020-05-05 13:19:40 +08:00 via Android
    @felix021 tcmalloc 还算稳定,没遇过什么大问题。用了这些库,有一个不好的地方,就是堆内存越界,总是很久后才 core,并且 call stack 大部分情况下会是 tcmalloc 的代码。行为上变得跟栈越界一样难查。
    zhuyie
        11
    zhuyie   2020-05-06 10:10:47 +08:00
    文章是好文章,只是有点标题党。C 是跨平台的,大把程序员在 Windows 下写 C/C++程序(例如绝大部分主流游戏公司),32bit Windows 下的地址空间布局可不是这样的。
    felix021
        12
    felix021   2020-05-06 10:25:43 +08:00
    @zhuyie 嗯,所以在原文的开头作者就声明了是基于 Linux 下的 C99 写的
    r1ng0
        13
    r1ng0   2020-05-09 18:26:53 +08:00
    请叫个问题呢 slab 中的小对象 能跨页么?
    felix021
        14
    felix021   2020-05-11 11:56:22 +08:00
    @r1ng0 看实现,如果你一次申请 n 页( n>1 )作为一个 slab,那就可以跨页。
    关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2173 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 05:24 · PVG 13:24 · LAX 22:24 · JFK 01:24
    ♥ Do have faith in what you're doing.