【作者：张佩】【原始链接：www.yiiyee.cn/blog】
Little Kernel是一个微型内核，某种意义上，可以被定义为微内核。当下声势大张的谷歌Fuchsia OS的微内核系统就是从它演进而来的。它更为一般的作用，是在安卓设备中，作为一个典型的boot loader并启动安卓OS。相较于更通用的arm平台上的u-boot，它当然更加地简单。所以如果不需要boot loader中实现复杂的功能，特别是不需要驱动复杂的IO设备的话，little kernel是非常合适的。
当然，并不是说Little Kernel（简称LK）没有IO支持。它对于基本的IO设备还是有接口层面的支持的。比如串口、GPIO、基于frame buffer的图形显示设备，以及更高级的设备比如磁盘设备、USB、网络等，甚至virtio设备。但仅限于接口定义，却缺少具体的设备支持。所以新平台的设备驱动开发是一个巨大任务。
在这个文档中，我带领大家一起走读一下LK的核心代码。
LK内核代码走读
这部分我带领大家走读一下LK内核部分的代码。因为代码很简单，所以走读一遍并不费事。和Linux内核相比，走读LK的内核如同在电视上看别人爬山一样，所费精力与实际爬山之人，实有天壤之别。但如鲁迅说的，我的双脚虽不能如愿地周游世界，但通过眼睛却能部分地实现它，观看风光纪录片便如部分地身临其境地领略了那些风光，也能增广见闻的。所以LK虽微，分析它亦不费事，但学习它也能达到增广见闻的目的，部分地达到学习内核实现的目的。
LK官方有一篇和小的文档介绍内核API，然太简。参考。下面我带领大家分别地看一下LK的内存管理、任务管理和同步机制，这三个主要部分的实现逻辑。
内存管理（novm）
如果硬件平台没有保护模式，运行其上的内核系统就只能直接地使用物理地址，在lk中，这种内存模式被称为novm——no virtual memory的意思，而实现它的模块也称为novm模块。
由于只要管理单一的地址空间，novm模块通过简单的两级建制来管理内存。第一级建制为内存arena——内存区域，表示一段连续的物理内存；第二级建制是page——内存页。
内存arena是很有限的，可以分别地根据arena的特性进行命名，这是一个可爱的地方。比如一个默认的arena被称为“main”。自古以来，命名权都是一种重要的权力，它是塑造集体意识形态的重要手段。比如“main”让我们联想到它应该是要被日常所主要使用的内存。
由于novm管理的内存arena是有限的，所以在arena对象的管理上，它通过一个全局数组来实现的：struct novm_arena arena[NOVM_MAX_ARENAS]。这个NOVM_MAX_ARENAS默认定义为1，但在平台适配的时候，可以通过设置编译命令来配置之。
介绍了如上的内容之后，回来看novm模块对外提供的功能接口，亦即内存管理接口——内存申请和释放。从其参数可看到，这两个接口函数都是以arena加page的方式来定位内存的。
void* novm_alloc_pages(size_t pages, uint32_t arena_bitmap);
void novm_free_pages(void* address, size_t pages);
申请函数的arena_bitmap参数是用来选择内存arena的，申请者期望从第一个arena中申请内存，此bitmap的bit 0就应设置为1。
novm还实现了简单的内存页的管理，这样在申请内存页的时候，能相对较快地找到合适的连续空闲页。novm为每个page定义一个状态位，0表示空闲，1表示使用中。每个arena结构体中都有一个变量用于此目的：map。本arena的第一个page由map的第一个bit表示使用状态，第二个page由其第二个bit表示，以此类推下去。这样对于页的申请和释放，就转换为map位的查询和设置操作了。
在哪里存放map变量呢？可以专门划出一个内存区域作此用。具体实现中，novm采用将本arena的前面的若干page专门开辟出来作为map之用。举个例子：如果arena的大小是128MB内存，页大小为4KB，则合计为：128×1024 X 1024 / 4096 = 32K 个page，对应的map大小当为32k/8 = 4KB，亦即1个page。这样需要占用这个arena的前1个page作为它的map区域，同时设置此page的第一个bit为1（使用状态），这样申请内存的时候，就不会将第一个page分配出去了。
内核命令
novm模块提供了一个亦名为‘novm’的内核命令，通过它可以获取novm模块本身以及它所管理的物理资源的信息。参数info可以列印出内存arena全局数组所代表的所有成员的信息。
内存管理（VM）
lk的vm模块，是在有虚拟内存能力的硬件平台上，对于内存资源的管理模块。无vm支持的平台是贫穷的家庭，关门闭户自己过日子；有vm支持的平台，是富裕的领主庄园，拥有几十成百的农户小家庭。vm可以为不同的任务提供不同的地址空间，让他们有自己独立的“小家庭”。小家庭里面发生的家长里短，只有关起门来的自家人才关心，不会影响到门外的路人，这是其好处。
启动阶段内存
启动阶段，一切从简。这时候如果需要使用内存，该当怎么办呢？虽然这个阶段非常短，但还是有内存使用的需求的。比如创建一个结构体队列，申请一段缓冲区啥的。一种办法，是在编译的时候就预先知道这段所需内存的长度，为其预留一段物理内存供内核使用。
好一点的办法，当然是灵活一点，可以动态地申请。LK做了这件事情，它利用了内核镜像结束处的一段物理内存，作为它的可用内存资源。通过函数boot_alloc_mem来实现内存申请逻辑。
这个函数的实现过于简单，我实在担心用得不小心会出问题。它的简单表现在两个方面。一，它只实现了申请函数，无释放函数，所以不能回收资源；二，它没有边界的安全检测。
好在现在lk中只有pmm用了它一次，申请了page结构体列表。此后，pmm就接管了物理内存管理的事务，系统不再需要它了。
uintptr_t boot_alloc_end = (uintptr_t) &_end;
void *boot_alloc_mem(size_t len)
{
uintptr_t ptr;
ptr = ALIGN(boot_alloc_end, 8);
boot_alloc_end = (ptr + ALIGN(len, 8));
return (void *)ptr;
}
全局变量boot_alloc_end的值被初始化为_end，即lk内核镜像所加载到的结束位置。这个值乃是在链接文件中手动指定的。
等价映射
一旦VM完成了初始化，boot阶段的内存管理器就不再使用了，将由pmm模块负责物理内存的管理。但boot阶段申请的所有物理内存，仍然是有效可用的——这需要做一步额外的操作即等价映射，来确保vm启动前后这段地址都可用。
VMM会将这段boot阶段的物理内存等价映射到内核地址空间中去，确保在vm启用后，这些内存的地址依然有效。即使用同样的地址，得到同样的内容——虽然此前是物理地址值，而VM启动后却是虚拟地址。
static void vm_init_preheap(uint level)
{
LTRACE_ENTRY;
/* allow the vmm a shot at initializing some of its data structures */
vmm_init_preheap();
/* mark all of the kernel pages in use */
LTRACEF("marking all kernel pages as used\n");
mark_pages_in_use((vaddr_t)&_start, ((uintptr_t)&_end - (uintptr_t)&_start));
/* mark the physical pages used by the boot time allocator */
if (boot_alloc_end != boot_alloc_start) {
LTRACEF("marking boot alloc used from 0x%lx to 0x%lx\n", boot_alloc_start, boot_alloc_end);
mark_pages_in_use(boot_alloc_start, boot_alloc_end - boot_alloc_start);
}
}
在vm没有启用的时候，代码可以肆意使用物理内存，往一个有效的地址中读写数据，或者从一个有效的地址处开始执行——前提是自己心里要有数，目标地址是有效可使用的。
一旦vm启用后，就没有这么自由了。你不可能有先验知识，某个地址或者地址范围是否有效。地址的有效与否，要通过vmm预先将它映射到一个物理页上去。所以，你要预先去构建vm的地址空间才行——等价映射就是这样的构建过程，它使得boot内存区域在vm启用后的虚拟内存环境中依然可用。
pmm模块
vm启动后还是要对物理内存进行管理的，但这时候功能就比启动阶段复杂了，它至少要有内存回收的能力。这时候，vm模块对物理内存的管理，其本质上所做的事情和novm是类似的，所以结构上有相似处。
pmm也用内存arena的概念，作为一级建制，它代表着一个有明确起讫地址的连续物理空间；然后多了一个内存region（区域）的建制，以便于为某个vm地址空间分配的连续的物理地址进行管理；最后才是page页。所以它的物理内存拥有三级管理建制。
vm模块中管理物理地址的子模块叫做pmm（物理内存管理者）。pmm也使用一个全局变量来维护内存arena对象，但它使用的是链表而非数组：
/* physical allocator */
typedef struct pmm_arena {
struct list_node node;
const char *name;
// ...
} pmm_arena_t;
static struct list_node arena_list = LIST_INITIAL_VALUE(arena_list);
物理page（页）是最基本的组织单元。和Linux等内核类似，它有必要为每个物理page维护一个基本的数据结构的。和其他复杂的内核相比，这个page结构相对比较简单，当前仅有：页的属性（flag）和引用计数（ref）。
/* core per page structure */
typedef struct vm_page {
struct list_node node;
uint flags : 8;
uint ref : 24;
} vm_page_t;
内存arena所管理的内存区域是不可以重叠的，所以arena和物理地址之间有一一对应关系。可以通过一个物理地址来找到对应的arena对象，并找到它对应的物理页结构体。下面这个函数就是这个功能。首先找到此物理地址的家长——只要这个物理地址落在某个arena区间，就找到家长了；然后通过arena结构体中的page_array数组来返回对应的page结构体：
vm_page_t *paddr_to_vm_page(paddr_t addr)
{
pmm_arena_t *a;
list_for_every_entry(&arena_list, a, pmm_arena_t, node) {
if (addr >= a->base && addr <= a->base + a->size - 1) {
size_t index = (addr - a->base) / PAGE_SIZE;
return &a->page_array[index];
}
}
return NULL;
}
虽然lk实现了支持多arena的能力，但实际上LK现在的既有平台实现，都只使用了唯一的内存arena，包括一般肯定会存在内存空洞的PC平台。说明目前LK的平台适配崇尚简易，有一段堪用的内存供其伸展便够了。这里贴一个简单的例子，看某mtk的平台是如何进行物理内存之快速初始化的：
static pmm_arena_t arena = {
.name = "dram",
.base = MEMBASE, // base和size是编译宏，由编译者根据平台
.size = MEMSIZE, // 属性配置；代码执行时，此两值都是常量
.flags = PMM_ARENA_FLAG_KMAP,
};
void platform_early_init(void)
{
//...
pmm_add_arene(&arena); // 初始化唯一的内存arena结构体并置入表头
}
pmm提供的对外接口说白了和novm类似，也是以page为单位进行内存的申请和释放。我们知道novm弄了一个简单的map来配置相应的page使用状态。pmm中的arena对象通过page结构体来管理物理页，并检索page结构体中的信息来获取其使用状态。arena对象还组织了一个free list来专门记录空闲页，从而可以快速地为申请者提供内存。
当一个page被分配出去的时候，pmm会设置其flags位：VM_PAGE_FLAG_NONFREE。同时，会把它从free list中移除。移除的操作很简单，page结构体的第一个成员变量node就是用来实现free list，直接操作node变量就可以将它移出free list了。
释放操作相对就简单了。对于一个page而言，它的VM_PAGE_FLAG_NONFREE flag会被清空。同时，把它重新插入到free list的末尾。
下面介绍两个内存申请的函数：
// @list是一个输出形参，它期望pmm把分配给它的page纳入到这个list中。
// @count是一个输入参数，调用者期望申请到的page数量。
// @ret，是pmm实际分配给调用者的page数量。资源充足时，它等于@count，不足时会小于它。
size_t pmm_alloc_pages(int count, struct list_node *list);
这个函数返回的物理页链表是离散的。如果申请者需要地址连续的物理内存，通过free list就不能保证了。因为一旦申请者释放内存的话，pmm就会把释放的内存保存到free list中。这导致一开始可能是连续的free list，一旦到了实际的使用环境中，很快就会变得零散了。所以要申请连续的物理内存，就只能通过查找page_array来实现，page_array是一个连续存储的page数组。
// @count是一个输入形参，它期望pmm分配给他的page数量
// @pa是一个输出形参，它得到的连续物理地址的起始值
// @list是一个输出形参，是pmm分配给调用者的page列表
// @ret是实际得到的page数量。它要么和count相等，要么是0，表示完全失败。没有中间结果。
size_t pmm_alloc_contignous(int count, paddr_t* pa, struct list_node* list)
内核命令
LK的内核基本模块都有一个专属的内核命令。这是一个有趣的架构设计。它一方面通过这个命令，提供了模块的基本操作接口；另一方面，很便于编写功能测试的代码，对此模块实现的基本功能进行验证。
pmm内核命令提供的操作：
- arenas 用来列印系统中的内存arenas结构体信息。前面我们经过，pmm通过全局数组来保存这个信息，而现有的实现都只有一个arena结构体。
- alloc/alloc_range/alloc_kpages/alloc_contig 不是形式的内存申请命令。所有的申请，都记录到一个名为allocated的静态列表变量中。
- free_alloced 释放名为allocated的静态列表变量中保存的page list内存。
- dump_alloced 列印名为allocated的静态列表变量中保存的page list的信息。
VMM
VMM就是虚拟地址空间的管理和维护者，它的主要工作对象是虚拟地址页表。不同架构的页表创建和维护的方式不尽相同，所以不同架构会有不同的实现版本，这里包括x86，amd64，arm，arm64，risc-v等。但他们的接口是统一的。
status_t arch_mmu_init_aspace(arch_aspace_t *aspace, vaddr_t base, size_t size, uint flags) ;
在系统启动的时候，会创建内核地址空间。它是第一个被创建的地址空间，所以是地址空间链表上的第一个成员。
void vmm_init_preheap(void)
{
/* initialize the kernel address space */
strlcpy(_kernel_aspace.name, "kernel", sizeof(_kernel_aspace.name));
_kernel_aspace.base = KERNEL_ASPACE_BASE;
_kernel_aspace.size = KERNEL_ASPACE_SIZE;
_kernel_aspace.flags = VMM_ASPACE_FLAG_KERNEL;
list_initialize(&_kernel_aspace.region_list);
arch_mmu_init_aspace(&_kernel_aspace.arch_aspace, KERNEL_ASPACE_BASE,
KERNEL_ASPACE_SIZE, ARCH_ASPACE_FLAG_KERNEL);
list_add_head(&aspace_list, &_kernel_aspace.node);
}
当_kernel_aspace创建之后，它将被加入到全局的地址空间链表aspace_list上。用户可以通过内核命令vmm查看系统中的所有地址空间。
要创建一个普通的地址空间，应该使用另一个函数vmm_create_aspace()。这个函数目前没有实际的场景在使用。换句话说，LK现在还没有恰当的用户层应用生态。
启动了VM后，系统使用的就是虚拟地址了。处理器在进行内存操作的时候，会主动地通过页表进行地址解码，在获得解码后的物理地址后再进行真正的内存操作。
内核虚拟地址
LK奉行的是一种简单的内核实现，所以在地址映射上，它也采取了简单的方法。内核虚拟地址是一种典型体现。在这种映射的关系中，系统可用的物理地址，一次性地映射到一个虚拟地址空间中。他们除了起始地址不一样外，整个地址空间，都是一一对应的。比如，将0-1G的物理地址映射到2-3G的虚拟地址空间中。通过这种方式，内核可以很方便地得到虚拟地址，转换效率高。
这种简便，相对于Linux内核而言，表现在它不必考虑内核的虚拟地址空间是否够用这种情况，它可以不使用超过它地址范围的物理内存。比如对于x86系统，它可以仅使用1G物理内存。
在系统加载的时候，系统开发者自己要决定，让LK使用哪部分的物理内存，这和平台bootloader需要把LK加载到哪个地址也有关系。下面的代码是x86的内存映射结构体，它默认将0-1G的物理内存，映射到2-3G虚拟地址空间上。
struct mmu_initial_mapping mmu_inital_mappings[] = {
/* 1GB of memory mapped where the kernel lives */
{
.phys = MEMBASE, // default 0
.virt = KERNEL_BASE, // default 2G
.size = 1*GB, /* x86 maps first 1GB by default */
.flags = 0,
.name = "kernel"
},
/* null entry to terminate the list */
{ 0 }
};
通过这种一一映射的关系，想要获取一个物理内存的虚拟地址，可以直接通过起始地址加上偏移量来求得。它通过搜索mmu_initial_mappings数组，确定物理地址是否落在某个物理区间中。如果是的话，就将此物理地址相对于区间的偏移量，加上对应的虚拟地址基地址，即可得到此物理地址的内核虚拟地址了。其实现代码如下：
void *paddr_to_kvaddr(paddr_t pa)
{
struct mmu_initial_mapping *map = mmu_initial_mappings;
while (map->size > 0) {
if (!(map->flags & MMU_INITIAL_MAPPING_TEMPORARY) &&
pa >= map->phys &&
pa <= map->phys + map->size - 1) {
return (void *)(map->virt + (pa - map->phys));
}
map++;
}
return NULL;
}
通过这种一一映射的方式，在LK内核执行的过程中，所有通过LK申请到的物理地址，都天然地有一个可用的虚拟地址。这个转换是很快的，因为它没有进行页表检索。但LK没有提供内核虚拟地址到物理地址的转换函数，这应该是它的一个缺失。
地址空间
上面一节提到的内核虚拟地址，它是一种便利的物理内存使用的方式。但LK还实现了更为正式的页表实现的地址空间这种虚拟地址的管理方式。虚拟地址空间通过一个结构体来表示：
/* virtual allocator */
typedef struct vmm_aspace {
struct list_node node;
char name[32];
uint flags;
vaddr_t base;
size_t size;
struct list_node region_list;
arch_aspace_t arch_aspace;
} vmm_aspace_t;
当前系统中有两类地址空间。一类，系统唯一的内核地址空间，因为它是系统唯一的，所以它通过全局变量_kernel_aspace定义了；一类，是每个任务独立拥有的用户地址空间，结构体保存在task结构体中。系统通过虚拟地址的范围来判断其所属哪类空间：
static inline bool is_kernel_address(vaddr_t va)
{
return (va >= (vaddr_t)KERNEL_ASPACE_BASE &&
va <= ((vaddr_t)KERNEL_ASPACE_BASE + ((vaddr_t)KERNEL_ASPACE_SIZE - 1)));
}
static inline bool is_user_address(vaddr_t va)
{
return (va >= USER_ASPACE_BASE &&
va <= (USER_ASPACE_BASE + (USER_ASPACE_SIZE - 1)));
}
这两个函数里面有一些涉及地址空间起始地址和长度的宏定义，它们基本上可以由系统开发者自由决定的，预先添加到编译文件中。如果开发者未手动设定，LK定义了如下的默认定义：
#define KERNEL_ASPACE_BASE ((vaddr_t)0x80000000UL)
#define KERNEL_ASPACE_SIZE ((vaddr_t)0x80000000UL)
#define USER_ASPACE_BASE ((vaddr_t)0x01000000UL))
#define USER_ASPACE_SIZE ((vaddr_t)KERNEL_ASPACE_BASE - USER_ASPACE_BASE - 0x01000000UL)
内存区域
地址空间下面还有一级管理建制，叫做内存区域（Region）。
typedef struct vmm_region {
struct list_node node;
char name[32];
uint flags;
uint arch_mmu_flags;
vaddr_t base;
size_t size;
struct list_node page_list;
} vmm_region_t;
内存区域是真正拥有物理地址空间的这么一个区域。因为地址空间是很庞大的，它本身是个虚拟的概念，比如64位系统上的有效内核地址空间可能是256G，它不可能完全映射到实际的物理内存上。物理内存是有限的。通过内核区域来管理有实际物理内存映射的地址空间。
内存区域是分散在地址空间内的，所以地址空间通过链表来管理所有的内存区域。这是成员变量node的作用。
一个内存区域是可命名的。默认名称为’unamed’，如果创建区域的时候未曾手动设置的话。
page_list是此内存区域的物理内存的page链表。这些物理内存，对应的虚拟地址范围是base和size。
内存申请
VMM提供了基于page的连续内存申请的接口，page粒度比较大，但lk提供了更小粒度的heap库供应用开发使用。VMM的内存申请接口根据特征，有若干个版本。
vmm_alloc：申请指定大小的虚拟内存；vmm负责为它完成物理内存的申请和地址映射；返回起始虚拟地址。
vmm_alloc_physical：调用者已经申请好了物理内存，并作为输入参数传递给vmm；vmm负责申请一块大小相当的虚拟地址空间，并映射到调用者指定的物理地址空间；返回起始虚拟地址。
vmm_alloc_contiguous：功能和vmm_alloc类似，但vmm需要为调用者申请连续的物理内存页；返回起始虚拟地址。
待续…
17,247 total views, 2 views today