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
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  * SOFTWARE, EVEN IF ADVISED OF THE 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 <sys/types.h>
  47 #include "util/timehist.h"
  48 #include "util/log.h"
  49
  50 /** special timestwo operation for time values in histogram setup */
  51 static void
  52 timestwo(struct timeval* v)
  53 {
  54 #ifndef S_SPLINT_S
  55         if(v->tv_sec == 0 && v->tv_usec == 0) {
  56                 v->tv_usec = 1;
  57                 return;
  58         }
  59         v->tv_sec *= 2;
  60         v->tv_usec *= 2;
  61         if(v->tv_usec == 1024*1024) {
  62                 /* nice values and easy to compute */
  63                 v->tv_sec = 1;
  64                 v->tv_usec = 0;
  65         }
  66 #endif
  67 }
  68
  69 /** do setup exponentially */
  70 static void
  71 dosetup(struct timehist* hist)
  72 {
  73         struct timeval last;
  74         size_t i;
  75         memset(&last, 0, sizeof(last));
  76         for(i=0; i<hist->num; i++) {
  77                 hist->buckets[i].lower = last;
  78                 timestwo(&last);
  79                 hist->buckets[i].upper = last;
  80                 hist->buckets[i].count = 0;
  81         }
  82 }
  83
  84 struct timehist* timehist_setup(void)
  85 {
  86         struct timehist* hist = (struct timehist*)calloc(1,
  87                 sizeof(struct timehist));
  88         if(!hist)
  89                 return NULL;
  90         hist->num = NUM_BUCKETS_HIST;
  91         hist->buckets = (struct th_buck*)calloc(hist->num,
  92                 sizeof(struct th_buck));
  93         if(!hist->buckets) {
  94                 free(hist);
  95                 return NULL;
  96         }
  97         /* setup the buckets */
  98         dosetup(hist);
  99         return hist;
 100 }
 101
 102 void timehist_delete(struct timehist* hist)
 103 {
 104         if(!hist)
 105                 return;
 106         free(hist->buckets);
 107         free(hist);
 108 }
 109
 110 void timehist_clear(struct timehist* hist)
 111 {
 112         size_t i;
 113         for(i=0; i<hist->num; i++)
 114                 hist->buckets[i].count = 0;
 115 }
 116
 117 /** histogram compare of time values */
 118 static int
 119 timeval_smaller(const struct timeval* x, const struct timeval* y)
 120 {
 121 #ifndef S_SPLINT_S
 122         if(x->tv_sec < y->tv_sec)
 123                 return 1;
 124         else if(x->tv_sec == y->tv_sec) {
 125                 if(x->tv_usec <= y->tv_usec)
 126                         return 1;
 127                 else    return 0;
 128         }
 129         else    return 0;
 130 #endif
 131 }
 132
 133
 134 void timehist_insert(struct timehist* hist, struct timeval* tv)
 135 {
 136         size_t i;
 137         for(i=0; i<hist->num; i++) {
 138                 if(timeval_smaller(tv, &hist->buckets[i].upper)) {
 139                         hist->buckets[i].count++;
 140                         return;
 141                 }
 142         }
 143         /* dump in last bucket */
 144         hist->buckets[hist->num-1].count++;
 145 }
 146
 147 void timehist_print(struct timehist* hist)
 148 {
 149 #ifndef S_SPLINT_S
 150         size_t i;
 151         for(i=0; i<hist->num; i++) {
 152                 if(hist->buckets[i].count != 0) {
 153                         printf("%4d.%6.6d %4d.%6.6d %u\n",
 154                                 (int)hist->buckets[i].lower.tv_sec,
 155                                 (int)hist->buckets[i].lower.tv_usec,
 156                                 (int)hist->buckets[i].upper.tv_sec,
 157                                 (int)hist->buckets[i].upper.tv_usec,
 158                                 (unsigned)hist->buckets[i].count);
 159                 }
 160         }
 161 #endif
 162 }
 163
 164 void timehist_log(struct timehist* hist, const char* name)
 165 {
 166 #ifndef S_SPLINT_S
 167         size_t i;
 168         log_info("[25%%]=%g median[50%%]=%g [75%%]=%g",
 169                 timehist_quartile(hist, 0.25),
 170                 timehist_quartile(hist, 0.50),
 171                 timehist_quartile(hist, 0.75));
 172         /*        0000.000000 0000.000000 0 */
 173         log_info("lower(secs) upper(secs) %s", name);
 174         for(i=0; i<hist->num; i++) {
 175                 if(hist->buckets[i].count != 0) {
 176                         log_info("%4d.%6.6d %4d.%6.6d %u",
 177                                 (int)hist->buckets[i].lower.tv_sec,
 178                                 (int)hist->buckets[i].lower.tv_usec,
 179                                 (int)hist->buckets[i].upper.tv_sec,
 180                                 (int)hist->buckets[i].upper.tv_usec,
 181                                 (unsigned)hist->buckets[i].count);
 182                 }
 183         }
 184 #endif
 185 }
 186
 187 /** total number in histogram */
 188 static size_t
 189 timehist_count(struct timehist* hist)
 190 {
 191         size_t i, res = 0;
 192         for(i=0; i<hist->num; i++)
 193                 res += hist->buckets[i].count;
 194         return res;
 195 }
 196
 197 double
 198 timehist_quartile(struct timehist* hist, double q)
 199 {
 200         double lookfor, passed, res;
 201         double low = 0, up = 0;
 202         size_t i;
 203         if(!hist || hist->num == 0)
 204                 return 0.;
 205         /* look for i'th element, interpolated */
 206         lookfor = (double)timehist_count(hist);
 207         if(lookfor < 4)
 208                 return 0.; /* not enough elements for a good estimate */
 209         lookfor *= q;
 210         passed = 0;
 211         i = 0;
 212         while(i+1 < hist->num &&
 213                 passed+(double)hist->buckets[i].count < lookfor) {
 214                 passed += (double)hist->buckets[i++].count;
 215         }
 216         /* got the right bucket */
 217 #ifndef S_SPLINT_S
 218         low = (double)hist->buckets[i].lower.tv_sec +
 219                 (double)hist->buckets[i].lower.tv_usec/1000000.;
 220         up = (double)hist->buckets[i].upper.tv_sec +
 221                 (double)hist->buckets[i].upper.tv_usec/1000000.;
 222 #endif
 223         res = (lookfor - passed)*(up-low)/((double)hist->buckets[i].count);
 224         return low+res;
 225 }
 226
 227 void
 228 timehist_export(struct timehist* hist, size_t* array, size_t sz)
 229 {
 230         size_t i;
 231         if(!hist) return;
 232         if(sz > hist->num)
 233                 sz = hist->num;
 234         for(i=0; i<sz; i++)
 235                 array[i] = hist->buckets[i].count;
 236 }
 237
 238 void
 239 timehist_import(struct timehist* hist, size_t* array, size_t sz)
 240 {
 241         size_t i;
 242         if(!hist) return;
 243         if(sz > hist->num)
 244                 sz = hist->num;
 245         for(i=0; i<sz; i++)
 246                 hist->buckets[i].count = array[i];
 247 }