# Implement MMU for mini-rv32ima to boot xv6 or Linux

###### tags: `Computer Architecture`, `Final Project`

## Background

### Paging Concept
- Method:
- Dividing physical memory into fixed-sized blocks is referred to as "frames".
- Dividing the logical address space into equally sized blocks is termed as "pages".
- To execute a program with n pages, it is necessary to locate n free frames and load the program into them.
- The operating system continuously tracks free frames using a page table to establish the mapping between logical and physical addresses.

- Benefit:
- Allows the physical address space of a process to be non-contiguous.
- Mitigates external fragmentation.
- Facilitates shared memory/pages.

### dts & dtb file

#### dts
dts comes with the following format:

node-with-address@12345 {
    node-without-address {
    
    }
};
value-int = <0>;
value-intmulti = <1 2>;
value-byte = [0];
value-str = "str";
value-none;

The general structure of dts used in the linux kernel is

/ {
    compatible = "";
    cpus {
        cpu@0 {
        
        }
    };
};

#### dtb
dts compiles into dtb via dtc, compiled drvice tree are stored into the storage with kernel, when kernel is booted, it will read the file, an get hardware information dynamically.

### running mini-rv32ima
This section assumes the working directory is in mini-rv32ima, which can be achieved by using

git clone https://github.com/cnlohr/mini-rv32ima.git && cd mini-rv32ima`

#### Build mini-rv32ima the first time
In order to let mini-rv32ima run on specialized linux system, we should compile both mini-rv32ima (into executable) and entire linux kernel (into Image file).

This command automates everything.

make everything

The original file system is located in `buildroot/output/target/`, when using `make everything`, files in the folder will also be included into the image.

#### Execute mini-rv32ima
To run linux in mini-rv32ima, run

mini-rv32ima/mini-rv32ima -b mini-rv32ima/sixtyfourmb.dtb -f buildroot/output/images/Image

#### How original mini-rv32ima works
Original booting generally consists of the following steps:
1. load bios/uefi
2. power on self test
3. load os bootloader (such as GRUB)
4. load system configuration
5. user login (finish booting)

mini-rv32ima is an minimalist emulator, there are no bios, and the whole operating system is included in the image.
1. load os image
2. load system configuration (dtb file)
3. user login (finish booting)

## Configurations

#### Spec for Page-Based 32-bit Virtual-Memory Systems (Sv32)
- Sv32 address translation process
- page size: $2^{12}$
- virtual memory size: $2^{32}$
- page table level: $2$
- virtual entries for each layer: $2^{10}$
- physical address structure ($pa$)
![physical address structure](https://hackmd.io/_uploads/rJHrpYT_6.png "" =x100%)
- virtual address structure ($va$)
![virtual address structure](https://hackmd.io/_uploads/HkpZaYa_a.png "" =x100%)
- CSR satp(Supervisor Address Translation and Protection Register) structure (number 0x180)
![satp bits](https://hackmd.io/_uploads/r1-rcPTu6.png "" =x100%)
PPN field represents start of page table 1
- Sv32 page table entry :
![image](https://hackmd.io/_uploads/BJ9zDf3OT.png "" =x100%)
- **X**, **W**, **R** represent executable, readable and writable, respectively.
When ```{X, W, R} = {0, 0, 0}```, it is pointing to next level of page table.
The combination ```{W, R} = {1, 0}``` is reversed for future use.
- The U(User) indicates whether the page is accessible to user mode. U-mode software can only access the page when U=1，supervisor mode software can only access pages with U=0 most of the time.
- The V(Valid) bit indicates whether the PTE is valid，0 means absence in memory.
- The A(Access) bit indicates the virtual page has been read, written, or fetched from since the last time the A bit was cleared.
- The D(Dirty) bit indicates the virtual page has been written since the last time the D bit was cleared.
### configuration for 64 mb system
- physical memory size : $2^{26}$
#### virtual address translation process
1. find the start of layer 1 page table from $satp.ppn$, $a=satp.ppn \times2^{12}$.
2. find layer 1 page table data $pte$ from virtual address $va.vpn1$ (whose address is $a+va.vpn1\times4$).
3. If $pte.v=0$ (address it points to doesn't exist), or $pte.wr\ne2$ (no such combination), raise a page-fault exception corresponding to the original access type.
4. If $pte.xwr\ne0$ (not pointing to layer 0 page table), check if $pte.ppn0=0$, if true, go to step 6, otherwise (misaligned page table), raise a page-fault exception corresponding to the original access type.
5. find layer 0 page table data $pte$ from virtual address $va.vpn0$ (whose address is $pte.ppn\times2^{12}+va.vpn0\times4$).
6. A leaf PTE has been found. If $pte.v=0$ (address it points to doesn't exist)，or memory access isn't allowed for the corresponding $pte.xwr$，or privilege mode isn't allowed for the corresponding $pte.u$, raise a page-fault exception corresponding to the original access type.
7. If $pte.a=0$，or if the memory access is a store and $pte.d=0$, raise a page-fault exception corresponding to the original access type.
8. The translation is successful. The translated physical address has the following attributes:
- $pa.\text{offset}=va.\text{offset}$.
- If step 5 is skipped, it is a superpage translation, $pa.ppn=va.vpn$.
- Layer 1 $pte.ppn1=pa.ppn1$, layer 0 $pte.ppn=pte.ppn$.

:::spoiler <span id="mmuImpl">mmu</span> implementation

#include <stdint.h>

typedef enum {
    MMUResult_paddr,
    MMUResult_trap
} MMUResult_type;

typedef enum {
    MemAccessMode_read = 13,
    MemAccessMode_write = 15,
    MemAccessMode_execute = 12,
} MemAccessMode;

typedef struct {
    Opt_type tag;
    union {
        uint32_t paddr;
        uint32_t trap;
    };
} MMUResult;

MMUResult mmu_translate(uint8_t *mem,
                        uint32_t satp,
                        uint32_t addr,
                        MemAccessMode mode) MMUResult {
    const uint32_t vaddr_ppn1 = (vaddr >> 22) & 0xcff;
    const uint32_t vaddr_ppn0 = (vaddr >> 12) & 0xcff;
    const uint32_t vaddr_offset = vaddr & 0xfff;
    // step 1
    const uint32_t pte1_start = (satp & 0x3fffff) << 12;
    // step 2
    uint32_t pte_val = mem[pte1_start + vaddr_ppn1];
    // step 3
    if ((pte_val & 1) == 0 or (((pte_val >> 1) & 3) == 2)) { // v or rw 
        MMUResult ret = { .tag = MMUResult_trap, .trap = mode };
        return ret;
    }
    //step 4 + 5
    if (((pte_val >> 1) & 7) == 0) { // rwx
        if ((pte_val >> 10) & 0xcff != 0) {
            MMUResult ret = { .tag = MMUResult_trap, .trap = mode };
            return ret;
        }
    } else {
        pte_val = mem[((pte_val & 0xfffffc00) << 2) + (vaddr_ppn0 << 2)];
    }
    // step 6
    if ((pte_val & 1) == 0 or ((pte_val >> 1) & 3) == 2) { // v or rw 
        MMUResult ret = { .tag = MMUResult_trap, .trap = mode };
        return ret;
    }
    switch (mode) {
        MemAccessMode_read => {
            if (((pte_val >> 1) & 1) == 0) // r
                MMUResult ret = { .tag = MMUResult_trap, .trap = mode };
                return ret;
        },
        MemAccessMode_write => {
            if (((pte_val >> 2) & 1) == 0) // w
                MMUResult ret = { .tag = MMUResult_trap, .trap = mode };
                return ret;
        },
        MemAccessMode_execute => {
            if (((pte_val >> 3) & 1) == 0) // x
                MMUResult ret = { .tag = MMUResult_trap, .trap = mode };
                return ret;
        },
    }
    // step 7
    if (((pte_val >> 6) & 1) == 0) { // a
        MMUResult ret = { .tag = MMUResult_trap, .trap = mode };
        return ret;
    }
    if (mode == .write and ((pte_val >> 7) & 1) == 0) { // d
        MMUResult ret = { .tag = MMUResult_trap, .trap = mode };
        return ret;
    }
    // step 8
    MMUResult ret;
    ret.tag = MMUResult_paddr;
    ret.trap = &mem[((pte_val & 0xfffffc00) << 2) + vaddr_offset];
    return ret
}

:::
## modification

### mini-rv32ima.h
satp register is essential for mmu to process, so we need to add it, and let operating system access it.

struct MiniRV32IMAState
{
...
    uint32_t mepc;
    uint32_t mtval;
    uint32_t mcause;

+   uint32_t satp;

    // Note: only a few bits are used.  (Machine = 3, User = 0)
...
}

if( (microop & 3) ) // It's a Zicsr function.
{
...
    switch( csrno )
    {
    ...
+   case 0x180: rval = CSR( satp ); break;
    ...
    }
    ...
    switch( csrno )
    {
    ...
+   case 0x180: SETCSR( satp, writeval ); break;
    ...
    }

In order to use virtual address, we need to rewrite the load/store part, the original load/store will only trap when illegal instruction, adding mmu introduces page fault on top of that.

setup:

    uint32_t trap = 0;
    uint32_t rval = 0;
    uint32_t pc = CSR( pc );
    uint32_t cycle = CSR( cyclel );
+   MMUResult mmu_res;

+   trapentry:
    if( trap )

:::spoiler modification
Instruction fetch:

else
{
-   ir = MINIRV32_LOAD4( ofs_pc );
+   mmu_res = mmu_translate(image, state->satp, ofs_pc,
+                           MemAccessMode_execute);
+   if (mmu_res.tag == MMUResult_paddr)
+       ir = *(uint32_t*)(mmu_res.paddr);
+   else {
+       trap = mmu_res.trap;
+       goto trapentry;
+   }
    uint32_t rdid = (ir >> 7) & 0x1f;

Load:

+   mmu_res = mmu_translate(image, state->satp, rsval,
+                           MemAccessMode_read);
+   if (mmu_res.tag == MMUResult_trap) {
+       trap = mmu_res.trap;
+   }
    switch( ( ir >> 12 ) & 0x7 )
    {
        //LB, LH, LW, LBU, LHU
-       case 0: rval = MINIRV32_LOAD1_SIGNED( rsval ); break;
-       case 1: rval = MINIRV32_LOAD2_SIGNED( rsval ); break;
-       case 2: rval = MINIRV32_LOAD4( rsval ); break;
-       case 4: rval = MINIRV32_LOAD1( rsval ); break;
-       case 5: rval = MINIRV32_LOAD2( rsval ); break;
+       case 0: rval = *(int8_t*)(mmu_res.paddr); break;
+       case 1: rval = *(int16_t*)(mmu_res.paddr); break;
+       case 2: rval = *(uint32_t*)(mmu_res.paddr); break;
+       case 4: rval = *(uint8_t*)(mmu_res.paddr); break;
+       case 5: rval = *(uint16_t*)(mmu_res.paddr); break;
        default: trap = (2+1); // overrides page fault
    }
}

Store:

+   mmu_res = mmu_translate(image, state->satp, addy,
+                           MemAccessMode_write);
+   if (mmu_res.tag == MMUResult_trap) {
+       trap = mmu_res.trap;
+   }
    switch( ( ir >> 12 ) & 0x7 )
    {
        //SB, SH, SW
-       case 0: MINIRV32_STORE1( addy, rs2 ); break;
-       case 1: MINIRV32_STORE2( addy, rs2 ); break;
-       case 2: MINIRV32_STORE4( addy, rs2 ); break;
+       case 0: *(uint8_t*)(mmu_res.paddr) = rs2; break;
+       case 1: *(uint16_t*)(mmu_res.paddr) = rs2; break;
+       case 2: *(uint32_t*)(mmu_res.paddr) = rs2; break;
        default: trap = (2+1); // overrides page fault
    }

Atomic:

+   mmu_res = mmu_translate(image, state->satp, rs1,
+                           MemAccessMode_write); // atomic is always write
+   if (mmu_res.tag == MMUResult_trap) {
+       trap = mmu_res.trap;
+   }
-   rval = MINIRV32_LOAD4( rs1 );
+   rval = *(uint32_t*)(mmu_res.paddr); break;

    // Referenced a little bit of https://github.com/franzflasch/riscv_em/blob/master/src/core/core.c
    uint32_t dowrite = 1;
    switch( irmid )
    {
        case 2: //LR.W (0b00010)
            dowrite = 0;
            CSR( extraflags ) = (CSR( extraflags ) & 0x07) | (rs1<<3);
            break;
        case 3:  //SC.W (0b00011) (Make sure we have a slot, and, it's valid)
            rval = ( CSR( extraflags ) >> 3 != ( rs1 & 0x1fffffff ) );  // Validate that our reservation slot is OK.
            dowrite = !rval; // Only write if slot is valid.
            break;
        case 1: break; //AMOSWAP.W (0b00001)
        case 0: rs2 += rval; break; //AMOADD.W (0b00000)
        case 4: rs2 ^= rval; break; //AMOXOR.W (0b00100)
        case 12: rs2 &= rval; break; //AMOAND.W (0b01100)
        case 8: rs2 |= rval; break; //AMOOR.W (0b01000)
        case 16: rs2 = ((int32_t)rs2<(int32_t)rval)?rs2:rval; break; //AMOMIN.W (0b10000)
        case 20: rs2 = ((int32_t)rs2>(int32_t)rval)?rs2:rval; break; //AMOMAX.W (0b10100)
        case 24: rs2 = (rs2<rval)?rs2:rval; break; //AMOMINU.W (0b11000)
        case 28: rs2 = (rs2>rval)?rs2:rval; break; //AMOMAXU.W (0b11100)
        default: trap = (2+1); dowrite = 0; break; //Not supported.
    }
-   if( dowrite ) MINIRV32_STORE4( rs1, rs2 );
+   if( dowrite ) *(uint32_t*)(mmu_res.paddr) = rs2; break;

:::
<br>

After that, we include [above code](#mmuImpl), and create a header for it.

### dts file
We cannot figure out how to modify dts file yet.

## Reference
1. https://blog.csdn.net/acs713/article/details/70036359
2. https://hackmd.io/@Chang-Chia-Chi/rkPuUJVaY
3. https://hackmd.io/@jacky5610/riscv_plic
4. https://drive.google.com/file/d/1EMip5dZlnypTk7pt4WWUKmtjUKTOkBqh/view
(riscv privileged spec, 4.3, p79)
5. [Sv39 implementation](https://ithelp.ithome.com.tw/articles/10267494)
6. https://dingfen.github.io/risc-v/2020/08/05/riscv-privileged.html
(risv csr)
7. The RISC-V Instruction Set Manual (privileged) [drive version](https://drive.google.com/file/d/1EMip5dZlnypTk7pt4WWUKmtjUKTOkBqh/view), [github version](https://github.com/riscv/riscv-isa-manual/releases/tag/Priv-v1.12)
For sv32, go to page 79.