V8 JavaScript引擎研究（三）垃圾回收器的实现
V8垃圾回收機制簡介
V8垃圾回收器的實現(xiàn)，是V8高效的一個非常重要的原因。
V8在運行時自動回收不再需要使用的對象內存，也即是垃圾回收。
V8使用了全暫停式（stop-the-world）、分代式（generational）、精確（accurate）等組合的垃圾回收機制，來確保更快的對象內存分配、更短的垃圾回收時觸發(fā)的暫停以及沒有內存碎片。
V8的垃圾回收有如下幾個特點：
- 當處理一個垃圾回收周期時，暫停所有程序的執(zhí)行。
- 在大多數垃圾回收周期，每次僅處理部分堆中的對象，使暫停程序所帶來的影響降至最低。
- 準確知道在內存中所有的對象及指針，避免錯誤地把對象當成指針所帶來的內存泄露。
在V8中，對象堆被分為兩個部分：新創(chuàng)建的對象所在的新生代，以及在一個垃圾回收周期后存活的對象被提升到的老生代。如果一個對象在一個垃圾回收周期中被移動，那么V8將會更新所有指向此對象的指針。
V8垃圾回收機制深入剖析
如大多數動態(tài)類型語言一樣，JavaScript使用垃圾回收機制來管理內存，然而ECMAScript沒有任何操作垃圾回收的接口，所有的操作都有JavaScript引擎自動完成。這讓開發(fā)者省卻了手動管理內存分配所帶來的各種棘手問題。
V8在實現(xiàn)JavaScript的垃圾回收機制時，使用了各種非常復雜的策略，保證了高效的內存使用及回收，這也是Node之所以選擇V8作為JavaScript引擎的原因之一。如果V8僅會在瀏覽器中被使用，那么即使發(fā)生內存泄漏等各種內存問題也僅僅會影響到一個終端用戶，而且考慮到V8引擎在瀏覽器中的生命周期不長，一旦頁面被關閉后，內存即會被釋放。但如果在服務器端使用V8（使用Node作為服務器環(huán)境），那么內存問題所造成的影響將會波及到大量終端用戶，顯然V8需要高效的內存管理機制。
V8會限制所使用的內存大小，原因一是最初V8是作為瀏覽器JavaScript引擎所設計的，二是V8的垃圾回收機制的限制，如果內存分配過大，那么垃圾回收周期也就越長，對程序造成的影響也就越大。V8的內存大小限制是可配置的。
V8的堆組成
V8的堆由一系列區(qū)域組成：
- 新生代區(qū)：大多數對象的創(chuàng)建被分配在這里，這個區(qū)域很小，但垃圾回收非常頻繁，獨立于其它區(qū)。
- 老生代指針區(qū)：包含大部分可能含有指向其它對象指針的對象。大多數從新生代晉升（存活一段時間）的對象會被移動到這里。
- 老生代數據區(qū)：包含原始數據對象（沒有指針指向其它對象）。Strings、boxed numbers以及雙精度unboxed數組從新生代中晉升后被移到這里。
- 大對象區(qū)：這里存放大小超過其它區(qū)的大對象。每個對象都有自己mmap內存。大對象不會被回收。
- 代碼區(qū)：代碼對象（即包含被JIT處理后的指令對象）存放在此。唯一的有執(zhí)行權限的區(qū)域（代碼過大也可能存放在大對象區(qū)，此時它們也可被執(zhí)行，但不代表大對象區(qū)都有執(zhí)行權限）。
- Cell區(qū)、屬性Cell區(qū)以及map區(qū)：包含cell、屬性cell以及map。每個區(qū)都存放他們指向的相同大小以及相同結構的對象。
每個區(qū)都由一系列的內存頁（page）組成。內存頁是一塊聯(lián)系的內存，使用操作系統(tǒng)的mmap（或Windows的等價物）分配。每個區(qū)的頁的大小都是1MB，而且以1MB對齊，除了大對象區(qū)（那里可能更大）。除了存儲對象，內存頁還會包含一個頭部信息（包括一些標志和元數據）以及一個記號位圖（指明哪些對象是活著的）。每個頁還有一個分配在單獨內存中的槽緩沖區(qū)，放置一組對象，這些對象可能指向在當前頁的其他對象。
識別指針
任何垃圾回收器首要解決的任務就是區(qū)分開出指針和數據。垃圾回收器需要循著指針來找到活著的對象。多數垃圾回收算法都會在內存中移動對象的位置（為了減少內存碎片以及使內存更緊湊），所以需要可以改寫指針指向的位置并且不破壞舊的數據。
目前有三種主流的方法來識別指針：
- 保守法（Conservative）?？稍跊]有編譯器支持的情況下實現(xiàn)?；旧?#xff0c;將堆上所有對齊的字都認為是指針，這意味著一些數據也會被當成是指針。因此，當一個整數被當成指針時，可能導致原本應該被回收的內存被誤認為還有指針（實際只是個整數）指向它而沒有被回收，這會產生非常奇怪的內存泄漏現(xiàn)象。我們不能移動內存中的任何對象，因為當錯把整數當成指針時會改變數據本身，這將導致垃圾回收的內存整理算法不會產生任何好處。（內存連續(xù)的好處顯而易見：更容易分配大的內存，省卻了內存碎片導致的不斷查找，cache緩存命中的幾率高）。
- 編譯器提示法（Compiler hints）。如果使用靜態(tài)類型語言，則編譯器可以準確告知每個類中指針的偏移地址。只要能知道一個對象實現(xiàn)自哪個類，就可找出它的全部指針。Java虛擬機使用了此種方法，然而這種方案對于動態(tài)類型語言（如JavaScript）來說確不切實際，因為一個對象中的屬性既可以是指針也可以是數據。
- 指針標記法（Tagged pointers）。此種方法需要在每個字（word）的末位保留一位來指明其是指針還是數據。這種方法有編譯器支持的限制，但實現(xiàn)簡單。V8使用了這種方法，一些靜態(tài)類型語言也使用了這種方法，如OCamI。V8將所有數據以32bit字寬來存儲，其中最低一位為0，而指針的最低兩位為01。
V8將屬于-230至230-1范圍內的所有小整數（V8內部用Sims表示）使用了一個最低位為0的32位字（word）來表示，指針的最低兩位為01。由于所有對象都至少以4個字節(jié)（byte）對齊，因此這樣實現(xiàn)沒有問題。在堆上的絕大多數對象都包含一組標記后的字（word），所以垃圾回收器可以快速的掃描它們，找出指針，忽略整數。有些對象，如string，已知僅包含數據（沒有指針），它們的內容可以不被標記。
分代式回收
在大多數程序中，絕大多數對象的生命周期很短，只有少部分對象擁有較長的生命周期。
考慮到這一點，V8將堆分成了兩代:新生代（new-space）及老生代（old-space）。
對象在新生代中被創(chuàng)建，新生代很小，只有1~8MB。在新生代中分配內存非常容易，持有一個指向內存區(qū)的分配指針，當需要給新對象分配內存時，遞增指針即可。當分配指針到達了新生代的末尾，就會觸發(fā)一個小垃圾回收周期（Scavenge算法），快速地從新生代中回收死去的對象。對于在兩個小垃圾回收周期都存活下來的對象，則將其晉升（promote）至老生代。老生代在標記-清除（mark-sweep）或標記-整理（mark-compact）這樣的非常不頻繁的大垃圾回收周期中回收內存。當足夠數量的對象被晉升至老生代中后，將觸發(fā)一次大垃圾回收周期，至于具體時機，取決于老生代的內存大小及程序的行為。
新生代垃圾回收算法
由于新生代中的垃圾回收非常頻繁，因此回收算法必須足夠快。V8的新生代垃圾回收使用了Scavenge算法（Cheney算法的一種實現(xiàn)）。
新生代被劃分為兩個大小相等的子區(qū)：to區(qū)及from區(qū)。絕大多數對象的內存分配都發(fā)生在to區(qū)（一些特定類型的對象，如可執(zhí)行的代碼對象，被分配在老生代中）。當to區(qū)被填滿后，交換to區(qū)和from區(qū)，現(xiàn)在所有對象都存儲在from區(qū)，然后將活著的對象從from區(qū)拷貝到to區(qū)或者將它們晉升至老生代中，拷貝的過程實際是對to區(qū)內存的一次整理過程，整理后to區(qū)的內存占用將是連續(xù)的，以便于下次的內存分配依然保持快速和簡單?？截愡^后，釋放from區(qū)的內存。
可以看出，在新生代的垃圾回收周期中，始終有一半的內存時空的，由于新生代很小，因此浪費的空間并不大，而且新生代中的絕大部分對象生命周期都很短，因此需要復制的活著的對象很少，所以時間效率極高。
新生代垃圾回收特點：
- 內存區(qū)小
- 浪費一半空間
- 垃圾多
- 拷貝范圍小
- 執(zhí)行頻率高且快
算法具體執(zhí)行過程：
在to區(qū)中維護兩個指針：allocationPtr（指向為下一個對象分配內存的地址）及scanPtr（指向下一個需要掃描的對象地址）。
首先，to區(qū)填滿，交換to區(qū)與from區(qū)，此時to區(qū)為空，from區(qū)為滿。
將from區(qū)中所有可從根對象到達的對象拷貝至to區(qū)，可以把此時的to區(qū)想象成一個雙端隊列，scanPtr指向隊首，allocationPtr指向隊尾，然后執(zhí)行循環(huán)，每次遍歷一個to區(qū)的對象，即每次遍歷一個scanPtr所指向的對象，然后自增scanPtr。遍歷到一個對象時，依次分析此對象內部的所有指針，如果指針不指向from區(qū)里的對象，則忽略它（因為此時它必指向老生代中的對象，而老生代中的對象還未回收）；如果指針指向from區(qū)中的對象，并且此對象還未被復制到to區(qū)（還未設置轉換地址，具體見后文），則將其復制到to區(qū)的末端，也即allocationPtr所指向的位置，同時自增allocationPtr。然后將from區(qū)中的此對象的轉換地址設置為復制后to區(qū)中的位置。轉換地址保存在此對象的第一個字中（word），代替map地址。垃圾回收器可以通過檢查對象第一個字中的低位來區(qū)分出轉換地址和map地址，map地址的低位被標記，而轉換地址沒有。后續(xù)當分析到一個指針指向一個在from區(qū)中的對象，并且此對象已經被復制到to區(qū)（已有轉換地址），那么只需簡單將此指針指向的地址更新為對象的轉換地址即可。
當所有to區(qū)中的對象都被處理后，即scanPtr與allocationPtr相遇時，算法結束。此時from中的所有對象都是垃圾對象，可以被全部釋放。
抽象來看，整個算法遍歷過程實際是一個BFS（廣度優(yōu)先搜索）過程，scanPtr之前所有對象都是其內部指針已被分析完畢的對象，scanPtr與allocationPtr之間的對象是需要分析內部指針的對象，當scanPtr與allocationPtr重合，搜索結束。
算法偽代碼如下：
def scavenge():swap(fromSpace, toSpace)allocationPtr = toSpace.bottomscanPtr = toSpace.bottomfor i = 0..len(roots):root = roots[i]if inFromSpace(root): rootCopy = copyObject(&allocationPtr, root) setForwardingAddress(root, rootCopy) roots[i] = rootCopy while scanPtr < allocationPtr: obj = object at scanPtr scanPtr += size(obj) n = sizeInWords(obj) for i = 0..n: if isPointer(obj[i]) and not inOldSpace(obj[i]): fromNeighbor = obj[i] if hasForwardingAddress(fromNeighbor): toNeighbor = getForwardingAddress(fromNeighbor) else: toNeighbor = copyObject(&allocationPtr, fromNeighbor) setForwardingAddress(fromNeighbor, toNeighbor) obj[i] = toNeighbor def copyObject(*allocationPtr, object): copy = *allocationPtr *allocationPtr += size(object) memcpy(copy, object, size(object)) return copy
寫屏障
上面的算法有一個問題被忽略了：如果新生代中的某個對象，只有一個指針指向它，并且此指針屬于老生代中的某個對象，那么如何識別出新生代中的此對象不是垃圾對象。將老生代中的全部對象掃描一遍是不現(xiàn)實的，因為數量龐大消耗巨大。
為了解決這個問題，V8在存儲緩沖區(qū)中維護了一個列表，記錄了老生代對象指向新生代對象的情況。當一個新對象被創(chuàng)建時，沒有指針指向它，但當一個老生代中的對象指向它時，便在列表中記錄下來，由于每次寫操作都需要執(zhí)行這樣一個過程，這也稱作寫屏障。
每次在發(fā)生一個指針指向對象這樣的寫操作時都需要執(zhí)行這樣一系列的額外指令，這就是垃圾回收機制所帶來的代價，但是代價并不大，寫操作相比讀操作并不常發(fā)生。一些其它JavaScript引擎的垃圾回收算法使用了讀屏障，但這需要硬件輔助才能有較低的消耗。V8采用了一些機制來優(yōu)化寫屏障所帶來的消耗：
- 通?？梢则炞C出一個對象位于新生代，寫屏障不會發(fā)生在新生代對象的操作上。
- 一個對象的所有引用都發(fā)生在局部時，此對象會被分配在棧上，棧上的對象顯然不需要寫屏障。
- 老->新這樣的情況很少見，因此快速檢測出新->新及老->老這兩種常見情況可以提升很大性能，因為此兩種情況不需要寫屏障。每個頁都以1MB來對齊，因此通過過濾一個對象的低20位（bit），可以找到它所在的頁。頁頭含有指向其是否在新舊生代的標識，因此可以快速檢查出兩個對象所處的生代。
- 當存有關系列表的存儲緩沖區(qū)被填滿后，V8將對其排序，合并相同的項目，移除指針不再指向新生代的情況。
老生代垃圾回收算法
Scavenge算法對于少量內存具有非?？斓幕厥蘸驼砟芰?#xff0c;但有很大的內存開銷，因為要同時支持to區(qū)及from區(qū)。這對于少量內存區(qū)是可以接受的，但對于超過數MB的內存區(qū)來說，使用Scavenge算法是不切實際的。因此對于老生代數百MB的內存空間，V8使用了兩種緊密相連的算法，即標記-清除算法與標記-整理算法。
這兩種算法都包含了兩個階段：標記階段，清除階段或整理階段。
標記清除（Mark-Sweep）
遍歷堆中所有的對象，標記所有活著的對象。在清除階段，只清除沒有被標記的對象，即垃圾對象。由于垃圾對象占比很小，因此效率很高。
標記清除所帶來的問題是，當一次清除結束后，內存空間往往出現(xiàn)了很多碎片，導致內存不再連續(xù)。當需要分配一個占有大量內存的對象時，如果沒有一個內存碎片能滿足此對象所需空間的大小，那么V8將無法完成此次分配，導致出發(fā)垃圾回收。
標記整理（Mark-Compact）
為了解決標記清除后所帶來的內存碎片問題，V8引入了標記整理。標記整理的標記階段與標記清除一樣，但清除階段變?yōu)檎黼A段：將活著的對象向內存區(qū)的一段移動，移動完后直接清除邊界外的內存。整理階段涉及對象的移動，因此效率不高，但能保證不會產生內存碎片。
老生代垃圾回收特點：
- 內存區(qū)大
- 存放的對象生命周期很長
- 被清除的對象少，回收范圍小
- 執(zhí)行頻率低且較慢
算法具體執(zhí)行過程：
在標記階段，所有在堆上活著的對象都會被發(fā)現(xiàn)且被標記。每個頁都包含一個標記位圖，位圖的每一位都對應頁上的一個字（一個指針大小就是一個字，也即對象的起始地址的大小就是一個字），這樣做非常必要，因為對象可以起始于任何字對齊的偏移地址。位圖會占據一定的內存開銷（32位系統(tǒng)下占3.1%，64位系統(tǒng)下占1.6%），然而所有的內存管理系統(tǒng)都有類似的開銷。同時使用2個位（bit）來代表一個對象的狀態(tài)，對象至少占有兩個字大小，因此這2個位不會重疊。
V8使用了三色標記法，對象的狀態(tài)可被標記成三種（所以用2位來標記）：
- 如果為白色，那么此對象沒有被垃圾回收器發(fā)現(xiàn)；
- 如果為灰色，那么此對象已被垃圾回收器發(fā)現(xiàn)，但其鄰接對象還未被處理；
- 如果為黑色，那么此對象已經被發(fā)現(xiàn)，且所有它的鄰接對象都已被處理完畢；
如果將堆想象成一個對象間通過指針連接的有向圖，那么標記算法本質上是一個DFS（深度優(yōu)先搜索）。在標記周期起始時，標記位圖被清空，所有的對象都為白色。將可從根部直達的所有對象都標記為灰色，然后放入一個單獨分配的雙端隊列中。接著循環(huán)處理隊列中的每個對象：每次垃圾回收器都從隊列中取出一個對象并將其標記為黑色，接著將其鄰接對象（內部指針指向的對象）標記為灰色并放入雙端隊列中。當隊列為空時，所有被發(fā)現(xiàn)的對象都被標記成了黑色，此時算法結束。對于特別大的對象，如長數組，在處理時可能會被分片處理，以減少隊列溢出的幾率。如果隊列發(fā)生溢出，則對象仍會被標記為灰色但不放進隊列中（此時它們的鄰接對象還未被發(fā)現(xiàn)），當隊列為空時，垃圾回收器會掃描堆中剩余的灰色對象，然后將它們放入隊列中，繼續(xù)執(zhí)行標記過程。
偽代碼如下：
markingDeque = [] overflow = falsedef markHeap():for root in roots:mark(root)do:if overflow:overflow = false refillMarkingDeque() while !markingDeque.isEmpty(): obj = markingDeque.pop() setMarkBits(obj, BLACK) for neighbor in neighbors(obj): mark(neighbor) while overflow def mark(obj): if markBits(obj) == WHITE: setMarkBits(obj, GREY) if markingDeque.isFull(): overflow = true else: markingDeque.push(obj) def refillMarkingDeque(): for each obj on heap: if markBits(obj) == GREY: markingDeque.push(obj) if markingDeque.isFull(): overflow = true return
當標記算法結束后，所有活著的對象都會被標記成黑色，所有死去的對象仍然為白色。這些信息將會被清除階段或整理階段使用，這取決于接下來使用哪種算法，這兩種算法都以頁級單位來回收內存（V8的頁是1MB的連續(xù)內存，與虛擬內存頁不同）。
清除算法掃描連續(xù)范圍內的垃圾對象，然后釋放它們的空間，并將它們加入空閑內存鏈表中。每個頁都包含一些單獨的空閑內存鏈表，分別代表小內存區(qū)（<256字）、中內存區(qū)（<2048字）、大內存區(qū)（<16384字）以及超大內存區(qū)。清除算法相當簡單，只需遍歷頁的標記位圖，找到范圍內的白對象，然后釋放。空閑內存鏈表被大量用于從新生代Scavenge算法所晉升過來放置在老生代的對象，同時也被整理所發(fā)用來移動對象。有些對象只能分配在老生代，因此空閑內存鏈表也被用來分配。
整理算法會嘗試將對象從碎片頁（包含許多小空閑內存的頁）中移動并整合到一起。這些對象會被遷移到別的頁上，因此這時可能會需要分配新的頁，而遷出后的頁即可返還給操作系統(tǒng)。整理的過程非常復雜，大概步驟是，對碎片頁中的每個活著的對象拷貝到由空間內存鏈表分配的一塊內存頁，然后在碎片頁的該對象的第一個字（word）寫上新的轉換地址，在之后的遷移過程中，對象的舊地址會被記錄下來，在遷移結束后，V8會遍歷所有記錄有舊地址的指針，然后將這些指針更新為新的轉換地址。如果一個頁非?；钴S，有非常多的別的頁的指針指向這個頁中的對象，那么此頁將會保留 ，等到下一輪垃圾回收周期再進行處理。
V8的老生代內存回收結合了標記清除與標記整理兩種算法，大部分情況下使用標記清除，當空間不足以分配從新生代晉升過來的對象時，才使用標記整理。
標記-清除與標記-整理的優(yōu)化
增量標記（Incremental Marking）
由于在標記清除與標記整理的回收期間內，V8會暫停所有正在執(zhí)行業(yè)務的代碼，這會造成應用程序的卡頓，并且隨著堆大小的增長，卡頓的時間會急速增加，這顯然是不太可接受的。因此V8在標記期間，采用了增量標記的方法，將標記的過程拆分成很多部分，每次只標記一小部分，然后恢復業(yè)務代碼的執(zhí)行，再標記，這樣循環(huán)交替執(zhí)行標記。這樣，原來應用程序卡頓的整個時間就會變分拆成多個細小的時間片，極大的提高了應用程序的響應度。
增量標記與標準的標記方式的最大區(qū)別在于，在標記期間，對象的有向圖會發(fā)生改變（因為會間歇允許業(yè)務代碼的執(zhí)行）。因此需要解決的是發(fā)生黑對象指向白對象這種情況。黑對象已經被垃圾回收器完全處理過，因此不會再次對其處理，所以如果發(fā)生這種情況，那么白對象（此時已非垃圾對象）將依然會被當做垃圾對象回收。V8解決的方法依然是使用寫屏障技術，此時不僅老生代指向新生代時發(fā)生寫屏障，當黑對象指向白對象也會觸發(fā)寫屏障，此時黑對象會被重新標記成灰對象，然后放進雙端隊列中，當標記算法在稍后處理到隊列中的該對象時，該對象指向的所有對象都會被標記成灰色，此時之前的白對象也已變成了灰色，目標達成。
惰性清除（Lazy Sweeping）
當增量標記完成后，惰性清除開始此時所有對象都已被標記成或生或死，堆已經準確知道可以回收多少內存，然而此時不必去一次全部回收死去的對象，可以采用延遲清理的處理手段，垃圾回收器可以根據需要來選擇回收部分內存， 直到全部垃圾對象回收完畢，整個增量標記-惰性清除的 周期結束。
更多優(yōu)化
V8已經加入了并行清除，主線程不會操作已死對象，由獨立的線程來負責回收死對象的內存，整個過程只需要非常少量的同步操作。
同時V8正在實驗并行標記，并將在今后引入這一技術。
總結
垃圾回收是一項非常復雜的技術，要實現(xiàn)高效快速的垃圾回收器需要結合多種算法以及大量優(yōu)化，幸好引擎已經做了全部的工作，開發(fā)者只需關注更重要的業(yè)務邏輯即可。
轉載于:https://www.cnblogs.com/wolfx/p/5919574.html
總結
以上是生活随笔為你收集整理的V8 JavaScript引擎研究（三）垃圾回收器的实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 求一个姓袁好听的名字。
- 下一篇： 乌镇特产有哪些值得带