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

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

void *pvPortMalloc( size_t xWantedSize )
{
BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
void *pvReturn = NULL;
	//掛起調(diào)度器，防止函數(shù)重入
	vTaskSuspendAll();
	{
		/* If this is the first call to malloc then the heap will require
		initialisation to setup the list of free blocks. */
		//pxEnd是NULL則是第一次調(diào)用，需要初始化堆
		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. */
		//xBlockAllocatedBit = 0x8000_0000;
		//待分配的內(nèi)存不能大于0x7FFF_FFFF，否則失敗
		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 )
			{
			    //加上管理結(jié)構(gòu)體占用大小
				xWantedSize += xHeapStructSize;
				/* Ensure that blocks are always aligned to the required number
				of bytes. */
				//xWantedSize大小進行字節(jié)對齊調(diào)整
				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();
			}
            //xWantedSize大于0且小于等于此時還剩字節(jié)數(shù)才能往下申請
			if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
			{
				/* Traverse the list from the start	(lowest address) block until
				one	of adequate size is found. */
				//pxPreviousBlock指向頭鏈表
				pxPreviousBlock = &xStart;
				//pxBlock指向頭鏈表的下一個即第一個空閑塊
				pxBlock = xStart.pxNextFreeBlock;
				//開始遍歷找到第一個比xWantedSize大的空閑塊
				while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
				{
				    //pxPreviousBlock保存空閑塊的上一個
					pxPreviousBlock = pxBlock;
					pxBlock = pxBlock->pxNextFreeBlock;
				}
				/* If the end marker was reached then a block of adequate size
				was	not found. */
				//遍歷完成pxBlock != pxEnd說明找到符合的空閑塊
				if( pxBlock != pxEnd )
				{
					/* Return the memory space pointed to - jumping over the
					BlockLink_t structure at its start. */
					//返回給用戶的內(nèi)存地址要跳過管理結(jié)構(gòu)體占用的內(nèi)存大小
					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指向的空閑塊被分配了，
					//所以要把pxPreviousBlock->pxNextFreeBlock指向的空閑塊移除出去，
					//也就是pxPreviousBlock->pxNextFreeBlock指向pxBlock->pxNextFreeBlock
					//也就是跳過分配出去的那個塊
					pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
					/* If the block is larger than required it can be split into
					two. */
					//這里判斷，
					//如果將要分配出去的內(nèi)存塊大小xBlockSize比分配出去的還要大heapMINIMUM_BLOCK_SIZE(2倍管理結(jié)構(gòu)體)
					//為了節(jié)約就把再分成2塊，一塊返回給用戶，
					//一塊構(gòu)造一個新的空閑管理結(jié)構(gòu)體后插入空閑鏈表
					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. */
						//注意這里xWantedSize是管理結(jié)構(gòu)體和和真正需要字節(jié)數(shù)之和
						//所以是在pxBlock基礎(chǔ)上偏移xWantedSize作為新的管理結(jié)構(gòu)體
						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新的管理結(jié)構(gòu)體大小
						//是待分配pxBlock->xBlockSize-xWantedSize
						pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
						//更新pxBlock->xBlockSize大小為xWantedSize
						pxBlock->xBlockSize = xWantedSize;
						/* Insert the new block into the list of free blocks. */
						//把新構(gòu)造的空閑管理結(jié)構(gòu)體按結(jié)構(gòu)體地址升序插入到空閑鏈表
						prvInsertBlockIntoFreeList( pxNewBlockLink );
					}
					else
					{
						mtCOVERAGE_TEST_MARKER();
					}
					//還?？臻e字節(jié)數(shù)要減去分配出去的
					xFreeBytesRemaining -= pxBlock->xBlockSize;
					//更新歷史最小剩余字節(jié)數(shù)
					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. */
					//xBlockSize最高位置1表示被這塊內(nèi)存被分配出去
					pxBlock->xBlockSize |= xBlockAllocatedBit;
					//所以管理結(jié)構(gòu)體的next要指向NULL
					pxBlock->pxNextFreeBlock = NULL;
				}
				else
				{
					mtCOVERAGE_TEST_MARKER();
				}
			}
			else
			{
				mtCOVERAGE_TEST_MARKER();
			}
		}
		else
		{
			mtCOVERAGE_TEST_MARKER();
		}
		traceMALLOC( pvReturn, xWantedSize );
	}//解掛調(diào)度器
	( void ) xTaskResumeAll();
    //如果定義了分配失敗鉤子函數(shù)，分配失敗則執(zhí)行鉤子函數(shù)
	#if( configUSE_MALLOC_FAILED_HOOK == 1 )
	{
		if( pvReturn == NULL )
		{
			extern void vApplicationMallocFailedHook( void );
			vApplicationMallocFailedHook();
		}
		else
		{
			mtCOVERAGE_TEST_MARKER();
		}
	}
	#endif
//返回給用戶
	configASSERT( ( ( ( size_t ) pvReturn ) & ( size_t ) portBYTE_ALIGNMENT_MASK ) == 0 );
	return pvReturn;
}

static void prvHeapInit( void )
{
BlockLink_t *pxFirstFreeBlock;
uint8_t *pucAlignedHeap;
size_t uxAddress;
size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;
	/* Ensure the heap starts on a correctly aligned boundary. */
	uxAddress = ( size_t ) ucHeap;
    //這里進行字節(jié)對齊
	if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
	{
		uxAddress += ( portBYTE_ALIGNMENT - 1 );
		uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
		//此時xTotalHeapSize表示管理的總內(nèi)存字節(jié)數(shù)
		xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;
	}
    //pucAlignedHeap指向?qū)R后首址
	pucAlignedHeap = ( uint8_t * ) uxAddress;
	/* 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. */
	//uxAddress此時指向管理內(nèi)存最后
	uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
	//退回一個BlockLink_t(字節(jié)對齊后)大小字節(jié)數(shù)
	uxAddress -= xHeapStructSize;
	//再次字節(jié)對齊
	uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
	//初始化尾鏈表
	pxEnd = ( void * ) uxAddress;
	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;
	//第一個空閑塊字節(jié)數(shù)=uxAddress(此時值=pxEnd) - pxFirstFreeBlock(此時值=pucAlignedHeap)
	pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;
	//第一個空閑塊指向尾節(jié)點
	pxFirstFreeBlock->pxNextFreeBlock = pxEnd;
	/* Only one block exists - and it covers the entire usable heap space. */
	//更新歷史還剩最少空閑字節(jié)數(shù)
	xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
	//更新實時還剩字節(jié)數(shù)
	xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
	/* Work out the position of the top bit in a size_t variable. */
	//這里sizeof( size_t ) = 4,heapBITS_PER_BYTE=8,表示1字節(jié)有8bit
	//xBlockAllocatedBit = 1<<(4*8-1) = 0x8000_0000;
	//FreeRTOS用xBlockSize最高位來標記此內(nèi)存塊是否空閑
	//所以heap4最大只能管理0x7FFF_FFFF字節(jié)內(nèi)存
	xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
}

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. */
	//這里是根據(jù)內(nèi)存塊的地址大小來迭代尋找和pxBlockToInsert相鄰的前一個空閑的內(nèi)存塊
	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? */
	//這里判斷pxBlockToInsert是否能與pxBlockToInsert相鄰的前一個空閑的內(nèi)存塊合并
	puc = ( uint8_t * ) pxIterator;
	if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
	{   //這里做向前合并,xBlockSize相加
		pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
		//pxBlockToInsert指向pxIterator
		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? */
	//這里再判斷是否能與后一個內(nèi)存塊合并
	puc = ( uint8_t * ) pxBlockToInsert;
	if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
	{   //這里做向后合并，如果要合并的后向不是pxEnd
		if( pxIterator->pxNextFreeBlock != pxEnd )
		{  //這里把后項合入到pxBlockToInsert
			/* Form one big block from the two blocks. */
			pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
			//pxBlockToInsert的下一個指向后項指向的空閑塊
			pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
		}
		else//如果后項是pxEnd就不能合并，指向pxEnd
		{
			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();
	}
}

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. */
		//檢查這個內(nèi)存塊是否是heap4之前分配的
		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. */
				//把分配的xBlockSize最高位標記清除
				pxLink->xBlockSize &= ~xBlockAllocatedBit;
                //掛起調(diào)度器
				vTaskSuspendAll();
				{
					/* Add this block to the list of free blocks. */
				   //更新剩余內(nèi)存數(shù)
					xFreeBytesRemaining += pxLink->xBlockSize;
					traceFREE( pv, pxLink->xBlockSize );
					//插入空閑內(nèi)存鏈表
					prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
				}//解掛調(diào)度器
				( void ) xTaskResumeAll();
			}
			else
			{
				mtCOVERAGE_TEST_MARKER();
			}
		}
		else
		{
			mtCOVERAGE_TEST_MARKER();
		}
	}
}

size_t xPortGetFreeHeapSize( void )
{
	return xFreeBytesRemaining;
}

size_t xPortGetMinimumEverFreeHeapSize( void )
{
	return xMinimumEverFreeBytesRemaining;
}