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 LIMITED
25 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
26 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
27 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
28 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
29 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
30 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
31 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
32 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 * 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 "util/timehist.h"
47#include "util/log.h"
48
49/** special timestwo operation for time values in histogram setup */
50static void
51timestwo(struct timeval* v)
52{
53#ifndef S_SPLINT_S
54	if(v->tv_sec == 0 && v->tv_usec == 0) {
55		v->tv_usec = 1;
56		return;
57	}
58	v->tv_sec *= 2;
59	v->tv_usec *= 2;
60	if(v->tv_usec == 1024*1024) {
61		/* nice values and easy to compute */
62		v->tv_sec = 1;
63		v->tv_usec = 0;
64	}
65#endif
66}
67
68/** do setup exponentially */
69static void
70dosetup(struct timehist* hist)
71{
72	struct timeval last;
73	size_t i;
74	memset(&last, 0, sizeof(last));
75	for(i=0; i<hist->num; i++) {
76		hist->buckets[i].lower = last;
77		timestwo(&last);
78		hist->buckets[i].upper = last;
79		hist->buckets[i].count = 0;
80	}
81}
82
83struct timehist* timehist_setup(void)
84{
85	struct timehist* hist = (struct timehist*)calloc(1,
86		sizeof(struct timehist));
87	if(!hist)
88		return NULL;
89	hist->num = NUM_BUCKETS_HIST;
90	hist->buckets = (struct th_buck*)calloc(hist->num,
91		sizeof(struct th_buck));
92	if(!hist->buckets) {
93		free(hist);
94		return NULL;
95	}
96	/* setup the buckets */
97	dosetup(hist);
98	return hist;
99}
100
101void timehist_delete(struct timehist* hist)
102{
103	if(!hist)
104		return;
105	free(hist->buckets);
106	free(hist);
107}
108
109void timehist_clear(struct timehist* hist)
110{
111	size_t i;
112	for(i=0; i<hist->num; i++)
113		hist->buckets[i].count = 0;
114}
115
116/** histogram compare of time values */
117static int
118timeval_smaller(const struct timeval* x, const struct timeval* y)
119{
120#ifndef S_SPLINT_S
121	if(x->tv_sec < y->tv_sec)
122		return 1;
123	else if(x->tv_sec == y->tv_sec) {
124		if(x->tv_usec <= y->tv_usec)
125			return 1;
126		else	return 0;
127	}
128	else	return 0;
129#endif
130}
131
132
133void timehist_insert(struct timehist* hist, struct timeval* tv)
134{
135	size_t i;
136	for(i=0; i<hist->num; i++) {
137		if(timeval_smaller(tv, &hist->buckets[i].upper)) {
138			hist->buckets[i].count++;
139			return;
140		}
141	}
142	/* dump in last bucket */
143	hist->buckets[hist->num-1].count++;
144}
145
146void timehist_print(struct timehist* hist)
147{
148#ifndef S_SPLINT_S
149	size_t i;
150	for(i=0; i<hist->num; i++) {
151		if(hist->buckets[i].count != 0) {
152			printf("%4d.%6.6d %4d.%6.6d %u\n",
153				(int)hist->buckets[i].lower.tv_sec,
154				(int)hist->buckets[i].lower.tv_usec,
155				(int)hist->buckets[i].upper.tv_sec,
156				(int)hist->buckets[i].upper.tv_usec,
157				(unsigned)hist->buckets[i].count);
158		}
159	}
160#endif
161}
162
163void timehist_log(struct timehist* hist, const char* name)
164{
165#ifndef S_SPLINT_S
166	size_t i;
167	log_info("[25%%]=%g median[50%%]=%g [75%%]=%g",
168		timehist_quartile(hist, 0.25),
169		timehist_quartile(hist, 0.50),
170		timehist_quartile(hist, 0.75));
171	/*        0000.000000 0000.000000 0 */
172	log_info("lower(secs) upper(secs) %s", name);
173	for(i=0; i<hist->num; i++) {
174		if(hist->buckets[i].count != 0) {
175			log_info("%4d.%6.6d %4d.%6.6d %u",
176				(int)hist->buckets[i].lower.tv_sec,
177				(int)hist->buckets[i].lower.tv_usec,
178				(int)hist->buckets[i].upper.tv_sec,
179				(int)hist->buckets[i].upper.tv_usec,
180				(unsigned)hist->buckets[i].count);
181		}
182	}
183#endif
184}
185
186/** total number in histogram */
187static size_t
188timehist_count(struct timehist* hist)
189{
190	size_t i, res = 0;
191	for(i=0; i<hist->num; i++)
192		res += hist->buckets[i].count;
193	return res;
194}
195
196double
197timehist_quartile(struct timehist* hist, double q)
198{
199	double lookfor, passed, res;
200	double low = 0, up = 0;
201	size_t i;
202	if(!hist || hist->num == 0)
203		return 0.;
204	/* look for i'th element, interpolated */
205	lookfor = (double)timehist_count(hist);
206	if(lookfor < 4)
207		return 0.; /* not enough elements for a good estimate */
208	lookfor *= q;
209	passed = 0;
210	i = 0;
211	while(i+1 < hist->num &&
212		passed+(double)hist->buckets[i].count < lookfor) {
213		passed += (double)hist->buckets[i++].count;
214	}
215	/* got the right bucket */
216#ifndef S_SPLINT_S
217	low = (double)hist->buckets[i].lower.tv_sec +
218		(double)hist->buckets[i].lower.tv_usec/1000000.;
219	up = (double)hist->buckets[i].upper.tv_sec +
220		(double)hist->buckets[i].upper.tv_usec/1000000.;
221#endif
222	res = (lookfor - passed)*(up-low)/((double)hist->buckets[i].count);
223	return low+res;
224}
225
226void
227timehist_export(struct timehist* hist, size_t* array, size_t sz)
228{
229	size_t i;
230	if(!hist) return;
231	if(sz > hist->num)
232		sz = hist->num;
233	for(i=0; i<sz; i++)
234		array[i] = hist->buckets[i].count;
235}
236
237void
238timehist_import(struct timehist* hist, size_t* array, size_t sz)
239{
240	size_t i;
241	if(!hist) return;
242	if(sz > hist->num)
243		sz = hist->num;
244	for(i=0; i<sz; i++)
245		hist->buckets[i].count = array[i];
246}
247