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