动态内存分配指针标识

Question

所以我有一个任务要在C语言中实现自己的malloc和free。问题是memory_free(void *ptr)函数的要求之一。如果指针无效，即它没有被memory_alloc(unsigned int size)分配，则必须返回1，否则返回0。我无法想出一种方法来做到这一点，而不会非常耗时。

我的内存结构如下：我有一个全局指针指向我要用作堆的数组的开头。每个内存块都有一个int头来告诉它的大小和是否空闲。

这是我当前的memory_free(void *ptr)函数，TYPE是typedef unsigned int:

int memory_free(void *ptr)
{
    void *head = ptr;
    if (head == NULL)
        return 1;
    head -= sizeof(TYPE);
    if (!((*(TYPE*) head) & 1 ))
        return 1;
    (*(TYPE*) head) &= ~0x1;
    return 0;
}

指针ptr指向用户块的第一个字节，这意味着如果我想读取头部，我必须返回4个字节。检查指针有效性的一种解决方案是从开头遍历堆并查看是否找到了相关的头部，但这不够高效。请问有更好的方法吗？

- Slaaavo

---

这段代码到底哪里效率低下了？在我看来它看起来相当高效。主要问题是代码看起来完全不安全。我不会实现一个动态内存分配算法，而没有一种查找表来跟踪实际存在的内存块。如果指针指向随机垃圾怎么办？如果用户错误地两次调用memory_free同一个对象怎么办？ - Lundin

这正是我的问题。每当调用memory_free时，我都必须针对它进行测试。这就是我的问题 :). 只是为了明确，我基本上现在没有检查它，因为那里的条件有一半的成功率。 - Slaaavo

如果是这样，你希望有人如何回答而不提供关于如何分配和跟踪内存的信息呢？ - Lundin

恐怕任何有效的解决方案都需要浪费一些内存（在每个块的头部保留一些状态信息）和时间（验证头部与分配器其余数据的一致性），或者浪费大量内存（例如，所有已分配块的单独列表或哈希表）。 - CiaPan

在释放指针时需要进行验证的要求确实会使实现变得复杂，这就是为什么在这种情况下free会导致未定义行为而不是抱怨指针的好原因。 - Blagovest Buyukliev

Answer 1

一个O(1)的解决方案是将头部从四个字节扩展到八个字节；使用额外的四个字节来表示有效性。例如，它可以是存储在其他四个字节中的补码。因此，您查看头部，如果这些额外的字节包含除头部第一部分的补码之外的任何内容，则知道它不是有效块。

- Ernest Friedman-Hill

---

这种方法似乎有一个缺陷：想象一下调用 ptr = memory_alloc(64)，然后用户代码写入该区域，然后调用 memory_free(ptr + 32)。这样分配器就会被“欺骗”，认为另外一种情况。 - Blagovest Buyukliev

当然可以。大多数malloc都可以很容易地通过这种方式“欺骗”。 - Ernest Friedman-Hill

free 不必检查其参数的有效性；传递一个不是由 (m|c|re)alloc 返回的指针是未定义的行为。 - Blagovest Buyukliev

这是一种O(1)的方法，但是浪费了大量的内存空间。我的malloc必须能够容纳至少100字节的内存，并且每个块额外的4字节非常巨大。不过还是谢谢你，好主意。 - Slaaavo

@Slaaavo：如果您对簿记的大小如此敏感，那么您应该考虑使用位向量，其位指示特定范围内的插槽是空闲还是占用。请记住，这仅适用于给定范围内固定大小的对象。我已经在我的slab分配器中实现了这样的“bitslots”：https://github.com/bbu/userland-slab-allocator - Blagovest Buyukliev

你遇到了一个问题，即malloc的结果必须正确对齐以适用于任何目的。通常，malloc具有16字节对齐，以容纳在malloc块中存储向量，因此你实际上被迫添加16字节。当然，除非你编写自己的malloc，例如为所有malloc分配一个大块，直到16字节，为所有malloc分配另一个大块，直到32字节等。 - gnasher729

Answer 2

我看到有两种可能的选择：

• 保持指针链表，您已经分配：由memory_alloc填充并由memory_free消耗。这样，您可以双重检查传递给memory_free的内容是否一致。
• 链接列表可能很耗时：作为折衷方案，您只需存储内存池开头和结尾的地址，并确保传递给memory_free的指针在正确的范围内。 这远不如精确和确定，但速度更快。

- n0p

---

问题在于，在分配器中使用链表时，仍然需要分配每个节点。我建议使用块的链表，其中每个块包含一些常量数量的指针。 - Blagovest Buyukliev

他似乎已经在问题中排除了O(N)的解决方案，认为它们太低效了--他不想扫描列表。 - Ernest Friedman-Hill

还有跳表，它的时间复杂度为O(log N)。另外，正如我之前所说，位向量可以将查找速度提高数倍。 - Blagovest Buyukliev

确切地说，我的老师告诉我有更好的解决方案。我不知道这个解决方案是否适用于我当前的内存管理。 - Slaaavo