这个 malloc 的实现是一个 bump 分配器吗？

Question

我最近写了一个小的 malloc 并且想知道它是否是一个 bump 分配器。我想知道这是因为（如果我错了请纠正我）我相信实际的 malloc（同时使用 mmap 而不是 sbrk）使用相同的技术（有点），但是一个 bump 分配器只是增加堆位置。这是我的代码：

#include <cstdio>
#include <cstddef>
#include <unistd.h>

#define word_size sizeof(intptr_t)
#define align(n) ((n + word_size - 1) & ~(word_size - 1))

void* my_malloc(size_t size) {
    void* p = sbrk(0);
    if (sbrk(align(size)) == (void*) -1)
        return NULL; // failed
    return p;
}

int main() {
    int* foo = (int*) my_malloc(1);
    *foo = 100;
    printf("%d\n", *foo);
}

Answer 1

所以我以前从未听说过"bump allocator"这个词，但这个概念很简单。

这是一个非常简单的分配器，由于涉及的内务处理量很少，所以速度可能非常快，但您必须忍受相当严格的限制：没有针对单个请求的 "free" 操作 - 您只需销毁整个事情。

在您的例子中，您调用 sbrk(0) 以获取程序整个数据段末尾的第一个地址 - 这将是 return 值 - 然后是 "bump"适当四舍五入后，内存结束 sbrk(nbytes)。

这意味着程序的数据 space 只会随着每个请求而增长，尝试释放一些东西没有任何意义，因为你不能在地址中打个洞 space（好吧，可能有一些时髦的 VM 东西可以工作，但这会变得复杂）。

static void *bump_arena_start = 0;

void* my_malloc(size_t size) {
    void* p = sbrk(0);

    if (bump_arena_start == 0) bump_arena_start = p;

    if (sbrk(align(size)) == (void*) -1)
        return NULL; // failed
    return p;
}

void destroy_bump_arena(void)
{
    if (bump_arena_start) brk(bump_arena_start);
}

这可能是一个 bump 分配器，但由于多种原因，它会是一个糟糕。

首先：它假设没有其他人正在分配内存，它必须覆盖所有其他操作：malloc、C++ new、 C运行时间等

想象一下，如果您在休息时自己做事，然后一些 other 函数调用 sbrk() 分配一些内存，会发生什么情况。现在他们在你的舞台中间，但你大多不知道。到目前为止没问题，但是一旦你去摧毁你的竞技场，它就会杀死其他一切。

你实际使用这种东西的方式是当你有很多你不想跟踪的微小分配并且可以一次释放所有时，所以你可以使用系统分配器（malloc()) 并要求一个足够大的块来满足您的需求——我们称它为 32kbytes——并将其填充到代表这个凹凸竞技场的某个对象中。

你在这里和那里分配了很多小位，做你需要做的任何任务，然后通过释放最初的 32 KB 块来销毁所有这些。

问题是：您必须超级小心不要让这些指针之一逃逸到系统的其他部分，因为不允许它们活在你的竞技场生命周期之外。

这只是一个非常专业的用例，可能不是普遍有用的，除非你在做嵌入式工作（你基本上控制自己的运行时间），否则你无法真正做到系统以这种方式中断。

旁注：如果对象大于整数指针的大小，则可能会遇到对齐问题。如果你这样做会怎样？

   int      *foo1 = my_malloc(sizeof(int));       // 8 bytes (usually)
   __int128 *foo2 = my_malloc(sizeof(__int128));  // 16 bytes

天真的对齐会将 int 置于 8 字节边界上，但 128 位值（即 16 字节）也是如此，而不是与其自身的大小对齐；在某些平台上，这可能是一个错误，而且几乎总是效率低下。

要做到这一点，您需要通过 sbrk(0) 查询当前的下一个值，并确保它与大小正确对齐，可能会增加 break a位.

编辑：我对此进行了更深入的研究，很明显您的示例并不能算作碰撞分配器。原因如下。

内存系统不仅会跟踪 "next" 指针，还会跟踪执行了多少次分配，并且它支持忽略指针值但仅递减分配计数器的伪释放操作。

如果分配计数器达到零，这意味着没有其他人拥有任何内存，因此它可以通过将中断倒回初始值来释放所有内容，基本上是从头开始。

要正确使用它，您必须非常小心您的重新分配，并且双重释放可能会非常痛苦。

真正有用的参考：https://os.phil-opp.com/allocator-designs/

EDIT2 - 关于每个请求对齐的更多信息。

无论您在什么平台上，您都必须至少对对齐有一定的了解，因为即使该平台允许对内存进行未对齐访问，它几乎总是更慢。

始终正确的超级简单方法是找出平台支持的最大可能标量对象，并将其用作对齐模数，也许 __int128。如果你总是四舍五入到最接近的 16 个字节，你几乎永远不会运行出现对齐问题（而且很容易）。

但它也是 space 低效的：如果您为两个字节 short 分配 space，它会浪费它后面的 14 个字节。这在您的应用程序中可能没什么大不了的，也可能是一件事。

我自己从来没有写过内存分配器，所以我在这里做了很多工作，但是任何使用 bump 分配器的人都有一些特殊要求，并且可能可以提出特殊要求。

所以：我可以想象一个分配器不仅需要大小，还需要对齐，它会使用 sbrk(0) 指针并将 that 向上舍入所需的对齐方式，将其保存为 return 值，然后调用 sbrk(size) 来碰撞结束标记。

请注意，您没有与分配的大小对齐，而只是与低级项目的大小对齐：要求 20 个 short 值的数组意味着您要求 40 个字节但是对齐为 2，字符串的 100 个字节意味着您只需采用接下来的 100 个字节 w/o 任何对齐方式。

void *my_malloc(size_t nbytes, size_t align = 8)
{
    void *p = sbrk(0);
    p += round up but too hard to think on Friday
    sbrk(nbytes);
    num_allocations++;
    return p;
}

这样，如果您不提供对齐大小，它会做出与您所做的相同的安全假设，但您可以随时询问是否想要特别。

再说一次：我主要是在编造这个，我从来没有这样想过，但我知道如果我在内存受限的平台上工作，比如带 RAM 的 Arduino以 千字节 为单位，您必须考虑一下。

这个 malloc 的实现是一个 bump 分配器吗？

Is this implementation of malloc a bump allocator?

c

malloc

allocator