1 /*

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

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

     4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     5  *

     6  * This code is free software; you can redistribute it and/or modify it

     7  * under the terms of the GNU General Public License version 2 only, as

     8  * published by the Free Software Foundation.

     9  *

    10  * This code is distributed in the hope that it will be useful, but WITHOUT

    11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    13  * version 2 for more details (a copy is included in the LICENSE file that

    14  * accompanied this code).

    15  *

    16  * You should have received a copy of the GNU General Public License version

    17  * 2 along with this work; if not, write to the Free Software Foundation,

    18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    19  *

    20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    21  * or visit www.oracle.com if you need additional information or have any

    22  * questions.

    23  *

    24  */

    25 #include "precompiled.hpp"

    26 

    27 #include "logging/log.hpp"

    28 #include "memory/allocation.hpp"

    29 #include "memory/metaspace/chunkHeaderPool.hpp"

    30 #include "memory/metaspace/chunkManager.hpp"

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

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

    33 #include "memory/metaspace/metaspaceCommon.hpp"

    34 #include "memory/metaspace/rootChunkArea.hpp"

    35 #include "utilities/debug.hpp"

    36 #include "utilities/globalDefinitions.hpp"

    37 

    38 namespace metaspace {

    39 

    40 RootChunkArea::RootChunkArea(const MetaWord* base)

    41   : _base(base), _first_chunk(NULL)

    42 {}

    43 

    44 RootChunkArea::~RootChunkArea() {

    45   // This is called when a VirtualSpaceNode is destructed (purged).

    46   // All chunks should be free of course. In fact, there should only

    47   // be one chunk, since all free chunks should have been merged.

    48   if (_first_chunk != NULL) {

    49     assert(_first_chunk->is_root_chunk() && _first_chunk->is_free(),

    50            "Cannot delete root chunk area if not all chunks are free.");

    51     ChunkHeaderPool::pool().return_chunk_header(_first_chunk);

    52   }

    53 }

    54 

    55 // Initialize: allocate a root node and a root chunk header; return the

    56 // root chunk header. It will be partly initialized.

    57 // Note: this just allocates a memory-less header; memory itself is allocated inside VirtualSpaceNode.

    58 Metachunk* RootChunkArea::alloc_root_chunk_header(VirtualSpaceNode* node) {

    59 

    60   assert(_first_chunk == 0, "already have a root");

    61 

    62   Metachunk* c = ChunkHeaderPool::pool().allocate_chunk_header();

    63   c->initialize(node, const_cast<MetaWord*>(_base), chklvl::ROOT_CHUNK_LEVEL);

    64 

    65   _first_chunk = c;

    66 

    67   return c;

    68 

    69 }

    70 

    71 

    72 

    73 // Given a chunk c, split it recursively until you get a chunk of the given target_level.

    74 //

    75 // The original chunk must not be part of a freelist.

    76 //

    77 // Returns pointer to the result chunk; the splitted-off chunks are added as

    78 //  free chunks to the freelists.

    79 //

    80 // Returns NULL if chunk cannot be split at least once.

    81 Metachunk* RootChunkArea::split(chklvl_t target_level, Metachunk* c, MetachunkListCluster* freelists) {

    82 

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

    84 

    85   // Splitting a chunk once works like this:

    86   //

    87   // For a given chunk we want to split:

    88   // - increase the chunk level (which halves its size)

    89   // - (but leave base address as it is since it will be the leader of the newly

    90   //    created chunk pair)

    91   // - then create a new chunk header of the same level, set its memory range

    92   //   to cover the second halfof the old chunk.

    93   // - wire them up (prev_in_vs/next_in_vs)

    94   // - return the follower chunk as "splinter chunk" in the splinters array.

    95 

    96   // Doing this multiple times will create a new free splinter chunk for every

    97   // level we split:

    98   //

    99   // A  <- original chunk

   100   //

   101   // B B  <- split into two halves

   102   //

   103   // C C B  <- first half split again

   104   //

   105   // D D C B  <- first half split again ...

   106   //

   107 

   108   // As an optimization, since we usually do not split once but multiple times,

   109   // to not do each split separately, since we would have to wire up prev_in_vs/next_in_vs

   110   // on every level just to tear it open in the next level when we reintroduce a new

   111   // half chunk splinter.

   112   // Instead, just split split split and delay building up the double linked list of the

   113   // new chunks at the end of all splits.

   114 

   115   DEBUG_ONLY(check_pointer(c->base());)

   116   assert(c->is_free(), "Can only split free chunks.");

   117 

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

   119   assert(target_level > c->level(), "Wrong target level");

   120 

   121   DEBUG_ONLY(verify(true);)

   122 

   123   const chklvl_t starting_level = c->level();

   124 

   125   Metachunk* result = c;

   126 

   127   log_trace(metaspace)("Splitting chunk @" PTR_FORMAT ", base " PTR_FORMAT ", level " CHKLVL_FORMAT "...",

   128                        p2i(c), p2i(c->base()), c->level());

   129 

   130   while (result->level() < target_level) {

   131 

   132     result->inc_level();

   133     Metachunk* splinter_chunk = ChunkHeaderPool::pool().allocate_chunk_header();

   134     splinter_chunk->initialize(result->vsnode(), result->end(), result->level());

   135 

   136     // Fix committed words info: If over the half of the original chunk was

   137     // committed, committed area spills over into the follower chunk.

   138     const size_t old_committed_words = result->committed_words();

   139     if (old_committed_words > result->word_size()) {

   140       result->set_committed_words(result->word_size());

   141       splinter_chunk->set_committed_words(old_committed_words - result->word_size());

   142     } else {

   143       splinter_chunk->set_committed_words(0);

   144     }

   145 

   146     // Insert splinter chunk into vs list

   147     if (result->next_in_vs() != NULL) {

   148       result->next_in_vs()->set_prev_in_vs(splinter_chunk);

   149     }

   150     splinter_chunk->set_next_in_vs(result->next_in_vs());

   151     splinter_chunk->set_prev_in_vs(result);

   152     result->set_next_in_vs(splinter_chunk);

   153 

   154     log_trace(metaspace)("Created splinter chunk @" PTR_FORMAT ", base " PTR_FORMAT ", level " CHKLVL_FORMAT "...",

   155                          p2i(splinter_chunk), p2i(splinter_chunk->base()), splinter_chunk->level());

   156 

   157     // Add splinter to free lists

   158     freelists->add(splinter_chunk);

   159 

   160     DEBUG_ONLY(InternalStats::inc_num_chunks_added_to_freelist_due_to_split();)

   161 

   162   }

   163 

   164   assert(result->level() == target_level, "Sanity");

   165 

   166   DEBUG_ONLY(verify(true);)

   167   DEBUG_ONLY(result->verify(true);)

   168 

   169   DEBUG_ONLY(InternalStats::inc_num_chunk_splits();)

   170 

   171   return result;

   172 

   173 }

   174 

   175 

   176 // Given a chunk, attempt to merge it recursively with its neighboring chunks.

   177 //

   178 // If successful (merged at least once), returns address of

   179 // the merged chunk; NULL otherwise.

   180 //

   181 // The merged chunks are removed from the freelists.

   182 //

   183 // !!! Please note that if this method returns a non-NULL value, the

   184 // original chunk will be invalid and should not be accessed anymore! !!!

   185 Metachunk* RootChunkArea::merge(Metachunk* c, MetachunkListCluster* freelists) {

   186 

   187   // Note rules:

   188   //

   189   // - a chunk always has a buddy, unless it is a root chunk.

   190   // - In that buddy pair, a chunk is either leader or follower.

   191   // - a chunk's base address is always aligned at its size.

   192   // - if chunk is leader, its base address is also aligned to the size of the next

   193   //   lower level, at least. A follower chunk is not.

   194 

   195   // How we merge once:

   196   //

   197   // For a given chunk c, which has to be free and non-root, we do:

   198   // - find out if we are the leader or the follower chunk

   199   // - if we are leader, next_in_vs must be the follower; if we are follower,

   200   //   prev_in_vs must be the leader. Now we have the buddy chunk.

   201   // - However, if the buddy chunk itself is split (of a level higher than us)

   202   //   we cannot merge.

   203   // - we can only merge if the buddy is of the same level as we are and it is

   204   //   free.

   205   // - Then we merge by simply removing the follower chunk from the address range

   206   //   linked list (returning the now useless header to the pool) and decreasing

   207   //   the leader chunk level by one. That makes it double the size.

   208 

   209   // Example:

   210   // (lower case chunks are free, the * indicates the chunk we want to merge):

   211   //

   212   // ........................

   213   // d d*c   b       A           <- we return the second (d*) chunk...

   214   //

   215   // c*  c   b       A           <- we merge it with its predecessor and decrease its level...

   216   //

   217   // b*      b       A           <- we merge it again, since its new neighbor was free too...

   218   //

   219   // a*              A           <- we merge it again, since its new neighbor was free too...

   220   //

   221   // And we are done, since its new neighbor, (A), is not free. We would also be done

   222   // if the new neighbor itself is splintered.

   223 

   224   DEBUG_ONLY(check_pointer(c->base());)

   225   assert(!c->is_root_chunk(), "Cannot be merged further.");

   226   assert(c->is_free(), "Can only merge free chunks.");

   227 

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

   229 

   230   log_trace(metaspace)("Attempting to merge chunk " METACHUNK_FORMAT ".", METACHUNK_FORMAT_ARGS(c));

   231 

   232   const chklvl_t starting_level = c->level();

   233 

   234   bool stop = false;

   235   Metachunk* result = NULL;

   236 

   237   do {

   238 

   239     // First find out if this chunk is the leader of its pair

   240     const bool is_leader = c->is_leader();

   241 

   242     // Note: this is either our buddy or a splinter of the buddy.

   243     Metachunk* const buddy = c->is_leader() ? c->next_in_vs() : c->prev_in_vs();

   244     DEBUG_ONLY(buddy->verify(true);)

   245 

   246     // A buddy chunk must be of the same or higher level (so, same size or smaller)

   247     // never be larger.

   248     assert(buddy->level() >= c->level(), "Sanity");

   249 

   250     // Is this really my buddy (same level) or a splinter of it (higher level)?

   251     // Also, is it free?

   252     if (buddy->level() != c->level() || buddy->is_free() == false) {

   253 

   254       log_trace(metaspace)("cannot merge with chunk " METACHUNK_FORMAT ".", METACHUNK_FORMAT_ARGS(buddy));

   255 

   256       stop = true;

   257 

   258     } else {

   259 

   260       log_trace(metaspace)("will merge with chunk " METACHUNK_FORMAT ".", METACHUNK_FORMAT_ARGS(buddy));

   261 

   262       // We can merge with the buddy.

   263 

   264       // First, remove buddy from the chunk manager.

   265       assert(buddy->is_free(), "Sanity");

   266       freelists->remove(buddy);

   267       DEBUG_ONLY(InternalStats::inc_num_chunks_removed_from_freelist_due_to_merge();)

   268 

   269       // Determine current leader and follower

   270       Metachunk* leader;

   271       Metachunk* follower;

   272       if (is_leader) {

   273         leader = c; follower = buddy;

   274       } else {

   275         leader = buddy; follower = c;

   276       }

   277 

   278       // Last checkpoint

   279       assert(leader->end() == follower->base() &&

   280              leader->level() == follower->level() &&

   281              leader->is_free() && follower->is_free(), "Sanity");

   282 

   283       // The new merged chunk is as far committed as possible (if leader

   284       // chunk is fully committed, as far as the follower chunk).

   285       size_t merged_committed_words = leader->committed_words();

   286       if (merged_committed_words == leader->word_size()) {

   287         merged_committed_words += follower->committed_words();

   288       }

   289 

   290       // Leader survives, follower chunk is freed. Remove follower from vslist ..

   291       leader->set_next_in_vs(follower->next_in_vs());

   292       if (follower->next_in_vs() != NULL) {

   293         follower->next_in_vs()->set_prev_in_vs(leader);

   294       }

   295 

   296       // .. and return follower chunk header to pool for reuse.

   297       ChunkHeaderPool::pool().return_chunk_header(follower);

   298 

   299       // Leader level gets decreased (leader chunk doubles in size) but

   300       // base address stays the same.

   301       leader->dec_level();

   302 

   303       // set commit boundary

   304       leader->set_committed_words(merged_committed_words);

   305 

   306       // If the leader is now of root chunk size, stop merging

   307       if (leader->is_root_chunk()) {

   308         stop = true;

   309       }

   310 

   311       result = c = leader;

   312 

   313       DEBUG_ONLY(leader->verify(true);)

   314 

   315     }

   316 

   317   } while (!stop);

   318 

   319 #ifdef ASSERT

   320   verify(true);

   321   if (result != NULL) {

   322     result->verify(true);

   323     if (result->level() < starting_level) {

   324       DEBUG_ONLY(InternalStats::inc_num_chunk_merges();)

   325     }

   326   }

   327 #endif // ASSERT

   328 

   329   return result;

   330 

   331 }

   332 

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

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

   335 //

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

   337 //

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

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

   340 //

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

   342 bool RootChunkArea::attempt_enlarge_chunk(Metachunk* c, MetachunkListCluster* freelists) {

   343 

   344   DEBUG_ONLY(check_pointer(c->base());)

   345   assert(!c->is_root_chunk(), "Cannot be merged further.");

   346 

   347   // There is no real reason for this limitation other than it is not

   348   // needed on free chunks since they should be merged already:

   349   assert(c->is_in_use(), "Can only enlarge in use chunks.");

   350 

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

   352 

   353   if (!c->is_leader()) {

   354     return false;

   355   }

   356 

   357   // We are the leader, so the buddy must follow us.

   358   Metachunk* const buddy = c->next_in_vs();

   359   DEBUG_ONLY(buddy->verify(true);)

   360 

   361   // Of course buddy cannot be larger than us.

   362   assert(buddy->level() >= c->level(), "Sanity");

   363 

   364   // We cannot merge buddy in if it is not free...

   365   if (!buddy->is_free()) {

   366     return false;

   367   }

   368 

   369   // ... nor if it is splintered.

   370   if (buddy->level() != c->level()) {

   371     return false;

   372   }

   373 

   374   // Okay, lets enlarge c.

   375 

   376   log_trace(metaspace)("Enlarging chunk " METACHUNK_FULL_FORMAT " by merging in follower " METACHUNK_FULL_FORMAT ".",

   377                        METACHUNK_FULL_FORMAT_ARGS(c), METACHUNK_FULL_FORMAT_ARGS(buddy));

   378 

   379   // the enlarged c is as far committed as possible:

   380   size_t merged_committed_words = c->committed_words();

   381   if (merged_committed_words == c->word_size()) {

   382     merged_committed_words += buddy->committed_words();

   383   }

   384 

   385   // Remove buddy from vs list...

   386   Metachunk* successor = buddy->next_in_vs();

   387   if (successor != NULL) {

   388     successor->set_prev_in_vs(c);

   389   }

   390   c->set_next_in_vs(successor);

   391 

   392   // .. and from freelist ...

   393   freelists->remove(buddy);

   394 

   395   // .. and return its empty husk to the pool...

   396   ChunkHeaderPool::pool().return_chunk_header(buddy);

   397 

   398   // Then decrease level of c.

   399   c->dec_level();

   400 

   401   // and correct committed words if needed.

   402   c->set_committed_words(merged_committed_words);

   403 

   404   log_debug(metaspace)("Enlarged chunk " METACHUNK_FULL_FORMAT ".", METACHUNK_FULL_FORMAT_ARGS(c));

   405 //  log_debug(metaspace)("Enlarged chunk " METACHUNK_FORMAT ".", METACHUNK_FORMAT_ARGS(c));

   406 

   407   DEBUG_ONLY(verify(true));

   408 

   409   return true;

   410 

   411 }

   412 

   413 

   414 #ifdef ASSERT

   415 

   416 #define assrt_(cond, ...) \

   417   if (!(cond)) { \

   418     fdStream errst(2); \

   419     this->print_on(&errst); \

   420     vmassert(cond, __VA_ARGS__); \

   421   }

   422 

   423 void RootChunkArea::verify(bool slow) const {

   424 

   425   assert_is_aligned(_base, chklvl::MAX_CHUNK_BYTE_SIZE);

   426 

   427   // Iterate thru all chunks in this area. They must be ordered correctly,

   428   // being adjacent to each other, and cover the complete area

   429   int num_chunk = 0;

   430 

   431   if (_first_chunk != NULL) {

   432 

   433     assrt_(_first_chunk->prev_in_vs() == NULL, "Sanity");

   434 

   435     const Metachunk* c = _first_chunk;

   436     const Metachunk* c_last = NULL;

   437     const MetaWord* expected_next_base = _base;

   438     const MetaWord* const area_end = _base + word_size();

   439 

   440     while (c != NULL) {

   441 

   442       assrt_(c->base() == expected_next_base,

   443              "Chunk No. %d " METACHUNK_FORMAT " - unexpected base.",

   444              num_chunk, METACHUNK_FORMAT_ARGS(c));

   445 

   446       assrt_(c->base() >= base() && c->end() <= end(),

   447              "chunk %d " METACHUNK_FORMAT " oob for this root area [" PTR_FORMAT ".." PTR_FORMAT ").",

   448              num_chunk, METACHUNK_FORMAT_ARGS(c), p2i(base()), p2i(end()));

   449 

   450       assrt_(is_aligned(c->base(), c->word_size()),

   451              "misaligned chunk %d " METACHUNK_FORMAT ".", num_chunk, METACHUNK_FORMAT_ARGS(c));

   452 

   453       const Metachunk* const successor = c->next_in_vs();

   454       if (successor != NULL) {

   455         assrt_(successor->prev_in_vs() == c,

   456                "Chunk No. %d " METACHUNK_FORMAT " - vs link to successor " METACHUNK_FORMAT " broken.", num_chunk,

   457                METACHUNK_FORMAT_ARGS(c), METACHUNK_FORMAT_ARGS(successor));

   458         assrt_(c->end() == successor->base(),

   459                "areas between neighbor chunks do not connect: "

   460                "this chunk %d " METACHUNK_FORMAT " and successor chunk %d " METACHUNK_FORMAT ".",

   461                num_chunk, METACHUNK_FORMAT_ARGS(c), num_chunk + 1, METACHUNK_FORMAT_ARGS(successor));

   462       }

   463 

   464       if (c_last != NULL) {

   465         assrt_(c->prev_in_vs() == c_last,

   466                "Chunk No. %d " METACHUNK_FORMAT " - vs backlink invalid.", num_chunk, METACHUNK_FORMAT_ARGS(c));

   467         assrt_(c_last->end() == c->base(),

   468                "areas between neighbor chunks do not connect: "

   469                "previous chunk %d " METACHUNK_FORMAT " and this chunk %d " METACHUNK_FORMAT ".",

   470                num_chunk - 1, METACHUNK_FORMAT_ARGS(c_last), num_chunk, METACHUNK_FORMAT_ARGS(c));

   471       } else {

   472         assrt_(c->prev_in_vs() == NULL,

   473                "unexpected back link: chunk %d " METACHUNK_FORMAT ".",

   474                num_chunk, METACHUNK_FORMAT_ARGS(c));

   475         assrt_(c == _first_chunk,

   476             "should be first: chunk %d " METACHUNK_FORMAT ".",

   477             num_chunk, METACHUNK_FORMAT_ARGS(c));

   478       }

   479 

   480       c->verify(slow); // <- also checks alignment and level etc

   481 

   482       expected_next_base = c->end();

   483       c_last = c;

   484       num_chunk ++;

   485 

   486       c = c->next_in_vs();

   487 

   488     }

   489     assrt_(expected_next_base == _base + word_size(), "Sanity");

   490   }

   491 

   492 }

   493 

   494 void RootChunkArea::verify_area_is_ideally_merged() const {

   495   int num_chunk = 0;

   496   for (const Metachunk* c = _first_chunk; c != NULL; c = c->next_in_vs()) {

   497     if (!c->is_root_chunk() && c->is_free()) {

   498       // If a chunk is free, it must not have a buddy which is also free, because

   499       // those chunks should have been merged.

   500       // In other words, a buddy shall be either in-use or splintered

   501       // (which in turn would mean part of it are in use).

   502       Metachunk* const buddy = c->is_leader() ? c->next_in_vs() : c->prev_in_vs();

   503       assrt_(buddy->is_in_use() || buddy->level() > c->level(),

   504              "Chunk No. %d " METACHUNK_FORMAT " : missed merge opportunity with neighbor " METACHUNK_FORMAT ".",

   505              num_chunk, METACHUNK_FORMAT_ARGS(c), METACHUNK_FORMAT_ARGS(buddy));

   506     }

   507     num_chunk ++;

   508   }

   509 }

   510 

   511 #endif

   512 

   513 void RootChunkArea::print_on(outputStream* st) const {

   514 

   515   st->print(PTR_FORMAT ": ", p2i(base()));

   516   if (_first_chunk != NULL) {

   517     const Metachunk* c = _first_chunk;

   518     //                                    01234567890123

   519     const char* letters_for_levels_cap = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

   520     const char* letters_for_levels =     "abcdefghijklmnopqrstuvwxyz";

   521     while (c != NULL) {

   522       const chklvl_t l = c->level();

   523       if (l >= 0 && (size_t)l < strlen(letters_for_levels)) {

   524 //        c->print_on(st); st->cr();

   525         st->print("%c", c->is_free() ? letters_for_levels[c->level()] : letters_for_levels_cap[c->level()]);

   526       } else {

   527         // Obviously garbage, but lets not crash.

   528         st->print("?");

   529       }

   530       c = c->next_in_vs();

   531     }

   532   } else {

   533     st->print(" (no chunks)");

   534   }

   535   st->cr();

   536 

   537 }

   538 

   539 

   540 // Create an array of ChunkTree objects, all initialized to NULL, covering

   541 // a given memory range. Memory range must be a multiple of root chunk size.

   542 RootChunkAreaLUT::RootChunkAreaLUT(const MetaWord* base, size_t word_size)

   543   : _base(base),

   544     _num(word_size / chklvl::MAX_CHUNK_WORD_SIZE),

   545     _arr(NULL)

   546 {

   547   assert_is_aligned(word_size, chklvl::MAX_CHUNK_WORD_SIZE);

   548   _arr = NEW_C_HEAP_ARRAY(RootChunkArea, _num, mtClass);

   549   const MetaWord* this_base = _base;

   550   for (int i = 0; i < _num; i ++) {

   551     RootChunkArea* rca = new(_arr + i) RootChunkArea(this_base);

   552     assert(rca == _arr + i, "Sanity");

   553     this_base += chklvl::MAX_CHUNK_WORD_SIZE;

   554   }

   555 }

   556 

   557 RootChunkAreaLUT::~RootChunkAreaLUT() {

   558   for (int i = 0; i < _num; i ++) {

   559     _arr[i].~RootChunkArea();

   560   }

   561   FREE_C_HEAP_ARRAY(RootChunkArea, _arr);

   562 }

   563 

   564 #ifdef ASSERT

   565 

   566 void RootChunkAreaLUT::verify(bool slow) const {

   567   for (int i = 0; i < _num; i ++) {

   568     check_pointer(_arr[i].base());

   569     _arr[i].verify(slow);

   570   }

   571 }

   572 

   573 #endif

   574 

   575 void RootChunkAreaLUT::print_on(outputStream* st) const {

   576   for (int i = 0; i < _num; i ++) {

   577     st->print("%2d:", i);

   578     _arr[i].print_on(st);

   579   }

   580 }

   581 

   582 

   583 } // end: namespace metaspace