FreeRTOS系列-- heap_4.c内存管理分析

heap_4.c简介

FreeRTOS有5个内存管理文件 ，heap_1.c 到heap_5.c，heap_4.c提供了空闲块内存合并功能，能大大减少内存碎片问题，因此我们一般使用的heap_4.c，因此本文主要分析heap_4.c的实现原理。
heap_4.c 提供的内存函数主要为：

void *pvPortMalloc( size_t xWantedSize ); //申请内存空间，指定大小，并返回一个指针
void vPortFree( void *pv );//释放指定地址下申请的内存空间
1
2

heap_4.c的内存堆本身是一个很大的数组，定义原型为

static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
1

其中configTOTAL_HEAP_SIZE 在freertos的头文件中进行了配置，每次申请内存都是从这个大数组里面申请的。也就是说，每次都会从这个大数组里面找到一个地址然后返回给申请者。

理解heap_4.c的关键点

1. 1:heap_4.c使用链表进行了空闲块的管理。
   这句话可以理解为，heap_4.c使用了链表将空闲的内存块地址进行连接 ，由此可有两个疑问，1）链表使用的空间哪里来呢。2）已经被申请的内存块就不会被链表管理吗？回答第一个问题，链表本身使用的空间也是来自这个大数组，链表本身和用申请的空间本身是连在一起的。回答第二个问题，已经被申请的空间是不会被链表链接进去的，会被链表删除，已经申请的空间会在释放的时候与其它内存块进行联系和合并，但是它本身节点已经被链表移除。

2. heap_4.c对相邻的空闲内存块进行合并处理。
   看这句话会有如下疑问。1）空闲块在什么时候进行合并。2)空闲块是如何进行合并的。3）已经被申请的内存，已经不被链表进行管理，那么释放已经申请的内存是如何找到前面的空闲块的。先回答第一个问题，空闲块在内存释放的时候变成空闲块的时候，和申请内存的时候会有新的空闲内存块，然后进行合并。回答第二个问题，如果两个空闲块都被连接进来，那么只要两个空闲块地址连接在一起就可以进行合并。回答第三个问题，释放内存时的空闲块会遍历所有链表，然后找到当前空闲块的前一个空闲块和后一个空闲块，如果地址重叠可以判定进行空闲块合并。

图示heap_4.c内存申请过程

内存状态分为：
1：刚初始化完成的内存空间

刚初始化完的堆内存如如上图所示，xStart节点为一个是一个全局静态链表节点，指向第一个空闲块，而pxEnd *是一个静态的链表节点地址，指向内存堆的最后一个节点。第一个内存链表节点排列在内存的前面，空闲块大小为中白色的地方的大小。内存堆的头和尾会因为字节对齐而被丢弃。

2：申请一个的内存空间

上图是申请一次之后的内存空间图，对比刚初始化完成可以发现，初始化完成之后的第一的节点被申请成功后，赋值的新的内存块大小，并当前节点从链表中删除，然后在申请内存占用最大的地方建立了一个新的空闲内存块节点，新的内存块没有被使用，因此被链表进行了管理，链表中只管理空闲的内存块。

图示heap_4.c内存合并过程

合并分为两种
1：前向合并内存块

前向合并代码如上图所示，前向合并仅仅是将blockSize加上了后面的大小而已

2：后向合并内存块

向后合并内存块与向前合并内存块有所不同，向后合并内存块，合并之后前面的链表指针指向了向后面内存地址。然后是将大小添加了后面内存的大小。

内存初始化源码分析

static void prvHeapInit( void )
{
//第一个内存块指针
BlockLink_t *pxFirstFreeBlock;
uint8_t *pucAlignedHeap;
uint32_t ulAddress;
//总大小
size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;

	/* Ensure the heap starts on a correctly aligned boundary. */
	//得到内存堆首地址
	ulAddress = ( uint32_t ) ucHeap;
	//进行字节对齐
	if( ( ulAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
	{
		ulAddress += ( portBYTE_ALIGNMENT - 1 );
		ulAddress &= ~portBYTE_ALIGNMENT_MASK;
		xTotalHeapSize -= ulAddress - ( uint32_t ) ucHeap;
	}
	//对齐之后的地址
	pucAlignedHeap = ( uint8_t * ) ulAddress;
	
	/* 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;
	//初始化结束链表节点
	/* pxEnd is used to mark the end of the list of free blocks and is inserted
	at the end of the heap space. */
	ulAddress = ( ( uint32_t ) pucAlignedHeap ) + xTotalHeapSize;
	ulAddress -= xHeapStructSize;
	ulAddress &= ~portBYTE_ALIGNMENT_MASK;
	pxEnd = ( void * ) ulAddress;
	pxEnd->xBlockSize = 0;
	pxEnd->pxNextFreeBlock = NULL;

	/* To start with there is a single free block that is sized to take up the
	entire heap space, minus the space taken by pxEnd. */
	//初始化第一个链表节点
	pxFirstFreeBlock = ( void * ) pucAlignedHeap;
	pxFirstFreeBlock->xBlockSize = ulAddress - ( uint32_t ) pxFirstFreeBlock;
	pxFirstFreeBlock->pxNextFreeBlock = pxEnd;
	#if defined(MTK_SUPPORT_HEAP_DEBUG) || defined(MTK_HEAP_SIZE_GUARD_ENABLE)
	pxFirstBlock = pxFirstFreeBlock;
	#endif
 	//得到最小的剩余内存
	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 );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

初始化内存池主要完成以下任务：
初始化xStart节点
初始化xEnd节点
初始化pxFirstFreeBlock节点

内存申请源码分析

void *pvPortMalloc( size_t xWantedSize )
{
	BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
	void *pvReturn = NULL;


	vTaskSuspendAll();
	{
		/* If this is the first call to malloc then the heap will require
		initialisation to setup the list of free blocks. */
		if( pxEnd == NULL )
		{
			//初始化链表
			prvHeapInit();
		}
		else
		{
			mtCOVERAGE_TEST_MARKER();
		}

		/* Check the requested block size is not so large that the top bit is
		set.  The top bit of the block size member of the BlockLink_t structure
		is used to determine who owns the block - the application or the
		kernel, so it must be free. */
		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. */
				pxPreviousBlock = &xStart;
				pxBlock = xStart.pxNextFreeBlock;
				//遍历链表，找到一个空闲块大于当前申请空间的节点 
				while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
				{
					pxPreviousBlock = pxBlock;
					pxBlock = pxBlock->pxNextFreeBlock;
				}

				/* If the end marker was reached then a block of adequate size
				was	not found. */
				//如果不是最后一个节点
				if( pxBlock != pxEnd )
				{
					/* Return the memory space pointed to - jumping over the
					BlockLink_t structure at its start. */
					//计算返回地址   等于前   + 结构体的地址    (第一个没有使用)
					pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
					#ifdef MTK_SUPPORT_HEAP_DEBUG
					pxPreviousBlock->pxNextFreeBlock->xLinkRegAddr = xLinkRegAddr;
					#endif /* MTK_SUPPORT_HEAP_DEBUG */

					/* This block is being returned for use so must be taken out
					of the list of free blocks. */
					//前一个节点的下一个 指向当前节点的下一个 
					pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;

					/* 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. */
						//将剩余空间 一分为2   ？  创建新的链表 节点  
						pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
						configASSERT( ( ( ( uint32_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->pxNextFreeBlock = NULL;
				}
				else
				{
					mtCOVERAGE_TEST_MARKER();
				}
			}
			else
			{
				mtCOVERAGE_TEST_MARKER();
			}
		}
		else
		{
			mtCOVERAGE_TEST_MARKER();
		}

		traceMALLOC( pvReturn, xWantedSize );
	}
	( void ) xTaskResumeAll();


	configASSERT( ( ( ( uint32_t ) pvReturn ) & portBYTE_ALIGNMENT_MASK ) == 0 );
	return pvReturn;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

内存释放分析

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 -= xHeapStructSize;

		/* This casting is to keep the compiler from issuing warnings. */
		pxLink = ( void * ) puc;

		/* Check the block is actually allocated. */
		configASSERT( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 );
		configASSERT( pxLink->pxNextFreeBlock == NULL );
		//确保链表使用了
		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;

				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();
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

空闲块内存合并源码分析

static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert )
{
BlockLink_t *pxIterator;
uint8_t *puc;

	/* Iterate through the list until a block is found that has a higher address
	than the block being inserted. */
	//遍历链表 找到当前 链表  物理地址前面的一个链表节点
	for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
	{
		/* Nothing to do here, just iterate to the right position. */
	}

	/* Do the block being inserted, and the block it is being inserted after
	make a contiguous block of memory? */
 
	//前向合并
	puc = ( uint8_t * ) pxIterator;
	//如果前面空闲块结束地址 等于当前链表的开始地址
	if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
	{
		//前面的链表 块 大小 += 当前链表块大小
		pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
		pxBlockToInsert = pxIterator;
	}
	else
	{
		mtCOVERAGE_TEST_MARKER();
	}

	/* Do the block being inserted, and the block it is being inserted before
	make a contiguous block of memory? */
	//后向合并内存块
	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 the block being inserted plugged a gab, so was merged with the block
	before and the block after, then it's pxNextFreeBlock pointer will have
	already been set, and should not be set here as that would make it point
	to itself. */
	if( pxIterator != pxBlockToInsert )
	{
		pxIterator->pxNextFreeBlock = pxBlockToInsert;
	}
	else
	{
		mtCOVERAGE_TEST_MARKER();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67