系統(tǒng)中的進程與其他進程共享CPU和主存含滴。首先進程多需要的內(nèi)存也多，其次內(nèi)存易被破壞，如進程A不小心寫入進程B使用的內(nèi)存航徙。為更有效管理內(nèi)存且少出錯，系統(tǒng)提供對主存的抽象概念叫虛擬內(nèi)存陷虎。虛擬內(nèi)存是硬件異常到踏、硬件地址翻譯、主存尚猿、磁盤文件和內(nèi)核的完美交互窝稿，為每個進程提供大的、一致的和私有的地址空間凿掂，虛擬內(nèi)存提供三個重要能力：

1. 使用主存更有效率：用 DRAM 作為部分的虛擬地址空間的緩存
2. 簡化內(nèi)存管理：每個進程都有統(tǒng)一的線性地址空間
3. 隔離地址空間：進程間不會相互影響伴榔；用戶程序不能訪問內(nèi)核信息和代碼

1 地址空間

物理地址通常應(yīng)用在“簡單”的嵌入式微控制器中（汽車、電梯等）庄萎，內(nèi)存管理較簡單踪少，但現(xiàn)代計算機，包括其他智能設(shè)備如筆記本電腦糠涛、智能手機等援奢，需要較復(fù)雜的內(nèi)存管理機制，因此虛擬地址必不可少忍捡，它是計算機科學中最偉大的ideas之一集漾。

image-20220129134301513

image-20220129134359009

2 虛擬內(nèi)存作為緩存工具

概念上來說，虛擬內(nèi)存就是存儲在磁盤上的 N 個連續(xù)字節(jié)的數(shù)組锉罐。磁盤上數(shù)組的內(nèi)容被緩存在物理內(nèi)存上（DRAM緩存））帆竹，其中的每個緩存塊(cache block)就稱為頁(page)，如下圖所示：

image-20220125135801064

任何時刻脓规，虛擬頁都可分為三個部分：

• 未分配的：VM系統(tǒng)還未分配或創(chuàng)建的頁栽连，不占用任何磁盤空間
• 緩存的：已緩存在主存中的已分配的頁
• 未緩存的：未緩存在物理內(nèi)存中的已分配頁

具體看上圖：0和3未分配，1侨舆、4秒紧、6被緩存在物理內(nèi)存，2挨下、5熔恢、7被分配但未緩存在主存

2.1 DRAM緩存組織

和之前的 cache memory類似，將訪問速度快的作為訪問速度慢的緩存臭笆，利用DRAM比磁盤快一萬倍叙淌，將磁盤數(shù)據(jù)盡量緩存在DRAM中（同樣DRAM比SRAM慢10倍秤掌，也可將SRAM作為緩存），所以需盡可能從 DRAM中拿數(shù)據(jù)鹰霍。為此需要：

• 更大的頁尺寸(page size)：通常是 4KB闻鉴，Linux"huge pages"是2M到1G
• 全相聯(lián)(Fully associative)：每一個虛擬頁(virual page)可以放在任意的物理頁(physical page)中，映射函數(shù)很復(fù)雜茂洒，不同于緩存孟岛，無法在硬件中實現(xiàn)，置換算法較昂貴
• 通常使用 Write-back 而非 Write-through 機制
  • Write-through: 命中后更新緩存督勺，同時寫入到內(nèi)存中
  • Write-back: 直到這個緩存需要被置換出去渠羞，才寫入到內(nèi)存（需dirty bit表示緩存中數(shù)據(jù)是否和內(nèi)存中相同，因為可能某時刻內(nèi)存中對應(yīng)地址的數(shù)據(jù)已更新智哀，重復(fù)寫入就會導致原有數(shù)據(jù)丟失）

2.2 頁表

頁表是一個元素為頁表項(PTE, page table entry)的數(shù)組次询，頁表項把虛擬頁映射到物理頁上。PTE由1個有效位和n個地址字段組成盏触。在 DRAM 中渗蟹，每個進程都有自己的頁表，具體如下：

image-20220125141404058

2.2.1 頁命中

訪問的虛擬地址的頁在DRAM緩存中赞辩，則叫頁命中雌芽，命中時由于在 DRAM 中有對應(yīng)的數(shù)據(jù)，可直接訪問辨嗽。不命中時世落，由于DRAM中沒有對應(yīng)數(shù)據(jù)，所以需從磁盤復(fù)制到DRAM中糟需，具體為：

• MMU觸發(fā) Page fault異常
• 將模式升級為內(nèi)核模式
• 調(diào)用軟件頁面錯誤處理程序
• Page fault handler選擇DRAM中要被置換的page屉佳，并把數(shù)據(jù)從磁盤復(fù)制到DRAM中，復(fù)制的等待時間稱為demand paging
• 重新執(zhí)行訪問指令洲押，這時候就會是page hit

2.2.2 處理頁錯誤

image-20220125143502513

image-20220125143645793

image-20220125144058702

image-20220125144706961

image-20220125150040888

在磁盤和內(nèi)存之間傳送頁的活動叫交換或頁面調(diào)度武花。頁從磁盤換入（或頁面調(diào)入）DRAM和從DRAM換出（或頁面調(diào)出）磁盤。一直等待直到最后時刻杈帐，當不命中發(fā)生時才換入頁面的策略叫按需頁面調(diào)度体箕，所有現(xiàn)代操作系統(tǒng)都使用按需頁面調(diào)度方式。

2.2.3 完成頁錯誤

頁錯誤處理程序執(zhí)行返回中斷指令（iret）返回：

• 像ret指令但恢復(fù)特權(quán)級別
• 返回造成錯誤的指令

image-20220125150120919

2.2.4 分配頁

image-20220125151159033

只有當出現(xiàn) page fault 的時候才將數(shù)據(jù)拷貝到內(nèi)存挑童，即按需頁面調(diào)度

2.2.5 局部性原理

• 虛擬內(nèi)存看起來不高效累铅，但因局部性原理，虛擬內(nèi)存非常高效
• 任何時刻程序都傾向于訪問一組稱為工作集的活動的虛擬頁站叼，局部性越好程序工作集越小
  • 工作集大小<內(nèi)存大小娃兽，進程有良好性能
  • 工作集大小>內(nèi)存大小，多個進程同時運行尽楔，頁面不斷被交換（復(fù)制）進或出投储，也叫抖動

3 作為內(nèi)存管理工具

每個進程都有自己的虛擬地址空間第练，這些地址空間可以看作是簡單的線性空間（但實際上在物理內(nèi)存中可能是間隔、分散的）轻要，映射函數(shù)通過物理內(nèi)存分散地址复旬，好的映射函數(shù)可提升局部性垦缅，具體的映射過程如圖：

image-20220125152536328

作為內(nèi)存管理工具：

• 簡化內(nèi)存分配：每個虛擬頁都可被映射到任何物理頁上冲泥。虛擬頁可在不同時間存在不同物理頁上
• 簡化共享：每個進程都有自己私有的代碼、數(shù)據(jù)壁涎、堆及棧不與其他進程共享凡恍，為操作系統(tǒng)提供進程和系統(tǒng)間共享代碼和數(shù)據(jù)的機制，映射不同進程的虛擬頁到同樣的物理頁（也就是上圖 PP 6 的狀況怔球，只讀）
• 簡化鏈接和加載：每個程序有相同的抽象嚼酝，有相似的虛擬地址空間，Code竟坛、data闽巩、heap段開始于相同的地址；execve為.text和.data節(jié)分配虛擬頁并創(chuàng)建標記為invalid的頁表項（PTEs）担汤；根據(jù)虛擬內(nèi)存系統(tǒng)的需要將.text和.data段逐頁復(fù)制

image-20220125153501332

4 作為內(nèi)存保護工具

任何現(xiàn)代計算機系統(tǒng)必須為操作系統(tǒng)提供手段控制對內(nèi)存系統(tǒng)的訪問涎跨，不應(yīng)允許進程修改只讀代碼段，也不許讀或修改任何內(nèi)核中的代碼和數(shù)據(jù)結(jié)構(gòu)崭歧。不許讀或改其他進程私有地址隅很，不許改任何與其他進程共享的虛擬頁面，除非所有共享者都顯式允許這么做（通過調(diào)用明確的進程間通信系統(tǒng)調(diào)用）

使用權(quán)限位擴展PTEs率碾，高位是表示權(quán)限的位叔营，MMU 檢查這些位進行權(quán)限控制（讀、寫所宰、執(zhí)行）绒尊，如下圖所示：

image-20220125154102852

5 地址翻譯

5.1 地址翻譯符號

地址空間可分為：

• 線性地址空間：連續(xù)非負整數(shù)地址的有序集合，{0, 1, 2, 3 ... }
• 虛擬地址空間：N=2^n的虛擬地址集合仔粥，{0, 1, 2, 3, ..., N-1}
• 物理地址空間：M=2^m的物理地址集合婴谱，{0, 1, 2, 3, ..., M-1}

地址翻譯：MAP: V → P U {}

• MAP(a) = a’：若虛擬地址a中的數(shù)據(jù)在P中的物理地址a '上
• MAP(a) = {}：若虛擬地址a中的數(shù)據(jù)不在物理內(nèi)存中（無效或存儲在磁盤）

開始之前先來了解以下參數(shù)：

• N=2^n：虛擬地址空間中的地址數(shù)量
• M=2^m：物理地址空間中的地址數(shù)量
• P=2^p：頁的大小（字節(jié)）

虛擬地址(VA, Virtual Address)中的元素：

• TLBI：TLB索引
• TLBT：TLB標記(tag)
• VPO：虛擬頁偏移量
• VPN：虛擬頁號

物理地址(PA, physical address)中的元素：

• PPO：物理頁偏移（與 VPO 的值相同）
• PPN：物理頁號
• CO：緩存偏移字節(jié)
• CI：緩存索引
• CT：緩存標簽

image-20220126104734332

5.2 用頁表進行地址翻譯

image-20220125170346736

具體的訪問過程為：

1. 通過虛擬地址找到頁表(page table)中對應(yīng)的條目
2. 檢查有效位(valid bit)件炉，是否需要觸發(fā)頁錯誤(page fault)
3. 根據(jù)頁表中的物理頁編號(physical page number)找到內(nèi)存中對應(yīng)地址
4. 把實際地址和虛擬頁偏移(virtual page offset)拼接即為最終的物理地址

這里又分兩種情況：Page Hit 和 Page Fault

5.2.1 page hit

image-20220125171002529

1. 處理器生成一個虛擬地址勘究，并把它傳給MMU
2. MMU生成PTE地址，并從高速緩存/主存請求得到它
3. 高速緩存/主存向MMU返回PTE
4. MMU構(gòu)造物理地址并把它傳送給高速緩存/內(nèi)存
5. 高速緩存/內(nèi)存返回所請求的數(shù)據(jù)字給處理器

5.2.2 page fault

image-20220125171259859

1. 處理器生成一個虛擬地址斟冕，并把它傳給MMU
2. MMU生成PTE地址口糕，并從高速緩存/主存請求得到它
3. 高速緩存/主存向MMU返回PTE
4. 有效位為零，所以MMU觸發(fā)頁故障異常磕蛇，傳遞CPU控制到系統(tǒng)內(nèi)核中缺頁異常處理程序
5. 處理程序?qū)ふ冶恢脫Q頁(如果頁臟景描，則將其換出到磁盤)
6. 處理程序從磁盤找到對應(yīng)頁并載入內(nèi)存/緩存并更新內(nèi)存中的PTE
7. 處理程序返回到原始進程十办，重啟出錯指令，CPU將引起缺頁的虛擬地址重新發(fā)給MMU超棺，由于已緩存在主存故會命中

5.3 結(jié)合虛擬內(nèi)存和高速緩存

在既有虛擬內(nèi)存又有SRAM高速緩存的系統(tǒng)中向族，是使用虛擬地址還是物理地址訪問SRAM高速緩存的討論有很多，但大多數(shù)系統(tǒng)用物理尋址棠绘，這樣多個進程共享虛擬頁和存儲的值件相，無需處理保護問題，因為訪問權(quán)限的檢查是地址翻譯過程的一部分氧苍。雖然緩存已經(jīng)很快了夜矗，但還能更快，主要思路是地址翻譯發(fā)生在高速緩存查找之前让虐，直接在 MMU和內(nèi)存之間加上L1緩存紊撕，于是就有了另外一種設(shè)計，如圖：

image-20220125172353442

頁表條目(PTE)像任何其他內(nèi)存中的數(shù)據(jù)一樣緩存在L1中赡突，PTE可能被其他數(shù)據(jù)驅(qū)逐对扶；PTE命中仍然需要一個小的L1延遲，解決辦法是使用Translation Lookaside Buffer(TLB)惭缰。TLB可以認為是頁表在處理芯片上的緩存浪南，是MMU中的小型集關(guān)聯(lián)硬件緩存，將虛擬頁號映射到物理頁號从媚，大多數(shù)頁表條目位于L1高速緩存逞泄，但被稱為TLB的頁表條目的片上高速緩存，包含少量頁的完整頁表條目拜效，通撑缰冢回消除訪問L1上的頁表條目的開銷。MMU使用虛擬地址的VPN部分位訪問TLB：

image-20220125173754024

如圖是TLB命中和不命中的兩種情況：

image-20220129171530524

若TLB不命中時紧憾，MMU必須從L1緩存中取出相應(yīng)的PTE到千，新取出的PTE存放在TLB中可能覆蓋已存在的條目（這里未畫出L1緩存，下面Interl Core i7部分畫出cpu中的L1緩存和MMU的TLB）

這里順便復(fù)習下前面的緩存結(jié)構(gòu)：

image-20220126104202992

這里 VPN + VPO 就是虛擬地址赴穗，同樣分成三部分憔四，分別用于匹配標簽、確定集合般眉，若TLB命中了赵，直接返回對應(yīng)頁表項(PTE)，否則甸赃，就要從緩存/內(nèi)存中獲取柿汛，并更新 TLB 的對應(yīng)集合。幸好不命中很少發(fā)生

image-20220125174126742

5.4 多級頁表

因為虛擬地址的位數(shù)比物理內(nèi)存的位數(shù)要大得多埠对，所以保存頁表項(PTE) 所需要的空間也是一個問題络断。例如：

假設(shè)每個頁的大小是 4KB（2的12次方）裁替，每個地址有 48 位，一條 PTE 記錄有 8 個字節(jié)貌笨，那么要全部保存下來弱判，需要的大小是：

2^48×2?12×2³⁼²39bytes = 512G

所以采用多層頁表，第一層的頁表中的條目指向第二層的頁表锥惋，一個一個索引下去昌腰，最終尋找具體的物理地址，如圖是二級頁表：

image-20220125175038605

K級頁表翻譯過程如下：

image-20220125175131141

5.5 地址翻譯實例

來看一個簡單的例子净刮，我們的內(nèi)存系統(tǒng)設(shè)定如下：

• 虛擬地址14 位
• 物理地址12 位
• 頁大小 64 字節(jié)

image-20220126111639666

簡單內(nèi)存系統(tǒng)的TLB的配置為：

• 存儲 16 條記錄
• 4個集合

image-20220126113022597

簡單內(nèi)存系統(tǒng)頁表：

image-20220126114813071

簡單內(nèi)存系統(tǒng)緩存：

• 16 行剥哑，每個塊 4 個字節(jié)
• 物理地址
• 直接映射（即 16 個集合）

image-20220126112017349

虛擬地址：0x03D4，在TLB中找到index為3的set淹父，且其tag為3的PPN為0D，加上前面的虛擬地址的VPO即為最終的物理地址

得到物理地址怎虫，在緩存中找到idx為暑认，tag為0D，且CO為0大审，則值為36

image-20220126121208245

虛擬地址為0x0020蘸际，雖然TLB中去找到編號為0的set且tag為0的緩存，但為0徒扶，所以TLB Miss了粮彤，從頁表中找到緩存PPN為2，則物理地址為0x0A20

image-20220126152151089

接下來找到idx為8的緩存姜骡，但tag不匹配导坟，故未命中緩存，只能重新讀取

image-20220126152452617

5.6 Intel Core i7內(nèi)存系統(tǒng)

image-20220126152942700

5.6.1 Intel Core i7 內(nèi)存翻譯

image-20220126153132476

5.6.2 Core i7 1-3層頁表項

image-20220126153501798

5.6.3 Core i7 4級頁表項

image-20220126153611237

5.6.4 加速技巧

將1）MMU將地址翻譯成物理地址2）將物理地址傳送到L1高速緩存圈澈。這兩步驟部分重疊惫周，故也加速對L1高速緩存的訪問。

image-20220126161457485

• 在虛擬地址和物理地址中確定CI的位
• 當?shù)刂贩g時康栈，可以將索引存入緩存
• 通常用TLB递递，PPN位（CT位）可很快得到
• 虛擬索引，物理標記
• 仔細調(diào)整緩存大小

6 Linux進程中的虛擬地址

Linux為每個進程維護單獨的虛擬地址空間啥么，包括內(nèi)核虛擬內(nèi)存和進程虛擬內(nèi)存登舞。前者某些區(qū)域被映射到所有進程共享的物理頁面，如每個進程共享內(nèi)核的代碼和全局數(shù)據(jù)結(jié)構(gòu)悬荣。有趣的是菠秒，Linux也將一組連續(xù)的虛擬頁面（大小等于系統(tǒng)中DRAM的總量）映射到相應(yīng)的一組連續(xù)的物理頁面，為內(nèi)核提供便利的方法訪問物理內(nèi)存中特定位置隅熙。

image-20220126163723576

6.1 Linux將虛擬內(nèi)存組織為“區(qū)域”集合

Linux將虛擬內(nèi)存組織稱一些區(qū)域（也叫段）的集合稽煤，區(qū)域就是已經(jīng)存在著的（已分配的）虛擬內(nèi)存的連續(xù)片核芽，這些頁以某種方式相關(guān)聯(lián)。如代碼段酵熙、數(shù)據(jù)段轧简、堆、共享庫段以及用戶棧都市不同區(qū)域匾二，每個存在的虛擬頁都抱存在某個區(qū)域中哮独，而不屬于某個區(qū)域的虛擬頁是不存在的，且不能被進程引用察藐。區(qū)域的概念很重要皮璧，因為它允許虛擬地址空間有間隙，內(nèi)核不用記錄那些不存在的虛擬頁分飞，而這樣的頁也不占用內(nèi)存悴务、磁盤或內(nèi)核本身中的任何資源。

image-20220126164112156

6.2 Linux頁異常處理

缺頁異常步驟：

1. 虛擬地址A是否和法：缺頁處理程序搜索區(qū)域結(jié)構(gòu)的鏈表譬猫，把A和每個區(qū)域結(jié)構(gòu)中的vm_start和vm_end做比較讯檐，若該指令不合法，則缺頁處理程序就出發(fā)一個段錯誤染服，從而終止該進程别洪，對應(yīng)下圖中的1
2. 內(nèi)存訪問是否合法：進程是否有讀、寫或執(zhí)行這個區(qū)域內(nèi)頁面的權(quán)限柳刮，如是不是因為運行在用戶模式的進程試圖從內(nèi)核虛擬內(nèi)存中讀取字造成挖垛，若訪問不合法則觸發(fā)缺頁異常，從而終止該進程秉颗，對應(yīng)圖中的2
3. 合法虛擬地址進行合法操作：按調(diào)度算法選擇一個頁痢毒，若該頁被修改過，將其交換出去換入新頁并更新頁表站宗。缺頁處理程序返回時闸准，CPU重新啟動引起缺頁的指令，該指令再次發(fā)A到MMU梢灭，這次就能正常翻譯A

image-20220126164209986

6.3 內(nèi)存映射

將虛擬內(nèi)存的areas與磁盤對象關(guān)聯(lián)并初始化的機制叫內(nèi)存映射夷家。area可通過磁盤的普通文件（如可執(zhí)行文件），初始化來自文件的一部分為頁敏释，或者匿名文件库快，首次錯誤將分配一個寫滿0的物理頁，一旦頁被寫（臟）就跟其他頁一樣钥顽。無論哪種情況义屏，一旦虛擬頁面被初始化了，它就在由內(nèi)核維護的專門的交換文件間換來換取，任何時刻闽铐，交換空間都限制著當前運行著的進程能分配的虛擬頁面的總數(shù)蝶怔。

6.3.1 共享對象

若虛擬內(nèi)存系統(tǒng)可集成到傳統(tǒng)的文件系統(tǒng)中，就能提供一種簡單而高效的把程序和數(shù)據(jù)加載到內(nèi)存中的方法兄墅。

很多進程都有同樣的只讀代碼區(qū)域踢星，且許多程序需訪問只讀運行時庫代碼的相同副本，如每個C程序都需標準C庫的printf函數(shù)隙咸，若每個進程都在主存中保持這些代碼的副本沐悦，就極端浪費。

一個對象可被映射到虛擬內(nèi)存的一個區(qū)域五督，要么作為共享對象桌粉，要么作為私有對象（非共享）蜂挪。

多個進程可共享相同的對象，虛擬地址可以有差異锐涯，但差異必須是頁大小的倍數(shù)

image-20220126211027901

6.3.2 私有的寫時復(fù)制對象

image-20220126211253809

對于每個映射私有對象的進程咙冗，相應(yīng)私有區(qū)域的頁表條目都被標記為只讀缺前，且該區(qū)域被標記為私有的寫時復(fù)制会放。一旦寫入則觸發(fā)保護錯誤盖腿，處理程序在主存中創(chuàng)建試圖寫私有的寫時復(fù)制區(qū)域中的一個頁面該頁面的信服本，更新頁表條目指向該新副本愈捅，再恢復(fù)該頁面可寫權(quán)限。指令在處理程序返回時重新執(zhí)行慈鸠，拷貝盡可能被推遲蓝谨。

image-20220126211658092

再看fork函數(shù)，當被當前進程調(diào)用時青团，創(chuàng)建當前進程的mm_struct譬巫、區(qū)域結(jié)構(gòu)和頁表的原樣副本。將兩個進程中的每個頁面都標記為只讀督笆，并將兩進程中每個區(qū)域結(jié)構(gòu)都標記為私有的寫時復(fù)制芦昔。fork返回時，新進程虛擬內(nèi)存和調(diào)用fork時存在的虛擬內(nèi)存相同娃肿，當兩進程中任一個后來進行寫操作咕缎，寫時復(fù)制機制就創(chuàng)建新頁面，因此也就為每個進程保持私有地址空間的抽象概念料扰。

再看execve假設(shè)執(zhí)行execve("a.out",NULL,NULL)該函數(shù)在當前進程中加載并運行包含在可執(zhí)行目標文件a.out中的程序凭豪，用a.out替代當前程序，需以下步驟：

• 刪除已存在的用戶區(qū)域：刪除當前進程虛擬地址的用戶部分中的已存在的區(qū)域結(jié)構(gòu)

• 映射私有區(qū)域：為新程序代碼晒杈、數(shù)據(jù)嫂伞、bss和棧區(qū)域常見新的區(qū)域結(jié)構(gòu)，所有這些新區(qū)域都是私有的、寫時復(fù)制的

• 映射共享區(qū)域：若a.out程序與共享對象鏈接帖努，先動態(tài)鏈接撰豺，再映射到用戶虛擬地址空間中的共享區(qū)域內(nèi)

• 設(shè)置程序計數(shù)器：設(shè)置當前進程上下文中的程序計數(shù)器，使之指向代碼區(qū)域入口點

  image-20220129220952271

6.3.3 找到可共享的頁

內(nèi)核相同頁歸并：

• 系統(tǒng)掃描所有物理內(nèi)存拼余，尋找重復(fù)頁污桦，找到則歸并為單個頁，標記為寫時拷貝
• 在2009年的Linux內(nèi)核實現(xiàn)姿搜，僅限于標記為可能的頁寡润，特別是處理器運行許多虛擬機時特別有用

6.3.4 用戶模式的內(nèi)存映射

函數(shù)void *mmap(void *start, int len,int prot, int flags, int fd, int offset)，從文件描述副fd指定的文件偏移量offset舅柜，從start地址（可能為0）開始映射len字節(jié)梭纹，prot表示權(quán)限（PROT_READ、PROT_WRITE致份、 PROT_EXEC）变抽，flags表示映射權(quán)限（MAP_ANON、 MAP_PRIVATE氮块、MAP_SHARED等）绍载，返回映射區(qū)域開始的指針（可能不是start）

image-20220126212909402

6.3.5 mmap的使用

使用分頁機制將大文件讀入內(nèi)存，共享數(shù)據(jù)結(jié)構(gòu)滔蝉，當調(diào)用帶MAP_SHARED的標簽時击儡，多進程可訪問相同內(nèi)存區(qū)域，很危險蝠引⊙舻基于文件的數(shù)據(jù)結(jié)構(gòu)例如數(shù)據(jù)庫，將prot設(shè)置為PROT_READ和PROT_WRITE螃概，當解除映射時矫夯，文件通過寫入被更新，通過文件加載/更新/寫回文件實現(xiàn)吊洼。

6.3.6 用mmap實現(xiàn)attack lab

當機器堆棧不能執(zhí)行時训貌，如何通過代碼注入進行攻擊，解決方法是使用mmap分配內(nèi)存并標記為可執(zhí)行冒窍，轉(zhuǎn)移堆棧到該區(qū)域递沪，執(zhí)行攻擊代碼，恢復(fù)原來堆棧超燃，移除映射區(qū)域区拳。

image-20220126214013583

image-20220126214448926

7 動態(tài)內(nèi)存分配

程序員通過動態(tài)內(nèi)存分配器（如 malloc）讓程序在運行時得到虛擬內(nèi)存，因為程序經(jīng)常直到實際運行時才知道某些數(shù)據(jù)結(jié)構(gòu)大小意乓。動態(tài)內(nèi)存分配器管理一個虛擬內(nèi)存區(qū)域樱调，稱為堆(heap)约素。

分配器以塊為單位來維護堆，可分配或釋放笆凌。有兩種類型的分配器：

• 顯式分配器：應(yīng)用分配并且回收空間（C 語言中的 malloc 和 free）
• 隱式分配器：應(yīng)用只負責分配圣猎，但是不負責回收（Java 中的new和垃圾收集）

7.1 相關(guān)函數(shù)

• malloc：失敗返回空指針并設(shè)置errno=ENOMEM，成功返回指向至少請求字節(jié)大小的內(nèi)存塊的指針
• free：將參數(shù)p指向的塊返回到可用內(nèi)存池乞而，p必須來自先前調(diào)用的malloc送悔、calloc、realloc
• calloc：將已分配的塊初始化為0的malloc版本
• realloc：改變先前分配的快的大小
• sbrk：分配器內(nèi)部使用爪模，用于增加或縮小堆

先來看看一個簡單的使用 malloc 和 free 的例子

#include <stdio.h>
#include <stdlib.h>

void foo(int n) {
    int i, *p;
    
    /* Allocate a block of n ints */
    p = (int *) malloc(n * sizeof(int));
    if (p == NULL) {
        perror("malloc");
        exit(0);
    }
    
    /* Initialize allocated block */
    for (i=0; i<n; i++)
        p[i] = i;

    /* Return allocated block to the heap */
    free(p);
}

為了講述方便欠啤，我們做如下假設(shè)：

• 內(nèi)存地址按照字來編碼
• 每個字的大小和整型一致

例如：

image-20220126220729562

可以用任意的順序發(fā)送 malloc 和 free 請求，但free 請求必須作用與已被分配的 block屋灌。

顯式分配器的限制：

• 不能控制已分配塊的數(shù)量和大小
• 必須立即響應(yīng) malloc 請求（不能緩存或者給請求重新排序）
• 必須在未分配的內(nèi)存中分配
• 不同的塊需要對齊（32 位中 8 byte洁段，64 位中 16 byte）
• 只能操作和修改未分配的內(nèi)存
• 不能移動已分配的塊，不允許壓縮共郭，為什么祠丝？

7.2 性能指標

假設(shè)給定 malloc 和 free 的請求的序列：

R0,R1,...,Rk,...,Rn?1R0,R1,...,Rk,...,Rn?1

目標是盡可能提高吞吐量以及內(nèi)存利用率（注意，這兩個目標常常是沖突的）

吞吐量是在單位時間內(nèi)完成的請求數(shù)量除嘹。假設(shè)在 10 秒中之內(nèi)進行了 5000 次 malloc 和 5000 次 free 調(diào)用写半，那么吞吐量是 1000 operations/second

另外一個目標是 Peak Memory Utilization，就是最大的內(nèi)存利用率尉咕。其次最小化開銷叠蝇，定義總負載Pk表示請求Rk完成時的當前已分配的載荷之和，當前堆大小Hk（假定Hk是單調(diào)非遞減）年缎，則K+1次請求的開銷Ok = Hk / (maxi≤k P i ) – 1.0

image-20220126222619739

7.3 內(nèi)存碎片

影響內(nèi)存利用率的主要因素就是『內(nèi)存碎片』蟆肆，分為內(nèi)部碎片和外部碎片兩種。

內(nèi)部碎片

內(nèi)部碎片指的是存儲的數(shù)據(jù)(payload)小于塊大小晦款，就會因?qū)R和維護堆所需的數(shù)據(jù)結(jié)構(gòu)或明確的決策（如返回大塊滿足小的請求）的緣故而出現(xiàn)無法利用的空間，例如：

image-20220126222956760

內(nèi)部碎片只依賴于之前的請求的具體模式

外部碎片

內(nèi)存中有足夠的空間枚冗，但是空間不連續(xù)缓溅，所以成為了碎片，取決于未來請求的模式

image-20220126223246988

實現(xiàn)細節(jié)

如何實現(xiàn)高效的內(nèi)存分配算法赁温？在具體實現(xiàn)之前坛怪，需要考慮以下問題：

• 給定一個指針，如何知道需要釋放多少內(nèi)存股囊？
• 如何記錄未分配的塊袜匿？
• 當分配的結(jié)構(gòu)小于所在的空閑塊時，如何處理多余的空間?
• 有多個區(qū)域滿足條件稚疹，如何選擇居灯？
• 如何重用已經(jīng)釋放的塊？

如何實現(xiàn)回收

標準方法：在塊開頭記錄塊的長度（包括塊頭），每個分配的塊需額外的字節(jié)

image-20220126223826411

具體這部分書中提到了四種方法：

1. 隱式列表 Implicit List：在首部記錄長度怪嫌，鏈接所有塊
2. 顯式列表 Explicit List：用指針的空閑塊的顯式列表
3. 分離的空閑列表 Segregated Free List：不同大小的不同鏈表
4. 按大小對塊排序 Blocks Sorted by Size：使用平衡樹（如紅黑樹）义锥，每個空閑塊都有指針，長度作為鍵

8 跟蹤自由塊

8.1 隱式空閑列表

每個塊都記錄大小和分配狀態(tài)岩灭，只需一個字節(jié)拌倍，當塊對齊時，一些低階地址位總是0噪径，與其存儲始終為0的位柱恤，不如將其作為已分配/空閑標志。當讀取Size字節(jié)時找爱，必須屏蔽該位

image-20220127153706405

image-20220127153855386

8.1.1 數(shù)據(jù)結(jié)構(gòu)

image-20220127154214347

8.1.2 頭訪問

image-20220127154347468

8.1.3 遍歷鏈表

image-20220127154608686

8.1.4 找到一個空閑塊

如何確定哪部分空間合適梗顺，有三種方法：

1. First Fit: 每次都從頭進行搜索，找到第一個合適的塊缴允，線性查找
2. Next Fit: 每次從上次搜索結(jié)束的位置繼續(xù)搜索荚守，避免重復(fù)搜索沒有幫助的塊，速度較快练般，但可能會有更多碎片矗漾，一些研究表明碎片化教糟糕
3. Best Fit: 每次遍歷列表，找到剩余字節(jié)最少最合適的塊薄料，碎片較少敞贡，通常可提高內(nèi)存利用率摄职，但是速度最慢誊役，仍是貪婪算法，沒最優(yōu)保證

image-20220127155513077

8.1.5 分配空閑塊

由于已分配空間可能小于空閑空間谷市，可以分割塊

image-20220127160440445

8.1.6 釋放塊

最簡單的實現(xiàn)方式是清除“已分配”的標記蛔垢，但可能導致錯誤的碎片化

image-20220127160956590

8.1.7 合并

若下一個/前一個塊是空閑的，則連接合并

image-20220127161205002

8.1.8 雙向合并

在前面的基礎(chǔ)上迫悠，在空閑塊的“底部”記錄塊的大小鹏漆，允許反向遍歷列表，但需額外空間创泄，邊界標簽（Knuth73）

image-20220127161802568

8.1.9 通過footers實現(xiàn)

image-20220127162300697

image-20220127162659576

image-20220127162921043

8.1.10 常數(shù)時間合并

總共四種情況艺玲，這里以第一種為例：

image-20220127163104867

image-20220127163242896

注意：對于頭和尾需要加上"dummy footer"，標記為已分配鞠抑，防止在釋放第一塊和最后一塊時意外合并

8.1.11 高層malloc/free代碼

malloc/free不常用饭聚，因為線性時間分配，多用于特殊目的應(yīng)用

const size_t dsize = 2*sizeof(word_t);
void *mm_malloc(size_t size)
{
    size_t asize = round_up(size + dsize, dsize);
    block_t *block = find_fit(asize);
    
    if (block == NULL)
        return NULL;
    
    size_t block_size = get_size(block);
    write_header(block, block_size, true);
    write_footer(block, block_size, true);
    
    split_block(block, asize);
    
    return header_to_payload(block);
}
void mm_free(void *bp)
{
    block_t *block = payload_to_header(bp);
    size_t size = get_size(block);
    
    write_header(block, size, false);
    write_footer(block, size, false);
    
    coalesce_block(block);
}

8.1.12 邊界標簽缺點

導致內(nèi)部碎片搁拙，footer標簽?zāi)鼙粌?yōu)化秒梳，未使用一位代表已分配/未分配法绵，除次之外使用多一位表示前一塊是否分配

image-20220127170341545

也有四種情況，這里以第一種情況為例：

image-20220127170413970

8.2 顯式空閑列表

維護空閑列表塊端幼，而不是所有塊礼烈，下一個/上一個空閑塊可能在任何地方，所以需存儲前向/后向指針婆跑，而不僅是塊大小此熬，合并仍需邊界標簽，根據(jù)記憶順序找到相鄰的塊

image-20220128145515753

image-20220128145548059

8.2.1 釋放塊

在空閑列表的什么地方放新釋放的塊滑进？

• 無序：LIFO（Last in First out）犀忱、FIFO（First in First out），簡單但花費時間扶关，研究表明碎片化比按地址序更糟
• 地址序：插入空閑塊阴汇，以便空閑塊總按地址順序排列，需搜索

同樣對于釋放內(nèi)存塊也有4種情況节槐，這里以第四種情況做簡要說明：

image-20220128151412793

8.2.2 一些實現(xiàn)的技巧建議

使用循環(huán)雙向鏈表搀庶，但數(shù)據(jù)結(jié)構(gòu)支持多種方法，要么保持自由指針固定要么作為搜索列表移動

8.2.3 顯式空閑列表總結(jié)

分配是空閑塊數(shù)量的線性時間铜异，而不是所有塊哥倔。由于需在列表中插入和取出塊，因此分配和自由更復(fù)雜揍庄。但需要額外的鏈接空間

8.3 分割列表分配器

每個大小塊類都有自己的空閑列表

image-20220128152714405

8.3.1 分割分配器

給定一個自由列表數(shù)組咆蒿，每個都是一定大小的類，分配一個大小為n的塊蚂子，搜索大小為m>n的塊沃测，若找到合適的塊，分割塊并放碎片在適當?shù)牧斜硎尘ィ魶]有塊被發(fā)現(xiàn)蒂破，嘗試下個更大的種類。重復(fù)直到塊被找到别渔。用sbrk從系統(tǒng)請求額外的堆內(nèi)存寞蚌，從該新內(nèi)存分配n個字節(jié)的塊，將剩余的塊作為一個單獨的空閑塊放在適當大小的類中钠糊。

8.3.2 分割分配器優(yōu)點

• 更高的吞吐量：種類大小的2次冪的對數(shù)時間vs線性時間
• 更好的內(nèi)存利用率：對隔離的自由列表的First-fit搜索近似對整個堆的最佳搜索；極端情況是給每個塊一個自己的大小的類相當于best-fit

8.4 內(nèi)存陷阱

關(guān)于內(nèi)存的使用需要注意避免以下問題：

• 解引用錯誤指針
• 讀取未初始化的內(nèi)存
• 覆蓋內(nèi)存
• 引用不存在的變量
• 多次釋放同一塊
• 引用已釋放的塊
• 釋放塊失敗

8.4.1 解引用錯誤指針

沒有引用對應(yīng)的地址壹哺，少了 &

int val;
...
scanf("%d", val);

8.4.2 讀取未初始化的內(nèi)存

不能假設(shè)堆中的數(shù)據(jù)會自動初始化為 0抄伍，如：

/* return y = Ax */
int *matvec(int **A, int *x) {
    int *y = malloc(N * sizeof(int));
    int i, j;
    
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            y[i] += A[i][j] * x[j];
    return y;
}

8.4.3 覆蓋內(nèi)存

第一種是分配錯誤的大小，下面的例子中管宵，一開始不能用 sizeof(int)截珍，因為指針的長度不一定和 int 一樣攀甚。

int **p;
p = malloc(N * sizeof(int));

for (i = 0; i < N; i++) 
    p[i] = malloc(M * sizeof(int));

第二個問題是超出分配的空間，下面代碼的 for 循環(huán)中岗喉，因為使用了 <=秋度，會寫入到其他位置

int **p;

p = malloc(N * sizeof (int *));

for (i = 0; i <= N; i++)
    p[i] = malloc(M * sizeof(int));

第三種是因為沒有檢查字符串的長度，超出部分就寫到其他地方去了（經(jīng)典的緩沖區(qū)溢出攻擊也是利用相同的機制）

char s[8];
int i;

gets(s); /* reads "123456789" from stdin */

第四種是沒有正確理解指針的大小以及對應(yīng)的操作钱床，應(yīng)該使用 sizeof(int *)

int *search(int *p, int val) {
    while (*p && *p != null)
        p += sizeof(int);
    
    return p;
}

第五種是引用了指針荚斯，而不是其指向的對象，下面的例子中查牌，*size-- 一句因為 -- 的優(yōu)先級比較高事期，所以實際上是對指針進行了操作，正確的應(yīng)該是 (*size)--

int *BinheapDelete(int **binheap, int *size) {
    int *packet;
    packet = binheap[0];
    binheap[0] = binheap[*size - 1];
    *size--;
    Heapify(binheap, *size, 0);
    return (packet);
}

8.4.4 引用不存在的變量

下面的情況中纸颜，沒有注意到局部變量會在函數(shù)返回的時候失效（所以對應(yīng)的指針也會無效）兽泣，這是傳引用和返回引用需要注意的，傳值的話則不用擔心

int *foo() {
    int val;
    
    return &val;
}

8.4.5 多次釋放同一塊內(nèi)存

這個不用多說胁孙，不能重復(fù)搞兩次

x = malloc(N * sizeof(int));
//  <manipulate x>
free(x);

y = malloc(M * sizeof(int));
//  <manipulate y>
free(x);

8.4.6 引用已釋放的塊

同樣是很明顯的錯誤唠倦，不要犯

x = malloc(N * sizeof(int));
//  <manipulate x>
free(x);
//  ....

y = malloc(M * sizeof(int));
for (i = 0; i < M; i++)
    y[i] = x[i]++;

8.4.7 內(nèi)存泄漏

用完沒有釋放，就是內(nèi)存泄露啦

foo() {
    int *x = malloc(N * sizeof(int));
    // ...
    return ;
}

或者只釋放了數(shù)據(jù)結(jié)構(gòu)的一部分：

struct list {
    int val;
};

foo() {
    struct list *head = malloc(sizeof(struct list));
    head->val = 0;
    head->next = NULL;
    //...
    free(head);
    return;
}

9 垃圾回收

垃圾回收自動回收堆分配的存儲涮较，程序不必顯式地釋放內(nèi)存稠鼻，這種機制在許多動態(tài)語言中都有實現(xiàn)：Python, Ruby, Java, Perl, ML, Lisp, Mathematica。C 和 C++ 中也有變種法希，但是注意枷餐，不可能回收所有垃圾。

如何知道什么東西才是垃圾苫亦？只要沒有任何指針指向的地方毛肋，不管有沒有用，因為都不可能被使用屋剑，當然可以直接清理掉润匙。不過這其實是需要一些前提條件的：

• 可以知道哪里是指針，哪里不是指針
• 每個指針都指向 block 的開頭
• 指針不能被隱藏(by coercing them to an int, and then back again)

相關(guān)算法如下：

• Mark-and-sweep collection (McCarthy, 1960)
• Reference counting (Collins, 1960)
• Copying collection (Minsky, 1963)
• Generational Collectors(Lieberman and Hewitt, 1983)

9.1 Mark&Sweep垃圾收集器

可在malloc/free包之上構(gòu)建唉匾，用malloc分配直到空間耗盡孕讳。當空間不足時，在每個塊的頭用額外的標記位標記巍膘，標記階段標記出根節(jié)點所有可達的和已分配的后繼厂财，在每個可達的塊上設(shè)置標記位，后面的清除釋放每個未被標記的已分配塊

image-20220128224150627

9.2 簡單實現(xiàn)

• 應(yīng)用：

  • new(n)：返回指向清除所有位置的新塊的指針
  • read(b,i)：讀塊b在i處的值到寄存器
  • wreite(b,i,v)：寫v到塊b的i處

• 每個塊都有一個頭：塊b的頭的地址是b[-1]峡懈，在不同的收集器中用于不同目的

• 垃圾收集器使用的指令：is_ptr(p)檢測p是否是指針璃饱，length(b)返回塊b的長，不包括頭肪康，get_roots()返回所有的roots

image-20220128224017850

10 總結(jié)

首先介紹虛擬內(nèi)存等方面的知識荚恶，具體來說：

• 從程序員角度看虛擬內(nèi)存：
  • 每個進程有自己的私有線性地址空間
  • 不能被其他進程破壞
• 從系統(tǒng)角度看虛擬內(nèi)存：
  • 通過緩存虛擬內(nèi)存頁更有效地使用內(nèi)存（局部性原理）
  • 簡化內(nèi)存管理和編程撩穿，提供方便的位檢查權(quán)限，簡化內(nèi)存保護
• 組合硬件和軟件實現(xiàn)：
  • MMU谒撼、TLB食寡、各種控制寄存器、異常處理機制是硬件部分
  • 管理頁表廓潜、頁置換算法抵皱、管理文件系統(tǒng)、頁異常處理茉帅、TLB管理是OS軟件部分

其次簡要介紹了動態(tài)內(nèi)存分配的基本概念和管理動態(tài)內(nèi)存分配的三種算法叨叙。最后提及了垃圾回收的基本原理和內(nèi)存使用中常見的錯誤。

本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布堪澎！