1.8. Skynet定时器原理

定时器涉及到的结构体为：

struct timer_event {        //记录每个节点回复消息的信息，存储在节点的后面
    uint32_t handle;        //记录定位服务的编号
    int session;            //记录用于接收消息响应时，定位到是响应哪一条消息，由发送消息的服务生成
};

struct timer_node {                //节点
    struct timer_node *next;    //指向下一个节点
    uint32_t expire;            //保存该节点的timer_event消息回复事件的触发时间片为：添加时的时间片加上延时触发的时间
};

struct link_list {                //链表
    struct timer_node head;        //头节点，head.next指向第一个节点
    struct timer_node *tail;    //尾节点
};

struct timer {                            //定时器的信息存储结构
    struct link_list near[TIME_NEAR];    //保存时间片低8位的链表，每次都是从该数组中取链表
    struct link_list t[4][TIME_LEVEL];    //保存时间片高24位的链表，按照0，1，2，3从低位到高位都分别对应6位
    struct spinlock lock;                //锁
    uint32_t time;                        //当前的时间片，单位为1/100秒
    uint32_t starttime;                    //系统的开始实时时间，从UTC1970-1-1 0:0:0开始计时，精确到秒
    uint64_t current;                    //从开始时刻到现在的时长，精确到1/100秒
    uint64_t current_point;                //系统启动时长，精确到1/100秒
};

定时器的原理为：如上图所示，32为位无符号整数time记录时间片分别对应数组near[256]和t[4][64]，每次添加节点时（skynet_timer.c文件中的add_node函数）：（简单的说：如果expire与time之差小于256则将节点添加到near数组对应元素的链表中，否则从高位往低位依次比较expire的第i个6位二进制的值n与time的第i个6位二进制的值m，哪个不相等则将节点添加到数组t[4-i][n]对应的元素链表中），而下面是从低位往高位进行比较的。

• 首先检查节点的expire与time的高24位是否相等，相等则将该节点添加到expire低8位值对应数组near的元素的链表中，不相等则进行下一步。
• 检查expire与time的高18位是否相等，相等则将该节点添加到expire低第9位到第14位对应的6位二进制值对应数组t[0]的元素的链表中，如果不相等则进行下一步。
• 检查expire与time的高12位是否相等，相等则将该节点添加到expire低第15位到第20位对应的6位二进制值对应数组t[1]的元素的链表中，如果不相等则进行下一步。
• 检查expire与time的高6位是否相等，相等则将该节点添加到expire低第21位到第26位对应的6位二进制值对应数组t[2]的元素的链表中，如果不相等则进行下一步。
• 将该节点添加到expire低第27位到第32位对应的6位二进制值对应数组t[3]的元素的链表中

定时器线程每隔2500微秒会调用skynet_timer.c文件中的skynet_updatetime函数刷新时间，函数skynet_updatetime的原理为：将本次执行函数skynet_updatetime到上一次执行函数skynet_updatetime的这段时间间隔划分为以1/100秒为单位的时间片，并对这些时间片中的每个时间片都依次进行取操作（skynet_timer.c文件中的timer_execute函数）、刷新时间片time、移动t[4][64]中的链表操作以及取操作。取操作（timer_execute函数）的原理是将time的低8位值对应的near[256]数组中的链表取出，依次对链表中的所有节点进行消息回复。刷新时间片time、移动t[4][64]中的链表操作（timer_shift函数）的原理是刷新时间片time：

• 检查time是否溢出，如果溢出则将t[3][0]这个链表取出并依次将该链表中的节点添加（即实现该链表的移动操作），如果time未溢出，则进行下一步。
• 检查time低8位是否溢出产生进位，没有则结束，有则检查time的低第9位到第14位是否产生溢出，没有则将time的低第9位到第14位对应的值对应数组t[0]中的链表取出，并依次将该链表中的节点添加（即实现该链表的移动操作），如果有溢出，则进行下一步。
• 检查time低14位是否溢出产生进位，没有则结束，有则检查time的低第15位到第20位是否产生溢出，没有则将time的低第15位到第20位对应的值对应数组t[1]中的链表取出，并依次将该链表中的节点添加（即实现该链表的移动操作），如果有溢出，则进行下一步。
• 检查time低20位是否溢出产生进位，没有则结束，有则检查time的低第21位到第26位是否产生溢出，没有则将time的低第21位到第26位对应的值对应数组t[2]中的链表取出，并依次将该链表中的节点添加（即实现该链表的移动操作），如果有溢出，则进行下一步。
• 检查time低26位是否溢出产生进位，没有则结束，有则检查time的低第27位到第32位是否产生溢出，没有则将time的低第27位到第32位对应的值对应数组t[3]中的链表取出，并依次将该链表中的节点添加（即实现该链表的移动操作）。

在skynet_start.c文件这的skynet_start函数调用了skynet_timer.c文件中的skynet_timer_init函数进行定时器初始化

//初始化系统计时
void skynet_timer_init(void) {
    TI = timer_create_timer();            //新建一个计时信息结构体
    uint32_t current = 0;
    systime(&TI->starttime, &current);    //获取系统初始化时的UTC时间
    TI->current = current;
    TI->current_point = gettime();    //获得系统启动时的CPU时间
}

//创建一个计时信息结构体
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;
}

//清除指定链表，并返回指向链表的第一个节点的指针
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;
}

添加定时回复节点：

//定时回复，time的单位为1/100秒
int skynet_timeout(uint32_t handle, int time, int session) {
    if (time <= 0) {    //如果时间小于或等于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;
}

//向链表中添加节点，time的单位为1/100秒
static void timer_add(struct timer *T,void *arg,size_t sz,int time) {
    //分配一个节点timer_node和附加的timer_event的内存块
    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);
}

//添加节点，将节点触发的时间和当前时间相比小于256的节点添加到near数组中，
//依次越靠近当前时间的添加到越低位
static void add_node(struct timer *T,struct timer_node *node) {
    uint32_t time=node->expire;            //回复的时间片
    uint32_t current_time=T->time;

    //TIME_NEAR_MASK=0xff，如果高24位相等则将该节点添加到底8位中对应的链表
    if ((time|TIME_NEAR_MASK)==(current_time|TIME_NEAR_MASK)) {        
        link(&T->near[time&TIME_NEAR_MASK],node);    //将该节点加入低8位对应的链表
    } else {
        int i;
        uint32_t mask=TIME_NEAR << TIME_LEVEL_SHIFT;        //TIME_NEAR=256，TIME_LEVEL_SHIFT=6初始化为低14位的掩码
        for (i=0;i<3;i++) {
            if ((time|(mask-1))==(current_time|(mask-1))) {
                break;
            }
            mask <<= TIME_LEVEL_SHIFT;    //往左移6位，即依次产生20位，26位，32位掩码
        }

        //将该节点加入高24位对应的链表 TIME_NEAR_SHIFT=8，TIME_LEVEL_MASK=0x3f
        link(&T->t[i][((time>>(TIME_NEAR_SHIFT + i*TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK)],node);    
    }
}

//向link_list链表中添加timer_node，head->next指向第一个，
//tail指向尾节点，并且节点timer_node的后面附加有timer_event的信息
static inline void link(struct link_list *list,struct timer_node *node) {
    list->tail->next = node;
    list->tail = node;
    node->next=0;
}

定时器线程刷新时间：

//刷新时间
void skynet_updatetime(void) {
    uint64_t cp = gettime();    //获得从系统启动开始计时的时间，不受系统时间被用户改变的影响，精确到1/100秒
    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);        //从系统启动到目前的时间差，精确到1/100秒
        TI->current_point = cp;                //记录下当前的时间，不受系统时间被用户改变的影响，精确到1/100秒
        TI->current += diff;    
        int i;
        for (i=0;i<diff;i++) {
            timer_update(TI);        //刷新时间片
        }
    }
}

//刷新时间片
static void timer_update(struct timer *T) {
    SPIN_LOCK(T);

    // try to dispatch timeout 0 (rare condition)
    timer_execute(T);        //检查当前的时间片的低8位对应的数组元素的链表是否为空，不为空则取出

    // shift time first, and then dispatch timer message
    timer_shift(T);            //时间片time自加1，移动高24位的链表

    timer_execute(T);        //检查当前的时间片的低8位对应的数组元素的链表是否为空，不为空则取出

    SPIN_UNLOCK(T);
}

//检查当前的时间片的低8位对应的数组元素的链表是否为空，不为空则取出
static inline void timer_execute(struct timer *T) {
    int idx = T->time & TIME_NEAR_MASK;        //取低8位对应的值

    while (T->near[idx].head.next) {        //如果低8位值对应的数组元素有链表，则取出
        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);
    }
}

//将高24位对应的4个6位的数组中的各个元素的链表往低位移
static void timer_shift(struct timer *T) {
    int mask = TIME_NEAR;    //256掩码
    uint32_t ct = ++T->time;    //时间片自加1
    if (ct == 0) {                //如果时间片已经溢出即归0
        move_list(T, 3, 0);        //将对应的t[3][0]链表取出，然后再依次将链表的节点添加，即实现了移动操作
    } else {
        uint32_t time = ct >> TIME_NEAR_SHIFT;    //ct右移8位
        int i=0;

        while ((ct & (mask-1))==0) {    //开始时，如果低8位溢出产生进位
            int idx=time & TIME_LEVEL_MASK;        //time & 0x3f  即取T->time的9-14位的值
            if (idx!=0) {
                move_list(T, i, idx);    //将对应的t[i][idx]链表取出，然后再依次将链表的节点添加，即实现了移动操作
                break;                
            }
            mask <<= TIME_LEVEL_SHIFT;        //mask左移6位
            time >>= TIME_LEVEL_SHIFT;        //time右移6位
            ++i;
        }
    }
}