【Create my OS】7 用户线程

December 22, 2024

本章我们来开始编写运行在 U-Mode 下的程序，并且实现一些简单的系统调用，让 U-Mode 进程和 S-Mode 的操作系统可以借此沟通。

7.1 创建用户程序

1、实现系统调用本节实现一个 U-Mode 的程序运行所需要的运行时环境，这个环境为 U-Mode 程序提供了堆空间和系统调用接口。用户程序通过 ecall 指令触发 User Environment Call 异常，来向运行在 S-Mode 下的内核请求服务，这个过程就像内核通过 ecall 请求 M-Mode 的 OpenSBI 提供服务一样。

我们首先来定义两个简单的系统调用（这部分内容和 kernel/sbi.h 的内容基本一致）：

// user/syscall.h

// 系统调用号定义
typedef enum {
    Write = 64,     // 向屏幕输出字符
    Exit = 93,      // 退出当前线程
} SyscallId;

// 系统调用宏定义（用户态调用ECALL）
// register声明四个寄存器变量，并通过asm与对应的寄存器绑定，然后赋值
// +表示a0是一个输入输出寄存器
// 输入操作数为a1、a2、a3、a7，使用任意动态分配的寄存器
// 修饰寄存器memory，告诉编译器ecall指令可能会修改内存，即不要对内存优化
// a7 寄存器保存系统调用号，a0、a1、a2 和 a3 分别是系统调用的参数。
#define sys_call(__num, __a0, __a1, __a2, __a3)                          \
({                                                                  \
    register unsigned long a0 asm("a0") = (unsigned long)(__a0);    \
    register unsigned long a1 asm("a1") = (unsigned long)(__a1);    \
    register unsigned long a2 asm("a2") = (unsigned long)(__a2);    \
    register unsigned long a3 asm("a3") = (unsigned long)(__a3);    \
    register unsigned long a7 asm("a7") = (unsigned long)(__num);   \
    asm volatile("ecall"                                            \
                : "+r"(a0)                                          \
                : "r"(a1), "r"(a2), "r"(a3), "r"(a7)                         \
                : "memory");                                        \
    a0;                                                             \
})

// 不同参数个数系统调用宏拓展，没有参数时传递0
#define sys_write(__a0) sys_call(Write, __a0, 0, 0, 0)
#define sys_exit(__a0) sys_call(Exit, __a0, 0, 0, 0)

Write 用于向屏幕上输出字符，Exit 用于退出当前线程。当然作为一个 U-Mode 程序是没有这些功能的，所以这些系统调用还需要由内核来实现。

2、实现printf()函数，和kernel/printf.c中的内容基本一致

// user/io.c

#include <stdarg.h>     // 对于参数不定场景，使用 va_list 迭代遍历采参数
#include "types.h"
#include "ulib.h"
#include "syscall.h"

// 提供 16 进制数字字符的映射，供 printint 和 printptr 使用
static char digits[] = "0123456789abcdef";

// 向终端输出一个字符
void putchar(int c)
{
    sys_write(c);
}

/*
    功能：将一个整数格式化为字符串，并输出到控制台
    输入：xx：要打印的整数；
        base：数字的进制，支持 10（十进制）和 16（十六进制）；
        sign：是否为有符号整数（1 表示有符号，0 表示无符号）
*/
static void
printint(int xx, int base, int sign)
{
    char buf[16];
    int i;
    uint x;

    if (sign && (sign = xx < 0))
        x = -xx;
    else
        x = xx;

    i = 0;
    do
    {
        buf[i++] = digits[x % base];
    } while ((x /= base) != 0);

    if (sign)
        buf[i++] = '-';

    while (--i >= 0)
        putchar(buf[i]);
}

/*
    功能：将指针（64 位地址）格式化为十六进制字符串并输出
    输入：x-要打印的指针地址
*/
static void
printptr(uint64 x)
{
    int i;
    putchar('0');
    putchar('x');
    for (i = 0; i < (sizeof(uint64) * 2); i++, x <<= 4)
        putchar(digits[x >> (sizeof(uint64) * 8 - 4)]);
}

/*
    功能：格式化输出到控制台，支持以下格式：
          %d：十进制整数。
          %x：十六进制整数。
          %p：指针。
          %s：字符串。
          %%：输出 % 本
    输入：fmt-格式化字符串；可变参数列表（...）-对应的值
*/
void printf(char *fmt, ...)
{
    va_list ap;
    int i, c;
    char *s;

    if (fmt == 0)
        panic("null fmt");

    va_start(ap, fmt);
    for (i = 0; (c = fmt[i] & 0xff) != 0; i++)
    {
        if (c != '%')
        {
            putchar(c);
            continue;
        }
        c = fmt[++i] & 0xff;
        if (c == 0)
            break;
        switch (c)
        {
        case 'd':
            printint(va_arg(ap, int), 10, 1);
            break;
        case 'x':
            printint(va_arg(ap, int), 16, 1);
            break;
        case 'p':
            printptr(va_arg(ap, uint64));
            break;
        case 's':
            if ((s = va_arg(ap, char *)) == 0)
                s = "(null)";
            for (; *s; s++)
                putchar(*s);
            break;
        case '%':
            putchar('%');
            break;
        default:
            putchar('%');
            putchar(c);
            break;
        }
    }
}

/*
    功能：打印紧急错误信息并冻结系统
    输入：s-错误消息字符串
*/
void panic(char *s)
{
    printf("panic: ");
    printf(s);
    printf("\n");
    sys_exit(1);
}

我们在用户文件夹下也创建一个函数库声明头文件

// user/ulib.h

/*  io.c    */
uint8 getc();
void printf(char *, ...);
void panic(char*);
void putchar(int c);

/*  malloc.c    */
void *malloc(uint32 size);
void free(void *ptr);

3、U-Mode动态内存分配

我们需要支持 U-Mode 下的动态内存分配，以便在用户进程中使用 malloc，这时的堆空间显然不可能存在内核里了，我们需要另外新建用户堆（分配算法也使用 Buddy System Allocation，和内核的实现基本一致）

// user/malloc.c

#include "types.h"
#include "ulib.h"

/* 动态内存分配相关常量 */
#define USER_HEAP_SIZE      0x1000          /* 堆空间大小 4K */
#define MIN_BLOCK_SIZE      0x20            /* 最小分配的内存块大小 32bytes */
#define HEAP_BLOCK_NUM      0x80            /* 管理的总块数 96 */
#define BUDDY_NODE_NUM      0xff            /* 二叉树节点个数 */

#define LEFT_LEAF(index) ((index) * 2 + 1)
#define RIGHT_LEAF(index) ((index) * 2 + 2)
#define PARENT(index) ( ((index) + 1) / 2 - 1)

#define IS_POWER_OF_2(x) (!((x)&((x)-1)))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

static uint8 HEAP[USER_HEAP_SIZE];          /*  用于分配的堆空间，4 KBytes */

/* 
 * Buddy System Allocation 的具体实现
 * 使用一棵数组形式的完全二叉数来监控内存
 */
struct
{
    uint32 size;                    /* 管理的总块数 */
    uint32 longest[BUDDY_NODE_NUM]; /* 每个节点表示范围内空闲块个数 */
} buddyTree;

// 二叉树初始化
void
buddyInit(int size)
{
    buddyTree.size = size;
    uint32 nodeSize = size << 1;
    int i;
    /* 初始化每个节点，此时每一块都是空闲的 */
    for(i = 0; i < (size << 1) - 1; i ++) {
        if(IS_POWER_OF_2(i+1)) {
            nodeSize /= 2;
        }
        buddyTree.longest[i] = nodeSize;
    }
}

// 初始化堆空间
void
initHeap()
{
    buddyInit(HEAP_BLOCK_NUM);
}

/*
 * 获得大于等于 size 的最小的 2 的幂级数
 * 算法来自于 Java 的 Hashmap
 */
uint32
fixSize(uint32 size)
{
    uint32 n = size - 1;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

/* 
 * 分配 size 大小的块(单位为MIN_BLOCK_SIZE)，通过二叉树进行管理
 * 返回空闲块的第一块在堆上的偏移（0~HEAP_BLOCK_NUM），单位为MIN_BLOCK_SIZE
 */
uint32
buddyAlloc(uint32 size)
{
    uint32 index = 0;
    uint32 nodeSize;
    uint32 offset;

    if(size <= 0) size = 1;
    else if(!IS_POWER_OF_2(size)) size = fixSize(size);

    /* 一共也没有那么多空闲块 */
    if(buddyTree.longest[0] < size) {
        return -1;
    }
    
    /* 寻找大小最符合的节点 */
    for(nodeSize = buddyTree.size; nodeSize != size; nodeSize /= 2) {
        uint32 left = buddyTree.longest[LEFT_LEAF(index)];
        uint32 right = buddyTree.longest[RIGHT_LEAF(index)];
        /* 优先选择最小的且满足条件的分叉，小块优先，尽量保留大块 */
        if(left <= right) {
            if(left >= size) index = LEFT_LEAF(index);
            else index = RIGHT_LEAF(index);
        } else {
            if(right >= size) index = RIGHT_LEAF(index);
            else index = LEFT_LEAF(index);
        }
    }

    /* 标记为占用 */
    buddyTree.longest[index] = 0;
    /* 获得这一段空闲块的第一块在堆上的偏移 */
    offset = (index + 1) * nodeSize - buddyTree.size;

    /* 向上修改父节点的值 */
    while(index) {
        index = PARENT(index);
        buddyTree.longest[index] = 
            MAX(buddyTree.longest[LEFT_LEAF(index)], buddyTree.longest[RIGHT_LEAF(index)]);
    }

    return offset;
}

/* 
 * 在堆上分配内存,利用 buddyAlloc 进行分配
 * 输入：size，单位为 Byte
 * 输出：分配空间的起始地址
*/
void *
malloc(uint32 size)
{
    if(size == 0) return 0;

    /* 获得所需要分配的块数 */
    uint32 n = (size - 1) / MIN_BLOCK_SIZE + 1;
    uint32 block = buddyAlloc(n);
    if(block == -1) panic("Malloc failed!\n");

    /* 清除这一段内存空间 */
    uint32 totalBytes = fixSize(n) * MIN_BLOCK_SIZE;
    uint8 *beginAddr = (uint8 *)((usize)HEAP + (usize)(block * MIN_BLOCK_SIZE));
    uint32 i;
    for(i = 0; i < totalBytes; i ++) {
        beginAddr[i] = 0;
    }
    
    return (void *)beginAddr;
}

/* 
 * 根据 offset 回收空间
 * offset单位为块（MIN_BLOCK_SIZE） 指在二叉树节点中的偏移 
*/
void
buddyFree(uint32 offset)
{
    uint32 nodeSize, index = 0;
    
    nodeSize = 1;
    index = offset + buddyTree.size - 1;

    /* 向上回溯到之前分配块的节点位置 */
    for( ; buddyTree.longest[index]; index = PARENT(index)) {
        nodeSize *= 2;
        if(index == 0) {
            return;
        }
    }
    buddyTree.longest[index] = nodeSize;

    /* 继续向上回溯，合并连续的空闲区间 */
    while(index) {
        index = PARENT(index);
        nodeSize *= 2;

        uint32 leftLongest, rightLongest;
        leftLongest = buddyTree.longest[LEFT_LEAF(index)];
        rightLongest = buddyTree.longest[RIGHT_LEAF(index)];

        if(leftLongest + rightLongest == nodeSize) {
            buddyTree.longest[index] = nodeSize;
        } else {
            buddyTree.longest[index] = MAX(leftLongest, rightLongest);
        }
    }
}

/* 
 * 回收被分配出去的内存 
 * 输入：回收空间的起始地址
*/
void
free(void *ptr)
{
    if((usize)ptr < (usize)HEAP) return;
    if((usize)ptr > (usize)HEAP + USER_HEAP_SIZE - MIN_BLOCK_SIZE) return;
    /* 相对于堆空间起始地址的偏移 */
    uint32 offset = (usize)((usize)ptr - (usize)HEAP);
    buddyFree(offset / MIN_BLOCK_SIZE);
}

4、用户程序入口点

和内核一样，用户程序也需要一个入口点。这里的入口点也不是 main() 函数，在进入 main() 函数之前，还需要做一些初始化工作，比如初始化堆空间。
入口点函数命名为 _start()，gcc 默认的编译配置中，当 _start() 函数存在时，会将 EntryPoint 设置为 _start()，而不是 main()。

// user/entry.c

#include "types.h"
#include "ulib.h"
#include "syscall.h"

/*
 * 弱链接 main 函数
 * 当没有 main 函数被链接时会链接此函数
 */
__attribute__((weak)) uint64
main()
{
    panic("No main linked!\n");
    return 1;
}

/*
 * 用户程序入口点
 * gcc 默认的编译配置中，当 _start() 函数存在时，会将 EntryPoint 设置为 _start()，而不是 main()
 * 初始化堆并调用 main
 */
void
_start(uint8 _args, uint8 *_argv)
{
    // 初始化用户堆空间
    extern void initHeap();     initHeap();
    sys_exit(main());
}

5、Hello World测试函数

// user/hello.c

#include "types.h"
#include "ulib.h"

uint64
main()
{
    int i;
    char *c = malloc(8);        // 在堆上分配内存
    for(i = 0; i < 8; i ++) {
        c[i] = i;
    }
    for(i = 0; i < 10; i ++) {
        printf("Hello world from user mode program!\n");
    }
    return 0;
}

在 Makefile 中新建一个 target，用来编译用户程序并链接，最终形成 User 文件。

// Makefile

U = user

UPROS =                        \
    $U/entry.o                \
    $U/malloc.o                \
    $U/io.o                    \
    $U/hello.o

User: $(subst .c,.o,$(wildcard $U/*.c))
    $(LD) $(LDFLAGS) -o $U/User $(UPROS)
    cp $U/User User

$U/%.o: $U/%.c
    $(CC) $(CFLAGS) -c $< -o $@

不要忘了把kernel/types.h文件拷贝一份到user/types.h
执行 make User 命令，就会在根目录生成一个 User 目标文件。

6、合并到内核

目前我们的操作系统还没有文件系统，文件系统会在下一节讲解。我们如果想在操作系统中运行上一节编写的用户程序，就只能暂时把它和内核合并在一起，这样在最开始 OpenSBI 就会将内核和应用程序一并加载到内存中了。
具体的做法就是将编译出的目标文件直接链接到 .data 段，一个字节都不改动。我们可以使用一个汇编文件实现这个功能。

# kernel/linkUser.asm

# 将用户程序链接到 .data 段

.section .data
    .global _user_img_start
    .global _user_img_end
_user_img_start:
    .incbin "User"
_user_img_end:

我们为应用程序数据的开头和结尾设置了两个全局符号：_user_img_start 和 _user_img_end，这样在内核中就可以快速找到这些数据了
不要忘了把这个文件关联到任意一个 .c 文件中，否则这段汇编不会生效。

// kernel/main.c

asm(".include \"kernel/linkUser.asm\"");

void
main()
....

同时，还需要将 Makefile 中 Kernel 的前置条件中加上 User，否则直接运行 Kernel 的话可能会无法找到 User 文件。

Kernel: User $(subst .c,.o,$(wildcard $K/*.c))
    $(LD) $(LDFLAGS) -T $K/kernel.ld -o $K/Kernel $(OBJS)
    $(OBJCOPY) $K/Kernel -O binary Image

7.2 实现系统调用

1、用户环境调用中断

我们需要让内核的中断处理函数响应来自 U-Mode 的系统调用。当系统调用发生时，scause 寄存器会被设置为 0x8。

// kernel/interrupt.c

// 系统调用中断处理
void
handleSyscall(InterruptContext *context)
{
    context->sepc += 4;     // 跳过 ecall 指令
    extern usize syscall(usize id, usize args[3], InterruptContext *context);
    // 处理系统调用
    usize ret = syscall(
        // 传入 a7 系统调用号
        context->x[17],     
        // 传入 a0、a1、a2 系统调用参数
        (usize[]){context->x[10], context->x[11], context->x[12]},
        context
    );
    context->x[10] = ret;   // 将 a0 寄存器设置为系统调用处理的返回值
}

// 中断处理函数，接受interrupt.S传递过来的三个参数 sp, scause, stval
// sp保存上下文向下移动34个usize，所以sp也是一个指向InterruptContext的指针！
void 
handleInterrupt(InterruptContext *context, usize scause, usize stval)
{
    switch(scause) {
        case BREAKPOINT:            // 断点中断
            breakpoint(context);
            break;
        case USER_ENV_CALL:         // U-Mode 系统调用
            handleSyscall(context);
            break;
        case SUPERVISOR_TIMER:      // 时钟中断
            supervisorTimer();
            break;
        default:                    // 未知中断
            fault(context, scause, stval);
            break;
    }
}

2、处理系统调用

处理系统调用的过程很简单，我们已经传入了系统调用号，只需要根据调用号来提供不同的服务就可以了。

// kernel/syscall.c

const usize SYS_WRITE = 64;
const usize SYS_EXIT = 93;

// 处理系统调用
usize
syscall(usize id, usize args[3], InterruptContext *context)
{
    switch (id)
    {
    case SYS_WRITE:     // 系统写
        consolePutchar(args[0]);
        return 0;
    case SYS_EXIT:      // 系统线程退出
        exitFromCPU(args[0]);
        return 0;
    default:
        printf("Unknown syscall id %d\n", id);
        panic("");
        return -1;
    }
}

SYS_EXIT 表示退出当前线程，此时 CPU 上运行着的就是发起这个系统调用的线程，所以直接调用 exitFromCPU() 退出。

谁在处理系统调用

通常，我们会毫不犹豫地说，是内核在处理系统调用。但实际上，所有的执行流都是位于线程中的，即使是最初的启动过程也是位于“启动线程”的。那么是哪个线程在处理呢？
是**发起系统调用的线程**在处理（谁发起，谁处理）。当用户线程发起系统调用时，会从 U-Mode 进入 S-Mode，但是线程还是原来的线程，保留有原本的线程 ID 等。这就是为什么线程需要两个栈，用户栈和内核栈，内核栈是在该线程进入 S-Mode 后使用的栈。

7.3 进程内存空间

1、还记得我们在 1.2节 编译内核镜像时说的，链接之后形成的 ELF 文件中，描述了系统各个段的信息。由于当时我们并没有操作系统，无法映射各个段到内存的正确位置，于是使用了 objcopy 工具来生成已经映射完成的镜像，随后被直接加载到 QEMU 中。

7.1节编译出的用户程序，也是 ELF 格式，这次我们需要在操作系统中运行这个程序，需要手动映射各个段，于是我们需要了解一下 ELF 文件的组成。

（出自1.3节）编译链接出的 elf 格式目标文件，是可以直接被操作系统加载进内存执行的，具体的过程就是操作系统根据 Program Header 的信息映射各个段到内存中。但是问题是，我们要运行的环境中没有操作系统（因为我们自己就是操作系统），自然没法映射各个段。于是，我们需要自己手动做这个工作。

**ELF 文件** 是一个 **带有头信息和段信息的结构化文件**，适用于操作系统加载和内存映射。
**镜像文件** 是一个 **纯粹的二进制文件**，它只包含程序的原始二进制数据，不包含 ELF 文件中的元数据（如头部和符号表等）。生成的 `Image` 文件是可以直接加载到内存中的，QEMU 虚拟机可以将其加载并执行。

ELF Header：ELF 头位于 ELF 文件开头，描述了一个 ELF 所有的基本信息，包括如何寻找到其他的信息。ELF Header 在 Linux Kernel 中的定义如下：

typedef struct
{
  unsigned char    e_ident[EI_NIDENT];    /* Magic number and other info */
  Elf64_Half    e_type;            /* Object file type */
  Elf64_Half    e_machine;        /* Architecture */
  Elf64_Word    e_version;        /* Object file version */
  Elf64_Addr    e_entry;        /* Entry point virtual address */
  Elf64_Off    e_phoff;        /* Program header table file offset */
  Elf64_Off    e_shoff;        /* Section header table file offset */
  Elf64_Word    e_flags;        /* Processor-specific flags */
  Elf64_Half    e_ehsize;        /* ELF header size in bytes */
  Elf64_Half    e_phentsize;        /* Program header table entry size */
  Elf64_Half    e_phnum;        /* Program header table entry count */
  Elf64_Half    e_shentsize;        /* Section header table entry size */
  Elf64_Half    e_shnum;        /* Section header table entry count */
  Elf64_Half    e_shstrndx;        /* Section header string table index */
} Elf64_Ehdr;

ELF 头的第一个字段是一个 MAGIC_NUMBER，用于校验这个文件是否是 ELF 文件。ELF MAGIC NUMBER 的取值是 0x7f454c46，实际上就是 7f “E” “L” “F”。
ELF 头描述了该文件的类型、架构、版本、入口点等基本信息。由于我们需要将这个文件加载进内存中运行，我们更需要关注这个字段：e_phoff，它表示 ELF 程序头相对于 ELF 文件的第一个字节的偏移。
Program Header：通过 e_phoff 我们可以找到文件的程序头，程序头定义如下：

typedef struct {
  Elf64_Word p_type;    //描述该段的类型
  Elf64_Word p_flags;   //以p_type而定
  Elf64_Off p_offset;   //该段的开始相对于文件开始的偏移量
  Elf64_Addr p_vaddr;   //段虚拟地址
  Elf64_Addr p_paddr;   //段的虚拟地址  
  Elf64_Xword p_filesz; //文件映像中该段的字节数
  Elf64_Xword p_memsz;  //内存映像中该段的字节数
  Elf64_Xword p_align;  //描述要对齐的段在内存中如何对齐，该值是2的整数次幂        
} Elf64_Phdr;

p_type 描述了该段的类型，对于操作系统来说，我们需要关注类型为 LOAD 的段，只需要把这些段装载进内存。
p_flags 字段是该段的具体权限，需要载入后转化为页表权限
p_offset 用于找到具体的段数据
p_vaddr 指定了这个段必须被加载到虚拟内存空间的哪一个地址
p_filesz 说明了这个段在文件中的大小
p_memsz 说明了这个段在内存中的大小
这些信息记录了 ELF 文件中的 Segment 信息，在程序被载入内存中使用。ELF 文件的另一个概念，section，描述了具体的代码段数据段的信息，但是 section 信息对于载入程序来说是透明的，操作系统不需要知道所载入的 Segment 和实际的 section 的关系。

2、解析ELF：

我们首先定义一些 ELF 的相关结构，这样可以方便地将数据直接转化成这些结构的指针，直接读取。

// kernel/elf.h

// ELF 魔数   F L E 7f
#define ELF_MAGIC 0x464C457FU 

// ELF 文件头
typedef struct {
  uint magic;
  uchar elf[12];        /* Magic number and other info */
  ushort type;          /* Object file type */
  ushort machine;       /* Architecture */
  uint version;         /* Object file version */
  uint64 entry;         /* Entry point virtual address */
  uint64 phoff;         /* Program header table file offset */
  uint64 shoff;         /* Section header table file offset */
  uint flags;           /* Processor-specific flags */
  ushort ehsize;        /* ELF header size in bytes */
  ushort phentsize;     /* Program header table entry size */
  ushort phnum;         /* Program header table entry count */
  ushort shentsize;     /* Section header table entry size */
  ushort shnum;         /* Section header table entry count */
  ushort shstrndx;      /* Section header string table index */
} ElfHeader;

// 程序段头
typedef struct {
  uint32 type;      // 描述该段的类型
  uint32 flags;     // 以p_type而定
  uint64 off;       // 该段的开始相对于文件开始的偏移量
  uint64 vaddr;     // 段加在到虚拟内存空间的地址
  uint64 paddr;     // 段的虚拟地址 
  uint64 filesz;    // 文件映像中该段的字节数
  uint64 memsz;     // 内存映像中该段的字节数
  uint64 align;     // 描述要对齐的段在内存中如何对齐，该值是2的整数次幂 
} ProgHeader;

// 程序段头类型
#define ELF_PROG_LOAD           1   /* 程序段头类型 LOAD */

/* 程序段头权限 */
#define ELF_PROG_FLAG_EXEC      1   /* 程序段头属性，可执行 */
#define ELF_PROG_FLAG_WRITE     2   /* 程序段头属性，可写 */
#define ELF_PROG_FLAG_READ      4   /* 程序段头属性，可读 */

我们需要创建用户进程的虚拟内存空间，其中，用户程序的代码和数据被映射在低地址空间，内核的代码和数据映射在高地址空间。在虚拟内存一章中，我们已经定义好了一个结构，Mapping，来表示一个内存空间，同时还创建了一个函数 newKernelMapping()，会返回一个已经映射好内核的 Mapping，我们直接在此基础上映射用户程序的各个段即可。

// kernel/elf.c

// 新建用户进程页映射
// 函数传入指向 ELF 文件的首字节的指针
Mapping
newUserMapping(char *elf)
{
    // 创建一个映射了内核的虚拟地址空间(创建根页表、映射程序各个段)
    Mapping m = newKernelMapping();
    ElfHeader *eHeader = (ElfHeader *)elf;
    // 校验 ELF 头
    if(eHeader->magic != ELF_MAGIC) {
        panic("Unknown file type!");
    }
    // 通过 e_phoff 可以找到文件的程序头
    ProgHeader *pHeader = (ProgHeader *)((usize)elf + eHeader->phoff);
    usize offset;
    int i;
    // 遍历所有的程序段，将类型为 LOAD 的段全部映射到虚拟内存空间
    for(i = 0, offset = (usize)pHeader; i < eHeader->phnum; i ++, offset += sizeof(ProgHeader)) {
        pHeader = (ProgHeader *)offset;
        //  判断该段的类型，对于操作系统来说，我们需要关注类型为 LOAD 的段
        if(pHeader->type != ELF_PROG_LOAD) {
            continue;
        }
        // 将 ELF 权限标志位转换为页表项属性
        usize flags = convertElfFlags(pHeader->flags);
        // 获取段映射到内存空间的起始虚拟地址、结束虚拟地址
        usize vhStart = pHeader->vaddr, vhEnd = vhStart + pHeader->memsz;
        // 创建描述映射到虚拟内存的一个段
        Segment segment = {vhStart, vhEnd, flags};
        // 计算段数据的起始位置
        char *source = (char *)((usize)elf + pHeader->off);
        // 
        mapFramedAndCopy(m, segment, source, pHeader->filesz);
    }
    return m;
}

// 将 ELF 权限标志位转换为页表项属性
usize
convertElfFlags(uint32 flags)
{
    usize ma = 1L;  // 设置有效位
    ma |= USER;     // 设置 USER 属性，以保证 U-Mode 下的程序可以访问
    if(flags & ELF_PROG_FLAG_EXEC) {
        ma |= EXECUTABLE;
    }
    if(flags & ELF_PROG_FLAG_WRITE) {
        ma |= WRITABLE;
    }
    if(flags & ELF_PROG_FLAG_READ) {
        ma |= READABLE;
    }
    return ma;
}

注意这个时候程序段的数据都实际存储在内核的 .data 段中，这片区域是属于内核的。我们当然也可以将两个虚拟地址区间映射到这些数据，但是后续我们实现文件系统时，这些数据就是存储在文件系统上了。所以我们最好还是分配新的物理内存，并且将这些数据复制到新分配的物理内存上，将虚拟地址映射到这一片空间中。mapFramedAndCopy() 就实现了这个功能。

// kernel/mapping.c

// 映射一个未被分配物理内存的段，并复制数据到新分配的内存
// m-新分配的根页表物理页号
void
mapFramedAndCopy(Mapping m, Segment segment, char *data, usize length)
{
    usize s = (usize)data, l = length;
    usize startVpn = segment.startVaddr / PAGE_SIZE;        // 起始地址虚拟页号
    usize endVpn = (segment.endVaddr - 1) / PAGE_SIZE + 1;  // 结束地址虚拟页号
    usize vpn;
    // 遍历每一页
    for(vpn = startVpn; vpn < endVpn; vpn ++) {
        // 根据给定的虚拟页号寻找三级页表项
        PageTableEntry *entry = findEntry(m, vpn);
        if(*entry != 0) {
            panic("Virtual address already mapped!\n");
        }
        // 分配一个物理页
        usize pAddr = allocFrame();
        // 设置页表项PTE
        *entry = (pAddr >> 2) | segment.flags | VALID;
        // 复制数据到目标位置
        char *dst = (char *)accessVaViaPa(pAddr);   /* 获得线性映射后的虚拟地址 */
        // 拷贝一页
        if(l >= PAGE_SIZE) {
            char *src = (char *)s;
            int i;
            for(i = 0; i < PAGE_SIZE; i ++) {
                dst[i] = src[i];    // 逐字节拷贝
            }
        } else {
            // 拷贝剩余不足一页的数据
            char *src = (char *)s;
            int i;
            for(i = 0; i < l; i ++) {
                dst[i] = src[i];    // 逐字节拷贝
            }
            for(i = l; i < PAGE_SIZE; i ++) {
                dst[i] = 0;         // 最后一页剩下字节置零
            }
        }
        // 继续拷贝下一页
        s += PAGE_SIZE;
        if(l >= PAGE_SIZE) l -= PAGE_SIZE;
        else l = 0;
    }
}

和线性映射类似，只不过填写页表项时填写的是新分配的物理页号。注意这时候如果我们想访问新分配的页面，以复制数据的话，目前的内存空间还是线性映射的内核地址空间，可以直接通过偏移量来访问。
这样我们就得到了一个同时映射好了内核和用户进程的代码和数据的虚拟地址空间了。
下一节我们就可以创建进程结构，并将其添加到 CPU 中运行。

7.4 创建用户进程

1、我们采用最简单的进程模型：一个进程中只有一个线程。

由于线程代表了进程的运行性特征，剥离出线程，进程仅仅成为了操作系统资源分配的最小单位。目前我们给进程分配的资源，就是虚拟内存空间了，可以在进程中直接保存 satp 寄存器，便于切换，后续还会给进程分配文件描述符等资源。同时，每个线程也有其所属的进程。

// kernel/thread.h

// 进程为资源分配的单位
// 保存线程共享资源
typedef struct {
    // 页表寄存器
    usize satp;
} Process;

typedef struct {
    // 线程上下文存储的地址
    usize contextAddr;
    // 线程栈底地址
    usize kstack;
    // 所属进程
    Process process;
} Thread;

由于 CPU 调度的基本单位是线程，进程只起到资源分配的作用，所以我们主要还是关注用户线程的创建。

2、创建用户线程上下文

// kernel/thread.c

/*
 * 创建新的用户线程上下文，并将线程上下文入栈
 * 借助中断恢复机制进行线程的初始化工作，即从中断恢复结束时即跳转到sepc，就是线程的入口点
 * 输入：线程入口点；用户线程栈顶；内核线程线程栈顶；内核线程页表
 * 输出：线程上下文地址
*/
usize
newUserThreadContext(usize entry, usize ustackTop, usize kstackTop, usize satp)
{
    InterruptContext ic;
    ic.x[2] = ustackTop;            // 设置sp寄存器为用户栈顶
    ic.sepc = entry;                // 中断返回地址为线程入口点
    ic.sstatus = r_sstatus();
    // 设置返回后的特权级为 U-Mode
    ic.sstatus &= ~SSTATUS_SPP;
    // 异步中断使能
    ic.sstatus |= SSTATUS_SPIE;
    ic.sstatus &= ~SSTATUS_SIE;
    // 创新新线程上下文
    ThreadContext tc;
    // 借助中断的恢复机制，来初始化新线程的每个寄存器，从 Context 中恢复所有寄存器
    extern void __restore(); tc.ra = (usize)__restore;
    tc.satp = satp;         // 设置页表
    tc.ic = ic;
    return pushContextToStack(tc, kstackTop);
}

3、用户线程结构

// kernel/consts.h

/*
 * 创建新的用户线程
 * 创建内核栈，创建上下文
*/
Thread
newUserThread(char *data)
{
    // 新建用户进程页映射, data为指向 ELF 文件的首字节的指针
    Mapping m = newUserMapping(data);
    usize ustackBottom = USER_STACK_OFFSET;                 // 用户栈底
    usize ustackTop = USER_STACK_OFFSET + USER_STACK_SIZE;  // 用户栈顶
    // 将用户栈映射到未被分配物理内存的段(添加到页表上、分配物理页映射)
    Segment s = {ustackBottom, ustackTop, 1L | USER | READABLE | WRITABLE};
    mapFramedSegment(m, s);

    // 构建用户线程的内核栈
    usize kstack = newKernelStack();
    usize entryAddr = ((ElfHeader *)data)->entry;
    Process p = {m.rootPpn | (8L << 60)};   // 构造进程（根页表地址，mode为sv39）
    // 创建新的用户线程上下文
    usize context = newUserThreadContext(
        entryAddr,                      // 线程入口点
        ustackTop,                      // 用户线程栈顶
        kstack + KERNEL_STACK_SIZE,     // 内核线程线程栈顶
        p.satp                          // 内核线程页表
    );
    Thread t = {context, kstack, p};    // 线程上下文地址，线程栈底地址，所属进程
    return t;
}

用户栈被固定在虚拟地址空间中的一个固定的位置，不要忘了这片区域也需要被设置到页表中，权限设置为可读可写，并且设置 USER 标志位。
用户程序所在的线程也需要处理中断等，需要进入 S-Mode，所以也需要建立一个内核栈。
映射用户栈使用的函数 mapFramedSegment() 用于映射一块还没有分配物理内存的虚拟地址空间，会在映射的过程中直接通过 allocFrame() 分配。

// kernel/mapping.c

// 映射一个未被分配物理内存的段
void
mapFramedSegment(Mapping m, Segment segment)
{
    usize startVpn = segment.startVaddr / PAGE_SIZE;        // 起始虚拟页
    usize endVpn = (segment.endVaddr - 1) / PAGE_SIZE + 1;  // 结束虚拟页
    usize vpn;
    for(vpn = startVpn; vpn < endVpn; vpn ++) {
        // 根据给定的虚拟页号寻找三级页表项
        PageTableEntry *entry = findEntry(m, vpn);  
        if(*entry != 0) {
            panic("Virtual address already mapped!\n");
        }
        // 分配一个物理页并设置标志位
        *entry = (allocFrame() >> 2) | segment.flags | VALID;
    }
}

4、万事具备，我们来创建用户线程参与调度。

// kernel/thread.c

void
initThread()
{
    ....
    for(i = 0; i < 5; i ++) {
        ....
    }
    // 创建一个用户线程并添加到 CPU
    extern void _user_img_start();
    Thread t = newUserThread((char *)_user_img_start);
    addToCPU(t);
    printf("***** init thread *****\n");
}

在创建完成 5 个内核线程后，我们创建了一个用户线程，并将其添加到了 CPU，运行一下，用户线程也参与调度了！

所以用户线程真的参与调度了吗？此时我相信所有的同学运行都是报错，根据scause查表可发现报错为Store/AMO access fault，这时我们就要使用GDB调试工具去排查错误了。

这里笔者的意图就是想教会大家真正地去调试代码，而不是全程跟着我的步骤来，所以强烈建议大家使用GDB去发现错误，如果实在解决不了再下面翻找答案。
具体调试步骤：
1. 我们在exterm vpod _user_img_start新增代码中打上断点，c运行到该断点处
2. 然后通过s跳转进去，再使用单步n运行，发现newUserMapping函数会触发异常
3. 再从头来，使用s跳转进newUserMapping函数，然后单步n运行，如此反复，最后可以定位到报错的最底层函数调用在kernel/memory.c文件的allocFrame函数中，原因是我们此时已经进行了虚拟地址映射，在清空分配区域时需要使用虚拟地址索引

修改如下：

// kernel/memory.c

usize
allocFrame()
{
    usize start = alloc() << 12;
    int i;
    /*
     * 清空被分配的区域
     * 这里访问需要通过虚拟地址
     */
    char *vStart = (char *)(start + KERNEL_MAP_OFFSET);
    for(i = 0; i < PAGE_SIZE; i ++) {
        vStart[i] = 0;
    }
    return (usize)start;
}

至此，我们可以正确将用户线程参与调度了！输出如下：

==== Init Interrupt ====
***** Init Memory *****
***** Remap Kernel *****
***** init thread *****

>>>> will switch_to thread 0 in idle_main!
Begin of thread 0
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
End of thread 0
Thread 0 exited, exit code = 0
<<<< switch_back to idle in idle_main!

>>>> will switch_to thread 1 in idle_main!
Begin of thread 1
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
End of thread 1
Thread 1 exited, exit code = 0
<<<< switch_back to idle in idle_main!

>>>> will switch_to thread 2 in idle_main!
Begin of thread 2
2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222<<<< switch_back to idle in idle_main!

>>>> will switch_to thread 3 in idle_main!
Begin of thread 3
33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
End of thread 3
Thread 3 exited, exit code = 0
<<<< switch_back to idle in idle_main!

>>>> will switch_to thread 4 in idle_main!
Begin of thread 4
44444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444
End of thread 4
Thread 4 exited, exit code = 0
<<<< switch_back to idle in idle_main!

>>>> will switch_to thread 5 in idle_main!