Bug Summary

File:jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp
Warning:line 491, column 14
Value stored to 'free' during its initialization is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name shenandoahFreeSet.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -mthread-model posix -fno-delete-null-pointer-checks -mframe-pointer=all -relaxed-aliasing -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -I /home/daniel/Projects/java/jdk/build/linux-x86_64-server-fastdebug/hotspot/variant-server/libjvm/objs/precompiled -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D _GNU_SOURCE -D _REENTRANT -D LIBC=gnu -D LINUX -D VM_LITTLE_ENDIAN -D _LP64=1 -D ASSERT -D CHECK_UNHANDLED_OOPS -D TARGET_ARCH_x86 -D INCLUDE_SUFFIX_OS=_linux -D INCLUDE_SUFFIX_CPU=_x86 -D INCLUDE_SUFFIX_COMPILER=_gcc -D TARGET_COMPILER_gcc -D AMD64 -D HOTSPOT_LIB_ARCH="amd64" -D COMPILER1 -D COMPILER2 -I /home/daniel/Projects/java/jdk/build/linux-x86_64-server-fastdebug/hotspot/variant-server/gensrc/adfiles -I /home/daniel/Projects/java/jdk/src/hotspot/share -I /home/daniel/Projects/java/jdk/src/hotspot/os/linux -I /home/daniel/Projects/java/jdk/src/hotspot/os/posix -I /home/daniel/Projects/java/jdk/src/hotspot/cpu/x86 -I /home/daniel/Projects/java/jdk/src/hotspot/os_cpu/linux_x86 -I /home/daniel/Projects/java/jdk/build/linux-x86_64-server-fastdebug/hotspot/variant-server/gensrc -I /home/daniel/Projects/java/jdk/src/hotspot/share/precompiled -I /home/daniel/Projects/java/jdk/src/hotspot/share/include -I /home/daniel/Projects/java/jdk/src/hotspot/os/posix/include -I /home/daniel/Projects/java/jdk/build/linux-x86_64-server-fastdebug/support/modules_include/java.base -I /home/daniel/Projects/java/jdk/build/linux-x86_64-server-fastdebug/support/modules_include/java.base/linux -I /home/daniel/Projects/java/jdk/src/java.base/share/native/libjimage -I /home/daniel/Projects/java/jdk/build/linux-x86_64-server-fastdebug/hotspot/variant-server/gensrc/adfiles -I /home/daniel/Projects/java/jdk/src/hotspot/share -I /home/daniel/Projects/java/jdk/src/hotspot/os/linux -I /home/daniel/Projects/java/jdk/src/hotspot/os/posix -I /home/daniel/Projects/java/jdk/src/hotspot/cpu/x86 -I /home/daniel/Projects/java/jdk/src/hotspot/os_cpu/linux_x86 -I /home/daniel/Projects/java/jdk/build/linux-x86_64-server-fastdebug/hotspot/variant-server/gensrc -D _FORTIFY_SOURCE=2 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/x86_64-linux-gnu/c++/7.5.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/x86_64-linux-gnu/c++/7.5.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -Wno-format-zero-length -Wno-unused-parameter -Wno-unused -Wno-parentheses -Wno-comment -Wno-unknown-pragmas -Wno-address -Wno-delete-non-virtual-dtor -Wno-char-subscripts -Wno-array-bounds -Wno-int-in-bool-context -Wno-ignored-qualifiers -Wno-missing-field-initializers -Wno-implicit-fallthrough -Wno-empty-body -Wno-strict-overflow -Wno-sequence-point -Wno-maybe-uninitialized -Wno-misleading-indentation -Wno-cast-function-type -Wno-shift-negative-value -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /home/daniel/Projects/java/jdk/make/hotspot -ferror-limit 19 -fmessage-length 0 -fvisibility hidden -stack-protector 1 -fno-rtti -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -o /home/daniel/Projects/java/scan/2021-12-21-193737-8510-1 -x c++ /home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp
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/shenandoahFreeSet.hpp"
28#include "gc/shenandoah/shenandoahHeap.inline.hpp"
29#include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
30#include "gc/shenandoah/shenandoahMarkingContext.inline.hpp"
31#include "logging/logStream.hpp"
32#include "memory/resourceArea.hpp"
33#include "runtime/orderAccess.hpp"
34
35ShenandoahFreeSet::ShenandoahFreeSet(ShenandoahHeap* heap, size_t max_regions) :
36 _heap(heap),
37 _mutator_free_bitmap(max_regions, mtGC),
38 _collector_free_bitmap(max_regions, mtGC),
39 _max(max_regions)
40{
41 clear_internal();
42}
43
44void ShenandoahFreeSet::increase_used(size_t num_bytes) {
45 shenandoah_assert_heaplocked()ShenandoahAsserts::assert_heaplocked("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 45)
;
46 _used += num_bytes;
47
48 assert(_used <= _capacity, "must not use more than we have: used: " SIZE_FORMATdo { if (!(_used <= _capacity)) { (*g_assert_poison) = 'X'
;; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 49, "assert(" "_used <= _capacity" ") failed", "must not use more than we have: used: "
"%" "l" "u" ", capacity: " "%" "l" "u" ", num_bytes: " "%" "l"
"u", _used, _capacity, num_bytes); ::breakpoint(); } } while
(0)
49 ", capacity: " SIZE_FORMAT ", num_bytes: " SIZE_FORMAT, _used, _capacity, num_bytes)do { if (!(_used <= _capacity)) { (*g_assert_poison) = 'X'
;; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 49, "assert(" "_used <= _capacity" ") failed", "must not use more than we have: used: "
"%" "l" "u" ", capacity: " "%" "l" "u" ", num_bytes: " "%" "l"
"u", _used, _capacity, num_bytes); ::breakpoint(); } } while
(0)
;
50}
51
52bool ShenandoahFreeSet::is_mutator_free(size_t idx) const {
53 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT " (left: " SIZE_FORMAT ", right: " SIZE_FORMAT ")",do { if (!(idx < _max)) { (*g_assert_poison) = 'X';; report_vm_error
("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 54, "assert(" "idx < _max" ") failed", "index is sane: "
"%" "l" "u" " < " "%" "l" "u" " (left: " "%" "l" "u" ", right: "
"%" "l" "u" ")", idx, _max, _mutator_leftmost, _mutator_rightmost
); ::breakpoint(); } } while (0)
54 idx, _max, _mutator_leftmost, _mutator_rightmost)do { if (!(idx < _max)) { (*g_assert_poison) = 'X';; report_vm_error
("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 54, "assert(" "idx < _max" ") failed", "index is sane: "
"%" "l" "u" " < " "%" "l" "u" " (left: " "%" "l" "u" ", right: "
"%" "l" "u" ")", idx, _max, _mutator_leftmost, _mutator_rightmost
); ::breakpoint(); } } while (0)
;
55 return _mutator_free_bitmap.at(idx);
56}
57
58bool ShenandoahFreeSet::is_collector_free(size_t idx) const {
59 assert (idx < _max, "index is sane: " SIZE_FORMAT " < " SIZE_FORMAT " (left: " SIZE_FORMAT ", right: " SIZE_FORMAT ")",do { if (!(idx < _max)) { (*g_assert_poison) = 'X';; report_vm_error
("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 60, "assert(" "idx < _max" ") failed", "index is sane: "
"%" "l" "u" " < " "%" "l" "u" " (left: " "%" "l" "u" ", right: "
"%" "l" "u" ")", idx, _max, _collector_leftmost, _collector_rightmost
); ::breakpoint(); } } while (0)
60 idx, _max, _collector_leftmost, _collector_rightmost)do { if (!(idx < _max)) { (*g_assert_poison) = 'X';; report_vm_error
("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 60, "assert(" "idx < _max" ") failed", "index is sane: "
"%" "l" "u" " < " "%" "l" "u" " (left: " "%" "l" "u" ", right: "
"%" "l" "u" ")", idx, _max, _collector_leftmost, _collector_rightmost
); ::breakpoint(); } } while (0)
;
61 return _collector_free_bitmap.at(idx);
62}
63
64HeapWord* ShenandoahFreeSet::allocate_single(ShenandoahAllocRequest& req, bool& in_new_region) {
65 // Scan the bitmap looking for a first fit.
66 //
67 // Leftmost and rightmost bounds provide enough caching to walk bitmap efficiently. Normally,
68 // we would find the region to allocate at right away.
69 //
70 // Allocations are biased: new application allocs go to beginning of the heap, and GC allocs
71 // go to the end. This makes application allocation faster, because we would clear lots
72 // of regions from the beginning most of the time.
73 //
74 // Free set maintains mutator and collector views, and normally they allocate in their views only,
75 // unless we special cases for stealing and mixed allocations.
76
77 switch (req.type()) {
78 case ShenandoahAllocRequest::_alloc_tlab:
79 case ShenandoahAllocRequest::_alloc_shared: {
80
81 // Try to allocate in the mutator view
82 for (size_t idx = _mutator_leftmost; idx <= _mutator_rightmost; idx++) {
83 if (is_mutator_free(idx)) {
84 HeapWord* result = try_allocate_in(_heap->get_region(idx), req, in_new_region);
85 if (result != NULL__null) {
86 return result;
87 }
88 }
89 }
90
91 // There is no recovery. Mutator does not touch collector view at all.
92 break;
93 }
94 case ShenandoahAllocRequest::_alloc_gclab:
95 case ShenandoahAllocRequest::_alloc_shared_gc: {
96 // size_t is unsigned, need to dodge underflow when _leftmost = 0
97
98 // Fast-path: try to allocate in the collector view first
99 for (size_t c = _collector_rightmost + 1; c > _collector_leftmost; c--) {
100 size_t idx = c - 1;
101 if (is_collector_free(idx)) {
102 HeapWord* result = try_allocate_in(_heap->get_region(idx), req, in_new_region);
103 if (result != NULL__null) {
104 return result;
105 }
106 }
107 }
108
109 // No dice. Can we borrow space from mutator view?
110 if (!ShenandoahEvacReserveOverflow) {
111 return NULL__null;
112 }
113
114 // Try to steal the empty region from the mutator view
115 for (size_t c = _mutator_rightmost + 1; c > _mutator_leftmost; c--) {
116 size_t idx = c - 1;
117 if (is_mutator_free(idx)) {
118 ShenandoahHeapRegion* r = _heap->get_region(idx);
119 if (can_allocate_from(r)) {
120 flip_to_gc(r);
121 HeapWord *result = try_allocate_in(r, req, in_new_region);
122 if (result != NULL__null) {
123 return result;
124 }
125 }
126 }
127 }
128
129 // No dice. Do not try to mix mutator and GC allocations, because
130 // URWM moves due to GC allocations would expose unparsable mutator
131 // allocations.
132
133 break;
134 }
135 default:
136 ShouldNotReachHere()do { (*g_assert_poison) = 'X';; report_should_not_reach_here(
"/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 136); ::breakpoint(); } while (0)
;
137 }
138
139 return NULL__null;
140}
141
142HeapWord* ShenandoahFreeSet::try_allocate_in(ShenandoahHeapRegion* r, ShenandoahAllocRequest& req, bool& in_new_region) {
143 assert (!has_no_alloc_capacity(r), "Performance: should avoid full regions on this path: " SIZE_FORMAT, r->index())do { if (!(!has_no_alloc_capacity(r))) { (*g_assert_poison) =
'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 143, "assert(" "!has_no_alloc_capacity(r)" ") failed", "Performance: should avoid full regions on this path: "
"%" "l" "u", r->index()); ::breakpoint(); } } while (0)
;
144
145 if (_heap->is_concurrent_weak_root_in_progress() &&
146 r->is_trash()) {
147 return NULL__null;
148 }
149
150 try_recycle_trashed(r);
151
152 in_new_region = r->is_empty();
153
154 HeapWord* result = NULL__null;
155 size_t size = req.size();
156
157 if (ShenandoahElasticTLAB && req.is_lab_alloc()) {
158 size_t free = align_down(r->free() >> LogHeapWordSize, MinObjAlignment);
159 if (size > free) {
160 size = free;
161 }
162 if (size >= req.min_size()) {
163 result = r->allocate(size, req.type());
164 assert (result != NULL, "Allocation must succeed: free " SIZE_FORMAT ", actual " SIZE_FORMAT, free, size)do { if (!(result != __null)) { (*g_assert_poison) = 'X';; report_vm_error
("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 164, "assert(" "result != __null" ") failed", "Allocation must succeed: free "
"%" "l" "u" ", actual " "%" "l" "u", free, size); ::breakpoint
(); } } while (0)
;
165 }
166 } else {
167 result = r->allocate(size, req.type());
168 }
169
170 if (result != NULL__null) {
171 // Allocation successful, bump stats:
172 if (req.is_mutator_alloc()) {
173 increase_used(size * HeapWordSize);
174 }
175
176 // Record actual allocation size
177 req.set_actual_size(size);
178
179 if (req.is_gc_alloc()) {
180 r->set_update_watermark(r->top());
181 }
182 }
183
184 if (result == NULL__null || has_no_alloc_capacity(r)) {
185 // Region cannot afford this or future allocations. Retire it.
186 //
187 // While this seems a bit harsh, especially in the case when this large allocation does not
188 // fit, but the next small one would, we are risking to inflate scan times when lots of
189 // almost-full regions precede the fully-empty region where we want allocate the entire TLAB.
190 // TODO: Record first fully-empty region, and use that for large allocations
191
192 // Record the remainder as allocation waste
193 if (req.is_mutator_alloc()) {
194 size_t waste = r->free();
195 if (waste > 0) {
196 increase_used(waste);
197 _heap->notify_mutator_alloc_words(waste >> LogHeapWordSize, true);
198 }
199 }
200
201 size_t num = r->index();
202 _collector_free_bitmap.clear_bit(num);
203 _mutator_free_bitmap.clear_bit(num);
204 // Touched the bounds? Need to update:
205 if (touches_bounds(num)) {
206 adjust_bounds();
207 }
208 assert_bounds();
209 }
210 return result;
211}
212
213bool ShenandoahFreeSet::touches_bounds(size_t num) const {
214 return num == _collector_leftmost || num == _collector_rightmost || num == _mutator_leftmost || num == _mutator_rightmost;
215}
216
217void ShenandoahFreeSet::recompute_bounds() {
218 // Reset to the most pessimistic case:
219 _mutator_rightmost = _max - 1;
220 _mutator_leftmost = 0;
221 _collector_rightmost = _max - 1;
222 _collector_leftmost = 0;
223
224 // ...and adjust from there
225 adjust_bounds();
226}
227
228void ShenandoahFreeSet::adjust_bounds() {
229 // Rewind both mutator bounds until the next bit.
230 while (_mutator_leftmost < _max && !is_mutator_free(_mutator_leftmost)) {
231 _mutator_leftmost++;
232 }
233 while (_mutator_rightmost > 0 && !is_mutator_free(_mutator_rightmost)) {
234 _mutator_rightmost--;
235 }
236 // Rewind both collector bounds until the next bit.
237 while (_collector_leftmost < _max && !is_collector_free(_collector_leftmost)) {
238 _collector_leftmost++;
239 }
240 while (_collector_rightmost > 0 && !is_collector_free(_collector_rightmost)) {
241 _collector_rightmost--;
242 }
243}
244
245HeapWord* ShenandoahFreeSet::allocate_contiguous(ShenandoahAllocRequest& req) {
246 shenandoah_assert_heaplocked()ShenandoahAsserts::assert_heaplocked("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 246)
;
247
248 size_t words_size = req.size();
249 size_t num = ShenandoahHeapRegion::required_regions(words_size * HeapWordSize);
250
251 // No regions left to satisfy allocation, bye.
252 if (num > mutator_count()) {
253 return NULL__null;
254 }
255
256 // Find the continuous interval of $num regions, starting from $beg and ending in $end,
257 // inclusive. Contiguous allocations are biased to the beginning.
258
259 size_t beg = _mutator_leftmost;
260 size_t end = beg;
261
262 while (true) {
263 if (end >= _max) {
264 // Hit the end, goodbye
265 return NULL__null;
266 }
267
268 // If regions are not adjacent, then current [beg; end] is useless, and we may fast-forward.
269 // If region is not completely free, the current [beg; end] is useless, and we may fast-forward.
270 if (!is_mutator_free(end) || !can_allocate_from(_heap->get_region(end))) {
271 end++;
272 beg = end;
273 continue;
274 }
275
276 if ((end - beg + 1) == num) {
277 // found the match
278 break;
279 }
280
281 end++;
282 };
283
284 size_t remainder = words_size & ShenandoahHeapRegion::region_size_words_mask();
285
286 // Initialize regions:
287 for (size_t i = beg; i <= end; i++) {
288 ShenandoahHeapRegion* r = _heap->get_region(i);
289 try_recycle_trashed(r);
290
291 assert(i == beg || _heap->get_region(i - 1)->index() + 1 == r->index(), "Should be contiguous")do { if (!(i == beg || _heap->get_region(i - 1)->index(
) + 1 == r->index())) { (*g_assert_poison) = 'X';; report_vm_error
("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 291, "assert(" "i == beg || _heap->get_region(i - 1)->index() + 1 == r->index()"
") failed", "Should be contiguous"); ::breakpoint(); } } while
(0)
;
292 assert(r->is_empty(), "Should be empty")do { if (!(r->is_empty())) { (*g_assert_poison) = 'X';; report_vm_error
("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 292, "assert(" "r->is_empty()" ") failed", "Should be empty"
); ::breakpoint(); } } while (0)
;
293
294 if (i == beg) {
295 r->make_humongous_start();
296 } else {
297 r->make_humongous_cont();
298 }
299
300 // Trailing region may be non-full, record the remainder there
301 size_t used_words;
302 if ((i == end) && (remainder != 0)) {
303 used_words = remainder;
304 } else {
305 used_words = ShenandoahHeapRegion::region_size_words();
306 }
307
308 r->set_top(r->bottom() + used_words);
309
310 _mutator_free_bitmap.clear_bit(r->index());
311 }
312
313 // While individual regions report their true use, all humongous regions are
314 // marked used in the free set.
315 increase_used(ShenandoahHeapRegion::region_size_bytes() * num);
316
317 if (remainder != 0) {
318 // Record this remainder as allocation waste
319 _heap->notify_mutator_alloc_words(ShenandoahHeapRegion::region_size_words() - remainder, true);
320 }
321
322 // Allocated at left/rightmost? Move the bounds appropriately.
323 if (beg == _mutator_leftmost || end == _mutator_rightmost) {
324 adjust_bounds();
325 }
326 assert_bounds();
327
328 req.set_actual_size(words_size);
329 return _heap->get_region(beg)->bottom();
330}
331
332bool ShenandoahFreeSet::can_allocate_from(ShenandoahHeapRegion *r) {
333 return r->is_empty() || (r->is_trash() && !_heap->is_concurrent_weak_root_in_progress());
334}
335
336size_t ShenandoahFreeSet::alloc_capacity(ShenandoahHeapRegion *r) {
337 if (r->is_trash()) {
338 // This would be recycled on allocation path
339 return ShenandoahHeapRegion::region_size_bytes();
340 } else {
341 return r->free();
342 }
343}
344
345bool ShenandoahFreeSet::has_no_alloc_capacity(ShenandoahHeapRegion *r) {
346 return alloc_capacity(r) == 0;
347}
348
349void ShenandoahFreeSet::try_recycle_trashed(ShenandoahHeapRegion *r) {
350 if (r->is_trash()) {
351 _heap->decrease_used(r->used());
352 r->recycle();
353 }
354}
355
356void ShenandoahFreeSet::recycle_trash() {
357 // lock is not reentrable, check we don't have it
358 shenandoah_assert_not_heaplocked()ShenandoahAsserts::assert_not_heaplocked("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 358)
;
359
360 for (size_t i = 0; i < _heap->num_regions(); i++) {
361 ShenandoahHeapRegion* r = _heap->get_region(i);
362 if (r->is_trash()) {
363 ShenandoahHeapLocker locker(_heap->lock());
364 try_recycle_trashed(r);
365 }
366 SpinPause(); // allow allocators to take the lock
367 }
368}
369
370void ShenandoahFreeSet::flip_to_gc(ShenandoahHeapRegion* r) {
371 size_t idx = r->index();
372
373 assert(_mutator_free_bitmap.at(idx), "Should be in mutator view")do { if (!(_mutator_free_bitmap.at(idx))) { (*g_assert_poison
) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 373, "assert(" "_mutator_free_bitmap.at(idx)" ") failed", "Should be in mutator view"
); ::breakpoint(); } } while (0)
;
374 assert(can_allocate_from(r), "Should not be allocated")do { if (!(can_allocate_from(r))) { (*g_assert_poison) = 'X';
; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 374, "assert(" "can_allocate_from(r)" ") failed", "Should not be allocated"
); ::breakpoint(); } } while (0)
;
375
376 _mutator_free_bitmap.clear_bit(idx);
377 _collector_free_bitmap.set_bit(idx);
378 _collector_leftmost = MIN2(idx, _collector_leftmost);
379 _collector_rightmost = MAX2(idx, _collector_rightmost);
380
381 _capacity -= alloc_capacity(r);
382
383 if (touches_bounds(idx)) {
384 adjust_bounds();
385 }
386 assert_bounds();
387}
388
389void ShenandoahFreeSet::clear() {
390 shenandoah_assert_heaplocked()ShenandoahAsserts::assert_heaplocked("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 390)
;
391 clear_internal();
392}
393
394void ShenandoahFreeSet::clear_internal() {
395 _mutator_free_bitmap.clear();
396 _collector_free_bitmap.clear();
397 _mutator_leftmost = _max;
398 _mutator_rightmost = 0;
399 _collector_leftmost = _max;
400 _collector_rightmost = 0;
401 _capacity = 0;
402 _used = 0;
403}
404
405void ShenandoahFreeSet::rebuild() {
406 shenandoah_assert_heaplocked()ShenandoahAsserts::assert_heaplocked("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 406)
;
407 clear();
408
409 for (size_t idx = 0; idx < _heap->num_regions(); idx++) {
410 ShenandoahHeapRegion* region = _heap->get_region(idx);
411 if (region->is_alloc_allowed() || region->is_trash()) {
412 assert(!region->is_cset(), "Shouldn't be adding those to the free set")do { if (!(!region->is_cset())) { (*g_assert_poison) = 'X'
;; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 412, "assert(" "!region->is_cset()" ") failed", "Shouldn't be adding those to the free set"
); ::breakpoint(); } } while (0)
;
413
414 // Do not add regions that would surely fail allocation
415 if (has_no_alloc_capacity(region)) continue;
416
417 _capacity += alloc_capacity(region);
418 assert(_used <= _capacity, "must not use more than we have")do { if (!(_used <= _capacity)) { (*g_assert_poison) = 'X'
;; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 418, "assert(" "_used <= _capacity" ") failed", "must not use more than we have"
); ::breakpoint(); } } while (0)
;
419
420 assert(!is_mutator_free(idx), "We are about to add it, it shouldn't be there already")do { if (!(!is_mutator_free(idx))) { (*g_assert_poison) = 'X'
;; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 420, "assert(" "!is_mutator_free(idx)" ") failed", "We are about to add it, it shouldn't be there already"
); ::breakpoint(); } } while (0)
;
421 _mutator_free_bitmap.set_bit(idx);
422 }
423 }
424
425 // Evac reserve: reserve trailing space for evacuations
426 size_t to_reserve = _heap->max_capacity() / 100 * ShenandoahEvacReserve;
427 size_t reserved = 0;
428
429 for (size_t idx = _heap->num_regions() - 1; idx > 0; idx--) {
430 if (reserved >= to_reserve) break;
431
432 ShenandoahHeapRegion* region = _heap->get_region(idx);
433 if (_mutator_free_bitmap.at(idx) && can_allocate_from(region)) {
434 _mutator_free_bitmap.clear_bit(idx);
435 _collector_free_bitmap.set_bit(idx);
436 size_t ac = alloc_capacity(region);
437 _capacity -= ac;
438 reserved += ac;
439 }
440 }
441
442 recompute_bounds();
443 assert_bounds();
444}
445
446void ShenandoahFreeSet::log_status() {
447 shenandoah_assert_heaplocked()ShenandoahAsserts::assert_heaplocked("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 447)
;
448
449 LogTarget(Info, gc, ergo)LogTargetImpl<LogLevel::Info, (LogTag::_gc), (LogTag::_ergo
), (LogTag::__NO_TAG), (LogTag::__NO_TAG), (LogTag::__NO_TAG)
, (LogTag::__NO_TAG)>
lt;
450 if (lt.is_enabled()) {
451 ResourceMark rm;
452 LogStream ls(lt);
453
454 {
455 size_t last_idx = 0;
456 size_t max = 0;
457 size_t max_contig = 0;
458 size_t empty_contig = 0;
459
460 size_t total_used = 0;
461 size_t total_free = 0;
462 size_t total_free_ext = 0;
463
464 for (size_t idx = _mutator_leftmost; idx <= _mutator_rightmost; idx++) {
465 if (is_mutator_free(idx)) {
466 ShenandoahHeapRegion *r = _heap->get_region(idx);
467 size_t free = alloc_capacity(r);
468
469 max = MAX2(max, free);
470
471 if (r->is_empty()) {
472 total_free_ext += free;
473 if (last_idx + 1 == idx) {
474 empty_contig++;
475 } else {
476 empty_contig = 1;
477 }
478 } else {
479 empty_contig = 0;
480 }
481
482 total_used += r->used();
483 total_free += free;
484
485 max_contig = MAX2(max_contig, empty_contig);
486 last_idx = idx;
487 }
488 }
489
490 size_t max_humongous = max_contig * ShenandoahHeapRegion::region_size_bytes();
491 size_t free = capacity() - used();
Value stored to 'free' during its initialization is never read
492
493 ls.print("Free: " SIZE_FORMAT"%" "l" "u" "%s, Max: " SIZE_FORMAT"%" "l" "u" "%s regular, " SIZE_FORMAT"%" "l" "u" "%s humongous, ",
494 byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free),
495 byte_size_in_proper_unit(max), proper_unit_for_byte_size(max),
496 byte_size_in_proper_unit(max_humongous), proper_unit_for_byte_size(max_humongous)
497 );
498
499 ls.print("Frag: ");
500 size_t frag_ext;
501 if (total_free_ext > 0) {
502 frag_ext = 100 - (100 * max_humongous / total_free_ext);
503 } else {
504 frag_ext = 0;
505 }
506 ls.print(SIZE_FORMAT"%" "l" "u" "%% external, ", frag_ext);
507
508 size_t frag_int;
509 if (mutator_count() > 0) {
510 frag_int = (100 * (total_used / mutator_count()) / ShenandoahHeapRegion::region_size_bytes());
511 } else {
512 frag_int = 0;
513 }
514 ls.print(SIZE_FORMAT"%" "l" "u" "%% internal; ", frag_int);
515 }
516
517 {
518 size_t max = 0;
519 size_t total_free = 0;
520
521 for (size_t idx = _collector_leftmost; idx <= _collector_rightmost; idx++) {
522 if (is_collector_free(idx)) {
523 ShenandoahHeapRegion *r = _heap->get_region(idx);
524 size_t free = alloc_capacity(r);
525 max = MAX2(max, free);
526 total_free += free;
527 }
528 }
529
530 ls.print_cr("Reserve: " SIZE_FORMAT"%" "l" "u" "%s, Max: " SIZE_FORMAT"%" "l" "u" "%s",
531 byte_size_in_proper_unit(total_free), proper_unit_for_byte_size(total_free),
532 byte_size_in_proper_unit(max), proper_unit_for_byte_size(max));
533 }
534 }
535}
536
537HeapWord* ShenandoahFreeSet::allocate(ShenandoahAllocRequest& req, bool& in_new_region) {
538 shenandoah_assert_heaplocked()ShenandoahAsserts::assert_heaplocked("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 538)
;
539 assert_bounds();
540
541 if (req.size() > ShenandoahHeapRegion::humongous_threshold_words()) {
542 switch (req.type()) {
543 case ShenandoahAllocRequest::_alloc_shared:
544 case ShenandoahAllocRequest::_alloc_shared_gc:
545 in_new_region = true;
546 return allocate_contiguous(req);
547 case ShenandoahAllocRequest::_alloc_gclab:
548 case ShenandoahAllocRequest::_alloc_tlab:
549 in_new_region = false;
550 assert(false, "Trying to allocate TLAB larger than the humongous threshold: " SIZE_FORMAT " > " SIZE_FORMAT,do { if (!(false)) { (*g_assert_poison) = 'X';; report_vm_error
("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 551, "assert(" "false" ") failed", "Trying to allocate TLAB larger than the humongous threshold: "
"%" "l" "u" " > " "%" "l" "u", req.size(), ShenandoahHeapRegion
::humongous_threshold_words()); ::breakpoint(); } } while (0)
551 req.size(), ShenandoahHeapRegion::humongous_threshold_words())do { if (!(false)) { (*g_assert_poison) = 'X';; report_vm_error
("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 551, "assert(" "false" ") failed", "Trying to allocate TLAB larger than the humongous threshold: "
"%" "l" "u" " > " "%" "l" "u", req.size(), ShenandoahHeapRegion
::humongous_threshold_words()); ::breakpoint(); } } while (0)
;
552 return NULL__null;
553 default:
554 ShouldNotReachHere()do { (*g_assert_poison) = 'X';; report_should_not_reach_here(
"/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 554); ::breakpoint(); } while (0)
;
555 return NULL__null;
556 }
557 } else {
558 return allocate_single(req, in_new_region);
559 }
560}
561
562size_t ShenandoahFreeSet::unsafe_peek_free() const {
563 // Deliberately not locked, this method is unsafe when free set is modified.
564
565 for (size_t index = _mutator_leftmost; index <= _mutator_rightmost; index++) {
566 if (index < _max && is_mutator_free(index)) {
567 ShenandoahHeapRegion* r = _heap->get_region(index);
568 if (r->free() >= MinTLABSize) {
569 return r->free();
570 }
571 }
572 }
573
574 // It appears that no regions left
575 return 0;
576}
577
578void ShenandoahFreeSet::print_on(outputStream* out) const {
579 out->print_cr("Mutator Free Set: " SIZE_FORMAT"%" "l" "u" "", mutator_count());
580 for (size_t index = _mutator_leftmost; index <= _mutator_rightmost; index++) {
581 if (is_mutator_free(index)) {
582 _heap->get_region(index)->print_on(out);
583 }
584 }
585 out->print_cr("Collector Free Set: " SIZE_FORMAT"%" "l" "u" "", collector_count());
586 for (size_t index = _collector_leftmost; index <= _collector_rightmost; index++) {
587 if (is_collector_free(index)) {
588 _heap->get_region(index)->print_on(out);
589 }
590 }
591}
592
593/*
594 * Internal fragmentation metric: describes how fragmented the heap regions are.
595 *
596 * It is derived as:
597 *
598 * sum(used[i]^2, i=0..k)
599 * IF = 1 - ------------------------------
600 * C * sum(used[i], i=0..k)
601 *
602 * ...where k is the number of regions in computation, C is the region capacity, and
603 * used[i] is the used space in the region.
604 *
605 * The non-linearity causes IF to be lower for the cases where the same total heap
606 * used is densely packed. For example:
607 * a) Heap is completely full => IF = 0
608 * b) Heap is half full, first 50% regions are completely full => IF = 0
609 * c) Heap is half full, each region is 50% full => IF = 1/2
610 * d) Heap is quarter full, first 50% regions are completely full => IF = 0
611 * e) Heap is quarter full, each region is 25% full => IF = 3/4
612 * f) Heap has one small object per each region => IF =~ 1
613 */
614double ShenandoahFreeSet::internal_fragmentation() {
615 double squared = 0;
616 double linear = 0;
617 int count = 0;
618
619 for (size_t index = _mutator_leftmost; index <= _mutator_rightmost; index++) {
620 if (is_mutator_free(index)) {
621 ShenandoahHeapRegion* r = _heap->get_region(index);
622 size_t used = r->used();
623 squared += used * used;
624 linear += used;
625 count++;
626 }
627 }
628
629 if (count > 0) {
630 double s = squared / (ShenandoahHeapRegion::region_size_bytes() * linear);
631 return 1 - s;
632 } else {
633 return 0;
634 }
635}
636
637/*
638 * External fragmentation metric: describes how fragmented the heap is.
639 *
640 * It is derived as:
641 *
642 * EF = 1 - largest_contiguous_free / total_free
643 *
644 * For example:
645 * a) Heap is completely empty => EF = 0
646 * b) Heap is completely full => EF = 0
647 * c) Heap is first-half full => EF = 1/2
648 * d) Heap is half full, full and empty regions interleave => EF =~ 1
649 */
650double ShenandoahFreeSet::external_fragmentation() {
651 size_t last_idx = 0;
652 size_t max_contig = 0;
653 size_t empty_contig = 0;
654
655 size_t free = 0;
656
657 for (size_t index = _mutator_leftmost; index <= _mutator_rightmost; index++) {
658 if (is_mutator_free(index)) {
659 ShenandoahHeapRegion* r = _heap->get_region(index);
660 if (r->is_empty()) {
661 free += ShenandoahHeapRegion::region_size_bytes();
662 if (last_idx + 1 == index) {
663 empty_contig++;
664 } else {
665 empty_contig = 1;
666 }
667 } else {
668 empty_contig = 0;
669 }
670
671 max_contig = MAX2(max_contig, empty_contig);
672 last_idx = index;
673 }
674 }
675
676 if (free > 0) {
677 return 1 - (1.0 * max_contig * ShenandoahHeapRegion::region_size_bytes() / free);
678 } else {
679 return 0;
680 }
681}
682
683#ifdef ASSERT1
684void ShenandoahFreeSet::assert_bounds() const {
685 // Performance invariants. Failing these would not break the free set, but performance
686 // would suffer.
687 assert (_mutator_leftmost <= _max, "leftmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, _mutator_leftmost, _max)do { if (!(_mutator_leftmost <= _max)) { (*g_assert_poison
) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 687, "assert(" "_mutator_leftmost <= _max" ") failed", "leftmost in bounds: "
"%" "l" "u" " < " "%" "l" "u", _mutator_leftmost, _max); ::
breakpoint(); } } while (0)
;
688 assert (_mutator_rightmost < _max, "rightmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, _mutator_rightmost, _max)do { if (!(_mutator_rightmost < _max)) { (*g_assert_poison
) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 688, "assert(" "_mutator_rightmost < _max" ") failed", "rightmost in bounds: "
"%" "l" "u" " < " "%" "l" "u", _mutator_rightmost, _max);
::breakpoint(); } } while (0)
;
689
690 assert (_mutator_leftmost == _max || is_mutator_free(_mutator_leftmost), "leftmost region should be free: " SIZE_FORMAT, _mutator_leftmost)do { if (!(_mutator_leftmost == _max || is_mutator_free(_mutator_leftmost
))) { (*g_assert_poison) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 690, "assert(" "_mutator_leftmost == _max || is_mutator_free(_mutator_leftmost)"
") failed", "leftmost region should be free: " "%" "l" "u", _mutator_leftmost
); ::breakpoint(); } } while (0)
;
691 assert (_mutator_rightmost == 0 || is_mutator_free(_mutator_rightmost), "rightmost region should be free: " SIZE_FORMAT, _mutator_rightmost)do { if (!(_mutator_rightmost == 0 || is_mutator_free(_mutator_rightmost
))) { (*g_assert_poison) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 691, "assert(" "_mutator_rightmost == 0 || is_mutator_free(_mutator_rightmost)"
") failed", "rightmost region should be free: " "%" "l" "u",
_mutator_rightmost); ::breakpoint(); } } while (0)
;
692
693 size_t beg_off = _mutator_free_bitmap.get_next_one_offset(0);
694 size_t end_off = _mutator_free_bitmap.get_next_one_offset(_mutator_rightmost + 1);
695 assert (beg_off >= _mutator_leftmost, "free regions before the leftmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, beg_off, _mutator_leftmost)do { if (!(beg_off >= _mutator_leftmost)) { (*g_assert_poison
) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 695, "assert(" "beg_off >= _mutator_leftmost" ") failed"
, "free regions before the leftmost: " "%" "l" "u" ", bound "
"%" "l" "u", beg_off, _mutator_leftmost); ::breakpoint(); } }
while (0)
;
696 assert (end_off == _max, "free regions past the rightmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, end_off, _mutator_rightmost)do { if (!(end_off == _max)) { (*g_assert_poison) = 'X';; report_vm_error
("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 696, "assert(" "end_off == _max" ") failed", "free regions past the rightmost: "
"%" "l" "u" ", bound " "%" "l" "u", end_off, _mutator_rightmost
); ::breakpoint(); } } while (0)
;
697
698 assert (_collector_leftmost <= _max, "leftmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, _collector_leftmost, _max)do { if (!(_collector_leftmost <= _max)) { (*g_assert_poison
) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 698, "assert(" "_collector_leftmost <= _max" ") failed",
"leftmost in bounds: " "%" "l" "u" " < " "%" "l" "u", _collector_leftmost
, _max); ::breakpoint(); } } while (0)
;
699 assert (_collector_rightmost < _max, "rightmost in bounds: " SIZE_FORMAT " < " SIZE_FORMAT, _collector_rightmost, _max)do { if (!(_collector_rightmost < _max)) { (*g_assert_poison
) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 699, "assert(" "_collector_rightmost < _max" ") failed",
"rightmost in bounds: " "%" "l" "u" " < " "%" "l" "u", _collector_rightmost
, _max); ::breakpoint(); } } while (0)
;
700
701 assert (_collector_leftmost == _max || is_collector_free(_collector_leftmost), "leftmost region should be free: " SIZE_FORMAT, _collector_leftmost)do { if (!(_collector_leftmost == _max || is_collector_free(_collector_leftmost
))) { (*g_assert_poison) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 701, "assert(" "_collector_leftmost == _max || is_collector_free(_collector_leftmost)"
") failed", "leftmost region should be free: " "%" "l" "u", _collector_leftmost
); ::breakpoint(); } } while (0)
;
702 assert (_collector_rightmost == 0 || is_collector_free(_collector_rightmost), "rightmost region should be free: " SIZE_FORMAT, _collector_rightmost)do { if (!(_collector_rightmost == 0 || is_collector_free(_collector_rightmost
))) { (*g_assert_poison) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 702, "assert(" "_collector_rightmost == 0 || is_collector_free(_collector_rightmost)"
") failed", "rightmost region should be free: " "%" "l" "u",
_collector_rightmost); ::breakpoint(); } } while (0)
;
703
704 beg_off = _collector_free_bitmap.get_next_one_offset(0);
705 end_off = _collector_free_bitmap.get_next_one_offset(_collector_rightmost + 1);
706 assert (beg_off >= _collector_leftmost, "free regions before the leftmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, beg_off, _collector_leftmost)do { if (!(beg_off >= _collector_leftmost)) { (*g_assert_poison
) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 706, "assert(" "beg_off >= _collector_leftmost" ") failed"
, "free regions before the leftmost: " "%" "l" "u" ", bound "
"%" "l" "u", beg_off, _collector_leftmost); ::breakpoint(); }
} while (0)
;
707 assert (end_off == _max, "free regions past the rightmost: " SIZE_FORMAT ", bound " SIZE_FORMAT, end_off, _collector_rightmost)do { if (!(end_off == _max)) { (*g_assert_poison) = 'X';; report_vm_error
("/home/daniel/Projects/java/jdk/src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp"
, 707, "assert(" "end_off == _max" ") failed", "free regions past the rightmost: "
"%" "l" "u" ", bound " "%" "l" "u", end_off, _collector_rightmost
); ::breakpoint(); } } while (0)
;
708}
709#endif