]>
Commit | Line | Data |
---|---|---|
2ac76861 | 1 | |
5625c032 | 2 | /* |
528b2c61 | 3 | * $Id: StatHist.cc,v 1.29 2003/01/23 00:37:14 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__) |
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", |
e900b417 | 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); |
5625c032 | 121 | assert(Dest->scale == Orig->scale); |
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", |
e1b3055c | 126 | (long int) (Dest->capacity * sizeof(*Dest->bins)), |
95c297ec | 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); | |
142 | if (Dest->capacity == Orig->capacity) | |
143 | statHistCopy(Dest, Orig); | |
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 |
160 | return 0; | |
161 | /* NOTREACHED */ | |
162 | #endif | |
2ac76861 | 163 | v -= H->min; /* offset */ |
41587298 | 164 | if (v <= 0.0) /* too small */ |
5625c032 | 165 | return 0; |
9a2c68b2 | 166 | bin = (int) floor(H->scale * H->val_in(v) + 0.5); |
2ac76861 | 167 | if (bin < 0) /* should not happen */ |
5625c032 | 168 | bin = 0; |
2ac76861 | 169 | if (bin >= H->capacity) /* too big */ |
5625c032 | 170 | bin = H->capacity - 1; |
171 | return bin; | |
172 | } | |
173 | ||
174 | static double | |
175 | statHistVal(const StatHist * H, int bin) | |
176 | { | |
4d62b0af | 177 | return H->val_out((double) bin / H->scale) + H->min; |
5625c032 | 178 | } |
179 | ||
180 | double | |
181 | statHistDeltaMedian(const StatHist * A, const StatHist * B) | |
182 | { | |
183 | int i; | |
184 | int s1 = 0; | |
185 | int h = 0; | |
186 | int a = 0; | |
187 | int b = 0; | |
188 | int I = 0; | |
189 | int J = A->capacity; | |
190 | int K; | |
191 | double f; | |
e6ccf245 | 192 | int *D = (int *)xcalloc(A->capacity, sizeof(int)); |
5625c032 | 193 | assert(A->capacity == B->capacity); |
194 | for (i = 0; i < A->capacity; i++) { | |
195 | D[i] = B->bins[i] - A->bins[i]; | |
196 | assert(D[i] >= 0); | |
197 | } | |
198 | for (i = 0; i < A->capacity; i++) | |
199 | s1 += D[i]; | |
200 | h = s1 >> 1; | |
201 | for (i = 0; i < A->capacity; i++) { | |
202 | J = i; | |
203 | b += D[J]; | |
204 | if (a <= h && h <= b) | |
205 | break; | |
206 | I = i; | |
207 | a += D[I]; | |
208 | } | |
209 | xfree(D); | |
210 | if (s1 == 0) | |
211 | return 0.0; | |
6a6c3b50 | 212 | if (a > h) |
5625c032 | 213 | return 0.0; |
6a6c3b50 | 214 | if (a >= b) |
5625c032 | 215 | return 0.0; |
6a6c3b50 | 216 | if (I >= J) |
5625c032 | 217 | return 0.0; |
5625c032 | 218 | f = (h - a) / (b - a); |
9a2c68b2 | 219 | K = (int) floor(f * (double) (J - I) + I); |
5625c032 | 220 | return statHistVal(A, K); |
221 | } | |
222 | ||
223 | static void | |
224 | statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count) | |
225 | { | |
226 | if (count) | |
227 | storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n", | |
2ac76861 | 228 | idx, val, count, count / size); |
5625c032 | 229 | } |
230 | ||
231 | void | |
eeb423fb | 232 | statHistDump(const StatHist * H, StoreEntry * sentry, StatHistBinDumper * bd) |
5625c032 | 233 | { |
234 | int i; | |
235 | double left_border = H->min; | |
236 | if (!bd) | |
237 | bd = statHistBinDumper; | |
238 | for (i = 0; i < H->capacity; i++) { | |
2ac76861 | 239 | const double right_border = statHistVal(H, i + 1); |
5625c032 | 240 | assert(right_border - left_border > 0.0); |
241 | bd(sentry, i, left_border, right_border - left_border, H->bins[i]); | |
242 | left_border = right_border; | |
243 | } | |
244 | } | |
245 | ||
246 | /* log based histogram */ | |
853310e4 | 247 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
248 | static | |
249 | #endif | |
250 | double | |
2ac76861 | 251 | Log(double x) |
252 | { | |
9689d97c | 253 | assert((x + 1.0) >= 0.0); |
254 | return log(x + 1.0); | |
2ac76861 | 255 | } |
853310e4 | 256 | |
b8890359 | 257 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
853310e4 | 258 | static |
259 | #endif | |
260 | double | |
2ac76861 | 261 | Exp(double x) |
262 | { | |
9689d97c | 263 | return exp(x) - 1.0; |
2ac76861 | 264 | } |
853310e4 | 265 | |
5625c032 | 266 | void |
267 | statHistLogInit(StatHist * H, int capacity, double min, double max) | |
268 | { | |
95c297ec | 269 | statHistInit(H, capacity, Log, Exp, min, max); |
5625c032 | 270 | } |
271 | ||
272 | /* linear histogram for enums */ | |
273 | /* we want to be have [-1,last_enum+1] range to track out of range enums */ | |
b8890359 | 274 | #if !defined(_SQUID_HPUX_) || !defined(__GNUC__) |
853310e4 | 275 | static |
276 | #endif | |
277 | double | |
2ac76861 | 278 | Null(double x) |
279 | { | |
280 | return x; | |
281 | } | |
ba4f8e5a | 282 | |
5625c032 | 283 | void |
284 | statHistEnumInit(StatHist * H, int last_enum) | |
285 | { | |
95c297ec | 286 | statHistInit(H, last_enum + 3, Null, Null, (double) -1, (double) (last_enum + 1 + 1)); |
5625c032 | 287 | } |
173d54ab | 288 | |
289 | void | |
ba4f8e5a | 290 | statHistEnumDumper(StoreEntry * sentry, int idx, double val, double size, int count) |
173d54ab | 291 | { |
292 | if (count) | |
4b4cd312 | 293 | storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n", |
294 | idx, (int) val, count); | |
173d54ab | 295 | } |
ba4f8e5a | 296 | |
297 | void | |
298 | statHistIntInit(StatHist * H, int n) | |
299 | { | |
c68e9c6b | 300 | statHistInit(H, n, Null, Null, (double) 0, (double) n - 1); |
ba4f8e5a | 301 | } |
302 | ||
303 | void | |
304 | statHistIntDumper(StoreEntry * sentry, int idx, double val, double size, int count) | |
305 | { | |
306 | if (count) | |
307 | storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count); | |
308 | } |