杨旭光的网站

说明

本文定时器是云风skynet框架下剥离出来的，之前拿了skynet源码后根据自己的情况做了相关的改变，放在server项目中。 定时器实现为linux内核的做法。定时器精度为0.01s。

核心结构体部分

//一个定时器内容
struct timer_event {
    uint32_t handle;//服务id
    int session;//会话id
};

//一个定时器
struct timer_node {
    struct timer_node *next;
    uint32_t expire;//到点时间 0.01s
};

//定时器向量
struct link_list {
    struct timer_node head;
    struct timer_node *tail;
};

//全局定时器结构体
struct timer {
    struct link_list near[256];//紧迫定时器向量数组
    struct link_list t[4][64];//4级梯度 松散型定时器向量数组
    uint32_t time;//已走过的时钟节拍数
    uint32_t current;//启动了多长时间 单位0.01s
    uint64_t current_point;//上一次更新时的 current
};

字段说明

0xff       =                                     [1 | 0000 0000]   =   256

0x3fff     =                               [11 1111 | 1111 1111]   =   16383

0x4000     =                           [1 | 00 0000 | 0000 0000]   =   16384

0xfffff    =                     [11 1111 | 11 1111 | 1111 1111]   =   1048575

0x100000   =                 [1 | 00 0000 | 00 0000 | 0000 0000]   =   1048576

0x3ffffff  =           [11 1111 | 11 1111 | 11 1111 | 1111 1111]   =   67108863

0x4000000  =       [1 | 00 0000 | 00 0000 | 00 0000 | 0000 0000]   =   67108864

0xffffffff = [11 1111 | 11 1111 | 11 1111 | 11 1111 | 1111 1111]   =   -1

紧迫定时器

我们最关心的，interval 值在 [0,255] 之间的256个定时器向量。我们这样组织它们的：这256个定时器向量被组织在一起存放在一个定时器向量数组，并作为数据结构timer的一部分。我们定义了一个成员near，以表示我们所关心的这256个定时器向量。这样我们在处理是否有到期定时器时，我们就只从定时器向量数组timer.near[0,255]中的某个定时器向量内进行扫描。

紧迫定时容器存储方式：

    255
[0000 0000]

利用 timer.time 对 255 求余后获得值 index，其初值为0，最大值为255。每进过一个时钟节拍时 timer.time 字段都会加1。显然，index字段所指定的定时器向量 timer.near[index] 中包含了当前时钟节拍内已经到期的所有动态定时器。而定时器向量 timer.near[index＋k] 则包含了接下来第k个时钟节拍时刻将到期的所有动态定时器。当 timer.time 求余后又重新变为0时，就意味着内核已经扫描完了timer.near中的所有256个定时器向量。

松散定时器

而对于我们不关心的，interval 值在 [0xff，0xffffffff] 之间的定时器，它们的到期紧迫程度也随其 interval 值的不同而不同。显然 interval 值越小，定时器紧迫程度也越高。因此在将它们以松散定时器向量进行组织时也应该区别对待。通常，定时器的 interval 值越小，它所处的定时器向量的松散度也就越低；而 interval 值越大，它所处的定时器向量的松散度也就越大。

我们规定，对于那些满足条件：(0x100 <= interval <= 0x3fff) 的定时器，只要表达式 (interval >> 8) 具有相同值的定时器都将被组织在同一个松散定时器向量中，即以 (1 >> 8 == 256) 为一个基本单位。因此，为组织所有满足条件 (0x100 <= interval <= 0x3fff) 的定时器，就需要 2^6==64 个松散定时器向量。同样地，为方便起见，这64个松散定时器向量也放在一起形成数组，并作为数据结构 timer 的一部分。我们定义了成员 t[0] ，来表示这64条松散定时器向量。

定时容器存储方式：

   64    |    255
[00 0000 | 0000 0000]

对于那些满足条件 (0x4000 <= interval <= 0xfffff) 的定时器，只要表达式 (interval >> 8+6) 的值相同的定时器都将被放在同一个松散定时器向量中。同样，要组织所有满足条件 (0x4000 <= interval <= 0xfffff) 的定时器，也需要 2^6==64 个松散定时器向量。类似地，这64个松散定时器向量也放在一起形成数组，并作为数据结构 timer 的一部分。我们定义了成员 t[1] ，来表示这64条松散定时器向量。

定时容器存储方式：

   64    |   64    |    255
[00 0000 | 00 0000 | 0000 0000]

对于那些满足条件 (0x100000 <= interval <= 0x3ffffff) 的定时器，只要表达式 (interval >> 8+6+6) 的值相同的定时器都将被放在同一个松散定时器向量中。同样，要组织所有满足条件 (0x100000 <= interval <= 0x3ffffff) 的定时器，也需要 2^6==64 个松散定时器向量。类似地，这64个松散定时器向量也放在一起形成数组，并作为数据结构 timer 的一部分。我们定义了成员 t[2] ，来表示这64条松散定时器向量。

定时容器存储方式：

   64    |   64    |   64    |    255
[00 0000 | 00 0000 | 00 0000 | 0000 0000]

对于那些满足条件 (0x4000000 <= interval <= 0xffffffff) 的定时器，只要表达式 (interval >> 8+6+6+6) 的值相同的定时器都将被放在同一个松散定时器向量中。同样，要组织所有满足条件 (0x4000000 <= interval <= 0xffffffff) 的定时器，也需要 2^6==64 个松散定时器向量。类似地，这64个松散定时器向量也放在一起形成数组，并作为数据结构 timer 的一部分。我们定义了成员 t[3] ，来表示这64条松散定时器向量。

定时容器存储方式：

   64    |   64    |   64    |   64    |    255
[00 0000 | 00 0000 | 00 0000 | 00 0000 | 0000 0000]

动态定时器的内部实现机制

在内核动态定时器机制的实现中，有三个操作时非常重要的：

1. 将一个定时器插入到它应该所处的定时器向量中。

2. 定时器的迁移，将一个定时器从它原来所处的定时器向量迁移到另一个定时器向量中。

3. 扫描并执行当前已经到期的定时器。

将一个定时器插入到链表中

函数server_timer_timeout()用于将一个不处于任何定时器向量中的定时器插入到它应该所处的定时器向量中去（根据定时器的expire值来决定）。

static void
add_node(struct timer *T, struct timer_node *node) {
    uint32_t time=node->expire;
    uint32_t current_time=T->time;
    if ((time|TIME_NEAR_MASK)==(current_time|TIME_NEAR_MASK)) {
        link(&T->near[time&TIME_NEAR_MASK],node);
    } else {
        int i;
        uint32_t mask=TIME_NEAR << TIME_LEVEL_SHIFT;
        for (i=0;i<3;i++) {
            if ((time|(mask-1))==(current_time|(mask-1))) {
                break;
            }
            mask <<= TIME_LEVEL_SHIFT;
        }
        link(&T->t[i][((time>>(TIME_NEAR_SHIFT + i*TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK)],node);
    }
}

static void
timer_add(struct timer *T, void *arg, size_t sz, int time) {
    struct timer_node *node = (struct timer_node *)malloc(sizeof(*node)+sz);
    memcpy(node+1,arg,sz);

    LOCK(T);

        node->expire=time+T->time;
        add_node(T,node);

    UNLOCK(T);
}

//外部接口 添加一个事件
int
server_timer_timeout(uint32_t handle, int time, int session) {
    if (time == 0) {
        printf("%d, %d, %d\n", handle, time, session);
    } else {
        struct timer_event event;
        event.handle = handle;
        event.session = session;
        timer_add(TI, &event, sizeof(event), time);
    }

    return session;
}

首先在添加一个定时器时，如果发现 time==0，那既认为是需要即时处理的，无需再加入定时器结构体中。handle 是用来描述定时器的来处，而 session 会话id是用来唯一标示此定时器。

接着我们调用 timer_add()，防止多线程的调用，我们需要在将定时器压入定时器向量前要加锁处理。

最后我们调用 add_node()，根据 expire 值来确定此定时器需要压入到哪个数组中的哪个定时器向量。

定时器迁移

由于一个定时器的 interval 值会随着时间的不断流逝而不断变小，因此那些原本到期紧迫程度较低的定时器会随着 timer.time 值的不断增大而成为即将马上到期的定时器。

比如定时器向量 timer.t[0][0] 中的定时器在经过 256 个时钟滴答后会成为未来256个时钟滴答内会到期的定时器。因此，定时器所处的位置也应相应地随着改变。

当 timer.time % 255 重新变为 0 时，则意味着 timer.near 中的 256 个定时器向量都已被我们扫描一遍了，从而使 timer.near 中的256个定时器向量变为空，此时需要用 timer.t[0][(timer.time>>8)&63] 定时器向量中的定时器去填充 timer.near 。

随着 timer.near 增加 256 后，(timer.near>>8)&63 自动加 1 ，当 (timer.near>>8)&63 == 63 时，意味着 timer.t[0] 中的 64 个定时器向量都已经被全部填充到 timer.near 中去了，从而使得 timer.t[0] 变为空，则用 timer.t[1][(timer.time>>(6+8)&63] 定时器向量中的定时器去填充 timer.t[0] ，timer.near。

如此一直类推下去，直到 timer.t[3]。

static void
timer_shift(struct timer *T) {
    LOCK(T);
    int mask = TIME_NEAR;//256
    uint32_t ct = ++T->time;//滴答数+1
    if (ct == 0) {
        move_list(T, 3, 0);
    } else {
        uint32_t time = ct >> TIME_NEAR_SHIFT;//8
        int i=0;

        while ((ct & (mask-1))==0) {//ct==256,512,768,1024,1280......
            int idx=time & TIME_LEVEL_MASK;//63[0011 1111]
            if (idx!=0) {
                move_list(T, i, idx);
                break;
            }
            mask <<= TIME_LEVEL_SHIFT;//6
            time >>= TIME_LEVEL_SHIFT;
            ++i;
        }
    }
    UNLOCK(T);
}

扫描更新并执行当前已经到期的定时器

//定时节点到了
static inline void
dispatch_list(struct timer_node *current) {
    do {
        struct timer_event * event = (struct timer_event *)(current+1);

        printf("%d, %d\n", event->handle, event->session);

        struct timer_node * temp = current;
        current=current->next;
        free(temp);
    } while (current);
}

static inline void
timer_execute(struct timer *T) {
    LOCK(T);
    int idx = T->time & TIME_NEAR_MASK;//idx==[0,255]
    while (T->near[idx].head.next) {
        struct timer_node *current = link_clear(&T->near[idx]);
        UNLOCK(T);
        // dispatch_list don't need lock T
        dispatch_list(current);
        LOCK(T);
    }

    UNLOCK(T);
}

在更新定时器迁移后，我们需要做的就是执行已经到期的定时器。此步骤就比较简单了，上面也介绍过，利用 timer.time 对 255 求余后获得值 index，其初值为0，最大值为255。每进过一个时钟节拍时 timer.time 字段都会加1。显然，index字段所指定的定时器向量 timer.near[index] 中包含了当前时钟节拍内已经到期的所有动态定时器。

注意在处理到期定时器之前一定要加锁，防止在处理过程中，别的线程对此定时器向量进行插入操作。

源码

好了，说了这么多，献上完整的源码收工吧。

timer.c

#include <time.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>

#define LOCK(q) while (__sync_lock_test_and_set(&(q)->lock,1)) {} //加锁
#define UNLOCK(q) __sync_lock_release(&(q)->lock); //解锁

#define TIME_NEAR_SHIFT 8//紧迫定时器位数
#define TIME_NEAR (1 << TIME_NEAR_SHIFT)//2^8 = 256 [0001 0000 0000]
#define TIME_LEVEL_SHIFT 6//松散定时器位数
#define TIME_LEVEL (1 << TIME_LEVEL_SHIFT)//2^6 = 64 [0100 0000]
#define TIME_NEAR_MASK (TIME_NEAR-1)//255 [1111 1111]
#define TIME_LEVEL_MASK (TIME_LEVEL-1)//63 [0011 1111]

//一个定时器内容
struct timer_event {
    uint32_t handle;//服务id
    int session;//会话id
};

//一个定时器
struct timer_node {
    struct timer_node *next;//下一定时器
    uint32_t expire;//到点时间 0.01s
};

//定时器向量链表
struct link_list {
    struct timer_node head;
    struct timer_node *tail;
};

//全局定时器结构体
struct timer {
    struct link_list near[TIME_NEAR];//紧迫定时器向量数组
    struct link_list t[4][TIME_LEVEL];//4级梯度 松散型定时器向量数组
    int lock;//操作锁
    uint32_t time;//已走过的时钟节拍数
    uint32_t current;//启动了多长时间 单位0.01s
    uint32_t starttime;//启动时间 单位 秒s
    uint64_t current_point;//上一次更新时的 current
    uint64_t origin_point;//获取linux系统启动到定时器初始化完毕时的秒数*100
};

static struct timer * TI = NULL;

static inline struct timer_node *
link_clear(struct link_list *list) {
    struct timer_node * ret = list->head.next;
    list->head.next = 0;
    list->tail = &(list->head);

    return ret;
}

static inline void
link(struct link_list *list, struct timer_node *node) {
    list->tail->next = node;
    list->tail = node;
    node->next = 0;
}

static void
add_node(struct timer *T, struct timer_node *node) {
    uint32_t time=node->expire;
    uint32_t current_time=T->time;
    if ((time|TIME_NEAR_MASK)==(current_time|TIME_NEAR_MASK)) {
        link(&T->near[time&TIME_NEAR_MASK],node);
    } else {
        int i;
        uint32_t mask=TIME_NEAR << TIME_LEVEL_SHIFT;
        for (i=0;i<3;i++) {
            if ((time|(mask-1))==(current_time|(mask-1))) {
                break;
            }
            mask <<= TIME_LEVEL_SHIFT;
        }
        link(&T->t[i][((time>>(TIME_NEAR_SHIFT + i*TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK)],node);
    }
}

static void
timer_add(struct timer *T, void *arg, size_t sz, int time) {
    struct timer_node *node = (struct timer_node *)malloc(sizeof(*node)+sz);
    memcpy(node+1,arg,sz);

    LOCK(T);

        node->expire=time+T->time;
        add_node(T,node);

    UNLOCK(T);
}

static void
move_list(struct timer *T, int level, int idx) {
    struct timer_node *current = link_clear(&T->t[level][idx]);
    while (current) {
        struct timer_node *temp=current->next;
        add_node(T,current);
        current=temp;
    }
}

//定时节点到了
static inline void
dispatch_list(struct timer_node *current) {
    do {
        struct timer_event * event = (struct timer_event *)(current+1);

        printf("%d, %d\n", event->handle, event->session);

        struct timer_node * temp = current;
        current=current->next;
        free(temp);
    } while (current);
}

static inline void
timer_execute(struct timer *T) {
    LOCK(T);
    int idx = T->time & TIME_NEAR_MASK;//idx==[0,255]
    while (T->near[idx].head.next) {
        struct timer_node *current = link_clear(&T->near[idx]);
        UNLOCK(T);
        // dispatch_list don't need lock T
        dispatch_list(current);
        LOCK(T);
    }

    UNLOCK(T);
}

static void
timer_shift(struct timer *T) {
    LOCK(T);
    int mask = TIME_NEAR;//256
    uint32_t ct = ++T->time;//滴答数+1
    if (ct == 0) {
        move_list(T, 3, 0);
    } else {
        uint32_t time = ct >> TIME_NEAR_SHIFT;//8
        int i=0;

        while ((ct & (mask-1))==0) {//ct==256,512,768,1024,1280......
            int idx=time & TIME_LEVEL_MASK;//63[0011 1111]
            if (idx!=0) {
                move_list(T, i, idx);
                break;
            }
            mask <<= TIME_LEVEL_SHIFT;//6
            time >>= TIME_LEVEL_SHIFT;
            ++i;
        }
    }
    UNLOCK(T);
}

static void
timer_update(struct timer *T) {
    // try to dispatch timeout 0 (rare condition)
    timer_execute(T);

    // shift time first, and then dispatch timer message
    timer_shift(T);

    timer_execute(T);
}

//外部接口 添加一个事件
int
server_timer_timeout(uint32_t handle, int time, int session) {
    if (time == 0) {
        printf("%d, %d, %d\n", handle, time, session);
    } else {
        struct timer_event event;
        event.handle = handle;
        event.session = session;
        timer_add(TI, &event, sizeof(event), time);
    }

    return session;
}

//创建定时器
static struct timer *
server_timer_create_timer() {
    struct timer *r=(struct timer *)malloc(sizeof(struct timer));
    memset(r,0,sizeof(*r));

    int i,j;

    for (i=0;i<TIME_NEAR;i++) {
        link_clear(&r->near[i]);
    }

    for (i=0;i<4;i++) {
        for (j=0;j<TIME_LEVEL;j++) {
            link_clear(&r->t[i][j]);
        }
    }

    r->lock = 0;
    r->current = 0;

    return r;
}

/*
     struct timespec
    {
        time_t tv_sec;//秒
        long tv_nsec;//纳秒 10亿纳秒==1秒
    }
    CLOCK_REALTIME：
    系统实时时间,随系统实时时间改变而改变,即从UTC1970-1-1 0:0:0开始计时,
    中间时刻如果系统时间被用户改成其他,则对应的时间相应改变。
    CLOCK_MONOTONIC,CLOCK_MONOTONIC_RAW：
    从系统启动这一刻起开始计时到现在经过多少秒,不受系统时间被用户改变的影响。
 */
//设置当前时间
static void
systime(uint32_t *sec, uint32_t *cs) {
    struct timespec ti;
    clock_gettime(CLOCK_REALTIME, &ti);
    *sec = (uint32_t)ti.tv_sec;
    *cs = (uint32_t)(ti.tv_nsec / 10000000);//centisecond: 1/100 second
}

//获取linux系统启动到现在的秒数*100
static uint64_t
gettime() {
    uint64_t t;
    struct timespec ti;
    clock_gettime(CLOCK_MONOTONIC_RAW, &ti);//单调递增时间
    t = (uint64_t)ti.tv_sec * 100;
    t += ti.tv_nsec / 10000000;
    return t;
}

//线程循环调用此函数
void
server_timer_updatetime(void) {
    uint64_t cp = gettime();
    if(cp < TI->current_point) {
        printf("time diff error: change from %ld to %ld", cp, TI->current_point);
        TI->current_point = cp;
    } else if (cp != TI->current_point) {
        uint32_t diff = (uint32_t)(cp - TI->current_point);//与上一次更新相隔多少 s/100
        TI->current_point = cp;

        uint32_t oc = TI->current;
        TI->current += diff;
        if (TI->current < oc) {
            // when cs > 0xffffffff(about 497 days), time rewind [1111 1111 | 1111 1111 | 1111 1111 | 1111 1111]
            TI->starttime += 0xffffffff / 100;
        }
        int i;
        for (i=0;i<diff;i++) {//定时器单位是 0.01s, 每 0.01s 进行一次检查, 所以此处需要进行diff次检查
            timer_update(TI);
        }
    }
}

//获取定时器启动时间 s
uint32_t
server_timer_gettime_fixsec(void) {
    return TI->starttime;
}

//获取定时器启动到现在经过了多少(秒*100)
uint32_t
server_timer_gettime(void) {
    return TI->current;
}

//初始化定时器
void
server_timer_init(void) {
    TI = server_timer_create_timer();
    systime(&TI->starttime, &TI->current);
    uint64_t point = gettime();
    TI->current_point = point;
    TI->origin_point = point;
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <signal.h>
#include <assert.h>
#include <unistd.h>
#include <pthread.h>

static void
create_thread(pthread_t *thread, void *(*start_routine) (void *), void *arg) {
    if (pthread_create(thread,NULL, start_routine, arg)) {
        fprintf(stderr, "Create thread failed");
        exit(1);
    }
}

static void *
_timer(void *p) {
    server_timer_init();
    for (;;) {
        server_timer_updatetime();
        usleep(2500);
    }
    return NULL;
}

int
main(int argc, char *argv[]) {
    pthread_t pid;
    create_thread(&pid, _timer, "_timer");
    sleep(1);
    server_timer_timeout(1, 20, 1001);
    server_timer_timeout(2, 40, 1002);
    server_timer_timeout(3, 60, 1003);
    server_timer_timeout(4, 80, 1004);
    server_timer_timeout(5, 100, 1005);
    for (;;) {
        sleep(1);
    }
    return 0;
}

gcc -o timer timer.c main.c -lpthread

游戏服务端定时器