h_timer.h revision eae78d43
1#ifndef H_TIMER_WHEEL_H
2#define H_TIMER_WHEEL_H
3/*
4 Hanoh Haim
5 Cisco Systems, Inc.
6*/
7
8/*
9Copyright (c) 2015-2015 Cisco Systems, Inc.
10
11Licensed under the Apache License, Version 2.0 (the "License");
12you may not use this file except in compliance with the License.
13You may obtain a copy of the License at
14
15    http://www.apache.org/licenses/LICENSE-2.0
16
17Unless required by applicable law or agreed to in writing, software
18distributed under the License is distributed on an "AS IS" BASIS,
19WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
20See the License for the specific language governing permissions and
21limitations under the License.
22*/
23
24#include <common/basic_utils.h>
25#include <stdint.h>
26#include <assert.h>
27#include <rte_prefetch.h>
28#include "pal_utl.h"
29#include "mbuf.h"
30
31
32
33typedef enum {
34    RC_HTW_OK = 0,
35    RC_HTW_ERR_NO_RESOURCES = -1,
36    RC_HTW_ERR_TIMER_IS_ON  = -2,
37    RC_HTW_ERR_NO_LOG2      = -3,
38    RC_HTW_ERR_MAX_WHEELS   = -4,
39    RC_HTW_ERR_NOT_ENOUGH_BITS  = -5,
40
41} RC_HTW_t;
42
43
44
45
46
47class CHTimerWheelLink {
48
49public:
50    CHTimerWheelLink  * m_next;
51    CHTimerWheelLink  * m_prev;
52
53public:
54    void reset(){
55        m_next = 0;
56        m_prev = 0;
57    }
58    void set_self(){
59        m_next=this;
60        m_prev=this;
61    }
62
63    bool is_self(){
64        if (m_next == this) {
65            return (true);
66        }
67        return (false);
68    }
69
70    void append(CHTimerWheelLink * obj){
71        obj->m_next = this;
72        obj->m_prev = m_prev;
73
74        m_prev->m_next   = obj;
75        m_prev           = obj;
76    }
77
78    void detach(void){
79        #ifdef HTW_DEBUG
80        assert(m_next);
81        #endif
82        CHTimerWheelLink *next;
83
84        next = m_next;
85        next->m_prev = m_prev;
86        m_prev->m_next = next;
87        m_next=0;
88        m_prev=0;
89    }
90} ;
91
92typedef uint32_t  htw_ticks_t;
93
94class CHTimerObj : public CHTimerWheelLink  {
95
96public:
97    inline void reset(void){
98        CHTimerWheelLink::reset();
99        m_ticks_left=0;
100        m_wheel=0;
101    }
102
103    inline bool is_running(){
104        if (m_next != 0) {
105            return (true);
106        }
107        return (false);
108    }
109
110
111    void Dump(FILE *fd);
112
113public:
114    /* CACHE LINE 0*/
115    htw_ticks_t       m_ticks_left; /* abs ticks left */
116    uint32_t          m_wheel;
117
118    uint32_t          m_pad[2];      /* aging time in ticks */
119} ;
120
121typedef void (*htw_on_tick_cb_t)(void *userdata,CHTimerObj *tmr);
122
123class CHTimerOneWheel {
124
125public:
126    CHTimerOneWheel(){
127        reset();
128    }
129
130    RC_HTW_t Create(uint32_t wheel_size);
131
132    RC_HTW_t Delete();
133
134    inline RC_HTW_t timer_start(CHTimerObj  *tmr,
135                                htw_ticks_t   ticks){
136
137        #ifdef HTW_DEBUG
138        if ( tmr->is_running() ){
139            return( RC_HTW_ERR_TIMER_IS_ON);
140        }
141        #endif
142
143        append( tmr, ticks);
144        return (RC_HTW_OK);
145    }
146
147    RC_HTW_t timer_stop (CHTimerObj *tmr);
148
149    inline bool check_timer_tick_cycle(){
150        return (m_tick_done);
151    }
152
153
154    inline bool timer_tick(){
155
156        m_ticks++;
157        m_bucket_index++;
158
159        if (m_tick_done) {
160            m_tick_done=false;
161        }
162        if ( m_bucket_index == m_wheel_size ) {
163            m_bucket_index = 0;
164            m_tick_done=true;
165        }
166        m_active_bucket = &m_buckets[m_bucket_index];
167        return (m_tick_done);
168    }
169
170
171    inline CHTimerObj *  pop_event(void) {
172
173        if ( m_active_bucket->is_self() ){
174            return ((CHTimerObj *)0);
175        }
176
177        CHTimerWheelLink * first = m_active_bucket->m_next;
178
179        rte_prefetch0(first->m_next);
180
181        first->detach();
182        return ((CHTimerObj *)first);
183    }
184
185
186
187public:
188
189      void  dump_link_list(uint32_t bucket_index,
190                           void *userdata,
191                           htw_on_tick_cb_t cb,
192                           FILE *fd);
193
194
195      uint32_t get_bucket_index(void){
196          return ( m_bucket_index);
197      }
198
199private:
200
201    inline void reset(void){
202       m_buckets=0;
203       m_active_bucket=0;
204       m_ticks=0;
205       m_wheel_size=0;
206       m_wheel_mask=0;
207       m_bucket_index=0;
208       m_tick_done=false;
209    }
210
211
212    inline void append (CHTimerObj *tmr,
213                        uint32_t ticks) {
214        CHTimerWheelLink *cur;
215
216        uint32_t cursor = ((m_bucket_index + ticks) & m_wheel_mask);
217        cur = &m_buckets[cursor];
218
219        cur->append((CHTimerWheelLink *)tmr);
220    }
221
222private:
223	CHTimerWheelLink  * m_buckets;
224    CHTimerWheelLink  * m_active_bucket;     /* point to the current bucket m_buckets[m_bucket_index] */
225
226    htw_ticks_t         m_ticks;
227    uint32_t            m_wheel_size; //e.g. 256
228    uint32_t            m_wheel_mask; // 256-1
229    uint32_t            m_bucket_index;
230    bool                m_tick_done;
231};
232
233
234
235
236#define MAX_H_TIMER_WHEELS  (4)
237
238class CHTimerWheel {
239
240public:
241    CHTimerWheel(){
242        reset();
243    }
244
245    RC_HTW_t Create(uint32_t wheel_size,
246                    uint32_t num_wheels);
247
248    RC_HTW_t Delete();
249
250    inline RC_HTW_t timer_start(CHTimerObj  *tmr,
251                                htw_ticks_t  ticks){
252        m_total_events++;
253        if (likely(ticks<m_wheel_size)) {
254            tmr->m_ticks_left=0;
255            tmr->m_wheel=0;
256            return (m_timer_w[0].timer_start(tmr,ticks));
257        }
258        return ( timer_start_rest(tmr, ticks));
259    }
260
261    RC_HTW_t timer_stop (CHTimerObj *tmr);
262
263    void on_tick(void *userdata,htw_on_tick_cb_t cb);
264
265    bool is_any_events_left(){
266        return(m_total_events>0?true:false);
267    }
268
269
270
271private:
272    void reset(void);
273
274    RC_HTW_t timer_start_rest(CHTimerObj  *tmr,
275                              htw_ticks_t  ticks);
276
277private:
278    htw_ticks_t         m_ticks;
279    uint32_t            m_num_wheels;
280    uint32_t            m_wheel_size;  //e.g. 256
281    uint32_t            m_wheel_mask;  //e.g 256-1
282    uint32_t            m_wheel_shift; // e.g 8
283    uint64_t            m_total_events;
284    CHTimerOneWheel     m_timer_w[MAX_H_TIMER_WHEELS];
285} ;
286
287
288#endif
289