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 // Merge this HdrSeq into hdr2: clear optional and on-by-default
124 // Note: this method isn't intrinsically MT-safe; callers must take care
125 // of any mutual exclusion as necessary.
126 void HdrSeq::merge(HdrSeq& hdr2, bool clear_this) {
127   for (int mag = 0; mag < MagBuckets; mag++) {
128     if (_hdr[mag] != NULL) {
129       int* that_bucket = hdr2._hdr[mag];
130       if (that_bucket == NULL) {
131         if (clear_this) {
132           // the target doesn't have any values, swap in ours.
133           // Could this cause native memory fragmentation?
134           hdr2._hdr[mag] = _hdr[mag];
135           _hdr[mag] = NULL;
136         } else {
137           // We can't clear this, so we create the entries & add in below
138           that_bucket = NEW_C_HEAP_ARRAY(int, ValBuckets, mtInternal);
139           for (int val = 0; val < ValBuckets; val++) {
140             that_bucket[val] = _hdr[mag][val];
141           }
142           hdr2._hdr[mag] = that_bucket;
143         }
144       } else {
145         // Add in our values into target
146         for (int val = 0; val < ValBuckets; val++) {
147           that_bucket[val] += _hdr[mag][val];
148           if (clear_this) {
149             _hdr[mag][val] = 0;
150           }
151         }
152       }
153     }
154   }
155   // Merge up the class hierarchy
156   NumberSeq::merge(hdr2, clear_this);
157 }
158 
159 BinaryMagnitudeSeq::BinaryMagnitudeSeq() {
160   _mags = NEW_C_HEAP_ARRAY(size_t, BitsPerSize_t, mtInternal);
161   clear();
162 }
163 
164 BinaryMagnitudeSeq::~BinaryMagnitudeSeq() {
165   FREE_C_HEAP_ARRAY(size_t, _mags);
166 }
167 
168 void BinaryMagnitudeSeq::clear() {
169   for (int c = 0; c < BitsPerSize_t; c++) {
170     _mags[c] = 0;
171   }
172   _sum = 0;
173 }
174 
175 void BinaryMagnitudeSeq::add(size_t val) {
176   Atomic::add(&_sum, val);
177 
178   int mag = log2i_graceful(val) + 1;
179 
180   // Defensively saturate for product bits:
181   if (mag < 0) {
182     assert (false, "bucket index (%d) underflow for value (" SIZE_FORMAT ")", mag, val);
183     mag = 0;
184   }
185 
186   if (mag >= BitsPerSize_t) {
187     assert (false, "bucket index (%d) overflow for value (" SIZE_FORMAT ")", mag, val);
188     mag = BitsPerSize_t - 1;
189   }
190 
191   Atomic::add(&_mags[mag], (size_t)1);
192 }
193 
194 size_t BinaryMagnitudeSeq::level(int level) const {
195   if (0 <= level && level < BitsPerSize_t) {
196     return _mags[level];
197   } else {
198     return 0;
199   }
200 }
201 
202 size_t BinaryMagnitudeSeq::num() const {
203   size_t r = 0;
204   for (int c = 0; c < BitsPerSize_t; c++) {
205     r += _mags[c];
206   }
207   return r;
208 }
209 
210 size_t BinaryMagnitudeSeq::sum() const {
211   return _sum;
212 }
213 
214 int BinaryMagnitudeSeq::min_level() const {
215   for (int c = 0; c < BitsPerSize_t; c++) {
216     if (_mags[c] != 0) {
217       return c;
218     }
219   }
220   return BitsPerSize_t - 1;
221 }
222 
223 int BinaryMagnitudeSeq::max_level() const {
224   for (int c = BitsPerSize_t - 1; c > 0; c--) {
225     if (_mags[c] != 0) {
226       return c;
227     }
228   }
229   return 0;
230 }