EdenSpace讲解了CMS算法中表示Ffrom和To区的ContiguousSpace，表示Eden区的EdenSpace和ConcEdenSpace，本篇继续讲解Space的子类CompactibleFreeListSpace及其相关类的实现，该类用来表示CMS算法的老年代的内存区域。

FreeChunk

FreeChunk的定义位于hotspot\src\share\vm\gc_implementation\concurrentMarkSweep\freeChunk.hpp中，是CMS中用来表示一个空闲的内存块，其包含的属性如下：

image.png

FreeChunk也是位于老年代的堆内存中，怎么跟正常的Java对象区分了？如果是32位或者64位下不开启UseCompressedOops则通过prev字段的地址最后一位来标识，如果是64位下开启UseCompressedOops则通过size字段来标识，参考如下方法的实现：

//根据addr判断这是否是一个FreeChunk，如果是返回true
static bool indicatesFreeChunk(const HeapWord* addr) {
    return ((volatile FreeChunk*)addr)->is_free();
}
 
bool is_free() const volatile {
    LP64_ONLY(if (UseCompressedOops) return mark()->is_cms_free_chunk(); else)
    return (((intptr_t)_prev) & 0x1) == 0x1;
}
 
markOop mark()     const volatile { return (markOop)_size; }
 
//size属性的读写
size_t size() const volatile {
    LP64_ONLY(if (UseCompressedOops) return mark()->get_size(); else )
    return _size;
  }
 
void set_size(size_t sz) {
    LP64_ONLY(if (UseCompressedOops) set_mark(markOopDesc::set_size_and_free(sz)); else )
    _size = sz;
}
 
void set_mark(markOop m)          { _size = (size_t)m; }
 
//prev属性的读写，|0x1就是将ptr地址的最后一位变成1，ptr因为需要按照内存页对齐，所以ptr通常最后的N位都是0，N位取决于内存页的大小
void link_prev(FreeChunk* ptr) {
    LP64_ONLY(if (UseCompressedOops) _prev = ptr; else)
    _prev = (FreeChunk*)((intptr_t)ptr | 0x1);
}
 
FreeChunk* prev() const {
    //& ~(0x3)实际就是把ptr地址的最后两位换成0，最后一位表示是否是FreeChunk，倒数第二位用于表示该FreeChunk不能执行合并
    return (FreeChunk*)(((intptr_t)_prev) & ~(0x3));
}
 
//将FreeChunk标记为非Free
void markNotFree() {
    // Set _prev (klass) to null before (if) clearing the mark word below
    _prev = NULL;
#ifdef _LP64
    if (UseCompressedOops) {
      OrderAccess::storestore();
      set_mark(markOopDesc::prototype());
    }
#endif
    assert(!is_free(), "Error");
  }
 
bool cantCoalesce() const {
    assert(is_free(), "can't get coalesce bit on not free");
    return (((intptr_t)_prev) & 0x2) == 0x2;
  }
 
//dontCoalesce用于标记当前FreeChunk不支持合并成一个更大的FreeChunk
void dontCoalesce() {
    // the block should be free
    assert(is_free(), "Should look like a free block");
    //| 0x2将prev地址的倒数第二位置为1
    _prev = (FreeChunk*)(((intptr_t)_prev) | 0x2);
  }

理解上述逻辑的关键在于，FreeChunk的前2个字宽和普通的Java对象即OopDesc是一致的，OopDesc的定义如下：

markOop其实是markOopDesc*的别名，也是一个指针，对应于FreeChunk的size属性，size_t的长度跟指针的长度是一致的，对应一个字宽，64位下8字节，32位下4字节；第二个字宽，_metadata对应于_prev。在64位下开启指针压缩的条件下，都读取第一个字宽的数据，在32位或者64位下不开启指针压缩时都读取第二个字宽的数据，然后根据特殊的位来判断是否是FreeChunk。

PromotionInfo

PromotionInfo的定义在同目录的promotionInfo.hpp中，主要用于保存分配的oop，并在必要时保存oop的对象头。其包含的属性如下：

• CompactibleFreeListSpace* _space; //关联的CompactibleFreeListSpace
• PromotedObject* _promoHead; // PromotedObject链表的头元素
• PromotedObject* _promoTail; // PromotedObject链表的尾元素
• SpoolBlock* _spoolHead; // SpoolBlock链表的头元素
• SpoolBlock* _spoolTail; // SpoolBlock链表的尾元素
• SpoolBlock* _splice_point; // 临时保存上一个spoolTail
• SpoolBlock* _spareSpool; // 已经遍历完成的SpoolBlock链表
• size_t _firstIndex; // spoolHead中下一个遍历的markOop的索引
• size_t _nextIndex; // spoolTail中下一个分配的markOop的索引
  重点关注以下方法的实现。

1、SpoolBlock
SpoolBlock继承自FreeChunk，用来保存被替换的对象头的，其定义在同目录的promotionInfo.hpp中。SpoolBlock增加了三个属性，如下：

image.png

其中bufferSize表示该Block可容纳的markOop的个数，displacedHdr表示保存的被替换的对象头markOop的数组。 重点关注其init方法的实现即可，如下：

void init() {
    bufferSize = computeBufferSize();
    //显示的初始化displacedHdr
    displacedHdr = (markOop*)&displacedHdr;
    nextSpoolBlock = NULL;
}
 
size_t computeBufferSize() {
    //size方法该内存块总的大小，减去SpoolBlock属性本身占用的空间就是剩余的可用空间了
    return (size() * sizeof(HeapWord) - sizeof(*this)) / sizeof(markOop);
}

2、PromotedObject
PromotedObject表示一个经过promoted的oop，是oop强转而来的，从而操作oop的对象头，其定义的属性是一个union结构，如下：

image.png

_next属性和_data属性都是一个字宽，因此这个union属性就是一个字宽，在内存结构上刚好对应于OopDesc的表示对象头的_mark属性，操作union属性实际就是操作对象的对象头。重点关注其next和setNext方法的实现，如下：

inline PromotedObject* next() const {
    //校验当前这个PromotedObject不是FreeChunk
    assert(!((FreeChunk*)this)->is_free(), "Error");
    PromotedObject* res;
    if (UseCompressedOops) {
      // The next pointer is a compressed oop stored in the top 32 bits
      res = (PromotedObject*)oopDesc::decode_heap_oop(_data._narrow_next);
    } else {
      res = (PromotedObject*)(_next & next_mask);
    }
    //校验res是oop
    assert(oop(res)->is_oop_or_null(true /* ignore mark word */), "Not an oop?");
    return res;
  }
  
inline void setNext(PromotedObject* x) {
    //校验表示next的位没有被占用
    assert(((intptr_t)x & ~next_mask) == 0, "Conflict in bit usage, "
           "or insufficient alignment of objects");
    if (UseCompressedOops) {
      assert(_data._narrow_next == 0, "Overwrite?");
      _data._narrow_next = oopDesc::encode_heap_oop(oop(x));
    } else {
      //|=的效果和=是一致的
      _next |= (intptr_t)x;
    }
    assert(!((FreeChunk*)this)->is_free(), "Error");
  }

即通过对象头可以把相关的oop串联起来。

3、track
track方法用于跟踪某个oop，具体来说是将这个oop放入PromotionInfo保存的PromotedObject链表中，并必要时保存原oop的对象头。其调用链如下：

image.png

其实现如下：

void PromotionInfo::track(PromotedObject* trackOop) {
  track(trackOop, oop(trackOop)->klass());
}
 
void PromotionInfo::track(PromotedObject* trackOop, Klass* klassOfOop) {
  // make a copy of header as it may need to be spooled
  markOop mark = oop(trackOop)->mark();
  //实际是清除原来的对象头，后面的setDisplacedMark和setPromotedMark相当于替换了原来的对象头
  trackOop->clear_next();
  //如果有偏向锁了
  if (mark->must_be_preserved_for_cms_scavenge(klassOfOop)) {
    //保存原来的对象头，然后设置DisplacedMark
    saveDisplacedHeader(mark);
    trackOop->setDisplacedMark();
  } else {
   
  }
  //如果_promoTail不为空则插入到_promoTail的后面
  if (_promoTail != NULL) {
    assert(_promoHead != NULL, "List consistency");
    _promoTail->setNext(trackOop);
    _promoTail = trackOop;
  } else {
    //_promoTail为空，初始化_promoHead和_promoTail
    assert(_promoHead == NULL, "List consistency");
    _promoHead = _promoTail = trackOop;
  }
  //设置PromotedMark
  assert(!trackOop->hasPromotedMark(), "Should not have been marked");
  trackOop->setPromotedMark();
}
 
 inline void clear_next()        {
    _next = 0;
    assert(!((FreeChunk*)this)->is_free(), "Error");
}
 
void PromotionInfo::saveDisplacedHeader(markOop hdr) {
  assert(_spoolHead != NULL && _spoolTail != NULL,
         "promotionInfo inconsistency");
  assert(_spoolTail->bufferSize > _nextIndex, "Off by one error at tail?");
  //保存对象头hdr
  _spoolTail->displacedHdr[_nextIndex] = hdr;
  //_nextIndex加1后等于_spoolTail->bufferSize，说明_spoolTail已经没有可用空间存储新的markOop了
  if (++_nextIndex == _spoolTail->bufferSize) { // last location in this block
    // get a new spooling block
    assert(_spoolTail->nextSpoolBlock == NULL, "tail should terminate spool list");
    //_splice_point用于临时的保存上一个_spoolTail
    _splice_point = _spoolTail;                   // save for splicing
    //获取一个新的SpoolBlock,插入到_spoolTail的后面，然后更新_spoolTail
    _spoolTail->nextSpoolBlock = getSpoolBlock(); // might fail
    _spoolTail = _spoolTail->nextSpoolBlock;      // might become NULL ...
    //置为1，下次分配就从索引为1的位置保存
    _nextIndex = 1;
  }
}
 
 
inline void setDisplacedMark() {
    _next |= displaced_mark;
    assert(!((FreeChunk*)this)->is_free(), "Error");
}
 
inline void setPromotedMark() {
    _next |= promoted_mask;
    assert(!((FreeChunk*)this)->is_free(), "Error");
  }
 
inline bool hasPromotedMark() const {
    assert(!((FreeChunk*)this)->is_free(), "Error");
    return (_next & promoted_mask) == promoted_mask;
  }
 
inline bool markOopDesc::must_be_preserved_for_cms_scavenge(Klass* klass_of_obj_containing_mark) const {
  //UseBiasedLocking表示是否使用偏向锁，默认为true
  if (!UseBiasedLocking)
    return (!is_unlocked() || !has_no_hash());
  return must_be_preserved_with_bias_for_cms_scavenge(klass_of_obj_containing_mark);
}
 
inline bool markOopDesc::must_be_preserved_with_bias_for_cms_scavenge(Klass* klass_of_obj_containing_mark) const {
  assert(UseBiasedLocking, "unexpected");
  //has_bias_pattern方法表示已经有偏向锁了
  if (has_bias_pattern() ||
      klass_of_obj_containing_mark->prototype_header()->has_bias_pattern()) {
    return true;
  }
  return (!is_unlocked() || !has_no_hash());
}
 
 bool is_unlocked() const {
    return (mask_bits(value(), biased_lock_mask_in_place) == unlocked_value);
 }
 
  bool has_bias_pattern() const {
    return (mask_bits(value(), biased_lock_mask_in_place) == biased_lock_pattern);
  }

4、 promoted_oops_iterate
promoted_oops_iterate实际有多个方法，都是用来遍历PromotedObject链表中的oop所引用的其他oop，如下图：

image.png

这些方法的定义和实现都是通过宏实现的，如下：

//SPECIALIZED_SINCE_SAVE_MARKS_CLOSURES_YOUNG宏定义不同类型的OopClosureType和nv_suffix
//PROMOTED_OOPS_ITERATE_DEFN定义具体的方法实现
SPECIALIZED_SINCE_SAVE_MARKS_CLOSURES_YOUNG(PROMOTED_OOPS_ITERATE_DEFN)
PROMOTED_OOPS_ITERATE_DEFN(OopsInGenClosure,_v)

#define PROMOTED_OOPS_ITERATE_DEFN(OopClosureType, nv_suffix)               \
                                                                           \
void PromotionInfo::promoted_oops_iterate##nv_suffix(OopClosureType* cl) {  \
 NOT_PRODUCT(verify());                                                    \
 PromotedObject *curObj, *nextObj;                                         \
 //从_promoHead开始遍历
 for (curObj = _promoHead; curObj != NULL; curObj = nextObj) {             \
    //获取下一个遍历对象
   if ((nextObj = curObj->next()) == NULL) {                               \
     //遍历完成将_promoHead和_promoTail都置为NULL
     assert(_promoTail == curObj, "Should have been the tail");            \
     _promoHead = _promoTail = NULL;                                       \
   }                                                                       \
   //如果对象头被替换了
   if (curObj->hasDisplacedMark()) {                                       \
     /* 获取原来的对象头并恢复 */                                        \
     oop(curObj)->set_mark(nextDisplacedHeader());                         \
   } else {                                                                \
     /* 恢复成初始状态的对象头 */                                     \
     oop(curObj)->init_mark();                                             \
   }                                                                       \
   /* The "promoted_mark" should now not be set */                         \
   assert(!curObj->hasPromotedMark(),                                      \
          "Should have been cleared by restoring displaced mark-word");    \
   NOT_PRODUCT(_promoHead = nextObj);                                      \
   //遍历curObj对象所有引用类型属性oop
   if (cl != NULL) oop(curObj)->oop_iterate(cl);                           \
   if (nextObj == NULL) { /* start at head of list reset above */          \
     nextObj = _promoHead;                                                 \
   }                                                                       \
 }                                                                         \
 //校验遍历完成的结果
 assert(noPromotions(), "post-condition violation");                       \
 assert(_promoHead == NULL && _promoTail == NULL, "emptied promoted list");\
 assert(_spoolHead == _spoolTail, "emptied spooling buffers");             \
 assert(_firstIndex == _nextIndex, "empty buffer");                        \
}

bool noPromotions() const {
   assert(_promoHead != NULL || _promoTail == NULL, "list inconsistency");
   return _promoHead == NULL;
 }

markOop PromotionInfo::nextDisplacedHeader() {
 //校验参数
 assert(_spoolHead != NULL, "promotionInfo inconsistency");
 assert(_spoolHead != _spoolTail || _firstIndex < _nextIndex,
        "Empty spool space: no displaced header can be fetched");
 assert(_spoolHead->bufferSize > _firstIndex, "Off by one error at head?");
 markOop hdr = _spoolHead->displacedHdr[_firstIndex];
 //增加_firstIndex，如果增加后的值等于 _spoolHead->bufferSize说明该SpoolBlock保存的markOop已经遍历完了
 if (++_firstIndex == _spoolHead->bufferSize) { // last location in this block
   //将_spoolHead归还到_spareSpool中，_spoolHead的nextSpoolBlock作为新的_spoolHead
   SpoolBlock* tmp = _spoolHead->nextSpoolBlock;
   assert(_spoolHead != _spoolTail, "Spooling storage mix-up");
   _spoolHead->nextSpoolBlock = _spareSpool;
   _spareSpool = _spoolHead;
   _spoolHead = tmp;
   //对新的spoolHead，_firstIndex被置为1，下一次遍历从索引为1的位置开始
   _firstIndex = 1;
 }
 return hdr;
}



//返回一个SpoolBlock的大小
size_t PromotionInfo::refillSize() const {
 const size_t CMSSpoolBlockSize = 256;
 //heap_word_size方法返回字宽数
 const size_t sz = heap_word_size(sizeof(SpoolBlock) + sizeof(markOop)
                                  * CMSSpoolBlockSize);
 //adjustObjectSize方法是按照对象分配的最低大小对齐                                 
 return CompactibleFreeListSpace::adjustObjectSize(sz);
}

SpoolBlock* PromotionInfo::getSpoolBlock() {
 SpoolBlock* res;
 //优先从空闲的SpoolBlock链表上分配
 if ((res = _spareSpool) != NULL) {
   _spareSpool = _spareSpool->nextSpoolBlock;
   res->nextSpoolBlock = NULL;
 } else {  // spare spool exhausted, get some from heap
   //没有空闲的SpoolBlock，refillSize方法返回SpoolBlock的大小
   res = (SpoolBlock*)(space()->allocateScratch(refillSize()));
   if (res != NULL) {
     //初始化SpoolBlock
     res->init();
   }
 }
 assert(res == NULL || res->nextSpoolBlock == NULL, "postcondition");
 return res;
 }

5、ensure_spooling_space
ensure_spooling_space用于判断是否有充足的空闲保存markOop，如果没有则获取一个新的SpollBlock，如果获取失败则返回false，否则返回true。其调用链如下：

image.png

其源码如下：

bool ensure_spooling_space() {
    return has_spooling_space() || ensure_spooling_space_work();
}
 
inline bool has_spooling_space() {
    //_spoolTail是否有空闲空间
    return _spoolTail != NULL && _spoolTail->bufferSize > _nextIndex;
}
 
//判断能否获取一个新的SpoolBlock
bool PromotionInfo::ensure_spooling_space_work() {
  assert(!has_spooling_space(), "Only call when there is no spooling space");
  //_spoolTail没有空闲空闲了，尝试获取一个新的SpoolBlock
  SpoolBlock* newSpool = getSpoolBlock();
  assert(newSpool == NULL ||
         (newSpool->bufferSize != 0 && newSpool->nextSpoolBlock == NULL),
        "getSpoolBlock() sanity check");
  if (newSpool == NULL) {
    return false;
  }
  _nextIndex = 1;
  if (_spoolTail == NULL) {
    //初始化_spoolTail
    _spoolTail = newSpool;
    if (_spoolHead == NULL) {
       //初始化_spoolHead
      _spoolHead = newSpool;
      _firstIndex = 1;
    } else {
      //不会走到此分支不可能_spoolHead不为空而_spoolTail为空
      assert(_splice_point != NULL && _splice_point->nextSpoolBlock == NULL,
             "Splice point invariant");
      _splice_point->nextSpoolBlock = newSpool;
    }
  } else {
    //_spoolTail不为空，插入到_spoolTail的后面
    assert(_spoolHead != NULL, "spool list consistency");
    _spoolTail->nextSpoolBlock = newSpool;
    _spoolTail = newSpool;
  }
  return true;
}

CompactibleFreeListSpace

1、定义
该类的定义在hotspot\src\share\vm\gc_implementation\concurrentMarkSweep\compactibleFreeListSpace.hpp中，继承自CompactibleSpace，其包含的属性如下：

• const size_t _rescan_task_size; //并行标记阶段一次rescan处理的内存块的大小
• const size_t _marking_task_size; //并行标记阶段一次mark 处理的内存块的大小
• SequentialSubTasksDone _conc_par_seq_tasks; //用来管控执行CMS GC的多个并行线程
• BlockOffsetArrayNonContigSpace _bt; //用于记录已分配的内存块的起始地址
• CMSCollector* _collector; // 关联的CMSCollector
• ConcurrentMarkSweepGeneration* _gen; //关联的ConcurrentMarkSweepGeneration
• static size_t IndexSetStart; //实际赋值等于最小内存块的字宽数
• static size_t IndexSetStride; //实际赋值等于分配对象时的最小字宽数，IndexSetStart和IndexSetStride用来限制_indexedFreeList实际使用的数组元素，如size小于IndexSetStart的_indexedFreeList数组元素实际是不使用的，会据此初始化每一个实际使用的_indexedFreeList数组元素对应的并发内存分配时使用的锁
• PromotionInfo _promoInfo; // 用于保存分配的oop
• static int _lockRank; // _freelistLock使用的锁类型
• mutable Mutex _freelistLock; //并发的从CompactibleFreeListSpace中分配内存时使用的全局锁
• LinearAllocBlock _smallLinearAllocBlock; //用于线性分配小块内存
• FreeBlockDictionary<FreeChunk>::DictionaryChoice _dictionaryChoice; //保存FreeBlockDictionary的实现类型，默认是表示二叉树的dictionaryBinaryTree
• AFLBinaryTreeDictionary* _dictionary; //用于保存大小不规整的，不满足_indexedFreeList支持的内存大小的空闲块
• AdaptiveFreeList<FreeChunk> _indexedFreeList[IndexSetSize];//用来保存不同大小的空闲内存块的链表，内存块的大小从0到IndexSetSize
• bool _fitStrategy; //是否使用最佳适配策略，由配置项UseCMSBestFit决定，默认为true
• bool _adaptive_freelists; // 是否使用自适应空闲chunk 链表，由配置项UseCMSAdaptiveFreeLists决定，默认为true
• HeapWord* _nearLargestChunk;
• HeapWord* _sweep_limit;
• mutable Mutex _parDictionaryAllocLock; //使用_dictionary并行分配内存时使用的锁
• Mutex* _indexedFreeListParLocks[IndexSetSize]; //与_indexedFreeList中实际使用的数组元素一一对应，保存其在并行分配时使用的锁

其中三个静态属性的初始化如下：

image.png

其中枚举Mutex::leaf表示锁类型，重点关注以下方法的实现。

CompactibleFreeListSpace定义了一个枚举描述内存分配时使用的常量，如下：

image.png

注意上述常量的单位都是字宽而非字节，即当申请的内存小于16字宽时使用_smallLinearAllocBlock分配内存，当申请的内存小于257字宽时使用_indexedFreeList分配。还有一个枚举FitStrategyOptions描述内存分配的适配侧率，如下：

image.png

其中FreeBlockBestFitFirst表示使用CMS内存分配时的最佳适配策略。

属性_smallLinearAllocBlock的类LinearAllocBlock实际只是一个数据结构而已，其定义也在compactibleFreeListSpace.hpp中，如下，具体通过LinearAllocBlock线性分配内存的逻辑都CompactibleFreeListSpace的相关方法中。

image.png

其所有属性都是public的， ptr表示分配内存的起始地址，word_size是剩余可分配空间的大小，实际分配过程中会不断往后移动ptr指针，同时减少word_size；refillSize是当LinearAllocBlock剩余可用空间不足时重新申请用来填充LinearAllocBlock的内存块的大小，_allocation_size_limit是通过LinearAllocBlock执行内存分配的内存大小上限，取值就是枚举SmallForLinearAlloc的值。

2、构造方法和set_cms_values
set_cms_values方法是一个静态方法，用来初始化静态属性IndexSetStart和IndexSetStride，在执行构造方法前调用。构造方法用来初始化CompactibleFreeListSpace的相关属性。这两方法的调用链如下：

image.png image.png

这两方法的实现如下：

 
void CompactibleFreeListSpace::set_cms_values() {
  // Set CMS global values
  assert(MinChunkSize == 0, "already set");
 
  //根据FreeChunk本身的大小计算FreeChunk，MinObjAlignmentInBytes等于配置项ObjectAlignmentInBytes的值，
  //该配置项表示对象分配时最小字节数，默认是8
  size_t min_chunk_size_in_bytes = align_size_up(sizeof(FreeChunk), MinObjAlignmentInBytes);
  MinChunkSize = min_chunk_size_in_bytes / BytesPerWord;
 
  assert(IndexSetStart == 0 && IndexSetStride == 0, "already set");
  IndexSetStart  = MinChunkSize;
  //MinObjAlignment由MinObjAlignmentInBytes换算成对应的字宽数，默认值是1
  IndexSetStride = MinObjAlignment;
}
 
 
CompactibleFreeListSpace::CompactibleFreeListSpace(BlockOffsetSharedArray* bs,
  MemRegion mr, bool use_adaptive_freelists,
  FreeBlockDictionary<FreeChunk>::DictionaryChoice dictionaryChoice) :
  _dictionaryChoice(dictionaryChoice),
  _adaptive_freelists(use_adaptive_freelists),
  _bt(bs, mr),
  _freelistLock(_lockRank--, "CompactibleFreeListSpace._lock", true),
  _parDictionaryAllocLock(Mutex::leaf - 1,  // == rank(ExpandHeap_lock) - 1
                          "CompactibleFreeListSpace._dict_par_lock", true),
  _rescan_task_size(CardTableModRefBS::card_size_in_words * BitsPerWord *
                    CMSRescanMultiple), //CMSRescanMultiple的默认值是32，表示并行rescan任务处理的卡表项的个数
  _marking_task_size(CardTableModRefBS::card_size_in_words * BitsPerWord *
                    CMSConcMarkMultiple), //CMSConcMarkMultiple的默认值是32，表示并行mark任务处理的卡表项的个数
  _collector(NULL)
{
  assert(sizeof(FreeChunk) / BytesPerWord <= MinChunkSize,
         "FreeChunk is larger than expected");
  _bt.set_space(this);
  //调用父类的initialize方法，初始化父类的相关属性
  initialize(mr, SpaceDecorator::Clear, SpaceDecorator::Mangle);
  // dictionaryChoice枚举表示FreeBlockDictionary的实现类型，现阶段默认使用二叉树实现，dictionarySplayTree的实现被暂时禁用了
  switch (dictionaryChoice) {
    case FreeBlockDictionary<FreeChunk>::dictionaryBinaryTree:
      _dictionary = new AFLBinaryTreeDictionary(mr);
      break;
    case FreeBlockDictionary<FreeChunk>::dictionarySplayTree:
    case FreeBlockDictionary<FreeChunk>::dictionarySkipList:
    default:
      warning("dictionaryChoice: selected option not understood; using"
              " default BinaryTreeDictionary implementation instead.");
  }
  assert(_dictionary != NULL, "CMS dictionary initialization");
  //初始化_indexedFreeList数组，每个FreeList都是空的，后面按需填充
  initializeIndexedFreeListArray();
 
  
  //use_adaptive_freelists参数最终由配置项UseCMSAdaptiveFreeLists决定，该配置项默认为true
  //注意如果使用adaptive_freelists分配内存，则优先从_smallLinearAllocBlock中分配
  if (!use_adaptive_freelists) {
    //如果不使用adaptive_freelists分配内存
    FreeChunk* fc = _dictionary->get_chunk(mr.word_size(),
                                           FreeBlockDictionary<FreeChunk>::atLeast);
    HeapWord* addr = (HeapWord*) fc;
    _smallLinearAllocBlock.set(addr, fc->size() ,
      1024*SmallForLinearAlloc, fc->size());
  } else {
    //SmallForLinearAlloc是枚举，值为16
    _smallLinearAllocBlock.set(0, 0, 1024*SmallForLinearAlloc,
                               SmallForLinearAlloc);
  }
  // CMSIndexedFreeListReplenish是一个配置项，表示使用多少个chunk填充_indexedFreeList,默认值是4
  //这里是校验其不小于1
  CMSIndexedFreeListReplenish = MAX2((uintx)1, CMSIndexedFreeListReplenish);
  _promoInfo.setSpace(this);
  //UseCMSBestFit表示使用CMS的最佳适配策略，默认是true
  if (UseCMSBestFit) {
    _fitStrategy = FreeBlockBestFitFirst;
  } else {
    _fitStrategy = FreeBlockStrategyNone;
  }
  //check_free_list_consistency方法在生产版本中是空实现
  check_free_list_consistency();
 
  // Initialize locks for parallel case.
 
  if (CollectedHeap::use_parallel_gc_threads()) {
    for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
      //初始化并行分配内存用到的锁，注意并不是所有的_indexedFreeList元素都有对应的锁
      _indexedFreeListParLocks[i] = new Mutex(Mutex::leaf - 1, // == ExpandHeap_lock - 1
                                              "a freelist par lock",
                                              true);
      DEBUG_ONLY(
        _indexedFreeList[i].set_protecting_lock(_indexedFreeListParLocks[i]);
      )
    }
    _dictionary->set_par_lock(&_parDictionaryAllocLock);
  }
}
 
void CompactibleFreeListSpace::initializeIndexedFreeListArray() {
  //初始化_indexedFreeList，注意起始size是从0开始的，实际size为0的元素并不会使用
  for (size_t i = 0; i < IndexSetSize; i++) {
    //reset方法将FreeList重置，并且设置hint
    _indexedFreeList[i].reset(IndexSetSize);
    //设置该FreeList保存的Chunk的大小
    _indexedFreeList[i].set_size(i);
    assert(_indexedFreeList[i].count() == 0, "reset check failed");
    assert(_indexedFreeList[i].head() == NULL, "reset check failed");
    assert(_indexedFreeList[i].tail() == NULL, "reset check failed");
    assert(_indexedFreeList[i].hint() == IndexSetSize, "reset check failed");
  }
}
 
#ifndef PRODUCT
void CompactibleFreeListSpace::check_free_list_consistency() const {
  assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size() <= IndexSetSize),
    "Some sizes can't be allocated without recourse to"
    " linear allocation buffers");
  assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size()*HeapWordSize == sizeof(TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >)),
    "else MIN_TREE_CHUNK_SIZE is wrong");
  assert(IndexSetStart != 0, "IndexSetStart not initialized");
  assert(IndexSetStride != 0, "IndexSetStride not initialized");
}
#endif

3、getFromListGreater / getChunkFromGreater
getFromListGreater方法用于从比指定大小大的FreeList中查找空闲的内存块，找到后再按照指定大小做切分，多余的内存块归还到FreeList中。getChunkFromGreater方法包含了getFromListGreater，还支持从_dictionary属性保存的空闲内存块二叉树中查找大于指定大小的内存块，同样的，找到后按照指定大小做切分，多余的内存块根据大小归还到FreeList或者_dictionary属性中保存。这两方法的调用链如下：

image.png image.png

其实现如下：

/* Requires fl->size >= numWords + MinChunkSize */
FreeChunk* CompactibleFreeListSpace::getFromListGreater(AdaptiveFreeList<FreeChunk>* fl,
  size_t numWords) {
  //获取FreeList链表头部的空闲的内存块
  FreeChunk *curr = fl->head();
  size_t oldNumWords = curr->size();
  //校验参数
  assert(numWords >= MinChunkSize, "Word size is too small");
  assert(curr != NULL, "List is empty");
  assert(oldNumWords >= numWords + MinChunkSize,
        "Size of chunks in the list is too small");
  
  //将该内存块从链表中移除
  fl->remove_chunk(curr);
  //将curr按照numWords切分，多余的内存块放到_indexedFreeList或者_dictionary中
  FreeChunk* new_chunk = splitChunkAndReturnRemainder(curr, numWords);
  assert(new_chunk == NULL || new_chunk->is_free(),
    "Should be returning a free chunk");
  return new_chunk;
}
 
FreeChunk*
CompactibleFreeListSpace::splitChunkAndReturnRemainder(FreeChunk* chunk,
  size_t new_size) {
  assert_locked();
  //获取chunk原来的大小
  size_t size = chunk->size();
  assert(size > new_size, "Split from a smaller block?");
  assert(is_aligned(chunk), "alignment problem");
  assert(size == adjustObjectSize(size), "alignment problem");
  //计算需要切分掉的大小
  size_t rem_size = size - new_size;
  assert(rem_size == adjustObjectSize(rem_size), "alignment problem");
  assert(rem_size >= MinChunkSize, "Free chunk smaller than minimum");
  //ffc就表示被切分掉的内存块
  FreeChunk* ffc = (FreeChunk*)((HeapWord*)chunk + new_size);
  assert(is_aligned(ffc), "alignment problem");
  ffc->set_size(rem_size);
  ffc->link_next(NULL);
  ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads.
  //强制所有的修改指令执行
  OrderAccess::storestore();
  assert(chunk->is_free() && ffc->is_free(), "Error");
  //bt中记录新切分出来的内存块的起始位置
  _bt.split_block((HeapWord*)chunk, chunk->size(), new_size);
  if (rem_size < SmallForDictionary) {
    //是否并行垃圾收集,如果是则获取对应FreeList的锁
    bool is_par = (SharedHeap::heap()->n_par_threads() > 0);
    if (is_par) _indexedFreeListParLocks[rem_size]->lock();
    assert(!is_par ||
           (SharedHeap::heap()->n_par_threads() ==
            SharedHeap::heap()->workers()->active_workers()), "Mismatch");
    //将新的被切分出去的内存块放入对应大小的_indexedFreeList中        
    returnChunkToFreeList(ffc);
    split(size, rem_size);
    //解锁
    if (is_par) _indexedFreeListParLocks[rem_size]->unlock();
  } else {
    //将新的被切分出来的内存块放到_dictionary中
    returnChunkToDictionary(ffc);
    split(size ,rem_size);
  }
  //重置chunk的大小
  chunk->set_size(new_size);
  return chunk;
}
 
void
CompactibleFreeListSpace::returnChunkToFreeList(FreeChunk* fc) {
  assert_locked();
  size_t size = fc->size();
  //校验fc是一个单独的没有被切分的内存块
  _bt.verify_single_block((HeapWord*) fc, size);
  //校验fc还未被分配出去
  _bt.verify_not_unallocated((HeapWord*) fc, size);
  if (_adaptive_freelists) {
     //如果使用adaptive_freelists，插入到链表尾部
    _indexedFreeList[size].return_chunk_at_tail(fc);
  } else {
     //插入到链表头部
    _indexedFreeList[size].return_chunk_at_head(fc);
  }
}
 
void
CompactibleFreeListSpace::returnChunkToDictionary(FreeChunk* chunk) {
  assert_locked();
 
  size_t size = chunk->size();
  _bt.verify_single_block((HeapWord*)chunk, size);
  //free方法实际是调整_unallocated_block属性，标记chunk对应的内存块未分配出去
  _bt.freed((HeapWord*)chunk, size);
  //将chunk放到_dictionary中管理
  _dictionary->return_chunk(chunk);
}
 
FreeChunk* CompactibleFreeListSpace::getChunkFromGreater(size_t numWords) {
  FreeChunk* ret;
 
  assert(numWords >= MinChunkSize, "Size is less than minimum");
  assert(linearAllocationWouldFail() || bestFitFirst(),
    "Should not be here");
 
  size_t i;
  size_t currSize = numWords + MinChunkSize;
  assert(currSize % MinObjAlignment == 0, "currSize should be aligned");
  //从currSize开始遍历查找，如果某个FreeList有空闲的内存块，则从该FreeList中分配指定大小的内存块
  for (i = currSize; i < IndexSetSize; i += IndexSetStride) {
    AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[i];
    if (fl->head()) {
      ret = getFromListGreater(fl, numWords);
      assert(ret == NULL || ret->is_free(), "Should be returning a free chunk");
      return ret;
    }
  }
  //所有的_indexedFreeList都是空的，尝试从dictionary中分配
  //从dictionary中分配时要求内存大于SmallForDictionary，即IndexSetSize
  currSize = MAX2((size_t)SmallForDictionary,
                  (size_t)(numWords + MinChunkSize));
 
  /* Try to get a chunk that satisfies request, while avoiding
     fragmentation that can't be handled. */
  {
    //从_dictionary中查找满足大小的内存块
    ret =  dictionary()->get_chunk(currSize);
    if (ret != NULL) {
      assert(ret->size() - numWords >= MinChunkSize,
             "Chunk is too small");
      //调整bt的_unallocated_block属性，表示ret对应的内存块被分配出去了       
      _bt.allocated((HeapWord*)ret, ret->size());
      /*将ret按照numWords做切分，多余的内存块归还到freeList或者_dictionary中*/
      (void) splitChunkAndReturnRemainder(ret, numWords);
      /* Label this as no longer a free chunk. */
      assert(ret->is_free(), "This chunk should be free");
      //去掉prev引用
      ret->link_prev(NULL);
    }
    assert(ret == NULL || ret->is_free(), "Should be returning a free chunk");
    return ret;
  }
  ShouldNotReachHere();
}
 
bool CompactibleFreeListSpace::linearAllocationWouldFail() const {
  return _smallLinearAllocBlock._word_size == 0;
}
 
 
FreeBlockDictionary<FreeChunk>* dictionary() const { return _dictionary; }

4、split / coalBirth / coalDeath
split方法是某个内存块发生切分时调用的，用来增减AllocationStats类维护的计数器，_indexedFreeList和_dictionary都有一个AllocationStats类属性。coalBirth和coalDeath的功能同split，不过是在发生内存块合并时调用的。这几个方法涉及的计数器的定义如下：

• ssize_t _coal_births; // 因为内存块合并增加的内存块的个数
• ssize_t _coal_deaths; // 因为内存块合并而减少的内存块的个数
• ssize_t _split_births; // 因为内存块切分增加的内存块的个数
• ssize_t _split_deaths; // 因为内存块切分减少的内存块的个数
• ssize_t _surplus; // 一个综合指标，CompactibleFreeListSpace::bestFitSmall方法使用的，随着_coal_births和_split_births的增加而减少，随着_coal_deaths和_split_deaths的增加而减少
  其实现如下：

//from是被切分前的大小，to1是被切分后多余的内存块的大小
void CompactibleFreeListSpace::split(size_t from, size_t to1) {
  size_t to2 = from - to1;
  splitDeath(from);
  split_birth(to1);
  split_birth(to2);
}
 
void CompactibleFreeListSpace::splitDeath(size_t size) {
  if (size  < SmallForDictionary) {
    smallSplitDeath(size);
  } else {
    //底层实现跟smallSplitDeath，都是调整计数器
    dictionary()->dict_census_update(size,
                                   true /* split */,
                                   false /* birth */);
  }
}
 
void CompactibleFreeListSpace::smallSplitDeath(size_t size) {
  assert(size < SmallForDictionary, "Size too large for indexed list");
  AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
  //这两方法都是调整AdaptiveFreeList的_allocation_stats属性保存的计数器，用来统计内存分配情况
  fl->increment_split_deaths();
  fl->decrement_surplus();
}
 
//AdaptiveFreeList的实现
void increment_split_deaths() {
    assert_proper_lock_protection();
    _allocation_stats.increment_split_deaths();
}
 
void decrement_surplus() {
    assert_proper_lock_protection();
    _allocation_stats.decrement_surplus();
  }
 
//_allocation_stats属性即AllocationStats类的实现
void increment_split_deaths() { _split_deaths++; }
 
 void decrement_surplus() { _surplus--; }
 
//实现同splitDeath，也是调整计数器
void CompactibleFreeListSpace::split_birth(size_t size) {
  if (size  < SmallForDictionary) {
    smallSplitBirth(size);
  } else {
    dictionary()->dict_census_update(size,
                                   true /* split */,
                                   true /* birth */);
  }
}
 
 
void CompactibleFreeListSpace::smallSplitBirth(size_t size) {
  assert(size < SmallForDictionary, "Size too large for indexed list");
  AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
  fl->increment_split_births();
  fl->increment_surplus();
}
 
//coalBirth实现同上，增减AllocationStats类维护的计数器
void CompactibleFreeListSpace::coalBirth(size_t size) {
  if (size  < SmallForDictionary) {
    smallCoalBirth(size);
  } else {
    dictionary()->dict_census_update(size,
                                   false /* split */,
                                   true /* birth */);
  }
}
 
void CompactibleFreeListSpace::smallCoalBirth(size_t size) {
  assert(size < SmallForDictionary, "Size too large for indexed list");
  AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
  fl->increment_coal_births();
  fl->increment_surplus();
}
 
void CompactibleFreeListSpace::coalDeath(size_t size) {
  if(size  < SmallForDictionary) {
    smallCoalDeath(size);
  } else {
    dictionary()->dict_census_update(size,
                                   false /* split */,
                                   false /* birth */);
  }
}
 
void CompactibleFreeListSpace::smallCoalDeath(size_t size) {
  assert(size < SmallForDictionary, "Size too large for indexed list");
  AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
  fl->increment_coal_deaths();
  fl->decrement_surplus();
}

这些方法的调用链如下：

image.png image.png image.png