changeset 49370:825f006619e5

8198423: Improve metaspace chunk allocation Reviewed-by: goetz, coleenp
author stuefe
date Tue, 06 Mar 2018 19:24:13 +0100
parents edb65305d3ac
children f95ef5511e1f
files src/hotspot/share/memory/metachunk.cpp src/hotspot/share/memory/metachunk.hpp src/hotspot/share/memory/metaspace.cpp src/hotspot/share/memory/metaspace.hpp src/hotspot/share/utilities/internalVMTests.cpp test/hotspot/gtest/memory/test_chunkManager.cpp test/hotspot/gtest/memory/test_metachunk.cpp test/hotspot/gtest/memory/test_metaspace_allocation.cpp
diffstat 8 files changed, 1536 insertions(+), 525 deletions(-) [+]
line wrap: on
line diff
--- a/src/hotspot/share/memory/metachunk.cpp	Tue Mar 06 08:36:44 2018 +0100
+++ b/src/hotspot/share/memory/metachunk.cpp	Tue Mar 06 19:24:13 2018 +0100
@@ -48,9 +48,14 @@
 
 // Metachunk methods
 
-Metachunk::Metachunk(size_t word_size,
+Metachunk::Metachunk(ChunkIndex chunktype, bool is_class, size_t word_size,
                      VirtualSpaceNode* container)
     : Metabase<Metachunk>(word_size),
+    _chunk_type(chunktype),
+    _is_class(is_class),
+    _sentinel(CHUNK_SENTINEL),
+    _origin(origin_normal),
+    _use_count(0),
     _top(NULL),
     _container(container)
 {
@@ -58,6 +63,7 @@
   set_is_tagged_free(false);
 #ifdef ASSERT
   mangle(uninitMetaWordVal);
+  verify();
 #endif
 }
 
@@ -83,15 +89,16 @@
 void Metachunk::print_on(outputStream* st) const {
   st->print_cr("Metachunk:"
                " bottom " PTR_FORMAT " top " PTR_FORMAT
-               " end " PTR_FORMAT " size " SIZE_FORMAT,
-               p2i(bottom()), p2i(_top), p2i(end()), word_size());
+               " end " PTR_FORMAT " size " SIZE_FORMAT " (%s)",
+               p2i(bottom()), p2i(_top), p2i(end()), word_size(),
+               chunk_size_name(get_chunk_type()));
   if (Verbose) {
     st->print_cr("    used " SIZE_FORMAT " free " SIZE_FORMAT,
                  used_word_size(), free_word_size());
   }
 }
 
-#ifndef PRODUCT
+#ifdef ASSERT
 void Metachunk::mangle(juint word_value) {
   // Overwrite the payload of the chunk and not the links that
   // maintain list of chunks.
@@ -99,16 +106,44 @@
   size_t size = word_size() - overhead();
   Copy::fill_to_words(start, size, word_value);
 }
-#endif // PRODUCT
 
 void Metachunk::verify() {
-#ifdef ASSERT
-  // Cannot walk through the blocks unless the blocks have
-  // headers with sizes.
-  assert(bottom() <= _top &&
-         _top <= (MetaWord*)end(),
-         "Chunk has been smashed");
-#endif
-  return;
+  assert(is_valid_sentinel(), "Chunk " PTR_FORMAT ": sentinel invalid", p2i(this));
+  const ChunkIndex chunk_type = get_chunk_type();
+  assert(is_valid_chunktype(chunk_type), "Chunk " PTR_FORMAT ": Invalid chunk type.", p2i(this));
+  if (chunk_type != HumongousIndex) {
+    assert(word_size() == get_size_for_nonhumongous_chunktype(chunk_type, is_class()),
+           "Chunk " PTR_FORMAT ": wordsize " SIZE_FORMAT " does not fit chunk type %s.",
+           p2i(this), word_size(), chunk_size_name(chunk_type));
+  }
+  assert(is_valid_chunkorigin(get_origin()), "Chunk " PTR_FORMAT ": Invalid chunk origin.", p2i(this));
+  assert(bottom() <= _top && _top <= (MetaWord*)end(),
+         "Chunk " PTR_FORMAT ": Chunk top out of chunk bounds.", p2i(this));
+
+  // For non-humongous chunks, starting address shall be aligned
+  // to its chunk size. Humongous chunks start address is
+  // aligned to specialized chunk size.
+  const size_t required_alignment =
+    (chunk_type != HumongousIndex ? word_size() : get_size_for_nonhumongous_chunktype(SpecializedIndex, is_class())) * sizeof(MetaWord);
+  assert(is_aligned((address)this, required_alignment),
+         "Chunk " PTR_FORMAT ": (size " SIZE_FORMAT ") not aligned to " SIZE_FORMAT ".",
+         p2i(this), word_size() * sizeof(MetaWord), required_alignment);
 }
 
+#endif // ASSERT
+
+// Helper, returns a descriptive name for the given index.
+const char* chunk_size_name(ChunkIndex index) {
+  switch (index) {
+    case SpecializedIndex:
+      return "specialized";
+    case SmallIndex:
+      return "small";
+    case MediumIndex:
+      return "medium";
+    case HumongousIndex:
+      return "humongous";
+    default:
+      return "Invalid index";
+  }
+}
--- a/src/hotspot/share/memory/metachunk.hpp	Tue Mar 06 08:36:44 2018 +0100
+++ b/src/hotspot/share/memory/metachunk.hpp	Tue Mar 06 19:24:13 2018 +0100
@@ -94,16 +94,84 @@
 //            |              |             |         |
 //            +--------------+ <- bottom --+       --+
 
+// ChunkIndex defines the type of chunk.
+// Chunk types differ by size: specialized < small < medium, chunks
+// larger than medium are humongous chunks of varying size.
+enum ChunkIndex {
+  ZeroIndex = 0,
+  SpecializedIndex = ZeroIndex,
+  SmallIndex = SpecializedIndex + 1,
+  MediumIndex = SmallIndex + 1,
+  HumongousIndex = MediumIndex + 1,
+  NumberOfFreeLists = 3,
+  NumberOfInUseLists = 4
+};
+
+// Utility functions.
+size_t get_size_for_nonhumongous_chunktype(ChunkIndex chunk_type, bool is_class);
+ChunkIndex get_chunk_type_by_size(size_t size, bool is_class);
+
+// Returns a descriptive name for a chunk type.
+const char* chunk_size_name(ChunkIndex index);
+
+// Verify chunk type.
+inline bool is_valid_chunktype(ChunkIndex index) {
+  return index == SpecializedIndex || index == SmallIndex ||
+         index == MediumIndex || index == HumongousIndex;
+}
+
+inline bool is_valid_nonhumongous_chunktype(ChunkIndex index) {
+  return is_valid_chunktype(index) && index != HumongousIndex;
+}
+
+enum ChunkOrigin {
+  // Chunk normally born (via take_from_committed)
+  origin_normal = 1,
+  // Chunk was born as padding chunk
+  origin_pad = 2,
+  // Chunk was born as leftover chunk in VirtualSpaceNode::retire
+  origin_leftover = 3,
+  // Chunk was born as result of a merge of smaller chunks
+  origin_merge = 4,
+  // Chunk was born as result of a split of a larger chunk
+  origin_split = 5,
+
+  origin_minimum = origin_normal,
+  origin_maximum = origin_split,
+  origins_count = origin_maximum + 1
+};
+
+inline bool is_valid_chunkorigin(ChunkOrigin origin) {
+  return origin == origin_normal ||
+    origin == origin_pad ||
+    origin == origin_leftover ||
+    origin == origin_merge ||
+    origin == origin_split;
+}
+
 class Metachunk : public Metabase<Metachunk> {
   friend class MetachunkTest;
   // The VirtualSpaceNode containing this chunk.
-  VirtualSpaceNode* _container;
+  VirtualSpaceNode* const _container;
 
   // Current allocation top.
   MetaWord* _top;
 
+  // A 32bit sentinel for debugging purposes.
+  enum { CHUNK_SENTINEL = 0x4d4554EF,  // "MET"
+         CHUNK_SENTINEL_INVALID = 0xFEEEEEEF
+  };
+
+  uint32_t _sentinel;
+
+  const ChunkIndex _chunk_type;
+  const bool _is_class;
+  // Whether the chunk is free (in freelist) or in use by some class loader.
   bool _is_tagged_free;
 
+  ChunkOrigin _origin;
+  int _use_count;
+
   MetaWord* initial_top() const { return (MetaWord*)this + overhead(); }
   MetaWord* top() const         { return _top; }
 
@@ -120,7 +188,7 @@
   // Size of the Metachunk header, including alignment.
   static size_t overhead();
 
-  Metachunk(size_t word_size , VirtualSpaceNode* container);
+  Metachunk(ChunkIndex chunktype, bool is_class, size_t word_size, VirtualSpaceNode* container);
 
   MetaWord* allocate(size_t word_size);
 
@@ -143,12 +211,23 @@
 
   bool contains(const void* ptr) { return bottom() <= ptr && ptr < _top; }
 
-#ifndef PRODUCT
-  void mangle(juint word_value);
-#endif
+  void print_on(outputStream* st) const;
 
-  void print_on(outputStream* st) const;
-  void verify();
+  bool is_valid_sentinel() const        { return _sentinel == CHUNK_SENTINEL; }
+  void remove_sentinel()                { _sentinel = CHUNK_SENTINEL_INVALID; }
+
+  int get_use_count() const             { return _use_count; }
+  void inc_use_count()                  { _use_count ++; }
+
+  ChunkOrigin get_origin() const        { return _origin; }
+  void set_origin(ChunkOrigin orig)     { _origin = orig; }
+
+  ChunkIndex get_chunk_type() const     { return _chunk_type; }
+  bool is_class() const                 { return _is_class; }
+
+  DEBUG_ONLY(void mangle(juint word_value);)
+  DEBUG_ONLY(void verify();)
+
 };
 
 // Metablock is the unit of allocation from a Chunk.
--- a/src/hotspot/share/memory/metaspace.cpp	Tue Mar 06 08:36:44 2018 +0100
+++ b/src/hotspot/share/memory/metaspace.cpp	Tue Mar 06 19:24:13 2018 +0100
@@ -58,6 +58,13 @@
 // Set this constant to enable slow integrity checking of the free chunk lists
 const bool metaspace_slow_verify = false;
 
+// 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;
@@ -67,33 +74,6 @@
 
 DEBUG_ONLY(bool Metaspace::_frozen = false;)
 
-// 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
-};
-
-// Helper, returns a descriptive name for the given index.
-static const char* chunk_size_name(ChunkIndex index) {
-  switch (index) {
-    case SpecializedIndex:
-      return "specialized";
-    case SmallIndex:
-      return "small";
-    case MediumIndex:
-      return "medium";
-    case HumongousIndex:
-      return "humongous";
-    default:
-      return "Invalid index";
-  }
-}
-
 enum ChunkSizes {    // in words.
   ClassSpecializedChunk = 128,
   SpecializedChunk = 128,
@@ -103,11 +83,69 @@
   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) {
+      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) {
+      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";
@@ -136,6 +174,9 @@
   //   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);
 
@@ -178,6 +219,29 @@
   }
   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];
@@ -190,16 +254,15 @@
   void get_statistics(ChunkManagerStatistics* stat) const;
   static void print_statistics(const ChunkManagerStatistics* stat, outputStream* out, size_t scale);
 
- 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.
+
+  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
@@ -209,6 +272,13 @@
   // 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).
@@ -391,6 +461,294 @@
   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.
+  bool get_bit_at_position(unsigned pos, unsigned layer) const {
+    assert(layer == 0 || layer == 1, "Invalid layer %d", layer);
+    const unsigned byteoffset = pos / 8;
+    assert(byteoffset < _map_size,
+           "invalid byte offset (%u), map size is " SIZE_FORMAT ".", byteoffset, _map_size);
+    const unsigned mask = 1 << (pos % 8);
+    return (_map[layer][byteoffset] & mask) > 0;
+  }
+
+  // Changes bit at position pos at bit-layer layer to value v.
+  void set_bit_at_position(unsigned pos, unsigned layer, bool v) {
+    assert(layer == 0 || layer == 1, "Invalid layer %d", layer);
+    const unsigned byteoffset = pos / 8;
+    assert(byteoffset < _map_size,
+           "invalid byte offset (%u), map size is " SIZE_FORMAT ".", byteoffset, _map_size);
+    const unsigned mask = 1 << (pos % 8);
+    if (v) {
+      _map[layer][byteoffset] |= mask;
+    } else {
+      _map[layer][byteoffset] &= ~mask;
+    }
+  }
+
+  // Optimized case of is_any_bit_set_in_region for 32/64bit aligned access:
+  // pos is 32/64 aligned and num_bits is 32/64.
+  // This is the typical case when coalescing to medium chunks, whose size is
+  // 32 or 64 times the specialized chunk size (depending on class or non class
+  // case), so they occupy 64 bits which should be 64bit aligned, because
+  // chunks are chunk-size aligned.
+  template <typename T>
+  bool is_any_bit_set_in_region_3264(unsigned pos, unsigned num_bits, unsigned layer) const {
+    assert(_map_size > 0, "not initialized");
+    assert(layer == 0 || layer == 1, "Invalid layer %d.", layer);
+    assert(pos % (sizeof(T) * 8) == 0, "Bit position must be aligned (%u).", pos);
+    assert(num_bits == (sizeof(T) * 8), "Number of bits incorrect (%u).", num_bits);
+    const size_t byteoffset = pos / 8;
+    assert(byteoffset <= (_map_size - sizeof(T)),
+           "Invalid byte offset (" SIZE_FORMAT "), map size is " SIZE_FORMAT ".", byteoffset, _map_size);
+    const T w = *(T*)(_map[layer] + byteoffset);
+    return w > 0 ? true : false;
+  }
+
+  // Returns true if any bit in region [pos1, pos1 + num_bits) is set in bit-layer layer.
+  bool is_any_bit_set_in_region(unsigned pos, unsigned num_bits, unsigned layer) const {
+    if (pos % 32 == 0 && num_bits == 32) {
+      return is_any_bit_set_in_region_3264<uint32_t>(pos, num_bits, layer);
+    } else if (pos % 64 == 0 && num_bits == 64) {
+      return is_any_bit_set_in_region_3264<uint64_t>(pos, num_bits, layer);
+    } else {
+      for (unsigned n = 0; n < num_bits; n ++) {
+        if (get_bit_at_position(pos + n, layer)) {
+          return true;
+        }
+      }
+    }
+    return false;
+  }
+
+  // Returns true if any bit in region [p, p+word_size) is set in bit-layer layer.
+  bool is_any_bit_set_in_region(MetaWord* p, size_t word_size, unsigned layer) const {
+    assert(word_size % _smallest_chunk_word_size == 0,
+        "Region size " SIZE_FORMAT " not a multiple of smallest chunk size.", word_size);
+    const unsigned pos = get_bitpos_for_address(p);
+    const unsigned num_bits = (unsigned) (word_size / _smallest_chunk_word_size);
+    return is_any_bit_set_in_region(pos, num_bits, layer);
+  }
+
+  // Optimized case of set_bits_of_region for 32/64bit aligned access:
+  // pos is 32/64 aligned and num_bits is 32/64.
+  // This is the typical case when coalescing to medium chunks, whose size
+  // is 32 or 64 times the specialized chunk size (depending on class or non
+  // class case), so they occupy 64 bits which should be 64bit aligned,
+  // because chunks are chunk-size aligned.
+  template <typename T>
+  void set_bits_of_region_T(unsigned pos, unsigned num_bits, unsigned layer, bool v) {
+    assert(pos % (sizeof(T) * 8) == 0, "Bit position must be aligned to %u (%u).",
+           (unsigned)(sizeof(T) * 8), pos);
+    assert(num_bits == (sizeof(T) * 8), "Number of bits incorrect (%u), expected %u.",
+           num_bits, (unsigned)(sizeof(T) * 8));
+    const size_t byteoffset = pos / 8;
+    assert(byteoffset <= (_map_size - sizeof(T)),
+           "invalid byte offset (" SIZE_FORMAT "), map size is " SIZE_FORMAT ".", byteoffset, _map_size);
+    T* const pw = (T*)(_map[layer] + byteoffset);
+    *pw = v ? all_ones<T>::value : (T) 0;
+  }
+
+  // Set all bits in a region starting at pos to a value.
+  void set_bits_of_region(unsigned pos, unsigned num_bits, unsigned layer, bool v) {
+    assert(_map_size > 0, "not initialized");
+    assert(layer == 0 || layer == 1, "Invalid layer %d.", layer);
+    if (pos % 32 == 0 && num_bits == 32) {
+      set_bits_of_region_T<uint32_t>(pos, num_bits, layer, v);
+    } else if (pos % 64 == 0 && num_bits == 64) {
+      set_bits_of_region_T<uint64_t>(pos, num_bits, layer, v);
+    } else {
+      for (unsigned n = 0; n < num_bits; n ++) {
+        set_bit_at_position(pos + n, layer, v);
+      }
+    }
+  }
+
+  // Helper: sets all bits in a region [p, p+word_size).
+  void set_bits_of_region(MetaWord* p, size_t word_size, unsigned layer, bool v) {
+    assert(word_size % _smallest_chunk_word_size == 0,
+        "Region size " SIZE_FORMAT " not a multiple of smallest chunk size.", word_size);
+    const unsigned pos = get_bitpos_for_address(p);
+    const unsigned num_bits = (unsigned) (word_size / _smallest_chunk_word_size);
+    set_bits_of_region(pos, num_bits, layer, v);
+  }
+
+  // Helper: given an address, return the bit position representing that address.
+  unsigned get_bitpos_for_address(const MetaWord* p) const {
+    assert(_reference_address != NULL, "not initialized");
+    assert(p >= _reference_address && p < _reference_address + _word_size,
+           "Address %p out of range for occupancy map [%p..%p).",
+            p, _reference_address, _reference_address + _word_size);
+    assert(is_aligned(p, _smallest_chunk_word_size * sizeof(MetaWord)),
+           "Address not aligned (%p).", p);
+    const ptrdiff_t d = (p - _reference_address) / _smallest_chunk_word_size;
+    assert(d >= 0 && (size_t)d < _map_size * 8, "Sanity.");
+    return (unsigned) d;
+  }
+
+ public:
+
+  OccupancyMap(const MetaWord* reference_address, size_t word_size, size_t smallest_chunk_word_size) :
+    _reference_address(reference_address), _word_size(word_size),
+    _smallest_chunk_word_size(smallest_chunk_word_size) {
+    assert(reference_address != NULL, "invalid reference address");
+    assert(is_aligned(reference_address, smallest_chunk_word_size),
+           "Reference address not aligned to smallest chunk size.");
+    assert(is_aligned(word_size, smallest_chunk_word_size),
+           "Word_size shall be a multiple of the smallest chunk size.");
+    // Calculate bitmap size: one bit per smallest_chunk_word_size'd area.
+    size_t num_bits = word_size / smallest_chunk_word_size;
+    _map_size = (num_bits + 7) / 8;
+    assert(_map_size * 8 >= num_bits, "sanity");
+    _map[0] = (uint8_t*) os::malloc(_map_size, mtInternal);
+    _map[1] = (uint8_t*) os::malloc(_map_size, mtInternal);
+    assert(_map[0] != NULL && _map[1] != NULL, "Occupancy Map: allocation failed.");
+    memset(_map[1], 0, _map_size);
+    memset(_map[0], 0, _map_size);
+    // Sanity test: the first respectively last possible chunk start address in
+    // the covered range shall map to the first and last bit in the bitmap.
+    assert(get_bitpos_for_address(reference_address) == 0,
+      "First chunk address in range must map to fist bit in bitmap.");
+    assert(get_bitpos_for_address(reference_address + word_size - smallest_chunk_word_size) == num_bits - 1,
+      "Last chunk address in range must map to last bit in bitmap.");
+  }
+
+  ~OccupancyMap() {
+    os::free(_map[0]);
+    os::free(_map[1]);
+  }
+
+  // Returns true if at address x a chunk is starting.
+  bool chunk_starts_at_address(MetaWord* p) const {
+    const unsigned pos = get_bitpos_for_address(p);
+    return get_bit_at_position(pos, layer_chunk_start_map);
+  }
+
+  void set_chunk_starts_at_address(MetaWord* p, bool v) {
+    const unsigned pos = get_bitpos_for_address(p);
+    set_bit_at_position(pos, layer_chunk_start_map, v);
+  }
+
+  // Removes all chunk-start-bits inside a region, typically as a
+  // result of a chunk merge.
+  void wipe_chunk_start_bits_in_region(MetaWord* p, size_t word_size) {
+    set_bits_of_region(p, word_size, layer_chunk_start_map, false);
+  }
+
+  // Returns true if there are life (in use) chunks in the region limited
+  // by [p, p+word_size).
+  bool is_region_in_use(MetaWord* p, size_t word_size) const {
+    return is_any_bit_set_in_region(p, word_size, layer_in_use_map);
+  }
+
+  // Marks the region starting at p with the size word_size as in use
+  // or free, depending on v.
+  void set_region_in_use(MetaWord* p, size_t word_size, bool v) {
+    set_bits_of_region(p, word_size, layer_in_use_map, v);
+  }
+
+#ifdef ASSERT
+  // Verify occupancy map for the address range [from, to).
+  // We need to tell it the address range, because the memory the
+  // occupancy map is covering may not be fully comitted yet.
+  void verify(MetaWord* from, MetaWord* to) {
+    Metachunk* chunk = NULL;
+    int nth_bit_for_chunk = 0;
+    MetaWord* chunk_end = NULL;
+    for (MetaWord* p = from; p < to; p += _smallest_chunk_word_size) {
+      const unsigned pos = get_bitpos_for_address(p);
+      // Check the chunk-starts-info:
+      if (get_bit_at_position(pos, layer_chunk_start_map)) {
+        // Chunk start marked in bitmap.
+        chunk = (Metachunk*) p;
+        if (chunk_end != NULL) {
+          assert(chunk_end == p, "Unexpected chunk start found at %p (expected "
+                 "the next chunk to start at %p).", p, chunk_end);
+        }
+        assert(chunk->is_valid_sentinel(), "Invalid chunk at address %p.", p);
+        if (chunk->get_chunk_type() != HumongousIndex) {
+          guarantee(is_aligned(p, chunk->word_size()), "Chunk %p not aligned.", p);
+        }
+        chunk_end = p + chunk->word_size();
+        nth_bit_for_chunk = 0;
+        assert(chunk_end <= to, "Chunk end overlaps test address range.");
+      } else {
+        // No chunk start marked in bitmap.
+        assert(chunk != NULL, "Chunk should start at start of address range.");
+        assert(p < chunk_end, "Did not find expected chunk start at %p.", p);
+        nth_bit_for_chunk ++;
+      }
+      // Check the in-use-info:
+      const bool in_use_bit = get_bit_at_position(pos, layer_in_use_map);
+      if (in_use_bit) {
+        assert(!chunk->is_tagged_free(), "Chunk %p: marked in-use in map but is free (bit %u).",
+               chunk, nth_bit_for_chunk);
+      } else {
+        assert(chunk->is_tagged_free(), "Chunk %p: marked free in map but is in use (bit %u).",
+               chunk, nth_bit_for_chunk);
+      }
+    }
+  }
+
+  // Verify that a given chunk is correctly accounted for in the bitmap.
+  void verify_for_chunk(Metachunk* chunk) {
+    assert(chunk_starts_at_address((MetaWord*) chunk),
+           "No chunk start marked in map for chunk %p.", chunk);
+    // For chunks larger than the minimal chunk size, no other chunk
+    // must start in its area.
+    if (chunk->word_size() > _smallest_chunk_word_size) {
+      assert(!is_any_bit_set_in_region(((MetaWord*) chunk) + _smallest_chunk_word_size,
+                                       chunk->word_size() - _smallest_chunk_word_size, layer_chunk_start_map),
+             "No chunk must start within another chunk.");
+    }
+    if (!chunk->is_tagged_free()) {
+      assert(is_region_in_use((MetaWord*)chunk, chunk->word_size()),
+             "Chunk %p is in use but marked as free in map (%d %d).",
+             chunk, chunk->get_chunk_type(), chunk->get_origin());
+    } else {
+      assert(!is_region_in_use((MetaWord*)chunk, chunk->word_size()),
+             "Chunk %p is free but marked as in-use in map (%d %d).",
+             chunk, chunk->get_chunk_type(), chunk->get_origin());
+    }
+  }
+
+#endif // ASSERT
+
+};
+
 // A VirtualSpaceList node.
 class VirtualSpaceNode : public CHeapObj<mtClass> {
   friend class VirtualSpaceList;
@@ -398,6 +756,9 @@
   // Link to next VirtualSpaceNode
   VirtualSpaceNode* _next;
 
+  // Whether this node is contained in class or metaspace.
+  const bool _is_class;
+
   // total in the VirtualSpace
   MemRegion _reserved;
   ReservedSpace _rs;
@@ -406,6 +767,8 @@
   // count of chunks contained in this VirtualSpace
   uintx _container_count;
 
+  OccupancyMap* _occupancy_map;
+
   // Convenience functions to access the _virtual_space
   char* low()  const { return virtual_space()->low(); }
   char* high() const { return virtual_space()->high(); }
@@ -416,16 +779,28 @@
 
   // Committed but unused space in the virtual space
   size_t free_words_in_vs() const;
+
+  // True if this node belongs to class metaspace.
+  bool is_class() const { return _is_class; }
+
+  // Helper function for take_from_committed: allocate padding chunks
+  // until top is at the given address.
+  void allocate_padding_chunks_until_top_is_at(MetaWord* target_top);
+
  public:
 
-  VirtualSpaceNode(size_t byte_size);
-  VirtualSpaceNode(ReservedSpace rs) : _top(NULL), _next(NULL), _rs(rs), _container_count(0) {}
+  VirtualSpaceNode(bool is_class, size_t byte_size);
+  VirtualSpaceNode(bool is_class, ReservedSpace rs) :
+    _is_class(is_class), _top(NULL), _next(NULL), _rs(rs), _container_count(0), _occupancy_map(NULL) {}
   ~VirtualSpaceNode();
 
   // Convenience functions for logical bottom and end
   MetaWord* bottom() const { return (MetaWord*) _virtual_space.low(); }
   MetaWord* end() const { return (MetaWord*) _virtual_space.high(); }
 
+  const OccupancyMap* occupancy_map() const { return _occupancy_map; }
+  OccupancyMap* occupancy_map() { return _occupancy_map; }
+
   bool contains(const void* ptr) { return ptr >= low() && ptr < high(); }
 
   size_t reserved_words() const  { return _virtual_space.reserved_size() / BytesPerWord; }
@@ -486,13 +861,18 @@
   // the smallest chunk size.
   void retire(ChunkManager* chunk_manager);
 
-#ifdef ASSERT
-  // Debug support
-  void mangle();
-#endif
 
   void print_on(outputStream* st) const;
   void print_map(outputStream* st, bool is_class) const;
+
+  // Debug support
+  DEBUG_ONLY(void mangle();)
+  // Verify counters, all chunks in this list node and the occupancy map.
+  DEBUG_ONLY(void verify();)
+  // Verify that all free chunks in this node are ideally merged
+  // (there not should be multiple small chunks where a large chunk could exist.)
+  DEBUG_ONLY(void verify_free_chunks_are_ideally_merged();)
+
 };
 
 #define assert_is_aligned(value, alignment)                  \
@@ -515,7 +895,8 @@
 }
 
   // byte_size is the size of the associated virtualspace.
-VirtualSpaceNode::VirtualSpaceNode(size_t bytes) : _top(NULL), _next(NULL), _rs(), _container_count(0) {
+VirtualSpaceNode::VirtualSpaceNode(bool is_class, size_t bytes) :
+  _is_class(is_class), _top(NULL), _next(NULL), _rs(), _container_count(0), _occupancy_map(NULL) {
   assert_is_aligned(bytes, Metaspace::reserve_alignment());
   bool large_pages = should_commit_large_pages_when_reserving(bytes);
   _rs = ReservedSpace(bytes, Metaspace::reserve_alignment(), large_pages);
@@ -531,12 +912,14 @@
 }
 
 void VirtualSpaceNode::purge(ChunkManager* chunk_manager) {
+  DEBUG_ONLY(this->verify();)
   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);
+    chunk->remove_sentinel();
     assert(chunk->next() == NULL &&
            chunk->prev() == NULL,
            "Was not removed from its list");
@@ -546,23 +929,10 @@
 
 void VirtualSpaceNode::print_map(outputStream* st, bool is_class) const {
 
-  // Format:
-  // <ptr>
-  // <ptr>  . .. .               .  ..
-  //        SSxSSMMMMMMMMMMMMMMMMsssXX
-  //        112114444444444444444
-  // <ptr>  . .. .               .  ..
-  //        SSxSSMMMMMMMMMMMMMMMMsssXX
-  //        112114444444444444444
-
   if (bottom() == top()) {
     return;
   }
 
-  // First line: dividers for every med-chunk-sized interval
-  // Second line: a dot for the start of a chunk
-  // Third line: a letter per chunk type (x,s,m,h), uppercase if in use.
-
   const size_t spec_chunk_size = is_class ? ClassSpecializedChunk : SpecializedChunk;
   const size_t small_chunk_size = is_class ? ClassSmallChunk : SmallChunk;
   const size_t med_chunk_size = is_class ? ClassMediumChunk : MediumChunk;
@@ -571,9 +941,12 @@
   const size_t section_len = align_up(spec_chunk_size * line_len, med_chunk_size);
   line_len = (int)(section_len / spec_chunk_size);
 
-  char* line1 = (char*)os::malloc(line_len, mtInternal);
-  char* line2 = (char*)os::malloc(line_len, mtInternal);
-  char* line3 = (char*)os::malloc(line_len, mtInternal);
+  static const int NUM_LINES = 4;
+
+  char* lines[NUM_LINES];
+  for (int i = 0; i < NUM_LINES; i ++) {
+    lines[i] = (char*)os::malloc(line_len, mtInternal);
+  }
   int pos = 0;
   const MetaWord* p = bottom();
   const Metachunk* chunk = (const Metachunk*)p;
@@ -581,12 +954,11 @@
   while (p < top()) {
     if (pos == line_len) {
       pos = 0;
-      st->fill_to(22);
-      st->print_raw(line1, line_len);
-      st->cr();
-      st->fill_to(22);
-      st->print_raw(line2, line_len);
-      st->cr();
+      for (int i = 0; i < NUM_LINES; i ++) {
+        st->fill_to(22);
+        st->print_raw(lines[i], line_len);
+        st->cr();
+      }
     }
     if (pos == 0) {
       st->print(PTR_FORMAT ":", p2i(p));
@@ -595,40 +967,45 @@
       chunk = (Metachunk*)p;
       chunk_end = p + chunk->word_size();
     }
-    if (p == (const MetaWord*)chunk) {
-      // chunk starts.
-      line1[pos] = '.';
-    } else {
-      line1[pos] = ' ';
-    }
+    // line 1: chunk starting points (a dot if that area is a chunk start).
+    lines[0][pos] = p == (const MetaWord*)chunk ? '.' : ' ';
+
     // Line 2: chunk type (x=spec, s=small, m=medium, h=humongous), uppercase if
     // chunk is in use.
     const bool chunk_is_free = ((Metachunk*)chunk)->is_tagged_free();
     if (chunk->word_size() == spec_chunk_size) {
-      line2[pos] = chunk_is_free ? 'x' : 'X';
+      lines[1][pos] = chunk_is_free ? 'x' : 'X';
     } else if (chunk->word_size() == small_chunk_size) {
-      line2[pos] = chunk_is_free ? 's' : 'S';
+      lines[1][pos] = chunk_is_free ? 's' : 'S';
     } else if (chunk->word_size() == med_chunk_size) {
-      line2[pos] = chunk_is_free ? 'm' : 'M';
-   } else if (chunk->word_size() > med_chunk_size) {
-      line2[pos] = chunk_is_free ? 'h' : 'H';
+      lines[1][pos] = chunk_is_free ? 'm' : 'M';
+    } else if (chunk->word_size() > med_chunk_size) {
+      lines[1][pos] = chunk_is_free ? 'h' : 'H';
     } else {
       ShouldNotReachHere();
     }
+
+    // Line 3: chunk origin
+    const ChunkOrigin origin = chunk->get_origin();
+    lines[2][pos] = origin == origin_normal ? ' ' : '0' + (int) origin;
+
+    // Line 4: Virgin chunk? Virgin chunks are chunks created as a byproduct of padding or splitting,
+    //         but were never used.
+    lines[3][pos] = chunk->get_use_count() > 0 ? ' ' : 'v';
+
     p += spec_chunk_size;
     pos ++;
   }
   if (pos > 0) {
-    st->fill_to(22);
-    st->print_raw(line1, pos);
-    st->cr();
-    st->fill_to(22);
-    st->print_raw(line2, pos);
-    st->cr();
-  }
-  os::free(line1);
-  os::free(line2);
-  os::free(line3);
+    for (int i = 0; i < NUM_LINES; i ++) {
+      st->fill_to(22);
+      st->print_raw(lines[i], line_len);
+      st->cr();
+    }
+  }
+  for (int i = 0; i < NUM_LINES; i ++) {
+    os::free(lines[i]);
+  }
 }
 
 
@@ -639,6 +1016,7 @@
   Metachunk* invalid_chunk = (Metachunk*) top();
   while (chunk < invalid_chunk ) {
     MetaWord* next = ((MetaWord*)chunk) + chunk->word_size();
+    do_verify_chunk(chunk);
     // Don't count the chunks on the free lists.  Those are
     // still part of the VirtualSpaceNode but not currently
     // counted.
@@ -651,6 +1029,77 @@
 }
 #endif
 
+#ifdef ASSERT
+// Verify counters, all chunks in this list node and the occupancy map.
+void VirtualSpaceNode::verify() {
+  uintx num_in_use_chunks = 0;
+  Metachunk* chunk = first_chunk();
+  Metachunk* invalid_chunk = (Metachunk*) top();
+
+  // Iterate the chunks in this node and verify each chunk.
+  while (chunk < invalid_chunk ) {
+    DEBUG_ONLY(do_verify_chunk(chunk);)
+    if (!chunk->is_tagged_free()) {
+      num_in_use_chunks ++;
+    }
+    MetaWord* next = ((MetaWord*)chunk) + chunk->word_size();
+    chunk = (Metachunk*) next;
+  }
+  assert(_container_count == num_in_use_chunks, "Container count mismatch (real: " UINTX_FORMAT
+         ", counter: " UINTX_FORMAT ".", num_in_use_chunks, _container_count);
+  // Also verify the occupancy map.
+  occupancy_map()->verify(this->bottom(), this->top());
+}
+#endif // ASSERT
+
+#ifdef ASSERT
+// Verify that all free chunks in this node are ideally merged
+// (there not should be multiple small chunks where a large chunk could exist.)
+void VirtualSpaceNode::verify_free_chunks_are_ideally_merged() {
+  Metachunk* chunk = first_chunk();
+  Metachunk* invalid_chunk = (Metachunk*) top();
+  // Shorthands.
+  const size_t size_med = (is_class() ? ClassMediumChunk : MediumChunk) * BytesPerWord;
+  const size_t size_small = (is_class() ? ClassSmallChunk : SmallChunk) * BytesPerWord;
+  int num_free_chunks_since_last_med_boundary = -1;
+  int num_free_chunks_since_last_small_boundary = -1;
+  while (chunk < invalid_chunk ) {
+    // Test for missed chunk merge opportunities: count number of free chunks since last chunk boundary.
+    // Reset the counter when encountering a non-free chunk.
+    if (chunk->get_chunk_type() != HumongousIndex) {
+      if (chunk->is_tagged_free()) {
+        // Count successive free, non-humongous chunks.
+        if (is_aligned(chunk, size_small)) {
+          assert(num_free_chunks_since_last_small_boundary <= 1,
+                 "Missed chunk merge opportunity at " PTR_FORMAT " for chunk size " SIZE_FORMAT_HEX ".", p2i(chunk) - size_small, size_small);
+          num_free_chunks_since_last_small_boundary = 0;
+        } else if (num_free_chunks_since_last_small_boundary != -1) {
+          num_free_chunks_since_last_small_boundary ++;
+        }
+        if (is_aligned(chunk, size_med)) {
+          assert(num_free_chunks_since_last_med_boundary <= 1,
+                 "Missed chunk merge opportunity at " PTR_FORMAT " for chunk size " SIZE_FORMAT_HEX ".", p2i(chunk) - size_med, size_med);
+          num_free_chunks_since_last_med_boundary = 0;
+        } else if (num_free_chunks_since_last_med_boundary != -1) {
+          num_free_chunks_since_last_med_boundary ++;
+        }
+      } else {
+        // Encountering a non-free chunk, reset counters.
+        num_free_chunks_since_last_med_boundary = -1;
+        num_free_chunks_since_last_small_boundary = -1;
+      }
+    } else {
+      // One cannot merge areas with a humongous chunk in the middle. Reset counters.
+      num_free_chunks_since_last_med_boundary = -1;
+      num_free_chunks_since_last_small_boundary = -1;
+    }
+
+    MetaWord* next = ((MetaWord*)chunk) + chunk->word_size();
+    chunk = (Metachunk*) next;
+  }
+}
+#endif // ASSERT
+
 // List of VirtualSpaces for metadata allocation.
 class VirtualSpaceList : public CHeapObj<mtClass> {
   friend class VirtualSpaceNode;
@@ -922,8 +1371,6 @@
   // Block allocation and deallocation.
   // Allocates a block from the current chunk
   MetaWord* allocate(size_t word_size);
-  // Allocates a block from a small chunk
-  MetaWord* get_small_chunk_and_allocate(size_t word_size);
 
   // Helper for allocations
   MetaWord* allocate_work(size_t word_size);
@@ -1078,6 +1525,9 @@
 
 VirtualSpaceNode::~VirtualSpaceNode() {
   _rs.release();
+  if (_occupancy_map != NULL) {
+    delete _occupancy_map;
+  }
 #ifdef ASSERT
   size_t word_size = sizeof(*this) / BytesPerWord;
   Copy::fill_to_words((HeapWord*) this, word_size, 0xf1f1f1f1);
@@ -1097,10 +1547,120 @@
   return pointer_delta(end(), top(), sizeof(MetaWord));
 }
 
+// Given an address larger than top(), allocate padding chunks until top is at the given address.
+void VirtualSpaceNode::allocate_padding_chunks_until_top_is_at(MetaWord* target_top) {
+
+  assert(target_top > top(), "Sanity");
+
+  // Padding chunks are added to the freelist.
+  ChunkManager* const chunk_manager = Metaspace::get_chunk_manager(this->is_class());
+
+  // shorthands
+  const size_t spec_word_size = chunk_manager->specialized_chunk_word_size();
+  const size_t small_word_size = chunk_manager->small_chunk_word_size();
+  const size_t med_word_size = chunk_manager->medium_chunk_word_size();
+
+  while (top() < target_top) {
+
+    // We could make this coding more generic, but right now we only deal with two possible chunk sizes
+    // for padding chunks, so it is not worth it.
+    size_t padding_chunk_word_size = small_word_size;
+    if (is_aligned(top(), small_word_size * sizeof(MetaWord)) == false) {
+      assert_is_aligned(top(), spec_word_size * sizeof(MetaWord)); // Should always hold true.
+      padding_chunk_word_size = spec_word_size;
+    }
+    MetaWord* here = top();
+    assert_is_aligned(here, padding_chunk_word_size * sizeof(MetaWord));
+    inc_top(padding_chunk_word_size);
+
+    // Create new padding chunk.
+    ChunkIndex padding_chunk_type = get_chunk_type_by_size(padding_chunk_word_size, is_class());
+    assert(padding_chunk_type == SpecializedIndex || padding_chunk_type == SmallIndex, "sanity");
+
+    Metachunk* const padding_chunk =
+      ::new (here) Metachunk(padding_chunk_type, is_class(), padding_chunk_word_size, this);
+    assert(padding_chunk == (Metachunk*)here, "Sanity");
+    DEBUG_ONLY(padding_chunk->set_origin(origin_pad);)
+    log_trace(gc, metaspace, freelist)("Created padding chunk in %s at "
+                                       PTR_FORMAT ", size " SIZE_FORMAT_HEX ".",
+                                       (is_class() ? "class space " : "metaspace"),
+                                       p2i(padding_chunk), padding_chunk->word_size() * sizeof(MetaWord));
+
+    // Mark chunk start in occupancy map.
+    occupancy_map()->set_chunk_starts_at_address((MetaWord*)padding_chunk, true);
+
+    // Chunks are born as in-use (see MetaChunk ctor). So, before returning
+    // the padding chunk to its chunk manager, mark it as in use (ChunkManager
+    // will assert that).
+    do_update_in_use_info_for_chunk(padding_chunk, true);
+
+    // Return Chunk to freelist.
+    inc_container_count();
+    chunk_manager->return_single_chunk(padding_chunk_type, padding_chunk);
+    // Please note: at this point, ChunkManager::return_single_chunk()
+    // may already have merged the padding chunk with neighboring chunks, so
+    // it may have vanished at this point. Do not reference the padding
+    // chunk beyond this point.
+  }
+
+  assert(top() == target_top, "Sanity");
+
+} // allocate_padding_chunks_until_top_is_at()
+
 // Allocates the chunk from the virtual space only.
 // This interface is also used internally for debugging.  Not all
 // chunks removed here are necessarily used for allocation.
 Metachunk* VirtualSpaceNode::take_from_committed(size_t chunk_word_size) {
+  // Non-humongous chunks are to be allocated aligned to their chunk
+  // size. So, start addresses of medium chunks are aligned to medium
+  // chunk size, those of small chunks to small chunk size and so
+  // forth. This facilitates merging of free chunks and reduces
+  // fragmentation. Chunk sizes are spec < small < medium, with each
+  // larger chunk size being a multiple of the next smaller chunk
+  // size.
+  // Because of this alignment, me may need to create a number of padding
+  // chunks. These chunks are created and added to the freelist.
+
+  // The chunk manager to which we will give our padding chunks.
+  ChunkManager* const chunk_manager = Metaspace::get_chunk_manager(this->is_class());
+
+  // shorthands
+  const size_t spec_word_size = chunk_manager->specialized_chunk_word_size();
+  const size_t small_word_size = chunk_manager->small_chunk_word_size();
+  const size_t med_word_size = chunk_manager->medium_chunk_word_size();
+
+  assert(chunk_word_size == spec_word_size || chunk_word_size == small_word_size ||
+         chunk_word_size >= med_word_size, "Invalid chunk size requested.");
+
+  // Chunk alignment (in bytes) == chunk size unless humongous.
+  // Humongous chunks are aligned to the smallest chunk size (spec).
+  const size_t required_chunk_alignment = (chunk_word_size > med_word_size ?
+                                           spec_word_size : chunk_word_size) * sizeof(MetaWord);
+
+  // Do we have enough space to create the requested chunk plus
+  // any padding chunks needed?
+  MetaWord* const next_aligned =
+    static_cast<MetaWord*>(align_up(top(), required_chunk_alignment));
+  if (!is_available((next_aligned - top()) + chunk_word_size)) {
+    return NULL;
+  }
+
+  // Before allocating the requested chunk, allocate padding chunks if necessary.
+  // We only need to do this for small or medium chunks: specialized chunks are the
+  // smallest size, hence always aligned. Homungous chunks are allocated unaligned
+  // (implicitly, also aligned to smallest chunk size).
+  if ((chunk_word_size == med_word_size || chunk_word_size == small_word_size) && next_aligned > top())  {
+    log_trace(gc, metaspace, freelist)("Creating padding chunks in %s between %p and %p...",
+        (is_class() ? "class space " : "metaspace"),
+        top(), next_aligned);
+    allocate_padding_chunks_until_top_is_at(next_aligned);
+    // Now, top should be aligned correctly.
+    assert_is_aligned(top(), required_chunk_alignment);
+  }
+
+  // Now, top should be aligned correctly.
+  assert_is_aligned(top(), required_chunk_alignment);
+
   // Bottom of the new chunk
   MetaWord* chunk_limit = top();
   assert(chunk_limit != NULL, "Not safe to call this method");
@@ -1126,7 +1686,20 @@
   inc_top(chunk_word_size);
 
   // Initialize the chunk
-  Metachunk* result = ::new (chunk_limit) Metachunk(chunk_word_size, this);
+  ChunkIndex chunk_type = get_chunk_type_by_size(chunk_word_size, is_class());
+  Metachunk* result = ::new (chunk_limit) Metachunk(chunk_type, is_class(), chunk_word_size, this);
+  assert(result == (Metachunk*)chunk_limit, "Sanity");
+  occupancy_map()->set_chunk_starts_at_address((MetaWord*)result, true);
+  do_update_in_use_info_for_chunk(result, true);
+
+  inc_container_count();
+
+  DEBUG_ONLY(chunk_manager->locked_verify());
+  DEBUG_ONLY(this->verify());
+  DEBUG_ONLY(do_verify_chunk(result));
+
+  result->inc_use_count();
+
   return result;
 }
 
@@ -1145,6 +1718,14 @@
   size_t commit = MIN2(preferred_bytes, uncommitted);
   bool result = virtual_space()->expand_by(commit, false);
 
+  if (result) {
+    log_trace(gc, metaspace, freelist)("Expanded %s virtual space list node by " SIZE_FORMAT " words.",
+              (is_class() ? "class" : "non-class"), commit);
+  } else {
+    log_trace(gc, metaspace, freelist)("Failed to expand %s virtual space list node by " SIZE_FORMAT " words.",
+              (is_class() ? "class" : "non-class"), commit);
+  }
+
   assert(result, "Failed to commit memory");
 
   return result;
@@ -1153,9 +1734,6 @@
 Metachunk* VirtualSpaceNode::get_chunk_vs(size_t chunk_word_size) {
   assert_lock_strong(SpaceManager::expand_lock());
   Metachunk* result = take_from_committed(chunk_word_size);
-  if (result != NULL) {
-    inc_container_count();
-  }
   return result;
 }
 
@@ -1195,6 +1773,10 @@
            _rs.size() / BytesPerWord);
   }
 
+  // Initialize Occupancy Map.
+  const size_t smallest_chunk_size = is_class() ? ClassSpecializedChunk : SpecializedChunk;
+  _occupancy_map = new OccupancyMap(bottom(), reserved_words(), smallest_chunk_size);
+
   return result;
 }
 
@@ -1279,6 +1861,133 @@
   account_for_removed_chunk(chunk);
 }
 
+bool ChunkManager::attempt_to_coalesce_around_chunk(Metachunk* chunk, ChunkIndex target_chunk_type) {
+  assert_lock_strong(SpaceManager::expand_lock());
+  assert(chunk != NULL, "invalid chunk pointer");
+  // Check for valid merge combinations.
+  assert((chunk->get_chunk_type() == SpecializedIndex &&
+          (target_chunk_type == SmallIndex || target_chunk_type == MediumIndex)) ||
+         (chunk->get_chunk_type() == SmallIndex && target_chunk_type == MediumIndex),
+        "Invalid chunk merge combination.");
+
+  const size_t target_chunk_word_size =
+    get_size_for_nonhumongous_chunktype(target_chunk_type, this->is_class());
+
+  // [ prospective merge region )
+  MetaWord* const p_merge_region_start =
+    (MetaWord*) align_down(chunk, target_chunk_word_size * sizeof(MetaWord));
+  MetaWord* const p_merge_region_end =
+    p_merge_region_start + target_chunk_word_size;
+
+  // We need the VirtualSpaceNode containing this chunk and its occupancy map.
+  VirtualSpaceNode* const vsn = chunk->container();
+  OccupancyMap* const ocmap = vsn->occupancy_map();
+
+  // The prospective chunk merge range must be completely contained by the
+  // committed range of the virtual space node.
+  if (p_merge_region_start < vsn->bottom() || p_merge_region_end > vsn->top()) {
+    return false;
+  }
+
+  // Only attempt to merge this range if at its start a chunk starts and at its end
+  // a chunk ends. If a chunk (can only be humongous) straddles either start or end
+  // of that range, we cannot merge.
+  if (!ocmap->chunk_starts_at_address(p_merge_region_start)) {
+    return false;
+  }
+  if (p_merge_region_end < vsn->top() &&
+      !ocmap->chunk_starts_at_address(p_merge_region_end)) {
+    return false;
+  }
+
+  // Now check if the prospective merge area contains live chunks. If it does we cannot merge.
+  if (ocmap->is_region_in_use(p_merge_region_start, target_chunk_word_size)) {
+    return false;
+  }
+
+  // Success! Remove all chunks in this region...
+  log_trace(gc, metaspace, freelist)("%s: coalescing chunks in area [%p-%p)...",
+    (is_class() ? "class space" : "metaspace"),
+    p_merge_region_start, p_merge_region_end);
+
+  const int num_chunks_removed =
+    remove_chunks_in_area(p_merge_region_start, target_chunk_word_size);
+
+  // ... and create a single new bigger chunk.
+  Metachunk* const p_new_chunk =
+      ::new (p_merge_region_start) Metachunk(target_chunk_type, is_class(), target_chunk_word_size, vsn);
+  assert(p_new_chunk == (Metachunk*)p_merge_region_start, "Sanity");
+  p_new_chunk->set_origin(origin_merge);
+
+  log_trace(gc, metaspace, freelist)("%s: created coalesced chunk at %p, size " SIZE_FORMAT_HEX ".",
+    (is_class() ? "class space" : "metaspace"),
+    p_new_chunk, p_new_chunk->word_size() * sizeof(MetaWord));
+
+  // Fix occupancy map: remove old start bits of the small chunks and set new start bit.
+  ocmap->wipe_chunk_start_bits_in_region(p_merge_region_start, target_chunk_word_size);
+  ocmap->set_chunk_starts_at_address(p_merge_region_start, true);
+
+  // Mark chunk as free. Note: it is not necessary to update the occupancy
+  // map in-use map, because the old chunks were also free, so nothing
+  // should have changed.
+  p_new_chunk->set_is_tagged_free(true);
+
+  // Add new chunk to its freelist.
+  ChunkList* const list = free_chunks(target_chunk_type);
+  list->return_chunk_at_head(p_new_chunk);
+
+  // And adjust ChunkManager:: _free_chunks_count (_free_chunks_total
+  // should not have changed, because the size of the space should be the same)
+  _free_chunks_count -= num_chunks_removed;
+  _free_chunks_count ++;
+
+  // VirtualSpaceNode::container_count does not have to be modified:
+  // it means "number of active (non-free) chunks", so merging free chunks
+  // should not affect that count.
+
+  // At the end of a chunk merge, run verification tests.
+  DEBUG_ONLY(this->locked_verify());
+  DEBUG_ONLY(vsn->verify());
+
+  return true;
+}
+
+// Remove all chunks in the given area - the chunks are supposed to be free -
+// from their corresponding freelists. 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 ChunkManager::remove_chunks_in_area(MetaWord* p, size_t word_size) {
+  assert(p != NULL && word_size > 0, "Invalid range.");
+  const size_t smallest_chunk_size = get_size_for_nonhumongous_chunktype(SpecializedIndex, is_class());
+  assert_is_aligned(word_size, smallest_chunk_size);
+
+  Metachunk* const start = (Metachunk*) p;
+  const Metachunk* const end = (Metachunk*)(p + word_size);
+  Metachunk* cur = start;
+  int num_removed = 0;
+  while (cur < end) {
+    Metachunk* next = (Metachunk*)(((MetaWord*)cur) + cur->word_size());
+    DEBUG_ONLY(do_verify_chunk(cur));
+    assert(cur->get_chunk_type() != HumongousIndex, "Unexpected humongous chunk found at %p.", cur);
+    assert(cur->is_tagged_free(), "Chunk expected to be free (%p)", cur);
+    log_trace(gc, metaspace, freelist)("%s: removing chunk %p, size " SIZE_FORMAT_HEX ".",
+      (is_class() ? "class space" : "metaspace"),
+      cur, cur->word_size() * sizeof(MetaWord));
+    cur->remove_sentinel();
+    // Note: cannot call ChunkManager::remove_chunk, because that
+    // modifies the counters in ChunkManager, which we do not want. So
+    // we call remove_chunk on the freelist directly (see also the
+    // splitting function which does the same).
+    ChunkList* const list = free_chunks(list_index(cur->word_size()));
+    list->remove_chunk(cur);
+    num_removed ++;
+    cur = next;
+  }
+  return num_removed;
+}
+
 // Walk the list of VirtualSpaceNodes and delete
 // nodes with a 0 container_count.  Remove Metachunks in
 // the node from their respective freelists.
@@ -1297,6 +2006,8 @@
     // Don't free the current virtual space since it will likely
     // be needed soon.
     if (vsl->container_count() == 0 && vsl != current_virtual_space()) {
+      log_trace(gc, metaspace, freelist)("Purging VirtualSpaceNode " PTR_FORMAT " (capacity: " SIZE_FORMAT
+                                         ", used: " SIZE_FORMAT ").", p2i(vsl), vsl->capacity_words_in_vs(), vsl->used_words_in_vs());
       // Unlink it from the list
       if (prev_vsl == vsl) {
         // This is the case of the current node being the first node.
@@ -1358,14 +2069,22 @@
 
 void VirtualSpaceNode::retire(ChunkManager* chunk_manager) {
   DEBUG_ONLY(verify_container_count();)
+  assert(this->is_class() == chunk_manager->is_class(), "Wrong ChunkManager?");
   for (int i = (int)MediumIndex; i >= (int)ZeroIndex; --i) {
     ChunkIndex index = (ChunkIndex)i;
     size_t chunk_size = chunk_manager->size_by_index(index);
 
     while (free_words_in_vs() >= chunk_size) {
       Metachunk* chunk = get_chunk_vs(chunk_size);
-      assert(chunk != NULL, "allocation should have been successful");
-
+      // Chunk will be allocated aligned, so allocation may require
+      // additional padding chunks. That may cause above allocation to
+      // fail. Just ignore the failed allocation and continue with the
+      // next smaller chunk size. As the VirtualSpaceNode comitted
+      // size should be a multiple of the smallest chunk size, we
+      // should always be able to fill the VirtualSpace completely.
+      if (chunk == NULL) {
+        break;
+      }
       chunk_manager->return_single_chunk(index, chunk);
     }
     DEBUG_ONLY(verify_container_count();)
@@ -1394,7 +2113,7 @@
                                    _virtual_space_count(0) {
   MutexLockerEx cl(SpaceManager::expand_lock(),
                    Mutex::_no_safepoint_check_flag);
-  VirtualSpaceNode* class_entry = new VirtualSpaceNode(rs);
+  VirtualSpaceNode* class_entry = new VirtualSpaceNode(is_class(), rs);
   bool succeeded = class_entry->initialize();
   if (succeeded) {
     link_vs(class_entry);
@@ -1426,7 +2145,7 @@
   assert_is_aligned(vs_byte_size, Metaspace::reserve_alignment());
 
   // Allocate the meta virtual space and initialize it.
-  VirtualSpaceNode* new_entry = new VirtualSpaceNode(vs_byte_size);
+  VirtualSpaceNode* new_entry = new VirtualSpaceNode(is_class(), vs_byte_size);
   if (!new_entry->initialize()) {
     delete new_entry;
     return false;
@@ -1483,12 +2202,18 @@
   assert_is_aligned(preferred_words, Metaspace::commit_alignment_words());
   assert(min_words <= preferred_words, "Invalid arguments");
 
+  const char* const class_or_not = (is_class() ? "class" : "non-class");
+
   if (!MetaspaceGC::can_expand(min_words, this->is_class())) {
+    log_trace(gc, metaspace, freelist)("Cannot expand %s virtual space list.",
+              class_or_not);
     return  false;
   }
 
   size_t allowed_expansion_words = MetaspaceGC::allowed_expansion();
   if (allowed_expansion_words < min_words) {
+    log_trace(gc, metaspace, freelist)("Cannot expand %s virtual space list (must try gc first).",
+              class_or_not);
     return false;
   }
 
@@ -1499,8 +2224,12 @@
                                     min_words,
                                     max_expansion_words);
   if (vs_expanded) {
-    return true;
-  }
+     log_trace(gc, metaspace, freelist)("Expanded %s virtual space list.",
+               class_or_not);
+     return true;
+  }
+  log_trace(gc, metaspace, freelist)("%s virtual space list: retire current node.",
+            class_or_not);
   retire_current_virtual_space();
 
   // Get another virtual space.
@@ -1524,6 +2253,24 @@
   return false;
 }
 
+// Given a chunk, calculate the largest possible padding space which
+// could be required when allocating it.
+static size_t largest_possible_padding_size_for_chunk(size_t chunk_word_size, bool is_class) {
+  const ChunkIndex chunk_type = get_chunk_type_by_size(chunk_word_size, is_class);
+  if (chunk_type != HumongousIndex) {
+    // Normal, non-humongous chunks are allocated at chunk size
+    // boundaries, so the largest padding space required would be that
+    // minus the smallest chunk size.
+    const size_t smallest_chunk_size = is_class ? ClassSpecializedChunk : SpecializedChunk;
+    return chunk_word_size - smallest_chunk_size;
+  } else {
+    // Humongous chunks are allocated at smallest-chunksize
+    // boundaries, so there is no padding required.
+    return 0;
+  }
+}
+
+
 Metachunk* VirtualSpaceList::get_new_chunk(size_t chunk_word_size, size_t suggested_commit_granularity) {
 
   // Allocate a chunk out of the current virtual space.
@@ -1536,7 +2283,11 @@
   // The expand amount is currently only determined by the requested sizes
   // and not how much committed memory is left in the current virtual space.
 
-  size_t min_word_size       = align_up(chunk_word_size,              Metaspace::commit_alignment_words());
+  // We must have enough space for the requested size and any
+  // additional reqired padding chunks.
+  const size_t size_for_padding = largest_possible_padding_size_for_chunk(chunk_word_size, this->is_class());
+
+  size_t min_word_size       = align_up(chunk_word_size + size_for_padding, Metaspace::commit_alignment_words());
   size_t preferred_word_size = align_up(suggested_commit_granularity, Metaspace::commit_alignment_words());
   if (min_word_size >= preferred_word_size) {
     // Can happen when humongous chunks are allocated.
@@ -1676,6 +2427,8 @@
   if (is_class && Metaspace::using_class_space()) {
     size_t class_committed = MetaspaceAux::committed_bytes(Metaspace::ClassType);
     if (class_committed + word_size * BytesPerWord > CompressedClassSpaceSize) {
+      log_trace(gc, metaspace, freelist)("Cannot expand %s metaspace by " SIZE_FORMAT " words (CompressedClassSpaceSize = " SIZE_FORMAT " words)",
+                (is_class ? "class" : "non-class"), word_size, CompressedClassSpaceSize / sizeof(MetaWord));
       return false;
     }
   }
@@ -1683,6 +2436,8 @@
   // Check if the user has imposed a limit on the metaspace memory.
   size_t committed_bytes = MetaspaceAux::committed_bytes();
   if (committed_bytes + word_size * BytesPerWord > MaxMetaspaceSize) {
+    log_trace(gc, metaspace, freelist)("Cannot expand %s metaspace by " SIZE_FORMAT " words (MaxMetaspaceSize = " SIZE_FORMAT " words)",
+              (is_class ? "class" : "non-class"), word_size, MaxMetaspaceSize / sizeof(MetaWord));
     return false;
   }
 
@@ -1700,6 +2455,9 @@
   size_t left_until_max  = MaxMetaspaceSize - committed_bytes;
   size_t left_until_GC = capacity_until_gc - committed_bytes;
   size_t left_to_commit = MIN2(left_until_GC, left_until_max);
+  log_trace(gc, metaspace, freelist)("allowed expansion words: " SIZE_FORMAT
+            " (left_until_max: " SIZE_FORMAT ", left_until_GC: " SIZE_FORMAT ".",
+            left_to_commit / BytesPerWord, left_until_max / BytesPerWord, left_until_GC / BytesPerWord);
 
   return left_to_commit / BytesPerWord;
 }
@@ -1948,6 +2706,17 @@
 void ChunkManager::locked_verify() {
   locked_verify_free_chunks_count();
   locked_verify_free_chunks_total();
+  for (ChunkIndex i = ZeroIndex; i < NumberOfFreeLists; i = next_chunk_index(i)) {
+    ChunkList* list = free_chunks(i);
+    if (list != NULL) {
+      Metachunk* chunk = list->head();
+      while (chunk) {
+        DEBUG_ONLY(do_verify_chunk(chunk);)
+        assert(chunk->is_tagged_free(), "Chunk should be tagged as free.");
+        chunk = chunk->next();
+      }
+    }
+  }
 }
 
 void ChunkManager::locked_print_free_chunks(outputStream* st) {
@@ -2007,27 +2776,173 @@
   return free_chunks(index);
 }
 
+// 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* ChunkManager::split_chunk(size_t target_chunk_word_size, Metachunk* larger_chunk) {
+  assert(larger_chunk->word_size() > target_chunk_word_size, "Sanity");
+
+  const ChunkIndex larger_chunk_index = larger_chunk->get_chunk_type();
+  const ChunkIndex target_chunk_index = get_chunk_type_by_size(target_chunk_word_size, is_class());
+
+  MetaWord* const region_start = (MetaWord*)larger_chunk;
+  const size_t region_word_len = larger_chunk->word_size();
+  MetaWord* const region_end = region_start + region_word_len;
+  VirtualSpaceNode* const vsn = larger_chunk->container();
+  OccupancyMap* const ocmap = vsn->occupancy_map();
+
+  // Any larger non-humongous chunk size is a multiple of any smaller chunk size.
+  // Since non-humongous chunks are aligned to their chunk size, the larger chunk should start
+  // at an address suitable to place the smaller target chunk.
+  assert_is_aligned(region_start, target_chunk_word_size);
+
+  // Remove old chunk.
+  free_chunks(larger_chunk_index)->remove_chunk(larger_chunk);
+  larger_chunk->remove_sentinel();
+
+  // Prevent access to the old chunk from here on.
+  larger_chunk = NULL;
+  // ... and wipe it.
+  DEBUG_ONLY(memset(region_start, 0xfe, region_word_len * BytesPerWord));
+
+  // In its place create first the target chunk...
+  MetaWord* p = region_start;
+  Metachunk* target_chunk = ::new (p) Metachunk(target_chunk_index, is_class(), target_chunk_word_size, vsn);
+  assert(target_chunk == (Metachunk*)p, "Sanity");
+  target_chunk->set_origin(origin_split);
+
+  // Note: we do not need to mark its start in the occupancy map
+  // because it coincides with the old chunk start.
+
+  // Mark chunk as free and return to the freelist.
+  do_update_in_use_info_for_chunk(target_chunk, false);
+  free_chunks(target_chunk_index)->return_chunk_at_head(target_chunk);
+
+  // This chunk should now be valid and can be verified.
+  DEBUG_ONLY(do_verify_chunk(target_chunk));
+
+  // In the remaining space create the remainder chunks.
+  p += target_chunk->word_size();
+  assert(p < region_end, "Sanity");
+
+  while (p < region_end) {
+
+    // Find the largest chunk size which fits the alignment requirements at address p.
+    ChunkIndex this_chunk_index = prev_chunk_index(larger_chunk_index);
+    size_t this_chunk_word_size = 0;
+    for(;;) {
+      this_chunk_word_size = get_size_for_nonhumongous_chunktype(this_chunk_index, is_class());
+      if (is_aligned(p, this_chunk_word_size * BytesPerWord)) {
+        break;
+      } else {
+        this_chunk_index = prev_chunk_index(this_chunk_index);
+        assert(this_chunk_index >= target_chunk_index, "Sanity");
+      }
+    }
+
+    assert(this_chunk_word_size >= target_chunk_word_size, "Sanity");
+    assert(is_aligned(p, this_chunk_word_size * BytesPerWord), "Sanity");
+    assert(p + this_chunk_word_size <= region_end, "Sanity");
+
+    // Create splitting chunk.
+    Metachunk* this_chunk = ::new (p) Metachunk(this_chunk_index, is_class(), this_chunk_word_size, vsn);
+    assert(this_chunk == (Metachunk*)p, "Sanity");
+    this_chunk->set_origin(origin_split);
+    ocmap->set_chunk_starts_at_address(p, true);
+    do_update_in_use_info_for_chunk(this_chunk, false);
+
+    // This chunk should be valid and can be verified.
+    DEBUG_ONLY(do_verify_chunk(this_chunk));
+
+    // Return this chunk to freelist and correct counter.
+    free_chunks(this_chunk_index)->return_chunk_at_head(this_chunk);
+    _free_chunks_count ++;
+
+    log_trace(gc, metaspace, freelist)("Created chunk at " PTR_FORMAT ", word size "
+      SIZE_FORMAT_HEX " (%s), in split region [" PTR_FORMAT "..." PTR_FORMAT ").",
+      p2i(this_chunk), this_chunk->word_size(), chunk_size_name(this_chunk_index),
+      p2i(region_start), p2i(region_end));
+
+    p += this_chunk_word_size;
+
+  }
+
+  return target_chunk;
+}
+
 Metachunk* ChunkManager::free_chunks_get(size_t word_size) {
   assert_lock_strong(SpaceManager::expand_lock());
 
   slow_locked_verify();
 
   Metachunk* chunk = NULL;
+  bool we_did_split_a_chunk = false;
+
   if (list_index(word_size) != HumongousIndex) {
+
     ChunkList* free_list = find_free_chunks_list(word_size);
     assert(free_list != NULL, "Sanity check");
 
     chunk = free_list->head();
 
     if (chunk == NULL) {
+      // Split large chunks into smaller chunks if there are no smaller chunks, just large chunks.
+      // This is the counterpart of the coalescing-upon-chunk-return.
+
+      ChunkIndex target_chunk_index = get_chunk_type_by_size(word_size, is_class());
+
+      // Is there a larger chunk we could split?
+      Metachunk* larger_chunk = NULL;
+      ChunkIndex larger_chunk_index = next_chunk_index(target_chunk_index);
+      while (larger_chunk == NULL && larger_chunk_index < NumberOfFreeLists) {
+        larger_chunk = free_chunks(larger_chunk_index)->head();
+        if (larger_chunk == NULL) {
+          larger_chunk_index = next_chunk_index(larger_chunk_index);
+        }
+      }
+
+      if (larger_chunk != NULL) {
+        assert(larger_chunk->word_size() > word_size, "Sanity");
+        assert(larger_chunk->get_chunk_type() == larger_chunk_index, "Sanity");
+
+        // We found a larger chunk. Lets split it up:
+        // - remove old chunk
+        // - in its place, create new smaller chunks, with at least one chunk
+        //   being of target size, the others sized as large as possible. This
+        //   is to make sure the resulting chunks are "as coalesced as possible"
+        //   (similar to VirtualSpaceNode::retire()).
+        // Note: during this operation both ChunkManager and VirtualSpaceNode
+        //  are temporarily invalid, so be careful with asserts.
+
+        log_trace(gc, metaspace, freelist)("%s: splitting chunk " PTR_FORMAT
+           ", word size " SIZE_FORMAT_HEX " (%s), to get a chunk of word size " SIZE_FORMAT_HEX " (%s)...",
+          (is_class() ? "class space" : "metaspace"), p2i(larger_chunk), larger_chunk->word_size(),
+          chunk_size_name(larger_chunk_index), word_size, chunk_size_name(target_chunk_index));
+
+        chunk = split_chunk(word_size, larger_chunk);
+
+        // This should have worked.
+        assert(chunk != NULL, "Sanity");
+        assert(chunk->word_size() == word_size, "Sanity");
+        assert(chunk->is_tagged_free(), "Sanity");
+
+        we_did_split_a_chunk = true;
+
+      }
+    }
+
+    if (chunk == NULL) {
       return NULL;
     }
 
     // Remove the chunk as the head of the list.
     free_list->remove_chunk(chunk);
 
-    log_trace(gc, metaspace, freelist)("ChunkManager::free_chunks_get: free_list " PTR_FORMAT " head " PTR_FORMAT " size " SIZE_FORMAT,
-                                       p2i(free_list), p2i(chunk), chunk->word_size());
+    log_trace(gc, metaspace, freelist)("ChunkManager::free_chunks_get: free_list: " PTR_FORMAT " chunks left: " SSIZE_FORMAT ".",
+                                       p2i(free_list), free_list->count());
+
   } else {
     chunk = humongous_dictionary()->get_chunk(word_size);
 
@@ -2041,17 +2956,24 @@
 
   // Chunk has been removed from the chunk manager; update counters.
   account_for_removed_chunk(chunk);
+  do_update_in_use_info_for_chunk(chunk, true);
+  chunk->container()->inc_container_count();
+  chunk->inc_use_count();
 
   // Remove it from the links to this freelist
   chunk->set_next(NULL);
   chunk->set_prev(NULL);
 
-  // Chunk is no longer on any freelist. Setting to false make container_count_slow()
-  // work.
-  chunk->set_is_tagged_free(false);
-  chunk->container()->inc_container_count();
-
-  slow_locked_verify();
+  // Run some verifications (some more if we did a chunk split)
+#ifdef ASSERT
+  locked_verify();
+  VirtualSpaceNode* const vsn = chunk->container();
+  vsn->verify();
+  if (we_did_split_a_chunk) {
+    vsn->verify_free_chunks_are_ideally_merged();
+  }
+#endif
+
   return chunk;
 }
 
@@ -2089,6 +3011,8 @@
 
 void ChunkManager::return_single_chunk(ChunkIndex index, Metachunk* chunk) {
   assert_lock_strong(SpaceManager::expand_lock());
+  DEBUG_ONLY(do_verify_chunk(chunk);)
+  assert(chunk->get_chunk_type() == index, "Chunk does not match expected index.");
   assert(chunk != NULL, "Expected chunk.");
   assert(chunk->container() != NULL, "Container should have been set.");
   assert(chunk->is_tagged_free() == false, "Chunk should be in use.");
@@ -2097,7 +3021,7 @@
   // Note: mangle *before* returning the chunk to the freelist or dictionary. It does not
   // matter for the freelist (non-humongous chunks), but the humongous chunk dictionary
   // keeps tree node pointers in the chunk payload area which mangle will overwrite.
-  NOT_PRODUCT(chunk->mangle(badMetaWordVal);)
+  DEBUG_ONLY(chunk->mangle(badMetaWordVal);)
 
   if (index != HumongousIndex) {
     // Return non-humongous chunk to freelist.
@@ -2116,11 +3040,24 @@
         chunk_size_name(index), p2i(chunk), chunk->word_size());
   }
   chunk->container()->dec_container_count();
-  chunk->set_is_tagged_free(true);
+  do_update_in_use_info_for_chunk(chunk, false);
 
   // Chunk has been added; update counters.
   account_for_added_chunk(chunk);
 
+  // Attempt coalesce returned chunks with its neighboring chunks:
+  // if this chunk is small or special, attempt to coalesce to a medium chunk.
+  if (index == SmallIndex || index == SpecializedIndex) {
+    if (!attempt_to_coalesce_around_chunk(chunk, MediumIndex)) {
+      // This did not work. But if this chunk is special, we still may form a small chunk?
+      if (index == SpecializedIndex) {
+        if (!attempt_to_coalesce_around_chunk(chunk, SmallIndex)) {
+          // give up.
+        }
+      }
+    }
+  }
+
 }
 
 void ChunkManager::return_chunk_list(ChunkIndex index, Metachunk* chunks) {
@@ -2589,6 +3526,11 @@
   MutexLockerEx fcl(SpaceManager::expand_lock(),
                     Mutex::_no_safepoint_check_flag);
 
+  assert(sum_count_in_chunks_in_use() == allocated_chunks_count(),
+         "sum_count_in_chunks_in_use() " SIZE_FORMAT
+         " allocated_chunks_count() " SIZE_FORMAT,
+         sum_count_in_chunks_in_use(), allocated_chunks_count());
+
   chunk_manager()->slow_locked_verify();
 
   dec_total_from_size_metrics();
@@ -2712,45 +3654,6 @@
   return next;
 }
 
-/*
- * The policy is to allocate up to _small_chunk_limit small chunks
- * after which only medium chunks are allocated.  This is done to
- * reduce fragmentation.  In some cases, this can result in a lot
- * of small chunks being allocated to the point where it's not
- * possible to expand.  If this happens, there may be no medium chunks
- * available and OOME would be thrown.  Instead of doing that,
- * if the allocation request size fits in a small chunk, an attempt
- * will be made to allocate a small chunk.
- */
-MetaWord* SpaceManager::get_small_chunk_and_allocate(size_t word_size) {
-  size_t raw_word_size = get_allocation_word_size(word_size);
-
-  if (raw_word_size + Metachunk::overhead() > small_chunk_size()) {
-    return NULL;
-  }
-
-  MutexLockerEx cl(lock(), Mutex::_no_safepoint_check_flag);
-  MutexLockerEx cl1(expand_lock(), Mutex::_no_safepoint_check_flag);
-
-  Metachunk* chunk = chunk_manager()->chunk_freelist_allocate(small_chunk_size());
-
-  MetaWord* mem = NULL;
-
-  if (chunk != NULL) {
-    // Add chunk to the in-use chunk list and do an allocation from it.
-    // Add to this manager's list of chunks in use.
-    add_chunk(chunk, false);
-    mem = chunk->allocate(raw_word_size);
-
-    inc_used_metrics(raw_word_size);
-
-    // Track metaspace memory usage statistic.
-    track_metaspace_memory_usage();
-  }
-
-  return mem;
-}
-
 MetaWord* SpaceManager::allocate(size_t word_size) {
   MutexLockerEx cl(lock(), Mutex::_no_safepoint_check_flag);
   size_t raw_word_size = get_allocation_word_size(word_size);
@@ -2808,8 +3711,8 @@
     for (ChunkIndex i = ZeroIndex; i < NumberOfInUseLists; i = next_chunk_index(i)) {
       Metachunk* curr = chunks_in_use(i);
       while (curr != NULL) {
-        curr->verify();
-        verify_chunk_size(curr);
+        DEBUG_ONLY(do_verify_chunk(curr);)
+        assert(curr->is_tagged_free() == false, "Chunk should be tagged as in use.");
         curr = curr->next();
       }
     }
@@ -3650,7 +4553,7 @@
          SIZE_FORMAT " != " SIZE_FORMAT, rs.size(), CompressedClassSpaceSize);
   assert(using_class_space(), "Must be using class space");
   _class_space_list = new VirtualSpaceList(rs);
-  _chunk_manager_class = new ChunkManager(ClassSpecializedChunk, ClassSmallChunk, ClassMediumChunk);
+  _chunk_manager_class = new ChunkManager(true/*is_class*/);
 
   if (!_class_space_list->initialization_succeeded()) {
     vm_exit_during_initialization("Failed to setup compressed class space virtual space list.");
@@ -3757,7 +4660,7 @@
 
   // Initialize the list of virtual spaces.
   _space_list = new VirtualSpaceList(word_size);
-  _chunk_manager_metadata = new ChunkManager(SpecializedChunk, SmallChunk, MediumChunk);
+  _chunk_manager_metadata = new ChunkManager(false/*metaspace*/);
 
   if (!_space_list->initialization_succeeded()) {
     vm_exit_during_initialization("Unable to setup metadata virtual space list.", NULL);
@@ -3957,18 +4860,7 @@
   }
 
   if (result == NULL) {
-    SpaceManager* sm;
-    if (is_class_space_allocation(mdtype)) {
-      sm = loader_data->metaspace_non_null()->class_vsm();
-    } else {
-      sm = loader_data->metaspace_non_null()->vsm();
-    }
-
-    result = sm->get_small_chunk_and_allocate(word_size);
-
-    if (result == NULL) {
-      report_metadata_oome(loader_data, word_size, type, mdtype, CHECK_NULL);
-    }
+    report_metadata_oome(loader_data, word_size, type, mdtype, CHECK_NULL);
   }
 
   // Zero initialize.
@@ -4099,6 +4991,24 @@
   }
 }
 
+#ifdef ASSERT
+static void do_verify_chunk(Metachunk* chunk) {
+  guarantee(chunk != NULL, "Sanity");
+  // Verify chunk itself; then verify that it is consistent with the
+  // occupany map of its containing node.
+  chunk->verify();
+  VirtualSpaceNode* const vsn = chunk->container();
+  OccupancyMap* const ocmap = vsn->occupancy_map();
+  ocmap->verify_for_chunk(chunk);
+}
+#endif
+
+static void do_update_in_use_info_for_chunk(Metachunk* chunk, bool inuse) {
+  chunk->set_is_tagged_free(!inuse);
+  OccupancyMap* const ocmap = chunk->container()->occupancy_map();
+  ocmap->set_region_in_use((MetaWord*)chunk, chunk->word_size(), inuse);
+}
+
 /////////////// Unit tests ///////////////
 
 #ifndef PRODUCT
@@ -4189,16 +5099,16 @@
     STATIC_ASSERT(SmallChunk % SpecializedChunk == 0);
 
     { // No committed memory in VSN
-      ChunkManager cm(SpecializedChunk, SmallChunk, MediumChunk);
-      VirtualSpaceNode vsn(vsn_test_size_bytes);
+      ChunkManager cm(false);
+      VirtualSpaceNode vsn(false, vsn_test_size_bytes);
       vsn.initialize();
       vsn.retire(&cm);
       assert(cm.sum_free_chunks_count() == 0, "did not commit any memory in the VSN");
     }
 
     { // All of VSN is committed, half is used by chunks
-      ChunkManager cm(SpecializedChunk, SmallChunk, MediumChunk);
-      VirtualSpaceNode vsn(vsn_test_size_bytes);
+      ChunkManager cm(false);
+      VirtualSpaceNode vsn(false, vsn_test_size_bytes);
       vsn.initialize();
       vsn.expand_by(vsn_test_size_words, vsn_test_size_words);
       vsn.get_chunk_vs(MediumChunk);
@@ -4212,8 +5122,8 @@
     // This doesn't work for systems with vm_page_size >= 16K.
     if (page_chunks < MediumChunk) {
       // 4 pages of VSN is committed, some is used by chunks
-      ChunkManager cm(SpecializedChunk, SmallChunk, MediumChunk);
-      VirtualSpaceNode vsn(vsn_test_size_bytes);
+      ChunkManager cm(false);
+      VirtualSpaceNode vsn(false, vsn_test_size_bytes);
 
       vsn.initialize();
       vsn.expand_by(page_chunks, page_chunks);
@@ -4233,8 +5143,8 @@
     }
 
     { // Half of VSN is committed, a humongous chunk is used
-      ChunkManager cm(SpecializedChunk, SmallChunk, MediumChunk);
-      VirtualSpaceNode vsn(vsn_test_size_bytes);
+      ChunkManager cm(false);
+      VirtualSpaceNode vsn(false, vsn_test_size_bytes);
       vsn.initialize();
       vsn.expand_by(MediumChunk * 2, MediumChunk * 2);
       vsn.get_chunk_vs(MediumChunk + SpecializedChunk); // Humongous chunks will be aligned up to MediumChunk + SpecializedChunk
@@ -4265,7 +5175,7 @@
 
   static void test_is_available_positive() {
     // Reserve some memory.
-    VirtualSpaceNode vsn(os::vm_allocation_granularity());
+    VirtualSpaceNode vsn(false, os::vm_allocation_granularity());
     assert(vsn.initialize(), "Failed to setup VirtualSpaceNode");
 
     // Commit some memory.
@@ -4283,7 +5193,7 @@
 
   static void test_is_available_negative() {
     // Reserve some memory.
-    VirtualSpaceNode vsn(os::vm_allocation_granularity());
+    VirtualSpaceNode vsn(false, os::vm_allocation_granularity());
     assert(vsn.initialize(), "Failed to setup VirtualSpaceNode");
 
     // Commit some memory.
@@ -4298,7 +5208,7 @@
 
   static void test_is_available_overflow() {
     // Reserve some memory.
-    VirtualSpaceNode vsn(os::vm_allocation_granularity());
+    VirtualSpaceNode vsn(false, os::vm_allocation_granularity());
     assert(vsn.initialize(), "Failed to setup VirtualSpaceNode");
 
     // Commit some memory.
@@ -4323,15 +5233,10 @@
   }
 };
 
-void TestVirtualSpaceNode_test() {
-  TestVirtualSpaceNodeTest::test();
-  TestVirtualSpaceNodeTest::test_is_available();
-}
-
 // The following test is placed here instead of a gtest / unittest file
 // because the ChunkManager class is only available in this file.
 void ChunkManager_test_list_index() {
-  ChunkManager manager(ClassSpecializedChunk, ClassSmallChunk, ClassMediumChunk);
+  ChunkManager manager(true);
 
   // Test previous bug where a query for a humongous class metachunk,
   // incorrectly matched the non-class medium metachunk size.
@@ -4368,266 +5273,6 @@
 
 #ifdef ASSERT
 
-// ChunkManagerReturnTest stresses taking/returning chunks from the ChunkManager. It takes and
-// returns chunks from/to the ChunkManager while keeping track of the expected ChunkManager
-// content.
-class ChunkManagerReturnTestImpl : public CHeapObj<mtClass> {
-
-  VirtualSpaceNode _vsn;
-  ChunkManager _cm;
-
-  // The expected content of the chunk manager.
-  unsigned _chunks_in_chunkmanager;
-  size_t _words_in_chunkmanager;
-
-  // A fixed size pool of chunks. Chunks may be in the chunk manager (free) or not (in use).
-  static const int num_chunks = 256;
-  Metachunk* _pool[num_chunks];
-
-  // Helper, return a random position into the chunk pool.
-  static int get_random_position() {
-    return os::random() % num_chunks;
-  }
-
-  // Asserts that ChunkManager counters match expectations.
-  void assert_counters() {
-    assert(_vsn.container_count() == num_chunks - _chunks_in_chunkmanager, "vsn counter mismatch.");
-    assert(_cm.free_chunks_count() == _chunks_in_chunkmanager, "cm counter mismatch.");
-    assert(_cm.free_chunks_total_words() == _words_in_chunkmanager, "cm counter mismatch.");
-  }
-
-  // Get a random chunk size. Equal chance to get spec/med/small chunk size or
-  // a humongous chunk size. The latter itself is random in the range of [med+spec..4*med).
-  size_t get_random_chunk_size() {
-    const size_t sizes [] = { SpecializedChunk, SmallChunk, MediumChunk };
-    const int rand = os::random() % 4;
-    if (rand < 3) {
-      return sizes[rand];
-    } else {
-      // Note: this affects the max. size of space (see _vsn initialization in ctor).
-      return align_up(MediumChunk + 1 + (os::random() % (MediumChunk * 4)), SpecializedChunk);
-    }
-  }
-
-  // Starting at pool index <start>+1, find the next chunk tagged as either free or in use, depending
-  // on <is_free>. Search wraps. Returns its position, or -1 if no matching chunk was found.
-  int next_matching_chunk(int start, bool is_free) const {
-    assert(start >= 0 && start < num_chunks, "invalid parameter");
-    int pos = start;
-    do {
-      if (++pos == num_chunks) {
-        pos = 0;
-      }
-      if (_pool[pos]->is_tagged_free() == is_free) {
-        return pos;
-      }
-    } while (pos != start);
-    return -1;
-  }
-
-  // A structure to keep information about a chunk list including which
-  // chunks are part of this list. This is needed to keep information about a chunk list
-  // we will to return to the ChunkManager, because the original list will be destroyed.
-  struct AChunkList {
-    Metachunk* head;
-    Metachunk* all[num_chunks];
-    size_t size;
-    int num;
-    ChunkIndex index;
-  };
-
-  // Assemble, from the in-use chunks (not in the chunk manager) in the pool,
-  // a random chunk list of max. length <list_size> of chunks with the same
-  // ChunkIndex (chunk size).
-  // Returns false if list cannot be assembled. List is returned in the <out>
-  // structure. Returned list may be smaller than <list_size>.
-  bool assemble_random_chunklist(AChunkList* out, int list_size) {
-    // Choose a random in-use chunk from the pool...
-    const int headpos = next_matching_chunk(get_random_position(), false);
-    if (headpos == -1) {
-      return false;
-    }
-    Metachunk* const head = _pool[headpos];
-    out->all[0] = head;
-    assert(head->is_tagged_free() == false, "Chunk state mismatch");
-    // ..then go from there, chain it up with up to list_size - 1 number of other
-    // in-use chunks of the same index.
-    const ChunkIndex index = _cm.list_index(head->word_size());
-    int num_added = 1;
-    size_t size_added = head->word_size();
-    int pos = headpos;
-    Metachunk* tail = head;
-    do {
-      pos = next_matching_chunk(pos, false);
-      if (pos != headpos) {
-        Metachunk* c = _pool[pos];
-        assert(c->is_tagged_free() == false, "Chunk state mismatch");
-        if (index == _cm.list_index(c->word_size())) {
-          tail->set_next(c);
-          c->set_prev(tail);
-          tail = c;
-          out->all[num_added] = c;
-          num_added ++;
-          size_added += c->word_size();
-        }
-      }
-    } while (num_added < list_size && pos != headpos);
-    out->head = head;
-    out->index = index;
-    out->size = size_added;
-    out->num = num_added;
-    return true;
-  }
-
-  // Take a single random chunk from the ChunkManager.
-  bool take_single_random_chunk_from_chunkmanager() {
-    assert_counters();
-    _cm.locked_verify();
-    int pos = next_matching_chunk(get_random_position(), true);
-    if (pos == -1) {
-      return false;
-    }
-    Metachunk* c = _pool[pos];
-    assert(c->is_tagged_free(), "Chunk state mismatch");
-    // Note: instead of using ChunkManager::remove_chunk on this one chunk, we call
-    // ChunkManager::free_chunks_get() with this chunk's word size. We really want
-    // to exercise ChunkManager::free_chunks_get() because that one gets called for
-    // normal chunk allocation.
-    Metachunk* c2 = _cm.free_chunks_get(c->word_size());
-    assert(c2 != NULL, "Unexpected.");
-    assert(!c2->is_tagged_free(), "Chunk state mismatch");
-    assert(c2->next() == NULL && c2->prev() == NULL, "Chunk should be outside of a list.");
-    _chunks_in_chunkmanager --;
-    _words_in_chunkmanager -= c->word_size();
-    assert_counters();
-    _cm.locked_verify();
-    return true;
-  }
-
-  // Returns a single random chunk to the chunk manager. Returns false if that
-  // was not possible (all chunks are already in the chunk manager).
-  bool return_single_random_chunk_to_chunkmanager() {
-    assert_counters();
-    _cm.locked_verify();
-    int pos = next_matching_chunk(get_random_position(), false);
-    if (pos == -1) {
-      return false;
-    }
-    Metachunk* c = _pool[pos];
-    assert(c->is_tagged_free() == false, "wrong chunk information");
-    _cm.return_single_chunk(_cm.list_index(c->word_size()), c);
-    _chunks_in_chunkmanager ++;
-    _words_in_chunkmanager += c->word_size();
-    assert(c->is_tagged_free() == true, "wrong chunk information");
-    assert_counters();
-    _cm.locked_verify();
-    return true;
-  }
-
-  // Return a random chunk list to the chunk manager. Returns the length of the
-  // returned list.
-  int return_random_chunk_list_to_chunkmanager(int list_size) {
-    assert_counters();
-    _cm.locked_verify();
-    AChunkList aChunkList;
-    if (!assemble_random_chunklist(&aChunkList, list_size)) {
-      return 0;
-    }
-    // Before returning chunks are returned, they should be tagged in use.
-    for (int i = 0; i < aChunkList.num; i ++) {
-      assert(!aChunkList.all[i]->is_tagged_free(), "chunk state mismatch.");
-    }
-    _cm.return_chunk_list(aChunkList.index, aChunkList.head);
-    _chunks_in_chunkmanager += aChunkList.num;
-    _words_in_chunkmanager += aChunkList.size;
-    // After all chunks are returned, check that they are now tagged free.
-    for (int i = 0; i < aChunkList.num; i ++) {
-      assert(aChunkList.all[i]->is_tagged_free(), "chunk state mismatch.");
-    }
-    assert_counters();
-    _cm.locked_verify();
-    return aChunkList.num;
-  }
-
-public:
-
-  ChunkManagerReturnTestImpl()
-    : _vsn(align_up(MediumChunk * num_chunks * 5 * sizeof(MetaWord), Metaspace::reserve_alignment()))
-    , _cm(SpecializedChunk, SmallChunk, MediumChunk)
-    , _chunks_in_chunkmanager(0)
-    , _words_in_chunkmanager(0)
-  {
-    MutexLockerEx ml(SpaceManager::expand_lock(), Mutex::_no_safepoint_check_flag);
-    // Allocate virtual space and allocate random chunks. Keep these chunks in the _pool. These chunks are
-    // "in use", because not yet added to any chunk manager.
-    _vsn.initialize();
-    _vsn.expand_by(_vsn.reserved_words(), _vsn.reserved_words());
-    for (int i = 0; i < num_chunks; i ++) {
-      const size_t size = get_random_chunk_size();
-      _pool[i] = _vsn.get_chunk_vs(size);
-      assert(_pool[i] != NULL, "allocation failed");
-    }
-    assert_counters();
-    _cm.locked_verify();
-  }
-
-  // Test entry point.
-  // Return some chunks to the chunk manager (return phase). Take some chunks out (take phase). Repeat.
-  // Chunks are choosen randomly. Number of chunks to return or taken are choosen randomly, but affected
-  // by the <phase_length_factor> argument: a factor of 0.0 will cause the test to quickly alternate between
-  // returning and taking, whereas a factor of 1.0 will take/return all chunks from/to the
-  // chunks manager, thereby emptying or filling it completely.
-  void do_test(float phase_length_factor) {
-    MutexLockerEx ml(SpaceManager::expand_lock(), Mutex::_no_safepoint_check_flag);
-    assert_counters();
-    // Execute n operations, and operation being the move of a single chunk to/from the chunk manager.
-    const int num_max_ops = num_chunks * 100;
-    int num_ops = num_max_ops;
-    const int average_phase_length = (int)(phase_length_factor * num_chunks);
-    int num_ops_until_switch = MAX2(1, (average_phase_length + os::random() % 8 - 4));
-    bool return_phase = true;
-    while (num_ops > 0) {
-      int chunks_moved = 0;
-      if (return_phase) {
-        // Randomly switch between returning a single chunk or a random length chunk list.
-        if (os::random() % 2 == 0) {
-          if (return_single_random_chunk_to_chunkmanager()) {
-            chunks_moved = 1;
-          }
-        } else {
-          const int list_length = MAX2(1, (os::random() % num_ops_until_switch));
-          chunks_moved = return_random_chunk_list_to_chunkmanager(list_length);
-        }
-      } else {
-        // Breath out.
-        if (take_single_random_chunk_from_chunkmanager()) {
-          chunks_moved = 1;
-        }
-      }
-      num_ops -= chunks_moved;
-      num_ops_until_switch -= chunks_moved;
-      if (chunks_moved == 0 || num_ops_until_switch <= 0) {
-        return_phase = !return_phase;
-        num_ops_until_switch = MAX2(1, (average_phase_length + os::random() % 8 - 4));
-      }
-    }
-  }
-};
-
-void* setup_chunkmanager_returntests() {
-  ChunkManagerReturnTestImpl* p = new ChunkManagerReturnTestImpl();
-  return p;
-}
-
-void teardown_chunkmanager_returntests(void* p) {
-  delete (ChunkManagerReturnTestImpl*) p;
-}
-
-void run_chunkmanager_returntests(void* p, float phase_length) {
-  ChunkManagerReturnTestImpl* test = (ChunkManagerReturnTestImpl*) p;
-  test->do_test(phase_length);
-}
-
 // The following test is placed here instead of a gtest / unittest file
 // because the ChunkManager class is only available in this file.
 class SpaceManagerTest : AllStatic {
@@ -4678,3 +5323,39 @@
 }
 
 #endif // ASSERT
+
+struct chunkmanager_statistics_t {
+  int num_specialized_chunks;
+  int num_small_chunks;
+  int num_medium_chunks;
+  int num_humongous_chunks;
+};
+
+extern void test_metaspace_retrieve_chunkmanager_statistics(Metaspace::MetadataType mdType, chunkmanager_statistics_t* out) {
+  ChunkManager* const chunk_manager = Metaspace::get_chunk_manager(mdType);
+  ChunkManager::ChunkManagerStatistics stat;
+  chunk_manager->get_statistics(&stat);
+  out->num_specialized_chunks = (int)stat.num_by_type[SpecializedIndex];
+  out->num_small_chunks = (int)stat.num_by_type[SmallIndex];
+  out->num_medium_chunks = (int)stat.num_by_type[MediumIndex];
+  out->num_humongous_chunks = (int)stat.num_humongous_chunks;
+}
+
+struct chunk_geometry_t {
+  size_t specialized_chunk_word_size;
+  size_t small_chunk_word_size;
+  size_t medium_chunk_word_size;
+};
+
+extern void test_metaspace_retrieve_chunk_geometry(Metaspace::MetadataType mdType, chunk_geometry_t* out) {
+  if (mdType == Metaspace::NonClassType) {
+    out->specialized_chunk_word_size = SpecializedChunk;
+    out->small_chunk_word_size = SmallChunk;
+    out->medium_chunk_word_size = MediumChunk;
+  } else {
+    out->specialized_chunk_word_size = ClassSpecializedChunk;
+    out->small_chunk_word_size = ClassSmallChunk;
+    out->medium_chunk_word_size = ClassMediumChunk;
+  }
+}
+
--- a/src/hotspot/share/memory/metaspace.hpp	Tue Mar 06 08:36:44 2018 +0100
+++ b/src/hotspot/share/memory/metaspace.hpp	Tue Mar 06 19:24:13 2018 +0100
@@ -89,6 +89,7 @@
   friend class MetaspaceShared;
   friend class CollectedHeap;
   friend class PrintCLDMetaspaceInfoClosure;
+  friend class MetaspaceAllocationTest;
 
  public:
   enum MetadataType {
@@ -176,6 +177,11 @@
     return mdtype == ClassType ? chunk_manager_class() : chunk_manager_metadata();
   }
 
+  // convenience function
+  static ChunkManager* get_chunk_manager(bool is_class) {
+    return is_class ? chunk_manager_class() : chunk_manager_metadata();
+  }
+
   static const MetaspaceTracer* tracer() { return _tracer; }
   static void freeze() {
     assert(DumpSharedSpaces, "sanity");
--- a/src/hotspot/share/utilities/internalVMTests.cpp	Tue Mar 06 08:36:44 2018 +0100
+++ b/src/hotspot/share/utilities/internalVMTests.cpp	Tue Mar 06 19:24:13 2018 +0100
@@ -45,7 +45,6 @@
   run_unit_test(TestReserveMemorySpecial_test);
   run_unit_test(TestVirtualSpace_test);
   run_unit_test(TestMetaspaceAux_test);
-  run_unit_test(TestVirtualSpaceNode_test);
   run_unit_test(GCTimer_test);
   run_unit_test(ObjectMonitor_test);
   run_unit_test(DirectivesParser_test);
--- a/test/hotspot/gtest/memory/test_chunkManager.cpp	Tue Mar 06 08:36:44 2018 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,59 +0,0 @@
-/*
- * Copyright (c) 2016, 2017 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"
-
-// The test function is only available in debug builds
-#ifdef ASSERT
-
-#include "unittest.hpp"
-
-void ChunkManager_test_list_index();
-
-TEST(ChunkManager, list_index) {
-  // The ChunkManager is only available in metaspace.cpp,
-  // so the test code is located in that file.
-  ChunkManager_test_list_index();
-
-}
-
-extern void* setup_chunkmanager_returntests();
-extern void teardown_chunkmanager_returntests(void*);
-extern void run_chunkmanager_returntests(void* p, float phase_length_factor);
-
-class ChunkManagerReturnTest : public ::testing::Test {
-protected:
-  void* _test;
-  virtual void SetUp() {
-    _test = setup_chunkmanager_returntests();
-  }
-  virtual void TearDown() {
-    teardown_chunkmanager_returntests(_test);
-  }
-};
-
-TEST_VM_F(ChunkManagerReturnTest, test00) { run_chunkmanager_returntests(_test, 0.0f); }
-TEST_VM_F(ChunkManagerReturnTest, test05) { run_chunkmanager_returntests(_test, 0.5f); }
-TEST_VM_F(ChunkManagerReturnTest, test10) { run_chunkmanager_returntests(_test, 1.0f); }
-
-#endif // ASSERT
--- a/test/hotspot/gtest/memory/test_metachunk.cpp	Tue Mar 06 08:36:44 2018 +0100
+++ b/test/hotspot/gtest/memory/test_metachunk.cpp	Tue Mar 06 19:24:13 2018 +0100
@@ -41,11 +41,16 @@
 };
 
 TEST(Metachunk, basic) {
-  size_t size = 2 * 1024 * 1024;
-  void* memory = malloc(size);
+  const ChunkIndex chunk_type = MediumIndex;
+  const bool is_class = false;
+  const size_t word_size = get_size_for_nonhumongous_chunktype(chunk_type, is_class);
+  // Allocate the chunk with correct alignment.
+  void* memory = malloc(word_size * BytesPerWord * 2);
   ASSERT_TRUE(NULL != memory) << "Failed to malloc 2MB";
 
-  Metachunk* metachunk = ::new (memory) Metachunk(size / BytesPerWord, NULL);
+  void* p_placement = align_up(memory, word_size * BytesPerWord);
+
+  Metachunk* metachunk = ::new (p_placement) Metachunk(chunk_type, is_class, word_size, NULL);
 
   EXPECT_EQ((MetaWord*) metachunk, metachunk->bottom());
   EXPECT_EQ((uintptr_t*) metachunk + metachunk->size(), metachunk->end());
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/hotspot/gtest/memory/test_metaspace_allocation.cpp	Tue Mar 06 19:24:13 2018 +0100
@@ -0,0 +1,265 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2018, SAP.
+ * 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 "memory/allocation.inline.hpp"
+#include "memory/metaspace.hpp"
+#include "runtime/mutex.hpp"
+#include "runtime/os.hpp"
+#include "utilities/align.hpp"
+#include "utilities/debug.hpp"
+#include "utilities/globalDefinitions.hpp"
+#include "utilities/ostream.hpp"
+#include "unittest.hpp"
+
+#define NUM_PARALLEL_METASPACES                 50
+#define MAX_PER_METASPACE_ALLOCATION_WORDSIZE   (512 * K)
+
+//#define DEBUG_VERBOSE true
+
+#ifdef DEBUG_VERBOSE
+
+struct chunkmanager_statistics_t {
+  int num_specialized_chunks;
+  int num_small_chunks;
+  int num_medium_chunks;
+  int num_humongous_chunks;
+};
+
+extern void test_metaspace_retrieve_chunkmanager_statistics(Metaspace::MetadataType mdType, chunkmanager_statistics_t* out);
+
+static void print_chunkmanager_statistics(outputStream* st, Metaspace::MetadataType mdType) {
+  chunkmanager_statistics_t stat;
+  test_metaspace_retrieve_chunkmanager_statistics(mdType, &stat);
+  st->print_cr("free chunks: %d / %d / %d / %d", stat.num_specialized_chunks, stat.num_small_chunks,
+               stat.num_medium_chunks, stat.num_humongous_chunks);
+}
+
+#endif
+
+struct chunk_geometry_t {
+  size_t specialized_chunk_word_size;
+  size_t small_chunk_word_size;
+  size_t medium_chunk_word_size;
+};
+
+extern void test_metaspace_retrieve_chunk_geometry(Metaspace::MetadataType mdType, chunk_geometry_t* out);
+
+
+class MetaspaceAllocationTest : public ::testing::Test {
+protected:
+
+  struct {
+    size_t allocated;
+    Mutex* lock;
+    Metaspace* space;
+    bool is_empty() const { return allocated == 0; }
+    bool is_full() const { return allocated >= MAX_PER_METASPACE_ALLOCATION_WORDSIZE; }
+  } _spaces[NUM_PARALLEL_METASPACES];
+
+  chunk_geometry_t _chunk_geometry;
+
+  virtual void SetUp() {
+    ::memset(_spaces, 0, sizeof(_spaces));
+    test_metaspace_retrieve_chunk_geometry(Metaspace::NonClassType, &_chunk_geometry);
+  }
+
+  virtual void TearDown() {
+    for (int i = 0; i < NUM_PARALLEL_METASPACES; i ++) {
+      if (_spaces[i].space != NULL) {
+        delete _spaces[i].space;
+        delete _spaces[i].lock;
+      }
+    }
+  }
+
+  void create_space(int i) {
+    assert(i >= 0 && i < NUM_PARALLEL_METASPACES, "Sanity");
+    assert(_spaces[i].space == NULL && _spaces[i].allocated == 0, "Sanity");
+    if (_spaces[i].lock == NULL) {
+      _spaces[i].lock = new Mutex(Monitor::native, "gtest-MetaspaceAllocationTest-lock", false, Monitor::_safepoint_check_never);
+      ASSERT_TRUE(_spaces[i].lock != NULL);
+    }
+    // Let every ~10th space be an anonymous one to test different allocation patterns.
+    const Metaspace::MetaspaceType msType = (os::random() % 100 < 10) ?
+      Metaspace::AnonymousMetaspaceType : Metaspace::StandardMetaspaceType;
+    _spaces[i].space = new Metaspace(_spaces[i].lock, msType);
+    _spaces[i].allocated = 0;
+    ASSERT_TRUE(_spaces[i].space != NULL);
+  }
+
+  // Returns the index of a random space where index is [0..metaspaces) and which is
+  //   empty, non-empty or full.
+  // Returns -1 if no matching space exists.
+  enum fillgrade { fg_empty, fg_non_empty, fg_full };
+  int get_random_matching_space(int metaspaces, fillgrade fg) {
+    const int start_index = os::random() % metaspaces;
+    int i = start_index;
+    do {
+      if (fg == fg_empty && _spaces[i].is_empty()) {
+        return i;
+      } else if ((fg == fg_full && _spaces[i].is_full()) ||
+                 (fg == fg_non_empty && !_spaces[i].is_full() && !_spaces[i].is_empty())) {
+        return i;
+      }
+      i ++;
+      if (i == metaspaces) {
+        i = 0;
+      }
+    } while (i != start_index);
+    return -1;
+  }
+
+  int get_random_emtpy_space(int metaspaces) { return get_random_matching_space(metaspaces, fg_empty); }
+  int get_random_non_emtpy_space(int metaspaces) { return get_random_matching_space(metaspaces, fg_non_empty); }
+  int get_random_full_space(int metaspaces) { return get_random_matching_space(metaspaces, fg_full); }
+
+  void do_test(Metaspace::MetadataType mdType, int metaspaces, int phases, int allocs_per_phase,
+               float probability_for_large_allocations // 0.0-1.0
+  ) {
+    // Alternate between breathing in (allocating n blocks for a random Metaspace) and
+    // breathing out (deleting a random Metaspace). The intent is to stress the coalescation
+    // and splitting of free chunks.
+    int phases_done = 0;
+    bool allocating = true;
+    while (phases_done < phases) {
+      bool force_switch = false;
+      if (allocating) {
+        // Allocate space from metaspace, with a preference for completely empty spaces. This
+        // should provide a good mixture of metaspaces in the virtual space.
+        int index = get_random_emtpy_space(metaspaces);
+        if (index == -1) {
+          index = get_random_non_emtpy_space(metaspaces);
+        }
+        if (index == -1) {
+          // All spaces are full, switch to freeing.
+          force_switch = true;
+        } else {
+          // create space if it does not yet exist.
+          if (_spaces[index].space == NULL) {
+            create_space(index);
+          }
+          // Allocate a bunch of blocks from it. Mostly small stuff but mix in large allocations
+          //  to force humongous chunk allocations.
+          int allocs_done = 0;
+          while (allocs_done < allocs_per_phase && !_spaces[index].is_full()) {
+            size_t size = 0;
+            int r = os::random() % 1000;
+            if ((float)r < probability_for_large_allocations * 1000.0) {
+              size = (os::random() % _chunk_geometry.medium_chunk_word_size) + _chunk_geometry.medium_chunk_word_size;
+            } else {
+              size = os::random() % 64;
+            }
+            MetaWord* const p = _spaces[index].space->allocate(size, mdType);
+            if (p == NULL) {
+              // We very probably did hit the metaspace "until-gc" limit.
+#ifdef DEBUG_VERBOSE
+              tty->print_cr("OOM for " SIZE_FORMAT " words. ", size);
+#endif
+              // Just switch to deallocation and resume tests.
+              force_switch = true;
+              break;
+            } else {
+              _spaces[index].allocated += size;
+              allocs_done ++;
+            }
+          }
+        }
+      } else {
+        // freeing: find a metaspace and delete it, with preference for completely filled spaces.
+        int index = get_random_full_space(metaspaces);
+        if (index == -1) {
+          index = get_random_non_emtpy_space(metaspaces);
+        }
+        if (index == -1) {
+          force_switch = true;
+        } else {
+          assert(_spaces[index].space != NULL && _spaces[index].allocated > 0, "Sanity");
+          delete _spaces[index].space;
+          _spaces[index].space = NULL;
+          _spaces[index].allocated = 0;
+        }
+      }
+
+      if (force_switch) {
+        allocating = !allocating;
+      } else {
+        // periodically switch between allocating and freeing, but prefer allocation because
+        // we want to intermingle allocations of multiple metaspaces.
+        allocating = os::random() % 5 < 4;
+      }
+      phases_done ++;
+#ifdef DEBUG_VERBOSE
+      int metaspaces_in_use = 0;
+      size_t total_allocated = 0;
+      for (int i = 0; i < metaspaces; i ++) {
+        if (_spaces[i].allocated > 0) {
+          total_allocated += _spaces[i].allocated;
+          metaspaces_in_use ++;
+        }
+      }
+      tty->print("%u:\tspaces: %d total words: " SIZE_FORMAT "\t\t\t", phases_done, metaspaces_in_use, total_allocated);
+      print_chunkmanager_statistics(tty, mdType);
+#endif
+    }
+#ifdef DEBUG_VERBOSE
+    tty->print_cr("Test finished. ");
+    MetaspaceAux::print_metaspace_map(tty, mdType);
+    print_chunkmanager_statistics(tty, mdType);
+#endif
+  }
+};
+
+
+
+TEST_F(MetaspaceAllocationTest, chunk_geometry) {
+  ASSERT_GT(_chunk_geometry.specialized_chunk_word_size, (size_t) 0);
+  ASSERT_GT(_chunk_geometry.small_chunk_word_size, _chunk_geometry.specialized_chunk_word_size);
+  ASSERT_EQ(_chunk_geometry.small_chunk_word_size % _chunk_geometry.specialized_chunk_word_size, (size_t)0);
+  ASSERT_GT(_chunk_geometry.medium_chunk_word_size, _chunk_geometry.small_chunk_word_size);
+  ASSERT_EQ(_chunk_geometry.medium_chunk_word_size % _chunk_geometry.small_chunk_word_size, (size_t)0);
+}
+
+
+TEST_VM_F(MetaspaceAllocationTest, single_space_nonclass) {
+  do_test(Metaspace::NonClassType, 1, 1000, 100, 0);
+}
+
+TEST_VM_F(MetaspaceAllocationTest, single_space_class) {
+  do_test(Metaspace::ClassType, 1, 1000, 100, 0);
+}
+
+TEST_VM_F(MetaspaceAllocationTest, multi_space_nonclass) {
+  do_test(Metaspace::NonClassType, NUM_PARALLEL_METASPACES, 100, 1000, 0.0);
+}
+
+TEST_VM_F(MetaspaceAllocationTest, multi_space_class) {
+  do_test(Metaspace::ClassType, NUM_PARALLEL_METASPACES, 100, 1000, 0.0);
+}
+
+TEST_VM_F(MetaspaceAllocationTest, multi_space_nonclass_2) {
+  // many metaspaces, with humongous chunks mixed in.
+  do_test(Metaspace::NonClassType, NUM_PARALLEL_METASPACES, 100, 1000, .006f);
+}
+