/*

 * 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/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 ShenandoahPretouchTask : public AbstractGangTask {

private:

  ShenandoahRegionIterator _regions;

  const size_t _bitmap_size;

  const size_t _page_size;

  char* _bitmap_base;

public:

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

    AbstractGangTask("Shenandoah PreTouch"),

    _bitmap_size(bitmap_size),

    _page_size(page_size),

    _bitmap_base(bitmap_base) {

  }

  virtual void work(uint worker_id) {

    ShenandoahHeapRegion* r = _regions.next();

    while (r != NULL) {

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

      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();

  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();

  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,

                            ShenandoahHeapRegion::region_size_bytes(),

                            "shenandoah heap");

  Universe::check_alignment(init_byte_size,

                            ShenandoahHeapRegion::region_size_bytes(),

                            "shenandoah 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()));

  ReservedSpace pgc_rs = heap_rs.first_part(max_byte_size);

  _num_regions = ShenandoahHeapRegion::region_count();

  size_t num_committed_regions = init_byte_size / ShenandoahHeapRegion::region_size_bytes();

  num_committed_regions = MIN2(num_committed_regions, _num_regions);

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

  _initial_size = num_committed_regions * ShenandoahHeapRegion::region_size_bytes();

  _committed = _initial_size;

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

          byte_size_in_proper_unit(_initial_size), proper_unit_for_byte_size(_initial_size));

  if (!os::commit_memory(pgc_rs.base(), _initial_size, false)) {

    vm_exit_out_of_memory(_initial_size, OOM_MMAP_ERROR, "Shenandoah failed to initialize heap");

  }

  size_t reg_size_words = ShenandoahHeapRegion::region_size_words();

  size_t reg_size_bytes = ShenandoahHeapRegion::region_size_bytes();

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

  _free_set = new ShenandoahFreeSet(this, _num_regions);

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

  if (ShenandoahPacing) {

    _pacer = new ShenandoahPacer(this);

    _pacer->setup_for_idle();

  } else {

    _pacer = NULL;

  }

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

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

  // 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 */,

                                               Shared_SATB_Q_lock);

  // Reserve space for prev and next bitmap.

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

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

  _bitmap_size = align_up(_bitmap_size, bitmap_page_size);

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

  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 bitmap0(_bitmap_size, bitmap_page_size);

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

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

  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);

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

                            "couldn't allocate initial bitmap");

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

  if (ShenandoahVerify) {

    ReservedSpace verify_bitmap(_bitmap_size, page_size);

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

                              "couldn't allocate verification bitmap");

    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);

  }

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

  {

    ShenandoahHeapLocker locker(lock());

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

      ShenandoahHeapRegion* r = new ShenandoahHeapRegion(this,

                                                         (HeapWord*) pgc_rs.base() + reg_size_words * i,

                                                         reg_size_words,

                                                         i,

                                                         i < num_committed_regions);

      _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);

    log_info(gc, heap)("Parallel pretouch " SIZE_FORMAT " regions with " SIZE_FORMAT " byte pages",

                       _num_regions, page_size);

    ShenandoahPretouchTask cl(bitmap0.base(), _bitmap_size, page_size);

    _workers->run_task(&cl);

  }

  // 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_bit_map.initialize(_heap_region, _aux_bitmap_region);

  _traversal_gc = heuristics()->can_do_traversal_gc() ?

                new ShenandoahTraversalGC(this, _num_regions) :

                NULL;

  _monitoring_support = new ShenandoahMonitoringSupport(this);

  _phase_timings = new ShenandoahPhaseTimings();

  if (ShenandoahAllocationTrace) {

    _alloc_tracker = new ShenandoahAllocTracker();

  }

  ShenandoahStringDedup::initialize();

  _control_thread = new ShenandoahControlThread();

  ShenandoahCodeRoots::initialize();

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

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

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

  _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));

  }

  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()));

    }

    if (ShenandoahStoreValEnqueueBarrier && ShenandoahStoreValReadBarrier) {

      vm_exit_during_initialization("Cannot use both ShenandoahStoreValEnqueueBarrier and ShenandoahStoreValReadBarrier");

    }

    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),

  _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(),

  _ref_processor(NULL),

  _marking_context(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",

               capacity() / K, committed() / K, used() / K);

  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, ");

  if (is_update_refs_in_progress())          st->print("updating refs, ");

  if (is_concurrent_traversal_in_progress()) st->print("traversal, ");

  if (is_degenerated_gc_in_progress())       st->print("degenerated gc, ");

  if (is_full_gc_in_progress())              st->print("full gc, ");

  if (is_full_gc_move_in_progress())         st->print("full gc move, ");

  if (cancelled_gc()) {

    st->print("cancelled");

  } else {

    st->print("not cancelled");

  }

  st->cr();

  st->print_cr("Reserved region:");

  st->print_cr(" - [" PTR_FORMAT ", " PTR_FORMAT ") ",

               p2i(reserved_region().start()),

               p2i(reserved_region().end()));

  st->cr();

  MetaspaceUtils::print_on(st);

  if (Verbose) {

    print_heap_regions_on(st);

  }

}

class ShenandoahInitGCLABClosure : public ThreadClosure {

public:

  void do_thread(Thread* thread) {

    if (thread != NULL && (thread->is_Java_thread() || thread->is_Worker_thread())) {

      ShenandoahThreadLocalData::initialize_gclab(thread);

    }

  }

};

void ShenandoahHeap::post_initialize() {

  CollectedHeap::post_initialize();

  MutexLocker ml(Threads_lock);

  ShenandoahInitGCLABClosure init_gclabs;

  Threads::threads_do(&init_gclabs);

  _workers->threads_do(&init_gclabs);

  _safepoint_workers->threads_do(&init_gclabs);

  // gclab can not be initialized early during VM startup, as it can not determinate its max_size.

  // Now, we will let WorkGang to initialize gclab when new worker is created.

  _workers->set_initialize_gclab();

  _scm->initialize(_max_workers);

  _full_gc->initialize(_gc_timer);

  ref_processing_init();

  _heuristics->initialize();

}

size_t ShenandoahHeap::used() const {

  return OrderAccess::load_acquire(&_used);

}

size_t ShenandoahHeap::committed() const {

  OrderAccess::acquire();

  return _committed;

}

void ShenandoahHeap::increase_committed(size_t bytes) {

  assert_heaplock_or_safepoint();

  _committed += bytes;

}

void ShenandoahHeap::decrease_committed(size_t bytes) {

  assert_heaplock_or_safepoint();

  _committed -= bytes;