src/StatHist.cc

   1
   2 /*
   3  * $Id: StatHist.cc,v 1.34 2007/04/28 22:26:37 hno 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     debugs(62, 3, "statHistCopy: Dest=" << Dest << ", Orig=" << Orig);
 111     assert(Dest->bins);
 112     /* better be safe than sorry */
 113     debugs(62, 3, "statHistCopy: capacity " << Dest->capacity << " " << Orig->capacity);
 114     assert(Dest->capacity == Orig->capacity);
 115     debugs(62, 3, "statHistCopy: min " << Dest->min << " " << Orig->min  );
 116     assert(Dest->min == Orig->min);
 117     debugs(62, 3, "statHistCopy: max " << Dest->max << " " << Orig->max  );
 118     assert(Dest->max == Orig->max);
 119     debugs(62, 3, "statHistCopy: scale " << Dest->scale << " " << Orig->scale  );
 120     assert(fabs(Dest->scale - Orig->scale) < 0.0000001);
 121     assert(Dest->val_in == Orig->val_in);
 122     assert(Dest->val_out == Orig->val_out);
 123     /* actual copy */
 124     debugs(62, 3, "statHistCopy: copying " <<
 125            (long int) (Dest->capacity * sizeof(*Dest->bins)) << " bytes to " <<
 126            Dest->bins << " from " << Orig->bins);
 127
 128     xmemcpy(Dest->bins, Orig->bins, Dest->capacity * sizeof(*Dest->bins));
 129 }
 130
 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);
 141
 142     if (Dest->capacity == Orig->capacity)
 143         statHistCopy(Dest, Orig);
 144 }
 145
 146 void
 147 statHistCount(StatHist * H, double val)
 148 {
 149     const int bin = statHistBin(H, val);
 150     assert(H->bins);            /* make sure it got initialized */
 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;
 159 #if BROKEN_STAT_HIST_BIN
 160
 161     return 0;
 162     /* NOTREACHED */
 163 #endif
 164
 165     v -= H->min;                /* offset */
 166
 167     if (v <= 0.0)               /* too small */
 168         return 0;
 169
 170     bin = (int) floor(H->scale * H->val_in(v) + 0.5);
 171
 172     if (bin < 0)                /* should not happen */
 173         bin = 0;
 174
 175     if (bin >= H->capacity)     /* too big */
 176         bin = H->capacity - 1;
 177
 178     return bin;
 179 }
 180
 181 static double
 182 statHistVal(const StatHist * H, int bin)
 183 {
 184     return H->val_out((double) bin / H->scale) + H->min;
 185 }
 186
 187 double
 188 statHistDeltaMedian(const StatHist * A, const StatHist * B)
 189 {
 190     return statHistDeltaPctile(A, B, 0.5);
 191 }
 192
 193 double
 194 statHistDeltaPctile(const StatHist * A, const StatHist * B, double pctile)
 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;
 205     int *D = (int *)xcalloc(A->capacity, sizeof(int));
 206     assert(A->capacity == B->capacity);
 207
 208     for (i = 0; i < A->capacity; i++) {
 209         D[i] = B->bins[i] - A->bins[i];
 210         assert(D[i] >= 0);
 211     }
 212
 213     for (i = 0; i < A->capacity; i++)
 214         s1 += D[i];
 215
 216     h = int(s1 * pctile);
 217
 218     for (i = 0; i < A->capacity; i++) {
 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];
 228     }
 229
 230     xfree(D);
 231
 232     if (s1 == 0)
 233         return 0.0;
 234
 235     if (a > h)
 236         return 0.0;
 237
 238     if (a >= b)
 239         return 0.0;
 240
 241     if (I >= J)
 242         return 0.0;
 243
 244     f = (h - a) / (b - a);
 245
 246     K = (int) floor(f * (double) (J - I) + I);
 247
 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)
 255         storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n",
 256                           idx, val, count, count / size);
 257 }
 258
 259 void
 260 statHistDump(const StatHist * H, StoreEntry * sentry, StatHistBinDumper * bd)
 261 {
 262     int i;
 263     double left_border = H->min;
 264
 265     if (!bd)
 266         bd = statHistBinDumper;
 267
 268     for (i = 0; i < H->capacity; i++) {
 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;
 273     }
 274 }
 275
 276 /* log based histogram */
 277 #if !defined(_SQUID_HPUX_) || !defined(__GNUC__)
 278 static
 279 #endif
 280 double
 281 Log(double x)
 282 {
 283     assert((x + 1.0) >= 0.0);
 284     return log(x + 1.0);
 285 }
 286
 287 #if !defined(_SQUID_HPUX_) || !defined(__GNUC__)
 288 static
 289 #endif
 290 double
 291 Exp(double x)
 292 {
 293     return exp(x) - 1.0;
 294 }
 295
 296 void
 297 statHistLogInit(StatHist * H, int capacity, double min, double max)
 298 {
 299     statHistInit(H, capacity, Log, Exp, min, max);
 300 }
 301
 302 /* linear histogram for enums */
 303 /* we want to be have [-1,last_enum+1] range to track out of range enums */
 304 #if !defined(_SQUID_HPUX_) || !defined(__GNUC__)
 305 static
 306 #endif
 307 double
 308 Null(double x)
 309 {
 310     return x;
 311 }
 312
 313 void
 314 statHistEnumInit(StatHist * H, int last_enum)
 315 {
 316     statHistInit(H, last_enum + 3, Null, Null, (double) -1, (double) (last_enum + 1 + 1));
 317 }
 318
 319 void
 320 statHistEnumDumper(StoreEntry * sentry, int idx, double val, double size, int count)
 321 {
 322     if (count)
 323         storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n",
 324                           idx, (int) val, count);
 325 }
 326
 327 void
 328 statHistIntInit(StatHist * H, int n)
 329 {
 330     statHistInit(H, n, Null, Null, (double) 0, (double) n - 1);
 331 }
 332
 333 void
 334 statHistIntDumper(StoreEntry * sentry, int idx, double val, double size, int count)
 335 {
 336     if (count)
 337         storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count);
 338 }