#FREERTOS的和heap_4内存分配算法

FreeRTOS的heap_4内存管理算法具有内存碎片合并的功能，可以有效防止内存碎片产生，使用First fit算法，在实现上与C标准库的malloc类似，但是效率更高且能进行碎片合并回收。以下是个人对源码的解析,有空再补充详细。
一、初始化

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. /*====================================== 1 ===========================================*/
9.     /* 字节对齐,4字节 */
10.     uxAddress = ( size_t ) ucHeap;
11.     /*字节对齐，一般是8字节*/
12.     if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
13.     {
14.         /* 对齐处理 */
15.         uxAddress += ( portBYTE_ALIGNMENT - 1 );
16.         uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
17.         xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;
18.     }
19.     /*取对齐后的地址*/
20.     pucAlignedHeap = ( uint8_t * ) uxAddress;
22. /*====================================== 2 ===========================================*/
23.     /* 把xStart的next指针指向对齐后的头地址，长度设置为0.xStart只是链表头不参与内存分配*/
24.     xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
25.     xStart.xBlockSize = ( size_t ) 0;
26. /*====================================== 3 ===========================================*/
27.     /* 计算尾部指针地址 */
28.     uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
29.     /* 减去end所占用的8个字节 */
30.     uxAddress -= xHeapStructSize;
31.     /* pxend字节对齐，也就是尾部会空出8-15字节用于放pxend */
32.     uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
33.     /* pxend初始化 */
34.     pxEnd = ( void * ) uxAddress;
35.     pxEnd->xBlockSize = 0;
36.     pxEnd->pxNextFreeBlock = NULL;
38. /*====================================== 4 ===========================================*/
39.     /* 初始化头结构，也就是xstart一开始指向的那个地址 */
40.     pxFirstFreeBlock = ( void * ) pucAlignedHeap;
41.     pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;
42.     pxFirstFreeBlock->pxNextFreeBlock = pxEnd;
43.     /* 初始化内存最大使用量和剩余空间这两个变量的值 */
44.     xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
45.     xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
46.     /* 定义xBlockSize最高bit，因为xBlockSize的最高bit用于判断是否使用 */
47.     xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
48. }

复制代码

三、释放内存

1. void *pvPortMalloc( size_t xWantedSize )
2. {
3.     BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
4.     void *pvReturn = NULL;
6.     {
7.         /* 如果还没初始化的话，就先初始化. */
8.         if( pxEnd == NULL )
9.         {
10.             prvHeapInit();
11.         }
12.         
13.         /* 检查要分配的大小是否超过了最大值,因为最高位用来标志空闲块是否已经使用，
14.             所以能分配的空间最大值为0x7FFF FFFF 也就是2G*/
15.         if( ( xWantedSize & xBlockAllocatedBit ) == 0 )
16.         {
17.             /* 检查分配空间是否为0 */
18.             if( xWantedSize > 0 )
19.             {
20.                 /* 加上链表结构的大小 */
21.                 xWantedSize += xHeapStructSize;
22.                 /* 日常字节对齐 */
23.                 if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
24.                 {
25.                     /* 补齐. */
26.                     xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
27.                 }
28.             }
29.             /* 这里也判断xWantedSize>0,可以跟上面的代码合并啊，判断空闲的空间还够不够 */
30.             if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
31.             {
32.                 /* 从头开始查找大小够分配的空闲块，直到找到pxend. */
33.                 pxPreviousBlock = &xStart;
34.                 pxBlock = xStart.pxNextFreeBlock;
35.                 while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
36.                 {
37.                     pxPreviousBlock = pxBlock;
38.                     pxBlock = pxBlock->pxNextFreeBlock;
39.                 }
40.                 /* 如果是pxEnd就是说没有能够分配的空闲块了，分配失败 */
41.                 if( pxBlock != pxEnd )
42.                 {
43.                     /* 分配的地址是空闲块管理结构地址+结构大小，如图
44.                                 分配了的空间     新的空闲块
45.                         |____|_______________|________________|
46.                           ☝  ↑分配的内存地址
47.                     有足够空间的结构， */
48.                     pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
49.                     /* 跳过刚刚被使用的空闲块，指向下一块 */
50.                     pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
51.                     /* 如果当前空闲块分配完之后剩余的大小还>=16字节，就分成两块 */
52.                     if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
53.                     {
54.                         /* 创建一个新的空闲块，计算偏移地址 */
55.                         pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
56.                         /* 初始化新空闲块的大小，next需要做插入处理 */
57.                         pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
58.                         /* 旧块重新定义大小 */
59.                         pxBlock->xBlockSize = xWantedSize;
60.                         /* Insert the new block into the list of free blocks.看英语解释 */
61.                         prvInsertBlockIntoFreeList( pxNewBlockLink );
62.                     }
63.                     /* 扣除剩余的空间统计 */
64.                     xFreeBytesRemaining -= pxBlock->xBlockSize;
65.                     /* 记录当前使用空间的最大值，也就是记录系统运行中最多用了多少空间 */
66.                     if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
67.                     {
68.                         xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
69.                     }
70.                     /* 最高位置为1，清楚next指针，标记已经用掉了 */
71.                     pxBlock->xBlockSize |= xBlockAllocatedBit;
72.                     pxBlock->pxNextFreeBlock = NULL;
73.                 }
74.             }
75.         }
76.     }
77.     {
78.         if( pvReturn == NULL )
79.         {
80.             printf("malloc fail \r\n");   
81.         }
82.         
83.     }
84.     return pvReturn;
85. }

复制代码

四、碎片整理

把新的空闲列表项插入链表中，同时进行空闲块合并。

1. oid vPortFree( void *pv )
2. {
3. uint8_t *puc = ( uint8_t * ) pv;
4. BlockLink_t *pxLink;
6.     if( pv != NULL )
7.     {
8.         /* 找到结构体的地址
9.                    ↓puc地址
10.             |______|___________________|
11.             ↑BlockLink_t地址*/
12.         puc -= xHeapStructSize;
13.         /* 防一手编译器警告 */
14.         pxLink = ( void * ) puc;
15.         /* 通过最高位判断是否已经使用 */
16.         if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
17.         {
18.             /* 已经使用的next被复制为null，可以看malloc */
19.             if( pxLink->pxNextFreeBlock == NULL )
20.             {
21.                 /*清掉标志位 */
22.                 pxLink->xBlockSize &= ~xBlockAllocatedBit;
23.                 {
24.                     /* 统计空闲内内存大小，插入链表中. */
25.                     xFreeBytesRemaining += pxLink->xBlockSize;
26.                     prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
27.                 }
28.             }
29.             
30.         }
31.         
32.     }
33. }
34. /*-----------------------------------------------------------*/

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！