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/globalDefinitions.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_cards = num_cards_in(_value);
 54     if (num_cards > 0) {
 55       cur_idx = find(card_idx, bits_per_card, cur_idx, num_cards);
 56     }
 57     // Check if the card is already stored in the pointer.
 58     if (cur_idx < num_cards) {
 59       return Found;
 60     }
 61     // Check if there is actually enough space.
 62     if (num_cards >= max_cards_in_inline_ptr) {
 63       return Overflow;
 64     }
 65     CardSetPtr new_value = merge(_value, card_idx, num_cards, 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_cards) {
 81   assert(start_at < num_cards, "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_cards; cur_idx++) {
 88     if ((value & card_mask) == card_idx) {
 89       return cur_idx;
 90     }
 91     value >>= bits_per_card;
 92   }
 93   return num_cards;
 94 }
 95 
 96 inline bool G1CardSetInlinePtr::contains(uint card_idx, uint bits_per_card) {
 97   uint num_cards = num_cards_in(_value);
 98   if (num_cards == 0) {
 99     return false;
100   }
101   uint cur_idx = find(card_idx, bits_per_card, 0, num_cards);
102   return cur_idx < num_cards;
103 }
104 
105 template <class CardVisitor>
106 inline void G1CardSetInlinePtr::iterate(CardVisitor& found, uint bits_per_card) {
107   uint const num_cards = 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_cards; 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_cards) :
140   G1CardSetContainer(),
141   _size(num_cards),
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* num_entries_addr) :
149   _num_entries_addr(num_entries_addr) {
150   SpinYield s;
151   EntryCountType num_entries = Atomic::load(_num_entries_addr) & EntryMask;
152   while (true) {
153     EntryCountType old_value = Atomic::cmpxchg(_num_entries_addr,
154                                                num_entries,
155                                                (EntryCountType)(num_entries | LockBitMask));
156     if (old_value == num_entries) {
157       // Succeeded locking the array.
158       _local_num_entries = num_entries;
159       break;
160     }
161     // Failed. Retry (with the lock bit stripped again).
162     num_entries = 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 allowed card value range.", 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 cards 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->max_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->max_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->max_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_max_cards_in_howl_bitmap();
325         G1CardSet::card_set_ptr<G1CardSetBitMap>(card_set)->iterate(found, config->max_cards_in_howl_bitmap(), offset);
326       }
327       return;
328     }
329     case G1CardSet::CardSetHowl: { // actually FullCardSet
330       assert(card_set == G1CardSet::FullCardSet, "Must be");
331       if (found.start_iterate(G1GCPhaseTimes::MergeRSHowlFull)) {
332         uint offset = index << config->log2_max_cards_in_howl_bitmap();
333         found(offset, config->max_cards_in_howl_bitmap());
334       }
335       return;
336     }
337   }
338 }
339 
340 inline G1CardSetHowl::EntryCountType G1CardSetHowl::num_buckets(size_t size_in_bits, size_t max_cards_in_array, size_t max_num_buckets) {
341   size_t size_bitmap_bytes = BitMap::calc_size_in_words(size_in_bits) * BytesPerWord;
342   // Ensure that in the worst case arrays consume half the memory size
343   // of storing the entire bitmap
344   size_t max_size_arrays_bytes = size_bitmap_bytes / 2;
345   size_t size_array_bytes = max_cards_in_array * sizeof(G1CardSetArray::EntryDataType);
346   size_t num_arrays = max_size_arrays_bytes / size_array_bytes;
347   // We use shifts and masks for indexing the array. So round down to the next
348   // power of two to not use more than expected memory.
349   num_arrays = round_down_power_of_2(MAX2((size_t)1, MIN2(num_arrays, max_num_buckets)));
350   return (EntryCountType)num_arrays;
351 }
352 
353 #endif // SHARE_GC_G1_G1CARDSETCONTAINERS_INLINE_HPP