]>
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 | */ | |
95c297ec | 61 | static hbase_f Log; |
62 | static hbase_f Exp; | |
63 | static hbase_f Null; | |
853310e4 | 64 | #endif |
5625c032 | 65 | |
66 | /* low level init, higher level functions has less params */ | |
67 | static void | |
7d47d8e6 | 68 | statHistInit(StatHist * H, int capacity, hbase_f * val_in, hbase_f * val_out, double min, double max) |
5625c032 | 69 | { |
70 | assert(H); | |
71 | assert(capacity > 0); | |
72 | assert(val_in && val_out); | |
2f266e7a | 73 | /* check before we divide to get scale */ |
74 | assert(val_in(max - min) > 0); | |
e6ccf245 | 75 | H->bins = (int *)xcalloc(capacity, sizeof(int)); |
5625c032 | 76 | H->min = min; |
77 | H->max = max; | |
78 | H->capacity = capacity; | |
79 | H->scale = capacity / val_in(max - min); | |
80 | H->val_in = val_in; | |
81 | H->val_out = val_out; | |
9a2c68b2 | 82 | |
83 | /* HPUX users: If you get one of the assertions below, please send | |
84 | * [at least] the values of all variables involved in the assertions | |
85 | * when reporting a bug! | |
86 | */ | |
87 | ||
2f266e7a | 88 | /* check that functions are valid */ |
89 | /* a min value should go into bin[0] */ | |
90 | assert(statHistBin(H, min) == 0); | |
91 | /* a max value should go into the last bin */ | |
92 | assert(statHistBin(H, max) == H->capacity - 1); | |
93 | /* it is hard to test val_out, here is a crude test */ | |
22ee4794 | 94 | assert(((int) floor(0.99 + statHistVal(H, 0) - min)) == 0); |
5625c032 | 95 | } |
96 | ||
97 | void | |
98 | statHistClean(StatHist * H) | |
99 | { | |
100 | xfree(H->bins); | |
101 | H->bins = NULL; | |
102 | } | |
103 | ||
104 | /* assumes that somebody already called init for Dest */ | |
105 | void | |
106 | statHistCopy(StatHist * Dest, const StatHist * Orig) | |
107 | { | |
95c297ec | 108 | assert(Dest); |
109 | assert(Orig); | |
bf8fe701 | 110 | debugs(62, 3, "statHistCopy: Dest=" << Dest << ", Orig=" << Orig); |
5625c032 | 111 | assert(Dest->bins); |
112 | /* better be safe than sorry */ | |
bf8fe701 | 113 | debugs(62, 3, "statHistCopy: capacity " << Dest->capacity << " " << Orig->capacity); |
5625c032 | 114 | assert(Dest->capacity == Orig->capacity); |
bf8fe701 | 115 | debugs(62, 3, "statHistCopy: min " << Dest->min << " " << Orig->min ); |
95c297ec | 116 | assert(Dest->min == Orig->min); |
bf8fe701 | 117 | debugs(62, 3, "statHistCopy: max " << Dest->max << " " << Orig->max ); |
95c297ec | 118 | assert(Dest->max == Orig->max); |
bf8fe701 | 119 | debugs(62, 3, "statHistCopy: scale " << Dest->scale << " " << Orig->scale ); |
2d6c1ac0 | 120 | assert(fabs(Dest->scale - Orig->scale) < 0.0000001); |
95c297ec | 121 | assert(Dest->val_in == Orig->val_in); |
122 | assert(Dest->val_out == Orig->val_out); | |
5625c032 | 123 | /* actual copy */ |
bf8fe701 | 124 | debugs(62, 3, "statHistCopy: copying " << |
125 | (long int) (Dest->capacity * sizeof(*Dest->bins)) << " bytes to " << | |
126 | Dest->bins << " from " << Orig->bins); | |
127 | ||
2ac76861 | 128 | xmemcpy(Dest->bins, Orig->bins, Dest->capacity * sizeof(*Dest->bins)); |
5625c032 | 129 | } |
130 | ||
ae50d52a | 131 | /* |
132 | * same as statHistCopy but will do nothing if capacities do not match; the | |
133 | * latter happens, for example, when #peers changes during reconfiguration; | |
134 | * if it happens too often we should think about more general solution.. | |
135 | */ | |
136 | void | |
137 | statHistSafeCopy(StatHist * Dest, const StatHist * Orig) | |
138 | { | |
139 | assert(Dest && Orig); | |
140 | assert(Dest->bins); | |
62e76326 | 141 | |
ae50d52a | 142 | if (Dest->capacity == Orig->capacity) |
62e76326 | 143 | statHistCopy(Dest, Orig); |
ae50d52a | 144 | } |
145 | ||
5625c032 | 146 | void |
147 | statHistCount(StatHist * H, double val) | |
148 | { | |
149 | const int bin = statHistBin(H, val); | |
2ac76861 | 150 | assert(H->bins); /* make sure it got initialized */ |
5625c032 | 151 | assert(0 <= bin && bin < H->capacity); |
152 | H->bins[bin]++; | |
153 | } | |
154 | ||
155 | static int | |
156 | statHistBin(const StatHist * H, double v) | |
157 | { | |
158 | int bin; | |
41587298 | 159 | #if BROKEN_STAT_HIST_BIN |
62e76326 | 160 | |
41587298 | 161 | return 0; |
162 | /* NOTREACHED */ | |
163 | #endif | |
62e76326 | 164 | |
2ac76861 | 165 | v -= H->min; /* offset */ |
62e76326 | 166 | |
41587298 | 167 | if (v <= 0.0) /* too small */ |
62e76326 | 168 | return 0; |
169 | ||
9a2c68b2 | 170 | bin = (int) floor(H->scale * H->val_in(v) + 0.5); |
62e76326 | 171 | |
2ac76861 | 172 | if (bin < 0) /* should not happen */ |
62e76326 | 173 | bin = 0; |
174 | ||
2ac76861 | 175 | if (bin >= H->capacity) /* too big */ |
62e76326 | 176 | bin = H->capacity - 1; |
177 | ||
5625c032 | 178 | return bin; |
179 | } | |
180 | ||
181 | static double | |
182 | statHistVal(const StatHist * H, int bin) | |
183 | { | |
4d62b0af | 184 | return H->val_out((double) bin / H->scale) + H->min; |
5625c032 | 185 | } |
186 | ||
187 | double | |
188 | statHistDeltaMedian(const StatHist * A, const StatHist * B) | |
04a28d46 | 189 | { |
190 | return statHistDeltaPctile(A, B, 0.5); | |
191 | } | |
192 | ||
193 | double | |
194 | statHistDeltaPctile(const StatHist * A, const StatHist * B, double pctile) | |
5625c032 | 195 | { |
196 | int i; | |
197 | int s1 = 0; | |
198 | int h = 0; | |
199 | int a = 0; | |
200 | int b = 0; | |
201 | int I = 0; | |
202 | int J = A->capacity; | |
203 | int K; | |
204 | double f; | |
e6ccf245 | 205 | int *D = (int *)xcalloc(A->capacity, sizeof(int)); |
5625c032 | 206 | assert(A->capacity == B->capacity); |
62e76326 | 207 | |
5625c032 | 208 | for (i = 0; i < A->capacity; i++) { |
62e76326 | 209 | D[i] = B->bins[i] - A->bins[i]; |
210 | assert(D[i] >= 0); | |
5625c032 | 211 | } |
62e76326 | 212 | |
5625c032 | 213 | for (i = 0; i < A->capacity; i++) |
62e76326 | 214 | s1 += D[i]; |
215 | ||
04a28d46 | 216 | h = int(s1 * pctile); |
62e76326 | 217 | |
5625c032 | 218 | for (i = 0; i < A->capacity; i++) { |
62e76326 | 219 | J = i; |
220 | b += D[J]; | |
221 | ||
222 | if (a <= h && h <= b) | |
223 | break; | |
224 | ||
225 | I = i; | |
226 | ||
227 | a += D[I]; | |
5625c032 | 228 | } |
62e76326 | 229 | |
5625c032 | 230 | xfree(D); |
62e76326 | 231 | |
5625c032 | 232 | if (s1 == 0) |
62e76326 | 233 | return 0.0; |
234 | ||
6a6c3b50 | 235 | if (a > h) |
62e76326 | 236 | return 0.0; |
237 | ||
6a6c3b50 | 238 | if (a >= b) |
62e76326 | 239 | return 0.0; |
240 | ||
6a6c3b50 | 241 | if (I >= J) |
62e76326 | 242 | return 0.0; |
243 | ||
5625c032 | 244 | f = (h - a) / (b - a); |
62e76326 | 245 | |
9a2c68b2 | 246 | K = (int) floor(f * (double) (J - I) + I); |
62e76326 | 247 | |
5625c032 | 248 | return statHistVal(A, K); |
249 | } | |
250 | ||
251 | static void | |
252 | statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count) | |
253 | { | |
254 | if (count) | |
62e76326 | 255 | storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n", |
256 | idx, val, count, count / size); | |
5625c032 | 257 | } |
258 | ||
259 | void | |
eeb423fb | 260 | statHistDump(const StatHist * H, StoreEntry * sentry, StatHistBinDumper * bd) |
5625c032 | 261 | { |
262 | int i; | |
263 | double left_border = H->min; | |
62e76326 | 264 | |
5625c032 | 265 | if (!bd) |
62e76326 | 266 | bd = statHistBinDumper; |
267 | ||
5625c032 | 268 | for (i = 0; i < H->capacity; i++) { |
62e76326 | 269 | const double right_border = statHistVal(H, i + 1); |
270 | assert(right_border - left_border > 0.0); | |
271 | bd(sentry, i, left_border, right_border - left_border, H->bins[i]); | |
272 | left_border = right_border; | |
5625c032 | 273 | } |
274 | } | |
275 | ||
276 | /* log based histogram */ | |
853310e4 | 277 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
278 | static | |
279 | #endif | |
280 | double | |
2ac76861 | 281 | Log(double x) |
282 | { | |
9689d97c | 283 | assert((x + 1.0) >= 0.0); |
284 | return log(x + 1.0); | |
2ac76861 | 285 | } |
853310e4 | 286 | |
b8890359 | 287 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
853310e4 | 288 | static |
289 | #endif | |
290 | double | |
2ac76861 | 291 | Exp(double x) |
292 | { | |
9689d97c | 293 | return exp(x) - 1.0; |
2ac76861 | 294 | } |
853310e4 | 295 | |
5625c032 | 296 | void |
297 | statHistLogInit(StatHist * H, int capacity, double min, double max) | |
298 | { | |
95c297ec | 299 | statHistInit(H, capacity, Log, Exp, min, max); |
5625c032 | 300 | } |
301 | ||
302 | /* linear histogram for enums */ | |
303 | /* we want to be have [-1,last_enum+1] range to track out of range enums */ | |
b8890359 | 304 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
853310e4 | 305 | static |
306 | #endif | |
307 | double | |
2ac76861 | 308 | Null(double x) |
309 | { | |
310 | return x; | |
311 | } | |
ba4f8e5a | 312 | |
5625c032 | 313 | void |
314 | statHistEnumInit(StatHist * H, int last_enum) | |
315 | { | |
95c297ec | 316 | statHistInit(H, last_enum + 3, Null, Null, (double) -1, (double) (last_enum + 1 + 1)); |
5625c032 | 317 | } |
173d54ab | 318 | |
319 | void | |
ba4f8e5a | 320 | statHistEnumDumper(StoreEntry * sentry, int idx, double val, double size, int count) |
173d54ab | 321 | { |
322 | if (count) | |
62e76326 | 323 | storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n", |
324 | idx, (int) val, count); | |
173d54ab | 325 | } |
ba4f8e5a | 326 | |
327 | void | |
328 | statHistIntInit(StatHist * H, int n) | |
329 | { | |
c68e9c6b | 330 | statHistInit(H, n, Null, Null, (double) 0, (double) n - 1); |
ba4f8e5a | 331 | } |
332 | ||
333 | void | |
334 | statHistIntDumper(StoreEntry * sentry, int idx, double val, double size, int count) | |
335 | { | |
336 | if (count) | |
62e76326 | 337 | storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count); |
ba4f8e5a | 338 | } |