OS Lab 攻略

Posted on:2022.06.20

TOC

Open TOC

OS Lab

docker

使用以下 Dockerfile 配置与在线评测一致的环境

我们开放了容器的 SYS_PTRACE 权限

FROM ubuntu:20.04
ENV DEBIAN_FRONTEND=noninteractive
RUN apt-get update
RUN apt-get install -y build-essential gcc-multilib qemu-system strace gdb sudo python3 libsdl2-dev libreadline-dev llvm-11 gcc-riscv64-linux-gnu
RUN useradd -ms /bin/bash user
USER user
WORKDIR /home/user

env

配置 vscode 调试环境

{
    // Use IntelliSense to learn about possible attributes.
    // Hover to view descriptions of existing attributes.
    // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387
    "version": "0.2.0",
    "configurations": [


        {
            "name": "debug",
            "type": "cppdbg",
            "request": "launch",
            "stopAtEntry": true,
            "program": "${workspaceFolder}/kernel/build/kernel-x86_64-qemu.elf",
            "cwd": "${workspaceFolder}",
            "miDebuggerServerAddress": "localhost:1234",
            "miDebuggerPath": "/usr/bin/gdb",
            "environment": [],
            "externalConsole": false,
            "MIMode": "gdb",
            "setupCommands": [
                {
                    "description": "pretty printing",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                }
            ],
            "logging": {
                // "engineLogging": true,
                // "programOutput": true
            }
        }
    ]
}

L0: 直接运行在硬件上的小游戏 (amgame)

git pull origin L0

注意此时在根目录已经得到了 abstract-machine

RTFM

http://jyywiki.cn/AbstractMachine/AM_Programs

http://jyywiki.cn/AbstractMachine/AM_klib

make

需要安装 qemu

sudo apt-get install qemu-system-x86

下面分析在 amgame 目录下执行 make 后发生了什么

# Building amgame-image [x86_64-qemu]
+ CC src/video.c
+ CC src/game.c
+ CC src/keyboard.c
# Building am-archive [x86_64-qemu]
+ AS src/x86/qemu/start64.S
+ AS src/x86/qemu/trap64.S
+ CC src/x86/qemu/trm.c
+ CC src/x86/qemu/cte.c
+ CC src/x86/qemu/ioe.c
+ CC src/x86/qemu/vme.c
+ CC src/x86/qemu/mpe.c
+ AR -> build/am-x86_64-qemu.a
# Building klib-archive [x86_64-qemu]
+ CC src/cpp.c
+ CC src/string.c
+ CC src/stdlib.c
+ CC src/stdio.c
+ CC src/int64.c
+ AR -> build/klib-x86_64-qemu.a
+ LD -> build/amgame-x86_64-qemu.elf
# Creating image [x86_64-qemu]
+ CC start.S main.c
+ CREATE -> build/amgame-x86_64-qemu

对 .c 文件

x86_64-linux-gnu-gcc -std=gnu11 -O2 -MMD -Wall -Werror -I/home/vgalaxy/os-workbench-2022/amgame/include -I/home/vgalaxy/os-workbench-2022/amgame/../abstract-machine/am/include/ -I/home/vgalaxy/os-workbench-2022/amgame/../abstract-machine/klib/include/ -D__ISA__=\"x86_64\" -D__ISA_X86_64__ -D__ARCH__=x86_64-qemu -D__ARCH_X86_64_QEMU -D__PLATFORM__=qemu -D__PLATFORM_QEMU -DARCH_H=\"arch/x86_64-qemu.h\" -fno-asynchronous-unwind-tables -fno-builtin -fno-stack-protector -Wno-main -U_FORTIFY_SOURCE -m64 -fPIC -mno-sse -c -o /home/vgalaxy/os-workbench-2022/amgame/build/x86_64-qemu/./src/video.o /home/vgalaxy/os-workbench-2022/amgame/src/video.c

对 .S 文件

x86_64-linux-gnu-gcc -MMD -I/home/vgalaxy/os-workbench-2022/amgame/../abstract-machine/am/src -I/home/vgalaxy/os-workbench-2022/abstract-machine/am/include -I/home/vgalaxy/os-workbench-2022/amgame/../abstract-machine/am/include/ -I/home/vgalaxy/os-workbench-2022/amgame/../abstract-machine/klib/include/ -m64 -fPIC -c -o /home/vgalaxy/os-workbench-2022/abstract-machine/am/build/x86_64-qemu/src/x86/qemu/start64.o /home/vgalaxy/os-workbench-2022/abstract-machine/am/src/x86/qemu/start64.S

归档

ar rcs /home/vgalaxy/os-workbench-2022/abstract-machine/am/build/am-x86_64-qemu.a /home/vgalaxy/os-workbench-2022/abstract-machine/am/build/x86_64-qemu/src/x86/qemu/start64.o /home/vgalaxy/os-workbench-2022/abstract-machine/am/build/x86_64-qemu/src/x86/qemu/trap64.o /home/vgalaxy/os-workbench-2022/abstract-machine/am/build/x86_64-qemu/src/x86/qemu/trm.o /home/vgalaxy/os-workbench-2022/abstract-machine/am/build/x86_64-qemu/src/x86/qemu/cte.o /home/vgalaxy/os-workbench-2022/abstract-machine/am/build/x86_64-qemu/src/x86/qemu/ioe.o /home/vgalaxy/os-workbench-2022/abstract-machine/am/build/x86_64-qemu/src/x86/qemu/vme.o /home/vgalaxy/os-workbench-2022/abstract-machine/am/build/x86_64-qemu/src/x86/qemu/mpe.o

注意这里是 32 位的，所以需要使用 x86_64-linux-gnu-ld

x86_64-linux-gnu-ld -melf_x86_64 -N -Ttext-segment=0x00100000 -o /home/vgalaxy/os-workbench-2022/amgame/build/amgame-x86_64-qemu.elf --start-group /home/vgalaxy/os-workbench-2022/amgame/build/x86_64-qemu/./src/video.o /home/vgalaxy/os-workbench-2022/amgame/build/x86_64-qemu/./src/game.o /home/vgalaxy/os-workbench-2022/amgame/build/x86_64-qemu/./src/keyboard.o /home/vgalaxy/os-workbench-2022/amgame/../abstract-machine/am/build/am-x86_64-qemu.a /home/vgalaxy/os-workbench-2022/amgame/../abstract-machine/klib/build/klib-x86_64-qemu.a --end-group

链接选项对应了 manual 中的

  1. -melf_x86_64：指定链接为 x86_64 ELF 格式；
  2. -N：标记 .text 和 .data 都可写，这样它们可以一起加载，而不需要对齐到页面边界，减少可执行文件的大小；
  3. -Ttext-segment=0x00100000：指定二进制文件应加载到地址 0x00100000。
x86_64-linux-gnu-gcc -static -m32 -fno-pic -Os -nostdlib -Ttext 0x7c00 -I/home/vgalaxy/os-workbench-2022/amgame/../abstract-machine/am/src -o bootblock.o start.S main.c
( cat /home/vgalaxy/os-workbench-2022/amgame/../abstract-machine/am/src/x86/qemu/boot/bootblock.o; head -c 1024 /dev/zero; cat /home/vgalaxy/os-workbench-2022/amgame/build/amgame-x86_64-qemu.elf ) > /home/vgalaxy/os-workbench-2022/amgame/build/amgame-x86_64-qemu

再分析通过 make run 运行小游戏

( echo -n ; ) | dd if=/dev/stdin of=/home/vgalaxy/os-workbench-2022/amgame/build/amgame-x86_64-qemu bs=512 count=2 seek=1 conv=notrunc status=none
qemu-system-x86_64 -serial mon:stdio -machine accel=tcg -smp "" -drive format=raw,file=/home/vgalaxy/os-workbench-2022/amgame/build/amgame-x86_64-qemu

可以使用 mainargs 指定参数

不太理解为什么要使用 dd

是为了传递 mainargs

可以模仿 manual 直接使用下列指令

qemu-system-x86_64 -S -s -serial none -nographic -machine accel=tcg -smp "" -drive format=raw,file=/home/vgalaxy/os-workbench-2022/amgame/build/amgame-x86_64-qemu
WARNING:
Image format was not specified for 'build/amgame-x86_64-qemu' and probing guessed raw.
Automatically detecting the format is dangerous for raw images, write operations on block 0 will be restricted.
Specify the 'raw' format explicitly to remove the restrictions.

然后就可以按照 manual 使用 gdb 进行远程调试了

snake

写了一个简单的贪吃蛇

对 IO 设备的访问类似 PA

typedef void (*handler_t)(void *buf);
static void *lut[128] = {
  [AM_UART_CONFIG ] = uart_config,
  [AM_UART_TX     ] = uart_tx,
  [AM_UART_RX     ] = uart_rx,
  [AM_TIMER_CONFIG] = timer_config,
  [AM_TIMER_RTC   ] = timer_rtc,
  [AM_TIMER_UPTIME] = timer_uptime,
  [AM_INPUT_CONFIG] = input_config,
  [AM_INPUT_KEYBRD] = input_keybrd,
  [AM_GPU_CONFIG  ] = gpu_config,
  [AM_GPU_FBDRAW  ] = gpu_fbdraw,
  [AM_GPU_STATUS  ] = gpu_status,
  [AM_GPU_MEMCPY  ] = gpu_memcpy,
  [AM_GPU_RENDER  ] = gpu_render,
  [AM_AUDIO_CONFIG] = audio_config,
  [AM_DISK_CONFIG ] = disk_config,
  [AM_DISK_STATUS ] = disk_status,
  [AM_DISK_BLKIO  ] = disk_blkio,
  [AM_NET_CONFIG  ] = net_config,
};

可以使用 ioe_read，也可以使用 io_read

#define io_read(reg) \
  ({ reg##_T __io_param; \
    ioe_read(reg, &__io_param); \
    __io_param; })


#define io_write(reg, ...) \
  ({ reg##_T __io_param = (reg##_T) { __VA_ARGS__ }; \
    ioe_write(reg, &__io_param); })

主要使用的抽象寄存器有

除了 AM_GPU_FBDRAW，主要使用的抽象寄存器均为 RD

注意 x86-qemu 会在 ioe_init() 中初始化这些寄存器

bool ioe_init() {
  panic_on(cpu_current() != 0, "init IOE in non-bootstrap CPU");


  for (int i = 0; i < LENGTH(lut); i++)
    if (!lut[i]) lut[i] = fail;


  uart_init();
  timer_init();
  gpu_init();


  return true;
}

其中 uart 对应了输出串口 0x3f8

void putch(char ch) {
  #define COM1 0x3f8
  outb(COM1, ch);
}

timer 启用了 rtc 功能，终于可以获取当前时间了

而 x86-nemu 只有 cte 和 vme，似乎并不会被使用

在 amgame 的 Makefile 中有

ifeq ($(ARCH),)
export ARCH := x86_64-qemu

所以不指定 ARCH，默认为 x86_64-qemu，屏幕大小为 640 × 480

可以指定为 native，屏幕大小为 400 × 300

make run mainargs=xxx ARCH=xxx

然后是 klib 库，目前照搬了 string.c 和 stdio.c

string.c 应该是没有问题的

stdio.c 后期还需要修改，目前能用

注意 native 会链接系统本地的 glibc，而非 klib

下面分析一下 snake 的实现

由于除非按 ESC 键，我们假设游戏程序不结束；而如果按 ESC 键后游戏不 halt()，将判定为错

所以游戏主循环如下

  while (1) {
    srand(io_read(AM_TIMER_RTC).second);
    start();
    logic();
  }

其中 logic 也是一个死循环，除非在 logic 中读取键盘时得到了 ESC，否则 logic 在游戏失败时仅仅简单的 break，即回到游戏主循环，开始新的一局

为此，需要在每局开始前设置随机种子，对于固定的屏幕大小，一共有 60 种可能的战局

然后在 start 中（重新）初始化游戏逻辑，这部分工作在 video.c 中完成

下面是对 snake 游戏的抽象

首先屏幕被分成许多方块，方块的大小固定，所以屏幕大小决定了方块的数量

这里定义了两个方向最多的方块的数量，便于定义数据结构

snake 由一个 Position 数组构成，下标 0 为 head 的位置，下标 tail 即为 tail 的位置

还有一个调色板数组 palette，决定了屏幕中的每一个方块的颜色

注意需要维护调色板和 snake 以及 target 之间的同步

初始情形下，snake 长为 3，原方向为 →，并随机生成 target

通过在 logic 中读取键盘按键，并给 update 函数传递一个新的方向，update 就可以真正的更新游戏逻辑

首先是方向的确定

根据方向得到 head 的新位置，并通过调色板判断是否与 target 相遇

另外，为了实现游戏的无边界化，使用了 overflow_fix 和 underflow_fix 函数调整临界情形

logic 调用 update 更新了调色板，若游戏未失败，则进行 redraw

void redraw() {
  for (int x = 0; x < w_side; x++) {
    for (int y = 0; y < h_side; y++) {
      draw_tile(x * SIDE, y * SIDE, SIDE, SIDE, palette[x][y]);
    }
  }
}

而 draw_tile 如下

static void draw_tile(int x, int y, int w, int h, uint32_t color) {
  uint32_t pixels[w * h]; // WARNING: large stack-allocated memory
  AM_GPU_FBDRAW_T event = {
      .x = x,
      .y = y,
      .w = w,
      .h = h,
      .sync = 1,
      .pixels = pixels,
  };
  for (int i = 0; i < w * h; i++) {
    pixels[i] = color;
  }
  ioe_write(AM_GPU_FBDRAW, &event);
}

另外，在 main.c 中还设计了 level 机制，可以通过 mainargs 指定 level

不过 level 似乎和 FPS 直接挂钩

L1: 物理内存管理 (pmm)

macro

MODULE(os) {
  void (*init)();
  void (*run)();
};


MODULE(pmm) {
  void  (*init)();
  void *(*alloc)(size_t size);
  void  (*free)(void *ptr);
};


MODULE_DEF(os) = {
  .init = os_init,
  .run  = os_run,
};


MODULE_DEF(pmm) = {
  .init  = pmm_init,
  .alloc = kalloc,
  .free  = kfree,
};

对应

typedef struct mod_os_t mod_os_t;
extern mod_os_t *os;
struct mod_os_t {
  void (*init)();
  void (*run)();
};


typedef struct mod_pmm_t mod_pmm_t;
extern mod_pmm_t *pmm;
struct mod_pmm_t {
  void (*init)();
  void *(*alloc)(size_t size);
  void (*free)(void *ptr);
};


extern mod_os_t __os_obj;
mod_os_t *os = &__os_obj;
mod_os_t __os_obj = {
  .init = os_init,
  .run = os_run,
};


extern mod_pmm_t __pmm_obj;
mod_pmm_t *pmm = &__pmm_obj;
mod_pmm_t __pmm_obj = {
  .init = pmm_init,
  .alloc = kalloc,
  .free = kfree,
};

AM

abstract-machine/am/include/am.h

// ---------------------- MPE: Multi-Processing ----------------------
bool     mpe_init    (void (*entry)());
int      cpu_count   (void);
int      cpu_current (void);
int      atomic_xchg (int *addr, int newval);

abstract-machine/am/src/x86/qemu/mpe.c

static void call_user_entry() {
  user_entry();
  panic("MPE entry should not return");
}


bool mpe_init(void (*entry)()) {
  user_entry = entry;
  boot_record()->jmp_code = 0x000bfde9; // (16-bit) jmp (0x7c00)
  for (int cpu = 1; cpu < __am_ncpu; cpu++) {
    boot_record()->is_ap = 1;
    __am_lapic_bootap(cpu, (void *)boot_record());
    while (xchg(&ap_ready, 0) != 1) {
      pause();
    }
  }
  call_user_entry();
  return true;
}


int cpu_count() {
  return __am_ncpu;
}


int cpu_current(void) {
  return __am_lapic[8] >> 24;
}


int atomic_xchg(int *addr, int newval) {
  return xchg(addr, newval);
}

abstract-machine/am/src/x86/x86.h

static inline int xchg(int *addr, int newval) {
  int result;
  asm volatile ("lock xchg %0, %1":
    "+m"(*addr), "=a"(result) : "1"(newval) : "cc", "memory");
  return result;
}

main

kernel/framework/main.c

#include <kernel.h>
#include <klib.h>


int main() {
  os->init();
  mpe_init(os->run);
  return 1;
}

run

默认运行参数为

qemu-system-x86_64 -serial mon:stdio -machine accel=tcg -smp "" -drive format=raw,file=/home/vgalaxy/os-workbench-2022/kernel/build/kernel-x86_64-qemu

只有一个 CPU，非常不爽

于是关注 -smp 参数

-smp [cpus=]n[,cores=cores][,threads=threads][,dies=dies][,sockets=sockets][,maxcpus=maxcpus]

虚拟 CPU 的个数，每个 thread 都视为一个虚拟 CPU

CPU 插槽数目，也就是 CPU 的个数

每个 CPU 核心拥有的线程数目

每个 CPU 拥有的 CPU 核心数目

于是有关系

n=sockets⋅threads⋅coresn = sockets \cdot threads \cdot cores

但是 Linux 似乎最多只支持 4 个虚拟 CPU

Linux limits the number of usable CPUs to 4.

而且线程数只能为 1，否则会警告

qemu-system-x86_64: warning: This family of AMD CPU doesn't support hyperthreading(2)

于是只能这样

qemu-system-x86_64 -serial mon:stdio -machine accel=tcg -smp 4,cores=1,threads=1,sockets=4 -drive format=raw,file=/home/vgalaxy/os-workbench-2022/kernel/build/kernel-x86_64-qemu

老老实实的单核心单线程

后来发现可以直接

make run smp=8

注意 abstract-machine/am/src/x86/x86.h 中定义了最大 CPU 数

#define MAX_CPU       8

note

原打算复用 malloc lab 中的隐式空闲链表

但是该实现是根据空闲链表中每一块的大小来分配内存，并不能保证返回的内存地址必须对齐到 2 的幂

于是考虑使用伙伴系统

参考：

堆区空间如下

Got 125 MiB heap: [0x300000, 0x8000000)

由于伙伴系统所能管理的内存必须为 2 的幂，所以考虑使用两个伙伴系统，其参数如下

管理 32MB，区间 [0x2000000, 0x4000000)

单位 32B，占用内存 1 * 1024 * 1024 * 2 * 4 = 8MB，区间 [0x300000, 0xa00000)

管理 64MB，区间 [0x4000000, 0x8000000)

单位 32B，占用内存 2 * 1024 * 1024 * 2 * 4 = 16MB，区间 [0xa00000, 0x1a00000)

所以最多可以使用的堆区只有 96MB

另外不考虑 klib 中的 malloc 和 free，直接根据 heap 进行操作

为了避免数据竞争，需要使用锁保护好共享数据

为此利用 AM 提供的硬件原语 atomic_xchg

int      atomic_xchg (int *addr, int newval);

置 *addr 为 newval，并返回 *addr 的旧值

根据 OSTEP，实现简单的自旋锁

typedef struct {
  int flag;
} lock_t;


static inline void init_lock(lock_t *lock) {
  atomic_xchg(&lock->flag, 0);
  // lock->flag = 0;
  // panic_on(lock->flag == 1, "Broken invariant.");
}


static inline void lock(lock_t *lock) {
  while (atomic_xchg(&lock->flag, 1) == 1)
    ;
  // panic_on(lock->flag == 0, "Broken invariant.");
}


static inline void unlock(lock_t *lock) {
  atomic_xchg(&lock->flag, 0);
  // lock->flag = 0;
  // panic_on(lock->flag == 1, "Broken invariant.");
}

由于无法保证原子性，不应使用防御性编程

unlock 时也需要使用 atomic_xchg

然后依据伙伴系统的三个 API

实现 kalloc 和 kfree 即可

主要细节就是内存之间的映射关系

关于 kalloc，先获取系统一的锁，若分配不出内存，则继续获取系统二的锁

实际上可以优化为先尝试获取系统一的锁，若获取不到，则继续获取系统二的锁

也就是 try_lock 语义

static inline void try_lock(lock_t *lock) {
  return !atomic_xchg(&lock->flag, 1);
}

返回 1 代表获取成功，反之获取失败

但是感觉会出现并发 bug，于是未采用

最难的一个部分是设计测试用例

因为 printf 的实现中使用了共享变量，所以需要使用 print_lck 加锁

但是似乎很难追踪每个 CPU 分配出的内存，导致在多 CPU 时会出现未及时释放内存的情形

另外，单 CPU 在 test_alloc 和 test_free 前后，buddy 的 longest[0] 似乎不一致

buddy_a - 1048576 unit(s)
buddy_b - 2097152 unit(s)
...
buddy_a - 524288 unit(s)
buddy_b - 1048576 unit(s)

但是根据 trace 信息内存已经都释放了，就很怪

于是修改了 kalloc，完全随机的选择伙伴系统

还考虑使用防御性编程检测 double-allocation 和 double-free

这就需要在 kfree 时了解分配出的内存大小，就需要使用伙伴系统的另一个 API - buddy2_size

注意在 buddy2_free 之前调用 buddy2_size

然后发现 buddy2_free 已经实现了 buddy2_size 的语义

直接让 buddy2_free 返回分配出的内存大小

后来发现了更奇怪的 double-free 现象，疑似伙伴系统内部数据被修改了

于是考虑对齐伙伴系统的内存

这样单 CPU 似乎就没有问题了……

submit

硬编码可还行……

所以要根据堆区的空间动态调整伙伴系统的参数

伙伴系统始终放在堆区开头

由于分配的最大内存为 16MB，所以实际的堆区开头要 16MB 对齐

同时考虑到两个伙伴系统的内存利用率可能不如一个伙伴系统，引入了 single mode

由于 OJ 总是返回 too slow，于是重新引入了 try_lock，同时注释掉一些调试代码

最后战况如下，感觉到极限了

==后续==

jyy 弱化了最后一个测试用例，所以只剩下 frequent small alloc 没有通过

local test

.
├── framework  -> 框架代码；可以在本地修改，但 Online Judge 评测时会被替换成我们的版本
│   ├── kernel.h
│   └── main.c
├── include    -> 头文件；可以自由修改/创建文件 (Online Judge 会复制)
│   └── common.h
├── Makefile
└── src        -> 源文件；可以自由修改/创建文件 (Online Judge 会复制)
    ├── os.c
    └── pmm.c

jyywiki 更新了如何构建本地测试框架

主要思想是不要让 pmm 链接到 AM APIs

不论是 native 还是运行在模拟器里，AM APIs 都和系统有紧密的耦合

使用 os ex 中提供的 thread 库进行测试

为此，在 kernel 中创建文件夹 test

.
├── am.h
├── common.h
├── test.c
└── thread.h

common.h 伪装成 kernel/include 下的 common.h

其中包含了 kernel.h

而 kernel.h 中包含了 am.h

其中包含了 native 环境下对 AM APIs 和 klib 中库函数的实现

这样在编译选项中只要指定头文件搜索路径为 framework 和 test 即可

test: git
  @gcc $(shell find src/ -name "pmm.c")  \
       $(shell find test/ -name "*.c") \
       -g -Wall -Werror \
       -Iframework -Itest\
       -DTEST -lpthread \
       -o build/test
  @build/test

千万不要加上 -Iinclude

另外，将 kernel/include/common.h 中的一些定义转移到 pmm.c 中

并且在 pmm.c 中对 AM APIs 依赖的地方增加一些条件编译

最后在 test.c 中使用 thread 库模拟多 CPU 动态分配内存的场景

就可以使用 make test 进行本地测试了

使用 gettid 获取当前线程号，从而近似实现 cpu_current

另外发现 pmm.c 中判定 Double allocation 和 Double free 的地方没有锁保护，所以并不可靠

其实构建本地测试框架的过程，就是理解 abstract-machine 如何提供抽象计算机模块化的过程

todo

L2: 内核线程管理 (kmt)

大的来了……

AM

CTE

bool cte_init(Context *(*handler)(Event, Context *)) {
  panic_on(cpu_current() != 0, "init CTE in non-bootstrap CPU");
  panic_on(!handler, "no interrupt handler");


  for (int i = 0; i < NR_IRQ; i ++) {
    idt[i]  = GATE(STS_TG, KSEL(SEG_KCODE), __am_irqall,  DPL_KERN);
  }
#define IDT_ENTRY(id, dpl, err) \
    idt[id] = GATE(STS_TG, KSEL(SEG_KCODE), __am_irq##id, DPL_##dpl);
  IRQS(IDT_ENTRY)


  user_handler = handler;
  return true;
}


void yield() {
  interrupt(0x81);
}


bool ienabled() {
  return (get_efl() & FL_IF) != 0;
}


void iset(bool enable) {
  if (enable) sti();
  else cli();
}


Context* kcontext(Area kstack, void (*entry)(void *), void *arg) {
  Context *ctx = kstack.end - sizeof(Context);
  *ctx = (Context) { 0 };


#if __x86_64__
  ctx->cs     = KSEL(SEG_KCODE);
  ctx->rip    = (uintptr_t)__am_kcontext_start;
  ctx->rflags = FL_IF;
  ctx->rsp    = (uintptr_t)kstack.end;
#else
  ctx->ds     = KSEL(SEG_KDATA);
  ctx->cs     = KSEL(SEG_KCODE);
  ctx->eip    = (uintptr_t)__am_kcontext_start;
  ctx->eflags = FL_IF;
  ctx->esp    = (uintptr_t)kstack.end;
#endif


  ctx->GPR1 = (uintptr_t)arg;
  ctx->GPR2 = (uintptr_t)entry;


  return ctx;
}


//////////////////////////////////


static inline void cli() {
  asm volatile ("cli");
}


static inline void sti() {
  asm volatile ("sti");
}


#define interrupt(id) \
  asm volatile ("int $" #id);


static inline uint32_t get_efl() {
  volatile uintptr_t efl;
  asm volatile ("pushf; pop %0": "=r"(efl));
  return efl;
}

cli 禁止中断发生

sti 允许中断发生

get_efl 获取 eflags 寄存器的内容

#define FL_IF          0x00000200  // Interrupt Enable

上下文切换

void __am_irq_handle(struct trap_frame *tf);


#if __x86_64__
struct trap_frame {
  Context saved_context;
  uint64_t irq, errcode;
  uint64_t rip, cs, rflags, rsp, ss;
};
#else
struct trap_frame {
  Context saved_context;
  uint32_t irq, errcode;
  uint32_t eip, cs, eflags, esp, ss;
};
#endif

Event/Context

// Arch-dependent processor context
typedef struct Context Context;


// An event of type @event, caused by @cause of pointer @ref
typedef struct {
  enum {
    EVENT_NULL = 0,
    EVENT_YIELD, EVENT_SYSCALL, EVENT_PAGEFAULT, EVENT_ERROR,
    EVENT_IRQ_TIMER, EVENT_IRQ_IODEV,
  } event;
  uintptr_t cause, ref;
  const char *msg;
} Event;

x86-64 Context

struct Context {
  void    *cr3;
  uint64_t rax, rbx, rcx, rdx,
           rbp, rsi, rdi,
           r8, r9, r10, r11,
           r12, r13, r14, r15,
           rip, cs, rflags,
           rsp, ss, rsp0;
};




#define GPR1 rdi
#define GPR2 rsi
#define GPR3 rdx
#define GPR4 rcx
#define GPRx rax

x86 Context

struct Context {
  void    *cr3;
  uint32_t ds, eax, ebx, ecx, edx,
           esp0, esi, edi, ebp,
           eip, cs, eflags, esp, ss3;
};


#define GPR1 eax
#define GPR2 ebx
#define GPR3 ecx
#define GPR4 edx
#define GPRx eax

debug

在 AM Makefile 的 CFLAGS 中加上 -g

在 AM 和 kernel 中 make clean

然后在 kernel.gdb 中添加

symbol-file /home/vgalaxy/os-workbench-2022/kernel/build/kernel-x86_64-qemu.elf

读取符号信息

如果需要调试 boot block，需要在 kernel.gdb 中添加

symbol-file /home/vgalaxy/os-workbench-2022/abstract-machine/am/src/x86/qemu/boot/bootblock.symbol

读取符号信息

其中 bootblock.symbol 通过修改 abstract-machine/am/src/x86/qemu/boot 中的 Makefile 得到

SRCS := start.S main.c
bootblock.o: $(SRCS) Makefile
  @echo + CC $(SRCS)
  @$(CROSS_COMPILE)gcc -static -m32 -fno-pic -Os -nostdlib -Ttext 0x7c00 -I$(AM_HOME)/am/src -o bootblock.o $(SRCS)
  @python3 genboot.py bootblock.o
  @$(CROSS_COMPILE)gcc -static -m32 -fno-pic -Os -g -nostdlib -Ttext 0x7c00 -I$(AM_HOME)/am/src -o bootblock.symbol $(SRCS)


clean:
  rm -rf *.o

另外还可以配置 .gdbinit

# 输出信息多时不会暂停输出
set pagination off


# 退出时不显示提示信息
set confirm off


# 按照派生类型打印对象
set print object on


# 打印数组的索引下标
set print array-indexes on


# 每行打印一个结构体成员
set print pretty on

local test

L1 的 local test 方法似乎失效，关键在于实现 AM 中的 CTE 和 IOE

与 L1 类似，Online Judge 会使用自己的 framework 代码，但会调用 os->init() 和 os->run()

所以可以在 os_init 中添加测试代码，但使用一些预编译指令确保在 Online Judge 时测试代码不会被执行

可以在 os_init 中 iset(true)，此时为单核

也可以在 os_run 中 iset(true)，可以测试多核

测试代码为死循环

输出要求，总是合法括号序列的前缀，且括号嵌套的深度不超过 5

使用 pc-check.py 检验

import sys


limit = int(sys.argv[1])
count, n = 0, 100000
while True:
    for ch in sys.stdin.read(n):
        if ch == '(': count += 1
        if ch == ')': count -= 1
        assert 0 <= count <= limit
    print(f'{n} Ok.')

输出流的内容有点乱

KISS

先不考虑线程/中断安全性

完全仿照 thread-os.c

主要分为三个部分

os_trap 直接抄实验指南即可

os_on_irq 保证插入时 seq 有序即可

限制 handlers 的最大值

kmt_create 中需要调用 kcontext，就像 thread-os.c 里面的 main 函数一样

仍然限制 tasks 的最大值

kmt_teardown 释放内存

线程调度使用随机的方式，参考 PA4，并使用 os_on_irq 注册

小心完全随机，可能调度的 task 正在其他的 CPU 上运行

于是引入 RUNNING 状态

注意到可能 create 出的线程都阻塞了

所以需要保存主线程的上下文，即 OS 在 os_run 中死循环处理各种中断

将 prev 上下文的保存和主线程上下文的保存置入 kmt_context_save 这个中断处理程序中

自旋锁就是 atomic_xchg

信号量可以参考 sem.py

还需要实现一个队列，注意指针的读写性质

xv6

试图抄作业

https://github.com/mit-pdos/xv6-public

$ make qemu

device

修复了 os.h 的错误后，尝试一下官方测试用例 dev 模块

struct device {
  const char *name;
  int id;
  void *ptr;
  devops_t *ops;
};

ptr 指向每一个设备具体的结构体

ops 抽象了设备的三种操作

typedef struct devops {
  int (*init)(device_t *dev);
  int (*read) (device_t *dev, int offset, void *buf, int count);
  int (*write)(device_t *dev, int offset, const void *buf, int count);
} devops_t;

有如下几种设备

支持读取键盘的输入

支持一个软件模拟的 2D 显示加速器的写入

两个支持读写的虚拟终端，使用 Alt-1, Alt-2 在虚拟中断之间切换

支持读写的物理磁盘，可以从中读出操作系统内核的 ELF 文件

先考虑 input 和 tty 之间的交互

input 对应的守护线程为 dev_input_task

void dev_input_task(void *args) {
  device_t *in = dev->lookup("input");
  uint32_t known_time = io_read(AM_TIMER_UPTIME).us;


  while (1) {
    uint32_t time;
    AM_INPUT_KEYBRD_T key;
    while ((key = io_read(AM_INPUT_KEYBRD)).keycode != 0) {
      input_keydown(in, key);
    }
    time = io_read(AM_TIMER_UPTIME).us;
    if ((time - known_time) / 1000 > 100 && is_empty(in->ptr)) {
      push_event(in->ptr, event(0, 0, 0));
      known_time = time;
    }
    kmt->sem_wait(&sem_kbdirq);
  }
}

从死循环的最后一行开始看，wait 信号量 sem_kbdirq

并且 input_init 中为键盘输入和时钟两个事件注册了中断处理程序，其中 signal 信号量 sem_kbdirq

实际上起到了阻塞的作用

来到死循环开头，若有键盘输入，则 input_keydown，其中会调用 push_event

否则也会调用 push_event，只不过 event 的具体内容不同

static void push_event(input_t *in, struct input_event ev) {
  kmt->spin_lock(&in->lock);
  in->events[in->rear] = ev;
  in->rear = (in->rear + 1) % NEVENTS;
  panic_on(is_empty(in), "input queue full");
  kmt->spin_unlock(&in->lock);
  kmt->sem_signal(&in->event_sem);
}


static struct input_event pop_event(input_t *in) {
  kmt->sem_wait(&in->event_sem);
  kmt->spin_lock(&in->lock);
  panic_on(is_empty(in), "input queue empty");
  int idx = in->front;
  in->front = (in->front + 1) % NEVENTS;
  struct input_event ret = in->events[idx];
  kmt->spin_unlock(&in->lock);
  return ret;
}

tty 对应的守护线程 dev_tty_task 会调用 input 设备的 input_read，其中调用 pop_event 读取 event

请注意 push_event 和 pop_event 中自旋锁和信号量的交互

multi-processing

https://lists.gnu.org/archive/html/qemu-devel/2022-01/msg04271.html

将

-smp 2

改为

-smp sockets=2

arch linux 的 qemu 版本太新……

klib todo

tty 翻页

直接抄 xv6

monitor log

https://qemu.readthedocs.io/en/latest/system/monitor.html

https://unix.stackexchange.com/questions/237409/logging-and-debugging-for-qemu-virtual-machines

虚拟机神秘重启

参考

 $ qemu-system-x86_64 -d help

添加如下参数

-d cpu_reset

或者在 monitor 中

(qemu) log cpu_reset

可以发现在重启前，PC 指向中断处理程序

判断在中断处理程序中错误的恢复了中断

导致了 triple fault

于是修改 kmt_spin_lock 和 kmt_spin_unlock

记录刚刚持有一个自旋锁时中断的状态，以及持有的自旋锁数量

后来参考 xv6 实现，在使用自旋锁时进行更多的断言

old ubuntu

ubuntu 18.04

安装 qemu

% qemu-system-x86_64 --version
QEMU emulator version 2.11.1(Debian 1:2.11+dfsg-1ubuntu7.39)
Copyright (c) 2003-2017 Fabrice Bellard and the QEMU Project developers

配置编译环境

% sudo apt-get install gcc-multilib

升级 python 版本

https://segmentfault.com/a/1190000018264955?utm_source=tag-newest

doubt

参考 thread-os.c 为 enum

实际上无所谓，使用 enum 保证整个 task 的大小为 stack 的大小，方便对齐

实际上 pmm 已经保证大小是 2 的幂了

注意创建内核栈的语句

Area stack = (Area){&task->u.context + 1, task + 1};

context 为指针，栈的低地址是 context 字段后的空间，栈的高地址是 task 的末尾

考虑使用金丝雀检测栈溢出

以 yield 为例

int 0x81，对应 __am_irq_129

.globl __am_irq##id; __am_irq##id: cli;      err; push $id; jmp trap;

触发 EX_YIELD 事件

不确定关中断的效果

比如在 thread-os.c 中测试

void mp_entry() {
  iset(false);
  yield();
}

仍然会进行中断处理

以 x86-64 为例

trap 汇编代码填充了除 Context 结构体最后 6 个字段的其余字段

struct Context {
  void    *cr3;
  uint64_t rax, rbx, rcx, rdx,
           rbp, rsi, rdi,
           r8, r9, r10, r11,
           r12, r13, r14, r15,
           rip, cs, rflags,
           rsp, ss, rsp0;
};

__am_irq_handle 中参数指向 Context 结构体的开头，并解释为 trap_frame 结构体

struct trap_frame {
  Context saved_context;
  uint64_t irq, errcode;
  uint64_t rip, cs, rflags, rsp, ss;
};

并通过 trap_frame 填充之前未填充的字段

  saved_ctx->rip    = tf->rip;
  saved_ctx->cs     = tf->cs;
  saved_ctx->rflags = tf->rflags;
  saved_ctx->rsp    = tf->rsp;
  saved_ctx->rsp0   = CPU->tss.rsp0;
  saved_ctx->ss     = tf->ss;

实际上，在 int 指令后，硬件保存了一些字段在栈上，同时跳转到对应的 __am_irq_xxx

qemu 使用 thread 来模拟 CPU 的执行

iset 只影响当前线程的 eflags 寄存器

请注意，即使当前 CPU 关了中断，也可能 thread 模拟调度到其他 CPU 执行

于是 os_trap 成为并发问题的重灾区

保存中断前的 FL_IF 位，然后关中断

处理后，若之前允许中断，则允许中断，否则仍关中断

cheat

参考 https://github.com/KruskalLin/os-workbench

重构 task 结构体和线程创建和调度部分

主要思路

使用 static 变量并在 pmm 中置内存为零，以确保默认初始化

submit

单 CPU 就 thread starvation 了

尝试 Round-Robin 仍然 thread starvation

处理线程返回的情形，引入 INVALID 状态，并使用 wrapper 包装 entry

破案了，罪魁祸首

Hello World from CPU #0

于是 AC

L3: 用户态进程 (uproc)

参考 https://www.bilibili.com/video/BV1iY411A7w1

user

$ install nasm
$ ndisasm -b 64 _init

没有 x86_64-linux-gnu-xxx

asynchronous

sleep / wait 本质上都是异步操作

进程需要满足一定的条件才能继续运行

可能的解决方案

mmap

每个进程维护如下的映射关系

va→pa\text{va} \to \text{pa}

观察到进程的地址空间范围

[0x100000000000, 0x108000000000)

代码段在最前，栈在最后

当触发缺页异常时，始终以 PROT_READ | PROT_WRITE 和 MAP_PRIVATE 的方式映射

实际上可以细分

fork 时，子进程会复制父进程的映射关系，并根据 flags 选择是否需要分配新的物理空间

子进程的 flags 目前始终为 MAP_PRIVATE

mmap 时，根据参数添加新的映射关系即可

memory

wait 需要将子进程 exit 的退出代码保存到 status 指向的位置

使用 handler 的方案，需要考虑如何持久化的保存 status 所指向的位置

如果有如下的映射关系

map: 0x100000000000 -> 0x102d000

在 qemu 的控制台中查看内存

x /fmt addr -- virtual memory dump starting at 'addr'
xp /fmt addr -- physical memory dump starting at 'addr'

一些例子

(qemu) xp /4x 0x102d000
000000000102d000: 0x00044ee8 0xc7894800 0x03c0c748 0xcd000000
(qemu) xp /4x 0x100000000000
0000100000000000: Cannot access memory
(qemu) x /4x 0x100000000000
0000100000000000: 0x00044ee8 0xc7894800 0x03c0c748 0xcd000000

在 gdb 中查看内存

-exec help x
Examine memory: x/FMT ADDRESS.
ADDRESS is an expression for the memory address to examine.
FMT is a repeat count followed by a format letter and a size letter.
Format letters are o(octal), x(hex), d(decimal), u(unsigned decimal),
  t(binary), f(float), a(address), i(instruction), c(char), s(string)
  and z(hex, zero padded on the left).
Size letters are b(byte), h(halfword), w(word), g(giant, 8 bytes).
The specified number of objects of the specified size are printed
according to the format.  If a negative number is specified, memory is
examined backward from the address.


Defaults for format and size letters are those previously used.
Default count is 1.  Default address is following last thing printed
with this command or "print".

一些例子

-exec x/4 0x100000000000
0x100000000000:  0x00044ee8  0xc7894800  0x03c0c748  0xcd000000
-exec x/4 0x102d000
0x102d000:  0x00044ee8  0xc7894800  0x03c0c748  0xcd000000

回到正题，当在内核代码中执行如下语句时

*(outer_curr->wstate) = inner_curr->xstate;

若 outer_curr->wstate 保存的是虚拟地址，则会根据 cr3 寄存器将其翻译为物理地址

注意到陷入内核时并不会重置 cr3 寄存器，只有从内核返回时才会根据上下文更新 cr3 寄存器

而父子进程的虚拟地址会出现重合，如栈区域，若此时 cr3 寄存器为子进程上下文中的，则会写入到子进程的栈中，这显然不合理

所以应该根据 outer_curr 的映射关系保存物理地址

detail

todo

需要自己写一个 printf

dfs-fork

访问全局数据区的行为诡异

缺页的线性地址 0x201 不在用户地址空间内

map: 0x0 -> 0x1034000
AM Panic: mapping an invalid address @ /home/vgalaxy/Desktop/os-workbench-2022/abstract-machine/am/src/x86/qemu/vme.c:142

若 static char map[][512]，则地图的一部分无法正常显示

修改为 static char map[][8]，则一切正常

发现是因为没有考虑 _init 超出一个页面大小的情形

需要注意页面的映射是以页面大小为单位的

在 init.c 中引入 printf 后，发现在不使用 static 修饰的情形下

访问 map[x][y] 会出错，访问 map[1][1] 则没有问题

考虑 if (map[x][y] == DEST) 的反汇编

$ ndisasm -b 64 ./_init

不使用 static 修饰

00000B7D  48C1E209          shl rdx,byte 0x9
00000B81  488D0527080000    lea rax,[rel 0x13af]
00000B88  4801D0            add rax,rdx
00000B8B  803C082B          cmp byte [rax+rcx],0x2b

使用 static 修饰

00000B7D  48C1E009          shl rax,byte 0x9
00000B81  48030560080000    add rax,[rel 0x13e8]
00000B88  803C102B          cmp byte [rax+rdx],0x2b

据悉，应当使用 static 修饰，因为 objcopy 时漏掉了某些 segments

ridiculousness

在 kalloc_safe 中添加如下代码，即可通过 L3 Easy Test(s)

  if (ret == NULL) {  // ridiculousness
    while(1);
  }

猜测是 pmm 实现存在问题，内存利用率不够