C++ malloc() 和 free() 如何工作？

How do malloc() and free() work?

提问by mahesh

I want to know how mallocand freework.

我想知道如何malloc和free工作。

int main() {
    unsigned char *p = (unsigned char*)malloc(4*sizeof(unsigned char));
    memset(p,0,4);
    strcpy((char*)p,"abcdabcd"); // **deliberately storing 8bytes**
    cout << p;
    free(p); // Obvious Crash, but I need how it works and why crash.
    cout << p;
    return 0;
}

I would be really grateful if the answer is in depth at memory level, if it's possible.

如果可能的话，如果答案在内存级别有深度，我将不胜感激。

回答by Juergen

OK some answers about malloc were already posted.

好的，已经发布了一些关于 malloc 的答案。

The more interesting part is how free works(and in this direction, malloc too can be understood better).

更有趣的部分是free是如何工作的（在这个方向上，malloc 也可以更好地理解）。

In many malloc/free implementations, free does normally not return the memory to the operating system (or at least only in rare cases). The reason is that you will get gaps in your heap and thus it can happen, that you just finish off your 2 or 4 GB of virtual memory with gaps. This should be avoided, since as soon as the virtual memory is finished, you will be in really big trouble. The other reason is, that the OS can only handle memory chunks that are of a specific size and alignment. To be specific: Normally the OS can only handle blocks that the virtual memory manager can handle (most often multiples of 512 bytes e.g. 4KB).

在许多 malloc/free 实现中，free 通常不会将内存返回给操作系统（或至少仅在极少数情况下）。原因是您的堆中会出现间隙，因此可能会发生这种情况，即您只是用间隙完成了 2 或 4 GB 的虚拟内存。这应该避免，因为一旦虚拟内存完成，你就会遇到很大的麻烦。另一个原因是，操作系统只能处理具有特定大小和对齐方式的内存块。具体来说：通常操作系统只能处理虚拟内存管理器可以处理的块（最常见的是 512 字节的倍数，例如 4KB）。

So returning 40 Bytes to the OS will just not work. So what does free do?

因此，将 40 字节返回给操作系统是行不通的。那么免费有什么作用呢？

Free will put the memory block in its own free block list. Normally it also tries to meld together adjacent blocks in the address space. The free block list is just a circular list of memory chunks which have some administrative data in the beginning. This is also the reason why managing very small memory elements with the standard malloc/free is not efficient. Every memory chunk needs additional data and with smaller sizes more fragmentation happens.

Free 会将内存块放入自己的空闲块列表中。通常它还会尝试将地址空间中的相邻块融合在一起。空闲块列表只是一个循环的内存块列表，在开始时有一些管理数据。这也是使用标准 malloc/free 管理非常小的内存元素效率不高的原因。每个内存块都需要额外的数据，并且尺寸越小，碎片就越多。

The free-list is also the first place that malloc looks at when a new chunk of memory is needed. It is scanned before it calls for new memory from the OS. When a chunk is found that is bigger than the needed memory, it is divided into two parts. One is returned to caller, the other is put back into the free list.

空闲列表也是 malloc 在需要新内存块时首先查看的位置。它在从操作系统调用新内存之前被扫描。当发现一个大于所需内存的块时，它被分成两部分。一个返回给调用者，另一个放回空闲列表。

There are many different optimizations to this standard behaviour (for example for small chunks of memory). But since malloc and free must be so universal, the standard behaviour is always the fallback when alternatives are not usable. There are also optimizations in handling the free-list — for example storing the chunks in lists sorted by sizes. But all optimizations also have their own limitations.

此标准行为有许多不同的优化（例如，对于小块内存）。但由于 malloc 和 free 必须如此通用，当替代品不可用时，标准行为总是后备。在处理空闲列表方面也有优化——例如将块存储在按大小排序的列表中。但是所有的优化也有其自身的局限性。

Why does your code crash:

为什么你的代码崩溃：

The reason is that by writing 9 chars (don't forget the trailing null byte) into an area sized for 4 chars, you will probably overwrite the administrative-data stored for another chunk of memory that resides "behind" your chunk of data (since this data is most often stored "in front" of the memory chunks). When free then tries to put your chunk into the free list, it can touch this administrative-data and therefore stumble over an overwritten pointer. This will crash the system.

原因是通过将 9 个字符（不要忘记尾随的空字节）写入一个大小为 4 个字符的区域，您可能会覆盖为另一个内存块存储的管理数据，该内存块位于您的数据块“后面”（因为此数据通常存储在内存块的“前面”）。当 free 尝试将您的块放入空闲列表时，它可以触及此管理数据并因此绊倒被覆盖的指针。这会使系统崩溃。

This is a rather graceful behaviour. I have also seen situations where a runaway pointer somewhere has overwritten data in the memory-free-list and the system did not immediately crash but some subroutines later. Even in a system of medium complexity such problems can be really, really hard to debug! In the one case I was involved, it took us (a larger group of developers) several days to find the reason of the crash -- since it was in a totally different location than the one indicated by the memory dump. It is like a time-bomb. You know, your next "free" or "malloc" will crash, but you don't know why!

这是一种相当优雅的行为。我还看到过某个地方的失控指针覆盖了内存空闲列表中的数据并且系统没有立即崩溃而是一些子程序稍后崩溃的情况。即使在中等复杂度的系统中，此类问题也可能非常非常难以调试！在我参与的一个案例中，我们（一大群开发人员）花了几天时间才找到崩溃的原因——因为它与内存转储所指示的位置完全不同。这就像一个定时炸弹。您知道，您的下一个“free”或“malloc”会崩溃，但您不知道为什么！

Those are some of the worst C/C++ problems, and one reason why pointers can be so problematic.

这些是一些最糟糕的 C/C++ 问题，也是指针问题如此严重的原因之一。

回答by joe

As aluser says in this forum thread:

正如 aluser 在此论坛主题中所说：

Your process has a region of memory, from address x to address y, called the heap. All your malloc'd data lives in this area. malloc() keeps some data structure, let's say a list, of all the free chunks of space in the heap. When you call malloc, it looks through the list for a chunk that's big enough for you, returns a pointer to it, and records the fact that it's not free any more as well as how big it is. When you call free() with the same pointer, free() looks up how big that chunk is and adds it back into the list of free chunks(). If you call malloc() and it can't find any large enough chunk in the heap, it uses the brk() syscall to grow the heap, i.e. increase address y and cause all the addresses between the old y and the new y to be valid memory. brk() must be a syscall; there is no way to do the same thing entirely from userspace.

您的进程有一个内存区域，从地址 x 到地址 y，称为堆。你所有的 malloc 数据都在这个区域。malloc() 保留一些数据结构，让我们说一个列表，堆中所有空闲空间块的列表。当您调用 malloc 时，它会在列表中查找对您来说足够大的块，返回一个指向它的指针，并记录它不再空闲的事实以及它有多大。当您使用相同的指针调用 free() 时，free() 会查找该块的大小并将其添加回空闲块的列表中（）。如果您调用 malloc() 并且在堆中找不到任何足够大的块，它会使用 brk() 系统调用来增大堆，即增加地址 y 并使旧 y 和新 y 之间的所有地址变为是有效的记忆。brk() 必须是系统调用；

malloc() is system/compiler dependent so it's hard to give a specific answer. Basically however it does keep track of what memory it's allocated and depending on how it does so your calls to free could fail or succeed.

malloc() 依赖于系统/编译器，因此很难给出具体答案。然而，基本上它确实会跟踪它分配的内存，并根据它的分配方式，您对 free 的调用可能会失败或成功。

malloc() and free() don't work the same way on every O/S.

malloc() and free() don't work the same way on every O/S.

回答by samoz

One implementation of malloc/free does the following:

malloc/free 的一种实现如下：

1. Get a block of memory from the OS through sbrk() (Unix call).
2. Create a header and a footer around that block of memory with some information such as size, permissions, and where the next and previous block are.
3. When a call to malloc comes in, a list is referenced which points to blocks of the appropriate size.
4. This block is then returned and headers and footers are updated accordingly.

1. 通过 sbrk()（Unix 调用）从操作系统获取一块内存。
2. 在该内存块周围创建页眉和页脚，其中包含一些信息，例如大小、权限以及下一个和上一个块的位置。
3. 当调用 malloc 时，会引用一个指向适当大小块的列表。
4. 然后返回该块并相应地更新页眉和页脚。

回答by DigitalRoss

Memory protection has page-granularity and would require kernel interaction

内存保护具有页面粒度，需要内核交互

Your example code essentially asks why the example program doesn't trap, and the answer is that memory protection is a kernel feature and applies only to entire pages, whereas the memory allocator is a library feature and it manages .. without enforcement .. arbitrary sized blocks which are often much smaller than pages.

您的示例代码本质上是问为什么示例程序没有陷阱，答案是内存保护是一个内核功能，仅适用于整个页面，而内存分配器是一个库功能，它管理 .. 无需强制执行 .. 任意大小的块通常比页面小得多。

Memory can only be removed from your program in units of pages, and even that is unlikely to be observed.

内存只能以页为单位从程序中删除，即使这样也不太可能被观察到。

calloc(3) and malloc(3) do interact with the kernel to get memory, if necessary. But most implementations of free(3) do not return memory to the kernel¹, they just add it to a free list that calloc() and malloc() will consult later in order to reuse the released blocks.

如有必要， calloc(3) 和 malloc(3) 确实与内核交互以获取内存。但是 free(3) 的大多数实现不会将内存返回给内核¹，它们只是将它添加到一个空闲列表中， calloc() 和 malloc() 稍后将参考该列表以重用已释放的块。

Even if a free() wanted to return memory to the system, it would need at least one contiguous memory page in order to get the kernel to actually protect the region, so releasing a small block would only lead to a protection change if it was the lastsmall block in a page.

即使 free() 想要将内存返回给系统，它也至少需要一个连续的内存页才能让内核真正保护该区域，因此释放一个小块只会导致保护更改，如果它是页面中的最后一个小块。

So your block is there, sitting on the free list. You can almost always access it and nearby memory just as if it were still allocated. C compiles straight to machine code and without special debugging arrangements there are no sanity checks on loads and stores. Now, if you try and access a free block, the behavior is undefined by the standard in order to not make unreasonable demands on library implementators. If you try and access freed memory or meory outside an allocated block, there are various things that can go wrong:

所以你的块就在那里，坐在空闲列表上。你几乎总是可以访问它和附近的内存，就像它仍然被分配一样。C 直接编译为机器代码，没有特殊的调试安排，没有对加载和存储的健全性检查。现在，如果您尝试访问一个空闲块，则标准未定义该行为，以免对库实现者提出不合理的要求。如果您尝试访问已分配块之外的已释放内存或内存，则可能会出现各种问题：

• Sometimes allocators maintain separate blocks of memory, sometimes they use a header they allocate just before or after (a "footer", I guess) your block, but they just might want to use memory within the block for the purpose of keeping the free list linked together. If so, your reading the block is OK, but its contents may change, and writing to the block would be likely to cause the allocator to misbehave or crash.
• Naturally, your block may be allocated in the future, and then it is likely to be overwritten by your code or a library routine, or with zeroes by calloc().
• If the block is reallocated, it may also have its size changed, in which case yet more links or initialization will be written in various places.
• Obviously you may reference so far out of range that you cross a boundary of one of your program's kernel-known segments, and in this one case you will trap.

• 有时分配器维护单独的内存块，有时他们使用他们在块之前或之后分配的标头（我猜是“页脚”），但他们可能只想使用块内的内存来保持空闲列表联系在一起。如果是这样，您读取该块是可以的，但其内容可能会发生变化，并且写入该块可能会导致分配器行为异常或崩溃。
• 自然，您的块可能会在将来分配，然后它很可能会被您的代码或库例程覆盖，或者被 calloc() 覆盖为零。
• 如果块被重新分配，它的大小也可能改变，在这种情况下，更多的链接或初始化将被写入不同的地方。
• 显然，您的引用可能超出范围，以至于跨越了程序的内核已知段之一的边界，在这种情况下，您将陷入困境。

Theory of Operation

操作理论

So, working backwards from your example to the overall theory, malloc(3) gets memory from the kernel when it needs it, and typically in units of pages. These pages are divided or consolidated as the program requires. Malloc and free cooperate to maintain a directory. They coalesce adjacent free blocks when possible in order to be able to provide large blocks. The directory may or may not involve using the memory in freed blocks to form a linked list. (The alternative is a bit more shared-memory and paging-friendly, and it involves allocating memory specifically for the directory.) Malloc and free have little if any ability to enforce access to individual blocks even when special and optional debugging code is compiled into the program.

因此，从您的示例到整体理论，malloc(3) 在需要时从内核获取内存，通常以页为单位。这些页面根据程序的需要进行划分或合并。malloc 和 free 合作维护一个目录。它们在可能的情况下合并相邻的空闲块，以便能够提供大块。目录可能会或可能不会涉及使用释放块中的内存来形成链表。（另一种方法是更共享内存和分页友好，它涉及专门为目录分配内存。）即使特殊和可选的调试代码被编译成，Malloc 和 free 也几乎没有强制访问单个块的能力该程序。

---

---

^{1. The fact that very few implementations of free() attempt to return memory to the system is not necessarily due to the implementors slacking off. Interacting with the kernel is much slower than simply executing library code, and the benefit would be small. Most programs have a steady-state or increasing memory footprint, so the time spent analyzing the heap looking for returnable memory would be completely wasted. Other reasons include the fact that internal fragmentation makes page-aligned blocks unlikely to exist, and it's likely that returning a block would fragment blocks to either side. Finally, the few programs that do return large amounts of memory are likely to bypass malloc() and simply allocate and free pages anyway.}

^{1. free() 的实现很少尝试将内存返回给系统的事实并不一定是由于实现者的懈怠。与内核交互比简单地执行库代码要慢得多，而且收益很小。大多数程序都有一个稳定状态或不断增加的内存占用，因此分析堆寻找可返回内存所花费的时间将完全浪费掉。其他原因包括内部碎片使得页面对齐的块不太可能存在这一事实，并且很可能返回块会将块碎片化到任一侧。最后，确实返回大量内存的少数程序可能会绕过 malloc() 并简单地分配和释放页面。}

回答by Chris Arguin

In theory, malloc gets memory from the operating system for this application. However, since you may only want 4 bytes, and the OS needs to work in pages (often 4k), malloc does a little more than that. It takes a page, and puts it's own information in there so it can keep track of what you have allocated and freed from that page.

理论上，malloc 会为此应用程序从操作系统获取内存。但是，由于您可能只需要 4 个字节，并且操作系统需要在页中工作（通常为 4k），因此 malloc 的作用不止于此。它需要一个页面，并将它自己的信息放在那里，以便它可以跟踪您从该页面分配和释放的内容。

When you allocate 4 bytes, for instance, malloc gives you a pointer to 4 bytes. What you may not realize is that the memory 8-12 bytes beforeyour 4 bytes is being used by malloc to make a chain of all the memory you have allocated. When you call free, it takes your pointer, backs up to where it's data is, and operates on that.

例如，当您分配 4 个字节时，malloc 会为您提供一个指向 4 个字节的指针。您可能没有意识到malloc 正在使用 4 个字节之前的8-12 个字节的内存来制作您分配的所有内存的链。当您调用 free 时，它​​会获取您的指针，备份到数据所在的位置，然后对其进行操作。

When you free memory, malloc takes that memory block off the chain... and may or may not return that memory to the operating system. If it does, than accessing that memory will probably fail, as the OS will take away your permissions to access that location. If malloc keeps the memory ( because it has other things allocated in that page, or for some optimization ), then the access will happen to work. It's still wrong, but it might work.

当您释放内存时，malloc 会将该内存块从链中取出……并且可能会也可能不会将该内存返回给操作系统。如果是这样，那么访问该内存可能会失败，因为操作系统将剥夺您访问该位置的权限。如果 malloc 保留内存（因为它在该页面中分配了其他东西，或者进行了一些优化），那么访问就会发生。它仍然是错误的，但它可能会起作用。

DISCLAIMER: What I described is a common implementation of malloc, but by no means the only possible one.

免责声明：我所描述的是 malloc 的一种常见实现，但绝不是唯一可能的实现。

回答by Steve Jessop

Your strcpy line attempts to store 9 bytes, not 8, because of the NUL terminator. It invokes undefined behaviour.

由于 NUL 终止符，您的 strcpy 行尝试存储 9 个字节，而不是 8 个。它调用未定义的行为。

The call to free may or may not crash. The memory "after" the 4 bytes of your allocation might be used for something else by your C or C++ implementation. If it is used for something else, then scribbling all over it will cause that "something else" to go wrong, but if it isn't used for anything else, then you could happen to get away with it. "Getting away with it" might sound good, but is actually bad, since it means your code will appear to run OK, but on a future run you might not get away with it.

对 free 的调用可能会也可能不会崩溃。分配的 4 个字节“之后”的内存可能会被 C 或 C++ 实现用于其他用途。如果它用于其他用途，那么在其上乱涂乱画会导致“其他用途”出错，但如果它不用于其他用途，那么您可能会侥幸逃脱。“摆脱它”可能听起来不错，但实际上很糟糕，因为这意味着您的代码看起来可以正常运行，但在将来的运行中您可能无法摆脱它。

With a debugging-style memory allocator, you might find that a special guard value has been written there, and that free checks for that value and panics if it doesn't find it.

使用调试风格的内存分配器，您可能会发现那里已经写入了一个特殊的保护值，并且免费检查该值，如果没有找到它就会发生恐慌。

Otherwise, you might find that the next 5 bytes includes part of a link node belonging to some other block of memory which hasn't been allocated yet. Freeing your block could well involved adding it to a list of available blocks, and because you've scribbled in the list node, that operation could dereference a pointer with an invalid value, causing a crash.

否则，您可能会发现接下来的 5 个字节包含属于尚未分配的某个其他内存块的链接节点的一部分。释放您的块很可能涉及将其添加到可用块列表中，并且由于您在列表节点中进行了涂鸦，该操作可能会取消引用具有无效值的指针，从而导致崩溃。

It all depends on the memory allocator - different implementations use different mechanisms.

这一切都取决于内存分配器——不同的实现使用不同的机制。

回答by Martin Liversage

How malloc() and free() works depends on the runtime library used. Generally, malloc() allocates a heap (a block of memory) from the operating system. Each request to malloc() then allocates a small chunk of this memory be returning a pointer to the caller. The memory allocation routines will have to store some extra information about the block of memory allocated to be able to keep track of used and free memory on the heap. This information is often stored in a few bytes just before the pointer returned by malloc() and it can be a linked list of memory blocks.

malloc() 和 free() 的工作方式取决于使用的运行时库。通常，malloc() 从操作系统分配一个堆（一块内存）。每个对 malloc() 的请求然后分配一小块内存并返回一个指向调用者的指针。内存分配例程必须存储一些关于分配的内存块的额外信息，以便能够跟踪堆上已用和空闲内存。此信息通常存储在 malloc() 返回的指针之前的几个字节中，它可以是内存块的链表。

By writing past the block of memory allocated by malloc() you will most likely destroy some of the book-keeping information of the next block which may be the remaining unused block of memory.

通过写入由 malloc() 分配的内存块，您很可能会破坏下一个块的一些簿记信息，这些信息可能是剩余的未使用的内存块。

One place where you program may also crash is when copying too many characters into the buffer. If the extra characters are located outside the heap you may get an access violation as you are trying to write to non-existing memory.

您的程序也可能崩溃的一个地方是将太多字符复制到缓冲区中。如果额外的字符位于堆外，您可能会在尝试写入不存在的内存时遇到访问冲突。

回答by Martin Liversage

This has nothing specifically to do with malloc and free. Your program exhibits undefined behaviour after you copy the string - it could crash at that point or at any point afterwards. This would be true even if you never used malloc and free, and allocated the char array on the stack or statically.

这与 malloc 和 free 没有特别的关系。您的程序在复制字符串后表现出未定义的行为 - 它可能在那时或之后的任何时候崩溃。即使您从未使用过 malloc 和 free，并且在堆栈上或静态地分配了 char 数组，这也是正确的。

回答by plinth

malloc and free are implementation dependent. A typical implementation involves partitioning available memory into a "free list" - a linked list of available memory blocks. Many implementations artificially divide it into small vs large objects. Free blocks start with information about how big the memory block is and where the next one is, etc.

malloc 和 free 依赖于实现。一个典型的实现包括将可用内存划分为一个“空闲列表”——一个可用内存块的链表。许多实现人为地将其分为小对象和大对象。空闲块以有关内存块有多大以及下一个内存块在哪里等信息开始。

When you malloc, a block is pulled from the free list. When you free, the block is put back in the free list. Chances are, when you overwrite the end of your pointer, you are writing on the header of a block in the free list. When you free your memory, free() tries to look at the next block and probably ends up hitting a pointer that causes a bus error.

当您 malloc 时，会从空闲列表中拉出一个块。当您释放时，该块将放回空闲列表中。很有可能，当您覆盖指针的末尾时，您正在写入空闲列表中块的标题。当您释放内存时，free() 会尝试查看下一个块，但最终可能会遇到导致总线错误的指针。

回答by Goz

Well it depends on the memory allocator implementation and the OS.

这取决于内存分配器的实现和操作系统。

Under windows for example a process can ask for a page or more of RAM. The OS then assigns those pages to the process. This is not, however, memory allocated to your application. The CRT memory allocator will mark the memory as a contiguous "available" block. The CRT memory allocator will then run through the list of free blocks and find the smallest possible block that it can use. It will then take as much of that block as it needs and add it to an "allocated" list. Attached to the head of the actual memory allocation will be a header. This header will contain various bit of information (it could, for example, contain the next and previous allocated blocks to form a linked list. It will most probably contain the size of the allocation).

例如，在 Windows 下，一个进程可以请求一页或更多的 RAM。然后操作系统将这些页面分配给进程。但是，这不是分配给您的应用程序的内存。CRT 内存分配器会将内存标记为连续的“可用”块。然后 CRT 内存分配器将遍历空闲块列表并找到它可以使用的最小块。然后它将根据需要占用该块并将其添加到“已分配”列表中。附加到实际内存分配的头部将是一个头部。这个头将包含各种信息（例如，它可以包含下一个和上一个分配的块以形成一个链表。它很可能包含分配的大小）。

Free will then remove the header and add it back to the free memory list. If it forms a larger block with the surrounding free blocks these will be added together to give a larger block. If a whole page is now free the allocator will, most likely, return the page to the OS.

Free 然后将删除标头并将其添加回空闲内存列表。如果它与周围的空闲块形成一个更大的块，这些块将被加在一起得到一个更大的块。如果整个页面现在空闲，分配器很可能会将页面返回给操作系统。

It is not a simple problem. The OS allocator portion is completely out of your control. I recommend you read through something like Doug Lea's Malloc (DLMalloc) to get an understanding of how a fairly fast allocator will work.

这不是一个简单的问题。操作系统分配器部分完全不受您的控制。我建议您通读 Doug Lea 的 Malloc (DLMalloc) 之类的内容，以了解相当快的分配器将如何工作。

Edit: Your crash will be caused by the fact that by writing larger than the allocation you have overwritten the next memory header. This way when it frees it gets very confused as to what exactly it is free'ing and how to merge into the following block. This may not always cause a crash straight away on the free. It may cause a crash later on. In general avoid memory overwrites!

编辑：您的崩溃将是由于写入大于分配而覆盖下一个内存标头的事实造成的。这样，当它释放时，它会非常困惑它究竟释放了什么以及如何合并到下一个块中。这可能并不总是立即导致免费崩溃。以后可能会导致崩溃。一般避免内存覆盖！