FreeRTOS 内存 Heap管理_freertos heap

@(嵌入式)

FreeRtos
FreeRtos 提供的几种 heap 管理在源码目录 Source/Portable/MemMang 下，选择哪种类型管理直接在编译时把原文件加入（比如在 makefile SRC中加入）即可， 堆大小是 FreeRTOSConfig.h 中的常量 configTOTAL_HEAP_SIZE，默认是17*1024，即17KB。

FreeRtos 内存管理提供的主要接口：

pvPortMalloc() 对应 malloc()
vPortFree() 对应 free()
xPortGetFreeHeapSize() 获取剩余可分配内存大小
为了适配不同平台、场合需求，对接口提供了不同的实现。

内存对齐
在 portmacro.h (Source/Portable/ + 对应编译器 + 平台 目录下) 的常量 portBYTE_ALIGNMENT 定义了字节对齐，对应的这个变量决定了 portable.h 中的一个常量 portBYTE_ALIGNMENT_MASK， 对应关系如下：

portBYTE_ALIGNMENT portBYTE_ALIGNMENT_MASK
8（表示以8个字节对齐） 0x0007
4（表示以4个字节对齐） 0x0003
2（表示以2个字节对齐） 0x0001
1（表示以1个字节对齐） 0x0000
在堆管理中涉及了一些字节对齐，此处做准备。

Heap_1
这个版本的堆管理，如源码注释

The simplest possible implementation of pvPortMalloc(). Note that this implementation does NOT allow allocated memory to be freed again.

实现 pvPortMalloc() 用于内存分配，但是不支持回收，适用于一些比较小的嵌入式设备，在系统 boot 后申请内存运行任务，队列和信号量等，在程序生命期内一般没有释放的需求。对于一些安全型的系统，一般是不允许动态申请的，满足设计需求下，越简单越安全。

调用函数 pvPortMalloc( size_t xWantedSize ) 申请内存时，按顺序完成如下工作：

字节对齐
分配内存
调用钩子函数
返回分配内存地址
初始化
#define configADJUSTED_HEAP_SIZE ( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )
/* Allocate the memory for the heap. */
static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
static size_t xNextFreeByte = ( size_t ) 0;
configADJUSTED_HEAP_SIZE 定义了实际可用的堆大小，因为保证字节的对齐，所以减去一个对齐的长度。
ucHeap[ configTOTAL_HEAP_SIZE ] 和 xNextFreeByte 分别对应堆 的地址和已经分配的值，堆实际上就是一个静态分配的大数组。

以下代码，均是函数 pvPortMalloc() 的内容

字节对齐处理
/* Ensure that blocks are always aligned to the required number of bytes. /
#if portBYTE_ALIGNMENT != 1
if( xWantedSize & portBYTE_ALIGNMENT_MASK )
{
/ Byte alignment required. */
xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
}
#endif
if 判断了申请的内存大小是否符合字节对齐，如果不符合，则进行对齐处理。举个例子，设置8字节对齐，你本来申请的 xWantedSize == 12 个byte，与 mask & 的结果是4（0100B）, 不对齐，为了对齐，系统会 ”强迫症“ 多给你4个字节。实际上你不应该用到，因为你申请了12bye。

分配内存
vTaskSuspendAll();
{
if( pucAlignedHeap == NULL )
{
/* Ensure the heap starts on a correctly aligned boundary. */
// 字节对齐
pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE )
&ucHeap[ portBYTE_ALIGNMENT ] ) & ( ( portPOINTER_SIZE_TYPE ) ~portBYTE_ALIGNMENT_MASK ) );
}

/* Check there is enough room left for the allocation. */
// 边界判断
if( ( ( xNextFreeByte + xWantedSize ) < configADJUSTED_HEAP_SIZE ) &&
    ( ( xNextFreeByte + xWantedSize ) > xNextFreeByte ) )/* Check for overflow. */
{
    /* Return the next free byte then increment the index past this
    block. */
    // 切块蛋糕一样把内存分配出来
    pvReturn = pucAlignedHeap + xNextFreeByte;
    xNextFreeByte += xWantedSize;
}
traceMALLOC( pvReturn, xWantedSize );
1
2
3
4
5
6
7
8
9
10
11
12

}
xTaskResumeAll();
系统调用了 vTaskSuspendAll() 挂起所有任务，保证线程安全， 避免分配时被切任务导致出错。
对堆的首地址作对齐处理
可能有人疑问堆首地址不就是上面提到那个数组的首地址 &ucHeap[0]， 为什么这里要使用 &ucHeap[ portBYTE_ALIGNMENT ] & portPOINTER_SIZE_TYPE？
其实这个地方处理还是考虑对齐问题，举个例子就明白了：
设置8byte对齐， 假如&ucHeap[0]地址是 0x00000006, 为了保证对齐，FreeRtos 直接在这个地址加上一个对齐的长度（保证&后不会越界访问），然后和 mark &一下，对应的，&ucHeap[ portBYTE_ALIGNMENT ]对应了0x000000014，& 上 mark 就是 0x00000008。由于做了这个调整后，实际的堆大小改变了，所以 configADJUSTED_HEAP_SIZE 表示实际可用的内存大小
分配内存
Heap_1 比较简单，按顺序分配，所以只需要判断剩下的内存够大，直接切出来，更新已分配大小的值，返回地址就可以了
钩子函数调用&返回地址
定义了configUSE_MALLOC_FAILED_HOOK == 1 后， 当申请失败的时候会调用钩子函数， 也可以自己添加其他处理代码。

#if( configUSE_MALLOC_FAILED_HOOK == 1 )
{
    if( pvReturn == NULL )
    {
        extern void vApplicationMallocFailedHook( void );
        vApplicationMallocFailedHook();
    }
}
#endif
return pvReturn;
1
2
3
4
5
6
7
8
9
10

}
Heap_1 的 vPortFree 函数就不提了

Heap_2
Heap_2 内存分配使用最佳匹配算法(best fit algorithm)，比如我们申请25k的内存，而可申请内存中有三块对应大小30K， 50K 和 100 K，按照最小匹配，这时候会把30k进行分割并返回申请内存的地址，剩余部分插回链表留待下次申请。
Heap_2 支持内存回收，但是不会把碎片合并，对于每次申请内存大小都比较固定的，这个方式是没有问题的。

开始和 Heap_1 差不多， 在内存中开辟了一个静态数组作为堆的空间，定义大小，字节对齐处理等。

建立链表
Heap_2 通过一个链表维护未分配的内存，链表节点定义：

typedef struct A_BLOCK_LINK
{
struct A_BLOCK_LINK pxNextFreeBlock;
/<< The next free block in the list. /
size_t xBlockSize;
/<< The size of the free block. */
} BlockLink_t;
两个变量分别是指向下一块内存的地址指针 pxNextFreeBlock 以及自己的内存大小 xBlockSize。

在第一次申请内存的时候会调用初始化函数 prvHeapInit() 初始化列表。初始化包括链表头 xStart 和链表尾 xEnd (这两个节点不包含空闲内存)，以及把整个堆作为一个完整的空闲节点。

每块内存（分配出的和未分配的）的结构如下 :

下一个空闲块地址 当前块大小 当前块可用内存
xx xx xx
每块的开头节点数据，提供了分配内存或者回收内存所需要的信息。

分配内存
当我们尝试申请内存的时候，除了和 Heap_1 一样进行对齐等处理外，系统会在我们申请内存大小 xWantedSize 的基础上增加一个 heapSTRUCT_SIZE （链表节点对齐后的大小）的链表节点，记录这块分配出去的内存的大小，供回收的时候使用。

从链表头开始遍历未分配内存链表，查找符合大小的内存块（链表按内存块大小排列，所以最先返回的的块最符合申请内存大小，所谓的最匹配算法就是这个意思来的）。返回该块 heapSTRUCT_SIZE 个字节后的地址给函数调用者， 前面预留的字节保留链表节点信息。

同时会判断当前这块内存是否有剩余（大于一个链表节点所需空间），如果有，就把剩余的内存再新建一个未分配内存块节点，插入到未分配链表中，供下次分配使用。其中 prvInsertBlockIntoFreeList() 这个宏函数是把节点按大小插入到链表中。

if( ( xWantedSize > 0 ) && ( xWantedSize < configADJUSTED_HEAP_SIZE ) )
{
/* Blocks are stored in byte order - traverse the list from the start
(smallest) block until one of adequate size is found. */
pxPreviousBlock = &xStart;
pxBlock = xStart.pxNextFreeBlock;
// 寻找匹配的内存块节点
while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
{
pxPreviousBlock = pxBlock;
pxBlock = pxBlock->pxNextFreeBlock;
}

/* If we found the end marker then a block of adequate size was not found. */
if( pxBlock != &xEnd )
{
    /* Return the memory space - jumping over the BlockLink_t structure
    at its start. */
    //返回给我们用地址，前面 heapSTRUCT_SIZE 保存链表节点数据
    pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );

    /* This block is being returned for use so must be taken out of the
    list of free blocks. */
    pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;

    /* If the block is larger than required it can be split into two. */
    // 内存块比较大，拆分多余的内存，插回到链表
    if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
    {
        /* This block is to be split into two.  Create a new block
        following the number of bytes requested. The void cast is
        used to prevent byte alignment warnings from the compiler. */
        pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );

        /* Calculate the sizes of two blocks split from the single
        block. */
        pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
        pxBlock->xBlockSize = xWantedSize;

        /* Insert the new block into the list of free blocks. */
        //　按内存大小插入
        prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );
    }

    xFreeBytesRemaining -= pxBlock->xBlockSize;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

}
回收内存
回收内存， 拿到分配时返回的地址，向前索引到对应链表节点，取出这块返回内存块的信息，调用链表插入函数，将这个节点归还。（线程安全）

puc -= heapSTRUCT_SIZE;
/* This unexpected casting is to keep some compilers from issuing
byte alignment warnings. /
pxLink = ( void * ) puc;
vTaskSuspendAll();
{
/ Add this block to the list of free blocks. */
prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
xFreeBytesRemaining += pxLink->xBlockSize;
traceFREE( pv, pxLink->xBlockSize );
}
xTaskResumeAll();
！！！　这里感觉，如果随便传个地址进来，会不会把系统弄傻…

Heap_3
Heap_3 实现是直接对标准库的 malloc 进行封装， 保证线程安全。

void *pvPortMalloc( size_t xWantedSize )
{
void *pvReturn;
vTaskSuspendAll(); // 挂起任务
{
pvReturn = malloc( xWantedSize );
}
xTaskResumeAll();
return pvReturn;
}
void vPortFree( void *pv )
{
if( pv != NULL )
{
vTaskSuspendAll();
{
free( pv );
}
xTaskResumeAll();
}
}
!! 这种模式下，堆大小不再由 FreeRTOSConfig.h 中定义的常量 configTOTAL_HEAP_SIZE 决定，而是由连接器或者启动代码决定。

Heap_4
相比 Heap_2, Heap_4 能够把内存碎片合并成大块内存，为了实现这个合并算法，空闲内存链表是按内存地址大小进行存储的（Heap_2　是按照内存块大小进行存储）。

xEnd 的位置
不同 heap_2 中 用一个静态变量 xEnd 作为链表尾，heap_4 把链表尾放在了堆的最后位置，如源码：

// 堆地址最后往回推一个链表节点的空间
uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
uxAddress -= xHeapStructSize;
uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
pxEnd = ( void * ) uxAddress;
pxEnd->xBlockSize = 0;
pxEnd->pxNextFreeBlock = NULL;
xBlockAllocatedBit 判断
另外，为了安全，增加一个位（xBlockSize　的最高位）标记检测 Free 时传入地址的正确性，在初始化的时候设置 xBlockAllocatedBit 的值, 一个 size_t 大小的值最高位置1， 分配出去的内存块链表节点的 xBlockSize 或上，回收的时候判断，如果最高位不是1， 说明出错。

/* Work out the position of the top bit in a size_t variable. */
xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
进行字节对齐和线程安全等的操作和前面两种方式差不多。

链表插入 （合并实现）
Heap_2 中的链表插入是通过宏实现的，按内存块大小进行插入，而 Heap_4 的插入操作是一个函数，该函数按内存块地址进行插入（低位前），这么做是为了实现内存块合并。
如下， 准备插入的内存块p， 系统查找到内存地址对应与其前面的内存块A, 判断 A 和 P 之间是否还有其他分配的块，如果没有，直接合并； 然后再判断和内存C 的位置关系，没有其他分配了的内存块的话，就直接合并。

内存块 … 内存块 A 准备插入内存块 P 内存块 C
xx xx xx xx
下面对应看看源码 ：

static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert )
{
BlockLink_t *pxIterator;
uint8_t puc;
// for 的目的是知道 pxIterator 指向内存块A
// pxIterator->pxNextFreeBlock 指向内存块C
// 插入内存块P 刚好夹在中间
for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
{
/ Nothing to do here, just iterate to the right position. */
}
// 判断内存块A 能否与插入内存块P 合并
// 合并条件：头尾衔接刚好
puc = ( uint8_t * ) pxIterator;
if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
{
pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
pxBlockToInsert = pxIterator;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
// 判断内存块C 能否与插入块P 合并
puc = ( uint8_t * ) pxBlockToInsert;
if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
{
// 如果是内存块C 是最后一个节点 xEnd，不能合并
if( pxIterator->pxNextFreeBlock != pxEnd )
{
pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
}
else
{
pxBlockToInsert->pxNextFreeBlock = pxEnd;
}
}
else
{
// 内存块C 不能合并的话，让上一块指向他
pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
}
if( pxIterator != pxBlockToInsert )
{
// 内存块A 不能合并，更新他指向刚插入的内存块P
pxIterator->pxNextFreeBlock = pxBlockToInsert;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
分配内存
相比 Heap_2 差别不大，主要是在分配过程多了一个位标记防止出错，因为使用了 xBlockSize 的最高位做标记，所以实际传入的 xWantedSize 最高位不能为1，否则超出范围。
其他差别不大，此处不做赘述。

回收内存
相比 Heap_2, Heap_4 多了一些检查，更加安全。

// 判断位标记，判断指向下一个节点是否 设置为 Null
configASSERT( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 );
configASSERT( pxLink->pxNextFreeBlock == NULL );
if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
{
if( pxLink->pxNextFreeBlock == NULL )
{
…
最后清除 xBlockSize 的高位标记，调用插入函数归还内存。

获取历史堆剩余最小值
可用于最坏情况下，堆的使用情况， 在每次调用 pvPortMalloc() 中进行更新。

size_t xPortGetMinimumEverFreeHeapSize( void )
Heap_5
前面方式1、2和4 方式都是静态申请一个数组作为堆，Heap_5 允许使用多个不连续的区域组成堆，申请函数前，必须通过函数 vPortDefineHeapRegions() 进行设置，对于一些内存分布不连续的嵌入式设备还是很有价值的，之后其他操作，和 Heap_4 基本一致。

所以这里主要分析下 vPortDefineHeapRegions() 的实现。

设置作为堆的区域需要用到一下结构体

/* Used by heap_5.c. */
typedef struct HeapRegion
{
uint8_t *pucStartAddress;
size_t xSizeInBytes;
} HeapRegion_t;
举个例子，
有两个不连续区域首地址0x00200000， 长度0x10000 和首地址0x00300000， 长度0xA0000 只做为堆，则可以建立如下数组传递给 vPortDefineHeapRegions(), 进行设置。

HeapRegion_t xHeapRegions[] =
{
{ ( uint8_t * ) 0x00200000UL, 0x10000 },
{ ( uint8_t * ) 0x00300000UL, 0xA0000 },
{ NULL, 0 } // 告知结束
};
相比前面其他模式，初始化时，把可以分配的内存作为一个节点，Heap_5 就把这几个不连续的内存区域分别作为节点链接起来。

每个连续区域作为一个节点，其结构如下

指向末端节点
本块内存区域大小
本块可用内存区域
指向下一块内存
0
参考
Using the FreeRTOS Real Time Kernel - A Practical Guide_opened
FreeRTOS memory

作者：orientlu
链接：https://www.jianshu.com/p/c5fbad706e9f
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
https://www.jianshu.com/p/c5fbad706e9f