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