2 * Copyright (c) 2015 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
15 #include <vppinfra/bitmap.h>
16 #include <vppinfra/error.h>
17 #include <vppinfra/format.h>
18 #include <vppinfra/pool.h>
19 #include <vppinfra/random.h>
20 #include <vppinfra/time.h>
21 #include <vppinfra/timing_wheel.h>
22 #include <vppinfra/zvec.h>
24 #include <vppinfra/math.h>
29 #define SQRT(a) sqrt(a)
39 /* Time is "synthetic" e.g. not taken from CPU timer. */
43 timing_wheel_t timing_wheel;
50 f64 total_iterate_time;
51 f64 time_iterate_start;
53 f64 time_per_status_update;
54 f64 time_next_status_update;
55 } test_timing_wheel_main_t;
61 } test_timing_wheel_tmp_t;
63 static void set_event (test_timing_wheel_main_t * tm, uword i)
65 timing_wheel_t * w = &tm->timing_wheel;
68 cpu_time = w->current_time_index << w->log2_clocks_per_bin;
69 if (tm->synthetic_time)
70 cpu_time += random_u32 (&tm->seed) % tm->n_iter;
72 cpu_time += random_f64 (&tm->seed) * tm->max_time * tm->time.clocks_per_second;
74 timing_wheel_insert (w, cpu_time, i);
75 timing_wheel_validate (w);
76 tm->events[i] = cpu_time;
79 static int test_timing_wheel_tmp_cmp (void * a1, void * a2)
81 test_timing_wheel_tmp_t * f1 = a1;
82 test_timing_wheel_tmp_t * f2 = a2;
84 return f1->dt < f2->dt ? -1 : (f1->dt > f2->dt ? +1 : 0);
88 test_timing_wheel_main (unformat_input_t * input)
90 clib_error_t * error = 0;
91 test_timing_wheel_main_t _tm, * tm = &_tm;
92 timing_wheel_t * w = &tm->timing_wheel;
95 memset (tm, 0, sizeof (tm[0]));
97 tm->time_per_status_update = 0;
100 tm->synthetic_time = 1;
102 tm->wait_time = 1e-3;
105 w->n_wheel_elt_time_bits = 32;
107 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
109 if (unformat (input, "iter %wd", &tm->n_iter))
111 else if (unformat (input, "events %d", &tm->n_events))
113 else if (unformat (input, "elt-time-bits %d", &w->n_wheel_elt_time_bits))
115 else if (unformat (input, "seed %d", &tm->seed))
117 else if (unformat (input, "verbose"))
119 else if (unformat (input, "validate"))
122 else if (unformat (input, "real-time"))
123 tm->synthetic_time = 0;
124 else if (unformat (input, "synthetic-time"))
125 tm->synthetic_time = 1;
126 else if (unformat (input, "max-time %f", &tm->max_time))
128 else if (unformat (input, "wait-time %f", &tm->wait_time))
130 else if (unformat (input, "iter-time %f", &tm->total_iterate_time))
132 else if (unformat (input, "print %f", &tm->time_per_status_update))
137 error = clib_error_create ("unknown input `%U'\n",
138 format_unformat_error, input);
144 tm->seed = random_default_seed ();
146 clib_time_init (&tm->time);
148 if (tm->synthetic_time)
150 w->min_sched_time = tm->time.seconds_per_clock;
151 w->max_sched_time = w->min_sched_time * 256;
152 timing_wheel_init (w, 0, tm->time.clocks_per_second);
156 timing_wheel_init (w, clib_cpu_time_now (), tm->time.clocks_per_second);
159 clib_warning ("iter %wd, events %d, seed %u, %U",
160 tm->n_iter, tm->n_events, tm->seed,
161 format_timing_wheel, &tm->timing_wheel, /* verbose */ 0);
163 /* Make some events. */
164 vec_resize (tm->events, tm->n_events);
165 for (i = 0; i < vec_len (tm->events); i++)
172 f64 max_error = 0, min_error = 1e30;
173 u32 * error_hist = 0;
175 uword * expired_bitmap[2] = {0};
176 uword n_events_in_wheel = vec_len (tm->events);
178 vec_resize (expired, 32);
179 vec_resize (error_hist, 1024);
181 tm->time_iterate_start = clib_time_now (&tm->time);
182 tm->time_next_status_update = tm->time_iterate_start + tm->time_per_status_update;
184 if (tm->total_iterate_time != 0)
187 for (iter = 0; iter < tm->n_iter || n_events_in_wheel > 0; iter++)
189 u64 cpu_time, min_next_time[2];
191 if (tm->synthetic_time)
192 cpu_time = iter << w->log2_clocks_per_bin;
194 cpu_time = clib_cpu_time_now ();
196 _vec_len (expired) = 0;
197 expired = timing_wheel_advance (w, cpu_time, expired, &min_next_time[0]);
198 timing_wheel_validate (w);
200 /* Update bitmap of expired events. */
203 for (i = 0; i < vec_len (tm->events); i++)
207 is_expired = (cpu_time >> w->log2_clocks_per_bin) >= (tm->events[i] >> w->log2_clocks_per_bin);
208 expired_bitmap[0] = clib_bitmap_set (expired_bitmap[0], i, is_expired);
210 /* Validate min next time. */
212 ASSERT (min_next_time[0] > tm->events[i]);
214 ASSERT (min_next_time[0] <= tm->events[i]);
218 n_expired += vec_len (expired);
219 for (i = 0; i < vec_len (expired); i++)
226 expired_bitmap[1] = clib_bitmap_ori (expired_bitmap[1], j);
228 dt_cpu = cpu_time - tm->events[j];
230 /* Event must be scheduled in correct bin. */
231 if (tm->synthetic_time)
232 ASSERT (dt_cpu >= 0 && dt_cpu <= (1 << w->log2_clocks_per_bin));
234 fdt_cpu = dt_cpu * tm->time.seconds_per_clock;
236 ave_error += fdt_cpu;
237 rms_error += fdt_cpu * fdt_cpu;
239 if (fdt_cpu > max_error)
241 if (fdt_cpu < min_error)
244 idt = (cpu_time >> w->log2_clocks_per_bin) - (tm->events[j] >> w->log2_clocks_per_bin);
245 idt = zvec_signed_to_unsigned (idt);
246 vec_validate (error_hist, idt);
247 error_hist[idt] += 1;
251 for (i = 0; i < vec_len (tm->events); i++)
253 int is_expired = clib_bitmap_get (expired_bitmap[0], i);
254 int is_expired_w = clib_bitmap_get (expired_bitmap[1], i);
255 ASSERT (is_expired == is_expired_w);
258 min_next_time[1] = ~0;
259 for (i = 0; i < vec_len (tm->events); i++)
261 if (! clib_bitmap_get (expired_bitmap[1], i))
262 min_next_time[1] = clib_min (min_next_time[1], tm->events[i]);
264 if (min_next_time[0] != min_next_time[1])
265 clib_error ("min next time wrong 0x%Lx != 0x%Lx", min_next_time[0], min_next_time[1]);
267 if (tm->time_per_status_update != 0
268 && clib_time_now (&tm->time) >= tm->time_next_status_update)
270 f64 ave = 0, rms = 0;
272 tm->time_next_status_update += tm->time_per_status_update;
275 ave = ave_error / n_expired;
276 rms = SQRT (rms_error / n_expired - ave * ave);
279 clib_warning ("%12wd iter done %10wd expired; ave. error %.4e +- %.4e, range %.4e %.4e",
280 iter, n_expired, ave, rms, min_error, max_error);
283 if (tm->total_iterate_time != 0
284 && (clib_time_now (&tm->time) - tm->time_iterate_start
285 >= tm->total_iterate_time))
288 /* Add new events to wheel to replace expired ones. */
289 n_events_in_wheel -= vec_len (expired);
290 if (iter < tm->n_iter)
292 for (i = 0; i < vec_len (expired); i++)
294 uword j = expired[i];
296 expired_bitmap[1] = clib_bitmap_andnoti (expired_bitmap[1], j);
298 n_events_in_wheel += vec_len (expired);
302 ave_error /= n_expired;
303 rms_error = SQRT (rms_error / n_expired - ave_error * ave_error);
305 clib_warning ("%wd iter done %wd expired; ave. error %.4e +- %.4e, range %.4e %.4e",
307 ave_error, rms_error,
308 min_error, max_error);
311 test_timing_wheel_tmp_t * fs, * f;
315 for (i = 0; i < vec_len (error_hist); i++)
317 if (error_hist[i] == 0)
320 f->dt = (((i64) zvec_unsigned_to_signed (i) << w->log2_clocks_per_bin)
321 * tm->time.seconds_per_clock);
322 f->fraction = (f64) error_hist[i] / (f64) n_expired;
323 f->count = error_hist[i];
326 vec_sort_with_function (fs, test_timing_wheel_tmp_cmp);
331 total_fraction += f->fraction;
333 fformat (stdout, "%=12s %=16s %=16s %s\n", "Error max", "Fraction", "Total", "Count");
334 fformat (stdout, "%12.4e %16.4f%% %16.4f%% %Ld\n",
335 f->dt, f->fraction * 100, total_fraction * 100, f->count);
339 clib_warning ("%U", format_timing_wheel, w, /* verbose */ 1);
347 int main (int argc, char * argv[])
350 clib_error_t * error;
352 unformat_init_command_line (&i, argv);
353 error = test_timing_wheel_main (&i);
357 clib_error_report (error);
363 #endif /* CLIB_UNIX */