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 */
52static void
53timestwo(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 */
71static void
72dosetup(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
85struct 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
103void timehist_delete(struct timehist* hist)
104{
105	if(!hist)
106		return;
107	free(hist->buckets);
108	free(hist);
109}
110
111void 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
118void 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
131void 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
148void 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 */
172static size_t
173timehist_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
181double
182timehist_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
211void
212timehist_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
222void
223timehist_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