url: https://mit-public-courses-cn-translatio.gitbook.io/mit6-s081/lec17-virtual-memory-for-applications-frans/17.1-ying-yong-cheng-xu-shi-yong-xu-ni-nei-cun-suo-xu-yao-de-te-xing

---

17.1 應用程序使用虛擬內存所需要的特性

今天的話題是用戶應用程序使用的虛擬內存，它主要是受這篇1991年的論文的啟發。

首先，你們已經知道了，操作系統內核以非常靈活的方式使用了虛擬內存Page Table。你們已經通過Lazy Allocation Lab，Copy on Write Lab，以及XV6中的各種內存實現了解到了這一點。而今天論文中的核心觀點是，用戶應用程序也應該從靈活的虛擬內存中獲得收益，也就是說用戶應用程序也可以使用虛擬內存。用戶應用程序本身就是運行在虛擬內存之上，我們這里說的虛擬內存是指：User Mode或者應用程序想要使用與內核相同的機制，來產生Page Fault并響應Page Fault（注，詳見Lec08，內核中幾乎所有的虛擬內存技巧都基于Page Fault）。也就是說User Mode需要能夠修改PTE的Protection位（注，Protection位是PTE中表明對當前Page的保護，對應了4.3中的Writeable和Readable位）或者Privileged level。今天的論文，通過查看6-7種不同的應用程序，來說明用戶應用程序使用虛擬內存的必要性。這些應用程序包括了：

• Garbage Collector
• Data Compression Application
• Shared Virtual Memory

你可以發現這都是一些非常不同的應用程序，并且它們都依賴虛擬內存的一些特性來正常工作。所以第一個問題是，上面的應用程序需要的特性是什么？所以我們先來討論一下需要的特性是什么？

• 首先，你需要trap來使得發生在內核中的Page Fault可以傳播到用戶空間，然后在用戶空間的handler可以處理相應的Page Fault，之后再以正常的方式返回到內核并恢復指令的執行。這個特性是必須的，否則的話，你不能基于Page Fault做任何事情。
• 第二個特性是Prot1，它會降低了一個內存Page的accessability。accessability的意思是指內存Page的讀寫權限。內存Page的accessability有不同的降低方式，例如，將一個可以讀寫的Page變成只讀的，或者將一個只讀的Page變成完全沒有權限。
• 除了對于每個內存Page的Prot1，還有管理多個Page的ProtN。ProtN基本上等效于調用N次Prot1，那為什么還需要有ProtN？因為單次ProtN的損耗比Prot1大不了多少，使用ProtN可以將成本分攤到N個Page，使得操作單個Page的性能損耗更少。在使用Prot1時，你需要修改PTE的bit位，并且在Prot1的結束時，需要清除TLB（注，詳見4.4 Translation Lookaside Buffer），而清除TLB比較費時。如果能對所有需要修改的內存Page集中清理一次TLB，就可以將成本分攤。所以ProtN等效于修改PTE的bit位N次，再加上清除一次TLB。如果執行了N次Prot1，那就是N次修改PTE的bit位，再加上清除N次TLB，所以ProtN可以減少清除TLB的次數，進而提升性能。
• 下一個特性是Unprot，它增加了內存Page的accessability，例如將本來只讀的Page變成可讀可寫的。
• 除此之外，還需要能夠查看內存Page是否是Dirty。
• 以及map2。map2使得一個應用程序可以將一個特定的內存地址空間映射兩次，并且這兩次映射擁有不同的accessability（注，也就是一段物理內存對應兩份虛擬內存，并且兩份虛擬內存有不同的accessability）。

XV6在用戶程序中支持以上任意的特性嗎？除了有類似于trap及其相關的alarm hander之外，XV6不支持任何一個以上的特性。XV6只有一個最小化的Unix接口，并不支持以上任何虛擬內存特性。盡管在XV6的內核中包含了所有的可用的虛擬內存的機制，但是并沒有以系統調用的形式將它們暴露給用戶空間。論文的觀點是，任何一個好的操作系統都應該以系統調用的形式提供以上特性，以供應用程序使用。

所以自然的，這就引出了另一個問題，當今的Unix系統的功能范圍是什么？以上特性屬于Unix的范疇嗎？如果你查看現在的Unix系統，例如Linux，你會發現，或許并不與論文中描述的完全一樣，但是這些特性都存在。在論文那個年代（1991年），某些操作系統只包含了部分以上特性，但是如今這些特性都已經在現代的Unix系統中廣泛支持了。接下來我們看一下如何實現這些特性。

---

17.2 支持應用程序使用虛擬內存的系統調用

第一個或許也是最重要的一個，是一個叫做mmap的系統調用。它接收某個對象，并將其映射到調用者的地址空間中。舉個例子，如果你想映射一個文件，那么你需要將文件描述符傳遞給mmap系統調用。mmap系統調用有許多令人眼花繚亂的參數（注，mmap的具體說明可以參考man page）：

• 第一個參數是一個你想映射到的特定地址，如果傳入null表示不指定特定地址，這樣的話內核會選擇一個地址來完成映射，并從系統調用返回。
• 第二個參數是想要映射的地址段長度len。
• 第三個參數是Protection bit，例如讀寫R|W。
• 第四個參數我們會跳過不做討論，它的值可以是MAP_PRIVATE。它指定了如果你更新了傳入的對象，會發生什么。（注，第四個參數是flags，MAP_PRIVATE是其中一個值，在mmap文件的場景下，MAP_PRIVATE表明更新文件不會寫入磁盤，只會更新在內存中的拷貝，詳見man page）。
• 第五個參數是傳入的對象，在上面的例子中就是文件描述符。
• 第六個參數是offset。

通過上面的系統調用，可以將文件描述符指向的文件內容，從起始位置加上offset的地方開始，映射到特定的內存地址（如果指定了的話），并且連續映射len長度。這使得你可以實現Memory Mapped File，你可以將文件的內容帶到內存地址空間，進而只需要方便的通過普通的指針操作，而不用調用read/write系統調用，就可以從磁盤讀寫文件內容。這是一個方便的接口，可以用來操縱存儲在文件中的數據結構。實際上，你們將會在下個lab實現基于文件的mmap，下個lab結合了XV6的文件系統和虛擬內存，進而實現mmap。

mmap還可以用作他途。除了可以映射文件之外，還可以用來映射匿名的內存（Anonymous Memory）。這是sbrk（注，詳見8.2）的替代方案，你可以向內核申請物理內存，然后映射到特定的虛擬內存地址。

mmap是實現應用程序虛擬內存的核心系統調用之一，我們稍后會將它與之前提到的特性關聯起來。

除此之外，還需要有一些系統調用來支持論文中討論到的特性。

mprotect系統調用（注，詳見man page）。當你將某個對象映射到了虛擬內存地址空間，你可以修改對應虛擬內存的權限，這樣你就可以以特定的權限保護對象的一部分，或者整個對象。

舉個例子，通過上圖對于mprotect的調用將權限設置成只讀（R），這時，對于addr到addr+len這段地址，load指令還能執行，但是store指令將會變成Page Fault。類似的，如果你想要將一段地址空間變成完成不可訪問的，那么可以在mprotect中的權限參數傳入None，那么任何對于addr到addr+len這段地址的訪問，都會生成Page Fault。

對應mmap還有一個系統調用munmap，它使得你可以移除一個地址或者一段內存地址的映射關系。如果你好奇這里是怎么工作的，你應該查看這些系統調用的man page。

最后一個系統調用是sigaction，它本質上是用來處理signal。它使得應用程序可以設置好一旦特定的signal發生了，就調用特定的函數。可以給它傳入函數f作為特定signal的handler。在Page Fault的場景下，生成的signal是segfault。你或許之前在用戶代碼中看過了segfault，通常來說當發生segfault時，應用程序會停止運行并crash。但是如果應用程序為segfault signal設置了handler，發生segfault時，應用程序不會停止，相應的handler會被內核調用，然后應用程序可以在handler中響應segfault。

當內核發現Page Fault時，或許會通過修復Page Table來使得應用程序還能繼續執行。與內核響應Page Fault的方式類似，在這里的handler中或許會調用mprotect來修改內存的權限來避免segfault，這樣應用程序的指令就可以恢復運行。

與sigaction類似的有sigalarm（譯注：sigalarm 是traps lab 中實現的一個系統調用，不屬于標準Unix 接口），在sigalarm中可以設置每隔一段時間就調用handler。sigaction也可以實現這個功能，只是它更加的通用，因為它可以響應不同類型的signal。

學生提問 --------------------------------------------------- start
學生提問：看起來mprotect暗示了你可以為單獨的地址添加不同的權限，然而在XV6中，我們只能為整個Page設置相同的權限，這里是有區別嗎？

Frans教授：不，這里并沒有區別，它們都在Page粒度工作。如果你好奇的話，有一個單獨的系統調用可以查看Page的大小。
學生提問 --------------------------------------------------- end

如果你回想前面提到過的虛擬內存特性，我們可以將它們對應到這一節描述的Unix接口中來。

• trap對應的是sigaction系統調用
• Prot1，ProtN和Unprot可以使用mprotect系統調用來實現。mprotect足夠的靈活，你可以用它來修改一個Page的權限，也可以用它來修改多個Page的權限。當修改多個Page的權限時，可以獲得只清除一次TLB的好處。
• 查看Page的Dirty位要稍微復雜點，并沒有一個直接的系統調用實現這個特性，不過你可以使用一些技巧完成它，我稍后會介紹它。
• map2也沒有一個系統調用能直接對應它，通過多次調用mmap，你可以實現map2特性。

或許并不完全受這篇論文所驅動，但是內核開發人員已經在操作系統中為現在的應用程序提供了這些特性。接下來，我將在框架層面簡單介紹一下這些特性是如何實現的，之后再看看應用程序是如何使用這些特性。

---

17.3 虛擬內存系統如何支持用戶應用程序

有關實現，有兩個方面較為有趣。

第一個是虛擬內存系統為了支持這里的特性，具體會發生什么？這里我們只會討論最重要的部分，并且它也與即將開始的mmap lab有一點相關，因為在mmap lab中你們將要做類似的事情。在現代的Unix系統中，地址空間是由硬件Page Table來體現的，在Page Table中包含了地址翻譯。但是通常來說，地址空間還包含了一些操作系統的數據結構，這些數據結構與任何硬件設計都無關，它們被稱為Virtual Memory Areas（VMAs）。VMA會記錄一些有關連續虛擬內存地址段的信息。在一個地址空間中，可能包含了多個section，每一個section都由一個連續的地址段構成，對于每個section，都有一個VMA對象。連續地址段中的所有Page都有相同的權限，并且都對應同一個對象VMA（例如一個進程的代碼是一個section，數據是另一個section，它們對應不同的VMA，VMA還可以表示屬于進程的映射關系，例如下面提到的Memory Mapped File）。

舉個例子，如果進程有一個Memory Mapped File，那么對于這段地址，會有一個VMA與之對應，VMA中會包含文件的權限，以及文件本身的信息，例如文件描述符，文件的offset等。在接下來的mmap lab中，你們將會實現一個非常簡單版本的VMA，并用它來實現針對文件的mmap系統調用。你可以在VMA中記錄mmap系統調用參數中的文件描述符和offset。

第二個部分我們了解的就不多了，它或許值得仔細看一下，也就是User level trap是如何實現的？我們假設一個PTE被標記成invalid或者只讀，而你想要向它寫入數據。這時，CPU會跳轉到kernel中的固定程序地址，也就是XV6中的trampoline代碼（注，詳見6.2）。kernel會保存應用程序的狀態，在XV6中是保存到trapframe。之后再向虛擬內存系統查詢，現在該做什么呢？虛擬內存系統或許會做點什么，例如在lazy lab和copy-on-write lab中，trap handler會查看Page Table數據結構。而在我們的例子中會查看VMA，并查看需要做什么。舉個例子，如果是segfault，并且應用程序設置了一個handler來處理它，那么

• segfault事件會被傳播到用戶空間
• 并且通過一個到用戶空間的upcall在用戶空間運行handler
• 在handler中或許會調用mprotect來修改PTE的權限
• 之后handler返回到內核代碼
• 最后，內核再恢復之前被中斷的進程。

當內核恢復了中斷的進程時，如果handler修復了用戶程序的地址空間，那么程序指令可以繼續正確的運行，如果哪里出錯了，那么會通過trap再次回到內核，因為硬件還是不能翻譯特定的虛擬內存地址。

學生問答 ------------------------------------------------------------ start
學生提問：當我們允許用戶針對Page Fault來運行handler代碼時，這不會引入安全漏洞嗎？

Frans教授：這是個很好的問題。會有安全問題嗎？你們怎么想的？這會破壞User/kernel或者不同進程之間的隔離性嗎？或者從另一個角度來說，你的問題是sigalarm會破壞隔離性嗎？

當我們執行upcall的時候，upcall會走到設置了handler的用戶空間進程中，所以handler與設置了它的應用程序運行在相同的context，相同的Page Table中。所以handler唯一能做的事情就是影響那個應用程序，并不能影響其他的應用程序，因為它不能訪問其他應用程序的Page Table，或者切換到其他應用程序的Page Table。所以這里還好。

當然，如果handler沒有返回，或者做了一些壞事，最終內核還是會殺掉進程。所以唯一可能出錯的地方就是進程傷害了自己，但是它不能傷害任何其他進程。
學生問答 ------------------------------------------------------------ end

---

17.4 構建大的緩存表

接下來，我將通過介紹幾個例子來看一下如何使用之前介紹的內容。我會從一個非常簡單的例子開始，之后我們會看一下Garbage Collector，因為很多同學都問了Garbage Collector的問題，所以GC是一個可以深入探討的好話題。

首先我想討論的是一個非常簡單的應用，它甚至都沒有在論文中提到，但它卻是展示這節課的內容非常酷的一個方法。這個應用里是構建一個大的緩存表，什么是緩存表？它是用來記錄一些運算結果的表單。舉個例子，你可以這么想，下面是我們的表單，它從0開始到n。表單記錄的是一些費時的函數運算的結果，函數的參數就是0到n之間的數字。

如果這個表單在最開始的時候就預計算好了，那么當你想知道f(i)的結果是什么時，你需要做的就是查看表單的i槽位，并獲取f(i)的值。這樣你可以將一個費時的函數運算轉變成快速的表單查找，所以這里一個酷的技巧就是預先將費時的運算結果保存下來。如果相同的計算需要運行很多很多次，那么預計算或許是一個聰明的方案。

這里的挑戰是，表單可能會很大，或許會大過物理內存，這里可以使用論文提到的虛擬內存特性來解決這個挑戰。

首先，你需要分配一個大的虛擬地址段，但是并不分配任何物理內存到這個虛擬地址段。這里只是從地址空間獲取了很大一段地址，并說我將要使用地址空間的這部分來保存表單。

但是現在表單中并沒有內容，表單只是一段內存地址。如果你現在查找表單的i槽位，會導致Page Fault。所以這里的計劃是，在發生Page Fault時，先針對對應的虛擬內存地址分配物理內存Page，之后計算f(i)，并將結果存儲于tb[i]，也就是表單的第i個槽位，最后再恢復程序的運行。

這種方式的優勢是，如果你需要再次計算f(i)，你不需要在進行任何費時的計算，只需要進行表單查找。即使接下來你要查找表單的i+1槽位，因為一個內存Page可能可以包含多個表單項，這時也不用通過Page Fault來分配物理內存Page。

不過如果你一直這么做的話，因為表單足夠大，你最終還是會消耗掉所有的物理內存。所以Page Fault Handler需要在消耗完所有的內存時，回收一些已經使用過的物理內存Page。當然，你需要修改已經被回收了的物理內存對應的PTE的權限，這樣在將來使用對應地址段時，就可以獲得Page Fault。所以你需要使用Prot1或者ProtN來減少這些Page的accessbility。

學生問答 --------------------------------------------- start
學生提問：在分配物理內存Page時，我們需要讓操作系統映射到地址空間的特定地址，否則的話可能會映射到任意地址，是吧？

Frans教授：操作系統會告知是哪個地址，并且這里可能是任意的地址。
學生問答 --------------------------------------------- end

為了更具體的描述這里的應用，我這里有個小的實現，我們可以看一看這里是如何使用現有的Unix特性。

在main函數中，首先調用setup_sqrt_region函數，它會從地址空間分配地址段，但是又不實際分配物理Page。之后調用test_sqrt_region。

在test_sqrt_region中，會以隨機數來遍歷表單，并通過實際運算對應的平方根值，來檢查表單中相應位置值是不是保存了正確的平方根值。在test_sqrt_region運行的過程中，會產生Page Fault，因為現在還并沒有分配任何物理內存Page。

應用程序該如何收到Page Fault呢？

在setup_sqrt_region函數中有一段代碼，通過將handle_sigsegv函數注冊到了SIGSEGV事件。這樣當segfault或者Page Fault發生時，內核會調用handle_sigsegv函數。

handle_sigsegv函數與你們之前看過很多很多次的trap代碼非常相似。

• 它首先會獲取觸發Page Fault的地址，
• 之后調用mmap對這個虛擬內存地址分配一個物理內存Page（注，這里是mmap映射匿名內存）。這里的虛擬內存地址就是我們想要在表單中用來保存數據的地址。
• 然后我們為這個Page中所有的表單項都計算對應的平方根值，之后就完事了。

這個應用程序有點極端，它在運行的時候只會使用一個物理內存Page，所以不論上一次使用的Page是什么，在handle_sigsegv的最后都會通過munmap釋放它。所以我們有一個巨大的表單，但是它只對應一個物理內存Page。

接下來我將運行一下這個應用程序。test_sqrt_region會隨機查看表單的內容，所以可以假設這會觸發很多Page Fault，但是可以看出表單中的所有內容都能通過檢查。

所以，盡管這里有一個巨大的表單用來保存平方根，但是實際在物理內存中只有一個內存Page。這是一個簡單的例子，它展示了用戶應用程序使用之前提到的虛擬內存特性之后可以做的一些酷的事情。

學生問答 ----------------------------------------------------------- start
學生提問：能再講一下為什么一個物理內存Page就可以工作嗎？我覺得這像是lazy allocation，但是區別又是什么呢？

Frans教授：當我們剛剛完成設置時，我們一個內存Page都沒有，setup_sqrt_region分配了一個地址段，但是又立即通過munmap將與這個地址段關聯的內存釋放了。所以在啟動的最開始對于表單并沒有一個物理內存Page與之關聯。

之后，當我們得到了一個Page Fault，這意味著整個表單對應的地址中至少有一個Page沒有被映射，雖然實際上我們一個Page都沒有映射。現在我們得到了一個Page Fault，我們只需要映射一個Page，在這個Page中，我們會存入i，i+1。。。的平方根（注，因為一個Page4096字節，一個double8個字節，所以一個Page可以保存512個表單項）。

因為這是第一個Page Fault，之前并沒有映射了內存Page，所以不需要做任何事情。

之后，程序繼續運行并且查找了表單中的更多項，如果查找一個沒有位于已分配Page上的表單項時，會得到另一個Page Fault。這時，在handle_sigsegv會分配第二個內存Page，并為這個Page計算平方根的值。之后會munmap記錄在last_page_base中的內存。

當然，在實際中我們永遠也不會這么做，在實際中至少會保留一些內存Page，這里只是以一種極端的方式展示，你可以只通過內存中的一個Page來表示一個巨大的表單。所以在handle_sigsegv中，會釋放上一次映射的內存Page。

之后程序繼續運行，所以在任何一個時間，只有一個物理內存Page被使用了。很明顯，你們在實際中不會這么做，這里更多的是展示前面提到特性的能力。
學生問答 ----------------------------------------------------------- end

---

17.5 Baker’s Real-Time Copying Garbage Collector

接下來我會討論另一個例子，也就是Garbage Collector（注，后面將Garbage Collector和Garbage Collection都簡稱為GC），并且我也收到了很多有關Garbage Collector的問題。

GC是指編程語言替程序員完成內存釋放，這樣程序員就不用像在C語言中一樣調用free來釋放內存。對于擁有GC的編程語言，程序員只需要調用類似malloc的函數來申請內存，但是又不需要擔心釋放內存的過程。GC會決定內存是否還在使用，如果內存并沒有被使用，那么GC會釋放內存。GC是一個很好的特性，有哪些編程語言帶有GC呢？Java，Python，Golang，幾乎除了C和Rust，其他所有的編程語言都帶有GC。

你可以想象，GC有很大的設計空間。這節課討論的論文并沒有說什么樣的GC是最好的，它只是展示了GC可以利用用戶空間虛擬內存特性。論文中討論了一種特定的GC，這是一種copying GC。什么是copying GC？假設你有一段內存作為heap，應用程序從其中申請內存。你將這段內存分為兩個空間，其中一個是from空間，另一個是to空間。當程序剛剛啟動的時候，所有的內存都是空閑的，應用程序會從from空間申請內存。假設我們申請了一個類似樹的數據結構。樹的根節點中包含了一個指針指向另一個對象，這個對象和根節點又都包含了一個指針指向第三個對象，這里構成了一個循環。

或許應用程序在內存中還有其他對象，但是沒有別的指針指向這些對象，所以所有仍然在使用的對象都可以從根節點訪問到。在某個時間，或許因為之前申請了大量的內存，已經沒有內存空間給新對象了，也就是說整個from空間都被使用了。

Copying GC的基本思想是將仍然在使用的對象拷貝到to空間去，具體的流程是從根節點開始拷貝。每一個應用程序都會在一系列的寄存器或者位于stack上的變量中保存所有對象的根節點指針，通常來說會存在多個根節點，但是為了說明的簡單，我們假設只有一個根節點。拷貝的流程會從根節點開始向下跟蹤，所以最開始將根節點拷貝到了to空間，但是現在根節點中的指針還是指向著之前的對象。

之后，GC會掃描根節點對象。因為程序的運行時知道對象的類型是什么，當然也就知道對象中的指針。接下來GC會將根節點對象中指針指向的對象也拷貝到to空間，很明顯這些也是還在使用中的對象。當一個對象被拷貝到to空間時，根節點中的指針會被更新到指向拷貝到了to空間的對象。

在之后的過程中，我們需要記住這個對象已經被拷貝過了。所以，我們還會存儲一些額外的信息來記住相應的對象已經保存在了to空間，這里會在from空間保留一個forwarding指針。這里將對象從from空間拷貝到to空間的過程稱為forward。

接下來還剩下一個對象，我們將這個對象從from空間拷貝到to空間，這個對象還包含一個指針指向第二個對象。

但是通過查看指針可以看到這個對象已經被拷貝了，并且我們已經知道了這個對象被拷貝到的地址（注，也就是之前在from空間留下的forwarding指針）。所以我們可以直接更新第三個對象的指針到正確的地址。

現在與根節點相關的對象都從from空間移到了to空間，并且所有的指針都被正確的更新了，所以現在我們就完成了GC，from空間的所有對象都可以被丟棄，并且from空間現在變成了空閑區域。

以上就是copying GC的基本思路。論文中討論的是一種更為復雜的GC算法，它被稱為Baker算法，這是一種很老的算法。它的一個優勢是它是實時的，這意味著它是一種incremental GC（注，incremental GC是指GC并不是一次做完，而是分批分步驟完成）。在Baker算法中，我們還是有from和to兩個空間。假設其中還是包含了上面介紹的幾個對象。

這里的基本思想是，GC的過程沒有必要停止程序的運行并將所有的對象都從from空間拷貝到to空間，然后再恢復程序的運行。GC開始之后，唯一必要的事情，就是將根節點拷貝到to空間。所以現在根節點被拷貝了，但是根節點內的指針還是指向位于from空間的對象。根節點只是被拷貝了并沒有被掃描，其中的指針還沒有被更新。

如果應用程序調用了new來申請內存，那就再掃描幾個對象，并將這些對象從from空間forward到to空間。這很好，因為現在我們將拷貝heap中還在使用的所有對象的過程，拆分成了漸進的步驟。每一次調用new都使得整個拷貝過程向前進一步。

當然應用程序也會使用這里對象所指向的指針。舉個例子，現在當根節點需要讀出其指向的一個對象時，這個對象仍然在from空間。這是危險的，因為我們不應該跟蹤from空間的指針（注，換言之GC時的指針跟蹤都應該只在同一個空間中完成）。所以每次獲取一個指針指向的對象時（dereference），你需要檢查對象是否在在from空間，如果是的話，將其從from空間forward到to空間。所以應用程序允許使用指針，但是編譯器需要對每個指針的訪問都包上一層檢查，這樣我們就可以保證在to空間的任何指針指向的是位于to空間的對象。我們需要確保這一點，因為在最后當GC完成了所有對象的跟蹤之后，我們會清空from部分并重用這部分內存。

論文對于這里的方案提出了兩個問題：

• 第一個是每次dereference都需要有以上的額外步驟，每次dereference不再是對于內存地址的單個load或者store指令，而是多個load或者store指令，這增加了應用程序的開銷。
• 第二個問題是并不能容易并行運行GC。如果程序運行在多核CPU的機器上，并且你擁有大量的空閑CPU，我們本來可以將GC運行在后臺來遍歷對象的圖關系，并漸進的拷貝對象。但是如果應用程序也在操作對象，那么這里可能會有搶占。應用程序或許在運行dereference檢查并拷貝一個對象，而同時GC也在拷貝這個對象。如果我們不夠小心的話，我們可能會將對象拷貝兩遍，并且最后指針指向的不是正確的位置。所以這里存在GC和應用程序race condition的可能。

---

17.6 使用虛擬內存特性的GC

論文中介紹，如果擁有了前面提到的虛擬內存特性，你可以使用虛擬內存來減少指針檢查的損耗，并且以幾乎零成本的代價來并行運行GC。這里的基本思想是將heap內存中from和to空間，再做一次劃分，每一個部分包含scanned，unscanned兩個區域。在程序啟動，或者剛剛完成了from和to空間的切換時，整個空間都是unscanned，因為其中還沒有任何對象。

之后的過程與前面描述的相同，在開始GC時，我們將根節點對象拷貝到to空間，但是根節點中的指針還是指向了位于from空間的對象。現在unscanned區域包括了所有的對象（注，現在只有根節點），我們會將unscanned區域的權限設置為None。這意味著，當開始GC之后，應用程序第一次使用根節點，它會得到Page Fault，因為這部分內存的權限為None。

在Page Fault Handler中，GC需要掃描位于內存Page中所有的對象，然后將這些對象所指向的其他對象從from空間forward到to空間。所以，在GC最開始的時候，我們將根節點拷貝過來了；之后在Page Fault Handler中通過掃描，將根節點指向的對象也都拷貝過來了。在我們的例子中根節點指向的只有兩個對象，這兩個對象會被拷貝到unscanned區域中，而根節點會被標記成scanned。在我們掃描完一個內存Page中的對象時，我們可以通過Unprot（注，詳見17.1）恢復對應內存Page的權限。

之后，應用程序就可以訪問特定的對象，因為我們將對象中的指針轉換成了可以安全暴露給應用程序的指針（注，因為這些指針現在指向了位于to空間的對象），所以應用程序可以訪問這些指針。當然這些指針對應的對象中還沒有被掃描。如果dereference這些指針，我們會再次得到Page Fault，之后我們會繼續掃描。

這種方案的好處是，它仍然是遞增的GC，因為每次只需要做一小部分GC的工作。除此之外，它還有額外的優勢：現在不需要對指針做額外的檢查了（注，也就是不需要查看指針是不是指向from空間，如果是的話，將其forward到to空間）。或者說指針檢查還在，只是現在通過虛擬內存相關的硬件來完成了。

學生問答 --------------------------------------------------------------- start

學生提問：剛剛說到在Handler里面會掃描一個Page中的所有對象，但是對象怎么跟內存Page對應起來呢？

Frans教授：在最開始的時候，to空間是沒有任何對象的。當需要forward的時候，我剛剛描述的是拷貝一個對象，但是實際上拷貝的是一個內存Page中的N個對象，這樣它們可以填滿整個Page。所以現在我們在to空間中，有N個對象位于一個Page中，并且它們都沒有被掃描。之后某個時間，Page Fault Handler會被調用，GC會遍歷這個內存Page上的N個對象，并檢查它們的指針。對于這些指針，GC會將對應的對象拷貝到to空間的unscanned區域中。之后，當應用程序使用了這些未被掃描的對象，它會再次得到Page Fault，進而再掃描這些對象，以此類推。

學生提問：在完成了GC之后，會切換from和to空間嗎？

Frans教授：最開始我們使用的是from空間，當用完了的時候，你會將對象拷貝到to空間，一旦完成了掃描，from空間也被完全清空了，你可以切換兩個空間的名字。現在會使用to空間來完成內存分配。直到它也滿了，你會再次切換。

學生問答 --------------------------------------------------------------- end

論文中提到使用虛擬內存的另一個好處是，它簡化了GC的并發。GC現在可以遍歷未被掃描的內存Page，并且一次掃描一個Page，同時可以確保應用程序不能訪問這個內存Page，因為對于應用程序來說，未被掃描的內存Page權限為None。虛擬內存硬件引入了這種顯式的同步機制，或者說對于搶占的保護。

現在只有GC可以訪問未被掃描的內存Page，而應用程序不能訪問。所以這里提供了自動的并發，應用程序可以運行并完成它的工作，GC也可以完成自己的工作，它們不會互相得罪，因為一旦應用程序訪問了一個未被掃描的Page，它就會得到一個Page Fault。而GC也永遠不會訪問掃描過的Page，所以也永遠不會干擾到應用程序。所以這里以近乎零成本獲取到了并發性。

但是實際上有個麻煩的問題。回到我們之前那張圖，我們在heap中有from空間，to空間。在to空間中又分為了unscanned和scanned區域，對于應用程序來說，unscanned區域中的Page權限為None。

這就引出了另一個問題，GC怎么能訪問這個區域的內存Page？因為對于應用程序來說，這些Page是inaccessible。

這里的技巧是使用map2（注，詳見17.1）。這里我們會將同一個物理內存映射兩次，第一次是我們之前介紹的方式，也就是為應用程序進行映射，第二次專門為GC映射。在GC的視角中，我們仍然有from和to空間。在to空間的unscanned區域中，Page具有讀寫權限。

所以GC可以遍歷這些內存Page，讀取內容并forward必要的對象。這里使用了map2將物理內存映射到應用程序地址空間中兩次的能力，其中每次映射都有不同的權限，這樣這里的場景才能工作。

學生問答 -------------------------------------------- start

學生提問：GC和應用程序是不是有不同的Page Table？

Frans教授：不，它們擁有相同的Page Table。它們只是將物理內存映射到了地址空間的兩個位置，也就是Page Table的兩個位置。在一個位置，PTE被標記成invalid，在另一個位置，PTE被標記成可讀寫的。

學生問答 -------------------------------------------- end

---

17.7 使用虛擬內存特性的GC代碼展示

為了更清晰的說明上一節的內容，我這里有個針對論文中方法的簡單實現，我可以肯定它包含了一些bug，因為我并沒有認真的測試它。

首先，應用程序使用的API包括了new和readptr。

readptr會檢查指針是否位于from空間，如果是的話，那么它指向的對象需要被拷貝。當然，當我們使用虛擬內存時，這里的readptr成本會比較低，它會直接返回參數。在這個簡單的例子中，我有一個循環鏈表，并且有兩個根節點，其中一個指向鏈表的頭節點，另一個指向鏈表的尾節點。

應用程序線程的工作是循環1000次，每次創建list，再檢查list。

所以它會產生大量的垃圾，因為每次make_clist完成之后，再次make_clist，上一個list就成為垃圾了。所以GC必然會有一些工作要做。

make_clist的代碼有點丑，主要是因為每個指針都需要被readptr檢查包圍。通常這里的檢查代碼是由編譯器生成的。但是我這里并沒有一個針對帶GC的編程語言的編譯器，所以我只能模仿一個編譯器可能生成的內容。

make_clist會構建一個LISTSZ大小的鏈表，分配新的元素，并將新元素加到鏈表的起始位置，之后更新鏈表尾指針指向鏈表新的起始位置，這樣就能構成一個循環鏈表。

這里更有趣的部分是，GC部分怎么實現。首先讓我們看看如果沒有虛擬內存會怎樣。我們只需要查看兩個API：new和readptr。

以上就是new的實現，先不考慮這里的mutex，因為這是為基于虛擬內存的實現提供的。先假設我們不需要掃描，也不需要collect。接下來會檢查是否有足夠的空間，如果有足夠的空間，我們就將指針地址增加一些，以分配內存空間給新的對象，最后返回。

如果沒有足夠的空間，我們需要調用flip，也就是運行GC。

flip首先會切換from和to指針，之后將這個應用程序的兩個根節點從from空間forward到to空間。接下來我們看一下forward函數。

這個函數會forward指針o指向的對象，首先檢查指針o是不是在from空間，如果是的話，并且之前沒有被拷貝過，那么就將它拷貝到to空間。如果之前拷貝過，那么就可以用to空間的指針代替對象指針，并將其返回。

對于readptr，如果我們沒有使用虛擬內存。會對指針p做forward操作，forward操作的意思是如果對象在from空間，那么就將其拷貝到to空間，所以這里會有耗時的檢查。

接下來我們看一下這里如何使用虛擬內存。

首先是設置內存，通過shm_open創建一個Share-memory object，shm_open是一個Linux/Uinx系統調用。Share-memory object表現的像是一個文件，但是它并不是一個文件，它位于內存，并沒有磁盤文件與之對應，如果你愿意的話，可以認為它是一個位于內存的文件系統。

之后我們裁剪這個Shared-memory object到from和to空間的大小。

之后我們通過mmap先將其映射一次，以供mutator也就是實際的應用程序使用。然后再映射一次，以供GC使用。這里shm_open，ftruncate，和兩次mmap，等效于map2。

回過去看之前的代碼，

使用了虛擬內存之后，readptr將不做任何事情，直接將參數返回。當然，如果我們使用這里的指針，并且指針對應的對象位于unscanned區域，我們會得到Page Fault。

在Page Fault hanlder中，GC會運行scan函數。但是scan函數是以GC對應的PTE來運行的，所以它能工作。而同時，應用程序或者mutator不能訪問這些Page，如果訪問了的話，這會產生Page Fault。一旦scan執行完成，handler中會將Page設置成對應用程序可訪問的（注，也就是調用mprotect）。

在flip函數中，

完成from和to空間的切換時，如果使用了虛擬內存，我們會通過mprotect將整個to空間對應用程序標記成不可訪問的。之后GC將root_head和root_last移到to空間中，這樣應用程序就不能訪問這兩個對象，任何時候應用程序需要訪問這兩個對象，都會導致一個Page Fault。在Page Fault handler中，GC可以將其他對象從from空間拷貝到to空間，然后再Unprot對應的Page。

在Page Fault handler中，先scan內存Page，再將內存Page標記成對應用程序可訪問的這個順序是至關重要的。因為如果你先將內存Page標記成應用程序可訪問的，然后再掃描它，如果有多個應用程序線程，那么應用程序可能會查看到unscanned區域的對象。當然我們要禁止這一點（注，因為為了避免搶占，unscanned區域只能GC訪問），所以這里的代碼是先掃描，再增加內存的訪問權限，這樣應用程序就可以安全的訪問這些內存Page。

接下來，我總結一下這節課的內容。有一個問題，你應該在這里使用虛擬內存嗎？或者說這里的這些技巧值得嗎？許多的GC并沒有使用虛擬內存，而是通過編譯器生成的代碼來完成GC，并且還有各種其他的技巧來減少性能損耗。所以GC的大部分場景都可以通過一些額外的指令來完成。這對于一個編譯器，程序運行時，或者編程語言來說，并不是一個太糟糕的選擇，因為編譯器就可以完成這些操作。但是如果沒有程序運行時或者編譯器，那么這個過程就會很痛苦。所以對于一些完全沒有編譯器參與的應用程序，例如checkpointing，shared-virtual memory，它們的確需要這里提到的虛擬內存特性。實際中，足夠多的應用程序開發人員發現了這些特性的價值，所以今天的操作系統都支持了這些虛擬內存特性。

很多人問了這個問題，從91年（論文發表的年份）至今，虛擬內存系統發生了什么改變？其中一個改變是，大部分的Unix系統都支持了這些虛擬內存特性了，并且從91年至今有許多變化。或許很難想象，但是在虛擬內存系統中有持續的開發，所以如果你查看Linux的git log，你可以發現在內核的各個方面都有持續的開發，其中包括了對虛擬內存系統的持續開發。在過去有一些重大的改變，比如說：

• 現在的Page Table是5級的，這樣可以處理非常大的地址
• 可以通過地址空間標識符來處理TLB flush
• 大概一年前，一種叫做KPTI（kernel page table isolation）的功能被引入，它是針對Meltdown attack的功能

虛擬內存系統絕對不是一個靜態的系統，幾乎Linux內核的所有方向都不是靜態的。幾乎每兩個月在內核的不同方向都會有大量的更新。所以每個子系統時不時的就會被重寫。

學生問答 -------------------------------------------------------------- start
學生提問：VMA中的連續地址是什么意思？

Frans教授：這里是指連續的虛擬內存地址，比如說一個VMA表示1000-2000這段地址。如果你有另一段地址，2100-2200，那么它會有屬于自己的VMA。所以每個VMA覆蓋了一段連續的地址，中間不會有中斷。你們將會在mmap lab中看到這樣的設計是更加的合理的。你們可以認為對于每個mmap系統調用，如果地址沒有重疊的話，都會有一個VMA。

學生提問：GC什么時候會停止，什么時候又會再開始？我認為GC可以一直運行，如果它是并發的。

Frans教授：是的，基于虛擬內存的解決方案一個酷的地方在于，GC可以一直運行。它可以在沒有unscanned對象時停止。

學生提問：但是你需要遍歷所有在from空間的對象，你怎么知道已經遍歷了所有的對象呢？

Frans教授：你會從根節點開始掃描整個對象的圖，然后拷貝到to空間。在某個時間點，你不再添加新的對象了，因為所有的對象已經被拷貝過了。當你不再添加新的對象，你的unscanned區域就不再增長，如果它不再增長，那么你就遍歷了所有的對象（注，可以想象一個普通的DFS或者BFS過程）。
學生問答 -------------------------------------------------------------- end

---