]>
Commit | Line | Data |
---|---|---|
2ac76861 | 1 | |
5625c032 | 2 | /* |
2d6c1ac0 | 3 | * $Id: StatHist.cc,v 1.31 2003/10/16 13:14:49 robertc Exp $ |
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. | |
24 | * | |
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. | |
29 | * | |
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: | |
38 | * | |
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 | * | |
42 | * In practice, the requirements are less strict, | |
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 */ | |
9a2c68b2 | 94 | assert(((int) floor(0.99L + 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); | |
7d47d8e6 | 110 | debug(62, 3) ("statHistCopy: Dest=%p, Orig=%p\n", Dest, Orig); |
5625c032 | 111 | assert(Dest->bins); |
112 | /* better be safe than sorry */ | |
7d47d8e6 | 113 | debug(62, 3) ("statHistCopy: capacity %d %d\n", |
62e76326 | 114 | Dest->capacity, Orig->capacity); |
5625c032 | 115 | assert(Dest->capacity == Orig->capacity); |
7d47d8e6 | 116 | debug(62, 3) ("statHistCopy: min %f %f\n", Dest->min, Orig->min); |
95c297ec | 117 | assert(Dest->min == Orig->min); |
7d47d8e6 | 118 | debug(62, 3) ("statHistCopy: max %f %f\n", Dest->max, Orig->max); |
95c297ec | 119 | assert(Dest->max == Orig->max); |
7d47d8e6 | 120 | debug(62, 3) ("statHistCopy: scale %f %f\n", Dest->scale, Orig->scale); |
2d6c1ac0 | 121 | assert(fabs(Dest->scale - Orig->scale) < 0.0000001); |
95c297ec | 122 | assert(Dest->val_in == Orig->val_in); |
123 | assert(Dest->val_out == Orig->val_out); | |
5625c032 | 124 | /* actual copy */ |
ed19251a | 125 | debug(62, 3) ("statHistCopy: copying %ld bytes to %p from %p\n", |
62e76326 | 126 | (long int) (Dest->capacity * sizeof(*Dest->bins)), |
127 | Dest->bins, | |
128 | Orig->bins); | |
2ac76861 | 129 | xmemcpy(Dest->bins, Orig->bins, Dest->capacity * sizeof(*Dest->bins)); |
5625c032 | 130 | } |
131 | ||
ae50d52a | 132 | /* |
133 | * same as statHistCopy but will do nothing if capacities do not match; the | |
134 | * latter happens, for example, when #peers changes during reconfiguration; | |
135 | * if it happens too often we should think about more general solution.. | |
136 | */ | |
137 | void | |
138 | statHistSafeCopy(StatHist * Dest, const StatHist * Orig) | |
139 | { | |
140 | assert(Dest && Orig); | |
141 | assert(Dest->bins); | |
62e76326 | 142 | |
ae50d52a | 143 | if (Dest->capacity == Orig->capacity) |
62e76326 | 144 | statHistCopy(Dest, Orig); |
ae50d52a | 145 | } |
146 | ||
5625c032 | 147 | void |
148 | statHistCount(StatHist * H, double val) | |
149 | { | |
150 | const int bin = statHistBin(H, val); | |
2ac76861 | 151 | assert(H->bins); /* make sure it got initialized */ |
5625c032 | 152 | assert(0 <= bin && bin < H->capacity); |
153 | H->bins[bin]++; | |
154 | } | |
155 | ||
156 | static int | |
157 | statHistBin(const StatHist * H, double v) | |
158 | { | |
159 | int bin; | |
41587298 | 160 | #if BROKEN_STAT_HIST_BIN |
62e76326 | 161 | |
41587298 | 162 | return 0; |
163 | /* NOTREACHED */ | |
164 | #endif | |
62e76326 | 165 | |
2ac76861 | 166 | v -= H->min; /* offset */ |
62e76326 | 167 | |
41587298 | 168 | if (v <= 0.0) /* too small */ |
62e76326 | 169 | return 0; |
170 | ||
9a2c68b2 | 171 | bin = (int) floor(H->scale * H->val_in(v) + 0.5); |
62e76326 | 172 | |
2ac76861 | 173 | if (bin < 0) /* should not happen */ |
62e76326 | 174 | bin = 0; |
175 | ||
2ac76861 | 176 | if (bin >= H->capacity) /* too big */ |
62e76326 | 177 | bin = H->capacity - 1; |
178 | ||
5625c032 | 179 | return bin; |
180 | } | |
181 | ||
182 | static double | |
183 | statHistVal(const StatHist * H, int bin) | |
184 | { | |
4d62b0af | 185 | return H->val_out((double) bin / H->scale) + H->min; |
5625c032 | 186 | } |
187 | ||
188 | double | |
189 | statHistDeltaMedian(const StatHist * A, const StatHist * B) | |
190 | { | |
191 | int i; | |
192 | int s1 = 0; | |
193 | int h = 0; | |
194 | int a = 0; | |
195 | int b = 0; | |
196 | int I = 0; | |
197 | int J = A->capacity; | |
198 | int K; | |
199 | double f; | |
e6ccf245 | 200 | int *D = (int *)xcalloc(A->capacity, sizeof(int)); |
5625c032 | 201 | assert(A->capacity == B->capacity); |
62e76326 | 202 | |
5625c032 | 203 | for (i = 0; i < A->capacity; i++) { |
62e76326 | 204 | D[i] = B->bins[i] - A->bins[i]; |
205 | assert(D[i] >= 0); | |
5625c032 | 206 | } |
62e76326 | 207 | |
5625c032 | 208 | for (i = 0; i < A->capacity; i++) |
62e76326 | 209 | s1 += D[i]; |
210 | ||
5625c032 | 211 | h = s1 >> 1; |
62e76326 | 212 | |
5625c032 | 213 | for (i = 0; i < A->capacity; i++) { |
62e76326 | 214 | J = i; |
215 | b += D[J]; | |
216 | ||
217 | if (a <= h && h <= b) | |
218 | break; | |
219 | ||
220 | I = i; | |
221 | ||
222 | a += D[I]; | |
5625c032 | 223 | } |
62e76326 | 224 | |
5625c032 | 225 | xfree(D); |
62e76326 | 226 | |
5625c032 | 227 | if (s1 == 0) |
62e76326 | 228 | return 0.0; |
229 | ||
6a6c3b50 | 230 | if (a > h) |
62e76326 | 231 | return 0.0; |
232 | ||
6a6c3b50 | 233 | if (a >= b) |
62e76326 | 234 | return 0.0; |
235 | ||
6a6c3b50 | 236 | if (I >= J) |
62e76326 | 237 | return 0.0; |
238 | ||
5625c032 | 239 | f = (h - a) / (b - a); |
62e76326 | 240 | |
9a2c68b2 | 241 | K = (int) floor(f * (double) (J - I) + I); |
62e76326 | 242 | |
5625c032 | 243 | return statHistVal(A, K); |
244 | } | |
245 | ||
246 | static void | |
247 | statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count) | |
248 | { | |
249 | if (count) | |
62e76326 | 250 | storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n", |
251 | idx, val, count, count / size); | |
5625c032 | 252 | } |
253 | ||
254 | void | |
eeb423fb | 255 | statHistDump(const StatHist * H, StoreEntry * sentry, StatHistBinDumper * bd) |
5625c032 | 256 | { |
257 | int i; | |
258 | double left_border = H->min; | |
62e76326 | 259 | |
5625c032 | 260 | if (!bd) |
62e76326 | 261 | bd = statHistBinDumper; |
262 | ||
5625c032 | 263 | for (i = 0; i < H->capacity; i++) { |
62e76326 | 264 | const double right_border = statHistVal(H, i + 1); |
265 | assert(right_border - left_border > 0.0); | |
266 | bd(sentry, i, left_border, right_border - left_border, H->bins[i]); | |
267 | left_border = right_border; | |
5625c032 | 268 | } |
269 | } | |
270 | ||
271 | /* log based histogram */ | |
853310e4 | 272 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
273 | static | |
274 | #endif | |
275 | double | |
2ac76861 | 276 | Log(double x) |
277 | { | |
9689d97c | 278 | assert((x + 1.0) >= 0.0); |
279 | return log(x + 1.0); | |
2ac76861 | 280 | } |
853310e4 | 281 | |
b8890359 | 282 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
853310e4 | 283 | static |
284 | #endif | |
285 | double | |
2ac76861 | 286 | Exp(double x) |
287 | { | |
9689d97c | 288 | return exp(x) - 1.0; |
2ac76861 | 289 | } |
853310e4 | 290 | |
5625c032 | 291 | void |
292 | statHistLogInit(StatHist * H, int capacity, double min, double max) | |
293 | { | |
95c297ec | 294 | statHistInit(H, capacity, Log, Exp, min, max); |
5625c032 | 295 | } |
296 | ||
297 | /* linear histogram for enums */ | |
298 | /* we want to be have [-1,last_enum+1] range to track out of range enums */ | |
b8890359 | 299 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
853310e4 | 300 | static |
301 | #endif | |
302 | double | |
2ac76861 | 303 | Null(double x) |
304 | { | |
305 | return x; | |
306 | } | |
ba4f8e5a | 307 | |
5625c032 | 308 | void |
309 | statHistEnumInit(StatHist * H, int last_enum) | |
310 | { | |
95c297ec | 311 | statHistInit(H, last_enum + 3, Null, Null, (double) -1, (double) (last_enum + 1 + 1)); |
5625c032 | 312 | } |
173d54ab | 313 | |
314 | void | |
ba4f8e5a | 315 | statHistEnumDumper(StoreEntry * sentry, int idx, double val, double size, int count) |
173d54ab | 316 | { |
317 | if (count) | |
62e76326 | 318 | storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n", |
319 | idx, (int) val, count); | |
173d54ab | 320 | } |
ba4f8e5a | 321 | |
322 | void | |
323 | statHistIntInit(StatHist * H, int n) | |
324 | { | |
c68e9c6b | 325 | statHistInit(H, n, Null, Null, (double) 0, (double) n - 1); |
ba4f8e5a | 326 | } |
327 | ||
328 | void | |
329 | statHistIntDumper(StoreEntry * sentry, int idx, double val, double size, int count) | |
330 | { | |
331 | if (count) | |
62e76326 | 332 | storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count); |
ba4f8e5a | 333 | } |