1 /*
   2  * Copyright (c) 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 
  26 #include "gc/shenandoah/shenandoahNumberSeq.hpp"
  27 #include "runtime/atomic.hpp"
  28 
  29 HdrSeq::HdrSeq() {
  30   _hdr = NEW_C_HEAP_ARRAY(int*, MagBuckets, mtInternal);
  31   for (int c = 0; c < MagBuckets; c++) {
  32     _hdr[c] = NULL;
  33   }
  34 }
  35 
  36 HdrSeq::~HdrSeq() {
  37   for (int c = 0; c < MagBuckets; c++) {
  38     int* sub = _hdr[c];
  39     if (sub != NULL) {
  40       FREE_C_HEAP_ARRAY(int, sub);
  41     }
  42   }
  43   FREE_C_HEAP_ARRAY(int*, _hdr);
  44 }
  45 
  46 void HdrSeq::add(double val) {
  47   if (val < 0) {
  48     assert (false, "value (%8.2f) is not negative", val);
  49     val = 0;
  50   }
  51 
  52   NumberSeq::add(val);
  53 
  54   double v = val;
  55   int mag;
  56   if (v > 0) {
  57     mag = 0;
  58     while (v > 1) {
  59       mag++;
  60       v /= 10;
  61     }
  62     while (v < 0.1) {
  63       mag--;
  64       v *= 10;
  65     }
  66   } else {
  67     mag = MagMinimum;
  68   }
  69 
  70   int bucket = -MagMinimum + mag;
  71   int sub_bucket = (int) (v * ValBuckets);
  72 
  73   // Defensively saturate for product bits:
  74   if (bucket < 0) {
  75     assert (false, "bucket index (%d) underflow for value (%8.2f)", bucket, val);
  76     bucket = 0;
  77   }
  78 
  79   if (bucket >= MagBuckets) {
  80     assert (false, "bucket index (%d) overflow for value (%8.2f)", bucket, val);
  81     bucket = MagBuckets - 1;
  82   }
  83 
  84   if (sub_bucket < 0) {
  85     assert (false, "sub-bucket index (%d) underflow for value (%8.2f)", sub_bucket, val);
  86     sub_bucket = 0;
  87   }
  88 
  89   if (sub_bucket >= ValBuckets) {
  90     assert (false, "sub-bucket index (%d) overflow for value (%8.2f)", sub_bucket, val);
  91     sub_bucket = ValBuckets - 1;
  92   }
  93 
  94   int* b = _hdr[bucket];
  95   if (b == NULL) {
  96     b = NEW_C_HEAP_ARRAY(int, ValBuckets, mtInternal);
  97     for (int c = 0; c < ValBuckets; c++) {
  98       b[c] = 0;
  99     }
 100     _hdr[bucket] = b;
 101   }
 102   b[sub_bucket]++;
 103 }
 104 
 105 double HdrSeq::percentile(double level) const {
 106   // target should be non-zero to find the first sample
 107   int target = MAX2(1, (int) (level * num() / 100));
 108   int cnt = 0;
 109   for (int mag = 0; mag < MagBuckets; mag++) {
 110     if (_hdr[mag] != NULL) {
 111       for (int val = 0; val < ValBuckets; val++) {
 112         cnt += _hdr[mag][val];
 113         if (cnt >= target) {
 114           return pow(10.0, MagMinimum + mag) * val / ValBuckets;
 115         }
 116       }
 117     }
 118   }
 119   return maximum();
 120 }
 121 
 122 BinaryMagnitudeSeq::BinaryMagnitudeSeq() {
 123   _mags = NEW_C_HEAP_ARRAY(size_t, BitsPerSize_t, mtInternal);
 124   for (int c = 0; c < BitsPerSize_t; c++) {
 125     _mags[c] = 0;
 126   }
 127   _sum = 0;
 128 }
 129 
 130 BinaryMagnitudeSeq::~BinaryMagnitudeSeq() {
 131   FREE_C_HEAP_ARRAY(size_t, _mags);
 132 }
 133 
 134 void BinaryMagnitudeSeq::add(size_t val) {
 135   Atomic::add(val, &_sum);
 136 
 137   int mag = log2_intptr(val) + 1;
 138 
 139   // Defensively saturate for product bits:
 140   if (mag < 0) {
 141     assert (false, "bucket index (%d) underflow for value (" SIZE_FORMAT ")", mag, val);
 142     mag = 0;
 143   }
 144 
 145   if (mag >= BitsPerSize_t) {
 146     assert (false, "bucket index (%d) overflow for value (" SIZE_FORMAT ")", mag, val);
 147     mag = BitsPerSize_t - 1;
 148   }
 149 
 150   Atomic::add((size_t)1, &_mags[mag]);
 151 }
 152 
 153 size_t BinaryMagnitudeSeq::level(int level) const {
 154   if (0 <= level && level < BitsPerSize_t) {
 155     return _mags[level];
 156   } else {
 157     return 0;
 158   }
 159 }
 160 
 161 size_t BinaryMagnitudeSeq::num() const {
 162   size_t r = 0;
 163   for (int c = 0; c < BitsPerSize_t; c++) {
 164     r += _mags[c];
 165   }
 166   return r;
 167 }
 168 
 169 size_t BinaryMagnitudeSeq::sum() const {
 170   return _sum;
 171 }
 172 
 173 int BinaryMagnitudeSeq::min_level() const {
 174   for (int c = 0; c < BitsPerSize_t; c++) {
 175     if (_mags[c] != 0) {
 176       return c;
 177     }
 178   }
 179   return BitsPerSize_t - 1;
 180 }
 181 
 182 int BinaryMagnitudeSeq::max_level() const {
 183   for (int c = BitsPerSize_t - 1; c > 0; c--) {
 184     if (_mags[c] != 0) {
 185       return c;
 186     }
 187   }
 188   return 0;
 189 }