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)
Sign in with Wallet
Connect another wallet