版本 f3e757121575f59fdf9a6dafe3ea924291ac702e
Changes from f3e757121575f59fdf9a6dafe3ea924291ac702e to 0d20c22e26d6b9c2f259d8a91e3444902685bde2
---
title: F9 microkernel
categories: embedded, arm, stm32, stm32f429, microkernel
toc: yes
...
組員與共筆
----------
* 廖健富 / Rampant1018
* 鄒宗延 / slpbaby
* 詹凱傑 / bpotatog
* 共筆 / `Hackpad<https://hackpad.com/F9-Kernel-Note-UnUXDVd9Zv2>`_
Overview
---------
About Microkernel
==================
在計算科學領域中，microkernel(μ-kernel)指的就是集合一些精簡的軟體，而這些軟體可以提供實作作業系統的機制，例如：地址空間(Address Space, AS)管理、執行緒(thread)管理、行程間通訊(Inter-Process Communication, IPC)。如果硬體或是CPU有提供不同的執行模式，則μ-kernel就是執行在權限最高的部份，例如ARM的handle mode。
Basic Idea
+++++++++++
傳統的作業系統核心(monolithic)會提供大部分的服務，像是UNIX-like系統或是Windows等等，這類的系統都有一些典型的階層架構，示意圖如下：
.. image:: /embedded/f9-kernel/os_structure.png
一個μ-kernel的概念則是盡可能的縮小核心，並將系統服務移到kernel外，而在這種系統中會使用IPC去呼叫服務。
優點
++++
* 會有比傳統核心要小的Trusted Computing Base(TCB)。Trusted Computing Base，系統中的一部分，可以通過他自己的安全方針，因此一個安全的系統操作依賴正確的TCB架構。
* 只要增加一些服務就能簡單的擴充
* 可以被高度的調整，針對不同的server實作不同的服務，不需要就移除
* 支援軟體工程技術，user-mode的程式會執行在自己的address space下，只能透過定義好的IPC界面被使用，實現軟體封裝
* 提供fault isolation，一個發生錯誤的元件只會造成他自己的AS錯誤，不會影響其他的元件
挑戰
++++
因為所有的系統服務都是透過IPC呼叫，所以IPC是整個系統的效能關鍵之一，事實上μ-kernel-based的系統在呼叫系統服務上的overhead會大於傳統系統，μ-kernel based的系統需要四個mode的切換以及兩次完整的context switch；傳統系統只需要兩個mode切換且不需要context switch。設計並且實作μ-kernel的挑戰就在盡力降低IPC的overhead上。
歷史
++++
μ-kernel的基礎概念是由Per Brinch Hansen提出的(Brinch Hansen, Communications of the ACM, 13, 1970)。1980年代在CMU有一個Mach Project，這就是第一代的μ-kernel，而且有很多類似的計畫都在1990左右誕生，但這些第一代的微內核因為效能表現不佳而無法存活下來，而效能不佳的原因有很大的部份就是IPC耗費太多資源。
接著Jochen Liedtke證明了IPC是可以被大幅度改善的，他展示了原來Mach Project低落的效能是因為糟糕的設計與實作，造成大量的cache miss。L4與其他這種類型的系統被稱作第二代的μ-kernel。
L4 microkernel
===============
L4屬於第二代的微內核，通常被用來實作Unix-like的作業系統。
L4與他的前代L3一樣，都是由德國電腦科學家Jochen Liedtke做出來的，目的是為了反應前代不好的效能表現。Jochen Liedtke認為系統的設計應該以高效能為目的出發，如此才能做出實際上可以使用的東西。他最初以Intel i386的組合語言實作出系統後，馬上引起電腦工業圈的熱烈關注。自從L4問世以來，L4已經被發展成獨立於平台之上，並且改善安全性(security)、獨立性(isolation)、以及容錯性(robustness)。
現在已經有很多版本重新實作原來L4的ABI，例如：L4Ka::Pistachio、L4/MIPS、Fiasco。因此現在L4不再指Liedtke最初實作的版本，而是指所有包含L4核心界面的μ-kernel家族。這其中有一個OKL4版本，已經在超過15億的行動裝置上使用。
作業系統架構
------------
Init Hook
----------
F9-kernel用了一個global initialization hook的技巧，這個技巧可以在任意地方定義一段要在系統初始化時執行的code。一個``init hook``會在特定的run level被呼叫，hook可以保證依據level順序呼叫，但不能保證在同一個level中呼叫的順序，下面是一個``init hook``的結構：
.. code-block:: c
/* include/init_hook.h */
typedef struct {
unsigned int level;
init_hook_t hook;
const char *hook_name;
} init_struct;
其中包含要在哪個level呼叫、要執行的code位置、名稱，宣告這個結構的方法如下：
.. code-block:: c
/* include/init_hook.h */
#define INIT_HOOK(_hook, _level) \
const init_struct _init_struct_##_hook __attribute__((section(".init_hook"))) = { \
.level = _level, \
.hook = _hook, \
.hook_name = #_hook, \
};
使用``INIT_HOOK``這個macro可以宣告一個``init_struct``，並且將這個結構放到``.init_hook`` section中，接著觀察linker script：
.. code-block:: c
/* loader/loader.ld */
SECTIONS {
.text 0x08000000:
{
KEEP(*(.isr_vector))
. = TEXT_BASE;
text_start = .;
*(.text*)
*(.rodata*)
.init_hook_start = .;
KEEP(*(.init_hook))
init_hook_end = .;
text_end = .;
} > MFlash
...
}
在``KEEP(*(.init_hook))``前後各紀錄了一個位置，``init_hook_start``會是section ``.init_hook``的開始，``init_hook_end``會是section ``.init_hook``的結束。
在F9-kernel中已經有一些地方使用到``INIT_HOOK``：
.. code-block:: c
$ grep INIT_HOOK kernel/* platform/*
kernel/kdb.c:INIT_HOOK(kdb_init, INIT_LEVEL_KERNEL);
kernel/kprobes.c:INIT_HOOK(kprobe_init, INIT_LEVEL_KERNEL);
kernel/ksym.c:INIT_HOOK(ksym_init, INIT_LEVEL_KERNEL_EARLY);
kernel/ktimer.c:INIT_HOOK(ktimer_event_init, INIT_LEVEL_KERNEL);
kernel/memory.c:INIT_HOOK(memory_init, INIT_LEVEL_KERNEL_EARLY);
kernel/sched.c:INIT_HOOK(sched_init, INIT_LEVEL_KERNEL_EARLY);
kernel/syscall.c:INIT_HOOK(syscall_init, INIT_LEVEL_KERNEL);
kernel/thread.c:INIT_HOOK(thread_init_subsys, INIT_LEVEL_KERNEL);
platform/debug_device.c:INIT_HOOK(dbg_device_init_hook, INIT_LEVEL_PLATFORM);
接著看一下``init_hook_start``跟``init_hook_end``的值，並觀察剛剛定義的``init_struct``是放在哪邊：
.. code-block:: c
$ arm-none-eabi-readelf -s f9.elf | grep "init_hook_start|init_hook_end" -E
765: 08005924 0 NOTYPE GLOBAL DEFAULT 1 init_hook_end
934: 080058b8 0 NOTYPE GLOBAL DEFAULT 1 init_hook_start
$ arm-none-eabi-objdump -d f9.elf | grep init_struct
080058b8 <_init_struct_dbg_device_init_hook>:
080058c4 <_init_struct_ktimer_event_init>:
080058d0 <_init_struct_memory_init>:
080058dc <_init_struct_sched_init>:
080058e8 <_init_struct_syscall_init>:
080058f4 <_init_struct_thread_init_subsys>:
08005900 <_init_struct_kdb_init>:
0800590c <_init_struct_kprobe_init>:
08005918 <_init_struct_ksym_init>:
可以發現``0x080058b8~0x08005924``剛好就是剛剛定義的``init_struct``內容(一個init_struct的大小是12byte，所以最後一個是0x8005918+12=0x8005924)，而且這些結構會是連續的存放在一起。剩下的就是如何執行這些code：
.. code-block:: c
/* kernel/init.c */
extern const init_struct init_hook_start[];
extern const init_struct init_hook_end[];
static unsigned int last_level = 0;
int run_init_hook(unsigned int level)
{
unsigned int max_called_level = last_level;
for (const init_struct *ptr = init_hook_start; ptr != init_hook_end; ++ptr)
if ((ptr->level > last_level) && (ptr->level <= level)) {
max_called_level = MAX(max_called_level, ptr->level);
ptr->hook();
}
last_level = max_called_level;
return last_level;
}
這段程式會從``init_hook_start``開始掃過一遍，當發現一個hook的level是大於上次呼叫``run_init_hook``而且小於等於這次要run的level時，就執行對應的hook function，並且更新最大呼叫過的level。
記憶體管理(Memory Management)
-----------------------------
與傳統L4用來建置``large system``的設計理念不同，F9將重點放在小型MCU的功耗上，因此：
* 沒有虛擬記憶體(virtual memory)與分頁(pages)
* RAM很小，但PAS(physical address space)比較大(32-bit)，包含：硬體裝置、flash、bit-band區域
* 只有8個MPU(memory protection unit)區域
記憶體管理分為三個部份：
Memory pool
一塊含有特定屬性的PAS區域(hardcoded in memmap table)
Flexible page
AS中的一塊區域，與L4不同，這邊是指MPU區域
Address page
由flexible page所組成
在Cortex-M中，MPU只支援2^n大小的區域，假設我們要建立一個96 bytes的page，我們應該要切成較小的區域，並且建立出一條包含32 byte與64 byte的fpage chain，這邊就是實作複雜的原因。
Memory pool
===========
.. code-block:: c
/* include/memory.h */
typedef struct {
memptr_t start;
memptr_t end;
uint32_t flags;
uint32_t tag;
} mempool_t;
/* Kernel permissions flags */
#define MP_KR 0x0001
#define MP_KW 0x0002
#define MP_KX 0x0004
/* Userspace permissions flags */
#define MP_UR 0x0010
#define MP_UW 0x0020
#define MP_UX 0x0040
/* Fpage type */
#define MP_NO_FPAGE 0x0000 /*! Not mappable */
#define MP_SRAM 0x0100 /*! Fpage in SRAM: granularity 1 << */
#define MP_AHB_RAM 0x0200 /*! Fpage in AHB SRAM: granularity 64 words, bit bang mappings */
#define MP_DEVICES 0x0400 /*! Fpage in AHB/APB0/AHB0: granularity 16 kB */
#define MP_MEMPOOL 0x0800 /*! Entire mempool is mapped */
/* Map memory from mempool always (for example text is mapped always because
* without it thread couldn't run)
* other fpages mapped on request because we limited in MPU resources)
*/
#define MP_MAP_ALWAYS 0x1000
typedef enum {
MPT_KERNEL_TEXT,
MPT_KERNEL_DATA,
MPT_USER_TEXT,
MPT_USER_DATA,
MPT_AVAILABLE,
MPT_DEVICES,
MPT_UNKNOWN = -1
} mempool_tag_t;
#define DECLARE_MEMPOOL(name_, start_, end_, flags_, tag_) \
{ \
.start = (memptr_t) (start_), \
.end = (memptr_t) (end_), \
.flags = flags_, \
.tag = tag_ \
}
#define DECLARE_MEMPOOL_2(name, prefix, flags, tag) \
DECLARE_MEMPOOL(name, &(prefix ## _start), &(prefix ## _end), flags, tag)
``mempool_t``定義出memory pool的結構，也就是PAS中的一個區域，因此此結構中包含：起始與結束位置、kernel與user的使用權限，還有fpage的creation rule。``DECLARE_MEMPOOL``與``DECLARE_MEMPOOL_2``用來宣告memory pool，兩者的差異在於定義start與end的位置，一個是直接賦值，一個是透過變數取值
.. code-block:: c
/* kernel/memory.c */
/**
* Memory map of MPU.
* Translated into memdesc array in KIP by memory_init
*/
static mempool_t memmap[] = {
DECLARE_MEMPOOL_2("KTEXT" , kernel_text, MP_KR | MP_KX | MP_NO_FPAGE, MPT_KERNEL_TEXT),
DECLARE_MEMPOOL_2("UTEXT" , user_text, MP_UR | MP_UX | MP_MEMPOOL | MP_MAP_ALWAYS, MPT_USER_TEXT),
DECLARE_MEMPOOL_2("KIP" , kip, MP_KR | MP_KW | MP_UR | MP_SRAM, MPT_KERNEL_DATA),
DECLARE_MEMPOOL("KDATA" , &kip_end, &kernel_data_end,MP_KR | MP_KW | MP_NO_FPAGE, MPT_KERNEL_DATA),
DECLARE_MEMPOOL_2("KBSS" , kernel_bss, MP_KR | MP_KW | MP_NO_FPAGE, MPT_KERNEL_DATA),
DECLARE_MEMPOOL_2("UDATA" , user_data, MP_UR | MP_UW | MP_MEMPOOL | MP_MAP_ALWAYS, MPT_USER_DATA),
DECLARE_MEMPOOL_2("UBSS" , user_bss, MP_UR | MP_UW | MP_MEMPOOL | MP_MAP_ALWAYS, MPT_USER_DATA),
DECLARE_MEMPOOL("MEM0" , &user_bss_end, 0x2001c000, MP_UR | MP_UW | MP_SRAM, MPT_AVAILABLE),
#ifdef CONFIG_BITMAP_BITBAND
DECLARE_MEMPOOL("KBITMAP" , &bitmap_bitband_start, &bitmap_bitband_end,MP_KR | MP_KW | MP_NO_FPAGE, MPT_KERNEL_DATA),
#else
DECLARE_MEMPOOL("KBITMAP" , &bitmap_start, &bitmap_end,MP_KR | MP_KW | MP_NO_FPAGE, MPT_KERNEL_DATA),
#endif
DECLARE_MEMPOOL("MEM1" , &kernel_ahb_end, 0x10010000,MP_UR | MP_UW | MP_AHB_RAM, MPT_AVAILABLE),
DECLARE_MEMPOOL("APB1DEV" , 0x40000000, 0x40007800,MP_UR | MP_UW | MP_DEVICES, MPT_DEVICES),
DECLARE_MEMPOOL("APB2_1DEV", 0x40010000, 0x40013400,MP_UR | MP_UW | MP_DEVICES, MPT_DEVICES),
DECLARE_MEMPOOL("APB2_2DEV", 0x40014000, 0x40014c00,MP_UR | MP_UW | MP_DEVICES, MPT_DEVICES),
DECLARE_MEMPOOL("AHB1_1DEV", 0x40020000, 0x40022400,MP_UR | MP_UW | MP_DEVICES, MPT_DEVICES),
DECLARE_MEMPOOL("AHB1_2DEV", 0x40023c00, 0x40040000,MP_UR | MP_UW | MP_DEVICES, MPT_DEVICES),
DECLARE_MEMPOOL("AHB2DEV" , 0x50000000, 0x50061000,MP_UR | MP_UW | MP_DEVICES, MPT_DEVICES),
DECLARE_MEMPOOL("AHB3DEV" , 0x60000000, 0xA0001000,MP_UR | MP_UW | MP_DEVICES, MPT_DEVICES),
};
// 如果addr落在size當中，則會將addr加上size對齊，不過不須對齊的情況應該直接return addr就好
static memptr_t addr_align(memptr_t addr, size_t size)
{
if (addr & (size - 1))
return (addr & ~(size - 1)) + size;
return (addr & ~(size - 1));
}
void memory_init()
{
int i = 0, j = 0;
uint32_t *shcsr = (uint32_t *) 0xE000ED24;
fpages_init();
ktable_init(&as_table);
mem_desc = (kip_mem_desc_t *) kip_extra;
/* Initialize mempool table in KIP */
for (i = 0; i < sizeof(memmap) / sizeof(mempool_t); ++i) {
switch (memmap[i].tag) {
case MPT_USER_DATA:
case MPT_USER_TEXT:
case MPT_DEVICES:
case MPT_AVAILABLE:
mem_desc[j].base = addr_align((memmap[i].start), CONFIG_SMALLEST_FPAGE_SIZE) | i;
mem_desc[j].size = addr_align((memmap[i].end - memmap[i].start), CONFIG_SMALLEST_FPAGE_SIZE) | memmap[i].tag;
j++;
break;
}
}
// memory_desc_ptr需要存的是從kip到mem_desc的offset
kip.memory_info.s.memory_desc_ptr = ((void *) mem_desc) - ((void *) &kip);
kip.memory_info.s.n = j;
*shcsr |= 1 << 16; /* Enable memfault */
}
INIT_HOOK(memory_init, INIT_LEVEL_KERNEL_EARLY);
``memory_init``先初始化``fpages``以及``as_table``，接著將``mempool table``的填入KIP中。``0xE000ED24``在ARM Cortex-M4中是System Handler Control and State Register(SHCSR)，最後enable memfault exception。
Flexible pages(fpage)
======================
.. code-block:: c
/* include/fpage.h */
struct fpage {
struct fpage *as_next;
struct fpage *map_next;
struct fpage *mpu_next;
union {
struct {
uint32_t base;
uint32_t mpid : 6;
uint32_t flags : 6;
uint32_t shift : 16;
uint32_t rwx : 4;
} fpage;
uint32_t raw[2];
};
};
typedef struct fpage fpage_t;
一個fpage包含：base address、memory pool id、flags、size、permission，
.. code-block:: c
/* kernel/fpage.c */
static int fp_addr_log2(memptr_t addr)
{
int shift = 0;
while ((addr <<= 1) != 0)
++shift;
return 31 - shift;
}
static fpage_t *create_fpage(memptr_t base, size_t shift, int mpid)
{
fpage_t *fpage = (fpage_t *) ktable_alloc(&fpage_table);
assert(fpage != NULL);
fpage->as_next = NULL;
fpage->map_next = fpage; /* That is first fpage in mapping */
fpage->mpu_next = NULL;
fpage->fpage.mpid = mpid;
fpage->fpage.flags = 0;
fpage->fpage.rwx = MP_USER_PERM(mempool_getbyid(mpid)->flags);
fpage->fpage.base = base;
fpage->fpage.shift = shift;
if (mempool_getbyid(mpid)->flags & MP_MAP_ALWAYS)
fpage->fpage.flags |= FPAGE_ALWAYS;
return fpage;
}
``create_fpage``用來建立並初始化一個新的fpage，首先先在``fpage_table``中要一塊新的空間，接著依據給予的參數(mpid、size、flags)進行設定。
.. code-block:: c
static void create_fpage_chain(memptr_t base, size_t size, int mpid, fpage_t **pfirst, fpage_t **plast)
{
int shift, sshift, bshift;
fpage_t *fpage = NULL;
while (size) {
/* Select least of log2(base), log2(size). Needed to make regions with correct align */
bshift = fp_addr_log2(base);
sshift = fp_addr_log2(size);
shift = ((1 << bshift) > size) ? sshift : bshift;
if (!*pfirst) {
/* Create first page */
fpage = create_fpage(base, shift, mpid);
*pfirst = fpage;
*plast = fpage;
} else {
/* Build chain */
fpage->as_next = create_fpage(base, shift, mpid);
fpage = fpage->as_next;
*plast = fpage;
}
size -= (1 << shift);
base += (1 << shift);
}
}
``create_fpage_chain``會根據base位置以及大小，建立一條鍊結，如果原來已經有鍊結存在，則會將新產生的fpage鍊接在元有的鍊結上；如果沒有就新建一條鍊結。
.. code-block:: c
int assign_fpages_ext(int mpid, as_t *as, memptr_t base, size_t size, fpage_t **pfirst, fpage_t **plast)
{
fpage_t **fp;
memptr_t end;
if (size <= 0)
return -1;
/* if mpid is unknown, search using base addr */
if (mpid == -1) {
if ((mpid = mempool_search(base, size)) == -1) {
/* Cannot find appropriate mempool, return error */
return -1;
}
}
end = base + size;
if (as) {
/* find unmapped space */
fp = &as->first;
while (base < end && *fp) {
if (base < FPAGE_BASE(*fp)) {
fpage_t *first = NULL, *last = NULL;
size = (end < FPAGE_BASE(*fp) ? end : FPAGE_BASE(*fp)) - base;
create_fpage_chain(mempool_align(mpid, base),
mempool_align(mpid, size),
mpid, &first, &last);
last->as_next = *fp;
*fp = first;
fp = &last->as_next;
if (!*pfirst)
*pfirst = first;
*plast = last;
base = FPAGE_END(*fp);
} else if (base < FPAGE_END(*fp)) {
if (!*pfirst)
*pfirst = *fp;
*plast = *fp;
base = FPAGE_END(*fp);
}
fp = &(*fp)->as_next;
}
if (base < end) {
fpage_t *first = NULL, *last = NULL;
size = end - base;
create_fpage_chain(mempool_align(mpid, base),
mempool_align(mpid, size),
mpid, &first, &last);
*fp = first;
if (!*pfirst)
*pfirst = first;
*plast = last;
}
} else {
create_fpage_chain(mempool_align(mpid, base),
mempool_align(mpid, size),
mpid, pfirst, plast);
}
return 0;
}
int assign_fpages(as_t *as, memptr_t base, size_t size)
{
fpage_t *first = NULL, *last = NULL;
return assign_fpages_ext(-1, as, base, size, &first, &last);
}
Address space(AS)
==================
.. code-block:: c
/* include/memory.h */
typedef struct {
uint32_t as_spaceid; /*! Space Identifier */
struct fpage *first; /*! head of fpage list */
struct fpage *mpu_first; /*! head of MPU fpage list */
struct fpage *mpu_stack_first; /*! head of MPU stack fpage list */
uint32_t shared; /*! shared user number */
} as_t;
.. code-block:: c
/* kernel/memory.c */
void as_map_user(as_t *as)
{
int i;
for (i = 0; i < sizeof(memmap) / sizeof(mempool_t); ++i) {
switch (memmap[i].tag) {
case MPT_USER_DATA:
case MPT_USER_TEXT:
/* Create fpages only for user text and user data */
assign_fpages(as, memmap[i].start, (memmap[i].end - memmap[i].start));
}
}
}
替``user text``以及``user data``建立fpage，並且映射到``as``。
硬體驅動原理
------------
Flash Patch and Breakpoint Unit (FPB), ARMv7-M Debug Architecture
==================================================================
MPU (Memory Protection Unit)
=============================
Overview
#########
在multitasking的系統中，必須確保不同task的操作不會互相干擾，而避免系統資源或是其他任務的資料被非法存取的機制就叫做保護(protection)。控制存取系統資源的方法有兩種：無硬體保護與有硬體保護，無硬體保護的系統就單純依靠軟體保護系統資源；有硬體保護的則是會由硬體與軟體一起進行保護。至於實際上的控制系統要使用哪種方法，取決於處理器的性能以及控制系統的需求。
在無保護的系統中，沒有專門處理週邊設備以及記憶體的硬體，在這類的系統中，為了避免不同的task有互相干擾的情況，必須有協調的機制，但如果其中有任務沒有遵守存取限制，則這個機制就可能失敗。下面是一個失敗的例子：當讀寫一個通訊用的序列阜(serial port)暫存器時，如果有一個任務正在使用序列阜，但他沒辦法阻止其他任務也使用相同的序列阜。所以，要順利的使用序列阜，就必須設計一個存取該序列阜的系統呼叫。但這些未經授權的任務在使用系統呼叫時，很容易就會破壞序列阜的通訊。
反過來說，在有保護的系統中，會有專門檢查並限制存取系統資源的硬體，它可以保證資源的所有權，任務必須遵守一組由操作環境定義的規則，而這規則會由硬體來維護，從硬體等級上授予監看和控制資源的特殊權限。受保護的系統可以防止一個任務使用到其他任務的資源，硬體保護會比使用軟體協調的辦法有更好的保護。
ARM的很多處理器都配有主動保護系統資源的硬體：memory protection unit(MPU)以及memory management unit(MMU)兩種，帶有MPU的處理器可以對一些由軟體定義的區域進行硬體保護；帶有MMU的處理器則是除了提供硬體保護外，還加上了虛擬記憶體(virtual memory)的功能。
在受保護的系統中，主要有兩種資源要監看：記憶體與週邊設備，因為ARM的週邊設備通常會被映射到記憶體中，因此MPU就可以用同樣的方法保護這兩種資源。
ARM Cortex-M4 Optional Memory Protection Unit
##############################################
MPU會將memory map切成幾塊區域，並定義每一個區域(region)的位置、大小、存取權限還有記憶體屬性(attributes)
* 每一個區域可以有獨立的屬性設定
* 區域可以overlapping
* 可以export記憶體屬性給系統
|
| 記憶體屬性會影響區域的記憶體存取，Cortex-M4定義了：
* 八個獨立的記憶體區域，0-7
* 一個背景區域(background region)
* 當overlap發生時，存取權限會以編號較高的區域屬性為準。例如區域7與任何其他的區域發生重疊時，都會以區域7的屬性為主
重疊的區域在賦予存取權限時可以有比較大的彈性，例如有一個小型的嵌入式系統，總共有256KB的記憶體，而起始位置在0x00000000，其中有一塊是privileged的系統區域32KB，不能被使用者存取，並且從0x00000000開始放起，剩下的記憶體則是給使用者。這個系統使用兩個區域：256KB的user區域跟32KB的privileged區域，因為privileged區域的優先度比較大，所以privileged區域使用編號1，user區域使用編號0。
.. image:: /embedded/f9-kernel/overlapping.png
* 背景區域與預設的memory map有相同的屬性，但是只能被privileged的軟體存取
重疊區域的另一個用處在背景區域－用來替一大塊記憶體空間分配相同屬性的低優先度區域，其他較高優先度的區域就能改變背景區域中的某一塊屬性。背景區域可以用來保護一些睡眠狀態的記憶體，使其不會被非法存取，而此時由另一個處於活躍狀態的記憶體就能被使用。
例如有一個嵌入式系統定義了一個較大的privileged區域，接著讓一些較小的unprivileged區域與這個privileged區域的部份重疊，這個較小區域可以在背景區域的不同位置，代表不同的用戶空間(user space)，當系統將這個較小的區域從一個位置移到另一個位置時，之前被覆蓋的空間就會在由背景區域進行保護。這個使用者區域(user region)就像一個window，允許存取背景區域的不同部份，但只有用戶等級(user-level)的屬性。
下圖是一個簡單的3-task保護架構，區域3定義了active task的保護屬性，而背景區域0則負責保護其他睡眠狀態的任務資源。
.. image:: /embedded/f9-kernel/background_region.png
* 指令存取(instruction access)與資料存取(data access)是使用相同的區域設定
* 當程式要存取受到MPU保護的區域時，會產生``MemManage fault(fault exception)``。在作業系統的環境中，kernel可以在程式執行時動態更新MPU區域。通常一個嵌入式OS會使用MPU作為memory protection
Implementation
###############
mpu的實作是依賴於硬體的，所以程式碼會放在``platform``底下
.. code-block:: c
/* include/platform/mpu.h */
#define MPU_BASE_ADDR 0xE000ED9C
#define MPU_ATTR_ADDR 0xE000EDA0
#define MPU_CTRL_ADDR 0xE000ED94
#define MPU_RNR_ADDR 0xE000ED98
#define MPU_REGION_MASK 0xFFFFFFE0
這邊先定義好mpu暫存器的位置，這些位置可以從arm的手冊中找到。至於``MPU_REGION_MASK``是用來取得區域用的遮罩值。
* MPU_BASE(`MPU Region Base Address Register<http://infocenter.arm.com/help/topic/com.arm.doc.dui0553a/Cihigffb.html>`_)
- .. image:: /embedded/f9-kernel/mpu_base.png
- 定義由MPU_RNR指定的MPU區域的base位置，並且更新MPU_RNR中的值，N值是在MPU_RASR中設定的size大小。
- ADDR - 區域的base位置
- VALID
+ 0 - MPU_RNR不會改變，處理器會更新由MPU_RNR指定的MPU區域的base位置
+ 1 - 將MPU_RNR更新成REGION，更新由MPU_RNR指定的MPU區域的base位置
+ 也就是說，設定0的話會更新原來的MPU_RNR區域的base，1的話就是先切換MPU_RNR區域在更新base
- REGION - 區域的index
* MPU_ATTR(`MPU Region Attribute and Size Register<http://infocenter.arm.com/help/topic/com.arm.doc.dui0553a/Cihegaib.html>`_)
- .. image:: /embedded/f9-kernel/mpu_attr.png
- 定義由MPU_RNR指定的MPU區域的屬性還有大小，並且enable區域與子區域
- XN
+ 0 - enable instruction fetch
+ 1 - disable instruction fetch
- AP - 存取權限
- TEX, C, B - 記憶體存取屬性
- S - shareable
- SRD
+ 0 - 對應子區域enable
+ 1 - 對應子區域disable
+ 區域在大小在128byte以下不能使用子區域
- SIZE - MPU區域的大小
- ENABLE - 區域enable
* MPU_CTRL(`MPU Control Register<http://infocenter.arm.com/help/topic/com.arm.doc.dui0553a/Cihjddef.html>`_)
- .. image:: /embedded/f9-kernel/mpu_ctrl.png
- PRIVDEFENA
+ 0 - disable預設的memory map，如果有存取到沒有被enable的區域，會造成錯誤
+ 1 - enable預設的memory map，background區域給priviledged軟體使用
- HFNMIENA - 在hard fault、NMI、FAULTMASK handler時要不要啟動MPU
+ 0 - disable
+ 1 - enable
- ENABLE
+ 0 - disable mpu
+ 1 - enable mpu
.. code-block:: c
/* platform/stm32f4/mpu.c */
void mpu_setup_region(int n, fpage_t *fp)
{
static uint32_t *mpu_base = (uint32_t *) MPU_BASE_ADDR;
static uint32_t *mpu_attr = (uint32_t *) MPU_ATTR_ADDR;
if (fp) {
*mpu_base = (FPAGE_BASE(fp) & MPU_REGION_MASK) | 0x10 | (n & 0xF);
*mpu_attr = ((mempool_getbyid(fp->fpage.mpid)->flags & MP_UX) ?
0 :
(1 << 28)) | /* XN bit */
(0x3 << 24) /* Full access */ |
((fp->fpage.shift - 1) << 1) /* Region */ |
1 /* Enable */;
} else {
/* Clean MPU region */
*mpu_base = 0x10 | (n & 0xF);
*mpu_attr = 0;
}
}
* ``*mpu_base = (FPAGE_BASE(fp) & MPU_REGION_MASK) | 0x10 | (n & 0xF)``，先取得fpage base再遮罩下去取得前27位，接著設定``VALID``跟``REGION``
* MPU_ATTR設定：
- MP_UX(userspace execute)
- 權限(all)
- 區域大小
- enable
.. code-block:: c
/* platform/stm32f4/mpu.c */
void mpu_enable(mpu_state_t i)
{
static uint32_t *mpu_ctrl = (uint32_t*) MPU_CTRL_ADDR;
*mpu_ctrl = i | MPU_PRIVDEFENA;
}
依據參數設定``MPU_CTRL``狀態，並且開啟``PRIVDEFENA``
.. code-block:: c
/* platform/stm32f4/mpu.c */
int addr_in_mpu(uint32_t addr)
{
static uint32_t *mpu_rnr = (uint32_t *) MPU_RNR_ADDR;
static uint32_t *mpu_base = (uint32_t *) MPU_BASE_ADDR;
static uint32_t *mpu_attr = (uint32_t *) MPU_ATTR_ADDR;
int i;
for (i = 0; i < 8; ++i) {
*mpu_rnr = i;
if (*mpu_attr & 0x1) {
uint32_t base = *mpu_base & MPU_REGION_MASK;
uint32_t size = 1 << (((*mpu_attr >> 1) & 0x1F) + 1);
if (addr >= base && addr < base + size)
return 1;
}
}
return 0;
}
掃過全部的mpu區域，並檢查給予的地址是不是在enable的區域內。
Basic Kernel Library
----------------------
KTable
=========================================
ktable是一套快速的物件管理機制，結構如下：
.. code-block:: c
struct ktable {
char *tname;
bitmap_ptr_t bitmap;
ptr_t data;
size_t num;
size_t size;
};
typedef struct ktable ktable_t;
* tname ： table名稱
* `bitmap<#bitmap>`_ ： 紀錄table的使用情況
* data ： 實際存放資料的區域
* num ： 總共有幾個區塊
* size ： 每個區塊的大小
接著是宣告ktable的方法，給予要存放在ktable中的型態、ktable的名字、以及需要的大小：
.. code-block:: c
// 宣告一個ktable
// $ arm-none-eabi-readelf f9.elf -s | grep fpage_table
// 263: 10000000 32 OBJECT LOCAL DEFAULT 8 kt_fpage_table_bitmap
// 265: 2000c4e0 6144 OBJECT LOCAL DEFAULT 4 kt_fpage_table_data
#define DECLARE_KTABLE(type, name, num_) \
DECLARE_BITMAP(kt_ ## name ## _bitmap, num_); \
static __KTABLE type kt_ ## name ## _data[num_]; \
ktable_t name = { \
.tname = #name, \
.bitmap = kt_ ## name ## _bitmap, \
.data = (ptr_t) kt_ ## name ## _data, \
.num = num_, .size = sizeof(type) \
}
ktable有提供下列的API可供使用：
.. code-block:: c
// 將kt中的bitmap全部設為0
void ktable_init(ktable_t *kt);
// 檢查第i個元素是否已經被配置
int ktable_is_allocated(ktable_t *kt, int i);
// 配置第i個元素，回傳元素的位置
void *ktable_alloc_id(ktable_t *kt, int i);
// 配置到第一個free的元素，回傳元素的位置
void *ktable_alloc(ktable_t *kt);
// 釋放元素
void ktable_free(ktable_t *kt, void *element);
// 取得該元素位在ktable內的id
uint32_t ktable_getid(ktable_t *kt, void *element);
.. image:: /embedded/f9-kernel/ktable.png
Bitmap
#######
bit array(bitmap, bitset, bit string, bit vector)是一種緊湊儲存位元的陣列結構，可以用來實作簡單的set結構。在硬體上操作bit-level時，bitmap是一種很有效的方法，一個典型的bitmap會儲存kw個位元，w代表一個單位需要w個位元(byte、word)，k則是一個非負的整數，如果w無法被要儲存的位元整除，則有些空間會因為內部片段被浪費。
**定義**
bitmap會從某一個domain mapping到一個集合{0, 1}，這個值可以代表valid/invalid、dark/light等等，重點在只會有兩個可能的值，所以可以被存在一個位元中。
**基本操作**
雖然大部分的機器無法取得或操作記憶體中的單一位元，但是可以透過bitwise操作一個word進而改變單一位元的資料：
* OR可以用來set一個位元為1：11101010 OR 00000100 = 11101110(set 3rd bit 1)
* AND可以用來set一個位元為0：11101010 AND 11111101 = 11101000(set 2nd bit 0)
* AND可以用來判斷某一個位元是否為1：11101010 AND 00000001 = 0(check 1st bit is 1)
* XOR可以用來toggle一個位元：11101010 XOR 00000100 = 11101110(toggle 3rd bit)
* NOT用來invert：NOT 11101010 = 00010101
只要n/w個bitwise operation用來算出兩個相同大小bitmap的union、intersection、difference、complement
.. code-block:: c
for i from 0 to n/w-1
complement[i] := not a[i]
union[i] := a[i] or b[i]
intersection[i] := a[i] and b[i]
difference[i] := a[i] and (not b[i])
如果要iterate bitmap中的所有bit，只要用一個雙層的迴圈就能有效率的掃完，只需要n/w次的memory access
.. code-block:: c
for i from 0 to n/w-1
index := 0 // if needed
word := a[i]
for b from 0 to w-1
value := word and 1 ≠ 0
word := word shift right 1
// do something with value
index := index + 1 // if needed
**Bit-banding**
bit-banding會將一塊較大記憶體中的word對應到一個較小的bit-band區域中的單一bit，例如寫到其中一個alias，可以set或是clear一個bit-band區域中對應的bit。
這使得bit-band區域中每一個獨立的bit都可以透過LDR指令搭配一個word-aligned的地址進行存取，也能讓每一個獨立bit被直接toggle，而不須經過read-modify-write的指令操作。
處理器的memory map包含了兩塊bit-band區域，分別是在SRAM以及Peripheral中最低位的1MB。
System bus interface包含了一個bit-band的存取邏輯：
* remap一個bit-band alias到bit-band區域
* 讀取時，會將requested bit放在回傳資料的Least Significant Bit中
* 寫入時，會將read-modify-write轉換成一個atomic的動作
* 處理器在bit-band操作中不會stall，除非試圖在bit-band操作中存取system bus
記憶體中有兩塊32MB的alias對應到兩塊1MB的bit-band區域：
* 32MB可存取的SRAM alias區域對應到1MB的bit-band SRAM區域
* 32MB可存取的peripheral alias區域對應到1MB的bit-band peripheral區域
有一個mapping公式可以將alias轉換成對應的bit-band位置
.. code-block:: c
bit_word_offset = (byte_offset x 32) + (bit_number × 4)
bit_word_addr = bit_band_base + bit_word_offset
* bit_word_offset是target bit在bit-band區域中的位置
* bit_word_addr是target bit在alias中對應的地址
* bit_band_base是alias區域的起始位置
* byte_offset是target bit在bit-band區域中的第幾個byte
* bit_number是target bit的bit位置，從0到7
範例如下：
* The alias word at 0x23FFFFE0 maps to bit [0] of the bit-band byte at 0x200FFFFF: 0x23FFFFE0 = 0x22000000 + (0xFFFFF*32) + 0*4.
* The alias word at 0x23FFFFFC maps to bit [7] of the bit-band byte at 0x200FFFFF: 0x23FFFFFC = 0x22000000 + (0xFFFFF*32) + 7*4.
* The alias word at 0x22000000 maps to bit [0] of the bit-band byte at 0x20000000: 0x22000000 = 0x22000000 + (0*32) + 0*4.
* The alias word at 0x2200001C maps to bit [7] of the bit-band byte at 0x20000000: 0x2200001C = 0x22000000 + (0*32) + 7*4.
* bit-band[0x20000000] <-> alias[0x22000000~0x2200001C](8格)
* bit-band 0x20000000[0]-0x20000000[1]-0x20000000[2]-0x20000000[3]-0x20000000[4]
* alias 0x22000000 -0x20000004 -0x20000008 -0x2000000C -0x20000010
.. image:: /embedded/f9-kernel/bitmap.png
**直接存取alias**
直接寫一個word到alias上與target bit的read-modify-write動作有同樣效果，Bit[0]代表要寫入target bit的值，Bit[31:1]沒有用處，所以寫入`0x01`跟`0xFF`是一樣的，都會寫入1到target bit；寫入`0x00`跟`0x0E`是一樣的，都會寫入0到target bit。
從alias讀取一個word會得到`0x01`或是`0x00`，Bit[31:1]會為0
**F9-kernel(Bitmap)**
Bit-band bitmap被放在AHB SRAM中，使用BitBang地址存取bit，使用bitmap cursor(type bitmap_cusor_t)iterate bitmap。
.. code-block:: c
/* include/lib/bitmap.h */
// 宣告一塊bitmap
#define DECLARE_BITMAP(name, size) \
static __BITMAP uint32_t name [ALIGNED(size, BITMAP_ALIGN)];
// ADDR_BITBAND指的是target bit所在byte對應到的align，還沒加上bit_number
// ((ptr_t) addr) & 0xFFFFF) 可以抓出addr在bit-band區域中的第幾個byte
#define BITBAND_ADDR_SHIFT 5
#define ADDR_BITBAND(addr) \
(bitmap_cursor_t) (0x22000000 + \
((((ptr_t) addr) & 0xFFFFF) << BITBAND_ADDR_SHIFT))
#define BIT_SHIFT 2
// bitmap_cursor是加上bit_number後的值，也就是target bit正確的align
#define bitmap_cursor(bitmap, bit) \
((ADDR_BITBAND(bitmap) + (bit << BIT_SHIFT)))
// bitmap_cursor_id可以取得bit_number
// ((1 << (BITBAND_ADDR_SHIFT + BIT_SHIFT)) - 1) 取得 0b1111111 也就是七位的mask，與cursor進行完AND操作並右移兩位後，會留下兩位的byte_offset以 及bit_number，也就是BBXXX(B:byte_offset、X:bit_number)
#define bitmap_cursor_id(cursor) \
(((ptr_t) cursor & ((1 << (BITBAND_ADDR_SHIFT + BIT_SHIFT)) - 1)) >> BIT_SHIFT)
// bitmap_cursor_goto_next 可以把cursor往前推一格(+= 4)
#define bitmap_cursor_goto_next(cursor) \
cursor += 1 << BIT_SHIFT
// for_each_in_bitmap 可以從某一個bitmap的start開始訪問完一塊bitmap
#define for_each_in_bitmap(cursor, bitmap, size, start) \
for (cursor = bitmap_cursor(bitmap, start); \
bitmap_cursor_id(cursor) < size; \
bitmap_cursor_goto_next(cursor))
* bitmap_set_bit(bitmap_cursor_t cursor) - 將cursor設為1
* bitmap_clear_bit(bitmap_cursor_t cursor) - 將cursor設為0
* bitmap_get_bit(bitmap_cursor_t cursor) - 取得cursor值
* bitmap_test_and_set_bit(bitmap_cursor_t cursor) - 測試cursor是否被使用並設為1
IPC
--------
F9的IPC 性質為同步傳送，舉個同步和非同步的例子:
* 同步 - 當A 要傳送資料給B 時候，會先檢查B 是否已經準備好，如果是的話就直接傳送，不是的話就等待對方。傳送過程中不會經過其他buffer，而是直接傳給B。
* 非同步 - 當A要傳送資料給B 時候，會把資料丟進系統IPC準備好的queue/buffer中; 當B 要接收資料的時候，會從queue/buffer中尋找。過程中需要係統IPC的buffer/queue做為中轉。
IPC register有兩種- message register & buffer register
* MRs有16個
* BR只有8個
Message Register
=================
共有 16 個，其中 0 ～ 7 是 R4 ～ R11，其他的為虛擬Registers是 UTCB中的 MR[0～8]。
.. code-block:: c
//user/include/l4/platform/vregs.h
register L4_Word32_t __L4_MR0 asm ("r4");
register L4_Word32_t __L4_MR1 asm ("r5");
register L4_Word32_t __L4_MR2 asm ("r6");
register L4_Word32_t __L4_MR3 asm ("r7");
register L4_Word32_t __L4_MR4 asm ("r8");
register L4_Word32_t __L4_MR5 asm ("r9");
register L4_Word32_t __L4_MR6 asm ("r10");
register L4_Word32_t __L4_MR7 asm ("r11");
//include/ipc.h
static uint32_t ipc_read_mr(tcb_t *from, int i)
{
// 可以發現 8以下的mr屬於ctx裡的regs
if (i >= 8)
return from->utcb->mr[i - 8];
return from->ctx.regs[i];
}
每個MR的值只能被使用一次，一次之後讀取的話會出現undefined結果。
MR 內容可包含
* **Untyped word**
* Typed item
- MapItem
- GrantItem
- CtrlXferItem (目前未完成）
- StringItem （目前未完成）
一次利用MR傳送的Message可以分為三塊區域：
Message Tag
位置固定在MR[0]。
Untyped Word
位置在MR[1～u]，u表示Untyped word的數量。
Typed Word
位置在MR[u+1～u+t]，t表示Typed word的數量。
Message Tag的作用是描述本次message的内容。
.. image:: /embedded/f9-kernel/MR0.jpg
* u : untyped words的數量
* t : words裡面有typed item的數量
* label : 使用者自定 opcode
* 0 : 保留
* p : 擴展性
此外，Message Tag也是接收内容的描述。
.. image:: /embedded/f9-kernel/resultmr0.jpg
* u : 收到的Untyped words數量
* t : 收到的Typed items數量
* E : 是否有發生錯誤，從UTCB中查看ErrorCode
* X : 是不是從其他CPU送來的message
* r : message是否有被重新導向
* p : 發送者使用propagation,可以從UTCB中找出真正的發送者
.. code-block:: c
//include/l4/ipc.h
typedef union {
struct {
/* Number of words */
uint32_t n_untyped : 6;
uint32_t n_typed : 6;
uint32_t prop : 1;
uint32_t reserved : 3; /* Type of operation */
uint16_t label;
} s;
uint32_t raw;
} ipc_msg_tag_t;
MapItem
========
Map的動作是透過將要map的fpage組成部分message傳送給Mappee。
Fpage細節由兩個words來組成：
.. image:: /embedded/f9-kernel/MapItemMR.jpg
* r w x : 權限
* snd base ： 在L4的文件中，snd base在snd fpage大於/小於接收者能接收的窗口中扮演不同的角色。而在F9的程式碼看起来，snd base是要map的目標位置，而snd fpage是size。
GrantItem
==========
| 如同Map, Grant也是透過傳送message完成。
| Fpage細節也是如同MapItem的兩個words，但其中100C部分由 101C 取代。
效能表現
--------
參考資料
--------
* http://www.slideshare.net/jserv/f9-microkernel
* http://www.slideshare.net/vh21/2014-0109f9kernelktimer
* `ARM System Developer's Guide : Designing and Optimizing System Software<http://eee.guc.edu.eg/Courses/Electronics/ELCT912%20Advanced%20Embedded%20Systems/Lectures/ARM%20System%20Developer's%20Guide.pdf>`_
* Bitmap
- http://en.wikipedia.org/wiki/Bit_array
- `ARM Information Center(2.5. Bit-banding)<http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dai0179b/CHDJHIDF.html>`_
* Init Hook
- http://kunyichen.wordpress.com/2014/04/18/f9-kernel-%E4%B9%8B-init_hook
- https://github.com/f9micro/f9-kernel/blob/master/Documentation/init-hooks.txt
* MPU
- `ARM Information Center(4.5. Optional Memory Protection Unit)<hhttp://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0553a/Cihjddef.html>`_
* Overview
- http://www.ertos.nicta.com.au/research/l4/microkernels.pml
- `Wikipedia(Microkernel)<http://en.wikipedia.org/wiki/Microkernel>`_
- `Wikipedia(L4_microkernel)<http://en.wikipedia.org/wiki/L4_microkernel>`_
*IPC
- http://www.l4ka.org/l4ka/l4-x2-r7.pdf
