From eae78d4356b8834b78a91c52d869a7949f8f3e90 Mon Sep 17 00:00:00 2001 From: Hanoh Haim Date: Wed, 7 Dec 2016 15:24:38 +0200 Subject: improve Stateful scheduler Signed-off-by: Hanoh Haim --- VERSION | 3 +- linux/ws_main.py | 4 +- linux_dpdk/ws_main.py | 4 +- scripts/cap2/cur_flow.yaml | 26 ++ scripts/cap2/udp_10_pkts.pcap | Bin 0 -> 804 bytes scripts/cfg/kiwi02_more_flows.yaml | 16 + scripts/exp/dns-0.erf | Bin 1872 -> 1872 bytes scripts/exp/dns_e-0.erf | Bin 1872 -> 1872 bytes scripts/exp/dns_flip-0.erf | Bin 1872 -> 1872 bytes scripts/exp/dns_ipv6-0.erf | Bin 2304 -> 2304 bytes scripts/exp/dns_ipv6_rxcheck.erf | Bin 304 -> 304 bytes scripts/exp/dns_one_server-0.erf | Bin 3952 -> 3952 bytes scripts/exp/dns_p-0.erf | Bin 1872 -> 1872 bytes scripts/exp/dns_rxcheck.erf | Bin 256 -> 256 bytes scripts/exp/dyn_pyld1-0.erf | Bin 1872 -> 1872 bytes scripts/exp/http_plugin-0.erf | Bin 35328 -> 35328 bytes scripts/exp/http_plugin_v6-0.erf | Bin 36008 -> 36008 bytes scripts/exp/imix-0-ex.erf | Bin 62784 -> 68104 bytes scripts/exp/imix-0.erf | Bin 62784 -> 68104 bytes scripts/exp/imix_v6-0-ex.erf | Bin 65376 -> 70928 bytes scripts/exp/imix_v6-0.erf | Bin 65376 -> 70928 bytes scripts/exp/ipv4_vlan-0-ex.erf | Bin 8800 -> 10648 bytes scripts/exp/ipv4_vlan-0.erf | Bin 8800 -> 10648 bytes scripts/exp/ipv6-0-ex.erf | Bin 11200 -> 13552 bytes scripts/exp/ipv6-0.erf | Bin 11200 -> 13552 bytes scripts/exp/ipv6_vlan-0-ex.erf | Bin 11200 -> 13552 bytes scripts/exp/ipv6_vlan-0.erf | Bin 11200 -> 13552 bytes scripts/exp/limit_multi_pkt-0-ex.erf | Bin 30368 -> 30944 bytes scripts/exp/limit_multi_pkt-0.erf | Bin 30368 -> 30944 bytes scripts/exp/limit_single_pkt-0-ex.erf | Bin 5192 -> 6688 bytes scripts/exp/limit_single_pkt-0.erf | Bin 5192 -> 6688 bytes scripts/exp/pcap_mode1-0-ex.erf | Bin 91456 -> 91456 bytes scripts/exp/pcap_mode1-0.erf | Bin 91456 -> 91456 bytes scripts/exp/pcap_mode2-0-ex.erf | Bin 914560 -> 823104 bytes scripts/exp/pcap_mode2-0.erf | Bin 914560 -> 0 bytes scripts/exp/rtsp_short1-0.erf | Bin 20024 -> 20024 bytes scripts/exp/rtsp_short1_ipv6_rxcheck.erf | Bin 21560 -> 21560 bytes scripts/exp/rtsp_short1_rxcheck.erf | Bin 20912 -> 20912 bytes scripts/exp/rtsp_short1_v6-0.erf | Bin 20672 -> 20672 bytes scripts/exp/rtsp_short2-0.erf | Bin 20024 -> 20024 bytes scripts/exp/rtsp_short2_v6-0.erf | Bin 20672 -> 20672 bytes scripts/exp/rtsp_short3-0.erf | Bin 20032 -> 20032 bytes scripts/exp/rtsp_short3_v6-0.erf | Bin 20696 -> 20696 bytes scripts/exp/sfr2-0-ex.erf | Bin 1731712 -> 1731712 bytes scripts/exp/sfr2-0.erf | Bin 1731712 -> 1731712 bytes scripts/exp/sfr3-0.erf | Bin 10351656 -> 10351656 bytes scripts/exp/sfr_4-0.erf | Bin 42968 -> 42968 bytes scripts/exp/sip_short1-0-ex.erf | Bin 3576 -> 3576 bytes scripts/exp/sip_short1-0.erf | Bin 3576 -> 3576 bytes scripts/exp/sip_short1_v6-0.erf | Bin 3880 -> 3880 bytes scripts/exp/sip_short2-0-ex.erf | Bin 3576 -> 3576 bytes scripts/exp/sip_short2-0.erf | Bin 3576 -> 3576 bytes scripts/exp/sip_short2_v6-0.erf | Bin 3880 -> 3880 bytes scripts/exp/sip_short3-0-ex.erf | Bin 3584 -> 3584 bytes scripts/exp/sip_short3-0.erf | Bin 3584 -> 3584 bytes scripts/exp/sip_short3_v6-0.erf | Bin 3888 -> 3888 bytes scripts/run-gtest-timer-clean | 3 + src/bp_gtest.cpp | 101 +++--- src/bp_sim.cpp | 381 +++++++++++++++----- src/bp_sim.h | 179 ++++------ src/common/basic_utils.h | 51 +++ src/gtest/bp_timer_gtest.cpp | 595 +++++++++++++++++++++++++++++++ src/h_timer.cpp | 231 ++++++++++++ src/h_timer.h | 288 +++++++++++++++ src/h_timer_w.h | 533 +++++++++++++++++++++++++++ src/nat_check.h | 2 + src/pal/linux/rte_prefetch.h | 30 ++ src/stateless/dp/trex_stream_node.h | 10 + src/stw_timer.cpp | 204 +++++++++++ src/stw_timer.h | 381 ++++++++++++++++++++ src/utl_ipg_bucket.h | 68 ++++ 71 files changed, 2875 insertions(+), 235 deletions(-) create mode 100644 scripts/cap2/cur_flow.yaml create mode 100644 scripts/cap2/udp_10_pkts.pcap create mode 100644 scripts/cfg/kiwi02_more_flows.yaml delete mode 100644 scripts/exp/pcap_mode2-0.erf create mode 100644 scripts/run-gtest-timer-clean create mode 100644 src/gtest/bp_timer_gtest.cpp create mode 100644 src/h_timer.cpp create mode 100644 src/h_timer.h create mode 100644 src/h_timer_w.h create mode 100644 src/pal/linux/rte_prefetch.h create mode 100644 src/stw_timer.cpp create mode 100644 src/stw_timer.h create mode 100644 src/utl_ipg_bucket.h diff --git a/VERSION b/VERSION index fac09c88..d824b299 100755 --- a/VERSION +++ b/VERSION @@ -1,5 +1,4 @@ -v2.12 - +v2.12-tw diff --git a/linux/ws_main.py b/linux/ws_main.py index 31d6b979..d885c597 100755 --- a/linux/ws_main.py +++ b/linux/ws_main.py @@ -96,6 +96,7 @@ bp_sim_main = SrcGroup(dir='src', bp_sim_gtest = SrcGroup(dir='src', src_list=[ 'bp_gtest.cpp', + 'gtest/bp_timer_gtest.cpp', 'gtest/tuple_gen_test.cpp', 'gtest/client_cfg_test.cpp', 'gtest/nat_test.cpp', @@ -132,7 +133,8 @@ main_src = SrcGroup(dir='src', 'pal/linux/mbuf.cpp', 'pal/common/common_mbuf.cpp', 'sim/trex_sim_stateless.cpp', - 'sim/trex_sim_stateful.cpp' + 'sim/trex_sim_stateful.cpp', + 'h_timer.cpp' ]); cmn_src = SrcGroup(dir='src/common', diff --git a/linux_dpdk/ws_main.py b/linux_dpdk/ws_main.py index 29143ce1..2327f28d 100755 --- a/linux_dpdk/ws_main.py +++ b/linux_dpdk/ws_main.py @@ -226,7 +226,9 @@ main_src = SrcGroup(dir='src', 'publisher/trex_publisher.cpp', 'pal/linux_dpdk/pal_utl.cpp', 'pal/linux_dpdk/mbuf.cpp', - 'pal/common/common_mbuf.cpp' + 'pal/common/common_mbuf.cpp', + 'h_timer.cpp' + ]); cmn_src = SrcGroup(dir='src/common', diff --git a/scripts/cap2/cur_flow.yaml b/scripts/cap2/cur_flow.yaml new file mode 100644 index 00000000..8f53c0be --- /dev/null +++ b/scripts/cap2/cur_flow.yaml @@ -0,0 +1,26 @@ +- duration : 0.1 + generator : + distribution : "seq" + clients_start : "16.0.0.1" + clients_end : "16.0.0.255" + servers_start : "48.0.0.1" + servers_end : "48.0.255.255" + clients_per_gb : 201 + min_clients : 101 + dual_port_mask : "1.0.0.0" + tcp_aging : 0 + udp_aging : 0 + mac : [0x0,0x0,0x0,0x1,0x0,0x00] + #cap_ipg : true + cap_info : + - name: cap2/udp_10_pkts.pcap + cps : 1 + ipg : 10000000 + rtt : 10000000 + w : 1 + - name: cap2/udp_10_pkts.pcap + cps : 99 + ipg : 200 + rtt : 200 + w : 1 + diff --git a/scripts/cap2/udp_10_pkts.pcap b/scripts/cap2/udp_10_pkts.pcap new file mode 100644 index 00000000..3417a1db Binary files /dev/null and b/scripts/cap2/udp_10_pkts.pcap differ diff --git a/scripts/cfg/kiwi02_more_flows.yaml b/scripts/cfg/kiwi02_more_flows.yaml new file mode 100644 index 00000000..a156d4f4 --- /dev/null +++ b/scripts/cfg/kiwi02_more_flows.yaml @@ -0,0 +1,16 @@ +- port_limit : 4 + version : 2 + interfaces : ["03:00.0","03:00.1","82:00.0","82:00.1"] # list of the interfaces to bind run ./dpdk_nic_bind.py --status + c : 4 + platform : + master_thread_id : 0 + latency_thread_id : 5 + dual_if : + - socket : 0 + threads : [1,2,3,4] + - socket : 1 + threads : [8,9,10,11] + + memory : + dp_flows : 4048576 + diff --git a/scripts/exp/dns-0.erf b/scripts/exp/dns-0.erf index 08a02075..2c3d7982 100644 Binary files a/scripts/exp/dns-0.erf and b/scripts/exp/dns-0.erf differ diff --git a/scripts/exp/dns_e-0.erf b/scripts/exp/dns_e-0.erf index 6ac25dfb..6fbb2db4 100644 Binary files a/scripts/exp/dns_e-0.erf and b/scripts/exp/dns_e-0.erf differ diff --git a/scripts/exp/dns_flip-0.erf b/scripts/exp/dns_flip-0.erf index b9b61e5d..8510c1b4 100644 Binary files a/scripts/exp/dns_flip-0.erf and b/scripts/exp/dns_flip-0.erf differ diff --git a/scripts/exp/dns_ipv6-0.erf b/scripts/exp/dns_ipv6-0.erf index 4284cc98..c455c9d9 100644 Binary files a/scripts/exp/dns_ipv6-0.erf and b/scripts/exp/dns_ipv6-0.erf differ diff --git a/scripts/exp/dns_ipv6_rxcheck.erf b/scripts/exp/dns_ipv6_rxcheck.erf index 3984c0ef..ba6effc9 100644 Binary files a/scripts/exp/dns_ipv6_rxcheck.erf and b/scripts/exp/dns_ipv6_rxcheck.erf differ diff --git a/scripts/exp/dns_one_server-0.erf b/scripts/exp/dns_one_server-0.erf index f1b4d7fe..1a244a61 100644 Binary files a/scripts/exp/dns_one_server-0.erf and b/scripts/exp/dns_one_server-0.erf differ diff --git a/scripts/exp/dns_p-0.erf b/scripts/exp/dns_p-0.erf index 3849dbc3..895ec298 100644 Binary files a/scripts/exp/dns_p-0.erf and b/scripts/exp/dns_p-0.erf differ diff --git a/scripts/exp/dns_rxcheck.erf b/scripts/exp/dns_rxcheck.erf index a6135f34..d0d151a1 100644 Binary files a/scripts/exp/dns_rxcheck.erf and b/scripts/exp/dns_rxcheck.erf differ diff --git a/scripts/exp/dyn_pyld1-0.erf b/scripts/exp/dyn_pyld1-0.erf index ef054447..1231ee12 100644 Binary files a/scripts/exp/dyn_pyld1-0.erf and b/scripts/exp/dyn_pyld1-0.erf differ diff --git a/scripts/exp/http_plugin-0.erf b/scripts/exp/http_plugin-0.erf index 6c0accd7..ff977fb9 100644 Binary files a/scripts/exp/http_plugin-0.erf and b/scripts/exp/http_plugin-0.erf differ diff --git a/scripts/exp/http_plugin_v6-0.erf b/scripts/exp/http_plugin_v6-0.erf index 2b5e7163..8e6cd298 100644 Binary files a/scripts/exp/http_plugin_v6-0.erf and b/scripts/exp/http_plugin_v6-0.erf differ diff --git a/scripts/exp/imix-0-ex.erf b/scripts/exp/imix-0-ex.erf index 4e9a685c..4f6d3d94 100755 Binary files a/scripts/exp/imix-0-ex.erf and b/scripts/exp/imix-0-ex.erf differ diff --git a/scripts/exp/imix-0.erf b/scripts/exp/imix-0.erf index 4e9a685c..4f6d3d94 100644 Binary files a/scripts/exp/imix-0.erf and b/scripts/exp/imix-0.erf differ diff --git a/scripts/exp/imix_v6-0-ex.erf b/scripts/exp/imix_v6-0-ex.erf index 1b6b6bb7..2dd16e11 100755 Binary files a/scripts/exp/imix_v6-0-ex.erf and b/scripts/exp/imix_v6-0-ex.erf differ diff --git a/scripts/exp/imix_v6-0.erf b/scripts/exp/imix_v6-0.erf index 1b6b6bb7..2dd16e11 100644 Binary files a/scripts/exp/imix_v6-0.erf and b/scripts/exp/imix_v6-0.erf differ diff --git a/scripts/exp/ipv4_vlan-0-ex.erf b/scripts/exp/ipv4_vlan-0-ex.erf index 1ec8a1fa..6f75b99b 100755 Binary files a/scripts/exp/ipv4_vlan-0-ex.erf and b/scripts/exp/ipv4_vlan-0-ex.erf differ diff --git a/scripts/exp/ipv4_vlan-0.erf b/scripts/exp/ipv4_vlan-0.erf index 1ec8a1fa..6f75b99b 100644 Binary files a/scripts/exp/ipv4_vlan-0.erf and b/scripts/exp/ipv4_vlan-0.erf differ diff --git a/scripts/exp/ipv6-0-ex.erf b/scripts/exp/ipv6-0-ex.erf index 1e102856..8293b109 100755 Binary files a/scripts/exp/ipv6-0-ex.erf and b/scripts/exp/ipv6-0-ex.erf differ diff --git a/scripts/exp/ipv6-0.erf b/scripts/exp/ipv6-0.erf index 1e102856..8293b109 100644 Binary files a/scripts/exp/ipv6-0.erf and b/scripts/exp/ipv6-0.erf differ diff --git a/scripts/exp/ipv6_vlan-0-ex.erf b/scripts/exp/ipv6_vlan-0-ex.erf index f7c82833..5ed0b866 100755 Binary files a/scripts/exp/ipv6_vlan-0-ex.erf and b/scripts/exp/ipv6_vlan-0-ex.erf differ diff --git a/scripts/exp/ipv6_vlan-0.erf b/scripts/exp/ipv6_vlan-0.erf index f7c82833..5ed0b866 100644 Binary files a/scripts/exp/ipv6_vlan-0.erf and b/scripts/exp/ipv6_vlan-0.erf differ diff --git a/scripts/exp/limit_multi_pkt-0-ex.erf b/scripts/exp/limit_multi_pkt-0-ex.erf index 5bf3a5b3..b6487e6f 100755 Binary files a/scripts/exp/limit_multi_pkt-0-ex.erf and b/scripts/exp/limit_multi_pkt-0-ex.erf differ diff --git a/scripts/exp/limit_multi_pkt-0.erf b/scripts/exp/limit_multi_pkt-0.erf index 5bf3a5b3..b6487e6f 100644 Binary files a/scripts/exp/limit_multi_pkt-0.erf and b/scripts/exp/limit_multi_pkt-0.erf differ diff --git a/scripts/exp/limit_single_pkt-0-ex.erf b/scripts/exp/limit_single_pkt-0-ex.erf index 5438feee..e2725b9e 100755 Binary files a/scripts/exp/limit_single_pkt-0-ex.erf and b/scripts/exp/limit_single_pkt-0-ex.erf differ diff --git a/scripts/exp/limit_single_pkt-0.erf b/scripts/exp/limit_single_pkt-0.erf index 5438feee..e2725b9e 100644 Binary files a/scripts/exp/limit_single_pkt-0.erf and b/scripts/exp/limit_single_pkt-0.erf differ diff --git a/scripts/exp/pcap_mode1-0-ex.erf b/scripts/exp/pcap_mode1-0-ex.erf index e8d0f202..dd98a699 100755 Binary files a/scripts/exp/pcap_mode1-0-ex.erf and b/scripts/exp/pcap_mode1-0-ex.erf differ diff --git a/scripts/exp/pcap_mode1-0.erf b/scripts/exp/pcap_mode1-0.erf index e8d0f202..72e14bef 100644 Binary files a/scripts/exp/pcap_mode1-0.erf and b/scripts/exp/pcap_mode1-0.erf differ diff --git a/scripts/exp/pcap_mode2-0-ex.erf b/scripts/exp/pcap_mode2-0-ex.erf index d8432f86..dde7d7e2 100755 Binary files a/scripts/exp/pcap_mode2-0-ex.erf and b/scripts/exp/pcap_mode2-0-ex.erf differ diff --git a/scripts/exp/pcap_mode2-0.erf b/scripts/exp/pcap_mode2-0.erf deleted file mode 100644 index d8432f86..00000000 Binary files a/scripts/exp/pcap_mode2-0.erf and /dev/null differ diff --git a/scripts/exp/rtsp_short1-0.erf b/scripts/exp/rtsp_short1-0.erf index 2f65a39d..d75f8f98 100644 Binary files a/scripts/exp/rtsp_short1-0.erf and b/scripts/exp/rtsp_short1-0.erf differ diff --git a/scripts/exp/rtsp_short1_ipv6_rxcheck.erf b/scripts/exp/rtsp_short1_ipv6_rxcheck.erf index a35e9f47..046e0a1e 100644 Binary files a/scripts/exp/rtsp_short1_ipv6_rxcheck.erf and b/scripts/exp/rtsp_short1_ipv6_rxcheck.erf differ diff --git a/scripts/exp/rtsp_short1_rxcheck.erf b/scripts/exp/rtsp_short1_rxcheck.erf index cfc3726a..dc195ac0 100644 Binary files a/scripts/exp/rtsp_short1_rxcheck.erf and b/scripts/exp/rtsp_short1_rxcheck.erf differ diff --git a/scripts/exp/rtsp_short1_v6-0.erf b/scripts/exp/rtsp_short1_v6-0.erf index cc2e1fc6..ba220161 100644 Binary files a/scripts/exp/rtsp_short1_v6-0.erf and b/scripts/exp/rtsp_short1_v6-0.erf differ diff --git a/scripts/exp/rtsp_short2-0.erf b/scripts/exp/rtsp_short2-0.erf index 2f65a39d..d75f8f98 100644 Binary files a/scripts/exp/rtsp_short2-0.erf and b/scripts/exp/rtsp_short2-0.erf differ diff --git a/scripts/exp/rtsp_short2_v6-0.erf b/scripts/exp/rtsp_short2_v6-0.erf index cc2e1fc6..ba220161 100644 Binary files a/scripts/exp/rtsp_short2_v6-0.erf and b/scripts/exp/rtsp_short2_v6-0.erf differ diff --git a/scripts/exp/rtsp_short3-0.erf b/scripts/exp/rtsp_short3-0.erf index be1027d5..57668046 100644 Binary files a/scripts/exp/rtsp_short3-0.erf and b/scripts/exp/rtsp_short3-0.erf differ diff --git a/scripts/exp/rtsp_short3_v6-0.erf b/scripts/exp/rtsp_short3_v6-0.erf index 08ae1be7..49fa4c20 100644 Binary files a/scripts/exp/rtsp_short3_v6-0.erf and b/scripts/exp/rtsp_short3_v6-0.erf differ diff --git a/scripts/exp/sfr2-0-ex.erf b/scripts/exp/sfr2-0-ex.erf index b0b93a26..2542a8b3 100755 Binary files a/scripts/exp/sfr2-0-ex.erf and b/scripts/exp/sfr2-0-ex.erf differ diff --git a/scripts/exp/sfr2-0.erf b/scripts/exp/sfr2-0.erf index b0b93a26..1761b48f 100644 Binary files a/scripts/exp/sfr2-0.erf and b/scripts/exp/sfr2-0.erf differ diff --git a/scripts/exp/sfr3-0.erf b/scripts/exp/sfr3-0.erf index ec8e3f90..2ba0a08b 100644 Binary files a/scripts/exp/sfr3-0.erf and b/scripts/exp/sfr3-0.erf differ diff --git a/scripts/exp/sfr_4-0.erf b/scripts/exp/sfr_4-0.erf index 89ca013b..69609004 100644 Binary files a/scripts/exp/sfr_4-0.erf and b/scripts/exp/sfr_4-0.erf differ diff --git a/scripts/exp/sip_short1-0-ex.erf b/scripts/exp/sip_short1-0-ex.erf index e642442c..4a03f5b3 100755 Binary files a/scripts/exp/sip_short1-0-ex.erf and b/scripts/exp/sip_short1-0-ex.erf differ diff --git a/scripts/exp/sip_short1-0.erf b/scripts/exp/sip_short1-0.erf index e642442c..ee1ddd13 100644 Binary files a/scripts/exp/sip_short1-0.erf and b/scripts/exp/sip_short1-0.erf differ diff --git a/scripts/exp/sip_short1_v6-0.erf b/scripts/exp/sip_short1_v6-0.erf index 000d3934..573b5b8d 100644 Binary files a/scripts/exp/sip_short1_v6-0.erf and b/scripts/exp/sip_short1_v6-0.erf differ diff --git a/scripts/exp/sip_short2-0-ex.erf b/scripts/exp/sip_short2-0-ex.erf index e642442c..4a03f5b3 100755 Binary files a/scripts/exp/sip_short2-0-ex.erf and b/scripts/exp/sip_short2-0-ex.erf differ diff --git a/scripts/exp/sip_short2-0.erf b/scripts/exp/sip_short2-0.erf index e642442c..ee1ddd13 100644 Binary files a/scripts/exp/sip_short2-0.erf and b/scripts/exp/sip_short2-0.erf differ diff --git a/scripts/exp/sip_short2_v6-0.erf b/scripts/exp/sip_short2_v6-0.erf index 000d3934..573b5b8d 100644 Binary files a/scripts/exp/sip_short2_v6-0.erf and b/scripts/exp/sip_short2_v6-0.erf differ diff --git a/scripts/exp/sip_short3-0-ex.erf b/scripts/exp/sip_short3-0-ex.erf index 1eb3881b..8d7a8778 100755 Binary files a/scripts/exp/sip_short3-0-ex.erf and b/scripts/exp/sip_short3-0-ex.erf differ diff --git a/scripts/exp/sip_short3-0.erf b/scripts/exp/sip_short3-0.erf index 1eb3881b..5f21788d 100644 Binary files a/scripts/exp/sip_short3-0.erf and b/scripts/exp/sip_short3-0.erf differ diff --git a/scripts/exp/sip_short3_v6-0.erf b/scripts/exp/sip_short3_v6-0.erf index aa9d6562..35b95903 100644 Binary files a/scripts/exp/sip_short3_v6-0.erf and b/scripts/exp/sip_short3_v6-0.erf differ diff --git a/scripts/run-gtest-timer-clean b/scripts/run-gtest-timer-clean new file mode 100644 index 00000000..3f098bc1 --- /dev/null +++ b/scripts/run-gtest-timer-clean @@ -0,0 +1,3 @@ +#! /bin/bash +valgrind --leak-check=full --error-exitcode=1 --show-reachable=yes ./bp-sim-64 --ut --gtest_filter="gt_r_timer.*" + diff --git a/src/bp_gtest.cpp b/src/bp_gtest.cpp index a3e52bb9..8de8fa0e 100755 --- a/src/bp_gtest.cpp +++ b/src/bp_gtest.cpp @@ -33,6 +33,7 @@ limitations under the License. #include "platform_cfg.h" #include "stateful_rx_core.h" #include "nat_check_flow_table.h" +#include "utl_ipg_bucket.h" int test_policer(){ CPolicer policer; @@ -85,25 +86,6 @@ int test_priorty_queue(void){ } -#if 0 -#ifdef WIN32 - -int test_rate(){ - int i; - CBwMeasure m; - uint64_t cnt=0; - for (i=0; i<10; i++) { - Sleep(100); - cnt+=10000; - printf (" %f \n",m.add(cnt)); - } - return (0); -} -#endif -#endif - - - void histogram_test(){ CTimeHistogram t; @@ -281,7 +263,7 @@ TEST_F(basic, limit_single_pkt) { EXPECT_EQ_UINT32(1, res?1:0)<< "pass"; } -TEST_F(basic, limit_multi_pkt) { +/*TEST_F(basic, limit_multi_pkt) { CTestBasic t1; CParserOption * po =&CGlobalInfo::m_options; @@ -291,7 +273,7 @@ TEST_F(basic, limit_multi_pkt) { po->out_file ="exp/limit_multi_pkt"; bool res=t1.init(); EXPECT_EQ_UINT32(1, res?1:0)<< "pass"; -} +} */ TEST_F(basic, imix) { @@ -2507,7 +2489,8 @@ public: TEST_F(file_flow_info, f1) { m_flow_info.load_cap_file("cap2/delay_10_rtp_250k_short.pcap",1,7) ; - m_flow_info.update_info(); + CFlowYamlInfo info; + m_flow_info.update_info(&info); //m_flow_info.Dump(stdout); int i; @@ -2541,8 +2524,8 @@ TEST_F(file_flow_info, f1) { TEST_F(file_flow_info, f2) { m_flow_info.load_cap_file("cap2/citrix.pcap",1,0) ; - m_flow_info.update_info(); - + CFlowYamlInfo info; + m_flow_info.update_info(&info); int i; for (i=0; im_pkt_indication.m_desc.IsOneDirectionalFlow(),0); } @@ -2569,7 +2553,8 @@ TEST_F(file_flow_info, http_two_dir) { TEST_F(file_flow_info, one_dir) { m_flow_info.load_cap_file("avl/delay_rtp_160k_1_1_0.pcap",1,0) ; - m_flow_info.update_info(); + CFlowYamlInfo info; + m_flow_info.update_info(&info); CFlowPktInfo * lp=m_flow_info.GetPacket((uint32_t)0); EXPECT_EQ(lp->m_pkt_indication.m_desc.IsOneDirectionalFlow(),1); } @@ -2592,7 +2577,8 @@ TEST_F(file_flow_info, nat_option_check) { TEST_F(file_flow_info, http_add_ipv4_option) { m_flow_info.load_cap_file("avl/delay_10_http_browsing_0.pcap",1,0) ; - m_flow_info.update_info(); + CFlowYamlInfo info; + m_flow_info.update_info(&info); CFlowPktInfo * lp=m_flow_info.GetPacket((uint32_t)0); printf(" before the change \n"); //lp->Dump(stdout); @@ -2616,7 +2602,9 @@ TEST_F(file_flow_info, http_add_ipv6_option) { po->preview.set_ipv6_mode_enable(true); m_flow_info.load_cap_file("avl/delay_10_http_browsing_0.pcap",1,0) ; - m_flow_info.update_info(); + CFlowYamlInfo info; + m_flow_info.update_info(&info); + CFlowPktInfo * lp=m_flow_info.GetPacket((uint32_t)0); //lp->Dump(stdout); //lp->m_packet->Dump(stdout,1); @@ -2915,23 +2903,52 @@ public: }; -#if 0 -TEST_F(gt_conf, t1) { - CPlatformYamlInfo info; - info.load_from_yaml_file("cfg/ex1.yaml"); - info.Dump(stdout); - CPlatformSocketInfoConfig cfg; - cfg.Create(&info.m_platform); - cfg.set_latency_thread_is_enabled(true); - cfg.set_number_of_dual_ports(1); - cfg.set_number_of_threads_per_ports(1); +class ipg_calc : public testing::Test { + protected: + virtual void SetUp() { + } + virtual void TearDown() { + } +public: +}; - cfg.sanity_check(); - cfg.dump(stdout); -} -#endif +TEST_F(ipg_calc, test1) { + + CCalcIpgDiff dcalc(20/1000000.0); + int i; + for (i=0; i<40; i++) { + uint32_t ticks=dcalc.do_calc(1.0/1000000.0); + if (i==19 || (i==39)) { + EXPECT_EQ(ticks,1); + }else{ + EXPECT_EQ(ticks,0); + } + } +} + +TEST_F(ipg_calc, test2) { + + CCalcIpgDiff dcalc(20/1000000.0); + int i; + for (i=0; i<40; i++) { + uint32_t ticks=dcalc.do_calc(40.0/1000000.0); + EXPECT_EQ(ticks,2); + } +} + +TEST_F(ipg_calc, test3) { + + CCalcIpgDiff dcalc(20/1000000.0); + int i; + for (i=0; i<1; i++) { + uint32_t ticks=dcalc.do_calc(2*((double)UINT32_MAX)*20.0/1000000.0); + //printf(" %ul \n",ticks,); + EXPECT_EQ(ticks,UINT32_MAX); + } +} + diff --git a/src/bp_sim.cpp b/src/bp_sim.cpp index 077bef63..080a6b5e 100755 --- a/src/bp_sim.cpp +++ b/src/bp_sim.cpp @@ -25,6 +25,7 @@ limitations under the License. #include "utl_yaml.h" #include "msg_manager.h" #include "trex_watchdog.h" +#include "utl_ipg_bucket.h" #include @@ -1897,6 +1898,94 @@ void CFlowPktInfo::Dump(FILE *fd){ +void CCapFileFlowInfo::generate_flow(CTupleTemplateGeneratorSmart * tuple_gen, + CNodeGenerator * gen, + dsec_t time, + uint64_t flow_id, + CFlowYamlInfo * template_info, + CGenNode * node){ + dsec_t c_time = time; + + node->m_type=CGenNode::FLOW_PKT; + CTupleBase tuple; + tuple_gen->GenerateTuple(tuple); + + CFlowGenListPerThread * lpThread=gen->Parent(); + + /* add the first packet of the flow */ + CFlowPktInfo * lp=GetPacket((uint32_t)0); + + node->set_socket_id(gen->m_socket_id); + + node->m_thread_id = tuple_gen->GetThreadId(); + node->m_flow_id = (flow_id & (0x000fffffffffffffULL)) | + ( ((uint64_t)(tuple_gen->GetThreadId()& 0xff)) <<56 ) ; + + node->m_time = c_time; + node->m_pkt_info = lp; + node->m_flow_info = this; + node->m_flags=0; + node->m_template_info =template_info; + node->m_tuple_gen = tuple_gen->get_gen(); + node->m_src_ip= tuple.getClient(); + node->m_dest_ip = tuple.getServer(); + node->m_src_idx = tuple.getClientId(); + node->m_dest_idx = tuple.getServerId(); + node->m_src_port = tuple.getClientPort(); + node->m_client_cfg = tuple.getClientCfg(); + + node->m_plugin_info =(void *)0; + + if ( unlikely( CGlobalInfo::is_learn_mode() ) ){ + // check if flow is two direction + if ( lp->m_pkt_indication.m_desc.IsBiDirectionalFlow() ) { + /* we are in learn mode */ + lpThread->associate(((uint32_t)flow_id) & NAT_FLOW_ID_MASK, node); /* associate flow_id=>node */ + node->set_nat_first_state(); + } + } + + if ( unlikely( get_is_rx_check_mode()) ) { + if ( (CGlobalInfo::m_options.m_rx_check_sample == 1 ) || + ( ( rte_rand() % CGlobalInfo::m_options.m_rx_check_sample ) == 1 )){ + if (unlikely(!node->is_repeat_flow() )) { + node->set_rx_check(); + } + } + } + + if ( unlikely( CGlobalInfo::m_options.preview.getClientServerFlowFlipAddr() ) ){ + node->set_initiator_start_from_server_side_with_server_addr(node->is_eligible_from_server_side()); + }else{ + /* -p */ + if ( likely( CGlobalInfo::m_options.preview.getClientServerFlowFlip() ) ){ + node->set_initiator_start_from_server(node->is_eligible_from_server_side()); + node->set_all_flow_from_same_dir(true); + }else{ + /* --flip */ + if ( unlikely( CGlobalInfo::m_options.preview.getClientServerFlip() ) ){ + node->set_initiator_start_from_server(node->is_eligible_from_server_side()); + } + } + } + + + /* in case of plugin we need to call the callback */ + if ( template_info->m_plugin_id ) { + /* alloc the info , generate the ports */ + on_node_first(template_info->m_plugin_id,node,template_info,tuple_gen,gen->Parent() ); + } + + node->m_tmr.reset(); + + /* in case of noraml flow use TW */ + if (likely(node->m_type == CGenNode::FLOW_PKT)){ + lpThread->on_flow_tick(node); /* tick packet */ + }else{ + gen->add_node(node); + } +} + void CCapFileFlowInfo::save_to_erf(std::string cap_file_name,int pcap){ if (Size() ==0) { @@ -2073,13 +2162,16 @@ enum CCapFileFlowInfo::load_cap_file_err CCapFileFlowInfo::is_valid_template_loa * 1. maximum aging * 2. per sub-flow pkt_num/max-pkt per dir and per global */ -void CCapFileFlowInfo::update_info(){ +void CCapFileFlowInfo::update_info(CFlowYamlInfo * flow_info){ flow_tmp_map_iter_t iter; flow_tmp_map_t ft; CTmpFlowInfo * lpFlow; int i; dsec_t ctime=0.0; + CCalcIpgDiff dtick_util(BUCKET_TIME_SEC); + + // first iteration, lern all the info into a temp flow table for (i=0; iSetMaxPkts(lpFlow->m_per_dir[dir].m_pkt_id); lp->m_pkt_indication.m_desc.SetMaxPktsPerFlow(lpFlow->m_max_pkts); lp->m_pkt_indication.m_desc.SetMaxFlowTimeout(lpFlow->m_max_aging_sec); + + + + /* update dtick from ipg */ + double dtime=0; + + if ( likely ( lp->m_pkt_indication.m_desc.IsPcapTiming()) ){ + dtime = lp->m_pkt_indication.m_cap_ipg ; + }else{ + if ( lp->m_pkt_indication.m_desc.IsRtt() ){ + dtime = flow_info->m_rtt_sec ; + }else{ + dtime = flow_info->m_ipg_sec; + } + lp->m_pkt_indication.m_cap_ipg = dtime; + } + lp->m_pkt_indication.m_ticks = dtick_util.do_calc(dtime); } @@ -2351,6 +2460,8 @@ enum CCapFileFlowInfo::load_cap_file_err CCapFileFlowInfo::load_cap_file(std::st return kOK; } + + void CCapFileFlowInfo::update_pcap_mode(){ int i; for (i=0; i<(int)Size(); i++) { @@ -3188,7 +3299,7 @@ bool CFlowGeneratorRec::Create(CFlowYamlInfo * info, if (m_flow_info.is_valid_template_load_time() != 0) { return (false); } - m_flow_info.update_info(); + m_flow_info.update_info(m_info); return (true); }else{ return (false); @@ -3311,7 +3422,7 @@ int CNodeGenerator::update_stl_stats(CGenNodeStateless *node_sl){ } -int CNodeGenerator::update_stats(CGenNode * node){ +int CNodeGenerator::update_stats(CGenNode * node){ if ( m_preview_mode.getVMode() >2 ){ fprintf(stdout," %llu ,", (unsigned long long)m_cnt); node->Dump(stdout); @@ -3320,6 +3431,7 @@ int CNodeGenerator::update_stats(CGenNode * node){ return (0); } + bool CNodeGenerator::has_limit_reached() { /* do we have a limit and has it passed ? */ return ( (m_limit > 0) && (m_cnt >= m_limit) ); @@ -3347,7 +3459,6 @@ bool CFlowGenListPerThread::Create(uint32_t thread_id, char name[100]; sprintf(name,"nodes-%d",m_core_id); - //printf(" create thread %d %s socket: %d \n",m_core_id,name,socket_id); m_node_pool = utl_rte_mempool_create_non_pkt(name, CGlobalInfo::m_memory_cfg.get_each_core_dp_flows(), @@ -3356,7 +3467,8 @@ bool CFlowGenListPerThread::Create(uint32_t thread_id, 0 , socket_id); - //printf(" pool %p \n",m_node_pool); + m_tw.Create(TW_BUCKETS,3); + m_node_gen.Create(this); m_flow_id_to_node_lookup.Create(); @@ -3556,6 +3668,7 @@ void CFlowGenListPerThread::Delete(){ m_node_gen.Delete(); Clean(); m_cpu_cp_u.Delete(); + m_tw.Delete(); utl_rte_mempool_delete(m_node_pool); } @@ -3628,22 +3741,109 @@ inline bool CNodeGenerator::handle_stl_node(CGenNode * node, } + +#define unsafe_container_of(var,ptr, type, member) \ + ((type *) ((uint8_t *)(ptr) - offsetof(type, member))) + + +/*TEARDOWN is true for stateful in second phase we wait for all the flow to finish +with --nc there is no TEARDOWN + +first phase ==> TEARDOWN =false +last phase ==> TEARDOWN =true + +this is relevant for repeatable flows +*/ + +template +inline void CFlowGenListPerThread::on_flow_tick(CGenNode *node){ + + #ifdef TREX_SIM + node->m_time=m_cur_time_sec; + #endif + #ifdef _DEBUG + m_node_gen.update_stats(node); + #endif + m_node_gen.flush_one_node_to_file(node); + + if ( likely (!node->is_repeat_flow()) ) { + if ( likely (!node->is_last_in_flow()) ) { + m_tw.timer_start(&node->m_tmr,node->update_next_pkt_in_flow_tw() ); + }else{ + free_last_flow_node( node); + } + }else{ + /* repeatable flow, we need to stop it in case of repeat */ + if ( node->is_last_in_flow() ) { + + if ( TEARDOWN == false ){ + node->m_time=m_cur_time_sec; /* update the node time as we schedule it */ + reschedule_flow(node); + }else{ + free_last_flow_node( node); + } + + }else{ + m_tw.timer_start(&node->m_tmr,node->update_next_pkt_in_flow_tw() ); + } + } +} + +#define GCC_DIAG_STR(s) #s +#define GCC_DIAG_JOINSTR(x,y) GCC_DIAG_STR(x ## y) +# define GCC_DIAG_DO_PRAGMA(x) _Pragma (#x) +# define GCC_DIAG_PRAGMA(x) GCC_DIAG_DO_PRAGMA(GCC diagnostic x) +#define GCC_DIAG_OFF(x) GCC_DIAG_PRAGMA(push) \ + GCC_DIAG_PRAGMA(ignored GCC_DIAG_JOINSTR(-W,x)) +#define GCC_DIAG_ON() GCC_DIAG_PRAGMA(pop) + +#define UNSAFE_CONTAINER_OF_PUSH GCC_DIAG_OFF(invalid-offsetof) +#define UNSAFE_CONTAINER_OF_POP GCC_DIAG_ON() + + + + +static void tw_on_tick_per_thread_cb_always(void *userdata, + CHTimerObj *tmr){ + CFlowGenListPerThread * thread=(CFlowGenListPerThread * )userdata; + UNSAFE_CONTAINER_OF_PUSH; + CGenNode * node=unsafe_container_of(node,tmr,CGenNode,m_tmr); + UNSAFE_CONTAINER_OF_POP; + + thread->on_flow_tick(node); +} + + +void tw_on_tick_per_thread_cb(void *userdata, + CHTimerObj *tmr){ + CFlowGenListPerThread * thread=(CFlowGenListPerThread * )userdata; + + UNSAFE_CONTAINER_OF_PUSH; + CGenNode * node=unsafe_container_of(node,tmr,CGenNode,m_tmr); + UNSAFE_CONTAINER_OF_POP; + + thread->on_flow_tick(node); +} + + inline bool CNodeGenerator::do_work_stl(CGenNode * node, - CFlowGenListPerThread * thread, - bool always){ + CFlowGenListPerThread * thread, + bool on_terminate){ if ( handle_stl_node(node,thread)){ return (false); }else{ - return (handle_slow_messages(node->m_type,node,thread,always)); + return (handle_slow_messages(node->m_type,node,thread,on_terminate)); } } + + + +template inline bool CNodeGenerator::do_work_both(CGenNode * node, - CFlowGenListPerThread * thread, - dsec_t d_time, - bool always - ){ + CFlowGenListPerThread * thread, + dsec_t d_time){ bool exit_scheduler=false; uint8_t type=node->m_type; @@ -3651,48 +3851,53 @@ inline bool CNodeGenerator::do_work_both(CGenNode * node, if ( handle_stl_node (node,thread) ){ }else{ - if ( likely( type == CGenNode::FLOW_PKT ) ) { - /* PKT */ - if ( !(node->is_repeat_flow()) || (always==false)) { - flush_one_node_to_file(node); - #ifdef _DEBUG - update_stats(node); - #endif - } + if ( likely( type == CGenNode::TW_SYNC ) ) { m_p_queue.pop(); - if ( node->is_last_in_flow() ) { - if ((node->is_repeat_flow()) && (always==false)) { - /* Flow is repeated, reschedule it */ - thread->reschedule_flow( node); + /* update bucket time */ + thread->m_cur_time_sec = node->m_time; + if ( ON_TERMINATE ) { + thread->m_tw.on_tick((void*)thread,tw_on_tick_per_thread_cb_always); + if ( thread->m_tw.is_any_events_left() ){ + node->m_time += BUCKET_TIME_SEC; + m_p_queue.push(node); }else{ - /* Flow will not be repeated, so free node */ - thread->free_last_flow_node( node); + thread->free_node(node); } }else{ - node->update_next_pkt_in_flow(); + thread->m_tw.on_tick((void*)thread,tw_on_tick_per_thread_cb); + node->m_time += BUCKET_TIME_SEC;; m_p_queue.push(node); } - }else{ - if ((type == CGenNode::FLOW_FIF)) { - /* callback to our method */ - m_p_queue.pop(); - if ( always == false) { - thread->m_cur_time_sec = node->m_time ; - thread->generate_flows_roundrobin(&done); + }else{ - if (!done) { - node->m_time +=d_time; - m_p_queue.push(node); + if ( likely( type == CGenNode::FLOW_PKT ) ) { + /* PKT */ + m_p_queue.pop(); + thread->on_flow_tick(node); + //printf(" MOVE from PKT->TW\n"); + }else{ + if ((type == CGenNode::FLOW_FIF)) { + /* callback to our method */ + m_p_queue.pop(); + if ( ON_TERMINATE == false) { + thread->m_cur_time_sec = node->m_time ; + + thread->generate_flows_roundrobin(&done); + + if (!done) { + node->m_time +=d_time; + m_p_queue.push(node); + }else{ + thread->free_node(node); + } }else{ thread->free_node(node); } + }else{ - thread->free_node(node); + exit_scheduler = handle_slow_messages(type,node,thread,ON_TERMINATE); } - - }else{ - exit_scheduler = handle_slow_messages(type,node,thread,always); } } } @@ -3702,18 +3907,16 @@ inline bool CNodeGenerator::do_work_both(CGenNode * node, -template +template inline bool CNodeGenerator::do_work(CGenNode * node, - CFlowGenListPerThread * thread, - dsec_t d_time, - bool always - ){ + CFlowGenListPerThread * thread, + dsec_t d_time){ /* template filter in compile time */ if ( SCH_MODE == smSTATELESS ) { - return ( do_work_stl(node,thread,always) ); + return ( do_work_stl(node,thread,ON_TERMINATE) ); }else{ /* smSTATEFUL */ - return ( do_work_both(node,thread,d_time,always) ); + return ( do_work_both(node,thread,d_time) ); } } @@ -3741,9 +3944,9 @@ inline void CNodeGenerator::do_sleep(dsec_t & cur_time, inline int CNodeGenerator::teardown(CFlowGenListPerThread * thread, - bool always, - double &old_offset, - double offset){ + bool on_terminate, + double &old_offset, + double offset){ thread->m_cpu_dp_u.commit1(); @@ -3752,7 +3955,7 @@ inline int CNodeGenerator::teardown(CFlowGenListPerThread * thread, return (0); } - if (!always) { + if (!on_terminate) { old_offset =offset; }else{ // free the left other @@ -3763,17 +3966,16 @@ inline int CNodeGenerator::teardown(CFlowGenListPerThread * thread, -template +template inline int CNodeGenerator::flush_file_realtime(dsec_t max_time, dsec_t d_time, - bool always, CFlowGenListPerThread * thread, double &old_offset) { CGenNode * node; dsec_t offset=0.0; dsec_t cur_time; dsec_t n_time; - if (always) { + if (ON_TERIMATE) { offset=old_offset; }else{ add_exit_node(thread,max_time); @@ -3810,7 +4012,7 @@ inline int CNodeGenerator::flush_file_realtime(dsec_t max_time, int node_count = 0; do { - bool s=do_work(node,thread,d_time,always); + bool s=do_work(node,thread,d_time); if (s) { // can we remove this IF ? state=scTERMINATE; break; @@ -3842,7 +4044,7 @@ inline int CNodeGenerator::flush_file_realtime(dsec_t max_time, }/* while*/ - return (teardown(thread,always,old_offset,offset)); + return (teardown(thread,ON_TERIMATE,old_offset,offset)); } @@ -3903,12 +4105,12 @@ void CNodeGenerator::handle_time_strech(CGenNode * &node, int CNodeGenerator::flush_file_sim(dsec_t max_time, dsec_t d_time, - bool always, + bool on_terminate, CFlowGenListPerThread * thread, double &old_offset){ CGenNode * node; - if (!always) { + if (!on_terminate) { add_exit_node(thread,max_time); } @@ -3916,30 +4118,46 @@ int CNodeGenerator::flush_file_sim(dsec_t max_time, node = m_p_queue.top(); bool do_exit; - if ( get_is_stateless() ) { - do_exit=do_work(node,thread,d_time,always); + if (on_terminate) { + if ( get_is_stateless() ) { + do_exit=do_work(node,thread,d_time); + }else{ + do_exit=do_work(node,thread,d_time); + } }else{ - do_exit=do_work(node,thread,d_time,always); + if ( get_is_stateless() ) { + do_exit=do_work(node,thread,d_time); + }else{ + do_exit=do_work(node,thread,d_time); + } } if ( do_exit ){ break; } } - return (teardown(thread,always,old_offset,0)); + return (teardown(thread,on_terminate,old_offset,0)); } int CNodeGenerator::flush_file(dsec_t max_time, dsec_t d_time, - bool always, + bool on_terminate, CFlowGenListPerThread * thread, double &old_offset){ #ifdef TREX_SIM - return ( flush_file_sim(max_time, d_time,always,thread,old_offset) ); + return ( flush_file_sim(max_time, d_time,on_terminate,thread,old_offset) ); #else - if ( get_is_stateless() ) { - return ( flush_file_realtime(max_time, d_time,always,thread,old_offset) ); + if (on_terminate) { + if ( get_is_stateless() ) { + return ( flush_file_realtime(max_time, d_time,thread,old_offset) ); + }else{ + return ( flush_file_realtime(max_time, d_time,thread,old_offset) ); + } }else{ - return ( flush_file_realtime(max_time, d_time,always,thread,old_offset) ); + if ( get_is_stateless() ) { + return ( flush_file_realtime(max_time, d_time,thread,old_offset) ); + }else{ + return ( flush_file_realtime(max_time, d_time,thread,old_offset) ); + } } #endif @@ -3953,9 +4171,7 @@ void CNodeGenerator::handle_flow_pkt(CGenNode *node, CFlowGenListPerThread *thre if ( node->is_nat_first_state() ) { node->set_nat_wait_state(); flush_one_node_to_file(node); - #ifdef _DEBUG - update_stats(node); - #endif + UPDATE_STATS(node); } else { if ( node->is_nat_wait_state() ) { if (node->is_responder_pkt()) { @@ -3966,9 +4182,7 @@ void CNodeGenerator::handle_flow_pkt(CGenNode *node, CFlowGenListPerThread *thre } else { flush_one_node_to_file(node); - #ifdef _DEBUG - update_stats(node); - #endif + UPDATE_STATS(node); } } else { if ( node->is_nat_wait_ack_state() ) { @@ -3980,9 +4194,7 @@ void CNodeGenerator::handle_flow_pkt(CGenNode *node, CFlowGenListPerThread *thre } else { flush_one_node_to_file(node); -#ifdef _DEBUG - update_stats(node); -#endif + UPDATE_STATS(node); } } else { assert(0); @@ -3993,7 +4205,7 @@ void CNodeGenerator::handle_flow_pkt(CGenNode *node, CFlowGenListPerThread *thre if ( node->is_last_in_flow() ) { thread->free_last_flow_node( node); } else { - node->update_next_pkt_in_flow(); + node->update_next_pkt_in_flow_as(); m_p_queue.push(node); } } @@ -4062,7 +4274,7 @@ bool CNodeGenerator::handle_slow_messages(uint8_t type, CGenNode * node, CFlowGenListPerThread * thread, - bool always){ + bool on_terminate){ /* should we continue after */ bool exit_scheduler = false; @@ -4519,9 +4731,18 @@ void CFlowGenListPerThread::start_generate_stateful(std::string erf_file_name, node= create_node() ; node->m_type = CGenNode::FLOW_SYNC; node->m_time = m_cur_time_sec + SYNC_TIME_OUT ; - m_node_gen.add_node(node); + + if ( !get_is_stateless() ){ + /* add TW only for Stateful right now */ + node= create_node() ; + node->m_type = CGenNode::TW_SYNC; + node->m_time = m_cur_time_sec + BUCKET_TIME_SEC ; + m_node_gen.add_node(node); + } + + #ifdef _DEBUG if ( m_preview_mode.getVMode() >2 ){ diff --git a/src/bp_sim.h b/src/bp_sim.h index c9e43ba3..fe8f55ac 100755 --- a/src/bp_sim.h +++ b/src/bp_sim.h @@ -61,6 +61,8 @@ limitations under the License. #include "flow_stat.h" #include "trex_watchdog.h" #include "trex_client_config.h" +#include "h_timer.h" + #include @@ -1338,6 +1340,8 @@ struct CFlowYamlInfo { m_client_pool_idx = 0; m_server_pool_idx = 0; m_cap_mode=false; + m_ipg_sec=0.01; + m_rtt_sec=0.01; } std::string m_name; @@ -1427,6 +1431,7 @@ public: EXIT_PORT_SCHED =8, PCAP_PKT =9, GRAT_ARP =10, + TW_SYNC =11 }; /* flags MASKS*/ @@ -1514,7 +1519,12 @@ public: void * m_plugin_info; -//private: +/* cache line -2 */ + CHTimerObj m_tmr; + uint64_t m_tmr_pad[4]; + +/* cache line -3 */ + CTupleGeneratorSmart *m_tuple_gen; // cache line 1 - 64bytes waste of space ! @@ -1543,8 +1553,11 @@ public: inline bool can_cache_mbuf(void); /* is it possible to cache MBUF */ + inline uint32_t update_next_pkt_in_flow_tw(void); + + /* update the node time for accurate scheduler */ + inline void update_next_pkt_in_flow_as(void); - inline void update_next_pkt_in_flow(void); inline void reset_pkt_in_flow(void); inline uint8_t get_plugin_id(void){ return ( m_template_info->m_plugin_id); @@ -1752,6 +1765,8 @@ struct CGenNodeDeferPort { uint32_t m_clients[DEFER_CLIENTS_NUM]; uint16_t m_ports[DEFER_CLIENTS_NUM]; uint8_t m_pool_idx[DEFER_CLIENTS_NUM]; + uint64_t m_pad4[8]; + public: void init(void){ m_type=CGenNode::FLOW_DEFER_PORT_RELEASE; @@ -2001,6 +2016,8 @@ public: class CNodeGenerator { public: + friend CFlowGenListPerThread; + typedef enum { scINIT = 0x17, scWORK , scWAIT , @@ -2035,7 +2052,7 @@ public: int close_file(CFlowGenListPerThread * thread); int flush_file(dsec_t max_time, dsec_t d_time, - bool always, + bool on_terminate, CFlowGenListPerThread * thread, double & old_offset); int defer_handler(CFlowGenListPerThread * thread); @@ -2063,18 +2080,27 @@ public: void dump_json(std::string & json); + private: + + #ifdef _DEBUG + #define UPDATE_STATS(a) update_stats(a) + #else + #define UPDATE_STATS(a) + #endif + + int update_stats(CGenNode * node); + inline int flush_one_node_to_file(CGenNode * node){ return (m_v_if->send_node(node)); } - int update_stats(CGenNode * node); int update_stl_stats(CGenNodeStateless *node_sl); bool has_limit_reached(); FORCE_NO_INLINE bool handle_slow_messages(uint8_t type, CGenNode * node, CFlowGenListPerThread * thread, - bool always); + bool on_terminate); private: void add_exit_node(CFlowGenListPerThread * thread, @@ -2086,18 +2112,17 @@ private: FORCE_INLINE bool do_work_stl(CGenNode * node, CFlowGenListPerThread * thread, - bool always); + bool on_terminate); + template FORCE_INLINE bool do_work_both(CGenNode * node, CFlowGenListPerThread * thread, - dsec_t d_time, - bool always); + dsec_t d_time); - template + template FORCE_INLINE bool do_work(CGenNode * node, CFlowGenListPerThread * thread, - dsec_t d_time, - bool always); + dsec_t d_time); FORCE_INLINE void do_sleep(dsec_t & cur_time, CFlowGenListPerThread * thread, @@ -2105,14 +2130,13 @@ private: FORCE_INLINE int teardown(CFlowGenListPerThread * thread, - bool always, + bool on_terminate, double &old_offset, double offset); - template + template int flush_file_realtime(dsec_t max_time, dsec_t d_time, - bool always, CFlowGenListPerThread * thread, double &old_offset); @@ -2569,8 +2593,9 @@ public: class CPacketIndication { public: - dsec_t m_cap_ipg; /* ipg from cap file */ - CCapPktRaw * m_packet; + uint32_t m_ticks; + CPacketDescriptor m_desc; + CCapPktRaw * m_packet; CFlow * m_flow; EthernetHeader * m_ether; @@ -2588,9 +2613,9 @@ public: uint16_t m_payload_len; uint16_t m_packet_padding; /* total packet size - IP total length */ + dsec_t m_cap_ipg; /* ipg from cap file */ CFlowKey m_flow_key; - CPacketDescriptor m_desc; uint8_t m_ether_offset; uint8_t m_ip_offset; @@ -3420,6 +3445,7 @@ public: }; + class CCapFileFlowInfo { public: const int LEARN_MODE_MIN_IPG = 10; // msec @@ -3453,13 +3479,13 @@ public: enum load_cap_file_err load_cap_file(std::string cap_file, uint16_t _id, uint8_t plugin_id); /* update flow info */ - void update_info(); + void update_info(CFlowYamlInfo * info); enum CCapFileFlowInfo::load_cap_file_err is_valid_template_load_time(); void save_to_erf(std::string cap_file_name,int pcap); - inline void generate_flow(CTupleTemplateGeneratorSmart * tuple_gen, + void generate_flow(CTupleTemplateGeneratorSmart * tuple_gen, CNodeGenerator * gen, dsec_t time, uint64_t flow_id, @@ -3713,6 +3739,12 @@ private: bool server_seq_init; /* TCP seq been init for server? */ }; +#define BUCKET_TIME_USEC (20) +#define TW_BUCKETS (1024) +#define BUCKET_TIME_SEC ((double)BUCKET_TIME_USEC/1000000.0) + +#define TW_BUCKETS_MAX_TIME (BUCKET_TIME_USEC *TW_BUCKETS) + ///////////////////////////////////////////////////////////////////////////////// /* per thread info */ @@ -3752,7 +3784,10 @@ public: m_monitor.tickle(); } - + template + inline void on_flow_tick(CGenNode *node); + + /* return the dual port ID this thread is attached to in 4 ports configuration there are 2 dual-ports @@ -3789,6 +3824,7 @@ public : inline void free_last_flow_node(CGenNode *p); + public: void Clean(); void start_generate_stateful(std::string erf_file_name,CPreviewMode &preview); @@ -3922,6 +3958,8 @@ public: public: CNodeGenerator m_node_gen; + CHTimerWheel m_tw; + public: uint32_t m_cur_template; uint32_t m_non_active_nodes; /* the number of non active nodes -> nodes that try to stop somthing */ @@ -4027,85 +4065,6 @@ public: -inline void CCapFileFlowInfo::generate_flow(CTupleTemplateGeneratorSmart * tuple_gen, - CNodeGenerator * gen, - dsec_t time, - uint64_t flow_id, - CFlowYamlInfo * template_info, - CGenNode * node){ - dsec_t c_time = time; - - node->m_type=CGenNode::FLOW_PKT; - CTupleBase tuple; - tuple_gen->GenerateTuple(tuple); - - /* add the first packet of the flow */ - CFlowPktInfo * lp=GetPacket((uint32_t)0); - - node->set_socket_id(gen->m_socket_id); - - node->m_thread_id = tuple_gen->GetThreadId(); - node->m_flow_id = (flow_id & (0x000fffffffffffffULL)) | - ( ((uint64_t)(tuple_gen->GetThreadId()& 0xff)) <<56 ) ; - - node->m_time = c_time; - node->m_pkt_info = lp; - node->m_flow_info = this; - node->m_flags=0; - node->m_template_info =template_info; - node->m_tuple_gen = tuple_gen->get_gen(); - node->m_src_ip= tuple.getClient(); - node->m_dest_ip = tuple.getServer(); - node->m_src_idx = tuple.getClientId(); - node->m_dest_idx = tuple.getServerId(); - node->m_src_port = tuple.getClientPort(); - node->m_client_cfg = tuple.getClientCfg(); - - node->m_plugin_info =(void *)0; - - if ( unlikely( CGlobalInfo::is_learn_mode() ) ){ - // check if flow is two direction - if ( lp->m_pkt_indication.m_desc.IsBiDirectionalFlow() ) { - /* we are in learn mode */ - CFlowGenListPerThread * lpThread=gen->Parent(); - lpThread->associate(((uint32_t)flow_id) & NAT_FLOW_ID_MASK, node); /* associate flow_id=>node */ - node->set_nat_first_state(); - } - } - - if ( unlikely( get_is_rx_check_mode()) ) { - if ( (CGlobalInfo::m_options.m_rx_check_sample == 1 ) || - ( ( rte_rand() % CGlobalInfo::m_options.m_rx_check_sample ) == 1 )){ - if (unlikely(!node->is_repeat_flow() )) { - node->set_rx_check(); - } - } - } - - if ( unlikely( CGlobalInfo::m_options.preview.getClientServerFlowFlipAddr() ) ){ - node->set_initiator_start_from_server_side_with_server_addr(node->is_eligible_from_server_side()); - }else{ - /* -p */ - if ( likely( CGlobalInfo::m_options.preview.getClientServerFlowFlip() ) ){ - node->set_initiator_start_from_server(node->is_eligible_from_server_side()); - node->set_all_flow_from_same_dir(true); - }else{ - /* --flip */ - if ( unlikely( CGlobalInfo::m_options.preview.getClientServerFlip() ) ){ - node->set_initiator_start_from_server(node->is_eligible_from_server_side()); - } - } - } - - - /* in case of plugin we need to call the callback */ - if ( template_info->m_plugin_id ) { - /* alloc the info , generate the ports */ - on_node_first(template_info->m_plugin_id,node,template_info,tuple_gen,gen->Parent() ); - } - - gen->add_node(node); -} inline void CFlowGeneratorRecPerThread::generate_flow(CNodeGenerator * gen, @@ -4144,20 +4103,22 @@ inline bool CGenNode::is_repeat_flow(){ return ( m_template_info->m_limit_was_set); } -inline void CGenNode::update_next_pkt_in_flow(void){ - if ( likely ( m_pkt_info->m_pkt_indication.m_desc.IsPcapTiming()) ){ - m_time += m_pkt_info->m_pkt_indication.m_cap_ipg ; - }else{ - if ( m_pkt_info->m_pkt_indication.m_desc.IsRtt() ){ - m_time += m_template_info->m_rtt_sec ; - }else{ - m_time += m_template_info->m_ipg_sec; - } - } +inline void CGenNode::update_next_pkt_in_flow_as(void){ + + m_time += m_pkt_info->m_pkt_indication.m_cap_ipg; + uint32_t pkt_index = m_pkt_info->m_pkt_indication.m_packet->pkt_cnt; + pkt_index++; + m_pkt_info = m_flow_info->GetPacket((pkt_index-1)); +} + +inline uint32_t CGenNode::update_next_pkt_in_flow_tw(void){ + + uint32_t dticks = m_pkt_info->m_pkt_indication.m_ticks; uint32_t pkt_index = m_pkt_info->m_pkt_indication.m_packet->pkt_cnt; pkt_index++; m_pkt_info = m_flow_info->GetPacket((pkt_index-1)); + return (dticks); } inline void CGenNode::reset_pkt_in_flow(void){ diff --git a/src/common/basic_utils.h b/src/common/basic_utils.h index 36f9db85..b715c4b7 100755 --- a/src/common/basic_utils.h +++ b/src/common/basic_utils.h @@ -21,6 +21,57 @@ limitations under the License. #include #include +/** + * return true if number of log2 + * + * @param num + * + * @return + */ +inline bool utl_islog2(uint32_t num){ + uint32_t mask=1; + int i; + for (i=0; i<31; i++) { + if (mask == num) { + return (true); + } + if (mask > num) { + return(false); + } + mask=mask<<1; + } + return (false); +} + +inline uint32_t utl_log2_shift(uint32_t num){ + uint32_t mask=1; + int i; + for (i=0; i<31; i++) { + if (mask == num) { + return ((uint32_t)i); + } + if (mask > num) { + return(false); + } + mask=mask<<1; + } + assert(0); + return (-1); +} + + +/** + * return mask for log2 number + * + * @param num + * + * @return + */ +inline uint32_t utl_mask_log2(uint32_t num){ + return (num-1); +} + + /** * the round must be power 2 e.g 2,4,8... * diff --git a/src/gtest/bp_timer_gtest.cpp b/src/gtest/bp_timer_gtest.cpp new file mode 100644 index 00000000..c0779868 --- /dev/null +++ b/src/gtest/bp_timer_gtest.cpp @@ -0,0 +1,595 @@ +/* + Hanoh Haim + Cisco Systems, Inc. +*/ + +/* +Copyright (c) 2015-2015 Cisco Systems, Inc. + +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 +#include +#include "h_timer.h" + + +class gt_r_timer : public testing::Test { + +protected: + virtual void SetUp() { + } + + virtual void TearDown() { + } +public: +}; + + + + +TEST_F(gt_r_timer, timer1) { + CHTimerObj timer; + timer.reset(); + timer.Dump(stdout); +} + + + +TEST_F(gt_r_timer, timer2) { + + CHTimerOneWheel timer; + + EXPECT_EQ( timer.Create(513),RC_HTW_ERR_NO_LOG2); + +} + +TEST_F(gt_r_timer, timer3) { + + CHTimerOneWheel timer; + EXPECT_EQ( timer.Create(512),RC_HTW_OK); + EXPECT_EQ( timer.Delete(),RC_HTW_OK); +} + + +void tw_on_tick_cb_test1(void *userdata, + CHTimerObj *tmr){ + //int tick=(int)((uintptr_t)userdata); + + printf(" action %lu \n",(ulong)tmr->m_pad[0]); +} + + +TEST_F(gt_r_timer, timer4) { + + CHTimerOneWheel timer; + CHTimerObj tmr1; + CHTimerObj tmr2; + tmr1.reset(); + tmr2.reset(); + + tmr1.m_ticks_left=0; + tmr1.m_pad[0]=1; + tmr2.m_ticks_left=0; + tmr2.m_pad[0]=2; + + EXPECT_EQ( timer.Create(512),RC_HTW_OK); + timer.timer_start(&tmr1,7); + timer.timer_start(&tmr2,7); + timer.dump_link_list(1,0,tw_on_tick_cb_test1,stdout); + timer.dump_link_list(7,0,tw_on_tick_cb_test1,stdout); + + + EXPECT_EQ( timer.Delete(),RC_HTW_OK); +} + +TEST_F(gt_r_timer, timer5) { + + CHTimerOneWheel timer; + CHTimerObj tmr1; + CHTimerObj tmr2; + tmr1.reset(); + tmr2.reset(); + + tmr1.m_ticks_left=0; + tmr1.m_pad[0]=1; + tmr2.m_ticks_left=0; + tmr2.m_pad[0]=2; + + EXPECT_EQ( timer.Create(512),RC_HTW_OK); + timer.timer_start(&tmr1,7); + timer.timer_start(&tmr2,7); + timer.dump_link_list(1,0,tw_on_tick_cb_test1,stdout); + timer.dump_link_list(7,0,tw_on_tick_cb_test1,stdout); + + assert( timer.pop_event()==0); + int i; + for (i=0; i<7; i++) { + timer.timer_tick(); + } + CHTimerObj * obj=timer.pop_event(); + assert(obj==&tmr1); + + timer.dump_link_list(7,0,tw_on_tick_cb_test1,stdout); + + + obj=timer.pop_event(); + assert(obj==&tmr2); + + EXPECT_EQ( timer.Delete(),RC_HTW_OK); +} + +class CMyTestObject { +public: + CMyTestObject(){ + m_id=0; + m_d_tick=0; + m_t_tick=0; + m_timer.reset(); + } + uint32_t m_id; + uint32_t m_d_tick; + uint32_t m_t_tick; + CHTimerObj m_timer; +}; + + +#define MY_OFFSET_OF(cls,member) ((uintptr_t)(&(cls *0)->member) ) + +void my_test_on_tick_cb(void *userdata,CHTimerObj *tmr){ + + + CHTimerWheel * lp=(CHTimerWheel *)userdata; + #pragma GCC diagnostic ignored "-Winvalid-offsetof" + CMyTestObject *lpobj=(CMyTestObject *)((uint8_t*)tmr-offsetof (CMyTestObject,m_timer)); + #pragma GCC diagnostic pop + printf(" [event %d ]",lpobj->m_id); + lp->timer_start(tmr,2); +} + +TEST_F(gt_r_timer, timer6) { + + CHTimerWheel timer; + + CMyTestObject tmr1; + tmr1.m_id=12; + + + EXPECT_EQ( timer.Create(8,3),RC_HTW_OK); + timer.timer_start(&tmr1.m_timer,3); + + int i; + for (i=0; i<20; i++) { + printf(" tick %d :",i); + timer.on_tick((void *)&timer,my_test_on_tick_cb); + printf(" \n"); + } + + EXPECT_EQ( timer.Delete(),RC_HTW_OK); +} + +void my_test_on_tick_cb7(void *userdata,CHTimerObj *tmr){ + + + CHTimerWheel * lp=(CHTimerWheel *)userdata; + #pragma GCC diagnostic ignored "-Winvalid-offsetof" + CMyTestObject *lpobj=(CMyTestObject *)((uint8_t*)tmr-offsetof (CMyTestObject,m_timer)); + #pragma GCC diagnostic pop + printf(" [event %d ]",lpobj->m_id); + lp->timer_start(tmr,9); +} + + +TEST_F(gt_r_timer, timer7) { + + CHTimerWheel timer; + + CMyTestObject tmr1; + tmr1.m_id=12; + + + EXPECT_EQ( timer.Create(4,4),RC_HTW_OK); + timer.timer_start(&tmr1.m_timer,80); + + int i; + for (i=0; i<150; i++) { + printf(" tick %d :",i); + timer.on_tick((void *)&timer,my_test_on_tick_cb7); + printf(" \n"); + } + + EXPECT_EQ( timer.Delete(),RC_HTW_OK); +} + + + +class CHTimerWheelTest1Cfg { +public: + uint32_t m_wheel_size; + uint32_t m_num_wheels; + uint32_t m_start_tick; + uint32_t m_restart_tick; + uint32_t m_total_ticks; + bool m_verbose; + bool m_dont_assert; +}; + +class CHTimerWheelBase { +public: + virtual void on_tick(CMyTestObject *lpobj)=0; +}; + + +class CHTimerWheelTest1 : public CHTimerWheelBase { + +public: + bool Create(CHTimerWheelTest1Cfg & cfg); + void Delete(); + void start_test(); + virtual void on_tick(CMyTestObject *lpobj); + +private: + CHTimerWheelTest1Cfg m_cfg; + CHTimerWheel m_timer; + CMyTestObject m_event; + uint32_t m_ticks; + uint32_t m_total_ticks; + uint32_t m_expected_total_ticks; + + uint32_t m_expect_tick; +}; + +void my_test_on_tick_cb8(void *userdata,CHTimerObj *tmr){ + CHTimerWheelBase * lp=(CHTimerWheelBase *)userdata; + #pragma GCC diagnostic ignored "-Winvalid-offsetof" + CMyTestObject *lpobj=(CMyTestObject *)((uint8_t*)tmr-offsetof (CMyTestObject,m_timer)); + #pragma GCC diagnostic pop + lp->on_tick(lpobj); +} + + +void CHTimerWheelTest1::on_tick(CMyTestObject *lpobj){ + assert(lpobj->m_id==17); + m_total_ticks++; + if (m_cfg.m_verbose) { + printf(" [event %d ]",lpobj->m_id); + } + if (!m_cfg.m_dont_assert){ + assert( m_ticks == m_expect_tick); + } + m_timer.timer_start(&lpobj->m_timer,m_cfg.m_restart_tick); + m_expect_tick+=m_cfg.m_restart_tick; +} + + +void CHTimerWheelTest1::start_test(){ + + if (m_cfg.m_verbose) { + printf(" test start %d,restart: %d \n",m_cfg.m_start_tick,m_cfg.m_restart_tick); + } + int i; + m_expected_total_ticks=0; + uint32_t cnt=m_cfg.m_start_tick; + for (i=0; im_id=i+1; + if (m_cfg.m_random) { + lp->m_d_tick = ((rand() % m_cfg.m_number_of_con_event)+1); + if (m_cfg.m_verbose) { + printf(" flow %d : %d \n",i,lp->m_d_tick); + } + }else{ + lp->m_d_tick=i+1; + } + lp->m_t_tick=lp->m_d_tick; + m_timer.timer_start(&lp->m_timer,lp->m_d_tick); + } + + for (i=0; im_id==lp->m_d_tick); + } + if (m_cfg.m_verbose) { + printf(" [event %d ]",lp->m_id); + } + m_timer.timer_start(&lp->m_timer,lp->m_d_tick); + if (!m_cfg.m_dont_check){ + assert(m_ticks == lp->m_t_tick); + } + lp->m_t_tick+=lp->m_d_tick; +} + +TEST_F(gt_r_timer, timer13) { + + CHTimerWheelTest2 test; + CHTimerWheelTest2Cfg cfg ={ + .m_wheel_size = 4, + .m_num_wheels = 4, + .m_number_of_con_event = 10, + .m_total_ticks =1000, + .m_random=false, + .m_verbose =false + }; + test.Create(cfg); + test.start_test(); + test.Delete(); +} + +TEST_F(gt_r_timer, timer14) { + + CHTimerWheelTest2 test; + CHTimerWheelTest2Cfg cfg ={ + .m_wheel_size = 8, + .m_num_wheels = 3, + .m_number_of_con_event = 10, + .m_total_ticks =1000, + .m_random=false, + .m_verbose =false + }; + test.Create(cfg); + test.start_test(); + test.Delete(); +} + +TEST_F(gt_r_timer, timer15) { + + CHTimerWheelTest2 test; + CHTimerWheelTest2Cfg cfg ={ + .m_wheel_size = 1024, + .m_num_wheels = 3, + .m_number_of_con_event = 100, + .m_total_ticks =10000, + .m_random=false, + .m_verbose =false + }; + test.Create(cfg); + test.start_test(); + test.Delete(); +} + +TEST_F(gt_r_timer, timer16) { + + CHTimerWheelTest2 test; + CHTimerWheelTest2Cfg cfg ={ + .m_wheel_size = 32, + .m_num_wheels = 4, + .m_number_of_con_event = 111, + .m_total_ticks =20000, + .m_random=true, + .m_verbose =false, + .m_dont_check=false + }; + test.Create(cfg); + test.start_test(); + test.Delete(); +} + diff --git a/src/h_timer.cpp b/src/h_timer.cpp new file mode 100644 index 00000000..baaaca31 --- /dev/null +++ b/src/h_timer.cpp @@ -0,0 +1,231 @@ +/* + Hanoh Haim + Cisco Systems, Inc. +*/ + +/* +Copyright (c) 2015-2015 Cisco Systems, Inc. + +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 "h_timer.h" + + +void CHTimerObj::Dump(FILE *fd){ + fprintf(fd,"m_tick_left :%lu \n", (ulong)m_ticks_left); +} + + +RC_HTW_t CHTimerOneWheel::Create(uint32_t wheel_size){ + + CHTimerWheelLink *bucket; + + if ( !utl_islog2(wheel_size) ){ + return (RC_HTW_ERR_NO_LOG2); + } + m_wheel_mask = utl_mask_log2(wheel_size); + m_wheel_size = wheel_size; + + m_buckets = (CHTimerWheelLink *)malloc(wheel_size * sizeof(CHTimerWheelLink)); + //printf(" bucket %x \n",); + if (m_buckets == 0) { + return (RC_HTW_ERR_NO_RESOURCES); + } + m_ticks=0; + m_bucket_index = 0; + m_tick_done=false; + + bucket = &m_buckets[0]; + m_active_bucket=bucket; + int i; + for (i = 0; i < wheel_size; i++) { + bucket->set_self(); + bucket++; + } + return (RC_HTW_OK); +} + +RC_HTW_t CHTimerOneWheel::Delete(){ + if (m_buckets) { + free(m_buckets); + m_buckets=0; + } + m_ticks=0; + m_bucket_index = 0; + return (RC_HTW_OK ); +} + + +RC_HTW_t CHTimerOneWheel::timer_stop(CHTimerObj *tmr){ + if ( tmr->is_running() ) { + tmr->detach(); + } + return (RC_HTW_OK); +} + + +void CHTimerOneWheel::dump_link_list(uint32_t bucket_index, + void *userdata, + htw_on_tick_cb_t cb, + FILE *fd){ + + + CHTimerWheelLink *bucket, *next; + CHTimerObj *tmr; + bucket = &m_buckets[bucket_index]; + + tmr = (CHTimerObj *)bucket->m_next; + bool found=false; + if ((CHTimerWheelLink *)tmr != bucket) { + fprintf(fd,"[%lu,\n",(ulong)bucket_index); + found=true; + } + + while( (CHTimerWheelLink *)tmr != bucket) { + + next = (CHTimerWheelLink *)tmr->m_next; + + tmr->Dump(fd); + cb(userdata,tmr); + + tmr = (CHTimerObj *)next; + } + if (found){ + fprintf(fd,"]\n"); + } +} + + +void CHTimerWheel::on_tick(void *userdata,htw_on_tick_cb_t cb){ + + int i; + + + for (i=0;ipop_event(); + if (!event) { + break; + } + m_total_events--; + if (event->m_ticks_left==0) { + cb(userdata,event); + }else{ + timer_start(event,event->m_ticks_left); + } + } + if (!lp->check_timer_tick_cycle()){ + break; + } + } + + /* tick all timers in one shoot */ + for (i=0;itimer_tick()){ + break; + } + } + m_ticks++; +} + + + +RC_HTW_t CHTimerWheel::timer_stop (CHTimerObj *tmr){ + if ( tmr->is_running() ) { + assert(tmr->m_wheelm_wheel].timer_stop(tmr); + m_total_events--; + } + return (RC_HTW_OK); +} + + + +RC_HTW_t CHTimerWheel::timer_start_rest(CHTimerObj *tmr, + htw_ticks_t ticks){ + int i; + htw_ticks_t nticks = ticks; + htw_ticks_t total_shift = 0; + htw_ticks_t residue_diff = m_timer_w[0].get_bucket_index(); + + for (i=1; i>m_wheel_shift; + total_shift += m_wheel_shift; + + if (likely(nticksm_wheel=i; + tmr->m_ticks_left = ticks - ((nticks<m_wheel=i-1; + residue_diff -= (m_timer_w[i-1].get_bucket_index()<m_ticks_left = ticks - ((m_wheel_mask<MAX_H_TIMER_WHEELS) { + return (RC_HTW_ERR_MAX_WHEELS); + } + m_num_wheels=num_wheels; + int i; + for (i=0; i (sizeof(htw_ticks_t)*8)) { + return(RC_HTW_ERR_NOT_ENOUGH_BITS); + } + m_wheel_mask = utl_mask_log2(wheel_size); + m_wheel_size = wheel_size; + return(RC_HTW_OK); +} + +RC_HTW_t CHTimerWheel::Delete(){ + int i; + for (i=0; i +#include +#include +#include +#include "pal_utl.h" +#include "mbuf.h" + + + +typedef enum { + RC_HTW_OK = 0, + RC_HTW_ERR_NO_RESOURCES = -1, + RC_HTW_ERR_TIMER_IS_ON = -2, + RC_HTW_ERR_NO_LOG2 = -3, + RC_HTW_ERR_MAX_WHEELS = -4, + RC_HTW_ERR_NOT_ENOUGH_BITS = -5, + +} RC_HTW_t; + + + + + +class CHTimerWheelLink { + +public: + CHTimerWheelLink * m_next; + CHTimerWheelLink * m_prev; + +public: + void reset(){ + m_next = 0; + m_prev = 0; + } + void set_self(){ + m_next=this; + m_prev=this; + } + + bool is_self(){ + if (m_next == this) { + return (true); + } + return (false); + } + + void append(CHTimerWheelLink * obj){ + obj->m_next = this; + obj->m_prev = m_prev; + + m_prev->m_next = obj; + m_prev = obj; + } + + void detach(void){ + #ifdef HTW_DEBUG + assert(m_next); + #endif + CHTimerWheelLink *next; + + next = m_next; + next->m_prev = m_prev; + m_prev->m_next = next; + m_next=0; + m_prev=0; + } +} ; + +typedef uint32_t htw_ticks_t; + +class CHTimerObj : public CHTimerWheelLink { + +public: + inline void reset(void){ + CHTimerWheelLink::reset(); + m_ticks_left=0; + m_wheel=0; + } + + inline bool is_running(){ + if (m_next != 0) { + return (true); + } + return (false); + } + + + void Dump(FILE *fd); + +public: + /* CACHE LINE 0*/ + htw_ticks_t m_ticks_left; /* abs ticks left */ + uint32_t m_wheel; + + uint32_t m_pad[2]; /* aging time in ticks */ +} ; + +typedef void (*htw_on_tick_cb_t)(void *userdata,CHTimerObj *tmr); + +class CHTimerOneWheel { + +public: + CHTimerOneWheel(){ + reset(); + } + + RC_HTW_t Create(uint32_t wheel_size); + + RC_HTW_t Delete(); + + inline RC_HTW_t timer_start(CHTimerObj *tmr, + htw_ticks_t ticks){ + + #ifdef HTW_DEBUG + if ( tmr->is_running() ){ + return( RC_HTW_ERR_TIMER_IS_ON); + } + #endif + + append( tmr, ticks); + return (RC_HTW_OK); + } + + RC_HTW_t timer_stop (CHTimerObj *tmr); + + inline bool check_timer_tick_cycle(){ + return (m_tick_done); + } + + + inline bool timer_tick(){ + + m_ticks++; + m_bucket_index++; + + if (m_tick_done) { + m_tick_done=false; + } + if ( m_bucket_index == m_wheel_size ) { + m_bucket_index = 0; + m_tick_done=true; + } + m_active_bucket = &m_buckets[m_bucket_index]; + return (m_tick_done); + } + + + inline CHTimerObj * pop_event(void) { + + if ( m_active_bucket->is_self() ){ + return ((CHTimerObj *)0); + } + + CHTimerWheelLink * first = m_active_bucket->m_next; + + rte_prefetch0(first->m_next); + + first->detach(); + return ((CHTimerObj *)first); + } + + + +public: + + void dump_link_list(uint32_t bucket_index, + void *userdata, + htw_on_tick_cb_t cb, + FILE *fd); + + + uint32_t get_bucket_index(void){ + return ( m_bucket_index); + } + +private: + + inline void reset(void){ + m_buckets=0; + m_active_bucket=0; + m_ticks=0; + m_wheel_size=0; + m_wheel_mask=0; + m_bucket_index=0; + m_tick_done=false; + } + + + inline void append (CHTimerObj *tmr, + uint32_t ticks) { + CHTimerWheelLink *cur; + + uint32_t cursor = ((m_bucket_index + ticks) & m_wheel_mask); + cur = &m_buckets[cursor]; + + cur->append((CHTimerWheelLink *)tmr); + } + +private: + CHTimerWheelLink * m_buckets; + CHTimerWheelLink * m_active_bucket; /* point to the current bucket m_buckets[m_bucket_index] */ + + htw_ticks_t m_ticks; + uint32_t m_wheel_size; //e.g. 256 + uint32_t m_wheel_mask; // 256-1 + uint32_t m_bucket_index; + bool m_tick_done; +}; + + + + +#define MAX_H_TIMER_WHEELS (4) + +class CHTimerWheel { + +public: + CHTimerWheel(){ + reset(); + } + + RC_HTW_t Create(uint32_t wheel_size, + uint32_t num_wheels); + + RC_HTW_t Delete(); + + inline RC_HTW_t timer_start(CHTimerObj *tmr, + htw_ticks_t ticks){ + m_total_events++; + if (likely(ticksm_ticks_left=0; + tmr->m_wheel=0; + return (m_timer_w[0].timer_start(tmr,ticks)); + } + return ( timer_start_rest(tmr, ticks)); + } + + RC_HTW_t timer_stop (CHTimerObj *tmr); + + void on_tick(void *userdata,htw_on_tick_cb_t cb); + + bool is_any_events_left(){ + return(m_total_events>0?true:false); + } + + + +private: + void reset(void); + + RC_HTW_t timer_start_rest(CHTimerObj *tmr, + htw_ticks_t ticks); + +private: + htw_ticks_t m_ticks; + uint32_t m_num_wheels; + uint32_t m_wheel_size; //e.g. 256 + uint32_t m_wheel_mask; //e.g 256-1 + uint32_t m_wheel_shift; // e.g 8 + uint64_t m_total_events; + CHTimerOneWheel m_timer_w[MAX_H_TIMER_WHEELS]; +} ; + + +#endif diff --git a/src/h_timer_w.h b/src/h_timer_w.h new file mode 100644 index 00000000..552c7423 --- /dev/null +++ b/src/h_timer_w.h @@ -0,0 +1,533 @@ +// -*- mode: c++; c-basic-offset: 4 indent-tabs-mode: nil -*- */ +// +// Copyright 2016 Juho Snellman, released under a MIT license (see +// LICENSE). +// +// A timer queue which allows events to be scheduled for execution +// at some later point. Reasons you might want to use this implementation +// instead of some other are: +// +// - A single-file C++11 implementation with no external dependencies. +// - Optimized for high occupancy rates, on the assumption that the +// utilization of the timer queue is proportional to the utilization +// of the system as a whole. When a tradeoff needs to be made +// between efficiency of one operation at a low occupancy rate and +// another operation at a high rate, we choose the latter. +// - Tries to minimize the cost of event rescheduling or cancelation, +// on the assumption that a large percentage of events will never +// be triggered. The implementation avoids unnecessary work when an +// event is rescheduled, and provides a way for the user specify a +// range of acceptable execution times instead of just an exact one. +// - Facility for limiting the number of events to execute on a +// single invocation, to allow fine grained interleaving of timer +// processing and application logic. +// - An interface that at least the author finds convenient. +// +// The exact implementation strategy is a hierarchical timer +// wheel. A timer wheel is effectively a ring buffer of linked lists +// of events, and a pointer to the ring buffer. As the time advances, +// the pointer moves forward, and any events in the ring buffer slots +// that the pointer passed will get executed. +// +// A hierarchical timer wheel layers multiple timer wheels running at +// different resolutions on top of each other. When an event is +// scheduled so far in the future than it does not fit the innermost +// (core) wheel, it instead gets scheduled on one of the outer +// wheels. On each rotation of the inner wheel, one slot's worth of +// events are promoted from the second wheel to the core. On each +// rotation of the second wheel, one slot's worth of events is +// promoted from the third wheel to the second, and so on. +// +// The basic usage is to create a single TimerWheel object and +// multiple TimerEvent or MemberTimerEvent objects. The events are +// scheduled for execution using TimerWheel::schedule() or +// TimerWheel::schedule_in_range(), or unscheduled using the event's +// cancel() method. +// +// Example usage: +// +// typedef std::function Callback; +// TimerWheel timers; +// int count = 0; +// TimerEvent timer([&count] () { ++count; }); +// +// timers.schedule(&timer, 5); +// timers.advance(4); +// assert(count == 0); +// timers.advance(1); +// assert(count == 1); +// +// timers.schedule(&timer, 5); +// timer.cancel(); +// timers.advance(4); +// assert(count == 1); +// +// To tie events to specific member functions of an object instead of +// a callback function, use MemberTimerEvent instead of TimerEvent. +// For example: +// +// class Test { +// public: +// Test() : inc_timer_(this) { +// } +// void start(TimerWheel* timers) { +// timers->schedule(&inc_timer_, 10); +// } +// void on_inc() { +// count_++; +// } +// int count() { return count_; } +// private: +// MemberTimerEvent inc_timer_; +// int count_ = 0; +// }; + +#ifndef RATAS_TIMER_WHEEL_H +#define RATAS_TIMER_WHEEL_H + +#include +#include +#include +#include +#include +#include + +typedef uint64_t tick_t; + +class TimerWheelSlot; +class TimerWheel; + +// An abstract class representing an event that can be scheduled to +// happen at some later time. +struct TimerEventInterface { +public: + // Unschedule this event. It's safe to cancel an event that is inactive. + inline void cancel(); + + // Return true iff the event is currently scheduled for execution. + bool active() const { + return slot_ != NULL; + } + + // Return the absolute tick this event is scheduled to be executed on. + tick_t scheduled_at() const { return scheduled_at_; } + +private: + TimerEventInterface(const TimerEventInterface& other) = delete; + TimerEventInterface& operator=(const TimerEventInterface& other) = delete; + friend TimerWheelSlot; + friend TimerWheel; + + + void set_scheduled_at(tick_t ts) { scheduled_at_ = ts; } + // Move the event to another slot. (It's safe for either the current + // or new slot to be NULL). + inline void relink(TimerWheelSlot* slot); + +private: + /* one CACHELINE 32 byte in 64bit processor */ + + tick_t scheduled_at_; + // The slot this event is currently in (NULL if not currently scheduled). + TimerWheelSlot* slot_ = NULL; + // The events are linked together in the slot using an internal + // doubly-linked list; this iterator does double duty as the + // linked list node for this event. + TimerEventInterface* next_ = NULL; + TimerEventInterface* prev_ = NULL; +}; + +#if 0 +// An event that takes the callback (of type CBType) to execute as +// a constructor parameter. +template +class TimerEvent : public TimerEventInterface { +public: + explicit TimerEvent(const CBType& callback) + : callback_(callback) { + } + + void execute() { + callback_(); + } + +private: + TimerEvent(const TimerEvent& other) = delete; + TimerEvent& operator=(const TimerEvent& other) = delete; + CBType callback_; +}; + +// An event that's specialized with a (static) member function of class T, +// and a dynamic instance of T. Event execution causes an invocation of the +// member function on the instance. +template +class MemberTimerEvent : public TimerEventInterface { +public: + MemberTimerEvent(T* obj) : obj_(obj) { + } + + virtual void execute () { + (obj_->*MFun)(); + } + +private: + T* obj_; +}; + +#endif + +// Purely an implementation detail. +class TimerWheelSlot { +public: + TimerWheelSlot() { + } + +private: + // Return the first event queued in this slot. + const TimerEventInterface* events() const { return events_; } + // Deque the first event from the slot, and return it. + TimerEventInterface* pop_event() { + auto event = events_; + events_ = event->next_; + if (events_) { + events_->prev_ = NULL; + } + event->next_ = NULL; + event->slot_ = NULL; + return event; + } + + TimerWheelSlot(const TimerWheelSlot& other) = delete; + TimerWheelSlot& operator=(const TimerWheelSlot& other) = delete; + friend TimerEventInterface; + friend TimerWheel; + + // Doubly linked (inferior) list of events. + TimerEventInterface* events_ = NULL; +}; + +// A TimerWheel is the entity that TimerEvents can be scheduled on +// for execution (with schedule() or schedule_in_range()), and will +// eventually be executed once the time advances far enough with the +// advance() method. + +class TimerWheel { +public: + bool Create(tick_t now = 0){ + for (int i = 0; i < NUM_LEVELS; ++i) { + now_[i] = now >> (WIDTH_BITS * i); + } + ticks_pending_ = 0; + } + void Delete(){ + } + + // Advance the TimerWheel by the specified number of ticks, and execute + // any events scheduled for execution at or before that time. The + // number of events executed can be restricted using the max_execute + // parameter. If that limit is reached, the function will return false, + // and the excess events will be processed on a subsequent call. + // + // - It is safe to cancel or schedule events from within event callbacks. + // - During the execution of the callback the observable event tick will + // be the tick it was scheduled to run on; not the tick the clock will + // be advanced to. + // - Events will happen in order; all events scheduled for tick X will + // be executed before any event scheduled for tick X+1. + // + // Delta should be non-0. The only exception is if the previous + // call to advance() returned false. + // + // advance() should not be called from an event callback. + inline bool advance(tick_t delta, + size_t max_execute=std::numeric_limits::max(), + int level = 0); + + // Schedule the event to be executed delta ticks from the current time. + // The delta must be non-0. + inline void schedule(TimerEventInterface* event, tick_t delta); + + // Schedule the event to happen at some time between start and end + // ticks from the current time. The actual time will be determined + // by the TimerWheel to minimize rescheduling and promotion overhead. + // Both start and end must be non-0, and the end must be greater than + // the start. + inline void schedule_in_range(TimerEventInterface* event, + tick_t start, tick_t end); + + // Return the current tick value. Note that if the time increases + // by multiple ticks during a single call to advance(), during the + // execution of the event callback now() will return the tick that + // the event was scheduled to run on. + tick_t now() const { return now_[0]; } + + // Return the number of ticks remaining until the next event will get + // executed. If the max parameter is passed, that will be the maximum + // tick value that gets returned. The max parameter's value will also + // be returned if no events have been scheduled. + // + // Will return 0 if the wheel still has unprocessed events from the + // previous call to advance(). + inline tick_t ticks_to_next_event(tick_t max = std::numeric_limits::max(), + int level = 0); + +private: + TimerWheel(const TimerWheel& other) = delete; + TimerWheel& operator=(const TimerWheel& other) = delete; + + // This handles the actual work of executing event callbacks and + // recursing to the outer wheels. + inline bool process_current_slot(tick_t now, size_t max_execute, int level); + + static const int WIDTH_BITS = 8; + static const int NUM_LEVELS = (64 + WIDTH_BITS - 1) / WIDTH_BITS; + static const int MAX_LEVEL = NUM_LEVELS - 1; + static const int NUM_SLOTS = 1 << WIDTH_BITS; + // A bitmask for looking at just the bits in the timestamp relevant to + // this wheel. + static const int MASK = (NUM_SLOTS - 1); + + // The current timestamp for this wheel. This will be right-shifted + // such that each slot is separated by exactly one tick even on + // the outermost wheels. + tick_t now_[NUM_LEVELS]; + // We've done a partial tick advance. This is how many ticks remain + // unprocessed. + tick_t ticks_pending_; + TimerWheelSlot slots_[NUM_LEVELS][NUM_SLOTS]; +}; + +// Implementation + +inline void TimerEventInterface::relink(TimerWheelSlot* new_slot) { + if (new_slot == slot_) { + return; + } + + // Unlink from old location. + if (slot_) { + auto prev = prev_; + auto next = next_; + if (next) { + next->prev_ = prev; + } + if (prev) { + prev->next_ = next; + } else { + // Must be at head of slot. Move the next item to the head. + slot_->events_ = next; + } + } + + // Insert in new slot. + { + if (new_slot) { + auto old = new_slot->events_; + next_ = old; + if (old) { + old->prev_ = this; + } + new_slot->events_ = this; + } else { + next_ = NULL; + } + prev_ = NULL; + } + slot_ = new_slot; +} + +inline void TimerEventInterface::cancel() { + // It's ok to cancel a event that's not scheduled. + if (!slot_) { + return; + } + + relink(NULL); +} + +inline bool TimerWheel::advance(tick_t delta, size_t max_events, int level) { + if (ticks_pending_) { + if (level == 0) { + // Continue collecting a backlog of ticks to process if + // we're called with non-zero deltas. + ticks_pending_ += delta; + } + // We only partially processed the last tick. Process the + // current slot, rather incrementing like advance() normally + // does. + tick_t now = now_[level]; + if (!process_current_slot(now, max_events, level)) { + // Outer layers are still not done, propagate that information + // back up. + return false; + } + if (level == 0) { + // The core wheel has been fully processed. We can now close + // down the partial tick and pretend that we've just been + // called with a delta containing both the new and original + // amounts. + delta = (ticks_pending_ - 1); + ticks_pending_ = 0; + } else { + return true; + } + } else { + // Zero deltas are only ok when in the middle of a partially + // processed tick. + assert(delta > 0); + } + + while (delta--) { + tick_t now = ++now_[level]; + if (!process_current_slot(now, max_events, level)) { + ticks_pending_ = (delta + 1); + return false; + } + } + return true; +} + +inline bool TimerWheel::process_current_slot(tick_t now, size_t max_events, int level) { + size_t slot_index = now & MASK; + auto slot = &slots_[level][slot_index]; + if (slot_index == 0 && level < MAX_LEVEL) { + if (!advance(1, max_events, level + 1)) { + return false; + } + } + while (slot->events()) { + auto event = slot->pop_event(); + if (level > 0) { + assert((now_[0] & MASK) == 0); + if (now_[0] >= event->scheduled_at()) { + event->execute(); + if (!--max_events) { + return false; + } + } else { + // There's a case to be made that promotion should + // also count as work done. And that would simplify + // this code since the max_events manipulation could + // move to the top of the loop. But it's an order of + // magnitude more expensive to execute a typical + // callback, and promotions will naturally clump while + // events triggering won't. + schedule(event, + event->scheduled_at() - now_[0]); + } + } else { + event->execute(); + if (!--max_events) { + return false; + } + } + } + return true; +} + +inline void TimerWheel::schedule(TimerEventInterface* event, tick_t delta) { + event->set_scheduled_at(now_[0] + delta); + + int level = 0; + while (delta >= NUM_SLOTS) { + delta = (delta + (now_[level] & MASK)) >> WIDTH_BITS; + ++level; + } + + size_t slot_index = (now_[level] + delta) & MASK; + auto slot = &slots_[level][slot_index]; + event->relink(slot); +} + +inline void TimerWheel::schedule_in_range(TimerEventInterface* event, + tick_t start, tick_t end) { + assert(end > start); + if (event->active()) { + auto current = event->scheduled_at() - now_[0]; + // Event is already scheduled to happen in this range. Instead + // of always using the old slot, we could check compute the + // new slot and switch iff it's aligned better than the old one. + // But it seems hard to believe that could be worthwhile. + if (current >= start && current <= end) { + return; + } + } + + // Zero as many bits (in WIDTH_BITS chunks) as possible + // from "end" while still keeping the output in the + // right range. + tick_t mask = ~0; + while ((start & mask) != (end & mask)) { + mask = (mask << WIDTH_BITS); + } + + tick_t delta = end & (mask >> WIDTH_BITS); + + schedule(event, delta); +} + +inline tick_t TimerWheel::ticks_to_next_event(tick_t max, int level) { + if (ticks_pending_) { + return 0; + } + // The actual current time (not the bitshifted time) + tick_t now = now_[0]; + + // Smallest tick (relative to now) we've found. + tick_t min = max; + for (int i = 0; i < NUM_SLOTS; ++i) { + // Note: Unlike the uses of "now", slot index calculations really + // need to use now_. + auto slot_index = (now_[level] + 1 + i) & MASK; + // We've reached slot 0. In normal scheduling this would + // mean advancing the next wheel and promoting or executing + // those events. So we need to look in that slot too + // before proceeding with the rest of this wheel. But we + // can't just accept those results outright, we need to + // check the best result there against the next slot on + // this wheel. + if (slot_index == 0 && level < MAX_LEVEL) { + // Exception: If we're in the core wheel, and slot 0 is + // not empty, there's no point in looking in the outer wheel. + // It's guaranteed that the events actually in slot 0 will be + // executed no later than anything in the outer wheel. + if (level > 0 || !slots_[level][slot_index].events()) { + auto up_slot_index = (now_[level + 1] + 1) & MASK; + const auto& slot = slots_[level + 1][up_slot_index]; + for (auto event = slot.events(); event != NULL; + event = event->next_) { + min = std::min(min, event->scheduled_at() - now); + } + } + } + bool found = false; + const auto& slot = slots_[level][slot_index]; + for (auto event = slot.events(); event != NULL; + event = event->next_) { + min = std::min(min, event->scheduled_at() - now); + // In the core wheel all the events in a slot are guaranteed to + // run at the same time, so it's enough to just look at the first + // one. + if (level == 0) { + return min; + } else { + found = true; + } + } + if (found) { + return min; + } + } + + // Nothing found on this wheel, try the next one (unless the wheel can't + // possibly contain an event scheduled earlier than "max"). + if (level < MAX_LEVEL && + (max >> (WIDTH_BITS * level + 1)) > 0) { + return ticks_to_next_event(max, level + 1); + } + + return max; +} + +#endif // RATAS_TIMER_WHEEL_H + diff --git a/src/nat_check.h b/src/nat_check.h index a8424ae6..538cf888 100755 --- a/src/nat_check.h +++ b/src/nat_check.h @@ -152,6 +152,7 @@ struct CGenNodeNatInfo : public CGenNodeMsgBase { uint32_t m_pad3; #endif CNatFlowInfo m_data[MAX_NAT_FLOW_INFO]; + uint64_t m_pad4[8]; public: CNatFlowInfo * get_next_msg() { @@ -178,6 +179,7 @@ struct CGenNodeLatencyPktInfo : public CGenNodeMsgBase { struct rte_mbuf *m_pkt; uint32_t m_pad4[MAX_PKT_MSG_INFO]; + uint64_t m_pad5[8]; }; diff --git a/src/pal/linux/rte_prefetch.h b/src/pal/linux/rte_prefetch.h new file mode 100644 index 00000000..cbc38964 --- /dev/null +++ b/src/pal/linux/rte_prefetch.h @@ -0,0 +1,30 @@ +#ifndef _RTE_PREFETCH_X86_64_H_ +#define _RTE_PREFETCH_X86_64_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +/* stubs */ + +static inline void rte_prefetch0(const volatile void *p) +{ +} + +static inline void rte_prefetch1(const volatile void *p) +{ +} + +static inline void rte_prefetch2(const volatile void *p) +{ +} + +static inline void rte_prefetch_non_temporal(const volatile void *p) +{ +} + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/src/stateless/dp/trex_stream_node.h b/src/stateless/dp/trex_stream_node.h index bc7be057..b74e0f62 100644 --- a/src/stateless/dp/trex_stream_node.h +++ b/src/stateless/dp/trex_stream_node.h @@ -42,6 +42,10 @@ public: uint8_t m_pad_end[104]; + /* CACHE_LINE */ + uint64_t m_pad3[8]; + + public: void free_command(); @@ -135,6 +139,9 @@ private: /* pad to match the size of CGenNode */ uint8_t m_pad_end[20]; + /* CACHE_LINE */ + uint64_t m_pad3[8]; + public: @@ -648,6 +655,9 @@ private: /* pad to match the size of CGenNode */ uint8_t m_pad_end[11]; + /* CACHE_LINE */ + uint64_t m_pad3[8]; + } __rte_cache_aligned; diff --git a/src/stw_timer.cpp b/src/stw_timer.cpp new file mode 100644 index 00000000..3146c9a5 --- /dev/null +++ b/src/stw_timer.cpp @@ -0,0 +1,204 @@ +#include +#include +#include +#include "stw_timer.h" + +/* todo : + +1. add jitter support +2. in case ticks take too much time add a quata and keep the time in the current bucket then speed up + +hhaim +*/ + + +void CTimerObj::Dump(FILE *fd){ + + fprintf(fd,"m_rotation_count :%lu \n", (ulong)m_rotation_count); + fprintf(fd,"m_last_update_tick :%lu \n", (ulong)m_last_update_tick); + fprintf(fd,"m_aging_ticks :%lu \n", (ulong)m_aging_ticks); +} + + +void CTimerWheelBucket::dump_link_list(void *userdata,tw_on_tick_cb_t cb,FILE *fd){ + + + CTimerWheelLink *bucket, *next; + CTimerObj *tmr; + + + bucket = m_active_bucket; + + tmr = (CTimerObj *)bucket->stw_next; + bool found=false; + if ((CTimerWheelLink *)tmr != bucket) { + fprintf(fd,"[%lu,\n",(ulong)m_bucket_index); + found=true; + } + + while( (CTimerWheelLink *)tmr != bucket) { + + next = (CTimerWheelLink *)tmr->m_links.stw_next; + + tmr->Dump(fd); + cb(userdata,tmr); + + tmr = (CTimerObj *)next; + } + if (found){ + fprintf(fd,"]\n"); + } +} + + +bool CTimerWheelBucket::do_tick(void *userdata, + tw_on_tick_cb_t cb, + int32_t limit){ + + + CTimerObj * tmr; + int cnt=0; + while ( true ) { + tmr = timer_tick_get_next(); + if (!tmr) { + break; + } + cb(userdata,tmr); + cnt++; + if (cnt>limit && (limit>0)) { + return(false); + } + } + timer_tick(); + return(true); +} + + +void CTimerWheelBucket::timer_stats_dump(FILE *fd){ + fprintf(fd,"wheel_size :%lu \n", (ulong)m_wheel_size); + fprintf(fd,"ticks :%lu \n", (ulong)m_ticks); + fprintf(fd,"bucket_index :%lu \n", (ulong)m_bucket_index); + fprintf(fd,"timer_active :%lu \n", (ulong)m_timer_active); + fprintf(fd,"timer_expired :%lu \n", (ulong)m_timer_expired); + fprintf(fd,"timer_hiwater_mark :%lu \n", (ulong)m_timer_hiwater_mark); + fprintf(fd,"timer_starts :%lu \n", (ulong)m_timer_starts); + fprintf(fd,"timer_cancelled :%lu \n", (ulong)m_timer_cancelled); + fprintf(fd,"m_timer_restart :%lu \n", (ulong)m_timer_restart); + +} + + +RC_STW_t CTimerWheelBucket::timer_stop (CTimerObj *tmr) +{ + CTimerWheelLink *next, *prev; + +#ifdef TW_DEBUG + + if (this == 0) { + return (RC_STW_NULL_WHEEL); + } + + if (tmr == 0) { + return (RC_STW_NULL_TMR); + } + + if (m_magic_tag != MAGIC_TAG ) { + return (RC_STW_INVALID_WHEEL); + } + +#endif + + next = tmr->m_links.stw_next; + if (next) { + prev = tmr->m_links.stw_prev; + next->stw_prev = prev; + prev->stw_next = next; + tmr->m_links.stw_next = 0; /* 0 == tmr is free */ + tmr->m_links.stw_prev = 0; + + /* + * stats bookkeeping + */ + m_timer_active--; + m_timer_cancelled++; + } + return (RC_STW_OK); +} + +RC_STW_t CTimerWheelBucket::Delete() { + uint32_t j; + CTimerWheelLink *spoke; + + CTimerObj *tmr; + if (this == 0) { + return (RC_STW_NULL_WHEEL); + } + + if (m_magic_tag != MAGIC_TAG ) { + return (RC_STW_INVALID_WHEEL); + } + + for (j = 0; j < m_wheel_size; j++) { + spoke = &m_buckets[j]; + + tmr = (CTimerObj *)spoke->stw_next; + + while ( (CTimerWheelLink *)tmr != spoke) { + timer_stop(tmr); + tmr = (CTimerObj *)spoke->stw_next; + } /* end while */ + + } /* end for */ + + /* + * clear the magic so we do not mistakenly access this wheel + */ + m_magic_tag = 0; + + /* + * now free the wheel structures + */ + free(m_buckets); + m_buckets=0; + + return (RC_STW_OK); +} + +RC_STW_t CTimerWheelBucket::Create(uint32_t wheel_size){ + uint32_t j; + CTimerWheelLink *bucket; + + if (wheel_size < STW_MIN_WHEEL_SIZE || wheel_size > STW_MAX_WHEEL_SIZE) { + return (RC_STW_INVALID_WHEEL_SIZE); + } + + m_buckets = (CTimerWheelLink *)malloc(wheel_size * sizeof(CTimerWheelLink)); + if (m_buckets == 0) { + return (RC_STW_NO_RESOURCES); + } + + m_magic_tag = MAGIC_TAG; + m_ticks = 0; + m_bucket_index = 0; + m_wheel_size = wheel_size; + + m_timer_hiwater_mark = 0; + m_timer_active = 0; + m_timer_cancelled=0; + m_timer_expired=0; + m_timer_starts=0; + m_timer_restart=0; + + bucket = &m_buckets[0]; + m_active_bucket=bucket; + m_active_tick_timer = m_active_bucket; + /* link list point to itself */ + for (j = 0; j < wheel_size; j++) { + bucket->stw_next = bucket; + bucket->stw_prev = bucket; + bucket++; + } + return (RC_STW_OK); +} + + diff --git a/src/stw_timer.h b/src/stw_timer.h new file mode 100644 index 00000000..0e2c146f --- /dev/null +++ b/src/stw_timer.h @@ -0,0 +1,381 @@ + /*------------------------------------------------------------------ + + * Februrary 2002, Bo Berry + * hhaim- 2013 + base on Februrary 2002, Bo Berry + * + * Copyright (c) 2005-2009 by Cisco Systems, Inc. + * All rights reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom + * the Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + + *------------------------------------------------------------------ + */ + +#ifndef __STW_TIMER_H__ +#define __STW_TIMER_H__ + +#undef TW_DEBUG + +#define MAGIC_TAG ( 0xDEADBEEF ) + +#include +#include +#include "pal_utl.h" +#include + + + +typedef enum { + RC_STW_OK = 0, + RC_STW_NULL_NAME, + RC_STW_NULL_FV, + RC_STW_NULL_WHEEL, + RC_STW_NULL_TMR, + RC_STW_TIMER_IS_ON, + RC_STW_INVALID_WHEEL, + RC_STW_INVALID_WHEEL_SIZE, + RC_STW_INVALID_GRANULARITY, + RC_STW_NO_RESOURCES, +} RC_STW_t; + + + +#define STW_MIN_WHEEL_SIZE ( 8 ) +#define STW_MAX_WHEEL_SIZE ( 100000 ) + + + +class CTimerWheelLink { +public: + CTimerWheelLink *stw_next; + CTimerWheelLink *stw_prev; +} ; + +class CTimerObj { + +public: + inline void reset(void){ + prepare (); + m_rotation_count=0; + m_last_update_tick=0; + m_aging_ticks=0; + } + + inline bool is_running(){ + if (m_links.stw_next != 0) { + return (true); + } + return (false); + } + + inline void prepare () { + m_links.stw_next = 0; + m_links.stw_prev = 0; + } + + inline uint32_t restart_aging_ticks(uint32_t cur_ticks){ + uint32_t dticks =(cur_ticks - m_last_update_tick ); + return ( m_aging_ticks -dticks ); + } + + void Dump(FILE *fd); +public: + CTimerWheelLink m_links; + uint32_t m_rotation_count; + uint32_t m_last_update_tick; /* cur timer tick the timer was set/restart */ + uint32_t m_aging_ticks; /* aging time in ticks */ + uint32_t m_pad; +} ; + + +typedef void (*tw_on_tick_cb_t)(void *userdata,CTimerObj *tmr); + +class CTimerWheelBucket { + +public: + + friend class CTimerWheelBucketUT; + + RC_STW_t Create(uint32_t wheel_size); + + RC_STW_t Delete(); + + inline RC_STW_t timer_restart(CTimerObj *tmr){ + + if ( tmr->is_running() ){ + tmr->m_last_update_tick = m_ticks;/* update the time with current tick */ + + #ifdef TW_DEBUG + m_timer_restart++ ; + #endif + } + return (RC_STW_OK); + } + + + + inline RC_STW_t timer_restart(CTimerObj *tmr, + uint32_t ticks){ + + if ( tmr->is_running() ){ + if ( tmr->restart_aging_ticks(m_ticks) < ticks) { + tmr->m_last_update_tick = m_ticks; + tmr->m_aging_ticks =ticks; + + #ifdef TW_DEBUG + m_timer_restart++ ; + #endif + return (RC_STW_OK); + + }else{ + timer_stop (tmr); + } + } + return (timer_start(tmr,ticks)); + } + + inline RC_STW_t timer_start(CTimerObj *tmr, + uint32_t ticks){ + + if ( tmr->is_running() ){ + return( RC_STW_TIMER_IS_ON); + } + + #ifdef TW_DEBUG + CTimerWheelLink *next, *prev; + + if (this == 0) { + return (RC_STW_NULL_WHEEL); + } + + if (tmr == 0) { + return (RC_STW_NULL_TMR); + } + + if (m_magic_tag != MAGIC_TAG) { + return (RC_STW_INVALID_WHEEL); + } + + /* + * First check to see if it is already running. If so, remove + * it from the wheel. We don't bother cleaning up the fields + * because we will be setting them below. + */ + next = tmr->m_links.stw_next; + if (next) { + prev = tmr->m_links.stw_prev; + next->stw_prev = prev; + prev->stw_next = next; + + /* + * stats book keeping + */ + m_timer_active--; + } + #endif + + tmr->m_last_update_tick = m_ticks; /* save the tick */ + tmr->m_aging_ticks = ticks; /* set the original aging tick */ + tmr_enqueue( tmr, ticks); + + #ifdef TW_DEBUG + m_timer_starts++; + m_timer_active++; + if (m_timer_active > m_timer_hiwater_mark) { + m_timer_hiwater_mark = m_timer_active; + } + #endif + + return (RC_STW_OK); + } + + + RC_STW_t timer_stop (CTimerObj *tmr); + + + inline void timer_tick(){ + + #ifdef TW_DEBUG + if ((this == 0) || (m_magic_tag != MAGIC_TAG)) { + return; + } + /* + * keep track of rolling the wheel + */ + #endif + + m_ticks++; + + m_bucket_index++; + + if ( m_bucket_index == m_wheel_size ) { + m_bucket_index=0; + } + m_active_bucket = &m_buckets[m_bucket_index]; + m_active_tick_timer = m_active_bucket; + } + + bool do_tick(void *userdata,tw_on_tick_cb_t cb,int32_t limit=0); + + + void dump_link_list(void *userdata,tw_on_tick_cb_t cb,FILE *fd) ; + + + inline CTimerObj * timer_tick_get_next(void) { + + if ( m_active_tick_timer == NULL ){ + return ((CTimerObj *)0); + } + + CTimerWheelLink *bucket, *next, *prev; + CTimerObj *tmr; + + #ifdef TW_DEBUG + if ((this == 0) || (m_magic_tag != MAGIC_TAG)) { + return (CTimerObj *)0; + } + #endif + + bucket = m_active_bucket; /* point the last/first */ + tmr = (CTimerObj *)m_active_tick_timer->stw_next; + + while( (CTimerWheelLink *)tmr != bucket) { + + next = (CTimerWheelLink *)tmr->m_links.stw_next; + rte_prefetch0(next); + + /* + * if the timer is a long one and requires one or more rotations + * decrement rotation count and leave for next turn. + */ + if (tmr->m_rotation_count != 0) { + tmr->m_rotation_count--; + } else { + + uint32_t reschedule = tmr->restart_aging_ticks(m_ticks); + + if ( reschedule == 0){ + /* no reschedule */ + prev = (CTimerWheelLink *)tmr->m_links.stw_prev; + + prev->stw_next = next; + next->stw_prev = prev; + + tmr->m_links.stw_next = 0; + tmr->m_links.stw_prev = 0; + + #ifdef TW_DEBUG + /* book keeping */ + m_timer_active--; + m_timer_expired++; + #endif + + m_active_tick_timer = next->stw_prev; + return(tmr); + }else{ + if ( (reschedule % m_wheel_size ==0)) { + /* same spoke */ + tmr->m_rotation_count = (reschedule / m_wheel_size)-1; + }else{ + /* diff spoke */ + + prev = (CTimerWheelLink *)tmr->m_links.stw_prev; + + prev->stw_next = next; + next->stw_prev = prev; + + tmr->m_links.stw_next = 0; + tmr->m_links.stw_prev = 0; + tmr_enqueue (tmr, reschedule); + } + + } + } + + tmr = (CTimerObj *)next; + } + m_active_tick_timer = NULL; /* point to the bucket */ + return (CTimerObj *)0; + } + +public: + void timer_stats_dump(FILE *fd); + + uint32_t get_ticks(){ + return (m_ticks); + } + +private: + + inline void tmr_enqueue (CTimerObj *tmr, + uint32_t ticks) { + CTimerWheelLink *prev, *spoke; + + uint32_t cursor; + + if (ticks >= m_wheel_size) { + tmr->m_rotation_count = (ticks / m_wheel_size); + }else{ + tmr->m_rotation_count=0; + } + cursor = ((m_bucket_index + ticks) % m_wheel_size); + spoke = &m_buckets[cursor]; + prev = spoke->stw_prev; + tmr->m_links.stw_next = spoke; + tmr->m_links.stw_prev = prev; + + prev->stw_next = (CTimerWheelLink *)tmr; + spoke->stw_prev = (CTimerWheelLink *)tmr; + } + + + +private: + CTimerWheelLink * m_buckets; + CTimerWheelLink * m_active_bucket; /* point to the current bucket m_buckets[m_bucket_index] */ + CTimerWheelLink * m_active_tick_timer; /* interator of current tick, could be NULL in case we finish scanning the line */ + + + uint32_t m_ticks; + uint32_t m_magic_tag; + + uint32_t m_wheel_size; + uint32_t m_bucket_index; + +protected: + /* stats */ + uint32_t m_timer_hiwater_mark; + uint32_t m_timer_active; + uint32_t m_timer_cancelled; + uint32_t m_timer_expired; + uint32_t m_timer_starts; + uint32_t m_timer_restart; +}; + + + + + +#endif /* __STW_TIMER_H__ */ + + diff --git a/src/utl_ipg_bucket.h b/src/utl_ipg_bucket.h new file mode 100644 index 00000000..40108c98 --- /dev/null +++ b/src/utl_ipg_bucket.h @@ -0,0 +1,68 @@ +#ifndef IPG_BUCKET_H +#define IPG_BUCKET_H + +/* + Hanoh Haim + Cisco Systems, Inc. +*/ + +/* +Copyright (c) 2015-2015 Cisco Systems, Inc. + +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. +*/ + + +class CCalcIpgDiff { + +public: + CCalcIpgDiff(double bucket_is_sec){ + m_acc=0; + m_bucket_is_sec=bucket_is_sec; + m_cnt=0; + } + + uint32_t do_calc(double ipg_sec){ + uint32_t res; + double d_residue=(m_acc+ipg_sec); + double d_buckets = (d_residue/m_bucket_is_sec); + if (d_buckets< 1.0) { + m_acc+=ipg_sec; + m_cnt++; + if (m_cnt>30) { + m_cnt=0; /* move at least 1 bucket after 20 packets not to create Infinite loop in timer wheel*/ + return(1); + } + return(0); + } + m_cnt=0; + if (d_buckets>(double)UINT32_MAX) { + d_buckets=(double)UINT32_MAX; + } + res=((uint32_t)d_buckets); + m_acc=(d_residue)-m_bucket_is_sec*(double)res; + return (res); + } + +private: + + double m_acc; + double m_bucket_is_sec; + uint8_t m_cnt; + +}; + + + + +#endif -- cgit 1.2.3-korg