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_INLINE_HPP
 26 #define SHARE_GC_G1_G1CARDSETCONTAINERS_INLINE_HPP
 27 
 28 #include "gc/g1/g1CardSetContainers.hpp"
 29 #include "gc/g1/g1GCPhaseTimes.hpp"
 30 #include "utilities/bitMap.inline.hpp"
 31 
 32 inline G1CardSetInlinePtr::CardSetPtr G1CardSetInlinePtr::merge(CardSetPtr orig_value, uint card_in_region, uint idx, uint bits_per_card) {
 33   assert((idx & (SizeFieldMask >> SizeFieldPos)) == idx, "Index %u too large to fit into size field", idx);
 34   assert(card_in_region < ((uint)1 << bits_per_card), "Card %u too large to fit into card value field", card_in_region);
 35 
 36   uint8_t card_pos = card_pos_for(idx, bits_per_card);
 37   assert(card_pos + bits_per_card < BitsInValue, "Putting card at pos %u with %u bits would extend beyond pointer", card_pos, bits_per_card);
 38 
 39   // Check that we do not touch any fields we do not own.
 40   uintptr_t mask = ((((uintptr_t)1 << bits_per_card) - 1) << card_pos);
 41   assert(((uintptr_t)orig_value & mask) == 0, "The bits in the new range should be empty; orig_value " PTR_FORMAT " mask " PTR_FORMAT, p2i(orig_value), mask);
 42 
 43   uintptr_t value = ((uintptr_t)(idx + 1) << SizeFieldPos) | ((uintptr_t)card_in_region << card_pos);
 44   uintptr_t res = (((uintptr_t)orig_value & ~SizeFieldMask) | value);
 45   return (CardSetPtr)res;
 46 }
 47 
 48 inline G1AddCardResult G1CardSetInlinePtr::add(uint card_idx, uint bits_per_card, uint max_cards_in_inline_ptr) {
 49   assert(_value_addr != nullptr, "No value address available, cannot add to set.");
 50 
 51   uint cur_idx = 0;
 52   while (true) {
 53     uint num_elems = num_cards_in(_value);
 54     if (num_elems > 0) {
 55       cur_idx = find(card_idx, bits_per_card, cur_idx, num_elems);
 56     }
 57     // Check if the card is already stored in the pointer.
 58     if (cur_idx < num_elems) {
 59       return Found;
 60     }
 61     // Check if there is actually enough space.
 62     if (num_elems >= max_cards_in_inline_ptr) {
 63       return Overflow;
 64     }
 65     CardSetPtr new_value = merge(_value, card_idx, num_elems, bits_per_card);
 66     CardSetPtr old_value = Atomic::cmpxchg(_value_addr, _value, new_value, memory_order_relaxed);
 67     if (_value == old_value) {
 68       return Added;
 69     }
 70     // Update values and retry.
 71     _value = old_value;
 72     // The value of the pointer may have changed to something different than
 73     // an inline card set. Exit then instead of overwriting.
 74     if (G1CardSet::card_set_type(_value) != G1CardSet::CardSetInlinePtr) {
 75       return Overflow;
 76     }
 77   }
 78 }
 79 
 80 inline uint G1CardSetInlinePtr::find(uint card_idx, uint bits_per_card, uint start_at, uint num_elems) {
 81   assert(start_at < num_elems, "Precondition!");
 82 
 83   uintptr_t const card_mask = (1 << bits_per_card) - 1;
 84   uintptr_t value = ((uintptr_t)_value) >> card_pos_for(start_at, bits_per_card);
 85 
 86   // Check if the card is already stored in the pointer.
 87   for (uint cur_idx = start_at; cur_idx < num_elems; cur_idx++) {
 88     if ((value & card_mask) == card_idx) {
 89       return cur_idx;
 90     }
 91     value >>= bits_per_card;
 92   }
 93   return num_elems;
 94 }
 95 
 96 inline bool G1CardSetInlinePtr::contains(uint card_idx, uint bits_per_card) {
 97   uint num_elems = num_cards_in(_value);
 98   if (num_elems == 0) {
 99     return false;
100   }
101   uint cur_idx = find(card_idx, bits_per_card, 0, num_elems);
102   return cur_idx < num_elems;
103 }
104 
105 template <class CardVisitor>
106 inline void G1CardSetInlinePtr::iterate(CardVisitor& found, uint bits_per_card) {
107   uint const num_elems = num_cards_in(_value);
108   uintptr_t const card_mask = (1 << bits_per_card) - 1;
109 
110   uintptr_t value = ((uintptr_t)_value) >> card_pos_for(0, bits_per_card);
111   for (uint cur_idx = 0; cur_idx < num_elems; cur_idx++) {
112     found(value & card_mask);
113     value >>= bits_per_card;
114   }
115 }
116 
117 inline bool G1CardSetContainer::try_increment_refcount() {
118   uintptr_t old_value = refcount();
119   while (true) {
120     if (old_value < 3 || (old_value & 0x1) == 0) {  // reclaimed,  reference counts are odd numbers starting at 3
121       return false; // dead, can't revive.
122     }
123 
124     uintptr_t new_value = old_value + 2;
125     uintptr_t ref_count = Atomic::cmpxchg(&_ref_count, old_value, new_value);
126     if (ref_count == old_value) {
127       return true;
128     }
129     old_value = ref_count;
130   }
131 }
132 
133 inline uintptr_t G1CardSetContainer::decrement_refcount() {
134   uintptr_t old_value = refcount();
135   assert((old_value & 0x1) != 0 && old_value >= 3, "precondition");
136   return Atomic::sub(&_ref_count, 2u);
137 }
138 
139 inline G1CardSetArray::G1CardSetArray(uint card_in_region, EntryCountType num_elems) :
140   G1CardSetContainer(),
141   _size(num_elems),
142   _num_entries(1) {
143   assert(_size > 0, "CardSetArray of size 0 not supported.");
144   assert(_size < LockBitMask, "Only support CardSetArray of size %u or smaller.", LockBitMask - 1);
145   _data[0] = card_in_region;
146 }
147 
148 inline G1CardSetArray::G1CardSetArrayLocker::G1CardSetArrayLocker(EntryCountType volatile* value) :
149   _value(value),
150   _success(false) {
151   SpinYield s;
152   EntryCountType original_value = (*_value) & EntryMask;
153   while (true) {
154     EntryCountType old_value = Atomic::cmpxchg(_value,
155                                                original_value,
156                                                (EntryCountType)(original_value | LockBitMask));
157     if (old_value == original_value) {
158       // Succeeded locking the array.
159       _original_value = original_value;
160       break;
161     }
162     // Failed. Retry (with the lock bit stripped again).
163     original_value = old_value & EntryMask;
164     s.wait();
165   }
166 }
167 
168 inline G1AddCardResult G1CardSetArray::add(uint card_idx) {
169   assert(card_idx < (1u << (sizeof(_data[0]) * BitsPerByte)),
170          "Card index %u does not fit card element.", card_idx);
171   EntryCountType num_entries = Atomic::load_acquire(&_num_entries) & EntryMask;
172   EntryCountType idx = 0;
173   for (; idx < num_entries; idx++) {
174     if (_data[idx] == card_idx) {
175       return Found;
176     }
177   }
178 
179   // Since we did not find the card, lock.
180   G1CardSetArrayLocker x(&_num_entries);
181 
182   // Reload number of entries from the G1CardSetArrayLocker as it might have changed.
183   // It already read the actual value with the necessary synchronization.
184   num_entries = x.num_entries();
185   // Look if the elements added while waiting for the lock are the same as our card.
186   for (; idx < num_entries; idx++) {
187     if (_data[idx] == card_idx) {
188       return Found;
189     }
190   }
191 
192   // Check if there is space left.
193   if (num_entries == _size) {
194     return Overflow;
195   }
196 
197   _data[num_entries] = card_idx;
198 
199   x.inc_num_entries();
200 
201   return Added;
202 }
203 
204 inline bool G1CardSetArray::contains(uint card_idx) {
205   EntryCountType num_entries = Atomic::load_acquire(&_num_entries) & EntryMask;
206 
207   for (EntryCountType idx = 0; idx < num_entries; idx++) {
208     if (_data[idx] == card_idx) {
209       return true;
210     }
211   }
212   return false;
213 }
214 
215 template <class CardVisitor>
216 void G1CardSetArray::iterate(CardVisitor& found) {
217   EntryCountType num_entries = Atomic::load_acquire(&_num_entries) & EntryMask;
218   for (EntryCountType idx = 0; idx < num_entries; idx++) {
219     found(_data[idx]);
220   }
221 }
222 
223 inline G1CardSetBitMap::G1CardSetBitMap(uint card_in_region, uint size_in_bits) :
224   G1CardSetContainer(), _num_bits_set(1) {
225   assert(size_in_bits % (sizeof(_bits[0]) * BitsPerByte) == 0,
226          "Size %u should be aligned to bitmap word size.", size_in_bits);
227   BitMapView bm(_bits, size_in_bits);
228   bm.clear();
229   bm.set_bit(card_in_region);
230 }
231 
232 inline G1AddCardResult G1CardSetBitMap::add(uint card_idx, size_t threshold, size_t size_in_bits) {
233   BitMapView bm(_bits, size_in_bits);
234   if (_num_bits_set >= threshold) {
235     return bm.at(card_idx) ? Found : Overflow;
236   }
237   if (bm.par_set_bit(card_idx)) {
238     Atomic::inc(&_num_bits_set, memory_order_relaxed);
239     return Added;
240   }
241   return Found;
242 }
243 
244 template <class CardVisitor>
245 inline void G1CardSetBitMap::iterate(CardVisitor& found, size_t size_in_bits, uint offset) {
246   BitMapView bm(_bits, size_in_bits);
247   BitMap::idx_t idx = bm.get_next_one_offset(0);
248   while (idx != size_in_bits) {
249     found((offset | (uint)idx));
250     idx = bm.get_next_one_offset(idx + 1);
251   }
252 }
253 
254 inline G1CardSetHowl::G1CardSetHowl(EntryCountType card_in_region, G1CardSetConfiguration* config) :
255   G1CardSetContainer(),
256   _num_entries((config->num_cards_in_array() + 1)) /* Card Transfer will not increment _num_entries */ {
257   EntryCountType num_buckets = config->num_buckets_in_howl();
258   EntryCountType bucket = config->howl_bucket_index(card_in_region);
259   for (uint i = 0; i < num_buckets; ++i) {
260     _buckets[i] = G1CardSetInlinePtr();
261     if (i == bucket) {
262       G1CardSetInlinePtr value(&_buckets[i], _buckets[i]);
263       value.add(card_in_region, config->inline_ptr_bits_per_card(), config->num_cards_in_inline_ptr());
264     }
265   }
266 }
267 
268 inline bool G1CardSetHowl::contains(uint card_idx, G1CardSetConfiguration* config) {
269   EntryCountType bucket = config->howl_bucket_index(card_idx);
270   CardSetPtr* array_entry = get_card_set_addr(bucket);
271   CardSetPtr card_set = Atomic::load_acquire(array_entry);
272 
273   switch (G1CardSet::card_set_type(card_set)) {
274     case G1CardSet::CardSetArrayOfCards : {
275       return G1CardSet::card_set_ptr<G1CardSetArray>(card_set)->contains(card_idx);
276     }
277     case G1CardSet::CardSetBitMap: {
278       uint card_offset = config->howl_bitmap_offset(card_idx);
279       return G1CardSet::card_set_ptr<G1CardSetBitMap>(card_set)->contains(card_offset, config->num_cards_in_howl_bitmap());
280     }
281     case G1CardSet::CardSetInlinePtr: {
282       G1CardSetInlinePtr ptr(card_set);
283       return ptr.contains(card_idx, config->inline_ptr_bits_per_card());
284     }
285     case G1CardSet::CardSetHowl: {// Fullcard set entry
286       assert(card_set == G1CardSet::FullCardSet, "Must be");
287       return true;
288     }
289   }
290   return false;
291 }
292 
293 template <class CardOrRangeVisitor>
294 inline void G1CardSetHowl::iterate(CardOrRangeVisitor& found, G1CardSetConfiguration* config) {
295   for (uint i = 0; i < config->num_buckets_in_howl(); ++i) {
296     iterate_cardset(_buckets[i], i, found, config);
297   }
298 }
299 
300 template <class CardSetPtrVisitor>
301 inline void G1CardSetHowl::iterate(CardSetPtrVisitor& found, uint num_card_sets) {
302   for (uint i = 0; i < num_card_sets; ++i) {
303     found(&_buckets[i]);
304   }
305 }
306 
307 template <class CardOrRangeVisitor>
308 inline void G1CardSetHowl::iterate_cardset(CardSetPtr const card_set, uint index, CardOrRangeVisitor& found, G1CardSetConfiguration* config) {
309   switch (G1CardSet::card_set_type(card_set)) {
310     case G1CardSet::CardSetInlinePtr: {
311       if (found.start_iterate(G1GCPhaseTimes::MergeRSHowlInline)) {
312         G1CardSetInlinePtr ptr(card_set);
313         ptr.iterate(found, config->inline_ptr_bits_per_card());
314       }
315       return;
316     }
317     case G1CardSet::CardSetArrayOfCards : {
318       if (found.start_iterate(G1GCPhaseTimes::MergeRSHowlArrayOfCards)) {
319         G1CardSet::card_set_ptr<G1CardSetArray>(card_set)->iterate(found);
320       }
321       return;
322     }
323     case G1CardSet::CardSetBitMap: {
324       if (found.start_iterate(G1GCPhaseTimes::MergeRSHowlBitmap)) {
325         uint offset = index << config->log2_num_cards_in_howl_bitmap();
326         G1CardSet::card_set_ptr<G1CardSetBitMap>(card_set)->iterate(found, config->num_cards_in_howl_bitmap(), offset);
327       }
328       return;
329     }
330     case G1CardSet::CardSetHowl: { // actually FullCardSet
331       if (found.start_iterate(G1GCPhaseTimes::MergeRSHowlFull)) {
332         assert(card_set == G1CardSet::FullCardSet, "Must be");
333         uint offset = index << config->log2_num_cards_in_howl_bitmap();
334         for (uint i = 0; i < config->max_cards_in_region(); i++) {
335           found((offset | (uint)i));
336         }
337       }
338       return;
339     }
340   }
341 }
342 
343 inline G1CardSetHowl::EntryCountType G1CardSetHowl::num_buckets(size_t size_in_bits, size_t num_cards_in_array, size_t max_num_buckets) {
344   size_t size_bitmap_bytes = BitMap::calc_size_in_words(size_in_bits) * BytesPerWord;
345   // Ensure that in the worst case arrays consume half the memory size
346   // of storing the entire bitmap
347   size_t max_size_arrays_bytes = size_bitmap_bytes / 2;
348   size_t size_array_bytes = num_cards_in_array * sizeof(G1CardSetArray::EntryDataType);
349   size_t num_arrays = max_size_arrays_bytes / size_array_bytes;
350   // We use shifts and masks for indexing the array. So round down to the next
351   // power of two to not use more than expected memory.
352   num_arrays = round_down_power_of_2(MAX2((size_t)1, MIN2(num_arrays, max_num_buckets)));
353   return (EntryCountType)num_arrays;
354 }
355 
356 #endif // SHARE_GC_G1_G1CARDSETCONTAINERS_INLINE_HPP