young generation garbage collection 整理

• DefNew, ParNew, PSYoungGen, etc.. 這些cryptic名字來由? RednaxelaFX解惑

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

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

  • 各種gc實現(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
  • 簡單介紹各個gc的特點
    • "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的暫時沒看
      • 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.

• 實現(xiàn)算法

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

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

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

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

  • Cheney algorithms 這個算法的原始論文是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.

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

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

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

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

  • 遍歷過程：

    1. 一開始公黑，所有對象都是白色的邑商；
    2. 把根集合能直接碰到的對象標(biāo)記為灰色。在只有一個根對象的地方就只要把那個對象標(biāo)記為灰色凡蚜。但GC通常不是只有一個特定根對象人断，而是有一個集合的引用作為根，這些引用能直接碰到的對象都要標(biāo)記為灰色朝蜘。
    3. 然后逐個掃描灰色對象的出邊恶迈，把這些邊能直接碰到的對象標(biāo)記為灰色。每當(dāng)一個對象的所有出邊都掃描完了谱醇，就把這個對象標(biāo)記為黑色暇仲。
    4. 重復(fù)第3步直到不再有灰色對象步做，遍歷結(jié)束。

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

  • Cheney算法正如上面說的一樣，用一個隊列來實現(xiàn)對象圖的遍歷(每個節(jié)點可以標(biāo)記狀態(tài)) 比較完整的偽代碼可以參考我發(fā)這節(jié)開頭給的鏈接斥滤，其中核心的部分抽取出來如下：
    `void garbage_collect(Heap* heap) {
    Semispace* to_space = heap->to_space();
    // 記錄灰色對象的隊列：從scanned到to_space->top()
    address scanned = to_space->bottom();
    // 1. 一開始對象都是白色的
    // 2. 把根集合的引用能碰到的對象標(biāo)記為灰色
    // 由于根集合的引用有可能有重復(fù)将鸵，所以這里也必須
    // 在把對象加入隊列前先檢查它是否已經(jīng)被掃描到了
    for (Object** refLoc : heap->root_reference_locations()) {
    Object* obj = *refLoc;
    if (obj != nullptr) {
    if (!obj->is_forwarded()) {
    // 記錄下它已經(jīng)被掃描到了，也把該對象放進(jìn)灰色隊列里等待掃描
    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()移動了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;          // 修正指針指向新對象
          } else {
              *refLoc = obj->forwardee(); // 修正指針指向新對象
          }
          }
      }
      // 3. 逐個掃描灰色對象的出邊直到?jīng)]有灰色對象
      while (scanned < to_space->top()) {
          Object* parent = (Object*) scanned;
          // 掃描灰色對象的出邊
          for (Object** fieldLoc : parent->object_fields()) {
              Object* obj = *fieldLoc;
              // 如果出邊指向的對象還沒有被掃描過
              if (obj != nullptr) {
                  if (!obj->is_forwarded()) {     // 尚未被掃描過的對象
                  // 記錄下它已經(jīng)被掃描到了咨堤，也把該對象放進(jìn)灰色隊列里等待掃描
                  size_t size = obj->size();
                  address new_addr = to_space->allocate(size);
                  // to_space->allocate()移動了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;          // 修正指針指向新對象
                  } else {                        // 已經(jīng)掃描過的對象
                  *fieldLoc = obj->forwardee(); // 修正指針指向新對象
                  }
              }
          }
          scanned += parent->size();
          // 移動scanned指針等同于scanning.dequeue(parent);
      }
    

    }`

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

    1. 它使用一塊連續(xù)的地址空間來實現(xiàn)GC堆漩符，并將其劃分為2個半分空間（semispace），分別稱為from-space與to-space驱还。平時只用其中一個嗜暴，也就是from-space；
    2. 逐個掃描指針议蟆，每掃描到一個對象的時候就把它從from-space拷貝到to-space闷沥，并在原來的對象里記錄下一個轉(zhuǎn)發(fā)指針（forwarding pointer），記住該對象被拷貝到哪里了咐容。要知道一個對象有沒有被掃描（標(biāo)記）過舆逃，只要看該對象是否有轉(zhuǎn)發(fā)指針即可；
    3. 每掃描完一個指針就順便把該指針修正為指向拷貝后的新對象戳粒。這樣路狮，對象的標(biāo)記（mark）、整理（compaction）蔚约、指針的修正就合起來在一步都做好了奄妨；
    4. 它不需要顯式為掃描隊列分配空間，而是復(fù)用了to-space的一部分用作隱式隊列苹祟。用一個scanned指針來區(qū)分to-space的對象的顏色：
       在to-space開頭到scanned指針之間的對象是黑色的砸抛，
       在scanned指針到to-space已分配對象的區(qū)域的末尾之間的對象是灰色的。
       如何知道還有沒有灰色對象呢树枫？
       只要scanned追上了to-space已分配對象區(qū)域的末尾就好了直焙。
       這種做法也叫做“兩手指”（two-finger）：
       “scanned”與“free”。只需要這兩個指針就能維護(hù)隱式掃描隊列砂轻。
       “free”在我的偽代碼里就是to_space->top()奔誓。

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

  • Cheney算法是一個非常非常簡單且高效的GC算法』仙埽看前面我寫的偽代碼就可以有直觀的感受它有多簡單颁褂。它的實現(xiàn)代碼恐怕比簡易mark-sweep還簡單。
    但為啥很多簡易的VM寧可采用mark-sweep而不用Cheney算法的copying GC呢傀广？
    因為mark-sweep GC的常規(guī)實現(xiàn)不移動對象颁独，而copying GC必須移動對象。
    移動對象意味著使用GC的程序（術(shù)語叫做mutator）需要做更多事情伪冰，例如說要能準(zhǔn)確定位到所有的指針誓酒，以便在對象移動之后修正指針。
    很多簡易VM都偷懶不想記住所有指針的位置贮聂，所以無法支持copying GC靠柑。

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

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

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

  • 那我們一點點把基本的Cheney算法映射過來

    • 基本Cheney算法用from-space和to-space敦腔，而HotSpot VM的DefNewGeneration有三個空間均澳，eden space、from-space、to-space找前。后者的eden space + from-space大致等于前者的from-space糟袁，而后者的to-space + old gen的一部分大致等于前者的to-space
    • 拷貝對象的目標(biāo)空間不一定是to-space，也有可能是old generation躺盛，也就是對象有可能會從young generation晉升到old generation项戴。
      為了實現(xiàn)這一功能，對象頭的mark word里有一小塊地方記錄對象的年齡（age）槽惫，也就是該對象經(jīng)歷了多少次minor GC周叮。如果掃描到一個對象，并且其年齡大于某個閾值（tenuring threshold）界斜，
      則該對象會被拷貝到old generation仿耽；如果年齡不大于那個閾值則拷貝到to-space。
      要留意的是各薇，基本Cheney算法中2個半分空間通常一樣大项贺，所以可以保證所有from-space里活著的對象都能在to-space里找到位置。但HotSpot VM的from-space與to-space通常比eden space小得多得糜，不一定能容納下所有活的對象敬扛。
      如果一次minor GC的過程中，to-space已經(jīng)裝滿之后還遇到活對象要拷貝朝抖，則剩下的對象都得晉升到old generation去。這種現(xiàn)象叫做過早晉升（premature tenuring）谍珊，要盡量避免
    • 既然拷貝去的目標(biāo)空間不一定是to-space治宣，那原本Cheney算法里的隱式掃描隊列會在哪里？
      答案是既在to-space砌滞，也在old generation侮邀。很簡單，在這兩個空間都記錄它們的scanned指針（叫做“saved mark”）贝润，這倆空間各自原本也記錄著它們的分配指針（“top”）绊茧，之間的部分就用作掃描隊列
    • Forwarding pointer安裝在對象（oopDesc）頭部的mark word（markOop）里。只有在minor GC的時候才會把已拷貝的對象的mark word借用來放轉(zhuǎn)發(fā)指針
    • 通過回調(diào)打掘，把遍歷邏輯與實際動作分離华畏。
      例如說，遍歷根集合的邏輯封裝在GenCollectedHeap::gen_process_strong_roots()尊蚁、SharedHeap::process_strong_roots()里亡笑，
      遍歷對象里的引用類型字段的邏輯封裝在oopDesc::oop_iterate()系的函數(shù)里；
      而實際拷貝對象的動作則由FastScanClosure::do_work()負(fù)責(zé)調(diào)用
    • 基本Cheney算法的“scanned”指針横朋，在HotSpot Serial GC里是每個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是個局部變量晰甚，而HotSpot里變成了每個空間的成員字段衙传？因為使用回調(diào)函數(shù)來分離遍歷邏輯與實際動作，代碼結(jié)構(gòu)變了厕九，這個scanned指針也只好另找地方放來讓需要訪問它的地方都能訪問到
    • HotSpot VM的分代式GC需要通過寫屏障（write barrier）來維護(hù)一個記憶集合（remember set）——記錄從old generation到y(tǒng)oung generation的跨代引用的數(shù)據(jù)結(jié)構(gòu)粪牲。具體在代碼中叫做CardTable。
      在minor GC時止剖，old generation被remember set所記錄下的區(qū)域會 被看作根集合的一部分腺阳。而在minor GC過程中，每當(dāng)有對象晉升到old generation都有可能產(chǎn)生新的跨代引用穿香。
      所以FastScanClosure::do_work()里也有調(diào)用寫屏障的邏輯：OopsInGenClosure::do_barrier()
    • HotSpot VM要支持Java的弱引用亭引。在GC的時候有些特殊處理要做
    • HotSpot VM的GC必須處理一些特殊情況，一個極端的例子是to-space和old generation的剩余空間加起來都無法容納eden與from-space的活對象皮获，導(dǎo)致GC無法完成焙蚓。這使得許多地方代碼看起來很復(fù)雜。但要了解主要工作流程的話可以先不關(guān)心這些旁支邏輯

  • 一次YGC過程主要分成兩個步驟：
    1洒宝、查找GC Roots购公，拷貝所引用的對象到 to 區(qū)；
    2雁歌、遞歸遍歷步驟1中對象宏浩，并拷貝其所引用的對象到 to 區(qū)，當(dāng)然可能會存在自然晉升靠瞎，或者因為 to 區(qū)空間不足引起的提前晉升的情況比庄；

  • SharedHeap::process_strong_roots()掃描了所有一定是GC Roots的內(nèi)存區(qū)域
    Universe類中所引用的一些必須存活的對象 Universe::oops_do(roots)
    所有JNI Handles JNIHandles::oops_do(roots)
    所有線程的棧 Threads::oops_do(roots, code_roots)
    所有被Synchronize鎖持有的對象 ObjectSynchronizer::oops_do(roots)
    VM內(nèi)實現(xiàn)的MBean所持有的對象 Management::oops_do(roots)
    JVMTI所持有的對象 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)

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

  • 遍歷活躍對象

    • 在查找GC Roots的步驟中岔霸，已經(jīng)找出了第一批存活的對象薛躬，這些存活對象可能在 to-space，也有可能直接晉升到了 old generation呆细，這些區(qū)域都是需要進(jìn)行遍歷的型宝，保證所有的活躍對象都能存活下來
    • 每個內(nèi)存區(qū)域都有兩個指針變量八匠，分別是 _saved_mark_word 和 _top，其中_saved_mark_word 指向當(dāng)前遍歷對象的位置趴酣，_top指向當(dāng)前內(nèi)存區(qū)域可分配的位置梨树，其中_saved_mark_word 到 _top之間的對象是已拷貝，但未掃描的對象
    • GC Roots引用的對象拷貝完成后岖寞，to-space的_saved_mark_word和_top的狀態(tài)如上圖所示抡四，假設(shè)期間沒有對象晉升到old generation。
      每次掃描一個對象仗谆，_saved_mark_word會往前移動指巡，期間也有新的對象會被拷貝到to-space，_top也會往前移動隶垮，直到 _saved_mark_word追上_top藻雪，說明to-space的對象都已經(jīng)遍歷完成
    • 其中while循環(huán)條件 while (!_gch->no_allocs_since_save_marks(_level)，就是在判斷各個內(nèi)存代中的_saved_mark_word是否已經(jīng)追到_top狸吞，如果還沒有追上勉耀，就執(zhí)行_gch->oop_since_save_marks_iterate進(jìn)行遍歷
    • 從代碼實現(xiàn)可以看出對新生代、老年代和永久代都會進(jìn)行遍歷蹋偏，其中新生代的遍歷實現(xiàn)
    • 這里會對eden便斥、from和to分別進(jìn)行遍歷，第一次看這塊邏輯的時候很納悶威始，為什么要對eden和from-space進(jìn)行遍歷枢纠，from倒沒什么問題，_saved_mark_word和_top一般都是相同的字逗，
      但是eden區(qū)的_saved_mark_word明顯不會等于_top京郑，一直沒有找到在eden區(qū)分配對象時，改變_top的同時也改變_saved_mark_word的邏輯葫掉，
      后來發(fā)現(xiàn)GenCollectedHeap::do_collection方法中，在調(diào)用各個代的collect之前跟狱，會調(diào)用save_marks()方法俭厚，將_saved_mark_word設(shè)置為_top，這樣在發(fā)生YGC時驶臊，eden區(qū)的對象其實是不會被遍歷的挪挤，被這個疑惑困擾了好久，結(jié)果是個遺留代碼
    • to-space對象的遍歷實現(xiàn)
    • 在FastScanClosure回調(diào)函數(shù)的do_oop_work方法實現(xiàn)中关翎，紅框的是重要的部分扛门，因為可能存在多個對象共同引用一個對象，所以在遍歷過程中纵寝，可能會遇到已經(jīng)處理過的對象论寨，如果遇到這樣的對象，就不會再次進(jìn)行復(fù)制了，
      如果該對象沒有被拷貝過葬凳，則調(diào)用 copy_to_survivor_space 方法拷貝對象到to-space或者晉升到old generation绰垂，
      這里提一下ParNew的實現(xiàn)，因為是并發(fā)執(zhí)行的火焰，所以可能存在多個線程拷貝了同一個對象到to-space劲装，不過通過原子操作，保證了只有一個對象是有效的
    • 拷貝對象的目標(biāo)空間不一定是to-space昌简，也有可能是old generation占业，如果一個對象經(jīng)歷了很多次YGC，會從young generation直接晉升到old generation纯赎，
      為了記錄對象經(jīng)歷的YGC次數(shù)谦疾，在對象頭的mark word 數(shù)據(jù)結(jié)構(gòu)中有一個位置記錄著對象的YGC次數(shù)，也叫對象的年齡址否，如果掃描到的對象餐蔬，其年齡小于某個閾值（tenuring threshold），
      該對象會被拷貝到to-space佑附，并增加該對象的年齡樊诺，同時to-space的_top指針也會往后移動，這個新對象等待著被掃描
    • 如果該對象的年齡大于某個閾值音同，會晉升到old generation词爬，或者在拷貝到to-space時空間不足，也會提前晉升到old generation权均，晉升過程通過老年代_next_gen的promote方法實現(xiàn)顿膨，
      如果old generation也沒有足夠的空間容納該對象，則會觸發(fā)晉升失敗

• card table

  • 在進(jìn)行YGC時叽赊，如果young generation的Y對象被old generation中O對象引用恋沃，那么稱O對象存在跨代引用，而且Y對象應(yīng)該在本次垃圾回收中存活下來必指，所以old generation的對象在YGC時也是Strong root的一部分囊咏，如果每次YGC都去掃描old generation中所有對象的話，肯定會非常耗時塔橡，那么有什么好的解決方案呢
  • 如果只掃描那些有young generation對象引用的對象梅割，是不是效率可以達(dá)到最高，不過使用這種方式葛家，需要有一個地方保存這些對象的引用户辞，是一個不小的內(nèi)存開銷，所以Hotspot實現(xiàn)中癞谒，并沒采用這樣方式底燎，而是使用一個GenRemSet數(shù)據(jù)結(jié)構(gòu)刃榨，記錄包含這些對象的內(nèi)存區(qū)域是clean or dirty狀態(tài)
  • 盜圖一張-remset
  • CardTable是GenRemSet的一種實現(xiàn)，類似于一個數(shù)組书蚪，每個元素對應(yīng)著堆內(nèi)存的一塊區(qū)域是否存在跨代引用的對象喇澡，如果存在，該Card為dirty狀態(tài)
  • GenRemSet隨著堆內(nèi)存一起初始化殊校，通過具體的垃圾收集策略進(jìn)行創(chuàng)建晴玖，比如CMS和G1是不一樣的，其中CMS對應(yīng)的是CardTable
  • 接上文中YGC遍歷old generation的邏輯
    rem_set()->younger_refs_iterate(_gens[i], older_gens);
    這里rem_set()方法返回的就是已經(jīng)初始化的CardTableRS對象为流，調(diào)用younger_refs_iterate呕屎，傳入的參數(shù)分別是old generation的引用和負(fù)責(zé)遍歷old generation對象的回調(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.reibang.com/p/5037459097ee
  • 每次的動作是先清除Card的dirty狀態(tài)，對象拷貝完成再判斷是否要設(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的一個問題
  • RednaxelaFX-cryptic gc name in gc log
  • Jon Masamitsu-Our Collectors
  • 占小狼-JVM源碼分析之YGC的來龍去脈
  • 占小狼-JVM源碼分析之跨代引用CardTable