Lab1 Booting a PC

lab1 主要是介绍一个PC启动时如何办到的,分为了三个部分:熟悉 x86 汇编语言、熟悉 QEMU x86 模拟器、熟悉 PC 加电启动过程,然后主要的代码在 kernel 文件夹下边儿。

​ 实验链接:https://pdos.csail.mit.edu/6.828/2018/labs/lab1/

实验文件安装

​ 实验环境:Ubuntu 20.04 LTS WSL

​ 环境配置:

1
sudo apt install gcc g++ build-essential gdb gcc-multilib qemu qemu-system

​ 环境检测,查看是否安装成功:

1
2
objdump -i
gcc -m32 -print-libgcc-file-name

​ 下载 git 仓库,并尝试安装:

1
2
3
4
mkdir 6.828
cd 6.828
git clone https://pdos.csail.mit.edu/6.828/2018/jos.git lab
cd lab

​ 基本的一些操作命令:

1
2
3
make
make qemu
make grade

Part 1:PC Bootstrap

​ 这个部分主要是学习 X86 汇编语言,并且学习如何通过 QEMU 和 QEMU/GDB 进行 debug。

x86 assembly

Exercise 1

​ 要求:熟悉 X86 汇编,并且了解 C 语言内联汇编的方式,这个之前做汇编学习过,也在 CSAPP 中学习过,可以直接过了就。

Simulating the x86

​ 实验通过 QEMU 模拟 X86 的环境,并进行相关的系统模拟启动执行,下边儿进行具体的步骤操作:

1
2
3
4
cd lab
make
make qemu
make qemu-nox

make 的时候,进行编译生成 ELF 的 image 镜像,并且将它保存到了 obj/kern/kernel.img 这个地方,镜像里边儿保存了两个部分:obj/boot/boot和obj/kernel

make

make qemu 或者 make qemu-nox 的时候从磁盘上启动该镜像,并且进入一个 Shell 的小界面如下图,该 shell 提供了两条命令:help、kerninfo

make qemu

退出 qemu 的话,只需要 ctrl+a x 按顺序按下去。然后,如果是在没有桌面环境的情况下,可以考虑使用 make qemu-nox 的命令行,这样就可以直接在 shell 上显示。

make qemu-nox

物理内存地址

​ 这个部分进行了JOS物理内存地址的学习,当执行 kerninfo 的时候显示了部分信息,这个部分的信息是 JOS 内核的一些基本内存信息:

kernifo

​ 可以看到这个部分的物理内存地址的分布情况,intel 处理器在研发过程中,从最早的 16 位到后来的 32 位、64 位,CPU 的寻址能力在提升,其物理地址空间也在变化,但总体而言 80386 的内存地址如下:

PC's physical address layout

​ 也就是说,在 PC 启动的时候 CPU 运行在实模式,只能进行 1M 的访存,然后进入保护模式过后才拥有 4G 的内存访问能力,Intel 进行了访问的拓展,所以内存地址如上图呈现。

​ 其中,上述内存布局我觉得应该掌握一些基本的常识:

  • 第一代 PC 的 16-bits 的 Intel 8086 处理器,只能访问 1Mb 的内存,最早的 PC 机物理地址空间开始于 0x00000000,结束于 0x0000FFFF 而不是 0xFFFFFFFF 的 64KB
  • Low Memory 的 640KB 的空间只能用于随机的访问(RAM)
  • 从 0x000A0000 开始到 0x000F0000 的 384KB 的空间被保留用于硬件的寻址,比如 VGA
  • 1M 保留空间种最重要的部分是 BIOS ROM,占据从 0x000C0000 到 0x00100000 的 64KB 空间,BIOS 主要是进行硬件检查和初始化工作,最后从硬盘或者 CD-ROM 上装载系统,并且交接控制权给操作系统

JOS 只是用前物理内存的 256M,假装机子有 32-bit 的物理地址空间。

The ROM BIOS

​ 我们尝试进行debug的方式学习,在同一个目录下打开两个窗口,让gdb连接上QEMU进行调试,然后去学习BIOS是如何进行工作的。实验中提供了一个.gdbinit的文件,设置gdb调试的时候使用16位的模式,并且让gdb监听QEMU。

1
2
make qemu-gdb
make gdb

make gdb

​可以看到,gdb 使用了该 .gdbint 文件进行操作,并且成功监听 QEMU。当前的架构是为 i8086 也就是 16-bits 模式,这个时候会执行一条指令:

1
2
[f000:fff0] 0xffff0: ljmp $0x3630,$0xf000e05b
0x0000fff0 in ?()

​这条指令是gdb反汇编产生的代码,可以看到:

  • IBM PC 启动执行的物理地址是再 0x000ffff0,它正是在 ROM BIOS 的高 64KB 的位置
  • PC 执行的时候执行:CS = 0xf000 和 IP = 0xfff0
  • 执行的第一条指令是 jmp,并且跳去的地址是 0xf000e05b,也就是 CS = 0xf000,IP = 0xe05b

​思考一个问题就是为什么 QEMU 里边儿显示的会这样执行?其实这个是 Intel 8086 处理器的设计有关,由于 BIOS 在 PC 中是 “hard-wired” 到物理地址范围0x000f0000-0x000fffff,这样设计是为了保证 PC 加电的时候能够立马执行并且控制系统,因为这个时候 RAM 内存中是没有可以执行的软件儿的(这个软件儿就是 OS)。QEMU emulator 它自带了 BIOS,当处理器重置的时候,QEMU 的虚拟处理器像正常的 CPU 那样,先是进入实模式并且设置 [CS:IP] 为 [0xf000:0xfff0],这样可以让它根据CS:IP 进行访问;

实模式下,CPU 寻址方式是根据 CS:IP 的值来的,physical address = 16 * segment + offset,因此:

​ 16 * 0xf000 + 0xfff0

​ = 0xf0000 + 0xfff0

​ = 0xffff0

Exercise 2

​要求:使用 GDB 命令 si(step instruction)进行单步跟踪,大致了解 BIOS 干了什么,而不需要太清楚细节。

​1、学习一个链接,关于计算机IO的:http://web.archive.org/web/20040404164813/members.iweb.net.au/~pstorr/pcbook/book2/book2.htm

​2、我们进行单步的跟踪得到如下的结果:

gdb si

​总而言之,当 BIOS 运行的时候,它设置好中断描述符表,初始化各种设备比如 VGA 显示器、这个时候 QEMU 中的 “Starting SeaBIOS” 就是初始化显示器过后显示的。在完成 PCI bus 和各种重要的 BIOS 知道的设备初始话过后,它开始寻找可以启动的设备比如软盘、硬盘、CD-ROM,当发现可以启动的设备过后,BIOS 读取该设备中的bootloader 并且将控制权移交给 bootloader。

Part 2:The Boot Loader

​PC 中的软盘、硬盘都可以被划分为一个个的大小为 512 字节的扇区,一个扇区是一次磁盘操作的最小粒度,每一次读取或者写入都必须是一个或者多个扇区。如果一个磁盘是可以用来启动的操作系统的,就把这个磁盘的第一个扇区叫做启动扇区,当 BIOS 找到一个可以启动的软盘或者硬盘过后,它就会将这 512 个字节加载到内存物理地址为 0x7c00 到0x7dff中,然后执行 jmp 来设置 CS:IP 为0000:7c00,转移控制给 boot loader 程序。和 BIOS 的加载地址一样,这些地址都是规定好的标准地址。

​在 6.828 中采用传统的硬盘启动机制,意识是说 boot loader 程序的大小必须小于512 字节,然后整个 boot loader 是由一个汇编文件,boot/boot.S 以及一个 C 语言的文件,boot/main.c 组成,其必须具备两个功能:

​1、boot loader 需要讲 CPU 从 16-bits 实模式切换到 32-bits 保护模式,只有在保护模式下边儿才可以完成超过 1M 的访存能力,并且在保护模式下,segment:offset pair 转换成物理地址的方式也不再是简单的乘以 16,而实更为复杂的段页式模式;

​2、boot loader 通过 x86 特定的 I/O 指令访问 IDE 设备寄存器,从磁盘中将 JOS 的内核读入内存

​说明:boot loader 来说,有一个文件比较重要,obj/boot/boot.asm,这个文件是真实运行的 boot loader 程序的反汇编版本,可以和它的源码 boot.S 和main.c 比较。同理,obj/kern/kernel.asm 也是 JOS kernel 的反汇编版本,后边儿调试应该会用到。

Exercise 3

​要求:在地址 0x7c00 处设置断点,这是 boot sector 被加载的位置。然后让程序继续运行直到这个断点。跟踪 /boot/boot.S 文件的每一条指令,同时使用 boot.S 文件和系统为你反汇编出来的文件 obj/boot/boot.asm。你也可以使用 GDB 的 x/i 指令来获取去任意一个机器指令的反汇编指令,把源文件 boot.S 文件和 boot.asm 文件以及在 GDB 反汇编出来的指令进行比较。追踪到 bootmain 函数中,而且还要具体追踪到readsect() 子函数里面。找出和 readsect() C 语言程序的每一条语句所对应的汇编指令,回到 bootmain(),然后找出把内核文件从磁盘读取到内存的那个 for 循环所对应的汇编语句。找出当循环结束后会执行哪条语句,在那里设置断点,继续运行到断点,然后运行完所有的剩下的语句。

​我们首先查看 boot.S 和 main.c 中源码文件中的内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#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.

.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
cli # Disable interrupts
cld # String operations increment

# Set up the important data segment registers (DS, ES, SS).
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.
seta20.1:
inb $0x64,%al # Wait for not busy
testb $0x2,%al
jnz seta20.1

movb $0xd1,%al # 0xd1 -> port 0x64
outb %al,$0x64

seta20.2:
inb $0x64,%al # Wait for not busy
testb $0x2,%al
jnz seta20.2

movb $0xdf,%al # 0xdf -> port 0x60
outb %al,$0x60

# 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
movl %cr0, %eax
orl $CR0_PE_ON, %eax
movl %eax, %cr0

# Jump to next instruction, but in 32-bit code segment.
# Switches processor into 32-bit mode.
ljmp $PROT_MODE_CSEG, $protcseg

.code32 # Assemble for 32-bit mode
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.
movl $start, %esp
call bootmain

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

# Bootstrap 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

gdtdesc:
.word 0x17 # sizeof(gdt) - 1
.long gdt # address gdt

​然后是 main.c 中几个函数的内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <inc/x86.h>
#include <inc/elf.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?
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)
readseg(ph->p_pa, ph->p_memsz, ph->p_offset);

// call the entry point from the ELF header
// note: does not return!
((void (*)(void)) (ELFHDR->e_entry))();

bad:
outw(0x8A00, 0x8A00);
outw(0x8A00, 0x8E00);
while (1)
/* do nothing */;
}

// Read 'count' bytes at 'offset' from kernel into physical address 'pa'.
// Might copy more than asked
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;

// 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.
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
outb(0x1F3, offset);
outb(0x1F4, offset >> 8);
outb(0x1F5, offset >> 16);
outb(0x1F6, (offset >> 24) | 0xE0);
outb(0x1F7, 0x20); // cmd 0x20 - read sectors

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

// read a sector
insl(0x1F0, dst, SECTSIZE/4);
}

​研究上述的两段儿代码,我们可以知道基本的过程,首先这两段儿程序共同构成了 boot loader 程序,并且这两段儿程序放到磁盘的第一个扇区作为启动扇区。BIOS 加载该扇区,同时这两段代码先执行的是 boot.S,在 boot.S 中从实模式切换到保护模式,并且建立好堆栈,在堆栈建立好过后才能够开始运行 C 代码,这个时候执行 main.c 中的函数bootmain(),然后 bootmain() 将内核加载进来过后,开始将控制权交给 JOS Kernel,这样就完成了启动工作。

​能够回答以下问题:

  • 处理器从什么时候开始执行 32 位代码?究竟是什么导致从 16 位模式切换到 32 位模式?

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
      .code32                     # Assemble for 32-bit mode
    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.
    movl $start, %esp
    call bootmain

    系统从.code32部分开始执行32位代码如上所示;

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    .globl start
    start:
    .code16 # Assemble for 16-bit mode
    cli # Disable interrupts
    cld # String operations increment

    # Set up the important data segment registers (DS, ES, SS).
    xorw %ax,%ax # Segment number zero
    movw %ax,%ds # -> Data Segment
    movw %ax,%es # -> Extra Segment
    movw %ax,%ss # -> Stack Segment

    CPU首先是运行在实模式,这个时候的 boot loader 运行在 16-bits 模式下边儿,这个时候中断屏蔽;由于之前 BIOS 执行的时候我们不清楚会不会寄存器内的内容是否会变我们无法保证,因此将 %ax 内的内容设置为0过后赋值给 %ds、%es、%ss 三个寄存器来清零;

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
      # 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.
    seta20.1:
    inb $0x64,%al # Wait for not busy
    testb $0x2,%al
    jnz seta20.1

    movb $0xd1,%al # 0xd1 -> port 0x64
    outb %al,$0x64

    seta20.2:
    inb $0x64,%al # Wait for not busy
    testb $0x2,%al
    jnz seta20.2

    movb $0xdf,%al # 0xdf -> port 0x60
    outb %al,$0x60

    由于运行在实模式下,物理主线的低 20 位是没有用到的,以至于总是使用高地址的 1 M 内存,因此需要开启 A20 模式,来让这些位可以使用。为什么这样可以让 A20 开启呢?在 Intel 设计中,通过键盘控制器寄存器来实现 A20 开启,如主线 port 描述中所述:http://bochs.sourceforge.net/techspec/PORTS.LST

    port

    port value

    A20

    可以看到,其中 0x64 端口是键盘控制器,当 0xd1 值输出到 0x64 port 里边儿,这个时候使 A20 gate 受到控制,然后再向 0x0060 port 写入 0xdf,这个时候根据port 描述可知,直接 enable address A20,至此 CPU 可以达到寻址范围增加,开启A20 成功。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # 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
    movl %cr0, %eax
    orl $CR0_PE_ON, %eax
    movl %eax, %cr0

    # Jump to next instruction, but in 32-bit code segment.
    # Switches processor into 32-bit mode.
    ljmp $PROT_MODE_CSEG, $protcseg

    由上述知道,CR0_PE_ON 里边儿的值是 0x1,这个是保护模式 enable 的标志,加载好全局描述符表过后,cr0 控制器要通过异或将标志位打开,同时最后执行一个 jmp 指令,其中 $PROT_MODE_CSEG,这个是 JOS kernel 的代码段地址,在保护模式下运行该代码段,这样就顺利切换到了 Kernel。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    # Bootstrap 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

    gdtdesc:
    .word 0x17 # sizeof(gdt) - 1
    .long gdt # address gdt

    其中 lgdt gdtdesc,把 gdtdesc 标识符的值送入全局映射描述符表 GDTR 中,CPU 的 GDTR中 保存了 gdt 的起始地址和 gdt 表的长,其中 GDTR 是一个位宽位 48 的寄存器,低 16 位表示该表的长度,高 32 表示该表在内存中的起始位置。gdtdesc 是一个标识符,其中前 2 个字节表示 gdt 表大小,后 4 个字节表示 gdt 表的内存中地址起始位置。

    而 gdt 描述符分为了三个段,分别是 null seg、code seg、data seg,而 JOS 中是没有分段机制的,也就是说数据和代码都是写在一起的,所以数据段和代码段的起始地址都是 0x0,大小都是 0xfffffffff = 4GB。

    其中 SEG() 函数我们可以在 mmu.h 中找到,它是一个宏函数:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    /*
    * Macros to build GDT entries in assembly.
    */
    #define SEG_NULL \
    .word 0, 0; \
    .byte 0, 0, 0, 0
    #define SEG(type,base,lim) \
    .word (((lim) >> 12) & 0xffff), ((base) & 0xffff); \
    .byte (((base) >> 16) & 0xff), (0x90 | (type)), \
    (0xC0 | (((lim) >> 28) & 0xf)), (((base) >> 24) & 0xff)

    #else // not __ASSEMBLER__

其中函数参数优势按个,分别是 type 表示了访问权限,base 表示这个段的起始地址,lim 表示这个段的大小界限。

完成上述步骤过后,就可以 call bootmain,这个时候将 kernel.img 从磁盘中读进来,然后就可以开始执行啦。

  • 引导加载程序执行 的最后一条指令是什么,它刚刚加载的内核的第一条指令是什么?

最后一条指令是bootmain程序中的((void (*)(void)) (ELFHDR->e_entry))(); 即跳转到操作系统内核程序的起始指令处。

它刚刚加载的第一条指令是位于 kern/entry.S 文件中的第一句,movw $0x1234,0x472

  • 内核的第一条指令在哪里?

kern/entry.S

  • 引导加载程序如何决定它必须读取多少个扇区才能从磁盘获取整个内核?它在哪里找到这些信息?

引导加载程序读取操作系统文件 Program Header Table 中,这个表会描述整个内核占了几个扇区,需要读取多少个段才可以将内核加载进来;这些信息保存在 kernel.img 的ELF 头部信息当中

Loading the Kernel

​学习 boot/main.c,在此之前需要学习 C 语言的指针,这个也是一个难点,同时需要学习 ELF 文件的格式,这样才能够继续阅读代码。

Exercise 4

​要求:阅读 K&R 中 5.1-5.5,学习 C 语言中指针和地址,然后下载 pointers.c 文件,运行它,并且搞懂那些值为什么会这样出现。其中该程序如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <stdlib.h>

void
f(void)
{
int a[4];
int *b = malloc(16);
int *c;
int i;

printf("1: a = %p, b = %p, c = %p\n", a, b, c);

c = a;
for (i = 0; i < 4; i++)
a[i] = 100 + i;
c[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]);

c[1] = 300;
*(c + 2) = 301;
3[c] = 302;
printf("3: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
a[0], a[1], a[2], a[3]);

c = c + 1;
*c = 400;
printf("4: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
a[0], a[1], a[2], a[3]);

c = (int *) ((char *) c + 1);
*c = 500;
printf("5: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
a[0], a[1], a[2], a[3]);

b = (int *) a + 1;
c = (int *) ((char *) a + 1);
printf("6: a = %p, b = %p, c = %p\n", a, b, c);
}

int
main(int ac, char **av)
{
f();
return 0;
}

​编译并执行所得结果如下所示,结果分析:

​学习完 CSAPP 咱们都应该知道,指针是指向某个内存地址的一个标识,而且指针也是具有不同的类型的,C 语言提供了访问指针地址的操作,同样提供了访问该地址位置的值的操作,指针操作是会改变该内存地址的值的,因此,不论多少指针或者说指针张啥样,只要修改其中任何一个指针的值,则其他指向该地址的指针的值都会改变,因此我们可以知道:

​a、b、c均是指向int类型的指针,不同点是 a 是采用数组的方式直接静态分配了内存,其大小为 4*4 字节,并且 a 执行数组的起始地址即 a[0];b 采用动态 malloc 的方式分配了 16 个字节的 void 类型地址,并且 b 指向这块内存的起始地址;c 只是命名了一个空指针,其单纯指向一个地址,没有大小或者说指针自身大小即根据多少位机子判断,其指向内存中的某个 int 的地址;我们也应该知道 int 是 4 个字节,指针大小和计算机位数有关,如 64-bits 的是 8 字节,32-bits 是 4 字节;

​c = a 让 c 和 a 同时指向了一块儿数组内存地址的起始地址,所以 c 和 a 就没有任何区别了就;

​第二行结果中,先循环修改了 a 的内容,然后修改 c[0] 中的值,由于 c 和 a 指向同一内存地址,因此 a[0] 的值改变;

第三行结果中,由于c进行了修改,c和a相同,那么a的值也进行了改变,只是说访问内存的方式不同罢了,其中几种访问都是一次内存增加int个字节大小;

第四次结果中,只改变了 c[1] 的值,因此和第三次比较只进行了 c[1] 的改变;

​第五次结果中,先是将 c[1] 通过 char 指针增长 1 个字节,访问 c[2] 的前 1 个字节,再将其转换成了 int 类型,因此目前 c 指向 int* a[1] 的后 3 个字节,同时起内存长度是 4 个字节,因此当前 c 指向的内存的末尾是 a[2] 的前 1 个字节的尾巴,再让 *c = 500 的时候,a[1]、a[2] 的值都进行了改变;

​第六次结果中,我们可以通过地址的大小发现,刚好验证了第五次中结果为啥是这样。

pointer.c results

ELF kernel.img

​单独列了一个标题为 ELF 的文件,主要是为了好好学习 ELF,这个部分有一些复杂的信息,需要进行记录和积累。点击可下载elf.pdf

​在 6.828 中,可以将 ELF 文件看作是一个带有固定的 header 的可执行代码文件,其中代码被分成了不同的段包含了 code、data 等等,这些地址是在文件中定义好了的而boot loader 不会定义这些地址,这些东西可以根据描述的地址加载进内存直接进行执行。

​一个 ELF 二进制文件中,包含一个指定长度的头部,候面跟了几个代码块,这些个代码块可以分为程序和数据,可以在 inc/elf.h 中看到如下结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#ifndef JOS_INC_ELF_H
#define JOS_INC_ELF_H

#define ELF_MAGIC 0x464C457FU /* "\x7FELF" in little endian */

struct Elf {
uint32_t e_magic; // must equal ELF_MAGIC
uint8_t e_elf[12];
uint16_t e_type;
uint16_t e_machine;
uint32_t e_version;
uint32_t e_entry;
uint32_t e_phoff;
uint32_t e_shoff;
uint32_t e_flags;
uint16_t e_ehsize;
uint16_t e_phentsize;
uint16_t e_phnum;
uint16_t e_shentsize;
uint16_t e_shnum;
uint16_t e_shstrndx;
};

struct Proghdr {
uint32_t p_type;
uint32_t p_offset;
uint32_t p_va;
uint32_t p_pa;
uint32_t p_filesz;
uint32_t p_memsz;
uint32_t p_flags;
uint32_t p_align;
};

struct Secthdr {
uint32_t sh_name;
uint32_t sh_type;
uint32_t sh_flags;
uint32_t sh_addr;
uint32_t sh_offset;
uint32_t sh_size;
uint32_t sh_link;
uint32_t sh_info;
uint32_t sh_addralign;
uint32_t sh_entsize;
};

// Values for Proghdr::p_type
#define ELF_PROG_LOAD 1

// Flag bits for Proghdr::p_flags
#define ELF_PROG_FLAG_EXEC 1
#define ELF_PROG_FLAG_WRITE 2
#define ELF_PROG_FLAG_READ 4

// Values for Secthdr::sh_type
#define ELF_SHT_NULL 0
#define ELF_SHT_PROGBITS 1
#define ELF_SHT_SYMTAB 2
#define ELF_SHT_STRTAB 3

// Values for Secthdr::sh_name
#define ELF_SHN_UNDEF 0

#endif /* !JOS_INC_ELF_H */

​program section中我们关注以下几个部分:

  • .text:程序可执行指令;

  • .rodata:只读数据;

  • .data:data section 包含了已经初始话的数据,比如全局变量 int x = 5;

  • .bss : 存放未初始化的变量, 但是在ELF中只需要记录 .bss 的起始地址和长度。Loader and program 必须自己将 .bss 段清零

我们可以通过objdump -h obj/kern/kernel来查看所有的名字和地址范围:

kernel headers

​在 JOS 中我们只关注上述的几个段,有一些我们需要特别关注的,比如 VMA(link address)、LMA(load addres),其中 LMA 就是程序运行的时候加载到内存中的位置,VMA 的话比较复杂,主要是用来添加或者执行一些共享的库之类的,在 JOS 中没有使用该段。

​我们同样可以通过objdump -h obj/boot/boot.out来查看 boot loader .text区域:

boot.out header

​我们可以看到其 LMA 的地址和 VMA 的地址都是 0x7c00,这个和我们之前看到的 BIOS 启动跳转的地址相同。

​同理,我们可以通过 objdump -x obj/kern/kernel 来查看整个kernel的header信息等。

kernel header all

​我们可以看到 LOAD 中的需要加载到内存中的区域,vaddr 是虚拟地址、paddr 是物理地址、加载区域大小 filesz/memsz,在 boot/main.c 中,ph->p_pa 每个程序头的字段都包含段的目标物理地址。BIOS 将引导扇区加载到内存中,从 0x7c00 开始,因此这是引导扇区的起始地址,由于这个地址也是引导扇区执行的地方,所以它也是链接地址,我们设置连接地址 -Ttext 0x7c00 到链接器 boot/Makefrag,链接器将产生正确的代码地址。

Exercise 5

​要求:先跟踪部分 boot loader 中的一小部分步骤,然后修改 boot/Makefrag 中的链接地址,查看其行为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#
# Makefile fragment for the JOS kernel.
# This is NOT a complete makefile;
# you must run GNU make in the top-level directory
# where the GNUmakefile is located.
#

OBJDIRS += boot

BOOT_OBJS := $(OBJDIR)/boot/boot.o $(OBJDIR)/boot/main.o

$(OBJDIR)/boot/%.o: boot/%.c
@echo + cc -Os $<
@mkdir -p $(@D)
$(V)$(CC) -nostdinc $(KERN_CFLAGS) -Os -c -o $@ $<

$(OBJDIR)/boot/%.o: boot/%.S
@echo + as $<
@mkdir -p $(@D)
$(V)$(CC) -nostdinc $(KERN_CFLAGS) -c -o $@ $<

$(OBJDIR)/boot/main.o: boot/main.c
@echo + cc -Os $<
$(V)$(CC) -nostdinc $(KERN_CFLAGS) -Os -c -o $(OBJDIR)/boot/main.o boot/main.c

$(OBJDIR)/boot/boot: $(BOOT_OBJS)
@echo + ld boot/boot
$(V)$(LD) $(LDFLAGS) -N -e start -Ttext 0x7C00 -o $@.out $^
$(V)$(OBJDUMP) -S $@.out >$@.asm
$(V)$(OBJCOPY) -S -O binary -j .text $@.out $@
$(V)perl boot/sign.pl $(OBJDIR)/boot/boot

​我们可以看到,通过编译生成了 boot/ 文件夹下的内容,并且在最后根据地址进行链接,我们尝试修改 0x7c00 为错误的地址 0x7000,看会如何执行;

0x7000 error

​我们可以看到在这个情况下边儿,由于 boot loader 加载地址,无法正常启动,导致 BIOS 不断重启去寻找可以启动的盘,此时的 qemu 就陷入了死循环,当我们把地址改为正确的时候,则可以正常启动,不过得执行命令 make clean 再重新编译。

Exercise 6

​要求:使用 GDB 中 x 命令来检测地址,其中 x/Nx ADDR 命令打印从 ADDR 开始的 N 个字的地址。测试 0x00100000 地址开始的 8 个字的内存,然后再引导程序进入内核时再次检查,他们为什么不同?第二个断点有什么?

x/Nx ADDR

​我们知道在 ELF 头中保存了一个叫做 e_entry 的字段,该字段中保存了程序中入口点的地址,也就是 kernel 的入口地址,我们根据要求查看进入内核前后的该处地址情况,发现在运行内核过后,内存 0x0010000 中加载了内核的代码地址。

Part 3:The Kernel

​第三个部分我们开始研究内核,在将内核加载到内存中,并且根据 e_entry 字段进入内核代码过后,CPU 流水开始执行 kernel,JOS 运行了起来。

虚拟内存解决位置依赖

​操作系统的内核通常被链接到非常高的虚拟地址如(0x00100000)下运行,以便留下处理器虚拟地址空间的低地址部分供用户程序使用。

​许多机子在地址范围无法到达 0xf0100000,因此我们不能在该处存储内核,我们可以使用处理器提供的内存管理硬件将虚拟地址 0xf0100000(内核代码期望云运行的链接地址)映射到物理地址 0x00100000(引导加载程序将内核加载到物理内存中)。

​我们目前不需要掌握细节,我们只需要知道可以通过 kern/entrypgdir.c 中静态初始化的页面目录和页表来完成此操作,映射前 4M 的物理内存就可以启动并运行起来。在内存映射的过程中有一个非常重要的寄存器,cr0 控制寄存器,当我们在 kern/entry.S 中设置 CR0_PG 标志位过后,内存映射打开,这个时候的虚拟地址被映射成了物理地址。此处我们开启了页机制,我们将虚拟地址 0xf0000000 到 0xffffffff 映射到 0x000000000到 0x0ffffffff。

Exercise 7

​要求:使用GDB调试跟踪内核并且停止在 movl %eax, %cr0 部分,并且检测内存0x00100000 和 0xf0100000,并且单步跟踪 GDB,查看内存前后内容的差别。

kernel.asm 指令地址

​我们可以在 obj/kern/kernel.asm 反汇编得到的代码中看到,movl %eax, %cr0 的代码地址为 0xf0100020,因此我们在此处设置断点,并且观察前后cr0寄存器的行为和内容;出现一个小错误就是,这里的 0xf0100020 是虚拟地址,我们需要跟踪映射过后的实际的地址,而实际的映射规则正如前边儿提到的,因此我们设置的断点应该为 0x00100020;

breakpoint

​我们可以看到,在该命令执行之后,原本放在 0xf0100000 处的内容映射到了0x00100000 处,因为这两个地方的值完全一样。

​接下来我们将 movl %eax, %cr0 注释掉,查看会发生什么:

make qemu no %cr0

​会发现,操作系统无法启动,这个时候由于没有开启页机制,kernel 的地址映射没有成功,从而超出了寻址范围,导致操作系统内核无法启动,修改回去可以成功启动。

格式化输出到控制台

​这个小节主要是为了说明,操作系统中是没有 printf() 这种函数的,我们需要去写一个可以输出到界面的比如 vga 的输出,并且封装来供使用,比如当前的 kernel 中就提供了三个和输出相关的文件 kern/printf.c,lib/printfmt.c 和 kern/console.c,我们需要学习这三个咋搞起来的还有他们之间的关系。

Exercise 8

​要求:在printfmt.c中省略了打印八进制数的格式,%o的格式选项,需要我们进行补充

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// (unsigned) octal
case 'o':
// Replace this with your code.
//putch('X', putdat);
//putch('X', putdat);
//putch('X', putdat);
//
num = getint(&ap,lflag);
if((long long)num <0){
putch('-',putdat);
num = -(long long) num;
}

base = 8;
goto number;

​这个还行,只需要照着前边儿的 10 进制进行复制就好了,基本没有难度,补充完毕就ok,接下来是回答一堆问题:

  • 1、解释 printf.c 和 console.c 之间的接口,尤其是 console.c 导出了什么函数,printf.c 如何使用这些函数?

printf.c 使用了 console.c 的 cputchar() 函数,通过直接调用该函数完成输出到vga 上;同时 printf.c 也使用 printfmt.c 中包装过的 console.c 中的函数,这样便于格式化的输出到屏幕上。

  • 2、解释console.c中的一段儿程序:
1
2
3
4
5
6
7
8
9
// What is the purpose of this?
if (crt_pos >= CRT_SIZE) {
int i;

memmove(crt_buf, crt_buf + CRT_COLS, (CRT_SIZE - CRT_COLS) * sizeof(uint16_t));
for (i = CRT_SIZE - CRT_COLS; i < CRT_SIZE; i++)
crt_buf[i] = 0x0700 | ' ';
crt_pos -= CRT_COLS;
}

​由于当前的输出是到 VGA 显示,这个地方是检测 ctr_pos 指针施否超出了 CTR 的范围,如果超出了,则需要对超出部分的显示缓存内容清零,并且对 ctr_pos 进行重新设置回到该位置。

  • 3、跟踪下边儿的一段儿代码:
1
2
int x = 1, y = 3, z = 4;
cprintf("x %d, y %x, z %d\n", x, y, z);

​cprintf(),fmt指向什么?ap又指向什么?

​这一段儿代码我们可以考虑插入到内核的任何位置,为了便于跟踪,我们可以考虑到加入的内核的初始化的地方 kern/init.c,因此我们加入过后进行跟踪:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void
i386_init(void)
{
extern char edata[], end[];

// Before doing anything else, complete the ELF loading process.
// Clear the uninitialized global data (BSS) section of our program.
// This ensures that all static/global variables start out zero.
memset(edata, 0, end - edata);

// Initialize the console.
// Can't call cprintf until after we do this!
cons_init();

cprintf("6828 decimal is %o octal!\n", 6828);

// Lab 1 exercise 8
{
// Trace the execution of the following code step-by-step

Lab1_exercise8_3:
{
int x = 1, y = 3, z = 4;
cprintf("x %d, y %d, z %d\n",x, y, z);
}

Lab1_exercise8_4:
{
// Run the following code
unsigned int i = 0x00646c72;
cprintf("H%x Wo%s\n",57616, &i);
}
Lab1_exercise8_5:
{
// y = ?
cprintf("x=%d y=%d\n",3);
}
}

// Test the stack backtrace function (lab 1 only)
test_backtrace(5);

// Drop into the kernel monitor.
while (1)
monitor(NULL);
}

​我们在obj/kern.kernel.asm 中找到添加的代码的位置,打上断点进行跟踪,具体方法和前边儿的调试方法相同,于是得到以下结果:

init

​单步运行,跟踪每个 call 中 cons_putc,va_arg 和 vcprintf,对于 cons_putc 列出参数,对于 va_arg,列出 ap 在调用前后分别指向什么,对于 vcprintf 列出参数和值

printfmt.c

​其他的也类似挨着跟踪一下就好了,可以看到调用链和每次传入的值。对于其中的可变参数的实现,我们可以在 inc/stdarg.h 中找到,为什么可以实现可变参数主要原因是因为函数的参数压栈是从左到右依次进栈的,然后根据这个规则进行取就好了。

  • 4、运行下边儿的代码,查看结果是什么:
1
2
unsigned int i = 0x00646c72;
cprintf("H%x Wo%s", 57616, &i);

​结果是:hell0,World,这个地方的输出跟ASCII码有关,凑成了 hell0 world

  • 5、下边儿的代码,y后边儿会输出什么?
1
cprintf("x=%d y=%d", 3);

​y 后边儿跟了一个未知的数

  • 6、GCC改变调用的时候参数压栈顺序,如何修改 cprintf() 函数可以让他输出可变个数的参数?

如果是从右往左进行压栈,我们可以考虑传进去一个参数个数的值,然后我们获取参数的从末尾开始拿就好了

The Stack

​我们最后来研究一下 X86 上的 C 语言栈,我们会实现一个 backtrace 的函数,来对栈内的参数和 IP 信息等进行打印出来。

Exercise 9

​要求:判断内核在哪个地方初始化的栈,并且判断栈在内存中的位置,内核是如何为栈保存空间的?并且在这个保留区域的 “end” 是堆栈指针最初指向的位置嘛?

栈的初始化,最先是在 boot loader 中,然后在进入内核过后,内核也对栈进行了重新初始化。​entry.S 中初始化的,然后初始化的时候我去调用 kernel.asm 文件,然后观察栈的大小啥的:

entry.S

在 memlayout.h 和 mmu.h 中可以找到内核栈的相关情况,理论上只要是空闲的物理地址都可以作为栈,JOS 对栈的定义在 memlayout.h 中:

  • 内核在 entry.S 中进行栈的重新初始化
  • 栈在内存中的位置,KSTACKTOP:KERNBASE(0xF0000000)
  • 内核为栈预留 KSTKIZE(8*PGSIZE,PGSIZE=4096) 的空间

Exercise 10

​要求:为了熟悉 X86 中 C 调用约定,test_backtrace 在 obj/kern/kernel.asm 中找到函数地址,在那里设置一个断点,然后检查内核启动后每次调用它会发生什么。每个递归嵌套级别的 test_backtrace 推入堆栈的32位字是多少,这些字是什么?

首先,我们再次熟悉x86栈的约定是长什么样:

x86 堆栈结构

​每个栈帧中保存了上述的信息,其中,%esp 寄存器始终指向栈顶,并且每一次入栈的时候,%esp 的减少,在 32-bit 模式下,堆栈只能保存 32-bit 的值,并且 %esp 总是可以被 4 整除。

%ebp 寄存器,基址寄存器,每一次函数调用压栈的时候,将 %esp 的值保存到 %ebp中,每一次都这样按照这个约定,这样的话每次取 %ebp 的上一次的值就可以拿到栈的调用链。

Exercise 11

​于是基于上述 exercise 10 中堆栈的描述约定的方式,我们可以进行栈的跟踪打印,实现方式如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int
mon_backtrace(int argc, char **argv, struct Trapframe *tf)
{
// Your code here.
// Lab 1 exercise 9

uint32_t ebp,*p,eip;
ebp = read_ebp();

cprintf("Stack backtrace:\n");
while(ebp != 0){
p = (uint32_t*) ebp;
eip = p[1];
cprintf("ebp %08x eip %08x args %08x %08x %08x %08x %08x\n", ebp, eip, p[2], p[3], p[4], p[5], p[6]);
ebp = p[0];
}
return 0;
}

​然后将其添加到内核的 cmd 中:

1
2
3
4
5
static struct Command commands[] = {
{ "help", "Display this list of commands", mon_help },
{ "kerninfo", "Display information about the kernel", mon_kerninfo },
{ "backtrace","Display the stack backtrace info",mon_backtrace},
};

​此时,我们就可以在内核启动的时候,调用 backtrace 完成堆栈跟踪展示信息了就。

Exercise 12

​要求:打印 debug info 出来,利用 eip,在 kern/kdebug.c 中完成检测;并且完成 stab_binsearch 取寻找一个地址的行号编号,然后添加 debuginfo_eip 到mon_backtrace 中,然后查看施否能够打印出来;

​先手动完成命令行的查看,然后编写二分搜索,阅读给出的 stab_binsearch 函数,按照二分的模板写吧和算法相同:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Search within [lline, rline] for the line number stab.
// If found, set info->eip_line to the right line number.
// If not found, return -1.
//
// Hint:
// There's a particular stabs type used for line numbers.
// Look at the STABS documentation and <inc/stab.h> to find
// which one.
// Your code here.

stab_binsearch(stabs,&lline,&rline,N_SLINE,addr);
if(lline <= rline){
info->eip_line = stabs[lline].n_desc;
}
else{
cprintf("line not find\n");
return -1;
}

​然后就是在 mon_backtrace 中添加:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

int
mon_backtrace(int argc, char **argv, struct Trapframe *tf)
{
// Your code here.
// Lab 1 exercise 9

uint32_t ebp,*p,eip;
ebp = read_ebp();
struct Eipdebuginfo info;

cprintf("Stack backtrace:\n");
while(ebp != 0){

p = (uint32_t*) ebp;
eip = p[1];
cprintf("ebp %08x eip %08x args %08x %08x %08x %08x %08x\n", ebp, eip, p[2], p[3], p[4], p[5], p[6]);

int c = debuginfo_eip(eip,&info);
if (c == 0){
int fn_offset = eip - info.eip_fn_addr;
cprintf("%s:%d: %.*s+%d\n", info.eip_file, info.eip_line, info.eip_fn_namelen, info.eip_fn_name, fn_offset);
}

ebp = p[0];
}
return 0;
}

​然后尝试 make grade 一下,完结撒花完成整个实验:

tests OK

​至此 Lab1 完结撒花。

补充一个点儿,有可能在 grade 的时候会失败,具体原因是由于 qemu 的执行结果重定向到 jos.out 文件过后,可能会有换行问题,导致 Python 的grade 脚本匹配失败,如:

grade fail

缺少回车

解决方法就是在 6828 前边儿加个回车符号,满足脚本儿要求。


Lab1 Booting a PC
https://www.bencorn.com/2021/08/09/Lab1-Booting-a-PC/
作者
Bencorn
发布于
2021年8月9日
许可协议