一、Introduction


这个实验是向 JOS 中添加功能以支持 User Environment(即 Unix 中的进程)。

注意: 在实验过程中,术语 environmentprocess 是等价的,都是对用户程序的一种抽象。在 JOS 中使用 environment,是为了和传统的 UNIX 中的 process 进行区分,它们在接口和语义上有点区别。

But,由于翻译过中文 “环境” 这个词听着实在别扭,以后的实验中有时候还是将 environment 称作进程。

1.1、Getting Started

先合并代码:

linux> cd ~/6.828/lab
linux> git commit -m "change"
linux> git pull
linux> git checkout -b lab3 origin/lab3
linux> git checkout lab1
linux> git merge lab3 

由于我是在 lab1 分之上做的开发,所以合并前需要切换到 lab1 分支。

下面是本实验需要用到的一些文件说明,大致浏览一下即可:

  1. inc/env.h Public definitions for user-mode environments
  2. trap.h Public definitions for trap handling
  3. syscall.h Public definitions for system calls from user environments to the kernel
  4. lib.h Public definitions for the user-mode support library
  5. kern/env.h Kernel-private definitions for user-mode environments
  6. env.c Kernel code implementing user-mode environments
  7. trap.h Kernel-private trap handling definitions
  8. trap.c Trap handling code
  9. trapentry.S Assembly-language trap handler entry-points
  10. syscall.h Kernel-private definitions for system call handling
  11. syscall.c System call implementation code
  12. lib/Makefrag Makefile fragment to build user-mode library, obj/lib/libjos.a
  13. entry.S Assembly-language entry-point for user environments
  14. libmain.c User-mode library setup code called from entry.S
  15. syscall.c User-mode system call stub functions
  16. console.c User-mode implementations of putchar and getchar, providing console I/O
  17. exit.c User-mode implementation of exit
  18. panic.c User-mode implementation of panic
  19. user/ Various test programs to check kernel lab 3 code

1.2、Inline Assembly

这个 lab 里很多地方会使用到内联汇编,下面是一些参考资料:

  1. Inline assembly for x86 in Linux
  2. Brennan’s Guide to Inline Assembly
  3. GCC Inline Assembly HOWTO
  4. 内联汇编初探

 

二、Part A: User Environment and Exception Handling


在文件 inc/env.h 中包括了一些重要的定义,最好能提前阅读一下。其中 Env 这个数据结构用来描述 user environment 的概念,这个实验要求能创建一个 environment,并支持多个 environment

kern/env.c 中, kernel 使用了 3 个全局变量来描述记录 environments:

struct Env *envs = NULL;		   // All environments
struct Env *curenv = NULL;		   // The current env
static struct Env *env_free_list;  // Free environment list
					               // (linked by Env->env_link)

当 JOS 启动后, envs 指向一个 Env 结构体数组,表示系统中所有的环境(environment)。在我们的设计中,JOS 支持最多 NENV(see blow)个进程同时活动。

#define LOG2NENV		10
#define NENV			(1 << LOG2NENV)

JOS 将所有不活动的进程放到 env_free_list 链表中,并使用 curenv 来表示当前正在执行的进程。系统刚启动时,curenv 被初始化为 NULL

2.1、Environment State

下面是 Env 结构体,随着实验的进行,会向里面添加更多的成员。

struct Env {
	struct Trapframe env_tf; // Saved registers
	struct Env *env_link;	   // Next free Env
	envid_t env_id;			     // Unique environment identifier
	envid_t env_parent_id;	 // env_id of this env's parent
	enum EnvType env_type;	 // Indicates special system environments
	unsigned env_status;	   // Status of the environment
	uint32_t env_runs;	 	   // Number of times environment has run
	// Address space 
	pde_t *env_pgdir;	    	 // Kernel virtual address of page dir
};

下面是成员进行说明:

  1. env_tf: 这里的 Trapframe 结构体与 xv6 中的 trapframe 是类似,当进程不运行的时候(i.e.,需要系统中另一个进程运行 or 此进程陷入内核),kernel 把当前进程相关的寄存器保存进 Trapframe,以便后面回到用户空间时使用。
  2. env_link: 指向空闲进程链表 env_free_list 中的下一个空闲进程,以形成链表(env_free_list 指向第一个空闲进程)。
  3. env_id: 此成员唯一标识当前系统中正在运行的进程。当用户进程结束时,kernel 可能会将此进程的 Env 结构体分配给下一个运行的进程使用,但是他们的 env_id 成员是不一样的,即使用同一块内存,但是内存中的 env_id 域唯一的标识了这块内存。
  4. env_parent_id: 记录此进程由哪个进程创建,形成 “family tree”
  5. env_type: 用来区别一些特殊的进程,目前只有 ENV_TYPE_USER 类型,定义在 EnvType 枚举类型里,在以后的实验中会向里面添加更多值。
  6. env_status: 一共有 5 种类型:
    • ENV_FREE: Indicates that the Env structure is inactive, and therefore on the env_free_list.
    • ENV_RUNNABLE: Indicates that the Env structure represents an environment that is waiting to run on the processor.
    • ENV_RUNNING: Indicates that the Env structure represents the currently running environment.
    • ENV_NOT_RUNNABLE: Indicates that the Env structure represents a currently active environment, but it is not currently ready to run: for example, because it is waiting for an interprocess communication (IPC) from another environment.
    • ENV_DYING: Indicates that the Env structure represents a zombie environment. A zombie environment will be freed the next time it traps to the kernel. We will not use this flag until Lab 4.
  7. env_pgdir: 这个变量保存着此进程的页目录的内核虚拟地址。

和 Unix 中的进程一样,JOS 的进程将线程和地址空间的概念结合到了一起:线程主要由 env_tf 成员描述;地址空间则由 env_pgdir 成员描述。为了运行一个进程,JOS kernel 必须为 CPU 设置好相关寄存器(Trapframe中的寄存器和控制寄存器)。

JOS 中的 struct Env 与 xv6 中的 struct proc 类似,两个结构体都在 trapframe 中都保存了用户态下的寄存器状态。与 xv6 不同的时,JOS 没有为每个进程单独设置内核栈,JOS 中任意时间只支持一个进程运行,所以 JOS 只需要一个内核栈即可。关于这点可以对比一下两者的结构体:

struct proc {
  uint sz;                     // Size of process memory (bytes)
  pde_t* pgdir;                // Page table
  char *kstack;                // Bottom of kernel stack for this process(important)
  enum procstate state;        // Process state(important)
  int pid;                     // Process ID
  struct proc *parent;         // Parent process
  struct trapframe *tf;        // Trap frame for current syscall
  struct context *context;     // swtch() here to run process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
  // add for alarmtest.c
  int alarmticks;
  void (*alarmhandler)();
  int tick_counts;
};

可以看到,struct procstruct Env 多了一个关键的成员 char *kstack,这就说明每创建一个进程就有一个 kstack 来记录此进程内核栈的位置,在 xv6/proc.c/allocproc() 中初始化内核栈:

  if((p->kstack = kalloc()) == 0)
    p->state = UNUSED;
    return 0;
  }

2.2、Allocating the Environment Arrays

与 lab2 类似,我们在 mem_init() 中分配一个 Env 结构体数组 envs,这个数组里包括 NENV 个结构体的实例, envs 这个全局变量在 kern/env.h 中声明,在 kern/env.c 中定义。

这个练习的主要目的就是为 envs 链表分配物理物理内存,再将这段内存映射到虚拟内存对应的位置:

                                                Permissions
                                                kernel/user
        4 Gig -> +------------------------------+
                 |                              | RW/--
                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                 :            ...               :
                 |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| RW/--
                 |                              | RW/--
                 |   Remapped Physical Memory   | RW/--
                 |                              | RW/--
    KERNBASE, -> +------------------------------+ 0xf0000000  -----------------+
    KSTACKTOP    |     CPU0's Kernel Stack      | RW/-- KSTKSIZE(8*PGSIZE)     |
                 | - - - - - - - - - - - - - - -|                              |
                 |      Invalid Memory (*)      | --/-- KSTKGAP(8*PGSIZE)      |
                 +------------------------------+                              |
                 |     CPU1's Kernel Stack      | RW/-- KSTKSIZE               |
                 | - - - - - - - - - - - - - - -|                         PTSIZE(1024*4096B
                 |      Invalid Memory (*)      | --/-- KSTKGAP                |
                 +------------------------------+                              |
                 :              .               :                              |
      MMIOLIM -> +------------------------------+ 0xefc00000  -----------------+
                 |       Memory-mapped I/O      | RW/--  PTSIZE
ULIM,MMIOBASE -> +------------------------------+ 0xef800000      
                 |  Cur. Page Table (User R-)   | R-/R-  PTSIZE    +-------+-----+-----+
         UVPT -> +------------------------------+ 0xef400000 ----> | 0x3BD | 0x0 | 0x0 |
                 |          RO PAGES            | R-/R-  PTSIZE    +-------+-----+-----+
       UPAGES -> +------------------------------+ 0xef000000
                 |           RO ENVS            | R-/R-  PTSIZE
   UTOP,UENVS -> +------------------------------+ 0xeec00000

映射到 [UENVS, UPAGES) 这段虚拟空间,下面看代码:

//////////////////////////////////////////////////////////////////////
// Make 'envs' point to an array of size 'NENV' of 'struct Env'.
// LAB 3: Your code here.

envs = (struct Env *)boot_alloc(NENV * sizeof(struct Env));
memset(envs, 0, NENV * sizeof(struct Env));
//////////////////////////////////////////////////////////////////////
// Map the 'envs' array read-only by the user at linear address UENVS
// (ie. perm = PTE_U | PTE_P).
// Permissions:
//    - the new image at UENVS  -- kernel R, user R
//    - envs itself -- kernel RW, user NONE
// LAB 3: Your code here.

boot_map_region(kern_pgdir, UENVS, PTSIZE, PADDR(envs), PTE_U | PTE_P);

关于执行后,memset() 函数将指针清空的问题,参照知乎JOS 2018版本linker script问题

2.3、Creating and Running Environments

接下来在 kern/env.c 中添加相关代码以支持进程的运行。因为目前 kernel 中没有文件系统,所以选择直接将二进制文件内嵌在 kernel 中。

JOS embeds this binary in the kernel as a ELF executable image.

此实验的 GNUmakefile 在 obj/user/ 目录下生成了一些二进制文件。查看 kern/Makefrag 文件:

# Binary program images to embed within the kernel.
# Binary files for LAB3
KERN_BINFILES :=	user/hello \
			user/buggyhello \
			user/buggyhello2 \
			user/evilhello \
			user/testbss \
			user/divzero \
			user/breakpoint \
			user/softint \
			user/badsegment \
			user/faultread \
			user/faultreadkernel \
			user/faultwrite \
			user/faultwritekernel

KERN_OBJFILES := $(patsubst %.c, $(OBJDIR)/%.o, $(KERN_SRCFILES))
KERN_OBJFILES := $(patsubst %.S, $(OBJDIR)/%.o, $(KERN_OBJFILES))
KERN_OBJFILES := $(patsubst $(OBJDIR)/lib/%, $(OBJDIR)/kern/%, $(KERN_OBJFILES))
KERN_BINFILES := $(patsubst %, $(OBJDIR)/%, $(KERN_BINFILES))

The -b binary option on the linker command line causes these files to be linked in as “raw” uninterpreted binary files rather than as regular .o files produced by the compiler.(As far as the linker is concerned, these files do not have to be ELF images at all - they could be anything, such as text files or pictures!)

在 make 后,查看 obj/kern/kernel.sym,你会发现链接器产生了一些奇怪的符号:_binary_obj_user_hello_start, _binary_obj_user_hello_end, _binary_obj_user_hello_size。 通过这些符号去引用上面内嵌的二进制文件。

man ld

Exercise 2. In the file env.c, finish coding the following functions:

在完成这些函数的过程中,合理使用 cprintf()%e,它会打印出错误码。

r = -E_NO_MEM;
panic("env_alloc: %e", r);

打印结果:”env_alloc: out of memory”。

下面是一些关键函数的调用顺序:

我们按照这个顺序来完成函数。

2.3.1、env_init()

Mark all environments in ‘envs’ as free, set their env_ids to 0,and insert them into the env_free_list. Make sure the environments are in the free list in the same order they are in the envs array (i.e., so that the first call to env_alloc() returns envs[0]).

因为要求空闲链表元素的顺序与数组顺序相同,所以选择倒序插入。

void env_init(void)
{
	int i;
	env_free_list = NULL;
	for (i = NENV - 1; i >= 0; i--)
	{
		envs[i].env_id = 0;
		envs[i].env_link = env_free_list;
		env_free_list = &envs[i];
	}
	env_init_percpu();
}

2.3.2、env_setup_vm()

Initialize the kernel virtual memory layout for environment e. Allocate a page directory, set e->env_pgdir accordingly, and initialize the kernel portion of the new environment’s address space. Do NOT (yet) map anything into the user portion of the environment’s virtual address space.

因为在 pmap.c 中已经写过了 kernel 的映射,所以直接将其复制过来即可,因为所有进程 kernel 部分的映射都是相同的。

static int env_setup_vm(struct Env *e)
{
	int i;
	struct PageInfo *p = NULL;
	// Allocate a page for the page directory
	if (!(p = page_alloc(ALLOC_ZERO)))
		return -E_NO_MEM;
	// LAB 3: Your code here.
	p->pp_ref++;
	e->env_pgdir = (pde_t *)page2kva(p);
	memcpy(e->env_pgdir, kern_pgdir, PGSIZE);
	/*把页表映射到UVPT*/
	e->env_pgdir[PDX(UVPT)] = PADDR(e->env_pgdir) | PTE_P | PTE_U;
	return 0;
}

2.3.3、region_alloc()

Allocate len bytes of physical memory for environment env, and map it at virtual address va in the environment’s address space. Does not zero or otherwise initialize the mapped pages in any way. Pages should be writable by user and kernel. Panic if any allocation attempt fails.

因为参数 va 和 len 有可能不是按页对齐的,所以对 va 做 Round Down 操作;对 va+len 做 Round Up 操作。注意一些极端情况。

上面也说了,不要对分配的物理内存做初始化工作,所以 page_alloc() 参数为 0。

static void region_alloc(struct Env *e, void *va, size_t len)
{
	void *begin_va = ROUNDDOWN(va, PGSIZE);
	void *end_va = ROUNDUP(va+len, PGSIZE);
	for (; begin_va < end_va; begin_va += PGSIZE)
	{
		struct PageInfo *pp = page_alloc(0);
		if (!pp) 
			panic("region_alloc() faild: pp == NULL");
		if (page_insert(e->env_pgdir, pp, begin_va, PTE_W | PTE_U) == -E_NO_MEM)
		 	panic("region_alloc() faild: page_inset() == -E_NO_MEM");
	}
}

2.3.4、load_icode()

根据 ELF 段头表中的指示来加载各个段。并且只加载 ph->p_type 类型为 ELF_PROG_LOAD 的段。每个段的虚拟地址在 ph->p_va 里,大小在 ph->p_memsz 里。将 ELF 二进制文件中的 [binary + ph->p_offset,binary + ph->p_offset + ph->p_filesz] 大小的字节映射虚拟地址范围:[ph->p_va, ph->p_va + ph->p_memsz] 处。通常不会映射满(通常ph->p_filesz <= ph->p_memsz),空缺的字节一般是一些全局变量,将它们置为 0 即可。使用 lab 2 中的函数来完成分配和映射。这时 PTE 中的保护位应为 **PTE_U PTE_W**。程序段一般没必要按页对齐。在这个函数里假设两个程序段不会使用到同一虚拟页。配合 region_alloc() 函数使用。

了解一下这个函数调用链:

+------------+
|ENV_CREATE()|
+------------+
      |
     \/
+------------+
|env_create()|
+------------+
      |
     \/
+------------+
|load_icode()|
+------------+

从这个调用链可知 load_icode() binary 参数来自 kernel.sym 中的型为 binary_obj_user*_start 的符号。上面已经说过,因为现在还没有文件系统,为了完成本 lab 相关的测试,obj/user/ 目录下的二进制文件已经在编译器就内嵌进了内核中。所以我们只需要照着 kernel.sym 引用其符号即可。

完成这个函数还需回顾一下 lab1 加载 kernel 的步骤(boot/main.c)。

static void load_icode(struct Env *e, uint8_t *binary)
{
	struct Proghdr *ph, *ph_end;
	struct Elf *ELFHDR = (struct Elf *)binary;
	if (ELFHDR->e_magic != ELF_MAGIC) panic("Not ELF!");
	ph = (struct Proghdr *)(ELFHDR->e_phoff + (uint8_t *)ELFHDR);
	ph_end = ph + ELFHDR->e_phnum;

	lcr3(PADDR(e->env_pgdir));

	for (; ph < ph_end; ph++){
		if (ph->p_type == ELF_PROG_LOAD)
		{
			region_alloc(e, (void *)ph->p_va, ph->p_memsz); /* 为新进程建立页表映射 */
			memset((void *)ph->p_va, 0, ph->p_memsz);
			memcpy((void *)ph->p_va, binary + ph->p_offset, ph->p_filesz);
		}
	}

	lcr3(PADDR(kern_pgdir));
	e->env_tf.tf_eip = ELFHDR->e_entry;

	region_alloc(e, (void *)(USTACKTOP - PGSIZE), PGSIZE);
}

下面是 ELF 文件的相关信息:

$ objdump -x hello

hello:     file format elf32-i386
hello
architecture: i386, flags 0x00000112:
EXEC_P, HAS_SYMS, D_PAGED
start address 0x00800020

Program Header:
   LOAD off    0x00001000 vaddr 0x00200000 paddr 0x00200000 align 2**12
        filesz 0x00004005 memsz 0x00004005 flags rw-
   LOAD off    0x00005020 vaddr 0x00800020 paddr 0x00800020 align 2**12
        filesz 0x00001140 memsz 0x00001140 flags r-x
   LOAD off    0x00007000 vaddr 0x00802000 paddr 0x00802000 align 2**12
        filesz 0x0000002c memsz 0x00000030 flags rw-
  STACK off    0x00000000 vaddr 0x00000000 paddr 0x00000000 align 2**4
        filesz 0x00000000 memsz 0x00000000 flags rwx

下面以加载 obj/usr/hello 二进制文件演示一下 for 循环里做了什么事:

Virtual Address Space
  +---------------+
  |               |   
  |     ...       |
  +---------------+ <- enf of kernel
  |               |
  |               |
  +---------------+
  |    hello      |
  +---------------+ <- 0xF011A330 (查看kernel.sym)
  |               |
  |     ...       |
  |               |
  +---------------+ <- 0xF0000000
  |     ...       |
  +---------------+
  | copied hello  |
  +---------------+ <- 0x00800020 (objdump可知)
  |     ...       |
  +---------------+

通过 objdump -x hello 得知,hello 这个可执行文件想要在想要在虚拟地址 0x00800020 处开始执行。然而,这个文件内嵌在 kenel ELF 中的虚拟地址却是 0xF011A330,二者不等。所以选择 memcpy() 函数,将 hello 文件拷贝到 0x00800020 处。可是直接拷贝还不行。因为通过浏览函数发现,此时硬件 MMU 使用的页目录是:

void mem_init(void)
{
  ...
  lcr3(PADDR(kern_pgdir));
  ...
}

这个页目录里只有内核的映射,如果在 memcpy() 中用到了用户空间的地址,就会 Page Fault(疑问TODO:page fault后为什么不能建立相应的PTE来弥补?)。在 for 循环里,我们通过 region_alloc() 函数逐步的建立此进程用户空间的映射。所以在 for 循环前,使用:

lcr3(PADDR(e->env_pgdir));

将页目录切换到当前进程的页目录,for 循环结束后再切换回去。

2.3.5、env_create()

Allocates a new env with env_alloc, loads the named elf binary into it with load_icode, and sets its env_type. This function is ONLY called during kernel initialization, before running the first user-mode environment. The new env’s parent ID is set to 0.

void env_create(uint8_t *binary, enum EnvType type)
{
	struct Env *new_env = NULL;
	if (env_alloc(&new_env, 0) < 0)
		panic("env_alloc() failed!");
	load_icode(new_env, binary);
	new_env->env_type = type;
}

2.3.5、env_run()

Context switch from curenv to env e. Note: if this is the first call to env_run(), curenv is NULL.

void env_run(struct Env *e)
{
	if (curenv != NULL)
	{
		if (curenv->env_status == ENV_RUNNING)
			curenv->env_status = ENV_RUNNABLE;
	}
	curenv = e;
	curenv->env_status = ENV_RUNNING;
	curenv->env_runs++;
	lcr3(PADDR(curenv->env_pgdir));
	env_pop_tf(&(curenv->env_tf));
}

当完成这些函数后,编译内核并启动 QEMU,打印如下:

[00000000] new env 00001000
entry 800020EAX=00000000 EBX=00000000 ECX=0000000d EDX=eebfde88
ESI=00000000 EDI=00000000 EBP=eebfde60 ESP=eebfde54
EIP=00800bc3 EFL=00000092 [--S-A--] CPL=3 II=0 A20=1 SMM=0 HLT=0
ES =0023 00000000 ffffffff 00cff300 DPL=3 DS   [-WA]
CS =001b 00000000 ffffffff 00cffa00 DPL=3 CS32 [-R-]
SS =0023 00000000 ffffffff 00cff300 DPL=3 DS   [-WA]
DS =0023 00000000 ffffffff 00cff300 DPL=3 DS   [-WA]
FS =0023 00000000 ffffffff 00cff300 DPL=3 DS   [-WA]
GS =0023 00000000 ffffffff 00cff300 DPL=3 DS   [-WA]
LDT=0000 00000000 00000000 00008200 DPL=0 LDT
TR =0028 f0182b80 00000067 00408900 DPL=0 TSS32-avl
GDT=     f011b300 0000002f
IDT=     f0182360 000007ff
CR0=80050033 CR2=00000000 CR3=003bc000 CR4=00000000
DR0=00000000 DR1=00000000 DR2=00000000 DR3=00000000 
DR6=ffff0ff0 DR7=00000400
EFER=0000000000000000
Triple fault.  Halting for inspection via QEMU monitor.

根据 EIP=00800bc3 查找 hello.asm

  800bbd:	89 c3                	mov    %eax,%ebx
  800bbf:	89 c7                	mov    %eax,%edi
  800bc1:	89 c6                	mov    %eax,%esi
  800bc3:	cd 30                	int    $0x30
	syscall(SYS_cputs, 0, (uint32_t)s, len, 0, 0, 0);
}
  800bc5:	5b                   	pop    %ebx

看来报错是正常的,因为目前 JOS 还不支持完整的中断和异常处理。

2.4、Handing Interrupts and Exceptions

在 JOS 中实现异常和系统调用处理。这样内核才能从用户态中接过控制权。

阅读材料:

这里推荐阅读 Intel 的手册。

2.5、Basic of Protected Control Transfer

Exceptions and interrupts are both “protected control transfers,” which cause the processor to switch from user to kernel mode (CPL=0) without giving the user-mode code any opportunity to interfere with the functioning of the kernel or other environments.

在 x86 中,当系统发生异常或者处理器接收到中断后,转去执行相应的 handler,执行哪个 handler 不由用户程序决定,而是通过以下两个机制来决定:

在 IDT 中,指定了 256 个进入 kernel 的入口点,它们对应着不同的中断或异常。IDT 的内容是由 kernel 编程。

大多时候,执行 handler 后还需要回到用户态, 继续执行被打断的用户程序。这就需要在进入内核态前,保存下当时的处理器状态。在 JOS 中,我们将这些状态保存在进程的内核栈里,内核栈的位置由 TSS.SSO 和 TSS.ESP0 指定。

2.6、Type of Exceptions and Interrupts

异常通常对应 IDT 0~31 的范围,剩下的 32~255 范围则通常对应软中断(INT n)和硬中断(external device)。

在这一小节中,我们为 JOS 添加相应的异常处理;下一小节则添加系统调用处理(INT 0x30);在 lab4 中添加硬中断处理(如时钟中断)。

2.7、Example

假设一个在用户态下的程序执行了除以 0 的操作(处理器内部异常)。

+-------------+ <- KSTACKTOP
| 0x00 |old SS|
+-------------+
|   old ESP   |
+-------------+
|  old EFLAGS |
+-------------+
| 0x00 |old CS|
+-------------+
|   old EIP   |
+-------------+ <- ESP = KSTACKTOP-20

查看 Intel 手册发现,有些异常还会压一个 error code 到内核栈上:

+------------------------+-----+----------+
|      Description       | Num |Error Code| 
+------------------------+-----+----------+
|      System error      |  8  |   Yse(0) |
+------------------------+-----+----------+
|      Invalid TSS       | 10  |   Yes    |
+------------------------+-----+----------+
|  Segment not present   | 11  |   Yes    |
+------------------------+-----+----------+
|    Stack exception     | 12  |   Yes    |
+------------------------+-----+----------+
|General protection fault| 13  |   Yes    |
+------------------------+-----+----------+
|      Page fault        | 14  |   Yes    |
+------------------------+-----+----------+
|    Alignment Check     | 17  |   Yes(0) |
+------------------------+-----+----------+

这种情况内核栈如下:

+-------------+ <- KSTACKTOP
| 0x00 |old SS|
+-------------+
|   old ESP   |
+-------------+
|  old EFLAGS |
+-------------+
| 0x00 |old CS|
+-------------+
|   old EIP   |
+-------------+
| error code  |
+-------------+ <- ESP = KSTACKTOP-24

2.8、Nested Exceptions and Interrupts

异常和中断既能发生在用户态,也能发生在内核态。当中断和异常发生在内核态时,对于嵌套异常的处理会更优雅。这种情况下,内核栈如下:

+-------------+ <- KSTACKTOP
|  old EFLAGS |
+-------------+
| 0x00 |old CS|
+-------------+
|   old EIP   |
+-------------+
| error code  |
+-------------+ <- ESP = KSTACKTOP-16

即已经在内核中发生中断或者异常的情况下,不会将 SS 和 ESP 压栈,也即不会切换栈。

有一种极端情况,那就是当内核栈不够用的时候,内核必须能够适当的处理这种情况。

2.9、Setting Up the IDT

头文件 inc/trap.hkern/trap.h 里包含了与异常中断相关重要的定义,前者对用户态程序使用,后者则是内核开发使用。

     IDT          trapentry.S       trap.c
+------------+                        
| &handler1  | -> handler1:         trap (struct Trapframe *tf)
|            |      // do stuff     {
|            |      call trap         // handle the exception/interrupt
|            |      // ...          }
+------------+
| &handler2  | -> handler2:
|            |      // do stuff
|            |      call trap
|            |      // ...
+------------+
     .
     .
+------------+
| &handlerX  | -> handlerX:
|            |       // do stuff
|            |       call trap
|            |       // ...
+------------+

每个异常或中断都应该有自己的处理函数。在 trapentry.Strap_init() 中使用处理函数的地址来初始化 IDT。

2.9.1、Exercise 4

在 xv6 中使用 perl 脚本来生成所有入口(0~255),见 xv6/vectors.pl。而在 JOS 中则使用两个宏 TRAPHANDLERTRAPHANDLER_NOEC 来生成。结合 inc/trap.h,写出所有能用到的入口:

/*
 * Lab 3: Your code here for generating entry points for the different traps.
 */
TRAPHANDLER_NOEC(DIVIDE, T_DIVIDE)
TRAPHANDLER_NOEC(DEBUG, T_DEBUG)
TRAPHANDLER_NOEC(NMI, T_NMI)
TRAPHANDLER_NOEC(BRKPT, T_BRKPT)
TRAPHANDLER_NOEC(OFLOW, T_OFLOW)
TRAPHANDLER_NOEC(BOUND, T_BOUND)
TRAPHANDLER_NOEC(ILLOP, T_ILLOP)
TRAPHANDLER_NOEC(DEVICE, T_DEVICE)
TRAPHANDLER(DBLFLT, T_DBLFLT)
TRAPHANDLER(TSS, T_TSS)
TRAPHANDLER(SEGNP, T_SEGNP)
TRAPHANDLER(STACK, T_STACK)
TRAPHANDLER(GPFLT, T_GPFLT)
TRAPHANDLER(PGFLT, T_PGFLT)
TRAPHANDLER_NOEC(FPERR, T_FPERR)
TRAPHANDLER(ALIGN, T_ALIGN)
TRAPHANDLER_NOEC(MCHK, T_MCHK)
TRAPHANDLER_NOEC(SIMDERR, T_SIMDERR)
TRAPHANDLER_NOEC(SYSCALL, T_SYSCALL)
TRAPHANDLER_NOEC(DEFAULT, T_DEFAULT)

当异常或中断选择一个宏入口后,执行 jmp _alltraps。对比 xv6 与 JOS 中的 trapframe,xv6 要比 JOS 多压两个寄存器(%fs和%gs)。我们可以类比 xv6/trapasm.S,写出 JOS 的 alltrap:

/*
 * Lab 3: Your code here for _alltraps
 */
.globl _alltraps
_alltraps:
  # Build trap frame.
  pushl %ds
  pushl %es
  pushal 
  # Set up data segments.
  # set up processor to run kernel C code, trap()
  movw $(GD_KD), %ax
  movw %ax, %ds
  movw %ax, %es

  # Call trap(tf), where tf=%esp
  pushl %esp       # create an argument for trap(tf)
  call trap

最后,使用宏 SETGATEtrap_init() 中初始化 IDT,每个 entry 指向 trapentry.S:

// LAB 3: Your code here.
void DIVIDE();
void DEBUG();
void NMI();
void BRKPT();
void OFLOW();
void BOUND();
void ILLOP();
void DEVICE();
void DBLFLT();
void TSS();
void SEGNP();
void STACK();
void GPFLT();
void PGFLT();
void FPERR();
void ALIGN();
void MCHK();
void SIMDERR();
void SYSCALL();
void DEFAULT();
SETGATE(idt[T_DIVIDE], 0, GD_KT, DIVIDE, 0);
SETGATE(idt[T_DEBUG], 0, GD_KT, DEBUG, 0);
SETGATE(idt[T_NMI], 0, GD_KT, NMI, 0);
SETGATE(idt[T_BRKPT], 0, GD_KT, BRKPT, 0);
SETGATE(idt[T_OFLOW], 0, GD_KT, OFLOW, 0);
SETGATE(idt[T_BOUND], 0, GD_KT, BOUND, 0);
SETGATE(idt[T_ILLOP], 0, GD_KT, ILLOP, 0);
SETGATE(idt[T_DEVICE], 0, GD_KT, DEVICE, 0);
SETGATE(idt[T_DBLFLT], 0, GD_KT, DBLFLT, 0);
SETGATE(idt[T_TSS], 0, GD_KT, TSS, 0);
SETGATE(idt[T_SEGNP], 0, GD_KT, SEGNP, 0);
SETGATE(idt[T_STACK], 0, GD_KT, STACK, 0);
SETGATE(idt[T_GPFLT], 0, GD_KT, GPFLT, 0);
SETGATE(idt[T_PGFLT], 0, GD_KT, PGFLT, 0);
SETGATE(idt[T_FPERR], 0, GD_KT, FPERR, 0);
SETGATE(idt[T_ALIGN], 0, GD_KT, ALIGN, 0);
SETGATE(idt[T_MCHK], 0, GD_KT, MCHK, 0);
SETGATE(idt[T_SIMDERR], 0, GD_KT, SIMDERR, 0);
SETGATE(idt[T_SYSCALL], 1, GD_KT, SYSCALL, 3);
SETGATE(idt[T_DEFAULT], 0, GD_KT, DEFAULT, 0);

注意第 T_SYSCALL 号 entry 是一个陷阱门,其余都是中断门。

整个流程是,查询 IDT,定位到具体 entry,通过 entry 的 Offset 字段去 trapentry.S 中定位到具体的汇编,最后来到所有中断异常都会通过的 _alltrap 入口,将寄存器压栈,最后 call trap 执行内核函数。

wu@wu-insparition:~/6.828/lab$ ./grade-lab3
+ cc kern/init.c
+ ld obj/kern/kernel
+ mk obj/kern/kernel.img
divzero: OK (1.5s) 
softint: OK (1.0s) 
badsegment: OK (0.9s) 
Part A score: 30/30

需要注意的是,由于这个实验是根据终端打印字符串匹配情况来给分。所以在代码中最好不要有多余的打印语句,否则即使代码逻辑正确,由于多了一处打印,最终还是不能通过。

2.9.2、Challenge

不影响后续实验,暂时跳过。

2.9.3、Q & A

What is the purpose of having an individual handler function for each exception/interrupt?

不同异常/中断的处理逻辑是不同的,分开的话有助于理解代码逻辑。

The grade script expects it to produce a general protection fault (trap 13), but softint’s code says int $14. Why should this produce interrupt vector 13?

在上面设置中断/异常门的时候,对于 IDT.DPL 域,注释中是这样解释的:

Descriptor Privilege Level: the privilege level required for software to invoke this interrupt/trap gate explicitly using an int instruction.

对于目前来说,我们配置了的中断,只有第 48 号 T_SYSCALL 可以在用户态下,在用户程序中执行 int $48 来产生。这么做也是合理的,要是一个用户程序都能随意的产生页异常,那操作系统岂不是大乱了。

 

三、Part B: Page Faults,Breakpoints Exceptions and System Calls


3.1、Handling Page Faults

下面我们来完善 Page Fault Exception。当发生 T_PGFLT 后,系统会将触发 T_PGFLT 的线性地址存放在 CR2 中。

3.1.1、Exercise 5

Modify trap_dispatch() to dispatch page fault exceptions to page_fault_handler(). You should now be able to get make grade to succeed on the faultread, faultreadkernel, faultwrite, and faultwritekernel tests. If any of them don’t work, figure out why and fix them. Remember that you can boot JOS into a particular user program using make run-x or make run-x-nox. For instance, make run-hello-nox runs the hello user program.

这里我们参考 xv6/trap.c 中 trap() 函数的实现。

static void trap_dispatch(struct Trapframe *tf)
{
	switch (tf->tf_trapno)
	{
	case T_PGFLT:
		page_fault_handler(tf);
		return;
		break;
	
	default:
		break;
	}
  ...
}
wu@wu-insparition:~/6.828/lab$ ./grade-lab3
+ cc kern/init.c
+ ld obj/kern/kernel
+ mk obj/kern/kernel.img
divzero: OK (2.3s) 
softint: OK (2.0s) 
badsegment: OK (1.8s) 
Part A score: 30/30

faultread: OK (2.2s) 
faultreadkernel: OK (1.8s) 
faultwrite: OK (2.1s) 
faultwritekernel: OK (2.1s)

看来实现没问题。下面用一张图来总结一下目前位置中断/异常的处理逻辑:

        +--------+----------+-------+---------+
        | entry0 |  entry1  |  ...  | entry255| IDT
        +----+---+-----+----+-------+---------+
             |         |
             v         v
        +----+---------+---+--------+---------+
        |DIVIDE()| DEBUG() |   ...  |         |
        +----+---------+---+--------+---------+
             |         |
             v         v
        +----+---+-----+---+--------+---------+
        |DIVIDE: | DEBUG:  |  ...   |         |
        +----+---+------+--+--------+---------+
             |          |
             |          |
             +-------v  v
                    +---+------+
                    | alltrap: |
                    +-----+----+
                          |
                    +-----v----+
                    |  trap()  |
                    +--+--+----+
                       |  |
       v---------------+  v
+----------------+--------+------+-----+---------------+
|DIVIDE_HANDLER()|DEBUG_HANDLER()|...  |               |
+----------------+---------------+-----+---------------+

3.2、The Breakpoints Exception

The breakpoint exception, interrupt vector 3 (T_BRKPT), is normally used to allow debuggers to insert breakpoints in a program’s code by temporarily replacing the relevant program instruction with the special 1-byte int3 software interrupt instruction.

3.2.1、Exercise 6

Modify trap_dispatch() to make breakpoint exceptions invoke the kernel monitor. You should now be able to get make grade to succeed on the breakpoint test.

static void trap_dispatch(struct Trapframe *tf)
{
  ...
	case T_BRKPT:
		monitor(tf);
		return;
		break;
	...
}

因为在 breakpoint.c 中执行 int $3,此时第 3 号中断门不允许用户程序进入内核。所以,需要将该中断门修改为:

SETGATE(idt[T_BRKPT], 0, GD_KT, BRKPT, 3);
wu@wu-insparition:~/6.828/lab$ ./grade-lab3
+ cc kern/init.c
+ ld obj/kern/kernel
+ mk obj/kern/kernel.img
divzero: OK (1.9s) 
softint: OK (2.3s) 
badsegment: OK (2.0s) 
Part A score: 30/30

faultread: OK (0.9s) 
faultreadkernel: OK (1.8s) 
faultwrite: OK (2.1s) 
faultwritekernel: OK (1.9s) 
breakpoint: OK (2.1s) 

3.2.2、Challenge

Challenge! Modify the JOS kernel monitor so that you can ‘continue’ execution from the current location (e.g., after the int3, if the kernel monitor was invoked via the breakpoint exception), and so that you can single-step one instruction at a time. You will need to understand certain bits of the EFLAGS register in order to implement single-stepping.

TODO

3.2.3、Optional

If you’re feeling really adventurous, find some x86 disassembler source code - e.g., by ripping it out of QEMU, or out of GNU binutils, or just write it yourself - and extend the JOS kernel monitor to be able to disassemble and display instructions as you are stepping through them. Combined with the symbol table loading from lab 1, this is the stuff of which real kernel debuggers are made.

TODO

3.2.4、Q & A

The break point test case will either generate a break point exception or a general protection fault depending on how you initialized the break point entry in the IDT (i.e., your call to SETGATE from trap_init). Why? How do you need to set it up in order to get the breakpoint exception to work as specified above and what incorrect setup would cause it to trigger a general protection fault?

这个问题上面已经回答过了。

What do you think is the point of these mechanisms, particularly in light of what the user/softint test program does?

这么做是为了防止用户程序越权,会破坏系统的安全性。

3.3、System Call

在 JOS 中,使用 int $0x30 来触发系统调用软中断。而在 xv6 中,则使用 int 0x40。允许用户程序执行 int $0x30,所以对应的中断描述符应为:

SETGATE(idt[T_SYSCALL], 1, GD_KT, SYSCALL, 3);

而且,这是一个 trap gate,与 interrupt gate 不同的是,在将寄存器值压入内核栈后,trap gate 不会将 EFLAGS.IF 置 0。

The application will pass the system call number and the system call arguments in registers. This way, the kernel won’t need to grub around in the user environment’s stack or instruction stream. The system call number will go in %eax, and the arguments (up to five of them) will go in %edx, %ecx, %ebx, %edi, and %esi, respectively. The kernel passes the return value back in %eax.

看来 JOS 与 xv6 二者系统调用的实现有很大的区别。在 xv6 中,系统调用的参数是放在用户栈上,而不是寄存器中:

int argint(int n, int *ip)
{
  uint addr = (myproc()->tf->esp) + 4 + 4 * n
  struct proc *curproc = myproc();
  if (addr >= curproc->sz || addr + 4 > curproc->sz) 
    return -1;
  *ip = *(int *)(addr);
  return 0;
}

这个函数(结合xv6/syscall.c中的两个函数)在当前运行的进程的 addr 地址处取一个 int 出来。可以看出,xv6 中系统调用的参数是去用户栈上取到的。

下面看一下 JOS 中用户态系统调用函数的实现(lib/syscall.c):

static inline int32_t syscall(int num, int check, uint32_t a1, uint32_t a2, uint32_t a3, uint32_t a4, uint32_t a5)
{
	int32_t ret;

	asm volatile("int %1\n"   // %1 对应 i(立即数),int $30
		     : "=a" (ret)       // 返回值存放在 ret 中
		     : "i" (T_SYSCALL),
		       "a" (num),       // 指明哪个系统调用
		       "d" (a1),        // edx
		       "c" (a2),        // ecx
		       "b" (a3),        // ebx
		       "D" (a4),        // edi
		       "S" (a5)         // esi
		     : "cc", "memory"); // 条件码和内存值可能会被修改

	if(check && ret > 0)
		panic("syscall %d returned %d (> 0)", num, ret);

	return ret;
}

The “volatile” tells the assembler not to optimize this instruction away just because we don’t use the return value.

关于内联汇编,可以看我的一篇博文:GCC Inline Assembly HOWTO[译]

用户态的所有系统调用 sys_ 都汇聚到 lib/syscall.c/syscall(),将参数放进相应寄存器,然后执行 int 0x30,通过第 48 号陷阱门进入内核。

3.3.1、Exercise 7

下面这张图有助于梳理 JOS 中系统调用的逻辑:

+----------------------------------------+
|       +-----------------------+        |
|       | lib/syscall.c/sys_*() |        |
|       +-----------+-----------+        |
|                   |                    |
|                   v                    | User Mode
|      +------------+------------+       |
|      | lib/syscall.c/syscall() |       |
|      +------------+------------+       |
|                   |                    |
+-------------------+--------------------+
                    |
+-------------------+--------------------+
|                   |IDT                 |
|                   |alltrap:            |
|          +--------v--------+           |
|          | lib/kern/trap() |           |
|          +--------+--------+           |
|                   |trap_dispatch()     | Kernel Mode
|                   v                    |
|         +---------+----------+         |
|         | lib/kern/syscall() |         |
|         +--------------------+         |
+----------------------------------------+

理清后开始完成代码:

static void trap_dispatch(struct Trapframe *tf)
{
  ...
	case T_SYSCALL:
		(tf->tf_regs).reg_eax = 
				(uint32_t)syscall((tf->tf_regs).reg_eax,
				          (tf->tf_regs).reg_edx,
				          (tf->tf_regs).reg_ecx,
				          (tf->tf_regs).reg_ebx,
				          (tf->tf_regs).reg_edi, 
				          (tf->tf_regs).reg_esi);
		return;
		break;

	...
}

注意,这里的参数顺序要与在用户态保存参数的顺序一致。

int32_t syscall(uint32_t syscallno, uint32_t a1, uint32_t a2, uint32_t a3, uint32_t a4, uint32_t a5)
{
	switch (syscallno) {
	    case SYS_cgetc:
	        sys_cgetc();
	    	return 0;
	    case SYS_cputs:
	    	sys_cputs((const char *)a1, (size_t)a2);
	    	return 0;
	    case SYS_getenvid:
	    	sys_getenvid();
	    	return 0;
	    case SYS_env_destroy:
	    	sys_env_destroy((envid_t)a1);
	    	return 0;
		case NSYSCALLS:
		    return 0;
	    default:
	    	return -E_INVAL;
	}
}

最后实现 sys_cputs 函数:

static void sys_cputs(const char *s, size_t len)
{
	if ((curenv->env_tf).tf_cs & 3)
		user_mem_assert(curenv, s, len, 0);
	cprintf("%.*s", len, s);
}
wu@wu-insparition:~/6.828/lab$ make run-hello-nox
...
hello, world
...
  trap 0x0000000e Page Fault
...
Welcome to the JOS kernel monitor!
Type 'help' for a list of commands.
K>

3.3.2、Challenge

TODO

3.4、User Mode Startup

JOS 中用户程序的运行逻辑,就是在编译 kernel 的时候将二进制文件内嵌进 kernel(因为目前没有文件系统),在 kern/init.c/i386_init() 中指定加载 usr/ 下的哪一个文件。加载的文件被放进新创建的进程环境里运行。

   +--------------------+
   | lib/entry.S:_start | 新进程第一条指令处
   +----------+---------+
              |
              |
+-------------v------------+
| lib/entry.S:call libmain |
+-------------+------------+
              |
              |
       +------v------+
       |   umain()   |
       +-------------+

3.4.1、Exercise 8

把当前系统中正在运行的进程指针,赋值给正在执行的用户程序(建立进程与运行二进制文件的关系)。

void libmain(int argc, char **argv)
{
  ...
	envid_t envid = sys_getenvid();
	thisenv = envs + ENVX(envid);
  ...
}
wu@wu-insparition:~/6.828/lab$ make qemu-nox
...
hello, world
Incoming TRAP frame at 0xefffffbc
i am environment 00001000
Incoming TRAP frame at 0xefffffbc
[00001000] exiting gracefully
[00001000] free env 00001000
...

3.5、Page faults and memory protection

在 kernel 中发生 Page Fault 比在用户程序用发生 Page Fault 要严重得多。在实现 JOS 系统调用的过程中,用户程序会向 kernel 传一些参数,如果这些参数包含一个非法指针,让 kernel 对此指针进行解引用,会造成严重的错误。所以我们应该在 kernel 添加一个检查类似错误的功能。

3.5.1、Exercise 9

Change kern/trap.c to panic if a page fault happens in kernel mode.

void page_fault_handler(struct Trapframe *tf)
{
  ...
	if (tf->tf_cs & 0)
		panic("Page-Fault happen in kernel mode at %x\n", fault_va);
  ...
}

Read user_mem_assert() in kern/pmap.c and implement user_mem_check() in that same file.

int user_mem_check(struct Env *env, const void *va, size_t len, int perm)
{
	uint32_t va_start = (uint32_t)ROUNDDOWN((void *)va, PGSIZE);
	uint32_t va_end = (uint32_t)ROUNDUP((void *)(va + len), PGSIZE);
	for (; va_start < va_end; va_start += PGSIZE)
	{
		pte_t *pte = pgdir_walk(env->env_pgdir, (void *)va_start, 0);
		if (ULIM <= va_start || !pte || !(*pte & PTE_P) || (*pte & perm) == 0 )
		{
			user_mem_check_addr = va_start > (uint32_t)va ? va_start : (uint32_t)va;
			return -E_FAULT;		
		}
	}
	return 0;
}

注意最后给 user_mem_check_addr 变量赋值,应该是最早发生错误的地址。

+--------+
|        |
|        |
|        |
+--------+ <-+ va_end
|        |
|XXXXXXXX| <-+ va + len
|XXXXXXXX|
+--------+
|XXXXXXXX|
|XXXXXXXX| <-+ va
|        |
+--------+ <-+ va_start
|        |
|        |
+--------+

Finally, change debuginfo_eip in kern/kdebug.c to call user_mem_check on usd, stabs, and stabstr.

int debuginfo_eip(uintptr_t addr, struct Eipdebuginfo *info)
{
  	if (user_mem_check(curenv, usd, sizeof(struct UserStabData), PTE_U | PTE_P) != 0)
		return -1;		
    ...
		if (user_mem_check(curenv, stabs, (stab_end - stabs) * sizeof(struct Stab), PTE_U | PTE_P) != 0)
			return -1;
		if (user_mem_check(curenv, stabstr, stabstr_end - stabstr, PTE_U | PTE_P) != 0)
			return -1;
}
wu@wu-insparition:~/6.828/lab$ ./grade-lab3
+ cc kern/init.c
+ ld obj/kern/kernel
+ mk obj/kern/kernel.img
divzero: OK (1.9s) 
softint: OK (1.2s) 
badsegment: OK (1.8s) 
Part A score: 30/30

faultread: OK (2.1s) 
faultreadkernel: OK (1.2s) 
faultwrite: OK (1.7s) 
faultwritekernel: OK (2.2s) 
breakpoint: OK (1.8s) 
testbss: OK (2.2s) 
hello: OK (1.8s) 
buggyhello: OK (2.0s) 
buggyhello2: OK (2.1s) 
evilhello: OK (1.8s) 
Part B score: 50/50

Score: 80/80

lab3 完成。