1 /*
2 * Copyright (c) 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 #ifndef SHARE_GC_SHARED_SLIDINGFORWARDING_HPP
26 #define SHARE_GC_SHARED_SLIDINGFORWARDING_HPP
27
28 #include "memory/allocation.hpp"
29 #include "memory/memRegion.hpp"
30 #include "oops/oopsHierarchy.hpp"
31
32 /**
33 * SlidingForwarding is a method to store forwarding information in a compressed form into the object header,
34 * that has been specifically designed for sliding compaction GCs.
35 * It avoids overriding the compressed class pointer in the upper bits of the header, which would otherwise
36 * be lost. SlidingForwarding requires only small side tables and guarantees constant-time access and modification.
37 *
38 * The idea is to use a pointer compression scheme very similar to the one that is used for compressed oops.
39 * We divide the heap into number of logical regions. Each region spans maximum of 2^NUM_BITS words.
40 * We take advantage of the fact that sliding compaction can forward objects from one region to a maximum of
41 * two regions (including itself, but that does not really matter). We need 1 bit to indicate which region is forwarded
42 * into. We also currently require the two lowest header bits to indicate that the object is forwarded.
43 *
44 * For addressing, we need a table with N*2 entries, for N logical regions. For each region, it gives the base
45 * address of the two target regions, or a special placeholder if not used.
46 *
47 * Adding a forwarding then works as follows:
48 * Given an original address 'orig', and a 'target' address:
49 * - Look-up first target base of region of orig. If not yet used,
50 * establish it to be the base of region of target address. Use that base in step 3.
51 * - Else, if first target base is already used, check second target base. This must either be unused, or the
52 * base of the region of our target address. If unused, establish it to be the base of the region of our target
53 * address. Use that base for next step.
54 * - Now we found a base address. Encode the target address with that base into lowest NUM_BITS bits, and shift
55 * that up by 3 bits. Set the 3rd bit if we used the secondary target base, otherwise leave it at 0. Set the
56 * lowest two bits to indicate that the object has been forwarded. Store that in the lowest NUM_BITS+3 bits of the
57 * original object's header.
58 *
59 * Similarily, looking up the target address, given an original object address works as follows:
60 * - Load lowest NUM_BITS + 3 from original object header. Extract target region bit and compressed address bits.
61 * - Depending on target region bit, load base address from the target base table by looking up the corresponding entry
62 * for the region of the original object.
63 * - Decode the target address by using the target base address and the compressed address bits.
64 */
65
66 class SlidingForwarding : public CHeapObj<mtGC> {
67 #ifdef _LP64
68 private:
69 static const int NUM_REGION_BITS = 1;
70
71 static const uintptr_t ONE = 1ULL;
72
73 static const size_t NUM_REGIONS = ONE << NUM_REGION_BITS;
74
75 // We need the lowest three bits to indicate a forwarded object and self-forwarding.
76 static const int BASE_SHIFT = 3;
77
78 // The compressed address bits start here.
79 static const int COMPRESSED_BITS_SHIFT = BASE_SHIFT + NUM_REGION_BITS;
80
81 // How many bits we use for the compressed pointer (we are going to need one more bit to indicate target region, and
82 // two lowest bits to mark objects as forwarded)
83 static const int NUM_COMPRESSED_BITS = 32 - BASE_SHIFT - NUM_REGION_BITS;
84
85 // Indicates an usused base address in the target base table. We cannot use 0, because that may already be
86 // a valid base address in zero-based heaps. 0x1 is safe because heap base addresses must be aligned by 2^X.
87 static HeapWord* const UNUSED_BASE;
88
89 HeapWord* const _heap_start;
90 size_t const _num_regions;
91 size_t const _region_size_words_shift;
92 HeapWord** const _target_base_table;
93
94 inline size_t region_index_containing(HeapWord* addr) const;
95 inline bool region_contains(HeapWord* region_base, HeapWord* addr) const;
96
97 inline uintptr_t encode_forwarding(HeapWord* original, HeapWord* target);
98 inline HeapWord* decode_forwarding(HeapWord* original, uintptr_t encoded) const;
99
100 #endif
101
102 public:
103 SlidingForwarding(MemRegion heap);
104 SlidingForwarding(MemRegion heap, size_t num_regions);
105 ~SlidingForwarding();
106
107 void clear();
108 inline void forward_to(oop original, oop target);
109 inline oop forwardee(oop original) const;
110 };
111
112 #endif // SHARE_GC_SHARED_SLIDINGFORWARDING_HPP