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