/*

 * Copyright (c) 2011, 2018, 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 "aot/aotLoader.hpp"

#include "gc/shared/collectedHeap.hpp"

#include "gc/shared/collectorPolicy.hpp"

#include "logging/log.hpp"

#include "logging/logStream.hpp"

#include "memory/allocation.hpp"

#include "memory/binaryTreeDictionary.hpp"

#include "memory/filemap.hpp"

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

#include "utilities/copy.hpp"

#include "utilities/debug.hpp"

#include "utilities/macros.hpp"

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

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

// Helper function that does a bunch of checks for a chunk.

DEBUG_ONLY(static void do_verify_chunk(Metachunk* chunk);)

// Given a Metachunk, update its in-use information (both in the

// chunk and the occupancy map).

static void do_update_in_use_info_for_chunk(Metachunk* chunk, bool inuse);

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;

DEBUG_ONLY(bool Metaspace::_frozen = false;)

enum ChunkSizes {    // in words.

  ClassSpecializedChunk = 128,

  SpecializedChunk = 128,

  ClassSmallChunk = 256,

  SmallChunk = 512,

  ClassMediumChunk = 4 * K,

  MediumChunk = 8 * K

};

// Returns size of this chunk type.

size_t get_size_for_nonhumongous_chunktype(ChunkIndex chunktype, bool is_class) {

  assert(is_valid_nonhumongous_chunktype(chunktype), "invalid chunk type.");

  size_t size = 0;

  if (is_class) {

    switch(chunktype) {

      case SpecializedIndex: size = ClassSpecializedChunk; break;

      case SmallIndex: size = ClassSmallChunk; break;

      case MediumIndex: size = ClassMediumChunk; break;

      default:

        ShouldNotReachHere();

    }

  } else {

    switch(chunktype) {

      case SpecializedIndex: size = SpecializedChunk; break;

      case SmallIndex: size = SmallChunk; break;

      case MediumIndex: size = MediumChunk; break;

      default:

        ShouldNotReachHere();

    }

  }

  return size;

}

ChunkIndex get_chunk_type_by_size(size_t size, bool is_class) {

  if (is_class) {

    if (size == ClassSpecializedChunk) {

      return SpecializedIndex;

    } else if (size == ClassSmallChunk) {

      return SmallIndex;

    } else if (size == ClassMediumChunk) {

      return MediumIndex;

    } else if (size > ClassMediumChunk) {

      // A valid humongous chunk size is a multiple of the smallest chunk size.

      assert(is_aligned(size, ClassSpecializedChunk), "Invalid chunk size");

      return HumongousIndex;

    }

  } else {

    if (size == SpecializedChunk) {

      return SpecializedIndex;

    } else if (size == SmallChunk) {

      return SmallIndex;

    } else if (size == MediumChunk) {

      return MediumIndex;

    } else if (size > MediumChunk) {

      // A valid humongous chunk size is a multiple of the smallest chunk size.

      assert(is_aligned(size, SpecializedChunk), "Invalid chunk size");

      return HumongousIndex;

    }

  }

  ShouldNotReachHere();

  return (ChunkIndex)-1;

}

static ChunkIndex next_chunk_index(ChunkIndex i) {

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

  return (ChunkIndex) (i+1);

}

static ChunkIndex prev_chunk_index(ChunkIndex i) {

  assert(i > ZeroIndex, "Out of bound");

  return (ChunkIndex) (i-1);

}

static const char* scale_unit(size_t scale) {

  switch(scale) {

    case 1: return "BYTES";

    case K: return "KB";

    case M: return "MB";

    case G: return "GB";

    default:

      ShouldNotReachHere();

      return NULL;

  }

}

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

  ChunkList _free_chunks[NumberOfFreeLists];

  // Whether or not this is the class chunkmanager.

  const bool _is_class;

  // Return non-humongous chunk list by its index.

  ChunkList* free_chunks(ChunkIndex index);

  // Returns non-humongous chunk list for the given chunk word size.

  ChunkList* find_free_chunks_list(size_t word_size);

  //   HumongousChunk

  ChunkTreeDictionary _humongous_dictionary;

  // Returns the humongous chunk dictionary.

  ChunkTreeDictionary* humongous_dictionary() {

    return &_humongous_dictionary;

  }

  // Size, in metaspace words, of all chunks managed by this ChunkManager

  size_t _free_chunks_total;

  // Number of chunks in this ChunkManager

  size_t _free_chunks_count;

  // Update counters after a chunk was added or removed removed.

  void account_for_added_chunk(const Metachunk* c);

  void account_for_removed_chunk(const Metachunk* c);

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

      locked_verify_free_chunks_total();

    }

  }

  void locked_verify_free_chunks_count();

  void slow_locked_verify_free_chunks_count() {

    if (VerifyMetaspace) {

      locked_verify_free_chunks_count();

    }

  }

  void verify_free_chunks_count();

  // Given a pointer to a chunk, attempts to merge it with neighboring

  // free chunks to form a bigger chunk. Returns true if successful.

  bool attempt_to_coalesce_around_chunk(Metachunk* chunk, ChunkIndex target_chunk_type);

  // Helper for chunk merging:

  //  Given an address range with 1-n chunks which are all supposed to be

  //  free and hence currently managed by this ChunkManager, remove them

  //  from this ChunkManager and mark them as invalid.

  // - This does not correct the occupancy map.

  // - This does not adjust the counters in ChunkManager.

  // - Does not adjust container count counter in containing VirtualSpaceNode.

  // Returns number of chunks removed.

  int remove_chunks_in_area(MetaWord* p, size_t word_size);

  // Helper for chunk splitting: given a target chunk size and a larger free chunk,

  // split up the larger chunk into n smaller chunks, at least one of which should be

  // the target chunk of target chunk size. The smaller chunks, including the target

  // chunk, are returned to the freelist. The pointer to the target chunk is returned.

  // Note that this chunk is supposed to be removed from the freelist right away.

  Metachunk* split_chunk(size_t target_chunk_word_size, Metachunk* chunk);

 public:

  struct ChunkManagerStatistics {

    size_t num_by_type[NumberOfFreeLists];

    size_t single_size_by_type[NumberOfFreeLists];

    size_t total_size_by_type[NumberOfFreeLists];

    size_t num_humongous_chunks;

    size_t total_size_humongous_chunks;

  };

  void locked_get_statistics(ChunkManagerStatistics* stat) const;

  void get_statistics(ChunkManagerStatistics* stat) const;

  static void print_statistics(const ChunkManagerStatistics* stat, outputStream* out, size_t scale);

  ChunkManager(bool is_class)

      : _is_class(is_class), _free_chunks_total(0), _free_chunks_count(0) {

    _free_chunks[SpecializedIndex].set_size(get_size_for_nonhumongous_chunktype(SpecializedIndex, is_class));

    _free_chunks[SmallIndex].set_size(get_size_for_nonhumongous_chunktype(SmallIndex, is_class));

    _free_chunks[MediumIndex].set_size(get_size_for_nonhumongous_chunktype(MediumIndex, is_class));

  }

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

  ChunkIndex list_index(size_t size);

  // Map a given index to the chunk size.

  size_t size_by_index(ChunkIndex index) const;

  bool is_class() const { return _is_class; }

  // Convenience accessors.

  size_t medium_chunk_word_size() const { return size_by_index(MediumIndex); }

  size_t small_chunk_word_size() const { return size_by_index(SmallIndex); }

  size_t specialized_chunk_word_size() const { return size_by_index(SpecializedIndex); }

  // Take a chunk from the ChunkManager. The chunk is expected to be in

  // the chunk manager (the freelist if non-humongous, the dictionary if

  // humongous).

  void remove_chunk(Metachunk* chunk);

  // Return a single chunk of type index to the ChunkManager.

  void return_single_chunk(ChunkIndex index, Metachunk* chunk);

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

  // of type index.

  void return_chunk_list(ChunkIndex index, Metachunk* chunk);

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

  // 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(is_valid_chunktype(index), "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 (VerifyMetaspace) {

      verify();

    }

  }

  void locked_verify();

  void slow_locked_verify() {

    if (VerifyMetaspace) {

      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;

  // Prints composition for both non-class and (if available)

  // class chunk manager.

  static void print_all_chunkmanagers(outputStream* out, size_t scale = 1);

};

class SmallBlocks : public CHeapObj<mtClass> {

  const static uint _small_block_max_size = sizeof(TreeChunk<Metablock,  FreeList<Metablock> >)/HeapWordSize;

  const static uint _small_block_min_size = sizeof(Metablock)/HeapWordSize;

 private:

  FreeList<Metablock> _small_lists[_small_block_max_size - _small_block_min_size];

  FreeList<Metablock>& list_at(size_t word_size) {

    assert(word_size >= _small_block_min_size, "There are no metaspace objects less than %u words", _small_block_min_size);

    return _small_lists[word_size - _small_block_min_size];

  }

 public:

  SmallBlocks() {

    for (uint i = _small_block_min_size; i < _small_block_max_size; i++) {

      uint k = i - _small_block_min_size;

      _small_lists[k].set_size(i);

    }

  }

  size_t total_size() const {

    size_t result = 0;

    for (uint i = _small_block_min_size; i < _small_block_max_size; i++) {

      uint k = i - _small_block_min_size;

      result = result + _small_lists[k].count() * _small_lists[k].size();

    }

    return result;

  }

  static uint small_block_max_size() { return _small_block_max_size; }

  static uint small_block_min_size() { return _small_block_min_size; }

  MetaWord* get_block(size_t word_size) {

    if (list_at(word_size).count() > 0) {

      MetaWord* new_block = (MetaWord*) list_at(word_size).get_chunk_at_head();

      return new_block;

    } else {

      return NULL;

    }

  }

  void return_block(Metablock* free_chunk, size_t word_size) {

    list_at(word_size).return_chunk_at_head(free_chunk, false);

    assert(list_at(word_size).count() > 0, "Should have a chunk");

  }

  void print_on(outputStream* st) const {

    st->print_cr("SmallBlocks:");

    for (uint i = _small_block_min_size; i < _small_block_max_size; i++) {

      uint k = i - _small_block_min_size;

      st->print_cr("small_lists size " SIZE_FORMAT " count " SIZE_FORMAT, _small_lists[k].size(), _small_lists[k].count());

    }

  }

};

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

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

class BlockFreelist : public CHeapObj<mtClass> {

  BlockTreeDictionary* const _dictionary;

  SmallBlocks* _small_blocks;

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

  SmallBlocks* small_blocks() {

    if (_small_blocks == NULL) {

      _small_blocks = new SmallBlocks();

    }

    return _small_blocks;

  }

 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() const  {

    size_t result = dictionary()->total_size();

    if (_small_blocks != NULL) {

      result = result + _small_blocks->total_size();

    }

    return result;

  }

  static size_t min_dictionary_size()   { return TreeChunk<Metablock, FreeList<Metablock> >::min_size(); }

  void print_on(outputStream* st) const;

};

// Helper for Occupancy Bitmap. A type trait to give an all-bits-are-one-unsigned constant.

template <typename T> struct all_ones  { static const T value; };

template <> struct all_ones <uint64_t> { static const uint64_t value = 0xFFFFFFFFFFFFFFFFULL; };

template <> struct all_ones <uint32_t> { static const uint32_t value = 0xFFFFFFFF; };

// The OccupancyMap is a bitmap which, for a given VirtualSpaceNode,

// keeps information about

// - where a chunk starts

// - whether a chunk is in-use or free

// A bit in this bitmap represents one range of memory in the smallest

// chunk size (SpecializedChunk or ClassSpecializedChunk).

class OccupancyMap : public CHeapObj<mtInternal> {

  // The address range this map covers.

  const MetaWord* const _reference_address;

  const size_t _word_size;

  // The word size of a specialized chunk, aka the number of words one

  // bit in this map represents.

  const size_t _smallest_chunk_word_size;

  // map data

  // Data are organized in two bit layers:

  // The first layer is the chunk-start-map. Here, a bit is set to mark

  // the corresponding region as the head of a chunk.

  // The second layer is the in-use-map. Here, a set bit indicates that

  // the corresponding belongs to a chunk which is in use.

  uint8_t* _map[2];

  enum { layer_chunk_start_map = 0, layer_in_use_map = 1 };

  // length, in bytes, of bitmap data

  size_t _map_size;

  // Returns true if bit at position pos at bit-layer layer is set.