skynet源码分析（7）--skynet中的timer

作者:shihuaping0918@163.com，转载请注明作者
skynet的timer是做游戏用得比较频繁的一个功能，分析一下它的源码还是有意义的。而且核心的C源码除了timer和网络以外，已经基本分析得差不多了。其它都是跟lua c api相关，或者是跟lua交互比较多的。timer的源码在skynet-timer.c和skynet-timer.h中。

在开始看代码之前，请大家默念三遍：
1秒=1000毫秒
1毫秒=1000微秒
1微秒=1000纳秒

然后再默念三遍：
skynet中的时间精度是10ms级别。

如果念完了我们开始准备看代码，在看源码前，还要说明一下，skynet的外部定时器是分为两部分存的，一部分存在叫near的数组里，另一部分存在一个二维数组里，分为四个级别。

最后，如果对位运算不熟悉的话就请回吧。

typedef void (*timer_execute_func)(void *ud,void *arg);

#define TIME_NEAR_SHIFT 8
#define TIME_NEAR (1 << TIME_NEAR_SHIFT)
#define TIME_LEVEL_SHIFT 6
#define TIME_LEVEL (1 << TIME_LEVEL_SHIFT)
#define TIME_NEAR_MASK (TIME_NEAR-1)
#define TIME_LEVEL_MASK (TIME_LEVEL-1)

//先搞清楚下面的单位
//1秒=1000毫秒 milliseconds
//1毫秒=1000微秒 microseconds
//1微秒=1000纳秒 nanoseconds

//整个timer中毫秒的精度都是10ms，
//也就是说毫秒的一个三个位，但是最小的位被丢弃

struct timer_event {
    uint32_t handle; //即是设置定时器的来源，又是超时消息发送的目标
    int session; //session，一个增ID，溢出了从1开始，所以不要设时间很长的timer
};

//链表
struct timer_node {
    struct timer_node *next; 
    uint32_t expire; 
};

//又一个链表
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]; //四个级别的定时器数组
    struct spinlock lock; //自旋锁
    uint32_t time; //计数器
    uint32_t starttime; //程序启动的时间点，timestamp，秒数
    uint64_t current; //从程序启动到现在的耗时，精度10毫秒级
    uint64_t current_point; //当前时间，精度10毫秒级
};

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 {  //这里有一种特殊情况，就是当time溢出，回绕的时候
        int i;
        uint32_t mask=TIME_NEAR << TIME_LEVEL_SHIFT;
        for (i=0;i<3;i++) { //看到i<3没，很重要很重要
            if ((time|(mask-1))==(current_time|(mask-1))) {
                break;
            }
            mask <<= TIME_LEVEL_SHIFT; //mask越来越大
        }
        //放入数组中
        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 *)skynet_malloc(sizeof(*node)+sz);
    memcpy(node+1,arg,sz);

    SPIN_LOCK(T);

        node->expire=time+T->time; //超时时间+当前计数
        add_node(T,node);

    SPIN_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 void
timer_shift(struct timer *T) {
    int mask = TIME_NEAR;
    uint32_t ct = ++T->time; 
    if (ct == 0) { //time溢出了
        move_list(T, 3, 0); //这里就是那个很重要的3
    } else { //time正常
        uint32_t time = ct >> TIME_NEAR_SHIFT;
        int i=0;

        while ((ct & (mask-1))==0) {
            int idx=time & TIME_LEVEL_MASK;
            if (idx!=0) {
                move_list(T, i, idx);
                break;              
            }
            mask <<= TIME_LEVEL_SHIFT; //mask越来越大
            time >>= TIME_LEVEL_SHIFT; //time越来越小
            ++i;
        }
    }
}

//派发消息到目标服务消息队列
static inline void
dispatch_list(struct timer_node *current) {
    do {
        struct timer_event * event = (struct timer_event *)(current+1);
        struct skynet_message message;
        message.source = 0;
        message.session = event->session; //这个很重要，接收侧靠它来识别是哪个timer
        message.data = NULL;
        message.sz = (size_t)PTYPE_RESPONSE << MESSAGE_TYPE_SHIFT;

        //派发定显示器消息
        skynet_context_push(event->handle, &message);
        
        struct timer_node * temp = current;
        current=current->next;
        skynet_free(temp);  
    } while (current); //一直到清空为止
}

//派发消息
static inline void
timer_execute(struct timer *T) {
    int idx = T->time & TIME_NEAR_MASK;
    
    while (T->near[idx].head.next) {
        struct timer_node *current = link_clear(&T->near[idx]);
        SPIN_UNLOCK(T);
        // dispatch_list don't need lock T
        dispatch_list(current);
        SPIN_LOCK(T);
    }
}

//时间更新好了以后，这里检查调用各个定时器
static void 
timer_update(struct timer *T) {
    SPIN_LOCK(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);

    SPIN_UNLOCK(T);
}

//创建一个定时器，没什么可说的
static struct timer *
timer_create_timer() {
    struct timer *r=(struct timer *)skynet_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]);
        }
    }

    SPIN_INIT(r)

    r->current = 0;

    return r;
}

int
skynet_timeout(uint32_t handle, int time, int session) {
    if (time <= 0) { //没有超时
        struct skynet_message message;
        message.source = 0;
        message.session = session;
        message.data = NULL;
        message.sz = (size_t)PTYPE_RESPONSE << MESSAGE_TYPE_SHIFT;
        //没有超时的直接发消息
        if (skynet_context_push(handle, &message)) {
            return -1;
        }
    } else { //有超时
        struct timer_event event;
        event.handle = handle;
        event.session = session;
        //有超时的加入定时器队列中
        timer_add(TI, &event, sizeof(event), time);
    }

    return session;
}

// centisecond: 1/100 second
static void
systime(uint32_t *sec, uint32_t *cs) {
#if !defined(__APPLE__)
    struct timespec ti;
    clock_gettime(CLOCK_REALTIME, &ti);
    *sec = (uint32_t)ti.tv_sec;
    *cs = (uint32_t)(ti.tv_nsec / 10000000);
#else
    struct timeval tv;
    gettimeofday(&tv, NULL);
    *sec = tv.tv_sec; //1970/1/1到现在的秒数
    *cs = tv.tv_usec / 10000; //微秒转毫秒，精度10ms
#endif
}

static uint64_t
gettime() {
    uint64_t t;
#if !defined(__APPLE__)
    struct timespec ti;
    clock_gettime(CLOCK_MONOTONIC, &ti);
    t = (uint64_t)ti.tv_sec * 100;
    t += ti.tv_nsec / 10000000;
#else
    struct timeval tv;
    gettimeofday(&tv, NULL);
    t = (uint64_t)tv.tv_sec * 100; //秒数
    t += tv.tv_usec / 10000; //精度为10毫秒级
#endif
    return t;
}

//在线程中不断被调用
//调用时间 间隔为 2500微秒，即2.5毫秒
void
skynet_updatetime(void) {
    uint64_t cp = gettime();
    if(cp < TI->current_point) {
        skynet_error(NULL, "time diff error: change from %lld to %lld", cp, TI->current_point);
        TI->current_point = cp;
    } else if (cp != TI->current_point) {
        uint32_t diff = (uint32_t)(cp - TI->current_point);
        TI->current_point = cp; //当前时间，毫秒级
        TI->current += diff; //从启动到现在耗时
        int i;
        for (i=0;i<diff;i++) {
            timer_update(TI); //注意这里
        }
    }
}

//返回启动的时的timestamp
uint32_t
skynet_starttime(void) {
    return TI->starttime;
}

//返回耗时
uint64_t 
skynet_now(void) {
    return TI->current;
}

//初始化
void 
skynet_timer_init(void) {
    TI = timer_create_timer();
    uint32_t current = 0;
    systime(&TI->starttime, &current); //取starttime和current
    TI->current = current;
    TI->current_point = gettime();
}

// for profile

#define NANOSEC 1000000000
#define MICROSEC 1000000

uint64_t
skynet_thread_time(void) {
#if  !defined(__APPLE__)
    struct timespec ti;
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ti);

    return (uint64_t)ti.tv_sec * MICROSEC + (uint64_t)ti.tv_nsec / (NANOSEC / MICROSEC);
#else
    struct task_thread_times_info aTaskInfo;
    mach_msg_type_number_t aTaskInfoCount = TASK_THREAD_TIMES_INFO_COUNT;
    if (KERN_SUCCESS != task_info(mach_task_self(), TASK_THREAD_TIMES_INFO, (task_info_t )&aTaskInfo, &aTaskInfoCount)) {
        return 0;
    }

    return (uint64_t)(aTaskInfo.user_time.seconds) + (uint64_t)aTaskInfo.user_time.microseconds;
#endif
}

代码分析完了，skynet中有一个timer线程，每2.5毫秒就更新一下timer中的时间。每次更新都会对一个叫time的计数器做加1操作，所以这个计数器其实可以当作时间来看待，然后对near数组中的定时器进行触发。

前面讲到还有四个级别的定时器数组，这些数组在timer_shift中被不断地重新调整优先级，直到移动到near数组中。四个级别分别是0，1，2，3，级别越大，expire也就越大，也就是超时时间越大。timer_shift会对各个级别中的定时器做重新的级别分配。

time计数器是有可能溢出的，有人称它为回绕，当它溢出了以后，会做一个特殊处理。即对level3的整个数组进行重新级别分配。

2017.8.24
还是补充说明一下，位运算在timer四个级别中的作用吧。一个time32位，初始near使用低7位作掩码，然后是13位掩码，然后19位，然后25位。

time和current_time都是对mask做与操作，与操作就是0 | 0 = 0 其它的都为1，这个操作意味着什么呢，就意味着a | b，结果肯定是两者中最大的，或者比两个都要大。因为a，b中只要有一个对应位置分别是0，1，最终都会变成1。而mask-1所有的位都是1，所以取到的值在mask位的肯定全为1。near取的是后8位，后8位的值也就是256，也就是说如果time和current_time只差255，那么时间就真的很接近了，255*2.5毫秒不到一秒钟。mask位数越多，被mask放大的数字也就越大。当然最高位也必须是相等的才行。

为什么time溢出了要把t[3]的定时器重新分配呢？这是因为time和current_time都特别大的时候，低8位(near)，8+6，8+62，这三个值的位数全设成1，不能够让time|mask等于current_time|mask。反而是8+63能够让time|mask==current_time|mask。所以全放到t[3]里面。而当time溢出了以后，current_time也会变。所以它要把t[3]全放进near里。换句话说，就是t[3]在timer溢出之前实际上充当了near的角色！

希望补充的这一段能够让多数人明白，这个算法的原理。