在C语言中，动态分配的内存是如何跟踪的？

Question

我们在C语言中使用malloc()动态分配内存，并收到指向堆中位置的指针。现在我们使用free()来释放内存，传递与其参数相同的指针值。

现在的问题是，free()如何知道要释放多少内存... 考虑到我们可以随时调整malloc()分配的内存块的大小。

这里是否与哈希表有关？

- ArunMKumar

Answer 1

一个典型的实现将在malloc返回的地址前存储信息。这些信息包括realloc或free需要了解的执行工作的信息，但具体存储的内容取决于实现方式。

- Vaughn Cato

Answer 2

原始技术是分配一个稍大的块并在开头存储大小，应用程序看不到其中的一部分。额外的空间保存大小和可能链接以线程自由块以便重用。

然而，这些技巧存在某些问题，例如缓存和内存管理行为不佳。在块中直接使用内存往往会不必要地将事物分页，并创建脏页，这会使共享和写时复制变得复杂。

因此，更高级的技术是保持单独的目录。还开发了一些奇特的方法，其中内存区域使用相同的2的幂大小。

总的来说，答案是：分配一个单独的数据结构来保持状态。

- DigitalRoss

---

在结尾处存储大小将是一种无望的低效策略。我认为http://en.wikipedia.org/wiki/Buddy_memory_allocation并不算“奇特”。 - Jim Balter

错误，呵呵，我想说的略有不同。已修复！ - DigitalRoss

我在Linux内核中看到过类似的技术，即使用“struct page”存储在分配的内存区域的开头，并使用该结构来保持内存状态的内核内存分配技术。 - ArunMKumar

Answer 3

在著名的K&R C圣经第186-188页中，最简单的实现方法如下：

我们实际得到的内存块比我们申请的要大（一个结构体头部或联合头部的大小）。该结构可能是这样的：

typedef long Align;

union header
{
    struct 
    {
        union header* ptr;  // next block
        unsigned size;      // size of this block , times of head size  
    }s;
    Align x;
};

下面是一个示意图：

当我们调用free函数时，可能会出现以下行为：

void free(void* ptr)
{
    Header *bp, *p;

    bp = (Header *)ptr - 1;

    /* .....                */
    /*return the memory to the linked list  */
}

在Visual Studio中，我们有两种模式：发布版本和调试版本，我们甚至可以使用头文件来存储调试信息以便于调试。在调试版本中的头文件称为_CrtMemBlockHeader，定义如下：

typedef struct _CrtMemBlockHeader
{
    struct _CrtMemBlockHeader * pBlockHeaderNext;
    struct _CrtMemBlockHeader * pBlockHeaderPrev;
    char *                      szFileName;
    int                         nLine;
    size_t                      nDataSize;
    int                         nBlockUse;
    long                        lRequest;
    unsigned char               gap[nNoMansLandSize];
} _CrtMemBlockHeader;

然后内存布局如下所示：

- prehistoricpenguin

---

非常感谢您提出这个问题。我有圣经，但完全错过了那个主题。您的描述非常清晰易懂。 - ArunMKumar

Answer 4

一种内存管理器使用表格来存储指针相关的附加数据，有时紧邻指针存储，有时存放在其他地方。由于 C 语言非常简单，所以最可能的数据类型为 int 或 long 类型，通常存储在 pointer-2 或 pointer-4 的位置。具体细节取决于编译器。

- Vesper

---

具体细节取决于语言实现的一部分C库。编译器与此无关。此外，一些实现将小尺寸块保留在内存池中，这些内存池由内存地址标识，因此对于这些块，大小不会被保留在任何地方。 - Jim Balter

哎呀，实际上大小是保存在某个地方的（而且必须）...它保存在描述内存池的数据结构中。 - Jim Balter

Answer 5

当我们使用malloc时，将会保留一个块，其大小将比我们请求的稍微大一些，并且作为对此malloc的回报，我们会得到指向该块开头的指针。正如我告诉您的那样，该块的大小将比您实际需要的要稍微大一些。这个额外的空间将用于保留块的实际请求大小、指向下一个空闲块的指针以及一些数据，这些数据检查“如果您试图访问超过分配块的内容”。因此，每当我们使用要释放的指针调用free时，该free将搜索在块空间中给定的额外信息，从而获得最终要释放的大小。

- Dayal rai