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 #ifndef SHARE_GC_SHARED_FULLGCFORWARDING_HPP
26 #define SHARE_GC_SHARED_FULLGCFORWARDING_HPP
27
28 #include "memory/allStatic.hpp"
29 #include "memory/memRegion.hpp"
30 #include "oops/markWord.hpp"
31 #include "oops/oopsHierarchy.hpp"
32
33 /*
34 * Implements forwarding for the Full GCs of Serial, Parallel, G1 and Shenandoah in
35 * a way that preserves upper N bits of object mark-words, which contain crucial
36 * Klass* information when running with compact headers. The encoding is similar to
37 * compressed-oops encoding: it basically subtracts the forwardee address from the
38 * heap-base, shifts that difference into the right place, and sets the lowest two
39 * bits (to indicate 'forwarded' state as usual).
40 * With compact-headers, we have 40 bits to encode forwarding pointers. This is
41 * enough to address 8TB of heap. If the heap size exceeds that limit, we turn off
42 * compact headers.
43 */
44 class FullGCForwarding : public AllStatic {
45 static const int NumLowBitsNarrow = LP64_ONLY(markWord::klass_shift) NOT_LP64(0 /*unused*/);
46 static const int NumLowBitsWide = BitsPerWord;
47 static const int Shift = markWord::lock_bits + markWord::lock_shift;
48
49 static HeapWord* _heap_base;
50 static int _num_low_bits;
51 public:
52 static void initialize_flags(size_t max_heap_size);
53 static void initialize(MemRegion heap);
54 static inline void forward_to(oop from, oop to);
55 static inline oop forwardee(oop from);
56 static inline bool is_forwarded(oop obj);
57 };
58
59 #endif // SHARE_GC_SHARED_FULLGCFORWARDING_HPP
|
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 #ifndef SHARE_GC_SHARED_FULLGCFORWARDING_HPP
26 #define SHARE_GC_SHARED_FULLGCFORWARDING_HPP
27
28 #include "memory/allocation.hpp"
29 #include "memory/memRegion.hpp"
30 #include "oops/markWord.hpp"
31 #include "oops/oopsHierarchy.hpp"
32
33 class FallbackTable;
34
35 /**
36 * FullGCForwarding is a method to store forwarding information in a compressed form into the object header,
37 * that has been specifically designed for sliding compacting GCs and compact object headers. With compact object
38 * headers, we store the compressed class pointer in the header, which would be overwritten by full forwarding
39 * pointers, if we allow the legacy forwarding code to act. This would lose the class information for the object,
40 * which is required later in GC cycle to iterate the reference fields and get the object size for copying.
41 *
42 * FullGCForwarding requires only small side tables and guarantees constant-time access and modification.
43 *
44 * The key advantage of sliding compaction for encoding efficiency:
45 * - It forwards objects linearily, starting at the heap bottom and moving up to the top, sliding
46 * live objects towards the bottom of the heap. (The reality in parallel or regionalized GCs is a bit more
47 * complex, but conceptually it is the same.)
48 * - Objects starting in any one block can only be forwarded to a memory region that is not larger than
49 * a block. (There are exceptions to this rule which are discussed below.)
50 *
51 * This is an intuitive property: when we slide the compact block full of data, it can not take up more
52 * memory afterwards.
53 * This property allows us to use a side table to record the addresses of the target memory region for
54 * each block. The table holds N entries for N blocks. For each block, it gives the base
55 * address of the target regions, or a special placeholder if not used.
56 *
57 * This encoding efficiency allows to store the forwarding information in the object header _together_ with the
58 * compressed class pointer.
59 *
60 * The idea is to use a pointer compression scheme very similar to the one that is used for compressed oops.
61 * We divide the heap into number of equal-sized blocks. Each block spans a maximum of 2^NUM_OFFSET_BITS words.
62 * We maintain a side-table of target-base-addresses, with one address entry per block.
63 *
64 * When recording the sliding forwarding, the mark word would look roughly like this:
65 *
66 * 32 0
67 * [.....................OOOOOOOOOTT]
68 * ^------ tag-bits, indicates 'forwarded'
69 * ^-------- in-region offset
70 * ^----------------- protected area, *not touched* by this code, useful for
71 * compressed class pointer with compact object headers
72 *
73 * Adding a forwarding then generally works as follows:
74 * 1. Compute the index of the block of the "from" address.
75 * 2. Load the target-base-offset of the from-block from the side-table.
76 * 3. If the base-offset is not-yet set, set it to the to-address of the forwarding.
77 * (In other words, the first forwarding of a block determines the target base-offset.)
78 * 4. Compute the offset of the to-address in the target region.
79 * 4. Store offset in the object header.
80 *
81 * Similarly, looking up the target address, given an original object address generally works as follows:
82 * 1. Compute the index of the block of the "from" address.
83 * 2. Load the target-base-offset of the from-block from the side-table.
84 * 3. Extract the offset from the object header.
85 * 4. Compute the "to" address from "to" region base and "offset"
86 *
87 * We reserve one special value for the offset:
88 * - 111111111: Indicates an exceptional forwarding (see below), for which a fallback hash-table
89 * is used to look up the target address.
90 *
91 * In order to support this, we need to make a change to the above algorithm:
92 * - Forwardings that would use offsets >= 111111111 (i.e. the last slot)
93 * would also need to use the fallback-table. We expect that to be relatively rare for two reasons:
94 * 1. It only affects 1 out of 512 possible offsets, in other words, 1/512th of all situations in an equal
95 * distribution.
96 * 2. Forwardings are not equally-distributed, because normally we 'skip' unreachable objects,
97 * thus compacting the block. Forwardings tend to cluster at the beginning of the target region,
98 * and become less likely towards the end of the possible encodable target address range.
99 * Which means in reality it will be much less frequent than 1/512.
100 *
101 * There are several conditions when the above algorithm would be broken because the assumption that
102 * 'objects from each block can only get forwarded to a region of block-size' is violated:
103 * - G1 last-ditch serial compaction: there, object from a single region can be forwarded to multiple,
104 * more than two regions. G1 serial compaction is not very common - it is the last-last-ditch GC
105 * that is used when the JVM is scrambling to squeeze more space out of the heap, and at that point,
106 * ultimate performance is no longer the main concern.
107 * - When forwarding hits a space (or G1/Shenandoah region) boundary, then latter objects of a block
108 * need to be forwarded to a different address range than earlier objects in the same block.
109 * This is rare.
110 * - With compact identity hash-code, objects can grow, and in the worst case use up more memory in
111 * the target block than we can address. We expect that to be rare.
112 *
113 * To deal with that, we initialize a fallback-hashtable for storing those extra forwardings, and use a special
114 * offset pattern (0b11...1) to indicate that the forwardee is not encoded but should be looked-up in the hashtable.
115 * This implies that this particular offset (the last word of a block) can not be used directly as forwarding,
116 * but also has to be handled by the fallback-table.
117 */
118 template <int BITS>
119 class FullGCForwardingImpl : public AllStatic {
120 friend class FullGCForwardingTest;
121 static constexpr int AVAILABLE_LOW_BITS = BITS;
122 static constexpr uintptr_t AVAILABLE_BITS_MASK = right_n_bits(AVAILABLE_LOW_BITS);
123 // The offset bits start after the lock-bits, which are currently used by Serial GC
124 // for marking objects. Could be 1 for Serial GC when being clever with the bits,
125 // and 0 for all other GCs.
126 static constexpr int OFFSET_BITS_SHIFT = markWord::lock_shift + markWord::lock_bits;
127
128 // How many bits we use for the offset
129 static constexpr int NUM_OFFSET_BITS = AVAILABLE_LOW_BITS - OFFSET_BITS_SHIFT;
130 static constexpr size_t BLOCK_SIZE_WORDS = 1ll << NUM_OFFSET_BITS;
131 static constexpr int BLOCK_SIZE_BYTES_SHIFT = NUM_OFFSET_BITS + LogHeapWordSize;
132 static constexpr size_t MAX_OFFSET = BLOCK_SIZE_WORDS - 2;
133 static constexpr uintptr_t OFFSET_MASK = right_n_bits(NUM_OFFSET_BITS) << OFFSET_BITS_SHIFT;
134
135 // This offset bit-pattern indicates that the actual mapping is handled by the
136 // fallback-table. This also implies that this cannot be used as a valid offset,
137 // and we must also use the fallback-table for mappings to the last word of a
138 // block.
139 static constexpr uintptr_t FALLBACK_PATTERN = right_n_bits(NUM_OFFSET_BITS);
140 static constexpr uintptr_t FALLBACK_PATTERN_IN_PLACE = FALLBACK_PATTERN << OFFSET_BITS_SHIFT;
141
142 // Indicates an unused base address in the target base table.
143 static HeapWord* const UNUSED_BASE;
144
145 static HeapWord* _heap_start;
146
147 static size_t _heap_start_region_bias;
148 static size_t _num_regions;
149 static uintptr_t _region_mask;
150
151 // The target base table memory.
152 static HeapWord** _bases_table;
153 // Entries into the target base tables, biased to the start of the heap.
154 static HeapWord** _biased_bases;
155
156 static size_t _fallback_table_log2_start_size;
157 static FallbackTable* _fallback_table;
158
159 #ifndef PRODUCT
160 static volatile uint64_t _num_forwardings;
161 static volatile uint64_t _num_fallback_forwardings;
162 #endif
163
164 static size_t biased_region_index_containing(HeapWord* addr);
165
166 static bool is_fallback(uintptr_t encoded);
167 static uintptr_t encode_forwarding(HeapWord* from, HeapWord* to);
168 static HeapWord* decode_forwarding(HeapWord* from, uintptr_t encoded);
169
170 static void maybe_init_fallback_table();
171 static void fallback_forward_to(HeapWord* from, HeapWord* to);
172 static HeapWord* fallback_forwardee(HeapWord* from);
173
174 static void forward_to_impl(oop from, oop to);
175 static oop forwardee_impl(oop from);
176
177 FullGCForwardingImpl() = delete;
178
179 // Used in unit-test, so that we can test fallback-table-growth.
180 static void set_fallback_table_log2_start_size(size_t fallback_table_log2_start_size) {
181 _fallback_table_log2_start_size = fallback_table_log2_start_size;
182 }
183 public:
184 static void initialize(MemRegion heap);
185
186 static void begin();
187 static void end();
188
189 static bool is_forwarded(oop obj);
190
191 static void forward_to(oop from, oop to);
192 static oop forwardee(oop from);
193 };
194
195 #ifdef _LP64
196 using FullGCForwarding = FullGCForwardingImpl<markWord::hashctrl_shift>;
197 #else
198 // On 32 bit, the BITS template argument is not used, but we still need
199 // to pass a value.
200 using FullGCForwarding = FullGCForwardingImpl<0>;
201 #endif
202
203 #endif // SHARE_GC_SHARED_FULLGCFORWARDING_HPP
|