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
timestwo(struct timeval * v)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
dosetup(struct timehist * hist)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
timehist_setup(void)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
timehist_delete(struct timehist * hist)103 void timehist_delete(struct timehist* hist)
104 {
105 if(!hist)
106 return;
107 free(hist->buckets);
108 free(hist);
109 }
110
timehist_clear(struct timehist * hist)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
timehist_insert(struct timehist * hist,struct timeval * tv)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
timehist_print(struct timehist * hist)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
timehist_log(struct timehist * hist,const char * name)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
timehist_count(struct timehist * hist)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
timehist_quartile(struct timehist * hist,double q)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
timehist_export(struct timehist * hist,long long * array,size_t sz)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
timehist_import(struct timehist * hist,long long * array,size_t sz)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