tags: linux2022

Linux 記憶體管理筆記

Linux 地址映射

• 在 Linux 內部的記憶體地址映射過程為邏輯地址 –> 線性地址–> 實體地址 (PA)

邏輯地址

• 在 X86 平台，Intel 為了兼容，將遠古時代的段式內存管理方式保留了下來。邏輯地址指的是機器語言指令中，用來指定一個操作數或者是一條指令的地址。
  • 一個邏輯地址，是由一個段標識符加上一個指定段內相對地址的偏移量，表示為 [段標識符：段內偏移量]
  • 段標示符（segment descriptor）：
    
    
  • 邏輯位址轉線性位址：首先，給定一個完整的邏輯地址[段選擇符：段內偏移地址]，
    1. 看段選擇符的 T1 = 0 還是 1，知道當前要轉換是 GDT 中的段，還是 LDT 中的段，再根據相應寄存器，得到其地址和大小。我們就有了一個數組了。
    2. 拿出段選擇符中前 13 位，可以在這個數組中，查找到對應的段描述符，這樣 Base，即基地址就知道了。
    3. 把Base + offset，就是要轉換的線性地址了。
       

邏輯地址 in Linux

• 按照 Intel 的本意，全局的用 GDT，每個進程自己的用 LDT。 不過Linux則對所有的進程都使用了相同的段來對指令和數據尋址。即用戶數據段，用戶代碼段，對應的，內核中的是內核數據段和內核代碼段。
  • 在Linux下，邏輯地址與線性地址總是一致（是一致，不是有些人說的相同）的，即邏輯地址的偏移量字段的值與線性地址的值總是相同的
• 在 Linux 中的邏輯地址對應於線性地址，也就是說 Intel 為了相容過往架構，把硬體設計搞得很複雜，Linux 核心的實作則予以簡化，並且在支援其他處理器架構時，儘量保持該原則。

線性地址

• 線性地址規則：如圖所示，這部分由 MMU 完成，其中在 IA32 架構下，涉及到主要的暫存器有 CR0, CR3。
  

實體地址

• 在匯流排中傳輸的數位信號。

實體記憶體管理

Buddy System

• Buddy System 是 Linux 一種記憶體管理機制，將連續的記憶體空間（以 page size 為單位）按照大小分類 (etc. 2^0, 2^1…)，如此一來可以更快的找到可使用的記憶體空間。
• 如果要分配 3 pages，去 4 pages 的列表裡面取一個，分配 3 個之後將剩下的 1 個放回去。
  
• 命令檢視
  

slab/slob/slub

slab

• 在許多處理器架構上，buddy system 每次分配記憶體都以 page (4KB）為單位，但系統執行時絕大部分的資料結構都是很小的，為一個小物件分配 4KB 顯然不划算。Linux 中使用 slab 來解決小物件的分配。
  • Buddy System 和 slab 不是二選一的關係，slab 記憶體分配器是對 Buddy System 的補充。
• slab 背後的思想是緩存經常使用的 object，並保持在初始狀態給 Kernel 使用。如果一個 object 被釋放了，他仍然會以初始的狀態存放在 slab，以供下次使用。

• slab allocator 是由一組 cache 所組成。 這些 cache 由叫做 cache chain 的 double circular linked list 連接在一起。
• 每一個 cache 由多個 slab 組成，slab 是 slab 分配器的最小單位，在實現上一個 slab 有一個或多個連續的物理頁組成（通常只有一頁）。單個 slab 可以在 slab 連結串列之間移動。
  • 例如：如果一個「半滿 slabs_partial 連結串列」被分配了物件後變滿了，就要從 slabs_partial 中刪除，同時插入到「全滿 slabs_full 連結串列」中去。
• 核心 slab 物件的分配過程是這樣的：
  1. 如果 slabs_partial連結串列還有未分配的空間，分配物件，若分配之後變滿，移動 slab 到slabs_full 連結串列。
  2. 如果 slabs_partial連結串列沒有未分配的空間，進入下一步。
  3. 如果slabs_empty 連結串列還有未分配的空間，分配物件，同時移動 slab 進入 slabs_partial連結串列。
  4. 如果slabs_empty為空，請求夥伴系統分頁，建立一個新的空閒slab， 按步驟 3 分配物件。

slab coloring

• 如果 object 打包放入 slab 後還有剩餘空間，這些剩餘空間將被用來將 slab 著色。不同的顏色代表不同的偏移量，避免相同大小的 object 放在同一個 cache line。
• 因為相同大小的 object 很有可能會放在相同的 CPU cache line，所以可能遇到不同 slab 中，相同大小的 object 映射到同一個 cache line 中。當同時讀取這兩個 object 時，他們可能會在 cache 與 RAM 之間不停地切換。
  • 假設對象 A,B 均為 32B ，且 A 的地址從 0 開始， B 的地址從 16K 開始，則根據組相聯或直接相聯映射方式 （全相聯方式很少使用）， A,B 對像很可能映射到 cache 的第 0 行 ，此時，如果 CPU 交替的訪問 A,B 各 50 次，每一次訪問 cache 第 0 行都失效，從而需要從 Memory 傳送數據。
  • 而 slab 著色就是為解決該問題產生的，不同的顏色代表了不同的起始對象偏移量，對於 B 對象，如果將其位置偏移向右偏移 32B ，則其可能會被映射到 cache 的第 1 行上，這樣交替的訪問 A,B 各 50 次，只需要 2 次內存訪問即可。

Virtual Memory

分頁和位址的構成

• 記憶體位址的操作可以分爲頁號和頁內的偏移量。
  

Page Fault

1. Major: This is the mechanism used by an operating system to increase the amount of program memory available on demand. The operating system delays loading parts of the program from disk until the program attempts to use it and the page fault is generated. If the page is not loaded in memory at the time of the fault, then it is called a major or hard page fault.
   • The page fault handler in the OS needs to find a free location: either a free page in memory, or a non-free page in memory. This latter might be used by another process, in which case the OS needs to write out the data in that page (if it has not been written out since it was last modified) and mark that page as not being loaded in memory in its process page table.
   • Once the space has been made available, the OS can read the data for the new page into memory, add an entry to its location in the memory management unit, and indicate that the page is loaded.
   • Thus major faults are more expensive than minor faults and add storage access latency to the interrupted program's execution.
2. Minor: 軟性分頁錯誤指分頁錯誤發生時，相關的頁已經被載入進記憶體，但是沒有向 MMU 註冊的情況。作業系統只需要在 MMU 中註冊相關頁對應的實體位址即可。
   • 發生這種情況的可能性之一：是一塊實體記憶體被兩個或多個程式共享，作業系統已經為其中的一個裝載並註冊了相應的頁，但是沒有為另一個程式註冊。
   • 可能性之二，是該頁已被從CPU的工作集中移除（工作集過大時），但是尚未被交換到磁碟上。
3. Invalid: If a page fault occurs for a reference to an address that is not part of the virtual address space, meaning there cannot be a page in memory corresponding to it, then it is called an invalid page fault.
   • The page fault handler in the operating system will then generally pass a segmentation fault to the offending process, indicating that the access was invalid; this usually results in abnormal termination of the code that made the invalid reference.

page table handling

Copy-on-Write

• Copy-on-Write (COW) allows 2 (both parent and child) processes to initially share the same pages in memory
  • 事實上不一定要是parent和child的關係，只要OS發現有二個task「可以」共用page即可
• If either process modifies a shared page, a copy of the shared page is created
• COW allows more efficient process creation as only modified pages are copied (UNIX’s fork())
  • 對Linux來說，fork主要的耗時在：複製task_struct及其附屬結構、複製並修改分頁表格（for child）、修改分頁表格（for parent，要將parent的page table中的r/w改成ro）、同步化TLB與分頁表格

User Space Memory Allocator

malloc

• malloc 用於申請使用者空間的虛擬記憶體，當申請小於 128KB 小記憶體的時， malloc 使用 sbrk 或 brk 分配記憶體；當申請大於 128KB 的記憶體時，使用 mmap 函式申請記憶體。

存在問題

• 由於 brk/sbrk/mmap 屬於系統呼叫，如果每次申請記憶體都要產生系統呼叫開銷，cpu 在使用者態和核心態之間頻繁切換，非常影響效能。
• 而且，堆是從低地址往高地址增長，如果低地址的記憶體沒有被釋放，高地址的記憶體就不能被回收，容易產生記憶體碎片。

解決

• 因此， malloc 採用的是記憶體池的實現方式，先申請一大塊記憶體，然後將記憶體分成不同大小的記憶體塊，然後使用者申請記憶體時，直接從記憶體池中選擇一塊相近的記憶體塊分配出去。

Kernel Memory Allocator

• 一般策略
  • chunk < 128 KiB → kmalloc()
  • chunk > 128 KiB → vmalloc()

kmalloc

• kmalloc() 分配的虛擬地址範圍在核心空間的「直接記憶體對映區」。
• 按位元組為單位虛擬記憶體，一般用於分配小塊記憶體，釋放記憶體對應於 kfree ，可以分配連續的實體記憶體。函式原型在 <linux/kmalloc.h> 中宣告，一般情況下在驅動程式中都是呼叫 kmalloc() 來給資料結構分配記憶體 。
• kmalloc 是基於slab 分配器的 ，同樣可以用cat /proc/slabinfo 命令，檢視 kmalloc 相關 slab 物件資訊，下面的 kmalloc-8、kmalloc-16 等等就是基於slab分配的 kmalloc 快取記憶體。

vmalloc

• Obtains a physically discontiguous block
• Unsuitable for DMA on some platforms

參考

• 我理解的邏輯地址、線性地址、物理地址和虛擬地址
• Linux 核心設計: 記憶體管理
• https://wellbay.cc/thread-1532004.htm
• https://blog.csdn.net/weixin_38537730/article/details/104520736
• https://groups.google.com/g/pongba/c/qSkUL0_fC_E?pli=1
• pthread - 中正大學資訊工程學系