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