/*

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

#include "memory/filemap.hpp"

#include "memory/freeList.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"

// Define this macro to deallocate Metablock.  If not defined,

// blocks are not yet deallocated and are only mangled.

#undef DEALLOCATE_BLOCKS

// Easily recognizable patterns

// These patterns can be the same in 32bit or 64bit since

// they only have to be easily recognizable.

const void* metaspace_allocation_leader = (void*) 0X11111111;

const void* metaspace_allocation_trailer = (void*) 0X77777777;

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

const size_t metadata_space_manager_allocate = 0xf3f3f3f3;

MetaWord* last_allocated = 0;

// Used in declarations in SpaceManager and ChunkManager

enum ChunkIndex {

  SmallIndex = 0,

  MediumIndex = 1,

  HumongousIndex = 2,

  NumberOfFreeLists = 3

};

static ChunkIndex next_chunk_index(ChunkIndex i) {

  assert(i < NumberOfFreeLists, "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.

//

// Metablock are the unit of allocation from a Chunk.  It contains

// the size of the requested allocation in a debug build.

// Also in a debug build it has a marker before and after the

// body of the block. The address of the body is the address returned

// by the allocation.

//

// Layout in a debug build.  In a product build only the body is present.

//

//     +-----------+-----------+------------+     +-----------+

//     | word size | leader    | body       | ... | trailer   |

//     +-----------+-----------+------------+     +-----------+

//

// A Metablock may be reused by its SpaceManager but are never moved between

// SpaceManagers.  There is no explicit link to the Metachunk

// from which it was allocated.  Metablock are not deallocated, rather

// the Metachunk it is a part of will be deallocated when it's

// associated class loader is collected.

//

// When the word size of a block is passed in to the deallocation

// call the word size no longer needs to be part of a Metablock.

class Metablock {

  friend class VMStructs;

 private:

  // Used to align the allocation (see below) and for debugging.

#ifdef ASSERT

  struct {

    size_t _word_size;

    void*  _leader;

  } _header;

  void* _data[1];

#endif

  static size_t _overhead;

#ifdef ASSERT

  void set_word_size(size_t v) { _header._word_size = v; }

  void* leader() { return _header._leader; }

  void* trailer() {

    jlong index = (jlong) _header._word_size - sizeof(_header)/BytesPerWord - 1;

    assert(index > 0, err_msg("Bad indexling of trailer %d", index));

    void** ptr = &_data[index];

    return *ptr;

  }

  void set_leader(void* v) { _header._leader = v; }

  void set_trailer(void* v) {

    void** ptr = &_data[_header._word_size - sizeof(_header)/BytesPerWord - 1];

    *ptr = v;

  }

 public:

  size_t word_size() { return _header._word_size; }

#endif

 public:

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

  // This places the body of the block at a 2 word boundary

  // because every block starts on a 2 word boundary.  Work out

  // how to make the body on a 2 word boundary if the block

  // starts on a arbitrary boundary.  JJJ

#ifdef ASSERT

  MetaWord* data() { return (MetaWord*) &_data[0]; }

#else

  MetaWord* data() { return (MetaWord*) this; }

#endif

  static Metablock* metablock_from_data(MetaWord* p) {

#ifdef ASSERT

    size_t word_offset = offset_of(Metablock, _data)/BytesPerWord;

    Metablock* result = (Metablock*) (p - word_offset);

    return result;

#else

    return (Metablock*) p;

#endif

  }

  static size_t overhead() { return _overhead; }

  void verify();

};

//  Metachunk - Quantum of allocation from a Virtualspace

//    Metachunks are reused (when freed are put on a global freelist) and

//    have no permanent association to a SpaceManager.

//            +--------------+ <- end

//            |              |          --+       ---+

//            |              |            | free     |

//            |              |            |          |

//            |              |            |          | capacity

//            |              |            |          |

//            |              | <- top   --+          |

//            |              |           ---+        |

//            |              |              | used   |

//            |              |              |        |

//            |              |              |        |

//            +--------------+ <- bottom ---+     ---+

class Metachunk VALUE_OBJ_CLASS_SPEC {

  // link to support lists of chunks

  Metachunk* _next;

  MetaWord* _bottom;

  MetaWord* _end;

  MetaWord* _top;

  size_t _word_size;

  // Metachunks are allocated out of a MetadataVirtualSpace and

  // and use some of its space to describe itself (plus alignment

  // considerations).  Metadata is allocated in the rest of the chunk.

  // This size is the overhead of maintaining the Metachunk within

  // the space.

  static size_t _overhead;

  void set_bottom(MetaWord* v) { _bottom = v; }

  void set_end(MetaWord* v) { _end = v; }

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

  void set_word_size(size_t v) { _word_size = v; }

 public:

  // Used to add a Metachunk to a list of Metachunks

  void set_next(Metachunk* v) { _next = v; assert(v != this, "Boom");}

  Metablock* allocate(size_t word_size);

  static Metachunk* initialize(MetaWord* ptr, size_t word_size);

  // Accessors

  Metachunk* next() const { return _next; }

  MetaWord* bottom() const { return _bottom; }

  MetaWord* end() const { return _end; }

  MetaWord* top() const { return _top; }

  size_t word_size() const { return _word_size; }

  static size_t overhead() { return _overhead; }

  // Reset top to bottom so chunk can be reused.

  void reset_empty() { _top = (_bottom + _overhead); }

  bool is_empty() { return _top == (_bottom + _overhead); }

  // used (has been allocated)

  // free (available for future allocations)

  // capacity (total size of chunk)

  size_t used_word_size();

  size_t free_word_size();

  size_t capacity_word_size();

#ifdef ASSERT

  void mangle() {

    // Mangle the payload of the chunk and not the links that

    // maintain list of chunks.

    HeapWord* start = (HeapWord*)(bottom() + overhead());

    size_t word_size = capacity_word_size() - overhead();

    Copy::fill_to_words(start, word_size, metadata_chunk_initialize);

  }

#endif // ASSERT

  void print_on(outputStream* st) const;

  void verify();

};

// 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[3];

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

  ChunkList* free_humongous_chunks() { return &_free_chunks[2]; }

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

};

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

#ifdef DEALLOCATE_BLOCKS

  BinaryTreeDictionary<Metablock>* _dictionary;

#endif

  static Metablock* initialize_free_chunk(Metablock* block, size_t word_size);

#ifdef DEALLOCATE_BLOCKS

  // Accessors

  BinaryTreeDictionary<Metablock>* dictionary() const { return _dictionary; }

#endif

 public:

  BlockFreelist();

  ~BlockFreelist();

  // Get and return a block to the free list

  Metablock* get_block(size_t word_size);

  void return_block(Metablock* block, size_t word_size);

  size_t totalSize() {

#ifdef DEALLOCATE_BLOCKS

    if (dictionary() == NULL) {

      return 0;

    } else {

      return dictionary()->totalSize();

    }

#else

    return 0;

#endif

  }

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