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 } 247