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