Unix V6 on PDP-11 architecture - Introduction
===

###### tags: `unix_v6` `kernel`

## 目錄
[TOC]

## Unix V6
Kenneth Lane Thompson, Dennis MacAlistair Ritchie 開發
貝爾實驗室 1976 年發布。

以下的 Unix V6 source 皆是以在 PDP-11/40 的機器上運行的為準。

## PDP-11 architecture
16-bit 架構，RISC，指令和 data 都是以 16 bit 為單位進行處理。

In PDP-11, `one word = 16 bits = 2 bytes`

bus 的地址寬度為 18 bits，所以 memory 最高可以安裝 2^18^ = 256KB 上去 (範圍： 0x00000 ~ 0x3FFFF)

PDP-11/40 的 I/O address, registers 會被 mapped 到 physical memory 的最上方 8 KB 的位置 (以 memory 256KB 為例，即 0x3e000 ~ 0x3FFFF)

### PDP-11 registers
register 的長度皆為 16 bit

#### General registers
1. r0, r1
- 用於運算
- 函數的回傳值
2. r2, r3, r4
- local 暫存、處理
3. r5
- frame pointer or environment pointer
4. r6
- stack pointer (sp)
5. r7
- program counter (pc)

#### PSW
*[PSW]: PSW (program status word)

類似 ARM 的 CPSR

| bit | 15-14 | 13-12 | 7-5 | 4 | 3 | 2 | 1 | 0 |
| --------- | --------- | --------- | --------- | ------- | ---- | ---- | ---- | ---- |
| functions | current mode | previous mode | 處理器的優先級 | trap 位 | N | Z | V | C |

mode (15-14 & 13-12 bits): 00 for user mode, 11 for kernel mode

## Process
- process 狀態
1. Executable
2. Sleep
- CPU 有兩種 mode，user mode and kernel mode，process 切換 mode 時，所對應的實體記憶體位置也會變，即 user mode 和 kernel mode 有不同的實體記憶體區域
- 隨著 process 增多，memory 會不足，這時會將休眠狀態或是重要度較低的 process 移出 memory 到 swap 裡。

### Process structure

一個 active process 會被分配到兩個 structure，`struct proc, struct user`
> One struct proc and one struct user are allocated per active process.

- struct proc
- 
- 一個 process 對應一個 struct proc，一個系統上的所有 process 就是 proc\[\]
- proc\[\] 常駐在 memory 中
- proc\[\] 的長度定義在 macro NPROC `#define NPROC 50` (參考：unixV6 param.h)

- struct user
- 
- struct user 是用來記錄 process 打開的目錄、文件等等訊息
- 由於 kernel 只需要當前執行的 process 所對應到的 struct user，所以當其他的 process 被 swapped out 時，他所對應的 struct user 也會被 swapped out
- 而當前所執行的 process，其所對應到的 struct user，kernel 可透過 global variable, `_u` 來存取，可參考 `conf/m40.s`

    /* conf/m40.s */
    .global _u
    _u = 140000     // Note: is octal! 

### Process in memory
- 首先先看一下在 pdp11 上，physical 和 virtual address 的長度容量差別：
| Address Space | address length | capacity |
| ------------- | ------------- | -------- |
| virtual address | 16 bits | 2^16^ = 64K |
| physical address | 18 bits | 2^18^ = 256K |

- 每個 process 都有一個自己的 virtual address space，使用 virtual address 而不直接使用 physical address 有以下的好處:
1. program 可以使用以任意地址為起點的 memory space
2. 管理方便，避免某 process 訪問到其他 process 的 memory space
3. 提高 memory 使用效率

Process Layout in the virtual memory (地址長度 16 bits，容量 64K):

Address (virtual)          Layout
0x0000 ←-------------┌────────────────┐---------╮
                     |                |         ↓
                     |                |
                     |     .TEXT      |   "Text Segment" 
                     |                | size=user.u_tsize
                     |                |         ↑
                     |────────────────|---------╯
                     |                |
                     |                |
                     |                |
                     |                |
                     |────────────────|--╮--------------------------╮   
                    (│   struct user  |) ↓                          |
                    (│----------------|) "PPDA", size=USIZE         |
                    (|  kernel stack  |) ↑                          |
0x2000N (Align 8KB) ←|────────────────|--╯------╮                   |
                     |     .DATA      |         ↓                   |
                     |----------------|                             |
                     |     .BSS       |      "Data Area"            |
                     |----------------|   size=user.u_dsize         |
                     |                |                             |
                     |      HEAP      |                             |
                     |                |         ↑                   |
                     |────────────────|---------╯                   ↓
                     |       ↓        |                       "Data Segment"
                     |                |          size = proc.p_size 
                     |                |               = USIZE + user.u_dsize
                     |                |                 + user.u_ssize
                     |                |                             ↑
                     |                |                             |
                     |                |                             |
                     |                |                             |
                     |       ↑        |                             |
                     |────────────────|---------╮                   |
                     |                |         ↓                   |
                     |                |      "Stack Area"           |                
                     |     STACK      |   size=user.u_ssize         |                        
                     |                |                             |                                 
                     |                |         ↑                   |
0xFFFF ←-------------└────────────────┘---------╯-------------------╯
                                       

:::danger
PPDA 實際上並不存在 virtual memory 中，只在 physical memroy 上，所以 user space 無法存取 PPDA，可見下圖
:::

:::info
以下講的 size，單位皆為 64 bytes，例如： size = 2，則大小總共為 64\*2 = 128 bytes
:::

#### Text Segment
- READ-ONLY，用來儲存 process 要被執行的 machine code
- 若某個 process 被執行多次，則共享同一個 Text Segment
- size = user.u_tsize

#### Data Segment
- 跟 Text Segment 不一樣，不會被多個 process 共享
- Data Segment 的 physical address 儲存在 proc.p_addr 裡，其長度則是儲存在 proc.p_size 裡
- proc.p_size = USIZE + user.u_dsize + user.u_ssize
- Data Segment 包含了
1. PPDA (pre-process data area)
- 由 struct user 和 kernel stack 所組成
- 每個 process 都有其自己的一段 virtual memory，即都有屬於自己的 PPDA
- 而 PPDA 儲存於 physical memory 中，**並沒有被 map 到 virtual memory 上**。
- 其在 physical memroy 中，位於 virtual memory mapped 到 physical memory 位置的上方 (較低位置處)。
- size = USIZE，USIZE 定義在 param.h 裡 `#define USIZE 16` ，所以其大小為 16\*64(bytes) = 1024 bytes = 1K

2. Data Area, size = user.u_dsize = .Data + .BSS + Heap size
1. .Data - static, global variables **with initialization**.
2. .BSS- static, global variables **without initialization**.
3. Heap - dynamic variables，可以往高位置的地方上長，以增加空間。

3. Stack Area (Stack)
- local varaibles, data
- 在 virtual address 中的最高位置，會往低位置上長
- size = user.u_ssize，以增加空間。

## Address Translation
*[MMU]: Memory Management Unit
*[APR]: Active Page Register

- MMU 透過 APR 去做 address translation

    virtual_address → MMU → physical_address
                      ⎛⎞
             ⎧‾‾‾‾‾‾‾‾‾⏉‾‾‾‾‾‾‾‾‾⎫
             |   PAR   ⎮   PDR    |
             ⎩_________⏊_________⎭
                      APR

### APR - PAR & PDR

#### APR


- APR 有兩種，kernel mode 和 user mode ，要使用哪種是根據 PSW register 的 \[15-14\] bits (即當前狀態) 來決定的 (00->kernel, 11->user)

- APR 的值保存在 struct user 中，當輪到某一個 process 執行時，則會把其相對應的 struct user 欄位裡的 APR 值 load 出來存進 APR register

- 一組 APR 由 8 個 (即 APR0, APR1, ..., APR7) registers，**每一個對應到一個 page**，然後 APR 總共又有兩個 (kernel mode & user mode)

- APR 由 PAR(Page Address Register) 和 PDR(Page Description Register) 所組成

*[PAR]: Page Address Register
*[PDR]: Page Description Register

#### PAR
用來記錄 base address

| bits | 11 - 0 |
| ---- | ------ |
| description | base address (64 bytes 為單位) |

#### PDR
用來記錄 page 裡總共有幾個 block，access rights 等等。

| bits | 14-8 | 6 | 3 | 2-1 |
| ---- | ---- | - | - | --- |
| description | block 數目 | update flag, 用來表示是否更新的 flag | page address 的分配方式 (1 : 0) = (Decending : Accending) | page access rights (00 : 01 : 11) = (未分配 : READ_ONLY : READ&WRITE) |

### How to translate?

#### Step 1.
先由 virtual_address \[15:13\] bits 算出是哪一個 APR (也就是第幾個 PAR )

**假設算出個結果是 N，即第 N+1 個**

Note: \[15:13\] 3 bits, 2^3^ = 8，剛好夠表示 APR0 ~ APR7，共八個

#### Step 2.
找出是哪一個 APR 後，找出其對應的 PAR
(Ex: 假設是第N+1個 APR，即 APR\[N\]，那對應的也是 PAR\[N\])

計算出 nBlock_baseAddr
~ nBlock_baseAddr = PAR\[N\]~\[11:0\]~ + virtual_address~\[12:6\]~

Note: nBlock_baseAddr 為 physical address 上第 N 個 Block 的 base address

#### Step 3.
有了 virtual address 是在 physical address 第幾個 block 的 **base address** 後，我們 append offset (virutal_address~\[5:0\]~)後，即可得到實際的 physical address (total 18 bits)

**再次提醒，physical address length = 18 bits, virtual = 16 bits**

### How to access current process's "struct user"?

Recall: 前面有提到可以透過 global variable `_u` 來獲 current process's "struct user"

/* conf/m40.s */
.global _u
_u = 140000     // Note: is octal! 


Address: 140000~octal~ = 1 110 000 000 000 000~bin~

最高三位為 6 代表他所對應的是 (kernel mode) APR\[6\]
`_u` 所指到的是 kernel space 裡 page6 的起始位置(因為後面都是0)

將這個位置作為 current process 的 Data Segment (including PPDA, Data Area, Stack Area)

即將 proc.p_addr = **PAR\[6\]~\[11:0\]~** << 6，可以這麼做的原因是因為他的後面 offset 全部是 0

而 PPDA 的位置是在 proc.p_addr，剛好 PPDA 的起始就是 current process's struct user，這樣我們就成功得到了 struct user 的 physical address 了。