Do It Yourself (OpenJDK) Garbage Collector

{
  GCTraceTime(Info, gc) time("Step 0: Prologue", NULL);

  // Commit marking bitmap memory. There are several upsides of doing this
  // before the cycle: no memory is taken if GC is not happening, the memory
  // is "cleared" on first touch, and untouched parts of bitmap are mapped
  // to zero page, boosting performance on sparse heaps.
  if (!os::commit_memory((char*)_bitmap_region.start(), _bitmap_region.byte_size(), false)) {
    log_warning(gc)("Could not commit native memory for marking bitmap, GC failed");
    return;
  }

  // We do not need parsable heap for this algorithm to work, but we want
  // threads to give up their TLABs.
  ensure_parsability(true);

  // Tell various parts of runtime we are doing GC.
  CodeCache::gc_prologue();
  BiasedLocking::preserve_marks();

  // Derived pointers would be re-discovered during the mark.
  // Clear and activate the table for them.
  DerivedPointerTable::clear();
}

{
  GCTraceTime(Info, gc) time("Step 1: Mark", NULL);

  // Marking stack and the closure that does most of the work. The closure
  // would scan the outgoing references, mark them, and push newly-marked
  // objects to stack for further processing.
  EpsilonMarkStack stack;
  EpsilonScanOopClosure cl(&stack, &_bitmap);

  // Seed the marking with roots.
  process_roots(&cl);
  stat_reachable_roots = stack.size();

  // Scan the rest of the heap until we run out of objects. Termination is
  // guaranteed, because all reachable objects would be marked eventually.
  while (!stack.is_empty()) {
    oop obj = stack.pop();
    obj->oop_iterate(&cl);
    stat_reachable_heap++;
  }

  // No more derived pointers discovered after marking is done.
  DerivedPointerTable::set_active(false);
}

class EpsilonScanOopClosure : public BasicOopIterateClosure {
private:
  EpsilonMarkStack* const _stack;
  MarkBitMap* const _bitmap;

  template <class T>
  void do_oop_work(T* p) {
    // p is the pointer to memory location where oop is, load the value
    // from it, unpack the compressed reference, if needed:
    T o = RawAccess<>::oop_load(p);
    if (!CompressedOops::is_null(o)) {
      oop obj = CompressedOops::decode_not_null(o);

      // Object is discovered. See if it is marked already. If not,
      // mark and push it on mark stack for further traversal. Non-atomic
      // check and set would do, as this closure is called by single thread.
      if (!_bitmap->is_marked(obj)) {
        _bitmap->mark(obj);
        _stack->push(obj);
      }
    }
  }
};

// Walk the marking bitmap and call object closure on every marked object.
// This is much faster that walking a (very sparse) parsable heap, but it
// takes up to 1/64-th of heap size for the bitmap.
void EpsilonHeap::walk_bitmap(ObjectClosure* cl) {
   HeapWord* limit = _space->top();
   HeapWord* addr = _bitmap.get_next_marked_addr(_space->bottom(), limit);
   while (addr < limit) {
     oop obj = oop(addr);
     assert(_bitmap.is_marked(obj), "sanity");
     cl->do_object(obj);
     addr += 1;
     if (addr < limit) {
       addr = _bitmap.get_next_marked_addr(addr, limit);
     }
   }
}

// We are going to store forwarding information (where the new copy resides)
// in mark words. Some of those mark words need to be carefully preserved.
// This is an utility that maintains the list of those special mark words.
PreservedMarks preserved_marks;

// New top of the allocated space.
HeapWord* new_top;

{
  GCTraceTime(Info, gc) time("Step 2: Calculate new locations", NULL);

  // Walk all alive objects, compute their new addresses and store those
  // addresses in mark words. Optionally preserve some marks.
  EpsilonCalcNewLocationObjectClosure cl(_space->bottom(), &preserved_marks);
  walk_bitmap(&cl);

  // After addresses are calculated, we know the new top for the allocated
  // space. We cannot set it just yet, because some asserts check that objects
  // are "in heap" based on current "top".
  new_top = cl.compact_point();

  stat_preserved_marks = preserved_marks.size();
}

class EpsilonCalcNewLocationObjectClosure : public ObjectClosure {
private:
  HeapWord* _compact_point;
  PreservedMarks* const _preserved_marks;

public:
  EpsilonCalcNewLocationObjectClosure(HeapWord* start, PreservedMarks* pm) :
                                      _compact_point(start),
                                      _preserved_marks(pm) {}

  void do_object(oop obj) {
    // Record the new location of the object: it is current compaction point.
    // If object stays at the same location (which is true for objects in
    // dense prefix, that we would normally get), do not bother recording the
    // move, letting downstream code ignore it.
    if ((HeapWord*)obj != _compact_point) {
      markOop mark = obj->mark_raw();
      if (mark->must_be_preserved(obj)) {
        _preserved_marks->push(obj, mark);
      }
      obj->forward_to(oop(_compact_point));
    }
    _compact_point += obj->size();
  }

  HeapWord* compact_point() {
    return _compact_point;
  }
};

{
  GCTraceTime(Info, gc) time("Step 3: Adjust pointers", NULL);

  // Walk all alive objects _and their reference fields_, and put "new
  // addresses" there. We know the new addresses from the forwarding data
  // in mark words. Take care of the heap objects first.
  EpsilonAdjustPointersObjectClosure cl;
  walk_bitmap(&cl);

  // Now do the same, but for all VM roots, which reference the objects on
  // their own: their references should also be updated.
  EpsilonAdjustPointersOopClosure cli;
  process_roots(&cli);

  // Finally, make sure preserved marks know the objects are about to move.
  preserved_marks.adjust_during_full_gc();
}

class EpsilonAdjustPointersOopClosure : public BasicOopIterateClosure {
private:
  template <class T>
  void do_oop_work(T* p) {
    // p is the pointer to memory location where oop is, load the value
    // from it, unpack the compressed reference, if needed:
    T o = RawAccess<>::oop_load(p);
    if (!CompressedOops::is_null(o)) {
      oop obj = CompressedOops::decode_not_null(o);

      // Rewrite the current pointer to the object with its forwardee.
      // Skip the write if update is not needed.
      if (obj->is_forwarded()) {
        oop fwd = obj->forwardee();
        assert(fwd != NULL, "just checking");
        RawAccess<>::oop_store(p, fwd);
      }
    }
  }
};

class EpsilonAdjustPointersObjectClosure : public ObjectClosure {
private:
  EpsilonAdjustPointersOopClosure _cl;
public:
  void do_object(oop obj) {
    // Apply the updates to all references reachable from current object:
    obj->oop_iterate(&_cl);
  }
};

{
  GCTraceTime(Info, gc) time("Step 4: Move objects", NULL);

  // Move all alive objects to their new locations. All the references are
  // already adjusted at previous step.
  EpsilonMoveObjectsObjectClosure cl;
  walk_bitmap(&cl);
  stat_moved = cl.moved();

  // Now we moved all objects to their relevant locations, we can retract
  // the "top" of the allocation space to the end of the compacted prefix.
  _space->set_top(new_top);
}

class EpsilonMoveObjectsObjectClosure : public ObjectClosure {
public:
  void do_object(oop obj) {
    // Copy the object to its new location, if needed. This is final step,
    // so we have to re-initialize its new mark word, dropping the forwardee
    // data from it.
    if (obj->is_forwarded()) {
      oop fwd = obj->forwardee();
      assert(fwd != NULL, "just checking");
      Copy::aligned_conjoint_words((HeapWord*)obj, (HeapWord*)fwd, obj->size());
      fwd->init_mark_raw();
    }
  }
};

{
  GCTraceTime(Info, gc) time("Step 5: Epilogue", NULL);

  // Restore all special mark words.
  preserved_marks.restore();

  // Tell the rest of runtime we have finished the GC.
  DerivedPointerTable::update_pointers();
  BiasedLocking::restore_marks();
  CodeCache::gc_epilogue();
  JvmtiExport::gc_epilogue();

  // Marking bitmap is not needed anymore
  if (!os::uncommit_memory((char*)_bitmap_region.start(), _bitmap_region.byte_size())) {
    log_warning(gc)("Could not uncommit native memory for marking bitmap");
  }

  // Return all memory back if so requested. On large heaps, this would
  // take a while.
  if (EpsilonUncommit) {
    _virtual_space.shrink_by((_space->end() - new_top) * HeapWordSize);
    _space->set_end((HeapWord*)_virtual_space.high());
  }
}

void EpsilonHeap::do_roots(OopClosure* cl) {
  // Need to tell runtime we are about to walk the roots with 1 thread
  StrongRootsScope scope(1);

  // Need to adapt oop closure for some special root types.
  CLDToOopClosure clds(cl, ClassLoaderData::_claim_none);
  MarkingCodeBlobClosure blobs(cl, CodeBlobToOopClosure::FixRelocations);

  // Walk all these different parts of runtime roots. Some roots require
  // holding the lock when walking them.
  {
    MutexLockerEx lock(CodeCache_lock, Mutex::_no_safepoint_check_flag);
    CodeCache::blobs_do(&blobs);
  }

  ClassLoaderDataGraph::cld_do(&clds);
  Universe::oops_do(cl);
  Management::oops_do(cl);
  JvmtiExport::oops_do(cl);
  JNIHandles::oops_do(cl);
  WeakProcessor::oops_do(cl);
  ObjectSynchronizer::oops_do(cl);
  SystemDictionary::oops_do(cl);
  Threads::possibly_parallel_oops_do(false, cl, &blobs);
}

// VM operation that executes collection cycle under safepoint
class VM_EpsilonCollect: public VM_Operation {
private:
  const GCCause::Cause _cause;
  EpsilonHeap* const _heap;
  static size_t _req_id;
public:
  VM_EpsilonCollect(GCCause::Cause cause) : VM_Operation(),
                                            _cause(cause),
                                            _heap(EpsilonHeap::heap()) {};

  VM_Operation::VMOp_Type type() const { return VMOp_EpsilonCollect; }
  const char* name()             const { return "Epsilon Collection"; }

  virtual bool doit_prologue() {
    size_t id = Atomic::load_acquire(&_req_id);

    // Need to take the Heap lock before managing backing storage.
    Heap_lock->lock();

    // Heap lock also naturally serializes GC requests, and allows us to coalesce
    // back-to-back GC requests from many threads. Avoid the consecutive GCs
    // if we started waiting when other GC request was being handled.
    if (id < Atomic::load_acquire(&_req_id)) {
      Heap_lock->unlock();
      return false;
    }

    // No contenders. Start handling a new GC request.
    Atomic::inc(&_req_id);
    return true;
  }

  virtual void doit() {
    _heap->entry_collect(_cause);
  }

  virtual void doit_epilogue() {
    Heap_lock->unlock();
  }
};

size_t VM_EpsilonCollect::_req_id = 0;

void EpsilonHeap::vmentry_collect(GCCause::Cause cause) {
  VM_EpsilonCollect vmop(cause);
  VMThread::execute(&vmop);
}

HeapWord* EpsilonHeap::allocate_or_collect_work(size_t size) {
  HeapWord* res = allocate_work(size);
  if (res == NULL && EpsilonSlidingGC) {
    vmentry_collect(GCCause::_allocation_failure);
    res = allocate_work(size);
  }
  return res;
}