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