graal-compiler: src/share/vm/gc_implementation/g1/concurrentG1Refine.cpp comparison

comparison src/share/vm/gc_implementation/g1/concurrentG1Refine.cpp @ 890:6cb8e9df7174

6819077: G1: first GC thread coming late into the GC. Summary: The first worker thread is delayed when entering the GC because it clears the card count table that is used in identifying hot cards. Replace the card count table with a dynamically sized evicting hash table that includes an epoch based counter. Reviewed-by: iveresov, tonyp

author	johnc
date	Tue, 04 Aug 2009 16:00:17 -0700
parents	15c5903cf9e1
children	035d2e036a9b

comparison

equal deleted inserted replaced

-:15c5903cf9e1
+:6cb8e9df7174
 */
 #include "incls/_precompiled.incl"
 #include "incls/_concurrentG1Refine.cpp.incl"
+// Possible sizes for the card counts cache: odd primes that roughly double in size.
+// (See jvmtiTagMap.cpp).
+int ConcurrentG1Refine::_cc_cache_sizes[] = {
+16381,    32771,    76831,    150001,   307261,
+614563,  1228891,  2457733,   4915219,  9830479,
+19660831, 39321619, 78643219, 157286461,       -1
+};
 ConcurrentG1Refine::ConcurrentG1Refine() :
-_card_counts(NULL), _cur_card_count_histo(NULL), _cum_card_count_histo(NULL),
+_card_counts(NULL), _card_epochs(NULL),
+_n_card_counts(0), _max_n_card_counts(0),
+_cache_size_index(0), _expand_card_counts(false),
 _hot_cache(NULL),
 _def_use_cache(false), _use_cache(false),
-_n_periods(0), _total_cards(0), _total_travs(0),
+_n_periods(0),
 _threads(NULL), _n_threads(0)
 {
 if (G1ConcRefine) {
 _n_threads = (int)thread_num();
 if (_n_threads > 0) {
 }
 return 0;
 }
 void ConcurrentG1Refine::init() {
-G1CollectedHeap* g1h = G1CollectedHeap::heap();
+if (G1ConcRSLogCacheSize > 0) {
-if (G1ConcRSLogCacheSize > 0 || G1ConcRSCountTraversals) {
+_g1h = G1CollectedHeap::heap();
-_n_card_counts =
+_max_n_card_counts =
-(unsigned) (g1h->g1_reserved_obj_bytes() >> CardTableModRefBS::card_shift);
+(unsigned) (_g1h->g1_reserved_obj_bytes() >> CardTableModRefBS::card_shift);
-_card_counts = NEW_C_HEAP_ARRAY(unsigned char, _n_card_counts);
-for (size_t i = 0; i < _n_card_counts; i++) _card_counts[i] = 0;
+size_t max_card_num = ((size_t)1 << (sizeof(unsigned)*BitsPerByte-1)) - 1;
-ModRefBarrierSet* bs = g1h->mr_bs();
+guarantee(_max_n_card_counts < max_card_num, "card_num representation");
+int desired = _max_n_card_counts / InitialCacheFraction;
+for (_cache_size_index = 0;
+_cc_cache_sizes[_cache_size_index] >= 0; _cache_size_index++) {
+if (_cc_cache_sizes[_cache_size_index] >= desired) break;
+}
+_cache_size_index = MAX2(0, (_cache_size_index - 1));
+int initial_size = _cc_cache_sizes[_cache_size_index];
+if (initial_size < 0) initial_size = _max_n_card_counts;
+// Make sure we don't go bigger than we will ever need
+_n_card_counts = MIN2((unsigned) initial_size, _max_n_card_counts);
+_card_counts = NEW_C_HEAP_ARRAY(CardCountCacheEntry, _n_card_counts);
+_card_epochs = NEW_C_HEAP_ARRAY(CardEpochCacheEntry, _n_card_counts);
+Copy::fill_to_bytes(&_card_counts[0],
+_n_card_counts * sizeof(CardCountCacheEntry));
+Copy::fill_to_bytes(&_card_epochs[0], _n_card_counts * sizeof(CardEpochCacheEntry));
+ModRefBarrierSet* bs = _g1h->mr_bs();
 guarantee(bs->is_a(BarrierSet::CardTableModRef), "Precondition");
-CardTableModRefBS* ctbs = (CardTableModRefBS*)bs;
+_ct_bs = (CardTableModRefBS*)bs;
-_ct_bot = ctbs->byte_for_const(g1h->reserved_region().start());
+_ct_bot = _ct_bs->byte_for_const(_g1h->reserved_region().start());
-if (G1ConcRSCountTraversals) {
-_cur_card_count_histo = NEW_C_HEAP_ARRAY(unsigned, 256);
-_cum_card_count_histo = NEW_C_HEAP_ARRAY(unsigned, 256);
-for (int i = 0; i < 256; i++) {
-_cur_card_count_histo[i] = 0;
-_cum_card_count_histo[i] = 0;
-}
-}
-}
-if (G1ConcRSLogCacheSize > 0) {
 _def_use_cache = true;
 _use_cache = true;
 _hot_cache_size = (1 << G1ConcRSLogCacheSize);
 _hot_cache = NEW_C_HEAP_ARRAY(jbyte*, _hot_cache_size);
 _n_hot = 0;
 _hot_cache_idx = 0;
 // For refining the cards in the hot cache in parallel
 int n_workers = (ParallelGCThreads > 0 ?
-g1h->workers()->total_workers() : 1);
+_g1h->workers()->total_workers() : 1);
 _hot_cache_par_chunk_size = MAX2(1, _hot_cache_size / n_workers);
 _hot_cache_par_claimed_idx = 0;
 }
 }
 }
 }
 }
 ConcurrentG1Refine::~ConcurrentG1Refine() {
-if (G1ConcRSLogCacheSize > 0 || G1ConcRSCountTraversals) {
+if (G1ConcRSLogCacheSize > 0) {
 assert(_card_counts != NULL, "Logic");
-FREE_C_HEAP_ARRAY(unsigned char, _card_counts);
+FREE_C_HEAP_ARRAY(CardCountCacheEntry, _card_counts);
-assert(_cur_card_count_histo != NULL, "Logic");
+assert(_card_epochs != NULL, "Logic");
-FREE_C_HEAP_ARRAY(unsigned, _cur_card_count_histo);
+FREE_C_HEAP_ARRAY(CardEpochCacheEntry, _card_epochs);
-assert(_cum_card_count_histo != NULL, "Logic");
-FREE_C_HEAP_ARRAY(unsigned, _cum_card_count_histo);
-}
-if (G1ConcRSLogCacheSize > 0) {
 assert(_hot_cache != NULL, "Logic");
 FREE_C_HEAP_ARRAY(jbyte*, _hot_cache);
 }
 if (_threads != NULL) {
 for (int i = 0; i < _n_threads; i++) {
 tc->do_thread(_threads[i]);
 }
 }
 }
+bool ConcurrentG1Refine::is_young_card(jbyte* card_ptr) {
-int ConcurrentG1Refine::add_card_count(jbyte* card_ptr) {
+HeapWord* start = _ct_bs->addr_for(card_ptr);
-size_t card_num = (card_ptr - _ct_bot);
+HeapRegion* r = _g1h->heap_region_containing(start);
-guarantee(0 <= card_num && card_num < _n_card_counts, "Bounds");
+if (r != NULL && r->is_young()) {
-unsigned char cnt = _card_counts[card_num];
+return true;
-if (cnt < 255) _card_counts[card_num]++;
+}
-return cnt;
+// This card is not associated with a heap region
-_total_travs++;
+// so can't be young.
-}
+return false;
+}
-jbyte* ConcurrentG1Refine::cache_insert(jbyte* card_ptr) {
-int count = add_card_count(card_ptr);
+jbyte* ConcurrentG1Refine::add_card_count(jbyte* card_ptr, int* count, bool* defer) {
-// Count previously unvisited cards.
+unsigned new_card_num = ptr_2_card_num(card_ptr);
-if (count == 0) _total_cards++;
+unsigned bucket = hash(new_card_num);
-// We'll assume a traversal unless we store it in the cache.
+assert(0 <= bucket && bucket < _n_card_counts, "Bounds");
+CardCountCacheEntry* count_ptr = &_card_counts[bucket];
+CardEpochCacheEntry* epoch_ptr = &_card_epochs[bucket];
+// We have to construct a new entry if we haven't updated the counts
+// during the current period, or if the count was updated for a
+// different card number.
+unsigned int new_epoch = (unsigned int) _n_periods;
+julong new_epoch_entry = make_epoch_entry(new_card_num, new_epoch);
+while (true) {
+// Fetch the previous epoch value
+julong prev_epoch_entry = epoch_ptr->_value;
+julong cas_res;
+if (extract_epoch(prev_epoch_entry) != new_epoch) {
+// This entry has not yet been updated during this period.
+// Note: we update the epoch value atomically to ensure
+// that there is only one winner that updates the cached
+// card_ptr value even though all the refine threads share
+// the same epoch value.
+cas_res = (julong) Atomic::cmpxchg((jlong) new_epoch_entry,
+(volatile jlong*)&epoch_ptr->_value,
+(jlong) prev_epoch_entry);
+if (cas_res == prev_epoch_entry) {
+// We have successfully won the race to update the
+// epoch and card_num value. Make it look like the
+// count and eviction count were previously cleared.
+count_ptr->_count = 1;
+count_ptr->_evict_count = 0;
+*count = 0;
+// We can defer the processing of card_ptr
+*defer = true;
+return card_ptr;
+}
+// We did not win the race to update the epoch field, so some other
+// thread must have done it. The value that gets returned by CAS
+// should be the new epoch value.
+assert(extract_epoch(cas_res) == new_epoch, "unexpected epoch");
+// We could 'continue' here or just re-read the previous epoch value
+prev_epoch_entry = epoch_ptr->_value;
+}
+// The epoch entry for card_ptr has been updated during this period.
+unsigned old_card_num = extract_card_num(prev_epoch_entry);
+// The card count that will be returned to caller
+*count = count_ptr->_count;
+// Are we updating the count for the same card?
+if (new_card_num == old_card_num) {
+// Same card - just update the count. We could have more than one
+// thread racing to update count for the current card. It should be
+// OK not to use a CAS as the only penalty should be some missed
+// increments of the count which delays identifying the card as "hot".
+if (*count < max_jubyte) count_ptr->_count++;
+// We can defer the processing of card_ptr
+*defer = true;
+return card_ptr;
+}
+// Different card - evict old card info
+if (count_ptr->_evict_count < max_jubyte) count_ptr->_evict_count++;
+if (count_ptr->_evict_count > G1CardCountCacheExpandThreshold) {
+// Trigger a resize the next time we clear
+_expand_card_counts = true;
+}
+cas_res = (julong) Atomic::cmpxchg((jlong) new_epoch_entry,
+(volatile jlong*)&epoch_ptr->_value,
+(jlong) prev_epoch_entry);
+if (cas_res == prev_epoch_entry) {
+// We successfully updated the card num value in the epoch entry
+count_ptr->_count = 0; // initialize counter for new card num
+// Even though the region containg the card at old_card_num was not
+// in the young list when old_card_num was recorded in the epoch
+// cache it could have been added to the free list and subsequently
+// added to the young list in the intervening time. If the evicted
+// card is in a young region just return the card_ptr and the evicted
+// card will not be cleaned. See CR 6817995.
+jbyte* old_card_ptr = card_num_2_ptr(old_card_num);
+if (is_young_card(old_card_ptr)) {
+*count = 0;
+// We can defer the processing of card_ptr
+*defer = true;
+return card_ptr;
+}
+// We do not want to defer processing of card_ptr in this case
+// (we need to refine old_card_ptr and card_ptr)
+*defer = false;
+return old_card_ptr;
+}
+// Someone else beat us - try again.
+}
+}
+jbyte* ConcurrentG1Refine::cache_insert(jbyte* card_ptr, bool* defer) {
+int count;
+jbyte* cached_ptr = add_card_count(card_ptr, &count, defer);
+assert(cached_ptr != NULL, "bad cached card ptr");
+assert(!is_young_card(cached_ptr), "shouldn't get a card in young region");
+// The card pointer we obtained from card count cache is not hot
+// so do not store it in the cache; return it for immediate
+// refining.
 if (count < G1ConcRSHotCardLimit) {
-_total_travs++;
+return cached_ptr;
-return card_ptr;
+}
-}
-// Otherwise, it's hot.
+// Otherwise, the pointer we got from the _card_counts is hot.
 jbyte* res = NULL;
 MutexLockerEx x(HotCardCache_lock, Mutex::_no_safepoint_check_flag);
 if (_n_hot == _hot_cache_size) {
-_total_travs++;
 res = _hot_cache[_hot_cache_idx];
 _n_hot--;
 }
 // Now _n_hot < _hot_cache_size, and we can insert at _hot_cache_idx.
-_hot_cache[_hot_cache_idx] = card_ptr;
+_hot_cache[_hot_cache_idx] = cached_ptr;
 _hot_cache_idx++;
 if (_hot_cache_idx == _hot_cache_size) _hot_cache_idx = 0;
 _n_hot++;
+if (res != NULL) {
+// Even though the region containg res was not in the young list
+// when it was recorded in the hot cache it could have been added
+// to the free list and subsequently added to the young list in
+// the intervening time. If res is in a young region, return NULL
+// so that res is not cleaned. See CR 6817995.
+if (is_young_card(res)) {
+res = NULL;
+}
+}
 return res;
 }
 void ConcurrentG1Refine::clean_up_cache(int worker_i, G1RemSet* g1rs) {
 assert(!use_cache(), "cache should be disabled");
 int start_idx;
 }
 }
 }
 }
+void ConcurrentG1Refine::expand_card_count_cache() {
+if (_n_card_counts < _max_n_card_counts) {
+int new_idx = _cache_size_index+1;
+int new_size = _cc_cache_sizes[new_idx];
+if (new_size < 0) new_size = _max_n_card_counts;
+// Make sure we don't go bigger than we will ever need
+new_size = MIN2((unsigned) new_size, _max_n_card_counts);
+// Expand the card count and card epoch tables
+if (new_size > (int)_n_card_counts) {
+// We can just free and allocate a new array as we're
+// not interested in preserving the contents
+assert(_card_counts != NULL, "Logic!");
+assert(_card_epochs != NULL, "Logic!");
+FREE_C_HEAP_ARRAY(CardCountCacheEntry, _card_counts);
+FREE_C_HEAP_ARRAY(CardEpochCacheEntry, _card_epochs);
+_n_card_counts = new_size;
+_card_counts = NEW_C_HEAP_ARRAY(CardCountCacheEntry, _n_card_counts);
+_card_epochs = NEW_C_HEAP_ARRAY(CardEpochCacheEntry, _n_card_counts);
+_cache_size_index = new_idx;
+}
+}
+}
 void ConcurrentG1Refine::clear_and_record_card_counts() {
-if (G1ConcRSLogCacheSize == 0 && !G1ConcRSCountTraversals) return;
+if (G1ConcRSLogCacheSize == 0) return;
+#ifndef PRODUCT
+double start = os::elapsedTime();
+#endif
+if (_expand_card_counts) {
+expand_card_count_cache();
+_expand_card_counts = false;
+// Only need to clear the epochs.
+Copy::fill_to_bytes(&_card_epochs[0], _n_card_counts * sizeof(CardEpochCacheEntry));
+}
+int this_epoch = (int) _n_periods;
+assert((this_epoch+1) <= max_jint, "to many periods");
+// Update epoch
 _n_periods++;
-if (G1ConcRSCountTraversals) {
-for (size_t i = 0; i < _n_card_counts; i++) {
+#ifndef PRODUCT
-unsigned char bucket = _card_counts[i];
+double elapsed = os::elapsedTime() - start;
-_cur_card_count_histo[bucket]++;
+_g1h->g1_policy()->record_cc_clear_time(elapsed * 1000.0);
-_card_counts[i] = 0;
+#endif
 }
-gclog_or_tty->print_cr("Card counts:");
-for (int i = 0; i < 256; i++) {
-if (_cur_card_count_histo[i] > 0) {
-gclog_or_tty->print_cr("  %3d: %9d", i, _cur_card_count_histo[i]);
-_cum_card_count_histo[i] += _cur_card_count_histo[i];
-_cur_card_count_histo[i] = 0;
-}
-}
-} else {
-assert(G1ConcRSLogCacheSize > 0, "Logic");
-Copy::fill_to_words((HeapWord*)(&_card_counts[0]),
-_n_card_counts / HeapWordSize);
-}
-}
-void
-ConcurrentG1Refine::
-print_card_count_histo_range(unsigned* histo, int from, int to,
-float& cum_card_pct,
-float& cum_travs_pct) {
-unsigned cards = 0;
-unsigned travs = 0;
-guarantee(to <= 256, "Precondition");
-for (int i = from; i < to-1; i++) {
-cards += histo[i];
-travs += histo[i] * i;
-}
-if (to == 256) {
-unsigned histo_card_sum = 0;
-unsigned histo_trav_sum = 0;
-for (int i = 1; i < 255; i++) {
-histo_trav_sum += histo[i] * i;
-}
-cards += histo[255];
-// correct traversals for the last one.
-unsigned travs_255 = (unsigned) (_total_travs - histo_trav_sum);
-travs += travs_255;
-} else {
-cards += histo[to-1];
-travs += histo[to-1] * (to-1);
-}
-float fperiods = (float)_n_periods;
-float f_tot_cards = (float)_total_cards/fperiods;
-float f_tot_travs = (float)_total_travs/fperiods;
-if (cards > 0) {
-float fcards = (float)cards/fperiods;
-float ftravs = (float)travs/fperiods;
-if (to == 256) {
-gclog_or_tty->print(" %4d-       %10.2f%10.2f", from, fcards, ftravs);
-} else {
-gclog_or_tty->print(" %4d-%4d   %10.2f%10.2f", from, to-1, fcards, ftravs);
-}
-float pct_cards = fcards*100.0/f_tot_cards;
-cum_card_pct += pct_cards;
-float pct_travs = ftravs*100.0/f_tot_travs;
-cum_travs_pct += pct_travs;
-gclog_or_tty->print_cr("%10.2f%10.2f%10.2f%10.2f",
-pct_cards, cum_card_pct,
-pct_travs, cum_travs_pct);
-}
-}
-void ConcurrentG1Refine::print_final_card_counts() {
-if (!G1ConcRSCountTraversals) return;
-gclog_or_tty->print_cr("Did %d total traversals of %d distinct cards.",
-_total_travs, _total_cards);
-float fperiods = (float)_n_periods;
-gclog_or_tty->print_cr("  This is an average of %8.2f traversals, %8.2f cards, "
-"per collection.", (float)_total_travs/fperiods,
-(float)_total_cards/fperiods);
-gclog_or_tty->print_cr("  This is an average of %8.2f traversals/distinct "
-"dirty card.\n",
-_total_cards > 0 ?
-(float)_total_travs/(float)_total_cards : 0.0);
-gclog_or_tty->print_cr("Histogram:\n\n%10s   %10s%10s%10s%10s%10s%10s",
-"range", "# cards", "# travs", "% cards", "(cum)",
-"% travs", "(cum)");
-gclog_or_tty->print_cr("------------------------------------------------------------"
-"-------------");
-float cum_cards_pct = 0.0;
-float cum_travs_pct = 0.0;
-for (int i = 1; i < 10; i++) {
-print_card_count_histo_range(_cum_card_count_histo, i, i+1,
-cum_cards_pct, cum_travs_pct);
-}
-for (int i = 10; i < 100; i += 10) {
-print_card_count_histo_range(_cum_card_count_histo, i, i+10,
-cum_cards_pct, cum_travs_pct);
-}
-print_card_count_histo_range(_cum_card_count_histo, 100, 150,
-cum_cards_pct, cum_travs_pct);
-print_card_count_histo_range(_cum_card_count_histo, 150, 200,
-cum_cards_pct, cum_travs_pct);
-print_card_count_histo_range(_cum_card_count_histo, 150, 255,
-cum_cards_pct, cum_travs_pct);
-print_card_count_histo_range(_cum_card_count_histo, 255, 256,
-cum_cards_pct, cum_travs_pct);
-}

Mercurial > hg > graal-compiler

comparison src/share/vm/gc_implementation/g1/concurrentG1Refine.cpp @ 890:6cb8e9df7174