23.1 内存管理的基本概念

在计算系统中，变量、中间数据一般存放在系统存储空间中，只有在实际使用时才将它们从存储空间调入到中央处理器内部进行运算。通常存储空间可以分为两种：内部存储空间和外部存储空间。内部存储空间访问速度比较快，能够按照变量地址随机地访问，也就是我们通常所说的 RAM（随机存储器），或电脑的内存；而外部存储空间内所保存的内容相对来说比较固定，即使掉电后数据也不会丢失，可以把它理解为电脑的硬盘。
FreeRTOS 操作系统将内核与内存管理分开实现，可以选择不同的算法。但是上层接口的API是一样的。可以自己选择。
在嵌入式程序设计中内存分配应该是根据所设计系统的特点来决定选择使用动态内存分配还是静态内存分配算法，一些可靠性要求非常高的系统应选择使用静态的，而普通的业务系统可以使用动态来提高内存使用效率。静态可以保证设备的可靠性但是需要考虑内存上限，内存使用效率低，而动态则是相反。
FreeRTOS 内存管理模块管理用于系统中内存资源，它是操作系统的核心模块之一。主要包括内存的初始化、分配以及释放。

什么不直接使用 C 标准库中的内存管理函数呢？在电脑中我们可以用 malloc()和 free()这两个函数动态的分配内存和释放内存。但是，在嵌入式实时操作系统中，调用 malloc()和 free()却是危险的，原因有以下几点：

  • 这些函数在小型嵌入式系统中并不总是可用的，小型嵌入式设备中的 RAM 不足。
  • 它们的实现可能非常的大，占据了相当大的一块代码空间。
  • 他们几乎都不是安全的。
  • 它们并不是确定的，每次调用这些函数执行的时间可能都不一样。
  • 它们有可能产生碎片。
  • 这两个函数会使得链接器配置得复杂。
  • 如果允许堆空间的生长方向覆盖其他变量占据的内存，它们会成为 debug 的灾难。

在一般的实时嵌入式系统中，由于实时性的要求，很少使用虚拟内存机制。所有的内存都需要用户参与分配，直接操作物理内存，所分配的内存不能超过系统的物理内存，所有的系统堆栈的管理，都由用户自己管理。

在嵌入式实时操作系统中，对内存的分配时间要求更为苛刻，分配内存的时间必须是确定的。 一般内存管理算法是根据需要存储的数据的长度在内存中去寻找一个与这段数据相适应的空闲内存块，然后将数据存储在里面。而寻找这样一个空闲内存块所耗费的时间是不确定的，因此对于实时系统来说，这就是不可接受的，实时系统必须要保证内存块的分配过程在可预测的确定时间内完成，否则实时任务对外部事件的响应也将变得不可确定。（分配时间要确定，要快）

在嵌入式系统，内存十分的珍贵。要避免出现内存碎片。

FreeRTOS根据不同的配置和要求，实现了不同的内存管理。
FreeRTOS 的 V9.0.0 版本为我们提供了 5 种内存管理算法，分别是 heap_1.c、 heap_2.c、 heap_3.c、 heap_4.c、 heap_5.c，源文件存放于FreeRTOS\Source\portable\MemMang 路径下，在使用的时候选择其中一个添加到我们的工程中去即可。
FreeRTOS 的内存管理模块通过对内存的申请、释放操作，来管理用户和系统对内存的使用，使内存的利用率和使用效率达到最优，同时最大限度地解决系统可能产生的内存碎片问题。

23.2 内存管理的应用场景

在自己的产品面前，应当选择哪种分配策略。
内存管理的主要工作是动态划分并管理用户分配好的内存区间，主要是在用户需要使用大小不等的内存块的场景中使用， 当用户需要分配内存时，可以通过操作系统的内存申请函数索取指定大小内存块，一旦使用完毕，通过动态内存释放函数归还所占用内存，使之可以重复使用（heap_1.c 的内存管理除外）。

例如我们需要定义一个 float 型数组： floatArr[];
但是，在使用数组的时候：数组应该有多大？在很多的情况下，你并不能确定要使用多大的数组，可能为了避免发生错误你就需要把数组定义得足够大。即使你知道想利用的空间大小，但是如果因为某种特殊原因空间利用的大小有增加或者减少，你又必须重新去修改程序，扩大数组的存储范围。这种分配固定大小的内存分配方法称之为静态内存分配。这种内存分配的方法存在比较严重的缺陷，在大多数情况下会浪费大量的内存空间，在少数情况下，当你定义的数组不够大时，可能引起下标越界错误，甚至导致严重后果。

用动态内存分配就可以解决上面的问题。所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不象数组等静态内存分配方法那样需要预先分配存储空间，而是由系统根据程序的需要即时分配，且分配的大小就是程序要求的大小。

23.3 内存管理方案详解

FreeRTOS 规定了内存管理的函数接口，具体见，但是不管其内部的内存管理方案是怎么实现的，所以， FreeRTOS 可以提供多个内存管理方案，下面，就一起看看各个内存管理方案的区别。 

  1. void *pvPortMalloc( size_t xSize ); //内存申请函数
  2. void vPortFree( void *pv ); //内存释放函数
  3. void vPortInitialiseBlocks( void ); //初始化内存堆函数
  4. size_t xPortGetFreeHeapSize( void ); //获取当前未分配的内存堆大小
  5. size_t xPortGetMinimumEverFreeHeapSize( void ); //获取未分配的内存堆历史最小值

FreeRTOS 提供的内存管理都是从内存堆中分配内存的。 从前面学习的过程中，我们也知道，创建任务、消息队列、事件等操作都使用到分配内存的函数，这是系统中默认使用内存管理函数从内存堆中分配内存给系统核心组件使用。
对于 heap_1.c、 heap_2.c 和 heap_4.c 这三种内存管理方案，内存堆实际上是一个很大的数组 ， 定义为 static uint8_t ucHeap[ configTOTAL_HEAP_SIZE] ， 而 宏定义configTOTAL_HEAP_SIZE 则表示系统管理内存大小，单位为字， 在 FreeRTOSConfig.h 中由用户设定。
对于 heap_3.c 这种内存管理方案， 它封装了 C 标准库中的 malloc()和 free()函数，封装后的 malloc()和 free()函数具备保护，可以安全在嵌入式系统中执行。因此， 用户需要通过编译器或者启动文件设置堆空间。
heap_5.c 方案允许用户使用多个非连续内存堆空间，每个内存堆的起始地址和大小由用户定义。 这种应用其实还是很大的，比如做图形显示、 GUI 等，可能芯片内部的 RAM是不够用户使用的，需要外部 SDRAM，那这种内存管理方案则比较合适。

23.3.1 heap_1.c

heap_1.c：只申请，不释放。利用率不高。
实际上，大多数的嵌入式系统并不会经常动态申请与释放内存这个内存管理方案实现简洁、安全可靠，使用的非常广泛。
特点：

  1. 用于从不删除任务、队列、信号量、互斥量等的应用程序（实际上大多数使用FreeRTOS 的应用程序都符合这个条件） 。
  2. 函数的执行时间是确定的并且不会产生内存碎片。

heap_1.c 管理方案使用两个静态变量对系统管理的内存进行跟踪内存分配 ：

  1. static size_t xNextFreeByte = ( size_t ) 0;
  2. static uint8_t *pucAlignedHeap = NULL;

变量 xNextFreeByte 用来定位下一个空闲的内存堆位置。 真正的运作过程是记录已经被分配的内存大小，在每次申请内存成功后，都会增加申请内存的字节数目。 因为内存堆际上是一个大数组，我们只需要知道已分配内存的大小，就可以用它作为偏移量找到未分配内存的起始地址。
静态变量 pucAlignedHeap 是一个指向对齐后的内存堆起始地址，我们使用一个数组作为堆内存，但是数组的起始地址并不一定是对齐的内存地址，所以我们需要得到FreeRTOS 管理的内存空间对齐后的起始地址，并且保存在静态变量 pucAlignedHeap 中。为什么要对齐？这是因为大多数硬件访问内存对齐的数据速度会更快。为了提高性能，FreeRTOS 会进行对齐操作，不同的硬件架构的内存对齐操作可能不一样，对于 Cortex-M3架构，进行 8 字节对齐。

1. 内存申请函数pvPortMalloc()

存申请函数就是用于申请一块用户指定大小的内存空间，当系统管理的内存空间满足用户需要的大小的时候，就能申请成功，并且返回内存空间的起始地址。

  1. void *pvPortMalloc( size_t xWantedSize )
  2. {
  3.     void *pvReturn = NULL;
  4.     static uint8_t *pucAlignedHeap = NULL;
  6.     /* 如果内存对齐字节!=1，即申请内存不是 1 字节对齐，
  7.       那么就把要申请的内存大小(xWantedSize)按照要求对齐 */  
  8.     #if( portBYTE_ALIGNMENT != 1 )
  9.     {
  10.         if( xWantedSize & portBYTE_ALIGNMENT_MASK )
  11.         {
  12.             xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
  13.         }
  14.     }
  15.     #endif
  17.     vTaskSuspendAll();
  18.     {
  19.         // 第一次使用，要设置堆也要内存对齐
  20.         if( pucAlignedHeap == NULL )
  21.         {
  22.             pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) );
  23.         }
  25.         // 检测是否溢出  检测输入的内存是不是正数
  26.        /* 边界检测，如果已经使用的内存空间 + 新申请的内存大小 <
  27.        系统能够提供的内存大小，那么就从数组中取一块 */
  28.         if( ( ( xNextFreeByte + xWantedSize ) < configADJUSTED_HEAP_SIZE ) &&
  29.             ( ( xNextFreeByte + xWantedSize ) > xNextFreeByte )    )
  30.         {
  31.             // 返回的地址：基地址 + 已经分配的内存大小
  32.             pvReturn = pucAlignedHeap + xNextFreeByte;
  33.             // 增加xNextFreeByte
  34.             xNextFreeByte += xWantedSize;
  35.         }
  37.         traceMALLOC( pvReturn, xWantedSize );
  38.     }
  39.     ( void ) xTaskResumeAll();
  41.     #if( configUSE_MALLOC_FAILED_HOOK == 1 )
  42.     {
  43.         if( pvReturn == NULL )
  44.         {
  45.             extern void vApplicationMallocFailedHook( void );
  46.             vApplicationMallocFailedHook();
  47.         }
  48.     }
  49.     #endif
  50.     //返回申请成功的内存起始地址
  51.     return pvReturn;
  52. }
  53. /*-----------------------------------------------------------*/
  1. 如果系统要求内存对齐的字节不是按 1 字节对齐，那么就把要申请的内存大小 xWantedSize 按照要求对齐。 举个例子，如果系统设置按 8 字节对齐，我们本来想要申请的内存大小 xWantedSize 是 30 个字节，与 portBYTE_ALIGNMENT_MASK相与的结果是 2， 这代表着我们申请的内存与系统设定对齐不一致， 为了内存统一对齐，系统会再多给我们分配 2 个字节， 也就是 32 个字节。实际上可能我们不应该用到后面的 2个字节，因为我们只申请了30个字节。
  2. 如果内存申请函数是第一次使用，那必须保证堆内存起始地址pucAlignedHeap 也是按照指定内存对齐要求进行对齐，通过这里可以知道，初始化pucAlignedHeap 时并不是一定等于&ucHeap[0]的，而是会根据字节对齐的要求，在&ucHeap[0]和&ucHeap[portBYTE_ALIGNMENT]之间。


在 使 用 内 存 申 请 函 数 之 前 ， 需 要 将 管 理 的 内 存 进 行 初 始 化 ， 需 要 将 变 量pucAlignedHeap 指向内存域第一个地址对齐处，因为系统管理的内存其实是一个大数组，而编译器为这个数组分配的起始地址是随机的，不一定符合系统的对齐要求，这时候要进行内存地址对齐操作。比如数组 ucHeap 的地址从 0x20000123 处开始，系统按照 8 字节对齐，则对齐后系统管理的内存示意图具体见图
image.png
在内存对齐完成后， 用户想要申请一个 30 字节大小的内存，那么按照系统对齐的要求，我们会申请到 32 个字节大小的内存空间，即使我们只需要 30 字节的内存，申请完成的示意图具体见图
image.png

2.其它函数

vPortFree()这个函数其实上面都没做，
因为 heap_1.c 采用的内存管理算法中不支持释放内存。

vPortInitialiseBlocks()仅仅将静态局部变量 xNextFreeByte 设置为 0，表示内存没有被申请。

xPortGetFreeHeapSize()则是获取当前未分配的内存堆大小， 这个函数通常用于检查我们设置的内存堆是否合理，通过这个函数可以估计出最坏情况下需要多大的内存堆，以便合理的节省内存资源。

23.3.2 heap_2.c

heap_2.c 方案与 heap_1.c 方案采用的内存管理算法不一样，它采用一种最佳匹配算法(best fit algorithm)，比如我们申请 100 字节的内存，而可申请内存中有三块对应大小 200 字节， 500 字节和 1000 字节大小的内存块，按照算法的最佳匹配，这时候系统会把 200 字节大小的内存块进行分割并返回申请内存的起始地址，剩余的内存则插回链表留待下次申请。
Heap_2.c 方案支持释放申请的内存， 但是它不能把相邻的两个小的内存块合成一个大的内存块， 对于每次申请内存大小都比较固定的，这个方式是没有问题的，而对于每次申请并不是固定内存大小的则会造成内存碎片， 后面要讲解的 heap_4.c 方案采用的内存管理算法能解决内存碎片的问题，可以把这些释放的相邻的小的内存块合并成一个大的内存块。
通过调用函数 xPortGetFreeHeapSize() 我们可以知道还剩下多少内存没有使用， 但是并不包括内存碎片，这样一来我们可以实时的调整和优化 configTOTAL_HEAP_SIZE 的大小。

heap_2.c的特点：

  1. 可以用在那些反复的删除任务、队列、信号量、等内核对象且不担心内存碎片的应用程序。
  2. 如果我们的应用程序中的队列、任务、信号量、 等工作在一个不可预料的顺序，这样子也有可能会导致内存碎片。
  3. 具有不确定性，但是效率比标准 C 库中的 malloc 函数高得多
  4. 不能用于那些内存分配和释放是随机大小的应用程序。

heap_2.c 方案与 heap_1 方案在内存堆初始化的时候操作都是一样的，在内存中开辟了一个静态数组作为堆的空间，大小由用户定义，
heap_2.c 方案采用链表的数据结构记录空闲内存块，将所有的空闲内存块组成一个空闲内存块链表， FreeRTOS 采用 2 个 BlockLink_t 类型的局部静态变量 xStart、 xEnd 来标识空闲内存块链表的起始位置与结束位置。

  1. typedef struct A_BLOCK_LINK
  2. {
  3.     // 成员变量是指向下一个空闲内存块的指针
  4.     struct A_BLOCK_LINK *pxNextFreeBlock;    /*<< The next free block in the list. */
  5.     // 用于记录申请的内存块的大小，包括链表结构体大小
  6.     size_t xBlockSize;                        /*<< The size of the free block. */
  7. } BlockLink_t;
  1. 系统会先从内存块空闲链表头开始进行遍历，查找符合用户申请大小的内存块（内存块空闲链表按内存块大小升序排列，所以最先返回的的块一定是最符合申请内存大小，所谓的最匹配算法就是这个意思来的）。当找到内存块的时候， 返回该内存块偏移 heapSTRUCT_SIZE 个字节后的地址， 因为在每块内存块前面预留的节点是用于记录内存块的信息， 用户不需要也不允许操作这部分内存。
  2. 在申请内存成功的同时系统还会判断当前这块内存是否有剩余（大于一个链表节点所需内存空间） ， 这样子就表示剩下的内存块还是能存放东西的，也要将其利用起来。 如果有剩余的内存空间， 系统会将内存块进行分割， 在剩余的内存块头部添加一个内存节点，并且完善该空闲内存块的信息，然后将其按内存块大小插入内存块空闲链表中， 供下次分配使用， 其中 prvInsertBlockIntoFreeList() 这个函数就是把节点按大小插入到链表中。

1. 申请

  1. void *pvPortMalloc( size_t xWantedSize )
  2. {
  3.     BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
  4.     static BaseType_t xHeapHasBeenInitialised = pdFALSE;
  5.     void *pvReturn = NULL;
  7.     vTaskSuspendAll();
  8.     {
  9.         // 判断堆是否进行初始化了 
  10.         if( xHeapHasBeenInitialised == pdFALSE )
  11.         {
  12.             // 进行初始化 代码在下面
  13.             // 然后再看示意图就理解了
  14.             prvHeapInit();
  15.             xHeapHasBeenInitialised = pdTRUE;
  16.         }
  18.         // 确定申请的内存是大于0的
  19.         if( xWantedSize > 0 )
  20.         {
  21.             // 算上前面的结构体
  22.             xWantedSize += heapSTRUCT_SIZE;
  24.            /* 需要申请的内存大小与系统要求对齐的字节数不匹配，需要进行内存对齐 */
  25.             if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0 )
  26.             {
  27.                 xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
  28.             }
  29.         }
  31.         //如果当前的空闲内存足够满足用户申请的内存大小，就进行内存申请操作
  32.         if( ( xWantedSize > 0 ) && ( xWantedSize < configADJUSTED_HEAP_SIZE ) )
  33.         {
  34.             /* 从空余内存链表的头部开始找，如果该空余内存的大小>xWantedSize，
  35.             就从这块内存中抠出一部分内存返回，剩余的内存生成新的 BlockLink_t 插入链表中 */
  36.             pxPreviousBlock = &xStart;
  37.             pxBlock = xStart.pxNextFreeBlock;
  38.             //从链表头部开始查找大小符合条件的空余内存
  39.             while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
  40.             {
  41.                 // 保存后面要进行链表的挂接
  42.                 pxPreviousBlock = pxBlock;
  43.                 pxBlock = pxBlock->pxNextFreeBlock;
  44.             }
  46.             /*如果搜索到链表尾 xEnd，说明没有找到合适的空闲内存块，否则进行下一步处理*/
  47.             if( pxBlock != &xEnd )
  48.             {
  49.                 /* 能执行到这里，说明已经找到合适的内存块了，找到内存块，就
  50.                 返回内存块地址，注意了：这里返回的是内存块 +
  51.                 内存块链表结构体空间的偏移地址，因为内存块头部需要有一个空闲链表节点 */
  52.                 pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );
  54.                 /* 因为这个内存块被用户使用了，需要从空闲内存块链表中移除 */
  55.                 pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
  57.                 /* If the block is larger than required it can be split into two. */
  58.                 if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
  59.                 {
  60.                     /*再看看这个内存块的内存空间够不够多，能不能分成两个
  61.                     申请的内存块就给用户，剩下的内存就留出来，
  62.                     放到空闲内存块链表中作为下一次内存块申请。 */
  63.                     pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
  65.                     pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
  66.                     pxBlock->xBlockSize = xWantedSize;
  68.                     // 插入到链表中
  69.                     prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );
  70.                 }
  71.                 // 剩余的容量
  72.                 xFreeBytesRemaining -= pxBlock->xBlockSize;
  73.             }
  74.         }
  76.         traceMALLOC( pvReturn, xWantedSize );
  77.     }
  78.     ( void ) xTaskResumeAll();
  80.     #if( configUSE_MALLOC_FAILED_HOOK == 1 )
  81.     {
  82.         if( pvReturn == NULL )
  83.         {
  84.             extern void vApplicationMallocFailedHook( void );
  85.             vApplicationMallocFailedHook();
  86.         }
  87.     }
  88.     #endif
  90.     return pvReturn;
  91. }
  92. /*-----------------------------------------------------------*/
  1. // 堆内存的初始化
  2. static void prvHeapInit( void )
  3. {
  4.     BlockLink_t *pxFirstFreeBlock;
  5.     uint8_t *pucAlignedHeap;
  7.     // 内存对齐
  8.     pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) );
  10.     // 开始指向堆内存的初始地址
  11.     xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
  12.     // 设置大小为0
  13.     xStart.xBlockSize = ( size_t ) 0;
  15.     // 堆内存的最后，设置大小为堆内存的大小
  16.     xEnd.xBlockSize = configADJUSTED_HEAP_SIZE;
  17.     xEnd.pxNextFreeBlock = NULL;
  19.     // 设置第一个位置struct
  20.     pxFirstFreeBlock = ( void * ) pucAlignedHeap;
  21.     // 设置为栈的大小
  22.     pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE;
  23.     // 设置结束的指针是xEnd
  24.     pxFirstFreeBlock->pxNextFreeBlock = &xEnd;
  25. }

image.png
随着内存申请， 越来越多申请的内存块脱离空闲内存链表， 但链表仍是以 xStart 节点开头以 xEnd 节点结尾， 空闲内存块链表根据空闲内存块的大小进行排序。每当用户申请一次内存的时候，系统都要分配一个 BlockLink_t 类型结构体空间，用于保存申请的内存块信息，并且每个内存块在申请成功后会脱离空闲内存块链表，申请两次后的内存示意图具体见图
image.png

2.内存释放函数

  1. void vPortFree( void *pv )
  2. {
  3.     // 要释放的内存
  4.     uint8_t *puc = ( uint8_t * ) pv;
  5.     BlockLink_t *pxLink;
  7.     // 确定不是空的
  8.     if( pv != NULL )
  9.     {
  10.         // 找到任务控制块的位置
  11.         puc -= heapSTRUCT_SIZE;
  13.         // 这个就是任务控制块
  14.         pxLink = ( void * ) puc;
  16.         vTaskSuspendAll();
  17.         {
  18.             // 添加到链表中
  19.             prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
  20.             // 
  21.             xFreeBytesRemaining += pxLink->xBlockSize;
  22.             traceFREE( pv, pxLink->xBlockSize );
  23.         }
  24.         ( void ) xTaskResumeAll();
  25.     }
  26. }

image.png
image.png
链表单插入

  1. #define prvInsertBlockIntoFreeList( pxBlockToInsert )                                \
  2. {                                                                                    \
  3.     BlockLink_t *pxIterator;                                                            \
  4.     size_t xBlockSize;                                                                    \
  5.                                                                                     \
  6.     xBlockSize = pxBlockToInsert->xBlockSize;                                        \
  7.                                                                                     \
  8.                                     \
  9.     for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock )    \
  10.     {                                                                                \
  12.     }                                                                                \
  13.                                                                                     \                                                    \
  14.     pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;                    \
  15.     pxIterator->pxNextFreeBlock = pxBlockToInsert;                                    \
  16. }

从内存的申请与释放看来， heap_2.c 方案采用的内存管理算法虽然是高效但还是有缺陷的，由于在释放内存时不会将相邻的内存块合并，所以这可能造成内存碎片，当然并不是说这种内存管理算法不好，只不过对使用的条件比较苛刻，要求用户每次创建或释放的任务、队列等必须大小相同如果分配或释放的内存是随机的，绝对不可以用这种内存管理策略；如果申请和释放的顺序不可预料，那也很危险。举个例子， 假设用户先申请 128 字节内存，然后释放，此时系统释放的 128 字节内存可以重复被利用； 如果用户再接着申请64k 的字节内存，那么一个本来 128 字节的大块就会被分为两个 64 字节的小块，如果这种情况经常发生，就会导致每个空闲块都可能很小，最终在申请一个大块时就会因为没有合适的空闲内存块而申请失败，这并不是因为总的空闲内存不足，而是无法申请到连续可以的大块内存。

23.3.3 heap_3.c

heap_3.c 方案只是简单的封装了标准 C 库中的 malloc()和 free()函数， 并且能满足常用的编译器。 重新封装后的 malloc()和 free()函数具有保护功能，采用的封装方式是操作内存前挂起调度器、完成后再恢复调度器。
特点：

  1. 需要链接器设置一个堆， malloc()和 free()函数由编译器提供。
  2. 具有不确定性。
  3. 可能增大 RTOS 内核的代码大小。

在 STM32 系列的工程中， 这个由编译器定义，的堆都在启动文件里面设置， 单位为字节，我们具体以 STM32F10x 系列为例， 具体见图23-7。而其它系列的都差不多。
image.png
比较简单：

  1. void *pvPortMalloc( size_t xWantedSize )
  2. {
  3.     void *pvReturn;
  5.     vTaskSuspendAll();
  6.     {
  7.         pvReturn = malloc( xWantedSize );
  8.         traceMALLOC( pvReturn, xWantedSize );
  9.     }
  10.     ( void ) xTaskResumeAll();
  12.     #if( configUSE_MALLOC_FAILED_HOOK == 1 )
  13.     {
  14.         if( pvReturn == NULL )
  15.         {
  16.             extern void vApplicationMallocFailedHook( void );
  17.             vApplicationMallocFailedHook();
  18.         }
  19.     }
  20.     #endif
  22.     return pvReturn;
  23. }
  24. /*-----------------------------------------------------------*/
  26. void vPortFree( void *pv )
  27. {
  28.     if( pv )
  29.     {
  30.         vTaskSuspendAll();
  31.         {
  32.             free( pv );
  33.             traceFREE( pv, 0 );
  34.         }
  35.         ( void ) xTaskResumeAll();
  36.     }
  37. }

23.3.3.4 heap_4.c

heap_4.c 方案与 heap_2.c 方案一样都采用最佳匹配算法来实现动态的内存分配，但是不一样的是 heap_4.c 方案还包含了一种合并算法，能把相邻的空闲的内存块合并成一个更大的块，这样可以减少内存碎片。
heap_4.c 方案的空闲内存块也是以单链表的形式连接起来的， BlockLink_t 类型的局部静态变量 xStart 表示链表头，但 heap_4.c 内存管理方案的链表尾部则保存在内存堆空间最后位置，并使用 BlockLink_t 指针类型局部静态变量 pxEnd 指向这个区域（而 heap_2.c 内存管理方案则使用 BlockLink_t 类型的静态变量 xEnd 表示链表尾） 。
heap_4.c 内存管理方案的空闲块链表不是以内存块大小进行排序的，而是以内存块起始地址大小排序， 内存地址小的在前，地址大的在后，因为 heap_4.c 方案还有一个内存合并算法，在释放内存的时候，假如相邻的两个空闲内存块在地址上是连续的，那么就可以合并为一个内存块， 这也是为了适应合并算法而作的改变。
特点：

  1. 可用于重复删除任务、队列、信号量、互斥量等的应用程序
  2. 可用于分配和释放随机字节内存的应用程序， 但并不像 heap2.c 那样产生严重的内
    存碎片。
  3. 具有不确定性，但是效率比标准 C 库中的 malloc 函数高得多。

1.内存申请函数 pvPortMalloc()

  1. 遍历查找可用内存卡
  2. 剩下的生成一个新的内存块，按地址顺序插入
  3. 进行合并算法看内存是否可以合并

通过上面的方式减少内存碎片。
注意：内存对齐的时候要思考好方向。

  1. void *pvPortMalloc( size_t xWantedSize )
  2. {
  3.     BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
  4.     void *pvReturn = NULL;
  6.     vTaskSuspendAll();
  7.     {
  8.         // 第一次执行 需要进行初始化
  9.         if( pxEnd == NULL )
  10.         {
  11.             prvHeapInit();
  12.         }
  13.         else
  14.         {
  15.             mtCOVERAGE_TEST_MARKER();
  16.         }
  18.         /* 这里 xWantedSize 的大小有要求，需要最高位为 0
  19.         因为后面 BlockLink_t 结构体中的 xBlockSize 的最高位需要使用
  20.         这个成员的最高位被用来标识这个块是否空闲。因此要申请的块大小不能使用这个位
  21.         */
  23.         if( ( xWantedSize & xBlockAllocatedBit ) == 0 )
  24.         {
  25.             // 设置申请为正数
  26.             if( xWantedSize > 0 )
  27.             {
  28.                 // 需要的数量 要加上前面链表的长度 一共是总的大小
  29.                 xWantedSize += xHeapStructSize;
  31.                 // 确保内存对齐
  32.                 if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
  33.                 {
  34.                     /* Byte alignment required. */
  35.                     xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
  36.                     configASSERT( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) == 0 );
  37.                 }
  38.                 else
  39.                 {
  40.                     mtCOVERAGE_TEST_MARKER();
  41.                 }
  42.             }
  43.             else
  44.             {
  45.                 mtCOVERAGE_TEST_MARKER();
  46.             }
  48.             // 还有剩余的空间
  49.             if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
  50.             {
  51.                 /* 从空余内存链表的头部开始找，如果该空余内存的大小>xWantedSize，
  52.                 就从这块内存中抠出一部分内存返回，剩余的内存生成新的 BlockLink_t 插入链表中
  53.                 */
  54.                 pxPreviousBlock = &xStart;
  55.                 pxBlock = xStart.pxNextFreeBlock;
  56.                 //从链表头部开始查找大小符合条件的空余内存
  57.                 while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
  58.                 {
  59.                     // 保存是为了后面链表的连接
  60.                     pxPreviousBlock = pxBlock;
  61.                     pxBlock = pxBlock->pxNextFreeBlock;
  62.                 }
  64.                 //如果搜索到链表尾 xEnd，说明没有找到合适的空闲内存块，否则进行下一步处
  65.                 if( pxBlock != pxEnd )
  66.                 {
  67.                     /* 能执行到这里，说明已经找到合适的内存块了，找到内存块，就
  68.                     返回内存块地址，注意了：这里返回的是内存块 +
  69.                     内存块链表结构体空间的偏移地址，因为内存块头部需要有一个空闲
  70.                     链表节点*/
  71.                     pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
  73.                     //* 因为这个内存块被用户使用了，需要从空闲内存块链表中移除 */
  74.                     pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
  76.                     /*再看看这个内存块的内存空间够不够多，能不能分成两个， */
  77.                     if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
  78.                     {
  79.                         /* 去除分配出去的内存，在剩余内存块的起始位置放置一个链表节点*/
  80.                         pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) 
  81.                                                      + xWantedSize );
  82.                         configASSERT( ( ( ( size_t ) pxNewBlockLink ) 
  83.                                        & portBYTE_ALIGNMENT_MASK ) == 0 );
  85.                         /* 通过计算得到剩余的内存大小，并且赋值给剩余内存块链表节点中
  86.                         的 xBlockSize 成员变量，方便下一次的内存查找 */
  87.                         pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
  88.                         pxBlock->xBlockSize = xWantedSize;
  90.                         /* 将被切割而产生的新空闲内存块添加到空闲链表中 */
  91.                         prvInsertBlockIntoFreeList( pxNewBlockLink );
  92.                     }
  93.                     else
  94.                     {
  95.                         mtCOVERAGE_TEST_MARKER();
  96.                     }
  97.                     //更新剩余内存总大小
  98.                     xFreeBytesRemaining -= pxBlock->xBlockSize;
  100.                     //如果当前内存大小小于历史最小记录，更新历史最小内存记录
  101.                     if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
  102.                     {
  103.                         xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
  104.                     }
  105.                     else
  106.                     {
  107.                         mtCOVERAGE_TEST_MARKER();
  108.                     }
  110.                     /* 注意这里的 xBlockSize 的最高位被设置为 1，标记内存已经被申请使用*/
  111.                     pxBlock->xBlockSize |= xBlockAllocatedBit;
  112.                     pxBlock->pxNextFreeBlock = NULL;
  113.                 }
  114.                 else
  115.                 {
  116.                     mtCOVERAGE_TEST_MARKER();
  117.                 }
  118.             }
  119.             else
  120.             {
  121.                 mtCOVERAGE_TEST_MARKER();
  122.             }
  123.         }
  124.         else
  125.         {
  126.             mtCOVERAGE_TEST_MARKER();
  127.         }
  129.         traceMALLOC( pvReturn, xWantedSize );
  130.     }
  131.     ( void ) xTaskResumeAll();
  133.     #if( configUSE_MALLOC_FAILED_HOOK == 1 )
  134.     {
  135.         if( pvReturn == NULL )
  136.         {
  137.             extern void vApplicationMallocFailedHook( void );
  138.             vApplicationMallocFailedHook();
  139.         }
  140.         else
  141.         {
  142.             mtCOVERAGE_TEST_MARKER();
  143.         }
  144.     }
  145.     #endif
  147.     configASSERT( ( ( ( size_t ) pvReturn ) & ( size_t ) portBYTE_ALIGNMENT_MASK ) == 0 );
  148.     return pvReturn;
  149. }
  150. /*-----------------------------------------------------------*/

初始化

  1. static void prvHeapInit( void )
  2. {
  3.     BlockLink_t *pxFirstFreeBlock;
  4.     uint8_t *pucAlignedHeap;
  5.     size_t uxAddress;
  6.     size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;
  8.     /* 要确保内存对齐 */
  9.     uxAddress = ( size_t ) ucHeap;
  11.     /* 如果内存没有对齐  */
  12.     if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
  13.     {
  14.         // 进行内存对齐
  15.         uxAddress += ( portBYTE_ALIGNMENT - 1 );
  16.         uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
  17.         // xTotalHeapSize 表示系统管理的总内存大小
  18.         xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;
  19.     }
  21.     // 对齐的地址
  22.     pucAlignedHeap = ( uint8_t * ) uxAddress;
  24.     //初始化链表头部
  25.     xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
  26.     xStart.xBlockSize = ( size_t ) 0;
  28.     /* 初始化 pxEnd，计算 pxEnd 的位置，它的值为内存尾部向前偏移一个
  29.     BlockLink_t 结构体大小，偏移出来的这个 BlockLink_t 就是 pxEnd */
  30.     uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
  31.     uxAddress -= xHeapStructSize;
  32.     uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
  33.     pxEnd = ( void * ) uxAddress;
  34.     pxEnd->xBlockSize = 0;
  35.     pxEnd->pxNextFreeBlock = NULL;
  37.     /* 和 heap_2.c 中的初始化类似，将当前所有内存插入空闲内存块链表中。
  38.     不同的是链表的尾部不是静态的，而是放在了内存的最后。 */
  39.     pxFirstFreeBlock = ( void * ) pucAlignedHeap;
  40.     pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;
  41.     pxFirstFreeBlock->pxNextFreeBlock = pxEnd;
  43.     /* 更新统计变量 */
  44.     xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
  45.     xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
  47.     /* 这个 xBlockAllocatedBit 比较特殊，这里被设置为最高位为 1 其余为 0 的
  48.     一个 size_t 大小的值，这样任意一个 size_t 大小的值和 xBlockAllocatedBit
  49.     进行按位与操作,如果该值最高位为 1，那么结果为 1，否则结果为 0，
  50.     FreeRTOS 利用这种特性标记一个内存块是否空闲的 */
  51.     xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
  52. }

初始化完成示意图：
image.png
链表插入：

  1. static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert )
  2. {
  3.     BlockLink_t *pxIterator;
  4.     uint8_t *puc;
  6.     /* Iterate through the list until a block is found that has a higher address
  7.     than the block being inserted. */
  8.     /* 首先找到和 pxBlockToInsert 相邻（比当前块的地址要高）的前一个空闲内存 */
  9.     for( pxIterator = &xStart; 
  10.         pxIterator->pxNextFreeBlock < pxBlockToInsert; 
  11.         pxIterator = pxIterator->pxNextFreeBlock )
  12.     {
  13.         /* Nothing to do here, just iterate to the right position. */
  14.     }
  17.     puc = ( uint8_t * ) pxIterator;
  18.     /* 如果前一个内存的尾部恰好是 pxBlockToInsert 的头部，
  19.         那代表这两个内存是连续的，可以合并*/
  20.     if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
  21.     {
  22.         /* 将 pxBlockToInsert 合并入 pxIterator 中 */
  23.         pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
  24.         pxBlockToInsert = pxIterator;
  25.     }
  26.     else
  27.     {
  28.         mtCOVERAGE_TEST_MARKER();
  29.     }
  31.     /* 判断 pxBlockToInsert 是否和后面的空闲内存相邻 */
  32.     puc = ( uint8_t * ) pxBlockToInsert;
  33.     if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
  34.     {
  35.         /* 与之相邻的下一个内存块不是链表尾节点 */
  36.         if( pxIterator->pxNextFreeBlock != pxEnd )
  37.         {
  38.             /* 将后面的内存合入 pxBlockToInsert，
  39.             并用 pxBlockToInsert 代替该内存在链表中的位置 */
  40.             pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
  41.             pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
  42.         }
  43.         else
  44.         {
  45.             pxBlockToInsert->pxNextFreeBlock = pxEnd;
  46.         }
  47.     }
  48.     else
  49.     {
  50.         //后面不相邻，那么只能插入链表了
  51.         pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
  52.     }
  54.     /* 判断下前面是否已经合并了，如果合并了，就不用再更新链表了 */
  55.     if( pxIterator != pxBlockToInsert )
  56.     {
  57.         pxIterator->pxNextFreeBlock = pxBlockToInsert;
  58.     }
  59.     else
  60.     {
  61.         mtCOVERAGE_TEST_MARKER();
  62.     }
  63. }

内存合并的情况：
image.png
image.png
内存对齐小总结：

  1. 上面，低地址对齐： uxAddress += ( portBYTE_ALIGNMENT - 1 );

    1.                  uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );

  2. 字节对齐： xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );

  3. 后面：尾对齐： uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );

23. 内存管理 - 图11

2. 内存释放函数vPortFree()

heap_4.c 内存管理方案的内存释放函数 vPortFree()也比较简单， 根据传入要释放的内存块地址，偏移之后找到链表节点，然后将这个内存块插入到空闲内存块链表中，在内存块插入过程中会执行合并算法，这个我们已经在内存申请中讲过了（而且合并算法多用于释放内存中） 。最后是将这个内存块标志为“空闲” （内存块节点的 xBlockSize 成员变量最高位清 0）、再更新未分配的内存堆大小即可， 

  1. void vPortFree( void *pv )
  2. {
  3. uint8_t *puc = ( uint8_t * ) pv;
  4. BlockLink_t *pxLink;
  6.     if( pv != NULL )
  7.     {
  8.         // 获取头结构体
  9.         puc -= xHeapStructSize;
  11.         /* This casting is to keep the compiler from issuing warnings. */
  12.         pxLink = ( void * ) puc;
  14.         configASSERT( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 );
  15.         configASSERT( pxLink->pxNextFreeBlock == NULL );
  17.         // !0 确实是被使用了
  18.         if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
  19.         {
  20.             if( pxLink->pxNextFreeBlock == NULL )
  21.             {
  22.                 // 清零标志位
  23.                 pxLink->xBlockSize &= ~xBlockAllocatedBit;
  25.                 vTaskSuspendAll();
  26.                 {
  27.                     // 更新参数
  28.                     xFreeBytesRemaining += pxLink->xBlockSize;
  29.                     traceFREE( pv, pxLink->xBlockSize );
  30.                     // 添加到List里面
  31.                     prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
  32.                 }
  33.                 ( void ) xTaskResumeAll();
  34.             }
  35.             else
  36.             {
  37.                 mtCOVERAGE_TEST_MARKER();
  38.             }
  39.         }
  40.         else
  41.         {
  42.             mtCOVERAGE_TEST_MARKER();
  43.         }
  44.     }
  45. }
  46. /*-----------------------------------------------------------*/

按照内存释放的过程，当我们释放一个内存时，如果与它相邻的内存块都不是空闲的，那么该内存块并不会合并，只会被添加到空闲内存块链表中，其过程示意图具体见图。而如果某个时间段释放了另一个内存块，发现该内存块前面有一个空闲内存块与它在地址上是连续的，那么这两个内存块会合并成一个大的内存块，并插入空闲内存块链表中。
image.png
image.png

23.3.5 heap_5.c

heap_5.c 方案在实现动态内存分配时与 heap4.c 方案一样， 采用最佳匹配算法和合并算法，并且允许内存堆跨越多个非连续的内存区，也就是允许在不连续的内存堆中实现内存分配，比如用户在片内 RAM 中定义一个内存堆，还可以在外部 SDRAM 再定义一个或多个内存堆，这些内存都归系统管理。
heap_5.c 方案通过调用 vPortDefineHeapRegions()函数来实现系统管理的内存初始化，
在内存初始化未完成前不允许使用内存分配和释放函数。 如创建 FreeRTOS 对象（任务、队列、信号量等）时会隐式的调用 pvPortMalloc()函数，因此必须注意：使用 heap_5.c 内存管理方案创建任何对象前，要先调用 vPortDefineHeapRegions()函数将内存初始化。
vPortDefineHeapRegions()函数只有一个形参， 该形参是一个 HeapRegion_t 类型的结构体数组。 HeapRegion_t 类型结构体在 portable.h 中定义 

  1. typedef struct HeapRegion {
  2.     /* 用于内存堆的内存块起始地址*/
  3.     uint8_t *pucStartAddress;
  4.     /* 内存块大小 */
  5.     size_t xSizeInBytes;
  6. }HeapRegion_t;

用 户 需 要指 定每 个 内存 堆 区域 的起 始 地址 和 内存 堆大 小 、将 它 们放 在一 个HeapRegion_t 结构体类型数组中， 这个数组必须用一个 NULL 指针和 0 作为结尾，起始地址必须从小到大排列。假设我们为内存堆分配两个内存块，第一个内存块大小为 0x10000字节，起始地址为 0x80000000；第二个内存块大小为 0xa0000 字节，起始地址为0x90000000， vPortDefineHeapRegions()函数使用实例具体 

  1. /* 在内存中为内存堆分配两个内存块。
  2. 第一个内存块大小为 0x10000 字节,起始地址为 0x80000000,
  3. 第二个内存块大小为 0xa0000 字节,起始地址为 0x90000000。
  4.  起始地址为 0x80000000 的内存块的起始地址更低,因此放到了数组的第一个位置。 */
  5. const HeapRegion_t xHeapRegions[] = {
  6.     { ( uint8_t * ) 0x80000000UL, 0x10000 },
  7.     { ( uint8_t * ) 0x90000000UL, 0xa0000 },
  8.     { NULL, 0 } /* 数组结尾 */
  9. };
  10. /* 向函数 vPortDefineHeapRegions()传递形参 */
  11.  vPortDefineHeapRegions( xHeapRegions );

用户在自定义好内存堆数组后，需要调用 vPortDefineHeapRegions()函数初始化这些内存堆，系统会已一个空闲内存块链表的数据结构记录这些空闲内存，链表以 xStart 节点构开头，以 pxEnd 指针指向的位置结束。 vPortDefineHeapRegions()函数对内存的初始化与heap_4.c 方案一样，
image.png
而对于 heap_5.c 方案的内存申请与释放函数，其实与 heap_4.c 方案是一样的