1 /* 2 * Copyright (c) 2001, 2019, Oracle and/or its affiliates. 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_G1_SPARSEPRT_HPP 26 #define SHARE_GC_G1_SPARSEPRT_HPP 27 28 #include "gc/g1/g1CollectedHeap.hpp" 29 #include "gc/g1/heapRegion.hpp" 30 #include "gc/shared/cardTableBarrierSet.hpp" 31 #include "memory/allocation.hpp" 32 #include "runtime/mutex.hpp" 33 #include "utilities/align.hpp" 34 #include "utilities/globalDefinitions.hpp" 35 36 class RSHashTable; 37 class SparsePRTEntry; 38 39 // Sparse remembered set for a heap region (the "owning" region). Maps 40 // indices of other regions to short sequences of cards in the other region 41 // that might contain pointers into the owner region. 42 // Concurrent access to a SparsePRT must be serialized by some external mutex. 43 class SparsePRT { 44 friend class SparsePRTBucketIter; 45 46 RSHashTable* _table; 47 48 static const size_t InitialCapacity = 8; 49 50 void expand(); 51 52 public: 53 SparsePRT(); 54 ~SparsePRT(); 55 56 size_t mem_size() const; 57 58 enum AddCardResult { 59 overflow, // The table is full, could not add the card to the table. 60 found, // The card is already in the PRT. 61 added // The card has been added. 62 }; 63 64 // Attempts to ensure that the given card_index in the given region is in 65 // the sparse table. If successful (because the card was already 66 // present, or because it was successfully added) returns "true". 67 // Otherwise, returns "false" to indicate that the addition would 68 // overflow the entry for the region. The caller must transfer these 69 // entries to a larger-capacity representation. 70 AddCardResult add_card(RegionIdx_t region_id, CardIdx_t card_index); 71 72 // Return the pointer to the entry associated with the given region. 73 SparsePRTEntry* get_entry(RegionIdx_t region_ind); 74 75 // If there is an entry for "region_ind", removes it and return "true"; 76 // otherwise returns "false." 77 bool delete_entry(RegionIdx_t region_ind); 78 79 // Clear the table, and reinitialize to initial capacity. 80 void clear(); 81 82 bool contains_card(RegionIdx_t region_id, CardIdx_t card_index) const; 83 }; 84 85 class SparsePRTEntry: public CHeapObj<mtGC> { 86 public: 87 // The type of a card entry. 88 typedef uint16_t card_elem_t; 89 90 private: 91 // We need to make sizeof(SparsePRTEntry) an even multiple of maximum member size, 92 // in order to force correct alignment that could otherwise cause SIGBUS errors 93 // when reading the member variables. This calculates the minimum number of card 94 // array elements required to get that alignment. 95 static const size_t card_array_alignment = sizeof(int) / sizeof(card_elem_t); 96 97 RegionIdx_t _region_ind; 98 int _next_index; 99 int _next_null; 100 // The actual cards stored in this array. 101 // WARNING: Don't put any data members beyond this line. Card array has, in fact, variable length. 102 // It should always be the last data member. 103 card_elem_t _cards[card_array_alignment]; 104 105 // Copy the current entry's cards into "cards". 106 inline void copy_cards(card_elem_t* cards) const; 107 public: 108 // Returns the size of the entry, used for entry allocation. size()109 static size_t size() { return sizeof(SparsePRTEntry) + sizeof(card_elem_t) * (cards_num() - card_array_alignment); } 110 // Returns the size of the card array. cards_num()111 static int cards_num() { 112 return align_up((int)G1RSetSparseRegionEntries, (int)card_array_alignment); 113 } 114 115 // Set the region_ind to the given value, and delete all cards. 116 inline void init(RegionIdx_t region_ind); 117 r_ind() const118 RegionIdx_t r_ind() const { return _region_ind; } valid_entry() const119 bool valid_entry() const { return r_ind() >= 0; } 120 next_index() const121 int next_index() const { return _next_index; } next_index_addr()122 int* next_index_addr() { return &_next_index; } set_next_index(int ni)123 void set_next_index(int ni) { _next_index = ni; } 124 125 // Returns "true" iff the entry contains the given card index. 126 inline bool contains_card(CardIdx_t card_index) const; 127 128 // Returns the number of non-NULL card entries. num_valid_cards() const129 inline int num_valid_cards() const { return _next_null; } 130 131 inline SparsePRT::AddCardResult add_card(CardIdx_t card_index); 132 133 // Copy the current entry's cards into the "_card" array of "e." 134 inline void copy_cards(SparsePRTEntry* e) const; 135 cards()136 card_elem_t* cards() { return _cards; } 137 card(int i) const138 inline CardIdx_t card(int i) const { 139 assert(i >= 0, "must be nonnegative"); 140 assert(i < cards_num(), "range checking"); 141 return (CardIdx_t)_cards[i]; 142 } 143 }; 144 145 class RSHashTable : public CHeapObj<mtGC> { 146 147 friend class RSHashTableBucketIter; 148 149 // Inverse maximum hash table occupancy used. 150 static float TableOccupancyFactor; 151 152 size_t _num_entries; 153 154 size_t _capacity; 155 size_t _capacity_mask; 156 size_t _occupied_entries; 157 158 SparsePRTEntry* _entries; 159 int* _buckets; 160 int _free_region; 161 int _free_list; 162 163 // Requires that the caller hold a lock preventing parallel modifying 164 // operations, and that the the table be less than completely full. If 165 // an entry for "region_ind" is already in the table, finds it and 166 // returns its address; otherwise allocates, initializes, inserts and 167 // returns a new entry for "region_ind". 168 SparsePRTEntry* entry_for_region_ind_create(RegionIdx_t region_ind); 169 170 // Returns the index of the next free entry in "_entries". 171 int alloc_entry(); 172 // Declares the entry "fi" to be free. (It must have already been 173 // deleted from any bucket lists. 174 void free_entry(int fi); 175 176 // For the empty sentinel created at static initialization time 177 RSHashTable(); 178 179 public: 180 RSHashTable(size_t capacity); 181 ~RSHashTable(); 182 183 static const int NullEntry = -1; 184 static RSHashTable empty_table; 185 should_expand() const186 bool should_expand() const { return _occupied_entries == _num_entries; } 187 188 // Attempts to ensure that the given card_index in the given region is in 189 // the sparse table. If successful (because the card was already 190 // present, or because it was successfully added) returns "true". 191 // Otherwise, returns "false" to indicate that the addition would 192 // overflow the entry for the region. The caller must transfer these 193 // entries to a larger-capacity representation. 194 SparsePRT::AddCardResult add_card(RegionIdx_t region_id, CardIdx_t card_index); 195 196 bool delete_entry(RegionIdx_t region_id); 197 198 bool contains_card(RegionIdx_t region_id, CardIdx_t card_index) const; 199 200 void add_entry(SparsePRTEntry* e); 201 202 SparsePRTEntry* get_entry(RegionIdx_t region_id) const; 203 204 void clear(); 205 capacity() const206 size_t capacity() const { return _capacity; } capacity_mask() const207 size_t capacity_mask() const { return _capacity_mask; } 208 size_t mem_size() const; 209 // The number of SparsePRTEntry instances available. num_entries() const210 size_t num_entries() const { return _num_entries; } 211 entry(int i) const212 SparsePRTEntry* entry(int i) const { 213 assert(i >= 0 && (size_t)i < _num_entries, "precondition"); 214 return (SparsePRTEntry*)((char*)_entries + SparsePRTEntry::size() * i); 215 } 216 217 void print(); 218 }; 219 220 // This is embedded in HRRS iterator. 221 class RSHashTableBucketIter { 222 uint _tbl_ind; // [0.._rsht->_capacity) 223 int _bl_ind; // [-1, 0.._rsht->_capacity) 224 225 RSHashTable* _rsht; 226 227 public: RSHashTableBucketIter(RSHashTable * rsht)228 RSHashTableBucketIter(RSHashTable* rsht) : 229 _tbl_ind(0), 230 _bl_ind(rsht->_buckets[_tbl_ind]), 231 _rsht(rsht) { } 232 233 bool has_next(SparsePRTEntry*& entry); 234 }; 235 236 class SparsePRTBucketIter: public RSHashTableBucketIter { 237 public: SparsePRTBucketIter(const SparsePRT * sprt)238 SparsePRTBucketIter(const SparsePRT* sprt) : 239 RSHashTableBucketIter(sprt->_table) {} 240 has_next(SparsePRTEntry * & entry)241 bool has_next(SparsePRTEntry*& entry) { 242 return RSHashTableBucketIter::has_next(entry); 243 } 244 }; 245 246 #endif // SHARE_GC_G1_SPARSEPRT_HPP 247