1 /*
   2  * Copyright (c) 2013, 2018, Red Hat, Inc. All rights reserved.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.
   7  *
   8  * This code is distributed in the hope that it will be useful, but WITHOUT
   9  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  10  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  11  * version 2 for more details (a copy is included in the LICENSE file that
  12  * accompanied this code).
  13  *
  14  * You should have received a copy of the GNU General Public License version
  15  * 2 along with this work; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  17  *
  18  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  19  * or visit www.oracle.com if you need additional information or have any
  20  * questions.
  21  *
  22  */
  23 
  24 #include "precompiled.hpp"
  25 #include "gc/shenandoah/shenandoahMetrics.hpp"
  26 #include "gc/shenandoah/shenandoahHeap.hpp"
  27 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
  28 #include "gc/shenandoah/shenandoahHeapRegion.hpp"
  29 #include "gc/shenandoah/shenandoahFreeSet.hpp"
  30 
  31 /*
  32  * Internal fragmentation metric: describes how fragmented the heap regions are.
  33  *
  34  * It is derived as:
  35  *
  36  *               sum(used[i]^2, i=0..k)
  37  *   IF = 1 - ------------------------------
  38  *              C * sum(used[i], i=0..k)
  39  *
  40  * ...where k is the number of regions in computation, C is the region capacity, and
  41  * used[i] is the used space in the region.
  42  *
  43  * The non-linearity causes IF to be lower for the cases where the same total heap
  44  * used is densely packed. For example:
  45  *   a) Heap is completely full  => IF = 0
  46  *   b) Heap is half full, first 50% regions are completely full => IF = 0
  47  *   c) Heap is half full, each region is 50% full => IF = 1/2
  48  *   d) Heap is quarter full, first 50% regions are completely full => IF = 0
  49  *   e) Heap is quarter full, each region is 25% full => IF = 3/4
  50  *   f) Heap has the small object per each region => IF =~ 1
  51  */
  52 double ShenandoahMetrics::internal_fragmentation() {
  53   ShenandoahHeap* heap = ShenandoahHeap::heap();
  54 
  55   double squared = 0;
  56   double linear = 0;
  57   int count = 0;
  58   for (size_t c = 0; c < heap->num_regions(); c++) {
  59     ShenandoahHeapRegion* r = heap->get_region(c);
  60     size_t used = r->used();
  61     squared += used * used;
  62     linear += used;
  63     count++;
  64   }
  65 
  66   if (count > 0) {
  67     double s = squared / (ShenandoahHeapRegion::region_size_bytes() * linear);
  68     return 1 - s;
  69   } else {
  70     return 0;
  71   }
  72 }
  73 
  74 /*
  75  * External fragmentation metric: describes how fragmented the heap is.
  76  *
  77  * It is derived as:
  78  *
  79  *   EF = 1 - largest_contiguous_free / total_free
  80  *
  81  * For example:
  82  *   a) Heap is completely empty => EF = 0
  83  *   b) Heap is completely full => EF = 1
  84  *   c) Heap is first-half full => EF = 1/2
  85  *   d) Heap is half full, full and empty regions interleave => EF =~ 1
  86  */
  87 double ShenandoahMetrics::external_fragmentation() {
  88   ShenandoahHeap* heap = ShenandoahHeap::heap();
  89 
  90   size_t last_idx = 0;
  91   size_t max_contig = 0;
  92   size_t empty_contig = 0;
  93 
  94   size_t free = 0;
  95   for (size_t c = 0; c < heap->num_regions(); c++) {
  96     ShenandoahHeapRegion* r = heap->get_region(c);
  97 
  98     if (r->is_empty() && (last_idx + 1 == c)) {
  99       empty_contig++;
 100     } else {
 101       empty_contig = 0;
 102     }
 103 
 104     free += r->free();
 105     max_contig = MAX2(max_contig, empty_contig);
 106     last_idx = c;
 107   }
 108 
 109   if (free > 0) {
 110     return 1 - (1.0 * max_contig * ShenandoahHeapRegion::region_size_bytes() / free);
 111   } else {
 112     return 1;
 113   }
 114 }
 115 
 116 ShenandoahMetricsSnapshot::ShenandoahMetricsSnapshot() {
 117   _heap = ShenandoahHeap::heap();
 118 }
 119 
 120 void ShenandoahMetricsSnapshot::snap_before() {
 121   _used_before = _heap->used();
 122   _if_before = ShenandoahMetrics::internal_fragmentation();
 123   _ef_before = ShenandoahMetrics::external_fragmentation();
 124 }
 125 void ShenandoahMetricsSnapshot::snap_after() {
 126   _used_after = _heap->used();
 127   _if_after = ShenandoahMetrics::internal_fragmentation();
 128   _ef_after = ShenandoahMetrics::external_fragmentation();
 129 }
 130 
 131 void ShenandoahMetricsSnapshot::print() {
 132   log_info(gc, ergo)("Used: before: " SIZE_FORMAT "M, after: " SIZE_FORMAT "M", _used_before/M, _used_after/M);
 133   log_info(gc, ergo)("Internal frag: before: %.1f%%, after: %.1f%%", _if_before * 100, _if_after * 100);
 134   log_info(gc, ergo)("External frag: before: %.1f%%, after: %.1f%%", _ef_before * 100, _ef_after * 100);
 135 }
 136 
 137 bool ShenandoahMetricsSnapshot::is_good_progress(const char *label) {
 138   // Under the critical threshold? Declare failure.
 139   size_t free_actual   = _heap->free_set()->available();
 140   size_t free_expected = _heap->max_capacity() / 100 * ShenandoahCriticalFreeThreshold;
 141   if (free_actual < free_expected) {
 142     log_info(gc, ergo)("Not enough free space (" SIZE_FORMAT "M, need " SIZE_FORMAT "M) after %s",
 143                        free_actual / M, free_expected / M, label);
 144     return false;
 145   }
 146 
 147   // Freed up enough? Good! Declare victory.
 148   size_t progress_actual   = (_used_before > _used_after) ? _used_before - _used_after : 0;
 149   size_t progress_expected = ShenandoahHeapRegion::region_size_bytes();
 150   if (progress_actual >= progress_expected) {
 151     return true;
 152   }
 153   log_info(gc,ergo)("Not enough progress (" SIZE_FORMAT "M, need " SIZE_FORMAT "M) after %s",
 154                     progress_actual / M, progress_expected / M, label);
 155 
 156   // Internal fragmentation is down? Good! Declare victory.
 157   double if_actual = _if_before - _if_after;
 158   double if_expected = 0.01; // 1% should be enough
 159   if (if_actual > if_expected) {
 160     return true;
 161   }
 162   log_info(gc,ergo)("Not enough internal fragmentation improvement (%.1f%%, need %.1f%%) after %s",
 163                     if_actual * 100, if_expected * 100, label);
 164 
 165   // External fragmentation is down? Good! Declare victory.
 166   double ef_actual = _ef_before - _ef_after;
 167   double ef_expected = 0.01; // 1% should be enough
 168   if (ef_actual > ef_expected) {
 169     return true;
 170   }
 171   log_info(gc,ergo)("Not enough external fragmentation improvement (%.1f%%, need %.1f%%) after %s",
 172                     if_actual * 100, if_expected * 100, label);
 173 
 174   // Nothing good had happened.
 175   return false;
 176 }