part 7

UseConcMarkSweepGC下的內存申請流程分析

-XX:+UseConcMarkSweepGC俗稱CMS灭必，是一種減少GC停頓時間的堆管理方案，使用的堆管理器是GenCollectedHeap乃摹，新生代堆類型是ParNew禁漓，老年代是ConcurrentMarkSweepGeneration，新生代使用多線程版本的copy算法來進行垃圾收集孵睬，將新生代分為Eden + From + To三個空間區(qū)域播歼；老年代使用CMS來進行周期性的垃圾收集，可以通過設置CMSInitiatingOccupancyFraction來讓CMS檢測是否需要進行一次CMS GC掰读，CMSInitiatingOccupancyFraction的默認值為92%秘狞，也就是如果老年代的空間使用占了92%，那么就會進行一次CMS GC蹈集，這個默認值是計算出來的：

void ConcurrentMarkSweepGeneration::init_initiating_occupancy(intx io, uintx tr) {
  assert(io <= 100 && tr <= 100, "Check the arguments");
  if (io >= 0) {
    _initiating_occupancy = (double)io / 100.0;
  } else {
    _initiating_occupancy = ((100 - MinHeapFreeRatio) +
                             (double)(tr * MinHeapFreeRatio) / 100.0)
                            / 100.0;
  }
}

參數(shù)io是CMSInitiatingOccupancyFraction烁试，trCMSTriggerRatio；是如果設置了CMSInitiatingOccupancyFraction拢肆，那么_initiating_occupancy就是(double)io / 100.0减响，否則通過else分支中的計算分支來計算，假設沒有設置CMSTriggerRatio郭怪，默認就是80支示，MinHeapFreeRatio是40；那么計算結果就是0.92移盆；CMS的GC分為background gc和foreground gc悼院，前者是CMS線程進行不但檢測是否需要進行CMS GC來實現(xiàn)垃圾回收的伤为，屬于后臺任務咒循；而后者是被"Allocation Fail"或者“Promotion Fail”觸發(fā)的，是一種主動的GC绞愚，而主動GC是要全程STW的叙甸，在實現(xiàn)上使用了SerialOld的策略，使用標記-清除-整理算法來進行整個堆空間的垃圾回收位衩；關于CMS GC的詳細細節(jié)另論裆蒸，本文的重點在于UseConcMarkSweepGC下的對象內存分配策略探索。

在UseConcMarkSweepGC下對象依然首先在Eden中進行內存申請糖驴，UseConcMarkSweepGC新生代使用的是ParNew僚祷，是DefNew的子類佛致，ParNew上的GC是DefNew上GC的多線程版本，在ParNew上進行空間分配應該也和DefNew差不多辙谜，下面來看看UseConcMarkSweepGC下內存分配的全流程俺榆。

因為前面的文章已經分析過對象在UseSerialGC下的內存申請流程，所以對于CMS的內存申請直接從CollectedHeap::common_mem_allocate_noinit函數(shù)開始看起装哆，在UseSerialGC的時候也說過該函數(shù)罐脊，這個函數(shù)首先allocate_from_tlab函數(shù)來試圖從TLAB申請空間，如果無法滿足蜕琴，那么就重新申請一塊TLAB萍桌，申請一塊TLAB和為對象申請空間的流程對于堆來說都是內存申請，所以后續(xù)的流程是一致的凌简；如果通過TLAB無法申請到內存上炎，那么就通過Universe::heap()->mem_allocate來直接在堆中申請內存，這個時候就要加鎖了雏搂，因為堆面向的是所有線程反症，不像TLAB是線程私有的，所以會存在多線程競爭的問題畔派，所以但愿TLAB可以有效铅碍；GenCollectorPolicy::mem_allocate_work將完成再堆中內存申請的流程，下面就主要來分析一下這個函數(shù)的具體實現(xiàn)线椰。

    // First allocation attempt is lock-free.
    Generation *young = gch->young_gen();
    assert(young->supports_inline_contig_alloc(),
      "Otherwise, must do alloc within heap lock");
    if (young->should_allocate(size, is_tlab)) {
      result = young->par_allocate(size, is_tlab);
      if (result != NULL) {
        assert(gch->is_in_reserved(result), "result not in heap");
        return result;
      }
    }

young->should_allocate用于判斷是否應該在新生代進行空間申請胞谈，大對象應該直接在老年代進行分配，如果不是大對象憨愉，那么就會通過young->par_allocate來進行空間申請烦绳，young->par_allocate使用的是DefNew的實現(xiàn)，ParNew繼承了DefNew的young->par_allocate實現(xiàn)配紫；

HeapWord* DefNewGeneration::par_allocate(size_t word_size,
                                         bool is_tlab) {
  HeapWord* res = eden()->par_allocate(word_size);
  if (CMSEdenChunksRecordAlways && _old_gen != NULL) {
    _old_gen->sample_eden_chunk();
  }
  return res;
}

可以看到是向Eden空間申請內存径密，具體實現(xiàn)時通過ContiguousSpace::par_allocate_impl來進行的，關于這塊的內容前面的文章已經分析過躺孝，不再贅述享扔，因為使用copying算法來進行垃圾回收，不會存在內存碎片問題植袍，所以可以使用指針碰撞算法來進行空間分配惧眠，所謂指針碰撞就是使用一個top指針，來標記當前空閑內存的起始地址于个，分配一塊size大小的內存空間的實現(xiàn)就是將top指針向前移動size即可實現(xiàn)氛魁；如果無法從Eden空間分配到內存，那么就要試圖從From區(qū)域分配內存了，gch->attempt_allocation將實現(xiàn)先嘗試從Eden區(qū)域申請內存秀存，如果無法成功捶码，那么嘗試從From區(qū)域分配，如果還不可以或链，那么就從Old區(qū)域分配的邏輯宙项，具體實現(xiàn)如下：

HeapWord* GenCollectedHeap::attempt_allocation(size_t size,
                                               bool is_tlab,
                                               bool first_only) {
  HeapWord* res = NULL;
  if (_young_gen->should_allocate(size, is_tlab)) {
    res = _young_gen->allocate(size, is_tlab);
    if (res != NULL || first_only) {
      return res;
    }
  }
  if (_old_gen->should_allocate(size, is_tlab)) {
    res = _old_gen->allocate(size, is_tlab);
  }
  return res;
}

_young_gen->allocate將會從From區(qū)域嘗試申請內存:

HeapWord* DefNewGeneration::allocate(size_t word_size, bool is_tlab) {
  // This is the slow-path allocation for the DefNewGeneration.
  // Most allocations are fast-path in compiled code.
  // We try to allocate from the eden.  If that works, we are happy.
  // Note that since DefNewGeneration supports lock-free allocation, we
  // have to use it here, as well.
  HeapWord* result = eden()->par_allocate(word_size);
  if (result != NULL) {
    if (CMSEdenChunksRecordAlways && _old_gen != NULL) {
      _old_gen->sample_eden_chunk();
    }
  } else {
    // If the eden is full and the last collection bailed out, we are running
    // out of heap space, and we try to allocate the from-space, too.
    // allocate_from_space can't be inlined because that would introduce a
    // circular dependency at compile time.
    result = allocate_from_space(word_size);
  }
  return result;
}

eden()->par_allocate將從Eden區(qū)域申請內存，如果無法滿足株扛，那么就通過allocate_from_space從From區(qū)域進行內存分配尤筐；

// The last collection bailed out, we are running out of heap space,
// so we try to allocate the from-space, too.
HeapWord* DefNewGeneration::allocate_from_space(size_t size) {
  bool should_try_alloc = should_allocate_from_space() || GCLocker::is_active_and_needs_gc();

  // If the Heap_lock is not locked by this thread, this will be called
  // again later with the Heap_lock held.
  bool do_alloc = should_try_alloc && (Heap_lock->owned_by_self()
                                       || (SafepointSynchronize::is_at_safepoint()
                                           && Thread::current()->is_VM_thread()));
  HeapWord* result = NULL;
  if (do_alloc) {
    result = from()->allocate(size);
  }
  return result;
}

當然，需要判斷是否允許在From區(qū)域進行內存分配洞就，如果不允許盆繁，那么還是無法在From區(qū)域進行分配；should_allocate_from_space將完成這個判斷旬蟋，當然油昂，如果當前有線程在進行GC，那么是運行從From區(qū)域進行內存分配的倾贰，下面看看should_allocate_from_space函數(shù)的具體判斷邏輯：

  bool should_allocate_from_space() const {
    return _should_allocate_from_space;
  }

  void clear_should_allocate_from_space() {
    _should_allocate_from_space = false;
  }
  void set_should_allocate_from_space() {
    _should_allocate_from_space = true;
  }

很簡單冕碟，直接返回_should_allocate_from_space的值，所以來看看在什么時候設置了該值即可找到判斷邏輯：

<img width="811" alt="2018-11-15 10 57 21" src="https://user-images.githubusercontent.com/16225796/48561231-77a4fe00-e92a-11e8-8fa9-bc88a06b4656.png">

判斷條件還是比較嚴格的匆浙，首先collection_attempt_is_safe是true安寺，并且Eden已經滿了，collection_attempt_is_safe函數(shù)的實現(xiàn)如下：

bool DefNewGeneration::collection_attempt_is_safe() {
  if (!to()->is_empty()) {
    log_trace(gc)(":: to is not empty ::");
    return false;
  }
  if (_old_gen == NULL) {
    GenCollectedHeap* gch = GenCollectedHeap::heap();
    _old_gen = gch->old_gen();
  }
  return _old_gen->promotion_attempt_is_safe(used());
}

如果To區(qū)域不為空首尼，那么就直接不可以在From區(qū)域進行分配挑庶，To區(qū)域不為空就說明發(fā)生了“Promotion Fail”，如果沒有發(fā)生過“Promotion Fail”软能，那么判斷晉升是否是安全的迎捺，通過_old_gen->promotion_attempt_is_safe函數(shù)來實現(xiàn)：

bool ConcurrentMarkSweepGeneration::promotion_attempt_is_safe(size_t max_promotion_in_bytes) const {
  size_t available = max_available();
  size_t av_promo  = (size_t)gc_stats()->avg_promoted()->padded_average();
  bool   res = (available >= av_promo) || (available >= max_promotion_in_bytes);
  return res;
}

available是老年代可用內存大小，av_promo是新生代評價晉升對象大小查排，max_promotion_in_bytes是新生代的使用量（Eden + From）凳枝，所以，如果老年代的可用空間大于新生代評價晉升對象大小跋核，或者大于新生代的使用量岖瑰，那么就說明年輕代晉升是安全的，否則就是不安全的了罪；

總結一下锭环，如果當前有線程在進行GC聪全，或者Eden區(qū)域已經滿了泊藕，或者老年代判斷晉升是安全的，那么就運行在From區(qū)域進行分配，否則只能到老年代去分配了娃圆；
如果新生代（包括從Eden和From區(qū)域）無法申請到內存的話玫锋，那么就要去老年代試試了，_old_gen->should_allocate首先判斷是否可以在老年代進行內存申請讼呢，如果允許撩鹿，那么就通過_old_gen->allocate函數(shù)來申請內存，下面先來看看_old_gen->should_allocate的實現(xiàn)悦屏；

  // Returns "true" iff this generation should be used to allocate an
  // object of the given size.  Young generations might
  // wish to exclude very large objects, for example, since, if allocated
  // often, they would greatly increase the frequency of young-gen
  // collection.
  virtual bool should_allocate(size_t word_size, bool is_tlab) {
    bool result = false;
    size_t overflow_limit = (size_t)1 << (BitsPerSize_t - LogHeapWordSize);
    if (!is_tlab || supports_tlab_allocation()) {
      result = (word_size > 0) && (word_size < overflow_limit);
    }
    return result;
  }

如果上述函數(shù)判斷是true节沦，那么就通過_old_gen->allocate來從老年代申請內存：

HeapWord* ConcurrentMarkSweepGeneration::allocate(size_t size, bool tlab) {
  CMSSynchronousYieldRequest yr;
  MutexLockerEx x(freelistLock(), Mutex::_no_safepoint_check_flag);
  return have_lock_and_allocate(size, tlab);
}

HeapWord* ConcurrentMarkSweepGeneration::have_lock_and_allocate(size_t size,
                                                                bool   tlab /* ignored */) {
  assert_lock_strong(freelistLock());
  size_t adjustedSize = CompactibleFreeListSpace::adjustObjectSize(size);
  HeapWord* res = cmsSpace()->allocate(adjustedSize);
  // Allocate the object live (grey) if the background collector has
  // started marking. This is necessary because the marker may
  // have passed this address and consequently this object will
  // not otherwise be greyed and would be incorrectly swept up.
  // Note that if this object contains references, the writing
  // of those references will dirty the card containing this object
  // allowing the object to be blackened (and its references scanned)
  // either during a preclean phase or at the final checkpoint.
  if (res != NULL) {
    // We may block here with an uninitialized object with
    // its mark-bit or P-bits not yet set. Such objects need
    // to be safely navigable by block_start().
    assert(oop(res)->klass_or_null() == NULL, "Object should be uninitialized here.");
    assert(!((FreeChunk*)res)->is_free(), "Error, block will look free but show wrong size");
    collector()->direct_allocated(res, adjustedSize);
    _direct_allocated_words += adjustedSize;
    // allocation counters
    NOT_PRODUCT(
      _numObjectsAllocated++;
      _numWordsAllocated += (int)adjustedSize;
    )
  }
  return res;
}

CompactibleFreeListSpace將會負責CMS老年代的內存分配工作，這里需要說一下的是础爬，CMS老年代和DefNew或者ParNew都不一樣甫贯，CMS老年代堆可能會產生內存碎片，所以無法使用指針碰撞算法來進行內存分配看蚜，CMS老年代使用了稱為空閑列表（Free-List）的算法來管理老年代的內存叫搁，下面來看看CompactibleFreeListSpace的allocate函數(shù)的實現(xiàn)：

HeapWord* CompactibleFreeListSpace::allocate(size_t size) {
  HeapWord* res = NULL;
  res = allocate_adaptive_freelists(size);
  if (res != NULL) {
    FreeChunk* fc = (FreeChunk*)res;
    fc->markNotFree();
    // Verify that the block offset table shows this to
    // be a single block, but not one which is unallocated.
    _bt.verify_single_block(res, size);
    _bt.verify_not_unallocated(res, size);
  }
  return res;
}

allocate_adaptive_freelists函數(shù)將盡最大努力來找到一塊合適的內存，這里面的流程也是非常復雜的供炎，但是這里的實現(xiàn)像極了C++ STL中內存池的實現(xiàn)渴逻，所以如果有條件的話還是希望去分析一下C++ STL內存池的相關實現(xiàn)。下面來看看allocate_adaptive_freelists函數(shù)的具體實現(xiàn)音诫。

<img width="825" alt="2018-11-15 11 21 27" src="https://user-images.githubusercontent.com/16225796/48563346-13d10400-e92f-11e8-9156-ca6b5bc9dbb3.png">

這里順便說一下惨奕，如果從Old區(qū)域中也無法滿足申請要求，那么就得去通過expand_heap_and_allocate擴展堆再來allocate了竭钝，如果還不行墓贿，那么就執(zhí)行進行GC了，VM_GenCollectForAllocation將會被放在VMThread中等待執(zhí)行蜓氨，具體執(zhí)行Minor GC還是FullGC需要具體判斷聋袋，這部分內容在前面的文章中分析過，就不再贅述穴吹，下面將詳細分析CMS Free-List內存分配的實現(xiàn)細節(jié)幽勒，也就是allocate_adaptive_freelists函數(shù)的具體實現(xiàn)細節(jié)。

HeapWord* CompactibleFreeListSpace::allocate_adaptive_freelists(size_t size) {
  assert_lock_strong(freelistLock());
  HeapWord* res = NULL;
  assert(size == adjustObjectSize(size),
         "use adjustObjectSize() before calling into allocate()");

  // Strategy
  //   if small
  //     exact size from small object indexed list if small
  //     small or large linear allocation block (linAB) as appropriate
  //     take from lists of greater sized chunks
  //   else
  //     dictionary
  //     small or large linear allocation block if it has the space
  // Try allocating exact size from indexTable first
  if (size < IndexSetSize) {
    res = (HeapWord*) getChunkFromIndexedFreeList(size);
    if(res != NULL) {
      assert(res != (HeapWord*)_indexedFreeList[size].head(),
        "Not removed from free list");
      // no block offset table adjustment is necessary on blocks in
      // the indexed lists.

    // Try allocating from the small LinAB
    } else if (size < _smallLinearAllocBlock._allocation_size_limit &&
        (res = getChunkFromSmallLinearAllocBlock(size)) != NULL) {
        // if successful, the above also adjusts block offset table
        // Note that this call will refill the LinAB to
        // satisfy the request.  This is different that
        // evm.
        // Don't record chunk off a LinAB?  smallSplitBirth(size);
    } else {
      // Raid the exact free lists larger than size, even if they are not
      // overpopulated.
      res = (HeapWord*) getChunkFromGreater(size);
    }
  } else {
    // Big objects get allocated directly from the dictionary.
    res = (HeapWord*) getChunkFromDictionaryExact(size);
    if (res == NULL) {
      // Try hard not to fail since an allocation failure will likely
      // trigger a synchronous GC.  Try to get the space from the
      // allocation blocks.
      res = getChunkFromSmallLinearAllocBlockRemainder(size);
    }
  }

  return res;
}

CMS使用的Free-List分配算法策略復雜港令，當然復雜帶來的好處是高效的內存分配速率啥容；這一塊內容日后再來整理。