1 /*
   2  * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved.
   3  * Copyright (c) 2020 SAP SE. 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 
  26 #include "precompiled.hpp"
  27 
  28 #include "logging/log.hpp"
  29 #include "memory/allocation.hpp"
  30 #include "memory/metaspace/chunkHeaderPool.hpp"
  31 #include "memory/metaspace/chunkManager.hpp"
  32 #include "memory/metaspace/freeChunkList.hpp"
  33 #include "memory/metaspace/metachunk.hpp"
  34 #include "memory/metaspace/metaspaceCommon.hpp"
  35 #include "memory/metaspace/rootChunkArea.hpp"
  36 #include "runtime/mutexLocker.hpp"
  37 #include "utilities/debug.hpp"
  38 #include "utilities/globalDefinitions.hpp"
  39 
  40 namespace metaspace {
  41 
  42 RootChunkArea::RootChunkArea(const MetaWord* base)
  43   : _base(base), _first_chunk(NULL)
  44 {}
  45 
  46 RootChunkArea::~RootChunkArea() {
  47   // This is called when a VirtualSpaceNode is destructed (purged).
  48   // All chunks should be free of course. In fact, there should only
  49   // be one chunk, since all free chunks should have been merged.
  50   if (_first_chunk != NULL) {
  51     assert(_first_chunk->is_root_chunk() && _first_chunk->is_free(),
  52            "Cannot delete root chunk area if not all chunks are free.");
  53     ChunkHeaderPool::pool()->return_chunk_header(_first_chunk);
  54   }
  55 }
  56 
  57 // Initialize: allocate a root node and a root chunk header; return the
  58 // root chunk header. It will be partly initialized.
  59 // Note: this just allocates a memory-less header; memory itself is allocated inside VirtualSpaceNode.
  60 Metachunk* RootChunkArea::alloc_root_chunk_header(VirtualSpaceNode* node) {
  61 
  62   assert(_first_chunk == 0, "already have a root");
  63 
  64   Metachunk* c = ChunkHeaderPool::pool()->allocate_chunk_header();
  65   c->initialize(node, const_cast<MetaWord*>(_base), chunklevel::ROOT_CHUNK_LEVEL);
  66 
  67   _first_chunk = c;
  68 
  69   return c;
  70 
  71 }
  72 
  73 // Given a chunk c, split it recursively until you get a chunk of the given target_level.
  74 //
  75 // The resulting target chunk resides at the same address as the original chunk.
  76 // The resulting splinters are added to freelists.
  77 //
  78 // Returns pointer to the result chunk; the splitted-off chunks are added as
  79 //  free chunks to the freelists.
  80 void RootChunkArea::split(chunklevel_t target_level, Metachunk* c, FreeChunkListVector* freelists) {
  81 
  82   // Splitting a chunk once works like this:
  83   //
  84   // For a given chunk we want to split:
  85   // - increase the chunk level (which halves its size)
  86   // - (but leave base address as it is since it will be the leader of the newly
  87   //    created chunk pair)
  88   // - then create a new chunk header of the same level, set its memory range
  89   //   to cover the second halfof the old chunk.
  90   // - wire them up (prev_in_vs/next_in_vs)
  91   // - return the follower chunk as "splinter chunk" in the splinters array.
  92 
  93   // Doing this multiple times will create a new free splinter chunk for every
  94   // level we split:
  95   //
  96   // A  <- original chunk
  97   //
  98   // B B  <- split into two halves
  99   //
 100   // C C B  <- first half split again
 101   //
 102   // D D C B  <- first half split again ...
 103   //
 104 
 105   // As an optimization, since we usually do not split once but multiple times,
 106   // to not do each split separately, since we would have to wire up prev_in_vs/next_in_vs
 107   // on every level just to tear it open in the next level when we reintroduce a new
 108   // half chunk splinter.
 109   // Instead, just split split split and delay building up the double linked list of the
 110   // new chunks at the end of all splits.
 111 
 112   DEBUG_ONLY(check_pointer(c->base());)
 113   DEBUG_ONLY(c->verify(false);)
 114   assert(c->is_free(), "Can only split free chunks.");
 115 
 116   DEBUG_ONLY(chunklevel::check_valid_level(target_level));
 117   assert(target_level > c->level(), "Wrong target level");
 118 
 119   const chunklevel_t starting_level = c->level();
 120 
 121   while (c->level() < target_level) {
 122 
 123     log_trace(metaspace)("Splitting chunk: " METACHUNK_FULL_FORMAT ".", METACHUNK_FULL_FORMAT_ARGS(c));
 124 
 125     c->inc_level();
 126     Metachunk* splinter_chunk = ChunkHeaderPool::pool()->allocate_chunk_header();
 127     splinter_chunk->initialize(c->vsnode(), c->end(), c->level());
 128 
 129     // Fix committed words info: If over the half of the original chunk was
 130     // committed, committed area spills over into the follower chunk.
 131     const size_t old_committed_words = c->committed_words();
 132     if (old_committed_words > c->word_size()) {
 133       c->set_committed_words(c->word_size());
 134       splinter_chunk->set_committed_words(old_committed_words - c->word_size());
 135     } else {
 136       splinter_chunk->set_committed_words(0);
 137     }
 138 
 139     // Insert splinter chunk into vs list
 140     if (c->next_in_vs() != NULL) {
 141       c->next_in_vs()->set_prev_in_vs(splinter_chunk);
 142     }
 143     splinter_chunk->set_next_in_vs(c->next_in_vs());
 144     splinter_chunk->set_prev_in_vs(c);
 145     c->set_next_in_vs(splinter_chunk);
 146 
 147     log_trace(metaspace)(".. Result chunk: " METACHUNK_FULL_FORMAT ".", METACHUNK_FULL_FORMAT_ARGS(c));
 148     log_trace(metaspace)(".. Splinter chunk: " METACHUNK_FULL_FORMAT ".", METACHUNK_FULL_FORMAT_ARGS(splinter_chunk));
 149 
 150     // Add splinter to free lists
 151     freelists->add(splinter_chunk);
 152 
 153   }
 154 
 155   assert(c->level() == target_level, "Sanity");
 156 
 157   DEBUG_ONLY(verify(true);)
 158   DEBUG_ONLY(c->verify(true);)
 159 
 160 }
 161 
 162 
 163 // Given a chunk, attempt to merge it recursively with its neighboring chunks.
 164 //
 165 // If successful (merged at least once), returns address of
 166 // the merged chunk; NULL otherwise.
 167 //
 168 // The merged chunks are removed from the freelists.
 169 //
 170 // !!! Please note that if this method returns a non-NULL value, the
 171 // original chunk will be invalid and should not be accessed anymore! !!!
 172 Metachunk* RootChunkArea::merge(Metachunk* c, FreeChunkListVector* freelists) {
 173 
 174   // Note rules:
 175   //
 176   // - a chunk always has a buddy, unless it is a root chunk.
 177   // - In that buddy pair, a chunk is either leader or follower.
 178   // - a chunk's base address is always aligned at its size.
 179   // - if chunk is leader, its base address is also aligned to the size of the next
 180   //   lower level, at least. A follower chunk is not.
 181 
 182   // How we merge once:
 183   //
 184   // For a given chunk c, which has to be free and non-root, we do:
 185   // - find out if we are the leader or the follower chunk
 186   // - if we are leader, next_in_vs must be the follower; if we are follower,
 187   //   prev_in_vs must be the leader. Now we have the buddy chunk.
 188   // - However, if the buddy chunk itself is split (of a level higher than us)
 189   //   we cannot merge.
 190   // - we can only merge if the buddy is of the same level as we are and it is
 191   //   free.
 192   // - Then we merge by simply removing the follower chunk from the address range
 193   //   linked list (returning the now useless header to the pool) and decreasing
 194   //   the leader chunk level by one. That makes it double the size.
 195 
 196   // Example:
 197   // (lower case chunks are free, the * indicates the chunk we want to merge):
 198   //
 199   // ........................
 200   // d d*c   b       A           <- we return the second (d*) chunk...
 201   //
 202   // c*  c   b       A           <- we merge it with its predecessor and decrease its level...
 203   //
 204   // b*      b       A           <- we merge it again, since its new neighbor was free too...
 205   //
 206   // a*              A           <- we merge it again, since its new neighbor was free too...
 207   //
 208   // And we are done, since its new neighbor, (A), is not free. We would also be done
 209   // if the new neighbor itself is splintered.
 210 
 211   DEBUG_ONLY(check_pointer(c->base());)
 212   assert(!c->is_root_chunk(), "Cannot be merged further.");
 213   assert(c->is_free(), "Can only merge free chunks.");
 214 
 215   DEBUG_ONLY(c->verify(false);)
 216 
 217   log_trace(metaspace)("Attempting to merge chunk " METACHUNK_FORMAT ".", METACHUNK_FORMAT_ARGS(c));
 218 
 219   const chunklevel_t starting_level = c->level();
 220 
 221   bool stop = false;
 222   Metachunk* result = NULL;
 223 
 224   do {
 225 
 226     // First find out if this chunk is the leader of its pair
 227     const bool is_leader = c->is_leader();
 228 
 229     // Note: this is either our buddy or a splinter of the buddy.
 230     Metachunk* const buddy = c->is_leader() ? c->next_in_vs() : c->prev_in_vs();
 231     DEBUG_ONLY(buddy->verify(true);)
 232 
 233     // A buddy chunk must be of the same or higher level (so, same size or smaller)
 234     // never be larger.
 235     assert(buddy->level() >= c->level(), "Sanity");
 236 
 237     // Is this really my buddy (same level) or a splinter of it (higher level)?
 238     // Also, is it free?
 239     if (buddy->level() != c->level() || buddy->is_free() == false) {
 240 
 241       log_trace(metaspace)("cannot merge with chunk " METACHUNK_FORMAT ".", METACHUNK_FORMAT_ARGS(buddy));
 242 
 243       stop = true;
 244 
 245     } else {
 246 
 247       log_trace(metaspace)("will merge with chunk " METACHUNK_FORMAT ".", METACHUNK_FORMAT_ARGS(buddy));
 248 
 249       // We can merge with the buddy.
 250 
 251       // First, remove buddy from the chunk manager.
 252       assert(buddy->is_free(), "Sanity");
 253       freelists->remove(buddy);
 254 
 255       // Determine current leader and follower
 256       Metachunk* leader;
 257       Metachunk* follower;
 258       if (is_leader) {
 259         leader = c; follower = buddy;
 260       } else {
 261         leader = buddy; follower = c;
 262       }
 263 
 264       // Last checkpoint
 265       assert(leader->end() == follower->base() &&
 266              leader->level() == follower->level() &&
 267              leader->is_free() && follower->is_free(), "Sanity");
 268 
 269       // The new merged chunk is as far committed as possible (if leader
 270       // chunk is fully committed, as far as the follower chunk).
 271       size_t merged_committed_words = leader->committed_words();
 272       if (merged_committed_words == leader->word_size()) {
 273         merged_committed_words += follower->committed_words();
 274       }
 275 
 276       // Leader survives, follower chunk is freed. Remove follower from vslist ..
 277       leader->set_next_in_vs(follower->next_in_vs());
 278       if (follower->next_in_vs() != NULL) {
 279         follower->next_in_vs()->set_prev_in_vs(leader);
 280       }
 281 
 282       // .. and return follower chunk header to pool for reuse.
 283       ChunkHeaderPool::pool()->return_chunk_header(follower);
 284 
 285       // Leader level gets decreased (leader chunk doubles in size) but
 286       // base address stays the same.
 287       leader->dec_level();
 288 
 289       // set commit boundary
 290       leader->set_committed_words(merged_committed_words);
 291 
 292       // If the leader is now of root chunk size, stop merging
 293       if (leader->is_root_chunk()) {
 294         stop = true;
 295       }
 296 
 297       result = c = leader;
 298 
 299       DEBUG_ONLY(leader->verify(true);)
 300 
 301     }
 302 
 303   } while (!stop);
 304 
 305 #ifdef ASSERT
 306   verify(true);
 307   if (result != NULL) {
 308     result->verify(true);
 309   }
 310 #endif // ASSERT
 311 
 312   return result;
 313 
 314 }
 315 
 316 // Given a chunk c, which must be "in use" and must not be a root chunk, attempt to
 317 // enlarge it in place by claiming its trailing buddy.
 318 //
 319 // This will only work if c is the leader of the buddy pair and the trailing buddy is free.
 320 //
 321 // If successful, the follower chunk will be removed from the freelists, the leader chunk c will
 322 // double in size (level decreased by one).
 323 //
 324 // On success, true is returned, false otherwise.
 325 bool RootChunkArea::attempt_enlarge_chunk(Metachunk* c, FreeChunkListVector* freelists) {
 326 
 327   DEBUG_ONLY(check_pointer(c->base());)
 328   assert(!c->is_root_chunk(), "Cannot be merged further.");
 329 
 330   // There is no real reason for this limitation other than it is not
 331   // needed on free chunks since they should be merged already:
 332   assert(c->is_in_use(), "Can only enlarge in use chunks.");
 333 
 334   DEBUG_ONLY(c->verify(false);)
 335 
 336   if (!c->is_leader()) {
 337     return false;
 338   }
 339 
 340   // We are the leader, so the buddy must follow us.
 341   Metachunk* const buddy = c->next_in_vs();
 342   DEBUG_ONLY(buddy->verify(true);)
 343 
 344   // Of course buddy cannot be larger than us.
 345   assert(buddy->level() >= c->level(), "Sanity");
 346 
 347   // We cannot merge buddy in if it is not free...
 348   if (!buddy->is_free()) {
 349     return false;
 350   }
 351 
 352   // ... nor if it is splintered.
 353   if (buddy->level() != c->level()) {
 354     return false;
 355   }
 356 
 357   // Okay, lets enlarge c.
 358 
 359   log_trace(metaspace)("Enlarging chunk " METACHUNK_FULL_FORMAT " by merging in follower " METACHUNK_FULL_FORMAT ".",
 360                        METACHUNK_FULL_FORMAT_ARGS(c), METACHUNK_FULL_FORMAT_ARGS(buddy));
 361 
 362   // the enlarged c is as far committed as possible:
 363   size_t merged_committed_words = c->committed_words();
 364   if (merged_committed_words == c->word_size()) {
 365     merged_committed_words += buddy->committed_words();
 366   }
 367 
 368   // Remove buddy from vs list...
 369   Metachunk* successor = buddy->next_in_vs();
 370   if (successor != NULL) {
 371     successor->set_prev_in_vs(c);
 372   }
 373   c->set_next_in_vs(successor);
 374 
 375   // .. and from freelist ...
 376   freelists->remove(buddy);
 377 
 378   // .. and return its empty husk to the pool...
 379   ChunkHeaderPool::pool()->return_chunk_header(buddy);
 380 
 381   // Then decrease level of c.
 382   c->dec_level();
 383 
 384   // and correct committed words if needed.
 385   c->set_committed_words(merged_committed_words);
 386 
 387   log_debug(metaspace)("Enlarged chunk " METACHUNK_FULL_FORMAT ".", METACHUNK_FULL_FORMAT_ARGS(c));
 388 //  log_debug(metaspace)("Enlarged chunk " METACHUNK_FORMAT ".", METACHUNK_FORMAT_ARGS(c));
 389 
 390   DEBUG_ONLY(verify(true));
 391 
 392   return true;
 393 
 394 }
 395 
 396 // Returns true if this root chunk area is completely free:
 397 //  In that case, it should only contain one chunk (maximally merged, so a root chunk)
 398 //  and it should be free.
 399 bool RootChunkArea::is_free() const {
 400   return _first_chunk == NULL ||
 401       (_first_chunk->is_root_chunk() && _first_chunk->is_free());
 402 }
 403 
 404 
 405 #ifdef ASSERT
 406 
 407 #define assrt_(cond, ...) \
 408   if (!(cond)) { \
 409     fdStream errst(2); \
 410     this->print_on(&errst); \
 411     vmassert(cond, __VA_ARGS__); \
 412   }
 413 
 414 void RootChunkArea::verify(bool slow) const {
 415 
 416 
 417   assert_lock_strong(MetaspaceExpand_lock);
 418   assert_is_aligned(_base, chunklevel::MAX_CHUNK_BYTE_SIZE);
 419 
 420   // Iterate thru all chunks in this area. They must be ordered correctly,
 421   // being adjacent to each other, and cover the complete area
 422   int num_chunk = 0;
 423 
 424   if (_first_chunk != NULL) {
 425 
 426     assrt_(_first_chunk->prev_in_vs() == NULL, "Sanity");
 427 
 428     const Metachunk* c = _first_chunk;
 429     const MetaWord* expected_next_base = _base;
 430     const MetaWord* const area_end = _base + word_size();
 431 
 432     while (c != NULL) {
 433 
 434       assrt_(c->is_free() || c->is_in_use(),
 435           "Chunk No. %d " METACHUNK_FORMAT " - invalid state.",
 436           num_chunk, METACHUNK_FORMAT_ARGS(c));
 437 
 438       assrt_(c->base() == expected_next_base,
 439              "Chunk No. %d " METACHUNK_FORMAT " - unexpected base.",
 440              num_chunk, METACHUNK_FORMAT_ARGS(c));
 441 
 442       assrt_(c->base() >= base() && c->end() <= end(),
 443              "chunk %d " METACHUNK_FORMAT " oob for this root area [" PTR_FORMAT ".." PTR_FORMAT ").",
 444              num_chunk, METACHUNK_FORMAT_ARGS(c), p2i(base()), p2i(end()));
 445 
 446       assrt_(is_aligned(c->base(), c->word_size()),
 447              "misaligned chunk %d " METACHUNK_FORMAT ".", num_chunk, METACHUNK_FORMAT_ARGS(c));
 448 
 449       c->verify_neighborhood();
 450       c->verify(slow);
 451 
 452       expected_next_base = c->end();
 453       num_chunk ++;
 454 
 455       c = c->next_in_vs();
 456 
 457     }
 458     assrt_(expected_next_base == _base + word_size(), "Sanity");
 459   }
 460 
 461 }
 462 
 463 void RootChunkArea::verify_area_is_ideally_merged() const {
 464 
 465   SOMETIMES(assert_lock_strong(MetaspaceExpand_lock);)
 466 
 467   int num_chunk = 0;
 468   for (const Metachunk* c = _first_chunk; c != NULL; c = c->next_in_vs()) {
 469     if (!c->is_root_chunk() && c->is_free()) {
 470       // If a chunk is free, it must not have a buddy which is also free, because
 471       // those chunks should have been merged.
 472       // In other words, a buddy shall be either in-use or splintered
 473       // (which in turn would mean part of it are in use).
 474       Metachunk* const buddy = c->is_leader() ? c->next_in_vs() : c->prev_in_vs();
 475       assrt_(buddy->is_in_use() || buddy->level() > c->level(),
 476              "Chunk No. %d " METACHUNK_FORMAT " : missed merge opportunity with neighbor " METACHUNK_FORMAT ".",
 477              num_chunk, METACHUNK_FORMAT_ARGS(c), METACHUNK_FORMAT_ARGS(buddy));
 478     }
 479     num_chunk ++;
 480   }
 481 }
 482 
 483 #endif
 484 
 485 void RootChunkArea::print_on(outputStream* st) const {
 486 
 487   st->print(PTR_FORMAT ": ", p2i(base()));
 488   if (_first_chunk != NULL) {
 489     const Metachunk* c = _first_chunk;
 490     //                                    01234567890123
 491     const char* letters_for_levels_cap = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 492     const char* letters_for_levels =     "abcdefghijklmnopqrstuvwxyz";
 493     while (c != NULL) {
 494       const chunklevel_t l = c->level();
 495       if (l >= 0 && (size_t)l < strlen(letters_for_levels)) {
 496 //        c->print_on(st); st->cr();
 497         st->print("%c", c->is_free() ? letters_for_levels[c->level()] : letters_for_levels_cap[c->level()]);
 498       } else {
 499         // Obviously garbage, but lets not crash.
 500         st->print("?");
 501       }
 502       c = c->next_in_vs();
 503     }
 504   } else {
 505     st->print(" (no chunks)");
 506   }
 507   st->cr();
 508 
 509 }
 510 
 511 
 512 // Create an array of ChunkTree objects, all initialized to NULL, covering
 513 // a given memory range. Memory range must be a multiple of root chunk size.
 514 RootChunkAreaLUT::RootChunkAreaLUT(const MetaWord* base, size_t word_size)
 515   : _base(base),
 516     _num((int)(word_size / chunklevel::MAX_CHUNK_WORD_SIZE)),
 517     _arr(NULL)
 518 {
 519   assert_is_aligned(word_size, chunklevel::MAX_CHUNK_WORD_SIZE);
 520   _arr = NEW_C_HEAP_ARRAY(RootChunkArea, _num, mtClass);
 521   const MetaWord* this_base = _base;
 522   for (int i = 0; i < _num; i ++) {
 523     RootChunkArea* rca = new(_arr + i) RootChunkArea(this_base);
 524     assert(rca == _arr + i, "Sanity");
 525     this_base += chunklevel::MAX_CHUNK_WORD_SIZE;
 526   }
 527 }
 528 
 529 RootChunkAreaLUT::~RootChunkAreaLUT() {
 530   for (int i = 0; i < _num; i ++) {
 531     _arr[i].~RootChunkArea();
 532   }
 533   FREE_C_HEAP_ARRAY(RootChunkArea, _arr);
 534 }
 535 
 536 // Returns true if all areas in this area table are free (only contain free chunks).
 537 bool RootChunkAreaLUT::is_free() const {
 538   for (int i = 0; i < _num; i ++) {
 539     if (!_arr[i].is_free()) {
 540       return false;
 541     }
 542   }
 543   return true;
 544 }
 545 
 546 #ifdef ASSERT
 547 
 548 void RootChunkAreaLUT::verify(bool slow) const {
 549   for (int i = 0; i < _num; i ++) {
 550     check_pointer(_arr[i].base());
 551     _arr[i].verify(slow);
 552   }
 553 }
 554 
 555 #endif
 556 
 557 void RootChunkAreaLUT::print_on(outputStream* st) const {
 558   for (int i = 0; i < _num; i ++) {
 559     st->print("%2d:", i);
 560     _arr[i].print_on(st);
 561   }
 562 }
 563 
 564 
 565 } // end: namespace metaspace