Linux 核心設計: 記憶體管理
===
:::warning
注意！這是上課筆記
:::

:::info
原始課程在這裡
- [影片 Part 1](https://www.youtube.com/watch?v=kY3g2r03erk)
- [影片 Part 2](https://www.youtube.com/watch?v=0oABzHrZDPY)
- [影片 Part 3](https://www.youtube.com/watch?v=9Kj7TBrvP-8)
- [講義](https://hackmd.io/@sysprog/linux-memory?type=view)

Original by [jserv](http://wiki.csie.ncku.edu.tw/User/jserv)
:::

---

# Part 1

| Section | Time| Description |
| -------- | -------- | -------- |
| 1 | [00:00:11](https://youtu.be/kY3g2r03erk?si=mXlESiwCQztm_pb_&t=11) | 1. 目標設定。<br>2. swap 的起源：PDP-7 unix.|
| 2 | [00:23:39](https://youtu.be/kY3g2r03erk?si=ASdY3U-2fMAhWBWb&t=1419) | 1. 學習金字塔。<br>2. 二戰的原子彈計算。<br>3. kernel space and user space 的比例。<br>4. 手機最重要的是 camera.|
| 3 | [00:38:33](https://youtu.be/kY3g2r03erk?si=KRWTtSYMQ8ocl4Hp&t=2313) | 1. 使用者模式和核心模式的切換。<br>2. PDP-11 mmu。<br>3. 定址空間: VA 轉成 PA。|
| 4 | [00:51:51](https://youtu.be/kY3g2r03erk?si=GIlSjF13KoTpGtF_&t=3111) | 1. MMU v.s. MPU.<br>2. protected mode.|
| 5 | [01:00:19](https://youtu.be/kY3g2r03erk?si=TRhs96uGiEh3PakA&t=3619) | 1. bootmem.<br>2. Device Tree.<br>3. buddy memory allocation.(buddy system) |
| 6 | [01:23:05](https://youtu.be/kY3g2r03erk?si=5rD3LA8kIhDdn_Yc&t=4985) | 1. page size(通常是 4K).<br>2. Linux 使用 slab 解決小物件分配。<br>3. NUMA 架構 凸顯 slab 的不足。<br>4. 因此 slub 讓每個 CPU 都有local slab。<br>5. 嵌入式系統則是使用 slob.|
| 7 | [01:46:35](https://youtu.be/kY3g2r03erk?si=KBulgm4AStL6pclp&t=6395) | 1. fragmentation buddy system.<br>2. vmalloc: virtually contiguous memory.<br>3. 記憶體配置器 for GPU: GEM v.s. TTM.<br>4. Ｔ型人才的重要。|
| 8 | [02:00:46](https://youtu.be/kY3g2r03erk?si=0-yhYOQKj_fvVUDY&t=7246) | 1. 執行檔對應到 process.<br>2. 連結器與執行檔資訊。<br>3. demo Process runtime 樣貌。|
| 9 | [02:17:00](https://youtu.be/kY3g2r03erk?si=NS3eKl_H4ItKchoP&t=8220) | 1. malloc and sbrk.<br>2. CoW: Copy-on-Write 需要的時候才配置空間。<br>3. 聊聊研究所考試。<br>4. page fault: major / minor / invalid.<br>5. minor page fault is for lazy allocation.|
| 10 | [02:46:55](https://youtu.be/kY3g2r03erk?si=rspjHPMeXAy9QETk&t=10015) | 1. kernel panic.<br>2. linux stack unwinding.<br>3. 下集預告。

# Part 2

| Section | Time| Description |
| -------- | -------- | -------- |
| 1 | [00:00:11](https://youtu.be/0oABzHrZDPY?si=bpIQE4Q8Fam8DB0W&t=11) | 1. 前情提要。<br>2. slob/slab/slub.<br>3. cache friendly data structure.|
| 2 | [00:18:00](https://youtu.be/0oABzHrZDPY?si=crRIfh5j4oMv5VGm&t=1080) | 1. 投影片 “Slab allocators in the Linux Kernel: SLAB, SLOB, SLUB”.<br>2. kernel API.<br>3. 如何鑑往知來。|
| 3 | [00:31:14](https://youtu.be/0oABzHrZDPY?si=X4s2lVu8bb1gwRUK&t=1874) | 1. slab:benchmark friendly; slub:execution time friendly.<br>2. SLOB data structures.<br>3. SLAB memory management.|
| 4 | [00:44:50](https://youtu.be/0oABzHrZDPY?si=KptY8AkzeDTNngdu&t=2690) | 1. Register allocation problem 著色問題。<br>2. SLAB data structures.<br>3. LRU cache implementation.|
| 5 | [00:56:26](https://youtu.be/0oABzHrZDPY?si=FphTZXSnTN3QgB2c&t=3386) | 1. SLUB memory layout.<br>2. SLUB data structures.<br>3. slabinfo tool / meminfo / htop.<br>4. 記憶體管理是 kernel 最難的部分。|
| 6 | [01:11:41](https://youtu.be/0oABzHrZDPY?si=hkP41R29yZ-dfnEd&t=4301) | 1. slabinfo basic output.<br>2. comparing memory use.<br>3. comparing performance.<br>4. 快速回顧。|
| 7 | [01:20:43](https://youtu.be/0oABzHrZDPY?si=TEy2fNSbGhx0qmz1&t=4843) | 1. Linux Kernel 追蹤方式：linux memory poisoning.<br>2. SLUB debug 原理。<br>3. KASAN: kernel address sanitizer 動態記憶體偵測器。|
| 8 | [01:38:50](https://youtu.be/0oABzHrZDPY?si=MyX4Qic0EDF8DY-w&t=5930) | 1. 投影片 “The Art and Science of Memory Allocation”.<br>2. malloc: sbrk for small size; mmap for big size.<br>3. mallopt. |
| 9 | [01:52:05](https://youtu.be/0oABzHrZDPY?si=fuvF2FJ7VVlokUQu&t=6725) | 1. Bump allocator.<br>2. linux kernel bookkeeping(記錄行為).<br>3. overarching issues.<br>4. Fragmentation: internal / external. |
| 10 | [02:03:27](https://youtu.be/0oABzHrZDPY?si=W5Laa9IEEifYjuW-&t=7407) | 1. HOARD: memory allocator.<br>2. superblock: 描述 block 資訊。<br>3. superblock example. |
| 11 | [02:15:09](https://youtu.be/0oABzHrZDPY?si=tRio_y2TebmxmXhP&t=8109) | 1. high-level strategy.<br>2. Big objects: mmap().<br>3. memory free.<br>4. LIFO: 盡可能用已經用過的。<br>5. Locking. |
| 12 | [02:27:17](https://youtu.be/0oABzHrZDPY?si=7PMH9WN6BIadJtVW&t=8837) | 1. performance argument: lockfree allocator.<br>2. cacheline alignment.<br>3. simple coherence model.<br>4. false sharing is bad. |
| 13 | [02:45:11](https://youtu.be/0oABzHrZDPY?si=LER85Xim5fNL2ALm&t=9911) | 1. kmem_caches().<br>2. caches(memory pool).<br>3. superblocks to slabs.<br>4. small system: bookkeeping 佔比太大。<br>5. Conclusion.

# Part 3

| Section | Time| Description |
| -------- | -------- | -------- |
| 1 | [00:00:11](https://youtu.be/9Kj7TBrvP-8?si=9k62eGS11IHQQ8hW&t=11) | 1. 前情提要。<br>2. Mimalloc: Microsoft Research 開發的完全 lock-free 記憶體管理器。<br>3. 論文：Mimalloc: Free List Sharding in Action.<br>4. 各種 malloc 數據比較。|
| 2 | [00:19:11](https://youtu.be/9Kj7TBrvP-8?si=9yHuUVzxD7UQC-3-&t=1151) | 1. Page cache.<br>2. mmap().<br>3. file descriptor: 號碼牌。<br>4. fopen() 回傳是一個 struct 指標。 |
| 3 | [00:39:25](https://youtu.be/9Kj7TBrvP-8?si=IB5oeDy1CCgSYrJa&t=2365) | 1. kernel 如何讀檔案給 user.<br>2. The address space abstraction.<br>3. anonymous map.<br>4. 回顧 “stack of function call”. |
| 4 | [00:50:35](https://youtu.be/9Kj7TBrvP-8?si=YpIig-DCjKW7EzOr&t=3035) | 1. page walker 的重要性。<br>2. File mappings.<br>3. VMA to a file. |
| 5 | [01:03:35](https://youtu.be/9Kj7TBrvP-8?si=PjOMw06AqNFpZzOp&t=3815) | 1. lsof().<br> 2. The radix tree.<br>3. Copy-on-write(COW).<br>4. File-backed mapping. |
| 6 | [01:17:46](https://youtu.be/9Kj7TBrvP-8?si=zY6ONjwiZimufWQE&t=4666) | 1. mmap /dev/mem.<br>2. flip-flop circuits.<br>3. PWM: 利用數位訊號做出類比的效果(e.g. 呼吸燈)。|
| 7 | [01:32:38](https://youtu.be/9Kj7TBrvP-8?si=Cn6GEX8u8frXweFt&t=5558) | 1. control register / data register.<br>2. direct memory access.<br>3. directly access IO port. |
| 8 | [01:40:00](https://youtu.be/9Kj7TBrvP-8?si=54KWUQWs0l1k-DOo&t=6000) | 1. fsync() / fdatasync().<br>2. buffer cache pages.<br>3. How to implement sync? |
| 9 | [01:50:43](https://youtu.be/9Kj7TBrvP-8?si=CzYIqmsxGrhCACV8&t=6643) | 1. superblock 的概念.<br>2. superblock 裡面的 dirty list 紀錄資料變更。<br>3. Asynchronous flushing: pdflush().|
| 10 | [01:59:30](https://youtu.be/9Kj7TBrvP-8?si=xsKUZHUORaw0QW6m&t=7170) | 1. Buffer head.<br>2. Page frame reclaiming.<br>3. swapping / overcommit. |
| 11 | [02:16:43](https://youtu.be/9Kj7TBrvP-8?si=LutlFAA4jLmcstZ2&t=8203) | 1. swap a page out.<br>2. overlays and swapping. |
| 12 | [02:30:10](https://youtu.be/9Kj7TBrvP-8?si=T5oT_20_X-RFYnm4&t=9010) | 1. shared memory.<br>2. reverse mapping.<br>3. 投影片 "20 years of Linux Virtual Memory."<br>4. KSM: kernel same-page merging.