/*

 * Copyright (c) 2011, 2014, 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 "gc_interface/collectedHeap.hpp"

#include "memory/allocation.hpp"

#include "memory/binaryTreeDictionary.hpp"

#include "memory/freeList.hpp"

#include "memory/collectorPolicy.hpp"

#include "memory/filemap.hpp"

#include "memory/freeList.hpp"

#include "memory/gcLocker.hpp"

#include "memory/metachunk.hpp"

#include "memory/metaspace.hpp"

#include "memory/metaspaceGCThresholdUpdater.hpp"

#include "memory/metaspaceShared.hpp"

#include "memory/metaspaceTracer.hpp"

#include "memory/resourceArea.hpp"

#include "memory/universe.hpp"

#include "runtime/atomic.inline.hpp"

#include "runtime/globals.hpp"

#include "runtime/init.hpp"

#include "runtime/java.hpp"

#include "runtime/mutex.hpp"

#include "runtime/orderAccess.inline.hpp"

#include "services/memTracker.hpp"

#include "services/memoryService.hpp"

#include "utilities/copy.hpp"

#include "utilities/debug.hpp"

PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC

typedef BinaryTreeDictionary<Metablock, FreeList<Metablock> > BlockTreeDictionary;

typedef BinaryTreeDictionary<Metachunk, FreeList<Metachunk> > ChunkTreeDictionary;

// Set this constant to enable slow integrity checking of the free chunk lists

const bool metaspace_slow_verify = false;

size_t const allocation_from_dictionary_limit = 4 * K;

MetaWord* last_allocated = 0;

size_t Metaspace::_compressed_class_space_size;

const MetaspaceTracer* Metaspace::_tracer = NULL;

// Used in declarations in SpaceManager and ChunkManager

enum ChunkIndex {

  ZeroIndex = 0,

  SpecializedIndex = ZeroIndex,

  SmallIndex = SpecializedIndex + 1,

  MediumIndex = SmallIndex + 1,

  HumongousIndex = MediumIndex + 1,

  NumberOfFreeLists = 3,

  NumberOfInUseLists = 4

};

enum ChunkSizes {    // in words.

  ClassSpecializedChunk = 128,

  SpecializedChunk = 128,

  ClassSmallChunk = 256,

  SmallChunk = 512,

  ClassMediumChunk = 4 * K,

  MediumChunk = 8 * K

};

static ChunkIndex next_chunk_index(ChunkIndex i) {

  assert(i < NumberOfInUseLists, "Out of bound");

  return (ChunkIndex) (i+1);

}

volatile intptr_t MetaspaceGC::_capacity_until_GC = 0;

uint MetaspaceGC::_shrink_factor = 0;

bool MetaspaceGC::_should_concurrent_collect = false;

typedef class FreeList<Metachunk> ChunkList;

// Manages the global free lists of chunks.

class ChunkManager : public CHeapObj<mtInternal> {

  friend class TestVirtualSpaceNodeTest;

  // Free list of chunks of different sizes.

  //   SpecializedChunk

  //   SmallChunk

  //   MediumChunk

  //   HumongousChunk

  ChunkList _free_chunks[NumberOfFreeLists];

  //   HumongousChunk

  ChunkTreeDictionary _humongous_dictionary;

  // ChunkManager in all lists of this type

  size_t _free_chunks_total;

  size_t _free_chunks_count;

  void dec_free_chunks_total(size_t v) {

    assert(_free_chunks_count > 0 &&

             _free_chunks_total > 0,

             "About to go negative");

    Atomic::add_ptr(-1, &_free_chunks_count);

    jlong minus_v = (jlong) - (jlong) v;

    Atomic::add_ptr(minus_v, &_free_chunks_total);

  }

  // Debug support

  size_t sum_free_chunks();

  size_t sum_free_chunks_count();

  void locked_verify_free_chunks_total();

  void slow_locked_verify_free_chunks_total() {

    if (metaspace_slow_verify) {

      locked_verify_free_chunks_total();

    }

  }

  void locked_verify_free_chunks_count();

  void slow_locked_verify_free_chunks_count() {

    if (metaspace_slow_verify) {

      locked_verify_free_chunks_count();

    }

  }

  void verify_free_chunks_count();

 public:

  ChunkManager(size_t specialized_size, size_t small_size, size_t medium_size)

      : _free_chunks_total(0), _free_chunks_count(0) {

    _free_chunks[SpecializedIndex].set_size(specialized_size);

    _free_chunks[SmallIndex].set_size(small_size);

    _free_chunks[MediumIndex].set_size(medium_size);

  }

  // add or delete (return) a chunk to the global freelist.

  Metachunk* chunk_freelist_allocate(size_t word_size);

  // Map a size to a list index assuming that there are lists

  // for special, small, medium, and humongous chunks.

  static ChunkIndex list_index(size_t size);

  // Remove the chunk from its freelist.  It is

  // expected to be on one of the _free_chunks[] lists.

  void remove_chunk(Metachunk* chunk);

  // Add the simple linked list of chunks to the freelist of chunks

  // of type index.

  void return_chunks(ChunkIndex index, Metachunk* chunks);

  // Total of the space in the free chunks list

  size_t free_chunks_total_words();

  size_t free_chunks_total_bytes();

  // Number of chunks in the free chunks list

  size_t free_chunks_count();

  void inc_free_chunks_total(size_t v, size_t count = 1) {

    Atomic::add_ptr(count, &_free_chunks_count);

    Atomic::add_ptr(v, &_free_chunks_total);

  }

  ChunkTreeDictionary* humongous_dictionary() {

    return &_humongous_dictionary;

  }

  ChunkList* free_chunks(ChunkIndex index);

  // Returns the list for the given chunk word size.

  ChunkList* find_free_chunks_list(size_t word_size);

  // Remove from a list by size.  Selects list based on size of chunk.

  Metachunk* free_chunks_get(size_t chunk_word_size);

#define index_bounds_check(index)                                         \

  assert(index == SpecializedIndex ||                                     \

         index == SmallIndex ||                                           \

         index == MediumIndex ||                                          \

         index == HumongousIndex, err_msg("Bad index: %d", (int) index))

  size_t num_free_chunks(ChunkIndex index) const {

    index_bounds_check(index);

    if (index == HumongousIndex) {

      return _humongous_dictionary.total_free_blocks();

    }

    ssize_t count = _free_chunks[index].count();

    return count == -1 ? 0 : (size_t) count;

  }

  size_t size_free_chunks_in_bytes(ChunkIndex index) const {

    index_bounds_check(index);

    size_t word_size = 0;

    if (index == HumongousIndex) {

      word_size = _humongous_dictionary.total_size();

    } else {

      const size_t size_per_chunk_in_words = _free_chunks[index].size();

      word_size = size_per_chunk_in_words * num_free_chunks(index);

    }

    return word_size * BytesPerWord;

  }

  MetaspaceChunkFreeListSummary chunk_free_list_summary() const {

    return MetaspaceChunkFreeListSummary(num_free_chunks(SpecializedIndex),

                                         num_free_chunks(SmallIndex),

                                         num_free_chunks(MediumIndex),

                                         num_free_chunks(HumongousIndex),

                                         size_free_chunks_in_bytes(SpecializedIndex),

                                         size_free_chunks_in_bytes(SmallIndex),

                                         size_free_chunks_in_bytes(MediumIndex),

                                         size_free_chunks_in_bytes(HumongousIndex));

  }

  // Debug support

  void verify();

  void slow_verify() {

    if (metaspace_slow_verify) {

      verify();

    }

  }

  void locked_verify();

  void slow_locked_verify() {

    if (metaspace_slow_verify) {

      locked_verify();

    }

  }

  void verify_free_chunks_total();

  void locked_print_free_chunks(outputStream* st);

  void locked_print_sum_free_chunks(outputStream* st);

  void print_on(outputStream* st) const;

};

// Used to manage the free list of Metablocks (a block corresponds

// to the allocation of a quantum of metadata).

class BlockFreelist VALUE_OBJ_CLASS_SPEC {

  BlockTreeDictionary* _dictionary;

  // Only allocate and split from freelist if the size of the allocation

  // is at least 1/4th the size of the available block.

  const static int WasteMultiplier = 4;

  // Accessors

  BlockTreeDictionary* dictionary() const { return _dictionary; }

 public:

  BlockFreelist();

  ~BlockFreelist();

  // Get and return a block to the free list

  MetaWord* get_block(size_t word_size);

  void return_block(MetaWord* p, size_t word_size);

  size_t total_size() {

  if (dictionary() == NULL) {

    return 0;

  } else {

    return dictionary()->total_size();

  }

}

  void print_on(outputStream* st) const;

};

// A VirtualSpaceList node.

class VirtualSpaceNode : public CHeapObj<mtClass> {

  friend class VirtualSpaceList;

  // Link to next VirtualSpaceNode

  VirtualSpaceNode* _next;

  // total in the VirtualSpace

  MemRegion _reserved;

  ReservedSpace _rs;

  VirtualSpace _virtual_space;

  MetaWord* _top;

  // count of chunks contained in this VirtualSpace

  uintx _container_count;

  // Convenience functions to access the _virtual_space

  char* low()  const { return virtual_space()->low(); }

  char* high() const { return virtual_space()->high(); }

  // The first Metachunk will be allocated at the bottom of the

  // VirtualSpace

  Metachunk* first_chunk() { return (Metachunk*) bottom(); }

  // Committed but unused space in the virtual space

  size_t free_words_in_vs() const;

 public:

  VirtualSpaceNode(size_t byte_size);

  VirtualSpaceNode(ReservedSpace rs) : _top(NULL), _next(NULL), _rs(rs), _container_count(0) {}

  ~VirtualSpaceNode();

  // Convenience functions for logical bottom and end

  MetaWord* bottom() const { return (MetaWord*) _virtual_space.low(); }

  MetaWord* end() const { return (MetaWord*) _virtual_space.high(); }

  bool contains(const void* ptr) { return ptr >= low() && ptr < high(); }

  size_t reserved_words() const  { return _virtual_space.reserved_size() / BytesPerWord; }

  size_t committed_words() const { return _virtual_space.actual_committed_size() / BytesPerWord; }

  bool is_pre_committed() const { return _virtual_space.special(); }

  // address of next available space in _virtual_space;

  // Accessors

  VirtualSpaceNode* next() { return _next; }

  void set_next(VirtualSpaceNode* v) { _next = v; }

  void set_reserved(MemRegion const v) { _reserved = v; }

  void set_top(MetaWord* v) { _top = v; }

  // Accessors

  MemRegion* reserved() { return &_reserved; }

  VirtualSpace* virtual_space() const { return (VirtualSpace*) &_virtual_space; }

  // Returns true if "word_size" is available in the VirtualSpace

  bool is_available(size_t word_size) { return word_size <= pointer_delta(end(), _top, sizeof(MetaWord)); }

  MetaWord* top() const { return _top; }

  void inc_top(size_t word_size) { _top += word_size; }

  uintx container_count() { return _container_count; }

  void inc_container_count();

  void dec_container_count();

#ifdef ASSERT

  uint container_count_slow();

  void verify_container_count();

#endif

  // used and capacity in this single entry in the list

  size_t used_words_in_vs() const;

  size_t capacity_words_in_vs() const;

  bool initialize();

  // get space from the virtual space

  Metachunk* take_from_committed(size_t chunk_word_size);

  // Allocate a chunk from the virtual space and return it.

  Metachunk* get_chunk_vs(size_t chunk_word_size);

  // Expands/shrinks the committed space in a virtual space.  Delegates

  // to Virtualspace

  bool expand_by(size_t min_words, size_t preferred_words);

  // In preparation for deleting this node, remove all the chunks

  // in the node from any freelist.

  void purge(ChunkManager* chunk_manager);

  // If an allocation doesn't fit in the current node a new node is created.

  // Allocate chunks out of the remaining committed space in this node

  // to avoid wasting that memory.

  // This always adds up because all the chunk sizes are multiples of

  // the smallest chunk size.

  void retire(ChunkManager* chunk_manager);

#ifdef ASSERT

  // Debug support

  void mangle();

#endif

  void print_on(outputStream* st) const;

};

#define assert_is_ptr_aligned(ptr, alignment) \

  assert(is_ptr_aligned(ptr, alignment),      \

    err_msg(PTR_FORMAT " is not aligned to "  \

      SIZE_FORMAT, ptr, alignment))

#define assert_is_size_aligned(size, alignment) \

  assert(is_size_aligned(size, alignment),      \

    err_msg(SIZE_FORMAT " is not aligned to "   \

       SIZE_FORMAT, size, alignment))

// Decide if large pages should be committed when the memory is reserved.

static bool should_commit_large_pages_when_reserving(size_t bytes) {

  if (UseLargePages && UseLargePagesInMetaspace && !os::can_commit_large_page_memory()) {

    size_t words = bytes / BytesPerWord;

    bool is_class = false; // We never reserve large pages for the class space.

    if (MetaspaceGC::can_expand(words, is_class) &&

        MetaspaceGC::allowed_expansion() >= words) {

      return true;

    }

  }

  return false;

}

  // byte_size is the size of the associated virtualspace.

VirtualSpaceNode::VirtualSpaceNode(size_t bytes) : _top(NULL), _next(NULL), _rs(), _container_count(0) {

  assert_is_size_aligned(bytes, Metaspace::reserve_alignment());

#if INCLUDE_CDS

  // This allocates memory with mmap.  For DumpSharedspaces, try to reserve

  // configurable address, generally at the top of the Java heap so other

  // memory addresses don't conflict.

  if (DumpSharedSpaces) {

    bool large_pages = false; // No large pages when dumping the CDS archive.

    char* shared_base = (char*)align_ptr_up((char*)SharedBaseAddress, Metaspace::reserve_alignment());

    _rs = ReservedSpace(bytes, Metaspace::reserve_alignment(), large_pages, shared_base, 0);

    if (_rs.is_reserved()) {

      assert(shared_base == 0 || _rs.base() == shared_base, "should match");

    } else {

      // Get a mmap region anywhere if the SharedBaseAddress fails.

      _rs = ReservedSpace(bytes, Metaspace::reserve_alignment(), large_pages);

    }

    MetaspaceShared::set_shared_rs(&_rs);

  } else

#endif

  {

    bool large_pages = should_commit_large_pages_when_reserving(bytes);

    _rs = ReservedSpace(bytes, Metaspace::reserve_alignment(), large_pages);

  }

  if (_rs.is_reserved()) {

    assert(_rs.base() != NULL, "Catch if we get a NULL address");

    assert(_rs.size() != 0, "Catch if we get a 0 size");

    assert_is_ptr_aligned(_rs.base(), Metaspace::reserve_alignment());

    assert_is_size_aligned(_rs.size(), Metaspace::reserve_alignment());

    MemTracker::record_virtual_memory_type((address)_rs.base(), mtClass);

  }

}

void VirtualSpaceNode::purge(ChunkManager* chunk_manager) {

  Metachunk* chunk = first_chunk();

  Metachunk* invalid_chunk = (Metachunk*) top();

  while (chunk < invalid_chunk ) {

    assert(chunk->is_tagged_free(), "Should be tagged free");

    MetaWord* next = ((MetaWord*)chunk) + chunk->word_size();

    chunk_manager->remove_chunk(chunk);

    assert(chunk->next() == NULL &&

           chunk->prev() == NULL,

           "Was not removed from its list");

    chunk = (Metachunk*) next;

  }

}

#ifdef ASSERT

uint VirtualSpaceNode::container_count_slow() {

  uint count = 0;

  Metachunk* chunk = first_chunk();

  Metachunk* invalid_chunk = (Metachunk*) top();

  while (chunk < invalid_chunk ) {

    MetaWord* next = ((MetaWord*)chunk) + chunk->word_size();

    // Don't count the chunks on the free lists.  Those are

    // still part of the VirtualSpaceNode but not currently

    // counted.

    if (!chunk->is_tagged_free()) {

      count++;

    }

    chunk = (Metachunk*) next;

  }

  return count;

}

#endif

// List of VirtualSpaces for metadata allocation.

class VirtualSpaceList : public CHeapObj<mtClass> {

  friend class VirtualSpaceNode;

  enum VirtualSpaceSizes {

    VirtualSpaceSize = 256 * K

  };

  // Head of the list

  VirtualSpaceNode* _virtual_space_list;

  // virtual space currently being used for allocations

  VirtualSpaceNode* _current_virtual_space;

  // Is this VirtualSpaceList used for the compressed class space

  bool _is_class;

  // Sum of reserved and committed memory in the virtual spaces