6.828 -- JOS操作系统实验

环境准备

可以使用docker准备环境，这样既方便，又不怕把自己的环境搞得乱七八糟的。而且如果换台电脑，也能很快的搭好。dockerfile如下:

FROM ubuntu:14.04

RUN apt-get update &&  apt-get install -y build-essential gdb zlib1g-dev pkg-config libglib2.0-dev binutils-dev libboost-all-dev autoconf libtool libssl-dev libpixman-1-dev libpython-dev python-pip git vim wget gcc-multilib

RUN git clone https://github.com/mit-pdos/6.828-qemu.git ~/qemu

RUN cd ~/qemu && ./configure --disable-kvm --disable-werror --prefix="/usr/local" --target-list="i386-softmmu x86_64-softmmu" && make && make install

RUN rm -rf ~/qemu
# run command: docker run -it -v /your_path:/home/ --name jos --privileged ubuntujos:v1 /bin/bash

这里说一下run command，”/your_path”是你本机实验lab代码的路径。以后编辑可以在本机进行代码编辑。进入docker，在docker进行编译并运行。当然，docker一般不带页面，所以执行是使用qemu都要加-nox，这个是要注意的。

Lab1 系统中的一些重要概念

kernel.img的构成

1.1 Make Boot, ld set Text At 0x7c00 then extract the text, fill with 0x00, end at 0x0510

1.2 Make kernel seg, ld kernal seg at PhyAddr 0x100000, but Logic Addr 0x0f100000

1.3 Link two segments by using dd command

+-------+----------------------------------------------------------+
|       |                                                          |
| boot  |                     kernel seg(ELF Format)               |
|       |                                                          |
+------------------------------------------------------------------+
^       ^
|       |
|       |
|       512B
|       |
|       |
|       PHY:0x100000 (logic 0x0f100000)
PHY:0x7c00

ELF Foramt

                  +-----------------------------+
                  |                             |
           +------+                             +-----------+
           |      |     ELF HEADER              |           |
           |      |                             |           |
           |      |                             |           |
           +----->+-----------------------------+           |
      +-----------+     Program Header 1        |           |
      |           +-----------------------------+           |
+-----------------+     Program Header 2        |           |
|     |           +-----------------------------+           |
|     |           |             .               |           |
|     |           |             .               |           |
|     |           |             .               |           |
|     |           +-----------------------------+           |
|     |    +------+     Program Header N        +           |
|     |    |      +-----------------------------+           |
|     +---------->+     PROGRAM SEG 1           |           |
|          |      |                             |<-------+  |
|          |      +-----------------------------+        |  |
|          |      |                             |        |  |
+---------------->+     PROGRAM SEG 2           +<----+  |  |
           |      |                             |     |  |  |
           |      +-----------------------------+     |  |  |
           |      |             .               |     |  |  |
           |      |             .               |     |  |  |
           |      |             .               |     |  |  |
           |      +-----------------------------+     |  |  |
           +----->+     PROGRAM SEG n           |     |  |  |
                  |                             <--+  |  |  |
                  +-----------------------------+  |  |  |  |
                  |                             <-----------+
                  |   SETCTION HEADER 1..N      |--|  |  |
                  |                             +-----+--+
                  +-----------------------------+

载入时根据ELFheader的信息载入program head，再根据program head的信息将每段program载入近内存。offset时针对变异出的二进制文件的byte位移。

分页

                                                 +------------+
                             +------------+      |            |
                             |            |      |            |
                             |            |PADDR |            |
                       +---->+            +----->+ PAGE 4KB   |
                       |     |PAGE table 1|      |            |
                       |     |            +--+   |            |
                       |     |            +--|   |            |
                       |     |            | ||   +------------+
+--------------+       |     +------------+ ||
|              +-------+                    ||   +------------+
|              |                            ||   |            |
|              |             +------------+ ||   |            |
|              +--------+    |            | |+-->+            |
|              |        |    |            | |    | PAGE 4KB   |
|PAGE directory|        +--->+            | |    |            |
|              |             |            | |    |            |
|              |             |PAGE table 2| |    |            |
|              +----+        |            | |    +------------+
+--------------+    |        |            | |
                    |        |            | |    +------------+
                    |        +------------+ |    |            |
                    |                       |    |            |
                    |              .        |    |            |
                    |              .        +--->+  PAGE 4KB  |
                    |              .             |            |
                    |              .             |            |
                    |              .             |            |
                    |              .             +------------+
                    |
                    |
                    |        +------------+
                    |        |            |
                    |        |            |
                    |        |            |
                    |        |            |
                    +------->+PAGE table n|
                             |            |
                             |            |
                             |            |
                             +------------+

这里时32位的分页系统，page dir 10位，page table 10位，page 12位。page table 中，存储的位page 的start Address 一般与2^12对其进行。还存放是否存在，读写权限等等。

开启分页机制

# Load the physical address of entry_pgdir into cr3.  entry_pgdir
	# is defined in entrypgdir.c.
	movl	$(RELOC(entry_pgdir)), %eax
	movl	%eax, %cr3
	# Turn on paging.
	movl	%cr0, %eax
	orl	$(CR0_PE|CR0_PG|CR0_WP), %eax
	movl	%eax, %cr0

调用栈这个图非常的重要，在后续会人为的制作调用栈来构建跳转，参数传递等。

          +------------------+ +-------------+
   +------+    last epb      |
   |      +------------------+
   |      |   local arg1     |   High Addr
   |      +------------------+
   |      |   local arg2     |
   |      +------------------+       ^
   |      |     ... ...      |       |
   |   F  +------------------+       |
   |   R  |   local arg(N)   |       |
   |   A  +------------------+       |
   |   M  |      arg(N)      |       |
   |   E  +------------------+       |
   |      |      arg(N-1)    |       |
   |      +------------------+       |
   |      |     ... ...      |       |
   |      +------------------+       |
   |      |      arg1        |       |
   |      +------------------+       |
   +------+  eip(ret addr)   |       |
          +------------------+       |
          |    last epb      |       +
          +------------------+
          |   local arg1     |
          +------------------+   Low AddR
          |     ... ...      |
          +------------------+
          |   NEXT FRAME     |
          +------------------+ +-------------+

Lab 2 Memory Management

lab2 主要使用内存的初始化以及管理,大致分为

收集硬件信息，判断总过又多少物理内存可以使用。【i386_detect_memory()】
给相应的内核信息分配内存,比如内核页目录(kern_pgdir)，页属性信息(pages)，进程信息(envs)。【boot_alloc()】
对页属性进行初始化【page_init】，后边不管内核，还是进程获取新物理内存时，内核都会通过根据pages中的信息，进行分配。初始化时将所有被第2步分配的页，内核所占的页都标记位使用。所有未被使用的，成为一个page_free_list指向的空闲页链表。后续分配从这个链表中分配空闲页，后续被释放的页，也会被插入这个空闲页链表中，可进行后续的分配。
将内核的相关信息【页属性信息(pages)，进程信息(envs)，内核栈信息， kernbase】等，的地址写入到内核页目录(kern_pgdir)中，以便通过虚拟地址(线性地址)直接访问。使用的boot_map_region函数。
将kern_pgdir加载如cr3中，开启分页。

boot_map_region 多一些解释，其中使用到了page_walk 这个函数，此函数主要作用就是位某个虚拟地址，获取其映射的PTE的信息。由于此期实验涉及到两级分页系统（页目录，页表，页），所以page_walk会根据所需要映射的虚拟地址，现在页目录中查找对应的页目录项(虚拟内存0-9位)，根据页目录项找对应的页表项(10-19位)。没有对应的页目录项，也就意味着需要page_alloc来分配一个页表(如果page_walk的create为true的话)。page_insert这个函数也比较重要，page_insert有点映射的意味在，vaddr1与vaddr2可能地址不同，但对应的页相同，信息也相同。

Lab 2一定要对分页系统了解清楚，在后边的实验中，涉及到进程fork的COW，IPC等。如果Lab2没有搞清，会遇到很多问题。

Lab3 User Environments

lab3 主要是在kernel初始化后，怎样创建用户环境的(进程)，以及初始中断和系统调用的。

对envs中所有的进程信息进行初始化，跟页信息pages差不多，初始的每个进程都放在env_free_list中，分配时从env_free_list中选，destroy了后被插入到env_free_list中，用作后续分配。(这里说一下，env_free_list根据envid从小到达插入，因为是envs[evnidx]这个获取env信息)。
完成create后，就要给这个进程分配空间，然后将二进制的代码映射到这个进程自己的地址空间。每个进程都有自己的e->env_pgdir。env_pgdir其实就是这个进程自己的地址空间。A env和B env 的入口可能都是0x80000000,但是对应内容是不一样的(物理页不同)。二进制代码即解析elf，判断ELF_PROG_LOAD和ELF_PROG_FLAG_WRITE的program segments，并初始化栈。
env_run执行可以运行的环境（或者进程），将当前正在进行的置为RUNNABLE，再将传入的置为RUNNING。这个有个比较巧妙的是lcr3(PADDR(curenv->env_pgdir))，先将内核的地址空间变为这个进程的地址空间，再使用env_pop_tf，将eip切换为这个进程的。还原这个进程所有的寄存器信息，这样就形成了内核态到用户态的转变。
trap初始，就是将中断号与中断对应的处理函数做映射。这里需要注意一点就是SETGATE中的istrap，如果是interrupt，那么会重制eflag中的IF标记为，标记为不可中断。trap的话IF不会被重制。
要把所有trap都放在一个公共函数中集中处理，这里涉及到了trapentry.S中的_alltraps函数。_alltraps 是所有中断函数的最后一道处理程序，即将寄存器信息储存，并将段寄存器信息变为内核态。然后调用C函数入口trap(struct Trapframe *tf)。
接着把所有系统调用的归类到syscall中。并按照用户在调用寄存器是指定的参数顺序将syscall中的参数填写完整。syscall是带返回值的，而且根据gcc的逻辑，会将返回值写到eax中。那么syscall的返回值就写到tf->tf_regs.reg_eax中。

Lab4 Preemptive Multitasking

lab4 第一完成一个能跑在多核下的操作系统。第二完在用户态实现fork进程，并实现copy-on-write。第三实现多进程与进程间通信。

修改以前单核逻辑的代码。首先多核使用也不是一上来就是多核并行。是由一个核最先将该初始化的东西都初始化成功。待主内核信息初始化后，将所有用的到核挨个进行初始化[boot_aps],其中boot_aps中将mpentry_start与mpentry_end地址的所有代码移到KADDR(MPENTRY_PADDR)的内存中，然后将所有AP处理器的eip都指向这个地址。mpentry_start在mpentry.S中进行定义。然后mpentry.S中可以看到，最后进入了mp_main中，初始化每个AP处理器中的trap，段寄存器等。强调一点，为了保证并行数据的安全性，所有cpu在运行内核态代码时，都要获取锁，推出时释放保证临界资源的安全性。当然，实验的比较简单，一把大锁锁住所有资源。实验的challenge中提到现实的OS会根据不同的资源使用不同的锁，换句话说就是使用细粒度的锁提高性能。
轮转调度。很简单的调度算法，就是每个进程根据时间片的运行时间雨露均沾，每个进程在用户态的时间是完全相等的。调度函数为sched_yield。谁调用了sched_yield，就意味着进程可能被切换。可以看到后边时间中断，env_destroy，等会有调用。【如果了解协程的话，跟协程的coro_yield差不多】。
为fork进程作准备，在fork时，需要完成以下的系统调用才能完整的fork出一个子进程。（这里说一下，系统调用中，如果envid传0，那么指的是当前env，这个坑lab5才发现）

3.1 sys_exofork 主要为alloc_envs，分配一个进程信息。

3.2 sys_env_set_status 设置系统状态，主要是父进程在创建完后，让子进程变得可运行（RUNNABLE）。

3.3 sys_page_alloc 为执行的进程分配一页内存。

3.4 sys_page_map 页映射，将A进程的a地址映射到B进程的b地址。

3.5 sys_page_unmap 将某个进程的某个地址映射物理页取消。

fork要做的就是首先先创建一个子进程，将基本的子进程信息填好，比如不可运行，子进程栈与页目录，cpu寄存器信息等【这里需要注意一点，而且unix-like系统中进程fork后父进程返回子进程pid，子进程返回0。父进程会在系统调用中下来的内核态使用sys_exofork系统调用返回的子进程进程号，如果一切顺利(lab3 中的第6点)。而子进程没有从系统调用中返回，eax也不会得到syscall的返回值。所以要在sys_exofork中的eax寄存器信息中专门制为0】。然后将自己所有的运行与数据信息给子进程都复制一份，包括自己的堆栈。这里用到了大量sys_page_alloc与sys_page_map。
Copy-On-Wirte, 这个概念就是从父进程中复制出来的很多内存子进程可能都不会去改，那用sys_page_map将父进程与子进程不同地址映射到同一个物理页不就好了。如果要改这个页的时候，咱再将这个物理页复制一份，再改复制的不久好了。换句话就是用到了再说，减少fork函数调用一次的系统开销，也尽可能的提高效率。为了实现这一点，需要实现分页中断处理。不复制了，那怎么做，给子进程COW是，给子进程的页表项的perm设置PTE_COW，给自己同样也要把PTE_W设置PTE_COW。子进程很好理解，父进程为什么也要呢？因为父进程也会修改，如果不给父进程触发重新分配，会影响到子进程的数据。所以不管谁先修改这个页，都需要拷贝。
还有一个比较trick的地方就是The UVPT。巧妙的使用了cpu的分页寻址机制，如图。这也是为什么在创建进程时e->env_pgdir[PDX(UVPT)] = PADDR(e->env_pgdir) | PTE_P | PTE_U;这个步骤的原因。uvpd其实也比较有意思。相当于PDX(la)与PTX(la)都要指向同一个物理页。页目录这样找：uvpd[PDX(vaddr)]，页表项这样找：uvpt[PGNUM(vaddr)]。
在以前如果尝试去写一个只读的物理页，会触发分页系统页中断。所以COW模式，需要先完成页中断的处理。_pgfault_upcall在这里作为所有处理页错误中断的模式。难点在处理完分页函数后，还原到用户态时的过程。
```
// exception stack:
//
//	trap-time esp
//	trap-time eflags
//	trap-time eip
//	utf_regs.reg_eax
//	...
//	utf_regs.reg_esi
//	utf_regs.reg_edi
//	utf_err (error code)
//	utf_fault_va            <-- %esp
```
首先跳过utf_err， utf_fault_va。然后 *(trap-time esp - 4) = trap-time eip, 还是那张图函数调用图，仔细体会，将栈数据人工修成gcc函数调用栈的样子。然后还原所有寄存器，然后将eflags还原【还原后，就不要做add sub计算了，否者eflag会有变化】，然后将esp指向trap-time esp，ret返回。
这里还要注意一点，就是在执行页处理函数是，还会有中断，或者函数调用，这里需要再处理页处理函数是一个临时的栈UXSTACKTOP。
进程间通信。进程间通信完成两个系统调用，一个是sys_ipc_try_send，另一个是sys_ipc_recv。就是一个接收一个等待的。通信由两种方式，一种是A向B传递一个值，另一个为A向B传递一个页映射。 ipc_try_send：如果接收方没准备好就死循环，如果准备好了看是传递值还是页映射，赋值传递，修改对方的进程为可执行（RUNNABLE）。 ipc_recv：将自己的ipc变为可接收，将自己的进程状态变为不可运行（ENV_NOT_RUNNABLE），交出运行时间[sched_yield()]。如果发送发将自己的进程状态改变为RUNNABLE，那么就可以在下次时钟中断后被轮询执行。

Lab5 File system, Spawn and Shell

JOS系统不同于早期使用宏内核的linux系统，JOS将文件系统作为一个用户态的进程，所有其他的进程需要进行文件访问，需要跟文件系统进行IPC通信。然后文件系统作为能够由I/O特权的进程进行I/O操作。

在创建文件系统这个进程时，使用ENV_TYPE_FS标记这个进程为文件系统，这样用户在找文件系统IPC时，能通过遍历进程找到文件系统的进程ID进行通信。同样，在创建时，在eflag中将这个进程标记FL_IOPL_3 IO权限。
文件系统在磁盘上的分布为一个block为一个文件系统分区，一个block为一页的大小——4KB。文件系统四大块，boot sector, superblock, bitmap, file/data block。boot sector为启动盘，superblock存储文件系统的总信息，比如文件系统magic number。磁盘总共由多少magic number，最重要的是文件根目录(“/”)的信息内容。有个root directory，我们才能找到文件系统上的所有文件与文件夹。bitmap，是记录整个磁盘在分块是，一共有做少块，以及块的使用情况。文件的元数据信息结构与早期linux稍有不同，JOS的文件系统只有一级寻址方式。
file文件进程与其他进程不同，它是将磁盘中的block与内存映射起来，换句话说，其他进程内存的映射空间是执行代码和alloc出来的内存。然而file进程将磁盘与内存映射。同样file进程的页错误处理函数跟其他用户进程是不同的，如果访问某个内存缺页了，那么它会从磁盘中读出指定的块，加载入内存，修改后页目录属性会被cpu修改（PTE_D），将修改的数据flush入磁盘。

文件系统整体接口

     Regular env           FS env
     +---------------+   +---------------+
     |      read     |   |   file_read   |
     |   (lib/fd.c)  |   |   (fs/fs.c)   |
  ...|.......|.......|...|.......^.......|...............
     |       v       |   |       |       | RPC mechanism
     |  devfile_read |   |  serve_read   |
     |  (lib/file.c) |   |  (fs/serv.c)  |
     |       |       |   |       ^       |
     |       v       |   |       |       |
     |     fsipc     |   |     serve     |
     |  (lib/file.c) |   |  (fs/serv.c)  |
     |       |       |   |       ^       |
     |       v       |   |       |       |
     |   ipc_send    |   |   ipc_recv    |
     |       |       |   |       ^       |
     +-------|-------+   +-------|-------+
             |                   |
             +-------------------+

文件进程对外暴露的接口是通过fsipc 进行IPC通信的几个操作,fsipc(unsigned type, void *dstva)

     union Fsipc {
     struct Fsreq_open {
         char req_path[MAXPATHLEN];
         int req_omode;
     } open;
     struct Fsreq_set_size {
         int req_fileid;
         off_t req_size;
     } set_size;
     struct Fsreq_read {
         int req_fileid;
         size_t req_n;
     } read;
     struct Fsret_read {
         char ret_buf[PGSIZE];
     } readRet;
     struct Fsreq_write {
         int req_fileid;
         size_t req_n;
         char req_buf[PGSIZE - (sizeof(int) + sizeof(size_t))];
     } write;
     struct Fsreq_stat {
         int req_fileid;
     } stat;
     struct Fsret_stat {
         char ret_name[MAXNAMELEN];
         off_t ret_size;
         int ret_isdir;
     } statRet;
     struct Fsreq_flush {
         int req_fileid;
     } flush;
     struct Fsreq_remove {
         char req_path[MAXPATHLEN];
     } remove;

     // Ensure Fsipc is one page
     char _pad[PGSIZE];
 };

都是一个IPC通信，传递过去一个页。只不过通过不同的类型，有不同的处理方式。

Spawning, 这个操作类似与fork，但与fork不同的是，fork是A进程根据自身复制一个一模一样的进程，而spawn是复制一个不同执行代码的进程。而执行代码可能就是放在文件系统中的一个二进制文件，后面可能有跟着这个进程初始时的一些参数。所以这里还要有一个设置进程的tfframde的系统调用来设置新进程的初始eip。还有一点不同的是，PTE_SHARE，这个进程会与其他的进程共享这个物理内存页。实验这里有一个挑战，就是实现一个linux的exec，即不是衍生一个新进程，而是把这个进程变一个新的执行代码。这里就需要一个系统调用，在陷入内核中是，kernel将这个进程的用户代码全部删掉，然后用读取新的代码，给这个进程换上。

shell其实就是运用了spawning。用户在shell输入需要执行的二进制文件以及这个文件需要的参数，shell进程就spawn用户想要打开的进程，将参数填入。这里shell会解读“>”,“

”等重定向符号。“>”其实就是sh打开后将标准输出重定向到打开的文件中。“｜”用pipe将两个进程相连。

Lab 6: Network Driver

根据e1000的特性，写一个网卡驱动。跟文件系统其实有点类似，一个是写硬盘，一个是写网卡buf，接收同理。这个lab中主要是怎样根据tick，实现sleep。查阅e1000硬件特性，怎样初始化网卡，buf写到哪里，怎样轮询读取等。

08 Dec 2020 by John Brown