/*

 * Copyright (c) 2011, 2012, 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/binaryTreeDictionary.hpp"

#include "memory/freeList.hpp"

#include "memory/collectorPolicy.hpp"

#include "memory/filemap.hpp"

#include "memory/freeList.hpp"

#include "memory/metablock.hpp"

#include "memory/metachunk.hpp"

#include "memory/metaspace.hpp"

#include "memory/metaspaceShared.hpp"

#include "memory/resourceArea.hpp"

#include "memory/universe.hpp"

#include "runtime/globals.hpp"

#include "runtime/mutex.hpp"

#include "services/memTracker.hpp"

#include "utilities/copy.hpp"

#include "utilities/debug.hpp"

typedef BinaryTreeDictionary<Metablock, FreeList> BlockTreeDictionary;

typedef BinaryTreeDictionary<Metachunk, FreeList> ChunkTreeDictionary;

// Parameters for stress mode testing

const uint metadata_deallocate_a_lot_block = 10;

const uint metadata_deallocate_a_lock_chunk = 3;

size_t const allocation_from_dictionary_limit = 64 * K;

const size_t metadata_chunk_initialize = 0xf7f7f7f7;

const size_t metadata_deallocate = 0xf5f5f5f5;

MetaWord* last_allocated = 0;

// Used in declarations in SpaceManager and ChunkManager

enum ChunkIndex {

  SmallIndex = 0,

  MediumIndex = 1,

  HumongousIndex = 2,

  NumberOfFreeLists = 2,

  NumberOfInUseLists = 3

};

static ChunkIndex next_chunk_index(ChunkIndex i) {

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

  return (ChunkIndex) (i+1);

}

// Originally _capacity_until_GC was set to MetaspaceSize here but

// the default MetaspaceSize before argument processing was being

// used which was not the desired value.  See the code

// in should_expand() to see how the initialization is handled

// now.

size_t MetaspaceGC::_capacity_until_GC = 0;

bool MetaspaceGC::_expand_after_GC = false;

uint MetaspaceGC::_shrink_factor = 0;

bool MetaspaceGC::_should_concurrent_collect = false;

// Blocks of space for metadata are allocated out of Metachunks.

//

// Metachunk are allocated out of MetadataVirtualspaces and once

// allocated there is no explicit link between a Metachunk and

// the MetadataVirtualspaces from which it was allocated.

//

// Each SpaceManager maintains a

// list of the chunks it is using and the current chunk.  The current

// chunk is the chunk from which allocations are done.  Space freed in

// a chunk is placed on the free list of blocks (BlockFreelist) and

// reused from there.

//

// Future modification

//

// The Metachunk can conceivable be replaced by the Chunk in

// allocation.hpp.  Note that the latter Chunk is the space for

// allocation (allocations from the chunk are out of the space in

// the Chunk after the header for the Chunk) where as Metachunks

// point to space in a VirtualSpace.  To replace Metachunks with

// Chunks, change Chunks so that they can be allocated out of a VirtualSpace.

size_t Metablock::_min_block_byte_size = sizeof(Metablock);

#ifdef ASSERT

  size_t Metablock::_overhead =

    Chunk::aligned_overhead_size(sizeof(Metablock)) / BytesPerWord;

#else

  size_t Metablock::_overhead = 0;

#endif

// Pointer to list of Metachunks.

class ChunkList VALUE_OBJ_CLASS_SPEC {

  // List of free chunks

  Metachunk* _head;

 public:

  // Constructor

  ChunkList() : _head(NULL) {}

  // Accessors

  Metachunk* head() { return _head; }

  void set_head(Metachunk* v) { _head = v; }

  // Link at head of the list

  void add_at_head(Metachunk* head, Metachunk* tail);

  void add_at_head(Metachunk* head);

  size_t sum_list_size();

  size_t sum_list_count();

  size_t sum_list_capacity();

};

// Manages the global free lists of chunks.

// Has three lists of free chunks, and a total size and

// count that includes all three

class ChunkManager VALUE_OBJ_CLASS_SPEC {

  // Free list of chunks of different sizes.

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

  void verify_free_chunks_count();

 public:

  ChunkManager() : _free_chunks_total(0), _free_chunks_count(0) {}

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

  Metachunk* chunk_freelist_allocate(size_t word_size);

  void chunk_freelist_deallocate(Metachunk* chunk);

  // Total of the space in the free chunks list

  size_t free_chunks_total();

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

  }

  ChunkList* free_medium_chunks() { return &_free_chunks[1]; }

  ChunkList* free_small_chunks() { return &_free_chunks[0]; }

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

  // Add and remove from a list by size.  Selects

  // list based on size of chunk.

  void free_chunks_put(Metachunk* chuck);

  Metachunk* free_chunks_get(size_t chunk_word_size);

  // Debug support

  void verify();

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

};

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

  static Metablock* initialize_free_chunk(MetaWord* p, size_t word_size);

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

};

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;

  // Convenience functions for logical bottom and end

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

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

  // Convenience functions to access the _virtual_space

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

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

 public:

  VirtualSpaceNode(size_t byte_size);

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

  ~VirtualSpaceNode();

  // 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 virtual space

  bool is_available(size_t word_size) { return _top + word_size <= end(); }

  MetaWord* top() const { return _top; }

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

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

  Metachunk* get_chunk_vs_with_expand(size_t chunk_word_size);

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

  // to Virtualspace

  bool expand_by(size_t words, bool pre_touch = false);

  bool shrink_by(size_t words);

  // Debug support

  static void verify_virtual_space_total();

  static void verify_virtual_space_count();

  void mangle();

  void print_on(outputStream* st) const;

};

  // byte_size is the size of the associated virtualspace.

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

  // This allocates memory with mmap.  For DumpSharedspaces, allocate the

  // space at low memory so that other shared images don't conflict.

  // This is the same address as memory needed for UseCompressedOops but

  // compressed oops don't work with CDS (offsets in metadata are wrong), so

  // borrow the same address.

  if (DumpSharedSpaces) {

    char* shared_base = (char*)HeapBaseMinAddress;

    _rs = ReservedSpace(byte_size, 0, false, shared_base, 0);

    if (_rs.is_reserved()) {

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

    } else {

      // If we are dumping the heap, then allocate a wasted block of address

      // space in order to push the heap to a lower address.  This extra

      // address range allows for other (or larger) libraries to be loaded

      // without them occupying the space required for the shared spaces.

      uintx reserved = 0;

      uintx block_size = 64*1024*1024;

      while (reserved < SharedDummyBlockSize) {

        char* dummy = os::reserve_memory(block_size);

        reserved += block_size;

      }

      _rs = ReservedSpace(byte_size);

    }

    MetaspaceShared::set_shared_rs(&_rs);

  } else {

    _rs = ReservedSpace(byte_size);

  }

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

}

// List of VirtualSpaces for metadata allocation.

// It has a  _next link for singly linked list and a MemRegion

// for total space in the VirtualSpace.

class VirtualSpaceList : public CHeapObj<mtClass> {

  friend class VirtualSpaceNode;

  enum VirtualSpaceSizes {

    VirtualSpaceSize = 256 * K

  };

  // Global list of virtual spaces

  // Head of the list

  VirtualSpaceNode* _virtual_space_list;

  // virtual space currently being used for allocations

  VirtualSpaceNode* _current_virtual_space;

  // Free chunk list for all other metadata

  ChunkManager      _chunk_manager;

  // Can this virtual list allocate >1 spaces?  Also, used to determine

  // whether to allocate unlimited small chunks in this virtual space

  bool _is_class;

  bool can_grow() const { return !is_class() || !UseCompressedKlassPointers; }

  // Sum of space in all virtual spaces and number of virtual spaces

  size_t _virtual_space_total;

  size_t _virtual_space_count;

  ~VirtualSpaceList();

  VirtualSpaceNode* virtual_space_list() const { return _virtual_space_list; }

  void set_virtual_space_list(VirtualSpaceNode* v) {

    _virtual_space_list = v;

  }

  void set_current_virtual_space(VirtualSpaceNode* v) {

    _current_virtual_space = v;

  }

  void link_vs(VirtualSpaceNode* new_entry, size_t vs_word_size);

  // Get another virtual space and add it to the list.  This

  // is typically prompted by a failed attempt to allocate a chunk

  // and is typically followed by the allocation of a chunk.

  bool grow_vs(size_t vs_word_size);

 public:

  VirtualSpaceList(size_t word_size);

  VirtualSpaceList(ReservedSpace rs);

  Metachunk* get_new_chunk(size_t word_size, size_t grow_chunks_by_words);

  VirtualSpaceNode* current_virtual_space() {

    return _current_virtual_space;

  }

  ChunkManager* chunk_manager() { return &_chunk_manager; }

  bool is_class() const { return _is_class; }

  // Allocate the first virtualspace.

  void initialize(size_t word_size);

  size_t virtual_space_total() { return _virtual_space_total; }

  void inc_virtual_space_total(size_t v) {

    Atomic::add_ptr(v, &_virtual_space_total);

  }

  size_t virtual_space_count() { return _virtual_space_count; }

  void inc_virtual_space_count() {

    Atomic::inc_ptr(&_virtual_space_count);

  }

  // Used and capacity in the entire list of virtual spaces.

  // These are global values shared by all Metaspaces

  size_t capacity_words_sum();

  size_t capacity_bytes_sum() { return capacity_words_sum() * BytesPerWord; }

  size_t used_words_sum();

  size_t used_bytes_sum() { return used_words_sum() * BytesPerWord; }

  bool contains(const void *ptr);

  void print_on(outputStream* st) const;

  class VirtualSpaceListIterator : public StackObj {

    VirtualSpaceNode* _virtual_spaces;

   public:

    VirtualSpaceListIterator(VirtualSpaceNode* virtual_spaces) :

      _virtual_spaces(virtual_spaces) {}

    bool repeat() {

      return _virtual_spaces != NULL;

    }

    VirtualSpaceNode* get_next() {

      VirtualSpaceNode* result = _virtual_spaces;

      if (_virtual_spaces != NULL) {

        _virtual_spaces = _virtual_spaces->next();

      }

      return result;

    }

  };

};

class Metadebug : AllStatic {

  // Debugging support for Metaspaces

  static int _deallocate_block_a_lot_count;

  static int _deallocate_chunk_a_lot_count;

  static int _allocation_fail_alot_count;

 public:

  static int deallocate_block_a_lot_count() {

    return _deallocate_block_a_lot_count;

  }

  static void set_deallocate_block_a_lot_count(int v) {

    _deallocate_block_a_lot_count = v;

  }

  static void inc_deallocate_block_a_lot_count() {

    _deallocate_block_a_lot_count++;

  }

  static int deallocate_chunk_a_lot_count() {

    return _deallocate_chunk_a_lot_count;

  }

  static void reset_deallocate_chunk_a_lot_count() {

    _deallocate_chunk_a_lot_count = 1;

  }

  static void inc_deallocate_chunk_a_lot_count() {

    _deallocate_chunk_a_lot_count++;

  }

  static void init_allocation_fail_alot_count();

#ifdef ASSERT

  static bool test_metadata_failure();

#endif

  static void deallocate_chunk_a_lot(SpaceManager* sm,

                                     size_t chunk_word_size);

  static void deallocate_block_a_lot(SpaceManager* sm,

                                     size_t chunk_word_size);

};

int Metadebug::_deallocate_block_a_lot_count = 0;

int Metadebug::_deallocate_chunk_a_lot_count = 0;

int Metadebug::_allocation_fail_alot_count = 0;

//  SpaceManager - used by Metaspace to handle allocations

class SpaceManager : public CHeapObj<mtClass> {

  friend class Metaspace;

  friend class Metadebug;

 private:

  // protects allocations and contains.

  Mutex* const _lock;

  // List of chunks in use by this SpaceManager.  Allocations