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
34 /**
35 * SlidingForwarding is a method to store forwarding information in a compressed form into the object header,
36 * that has been specifically designed for sliding compaction GCs and compact object headers. With compact object
37 * headers, we store the compressed class pointer in the header, which would be overwritten by full forwarding
38 * pointer, if we allow the legacy forwarding code to act. This would lose the class information for the object,
39 * which is required later in GC cycle to iterate the reference fields and get the object size for copying.
40 *
41 * SlidingForwarding requires only small side tables and guarantees constant-time access and modification.
42 *
43 * The idea is to use a pointer compression scheme very similar to the one that is used for compressed oops.
44 * We divide the heap into number of logical regions. Each region spans maximum of 2^NUM_OFFSET_BITS words.
45 *
46 * The key advantage of sliding compaction for encoding efficiency: it can forward objects from one region to a
47 * maximum of two regions. This is an intuitive property: when we slide the compact region full of data, it can
48 * only span two adjacent regions. This property allows us to use the off-side table to record the addresses of
49 * two target regions. The table holds N*2 entries for N logical regions. For each region, it gives the base
50 * address of the two target regions, or a special placeholder if not used. A single bit in forwarding would
51 * indicate to which of the two "to" regions the object is forwarded into.
52 *
53 * This encoding efficiency allows to store the forwarding information in the object header _together_ with the
54 * compressed class pointer.
55 *
56 * When recording the sliding forwarding, the mark word would look roughly like this:
57 *
58 * 64 32 0
59 * [................................OOOOOOOOOOOOOOOOOOOOOOOOOOOOAFTT]
60 * ^----- normal lock bits, would record "object is forwarded"
61 * ^------- fallback bit (explained below)
62 * ^-------- alternate region select
63 * ^------------------------------------ in-region offset
64 * ^-------------------------------------------------------------------- protected area, *not touched* by this code, useful for
65 * compressed class pointer with compact object headers
66 *
67 * Adding a forwarding then generally works as follows:
68 * 1. Compute the "to" offset in the "to" region, this gives "offset".
69 * 2. Check if the primary "from" offset at base table contains "to" region base, use it.
70 * If not usable, continue to next step. If usable, set "alternate" = "false" and jump to (4).
71 * 3. Check if the alternate "from" offset at base table contains "to" region base, use it.
72 * This gives us "alternate" = "true". This should always complete for sliding forwarding.
73 * 4. Compute the mark word from "offset" and "alternate", write it out
74 *
75 * Similarly, looking up the target address, given an original object address generally works as follows:
76 * 1. Load the mark from object, and decode "offset" and "alternate" from there
77 * 2. Compute the "from" base offset from the object
78 * 3. Look up "to" region base from the base table either at primary or alternate indices, using "alternate" flag
79 * 4. Compute the "to" address from "to" region base and "offset"
80 *
81 * This algorithm is broken by G1 last-ditch serial compaction: there, object from a single region can be
82 * forwarded to multiple, more than two regions. To deal with that, we initialize a fallback-hashtable for
83 * storing those extra forwardings, and set another bit in the header to indicate that the forwardee is not
84 * encoded but should be looked-up in the hashtable. G1 serial compaction is not very common - it is the
85 * last-last-ditch GC that is used when the JVM is scrambling to squeeze more space out of the heap, and at
86 * that point, ultimate performance is no longer the main concern.
87 */
88 class SlidingForwarding : public AllStatic {
89 private:
90
91 /*
92 * A simple hash-table that acts as fallback for the sliding forwarding.
93 * This is used in the case of G1 serial compaction, which violates the
94 * assumption of sliding forwarding that each object of any region is only
95 * ever forwarded to one of two target regions. At this point, the GC is
96 * scrambling to free up more Java heap memory, and therefore performance
97 * is not the major concern.
98 *
99 * The implementation is a straightforward open hashtable.
100 * It is a single-threaded (not thread-safe) implementation, and that
101 * is sufficient because G1 serial compaction is single-threaded.
102 */
103 class FallbackTable : public CHeapObj<mtGC>{
104 private:
105 struct FallbackTableEntry {
106 FallbackTableEntry* _next;
107 HeapWord* _from;
108 HeapWord* _to;
109 };
110
111 static const uint TABLE_SIZE = 1024;
112 FallbackTableEntry _table[TABLE_SIZE];
113
114 static size_t home_index(HeapWord* from);
115
116 public:
117 FallbackTable();
118 ~FallbackTable();
119
120 void forward_to(HeapWord* from, HeapWord* to);
121 HeapWord* forwardee(HeapWord* from) const;
122 };
123
124 static const uintptr_t MARK_LOWER_HALF_MASK = right_n_bits(32);
125
126 // We need the lowest two bits to indicate a forwarded object.
127 // The next bit indicates that the forwardee should be looked-up in a fallback-table.
128 static const int FALLBACK_SHIFT = markWord::lock_bits;
129 static const int FALLBACK_BITS = 1;
130 static const int FALLBACK_MASK = right_n_bits(FALLBACK_BITS) << FALLBACK_SHIFT;
131
132 // Next bit selects the target region
133 static const int ALT_REGION_SHIFT = FALLBACK_SHIFT + FALLBACK_BITS;
134 static const int ALT_REGION_BITS = 1;
135 // This will be "2" always, but expose it as named constant for clarity
136 static const size_t NUM_TARGET_REGIONS = 1 << ALT_REGION_BITS;
137
138 // The offset bits start then
139 static const int OFFSET_BITS_SHIFT = ALT_REGION_SHIFT + ALT_REGION_BITS;
140
141 // How many bits we use for the offset
142 static const int NUM_OFFSET_BITS = 32 - OFFSET_BITS_SHIFT;
143
144 // Indicates an unused base address in the target base table.
145 static HeapWord* const UNUSED_BASE;
146
147 static HeapWord* _heap_start;
148 static size_t _region_size_words;
149
150 static size_t _heap_start_region_bias;
151 static size_t _num_regions;
152 static uint _region_size_bytes_shift;
153 static uintptr_t _region_mask;
154
155 // The target base table memory.
156 static HeapWord** _bases_table;
157 // Entries into the target base tables, biased to the start of the heap.
158 static HeapWord** _biased_bases[NUM_TARGET_REGIONS];
159
160 static FallbackTable* _fallback_table;
161
162 static inline size_t biased_region_index_containing(HeapWord* addr);
163
164 static inline uintptr_t encode_forwarding(HeapWord* from, HeapWord* to);
165 static inline HeapWord* decode_forwarding(HeapWord* from, uintptr_t encoded);
166
167 static void fallback_forward_to(HeapWord* from, HeapWord* to);
168 static HeapWord* fallback_forwardee(HeapWord* from);
169
170 static inline void forward_to_impl(oop from, oop to);
171 static inline oop forwardee_impl(oop from);
172
173 public:
174 static void initialize(MemRegion heap, size_t region_size_words);
175
176 static void begin();
177 static void end();
178
179 static inline bool is_forwarded(oop obj);
180 static inline bool is_not_forwarded(oop obj);
181
182 template <bool ALT_FWD>
183 static inline void forward_to(oop from, oop to);
184 template <bool ALT_FWD>
185 static inline oop forwardee(oop from);
186 };
187
188 #endif // SHARE_GC_SHARED_SLIDINGFORWARDING_HPP