src/StatHist.cc

   1
   2 /*
   3  * $Id: StatHist.cc,v 1.33 2007/04/13 22:46:03 wessels Exp $
   4  *
   5  * DEBUG: section 62    Generic Histogram
   6  * AUTHOR: Duane Wessels
   7  *
   8  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   9  * ----------------------------------------------------------
  10  *
  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.
  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
  32  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  33  *
  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"
  49 #include "Store.h"
  50
  51 /* Local functions */
  52 static void statHistInit(StatHist * H, int capacity, hbase_f * val_in, hbase_f * val_out, double min, double max);
  53 static int statHistBin(const StatHist * H, double v);
  54 static double statHistVal(const StatHist * H, int bin);
  55 static StatHistBinDumper statHistBinDumper;
  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  */
  61 static hbase_f Log;
  62 static hbase_f Exp;
  63 static hbase_f Null;
  64 #endif
  65
  66 /* low level init, higher level functions has less params */
  67 static void
  68 statHistInit(StatHist * H, int capacity, hbase_f * val_in, hbase_f * val_out, double min, double max)
  69 {
  70     assert(H);
  71     assert(capacity > 0);
  72     assert(val_in && val_out);
  73     /* check before we divide to get scale */
  74     assert(val_in(max - min) > 0);
  75     H->bins = (int *)xcalloc(capacity, sizeof(int));
  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;
  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
  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 */
  94     assert(((int) floor(0.99 + statHistVal(H, 0) - min)) == 0);
  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 {
 108     assert(Dest);
 109     assert(Orig);
 110     debug(62, 3) ("statHistCopy: Dest=%p, Orig=%p\n", Dest, Orig);
 111     assert(Dest->bins);
 112     /* better be safe than sorry */
 113     debug(62, 3) ("statHistCopy: capacity %d %d\n",
 114                   Dest->capacity, Orig->capacity);
 115     assert(Dest->capacity == Orig->capacity);
 116     debug(62, 3) ("statHistCopy: min %f %f\n", Dest->min, Orig->min);
 117     assert(Dest->min == Orig->min);
 118     debug(62, 3) ("statHistCopy: max %f %f\n", Dest->max, Orig->max);
 119     assert(Dest->max == Orig->max);
 120     debug(62, 3) ("statHistCopy: scale %f %f\n", Dest->scale, Orig->scale);
 121     assert(fabs(Dest->scale - Orig->scale) < 0.0000001);
 122     assert(Dest->val_in == Orig->val_in);
 123     assert(Dest->val_out == Orig->val_out);
 124     /* actual copy */
 125     debug(62, 3) ("statHistCopy: copying %ld bytes to %p from %p\n",
 126                   (long int) (Dest->capacity * sizeof(*Dest->bins)),
 127                   Dest->bins,
 128                   Orig->bins);
 129     xmemcpy(Dest->bins, Orig->bins, Dest->capacity * sizeof(*Dest->bins));
 130 }
 131
 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
 143     if (Dest->capacity == Orig->capacity)
 144         statHistCopy(Dest, Orig);
 145 }
 146
 147 void
 148 statHistCount(StatHist * H, double val)
 149 {
 150     const int bin = statHistBin(H, val);
 151     assert(H->bins);            /* make sure it got initialized */
 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;
 160 #if BROKEN_STAT_HIST_BIN
 161
 162     return 0;
 163     /* NOTREACHED */
 164 #endif
 165
 166     v -= H->min;                /* offset */
 167
 168     if (v <= 0.0)               /* too small */
 169         return 0;
 170
 171     bin = (int) floor(H->scale * H->val_in(v) + 0.5);
 172
 173     if (bin < 0)                /* should not happen */
 174         bin = 0;
 175
 176     if (bin >= H->capacity)     /* too big */
 177         bin = H->capacity - 1;
 178
 179     return bin;
 180 }
 181
 182 static double
 183 statHistVal(const StatHist * H, int bin)
 184 {
 185     return H->val_out((double) bin / H->scale) + H->min;
 186 }
 187
 188 double
 189 statHistDeltaMedian(const StatHist * A, const StatHist * B)
 190 {
 191     return statHistDeltaPctile(A, B, 0.5);
 192 }
 193
 194 double
 195 statHistDeltaPctile(const StatHist * A, const StatHist * B, double pctile)
 196 {
 197     int i;
 198     int s1 = 0;
 199     int h = 0;
 200     int a = 0;
 201     int b = 0;
 202     int I = 0;
 203     int J = A->capacity;
 204     int K;
 205     double f;
 206     int *D = (int *)xcalloc(A->capacity, sizeof(int));
 207     assert(A->capacity == B->capacity);
 208
 209     for (i = 0; i < A->capacity; i++) {
 210         D[i] = B->bins[i] - A->bins[i];
 211         assert(D[i] >= 0);
 212     }
 213
 214     for (i = 0; i < A->capacity; i++)
 215         s1 += D[i];
 216
 217     h = int(s1 * pctile);
 218
 219     for (i = 0; i < A->capacity; i++) {
 220         J = i;
 221         b += D[J];
 222
 223         if (a <= h && h <= b)
 224             break;
 225
 226         I = i;
 227
 228         a += D[I];
 229     }
 230
 231     xfree(D);
 232
 233     if (s1 == 0)
 234         return 0.0;
 235
 236     if (a > h)
 237         return 0.0;
 238
 239     if (a >= b)
 240         return 0.0;
 241
 242     if (I >= J)
 243         return 0.0;
 244
 245     f = (h - a) / (b - a);
 246
 247     K = (int) floor(f * (double) (J - I) + I);
 248
 249     return statHistVal(A, K);
 250 }
 251
 252 static void
 253 statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count)
 254 {
 255     if (count)
 256         storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n",
 257                           idx, val, count, count / size);
 258 }
 259
 260 void
 261 statHistDump(const StatHist * H, StoreEntry * sentry, StatHistBinDumper * bd)
 262 {
 263     int i;
 264     double left_border = H->min;
 265
 266     if (!bd)
 267         bd = statHistBinDumper;
 268
 269     for (i = 0; i < H->capacity; i++) {
 270         const double right_border = statHistVal(H, i + 1);
 271         assert(right_border - left_border > 0.0);
 272         bd(sentry, i, left_border, right_border - left_border, H->bins[i]);
 273         left_border = right_border;
 274     }
 275 }
 276
 277 /* log based histogram */
 278 #if !defined(_SQUID_HPUX_) || !defined(__GNUC__)
 279 static
 280 #endif
 281 double
 282 Log(double x)
 283 {
 284     assert((x + 1.0) >= 0.0);
 285     return log(x + 1.0);
 286 }
 287
 288 #if !defined(_SQUID_HPUX_) || !defined(__GNUC__)
 289 static
 290 #endif
 291 double
 292 Exp(double x)
 293 {
 294     return exp(x) - 1.0;
 295 }
 296
 297 void
 298 statHistLogInit(StatHist * H, int capacity, double min, double max)
 299 {
 300     statHistInit(H, capacity, Log, Exp, min, max);
 301 }
 302
 303 /* linear histogram for enums */
 304 /* we want to be have [-1,last_enum+1] range to track out of range enums */
 305 #if !defined(_SQUID_HPUX_) || !defined(__GNUC__)
 306 static
 307 #endif
 308 double
 309 Null(double x)
 310 {
 311     return x;
 312 }
 313
 314 void
 315 statHistEnumInit(StatHist * H, int last_enum)
 316 {
 317     statHistInit(H, last_enum + 3, Null, Null, (double) -1, (double) (last_enum + 1 + 1));
 318 }
 319
 320 void
 321 statHistEnumDumper(StoreEntry * sentry, int idx, double val, double size, int count)
 322 {
 323     if (count)
 324         storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n",
 325                           idx, (int) val, count);
 326 }
 327
 328 void
 329 statHistIntInit(StatHist * H, int n)
 330 {
 331     statHistInit(H, n, Null, Null, (double) 0, (double) n - 1);
 332 }
 333
 334 void
 335 statHistIntDumper(StoreEntry * sentry, int idx, double val, double size, int count)
 336 {
 337     if (count)
 338         storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count);
 339 }