summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/test_tw_timer.c
blob: 47e5e49bf1ff27d762dde8564c10d169eee92073 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195

@media only all and (prefers-color-scheme: dark) {
.highlight .hll { background-color: #49483e }
.highlight .c { color: #75715e } /* Comment */
.highlight .err { color: #960050; background-color: #1e0010 } /* Error */
.highlight .k { color: #66d9ef } /* Keyword */
.highlight .l { color: #ae81ff } /* Literal */
.highlight .n { color: #f8f8f2 } /* Name */
.highlight .o { color: #f92672 } /* Operator */
.highlight .p { color: #f8f8f2 } /* Punctuation */
.highlight .ch { color: #75715e } /* Comment.Hashbang */
.highlight .cm { color: #75715e } /* Comment.Multiline */
.highlight .cp { color: #75715e } /* Comment.Preproc */
.highlight .cpf { color: #75715e } /* Comment.PreprocFile */
.highlight .c1 { color: #75715e } /* Comment.Single */
.highlight .cs { color: #75715e } /* Comment.Special */
.highlight .gd { color: #f92672 } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gi { color: #a6e22e } /* Generic.Inserted */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #75715e } /* Generic.Subheading */
.highlight .kc { color: #66d9ef } /* Keyword.Constant */
.highlight .kd { color: #66d9ef } /* Keyword.Declaration */
.highlight .kn { color: #f92672 } /* Keyword.Namespace */
.highlight .kp { color: #66d9ef } /* Keyword.Pseudo */
.highlight .kr { color: #66d9ef } /* Keyword.Reserved */
.highlight .kt { color: #66d9ef } /* Keyword.Type */
.highlight .ld { color: #e6db74 } /* Literal.Date */
.highlight .m { color: #ae81ff } /* Literal.Number */
.highlight .s { color: #e6db74 } /* Literal.String */
.highlight .na { color: #a6e22e } /* Name.Attribute */
.highlight .nb { color: #f8f8f2 } /* Name.Builtin */
.highlight .nc { color: #a6e22e } /* Name.Class */
.highlight .no { color: #66d9ef } /* Name.Constant */
.highlight .nd { color: #a6e22e } /* Name.Decorator */
.highlight .ni { color: #f8f8f2 } /* Name.Entity */
.highlight .ne { color: #a6e22e } /* Name.Exception */
.highlight .nf { color: #a6e22e } /* Name.Function */
.highlight .nl { color: #f8f8f2 } /* Name.Label */
.highlight .nn { color: #f8f8f2 } /* Name.Namespace */
.highlight .nx { color: #a6e22e } /* Name.Other */
.highlight .py { color: #f8f8f2 } /* Name.Property */
.highlight .nt { color: #f92672 } /* Name.Tag */
.highlight .nv { color: #f8f8f2 } /* Name.Variable */
.highlight .ow { color: #f92672 } /* Operator.Word */
.highlight .w { color: #f8f8f2 } /* Text.Whitespace */
.highlight .mb { color: #ae81ff } /* Literal.Number.Bin */
.highlight .mf { color: #ae81ff } /* Literal.Number.Float */
.highlight .mh { color: #ae81ff } /* Literal.Number.Hex */
.highlight .mi { color: #ae81ff } /* Literal.Number.Integer */
.highlight .mo { color: #ae81ff } /* Literal.Number.Oct */
.highlight .sa { color: #e6db74 } /* Literal.String.Affix */
.highlight .sb { color: #e6db74 } /* Literal.String.Backtick */
.highlight .sc { color: #e6db74 } /* Literal.String.Char */
.highlight .dl { color: #e6db74 } /* Literal.String.Delimiter */
.highlight .sd { color: #e6db74 } /* Literal.String.Doc */
.highlight .s2 { color: #e6db74 } /* Literal.String.Double */
.highlight .se { color: #ae81ff } /* Literal.String.Escape */
.highlight .sh { color: #e6db74 } /* Literal.String.Heredoc */
.highlight .si { color: #e6db74 } /* Literal.String.Interpol */
.highlight .sx { color: #e6db74 } /* Literal.String.Other */
.highlight .sr { color: #e6db74 } /* Literal.String.Regex */
.highlight .s1 { color: #e6db74 } /* Literal.String.Single */
.highlight .ss { color: #e6db74 } /* Literal.String.Symbol */
.highlight .bp { color: #f8f8f2 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #a6e22e } /* Name.Function.Magic */
.highlight .vc { color: #f8f8f2 } /* Name.Variable.Class */
.highlight .vg { color: #f8f8f2 } /* Name.Variable.Global */
.highlight .vi { color: #f8f8f2 } /* Name.Variable.Instance */
.highlight .vm { color: #f8f8f2 } /* Name.Variable.Magic */
.highlight .il { color: #ae81ff } /* Literal.Number.Integer.Long */
}
@media (prefers-color-scheme: light) {
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
}
#!/usr/bin/env python3

# 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.

import ipaddress
import argparse
import sys

# map add domain ip4-pfx <pfx> ip6-pfx ::/0 ip6-src <ip6-src> ea-bits-len 0 psid-offset 6 psid-len 6
# map add rule index <0> psid <psid> ip6-dst <ip6-dst>

def_ip4_pfx = '192.0.2.0/24'
def_ip6_pfx = '2001:db8::/32'
def_ip6_src = '2001:db8::1'
def_psid_offset = 6
def_psid_len = 6
def_ea_bits_len = 0

parser = argparse.ArgumentParser(description='MAP VPP configuration generator')
parser.add_argument('-t', action="store", dest="mapmode")
parser.add_argument('-f', action="store", dest="format", default="vpp")
parser.add_argument('--ip4-prefix', action="store", dest="ip4_pfx", default=def_ip4_pfx)
parser.add_argument('--ip6-prefix', action="store", dest="ip6_pfx", default=def_ip6_pfx)
parser.add_argument('--ip6-src', action="store", dest="ip6_src", default=def_ip6_src)
parser.add_argument('--psid-len', action="store", dest="psid_len", default=def_psid_len)
parser.add_argument('--psid-offset', action="store", dest="psid_offset", default=def_psid_offset)
parser.add_argument('--ea-bits-len', action="store", dest="ea_bits_len", default=def_ea_bits_len)
args = parser.parse_args()

#
# Print domain
#
def domain_print(i, ip4_pfx, ip6_pfx, ip6_src, eabits_len, psid_offset, psid_len):
    if format == 'vpp':
        print("map add domain ip4-pfx " + ip4_pfx + " ip6-pfx", ip6_pfx, "ip6-src " + ip6_src +
              " ea-bits-len", eabits_len, "psid-offset", psid_offset, "psid-len", psid_len)
    if format == 'confd':
        print("vpp softwire softwire-instances softwire-instance", i, "br-ipv6 " + ip6_src +
              " ipv6-prefix " + ip6_pfx + " ipv4-prefix " + ip4_pfx +
              " ea-bits-len", eabits_len, "psid-offset", psid_offset, "psid-len", psid_len)
    if format == 'xml':
        print("<softwire-instance>")
        print("<id>", i, "</id>");
        print("  <br-ipv6>" + ip6_src + "</br-ipv6>")
        print("  <ipv6-prefix>" + ip6_pfx + "</ipv6-prefix>")
        print("  <ipv4-prefix>" + ip4_pfx + "</ipv4-prefix>")
        print("  <ea-len>", eabits_len, "</ea-len>")
        print("  <psid-len>", psid_len, "</psid-len>")
        print("  <psid-offset>", psid_offset, "</psid-offset>")

def domain_print_end():
    if format == 'xml':
        print("</softwire-instance>")

def rule_print(i, psid, dst):
    if format == 'vpp':
        print("map add rule index", i, "psid", psid, "ip6-dst", dst)
    if format == 'confd':
        print("binding", psid, "ipv6-addr", dst)
    if format == 'xml':
        print("  <binding>")
        print("    <psid>", psid, "</psid>")
        print("    <ipv6-addr>", dst, "</ipv6-addr>")
        print("  </binding>")

#
# Algorithmic mapping Shared IPv4 address
#
def algo(ip4_pfx_str, ip6_pfx_str, ip6_src_str, ea_bits_len, psid_offset, psid_len, ip6_src_ecmp = False):
    domain_print(0, ip4_pfx_str, ip6_pfx_str, ip6_src_str, ea_bits_len, psid_offset, psid_len)
    domain_print_end()

#
# 1:1 Full IPv4 address
#
def lw46(ip4_pfx_str, ip6_pfx_str, ip6_src_str, ea_bits_len, psid_offset, psid_len, ip6_src_ecmp = False):
    ip4_pfx = ipaddress.ip_network(ip4_pfx_str)
    ip6_src = ipaddress.ip_address(ip6_src_str)
    ip6_dst = ipaddress.ip_network(ip6_pfx_str)
    psid_len = 0
    mod = ip4_pfx.num_addresses / 1024

    for i in range(ip4_pfx.num_addresses):
        domain_print(i, str(ip4_pfx[i]) + "/32", str(ip6_dst[i]) + "/128", str(ip6_src), 0, 0, 0)
        domain_print_end()
        if ip6_src_ecmp and not i % mod:
            ip6_src = ip6_src + 1

#
# 1:1 Shared IPv4 address, shared BR (16) VPP CLI
#
def lw46_shared(ip4_pfx_str, ip6_pfx_str, ip6_src_str, ea_bits_len, psid_offset, psid_len, ip6_src_ecmp = False):
    ip4_pfx = ipaddress.ip_network(ip4_pfx_str)
    ip6_src = ipaddress.ip_address(ip6_src_str)
    ip6_dst = ipaddress.ip_network(ip6_pfx_str)
    mod = ip4_pfx.num_addresses / 1024

    for i in range(ip4_pfx.num_addresses):
        domain_print(i, str(ip4_pfx[i]) + "/32", "::/0", str(ip6_src), 0, 0, psid_len)
        for psid in range(0x1 << int(psid_len)):
            rule_print(i, psid, str(ip6_dst[(i * (0x1<<int(psid_len))) + psid]))
        domain_print_end()
        if ip6_src_ecmp and not i % mod:
            ip6_src = ip6_src + 1


#
# 1:1 Shared IPv4 address, shared BR
#
def lw46_shared_b(ip4_pfx_str, ip6_pfx_str, ip6_src_str, ea_bits_len, psid_offset, psid_len, ip6_src_ecmp = False):
    ip4_pfx = ipaddress.ip_network(ip4_pfx_str)
    ip6_src = ipaddress.ip_address(ip6_src_str)
    ip6_dst = list(ipaddress.ip_network(ip6_pfx_str).subnets(new_prefix=56))
    mod = ip4_pfx.num_addresses / 1024

    for i in range(ip4_pfx.num_addresses):
        domain_print(i, str(ip4_pfx[i]) + "/32", "::/0", str(ip6_src), 0, 0, psid_len)
        for psid in range(0x1 << psid_len):
            enduserprefix = list(ip6_dst.pop(0).subnets(new_prefix=64))[255-1]
            rule_print(i, psid, enduserprefix[(i * (0x1<<psid_len)) + psid])
        domain_print_end()
        if ip6_src_ecmp and not i % mod:
            ip6_src = ip6_src + 1


def xml_header_print():
    print('''
<?xml version="1.0" encoding="UTF-8"?>
    <hello xmlns="urn:ietf:params:xml:ns:netconf:base:1.0">
    <capabilities>
    <capability>urn:ietf:params:netconf:base:1.0</capability>
    </capabilities>
    </hello>
]]>]]>

<?xml version="1.0" encoding="UTF-8"?>
    <rpc xmlns="urn:ietf:params:xml:ns:netconf:base:1.0"  message-id="1">
    <edit-config>
    <target>
    <candidate/>
    </target>
    <config>

    <vpp xmlns="http://www.cisco.com/yang/cisco-vpp">
 <softwire>
 <softwire-instances>

    ''')

def xml_footer_print():
    print('''
</softwire-instances>
</softwire>
</vpp>
    </config>
    </edit-config>
    </rpc>

]]>]]>

<?xml version="1.0" encoding="UTF-8"?>
    <rpc xmlns="urn:ietf:params:xml:ns:netconf:base:1.0" message-id="2">
    <close-session/>
    </rpc>

]]>]]>
    ''')


format = args.format
if format == 'xml':
    xml_header_print()
globals()[args.mapmode](args.ip4_pfx, args.ip6_pfx, args.ip6_src, args.ea_bits_len, args.psid_offset, args.psid_len)
if format == 'xml':
    xml_footer_print()
> 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496
#include <vppinfra/time.h>
#include <vppinfra/cache.h>
#include <vppinfra/error.h>
#include <vppinfra/tw_timer_2t_1w_2048sl.h>
#include <vppinfra/tw_timer_2t_2w_512sl.h>
#include <vppinfra/tw_timer_16t_2w_512sl.h>
#include <vppinfra/tw_timer_4t_3w_256sl.h>
#include <vppinfra/tw_timer_1t_3w_1024sl_ov.h>

typedef struct
{
  /** Handle returned from tw_start_timer */
  u32 stop_timer_handle;

  /** Test item should expire at this clock tick */
  u64 expected_to_expire;
} tw_timer_test_elt_t;

typedef struct
{
  /** Pool of test objects */
  tw_timer_test_elt_t *test_elts;

  /** The single-wheel */
  tw_timer_wheel_2t_1w_2048sl_t single_wheel;

  /** The double-wheel */
  tw_timer_wheel_16t_2w_512sl_t double_wheel;

  /* The triple wheel */
  tw_timer_wheel_4t_3w_256sl_t triple_wheel;

  /* The triple wheel with overflow vector */
  tw_timer_wheel_1t_3w_1024sl_ov_t triple_ov_wheel;

  /* Another two timer wheel geometry */
  tw_timer_wheel_2t_2w_512sl_t two_timer_double_wheel;

  /** random number seed */
  u64 seed;

  /** number of timers */
  u32 ntimers;

  /** number of "churn" iterations */
  u32 niter;

  /** number of clock ticks per churn iteration */
  u32 ticks_per_iter;

  /** cpu timer */
  clib_time_t clib_time;
} tw_timer_test_main_t;

tw_timer_test_main_t tw_timer_test_main;

static void
run_single_wheel (tw_timer_wheel_2t_1w_2048sl_t * tw, u32 n_ticks)
{
  u32 i;
  f64 now = tw->last_run_time + 1.01;

  for (i = 0; i < n_ticks; i++)
    {
      tw_timer_expire_timers_2t_1w_2048sl (tw, now);
      now += 1.01;
    }
}

static void
run_double_wheel (tw_timer_wheel_16t_2w_512sl_t * tw, u32 n_ticks)
{
  u32 i;
  f64 now = tw->last_run_time + 1.01;

  for (i = 0; i < n_ticks; i++)
    {
      tw_timer_expire_timers_16t_2w_512sl (tw, now);
      now += 1.01;
    }
}

static void
run_two_timer_double_wheel (tw_timer_wheel_2t_2w_512sl_t * tw, u32 n_ticks)
{
  u32 i;
  f64 now = tw->last_run_time + 1.01;

  for (i = 0; i < n_ticks; i++)
    {
      tw_timer_expire_timers_2t_2w_512sl (tw, now);
      now += 1.01;
    }
}

static void
run_triple_wheel (tw_timer_wheel_4t_3w_256sl_t * tw, u32 n_ticks)
{
  u32 i;
  f64 now = tw->last_run_time + 1.01;

  for (i = 0; i < n_ticks; i++)
    {
      tw_timer_expire_timers_4t_3w_256sl (tw, now);
      now += 1.01;
    }
}

static void
run_triple_ov_wheel (tw_timer_wheel_1t_3w_1024sl_ov_t * tw, u32 n_ticks)
{
  u32 i;
  f64 now = tw->last_run_time + 1.01;

  for (i = 0; i < n_ticks; i++)
    {
      tw_timer_expire_timers_1t_3w_1024sl_ov (tw, now);
      now += 1.01;
    }
}

static void
expired_timer_single_callback (u32 * expired_timers)
{
  int i;
  u32 pool_index, timer_id;
  tw_timer_test_elt_t *e;
  tw_timer_test_main_t *tm = &tw_timer_test_main;

  for (i = 0; i < vec_len (expired_timers); i++)
    {
      pool_index = expired_timers[i] & 0x7FFFFFFF;
      timer_id = expired_timers[i] >> 31;

      ASSERT (timer_id == 1);

      e = pool_elt_at_index (tm->test_elts, pool_index);

      if (e->expected_to_expire != tm->single_wheel.current_tick)
	{
	  fformat (stdout, "[%d] expired at %lld not %lld\n",
		   e - tm->test_elts, tm->single_wheel.current_tick,
		   e->expected_to_expire);
	}
      pool_put (tm->test_elts, e);
    }
}

static void
expired_timer_double_callback (u32 * expired_timers)
{
  int i;
  u32 pool_index, timer_id;
  tw_timer_test_elt_t *e;
  tw_timer_test_main_t *tm = &tw_timer_test_main;

  for (i = 0; i < vec_len (expired_timers); i++)
    {
      pool_index = expired_timers[i] & 0x0FFFFFFF;
      timer_id = expired_timers[i] >> 28;

      ASSERT (timer_id == 14);

      e = pool_elt_at_index (tm->test_elts, pool_index);

      if (e->expected_to_expire != tm->double_wheel.current_tick)
	{
	  fformat (stdout, "[%d] expired at %lld not %lld\n",
		   e - tm->test_elts, tm->double_wheel.current_tick,
		   e->expected_to_expire);
	}
      pool_put (tm->test_elts, e);
    }
}

static void
expired_timer_two_timer_double_callback (u32 * expired_timers)
{
  int i;
  u32 pool_index, timer_id;
  tw_timer_test_elt_t *e;
  tw_timer_test_main_t *tm = &tw_timer_test_main;

  for (i = 0; i < vec_len (expired_timers); i++)
    {
      pool_index = expired_timers[i] & 0x7FFFFFFF;
      timer_id = expired_timers[i] >> 31;

      ASSERT (timer_id == 1);

      e = pool_elt_at_index (tm->test_elts, pool_index);

      if (e->expected_to_expire != tm->two_timer_double_wheel.current_tick)
	{
	  fformat (stdout, "[%d] expired at %lld not %lld\n",
		   e - tm->test_elts, tm->two_timer_double_wheel.current_tick,
		   e->expected_to_expire);
	}
      pool_put (tm->test_elts, e);
    }
}

static void
expired_timer_triple_callback (u32 * expired_timers)
{
  int i;
  u32 pool_index, timer_id;
  tw_timer_test_elt_t *e;
  tw_timer_test_main_t *tm = &tw_timer_test_main;

  for (i = 0; i < vec_len (expired_timers); i++)
    {
      pool_index = expired_timers[i] & 0x3FFFFFFF;
      timer_id = expired_timers[i] >> 30;

      ASSERT (timer_id == 3);

      e = pool_elt_at_index (tm->test_elts, pool_index);

      if (e->expected_to_expire != tm->triple_wheel.current_tick)
	{
	  fformat (stdout, "[%d] expired at %lld not %lld\n",
		   e - tm->test_elts, tm->triple_wheel.current_tick,
		   e->expected_to_expire);
	}
      pool_put (tm->test_elts, e);
    }
}

static void
expired_timer_triple_ov_callback (u32 * expired_timers)
{
  int i;
  u32 pool_index;
  tw_timer_test_elt_t *e;
  tw_timer_test_main_t *tm = &tw_timer_test_main;

  for (i = 0; i < vec_len (expired_timers); i++)
    {
      pool_index = expired_timers[i];

      e = pool_elt_at_index (tm->test_elts, pool_index);

      if (e->expected_to_expire != tm->triple_ov_wheel.current_tick)
	{
	  fformat (stdout, "[%d] expired at %lld not %lld\n",
		   e - tm->test_elts, tm->triple_ov_wheel.current_tick,
		   e->expected_to_expire);
	}
      pool_put (tm->test_elts, e);
    }
}

static clib_error_t *
test2_single (tw_timer_test_main_t * tm)
{
  u32 i, j;
  tw_timer_test_elt_t *e;
  u32 initial_wheel_offset;
  u64 expiration_time;
  u32 max_expiration_time = 0;
  u32 *deleted_indices = 0;
  u32 adds = 0, deletes = 0;
  f64 before, after;

  clib_time_init (&tm->clib_time);

  tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
				    expired_timer_single_callback,
				    1.0 /* timer interval */ , ~0);

  /* Prime offset */
  initial_wheel_offset = 757;

  run_single_wheel (&tm->single_wheel, initial_wheel_offset);

  fformat (stdout, "initial wheel time %d, fast index %d\n",
	   tm->single_wheel.current_tick,
	   tm->single_wheel.current_index[TW_TIMER_RING_FAST]);

  initial_wheel_offset = tm->single_wheel.current_tick;

  fformat (stdout,
	   "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
	   tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);

  before = clib_time_now (&tm->clib_time);

  /* Prime the pump */
  for (i = 0; i < tm->ntimers; i++)
    {
      pool_get (tm->test_elts, e);
      clib_memset (e, 0, sizeof (*e));

      do
	{
	  expiration_time = random_u64 (&tm->seed) & (2047);
	}
      while (expiration_time == 0);

      if (expiration_time > max_expiration_time)
	max_expiration_time = expiration_time;

      e->expected_to_expire = expiration_time + initial_wheel_offset;
      e->stop_timer_handle =
	tw_timer_start_2t_1w_2048sl (&tm->single_wheel, e - tm->test_elts,
				     1 /* timer id */ ,
				     expiration_time);
    }

  adds += i;

  for (i = 0; i < tm->niter; i++)
    {
      run_single_wheel (&tm->single_wheel, tm->ticks_per_iter);

      j = 0;
      vec_reset_length (deleted_indices);
      /* *INDENT-OFF* */
      pool_foreach (e, tm->test_elts)
       {
        tw_timer_stop_2t_1w_2048sl (&tm->single_wheel, e->stop_timer_handle);
        vec_add1 (deleted_indices, e - tm->test_elts);
        if (++j >= tm->ntimers / 4)
          goto del_and_re_add;
      }
      /* *INDENT-ON* */

    del_and_re_add:
      for (j = 0; j < vec_len (deleted_indices); j++)
	{
	  pool_put_index (tm->test_elts, deleted_indices[j]);
	}

      deletes += j;

      for (j = 0; j < tm->ntimers / 4; j++)
	{
	  pool_get (tm->test_elts, e);
	  clib_memset (e, 0, sizeof (*e));

	  do
	    {
	      expiration_time = random_u64 (&tm->seed) & (2047);
	    }
	  while (expiration_time == 0);

	  if (expiration_time > max_expiration_time)
	    max_expiration_time = expiration_time;

	  e->expected_to_expire =
	    expiration_time + tm->single_wheel.current_tick;
	  e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
	    (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
	     expiration_time);
	}
      adds += j;
    }

  vec_free (deleted_indices);

  run_single_wheel (&tm->single_wheel, max_expiration_time + 1);

  after = clib_time_now (&tm->clib_time);

  fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
	   tm->single_wheel.current_tick);
  fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
	   (after - before),
	   ((f64) adds + (f64) deletes +
	    (f64) tm->single_wheel.current_tick) / (after - before));

  if (pool_elts (tm->test_elts))
    fformat (stdout, "Note: %d elements remain in pool\n",
	     pool_elts (tm->test_elts));

  /* *INDENT-OFF* */
  pool_foreach (e, tm->test_elts)
   {
    fformat (stdout, "[%d] expected to expire %d\n",
             e - tm->test_elts,
             e->expected_to_expire);
  }
  /* *INDENT-ON* */

  pool_free (tm->test_elts);
  tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
  return 0;
}

static clib_error_t *
test2_double (tw_timer_test_main_t * tm)
{
  u32 i, j;
  tw_timer_test_elt_t *e;
  u32 initial_wheel_offset;
  u32 expiration_time;
  u32 max_expiration_time = 0;
  u32 *deleted_indices = 0;
  u32 adds = 0, deletes = 0;
  f64 before, after;

  clib_time_init (&tm->clib_time);

  tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
				    expired_timer_double_callback,
				    1.0 /* timer interval */ , ~0);

  /* Prime offset */
  initial_wheel_offset = 7577;

  run_double_wheel (&tm->double_wheel, initial_wheel_offset);

  fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
	   tm->double_wheel.current_tick,
	   tm->double_wheel.current_index[TW_TIMER_RING_FAST],
	   tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);

  initial_wheel_offset = tm->double_wheel.current_tick;

  fformat (stdout,
	   "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
	   tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);

  before = clib_time_now (&tm->clib_time);

  /* Prime the pump */
  for (i = 0; i < tm->ntimers; i++)
    {
      pool_get (tm->test_elts, e);
      clib_memset (e, 0, sizeof (*e));

      do
	{
	  expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
	}
      while (expiration_time == 0);

      if (expiration_time > max_expiration_time)
	max_expiration_time = expiration_time;

      e->expected_to_expire = expiration_time + initial_wheel_offset;

      e->stop_timer_handle =
	tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
				     14 /* timer id */ ,
				     expiration_time);
    }

  adds += i;

  for (i = 0; i < tm->niter; i++)
    {
      run_double_wheel (&tm->double_wheel, tm->ticks_per_iter);

      j = 0;
      vec_reset_length (deleted_indices);
      /* *INDENT-OFF* */
      pool_foreach (e, tm->test_elts)
       {
        tw_timer_stop_16t_2w_512sl (&tm->double_wheel, e->stop_timer_handle);
        vec_add1 (deleted_indices, e - tm->test_elts);
        if (++j >= tm->ntimers / 4)
          goto del_and_re_add;
      }
      /* *INDENT-ON* */

    del_and_re_add:
      for (j = 0; j < vec_len (deleted_indices); j++)
	pool_put_index (tm->test_elts, deleted_indices[j]);

      deletes += j;

      for (j = 0; j < tm->ntimers / 4; j++)
	{
	  pool_get (tm->test_elts, e);
	  clib_memset (e, 0, sizeof (*e));

	  do
	    {
	      expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
	    }
	  while (expiration_time == 0);

	  if (expiration_time > max_expiration_time)
	    max_expiration_time = expiration_time;

	  e->expected_to_expire = expiration_time +
	    tm->double_wheel.current_tick;

	  e->stop_timer_handle = tw_timer_start_16t_2w_512sl
	    (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
	     expiration_time);
	}
      adds += j;
    }

  vec_free (deleted_indices);

  run_double_wheel (&tm->double_wheel, max_expiration_time + 1);

  after = clib_time_now (&tm->clib_time);

  fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
	   tm->double_wheel.current_tick);
  fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
	   (after - before),
	   ((f64) adds + (f64) deletes +
	    (f64) tm->double_wheel.current_tick) / (after - before));

  if (pool_elts (tm->test_elts))
    fformat (stdout, "Note: %d elements remain in pool\n",
	     pool_elts (tm->test_elts));

  /* *INDENT-OFF* */
  pool_foreach (e, tm->test_elts)
   {
    fformat (stdout, "[%d] expected to expire %d\n",
             e - tm->test_elts,
             e->expected_to_expire);
  }
  /* *INDENT-ON* */

  pool_free (tm->test_elts);
  tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
  return 0;
}

static u32
get_expiration_time (tw_timer_test_main_t * tm)
{
  u32 expiration_time;
  do
    {
      expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
    }
  while (expiration_time == 0);
  return expiration_time;
}

static clib_error_t *
test2_double_updates (tw_timer_test_main_t * tm)
{
  u32 i, j;
  tw_timer_test_elt_t *e;
  u32 initial_wheel_offset;
  u32 expiration_time;
  u32 max_expiration_time = 0, updates = 0;
  f64 before, after;

  clib_time_init (&tm->clib_time);
  tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
				    expired_timer_double_callback,
				    1.0 /* timer interval */ , ~0);

  /* Prime offset */
  initial_wheel_offset = 7577;
  run_double_wheel (&tm->double_wheel, initial_wheel_offset);
  fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
	   tm->double_wheel.current_tick,
	   tm->double_wheel.current_index[TW_TIMER_RING_FAST],
	   tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);

  initial_wheel_offset = tm->double_wheel.current_tick;
  fformat (stdout,
	   "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
	   tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);

  before = clib_time_now (&tm->clib_time);

  /* Prime the pump */
  for (i = 0; i < tm->ntimers; i++)
    {
      pool_get (tm->test_elts, e);
      clib_memset (e, 0, sizeof (*e));

      expiration_time = get_expiration_time (tm);
      max_expiration_time = clib_max (expiration_time, max_expiration_time);

      e->expected_to_expire = expiration_time + initial_wheel_offset;
      e->stop_timer_handle = tw_timer_start_16t_2w_512sl (&tm->double_wheel,
							  e - tm->test_elts,
							  14 /* timer id */ ,
							  expiration_time);
    }

  for (i = 0; i < tm->niter; i++)
    {
      run_double_wheel (&tm->double_wheel, tm->ticks_per_iter);

      j = 0;

      /* *INDENT-OFF* */
      pool_foreach (e, tm->test_elts)
       {
        expiration_time = get_expiration_time (tm);
        max_expiration_time = clib_max (expiration_time, max_expiration_time);
	e->expected_to_expire = expiration_time
				+ tm->double_wheel.current_tick;
        tw_timer_update_16t_2w_512sl (&tm->double_wheel, e->stop_timer_handle,
                                      expiration_time);
        if (++j >= tm->ntimers / 4)
          goto done;
      }
      /* *INDENT-ON* */

    done:
      updates += j;
    }

  run_double_wheel (&tm->double_wheel, max_expiration_time + 1);

  after = clib_time_now (&tm->clib_time);

  fformat (stdout, "%d updates, %d ticks\n", updates,
	   tm->double_wheel.current_tick);
  fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
	   (after - before),
	   ((f64) updates + (f64) tm->double_wheel.current_tick) / (after -
								    before));

  if (pool_elts (tm->test_elts))
    fformat (stdout, "Note: %d elements remain in pool\n",
	     pool_elts (tm->test_elts));

  /* *INDENT-OFF* */
  pool_foreach (e, tm->test_elts)
   {
    fformat (stdout, "[%d] expected to expire %d\n",
             e - tm->test_elts,
             e->expected_to_expire);
  }
  /* *INDENT-ON* */

  pool_free (tm->test_elts);
  tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
  return 0;
}

static clib_error_t *
test2_triple (tw_timer_test_main_t * tm)
{
  u32 i, j;
  tw_timer_test_elt_t *e;
  u32 initial_wheel_offset = 0;
  u32 expiration_time;
  u32 max_expiration_time = 0;
  u32 *deleted_indices = 0;
  u32 adds = 0, deletes = 0;
  f64 before, after;

  clib_time_init (&tm->clib_time);

  tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel,
				   expired_timer_triple_callback,
				   1.0 /* timer interval */ , ~0);


  /* Prime offset */
  initial_wheel_offset = 75700;
  run_triple_wheel (&tm->triple_wheel, initial_wheel_offset);

  fformat (stdout,
	   "initial wheel time %d, fi %d si %d gi %d\n",
	   tm->triple_wheel.current_tick,
	   tm->triple_wheel.current_index[TW_TIMER_RING_FAST],
	   tm->triple_wheel.current_index[TW_TIMER_RING_SLOW],
	   tm->triple_wheel.current_index[TW_TIMER_RING_GLACIER]);

  initial_wheel_offset = tm->triple_wheel.current_tick;

  fformat (stdout,
	   "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
	   tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);

  before = clib_time_now (&tm->clib_time);

  /* Prime the pump */
  for (i = 0; i < tm->ntimers; i++)
    {
      pool_get (tm->test_elts, e);
      clib_memset (e, 0, sizeof (*e));

      do
	{
	  expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
	}
      while (expiration_time == 0);

      if (expiration_time > max_expiration_time)
	max_expiration_time = expiration_time;

      e->expected_to_expire = expiration_time + initial_wheel_offset;

      e->stop_timer_handle =
	tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts,
				    3 /* timer id */ ,
				    expiration_time);
    }

  adds += i;

  for (i = 0; i < tm->niter; i++)
    {
      run_triple_wheel (&tm->triple_wheel, tm->ticks_per_iter);

      j = 0;
      vec_reset_length (deleted_indices);
      /* *INDENT-OFF* */
      pool_foreach (e, tm->test_elts)
       {
        tw_timer_stop_4t_3w_256sl (&tm->triple_wheel, e->stop_timer_handle);
        vec_add1 (deleted_indices, e - tm->test_elts);
        if (++j >= tm->ntimers / 4)
          goto del_and_re_add;
      }
      /* *INDENT-ON* */

    del_and_re_add:
      for (j = 0; j < vec_len (deleted_indices); j++)
	pool_put_index (tm->test_elts, deleted_indices[j]);

      deletes += j;

      for (j = 0; j < tm->ntimers / 4; j++)
	{
	  pool_get (tm->test_elts, e);
	  clib_memset (e, 0, sizeof (*e));

	  do
	    {
	      expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
	    }
	  while (expiration_time == 0);

	  if (expiration_time > max_expiration_time)
	    max_expiration_time = expiration_time;

	  e->expected_to_expire = expiration_time +
	    tm->triple_wheel.current_tick;

	  e->stop_timer_handle = tw_timer_start_4t_3w_256sl
	    (&tm->triple_wheel, e - tm->test_elts, 3 /* timer id */ ,
	     expiration_time);
	}
      adds += j;
    }

  vec_free (deleted_indices);

  run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1);

  after = clib_time_now (&tm->clib_time);

  fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
	   tm->triple_wheel.current_tick);
  fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
	   (after - before),
	   ((f64) adds + (f64) deletes +
	    (f64) tm->triple_wheel.current_tick) / (after - before));

  if (pool_elts (tm->test_elts))
    fformat (stdout, "Note: %d elements remain in pool\n",
	     pool_elts (tm->test_elts));

  /* *INDENT-OFF* */
  pool_foreach (e, tm->test_elts)
   {
    fformat (stdout, "[%d] expected to expire %d\n",
             e - tm->test_elts,
             e->expected_to_expire);
  }
  /* *INDENT-ON* */

  pool_free (tm->test_elts);
  tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel);
  return 0;
}

static clib_error_t *
test2_triple_ov (tw_timer_test_main_t * tm)
{
  u32 i, j;
  tw_timer_test_elt_t *e;
  u32 initial_wheel_offset = 0;
  u32 expiration_time;
  u32 max_expiration_time = 0;
  u32 *deleted_indices = 0;
  u32 adds = 0, deletes = 0;
  f64 before, after;

  clib_time_init (&tm->clib_time);

  tw_timer_wheel_init_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
				       expired_timer_triple_ov_callback,
				       1.0 /* timer interval */ , ~0);


  /* Prime offset */
  initial_wheel_offset = 75700;
  run_triple_ov_wheel (&tm->triple_ov_wheel, initial_wheel_offset);

  fformat (stdout,
	   "initial wheel time %d, fi %d si %d gi %d\n",
	   tm->triple_ov_wheel.current_tick,
	   tm->triple_ov_wheel.current_index[TW_TIMER_RING_FAST],
	   tm->triple_ov_wheel.current_index[TW_TIMER_RING_SLOW],
	   tm->triple_ov_wheel.current_index[TW_TIMER_RING_GLACIER]);

  initial_wheel_offset = tm->triple_ov_wheel.current_tick;

  fformat (stdout,
	   "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
	   tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);

  before = clib_time_now (&tm->clib_time);

  /* Prime the pump */
  for (i = 0; i < tm->ntimers; i++)
    {
      pool_get (tm->test_elts, e);
      clib_memset (e, 0, sizeof (*e));

      do
	{
	  expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
	}
      while (expiration_time == 0);

      if (expiration_time > max_expiration_time)
	max_expiration_time = expiration_time;

      e->expected_to_expire = expiration_time + initial_wheel_offset;

      e->stop_timer_handle =
	tw_timer_start_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
					e - tm->test_elts, 0 /* timer id */ ,
					expiration_time);
    }

  adds += i;

  for (i = 0; i < tm->niter; i++)
    {
      run_triple_ov_wheel (&tm->triple_ov_wheel, tm->ticks_per_iter);

      j = 0;
      vec_reset_length (deleted_indices);
      /* *INDENT-OFF* */
      pool_foreach (e, tm->test_elts)
       {
        tw_timer_stop_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
                                       e->stop_timer_handle);
        vec_add1 (deleted_indices, e - tm->test_elts);
        if (++j >= tm->ntimers / 4)
          goto del_and_re_add;
      }
      /* *INDENT-ON* */

    del_and_re_add:
      for (j = 0; j < vec_len (deleted_indices); j++)
	pool_put_index (tm->test_elts, deleted_indices[j]);

      deletes += j;

      for (j = 0; j < tm->ntimers / 4; j++)
	{
	  pool_get (tm->test_elts, e);
	  clib_memset (e, 0, sizeof (*e));

	  do
	    {
	      expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
	    }
	  while (expiration_time == 0);

	  if (expiration_time > max_expiration_time)
	    max_expiration_time = expiration_time;

	  e->expected_to_expire = expiration_time +
	    tm->triple_ov_wheel.current_tick;

	  e->stop_timer_handle = tw_timer_start_1t_3w_1024sl_ov
	    (&tm->triple_ov_wheel, e - tm->test_elts, 0 /* timer id */ ,
	     expiration_time);
	}
      adds += j;
    }

  vec_free (deleted_indices);

  run_triple_ov_wheel (&tm->triple_ov_wheel, max_expiration_time + 1);

  after = clib_time_now (&tm->clib_time);

  fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
	   tm->triple_ov_wheel.current_tick);
  fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
	   (after - before),
	   ((f64) adds + (f64) deletes +
	    (f64) tm->triple_ov_wheel.current_tick) / (after - before));

  if (pool_elts (tm->test_elts))
    fformat (stdout, "Note: %d elements remain in pool\n",
	     pool_elts (tm->test_elts));

  /* *INDENT-OFF* */
  pool_foreach (e, tm->test_elts)
   {
    TWT (tw_timer) * t;

    fformat (stdout, "[%d] expected to expire %d\n",
             e - tm->test_elts,
             e->expected_to_expire);
    t = pool_elt_at_index (tm->triple_ov_wheel.timers, e->stop_timer_handle);
    fformat (stdout, "  expiration_time %lld\n", t->expiration_time);
  }
  /* *INDENT-ON* */

  pool_free (tm->test_elts);
  tw_timer_wheel_free_1t_3w_1024sl_ov (&tm->triple_ov_wheel);
  return 0;
}

static clib_error_t *
test1_single (tw_timer_test_main_t * tm)
{
  u32 i;
  tw_timer_test_elt_t *e;
  u32 offset;

  tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
				    expired_timer_single_callback,
				    1.0 /* timer interval */ , ~0);

  /*
   * Prime offset, to make sure that the wheel starts in a
   * non-trivial position
   */
  offset = 123;

  run_single_wheel (&tm->single_wheel, offset);

  fformat (stdout, "initial wheel time %d, fast index %d\n",
	   tm->single_wheel.current_tick,
	   tm->single_wheel.current_index[TW_TIMER_RING_FAST]);

  offset = tm->single_wheel.current_tick;

  for (i = 0; i < tm->ntimers; i++)
    {
      u32 expected_to_expire;
      u32 timer_arg;

      timer_arg = 1 + i;
      timer_arg &= 2047;
      if (timer_arg == 0)
	timer_arg = 1;

      expected_to_expire = timer_arg + tm->single_wheel.current_tick;

      pool_get (tm->test_elts, e);
      clib_memset (e, 0, sizeof (*e));
      e->expected_to_expire = expected_to_expire;
      e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
	(&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
	 timer_arg);
    }
  run_single_wheel (&tm->single_wheel, tm->ntimers + 3);

  if (pool_elts (tm->test_elts))
    fformat (stdout, "Note: %d elements remain in pool\n",
	     pool_elts (tm->test_elts));

  /* *INDENT-OFF* */
  pool_foreach (e, tm->test_elts)
   {
    fformat(stdout, "[%d] expected to expire %d\n",
                     e - tm->test_elts,
                     e->expected_to_expire);
  }
  /* *INDENT-ON* */

  fformat (stdout,
	   "final wheel time %d, fast index %d\n",
	   tm->single_wheel.current_tick,
	   tm->single_wheel.current_index[TW_TIMER_RING_FAST]);

  pool_free (tm->test_elts);
  tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
  return 0;
}

static clib_error_t *
test1_double (tw_timer_test_main_t * tm)
{
  u32 i;
  tw_timer_test_elt_t *e;
  u32 offset;

  tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
				    expired_timer_double_callback,
				    1.0 /* timer interval */ , ~0);

  /*
   * Prime offset, to make sure that the wheel starts in a
   * non-trivial position
   */
  offset = 227989;

  run_double_wheel (&tm->double_wheel, offset);

  fformat (stdout, "initial wheel time %d, fast index %d\n",
	   tm->double_wheel.current_tick,
	   tm->double_wheel.current_index[TW_TIMER_RING_FAST]);

  for (i = 0; i < tm->ntimers; i++)
    {
      pool_get (tm->test_elts, e);
      clib_memset (e, 0, sizeof (*e));

      e->expected_to_expire = i + tm->double_wheel.current_tick + 1;
      e->stop_timer_handle = tw_timer_start_16t_2w_512sl
	(&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
	 i + 1);
    }
  run_double_wheel (&tm->double_wheel, tm->ntimers + 3);

  if (pool_elts (tm->test_elts))
    fformat (stdout, "Note: %d elements remain in pool\n",
	     pool_elts (tm->test_elts));

  /* *INDENT-OFF* */
  pool_foreach (e, tm->test_elts)
   {
    fformat(stdout, "[%d] expected to expire %d\n",
                     e - tm->test_elts,
                     e->expected_to_expire);
  }
  /* *INDENT-ON* */

  fformat (stdout,
	   "final wheel time %d, fast index %d\n",
	   tm->double_wheel.current_tick,
	   tm->double_wheel.current_index[TW_TIMER_RING_FAST]);

  pool_free (tm->test_elts);
  tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
  return 0;
}

static clib_error_t *
test1_two_timer_double (tw_timer_test_main_t * tm)
{
  u32 i;
  tw_timer_test_elt_t *e;
  u32 offset;

  tw_timer_wheel_init_2t_2w_512sl (&tm->two_timer_double_wheel,
				   expired_timer_two_timer_double_callback,
				   1.0 /* timer interval */ , ~0);

  /*
   * Prime offset, to make sure that the wheel starts in a
   * non-trivial position
   */
  offset = 2745;

  run_two_timer_double_wheel (&tm->two_timer_double_wheel, offset);

  fformat (stdout, "initial wheel time %d, fast index %d\n",
	   tm->two_timer_double_wheel.current_tick,
	   tm->two_timer_double_wheel.current_index[TW_TIMER_RING_FAST]);

  for (i = 0; i < tm->ntimers; i++)
    {
      pool_get (tm->test_elts, e);
      clib_memset (e, 0, sizeof (*e));

      e->expected_to_expire = i + tm->two_timer_double_wheel.current_tick + 1;
      e->stop_timer_handle = tw_timer_start_2t_2w_512sl
	(&tm->two_timer_double_wheel, e - tm->test_elts, 1 /* timer id */ ,
	 i + 1);
    }
  run_two_timer_double_wheel (&tm->two_timer_double_wheel, tm->ntimers + 3);

  if (pool_elts (tm->test_elts))
    fformat (stdout, "Note: %d elements remain in pool\n",
	     pool_elts (tm->test_elts));

  /* *INDENT-OFF* */
  pool_foreach (e, tm->test_elts)
   {
    fformat(stdout, "[%d] expected to expire %d\n",
                     e - tm->test_elts,
                     e->expected_to_expire);
  }
  /* *INDENT-ON* */

  fformat (stdout,
	   "final wheel time %d, fast index %d\n",
	   tm->two_timer_double_wheel.current_tick,
	   tm->two_timer_double_wheel.current_index[TW_TIMER_RING_FAST]);

  pool_free (tm->test_elts);
  tw_timer_wheel_free_2t_2w_512sl (&tm->two_timer_double_wheel);
  return 0;
}

static clib_error_t *
test3_triple_double (tw_timer_test_main_t * tm)
{
  tw_timer_test_elt_t *e;
  u32 initial_wheel_offset = 0;
  u32 expiration_time;
  u32 max_expiration_time = 0;
  u32 adds = 0, deletes = 0;
  f64 before, after;

  clib_time_init (&tm->clib_time);

  tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel,
				   expired_timer_triple_callback,
				   1.0 /* timer interval */ , ~0);

  initial_wheel_offset = 0;
  run_triple_wheel (&tm->triple_wheel, initial_wheel_offset);

  fformat (stdout,
	   "initial wheel time %d, fi %d si %d gi %d\n",
	   tm->triple_wheel.current_tick,
	   tm->triple_wheel.current_index[TW_TIMER_RING_FAST],
	   tm->triple_wheel.current_index[TW_TIMER_RING_SLOW],
	   tm->triple_wheel.current_index[TW_TIMER_RING_GLACIER]);

  initial_wheel_offset = tm->triple_wheel.current_tick;

  fformat (stdout, "Create a timer which expires at wheel-time (1, 0, 0)\n");

  before = clib_time_now (&tm->clib_time);

  /* Prime the pump */
  pool_get (tm->test_elts, e);
  clib_memset (e, 0, sizeof (*e));

  /* 1 glacier ring tick from now */
  expiration_time = TW_SLOTS_PER_RING * TW_SLOTS_PER_RING;
  e->expected_to_expire = expiration_time + initial_wheel_offset;
  max_expiration_time = expiration_time;

  e->stop_timer_handle =
    tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts,
				3 /* timer id */ ,
				expiration_time);

  run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1);

  after = clib_time_now (&tm->clib_time);

  fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
	   tm->triple_wheel.current_tick);
  fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
	   (after - before),
	   ((f64) adds + (f64) deletes +
	    (f64) tm->triple_wheel.current_tick) / (after - before));

  if (pool_elts (tm->test_elts))
    fformat (stdout, "Note: %d elements remain in pool\n",
	     pool_elts (tm->test_elts));

  /* *INDENT-OFF* */
  pool_foreach (e, tm->test_elts)
   {
    fformat (stdout, "[%d] expected to expire %d\n",
             e - tm->test_elts,
             e->expected_to_expire);
  }
  /* *INDENT-ON* */

  pool_free (tm->test_elts);
  tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel);
  return 0;
}

static clib_error_t *
test4_double_double (tw_timer_test_main_t * tm)
{
  u32 i;
  tw_timer_test_elt_t *e;
  u32 initial_wheel_offset;
  u32 expiration_time;
  u32 max_expiration_time = 0;
  u32 *deleted_indices = 0;
  u32 adds = 0, deletes = 0;
  f64 before, after;

  clib_time_init (&tm->clib_time);

  tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
				    expired_timer_double_callback,
				    1.0 /* timer interval */ , ~0);
  /* Prime offset */
  initial_wheel_offset = 0;

  run_double_wheel (&tm->double_wheel, initial_wheel_offset);

  fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
	   tm->double_wheel.current_tick,
	   tm->double_wheel.current_index[TW_TIMER_RING_FAST],
	   tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);

  initial_wheel_offset = tm->double_wheel.current_tick;

  fformat (stdout, "test timer which expires at 512 ticks\n");

  before = clib_time_now (&tm->clib_time);

  /* Prime the pump */
  for (i = 0; i < tm->ntimers; i++)
    {
      pool_get (tm->test_elts, e);
      clib_memset (e, 0, sizeof (*e));

      expiration_time = 512;

      if (expiration_time > max_expiration_time)
	max_expiration_time = expiration_time;

      e->expected_to_expire = expiration_time + initial_wheel_offset;
      e->stop_timer_handle =
	tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
				     14 /* timer id */ ,
				     expiration_time);
    }

  adds = 1;

  vec_free (deleted_indices);

  run_double_wheel (&tm->double_wheel, max_expiration_time + 1);

  after = clib_time_now (&tm->clib_time);

  fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
	   tm->double_wheel.current_tick);
  fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
	   (after - before),
	   ((f64) adds + (f64) deletes +
	    (f64) tm->double_wheel.current_tick) / (after - before));

  if (pool_elts (tm->test_elts))
    fformat (stdout, "Note: %d elements remain in pool\n",
	     pool_elts (tm->test_elts));

  /* *INDENT-OFF* */
  pool_foreach (e, tm->test_elts)
   {
    fformat (stdout, "[%d] expected to expire %d\n",
             e - tm->test_elts,
             e->expected_to_expire);
  }
  /* *INDENT-ON* */

  pool_free (tm->test_elts);
  tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
  return 0;
}

static clib_error_t *
test5_double (tw_timer_test_main_t * tm)
{
  u32 i;
  tw_timer_test_elt_t *e;
  u32 initial_wheel_offset;
  u32 expiration_time;
  u32 max_expiration_time = 0;
  u32 adds = 0, deletes = 0;
  f64 before, after;

  clib_time_init (&tm->clib_time);

  tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
				    expired_timer_double_callback,
				    1.0 /* timer interval */ , ~0);

  /* Prime offset */
  initial_wheel_offset = 7567;

  run_double_wheel (&tm->double_wheel, initial_wheel_offset);

  fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
	   tm->double_wheel.current_tick,
	   tm->double_wheel.current_index[TW_TIMER_RING_FAST],
	   tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);

  initial_wheel_offset = tm->double_wheel.current_tick;

  fformat (stdout,
	   "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
	   tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);

  before = clib_time_now (&tm->clib_time);

  /* Prime the pump */
  for (i = 0; i < tm->ntimers; i++)
    {
      pool_get (tm->test_elts, e);
      clib_memset (e, 0, sizeof (*e));

      expiration_time = i + 1;

      if (expiration_time > max_expiration_time)
	max_expiration_time = expiration_time;

      e->expected_to_expire = expiration_time + initial_wheel_offset;
      e->stop_timer_handle =
	tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
				     14 /* timer id */ ,
				     expiration_time);
    }

  adds += i;

  run_double_wheel (&tm->double_wheel, max_expiration_time + 1);

  after = clib_time_now (&tm->clib_time);

  fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
	   tm->double_wheel.current_tick);
  fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
	   (after - before),
	   ((f64) adds + (f64) deletes +
	    (f64) tm->double_wheel.current_tick) / (after - before));

  if (pool_elts (tm->test_elts))
    fformat (stdout, "Note: %d elements remain in pool\n",
	     pool_elts (tm->test_elts));

  /* *INDENT-OFF* */
  pool_foreach (e, tm->test_elts)
   {
    fformat (stdout, "[%d] expected to expire %d\n",
             e - tm->test_elts,
             e->expected_to_expire);
  }
  /* *INDENT-ON* */

  pool_free (tm->test_elts);
  tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
  return 0;
}

static clib_error_t *
timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input)
{

  int is_test1 = 0, is_updates = 0;
  int num_wheels = 1;
  int is_test2 = 0;
  int is_test3 = 0;
  int is_test4 = 0;
  int is_test5 = 0;
  int overflow = 0;

  clib_memset (tm, 0, sizeof (*tm));
  /* Default values */
  tm->ntimers = 100000;
  tm->seed = 0xDEADDABEB00BFACE;
  tm->niter = 1000;
  tm->ticks_per_iter = 727;

  while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
    {
      if (unformat (input, "seed %lld", &tm->seed))
	;
      else if (unformat (input, "test1"))
	is_test1 = 1;
      else if (unformat (input, "test2"))
	is_test2 = 1;
      else if (unformat (input, "overflow"))
	overflow = 1;
      else if (unformat (input, "lebron"))
	is_test3 = 1;
      else if (unformat (input, "wilt"))
	is_test4 = 1;
      else if (unformat (input, "linear"))
	is_test5 = 1;
      else if (unformat (input, "updates"))
	is_updates = 1;
      else if (unformat (input, "wheels %d", &num_wheels))
	;
      else if (unformat (input, "ntimers %d", &tm->ntimers))
	;
      else if (unformat (input, "niter %d", &tm->niter))
	;
      else if (unformat (input, "ticks_per_iter %d", &tm->ticks_per_iter))
	;
      else
	break;
    }

  if (is_test1 + is_test2 + is_test3 + is_test4 + is_test5 == 0)
    return clib_error_return (0, "No test specified [test1..n]");

  if (num_wheels < 1 || num_wheels > 3)
    return clib_error_return (0, "unsupported... 1 or 2 wheels only");

  if (is_test1)
    {
      if (num_wheels == 1)
	return test1_single (tm);
      else
	{
	  (void) test1_double (tm);
	  return test1_two_timer_double (tm);
	}
    }
  if (is_test2)
    {
      if (num_wheels == 1)
	return test2_single (tm);
      else if (num_wheels == 2)
	if (is_updates)
	  return test2_double_updates (tm);
	else
	  return test2_double (tm);
      else if (num_wheels == 3)
	{
	  if (overflow == 0)
	    return test2_triple (tm);
	  else
	    return test2_triple_ov (tm);
	}
    }
  if (is_test3)
    return test3_triple_double (tm);

  if (is_test4)
    return test4_double_double (tm);

  if (is_test5)
    return test5_double (tm);

  /* NOTREACHED */
  return 0;
}

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

  clib_mem_init (0, 3ULL << 30);

  unformat_init_command_line (&i, argv);
  error = timer_test_command_fn (tm, &i);
  unformat_free (&i);

  if (error)
    {
      clib_error_report (error);
      return 1;
    }
  return 0;
}
#endif /* CLIB_UNIX */

/* For debugging... */
int
pifi (void *p, u32 index)
{
  return pool_is_free_index (p, index);
}

u32
vl (void *p)
{
  return vec_len (p);
}

uword
pe (void *v)
{
  return (pool_elts (v));
}

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