1 /*
  2  * Copyright (c) 2018, 2019, Red Hat, Inc. 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/shenandoahNumberSeq.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);
 42     }
 43   }
 44   FREE_C_HEAP_ARRAY(int*, _hdr);
 45 }
 46 
 47 void HdrSeq::add(double val) {
 48   if (val < 0) {
 49     assert (false, "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, "bucket index (%d) underflow for value (%8.2f)", bucket, val);
 77     bucket = 0;
 78   }
 79 
 80   if (bucket >= MagBuckets) {
 81     assert (false, "bucket index (%d) overflow for value (%8.2f)", bucket, val);
 82     bucket = MagBuckets - 1;
 83   }
 84 
 85   if (sub_bucket < 0) {
 86     assert (false, "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, "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(size_t, BitsPerSize_t, mtInternal);
125   clear();
126 }
127 
128 BinaryMagnitudeSeq::~BinaryMagnitudeSeq() {
129   FREE_C_HEAP_ARRAY(size_t, _mags);
130 }
131 
132 void BinaryMagnitudeSeq::clear() {
133   for (int c = 0; c < BitsPerSize_t; c++) {
134     _mags[c] = 0;
135   }
136   _sum = 0;
137 }
138 
139 void BinaryMagnitudeSeq::add(size_t val) {
140   Atomic::add(&_sum, val);
141 
142   int mag = log2i_graceful(val) + 1;
143 
144   // Defensively saturate for product bits:
145   if (mag < 0) {
146     assert (false, "bucket index (%d) underflow for value (" SIZE_FORMAT ")", mag, val);
147     mag = 0;
148   }
149 
150   if (mag >= BitsPerSize_t) {
151     assert (false, "bucket index (%d) overflow for value (" SIZE_FORMAT ")", mag, val);
152     mag = BitsPerSize_t - 1;
153   }
154 
155   Atomic::add(&_mags[mag], (size_t)1);
156 }
157 
158 size_t BinaryMagnitudeSeq::level(int level) const {
159   if (0 <= level && level < BitsPerSize_t) {
160     return _mags[level];
161   } else {
162     return 0;
163   }
164 }
165 
166 size_t BinaryMagnitudeSeq::num() const {
167   size_t r = 0;
168   for (int c = 0; c < BitsPerSize_t; 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 < BitsPerSize_t; c++) {
180     if (_mags[c] != 0) {
181       return c;
182     }
183   }
184   return BitsPerSize_t - 1;
185 }
186 
187 int BinaryMagnitudeSeq::max_level() const {
188   for (int c = BitsPerSize_t - 1; c > 0; c--) {
189     if (_mags[c] != 0) {
190       return c;
191     }
192   }
193   return 0;
194 }