1 /*
2 * Copyright (c) 2021, Red Hat, Inc. All rights reserved.
3 * Copyright Amazon.com Inc. or its affiliates. All Rights Reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 *
24 */
25
26 #ifndef SHARE_GC_SHARED_SLIDINGFORWARDING_HPP
27 #define SHARE_GC_SHARED_SLIDINGFORWARDING_HPP
28
29 #include "memory/allocation.hpp"
30 #include "memory/memRegion.hpp"
31 #include "oops/markWord.hpp"
32 #include "oops/oopsHierarchy.hpp"
33 #include "utilities/fastHash.hpp"
34 #include "utilities/resourceHash.hpp"
35
36 /**
37 * SlidingForwarding is a method to store forwarding information in a compressed form into the object header,
38 * that has been specifically designed for sliding compaction GCs and compact object headers. With compact object
39 * headers, we store the compressed class pointer in the header, which would be overwritten by full forwarding
40 * pointer, if we allow the legacy forwarding code to act. This would lose the class information for the object,
41 * which is required later in GC cycle to iterate the reference fields and get the object size for copying.
42 *
43 * SlidingForwarding requires only small side tables and guarantees constant-time access and modification.
44 *
45 * The idea is to use a pointer compression scheme very similar to the one that is used for compressed oops.
46 * We divide the heap into number of logical regions. Each region spans maximum of 2^NUM_OFFSET_BITS words.
47 *
48 * The key advantage of sliding compaction for encoding efficiency: it can forward objects from one region to a
49 * maximum of two regions. This is an intuitive property: when we slide the compact region full of data, it can
50 * only span two adjacent regions. This property allows us to use the off-side table to record the addresses of
51 * two target regions. The table holds N*2 entries for N logical regions. For each region, it gives the base
52 * address of the two target regions, or a special placeholder if not used. A single bit in forwarding would
53 * indicate to which of the two "to" regions the object is forwarded into.
54 *
55 * This encoding efficiency allows to store the forwarding information in the object header _together_ with the
56 * compressed class pointer.
57 *
58 * When recording the sliding forwarding, the mark word would look roughly like this:
59 *
60 * 64 32 0
61 * [................................OOOOOOOOOOOOOOOOOOOOOOOOOOOOAFTT]
62 * ^----- normal lock bits, would record "object is forwarded"
63 * ^------- fallback bit (explained below)
64 * ^-------- alternate region select
65 * ^------------------------------------ in-region offset
66 * ^-------------------------------------------------------------------- protected area, *not touched* by this code, useful for
67 * compressed class pointer with compact object headers
68 *
69 * Adding a forwarding then generally works as follows:
70 * 1. Compute the "to" offset in the "to" region, this gives "offset".
71 * 2. Check if the primary "from" offset at base table contains "to" region base, use it.
72 * If not usable, continue to next step. If usable, set "alternate" = "false" and jump to (4).
73 * 3. Check if the alternate "from" offset at base table contains "to" region base, use it.
74 * This gives us "alternate" = "true". This should always complete for sliding forwarding.
75 * 4. Compute the mark word from "offset" and "alternate", write it out
76 *
77 * Similarly, looking up the target address, given an original object address generally works as follows:
78 * 1. Load the mark from object, and decode "offset" and "alternate" from there
79 * 2. Compute the "from" base offset from the object
80 * 3. Look up "to" region base from the base table either at primary or alternate indices, using "alternate" flag
81 * 4. Compute the "to" address from "to" region base and "offset"
82 *
83 * This algorithm is broken by G1 last-ditch serial compaction: there, object from a single region can be
84 * forwarded to multiple, more than two regions. To deal with that, we initialize a fallback-hashtable for
85 * storing those extra forwardings, and set another bit in the header to indicate that the forwardee is not
86 * encoded but should be looked-up in the hashtable. G1 serial compaction is not very common - it is the
87 * last-last-ditch GC that is used when the JVM is scrambling to squeeze more space out of the heap, and at
88 * that point, ultimate performance is no longer the main concern.
89 */
90 class SlidingForwarding : public AllStatic {
91 private:
92
93 /*
94 * A simple hash-table that acts as fallback for the sliding forwarding.
95 * This is used in the case of G1 serial compaction, which violates the
96 * assumption of sliding forwarding that each object of any region is only
97 * ever forwarded to one of two target regions. At this point, the GC is
98 * scrambling to free up more Java heap memory, and therefore performance
99 * is not the major concern.
100 *
101 * The implementation is a straightforward open hashtable.
102 * It is a single-threaded (not thread-safe) implementation, and that
103 * is sufficient because G1 serial compaction is single-threaded.
104 */
105 inline static unsigned hash(HeapWord* const& from) {
106 uint64_t val = reinterpret_cast<uint64_t>(from);
107 uint64_t hash = FastHash::get_hash64(val, UCONST64(0xAAAAAAAAAAAAAAAA));
108 return checked_cast<unsigned>(hash >> 32);
109 }
110 inline static bool equals(HeapWord* const& lhs, HeapWord* const& rhs) {
111 return lhs == rhs;
112 }
113 typedef ResourceHashtable<HeapWord* /* key-type */, HeapWord* /* value-type */,
114 1024 /* size */, AnyObj::C_HEAP /* alloc-type */, mtGC,
115 SlidingForwarding::hash, SlidingForwarding::equals> FallbackTable;
116
117 static const uintptr_t MARK_LOWER_HALF_MASK = right_n_bits(32);
118
119 // We need the lowest two bits to indicate a forwarded object.
120 // The next bit indicates that the forwardee should be looked-up in a fallback-table.
121 static const int FALLBACK_SHIFT = markWord::lock_bits;
122 static const int FALLBACK_BITS = 1;
123 static const int FALLBACK_MASK = right_n_bits(FALLBACK_BITS) << FALLBACK_SHIFT;
124
125 // Next bit selects the target region
126 static const int ALT_REGION_SHIFT = FALLBACK_SHIFT + FALLBACK_BITS;
127 static const int ALT_REGION_BITS = 1;
128 // This will be "2" always, but expose it as named constant for clarity
129 static const size_t NUM_TARGET_REGIONS = 1 << ALT_REGION_BITS;
130
131 // The offset bits start then
132 static const int OFFSET_BITS_SHIFT = ALT_REGION_SHIFT + ALT_REGION_BITS;
133
134 // How many bits we use for the offset
135 static const int NUM_OFFSET_BITS = 32 - OFFSET_BITS_SHIFT;
136
137 // Indicates an unused base address in the target base table.
138 static HeapWord* const UNUSED_BASE;
139
140 static HeapWord* _heap_start;
141 static size_t _region_size_words;
142
143 static size_t _heap_start_region_bias;
144 static size_t _num_regions;
145 static uint _region_size_bytes_shift;
146 static uintptr_t _region_mask;
147
148 // The target base table memory.
149 static HeapWord** _bases_table;
150 // Entries into the target base tables, biased to the start of the heap.
151 static HeapWord** _biased_bases[NUM_TARGET_REGIONS];
152
153 static FallbackTable* _fallback_table;
154
155 static inline size_t biased_region_index_containing(HeapWord* addr);
156
157 static inline uintptr_t encode_forwarding(HeapWord* from, HeapWord* to);
158 static inline HeapWord* decode_forwarding(HeapWord* from, uintptr_t encoded);
159
160 static void fallback_forward_to(HeapWord* from, HeapWord* to);
161 static HeapWord* fallback_forwardee(HeapWord* from);
162
163 static inline void forward_to_impl(oop from, oop to);
164 static inline oop forwardee_impl(oop from);
165
166 public:
167 static void initialize(MemRegion heap, size_t region_size_words);
168
169 static void begin();
170 static void end();
171
172 static inline bool is_forwarded(oop obj);
173 static inline bool is_not_forwarded(oop obj);
174
175 template <bool ALT_FWD>
176 static inline void forward_to(oop from, oop to);
177 template <bool ALT_FWD>
178 static inline oop forwardee(oop from);
179 };
180
181 #endif // SHARE_GC_SHARED_SLIDINGFORWARDING_HPP