分享到plurk 分享到twitter 分享到facebook

版本 1d75adc5f4186d0e496e827639ffec6e67c7dc7f

F9 microkernel

組員
* 廖健富 / Rampant1018 * 鄒宗延 / slpbaby * 詹凱傑 / bpotatog 共筆
  • Hackpad<https://hackpad.com/F9-Kernel-Note-UnUXDVd9Zv2>_

作業系統架構

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_startinit_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。

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 + (0xFFFFF32) + 04.
  • The alias word at 0x23FFFFFC maps to bit [7] of the bit-band byte at 0x200FFFFF: 0x23FFFFFC = 0x22000000 + (0xFFFFF32) + 74.
  • The alias word at 0x22000000 maps to bit [0] of the bit-band byte at 0x20000000: 0x22000000 = 0x22000000 + (032) + 04.
  • The alias word at 0x2200001C maps to bit [7] of the bit-band byte at 0x20000000: 0x2200001C = 0x22000000 + (032) + 74.
  • bit-band[0x20000000] <-> alias0x22000000~0x2200001C
  • 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]沒有用處,所以寫入0x010xFF是一樣的,都會寫入1到target bit;寫入0x000x0E是一樣的,都會寫入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

硬體驅動原理

  • Flash Patch and Breakpoint Unit (FPB), ARMv7-M Debug Architecture
  • MPU (Memory Protection Unit)

效能表現

參考資料

  • http://www.slideshare.net/jserv/f9-microkernel
  • http://www.slideshare.net/vh21/2014-0109f9kernelktimer
  • 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