I Data structure of timer

skynet timer uses a timer data structure to save data, as follows:

    struct timer {
    	struct link_list near[TIME_NEAR];    //The event queue closest to the current time is retrieved from this queue every time a tick is made
    	struct link_list t[4][TIME_LEVEL];   //An event queue that is far from the current time.
    	struct spinlock lock;                
    	uint32_t time;                       //tick + 1 indicates the number of ticks each time
    	uint32_t starttime;                  //System time when the process started
    	uint64_t current;                    //How much time has elapsed since the process started, unit:
    	uint64_t current_point;              //Current system time of the process: unit: 1 / 100 second.
    };

II See how to add a timer event.

    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);	
    	}
    }

In this function, (time|TIME_NEAR_MASK)==(current_time|TIME_NEAR_MASK) compare whether the first 24 bits of the two time numbers are the same. If so, it means that the trigger time of this event is within the current 256 1 / 100 seconds. Then add the event node to the corresponding queue. If the first 24 bits of two time numbers are different, this event should be added to the corresponding high-order time queue.

Take a look at timer_ Data structure of node.

    struct timer_node {
    	struct timer_node *next;
    	uint32_t expire;
    };

There is only one expiration time and the pointer of the next node node. How does this node structure relate to specific timing events? Let's look at timer_add function.

    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);
    }

In production timer_ In the node structure, sz bytes are allocated. The sz bytes of memory represent specific events. Let's see the structure of specific events.

    struct timer_event {
    	uint32_t handle;
    	int session;
    };

This structure records the specific service and the session of the service message queue. Through this session, you can find the specific event function.

III Timer tick function.

    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);
    		}
    	}
    }

tick every 1 / 100 second and run timer_update function.

    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);
    }

timer_ The execute (T) function is to take out the expired event node and execute it. Let's take a closer look:

    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);
    	}
    }

This function is the specific execution timer function, which runs the time list corresponding to the current time. timer_shift(T) is a key function, time queue transfer function. See the following for details:

    static void timer_shift(struct timer *T) {
		int mask = TIME_NEAR;
		uint32_t ct = ++T->time;
		if (ct == 0) {
			move_list(T, 3, 0);
		} else {
			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;
				time >>= TIME_LEVEL_SHIFT;
				++i;
			}
		}
	}

When the last 8 bits of time+1 = = 0, start to re hash the events in the high-order queue to the near queue. We see timer_ Timer was run twice in update_ Execute, why? The first run is the event added to the time queue when timeout = 0, and the second run is the event queue corresponding to time+1. So far, the introduction of the timer of the whole skynet is completed. Generally speaking, there are four basic ways: 1 Linked list 2 Sort linked list 3 Minimum heap 4 Based on time wheel. The implementation of time wheel takes up more memory, but the speed of search, insertion and deletion is the fastest, which is 0 (1). Other data structures are memory saving methods, and the time complexity is generally o(n) or 0(lgn(n)). The efficiency of time wheel algorithm is the highest.