Why does calloc exist?

 

原文链接:https://vorpus.org/blog/why-does-calloc-exist/

在用 C 语言编程时,有两种标准方法可以在堆上分配一些新内存:

void* buffer1 = malloc(size);
void* buffer2 = calloc(count, size);

malloc 分配一个具有给定字节数的未初始化数组,即 buffer1 可以包含任何内容。就其公共 API 而言,calloc 在两个方面有所不同:首先,它接受两个参数而不是一个参数;其次,它返回预初始化为全零的内存。所以有很多书籍和网页声称上面的 calloc 调用等同于调用 malloc,然后调用 memset 用零填充内存:

/* Equivalent to the calloc() call above -- OR IS IT?? */
void* buffer3 = malloc(count * size);
memset(buffer3, 0, count * size);

那么为什么 calloc 存在,如果它等同于这两行? C 库并不以过度专注于提供方便的速记而闻名!

事实证明,答案并没有我想象的那么广为人知!如果此时我是 Julia Evans,我会制作一个简洁的小漫画😊。但我不是,所以…这是一堵文字墙。

Julia Evans 的网站: https://drawings.jvns.ca/

事实证明,调用 calloc 与调用 malloc + memset 之间实际上有两个区别。

一.运算

当 calloc 乘以 count * size 时,它​​会检查溢出,如果乘法返回的值不适合 32 位或 64 位整数(无论哪个与您的平台相关),都会出错。这很好。如果你按照我上面做的天真方式做乘法,只写 count * size,那么如果值太大,那么乘法会溢出,malloc 会愉快地分配一个比我们预期的更小的缓冲区。那很糟。“这部分代码认为缓冲区有这么长,但那部分代码认为它有那么长”是每年 1100 亿条安全建议的开始。

我写了一个小程序来演示。它尝试分配一个包含 263 × 263 = 2126 bytes 字节的缓冲区,首先使用 malloc,然后使用 calloc:

#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <stdint.h>

int main(int argc, char** argv)
{
    size_t huge = INTPTR_MAX;

    void* buf = malloc(huge * huge);
    if (!buf) perror("malloc failed");
    printf("malloc(huge * huge) returned: %p\n", buf);
    free(buf);

    buf = calloc(huge, huge);
    if (!buf) perror("calloc failed");
    printf("calloc(huge, huge) returned: %p\n", buf);
    free(buf);
}

在我的电脑上,我得到:

~$ gcc calloc-overflow-demo.c -o calloc-overflow-demo
~$ ./calloc-overflow-demo
malloc(huge * huge) returned: 0x55c389d94010
calloc failed: Cannot allocate memory
calloc(huge, huge) returned: (nil)

所以是的,显然 malloc 成功分配了一个 73786976294838206464 exbiyte 数组?我相信那会很好。这是 calloc 的一个优点:它有助于避免可怕的安全漏洞。

但是,这并不那么令人兴奋。 (我的意思是,老实说:如果我们真的关心安全性,我们就不会用 C 编写。)它只在您通过将两个数字相乘来决定要分配多少内存的特定情况下有所帮助。这种情况发生了,这是一个重要的案例,但还有很多其他情况,我们要么根本不做任何算术,要么我们正在做一些更复杂的算术并需要更通用的解决方案。另外,如果我们愿意,我们当然可以为 malloc 编写我们自己的包装器,它接受两个参数并将它们相乘并进行溢出检查。事实上,如果我们想要一个溢出安全版本的 realloc,或者如果我们不希望内存被零初始化,那么我们仍然必须这样做。那么,这很好吗?但这并不能真正证明 calloc 的存在。

另一个区别是什么?非常非常重要。

二.虚拟内存

  这是一个小的基准测试程序,用于测量调用 1 GB 缓冲区与 malloc+memset 1 GB 缓冲区所需的时间。 (确保你在没有优化的情况下编译,因为现代编译器足够聪明,知道 free(calloc(…)) 是一个空操作并优化它!)
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>

const int LOOPS = 100;

float now()
{
    struct timespec t;
    if (clock_gettime(CLOCK_MONOTONIC, &t) < 0) {
        perror("clock_gettime");
        exit(1);
    }
    return t.tv_sec + (t.tv_nsec / 1e9);
}

int main(int argc, char** argv)
{
    float start = now();
    for (int i = 0; i < LOOPS; ++i) {
        free(calloc(1, 1 << 30));
    }
    float stop = now();
    printf("calloc+free 1 GiB: %0.2f ms\n", (stop - start) / LOOPS * 1000);

    start = now();
    for (int i = 0; i < LOOPS; ++i) {
        void* buf = malloc(1 << 30);
        memset(buf, 0, 1 << 30);
        free(buf);
    }
    stop = now();
    printf("malloc+memset+free 1 GiB: %0.2f ms\n", (stop - start) / LOOPS * 1000);
}
在我的笔记本电脑上我得到:
~$ gcc calloc-1GiB-demo.c -o calloc-1GiB-demo
~$ ./calloc-1GiB-demo
calloc+free 1 GiB: 3.44 ms
malloc+memset+free 1 GiB: 365.00 ms

即,calloc 快了 100 倍以上。我们的教科书和手册页说它们是等价的。到底发生了什么?

答案当然是 calloc 在作弊。

对于小的分配,calloc 字面上只会调用 malloc+memset,所以它的速度是一样的。但是对于更大的分配,大多数内存分配器会出于各种原因向操作系统发出特殊请求,以便为这次分配获取更多内存。 (这里的“小”和“大”由内存分配器中的一些试探法确定;对于 glibc,“大”是大于 128 KiB 的任何东西,至少在其默认配置中是这样)。

是否启用mmap, mmap通过linux 伙伴系统 申请内存以页为单位。

当操作系统将内存分配给一个进程时,它总是先将其清零,否则我们的进程将能够查看最后一个使用它的进程在该内存中留下的任何碎屑,其中可能包括,例如,加密密钥或其他一些敏感信息。所以这就是 calloc 作弊的第一种方式:当你调用 malloc 分配一个大缓冲区时,那么内存可能来自操作系统并且已经归零,所以不需要调用 memset。但你不确定!内存分配器非常难以理解。所以你必须每次都调用 memset 以防万一。但是 calloc 存在于内存分配器中,所以它知道它返回的内存是否是来自操作系统的新内存,如果是,则它会跳过调用 memset。这就是为什么必须将 calloc 内置到标准库中,并且您无法有效地将其伪装成 malloc 之上的一层。

但这只能解释部分加速:memset+malloc 实际上是清除内存两次,而 calloc 只清除一次,所以我们可能期望 calloc 最多快 2 倍。相反它快了 100 倍。有没有搞错?

原来内核也在作弊!当我们向它请求 1 GiB 的内存时,它实际上并没有出去找到那么多 物理内存 并向其中写入零,然后将其交给我们的进程。相反,它使用虚拟内存来伪造它:它占用一个 4 KiB 的内存页面,该页面已经充满了零(为此目的而保留),并映射 1 GiB / 4 KiB = 262144 copy-on-write它的副本到我们进程的地址空间中。所以我们第一次实际写入这 262144 页中的每一个,然后内核必须去寻找一个真实的 物理内存 页,向其中写入零,然后快速交换它以代替“虚拟”页面以前在那里。但这是在逐页的基础上地发生的。

所以在现实生活中,差异不会像我们在上面的基准测试中看起来那么明显——部分诀窍是 calloc 正在转移一些清零页面的成本,稍后执行,而 malloc+memset 则是申请空间完毕后进行清零处理。但是,至少我们没有将它们清零两次。至少我们没有预先破坏缓存层次结构——如果我们延迟清零直到我们无论如何都要写入页面,那么这意味着两次写入同时发生,事实上我们只需要申请一次一组 TLB / L2 缓存 / 等未命中部分。而且,最重要的是,我们可能永远都没有时间写入所有这些页面,在这种情况下,calloc + 内核偷偷摸摸的诡计是一个巨大的胜利!
当然,calloc 使用的优化的方法因你的环境而异。曾经流行的一个巧妙的技巧是内核会在系统空闲时并推测性地将页面清零 (Pre-zeroing),以便它们在需要时保持更新并准备就绪
但这在当前系统上已经过时了。没有虚拟内存的微型嵌入式系统显然不会使用虚拟内存技巧。但总的来说,calloc 永远不会比 malloc+memset 差,而且在主流系统上它可以做得更好。
PG_ZERO:通过增加零页标识和快速查询列表,重置和分配零页。
PG_ZERO: https://lwn.net/Articles/109188/
但是在现代cpu上预先置零(Pre-zeroing)效率并不高,并且影响性能
https://lists.dragonflybsd.org/pipermail/commits/2016-August/624202.html

一个现实生活中的例子是最近请求中的一个错误,其中通过具有较大接收块大小的 HTTPS 进行流式下载会占用 100% 的 CPU。事实证明,问题是当用户说他们愿意一次处理最多 100 MiB 块时,请求将其传递给 pyopenssl,然后 pyopenssl 使用 cffi.new 分配一个 100 MiB 缓冲区来保存传入的数据。但大多数时候,实际上并没有 100 MiB 准备好在连接上读取;所以 pyopenssl 会分配这个大缓冲区,但随后只会使用其中的一小部分。事实证明,cffi.new 通过执行 malloc+memset 来模拟 calloc,所以他们支付分配和清零整个缓冲区的费用。如果 cffi.new 改用 calloc,那么错误就不会发生了!希望他们能尽快解决这个问题。

https://github.com/pyca/pyopenssl/pull/578

这个提交中已经将内存申请调整为 no_zero_allocator方式

 

或者这里是 numpy 中出现的另一个例子:假设你想制作一个大的单位矩阵,一个有 16384 行和 16384 列的矩阵。这需要分配一个缓冲区来容纳 16384 * 16384 个浮点数,每个浮点数为 8 个字节,因此总共需要 2 GiB 的内存。

在我们创建矩阵之前,我们的进程使用 24 MiB 内存:

>>> import numpy as np
>>> import resource
>>> # this way of fetching memory usage probably only works right on Linux:
>>> def mebibytes_used():
...     return resource.getrusage(resource.RUSAGE_SELF).ru_maxrss / 1024
...
>>> mebibytes_used()
24.35546875
然后我们分配一个 2 GiB 的密集矩阵:然后我们分配一个 2 GiB 的密集矩阵:
>>> big_identity_matrix = np.eye(16384)
>>> big_identity_matrix
array([[ 1.,  0.,  0., ...,  0.,  0.,  0.],
       [ 0.,  1.,  0., ...,  0.,  0.,  0.],
       [ 0.,  0.,  1., ...,  0.,  0.,  0.],
       ...,
       [ 0.,  0.,  0., ...,  1.,  0.,  0.],
       [ 0.,  0.,  0., ...,  0.,  1.,  0.],
       [ 0.,  0.,  0., ...,  0.,  0.,  1.]])
>>> big_identity_matrix.shape
(16384, 16384)

我们的进程现在使用了多少内存?答案可能会让您大吃一惊(现在学习这个奇怪的技巧来精简您的流程)

>>> mebibytes_used()
88.3515625

Numpy 使用 calloc 分配了数组,然后它在对角线上写了 1s…但是数组的大部分仍然是零,所以它实际上并没有占用任何内存,我们的 2 GiB 矩阵适合 ~60 MiB 的实际内存。当然还有其他方法可以完成同样的事情,比如使用真正的稀疏矩阵库,但这不是重点。关键是,如果你这样做,calloc 会神奇地使一切变得更有效率——而且它总是至少和替代方法一样快。

所以基本上,calloc 的存在是因为它让内存分配器和内核参与一个偷偷摸摸的阴谋,让你的代码更快,使用更少的内存。你应该让!不要使用 malloc+memset!

 

参考及引用

图片from Tw.luoyin 旅行客

 

Comments are closed.