Linux0.11分析之内存分配（结合uCos和VxWorks）

Linux0.11分析之内存分配（结合uCos和VxWorks）

看了Linux0.11的malloc和free函数实现，很有感触，存储桶的概念以前没有接触过，我觉得很经典，至少在结构和设计上，让人喜欢。至于性能等其它方面众多的考虑，我想结合目前熟悉的uCos和VxWorks来谈一谈。

首先看Linux0.11的存储桶原理及实现。桶很容易让人想到数组，先看下面几个数据结构。

下图这个是存储桶描述符数据结构定义，描述一个存储桶。从图片中各个字段的描述中就可以明白个大概了，page指向一个页面，指向的这个页面就是一个存储桶，这个页面（桶）被分为一个个相同大小的块，块大小由bucket_size给定，freeptr指向桶中空闲内存位置，即指向桶中空闲的块，可以猜到，桶中的块应该是由链表练起来了（这个很多系统中都这个实现），refcnt一个引用计数，即桶中分配出去的块数目，next字段显然就是让桶描述构成一个链条。

（声明，本文图来自《Linux0.11内核完全注释》） 《Linux 0.11内核完全注释(PDF+源码) 》下载在http://www.bkjia.net/thread-2080-1-1.html

下面再看一个存储桶目录数据结构，以及目录数组。

不同大小的目录指向不同存储桶大小的描述符，每种存储桶大小的描述符可以用链表链起来，这样内存分配就不会受到限制了。整体结构如下图。

现在存储桶原理已经很清晰了，最后再看一张空闲存储桶描述符链表结构指针。

刚开始malloc的时候，会用一页内存建立上面这样一个空闲存储桶描述符链表，这样，当需要用到存储桶描述符的时候（当为某一种大小的存储桶再申请一页内存供分配的时候就再需要一个存储桶描述符）或者存储桶描述符使用完毕的时候（当一个存储桶中所有块都被释放掉的时候，这个存储桶（页面）就需要被释放，这个存储桶描述符就需要回收）可以从链表中得到（释放）一个存储桶描述符。

最后说一点就是malloc的时候对于指定内存size，会搜索存储桶目录从小到大，直到找到第一个大于size的存储桶目录项，然后在这个存储桶目录项对应的存储桶中分配一块空间。