基于FreeRTOS的STM32F103系统—Heap_4内存管理机制介绍

1

Heap_4内存管理机制详解

首先介绍一下用到的重要的结构体-标记内存块，在每个存放数据的内存块前都会有一个这样的标记结构体。

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用来表示它所标记的内存块大小。

还有一些全局变量，都写了注释很好理解，就不多解释。

//内存堆大小，并字节对齐
static const size_t xHeapStructSize  = ( sizeof( BlockLink_t ) + ( ( size_t ) ( portBYTE_ALIGNMENT - 1 ) ) ) & ~( ( size_t ) portBYTE_ALIGNMENT_MASK );

/* Create a couple of list links to mark the start and end of the list. */
static BlockLink_t xStart, *pxEnd = NULL;      //内存堆头尾

/* Keeps track of the number of free bytes remaining, but says nothing about
fragmentation. */
static size_t xFreeBytesRemaining = 0U;        //内存堆剩余大小
static size_t xMinimumEverFreeBytesRemaining = 0U;  //历史剩余大小的最小值

/* Gets set to the top bit of an size_t type.  When this bit in the xBlockSize
member of an BlockLink_t structure is set then the block belongs to the
application.  When the bit is free the block is still part of the free heap
space. */
static size_t xBlockAllocatedBit = 0;      //1这个块被申请；0这个块空闲

2

内存堆初始化

首先定义一些临时变量

BlockLink_t *pxFirstFreeBlock;                  //整个空闲内存块之前的标记结构体
uint8_t *pucAlignedHeap;                    //字节对齐后的起始地址
size_t uxAddress;                        //相当于临时变量
size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;          //抛弃不可用内存块后总的大小

经过一系列的操作，使初始化后，空闲内存表的起始地址为字节对齐，这里和heap_2不同的地方是，使用了临时变量uxAddress存储中间计算出来的一些地址，这里uxAddress存储的是字节对齐后的初始地址，然后赋值给pucAlignedHeap变量中。

/* Ensure the heap starts on a correctly aligned boundary. */
  /*确保字节对齐后的起始地址正确*/
  uxAddress = ( size_t ) ucHeap;                //获得内存堆的大小放到uxAddress中

  if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )      //如果内存堆大小不为0且不在掩模中
  {
    uxAddress += ( portBYTE_ALIGNMENT - 1 );        //portBYTE_ALIGNMENT = 7
    uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );  
    xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;    //抛弃不可用内存块后总的大小
  }

  pucAlignedHeap = ( uint8_t * ) uxAddress;          //字节对齐后的起始地址

这部分代码用来初始化空闲内存表的头和尾，使头的下一个内存块指向字节对齐后的首地址，大小初始化为0；这里的uxAddress变量经过一系列操作以及变成了内存块的末地址，然后使尾的首地址指向末地址(pxEnd=(void *)uxAddress），大小初始化为0，尾的下一个内存块为NULL。

/*初始化链表头和尾*/
  xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;      //下一个头指向字节对齐后的起始地址
  xStart.xBlockSize = ( size_t ) 0;              //大小初始化为0              

  /* pxEnd is used to mark the end of the list of free blocks and is inserted
  at the end of the heap space. */
  uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;  //这里的uxAddress已经变成了末尾的地址
  uxAddress -= xHeapStructSize;                //减去一个标志结构体的大小
  uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );    //字节对齐
  pxEnd = ( void * ) uxAddress;                //这里的uxAddress已经变成了内存堆尾-一个标志结构体然后字节对齐后的地址
  pxEnd- >xBlockSize = 0;                    //末尾的内存块大小初始化为0
  pxEnd- >pxNextFreeBlock = NULL;                //下一个指向NULL

在申请内存的最开始，把整个内存堆都看成一个整体，作为一个大内存块，这个内存块之前也需要有一个标记结构体，也就是pxFirstFreeBlock结构体，这里对这个结构体进行初始化，它的首地址就是字节对齐后的地址，大小是尾地址uxAddess-内存块字节对齐后的首地址，下一个内存块指向pxEnd。

/*开始的时候将内存堆整个可用空间看成一个空闲内存块*/
  pxFirstFreeBlock = ( void * ) pucAlignedHeap;              //空闲内存块之前的标记结构体地址    
  pxFirstFreeBlock- >xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;  //标记结构体记录内存块大小为末地址-初地址
  pxFirstFreeBlock- >pxNextFreeBlock = pxEnd;                //下一个空闲内存块为末尾内存块指针

最后这里就是更新一下全局变量，并标记一下块被占用。

/*只有一个内存块，而且这个内存块拥有内存堆的整个可用空间*/
  xMinimumEverFreeBytesRemaining = pxFirstFreeBlock- >xBlockSize;      //记录最小的空闲内存块大小
  xFreeBytesRemaining = pxFirstFreeBlock- >xBlockSize;            //记录历史最小的空闲内存块大小

  /* Work out the position of the top bit in a size_t variable. */
  xBlockAllocatedBit = ( ( size_t ) 1 ) < < ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );    //初始化静态变量，初始化完成以后此变量值为 0X80000000
  //在 heap_4 中其最高位表示此内存块是否被使用，如果为 1 的话就表示被使用了，所以在 heap_4 中一个内存块最大只能为 0x7FFFFFFF

借用一下原子手册的图解：

3

插入空闲内存表函数

先定义两个用到的局部变量，pxIterator相当于C++中容器的迭代器，puc就是个临时变量。

BlockLink_t *pxIterator;    //相当于查找合适位置的迭代器
uint8_t *puc;          //相当于临时变量

这里就是使用迭代器一次次循环，知道找到空闲内存表中满足内存要求（pxIterator->pxNextFreeBlock < pxBlockToInsert）的内存块地址。

//遍历空闲内存块链表，找出内存块插入点，内存块按照地址从低到高连接在一起（迭代器思想）
  for( pxIterator = &xStart; pxIterator- >pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator- >pxNextFreeBlock )
  {
    /* Nothing to do here, just iterate to the right position. */
  }

这里是判断要插入的这块内存和前一块内存是否相邻，如果相邻就合并成一块，判断是否相邻的条件是puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert，插入点地址+这块内存的大小==要插入块首地址；即上一块末地址==要插入块起始地址

//插入内存块，如果要插入的内存块可以和前一个内存块合并的话就
  //合并两个内存块
  puc = ( uint8_t * ) pxIterator;                //找到的合适的插入点的地址
  if( ( puc + pxIterator- >xBlockSize ) == ( uint8_t * ) pxBlockToInsert ) //插入点地址+这块内存的大小==要插入块首地址；即上一块末地址==要插入块起始地址
  {
    pxIterator- >xBlockSize += pxBlockToInsert- >xBlockSize;  //大小合并
    pxBlockToInsert = pxIterator;              //合并后内存首地址不变
  }
  else
  {
    mtCOVERAGE_TEST_MARKER();
  }

再借用一下原子的图：

这一部分代码是检查要插入的内存块是否和后一块内存相邻，如果相邻就合并起来，判断条件是puc + pxBlockToInsert->xBlockSize == ( uint8_t * ) （ pxIterator->pxNextFreeBlock )，要插入块首地址+这块内存的大小==下一块首地址；即要插入块末地址==下一块起始地址

//检查是否可以和后面的内存块合并，可以的话就合并
  puc = ( uint8_t * ) pxBlockToInsert;      //要插入的内存块的首地址
  if( ( puc + pxBlockToInsert- >xBlockSize ) == ( uint8_t * ) pxIterator- >pxNextFreeBlock )  要插入块首地址+这块内存的大小==下一块首地址；即要插入块末地址==下一块起始地址
  {
    if( pxIterator- >pxNextFreeBlock != pxEnd )    //下一块不是表尾
    {
      /* Form one big block from the two blocks. */
      //将两个内存块组合成一个大的内存块时
      pxBlockToInsert- >xBlockSize += pxIterator- >pxNextFreeBlock- >xBlockSize;      内存块大小合并
      pxBlockToInsert- >pxNextFreeBlock = pxIterator- >pxNextFreeBlock- >pxNextFreeBlock;//合并起来之后下下快变成了下一块
    }
    else
    {
      pxBlockToInsert- >pxNextFreeBlock = pxEnd;  //要插入的变成表尾
    }
  }
  else
  {
    pxBlockToInsert- >pxNextFreeBlock = pxIterator- >pxNextFreeBlock;
  }

最后借用一下原子的图：

如果和前后都不相邻，则使用最简单的插入方法：

//在内存块插入的过程中没有进行过一次内存合并，使用最简单的插入方法
  if( pxIterator != pxBlockToInsert )
  {
    pxIterator- >pxNextFreeBlock = pxBlockToInsert;
  }
  else
  {
    mtCOVERAGE_TEST_MARKER();
  }

4

内存申请函数

先初始化一下内存堆：

//第一次调用，初始化内存堆
    if( pxEnd == NULL )
    {
      prvHeapInit();
    }
    else
    {
      mtCOVERAGE_TEST_MARKER();
    }

判断一下想要插入数据的内存块是否被使用，就是和xBlockAllocateBit变量做一次与运算，如果结果不是1，则说明没被使用；在确保要插入的大小大于0之后，需要附加上标记结构体的大小（8字节）后，再进行字节对齐。

//需要申请的内存块大小的最高位不能为 1，因为最高位用来表示内存块有没有被使用
    if( ( xWantedSize & xBlockAllocatedBit ) == 0 )
    {
      /* 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 += xHeapStructSize;    //要申请的大小加上标记结构体的大小
        /* Ensure that blocks are always aligned to the required number
        of bytes. */
        if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
        {
          /* Byte alignment required. */
          /*要插入的内存块字节对齐*/
          xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
          configASSERT( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) == 0 );
        }
        else
        {
          mtCOVERAGE_TEST_MARKER();
        }
      }
      else
      {
        mtCOVERAGE_TEST_MARKER();
      }

当我们想要插入的内存块小于剩余内存大小时，就开始查找满足要求的内存块。

if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
      {
        /* Traverse the list from the start  (lowest address) block until
        one  of adequate size is found. */
        //从 xStart(内存块最小)开始，查找大小满足所需要内存的内存块
        pxPreviousBlock = &xStart;        //上一个内存块
        pxBlock = xStart.pxNextFreeBlock;    //满足要求的内存块（下一块）
        while( ( pxBlock- >xBlockSize < xWantedSize ) && ( pxBlock- >pxNextFreeBlock != NULL ) )
        {
          pxPreviousBlock = pxBlock;
          pxBlock = pxBlock- >pxNextFreeBlock;
        }

如果找到的是pxEnd表示没有内存可以分配，否则就将内存首地址保存在 pvReturn 中，函数返回的时候返回此值，然后将这块内存从空闲内存表中删除

//如果找到的内存块是 pxEnd 的话就表示没有内存可以分配
        if( pxBlock != pxEnd )
        {
          /* Return the memory space pointed to - jumping over the
          BlockLink_t structure at its start. */
          //找到内存块以后就将内存首地址保存在 pvReturn 中，函数返回的时候返回此值
          //找到的内存块让出一个标志结构体的大小
          pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock- >pxNextFreeBlock ) + xHeapStructSize );

          /* This block is being returned for use so must be taken out
          of the list of free blocks. */
          //将申请到的内存块从空闲内存链表中移除
          pxPreviousBlock- >pxNextFreeBlock = pxBlock- >pxNextFreeBlock;  //把满足要求的pxBlock块的下一块拼接到上一块

申请的内存大小小于空闲的一大块内存的大小，则将其分割，剩下的留着，相当于给空闲内存块的首地址做一个地址偏移：新的空闲内存块=满足要求的内存块首地址+需要的内存块首地址，然后更新新的空闲内存块的大小，并将其插入到空闲内存表。

//如果申请到的内存块大于所需的内存，就将其分成两块
          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 );  //新的空闲内存块=满足要求的内存块首地址+需要的内存块首地址 
            configASSERT( ( ( ( size_t ) pxNewBlockLink ) & portBYTE_ALIGNMENT_MASK ) == 0 );

            /* 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 );          //插入新的空闲内存块
          }
          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最高位置1
          pxBlock- >pxNextFreeBlock = NULL;      //满足要求的内存块下一块指向NULL

后面还可以配置内存申请失败时的钩子函数，需要把configUSE_MALLOC_FAILED_HOOK宏打开

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

5

内存释放函数

先定义一些用到的局部变量：

uint8_t *puc = ( uint8_t * ) pv;  //传入要释放内存的地址
BlockLink_t *pxLink;        //包含了标志结构体后的首地址

传入的数据地址没包含标志结构体，需要先做减法，进行地址移位，然后将包含了标志结构体的首地址保存在pxLink中

puc -= xHeapStructSize;          //释放的部分包括上标志结构体大小
/* This casting is to keep the compiler from issuing warnings. */
pxLink = ( void * ) puc;        //防止编译器报错

如果要释放的内存真的被使用，就开始释放操作，先把首位变0，表示变成空闲，然后更新空闲内存大小，将这块内存插入回空闲内存表中，要注意：释放和申请内存，并不是把这块内存从一个链表中拿出来了，只是做了一些标记，让程序知道这部分被占用，有数据，在释放内存之前我们将数据删除，然后把标志位改为空闲状态就行，这就是释放的本质。

if( ( pxLink- >xBlockSize & xBlockAllocatedBit ) != 0 )    //判断是否真被使用
    {
      if( pxLink- >pxNextFreeBlock == NULL )
      {
        /* The block is being returned to the heap - it is no longer
        allocated. */
        pxLink- >xBlockSize &= ~xBlockAllocatedBit;      //首位变0，表示未被使用

        vTaskSuspendAll();
        {
          /* Add this block to the list of free blocks. */
          /*将内存块插到空闲内存链表中*/
          xFreeBytesRemaining += pxLink- >xBlockSize;          //更新最小内存块大小
          traceFREE( pv, pxLink- >xBlockSize );            
          prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );  //将被释放的内存块插入空闲内存链表中
        }
        ( void ) xTaskResumeAll();
      }
      else
      {
        mtCOVERAGE_TEST_MARKER();
      }
    }
    else
    {
      mtCOVERAGE_TEST_MARKER();
    }

6

总结

其他的函数主要就是直接返回我们之前更新的全局变量，终于把基础知识都铺垫完了，下面结合具体项目程序谈谈怎么优化了。