1 /*
2 * Copyright (c) 2016, 2021, Red Hat, Inc. 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
25 #include "precompiled.hpp"
26 #include "gc/shared/tlab_globals.hpp"
27 #include "gc/shenandoah/shenandoahBarrierSet.hpp"
28 #include "gc/shenandoah/shenandoahFreeSet.hpp"
29 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
30 #include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
31 #include "gc/shenandoah/shenandoahMarkingContext.inline.hpp"
32 #include "gc/shenandoah/shenandoahOldGeneration.hpp"
33 #include "gc/shenandoah/shenandoahScanRemembered.inline.hpp"
34 #include "gc/shenandoah/shenandoahYoungGeneration.hpp"
35 #include "logging/logStream.hpp"
36 #include "memory/resourceArea.hpp"
37 #include "runtime/orderAccess.hpp"
38
39 ShenandoahFreeSet::ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions) :
40 _heap(heap),
41 _mutator_free_bitmap(max_regions, mtGC),
42 _collector_free_bitmap(max_regions, mtGC),
43 _max(max_regions)
44 {
45 clear_internal();
46 }
47
48 void ShenandoahFreeSet::increase_used(size_t num_bytes) {
49 shenandoah_assert_heaplocked();
50 _used += num_bytes;
51
52 assert(_used <= _capacity, "must not use more than we have: used: " SIZE_FORMAT
53 ", capacity: " SIZE_FORMAT ", num_bytes: " SIZE_FORMAT, _used, _capacity, num_bytes);
54 }
55
56 bool ShenandoahFreeSet::is_mutator_free(size_t idx) const {
57 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT " (left: " SIZE_FORMAT ", right: " SIZE_FORMAT ")",
58 idx, _max, _mutator_leftmost, _mutator_rightmost);
59 return _mutator_free_bitmap.at(idx);
60 }
61
62 bool ShenandoahFreeSet::is_collector_free(size_t idx) const {
63 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT " (left: " SIZE_FORMAT ", right: " SIZE_FORMAT ")",
64 idx, _max, _collector_leftmost, _collector_rightmost);
65 return _collector_free_bitmap.at(idx);
66 }
67
68 // This is a temporary solution to work around a shortcoming with the existing free set implementation.
69 // TODO:
70 // Remove this function after restructing FreeSet representation. A problem in the existing implementation is that old-gen
71 // regions are not considered to reside within the is_collector_free range.
72 //
73 HeapWord* ShenandoahFreeSet::allocate_with_old_affiliation(ShenandoahAllocRequest& req, bool& in_new_region) {
74 ShenandoahRegionAffiliation affiliation = ShenandoahRegionAffiliation::OLD_GENERATION;
75
76 size_t rightmost = MAX2(_collector_rightmost, _mutator_rightmost);
77 size_t leftmost = MIN2(_collector_leftmost, _mutator_leftmost);
78
79 for (size_t c = rightmost + 1; c > leftmost; c--) {
80 // size_t is unsigned, need to dodge underflow when _leftmost = 0
81 size_t idx = c - 1;
82 ShenandoahHeapRegion* r = _heap->get_region(idx);
83 if (r->affiliation() == affiliation && !r->is_humongous()) {
84 if (!r->is_cset() && !has_no_alloc_capacity(r)) {
85 HeapWord* result = try_allocate_in(r, req, in_new_region);
86 if (result != NULL) {
87 return result;
88 }
89 }
90 }
91 }
92 return nullptr;
93 }
94
95 HeapWord* ShenandoahFreeSet::allocate_with_affiliation(ShenandoahRegionAffiliation affiliation, ShenandoahAllocRequest& req, bool& in_new_region) {
96 for (size_t c = _collector_rightmost + 1; c > _collector_leftmost; c--) {
97 // size_t is unsigned, need to dodge underflow when _leftmost = 0
98 size_t idx = c - 1;
99 if (is_collector_free(idx)) {
100 ShenandoahHeapRegion* r = _heap->get_region(idx);
101 if (r->affiliation() == affiliation) {
102 HeapWord* result = try_allocate_in(r, req, in_new_region);
103 if (result != NULL) {
104 return result;
105 }
106 }
107 }
108 }
109 return NULL;
110 }
111
112 HeapWord* ShenandoahFreeSet::allocate_single(ShenandoahAllocRequest& req, bool& in_new_region) {
113 // Scan the bitmap looking for a first fit.
114 //
115 // Leftmost and rightmost bounds provide enough caching to walk bitmap efficiently. Normally,
116 // we would find the region to allocate at right away.
117 //
118 // Allocations are biased: new application allocs go to beginning of the heap, and GC allocs
119 // go to the end. This makes application allocation faster, because we would clear lots
120 // of regions from the beginning most of the time.
121 //
122 // Free set maintains mutator and collector views, and normally they allocate in their views only,
123 // unless we special cases for stealing and mixed allocations.
124
125 // Overwrite with non-zero (non-NULL) values only if necessary for allocation bookkeeping.
126
127 bool allow_new_region = true;
128 switch (req.affiliation()) {
129 case ShenandoahRegionAffiliation::OLD_GENERATION:
130 // Note: unsigned result from adjusted_unaffiliated_regions() will never be less than zero, but it may equal zero.
131 if (_heap->old_generation()->adjusted_unaffiliated_regions() <= 0) {
132 allow_new_region = false;
133 }
134 break;
135
136 case ShenandoahRegionAffiliation::YOUNG_GENERATION:
137 // Note: unsigned result from adjusted_unaffiliated_regions() will never be less than zero, but it may equal zero.
138 if (_heap->young_generation()->adjusted_unaffiliated_regions() <= 0) {
139 allow_new_region = false;
140 }
141 break;
142
143 case ShenandoahRegionAffiliation::FREE:
144 default:
145 ShouldNotReachHere();
146 break;
147 }
148
149 switch (req.type()) {
150 case ShenandoahAllocRequest::_alloc_tlab:
151 case ShenandoahAllocRequest::_alloc_shared: {
152 // Try to allocate in the mutator view
153 for (size_t idx = _mutator_leftmost; idx <= _mutator_rightmost; idx++) {
154 ShenandoahHeapRegion* r = _heap->get_region(idx);
155 if (is_mutator_free(idx) && (allow_new_region || r->affiliation() != ShenandoahRegionAffiliation::FREE)) {
156 // try_allocate_in() increases used if the allocation is successful.
157 HeapWord* result = try_allocate_in(r, req, in_new_region);
158 if (result != NULL) {
159 return result;
160 }
161 }
162 }
163 // There is no recovery. Mutator does not touch collector view at all.
164 break;
165 }
166 case ShenandoahAllocRequest::_alloc_gclab:
167 // GCLABs are for evacuation so we must be in evacuation phase. If this allocation is successful, increment
168 // the relevant evac_expended rather than used value.
169
170 case ShenandoahAllocRequest::_alloc_plab:
171 // PLABs always reside in old-gen and are only allocated during evacuation phase.
172
173 case ShenandoahAllocRequest::_alloc_shared_gc: {
174 // First try to fit into a region that is already in use in the same generation.
175 HeapWord* result;
176 if (req.affiliation() == ShenandoahRegionAffiliation::OLD_GENERATION) {
177 // TODO: this is a work around to address a deficiency in FreeSet representation. A better solution fixes
178 // the FreeSet implementation to deal more efficiently with old-gen regions as being in the "collector free set"
179 result = allocate_with_old_affiliation(req, in_new_region);
180 } else {
181 result = allocate_with_affiliation(req.affiliation(), req, in_new_region);
182 }
183 if (result != NULL) {
184 return result;
185 }
186 if (allow_new_region) {
187 // Then try a free region that is dedicated to GC allocations.
188 result = allocate_with_affiliation(FREE, req, in_new_region);
189 if (result != NULL) {
190 return result;
191 }
192 }
193
194 // No dice. Can we borrow space from mutator view?
195 if (!ShenandoahEvacReserveOverflow) {
196 return NULL;
197 }
198
199 if (allow_new_region) {
200 // Try to steal an empty region from the mutator view.
201 for (size_t c = _mutator_rightmost + 1; c > _mutator_leftmost; c--) {
202 size_t idx = c - 1;
203 if (is_mutator_free(idx)) {
204 ShenandoahHeapRegion* r = _heap->get_region(idx);
205 if (can_allocate_from(r)) {
206 flip_to_gc(r);
207 HeapWord *result = try_allocate_in(r, req, in_new_region);
208 if (result != NULL) {
209 return result;
210 }
211 }
212 }
213 }
214 }
215
216 // No dice. Do not try to mix mutator and GC allocations, because
217 // URWM moves due to GC allocations would expose unparsable mutator
218 // allocations.
219 break;
220 }
221 default:
222 ShouldNotReachHere();
223 }
224 return NULL;
225 }
226
227 HeapWord* ShenandoahFreeSet::try_allocate_in(ShenandoahHeapRegion* r, ShenandoahAllocRequest& req, bool& in_new_region) {
228 assert (!has_no_alloc_capacity(r), "Performance: should avoid full regions on this path: " SIZE_FORMAT, r->index());
229
230 if (_heap->is_concurrent_weak_root_in_progress() &&
231 r->is_trash()) {
232 return NULL;
233 }
234 try_recycle_trashed(r);
235 if (r->affiliation() == ShenandoahRegionAffiliation::FREE) {
236 ShenandoahMarkingContext* const ctx = _heap->complete_marking_context();
237 r->set_affiliation(req.affiliation());
238 if (r->is_old()) {
239 // Any OLD region allocated during concurrent coalesce-and-fill does not need to be coalesced and filled because
240 // all objects allocated within this region are above TAMS (and thus are implicitly marked). In case this is an
241 // OLD region and concurrent preparation for mixed evacuations visits this region before the start of the next
242 // old-gen concurrent mark (i.e. this region is allocated following the start of old-gen concurrent mark but before
243 // concurrent preparations for mixed evacuations are completed), we mark this region as not requiring any
244 // coalesce-and-fill processing.
245 r->end_preemptible_coalesce_and_fill();
246 _heap->clear_cards_for(r);
247 }
248
249 assert(ctx->top_at_mark_start(r) == r->bottom(), "Newly established allocation region starts with TAMS equal to bottom");
250 assert(ctx->is_bitmap_clear_range(ctx->top_bitmap(r), r->end()), "Bitmap above top_bitmap() must be clear");
251
252 // Leave top_bitmap alone. The first time a heap region is put into service, top_bitmap should equal end.
253 // Thereafter, it should represent the upper bound on parts of the bitmap that need to be cleared.
254 log_debug(gc)("NOT clearing bitmap for region " SIZE_FORMAT ", top_bitmap: "
255 PTR_FORMAT " at transition from FREE to %s",
256 r->index(), p2i(ctx->top_bitmap(r)), affiliation_name(req.affiliation()));
257 } else if (r->affiliation() != req.affiliation()) {
258 return NULL;
259 }
260
261 in_new_region = r->is_empty();
262 HeapWord* result = NULL;
263 size_t size = req.size();
264
265 // req.size() is in words, r->free() is in bytes.
266 if (ShenandoahElasticTLAB && req.is_lab_alloc()) {
267 if (req.type() == ShenandoahAllocRequest::_alloc_plab) {
268 // Need to assure that plabs are aligned on multiple of card region.
269 size_t free = r->free();
270 size_t usable_free = (free / CardTable::card_size()) << CardTable::card_shift();
271 if ((free != usable_free) && (free - usable_free < ShenandoahHeap::min_fill_size() * HeapWordSize)) {
272 // We'll have to add another card's memory to the padding
273 if (usable_free > CardTable::card_size()) {
274 usable_free -= CardTable::card_size();
275 } else {
276 assert(usable_free == 0, "usable_free is a multiple of card_size and card_size > min_fill_size");
277 }
278 }
279 free /= HeapWordSize;
280 usable_free /= HeapWordSize;
281 size_t remnant = size % CardTable::card_size_in_words();
282 if (remnant > 0) {
283 // Since we have Elastic TLABs, align size up. This is consistent with aligning min_size up.
284 size = size - remnant + CardTable::card_size_in_words();
285 }
286 if (size > usable_free) {
287 size = usable_free;
288 assert(size % CardTable::card_size_in_words() == 0, "usable_free is a multiple of card table size");
289 }
290
291 size_t adjusted_min_size = req.min_size();
292 remnant = adjusted_min_size % CardTable::card_size_in_words();
293 if (remnant > 0) {
294 // Round up adjusted_min_size to a multiple of alignment size
295 adjusted_min_size = adjusted_min_size - remnant + CardTable::card_size_in_words();
296 }
297 if (size >= adjusted_min_size) {
298 result = r->allocate_aligned(size, req, CardTable::card_size());
299 assert(result != nullptr, "Allocation cannot fail");
300 size = req.actual_size();
301 assert(r->top() <= r->end(), "Allocation cannot span end of region");
302 // actual_size() will be set to size below.
303 assert((result == nullptr) || (size % CardTable::card_size_in_words() == 0),
304 "PLAB size must be multiple of card size");
305 assert((result == nullptr) || (((uintptr_t) result) % CardTable::card_size_in_words() == 0),
306 "PLAB start must align with card boundary");
307 if (free > usable_free) {
308 // Account for the alignment padding
309 size_t padding = (free - usable_free) * HeapWordSize;
310 increase_used(padding);
311 assert(r->affiliation() == ShenandoahRegionAffiliation::OLD_GENERATION, "All PLABs reside in old-gen");
312 _heap->old_generation()->increase_used(padding);
313 // For verification consistency, we need to report this padding to _heap
314 _heap->increase_used(padding);
315 }
316 }
317 // Otherwise, leave result == NULL because the adjusted size is smaller than min size.
318 } else {
319 // This is a GCLAB or a TLAB allocation
320 size_t free = align_down(r->free() >> LogHeapWordSize, MinObjAlignment);
321 if (size > free) {
322 size = free;
323 }
324 if (size >= req.min_size()) {
325 result = r->allocate(size, req);
326 if (result != nullptr) {
327 // Record actual allocation size
328 req.set_actual_size(size);
329 }
330 assert (result != NULL, "Allocation must succeed: free " SIZE_FORMAT ", actual " SIZE_FORMAT, free, size);
331 } else {
332 log_trace(gc, ergo)("Failed to shrink TLAB or GCLAB request (" SIZE_FORMAT ") in region " SIZE_FORMAT " to " SIZE_FORMAT
333 " because min_size() is " SIZE_FORMAT, req.size(), r->index(), size, req.min_size());
334 }
335 }
336 } else if (req.is_lab_alloc() && req.type() == ShenandoahAllocRequest::_alloc_plab) {
337 // inelastic PLAB
338 size_t free = r->free();
339 size_t usable_free = (free / CardTable::card_size()) << CardTable::card_shift();
340 free /= HeapWordSize;
341 usable_free /= HeapWordSize;
342 if ((free != usable_free) && (free - usable_free < ShenandoahHeap::min_fill_size() * HeapWordSize)) {
343 // We'll have to add another card's memory to the padding
344 if (usable_free > CardTable::card_size_in_words()) {
345 usable_free -= CardTable::card_size_in_words();
346 } else {
347 assert(usable_free == 0, "usable_free is a multiple of card_size and card_size > min_fill_size");
348 }
349 }
350 assert(size % CardTable::card_size_in_words() == 0, "PLAB size must be multiple of remembered set card size");
351 if (size <= usable_free) {
352 result = r->allocate_aligned(size, req, CardTable::card_size());
353 size = req.actual_size();
354 assert(result != nullptr, "Allocation cannot fail");
355 assert(r->top() <= r->end(), "Allocation cannot span end of region");
356 assert(req.actual_size() % CardTable::card_size_in_words() == 0, "PLAB start must align with card boundary");
357 assert(((uintptr_t) result) % CardTable::card_size_in_words() == 0, "PLAB start must align with card boundary");
358 if (free > usable_free) {
359 // Account for the alignment padding
360 size_t padding = (free - usable_free) * HeapWordSize;
361 increase_used(padding);
362 assert(r->affiliation() == ShenandoahRegionAffiliation::OLD_GENERATION, "All PLABs reside in old-gen");
363 _heap->old_generation()->increase_used(padding);
364 // For verification consistency, we need to report this padding to _heap
365 _heap->increase_used(padding);
366 }
367 }
368 } else {
369 result = r->allocate(size, req);
370 if (result != nullptr) {
371 // Record actual allocation size
372 req.set_actual_size(size);
373 }
374 }
375
376 if (result != NULL) {
377 // Allocation successful, bump stats:
378 if (req.is_mutator_alloc()) {
379 // Mutator allocations always pull from young gen.
380 _heap->young_generation()->increase_used(size * HeapWordSize);
381 increase_used(size * HeapWordSize);
382 } else {
383 assert(req.is_gc_alloc(), "Should be gc_alloc since req wasn't mutator alloc");
384
385 // For GC allocations, we advance update_watermark because the objects relocated into this memory during
386 // evacuation are not updated during evacuation. For both young and old regions r, it is essential that all
387 // PLABs be made parsable at the end of evacuation. This is enabled by retiring all plabs at end of evacuation.
388 // TODO: Making a PLAB parsable involves placing a filler object in its remnant memory but does not require
389 // that the PLAB be disabled for all future purposes. We may want to introduce a new service to make the
390 // PLABs parsable while still allowing the PLAB to serve future allocation requests that arise during the
391 // next evacuation pass.
392 r->set_update_watermark(r->top());
393
394 if (r->affiliation() == ShenandoahRegionAffiliation::YOUNG_GENERATION) {
395 _heap->young_generation()->increase_used(size * HeapWordSize);
396 } else {
397 assert(r->affiliation() == ShenandoahRegionAffiliation::OLD_GENERATION, "GC Alloc was not YOUNG so must be OLD");
398 assert(req.type() != ShenandoahAllocRequest::_alloc_gclab, "old-gen allocations use PLAB or shared allocation");
399 _heap->old_generation()->increase_used(size * HeapWordSize);
400 // for plabs, we'll sort the difference between evac and promotion usage when we retire the plab
401 }
402 }
403 }
404 if (result == NULL || has_no_alloc_capacity(r)) {
405 // Region cannot afford this or future allocations. Retire it.
406 //
407 // While this seems a bit harsh, especially in the case when this large allocation does not
408 // fit, but the next small one would, we are risking to inflate scan times when lots of
409 // almost-full regions precede the fully-empty region where we want to allocate the entire TLAB.
410 // TODO: Record first fully-empty region, and use that for large allocations and/or organize
411 // available free segments within regions for more efficient searches for "good fit".
412
413 // Record the remainder as allocation waste
414 if (req.is_mutator_alloc()) {
415 size_t waste = r->free();
416 if (waste > 0) {
417 increase_used(waste);
418 _heap->generation_for(req.affiliation())->increase_allocated(waste);
419 _heap->notify_mutator_alloc_words(waste >> LogHeapWordSize, true);
420 }
421 }
422
423 size_t num = r->index();
424 _collector_free_bitmap.clear_bit(num);
425 _mutator_free_bitmap.clear_bit(num);
426 // Touched the bounds? Need to update:
427 if (touches_bounds(num)) {
428 adjust_bounds();
429 }
430 assert_bounds();
431 }
432 return result;
433 }
434
435 bool ShenandoahFreeSet::touches_bounds(size_t num) const {
436 return num == _collector_leftmost || num == _collector_rightmost || num == _mutator_leftmost || num == _mutator_rightmost;
437 }
438
439 void ShenandoahFreeSet::recompute_bounds() {
440 // Reset to the most pessimistic case:
441 _mutator_rightmost = _max - 1;
442 _mutator_leftmost = 0;
443 _collector_rightmost = _max - 1;
444 _collector_leftmost = 0;
445
446 // ...and adjust from there
447 adjust_bounds();
448 }
449
450 void ShenandoahFreeSet::adjust_bounds() {
451 // Rewind both mutator bounds until the next bit.
452 while (_mutator_leftmost < _max && !is_mutator_free(_mutator_leftmost)) {
453 _mutator_leftmost++;
454 }
455 while (_mutator_rightmost > 0 && !is_mutator_free(_mutator_rightmost)) {
456 _mutator_rightmost--;
457 }
458 // Rewind both collector bounds until the next bit.
459 while (_collector_leftmost < _max && !is_collector_free(_collector_leftmost)) {
460 _collector_leftmost++;
461 }
462 while (_collector_rightmost > 0 && !is_collector_free(_collector_rightmost)) {
463 _collector_rightmost--;
464 }
465 }
466
467 HeapWord* ShenandoahFreeSet::allocate_contiguous(ShenandoahAllocRequest& req) {
468 shenandoah_assert_heaplocked();
469
470 size_t words_size = req.size();
471 size_t num = ShenandoahHeapRegion::required_regions(words_size * HeapWordSize);
472
473 assert(req.affiliation() == ShenandoahRegionAffiliation::YOUNG_GENERATION, "Humongous regions always allocated in YOUNG");
474 size_t avail_young_regions = _heap->young_generation()->adjusted_unaffiliated_regions();
475
476 // No regions left to satisfy allocation, bye.
477 if (num > mutator_count() || (num > avail_young_regions)) {
478 return NULL;
479 }
480
481 // Find the continuous interval of $num regions, starting from $beg and ending in $end,
482 // inclusive. Contiguous allocations are biased to the beginning.
483
484 size_t beg = _mutator_leftmost;
485 size_t end = beg;
486
487 while (true) {
488 if (end >= _max) {
489 // Hit the end, goodbye
490 return NULL;
491 }
492
493 // If regions are not adjacent, then current [beg; end] is useless, and we may fast-forward.
494 // If region is not completely free, the current [beg; end] is useless, and we may fast-forward.
495 if (!is_mutator_free(end) || !can_allocate_from(_heap->get_region(end))) {
496 end++;
497 beg = end;
498 continue;
499 }
500
501 if ((end - beg + 1) == num) {
502 // found the match
503 break;
504 }
505
506 end++;
507 };
508
509 size_t remainder = words_size & ShenandoahHeapRegion::region_size_words_mask();
510 ShenandoahMarkingContext* const ctx = _heap->complete_marking_context();
511
512 // Initialize regions:
513 for (size_t i = beg; i <= end; i++) {
514 ShenandoahHeapRegion* r = _heap->get_region(i);
515 try_recycle_trashed(r);
516
517 assert(i == beg || _heap->get_region(i - 1)->index() + 1 == r->index(), "Should be contiguous");
518 assert(r->is_empty(), "Should be empty");
519
520 if (i == beg) {
521 r->make_humongous_start();
522 } else {
523 r->make_humongous_cont();
524 }
525
526 // Trailing region may be non-full, record the remainder there
527 size_t used_words;
528 if ((i == end) && (remainder != 0)) {
529 used_words = remainder;
530 } else {
531 used_words = ShenandoahHeapRegion::region_size_words();
532 }
533
534 r->set_affiliation(req.affiliation());
535 r->set_update_watermark(r->bottom());
536 r->set_top(r->bottom()); // Set top to bottom so we can capture TAMS
537 ctx->capture_top_at_mark_start(r);
538 r->set_top(r->bottom() + used_words); // Then change top to reflect allocation of humongous object.
539 assert(ctx->top_at_mark_start(r) == r->bottom(), "Newly established allocation region starts with TAMS equal to bottom");
540 assert(ctx->is_bitmap_clear_range(ctx->top_bitmap(r), r->end()), "Bitmap above top_bitmap() must be clear");
541
542 // Leave top_bitmap alone. The first time a heap region is put into service, top_bitmap should equal end.
543 // Thereafter, it should represent the upper bound on parts of the bitmap that need to be cleared.
544 // ctx->clear_bitmap(r);
545 log_debug(gc)("NOT clearing bitmap for Humongous region [" PTR_FORMAT ", " PTR_FORMAT "], top_bitmap: "
546 PTR_FORMAT " at transition from FREE to %s",
547 p2i(r->bottom()), p2i(r->end()), p2i(ctx->top_bitmap(r)), affiliation_name(req.affiliation()));
548
549 _mutator_free_bitmap.clear_bit(r->index());
550 }
551
552 // While individual regions report their true use, all humongous regions are
553 // marked used in the free set.
554 increase_used(ShenandoahHeapRegion::region_size_bytes() * num);
555 if (req.affiliation() == ShenandoahRegionAffiliation::YOUNG_GENERATION) {
556 _heap->young_generation()->increase_used(words_size * HeapWordSize);
557 } else if (req.affiliation() == ShenandoahRegionAffiliation::OLD_GENERATION) {
558 _heap->old_generation()->increase_used(words_size * HeapWordSize);
559 }
560
561 if (remainder != 0) {
562 // Record this remainder as allocation waste
563 size_t waste = ShenandoahHeapRegion::region_size_words() - remainder;
564 _heap->notify_mutator_alloc_words(waste, true);
565 _heap->generation_for(req.affiliation())->increase_allocated(waste * HeapWordSize);
566 }
567
568 // Allocated at left/rightmost? Move the bounds appropriately.
569 if (beg == _mutator_leftmost || end == _mutator_rightmost) {
570 adjust_bounds();
571 }
572 assert_bounds();
573 req.set_actual_size(words_size);
574 return _heap->get_region(beg)->bottom();
575 }
576
577 bool ShenandoahFreeSet::can_allocate_from(ShenandoahHeapRegion *r) {
578 return r->is_empty() || (r->is_trash() && !_heap->is_concurrent_weak_root_in_progress());
579 }
580
581 size_t ShenandoahFreeSet::alloc_capacity(ShenandoahHeapRegion *r) {
582 if (r->is_trash()) {
583 // This would be recycled on allocation path
584 return ShenandoahHeapRegion::region_size_bytes();
585 } else {
586 return r->free();
587 }
588 }
589
590 bool ShenandoahFreeSet::has_no_alloc_capacity(ShenandoahHeapRegion *r) {
591 return alloc_capacity(r) == 0;
592 }
593
594 void ShenandoahFreeSet::try_recycle_trashed(ShenandoahHeapRegion *r) {
595 if (r->is_trash()) {
596 _heap->decrease_used(r->used());
597 r->recycle();
598 }
599 }
600
601 void ShenandoahFreeSet::recycle_trash() {
602 // lock is not reentrable, check we don't have it
603 shenandoah_assert_not_heaplocked();
604 for (size_t i = 0; i < _heap->num_regions(); i++) {
605 ShenandoahHeapRegion* r = _heap->get_region(i);
606 if (r->is_trash()) {
607 ShenandoahHeapLocker locker(_heap->lock());
608 try_recycle_trashed(r);
609 }
610 SpinPause(); // allow allocators to take the lock
611 }
612 }
613
614 void ShenandoahFreeSet::flip_to_gc(ShenandoahHeapRegion* r) {
615 size_t idx = r->index();
616
617 assert(_mutator_free_bitmap.at(idx), "Should be in mutator view");
618 assert(can_allocate_from(r), "Should not be allocated");
619
620 _mutator_free_bitmap.clear_bit(idx);
621 _collector_free_bitmap.set_bit(idx);
622 _collector_leftmost = MIN2(idx, _collector_leftmost);
623 _collector_rightmost = MAX2(idx, _collector_rightmost);
624
625 _capacity -= alloc_capacity(r);
626
627 if (touches_bounds(idx)) {
628 adjust_bounds();
629 }
630 assert_bounds();
631
632 // We do not ensure that the region is no longer trash,
633 // relying on try_allocate_in(), which always comes next,
634 // to recycle trash before attempting to allocate anything in the region.
635 }
636
637 void ShenandoahFreeSet::clear() {
638 shenandoah_assert_heaplocked();
639 clear_internal();
640 }
641
642 void ShenandoahFreeSet::clear_internal() {
643 _mutator_free_bitmap.clear();
644 _collector_free_bitmap.clear();
645 _mutator_leftmost = _max;
646 _mutator_rightmost = 0;
647 _collector_leftmost = _max;
648 _collector_rightmost = 0;
649 _capacity = 0;
650 _used = 0;
651 }
652
653 void ShenandoahFreeSet::rebuild() {
654 shenandoah_assert_heaplocked();
655 clear();
656
657 log_debug(gc)("Rebuilding FreeSet");
658 for (size_t idx = 0; idx < _heap->num_regions(); idx++) {
659 ShenandoahHeapRegion* region = _heap->get_region(idx);
660 if (region->is_alloc_allowed() || region->is_trash()) {
661 assert(!region->is_cset(), "Shouldn't be adding those to the free set");
662
663 // Do not add regions that would surely fail allocation
664 if (has_no_alloc_capacity(region)) continue;
665
666 _capacity += alloc_capacity(region);
667 assert(_used <= _capacity, "must not use more than we have");
668
669 assert(!is_mutator_free(idx), "We are about to add it, it shouldn't be there already");
670 _mutator_free_bitmap.set_bit(idx);
671
672 log_debug(gc)(" Setting Region " SIZE_FORMAT " _mutator_free_bitmap bit to true", idx);
673 }
674 }
675
676 // Evac reserve: reserve trailing space for evacuations
677 if (!_heap->mode()->is_generational()) {
678 size_t to_reserve = (_heap->max_capacity() / 100) * ShenandoahEvacReserve;
679 reserve_regions(to_reserve);
680 } else {
681 size_t young_reserve = (_heap->young_generation()->max_capacity() / 100) * ShenandoahEvacReserve;
682 // Note that all allocations performed from old-gen are performed by GC, generally using PLABs for both
683 // promotions and evacuations. The partition between which old memory is reserved for evacuation and
684 // which is reserved for promotion is enforced using thread-local variables that prescribe intentons within
685 // each PLAB. We do not reserve any of old-gen memory in order to facilitate the loaning of old-gen memory
686 // to young-gen purposes.
687 size_t old_reserve = 0;
688 size_t to_reserve = young_reserve + old_reserve;
689 reserve_regions(to_reserve);
690 }
691
692 recompute_bounds();
693 assert_bounds();
694 }
695
696 void ShenandoahFreeSet::reserve_regions(size_t to_reserve) {
697 size_t reserved = 0;
698
699 for (size_t idx = _heap->num_regions() - 1; idx > 0; idx--) {
700 if (reserved >= to_reserve) break;
701
702 ShenandoahHeapRegion* region = _heap->get_region(idx);
703 if (_mutator_free_bitmap.at(idx) && can_allocate_from(region)) {
704 _mutator_free_bitmap.clear_bit(idx);
705 _collector_free_bitmap.set_bit(idx);
706 size_t ac = alloc_capacity(region);
707 _capacity -= ac;
708 reserved += ac;
709 log_debug(gc)(" Shifting region " SIZE_FORMAT " from mutator_free to collector_free", idx);
710 }
711 }
712 }
713
714 void ShenandoahFreeSet::log_status() {
715 shenandoah_assert_heaplocked();
716
717 LogTarget(Info, gc, ergo) lt;
718 if (lt.is_enabled()) {
719 ResourceMark rm;
720 LogStream ls(lt);
721
722 {
723 size_t last_idx = 0;
724 size_t max = 0;
725 size_t max_contig = 0;
726 size_t empty_contig = 0;
727
728 size_t total_used = 0;
729 size_t total_free = 0;
730 size_t total_free_ext = 0;
731
732 for (size_t idx = _mutator_leftmost; idx <= _mutator_rightmost; idx++) {
733 if (is_mutator_free(idx)) {
734 ShenandoahHeapRegion *r = _heap->get_region(idx);
735 size_t free = alloc_capacity(r);
736
737 max = MAX2(max, free);
738
739 if (r->is_empty()) {
740 total_free_ext += free;
741 if (last_idx + 1 == idx) {
742 empty_contig++;
743 } else {
744 empty_contig = 1;
745 }
746 } else {
747 empty_contig = 0;
748 }
749
750 total_used += r->used();
751 total_free += free;
752
753 max_contig = MAX2(max_contig, empty_contig);
754 last_idx = idx;
755 }
756 }
757
758 size_t max_humongous = max_contig * ShenandoahHeapRegion::region_size_bytes();
759 size_t free = capacity() - used();
760
761 ls.print("Free: " SIZE_FORMAT "%s, Max: " SIZE_FORMAT "%s regular, " SIZE_FORMAT "%s humongous, ",
762 byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free),
763 byte_size_in_proper_unit(max), proper_unit_for_byte_size(max),
764 byte_size_in_proper_unit(max_humongous), proper_unit_for_byte_size(max_humongous)
765 );
766
767 ls.print("Frag: ");
768 size_t frag_ext;
769 if (total_free_ext > 0) {
770 frag_ext = 100 - (100 * max_humongous / total_free_ext);
771 } else {
772 frag_ext = 0;
773 }
774 ls.print(SIZE_FORMAT "%% external, ", frag_ext);
775
776 size_t frag_int;
777 if (mutator_count() > 0) {
778 frag_int = (100 * (total_used / mutator_count()) / ShenandoahHeapRegion::region_size_bytes());
779 } else {
780 frag_int = 0;
781 }
782 ls.print(SIZE_FORMAT "%% internal; ", frag_int);
783 }
784
785 {
786 size_t max = 0;
787 size_t total_free = 0;
788
789 for (size_t idx = _collector_leftmost; idx <= _collector_rightmost; idx++) {
790 if (is_collector_free(idx)) {
791 ShenandoahHeapRegion *r = _heap->get_region(idx);
792 size_t free = alloc_capacity(r);
793 max = MAX2(max, free);
794 total_free += free;
795 }
796 }
797
798 ls.print_cr("Reserve: " SIZE_FORMAT "%s, Max: " SIZE_FORMAT "%s",
799 byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free),
800 byte_size_in_proper_unit(max), proper_unit_for_byte_size(max));
801 }
802 }
803 }
804
805 HeapWord* ShenandoahFreeSet::allocate(ShenandoahAllocRequest& req, bool& in_new_region) {
806 shenandoah_assert_heaplocked();
807 assert_bounds();
808
809 // Allocation request is known to satisfy all memory budgeting constraints.
810 if (req.size() > ShenandoahHeapRegion::humongous_threshold_words()) {
811 switch (req.type()) {
812 case ShenandoahAllocRequest::_alloc_shared:
813 case ShenandoahAllocRequest::_alloc_shared_gc:
814 in_new_region = true;
815 return allocate_contiguous(req);
816 case ShenandoahAllocRequest::_alloc_plab:
817 case ShenandoahAllocRequest::_alloc_gclab:
818 case ShenandoahAllocRequest::_alloc_tlab:
819 in_new_region = false;
820 assert(false, "Trying to allocate TLAB larger than the humongous threshold: " SIZE_FORMAT " > " SIZE_FORMAT,
821 req.size(), ShenandoahHeapRegion::humongous_threshold_words());
822 return NULL;
823 default:
824 ShouldNotReachHere();
825 return NULL;
826 }
827 } else {
828 return allocate_single(req, in_new_region);
829 }
830 }
831
832 size_t ShenandoahFreeSet::unsafe_peek_free() const {
833 // Deliberately not locked, this method is unsafe when free set is modified.
834
835 for (size_t index = _mutator_leftmost; index <= _mutator_rightmost; index++) {
836 if (index < _max && is_mutator_free(index)) {
837 ShenandoahHeapRegion* r = _heap->get_region(index);
838 if (r->free() >= MinTLABSize) {
839 return r->free();
840 }
841 }
842 }
843
844 // It appears that no regions left
845 return 0;
846 }
847
848 void ShenandoahFreeSet::print_on(outputStream* out) const {
849 out->print_cr("Mutator Free Set: " SIZE_FORMAT "", mutator_count());
850 for (size_t index = _mutator_leftmost; index <= _mutator_rightmost; index++) {
851 if (is_mutator_free(index)) {
852 _heap->get_region(index)->print_on(out);
853 }
854 }
855 out->print_cr("Collector Free Set: " SIZE_FORMAT "", collector_count());
856 for (size_t index = _collector_leftmost; index <= _collector_rightmost; index++) {
857 if (is_collector_free(index)) {
858 _heap->get_region(index)->print_on(out);
859 }
860 }
861 }
862
863 /*
864 * Internal fragmentation metric: describes how fragmented the heap regions are.
865 *
866 * It is derived as:
867 *
868 * sum(used[i]^2, i=0..k)
869 * IF = 1 - ------------------------------
870 * C * sum(used[i], i=0..k)
871 *
872 * ...where k is the number of regions in computation, C is the region capacity, and
873 * used[i] is the used space in the region.
874 *
875 * The non-linearity causes IF to be lower for the cases where the same total heap
876 * used is densely packed. For example:
877 * a) Heap is completely full => IF = 0
878 * b) Heap is half full, first 50% regions are completely full => IF = 0
879 * c) Heap is half full, each region is 50% full => IF = 1/2
880 * d) Heap is quarter full, first 50% regions are completely full => IF = 0
881 * e) Heap is quarter full, each region is 25% full => IF = 3/4
882 * f) Heap has one small object per each region => IF =~ 1
883 */
884 double ShenandoahFreeSet::internal_fragmentation() {
885 double squared = 0;
886 double linear = 0;
887 int count = 0;
888
889 for (size_t index = _mutator_leftmost; index <= _mutator_rightmost; index++) {
890 if (is_mutator_free(index)) {
891 ShenandoahHeapRegion* r = _heap->get_region(index);
892 size_t used = r->used();
893 squared += used * used;
894 linear += used;
895 count++;
896 }
897 }
898
899 if (count > 0) {
900 double s = squared / (ShenandoahHeapRegion::region_size_bytes() * linear);
901 return 1 - s;
902 } else {
903 return 0;
904 }
905 }
906
907 /*
908 * External fragmentation metric: describes how fragmented the heap is.
909 *
910 * It is derived as:
911 *
912 * EF = 1 - largest_contiguous_free / total_free
913 *
914 * For example:
915 * a) Heap is completely empty => EF = 0
916 * b) Heap is completely full => EF = 0
917 * c) Heap is first-half full => EF = 1/2
918 * d) Heap is half full, full and empty regions interleave => EF =~ 1
919 */
920 double ShenandoahFreeSet::external_fragmentation() {
921 size_t last_idx = 0;
922 size_t max_contig = 0;
923 size_t empty_contig = 0;
924
925 size_t free = 0;
926
927 for (size_t index = _mutator_leftmost; index <= _mutator_rightmost; index++) {
928 if (is_mutator_free(index)) {
929 ShenandoahHeapRegion* r = _heap->get_region(index);
930 if (r->is_empty()) {
931 free += ShenandoahHeapRegion::region_size_bytes();
932 if (last_idx + 1 == index) {
933 empty_contig++;
934 } else {
935 empty_contig = 1;
936 }
937 } else {
938 empty_contig = 0;
939 }
940
941 max_contig = MAX2(max_contig, empty_contig);
942 last_idx = index;
943 }
944 }
945
946 if (free > 0) {
947 return 1 - (1.0 * max_contig * ShenandoahHeapRegion::region_size_bytes() / free);
948 } else {
949 return 0;
950 }
951 }
952
953 #ifdef ASSERT
954 void ShenandoahFreeSet::assert_bounds() const {
955 // Performance invariants. Failing these would not break the free set, but performance
956 // would suffer.
957 assert (_mutator_leftmost <= _max, "leftmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, _mutator_leftmost, _max);
958 assert (_mutator_rightmost < _max, "rightmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, _mutator_rightmost, _max);
959
960 assert (_mutator_leftmost == _max || is_mutator_free(_mutator_leftmost), "leftmost region should be free: " SIZE_FORMAT, _mutator_leftmost);
961 assert (_mutator_rightmost == 0 || is_mutator_free(_mutator_rightmost), "rightmost region should be free: " SIZE_FORMAT, _mutator_rightmost);
962
963 size_t beg_off = _mutator_free_bitmap.get_next_one_offset(0);
964 size_t end_off = _mutator_free_bitmap.get_next_one_offset(_mutator_rightmost + 1);
965 assert (beg_off >= _mutator_leftmost, "free regions before the leftmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, beg_off, _mutator_leftmost);
966 assert (end_off == _max, "free regions past the rightmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, end_off, _mutator_rightmost);
967
968 assert (_collector_leftmost <= _max, "leftmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, _collector_leftmost, _max);
969 assert (_collector_rightmost < _max, "rightmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, _collector_rightmost, _max);
970
971 assert (_collector_leftmost == _max || is_collector_free(_collector_leftmost), "leftmost region should be free: " SIZE_FORMAT, _collector_leftmost);
972 assert (_collector_rightmost == 0 || is_collector_free(_collector_rightmost), "rightmost region should be free: " SIZE_FORMAT, _collector_rightmost);
973
974 beg_off = _collector_free_bitmap.get_next_one_offset(0);
975 end_off = _collector_free_bitmap.get_next_one_offset(_collector_rightmost + 1);
976 assert (beg_off >= _collector_leftmost, "free regions before the leftmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, beg_off, _collector_leftmost);
977 assert (end_off == _max, "free regions past the rightmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, end_off, _collector_rightmost);
978 }
979 #endif