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
  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 #include "util/timeval_func.h"
  50
  51 /** special timestwo operation for time values in histogram setup */
  52 static void
  53 timestwo(struct timeval* v)
  54 {
  55 #ifndef S_SPLINT_S
  56         if(v->tv_sec == 0 && v->tv_usec == 0) {
  57                 v->tv_usec = 1;
  58                 return;
  59         }
  60         v->tv_sec *= 2;
  61         v->tv_usec *= 2;
  62         if(v->tv_usec == 1024*1024) {
  63                 /* nice values and easy to compute */
  64                 v->tv_sec = 1;
  65                 v->tv_usec = 0;
  66         }
  67 #endif
  68 }
  69
  70 /** do setup exponentially */
  71 static void
  72 dosetup(struct timehist* hist)
  73 {
  74         struct timeval last;
  75         size_t i;
  76         memset(&last, 0, sizeof(last));
  77         for(i=0; i<hist->num; i++) {
  78                 hist->buckets[i].lower = last;
  79                 timestwo(&last);
  80                 hist->buckets[i].upper = last;
  81                 hist->buckets[i].count = 0;
  82         }
  83 }
  84
  85 struct timehist* timehist_setup(void)
  86 {
  87         struct timehist* hist = (struct timehist*)calloc(1,
  88                 sizeof(struct timehist));
  89         if(!hist)
  90                 return NULL;
  91         hist->num = NUM_BUCKETS_HIST;
  92         hist->buckets = (struct th_buck*)calloc(hist->num,
  93                 sizeof(struct th_buck));
  94         if(!hist->buckets) {
  95                 free(hist);
  96                 return NULL;
  97         }
  98         /* setup the buckets */
  99         dosetup(hist);
 100         return hist;
 101 }
 102
 103 void timehist_delete(struct timehist* hist)
 104 {
 105         if(!hist)
 106                 return;
 107         free(hist->buckets);
 108         free(hist);
 109 }
 110
 111 void timehist_clear(struct timehist* hist)
 112 {
 113         size_t i;
 114         for(i=0; i<hist->num; i++)
 115                 hist->buckets[i].count = 0;
 116 }
 117
 118 void timehist_insert(struct timehist* hist, struct timeval* tv)
 119 {
 120         size_t i;
 121         for(i=0; i<hist->num; i++) {
 122                 if(timeval_smaller(tv, &hist->buckets[i].upper)) {
 123                         hist->buckets[i].count++;
 124                         return;
 125                 }
 126         }
 127         /* dump in last bucket */
 128         hist->buckets[hist->num-1].count++;
 129 }
 130
 131 void timehist_print(struct timehist* hist)
 132 {
 133 #ifndef S_SPLINT_S
 134         size_t i;
 135         for(i=0; i<hist->num; i++) {
 136                 if(hist->buckets[i].count != 0) {
 137                         printf("%4d.%6.6d %4d.%6.6d %u\n",
 138                                 (int)hist->buckets[i].lower.tv_sec,
 139                                 (int)hist->buckets[i].lower.tv_usec,
 140                                 (int)hist->buckets[i].upper.tv_sec,
 141                                 (int)hist->buckets[i].upper.tv_usec,
 142                                 (unsigned)hist->buckets[i].count);
 143                 }
 144         }
 145 #endif
 146 }
 147
 148 void timehist_log(struct timehist* hist, const char* name)
 149 {
 150 #ifndef S_SPLINT_S
 151         size_t i;
 152         log_info("[25%%]=%g median[50%%]=%g [75%%]=%g",
 153                 timehist_quartile(hist, 0.25),
 154                 timehist_quartile(hist, 0.50),
 155                 timehist_quartile(hist, 0.75));
 156         /*        0000.000000 0000.000000 0 */
 157         log_info("lower(secs) upper(secs) %s", name);
 158         for(i=0; i<hist->num; i++) {
 159                 if(hist->buckets[i].count != 0) {
 160                         log_info("%4d.%6.6d %4d.%6.6d %u",
 161                                 (int)hist->buckets[i].lower.tv_sec,
 162                                 (int)hist->buckets[i].lower.tv_usec,
 163                                 (int)hist->buckets[i].upper.tv_sec,
 164                                 (int)hist->buckets[i].upper.tv_usec,
 165                                 (unsigned)hist->buckets[i].count);
 166                 }
 167         }
 168 #endif
 169 }
 170
 171 /** total number in histogram */
 172 static size_t
 173 timehist_count(struct timehist* hist)
 174 {
 175         size_t i, res = 0;
 176         for(i=0; i<hist->num; i++)
 177                 res += hist->buckets[i].count;
 178         return res;
 179 }
 180
 181 double
 182 timehist_quartile(struct timehist* hist, double q)
 183 {
 184         double lookfor, passed, res;
 185         double low = 0, up = 0;
 186         size_t i;
 187         if(!hist || hist->num == 0)
 188                 return 0.;
 189         /* look for i'th element, interpolated */
 190         lookfor = (double)timehist_count(hist);
 191         if(lookfor < 4)
 192                 return 0.; /* not enough elements for a good estimate */
 193         lookfor *= q;
 194         passed = 0;
 195         i = 0;
 196         while(i+1 < hist->num &&
 197                 passed+(double)hist->buckets[i].count < lookfor) {
 198                 passed += (double)hist->buckets[i++].count;
 199         }
 200         /* got the right bucket */
 201 #ifndef S_SPLINT_S
 202         low = (double)hist->buckets[i].lower.tv_sec +
 203                 (double)hist->buckets[i].lower.tv_usec/1000000.;
 204         up = (double)hist->buckets[i].upper.tv_sec +
 205                 (double)hist->buckets[i].upper.tv_usec/1000000.;
 206 #endif
 207         res = (lookfor - passed)*(up-low)/((double)hist->buckets[i].count);
 208         return low+res;
 209 }
 210
 211 void
 212 timehist_export(struct timehist* hist, long long* array, size_t sz)
 213 {
 214         size_t i;
 215         if(!hist) return;
 216         if(sz > hist->num)
 217                 sz = hist->num;
 218         for(i=0; i<sz; i++)
 219                 array[i] = (long long)hist->buckets[i].count;
 220 }
 221
 222 void
 223 timehist_import(struct timehist* hist, long long* array, size_t sz)
 224 {
 225         size_t i;
 226         if(!hist) return;
 227         if(sz > hist->num)
 228                 sz = hist->num;
 229         for(i=0; i<sz; i++)
 230                 hist->buckets[i].count = (size_t)array[i];
 231 }