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