首页 > 代码库 > malloc实现原理
malloc实现原理
记得早一段时间，看到一本书上写过delete的一个。。今天突然找啦一下资料：
malloc（）是C语言中动态存储管理的一组标准库函数之中的一个。其作用是在内存的动态存储区中分配一个长度为size的连续空间。其參数是一个无符号整形数，返回值是一个指向所分配的连续存储域的起始地址的指针。
动态内存分配就是指在程序运行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不像数组等静态内存分配方法那样须要预先分配存储空间，而是由系统依据程序的须要即时分配，且分配的大小就是程序要求的大小。本文简介动态内存分配函数malloc（）及几种实现方法。
1． 简单介绍
malloc（）是C语言中动态存储管理的一组标准库函数之中的一个。其作用是在内存的动态存储区中分配一个长度为size的连续空间。其參数是一个无符号整形数，返回值是一个指向所分配的连续存储域的起始地址的指针。另一点必须注意的是，当函数未能成功分配存储空间（如内存不足）就会返回一个NULL指针。所以在调用该函数时应该检測返回值是否为NULL并运行对应的操作。
2． 函数说明
C语言的动态存储管理由一组标准库函数实现，其原型在标准文件<stdlib.h>里描写叙述，须要用这些功能时应包括这个文件。与动态存储分配有关的函数共同拥有四个，当中就包含存储分配函数malloc（）。函数原型是：void *malloc (size_t n);这里的size_t是标准库里定义的一个类型，它是一个无符号整型。这个整型可以满足全部对存储块大小描写叙述的须要，详细相当于哪个整型由详细的C系统确定。malloc的返回值为(void *)类型（这是通用指针的一个重要用途），它分配一片能存放大小为n的数据的存储块，返回相应的指针值；假设不能满足申请（找不到能满足要求的存储块）就返回NULL。在使用时，应该把malloc的返回值转换到特定指针类型，赋给一个指针。
注意，尽管这里的存储块是通过动态分配得到的，但是它的大小也是确定的，相同不同意越界使用。比如上面程序段分配的块里能存n个双精度数据，随后的使用就必须在这个范围内进行。越界使用动态分配的存储块，尤其是越界赋值，可能引起很严重的后果，一般会破坏程序的执行系统，可能造成本程序或者整个计算机系统垮台。
下例是一个动态分配的样例：
#include <stdlib.h>
main()
{
int count,*array; /*count是一个计数器，array是一个整型指针，也能够理解为指向一个整型数组的首地址*/
if((array(int *) malloc (10*sizeof(int)))==NULL)
{
printf("不能成功分配存储空间。");
exit(1);
}
for (count=0;count〈10;count++) /*给数组赋值*/
array[count]=count;
for(count=0;count〈10;count++) /*打印数组元素*/
printf("%2d",array[count]);
}
上例中动态分配了10个整型存储区域，然后进行赋值并打印。例中if((array(int *) malloc (10*sizeof(int)))==NULL)语句能够分为下面几步：
1）分配10个整型的连续存储空间，并返回一个指向其起始地址的整型指针
2）把此整型指针地址赋给array
3）检測返回值是否为NULL
3． malloc（）工作机制
malloc函数的实质体如今，它有一个将可用的内存块连接为一个长长的列表的所谓空暇链表。调用malloc函数时，它沿连接表寻找一个大到足以满足用户请求所须要的内存块。然后，将该内存块一分为二（一块的大小与用户请求的大小相等，还有一块的大小就是剩下的字节）。接下来，将分配给用户的那块内存传给用户，并将剩下的那块（假设有的话）返回到连接表上。调用free函数时，它将用户释放的内存块连接到空暇链上。到最后，空暇链会被切成非常多的小内存片段，假设这时用户申请一个大的内存片段，那么空暇链上可能没有能够满足用户要求的片段了。于是，malloc函数请求延时，并開始在空暇链上翻箱倒柜地检查各内存片段，对它们进行整理，将相邻的小空暇块合并成较大的内存块。
4． malloc（）在操作系统中的实现
在 C 程序中，多次使用malloc () 和 free()。只是，您可能没实用一些时间去思考它们在您的操作系统中是怎样实现的。本节将向您展示 malloc 和 free 的一个最简化实现的代码，来帮助说明管理内存时都涉及到了哪些事情。
在大部分操作系统中，内存分配由下面两个简单的函数来处理：
void *malloc (long numbytes)：该函数负责分配 numbytes 大小的内存，并返回指向第一个字节的指针。
void free(void *firstbyte)：假设给定一个由先前的 malloc 返回的指针，那么该函数会将分配的空间归还给进程的“空暇空间”。
malloc_init 将是初始化内存分配程序的函数。它要完毕下面三件事：将分配程序标识为已经初始化，找到系统中最后一个有效内存地址，然后建立起指向我们管理的内存的指针。这三个变量都是全局变量：
清单 1. 我们的简单分配程序的全局变量
int has_initialized = 0;
void *managed_memory_start;
void *last_valid_address;
如前所述，被映射的内存的边界（最后一个有效地址）常被称为系统中断点或者 当前中断点。在非常多 UNIX? 系统中，为了指出当前系统中断点，必须使用 sbrk(0) 函数。 sbrk 依据參数中给出的字节数移动当前系统中断点，然后返回新的系统中断点。使用參数 0 仅仅是返回当前中断点。这里是我们的 malloc 初始化代码，它将找到当前中断点并初始化我们的变量：
清单 2. 分配程序初始化函数
/* Include the sbrk function */
#include
void malloc_init()
{
/* grab the last valid address from the OS */
last_valid_address = sbrk(0);
/* we don‘t have any memory to manage yet, so
*just set the beginning to be last_valid_address
*/
managed_memory_start = last_valid_address;
/* Okay, we‘re initialized and ready to go */
has_initialized = 1;
}
如今，为了全然地管理内存，我们须要可以追踪要分配和回收哪些内存。在对内存块进行了 free 调用之后，我们须要做的是诸如将它们标记为未被使用的等事情，而且，在调用 malloc 时，我们要可以定位未被使用的内存块。因此， malloc 返回的每块内存的起始处首先要有这个结构：
清单 3. 内存控制块结构定义
struct mem_control_block {
int is_available;
int size;
};
如今，您可能会觉得当程序调用 malloc 时这会引发问题 —— 它们怎样知道这个结构？答案是它们不必知道；在返回指针之前，我们会将其移动到这个结构之后，把它隐藏起来。这使得返回的指针指向没实用于不论什么其它用途的内存。那样，从调用程序的角度来看，它们所得到的所有是空暇的、开放的内存。然后，当通过 free() 将该指针传递回来时，我们仅仅须要倒退几个内存字节就能够再次找到这个结构。
在讨论分配内存之前，我们将先讨论释放，由于它更简单。为了释放内存，我们必需要做的惟一一件事情就是，获得我们给出的指针，回退 sizeof(struct mem_control_block) 个字节，并将其标记为可用的。这里是相应的代码：
清单 4. 解除分配函数
void free(void *firstbyte) {
struct mem_control_block *mcb;
/* Backup from the given pointer to find the
* mem_control_block
*/
mcb = firstbyte - sizeof(struct mem_control_block);
/* Mark the block as being available */
mcb->is_available = 1;
/* That‘s It! We‘re done. */
return;
}
如您所见，在这个分配程序中，内存的释放使用了一个很easy的机制，在固定时间内完毕内存释放。分配内存略微困难一些。下面是该算法的略述：
清单 5. 主分配程序的伪代码
1. If our allocator has not been initialized, initialize it.
2. Add sizeof(struct mem_control_block) to the size requested.
3. start at managed_memory_start.
4. Are we at last_valid address?
5. If we are:
A. We didn‘t find any existing space that was large enough
-- ask the operating system for more and return that.
6. Otherwise:
A. Is the current space available (check is_available from
the mem_control_block)?
B. If it is:
i) Is it large enough (check "size" from the
mem_control_block)?
ii) If so:
a. Mark it as unavailable
b. Move past mem_control_block and return the
pointer
iii) Otherwise:
a. Move forward "size" bytes
b. Go back go step 4
C. Otherwise:
i) Move forward "size" bytes
ii) Go back to step 4
我们主要使用连接的指针遍历内存来寻找开放的内存块。这里是代码：
清单 6. 主分配程序
void *malloc(long numbytes) {
/* Holds where we are looking in memory */
void *current_location;
/* This is the same as current_location, but cast to a
* memory_control_block
*/
struct mem_control_block *current_location_mcb;
/* This is the memory location we will return. It will
* be set to 0 until we find something suitable
*/
void *memory_location;
/* Initialize if we haven‘t already done so */
if(! has_initialized) {
malloc_init();
}
/* The memory we search for has to include the memory
* control block, but the users of malloc don‘t need
* to know this, so we‘ll just add it in for them.
*/
numbytes = numbytes + sizeof(struct mem_control_block);
/* Set memory_location to 0 until we find a suitable
* location
*/
memory_location = 0;
/* Begin searching at the start of managed memory */
current_location = managed_memory_start;
/* Keep going until we have searched all allocated space */
while(current_location != last_valid_address)
{
/* current_location and current_location_mcb point
* to the same address. However, current_location_mcb
* is of the correct type, so we can use it as a struct.
* current_location is a void pointer so we can use it
* to calculate addresses.
*/
current_location_mcb =
(struct mem_control_block *)current_location;
if(current_location_mcb->is_available)
{
if(current_location_mcb->size >= numbytes)
{
/* Woohoo! We‘ve found an open,
* appropriately-size location.
*/
/* It is no longer available */
current_location_mcb->is_available = 0;
/* We own it */
memory_location = current_location;
/* Leave the loop */
break;
}
}
/* If we made it here, it‘s because the Current memory
* block not suitable; move to the next one
*/
current_location = current_location +
current_location_mcb->size;
}
/* If we still don‘t have a valid location, we‘ll
* have to ask the operating system for more memory
*/
if(! memory_location)
{
/* Move the program break numbytes further */
sbrk(numbytes);
/* The new memory will be where the last valid
* address left off
*/
memory_location = last_valid_address;
/* We‘ll move the last valid address forward
* numbytes
*/
last_valid_address = last_valid_address + numbytes;
/* We need to initialize the mem_control_block */
current_location_mcb = memory_location;
current_location_mcb->is_available = 0;
current_location_mcb->size = numbytes;
}
/* Now, no matter what (well, except for error conditions),
* memory_location has the address of the memory, including
* the mem_control_block
*/
/* Move the pointer past the mem_control_block */
memory_location = memory_location + sizeof(struct mem_control_block);
/* Return the pointer */
return memory_location;
}
这就是我们的内存管理器。如今，我们仅仅须要构建它，并在程序中使用它就可以。
5． malloc（）的其它实现
malloc() 的实现有非常多，这些实现各有长处与缺点。在设计一个分配程序时，要面临很多须要折衷的选择，当中包含：
分配的速度。
回收的速度。
有线程的环境的行为。
内存将要被用光时的行为。
局部缓存。
簿记（Bookkeeping）内存开销。
虚拟内存环境中的行为。
小的或者大的对象。
实时保证。
每个实现都有其自身的优缺点集合。在我们的简单的分配程序中，分配很慢，而回收很快。另外，因为它在使用虚拟内存系统方面较差，所以它最适于处理大的对象。
还有其它很多分配程序能够使用。当中包含：
Doug Lea Malloc：Doug Lea Malloc 实际上是完整的一组分配程序，当中包含 Doug Lea 的原始分配程序，GNU libc 分配程序和 ptmalloc。 Doug Lea 的分配程序有着与我们的版本号很相似的基本结构，可是它增加了索引，这使得搜索速度更快，而且能够将多个没有被使用的块组合为一个大的块。它还支持缓存，以便更快地再次使用近期释放的内存。 ptmalloc 是 Doug Lea Malloc 的一个扩展版本号，支持多线程。在本文后面的 參考资料部分中，有一篇描写叙述 Doug Lea 的 Malloc 实现的文章。
BSD Malloc：BSD Malloc 是随 4.2 BSD 发行的实现，包括在 FreeBSD 之中，这个分配程序能够从预先确实大小的对象构成的池中分配对象。它有一些用于对象大小的 size 类，这些对象的大小为 2 的若干次幂减去某一常数。所以，假设您请求给定大小的一个对象，它就简单地分配一个与之匹配的 size 类。这样就提供了一个高速的实现，可是可能会浪费内存。在 參考资料部分中，有一篇描写叙述该实现的文章。
Hoard：编写 Hoard 的目标是使内存分配在多线程环境中进行得非常快。因此，它的构造以锁的使用为中心，从而使全部进程不必等待分配内存。它能够显著地加快那些进行非常多分配和回收的多线程进程的速度。在 參考资料部分中，有一篇描写叙述该实现的文章。
众多可用的分配程序中最有名的就是上述这些分配程序。假设您的程序有特别的分配需求，那么您可能更愿意编写一个定制的能匹配您的程序内存分配方式的分配程序。只是，假设不熟悉分配程序的设计，那么定制分配程序一般会带来比它们解决的问题很多其它的问题。
附：：
C++中内存的动态分配与管理永远是一个让C++开发人员头痛的问题，本文通过对C++中内存的动态分配释放的基本原理的介绍，让读者朋友能对C++中的内存的动态分配与释放有较为深入的理解，从而更好驾驭C++程序。
1. 函数(Function)
(1) operator new function
1 | void |
上面是C++中operator new function的原型，一个是全局类型的，一个的类成员类型的。全局类型的operator new函数在以下两种情况下被调用：一种是在分配C++内建（built-in）类型的动态内存时，一种是在分配用户没有自定义operator new成员函数的用户自定义类型的动态内存时。 假设用户在自定义的类型中，定义了operator new函数，那么用户在用new申请该类型的动态内存时, 便会调用该类型的成员函数operator new, 而不是全局的operator new。
另外，我们注意到，上面的原型中函数的返回值为void *类型, 第一个參数为size_t类型，这个是C++编译器要求的，假设要自己重载operator new函数，返回值必须为void* 类型，第一个參数必须为size_t类型，否则，编译器会返回例如以下错误信息：
1 | error: ‘operator new’ takes type ‘size_t’ (‘unsigned int’) as first parameter |
这里须要注意的一点是，我们能够利用operator new function能够重载的特点，能够通过參数传入一些额外的信息，来调试程序，检測内存泄露等。比方，我们能够像以下这样重载，传入调用处的行号，函数名，这样就能够跟踪内存的分配使用情况：
1 | void |
(2) operator delete function
1 | void |
上面是operator delete function的原型。operator delete function也有全局的和类成员的两种。这里须要注意，一个类仅仅能有一个operator delete function做为其成员函数，并且必须为上面两种中的当中一种，没有其他的形式。假设一个类实现了自己的operator delete function成员函数，那么在释放该类型的内存时，编译器便会调用成员operator delete function, 而不是全局的。
上面的两种原型，第一种，在调用的时候，编译器会把要释放的内存的首地址传入，另外一种，在调用的时候，编译器会把要释放的内存的首地址和大小都传入。因此，能够利用这一特性，假设我们在基类中实现另外一种形式的operator delete function的成员函数，那么便能够用之来释放子类类型的内存（详细參考最后面的样例）。
2. 运算符(Operator)
(1) new operator
1 | [ |
注：上面的’[]‘表示在当中的部分是optional（可选的）
上面是new operator的原型。在C++中，动态内存的分配,通常都是调用new operator来完毕的，利用new operator来分配动态内存，编译器要做以下两项工作：
- a. 调用operator new function分配内存（allocate the memory）
- b. 调用构造函数（call the constructor）来进行初始化
以下来说一说new operator的原型中各部分究竟是干什么的：
placement: 假设你重载了operator new function, placement能够用来传递额外的參数
type-name: 指定要分配的内存的类型，能够是内建(built-in)类型，也能够是用户自己定义类型
new-initializer: 指定对分配后内存的初始化的參数，也就的构造函数的參数 。这里须要注意一点，在分配一个对象的数组类型的内存时，不可以指定初始化參数；换言之，要想分配一个对象的数组类型的内存，该对象必须有缺省构造函数
(2) delete opeartor
1 | [ |
上面是delete operator的原型，第一种用来释放普通的对象(包含内建类型）类型的内存，另外一种用来释放对象的数组类型的内存。在C++中，用new operator分配的动态内存，必须调用delete operator来释放，通经常使用delete operator释放内存编译器要做以下两项工作：
- a. 调用对象析构函数来析构对象
- b. 调用operator delete function来释放内存(deallocate the memory)
3. 关于new/delete使用过程中一些须要注意的点
(1)怎样差别operator new/delete function 与 new/delete operator ?
通过上面的讲述，不难看出，我们分配/释放动态内存，调用的是new/delete operator, 而在调用new/delete的过程中，编译器会自己主动调用operator new/delete function来完毕实际的内存分配/释放的工作
(2) 用delete operator去释放一块不是由new operator释放的内存，结果是不可预料的，因此，切记，operator new与operator delete一定要配对使用，这是写好程序的基础
(3) new operator调用失败会抛出std::bad_alloc异常，前提是你没有自己重载相应的operator new function；delete operator失败，常见的原因是多次delete同一块内存
(4) 假设一块内存被delete后，再对它解引用(Dereference)，结果也是不可预測的，非常可能导致程序崩溃
(5) delete一个空(NULL)指针是安全的，没有不论什么害处的
(6) 类成员类型的operator new/delete函数必须为静态(static)函数，因此它们不能为虚函数(virtual function)，也遵守public, protected, private的訪问权限控制
4. 关于上面所讲的内容的一些样例：
程序：
1 | #include <stdio .h> |
执行结果：
1 | wuzesheng@wuzesheng-ubuntu:~/Program$ ./a.out |
上面的程序非常easy，我在这里不做过多的解释，感兴趣的朋友能够自己分析一下。
通过我上面的解说，相信大多数朋友应该对C++中内存的动态分配与释放有了较为深入的理解。兴许我还有可能写一些关于C++中内存管理的文章，仅仅有把本文所讲的内容与兴许的内存管理的一些常见的方法结合起来，我们才写出更加健壮的C++程序。欢迎读者朋友留言一起交流！
malloc实现原理