Lab 4 - HackMD

# Lab 4  > 國立成功大學資訊工程學系嵌入式作業系統分析與實作 Analysis and Implementation of Embedded Operating Systems [CSIE7618] 2022 Spring > GitHub: https://github.com/cpt1020/EmbeddedOS-Lab4 ## Objective 瞭解 FreeRTOS 管理 free memory block 之機制 ## Requirement :::info - Part 0 - Create 6 tasks: - `red_LED_task` - `green_LED_task` - `task1` - `task2` - `task3` - `print_task` - `task1`, `task2`, and `task3` will delete themselves - `print_task` will call `vPrintFreeList` function to show free list information - Part 1 - Use UART to show free memory list - Create a task to call `vPrintFreeList` - Implement your `vPrintFreeList` function in `heap_2.c` - Part 2 - Modify `prvInsertBlockIntoFreeList` macro in `heap_2.c` to implement memory merging ![image](https://hackmd.io/_uploads/r1Dt83-ET.png) Part 1 的 `vPrintFreeList` 功能做好後應該要能印出上圖的資訊，此 function 會把 free memory list 的每個 free memory block 的資訊印出來。此圖可看到許多 free memory block 其實是相鄰的，可以做合併。 ![image](https://hackmd.io/_uploads/rJG082bNT.png) Part 2 修改完 `prvInsertBlockIntoFreeList` macro 後，要能把相鄰的 free memory block 合併，合併後印出來的資訊要如上圖一樣。 ::: ## Prerequisites and Configuration Setup - Project前置設定可參考這篇 https://hackmd.io/@cpt/embeddedOS_lab0 - USART設定可參考這篇 https://hackmd.io/@cpt/embeddedOS_USART ### Pin Configuration in STM32CubeIDE ![image](https://hackmd.io/_uploads/ry0O_3WN6.png) - 最重要的就是左下角的兩個 USART2 的 pin 引腳要設定 - LED 燈也要設定為 `GPIO_Output` ## Template 至[此連結](https://drive.google.com/file/d/1-9Vmgm90TWZJ0yOkk8-Cb90s1n8bCPoO/view?usp=sharing)取得助教所提供的這次 lab 的 template，下載後將這些檔案取代原本自己 project 中相對應的檔案 ``` lab 4 template ├── Core │ └── Src │ └── main.c └── FreeRTOS ├── include │ ├── FreeRTOSConfig.h │ ├── portable.h │ └── task.h ├── portable │ └── MemMang │ └── heap_2.c └── tasks.c ``` :::info - 記得要將原本 `FreeRTOS/portable/MemMang` 內的 `heap_4.c` 刪掉 - template 中的 `task.h` 的 `UART_HandleTypeDef huart2;` 要改成 `extern UART_HandleTypeDef huart2;` ，否則編譯時會出現 multiple definition 的錯誤訊息(我自己的電腦是會有這狀況啦@@) - 編譯時若出現 pin 的名稱 undeclared 之類的錯誤訊息，可以點 `generate code` 來產出相對應的 pin 名稱 - 助教給的 template code 直接去執行的話會出現以下的 output ![image](https://hackmd.io/_uploads/SkPkOaJE6.png) ::: ## `heap_2.c` in FreeRTOS - 如果依照 template 來做的話，Part 1 主要就是要在 `heap_2.c` 完成 `void vPrintFreeList(void)` 這個 function - 如果要完成這 function 就需要理解 FreeRTOS 用什麼 struct 來記錄這些 free memory block ```cpp=73 /* Define the linked list structure. This is used to link free blocks in order of their size. */ 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; static const uint16_t heapSTRUCT_SIZE = ( ( sizeof ( BlockLink_t ) + ( portBYTE_ALIGNMENT - 1 ) ) & ~portBYTE_ALIGNMENT_MASK ); #define heapMINIMUM_BLOCK_SIZE ( ( size_t ) ( heapSTRUCT_SIZE * 2 ) ) /* Create a couple of list links to mark the start and end of the list. */ static BlockLink_t xStart, xEnd; ``` 以上 `heap_2.c` 內的程式碼可以看到，`heap_2.c` 是用 `BlockLink_t` 這個struct來記錄free memory block - `pxNextFreeBlock` 會指向下一個free memory block的 `BlockLink_t` - `xBlockSize` 則是紀錄目前這個free memory block有多大 - 記錄每個free memory block的 `BlockLink_t` 其實會存放在該free memory block的起始位址，所以只要對該 `BlockLink_t` 取他的address，就可以知道這個free memory block從哪裡開始(也就是start address) - start address + `xBlockSize` = end address 另外，在第86行宣告兩個 `BlockLink_t` 的global variable `xStart` 和 `xEnd` 來當作這個list的頭跟尾。第82行則是 `BlockLink_t` 的size，用 `heapSTRUCT_SIZE` 來表示<br>(`heap_2.c` 後面的程式碼都用 `heapSTRUCT_SIZE` 來表示 `BlockLink_t` 的size) - `portBYTE_ALIGNMENT` 被定義在 `portmacro.h`，是 `8` - `portBYTE_ALIGNMENT_MASK` 被定義在 `portable.h`，是 `0x0007`，也就是 `0000 0000 0000 0111` - `( ( sizeof ( BlockLink_t ) + ( portBYTE_ALIGNMENT - 1 ) ) & ~portBYTE_ALIGNMENT_MASK )` 是為了要對齊8，手算出來的結果也是 `8` - 但 `sizeof(BlockLink_t)` 印出來也是 `8` - 所以我其實不太瞭解為什麼不直接 `static const uint16_t heapSTRUCT_SIZE = ( sizeof ( BlockLink_t ) );` 這樣就好了Ｑ＿Ｑ？ :::info 之後思考了一下 `uint16_t heapSTRUCT_SIZE = ( ( sizeof ( BlockLink_t ) + ( portBYTE_ALIGNMENT - 1 ) ) & ~portBYTE_ALIGNMENT_MASK )` 這件事~好像有想通了今天這個 `BlockLink_t` 是因為在這塊開發板上才會 `sizeof` 得到8，那有可能在其他的 CPU 經由 `sizeof` 得到的就不一定是8 那由於記憶體位址要對齊 8 的倍數，所以要確保分配給 `BlockLink_t` 的空間是 8 的倍數，所以用 `( ( sizeof ( BlockLink_t ) + ( portBYTE_ALIGNMENT - 1 ) ) & ~portBYTE_ALIGNMENT_MASK )` 來設定，就能確保 `heapSTRUCT_SIZE` 一定是 8 的倍數，且會是 >= `sizeof(BlockLink_t)` 舉例來說，假設某台電腦 `sizeof(BlockLink_t)` 得到4 (`100`)，那 `(100 + 111) & ~(0000 0000 0000 0111)` = `(100 + 111) & (1111 1111 1111 1000)` = `1000`，也就是 8 假設另一台電腦 `sizeof(BlockLink_t)` 得到 12 (`1100`)，那 `(1100 + 111) & (1111 1111 1111 1000)` = `10000`，也就是 16 ::: ![block_link](https://hackmd.io/_uploads/SyH-jgzEp.png) 所以可以看到這個list大概會是長這樣，而且++紀錄free memory block的 `BlockLink_t` 會依據block size在list中由小排到大++(在 `prvInsertBlockIntoFreeList` 可看到相關的code)，所以 `xStart` 會指向最小的free memory block的 `BlockLink_t`，而最後一個free memory block會指向 `xEnd` 。 ```cpp static void prvHeapInit( void ) { BlockLink_t *pxFirstFreeBlock; uint8_t *pucAlignedHeap; /* Ensure the heap starts on a correctly aligned boundary. */ pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) ); /* 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; /* xEnd is used to mark the end of the list of free blocks. */ xEnd.xBlockSize = configADJUSTED_HEAP_SIZE; xEnd.pxNextFreeBlock = NULL; /* To start with there is a single free block that is sized to take up the entire heap space. */ pxFirstFreeBlock = ( void * ) pucAlignedHeap; pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE; pxFirstFreeBlock->pxNextFreeBlock = &xEnd; } ``` 接下來，`prvHeapInit` 這個 function 是初始化 Heap 用的，當 `pvPortMalloc` ++第一次++被呼叫時，就會呼叫 `prvHeapInit` 此 function 來初始化 Heap，這個 function 我把他分成三個部分來說明： :::info ```cpp uint8_t *pucAlignedHeap; pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) ); ``` 這個東西看起來很複雜，他主要是要把Heap的起始位址依據 `portBYTE_ALIGNMENT` 做對齊： - `portBYTE_ALIGNMENT` 被定義在 `portmacro.h`，被定義成 `8`，所以想把Heap的起始位址設定成8的倍數 - `portPOINTER_SIZE_TYPE` 被定義在 `FreeRTOS.h`，被定義成 `uint32_t` - `ucHeap` 定義在 `heap_2.c`，是 **`uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];`** - `configTOTAL_HEAP_SIZE` 被定義在 `FreeRTOSConfig.h`，在這次的lab被助教定義成 `( ( size_t ) ( 5 * 1024 ) )` - 所以 `ucHeap` 是unsinged char的data type的array，每個element大小都是8 bit (1 byte)，數量是 `5 * 1024`，也就是我們Heap的大小，所以我們Heap的大小是 5 kbyte - `portBYTE_ALIGNMENT_MASK` 被定義在 `portable.h`，是 `0x0007`，也就是 `0000 0000 0000 0111` - 所以 `~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK )` 就會得到 `1111 1111 1111 1000`，那其他的數字去跟這個值做 `&` 一定都會變成是8的倍數，因為最右邊的3個bit都會變成0，而其他的bit都會保留成原本的bit - `&ucHeap[ portBYTE_ALIGNMENT ]`，也就是 `&ucHeap[8]`。那為什麼是要取`ucHeap[8]` 的address出來做對齊？為什麼不是用 `ucHeap[0]`, `ucHeap[5]`... 或其他的address？ - 首先，我們的heap的address會從 `ucHeap[0]` 開始，那由於data type是`uint8_t`，一個element只會佔用8 bit，也就是1 byte，所以可以知道 `ucHeap[0]` 和 `ucHeap[1]` 的address只會差1，像是`ucHeap[5]` 的address就是`ucHeap[0]` 的address + 5，所以 `ucHeap[n]` 的address就是 `ucHeap[0]`的address + `n` - 由於我們要讓位址跟8的倍數做對齊，再加上我們不知道 `ucHeap[0]` 的位址會是多少，++但我們可以確定的是 `ucHeap[0]` 的address + 8，也就是在 `ucHeap[0]` ~ `ucHeap[8]` 之間的address，一定會有一個address是 8 的倍數++。 - 譬如說，假如本來是13，那13 + 8 = 21 (`10101`)，那`10101 & 1111 1111 1111 1000` 就會得到 `10000`，也就是16 - 所以這裡才會用 `ucHeap[8]` 的address去跟 `1111 1111 1111 1000` 做 `&` ，這樣就能保證能得到一個8的倍數的address，且此address是在`ucHeap[0]` ~ `ucHeap[8]` 之間 - 這個對齊8的倍數的address就會是 `pucAlignedHeap` 的value - 從這裡可以看到為了對齊記憶體位址會lost一些byte，像前面13的例子，為了對齊8的倍數，就會用16當作起始位址，那就會失去16-13=3個bytes - 但在 `heap_2.c` 有定義 `#define configADJUSTED_HEAP_SIZE ( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )`，直接把 `configADJUSTED_HEAP_SIZE` 當作真正可使用的記憶體空間，也就是直接lost `portBYTE_ALIGNMENT` 個空間  ::: :::info ```cpp xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap; xStart.xBlockSize = ( size_t ) 0; xEnd.xBlockSize = configADJUSTED_HEAP_SIZE; xEnd.pxNextFreeBlock = NULL; ``` 再來是初始化 `xStart` 和 `xEnd`： - `xStart` - `pxNextFreeBlock` 被設定為經由對齊後的Heap的起始位址 - `xBlockSize` 被設定為0 - `xEnd` - `xBlockSize` 被設定成 `configADJUSTED_HEAP_SIZE`，這樣 `xEnd` 的size就會是全部list中最大的 - `pxNextFreeBlock` 被設定為 `NULL` ::: :::info ```cpp BlockLink_t *pxFirstFreeBlock; pxFirstFreeBlock = ( void * ) pucAlignedHeap; pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE; pxFirstFreeBlock->pxNextFreeBlock = &xEnd; ``` 這裡在設定第一個free memory block - 可以看到第一個free memory block是從heap的對齊後的起始位址開始存放 - `xBlockSize` 就是目前Heap可以用的空間，也就是 `configADJUSTED_HEAP_SIZE` - `pxNextFreeBlock` 指向 `xEnd` 所以在這裡可以看到，假如有一塊free memory block，那++紀錄這個free memory block的 `BlockLink_t` 就是放在這個free meory block的起始位址++，++我們只要去取該`BlockLink_t` 的address，就可以知道這個free memory block的起始位址(start address)是多少++ 所以++每塊free memory block，在起始位址的地方都會用掉 `heapSTRUCT_SIZE` 的空間來存放 `BlockLink_t`，也就是用8 bytes的空間來存放++ 那每一個 `BlockLink_t` 的 `xBlockSize` 會紀錄這塊free memory block有多大，那只要start address + `xBlockSize` 就可以得到這塊free memory block的end address ::: ![heap](https://hackmd.io/_uploads/ryEFL5XV6.png) 所以Heap剛被初始化完畢的話，大概就如上面這張示意圖所示 - 一開始要求的Heap大小是 `configTOTAL_HEAP_SIZE` bytes，但為了要讓Heap的位址對齊，會失去一些byte，所以剩下可用的Heap空間就是 `configADJUSTED_HEAP_SIZE` - `pucAlignedHeap` 會指向對齊後的記憶體的起始位址，在這個地方會用8 bytes儲存第一個 `BlockLink_t`，他的 `xBlockSize` 就是目前整個可用的Heap空間，也就是 `configADJUSTED_HEAP_SIZE` - `xStart` 的 `pxNextFreeBlock` 會指向這一個 `BlockLink_t` 所在的位址，也就是 `pucAlignedHeap` - 這個 `BlockLink_t` 的`pxNextFreeBlock` 會指向 `xEnd` ```cpp=94 /* * Insert a block into the list of free blocks - which is ordered by size of * the block. Small blocks at the start of the list and large blocks at the end * of the list. */ #define prvInsertBlockIntoFreeList( pxBlockToInsert ) \ { \ BlockLink_t *pxIterator; \ size_t xBlockSize; \ \ 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; \ } /*-----------------------------------------------------------*/ ``` 這個macro的功能是，當有一個新的free memory block要被加入list時，由於list中的free memory block會依據block size由小排到大，所以這裡就是要依據block size找到最適合的位子，把新的block插入。從第108行到第116行，就是在尋找最適合的位子，把新的block插入list中。 ```cpp= void *pvPortMalloc( size_t xWantedSize ) { BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink; static BaseType_t xHeapHasBeenInitialised = pdFALSE; 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( 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; } ``` 這一個function是要拿來allocate記憶體用的，當一個task要被create時就會呼叫他。此function可以分成幾個部分來看 :::info ```cpp=9 /* 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; } ``` - 如果是第一次呼叫 `pvPortMalloc` 這個function的話，他就會去呼叫 `prvHeapInit` 將Heap初始化。 - `xHeapHasBeenInitialised` 被宣告為 `static` 型態的變數，所以這個變數可以用來紀錄Heap有沒有被初始化過了 ::: :::info ```cpp=17 /* 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 ) ); } } ``` - `xWantedSize` 是我們要多少byte的記憶體空間 - [`xTaskCreate`](https://www.freertos.org/a00125.html) 的第三個參數，`configSTACK_DEPTH_TYPE usStackDepth`，就是指說對於這個task，我要分配多大的stack給這個task，可以在官方的網站看到 `usStackDepth` 的單位是word - `usStackDepth`: The number of words (not bytes!) to allocate for use as the task's stack - 在 `task.c` 的 `xTaskCreate` 可以看到這一段程式碼：<br>`pxStack = pvPortMalloc( ( ( ( size_t ) usStackDepth ) * sizeof( StackType_t ) ) );` - `StackType_t` 被定義在 `FreeRTOS/portable/ARM_CM4F/portmacro.h` ，是 `uint32_t`，所以32 bit - 所以 `xTaskCreate` 的第三個參數 * 4，就是我們想要分配多少byte給這個task的stack，也就是 `xWantedSize` - 把 `xWantedSize` 加上 `heapSTRUCT_SIZE`，才能確保我們接下來找到的free memory block的空間可以涵蓋我們想要分配的空間&能涵蓋 `BlockLink_t` 的空間 - `if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0 )` - 這段是在判斷 `xWantedSize` 是不是8的倍數 - `portBYTE_ALIGNMENT_MASK` 是 `0000 0000 0000 0111`，如果`xWantedSize`是8的倍數的話，最右邊的3個bit一定都是0，所以跟那個Mask做`&`的話一定會得到0 - 如果不是8的倍數的話就加上一些byte，讓 `xWantedSize` 變成8的倍數，也就是加上 `( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) )` ::: :::info ```cpp /* 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; } ``` - 由於紀錄free memory block的list會依據每個free memory block的大小由小排到大，所以這裡主要就是要找到第一個 >= `xWantedSize` 的free memory block - `pxBlock` 會指向該free memory block，或如果沒找到的話，就指向 `xEnd` ::: :::info ```cpp= /* 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; } ``` 若 `pxBlock` 有找到所需空間的free meory block，就做以下的事情： - `pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );` - 由於這塊free memory block的前8個byte是放 `BlockLink_t` 的地方，所以 `pvReturn` 應該是要指向此free memory block起始位址 + 8的位址 - `pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;` - 把前一個free memory block的 `BlockLink_t` 的`pxNextFreeBlock`指向下下一個free memory block - `if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )` - `heapMINIMUM_BLOCK_SIZE` 被定義在 `heap_2.c`，是 `( ( size_t ) ( heapSTRUCT_SIZE * 2 ) )` - 也就是如果這個free memory block的size減掉 `xWantedSize` 後的空間，若大於 `heapMINIMUM_BLOCK_SIZE` ，就把這塊free memory block的空間做切割，讓多餘的空間可以拿去給其他task使用 - 後面幾段就是設定新的free memory block的起始位址，以及他的block size，並使用 `prvInsertBlockIntoFreeList` 將其插入free memory block list當中~ ::: :::warning ```cpp=75 traceMALLOC( pvReturn, xWantedSize ); ``` 第75行的這個macro，只有在 `FreeRTOS.h` 找到他的declaration，但都找不到他的definition，不知道他是要做什麼＠＿＠ ::: ![heap](https://hackmd.io/_uploads/B1qkws7E6.png) 可以看到當有一個Task被created了，我們希望這個Task的stack的大小是 `WantedSize` 大小，但還會被加上 `heapSTRUCT_SIZE`(圖中橘色的區塊)，所以實際分配到的記憶體空間是 `WantedSize` + `heapSTRUCT_SIZE`，也就是`BlockSize`。這們做的用意是為了保留原本紀錄這塊free memory block的 `BlockLink_t`。然後由於可用的free memory block減掉 `BlockSize` 大於 `heapMINIMUM_BLOCK_SIZE` ，所以就把剩餘不會用到的記憶體空間再用一個 `BlockLink_t` 去記錄他。 ![heap](https://hackmd.io/_uploads/BkFp5jXNp.png) 再來，由於我們用的開發板的processor是full descending stack，也就是在stack裡面放東西的話是會從記憶體位址大往記憶體位址小的地方存東西進去stack，TCB的 `pxTopOfStack` 會指向上次push到哪裡的位址，所以 `pxTopOfStack` 指向的位址是有存東西的，當要push新的東西進去，`pxTopOfStack` 會先 `- 1`，然後才放東西進去。在 `portmacro.h` 可以看到 `portSTACK_GROWTH` 被定義成 `-1`，這就代表full descending stack。在 `tasks.c` 的 `xTaskCreate` 的程式碼可以看到，若 `portSTACK_GROWTH` 小於0的話，會先執行 `pxStack = pvPortMalloc( ( ( ( size_t ) usStackDepth ) * sizeof( StackType_t ) ) )`，之後才執行 `pxNewTCB = ( TCB_t * ) pvPortMalloc( sizeof( TCB_t ) );`，也就是先分配stack的記憶體空間，之後才分配TCB的記憶體空間，這麼做的用意是為了避免stack長到TCB。所以上一張圖先分配了stack需要的記憶體空間，這張圖就是分配TCB所需的記憶體空間。同樣地，在起始位址會用8 bytes存放剛剛的 `BlockLink_t`，之後才是TCB所需的記憶體大小。 :::info ![image](https://hackmd.io/_uploads/SkPkOaJE6.png) ```cpp! int main() { xTaskCreate(red_LED_task, "RED_LED", 100, NULL, 0, NULL); xTaskCreate(task1, "TASK1", 50, NULL, 0, NULL); xTaskCreate(task2, "TASK2", 30, NULL, 0, NULL); xTaskCreate(green_LED_task, "GREEN_LED", 130, NULL, 0, NULL); xTaskCreate(task3, "TASK3", 40, NULL, 0, NULL); xTaskCreate(print_task, "PRINT", 130, NULL, 0, NULL); vTaskStartScheduler(); } ``` 前面的輸出的結果，再加上 `main()` 的程式碼就可以看到，對於每個task，都是先分配他的stack所需要的記憶體空間，且 `xTaskCreate` 的第三個參數乘以4就會是 `WantedSize`，然後 `WantedSize` 再加上 `heapSTRUCT_SIZE` 就會是 `BlockSize` 然後每個task都會再allocate一個 `WantedSize` 是 `88` 的記憶體空間，這就是TCB所佔的空間。同樣地，也會再加上 `heapSTRUCT_SIZE` 以保留原本紀錄該free memory block的 `BlockLink_t`。最後可以看到，對於每個task，都是先allocate他的stack所需的記憶體空間，之後才allocate TCB所需的記憶體空間。 ::: ```cpp 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 -= heapSTRUCT_SIZE; /* This unexpected casting is to keep some compilers from issuing byte alignment warnings. */ pxLink = ( void * ) puc; vTaskSuspendAll(); { /* Add this block to the list of free blocks. */ prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) ); xFreeBytesRemaining += pxLink->xBlockSize; traceFREE( pv, pxLink->xBlockSize ); } ( void ) xTaskResumeAll(); } } ``` 這是當有一塊記憶體空間被釋放時所呼叫的function - `puc -= heapSTRUCT_SIZE;` - 減掉 `heapSTRUCT_SIZE` 才能讓 `puc` 指向紀錄這塊memory block的 `BlockLink_t` - 之後再用 `prvInsertBlockIntoFreeList` 把這個被釋放的memory block的 `BlockLink_T` 加入free memory block list ![EmbeddedOS](https://hackmd.io/_uploads/Sk2l-h74p.png) 所以當某個task被deleted，他的stack和TCB所用的記憶體空間就會被釋放，那原本紀錄那些記憶體區塊有多大的 `BlockLink_t` 就會被加入list當中，並且會依據block size由小串到大。 ## Part 1 所以從前面的理解~大概可以知道要怎麼實作 `vPrintFreeList` 了，就從 `xStart` 開始iterate，直到 `xEnd` 為止，然後把這中間經過的block的資訊都印出來即可~就只是很簡單的linked list的問題，以下是我的code~ ```cpp= void vPadding(char str [], int padNum) { for (int i = 0; i < padNum; ++i) { strcat(str, " "); } } void vPrintFreeList(void) { char msg [100]; memset(msg, '\0', sizeof(msg)); sprintf(msg, "StartAddress heapSTRUCT_SIZE xBlockSize EndAddress\n\r"); HAL_UART_Transmit(&huart2, (uint8_t *) msg, strlen(msg), 0xffff); BlockLink_t *curNode = xStart.pxNextFreeBlock; while ( (void *) curNode != (void *) &(xEnd) ) { memset(msg, '\0', sizeof(msg)); char startAddr [20]; memset(startAddr, '\0', sizeof(startAddr)); itoa((size_t) curNode, startAddr, 16); strcat(msg, "0x"); strcat(msg, startAddr); vPadding(msg, 9); char heapStructSize [5]; memset(heapStructSize, '\0', sizeof(heapStructSize)); itoa((uint16_t) heapSTRUCT_SIZE, heapStructSize, 10); strcat(msg, heapStructSize); vPadding(msg, 10); char blockSize [10]; memset(blockSize, '\0', sizeof(blockSize)); itoa((size_t) curNode->xBlockSize, blockSize, 10); char tmp [10]; memset(tmp, '\0', sizeof(tmp)); vPadding(tmp, 5 - strlen(blockSize)); strcat(tmp, blockSize); strcat(msg, tmp); vPadding(msg, 5); char endAddr [20]; memset(endAddr, '\0', sizeof(endAddr)); itoa((size_t) curNode + curNode->xBlockSize, endAddr, 16); strcat(msg, "0x"); strcat(msg, endAddr); strcat(msg, "\n\r"); HAL_UART_Transmit(&huart2, (uint8_t *) msg, strlen(msg), 0xffff); curNode = curNode->pxNextFreeBlock; } memset(msg, '\0', sizeof(msg)); sprintf(msg, "configADJUSTED_HEAP_SIZE: %d xFreeBytesRemaining: %d\n\r", configADJUSTED_HEAP_SIZE, xFreeBytesRemaining); HAL_UART_Transmit(&huart2, (uint8_t *) msg, strlen(msg), 0xffff); } ``` 結果如下： ![ezgif-4-48e35e5a0a](https://hackmd.io/_uploads/SkM-BogV6.gif)  ![image](https://hackmd.io/_uploads/Hk2m8yYi6.png) 從輸出的結果可以看到，有好幾塊free memory block都是相鄰的，我把相鄰的都用同顏色標示。若有做merge的話，應該是只會顯示三塊free memory block。另外也可以看到block size `128`、`168`、和 `208` 是 `task1`、`task2`、`task3` 實際被分配到的block size，而另外三個block size為 `96` 的free memory block就是原本被用來存放這三個task的TCB的空間。 ## Part 2 接下來就是改寫 `prvInsertBlockIntoFreeList` 這個macro讓他會將相鄰的free memory block做合併。首先來考慮什麼情況會需要做merge~ ![merge](https://hackmd.io/_uploads/SJFxAZMEp.png) - 綠色的block是新block，準備要被插入list中；橘色和藍色的block則是本來就在list中的block ![merge](https://hackmd.io/_uploads/S1hwsverT.png) - 第一種情況，發生在橘色跟綠色的block - 也就是橘色block的end address等於綠色block的start address - 這樣我們就知道綠色的block是緊鄰在橘色block的後面 - 第二種情況，發生在藍色跟綠色的block - 也就是綠色block的end address等於藍色block的start address - 這樣我們就知道藍色block是緊鄰在綠色block的後面知道什麼情況會相鄰後，再來就討論怎麼做merge： - 我的想法是先取得要插入的新的block的start address和end address - 再來，walk through free memory block list的每個 `BlockLink_t` - 對於每個block，找出他的start address和end address，檢查是否有相鄰，若有相鄰： - 若是前面討論的第一種情況： - 直接把指向綠色block的pointer指向橘色block - 將橘色block的block size加上綠色block的block size - 將橘色block從list中移除 - 若是第二種情況： - 直接把綠色block的block size加上藍色block的block size - 把藍色block從list中移除 - 最後，由於list中的 `BlockLink_t` 會依據block size由小排到大，所以可以直接利用原本macro最後的code，找出最適合的位址將此 `BlockLink_t` 插入以下是我的code~ ```cpp= #define prvInsertBlockIntoFreeList( pxBlockToInsert ) \ { \ /* pxIterator是原本macro就有寫的，後面會用到 */ /* pxBlockPtr用來指向 pxBlockToInsert，後面會說明為什麼要另外一個pointer來用 */ BlockLink_t *pxIterator, *pxBlockPtr = pxBlockToInsert; \ size_t xBlockSize = pxBlockPtr->xBlockSize; \ \ /* 新的block的start address */ size_t xStartAddress = (size_t) pxBlockPtr; \ /* 新的block的end address */ size_t xEndAddress = (xStartAddress + xBlockSize); \ \ BlockLink_t *pxPrevBlock = &(xStart); \ BlockLink_t *pxCurBlock = xStart.pxNextFreeBlock; \ \ while ((void *) pxCurBlock != (void *) &(xEnd)) { \ \ /* 目前指向的list的Block的start address */ size_t xCurBlockStartAddr = (size_t) pxCurBlock; \ /* 目前指向的list的Block的block size */ size_t xCurBlockSize = pxCurBlock->xBlockSize; \ /* 目前指向的list的Block的end address */ size_t xCurBlockEndAddr = (xCurBlockStartAddr + xCurBlockSize); \ \ /* 若都沒有相鄰的狀況，那就指向list的下一個block */ if (xStartAddress != xCurBlockEndAddr && xEndAddress != xCurBlockStartAddr) { \ pxPrevBlock = pxCurBlock; \ pxCurBlock = pxCurBlock->pxNextFreeBlock; \ continue; \ } \ \ /* 沒有相鄰的情況在前面就已經被處理掉 */ /* 下面就是處理有相鄰的狀況 */ /* 有相鄰的話可以分成兩種狀況 */ /* 一種是新插入的Block在前面，目前指向的block在後面 */ /* 另一種狀況則是目前指向的block在前面，新插入的block在後面 */ /* 目前指向的block在前面，新插入的block在後面 */ if (xStartAddress == xCurBlockEndAddr) { \ /* pxBlockPtr改成指向目前的這個block */ pxBlockPtr = pxCurBlock; \ /* 目前list中的這個block的size必須要加上新插入的block的block size */ pxBlockPtr->xBlockSize += xBlockSize; \ } \ /* 新插入的Block在前面，目前指向的block在後面 */ else if (xEndAddress == xCurBlockStartAddr) { \ /* 新插入的block的block size加上目前指向的block的block size */ pxBlockPtr->xBlockSize += xCurBlockSize; \ } \ /* 前一個block的next pointer指向目前這個block的下一個block */ pxPrevBlock->pxNextFreeBlock = pxCurBlock->pxNextFreeBlock; \ /* 換到下一個block */ pxCurBlock = pxCurBlock->pxNextFreeBlock; \ \ } \ \ /* block size可能有更新過，再重新assign一次 */ xBlockSize = pxBlockPtr->xBlockSize; \ /* 以下的程式碼會直接找到適合插入此block的位子 */ /* 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. */ \ pxBlockPtr->pxNextFreeBlock = pxIterator->pxNextFreeBlock; \ pxIterator->pxNextFreeBlock = pxBlockPtr; \ } ``` Output結果如下： ![ezgif-4-aaf414cb50](https://hackmd.io/_uploads/S1QWBf-E6.gif) ![image](https://hackmd.io/_uploads/BkWIUJFoT.png)  可以印出正確的執行結果~ ## 為何另外宣告 `pxBlockPtr` 我本來在macro裡面都是用 `pxBlockToInsert` 去操作，而沒有另外宣告 `pxBlockPtr` 來使用，結果編譯時就出現以下錯誤訊息： ![image](https://hackmd.io/_uploads/ryvIdlZNp.png) 問題是出在前面程式碼第41行這段 `pxBlockToInsert = pxCurBlock;`，錯誤訊息是 `error: lvalue required as left operand of assignment` ，我整個不能理解@@ 奇怪，`pxBlockToInsert` 不是pointer嗎？我把另一個pointer的value assign給這個pointer，而且這兩個pointer都指向相同的data type，我只是讓這兩個pointer都指向同一個物件呀~照理說應該不會有問題＠＿＠我這邊卡了好久不知道到底是出了什麼問題，也不知道我的觀念到底是哪裡出錯Q_Q 之後去查其他function都怎麼使用這個macro，結果看到以下這個function： ```cpp= 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 -= heapSTRUCT_SIZE; /* This unexpected casting is to keep some compilers from issuing byte alignment warnings. */ pxLink = ( void * ) puc; vTaskSuspendAll(); { /* Add this block to the list of free blocks. */ prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) ); xFreeBytesRemaining += pxLink->xBlockSize; traceFREE( pv, pxLink->xBlockSize ); } ( void ) xTaskResumeAll(); } } ``` 第19行，`prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );` 才知道問題出在哪裡。因為macro只是preprocessor會幫忙替換設定好的程式碼，所以第19行，傳入的參數是 `( ( BlockLink_t * ) pxLink )` ，這就代表 `pxBlockToInsert` 等於 `( ( BlockLink_t * ) pxLink )` ，也就是macro中只要有出現 `pxBlockToInsert` 的地方，就會被替換成 `( ( BlockLink_t * ) pxLink )`。所以前面那段code，`pxBlockToInsert = pxCurBlock;` 就會被替換成： ```cpp ( ( BlockLink_t * ) pxLink ) = pxCurBlock; ``` 而問題就出在 `( ( BlockLink_t * ) pxLink )` 是一個rvalue，我們不能assign東西給rvalue，所以才會有這個error message。而我的解決方法就是宣告另一個pointer `pxBlockPtr`，並把 `( ( BlockLink_t * ) pxLink )` 的value assign給 `pxBlockPtr`。 :::danger 所以之後看到別人定義好的macro，在使用他之前，最好要先看一下別人都怎麼使用它，這樣才比較保險Q_Q ::: ## Merge with xStart/xEnd? ![block_link](https://hackmd.io/_uploads/SyH-jgzEp.png) 前面在做merge的時候有在疑惑說有沒有可能會發生跟 `xStart` 或 `xEnd` 做 merge，但回去看程式碼才想到 `xStart` 跟 `xEnd` 是被宣告為 global variable ，那 global variable 會被存放在 Data section，不是放在 Stack，所以不會有這狀況發生

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.