/*

 * Copyright (c) 2001, 2015, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * 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 "classfile/metadataOnStackMark.hpp"

#include "classfile/stringTable.hpp"

#include "classfile/symbolTable.hpp"

#include "code/codeCache.hpp"

#include "code/icBuffer.hpp"

#include "gc/g1/bufferingOopClosure.hpp"

#include "gc/g1/concurrentG1Refine.hpp"

#include "gc/g1/concurrentG1RefineThread.hpp"

#include "gc/g1/concurrentMarkThread.inline.hpp"

#include "gc/g1/g1Allocator.inline.hpp"

#include "gc/g1/g1CollectedHeap.inline.hpp"

#include "gc/g1/g1CollectorPolicy.hpp"

#include "gc/g1/g1CollectorState.hpp"

#include "gc/g1/g1EvacStats.inline.hpp"

#include "gc/g1/g1GCPhaseTimes.hpp"

#include "gc/g1/g1MarkSweep.hpp"

#include "gc/g1/g1OopClosures.inline.hpp"

#include "gc/g1/g1ParScanThreadState.inline.hpp"

#include "gc/g1/g1RegionToSpaceMapper.hpp"

#include "gc/g1/g1RemSet.inline.hpp"

#include "gc/g1/g1RootClosures.hpp"

#include "gc/g1/g1RootProcessor.hpp"

#include "gc/g1/g1StringDedup.hpp"

#include "gc/g1/g1YCTypes.hpp"

#include "gc/g1/heapRegion.inline.hpp"

#include "gc/g1/heapRegionRemSet.hpp"

#include "gc/g1/heapRegionSet.inline.hpp"

#include "gc/g1/suspendibleThreadSet.hpp"

#include "gc/g1/vm_operations_g1.hpp"

#include "gc/shared/gcHeapSummary.hpp"

#include "gc/shared/gcId.hpp"

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

#include "gc/shared/gcTimer.hpp"

#include "gc/shared/gcTrace.hpp"

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

#include "gc/shared/generationSpec.hpp"

#include "gc/shared/isGCActiveMark.hpp"

#include "gc/shared/referenceProcessor.hpp"

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

#include "logging/log.hpp"

#include "memory/allocation.hpp"

#include "memory/iterator.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/atomic.inline.hpp"

#include "runtime/init.hpp"

#include "runtime/orderAccess.inline.hpp"

#include "runtime/vmThread.hpp"

#include "utilities/globalDefinitions.hpp"

#include "utilities/stack.inline.hpp"

size_t G1CollectedHeap::_humongous_object_threshold_in_words = 0;

// INVARIANTS/NOTES

//

// All allocation activity covered by the G1CollectedHeap interface is

// serialized by acquiring the HeapLock.  This happens in mem_allocate

// and allocate_new_tlab, which are the "entry" points to the

// allocation code from the rest of the JVM.  (Note that this does not

// apply to TLAB allocation, which is not part of this interface: it

// is done by clients of this interface.)

// Local to this file.

class RefineCardTableEntryClosure: public CardTableEntryClosure {

  bool _concurrent;

public:

  RefineCardTableEntryClosure() : _concurrent(true) { }

  bool do_card_ptr(jbyte* card_ptr, uint worker_i) {

    bool oops_into_cset = G1CollectedHeap::heap()->g1_rem_set()->refine_card(card_ptr, worker_i, false);

    // This path is executed by the concurrent refine or mutator threads,

    // concurrently, and so we do not care if card_ptr contains references

    // that point into the collection set.

    assert(!oops_into_cset, "should be");

    if (_concurrent && SuspendibleThreadSet::should_yield()) {

      // Caller will actually yield.

      return false;

    }

    // Otherwise, we finished successfully; return true.

    return true;

  }

  void set_concurrent(bool b) { _concurrent = b; }

};

class RedirtyLoggedCardTableEntryClosure : public CardTableEntryClosure {

 private:

  size_t _num_dirtied;

  G1CollectedHeap* _g1h;

  G1SATBCardTableLoggingModRefBS* _g1_bs;

  HeapRegion* region_for_card(jbyte* card_ptr) const {

    return _g1h->heap_region_containing(_g1_bs->addr_for(card_ptr));

  }

  bool will_become_free(HeapRegion* hr) const {

    // A region will be freed by free_collection_set if the region is in the

    // collection set and has not had an evacuation failure.

    return _g1h->is_in_cset(hr) && !hr->evacuation_failed();

  }

 public:

  RedirtyLoggedCardTableEntryClosure(G1CollectedHeap* g1h) : CardTableEntryClosure(),

    _num_dirtied(0), _g1h(g1h), _g1_bs(g1h->g1_barrier_set()) { }

  bool do_card_ptr(jbyte* card_ptr, uint worker_i) {

    HeapRegion* hr = region_for_card(card_ptr);

    // Should only dirty cards in regions that won't be freed.

    if (!will_become_free(hr)) {

      *card_ptr = CardTableModRefBS::dirty_card_val();

      _num_dirtied++;

    }

    return true;

  }

  size_t num_dirtied()   const { return _num_dirtied; }

};

void G1RegionMappingChangedListener::reset_from_card_cache(uint start_idx, size_t num_regions) {

  HeapRegionRemSet::invalidate_from_card_cache(start_idx, num_regions);

}

void G1RegionMappingChangedListener::on_commit(uint start_idx, size_t num_regions, bool zero_filled) {

  // The from card cache is not the memory that is actually committed. So we cannot

  // take advantage of the zero_filled parameter.

  reset_from_card_cache(start_idx, num_regions);

}

void G1CollectedHeap::push_dirty_cards_region(HeapRegion* hr)

{

  // Claim the right to put the region on the dirty cards region list

  // by installing a self pointer.

  HeapRegion* next = hr->get_next_dirty_cards_region();

  if (next == NULL) {

    HeapRegion* res = (HeapRegion*)

      Atomic::cmpxchg_ptr(hr, hr->next_dirty_cards_region_addr(),

                          NULL);

    if (res == NULL) {

      HeapRegion* head;

      do {

        // Put the region to the dirty cards region list.

        head = _dirty_cards_region_list;

        next = (HeapRegion*)

          Atomic::cmpxchg_ptr(hr, &_dirty_cards_region_list, head);

        if (next == head) {

          assert(hr->get_next_dirty_cards_region() == hr,

                 "hr->get_next_dirty_cards_region() != hr");

          if (next == NULL) {

            // The last region in the list points to itself.

            hr->set_next_dirty_cards_region(hr);

          } else {

            hr->set_next_dirty_cards_region(next);

          }

        }

      } while (next != head);

    }

  }

}

HeapRegion* G1CollectedHeap::pop_dirty_cards_region()

{

  HeapRegion* head;

  HeapRegion* hr;

  do {

    head = _dirty_cards_region_list;

    if (head == NULL) {

      return NULL;

    }

    HeapRegion* new_head = head->get_next_dirty_cards_region();

    if (head == new_head) {

      // The last region.

      new_head = NULL;

    }

    hr = (HeapRegion*)Atomic::cmpxchg_ptr(new_head, &_dirty_cards_region_list,

                                          head);

  } while (hr != head);

  assert(hr != NULL, "invariant");

  hr->set_next_dirty_cards_region(NULL);

  return hr;

}

// Returns true if the reference points to an object that

// can move in an incremental collection.

bool G1CollectedHeap::is_scavengable(const void* p) {

  HeapRegion* hr = heap_region_containing(p);

  return !hr->is_pinned();

}

// Private methods.

HeapRegion*

G1CollectedHeap::new_region_try_secondary_free_list(bool is_old) {

  MutexLockerEx x(SecondaryFreeList_lock, Mutex::_no_safepoint_check_flag);

  while (!_secondary_free_list.is_empty() || free_regions_coming()) {

    if (!_secondary_free_list.is_empty()) {

      log_develop_trace(gc, freelist)("G1ConcRegionFreeing [region alloc] : "

                                      "secondary_free_list has %u entries",

                                      _secondary_free_list.length());

      // It looks as if there are free regions available on the

      // secondary_free_list. Let's move them to the free_list and try

      // again to allocate from it.

      append_secondary_free_list();

      assert(_hrm.num_free_regions() > 0, "if the secondary_free_list was not "

             "empty we should have moved at least one entry to the free_list");

      HeapRegion* res = _hrm.allocate_free_region(is_old);

      log_develop_trace(gc, freelist)("G1ConcRegionFreeing [region alloc] : "

                                      "allocated " HR_FORMAT " from secondary_free_list",

                                      HR_FORMAT_PARAMS(res));

      return res;

    }

    // Wait here until we get notified either when (a) there are no

    // more free regions coming or (b) some regions have been moved on

    // the secondary_free_list.

    SecondaryFreeList_lock->wait(Mutex::_no_safepoint_check_flag);

  }

  log_develop_trace(gc, freelist)("G1ConcRegionFreeing [region alloc] : "

                                  "could not allocate from secondary_free_list");

  return NULL;

}

HeapRegion* G1CollectedHeap::new_region(size_t word_size, bool is_old, bool do_expand) {

  assert(!is_humongous(word_size) || word_size <= HeapRegion::GrainWords,

         "the only time we use this to allocate a humongous region is "

         "when we are allocating a single humongous region");

  HeapRegion* res;

  if (G1StressConcRegionFreeing) {

    if (!_secondary_free_list.is_empty()) {

      log_develop_trace(gc, freelist)("G1ConcRegionFreeing [region alloc] : "

                                      "forced to look at the secondary_free_list");

      res = new_region_try_secondary_free_list(is_old);

      if (res != NULL) {

        return res;

      }

    }

  }

  res = _hrm.allocate_free_region(is_old);

  if (res == NULL) {

    log_develop_trace(gc, freelist)("G1ConcRegionFreeing [region alloc] : "

                                    "res == NULL, trying the secondary_free_list");

    res = new_region_try_secondary_free_list(is_old);

  }

  if (res == NULL && do_expand && _expand_heap_after_alloc_failure) {

    // Currently, only attempts to allocate GC alloc regions set

    // do_expand to true. So, we should only reach here during a

    // safepoint. If this assumption changes we might have to

    // reconsider the use of _expand_heap_after_alloc_failure.

    assert(SafepointSynchronize::is_at_safepoint(), "invariant");

    log_debug(gc, ergo, heap)("Attempt heap expansion (region allocation request failed). Allocation request: " SIZE_FORMAT "B",

                              word_size * HeapWordSize);

    if (expand(word_size * HeapWordSize)) {

      // Given that expand() succeeded in expanding the heap, and we

      // always expand the heap by an amount aligned to the heap

      // region size, the free list should in theory not be empty.

      // In either case allocate_free_region() will check for NULL.

      res = _hrm.allocate_free_region(is_old);

    } else {

      _expand_heap_after_alloc_failure = false;

    }

  }

  return res;

}

HeapWord*

G1CollectedHeap::humongous_obj_allocate_initialize_regions(uint first,

                                                           uint num_regions,

                                                           size_t word_size,

                                                           AllocationContext_t context) {

  assert(first != G1_NO_HRM_INDEX, "pre-condition");

  assert(is_humongous(word_size), "word_size should be humongous");

  assert(num_regions * HeapRegion::GrainWords >= word_size, "pre-condition");

  // Index of last region in the series.

  uint last = first + num_regions - 1;

  // We need to initialize the region(s) we just discovered. This is

  // a bit tricky given that it can happen concurrently with

  // refinement threads refining cards on these regions and

  // potentially wanting to refine the BOT as they are scanning

  // those cards (this can happen shortly after a cleanup; see CR

  // 6991377). So we have to set up the region(s) carefully and in

  // a specific order.

  // The word size sum of all the regions we will allocate.

  size_t word_size_sum = (size_t) num_regions * HeapRegion::GrainWords;

  assert(word_size <= word_size_sum, "sanity");

  // This will be the "starts humongous" region.

  HeapRegion* first_hr = region_at(first);

  // The header of the new object will be placed at the bottom of

  // the first region.

  HeapWord* new_obj = first_hr->bottom();

  // This will be the new top of the new object.

  HeapWord* obj_top = new_obj + word_size;

  // First, we need to zero the header of the space that we will be

  // allocating. When we update top further down, some refinement

  // threads might try to scan the region. By zeroing the header we

  // ensure that any thread that will try to scan the region will

  // come across the zero klass word and bail out.

  //

  // NOTE: It would not have been correct to have used

  // CollectedHeap::fill_with_object() and make the space look like

  // an int array. The thread that is doing the allocation will

  // later update the object header to a potentially different array

  // type and, for a very short period of time, the klass and length

  // fields will be inconsistent. This could cause a refinement

  // thread to calculate the object size incorrectly.

  Copy::fill_to_words(new_obj, oopDesc::header_size(), 0);

  // How many words we use for filler objects.

  size_t word_fill_size = word_size_sum - word_size;

  // How many words memory we "waste" which cannot hold a filler object.

  size_t words_not_fillable = 0;

  if (word_fill_size >= min_fill_size()) {

    fill_with_objects(obj_top, word_fill_size);

  } else if (word_fill_size > 0) {

    // We have space to fill, but we cannot fit an object there.

    words_not_fillable = word_fill_size;

    word_fill_size = 0;

  }

  // We will set up the first region as "starts humongous". This

  // will also update the BOT covering all the regions to reflect

  // that there is a single object that starts at the bottom of the

  // first region.

  first_hr->set_starts_humongous(obj_top, word_fill_size);

  first_hr->set_allocation_context(context);

  // Then, if there are any, we will set up the "continues

  // humongous" regions.

  HeapRegion* hr = NULL;

  for (uint i = first + 1; i <= last; ++i) {

    hr = region_at(i);

    hr->set_continues_humongous(first_hr);

    hr->set_allocation_context(context);

  }

  // Up to this point no concurrent thread would have been able to

  // do any scanning on any region in this series. All the top

  // fields still point to bottom, so the intersection between

  // [bottom,top] and [card_start,card_end] will be empty. Before we

  // update the top fields, we'll do a storestore to make sure that

  // no thread sees the update to top before the zeroing of the

  // object header and the BOT initialization.

  OrderAccess::storestore();

  // Now, we will update the top fields of the "continues humongous"

  // regions except the last one.

  for (uint i = first; i < last; ++i) {

    hr = region_at(i);

    hr->set_top(hr->end());

  }

  hr = region_at(last);

  // If we cannot fit a filler object, we must set top to the end

  // of the humongous object, otherwise we cannot iterate the heap

  // and the BOT will not be complete.

  hr->set_top(hr->end() - words_not_fillable);

  assert(hr->bottom() < obj_top && obj_top <= hr->end(),

         "obj_top should be in last region");

  check_bitmaps("Humongous Region Allocation", first_hr);

  assert(words_not_fillable == 0 ||

         first_hr->bottom() + word_size_sum - words_not_fillable == hr->top(),

         "Miscalculation in humongous allocation");

  increase_used((word_size_sum - words_not_fillable) * HeapWordSize);

  for (uint i = first; i <= last; ++i) {

    hr = region_at(i);

    _humongous_set.add(hr);

    _hr_printer.alloc(hr);

  }

  return new_obj;

}

size_t G1CollectedHeap::humongous_obj_size_in_regions(size_t word_size) {

  assert(is_humongous(word_size), "Object of size " SIZE_FORMAT " must be humongous here", word_size);

  return align_size_up_(word_size, HeapRegion::GrainWords) / HeapRegion::GrainWords;

}

// If could fit into free regions w/o expansion, try.

// Otherwise, if can expand, do so.

// Otherwise, if using ex regions might help, try with ex given back.

HeapWord* G1CollectedHeap::humongous_obj_allocate(size_t word_size, AllocationContext_t context) {

  assert_heap_locked_or_at_safepoint(true /* should_be_vm_thread */);

  verify_region_sets_optional();

  uint first = G1_NO_HRM_INDEX;

  uint obj_regions = (uint) humongous_obj_size_in_regions(word_size);

  if (obj_regions == 1) {

    // Only one region to allocate, try to use a fast path by directly allocating

    // from the free lists. Do not try to expand here, we will potentially do that

    // later.

    HeapRegion* hr = new_region(word_size, true /* is_old */, false /* do_expand */);

    if (hr != NULL) {

      first = hr->hrm_index();

    }

  } else {

    // We can't allocate humongous regions spanning more than one region while

    // cleanupComplete() is running, since some of the regions we find to be

    // empty might not yet be added to the free list. It is not straightforward

    // to know in which list they are on so that we can remove them. We only

    // need to do this if we need to allocate more than one region to satisfy the

    // current humongous allocation request. If we are only allocating one region

    // we use the one-region region allocation code (see above), that already

    // potentially waits for regions from the secondary free list.

    wait_while_free_regions_coming();

    append_secondary_free_list_if_not_empty_with_lock();

    // Policy: Try only empty regions (i.e. already committed first). Maybe we

    // are lucky enough to find some.

    first = _hrm.find_contiguous_only_empty(obj_regions);

    if (first != G1_NO_HRM_INDEX) {

      _hrm.allocate_free_regions_starting_at(first, obj_regions);

    }

  }

  if (first == G1_NO_HRM_INDEX) {

    // Policy: We could not find enough regions for the humongous object in the

    // free list. Look through the heap to find a mix of free and uncommitted regions.

    // If so, try expansion.

    first = _hrm.find_contiguous_empty_or_unavailable(obj_regions);

    if (first != G1_NO_HRM_INDEX) {

      // We found something. Make sure these regions are committed, i.e. expand

      // the heap. Alternatively we could do a defragmentation GC.

      log_debug(gc, ergo, heap)("Attempt heap expansion (humongous allocation request failed). Allocation request: " SIZE_FORMAT "B",

                                    word_size * HeapWordSize);

      _hrm.expand_at(first, obj_regions);

      g1_policy()->record_new_heap_size(num_regions());

#ifdef ASSERT

      for (uint i = first; i < first + obj_regions; ++i) {

        HeapRegion* hr = region_at(i);

        assert(hr->is_free(), "sanity");

        assert(hr->is_empty(), "sanity");

        assert(is_on_master_free_list(hr), "sanity");

      }

#endif

      _hrm.allocate_free_regions_starting_at(first, obj_regions);

    } else {

      // Policy: Potentially trigger a defragmentation GC.