鉴于上次领导告诉一个解决方案，让我把它写成文档，结果自己脑子里知道如何操作和解决，但就是不知道如何用语言文字把它给描述出来。决定以后多写一些笔记和微博来锻炼自己的文字功底和培养逻辑思维，不然只会是一个敲代码的，永远到不了管理的层面。
把《C程序设计语言》细读了一遍后，到第8章UNIX系统接口的最后两节――“目录列表”和“存储分配程序”，看了一遍都没看懂。智商不过高啊。把存储分配重新看了一遍，才有了眉头。这两天还要找时间把目录列表再看一遍，确保掌握。（前几章节有些地方看了很多遍也糊里糊涂，就找谷歌百度帮忙了）
这里的存储分配程序，讲的就是标准库中malloc函数的实现原理。首先要了解针对malloc的内存存储结构。malloc不像全局变量一样，不是在编译器编译的时候就会分配内存空间，而是在调用到malloc函数时才会分配空间。有时还会中途调用free函数释放空间出来。所以：
1、malloc在第一次被调用时，从系统中获取最小为一个单元的空闲空间（eg：最小单元为1024个最受限单元块。当x<=1024，获取1024个，否则获取x个），再进行分配；
2、malloc所剩下的空闲空间一般都不是连续的，而是分散的。这样也提高了空间的利用率。
为了管理malloc的空闲空间，每一个独立块的最前面都包含了一个“头部”信息：一个指向下一个空闲块的指针、一个本身独立块的长度（书上说还有一个指向自身存储空间的指针，但每个存储空间都有自身的指针，为什么还要这个呢。后看英语版原著，这么写的：Each block contains a size, a pointer to nextblock, and the space itself.）。下一个空闲块是按存储地址升序排列，离本空闲块最近的一个空闲块，若本空闲块在最后，则指向最前的空闲块。这样所有属于malloc的空闲空间都被串在了一起。如下图所示：
![\]()
注：中文版的此图解释翻译搞错了，如下图：
![\]()
因为后面的free函数已经把相邻的空闲链表给整合成一块了，所以我的图没有出现相邻的空闲链表。
每块由malloc控制的空间都包含一个“头部”信息，为了方便管理，每块的空间大小都是头部大小的整数倍。而头部长度=指向下一个空闲块的指针的长度+自身空间大小的unsigned长度。但为了确保由malloc函数返回的存储空间满足将要保存的对象的对齐要求。每个机器都有一个最受限的类型：如果最受限的类型可以存储在某一个特定的地址中，则其他所有的类型也可以存放在此地址中。有的是double型，有的是long型，甚至还有的是int型。因此，头部结构将与最受限的类型进行联合，来确保对齐。
因为有头部信息，头部信息里的本块空间size也是包括头部的大小，所以每次申请malloc空闲块的时候，都要加上一个单元，最后返回给用户的时候，再去掉头部。
每次调用malloc申请空间时，malloc有一个专门指向当前空闲块链表的静态指针freep。从当前开始扫描剩下的空闲块链表，直到扫到一个足够大的空闲块。此算法成为“首次适应”（first fit），与之相对的是“最佳适应”（best fit）：它将扫描出满足条件最小的块。这里的代码是“首次适应”算法。结果将出现三种情况：
1）找到一块刚好合适的空闲块，则此块空间从链表中移走并将此块的地址返回给用户，并把静态指针freep指向前一空闲块地址；
2）找到一块比需求大的空闲块，则从此空闲块中的后部取一块与需求一样的空间给用户，前部改变空闲块大小便可；
![\]()
注（直到写本博文才发现自己错了）：
①一直都认为返回给用户地址前一单元的头部，应该把空间退还给前面的空闲块，不然就闲着了。其实，里面记录了一个重要信息：空间块大小（包括头部和返回给用户的单元大小），在free释放空间的时候，就必须用到此头部的信息；
②后面的free程序以为是专供系统申请空间后插入空闲块链表用的，其实它就是我们平常用malloc、realloc、或calloc申请空间后，再释放的程序。
3）如果扫描了一遍，都没有找到足够大的空闲块，则向系统再申请一块新的空间。
上面都是在malloc已经有了空闲块的前提下，但第一次申请的时候，malloc是没有空闲块空间的。因此，在预编译时，就建立了一个单元的空闲块链表base来当做空闲链表的入口。当第一次调用malloc时，空闲链表的静态指针freep为NULL，那将它指向base，大小设为0（这样这块base空间将一直存在，且不被申请，确保了之后freep一直指向有效的空闲块链表），且指向它自己，同时向系统申请空闲空间（每次向系统申请的空间都是一块连续的空闲块）。
typedef long Align; /*按照long类型的边界对齐，即以long作为最受限类型*/
union header{ /*头部信息*/
struct {
union header *ptr; /*指向下一个空闲块*/
unsigned size; /*本空闲块大小*/
}s;
Align x; /*强制对齐*/
};
typedef union header Header;
static Header base; /*第一次调用malloc的空闲块链表入口，大小为0的空链表（按照上面逻辑的来说，这里的size应该为1）*/
static Header *freep = NULL; /*静态的空闲块链表指针，初始化为NULL。第一次申请后才会指向base*/
/*malloc函数：通用存储分配函数*/
void *malloc(unsigned nbytes)
{
Header *p,*prevp; /*定义一个当前空闲块指针变量，和前一个空闲块指针变量*/
Header *morecore(unsigned); /*用于向系统申请空闲空间函数*/
unsigned nunits; /*需要申请的实际单元大小，即上面图中的z*/
nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1; /*与上图对应，把字节大小转换为单元大小，向上取整，并加上一个单元（头部）*/
if((prevp = freep) == NULL){ /*没有空闲链表，第一次申请*/
base.s.ptr = prevp = freep = &base; /*freep指向base，base的下一个空闲块指针指向自己*/
base.s.size =0; /*设置大小为0*/
}
for(p = prevp->s.ptr;;prevp = p, p = p->s.ptr){
if(p->s.size >= nunits){
if(p->s.size == nunits) /*大小刚好合适*/
prevp->s.ptr = p->s.ptr; /*移走此块空闲区域*/
else{ /*比实际需求大，从空闲块尾部分配*/
p->s.size -= nunits; /*缩小空闲块大小*/
p += p->s.size; /*指针指向被申请的空间的头部*/
p->s.size = nunits; /*设置被申请的空闲块大小*/
}
freep =prevp; /*当前静态指针指向前一空闲块，如果当前块还有空闲区域，下次将继续从此处开始扫