学过 c 语言的同学一定用过malloc, calloc, realloc, free . 学会自己管理内存可以使程序性能更高。然而在不了解其内部原理的情况下使用它们，容易造成内存溢出, 野指针等问题.
通过这篇文章，你将了解到内存，虚拟内存等概念，并且自己手写一个内存管理器 (Memory Allocator)
内存 (RAM) 与 硬盘 (DRIVER)#
有些人会把内存和硬盘的概念混淆。通常，内存是用来储存程序的二进制指令及相关变量的硬件，而硬盘则是用来储存大量数据的硬件.
实际上，内存和硬盘没有本质的区别，它们都是计算机储存器(memory), 用来储存一定的数据。内存的访问速度快，但是单位造价高，所以用作需要频繁读写的地方，例如储存程序上下文。硬盘，读写速度相较于内存较慢，但是容量大，适合用作长期储存不需要频繁读写的文件.
内存可以看作是硬盘的缓存，当需要获取一段数据时，可以将硬盘的数据临时拷贝到内存。等到计算机需要这些数据时，可以直接从读写速度很快的内存中拿到它们.
这样的缓存机制在计算机里随处可见，cpu 中除了 ALU (计算单元外), 还有一个重要的部分叫做 register (寄存器), 寄存器也是一种计算机储存器，它可以看作是内存的缓存。这样的说法实际上有些片面，cpu 还有一种叫做三级缓存的机制，此处不再赘述，有兴趣的读者可以自行查阅.
虚拟内存#
虚拟内存, 是计算机系统 (OS) 对一块内存的抽象。在应用程序的视角中，自己占据计算机的全部内存 (一块连续可用的地址空间). 然而实际上，这块内存是由计算机系统暴露给应用程序的内存碎片。它可能不仅仅包含一部分物理内存，还会包含硬盘空间.
如果没有虚拟内存，进程 (process) 间会对内存资源进行争夺，甚至越界访问，极易造成内存泄漏。并且由于进程的内存是以块的形式储存，小部分未分配的内存无法被更大的进程申请，造成了一定的资源浪费.
使用虚拟内存管理物理内存，我们可以将物理内存人为的划分成一个个块 (chunk), 多个块组成页 (page), 然后将页与其占有情况写入页表。这样就可以将进程所需的内存拆分成块的形式储存，我们不必使这些内存集中存放，相反可以将它们放入任意位置. 只需要记录虚拟内存与物理内存之间的映射关系 (index), 将映射关系存放在页表中，我们就可以根据这些信息找到物理内存地址. 并且这些操作都是由硬件完成，速度极快，大大增加了内存的可用性和效率.
cpu 首先接受到操作指令，并且将虚拟地址发送到 MMU (内存管理单元), MMU 将访问物理内存 (实际上访问了物理内存的缓存，TLB) 获取页表，然后找到其映射关系并计算出物理地址，之后交给 cpu, cpu 访问物理内存取得数据.
内存的结构#
在开始操作内存前，我们先了解一下内存的结构都有哪些.
- Text section
- Data section
- BSS
- Heap
- Stack
我们在使用malloc时操作的内存结构是 Heap (堆). 它的末尾有一个名为brk的指针，它指向堆顶.
这是一种可以动态分配的内存结构，可以根据需求动态的申请一定量的内存，同时支持删除操作，我们一般通过指针对申请的地址进行数据操作.
操作内存并不需要我们直接对硬件进行操作，可以直接使用系统封装好的 APIsbrk()
sbrk(0)返回当前程序执行的位置的内存地址.
sbrk(x)使得brk向正方向增长 x 字节 (bytes).
sbrk(-x)使得brk向负方向增长 x 字节 (bytes).
如果 sbrk () 出于某些原因未能完成操作，将返回(void*) -1
malloc()#
好了，目前为止我们终于可以写出一个简易的malloc()了:
void* malloc( size_t size )
{
void* block;
block = sbrk(size);
if ( block == (void*) -1 )
return NULL;
return block;
}
看起来很不错，但是不够完美.
在写free()函数时我们接受一个指针，以便释放与它相关的内存，然而我们如何得知释放内存的大小呢？
我们可以在每段地址的初段定义一个Header:
struct header_t {
size_t size;
unsigned is_free;
};
size用来储存Header指向的内存的大小.
is_free用来标记这块内存是否被占用.
现在我们的一块内存看起来是这样的:
我们还需要一个方法可以遍历这个内存，因为我们需要遍历以找到一块未被占用的内存。链表是一个不错的方案:
struct header_t {
size_t size;
unsigned is_free;
struct header_t* next;
};
现在它长这样:
由于我们以块的形式管理内存，所以需要对齐操作:
typedef char ALIGN[16];
union header {
struct {
size_t size;
unsigned is_free;
union header *next;
} s;
ALIGN stub;
};
typedef union header header_t;
我们还需要定义首尾节点:
header_t *head, *tail;
为了避免多线程同时调用内存，要定义我们加入全局锁，在申请完地址后再释放:
pthread_mutex_t global_malloc_lock;
现在我们的版本是这样的:
void* malloc(size_t size) {
size_t total_size;
header_t* header;
void* block;
if ( size <= 0 ) {
return NULL;
};
pthread_mutex_lock(&global_malloc_lock);
header = get_header_t(size);
if (header)
{
header->s.isFree = 0;
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(header + 1);
}
total_size = size + sizeof(header_t);
block = sbrk(total_size);
if (block == (void*) - 1) {
pthread_mutex_unlock(&global_malloc_lock);
return NULL;
} else {
header = block;
};
header->s.isFree = 0;
header->s.size = size;
header->s.next = NULL;
if (head == NULL)
head = header;
if (tail)
tail->s.next = header;
tail = header;
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(header + 1);
};
header_t* get_header_t( size_t size ) {
header_t* curr = head;
while (curr)
{
if ( curr->s.isFree && curr->s.size >= size) {
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(head);
};
curr = curr->s.next;
}
return NULL;
}
首先我们判断申请的内存是否合法，之后寻找最低地址的节点指针 (get_header_t()).
找到了就标记为isFree, 然后解锁返回虚拟地址的首端的指针.
如果没有找到，就调用sbrk申请内存，并初始化header将其设为tail节点，之后解锁返回地址.
其中total_size包含头部与实际所需内存大小两部分.
free()#
在设计free()函数时，有一个需要注意的细节：先判断需要释放的地址是否位于堆的尾部
如果位于尾部，则直接交给操作系统释放，否则将其标记为isFree, 我们将在以后重用它们.
void free(void* block) {
if (!block)
{
return NULL;
}
header_t* header = (header_t*)block - 1;
void* programbreak = sbrk(0);
pthread_mutex_lock(&global_malloc_lock);
if ((char*)block + header->s.size == programbreak)
{
size_t total_size = header->s.size + sizeof(header_t);
//release
if (head == tail)
{
head = tail = NULL;
} else {
header_t* curr = head;
//change tail
while (curr->s.next == tail)
{
curr->s.next = NULL;
tail = curr;
}
}
sbrk(-total_size);
pthread_mutex_unlock(&global_malloc_lock);
return;
};
header->s.isFree = 1;
pthread_mutex_unlock(&global_malloc_lock);
}
首先找到brk的位置并将其赋给programbreak, 之后判断释放的对象是否位于堆顶.
char*与size_t, void*具有相同的字节数:
//test.c
#include <stddef.h>
int main(int argc, char const *argv[])
{
printf("char* is:%d, char is:%d, void* is:%d, size_t is:%d", sizeof(char*), sizeof(char), sizeof(void*), sizeof(size_t));
return 0;
}
//char* is:8, char is:1, void* is:8, size_t is:8
如果在堆顶，则(char*)block + header->s.size == programbreak
之后遍历找到最后一块内存并释放，把倒数第二块内存设为tail.
如果不在堆顶，则暂时标记为isFree, 等待之后复用.
calloc()#
void* calloc( size_t nsize, size_t num)
{
size_t size;
void* block;
if (!num || !nsize)
return NULL;
size = nsize * num;
//overflow check
if (size != nsize * num)
return NULL;
block = malloc(size);
if (!block)
return NULL;
memset(block, 0, size);
return block;
}
calloc () 要求返回的地址所指向的内存块都为Null, 我们可以通过memset将其设为 0.
realloc()#
void* realloc(void* block, size_t size)
{
header_t* header;
void* ret;
if (!block || !size)
return NULL;
header = (header_t*)block - 1;
if (header->s.size >= size)
return block;
ret = malloc(size);
if (ret)
{
memcpy(ret, block, header->s.size);
free(block);
}
return ret;
}
realloc()比较特殊，使用时应该注意返回的指针所指向的地址不一定会是原来的地址.
因为realloc()时，会出现两种情况:
- 堆内存向高位增长，上方空闲的内存大小可以容纳增长大小。则返回原来的地址，并修改
header的size. - 堆内存上方空闲内存不足，调用
malloc重新申请一块地址，并把原地址内容复制给新申请的地址.
Compile#
$ gcc -o memalloc.so -fPIC -shared memalloc.c
$ export LD_PRELOAD=$PWD/memalloc.so
$ ls
memalloc.c memalloc.so
拓展#
c/c++ 一直以其性能优越著名，然而这也是一直让人诟病的地方。如果使用它的人缺少对计算机系统的深入了解，很容易造成误操作.
而其他高级语言将内存管理自动化，并将其机制命名为垃圾回收(OC), 其原理大致可概况为：如果某对象不可达则会被垃圾回收器回收.
References#
推荐阅读: