1 /*
  2  * Copyright Amazon.com Inc. 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 #include "precompiled.hpp"
 26 
 27 #include "gc/shenandoah/mode/shenandoahGenerationalMode.hpp"
 28 #include "gc/shenandoah/shenandoahAgeCensus.hpp"
 29 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
 30 
 31 ShenandoahAgeCensus::ShenandoahAgeCensus() {
 32   assert(ShenandoahHeap::heap()->mode()->is_generational(), "Only in generational mode");
 33   if (ShenandoahGenerationalMinTenuringAge > ShenandoahGenerationalMaxTenuringAge) {
 34     vm_exit_during_initialization(
 35       err_msg("ShenandoahGenerationalMinTenuringAge=" SIZE_FORMAT
 36               " should be no more than ShenandoahGenerationalMaxTenuringAge=" SIZE_FORMAT,
 37               ShenandoahGenerationalMinTenuringAge, ShenandoahGenerationalMaxTenuringAge));
 38   }
 39 
 40   _global_age_table = NEW_C_HEAP_ARRAY(AgeTable*, MAX_SNAPSHOTS, mtGC);
 41   CENSUS_NOISE(_global_noise = NEW_C_HEAP_ARRAY(ShenandoahNoiseStats, MAX_SNAPSHOTS, mtGC);)
 42   _tenuring_threshold = NEW_C_HEAP_ARRAY(uint, MAX_SNAPSHOTS, mtGC);
 43 
 44   for (int i = 0; i < MAX_SNAPSHOTS; i++) {
 45     // Note that we don't now get perfdata from age_table
 46     _global_age_table[i] = new AgeTable(false);
 47     CENSUS_NOISE(_global_noise[i].clear();)
 48     // Sentinel value
 49     _tenuring_threshold[i] = MAX_COHORTS;
 50   }
 51   if (ShenandoahGenerationalAdaptiveTenuring && !ShenandoahGenerationalCensusAtEvac) {
 52     size_t max_workers = ShenandoahHeap::heap()->max_workers();
 53     _local_age_table = NEW_C_HEAP_ARRAY(AgeTable*, max_workers, mtGC);
 54     CENSUS_NOISE(_local_noise = NEW_C_HEAP_ARRAY(ShenandoahNoiseStats, max_workers, mtGC);)
 55     for (uint i = 0; i < max_workers; i++) {
 56       _local_age_table[i] = new AgeTable(false);
 57       CENSUS_NOISE(_local_noise[i].clear();)
 58     }
 59   } else {
 60     _local_age_table = nullptr;
 61   }
 62   _epoch = MAX_SNAPSHOTS - 1;  // see update_epoch()
 63 }
 64 
 65 CENSUS_NOISE(void ShenandoahAgeCensus::add(uint obj_age, uint region_age, uint region_youth, size_t size, uint worker_id) {)
 66 NO_CENSUS_NOISE(void ShenandoahAgeCensus::add(uint obj_age, uint region_age, size_t size, uint worker_id) {)
 67   if (obj_age <= markWord::max_age) {
 68     assert(obj_age < MAX_COHORTS && region_age < MAX_COHORTS, "Should have been tenured");
 69 #ifdef SHENANDOAH_CENSUS_NOISE
 70     // Region ageing is stochastic and non-monotonic; this vitiates mortality
 71     // demographics in ways that might defeat our algorithms. Marking may be a
 72     // time when we might be able to correct this, but we currently do not do
 73     // this. Like skipped statistics further below, we want to track the
 74     // impact of this noise to see if this may be worthwhile. JDK-<TBD>.
 75     uint age = obj_age;
 76     if (region_age > 0) {
 77       add_aged(size, worker_id);   // this tracking is coarse for now
 78       age += region_age;
 79       if (age >= MAX_COHORTS) {
 80         age = (uint)(MAX_COHORTS - 1);  // clamp
 81         add_clamped(size, worker_id);
 82       }
 83     }
 84     if (region_youth > 0) {   // track object volume with retrograde age
 85       add_young(size, worker_id);
 86     }
 87 #else   // SHENANDOAH_CENSUS_NOISE
 88     uint age = MIN2(obj_age + region_age, (uint)(MAX_COHORTS - 1));  // clamp
 89 #endif  // SHENANDOAH_CENSUS_NOISE
 90     get_local_age_table(worker_id)->add(age, size);
 91   } else {
 92     // update skipped statistics
 93     CENSUS_NOISE(add_skipped(size, worker_id);)
 94   }
 95 }
 96 
 97 #ifdef SHENANDOAH_CENSUS_NOISE
 98 void ShenandoahAgeCensus::add_skipped(size_t size, uint worker_id) {
 99   _local_noise[worker_id].skipped += size;
100 }
101 
102 void ShenandoahAgeCensus::add_aged(size_t size, uint worker_id) {
103   _local_noise[worker_id].aged += size;
104 }
105 
106 void ShenandoahAgeCensus::add_clamped(size_t size, uint worker_id) {
107   _local_noise[worker_id].clamped += size;
108 }
109 
110 void ShenandoahAgeCensus::add_young(size_t size, uint worker_id) {
111   _local_noise[worker_id].young += size;
112 }
113 #endif // SHENANDOAH_CENSUS_NOISE
114 
115 // Prepare for a new census update, by clearing appropriate global slots.
116 void ShenandoahAgeCensus::prepare_for_census_update() {
117   assert(_epoch < MAX_SNAPSHOTS, "Out of bounds");
118   if (++_epoch >= MAX_SNAPSHOTS) {
119     _epoch=0;
120   }
121   _global_age_table[_epoch]->clear();
122   CENSUS_NOISE(_global_noise[_epoch].clear();)
123 }
124 
125 // Update the census data from appropriate sources,
126 // and compute the new tenuring threshold.
127 void ShenandoahAgeCensus::update_census(size_t age0_pop, AgeTable* pv1, AgeTable* pv2) {
128   // Check that we won't overwrite existing data: caller is
129   // responsible for explicitly clearing the slot via calling
130   // prepare_for_census_update().
131   assert(_global_age_table[_epoch]->is_clear(), "Dirty decks");
132   CENSUS_NOISE(assert(_global_noise[_epoch].is_clear(), "Dirty decks");)
133   if (ShenandoahGenerationalAdaptiveTenuring && !ShenandoahGenerationalCensusAtEvac) {
134     assert(pv1 == nullptr && pv2 == nullptr, "Error, check caller");
135     // Seed cohort 0 with population that may have been missed during
136     // regular census.
137     _global_age_table[_epoch]->add((uint)0, age0_pop);
138 
139     size_t max_workers = ShenandoahHeap::heap()->max_workers();
140     // Merge data from local age tables into the global age table for the epoch,
141     // clearing the local tables.
142     for (uint i = 0; i < max_workers; i++) {
143       // age stats
144       _global_age_table[_epoch]->merge(_local_age_table[i]);
145       _local_age_table[i]->clear();   // clear for next census
146       // Merge noise stats
147       CENSUS_NOISE(_global_noise[_epoch].merge(_local_noise[i]);)
148       CENSUS_NOISE(_local_noise[i].clear();)
149     }
150   } else {
151     // census during evac
152     assert(pv1 != nullptr && pv2 != nullptr, "Error, check caller");
153     _global_age_table[_epoch]->merge(pv1);
154     _global_age_table[_epoch]->merge(pv2);
155   }
156 
157   update_tenuring_threshold();
158 }
159 
160 
161 // Reset the epoch for the global age tables,
162 // clearing all history.
163 void ShenandoahAgeCensus::reset_global() {
164   assert(_epoch < MAX_SNAPSHOTS, "Out of bounds");
165   for (uint i = 0; i < MAX_SNAPSHOTS; i++) {
166     _global_age_table[i]->clear();
167     CENSUS_NOISE(_global_noise[i].clear();)
168   }
169   _epoch = MAX_SNAPSHOTS;
170   assert(_epoch < MAX_SNAPSHOTS, "Error");
171 }
172 
173 // Reset the local age tables, clearing any partial census.
174 void ShenandoahAgeCensus::reset_local() {
175   if (!ShenandoahGenerationalAdaptiveTenuring || ShenandoahGenerationalCensusAtEvac) {
176     assert(_local_age_table == nullptr, "Error");
177     return;
178   }
179   size_t max_workers = ShenandoahHeap::heap()->max_workers();
180   for (uint i = 0; i < max_workers; i++) {
181     _local_age_table[i]->clear();
182     CENSUS_NOISE(_local_noise[i].clear();)
183   }
184 }
185 
186 // Is global census information clear?
187 bool ShenandoahAgeCensus::is_clear_global() {
188   assert(_epoch < MAX_SNAPSHOTS, "Out of bounds");
189   for (uint i = 0; i < MAX_SNAPSHOTS; i++) {
190     bool clear = _global_age_table[i]->is_clear();
191     CENSUS_NOISE(clear |= _global_noise[i].is_clear();)
192     if (!clear) {
193       return false;
194     }
195   }
196   return true;
197 }
198 
199 // Is local census information clear?
200 bool ShenandoahAgeCensus::is_clear_local() {
201   if (!ShenandoahGenerationalAdaptiveTenuring || ShenandoahGenerationalCensusAtEvac) {
202     assert(_local_age_table == nullptr, "Error");
203     return true;
204   }
205   size_t max_workers = ShenandoahHeap::heap()->max_workers();
206   for (uint i = 0; i < max_workers; i++) {
207     bool clear = _local_age_table[i]->is_clear();
208     CENSUS_NOISE(clear |= _local_noise[i].is_clear();)
209     if (!clear) {
210       return false;
211     }
212   }
213   return true;
214 }
215 
216 void ShenandoahAgeCensus::update_tenuring_threshold() {
217   if (!ShenandoahGenerationalAdaptiveTenuring) {
218     _tenuring_threshold[_epoch] = InitialTenuringThreshold;
219   } else {
220     uint tt = compute_tenuring_threshold();
221     assert(tt <= MAX_COHORTS, "Out of bounds");
222     _tenuring_threshold[_epoch] = tt;
223   }
224   print();
225   log_trace(gc, age)("New tenuring threshold " UINTX_FORMAT " (min " UINTX_FORMAT ", max " UINTX_FORMAT")",
226     (uintx) _tenuring_threshold[_epoch], ShenandoahGenerationalMinTenuringAge, ShenandoahGenerationalMaxTenuringAge);
227 }
228 
229 // Currently Shenandoah{Min,Max}TenuringAge have a floor of 1 because we
230 // aren't set up to promote age 0 objects.
231 uint ShenandoahAgeCensus::compute_tenuring_threshold() {
232   // Dispose of the extremal cases early so the loop below
233   // is less fragile.
234   if (ShenandoahGenerationalMaxTenuringAge == ShenandoahGenerationalMinTenuringAge) {
235     return ShenandoahGenerationalMaxTenuringAge; // Any value in [1,16]
236   }
237   assert(ShenandoahGenerationalMinTenuringAge < ShenandoahGenerationalMaxTenuringAge, "Error");
238 
239   // Starting with the oldest cohort with a non-trivial population
240   // (as specified by ShenandoahGenerationalTenuringCohortPopulationThreshold) in the
241   // previous epoch, and working down the cohorts by age, find the
242   // oldest age that has a significant mortality rate (as specified by
243   // ShenandoahGenerationalTenuringMortalityRateThreshold). We use this as
244   // tenuring age to be used for the evacuation cycle to follow.
245   // Results are clamped between user-specified min & max guardrails,
246   // so we ignore any cohorts outside ShenandoahGenerational[Min,Max]Age.
247 
248   // Current and previous epoch in ring
249   const uint cur_epoch = _epoch;
250   const uint prev_epoch = cur_epoch > 0  ? cur_epoch - 1 : markWord::max_age;
251 
252   // Current and previous population vectors in ring
253   const AgeTable* cur_pv = _global_age_table[cur_epoch];
254   const AgeTable* prev_pv = _global_age_table[prev_epoch];
255   uint upper_bound = ShenandoahGenerationalMaxTenuringAge;
256   const uint prev_tt = previous_tenuring_threshold();
257   if (ShenandoahGenerationalCensusIgnoreOlderCohorts && prev_tt > 0) {
258      // We stay below the computed tenuring threshold for the last cycle plus 1,
259      // ignoring the mortality rates of any older cohorts.
260      upper_bound = MIN2(upper_bound, prev_tt + 1);
261   }
262   upper_bound = MIN2(upper_bound, markWord::max_age);
263 
264   const uint lower_bound = MAX2((uint)ShenandoahGenerationalMinTenuringAge, (uint)1);
265 
266   uint tenuring_threshold = upper_bound;
267   for (uint i = upper_bound; i >= lower_bound; i--) {
268     assert(i > 0, "Index (i-1) would underflow/wrap");
269     assert(i <= markWord::max_age, "Index i would overflow");
270     // Cohort of current age i
271     const size_t cur_pop = cur_pv->sizes[i];
272     const size_t prev_pop = prev_pv->sizes[i-1];
273     const double mr = mortality_rate(prev_pop, cur_pop);
274     if (prev_pop > ShenandoahGenerationalTenuringCohortPopulationThreshold &&
275         mr > ShenandoahGenerationalTenuringMortalityRateThreshold) {
276       // This is the oldest cohort that has high mortality.
277       // We ignore any cohorts that had a very low population count, or
278       // that have a lower mortality rate than we care to age in young; these
279       // cohorts are considered eligible for tenuring when all older
280       // cohorts are. We return the next higher age as the tenuring threshold
281       // so that we do not prematurely promote objects of this age.
282       assert(tenuring_threshold == i+1 || tenuring_threshold == upper_bound, "Error");
283       assert(tenuring_threshold >= lower_bound && tenuring_threshold <= upper_bound, "Error");
284       return tenuring_threshold;
285     }
286     // Remember that we passed over this cohort, looking for younger cohorts
287     // showing high mortality. We want to tenure cohorts of this age.
288     tenuring_threshold = i;
289   }
290   assert(tenuring_threshold >= lower_bound && tenuring_threshold <= upper_bound, "Error");
291   return tenuring_threshold;
292 }
293 
294 // Mortality rate of a cohort, given its previous and current population
295 double ShenandoahAgeCensus::mortality_rate(size_t prev_pop, size_t cur_pop) {
296   // The following also covers the case where both entries are 0
297   if (prev_pop <= cur_pop) {
298     // adjust for inaccurate censuses by finessing the
299     // reappearance of dark matter as normal matter;
300     // mortality rate is 0 if population remained the same
301     // or increased.
302     if (cur_pop > prev_pop) {
303       log_trace(gc, age)
304         (" (dark matter) Cohort population " SIZE_FORMAT_W(10) " to " SIZE_FORMAT_W(10),
305         prev_pop*oopSize, cur_pop*oopSize);
306     }
307     return 0.0;
308   }
309   assert(prev_pop > 0 && prev_pop > cur_pop, "Error");
310   return 1.0 - (((double)cur_pop)/((double)prev_pop));
311 }
312 
313 void ShenandoahAgeCensus::print() {
314   // Print the population vector for the current epoch, and
315   // for the previous epoch, as well as the computed mortality
316   // ratio for each extant cohort.
317   const uint cur_epoch = _epoch;
318   const uint prev_epoch = cur_epoch > 0 ? cur_epoch - 1: markWord::max_age;
319 
320   const AgeTable* cur_pv = _global_age_table[cur_epoch];
321   const AgeTable* prev_pv = _global_age_table[prev_epoch];
322 
323   const uint tt = tenuring_threshold();
324 
325   size_t total= 0;
326   for (uint i = 1; i < MAX_COHORTS; i++) {
327     const size_t prev_pop = prev_pv->sizes[i-1];  // (i-1) OK because i >= 1
328     const size_t cur_pop  = cur_pv->sizes[i];
329     double mr = mortality_rate(prev_pop, cur_pop);
330     // Suppress printing when everything is zero
331     if (prev_pop + cur_pop > 0) {
332       log_info(gc, age)
333         (" - age %3u: prev " SIZE_FORMAT_W(10) " bytes, curr " SIZE_FORMAT_W(10) " bytes, mortality %.2f ",
334          i, prev_pop*oopSize, cur_pop*oopSize, mr);
335     }
336     total += cur_pop;
337     if (i == tt) {
338       // Underline the cohort for tenuring threshold (if < MAX_COHORTS)
339       log_info(gc, age)("----------------------------------------------------------------------------");
340     }
341   }
342   CENSUS_NOISE(_global_noise[cur_epoch].print(total);)
343 }
344 
345 #ifdef SHENANDOAH_CENSUS_NOISE
346 void ShenandoahNoiseStats::print(size_t total) {
347   if (total > 0) {
348     float f_skipped = (float)skipped/(float)total;
349     float f_aged    = (float)aged/(float)total;
350     float f_clamped = (float)clamped/(float)total;
351     float f_young   = (float)young/(float)total;
352     log_info(gc, age)("Skipped: " SIZE_FORMAT_W(10) " (%.2f),  R-Aged: " SIZE_FORMAT_W(10) " (%.2f),  "
353                       "Clamped: " SIZE_FORMAT_W(10) " (%.2f),  R-Young: " SIZE_FORMAT_W(10) " (%.2f)",
354                       skipped*oopSize, f_skipped, aged*oopSize, f_aged,
355                       clamped*oopSize, f_clamped, young*oopSize, f_young);
356   }
357 }
358 #endif // SHENANDOAH_CENSUS_NOISE