contrib/unbound/util/timehist.c

   1 /*
   2  * util/timehist.c - make histogram of time values.
   3  *
   4  * Copyright (c) 2007, NLnet Labs. All rights reserved.
   5  *
   6  * This software is open source.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * Redistributions of source code must retain the above copyright notice,
  13  * this list of conditions and the following disclaimer.
  14  *
  15  * Redistributions in binary form must reproduce the above copyright notice,
  16  * this list of conditions and the following disclaimer in the documentation
  17  * and/or other materials provided with the distribution.
  18  *
  19  * Neither the name of the NLNET LABS nor the names of its contributors may
  20  * be used to endorse or promote products derived from this software without
  21  * specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  25  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  26  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
  27  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  28  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  29  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  30  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  31  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  32  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33  * POSSIBILITY OF SUCH DAMAGE.
  34  */
  35
  36 /**
  37  * \file
  38  *
  39  * This file contains functions to make a histogram of time values.
  40  */
  41 #include "config.h"
  42 #ifdef HAVE_TIME_H
  43 #include <time.h>
  44 #endif
  45 #include <sys/time.h>
  46 #include "util/timehist.h"
  47 #include "util/log.h"
  48
  49 /** special timestwo operation for time values in histogram setup */
  50 static void
  51 timestwo(struct timeval* v)
  52 {
  53 #ifndef S_SPLINT_S
  54         if(v->tv_sec == 0 && v->tv_usec == 0) {
  55                 v->tv_usec = 1;
  56                 return;
  57         }
  58         v->tv_sec *= 2;
  59         v->tv_usec *= 2;
  60         if(v->tv_usec == 1024*1024) {
  61                 /* nice values and easy to compute */
  62                 v->tv_sec = 1;
  63                 v->tv_usec = 0;
  64         }
  65 #endif
  66 }
  67
  68 /** do setup exponentially */
  69 static void
  70 dosetup(struct timehist* hist)
  71 {
  72         struct timeval last;
  73         size_t i;
  74         memset(&last, 0, sizeof(last));
  75         for(i=0; i<hist->num; i++) {
  76                 hist->buckets[i].lower = last;
  77                 timestwo(&last);
  78                 hist->buckets[i].upper = last;
  79                 hist->buckets[i].count = 0;
  80         }
  81 }
  82
  83 struct timehist* timehist_setup(void)
  84 {
  85         struct timehist* hist = (struct timehist*)calloc(1,
  86                 sizeof(struct timehist));
  87         if(!hist)
  88                 return NULL;
  89         hist->num = NUM_BUCKETS_HIST;
  90         hist->buckets = (struct th_buck*)calloc(hist->num,
  91                 sizeof(struct th_buck));
  92         if(!hist->buckets) {
  93                 free(hist);
  94                 return NULL;
  95         }
  96         /* setup the buckets */
  97         dosetup(hist);
  98         return hist;
  99 }
 100
 101 void timehist_delete(struct timehist* hist)
 102 {
 103         if(!hist)
 104                 return;
 105         free(hist->buckets);
 106         free(hist);
 107 }
 108
 109 void timehist_clear(struct timehist* hist)
 110 {
 111         size_t i;
 112         for(i=0; i<hist->num; i++)
 113                 hist->buckets[i].count = 0;
 114 }
 115
 116 /** histogram compare of time values */
 117 static int
 118 timeval_smaller(const struct timeval* x, const struct timeval* y)
 119 {
 120 #ifndef S_SPLINT_S
 121         if(x->tv_sec < y->tv_sec)
 122                 return 1;
 123         else if(x->tv_sec == y->tv_sec) {
 124                 if(x->tv_usec <= y->tv_usec)
 125                         return 1;
 126                 else    return 0;
 127         }
 128         else    return 0;
 129 #endif
 130 }
 131
 132
 133 void timehist_insert(struct timehist* hist, struct timeval* tv)
 134 {
 135         size_t i;
 136         for(i=0; i<hist->num; i++) {
 137                 if(timeval_smaller(tv, &hist->buckets[i].upper)) {
 138                         hist->buckets[i].count++;
 139                         return;
 140                 }
 141         }
 142         /* dump in last bucket */
 143         hist->buckets[hist->num-1].count++;
 144 }
 145
 146 void timehist_print(struct timehist* hist)
 147 {
 148 #ifndef S_SPLINT_S
 149         size_t i;
 150         for(i=0; i<hist->num; i++) {
 151                 if(hist->buckets[i].count != 0) {
 152                         printf("%4d.%6.6d %4d.%6.6d %u\n",
 153                                 (int)hist->buckets[i].lower.tv_sec,
 154                                 (int)hist->buckets[i].lower.tv_usec,
 155                                 (int)hist->buckets[i].upper.tv_sec,
 156                                 (int)hist->buckets[i].upper.tv_usec,
 157                                 (unsigned)hist->buckets[i].count);
 158                 }
 159         }
 160 #endif
 161 }
 162
 163 void timehist_log(struct timehist* hist, const char* name)
 164 {
 165 #ifndef S_SPLINT_S
 166         size_t i;
 167         log_info("[25%%]=%g median[50%%]=%g [75%%]=%g",
 168                 timehist_quartile(hist, 0.25),
 169                 timehist_quartile(hist, 0.50),
 170                 timehist_quartile(hist, 0.75));
 171         /*        0000.000000 0000.000000 0 */
 172         log_info("lower(secs) upper(secs) %s", name);
 173         for(i=0; i<hist->num; i++) {
 174                 if(hist->buckets[i].count != 0) {
 175                         log_info("%4d.%6.6d %4d.%6.6d %u",
 176                                 (int)hist->buckets[i].lower.tv_sec,
 177                                 (int)hist->buckets[i].lower.tv_usec,
 178                                 (int)hist->buckets[i].upper.tv_sec,
 179                                 (int)hist->buckets[i].upper.tv_usec,
 180                                 (unsigned)hist->buckets[i].count);
 181                 }
 182         }
 183 #endif
 184 }
 185
 186 /** total number in histogram */
 187 static size_t
 188 timehist_count(struct timehist* hist)
 189 {
 190         size_t i, res = 0;
 191         for(i=0; i<hist->num; i++)
 192                 res += hist->buckets[i].count;
 193         return res;
 194 }
 195
 196 double
 197 timehist_quartile(struct timehist* hist, double q)
 198 {
 199         double lookfor, passed, res;
 200         double low = 0, up = 0;
 201         size_t i;
 202         if(!hist || hist->num == 0)
 203                 return 0.;
 204         /* look for i'th element, interpolated */
 205         lookfor = (double)timehist_count(hist);
 206         if(lookfor < 4)
 207                 return 0.; /* not enough elements for a good estimate */
 208         lookfor *= q;
 209         passed = 0;
 210         i = 0;
 211         while(i+1 < hist->num &&
 212                 passed+(double)hist->buckets[i].count < lookfor) {
 213                 passed += (double)hist->buckets[i++].count;
 214         }
 215         /* got the right bucket */
 216 #ifndef S_SPLINT_S
 217         low = (double)hist->buckets[i].lower.tv_sec +
 218                 (double)hist->buckets[i].lower.tv_usec/1000000.;
 219         up = (double)hist->buckets[i].upper.tv_sec +
 220                 (double)hist->buckets[i].upper.tv_usec/1000000.;
 221 #endif
 222         res = (lookfor - passed)*(up-low)/((double)hist->buckets[i].count);
 223         return low+res;
 224 }
 225
 226 void
 227 timehist_export(struct timehist* hist, size_t* array, size_t sz)
 228 {
 229         size_t i;
 230         if(!hist) return;
 231         if(sz > hist->num)
 232                 sz = hist->num;
 233         for(i=0; i<sz; i++)
 234                 array[i] = hist->buckets[i].count;
 235 }
 236
 237 void
 238 timehist_import(struct timehist* hist, size_t* array, size_t sz)
 239 {
 240         size_t i;
 241         if(!hist) return;
 242         if(sz > hist->num)
 243                 sz = hist->num;
 244         for(i=0; i<sz; i++)
 245                 hist->buckets[i].count = array[i];
 246 }