1238106Sdes/* 2238106Sdes * util/timehist.c - make histogram of time values. 3238106Sdes * 4238106Sdes * Copyright (c) 2007, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * This software is open source. 7238106Sdes * 8238106Sdes * Redistribution and use in source and binary forms, with or without 9238106Sdes * modification, are permitted provided that the following conditions 10238106Sdes * are met: 11238106Sdes * 12238106Sdes * Redistributions of source code must retain the above copyright notice, 13238106Sdes * this list of conditions and the following disclaimer. 14238106Sdes * 15238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 16238106Sdes * this list of conditions and the following disclaimer in the documentation 17238106Sdes * and/or other materials provided with the distribution. 18238106Sdes * 19238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 20238106Sdes * be used to endorse or promote products derived from this software without 21238106Sdes * specific prior written permission. 22238106Sdes * 23238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24238106Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 25238106Sdes * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 26238106Sdes * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 27238106Sdes * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 28238106Sdes * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 29238106Sdes * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 30238106Sdes * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 31238106Sdes * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 32238106Sdes * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33238106Sdes * POSSIBILITY OF SUCH DAMAGE. 34238106Sdes */ 35238106Sdes 36238106Sdes/** 37238106Sdes * \file 38238106Sdes * 39238106Sdes * This file contains functions to make a histogram of time values. 40238106Sdes */ 41238106Sdes#include "config.h" 42238106Sdes#ifdef HAVE_TIME_H 43238106Sdes#include <time.h> 44238106Sdes#endif 45238106Sdes#include <sys/time.h> 46238106Sdes#include "util/timehist.h" 47238106Sdes#include "util/log.h" 48238106Sdes 49238106Sdes/** special timestwo operation for time values in histogram setup */ 50238106Sdesstatic void 51238106Sdestimestwo(struct timeval* v) 52238106Sdes{ 53238106Sdes#ifndef S_SPLINT_S 54238106Sdes if(v->tv_sec == 0 && v->tv_usec == 0) { 55238106Sdes v->tv_usec = 1; 56238106Sdes return; 57238106Sdes } 58238106Sdes v->tv_sec *= 2; 59238106Sdes v->tv_usec *= 2; 60238106Sdes if(v->tv_usec == 1024*1024) { 61238106Sdes /* nice values and easy to compute */ 62238106Sdes v->tv_sec = 1; 63238106Sdes v->tv_usec = 0; 64238106Sdes } 65238106Sdes#endif 66238106Sdes} 67238106Sdes 68238106Sdes/** do setup exponentially */ 69238106Sdesstatic void 70238106Sdesdosetup(struct timehist* hist) 71238106Sdes{ 72238106Sdes struct timeval last; 73238106Sdes size_t i; 74238106Sdes memset(&last, 0, sizeof(last)); 75238106Sdes for(i=0; i<hist->num; i++) { 76238106Sdes hist->buckets[i].lower = last; 77238106Sdes timestwo(&last); 78238106Sdes hist->buckets[i].upper = last; 79238106Sdes hist->buckets[i].count = 0; 80238106Sdes } 81238106Sdes} 82238106Sdes 83238106Sdesstruct timehist* timehist_setup(void) 84238106Sdes{ 85238106Sdes struct timehist* hist = (struct timehist*)calloc(1, 86238106Sdes sizeof(struct timehist)); 87238106Sdes if(!hist) 88238106Sdes return NULL; 89238106Sdes hist->num = NUM_BUCKETS_HIST; 90238106Sdes hist->buckets = (struct th_buck*)calloc(hist->num, 91238106Sdes sizeof(struct th_buck)); 92238106Sdes if(!hist->buckets) { 93238106Sdes free(hist); 94238106Sdes return NULL; 95238106Sdes } 96238106Sdes /* setup the buckets */ 97238106Sdes dosetup(hist); 98238106Sdes return hist; 99238106Sdes} 100238106Sdes 101238106Sdesvoid timehist_delete(struct timehist* hist) 102238106Sdes{ 103238106Sdes if(!hist) 104238106Sdes return; 105238106Sdes free(hist->buckets); 106238106Sdes free(hist); 107238106Sdes} 108238106Sdes 109238106Sdesvoid timehist_clear(struct timehist* hist) 110238106Sdes{ 111238106Sdes size_t i; 112238106Sdes for(i=0; i<hist->num; i++) 113238106Sdes hist->buckets[i].count = 0; 114238106Sdes} 115238106Sdes 116238106Sdes/** histogram compare of time values */ 117238106Sdesstatic int 118238106Sdestimeval_smaller(const struct timeval* x, const struct timeval* y) 119238106Sdes{ 120238106Sdes#ifndef S_SPLINT_S 121238106Sdes if(x->tv_sec < y->tv_sec) 122238106Sdes return 1; 123238106Sdes else if(x->tv_sec == y->tv_sec) { 124238106Sdes if(x->tv_usec <= y->tv_usec) 125238106Sdes return 1; 126238106Sdes else return 0; 127238106Sdes } 128238106Sdes else return 0; 129238106Sdes#endif 130238106Sdes} 131238106Sdes 132238106Sdes 133238106Sdesvoid timehist_insert(struct timehist* hist, struct timeval* tv) 134238106Sdes{ 135238106Sdes size_t i; 136238106Sdes for(i=0; i<hist->num; i++) { 137238106Sdes if(timeval_smaller(tv, &hist->buckets[i].upper)) { 138238106Sdes hist->buckets[i].count++; 139238106Sdes return; 140238106Sdes } 141238106Sdes } 142238106Sdes /* dump in last bucket */ 143238106Sdes hist->buckets[hist->num-1].count++; 144238106Sdes} 145238106Sdes 146238106Sdesvoid timehist_print(struct timehist* hist) 147238106Sdes{ 148238106Sdes#ifndef S_SPLINT_S 149238106Sdes size_t i; 150238106Sdes for(i=0; i<hist->num; i++) { 151238106Sdes if(hist->buckets[i].count != 0) { 152238106Sdes printf("%4d.%6.6d %4d.%6.6d %u\n", 153238106Sdes (int)hist->buckets[i].lower.tv_sec, 154238106Sdes (int)hist->buckets[i].lower.tv_usec, 155238106Sdes (int)hist->buckets[i].upper.tv_sec, 156238106Sdes (int)hist->buckets[i].upper.tv_usec, 157238106Sdes (unsigned)hist->buckets[i].count); 158238106Sdes } 159238106Sdes } 160238106Sdes#endif 161238106Sdes} 162238106Sdes 163238106Sdesvoid timehist_log(struct timehist* hist, const char* name) 164238106Sdes{ 165238106Sdes#ifndef S_SPLINT_S 166238106Sdes size_t i; 167238106Sdes log_info("[25%%]=%g median[50%%]=%g [75%%]=%g", 168238106Sdes timehist_quartile(hist, 0.25), 169238106Sdes timehist_quartile(hist, 0.50), 170238106Sdes timehist_quartile(hist, 0.75)); 171238106Sdes /* 0000.000000 0000.000000 0 */ 172238106Sdes log_info("lower(secs) upper(secs) %s", name); 173238106Sdes for(i=0; i<hist->num; i++) { 174238106Sdes if(hist->buckets[i].count != 0) { 175238106Sdes log_info("%4d.%6.6d %4d.%6.6d %u", 176238106Sdes (int)hist->buckets[i].lower.tv_sec, 177238106Sdes (int)hist->buckets[i].lower.tv_usec, 178238106Sdes (int)hist->buckets[i].upper.tv_sec, 179238106Sdes (int)hist->buckets[i].upper.tv_usec, 180238106Sdes (unsigned)hist->buckets[i].count); 181238106Sdes } 182238106Sdes } 183238106Sdes#endif 184238106Sdes} 185238106Sdes 186238106Sdes/** total number in histogram */ 187238106Sdesstatic size_t 188238106Sdestimehist_count(struct timehist* hist) 189238106Sdes{ 190238106Sdes size_t i, res = 0; 191238106Sdes for(i=0; i<hist->num; i++) 192238106Sdes res += hist->buckets[i].count; 193238106Sdes return res; 194238106Sdes} 195238106Sdes 196238106Sdesdouble 197238106Sdestimehist_quartile(struct timehist* hist, double q) 198238106Sdes{ 199238106Sdes double lookfor, passed, res; 200238106Sdes double low = 0, up = 0; 201238106Sdes size_t i; 202238106Sdes if(!hist || hist->num == 0) 203238106Sdes return 0.; 204238106Sdes /* look for i'th element, interpolated */ 205238106Sdes lookfor = (double)timehist_count(hist); 206238106Sdes if(lookfor < 4) 207238106Sdes return 0.; /* not enough elements for a good estimate */ 208238106Sdes lookfor *= q; 209238106Sdes passed = 0; 210238106Sdes i = 0; 211238106Sdes while(i+1 < hist->num && 212238106Sdes passed+(double)hist->buckets[i].count < lookfor) { 213238106Sdes passed += (double)hist->buckets[i++].count; 214238106Sdes } 215238106Sdes /* got the right bucket */ 216238106Sdes#ifndef S_SPLINT_S 217238106Sdes low = (double)hist->buckets[i].lower.tv_sec + 218238106Sdes (double)hist->buckets[i].lower.tv_usec/1000000.; 219238106Sdes up = (double)hist->buckets[i].upper.tv_sec + 220238106Sdes (double)hist->buckets[i].upper.tv_usec/1000000.; 221238106Sdes#endif 222238106Sdes res = (lookfor - passed)*(up-low)/((double)hist->buckets[i].count); 223238106Sdes return low+res; 224238106Sdes} 225238106Sdes 226238106Sdesvoid 227238106Sdestimehist_export(struct timehist* hist, size_t* array, size_t sz) 228238106Sdes{ 229238106Sdes size_t i; 230238106Sdes if(!hist) return; 231238106Sdes if(sz > hist->num) 232238106Sdes sz = hist->num; 233238106Sdes for(i=0; i<sz; i++) 234238106Sdes array[i] = hist->buckets[i].count; 235238106Sdes} 236238106Sdes 237238106Sdesvoid 238238106Sdestimehist_import(struct timehist* hist, size_t* array, size_t sz) 239238106Sdes{ 240238106Sdes size_t i; 241238106Sdes if(!hist) return; 242238106Sdes if(sz > hist->num) 243238106Sdes sz = hist->num; 244238106Sdes for(i=0; i<sz; i++) 245238106Sdes hist->buckets[i].count = array[i]; 246238106Sdes} 247