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 --- src/stw_timer.h | 381 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 381 insertions(+) create mode 100644 src/stw_timer.h (limited to 'src/stw_timer.h') 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__ */ + + -- cgit 1.2.3-korg