2  * Copyright (c) 2018, 2019, Oracle and/or its affiliates. All rights reserved.

     2  * Copyright (c) 2019, SAP SE. All rights reserved.

     3  * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.

    28 #include "memory/binaryTreeDictionary.inline.hpp"

    31 #include "memory/metaspace/chunkAllocSequence.hpp"

    29 #include "memory/freeList.inline.hpp"

    32 #include "memory/metaspace/chunkLevel.hpp"

    44 ChunkManager::ChunkManager(bool is_class)

    46 

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

    47 // Return a single chunk to the freelist and adjust accounting. No merge is attempted.

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

    48 void ChunkManager::return_chunk_simple(Metachunk* c) {

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

    49 

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

    50   assert_lock_strong(MetaspaceExpand_lock);

    49 }

    51 

    50 

    52   DEBUG_ONLY(c->verify(false));

    51 void ChunkManager::remove_chunk(Metachunk* chunk) {

    53 

    52   size_t word_size = chunk->word_size();

    54   const chklvl_t lvl = c->level();

    53   ChunkIndex index = list_index(word_size);

    55   _chunks.add(c);

    54   if (index != HumongousIndex) {

    56   c->reset_used_words();

    55     free_chunks(index)->remove_chunk(chunk);

    57 

    58   // Tracing

    59   log_debug(metaspace)("ChunkManager %s: returned chunk " METACHUNK_FORMAT ".",

    60                        _name, METACHUNK_FORMAT_ARGS(c));

    61 

    62 }

    63 

    64 // Take a single chunk from the given freelist and adjust counters. Returns NULL

    65 // if there is no fitting chunk for this level.

    66 Metachunk* ChunkManager::remove_first_chunk_at_level(chklvl_t l) {

    67 

    68   assert_lock_strong(MetaspaceExpand_lock);

    69   DEBUG_ONLY(chklvl::check_valid_level(l);)

    70 

    71   Metachunk* c = _chunks.remove_first(l);

    72 

    73   // Tracing

    74   if (c != NULL) {

    75     log_debug(metaspace)("ChunkManager %s: removed chunk " METACHUNK_FORMAT ".",

    76                          _name, METACHUNK_FORMAT_ARGS(c));

    57     humongous_dictionary()->remove_chunk(chunk);

    78     log_trace(metaspace)("ChunkManager %s: no chunk found for level " CHKLVL_FORMAT,

    58   }

    79                          _name, l);

    59 

    80   }

    60   // Chunk has been removed from the chunks free list, update counters.

    81 

    61   account_for_removed_chunk(chunk);

    82   return c;

    62 }

    83 }

    63 

    84 

    64 bool ChunkManager::attempt_to_coalesce_around_chunk(Metachunk* chunk, ChunkIndex target_chunk_type) {

    85 // Creates a chunk manager with a given name (which is for debug purposes only)

    65   assert_lock_strong(MetaspaceExpand_lock);

    86 // and an associated space list which will be used to request new chunks from

    66   assert(chunk != NULL, "invalid chunk pointer");

    87 // (see get_chunk())

    67   // Check for valid merge combinations.

    88 ChunkManager::ChunkManager(const char* name, VirtualSpaceList* space_list)

    68   assert((chunk->get_chunk_type() == SpecializedIndex &&

    89   : _vslist(space_list),

    69           (target_chunk_type == SmallIndex || target_chunk_type == MediumIndex)) ||

    90     _name(name),

    70          (chunk->get_chunk_type() == SmallIndex && target_chunk_type == MediumIndex),

    91     _chunks()

    71         "Invalid chunk merge combination.");

    92 {

    72 

    93 }

    73   const size_t target_chunk_word_size =

    94 

    74     get_size_for_nonhumongous_chunktype(target_chunk_type, this->is_class());

    95 // Given a chunk we are about to handout to the caller, make sure it is committed

    75 

    96 // according to constants::committed_words_on_fresh_chunks

    76   // [ prospective merge region )

    97 bool ChunkManager::commit_chunk_before_handout(Metachunk* c) {

    77   MetaWord* const p_merge_region_start =

    98   assert_lock_strong(MetaspaceExpand_lock);

    78     (MetaWord*) align_down(chunk, target_chunk_word_size * sizeof(MetaWord));

    99   const size_t must_be_committed = MIN2(c->word_size(), Settings::committed_words_on_fresh_chunks());

    79   MetaWord* const p_merge_region_end =

   100   return c->ensure_committed_locked(must_be_committed);

    80     p_merge_region_start + target_chunk_word_size;

   101 }

    81 

   102 

    82   // We need the VirtualSpaceNode containing this chunk and its occupancy map.

   103 // Given a chunk which must be outside of a freelist and must be free, split it to

    83   VirtualSpaceNode* const vsn = chunk->container();

   104 // meet a target level and return it. Splinters are added to the freelist.

    84   OccupancyMap* const ocmap = vsn->occupancy_map();

   105 Metachunk* ChunkManager::split_chunk_and_add_splinters(Metachunk* c, chklvl_t target_level) {

    85 

   106 

    86   // The prospective chunk merge range must be completely contained by the

   107   assert_lock_strong(MetaspaceExpand_lock);

    87   // committed range of the virtual space node.

   108 

    88   if (p_merge_region_start < vsn->bottom() || p_merge_region_end > vsn->top()) {

   109   assert(c->is_free() && c->level() < target_level, "Invalid chunk for splitting");

    89     return false;

   110   DEBUG_ONLY(chklvl::check_valid_level(target_level);)

    90   }

   111 

    91 

   112   DEBUG_ONLY(c->verify(true);)

    92   // Only attempt to merge this range if at its start a chunk starts and at its end

   113   DEBUG_ONLY(c->vsnode()->verify(true);)

    93   // a chunk ends. If a chunk (can only be humongous) straddles either start or end

   114 

    94   // of that range, we cannot merge.

   115   // Chunk must be outside of our freelists

    95   if (!ocmap->chunk_starts_at_address(p_merge_region_start)) {

   116   assert(_chunks.contains(c) == false, "Chunk is in freelist.");

    96     return false;

   117 

    97   }

   118   log_debug(metaspace)("ChunkManager %s: will split chunk " METACHUNK_FORMAT " to " CHKLVL_FORMAT ".",

    98   if (p_merge_region_end < vsn->top() &&

   119                        _name, METACHUNK_FORMAT_ARGS(c), target_level);

    99       !ocmap->chunk_starts_at_address(p_merge_region_end)) {

   120 

   100     return false;

   121   const chklvl_t orig_level = c->level();

   101   }

   122   c = c->vsnode()->split(target_level, c, &_chunks);

   102 

   123 

   103   // Now check if the prospective merge area contains live chunks. If it does we cannot merge.

   124   // Splitting should never fail.

   104   if (ocmap->is_region_in_use(p_merge_region_start, target_chunk_word_size)) {

   125   assert(c != NULL, "Split failed");

   105     return false;

   126   assert(c->level() == target_level, "Sanity");

   106   }

   127 

   107 

   128   DEBUG_ONLY(c->verify(false));

   108   // Success! Remove all chunks in this region...

   129 

   109   log_trace(gc, metaspace, freelist)("%s: coalescing chunks in area [%p-%p)...",

   130   DEBUG_ONLY(verify_locked(true);)

   110     (is_class() ? "class space" : "metaspace"),

   131 

   111     p_merge_region_start, p_merge_region_end);

   132   DEBUG_ONLY(c->vsnode()->verify(true);)

   112 

   133 

   113   const int num_chunks_removed =

   134   return c;

   114     remove_chunks_in_area(p_merge_region_start, target_chunk_word_size);

   135 }

   115 

   136 

   116   // ... and create a single new bigger chunk.

   137 // Get a chunk and be smart about it.

   117   Metachunk* const p_new_chunk =

   138 // - 1) Attempt to find a free chunk of exactly the pref_level level

   118       ::new (p_merge_region_start) Metachunk(target_chunk_type, is_class(), target_chunk_word_size, vsn);

   139 // - 2) Failing that, attempt to find a chunk smaller or equal the max level.

   119   assert(p_new_chunk == (Metachunk*)p_merge_region_start, "Sanity");

   140 // - 3) Failing that, attempt to find a free chunk of larger size and split it.

   120   p_new_chunk->set_origin(origin_merge);

   141 // - 4) Failing that, attempt to allocate a new chunk from the connected virtual space.

   121 

   142 // - Failing that, give up and return NULL.

   122   log_trace(gc, metaspace, freelist)("%s: created coalesced chunk at %p, size " SIZE_FORMAT_HEX ".",

   143 // Note: this is not guaranteed to return a *committed* chunk. The chunk manager will

   123     (is_class() ? "class space" : "metaspace"),

   144 //   attempt to commit the returned chunk according to constants::committed_words_on_fresh_chunks;

   124     p_new_chunk, p_new_chunk->word_size() * sizeof(MetaWord));

   145 //   but this may fail if we hit a commit limit. In that case, a partly uncommit chunk

   125 

   146 //   will be returned, and the commit is attempted again when we allocate from the chunk's

   126   // Fix occupancy map: remove old start bits of the small chunks and set new start bit.

   147 //   uncommitted area. See also Metachunk::allocate.

   127   ocmap->wipe_chunk_start_bits_in_region(p_merge_region_start, target_chunk_word_size);

   148 Metachunk* ChunkManager::get_chunk(chklvl_t max_level, chklvl_t pref_level) {

   128   ocmap->set_chunk_starts_at_address(p_merge_region_start, true);

   149 

   129 

   150   MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

   130   // Mark chunk as free. Note: it is not necessary to update the occupancy

   151 

   131   // map in-use map, because the old chunks were also free, so nothing

   152   DEBUG_ONLY(verify_locked(false);)

   132   // should have changed.

   153 

   133   p_new_chunk->set_is_tagged_free(true);

   154   DEBUG_ONLY(chklvl::check_valid_level(max_level);)

   134 

   155   DEBUG_ONLY(chklvl::check_valid_level(pref_level);)

   135   // Add new chunk to its freelist.

   156   assert(max_level >= pref_level, "invalid level.");

   136   ChunkList* const list = free_chunks(target_chunk_type);

   157 

   137   list->return_chunk_at_head(p_new_chunk);

   158   Metachunk* c = NULL;

   138 

   159 

   139   // And adjust ChunkManager:: _free_chunks_count (_free_chunks_total

   160   // Tracing

   140   // should not have changed, because the size of the space should be the same)

   161   log_debug(metaspace)("ChunkManager %s: get chunk: max " CHKLVL_FORMAT " (" SIZE_FORMAT "),"

   141   _free_chunks_count -= num_chunks_removed;

   162                        "preferred " CHKLVL_FORMAT " (" SIZE_FORMAT ").",

   142   _free_chunks_count ++;

   163                        _name, max_level, chklvl::word_size_for_level(max_level),

   143 

   164                        pref_level, chklvl::word_size_for_level(pref_level));

   144   // VirtualSpaceNode::chunk_count does not have to be modified:

   165 

   145   // it means "number of active (non-free) chunks", so merging free chunks

   166   // 1) Attempt to find a free chunk of exactly the pref_level level

   146   // should not affect that count.

   167   c = remove_first_chunk_at_level(pref_level);

   147 

   168 

   148   // At the end of a chunk merge, run verification tests.

   169   // Todo:

   170   //

   171   // We need to meditate about steps (2) and (3) a bit more.

   172   // By simply preferring to reuse small chunks vs splitting larger chunks we may emphasize

   173   // fragmentation, strangely enough, if callers wanting medium sized chunks take small chunks

   174   // instead, and taking them away from the many users which prefer small chunks.

   175   // Alternatives:

   176   // - alternating between (2) (3) and (3) (2)

   177   // - mixing (2) and (3) into one loop with a growing delta, and maybe a "hesitance" barrier function

   178   // - keeping track of chunk demand and adding this into the equation: if e.g. 4K chunks were heavily

   179   //   preferred in the past, maybe for callers wanting larger chunks leave those alone.

   180   // - Take into account which chunks are committed? This would require some extra bookkeeping...

   181 

   182   // 2) Failing that, attempt to find a chunk smaller or equal the minimal level.

   183   if (c == NULL) {

   184     for (chklvl_t lvl = pref_level + 1; lvl <= max_level; lvl ++) {

   185       c = remove_first_chunk_at_level(lvl);

   186       if (c != NULL) {

   187         break;

   188       }

   189     }

   190   }

   191 

   192   // 3) Failing that, attempt to find a free chunk of larger size and split it.

   193   if (c == NULL) {

   194     for (chklvl_t lvl = pref_level - 1; lvl >= chklvl::ROOT_CHUNK_LEVEL; lvl --) {

   195       c = remove_first_chunk_at_level(lvl);

   196       if (c != NULL) {

   197         // Split chunk; add splinters to freelist

   198         c = split_chunk_and_add_splinters(c, pref_level);

   199         break;

   200       }

   201     }

   202   }

   203 

   204   // 4) Failing that, attempt to allocate a new chunk from the connected virtual space.

   205   if (c == NULL) {

   206 

   207     // Tracing

   208     log_debug(metaspace)("ChunkManager %s: need new root chunk.", _name);

   209 

   210     c = _vslist->allocate_root_chunk();

   211 

   212     // This should always work. Note that getting the root chunk may not mean we committed memory.

   213     assert(c != NULL, "Unexpected");

   214     assert(c->level() == chklvl::LOWEST_CHUNK_LEVEL, "Not a root chunk?");

   215 

   216     // Split this root chunk to the desired chunk size.

   217     if (pref_level > c->level()) {

   218       c = split_chunk_and_add_splinters(c, pref_level);

   219     }

   220   }

   221 

   222   // Note that we should at this point have a chunk; should always work. If we hit

   223   // a commit limit in the meantime, the chunk may still be uncommitted, but the chunk

   224   // itself should exist now.

   225   assert(c != NULL, "Unexpected");

   226 

   227   // Before returning the chunk, attempt to commit it according to the handout rules.

   228   // If that fails, we ignore the error and return the uncommitted chunk.

   229   if (commit_chunk_before_handout(c) == false) {

   230     log_info(gc, metaspace)("Failed to commit chunk prior to handout.");

   231   }

   232 

   233   // Any chunk returned from ChunkManager shall be marked as in use.

   234   c->set_in_use();

   235 

   236   DEBUG_ONLY(verify_locked(false);)

   237 

   238   log_debug(metaspace)("ChunkManager %s: handing out chunk " METACHUNK_FORMAT ".",

   239                        _name, METACHUNK_FORMAT_ARGS(c));

   240 

   241 

   242   DEBUG_ONLY(InternalStats::inc_num_chunks_taken_from_freelist();)

   243 

   244   return c;

   245 

   246 } // ChunkManager::get_chunk

   247 

   248 

   249 // Return a single chunk to the ChunkManager and adjust accounting. May merge chunk

   250 //  with neighbors.

   251 // As a side effect this removes the chunk from whatever list it has been in previously.

   252 // Happens after a Classloader was unloaded and releases its metaspace chunks.

   253 // !! Note: this may invalidate the chunk. Do not access the chunk after

   254 //    this function returns !!

   255 void ChunkManager::return_chunk(Metachunk* c) {

   256 

   257   MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

   258 

   259   log_debug(metaspace)("ChunkManager %s: returning chunk " METACHUNK_FORMAT ".",

   260                        _name, METACHUNK_FORMAT_ARGS(c));

   261 

   262   DEBUG_ONLY(verify_locked(false);)

   263   DEBUG_ONLY(c->verify(false);)

   264 

   265   assert(!_chunks.contains(c), "A chunk to be added to the freelist must not be in the freelist already.");

   266 

   267   assert(c->is_in_use(), "Unexpected chunk state");

   268   assert(!c->in_list(), "Remove from list first");

   269   c->set_free();

   270   c->reset_used_words();

   271 

   272   const chklvl_t orig_lvl = c->level();

   273 

   274   Metachunk* merged = NULL;

   275   if (!c->is_root_chunk()) {

   276     // Only attempt merging if we are not of the lowest level already.

   277     merged = c->vsnode()->merge(c, &_chunks);

   278   }

   279 

   280   if (merged != NULL) {

   281 

   282     DEBUG_ONLY(merged->verify(false));

   283 

   284     // We did merge our chunk into a different chunk.

   285 

   286     // We did merge chunks and now have a bigger chunk.

   287     assert(merged->level() < orig_lvl, "Sanity");

   288 

   289     log_trace(metaspace)("ChunkManager %s: merged into chunk " METACHUNK_FORMAT ".",

   290                          _name, METACHUNK_FORMAT_ARGS(merged));

   291 

   292     c = merged;

   293 

   294   }

   295 

   296   if (Settings::uncommit_on_return() &&

   297       Settings::uncommit_on_return_min_word_size() <= c->word_size())

   298   {

   299     log_trace(metaspace)("ChunkManager %s: uncommitting free chunk " METACHUNK_FORMAT ".",

   300                          _name, METACHUNK_FORMAT_ARGS(c));

   301     c->uncommit_locked();

   302   }

   303 

   304   return_chunk_simple(c);

   305 

   306   DEBUG_ONLY(verify_locked(false);)

   307   DEBUG_ONLY(c->vsnode()->verify(true);)

   308 

   309   DEBUG_ONLY(InternalStats::inc_num_chunks_returned_to_freelist();)

   310 

   311 }

   312 

   313 // Given a chunk c, which must be "in use" and must not be a root chunk, attempt to

   314 // enlarge it in place by claiming its trailing buddy.

   315 //

   316 // This will only work if c is the leader of the buddy pair and the trailing buddy is free.

   317 //

   318 // If successful, the follower chunk will be removed from the freelists, the leader chunk c will

   319 // double in size (level decreased by one).

   320 //

   321 // On success, true is returned, false otherwise.

   322 bool ChunkManager::attempt_enlarge_chunk(Metachunk* c) {

   323   MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

   324   return c->vsnode()->attempt_enlarge_chunk(c, &_chunks);

   325 }

   326 

   327 static void print_word_size_delta(outputStream* st, size_t word_size_1, size_t word_size_2) {

   328   if (word_size_1 == word_size_2) {

   329     print_scaled_words(st, word_size_1);

   330     st->print (" (no change)");

   331   } else {

   332     print_scaled_words(st, word_size_1);

   333     st->print("->");

   334     print_scaled_words(st, word_size_2);

   335     st->print(" (");

   336     if (word_size_2 <= word_size_1) {

   337       st->print("-");

   338       print_scaled_words(st, word_size_1 - word_size_2);

   339     } else {

   340       st->print("+");

   341       print_scaled_words(st, word_size_2 - word_size_1);

   342     }

   343     st->print(")");

   344   }

   345 }

   346 

   347 // Attempt to reclaim free areas in metaspace wholesale:

   348 // - first, attempt to purge nodes of the backing virtual space. This can only be successful

   349 //   if whole nodes are only containing free chunks, so it highly depends on fragmentation.

   350 // - then, it will uncommit areas of free chunks according to the rules laid down in

   351 //   settings (see settings.hpp).

   352 void ChunkManager::wholesale_reclaim() {

   353 

   354   MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

   355 

   356   log_info(metaspace)("ChunkManager \"%s\": reclaiming memory...", _name);

   357 

   358   const size_t reserved_before = _vslist->reserved_words();

   359   const size_t committed_before = _vslist->committed_words();

   360   int num_nodes_purged = 0;

   361 

   362   if (Settings::delete_nodes_on_purge()) {

   363     num_nodes_purged = _vslist->purge(&_chunks);

   364     DEBUG_ONLY(InternalStats::inc_num_purges();)

   365   }

   366 

   367   if (Settings::uncommit_on_purge()) {

   368     const chklvl_t max_level =

   369         chklvl::level_fitting_word_size(Settings::uncommit_on_purge_min_word_size());

   370     for (chklvl_t l = chklvl::LOWEST_CHUNK_LEVEL;

   371          l <= max_level;

   372          l ++)

   373     {

   374       for (Metachunk* c = _chunks.first_at_level(l); c != NULL; c = c->next()) {

   375         c->uncommit_locked();

   376       }

   377     }

   378     DEBUG_ONLY(InternalStats::inc_num_wholesale_uncommits();)

   379   }

   380 

   381   const size_t reserved_after = _vslist->reserved_words();

   382   const size_t committed_after = _vslist->committed_words();

   383 

   384   // Print a nice report.

   385   if (reserved_after == reserved_before && committed_after == committed_before) {

   386     log_info(metaspace)("ChunkManager %s: ... nothing reclaimed.", _name);

   387   } else {

   388     LogTarget(Info, metaspace) lt;

   389     if (lt.is_enabled()) {

   390       LogStream ls(lt);

   391       ls.print_cr("ChunkManager %s: finished reclaiming memory: ", _name);

   392 

   393       ls.print("reserved: ");

   394       print_word_size_delta(&ls, reserved_before, reserved_after);

   395       ls.cr();

   396 

   397       ls.print("committed: ");

   398       print_word_size_delta(&ls, committed_before, committed_after);

   399       ls.cr();

   400 

   401       ls.print_cr("full nodes purged: %d", num_nodes_purged);

   402     }

   403   }

   404 

   405   DEBUG_ONLY(_vslist->verify_locked(true));

   406   DEBUG_ONLY(verify_locked(true));

   407 

   408 }

   409 

   410 

   411 ChunkManager* ChunkManager::_chunkmanager_class = NULL;

   412 ChunkManager* ChunkManager::_chunkmanager_nonclass = NULL;

   413 

   414 void ChunkManager::set_chunkmanager_class(ChunkManager* cm) {

   415   assert(_chunkmanager_class == NULL, "Sanity");

   416   _chunkmanager_class = cm;

   417 }

   418 

   419 void ChunkManager::set_chunkmanager_nonclass(ChunkManager* cm) {

   420   assert(_chunkmanager_nonclass == NULL, "Sanity");

   421   _chunkmanager_nonclass = cm;

   422 }

   423 

   424 

   425 // Update statistics.

   426 void ChunkManager::add_to_statistics(cm_stats_t* out) const {

   427 

   428   MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

   429 

   430   for (chklvl_t l = chklvl::ROOT_CHUNK_LEVEL; l <= chklvl::HIGHEST_CHUNK_LEVEL; l ++) {

   431     out->num_chunks[l] += _chunks.num_chunks_at_level(l);

   432     out->committed_word_size[l] += _chunks.committed_word_size_at_level(l);

   433   }

   434 

   435   DEBUG_ONLY(out->verify();)

   436 

   437 }

   438 

   230   MutexLocker cl(MetaspaceExpand_lock,

   442   MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

   231                      Mutex::_no_safepoint_check_flag);

   443   verify_locked(slow);

   232   locked_verify(slow);

   444 }

   233 }

   445 

   234 

   446 void ChunkManager::verify_locked(bool slow) const {

   235 void ChunkManager::locked_verify(bool slow) const {

   447 

   236   log_trace(gc, metaspace, freelist)("verifying %s chunkmanager (%s).",

   448   assert_lock_strong(MetaspaceExpand_lock);

   237     (is_class() ? "class space" : "metaspace"), (slow ? "slow" : "quick"));

   449 

   238 

   450   assert(_vslist != NULL, "No vslist");

   239   assert_lock_strong(MetaspaceExpand_lock);

   451 

   240 

   452   // This checks that the lists are wired up correctly, that the counters are valid and

   241   size_t chunks_counted = 0;

   453   // that each chunk is (only) in its correct list.

   242   size_t wordsize_chunks_counted = 0;

   454   _chunks.verify(true);

   243   for (ChunkIndex i = ZeroIndex; i < NumberOfFreeLists; i = next_chunk_index(i)) {

   455 

   244     const ChunkList* list = _free_chunks + i;

   456   // Need to check that each chunk is free..._size = 0;

   245     if (list != NULL) {

   457   for (chklvl_t l = chklvl::LOWEST_CHUNK_LEVEL; l <= chklvl::HIGHEST_CHUNK_LEVEL; l ++) {

   246       Metachunk* chunk = list->head();

   458     for (const Metachunk* c = _chunks.first_at_level(l); c != NULL; c = c->next()) {

   247       while (chunk) {

   459       assert(c->is_free(), "Chunk is not free.");

   248         if (slow) {

   460       assert(c->used_words() == 0, "Chunk should have not used words.");

   249           do_verify_chunk(chunk);

   461     }

   250         }

   462   }

   251         assert(chunk->is_tagged_free(), "Chunk should be tagged as free.");

   463 

   252         chunks_counted ++;

   464 }

   253         wordsize_chunks_counted += chunk->size();

   465 

   254         chunk = chunk->next();

   255       }

   256     }

   257   }

   258 

   259   chunks_counted += humongous_dictionary()->total_free_blocks();

   260   wordsize_chunks_counted += humongous_dictionary()->total_size();

   261 

   262   assert(chunks_counted == _free_chunks_count && wordsize_chunks_counted == _free_chunks_total,

   263          "freelist accounting mismatch: "

   264          "we think: " SIZE_FORMAT " chunks, total " SIZE_FORMAT " words, "

   265          "reality: " SIZE_FORMAT " chunks, total " SIZE_FORMAT " words.",

   266          _free_chunks_count, _free_chunks_total,

   267          chunks_counted, wordsize_chunks_counted);

   268 }

   271 void ChunkManager::locked_print_free_chunks(outputStream* st) {

   468 void ChunkManager::print_on(outputStream* st) const {

   272   assert_lock_strong(MetaspaceExpand_lock);

   469   MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

   273   st->print_cr("Free chunk total " SIZE_FORMAT "  count " SIZE_FORMAT,

   470   print_on_locked(st);

   274                 _free_chunks_total, _free_chunks_count);

   471 }

   275 }

   472 

   276 

   473 void ChunkManager::print_on_locked(outputStream* st) const {

   277 ChunkList* ChunkManager::free_chunks(ChunkIndex index) {

   474   assert_lock_strong(MetaspaceExpand_lock);

   278   assert(index == SpecializedIndex || index == SmallIndex || index == MediumIndex,

   475   st->print_cr("cm %s: %d chunks, total word size: " SIZE_FORMAT ", committed word size: " SIZE_FORMAT, _name,

   279          "Bad index: %d", (int)index);

   476                total_num_chunks(), total_word_size(), _chunks.total_committed_word_size());

   280   return &_free_chunks[index];

   477   _chunks.print_on(st);

   281 }

   282 

   283 ChunkList* ChunkManager::find_free_chunks_list(size_t word_size) {

   284   ChunkIndex index = list_index(word_size);

   285   assert(index < HumongousIndex, "No humongous list");

   286   return free_chunks(index);

   287 }

   288 

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

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

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

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

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

   294 Metachunk* ChunkManager::split_chunk(size_t target_chunk_word_size, Metachunk* larger_chunk) {

   295   assert(larger_chunk->word_size() > target_chunk_word_size, "Sanity");

   296 

   297   const ChunkIndex larger_chunk_index = larger_chunk->get_chunk_type();

   298   const ChunkIndex target_chunk_index = get_chunk_type_by_size(target_chunk_word_size, is_class());

   299 

   300   MetaWord* const region_start = (MetaWord*)larger_chunk;

   301   const size_t region_word_len = larger_chunk->word_size();

   302   MetaWord* const region_end = region_start + region_word_len;

   303   VirtualSpaceNode* const vsn = larger_chunk->container();

   304   OccupancyMap* const ocmap = vsn->occupancy_map();

   305 

   306   // Any larger non-humongous chunk size is a multiple of any smaller chunk size.

   307   // Since non-humongous chunks are aligned to their chunk size, the larger chunk should start

   308   // at an address suitable to place the smaller target chunk.

   309   assert_is_aligned(region_start, target_chunk_word_size);

   310 

   311   // Remove old chunk.

   312   free_chunks(larger_chunk_index)->remove_chunk(larger_chunk);

   313   larger_chunk->remove_sentinel();

   314 

   315   // Prevent access to the old chunk from here on.

   316   larger_chunk = NULL;

   317   // ... and wipe it.

   318   DEBUG_ONLY(memset(region_start, 0xfe, region_word_len * BytesPerWord));

   319 

   320   // In its place create first the target chunk...

   321   MetaWord* p = region_start;

   322   Metachunk* target_chunk = ::new (p) Metachunk(target_chunk_index, is_class(), target_chunk_word_size, vsn);

   323   assert(target_chunk == (Metachunk*)p, "Sanity");

   324   target_chunk->set_origin(origin_split);

   325 

   326   // Note: we do not need to mark its start in the occupancy map

   327   // because it coincides with the old chunk start.

   328 

   329   // Mark chunk as free and return to the freelist.

   330   do_update_in_use_info_for_chunk(target_chunk, false);

   331   free_chunks(target_chunk_index)->return_chunk_at_head(target_chunk);

   332 

   333   // This chunk should now be valid and can be verified.

   334   DEBUG_ONLY(do_verify_chunk(target_chunk));

   335 

   336   // In the remaining space create the remainder chunks.

   337   p += target_chunk->word_size();

   338   assert(p < region_end, "Sanity");

   339 

   340   while (p < region_end) {

   341 

   342     // Find the largest chunk size which fits the alignment requirements at address p.

   343     ChunkIndex this_chunk_index = prev_chunk_index(larger_chunk_index);

   344     size_t this_chunk_word_size = 0;

   345     for(;;) {

   346       this_chunk_word_size = get_size_for_nonhumongous_chunktype(this_chunk_index, is_class());

   347       if (is_aligned(p, this_chunk_word_size * BytesPerWord)) {

   348         break;

   349       } else {

   350         this_chunk_index = prev_chunk_index(this_chunk_index);

   351         assert(this_chunk_index >= target_chunk_index, "Sanity");

   352       }

   353     }

   354 

   355     assert(this_chunk_word_size >= target_chunk_word_size, "Sanity");

   356     assert(is_aligned(p, this_chunk_word_size * BytesPerWord), "Sanity");

   357     assert(p + this_chunk_word_size <= region_end, "Sanity");

   358 

   359     // Create splitting chunk.

   360     Metachunk* this_chunk = ::new (p) Metachunk(this_chunk_index, is_class(), this_chunk_word_size, vsn);

   361     assert(this_chunk == (Metachunk*)p, "Sanity");

   362     this_chunk->set_origin(origin_split);

   363     ocmap->set_chunk_starts_at_address(p, true);

   364     do_update_in_use_info_for_chunk(this_chunk, false);

   365 

   366     // This chunk should be valid and can be verified.

   367     DEBUG_ONLY(do_verify_chunk(this_chunk));

   368 

   369     // Return this chunk to freelist and correct counter.

   370     free_chunks(this_chunk_index)->return_chunk_at_head(this_chunk);

   371     _free_chunks_count ++;

   372 

   373     log_trace(gc, metaspace, freelist)("Created chunk at " PTR_FORMAT ", word size "

   374       SIZE_FORMAT_HEX " (%s), in split region [" PTR_FORMAT "..." PTR_FORMAT ").",

   375       p2i(this_chunk), this_chunk->word_size(), chunk_size_name(this_chunk_index),

   376       p2i(region_start), p2i(region_end));

   377 

   378     p += this_chunk_word_size;

   379 

   380   }

   381 

   382   // Note: at this point, the VirtualSpaceNode is invalid since we split a chunk and

   383   // did not yet hand out part of that split; so, vsn->verify_free_chunks_are_ideally_merged()

   384   // would assert. Instead, do all verifications in the caller.

   385 

   386   DEBUG_ONLY(g_internal_statistics.num_chunk_splits ++);

   387 

   388   return target_chunk;

   389 }

   390 

   391 Metachunk* ChunkManager::free_chunks_get(size_t word_size) {

   392   assert_lock_strong(MetaspaceExpand_lock);

   393 

   394   Metachunk* chunk = NULL;

   395   bool we_did_split_a_chunk = false;

   396 

   397   if (list_index(word_size) != HumongousIndex) {

   398 

   399     ChunkList* free_list = find_free_chunks_list(word_size);

   400     assert(free_list != NULL, "Sanity check");

   401 

   402     chunk = free_list->head();

   403 

   404     if (chunk == NULL) {

   405       // Split large chunks into smaller chunks if there are no smaller chunks, just large chunks.

   406       // This is the counterpart of the coalescing-upon-chunk-return.

   407 

   408       ChunkIndex target_chunk_index = get_chunk_type_by_size(word_size, is_class());

   409 

   410       // Is there a larger chunk we could split?

   411       Metachunk* larger_chunk = NULL;

   412       ChunkIndex larger_chunk_index = next_chunk_index(target_chunk_index);

   413       while (larger_chunk == NULL && larger_chunk_index < NumberOfFreeLists) {

   414         larger_chunk = free_chunks(larger_chunk_index)->head();

   415         if (larger_chunk == NULL) {

   416           larger_chunk_index = next_chunk_index(larger_chunk_index);

   417         }

   418       }

   419 

   420       if (larger_chunk != NULL) {

   421         assert(larger_chunk->word_size() > word_size, "Sanity");

   422         assert(larger_chunk->get_chunk_type() == larger_chunk_index, "Sanity");

   423 

   424         // We found a larger chunk. Lets split it up:

   425         // - remove old chunk

   426         // - in its place, create new smaller chunks, with at least one chunk

   427         //   being of target size, the others sized as large as possible. This

   428         //   is to make sure the resulting chunks are "as coalesced as possible"

   429         //   (similar to VirtualSpaceNode::retire()).

   430         // Note: during this operation both ChunkManager and VirtualSpaceNode

   431         //  are temporarily invalid, so be careful with asserts.

   432 

   433         log_trace(gc, metaspace, freelist)("%s: splitting chunk " PTR_FORMAT

   434            ", word size " SIZE_FORMAT_HEX " (%s), to get a chunk of word size " SIZE_FORMAT_HEX " (%s)...",

   435           (is_class() ? "class space" : "metaspace"), p2i(larger_chunk), larger_chunk->word_size(),

   436           chunk_size_name(larger_chunk_index), word_size, chunk_size_name(target_chunk_index));

   437 

   438         chunk = split_chunk(word_size, larger_chunk);

   439 

   440         // This should have worked.

   441         assert(chunk != NULL, "Sanity");

   442         assert(chunk->word_size() == word_size, "Sanity");

   443         assert(chunk->is_tagged_free(), "Sanity");

   444 

   445         we_did_split_a_chunk = true;

   446 

   447       }

   448     }

   449 

   450     if (chunk == NULL) {

   451       return NULL;

   452     }

   453 

   454     // Remove the chunk as the head of the list.

   455     free_list->remove_chunk(chunk);

   456 

   457     log_trace(gc, metaspace, freelist)("ChunkManager::free_chunks_get: free_list: " PTR_FORMAT " chunks left: " SSIZE_FORMAT ".",

   458                                        p2i(free_list), free_list->count());

   459 

   460   } else {

   461     chunk = humongous_dictionary()->get_chunk(word_size);

   462 

   463     if (chunk == NULL) {

   464       return NULL;

   465     }

   466 

   467     log_trace(gc, metaspace, alloc)("Free list allocate humongous chunk size " SIZE_FORMAT " for requested size " SIZE_FORMAT " waste " SIZE_FORMAT,

   468                                     chunk->word_size(), word_size, chunk->word_size() - word_size);

   469   }

   470 

   471   // Chunk has been removed from the chunk manager; update counters.

   472   account_for_removed_chunk(chunk);

   473   do_update_in_use_info_for_chunk(chunk, true);

   474   chunk->container()->inc_container_count();

   475   chunk->inc_use_count();

   476 

   477   // Remove it from the links to this freelist

   478   chunk->set_next(NULL);

   479   chunk->set_prev(NULL);

   480 

   481   // Run some verifications (some more if we did a chunk split)

   482 #ifdef ASSERT

   483 

   484   EVERY_NTH(VerifyMetaspaceInterval)

   485     // Be extra verify-y when chunk split happened.

   486     locked_verify(true);

   487     VirtualSpaceNode* const vsn = chunk->container();

   488     vsn->verify(true);

   489     if (we_did_split_a_chunk) {

   490       vsn->verify_free_chunks_are_ideally_merged();

   491     }

   492   END_EVERY_NTH

   493 

   494   g_internal_statistics.num_chunks_removed_from_freelist ++;

   495 

   496 #endif

   497 

   498   return chunk;

   499 }

   500 

   501 Metachunk* ChunkManager::chunk_freelist_allocate(size_t word_size) {

   502   assert_lock_strong(MetaspaceExpand_lock);

   503 

   504   // Take from the beginning of the list

   505   Metachunk* chunk = free_chunks_get(word_size);

   506   if (chunk == NULL) {

   507     return NULL;

   508   }

   509 

   510   assert((word_size <= chunk->word_size()) ||

   511          (list_index(chunk->word_size()) == HumongousIndex),

   512          "Non-humongous variable sized chunk");

   513   LogTarget(Trace, gc, metaspace, freelist) lt;

   514   if (lt.is_enabled()) {

   515     size_t list_count;

   516     if (list_index(word_size) < HumongousIndex) {

   517       ChunkList* list = find_free_chunks_list(word_size);

   518       list_count = list->count();

   519     } else {

   520       list_count = humongous_dictionary()->total_count();

   521     }

   522     LogStream ls(lt);

   523     ls.print("ChunkManager::chunk_freelist_allocate: " PTR_FORMAT " chunk " PTR_FORMAT "  size " SIZE_FORMAT " count " SIZE_FORMAT " ",

   524              p2i(this), p2i(chunk), chunk->word_size(), list_count);

   525     ResourceMark rm;

   526     locked_print_free_chunks(&ls);

   527   }

   528 

   529   return chunk;

   530 }

   531 

   532 void ChunkManager::return_single_chunk(Metachunk* chunk) {

   533 

   534 #ifdef ASSERT

   535   EVERY_NTH(VerifyMetaspaceInterval)

   536     this->locked_verify(false);

   537     do_verify_chunk(chunk);

   538   END_EVERY_NTH

   539 #endif

   540 

   541   const ChunkIndex index = chunk->get_chunk_type();

   542   assert_lock_strong(MetaspaceExpand_lock);

   543   DEBUG_ONLY(g_internal_statistics.num_chunks_added_to_freelist ++;)

   544   assert(chunk != NULL, "Expected chunk.");

   545   assert(chunk->container() != NULL, "Container should have been set.");

   546   assert(chunk->is_tagged_free() == false, "Chunk should be in use.");

   547   index_bounds_check(index);

   548 

   549   // Note: mangle *before* returning the chunk to the freelist or dictionary. It does not

   550   // matter for the freelist (non-humongous chunks), but the humongous chunk dictionary

   551   // keeps tree node pointers in the chunk payload area which mangle will overwrite.

   552   DEBUG_ONLY(chunk->mangle(badMetaWordVal);)

   553 

   554   // may need node for verification later after chunk may have been merged away.

   555   DEBUG_ONLY(VirtualSpaceNode* vsn = chunk->container(); )

   556 

   557   if (index != HumongousIndex) {

   558     // Return non-humongous chunk to freelist.

   559     ChunkList* list = free_chunks(index);

   560     assert(list->size() == chunk->word_size(), "Wrong chunk type.");

   561     list->return_chunk_at_head(chunk);

   562     log_trace(gc, metaspace, freelist)("returned one %s chunk at " PTR_FORMAT " to freelist.",

   563         chunk_size_name(index), p2i(chunk));

   564   } else {

   565     // Return humongous chunk to dictionary.

   566     assert(chunk->word_size() > free_chunks(MediumIndex)->size(), "Wrong chunk type.");

   567     assert(chunk->word_size() % free_chunks(SpecializedIndex)->size() == 0,

   568            "Humongous chunk has wrong alignment.");

   569     _humongous_dictionary.return_chunk(chunk);

   570     log_trace(gc, metaspace, freelist)("returned one %s chunk at " PTR_FORMAT " (word size " SIZE_FORMAT ") to freelist.",

   571         chunk_size_name(index), p2i(chunk), chunk->word_size());

   572   }

   573   chunk->container()->dec_container_count();

   574   do_update_in_use_info_for_chunk(chunk, false);

   575 

   576   // Chunk has been added; update counters.

   577   account_for_added_chunk(chunk);

   578 

   579   // Attempt coalesce returned chunks with its neighboring chunks:

   580   // if this chunk is small or special, attempt to coalesce to a medium chunk.

   581   if (index == SmallIndex || index == SpecializedIndex) {

   582     if (!attempt_to_coalesce_around_chunk(chunk, MediumIndex)) {

   583       // This did not work. But if this chunk is special, we still may form a small chunk?

   584       if (index == SpecializedIndex) {

   585         if (!attempt_to_coalesce_around_chunk(chunk, SmallIndex)) {

   586           // give up.

   587         }

   588       }

   589     }

   590   }

   591 

   592   // From here on do not access chunk anymore, it may have been merged with another chunk.

   593 

   594 #ifdef ASSERT

   595   EVERY_NTH(VerifyMetaspaceInterval)

   596     this->locked_verify(true);

   597     vsn->verify(true);

   598     vsn->verify_free_chunks_are_ideally_merged();

   599   END_EVERY_NTH

   600 #endif

   601 

   602 }

   603 

   604 void ChunkManager::return_chunk_list(Metachunk* chunks) {

   605   if (chunks == NULL) {

   606     return;

   607   }

   608   LogTarget(Trace, gc, metaspace, freelist) log;

   609   if (log.is_enabled()) { // tracing

   610     log.print("returning list of chunks...");

   611   }

   612   unsigned num_chunks_returned = 0;

   613   size_t size_chunks_returned = 0;

   614   Metachunk* cur = chunks;

   615   while (cur != NULL) {

   616     // Capture the next link before it is changed

   617     // by the call to return_chunk_at_head();

   618     Metachunk* next = cur->next();

   619     if (log.is_enabled()) { // tracing

   620       num_chunks_returned ++;

   621       size_chunks_returned += cur->word_size();

   622     }

   623     return_single_chunk(cur);

   624     cur = next;

   625   }

   626   if (log.is_enabled()) { // tracing

   627     log.print("returned %u chunks to freelist, total word size " SIZE_FORMAT ".",

   628         num_chunks_returned, size_chunks_returned);

   629   }

   630 }

   631 

   632 void ChunkManager::collect_statistics(ChunkManagerStatistics* out) const {

   633   MutexLocker cl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

   634   for (ChunkIndex i = ZeroIndex; i < NumberOfInUseLists; i = next_chunk_index(i)) {

   635     out->chunk_stats(i).add(num_free_chunks(i), size_free_chunks_in_bytes(i) / sizeof(MetaWord));

   636   }