RT-Thread內(nèi)存管理算法源碼閱讀

之前對RT-Thread中如何解決

分配內(nèi)存時間的確定性問題
內(nèi)存碎片問題
資源受限的設(shè)備的內(nèi)存管理問題
比較好奇，所以查看了RT-Thread關(guān)于內(nèi)存管理算法的源碼，在此和官方文檔一起整理出來。

RT-Thread對于內(nèi)存管理主要有三種方式：小內(nèi)存管理算法、slab管理算法和memheap管理算法，分別在src/mem.c?、src/slab.c?和src/memheap.c?中。

小內(nèi)存管理算法
小內(nèi)存管理算法是一個簡單的內(nèi)存分配算法。初始時，它是一塊大的內(nèi)存。當(dāng)需要分配內(nèi)存塊時，將從這個大的內(nèi)存塊上分割出相匹配的內(nèi)存塊，然后把分割出來的空閑內(nèi)存塊還回給堆管理系統(tǒng)中。并有一個指針指向空閑內(nèi)存塊的第一個。

struct rt_small_mem
{
struct rt_memory parent; / < inherit from rt_memory /
rt_uint8_t heap_ptr; / < pointer to the heap */
struct rt_small_mem_item *heap_end;
struct rt_small_mem_item *lfree;
rt_size_t mem_size_aligned; /< aligned memory size */
};
每個內(nèi)存塊都包含一個管理用的數(shù)據(jù)頭，而通過這個數(shù)據(jù)頭和數(shù)據(jù)大小計算來偏移得到下一個內(nèi)存塊，本質(zhì)上是通過數(shù)組的方式。

每個內(nèi)存塊（不管是已分配的內(nèi)存塊還是空閑的內(nèi)存塊）都包含一個數(shù)據(jù)頭，其中包括：

1）magic：變數(shù)（或稱為幻數(shù)），它會被初始化成 0x1ea0（即英文單詞 heap），用于標(biāo)記這個內(nèi)存塊是一個內(nèi)存管理用的內(nèi)存數(shù)據(jù)塊；變數(shù)不僅僅用于標(biāo)識這個數(shù)據(jù)塊是一個內(nèi)存管理用的內(nèi)存數(shù)據(jù)塊，實質(zhì)也是一個內(nèi)存保護(hù)字：如果這個區(qū)域被改寫，那么也就意味著這塊內(nèi)存塊被非法改寫（正常情況下只有內(nèi)存管理器才會去碰這塊內(nèi)存）。

2）used：指示出當(dāng)前內(nèi)存塊是否已經(jīng)分配。

struct rt_small_mem_item
{
rt_ubase_t pool_ptr; / < small memory object addr /
#ifdef ARCH_CPU_64BIT
rt_uint32_t resv;
#endif / ARCH_CPU_64BIT /
rt_size_t next; / < next free item */
rt_size_t prev; / < prev free item /
#ifdef RT_USING_MEMTRACE
#ifdef ARCH_CPU_64BIT
rt_uint8_t thread[8]; / < thread name */
#else
rt_uint8_t thread[4]; /< thread name /
#endif / ARCH_CPU_64BIT /
#endif / RT_USING_MEMTRACE */
};
內(nèi)存管理算法的初始化和刪除比較簡單，主要是對rt_small_mem??和第一個內(nèi)存塊的初始化，以及對內(nèi)核對象的操作。

內(nèi)存管理的表現(xiàn)主要體現(xiàn)在內(nèi)存的分配與釋放上，小型內(nèi)存管理算法可以用以下例子體現(xiàn)出來。

如下圖所示的內(nèi)存分配情況，空閑鏈表指針 lfree 初始指向 32 字節(jié)的內(nèi)存塊。當(dāng)用戶線程要再分配一個 64 字節(jié)的內(nèi)存塊時，但此 lfree 指針指向的內(nèi)存塊只有 32 字節(jié)并不能滿足要求，內(nèi)存管理器會繼續(xù)尋找下一內(nèi)存塊，當(dāng)找到再下一塊內(nèi)存塊，128 字節(jié)時，它滿足分配的要求。因為這個內(nèi)存塊比較大，分配器將把此內(nèi)存塊進(jìn)行拆分，余下的內(nèi)存塊（52 字節(jié)）繼續(xù)留在 lfree 鏈表中，如下圖分配 64 字節(jié)后的鏈表結(jié)構(gòu)所示。

另外，在每次分配內(nèi)存塊前，都會留出 12 字節(jié)數(shù)據(jù)頭用于 magic、used 信息及鏈表節(jié)點使用。返回給應(yīng)用的地址實際上是這塊內(nèi)存塊 12 字節(jié)以后的地址，前面的 12 字節(jié)數(shù)據(jù)頭是用戶永遠(yuǎn)不應(yīng)該碰的部分（注：12 字節(jié)數(shù)據(jù)頭長度會與系統(tǒng)對齊差異而有所不同）。

總的來說，大致有以下幾步：

首先是基本條件的判定和操作，如內(nèi)存對齊和大小等

遍歷空閑的內(nèi)存塊鏈表

這里本質(zhì)上不是鏈表，而是數(shù)組
所以是通過計算偏移完成遍歷的
速度十分快
如果內(nèi)存塊足夠大，那就進(jìn)行切割

否則就不切割
然后更新內(nèi)存的基本信息
更新當(dāng)前空閑內(nèi)存塊鏈表（數(shù)組）的頭結(jié)點
void *rt_smem_alloc(rt_smem_t m, rt_size_t size)
{
rt_size_t ptr, ptr2;
struct rt_small_mem_item *mem, *mem2;
struct rt_small_mem *small_mem;
if (size == 0)
return RT_NULL;
RT_ASSERT(m != RT_NULL);
RT_ASSERT(rt_object_get_type(&m->parent) == RT_Object_Class_Memory);
RT_ASSERT(rt_object_is_systemobject(&m->parent));
if (size != RT_ALIGN(size, RT_ALIGN_SIZE))
{
RT_DEBUG_LOG(RT_DEBUG_MEM, ("malloc size %d, but align to %dn",
size, RT_ALIGN(size, RT_ALIGN_SIZE)));
}
else
{
RT_DEBUG_LOG(RT_DEBUG_MEM, ("malloc size %dn", size));
}
small_mem = (struct rt_small_mem )m;
/ alignment size /
size = RT_ALIGN(size, RT_ALIGN_SIZE);
/ every data block must be at least MIN_SIZE_ALIGNED long */
if (size < MIN_SIZE_ALIGNED)
size = MIN_SIZE_ALIGNED;
if (size > small_mem->mem_size_aligned)
{
RT_DEBUG_LOG(RT_DEBUG_MEM, ("no memoryn"));
return RT_NULL;
}
for (ptr = (rt_uint8_t *)small_mem->lfree - small_mem->heap_ptr;
ptr <= small_mem->mem_size_aligned - size;
ptr = ((struct rt_small_mem_item *)&small_mem->heap_ptr[ptr])->next)
{
mem = (struct rt_small_mem_item )&small_mem->heap_ptr[ptr];
if ((!MEM_ISUSED(mem)) && (mem->next - (ptr + SIZEOF_STRUCT_MEM)) >= size)
{
/ mem is not used and at least perfect fit is possible:

mem->next - (ptr + SIZEOF_STRUCT_MEM) gives us the 'user data size' of mem /
if (mem->next - (ptr + SIZEOF_STRUCT_MEM) >=
(size + SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED))
{
/ (in addition to the above, we test if another struct rt_small_mem_item (SIZEOF_STRUCT_MEM) containing
at least MIN_SIZE_ALIGNED of data also fits in the 'user data space' of 'mem')
-> split large block, create empty remainder,
remainder must be large enough to contain MIN_SIZE_ALIGNED data: if
mem->next - (ptr + (2*SIZEOF_STRUCT_MEM)) == size,
struct rt_small_mem_item would fit in but no data between mem2 and mem2->next
@todo we could leave out MIN_SIZE_ALIGNED. We would create an empty

region that couldn't hold data, but when mem->next gets freed,
the 2 regions would be combined, resulting in more free memory

/
ptr2 = ptr + SIZEOF_STRUCT_MEM + size;
/ create mem2 struct */
mem2 = (struct rt_small_mem_item )&small_mem->heap_ptr[ptr2];
mem2->pool_ptr = MEM_FREED();
mem2->next = mem->next;
mem2->prev = ptr;
#ifdef RT_USING_MEMTRACE
rt_smem_setname(mem2, " ");
#endif / RT_USING_MEMTRACE /
/ and insert it between mem and mem->next */
mem->next = ptr2;
if (mem2->next != small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM)
{
((struct rt_small_mem_item )&small_mem->heap_ptr[mem2->next])->prev = ptr2;
}
small_mem->parent.used += (size + SIZEOF_STRUCT_MEM);
if (small_mem->parent.max < small_mem->parent.used)
small_mem->parent.max = small_mem->parent.used;
}
else
{
/ (a mem2 struct does no fit into the user data space of mem and mem->next will always
be used at this point: if not we have 2 unused structs in a row, plug_holes should have

take care of this).
-> near fit or excact fit: do not split, no mem2 creation
also can't move mem->next directly behind mem, since mem->next
will always be used at this point!
*/
small_mem->parent.used += mem->next - ((rt_uint8_t )mem - small_mem->heap_ptr);
if (small_mem->parent.max < small_mem->parent.used)
small_mem->parent.max = small_mem->parent.used;
}
/ set small memory object /
mem->pool_ptr = MEM_USED();
#ifdef RT_USING_MEMTRACE
if (rt_thread_self())
rt_smem_setname(mem, rt_thread_self()->parent.name);
else
rt_smem_setname(mem, "NONE");
#endif / RT_USING_MEMTRACE /
if (mem == small_mem->lfree)
{
/ Find next free block after mem and update lowest free pointer */
while (MEM_ISUSED(small_mem->lfree) && small_mem->lfree != small_mem->heap_end)
small_mem->lfree = (struct rt_small_mem_item *)&small_mem->heap_ptr[small_mem->lfree->next];
RT_ASSERT(((small_mem->lfree == small_mem->heap_end) || (!MEM_ISUSED(small_mem->lfree))));
}
RT_ASSERT((rt_ubase_t)mem + SIZEOF_STRUCT_MEM + size <= (rt_ubase_t)small_mem->heap_end);
RT_ASSERT((rt_ubase_t)((rt_uint8_t *)mem + SIZEOF_STRUCT_MEM) % RT_ALIGN_SIZE == 0);
RT_ASSERT((((rt_ubase_t)mem) & (RT_ALIGN_SIZE - 1)) == 0);
RT_DEBUG_LOG(RT_DEBUG_MEM,
("allocate memory at 0x%x, size: %dn",
(rt_ubase_t)((rt_uint8_t *)mem + SIZEOF_STRUCT_MEM),
(rt_ubase_t)(mem->next - ((rt_uint8_t )mem - small_mem->heap_ptr))));
/ return the memory data except mem struct */
return (rt_uint8_t *)mem + SIZEOF_STRUCT_MEM;
}
}
return RT_NULL;
}
釋放時則是相反的過程，但分配器會查看前后相鄰的內(nèi)存塊是否空閑，如果空閑則合并成一個大的空閑內(nèi)存塊。

主要就是把要釋放的內(nèi)存塊放入空閑內(nèi)存塊鏈表

調(diào)用plug_holes?合并空閑內(nèi)存塊

只會判斷前后內(nèi)存塊，保證了效率
void rt_smem_free(void *rmem)
{
struct rt_small_mem_item *mem;
struct rt_small_mem small_mem;
if (rmem == RT_NULL)
return;
RT_ASSERT((((rt_ubase_t)rmem) & (RT_ALIGN_SIZE - 1)) == 0);
/ Get the corresponding struct rt_small_mem_item ... */
mem = (struct rt_small_mem_item *)((rt_uint8_t )rmem - SIZEOF_STRUCT_MEM);
/ ... which has to be in a used state ... */
small_mem = MEM_POOL(mem);
RT_ASSERT(small_mem != RT_NULL);
RT_ASSERT(MEM_ISUSED(mem));
RT_ASSERT(rt_object_get_type(&small_mem->parent.parent) == RT_Object_Class_Memory);
RT_ASSERT(rt_object_is_systemobject(&small_mem->parent.parent));
RT_ASSERT((rt_uint8_t *)rmem >= (rt_uint8_t *)small_mem->heap_ptr &&
(rt_uint8_t *)rmem < (rt_uint8_t *)small_mem->heap_end);
RT_ASSERT(MEM_POOL(&small_mem->heap_ptr[mem->next]) == small_mem);
RT_DEBUG_LOG(RT_DEBUG_MEM,
("release memory 0x%x, size: %dn",
(rt_ubase_t)rmem,
(rt_ubase_t)(mem->next - ((rt_uint8_t )mem - small_mem->heap_ptr))));
/ ... and is now unused. /
mem->pool_ptr = MEM_FREED();
#ifdef RT_USING_MEMTRACE
rt_smem_setname(mem, " ");
#endif / RT_USING_MEMTRACE /
if (mem < small_mem->lfree)
{
/ the newly freed struct is now the lowest */
small_mem->lfree = mem;
}
small_mem->parent.used -= (mem->next - ((rt_uint8_t )mem - small_mem->heap_ptr));
/ finally, see if prev or next are free also */
plug_holes(small_mem, mem);
}
static void plug_holes(struct rt_small_mem *m, struct rt_small_mem_item *mem)
{
struct rt_small_mem_item *nmem;
struct rt_small_mem_item *pmem;
RT_ASSERT((rt_uint8_t *)mem >= m->heap_ptr);
RT_ASSERT((rt_uint8_t *)mem < (rt_uint8_t )m->heap_end);
/ plug hole forward */
nmem = (struct rt_small_mem_item *)&m->heap_ptr[mem->next];
if (mem != nmem && !MEM_ISUSED(nmem) &&
(rt_uint8_t *)nmem != (rt_uint8_t )m->heap_end)
{
/ if mem->next is unused and not end of m->heap_ptr,

combine mem and mem->next
*/
if (m->lfree == nmem)
{
m->lfree = mem;
}
nmem->pool_ptr = 0;
mem->next = nmem->next;
((struct rt_small_mem_item *)&m->heap_ptr[nmem->next])->prev = (rt_uint8_t )mem - m->heap_ptr;
}
/ plug hole backward */
pmem = (struct rt_small_mem_item )&m->heap_ptr[mem->prev];
if (pmem != mem && !MEM_ISUSED(pmem))
{
/ if mem->prev is unused, combine mem and mem->prev */
if (m->lfree == mem)
{
m->lfree = pmem;
}
mem->pool_ptr = 0;
pmem->next = mem->next;
((struct rt_small_mem_item *)&m->heap_ptr[mem->next])->prev = (rt_uint8_t *)pmem - m->heap_ptr;
}
}

slab 管理算法
RT-Thread 的 slab 分配器實現(xiàn)是純粹的緩沖型的內(nèi)存池算法。slab 分配器會根據(jù)對象的大小分成多個區(qū)（zone），也可以看成每類對象有一個內(nèi)存池，如下圖所示：

一個 zone 的大小在 32K 到 128K 字節(jié)之間，分配器會在堆初始化時根據(jù)堆的大小自動調(diào)整。系統(tǒng)中的 zone 最多包括 72 種對象，一次最大能夠分配 16K 的內(nèi)存空間，如果超出了 16K 那么直接從頁分配器中分配。每個 zone 上分配的內(nèi)存塊大小是固定的，能夠分配相同大小內(nèi)存塊的 zone 會鏈接在一個鏈表中，而 72 種對象的 zone 鏈表則放在一個數(shù)組（zone_array[]）中統(tǒng)一管理。

整個slab由rt_slab?進(jìn)行管理，zone_array?存放著所有zone，zone_free?存放著空閑的zone。每個zone當(dāng)中的基本單位又是rt_slab_chunk?，作為最低一級內(nèi)存分配單位。

struct rt_slab
{
struct rt_memory parent; / *< inherit from rt_memory /
rt_ubase_t heap_start; / < memory start address */
rt_ubase_t heap_end; / **< memory end address */
struct rt_slab_memusage *memusage;
struct rt_slab_zone zone_array[RT_SLAB_NZONES]; / linked list of zones NFree > 0 */
struct rt_slab_zone zone_free; / whole zones that have become free /
rt_uint32_t zone_free_cnt;
rt_uint32_t zone_size;
rt_uint32_t zone_limit;
rt_uint32_t zone_page_cnt;
struct rt_slab_page page_list;
};
struct rt_slab_zone
{
rt_uint32_t z_magic; / < magic number for sanity check */
rt_uint32_t z_nfree; / *< total free chunks / ualloc space in zone /
rt_uint32_t z_nmax; / < maximum free chunks */
struct rt_slab_zone *z_next; / **< zoneary[] link if z_nfree non-zero /
rt_uint8_t z_baseptr; / < pointer to start of chunk array */
rt_uint32_t z_uindex; / *< current initial allocation index /
rt_uint32_t z_chunksize; / < chunk size for validation */
rt_uint32_t z_zoneindex; / **< zone index /
struct rt_slab_chunk z_freechunk; / < free chunk list */
};
struct rt_slab_chunk
{
struct rt_slab_chunk *c_next;
};
其中在初始化時會初始化page_list?，相當(dāng)于slab的內(nèi)存池，每次分配都會從這個內(nèi)存池當(dāng)中進(jìn)行分配。其中關(guān)于page的初始化、分配和釋放和小內(nèi)存管理算法是類似的，本質(zhì)上都是使用數(shù)組和計算偏移的方式。具體可見rt_slab_page_init?、rt_slab_page_alloc?和rt_slab_page_free?。

struct rt_slab_page
{
struct rt_slab_page *next; / *< next valid page /
rt_size_t page; / < number of page /
/ dummy */
char dummy[RT_MM_PAGE_SIZE - (sizeof(struct rt_slab_page *) + sizeof(rt_size_t))];
};
slab的初始化操作比較簡單，仍然主要是對rt_slab??結(jié)構(gòu)進(jìn)行初始化，以及初始化page_list??以及memusage??，memusage主要是用來標(biāo)記page的大小以及類型。

內(nèi)存分配器當(dāng)中最主要的就是兩種操作：

（1）內(nèi)存分配

假設(shè)分配一個 32 字節(jié)的內(nèi)存，slab 內(nèi)存分配器會先按照 32 字節(jié)的值，從 zone array 鏈表表頭數(shù)組中找到相應(yīng)的 zone 鏈表。如果這個鏈表是空的，則向頁分配器分配一個新的 zone，然后從 zone 中返回第一個空閑內(nèi)存塊。如果鏈表非空，則這個 zone 鏈表中的第一個 zone 節(jié)點必然有空閑塊存在（否則它就不應(yīng)該放在這個鏈表中），那么就取相應(yīng)的空閑塊。如果分配完成后，zone 中所有空閑內(nèi)存塊都使用完畢，那么分配器需要把這個 zone 節(jié)點從鏈表中刪除。

總的來說，主要完成以下操作：

首先對于特大內(nèi)存塊（size >= slab->zone_limit）會單獨進(jìn)行處理，不分配進(jìn)zone

其次就是計算當(dāng)前size應(yīng)該放入哪個zone，由zoneindex?進(jìn)行計算

如果這個zone存在

如果zone加上此次操作即會滿，則移除出zone_array
如果當(dāng)前chunk還沒達(dá)到最大值，則直接分配一個chunk
否則就從freechunk當(dāng)中進(jìn)行分配
最后更新內(nèi)存信息直接返回
如果不存在這個zone

如果存在zone_free，則直接分配出一個

如果不存在zone_free，zone_free本質(zhì)上是還未使用的zone

分配一個新的page并設(shè)置memusage
初始化這個zone，然后分配一個chunk
void *rt_slab_alloc(rt_slab_t m, rt_size_t size)
{
struct rt_slab_zone *z;
rt_int32_t zi;
struct rt_slab_chunk *chunk;
struct rt_slab_memusage *kup;
struct rt_slab *slab = (struct rt_slab )m;
/ zero size, return RT_NULL /
if (size == 0)
return RT_NULL;
/
Handle large allocations directly. There should not be very many of

these so performance is not a big issue.
/
if (size >= slab->zone_limit)
{
size = RT_ALIGN(size, RT_MM_PAGE_SIZE);
chunk = rt_slab_page_alloc(m, size >> RT_MM_PAGE_BITS);
if (chunk == RT_NULL)
return RT_NULL;
/ set kup /
kup = btokup(chunk);
kup->type = PAGE_TYPE_LARGE;
kup->size = size >> RT_MM_PAGE_BITS;
RT_DEBUG_LOG(RT_DEBUG_SLAB,
("alloc a large memory 0x%x, page cnt %d, kup %dn",
size,
size >> RT_MM_PAGE_BITS,
((rt_ubase_t)chunk - slab->heap_start) >> RT_MM_PAGE_BITS));
/ mem stat /
slab->parent.used += size;
if (slab->parent.used > slab->parent.max)
slab->parent.max = slab->parent.used;
return chunk;
}
/
Attempt to allocate out of an existing zone. First try the free list,
then allocate out of unallocated space. If we find a good zone move
it to the head of the list so later allocations find it quickly
(we might have thousands of zones in the list).

Note: zoneindex() will panic of size is too large.
/
zi = zoneindex(&size);
RT_ASSERT(zi < RT_SLAB_NZONES);
RT_DEBUG_LOG(RT_DEBUG_SLAB, ("try to alloc 0x%x on zone: %dn", size, zi));
if ((z = slab->zone_array[zi]) != RT_NULL)
{
RT_ASSERT(z->z_nfree > 0);
/ Remove us from the zone_array[] when we become full /
if (--z->z_nfree == 0)
{
slab->zone_array[zi] = z->z_next;
z->z_next = RT_NULL;
}
/

No chunks are available but nfree said we had some memory, so

it must be available in the never-before-used-memory area
governed by uindex. The consequences are very serious if our zone
got corrupted so we use an explicit rt_kprintf rather then a KASSERT.
*/
if (z->z_uindex + 1 != z->z_nmax)
{
z->z_uindex = z->z_uindex + 1;
chunk = (struct rt_slab_chunk )(z->z_baseptr + z->z_uindex * size);
}
else
{
/ find on free chunk list /
chunk = z->z_freechunk;
/ remove this chunk from list /
z->z_freechunk = z->z_freechunk->c_next;
}
/ mem stats /
slab->parent.used += z->z_chunksize;
if (slab->parent.used > slab->parent.max)
slab->parent.max = slab->parent.used;
return chunk;
}
/
If all zones are exhausted we need to allocate a new zone for this
index.

At least one subsystem, the tty code (see CROUND) expects power-of-2
allocations to be power-of-2 aligned. We maintain compatibility by
adjusting the base offset below.
/
{
rt_uint32_t off;
if ((z = slab->zone_free) != RT_NULL)
{
/ remove zone from free zone list /
slab->zone_free = z->z_next;
-- slab->zone_free_cnt;
}
else
{
/ allocate a zone from page /
z = rt_slab_page_alloc(m, slab->zone_size / RT_MM_PAGE_SIZE);
if (z == RT_NULL)
{
return RT_NULL;
}
RT_DEBUG_LOG(RT_DEBUG_SLAB, ("alloc a new zone: 0x%xn",
(rt_ubase_t)z));
/ set message usage /
for (off = 0, kup = btokup(z); off < slab->zone_page_cnt; off ++)
{
kup->type = PAGE_TYPE_SMALL;
kup->size = off;
kup ++;
}
}
/ clear to zero /
rt_memset(z, 0, sizeof(struct rt_slab_zone));
/ offset of slab zone struct in zone /
off = sizeof(struct rt_slab_zone);
/
Guarentee power-of-2 alignment for power-of-2-sized chunks.
Otherwise just 8-byte align the data.
*/
if ((size | (size - 1)) + 1 == (size << 1))
off = (off + size - 1) & ~(size - 1);
else
off = (off + MIN_CHUNK_MASK) & ~MIN_CHUNK_MASK;
z->z_magic = ZALLOC_SLAB_MAGIC;
z->z_zoneindex = zi;
z->z_nmax = (slab->zone_size - off) / size;
z->z_nfree = z->z_nmax - 1;
z->z_baseptr = (rt_uint8_t *)z + off;
z->z_uindex = 0;
z->z_chunksize = size;
chunk = (struct rt_slab_chunk )(z->z_baseptr + z->z_uindex * size);
/ link to zone array /
z->z_next = slab->zone_array[zi];
slab->zone_array[zi] = z;
/ mem stats */
slab->parent.used += z->z_chunksize;
if (slab->parent.used > slab->parent.max)
slab->parent.max = slab->parent.used;
}
return chunk;
}
RTM_EXPORT(rt_slab_alloc);
（2）內(nèi)存釋放

分配器需要找到內(nèi)存塊所在的 zone 節(jié)點，然后把內(nèi)存塊鏈接到 zone 的空閑內(nèi)存塊鏈表中。如果此時 zone 的空閑鏈表指示出 zone 的所有內(nèi)存塊都已經(jīng)釋放，即 zone 是完全空閑的，那么當(dāng) zone 鏈表中全空閑 zone 達(dá)到一定數(shù)目后，系統(tǒng)就會把這個全空閑的 zone 釋放到頁面分配器中去。

首先找到當(dāng)前要釋放的內(nèi)存塊的memusage

如果是前面所述的特大內(nèi)存，那就直接使用rt_slab_page_free?釋放。
根據(jù)memuage計算偏移找到zone和chunk，將chunk放入freechunk中，下次直接使用

如果當(dāng)前的zone是完全空閑的

移除這個zone，并更新rt_slab?的信息
并釋放page
void rt_slab_free(rt_slab_t m, void *ptr)
{
struct rt_slab_zone *z;
struct rt_slab_chunk *chunk;
struct rt_slab_memusage *kup;
struct rt_slab *slab = (struct rt_slab )m;
/ free a RT_NULL pointer /
if (ptr == RT_NULL)
return ;
/ get memory usage /
#if RT_DEBUG_SLAB
{
rt_ubase_t addr = ((rt_ubase_t)ptr & ~RT_MM_PAGE_MASK);
RT_DEBUG_LOG(RT_DEBUG_SLAB,
("free a memory 0x%x and align to 0x%x, kup index %dn",
(rt_ubase_t)ptr,
(rt_ubase_t)addr,
((rt_ubase_t)(addr) - slab->heap_start) >> RT_MM_PAGE_BITS));
}
#endif / RT_DEBUG_SLAB /
kup = btokup((rt_ubase_t)ptr & ~RT_MM_PAGE_MASK);
/ release large allocation /
if (kup->type == PAGE_TYPE_LARGE)
{
rt_ubase_t size;
/ clear page counter /
size = kup->size;
kup->size = 0;
/ mem stats /
slab->parent.used -= size * RT_MM_PAGE_SIZE;
RT_DEBUG_LOG(RT_DEBUG_SLAB,
("free large memory block 0x%x, page count %dn",
(rt_ubase_t)ptr, size));
/ free this page /
rt_slab_page_free(m, ptr, size);
return;
}
/ zone case. get out zone. */
z = (struct rt_slab_zone *)(((rt_ubase_t)ptr & ~RT_MM_PAGE_MASK) -
kup->size * RT_MM_PAGE_SIZE);
RT_ASSERT(z->z_magic == ZALLOC_SLAB_MAGIC);
chunk = (struct rt_slab_chunk )ptr;
chunk->c_next = z->z_freechunk;
z->z_freechunk = chunk;
/ mem stats /
slab->parent.used -= z->z_chunksize;
/

• Bump the number of free chunks. If it becomes non-zero the zone
• must be added back onto the appropriate list.
  /
  if (z->z_nfree++ == 0)
  {
  z->z_next = slab->zone_array[z->z_zoneindex];
  slab->zone_array[z->z_zoneindex] = z;
  }
  /
• If the zone becomes totally free, and there are other zones we
• can allocate from, move this zone to the FreeZones list. Since
• this code can be called from an IPI callback, do NOT try to mess
• with kernel_map here. Hysteresis will be performed at malloc() time.
  */
  if (z->z_nfree == z->z_nmax &&
  (z->z_next || slab->zone_array[z->z_zoneindex] != z))
  {
  struct rt_slab_zone *pz;
  RT_DEBUG_LOG(RT_DEBUG_SLAB, ("free zone 0x%xn",
  (rt_ubase_t)z, z->z_zoneindex));
  / remove zone from zone array list */
  for (pz = &slab->zone_array[z->z_zoneindex]; z != *pz; pz = &(*pz)->z_next)
  ;
  pz = z->z_next;
  / reset zone /
  z->z_magic = RT_UINT32_MAX;
  / insert to free zone list /
  z->z_next = slab->zone_free;
  slab->zone_free = z;
  ++ slab->zone_free_cnt;
  / release zone to page allocator /
  if (slab->zone_free_cnt > ZONE_RELEASE_THRESH)
  {
  register rt_uint32_t i;
  z = slab->zone_free;
  slab->zone_free = z->z_next;
  -- slab->zone_free_cnt;
  / set message usage /
  for (i = 0, kup = btokup(z); i < slab->zone_page_cnt; i ++)
  {
  kup->type = PAGE_TYPE_FREE;
  kup->size = 0;
  kup ++;
  }
  / release pages */
  rt_slab_page_free(m, z, slab->zone_size / RT_MM_PAGE_SIZE);
  return;
  }
  }
  }
  memheap 管理算法
  ?memheap?管理算法適用于系統(tǒng)含有多個地址可不連續(xù)的內(nèi)存堆。使用memheap?內(nèi)存管理可以簡化系統(tǒng)存在多個內(nèi)存堆時的使用：當(dāng)系統(tǒng)中存在多個內(nèi)存堆的時候，用戶只需要在系統(tǒng)初始化時將多個所需的memheap?初始化，并開啟memheap?功能就可以很方便地把多個memheap?（地址可不連續(xù)）粘合起來用于系統(tǒng)的 heap 分配。

首先，RT-Thread的實現(xiàn)用rt_memheap?來表示一個memheap?，使用rt_memheap_item?來表示堆中的一個節(jié)點或者說一個內(nèi)存塊。

除了包含基本信息外，rt_memheap?當(dāng)中主要包含著一個鏈接所有內(nèi)存塊的block_list?和鏈接所有空閑內(nèi)存塊的free_list?，而rt_memheap_item?也主要圍繞這兩個結(jié)構(gòu)，主要是指向前后兩個塊和前后兩個空閑塊。此外，rt_memheap?還有用來處理并發(fā)的信號量。

struct rt_memheap_item
{
rt_uint32_t magic; / **< magic number for memheap /
struct rt_memheap pool_ptr; / < point of pool */
struct rt_memheap_item *next; / **< next memheap item /
struct rt_memheap_item prev; / < prev memheap item */
struct rt_memheap_item next_free; / < next free memheap item /
struct rt_memheap_item prev_free; / < prev free memheap item */
#ifdef RT_USING_MEMTRACE
rt_uint8_t owner_thread_name[4]; /< owner thread name /
#endif / RT_USING_MEMTRACE /
};
/

Base structure of memory heap object
*/
struct rt_memheap
{
struct rt_object parent; / **< inherit from rt_object /
void start_addr; / < pool start address and size */
rt_size_t pool_size; / *< pool size /
rt_size_t available_size; / < available size */
rt_size_t max_used_size; / **< maximum allocated size /
struct rt_memheap_item block_list; / < used block list */
struct rt_memheap_item *free_list; / *< free block list /
struct rt_memheap_item free_header; / < free block list header */
struct rt_semaphore lock; / *< semaphore lock /
rt_bool_t locked; / < External lock mark */
};
memheap 工作機(jī)制如下圖所示，首先將多塊內(nèi)存加入 memheap_item 鏈表進(jìn)行粘合。當(dāng)分配內(nèi)存塊時，會先從默認(rèn)內(nèi)存堆去分配內(nèi)存，當(dāng)分配不到時會查找 memheap_item 鏈表，嘗試從其他的內(nèi)存堆上分配內(nèi)存塊。應(yīng)用程序不用關(guān)心當(dāng)前分配的內(nèi)存塊位于哪個內(nèi)存堆上，就像是在操作一個內(nèi)存堆。

這在RT-Thread真正的實現(xiàn)當(dāng)中，主要是依靠內(nèi)核對象完成的。首先heap參數(shù)是由上層封裝的另一個接口傳入的系統(tǒng)heap（在后面會講解），所以實現(xiàn)多內(nèi)存堆主要依靠遍歷內(nèi)核對象（memheap?在初始化會加入內(nèi)存對象鏈表）獲取每一個內(nèi)存堆并嘗試內(nèi)存分配。

具體可見src/memheap.c?的_memheap_alloc?函數(shù)

對于memheap?的初始化和前兩個管理算法是類似的，都比較簡單，主要是對rt_memheap?的初始化和block_list?和free_list?的初始化，以及對內(nèi)核對象的操作。

其中主要的同樣還是內(nèi)存的分配以及釋放。

內(nèi)存分配的主要操作是：

如果當(dāng)前整個memheap?的可用內(nèi)存都不夠大，則直接返回RT_NULL?交由上層處理

首先先遍歷free_list?找到合適大小的內(nèi)存塊

如果這個內(nèi)存塊的大小超過了一個item?結(jié)構(gòu)+要求分配的內(nèi)存大小+最小可分配的內(nèi)存塊大小

那么就切割這個內(nèi)存塊，主要就是對prev?和next?指針的鏈表操作。在free_list?中刪除新分配的內(nèi)存塊，并加入切割出來的內(nèi)存塊
并且會更新當(dāng)前堆的信息
如果內(nèi)存塊大小不足的話，只會在free_list?中刪除新分配的內(nèi)存塊
void *rt_memheap_alloc(struct rt_memheap *heap, rt_size_t size)
{
rt_err_t result;
rt_size_t free_size;
struct rt_memheap_item header_ptr;
RT_ASSERT(heap != RT_NULL);
RT_ASSERT(rt_object_get_type(&heap->parent) == RT_Object_Class_MemHeap);
/ align allocated size */
size = RT_ALIGN(size, RT_ALIGN_SIZE);
if (size < RT_MEMHEAP_MINIALLOC)
size = RT_MEMHEAP_MINIALLOC;
RT_DEBUG_LOG(RT_DEBUG_MEMHEAP, ("allocate %d on heap:%8.s",
size, RT_NAME_MAX, heap->parent.name));
if (size < heap->available_size)
{
/ search on free list /
free_size = 0;
/ lock memheap /
if (heap->locked == RT_FALSE)
{
result = rt_sem_take(&(heap->lock), RT_WAITING_FOREVER);
if (result != RT_EOK)
{
rt_set_errno(result);
return RT_NULL;
}
}
/ get the first free memory block /
header_ptr = heap->free_list->next_free;
while (header_ptr != heap->free_list && free_size < size)
{
/ get current freed memory block size /
free_size = MEMITEM_SIZE(header_ptr);
if (free_size < size)
{
/ move to next free memory block /
header_ptr = header_ptr->next_free;
}
}
/ determine if the memory is available. /
if (free_size >= size)
{
/ a block that satisfies the request has been found. /
/ determine if the block needs to be split. */
if (free_size >= (size + RT_MEMHEAP_SIZE + RT_MEMHEAP_MINIALLOC))
{
struct rt_memheap_item new_ptr;
/ split the block. */
new_ptr = (struct rt_memheap_item *)
(((rt_uint8_t )header_ptr) + size + RT_MEMHEAP_SIZE);
RT_DEBUG_LOG(RT_DEBUG_MEMHEAP,
("split: block[0x%08x] nextm[0x%08x] prevm[0x%08x] to new[0x%08x]n",
header_ptr,
header_ptr->next,
header_ptr->prev,
new_ptr));
/ mark the new block as a memory block and freed. /
new_ptr->magic = (RT_MEMHEAP_MAGIC | RT_MEMHEAP_FREED);
/ put the pool pointer into the new block. /
new_ptr->pool_ptr = heap;
#ifdef RT_USING_MEMTRACE
rt_memset(new_ptr->owner_thread_name, ' ', sizeof(new_ptr->owner_thread_name));
#endif / RT_USING_MEMTRACE /
/ break down the block list /
new_ptr->prev = header_ptr;
new_ptr->next = header_ptr->next;
header_ptr->next->prev = new_ptr;
header_ptr->next = new_ptr;
/ remove header ptr from free list /
header_ptr->next_free->prev_free = header_ptr->prev_free;
header_ptr->prev_free->next_free = header_ptr->next_free;
header_ptr->next_free = RT_NULL;
header_ptr->prev_free = RT_NULL;
/ insert new_ptr to free list /
new_ptr->next_free = heap->free_list->next_free;
new_ptr->prev_free = heap->free_list;
heap->free_list->next_free->prev_free = new_ptr;
heap->free_list->next_free = new_ptr;
RT_DEBUG_LOG(RT_DEBUG_MEMHEAP, ("new ptr: next_free 0x%08x, prev_free 0x%08xn",
new_ptr->next_free,
new_ptr->prev_free));
/ decrement the available byte count. /
heap->available_size = heap->available_size -
size -
RT_MEMHEAP_SIZE;
if (heap->pool_size - heap->available_size > heap->max_used_size)
heap->max_used_size = heap->pool_size - heap->available_size;
}
else
{
/ decrement the entire free size from the available bytes count. /
heap->available_size = heap->available_size - free_size;
if (heap->pool_size - heap->available_size > heap->max_used_size)
heap->max_used_size = heap->pool_size - heap->available_size;
/ remove header_ptr from free list /
RT_DEBUG_LOG(RT_DEBUG_MEMHEAP,
("one block: block[0x%08x], next_free 0x%08x, prev_free 0x%08xn",
header_ptr,
header_ptr->next_free,
header_ptr->prev_free));
header_ptr->next_free->prev_free = header_ptr->prev_free;
header_ptr->prev_free->next_free = header_ptr->next_free;
header_ptr->next_free = RT_NULL;
header_ptr->prev_free = RT_NULL;
}
/ Mark the allocated block as not available. /
header_ptr->magic = (RT_MEMHEAP_MAGIC | RT_MEMHEAP_USED);
#ifdef RT_USING_MEMTRACE
if (rt_thread_self())
rt_memcpy(header_ptr->owner_thread_name, rt_thread_self()->parent.name, sizeof(header_ptr->owner_thread_name));
else
rt_memcpy(header_ptr->owner_thread_name, "NONE", sizeof(header_ptr->owner_thread_name));
#endif / RT_USING_MEMTRACE /
if (heap->locked == RT_FALSE)
{
/ release lock /
rt_sem_release(&(heap->lock));
}
/ Return a memory address to the caller. */
RT_DEBUG_LOG(RT_DEBUG_MEMHEAP,
("alloc mem: memory[0x%08x], heap[0x%08x], size: %dn",
(void *)((rt_uint8_t *)header_ptr + RT_MEMHEAP_SIZE),
header_ptr,
size));
return (void *)((rt_uint8_t )header_ptr + RT_MEMHEAP_SIZE);
}
if (heap->locked == RT_FALSE)
{
/ release lock /
rt_sem_release(&(heap->lock));
}
}
RT_DEBUG_LOG(RT_DEBUG_MEMHEAP, ("allocate memory: failedn"));
/ Return the completion status. */
return RT_NULL;
}
對于內(nèi)存釋放來說，主要操作如下：

首先會檢查內(nèi)存塊的magic number，然后更新堆的信息

然后會判斷前后兩塊內(nèi)存塊是否能夠合并

如果能夠合并則更新鏈表和內(nèi)存塊信息
如果沒有和前一內(nèi)存塊進(jìn)行合并，則需要重新放入free_list?

遍歷free_list?，按照大小排序放入鏈表
void rt_memheap_free(void *ptr)
{
rt_err_t result;
struct rt_memheap *heap;
struct rt_memheap_item *header_ptr, new_ptr;
rt_bool_t insert_header;
/ NULL check /
if (ptr == RT_NULL) return;
/ set initial status as OK */
insert_header = RT_TRUE;
new_ptr = RT_NULL;
header_ptr = (struct rt_memheap_item *)
((rt_uint8_t )ptr - RT_MEMHEAP_SIZE);
RT_DEBUG_LOG(RT_DEBUG_MEMHEAP, ("free memory: memory[0x%08x], block[0x%08x]n",
ptr, header_ptr));
/ check magic /
if (header_ptr->magic != (RT_MEMHEAP_MAGIC | RT_MEMHEAP_USED) ||
(header_ptr->next->magic & RT_MEMHEAP_MASK) != RT_MEMHEAP_MAGIC)
{
RT_DEBUG_LOG(RT_DEBUG_MEMHEAP, ("bad magic:0x%08x @ memheapn",
header_ptr->magic));
RT_ASSERT(header_ptr->magic == (RT_MEMHEAP_MAGIC | RT_MEMHEAP_USED));
/ check whether this block of memory has been over-written. /
RT_ASSERT((header_ptr->next->magic & RT_MEMHEAP_MASK) == RT_MEMHEAP_MAGIC);
}
/ get pool ptr /
heap = header_ptr->pool_ptr;
RT_ASSERT(heap);
RT_ASSERT(rt_object_get_type(&heap->parent) == RT_Object_Class_MemHeap);
if (heap->locked == RT_FALSE)
{
/ lock memheap /
result = rt_sem_take(&(heap->lock), RT_WAITING_FOREVER);
if (result != RT_EOK)
{
rt_set_errno(result);
return ;
}
}
/ Mark the memory as available. /
header_ptr->magic = (RT_MEMHEAP_MAGIC | RT_MEMHEAP_FREED);
/ Adjust the available number of bytes. /
heap->available_size += MEMITEM_SIZE(header_ptr);
/ Determine if the block can be merged with the previous neighbor. /
if (!RT_MEMHEAP_IS_USED(header_ptr->prev))
{
RT_DEBUG_LOG(RT_DEBUG_MEMHEAP, ("merge: left node 0x%08xn",
header_ptr->prev));
/ adjust the available number of bytes. /
heap->available_size += RT_MEMHEAP_SIZE;
/ yes, merge block with previous neighbor. /
(header_ptr->prev)->next = header_ptr->next;
(header_ptr->next)->prev = header_ptr->prev;
/ move header pointer to previous. /
header_ptr = header_ptr->prev;
/ don't insert header to free list /
insert_header = RT_FALSE;
}
/ determine if the block can be merged with the next neighbor. /
if (!RT_MEMHEAP_IS_USED(header_ptr->next))
{
/ adjust the available number of bytes. /
heap->available_size += RT_MEMHEAP_SIZE;
/ merge block with next neighbor. /
new_ptr = header_ptr->next;
RT_DEBUG_LOG(RT_DEBUG_MEMHEAP,
("merge: right node 0x%08x, next_free 0x%08x, prev_free 0x%08xn",
new_ptr, new_ptr->next_free, new_ptr->prev_free));
new_ptr->next->prev = header_ptr;
header_ptr->next = new_ptr->next;
/ remove new ptr from free list */
new_ptr->next_free->prev_free = new_ptr->prev_free;
new_ptr->prev_free->next_free = new_ptr->next_free;
}
if (insert_header)
{
struct rt_memheap_item n = heap->free_list->next_free;;
#if defined(RT_MEMHEAP_BEST_MODE)
rt_size_t blk_size = MEMITEM_SIZE(header_ptr);
for (;n != heap->free_list; n = n->next_free)
{
rt_size_t m = MEMITEM_SIZE(n);
if (blk_size <= m)
{
break;
}
}
#endif
/ no left merge, insert to free list /
header_ptr->next_free = n;
header_ptr->prev_free = n->prev_free;
n->prev_free->next_free = header_ptr;
n->prev_free = header_ptr;
RT_DEBUG_LOG(RT_DEBUG_MEMHEAP,
("insert to free list: next_free 0x%08x, prev_free 0x%08xn",
header_ptr->next_free, header_ptr->prev_free));
}
#ifdef RT_USING_MEMTRACE
rt_memset(header_ptr->owner_thread_name, ' ', sizeof(header_ptr->owner_thread_name));
#endif / RT_USING_MEMTRACE /
if (heap->locked == RT_FALSE)
{
/ release lock */
rt_sem_release(&(heap->lock));
}
}
上層抽象
因為RT-Thread支持多種內(nèi)存管理算法，所以必須有一個統(tǒng)一的上層抽象，其中主要由rtconfig.h?以及中的宏來控制使用哪種算法

#define RT_PAGE_MAX_ORDER 11
#define RT_USING_MEMPOOL
#define RT_USING_SMALL_MEM
#define RT_USING_MEMHEAP
#define RT_MEMHEAP_FAST_MODE
#define RT_USING_SMALL_MEM_AS_HEAP
#define RT_USING_MEMTRACE
#define RT_USING_HEAP
最后在src/kservice.c?當(dāng)中將接口進(jìn)行統(tǒng)一抽象，也就是統(tǒng)一為rt_malloc?、rt_free?和re_realloc?等等

#define _MEM_INIT(_name, _start, _size)
system_heap = rt_smem_init(_name, _start, _size)
#define _MEM_MALLOC(_size)
rt_smem_alloc(system_heap, _size)
#define _MEM_REALLOC(_ptr, _newsize)
rt_smem_realloc(system_heap, _ptr, _newsize)
#define _MEM_FREE(_ptr)
rt_smem_free(_ptr)
#define _MEM_INFO(_total, _used, _max)
_smem_info(_total, _used, _max)
#elif defined(RT_USING_MEMHEAP_AS_HEAP)
static struct rt_memheap system_heap;
void *_memheap_alloc(struct rt_memheap *heap, rt_size_t size);
void _memheap_free(void *rmem);
void *_memheap_realloc(struct rt_memheap *heap, void *rmem, rt_size_t newsize);
#define _MEM_INIT(_name, _start, _size)
rt_memheap_init(&system_heap, _name, _start, _size)
#define _MEM_MALLOC(_size)
_memheap_alloc(&system_heap, _size)
#define _MEM_REALLOC(_ptr, _newsize)
_memheap_realloc(&system_heap, _ptr, _newsize)
#define _MEM_FREE(_ptr)
_memheap_free(_ptr)
#define _MEM_INFO(_total, _used, _max)
rt_memheap_info(&system_heap, _total, _used, _max)
#elif defined(RT_USING_SLAB_AS_HEAP)
static rt_slab_t system_heap;
rt_inline void _slab_info(rt_size_t *total,
rt_size_t *used, rt_size_t *max_used)
{
if (total)
*total = system_heap->total;
if (used)
*used = system_heap->used;
if (max_used)
*max_used = system_heap->max;
}
#define _MEM_INIT(_name, _start, _size)
system_heap = rt_slab_init(_name, _start, _size)
#define _MEM_MALLOC(_size)
rt_slab_alloc(system_heap, _size)
#define _MEM_REALLOC(_ptr, _newsize)
rt_slab_realloc(system_heap, _ptr, _newsize)
#define _MEM_FREE(_ptr)
rt_slab_free(system_heap, _ptr)
#define _MEM_INFO _slab_info
#else
#define _MEM_INIT(...)
#define _MEM_MALLOC(...) RT_NULL
#define _MEM_REALLOC(...) RT_NULL
#define _MEM_FREE(...)
#define _MEM_INFO(...)
#endif
rt_weak void *rt_malloc(rt_size_t size)
{
rt_base_t level;
void ptr;
/ Enter critical zone /
level = _heap_lock();
/ allocate memory block from system heap /
ptr = _MEM_MALLOC(size);
/ Exit critical zone /
_heap_unlock(level);
/ call 'rt_malloc' hook */
RT_OBJECT_HOOK_CALL(rt_malloc_hook, (ptr, size));
return ptr;
}
RTM_EXPORT(rt_malloc);