OS Mini Lab

回顾 mini lab 流程

在 .bashrc 中设置 TOKEN 环境变量

git pull origin M1 后，在 pstree 的 Makefile 中添加学号和姓名环境变量

在 ~/os-workbench-2022 中进行 git add . 和 git commit

实际上在 ~/os-workbench-2022/pstree 中进行 make 就会有 git 记录了

在 ~/os-workbench-2022/pstree 中进行 make submit

M1: 打印进程树 (pstree)

一些手册

man pstree
man 5 proc

一种思路

strace pstree

解析命令行参数

使用 getopt

注意

pstree -V

会写入到 stderr

但是返回值是 EXIT_SUCCESS

而无法识别的命令行参数，需要返回 EXIT_FAILURE

获取进程信息

先找一下映射关系

systemd(1)-+-ModemManager(672)-+-{ModemManager}(696)
           |                   `-{ModemManager}(699)
           |-NetworkManager(581)-+-{NetworkManager}(620)
           |                     `-{NetworkManager}(666)
           |-VBoxService(902)-+-{VBoxService}(903)
           |                  |-{VBoxService}(904)
           |                  |-{VBoxService}(905)
           |                  |-{VBoxService}(906)
           |                  |-{VBoxService}(907)
           |                  |-{VBoxService}(908)
           |                  |-{VBoxService}(909)
           |                  `-{VBoxService}(910)
           |-accounts-daemon(571)-+-{accounts-daemon}(577)
           |                      `-{accounts-daemon}(664)
           |-acpid(572)
           |-avahi-daemon(575)---avahi-daemon(642)

进程信息在下面的文件中

/proc/[pid]/stat

stat 文件部分格式

(1) pid  %d
(2) comm  %s
(3) state  %c
(4) ppid  %d
(5) pgrp  %d
(6) session  %d

示例

1 (systemd) S 0 1 1
575 (avahi-daemon) S 1 575 575
642 (avahi-daemon) S 575 575 575

获取进程的线程信息

/proc/[pid]/task/[tid]/stat
/proc/[tid]/stat

示例

696 (gmain) S 1 672 672

于是只要维护如下的结构体信息

typedef struct {
  char name[MAX_LENGTH];
  int pid;
  // -1 -> thread, otherwise, the pid of parent
  int ppid;
  // -1 -> not thread, otherwise, the pid of creator
  int ptid;
} Process;

对于进程而言，ptid 为 -1，其余的语义和手册中一致

对于线程而言，为了区分，假定 ppid 为 -1，实际上应该是 creator 的 ppid，而 ptid 为 creator 的 pid

有些线程的名字在 stat 中是不同于进程的，但是 pstree 打印的线程名与进程名相同

使用了手册中提及的 getdents 遍历目录信息

getdents 不会遍历到线程所在的目录，从而简化了逻辑

这里理解错了，/proc 下不含线程所在的目录

在匹配信息时使用了 regex，因为有些进程名中会有空格

打印

根据命令行参数和之前获得的信息递归打印即可

注意到除了 systemd，其他进程的 ppid 也可能为 0

目前只对相同的线程实现了 compaction

相同进程的 compaction，可能出现下面的情形

├─bash─┬─2*[gdb───{gdb}]

若需要显示 pid，则相当于关闭了 compaction

├─bash(5219)─┬─gdb(8452)───{gdb}(8454)
             ├─gdb(8646)───{gdb}(8648)

缩进的条件大概是，进程名相同，且线程数目相同

目前尚未实现

另外 kthreadd 作为所有内核线程的祖先，ppid 也为 0

提交

不能使用如下的头文件

#include <sys/stat.h>
#include <sys/syscall.h>

也就是说不能使用 getdents 遍历目录信息

应该使用 readdir 系列函数，使用起来也更方便

另外注意字符串应该清零的问题

除非 snprintf 或 strncpy 中参数 count 等于数组的长度

否则都应该使用 memset 先清零

M2: 协程库 (libco)

编译选项

首先编译 co.c 和 co.h，生成共享库 libco-32.so 和 libco-64.so

$(NAME)-64.so: $(DEPS) # 64bit shared library
  gcc -fPIC -shared -m64 $(CFLAGS) $(SRCS) -o $@ $(LDFLAGS)

注意 libco 的 Makefile 里指明了 all

all: $(NAME)-64.so $(NAME)-32.so

所以在 libco 下 make 只会生成 .so 文件

另外 libco 的 Makefile 里还添加了一些 CFLAGS

CFLAGS += -U_FORTIFY_SOURCE -DLOCAL_MACHINE

-U_FORTIFY_SOURCE 用来防止 __longjmp_chk 代码检查到堆栈切换，当成是 stack smashing，然后报错

参考如下

from man 7 feature_test_macros

https://stackoverflow.com/questions/13517526/difference-between-gcc-d-fortify-source-1-and-d-fortify-source-2

from man gcc

NOTE: In Ubuntu 8.10 and later versions, -D_FORTIFY_SOURCE=2 is set by default, and is activated when -O is set to 2 or higher. This enables additional compile-time and run-time checks for several libc functions. To disable, specify either -U_FORTIFY_SOURCE or -D_FORTIFY_SOURCE=0.

-DLOCAL_MACHINE 相当于 #define LOCAL_MACHINE

然后框架代码提供了一组协程库的测试用例，位于 libco/test 的 main.c 中

需要通过如下方式编译

libco-test-64: main.c
  gcc -I.. -L.. -m64 main.c -o libco-test-64 -lco-64

-I 选项代表 include path，使我们可以 #include <co.h>
-L 选项代表增加 link search path
-l 选项代表链接某个库，链接时会自动加上 lib 的前缀，即 -lco-64 会依次在库函数的搜索路径中查找 libco-64.so 和 libco-64.a，直到找到为止

生成可执行文件 libco-test-64 后，还需要设置环境变量 LD_LIBRARY_PATH=..

export LD_LIBRARY_PATH=..

用于指定查找共享库时除了默认路径之外的其他路径

注意这是在 libco/test 中进行的

也可以直接在 libco/test 中 make test

实验指南

http://jyywiki.cn/OS/2022/labs/M2 写的非常详细

注意如下约定，使用协程库的程序应当保证除了初始协程外，其他协程都必须被 co_wait 恰好一次，否则会造成内存泄漏

一些细节

为初始协程分配数据结构

需要使用 __attribute__((constructor))

另外使用 __attribute__((destructor)) 进行资源回收

似乎无法通过 Valgrind 或 Address Sanitizer 进行检测

上下文切换

核心方法是 stack_switch_call

static inline void stack_switch_call(void *sp, void *entry, uintptr_t arg,
                                     void *ret_entry) {
  asm volatile(
#if __x86_64__
      "movq %0, %%rsp; movq %2, %%rdi; movq %3, (%0); jmp *%1"
      :
      : "b"((uintptr_t)sp - 8), "d"(entry), "a"(arg), "c"(ret_entry)
      : "memory"
#else
      "movl %0, %%esp; movl %2, 4(%0); movl %3, (%0); jmp *%1"
      :
      : "b"((uintptr_t)sp - 8), "d"(entry), "a"(arg), "c"(ret_entry)
      : "memory"
#endif
  );
}

这里寄存器的选择挺随意的……

相当于为每个协程的入口处构造相应的栈帧

对于 __x86_64__ 而言，应在寄存器 rsp 的地址处放置返回地址

注意栈的含义，在执行 entry 的第一条指令前和执行 entry 的最后一条指令前，寄存器 rsp 的值是相同的

对于 __x86__ 而言，应在寄存器 rsp 的地址处放置返回地址，并在 rsp + 4 处放置第一个参数

堆栈的增长方向

调用 longjmp 出现 segmentation fault

注意堆栈是向低地址增长的，所以赋给 stack_switch_call 应该是堆栈的高地址

否则 context 中的内容会被覆写

yield

在 co_wait 和 ret_entry 中均使用了 co_yield 进行上下文切换

而 co_yield 通过随机调度到非 DEAD 协程，保证了相关的语义

请仔细体会某些函数是永不返回的

x86-64 堆栈对齐

https://stackoverflow.com/questions/49391001/why-does-the-x86-64-amd64-system-v-abi-mandate-a-16-byte-stack-alignment

很怪

#if __x86_64__
      "movq %0, %%rsp; movq %2, %%rdi; movq %3, (%0); jmp *%1"
      :
      : "b"((uintptr_t)sp - 8), "d"(entry), "a"(arg), "c"(ret_entry)
      : "memory"

这样的话在应用程序中可以使用 printf，但是 co.c 中不能使用 printf

如果改为

#if __x86_64__
      "movq %0, %%rsp; movq %2, %%rdi; movq %3, (%0); jmp *%1"
      :
      : "b"((uintptr_t)sp - 16), "d"(entry), "a"(arg), "c"(ret_entry)
      : "memory"

这样的话在应用程序中不可以使用 printf，co.c 中似乎也不能使用 printf

Ref.

http://rk700.github.io/2020/01/19/inline-assembly-constraints/

How to Use Inline Assembly Language in C Code

https://www.ibiblio.org/gferg/ldp/GCC-Inline-Assembly-HOWTO.html

另外在 gdb 中更美观的打印结构体

set print pretty on

M3: 系统调用 Profiler (sperf)

strace 参数

观察到 strace 的一些参数

strace -c
strace -T

不过 -c 下的粒度不大

考察的是解析 -T 下的输出

环境变量

父进程的环境变量，是 main 函数的 envp

子进程 execve 后的环境变量，是 execve 时传入的 envp

另外需要在子进程 execve 前找到 strace 的正确路径，因为 execve 是不考虑环境变量的

注意 strtok 是破坏性的，不能直接对 envp 的 PATH 进行 strtok

execve 中 sub_argv 的格式如下

strace -T COMMAND [ARG]

注意 COMMAND [ARG] 相对于 argv 有一格偏移

进程间通信

父进程创建一个管道，父进程读取，子进程写入

strace 输出到标准错误流，所以需要将子进程的标准错误流重定向到写端

考虑到 strace 里面的程序会有输出，需要将将子进程的标准输出流重定向到 /dev/null

如果 strace 里面的程序输出到标准错误流，可能会影响解析

另外，重定向放在 execute 函数里面，似乎不起作用

为了方便起见，将父进程的标准输入流重定向到读端

使用 lsof 命令查看进程打开的文件描述符

正则表达式

可以参考 https://ahuigo.github.io/b/code/code-regex#/

读取时似乎正好是一行，所以使用 ^ 和 $ 来定位

之前一直忘了使用 regfree 释放内存……

$ valgrind --leak-check=full --show-leak-kinds=all --error-exitcode=1 ./sperf-64 ls

计时器

父进程不使用 wait(NULL)

每隔一秒排序并输出

调试选项

调试多进程

尝试下面一些选项

set follow-fork-mode child
set detach-on-fork off
catch exec

catch exec 用于捕获 execve

测试

$ ./sperf-32 python3 -c "2 ** 1000000000"
$ ./sperf-32 demo/demo
$ ./sperf-32 tree /
$ ./sperf-32 ./sperf-64 ./sperf-32 ./sperf-64 ./sperf-32 ls

TODO

注意到找不到 COMMAND 对应的程序时会出现

sperf$ ./sperf-32 l
======== Statistic ========
 (-2147483648%)
 (-2147483648%)
 (-2147483648%)
 (-2147483648%)
 (-2147483648%)

执行 COMMAND 发生在 strace 内部

考虑在 execve 前确认 COMMAND 的路径是否存在

如果 COMMAND 是以 / 开头的绝对路径，则直接执行

否则在 PATH 环境变量中搜索到第一个存在且可执行的文件

绘图

ANSI Escape Code

M4: C Real-Eval-Print-Loop (crepl)

思路

若为函数，则将其内容保存到 /tmp/crepl/template-XXXXXX.c 中，使用 gcc -c 编译观察是否有语法错误，若没有错误，则编译到共享库 /tmp/crepl/libcrepl.so 中
若为表达式，在上述步骤的基础上，动态链接到共享库，并调用对应的 wrapper name

共享库的创建

对于使用共享库的程序而言，可以是多个共享库

$ gcc -shared -fpic -o ./libcrepl-1.so template-cRg6lg.c
$ gcc -shared -fpic -o ./libcrepl-2.so ./libcrepl-1.so template-yVGkFl.c
$ gcc a.c ./libcrepl-1.so ./libcrepl-2.so

也可以是一个共享库

$ gcc -shared -fpic -o ./libcrepl.so template-*.c
$ gcc a.c ./libcrepl.so

但显然一个共享库会方便很多

wrapper

每当我们收到一个表达式，例如 gcd(256, 144) 的时候，我们都可以人工生成一段 C 代码

int __expr_wrapper_4() {
  return gcd(256, 144);
}

请记住这个反复使用的小技巧

一些细节

编译选项 -Wno-implicit-function-declaration

从而让函数和表达式均可以调用之前定义过的函数，而不会报错影响合法性判断

后来发现这种行为是掩耳盗铃，实际上需要在每个函数之前显式的添加声明

只不过这样就不能创建互相递归调用的函数了

注意共享库的创建的可移植性 -m64/-m32

创建子进程的核心函数 fork_exec_test

使用 pipe 连接父子进程，关闭子进程的 stdout，重定向子进程的 stderr

父进程根据输出来判断子进程中是否发生了错误

使用函数指针增加灵活性

对于共享库的链接，直接照抄 CSAPP

void exec_expr(const char *wrapper_name) {
  int (*wrapper)(void);
  void *handle;
  char *error;

  handle = dlopen(sopath, RTLD_LAZY);
  if (!handle) {
    fprintf(stderr, "%s\n", dlerror());
    handle_error("dlopen");
  }

  wrapper = dlsym(handle, wrapper_name);
  if ((error = dlerror()) != NULL) {
    fprintf(stderr, "%s\n", error);
    handle_error("dlsym");
  }

  printf("%d\n", wrapper());

  if (dlclose(handle) < 0) {
    fprintf(stderr, "%s\n", dlerror());
    handle_error("dlclose");
  }
}

TODO

函数重名

M5: File Recovery (frecov)

sha1sum ref

$ sha1sum *.bmp
d60e7d3d2b47d19418af5b0ba52406b86ec6ef83  0M15CwG1yP32UPCp.bmp
1ab8c4f2e61903ae2a00d0820ea0111fac04d9d3  1yh0sw8n6.bmp
1681e23d7b8bb0b36c399c065514bc04badfde79  2Kbg82NaSqPga.bmp
aabd1ef8a2371dd64fb64fc7f10a0a31047d1023  2pxHTrpI.bmp
3f4cfd6c2b7b788062283db37a8f06a4a4a210e4  335qZ0PhcpRTxMb.bmp
77b6d70b6e52d6613b7c95e059cbfc429b3de7e0  35OZL3hvJnEf.bmp
03ec749d01bae86200189b546839fab1630766b7  3DhTVVP9avTrH.bmp
d46c5781477c8b7e18e71507f2713fc5a11e4af6  4QDw0lcDAIhO.bmp
bf06738214223ce3fb4651edeedc7488d28fc58d  5VelGxd7.bmp
a4e48d5bd7be56f441f1cd77cff473f4709fb37c  5wISaRF1C3r4JgP.bmp
e02a7e2628fe0edfb0fc87f6725fb5b0935aa237  5YpvCYAOItJaxUBL.bmp
94ff9fd78a105eda524e0ecc3e3c7e79088ba902  6lHVixCC6.bmp
e55615c8bb6a5ba187771f6462e8c9a65939a8bc  7biIM7Q8P9bq.bmp
e1dd4448134c8fbf66626dbd714c9e19ec90fefa  8G5szK2BVe.bmp
a776e14ab2ad3a65f166683c02735050a9e00f27  8uGiCZmSVfvwh0SZ.bmp
dfc6272ba28ffd86bb288813afe67200e3da9ebb  8WkOrZWB2ukhnnd5M.bmp
2f2abc7151e7ef34d07395ff9fafbe78cbb8596c  9my4xesCy2E9jAN.bmp
3c324066045f9b1cc6b0950d4652b205587b7e64  aAIzYjw4CD.bmp
3424b6253defdca5ab2c816cfb1f2bbdb3ca76ec  aCYph3JKNaQ5.bmp
49af0c1aad982744d2ebb2e67eaeaf8332ff8732  aMm0Fgjgwdde.bmp
9d7ef1ad6532e9b4ae86ef329948d0beb6491fae  ASGbmfyufH4dN0.bmp
b33ec9a67b7304dc9b3eda8bd31726b83a851a54  aUqJhfhLguLzI56.bmp
d362e8966a9f4e6b2f057d1e2c3c454153f2df47  B8siuWRm7u7gQDr.bmp
2efb8417d20275b3e7ddf3f229086958e7dd91ed  BE4gsl2y.bmp
d4806efff96df9dc1ae3c25c79838b5c9ea90ab0  bhxRNph5PX.bmp
a64be9c9e3e28542903518d192e8f97d4d8a777b  BOHQPYEfWAzaSy.bmp
8070af25a450771da1eae9d2126396ed6778778a  bPtMCWiwCuGKe8.bmp
fb1de8d4cfa9a823868a622034279d2efb8b1d23  BSMby3blPP2g.bmp
a9d9d319d3ca10870e31d1595f00d5c27dee7f1b  C0NrniO8Tu5T.bmp
29a3da15fd10cb619a3fdf12520f5c9ec7075619  C6bsubODgR3P.bmp
5879e4ddd92f347577bdbcc49adf5adc5c186d24  CfWT9haBXoTJ.bmp
3d9e4babbe86de760528da349c51062d1c63c30a  ChUOLUWrtaNmMeIdG.bmp
5afaa51e0f0aef45d9a2482108e4f418cf9337fb  CJuVzZpj9AXIQE.bmp
86f758470f2be0164ff71a024dae4db95f7956ed  cLFhqxWoVDu7d4AF.bmp
f9b346a8df95d82e576a30228bb2aba2396c3f71  cwPgyDeTuhhf.bmp
cf3542551edba0a29d8fafd1aa5d0002910b029e  Dnf6EC9Wn.bmp
1538b092d4961cea7ef6c190bfb432847ac47310  dwuwDLbM.bmp
cf60d5c1965db724854b9fdd4deadfc6d25870a3  e8XGTmRSoGBp.bmp
8940595fb105e5825e8a43add015ff26cb2957db  eDMwaMHsNO2TVn.bmp
a40e45f3f1a25a55abc916f7fc7f8a85d73f830b  EhDqKXHi3AUn.bmp
6e4afd6d293d0b8e969442fe5f5583febb3fb1f9  emvzYdDWfu9i28IGJ.bmp
5e84aa3e615f95024d2a55f543cdceab63a30c44  FaccLox6fC9h.bmp
80270bb73ad0331cc2889604350c9f9a192de079  GolAJQfSet.bmp
84c34532c462f5ca7222f2d738105b2c426760eb  GVTL53R3j6ha.bmp
cabf852574ecca866278329de8a1d1a82189165c  Hj9Afs61.bmp
38fe0c7bfe9ed7c931843dcf0ea2b29688297a75  IEyXmSDCCO4Q.bmp
cafd0cde89647fe4c2457f3f0a4cba865c215a35  izV3ngDlqtNQvI359.bmp
9b694c640b71edb91e9f1322c03617c2bfdcc511  j1KVXozUClC.bmp
6eec4f7f578056e8148015e8dcb5270672c47210  jGptw2hnT.bmp
04bbc0049f28caa430b26192073c348b1a99a076  jJQ0E9ujM6.bmp
2cea6f5ea98b2d487e3cc32a3308597dfe7da7c8  jxtrT1VRRrr.bmp
c5170b33cc819ffc19bc0e7fc9ef9e7bbc00a514  K3P0frhdzAz.bmp
1f23b0c13aea51b8a3c388e67e06e5410e504ecf  k43VQUbabT0tC54Y.bmp
25f90ec06c1e2cedc87a9c838c24c34f4ba31fa8  KRFgoEA52w.bmp
4d6b2b2bcbc10e04ad64350a61abe77effb79a42  Le4I4eLH.bmp
3a768b40bf66cf8afd20ac93b903973b21e031d0  lgmdA1fW9NZu4T.bmp
53962ea913ee0da56141aa2d2752cbd3d3973771  Lh3gk68UqXC.bmp
d3ae99abb401b06cac5fc3f149f0c373cd0af053  ljaGhx0jOu5r7ge.bmp
50097799b816c48f1a7c1a88cd285025b85172c0  lulFqviqr.bmp
5108c6653024f398d564f30dc674cb286f29d0da  mwaYW7RAfDfDPKY0.bmp
befc711f13af3adacd38a76579b500a3580d79ed  NkeMerFkx02.bmp
5274d124d86be0cb83f9a2bc6f19fe7d1dc0aef6  NUiFpilAZL1w.bmp
d93a6970969741e581dee787b0b0d27bd68cd97e  O6GneCnOfJ7.bmp
894de00f8f24df0be6fc28a153b06db7ad35d7d1  OqpvBJ3LdOJ7.bmp
f7709bf0e29f85d5eadd34bf2e4d342cad067637  P4LECOKK.bmp
663699b660831db55071c0b0ff320ca35bda23a3  p6FaDZ3Z8GxJaV2L.bmp
9b6931a8126156ccaf40e263b4ba423a4ad4193e  pEmFLlmuB.bmp
7c75729e797338a5b1baf2cb0c41eaa65605e74d  PNTuejwC2.bmp
8b5cc9b357e3e3b556063f80d2192ad7c1417f71  ptWAWyKPZrvz.bmp
2663c82d2de3c6a40dd544817d11f4922470389e  PxyLldumMJ7x9bhVp.bmp
625b7508940cb3234363fa9308b2bc7ca0a78518  q43vVNgf6SLsZ9lB0.bmp
0c08b4b1ef563d9e35fbc3b5bc6a813eb630078a  qD9yubK8hHkYUURK.bmp
a1a958308141554f7dc0aafc32f79a83549c28c7  QEh5F9z7e.bmp
2ea146afa7f84d696a3d29f48423658164544833  REPlnIEiLXRund.bmp
3ad258494666771200c62bc8a60588ae32cfe854  rgwfuyGZAfPrLw6n.bmp
f7c74bcb0e0701bf3cc4d15328f8e3c10709cefb  rnS6rbKwG6R2h4krD.bmp
7cd8bf73ec91b56745ec5c12b8ca8cec05fdfbbc  rVVtFPtJ.bmp
537c8d34341af415313d67efe8fa591dc7910ae4  S0A5Dyr2uLL.bmp
9ae2b885673a9ec2cd4f0cb19ea3ff6fe0ed77fa  TAYFI98zRuFHE2.bmp
2f573bdbc9609f5845a63a64b28b00443475a680  tEzVaAJO1.bmp
b4d86bde39a8704b8db8f17003b45f0789a155d4  Tn23kpRhjIUK1Tr.bmp
895482516ee54fee57f03d38c41dacafb8422471  u6wlQF01C451.bmp
f9d8cebbabbe0fcdb99061a5c5466ad0b326acc2  u7TOeSELhp.bmp
68278b919a2cc1d1253e3ec354794b5d21425203  uf9jm62NlUHYMknj.bmp
2cf9ec47bb6e7f4f78cffb33247f048837c5e300  UJVORXkzJG.bmp
548466f58810eae6fce81a283cadcdbbed8ea6b1  uqPcdWI64PpuXGYsM.bmp
b1c3493f6ad60f5e6942539b0559205b903af4c4  Utq6k0l5A4nuN0q.bmp
97e9f140bc7aff5525f1ac5ce0bb7c75c9958021  Vc5voqD38uOuc.bmp
5f210448e64abdd5d87b01fb3e848a658b209459  vdLqNhwlgd5.bmp
f1def12736c2e294582af8885f41384623c818f3  vXyZkWFGf486oGM.bmp
ae8e33136c7fef924131ef16f83d6d10beaeae9f  wCxJzyUXtXjCWnpU.bmp
98dee77fccdda83f577f255122303758565af1e2  WDESkd1ohYoeScb0.bmp
be8989c7385a43ea421e1d2ea98b47822772dec0  whCeEdLoscu89d5Km.bmp
c5e72335ba4cb2ac5d2b581a12de2d4ceb7a5af8  WkoT3Hhve6K4a5.bmp
3c37d7c2a9f56bdcb809b054bcb5d668fa67ce3b  YpudsKsAkEzDBoJ.bmp
e8954cefdd31314ad94d371ac9b6b8caa0a3ce17  zOU0Xf3NSQyiJESqD.bmp
3de7d1e949ae7f260119ac40a4560cab6885c525  zXcUJJDdm.bmp

mkfs.fat

$ mkfs.fat -v -F 32 -S 512 -s 8 fs.img
mkfs.fat 4.2 (2021-01-31)
WARNING: Number of clusters for 32 bit FAT is less then suggested minimum.
fs.img has 8 heads and 32 sectors per track,
hidden sectors 0x0000;
logical sector size is 512,
using 0xf8 media descriptor, with 131072 sectors;
drive number 0x80;
filesystem has 2 32-bit FATs and 8 sectors per cluster.
FAT size is 128 sectors, and provides 16348 clusters.
There are 32 reserved sectors.
Volume ID is ba4d744b, no volume label.

-F 32 表示 FAT-32
-S 512 表示 sector 大小是 512 bytes
-s 8 表示每个 cluster 有 8 个 sectors

FAT-32

http://jyywiki.cn/pages/OS/manuals/MSFAT-spec.pdf

BPB

记录了一些 metadata

主要关注如下字段

BPB_BytsPerSec

每个 sector 的字节数

BPB_SecPerClus

每个 cluster 包含的 sector

BPB_RsvdSecCnt

Reserved Region 也就是 volume #0 占据的 sector 数量

sector #0 存储了 BPB 信息

通常 sector #6 会对 BPB 进行备份

可以观察 BPB_BkBootSec 字段得知

BPB_NumFATs

FAT 的备份数量

BPB_FATSz32

每个 FAT 包含的 sector

BPB_TotSec32

整个镜像包含的 sector

FAT

FAT Region 中每个 entry 占据 32 字节，记录了 Data Region 对应 cluster 的 ID

通过 cluster ID，可以定位到 Data Region 一段 BPB_BytsPerSec * BPB_SecPerClus 字节长度的空间

这段空间中可能会存储三种数据结构

data

文件的数据信息

short entry - 32 字节

主要关注如下字段

DIR_Name - short name

DIR_Attr - 一些属性

通过

DIR_FstClusLO | DIR_FstClusHI << 16

可以得到对应数据信息的 cluster ID

long entry - 32 字节

记录了完整的文件名或目录名

TFM 指出 long entry 应倒序排列在对应 short entry 之前，如图所示

然而似乎存在不满足这个约定的 entry

其中的 checksum 对 short name 的进行了某些计算

另外，根目录 cluster ID 记录在 FAT 的 entry #2 中，对应 Data Region 的 cluster #0

将 cluster ID 转换到 sector 对应空间需要减去这个偏移

void *cluster_to_sec(int n) {
  // RTFM: Sec 3.5 and 4 (TRICKY)
  u32 data_sec = hdr->BPB_RsvdSecCnt + hdr->BPB_NumFATs * hdr->BPB_FATSz32;
  data_sec += (n - 2) * hdr->BPB_SecPerClus;
  return ((char *)hdr) + data_sec * hdr->BPB_BytsPerSec;
}

BMP

假设所有的 BMP 文件，都是使用 Python PIL 库创建的 24-bit 位图

$ file 0M15CwG1yP32UPCp.bmp
0M15CwG1yP32UPCp.bmp: PC bitmap, Windows 3.x format, 364 x 448 x 24

https://en.wikipedia.org/wiki/BMP_file_format#File_structure

https://zhuanlan.zhihu.com/p/25119530

关键在于计算 image size

可以参考 https://en.wikipedia.org/wiki/BMP_file_format#Pixel_storage

note

首先在没有格式化的情形下，尝试得到文件名和校验和
- 这个过程实际上就可以完成本实验的大部分的内容了
文件恢复 trivial 算法
- short name 以 BMP 结尾
- 数据连续存储
优化算法
- 行间求点积，难以设置阈值
- 考虑每行最后的 padding，猜测 0 出现的次数不能太多
进行文件恢复时，注意需要将一些 assertions 转换为条件分支，防止提前 crash
注意对于 long name 存储使用的是空终止宽字符串
- 也就是 wchar_t 数组
- 清空时需要使用 wmemset(long_filename, 0, sizeof(long_filename) / sizeof(wchar_t))

OS Mini Lab 攻略

TOC

OS Mini Lab

M1: 打印进程树 (pstree)

解析命令行参数

获取进程信息

打印

提交

M2: 协程库 (libco)

编译选项

实验指南

一些细节

Ref.

M3: 系统调用 Profiler (sperf)

strace 参数

环境变量

进程间通信

正则表达式

计时器

调试选项

测试

TODO

M4: C Real-Eval-Print-Loop (crepl)

思路

共享库的创建

wrapper

一些细节

TODO

M5: File Recovery (frecov)

sha1sum ref

mkfs.fat

FAT-32

BPB

FAT

BMP

note