rCore-OS Lab5: Process

Lab5: Process

0x00 The Concepts and Syscalls

It’s hard to define what a process is. Usually it is a procedure in which the OS selects an executable file and performs the dynamic execution. During the execution there will be many interaction between the process and the hardware or virtual resources, and we know those are handled by the OS through syscalls. Besides, there are some important syscalls specially made for process management: fork/exec/waitpid:

  • fork: When a process (let’s name it A) call fork, the kernel will create a new process (let’s name it B) which is almost identical to A: they have exactly same stack, .text segment or other data segment content, and every registers except a0 which stores the return value of the syscall. They are in different address spaces but the bytes stores in these address space are exactly same at the moment fork returns. The only way a process can figure out whether it is the new process or the old parent is the returen value of fork: 0 for the new born process and pid of child process for the parent. This parent-child relation is very important in unix-like OS.
  • exec: This will help us run a new program in the current address space, use it together with fork we can easily create a process that runs a new program.
  • waitpid: When a process returns, the memory resources it have consumed cannot be fully recycled through the exit syscall, for eaxmple the current kernel stack. A typical solution for this is to mark the process as zombie, then it’s parent process do the rest recycle work and get the exit status through the waitpid syscall.

0x01 Data Structures for Process

RAII is heavily used to help us safe memory management. For a process, we bind its pid, kernel stack, and address space(MemorySet) to a TaskControlBlock. The TCBs ares stored in a tree formed by the parent-child relations(created through fork&exec) between processes:

pub struct TaskControlBlock {
    // immutable
    pub pid: PidHandle,
    pub kernel_stack: KernelStack,
    // mutable
    inner: UPSafeCell<TaskControlBlockInner>,
}

pub struct TaskControlBlockInner {
    pub trap_cx_ppn: PhysPageNum,
    pub base_size: usize,
    pub priority: usize,
    pub pass: usize,
    pub task_cx: TaskContext,
    pub task_status: TaskStatus,
    pub memory_set: MemorySet,
    pub parent: Option<Weak<TaskControlBlock> >,
    pub children: Vec<Arc<TaskControlBlock> >,
    pub exit_code: i32,
}

Here we use alloc::sync::Weak to wrap the parent pointer so that there will be no cyclic refernces between the parent and it’s child.

Another significant modification from previous chapter is that we split the original task manager module into Processor and TaskManager.
– The Processor module maintains the CPU’s states, including current process and idle task context. In a single-core CPU environment, we only create one gloable instance of Processor.
– The TaskManager stores all Arcs in a BTreeMap, so that we can easily fetch/remove or add/insert tasks(processes) with our scheduler.

pub struct TaskManager {
    ready_queue: BTreeMap<usize, Arc<TaskControlBlock>>,
    scheduler: Box<Scheduler>,
}

impl TaskManager {
    pub fn new() -> Self {
        let stride_scheduler: Scheduler = Scheduler::new();
        Self {
            ready_queue: BTreeMap::new(),
            scheduler: Box::new(stride_scheduler),
        }
    }

    pub fn add(&mut self, task: Arc<TaskControlBlock>) {
        // update pass for stride scheduler
        let mut task_inner = task.inner_exclusive_access();
        task_inner.pass += BIG_STRIDE / task_inner.priority;
        drop(task_inner);
        self.scheduler.insert_task(task.getpid(), task.clone().inner_exclusive_access().pass);
        self.ready_queue.insert(task.getpid(), task);
    }

    pub fn fetch(&mut self) -> Option<Arc<TaskControlBlock>> {
        let next_pid = loop {
            if let Some(next_pid) = self.scheduler.find_next_task() {
                // TODO how about wait state
                if self.ready_queue.contains_key(&next_pid){
                    break next_pid
                }
            } else {
                return None;
            }

        };
        let (_, task) = self.ready_queue.remove_entry(&next_pid).unwrap();
        Some(task)
    }
}

0x02 Process Management

继续阅读“rCore-OS Lab5: Process”

rCore-OS Lab4: Address Space

Lab4: Address Space

Address Space is a significant mechanism in modern operating system. By adding an abstract layer between code and physical memory, it frees the developers from the painful memory arrangement work, helping them focus more on their code other than the hardware stuff.

The following figure gives an overview of how Address Space works:

Having Address Space enabled, the codes can only see the Virtual Address. If a process wants to access any address virt_addr, it will be first translated to Physical Address by CPU’s MMU module according to the process’s page table.

0x00 Hardware supports for Multilevel Paging in RISCV

The MMU is disabled by default, thus previously any program are able to access any physical memory. We can enbale the MMU by setting a register named satp:

The above figure shows the meaning of bits in satp:

  • MODE controls how the MMU translate address. When MODE = 0 the MMU is disabled, and when ‘MODE’ = 8 the MMU use page table mechanism to translate the address.
  • ASID indetifies the address space by id, since we don’t have process implemented yet we just ignore it.
  • PPN is the physical page number of the root page table entry.

The address format under page table mechanism consists of two parts: page number and offset:

Each page table entry consists of 3 level virtual page number (vpn) and several flag bits:

With these knowledge we can easily understand how the MMU translates virtual memory address:

TLB

TLB (Translation Lookaside Buffer) works like some kinds of cache, note that we have to use sfence.vma instruction to refresh it after we change satp or any page table entry.

0x01 Address Space of Kernel and User

After satp is enabled, the memory of kernel and user applications are seperated, we need to carefully handle the interaction between different address spaces. In rCore, the designers use a Trampoline to bridge the kernel and usermode applications:

The virtual address of Trampoline is exactly same across each user spaces and the kernel space. Note that there is a guard page between kernel stacks. Those holes in the address space are settled to prevent buffer overflow damage in kernel stack.

The address space of the kernel is illustrated in the following figure:

The permissions here are critical for system security: no page table can be both writable and executable. Besides, we use identical mapping here, so the kernel can read/write any user space memory in an easy way.

In user mode, the address space is quite familiar to us:

We palce the TrapContext just under the Trampoline.

0x02 Multi-tasking with Address Space

__all_traps and trap_return shoud take care of the address space switch. Note that for each task, we should set their TaskContext’s initial ra to trap_return. We don’t have the ra pushed in kernel stack for the first time to run a task so we have to handle this manually.

The syscall call stack is:

syscall: user space ecall -> __all_traps(trampoline) -> trap_handler -> do syscall -> trap_return -> __restore -> user space

The switch process is:
继续阅读“rCore-OS Lab4: Address Space”

Intel SGX: 基本概念

SGX是Intel实现的可信执行环境,主要面向服务器和桌面端,提供了内存加密(Memory Encryption)、访问控制(Access Control)、远程认证(Remote Attestation)、本地密封(Sealing)等功能。

0x00 Overview

关于应用程序代码与可信执行环境的基本关系:

  1. 每个application分为两部分:安全(可信)部分和不安全(不可信)的部分
  2. application启动后,会在受保护的可信内存中加载一块飞地(enclave)
  3. application通过把机密数据、代码放到enclave里来保证安全性
  4. enclave为application提供调用接口,当application调用enclave内的函数时,其内部的任何内存仅enclave自身可见
  5. enclave内存即使ring 0的攻击者也看不到,因为是CPU层面的保护。实际上在SGX的安全模型里OS、BIOS等等都可以被认为是不可信的

关于可信执行环境与用户进程的关系:

  1. application 本身包括了自身的代码、数据和enclave
  2. enclave里面也有其自身的代码、数据
  3. SGX保证enclave里面的代码和数据的integrity和confidentiality
  4. enclave的entry points在编译期就确定了
  5. enclave可以访问它所在的application里的内存,但是反过来不行
  6. 支持多线程


继续阅读“Intel SGX: 基本概念”

rCore-OS Lab2: Batch Processing and Privileges

In lab 1, we have made our code work on a bare-metal computer (simulated by QEMU) successfully. However, it can do nothing but print some strings we hardcoded in the program on the terminal. Of course you can make it more complicated, such as factoring a large number, calculating the inverse of a matrix, etc. That’s cool but there are two significant drawbacks of this approach:

  1. The CPU runs a single program each time. Since the computing resources are precious(especially in the old time when you don’t have a modern OS), users who have many programs to run have to wait in front of the computer and manually load&start the next program after the previous one finished.
  2. Nobody wants to write the SBI and assembly level stuff every time, and it’s a duplication of efforts.

In order to solve these problems, people invented the Simple Batch Processing System, which can load a batch of application programs and automatically execute them one by one. Besides, the Batch Processing System will provide some “library” code such as console output functions which may be reused by many programs.

A new problem arises when we use the batch process system: error handling. The user’s program may (often) run into errors, unconsciously or intentionally. We do not want the error of any program to affect others or the system, so the system should be able to handle these errors and terminate the programs when necessary. To achieve this goal we introduced the Privileges mechanism and isolate user’s code from the system, which we will refer to as user mode and kernel mode. Note that this mechanism requires some support from hardware, and we will illustrate that with code in the following parts.

0x00 Privileges mechanism

The underlying reason for implementing the privileges mechanism is the system cannot trust any submitted program. Any errors or attacks could happen and may corrupt the system. We have to restrict users’ programs in an isolated “harmless” environment, where they have no access to 1) arbitrary memory or 2) any over-powerful instructions which may break the computer. In this lab, we mainly focus on the last point.

Prohibiting users’ program from using privileged instructions need the help from CPU. In riscv64, 4 levels of privileges are designed:

Level Encode Name
0 00 U, User/Application
1 01 S, Supervisor
2 10 H, Hypervisor
3 11 M, Machine

All modes, except Machine, have to go through binary interfaces provided by higher levels to control the hardware. The privileges level and their relation in our scenario are shown in the following figure:

The binary interfaces between User mode and Supervisor mode are named Application Binary Interface (ABI), or another more famous one: syscall.
继续阅读“rCore-OS Lab2: Batch Processing and Privileges”

公式识别Web端更新 21.11.09

最近有一些同学反映他们需要大量使用识别工具,但由于种种原因不想或者不能在自己电脑上装客户端,希望能将第三方API集成到Web端。

这个功能我很早就有意识到有需求,但是我还是比较想让大家用MathpixCsharp,因为Web端不支持快捷键,而我个人认为快捷键对于生产力来说非常重要,没有的话体验会很差。但是由于最近我女朋友换了Mac电脑,我意识到有很多MacOS的同学目前是没有办法用MathpixCsharp的,所以我就打算先把这个功能加到Web端,满足更多平台同学的需求。

昨晚抽空先糊了一个勉强能用的界面提供了这项功能,使用示例参考下图:

payLatex.gif

基本的使用方式跟原来的免费接口是一样的,使用截图工具将要识别的公式截取之后在Web页面粘贴即可。可以参考原版的介绍文章

新增的付费接口的使用方法

  1. 这个网站购买卡密
  2. 在网页中点选 第三方付费接口
  3. 将得到的卡密中的APP_IDAPP_KEY分别填入网页中提示填写的两个文本框内
  4. 然后截图+粘贴使用即可

其中Uses会显示当前卡密的剩余使用次数。

有任何疑问都可以仔细阅读MathpixCsharp的介绍:https://itewqq.cn/mathpixcsharp-opensource-windows-client/ 和免费版Web app的介绍https://itewqq.cn/image-to-latex-convert-app/

新的版本是临时糊出来的,比较粗糙,有各种问题、意见、建议都欢迎大家到github提issues:https://github.com/itewqq/MathF/issues

另:由于我的前端优化和审美UI设计能力几乎为0,所以如果您对于前端界面有自己的想法,也可以直接修改代码( https://github.com/itewqq/MathF/blob/master/index.html ),欢迎PR!

[DP][扫描线][思维] Codeforces 1313D Happy New Year

题目链接

题意:

有 $m$ 个小朋友,圣诞老人有 $N$ 个咒语,第 $i$ 个咒语施展出来的话,可以给 $[Li,Ri]$ 范围内的小朋友一块糖果,对每个小朋友来说,他得到的糖如果是奇数的话就会happy,否则就会不happy。

现在要求求出当圣诞老人采取某种最优的施展咒语的策略(一些用了一些没用,具体不需要求出来)的时候,最多有多少个小朋友可以happy?

题目保证,每个小朋友最多被 k 个咒语覆盖到。

数据范围: $m \le 10^9$, $N \le 10^5$, $1 \le k \le 8$, $1 \le Li \le Ri \le m$

题解:

(先吐槽下这题竟然2600分,这可是个div2D)

用扫描线的思想来做。

假设有一根竖直的扫描线在横轴上扫过去,那么他只会在每个 $[Li,Ri]$ 段的头尾两端发生状态变化,我们设置这些点为关键点,当我们采取某种特定的策略的时候,两个关键点之间的数据是不会发生变化的。

由于每个点最多被 $k$ 个线段覆盖,我们可以暴力的枚举出来当前扫描到的点的状态,即它被多少种线段覆盖到了,这个状态显然可以用二进制位来表示。由于我们是一个一个关键点找过去的,而两个关键点之间的数据状态仅由前一个点即可确定,所以我们的dp转移只需要考虑前一个点。

具体的转移:设 $dp[i][S]$ 为考虑到了第i个关键点(按从小到大的顺序),覆盖当前点的线段状态为 $S$ 的时候,最优解是多少。

  1. 当当前点为某线段的起点时,我们考虑每个 $S$ 中是否包含了第 $i$ 条线段,如果
    • 包含了,那么 $dp[i][S]=dp[i-1][S^(1<<p)]+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$ ,因为我们相当于加上了新的一段;(其中p为当前线段所应在的二进制位,下同)
    • 没包含,那么$dp[i][S]=dp[i][S]$ $+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$,等于说我们的扫描线在这一段仍然是按照之前的状态在扫描。
  2. 当当前点为某线段的终点时,我们仍然考虑每个 $S$ 中是否包含了第 $i$ 条线段,如果
    • 包含了,由于这条线段到此我们认为结束了,所以这种状态根本不合法,直接设置为$-INF$
    • 没包含,那么$dp[i][S]=max(dp[i-1][S],dp[i-1][S^(1<<p)])$ $+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$,因为我们前面一段可能选了大,也可能不选更大,我们需要取个最优解。

然后我们可以发现两个转移都有方向性,我们可以用滚动数组忽略掉第一维,也就是说状态数组可以只开 $dp[1<<8]$ 即可。

继续阅读“[DP][扫描线][思维] Codeforces 1313D Happy New Year”

MathpixCsharp: C#实现的Mathpix Windows开源客户端

21.3.28: 第三方Api支付服务已修复。

不填appid和appkey是没法用的

不填appid和appkey是没法用的

不填appid和appkey是没法用的

👆强调一下,因为最近没有看使用说明就来跟我说用不了的人太多了。要么注册官方的开发者api,要么使用第三方的api和key。

github地址 https://github.com/itewqq/MathpixCsharp

应该不会有外国用户所以就只写中文README了(雾)

demo1.gif

功能支持:

  • [x] 截图识别公式转换为Latex代码
  • [x] 截图识别公式转换为Office Word公式
  • [x] 多显示器支持
  • [x] 最小化到系统托盘
  • [x] 快捷键截图,Ctrl+Alt+M(与官方客户端相同)
  • [x] 官方API支持,每个月可免费用1000次,需要国外信用卡
  • [x] 无需信用卡的第三方API支持

客户端安装:

使用安装包:

下载最新的安装包,解压之后双击Setup.exe,按照提示走即可安装好MathpixCsharp。

不能正常从github下载的点这里走网盘

链接:https://pan.baidu.com/s/10lzjMhyiB-wv7PSyDa2BTQ
提取码:hkfb

如果链接失效请留言我知乎账号谢谢 🙂
继续阅读“MathpixCsharp: C#实现的Mathpix Windows开源客户端”

[娱乐] 一个监控NIKE官网NBA球衣打折的QQ机器人

上次写的微信版机器人的爬虫已经失效了,这次重新搞了爬虫,平常用的qq比较多所以也换成了qq版。

需要准备:

  • Windows服务器一台,阿里云ECS即可(Linux也可以但是需要Wine,不如直接原生Windows)
  • QQ小号一个,用来作为发送消息的载体

首先到coolq的社区下载最新版的coolq air,图灵版或者小i版都行,无所谓,我们不会用到他们的ai。
继续阅读“[娱乐] 一个监控NIKE官网NBA球衣打折的QQ机器人”

JetBrains Quest 免费领取三个月全家桶 解密

首先看官推给出的这串代码

48 61 76 65 20 79 6f 75 20 73 65 65 6e 20 74 68 65 20 73 6f 75 72 63 65 20 63 6f 64 65 20 6f 66 20 74 68 65 20 4a 65 74 42 72 61 69 6e 73 20 77 65 62 73 69 74 65 3f

看上去是十六进制,猜测是ASCII,转码一下试试

得到了

Have you seen the source code of the JetBrains website?

那么根据提示我们来到jetBrains的官网看源代码,就找到了如下注释:

      O
{o)xxx|===============-
      O

Welcome to the JetBrains Quest.

What awaits ahead is a series of challenges. Each one will require a little initiative, a little thinking, and a whole lot of JetBrains to get to the end. Cheating is allowed and in some places encouraged. You have until the 15th of March at 12:00 CET to finish all the quests.
Getting to the end of each quest will earn you a reward.
Let the quest commence!

JetBrains has a lot of products, but there is one that looks like a joke on our Products page, you should start there... (hint: use Chrome Incognito mode)
It’s dangerous to go alone take this key: Good luck! == Jrrg#oxfn$

                 O
-===============|xxx(o}
                 O

看到了hint说使用Chrome的无痕模式,那我们无痕模式打开一下Products 页面。顺便,注意他的一句话:带上这个key Good luck! == Jrrg#oxfn$
继续阅读“JetBrains Quest 免费领取三个月全家桶 解密”

[数学] 向量函数的雅可比矩阵与链式法则

复习一下我的数学知识T_T

1. 回顾高等数学:多元数量函数的梯度

回想高等数学中常见的多元数量函数$f:\mathbb{R}^{n}\rightarrow \mathbb{R}^{1}$,我们可以把他的输入当作一个向量 $\bf{x}\in \mathbb{R}^{n}$,输出$y=f(\bf{x})\in \mathbb{R}^{1}$是一个数字。那么由高数的知识我们知道$f$的梯度定义为
$$
\nabla f_{\boldsymbol{x}} \overset{\underset{\mathrm{def}}{}}{=} \left[ \frac{\partial f }{\partial x_1}, \frac{\partial f }{\partial x_2},\cdots,\frac{\partial f }{\partial x_n} \right]=\frac{\partial f }{\partial \boldsymbol{x}}
$$

有了上式,我们还可以写出全微分的向量化表示

\[
\begin{aligned}
df &= \frac{\partial f}{\partial x_1}dx_1+\frac{\partial f}{\partial x_2}dx_2+\cdots+\frac{\partial f}{\partial x_n}dx_n \\
&=\left[ \frac{\partial f }{\partial x_1}, \frac{\partial f }{\partial x_2},\cdots,\frac{\partial f }{\partial x_n} \right] \left[dx_1, dx_2,\cdots,dx_n \right]^T \\
&=\frac{\partial f }{\partial \boldsymbol{x}} d\boldsymbol{x}
\end{aligned}
\]

接下来我们将其推广到向量函数。向量函数的“梯度”其实就是雅可比矩阵
继续阅读“[数学] 向量函数的雅可比矩阵与链式法则”