Computer Architecture

Overview

von Neumann architecture

1. An electronic digital computer with these components:

   • Processor unit: arithmetic unit and processor registers
   • control unit: instruction register(IR) and program counter(PC)
   • Memeory
   • External mass storage
   • Input and Output mechanisms

2. Instructions and data are stored in memory with equal status.

3. Instructions is composed of Opcode and ddress code, the address code is used to point Operand.

The term “von Neumann architecture” has evolved to refer to any stored-program computer in which an instruction fetch and a data operation cannot occur at the same time (since they share a common bus)

Privilege level Switch

System call and Function call

Overview

• Function call is running in user mode, using the user source, and there is no need for privilege switching and context restoring.
• System call is the request from user mode to higher privilege mode, for getting into system to use kernel source such as I/O device, network interface.

System call

System call is the ABI(Application Binary Interface), which provide interface for U mode to use OS source. The follow is the process of system call:

1. The user program prepares for system call by loading the system call number and the arguments that needed in predefined registers(a7: system call number, a0~a6: Hold arguments of system call, a0 also hold the return value from the system call)
2. After that, user program issue the ecall instruction. After the ecall executed, a trap occurs, and the trap context switch performs. The CPU transfers control to the operating system’s trap handler. The trap handler use the sscause and system call number in a7 to execute requested system call. Once the system call is completed, the return value (if any) is placed in register a0.
3. Finally, restore user context to return user mode.

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

.section .data
message:
    .asciz "Hello, World!\n"

.section .text
.globl _start
_start:
    # System call to write
    li a7, 64          # Load system call number for 'write' (64) into a7
    li a0, 1           # File descriptor 1 (stdout) into a0
    la a1, message     # Load address of message into a1
    li a2, 14          # Message length (14 bytes) into a2
    ecall              # Issue the system call

    # System call to exit
    li a7, 93          # Load system call number for 'exit' (93) into a7
    li a0, 0           # Exit code 0 into a0
    ecall              # Issue the system call

ASIDE: WHY SYSTEM CALLS LOOK LIKE PROCEDURE CALLS

You may wonder why a call to a system call, such as open() or read(), looks exactly like a typical procedure call in C; that is, if it looks just like a procedure call, how does the system know it’s a system call, and do all the right stuff? The simple reason: it is a procedure call, but hidden inside that procedure call is the famous trap instruction. More specifically, when you call open() (for example), you are executing a procedure call into the C library. Therein, whether for open() or any of the other system calls provided, the library uses an agreed-upon calling convention with the kernel to put the arguments to open in well-known locations (e.g., on the stack, or in specific registers), puts the system-call number into a well-known location as well (again, onto the stack or a register), and then executes the aforementioned trap instruction. The code in the library after the trap unpacks return values and returns control to the program that issued the system call. Thus, the parts of the C library that make system calls are hand-coded in assembly, as they need to carefully follow convention in order to process arguments and return values correctly, as well as execute the hardware-specific trap instruction. And now you know why you personally don’t have to write assembly code to trap into an OS; somebody has already written that assembly for you.

Trap Management

When user program issues the ecall instruction, it trigger the trap execution to switch the processor from user mode to supervisor mode.
Then the first step is to find the trap handler entry address to jump to.
To do this, the kernel set the trap table at boot time.

In rCore, at boot time, trap entry address is set by

1
2
3
4
5
6
7
8
9

/// initialize CSR `stvec` as the entry of `__alltraps`
pub fn init() {
    extern "C" {
        fn __alltraps();
    }
    unsafe {
        stvec::write(__alltraps as usize, TrapMode::Direct);
    }
}

There is only a single trap entry _alltraps. All traps get into _alltraps to do trap context save and load and run different functionality base on what exception was(sscause).

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

/// handle an interrupt, exception, or system call from user space
pub fn trap_handler(cx: &mut TrapContext) -> &mut TrapContext {
    let scause = scause::read(); // get trap cause
    let stval = stval::read(); // get extra value
    match scause.cause() {
        Trap::Exception(Exception::UserEnvCall) => {
            cx.sepc += 4;
            cx.x[10] = syscall(cx.x[17], [cx.x[10], cx.x[11], cx.x[12]]) as usize;
        }
        Trap::Exception(Exception::StoreFault) | Trap::Exception(Exception::StorePageFault) => {
            println!("[kernel] PageFault in application, kernel killed it.");
            run_next_app();
        }
        Trap::Exception(Exception::IllegalInstruction) => {
            println!("[kernel] IllegalInstruction in application, kernel killed it.");
            run_next_app();
        }
        _ => {
            panic!(
                "Unsupported trap {:?}, stval = {:#x}!",
                scause.cause(),
                stval
            );
        }
    }
    cx

Trap context

User Stack and Kernel Stack

Structure

1
2
3
4
5
6
7
8
9
10

/// Trap Context
#[repr(C)]
pub struct TrapContext {
    /// general regs[0..31]
    pub x: [usize; 32],
    /// CSR sstatus      
    pub sstatus: Sstatus,
    /// CSR sepc
    pub sepc: usize,
}

Save and Restore Trap context

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

# os/src/trap/trap.S

.macro SAVE_GP n
    sd x\n, \n*8(sp)
.endm

.align 2
__alltraps:
    csrrw sp, sscratch, sp
    # now sp->kernel stack, sscratch->user stack
    # allocate a TrapContext on kernel stack
    addi sp, sp, -34*8
    # save general-purpose registers
    sd x1, 1*8(sp)
    # skip sp(x2), we will save it later
    sd x3, 3*8(sp)
    # skip tp(x4), application does not use it
    # save x5~x31
    .set n, 5
    .rept 27
        SAVE_GP %n
        .set n, n+1
    .endr
    # we can use t0/t1/t2 freely, because they were saved on kernel stack
    csrr t0, sstatus
    csrr t1, sepc
    sd t0, 32*8(sp)
    sd t1, 33*8(sp)
    # read user stack from sscratch and save it on the kernel stack
    csrr t2, sscratch
    sd t2, 2*8(sp)
    # set input argument of trap_handler(cx: &mut TrapContext)
    mv a0, sp
    call trap_handler

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

__restore:
    # case1: start running app by __restore
    # case2: back to U after handling trap
    mv sp, a0
    # now sp->kernel stack(after allocated), sscratch->user stack
    # restore sstatus/sepc
    ld t0, 32*8(sp)
    ld t1, 33*8(sp)
    ld t2, 2*8(sp)
    csrw sstatus, t0
    csrw sepc, t1
    csrw sscratch, t2
    # restore general-purpuse registers except sp/tp
    ld x1, 1*8(sp)
    ld x3, 3*8(sp)
    .set n, 5
    .rept 27
        LOAD_GP %n
        .set n, n+1
    .endr
    # release TrapContext on kernel stack
    addi sp, sp, 34*8
    # now sp->kernel stack, sscratch->user stack
    csrrw sp, sscratch, sp
    sret

What is AVL Tree?

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

#include<iostream>
#include<cstdio>

using namespace std;

class Node {
public:
    int data;
    int height;
    Node *left;
    Node *right;
};

Node *newNode(int data) {
    Node* node = new Node();
    node->data = data;
    node->height = 1;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int getHeight(Node* node) {
    if (node == NULL)
        return 0;
    return node->height;
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

int getBalance(Node* node) {
    if (node == NULL)
        return 0;
    return getHeight(node->left) - getHeight(node->right);
}

Node *rightRotate(Node* y) {
    Node *x = y->left;
    Node *T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

    return x;
}

Node *leftRotate(Node *x) {
    Node *y = x->right;

    Node *T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

    return y;
}

Node *insert(Node *node, int data){
    if (node == nullptr) {
        return (newNode(data));
    }
    if (data < node->data) {
        node->left = insert(node->left, data);
    }
    else if (data > node->data) {
        node->right = insert(node->right, data);
    }
    else {
        return node;
    }

    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    int balance = getBalance(node);

    if (balance > 1 && data < node->left->data) {
        return  rightRotate(node);
    }

    if (balance < -1 && data > node->right->data) {
         return leftRotate(node);
    }

    if  (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

void printTree(Node *root) {
    if (root == NULL) {
        return;
    }
    printTree(root->left);
    cout << root->data << " ";
    printTree(root->right);
}

int main() {
    Node *root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    printTree(root);
    return 0;
}

BIOS

It is a firmware that provide the necessary instruction for the computer to perform basic functions such as hardware initialization.

Functions of the BIOS

1. Power-On Self-Test (POST):
   When you turn on your computer, the BIOS performs a POST to check that all the necessary hardware components (like memory, keyboard, and storage devices) are functioning correctly.
2. Bootloader Execution:
   After the POST, the BIOS looks for a bootable device (like a hard drive, SSD, USB drive, or CD/DVD) and loads the bootloader from the bootable device into memory. The bootloader then takes over to load the operating system kernel.
3. Hardware Initialization:
   The BIOS initializes and configures hardware components, setting up basic operational parameters. This includes setting up the CPU, memory, and peripherals such as disk drives and video cards.
4. BIOS Setup Utility:
   The BIOS includes a setup utility that users can access to configure hardware settings, such as system time and date, boot sequence, and hardware parameters.
5. BIOS Services:
   The BIOS provides low-level routines that operating systems and programs can use to interact with hardware. These routines offer a standardized way for software to communicate with hardware devices without needing to know the details of the hardware.

BIOS interrupt

It refer to invoke routines provided by the BIOS to the x86-based computer. It allows the CPU to switch from executing the current program to the routine provided by the BIOS.
Calling BIOS Interrupts:

• To invoke a BIOS interrupt, software sets up registers with specific values, including the interrupt number (represented as an index into the IVT). Then, the software triggers the interrupt using the INT instruction, which causes the CPU to transfer control to the corresponding ISR in the BIOS.
  Purpose and Usage:
• BIOS interrupts are used to perform low-level operations that interact directly with hardware, such as disk I/O, keyboard input, video display, system timer control, and system shutdown/restart functions.
• They provide a standardized interface for software running in real mode to access these hardware functions without needing to know specific hardware details.

Example of BIOS interrupt

INT 13h: Provides disk services, such as reading and writing sectors from/to disk drives
INT 15h: Provides system services, including memory allocation, system configuration query, and power management functions.

Bootloader

Bootloader is a program to load the operator system kernel into memory.

Functions of a Bootloader

1. Power-On Self-Test (POST):
   When you turn on your computer, the Basic Input/Output System (BIOS) or the Unified Extensible Firmware Interface (UEFI) performs a POST to check hardware components’ functionality.
2. Boot Device Detection:
   After the POST, the BIOS/UEFI searches for a bootable device, such as a hard drive, SSD, USB drive, or CD/DVD, based on the boot order specified in BIOS/UEFI settings.
3. Loading the Bootloader:
   Once a bootable device is detected, the BIOS/UEFI loads the initial bootloader program stored in a specific location on that device (e.g., the Master Boot Record or EFI System Partition).
4. Bootloader Execution:
   The bootloader program takes control, initializes hardware (if necessary), and allows the user to select which operating system or kernel to load if multiple options are available (e.g., dual-boot systems).
5. Loading the Kernel:
   The main task of the bootloader is to load the operating system kernel into memory. It reads the kernel file from the boot device and transfers control to the kernel, passing any necessary parameters.
6. Transition to Operating System:
   Once the kernel is loaded and initialized, the operating system takes over and continues the boot process. The OS then loads necessary drivers, initializes system services, and presents the user with a login screen or desktop environment.

Load kernel process

LBA

LBA is commonly used in BIOS (Basic Input/Output System) and operating systems to access data on hard drives, solid-state drives (SSDs), and other storage devices.
When reading or writing data to a disk using LBA, the operating system or application specifies the LBA address along with other parameters (such as the number of sectors to read/write and the buffer address).

How to read a sector

1. Prepare Registers:
   • mov $0x42, %ah sets AH to 0x42 to indicate the Extended Read function.
   • mov %sp, %si sets SI to point to the stack pointer, which will be used as the pointer to the data packet.
2. Push [[Data packet]] onto the Stack:
   • Push the packet size (16 bytes).
   • Push the number of sectors to read (1 sector).
   • Push the buffer offset (0), which is the offset within the segment where data should be read into.
   • Push the buffer segment (ES), which is the segment where data should be read into.
   • Push the LBA address in three parts (high part, mid part, low part).
3. Call BIOS Interrupt:
   • int $0x13 calls the BIOS interrupt to perform the Extended Read operation using the data packet.

homework4

1. 100%
2. cpu 4 + io-run 1 + block 5 + io-done 1 总时间 11，cpu:5, io:6
3. 交换顺序后，io阻塞期间，系统同时执行CPU工作，总时间为7。交换顺序可以有效利用系统资源。
4. 系统执行完I/O后执行CPU工作。
5. 系统执行I/O同时执行CPU工作。
6. 当 I/O 完成时， 发出它的进程不一定马上运行。相反，当时运行的进程一直运行。
7. CPU利用率显著提高。运行完一个刚刚完成I/O的进程，可以有效利用I/O阻塞时间，执行CPU工作。
8. 指令：-s 2 -l 3:50,10:100
   • -I -IO_RUN_IMMEDIATE：I/O完成时，发出它的进程立刻运行io-done (Total time: 15)
   • -I-IO_RUN_LATER：I/O完成时，发出它的进程等待CPU工作完成后再运行。(Total time: 20)
   • -S SWITCH_ON_IO：进行I/O操作时，系统会切换到其他进程。(Total time: 20)
   • -S SWITCH_ON_END：进行I/O操作时，系统不会切换到其他进程。(Total time: 25)

费曼学习法是由著名物理学家、诺贝尔物理学奖得主理 查德·费曼提出的。其核心就是： 通过简短的语言，向别人清楚地解说一件事，来检验自己是否真的弄懂了这件事。
费曼学习法可以简化为四个单词： concept（概念）、Teach（教给别人）、Review（评价）、Simplify（简化）。具体操作可概括四个步骤：

什么是KDTree

KDTree 是一种树数据结构，用于存储多维数据，是二叉搜索树(BST)的推广，广泛应用于查询操作。KDTree表示数据的维数必须全部相同，KDTree是每个节点都为k维点的二叉树。所有非叶子节点可以视作用一个超平面把空间分割成两个半空间。节点左边的子树代表在超平面左边的点，节点右边的子树代表在超平面右边的点。选择超平面的方法如下：每个节点都与k维中垂直于超平面的那一维有关。因此，如果选择按照x轴划分(如图1 (30,40节点)，所有x值小于30的节点都会出现在左子树，所有x值大于等于30的节点都会出现在右子树。这样，超平面可以用该x值来确定，其法线为x轴的单位向量。下一层，按照y轴划分(如图1 (5, 25节点)，所有y值小于25的节点放在左子树，大于25的放在右子树。以此类推，KDTree根据深度选择分割超平面，设深度为level，数据维数为dim。则分割超平面用第level % dim维的值来确定。图2是三维KDTree。