内存分配

传统的内存分配算法有两种，固定块大小分配法和块相连分配法：

固定块大小分配法（如ucos ii的内存管理）：分配速度快，算法实现简单，但由于只支持固定的一种或几种的固定块大小，使得内存空间利用率低，不够灵活，不适用于相对复杂的应用。
块相连分配法：通过指针链表的形式能够实现比较灵活的不同内存大小的分配，但经常需要遍历整个链表，导致耗时长，且容易产生碎片。

而RT-Thread的slab内存分配算法是上述两种算法的折中，其分两层：

底层是页分配器
上层是slab分配器

其页分配器的本质其实一个以page为单位块相连的分配算法，而其slab分配器则相当个支持72种大小的固定块分配法，所以RT-Thread的slab内存分配算法很好的兼顾了内存分配时的快速性、灵活性、不易产生碎片等要求。而其底层是已page为单位的分配，所以特别适合带虚拟内存交换机制的系统。

slab内存分配

底层的页分配器算法

涉及到的函数、变量、数据结构有：

void *rt_page_alloc(rt_size_t npages)   //分配页

void rt_page_free(void *addr, rt_size_t npages) //释放页

void rt_page_init(void* addr, rt_size_t npages) //页分配器初始化

void rt_system_heap_init(void *begin_addr, void* end_addr)  //内存管理初始化

struct rt_page_head //链表数据结构，正是通过这个数据结构将搜索的页形成一个链表

{

   struct rt_page_head *next;      /* next valid page */

   rt_size_t page;                 /* number of page  */

   char dummy[RT_MM_PAGE_SIZE - (sizeof(structrt_page_head*) + sizeof (rt_size_t))];

    };

   struct rt_page_head *rt_page_list;  //指向首个可用于分配的页

我们先从rt_system_heap_init入手，可以看到调用rt_page_init对页分配器进行了初始化。

下图可以看到，在每个连续的空间页的首地址收存放着一个数据结构struct rt_page_head，其元素page代表接下来有多少个连续的空间页可用于分配，next指向下一个与其不连续的空闲页。而全局的链表指针rt_page_list则指向首个可用于分配的空闲页。
下图还可以看到，RT-Thread的页分配器和常见的块相连分配法的原理一样，但它又有自己的特：
- 它是已页为单位的分配。
- 分配之后不需要花空间去记录这次分配的大小，因为上层的slab分配器使用页分配器时都是分配zone_size/4（zone_size一般为128K）大小个的页。
- 已分配的页的起始地址的数据内存管理程序已不再使用，完全可以交给申请者使用。

上层的slab分配器

首先来解释两个概念，一个是zone、另一个是chunk

Chunk：chunk是指一段固定大小的空间，slab分配器中共支持72种大小的chunk，那72种大小分别是8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128、144、160、176、192、208、224、240、256、288、320、352、384、416、448、480、512、576、640、704、770、834、898、962、1024、1152、1280、1408、1536、1664、1792、1920、2048、2304、2560、2816、3072、3328、3584、3840、4096、4608、5120、5632、6144、6656、7168、7680、8192、9216、10240、11264、12288、13312、14336、15360、16384（具体规律可参考zoneindex函数）。也就是说slab内存分配器只能分配上述大小的空间，如果过需要分配的空间不等上述大小，则会通过zoneindex函数自动寻找一个最接近的大小来代替，如果要分配的空间大于16K则，则直接分配一个4K大小对齐的空间。
Zone：每个zone一般都是128K，每个zone里包含着n个大小相同的chunk，所以就有72种类型的zone。如某个zone为128K，chunk属于512字节的类型，则说明它包含着128*1024/512个chunk。

接下来说一些主要的数据结构和全局变量

typedef struct slab_zone {

    rt_int32_t z_magic;    //没什么主要用途，可以不分析

    rt_int32_t z_nfree;    //该zone里有多少个可用于分配的chunk

    rt_int32_t z_nmax;     //该zone里拥有多少个chunk

    struct slab_zone *z_next;  //指向下一个同样类型的zone，并且所指向的zone中的chunk没有分配完，否则为NULL

    rt_uint8_t *z_baseptr;     //该zone第一个chunk的偏移，因为zone起始地址存放着这个数据结构

    rt_int32_t z_uindex;       //每次分配chunk就自加1，直到z_uindex+1= z_nmax,就会从z_freechunk中寻找可分配的chunk

    rt_int32_t z_chunksize;   //该zone中每个chunk的大小

    rt_int32_t z_zoneindex;   //对应的zoneindex，其实就是跟chunk的大小有关，大小为8时index为0，大小为16384时index为71

    slab_chunk *z_freechunk; //指向该zone中首个已被free掉的chunk，如果没有则为NULL

} slab_zone;

该数据结构存放在没有zone的起始空间中，描述了该zone的类型，该zone里面有哪些chunk可用于分配，哪些chunk被free了，下一个同类型的zone的地址等。

struct memusage {

rt_uint32_t type:2 ;                   //记录着对应空间分配的chunk是小于等于16K类型的还是大于16K的类型

rt_uint32_t size:30;    //如果是大于16K的类型，则记录具体分配的大小，否则记录该页在zone中的编号（因为每个zone包含32个页，也就是记录页号）

};

整个堆空间有多少个页就会开辟多少个这样的数据结构记录着对应页的状态。

zone_array[NZONES]

有72种类型的zone，所以就有上述的72的指针数组，分别指向对应类型的zone的首地址，然后这个zone数据结构又会指向下一个同类型的zone，所以全部同类型的zone就组成了一个链表。

接下来说说一下大概分配内存的过程：

首先初始化的时候zone_array[NZONES]会被全部置空，表明没有任何可用的zone，然后调用rt_malloc（200）申请200字节的空间，通过zoneindex函数后调整申请大小为208，且zoneindex为20，然后查询zone_array[20]发现为空，则说明208字节chunk大小类型的zone没有被建立或者没有一个包含空闲chunk的这样类型的zone。
然后就会建立一个新的且chunk大小为208字节的zone，通过rt_page_alloc 32个page实现，因为每个zone都为32*4K大小。
然后在所申请的页对应的memusage数组设置相应的标志及编号，然后初始化slab_zone数据结构，然后返回该zone内第一个chunk的地址，申请成功。