有关内存管理的算法实在是太多了，多到什么程度呢？基本上能想得到的数据结构，都能出现在各式各样的内存管理算法之中，数组、链表、散列表、二叉树等等都在这里大放异彩。研究内存管理实在是一件有趣的事情，同时也能极大的提高自己的编程能力。
内存管理方案
MudOS中定义了至少3套内存分配函数库：
1. Build-in system malloc——系统内建函数库，即malloc，realloc，calloc，free；
2. Satoria's malloc——这算是专门为MudOS打造的函数库，比大多数系统内建函数要快；
3. BSD (Berkeley Software Distributions) malloc——随着FreeBSD发布出来的malloc源代码，速度应该算是最快的，但会浪费不少内存空间。
定义了至少2套包装（wrap）函数库：
1. WRAPPEDMALLOC——简单的对内存分配函数进行了一下包装，提供了有限的内存分配统计功能：内存分配次数（alloc），内存释放次数（free），内存再分配次数（realloc）；
2. DEBUGMALLOC——正如其名所暗示的：调试期使用的内存分配函数，它的实现比较复杂，不仅提供了安全性检查，而且提供的统计功能也更完善，比如可以查出某次内存分配是为哪种数据类型提供内存空间。
在编译MudOS时，通过选择不同的宏定义来选择不同的内存管理方案：
/* macro.h */
/*
Define for MALLOC, FREE, REALLOC, and CALLOC depend upon what malloc
package and optional wrapper is used. This technique is used because
overlaying system malloc with another function also named malloc doesn't
work on most mahines that have shared libraries. It will also let
us keep malloc stats even when system malloc is used.
Please refer to options.h for selecting malloc package and wrapper.
*/
#if (defined(SYSMALLOC) + defined(SMALLOC) + defined(BSDMALLOC)) > 1
!Only one malloc package should be defined
#endif
#if (defined(WRAPPEDMALLOC) + defined(DEBUGMALLOC)) > 1
!Only one wrapper (at most) should be defined
#endif
#if defined (WRAPPEDMALLOC) && !defined(IN_MALLOC_WRAPPER)
# define MALLOC(x) wrappedmalloc(x)
# define FREE(x) wrappedfree(x)
# define REALLOC(x, y) wrappedrealloc(x, y)
# define CALLOC(x, y) wrappedcalloc(x, y)
# define DXALLOC(x, t, d) xalloc(x)
# define DMALLOC(x, t, d) MALLOC(x)
# define DREALLOC(x, y, t, d) REALLOC(x,y)
# define DCALLOC(x, y, t, d) CALLOC(x,y)
#else
# if defined(DEBUGMALLOC) && !defined(IN_MALLOC_WRAPPER)
# define MALLOC(x) debugmalloc(x, 0, (char *)0)
# define DMALLOC(x, t, d) debugmalloc(x, t, d)
# define DXALLOC(x, t, d) debugmalloc(x, t, d)
# define FREE(x) debugfree(x)
# define REALLOC(x,y) debugrealloc(x,y,0,(char *)0)
# define DREALLOC(x,y,tag,desc) debugrealloc(x,y,tag,desc)
# define CALLOC(x,y) debugcalloc(x,y,0,(char *)0)
# define DCALLOC(x,y,tag,desc) debugcalloc(x,y,tag,desc)
# else
# include "malloc.h"
# endif
#endif
/* malloc.h */
/*
* to use sysmalloc or malloc replacements
*/
#if defined(SYSMALLOC) || \
(defined(SMALLOC) && defined(SBRK_OK)) || \
defined(BSDMALLOC)
#define MALLOC(x) malloc(x)
#define FREE(x) free(x)
#define REALLOC(x,y) realloc(x,y)
#define CALLOC(x,y) calloc(x,y)
#endif
/* smalloc - choice between replacement or wrapper */
#if defined(SMALLOC) && !defined(SYSMALLOC)
# ifdef SBRK_OK
# define smalloc_malloc malloc
# define smalloc_free free
# define smalloc_realloc realloc
# define smalloc_calloc calloc
# else
# define MALLOC(x) smalloc_malloc(x)
# define FREE(x) smalloc_free(x)
# define REALLOC(x,y) smalloc_realloc(x,y)
# define CALLOC(x,y) smalloc_calloc(x,y)
# endif
#endif
/* bsdmalloc - always a replacement */
#if defined(BSDMALLOC) && !defined(SYSMALLOC)
# define bsdmalloc_malloc malloc
# define bsdmalloc_free free
# define bsdmalloc_realloc realloc
# define bsdmalloc_calloc calloc
#endif
#define DXALLOC(x,tag,desc) xalloc(x)
#define DMALLOC(x,tag,desc) MALLOC(x)
#define DREALLOC(x,y,tag,desc) REALLOC(x,y)
#define DCALLOC(x,y,tag,desc) CALLOC(x,y)
另外在其他文件里有些零零散散宏定义，这所有的宏定义组合起来，让MudOS最终编译时拥有一套合适的内存分配方案。这两个文件（macro.h、malloc.h）的内容大致描述了选择不同的宏定义将会使用到哪些内存分配函数。
（注: 这些宏定义之间的联系实在是错综复杂，足足看了两天才搞清楚选择某个宏将会用到哪些函数。然而在C++里面，完全可以抛开这些宏定义，直接用模板来控制客户代码所使用的函数库，比如STL中的Allocator，这么做又不会损失执行效率，可见模板真是个不错的东西，难怪java、c#要添加这些功能。）
列举几个在MudOS源码中出现的比较奇怪的宏定义：
1.
#if (defined(SYSMALLOC) + defined(SMALLOC) + defined(BSDMALLOC)) > 1
#error Only one malloc package should be defined
#endif
三个宏至少定义一个，否则报错。#error是我自己添加的，源代码为“！”，为什么源代码不用#error呢？
在#if语句里，可以使用大小比较符号：“>”、“<”、“==”比如下面这行代码：
#if defined(AA) || defined(BB) || defined(CC)
就可以改写成：
#if (defined(AA) + defined(BB) + defined(CC)) > 0
2.
#if defined(BSDMALLOC) && !defined(SYSMALLOC)
# define bsdmalloc_malloc malloc
# define bsdmalloc_free free
# define bsdmalloc_realloc realloc
# define bsdmalloc_calloc calloc
#endif
如果定义了BSDMALLOC，而SYSMALLOC未定义，那么用malloc代替bsdmalloc_malloc。这是个非常奇怪的定义：假如编译过程中已有malloc函数的定义，那么用这里出现的替代将会导致程序编译出现重定义的错误。比如下面这个例子：
void func() {
};
#define FUNC func
void FUNC() { // !error: function 'void __cdecl func(void)' already has a body
};
或许作者压根就不想用bsdmalloc_malloc，如同注释里写的”always a replacement”，只是把已有代码里的bsdmalloc_malloc替换成系统内建的malloc。同样问题也出现在smalloc上。这里不对其深究，老实说这些龇牙咧嘴的宏定义很容易让人走火入魔的。
BSD malloc
虽然新版的MudOS可能不打算使用BSD malloc，但还是有必要介绍一下里面涉及到的算法——“Studying memory usage trends of programs is a very interesting activity”（ Andrei Alexandrescu, Modern C++ Design: Generic Programming and Design Patterns）。
大概每种存储分配都需要对每个可用内存块定义一个overhead，记录一些分配信息以便释放内存。在BSD malloc函数库中是这样定义的：
union overhead {
union overhead *ov_next; /* when free */
struct {
u_char ovu_magic; /* magic number */
u_char ovu_index; /* bucket # */
#ifdef RCHECK
u_short ovu_rmagic; /* range magic number */
u_int ovu_size; /* actual block size */
#endif
} ovu;
#define ov_magic ovu.ovu_magic
#define ov_index ovu.ovu_index
#define ov_rmagic ovu.ovu_rmagic
#define ov_size ovu.ovu_size
};
当内存块未被使用时，这些内存块形成一个链表，ov_next指向下一块内存。当内存块被使用时，ovu_index标识这块内存隶属于链表散列中的哪个链表。释放的时候直接将这个内存块链接到那个链表上就可以了。
BSD malloc的内存块由一个链表散列来管理。桶子个数为30，第i个桶子可以处理的内存大小为2^(i+3)，每个桶子管理一个未使用内存链表，链表元素包括一个overhead和一块固定大小的内存块，分配内存时总是选择能够令目标大小最接近不大于2^(i+3)的桶子，比如需要分配15字节大小内存，加上overhead的大小4，总共19byte，将使用到元素大小为2^(2+3)的桶子，也就是第2个（从0开始）。桶子定义如下：
#define NBUCKETS 30
static union overhead *nextf[NBUCKETS];
BSD malloc的内存分配和释放非常的简单。
分配：
寻找合适的桶子i。
若这个桶子是第一次用到，则调用底层函数sbrk分配内存，将内存按照2(i+3)大小划分，将每个内存块链接成链表
将nextf[i]分配给客户代码，nextf[i]指向nextf[i].ov_next
释放：
待释放内存块cp
op = (union overhead *) ((caddr_t) cp - sizeof(union overhead));
取出op->ov_index值作为桶子索引i
待释放内存块指向nextf[i].ov_next
nextf[i]指向待释放内存块
从BSD malloc的实现来看，由于使用的链表，它的释放也就不涉及到合并内存块的问题。但是由于总是选取最接近但不大于2^(i+3)的大小来分配，这样造成的浪费是很可观的。比如需要分配15字节，但是管理器却为之付出了32byte。这也许就是MudOS最终放弃这个函数库的原因吧？
Satoria's malloc
这个函数库用AVL Tree来管理内存。因为后续章节会介绍到AVL Tree，所以这里就不介绍它的实现了（主要是代码太多——1500多行，汗）
WRAPPEDMALLOC
这个包装简单而实用，通过察看stats.alloc_calls – stats.free_calls来确定是否造成内存泄露：
/* wrappedmalloc.c */
typedef struct stats_s {
unsigned int free_calls, alloc_calls, realloc_calls;
} stats_t;
static stats_t stats;
void wrappedmalloc_init()
{
stats.free_calls = 0;
stats.alloc_calls = 0;
stats.realloc_calls = 0;
}
INLINE void *wrappedrealloc P2(void *, ptr, int, size)
{
stats.realloc_calls++;
return (void *) REALLOC(ptr, size);
}
INLINE void *wrappedmalloc P1(int, size)
{
stats.alloc_calls++;
return (void *) MALLOC(size);
}
INLINE void *wrappedcalloc P2(int, nitems, int, size)
{
stats.alloc_calls++;
return (void *) CALLOC(nitems, size);
}
INLINE void wrappedfree P1(void *, ptr)
{
stats.free_calls++;
FREE(ptr);
}
void dump_malloc_data P1(outbuffer_t *, ob)
{
outbuf_add(ob, "using wrapped malloc:\n\n");
outbuf_addv(ob, "#alloc calls: %10lu\n", stats.alloc_calls);
outbuf_addv(ob, "#free calls: %10lu\n", stats.free_calls);
outbuf_addv(ob, "#alloc - #free: %10lu\n",
stats.alloc_calls - stats.free_calls);
outbuf_addv(ob, "#realloc calls: %10lu\n", stats.realloc_calls);
}
DEBUGMALLOC
这个包装就非常复杂了，由于是debug的时候使用，那么当然是选择强健的代码而不需要考虑效率了。
仅仅通过阅读debugmalloc函数的代码就可窥全豹。
/* debugmalloc.c */
#ifdef NOISY_MALLOC
#define NOISY(x) printf(x)
#define NOISY1(x,y) printf(x,y)
#define NOISY2(x,y,z) printf(x,y,z)
#define NOISY3(w,x,y,z) printf(w,x,y,z)
#else
#define NOISY(x)
#define NOISY1(x,y)
#define NOISY2(x,y,z)
#define NOISY3(w,x,y,z)
#endif
#define MD_OVERHEAD (sizeof(md_node_t))
INLINE void *debugmalloc P3(int, size, int, tag, char *, desc)
{
void *tmp;
if (size <= 0)
fatal ("illegal size in debugmalloc()"); // mudos结束
stats.alloc_calls++;
tmp = (void *) MALLOC(size + MD_OVERHEAD);
MDmalloc(tmp, size, tag, desc);
NOISY3("malloc: %i (%x), %s\n", size, (md_node_t *)tmp + 1, desc);
return (md_node_t *) tmp + 1;
}
每次分配内存，都将stats.alloc_calls++，除了这么简单的统计功能之外，每次分配在将多分配sizeof(md_node_t)大小的内存用来记录一些附加信息，这个结构体的内容如下：
typedef struct md_node_s {
int size; // 内存大小
struct md_node_s *next; // 下一块被分配的内存
#ifdef DEBUGMALLOC_EXTENSIONS
int id; // 该次分配的id
int tag; // 数据类型
char *desc; // 描述
#endif
#ifdef CHECK_MEMORY
int magic;
#endif
} md_node_t;
分配后的内存见下图：
MALLOC为实际分配函数，而MDmalloc则处理附加信息节点的相关操作。
/* MD.c */
void
MDmalloc P4(md_node_t *, node, int, size, int, tag, char *, desc)
{
unsigned int h;
static int count = 0;
if (!size) {
debug_message("md: debugmalloc: attempted to allocate zero bytes\n");
#ifdef MDEBUG
abort();
#endif
return;
}
total_malloced += size;
if (total_malloced > hiwater) {
hiwater = total_malloced;
}
h = (unsigned int) node % TABLESIZE;
node->size = size;
node->next = table[h];
#ifdef CHECK_MEMORY
LEFT_MAGIC(node) = MD_MAGIC;
STORE_RIGHT_MAGIC(node);
#endif
#ifdef DEBUGMALLOC_EXTENSIONS
if ((tag & 0xff) < MAX_CATEGORY) {
totals[tag & 0xff] += size;
blocks[tag & 0xff]++;
}
if (((tag >> 8) & 0xff) < MAX_CATEGORY) {
totals[(tag >> 8) & 0xff] += size;
blocks[(tag >> 8) & 0xff]++;
}
node->tag = tag;
node->id = count++;
node->desc = desc ? desc : "default";
if (malloc_mask == node->tag) {
debug_message("MDmalloc: %5d, [%-25s], %8x:(%d)\n",
node->tag, node->desc, (unsigned int) PTR(node), node->size);
}
#endif
table[h] = node;
}
在MDmalloc函数中，每个附加信息节点通过一个散列链表来管理，定义如下：
static md_node_t **table;
初始化如下：
void MDinit()
{
int j;
table = (md_node_t **) calloc(TABLESIZE, sizeof(md_node_t *));
for (j = 0; j < MAX_CATEGORY; j++) {
totals[j] = 0;
}
}
因此分配完毕后实际管理附加信息节点的链表如图所示：
