1 /*
   2  * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 #include "precompiled.hpp"
  25 
  26 //#include "logging/log.hpp"
  27 #include "memory/metaspace/chunkTree.hpp"
  28 #include "memory/metaspace/metachunk.hpp"
  29 //#include "utilities/ostream.hpp"
  30 #include "utilities/debug.hpp"
  31 #include "utilities/globalDefinitions.hpp"
  32 
  33 namespace metaspace {
  34 
  35 ChunkTreeNodePool ChunkTree::_nodePool("metaspace chunk tree node pool");
  36 
  37 
  38 #ifdef ASSERT
  39 void ChunkTree::verify_node(const qtnode_t* n) {
  40 
  41   // Child pointers are never NULL; either one of them may point to another node,
  42   // or to a Metachunk*.
  43   assert(n->child[0] != NULL &&
  44          n->child[1] != NULL &&
  45          n->child[2] != NULL &&
  46          n->child[3] != NULL, "child ptrs null");
  47 
  48   if (n->parent != NULL) {
  49     _nodePool.check_elem(n->parent);
  50   }
  51 
  52   for (int i = 0; i < 4; i ++) {
  53     // Each child pointer shall point to either another node or to a chunk header
  54     Metachunk* c = resolve_chunk_ptr(n->child[i]);
  55     qtnode_t* n2 = resolve_node_ptr(n->child[i]);
  56     if (c != NULL) {
  57       // It is a chunk.
  58       assert(c->tree_node() == n, "Chunk must have backlink to parent");
  59       assert(n2 == NULL, "only one");
  60     } else {
  61       // It is a node.
  62       assert(n2->parent == n, "Chunk must have backlink to parent");
  63       assert(c == NULL, "only one");
  64     }
  65   }
  66 
  67 }
  68 #endif
  69 
  70 
  71 // Initialize: allocate a root node and a root chunk header; return the
  72 // root chunk header.
  73 Metachunk* ChunkTree::alloc_root() {
  74 
  75   assert(_root == NULL, "already have a root");
  76 
  77   Metachunk* c = MetachunkPool::alloc_header();
  78 
  79   // Newly created chunks should have level==0 aka root
  80   assert(c->level() == chklvl::ROOT_CHUNK_LEVEL, "not root chunk?");
  81 
  82   _root = c;
  83 
  84   return c;
  85 
  86 }
  87 
  88 
  89 // Given a chunk c, split it into four smaller chunks.
  90 // Returns pointer to the result chunk; appends splintered off chunks to the given linked list.
  91 // Returns NULL if chunk cannot be split.
  92 Metachunk* ChunkTree::split_once(Metachunk* c, Metachunk** p_splinters) {
  93 
  94   Metachunk* remainder_list = NULL;
  95 
  96   if (c->level() == chklvl::HIGHEST_CHUNK_LEVEL) {
  97     return NULL;
  98   }
  99 
 100   MetaWord* new_base = c->base();
 101   const int new_level = c->level() + 1;
 102   const size_t new_word_size = chklvl::word_size_for_level(new_level);
 103   qtnode_t* const old_parent = c->tree_node();
 104 
 105   // 1. Create a single new parent node...
 106   qtnode_t* new_parent_node = allocate_node();
 107 
 108   // 2. the originating chunk header is reused as the first chunk header
 109   //    of all splinters.
 110   c->set_level(new_level);
 111   c->set_tree_node(new_parent_node);
 112   new_parent_node->child[0] = c;
 113 
 114   // 3. Create three new sibling chunk headers; initialize them;
 115   //    and append them to the splinters list.
 116   for (int i = 0; i < 3; i ++) {
 117     Metachunk* sib = MetachunkPool::alloc_header();
 118     sib->set_level(new_level);
 119     sib->set_base(new_base);
 120 
 121     new_base += new_word_size;
 122 
 123     sib->set_tree_node(new_parent_node);
 124     new_parent_node->child[i] = sib;
 125 
 126     // Return splinters in this linked list
 127     sib->set_next(*p_splinters);
 128     *p_splinters = sib;
 129   }
 130 
 131   // 4. ... Now, replace the old header storage location with the
 132   //        new parent node.
 133   if (old_parent == NULL) {
 134     assert(_root == c, "Must have been root");
 135     _root = new_parent_node;
 136   } else {
 137     if (old_parent->child[0] == c) {
 138       old_parent->child[0] = new_parent_node;
 139     } else if (old_parent->child[1] == c) {
 140       old_parent->child[1] = new_parent_node;
 141     } else if (old_parent->child[2] == c) {
 142       old_parent->child[2] = new_parent_node;
 143     } else if (old_parent->child[3] == c) {
 144       old_parent->child[3] = new_parent_node;
 145     } else {
 146       ShouldNotReachHere();
 147     }
 148   }
 149 
 150   return c;
 151 }
 152 
 153 // Given a chunk c, split it repeatedly until you get a chunk of the given target_level.
 154 // Return the remainder chunks in a linked list.
 155 Metachunk* ChunkTree::split(chklvl_t target_level, Metachunk* c, Metachunk** p_splinters) {
 156 
 157   DEBUG_ONLY(chklvl::check_valid_level(target_level));
 158   assert(target_level > c->level(), "Wrong target level");
 159 
 160   Metachunk* c_last = split_once(c, p_splinters);
 161   while (c_last != NULL && c_last->level() < target_level) {
 162     c_last = split_once(c, p_splinters);
 163   }
 164 
 165   assert(c != NULL, "Sanity");
 166 
 167   return c;
 168 
 169 }
 170 
 171 
 172 // Given a chunk, attempt to merge it with its siblings
 173 // if they are free.
 174 // Returns pointer to the result chunk if successful, NULL otherwise.
 175 //
 176 // !!! Please note that if this method returns a non-NULL value, the
 177 // original chunk will be invalid and should not be accessed anymore! !!!
 178 Metachunk* ChunkTree::merge_once(Metachunk* c) {
 179 
 180   DEBUG_ONLY(c->verify(false);)
 181   assert(c->is_free(), "Only call for free chunks.");
 182 
 183   if (c->level() == chklvl::ROOT_CHUNK_LEVEL) {
 184     return NULL;
 185   }
 186 
 187   qtnode_t* old_parent = c->tree_node();
 188   assert(old_parent != NULL, "Sanity");
 189 
 190   // Are all neighbors able to merge? They are if none is splintered (they are
 191   // all leaf nodes) and free.
 192   Metachunk* s0, *s1, *s2, *s3;
 193   if ((s0 = resolve_chunk_ptr(old_parent->child[0])) == NULL || s0->is_in_use() ||
 194       (s1 = resolve_chunk_ptr(old_parent->child[1])) == NULL || s1->is_in_use() ||
 195       (s2 = resolve_chunk_ptr(old_parent->child[2])) == NULL || s2->is_in_use() ||
 196       (s3 = resolve_chunk_ptr(old_parent->child[3])) == NULL || s3->is_in_use()) {
 197     return NULL;
 198   }
 199 
 200   // The new merged chunk is the first one. Nothing but the level changes.
 201   Metachunk* c_merged = s0;
 202   const int new_level = c->level() - 1;
 203   c_merged->set_level(new_level);
 204 
 205   // The other chunk headers are not needed anymore and can be returned to the
 206   // pool.
 207   MetachunkPool::release_header(s1);
 208   MetachunkPool::release_header(s2);
 209   MetachunkPool::release_header(s3);
 210 
 211   // The former parent node is not needed anymore. Add the new chunk to its parent.
 212   qtnode_t* old_grandparent = old_parent->parent;
 213   if (old_grandparent == NULL) {
 214     // old parent was root.
 215     _root = c_merged;
 216   } else {
 217     // old parent was not NULL. Replace the pointer to old parent in the grand parent
 218     // child array with the newly created chunk header.
 219     if (old_grandparent->child[0] == old_parent) {
 220       old_grandparent->child[0] = c_merged;
 221     } else if (old_grandparent->child[1] == old_parent) {
 222       old_grandparent->child[1] = c_merged;
 223     } else if (old_grandparent->child[2] == old_parent) {
 224       old_grandparent->child[2] = c_merged;
 225     } else if (old_grandparent->child[3] == old_parent) {
 226       old_grandparent->child[3] = c_merged;
 227     } else {
 228       ShouldNotReachHere();
 229     }
 230   }
 231 
 232   // Old parent node is not needed anymore
 233   release_node(old_parent);
 234 
 235   // Now repeat recursively:
 236   return c_merged;
 237 
 238 }
 239 
 240 
 241 // Given a chunk, attempt to merge it with its neighboring chunks
 242 // if they are free.
 243 // Does so recursively until either the chunk is a root chunk or
 244 // one of the neighbors is non-free.
 245 // If successful (at least one merge happened), returns address of
 246 // the merged chunk; NULL otherwise.
 247 //
 248 // !!! Please note that if this method returns a non-NULL value, the
 249 // original chunk will be invalid and should not be accessed anymore! !!!
 250 Metachunk* ChunkTree::merge(Metachunk* c) {
 251 
 252   DEBUG_ONLY(c->verify(false);)
 253   assert(c->is_free(), "Only merge free chunks.");
 254   assert(c->level() > chklvl::ROOT_CHUNK_LEVEL, "Only merge root chunks.");
 255 
 256   Metachunk* c_last = merge_once(c);
 257   while (c_last != NULL && c_last->level() > chklvl::ROOT_CHUNK_LEVEL) {
 258     c_last = merge_once(c);
 259   }
 260 
 261   return c_last;
 262 }
 263 
 264 
 265 //// ChunkTreeArray /////////////777
 266 
 267 // Create an array of ChunkTree objects, all initialized to NULL, covering
 268 // a given memory range. Memory range must be aligned to size of root chunks.
 269 ChunkTreeArray::ChunkTreeArray(const MetaWord* base, size_t word_size)
 270   : _base(base), _word_size(word_size),
 271     _arr(NULL), _num(0)
 272 {
 273   assert(is_aligned(_word_size, chklvl::MAX_CHUNK_WORD_SIZE), "not aligned");
 274   _num = _word_size / chklvl::MAX_CHUNK_WORD_SIZE;
 275   _arr = NEW_C_HEAP_ARRAY(ChunkTree*, _num, mtInternal);
 276   memset(_arr, 0, sizeof(ChunkTree*) * _num);
 277 }
 278 
 279 ChunkTreeArray::~ChunkTreeArray() {
 280   FREE_C_HEAP_ARRAY(ChunkTree*, _arr);
 281 }
 282 
 283 } // namespace metaspace
 284 
 285