三生万物: 实现加载程序的loader

loader是一个用于加载程序的模块, 实现了足够多的指令之后, 你也可以实现一个很简单的loader, 来加载其它用户程序.

可执行文件的组织

我们知道程序中包括代码和数据, 它们都是存储在可执行文件中. 加载的过程就是把可执行文件中的代码和数据放置在正确的内存位置, 然后跳转到程序入口, 程序就开始执行了. 更具体的, 我们需要解决以下问题:

• 可执行文件在哪里?
• 代码和数据在可执行文件的哪个位置?
• 代码和数据有多少?
• "正确的内存位置"在哪里?

我们在PA1中已经提到了以下内容:

在一个完整的模拟器中, 程序应该存放在磁盘中, 但目前我们并没有实现磁盘的模拟, 因此NEMU先把内存开始的位置作为ramdisk来使用.

现在的ramdisk十分简单, 它只有一个文件, 也就是我们将要加载的用户程序, 访问内存位置0就可以得到用户程序的第一个字节. 这其实已经回答了上述第一个问题: 可执行文件位于内存位置0. 为了回答剩下的问题, 我们首先需要了解可执行文件是如何组织的.

代码和(静态)数据是程序的必备要素, 可执行文件中自然需要包含这两者. 但仅仅包含它们还是不够的, 我们还需要一些额外的信息来告诉我们"代码和数据分别有多少", 否则我们连它们两者的分界线在哪里都不知道. 这些额外的信息描述了可执行文件的组织形式, 不同组织形式形成了不同格式的可执行文件, 例如Windows主流的可执行文件是PE(Protable Executable)格式, 而GNU/Linux主要使用ELF(Executable and Linkable Format)格式, 因此一般情况下, 你不能在Windows下把一个可执行文件拷贝到GNU/Linux下执行, 反之亦然. ELF是GNU/Linux可执行文件的标准格式, 这是因为GNU/Linux遵循System V ABI(Application Binary Interface).

你应该已经学会使用 readelf 命令来查看ELF文件的信息了. ELF文件提供了两个视角来组织一个可执行文件, 一个是面向链接过程的section视角, 这个视角提供了用于链接与重定位的信息(例如符号表); 另一个是面向执行的segment视角, 这个视角提供了用于加载可执行文件的信息. 通过readelf命令, 我们还可以看到section和segment之间的映射关系: 一个segment可能由0个或多个section组成, 但一个section可能不被包含于任何segment中.

我们现在关心的是如何加载程序, 因此我们重点关注segment的视角. ELF中采用program header table来管理segment, program header table的一个表项描述了一个segment的所有属性, 包括类型, 虚拟地址, 标志, 对齐方式, 以及文件内偏移量和segment大小. 根据这些信息, 我们就可以知道需要加载可执行文件的哪些字节了, 同时我们也可以看到, 加载一个可执行文件并不是加载它所包含的所有内容, 只要加载那些与运行时刻相关的内容就可以了, 例如调试信息和符号表就不必加载. 由于运行时环境的约束, 在PA中我们只需要加载代码段和数据段, 如果你在GNU/Linux下编译一个Hello world程序并使用 readelf 查看, 你会发现它需要加载更多的内容.

我们通过下面的图来说明如何根据segment的属性来加载它:

      +-------+---------------+-----------------------+
      |       |...............|                       |
      |       |...............|                       |  ELF file
      |       |...............|                       |
      +-------+---------------+-----------------------+
      0       ^               |              
              |<------+------>|       
              |       |       |             
              |       |                            
              |       +----------------------------+       
              |                                    |       
   Type       |   Offset    VirtAddr    PhysAddr   |FileSiz  MemSiz   Flg  Align
   LOAD       +-- 0x001000  0x00100000  0x00100000 +0x1d600  0x27240  RWE  0x1000
                               |                       |       |     
                               |   +-------------------+       |     
                               |   |                           |     
                               |   |     |           |         |       
                               |   |     |           |         |      
                               |   |     +-----------+ ---     |     
                               |   |     |00000000000|  ^      |   
                               |   | --- |00000000000|  |      |    
                               |   |  ^  |...........|  |      |  
                               |   |  |  |...........|  +------+
                               |   +--+  |...........|  |      
                               |      |  |...........|  |     
                               |      v  |...........|  v    
                               +-------> +-----------+ ---  
                                         |           |     
                                         |           |    
                                            Memory

你需要找出每一个program header的 Offset , VirtAddr , FileSiz 和 MemSiz 这些参数. 其中相对文件偏移 Offset 指出相应segment的内容从ELF文件的第 Offset 字节开始, 在文件中的大小为 FileSiz , 它需要被分配到以 VirtAddr 为首地址的虚拟内存位置, 在内存中它占用大小为 MemSiz . 但现在NEMU还没有虚拟地址的概念, 因此你只需要把 VirtAddr 当做物理地址来使用就可以了, 也就是说, 这个segment使用的内存就是 [VirtAddr, VirtAddr + MemSiz) 这一连续区间, 然后将segment的内容从ELF文件中读入到这一内存区间, 并将 [VirtAddr + FileSiz, VirtAddr + MemSiz) 对应的物理区间清零.

关于程序从何而来, 可以参考一篇文章: COMPILER, ASSEMBLER, LINKER AND LOADER: A BRIEF STORY. 如果你希望查阅更多与ELF文件相关的信息, 请参考

man 5 elf

在kernel中实现loader

理解了上述内容之后, 你就可以在kernel中实现loader了. 在这之前, 我们先对kernel作一些简单的介绍.

在PA中, kernel是一个单任务微型操作系统的内核, 其代码在工程目录的 kernel 目录下. kernel已经包含了后续PA用到的所有模块, 换句话说, 我们现在就要在NEMU上运行一个操作系统了(尽管这是一个十分简陋的操作系统), 同时也将带领你根据课堂上的知识剖析一个简单操作系统内核的组成. 这不仅是作为对这些抽象知识的很好的复(预)习, 同时也是为以后的操作系统实验打下坚实的基础. 由于NEMU的功能是逐渐添加的, kernel也要配合这个过程, 你会通过 kernel/include/common.h 中的一些与实验进度相关的宏来控制kernel的功能. 随着实验进度的推进, 我们会逐渐讲解所有的模块, kernel做的工作也会越来越多. 因此在阅读kernel的代码时, 你只需要关心和当前进度相关的模块就可以了, 不要纠缠于和当前进度无关的代码.

另外需要说明的是, 虽然不会引起明显的误解, 但在引入kernel之后, 我们还是会在某些地方使用"用户进程"的概念, 而不是"用户程序". 如果你现在不能理解什么是进程, 你只需要把进程作为"正在运行的程序"来理解就可以了. 还感觉不出这两者的区别? 举一个简单的例子吧, 如果你打开了记事本3次, 计算机上就会有3个记事本进程在运行, 但磁盘中的记事本程序只有一个. 进程是操作系统中一个重要的概念, 有关进程的详细知识会在操作系统课上进行介绍.

在工程目录下执行 make kernel 来编译kernel. kernel的源文件组织如下:

kernel
├── include
│   ├── common.h
│   ├── debug.h
│   ├── memory.h
│   ├── x86
│   │   ├── cpu.h
│   │   ├── io.h
│   │   └── memory.h
│   └── x86.h
├── Makefile.part
└── src
    ├── driver
    │   ├── ide            # IDE驱动程序
    │   │   └── ...
    │   └── ramdisk.c    # ramdisk驱动程序
    ├── elf            # loader相关
    │   └── elf.c
    ├── fs            # 文件系统
    │   └── fs.c
    ├── irq            # 中断处理相关
    │   ├── do_irq.S        # 中断处理入口代码
    │   ├── i8259.c        # intel 8259中断控制器
    │   ├── idt.c        # IDT相关
    │   └── irq_handle.c    # 中断分发和处理
    ├── lib
    │   ├── misc.c        # 杂项
    │   ├── printk.c
    │   └── serial.c        # 串口
    ├── main.c
    ├── memory            # 存储管理相关
    │   ├── kvm.c        # kernel虚拟内存
    │   ├── mm.c        # 存储管理器MM
    │   ├── mm_malloc.o        # 为用户程序分配内存的接口函数, 不要删除它!
    │   └── vmem.c        # video memory
    ├── start.S            # kernel入口代码
    └── syscall            # 系统调用处理相关
        └── do_syscall.c

一开始 kernel/include/common.h 中所有与实验进度相关的宏都没有定义, 此时kernel的功能十分简单. 我们先简单梳理一下此时kernel的行为:

1. 第一条指令从 kernel/src/start.S 开始, 设置好堆栈之后就跳转到 kernel/src/main.c 的 init() 函数处执行.
2. 由于NEMU还没有实现分段分页的功能, 此时kernel会跳过很多初始化工作, 直接跳转到 init_cond() 函数处继续进行初始化.
3. 继续跳过一些初始化工作之后, 会通过 Log() 宏输出一句话. 需要说明的是, kernel中定义的 Log() 宏并不是NEMU中定义的 Log() 宏, kernel和NEMU的代码是相互独立的, 因此编译某一方时都不会受到对方代码的影响, 你在阅读代码的时候需要注意这一点. 在kernel中, Log() 宏通过 printk() 输出. 阅读 printk() 的代码, 发现此时 printk() 什么都不做就直接返回了, 这是由于现在NEMU还不能提供输出的功能, 因此现在kernel中的 Log() 宏并不能成功输出.
4. 调用 loader() 函数加载用户程序, loader() 函数会返回用户程序的入口地址.
5. 跳转到用户程序的入口执行.

理解上述过程后, 你需要在 kernel/src/elf/elf.c 的 loader() 函数中定义正确ELF文件魔数, 然后编写加载segment的代码, 完成加载用户程序的功能. 你需要使用 ramdisk_read() 函数来读出ramdisk中的内容, ramdisk_read() 函数的原型如下:

它负责把从ramdisk中 offset 偏移处的 len 字节读入到 buf 中.

我们之前让用户程序直接在 0x100000 处运行, 而现在我们希望先从 0x100000 处运行kernel, 让kernel中的loader模块加载用户程序, 然后跳转到用户程序处运行. 为此, 我们需要修改用户程序的链接选项:

我们让用户程序从 0x800000 附近开始运行, 避免和kernel的内容产生冲突. 最后我们还需要修改工程目录下的 Makefile , 把kernel作为entry:

我们从运行时刻的角度来描述NEMU中物理内存的变化过程:

• 刚开始运行NEMU时, NEMU会进行一些全局的初始化操作, 其中有一项内容是初始化ramdisk(由 nemu/src/monitor/monitor.c 中的 init_ramdisk() 函数完成): 将用户程序的ELF文件从真实磁盘拷贝到模拟内存中地址为0的位置. 目前ramdisk中只有一个文件, 就是用户程序的ELF文件:

  0
  +------------+---------------------------------------------------
  |            |
  |  ELF file  |
  |            |
  +------------+---------------------------------------------------
  

• 第二项初始化操作是将entry加载到内存位置 0x100000 (由 nemu/src/monitor/monitor.c 中的 load_entry() 函数完成). 之前entry就是用户程序本身, 引入kernel之后, entry就变成kernel了. 换句话说, 在我们的PA中, kernel是由NEMU的monitor模块直接加载到内存中的. 这一点与真实的计算机有所不同, 在真实的计算机中, 计算机启动之后会首先运行BIOS程序, BIOS程序会将MBR加载到内存, MBR再加载别的程序... 最后加载kernel. 要模拟这个过程需要一个完善的模拟磁盘, 而且需要涉及较多的细节, 根据KISS法则, 我们不模拟这个过程, 而是让NEMU直接将kernel加载到内存. 这样, 在NEMU开始执行第一条指令之前, kernel就已经在内存中了:

  0                   0x100000
  +------------+----------+----------+-----------------------------
  |            |          |          |
  |  ELF file  |          |  kernel  |
  |            |          |          |
  +------------+----------+----------+-----------------------------
  

• NEMU执行的第一条指令就是kernel的第一条指令. 如上文所述, kernel会完成一些自身的初始化工作, 然后从ramdisk中的EFL文件把用户程序加载到内存位置 0x800000 附近, 然后跳转到用户程序中执行:

  0                   0x100000             0x800000
  +------------+----------+----------+---------+-----------+-------
  |            |          |          |         |           |        
  |  ELF file  |          |  kernel  |         |  program  |      
  |            |          |          |         |           |       
  +------------+----------+----------+---------+-----------+-------
  

make test