/*------------------------------------------------------------------ * 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__ */