RISC-V assembly

There is a file user/call.c in your xv6 repo. make fs.img compiles it and also produces a readable assembly version of the program in user/call.asm.

我们启动qemu可以看到有call.c文件，执行make fs.img可以生成汇编文件

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

#include "kernel/param.h"
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int g(int x) {
  return x+3;
}

int f(int x) {
  return g(x);
}

void main(void) {
  printf("%d %d\n", f(8)+1, 13);
  exit(0);
}

Which registers contain arguments to functions? For example, which register holds 13 in main's call to printf?

那几个寄存器保存了函数的参数，例如main函数里面那个寄存器保存了printf的入参13这个值

1
2
3
4
5
6
7

void main(void) {
  1c:	1141                	addi	sp,sp,-16
  1e:	e406                	sd	ra,8(sp)
  20:	e022                	sd	s0,0(sp)
  22:	0800                	addi	s0,sp,16
  printf("%d %d\n", f(8)+1, 13);
  24:	4635                	li	a2,13

从上面可以看出li a2,13 。将13加载到了a2寄存器中，从下图中可以看出，a2寄存器一般是用来传递函数的参数的

Where is the call to function f in the assembly code for main? Where is the call to g? (Hint: the compiler may inline functions.)

没有这样的代码。 g(x) 被内链到 f(x) 中，然后 f(x) 又被进一步内链到 main() 中

# Memory bound algorithms

获取数据有时比计算的开销更大：

带宽和时延

什么样的运输受限于访存

以稠密矩阵的计算为例

Speed up system calls

一些操作系统 (e.g., Linux)通过在只读的区域共享用户空间和内核态空间的数据加速特定的系统调用。这种方法可以减少系统调用需要不断跨越用户态和内核态的需求T. To help you learn how to insert mappings into a page table, your first task is to implement this optimization for the getpid() system call in xv6.

1
2
3
4
5
6

int
ugetpid(void)
{
  struct usyscall *u = (struct usyscall *)USYSCALL;//获得USYSCALL的页把它转为一个结构体指针
  return u->pid;
}

当每个process被创建的时候, 在USYSCALL (a VA defined in memlayout.h)映射一个只读page . 在页的开头, store a struct usyscall (also defined in memlayout.h), and initialize it to store the PID of the current process.

1
2
3
4
5
6

#define TRAPFRAME (TRAMPOLINE - PGSIZE)
#ifdef LAB_PGTBL
#define USYSCALL (TRAPFRAME - PGSIZE)
struct usyscall {
  int pid;  // Process ID
};

For this lab, ugetpid() has been provided on the userspace side and will automatically use the USYSCALL mapping.

从上面可以看出应该是TRAPFRAME在TRAMPOLINE下面一页，USYSCALL在TRAPFRAME往下一页的位置

• You can perform the mapping in proc_pagetable() in kernel/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
32
33
34
35
36
37

 //给进程分配了一个页表
// An empagetable_t
proc_pagetable(struct proc *p)
{
  pagetable_t pagetable;

  // An empty page table.
  pagetable = uvmcreate();
  if(pagetable == 0)
    return 0;

  // map the trampoline code (for system call return)
  // at the highest user virtual address.
  // only the supervisor uses it, on the way
  // to/from user space, so not PTE_U.
  if(mappages(pagetable, TRAMPOLINE, PGSIZE,
              (uint64)trampoline, PTE_R | PTE_X) < 0){
    uvmfree(pagetable, 0);
    return 0;
  }

  // map the trapframe just below TRAMPOLINE, for trampoline.S.
  if(mappages(pagetable, TRAPFRAME, PGSIZE,
              (uint64)(p->trapframe), PTE_R | PTE_W) < 0){
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
  }
    //map the usyscall
   if(mappages(pagetable, USYSCALL, PGSIZE,
              (uint64)(p->usyscall), PTE_R | PTE_U) < 0){
    uvmunmap(pagetable, USYSCALL, 1, 0); //如果失败取消映射并释放页
    uvmfree(pagetable, 0);
    return 0;
  }
  return pagetable;
}

我们从上面的函数中可以看到trampoline code和trapframe的映射过程，我们的目标是通过模仿这两个的过程实现对USYSCALL的映射。

写在前面： 因为对C++ 17的特性不太了解，写的很痛苦,感觉对C++的智能指针，模板等新特性有了更深入的了解，收获颇多。

实验官网链接

task1：Copy-On-Write Trie

一开始的树节结构是一个前缀树的结构（详见数据结构与算法前缀树的笔记）

修改 trie.h 和 trie.cpp来实现copy-on-write trie. 什么是 copy-on-write trie？对树的操作不需要直接修改原来的树节点，而是创建新的节点并返回新的root节点。例如插入：("ad", 2) ，先创建一个新的节点： Node2 ，NODE2会重用原来树的孩子节点，返回新的根节点

插入 ("a", "abc") 并且移除("ab", 1)：

尝试完成三种操作

• Get(key): 获取key对应的value值

• Put(key, value): 设置key对应的value值.如果key值已经存在则覆盖. Note that the type of the value might be non-copyable (i.e., std::unique_ptr<int>). This method returns a new trie.

  在 C++ 中，有一些类型是不允许直接进行复制的，而是通过移动或者转移所有权的方式来操作。std::unique_ptr 就是这样的一个例子。它表示一个独占所有权的指针，意味着同一时刻只有一个指针可以拥有它所指向的资源。由于其独占性质，它不允许直接进行复制，而是通过移动（move）操作来传递所有权。

• Delete(key): Delete the value for the key. This method returns a new trie.

SIMD

SIMD Processing (Single instruction, multiple data (SIMD))

它描述了具有多个处理元素(multiple processing elements)的计算机，可以在多个数据点(data points)上同时(simultaneously)完成相同的操作。

不是所有的算法都可以容易地被向量化.

硬件架构

一个cycle有两个FMA单元，一个store单元

trace

在 usys.pl 中，有用户态到内核态的跳板函数：

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

# user/usys.pl

entry("fork");
entry("exit");
entry("wait");
entry("pipe");
entry("read");
entry("write");
entry("close");
entry("kill");
entry("exec");
entry("open");
entry("mknod");
entry("unlink");
entry("fstat");
entry("link");
entry("mkdir");
entry("chdir");
entry("dup");
entry("getpid");
entry("sbrk");
entry("sleep");
entry("uptime");
entry("trace");  # HERE

这个脚本在运行后会生成 usys.S 汇编文件，里面定义了每个 system call 的用户态跳板函数：

1
2
3
4

trace:		# 定义用户态跳板函数
 li a7, SYS_trace	# 将系统调用 id 存入 a7 寄存器
 ecall				# ecall，调用 system call ，跳到内核态的统一系统调用处理函数 syscall()  (syscall.c)
 ret

项目代码中系统调用流程：

1
2
3
4
5

user/user.h:		用户态程序调用跳板函数 trace()
user/usys.S:		跳板函数 trace() 使用 CPU 提供的 ecall 指令，调用到内核态
kernel/syscall.c	到达内核态统一系统调用处理函数 syscall()，所有系统调用都会跳到这里来处理。
kernel/syscall.c	syscall() 根据跳板传进来的系统调用编号，查询 syscalls[] 表，找到对应的内核函数并调用。
kernel/sysproc.c	到达 sys_trace() 函数，执行具体内核操作

系统调用实现函数都是不带参数的，实际上系统调用传入的参数会被放在当前的寄存器中，通过kernel/syscall.c文件中的argint,argaddr,argstr等函数能够获取到

bug2： 测试trace 2147483647 grep hello README的时候不显示trace的系统调用

主要的问题出在，调用trace的时候执行到打印的时候可以看出mask没有传进来比较滞后还是0。

项目背景

为了提高MySQL数据库（基于客户端服务端模型）的访问瓶颈

策略一：减小磁盘的IO。

• 在服务器端增加缓存服务器缓存常用的数据（例如redis）

• 可以增加连接池，来提高MySQL Server的访问效率。

  在高并发情况下，大量的TCP三次握手、MySQL Server连接认证、MySQL Server关闭连接回收资源和TCP四次挥手所耗费的性能时间也是很明显的，增加连接池就是为了减少这一部分的性能损耗。

本项目就是为了在C/C++项目中，提高MySQL Server的访问效率，实现基于C++代码的数据库连接池模块。

什么是连接池

数据库连接池的解决方案是在应用程序启动时建立足够的数据库连接，并讲这些连接组成一个连接池，由应用程序动态地对池中的连接进行申请、使用和释放。对于多于连接池中连接数的并发请求，应该在请求队列中排队等待。并且应用程序可以根据池中连接的使用率，动态增加或减少池中的连接数。

连接池一般包含了数据库连接所用的ip地址、port端口号、用户名和密码以及其它的性能参数，例如初始连接量，最大连接量，最大空闲时间、连接超时时间等。

初始连接量（initSize）：表示连接池事先会和MySQL Server创建initSize个数的connection连接，当应用发起MySQL访问时，不用再创建和MySQL Server新的连接，直接从连接池中获取一个可用的连接就可以，使用完成后，并不去释放connection，而是把当前connection再归还到连接池当中。

最大连接量（maxSize）：当并发访问MySQL Server的请求增多时，初始连接量已经不够使用了，此时会根据新的请求数量去创建更多的连接给应用去使用，但是新创建的连接数量上限是maxSize，不能无限制的创建连接，因为每一个连接都会占用一个socket资源，一般连接池和服务器程序是部署在一台主机上的，如果连接池占用过多的socket资源，那么服务器就不能接收太多的客户端请求了。当这些连接使用完成后，再次归还到连接池当中来维护。

linux 0.11内存管理

线性地址空间的格局

每个线程的虚拟地址空间并不重叠，每个进程不跨越自己的空间。如何防止进程跨越64M的空间进行非法访问？

非法跨越进程边界有两种情况：

• 一个进程非法跨越到内核

• 一个进程非法跨越到另一个进程

非法跨越问题

如何防止进程跨越到内核的非法访问

通过cpu硬件禁止从3特权级跳转到0特权级。通过设置LDT,GDT设定了特权级。进程能否自己修改LDT,GDT?不能，因为这两个都在内核数据段，是0特权级，进程无法访问。那进程能不能自己建一个LDT,GDT狸猫换太子？也不能，因为运行的时候CPU只将GDTR和LDTR寄存器指向的数据结构认定为LDT,GDT，进程自己没法伪造。而LDTR和GDTR是0特权级的进程没法把自己伪造的挂上去。

在寻址过程中我们会对这一内容做一个总结。详见下面的寻址章节。

linux0.11缓冲区设计解读

在之前的笔记中，我们已经零散的介绍了缓冲区的相关设计。这里我们系统的总结linux0.11关于缓冲区的相关设计

缓冲区：高速缓冲区位于内核代码块和主内存区之间

缓冲区的作用与设计原则

首先，我们需要考虑，我们为什么需要缓冲区，在什么情况下缓冲区可以没有。

缓冲区：开一块内存，磁盘内容先读到缓冲区，在缓冲区读到内存

缓冲区的优势：

1.块设备的统一集散地，使得操作系统设计更方便，更灵活

2.对块设备的文件操作运行效率更高

前提：从内存读比从磁盘读快200倍

Linux 0.11中断机制解读

在bios启动的时候首先使用的是bios自带的中断服务函数，int 0x13和int 0x19。

在setup.s里面关中断：将EFLAGS置为0。setup将head.s和内核代码搬运到0x0000开始的地址处，覆盖了原BIOS的中断函数部分，废除了BIOS的中断函数机制。故事就从这里开始。

与中断相关的标志位：iF 中断许可（第 9 位）

中断服务函数挂接

外部中断、软件中断和异常是通过中断描述符表（IDT）处理的。 IDT 中包含访问中断和异常处理程序的门描述符的集合。像 GDT 一样，IDT 不是一个段， IDT 的线性基地址包含在 IDT 寄存器中（IDTR）。

异常处理类中断服务函数

trap_init();函数把中断异常处理服务程序与IDT进行挂接

将异常处理函数插入IDT的表项是由set_trap_gate（）和set_system_gate（）函数来完成的