_malloc/_free模拟

前言
看《The C Programming_Language》时，对8.7章的malloc讲解感觉不是很理解。趁着时间空闲，在内网里憋了几天，顺便将一些心得和资料记录如下，也让荒废多日的blog添点新东西^_^。
该文中一些注意地方如下，大体思路按照书中原码，改动的部分在“代码中的讲解”这段中有说明；本人在学习过程中难免有一些疏漏，知识水平有限，错误的地方还请大家斧正。
在附件中已经包含可运行代码，一些注意和编译环境都在源代码中说明，可随意转载，请保留版权说明即可。

因为文章比较长，一些段落小题目整理如下：
模拟概念图
申明内存块的规则
释放内存块的规则
内存块结构的定义
分配空间单位大小的设置
代码中的讲解
这里只有9可以满足相邻的条件?
程序运行结果展示

模拟概念图
在本文中将会完成以下功能，先malloc出一大段内存，模拟系统中可用的malloc控制的那段连续内存，然后对它进行申明调用和释放。或者说这也是一个小型的内存池模拟。在书中对malloc内存排列规则有如下的描述：
Since other activities in the program may also request space without calling this allocator, the space that malloc manages may not be contiguous. Thus its free storage is kept as a list of free blocks. Each block contains a size, a pointer to the next block, and the space itself. The blocks are kept in order of increasing storage address, and the last block (highest address) points to the first.

一张完整的模拟图如下，图中红色的数字标志为了方便一些描述而加上


为了更好的理解英文和图，我们这里设想一下现场情况。
假设一个QQ程序启动了，那么他使用的部分内存可能不需要malloc，可以是静态的，自然的，0就归它所有了。可能就这么巧合，系统中给某个程序堆的内存和0号是相邻的，也就是malloc的控制，这中间可能进行了一些优化调整，比如分成10MB的若干块，1MB的若干块等。(就成了1-6的链表块)。接着你启用了你的demo1程序，它得需要10M的内存(in use 1)；你又启动了你的demo2程序，它需要20MB的内存，很不幸,2和3都小于这个容量，还好in use 4满足了这个要求(尽管从图中看起来3似乎比4大块点)。这样若干后，另一个类似QQ的程序启动了，他也需要一些静态，因而7就被它所占领了，再或者需要更太的内存块，10就这么来了。。。。
当然这只是很简单的描述，就比如6和8之间的7可能是经过一系列复杂的变化后掺杂进去，我这么描述只是简单的描绘内存的使用之所以会成如上图的原因。。

摆在我们面前的几个问题如下：一些定义就引用书中的话
申明内存块的规则
When a request is made, the free list is scanned until a big-enough block is found. This algorithm is called ``first fit,'' by contrast with ``best fit,'' which looks for the smallest block that will satisfy the request. If the block is exactly the size requested it is unlinked from the list and returned to the user. If the block is too big, it is split, and the proper amount is returned to the user while the residue remains on the free list. If no big-enough block is found, another large chunk is obtained by the operating system and linked into the free list.
文中只使用"first fit",如果太大则进行分割，将割好的内存返回给用户。如果链中没有合适的内存则向系统申请。该程序中为了简单模拟没有进行这一步，但是通过一些申请、释放也形成了一个不连续的链表，会在后边的块配合代码详细描述。

释放内存块的规则
Freeing also causes a search of the free list, to find the proper place to insert the block being freed. If the block being freed is adjacent to a free block on either side, it is coalesced with it into a single bigger block, so storage does not become too fragmented. Determining the
adjacency is easy because the free list is maintained in order of decreasing address.
简单的说就是根据地址的排列的一些特性，比如从低到高(该程序中的new只是在X86的WINDOWS机上试过是从低到高的连续地址)，放在顺序的地址里并入,这里又分在头部和尾部，连续和不连续等几种。会在后边的块配合代码详细描述。

内存块结构的定义
首先是结构头部的定义，必然包括了一个指向下几一个结点的指针，一个描述该内存块大小的变量，如下所示

struct header
{
	header *ptr;
	unsigned int size;
};

sizeof(header) = 8;而我们分配内存是以字节sizeof(int)为单位，这里要注意下计算。原书中是以header和分配的单位量大小一致，这里略有改动。

那么在内存中如下表示，初始大小

ptr   | size |   size表示的内存大小              					     |
____________________________________________________________________________________
0     3      7                                                                     n

我们来试试，当申请一个 size1大小的内存(尾部返回)，(0<size1<size),需要做如下操作
1、从header.size减去size1大小
2、在size内存段里产生一个对size1描述的header结构
3、将size1内存返回，
虚拟图变成如下

ptr   | size |   size-size1-1         | ptr  | size1|  		size1-1	     |
____________________________________________________________________________________
0     3      7                        |header size=8|                              n

那么其实申请的是header+size1的大小,ptr = size-size1-1;

为了方便释放的描述，假设申请了size1,size2,那就继续从(size-size1-1)这段内存里分割出size2的大小

ptr   | size | size-size1-1-size2-1   | ptr|size2| size2-1    |ptr|size1|size1-1                |
_________________________________________________________________________________________________
0     3      7                       										n

分配空间单位大小的设置
这里为了CPU一个周期的访问，单位的长度为CPU位数/8,比如一台32位的单位长度就是4个字节，不过一些编译器也
可能把他设成8个字节(vs就是8个字节，gcc是4个字节)。那么同理，header也必须是如上的规则.

struct header
{
	header *ptr;			
	unsigned int size;
}

其中指针的大小跟CPU位数相关，为CPU位数/8，unsigned int size;表示的范围是最大能申请的内存，约4G左右(没人会申请那么多吧)，变量大小也是4个字节，符合对齐的规律。那么可知一个块的最小值是sizeof(header)+CPU位数/8,这里还需要一个公式，来对传入的申请值进行计算，以达到以上的对齐规律。假设传入为n，那么将其变为
( n+sizeof(int) )/sizeof(int) + sizeof(header),算出他的sizeof(int)的单位个数.更为细致的方法是，对传入的n值进行是否是该平台内存对齐值的倍数。


代码中的讲解
一些代码风格和算法大部分都按照书上的源码。只是对它做了详细的分析
整体数据结构的模拟:
和上部分的malloc完整模拟图差不多，不同的有三个地方
1、增加了一个链表头，不过不妨碍整个程序运行
2、没有not owned by malloc部分
3、一开始是一段的内存，经过几次使用和释放，模拟成模拟图里的使用情况

代码里和书中不同的地方如下：
1、结构头分配的大小不一样，导致计算方法有所偏差（因为我不知道这本书当时的机器环境）
2、一些算法上的比较，比如_malloc函数中判断是否满足大小的要求，要减去结构头的大小
3、自增了许多打印信息的调试，方便跟踪观察

结构体：

typedef union header 
{	/* block header */
	struct 
	{
		union header *ptr;				/* next block if on free list */
		unsigned size;					/* size of this block */
	} s;
	//Align align_x;						/* force alignment of blocks */
}Header;

这里原先想和书上的内存对齐一致，但是没必要。不过却懒得再对已经写好代码的结构体修改

全局变量：

const int HEADER_LEN     = sizeof(header);   
const int LIST_LEN       = 200;	                  /*空间的大小*/
			
static void *empty_list	  = malloc(LIST_LEN);   	/*empty list to get started*/
static Header *freep_list = NULL;			      /*start of free list*/

函数说明:

void  _init();              				     /*初始,比如链表的结构头等*/
void* _malloc (unsigned nbytes);			     /*分配*/
void  _free   (void * pFree); 			     /*释放*/
void  _debug_node  (const Header *const header);     /*打印一个结点的具体信息*/
void  _debug_list  ();					     /*打印当前链表的信息*/

代码具体说明:
我在源程序中一些地方也已经做了比较完整的注释
void _init():
创建一个表头(暂时没什么用)，然后跳过该表头开始正式内存段。

	/*表头*/
	pHeader->s.size = 0;
	pHeader->s.ptr  = pHeader+1;

	/*第一块内存表头,长度需要减去表头的长度*/
	pHeaderFirst = pHeader->s.ptr;
	pHeaderFirst->s.size = LIST_LEN-HEADER_LEN;

因为这个时候内存只有一块，所以ptr为自己
pHeaderFirst->s.ptr  = pHeaderFirst;

void *_malloc(unsigned int nbytes):
在指针使用上是这样的，首先获得当前freep_list第一个结点pPrev，接着将pUsed的值设为pPrev的ptr值。这样虽然在第一次遍历会条过第一个结点，但是极大方便了内存的分配。在对pUsed这块内存进行判断大小时，采取的是best fit(详见前文描述)策略。如果刚好等于，则将pUsed+1返回当前可用内存，而pPrev的ptr设为pUsed的ptr,保持链表的循环；如果大于，则在pUsed的内存中划分出一段内存，对其设置好头部大小后返回，不做其他的操作.最后是判断是否循环到尾的操作

		if( pUsed==freep_list->s.ptr )        /*wrapped around free list*/
		{
			return NULL;
		}

还记得我们刚才跳过的结点吗？刚好在第二次遍历完它的时候进行退出的判断

void _free(void * pFree):
	/*跳过表头结构*/
	pFree_list = freep_list->s.ptr;
	for( ; !(pFree_list<pHeader && pHeader<pFree_list->s.ptr) ; 
		   pFree_list = pFree_list->s.ptr)
	{
		if( pFree_list>=pFree_list->s.ptr && 
			(pFree_list<pHeader || pHeader<pFree_list->s.ptr)
		  )
		{
			break;
		}
	}

假设现在链表如下：(地址从低到高，循环链表)
3->4->6->8
这里分三种情况，分别是头、尾、中间，用以下值假设地址
pHeader={ 1,2,5,9,10 },
所以在for的条件中用pFree_list<pHeader && pHeader<pFree_list->s.ptr判断是否在两个结点的中间。如果是pFree=5；则很好理解。如果是1或者9则这条规则不适用，则以pFree_list>=pFree_list->s.ptr判断是否到尾部。其中，

		 /*		 
		 *pFree_list == pFree_list->s.ptr,	表示只有一个结点
		 *pFree_list > pFree_list->s.ptr，	表示大于1个结点
		 *pHeader    < pFree_list->s.ptr,	表示插入头部
		 *pFree_list < pHeader:			表示插入尾部
		*/

但接下来的代码很巧妙的完成了并入了过程，并没有用到pHeader<pFree_list->s.ptr和pFree_list<pHeader这两个条件,不过也给出了利用这两个条件的伪码.

	if( (int)pHeader + pHeader->s.size == (int)pFree_list->s.ptr )
	{
		pHeader->s.size += pFree_list->s.size;
		pHeader->s.ptr  = pFree_list->s.ptr->s.ptr;
	}
	else
	{
		pHeader->s.ptr = pFree_list->s.ptr;
	}

	if( (int)pFree_list + pFree_list->s.size == (int)pHeader )
	{
		pFree_list->s.size += pHeader->s.size;
		pFree_list->s.ptr  =  pHeader->s.ptr; /*这句我认为是多余的*/
	}
	else
	{
		pFree_list->s.ptr  = pHeader;
	}

这里以pFree为10为例子,最终我们要把它变成3->4->6->8->10的形式。这时的pFree_list=8.首先不满足第一个if,在else部分将自己的ptr指向3;在第二个if中，也不满足if的条件(这里只有9可以满足相邻的条件)。在else部分，将8的ptr设为10.这样就完成了一个结点的插入。即在这个循环链表里，对假设是头部的进行头部结点的操作；对假设是尾部的进行尾部结点的操作。恰好的完成了结点的并入。

/*
	这里给出另一段伪代码，根据pFree_list<pHeader || pHeader<pFree_list->s.ptr
	这两个条件来判断是在头部还是尾部。原来的代码更简练。
*/	
	//头部插入
	if( pHeader < pFree_list->s.ptr )
	{
		if( pHeader + pHeader->s.size == pFree_list->s.ptr )	//刚好
		{
			pHeader->s.size += pFree_list->s.size;
			pHeader->s.ptr  = pFree_list->s.ptr->s.ptr;
		}
		else
		{
			pHeader->s.ptr = pFree_list->s.ptr;
			pFree_list->s.ptr  = pHeader;            		//看吧，只是多了一行代码
		}
	}

这里只有9可以满足相邻的条件?
这里也是利用了地址相邻的特性。假设一段可用内存有100字节，头部占用8个字节。申请50个字节，那原有的可用字节只有100-8-50=42.即申请的内存从地址42开始，所以这是只要将可用内存加上自己的size判断是否会和下一段内存相等即可知相邻。然后将两段内存并入。换一句话说，内存的碎片也是这样产生的，如果中间(地址相邻)的内存不释放或者释放不正确，则下一个结点就无法进行归并，当然这个还有很多原因，起码这也是其中之一。


程序运行结果展示
终于到最后一个模块了。。
假设内存最早是200byte，我们申请10，15，20，25这几块内存。结果如下：
以*****************/做为分块表示

因为链表头部用了8个字节，所以第一块的size为192。从2-5块里，都是对分配到的结点信息。_malloc:nunits:20:10,:10表示我们需要的申请的内存数，20表示实际申请的内存数(包括一个结构头和内存对齐).

这时可用的链表中信息如下：

192-20-24-32-36=80

释放掉3和5块的内存


这个时候可用的链表中信息如下


为什么是116呢？注意，这个时候按顺序申请的内存实际是倒着链表，所以5块被认为是开头的点了，就自然的并入了



完整代码见 代码储备->malloc模拟

资料参考
《The C Programming_Language》  K&R
8.7 Example - A Storage Allocator