1

Heap_4內(nèi)存管理機(jī)制詳解

首先介紹一下用到的重要的結(jié)構(gòu)體-標(biāo)記內(nèi)存塊，在每個(gè)存放數(shù)據(jù)的內(nèi)存塊前都會(huì)有一個(gè)這樣的標(biāo)記結(jié)構(gòu)體。

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;

里面有兩個(gè)變量，pxNextFreeBlock指向下一個(gè)內(nèi)存塊，xBlockSize用來表示它所標(biāo)記的內(nèi)存塊大小。

還有一些全局變量，都寫了注釋很好理解，就不多解釋。

//內(nèi)存堆大小，并字節(jié)對齊
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;      //內(nèi)存堆頭尾

/* Keeps track of the number of free bytes remaining, but says nothing about
fragmentation. */
static size_t xFreeBytesRemaining = 0U;        //內(nèi)存堆剩余大小
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這個(gè)塊被申請；0這個(gè)塊空閑

2

內(nèi)存堆初始化

首先定義一些臨時(shí)變量

BlockLink_t *pxFirstFreeBlock;                  //整個(gè)空閑內(nèi)存塊之前的標(biāo)記結(jié)構(gòu)體
uint8_t *pucAlignedHeap;                    //字節(jié)對齊后的起始地址
size_t uxAddress;                        //相當(dāng)于臨時(shí)變量
size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;          //拋棄不可用內(nèi)存塊后總的大小

經(jīng)過一系列的操作，使初始化后，空閑內(nèi)存表的起始地址為字節(jié)對齊，這里和heap_2不同的地方是，使用了臨時(shí)變量uxAddress存儲(chǔ)中間計(jì)算出來的一些地址，這里uxAddress存儲(chǔ)的是字節(jié)對齊后的初始地址，然后賦值給pucAlignedHeap變量中。

/* Ensure the heap starts on a correctly aligned boundary. */
  /*確保字節(jié)對齊后的起始地址正確*/
  uxAddress = ( size_t ) ucHeap;                //獲得內(nèi)存堆的大小放到uxAddress中

  if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )      //如果內(nèi)存堆大小不為0且不在掩模中
  {
    uxAddress += ( portBYTE_ALIGNMENT - 1 );        //portBYTE_ALIGNMENT = 7
    uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );  
    xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;    //拋棄不可用內(nèi)存塊后總的大小
  }

  pucAlignedHeap = ( uint8_t * ) uxAddress;          //字節(jié)對齊后的起始地址

這部分代碼用來初始化空閑內(nèi)存表的頭和尾，使頭的下一個(gè)內(nèi)存塊指向字節(jié)對齊后的首地址，大小初始化為0；這里的uxAddress變量經(jīng)過一系列操作以及變成了內(nèi)存塊的末地址，然后使尾的首地址指向末地址(pxEnd=(void *)uxAddress），大小初始化為0，尾的下一個(gè)內(nèi)存塊為NULL。

/*初始化鏈表頭和尾*/
  xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;      //下一個(gè)頭指向字節(jié)對齊后的起始地址
  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已經(jīng)變成了末尾的地址
  uxAddress -= xHeapStructSize;                //減去一個(gè)標(biāo)志結(jié)構(gòu)體的大小
  uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );    //字節(jié)對齊
  pxEnd = ( void * ) uxAddress;                //這里的uxAddress已經(jīng)變成了內(nèi)存堆尾-一個(gè)標(biāo)志結(jié)構(gòu)體然后字節(jié)對齊后的地址
  pxEnd- >xBlockSize = 0;                    //末尾的內(nèi)存塊大小初始化為0
  pxEnd- >pxNextFreeBlock = NULL;                //下一個(gè)指向NULL

在申請內(nèi)存的最開始，把整個(gè)內(nèi)存堆都看成一個(gè)整體，作為一個(gè)大內(nèi)存塊，這個(gè)內(nèi)存塊之前也需要有一個(gè)標(biāo)記結(jié)構(gòu)體，也就是pxFirstFreeBlock結(jié)構(gòu)體，這里對這個(gè)結(jié)構(gòu)體進(jìn)行初始化，它的首地址就是字節(jié)對齊后的地址，大小是尾地址uxAddess-內(nèi)存塊字節(jié)對齊后的首地址，下一個(gè)內(nèi)存塊指向pxEnd。

/*開始的時(shí)候?qū)?nèi)存堆整個(gè)可用空間看成一個(gè)空閑內(nèi)存塊*/
  pxFirstFreeBlock = ( void * ) pucAlignedHeap;              //空閑內(nèi)存塊之前的標(biāo)記結(jié)構(gòu)體地址    
  pxFirstFreeBlock- >xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;  //標(biāo)記結(jié)構(gòu)體記錄內(nèi)存塊大小為末地址-初地址
  pxFirstFreeBlock- >pxNextFreeBlock = pxEnd;                //下一個(gè)空閑內(nèi)存塊為末尾內(nèi)存塊指針

最后這里就是更新一下全局變量，并標(biāo)記一下塊被占用。

/*只有一個(gè)內(nèi)存塊，而且這個(gè)內(nèi)存塊擁有內(nèi)存堆的整個(gè)可用空間*/
  xMinimumEverFreeBytesRemaining = pxFirstFreeBlock- >xBlockSize;      //記錄最小的空閑內(nèi)存塊大小
  xFreeBytesRemaining = pxFirstFreeBlock- >xBlockSize;            //記錄歷史最小的空閑內(nèi)存塊大小

  /* Work out the position of the top bit in a size_t variable. */
  xBlockAllocatedBit = ( ( size_t ) 1 ) < < ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );    //初始化靜態(tài)變量，初始化完成以后此變量值為 0X80000000
  //在 heap_4 中其最高位表示此內(nèi)存塊是否被使用，如果為 1 的話就表示被使用了，所以在 heap_4 中一個(gè)內(nèi)存塊最大只能為 0x7FFFFFFF

借用一下原子手冊的圖解：

3

插入空閑內(nèi)存表函數(shù)

先定義兩個(gè)用到的局部變量，pxIterator相當(dāng)于C++中容器的迭代器，puc就是個(gè)臨時(shí)變量。

BlockLink_t *pxIterator;    //相當(dāng)于查找合適位置的迭代器
uint8_t *puc;          //相當(dāng)于臨時(shí)變量

這里就是使用迭代器一次次循環(huán)，知道找到空閑內(nèi)存表中滿足內(nèi)存要求（pxIterator->pxNextFreeBlock < pxBlockToInsert）的內(nèi)存塊地址。

//遍歷空閑內(nèi)存塊鏈表，找出內(nèi)存塊插入點(diǎn)，內(nèi)存塊按照地址從低到高連接在一起（迭代器思想）
  for( pxIterator = &xStart; pxIterator- >pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator- >pxNextFreeBlock )
  {
    /* Nothing to do here, just iterate to the right position. */
  }

這里是判斷要插入的這塊內(nèi)存和前一塊內(nèi)存是否相鄰，如果相鄰就合并成一塊，判斷是否相鄰的條件是puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert，插入點(diǎn)地址+這塊內(nèi)存的大小==要插入塊首地址；即上一塊末地址==要插入塊起始地址

//插入內(nèi)存塊，如果要插入的內(nèi)存塊可以和前一個(gè)內(nèi)存塊合并的話就
  //合并兩個(gè)內(nèi)存塊
  puc = ( uint8_t * ) pxIterator;                //找到的合適的插入點(diǎn)的地址
  if( ( puc + pxIterator- >xBlockSize ) == ( uint8_t * ) pxBlockToInsert ) //插入點(diǎn)地址+這塊內(nèi)存的大小==要插入塊首地址；即上一塊末地址==要插入塊起始地址
  {
    pxIterator- >xBlockSize += pxBlockToInsert- >xBlockSize;  //大小合并
    pxBlockToInsert = pxIterator;              //合并后內(nèi)存首地址不變
  }
  else
  {
    mtCOVERAGE_TEST_MARKER();
  }

再借用一下原子的圖：

這一部分代碼是檢查要插入的內(nèi)存塊是否和后一塊內(nèi)存相鄰，如果相鄰就合并起來，判斷條件是puc + pxBlockToInsert->xBlockSize == ( uint8_t * ) （ pxIterator->pxNextFreeBlock )，要插入塊首地址+這塊內(nèi)存的大小==下一塊首地址；即要插入塊末地址==下一塊起始地址

//檢查是否可以和后面的內(nèi)存塊合并，可以的話就合并
  puc = ( uint8_t * ) pxBlockToInsert;      //要插入的內(nèi)存塊的首地址
  if( ( puc + pxBlockToInsert- >xBlockSize ) == ( uint8_t * ) pxIterator- >pxNextFreeBlock )  要插入塊首地址+這塊內(nèi)存的大小==下一塊首地址；即要插入塊末地址==下一塊起始地址
  {
    if( pxIterator- >pxNextFreeBlock != pxEnd )    //下一塊不是表尾
    {
      /* Form one big block from the two blocks. */
      //將兩個(gè)內(nèi)存塊組合成一個(gè)大的內(nèi)存塊時(shí)
      pxBlockToInsert- >xBlockSize += pxIterator- >pxNextFreeBlock- >xBlockSize;      內(nèi)存塊大小合并
      pxBlockToInsert- >pxNextFreeBlock = pxIterator- >pxNextFreeBlock- >pxNextFreeBlock;//合并起來之后下下快變成了下一塊
    }
    else
    {
      pxBlockToInsert- >pxNextFreeBlock = pxEnd;  //要插入的變成表尾
    }
  }
  else
  {
    pxBlockToInsert- >pxNextFreeBlock = pxIterator- >pxNextFreeBlock;
  }

最后借用一下原子的圖：

如果和前后都不相鄰，則使用最簡單的插入方法：

//在內(nèi)存塊插入的過程中沒有進(jìn)行過一次內(nèi)存合并，使用最簡單的插入方法
  if( pxIterator != pxBlockToInsert )
  {
    pxIterator- >pxNextFreeBlock = pxBlockToInsert;
  }
  else
  {
    mtCOVERAGE_TEST_MARKER();
  }

4

內(nèi)存申請函數(shù)

先初始化一下內(nèi)存堆：

//第一次調(diào)用，初始化內(nèi)存堆
    if( pxEnd == NULL )
    {
      prvHeapInit();
    }
    else
    {
      mtCOVERAGE_TEST_MARKER();
    }

判斷一下想要插入數(shù)據(jù)的內(nèi)存塊是否被使用，就是和xBlockAllocateBit變量做一次與運(yùn)算，如果結(jié)果不是1，則說明沒被使用；在確保要插入的大小大于0之后，需要附加上標(biāo)記結(jié)構(gòu)體的大小（8字節(jié)）后，再進(jìn)行字節(jié)對齊。

//需要申請的內(nèi)存塊大小的最高位不能為 1，因?yàn)樽罡呶挥脕肀硎緝?nèi)存塊有沒有被使用
    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;    //要申請的大小加上標(biāo)記結(jié)構(gòu)體的大小
        /* Ensure that blocks are always aligned to the required number
        of bytes. */
        if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
        {
          /* Byte alignment required. */
          /*要插入的內(nèi)存塊字節(jié)對齊*/
          xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
          configASSERT( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) == 0 );
        }
        else
        {
          mtCOVERAGE_TEST_MARKER();
        }
      }
      else
      {
        mtCOVERAGE_TEST_MARKER();
      }

當(dāng)我們想要插入的內(nèi)存塊小于剩余內(nèi)存大小時(shí)，就開始查找滿足要求的內(nèi)存塊。

if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
      {
        /* Traverse the list from the start  (lowest address) block until
        one  of adequate size is found. */
        //從 xStart(內(nèi)存塊最小)開始，查找大小滿足所需要內(nèi)存的內(nèi)存塊
        pxPreviousBlock = &xStart;        //上一個(gè)內(nèi)存塊
        pxBlock = xStart.pxNextFreeBlock;    //滿足要求的內(nèi)存塊（下一塊）
        while( ( pxBlock- >xBlockSize < xWantedSize ) && ( pxBlock- >pxNextFreeBlock != NULL ) )
        {
          pxPreviousBlock = pxBlock;
          pxBlock = pxBlock- >pxNextFreeBlock;
        }

如果找到的是pxEnd表示沒有內(nèi)存可以分配，否則就將內(nèi)存首地址保存在 pvReturn 中，函數(shù)返回的時(shí)候返回此值，然后將這塊內(nèi)存從空閑內(nèi)存表中刪除

//如果找到的內(nèi)存塊是 pxEnd 的話就表示沒有內(nèi)存可以分配
        if( pxBlock != pxEnd )
        {
          /* Return the memory space pointed to - jumping over the
          BlockLink_t structure at its start. */
          //找到內(nèi)存塊以后就將內(nèi)存首地址保存在 pvReturn 中，函數(shù)返回的時(shí)候返回此值
          //找到的內(nèi)存塊讓出一個(gè)標(biāo)志結(jié)構(gòu)體的大小
          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. */
          //將申請到的內(nèi)存塊從空閑內(nèi)存鏈表中移除
          pxPreviousBlock- >pxNextFreeBlock = pxBlock- >pxNextFreeBlock;  //把滿足要求的pxBlock塊的下一塊拼接到上一塊

申請的內(nèi)存大小小于空閑的一大塊內(nèi)存的大小，則將其分割，剩下的留著，相當(dāng)于給空閑內(nèi)存塊的首地址做一個(gè)地址偏移：新的空閑內(nèi)存塊=滿足要求的內(nèi)存塊首地址+需要的內(nèi)存塊首地址，然后更新新的空閑內(nèi)存塊的大小，并將其插入到空閑內(nèi)存表。

//如果申請到的內(nèi)存塊大于所需的內(nèi)存，就將其分成兩塊
          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 );  //新的空閑內(nèi)存塊=滿足要求的內(nèi)存塊首地址+需要的內(nèi)存塊首地址 
            configASSERT( ( ( ( size_t ) pxNewBlockLink ) & portBYTE_ALIGNMENT_MASK ) == 0 );

            /* Calculate the sizes of two blocks split from the
            single block. */
            pxNewBlockLink- >xBlockSize = pxBlock- >xBlockSize - xWantedSize;  //更新新的空閑內(nèi)存塊的大小
            pxBlock- >xBlockSize = xWantedSize;                //滿足要求的內(nèi)存塊的大小

            /* Insert the new block into the list of free blocks. */
            prvInsertBlockIntoFreeList( pxNewBlockLink );          //插入新的空閑內(nèi)存塊
          }
          else
          {
            mtCOVERAGE_TEST_MARKER();
          }

最后就是更新一下全局變量

xFreeBytesRemaining -= pxBlock- >xBlockSize;              //更新最小內(nèi)存塊大小

          if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )      //更新歷史最小內(nèi)存塊大小
          {
            xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
          }
          else
          {
            mtCOVERAGE_TEST_MARKER();
          }

          /* The block is being returned - it is allocated and owned
          by the application and has no "next" block. */
          //內(nèi)存塊申請成功，標(biāo)記此內(nèi)存塊已經(jīng)被使用
          pxBlock- >xBlockSize |= xBlockAllocatedBit;  //將pxBlock最高位置1
          pxBlock- >pxNextFreeBlock = NULL;      //滿足要求的內(nèi)存塊下一塊指向NULL

后面還可以配置內(nèi)存申請失敗時(shí)的鉤子函數(shù)，需要把configUSE_MALLOC_FAILED_HOOK宏打開

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

5

內(nèi)存釋放函數(shù)

先定義一些用到的局部變量：

uint8_t *puc = ( uint8_t * ) pv;  //傳入要釋放內(nèi)存的地址
BlockLink_t *pxLink;        //包含了標(biāo)志結(jié)構(gòu)體后的首地址

傳入的數(shù)據(jù)地址沒包含標(biāo)志結(jié)構(gòu)體，需要先做減法，進(jìn)行地址移位，然后將包含了標(biāo)志結(jié)構(gòu)體的首地址保存在pxLink中

puc -= xHeapStructSize;          //釋放的部分包括上標(biāo)志結(jié)構(gòu)體大小
/* This casting is to keep the compiler from issuing warnings. */
pxLink = ( void * ) puc;        //防止編譯器報(bào)錯(cuò)

如果要釋放的內(nèi)存真的被使用，就開始釋放操作，先把首位變0，表示變成空閑，然后更新空閑內(nèi)存大小，將這塊內(nèi)存插入回空閑內(nèi)存表中，要注意：釋放和申請內(nèi)存，并不是把這塊內(nèi)存從一個(gè)鏈表中拿出來了，只是做了一些標(biāo)記，讓程序知道這部分被占用，有數(shù)據(jù)，在釋放內(nèi)存之前我們將數(shù)據(jù)刪除，然后把標(biāo)志位改為空閑狀態(tài)就行，這就是釋放的本質(zhì)。

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. */
          /*將內(nèi)存塊插到空閑內(nèi)存鏈表中*/
          xFreeBytesRemaining += pxLink- >xBlockSize;          //更新最小內(nèi)存塊大小
          traceFREE( pv, pxLink- >xBlockSize );            
          prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );  //將被釋放的內(nèi)存塊插入空閑內(nèi)存鏈表中
        }
        ( void ) xTaskResumeAll();
      }
      else
      {
        mtCOVERAGE_TEST_MARKER();
      }
    }
    else
    {
      mtCOVERAGE_TEST_MARKER();
    }

6

總結(jié)

其他的函數(shù)主要就是直接返回我們之前更新的全局變量，終于把基礎(chǔ)知識(shí)都鋪墊完了，下面結(jié)合具體項(xiàng)目程序談?wù)勗趺磧?yōu)化了。