/*

 * Copyright (c) 2011, 2013, 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 "runtime/orderAccess.hpp"

#include "services/memTracker.hpp"

#include "utilities/copy.hpp"

#include "utilities/debug.hpp"

typedef BinaryTreeDictionary<Metablock, FreeList> BlockTreeDictionary;

typedef BinaryTreeDictionary<Metachunk, FreeList> ChunkTreeDictionary;

// Define this macro to enable slow integrity checking of

// the free chunk lists

const bool metaspace_slow_verify = false;

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

MetaWord* last_allocated = 0;

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

  HumongousChunkGranularity = 8

};

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.

typedef class FreeList<Metachunk> ChunkList;

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

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

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

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

  }

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

};

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

  // count of chunks contained in this VirtualSpace

  uintx _container_count;

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

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

  // VirtualSpace

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

  void inc_container_count();

#ifdef ASSERT

  uint container_count_slow();

#endif

 public:

  VirtualSpaceNode(size_t byte_size);

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

  ~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 VirtualSpace

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

  uintx container_count() { return _container_count; }

  void dec_container_count();

#ifdef ASSERT

  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;

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

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

  // in the node from any freelist.

  void purge(ChunkManager* chunk_manager);

#ifdef ASSERT

  // Debug support

  static void verify_virtual_space_total();

  static void verify_virtual_space_count();

  void mangle();

#endif

  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), _container_count(0) {

  // align up to vm allocation granularity

  byte_size = align_size_up(byte_size, os::vm_allocation_granularity());

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

    char* shared_base = (char*)SharedBaseAddress;

    _rs = ReservedSpace(byte_size, 0, false, 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(byte_size);

    }

    MetaspaceShared::set_shared_rs(&_rs);

  } else {

    _rs = ReservedSpace(byte_size);

  }

  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_free(), "Should be marked 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_free()) {

      count++;

    }

    chunk = (Metachunk*) next;

  }

  return count;

}

#endif

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

  size_t free_bytes();

  Metachunk* get_new_chunk(size_t word_size,

                           size_t grow_chunks_by_words,

                           size_t medium_chunk_bunch);

  // Get the first chunk for a Metaspace.  Used for

  // special cases such as the boot class loader, reflection

  // class loader and anonymous class loader.

  Metachunk* get_initialization_chunk(size_t word_size, size_t chunk_bunch);

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

  void dec_virtual_space_total(size_t v);

  void inc_virtual_space_count();

  void dec_virtual_space_count();

  // Unlink empty VirtualSpaceNodes and free it.

  void purge();

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

    }

  };

};