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