MIT6.828操作系统工程Lab1-Booting a PC实验报告

本学期开设了操作系统的专业课。根据老师的介绍，下个学期的操作系统课设就是MIT的6.828的Labs，再加上团队老学长/同学的推荐，打算先在这个学期完成6.828，加深对于系统的理解。
Lab1 - Booting a PC是比较简单的实验，主要包括了引导、内核、控制台输出、以及栈。尽管如此，由于相关知识的缺失，我断断续续做了2周（2017年10月26日）才完成该实验。
2017年12月9日，完成了实验的提高部分并写完了报告。

实验准备

首先需要完成实验环境的搭建。实验环境主要由两个部分组成：QEMU用来模拟运行内核，以及一条编译工具链用于编译和测试内核。这里我使用的系统是64位的ArchLinux。

本部分可以参考MIT 6.828官网的Tools。

编译工具链

编译工具链包含了C编译器、汇编器、连接器，用于从源代码生成可执行二进制文件。本实验的目标代码是32位的Intel架构（x86），可执行文件格式为ELF。

在Arch Linux下，若是在安装时选择了base-devel包组，则gcc应该是系统自带的编译工具链。但是，该gcc默认不能编译生成32位的可执行文件。需要手动开启multilib并安装gcc-multilib以及相关的软件包。

GCC版本降级说明

在我和华田的Arch下，使用gcc 7.1.1-3之后的版本编译生成的JOS kernel均无法使用。在无法查明原因的情况下，推荐将gcc降级至7.1.1-3完成6.828的实验。

有关于Arch下软件包降级的教程请看这里。

在后续的实验中，为了使得编译JOS内核的工具链不和系统工具链冲突以及为了保证系统工具链的最新，尝试了手动编译32位的gcc 4.6.1作为JOS专用的交叉编译工具链，并使用modules来管理环境变量，具体可以参考这里。

Qemu模拟器

QEMU是一个现代并且快速的PC模拟器，但是为了与实验兼容，MIT推荐使用他们patched过的QEMU版本。需要按照Tools上的教程从源码编译并安装QEMU。

注意：提供的QEMU并不支持make uninstall，需要手动卸载QEMU。如果您对于手动编译并安装可能存在的后果抱有顾虑，推荐使用包管理软件安装QEMU，或是修改编译前缀，不要将编译好的qemu安装到/usr/local/下

问题

所需要的库名可以在arch官网上通过搜索软件包的方式找到；
configure的时候加上–disable-werror以保证不会因出现编译警告而终止编译；

出现如下错误：

Unescaped left brace in regex is illegal here in regex; marked by <-- HERE
in m/^\@strong{ <-- HERE (.*)}$/ at /home/guest/qemu/scripts/texi2pod.pl
line 320.

make: *** [Makefile:474：qemu.1] 错误 255。

该错误是由于perl版本更新后正则表达式语法的变动造成的，直接修改安装脚本的/home/chenzhihao/qemu/scripts/texi2pod.pl line 320，将{改成 \{即可；

configure时可能需要指定python版本为2以避免调用python3出现错误，参数为--python=/usr/bin/python2.7。

实验介绍

实验1总共分为3个部分：

第1部分主要关注x86汇编语言、QEMU x86模拟器以及PC的上电启动流程；
第2部分主要关注6.828内核的引导程序；
第3部分开始挖掘6.828内核的最初模板 - JOS。

实验使用Git进行版本管理，需要从MIT的Git克隆最开始的仓库，有关这一部分的具体说明请自行参考Lab1实验讲义。

有关于Git的教程推荐廖雪峰的官方博客或者是Pro Git 2。

实验过程

第一部分 PC Bootstrap - PC引导

x86汇编

练习1：
本实验需要熟悉x86汇编。

8086汇编已经在王爽的《汇编语言》以及学院的汇编语言课程中学习过，x86_64汇编也已经在《深入理解计算机系统》中有所涉猎。本实验中使用的是i386汇编。这里不再赘述。

模拟x86

在本实验中使用QEMU作为模拟器。尽管QEMU内置的监控只能提供少量的调试支持，但是QEMU却可以作为GNU-Debugging（GDB）的远程调试目标。

根据实验指导使用make编译生成内核并且用make qemu或者是make qemu-nox启动QEMU。可以看到，当前的内核仅支持两条命令help和kerninfo。

PC的物理地址空间

PC的物理地址空间有着如下的布局：

+------------------+  <- 0xFFFFFFFF (4GB)
|      32-bit      |
|  memory mapped   |
|     devices      |
|                  |
/\/\/\/\/\/\/\/\/\/\

/\/\/\/\/\/\/\/\/\/\
|                  |
|      Unused      |
|                  |
+------------------+  <- depends on amount of RAM
|                  |
|                  |
| Extended Memory  |
|                  |
|                  |
+------------------+  <- 0x00100000 (1MB)
|     BIOS ROM     |
+------------------+  <- 0x000F0000 (960KB)
|  16-bit devices, |
|  expansion ROMs  |
+------------------+  <- 0x000C0000 (768KB)
|   VGA Display    |
+------------------+  <- 0x000A0000 (640KB)
|                  |
|    Low Memory    |
|                  |
+------------------+  <- 0x00000000

最初的PC基于Intel的16位8088处理器，仅能够支持2^20B = 2^10KB = 1MB的寻址，早期的地址空间从0x00000开始到0xFFFFF结束。

0x00000到0xA0000（640KB）被称作低内存，是早期PC能用的唯一的RAM；
0xA0000到0xFFFFF（384KB）被硬件保留作特殊用途如视频缓冲区或是固件，该部分最重要的区域是从0xF0000到0xFFFFF（64KB）的基本输入输出系统（BIOS）。BIOS用作执行最基本的系统初始化如激活显卡、检查内存等。在初始化完成后，BIOS从软盘、硬盘、光驱或是网络中读取操作系统，并且将机器控制权转移给操作系统。

从Intel的80286到80386，处理器能够支持16MB和4GB的地址空间。但为了后向兼容性，硬件设计者保留了低1M内存的布局。
现代PC因此在0x000A0000到0x00100000的内存中有一个“洞”，这个洞将内存分为了低内存/保留内存（Low Memory）（低640KB）以及扩展内存（Extended Memory）（其他内存）。除此以外，32位PC的地址空间的最上方，常常被BIOS保留用作32位的PCI设备。

最新的x86处理器能够支持超过4GB的物理内存，因此内存可以超过0xFFFFFFFF。因此BIOS需要预留出第二个“洞”以保证那些32位的PCI设备的地址可以被正确的映射。

由于JOS只会使用256M内存，在此假设仅PC具有32位的地址空间。

ROM BIOS

根据实验指导，进行QEMU和GDB的联合调试。会发现从上电开始，IBM PC从0x000ffff0开始执行指令。该处位于为BIOS预留的64kb的空间的顶层。此时CS = 0xf000 IP = 0xfff0。且第1条指令是一个jmp指令，跳转至CS = 0xf000 IP = 0xe05b。

这些都是早期的8088处理器的设计者设计的。这样的设计保证了BIOS总能控制机器。因为在刚上电的时候，在内存中并不存在能够执行的代码。

此处需要理解8086的分段式寻址，即通过两个16位寄存器的值构造20位地址。实际地址为CS × 16 + IP = 0xf000 × 16 + 0xfff0 = 0xffff0。

练习2：
使用gdb的si（单步调试）命令进入ROM BIOS并追踪几条指令，并猜测这些指令的作用。不需要指出指令具体的细节，只要理解BIOS一开始运行的核心思想而已。

BIOS执行的前若干条指令和作用如下：

[f000:fff0]    0xffff0: ljmp   $0xf000,$0xe05b # 跳到一个较早的位置
[f000:e05b]    0xfe05b: cmpl   $0x0,%cs:0x6ac8
[f000:e062]    0xfe062: jne    0xfd2e1         # 测试cs段的0x6ac8字是否为0        
[f000:e066]    0xfe066: xor    %dx,%dx         # 测试为0
[f000:e068]    0xfe068: mov    %dx,%ss         
[f000:e06a]    0xfe06a: mov    $0x7000,%esp    # 设置栈段寄存器和栈指针寄存器
                                               # 栈的延伸方向和代码段延伸方向相反
[f000:e070]    0xfe070: mov    $0xf34c2,%edx   # 设置edx寄存器值
[f000:e076]    0xfe076: jmp    0xfd15c         # 跳转
[f000:d15c]    0xfd15c: mov    %eax,%ecx       
[f000:d15f]    0xfd15f: cli                    # 关闭硬件中断
[f000:d160]    0xfd160: cld                    # 设置串传送指令方向
[f000:d161]    0xfd161: mov    $0x8f,%eax      
[f000:d167]    0xfd167: out    %al,$0x70       # 关闭不可屏蔽中断
[f000:d169]    0xfd169: in     $0x71,%al       # 从CMOS读取选择的寄存器
[f000:d16b]    0xfd16b: in     $0x92,%al       # 读取系统控制端口A
[f000:d16d]    0xfd16d: or     $0x2,%al        
[f000:d16f]    0xfd16f: out    %al,$0x92       # 通过快速A20以启动A20
[f000:d171]    0xfd171: lidtw  %cs:0x6ab8      # 将cs:0x6ab8加载进入IDT表
[f000:d177]    0xfd177: lgdtw  %cs:0x6a74      # 将cs:0x6a74加载进入GDT表
[f000:d17d]    0xfd17d: mov    %cr0,%eax   
[f000:d180]    0xfd180: or     $0x1,%eax       
[f000:d184]    0xfd184: mov    %eax,%cr0       # 将cr0寄存器的保护模式位打开
[f000:d187]    0xfd187: ljmpl  $0x8,$0xfd18f   # 通过ljmp指令进入保护模式
=> 0xfd18f:     mov    $0x10,%eax              # 设置段寄存器
=> 0xfd194:     mov    %eax,%ds
=> 0xfd196:     mov    %eax,%es  
=> 0xfd198:     mov    %eax,%ss
=> 0xfd19a:     mov    %eax,%fs
=> 0xfd19c:     mov    %eax,%gs
=> 0xfd19e:     mov    %ecx,%eax  
=> 0xfd1a0:     jmp    *%edx                   # 跳转

第二部分引导

软盘和硬盘被分为了512Bytes的区域 - 扇区（Sector）。一个扇区是磁盘传输的最小粒度：每一个读操作和写操作必须是一个或是一个以上的扇区，并且必须要对齐到扇区。

如果一个磁盘是可引导的，那么它的第一个扇区就被称作引导扇区，引导代码就存储在引导扇区中。如果BIOS发现了一个可引导的硬件，那么它就将这个扇区从磁盘读取至内存的0x7c00到0x7dff处，并且使用一个jmp指令设置CS：IP = 0000:7C00，将控制传递给引导。和BIOS读取地址一样，这个地址对于PC来说是固定和标准化的。

从光盘引导的情形更加复杂，因为光盘的一个扇区为2048Byte，BIOS可以从硬盘读取一个更大的引导镜像到内存中。

在6.828中，使用硬盘的传统引导机制。这意味这引导必须满足512个Bytes的限制。引导由一个汇编文件boot/boot.S，以及一个C语言文件boot/main.c组成。

练习3：追踪boot.S和main.C，分析每一个部分的作用。

为了理解boot.S，需要以下的知识储备。

实模式和保护模式

实模式是为了与8086兼容而设置的。在实模式下，处理器相当于一个快速的8086处理器。当处理器被加电或者复位时以实模式启动。

实模式下各寄存器以实模式的初始化值工作；
实模式的地址空间总共为20位（1MB）；
实模式下不支持内存分页机制；
实模式下各内存段均是可读、可写、可执行的，不支持指令优先级，所有的指令均运行在特权级；
实模式不支持多任务切换；
实模式的中断处理也和8086相同，使用中断向量表来定位中断服务程序。

在保护模式下，处理器的所有功能都是可用的。具体来说：

保护模式提供了完全的32位地址空间，寻址空间为4GB；
保护模式支持内存分页机制，提供了对虚拟内存的硬件支持；
保护模式的处理器支持多任务（上下文切换）；
保护模式的处理器支持指令和数据的特权级，配合边界检查等机制，既可以共享数据也可以隔离各个任务。

为了保证后向兼容性，x86的处理器启动时默认是实模式，需要手动从实模式切换至保护模式。但是切换至保护模式之前需要做一些必要的准备工作，如打开A20和建立全局描述符表等。

A20地址线

在早期的PC上处理器仅支持20位的地址空间，任何超过20位的地址都会被卷回。
例如：0xFFFF+0xFFFF = 0x1FFFE -> 0xFFFE

然而，从80286开始，Intel支持了24位的地址空间，上例的地址相加将不会发生卷回。
为了保证与早期PC的完全兼容，Intel采用了“黑魔法” - 将A20（第21根）地址线与键盘控制器的一个输出进行了与运算。进而控制A20地址线的值。

默认情况下，A20是置0的，PC将只能访问1M、3M、5M…这样的奇数段。进入保护模式前需要先打开A20以获得完全的寻址能力。

JOS内核通过端口的方式与键盘控制器进行通信并打开A20。可以参考Reference中的PS/2 Keyboard Interface。

8042有一个1 Byte的输入缓冲区，一个1 Byte的输出缓冲区、一个1 Byte的状态寄存器、以及一个1 Byte的控制寄存器。前三个寄存器可以直接从0x60和0x64端口进行访问。最后一个寄存器通过“Read Command Byte”命令进行读，通过“Write Command Byte”命令进行写。
对0x60端口读会读输入缓冲区；对0x60端口写会写输出缓冲区；对0x64端口读会读状态寄存器；对0x64端口写会发送命令。
状态寄存器的Bit1为IBF - Input Buffer Full，当该Bit为1时，输入缓冲区满，不能对0x60端口或0x64端口写。
对0x64端口写0xd1发送的命令是“Write Output Port”写输出端口，表明将参数写入输出端口（0x60端口写）。
A20使用的是键盘控制器输出的Bit 1，向输出端口写入0xdf可以打开A20；向输出端口写入0xdd则会关闭A20。

分段机制与全局描述符表

x86处理器提供了分段机制和分页机制两种内存管理模式。如果要进入保护模式，就必须要先启动分段机制。（分页机制不是必须的）

分段机制将内存划分为若干个段，每个段都由段基址、段界限和段属性组成。由一个段描述符表（可以理解为一个数组）描述所有段的信息。段描述符表可以是全局的也可以是局部的。

简化的说，程序首先将对应的段选择子（可以理解为数组的索引）加载进入段寄存器中。然后在执行程序时，根据指令的内容确定应该使用的段寄存器，根据段寄存器中的段选择子确定应该使用的段描述符。再结合段描述符中包含的信息加上指令自身的地址构造出实际的物理地址。最终将该地址发送到地址总线上，到物理内存中寻址，并取回相应的数据。这之中简化了有关特权级、边界检查的相关内容，但足以描述分段机制的基本原理。

分段机制将虚拟地址转换成了线性地址。

全局描述符表寄存器

x86处理器提供了专门的全局描述符表寄存器（Global Descriptor Table Register）用于保存全局描述符表的表基址和表限长。GDTR由2个字节的表限长（limit）和4个字节的表基址（base）组成。其中表基址指定了全局描述符表的起始地址，表限长指定了全局描述符表的大小。其C结构体描述如下：

struct gdtr {
	u16 limite;
	u32 base;
} __attribute__ ((packed));

在机器刚加电或者是处理器复位后，表基址默认被置为0，表限长则默认被置为0xFFFF。在保护模式初始化的过程中，必须给GDTR加载新的值。可以使用lgdt指令为GDTR加载新值。

段选择子

段选择子（2个字节）用于选择特定的描述符表以及表中的特定描述符。段选择子一般被放置于段寄存器中，段选择子由13位的索引、1位的表指示位和2位的请求特权级三部分组成。其中索引指定了描述符，表指示位选择应该访问的描述符表 - 0代表全局描述符表，1代表局部描述符表，请求特权级用于段级的保护机制，自0到4分别代表ring 0到ring 3。其C结构体描述如下：

struct selector {
    u16 index:13;
    u16 ti:1;
    u16 rpl:2;
}

段描述符

段描述符（8个字节）是段描述符表这个“数组”的“元素”。用C结构体描述如下：

struct gdtdesc {
	u16 lim0_15;
	u16 base0_15;
	u8 base16_23;
	u8 acces;
	u8 lim16_19:4;
	u8 other:4;
	u8 base24_31;
} __attribute__ ((packed));

其中总共包含了32位的段基址、20位的段界限、以及12位的类型。
段基址规定了段的起始地址。段界限规定了段的大小。而类型用于区别不同类型的描述符。包括描述符特权级、段存在位、已访问位等等。

boot.S代码详解

#include <inc/mmu.h>

# Start the CPU: switch to 32-bit protected mode, jump into C.
# The BIOS loads this code from the first sector of the hard disk into
# memory at physical address 0x7c00 and starts executing in real mode
# with %cs=0 %ip=7c00.
# boot.S 主要将CPU切换至32位保护模式，并且跳转进入C代码

.set PROT_MODE_CSEG, 0x8         # kernel code segment selector
.set PROT_MODE_DSEG, 0x10        # kernel data segment selector
.set CR0_PE_ON,      0x1         # protected mode enable flag

.globl start
start:                        # 程序入口
  .code16                     # Assemble for 16-bit mode 指导生成16位汇编代码
  cli                         # Disable interrupts 关中断
  cld                         # String operations increment 设置串传递顺序递增

  # Set up the important data segment registers (DS, ES, SS). 设置重要的段寄存器为0
  xorw    %ax,%ax             # Segment number zero
  movw    %ax,%ds             # -> Data Segment
  movw    %ax,%es             # -> Extra Segment
  movw    %ax,%ss             # -> Stack Segment

  # Enable A20:
  #   For backwards compatibility with the earliest PCs, physical
  #   address line 20 is tied low, so that addresses higher than
  #   1MB wrap around to zero by default.  This code undoes this.
  # 开启A20：
  #   A20的介绍已经给出，不再赘述。
seta20.1:
  inb     $0x64,%al               # Wait for not busy 等待缓冲区可用
  testb   $0x2,%al                # Test for bit1
                                  # if bit1 = 1 then buffer is full
  jnz     seta20.1

  movb    $0xd1,%al               # 0xd1 -> port 0x64
  outb    %al,$0x64               # Prepare to write output port 准备写入输出端口

seta20.2:
  inb     $0x64,%al               # Wait for not busy 等待缓冲区可用
  testb   $0x2,%al
  jnz     seta20.2                # The same as above 同上

  movb    $0xdf,%al               # 0xdf -> port 0x60
  outb    %al,$0x60               # 0xdf -> A20 gate enable command 打开A20

  # Switch from real to protected mode, using a bootstrap GDT
  # and segment translation that makes virtual addresses
  # identical to their physical addresses, so that the
  # effective memory map does not change during the switch.
  lgdt    gdtdesc                # Load gdt size/base to gdtr 设置全局描述符表
  movl    %cr0, %eax             # Control register 0
                                 # bit0 is protected enable bit
                                 # 读取控制寄存器0的值，其Bit0为允许保护模式位
  orl     $CR0_PE_ON, %eax       # Set PE 将允许保护模式位置1
  movl    %eax, %cr0             # Update Control register 0 设置控制寄存器0

  # Jump to next instruction, but in 32-bit code segment.
  # Switches processor into 32-bit mode.
  ljmp    $PROT_MODE_CSEG, $protcseg # 通过ljmp指令（跳转至下一条指令）进入保护模式

  .code32                     # Assemble for 32-bit mode 指导生成32位汇编代码
protcseg:
  # Set up the protected-mode data segment registers 设置保护模式的数据段寄存器
  movw    $PROT_MODE_DSEG, %ax    # Our data segment selector
  movw    %ax, %ds                # -> DS: Data Segment
  movw    %ax, %es                # -> ES: Extra Segment
  movw    %ax, %fs                # -> FS
  movw    %ax, %gs                # -> GS
  movw    %ax, %ss                # -> SS: Stack Segment

  # Set up the stack pointer and call into C. 设置栈指针并且调用C
  movl    $start, %esp  # Stack has the opposite extension direction than Code
                        # 注意栈的延伸方向和代码段相反
  call bootmain #调用main.c中的bootmain函数

  # If bootmain returns (it shouldn't), loop.
spin:
  jmp spin

# Bootstrap GDT 引导GDT
.p2align 2                                # force 4 byte alignment
gdt:
  SEG_NULL				# null seg 默认第一个段描述符为空
  SEG(STA_X|STA_R, 0x0, 0xffffffff)	# code seg 设置代码段描述符
  SEG(STA_W, 0x0, 0xffffffff)	        # data seg 设置数据段描述符
  # 关于SEG宏可以参考mmu.h

gdtdesc:                                  # 用于设置全局段描述符寄存器
  .word   0x17                            # sizeof(gdt) - 1 # Size of gdt
  .long   gdt                             # address gdt # Base address of gdt

为了理解main.c，需要如下的知识储备。

ELF文件格式

可执行和可链接格式（Executable and Linkable Format）是一种用于二进制文件、可执行文件、目标代码、共享库和核心转储格式文件。

ELF文件可以分为两种组成 - 链接视图（Linking View）和执行视图（Execution View）。这里只讨论执行视图。

执行视图的结构如下：

+--------------------+
|     ELF Header     |
+--------------------+
|Program Header Table|
+--------------------+
|      Segment 1     |
+--------------------+
|      Segment 2     |
+--------------------+
|         ...        |
+--------------------+
|Section Header Table|
|       optinal      |
+--------------------+

ELF文件格式主要由ELF头（ELF Header）、程序头部表（Program Header Table）和节头部表（Section Header Table）组成。在执行视图中，节头部表是可选的。

有关于这些数据结构的C语言定义可以参考头文件<inc/elf.h>。

ELF头主要包含了ELF魔数、文件类型、程序头部表偏移和大小、程序入口等信息；
程序头部表可以看做一个数据结构的数组，每一个元素都描述了一个段。主要包含了段的偏移、段的虚拟地址、段的物理地址、段的大小等信息。

磁盘控制器

磁盘是电脑主要的存储媒介。磁盘是由盘片构成的。每个盘片有两面或者称为表面，表面覆盖着磁性记录材料。盘片中央有一个可以旋转的主轴，它使得盘片以固定的旋转速率旋转，通常是5400-15000转每分钟（Revolution Per Minute）。磁盘通常包含一个或多个这样的盘片，并封装在一个密封的容器内。

每一个表面是由一组称为磁道的同心圆组成。每个磁道被划分为一组扇区。每个扇区包含相等数量的数据位（通常是512字节），这些数据编码在扇区上的磁性材料中。扇区之间由一些间隙分隔开，这些间隙中不存储数据位。间隙用来标识扇区的格式化位。

磁盘的柱面是所有盘片表面上到主轴中心距离相等的磁道的集合。

对于磁盘的寻址通常分为CHS和LBA两种。

CHS即柱面（cylinder）-磁头（head）-扇区（sector）寻址。每个盘片都对应着一个磁头，每一个盘片都被划分成柱面，每一个柱面都被划分成多个段。磁盘的最小存储单元是段。早期的IBM PC架构上采用CHS进行磁盘寻址。CHS是一个三元组，包括10bit的柱面号，8bit的磁头号以及6bit的扇区号。这样CHS的最大寻址范围为2^10 × 2^8 × 2^6 × 512 = 8GB。
随着磁盘容量的不断扩大，CHS的8GB寻址范围已经不能满足需要，现在的磁盘普遍采用逻辑区块地址（Logical Block Adress）的方式进行寻址来进行抽象。LBA是一个整数，代表磁盘上的一个逻辑区块编号，通过将这个整数转换成CHS格式来完成磁盘的具体寻址。LBA为48个bit，最大寻址范围为128PB。在本实验中，LBA按照旧的规范采用28个bit。

IDE硬盘控制器（IDE Hard Drive Controller）的0x1F7端口读为磁盘0状态寄存器。
其Bit6为RDY Bit，当其置1表明磁盘上电完成。在对于磁盘做任何操作（除了复位）之前务必要保证该Bit为1。
其Bit7为BSY Bit，当其置1表明磁盘忙。在你向磁盘发送任何指令前务必保证该Bit为0。

通过IDE硬盘控制器读取扇区需要如下的步骤：

向0x1F2端口写入待操作的扇区数目；
向0x1F3-0x1F5端口依次写入LBA的低24位；
向0x1F6端口的低4位写入LBA的高4位，向0x1F6端口的高4位写入驱动器地址；
向0x1F7端口写入读命令0x20。

0x1F6寄存器又称Drive/Head寄存器。其低4位是LBA的高4位。其Bit5和Bit7一般是1。其Bit6为LBA位，当置1时表示启用LBA寻址。其Bit4为DRV位。用来选择驱动器，Master驱动器为0，Slave驱动器为1。这里将高4位置为0x1110

在使用读命令0x20之前需要完整的设置柱面/磁头/扇区。当这个命令完成，你可以从磁盘的数据寄存器（0x1F0端口）读取256个字（16Bits）。

main.c代码详解

#include <inc/elf.h>
#include <inc/x86.h>

/**********************************************************************
 * This a dirt simple boot loader, whose sole job is to boot
 * an ELF kernel image from the first IDE hard disk.
 *
 * DISK LAYOUT
 *  * This program(boot.S and main.c) is the bootloader.  It should
 *    be stored in the first sector of the disk.
 *
 *  * The 2nd sector onward holds the kernel image.
 *
 *  * The kernel image must be in ELF format.
 *
 * BOOT UP STEPS
 *  * when the CPU boots it loads the BIOS into memory and executes it
 *
 *  * the BIOS intializes devices, sets of the interrupt routines, and
 *    reads the first sector of the boot device(e.g., hard-drive)
 *    into memory and jumps to it.
 *
 *  * Assuming this boot loader is stored in the first sector of the
 *    hard-drive, this code takes over...
 *
 *  * control starts in boot.S -- which sets up protected mode,
 *    and a stack so C code then run, then calls bootmain()
 *
 *  * bootmain() in this file takes over, reads in the kernel and jumps to it.
 **********************************************************************/

#define SECTSIZE 512
#define ELFHDR ((struct Elf *)0x10000)    // scratch space

void readsect(void *, uint32_t);
void readseg(uint32_t, uint32_t, uint32_t);

void bootmain(void) {
    struct Proghdr *ph, *eph;

    // read 1st page off disk 从磁盘上读取第一页
    readseg((uint32_t)ELFHDR, SECTSIZE * 8, 0);

    // is this a valid ELF? 通过ELF魔数确认ELF有效
    if (ELFHDR->e_magic != ELF_MAGIC) goto bad;

    // load each program segment (ignores ph flags) 读取各个段
    ph = (struct Proghdr *)((uint8_t *)ELFHDR + ELFHDR->e_phoff);
    // 程序头部表的起始地址
    eph = ph + ELFHDR->e_phnum;    // 程序头部表的结束地址
    for (; ph < eph; ph++)
        // p_pa is the load address of this segment (as well
        // as the physical address)
        // p_pa是加载地址也是物理地址
        readseg(ph->p_pa, ph->p_memsz, ph->p_offset);

    // call the entry point from the ELF header 从ELF头调用程序入口
    // note: does not return!
    ((void (*)(void))(ELFHDR->e_entry))();

bad:
    // stops simulation and breaks into the debug console
    outw(0x8A00, 0x8A00);
    outw(0x8A00, 0x8E00);
    while (1) /* do nothing */;
}

// Read 'count' bytes at 'offset' from kernel into physical address 'pa'.
// 从内核的offset处读取count个字节到物理地址pa处
// Might copy more than asked 可能会读取超过count个（扇区对齐）
void readseg(uint32_t pa, uint32_t count, uint32_t offset) {
    uint32_t end_pa;

    end_pa = pa + count;    // 结束物理地址

    // round down to sector boundary 对齐到扇区
    pa &= ~(SECTSIZE - 1);

    // translate from bytes to sectors, and kernel starts at sector 1
    offset =
        (offset / SECTSIZE) + 1;    // 算出扇区数 注意扇区从1开始（0为引导扇区）

    // If this is too slow, we could read lots of sectors at a time.
    // We'd write more to memory than asked, but it doesn't matter --
    // we load in increasing order.
    // 在实际中往往将多个扇区一起读出以提高效率。
    while (pa < end_pa) {
        // Since we haven't enabled paging yet and we're using
        // an identity segment mapping (see boot.S), we can
        // use physical addresses directly.  This won't be the
        // case once JOS enables the MMU.
        // 考虑到没有开启分页以及boot.S中使用了一一对应的映射规则，
        // 加载地址和物理地址是一致的。
        readsect((uint8_t *)pa, offset);
        pa += SECTSIZE;
        offset++;
    }
}

void waitdisk(void) {
    // wait for disk reaady 等待磁盘准备完毕。
    while ((inb(0x1F7) & 0xC0) != 0x40) /* do nothing */;
}

void readsect(void *dst, uint32_t offset) {
    // wait for disk to be ready
    waitdisk();

    outb(0x1F2, 1);    // count = 1 0x1F2 Disk 0 sector count
    // Read one sector each time
    outb(0x1F3, offset);    // Disk 0 sector number (CHS Mode)
    // First sector's number
    outb(0x1F4, offset >> 8);     // Cylinder low (CHS Mode)
    outb(0x1F5, offset >> 16);    // Cylinder high (CHS Mode)
    // Cylinder number
    outb(0x1F6, (offset >> 24) | 0xE0);    // Disk 0 drive/head
    // MASK 11100000
    // Drive/Head Register: bit 7 and bit 5 should be set to 1
    // Bit6: 1 LBA mode, 0 CHS mode
    outb(0x1F7, 0x20);    // cmd 0x20 - read sectors
    /*20H       Read sector with retry. NB: 21H = read sector
                without retry. For this command you have to load
                the complete circus of cylinder/head/sector
                first. When the command completes (DRQ goes
                active) you can read 256 words (16-bits) from the
                disk's data register. */

    // wait for disk to be ready
    waitdisk();

    // read a sector
    insl(0x1F0, dst, SECTSIZE / 4);
    // Data register: data exchange with 8/16 bits
    // insl port addr cnt: read cnt dwords from the input port
    // specified by port into the supplied output array addr.
    // dword: 4 bytes = 16 bits
}

练习3：

0x7c2d: ljmp $0x8, $0x7c32 从这句汇编指令之后处理器开始执行32位指令。ljmp指令导致了16位指令到32位指令的转变。
引导最后执行的指令是call *0x10018，内核的第一条指令是movw $0x1234,0x472。
内核的第一条指令位于0x10000c。
引导从程序头部表中得到段的数目以及每个段的大小，以此决定要从磁盘上读出多少个扇区。

加载内核

本部分主要需要了解.text段.rodata段和.data段，并且使用objdump读取ELF格式的信息。

boot/Makefrag文件中指定了引导的text段的位置为0x7c00。

练习4：
阅读并学习关于C语言指针的知识。下载pointer.c，编译运行并确保理解它。

pointer.c的代码和解释如下：

#include <stdio.h>
#include <stdlib.h>

void f(void) {
    int  a[4];    // 含有4个元素的整形数组
    int *b =
        malloc(16);    // 分配16个字节的内存，并且用一个整形指针指向内存首地址
    int *c;    // 一个悬挂的整形指针
    int  i;    // 一个整形数

    printf("1: a = %p, b = %p, c = %p\n", a, b, c);
    // 打印a和b和c的地址，分别为0xff9bebcc, 0x566fc160和0xf7ede1e8

    c = a;
    // 令c指向数组a的首地址
    for (i = 0; i < 4; i++) a[i] = 100 + i;    // 为a[0]到a[3]分配100-103
    c[0] = 200;                                // 将c[0]也就是a[0]改为200
    printf("2: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n", a[0], a[1], a[2],
           a[3]);
    // 输出200 101 102 103

    c[1]     = 300;    // 将c[1]也就是a[1]改为300
    *(c + 2) = 301;    //将*(c + 2)也就是a[2]改为301
    3 [c]    = 302;    // 将3[c]也就是c[3]改为302
    printf("3: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n", a[0], a[1], a[2],
           a[3]);
    // 输出200 300 301 302

    c  = c + 1;    // 令c指向a[1]
    *c = 400;      // 将a[1]改为400
    printf("4: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n", a[0], a[1], a[2],
           a[3]);
    // 输出200 400 301 302

    c = (int *)((char *)c + 1);
    // 将c先转换为char指针指向下一个字节后再转回int指针
    // 现在a数组的字节分布为（小端）C8000000 90010000 2D010000 2E010000
    | (c的指针)*c = 500;
    // 执行后的a数组字节分布（小端）C8000000 90F40100 00010000 2E010000
    printf("5: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n", a[0], a[1], a[2],
           a[3]);
    // 输出200 128144 256 302

    b = (int *)a + 1;
    // 将b指向a[1]
    c = (int *)((char *)a + 1);
    // 将a先转换为char指针指向下一个字节后再转回int指针
    printf("6: a = %p, b = %p, c = %p\n", a, b, c);
    // 输出0xff9bebcc, 0xff9bebd0和0xff9bebcd
}

int main(int ac, char **av) {
    // 函数入口
    f();
    return 0;
}

练习5：
修改了text段的加载地址使得汇编代码中的跳转地址出现错误，进而导致整个引导因为错误提前终止。

练习6：
结果是非常显然的，因为引导的作用就是将内核从磁盘加载进入内存中。使用objdump -h obj/kern/kernel可以看到如下的信息：
0 .text 00001809 f0100000 00100000 00001000 2**4
CONTENTS, ALLOC, LOAD, READONLY, CODE
可以直到内核的text段会被加载至内存中0x100000（物理地址）处。

第三部分内核

使用虚拟内存去解决位置依赖

可以发现内核将自己链接至了非常高的虚拟地址，比如0xf0100000，为了将处理器虚拟地址的较低部分给用户程序去使用。将在下一个实验介绍这一现象。

实际上，许多的机器在物理内存中并没有0xf0100000这样的高地址。实际上由处理器的内存管理硬件将虚拟地址0xf0100000映射到了实际内存中的物理地址0x100000。

这涉及了分页机制以及页表。
在kern/entry.S设置CR0_PG标记之前，内存引用被当做线性地址。实际上，由于在boot/boot.S设置了线性地址到物理地址的一致映射，所以线性地址在这里可以等同于物理地址。
当CR0_PG标记被设置了之后，所有的内存引用都被当作虚拟地址。虚拟地址通过虚拟内存硬件被翻译成物理地址。
kern/entrypgdir.c将0xf0000000到0xf0400000的虚拟地址翻译为物理地址的0x000000到0x400000，也将0x00000000到0x00400000的虚拟地址翻译为物理地址的0x00000000到0x00400000。
引用这些地址范围以外的虚拟地址将会抛出缺页的异常。
但是还没有为该异常设置中断处理程序。这会导致QEMU导出机器状态并退出。

练习7：
在movl %eax, %cr0指令（启动页表）之前，0x00100000出的内存不为空，0xf0100000出的内存全为0。
当stepi之后，0xf0100000处的内存和0x00100000处的内存完全一样。这表明已经成功启用了页表，并且完成了地址的映射。

控制台的格式化字符串

练习8：
缺失的代码为：

case 'o':
	num = getuint(&ap, lflag);
base = 8
goto number;

console.c提供了基本的I/O操作，同时封装了cputchar、getchar等函数供printf.c中的printf使用。printf使用了vprintfmt去解析格式化字符串并提供可变参数的特性。
这段代码主要实现了换行。其首先检查了当前的光标是否超过了最大值，如果是，则证明需要进行换行。其将第1行到第MAX-1行的内容复制到第0行到第MAX-2行所在的内存中，然后将第MAX-1行置空。最后将光标设置到新一行的开始。

fmt指向了格式化字符串”x %d, y %x, z %d\n”
ap指向了局部变量并且初始值为1

vcprintf(0xf0102449, 0xf0110e14);
0xf0102449 -> "x %d, y %x, z %d\n" 0xf0110e14 -> 1
cons_putc(120);
cons_putc(32);
va_arg(0xf0110dbc, int);
Before: 0xf0110dbc -> 0xf0110e14 -> 1
After: 0xf0110dbc -> 0xf0110e18 -> 3
cons_putc(49);
cons_putc(44);
cons_putc(32);
cons_putc(121);
cons_putc(32);
va_arg(0xf0110dbc, int);
Before: 0xf0110dbc -> 0xf0110e18 -> 3
After: 0xf0110dbc -> 0xf0110e1c -> 4
cons_putc(51);
cons_putc(44);
cons_putc(32);
cons_putc(122);
cons_put(32);
va_arg(0xf0110dbc, int);
Before: 0xf0110dbc -> 0xf0110e1c -> 4
After: 0xf0110dbc -> 0xf0110e20 -> 536870922
cons_put(52);
cons_put(10);

注意这里va_arg是宏而不是函数，不能通过加断点的方式跟踪。我采用的方法是在调用va_arg的地方添加断点并跟踪。
在GNUmakefile中的C_FLAGS -O1会重排C代码，导致了追踪va_arg变得困难。所以，仅在此处将-O1变成-O0，尽管这会导致在backtrace时kernel panic。

57616 = 0xe110。此外，根据x86的小端序，&i指向了byte序列0x72、0x6c、0x64、0x00。这等同于字符串”rld”。所以，最终的输出为”He110 World”。
需要将i改为0x726c6400。不需要修改57616。
这是由于程序从格式化字符串中推断出了应当有3个参数，所以程序会从cprintf的栈中多读取一个参数。但实际上只有2个参数。所以最后一个参数是未指定的。
vcprintf(…, const char * fmt)。

栈

练习9：
f0100034: bc 00 00 11 f0 mov $0xf0110000,%esp
这一条指令初始化了引导栈，它位于0xf0110000处。内核仅通过设置esp寄存器的值为栈预留空间。栈指针指向高地址，并且栈自高地址向低地址延伸。

练习10：
本题考察了x86架构下的栈帧与函数调用。
函数调用时先将返回地址压栈，然后跳转至目标函数的起始地址；在目标函数内先将ebp寄存器的值（栈底）压栈保存，然后再将栈顶指针设置为新的栈底；
在函数中调用函数需要使用栈来传递参数，即将函数的参数以此压入栈中；
test_backtrace函数的汇编中使用了ebx寄存器，该寄存器为被调用者保存的寄存器，在使用的时候也要先压栈保存，再函数返回时恢复；
函数返回的时候通过先操作esp释放栈资源，然后恢复相应的被调用者保存的寄存器的值，最后调用汇编指令leave、ret返回；
leave指令先将esp的值置为ebp，然后再从栈中取出被保存的ebp的旧值；ret从栈中取出返回地址并跳转。

练习10-12：
mon_backtrace的实现如下：

int mon_backtrace(int argc, char **argv, struct Trapframe *tf) {
    uint32_t            ebp, eip, args[5];
    struct Eipdebuginfo info;
    cprintf("Stack backtrace:\n");
    for (ebp = read_ebp(); ebp != 0; ebp = *((uint32_t *)ebp)) {
        eip = *((uint32_t *)ebp + 1);
        debuginfo_eip(eip, &info);
        args[0] = *((uintptr_t *)ebp + 2);
        args[1] = *((uintptr_t *)ebp + 3);
        args[2] = *((uintptr_t *)ebp + 4);
        args[3] = *((uintptr_t *)ebp + 5);
        args[4] = *((uintptr_t *)ebp + 6);
        cprintf("  ebp %08x  eip %08x  args %08x %08x %08x %08x %08x\n", ebp,
                eip, args[0], args[1], args[2], args[3], args[4]);
        cprintf("      %s:%d: %.*s+%d\n", info.eip_file, info.eip_line,
                info.eip_fn_namelen, info.eip_fn_name, eip - info.eip_fn_addr);
    }
    return 0;
}

查阅STABS文档可以知道表示行号的成员是n_desc，所以debuginfo_eip的缺失的代码如下：

stab_binsearch(stabs, &lline, &rline, N_SLINE, addr);
if (lline <= rline) {
    info->eip_line = stabs[lline].n_desc;
} else {
    return -1;
}

修改后的commands结构体如下：

static struct Command commands[] = {
   { "help", "Display this list of commands", mon_help },
   { "kerninfo", "Display information about the kernel", mon_kerninfo },
   { "backtrace", "Display information about the stack frames", mon_backtrace },
};

提高 - 允许控制台输出不同颜色的文本

要求能增强控制台的功能使得控制台可以输出不同颜色的字体。这里使用了传统的实现，解析嵌入在文本字符串中的ANSI转义序列来实现题目的要求。

在王爽的《汇编语言》中，已经接触过了字符的“属性字节”，一个字符的自低到高的第2个字节可以作为属性字节，用来指示字符的属性如闪烁、高亮、前景色、背景色等。
有关于ANSI转义序列的相关知识可以参考这里。

出于简化考虑，只部分实现ANSI转义序列中的ESC[Ps;...;Psm。

实现的思路是实现<kern/printf.c>中的punch函数的替代版本attribute_punch，来实现对于ANSI转义序列的解析，并且相应地设置字符的属性字节。

解析所需要的状态机具有三个状态：A_NORM代表正常的输出字符的状态、A_TRANS代表接收到[ESC]开始，从正常状态到解析转义序列的过渡状态、A_ESCAPE代表解析转义序列的状态。它们之间的状态转换图如图所示：

value用来存储每一个解析到的值，temp代表了解析过程中临时的属性字节，attribute代表了当前打印字符时附加的属性字节。

具体的实现代码在<kern/printf.c>中：

// state for ANSI escape sequence interpretation
enum { A_NORM = 0, A_TRANS, A_ESCAPE };

// colormap - number (x - 30/40)[0, 7] -> attribute byte
static uint16_t colormap[8] = {
    0x0000, 0x4400, 0x2200, 0x6600, 0x1100, 0x5500, 0x3300, 0x7700,
};

static void attribute_punch(int ch, int *cnt) {
    static int value     = 0;         // value
    static int state     = A_NORM;    // current state
    static int temp      = 0x0000,
               attribute = 0x0000;    // temp attribute, current attribute

    switch (state) {    // state machine
        case A_NORM:
            if (ch == 0x1B) {       // [ESC]
                state = A_TRANS;    // transfer from A_NORM to A_TRANS
            } else {
                cputchar((attribute & 0xFF00) |
                         ch);    // put character with attribute
                *cnt++;
            }
            break;
        case A_TRANS:
            if (ch == '[') {         // [
                state = A_ESCAPE;    // transfer from A_TRANS to A_ESCAPE
            } else {
                state = A_NORM;    // transfer from A_TRANS to A_NORM
            }
            break;
        case A_ESCAPE:
            if (ch >= '0' && ch <= '9') {    // digit - update value
                value = value * 10 + ch - '0';
            } else if (ch == ';' ||
                       ch == 'm') {    // ; or m set temp and clear value
                if (value == 0) {
                    temp = colormap[0];
                } else if (value == 5) {
                    temp |= 0x8000;
                } else if (value >= 30 && value <= 38) {
                    temp |= colormap[value - 30] &
                            0x0700;    // look up in color map
                } else if (value >= 40 && value <= 48) {
                    temp |=
                        colormap[value - 40] & 0x7000;    // avoid complex cases
                }
                value = 0;
                if (ch == 'm') {    // m needed extra work - update attribute
                    attribute = temp;
                    temp      = 0x0000;
                    state     = A_NORM;    // transfer from A_ESCAPE to A_NORM
                }
            } else {               // non_digit nor m
                state = A_NORM;    // transfer from A_ESCAPE to A_NORM
            }
            break;
    }
}

int vcprintf(const char *fmt, va_list ap) {
    int cnt = 0;

    // vprintfmt((void*)putch, &cnt, fmt, ap);
    // use attribute_punch rather than punch
    vprintfmt((void *)attribute_punch, &cnt, fmt, ap);
    return cnt;
}

最后在monitor.c中添加相关cprintf代码，并重新编译测试。最终如图所示：

有关于实验指导中提到的打开vga硬件的graphics mode使得控制台绘制文本到图形帧缓冲区的实现，由于时间和难度原因，这里暂时跳过。

实验小结

最终执行make grade，评分脚本的输出如下：

running JOS: (1.2s)
  printf: OK
  backtrace count: OK
  backtrace arguments: OK
  backtrace symbols: OK
  backtrace lines: OK
Score: 50/50

至此，实验一结束。

第一个实验总体来说更偏重于概念的理解、工具的使用而不是实际的代码。

尽管如此，大量的概念也浪费了我很多时间去理解。MIT的6.828同清华的ucore操作系统实验相比提供了相当多的reference（ucore的阅读材料几乎都是现成的），这也对文档阅读和信息检索能力有了更高的要求。