FreeRTOS的内存分配heap_1/2/3/4

http://blog.csdn.net/u014381531/article/details/38623641

内存管理是一个操作系统的重要组成部分之一，所有应用程序都离不开操作系统的内存管理。因此，在剖析FreeRTOS的内核代码之前，前对FreeRTOS的内存管理进行研究。

    现在以FreeRTOS8.0.1进行剖析研究。参考资料为《Using the FreeRTOS Real Time Kernel-A Practical Guide opened》。

    Heap_1.c的注释说明，Heap_1.c只是简单地实现了pvPortMalloc()这一个函数，这个堆的实现方案并不允许已分配的内存再次被释放。（The simplest possible implementation of pvPortMalloc(). Note that this implementation does NOT allow allocated memory to be freed again.）

 

/* Allocate the memory for the heap. */
static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
static size_t xNextFreeByte = ( size_t ) 0;

 

    首先看到的是两个全局变量。第一个是ucHeap，第二个是xNextFreeByte。根据名字的意思可以看出，ucHeap就是FreeRTOS可以用的整个堆的空间数组，其大小是在FreeRTOSConfig.h中定义的常量configTOTAL_HEAP_SIZE，默认是17*1024，即17KB；而xNextFreeByte，则是指向下一个还没被用上的内存堆所在的数组下标，由于一开始整个堆都没被用上，所以它的默认值为0。

    接下来要分析的是void *pvPortMalloc( size_t xWantedSize )这一个函数。这个函数是Heap_1.c的重点。它的工作流程如下：

    第一步：对齐处理；第二步：分配内存；第三步：勾子函数调用。

    第一步的代码如下：

 

/* 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

 

    在说这一部分的时候，要先看看portmacro.h中的一个常量portBYTE_ALIGNMENT，这个常量指示字节对齐数，其默认值为8，即默认以8个字节进行内存对齐。第二个要看的是portable.h中的一个常量portBYTE_ALIGNMENT_MASK，这个常量是根据portBYTE_ALIGNMENT的值进行定义的，其对应关系如下：

portBYTE_ALIGNMENT	portBYTE_ALIGNMENT_MASK
8（表示以8个字节对齐）	0x0007
4（表示以4个字节对齐）	0x0003
2（表示以2个字节对齐）	0x0001
1（表示以1个字节对齐）	0x0000

    备注：在移植的时候，可以根据硬件平台的对齐方式修改portBYTE_ALIGNMENT，这样可以避免内存空间的浪费。

    第一步的工作主要是将用户所需要的内存空间大小进行对齐。如果是以1个字节对齐，则这一步可以跳过（条件编译）。条件编译内部，if( xWantedSize & portBYTE_ALIGNMENT_MASK )主要是用来判断用户所需要的内存大小是否已对齐，例如，在默认情况下（以8个字节对齐），如果用户申请的内存大小为13个字节，经过和字节对齐掩码进行与操作后的结果为0x0005，即没有对齐；如果用户申请的内存大小为16个字节，经过和字节对齐掩码进行与操作后的结果为0x0000，即已经对齐。

    字节对齐的方法在if语块里。可以发现用户申请内存大小和字节对齐掩码进行与操作后，其结果和需要补齐的字节数相加，刚好等于字节对齐掩码的值，因此只要用掩码值减去与操作的结果，就可以得到需要补齐的字节数，这样只要把补齐的字节数加到用户申请的内存大小就可以使其字节对齐。

 

    第二步就是真正在堆中分配内存了。在分配内存一开始的时候，系统首先调用vTaskSuspendAll()将所有的任务都挂起，以防止上下文切换。这个函数在这里只是为了确保内存分配过程不被其它中断打断，具体的实现流程以后再慢慢分析，这里就不详细展开了。紧接着，系统要对这个堆进行对齐工作。这里的对齐和上面说的对齐不是一回事。这里说的对齐是因为FreeRTOS管理的堆是一个全局数组，并不能保证数组首地址按portBYTE_ALIGNMENT对齐。因此FreeRTOS对堆首地址做了这个对齐处理。要留意的是，这个对齐处理只做了一次。原因是对齐后的堆首地址是一个静态变量，初始值赋为NULL。而当这个变量为NULL时才进行对齐处理，对齐处理后这个变量就指向堆首地址，这样在下一次调用pvPortMalloc()时就不会再进行对齐处理了。对齐处理的代码如下。

 

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 ) );
}

 

    一开始看这段代码的时候我还是有点迷惑的，为什么要用&ucHeap[ portBYTE_ALIGNMENT ]进行与运算面不是用&ucHeap[ 0 ]呢？可以考虑以下的这种情况，假如堆数组地址为0x00000006，在默认情况下（portBYTE_ALIGNMENT=8）pucAlignedHeap的结果为0x00000000，但这个地址已经超出了堆数组的地址范围了，这样就容易修改内存其它地址上的值了。因此，用&ucHeap[ portBYTE_ALIGNMENT ]进行运算是为了最后的运算结果还是在堆数组地址的范围内。

    但是另一方面，FreeRTOS对堆数组进行地址对齐操作，这样的后果就是要是原本堆数组首地址没有对齐，则进行对齐操作后就会使堆大小改变了。因此，FreeRTOS对堆数组的大小进行重新定义。

 

/* A few bytes might be lost to byte aligning the heap start address. */
    #define configADJUSTED_HEAP_SIZE    ( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )

 

    在Heap_1模型中，堆的模型如下图所示：

 

 

    由于分配出去的内存空间不需要回收，因此每一次分配空间的时候只需要按需要的内存大小在空闲空间上分割出来就可以了。分割时，首先要检查需要的内存大小有没有超出空闲空间的大小，还要检查假如分配完空间后，其末地址是否溢出。假如没有超出空闲空间大小，出没有发生内存溢出现象，才进行分配，记录新分配空间的首地址到pvReturn，并重新记录新的空闲空间的首地址经NextFreeByte。代码如下：

 

/* 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 );

 

    代码最后的traceMALLOC( pvReturn, xWantedSize )是一个宏，用于输出内存分配的调试信息，这个宏定义在FreeRTOS.h中，默认为空，如果需要将这些调试信息输出到串口或其它东西，就可以修改这个宏将信息输出到所需要的地方。

    到这里，分配内存的过程就几乎结束了，所以在第二步的最后就要调用xTaskResumeAll()将所有挂起的任务重新恢复。

    当然，并不是所有的内存分配过程都会成功的，当内存分配失败的时候，如果在FreeRTOS.h中有定义宏configUSE_MALLOC_FAILED_HOOK=1，则会调用一个勾子函数vApplicationMallocFailedHook()。在这个勾子函数中，用户可以进行其它一些必要的操作，这里就不展开描述了。

    最后的最后，就是返回新分配内存的首地址pvReturn。如果分配失败则pvReturn就为NULL。

    到这里，整个pvPortMalloc()的工作流程就结束了。

 

    由于Heap_1的模型是只分配不回收，因此对于vPortFree()里的实现则是什么都不干。vPortInitialiseBlocks()则只是初始化xNextFreeByte而已。还有xPortGetFreeHeapSize()也只是用于返回剩余内存空间的大小而已，非常简单，也不用细讲了。

 

总结：这是我第一次写的技术笔记，原本是想先剖析LwIP，然后再剖析FreeRTOS的。不过发现自己对TCP/IP的认识还不够深，对LwIP的好多代码还看不懂，因此还是先从FreeRTOS开始吧。希望接下来我能够坚持，把FreeRTOS的整个代码剖析完毕。我想对FreeRTOS进行剖析，不仅要剖析它的代码是怎么写的，还要剖析它的代码为什么要这样写的。感觉这个还是挻有价值的，毕竟FreeRTOS是一个免费的嵌入式操作系统，要是剖析之后能够对它进行优化，则对以后做产品有一个很大的帮助。呃，就这样吧。

---

http://blog.csdn.net/u014381531/article/details/38642139

 

在FreeRTOS8.0.1这个版本中，一共有四个内存堆模型。这一次讲的就是第二个模型Heap_2.c。从一开始就可以看到注释中对Heap_2的模型解释：这是对pvPortMalloc()和vPortFree()的简单实现，除了可以分配内存之外，还可以对已分配的内存进行回收，但相邻空闲块不会进行合并，因此会造成一定的内存碎片。（A sample implementation of pvPortMalloc() and vPortFree() that permits allocated blocks to be freed, but does not combine adjacent free blocks into a single larger block (and so will fragment memory).）

    在Heap_2中，由于开始支持对内存进行回收，因此FreeRTOS以空闲块对内存堆进行管理，并且使用了最佳适配算法(best fit algorithm)去进行内存的分配。

    首先，还是由内存中开辟一个静态数组ucHeap[ configTOTAL_HEAP_SIZE ]作为FreeRTOS的内存堆。同样也会因为对齐的原因FreeRTOS对内存堆的可用空间进行了调整，并定义了常量configADJUSTED_HEAP_SIZE。（具体已在上一篇《内存管理Heap_1.c》中介绍）

    接下来可以留意Heap_2.c中最重要的结构struct A_BLOCK_LINK。由于FreeRTOS用空闲块对内存堆进行管理，于是用这一个结构来形成一条空闲块链表对空闲块进行组织和管理。

 

/* Define the linked list structure. This is used to link free blocks in order  of their size. */
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;

    这个结构有两个成员，第一个是节点Next指针pxNextFreeBlock，第二个是空闲块大小。一个空闲块就用这样的一个结构节点表示，所有节点通过Next指针形成一条空闲块链表。FreeRTOS还定义了这个链表的头xStart和尾xEnd。

 

/* Create a couple of list links to mark the start and end of the list. */
static BlockLink_t xStart, xEnd;

   与Heap_1不同，在Heap_2中会有一个堆初始化的过程prvHeapInit()。这一个过程被pvPortMalloc()调用，但只被调用一次。主要还是对内存堆进行对齐还有对空闲块表进行初始化工作。下面是它的工作流程。

    首先，初始化流程对整个内存堆进行地址对齐工作。对齐的原因的原理与Heap_1一样。

 

/* Ensure the heap starts on a correctly aligned boundary. */
pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ( portPOINTER_SIZE_TYPE ) ~portBYTE_ALIGNMENT_MASK ) );

 

    在获取到地址对齐后的内存堆首地址之后，就要对空闲块链表进行初始化。留意，xStart是链表头，并不表示一个空闲块，xEnd是链表尾，也不表示一个空闲块，但记录着整个堆的大小。其代码如下：

 

/* xStart is used to hold a pointer to the first item in the list of free
blocks. The void cast is used to prevent compiler warnings. */
xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
xStart.xBlockSize = ( size_t ) 0;

/* xEnd is used to mark the end of the list of free blocks. */
xEnd.xBlockSize = configADJUSTED_HEAP_SIZE;
xEnd.pxNextFreeBlock = NULL;

/* To start with there is a single free block that is sized to take up the
entire heap space. */
pxFirstFreeBlock = ( void * ) pucAlignedHeap;
pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE;
pxFirstFreeBlock->pxNextFreeBlock = &xEnd;

 

    经过上面的初始化流程后，整个链表如下图所示。注意，xStart和xEnd是存在于静态存储区中，并不在FreeRTOS申请的内存堆数组中，但初始时第一个节点却在内存堆数组中。我用的编译器是Keil MDK 5.11，并且将FreeRTOS移植到STM32上，因此一个A_BLOCK_LINK的大小为8个字节。

 

 

    整个初始化的流程就完成了。接下来看看pvPortMalloc()分配内存的流程。如Heap_1一样，在真正开始分配内存时，用vTaskSuspendAll()挂起所有任务，防止分配内存的过程被中断，确保操作的原子性。紧接着，如果是第一次调用pvPortMalloc()，则调用prvHeapInit()对内存堆和空闲块链表进行初始化。由于在Heap_2中将内存堆用空闲块处理，因此用户每申请一次内存，FreeRTOS都会在申请的空间前加上空闲块头部BlockLink_t，用于记录分配出去的空间的大小。因此，真正要分配的内存空间大小就等于用户申请的内存空间大小加上空闲块头部的大小。加上头部之后，还要对整个大小进行对齐。因此，在真正分配空间之前，FreeRTOS都对用户申请的空间大小进行了调整。如下面的代码所示。

 

/* The wanted size is increased so it can contain a BlockLink_t
structure in addition to the requested amount of bytes. */
if( xWantedSize > 0 )
{
 xWantedSize += heapSTRUCT_SIZE;

 /* Ensure that blocks are always aligned to the required number of bytes. */
 if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0 )
 {
  /* Byte alignment required. */
  xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
 }
}

    在这一段代码里，有一个地方要注意的就是这里用到的空闲块头部并不是直接sizeof(BlockLink_t)，而是heapSTRUCT_SIZE，这个常量也定义在Heap_2.c中，这是对空闲块头部的大小再进行了一次大小对齐。

    接下来做了一个分配判断。xWantedSize0，还看得我很迷糊的。本来xWantedSize就是unsigned int，是大于等于0的，一下子没有留意到等于0是什么情况。等于0，就是加上空闲块头之后的大小变为0了？这是神马情况？！看来这个判断条件很另人费解啊。过了分配判断之后，接下来就是best fit algorithm的实现了。在这里，空闲块的大小是按从小到大的顺序排列的。因此，遍历链表，找到第一块比申请空间大的空闲块即为最合适的空闲块。然后返回这个空闲块头后的首地址。注意，一定是空闲块头后的首地址哦，要是直接将空闲块的首地址返回的话，那用户就会将空闲块头修改了。另一个要注意的地方是，要是分配出去的空闲块的剩余空间要是比两倍的空闲块头还要大，则将分配出去的这个空闲块分割剩余的空间出来，重新放到空闲块链表中。例如，初始化后只有一个空闲块，这个空闲块大小为17KB。经过调整后的用户申请空间大小为1KB，则FreeRTOS就从这个空闲块靠近块首的地方分割出1KB出来分配出去，剩余的16KB则重新放回空闲块链表里。以便下一次继续分配。这一个切割空闲块的代码如下。

 

/* 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 ) );
}

    在上面的一段代码里，有一个值得注意的宏prvInsertBlockIntoFreeList()。这个宏的作用是将空闲块重新添加到空闲块链表中。注意，并不能将分割出来的空闲块放到原空闲块的位置中，因为链表中的空闲块是按从小到大的顺序排列的，这个宏的作用就是将新空闲块插入到合适的链表位置中。这是一个简单的链表操作，非常简单，也不必详细说明了。这个宏的具体代码如下。

 

/*
 * Insert a block into the list of free blocks - which is ordered by size of
 * the block. Small blocks at the start of the list and large blocks at the end
 * of the list.
 */
#define prvInsertBlockIntoFreeList( pxBlockToInsert )   \
{   \
BlockLink_t *pxIterator;    \
size_t xBlockSize;  \
                     \
 xBlockSize = pxBlockToInsert->xBlockSize;   \
                     \
 /* Iterate through the list until a block is found that has a larger size */   \
 /* than the block we are inserting. */ \
 for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock )    \
 {  \
  /* There is nothing to do here - just iterate to the correct position. */ \
 }  \
                     \
 /* Update the list to include the block being inserted in the correct */   \
 /* position. */    \
 pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;  \
 pxIterator->pxNextFreeBlock = pxBlockToInsert;  \
}

 

    完成以上操作后，修改剩余空闲块空闲大小xFreeBytesRemaining，整个分配内存的工作就差不多结束了。接下来FreeRTOS调用一个调试信息用的宏traceMALLOC()，恢复所有挂起的任务，再根据宏配置调用勾子函数vApplicationMallocFailedHook()，最后返回分配出来的空间地址pvReturn（成功时为空间地址，失败时为NULL）。这样整个pvPortMalloc()就结束了。

    接下来要继续剖析的是Heap_1中所没有具体实现的vPortFree()。这一个函数非常地短，首先判断要释放的内存是否为空。要是不为空，则寻找这个内存空间的空闲块头，然后挂起所有任务，按照空闲块头的信息把它重新插入到空闲块链表中，最后调用调试信息宏，恢复挂起的任务就结束了。其代码如下。

 

void vPortFree( void *pv )
{
uint8_t *puc = ( uint8_t * ) pv;
BlockLink_t *pxLink;

 if( pv != NULL )
 {
  /* The memory being freed will have an BlockLink_t structure immediately
  before it. */
  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();
 }
}

 

    不过在仔细想想这一段代码，我觉得这一段代码是有点问题，就是判断要释放内存的有效性。这里它只是很简单地判断传进来的指针是否为空而已，但是要是这个指针不为空，但却在FreeRTOS申请的内存堆数组之外呢？这样的话就会修改到内存的其它部分了，非常危险的操作。因此我觉得，如果要修改的话，应该还要加上判断传入进来的地址是否在有效的地址范围内，如下面代码所示。至于我这一个想法是否有问题，希望大家能讨论一下，这样我也可以从大家的讨论中学习学习。

 

if( pv!=NULL)
{
    if( pv >= &ucHeap[ pucAlignedHeap ] && pv <= &ucHeap[ pucAlignedHeap + configADJUSTED_HEAP_SIZE ] )
    {
        /* the operation of adding the block to the list of free blocks */
    }
}

 

    到这里，Heap_2的重点部分就已经剖析完了。剩下的xPortGetFreeHeapSize()只是返回剩余堆大小而已，vPortInitialiseBlocks()实际上啥也没实现，根据注释它的作用只是防止链接器放警告而已。

 

总结：Heap_2比Heap_1的代码更长，要剖析的知识点更多。一开始看的时候还觉得有点怕怕，怕剖着剖着就不知道怎么剖了。在剖的过程中还有很多知识点要翻翻课本，例如在看到最佳适配算法(best fit algorithm)时，要翻翻Andrew S. Tanenbaum写的《Modern Operating Systems》。经过这样的实例剖析之后，我发觉对以前学的东西有了更深刻的理解。以前上课只是说说有这个算法而已，具体怎么实现却完全没有讲。直到现在，我才发觉原来这个算法的真实应用，真是另我大开眼界。以后学习的路还很长，剖析完FreeRTOS还有很长的一段距离。要继续加油加油！

---

http://blog.csdn.net/u014381531/article/details/38665189

FreeRTOS8.0.1的第三个模型Heap_3，可以说是最容易理解的一个内存堆管理模型。因为在这个模型里，FreeRTOS直接将标准C库中的malloc()和free()进行加工打包。（Implementation of pvPortMalloc() and vPortFree() that relies on the compilers own malloc() and free() implementations.）因此，FreeRTOSConfig.h中的configTOTAL_HEAP_SIZE在这个模型中就失效了。FreeRTOS直接管理编译器编译时分配的堆。例如，在STM32F103中，FreeRTOS管理的堆就定义在启动文件startup_stm32f10x_xd.s中。

    不过，就算是直接引用了标准C库中的malloc()和free()也是不行的。原因是库中的这两个接口在FreeRTOS中并不是线程安全的。因此，FreeRTOS将这两个接口进行重新打包。首先看看pvPortMalloc()是怎么将malloc()重新打包的。

 

void *pvPortMalloc( size_t xWantedSize )
{
void *pvReturn;

 vTaskSuspendAll();
 {
  pvReturn = malloc( xWantedSize );
  traceMALLOC( pvReturn, xWantedSize );
 }
 ( void ) xTaskResumeAll();

 #if( configUSE_MALLOC_FAILED_HOOK == 1 )
 {
  if( pvReturn == NULL )
  {
   extern void vApplicationMallocFailedHook( void );
   vApplicationMallocFailedHook();
  }
 }
 #endif

 return pvReturn;
}

 

    这一段就是pvPortMalloc()的所有代码，很短，也很容易理解。首先，和Heap_1、Heap_2一样，用vTaskSuspendAll()挂起所有的任务，以确保分配内存的过程是线程安全的。接下来才使用malloc()进行内存分配。然后就是调用调试信息宏traceMALLOC()并调用xTaskResumeAll()恢复被挂起的任务。这样基本的分配内存流程就结束了。如果在FreeRTOS.h中设置了勾子函数宏，则在调用勾子函数vApplicationMallocFailedHook()之后再向用户返回分配内存的首地址。

 

void vPortFree( void *pv )
{
 if( pv )
 {
  vTaskSuspendAll();
  {
   free( pv );
   traceFREE( pv, 0 );
  }
  ( void ) xTaskResumeAll();
 }
}

 

    上面这一段代码是vPortFree()对free()的重新包装。过程也是很简单。首先是检查指针的有效性，然后挂起所有任务，调用free()接口将内存回收，接着调用调试信息宏traceFREE()，最后恢复所有挂起进程。这样整个回收过程就结束了。

 

总结：一开始的时候看到原有的注释说明，就不想为这个模型剖析下去了。不过后来想想，要成大事必从小事做起，就算是简单也不能放弃，所以还是把这一部分的代码剖析了。以后不能再有这种懒惰的想法了。FreeRTOS中4个内存堆管理模型已经剖析完3个了，还有1个下次继续剖析。之后应该能进入内核了吧？

---

http://blog.csdn.net/u014381531/article/details/38689701

FreeRTOS8.0.1内存管理的最后一个堆模型Heap_4，貌似是在这一个版本才有的。所以找到的说明几乎没有。代码的开头注释也只是简单地说了一下实现了pvPortMalloc()和vPortFree()两个函数，并且能够对回收的内存块进行合并，减少碎片的出现。（A sample implementation of pvPortMalloc() and vPortFree() that combines (coalescences) adjacent memory blocks as they are freed, and in so doing limits memory fragmentation.）不过经过这一次的剖析之后，发现Heap_4所用的内存管理算法为首次适配法（first fit algorithm）。

    和Heap_2一样，Heap_4先申请了一个数组ucHeap[ configTOTAL_HEAP_SIZE ]作为自己管理的堆空间，同样也有空闲块头结构BlockLink_t来管理空闲块。但是和Heap_2不一样的是，Heap_4用了BlockLink_t中xBlockSize的最高一位来标识某个内存块是否处于空闲状态。所以这就是为什么会有一个宏heapBITS_PER_BYTE的出现，而且定义为( ( size_t ) 8 )。这样一来，每一个分配出去的内存块大小就有限制了。例如，我用的是STM32F103，size_t是定义为unsigned int类型的，32位，可支持到4G的内存空间。但是最高1位用来指示空间状态的话，那就只有31位去标识内存块地址，即只支持到2G的内存空间。所以用Heap_4还是有一点点代价的，特别是用在16位或8位的单片机上。

    还是先剖析一下堆空间的初始化过程prvHeapInit()。首先还是先将内存堆进行首地址对齐。接下来就是运用xStart和pxEnd来组织整个空闲块链表。要注意的是，xStart是BlockLink_t的一个实体变量，存储在静态存储区，而pxEnd只是BlockLink_t的一个指针，存储在静态存储区中，却指向了内存堆的最后一个BlockLink_t大小的位置上。也就是说，内存堆最后的空间是存储着一个BlockLink_t，用来指示空闲块链表的终结，这是和Heap_2有所不同的地方。下图说明了初始化流程最终将空闲块链表组织成的样子。

 

 

    接下来剖析Heap_4的第一个重点：pvPortMalloc()。和以前一样，分配内存之前还是先调用vTaskSuspendAll()挂起所有任务，以确保分配内存的过程不被中断。下一步通过判断pxEnd是否为空来决定是否需要初始化内存堆和空闲块链表。因此，初始化之后pxEnd就不为空了，以后再调用pvPortMalloc()也因此不再调用初始化函数。但是这一个判断的另一个分支（else分支却调用了一个mtCOVERAGE_TEST_MARKER()的宏，这个宏的定义在FreeRTOS.h里，定义为空。因此目前还不知道这一个宏具体作用，看名字应该是用来测试什么的。接下来是判断用户申请内存大小的最高位是否为0，为0即合法（之前说过，最高位用来标识空闲块的空闲状态，因此最高位为1则说明用户申请的内存大小已超出空闲块的最大大小）。然后还是一个size_t类型的数据与0比较的判断（虽然这个判断总为真，但也不知道作者为啥要写这么一个判断，要是有人知道这一个判断的意途，请告诉我），里面是增大用户申请的空间大小以便容纳空闲块块头BlockLink_t以及将最终申请的内存大小进行对齐。

    以上的预处理完成了，开始进入分配算法的核心了。只要最终申请的空间大小仍在空闲空间大小的范围内，则进入内存的分配。首先遍历链表，找到第1块能比申请空间大小大的空闲块，修改空闲块的信息，记录用户可用的内存首地址。接下来，如果分配出去的空闲块比申请的空间大很多，则将该空闲块进行分割，把剩余的部分重新添加到链表中。

    分配内存的主要流程基本结束了，和之前分析的一样，pvPortMalloc()继续调用调试宏traceMALLOC()输出调试信息，恢复所有挂起的任务，并按设置调用勾子函数vApplicationMallocFailedHook()，最终把用户可用的内存首地址返回。到这里整个pvPortMalloc()就结束了。

    但是，有一个地方刚刚没怎么详细讲，就是把分割出来的空闲块重新添加到链表中的过程。现在来详细分析一下，这也是Heap_4的一个重点。和Heap_2不同，这一次的prvInsertBlockIntoFreeList()并不是写成一个宏，而是写成了一个函数。进入函数的开始，可以看到，FreeRTOS实际上是将这个空闲块链表里的所有空闲块按地址顺序排列的。当然，如果不这么排列，怎么能将相邻的空闲块进行合并呢？将要回收的空闲块为pxBlockToInsert，这个空闲块将被插到pxIterator的后面。通过一次链表的遍历，就把pxIterator找出来了。接下来，FreeRTOS先试着将pxIterator和pxBlockToInsert进行合并，可以合并的标准为pxIterator的首地址加上pxIterator的块大小之后等于pxBlockToInsert的首地址。相等就说明两个块是相邻的。如果不能合并，就什么事都不做。然后，FreeRTOS再试着将pxBlockToInsert和pxIterator指向的下一个空闲块进行合并。可合并的标准和刚刚说的一样，只是这次用pxBlockToInsert的首地址加上pxBlockToInsert的块大小与pxIterator指向的下一个块地址比较。能合并是最好的，不能合并，则要修改pxBlockToInsert的Next指针，指向pxIterator的下一个空闲块。这是链表插入的基本操作，不用再细讲了。最后，要是pxBlockToInsert没有和pxIterator合并，则还要修改pxIterator的Next指针，这样整条链表才完整无误。

    最后一个重点是vPortFree()。不过这里的vPortFree()的流程和Heap_2的差不多，只是判断指针合法性的时候多了两个条件，一个是检查回收的块大小最高位是否为1，为1才是合法的，毕竟是分配出去了嘛。第二个是Next指针是否为空，为空了说明那是pxEnd，那就不能回收了。在这两个判断之前也有这两个条件的断言configASSERT()，定义在FreeRTOS.h里，同样也是定义为空，可能是留给用户另外用的吧。

    Heap_4的其它三个函数，一个名字看上去是做什么初始化的，却什么都没有实现，所以没啥好讲的，另外两个只是用来返回内存堆的一些状态而已，所以也没啥好讲的。到这里，整个Heap_4就剖析完成了。

 

总结：终于把FreeRTOS的4个内存堆模型全部剖析完了。心情好激动。终于可以开始剖析FreeRTOS的内核代码了。不过，内核代码可不是那么容易剖析的，可能不像内存堆一样，几百行就解决了，所以，之后花的时间可能会更多。不过不怕，反正有的是时间，总会有一天把整个内核都剖析完的。下一次开始，就从list.c开始剖析吧！