版本 fde43fdd8b62930ae646c3e2a76c6b9554eeaec0

rtenv+

協作者

2015 年夏季:
- 陳建霖
2015 年春季:
- 劉家瑄, 賴弈豪, 陳建霖, 蘇容德, 李洋逸, 戴紹軒
2014 年春季:
- 楊震, 丁士宸, 程政罡, 李昆憶, 鄭聖文

共筆

2015 年夏季: PSE51
2015 年春季: hackpad, Context Switch hackpad
2014 年春季: hackpad

作業系統架構

rtenv+介紹

rtenv+是一個基於Cortex-M3的極小型的RTOS系統，用以教學用。

設計結構：

dual mode：十分簡易，目前kernel mode僅負責exception handling 、system call與 context switch的處理。rtenv+將 file system server 與path server在user task執行，並將其priority設為最高，藉由message來通知server process。
task：在rtenv+，可同時執行多 tasks (concurrency)，以priority + round-robin的方式排程。利用linked list的方式實作ready queue，event queue，並有分別的task state使task有基本的ready - running - blocked的state。因為程式方面十分簡單、易懂，在 scheduling 與 task 方面提供極大的擴充性。目前也提供了部份的POSIX Thread。
communication：rtenv+提供多種通訊方式，pipe、block、message queue、register file。所有的實作已有完整結構，未來要自由擴充十分容易。而目前主要用到的部份在於shell 的 input/ouput與file system方面。
file system：目前實作的部份有romfs，以block的方式read/write，但尚未實作相對應的shell指令。

Source code

原始來源： https://github.com/embedded2014/rtenv-plus

文件請見：rtenv+ 2014

(目前)擴充： https://github.com/lecopzer/rtenv-plus

Cortex-M3 基本概念

Execution modes

User (non-privileged) mode

has limited access to the MSR and MRS instructions, and cannot use the CPS instruction
cannot access the system timer, NVIC, or system control block
might have restricted access to memory or peripherals.

Privileged mode

software can use all the instructions and has access to all resources.

Operation mode

Thread mode

The Cortex-M3 提供 Privileged and User ( non-privileged ) execution
Privileged mode在code執行時可full access
non-privileged是limited。

Handler mode

只有在exception發生時進入，且必為Privileged。
Main and Process Stacks

MSP：Main Stack Pointer

一開始程式進入即為MSP

PSP：Process Stack Pointer

這是Programmer可以自己利用，在切換task間的SP。就是可以讓每個task有自己的sp。

Exception (Cortex-M3)

Cortex-M3有支援許多不同的Exception types

這裡我以SVC來做說明。

當呼叫SVC 0時，SVC會觸發exception number 11並且發生exception entry

Exception Entry

進入exception的條件：

要在thread mode
或者，要進入的exception的priority比正在執行的還高，則preempts，

若已有其他exception正在handle，則exception變成巢狀的(exception中還有exception)。

而無論exception是 tail-chained或late-arriving exception，都會自動依序將xPSR, PC, LR, R12(ip), R3, R2, R1, R0 push進去

tail-chained

當一exception handler完成時，若這時剛好有其他在等待的exception符合exception entry的條件時，並要進入時，則剛剛完成的exception handler的最後就不用pop，直接執行下一個exception handler。用來加速exception servicing。

late-arriving

當一exception在執行state saving時，若此時有high priority的exception進入的話，則不用中斷此state saving，因為他們是來自同一state。用來加速exception的preemption。

而當此state saving完成後才會開始執行exception handler，而同時，processor也會將EXC_RETURN寫入LR

EXC_RETURN的功能是，他要記錄你在發生exception前你的sp是位在psp還是msp，且你是在handler mode 還是 thread mode，以便得知exception return時應該有的行為。

Exception Return

exception有進就要有出。

exception return的條件： - 在Handler mode發生，且要使PC被設為EXC_RETURN。

將PC設為EXC_RETURN是為了要讓exception得的機制知道exception完成了，藉由偵測31~4bits，當全為 f 時，processor會detect到他不是一個一般的branch，並且會開始執行exception return的部分。

這張圖很清楚的說明exception return做了甚麼事。

Exception return：當 LR 值為 EXC_RETURN 之一: 0xfffffffd 時，
1. processor 會轉回 thread mode
2. 從 process stack 取回 exception 時所 push 進去的 registers
3. 使用 PSP 為當下的 SP

Rtenv+ 系統詳細內容

task

rtenv-plus 中的 task 以 task_control_block 來呈現其資訊。

    struct task_control_block {
        struct user_thread_stack *stack;  // 指到記憶體中 stack 的位置
        int pid; //記錄目前 task 的 pid
        int status; //記錄目前 task 的狀態
        int priority; //記錄目前 task 的優先度
        int inuse; //記錄目前 task 是否使用

        struct list list; 
    };
    
    // 其中 status 共有 5 種狀態被定義
    #define TASK_READY      0
    #define TASK_WAIT_READ  1         
    #define TASK_WAIT_WRITE 2
    #define TASK_WAIT_INTR  3
    #define TASK_WAIT_TIME  4

struct task_control_block *current_tcb：此 global variable 用來指向當前執行的 task 的 tcb 的頭（struct user_thread_stack *stack），用於context switch與exception handler

init_task

功能：將系統初始函式的位址放置到 process stack 的 lr 位置。以及 exception return 的 lr 位置
運作：

    /* 傳入的參數為：欲初始化的 stack pointer, 與初始的 function 位置 */
    unsigned int *init_task(unsigned int *stack, void (*start)())
    {
        /* 由於 stack 的設計為 full descendent stack（從低位到高位），
         * 所以 stack pointer 一開始必須指向最高位址。
         * 觀察 user_thread_stack 的設計：r4 是最低位址，處在 stack 的底部
         * 而預期將 thread 的初始 function 位址存到 _lr 中以及 lr 中，加上CPSR的初始值，所以必須 push 18個 word.
         */
        stack += STACK_SIZE - 18;
        /* 利用 pointer arithmetic，可以將 first() 的位址存到 _lr 中：
         * user_thread_stack -> |r4 |r5 |r6 |r7 |r8 |r9 |r10| fp |_lr|...
         *                         stack ->| [0]|[1]|[2]|[3] |[4]|[5]|  [6]| [7]|[8]|...
         *                         其餘部份請參考
         */
        stack[8] = (unsigned int)start;
        /*  lr   */
        stack[16] = (unsigned int)start;
        /*  CPSR  */
        stack[17] = (unsigned int)0x01000000;
        /* 回傳新的 sp 給該 task */
        return stack;
    }

POSIX thread

pthread -> task -> kernel

void task_create(int priority, void *func, void *arg)
void task_exit(void* ptr)

    _disable_irq();  //利用將 current_tcb 的 list 從 ready list 移除，並且將現在的 tcb 的 inuse設為0表示task 為沒使用的狀態，最後進到while(1) 等待下一次systick exception 作context switch 後將永遠不會再選到這個 task。
    list_remove(&current_tcb->list);         
    /*  Never context switch here   */
    current_tcb->inuse = 0;
    task_count--;
    _enable_irq();
        
    while(1);

建立與執行task

一開始呼叫task_create，以以下為例 task_create(0, func, NULL)

在執行後：

再來使current_tcb指向pid = 0的task。並開啟Systick

最後task_start() 會將 task的 (r7-r11, lr, _r7) 存入system register，並且切換至 PSP 開始執行 task (bx lr)

list

實作檔案：list.c
類型：cyclic double linked list
函式：
- list_init：初始化 node，prev 及 next 都指向自己。
- list_empty：如果 list 的 next 還是指向自己，代表 list 為空。
- list_remove：將指定的 node 從 linked list 中移除。
- list_unshift：將 new 從原本的 linked list 中移除，再將其 push 到 list 的 next。
- list_push：將 new 從原本的 linked list 中移除，再將其 push 到 list 的 prev。
- list_shift：將 list 的 next 從 linked list 中 pop 出來。
Macro：
- list_entry：取得該 list node 所屬的 structure 或 union variable 的位址。

    #define list_entry(list, type, member) \
        (container_of((list), type, member))
    #define container_of(ptr, type, member) \
        ((type *)(((void *)ptr) - offsetof(type, member)))

Macro offsetof( type, member ) 會以 bytes 的形式回傳指定 member 在 type 指定的 structure 或 union 的位置。如：

    struct foo {
        int a;
        int b;
    };

則 offsetof( foo, a ) 會回傳 0，offsetof( foo, b ) 會回傳 4。看到 TCB 的設計:

    struct task_control_block {
        struct user_thread_stack *stack;
        int pid;
        int status;
        int priority;
        int inuse;
    
        struct list list;
    };

使用 task = list_entry(curr, struct task_control_block, list); 傳入 list node 的位址減去 list node 在 structure 中的 byte 位置，就會得到該 structure 第一個元素的起始位址，同時也是該 structure 變數的位址。

list_for_each：以 list 為起點，搜尋所有 node。
list_for_each_safe：以 list 為起點，但考慮到有些因為呼叫如 list_shift 之類的 function 會把 list node pop 出來，導致搜尋的連結中斷，list_for_each_safe 讓剩下的 node 可以繼續被搜尋。

scheduler

rtenv-plus maintain 一個 global 的 list 陣列 ready_list，為 scheduler 的資料結構，ready_list 的每一個元素都對應到不同優先權。

    struct list ready_list[PRIORITY_LIMIT + 1];

在第一個 task 的初始化，建立新的 task，或是利用 setpriority 設定 task 的優先權，會使用 list_push 將 task push 到對應優先權的 ready_list 中，多個 task 之優先權可能相同

判別 ready_list 中的 element 是否為 empty，則觀察有沒有 task 被 push 到該 element 中

觸發 scheduler 選擇下一個執行的 task 有三種狀況

SysTick_Handler：STM32F4 系統時鐘預設為 168MHz

    SysTick_Config(configCPU_CLOCK_HZ / configTICK_RATE_HZ);

configCPU_CLOCK_HZ 為 72MHz， configTICK_RATE_HZ 為 100， ( 72M/100 ) /168M = 4.29m，每經過 4.29ms 就會觸發一次 SysTick_Handler

USART2_IRQHandler：STM32F4 與週邊裝置或是連結的電腦傳輸資料時，usart2所觸發的中斷
SVC_Handler ：system call 執行 svc 0 觸發

當 rtenv-plus 分配給 task 的執行時間到了，且正在執行的 task 之優先權所對應到的 ready_list 元素，最前端為正在執行的 task，則將該 task 放到 ready_list 元素的最末端，讓其他有相同優先權的 task 能夠被執行。

    task = &tasks[current_task];
    if (timeup && ready_list[task->priority].next == &task->list)
        list_push(&ready_list[task->priority], &tasks[current_task].list);

每次 scheduler 在選擇下一個要執行的 task，會從 ready_list 中尋找優先權最大且最前端的 task。

    for (i = 0; list_empty(&ready_list[i]); i++); // 尋找非空的 ready_list。
    
    list = ready_list[i].next; // 將 list 指到 ready_list[i].next 所指的 `struct list`，這個 list 會指到某一個 struct task 裡頭的 struct list。
    task = list_entry(list, struct task_control_block, list); // 將 task 指到上面講的 struct task
    current_task = task->pid; // 記錄這個 task 的 pid

由上述可知道 rtenv-plus 是一個使用 round-robin 排程的 preemptive 作業系統

Event Monitoring

實作檔案：event_monitor.c
功能：負責處理所有的 event 。event 包含所有file 的 read/write、所有的exception都是一個“event”，且其有對應的handler。
特性：
- Event Collection：kernel 擁有一個 event monitor 來收集 occurrences 並轉送給 handlers。
函式：
- event_monitor_init：初始化 event_monitor
- event_monitor_find_free：找尋有無尚未 registe r的 event_monitor
- event_monitor_register：為 event 註冊其對應的 handler 與 data
- event_monitor_block：將傳入的 task 的 list 從原有的list中移除，並將此list link到指定的event 的 list (i.e. 此task在等此event)。
- event_monitor_release：標記指定的 event 的狀態為pending，表示已可處理在等此event的所有task。
- event_monitor_serve：檢查 pending，並讓 handler 處理 pending event 中 list 的 task。處理完後將 task 從 event 的 list 取出移到 ready list 裡

PendSV

只負責context switch，且要在沒有exception active才會執行。

可減少多餘的context switch
exception handler 只需關心自己要處理的部份，不用管如何context switch
有利於多exception 同時 pending 時的處理

PendSV實作

當要call PendSV前，要先使PendSV pending，藉由設定ICSR (Interrupt Control and State Register)。

    void __attribute__((naked)) set_pendsv()
    {
    __asm volatile(
        "ldr r4, =0xe000ed04    \n"
        /*  Pending PendSV */
        "mov r5, #0x12000000    \n"
        "str r5, [r4]           \n"
        "bx lr                  \n"
    );   
    }

當所有exception handler都exception return後 (意即沒有active的exception)，此時處於pending的 PendSV會開始執行其hadler:

    PendSV_Handler:
      // 必須先關閉所有interrupt避免context switch途中遭中斷。                                                                                                      
      cpsid i
      //將psp存入r0
      mrs r0, psp 

      ldr r3, =current_tcb
      ldr r2, [r3]
      ldr r1, [r2]        
      // 將必要的register 存回PSP (save state)
      stmdb r0!, {r7}
      stmdb r0!, {r4-r11,ip}
      // 把PSP存入current_tcb
      str r0, [r2]
      // 注意這裡的lr是exception return的值0xfffffffX
      stmdb sp!, {r3, lr}
      bl context_switch
      ldmia sp!, {r3, lr}
      // 重新讀取current_tcb
      ldr r1, [r3]
      ldr r0, [r1]
      // context switch後要將下一個要載入的task的state pop出來
      ldmia r0!, {r4-r11,ip}
      ldmia r0!, {r7}
      msr psp, r0
      cpsie i
      // exception return
      bx lr

System Call

user mode 時，執行屬於 system call 的函式，將 system call 的代碼存入 []r7並觸發 SVC exception，執行SVC_Handler轉換成 kernel mode 後，在syscall()`` 中實作 system call 功能。

system call 函數的參數以及原本 user mode push 進去的暫存器之值，皆可透過 current_tcb 來傳遞，因為 current_tcb->task 指向 task 在 user mode 用來 push 的 stack，且 system call 的函數變數會先儲存到暫存器 r0 ~ r3

syscall() 中判斷 system call 的代號並執行對應功能

0x1：fork

int fork();

分支出一個新的子task，子task複製所有父task push 進去的 stack 資料，繼承優先權，並為子task設定 pid 為當前task的數量-1(第一個初始task之 pid 為0)，也將子task.list push 進 ready_list。父task回傳0，子task則回傳 pid 之值(不等於0)。

若task數量已達到上限，則無法分支出新的 task，回傳-1。

0x2：getpid

int getpid();

回傳該 task 之 pid，也就是 current_task。

0x3：write

int write(int fd, const void *buf, size_t count); fd 是對應的 file descriptor，buf 則是要被寫入的地方，count 則是要寫入多少資料

實現行程之間的溝通以及檔案系統的實作。根據不同檔案類型，用 writable(struct file*, struct file_request*, struct event_monitor *) 確認是否可寫入，若可以則執行定義好的 write(struct file*, struct file_request*, struct event_monitor *) ( 非system call )

0x4：read

int read(int fd, void *buf, size_t count); fd 是對應的 file descriptor，buf 則是要被讀取的地方，count 則是要讀取多少資料

實現行程之間的溝通以及檔案系統的實作。根據不同檔案類型，用 readable(struct file*, struct file_request*, struct event_monitor *) 確認是否可讀取，若可以則執行定義好的 read(struct file*, struct file_request*, struct event_monitor *) ( 非system call )

0x5：interrupt_wait

void interrupt_wait(int intr); intr 為特定的 interrupt 編號

透過 NVIC_EnableIRQ(current_tcb->stack->r0); 啟動特定的 interrupt 使之後能夠被觸發，task 必須在 interrupt 被觸發之後才可以繼續執行，於是先使用 event_monitor_block 擋住 task，task的狀態變成TASK_WAIT_INTR。

0x6：getpriority

int getpriority(int who); who 決定選擇哪個 task，0為 tasks[current_task]

回傳 task 的優先權。

0x7：setpriority

int setpriority(int who, int value); who 決定選擇哪個 task，0為 tasks[current_task]，value 則是優先權大小

設定 task 的優先權，優先權不小於 0 也不大於 PRIORITY_LIMIT，除了設定 current_task 的優先權之外，也可以更改其他 task 的優先權。

0x8：mknod

int mknod(int fd, int mode, int dev); fd 是對應的 file descriptor，mode 不影響，dev 決定 file_operation 結構為哪種檔案類型

改變傳入對應參數 files[fd] 所指向的 file_operation 結構，結構包含write，writable，read，readable，lseek，lseekable 函式(不是 system call 的函式)。

0x9：sleep

void sleep(unsigned int); unsigned int 表示需等待幾次 SysTick 發生

將 tasks[current_task] 擋住，狀態變成 TASK_WAIT_TIME，等待觸發 SysTick_Handler ，且觸發次數必須為 unsigned int 之值，才能繼續執行。

0xa：lseek

void lseek(int fd, int offset, int whence); fd 是對應的 file descriptor，offset 是偏移量，whence 則是決定讀寫頭一開始會指到哪裡

實現檔案系統的實作。根據不同檔案類型，用 lseekable(struct file*, struct file_request*, struct event_monitor *) 確認是否可寫入，若可以則執行定義好的 lseek(struct file*, struct file_request*, struct event_monitor *) ( 非system call )

default：

syscall執行說明

在 syscall (以fork說明) 中，會觸發 svc exception，程式轉往執行 SVC_Handler()，
1. 同時 processor 會將 xPSR、PC、LR、R12、R3、R2、R1、R0依序 push 到目前的 stack 中 ( process stack )，被 push 到 process stack 的資訊中含有離開 fork() 後繼續執行的指令位址。此步即exception entry。
2. 進入 syscall() 根據 current_tcb->stack->r7 (這裡是fork:0x01)來處理對應的syscall
3. 最後將 exception entry 時所 push 的 register pop 出來，並回到exception entry 時的 PC 。

進行fork

開始執行 kernel mode 後，藉由 tasks[current_task].stack->r7，可以取得在 fork() 傳入的值。因此 kernel 判定要執行 fork 動作，將母 task 的 stack 內容複製到子 task 的 stack 中，但是母 task 的 r0 存的是目前產生的 task 數量，而子 task 則是 0。

::

[ fork() ] .global fork fork: 115d0: b480 push {r7, lr} 115d2: f04f 0701 mov.w r7, #1 115d6: df00 svc 0 // <- Exception 在這裡發生，所以 PC 被存的值為 0x115d8 115d8: bf00 nop // <- 藉由 exception return 使的程式回到這裡繼續執行 115da: bc80 pop {r7, lr} 115dc: 4770 bx lr // <- 回到 task 繼續執行
由於在 kernel mode 中，已經將 fork() 所應回傳的值放到 process stack 的 r0 中，藉由 exception return 將這個值 pop 到 R0。則當程式離開 fork() 時，會回傳 task_count (R0)。

與 POSIX fork 差別

不同於 POSIX fork 的使用是架構在 virtual memory 上，利用copy-on-write的方式。

rtenv-plus 只是單純地將母 task 在記憶體中所使用的 stack 完完整整地複製一份到子 task 所對應的 stack。

在 file descriptor 方面，因為 rtenv-plus 並沒有所謂的 file descriptor table，所以如果母 task 有開檔的話，子 task 也只是單純繼承 file descriptor 的值而已。

rtenv-plus 的 fork 與在同樣沒有 virtual memory 支援下所使用的 vfork 也有非常大的不同處。

vfork 在產生子 task 後，會先將母 task suspend 直到子 task 結束為止。而 rtenv-plus 則是兩個 task 能夠同時存在。
在記憶體使用方面，vfork 的兩個 task 會使用同一個實體記憶體位置，不同於 rtenv-plus 兩個 task 用的是不同的實體記憶體位置。

另外，在其它系統上，子 task 的 PPID 會是其母 task 的 PID，所以兩者之間可以有互動，例如母 task 等待子 task 結束。但在 rtenv-plus 上，因為沒有實作 PPID ，所以兩個 task 基本上是獨立運作而互不干擾的。

File Descriptor

在 rtenv-plus 中提供四種檔案類型，分別為 fifo pipe ( S_IFIFO )、message queue ( S_IMSGQ )、register file ( S_IFREG )、block file ( S_IFBLK )。每一種檔案類型都擁有自己的資料結構以及處理函式，其中處理函式針對 read、write、lseek 這三個 system call 都有提供一個檢查函式 ( e.g. fifo_writable ) 以及一個或多個運作函式 ( e.g. fifo_write )[#]_ 。

檔案類型一覽表：

檔案類型	\| type	\| 資料結構	\| 處理函式	\| 初始化函式
fifo pipe	S_IFIFO	struct pipe_ringbuffer	沒有 lseek	fifo_init
message queue	S_IMSGQ	struct pipe_ringbuffer	沒有 lseek	mq_init
register file	S_IFREG	struct regfile	皆有提供	regfile_init
block file	S_IFBLK	struct block	皆有提供	block_init

初始化

透過 system call int mknod(int fd, int mode, int dev) 來指定 file descriptor 的類型，每一種檔案類型都有提供一個初始化函式。初始化函式會：

從 memory pool 配置一塊記憶體給該檔案的資料結構
設置處理函式
將資料結構中的 file 元素存到 file descriptor array。
設置 event sensor

Structures

file_request：task 對於 fd 的請求，或是 fd 對 fd 的請求

    struct file_request {
        struct task_control_block *task;
        char *buf;        // 請求所需的資料，可以是 buffer 或是 其他 request 的資料結構
        int size;         // *buf 的大小
        int whence;       // 用於 lseek，標記 lseek 的請求類型
    };

file：file descriptor 的 fd number 以及所屬的處理函式

    struct file {
        int fd;          // 獨特的 fd number
        struct file_operations *ops;     // 指向所屬的處理函式結構
    };

file_operations：利用 pointer to function 來設置處理函式

    struct file_operations {
        int (*readable)(struct file*, struct file_request*, struct event_monitor *);
        int (*writable)(struct file*, struct file_request*, struct event_monitor *);
        int (*read)(struct file*, struct file_request*, struct event_monitor *);
        int (*write)(struct file*, struct file_request*, struct event_monitor *);
        int (*lseekable)(struct file*, struct file_request*, struct event_monitor *);
        int (*lseek)(struct file*, struct file_request*, struct event_monitor *);
    };

file descriptor 關係

在初始化函式中，會將資料結構中的 file 元素存到 kernel 的 file descriptor array，所以只要在 file descriptor array 中拿到指定的 file 元素，透過 marco container_of，就可以拿到該 file descriptor 的資料結構。

pipe ( fifo pipe, message queue )

IPC 的實作方式之一。
資料結構

    struct pipe_ringbuffer {
        struct file file;      // 所屬的 fd 以及 file operations
        int start;             // ring buffer 目前的讀寫起點
        int end;               // ring buffer 目前的讀寫終點
        int read_event;        // 該 fd 所屬的 read event ID
        int write_event;       // 該 fd 所屬的 write event ID
        char data[PIPE_BUF];   // pipe 的 buffer，ring buffer
    };

Event Handler
- int pipe_read_release(struct event_monitor *monitor, int event, struct task_control_block *task, void *data)：讓因為讀取而被 block 住的 task，重新送出讀取請求。
- int pipe_write_release(struct event_monitor *monitor, int event, struct task_control_block *task, void *data)：讓因為寫入而被 block 住的 task，重新送出寫入請求。
Macros
- PIPE_PUSH( pipe, src )：從 src push 1 byte 的資料到 pipe 中。
- PIPE_POP( pipe, dst )：從 pipe pop 1 byte 的資料到 dst 中。
- PIPE_PICK( pipe, dst, size_byte )：從 pipe 中讀取指定 size 的資料到 dst，但不會將 pipe 的資料 pop 出來。
- PIPE_LEN( pipe )：回傳 pipe 中的資料量 in bytes。
fifo pipe ( S_IFIFO )
- 傳遞資料格式：| 資料 |
- fifo_readable
  - FILE_ACCESS_ERROR：請求讀取的大小超過 pipe buffer 的大小。
  - FILE_ACCESS_BLOCK：pipe 中的有效資料量未達要求讀取的大小，task 會被 push 到該資料結構的 read event list 中，進入 TASK_WAIT_READ 狀態。
  - FILE_ACCESS_ACCEPT：pipe 中的有效資料量大於或等於要求讀取的大小。
- fifo_read：1 byte 1 byte 的從 pipe POP 資料出來存到使用者提供的 buffer 裡。讀取完成後，發出 write pending 讓等待寫入同一個 file descriptor 的 task 可以寫入資料。
- fifo_writable
  - FILE_ACCESS_ERROR：請求寫入的大小超過 pipe buffer 的大小。
  - FILE_ACCESS_BLOCK：如果剩餘有效空間小於要求寫入大小的話，task 會被 push 到 write event list 中，進入 TASK_WAIT_WRITE 狀態。
  - FILE_ACCESS_ACCEPT：pipe 有足夠空間可以寫入。
- fifo_write：1 byte 1 byte 將資料從使用者提供的 buffer 寫入 pipe 裡。寫入完成後，發出 read pending 讓等待讀取同一個 file descriptor 的 task 可以讀取資料。
message queue ( S_IMSGQ )
- 傳遞資料格式：| 資料長度(4 bytes) | 資料 |
- mq_readable
  - FILE_ACCESS_BLOCK：message queue的資料傳輸格式一定帶有 4 bytes 的資料來指示後面所帶的資料長度，所以當 pipe 的有效資料未達 4 byte 時，代表還未傳輸完成，task 會被 push 到 read event list，進入 TASK_WAIT_READ 狀態。
  - FILE_ACCESS_ERROR：請求讀取長度大於這次傳輸的長度。透過“資料長度( 4 bytes )”來檢查。
  - FILE_ACCESS_ACCEPT：請求長度等於或小於這次的傳輸長度。
- mq_read：先從 pipe 中取出資料長度，再依照資料長度將 pipe 資料 pop 出來存到使用者提供的 buffer 裡。讀取完成後，發出 write event pending 讓等待寫入同一個 file descriptor 的 task 可以寫入資料。
- mq_writable
  - FILE_ACCESS_ERROR：寫入必須是 non-atomic，所以寫入長度( 包含 4 byte 的長度資訊 )不能大於 pipe 的大小。
  - FILE_ACCESS_BLOCK：pipe 沒有足夠的有效空間寫入，將 task push 到 write event list，進入 TASK_WAIT_WRITE 狀態。
  - FILE_ACCESS_ACCEPT：pipe 有足夠的有效空間
- mq_write：先將請求寫入的長度 push 到 pipe 裡，再將資料 push 到 pipe 裡。寫入完成後，發出 read event pending，讓等待讀取同一個 file descriptor 的 task 可以讀取資料。

Pipe 的 Read 與 Write

以 serialout() 與 rs232_xmit_msg_task() 為例。/dev/tty0/out 為 fifo pipe，而 rs232_xmit_msg_task() 寫入資料到 pipe 中，serialout() 從這個 pipe 讀出資料。

以 write 的部分為例，在 FILE_ACCESS_ACCEPT 的 case 中會送出 read_event pending。執行完 write 的工作後，kernel 會繼續執行 event_monitor_serve()，檢查有沒有 event pending，此時，剛剛送出的 read_event 就會被處理，檢查有沒有在 read 的時候被 push 到 read_event list 的 task。如果有，則執行 read_event 的 handler - pipe_read_release()。pipe_read_release() 會重新呼叫 file_read()，讓 task 再次嘗試讀取 pipe，流程判斷如上圖，但是不同的 case 有不同的處理方式：

FILE_ACCESS_ACCEPT：值為1，代表讀取成功。event_monitor_serve() 會將該 task 從 read_event 的 list 中 pop 出來，並重新 push 回 ready_list 裡，task 的狀態也被改為 TASK_READY。
FILE_ACCESS_BLOCK：值為0，代表仍舊未達指定讀取量，則會被繼續 BLOCK 住。
FILE_ACCESS_ERROR：不會發生。因為在第一次嘗試讀取時，如果發生 FILE_ACCESS_ERROR，該 task 不會被 push 到 read_event 的 list 中。

至於 read，則反之。下圖為從輸入到輸出所牽涉的 task 以及使用的 pipe，其中箭頭的起點方執行 write，終點方為 read：

Block File( S_IFBLK )

特性：資料的讀寫以 block 為單位，大小不定，小至1，大至 fd 所提供的 buffer 大小。當需要從硬體讀取資料時，會將一整塊資料放入緩衝區裡，系統在從緩衝區裡取得資料；寫回時也會先將資料放在緩衝區，直到資料滿了在一次寫進硬體中。[#]_
資料結構

    struct block {
        struct file file;           // 所屬的 fd 以及 block file operations
        int driver_pid;              // 所屬 driver ( 就是將此 fd 註冊為 S_IFBLK 的 task ) 的 pid
        struct file *driver_file;   // 所屬 driver 的 fd
        int event;                   // block event ID

        /* request */
        int request_pid;            // 請求 access 此 fd 的 task pid，如果為 0 代表尚未對 driver 發出請求
        int buzy;                   // 為 1 時代表此 fd 正等待 driver 處理，否則為 0
        int pos;                    // block file 的讀寫頭位置
        char buf[BLOCK_BUF];        // buffer

        /* response */
        int transfer_len;           // lseek：driver 計算完的新的讀寫頭位置
    };

    struct block_request {
        int cmd;       // 請求 romdev_driver() 執行的指令
        int task;      // 請求 task 的 pid
        int fd;        // 請求 access 的 fd number
        int size;      // lseek 為指定的讀寫起點；read 和 write 則為讀寫大小
        int pos;       // 詳見 block_request_****able 條目
    };

Event Handler: block_event_release(struct event_monitor *monitor, int event, struct task_control_block *task, void *data)

讓 task 重新發送一次請求，請求類別由 stack 中的 r7 值( 0x03: file_write, 0x04: file_read, 0x0a: file_lseek )判定，請求的 file descriptor 資料結構的 reference 存在 data 中。
block 的請求有 read、write、lseek，分成兩大類，一個是外部對 fd 的請求 ( block_request_ 系列 )，另一個是 driver 對 fd 的請求 ( block_driver_ 系列 )。當外部想要對此 fd 請求時，會先被 block 住，等待 driver 對 fd 發出請求並處理完後，才會讓外部重新發出請求。
block_request_****able
- 第一次請求( request_pid 為 0 )：先對 block 所屬的 driver 發出請求，如下表：

　　將 block_request 的 reference 存到 file_request，透過 IPC 將 file_request 傳給 romdev_driver()。並將 fd 的 request_pid 設為自己的 pid，將 buzy 設為 1，代表對 driver 發出 access 此 fd 的請求。task 會被 push 到該 fd 的 event list 中，進入 TASK_WAIT_WRITE 狀態。

第二次請求( request_pid 為請求 task 的 pid )：由 event_monitor_serve() 來幫助 task 再次發出請求。如果 driver 已經處理完請求的話 ( buzy 為 0 ) 就會回傳 FILE_ACCESS_ACCEPT。否則就繼續 block 住。
block_driver_****able
- FILE_ACCESS_ACCEPT：只有在有 task 想要 access block fd 時 ( buzy = 1 )
- FILE_ACCESS_ERROR：如果沒有 task 請求 access 該 block fd
block_response：將指定資料傳送到指定的 block file descriptor，透過這些資訊 file descriptor 可以從 block file 取得資料。

    struct block_response response = {
        .transfer_len = len,  // 請求讀取的長度
        .buf = buf            // 請求資料的起點
    };

以下將以對 block file 執行 lseek、write、read 指令所牽涉的過程來探討：

lseek：設定 block file 讀寫頭。回傳：新的讀寫頭位置。
1. void lseek(int fd, int offset, int whence);： fd 為對象 file descriptor 的 ID；offset 為距離檔案起點的位置( in bytes )；whence 可以指定使用哪一種設置方式( SEEK_SET, SEEK_CUR, SEEK_END )。
2. 透過 system call 將請求資訊放到 file_request，並傳送給對象 fd。

    struct file_request {
        struct task_control_block *task;   // 為請求的 task
        char *buf;     // NULL
        int size;      // offset
        int whence;    // whence：SEEK_SET、SEEK_CUR、SEEK_END
    };

由於請求的 task 非 driver，所以進行 block_request_lseekable。由於是第一次請求，所以透過 IPC 向 driver 送出 block_request ( 包在 file_request 中 )，並等待 driver 的處理。
driver 收到 BLOCK_CMD_SEEK 指令後，計算好要設定的讀寫頭位置，使用 SEEK_SET ( 直接指定位置 ) 設定讀寫頭：

+ SEEK_SET：直接將讀寫頭設定在 ``offset`` 指定的位置
+ SEEK_END：將讀寫頭設定在 block file 結尾 (EOF) 後 ``offset`` bytes 的位置
+ SEEK_CUR：將讀寫頭設定在 block file 的目前讀寫頭後 ``offset`` bytes 的位置

    struct file_request {
        struct task_control_block *task;   // driver
        char *buf;     // NULL
        int size;      // 相對於 block file 起點的位置
        int whence;    // SEEK_SET
    };

現在是由 driver 發出 lseek 的請求，也確認此 fd 正有請求要處理後，執行 block_driver_lseek。block_driver_lseek 會將欲設定讀寫頭的位置存在此 fd 的 transfer_len 欄位，並將 buzy 設回 0，確認處理外部 task 對此 block fd 的請求。送出 block event pending，讓等待處理的 task 繼續執行。
event_monitor_serve 處理 block event pending 會執行 block_event_release，透過 block_event_release 使得請求此 fd 的 task 再次 lseek 發出請求。
外部 task 對於此 fd 為第二次請求，而且 driver 也已經處理完請求，執行 block_request_lseek。
block_request_lseek 將 driver 所欲設定的值 ( 存在 transfer_len 欄位 ) 複製到此 fd 的 pos 欄位，完成設定讀寫頭的位置。
將此 fd 的 request_pid 設回 0，代表完成外部 task 的請求，請求 task 會被 push 回 ready list，回傳值為新的讀寫頭位置。

read：以 fd 的讀寫頭為起點，一次讀取指定大小的資料。回傳：實際讀取的資料量
1. 外部 task 對此 fd 作 read 的請求，執行 block_request_readable。由於是第一次請求，所以透過 IPC 向 driver 送出 block_request，並等待 driver 的處理。
2. driver 收到 request 後，執行 BLOCK_CMD_READ 指令。driver 會計算讀取的區塊是否有超過 block file 的檔案結尾，如果有就只會讀取到檔案結尾。driver 會將計算結果透過 block_response 來讓 fd 讀取 block file 的資料。
1. block_response 使用 system call write 來傳輸資料給指定 fd。來自於 driver 的請求，block_driver_writable 檢查該 fd 是否有收到外部請求，因為在 ‘1.’ 時有發出請求，所以執行 block_driver_write。
2. block_driver_write：將資料從 block file 複製到 fd 的 buffer 中，將寫入長度存到 fd 的 transfer_len 欄位中，將 buzy 設為 0，表示 driver 處理完請求，並發出 block event pending。
3. 透過 block event handler block_event_release，被 block 住的 task 再次送出 read 請求。由於 driver 已經處理完請求，所以執行 block_request_read。
4. block_request_read 將 fd buffer 中的資料複製到使用者提供的 buffer 中，並更新 fd 的讀寫頭位置。完成讀取 block file。
write：block file 是唯讀的，無法寫入。回傳：-1。
1. 如果外部對 block file 提出寫入請求，block_request_write 會透過 IPC 傳送資料給 driver，而請求的 task 會被 push 到 block event list。
2. driver 執行 BLOCK_CMD_WRITE 指令，由於 block file 是唯讀的，所以執行block_response(fd, NULL, -1);。
3. 參考 write 指令中，block_response的執行過程，將不會讀取任何資料到 fd 的 buffer 中，而使用者的資料也不會被寫入到 block file 中。

Register File( S_IFREG )

透過 romfs_server() 註冊的檔案，類型為 S_IFREG ，皆由 romfs_server() 來管理。亦是一種 block file descriptor，從 block file 讀取資料。
資料結構：

    struct romfs_file {
        int fd;         // fd number
        int device;     // 該檔案資料所在的 fd number
        int start;      // 在檔案資料中的資料起點
        size_t len;     // 在檔案資料中的長度
    };

    struct regfile {
        struct file file;           // 所屬的 fd number 以及 regfile operations
        int driver_pid;              // 所屬 driver ( 註冊此 fd 的 task ) 的 pid
        struct file *driver_file;   // 所屬 driver 的 fd file
        int event;                   // regfile event ID

        /* request */
        int request_pid;            // 請求 access 此 fd 的 task pid，如果為 0 代表尚未對 driver 發出請求
        int buzy;                   // 為 1 時代表此 fd 正等待 driver 處理，否則為 0
        int pos;                    // regfile 的讀寫頭位置
        char buf[REGFILE_BUF];        // buffer

        /* response */
        int transfer_len;           // 
    };

Event Handler: int regfile_event_release(struct event_monitor *monitor, int event, struct task_control_block *task, void *data)

讓 task 重新發送一次請求，請求類別由 stack 中的 r7 值( 0x03: file_write, 0x04: file_read, 0x0a: file_lseek )判定，請求的 file descriptor 資料結構的 reference 存在 data 中。
register file 對於 lseek、read、write 的請求一樣可以分成兩大類，一類是外部對於 register file descriptor 的請求 ( regfile_request_ 系列 )，一類是 block file device 對於 reigster file descriptor 的請求 ( regfile_driver_系列 )。但是請求過程與 block file 有些許不同，block file 是直接向 block device 發出請求，而 register file 則是間接透過 romfs_server() 來向 block device 發出請求。
regfile_request_****able
- 第一次請求( request_pid 為 0 )：先對 romfs_server() 發出請求，如下表：

　　將 fs_request 的 reference 存到 file_request，透過 IPC 將 file_request 傳給 romdev_driver()。並將 fd 的 request_pid 設為自己的 pid，將 buzy 設為 1，代表對 driver 發出 access 此 fd 的請求。task 會被 push 到該 fd 的 event list 中，進入 TASK_WAIT_WRITE 狀態。

第二次請求( request_pid 為請求 task 的 pid )：由 event_monitor_serve() 來幫助 task 再次發出請求。如果 driver 已經處理完請求的話 ( buzy 為 0 ) 就會回傳 FILE_ACCESS_ACCEPT。否則就繼續 block 住。
regfile_driver_****able
- FILE_ACCESS_ACCEPT：只有在有 task 想要 access regfile fd 時 ( buzy = 1 )
- FILE_ACCESS_ERROR：如果沒有 task 請求 access 該 regfile fd
regfile_response：將指定資料傳送到指定的 register file descriptor，透過這些資訊 file descriptor 可以從 block device 取得資料。

    struct regfile_response response {
        int transfer_len;  // 請求讀取的長度
        char *buf;         // 請求資料的起點
    };

lseek：void lseek(int fd, int offset, int whence);：設定檔案讀寫頭的位置，回傳：讀寫頭的新位置
1. 由外部 task 發出請求，第一次請求存取 regfile fd。regfile_request_lseekable 透過 IPC 將 fs_request 傳送到 romfs_server()，task 會被 push 到 event list 上，進入 TASK_WAIT_WRITE 狀態，等待 driver 的處理。
2. romfs_server() 執行 FS_CMD_SEEK 指令。先計算讀寫頭的位置，再使用 SEEK_SET 向請求的 fd 設置讀寫頭。
- SEEK_SET：為 offset 所指定的位置
- SEEK_CUR：目前讀寫頭的位置加上 offset
- SEEK_END：資料終點的位置加上 offset
1. 由 driver 發出的請求，而且該 fd 正有 task 要求存取，執行regfile_driver_lseek()。將已經計算過後新的讀寫頭位置存到該 fd 的 request_len。driver 完成處理，發出 pending 讓外部 task 重新發出請求。
2. 透過 event_monitor_serve() ，外部 task 重新發出請求後，是第二次發出請求。regfile_request_lseek() 將 driver 存放在 request_len 的值拿來更新 fd 的讀寫頭位置。
3. task 再次回到 ready_list 中。
read：讀取指定檔案的資料
1. 外部 task 對 regfile fd 先發出第一次 read 請求，regfile_request_readable() 透過 IPC 將 fs_request 傳送給 romfs_server()，而外部 task 被 push 到 event list，進入 TASK_WAIT_READ 的狀態，等待 driver 的處理。
2. romfs_server() 執行 FS_CMD_READ 指令。先計算在 block device 的讀取區間，然後設定 block fd 的讀寫頭，並透過 block fd 從 block device 讀取指定大小的資料。
3. 將從 block device 讀取到的資料，寫入到外部請求讀取的 fd 中。由於是 driver 發出的寫入請求，所以執行 regfile_driver_write()，會將 driver 暫存的讀取資料寫到 regfile fd 的 buffer 中，並將寫入長度存到 transfer_len 的欄位中，並發出 event pending。
4. 透過 event_monitor_serve() ，外部 task 再度發出 read 請求，是第二次發出請求，所以執行 regfile_request_read()，將存在 regfile fd buffer 的資料複製到使用者提供的 buffer，更新 regfile fd 的讀寫頭位置，並回傳讀取大小。
write：檔案是 read only，所以一定回傳 -1。

File System

在 rtenv-plus 中，與檔案系統有關的 task 有三個：

pathserver()：檔案系統的最上層，負責管理已經註冊( register，或譯暫存 )的檔案路徑及 mount point。
romfs_server()：向 pathserver() 註冊 ROMFS_TYPE，處理對於擁有 ROMFS_TYPE 的 mount point 的請求。
romdev_driver()：檔案系統的底層，可以直接取得 block file 的資料。

初始化

romfs_server()：向 pathserver() 註冊 fs type - ROMFS_TYPE，使得 pathserver() 處理向註冊為 ROMFS_TYPE 的 mount point 請求時，可以透過 romfs_server() 來處理。
romdev_driver()：向 pathserver() 註冊所管理的檔案路徑 ROMDEV_PATH - “/dev/rom0”，並將 path 所屬的 file descriptor 設為 block fd，以作為取得 block file 的資料之用。
first() 中的 mount("/dev/rom0", "/", ROMFS_TYPE, 0)：設置掛載點，對於尋找 / 目錄下的檔案，會往 /dev/rom0 來尋找，並透過 romfs_server() 以及 romdev_driver() 來取得所需的檔案內容。

外部檔案資訊

在 rtenv-plus 中類型為 block file，透過 block file descriptor 來存取。在 romdev_driver() 中有兩個指標 - &_sromdev 及 &_eromdev，分別標記 block file 的資料起點及終點。

檔頭資訊的資料結構

    struct romfs_entry {
        uint32_t parent;         // parent file entry 的 offset
        uint32_t prev;           // 同一個 parent 的前一個 child file entry 的 offset
        uint32_t next;           // 同一個 parent 的下一個 child file entry 的 offset
        uint32_t isdir;          // 標記是否為資料夾
        uint32_t len;            // 檔頭後面屬於此檔案的資料長度
        uint8_t name[PATH_MAX];  // 檔案名稱
    };

在 gdb 中可以藉由建立 marco 來取得 block file 所紀錄的資料：

    (gdb) define xxd
    >dump binary memory dump.bin $arg0 $arg1
    >shell xxd dump.bin
    >end
    (gdb) xxd &_sromdev &_eromdev

marco get_entry_at 可以從 block file 讀取檔頭資訊並顯示到 gdb 上

    (gdb) define get_entry_at
    >set memcpy( &entry, &_sromdev+$arg0, sizeof(entry) )
    >print entry
    >end
    (gdb) get_entry_at  # arg0 為 offset

檔頭資訊與內容的關係如下圖：

如果是目錄，則其資料長度 (len 欄位) 會包含此目錄下的檔案以及子目錄的資訊，如果是檔案，則只會包含自己的檔案內容。

開啟一個檔案

int open(const char *pathname, int flags);，回傳該檔案的 fd number

透過 IPC 將請求的檔名傳送到 pathserver()。
pathserver() 先尋找已經儲存的檔案路徑，如果沒有則往 mount point 尋找。如果沒有則回傳 -1，有則透過 IPC 向 romfs_server() 請求開啟此檔案。
romfs_server() 開始找尋檔案資訊：
romfs_open() 將先將 block fd 的讀寫頭設置在 block file 的資料起點，先讀取 root directory entry。
romfs_open_recur() 會來取得指定的檔案檔頭。其尋找方式為，如果是目錄，則依次讀取子檔案的檔頭並比對，如果遇到子目錄，則在呼叫一次 romfs_open_recur() 繼續尋找想要的檔頭。
如果找到指定的檔案的檔頭會回傳其檔頭起點在 block file 的 offset，如果沒有則回傳 -1。
如果有尋找到檔案，則將檔按路徑註冊到 pathserver()，並且將其 file descriptor 設置為 S_IFREG，設置其在 block device 的讀寫起點，以及可讀取的資料範圍 ( 檔頭中 len 欄位所指的資料長度 )，並回傳該 register fd 的 fd number 給最初呼叫的 task。

    struct romfs_file {
        int fd;         // fd number
        int device;     // 該檔案資料所在的 fd ( block device ) number
        int start;      // 檔頭所表記的資料起點 ( offset )
        size_t len;     // 檔頭所標記的長度
    };

第一次開啟檔案後，會將路徑存到 pathserver()，讓第二次之後的開檔可以直接在 pathserver() 中找到並回傳 fd number，節省尋找時間。且第二次作 lseek 是透過 romfs_server() 而非 romdev_driver()。

讀取外部檔案資料

外部檔案資料的 file descriptor 都會被註冊為 register file，所以執行 read 指令時，會透過 romfs_server() 向 romdev_driver() 存取 block device 的資料。每個 regfile fd 的讀寫頭起初都會被配置在其檔頭後面所帶的資料起點，如下圖:

讀取詳細過程可以參考 register file 條目的 read 細項。

安裝和測試 with qemu

建立環境

    $ sudo apt-get install build-essential git zlib1g-dev libsdl1.2-dev libglib2.0-dev "automake*" "autoconf*" libtool libpixman-1-dev

若 Ubuntu 使用 64bit 版本 ，請額外安裝 lib32gcc1 之套件

    $ sudo apt-get install lib32gcc1 lib32ncurses5

取得 GNU Toolchain: GNU Tools for ARM Embedded Processors ，或用 apt-get 取得，操作如下

    $ sudo apt-get install gcc-arm-none-eabi libnewlib-arm-none-eabi gcc-arm-linux-gnueabihf g++-arm-linux-gnueabihf qemu-user qemu-system-arm

STM32 on QEMU 環境建立與測試

You will need to prepare QEMU STM32 emulator from: QEMU STM32 v0.1.3

After download, compile the qemu_stm32 by:

    $ ./configure --disable-werror --enable-debug \
        --target-list="arm-softmmu" \
        --extra-cflags=-DDEBUG_CLKTREE \
        --extra-cflags=-DDEBUG_STM32_RCC \
        --extra-cflags=-DDEBUG_STM32_UART \
        --extra-cflags=-DSTM32_UART_NO_BAUD_DELAY \
        --extra-cflags=-DSTM32_UART_ENABLE_OVERRUN --python=python2
    $ make -j8
    $ cd && mkdir -p workspace
    $ cd workspace
    $ git clone git://github.com/beckus/stm32_p103_demos.git || git clone https://github.com/beckus/stm32_p103_demos.git 
    $ cd qemu_stm32
    git submodule update --init dtc || sudo apt-get install libfdt-dev
    ./configure --disable-werror --enable-debug \
        --target-list="arm-softmmu" \
        --extra-cflags=-DSTM32_UART_NO_BAUD_DELAY \
        --extra-cflags=-DSTM32_UART_ENABLE_OVERRUN \
        --disable-gtk
    $ make
    $ cd ../stm32_p103_demos
    $ make all
    $ make blink_flash_QEMURUN
    $ make button_QEMURUN
    $ make uart_echo_QEMURUN