1 /*
  2  * Copyright (c) 2021, 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_G1CARDSETCONTAINERS_HPP
 26 #define SHARE_GC_G1_G1CARDSETCONTAINERS_HPP
 27 
 28 #include "gc/g1/g1CardSet.hpp"
 29 #include "memory/allocation.hpp"
 30 #include "runtime/atomic.hpp"
 31 #include "utilities/bitMap.hpp"
 32 #include "utilities/globalDefinitions.hpp"
 33 #include "utilities/spinYield.hpp"
 34 
 35 #include "logging/log.hpp"
 36 
 37 #include "runtime/thread.inline.hpp"
 38 
 39 // A helper class to encode a few card indexes within a CardSetPtr.
 40 //
 41 // The pointer value (either 32 or 64 bits) is split into two areas:
 42 //
 43 // - Header containing identifying tag and number of encoded cards.
 44 // - Data area containing the card indexes themselves
 45 //
 46 // The header starts (from LSB) with the identifying tag (two bits,
 47 // always 00), and three bits size. The size stores the number of
 48 // valid card indexes after the header.
 49 //
 50 // The data area makes up the remainder of the word, with card indexes
 51 // put one after another at increasing bit positions. The separate
 52 // card indexes use just enough space (bits) to represent the whole
 53 // range of cards needed for covering the whole range of values
 54 // (typically in a region). There may be unused space at the top of
 55 // the word.
 56 //
 57 // Example:
 58 //
 59 //   64 bit pointer size, with 8M-size regions (8M == 2^23)
 60 // -> 2^14 (2^23 / 2^9) cards; each card represents 512 bytes in a region
 61 // -> 14 bits per card; must have enough bits to hold the max card index
 62 // -> may encode up to 4 cards into it, using 61 bits (5 bits header + 4 * 14)
 63 //
 64 // M                                                     L
 65 // S                                                     S
 66 // B                                                     B
 67 // +------+         +---------------+--------------+-----+
 68 // |unused|   ...   |  card_index1  | card_index0  |SSS00|
 69 // +------+         +---------------+--------------+-----+
 70 class G1CardSetInlinePtr : public StackObj {
 71   friend class G1CardSetContainersTest;
 72 
 73   typedef G1CardSet::CardSetPtr CardSetPtr;
 74 
 75   CardSetPtr volatile * _value_addr;
 76   CardSetPtr _value;
 77 
 78   static const uint SizeFieldLen = 3;
 79   static const uint SizeFieldPos = 2;
 80   static const uint HeaderSize = G1CardSet::CardSetPtrHeaderSize + SizeFieldLen;
 81 
 82   static const uint BitsInValue = sizeof(CardSetPtr) * BitsPerByte;
 83 
 84   static const uintptr_t SizeFieldMask = (((uint)1 << SizeFieldLen) - 1) << SizeFieldPos;
 85 
 86   static uint8_t card_pos_for(uint const idx, uint const bits_per_card) {
 87     return (idx * bits_per_card + HeaderSize);
 88   }
 89 
 90   static CardSetPtr merge(CardSetPtr orig_value, uint card_in_region, uint idx, uint bits_per_card);
 91 
 92   static uint card_at(CardSetPtr value, uint const idx, uint const bits_per_card) {
 93     uint8_t card_pos = card_pos_for(idx, bits_per_card);
 94     uint result = ((uintptr_t)value >> card_pos) & (((uintptr_t)1 << bits_per_card) - 1);
 95     return result;
 96   }
 97 
 98   uint find(uint const card_idx, uint const bits_per_card, uint start_at, uint num_elems);
 99 
100 public:
101   G1CardSetInlinePtr() : _value_addr(nullptr), _value((CardSetPtr)G1CardSet::CardSetInlinePtr) { }
102 
103   G1CardSetInlinePtr(CardSetPtr value) : _value_addr(nullptr), _value(value) {
104     assert(G1CardSet::card_set_type(_value) == G1CardSet::CardSetInlinePtr, "Value " PTR_FORMAT " is not a valid G1CardSetInPtr.", p2i(_value));
105   }
106 
107   G1CardSetInlinePtr(CardSetPtr volatile* value_addr, CardSetPtr value) : _value_addr(value_addr), _value(value) {
108     assert(G1CardSet::card_set_type(_value) == G1CardSet::CardSetInlinePtr, "Value " PTR_FORMAT " is not a valid G1CardSetInPtr.", p2i(_value));
109   }
110 
111   G1AddCardResult add(uint const card_idx, uint const bits_per_card, uint const max_cards_in_inline_ptr);
112 
113   bool contains(uint const card_idx, uint const bits_per_card);
114 
115   template <class CardVisitor>
116   void iterate(CardVisitor& found, uint const bits_per_card);
117 
118   operator CardSetPtr () { return _value; }
119 
120   static uint max_cards_in_inline_ptr(uint bits_per_card) {
121     return (BitsInValue - HeaderSize) / bits_per_card;
122   }
123 
124   static uint num_cards_in(CardSetPtr value) {
125     return ((uintptr_t)value & SizeFieldMask) >> SizeFieldPos;
126   }
127 };
128 
129 
130 // Common base class for card set containers where the memory for the entries is
131 // managed on the (C-)heap. Depending on the current use, one of the two overlapping
132 // members are used:
133 //
134 // While such an object is assigned to a card set container, we utilize the
135 // reference count for memory management.
136 //
137 // In this case the object is one of three states:
138 // 1: Live: The object is visible to other threads, thus can
139 //    safely be accessed by other threads (_ref_count >= 3).
140 // 2: Dead: The object is visible to only a single thread and may be
141 //    safely reclaimed (_ref_count == 1).
142 // 3: Reclaimed: The object's memory has been reclaimed ((_ref_count & 0x1) == 0).
143 // To maintain these constraints, live objects should have ((_ref_count & 0x1) == 1),
144 // which requires that we increment the reference counts by 2 starting at _ref_count = 3.
145 //
146 // When such an object is on a free list, we reuse the same field for linking
147 // together those free objects.
148 //
149 // All but inline pointers are of this kind. For those, card entries are stored
150 // directly in the CardSetPtr of the ConcurrentHashTable node.
151 class G1CardSetContainer {
152 private:
153   union {
154     G1CardSetContainer* _next;
155     uintptr_t _ref_count;
156   };
157 
158 public:
159   G1CardSetContainer() : _ref_count(3) { }
160 
161   uintptr_t refcount() const { return Atomic::load_acquire(&_ref_count); }
162 
163   bool try_increment_refcount();
164 
165   // Decrement refcount potentially while racing increment, so we need
166   // to check the value after attempting to decrement.
167   uintptr_t decrement_refcount();
168 
169   G1CardSetContainer* next() {
170     return _next;
171   }
172 
173   G1CardSetContainer** next_addr() {
174     return &_next;
175   }
176 
177   void set_next(G1CardSetContainer* next) {
178     _next = next;
179   }
180 };
181 
182 class G1CardSetArray : public G1CardSetContainer {
183 public:
184   typedef uint16_t EntryDataType;
185   typedef uint EntryCountType;
186   using CardSetPtr = G1CardSet::CardSetPtr;
187 private:
188   EntryCountType _size;
189   EntryCountType volatile _num_entries;
190   EntryDataType _data[2];
191 
192   static const EntryCountType LockBitMask = (EntryCountType)1 << (sizeof(EntryCountType) * BitsPerByte - 1);
193   static const EntryCountType EntryMask = LockBitMask - 1;
194 
195   class G1CardSetArrayLocker : public StackObj {
196     EntryCountType volatile* _value;
197     EntryCountType volatile _original_value;
198     bool _success;
199   public:
200     G1CardSetArrayLocker(EntryCountType volatile* value);
201 
202     EntryCountType num_entries() const { return _original_value; }
203     void inc_num_entries() { _success = true; }
204 
205     ~G1CardSetArrayLocker() {
206       assert(((_original_value + _success) & EntryMask) == (EntryCountType)(_original_value + _success), "precondition!" );
207 
208       Atomic::release_store(_value, (EntryCountType)(_original_value + _success));
209     }
210   };
211 
212   template<typename Derived>
213   static size_t header_size_in_bytes_internal() {
214     return offset_of(Derived, _data);
215   }
216 
217 public:
218   G1CardSetArray(uint const card_in_region, EntryCountType num_elems);
219 
220   G1AddCardResult add(uint card_idx);
221 
222   bool contains(uint card_idx);
223 
224   template <class CardVisitor>
225   void iterate(CardVisitor& found);
226 
227   size_t num_entries() const { return _num_entries & EntryMask; }
228   size_t max_entries() const { return _size; }
229 
230   static size_t header_size_in_bytes() { return header_size_in_bytes_internal<G1CardSetArray>(); }
231 
232   static size_t size_in_bytes(size_t num_cards) {
233     return header_size_in_bytes() + sizeof(EntryDataType) * num_cards;
234   }
235 };
236 
237 class G1CardSetBitMap : public G1CardSetContainer {
238   size_t _num_bits_set;
239   BitMap::bm_word_t _bits[1];
240 
241   using CardSetPtr = G1CardSet::CardSetPtr;
242 
243   template<typename Derived>
244   static size_t header_size_in_bytes_internal() {
245     return offset_of(Derived, _bits);
246   }
247 
248 public:
249   G1CardSetBitMap(uint const card_in_region, uint const size_in_bits);
250 
251   G1AddCardResult add(uint card_idx, size_t threshold, size_t size_in_bits);
252 
253   bool contains(uint card_idx, size_t size_in_bits) {
254     BitMapView bm(_bits, size_in_bits);
255     return bm.at(card_idx);
256   }
257 
258   uint num_bits_set() const { return (uint)_num_bits_set; }
259 
260   template <class CardVisitor>
261   void iterate(CardVisitor& found, size_t const size_in_bits, uint offset);
262 
263   uint next(uint const idx, size_t const size_in_bits) {
264     BitMapView bm(_bits, size_in_bits);
265     return static_cast<uint>(bm.get_next_one_offset(idx));
266   }
267 
268   static size_t header_size_in_bytes() { return header_size_in_bytes_internal<G1CardSetBitMap>(); }
269 
270   static size_t size_in_bytes(size_t size_in_bits) { return header_size_in_bytes() + BitMap::calc_size_in_words(size_in_bits) * BytesPerWord; }
271 };
272 
273 class G1CardSetHowl : public G1CardSetContainer {
274 public:
275   typedef uint EntryCountType;
276   using CardSetPtr = G1CardSet::CardSetPtr;
277   EntryCountType volatile _num_entries;
278 private:
279   CardSetPtr _buckets[2];
280   // Do not add class member variables beyond this point
281 
282   template<typename Derived>
283   static size_t header_size_in_bytes_internal() {
284     return offset_of(Derived, _buckets);
285   }
286 
287   // Iterates over the given CardSetPtr with at index in this Howl card set,
288   // applying a CardOrRangeVisitor on it.
289   template <class CardOrRangeVisitor>
290   void iterate_cardset(CardSetPtr const card_set, uint index, CardOrRangeVisitor& found, G1CardSetConfiguration* config);
291 
292 public:
293   G1CardSetHowl(EntryCountType card_in_region, G1CardSetConfiguration* config);
294 
295   CardSetPtr* get_card_set_addr(EntryCountType index) {
296     return &_buckets[index];
297   }
298 
299   bool contains(uint card_idx, G1CardSetConfiguration* config);
300 
301   // Iterates over all CardSetPtrs in this Howl card set, applying a CardOrRangeVisitor
302   // on it.
303   template <class CardOrRangeVisitor>
304   void iterate(CardOrRangeVisitor& found, G1CardSetConfiguration* config);
305 
306   // Iterates over all CardSetPtrs in this Howl card set. Calls
307   //
308   //   void operator ()(CardSetPtr* card_set_addr);
309   //
310   // on all of them.
311   template <class CardSetPtrVisitor>
312   void iterate(CardSetPtrVisitor& found, uint num_card_sets);
313 
314   static EntryCountType num_buckets(size_t size_in_bits, size_t num_cards_in_array, size_t max_buckets);
315 
316   static EntryCountType bitmap_size(size_t size_in_bits, uint num_buckets) {
317     EntryCountType num_cards = (EntryCountType)size_in_bits / num_buckets;
318     return round_up_power_of_2(num_cards);
319   }
320 
321   static size_t header_size_in_bytes() { return header_size_in_bytes_internal<G1CardSetHowl>(); }
322 
323   static size_t size_in_bytes(size_t num_arrays) {
324     return header_size_in_bytes() + sizeof(CardSetPtr) * num_arrays;
325   }
326 };
327 
328 #endif // SHARE_GC_G1_G1CARDSETCONTAINERS_HPP