凡是涉及到内存的地方都有相应的内存分配算法。内核空间有内核空间的内存分配算法，比如，Buddy-System、slab分配器等；用户进程空间也有相应的内存分配算法，比如，First-Fit、Best-Fit、Nest-Fit、Worst-Fit等；而应用程序也可能根据自身内存使用特点，采用自己实现的内存分配算法，比如，memcached、nginx、lighttpd会使用splay tree之类的内存分配算法。可见没有绝对好的算法，只有最适用的算法。
今天简单了解一下我们平时最常用的用户进程空间的内存分配函数：malloc(3)。这个内存分配函数其实有很多种实现，常用的一种内存分配算法是First-Fit，因为分配速度快。一般做法是，维护一个空闲链表，记录所有可用的内存块。当遇到内存请求的时候，遍历该链表，找到第一个满足条件的内存块即返回。当然这样可能很容易导致内存碎片，所以对碎片的处理是各种malloc算法的关键。相应的free函数一般比较简单，直接在空闲链表里标记该内存可用即可，也有些做法是在free的时候做相邻碎片的合并。
大致算法描述如下：
malloc(待分配内存大小n)
Begin
For 空闲链表的每个空闲块记录 Do
If 空闲块大于n Then
切分空闲块，剩下的重新挂到空闲链表上
Return 大小为n的空闲块
End If
End For
合并空闲链表上相邻的空闲块
If 合并后的空闲块大于n Then
切分空闲块，剩下的重新挂到空闲链表上
Return 大小为n的空闲块
End If
调用sbrk(n)像系统请求内存，即扩展堆大小
If 调用成功 Then
Return 请求到的内存块
End If
Return NULL
End
free(内存地址)
Begin
在空闲链表上标记该内存可用
End
下边按照如上算法描述实现一套简陋的内存分配方法。其中一个技巧是，使用自定义的内存控制块结构mem_control_block来保存当前内存块的相关信息，同时可以在一个连续线性地址上当作空闲链表节点来使用。
/* 内存分配程序的初始化标识 */
int has_initialized = 0;
/* 内存分配的起始地址 */
void *managed_memory_start;
/* 内存分配的结束地址 */
void *last_valid_address;
/* 内存分配程序的初始化函数 */
void malloc_init()
{
/* 获取堆的边界地址 */
last_valid_address = sbrk(0);
/* 还没有分配内存，所以初始化为边界地址 */
managed_memory_start = last_valid_address;
/* 标记初始化完毕 */
has_initialized = 1;
}
/* 内存控制块结构定义 */
struct mem_control_block
{
int is_available;
int size;
};
void free(void *firstbyte)
{
struct mem_control_block *mcb;
/* 首先寻找mem_control_block结构 */
mcb = firstbyte - sizeof(struct mem_control_block);
/* 修改标识，表明该段内存重新可用了 */
mcb->is_available = 1;
return;
}
void *malloc(long numbytes)
{
/* 从这个地址开始寻找空闲内存 */
void *current_location;
/* 同上，但被cast成 struct mem_control_block* */
struct mem_control_block *current_location_mcb;
/* 待返回的分配地址 */
void *memory_location;
if(! has_initialized) {
malloc_init();
}
/* 实际分配的地址还要包括控制信息，但这对用户是透明的 */
numbytes = numbytes + sizeof(struct mem_control_block);
memory_location = 0;
current_location = managed_memory_start;
while(current_location != last_valid_address) {
current_location_mcb = (struct mem_control_block *)current_location;
if(current_location_mcb->is_available) {
if(current_location_mcb->size >= numbytes) {
/* 标记找到了合适的内存块 */
current_location_mcb->is_available = 0;
memory_location = current_location;
break;
}
}
/* 没找到合适的内存块，跳到链表的下一元素 */
current_location = current_location + current_location_mcb->size;
}
/* 如果当前链表中没有足够的内存块分配，则向操作系统请求 */
if(! memory_location) {
/* 著名的sbrk()函数，扩大堆边界 */
sbrk(numbytes);
memory_location = last_valid_address;
last_valid_address = last_valid_address + numbytes;
/* 保存信息到控制节点 */
current_location_mcb = memory_location;
current_location_mcb->is_available = 0;
current_location_mcb->size = numbytes;
}
memory_location = memory_location + sizeof(struct mem_control_block);
return memory_location;
}
Linux系统里glibc的malloc函数使用ptmalloc实现，是来自dlmalloc的改进。dlmalloc把类似大小的内存块组成bins以便改进速度和降低总体的碎片数，dlmalloc算法大致如下。
- 对小于256字节的请求(smallbin)，使用了一个简单的两倍Best-Fit分配器。并且利用CPU指令(
__builtin_clz())来快速寻找合适的bin。如果在一个bin里面没有空闲块，就接着寻找下一个bin并切分。 - 对大于等于256字节但小于mmap阈值的(largebin)，使用了一个in-place的bitwise trie算法。
- 对大于等于mmap阈值的，使用mmap系统调用分配内存，它总是按页分配，即4KB的倍数。mmap阈值默认是256KB(ptmalloc是1MB)，可以使用
mallopt()函数更改。 - 如果小于mmap阈值，又没有足够的空闲空间，dlmalloc会通过
brk()增加堆的大小。
因为空闲空间的碎片合并会导致刷新TLB，所以dlmalloc只有一个很弱的碎片合并算法，每4096次free()调用会执行一次碎片合并。