young generation garbage collection 整理

• DefNew, ParNew, PSYoungGen, etc.. 這些cryptic名字來(lái)由? RednaxelaFX解惑

  • DefNew->default new generation
  • ParNew->parallel new generation
  • 原本HotSpot VM里沒(méi)有并行GC,當(dāng)時(shí)就只有NewGeneration,后來(lái)準(zhǔn)備要加入young gen的并行GC,就把原本的NewGeneration改名為DefNewGeneration,然后把新加的并行版叫做ParNewGeneration
  • 這些XXXGeneration都在HotSpot VM的“分代式GC框架”內(nèi)。
    本來(lái)HotSpot VM鼓勵(lì)開(kāi)發(fā)者盡量在這個(gè)框架內(nèi)開(kāi)發(fā)GC，但后來(lái)有個(gè)開(kāi)發(fā)就是不愿意被這框架憋著
    自己硬寫了個(gè)沒(méi)有使用已有框架的新并行GC，并拉攏性能測(cè)試團(tuán)隊(duì)用這個(gè)并行GC來(lái)跑分，成績(jī)也還不錯(cuò)，
    于是這個(gè)GC就放進(jìn)HotSpot VM里了。這就是我們現(xiàn)在看到的 ParallelScavenge
  • PSYoungGen->Parallel scavenge young generation
  • 結(jié)果就是HotSpot GC組不得不維護(hù)兩個(gè)功能幾乎一樣、但各種具體細(xì)節(jié)不同的并行GC。其實(shí)是件很頭疼的事情
  • Scavenge或者叫scavenging GC，其實(shí)就是copying GC的另一種叫法而已
    HotSpot VM里的GC都是在minor GC收集器里用scavenging的
    DefNew、ParNew和ParallelScavenge都是，只不過(guò)DefNew是串行的copying GC，而后兩者是并行的copying GC
    由此名字就可以知道，“ParallelScavenge”的初衷就是把“scavenge”給并行化。換句話說(shuō)就是把minor GC并行化
    至于full GC，那不是當(dāng)初關(guān)注的重點(diǎn)。
    把GC并行化的目的是想提高GC速度，也就是提高吞吐量（throughput）
    所以其實(shí)ParNew與ParallelScavenge都可叫做Throughput GC
    但是在HotSpot VM的術(shù)語(yǔ)里“Throughput GC”通常特指“ParallelScavenge”
  • ParallelScavenge和ParNew都是并行GC，主要是并行收集young gen，目的和性能其實(shí)都差不多。最明顯的區(qū)別有下面幾點(diǎn)
    • PS以前是廣度優(yōu)先順序來(lái)遍歷對(duì)象圖的，JDK6的時(shí)候改為默認(rèn)用深度優(yōu)先順序遍歷，并留有一個(gè)UseDepthFirstScavengeOrder參數(shù)來(lái)選擇是用深度還是廣度優(yōu)先
      在JDK6u18之后這個(gè)參數(shù)被去掉，PS變?yōu)橹挥蒙疃葍?yōu)先遍歷。ParNew則是一直都只用廣度優(yōu)先順序來(lái)遍歷
    • PS完整實(shí)現(xiàn)了adaptive size policy，而ParNew及“分代式GC框架”內(nèi)的其它GC都沒(méi)有實(shí)現(xiàn)完（倒不是不能實(shí)現(xiàn)，就是麻煩+沒(méi)人力資源去做）
      所以千萬(wàn)千萬(wàn)別在用ParNew+CMS的組合下用UseAdaptiveSizePolicy，請(qǐng)只在使用UseParallelGC或UseParallelOldGC的時(shí)候用它
    • 由于在“分代式GC框架”內(nèi)，ParNew可以跟CMS搭配使用，而ParallelScavenge不能。當(dāng)時(shí)ParNew GC被從Exact VM移植到HotSpot VM的最大原因就是為了跟CMS搭配使用
    • 在PS成為主要的throughput GC之后，它還實(shí)現(xiàn)了針對(duì)NUMA的優(yōu)化；而ParNew一直沒(méi)有得到NUMA優(yōu)化的實(shí)現(xiàn)
  • ParallelScavenge并行收集young gen，那old/perm gen呢？
    • 其實(shí)最初的ParallelScavenge的目標(biāo)只是并行收集young gen，而full GC的實(shí)際實(shí)現(xiàn)還是跟serial GC一樣
      只不過(guò)因?yàn)樗鼪](méi)有用HotSpot VM的generational GC framework，自己實(shí)現(xiàn)了一個(gè)CollectedHeap的子類ParallelScavengeHeap
      里面都弄了獨(dú)立的一套接口，而跟HotSpot當(dāng)時(shí)其它幾個(gè)GC不兼容。其實(shí)真的有用的代碼大部分就在PSScavenge（＝“ParallelScavenge的Scavenge”）里，也就是負(fù)責(zé)minor GC的收集器
      而負(fù)責(zé)full GC的收集器叫做PSMarkSweep（＝“ParallelScavenge的MarkSweep”）
      其實(shí)只是在serial GC的核心外面套了層皮而已，骨子里是一樣的LISP2算法的mark-compact收集器（別被名字騙了，它并不是一個(gè)mark-sweep收集器）
    • 當(dāng)啟用-XX:+UseParallelGC時(shí)，用的就是PSScavenge+PSMarkSweep的組合。 這是名副其實(shí)的“ParallelScavenge”——只并行化了“scavenge”
    • 不知道后來(lái)什么原因?qū)е耭ull GC的并行化并沒(méi)有在原本的generational GC framework上進(jìn)行，而只在ParallelScavenge系上進(jìn)行了。其成果就是使用了LISP2算法的并行版的full GC收集器，名為PSCompact（＝“ParallelScavenge-MarkCompact”），收集整個(gè)GC堆
    • 當(dāng)啟用-XX:+UseParallelOldGC時(shí)，用的就是PSScavenge+PSCompact的組合,此時(shí)ParallelScavenge其實(shí)已經(jīng)名不符實(shí)了——它不只并行化了“scavenge”（minor GC），也并行化了“mark-compact”（full GC）

• HotSpot VM的GC組老人之一Jon Masamitsu Our Collectors

  • 各種gc實(shí)現(xiàn)的組合關(guān)系 圖在這里
    • 忽略G1,shenandoah(not product-ready)
    • young
      • Serial -> CMS,Serial Old(MSC)
      • ParNew -> CMS,Serial Old(MSC)
      • Parallel Scavenge -> Serial Old(MSC),Parallel Old
    • old
      • CMS -> Serial,ParNew,Serial Old(MSC)
      • Serial Old(MSC)->CMS, Serial, ParNew, Parallel Scavenge
      • Parallel Old -> Parallel Scavenge
  • 簡(jiǎn)單介紹各個(gè)gc的特點(diǎn)
    • "Serial" is a stop-the-world, copying collector which uses a single GC thread.
    • "ParNew" is a stop-the-world, copying collector which uses multiple GC threads. It differs
      from "Parallel Scavenge" in that it has enhancements that make it usable with CMS.
      For example, "ParNew" does the synchronization needed so that it can run during the concurrent phases of CMS.
    • "Parallel Scavenge" is a stop-the-world, copying collector which uses multiple GC threads.
    • "Serial Old" is a stop-the-world,mark-sweep-compact collector that uses a single GC thread.
    • "CMS" is a mostly concurrent, low-pause collector.
    • "Parallel Old" is a compacting collector that uses multiple GC threads. Using the -XX flags for our collectors for jdk6,
    • USAGE
      • UseSerialGC is "Serial" + "Serial Old"
      • UseParNewGC is "ParNew" + "Serial Old"
      • UseConcMarkSweepGC is "ParNew" + "CMS" + "Serial Old". "CMS" is used most of the time to collect the tenured generation. "Serial Old" is used when a concurrent mode failure occurs.
      • UseParallelGC is "Parallel Scavenge" + "Serial Old"
      • UseParallelOldGC is "Parallel Scavenge" + "Parallel Old"
    • FAQ
      • How do I use "CMS" with "Serial"?
        • -XX:+UseConcMarkSweepGC -XX:-UseParNewGC.
          Don't use -XX:+UseConcMarkSweepGC and -XX:+UseSerialGC.
          Although that's seems like a logical combination, it will result in a message saying something about
          conflicting collector combinations and the JVM won't start. Sorry about that.
          Our bad
      • G1的暫時(shí)沒(méi)看
      • If G1 works out as we expect, it will become our low-pause collector in place of
        "ParNew" + "CMS". And if you're about to ask when will it be ready, please don't
        be offended by my dead silence. It's the highest priority project for our team,
        but it is software development so there are the usual unknowns. It will be out
        by JDK7. The sooner the better as far as we're concerned.

• 實(shí)現(xiàn)算法

  • Minor GC只收集young generation，而使用Serial GC時(shí)這個(gè)young generation的實(shí)現(xiàn)類叫做DefNewGeneration

  • FastScanClosure只在DefNewGeneration的收集中有用到。

    • HotSpot VM里有很多以*-Closure方式命名的類。它們其實(shí)是封裝起來(lái)的回調(diào)函數(shù)。為了讓GC的具體邏輯與對(duì)象內(nèi)部遍歷字段的邏輯能松耦合，這部分都是通過(guò)回調(diào)函數(shù)來(lái)連接到一起的。
    • ScanClosure與FastScanClosure都可用于DefNewGeneration的掃描

  • HotSpot VM Serial GC的minor GC使用的是Cheney算法的變種，所以先理解基本的Cheney算法有助理清頭緒

  • Cheney algorithms 這個(gè)算法的原始論文是C. J. Cheney在1970年發(fā)表的：A nonrecursive list compacting algorithm 維基百科解釋

    • is a stop and copy method of tracing garbage collection in computer software systems. In this scheme, the heap is divided into two equal halves, only one of which is in use at any one time. Garbage collection is performed by copying live objects from one semispace (the from-space) to the other (the to-space), which then becomes the new heap. The entire old heap is then discarded in one piece. It is an improvement on the previous stop and copy technique
    • Cheney's algorithm reclaims items as follows
      • Object references on the stack
        • Object references on the stack are checked. One of the two following actions is taken for each object reference that points to an object in from-space
        • If the object has not yet been moved to the to-space, this is done by creating an identical copy in the to-space, and then replacing the from-space version with a forwarding pointer to the to-space copy. Then update the object reference to refer to the new version in to-space
        • If the object has already been moved to the to-space, simply update the reference from the forwarding pointer in from-space
      • Objects in the to-space
        • The garbage collector examines all object references in the objects that have been migrated to the to-space,
        • and performs one of the above two actions on the referenced objects
    • Once all to-space references have been examined and updated, garbage collection is complete
    • The algorithm needs no stack and only two pointers outside of the from-space and to-space:
      a pointer to the beginning of free space in the to-space,
      and a pointer to the next word in to-space that needs to be examined.
    • For this reason, it's sometimes called a "two-finger" collector --- it only needs "two fingers" pointing into the to-space to keep track of its state.
    • The data between the two fingers represents work remaining for it to do.
    • The forwarding pointer (sometimes called a "broken heart") is used only during the garbage collection process;
      when a reference to an object already in to-space (thus having a forwarding pointer in from-space) is found,
      the reference can be updated quickly simply by updating its pointer to match the forwarding pointer.
    • Because the strategy is to exhaust all live references, and then all references in referenced objects, this is known as a breadth-first list copying garbage collection scheme
    • Equivalence to tri-color abstraction
      • Cheney's algorithm is an example of a tri-color marking garbage collector. The first member of the gray set is the stack itself. Objects referenced on the stack are copied into the to-space, which contains members of the black and gray sets.
      • The algorithm moves any white objects (equivalent to objects in the from-space without forwarding pointers) to the gray set by copying them to the to-space. Objects that are between the scanning pointer and the free-space pointer on the to-space area are members of the gray set still to be scanned. Objects below the scanning pointer belong to the black set. Objects are moved to the black set by simply moving the scanning pointer over them.
      • When the scanning pointer reaches the free-space pointer, the gray set is empty, and the algorithm ends.

  • 每個(gè)版本的算法描述都稍微不同，我的偽代碼也跟這兩本書(shū)寫的方式稍微不同，但背后要表達(dá)的核心思想是一樣的就OK了。

  • Tracing GC的核心操作之一就是從給定的根集合出發(fā)去遍歷對(duì)象圖。對(duì)象圖是一種有向圖，該圖的節(jié)點(diǎn)是對(duì)象，邊是引用。遍歷它有兩種典型順序：深度優(yōu)先（DFS）和廣度優(yōu)先（BFS）

  • 廣度優(yōu)先遍歷的典型實(shí)現(xiàn)思路是三色遍歷：給對(duì)象賦予白、灰、黑三種顏色以標(biāo)記其遍歷狀態(tài)：

    • 白色：未遍歷到的對(duì)象
    • 灰色：已遍歷到但還未處理完的對(duì)象（意味著該對(duì)象尚有未遍歷到的出邊）
    • 黑色：已遍歷完的對(duì)象

  • 遍歷過(guò)程：

    1. 一開(kāi)始，所有對(duì)象都是白色的；
    2. 把根集合能直接碰到的對(duì)象標(biāo)記為灰色。在只有一個(gè)根對(duì)象的地方就只要把那個(gè)對(duì)象標(biāo)記為灰色。但GC通常不是只有一個(gè)特定根對(duì)象，而是有一個(gè)集合的引用作為根，這些引用能直接碰到的對(duì)象都要標(biāo)記為灰色。
    3. 然后逐個(gè)掃描灰色對(duì)象的出邊，把這些邊能直接碰到的對(duì)象標(biāo)記為灰色。每當(dāng)一個(gè)對(duì)象的所有出邊都掃描完了，就把這個(gè)對(duì)象標(biāo)記為黑色。
    4. 重復(fù)第3步直到不再有灰色對(duì)象，遍歷結(jié)束。

  • 這黑白灰要怎么跟實(shí)際實(shí)現(xiàn)聯(lián)系起來(lái)呢？基本算法會(huì)使用一個(gè)隊(duì)列（queue）與一個(gè)集合set
    void breadth_first_search(Graph* graph) { // 記錄灰色對(duì)象的隊(duì)列 Queue<Node*> scanning; // 1. 一開(kāi)始對(duì)象都是白色的 // 2. 把根集合的引用能碰到的對(duì)象標(biāo)記為灰色 // 由于根集合的引用有可能有重復(fù)，所以這里也必須 // 在把對(duì)象加入隊(duì)列前先檢查它是否已經(jīng)被掃描到了 for (Node* node : graph->root_edges()) { // 如果出邊指向的對(duì)象還沒(méi)有被掃描過(guò) if (node != nullptr && !node->is_marked()) { node->set_marked(); // 記錄下它已經(jīng)被掃描到了 scanning.enqueue(child); // 也把該對(duì)象放進(jìn)灰色隊(duì)列里等待掃描 } } // 3. 逐個(gè)掃描灰色對(duì)象的出邊直到?jīng)]有灰色對(duì)象 while (!scanning.is_empty()) { Node* parent = scanning.dequeue(); for (Node* child : parent->child_nodes() { // 掃描灰色對(duì)象的出邊 // 如果出邊指向的對(duì)象還沒(méi)有被掃描過(guò) if (child != nullptr && !child->is_marked()) { child->set_marked(); // 把它記錄到黑色集合里 scanning.enqueue(child); // 也把該對(duì)象放進(jìn)灰色隊(duì)列里等待掃描 } } } }

  • Cheney算法正如上面說(shuō)的一樣，用一個(gè)隊(duì)列來(lái)實(shí)現(xiàn)對(duì)象圖的遍歷(每個(gè)節(jié)點(diǎn)可以標(biāo)記狀態(tài)) 比較完整的偽代碼可以參考我發(fā)這節(jié)開(kāi)頭給的鏈接，其中核心的部分抽取出來(lái)如下：
    `void garbage_collect(Heap* heap) {
    Semispace* to_space = heap->to_space();
    // 記錄灰色對(duì)象的隊(duì)列：從scanned到to_space->top()
    address scanned = to_space->bottom();
    // 1. 一開(kāi)始對(duì)象都是白色的
    // 2. 把根集合的引用能碰到的對(duì)象標(biāo)記為灰色
    // 由于根集合的引用有可能有重復(fù)，所以這里也必須
    // 在把對(duì)象加入隊(duì)列前先檢查它是否已經(jīng)被掃描到了
    for (Object** refLoc : heap->root_reference_locations()) {
    Object* obj = *refLoc;
    if (obj != nullptr) {
    if (!obj->is_forwarded()) {
    // 記錄下它已經(jīng)被掃描到了，也把該對(duì)象放進(jìn)灰色隊(duì)列里等待掃描
    size_t size = obj->size();
    address new_addr = to_space->allocate(size);

              // address Semispace::allocate(size_t size) {
              //   if (_top + size < _end) {
              //     address new_addr = _top;
              //     _top += size;
              //     return new_addr;
              //   } else {
              //     return nullptr;
              //   }
              // }
    
              // to_space->allocate()移動(dòng)了to_space->top()指針，
              // 等同于scanning.enqueue(obj);
              
              copy(/* to */ new_addr, /* from */ obj, size);
              Object* new_obj = (Object*) new_addr;
              obj->forward_to(new_obj);   // 設(shè)置轉(zhuǎn)發(fā)指針（forwarding pointer）
              *refLoc = new_obj;          // 修正指針指向新對(duì)象
          } else {
              *refLoc = obj->forwardee(); // 修正指針指向新對(duì)象
          }
          }
      }
      // 3. 逐個(gè)掃描灰色對(duì)象的出邊直到?jīng)]有灰色對(duì)象
      while (scanned < to_space->top()) {
          Object* parent = (Object*) scanned;
          // 掃描灰色對(duì)象的出邊
          for (Object** fieldLoc : parent->object_fields()) {
              Object* obj = *fieldLoc;
              // 如果出邊指向的對(duì)象還沒(méi)有被掃描過(guò)
              if (obj != nullptr) {
                  if (!obj->is_forwarded()) {     // 尚未被掃描過(guò)的對(duì)象
                  // 記錄下它已經(jīng)被掃描到了，也把該對(duì)象放進(jìn)灰色隊(duì)列里等待掃描
                  size_t size = obj->size();
                  address new_addr = to_space->allocate(size);
                  // to_space->allocate()移動(dòng)了to_space->top()指針，
                  // 等同于scanning.enqueue(obj);
                  copy(/* to */ new_addr, /* from */ obj, size);
                  Object* new_obj = (Object*) new_addr;
                  obj->forward_to(new_obj);     // 設(shè)置轉(zhuǎn)發(fā)指針（forwarding pointer）
                  *fieldLoc = new_obj;          // 修正指針指向新對(duì)象
                  } else {                        // 已經(jīng)掃描過(guò)的對(duì)象
                  *fieldLoc = obj->forwardee(); // 修正指針指向新對(duì)象
                  }
              }
          }
          scanned += parent->size();
          // 移動(dòng)scanned指針等同于scanning.dequeue(parent);
      }
    

    }`

  • 它的設(shè)計(jì)非常精妙

    1. 它使用一塊連續(xù)的地址空間來(lái)實(shí)現(xiàn)GC堆，并將其劃分為2個(gè)半分空間（semispace），分別稱為from-space與to-space。平時(shí)只用其中一個(gè)，也就是from-space；
    2. 逐個(gè)掃描指針，每掃描到一個(gè)對(duì)象的時(shí)候就把它從from-space拷貝到to-space，并在原來(lái)的對(duì)象里記錄下一個(gè)轉(zhuǎn)發(fā)指針（forwarding pointer），記住該對(duì)象被拷貝到哪里了。要知道一個(gè)對(duì)象有沒(méi)有被掃描（標(biāo)記）過(guò)，只要看該對(duì)象是否有轉(zhuǎn)發(fā)指針即可；
    3. 每掃描完一個(gè)指針就順便把該指針修正為指向拷貝后的新對(duì)象。這樣，對(duì)象的標(biāo)記（mark）、整理（compaction）、指針的修正就合起來(lái)在一步都做好了；
    4. 它不需要顯式為掃描隊(duì)列分配空間，而是復(fù)用了to-space的一部分用作隱式隊(duì)列。用一個(gè)scanned指針來(lái)區(qū)分to-space的對(duì)象的顏色：
       在to-space開(kāi)頭到scanned指針之間的對(duì)象是黑色的，
       在scanned指針到to-space已分配對(duì)象的區(qū)域的末尾之間的對(duì)象是灰色的。
       如何知道還有沒(méi)有灰色對(duì)象呢？
       只要scanned追上了to-space已分配對(duì)象區(qū)域的末尾就好了。
       這種做法也叫做“兩手指”（two-finger）：
       “scanned”與“free”。只需要這兩個(gè)指針就能維護(hù)隱式掃描隊(duì)列。
       “free”在我的偽代碼里就是to_space->top()。

  • Cheney算法GC工作時(shí)，to-space中各指針的樣子如下：
    |[ 已分配并且已掃描完的對(duì)象 ]|[ 已分配但未掃描完的對(duì)象 ]|[ 未分配空間 ]|
    ^ ^ ^ ^
    bottom scanned top end
    在GC結(jié)束時(shí)，不需要對(duì)原本的from-space做什么清理動(dòng)作，只要把它的分配指針（top）設(shè)回到初始位置（bottom）即可。
    之前在里面的對(duì)象就當(dāng)作不存在了。
    自然，也就不需要清理其中設(shè)置了的轉(zhuǎn)發(fā)指針。

  • Cheney算法是一個(gè)非常非常簡(jiǎn)單且高效的GC算法。看前面我寫的偽代碼就可以有直觀的感受它有多簡(jiǎn)單。它的實(shí)現(xiàn)代碼恐怕比簡(jiǎn)易mark-sweep還簡(jiǎn)單。
    但為啥很多簡(jiǎn)易的VM寧可采用mark-sweep而不用Cheney算法的copying GC呢？
    因?yàn)閙ark-sweep GC的常規(guī)實(shí)現(xiàn)不移動(dòng)對(duì)象，而copying GC必須移動(dòng)對(duì)象。
    移動(dòng)對(duì)象意味著使用GC的程序（術(shù)語(yǔ)叫做mutator）需要做更多事情，例如說(shuō)要能準(zhǔn)確定位到所有的指針，以便在對(duì)象移動(dòng)之后修正指針。
    很多簡(jiǎn)易VM都偷懶不想記住所有指針的位置，所以無(wú)法支持copying GC。

  • Cheney算法的簡(jiǎn)單優(yōu)雅之處來(lái)自它通過(guò)隱式隊(duì)列來(lái)實(shí)現(xiàn)廣度優(yōu)先遍歷，但它的缺點(diǎn)之一卻也在此：
    廣度優(yōu)先的拷貝順序使得GC后對(duì)象的空間局部性（memory locality）變差了。
    但是如果要改為真的深度優(yōu)先順序就會(huì)需要一個(gè)棧，無(wú)論是隱式（通常意味著遞歸調(diào)用）或者是顯式。
    使用遞歸實(shí)現(xiàn)的隱患是容易爆棧，有沒(méi)有啥辦法模擬深度優(yōu)先的拷貝順序但不用棧呢？這方面有很多研究。其中一種有趣的做法是IBM的hierarchical copying GC

  • 相比基本的Cheney算法，HotSpot VM Serial GC有什么異同呢？

    • 相同點(diǎn)：
      1. 使用廣度優(yōu)先遍歷；
      2. 使用隱式隊(duì)列；
      3. copy等同mark + relocate (compact) + remap (pointer fixup)三件事一步完成。
    • 在HotSpot VM里，copying GC用了scavenge這個(gè)名字，說(shuō)的是完全相同的事
    • 相異點(diǎn)：
      1. 基本Cheney算法不分代，而HotSpot的GC分兩代
      2. 基本Cheney算法使用2個(gè)半分空間（semispace），而HotSpot的GC在young generation使用3個(gè)空間——1個(gè)eden與兩個(gè)survivor space。注意這兩個(gè)survivor space就與semispace的作用類似。
    • 在G1 GC之前，所有HotSpot VM的GC堆布局都繼承自1984年David Ungar在Berkeley Smalltalk里所實(shí)現(xiàn)的Generation Scavenging

  • 那我們一點(diǎn)點(diǎn)把基本的Cheney算法映射過(guò)來(lái)

    • 基本Cheney算法用from-space和to-space，而HotSpot VM的DefNewGeneration有三個(gè)空間，eden space、from-space、to-space。后者的eden space + from-space大致等于前者的from-space，而后者的to-space + old gen的一部分大致等于前者的to-space
    • 拷貝對(duì)象的目標(biāo)空間不一定是to-space，也有可能是old generation，也就是對(duì)象有可能會(huì)從young generation晉升到old generation。
      為了實(shí)現(xiàn)這一功能，對(duì)象頭的mark word里有一小塊地方記錄對(duì)象的年齡（age），也就是該對(duì)象經(jīng)歷了多少次minor GC。如果掃描到一個(gè)對(duì)象，并且其年齡大于某個(gè)閾值（tenuring threshold），
      則該對(duì)象會(huì)被拷貝到old generation；如果年齡不大于那個(gè)閾值則拷貝到to-space。
      要留意的是，基本Cheney算法中2個(gè)半分空間通常一樣大，所以可以保證所有from-space里活著的對(duì)象都能在to-space里找到位置。但HotSpot VM的from-space與to-space通常比eden space小得多，不一定能容納下所有活的對(duì)象。
      如果一次minor GC的過(guò)程中，to-space已經(jīng)裝滿之后還遇到活對(duì)象要拷貝，則剩下的對(duì)象都得晉升到old generation去。這種現(xiàn)象叫做過(guò)早晉升（premature tenuring），要盡量避免
    • 既然拷貝去的目標(biāo)空間不一定是to-space，那原本Cheney算法里的隱式掃描隊(duì)列會(huì)在哪里？
      答案是既在to-space，也在old generation。很簡(jiǎn)單，在這兩個(gè)空間都記錄它們的scanned指針（叫做“saved mark”），這倆空間各自原本也記錄著它們的分配指針（“top”），之間的部分就用作掃描隊(duì)列
    • Forwarding pointer安裝在對(duì)象（oopDesc）頭部的mark word（markOop）里。只有在minor GC的時(shí)候才會(huì)把已拷貝的對(duì)象的mark word借用來(lái)放轉(zhuǎn)發(fā)指針
    • 通過(guò)回調(diào)，把遍歷邏輯與實(shí)際動(dòng)作分離。
      例如說(shuō)，遍歷根集合的邏輯封裝在GenCollectedHeap::gen_process_strong_roots()、SharedHeap::process_strong_roots()里，
      遍歷對(duì)象里的引用類型字段的邏輯封裝在oopDesc::oop_iterate()系的函數(shù)里；
      而實(shí)際拷貝對(duì)象的動(dòng)作則由FastScanClosure::do_work()負(fù)責(zé)調(diào)用
    • 基本Cheney算法的“scanned”指針，在HotSpot Serial GC里是每個(gè)space的“saved mark”。相關(guān)操作的函數(shù)名是：“save_marks()” / “set_saved_mark()”、“reset_saved_mark()”、“no_allocs_since_save_marks()” / “saved_mark_at_top()”
    • 看看遍歷循環(huán)的結(jié)束條件（循環(huán)條件的反條件）bool saved_mark_at_top() const { return saved_mark_word() == top(); } 跟基本Cheney算法的循環(huán)條件 scanned != top() 一樣
    • 為啥我的偽代碼里scanned是個(gè)局部變量，而HotSpot里變成了每個(gè)空間的成員字段？因?yàn)槭褂没卣{(diào)函數(shù)來(lái)分離遍歷邏輯與實(shí)際動(dòng)作，代碼結(jié)構(gòu)變了，這個(gè)scanned指針也只好另找地方放來(lái)讓需要訪問(wèn)它的地方都能訪問(wèn)到
    • HotSpot VM的分代式GC需要通過(guò)寫屏障（write barrier）來(lái)維護(hù)一個(gè)記憶集合（remember set）——記錄從old generation到y(tǒng)oung generation的跨代引用的數(shù)據(jù)結(jié)構(gòu)。具體在代碼中叫做CardTable。
      在minor GC時(shí)，old generation被remember set所記錄下的區(qū)域會(huì) 被看作根集合的一部分。而在minor GC過(guò)程中，每當(dāng)有對(duì)象晉升到old generation都有可能產(chǎn)生新的跨代引用。
      所以FastScanClosure::do_work()里也有調(diào)用寫屏障的邏輯：OopsInGenClosure::do_barrier()
    • HotSpot VM要支持Java的弱引用。在GC的時(shí)候有些特殊處理要做
    • HotSpot VM的GC必須處理一些特殊情況，一個(gè)極端的例子是to-space和old generation的剩余空間加起來(lái)都無(wú)法容納eden與from-space的活對(duì)象，導(dǎo)致GC無(wú)法完成。這使得許多地方代碼看起來(lái)很復(fù)雜。但要了解主要工作流程的話可以先不關(guān)心這些旁支邏輯

  • 一次YGC過(guò)程主要分成兩個(gè)步驟：
    1、查找GC Roots，拷貝所引用的對(duì)象到 to 區(qū)；
    2、遞歸遍歷步驟1中對(duì)象，并拷貝其所引用的對(duì)象到 to 區(qū)，當(dāng)然可能會(huì)存在自然晉升，或者因?yàn)?to 區(qū)空間不足引起的提前晉升的情況；

  • SharedHeap::process_strong_roots()掃描了所有一定是GC Roots的內(nèi)存區(qū)域
    Universe類中所引用的一些必須存活的對(duì)象 Universe::oops_do(roots)
    所有JNI Handles JNIHandles::oops_do(roots)
    所有線程的棧 Threads::oops_do(roots, code_roots)
    所有被Synchronize鎖持有的對(duì)象 ObjectSynchronizer::oops_do(roots)
    VM內(nèi)實(shí)現(xiàn)的MBean所持有的對(duì)象 Management::oops_do(roots)
    JVMTI所持有的對(duì)象 JvmtiExport::oops_do(roots)
    （可選）所有已加載的類 或 所有已加載的系統(tǒng)類 SystemDictionary::oops_do(roots)
    （可選）所有駐留字符串（StringTable） StringTable::oops_do(roots)
    （可選）代碼緩存（CodeCache） CodeCache::scavenge_root_nmethods_do(code_roots)
    （可選）PermGen的remember set所記錄的存在跨代引用的區(qū)域 rem_set()->younger_refs_iterate(perm_gen(), perm_blk)

  • 如果一個(gè)old generation的對(duì)象引用了young generation，那么這個(gè)old generation的對(duì)象肯定也屬于Strong root的一部分，
    這部分邏輯并沒(méi)有在process_strong_roots中實(shí)現(xiàn)，而是在綠色框中實(shí)現(xiàn)了，其中rem_set中保存了old generation中dirty card的對(duì)應(yīng)區(qū)域，
    每次對(duì)象的拷貝移動(dòng)都會(huì)檢查一下是否產(chǎn)生了新的跨代引用，比如有對(duì)象晉升到了old generation，而該對(duì)象還引用了young generation的對(duì)象，
    這種情況下會(huì)把相應(yīng)的card置為dirty，下次YGC的時(shí)候只會(huì)掃描dirty card所指內(nèi)存的對(duì)象，避免掃描所有的old generation對(duì)象

  • 遍歷活躍對(duì)象

    • 在查找GC Roots的步驟中，已經(jīng)找出了第一批存活的對(duì)象，這些存活對(duì)象可能在 to-space，也有可能直接晉升到了 old generation，這些區(qū)域都是需要進(jìn)行遍歷的，保證所有的活躍對(duì)象都能存活下來(lái)
    • 每個(gè)內(nèi)存區(qū)域都有兩個(gè)指針變量，分別是 _saved_mark_word 和 _top，其中_saved_mark_word 指向當(dāng)前遍歷對(duì)象的位置，_top指向當(dāng)前內(nèi)存區(qū)域可分配的位置，其中_saved_mark_word 到 _top之間的對(duì)象是已拷貝，但未掃描的對(duì)象
    • GC Roots引用的對(duì)象拷貝完成后，to-space的_saved_mark_word和_top的狀態(tài)如上圖所示，假設(shè)期間沒(méi)有對(duì)象晉升到old generation。
      每次掃描一個(gè)對(duì)象，_saved_mark_word會(huì)往前移動(dòng)，期間也有新的對(duì)象會(huì)被拷貝到to-space，_top也會(huì)往前移動(dòng)，直到 _saved_mark_word追上_top，說(shuō)明to-space的對(duì)象都已經(jīng)遍歷完成
    • 其中while循環(huán)條件 while (!_gch->no_allocs_since_save_marks(_level)，就是在判斷各個(gè)內(nèi)存代中的_saved_mark_word是否已經(jīng)追到_top，如果還沒(méi)有追上，就執(zhí)行_gch->oop_since_save_marks_iterate進(jìn)行遍歷
    • 從代碼實(shí)現(xiàn)可以看出對(duì)新生代、老年代和永久代都會(huì)進(jìn)行遍歷，其中新生代的遍歷實(shí)現(xiàn)
    • 這里會(huì)對(duì)eden、from和to分別進(jìn)行遍歷，第一次看這塊邏輯的時(shí)候很納悶，為什么要對(duì)eden和from-space進(jìn)行遍歷，from倒沒(méi)什么問(wèn)題，_saved_mark_word和_top一般都是相同的，
      但是eden區(qū)的_saved_mark_word明顯不會(huì)等于_top，一直沒(méi)有找到在eden區(qū)分配對(duì)象時(shí)，改變_top的同時(shí)也改變_saved_mark_word的邏輯，
      后來(lái)發(fā)現(xiàn)GenCollectedHeap::do_collection方法中，在調(diào)用各個(gè)代的collect之前，會(huì)調(diào)用save_marks()方法，將_saved_mark_word設(shè)置為_(kāi)top，這樣在發(fā)生YGC時(shí)，eden區(qū)的對(duì)象其實(shí)是不會(huì)被遍歷的，被這個(gè)疑惑困擾了好久，結(jié)果是個(gè)遺留代碼
    • to-space對(duì)象的遍歷實(shí)現(xiàn)
    • 在FastScanClosure回調(diào)函數(shù)的do_oop_work方法實(shí)現(xiàn)中，紅框的是重要的部分，因?yàn)榭赡艽嬖诙鄠€(gè)對(duì)象共同引用一個(gè)對(duì)象，所以在遍歷過(guò)程中，可能會(huì)遇到已經(jīng)處理過(guò)的對(duì)象，如果遇到這樣的對(duì)象，就不會(huì)再次進(jìn)行復(fù)制了，
      如果該對(duì)象沒(méi)有被拷貝過(guò)，則調(diào)用 copy_to_survivor_space 方法拷貝對(duì)象到to-space或者晉升到old generation，
      這里提一下ParNew的實(shí)現(xiàn)，因?yàn)槭遣l(fā)執(zhí)行的，所以可能存在多個(gè)線程拷貝了同一個(gè)對(duì)象到to-space，不過(guò)通過(guò)原子操作，保證了只有一個(gè)對(duì)象是有效的
    • 拷貝對(duì)象的目標(biāo)空間不一定是to-space，也有可能是old generation，如果一個(gè)對(duì)象經(jīng)歷了很多次YGC，會(huì)從young generation直接晉升到old generation，
      為了記錄對(duì)象經(jīng)歷的YGC次數(shù)，在對(duì)象頭的mark word 數(shù)據(jù)結(jié)構(gòu)中有一個(gè)位置記錄著對(duì)象的YGC次數(shù)，也叫對(duì)象的年齡，如果掃描到的對(duì)象，其年齡小于某個(gè)閾值（tenuring threshold），
      該對(duì)象會(huì)被拷貝到to-space，并增加該對(duì)象的年齡，同時(shí)to-space的_top指針也會(huì)往后移動(dòng)，這個(gè)新對(duì)象等待著被掃描
    • 如果該對(duì)象的年齡大于某個(gè)閾值，會(huì)晉升到old generation，或者在拷貝到to-space時(shí)空間不足，也會(huì)提前晉升到old generation，晉升過(guò)程通過(guò)老年代_next_gen的promote方法實(shí)現(xiàn)，
      如果old generation也沒(méi)有足夠的空間容納該對(duì)象，則會(huì)觸發(fā)晉升失敗

• card table

  • 在進(jìn)行YGC時(shí)，如果young generation的Y對(duì)象被old generation中O對(duì)象引用，那么稱O對(duì)象存在跨代引用，而且Y對(duì)象應(yīng)該在本次垃圾回收中存活下來(lái)，所以old generation的對(duì)象在YGC時(shí)也是Strong root的一部分，如果每次YGC都去掃描old generation中所有對(duì)象的話，肯定會(huì)非常耗時(shí)，那么有什么好的解決方案呢
  • 如果只掃描那些有young generation對(duì)象引用的對(duì)象，是不是效率可以達(dá)到最高，不過(guò)使用這種方式，需要有一個(gè)地方保存這些對(duì)象的引用，是一個(gè)不小的內(nèi)存開(kāi)銷，所以Hotspot實(shí)現(xiàn)中，并沒(méi)采用這樣方式，而是使用一個(gè)GenRemSet數(shù)據(jù)結(jié)構(gòu)，記錄包含這些對(duì)象的內(nèi)存區(qū)域是clean or dirty狀態(tài)
  • 盜圖一張-remset
  • CardTable是GenRemSet的一種實(shí)現(xiàn)，類似于一個(gè)數(shù)組，每個(gè)元素對(duì)應(yīng)著堆內(nèi)存的一塊區(qū)域是否存在跨代引用的對(duì)象，如果存在，該Card為dirty狀態(tài)
  • GenRemSet隨著堆內(nèi)存一起初始化，通過(guò)具體的垃圾收集策略進(jìn)行創(chuàng)建，比如CMS和G1是不一樣的，其中CMS對(duì)應(yīng)的是CardTable
  • 接上文中YGC遍歷old generation的邏輯
    rem_set()->younger_refs_iterate(_gens[i], older_gens);
    這里rem_set()方法返回的就是已經(jīng)初始化的CardTableRS對(duì)象，調(diào)用younger_refs_iterate，傳入的參數(shù)分別是old generation的引用和負(fù)責(zé)遍歷old generation對(duì)象的回調(diào)函數(shù)FastScanClosure，一步一步調(diào)用下去，最終調(diào)用到ClearNoncleanCardWrapper::do_MemRegion方法
  • 其中參數(shù)MemRegion相當(dāng)于堆內(nèi)存的一塊區(qū)域，這里指向old generation從_bottom 到 _top的區(qū)間
  • 具體看http://www.itdecent.cn/p/5037459097ee
  • 每次的動(dòng)作是先清除Card的dirty狀態(tài)，對(duì)象拷貝完成再判斷是否要設(shè)置為dirty，即非clean

• unread
  • https://blogs.oracle.com/jonthecollector/
  • https://blogs.oracle.com/jonthecollector/java-7
  • https://blogs.oracle.com/jonthecollector/guest-contributor

• References
  • RednaxelaFX-HotSpot VM Serial GC的一個(gè)問(wèn)題
  • RednaxelaFX-cryptic gc name in gc log
  • Jon Masamitsu-Our Collectors
  • 占小狼-JVM源碼分析之YGC的來(lái)龍去脈
  • 占小狼-JVM源碼分析之跨代引用CardTable