FreeRTOS之heap4

操作系统离不开内存管理。FreeRTOS提供了5种内存管理方法。实现在portable\MemMang里heap1到heap5。每种管理方案策略不同。我采用的是比较有代表性的heap4管理方案。该模式定义了ucHeap全局数组充当堆内存池。然后通过链表管理未分配的内存块空间。首先所有的堆和栈内存空间申请都来着ucHeap的数组。然后没分配一块内存就到可用链表里找到第一个合适的自由块分配给使用者。如果该块大于申请大小。分配后就有一个剩余空间，如果剩余空间小于管理用的结构体占用空间，那么剩余空间不用再构建新的空闲块，因为他连管理用的结构体都无法放下。如果剩余空间大于关联用的结构体空间，那么剩余空间就还有可用加载，在分配地址返回前把要分配的块截止大小为申请的大小，把剩余的空间构造一个新的自由块加入自由跨链表。如果使用者调用了释放内存方法，那么先给传入的要释放内存地址前移内存管理块的大小，即得到当前释放内存块的管理结构体地址。然后按地址大小找到空闲列表对应位置插入释放块。如果释放块和前后地址接的上那么就和前后进行块合并操作。整体就是这样一种操作。

要理解FreeRTOS的内核调度，要先理解内核的内存分配方案。结构图如下(引用的别人的图)：

heap_4.c实现如下

//堆内存管理的实现，该模式可以申请和释放内存。定义了ucHeap全局数组充当堆内存池。
//实际分配的该数组的空间。采用链表管理分配，将多个自由内存块链接起来。
//定义了#define pvPortMallocStack    pvPortMalloc，所有内核栈也是从这里申请内存

/*动态内存分配是C语言编程中的一个概念，而不是FreeRTOS或者多任务里面的特有的概念。
FreeRTOS需要涉及到动态内存分配是因为内核对象是动态构造的。
在通用的C语言编程环境里，我们可以使用标准库中的malloc()和free()来进行动态内存分配的操作，
但这些函数对于实时应用是不合适的，原因有如下几点：
1.在嵌入式系统中他们不总是可用的，有的环境不支持或者没有实现
2.他们的底层实现可能需要较多的资源，调用时开销大
3.他们很少情况下是线程安全的
4.他们的调用耗时是不确定的（not deterministic），每次调用耗时都可能不一样（标准只要求他们的执行尽可能的快速完成并返回）
5.可能会造成内存碎片问题
6.他们会使连接器的配置变的复杂
7.会使得代码很难调试

提供下面方法给内核申请和释放内存
void *pvPortMalloc( size_t xWantedSize )
void vPortFree( void *pv )
*/

#include <stdlib.h>

/* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining
 * all the API functions to use the MPU wrappers.  That should only be done when
 * task.h is included from an application file. */
#define MPU_WRAPPERS_INCLUDED_FROM_API_FILE

#include "FreeRTOS.h"
#include "task.h"

#undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE
//这个模式就是动态管理内存，所以不允许关闭动态内存
#if (configSUPPORT_DYNAMIC_ALLOCATION == 0)
    #error This file must not be used if configSUPPORT_DYNAMIC_ALLOCATION is 0
#endif

//最小可用做内存分配的堆大小
//一个内存块分配给需求之后剩余大小如果小于对结构体大小就不能当做空闲块。因为分配内存要用堆结构体记录分配信息
//剩余空间都小于结构体大小了就不能当新的空闲块
//所以最小堆大小就是堆结构体打印左一1位，即堆结构体大小加八个比特
#define heapMINIMUM_BLOCK_SIZE    ((size_t) ( xHeapStructSize << 1))

/*假设8bit 字节！*/
#define heapBITS_PER_BYTE         ((size_t) 8)

/*如果配置了运用程序自己定义堆数组就使用外部的堆。
	ucHeap的存放位置是在编译期间，由链接器（linker）决定的，
	如果ucHeap被放到了访问速度较慢的外部SRAM，则任务的执行速度将受到不利影响。
	这个时候可以由开发者自己定义ucHeap内存池数组*/
#if (configAPPLICATION_ALLOCATED_HEAP == 1)
		//引入自定义堆
    extern uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
#else
		//堆就是一个u8类型大数组
    PRIVILEGED_DATA static uint8_t ucHeap[configTOTAL_HEAP_SIZE ];
#endif

//用于内存管理的链表结构，通过该链表把空闲内块链接起来管理
typedef struct A_BLOCK_LINK
{
	 //下一个空闲块
   struct A_BLOCK_LINK * pxNextFreeBlock;
	 //空闲块的大小
   size_t xBlockSize;
} BlockLink_t;

/*-----------------------------------------------------------*/

//把要释放的内存块放入自由内存块链表。按地址找到插入位置。如果能和前后正好接上就做块合并处理
static void prvInsertBlockIntoFreeList(BlockLink_t * pxBlockToInsert) PRIVILEGED_FUNCTION;

//初始化堆，第一个内存分配时候自动调用
static void prvHeapInit(void) PRIVILEGED_FUNCTION;

/*-----------------------------------------------------------*/

//堆结构体的大小。每次分配要用堆结构体记录分配的一块信息。记录的结构体本身要占空间
static const size_t xHeapStructSize = (sizeof(BlockLink_t) + ((size_t) (portBYTE_ALIGNMENT - 1))) & ~((size_t) portBYTE_ALIGNMENT_MASK);

/*创建内存块开始和结束节点，通过xStart和pxEnd遍历找到合适内存分配*/
PRIVILEGED_DATA static BlockLink_t xStart, * pxEnd = NULL;

/* 跟踪分配和释放内存的调用次数以及
  * 剩余的空闲字节数，但没有说明碎片。 */
PRIVILEGED_DATA static size_t xFreeBytesRemaining = 0U;
PRIVILEGED_DATA static size_t xMinimumEverFreeBytesRemaining = 0U;
PRIVILEGED_DATA static size_t xNumberOfSuccessfulAllocations = 0;
PRIVILEGED_DATA static size_t xNumberOfSuccessfulFrees = 0;

//已经分配的比特数
PRIVILEGED_DATA static size_t xBlockAllocatedBit = 0;

/*-----------------------------------------------------------*/
//申请内存
//xWantedSize:想要申请的大小
void * pvPortMalloc(size_t xWantedSize)
{
    BlockLink_t * pxBlock, * pxPreviousBlock, * pxNewBlockLink;
    void * pvReturn = NULL;
    //挂起所有任务
    vTaskSuspendAll();
    {
        /* 如果这是对 malloc 的第一次调用，那么堆将需要
          * 初始化设置空闲块列表。 */
        if( pxEnd == NULL )
        {
					  //第一次申请内存就初始化堆
            prvHeapInit();
        }
        else
        {
            mtCOVERAGE_TEST_MARKER();
        }

        //检查申请分配的内存是否具有合法性和检查申请的内存是否过大
        if((xWantedSize & xBlockAllocatedBit ) == 0)
        {
            //分配的数必须大于0
            if((xWantedSize > 0) && ((xWantedSize + xHeapStructSize)> xWantedSize))
            {
							  //申请的大小要加上堆记录结构体大小
                xWantedSize += xHeapStructSize;

                /*确保块对齐*/
                if((xWantedSize & portBYTE_ALIGNMENT_MASK) != 0x00)
                {
                    /*需要字节对齐。检查溢出。*/
                    if((xWantedSize + (portBYTE_ALIGNMENT - (xWantedSize & portBYTE_ALIGNMENT_MASK )))
                            > xWantedSize )
                    {
                        xWantedSize += (portBYTE_ALIGNMENT - (xWantedSize & portBYTE_ALIGNMENT_MASK));
                        configASSERT((xWantedSize & portBYTE_ALIGNMENT_MASK) == 0 );
                    }
                    else
                    {
                        xWantedSize = 0;
                    }
                }
                else
                {
                    mtCOVERAGE_TEST_MARKER();
                }
            }
            else
            {
                xWantedSize = 0;
            }
						//申请大小小于剩余的内存大小
            if((xWantedSize > 0) && (xWantedSize <= xFreeBytesRemaining) )
            {
                /*从开始（最低地址）块遍历列表，直到
                  * 找到一个足够大小的。 */
							  //前一个块，从开始块找
                pxPreviousBlock = &xStart;
							  //当前块，从开始取下一个空闲块
                pxBlock = xStart.pxNextFreeBlock;
								//一直找到大小大于申请大小的块或者找到最后块
                while((pxBlock->xBlockSize < xWantedSize) && (pxBlock->pxNextFreeBlock != NULL))
                {
										//前一个块等于当前块
                    pxPreviousBlock = pxBlock;
									  //当前块往下移一个
                    pxBlock = pxBlock->pxNextFreeBlock;
                }

                //如果当前块不等于结束就代表找到了符合的内存块了
                if( pxBlock != pxEnd )
                {
                    //返回当前块地址加上一个堆结构大小的地址
                    pvReturn = (void *) (((uint8_t *) pxPreviousBlock->pxNextFreeBlock) + xHeapStructSize);

                    //前一个块执行当前块的下一个块
                    pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;

                    //当前块分配给要的空间后如果剩余大小大于堆最小大小。剩下的空间就是一个可用的块
									  //构造一个新的空闲块
                    if((pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE)
                    {
                        //新空闲块执行当前块分配给想要空间大小后的地址
                        pxNewBlockLink = (void *) ((( uint8_t *) pxBlock) + xWantedSize);
                        configASSERT((((size_t) pxNewBlockLink) & portBYTE_ALIGNMENT_MASK ) == 0);

                        //新空闲块大小为当前块大小减去要申请的大小
                        pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
											  //当前块已经把剩下空间构成新块了，他本身大小变为申请的大小了
                        pxBlock->xBlockSize = xWantedSize;

                       //把新的空闲块插入空闲块列表
                        prvInsertBlockIntoFreeList(pxNewBlockLink);
                    }
                    else
                    {
                        mtCOVERAGE_TEST_MARKER();
                    }
										//空闲内存大小减去申请的大小
                    xFreeBytesRemaining -= pxBlock->xBlockSize;

                    if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
                    {
                        xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
                    }
                    else
                    {
                        mtCOVERAGE_TEST_MARKER();
                    }

                    /* The block is being returned - it is allocated and owned
                     * by the application and has no "next" block. */
                    pxBlock->xBlockSize |= xBlockAllocatedBit;
										//当前块已经分配出去了，所以下一个自由块执行空指针
                    pxBlock->pxNextFreeBlock = NULL;
										//成功分配内存的数量加1
                    xNumberOfSuccessfulAllocations++;
                }
                else
                {
                    mtCOVERAGE_TEST_MARKER();
                }
            }
            else
            {
                mtCOVERAGE_TEST_MARKER();
            }
        }
        else
        {
            mtCOVERAGE_TEST_MARKER();
        }
				//跟踪内存分配
        traceMALLOC(pvReturn,xWantedSize);
    }
		//恢复挂起的任务
    (void) xTaskResumeAll();
    //配置了分配内存失败钩子的处理
    #if (configUSE_MALLOC_FAILED_HOOK == 1)
        {
						//分配失败之后调用钩子函数
            if(pvReturn == NULL)
            {
                extern void vApplicationMallocFailedHook(void);
                vApplicationMallocFailedHook();
            }
            else
            {
                mtCOVERAGE_TEST_MARKER();
            }
        }
    #endif 
    configASSERT(((( size_t) pvReturn) & (size_t) portBYTE_ALIGNMENT_MASK ) == 0);
		//返回内存地址
    return pvReturn;
}
/*-----------------------------------------------------------*/
//释放分配的内存
//要释放的内存首地址
void vPortFree(void * pv)
{
    uint8_t * puc = (uint8_t *)pv;
	  //堆分配块指针
    BlockLink_t * pxLink;

    if(pv != NULL)
    {
        //由于申请内存返回地址加了堆结构体的大小。所以这里减去堆结构体大小就得到要释放内存的结构体
        puc -= xHeapStructSize;

        //转换为内存结构体指针
        pxLink = (void *)puc;

        //断言用的
        configASSERT((pxLink->xBlockSize & xBlockAllocatedBit) != 0);
        configASSERT(pxLink->pxNextFreeBlock == NULL);

        if((pxLink->xBlockSize & xBlockAllocatedBit ) != 0)
        {
					  //是使用的内存块的下一个自由块为空指针
					  //防止是用户程序传错了要释放的地址
            if(pxLink->pxNextFreeBlock == NULL)
            {
                /* 该块正在返回到堆中 - 它不再是分配 */
                pxLink->xBlockSize &= ~xBlockAllocatedBit;
								//挂起所有任务
                vTaskSuspendAll();
                {
                    //空闲内存大小加上释放块的大小
                    xFreeBytesRemaining += pxLink->xBlockSize;
									  //跟踪位点
                    traceFREE( pv, pxLink->xBlockSize );
									  //把要释放的内存块加入空闲内存列表
                    prvInsertBlockIntoFreeList(((BlockLink_t *) pxLink));
									  //成功释放内存次数加1
                    xNumberOfSuccessfulFrees++;
                }
								//恢复所有挂起的任务
                (void) xTaskResumeAll();
            }
            else
            {
                mtCOVERAGE_TEST_MARKER();
            }
        }
        else
        {
            mtCOVERAGE_TEST_MARKER();
        }
    }
}
/*-----------------------------------------------------------*/
//得到自由堆大小
size_t xPortGetFreeHeapSize(void)
{
    return xFreeBytesRemaining;
}
/*-----------------------------------------------------------*/

size_t xPortGetMinimumEverFreeHeapSize(void)
{
    return xMinimumEverFreeBytesRemaining;
}
/*-----------------------------------------------------------*/

void vPortInitialiseBlocks(void)
{
    /*这只是为了保持链接器安静。*/
}
/*-----------------------------------------------------------*/
//用来第一次申请内存时候初始化堆
//第一步：起始地址做字节对齐,保存pucAlignedHeap 可用空间大小为xTotalHeapSize 
//第二步：计算首尾 ,这里需要注意的是链表的尾部指针是保存到该地址尾部的
//第三部：完成链表的初始化，记录内存块信息
static void prvHeapInit(void) 
{
    BlockLink_t * pxFirstFreeBlock;
    uint8_t * pucAlignedHeap;
    size_t uxAddress;
    size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;

    //起始地址做字节对齐处理
	  //执行堆数组开始位置
    uxAddress = (size_t)ucHeap;
    //开始地址做8位对齐
    if((uxAddress & portBYTE_ALIGNMENT_MASK) != 0)
    {
        uxAddress+=(portBYTE_ALIGNMENT-1);
        uxAddress &= ~((size_t)portBYTE_ALIGNMENT_MASK);
			  //减去对齐舍弃的字节
        xTotalHeapSize -= uxAddress - (size_t) ucHeap;
    }
    //对齐后可以用的起始地址
    pucAlignedHeap = (uint8_t *)uxAddress;

    //开始的下一个自由块执行对齐的堆首地址
    xStart.pxNextFreeBlock = (void *) pucAlignedHeap;
		//块大小设置0
    xStart.xBlockSize = (size_t) 0;

    //按对齐的堆的首地址和堆的总大小计算堆的结束位置
    uxAddress = ((size_t)pucAlignedHeap ) + xTotalHeapSize;
    uxAddress -= xHeapStructSize;
    uxAddress &= ~((size_t) portBYTE_ALIGNMENT_MASK);
		//设置计算地址到结束地址，结束块大小为0，结束块的下一个自由块执行空指针
    pxEnd = (void *) uxAddress;
    pxEnd->xBlockSize = 0;
    pxEnd->pxNextFreeBlock = NULL;

    //得到第一个自由块。开始地址是对齐堆的首地址
    pxFirstFreeBlock = (void *) pucAlignedHeap;
		//第一个自由块大小就是堆结束地址减堆对齐的首地址
    pxFirstFreeBlock->xBlockSize = uxAddress - (size_t)pxFirstFreeBlock;
		//第一个自由块执行结束块
    pxFirstFreeBlock->pxNextFreeBlock = pxEnd;

    //记录最小的空闲内存块大小，即开始堆的总大小
    xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
		//剩余内存堆大小
    xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;

    //已经申请的大小
    xBlockAllocatedBit = ((size_t) 1) << ((sizeof(size_t) * heapBITS_PER_BYTE ) - 1);
}
/*-----------------------------------------------------------*/
//插入块到空闲列表
static void prvInsertBlockIntoFreeList(BlockLink_t * pxBlockToInsert) 
{
	  //遍历用的游标
    BlockLink_t * pxIterator;
    uint8_t * puc;

    //从开始块一直找到第一个地址大于要插入块地址的内存块
    for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
    {
        /* 这里没什么可做的，只是迭代到正确的位置。 */
    }

    //找到的块地址转换为u8
    puc = (uint8_t *) pxIterator;
    //如果找到块的首地址加上块大小等于要插入块的首地址
    if((puc + pxIterator->xBlockSize) == (uint8_t *)pxBlockToInsert)
    {
			  //就把要插入的块合并到找到的块
        pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
			  //要插入的块指向找到的块。即两个块合并了
        pxBlockToInsert = pxIterator;
    }
    else
    {
        mtCOVERAGE_TEST_MARKER();
    }

    //要插入块的首地址
    puc = (uint8_t *) pxBlockToInsert;
    //如果要插入的块能和后面合并就再合并
    if((puc+pxBlockToInsert->xBlockSize) == (uint8_t *) pxIterator->pxNextFreeBlock )
    {
			  //没到最后
        if( pxIterator->pxNextFreeBlock != pxEnd )
        {
            //记录合并后的大小
            pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
					  //指向更后一个自由块
            pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
        }
				//已经是最后了，插入块就指向End
        else
        {
            pxBlockToInsert->pxNextFreeBlock = pxEnd;
        }
    }
		//如果不能合并就让插入块执行当前块后一个块
    else
    {
        pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
    }

    //如果当前块和要插入块指向不同，当前块的下一块指向要插入的块
    if( pxIterator != pxBlockToInsert )
    {
        pxIterator->pxNextFreeBlock = pxBlockToInsert;
    }
    else
    {
        mtCOVERAGE_TEST_MARKER();
    }
}
/*-----------------------------------------------------------*/
//得到堆的状态
void vPortGetHeapStats( HeapStats_t * pxHeapStats )
{
    BlockLink_t * pxBlock;
	  //块数量、最大的大小、最小的大小(先设置为最大分配大小)
    size_t xBlocks = 0, xMaxSize = 0, xMinSize = portMAX_DELAY;
		//挂起所有任务
    vTaskSuspendAll();
    {
			  //当前块从开始节点下一个开始
        pxBlock = xStart.pxNextFreeBlock;

        //如果开始的下一个有东西就是初始化过了，否则就是没初始化的
        if( pxBlock != NULL )
        {
            do
            {
                //块数量加1
                xBlocks++;
								//统计最大的块大小
                if( pxBlock->xBlockSize > xMaxSize )
                {
                    xMaxSize = pxBlock->xBlockSize;
                }
								//统计最小的块大小
                if( pxBlock->xBlockSize < xMinSize )
                {
                    xMinSize = pxBlock->xBlockSize;
                }

                //移动到链中的下一个块，一直到最后
                pxBlock = pxBlock->pxNextFreeBlock;
            } while( pxBlock != pxEnd );
        }
    }
		//恢复任务挂起
    (void) xTaskResumeAll();
    //设置最大块、最小块、块数到对状态结构体
    pxHeapStats->xSizeOfLargestFreeBlockInBytes = xMaxSize;
    pxHeapStats->xSizeOfSmallestFreeBlockInBytes = xMinSize;
    pxHeapStats->xNumberOfFreeBlocks = xBlocks;
		//跟踪调试用的位点
    taskENTER_CRITICAL();
    {
        pxHeapStats->xAvailableHeapSpaceInBytes = xFreeBytesRemaining;
        pxHeapStats->xNumberOfSuccessfulAllocations = xNumberOfSuccessfulAllocations;
        pxHeapStats->xNumberOfSuccessfulFrees = xNumberOfSuccessfulFrees;
        pxHeapStats->xMinimumEverFreeBytesRemaining = xMinimumEverFreeBytesRemaining;
    }
    taskEXIT_CRITICAL();
}