版本 5d1d48a42cfcaf7d78a7df27375776b1c047ee8e

F9 microkernel

組員與共筆
作業系統架構
Init Hook
記憶體管理(Memory Management)
Memory pool
Flexible pages(fpage)
Address space(AS)
- 硬體驅動原理
Flash Patch and Breakpoint Unit (FPB), ARMv7-M Debug Architecture
MPU (Memory Protection Unit)
- Basic Kernel Library
KTable
- 效能表現
- 參考資料

組員與共筆

廖健富 / 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_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)

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 + (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]沒有用處，所以寫入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

效能表現

參考資料

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
MPU
- ARM Information Center(4.5. Optional Memory Protection Unit)<hhttp://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0553a/Cihjddef.html>_