diff options
| -rw-r--r-- | .gitignore | 10 | ||||
| -rw-r--r-- | scripts/cap2/imix_64_fast.yaml | 28 | ||||
| -rwxr-xr-x | scripts/exp/imix-0-ex.erf | bin | 68104 -> 67928 bytes | |||
| -rw-r--r-- | scripts/exp/imix-0.erf | bin | 68104 -> 67928 bytes | |||
| -rw-r--r-- | scripts/exp/imix_64_fast-0-ex.erf | bin | 0 -> 13288 bytes | |||
| -rwxr-xr-x | scripts/exp/imix_v6-0-ex.erf | bin | 70928 -> 70720 bytes | |||
| -rw-r--r-- | scripts/exp/imix_v6-0.erf | bin | 70928 -> 70720 bytes | |||
| -rwxr-xr-x | scripts/exp/ipv4_vlan-0-ex.erf | bin | 10648 -> 10560 bytes | |||
| -rw-r--r-- | scripts/exp/ipv4_vlan-0.erf | bin | 10648 -> 10560 bytes | |||
| -rwxr-xr-x | scripts/exp/ipv6-0-ex.erf | bin | 13552 -> 13440 bytes | |||
| -rw-r--r-- | scripts/exp/ipv6-0.erf | bin | 13552 -> 13440 bytes | |||
| -rwxr-xr-x | scripts/exp/ipv6_vlan-0-ex.erf | bin | 13552 -> 13440 bytes | |||
| -rw-r--r-- | scripts/exp/ipv6_vlan-0.erf | bin | 13552 -> 13440 bytes | |||
| -rw-r--r-- | scripts/exp/limit_multi_pkt-0.erf | bin | 30944 -> 30944 bytes | |||
| -rwxr-xr-x | scripts/exp/limit_single_pkt-0-ex.erf | bin | 6688 -> 6512 bytes | |||
| -rw-r--r-- | scripts/exp/limit_single_pkt-0.erf | bin | 6688 -> 6512 bytes | |||
| -rwxr-xr-x | src/bp_gtest.cpp | 16 | ||||
| -rwxr-xr-x | src/bp_sim.cpp | 77 | ||||
| -rwxr-xr-x | src/bp_sim.h | 22 | ||||
| -rw-r--r-- | src/gtest/bp_timer_gtest.cpp | 61 | ||||
| -rw-r--r-- | src/h_timer.cpp | 44 | ||||
| -rw-r--r-- | src/h_timer.h | 68 | ||||
| -rw-r--r-- | src/h_timer_w.h | 533 |
23 files changed, 293 insertions, 566 deletions
@@ -80,6 +80,16 @@ scripts/exp/udp_64B_vm_mask5.pcap scripts/exp/udp_64B_vm_mask6.pcap scripts/exp/stl_vm_enable0_cache_10-0.erf scripts/exp/stl_vm_enable1_cache_500-0.erf +scripts/exp/imix-0.erf +scripts/exp/imix_v6-0.erf +scripts/exp/ipv4_vlan-0.erf +scripts/exp/ipv6-0.erf +scripts/exp/ipv6_vlan-0.erf +scripts/exp/limit_multi_pkt-0.erf +scripts/exp/limit_single_pkt-0.erf +scripts/exp/imix_64_fast-0.erf +scripts/exp/pcap_mode2-0.erf + diff --git a/scripts/cap2/imix_64_fast.yaml b/scripts/cap2/imix_64_fast.yaml new file mode 100644 index 00000000..f259381c --- /dev/null +++ b/scripts/cap2/imix_64_fast.yaml @@ -0,0 +1,28 @@ +# +# Simple IMIX test 64B +# +- duration : 0.0001 + 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] +# +# the templates are duplicated in purpose , to utilized all DRAM BW and get better performance, we should do it automaticly +# but for now it like this , you should have at least 8 +# + cap_info : + - name: cap2/udp_64B.pcap + cps : 1000000.0 + ipg : 10000 + rtt : 10000 + w : 1 + limit : 50 + diff --git a/scripts/exp/imix-0-ex.erf b/scripts/exp/imix-0-ex.erf Binary files differindex 4f6d3d94..6f5f4f07 100755 --- a/scripts/exp/imix-0-ex.erf +++ b/scripts/exp/imix-0-ex.erf diff --git a/scripts/exp/imix-0.erf b/scripts/exp/imix-0.erf Binary files differindex 4f6d3d94..6f5f4f07 100644 --- a/scripts/exp/imix-0.erf +++ b/scripts/exp/imix-0.erf diff --git a/scripts/exp/imix_64_fast-0-ex.erf b/scripts/exp/imix_64_fast-0-ex.erf Binary files differnew file mode 100644 index 00000000..bc8bc1cc --- /dev/null +++ b/scripts/exp/imix_64_fast-0-ex.erf diff --git a/scripts/exp/imix_v6-0-ex.erf b/scripts/exp/imix_v6-0-ex.erf Binary files differindex 2dd16e11..d52d8541 100755 --- a/scripts/exp/imix_v6-0-ex.erf +++ b/scripts/exp/imix_v6-0-ex.erf diff --git a/scripts/exp/imix_v6-0.erf b/scripts/exp/imix_v6-0.erf Binary files differindex 2dd16e11..d52d8541 100644 --- a/scripts/exp/imix_v6-0.erf +++ b/scripts/exp/imix_v6-0.erf diff --git a/scripts/exp/ipv4_vlan-0-ex.erf b/scripts/exp/ipv4_vlan-0-ex.erf Binary files differindex 6f75b99b..435d8c32 100755 --- a/scripts/exp/ipv4_vlan-0-ex.erf +++ b/scripts/exp/ipv4_vlan-0-ex.erf diff --git a/scripts/exp/ipv4_vlan-0.erf b/scripts/exp/ipv4_vlan-0.erf Binary files differindex 6f75b99b..435d8c32 100644 --- a/scripts/exp/ipv4_vlan-0.erf +++ b/scripts/exp/ipv4_vlan-0.erf diff --git a/scripts/exp/ipv6-0-ex.erf b/scripts/exp/ipv6-0-ex.erf Binary files differindex 8293b109..d50f1704 100755 --- a/scripts/exp/ipv6-0-ex.erf +++ b/scripts/exp/ipv6-0-ex.erf diff --git a/scripts/exp/ipv6-0.erf b/scripts/exp/ipv6-0.erf Binary files differindex 8293b109..d50f1704 100644 --- a/scripts/exp/ipv6-0.erf +++ b/scripts/exp/ipv6-0.erf diff --git a/scripts/exp/ipv6_vlan-0-ex.erf b/scripts/exp/ipv6_vlan-0-ex.erf Binary files differindex 5ed0b866..8ca5f09b 100755 --- a/scripts/exp/ipv6_vlan-0-ex.erf +++ b/scripts/exp/ipv6_vlan-0-ex.erf diff --git a/scripts/exp/ipv6_vlan-0.erf b/scripts/exp/ipv6_vlan-0.erf Binary files differindex 5ed0b866..8ca5f09b 100644 --- a/scripts/exp/ipv6_vlan-0.erf +++ b/scripts/exp/ipv6_vlan-0.erf diff --git a/scripts/exp/limit_multi_pkt-0.erf b/scripts/exp/limit_multi_pkt-0.erf Binary files differindex b6487e6f..4cb69891 100644 --- a/scripts/exp/limit_multi_pkt-0.erf +++ b/scripts/exp/limit_multi_pkt-0.erf diff --git a/scripts/exp/limit_single_pkt-0-ex.erf b/scripts/exp/limit_single_pkt-0-ex.erf Binary files differindex e2725b9e..344a25d0 100755 --- a/scripts/exp/limit_single_pkt-0-ex.erf +++ b/scripts/exp/limit_single_pkt-0-ex.erf diff --git a/scripts/exp/limit_single_pkt-0.erf b/scripts/exp/limit_single_pkt-0.erf Binary files differindex e2725b9e..344a25d0 100644 --- a/scripts/exp/limit_single_pkt-0.erf +++ b/scripts/exp/limit_single_pkt-0.erf diff --git a/src/bp_gtest.cpp b/src/bp_gtest.cpp index 87f3f7ca..4c04dde9 100755 --- a/src/bp_gtest.cpp +++ b/src/bp_gtest.cpp @@ -263,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; @@ -273,7 +273,7 @@ TEST_F(basic, limit_single_pkt) { po->out_file ="exp/limit_multi_pkt"; bool res=t1.init(); EXPECT_EQ_UINT32(1, res?1:0)<< "pass"; -} */ +} TEST_F(basic, imix) { @@ -287,6 +287,18 @@ TEST_F(basic, imix) { EXPECT_EQ_UINT32(1, res?1:0)<< "pass"; } +TEST_F(basic, imix_fast) { + + CTestBasic t1; + CParserOption * po =&CGlobalInfo::m_options; + po->preview.setVMode(3); + po->preview.setFileWrite(true); + po->cfg_file ="cap2/imix_64_fast.yaml"; + po->out_file ="exp/imix_64_fast"; + bool res=t1.init(); + EXPECT_EQ_UINT32(1, res?1:0)<< "pass"; +} + TEST_F(basic, dns) { diff --git a/src/bp_sim.cpp b/src/bp_sim.cpp index 0725a437..72eb91ba 100755 --- a/src/bp_sim.cpp +++ b/src/bp_sim.cpp @@ -3475,8 +3475,12 @@ bool CFlowGenListPerThread::Create(uint32_t thread_id, 0 , socket_id); - m_tw.Create(TW_BUCKETS,3); - + RC_HTW_t tw_res=m_tw.Create(TW_BUCKETS,3); + if (tw_res != RC_HTW_OK){ + CHTimerWheelErrorStr err(tw_res); + printf("ERROR %-30s - %s \n",err.get_str(),err.get_help_str()); + exit(1); + } m_node_gen.Create(this); m_flow_id_to_node_lookup.Create(); @@ -3542,19 +3546,6 @@ FORCE_NO_INLINE void CFlowGenListPerThread::handler_defer_job(CGenNode *p){ } } -FORCE_NO_INLINE void CFlowGenListPerThread::handler_defer_job_flush(void){ - /* flush the pending job of free ports */ - if (m_tcp_dpc) { - handler_defer_job((CGenNode *)m_tcp_dpc); - free_node((CGenNode *)m_tcp_dpc); - m_tcp_dpc=0; - } - if (m_udp_dpc) { - handler_defer_job((CGenNode *)m_udp_dpc); - free_node((CGenNode *)m_udp_dpc); - m_udp_dpc=0; - } -} void CFlowGenListPerThread::defer_client_port_free(bool is_tcp, @@ -3767,7 +3758,10 @@ template<bool TEARDOWN> inline void CFlowGenListPerThread::on_flow_tick(CGenNode *node){ #ifdef TREX_SIM - node->m_time=m_cur_time_sec; + /* for sim, we need to update the node from tick time*/ + if ( likely (!node->is_repeat_flow() ) ){ + node->m_time=m_cur_time_sec; + } #endif #ifdef _DEBUG m_node_gen.update_stats(node); @@ -3777,22 +3771,22 @@ inline void CFlowGenListPerThread::on_flow_tick(CGenNode *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{ + 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); + reschedule_flow(node); }else{ - free_last_flow_node( node); + free_last_flow_node(node); } }else{ - m_tw.timer_start(&node->m_tmr,node->update_next_pkt_in_flow_tw() ); + /* need to update both accurate time and bucket time in this case update_next_pkt_in_flow_both() for reschedule to be accurate */ + m_tw.timer_start(&node->m_tmr,node->update_next_pkt_in_flow_both() ); } } } @@ -3809,6 +3803,19 @@ inline void CFlowGenListPerThread::on_flow_tick(CGenNode *node){ #define UNSAFE_CONTAINER_OF_POP GCC_DIAG_ON() +static void tw_free_node(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; + if (node->is_flow_node()) { + /* this is a flow*/ + thread->free_last_flow_node(node); + }else{ + thread->free_node(node); + } +} static void tw_on_tick_per_thread_cb_always(void *userdata, @@ -3834,6 +3841,26 @@ void tw_on_tick_per_thread_cb(void *userdata, } +FORCE_NO_INLINE void CFlowGenListPerThread::handler_defer_job_flush(void){ + + /* free the objects letf in TW */ + m_tw.detach_all((void *)this,tw_free_node); + + /* flush the pending job of free ports */ + if (m_tcp_dpc) { + handler_defer_job((CGenNode *)m_tcp_dpc); + free_node((CGenNode *)m_tcp_dpc); + m_tcp_dpc=0; + } + if (m_udp_dpc) { + handler_defer_job((CGenNode *)m_udp_dpc); + free_node((CGenNode *)m_udp_dpc); + m_udp_dpc=0; + } +} + + + inline bool CNodeGenerator::do_work_stl(CGenNode * node, CFlowGenListPerThread * thread, bool on_terminate){ @@ -3883,7 +3910,6 @@ inline bool CNodeGenerator::do_work_both(CGenNode * node, /* PKT */ m_p_queue.pop(); thread->on_flow_tick<ON_TERMINATE>(node); - //printf(" MOVE from PKT->TW\n"); }else{ if ((type == CGenNode::FLOW_FIF)) { /* callback to our method */ @@ -3968,6 +3994,7 @@ inline int CNodeGenerator::teardown(CFlowGenListPerThread * thread, }else{ // free the left other thread->handler_defer_job_flush(); + } return (0); } @@ -4211,7 +4238,7 @@ void CNodeGenerator::handle_flow_pkt(CGenNode *node, CFlowGenListPerThread *thre } m_p_queue.pop(); if ( node->is_last_in_flow() ) { - thread->free_last_flow_node( node); + thread->free_last_flow_node(node); } else { node->update_next_pkt_in_flow_as(); m_p_queue.push(node); @@ -4510,7 +4537,7 @@ void CFlowGenListPerThread::terminate_nat_flows(CGenNode *p){ } else { m_flow_id_to_node_lookup.remove_no_lookup(p->get_short_fid() & NAT_FLOW_ID_MASK_IP_ID); } - free_last_flow_node( p); + free_last_flow_node(p); } diff --git a/src/bp_sim.h b/src/bp_sim.h index e8a37f6f..a41349d0 100755 --- a/src/bp_sim.h +++ b/src/bp_sim.h @@ -1498,6 +1498,14 @@ public: } void free_base(); + + bool is_flow_node(){ + if ((m_type == FLOW_PKT) || (m_type == FLOW_PKT_NAT)) { + return (true); + }else{ + return (false); + } + } }; @@ -1557,6 +1565,9 @@ public: /* update the node time for accurate scheduler */ inline void update_next_pkt_in_flow_as(void); + inline uint32_t update_next_pkt_in_flow_both(void); + + inline void reset_pkt_in_flow(void); inline uint8_t get_plugin_id(void){ return ( m_template_info->m_plugin_id); @@ -4108,6 +4119,17 @@ inline void CGenNode::update_next_pkt_in_flow_as(void){ m_pkt_info = m_flow_info->GetPacket((pkt_index-1)); } + +inline uint32_t CGenNode::update_next_pkt_in_flow_both(void){ + m_time += m_pkt_info->m_pkt_indication.m_cap_ipg; + 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 uint32_t CGenNode::update_next_pkt_in_flow_tw(void){ uint32_t dticks = m_pkt_info->m_pkt_indication.m_ticks; diff --git a/src/gtest/bp_timer_gtest.cpp b/src/gtest/bp_timer_gtest.cpp index c0779868..5185da87 100644 --- a/src/gtest/bp_timer_gtest.cpp +++ b/src/gtest/bp_timer_gtest.cpp @@ -189,6 +189,17 @@ void my_test_on_tick_cb7(void *userdata,CHTimerObj *tmr){ lp->timer_start(tmr,9); } +void my_test_on_tick_cb_free(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); + delete lpobj; +} + TEST_F(gt_r_timer, timer7) { @@ -593,3 +604,53 @@ TEST_F(gt_r_timer, timer16) { test.Delete(); } + +/* test free of iterator */ +TEST_F(gt_r_timer, timer17) { + + CHTimerWheel timer; + + CMyTestObject * tmr1; + tmr1 = new CMyTestObject(); + tmr1->m_id=12; + + CMyTestObject * tmr2; + tmr2 = new CMyTestObject(); + tmr2->m_id=13; + + CMyTestObject * tmr3; + tmr3 = new CMyTestObject(); + tmr3->m_id=14; + + + EXPECT_EQ( timer.Create(4,4),RC_HTW_OK); + timer.timer_start(&tmr1->m_timer,80); + timer.timer_start(&tmr2->m_timer,1); + timer.timer_start(&tmr3->m_timer,0); + + timer.detach_all((void *)&timer,my_test_on_tick_cb_free); + EXPECT_EQ( timer.Delete(),RC_HTW_OK); +} + + +TEST_F(gt_r_timer, timer18) { + + RC_HTW_t res[]={ + RC_HTW_OK, + RC_HTW_ERR_NO_RESOURCES, + RC_HTW_ERR_TIMER_IS_ON, + RC_HTW_ERR_NO_LOG2, + RC_HTW_ERR_MAX_WHEELS, + RC_HTW_ERR_NOT_ENOUGH_BITS + }; + + int i; + for (i=0; i<sizeof(res)/sizeof(RC_HTW_t); i++) { + CHTimerWheelErrorStr err(res[i]); + printf(" %-30s - %s \n",err.get_str(),err.get_help_str()); + } +} + + + + diff --git a/src/h_timer.cpp b/src/h_timer.cpp index baaaca31..b3d86d46 100644 --- a/src/h_timer.cpp +++ b/src/h_timer.cpp @@ -27,6 +27,10 @@ void CHTimerObj::Dump(FILE *fd){ } + +void detach_all(void *userdata,htw_on_tick_cb_t cb); + + RC_HTW_t CHTimerOneWheel::Create(uint32_t wheel_size){ CHTimerWheelLink *bucket; @@ -67,6 +71,26 @@ RC_HTW_t CHTimerOneWheel::Delete(){ } + +uint32_t CHTimerOneWheel::detach_all(void *userdata,htw_on_tick_cb_t cb){ + + uint32_t m_total_events=0; + int i; + for (i = 0; i < m_wheel_size; i++) { + CHTimerWheelLink * lp=&m_buckets[i]; + CHTimerWheelLink * first; + + while (!lp->is_self()) { + first = lp->m_next; + first->detach(); + m_total_events++; + assert(cb); + cb(userdata,(CHTimerObj *)first); + } + } + return (m_total_events); +} + RC_HTW_t CHTimerOneWheel::timer_stop(CHTimerObj *tmr){ if ( tmr->is_running() ) { tmr->detach(); @@ -107,11 +131,27 @@ void CHTimerOneWheel::dump_link_list(uint32_t bucket_index, } -void CHTimerWheel::on_tick(void *userdata,htw_on_tick_cb_t cb){ - +void CHTimerWheel::detach_all(void *userdata,htw_on_tick_cb_t cb){ + #ifndef _DEBUG + if (m_total_events==0) { + return; + } + #endif int i; + uint32_t res=0; + for (i=0;i<m_num_wheels; i++) { + CHTimerOneWheel * lp=&m_timer_w[i]; + res=lp->detach_all(userdata,cb); + assert(m_total_events>=res); + m_total_events -=res; + } + assert(m_total_events==0); +} +void CHTimerWheel::on_tick(void *userdata,htw_on_tick_cb_t cb){ + + int i; for (i=0;i<m_num_wheels; i++) { CHTimerOneWheel * lp=&m_timer_w[i]; CHTimerObj * event; diff --git a/src/h_timer.h b/src/h_timer.h index 1d57640b..a937d548 100644 --- a/src/h_timer.h +++ b/src/h_timer.h @@ -40,9 +40,64 @@ typedef enum { } RC_HTW_t; +class CHTimerWheelErrorStr { +public: + CHTimerWheelErrorStr(RC_HTW_t val){ + m_err=val; + } + const char * get_str(void){ + switch (m_err) { + case RC_HTW_OK: + return ("RC_HTW_OK"); + break; + case RC_HTW_ERR_NO_RESOURCES : + return ("RC_HTW_ERR_NO_RESOURCES"); + break; + case RC_HTW_ERR_TIMER_IS_ON : + return ("RC_HTW_ERR_TIMER_IS_ON"); + break; + case RC_HTW_ERR_NO_LOG2 : + return ("RC_HTW_ERR_NO_LOG2"); + break; + case RC_HTW_ERR_MAX_WHEELS : + return ("RC_HTW_ERR_MAX_WHEELS"); + break; + case RC_HTW_ERR_NOT_ENOUGH_BITS : + return ("RC_HTW_ERR_NOT_ENOUGH_BITS"); + break; + default: + assert(0); + } + } + const char * get_help_str(void){ + switch (m_err) { + case RC_HTW_OK: + return ("ok"); + break; + case RC_HTW_ERR_NO_RESOURCES : + return ("not enough memory"); + break; + case RC_HTW_ERR_TIMER_IS_ON : + return ("timer is already on, you should stop before start"); + break; + case RC_HTW_ERR_NO_LOG2 : + return ("number of buckets should be log2"); + break; + case RC_HTW_ERR_MAX_WHEELS : + return ("maximum number of wheels is limited to 4"); + break; + case RC_HTW_ERR_NOT_ENOUGH_BITS : + return ("(log2(buckets) * number of wheels) should be less than 32, try to reduce the number of wheels"); + break; + default: + assert(0); + } + } - +private: + RC_HTW_t m_err; +}; class CHTimerWheelLink { @@ -76,7 +131,7 @@ public: } void detach(void){ - #ifdef HTW_DEBUG + #ifdef _DEBUG assert(m_next); #endif CHTimerWheelLink *next; @@ -134,7 +189,7 @@ public: inline RC_HTW_t timer_start(CHTimerObj *tmr, htw_ticks_t ticks){ - #ifdef HTW_DEBUG + #ifdef _DEBUG if ( tmr->is_running() ){ return( RC_HTW_ERR_TIMER_IS_ON); } @@ -146,6 +201,8 @@ public: RC_HTW_t timer_stop (CHTimerObj *tmr); + uint32_t detach_all(void *userdata,htw_on_tick_cb_t cb); + inline bool check_timer_tick_cycle(){ return (m_tick_done); } @@ -247,6 +304,7 @@ public: RC_HTW_t Delete(); + inline RC_HTW_t timer_start(CHTimerObj *tmr, htw_ticks_t ticks){ m_total_events++; @@ -265,7 +323,9 @@ public: bool is_any_events_left(){ return(m_total_events>0?true:false); } - + + /* iterate all, detach and call the callback */ + void detach_all(void *userdata,htw_on_tick_cb_t cb); private: diff --git a/src/h_timer_w.h b/src/h_timer_w.h deleted file mode 100644 index 552c7423..00000000 --- a/src/h_timer_w.h +++ /dev/null @@ -1,533 +0,0 @@ -// -*- 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<void()> Callback; -// TimerWheel timers; -// int count = 0; -// TimerEvent<Callback> 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<Test, &Test::on_inc> inc_timer_; -// int count_ = 0; -// }; - -#ifndef RATAS_TIMER_WHEEL_H -#define RATAS_TIMER_WHEEL_H - -#include <cassert> -#include <cstdlib> -#include <cstdint> -#include <cstdio> -#include <limits> -#include <memory> - -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<typename CBType> -class TimerEvent : public TimerEventInterface { -public: - explicit TimerEvent<CBType>(const CBType& callback) - : callback_(callback) { - } - - void execute() { - callback_(); - } - -private: - TimerEvent<CBType>(const TimerEvent<CBType>& other) = delete; - TimerEvent<CBType>& operator=(const TimerEvent<CBType>& 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<typename T, void(T::*MFun)() > -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<size_t>::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<tick_t>::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 - |