---
# System prepended metadata

title: 2021 嵌入式作業系統分析與實做 Lab4 report
tags: [FreeRTOS]

---

2021 嵌入式作業系統分析與實做 Lab4 report
===
[Lab4](https://docs.google.com/presentation/d/1SAb8jS3tac0BpAkFxz-q6QqMzWEK63KdGZw4KxRxsn8/edit#slide=id.gd16f07b711_2_50)
contribute by `Liao712148`
###### tags: `FreeRTOS`
### Lab要求
* Step1:
    * Use Uart to show Free linked list.
    * Create a task to call vPrintFreeList.
    * Implement your vPrintFreeList function in heap_2.c.
* Step2:
    * Modifying prvInsertBlockIntoFreeList code in heap_2.c to implement memory merge.
*  Create six tasks
    *    RedLEDTask
    *    GreenLEDTask
    *    Task1
    *    Task2
    *    Task3
    *    PrintTask
*    Task1、Task2、Task3 will delete themselves.
*    PrintTask will call vPrintFreeList function to show free list information.


###  實做流程
####   Heap_2
*    introduce
    *    Heap_2 記憶體分配使用的是`best fit algorithm`.
    *    Heap_2 支持記憶體回收，但是==不會把相鄰的回收後的記憶體做合併==，所以有可能造成**記憶體破碎化**。
    *    適合用在雖然需要釋放記憶體但是每個task需要的TCB、Stack是相同的。這樣釋放後的記憶體空間就能直接被其他的task使用，可以避免**記憶體破碎化**。
*    在call xTaskCreate()會調用 pvPortMalloc() 來跟memory要空間，可以從xTaskCreate()發現task中的TCB, Stack 是分開跟memory要空間的。
```cpp=
BaseType_t xTaskCreate(	TaskFunction_t pxTaskCode,
							const char * const pcName,		/*lint !e971 Unqualified char types are allowed for strings and single characters only. */
							const configSTACK_DEPTH_TYPE usStackDepth,
							void * const pvParameters,
							UBaseType_t uxPriority,
							TaskHandle_t * const pxCreatedTask )
{
                        /*...*/
			/* Allocate space for the TCB.  Where the memory comes from depends on
			the implementation of the port malloc function and whether or not static
			allocation is being used. */
			pxNewTCB = ( TCB_t * ) pvPortMalloc( sizeof( TCB_t ) );
                        /*...*/
			/* Allocate space for the stack used by the task being created. */
			pxStack = pvPortMalloc( ( ( ( size_t ) usStackDepth ) * sizeof( StackType_t ) ) ); 
 
                        /*...*/
}
```
---
*    因為heap2有支持記憶體釋放，但是釋放後的記憶體不能互相合併，所以我們必須將釋放後的記憶體區塊，用一個list串接起來。並且依照區塊的大小由小到大串接起來。以方便做`best fit algorithm`。所以有必要在第一次調用pvPortMalloc()的時候，初始化一個free list。

```cpp=
static void prvHeapInit( void )
{
BlockLink_t *pxFirstFreeBlock;
uint8_t *pucAlignedHeap;
	pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) );

	xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
	xStart.xBlockSize = ( size_t ) 0;

	xEnd.xBlockSize = configADJUSTED_HEAP_SIZE;
	xEnd.pxNextFreeBlock = NULL;

	pxFirstFreeBlock = ( void * ) pucAlignedHeap;
	pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE;
	pxFirstFreeBlock->pxNextFreeBlock = &xEnd;
}
```
*    第`5`行：記憶體對齊
    *    ucHeap是一個由`uint8_t`組成，大小為`configTOTAL_HEAP_SIZE`的陣列。所以分配記憶體其實是在一個陣列上做劃分。
    *    但是ucHeap並沒有保證會是記憶體對齊的，所以並不是整個ucHeap都能夠使用。最先能使用的地方為第一個滿足記憶體對齊的記憶體位址。舉例來說假設&ucHeap[0]的記憶體位址是0x00000003並不滿足記憶體對齊的條件。而&ucHeap[8]的記憶體位址是0x0000000B，所以如果遮蔽最低3個bit。可以得到0x00000008。此記憶體位址滿足記憶體對齊。所以就能找出第一個能使用的記憶體位址。但是浪費了0x00000003~0x00000007的記憶體。
*  第`7~16`行： 並將這個記憶體位址，和將剩下可以用的空間(configTOTAL_HEAP_SIZE - 8 )一起存入pxFirstFreeBlock。然後在用xStart串起，xStart為free list的開頭，xEnd則為結尾。
---
*    以下為pvPortMalloc() trace
```cpp=
void *pvPortMalloc( size_t xWantedSize )
{
BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
static BaseType_t xHeapHasBeenInitialised = pdFALSE;
void *pvReturn = NULL;
size_t BlockSize,WantedSize;
WantedSize = xWantedSize;

	vTaskSuspendAll();
	{
		/* If this is the first call to malloc then the heap will require
		initialisation to setup the list of free blocks. */
		if( xHeapHasBeenInitialised == pdFALSE )
		{
			prvHeapInit();
			xHeapHasBeenInitialised = pdTRUE;
		}

		/* 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 += heapSTRUCT_SIZE;

			/* Ensure that blocks are always aligned to the required number of bytes. */
			if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0 )
			{
				/* Byte alignment required. */
				xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
			}
		}

		if( ( xWantedSize > 0 ) && ( xWantedSize < configADJUSTED_HEAP_SIZE ) )
		{
			/* Blocks are stored in byte order - traverse the list from the start
			(smallest) 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 we found the end marker then a block of adequate size was not found. */
			if( pxBlock != &xEnd )
			{
				/* Return the memory space - jumping over the BlockLink_t structure
				at its start. */
				pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );

				/* 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. */
					pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );

					/* 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 ) );
				}

				xFreeBytesRemaining -= pxBlock->xBlockSize;
			}
		}

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

	#if( configUSE_MALLOC_FAILED_HOOK == 1 )
	{
		if( pvReturn == NULL )
		{
			extern void vApplicationMallocFailedHook( void );
			vApplicationMallocFailedHook();
		}
	}
	#endif
	return pvReturn;
}
```
*    第`9`行：調用了vTaskSuspendAll()，suspend所有的task，已保證thread safe，避免分配記憶體的過程被打斷。
*    第`13`行：透過`xHeapHasBeenInitialised`來檢查是否已經初始化free list。如果已經有初始化過的話，該變數會被改成`pdTRUE`，否則為`pdFALSE`。因為有用static修飾該變數，因此下次調用pvPortMalloc()時，該變數仍然存在。
*    第`23`行：由於除了我們要allocate的記憶體大小外，還要多allocate一個heapSTRUCT_SIZE的空間用來存放下一個free  block的記憶體位址以及本次allocate的所有空間, i.e. xWantedSize = heapSTRUCT_SIZE + 我們要allocate的記憶體大小。
*    第`26~30`行：檢查總共要allocate的空間(xWantedSize)是否能滿足記憶體對齊，如果不滿足就要allocate到最小能夠記憶體對齊的記憶體空間。
*    第`39~43`行：在free list中找尋與大於xWantedSize且最接近的free block。
*    第`50`行：找到的適合的free block後，就可以將該記憶體位址返回給使用者，要注意的是==記憶體區塊的一開始是存放BlockLink_t的資料節構==，所以我們真正會使用的地方應該是要在這個資料結構之後，所以我們的回傳的記憶體位址要是`	pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );
`
*    第`54`行：將該free block從記憶體串列中刪除。
*    第`57~71`行：我們分配出去的free block雖然會滿足`best fit algorithm`但是有可能free block的空間還是超過xWantedSize很多。這時候就可以把過多的部份回收回來。透過`pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );`可以得到於的記憶體位址，形成新的free block，在將多餘的記憶體大小存入該free block中，再利用`prvInsertBlockIntoFreeList( ( pxNewBlockLink ) )`將這個新的free block串回 free list中。
*    第`73`行：更改剩餘的記憶體空間的大小。
---
##### Step 1:
Lab要求1，是要print出free list中的每個free block的起始位址、結束的位址、block的大小、剩餘的記憶體空間。
透過上述對free list的講解可以知道每個free block是透過linked list根據free block的大小，由小到大的方式串接起來的。所以透過free list的走訪即可找出每個free block中的相關資訊。
```cpp=
void vPrintFreeList( void )
{
	char MonitorTset[60] = "StartAddress|heapSTRUCT_SIZE|xBlockSize|EndAddress";
	char startadderss[15];
	char endaddress[15];
	char pxStack[15];
	memset(pxStack,'\0',sizeof(pxStack));
	sprintf(pxStack," %s \n\r",MonitorTset);
	HAL_UART_Transmit(&huart2,(uint8_t *)pxStack,strlen(pxStack),0xffff);
	BlockLink_t *temp ;
	temp = xStart.pxNextFreeBlock;
	while (temp != NULL && temp->pxNextFreeBlock != NULL)
	{
		memset(pxStack,'\0',sizeof(pxStack));
		memset(pxStack,'\0',sizeof(startadderss));
		memset(pxStack,'\0',sizeof(endaddress));
		memset(MonitorTset,'\0',sizeof(MonitorTset));
		Uint32ConvertHex((uint32_t)(temp), startadderss);
		Uint32ConvertHex((uint32_t)(temp)+(uint32_t)(temp->xBlockSize), endaddress);
		sprintf(MonitorTset,"%s	%0d %0d %s\n\r",startadderss, heapSTRUCT_SIZE,temp->xBlockSize,endaddress);
		HAL_UART_Transmit(&huart2,(uint8_t *)MonitorTset,strlen(MonitorTset),0xffff);
		temp = temp->pxNextFreeBlock;
	}
	memset(MonitorTset,'\0',sizeof(MonitorTset));
	sprintf(MonitorTset," configADJUSTED_HEAP_SIZE:%0d   xFreeBytesRemaining:%d \n\r",configADJUSTED_HEAP_SIZE, xFreeBytesRemaining );
	HAL_UART_Transmit(&huart2,(uint8_t *)MonitorTset,strlen(MonitorTset),0xffff);
}
```
*    第`10,11`行：宣告一個變數，其型別為poniter to BlockLink_t，用來對free list做走訪。
*    第`12`行：為走訪的判斷式
    *    第`18`行：因為是用pointer做走訪，所以pointer的值就是該free block的記憶體起始位址。所以直接將pointer的值，轉成16進位即為所求。
    *    第`19`行：將pointer的值加上該free block的block size即可得到該free block的中止位址。

##### Step 2:
根據lab的要求要將相鄰的free block合併成一個大塊的free block，在free list中的排序依就是要從小的free block size排到大的。
思路：在每加入一塊new_free block的同時就需要根據新的free block的記憶體起始、中止位址，然後在free list中找看由沒有相鄰近的free block。如果有的話就將該free block與本次要加進去的new_free block合併成一個更大塊的new_free block，==並將原先的free block從free list中移除==。
由於free block串入 free list是透過`prvInsertBlockIntoFreeList`，所以我們需要對這個macro做修改。
```cpp=
#define prvInsertBlockIntoFreeList( pxBlockToInsert )	        \
{		                        																			\
BlockLink_t *pxIterator, *pxprevious, *target;												\
size_t xBlockSize;                                                                                                                                            \
uint32_t startaddress, endaddress, tempeendaddress;                                                                    \
tempeendaddress = (uint32_t)pxBlockToInsert + (uint32_t)pxBlockToInsert->xBlockSize;   \
pxprevious = &xStart;                                                                                                                                     \
target = xStart.pxNextFreeBlock;                                                                                                                \
while(target != &xEnd)                                                                                                                                    \
{                                                                                                                                                                               \
	startaddress = (uint32_t) target;                                                                                                         \
	endaddress = startaddress + (uint32_t)target->xBlockSize;                                                       \
	if (startaddress == tempeendaddress||endaddress ==(uint32_t)pxBlockToInsert )             \
	{                                                                                                                                                                        \
		pxBlockToInsert->xBlockSize = pxBlockToInsert->xBlockSize +target->xBlockSize;     \
		pxprevious->pxNextFreeBlock = target->pxNextFreeBlock;	                                                \
		target->pxNextFreeBlock = NULL;                                                                                                    \
		target = pxprevious->pxNextFreeBlock;                                                                                        \
	}                                                                                                                                                                         \
else{                                                                                                                                                                        \
	target = target->pxNextFreeBlock;	                                                                                                    \
	pxprevious = pxprevious->pxNextFreeBlock;                                                                                     \
	}                                                                                                                                                                        \
}                                                                                                                                                                                \
		xBlockSize = pxBlockToInsert->xBlockSize;										            \
	/* Iterate through the list until a block is found that has a larger size */	                           \
	/* than the block we are inserting. */											                            \
	for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock )	\
	{																				                            \
		/* There is nothing to do here - just iterate to the correct position. */	                            \
	}																				                            \
	/* Update the list to include the block being inserted in the correct */		                            \
	/* position. */																	                            \
	pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;					       \
	pxIterator->pxNextFreeBlock = pxBlockToInsert;									              \
}
```
*    第`3`行：宣告target類型為pointer to BlockLink_t，用來走訪整個free list。
*    第`6`行：tempeendaddress用來存放新加入的pxBlockToInsert的中止位址。
*    第`10,11`行：startaddress、endaddress為當下走訪的free block他的起始位址和中止位址
*    第`13~19`行：如果有發現該free block的位址與我們要加入的pxBlockToInsert相鄰就要將兩個不同的 block合併。
    *     第`15`行：將pxBlockToInsert的blocl size更改成兩個free block的blocl size相加。
    *     第`16`行：把找到的free block從free list中移除。
    *     第`17`行：並將free block指向NULL。以防止錯誤發生。
*    第`25~35`行：此時pxBlockToInsert的Block Size已經被修改，爾且相鄰的free block也已經移除。引此可以透過原先的方式將pxBlockToInsert依據free block size由小到大的插入free list中。
##### Step 3:
初始化task
```cpp=
int main(void)
{

  /* ... */
  xTaskCreate(RedLEDTask,"RedLEDTask",100,NULL,0,NULL);
  xTaskCreate(Task1,"Task1",50,NULL,0,NULL);
  xTaskCreate(Task2,"Task2",30,NULL,0,NULL);
  xTaskCreate(GreenLEDTask,"GreenLEDTask",130,NULL,0,NULL);
  xTaskCreate(Task3,"Task3",40,NULL,0,NULL);
  xTaskCreate(PrintTask,"PrintTask",130,NULL,0,NULL);
  vTaskStartScheduler();

  /* ... */
}
void RedLEDTask(void const * argument)
{
	for(;;)
	{
		HAL_GPIO_TogglePin(Red_LED_GPIO_Port, GPIO_PIN_14);
		vTaskDelay(500);
	}
}
void GreenLEDTask(void const * argument)
{
	for(;;)
	{
		HAL_GPIO_TogglePin(Green_LED_GPIO_Port, GPIO_PIN_12);
		vTaskDelay(1000);
	}
}
void Task1(void const * argument)
{
	for(;;)
	{
		vTaskDelete( NULL );
	}
}
void Task2(void const * argument)
{
	for(;;)
	{
		vTaskDelete( NULL );
	}
}

void Task3(void const * argument)
{
	for(;;)
	{
		vTaskDelete( NULL );
	}
}
void PrintTask(void const * argument)
{
	for(;;)
	{
		vPrintFreeList();
		vTaskDelay(3000);
	}
}
```
###  心得
謝謝助教的幫忙。
###  參考資料
[FreeRTOS程式碼閱讀筆記：heap_2.c](https://www.itread01.com/content/1540952709.html)
[FreeRTOS程式碼閱讀筆記：heap_4.c](https://www.itread01.com/content/1540952703.html)
[FreeRTOS(五)——heap檔案解析](https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/101847/)
[FreeRTOS 内存 Heap管理](https://www.jianshu.com/p/c5fbad706e9f)

