]>
Commit | Line | Data |
---|---|---|
2ac76861 | 1 | |
5625c032 | 2 | /* |
262a0e14 | 3 | * $Id$ |
5625c032 | 4 | * |
5 | * DEBUG: section 62 Generic Histogram | |
6 | * AUTHOR: Duane Wessels | |
7 | * | |
2b6662ba | 8 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
e25c139f | 9 | * ---------------------------------------------------------- |
5625c032 | 10 | * |
2b6662ba | 11 | * Squid is the result of efforts by numerous individuals from |
12 | * the Internet community; see the CONTRIBUTORS file for full | |
13 | * details. Many organizations have provided support for Squid's | |
14 | * development; see the SPONSORS file for full details. Squid is | |
15 | * Copyrighted (C) 2001 by the Regents of the University of | |
16 | * California; see the COPYRIGHT file for full details. Squid | |
17 | * incorporates software developed and/or copyrighted by other | |
18 | * sources; see the CREDITS file for full details. | |
5625c032 | 19 | * |
20 | * This program is free software; you can redistribute it and/or modify | |
21 | * it under the terms of the GNU General Public License as published by | |
22 | * the Free Software Foundation; either version 2 of the License, or | |
23 | * (at your option) any later version. | |
26ac0430 | 24 | * |
5625c032 | 25 | * This program is distributed in the hope that it will be useful, |
26 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
27 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
28 | * GNU General Public License for more details. | |
26ac0430 | 29 | * |
5625c032 | 30 | * You should have received a copy of the GNU General Public License |
31 | * along with this program; if not, write to the Free Software | |
cbdec147 | 32 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. |
e25c139f | 33 | * |
5625c032 | 34 | */ |
35 | ||
36 | /* | |
37 | * Important restrictions on val_in and val_out functions: | |
26ac0430 | 38 | * |
5625c032 | 39 | * - val_in: ascending, defined on [0, oo), val_in(0) == 0; |
40 | * - val_out: x == val_out(val_in(x)) where val_in(x) is defined | |
41 | * | |
26ac0430 | 42 | * In practice, the requirements are less strict, |
5625c032 | 43 | * but then it gets hard to define them without math notation. |
44 | * val_in is applied after offseting the value but before scaling | |
45 | * See log and linear based histograms for examples | |
46 | */ | |
47 | ||
48 | #include "squid.h" | |
e6ccf245 | 49 | #include "Store.h" |
5625c032 | 50 | |
51 | /* Local functions */ | |
7d47d8e6 | 52 | static void statHistInit(StatHist * H, int capacity, hbase_f * val_in, hbase_f * val_out, double min, double max); |
5625c032 | 53 | static int statHistBin(const StatHist * H, double v); |
54 | static double statHistVal(const StatHist * H, int bin); | |
ba4f8e5a | 55 | static StatHistBinDumper statHistBinDumper; |
853310e4 | 56 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
62e76326 | 57 | /* |
58 | * HP-UX and GCC (2.8?) give strange errors when these simple | |
59 | * functions are static. | |
60 | */ | |
20efa1c2 AJ |
61 | namespace Math |
62 | { | |
95c297ec | 63 | static hbase_f Log; |
64 | static hbase_f Exp; | |
65 | static hbase_f Null; | |
20efa1c2 | 66 | }; |
853310e4 | 67 | #endif |
5625c032 | 68 | |
69 | /* low level init, higher level functions has less params */ | |
70 | static void | |
7d47d8e6 | 71 | statHistInit(StatHist * H, int capacity, hbase_f * val_in, hbase_f * val_out, double min, double max) |
5625c032 | 72 | { |
73 | assert(H); | |
74 | assert(capacity > 0); | |
75 | assert(val_in && val_out); | |
2f266e7a | 76 | /* check before we divide to get scale */ |
77 | assert(val_in(max - min) > 0); | |
e6ccf245 | 78 | H->bins = (int *)xcalloc(capacity, sizeof(int)); |
5625c032 | 79 | H->min = min; |
80 | H->max = max; | |
81 | H->capacity = capacity; | |
82 | H->scale = capacity / val_in(max - min); | |
83 | H->val_in = val_in; | |
84 | H->val_out = val_out; | |
9a2c68b2 | 85 | |
86 | /* HPUX users: If you get one of the assertions below, please send | |
87 | * [at least] the values of all variables involved in the assertions | |
88 | * when reporting a bug! | |
89 | */ | |
90 | ||
2f266e7a | 91 | /* check that functions are valid */ |
92 | /* a min value should go into bin[0] */ | |
93 | assert(statHistBin(H, min) == 0); | |
94 | /* a max value should go into the last bin */ | |
95 | assert(statHistBin(H, max) == H->capacity - 1); | |
96 | /* it is hard to test val_out, here is a crude test */ | |
22ee4794 | 97 | assert(((int) floor(0.99 + statHistVal(H, 0) - min)) == 0); |
5625c032 | 98 | } |
99 | ||
100 | void | |
101 | statHistClean(StatHist * H) | |
102 | { | |
103 | xfree(H->bins); | |
104 | H->bins = NULL; | |
105 | } | |
106 | ||
107 | /* assumes that somebody already called init for Dest */ | |
108 | void | |
109 | statHistCopy(StatHist * Dest, const StatHist * Orig) | |
110 | { | |
95c297ec | 111 | assert(Dest); |
112 | assert(Orig); | |
bf8fe701 | 113 | debugs(62, 3, "statHistCopy: Dest=" << Dest << ", Orig=" << Orig); |
5625c032 | 114 | assert(Dest->bins); |
115 | /* better be safe than sorry */ | |
bf8fe701 | 116 | debugs(62, 3, "statHistCopy: capacity " << Dest->capacity << " " << Orig->capacity); |
5625c032 | 117 | assert(Dest->capacity == Orig->capacity); |
bf8fe701 | 118 | debugs(62, 3, "statHistCopy: min " << Dest->min << " " << Orig->min ); |
95c297ec | 119 | assert(Dest->min == Orig->min); |
bf8fe701 | 120 | debugs(62, 3, "statHistCopy: max " << Dest->max << " " << Orig->max ); |
95c297ec | 121 | assert(Dest->max == Orig->max); |
bf8fe701 | 122 | debugs(62, 3, "statHistCopy: scale " << Dest->scale << " " << Orig->scale ); |
2d6c1ac0 | 123 | assert(fabs(Dest->scale - Orig->scale) < 0.0000001); |
95c297ec | 124 | assert(Dest->val_in == Orig->val_in); |
125 | assert(Dest->val_out == Orig->val_out); | |
5625c032 | 126 | /* actual copy */ |
bf8fe701 | 127 | debugs(62, 3, "statHistCopy: copying " << |
128 | (long int) (Dest->capacity * sizeof(*Dest->bins)) << " bytes to " << | |
129 | Dest->bins << " from " << Orig->bins); | |
130 | ||
41d00cd3 | 131 | memcpy(Dest->bins, Orig->bins, Dest->capacity * sizeof(*Dest->bins)); |
5625c032 | 132 | } |
133 | ||
ae50d52a | 134 | /* |
135 | * same as statHistCopy but will do nothing if capacities do not match; the | |
136 | * latter happens, for example, when #peers changes during reconfiguration; | |
137 | * if it happens too often we should think about more general solution.. | |
138 | */ | |
139 | void | |
140 | statHistSafeCopy(StatHist * Dest, const StatHist * Orig) | |
141 | { | |
142 | assert(Dest && Orig); | |
143 | assert(Dest->bins); | |
62e76326 | 144 | |
ae50d52a | 145 | if (Dest->capacity == Orig->capacity) |
62e76326 | 146 | statHistCopy(Dest, Orig); |
ae50d52a | 147 | } |
148 | ||
5625c032 | 149 | void |
150 | statHistCount(StatHist * H, double val) | |
151 | { | |
152 | const int bin = statHistBin(H, val); | |
2ac76861 | 153 | assert(H->bins); /* make sure it got initialized */ |
5625c032 | 154 | assert(0 <= bin && bin < H->capacity); |
155 | H->bins[bin]++; | |
156 | } | |
157 | ||
158 | static int | |
159 | statHistBin(const StatHist * H, double v) | |
160 | { | |
161 | int bin; | |
41587298 | 162 | #if BROKEN_STAT_HIST_BIN |
62e76326 | 163 | |
41587298 | 164 | return 0; |
165 | /* NOTREACHED */ | |
166 | #endif | |
62e76326 | 167 | |
2ac76861 | 168 | v -= H->min; /* offset */ |
62e76326 | 169 | |
41587298 | 170 | if (v <= 0.0) /* too small */ |
62e76326 | 171 | return 0; |
172 | ||
9a2c68b2 | 173 | bin = (int) floor(H->scale * H->val_in(v) + 0.5); |
62e76326 | 174 | |
2ac76861 | 175 | if (bin < 0) /* should not happen */ |
62e76326 | 176 | bin = 0; |
177 | ||
2ac76861 | 178 | if (bin >= H->capacity) /* too big */ |
62e76326 | 179 | bin = H->capacity - 1; |
180 | ||
5625c032 | 181 | return bin; |
182 | } | |
183 | ||
184 | static double | |
185 | statHistVal(const StatHist * H, int bin) | |
186 | { | |
4d62b0af | 187 | return H->val_out((double) bin / H->scale) + H->min; |
5625c032 | 188 | } |
189 | ||
190 | double | |
191 | statHistDeltaMedian(const StatHist * A, const StatHist * B) | |
04a28d46 | 192 | { |
193 | return statHistDeltaPctile(A, B, 0.5); | |
194 | } | |
195 | ||
196 | double | |
197 | statHistDeltaPctile(const StatHist * A, const StatHist * B, double pctile) | |
5625c032 | 198 | { |
199 | int i; | |
200 | int s1 = 0; | |
201 | int h = 0; | |
202 | int a = 0; | |
203 | int b = 0; | |
204 | int I = 0; | |
205 | int J = A->capacity; | |
206 | int K; | |
207 | double f; | |
e6ccf245 | 208 | int *D = (int *)xcalloc(A->capacity, sizeof(int)); |
5625c032 | 209 | assert(A->capacity == B->capacity); |
62e76326 | 210 | |
5625c032 | 211 | for (i = 0; i < A->capacity; i++) { |
62e76326 | 212 | D[i] = B->bins[i] - A->bins[i]; |
213 | assert(D[i] >= 0); | |
5625c032 | 214 | } |
62e76326 | 215 | |
5625c032 | 216 | for (i = 0; i < A->capacity; i++) |
62e76326 | 217 | s1 += D[i]; |
218 | ||
04a28d46 | 219 | h = int(s1 * pctile); |
62e76326 | 220 | |
5625c032 | 221 | for (i = 0; i < A->capacity; i++) { |
62e76326 | 222 | J = i; |
223 | b += D[J]; | |
224 | ||
225 | if (a <= h && h <= b) | |
226 | break; | |
227 | ||
228 | I = i; | |
229 | ||
230 | a += D[I]; | |
5625c032 | 231 | } |
62e76326 | 232 | |
5625c032 | 233 | xfree(D); |
62e76326 | 234 | |
5625c032 | 235 | if (s1 == 0) |
62e76326 | 236 | return 0.0; |
237 | ||
6a6c3b50 | 238 | if (a > h) |
62e76326 | 239 | return 0.0; |
240 | ||
6a6c3b50 | 241 | if (a >= b) |
62e76326 | 242 | return 0.0; |
243 | ||
6a6c3b50 | 244 | if (I >= J) |
62e76326 | 245 | return 0.0; |
246 | ||
5625c032 | 247 | f = (h - a) / (b - a); |
62e76326 | 248 | |
9a2c68b2 | 249 | K = (int) floor(f * (double) (J - I) + I); |
62e76326 | 250 | |
5625c032 | 251 | return statHistVal(A, K); |
252 | } | |
253 | ||
254 | static void | |
255 | statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count) | |
256 | { | |
257 | if (count) | |
62e76326 | 258 | storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n", |
259 | idx, val, count, count / size); | |
5625c032 | 260 | } |
261 | ||
262 | void | |
eeb423fb | 263 | statHistDump(const StatHist * H, StoreEntry * sentry, StatHistBinDumper * bd) |
5625c032 | 264 | { |
265 | int i; | |
266 | double left_border = H->min; | |
62e76326 | 267 | |
5625c032 | 268 | if (!bd) |
62e76326 | 269 | bd = statHistBinDumper; |
270 | ||
5625c032 | 271 | for (i = 0; i < H->capacity; i++) { |
62e76326 | 272 | const double right_border = statHistVal(H, i + 1); |
273 | assert(right_border - left_border > 0.0); | |
274 | bd(sentry, i, left_border, right_border - left_border, H->bins[i]); | |
275 | left_border = right_border; | |
5625c032 | 276 | } |
277 | } | |
278 | ||
279 | /* log based histogram */ | |
853310e4 | 280 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
281 | static | |
282 | #endif | |
283 | double | |
20efa1c2 | 284 | Math::Log(double x) |
2ac76861 | 285 | { |
9689d97c | 286 | assert((x + 1.0) >= 0.0); |
287 | return log(x + 1.0); | |
2ac76861 | 288 | } |
853310e4 | 289 | |
b8890359 | 290 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
853310e4 | 291 | static |
292 | #endif | |
293 | double | |
20efa1c2 | 294 | Math::Exp(double x) |
2ac76861 | 295 | { |
9689d97c | 296 | return exp(x) - 1.0; |
2ac76861 | 297 | } |
853310e4 | 298 | |
5625c032 | 299 | void |
300 | statHistLogInit(StatHist * H, int capacity, double min, double max) | |
301 | { | |
20efa1c2 | 302 | statHistInit(H, capacity, Math::Log, Math::Exp, min, max); |
5625c032 | 303 | } |
304 | ||
305 | /* linear histogram for enums */ | |
306 | /* we want to be have [-1,last_enum+1] range to track out of range enums */ | |
b8890359 | 307 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
853310e4 | 308 | static |
309 | #endif | |
310 | double | |
20efa1c2 | 311 | Math::Null(double x) |
2ac76861 | 312 | { |
313 | return x; | |
314 | } | |
ba4f8e5a | 315 | |
5625c032 | 316 | void |
317 | statHistEnumInit(StatHist * H, int last_enum) | |
318 | { | |
20efa1c2 | 319 | statHistInit(H, last_enum + 3, Math::Null, Math::Null, (double) -1, (double) (last_enum + 1 + 1)); |
5625c032 | 320 | } |
173d54ab | 321 | |
322 | void | |
ba4f8e5a | 323 | statHistEnumDumper(StoreEntry * sentry, int idx, double val, double size, int count) |
173d54ab | 324 | { |
325 | if (count) | |
62e76326 | 326 | storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n", |
327 | idx, (int) val, count); | |
173d54ab | 328 | } |
ba4f8e5a | 329 | |
330 | void | |
331 | statHistIntInit(StatHist * H, int n) | |
332 | { | |
20efa1c2 | 333 | statHistInit(H, n, Math::Null, Math::Null, (double) 0, (double) n - 1); |
ba4f8e5a | 334 | } |
335 | ||
336 | void | |
337 | statHistIntDumper(StoreEntry * sentry, int idx, double val, double size, int count) | |
338 | { | |
339 | if (count) | |
62e76326 | 340 | storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count); |
ba4f8e5a | 341 | } |