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