> For the complete documentation index, see [llms.txt](https://clu.gitbook.io/about-java-memory-model-jmm-a-k-a-jsr-133/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://clu.gitbook.io/about-java-memory-model-jmm-a-k-a-jsr-133/chapter-3-6-gc-hotspot-implementations.md).

# Chapter 3-6. GC - HotSpot Implementations

前面簡單的介紹了物件存活判定以及垃圾回收的演算法, 再來這邊會簡介一下Hotspot在實作這些演算法時的做法, 但我功力不足, 這邊寫得不是很好, 等之後讀通了會再回來修改, 所以看看就好.

## 窮舉根節點(GC Roots Enumeration)

在reachability analysis中, 以從GC Roots節點找到reference chain這個操作為例子, 可作為GC Roots的節點主要在global的reference(如**常數**或是**類別的static fields**)與執行context(譬如說stack frame中的**Local Variable table**)中, 如果要逐一檢查這裡面的參照, 是一定會消耗相當可觀的時間的.

另外, reachability對執行時間的敏感也體現在GC停頓上, 因為**這個分析作業必須在一個能確保一致性的snapshot中進行**, 這邊講的一致性就是指說在整個分析期間, **整個執行系統看起來就像是被'凍結"在某個時間點上一般, 不可以出現分析過程中物件參照關係還一直在不斷變化的情況, 否則分析結果的準確性就無法得到保證了**. 這點就是導致GC運作時**必須停頓所有Java執行緒**(這個動作又稱為**Stop The World**, a.k.a. **STW**)的其中一個重要原因, 即使是在號稱幾乎不會發生停頓的CMS collector中, 窮舉根節點的時候也是必須要停頓的.

其實, 目前的主流JVM用的都是準確式GC, 故當執行系統停頓下來後, 並不需要一個不漏地檢查完所有執行context和global的參照位置, JVM應該是要有辦法直接得知哪些地方存放著物件參照的. 這部分在HotSpot中, 是使用一組稱為**OopMap**的資料結構來達到這個目的的, 在class加載完畢後, HotSpot就把物件內什麼offset上是什麼類型的資料給計算出來, 在JIT編譯過程中, 也會在**特定的位置(即接下來會提到的安全點 --- Safepoint)**記錄下stack/registor中哪些位置是參照. 這樣, GC在掃描時就可以直接知道這些資訊了.

上面這樣講OopMap感覺有講跟沒講一樣, 所以這邊就再寫多一點, 但這只是我粗淺的讀了點東西後的想法, 可能也不是完全正確的.

所謂OopMap, 就是要拿來紀錄stack上Local Variable Table裡的變數到heap上的物件的參照關係. **它的作用是當GC發生時, collector thread會對stack上的記憶體進行掃描, 看看哪些地方儲存了reference type. 若某些位置儲存了reference type, 就表示這些位置所參照的物件不可以在這次的回收作業中被回收**. 但問題就在這: **stack上的Local Variable Table裡只有一部分資料是reference type(這就是我們要的), 但那些非reference type的資料, 對我們又沒什麼用處, 但我們還是不得不把整個stack掃一次, 這就很浪費(時間跟資源)**.

所以, 另一個想法就是, 能不能乾脆用空間來換時間呢? 就是說**在某個時間點把stack上代表reference的位置都記下來, 這樣到真正GC的時候, 就直接讀取這些被記下來的位置就好了, 然後就不用一直在那邊掃描了**. 這就是HotSpot裡的OopMap在做的事情.

到這邊為止, 我們可以知道這樣的關係: **一個執行緒代表一個stack -> 一個stack由多個stack frame組成 -> 一個stack frame對應著一個方法 -> 一個方法裡可能會有多個Safepoint**. GC發生時, 程式就會先找到最近的一個Safepoint停下來, 然後更新自己的OopMap, 記錄一下stack上有哪些位置代表reference type. 這樣一來, 在窮舉GC Roots的時候, 只要遞迴掃過每個stack frame的OopMap, 通過stack中紀錄的被參照物件的記憶體位置, 就可以找出這些GC Roots節點了.

## 安全點(Safepoint)

好了, 所以在OopMap的協助下, HotSpot就可以用比較有效率的方式準確地完成窮舉GC Roots的動作, 但接下來又出現了另一個問題 --- 可能導致參照關係發生變化, 或是換句話說, OopMap內容變化的指令非常多, 如果為每一條指令都升成對應的OopMap, 那就會需要大量的額外空間, 這樣GC的空間成本會變很高.

不過實際上HotSpot也沒有真的為每一條指令都升成OopMap, 前面有提到只會在"**特定的位置**"記錄這些資訊, 這些位置就叫做安全點(**Safepoint**), **即程式運作時並非在所有地方都能停頓下來開始GC, 只有在到達安全點的時候才可以暫停**. 選Safepoint是一門學問, 因為**選太少可能會讓GC等待時間太長; 選太多又會過份增加運行時的負擔**. 所以其選定的基本方式是以程式"**是否具有讓程式長時間執行的特徵**"為標準來進行選定的. 因為每條指令執行的時間都很短, 程式不太可能因為指令流的長度太長這個原因就過長時間運作, 長時間運作的最明顯特徵就是指令序列的重用, 譬如說method invocation, loop跳轉, exception跳轉等, 所以具有這些功能的指令才會產生Safepoint.

下一個要考慮的問題是, 如何在GC發生時讓所有執行緒(不包含執行JNI invocation的執行緒)都"跑"到最近的Safepoint上再停下來. 這裡基本上有兩種方案:

* **搶先式中斷(Preemptive Suspension)**: 不需要執行緒的執行程式主動去配合, 在GC發生時, 首先把所有執行緒全都中斷, 若發現有執行緒中斷的地方不是在Safepoint上, 就恢復該執行緒, 讓其跑到Safepoint上.
* **主動式中斷(Voluntary Suspension)**: 當GC需要中斷執行緒的時候, 不直接對執行緒操作, 僅僅是簡單地設置一個flag, 各個執行緒執行時主動去poll(輪詢)這個flag, 發現中斷flag為trye的時候就自己中斷並且hang up. 這些pool flag和Safepoint是重合的, 另外再加上建立物件需要分配記憶體的地方. 目前HotSpot採用的就是這種方式.

## 安全區域(Safe Region)

感覺上, 使用Safepoint好像已經完美解決了如何進入GC的問題, 但實際情況並沒有這麼美好. Safepoint機制保證了程式在"**執行"**時, 在不太長的時間內就會遇到可進入GC的Safepoint. 但是當程式"**不執行**"的時候呢? 所謂的不執行就是**沒有分配CPU時間**, 最典型的例子就是**執行緒處於sleep狀態或是blocked狀態的時候了**, 這時候執行緒無法回應JVM的中斷請求並且走到安全的地方去中斷且hang up, 而JVM顯然也不會去等這些執行緒被重新分配CPU時間. 這種時候就必須依靠安全區域(Safe Region)來解決.

安全區域指的是**在一段程式片段中, 參照關係不會發生變**化. 在這個區域中的任何地方開始GC都會是安全的. 所以我們也可以把安全區域看成是擴充後的安全點.

當執行緒執行到安全區域中的程式時, 會先標識自己已經進入了安全區域了, 這樣當在這段時間裡JVM要發動GC時, 就不用管這些說自己已經是安全了(Safe Region Status)的執行緒了. 執行緒要離開安全區域時, 要先檢查系統是否已經完成了窮舉根節點(或著是整個GC過程), 若完成了, 就可以繼續執行, 不然它就必須等待直到收到可以離開安全區域的信號為止.