1 /*
2 * Copyright Amazon.com Inc. or its affiliates. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 #ifndef SHARE_GC_SHARED_FULLGCFORWARDING_INLINE_HPP
25 #define SHARE_GC_SHARED_FULLGCFORWARDING_INLINE_HPP
26
27 #include "gc/shared/fullGCForwarding.hpp"
28 #include "logging/log.hpp"
29 #include "nmt/memTag.hpp"
30 #include "oops/markWord.hpp"
31 #include "oops/oop.inline.hpp"
32 #include "utilities/concurrentHashTable.inline.hpp"
33 #include "utilities/fastHash.hpp"
34 #include "utilities/macros.hpp"
35 #include "utilities/powerOfTwo.hpp"
36
37 // We cannot use 0, because that may already be a valid base address in zero-based heaps.
38 // 0x1 is safe because heap base addresses must be aligned by much larger alignment
39 template <int BITS>
40 HeapWord* const FullGCForwardingImpl<BITS>::UNUSED_BASE = reinterpret_cast<HeapWord*>(0x1);
41
42 template <int BITS>
43 HeapWord* FullGCForwardingImpl<BITS>::_heap_start = nullptr;
44 template <int BITS>
45 size_t FullGCForwardingImpl<BITS>::_heap_start_region_bias = 0;
46 template <int BITS>
47 size_t FullGCForwardingImpl<BITS>::_num_regions = 0;
48 template <int BITS>
49 uintptr_t FullGCForwardingImpl<BITS>::_region_mask = 0;
50 template <int BITS>
51 HeapWord** FullGCForwardingImpl<BITS>::_biased_bases = nullptr;
52 template <int BITS>
53 HeapWord** FullGCForwardingImpl<BITS>::_bases_table = nullptr;
54 template <int BITS>
55 size_t FullGCForwardingImpl<BITS>::_fallback_table_log2_start_size = 9; // 512 entries.
56 template <int BITS>
57 FallbackTable* FullGCForwardingImpl<BITS>::_fallback_table = nullptr;
58 #ifndef PRODUCT
59 template <int BITS>
60 volatile uint64_t FullGCForwardingImpl<BITS>::_num_forwardings = 0;
61 template <int BITS>
62 volatile uint64_t FullGCForwardingImpl<BITS>::_num_fallback_forwardings = 0;
63 #endif
64
65 template <int BITS>
66 bool FullGCForwardingImpl<BITS>::is_forwarded(oop obj) {
67 return obj->is_forwarded();
68 }
69
70 template <int BITS>
71 size_t FullGCForwardingImpl<BITS>::biased_region_index_containing(HeapWord* addr) {
72 return reinterpret_cast<uintptr_t>(addr) >> BLOCK_SIZE_BYTES_SHIFT;
73 }
74
75 template <int BITS>
76 bool FullGCForwardingImpl<BITS>::is_fallback(uintptr_t encoded) {
77 return (encoded & OFFSET_MASK) == FALLBACK_PATTERN_IN_PLACE;
78 }
79
80 template <int BITS>
81 uintptr_t FullGCForwardingImpl<BITS>::encode_forwarding(HeapWord* from, HeapWord* to) {
82 size_t from_block_idx = biased_region_index_containing(from);
83
84 HeapWord* to_region_base = _biased_bases[from_block_idx];
85 if (to_region_base == UNUSED_BASE) {
86 HeapWord* prev = Atomic::cmpxchg(&_biased_bases[from_block_idx], UNUSED_BASE, to);
87 if (prev == UNUSED_BASE) {
88 to_region_base = to;
89 } else {
90 to_region_base = prev;
91 }
92 // _biased_bases[from_block_idx] = to_region_base = to;
93 }
94 // Avoid pointer_delta() on purpose: using an unsigned subtraction,
95 // we get an underflow when to < to_region_base, which means
96 // we can use a single comparison instead of:
97 // if (to_region_base > to || (to - to_region_base) > MAX_OFFSET) { .. }
98 size_t offset = static_cast<size_t>(to - to_region_base);
99 if (offset > MAX_OFFSET) {
100 offset = FALLBACK_PATTERN;
101 }
102 uintptr_t encoded = (offset << OFFSET_BITS_SHIFT) | markWord::marked_value;
103
104 assert(is_fallback(encoded) || to == decode_forwarding(from, encoded), "must be reversible: " PTR_FORMAT " -> " PTR_FORMAT ", reversed: " PTR_FORMAT ", encoded: " INTPTR_FORMAT ", to_region_base: " PTR_FORMAT ", from_block_idx: %lu", p2i(from), p2i(to), p2i(decode_forwarding(from, encoded)), encoded, p2i(to_region_base), from_block_idx);
105 assert((encoded & ~AVAILABLE_BITS_MASK) == 0, "must encode to available bits");
106 return encoded;
107 }
108
109 template <int BITS>
110 HeapWord* FullGCForwardingImpl<BITS>::decode_forwarding(HeapWord* from, uintptr_t encoded) {
111 assert(!is_fallback(encoded), "must not be fallback-forwarded, encoded: " INTPTR_FORMAT ", OFFSET_MASK: " INTPTR_FORMAT ", FALLBACK_PATTERN_IN_PLACE: " INTPTR_FORMAT, encoded, OFFSET_MASK, FALLBACK_PATTERN_IN_PLACE);
112 assert((encoded & ~AVAILABLE_BITS_MASK) == 0, "must decode from available bits, encoded: " INTPTR_FORMAT, encoded);
113 uintptr_t offset = (encoded >> OFFSET_BITS_SHIFT);
114
115 size_t from_idx = biased_region_index_containing(from);
116 HeapWord* base = _biased_bases[from_idx];
117 assert(base != UNUSED_BASE, "must not be unused base: encoded: " INTPTR_FORMAT, encoded);
118 HeapWord* decoded = base + offset;
119 assert(decoded >= _heap_start,
120 "Address must be above heap start. encoded: " INTPTR_FORMAT ", base: " PTR_FORMAT,
121 encoded, p2i(base));
122
123 return decoded;
124 }
125
126 template <int BITS>
127 void FullGCForwardingImpl<BITS>::forward_to_impl(oop from, oop to) {
128 assert(_bases_table != nullptr, "call begin() before forwarding");
129
130 markWord from_header = from->mark();
131 HeapWord* from_hw = cast_from_oop<HeapWord*>(from);
132 HeapWord* to_hw = cast_from_oop<HeapWord*>(to);
133 uintptr_t encoded = encode_forwarding(from_hw, to_hw);
134 markWord new_header = markWord((from_header.value() & ~OFFSET_MASK) | encoded);
135 from->set_mark(new_header);
136
137 if (is_fallback(encoded)) {
138 fallback_forward_to(from_hw, to_hw);
139 }
140 NOT_PRODUCT(Atomic::inc(&_num_forwardings);)
141 }
142
143 template <int BITS>
144 void FullGCForwardingImpl<BITS>::forward_to(oop obj, oop fwd) {
145 assert(fwd != nullptr, "no null forwarding");
146 #ifdef _LP64
147 assert(_bases_table != nullptr, "expect sliding forwarding initialized");
148 forward_to_impl(obj, fwd);
149 // assert(forwardee(obj) == fwd, "must be forwarded to correct forwardee, obj: " PTR_FORMAT ", forwardee(obj): " PTR_FORMAT ", fwd: " PTR_FORMAT ", mark: " INTPTR_FORMAT ", num-regions: %lu, base: " PTR_FORMAT ", OFFSET_MASK: " INTPTR_FORMAT ", encoded: " PTR_FORMAT ", biased-base: " PTR_FORMAT ", heap-start: " PTR_FORMAT, p2i(obj), p2i(forwardee(obj)), p2i(fwd), obj->mark().value(), _num_regions, p2i(_bases_table[0]), OFFSET_MASK, encode_forwarding(cast_from_oop<HeapWord*>(obj), cast_from_oop<HeapWord*>(fwd)), p2i(_biased_bases[biased_region_index_containing(cast_from_oop<HeapWord*>(obj))]), p2i(_heap_start));
150 #else
151 obj->forward_to(fwd);
152 #endif
153 }
154
155 template <int BITS>
156 oop FullGCForwardingImpl<BITS>::forwardee_impl(oop from) {
157 assert(_bases_table != nullptr, "call begin() before asking for forwarding");
158
159 markWord header = from->mark();
160 HeapWord* from_hw = cast_from_oop<HeapWord*>(from);
161 if (is_fallback(header.value())) {
162 HeapWord* to = fallback_forwardee(from_hw);
163 return cast_to_oop(to);
164 }
165 uintptr_t encoded = header.value() & OFFSET_MASK;
166 HeapWord* to = decode_forwarding(from_hw, encoded);
167 return cast_to_oop(to);
168 }
169
170 template <int BITS>
171 oop FullGCForwardingImpl<BITS>::forwardee(oop obj) {
172 #ifdef _LP64
173 assert(_bases_table != nullptr, "expect sliding forwarding initialized");
174 return forwardee_impl(obj);
175 #else
176 return obj->forwardee();
177 #endif
178 }
179
180 static uintx hash(HeapWord* const& addr) {
181 uint64_t val = reinterpret_cast<uint64_t>(addr);
182 uint32_t hash = FastHash::get_hash32(static_cast<uint32_t>(val), static_cast<uint32_t>(val >> 32));
183 return hash;
184 }
185
186 struct ForwardingEntry {
187 HeapWord* _from;
188 HeapWord* _to;
189 ForwardingEntry(HeapWord* from, HeapWord* to) : _from(from), _to(to) {}
190 };
191
192 struct FallbackTableConfig {
193 using Value = ForwardingEntry;
194 static uintx get_hash(Value const& entry, bool* is_dead) {
195 return hash(entry._from);
196 }
197 static void* allocate_node(void* context, size_t size, Value const& value) {
198 return AllocateHeap(size, mtGC);
199 }
200 static void free_node(void* context, void* memory, Value const& value) {
201 FreeHeap(memory);
202 }
203 };
204
205 class FallbackTable : public ConcurrentHashTable<FallbackTableConfig, mtGC> {
206 public:
207 explicit FallbackTable(size_t log2size) : ConcurrentHashTable(log2size) {}
208 };
209
210 class FallbackTableLookup : public StackObj {
211 ForwardingEntry const _entry;
212 public:
213 explicit FallbackTableLookup(HeapWord* from) : _entry(from, nullptr) {}
214 uintx get_hash() const {
215 return hash(_entry._from);
216 }
217 bool equals(const ForwardingEntry* value) const {
218 return _entry._from == value->_from;
219 }
220 static bool is_dead(ForwardingEntry* value) { return false; }
221 };
222
223 template <int BITS>
224 void FullGCForwardingImpl<BITS>::initialize(MemRegion heap) {
225 #ifdef _LP64
226 _heap_start = heap.start();
227
228 size_t rounded_heap_size = MAX2(round_up_power_of_2(heap.byte_size()) / BytesPerWord, BLOCK_SIZE_WORDS);
229
230 _num_regions = rounded_heap_size / BLOCK_SIZE_WORDS;
231
232 _heap_start_region_bias = reinterpret_cast<uintptr_t>(_heap_start) >> BLOCK_SIZE_BYTES_SHIFT;
233 _region_mask = ~((static_cast<uintptr_t>(1) << BLOCK_SIZE_BYTES_SHIFT) - 1);
234
235 assert(_bases_table == nullptr, "should not be initialized yet");
236 assert(_fallback_table == nullptr, "should not be initialized yet");
237 #endif
238 }
239
240 template <int BITS>
241 void FullGCForwardingImpl<BITS>::begin() {
242 #ifdef _LP64
243 assert(_bases_table == nullptr, "should not be initialized yet");
244 assert(_fallback_table == nullptr, "should not be initialized yet");
245
246 _fallback_table = nullptr;
247
248 #ifndef PRODUCT
249 _num_forwardings = 0;
250 _num_fallback_forwardings = 0;
251 #endif
252
253 size_t max = _num_regions;
254 _bases_table = NEW_C_HEAP_ARRAY(HeapWord*, max, mtGC);
255 HeapWord** biased_start = _bases_table - _heap_start_region_bias;
256 _biased_bases = biased_start;
257 if (max == 1) {
258 // Optimize the case when the block-size >= heap-size.
259 // In this case we can use the heap-start as block-start,
260 // and don't risk that competing GC threads set a higher
261 // address as block-start, which would lead to unnecessary
262 // fallback-usage.
263 _bases_table[0] = _heap_start;
264 } else {
265 for (size_t i = 0; i < max; i++) {
266 _bases_table[i] = UNUSED_BASE;
267 }
268 }
269 #endif
270 }
271
272 template <int BITS>
273 void FullGCForwardingImpl<BITS>::end() {
274 #ifndef PRODUCT
275 size_t fallback_table_size = _fallback_table != nullptr ? _fallback_table->get_mem_size(Thread::current()) : 0;
276 log_info(gc)("Total forwardings: " UINT64_FORMAT ", fallback forwardings: " UINT64_FORMAT
277 ", ratio: %f, memory used by fallback table: %zu%s, memory used by bases table: %zu%s",
278 _num_forwardings, _num_fallback_forwardings, static_cast<float>(_num_forwardings) / static_cast<float>(_num_fallback_forwardings),
279 byte_size_in_proper_unit(fallback_table_size),
280 proper_unit_for_byte_size(fallback_table_size),
281 byte_size_in_proper_unit(sizeof(HeapWord*) * _num_regions),
282 proper_unit_for_byte_size(sizeof(HeapWord*) * _num_regions));
283 #endif
284 #ifdef _LP64
285 assert(_bases_table != nullptr, "should be initialized");
286 FREE_C_HEAP_ARRAY(HeapWord*, _bases_table);
287 _bases_table = nullptr;
288 if (_fallback_table != nullptr) {
289 delete _fallback_table;
290 _fallback_table = nullptr;
291 }
292 #endif
293 }
294
295 template <int BITS>
296 void FullGCForwardingImpl<BITS>::maybe_init_fallback_table() {
297 if (_fallback_table == nullptr) {
298 FallbackTable* fallback_table = new FallbackTable(_fallback_table_log2_start_size);
299 FallbackTable* prev = Atomic::cmpxchg(&_fallback_table, static_cast<FallbackTable*>(nullptr), fallback_table);
300 if (prev != nullptr) {
301 // Another thread won, discard our table.
302 delete fallback_table;
303 }
304 }
305 }
306
307 template <int BITS>
308 void FullGCForwardingImpl<BITS>::fallback_forward_to(HeapWord* from, HeapWord* to) {
309 assert(to != nullptr, "no null forwarding");
310 maybe_init_fallback_table();
311 assert(_fallback_table != nullptr, "should be initialized");
312 FallbackTableLookup lookup_f(from);
313 ForwardingEntry entry(from, to);
314 auto found_f = [&](ForwardingEntry* found) {
315 // If dupe has been found, override it with new value.
316 // This is also called when new entry is succussfully inserted.
317 if (found->_to != to) {
318 found->_to = to;
319 }
320 };
321 Thread* current_thread = Thread::current();
322 bool grow;
323 bool added = _fallback_table->insert_get(current_thread, lookup_f, entry, found_f, &grow);
324 NOT_PRODUCT(Atomic::inc(&_num_fallback_forwardings);)
325 #ifdef ASSERT
326 assert(fallback_forwardee(from) != nullptr, "must have entered forwarding");
327 assert(fallback_forwardee(from) == to, "forwarding must be correct, added: %s, from: " PTR_FORMAT ", to: " PTR_FORMAT ", fwd: " PTR_FORMAT, BOOL_TO_STR(added), p2i(from), p2i(to), p2i(fallback_forwardee(from)));
328 #endif
329 if (grow) {
330 _fallback_table->grow(current_thread);
331 log_debug(gc)("grow fallback table to size: %zu bytes", _fallback_table->get_mem_size(current_thread));
332 }
333 }
334
335 template <int BITS>
336 HeapWord* FullGCForwardingImpl<BITS>::fallback_forwardee(HeapWord* from) {
337 assert(_fallback_table != nullptr, "fallback table must be present");
338 HeapWord* result;
339 FallbackTableLookup lookup_f(from);
340 auto found_f = [&](const ForwardingEntry* found) {
341 result = found->_to;
342 };
343 bool found = _fallback_table->get(Thread::current(), lookup_f, found_f);
344 assert(found, "something must have been found");
345 assert(result != nullptr, "must have found forwarding");
346 return result;
347 }
348
349 #endif // SHARE_GC_SHARED_FULLGCFORWARDING_INLINE_HPP