/*

 * Copyright (c) 2013, 2019, Red Hat, Inc. All rights reserved.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#include "precompiled.hpp"

#include "memory/allocation.hpp"

#include "gc/shared/gcTimer.hpp"

#include "gc/shared/gcTraceTime.inline.hpp"

#include "gc/shared/memAllocator.hpp"

#include "gc/shared/parallelCleaning.hpp"

#include "gc/shared/plab.hpp"

#include "gc/shenandoah/shenandoahAllocTracker.hpp"

#include "gc/shenandoah/shenandoahBarrierSet.hpp"

#include "gc/shenandoah/shenandoahBrooksPointer.hpp"

#include "gc/shenandoah/shenandoahCollectionSet.hpp"

#include "gc/shenandoah/shenandoahCollectorPolicy.hpp"

#include "gc/shenandoah/shenandoahConcurrentMark.inline.hpp"

#include "gc/shenandoah/shenandoahControlThread.hpp"

#include "gc/shenandoah/shenandoahFreeSet.hpp"

#include "gc/shenandoah/shenandoahPhaseTimings.hpp"

#include "gc/shenandoah/shenandoahHeap.inline.hpp"

#include "gc/shenandoah/shenandoahHeapRegion.hpp"

#include "gc/shenandoah/shenandoahHeapRegionSet.hpp"

#include "gc/shenandoah/shenandoahMarkCompact.hpp"

#include "gc/shenandoah/shenandoahMarkingContext.inline.hpp"

#include "gc/shenandoah/shenandoahMemoryPool.hpp"

#include "gc/shenandoah/shenandoahMetrics.hpp"

#include "gc/shenandoah/shenandoahMonitoringSupport.hpp"

#include "gc/shenandoah/shenandoahOopClosures.inline.hpp"

#include "gc/shenandoah/shenandoahPacer.inline.hpp"

#include "gc/shenandoah/shenandoahRootProcessor.hpp"

#include "gc/shenandoah/shenandoahStringDedup.hpp"

#include "gc/shenandoah/shenandoahUtils.hpp"

#include "gc/shenandoah/shenandoahVerifier.hpp"

#include "gc/shenandoah/shenandoahCodeRoots.hpp"

#include "gc/shenandoah/shenandoahVMOperations.hpp"

#include "gc/shenandoah/shenandoahWorkGroup.hpp"

#include "gc/shenandoah/shenandoahWorkerPolicy.hpp"

#include "gc/shenandoah/heuristics/shenandoahAdaptiveHeuristics.hpp"

#include "gc/shenandoah/heuristics/shenandoahAggressiveHeuristics.hpp"

#include "gc/shenandoah/heuristics/shenandoahCompactHeuristics.hpp"

#include "gc/shenandoah/heuristics/shenandoahPassiveHeuristics.hpp"

#include "gc/shenandoah/heuristics/shenandoahStaticHeuristics.hpp"

#include "gc/shenandoah/heuristics/shenandoahTraversalHeuristics.hpp"

#include "memory/metaspace.hpp"

#include "runtime/interfaceSupport.inline.hpp"

#include "runtime/safepointMechanism.hpp"

#include "runtime/vmThread.hpp"

#include "services/mallocTracker.hpp"

ShenandoahUpdateRefsClosure::ShenandoahUpdateRefsClosure() : _heap(ShenandoahHeap::heap()) {}

#ifdef ASSERT

template <class T>

void ShenandoahAssertToSpaceClosure::do_oop_work(T* p) {

  T o = RawAccess<>::oop_load(p);

  if (! CompressedOops::is_null(o)) {

    oop obj = CompressedOops::decode_not_null(o);

    shenandoah_assert_not_forwarded(p, obj);

  }

}

void ShenandoahAssertToSpaceClosure::do_oop(narrowOop* p) { do_oop_work(p); }

void ShenandoahAssertToSpaceClosure::do_oop(oop* p)       { do_oop_work(p); }

#endif

class ShenandoahPretouchHeapTask : public AbstractGangTask {

private:

  ShenandoahRegionIterator _regions;

  const size_t _page_size;

public:

  ShenandoahPretouchHeapTask(size_t page_size) :

    AbstractGangTask("Shenandoah Pretouch Heap"),

    _page_size(page_size) {}

  virtual void work(uint worker_id) {

    ShenandoahHeapRegion* r = _regions.next();

    while (r != NULL) {

      os::pretouch_memory(r->bottom(), r->end(), _page_size);

      r = _regions.next();

    }

  }

};

class ShenandoahPretouchBitmapTask : public AbstractGangTask {

private:

  ShenandoahRegionIterator _regions;

  char* _bitmap_base;

  const size_t _bitmap_size;

  const size_t _page_size;

public:

  ShenandoahPretouchBitmapTask(char* bitmap_base, size_t bitmap_size, size_t page_size) :

    AbstractGangTask("Shenandoah Pretouch Bitmap"),

    _bitmap_base(bitmap_base),

    _bitmap_size(bitmap_size),

    _page_size(page_size) {}

  virtual void work(uint worker_id) {

    ShenandoahHeapRegion* r = _regions.next();

    while (r != NULL) {

      size_t start = r->region_number()       * ShenandoahHeapRegion::region_size_bytes() / MarkBitMap::heap_map_factor();

      size_t end   = (r->region_number() + 1) * ShenandoahHeapRegion::region_size_bytes() / MarkBitMap::heap_map_factor();

      assert (end <= _bitmap_size, "end is sane: " SIZE_FORMAT " < " SIZE_FORMAT, end, _bitmap_size);

      os::pretouch_memory(_bitmap_base + start, _bitmap_base + end, _page_size);

      r = _regions.next();

    }

  }

};

jint ShenandoahHeap::initialize() {

  ShenandoahBrooksPointer::initial_checks();

  initialize_heuristics();

  //

  // Figure out heap sizing

  //

  size_t init_byte_size = collector_policy()->initial_heap_byte_size();

  size_t max_byte_size  = collector_policy()->max_heap_byte_size();

  size_t heap_alignment = collector_policy()->heap_alignment();

  size_t reg_size_bytes = ShenandoahHeapRegion::region_size_bytes();

  if (ShenandoahAlwaysPreTouch) {

    // Enabled pre-touch means the entire heap is committed right away.

    init_byte_size = max_byte_size;

  }

  Universe::check_alignment(max_byte_size,  reg_size_bytes, "Shenandoah heap");

  Universe::check_alignment(init_byte_size, reg_size_bytes, "Shenandoah heap");

  _num_regions = ShenandoahHeapRegion::region_count();

  size_t num_committed_regions = init_byte_size / reg_size_bytes;

  num_committed_regions = MIN2(num_committed_regions, _num_regions);

  assert(num_committed_regions <= _num_regions, "sanity");

  _initial_size = num_committed_regions * reg_size_bytes;

  _committed = _initial_size;

  size_t heap_page_size   = UseLargePages ? (size_t)os::large_page_size() : (size_t)os::vm_page_size();

  size_t bitmap_page_size = UseLargePages ? (size_t)os::large_page_size() : (size_t)os::vm_page_size();

  //

  // Reserve and commit memory for heap

  //

  ReservedSpace heap_rs = Universe::reserve_heap(max_byte_size, heap_alignment);

  initialize_reserved_region((HeapWord*)heap_rs.base(), (HeapWord*) (heap_rs.base() + heap_rs.size()));

  _heap_region = MemRegion((HeapWord*)heap_rs.base(), heap_rs.size() / HeapWordSize);

  _heap_region_special = heap_rs.special();

  assert((((size_t) base()) & ShenandoahHeapRegion::region_size_bytes_mask()) == 0,

         "Misaligned heap: " PTR_FORMAT, p2i(base()));

  ReservedSpace sh_rs = heap_rs.first_part(max_byte_size);

  if (!_heap_region_special) {

    os::commit_memory_or_exit(sh_rs.base(), _initial_size, heap_alignment, false,

                              "Cannot commit heap memory");

  }

  //

  // Reserve and commit memory for bitmap(s)

  //

  _bitmap_size = MarkBitMap::compute_size(heap_rs.size());

  _bitmap_size = align_up(_bitmap_size, bitmap_page_size);

  size_t bitmap_bytes_per_region = reg_size_bytes / MarkBitMap::heap_map_factor();

  guarantee(bitmap_bytes_per_region != 0,

            "Bitmap bytes per region should not be zero");

  guarantee(is_power_of_2(bitmap_bytes_per_region),

            "Bitmap bytes per region should be power of two: " SIZE_FORMAT, bitmap_bytes_per_region);

  if (bitmap_page_size > bitmap_bytes_per_region) {

    _bitmap_regions_per_slice = bitmap_page_size / bitmap_bytes_per_region;

    _bitmap_bytes_per_slice = bitmap_page_size;

  } else {

    _bitmap_regions_per_slice = 1;

    _bitmap_bytes_per_slice = bitmap_bytes_per_region;

  }

  guarantee(_bitmap_regions_per_slice >= 1,

            "Should have at least one region per slice: " SIZE_FORMAT,

            _bitmap_regions_per_slice);

  guarantee(((_bitmap_bytes_per_slice) % bitmap_page_size) == 0,

            "Bitmap slices should be page-granular: bps = " SIZE_FORMAT ", page size = " SIZE_FORMAT,

            _bitmap_bytes_per_slice, bitmap_page_size);

  ReservedSpace bitmap(_bitmap_size, bitmap_page_size);

  MemTracker::record_virtual_memory_type(bitmap.base(), mtGC);

  _bitmap_region = MemRegion((HeapWord*) bitmap.base(), bitmap.size() / HeapWordSize);

  _bitmap_region_special = bitmap.special();

  size_t bitmap_init_commit = _bitmap_bytes_per_slice *

                              align_up(num_committed_regions, _bitmap_regions_per_slice) / _bitmap_regions_per_slice;

  bitmap_init_commit = MIN2(_bitmap_size, bitmap_init_commit);

  if (!_bitmap_region_special) {

    os::commit_memory_or_exit((char *) _bitmap_region.start(), bitmap_init_commit, bitmap_page_size, false,

                              "Cannot commit bitmap memory");

  }

  _marking_context = new ShenandoahMarkingContext(_heap_region, _bitmap_region, _num_regions);

  if (ShenandoahVerify) {

    ReservedSpace verify_bitmap(_bitmap_size, bitmap_page_size);

    if (!verify_bitmap.special()) {

      os::commit_memory_or_exit(verify_bitmap.base(), verify_bitmap.size(), bitmap_page_size, false,

                                "Cannot commit verification bitmap memory");

    }

    MemTracker::record_virtual_memory_type(verify_bitmap.base(), mtGC);

    MemRegion verify_bitmap_region = MemRegion((HeapWord *) verify_bitmap.base(), verify_bitmap.size() / HeapWordSize);

    _verification_bit_map.initialize(_heap_region, verify_bitmap_region);

    _verifier = new ShenandoahVerifier(this, &_verification_bit_map);

  }

  // Reserve aux bitmap for use in object_iterate(). We don't commit it here.

  ReservedSpace aux_bitmap(_bitmap_size, bitmap_page_size);

  MemTracker::record_virtual_memory_type(aux_bitmap.base(), mtGC);

  _aux_bitmap_region = MemRegion((HeapWord*) aux_bitmap.base(), aux_bitmap.size() / HeapWordSize);

  _aux_bitmap_region_special = aux_bitmap.special();

  _aux_bit_map.initialize(_heap_region, _aux_bitmap_region);

  //

  // Create regions and region sets

  //

  _regions = NEW_C_HEAP_ARRAY(ShenandoahHeapRegion*, _num_regions, mtGC);

  _free_set = new ShenandoahFreeSet(this, _num_regions);

  _collection_set = new ShenandoahCollectionSet(this, (HeapWord*)sh_rs.base());

  {

    ShenandoahHeapLocker locker(lock());

    size_t size_words = ShenandoahHeapRegion::region_size_words();

    for (size_t i = 0; i < _num_regions; i++) {

      HeapWord* start = (HeapWord*)sh_rs.base() + size_words * i;

      bool is_committed = i < num_committed_regions;

      ShenandoahHeapRegion* r = new ShenandoahHeapRegion(this, start, size_words, i, is_committed);

      _marking_context->initialize_top_at_mark_start(r);

      _regions[i] = r;

      assert(!collection_set()->is_in(i), "New region should not be in collection set");

    }

    // Initialize to complete

    _marking_context->mark_complete();

    _free_set->rebuild();

  }

  if (ShenandoahAlwaysPreTouch) {

    assert(!AlwaysPreTouch, "Should have been overridden");

    // For NUMA, it is important to pre-touch the storage under bitmaps with worker threads,

    // before initialize() below zeroes it with initializing thread. For any given region,

    // we touch the region and the corresponding bitmaps from the same thread.

    ShenandoahPushWorkerScope scope(workers(), _max_workers, false);

    size_t pretouch_heap_page_size = heap_page_size;

    size_t pretouch_bitmap_page_size = bitmap_page_size;

#ifdef LINUX

    // UseTransparentHugePages would madvise that backing memory can be coalesced into huge

    // pages. But, the kernel needs to know that every small page is used, in order to coalesce

    // them into huge one. Therefore, we need to pretouch with smaller pages.

    if (UseTransparentHugePages) {

      pretouch_heap_page_size = (size_t)os::vm_page_size();

      pretouch_bitmap_page_size = (size_t)os::vm_page_size();

    }

#endif

    // OS memory managers may want to coalesce back-to-back pages. Make their jobs

    // simpler by pre-touching continuous spaces (heap and bitmap) separately.

    log_info(gc, init)("Pretouch bitmap: " SIZE_FORMAT " regions, " SIZE_FORMAT " bytes page",

                       _num_regions, pretouch_bitmap_page_size);

    ShenandoahPretouchBitmapTask bcl(bitmap.base(), _bitmap_size, pretouch_bitmap_page_size);

    _workers->run_task(&bcl);

    log_info(gc, init)("Pretouch heap: " SIZE_FORMAT " regions, " SIZE_FORMAT " bytes page",

                       _num_regions, pretouch_heap_page_size);

    ShenandoahPretouchHeapTask hcl(pretouch_heap_page_size);

    _workers->run_task(&hcl);

  }

  //

  // Initialize the rest of GC subsystems

  //

  _liveness_cache = NEW_C_HEAP_ARRAY(jushort*, _max_workers, mtGC);

  for (uint worker = 0; worker < _max_workers; worker++) {

    _liveness_cache[worker] = NEW_C_HEAP_ARRAY(jushort, _num_regions, mtGC);

    Copy::fill_to_bytes(_liveness_cache[worker], _num_regions * sizeof(jushort));

  }

  // The call below uses stuff (the SATB* things) that are in G1, but probably

  // belong into a shared location.

  ShenandoahBarrierSet::satb_mark_queue_set().initialize(this,

                                                         SATB_Q_CBL_mon,

                                                         20 /* G1SATBProcessCompletedThreshold */,

                                                         60 /* G1SATBBufferEnqueueingThresholdPercent */);

  _monitoring_support = new ShenandoahMonitoringSupport(this);

  _phase_timings = new ShenandoahPhaseTimings();

  ShenandoahStringDedup::initialize();

  ShenandoahCodeRoots::initialize();

  if (ShenandoahAllocationTrace) {

    _alloc_tracker = new ShenandoahAllocTracker();

  }

  if (ShenandoahPacing) {

    _pacer = new ShenandoahPacer(this);

    _pacer->setup_for_idle();

  } else {

    _pacer = NULL;

  }

  _traversal_gc = heuristics()->can_do_traversal_gc() ?

                  new ShenandoahTraversalGC(this, _num_regions) :

                  NULL;

  _control_thread = new ShenandoahControlThread();

  log_info(gc, init)("Initialize Shenandoah heap with initial size " SIZE_FORMAT "%s",

                     byte_size_in_proper_unit(_initial_size), proper_unit_for_byte_size(_initial_size));

  log_info(gc, init)("Safepointing mechanism: %s",

                     SafepointMechanism::uses_thread_local_poll() ? "thread-local poll" :

                     (SafepointMechanism::uses_global_page_poll() ? "global-page poll" : "unknown"));

  return JNI_OK;

}

void ShenandoahHeap::initialize_heuristics() {

  if (ShenandoahGCHeuristics != NULL) {

    if (strcmp(ShenandoahGCHeuristics, "aggressive") == 0) {

      _heuristics = new ShenandoahAggressiveHeuristics();

    } else if (strcmp(ShenandoahGCHeuristics, "static") == 0) {

      _heuristics = new ShenandoahStaticHeuristics();

    } else if (strcmp(ShenandoahGCHeuristics, "adaptive") == 0) {

      _heuristics = new ShenandoahAdaptiveHeuristics();

    } else if (strcmp(ShenandoahGCHeuristics, "passive") == 0) {

      _heuristics = new ShenandoahPassiveHeuristics();

    } else if (strcmp(ShenandoahGCHeuristics, "compact") == 0) {

      _heuristics = new ShenandoahCompactHeuristics();

    } else if (strcmp(ShenandoahGCHeuristics, "traversal") == 0) {

      _heuristics = new ShenandoahTraversalHeuristics();

    } else {

      vm_exit_during_initialization("Unknown -XX:ShenandoahGCHeuristics option");

    }

    if (_heuristics->is_diagnostic() && !UnlockDiagnosticVMOptions) {

      vm_exit_during_initialization(

              err_msg("Heuristics \"%s\" is diagnostic, and must be enabled via -XX:+UnlockDiagnosticVMOptions.",

                      _heuristics->name()));

    }

    if (_heuristics->is_experimental() && !UnlockExperimentalVMOptions) {

      vm_exit_during_initialization(

              err_msg("Heuristics \"%s\" is experimental, and must be enabled via -XX:+UnlockExperimentalVMOptions.",

                      _heuristics->name()));

    }

    log_info(gc, init)("Shenandoah heuristics: %s",

                       _heuristics->name());

  } else {

      ShouldNotReachHere();

  }

}

#ifdef _MSC_VER

#pragma warning( push )

#pragma warning( disable:4355 ) // 'this' : used in base member initializer list

#endif

ShenandoahHeap::ShenandoahHeap(ShenandoahCollectorPolicy* policy) :

  CollectedHeap(),

  _initial_size(0),

  _used(0),

  _committed(0),

  _bytes_allocated_since_gc_start(0),

  _max_workers(MAX2(ConcGCThreads, ParallelGCThreads)),

  _workers(NULL),

  _safepoint_workers(NULL),

  _heap_region_special(false),

  _num_regions(0),

  _regions(NULL),

  _update_refs_iterator(this),

  _control_thread(NULL),

  _shenandoah_policy(policy),

  _heuristics(NULL),

  _free_set(NULL),

  _scm(new ShenandoahConcurrentMark()),

  _traversal_gc(NULL),

  _full_gc(new ShenandoahMarkCompact()),

  _pacer(NULL),

  _verifier(NULL),

  _alloc_tracker(NULL),

  _phase_timings(NULL),

  _monitoring_support(NULL),

  _memory_pool(NULL),

  _stw_memory_manager("Shenandoah Pauses", "end of GC pause"),

  _cycle_memory_manager("Shenandoah Cycles", "end of GC cycle"),

  _gc_timer(new (ResourceObj::C_HEAP, mtGC) ConcurrentGCTimer()),

  _soft_ref_policy(),

  _log_min_obj_alignment_in_bytes(LogMinObjAlignmentInBytes),

  _ref_processor(NULL),

  _marking_context(NULL),

  _bitmap_size(0),

  _bitmap_regions_per_slice(0),

  _bitmap_bytes_per_slice(0),

  _bitmap_region_special(false),

  _aux_bitmap_region_special(false),

  _liveness_cache(NULL),

  _collection_set(NULL)

{

  log_info(gc, init)("GC threads: " UINT32_FORMAT " parallel, " UINT32_FORMAT " concurrent", ParallelGCThreads, ConcGCThreads);

  log_info(gc, init)("Reference processing: %s", ParallelRefProcEnabled ? "parallel" : "serial");

  BarrierSet::set_barrier_set(new ShenandoahBarrierSet(this));

  _max_workers = MAX2(_max_workers, 1U);

  _workers = new ShenandoahWorkGang("Shenandoah GC Threads", _max_workers,

                            /* are_GC_task_threads */true,

                            /* are_ConcurrentGC_threads */false);

  if (_workers == NULL) {

    vm_exit_during_initialization("Failed necessary allocation.");

  } else {

    _workers->initialize_workers();

  }

  if (ShenandoahParallelSafepointThreads > 1) {

    _safepoint_workers = new ShenandoahWorkGang("Safepoint Cleanup Thread",

                                                ShenandoahParallelSafepointThreads,

                                                false, false);

    _safepoint_workers->initialize_workers();

  }

}

#ifdef _MSC_VER

#pragma warning( pop )

#endif

class ShenandoahResetBitmapTask : public AbstractGangTask {

private:

  ShenandoahRegionIterator _regions;

public:

  ShenandoahResetBitmapTask() :

    AbstractGangTask("Parallel Reset Bitmap Task") {}

  void work(uint worker_id) {

    ShenandoahHeapRegion* region = _regions.next();

    ShenandoahHeap* heap = ShenandoahHeap::heap();

    ShenandoahMarkingContext* const ctx = heap->marking_context();

    while (region != NULL) {

      if (heap->is_bitmap_slice_committed(region)) {

        ctx->clear_bitmap(region);

      }

      region = _regions.next();

    }

  }

};

void ShenandoahHeap::reset_mark_bitmap() {

  assert_gc_workers(_workers->active_workers());

  mark_incomplete_marking_context();

  ShenandoahResetBitmapTask task;

  _workers->run_task(&task);

}

void ShenandoahHeap::print_on(outputStream* st) const {

  st->print_cr("Shenandoah Heap");

  st->print_cr(" " SIZE_FORMAT "K total, " SIZE_FORMAT "K committed, " SIZE_FORMAT "K used",

  st->print_cr(" " SIZE_FORMAT " x " SIZE_FORMAT"K regions",

               num_regions(), ShenandoahHeapRegion::region_size_bytes() / K);

  st->print("Status: ");

  if (has_forwarded_objects())               st->print("has forwarded objects, ");

  if (is_concurrent_mark_in_progress())      st->print("marking, ");

  if (is_evacuation_in_progress())           st->print("evacuating, ");