1. Preface
Recently I have been looking for time round C language implementation code, found that many are Java or C ++ implementation. And I’m not familiar with the other languages. I can’t read them very well. I haven’t found a good implementation for C, and there’s only one 135-star project on Github that I haven’t looked at yet. Later after the search, found two more similar code, bloggers are called reference implementation in the Linux source code, but I didn’t find the corresponding code, the individual feels they code implementation is very good, share it out for later again after finishing study (anyway I write my own not to come out, I try to write a simple time code, is can’t look straight into).
2. Multi-stage time wheel implementation framework
The diagram above shows a cascade of five time rounds. The big wheel in the middle is the work wheel, and only the tasks on it are performed; Tasks on other rounds will later migrate to the next round, and they will eventually migrate to the work round and be scheduled for execution.
The principle of the multistage time wheel is also easy to understand: take a clock for example, the second hand turns one turn and the minute hand turns one frame; One turn of the minute hand one turn of the hour hand; The same is true for the time wheel: when the lower wheel rotates one circle, the higher wheel rotates one circle, and the tasks on the higher wheel are reassigned to the lower wheel. Thus, the cascade effect of multistage wheels is realized.
2.1 Multilevel time wheel objects
- Multistage time rounds should include at least the following:
- Time round object for each level
- The position of the pointer on the wheel
There is a clever way of determining the position of the pointer on the wheel: bit operation. For example, to define an unsigned integer:
== Obtain the current system time and convert it to the time in the time wheel by bit operation. Compare the time in the time wheel with the time in the actual time wheel to determine the time for scheduling the time wheel forward, and then operate the task corresponding to the slot in the time wheel ==.
-
Why do you need at least two members?
- To define a multistage time wheel, the first thing you need to know is the number of layers in the cascade, that is, how many time wheels there are.
- The pointer position on the wheel is the position to which the current time wheel runs. The difference between it and the real time means that the subsequent time wheel needs to be scheduled and executed. Their difference is the driving force for the operation of the time wheel.
-
Definition of a multilevel time wheel object
// Implement level 5 time wheel range 0~ (2^8 *2^6 *2^6 *2^6 *2^6)=2^32
struct tvec_base
{
unsigned long current_index;
pthread_t thincrejiffies;
pthread_t threadID;
struct tvec_root tv1; /* First round */
struct tvec tv2; /* Second round */
struct tvec tv3; /* Third round */
struct tvec tv4; /* The fourth round */
struct tvec tv5; /* Fifth round */
};
Copy the code2.2 Time round objects
We know that each wheel is actually a hash table, and above we just instantiate the object for the five wheels, but it’s not clear what the five wheels contain, how many slots, etc. (struct tvec and struct tvec_root).
#define TVN_BITS 6
#define TVR_BITS 8
#define TVN_SIZE (1<<TVN_BITS)
#define TVR_SIZE (1<<TVR_BITS)
struct tvec {
struct list_head vec[TVN_SIZE];/*64 squares */
};
struct tvec_root{
struct list_head vec[TVR_SIZE];/*256 cells */
};
Copy the codeIn addition, every time wheel is a hash table, so its type should contain at least two pointer fields to implement the function of a bidirectional linked list. Here we use the general struct list_head bi-directional list structure for convenience.
2.3 Scheduled Task Objects
The main job of a timer is to complete a task at a specific time in the future, and this task often contains the following:
- Task processing logic (callback function)
- Task parameters
- Bidirectional linked list node
- When time
Specifies the definition of a scheduled task object
typedef void (*timeouthandle)(unsigned long );
struct timer_list{
struct list_head entry; // Join The Times into a linked list
unsigned long expires; // Timeout period
void (*function)(unsigned long); // The handler after the timeout
unsigned long data; // Handle the parameters of the function
struct tvec_base *base; // Point to the time wheel
};
Copy the codeRenderings on the wheel of time:
2.4 Two-way linked list
On the time wheel we use the data type of two-way linked list. The use of two-way linked list in addition to the operation than a single linked list complex, more than a pointer to the region has no other unacceptable problems. An extra pointer field is obviously not a problem in today’s large memory era. As for the complexity of bidirectional linked list operations, we can solve this by using the generic struct list structure, because bidirectional linked lists have many standard operation functions, and we can use the interface provided by them by referring directly to the list.h header.
Struct List can be said to be a universal two-way linked list operation framework, we only need to define a struct list object in a custom structure to use its standard operation interface. It also provides an interface like container_of, which is usually called list_Entry in the application layer, so you can easily find the starting address of a custom struct from a struct list member.
For log.h for the application layer, I’ll attach this file in the code below. If you need a kernel layer implementation, you can get it directly from the Linux source code.
2.5 Connection Mode
Multi-stage time wheel effect diagram:
3. Multi-level time round implementation with C language
3.1 Bidirectional linked list header file: list.h
Mention bidirectional linked list, many source code projects will achieve a series of unified bidirectional linked list operation functions. They encapsulate the statistical interface for the bidirectional linked list. The user only needs to add a struct list_head structure to the custom structure and then call the interface provided by them to complete all operations of the bidirectional linked list. These operations are typically implemented in the list.h header file. Linux source code also has the implementation (kernel mode implementation). They are implemented in essentially the same way, with a slight difference in the number of interfaces and functionality implemented. You can say that the ==list.h file is the best choice for learning two-way lists. It implements almost all operations: add, delete, change, search, iterate, replace, empty, and so on. Here I pieced together a log.h function from the source code to finally get the interface to use in the multilevel time round (the original blogger didn’t provide the list.h file, so I had to do it myself).
#if! defined(_BLKID_LIST_H) && ! defined(LIST_HEAD)
#define _BLKID_LIST_H
#ifdef __cplusplus
extern "C" {
#endif
/* * Simple doubly linked list implementation. * * Some of the internal functions ("__xxx") are useful when * manipulating whole lists rather than single entries, as * sometimes we already know the next/prev entries and we can * generate better code by using them directly rather than * using the generic single-entry routines. */
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
static inline void
__list_add(struct list_head *entry,
struct list_head *prev, struct list_head *next)
{
next->prev = entry;
entry->next = next;
entry->prev = prev;
prev->next = entry;
}
/** * Insert a new element after the given list head. The new element does not * need to be initialised as empty list. * The list of changes from: * head → some elements →... * to * head → new element → older element →... * * Example: * struct foo *newfoo = malloc(...) ; * list_add(&newfoo->entry, &bar->list_of_foos); * * @param entry The new element to prepend to the list. * @param head The existing list. */
static inline void
list_add(struct list_head *entry, struct list_head *head)
{
__list_add(entry, head, head->next);
}
/** * Append a new element to the end of the list given with this list head. * * The list changes from: * head → some element →... → lastelement * to * head → some element →... → lastElement → new element * * Example: * struct foo *newfoo = malloc(...) ; * list_add_tail(&newfoo->entry, &bar->list_of_foos); * * @param entry The new element to prepend to the list. * @param head The existing list. */
static inline void
list_add_tail(struct list_head *entry, struct list_head *head)
{
__list_add(entry, head->prev, head);
}
static inline void
__list_del(struct list_head *prev, struct list_head *next)
{
next->prev = prev;
prev->next = next;
}
/** * Remove the element from the list it is in. Using this function will reset * the pointers to/from this element so it is removed from the list. It does * NOT free the element itself or manipulate it otherwise. * * Using list_del on a pure list head (like in the example at the top of * this file) will NOT remove the first element from * the list but rather reset the list as empty list. * * Example: * list_del(&foo->entry); * * @param entry The element to remove. */
static inline void
list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
}
static inline void
list_del_init(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
INIT_LIST_HEAD(entry);
}
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
{
__list_del(list->prev, list->next);
list_add_tail(list, head);
}
/** * Check if the list is empty. * * Example: * list_empty(&bar->list_of_foos); * * @return True if the list contains one or more elements or False otherwise. */
static inline int
list_empty(struct list_head *head)
{
return head->next == head;
}
/** * list_replace - replace old entry by new one * @old : the element to be replaced * @new : the new element to insert * * If @old was empty, it will be overwritten. */
static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
/** * Retrieve the first list entry for the given list pointer. * * Example: * struct foo *first; * first = list_first_entry(&bar->list_of_foos, struct foo, list_of_foos); * * @param ptr The list head * @param type Data type of the list element to retrieve * @param member Member name of the struct list_head field in the list element. * @return A pointer to the first list element. */
#define list_first_entry(ptr, type, member) \
list_entry((ptr)->next, type, member)
static inline void list_replace_init(struct list_head *old,
struct list_head *new)
{
list_replace(old, new);
INIT_LIST_HEAD(old);
}
/** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. */
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
/** * list_for_each - iterate over elements in a list * @pos: the &struct list_head to use as a loop counter. * @head: the head for your list. */
#definelist_for_each(pos, head) \ for (pos = (head)->next; pos ! = (head); pos = pos->next)
/** * list_for_each_safe - iterate over elements in a list, but don't dereference * pos after the body is done (in case it is freed) * @pos: the &struct list_head to use as a loop counter. * @pnext: the &struct list_head to use as a pointer to the next item. * @head: the head for your list (not included in iteration). */
#definelist_for_each_safe(pos, pnext, head) \ for (pos = (head)->next, pnext = pos->next; pos ! = (head); \ pos = pnext, pnext = pos->next)
#ifdef __cplusplus
}
#endif
#endif /* _BLKID_LIST_H */
Copy the codeOne important implementation is usually used: ==container_of==. If you don’t know how it works, you can read the other blog post about container of()
3.2 Debugging header file: log.h
This header file is not really necessary, I just use it to add debugging information (errlog() and log() in the code are both macro functions in log.h). Its effect is to add color to the printed information, and the effect is as follows:
The code for log.h is as follows:
#ifndef _LOG_h_
#define _LOG_h_
#include <stdio.h>
#define COL(x) "\ [033." #x "m"
#define RED COL(31)
#define GREEN COL(32)
#define YELLOW COL(33)
#define BLUE COL(34)
#define MAGENTA COL(35)
#define CYAN COL(36)
#define WHITE COL(0)
#define GRAY "\033[0m"
#define errlog(fmt, arg...) do{ \
printf(RED"[#ERROR: Toeny Sun:"GRAY YELLOW" %s:%d]:"GRAY WHITE fmt GRAY, __func__, __LINE__, ##arg); \ }while(0)
#define log(fmt, arg...) do{ \
printf(WHITE"[#DEBUG: Toeny Sun: "GRAY YELLOW"%s:%d]:"GRAY WHITE fmt GRAY, __func__, __LINE__, ##arg); \ }while(0)
#endif
Copy the code3.3 timewheel code: timewheel.c
/* * Millisecond timer adopts the multi-stage time wheel mode. Use the Linux kernel implementation. * The supported range is 1 to 2^32 milliseconds (about 49 days) * If the set timer exceeds the maximum value, set the timer according to the maximum value
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
#include <sys/time.h>
#include "list.h"
#include "log.h"
#define TVN_BITS 6
#define TVR_BITS 8
#define TVN_SIZE (1<<TVN_BITS)
#define TVR_SIZE (1<<TVR_BITS)
#define TVN_MASK (TVN_SIZE - 1)
#define TVR_MASK (TVR_SIZE - 1)
#define SEC_VALUE 0
#define USEC_VALUE 2000
struct tvec_base;
#define INDEX(N) ((ba->current_index >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK)
typedef void (*timeouthandle)(unsigned long );
struct timer_list{
struct list_head entry; // Join The Times into a linked list
unsigned long expires; // Timeout period
void (*function)(unsigned long); // The handler after the timeout
unsigned long data; // Handle the parameters of the function
struct tvec_base *base; // Point to the time wheel
};
struct tvec {
struct list_head vec[TVN_SIZE];
};
struct tvec_root{
struct list_head vec[TVR_SIZE];
};
// Implement level 5 time wheel range 0~ (2^8 *2^6 *2^6 *2^6 *2^6)=2^32
struct tvec_base
{
unsigned long current_index;
pthread_t thincrejiffies;
pthread_t threadID;
struct tvec_root tv1; /* First round */
struct tvec tv2; /* Second round */
struct tvec tv3; /* Third round */
struct tvec tv4; /* The fourth round */
struct tvec tv5; /* Fifth round */
};
static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
{
struct list_head *vec;
unsigned long expires = timer->expires;
unsigned long idx = expires - base->current_index;
#if 1
if((signed long)idx < 0 ) /* There is no way to distinguish between outdated and super long time, right? * /
{
vec = base->tv1.vec + (base->current_index & TVR_MASK);/* Put it in the current slot of the first round */
}
else if ( idx < TVR_SIZE ) /* First round */
{
int i = expires & TVR_MASK;
vec = base->tv1.vec + i;
}
else if( idx < 1 << (TVR_BITS + TVN_BITS) )/* Second round */
{
int i = (expires >> TVR_BITS) & TVN_MASK;
vec = base->tv2.vec + i;
}
else if( idx < 1 << (TVR_BITS + 2 * TVN_BITS) )/* Third round */
{
int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
vec = base->tv3.vec + i;
}
else if( idx < 1 << (TVR_BITS + 3 * TVN_BITS) )/* The fourth round */
{
int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
vec = base->tv4.vec + i;
}
else /* Fifth round */
{
int i;
if (idx > 0xffffffffUL)
{
idx = 0xffffffffUL;
expires = idx + base->current_index;
}
i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
vec = base->tv5.vec + i;
}
#else
/* * * * * *;
#endif
list_add_tail(&timer->entry, vec);
}
static inline void detach_timer(struct timer_list *timer)
{
struct list_head *entry = &timer->entry;
__list_del(entry->prev, entry->next);
entry->next = NULL;
entry->prev = NULL;
}
static int __mod_timer(struct timer_list *timer, unsigned long expires)
{
if(NULL! = timer->entry.next) detach_timer(timer); internal_add_timer(timer->base, timer);return 0;
}
// Modify the timeout period of the timer external interface
int mod_timer(void *ptimer, unsigned long expires)
{
struct timer_list *timer = (struct timer_list *)ptimer;
struct tvec_base *base;
base = timer->base;
if(NULL == base)
return - 1;
expires = expires + base->current_index;
if(timer->entry.next ! =NULL && timer->expires == expires)
return 0;
if( NULL == timer->function )
{
errlog("timer's timeout function is null\n");
return - 1;
}
timer->expires = expires;
return __mod_timer(timer,expires);
}
// Add a timer
static void __ti_add_timer(struct timer_list *timer)
{
if( NULL! = timer->entry.next ) { errlog("timer is already exist\n");
return;
}
mod_timer(timer, timer->expires);
}
/* Add a timer external interface * return timer */
void* ti_add_timer(void *ptimewheel, unsigned long expires,timeouthandle phandle, unsigned long arg)
{
struct timer_list *ptimer;
ptimer = (struct timer_list *)malloc( sizeof(struct timer_list) );
if(NULL == ptimer)
return NULL;
bzero( ptimer,sizeof(struct timer_list) );
ptimer->entry.next = NULL;
ptimer->base = (struct tvec_base *)ptimewheel;
ptimer->expires = expires;
ptimer->function = phandle;
ptimer->data = arg;
__ti_add_timer(ptimer);
return ptimer;
}
/* * Delete a timer external interface * * */
void ti_del_timer(void *p)
{
struct timer_list *ptimer =(struct timer_list*)p;
if(NULL == ptimer)
return;
if(NULL! = ptimer->entry.next) detach_timer(ptimer);free(ptimer);
}
/* Time wheel cascade */
static int cascade(struct tvec_base *base, struct tvec *tv, int index)
{
struct list_head *pos, *tmp;
struct timer_list *timer;
struct list_head tv_list;
/* Transfer all tasks in slot TV [index] to tv_list and clear TV [index]*/
list_replace_init(tv->vec + index, &tv_list);/* replace TV with tv_list ->vec + index*/
list_for_each_safe(pos, tmp, &tv_list)/* Iterates through the tv_list bidirectional list, adding tasks back to the time wheel */
{
timer = list_entry(pos,struct timer_list,entry);/* Struct timer_list (struct timer_list (struct timer_list))
internal_add_timer(base, timer);
}
return index;
}
static void *deal_function_timeout(void *base)
{
struct timer_list *timer;
int ret;
struct timeval tv;
struct tvec_base *ba = (struct tvec_base *)base;
for(;;)
{
gettimeofday(&tv, NULL);
while( ba->current_index <= (tv.tv_sec*1000 + tv.tv_usec/1000))/* Unit: ms*/
{
struct list_head work_list;
int index = ba->current_index & TVR_MASK;/* Get the pointer position on the first round */
struct list_head *head = &work_list;
/* If the pointer points to slot 0, the task list of the cascade wheel needs to be updated */
if(! index && (! cascade(ba, &ba->tv2, INDEX(0&& ()))! cascade(ba, &ba->tv3, INDEX(1&& ()))! cascade(ba, &ba->tv4, INDEX(2))) )
cascade(ba, &ba->tv5, INDEX(3));
ba->current_index ++;
list_replace_init(ba->tv1.vec + index, &work_list);
while(! list_empty(head)) {void (*fn)(unsigned long);
unsigned longdata; timer = list_first_entry(head, struct timer_list, entry); fn = timer->function; data = timer->data; detach_timer(timer); (*fn)(data); }}}}static void init_tvr_list(struct tvec_root * tvr)
{
int i;
for( i = 0; i<TVR_SIZE; i++ )
INIT_LIST_HEAD(&tvr->vec[i]);
}
static void init_tvn_list(struct tvec * tvn)
{
int i;
for( i = 0; i<TVN_SIZE; i++ )
INIT_LIST_HEAD(&tvn->vec[i]);
}
// Create an external time wheel interface
void *ti_timewheel_create(void )
{
struct tvec_base *base;
int ret = 0;
struct timeval tv;
base = (struct tvec_base *) malloc( sizeof(struct tvec_base) );
if( NULL==base )
return NULL;
bzero( base,sizeof(struct tvec_base) );
init_tvr_list(&base->tv1);
init_tvn_list(&base->tv2);
init_tvn_list(&base->tv3);
init_tvn_list(&base->tv4);
init_tvn_list(&base->tv5);
gettimeofday(&tv, NULL);
base->current_index = tv.tv_sec*1000 + tv.tv_usec/1000;/* Number of current milliseconds */
if( 0! = pthread_create(&base->threadID,NULL,deal_function_timeout,base) )
{
free(base);
return NULL;
}
return base;
}
static void ti_release_tvr(struct tvec_root *pvr)
{
int i;
struct list_head *pos, *tmp;
struct timer_list *pen;
for(i = 0; i < TVR_SIZE; i++)
{
list_for_each_safe(pos,tmp,&pvr->vec[i])
{
pen = list_entry(pos,struct timer_list, entry);
list_del(pos);
free(pen); }}}static void ti_release_tvn(struct tvec *pvn)
{
int i;
struct list_head *pos, *tmp;
struct timer_list *pen;
for(i = 0; i < TVN_SIZE; i++)
{
list_for_each_safe(pos,tmp,&pvn->vec[i])
{
pen = list_entry(pos,struct timer_list, entry);
list_del(pos);
free(pen); }}}/* * Release the time wheel external interface * */
void ti_timewheel_release(void * pwheel)
{
struct tvec_base *base = (struct tvec_base *)pwheel;
if(NULL == base)
return;
ti_release_tvr(&base->tv1);
ti_release_tvn(&base->tv2);
ti_release_tvn(&base->tv3);
ti_release_tvn(&base->tv4);
ti_release_tvn(&base->tv5);
free(pwheel);
}
/************demo****************/
struct request_para{
void *timer;
int val;
};
void mytimer(unsigned long arg)
{
struct request_para *para = (struct request_para *)arg;
log("%d\n",para->val);
mod_timer(para->timer,3000); // Start the timer again
sleep(10);/* Timer is still blocked */
// The release of timer resources is done here
//ti_del_timer(para->timer);
}
int main(int argc,char *argv[])
{
void *pwheel = NULL;
void *timer = NULL;
struct request_para *para;
para = (struct request_para *)malloc( sizeof(struct request_para) );
if(NULL == para)
return 0;
bzero(para,sizeof(struct request_para));
// Create a time round
pwheel = ti_timewheel_create();
if(NULL == pwheel)
return - 1;
// Add a timer
para->val = 100;
para->timer = ti_add_timer(pwheel, 3000, &mytimer, (unsigned long)para);
while(1)
{
sleep(2);
}
// Release the time wheel
ti_timewheel_release(pwheel);
return 0;
}
Copy the code3.4 Compile and Run
toney@ubantu:/ MNT/HGFS/EM Embedded Learning Record / 4.Timerwheel /2. $ls a.out list.h log.h mutitimewheel. c toney@ubantu:/ MNT/HGFS/EM Embedded Learning record / 4.timerwheel /2. $GCC mutiTimeWheel. C-lpthread toney@ubantu:/ MNT/HGFS/EM Embedded learning record /4. timerwheel/2. Multistage time round $./ A. Out[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
[#DEBUG: Toeny Sun: mytimer:370]:100
Copy the codeThe result shows that if the added scheduled task is a time-consuming operation, subsequent tasks will also be blocked until timeout, or even blocked all the time, depending on whether the current task is time-consuming. This is theoretically unacceptable: one task should not and cannot affect other tasks. However, there is no improvement and improvement to this problem at present, and there will be opportunities to continue to improve it.