Little Kernel 代码走读(一)

作者:张佩】【原始链接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内核命令提供的操作:

  1. arenas 用来列印系统中的内存arenas结构体信息。前面我们经过,pmm通过全局数组来保存这个信息,而现有的实现都只有一个arena结构体。
  2. alloc/alloc_range/alloc_kpages/alloc_contig 不是形式的内存申请命令。所有的申请,都记录到一个名为allocated的静态列表变量中。
  3. free_alloced 释放名为allocated的静态列表变量中保存的page list内存。
  4. 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需要为调用者申请连续的物理内存页;返回起始虚拟地址。

待续…

13,635 total views, 5 views today

发表评论

电子邮件地址不会被公开。