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

版本 5776d4668166e13d2e25f63ce8379540dafd5f08

embedded/f9-kernel

Changes from 5776d4668166e13d2e25f63ce8379540dafd5f08 to 58174d69841b212fb922b7687b12320ec7e68747

---
title: F9 microkernel
categories: embedded, arm, stm32, stm32f429
toc: no
...

----
組員
目錄
----



1. `組員與共筆<#組員與共筆>`_

2. `作業系統架構<#作業系統架構>`_

3. `記憶體管理(Memory Management)<#記憶體管理(Memory Management)>`_

    3.1 `Memory pool<#Memory pool>`_

    3.2 `Flexible pages(fpage)<#Flexible pages(fpage)>`_

    3.3 `Address space(AS)<#Address space(AS)>`_

4. `硬體驅動原理<#硬體驅動原理>`_

5. `Basic Kernel Library<#Basic Kernel Library>`_

    5.1 `KTable<#KTable>`_

        5.1.1 `Bitmap<#Bitmap>`_

組員與共筆
----------

* 廖健富 / Rampant1018
* 鄒宗延 / slpbaby
* 詹凱傑 / bpotatog
                                                       
共筆
---
* `Hackpad<https://hackpad.com/F9-Kernel-Note-UnUXDVd9Zv2>`_
* 共筆 / `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)

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

效能表現
--------

參考資料
--------
* 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