---
# System prepended metadata

title: Virtual Memory Complete

---

# Virtual Memory Complete
410410062 張秉棋 資工系三年級
### 1. VAX/VMS Virtual Memory
#### 1.1 Memory Management Hardware
- VAX-11 提供每一個 process 最多 32-bit 的 virtual address space
- 而其中每一個 page 的 size 是 512-Byte ($2^9 = 512$)
- 所以 32-bit 將會被分為 23-bit 用來表示 VPN 剩下的 9-bit 用來表示 offset
- 同時最高的 2-bit 將會被用來表示所屬的 segment
- 因為 page size 的太小所以可能會導致 page table 太大可以有兩種解決方式 <br/>
-- 將 user address space 分成兩個 segmation (P0,P1)
-- 講 user page table 放在 kernel virtual memory

#### 1.2 A Real Address Space
![](https://hackmd.io/_uploads/ByRZbLfG6.png)

#### 1.3 Page Replacement
- VAX 的 Page Table Entry(PTE)包含以下幾個有效的 bit :

| valid bit | protection bit | dirty bit | reserved bit | PEN   |
| --------- | -------------- | --------- | ------------ | --- |
| 1-bit     | 4-bit          | 1-bit     | 5-bit        | 剩下的bit|

- 會遇到的問題：
<br/>
    - no **reference bit**, so VMS replacement algorithm must make do without hardware support for determining which pages are active.
    - 當其中一個 process 使用了很大的 memory 會導致 other process 沒有 memory 可以用 
<br/>
- 為了解決問題 developers 提出的解決方法： 
<br/>
    - **segmented FIFO replacement policy :** 
each process has a maximum number of pages it can keep in memory, known as its resident set size (RSS). Each of these pages is kept on a FIFO list; when a process exceeds its RSS, the “first-in” page is evicted.
    - **secondchance lists :** 
**clean-page free list** and **dirty-page list** 用來存放被 evicted 掉的 process.

#### 1.4 Other Neat Tricks
- demand zeroing
- copy-on-write
<br/>

### 2. Linux Virtual Memory System
#### 2.1 The Linux Address Space
![](https://hackmd.io/_uploads/S1j-zPMzT.png)

- Linux 包含兩種 kernel virtual addresses ：
<br/>
    - **kernel logical addresses**
        - 大部分的 kernel data structures 都會在這裡（ page tables, per-process kernel stacks, and so forth ）
        - 支援 Directory Memory Access (DMA)
    - **kernel virtual address**
        - memory 更容易 allocate 因此大多用來當 large buffer
        - 不支援 Directory Memory Access (DMA)
        
#### 2.2 Page Table Structure
![](https://hackmd.io/_uploads/BkeQmIvGGT.png)
<br/>
- 64-bit x86 address page table structure :
<br/>
    - **four-level table**
並沒有使用到全部的 bit 數而是指使用到 48-bit
(P1,P2,P3,P4 = 9-bits , Offset = 12-bits )
P1 portion of the address is used to index into the topmost page directory, and the translation proceeds from there, one level at a time, until the actual page of the page table is indexed by P4, yielding the desired page table entry.

#### 2.3 Large Page Support
- advantage
    - 可以降低發生 TLB miss 的情況
    - 可以縮減 Page 的 level 數
    - OS 處理 TLB miss 時可以用更快的速度找到目標 page 
<br/>
- disadvantage
    - 會產生 internal fragmentation 

#### 2.4 The Page Cache
- Linux 的 Page Cache 是統一的其中的三個來源：
<br/>
    - **memory-mapped files**
file data and metadata from devices 
    - **anonymous memory**
heap and stack pages that comprise each process
    - **page cache hash table**
entities are kept
<br/>
- Linux 使用 2Q replacement Algorithm 來決定移除的process :
<br/>
    - **2Q replacement Algorithm:**
        - 產生兩個 Queue : **inactive list** 跟 **active list**
        - first time page 會被放到 inactive list
        - re-referenced 時 page 會被移到 active list
        - 當需要替換時優先從 inactive list 裡面來替換
        - 一定週期將 active list 的 page 移動到 inactive list
<br/>        
    - 2Q replacement Algorithm 可以 approximate 於 LRU Algorithm
        - 使用較低的cost就達到近似的效果

#### 2.5 Security And Buffer Overflows
-  buffer overflow attacks
![](https://hackmd.io/_uploads/BJDJtOzGT.png)
    - 發生原因：input is in fact too long, it overflows the buffer, thus overwriting memory of the target.
    
- 解決 buffer overflow attacks 的措施

    - **NX bit** (for No-eXecute) : it just prevents execution from any page which has this bit set in its corresponding page table entry. The approach prevents code, injected by an attacker into the target’s stack, from being executed, and thus mitigates the problem.
- return-to-libc attack
    - 攻擊方式： 使當前執行函數中的返回地址指向所需的惡意指令
- 解決 return-to-libc attack 的措施

    - **address space layout randomization** (ASLR) : Instead of placing code, stack, and the heap at fixed locations within the virtual address space, the OS randomizes their placement, thus making it quite challenging to craft the intricate code sequence required to implement this class of attacks.

- 目前的 Ｃ 語言就是使用 ASLR 的技術：
    - 我們可以看到每次的 virtual address 都會不一樣

![](https://hackmd.io/_uploads/SyY5n_MMa.png)
![](https://hackmd.io/_uploads/HydJ6_MGa.png)

#### 2.6 Other Security Problems
- Meltdown
是一個存在於英特爾大部分x86/x86-64微處理器、部分IBM POWER架構處理器以及部分ARM架構處理器中的關於推測執行機制的硬體設計缺陷及安全漏洞。該缺陷使得低權限的行程無論是否取得特權，均可以獲取受高權限保護的記憶體空間中的資料，漏洞利用是基於時間的旁路攻擊。
- Spectre
是一個存在於分支預測實現中的硬體缺陷及安全漏洞，含有預測執行功能的現代微處理器均受其影響，漏洞利用是基於時間的旁路攻擊，允許惡意行程獲得其他程式在對映記憶體中的資料內容。

## Reference
https://pages.cs.wisc.edu/~remzi/OSTEP/vm-complete.pdf
https://zh.wikipedia.org/wiki/熔毁_(安全漏洞)
https://zh.wikipedia.org/wiki/幽灵漏洞


