/src/unbound/util/timehist.c

Source (jump to first uncovered line)
/*
 * util/timehist.c - make histogram of time values.
 *
 * Copyright (c) 2007, NLnet Labs. All rights reserved.
 *
 * This software is open source.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 * 
 * Neither the name of the NLNET LABS nor the names of its contributors may
 * be used to endorse or promote products derived from this software without
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/**
 * \file
 *
 * This file contains functions to make a histogram of time values.
 */
#include "config.h"
#ifdef HAVE_TIME_H
#include <time.h>
#endif
#include <sys/time.h>
#include <sys/types.h>
#include "util/timehist.h"
#include "util/log.h"

/** special timestwo operation for time values in histogram setup */
static void
timestwo(struct timeval* v)
{
#ifndef S_SPLINT_S
  if(v->tv_sec == 0 && v->tv_usec == 0) {
    v->tv_usec = 1;
    return;
  }
  v->tv_sec *= 2;
  v->tv_usec *= 2;
  if(v->tv_usec == 1024*1024) {
    /* nice values and easy to compute */
    v->tv_sec = 1;
    v->tv_usec = 0;
  }
#endif
}

/** do setup exponentially */
static void
dosetup(struct timehist* hist)
{
  struct timeval last;
  size_t i;
  memset(&last, 0, sizeof(last));
  for(i=0; i<hist->num; i++) {
    hist->buckets[i].lower = last;
    timestwo(&last);
    hist->buckets[i].upper = last;
    hist->buckets[i].count = 0;
  }
}

struct timehist* timehist_setup(void)
{
  struct timehist* hist = (struct timehist*)calloc(1, 
    sizeof(struct timehist));
  if(!hist)
    return NULL;
  hist->num = NUM_BUCKETS_HIST;
  hist->buckets = (struct th_buck*)calloc(hist->num, 
    sizeof(struct th_buck));
  if(!hist->buckets) {
    free(hist);
    return NULL;
  }
  /* setup the buckets */
  dosetup(hist);
  return hist;
}

void timehist_delete(struct timehist* hist)
{
  if(!hist)
    return;
  free(hist->buckets);
  free(hist);
}

void timehist_clear(struct timehist* hist)
{
  size_t i;
  for(i=0; i<hist->num; i++)
    hist->buckets[i].count = 0;
}

/** histogram compare of time values */
static int
timeval_smaller(const struct timeval* x, const struct timeval* y)
{
#ifndef S_SPLINT_S
  if(x->tv_sec < y->tv_sec)
    return 1;
  else if(x->tv_sec == y->tv_sec) {
    if(x->tv_usec <= y->tv_usec)
      return 1;
    else  return 0;
  }
  else  return 0;
#endif
}


void timehist_insert(struct timehist* hist, struct timeval* tv)
{
  size_t i;
  for(i=0; i<hist->num; i++) {
    if(timeval_smaller(tv, &hist->buckets[i].upper)) {
      hist->buckets[i].count++;
      return;
    }
  }
  /* dump in last bucket */
  hist->buckets[hist->num-1].count++;
}

void timehist_print(struct timehist* hist)
{
#ifndef S_SPLINT_S
  size_t i;
  for(i=0; i<hist->num; i++) {
    if(hist->buckets[i].count != 0) {
      printf("%4d.%6.6d %4d.%6.6d %u\n",
        (int)hist->buckets[i].lower.tv_sec,
        (int)hist->buckets[i].lower.tv_usec,
        (int)hist->buckets[i].upper.tv_sec,
        (int)hist->buckets[i].upper.tv_usec,
        (unsigned)hist->buckets[i].count);
    }
  }
#endif
}

void timehist_log(struct timehist* hist, const char* name)
{
#ifndef S_SPLINT_S
  size_t i;
  log_info("[25%%]=%g median[50%%]=%g [75%%]=%g",
    timehist_quartile(hist, 0.25),
    timehist_quartile(hist, 0.50),
    timehist_quartile(hist, 0.75));
  /*        0000.000000 0000.000000 0 */
  log_info("lower(secs) upper(secs) %s", name);
  for(i=0; i<hist->num; i++) {
    if(hist->buckets[i].count != 0) {
      log_info("%4d.%6.6d %4d.%6.6d %u",
        (int)hist->buckets[i].lower.tv_sec,
        (int)hist->buckets[i].lower.tv_usec,
        (int)hist->buckets[i].upper.tv_sec,
        (int)hist->buckets[i].upper.tv_usec,
        (unsigned)hist->buckets[i].count);
    }
  }
#endif
}

/** total number in histogram */
static size_t
timehist_count(struct timehist* hist)
{
  size_t i, res = 0;
  for(i=0; i<hist->num; i++)
    res += hist->buckets[i].count;
  return res;
}

double 
timehist_quartile(struct timehist* hist, double q)
{
  double lookfor, passed, res;
  double low = 0, up = 0;
  size_t i;
  if(!hist || hist->num == 0)
    return 0.;
  /* look for i'th element, interpolated */
  lookfor = (double)timehist_count(hist);
  if(lookfor < 4)
    return 0.; /* not enough elements for a good estimate */
  lookfor *= q;
  passed = 0;
  i = 0;
  while(i+1 < hist->num && 
    passed+(double)hist->buckets[i].count < lookfor) {
    passed += (double)hist->buckets[i++].count;
  }
  /* got the right bucket */
#ifndef S_SPLINT_S
  low = (double)hist->buckets[i].lower.tv_sec + 
    (double)hist->buckets[i].lower.tv_usec/1000000.;
  up = (double)hist->buckets[i].upper.tv_sec + 
    (double)hist->buckets[i].upper.tv_usec/1000000.;
#endif
  res = (lookfor - passed)*(up-low)/((double)hist->buckets[i].count);
  return low+res;
}

void 
timehist_export(struct timehist* hist, long long* array, size_t sz)
{
  size_t i;
  if(!hist) return;
  if(sz > hist->num)
    sz = hist->num;
  for(i=0; i<sz; i++)
    array[i] = (long long)hist->buckets[i].count;
}

void 
timehist_import(struct timehist* hist, long long* array, size_t sz)
{
  size_t i;
  if(!hist) return;
  if(sz > hist->num)
    sz = hist->num;
  for(i=0; i<sz; i++)
    hist->buckets[i].count = (size_t)array[i];
}

Coverage Report

Created: 2023-03-26 06:07

Line	Count	Source (jump to first uncovered line)
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	0	{
54	0	#ifndef S_SPLINT_S
55	0	if(v->tv_sec == 0 && v->tv_usec == 0) {
56	0	v->tv_usec = 1;
57	0	return;
58	0	}
59	0	v->tv_sec *= 2;
60	0	v->tv_usec *= 2;
61	0	if(v->tv_usec == 1024*1024) {
62		/* nice values and easy to compute */
63	0	v->tv_sec = 1;
64	0	v->tv_usec = 0;
65	0	}
66	0	#endif
67	0	}
68
69		/** do setup exponentially */
70		static void
71		dosetup(struct timehist* hist)
72	0	{
73	0	struct timeval last;
74	0	size_t i;
75	0	memset(&last, 0, sizeof(last));
76	0	for(i=0; i<hist->num; i++) {
77	0	hist->buckets[i].lower = last;
78	0	timestwo(&last);
79	0	hist->buckets[i].upper = last;
80	0	hist->buckets[i].count = 0;
81	0	}
82	0	}
83
84		struct timehist* timehist_setup(void)
85	0	{
86	0	struct timehist* hist = (struct timehist*)calloc(1,
87	0	sizeof(struct timehist));
88	0	if(!hist)
89	0	return NULL;
90	0	hist->num = NUM_BUCKETS_HIST;
91	0	hist->buckets = (struct th_buck*)calloc(hist->num,
92	0	sizeof(struct th_buck));
93	0	if(!hist->buckets) {
94	0	free(hist);
95	0	return NULL;
96	0	}
97		/* setup the buckets */
98	0	dosetup(hist);
99	0	return hist;
100	0	}
101
102		void timehist_delete(struct timehist* hist)
103	0	{
104	0	if(!hist)
105	0	return;
106	0	free(hist->buckets);
107	0	free(hist);
108	0	}
109
110		void timehist_clear(struct timehist* hist)
111	0	{
112	0	size_t i;
113	0	for(i=0; i<hist->num; i++)
114	0	hist->buckets[i].count = 0;
115	0	}
116
117		/** histogram compare of time values */
118		static int
119		timeval_smaller(const struct timeval* x, const struct timeval* y)
120	0	{
121	0	#ifndef S_SPLINT_S
122	0	if(x->tv_sec < y->tv_sec)
123	0	return 1;
124	0	else if(x->tv_sec == y->tv_sec) {
125	0	if(x->tv_usec <= y->tv_usec)
126	0	return 1;
127	0	else return 0;
128	0	}
129	0	else return 0;
130	0	#endif
131	0	}
132
133
134		void timehist_insert(struct timehist* hist, struct timeval* tv)
135	0	{
136	0	size_t i;
137	0	for(i=0; i<hist->num; i++) {
138	0	if(timeval_smaller(tv, &hist->buckets[i].upper)) {
139	0	hist->buckets[i].count++;
140	0	return;
141	0	}
142	0	}
143		/* dump in last bucket */
144	0	hist->buckets[hist->num-1].count++;
145	0	}
146
147		void timehist_print(struct timehist* hist)
148	0	{
149	0	#ifndef S_SPLINT_S
150	0	size_t i;
151	0	for(i=0; i<hist->num; i++) {
152	0	if(hist->buckets[i].count != 0) {
153	0	printf("%4d.%6.6d %4d.%6.6d %u\n",
154	0	(int)hist->buckets[i].lower.tv_sec,
155	0	(int)hist->buckets[i].lower.tv_usec,
156	0	(int)hist->buckets[i].upper.tv_sec,
157	0	(int)hist->buckets[i].upper.tv_usec,
158	0	(unsigned)hist->buckets[i].count);
159	0	}
160	0	}
161	0	#endif
162	0	}
163
164		void timehist_log(struct timehist* hist, const char* name)
165	0	{
166	0	#ifndef S_SPLINT_S
167	0	size_t i;
168	0	log_info("[25%%]=%g median[50%%]=%g [75%%]=%g",
169	0	timehist_quartile(hist, 0.25),
170	0	timehist_quartile(hist, 0.50),
171	0	timehist_quartile(hist, 0.75));
172		/* 0000.000000 0000.000000 0 */
173	0	log_info("lower(secs) upper(secs) %s", name);
174	0	for(i=0; i<hist->num; i++) {
175	0	if(hist->buckets[i].count != 0) {
176	0	log_info("%4d.%6.6d %4d.%6.6d %u",
177	0	(int)hist->buckets[i].lower.tv_sec,
178	0	(int)hist->buckets[i].lower.tv_usec,
179	0	(int)hist->buckets[i].upper.tv_sec,
180	0	(int)hist->buckets[i].upper.tv_usec,
181	0	(unsigned)hist->buckets[i].count);
182	0	}
183	0	}
184	0	#endif
185	0	}
186
187		/** total number in histogram */
188		static size_t
189		timehist_count(struct timehist* hist)
190	0	{
191	0	size_t i, res = 0;
192	0	for(i=0; i<hist->num; i++)
193	0	res += hist->buckets[i].count;
194	0	return res;
195	0	}
196
197		double
198		timehist_quartile(struct timehist* hist, double q)
199	0	{
200	0	double lookfor, passed, res;
201	0	double low = 0, up = 0;
202	0	size_t i;
203	0	if(!hist \|\| hist->num == 0)
204	0	return 0.;
205		/* look for i'th element, interpolated */
206	0	lookfor = (double)timehist_count(hist);
207	0	if(lookfor < 4)
208	0	return 0.; /* not enough elements for a good estimate */
209	0	lookfor *= q;
210	0	passed = 0;
211	0	i = 0;
212	0	while(i+1 < hist->num &&
213	0	passed+(double)hist->buckets[i].count < lookfor) {
214	0	passed += (double)hist->buckets[i++].count;
215	0	}
216		/* got the right bucket */
217	0	#ifndef S_SPLINT_S
218	0	low = (double)hist->buckets[i].lower.tv_sec +
219	0	(double)hist->buckets[i].lower.tv_usec/1000000.;
220	0	up = (double)hist->buckets[i].upper.tv_sec +
221	0	(double)hist->buckets[i].upper.tv_usec/1000000.;
222	0	#endif
223	0	res = (lookfor - passed)*(up-low)/((double)hist->buckets[i].count);
224	0	return low+res;
225	0	}
226
227		void
228		timehist_export(struct timehist* hist, long long* array, size_t sz)
229	0	{
230	0	size_t i;
231	0	if(!hist) return;
232	0	if(sz > hist->num)
233	0	sz = hist->num;
234	0	for(i=0; i<sz; i++)
235	0	array[i] = (long long)hist->buckets[i].count;
236	0	}
237
238		void
239		timehist_import(struct timehist* hist, long long* array, size_t sz)
240	0	{
241	0	size_t i;
242	0	if(!hist) return;
243	0	if(sz > hist->num)
244	0	sz = hist->num;
245	0	for(i=0; i<sz; i++)
246	0	hist->buckets[i].count = (size_t)array[i];
247	0	}