动态分配内存，进行内存管理

参考:
伙伴算法原理简介
linux 0.11源码

本文主要针对Linux0.11的malloc和free进行分析。是一种类似伙伴系统的内存管理方法，不过伙伴系统的内存通常是申请大于一页的内存，但是在该内核版本的内存管理，申请的内存是小于一页的。

1.结构体

桶描述符bucket_desc ，用于关联物理页page，和空闲内存freeptr。bucket_size桶的大小用于确定每次分配的内存大小。同时桶描述符会进行链表连接bucket_desc。

struct bucket_desc {	/* 16 bytes */void			    *page;          // 管理的物理页struct bucket_desc	*next;          // 下一个bucket地址void			    *freeptr;       // 下一个可供分配的unsigned short		refcnt;         // 引用计数，释放物理页时要用unsigned short		bucket_size;    // 每个桶的大小
};
/** This contains a linked list of free bucket descriptor blocks 这包含空闲bucket描述符块的链接列表*/
struct bucket_desc *free_bucket_desc = (struct bucket_desc *) 0;

桶目录，用于确定分配的内存大小和与桶描述符进行关联。bucket_dir的size是2的n次幂，最大是4096，即为1页大小（4K），当超过1页时，无法分配。

struct _bucket_dir {	/* 8 bytes */int			size;struct bucket_desc	*chain;
};struct _bucket_dir bucket_dir[] = {{ 16,	(struct bucket_desc *) 0},{ 32,	(struct bucket_desc *) 0},{ 64,	(struct bucket_desc *) 0},{ 128,	(struct bucket_desc *) 0},{ 256,	(struct bucket_desc *) 0},{ 512,	(struct bucket_desc *) 0},{ 1024, (struct bucket_desc *) 0},{ 2048, (struct bucket_desc *) 0},{ 4096, (struct bucket_desc *) 0},{ 0,    (struct bucket_desc *) 0}
};   /* End of list marker */

2.初始化存储桶描述页

static inline void init_bucket_desc()
{struct bucket_desc *bdesc, *first;int	i;first = bdesc = (struct bucket_desc *) get_free_page();if (!bdesc)return ;for (i = P_SIZE/sizeof(struct bucket_desc); i > 1; i--) {    // 進行拼接bdesc->next = bdesc+1;bdesc++;}/** This is done last, to avoid race conditions in case* get_free_page() sleeps and this routine gets called again....* 这是最后完成的，以避免在get_free_page（）休眠并且再次调用此例程时出现竞争条件。。。*/bdesc->next = free_bucket_desc;free_bucket_desc = first;
}

init_bucket_desc会申请一个物理页，用于存储bucket_desc 描述符，如下图所示：

申请的物理页会存储256(4096 / 16)个桶描述符bucket_desc， free_bucket_desc会指向第一个空闲的bucket_desc。

3.申请内存

void* malloc(size_t len) {struct _bucket_dir	*bdir;struct bucket_desc	*bdesc;void			*retval;/** First we search the bucket_dir to find the right bucket change* for this request.*/// 首先，我们搜索bucket_dir以找到此请求的正确bucket更改。for (bdir = bucket_dir; bdir->size; bdir++) //找到合适的大小的slab链表if (bdir->size >= len)break;if (!bdir->size) {printk("malloc called with impossibly large argument (%d)\n",len);return NULL;}/** Now we search for a bucket descriptor which has free space   现在我们搜索一个有空闲空间的bucket描述符*/CLI	/* Avoid race conditions    關中斷、避免竟態條件 */for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next)if (bdesc->freeptr)break;/** If we didn't find a bucket with free space, then we'll* allocate a new one. 如果我们没有找到一个有空闲空间的桶，那么我们会分配一个新的。*/if (!bdesc) {char		*cp;int		i;if (!free_bucket_desc)init_bucket_desc();bdesc = free_bucket_desc;free_bucket_desc = bdesc->next; // 還原爲0bdesc->refcnt = 0;bdesc->bucket_size = bdir->size;bdesc->page = bdesc->freeptr = (void *) (cp = (char *) get_free_page());if (!cp)return NULL;/* Set up the chain of free objects 设置空閒对象链*/for (i=P_SIZE/bdir->size; i > 1; i--) {char *next_block = cp + bdir->size;   // 计算下一个内存块的地址*(char**) cp = next_block; // 在 cp 所指向的内存块中存储下一个内存块的地址cp += bdir->size;}*((char **) cp) = 0;bdesc->next = bdir->chain; /* OK, link it in! */bdir->chain = bdesc;}retval = (void *) bdesc->freeptr;   // 下一个可供分配的bdesc->freeptr = *((void **) retval);bdesc->refcnt++;STI	/* OK, we're safe again */return(retval);
}

假设使用malloc申请一个8字节的内存:malloc(8):

• 1.搜索bucket_dir,找到第一个size > 8的_bucket_dir

    for (bdir = bucket_dir; bdir->size; bdir++) //找到合适的大小的slab链表if (bdir->size >= len)break;if (!bdir->size) {printk("malloc called with impossibly large argument (%d)\n",len);return NULL;}

16 > 8,bucket_dir[0]满足条件。

• 2.现在搜索一个有空闲空间的bucket描述符

    for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next)if (bdesc->freeptr)break;

• 3.如果没有找到一个有空闲空间的桶，那么会分配一个新的。

    if (!bdesc) {char		*cp;int		i;if (!free_bucket_desc)init_bucket_desc();bdesc = free_bucket_desc;free_bucket_desc = bdesc->next; // 還原爲0bdesc->refcnt = 0;bdesc->bucket_size = bdir->size;bdesc->page = bdesc->freeptr = (void *) (cp = (char *) get_free_page());if (!cp)return NULL;/* Set up the chain of free objects 设置空閒对象链*/for (i=P_SIZE/bdir->size; i > 1; i--) {char *next_block = cp + bdir->size;   // 计算下一个内存块的地址*(char**) cp = next_block; // 在 cp 所指向的内存块中存储下一个内存块的地址cp += bdir->size;}*((char **) cp) = 0;bdesc->next = bdir->chain; /* OK, link it in! */bdir->chain = bdesc;}

首先会判断 free_bucket_desc是否为0，如果为0说明未初始化，则需要进行初始化。当完成初始化之后，将free_bucket_desc赋值给桶描述符bdesc,并将free_bucket_desc重新赋值为bdesc->next，以此进行关联。并申请一个物理页get_free_page()与bdesc关联。再通过for (i=P_SIZE/bdir->size; i > 1; i--)设置空閒对象链。

• 4.返回空余内存retval，并将 bdesc->freeptr指向下一个可分配的。
  完整图示如下:
  

4.释放内存

• 1.计算此对象所在的页面

    page = (void *)  ((unsigned long) obj & 0xfffff000);

• 2.搜索该页面的bucket

    for (bdir = bucket_dir; bdir->size; bdir++) {prev = 0;/* If size is zero then this conditional is always false 如果大小为零，则此条件始终为false*/if (bdir->size < size)continue;for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) {if (bdesc->page == page)goto found;prev = bdesc;}}return;

• 3.释放内存，并将引用计数减一。

    *((void **)obj) = bdesc->freeptr;bdesc->freeptr = obj;bdesc->refcnt--;

• 4.如果引用计数为0，释放整个页面page。

    if (bdesc->refcnt == 0) {/** We need to make sure that prev is still accurate.  It* may not be, if someone rudely interrupted us....*/if ((prev && (prev->next != bdesc)) ||(!prev && (bdir->chain != bdesc)))for (prev = bdir->chain; prev; prev = prev->next)if (prev->next == bdesc)break;if (prev)prev->next = bdesc->next;else {if (bdir->chain != bdesc)return;bdir->chain = bdesc->next;}free_page( bdesc->page);bdesc->next = free_bucket_desc;free_bucket_desc = bdesc;}

完整图示如下：