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/msChunkHeaderPool.hpp"
31 #include "memory/metaspace/msChunkManager.hpp"
32 #include "memory/metaspace/msCommon.hpp"
33 #include "memory/metaspace/msFreeChunkList.hpp"
34 #include "memory/metaspace/msMetachunk.hpp"
35 #include "memory/metaspace/msRootChunkArea.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();)
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();)
158 DEBUG_ONLY(c->verify();)
159
160 }
161
162 // Given a chunk, attempt to merge it recursively with its neighboring chunks.
163 //
164 // If successful (merged at least once), returns address of
165 // the merged chunk; NULL otherwise.
166 //
167 // The merged chunks are removed from the freelists.
168 //
169 // !!! Please note that if this method returns a non-NULL value, the
170 // original chunk will be invalid and should not be accessed anymore! !!!
171 Metachunk* RootChunkArea::merge(Metachunk* c, FreeChunkListVector* freelists) {
172
173 // Note rules:
174 //
175 // - a chunk always has a buddy, unless it is a root chunk.
176 // - In that buddy pair, a chunk is either leader or follower.
177 // - a chunk's base address is always aligned at its size.
178 // - if chunk is leader, its base address is also aligned to the size of the next
179 // lower level, at least. A follower chunk is not.
180
181 // How we merge once:
182 //
183 // For a given chunk c, which has to be free and non-root, we do:
184 // - find out if we are the leader or the follower chunk
185 // - if we are leader, next_in_vs must be the follower; if we are follower,
186 // prev_in_vs must be the leader. Now we have the buddy chunk.
187 // - However, if the buddy chunk itself is split (of a level higher than us)
188 // we cannot merge.
189 // - we can only merge if the buddy is of the same level as we are and it is
190 // free.
191 // - Then we merge by simply removing the follower chunk from the address range
192 // linked list (returning the now useless header to the pool) and decreasing
193 // the leader chunk level by one. That makes it double the size.
194
195 // Example:
196 // (lower case chunks are free, the * indicates the chunk we want to merge):
197 //
198 // ........................
199 // d d*c b A <- we return the second (d*) chunk...
200 //
201 // c* c b A <- we merge it with its predecessor and decrease its level...
202 //
203 // b* b A <- we merge it again, since its new neighbor was free too...
204 //
205 // a* A <- we merge it again, since its new neighbor was free too...
206 //
207 // And we are done, since its new neighbor, (A), is not free. We would also be done
208 // if the new neighbor itself is splintered.
209
210 DEBUG_ONLY(check_pointer(c->base());)
211 assert(!c->is_root_chunk(), "Cannot be merged further.");
212 assert(c->is_free(), "Can only merge free chunks.");
213
214 DEBUG_ONLY(c->verify();)
215
216 log_trace(metaspace)("Attempting to merge chunk " METACHUNK_FORMAT ".", METACHUNK_FORMAT_ARGS(c));
217
218 const chunklevel_t starting_level = c->level();
219
220 bool stop = false;
221 Metachunk* result = NULL;
222
223 do {
224
225 // First find out if this chunk is the leader of its pair
226 const bool is_leader = c->is_leader();
227
228 // Note: this is either our buddy or a splinter of the buddy.
229 Metachunk* const buddy = c->is_leader() ? c->next_in_vs() : c->prev_in_vs();
230 DEBUG_ONLY(buddy->verify();)
231
232 // A buddy chunk must be of the same or higher level (so, same size or smaller)
233 // never be larger.
234 assert(buddy->level() >= c->level(), "Sanity");
235
236 // Is this really my buddy (same level) or a splinter of it (higher level)?
237 // Also, is it free?
238 if (buddy->level() != c->level() || buddy->is_free() == false) {
239
240 log_trace(metaspace)("cannot merge with chunk " METACHUNK_FORMAT ".", METACHUNK_FORMAT_ARGS(buddy));
241
242 stop = true;
243
244 } else {
245
246 log_trace(metaspace)("will merge with chunk " METACHUNK_FORMAT ".", METACHUNK_FORMAT_ARGS(buddy));
247
248 // We can merge with the buddy.
249
250 // First, remove buddy from the chunk manager.
251 assert(buddy->is_free(), "Sanity");
252 freelists->remove(buddy);
253
254 // Determine current leader and follower
255 Metachunk* leader;
256 Metachunk* follower;
257 if (is_leader) {
258 leader = c; follower = buddy;
259 } else {
260 leader = buddy; follower = c;
261 }
262
263 // Last checkpoint
264 assert(leader->end() == follower->base() &&
265 leader->level() == follower->level() &&
266 leader->is_free() && follower->is_free(), "Sanity");
267
268 // The new merged chunk is as far committed as possible (if leader
269 // chunk is fully committed, as far as the follower chunk).
270 size_t merged_committed_words = leader->committed_words();
271 if (merged_committed_words == leader->word_size()) {
272 merged_committed_words += follower->committed_words();
273 }
274
275 // Leader survives, follower chunk is freed. Remove follower from vslist ..
276 leader->set_next_in_vs(follower->next_in_vs());
277 if (follower->next_in_vs() != NULL) {
278 follower->next_in_vs()->set_prev_in_vs(leader);
279 }
280
281 // .. and return follower chunk header to pool for reuse.
282 ChunkHeaderPool::pool()->return_chunk_header(follower);
283
284 // Leader level gets decreased (leader chunk doubles in size) but
285 // base address stays the same.
286 leader->dec_level();
287
288 // set commit boundary
289 leader->set_committed_words(merged_committed_words);
290
291 // If the leader is now of root chunk size, stop merging
292 if (leader->is_root_chunk()) {
293 stop = true;
294 }
295
296 result = c = leader;
297
298 DEBUG_ONLY(leader->verify();)
299
300 }
301
302 } while (!stop);
303
304 #ifdef ASSERT
305 verify();
306 if (result != NULL) {
307 result->verify();
308 }
309 #endif // ASSERT
310
311 return result;
312
313 }
314
315 // Given a chunk c, which must be "in use" and must not be a root chunk, attempt to
316 // enlarge it in place by claiming its trailing buddy.
317 //
318 // This will only work if c is the leader of the buddy pair and the trailing buddy is free.
319 //
320 // If successful, the follower chunk will be removed from the freelists, the leader chunk c will
321 // double in size (level decreased by one).
322 //
323 // On success, true is returned, false otherwise.
324 bool RootChunkArea::attempt_enlarge_chunk(Metachunk* c, FreeChunkListVector* freelists) {
325
326 DEBUG_ONLY(check_pointer(c->base());)
327 assert(!c->is_root_chunk(), "Cannot be merged further.");
328
329 // There is no real reason for this limitation other than it is not
330 // needed on free chunks since they should be merged already:
331 assert(c->is_in_use(), "Can only enlarge in use chunks.");
332
333 DEBUG_ONLY(c->verify();)
334
335 if (!c->is_leader()) {
336 return false;
337 }
338
339 // We are the leader, so the buddy must follow us.
340 Metachunk* const buddy = c->next_in_vs();
341 DEBUG_ONLY(buddy->verify();)
342
343 // Of course buddy cannot be larger than us.
344 assert(buddy->level() >= c->level(), "Sanity");
345
346 // We cannot merge buddy in if it is not free...
347 if (!buddy->is_free()) {
348 return false;
349 }
350
351 // ... nor if it is splintered.
352 if (buddy->level() != c->level()) {
353 return false;
354 }
355
356 // Okay, lets enlarge c.
357
358 log_trace(metaspace)("Enlarging chunk " METACHUNK_FULL_FORMAT " by merging in follower " METACHUNK_FULL_FORMAT ".",
359 METACHUNK_FULL_FORMAT_ARGS(c), METACHUNK_FULL_FORMAT_ARGS(buddy));
360
361 // the enlarged c is as far committed as possible:
362 size_t merged_committed_words = c->committed_words();
363 if (merged_committed_words == c->word_size()) {
364 merged_committed_words += buddy->committed_words();
365 }
366
367 // Remove buddy from vs list...
368 Metachunk* successor = buddy->next_in_vs();
369 if (successor != NULL) {
370 successor->set_prev_in_vs(c);
371 }
372 c->set_next_in_vs(successor);
373
374 // .. and from freelist ...
375 freelists->remove(buddy);
376
377 // .. and return its empty husk to the pool...
378 ChunkHeaderPool::pool()->return_chunk_header(buddy);
379
380 // Then decrease level of c.
381 c->dec_level();
382
383 // and correct committed words if needed.
384 c->set_committed_words(merged_committed_words);
385
386 log_debug(metaspace)("Enlarged chunk " METACHUNK_FULL_FORMAT ".", METACHUNK_FULL_FORMAT_ARGS(c));
387 // log_debug(metaspace)("Enlarged chunk " METACHUNK_FORMAT ".", METACHUNK_FORMAT_ARGS(c));
388
389 DEBUG_ONLY(verify());
390
391 return true;
392
393 }
394
395 // Returns true if this root chunk area is completely free:
396 // In that case, it should only contain one chunk (maximally merged, so a root chunk)
397 // and it should be free.
398 bool RootChunkArea::is_free() const {
399 return _first_chunk == NULL ||
400 (_first_chunk->is_root_chunk() && _first_chunk->is_free());
401 }
402
403 #ifdef ASSERT
404
405 #define assrt_(cond, ...) \
406 if (!(cond)) { \
407 fdStream errst(2); \
408 this->print_on(&errst); \
409 vmassert(cond, __VA_ARGS__); \
410 }
411
412 void RootChunkArea::verify() const {
413
414 assert_lock_strong(MetaspaceExpand_lock);
415 assert_is_aligned(_base, chunklevel::MAX_CHUNK_BYTE_SIZE);
416
417 // Iterate thru all chunks in this area. They must be ordered correctly,
418 // being adjacent to each other, and cover the complete area
419 int num_chunk = 0;
420
421 if (_first_chunk != NULL) {
422
423 assrt_(_first_chunk->prev_in_vs() == NULL, "Sanity");
424
425 const Metachunk* c = _first_chunk;
426 const MetaWord* expected_next_base = _base;
427 const MetaWord* const area_end = _base + word_size();
428
429 while (c != NULL) {
430
431 assrt_(c->is_free() || c->is_in_use(),
432 "Chunk No. %d " METACHUNK_FORMAT " - invalid state.",
433 num_chunk, METACHUNK_FORMAT_ARGS(c));
434
435 assrt_(c->base() == expected_next_base,
436 "Chunk No. %d " METACHUNK_FORMAT " - unexpected base.",
437 num_chunk, METACHUNK_FORMAT_ARGS(c));
438
439 assrt_(c->base() >= base() && c->end() <= end(),
440 "chunk %d " METACHUNK_FORMAT " oob for this root area [" PTR_FORMAT ".." PTR_FORMAT ").",
441 num_chunk, METACHUNK_FORMAT_ARGS(c), p2i(base()), p2i(end()));
442
443 assrt_(is_aligned(c->base(), c->word_size()),
444 "misaligned chunk %d " METACHUNK_FORMAT ".", num_chunk, METACHUNK_FORMAT_ARGS(c));
445
446 c->verify_neighborhood();
447 c->verify();
448
449 expected_next_base = c->end();
450 num_chunk++;
451
452 c = c->next_in_vs();
453
454 }
455 assrt_(expected_next_base == _base + word_size(), "Sanity");
456 }
457
458 }
459
460 void RootChunkArea::verify_area_is_ideally_merged() const {
461
462 SOMETIMES(assert_lock_strong(MetaspaceExpand_lock);)
463
464 int num_chunk = 0;
465 for (const Metachunk* c = _first_chunk; c != NULL; c = c->next_in_vs()) {
466 if (!c->is_root_chunk() && c->is_free()) {
467 // If a chunk is free, it must not have a buddy which is also free, because
468 // those chunks should have been merged.
469 // In other words, a buddy shall be either in-use or splintered
470 // (which in turn would mean part of it are in use).
471 Metachunk* const buddy = c->is_leader() ? c->next_in_vs() : c->prev_in_vs();
472 assrt_(buddy->is_in_use() || buddy->level() > c->level(),
473 "Chunk No. %d " METACHUNK_FORMAT " : missed merge opportunity with neighbor " METACHUNK_FORMAT ".",
474 num_chunk, METACHUNK_FORMAT_ARGS(c), METACHUNK_FORMAT_ARGS(buddy));
475 }
476 num_chunk++;
477 }
478 }
479
480 #endif
481
482 void RootChunkArea::print_on(outputStream* st) const {
483
484 st->print(PTR_FORMAT ": ", p2i(base()));
485 if (_first_chunk != NULL) {
486 const Metachunk* c = _first_chunk;
487 // 01234567890123
488 const char* letters_for_levels_cap = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
489 const char* letters_for_levels = "abcdefghijklmnopqrstuvwxyz";
490 while (c != NULL) {
491 const chunklevel_t l = c->level();
492 if (l >= 0 && (size_t)l < strlen(letters_for_levels)) {
493 // c->print_on(st); st->cr();
494 st->print("%c", c->is_free() ? letters_for_levels[c->level()] : letters_for_levels_cap[c->level()]);
495 } else {
496 // Obviously garbage, but lets not crash.
497 st->print("?");
498 }
499 c = c->next_in_vs();
500 }
501 } else {
502 st->print(" (no chunks)");
503 }
504 st->cr();
505
506 }
507
508 // Create an array of ChunkTree objects, all initialized to NULL, covering
509 // a given memory range. Memory range must be a multiple of root chunk size.
510 RootChunkAreaLUT::RootChunkAreaLUT(const MetaWord* base, size_t word_size)
511 : _base(base),
512 _num((int)(word_size / chunklevel::MAX_CHUNK_WORD_SIZE)),
513 _arr(NULL)
514 {
515 assert_is_aligned(word_size, chunklevel::MAX_CHUNK_WORD_SIZE);
516 _arr = NEW_C_HEAP_ARRAY(RootChunkArea, _num, mtClass);
517 const MetaWord* this_base = _base;
518 for (int i = 0; i < _num; i++) {
519 RootChunkArea* rca = new(_arr + i) RootChunkArea(this_base);
520 assert(rca == _arr + i, "Sanity");
521 this_base += chunklevel::MAX_CHUNK_WORD_SIZE;
522 }
523 }
524
525 RootChunkAreaLUT::~RootChunkAreaLUT() {
526 for (int i = 0; i < _num; i++) {
527 _arr[i].~RootChunkArea();
528 }
529 FREE_C_HEAP_ARRAY(RootChunkArea, _arr);
530 }
531
532 // Returns true if all areas in this area table are free (only contain free chunks).
533 bool RootChunkAreaLUT::is_free() const {
534 for (int i = 0; i < _num; i++) {
535 if (!_arr[i].is_free()) {
536 return false;
537 }
538 }
539 return true;
540 }
541
542 #ifdef ASSERT
543
544 void RootChunkAreaLUT::verify() const {
545 for (int i = 0; i < _num; i++) {
546 check_pointer(_arr[i].base());
547 _arr[i].verify();
548 }
549 }
550
551 #endif
552
553 void RootChunkAreaLUT::print_on(outputStream* st) const {
554 for (int i = 0; i < _num; i++) {
555 st->print("%2d:", i);
556 _arr[i].print_on(st);
557 }
558 }
559
560 } // end: namespace metaspace