timehist.c revision 356345
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 */ 51static void 52timestwo(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 */ 70static void 71dosetup(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 84struct 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 102void timehist_delete(struct timehist* hist) 103{ 104 if(!hist) 105 return; 106 free(hist->buckets); 107 free(hist); 108} 109 110void 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 */ 118static int 119timeval_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 134void 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 147void 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 164void 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 */ 188static size_t 189timehist_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 197double 198timehist_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 227void 228timehist_export(struct timehist* hist, long long* 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] = (long long)hist->buckets[i].count; 236} 237 238void 239timehist_import(struct timehist* hist, long long* 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 = (size_t)array[i]; 247} 248