src/vppinfra/test_timing_wheel.c - fdio/vpp - Gitiles

 /*
  * Copyright (c) 2015 Cisco and/or its affiliates.
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at:
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 #include <vppinfra/bitmap.h>
 #include <vppinfra/error.h>
 #include <vppinfra/format.h>
 #include <vppinfra/pool.h>
 #include <vppinfra/random.h>
 #include <vppinfra/time.h>
 #include <vppinfra/timing_wheel.h>
 #include <vppinfra/zvec.h>

 #include <vppinfra/math.h>

 #if __GNUC__ < 4
 #define SQRT(a) a
 #else
 #define SQRT(a) sqrt(a)
 #endif

 typedef struct
 {
   uword n_iter;

   u32 n_events;
   u32 seed;
   u32 verbose;

   /* Time is "synthetic" e.g. not taken from CPU timer. */
   u32 synthetic_time;

   clib_time_t time;
   timing_wheel_t timing_wheel;

   u64 *events;

   f64 max_time;
   f64 wait_time;

   f64 total_iterate_time;
   f64 time_iterate_start;

   f64 time_per_status_update;
   f64 time_next_status_update;
 } test_timing_wheel_main_t;

 typedef struct
 {
   f64 dt;
   f64 fraction;
   u64 count;
 } test_timing_wheel_tmp_t;

 static void
 set_event (test_timing_wheel_main_t * tm, uword i)
 {
   timing_wheel_t *w = &tm->timing_wheel;
   u64 cpu_time;

   cpu_time = w->current_time_index << w->log2_clocks_per_bin;
   if (tm->synthetic_time)
     cpu_time += random_u32 (&tm->seed) % tm->n_iter;
   else
     cpu_time +=
       random_f64 (&tm->seed) * tm->max_time * tm->time.clocks_per_second;

   timing_wheel_insert (w, cpu_time, i);
   timing_wheel_validate (w);
   tm->events[i] = cpu_time;
 }

 static int
 test_timing_wheel_tmp_cmp (void *a1, void *a2)
 {
   test_timing_wheel_tmp_t *f1 = a1;
   test_timing_wheel_tmp_t *f2 = a2;

   return f1->dt < f2->dt ? -1 : (f1->dt > f2->dt ? +1 : 0);
 }

 clib_error_t *
 test_timing_wheel_main (unformat_input_t * input)
 {
   clib_error_t *error = 0;
   test_timing_wheel_main_t _tm, *tm = &_tm;
   timing_wheel_t *w = &tm->timing_wheel;
   uword iter, i;

   memset (tm, 0, sizeof (tm[0]));
   tm->n_iter = 10;
   tm->time_per_status_update = 0;
   tm->n_events = 100;
   tm->seed = 1;
   tm->synthetic_time = 1;
   tm->max_time = 1;
   tm->wait_time = 1e-3;

   w->validate = 0;
   w->n_wheel_elt_time_bits = 32;

   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
     {
       if (unformat (input, "iter %wd", &tm->n_iter))
 	;
       else if (unformat (input, "events %d", &tm->n_events))
 	;
       else
 	if (unformat (input, "elt-time-bits %d", &w->n_wheel_elt_time_bits))
 	;
       else if (unformat (input, "seed %d", &tm->seed))
 	;
       else if (unformat (input, "verbose"))
 	tm->verbose = 1;
       else if (unformat (input, "validate"))
 	w->validate = 1;

       else if (unformat (input, "real-time"))
 	tm->synthetic_time = 0;
       else if (unformat (input, "synthetic-time"))
 	tm->synthetic_time = 1;
       else if (unformat (input, "max-time %f", &tm->max_time))
 	;
       else if (unformat (input, "wait-time %f", &tm->wait_time))
 	;
       else if (unformat (input, "iter-time %f", &tm->total_iterate_time))
 	;
       else if (unformat (input, "print %f", &tm->time_per_status_update))
 	;

       else
 	{
 	  error = clib_error_create ("unknown input `%U'\n",
 				     format_unformat_error, input);
 	  goto done;
 	}
     }

   if (!tm->seed)
     tm->seed = random_default_seed ();

   clib_time_init (&tm->time);

   if (tm->synthetic_time)
     {
       w->min_sched_time = tm->time.seconds_per_clock;
       w->max_sched_time = w->min_sched_time * 256;
       timing_wheel_init (w, 0, tm->time.clocks_per_second);
     }
   else
     {
       timing_wheel_init (w, clib_cpu_time_now (), tm->time.clocks_per_second);
     }

   clib_warning ("iter %wd, events %d, seed %u, %U",
 		tm->n_iter, tm->n_events, tm->seed,
 		format_timing_wheel, &tm->timing_wheel, /* verbose */ 0);

   /* Make some events. */
   vec_resize (tm->events, tm->n_events);
   for (i = 0; i < vec_len (tm->events); i++)
     set_event (tm, i);

   {
     u32 *expired = 0;
     f64 ave_error = 0;
     f64 rms_error = 0;
     f64 max_error = 0, min_error = 1e30;
     u32 *error_hist = 0;
     uword n_expired = 0;
     uword *expired_bitmap[2] = { 0 };
     uword n_events_in_wheel = vec_len (tm->events);

     vec_resize (expired, 32);
     vec_resize (error_hist, 1024);

     tm->time_iterate_start = clib_time_now (&tm->time);
     tm->time_next_status_update =
       tm->time_iterate_start + tm->time_per_status_update;

     if (tm->total_iterate_time != 0)
       tm->n_iter = ~0;

     for (iter = 0; iter < tm->n_iter || n_events_in_wheel > 0; iter++)
       {
 	u64 cpu_time, min_next_time[2];

 	if (tm->synthetic_time)
 	  cpu_time = iter << w->log2_clocks_per_bin;
 	else
 	  cpu_time = clib_cpu_time_now ();

 	_vec_len (expired) = 0;
 	expired =
 	  timing_wheel_advance (w, cpu_time, expired, &min_next_time[0]);
 	timing_wheel_validate (w);

 	/* Update bitmap of expired events. */
 	if (w->validate)
 	  {
 	    for (i = 0; i < vec_len (tm->events); i++)
 	      {
 		uword is_expired;

 		is_expired =
 		  (cpu_time >> w->log2_clocks_per_bin) >=
 		  (tm->events[i] >> w->log2_clocks_per_bin);
 		expired_bitmap[0] =
 		  clib_bitmap_set (expired_bitmap[0], i, is_expired);

 		/* Validate min next time. */
 		if (is_expired)
 		  ASSERT (min_next_time[0] > tm->events[i]);
 		else
 		  ASSERT (min_next_time[0] <= tm->events[i]);
 	      }
 	  }

 	n_expired += vec_len (expired);
 	for (i = 0; i < vec_len (expired); i++)
 	  {
 	    word j, idt;
 	    i64 dt_cpu;
 	    f64 fdt_cpu;

 	    j = expired[i];
 	    expired_bitmap[1] = clib_bitmap_ori (expired_bitmap[1], j);

 	    dt_cpu = cpu_time - tm->events[j];

 	    /* Event must be scheduled in correct bin. */
 	    if (tm->synthetic_time)
 	      ASSERT (dt_cpu >= 0 && dt_cpu <= (1 << w->log2_clocks_per_bin));

 	    fdt_cpu = dt_cpu * tm->time.seconds_per_clock;

 	    ave_error += fdt_cpu;
 	    rms_error += fdt_cpu * fdt_cpu;

 	    if (fdt_cpu > max_error)
 	      max_error = fdt_cpu;
 	    if (fdt_cpu < min_error)
 	      min_error = fdt_cpu;

 	    idt =
 	      (cpu_time >> w->log2_clocks_per_bin) -
 	      (tm->events[j] >> w->log2_clocks_per_bin);
 	    idt = zvec_signed_to_unsigned (idt);
 	    vec_validate (error_hist, idt);
 	    error_hist[idt] += 1;
 	  }

 	if (w->validate)
 	  for (i = 0; i < vec_len (tm->events); i++)
 	    {
 	      int is_expired = clib_bitmap_get (expired_bitmap[0], i);
 	      int is_expired_w = clib_bitmap_get (expired_bitmap[1], i);
 	      ASSERT (is_expired == is_expired_w);
 	    }

 	min_next_time[1] = ~0;
 	for (i = 0; i < vec_len (tm->events); i++)
 	  {
 	    if (!clib_bitmap_get (expired_bitmap[1], i))
 	      min_next_time[1] = clib_min (min_next_time[1], tm->events[i]);
 	  }
 	if (min_next_time[0] != min_next_time[1])
 	  clib_error ("min next time wrong 0x%Lx != 0x%Lx", min_next_time[0],
 		      min_next_time[1]);

 	if (tm->time_per_status_update != 0
 	    && clib_time_now (&tm->time) >= tm->time_next_status_update)
 	  {
 	    f64 ave = 0, rms = 0;

 	    tm->time_next_status_update += tm->time_per_status_update;
 	    if (n_expired > 0)
 	      {
 		ave = ave_error / n_expired;
 		rms = SQRT (rms_error / n_expired - ave * ave);
 	      }

 	    clib_warning
 	      ("%12wd iter done %10wd expired; ave. error %.4e +- %.4e, range %.4e %.4e",
 	       iter, n_expired, ave, rms, min_error, max_error);
 	  }

 	if (tm->total_iterate_time != 0
 	    && (clib_time_now (&tm->time) - tm->time_iterate_start
 		>= tm->total_iterate_time))
 	  tm->n_iter = iter;

 	/* Add new events to wheel to replace expired ones. */
 	n_events_in_wheel -= vec_len (expired);
 	if (iter < tm->n_iter)
 	  {
 	    for (i = 0; i < vec_len (expired); i++)
 	      {
 		uword j = expired[i];
 		set_event (tm, j);
 		expired_bitmap[1] =
 		  clib_bitmap_andnoti (expired_bitmap[1], j);
 	      }
 	    n_events_in_wheel += vec_len (expired);
 	  }
       }

     ave_error /= n_expired;
     rms_error = SQRT (rms_error / n_expired - ave_error * ave_error);

     clib_warning
       ("%wd iter done %wd expired; ave. error %.4e +- %.4e, range %.4e %.4e",
        1 + iter, n_expired, ave_error, rms_error, min_error, max_error);

     {
       test_timing_wheel_tmp_t *fs, *f;
       f64 total_fraction;

       fs = 0;
       for (i = 0; i < vec_len (error_hist); i++)
 	{
 	  if (error_hist[i] == 0)
 	    continue;
 	  vec_add2 (fs, f, 1);
 	  f->dt =
 	    (((i64) zvec_unsigned_to_signed (i) << w->log2_clocks_per_bin) *
 	     tm->time.seconds_per_clock);
 	  f->fraction = (f64) error_hist[i] / (f64) n_expired;
 	  f->count = error_hist[i];
 	}

       vec_sort_with_function (fs, test_timing_wheel_tmp_cmp);

       total_fraction = 0;
       vec_foreach (f, fs)
       {
 	total_fraction += f->fraction;
 	if (f == fs)
 	  fformat (stdout, "%=12s %=16s %=16s %s\n", "Error max", "Fraction",
 		   "Total", "Count");
 	fformat (stdout, "%12.4e %16.4f%% %16.4f%% %Ld\n", f->dt,
 		 f->fraction * 100, total_fraction * 100, f->count);
       }
     }

     clib_warning ("%U", format_timing_wheel, w, /* verbose */ 1);
   }

 done:
   return error;
 }

 #ifdef CLIB_UNIX
 int
 main (int argc, char *argv[])
 {
   unformat_input_t i;
   clib_error_t *error;

   unformat_init_command_line (&i, argv);
   error = test_timing_wheel_main (&i);
   unformat_free (&i);
   if (error)
     {
       clib_error_report (error);
       return 1;
     }
   else
     return 0;
 }
 #endif /* CLIB_UNIX */

 /*
  * fd.io coding-style-patch-verification: ON
  *
  * Local Variables:
  * eval: (c-set-style "gnu")
  * End:
  */
	/*
	* Copyright (c) 2015 Cisco and/or its affiliates.
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at:
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	#include <vppinfra/bitmap.h>
	#include <vppinfra/error.h>
	#include <vppinfra/format.h>
	#include <vppinfra/pool.h>
	#include <vppinfra/random.h>
	#include <vppinfra/time.h>
	#include <vppinfra/timing_wheel.h>
	#include <vppinfra/zvec.h>

	#include <vppinfra/math.h>

	#if __GNUC__ < 4
	#define SQRT(a) a
	#else
	#define SQRT(a) sqrt(a)
	#endif

	typedef struct
	{
	uword n_iter;

	u32 n_events;
	u32 seed;
	u32 verbose;

	/* Time is "synthetic" e.g. not taken from CPU timer. */
	u32 synthetic_time;

	clib_time_t time;
	timing_wheel_t timing_wheel;

	u64 *events;

	f64 max_time;
	f64 wait_time;

	f64 total_iterate_time;
	f64 time_iterate_start;

	f64 time_per_status_update;
	f64 time_next_status_update;
	} test_timing_wheel_main_t;

	typedef struct
	{
	f64 dt;
	f64 fraction;
	u64 count;
	} test_timing_wheel_tmp_t;

	static void
	set_event (test_timing_wheel_main_t * tm, uword i)
	{
	timing_wheel_t *w = &tm->timing_wheel;
	u64 cpu_time;

	cpu_time = w->current_time_index << w->log2_clocks_per_bin;
	if (tm->synthetic_time)
	cpu_time += random_u32 (&tm->seed) % tm->n_iter;
	else
	cpu_time +=
	random_f64 (&tm->seed) * tm->max_time * tm->time.clocks_per_second;

	timing_wheel_insert (w, cpu_time, i);
	timing_wheel_validate (w);
	tm->events[i] = cpu_time;
	}

	static int
	test_timing_wheel_tmp_cmp (void a1, void a2)
	{
	test_timing_wheel_tmp_t *f1 = a1;
	test_timing_wheel_tmp_t *f2 = a2;

	return f1->dt < f2->dt ? -1 : (f1->dt > f2->dt ? +1 : 0);
	}

	clib_error_t *
	test_timing_wheel_main (unformat_input_t * input)
	{
	clib_error_t *error = 0;
	test_timing_wheel_main_t _tm, *tm = &_tm;
	timing_wheel_t *w = &tm->timing_wheel;
	uword iter, i;

	memset (tm, 0, sizeof (tm[0]));
	tm->n_iter = 10;
	tm->time_per_status_update = 0;
	tm->n_events = 100;
	tm->seed = 1;
	tm->synthetic_time = 1;
	tm->max_time = 1;
	tm->wait_time = 1e-3;

	w->validate = 0;
	w->n_wheel_elt_time_bits = 32;

	while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
	{
	if (unformat (input, "iter %wd", &tm->n_iter))
	;
	else if (unformat (input, "events %d", &tm->n_events))
	;
	else
	if (unformat (input, "elt-time-bits %d", &w->n_wheel_elt_time_bits))
	;
	else if (unformat (input, "seed %d", &tm->seed))
	;
	else if (unformat (input, "verbose"))
	tm->verbose = 1;
	else if (unformat (input, "validate"))
	w->validate = 1;

	else if (unformat (input, "real-time"))
	tm->synthetic_time = 0;
	else if (unformat (input, "synthetic-time"))
	tm->synthetic_time = 1;
	else if (unformat (input, "max-time %f", &tm->max_time))
	;
	else if (unformat (input, "wait-time %f", &tm->wait_time))
	;
	else if (unformat (input, "iter-time %f", &tm->total_iterate_time))
	;
	else if (unformat (input, "print %f", &tm->time_per_status_update))
	;

	else
	{
	error = clib_error_create ("unknown input `%U'\n",
	format_unformat_error, input);
	goto done;
	}
	}

	if (!tm->seed)
	tm->seed = random_default_seed ();

	clib_time_init (&tm->time);

	if (tm->synthetic_time)
	{
	w->min_sched_time = tm->time.seconds_per_clock;
	w->max_sched_time = w->min_sched_time * 256;
	timing_wheel_init (w, 0, tm->time.clocks_per_second);
	}
	else
	{
	timing_wheel_init (w, clib_cpu_time_now (), tm->time.clocks_per_second);
	}

	clib_warning ("iter %wd, events %d, seed %u, %U",
	tm->n_iter, tm->n_events, tm->seed,
	format_timing_wheel, &tm->timing_wheel, /* verbose */ 0);

	/* Make some events. */
	vec_resize (tm->events, tm->n_events);
	for (i = 0; i < vec_len (tm->events); i++)
	set_event (tm, i);

	{
	u32 *expired = 0;
	f64 ave_error = 0;
	f64 rms_error = 0;
	f64 max_error = 0, min_error = 1e30;
	u32 *error_hist = 0;
	uword n_expired = 0;
	uword *expired_bitmap[2] = { 0 };
	uword n_events_in_wheel = vec_len (tm->events);

	vec_resize (expired, 32);
	vec_resize (error_hist, 1024);

	tm->time_iterate_start = clib_time_now (&tm->time);
	tm->time_next_status_update =
	tm->time_iterate_start + tm->time_per_status_update;

	if (tm->total_iterate_time != 0)
	tm->n_iter = ~0;

	for (iter = 0; iter < tm->n_iter \|\| n_events_in_wheel > 0; iter++)
	{
	u64 cpu_time, min_next_time[2];

	if (tm->synthetic_time)
	cpu_time = iter << w->log2_clocks_per_bin;
	else
	cpu_time = clib_cpu_time_now ();

	_vec_len (expired) = 0;
	expired =
	timing_wheel_advance (w, cpu_time, expired, &min_next_time[0]);
	timing_wheel_validate (w);

	/* Update bitmap of expired events. */
	if (w->validate)
	{
	for (i = 0; i < vec_len (tm->events); i++)
	{
	uword is_expired;

	is_expired =
	(cpu_time >> w->log2_clocks_per_bin) >=
	(tm->events[i] >> w->log2_clocks_per_bin);
	expired_bitmap[0] =
	clib_bitmap_set (expired_bitmap[0], i, is_expired);

	/* Validate min next time. */
	if (is_expired)
	ASSERT (min_next_time[0] > tm->events[i]);
	else
	ASSERT (min_next_time[0] <= tm->events[i]);
	}
	}

	n_expired += vec_len (expired);
	for (i = 0; i < vec_len (expired); i++)
	{
	word j, idt;
	i64 dt_cpu;
	f64 fdt_cpu;

	j = expired[i];
	expired_bitmap[1] = clib_bitmap_ori (expired_bitmap[1], j);

	dt_cpu = cpu_time - tm->events[j];

	/* Event must be scheduled in correct bin. */
	if (tm->synthetic_time)
	ASSERT (dt_cpu >= 0 && dt_cpu <= (1 << w->log2_clocks_per_bin));

	fdt_cpu = dt_cpu * tm->time.seconds_per_clock;

	ave_error += fdt_cpu;
	rms_error += fdt_cpu * fdt_cpu;

	if (fdt_cpu > max_error)
	max_error = fdt_cpu;
	if (fdt_cpu < min_error)
	min_error = fdt_cpu;

	idt =
	(cpu_time >> w->log2_clocks_per_bin) -
	(tm->events[j] >> w->log2_clocks_per_bin);
	idt = zvec_signed_to_unsigned (idt);
	vec_validate (error_hist, idt);
	error_hist[idt] += 1;
	}

	if (w->validate)
	for (i = 0; i < vec_len (tm->events); i++)
	{
	int is_expired = clib_bitmap_get (expired_bitmap[0], i);
	int is_expired_w = clib_bitmap_get (expired_bitmap[1], i);
	ASSERT (is_expired == is_expired_w);
	}

	min_next_time[1] = ~0;
	for (i = 0; i < vec_len (tm->events); i++)
	{
	if (!clib_bitmap_get (expired_bitmap[1], i))
	min_next_time[1] = clib_min (min_next_time[1], tm->events[i]);
	}
	if (min_next_time[0] != min_next_time[1])
	clib_error ("min next time wrong 0x%Lx != 0x%Lx", min_next_time[0],
	min_next_time[1]);

	if (tm->time_per_status_update != 0
	&& clib_time_now (&tm->time) >= tm->time_next_status_update)
	{
	f64 ave = 0, rms = 0;

	tm->time_next_status_update += tm->time_per_status_update;
	if (n_expired > 0)
	{
	ave = ave_error / n_expired;
	rms = SQRT (rms_error / n_expired - ave * ave);
	}

	clib_warning
	("%12wd iter done %10wd expired; ave. error %.4e +- %.4e, range %.4e %.4e",
	iter, n_expired, ave, rms, min_error, max_error);
	}

	if (tm->total_iterate_time != 0
	&& (clib_time_now (&tm->time) - tm->time_iterate_start
	>= tm->total_iterate_time))
	tm->n_iter = iter;

	/* Add new events to wheel to replace expired ones. */
	n_events_in_wheel -= vec_len (expired);
	if (iter < tm->n_iter)
	{
	for (i = 0; i < vec_len (expired); i++)
	{
	uword j = expired[i];
	set_event (tm, j);
	expired_bitmap[1] =
	clib_bitmap_andnoti (expired_bitmap[1], j);
	}
	n_events_in_wheel += vec_len (expired);
	}
	}

	ave_error /= n_expired;
	rms_error = SQRT (rms_error / n_expired - ave_error * ave_error);

	clib_warning
	("%wd iter done %wd expired; ave. error %.4e +- %.4e, range %.4e %.4e",
	1 + iter, n_expired, ave_error, rms_error, min_error, max_error);

	{
	test_timing_wheel_tmp_t fs, f;
	f64 total_fraction;

	fs = 0;
	for (i = 0; i < vec_len (error_hist); i++)
	{
	if (error_hist[i] == 0)
	continue;
	vec_add2 (fs, f, 1);
	f->dt =
	(((i64) zvec_unsigned_to_signed (i) << w->log2_clocks_per_bin) *
	tm->time.seconds_per_clock);
	f->fraction = (f64) error_hist[i] / (f64) n_expired;
	f->count = error_hist[i];
	}

	vec_sort_with_function (fs, test_timing_wheel_tmp_cmp);

	total_fraction = 0;
	vec_foreach (f, fs)
	{
	total_fraction += f->fraction;
	if (f == fs)
	fformat (stdout, "%=12s %=16s %=16s %s\n", "Error max", "Fraction",
	"Total", "Count");
	fformat (stdout, "%12.4e %16.4f%% %16.4f%% %Ld\n", f->dt,
	f->fraction * 100, total_fraction * 100, f->count);
	}
	}

	clib_warning ("%U", format_timing_wheel, w, /* verbose */ 1);
	}

	done:
	return error;
	}

	#ifdef CLIB_UNIX
	int
	main (int argc, char *argv[])
	{
	unformat_input_t i;
	clib_error_t *error;

	unformat_init_command_line (&i, argv);
	error = test_timing_wheel_main (&i);
	unformat_free (&i);
	if (error)
	{
	clib_error_report (error);
	return 1;
	}
	else
	return 0;
	}
	#endif /* CLIB_UNIX */

	/*
	* fd.io coding-style-patch-verification: ON
	*
	* Local Variables:
	* eval: (c-set-style "gnu")
	* End:
	*/