xref: /freebsd/contrib/unbound/util/timehist.c (revision 62cfcf62f627e5093fb37026a6d8c98e4d2ef04c)
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, 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 
238 void
239 timehist_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