OS - Lab 6: Driver and LibC
目录
Operating Systems (H) @ Fudan University, fall 2020.
1 实验简介
2 实验报告
2.1 I/O 框架
2.1.1 请求队列
实验目标
请补全 inc/buf.h 以便于 SD 卡驱动中请求队列的实现,即每个请求都是一个 buf,所有请求排成一队。
这里直接参考了 xv6 和 xv6-riscv 的设计,具体作用参见注释:inc/buf.h
1
2
3
4
5
6
7
8
9
10
;
对于一个请求(buf)队列,我们在 kern/bio.c 中定义了 bcache。kern/bio.c
1
2
3
4
5
6
7
8
9
bcache;
本质上,bcache 是一个带哨兵节点的双向循环链表。这里 NBUF 的值定义为 30,表示请求队列长度的最大值。
在使用前,我们先对 bcache 进行初始化,也就是创建一个双向循环链表,并初始化每个 buf 的锁。kern/bio.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void
当我们需要进行读操作时,我们先调用函数 bget 在 bcache 中获取一个可用的 buf。如果这个请求已经在 bcache 里了,那么就将相应的 buf 的 refcnt 加 1,然后加锁并返回。否则,我们回收一个最早使用过的(Least Recently Used, LRU)且当前不在使用中的 buf,将其 refcnt 设置为 1,然后加锁并返回。kern/bio.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
/*
* Look through buffer cache for block on device dev.
* If not found, allocate a buffer.
* In either case, return locked buffer.
*/
static struct buf*
随后,我们调用函数 bread 对这个 buf 进行读操作。kern/bio.c
1
2
3
4
5
6
7
8
9
10
11
12
13
/*
* Return a locked buf with the contents of the indicated block.
*/
struct buf*
其中,常量 LBA 指的是第 2 个分区起始块的逻辑区块地址(logical block address, LBA),LBA 的值(0x20800)将在 SD 卡初始化:sd_init 节解析主引导记录时得到。这里之所以要给 block number 加上这个偏移量,是因为我们需要先定位到我们的文件系统,而第 2 个分区正是我们的文件系统所在的根目录分区。函数 sd_rw 负责 SD 卡的读写操作,详情将在 SD 卡读写磁盘:sd_rw 节提到。
当我们需要进行写操作时,我们调用函数 bwrite 对这个 buf 进行写操作。kern/bio.c
1
2
3
4
5
6
7
8
9
10
/*
* Write b's contents to disk. Must be locked.
*/
void
最后,当我们需要释放一个 buf 时,我们调用函数 brelse 将它的 refcnt 减 1。如果此时 refcnt 的值为 0,说明已经没有设备在等待这个 buf 了,那么我们就将这个 buf 移动到 bcache 的头部(实际上是 head->next),表示这是一个最晚使用过的(Most Recently Used, MRU)buf。kern/bio.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
* Release a locked buffer.
* Move to the head of the most-recently-used list.
*/
void
此外,我们还定义了函数 bpin 和 bunpin,分别用于将一个 buf 的 refcnt 加 1 或减 1。kern/bio.c
1
2
3
4
5
6
7
void
kern/bio.c
1
2
3
4
5
6
7
void
2.2 块设备驱动
2.2.1 Sleep 实现
实验目标
请完成 kern/proc.c 中的 sleep 和 wakeup 函数,并简要描述并分析你的设计。
函数 sleep 的工作是释放进程所持有的锁,设置进程状态为 SLEEPING,并在 chan 上睡眠,然后调用函数 sched 回到 scheduler,决定下一个运行的程序。当进程被唤醒且再次轮到本进程执行时,重新获取进程本来持有的锁。由于我们在执行 sleep 前会先获取进程锁 p->lock,而执行 wakeup 时同样需要先获取进程锁,因此我们可以确定在执行 sleep 的过程中,进程不会被意外 wakeup,导致这个 wakeup 没有被捕获到,进程永远不再醒来。kern/proc.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
/*
* Atomically release lock and sleep on chan.
* Reacquires lock when awakened.
*/
void
函数 wakeup 的工作是将指定 chan 上睡眠的进程全部唤醒,设置进程状态为 RUNNABLE,从而可以被 scheduler 调度。kern/proc.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
* Wake up all processes sleeping on chan.
* Must be called without any p->lock.
*/
void
2.2.2 SD 卡初始化
实验目标
请完成 kern/sd.c 中的 sd_init, sd_intr, sd_rw,然后分别在合适的地方调用 sd_init 和 sd_test 完成 SD 卡初始化并通过测试。
我研究了半天,最后还是觉得要修改其他源代码才能比较优雅地实现这几个函数,否则结构实在太乱了,可复用性也很差。而且引用的这个 源代码 的代码风格简直不忍直视,看得恶心,最后还是先全部简单改了一遍。完全改过来还是算了,style fix 约等于 refactor,像日志输出全是乱打的。强烈建议每一位 C / C++ 程序员在写代码前先通览一遍 Google C++ Style Guide 或者其他随便什么靠谱的 style guide,最起码要保证前后的风格是统一的,不要随心所欲想怎么写就怎么写。
2.2.2.1 SD 卡读写磁盘: sd_rw
为了优雅地实现 sd_init,我们决定先实现 sd_rw。
这里我们就直接在函数 _sd_start 里修改了,因为它其实已经实现了 SD 卡的写操作,我们只需在它的基础上增加一个读操作即可(直接读到 buf->data)。根据 buf 的 flags 中 B_DIRTY 位的值,我们可以判断此时应当采取读操作(0)还是写操作(1)。kern/sd.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
/*
* Start the request for b. Caller must hold sdlock.
*/
static void
在函数 sd_rw 里,我们先调用函数 _sd_start 对 buf 进行 I/O 操作,然后将其 flags 的 B_DIRTY 位设置为 0、B_VALID 位设置为 1,最后调用函数 brelse 释放 buf(见 请求队列 节)。kern/sd.c
1
2
3
4
5
6
7
8
9
10
11
12
/*
* Sync buf with disk.
* If B_DIRTY is set, write buf to disk, clear B_DIRTY, set B_VALID.
* Else if B_VALID is not set, read buf from disk, set B_VALID.
*/
void
2.2.2.2 SD 卡中断处理: sd_intr
函数 sd_intr 的工作是处理设备中断。具体来说,检查请求是否已执行完毕,然后清空中断信息。kern/sd.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* The interrupt handler.
*/
void
我稍微解释一下为什么只有这么点内容。简单来说是因为大多数事情已经被其他函数干掉了,具体来说:
- 不需要检查
bcache是否为空,因为我们不需要对bcache中的buf进行读写,原因见 2。 - 不需要检查中断是否可能为
INT_READ_RDY,因为我们在函数_sd_start里已经完成了读取到buf->data的操作,它只能为INT_DATA_DONE。 - 不需要获取
bcache的队首buf,原因同 1。 - 不需要判断请求类型,并据此判断中断是否合法,原因同 2。
- 不需要将数据读取到
buf->data,原因同 2。 - 不需要设置
buf->flags,因为我们在函数sd_rw里完成了这项操作。 - 不需要唤醒
buf,因为我们在函数brelse里完成了这项操作。 - 不知道是否需要继续进行下一个
buf的读写操作,因为测试代码里似乎没有对函数sd_intr的测试,我不清楚文件系统里会怎么调用这个sd_intr。- 毕竟文件系统是我自己设计的,而我大概不太会采用样例里的这个中断处理逻辑。
- 目前我的
bcache不需要手动维护其结构,如果需要一个清空buf队列的操作(我猜sd_intr可能想干这个事情),到时候我可以直接在bcache提供一个方法bclear,思路是循环调用sd_rw,并不需要让sd_intr去处理这个事情。 - 还是要看实际的应用场景,在有函数需要用到
sd_intr前我不打算写这一部分,反正这个需求到时候加起来很快的。
2.2.2.3 SD 卡初始化: sd_init
函数 sd_init 的工作分为两部分:
- 初始化 SD 卡
- 解析主引导记录(Master Boot Record, MBR)
对于第一部分,我们只需调用函数 _sd_init 初始化 SD 卡即可。
对于第二部分,我们先从磁盘地址 0x0 处读取 MBR 到 buf,然后利用函数 _parse_partition_entry 解析每条磁盘分区表项(partition table entry, PTE)并输出其内容,其中 4 条分区表的地址分别为 0x1BE, 0x1CE, 0x1DE, 0x1EE,最后输出 2 字节的结束标志(若为 55, AA 则表示 MBR 有效)1。kern/sd.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
/*
* Initialize SD card and parse MBR.
* 1. The first partition should be FAT and is used for booting.
* 2. The second partition is used by our file system.
*
* See https://en.wikipedia.org/wiki/Master_boot_record
*/
void
其中,函数 _parse_partition_entry 负责解析各分区表项,并输出以下信息1:
- 磁盘状态(state)
- 分区内第一个扇区的柱面-磁头-扇区(cylinder-head-sector, CHS)地址
- 分区类型(partition type)
- 分区内最后一个扇区的柱面-磁头-扇区地址
- 分区内第一个扇区的逻辑区块地址(logical block address, LBA)
- 分区内的总扇区数(number of sectors)
kern/sd.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 | |
这里函数 _parse_uint32_t 用于将 4 个字节(uint8_t)按照小端法(little-endian)合并为一个 32 位的整数(uint32_t)。kern/sd.c
1
2
3
4
5
6
static uint32_t
2.2.2.4 SD 卡初始化及测试
在函数 main 中,调用函数 sd_init 完成 SD 卡初始化,调用函数 sd_test 进行测试。kern/main.c
1
2
3
4
5
6
7
8
9
10
11
void
2.3 制作启动盘
2.3.1 获取分区信息
实验目标
请在 sd_init 中解析 MBR 获得第二分区起始块的 LBA 和分区大小以便后续使用。
见 SD 卡初始化:sd_init 节,我们将所有信息直接输出到终端。
3 运行结果
Shell
1 | |
Plain Text
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 | |
4 测试环境
- Ubuntu 18.04.5 LTS (WSL2 5.4.72)
- QEMU emulator 5.0.50
- GCC 8.4.0 (Target: aarch64-linux-gnu)
- GDB 8.2 (Target: aarch64-linux-gnu)
- GNU Make 4.1
5 参考资料
- xv6: a simple, Unix-like teaching operating system - MIT
- mit-pdos / xv6-public: xv6 OS - GitHub
- mit-pdos / xv6-riscv: Xv6 for RISC-V - GitHub
- Master boot record - Wikipedia