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 }