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
36 #ifdef ASSERT
37
38 void ChunkTree::check_is_valid_ref(ref_t ref) {
39 const u2 raw_idx = get_raw_index_from_reference(ref);
40 const u2 info = get_info_from_reference(ref);
41 switch (info) {
42 case node_marker:
43 assert(_nodePool.is_valid_index(raw_idx), "Invalid node ref: %u", (unsigned)ref);
44 break;
45 case free_chunk_marker:
46 case used_chunk_marker:
47 assert(_chunkPool.is_valid_index(raw_idx), "Invalid chunk ref: %u", (unsigned)ref);
48 break;
49 default:
50 ShouldNotReachHere();
51 }
52 }
53
54 void ChunkTree::verify_node(const btnode_t* n) {
55
56 const ref_t node_ref = encode_reference_for_node(n);
57
58 // Check parent.
59 const ref_t parent_ref = n->parent;
60
61 if (parent_ref == 0) {
62 assert(node_ref == _root, "This should be the root node");
63 } else {
64 btnode_t* parent_node = resolve_reference_to_node(parent_ref);
65 assert(parent_node->child[0] == node_ref ||
66 parent_node->child[1] == node_ref, "Incorrect parent backlink.");
67 }
68
69 // Check children.
70 for (int i = 0; i < 2; i ++) {
71 const ref_t child_ref = n->child[i];
72 assert(child_ref != 0, "child ref null");
73
74 // May be either a chunk or another node.
75 if (reference_is_chunk(child_ref)) {
76 Metachunk* c = resolve_reference_to_chunk(child_ref);
77 assert(c->tree_node_ref() == node_ref, "Incorrect parent backlink.");
78 if (reference_is_free_chunk(child_ref)) {
79 assert(c->is_free(), "free info mismatch");
80 } else {
81 assert(c->is_in_use(), "free info mismatch");
82 }
83 } else {
84 // This chunk is another node
85 btnode_t* n = resolve_reference_to_node(child_ref);
86 assert(n->parent == node_ref, "Incorrect parent backlink.");
87 }
88 }
89
90 }
91 #endif
92
93
94 // Initialize: allocate a root node and a root chunk header; return the
95 // root chunk header. It will be partly initialized.
96 // Note: this just allocates a memory-less header; memory itself is allocated inside VirtualSpaceNode.
97 Metachunk* ChunkTree::alloc_root_chunk_header() {
98
99 assert(_root == 0, "already have a root");
100
101 Metachunk* c = _chunkPool.allocate_element();
102 c->wipe();
103
104 c->set_level(chklvl::ROOT_CHUNK_LEVEL);
105
106 const ref_t root_node_ref = encode_reference_for_chunk(c, true);
107
108 _root = root_node_ref;
109
110 return c;
111
112 }
113
114 // Given a chunk c, split it once.
115 //
116 // The original chunk must not be part of a freelist.
117 //
118 // Returns pointer to the result chunk; updates the splinters array to return the splintered off chunk.
119 //
120 // Returns NULL if chunk cannot be split any further.
121 Metachunk* ChunkTree::split_once(Metachunk* c, Metachunk* splinters[chklvl::NUM_CHUNK_LEVELS]) {
122
123 assert(c->is_free(), "Can only split free chunks.");
124
125 if (c->level() == chklvl::HIGHEST_CHUNK_LEVEL) {
126 return NULL;
127 }
128
129 const ref_t orig_chunk_ref = encode_reference_for_chunk(c, true);
130
131 // Split chunk into two chunks.
132 Metachunk* leader = c;
133 Metachunk* follower = allocate_new_chunk();
134 follower->wipe();
135
136 const chklvl_t new_level = c->level() + 1;
137 const size_t new_word_size = chklvl::word_size_for_level(new_level);
138 const size_t old_committed_words = c->committed_words();
139
140 assert(new_word_size == c->word_size() / 2, "Sanity");
141 assert(old_committed_words <= c->word_size(), "Sanity");
142
143 leader->set_level(new_level);
144 follower->set_level(new_level);
145
146 follower->set_base(c->base() + new_word_size);
147
148 // Carry over commit boundary to new chunk; this is an optimization
149 // to avoid too frequent commit requests.
150 if (old_committed_words >= new_word_size) {
151 leader->set_committed_words(new_word_size);
152 follower->set_committed_words(old_committed_words - new_word_size);
153 } else {
154 leader->set_committed_words(old_committed_words);
155 follower->set_committed_words(0);
156 }
157
158 // Create a new parent node for the two sibling chunks.
159 btnode_t* const new_parent = allocate_new_node();
160 const ref_t new_parent_ref = encode_reference_for_node(new_parent);
161
162 // Replace the reference to the original chunk in the parent node with
163 // the reference to the parent node.
164 if (_root == orig_chunk_ref) {
165 assert(new_level == chklvl::ROOT_CHUNK_LEVEL + 1, "Original chunk should have been root chunk.");
166 assert(c->tree_node_ref() == 0, "Original chunk should not have a parent.");
167 _root = new_parent_ref;
168 } else {
169 const ref_t old_parent_ref = c->tree_node_ref();
170 btnode_t* const old_parent = resolve_reference_to_node(old_parent_ref);
171 assert(old_parent != NULL, "Original chunk should have a parent.");
172 if (old_parent->child[0] == orig_chunk_ref) {
173 old_parent->child[0] = new_parent_ref;
174 } else if (old_parent->child[1] == orig_chunk_ref) {
175 old_parent->child[1] = new_parent_ref;
176 } else {
177 ShouldNotReachHere();
178 }
179 }
180
181 // Tell the two new chunks who their parent is.
182 c->set_tree_node_ref(new_parent_ref);
183 follower->set_tree_node_ref(new_parent_ref);
184
185 // Remember the splintered off chunk in the splinters array
186 assert(splinters[new_level] == NULL, "Sanity");
187 splinters[new_level] = follower;
188
189 return c;
190
191 }
192
193 // Given a chunk, attempt to merge it with its sibling if it is free.
194 // Returns pointer to the result chunk if successful, NULL otherwise.
195 //
196 // Returns number of merged chunks, by chunk level, in num_merged array. These numbers
197 // includes the original chunk.
198 //
199 // !!! Please note that if this method returns a non-NULL value, the
200 // original chunk will be invalid and should not be accessed anymore! !!!
201 Metachunk* ChunkTree::merge_once(Metachunk* c, int num_merged[chklvl::NUM_CHUNK_LEVELS]) {
202
203 assert(c->is_free(), "Only call for free chunks.");
204
205 const chklvl_t orig_level = c->level();
206
207 // If chunk is already a root chunk, we cannot merge any further.
208 if (orig_level == chklvl::ROOT_CHUNK_LEVEL) {
209 return NULL;
210 }
211
212 const ref_t orig_chunk_ref = encode_reference_for_chunk(c, true);
213
214 // Get parent node and parent ref.
215 const ref_t parent_ref = c->tree_node_ref();
216 btnode_t* const parent = resolve_reference_to_node(parent_ref);
217 assert(parent != NULL, "Chunk should have a parent."); // Since we left for root chunks already
218
219 // Check if sibling are free and not splintered.
220 if (reference_is_free_chunk(parent->child[0]) == false ||
221 reference_is_free_chunk(parent->child[1]) == false) {
222 return NULL;
223 }
224
225 // Merge chunks.
226 Metachunk* c1 = resolve_reference_to_chunk(parent->child[0]);
227 Metachunk* c2 = resolve_reference_to_chunk(parent->child[1]);
228
229 // At this point, both metachunks should be free and not splintered.
230 assert(c1->is_free() && c2->is_free() && c1->level() == c2->level(), "Sanity");
231
232 // Find out who is leader. Let the leader live on.
233 Metachunk* leader = c1;
234 Metachunk* follower = c2;
235
236 if (c1->base() > c2->base()) {
237 leader = c2; follower = c1;
238 }
239
240 // Chunk memory should be adjacent to each other.
241 assert(leader->base() + leader->word_size() == follower->base(), "Wrong geometry");
242
243 leader->set_level(orig_level - 1);
244
245 // Carry over committed words.
246 size_t new_committed_words = leader->committed_words();
247 if (leader->is_fully_committed()) {
248 new_committed_words += follower->committed_words();
249 }
250 assert(new_committed_words <= leader->word_size(), "Sanity");
251 leader->set_committed_words(new_committed_words);
252
253 const ref_t leader_ref = encode_reference_for_chunk(leader, true);
254
255 // Re-hang new merged chunk in tree one level up.
256 const ref_t grand_parent_ref = parent->parent;
257 if (grand_parent_ref == 0) {
258 // Seems old parent node was root. That means we should have a root chunk now.
259 assert(leader->level() == chklvl::ROOT_CHUNK_LEVEL, "Sanity");
260 // Which we just hang under _root...
261 _root = leader_ref;
262 } else {
263 btnode_t* grand_parent = resolve_reference_to_node(grand_parent_ref);
264 if (grand_parent->child[0] == parent_ref) {
265 grand_parent->child[0] = leader_ref;
266 } else if (grand_parent->child[1] == parent_ref) {
267 grand_parent->child[1] = leader_ref;
268 } else {
269 ShouldNotReachHere();
270 }
271 }
272
273 // Remove the follower from its free list
274 follower->remove_from_list();
275
276 // Adjust stats
277 num_merged[orig_level] ++;
278
279 // Release the superfluous chunk header, and the old parent node.
280 release_chunk(follower);
281 release_node(parent);
282
283 return leader;
284
285 }
286
287 // Given a chunk c, split it recursively until you get a chunk of the given target_level.
288 //
289 // The original chunk must not be part of a freelist.
290 //
291 // Returns pointer to the result chunk; returns split off chunks in splinters array.
292 //
293 // Returns NULL if chunk cannot be split at least once.
294 Metachunk* ChunkTree::split(chklvl_t target_level, Metachunk* c, Metachunk* splinters[chklvl::NUM_CHUNK_LEVELS]) {
295
296 DEBUG_ONLY(chklvl::check_valid_level(target_level));
297 assert(target_level > c->level(), "Wrong target level");
298
299 Metachunk* c_last = split_once(c, splinters);
300 while (c_last != NULL && c_last->level() < target_level) {
301 c_last = split_once(c, splinters);
302 }
303
304 assert(c != NULL, "Sanity");
305
306 return c;
307
308 }
309
310 // Given a chunk, attempt to merge it recursively with its neighboring chunks.
311 //
312 // If successful (merged at least once), returns address of
313 // the merged chunk; NULL otherwise.
314 //
315 // The merged chunks are removed from their freelist; the number of merged chunks is
316 // returned, split by level, in num_merged array. Note that these numbers does not
317 // include the original chunk.
318 //
319 // !!! Please note that if this method returns a non-NULL value, the
320 // original chunk will be invalid and should not be accessed anymore! !!!
321 Metachunk* ChunkTree::merge(Metachunk* c, int num_merged[chklvl::NUM_CHUNK_LEVELS]) {
322
323 DEBUG_ONLY(c->verify(false);)
324 assert(c->is_free(), "Only merge free chunks.");
325
326 assert(c->level() > chklvl::ROOT_CHUNK_LEVEL, "Do not merge root chunks");
327
328 // Original chunk should be outside the chunk manager freelist before attempting to merge.
329 assert(c->prev() == NULL && c->next() == NULL, "Remove chunk from freelist before merging.");
330
331 Metachunk* c_last = merge_once(c, num_merged);
332 while (c_last != NULL && c_last->level() > chklvl::ROOT_CHUNK_LEVEL) {
333 c_last = merge_once(c, num_merged);
334 }
335
336 return c_last;
337 }
338
339
340 //// tree traversal ////
341
342 bool ChunkTree::iterate_chunks_helper(ref_t ref, ChunkClosure* cc) const {
343 if (reference_is_chunk(ref)) {
344 Metachunk* const c = resolve_reference_to_chunk(ref);
345 return cc->do_chunk(c);
346 } else {
347 btnode_t* const n = resolve_reference_to_node(ref);
348 assert(n->child[0] != 0 && n->child[1] != 0, "nodes have always children");
349 return iterate_chunks_helper(n->child[0], cc) &&
350 iterate_chunks_helper(n->child[1], cc);
351 }
352
353 return true;
354 }
355
356 // Iterate over all nodes in this tree. Returns true for complete traversal,
357 // false if traversal was cancelled.
358 bool ChunkTree::iterate_chunks(ChunkClosure* cc) const {
359
360 if (_root == 0) {
361 return true;
362 }
363
364 return iterate_chunks_helper(_root, cc);
365 }
366
367
368
369 #ifdef ASSERT
370
371 // Helper for verify()
372 void ChunkTree::verify_helper(bool slow, ref_t ref, const MetaWord* p, int* num_chunks, int* num_nodes) const {
373
374 if (reference_is_node(ref)) {
375
376 // A node
377
378 const btnode_t* const n = resolve_reference_to_node(ref);
379
380 verify_node(n);
381
382 (*num_nodes) ++;
383
384 // Verify childs recursively.
385 verify_helper(slow, n->child[0], p, num_chunks, num_nodes);
386 verify_helper(slow, n->child[1], p, num_chunks, num_nodes);
387
388 } else {
389
390 // A chunk.
391
392 const Metachunk* const c = resolve_reference_to_chunk(ref);
393
394 assert(c->is_free() == reference_is_free_chunk(ref), "free info mismatch");
395
396 // Chunks in the tree should be ordered by base address of the range
397 // they represent, and there should be no address holes.
398 if (p == NULL) {
399 p = c->base() + c->word_size();
400 } else {
401 assert(c->base() == p, "Chunk base address mismatch.");
402 }
403
404 c->verify(slow);
405
406 (*num_chunks) ++;
407
408 }
409
410 }
411
412 void ChunkTree::verify(bool slow, const MetaWord* base) const {
413
414 int num_chunks = 0;
415 int num_nodes = 0;
416
417 verify_helper(slow, _root, base, &num_chunks, &num_nodes);
418
419 // Number of chunks in the tree should be equal to the number of chunks
420 // taken from the pool; same for nodes.
421 assert(num_chunks == _chunkPool.used() - _chunkPool.free(), "chunk count mismatch");
422 assert(num_nodes == _nodePool.used() - _nodePool.free(), "node count mismatch");
423
424 }
425
426 #endif // ASSERT
427
428
429
430
431 //// ChunkTreeArray /////////////777
432
433 // Create an array of ChunkTree objects, all initialized to NULL, covering
434 // a given memory range. Memory range must be aligned to size of root chunks.
435 ChunkTreeArray::ChunkTreeArray(const MetaWord* base, size_t word_size)
436 : _base(base), _word_size(word_size),
437 _arr(NULL), _num(0)
438 {
439 assert(is_aligned(_word_size, chklvl::MAX_CHUNK_WORD_SIZE), "not aligned");
440 _num = _word_size / chklvl::MAX_CHUNK_WORD_SIZE;
441 _arr = NEW_C_HEAP_ARRAY(ChunkTree*, _num, mtInternal);
442 for (int i = 0; i < _num; i ++) {
443 _arr[i] = NULL;
444 }
445 }
446
447 ChunkTreeArray::~ChunkTreeArray() {
448 FREE_C_HEAP_ARRAY(ChunkTree*, _arr);
449 }
450
451
452 // Iterate over all nodes in all trees. Returns true for complete traversal,
453 // false if traversal was cancelled.
454 bool ChunkTreeArray::iterate_chunks(ChunkClosure* cc) const {
455 for (int i = 0; i < _num; i ++) {
456 if (_arr[i] != NULL) {
457 if (_arr[i]->iterate_chunks(cc) == false) {
458 return false;
459 }
460 }
461 }
462 }
463
464 #ifdef ASSERT
465 void ChunkTreeArray::verify(bool slow) const {
466 for (int i = 0; i < _num; i ++) {
467 if (_arr[i] != NULL) {
468 _arr[i]->verify(slow, _base);
469 }
470 }
471 }
472 #endif
473
474
475 } // namespace metaspace
476
477