2021 嵌入式作業系統分析與實做 Final Project report
===
[Final Project](https://docs.google.com/presentation/d/1Hc4OrKeXWsm3mj0J5Nqb_QVsQJC0JkKPwPZ9Vp1pK-k/edit#slide=id.gddffb63a37_0_26)
contribute by `N26081157 廖振凱
` `N26091877 羅子渝`
###### tags: `FreeRTOS`

### 目標
因為我們認為FreeRTOS在不支援Memory protection unit的情況下，雖然OS本身依舊有提供software detection的方式來檢測是否發生stack overflow。但是效果有改善的空間，因此我們希望透過了解其他RTOS是如何用software的方式來偵測stack overflow，並且移植到FreeRTOS上。因為我們使用的處理器是[STM32F407VG](https://www.st.com/en/microcontrollers-microprocessors/stm32f407vg.html)本身有MPU，所以我們也在最後會嘗試使用hardware的方式來做stack overflow的偵測。

### 常見的RTOS中software stack overflow detection的方式
#### Mynewt OS stack overflow detection
> Mynewt OS ==fills the stack of a task with a pattern== at the time task gets created. If you’re suspecting that stack might be blown, check the start of the stack during Context Switch.
You can ask OS to check the top of the stack on every context switch. It’ll walk over X number of os_stack_t elements, checking if our pattern is still there for the task which is about to be switched out.

#### chibi OS
>The debug option **CH_DBG_ENABLE_STACK_CHECK** enables checks on stack overflow conditions. The most common implementation is to ==check the stack position== when a context switch is about to be performed, if the calculated new stack position overflows the stack limit then the system is halted.

#### ecos
>The kernel does contain some code to help detect stack overflows, controlled by the configuration option **CYGFUN_KERNEL_THREADS_STACK_CHECKING**: a small amount of space is reserved at the stack limit and ==filled with a special signature==; every time a thread context switch occurs this signature is checked, and if invalid that is a good indication (but not absolute proof) that a stack overflow has occurred. This form of stack checking is enabled by default when the system is built with debugging enabled.

#### RT-Thread
>The debug option **RT_USING_OVERFLOW_CHECK** enables checks on stack overflow conditions. The implementation of the detection dependents on the direction of stack growth, so need to check wether the macro **ARCH_CPU_STACK_GROWS_UPWARD** be defined. if the macro be defined then ==determine whether the tail symbol of stack is `#`== ,else determine whether the head symbol of stack is `#`.

#### Threadx
>ThreadX ==places a 0xEF data pattern== throughout each thread’s stack. The idea here is to run the thread through its validation tests and then review all of the thread stacks. The non-0xEF byte closest to the start of the stack represents the high-water mark of that thread’s stack usage. Of course, if there are no remaining 0xEF data patterns in a thread’s stack, there is a high-probability that a stack overflow has occurred. The following figure shows an example thread stack with the 0xEF data pattern:

#### ucos-III
>There is a ==StkLimitPtr== member in TCB.Assume that before switching to task S, the code will check whether the value of the stack pointer to be loaded into the CPU exceeds the StkLimitPtr limit in the TCB of the task S. Because the software cannot react quickly when overflowing, the value of StkLimitPtr should be set as far away as possible from &MyTaskStk[0] to ensure that there is enough overflow buffer, usually set StkLimitPtr to point to 90% of the task stack size, and then get the task stack usage. If the stack usage rate is greater than 90%, a warning must be given !

#### Zephyr
>If a platform lacks memory management hardware support, **CONFIG_STACK_SENTINEL** is a software-only stack overflow detection feature which periodically checks if a ==sentinel value== at the end of the stack buffer has been corrupted.

---
### stack overfllow detcetion實現
綜觀上述RTOS若是用software的方式來檢測stacl overflow不外乎就是檢查pointer的位址是否在合法的範圍，以及最後幾個位址的內容有沒有被修改調。

#### vApplicationStackOverflowHook
這個hook function是被我們定義在`main.c`中，在檢測到stack overflow時會被呼叫。此 function提供了目前是那一個task發生了stack overflow。

void vApplicationStackOverflowHook( TaskHandle_t xTask, char *pcTaskName )
{

	while (1)
	{
		printf("%s is stack overflow\r\n", pcTaskName);
		vTaskDelay(500);
	}
}

#### Realize Mynewt OS stack overflow detection on FreeRTOS
因為`configCHEXK_FOR_STACK_OVERFLOW == 3`，所以在產生task的時候會在stack裡面填入預設值。所以我們可以透過直接檢查最後一個`word`還是不是原來的值來判斷
，有沒有產生`stack overflow`。

#if( ( configCHECK_FOR_STACK_OVERFLOW == 3 ) && ( portSTACK_GROWTH < 0 ) )

	#define taskCHECK_FOR_STACK_OVERFLOW()																								\
	{																																	\
		const uint32_t * const pulStack = ( uint32_t * ) (pxCurrentTCB->pxStack);														\
		const uint32_t ulCheckValue = ( uint32_t ) 0xa5a5a5a5;												\
		if( pulStack[0] != ulCheckValue )															\
		{						\
			printf("configCHECK_FOR_STACK_OVERFLOW = %d\r\n", configCHECK_FOR_STACK_OVERFLOW);				\
			vApplicationStackOverflowHook( ( TaskHandle_t ) pxCurrentTCB, pxCurrentTCB->pcTaskName );	\
		}																								\
	}

#endif /* #if( configCHECK_FOR_STACK_OVERFLOW == 3 ) */

#### Realize ucos-III stack overflow detection on FreeRTOS
透過新增一個成員(`ucosIII`)在`TCB_t`中，用來記錄stack中最後10%的位址，所以我們在xTaskCreate中

		#if( ( portSTACK_GROWTH < 0 ) )
			pxNewTCB->ucosIII =(StackType_t )((pxNewTCB->pxTopOfStack - pxNewTCB->pxStack)*0.1) + pxNewTCB->pxStack;
		#else
			pxNewTCB->ucosIII =pxNewTCB->pxEndOfStack - (StackType_t )((pxNewTCB->pxEndOfStack - pxNewTCB->pxTopOfStack)*0.1);
		#endif

* 第1行：根據不同的stack生長方向`ucosIII`的方向也會有所調整
* 第2行：透過`pxNewTCB->pxTopOfStack`、`pxNewTCB->pxStack`，可以知道這個task總共有多少stack可以使用，計算完之後在將這個最後10%的位址存入`pxNewTCB->ucosIII`。

透過`pxNewTCB->ucosIII`我們可以方便的用來做stack overflow的檢查

#if( ( configCHECK_FOR_STACK_OVERFLOW == 4 ) && ( portSTACK_GROWTH < 0 ) )

	/* Only the current stack state is to be checked. */
	#define taskCHECK_FOR_STACK_OVERFLOW()																\
	{																									\
		/* Is the currently saved stack pointer within the stack limit? */								\
		if( pxCurrentTCB->pxTopOfStack <= pxCurrentTCB->ucosIII )										\
		{																								\
			printf("configCHECK_FOR_STACK_OVERFLOW = %d\r\n", configCHECK_FOR_STACK_OVERFLOW);			\
			vApplicationStackOverflowHook( ( TaskHandle_t ) pxCurrentTCB, pxCurrentTCB->pcTaskName );	\
		}																								\
	}

#endif /* configCHECK_FOR_STACK_OVERFLOW == 4 */

#### Combine the concepts of the above methods
觀察以上的偵測方式可以發現，若是只檢查最後一個`word`的內容有可能偵測錯誤，但若是保留最後的10%，那這樣stack就不能充分地被利用。我們認為同一個task在同一個長度的時間片段中，會使用到的stack容量應該會是差不多的。所以context switch到底要檢查幾個word應該根據不同task使用stack的情況來做動態的調整。
我們在TCB_t 中新增了一個成員`pxTopOfStack_prev`用來方便我們計算本次時間片段中這個task使用了多少的stack空間，它會在每次做stack檢查的最後被修改。

#if( ( configCHECK_FOR_STACK_OVERFLOW == 5 ) && ( portSTACK_GROWTH < 0 ) )

	#define taskCHECK_FOR_STACK_OVERFLOW()																		\
	{																											\
		const uint32_t * const pulStack = ( uint32_t * ) pxCurrentTCB->pxStack;									\
		const uint32_t ulCheckValue = ( uint32_t ) 0xa5a5a5a5;													\
		int	delta_of_stack = pxCurrentTCB->pxTopOfStack_prev - pxCurrentTCB->pxTopOfStack;       				\
		if(delta_of_stack > 1)																					\
		{								\
		    if( pulStack[ 0 ] != ulCheckValue || pxCurrentTCB->pxTopOfStack <= pxCurrentTCB->pxStack + delta_of_stack )																\
		    {																								\
			    printf("configCHECK_FOR_STACK_OVERFLOW = %d\r\n", configCHECK_FOR_STACK_OVERFLOW);			\
			    vApplicationStackOverflowHook( ( TaskHandle_t ) pxCurrentTCB, pxCurrentTCB->pcTaskName );	\
		    }																								\								
		}																										\
		else																									\
		{																										\
		    if(pulStack[ 0 ] != ulCheckValue)																	\
		    {																									\
			    printf("configCHECK_FOR_STACK_OVERFLOW = %d\r\n", configCHECK_FOR_STACK_OVERFLOW);				\
			    vApplicationStackOverflowHook( ( TaskHandle_t ) pxCurrentTCB, pxCurrentTCB->pcTaskName );		\
		    }																									\
		}																										\
		pxCurrentTCB->pxTopOfStack_prev  = pxCurrentTCB->pxTopOfStack;											\
	}

#endif /* #if( configCHECK_FOR_STACK_OVERFLOW == 5 ) */

* 第7行：在本次時間片段中使用stack的情況可以根據`pxCurrentTCB->pxTopOfStack`來了解，而`pxCurrentTCB->pxTopOfStack_prev`存放了上次stack的使用情況，透過這兩個變數相減，就可以計算出本次時間片段中使用了多少的stack。
* 第8行：因為`delta_of_stack`的值是pointer的差值。pointer to StackType_t的大小是4個byte，所以如果pointer數相差1個以下就只需要檢查一個word即可。
* 第27行：將`pxCurrentTCB->pxTopOfStack_prev`的內容改為`pxCurrentTCB->pxTopOfStack`，以便下一次使用。

* 透過以下的圖可以發現


依上圖所示，若是每次stack增加的很多，就會在底部保留較多的空間，用以預防stack overflow，也確保下次如果寫入這跟這次一樣的資料量時。由足夠的空間可以放。若是每次增加的stack空間不多，此方法也可以確保stack能被徹底使用。

### 比較不同的stack overflow detection對context switch的影響
由於採用不同的stack overflow對context switch的影響是不一樣的，為了量化他們之間的差距，我們設計了以下的實驗
**建立兩個 task**

void Task1(void) {
	for(;;) {
		iii++;
	}
}
void Task2(void) {
	 TickType_t xLastWakeTime;
	 const TickType_t xFrequency = 1000;
	 xLastWakeTime = xTaskGetTickCount();
	for(;;) {
		vTaskDelayUntil( &xLastWakeTime, xFrequency );
	    array[arr_index++] = iii;
	    iii = 0;
	}
}

其中Task2的priority較Task1高。
Task1不斷的對`iii`加1，而Task2會在固定的時間被執行並將`iii`記錄到全域變數`array`中。這樣我們就可以透過`array`內的數值來計算，Task2被block的這段期間，Task1到底做了多少的加法運算。
**實現結果**
我們可以清楚的看到使用`configCHECK_FOR_STACK_OVERFLOW 1`的檢查方式，Task1的加法運算少了四次，所以可以推斷`context switch`所花的時間應該較原先的多了4個加法運算。

### FreeRTOS-MPU
#### portmacro.h
要使用MPU的API，首先需要將原本所include 的portmacro.h 改成有支援MPU的portmacre.h
也就是將原本所include的資料夾ARM_CM4F改成ARM_CM4_MPU，其中portmacro.h便會將是否使用MPU的config設為1
#### mpu_wrapper.c
欲使用mpu的API便會需要mpu_wrapper.c，裡面實作了有關MPU API 的function
此檔案位於FreeRTOS/Source/portable/Common底下，必須將此檔案加在Source Directory下
#### STM32F407VGTX_FLASH.ld
此檔案定義了一些extern的變數，我想應該是因為MPU是一塊硬體，必須設定一些參數。
以下是我的設置

_Privileged_Functions_Region_Size = 16K;
_Privileged_Data_Region_Size = 1024;

__FLASH_segment_start__ = ORIGIN( FLASH );
__FLASH_segment_end__ = __FLASH_segment_start__ + LENGTH( FLASH );

__privileged_functions_start__ = ORIGIN( FLASH );
__privileged_functions_end__ = __privileged_functions_start__ + _Privileged_Functions_Region_Size;

__SRAM_segment_start__ = ORIGIN( RAM );
__SRAM_segment_end__ = __SRAM_segment_start__ + LENGTH( RAM );

__privileged_data_start__ = ORIGIN( RAM );
__privileged_data_end__ = ORIGIN( RAM ) + _Privileged_Data_Region_Size;

此設置會導致在create task時跑進hard fault handler，經由debugger 觀察出在建完TCB要插入ITEMLIST時會access到沒有權限的記憶體位置，因此懷疑為linker script的錯誤，但我屢次改動此.ld檔卻依舊沒辦法成功建出task，因此有關於MPU的實作以失敗告終。