十、任务调度(二)

Eb32tree

Eb32tree是Ebtree32位版本的一个具体实现。

[cpp] view plaincopy

1. [ebtree/eb32tree.h]  
2. /* This structure carries a node, a leaf, and a key. It must start with the 
3.  * eb_node so that it can be cast into an eb_node. We could also have put some 
4.  * sort of transparent union here to reduce the indirection level, but the fact 
5.  * is, the end user is not meant to manipulate internals, so this is pointless. 
6.  */  
7. struct eb32_node {  
8.     struct eb_node node; /* the tree node, must be at the beginning */  
9.     u32 key;  
10. };  
11.   
12. /* 
13.  * Exported functions and macros.  
14.  * Many of them are always inlined because they are extremely small, and 
15.  * are generally called at most once or twice in a program. 
16.  */  
17.   
18. /* Return leftmost node in the tree, or NULL if none */   
19. static inline struct eb32_node *eb32_first(struct eb_root *root)  
20. {  
21.     return eb32_entry(eb_first(root), struct eb32_node, node);  
22. }  
23.   
24. /* Return rightmost node in the tree, or NULL if none */   
25. static inline struct eb32_node *eb32_last(struct eb_root *root)  
26. {  
27.     return eb32_entry(eb_last(root), struct eb32_node, node);  
28. }  
29.   
30. /* Return next node in the tree, or NULL if none */  
31. static inline struct eb32_node *eb32_next(struct eb32_node *eb32)  
32. {  
33.     return eb32_entry(eb_next(&eb32->node), struct eb32_node, node);  
34. }  
35.   
36. /* Return previous node in the tree, or NULL if none */  
37. static inline struct eb32_node *eb32_prev(struct eb32_node *eb32)  
38. {  
39.     return eb32_entry(eb_prev(&eb32->node), struct eb32_node, node);  
40. }  
41.   
42. /* Return next node in the tree, skipping duplicates, or NULL if none */  
43. static inline struct eb32_node *eb32_next_unique(struct eb32_node *eb32)  
44. {  
45.     return eb32_entry(eb_next_unique(&eb32->node), struct eb32_node, node);  
46. }  
47.   
48. /* Return previous node in the tree, skipping duplicates, or NULL if none */  
49. static inline struct eb32_node *eb32_prev_unique(struct eb32_node *eb32)  
50. {  
51.     return eb32_entry(eb_prev_unique(&eb32->node), struct eb32_node, node);  
52. }  
53.   
54. /* Delete node from the tree if it was linked in. Mark the node unused. Note 
55.  * that this function relies on a non-inlined generic function: eb_delete. 
56.  */  
57. static inline void eb32_delete(struct eb32_node *eb32)  
58. {  
59.     eb_delete(&eb32->node);  
60. }  
61.   
62. /* Delete node from the tree if it was linked in. Mark the node unused. */  
63. static forceinline void __eb32_delete(struct eb32_node *eb32)  
64. {  
65.     __eb_delete(&eb32->node);  
66. }  

以上代码需要说明的是，eb32_entry是container_of的宏别名。为了说明清楚bit如何表示当前节点的值范围，现在将分析一下__eb32_insert()的代码，其他函数用到到时候再分析。

[cpp] view plaincopy

1. [ebtree/eb32tree.h]__eb32_insert()  
2. /* Insert eb32_node <new> into subtree starting at node root <root>. 
3.  * Only new->key needs be set with the key. The eb32_node is returned. 
4.  * If root->b[EB_RGHT]==1, the tree may only contain unique keys. 
5.  */  
6. static forceinline struct eb32_node *  
7. __eb32_insert(struct eb_root *root, struct eb32_node *new) {  
8.     struct eb32_node *old;  
9.     unsigned int side;  
10.     eb_troot_t *troot, **up_ptr;  
11.     u32 newkey; /* caching the key saves approximately one cycle */  
12.     eb_troot_t *root_right;  
13.     eb_troot_t *new_left, *new_rght;  
14.     eb_troot_t *new_leaf;  
15.     int old_node_bit;  
16.   
17.     side = EB_LEFT;  
18.     troot = root->b[EB_LEFT];  
19.     root_right = root->b[EB_RGHT];  
20.     if (unlikely(troot == NULL)) {  
21.         /* Tree is empty, insert the leaf part below the left branch */  
22.         root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);  
23.         new->node.leaf_p = eb_dotag(root, EB_LEFT);  
24.         new->node.node_p = NULL; /* node part unused */  
25.         return new;  
26. }  

如果root节点的左子树为空，那么表示这棵树是空的，将新插入节点作为叶子节点插入到root的左孩子上。此叶子节点是没有node节点的，这是作者在前面到描述中也提到过的。

[cpp] view plaincopy

1. [ebtree/eb32tree.h]__eb32_insert()  
2.     /* The tree descent is fairly easy : 
3.      *  - first, check if we have reached a leaf node 
4.      *  - second, check if we have gone too far 
5.      *  - third, reiterate 
6.      * Everywhere, we use <new> for the node node we are inserting, <root> 
7.      * for the node we attach it to, and <old> for the node we are 
8.      * displacing below <new>. <troot> will always point to the future node 
9.      * (tagged with its type). <side> carries the side the node <new> is 
10.      * attached to below its parent, which is also where previous node 
11.      * was attached. <newkey> carries the key being inserted. 
12.      */  
13.     newkey = new->key;  
14.   
15.     while (1) {  
16.         if (eb_gettag(troot) == EB_LEAF) {  
17.             /* insert above a leaf */  
18.             old = container_of(eb_untag(troot, EB_LEAF),  
19.                         struct eb32_node, node.branches);  
20.             new->node.node_p = old->node.leaf_p;  
21.             up_ptr = &old->node.leaf_p;  
22.             break;  
23.         }  

如果当前节点就是叶子节点，那么新节点将会插入在它之上。跳出循环，那么下面到代码就没必要执行了。

eb_untag(troot,EB_LEAF)得到的是struct eb_root结构体的实例，而struct eb_node中的branches成员就是struct eb_root类型，而struct eb_node结构体在struct eb32_node结构体中的成员名为node，因此通过eb_root_t的地址获取对应struct eb32_node的地址时需要将 eb_root_t转换成eb_root，然后使用node.branches成员与之对应，才能正确得到。

[cpp] view plaincopy

1. [ebtree/eb32tree.h]__eb32_insert()  
2.         /* OK we're walking down this link */  
3.         old = container_of(eb_untag(troot, EB_NODE),  
4.                     struct eb32_node, node.branches);  
5.         old_node_bit = old->node.bit;  
6.   
7.         /* Stop going down when we don't have common bits anymore. We 
8.          * also stop in front of a duplicates tree because it means we 
9.          * have to insert above. 
10.          */  
11.   
12.         if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */  
13.             (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {  
14.             /* The tree did not contain the key, so we insert <new> before the node 
15.              * <old>, and set ->bit to designate the lowest bit position in <new> 
16.              * which applies to ->branches.b[]. 
17.              */  
18.             new->node.node_p = old->node.node_p;  
19.             up_ptr = &old->node.node_p;  
20.             break;  
21.         }  
22.   
23.         /* walk down */  
24.         root = &old->node.branches;  
25.         side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;  
26.         troot = root->b[side];  
27. }  

当前节点是链接节点，那么如果它到bit小于0，表示其下的子树是值与其相等的子树，因此，不再向下查找。

(new->key ^ old->key) >> old_node_bit，之前提示过说，bit表示的是当前节点的值二进制1出现到最高位。因此这个表达式到值就是得到新节点到值是否最高位1到出现位置比当前查找节点的最高位1还高，如果这个表达式的值大于等于EB_NODE_BRANCHES(2)，那么表示，新节点插入应该在当前节点之上，因此不需要往下再查找。

如果新节点最高位1出现位置小于当前节点的话，新节点将会被插入到当前节点到左子树；若新节点最高位1出现位置等于当前节点的话，那么新节点将会被插入到当前节点到右子树。在进入子树之后由于前面while语句的存在，会继续查找子树，直到叶子节点或者遇到重复子树或者遇到当前节点与子树节点之间出现断层到现象，而待插入节点刚好处于断层范围内到值时而停止查找。

[cpp] view plaincopy

1. [ebtree/eb32tree.h]__eb32_insert()  
2.     new_left = eb_dotag(&new->node.branches, EB_LEFT);  
3.     new_rght = eb_dotag(&new->node.branches, EB_RGHT);  
4.     new_leaf = eb_dotag(&new->node.branches, EB_LEAF);  
5.   
6.     /* We need the common higher bits between new->key and old->key. 
7.      * What differences are there between new->key and the node here ? 
8.      * NOTE that bit(new) is always < bit(root) because highest 
9.      * bit of new->key and old->key are identical here (otherwise they 
10.      * would sit on different branches). 
11.      */  
12.   
13.     // note that if EB_NODE_BITS > 1, we should check that it's still >= 0  
14. new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;  

对于eb_dotag()没什么好说的。接下来看看fldnz()函数是个什么意思。

[cpp] view plaincopy

1. [ebtree/ebtree.h]flsnz()  
2. static inline int flsnz(int x)  
3. {     
4.     int r;  
5.     __asm__("bsrl %1,%0\n"  
6.             : "=r" (r) : "rm" (x));  
7.     return r+1;  
8. }  

bsrl指令是用于获取给定变量的二进制1出现的位置，范围0----31，此函数得到这个值之后，返回加一之后的值，也就是返回范围为1----32的值。

那么前面在赋给新节点之前，减去了一个EB_NODE_BITS，这是在ebtree/ebtree.h中定义为1的。因此结果就是bsrl返回到值，可是干什么要这么绕呢？我不懂。除了基于x86架构以及后续的x86_64的实现版本，在其他CPU上的版本如下

[cpp] view plaincopy

1. [ebtree/ebtree.h]flsnz()  
2. #define flsnz(___a) ({ \  
3.     register int ___x, ___bits = 0; \  
4.     ___x = (___a); \  
5.     if (___x & 0xffff0000) { ___x &= 0xffff0000; ___bits += 16;} \  
6.     if (___x & 0xff00ff00) { ___x &= 0xff00ff00; ___bits +=  8;} \  
7.     if (___x & 0xf0f0f0f0) { ___x &= 0xf0f0f0f0; ___bits +=  4;} \  
8.     if (___x & 0xcccccccc) { ___x &= 0xcccccccc; ___bits +=  2;} \  
9.     if (___x & 0xaaaaaaaa) { ___x &= 0xaaaaaaaa; ___bits +=  1;} \  
10.     ___bits + 1; \  
11. })  

代码解释如下，如果在高16有值，那么最高位1到出现位置应该大于16，因此需要将bit加16，更新__x的值，再检查往上的8位、4位、2位、1位，最后还要将__bits+1。看起来似乎这儿的+1还是多余了，因为在前面赋值给新节点到时候又减1了。所以我不懂为何作者要这样做，可能唯一到解释是为了方便人们的思想，好多编号都是从1开始的。

[cpp] view plaincopy

1. [ebtree/eb32tree.h]__eb32_insert()  
2.     if (new->key == old->key) {  
3.         new->node.bit = -1; /* mark as new dup tree, just in case */  
4.   
5.         if (likely(eb_gettag(root_right))) {  
6.             /* we refuse to duplicate this key if the tree is 
7.              * tagged as containing only unique keys. 
8.              */  
9.             return old;  
10.         }  
11.   
12.         if (eb_gettag(troot) != EB_LEAF) {  
13.             /* there was already a dup tree below */  
14.             struct eb_node *ret;  
15.             ret = eb_insert_dup(&old->node, &new->node);  
16.             return container_of(ret, struct eb32_node, node);  
17.         }  
18.         /* otherwise fall through */  
19.     }  

如果新节点与当前节点相同，那么将新节点的bit设置为-1，这只是为了以防这是一颗新产生的重复子树而已。因为若之前就已经存在重复子树，那么根据上一章对重复子树的插入可以知道，新节点到bit都会被重新设置。上一章描述的重复插入要求重复子树至少有两个节点。

设置好bit后，需要检查当前树是否允许存在重复值，上一章描述过，这是由root节点到右孩子指针上的一些附加信息来描述的。

如果不允许重复，那么直接返回当前节点。

允许重复，若当前节点不是叶子节点，也就是说之前在此处已经存在重复子树了，也就是之前在树中存在至少两个节点与新节点到值相同。若是叶子节点，那么插入操作与新节点值比当前节点大到情况相同。按照上一节对重复节点的插入操作可知，新节点总是插入在父节点的右子树，而把之前的右孩子节点作为新node节点的左孩子,自身的leaf放到新node节点的右孩子位置上;对于新节点值比当前节点到值大的情况，新节点(node和leaf)也是插入在父节点的右孩子，(除了位于root节点下的叶子节点，每个叶子节点都存在node和leaf节点，它们其实是同一个节点），而把之前的右孩子放到新node节点的左孩子，新的leaf则放到新node节点的右孩子上。

[cpp] view plaincopy

1. [ebtree/eb32tree.h]__eb32_insert()  
2.     if (new->key >= old->key) {  
3.         new->node.branches.b[EB_LEFT] = troot;  
4.         new->node.branches.b[EB_RGHT] = new_leaf;  
5.         new->node.leaf_p = new_rght;  
6.         *up_ptr = new_left;  
7.     }  
8.     else {  
9.         new->node.branches.b[EB_LEFT] = new_leaf;  
10.         new->node.branches.b[EB_RGHT] = troot;  
11.         new->node.leaf_p = new_left;  
12.         *up_ptr = new_rght;  
13.     }  
14.   
15.     /* Ok, now we are inserting <new> between <root> and <old>. <old>'s 
16.      * parent is already set to <new>, and the <root>'s branch is still in 
17.      * <side>. Update the root's leaf till we have it. Note that we can also 
18.      * find the side by checking the side of new->node.node_p. 
19.      */  
20.   
21.     root->b[side] = eb_dotag(&new->node.branches, EB_NODE);  
22.     return new;  
23. }  

按照具体值插入到相应位置，最后将当前节点的父节点到对应孩子设置为新节点。root的值随着遍历而改变，但总是指向当前节点的父节点。

还需要说明的就是up_ptr，这是为了统一代码修改当前节点的父节点指针而设置的。

在此总结一下存储于eb32tree中数据的特点，从上至下，存储的数据值从大到小；从左到右，存储的数据值从小到大；根据root右孩子指针的附加信息决定是否允许含有重复值；root左孩子树用于数据存储，root本身不用于存储数据。

任务的唤醒

任务到唤醒除了之前在process_session中提到的与stream_interfacer相关的操作可能唤醒当前任务之外，在每一轮run_loop里面还有会一个专门用于唤醒超时任务的函数。

[cpp] view plaincopy

1. [ebtree/task.c]wake_expired_tasks()  
2. /* 
3.  * Extract all expired timers from the timer queue, and wakes up all 
4.  * associated tasks. Returns the date of next event (or eternity) in <next>.  
5.  */  
6. void wake_expired_tasks(int *next)  
7. {  
8.     struct task *task;  
9.     struct eb32_node *eb;  
10.   
11. eb = eb32_lookup_ge(&timers, now_ms - TIMER_LOOK_BACK);  

通过eb32_lookup_ge()查找超时时间不比now_ms - TIMER_LOOK_BACK小的节点。本函数内是检查超时的任务，为什么要用一个比当前时间小的值作为参数来查找不比这个值小的第一个节点呢？直接使用eb32_lookup_le()然后以当前时间去查找最后一个比当前值小的节点呢？其实两种方法都可以，但是我想作者在此主要是想为以后对超时时间任务做一个控制而这样做的。比如当以后需要将程序改成只需要前面10ms内超时的任务的时候，那么就可以将TIMER_LOOK_BACK设置为10，那么得到的就是过去10ms内出现超时，但是还没移到可执行队列中的任务。

[cpp] view plaincopy

1. [ebtree/task.c]eb32_lookup_ge()  
2.     /* 
3.      * Find the first occurrence of the lowest key in the tree <root>, which is 
4.      * equal to or greater than <x>. NULL is returned is no key matches. 
5.      */  
6.     REGPRM2 struct eb32_node *eb32_lookup_ge(struct eb_root *root, u32 x)  
7.     {  
8.         struct eb32_node *node;  
9.         eb_troot_t *troot;  
10.       
11.         troot = root->b[EB_LEFT];  
12.         if (unlikely(troot == NULL))  
13.             return NULL;  
14.       
15.         while (1) {  
16.             if ((eb_gettag(troot) == EB_LEAF)) {  
17.                 /* We reached a leaf, which means that the whole upper 
18.                  * parts were common. We will return either the current 
19.                  * node or its next one if the former is too small. 
20.                  */  
21.                 node = container_of(eb_untag(troot, EB_LEAF),  
22.                             struct eb32_node, node.branches);  
23.                 if (node->key >= x)  
24.                     return node;  
25.                 /* return next */  
26.                 troot = node->node.leaf_p;  
27.                 break;  
28.         }  

如果当前节点是叶子节点，那么查看其值是否不小于要查找的x，若是则返回，否则退回上一层。

[cpp] view plaincopy

1. [ebtree/task.c]eb32_lookup_ge()  
2.         node = container_of(eb_untag(troot, EB_NODE),  
3.                     struct eb32_node, node.branches);  
4.   
5.         if (node->node.bit < 0) {  
6.             /* We're at the top of a dup tree. Either we got a 
7.              * matching value and we return the leftmost node, or 
8.              * we don't and we skip the whole subtree to return the 
9.              * next node after the subtree. Note that since we're 
10.              * at the top of the dup tree, we can simply return the 
11.              * next node without first trying to escape from the 
12.              * tree. 
13.              */  
14.             if (node->key >= x) {  
15.                 troot = node->node.branches.b[EB_LEFT];  
16.                 while (eb_gettag(troot) != EB_LEAF)  
17.                     troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];  
18.                 return container_of(eb_untag(troot, EB_LEAF),  
19.                             struct eb32_node, node.branches);  
20.             }  
21.             /* return next */  
22.             troot = node->node.node_p;  
23.             break;  
24.        }  

如果当前节点为重复子树的入口点，若当前节点值不小于待查值，则返回重复子树中最左边的叶子节点，否则退回上一层。

[cpp] view plaincopy

1. [ebtree/task.c]eb32_lookup_ge()  
2.         if (((x ^ node->key) >> node->node.bit) >= EB_NODE_BRANCHES) {  
3.             /* No more common bits at all. Either this node is too 
4.              * large and we need to get its lowest value, or it is too 
5.              * small, and we need to get the next value. 
6.              */  
7.             if ((node->key >> node->node.bit) > (x >> node->node.bit)) {  
8.                 troot = node->node.branches.b[EB_LEFT];  
9.                 return eb32_entry(eb_walk_down(troot, EB_LEFT), struct eb32_node,                               node);  
10.             }  
11.   
12.             /* Further values will be too low here, so return the next 
13.              * unique node (if it exists). 
14.              */  
15.             troot = node->node.node_p;  
16.             break;  
17.         }  
18.         troot = node->node.branches.b[(x >> node->node.bit)   
19. & EB_NODE_BRANCH_MASK];  
20.    }  

当前节点不存在重复子树，那么检查当前节点值与待查值的大小；

如果待查值比当前节点值大得多，那么返回上一层。至于里面作者检查是否当前节点比待查值大很多，我觉得在前面的if成立的情况下不可能发生。

如果以上条件均不满足，那么根据其右移bit得到的分支获取下一个节点，然后循环之前的操作。

[cpp] view plaincopy

1.     [ebtree/task.c]eb32_lookup_ge()  
2.         /* If we get here, it means we want to report next node after the 
3.          * current one which is not below. <troot> is already initialised 
4.          * to the parent's branches. 
5.          */  
6.         while (eb_gettag(troot) != EB_LEFT)  
7.             /* Walking up from right branch, so we cannot be below root */  
8.             troot = (eb_root_to_node(eb_untag(troot, EB_RGHT)))->node_p;  
9.       
10.         /* Note that <troot> cannot be NULL at this stage */  
11.         troot = (eb_untag(troot, EB_LEFT))->b[EB_RGHT];  
12.         if (eb_clrtag(troot) == NULL)  
13.             return NULL;  
14.       
15.         node = eb32_entry(eb_walk_down(troot, EB_LEFT), struct eb32_node, node);  
16.         return node;  
17. }  

运行至此，表示之前检查的节点小于待查值，现在需要找到比当前节点值大的最小叶子节点，那么首先需要找到共同祖先。这个共同祖先满足，当前节点位于其左子树的最右边。找到祖先之后，先获取其右子树，然后一直往左找到其位于最左边的叶子节点，这个点就是比当前节点大并且比待查节点大的第一个叶子节点。这是为什么呢？因为在查找过程中，如果跑到了当前节点左子树，这表明待查节点是比当前节点小至少一个档次，而右子树与当前节点是同一个档次的，因此如果在其左子树中找到的最大值小于待查值，那么其右子树的最左边的叶子节点就必然不小于待查值。

[cpp] view plaincopy

1. [ebtree/task.c]wake_expired_tasks()  
2.     while (1) {  
3.         if (unlikely(!eb)) {  
4.             /* we might have reached the end of the tree, typically because  
5.             * <now_ms> is in the first half and we're first scanning the last 
6.             * half. Let's loop back to the beginning of the tree now. 
7.             */        
8.             eb = eb32_first(&timers);  
9.             if (likely(!eb))  
10.                 break;    
11.         }  

如果之前等待队列中没有任务，之前查找返回的任务为空；或者由于之前返回的是等待队列中的最后一个，而且刚好超时时间和当前时间相等，那么在处理完之后，eb32_next()得到的也是空的。

[cpp] view plaincopy

1. [ebtree/task.c]wake_expired_tasks()  
2.         if (likely(tick_is_lt(now_ms, eb->key))) {  
3.             /* timer not expired yet, revisit it later */  
4.             *next = eb->key;  
5.             return;   
6.         }  
7.   
8.         /* timer looks expired, detach it from the queue */  
9.         task = eb32_entry(eb, struct task, wq);  
10.         eb = eb32_next(eb);  
11.         __task_unlink_wq(task);  

如果当前节点的超时时间大于当前时间，那么将next设置为当前节点的时间，然后返回。否则获取当前节点关联的任务，将当前节点指向逻辑上的下一个节点，然后将当前节点关联任务从等待队列中移除。

[cpp] view plaincopy

1. [ebtree/task.c]wake_expired_tasks()  
2.     /* It is possible that this task was left at an earlier place in the 
3.          * tree because a recent call to task_queue() has not moved it. This 
4.          * happens when the new expiration date is later than the old one. 
5.          * Since it is very unlikely that we reach a timeout anyway, it's a 
6.          * lot cheaper to proceed like this because we almost never update 
7.          * the tree. We may also find disabled expiration dates there. Since 
8.          * we have detached the task from the tree, we simply call task_queue 
9.          * to take care of this. Note that we might occasionally requeue it at 
10.          * the same place, before <eb>, so we have to check if this happens, 
11.          * and adjust <eb>, otherwise we may skip it which is not what we want. 
12.          * We may also not requeue the task (and not point eb at it) if its 
13.          * expiration time is not set. 
14.          */  
15.         if (!tick_is_expired(task->expire, now_ms)) {  
16.             if (!tick_isset(task->expire))  
17.                 continue;  
18.             __task_queue(task);  
19.             if (!eb || eb->key > task->wq.key)  
20.                 eb = &task->wq;  
21.             continue;  
22.         }  
23.         task_wakeup(task, TASK_WOKEN_TIMER);  
24. }  

如果当前任务没有超时，若其超时时间不存在，那么转到下一个节点；并且其超时时间是存在的，那么将其重新入等待队列，并且若下一个节点不存在，或者下一个节点必当前节点还大，那么将下一次处理的节点设置为当前节点。这儿的处理是为了处理一些冤假错案，但是可以这么说，基本上不会发生。

任务已经超时，那么将其转到可执行队列中，唤醒机制属于定时器超时。

[cpp] view plaincopy

1. [ebtree/task.c]wake_expired_tasks()  
2.     /* We have found no task to expire in any tree */  
3.     *next = TICK_ETERNITY;  
4.     return;  
5. }  

最后对于没有任务的队列，当然将*next设置为无限，表示下一个定时器超时时间是不存在的，因为没有定时器存在。

在前面用到了__task_queue()和task_wakeup()，那么接下来先看下它们的实现。

附加函数

[cpp] view plaincopy

1. [ebtree/task.c]__task_queue()  
2. /* 
3.  * __task_queue() 
4.  * 
5.  * Inserts a task into the wait queue at the position given by its expiration 
6.  * date. It does not matter if the task was already in the wait queue or not,  
7.  * as it will be unlinked. The task must not have an infinite expiration timer. 
8.  * Last, tasks must not be queued further than the end of the tree, which is 
9.  * between <now_ms> and <now_ms> + 2^31 ms (now+24days in 32bit).  
10.  * 
11.  * This function should not be used directly, it is meant to be called by the 
12.  * inline version of task_queue() which performs a few cheap preliminary tests 
13.  * before deciding to call __task_queue(). 
14.  */  
15. void __task_queue(struct task *task)  
16. {  
17.     if (likely(task_in_wq(task)))  
18.         __task_unlink_wq(task);  

如果当前task位于queue中，那么需要先将它删除掉，这是为什么呢？因为按照之前的流程来看，这个task对应的eb32_node的信息不是很正确，因此它如果还在队列中，那么需要将其移出队列，然后修正信息之后再重新链入队列。

[cpp] view plaincopy

1. [ebtree/task.c]task_in_wq()  
2. /* return 0 if task is in wait queue, otherwise non-zero */  
3. static inline int task_in_wq(struct task *t)  
4. {  
5.     return t->wq.node.leaf_p != NULL;  
6. }  
7.   
8. [ebtree/task.c]__task_unlink_wq()  
9. static inline struct task *__task_unlink_wq(struct task *t)  
10. {         
11.     eb32_delete(&t->wq);  
12.     if (last_timer == &t->wq)   
13.         last_timer = NULL;  
14.     return t;  
15. }  

last_timer表示位于定时器树中的超时时间最大的一个节点。

[cpp] view plaincopy

1. [ebtree/task.c]__task_queue()  
2.     /* the task is not in the queue now */  
3.     task->wq.key = task->expire;  
4. #ifdef DEBUG_CHECK_INVALID_EXPIRATION_DATES  
5.     if (tick_is_lt(task->wq.key, now_ms))  
6.         /* we're queuing too far away or in the past (most likely) */  
7.         return;   
8. #endif  

将eb32_node的key值设置为相应任务的超时时间。

[cpp] view plaincopy

1. [ebtree/task.c]__task_queue()  
2.     if (likely(last_timer &&  
3.            last_timer->node.bit < 0 &&  
4.            last_timer->key == task->wq.key &&  
5.            last_timer->node.node_p)) {  
6.          /* Most often, last queued timer has the same expiration date, so 
7.          * if it's not queued at the root, let's queue a dup directly there. 
8.          * Note that we can only use dups at the dup tree's root (most 
9.          * negative bit). 
10.          */  
11.         eb_insert_dup(&last_timer->node, &task->wq.node);  
12.         if (task->wq.node.bit < last_timer->node.bit)  
13.             last_timer = &task->wq;  
14.         return;  
15.     }  
16.     eb32_insert(&timers, &task->wq);  
17.   
18.     /* Make sure we don't assign the last_timer to a node-less entry */  
19.     if (task->wq.node.node_p && (!last_timer || (task->wq.node.bit < last_timer->node.bit)))  
20.         last_timer = &task->wq;  
21.     return;  
22. }  

如果last_timer存在，并且last_timer是一个重复子树的入口点，而且last_timer的超时时间与待插入节点超时时间相同，并且last_timer节点不是root节点，那么直接点调用eb_insert_dup()将待插入节点插入到以last_timer作为根的重复子树中。

如果条件不满足，那么用eb32_insert()将待插入节点插入到定时器树中。

最后还需要根据条件决定是否将刚插入的节点更新为last_timer。last_timer的优化仅仅是优化定时器入队时对于当前树中存在入口点为last_timer的重复子树的情况。那么为了在eb32_insert()之后，对于last_timer是否需要更新使用的判断条件仍然使用task->wq.node.bit < last_timer->node.bit？这个判断的依据是什么？

 

 

[cpp] view plaincopy

1. [ebtree/task.c]task_wakeup()  
2. /* puts the task <t> in run queue with reason flags <f>, and returns <t> */  
3. static inline struct task *task_wakeup(struct task *t, unsigned int f)  
4. {     
5.     if (likely(!task_in_rq(t)))  
6.         __task_wakeup(t);  
7.     t->state |= f;  
8.     return t;  
9. }  

如果待唤醒任务已经存在与可执行队列，那么将任务的状态加上相应的唤醒标志即可。否则调用__task_wakeup()将任务链入可执行队列中。

[cpp] view plaincopy

1. [ebtree/task.c]__task_wakeup()  
2. /* Puts the task <t> in run queue at a position depending on t->nice. <t> is 
3.  * returned. The nice value assigns boosts in 32th of the run queue size. A 
4.  * nice value of -1024 sets the task to -run_queue*32, while a nice value of 
5.  * 1024 sets the task to run_queue*32. The state flags are cleared, so the 
6.  * caller will have to set its flags after this call. 
7.  * The task must not already be in the run queue. If unsure, use the safer 
8.  * task_wakeup() function. 
9.  */   
10. struct task *__task_wakeup(struct task *t)  
11. {  
12.     run_queue++;  
13.     t->rq.key = ++rqueue_ticks;  
14.   
15.     if (likely(t->nice)) {  
16.         int offset;  
17.   
18.         niced_tasks++;  
19.         if (likely(t->nice > 0))  
20.             offset = (unsigned)((run_queue * (unsigned int)t->nice) / 32U);  
21.         else  
22.             offset = -(unsigned)((run_queue * (unsigned int)-t->nice) / 32U);  
23.         t->rq.key += offset;  
24.     }  
25.   
26.     /* clear state flags at the same time */  
27.     t->state &= ~TASK_WOKEN_ANY;  
28.   
29.     eb32_insert(&rqueue, &t->rq);  
30.     return t;  
31. }  

可执行任务的key设置为对runqueue的当前插入次数，如果待插入任务含有优先级，那么更新优先任务的数量，然后根据任务的优先级是大于还是小于0来决定其相对key的位移。正和负运算的结果绝对值是一样的，不同的仅仅是符号。那么与t->rq.key相加之后产生的效果是将当前任务在可执行队列中提前或者推后。

对于任务的优先级是在event_accept函数中在创建task的时候继承自LISTENER。

在此函数之中，任务的唤醒状态将会被全部清空，因此如果需要任务的唤醒状态的，则需要在此函数调用之后自己设置。

任务的执行

任务的执行函数为process_runnable_tasks()，入口位于run_poll_loop()中。

[cpp] view plaincopy

1. [ebtree/task.c]__task_wakeup()  
2. /* The run queue is chronologically sorted in a tree. An insertion counter is 
3.  * used to assign a position to each task. This counter may be combined with 
4.  * other variables (eg: nice value) to set the final position in the tree. The 
5.  * counter may wrap without a problem, of course. We then limit the number of 
6.  * tasks processed at once to 1/4 of the number of tasks in the queue, and to 
7.  * 200 max in any case, so that general latency remains low and so that task 
8.  * positions have a chance to be considered. 
9.  * 
10.  * The function adjusts <next> if a new event is closer.  
11.  */  

作者说明，任务在树中的位置由插入次数决定，当然可能在这个值之上用其他值修正(例如:nice值)。每一次处理可执行队列时，至少保证执行可执行队列四分之一的任务，上限为200个，以保证延迟较低而且还能兼顾一些具有优先级的任务，这是因为event_accept是在POLLER中进行处理的，而此处主要是负责TASK的处理，实际上就是process_session()的执行。

[cpp] view plaincopy

1. [ebtree/task.c]__task_wakeup()  
2. void process_runnable_tasks(int *next)  
3. {  
4.     struct task *t;  
5.     struct eb32_node *eb;  
6.     unsigned int max_processed;  
7.     int expire;   
8.   
9.     run_queue_cur = run_queue; /* keep a copy for reporting */  
10.     nb_tasks_cur = nb_tasks;  
11.     max_processed = run_queue;  
12.     if (max_processed > 200)  
13.         max_processed = 200;  
14.   
15.     if (likely(niced_tasks))  
16.         max_processed = (max_processed + 3) / 4;   
17.   
18.     expire = *next;  
19.     eb = eb32_lookup_ge(&rqueue, rqueue_ticks - TIMER_LOOK_BACK);  
20.     while (max_processed--) {  
21.         /* Note: this loop is one of the fastest code path in 
22.          * the whole program. It should not be re-arranged 
23.          * without a good reason. 
24.          */  
25.   
26.         if (unlikely(!eb)) {  
27.             /* we might have reached the end of the tree, typically because 
28.             * <rqueue_ticks> is in the first half and we're first scanning 
29.             * the last half. Let's loop back to the beginning of the tree now. 
30.             */  
31.             eb = eb32_first(&rqueue);  
32.             if (likely(!eb))  
33.                 break;  
34.         }  
35.   
36.         /* detach the task from the queue */  
37.         t = eb32_entry(eb, struct task, rq);  
38.         eb = eb32_next(eb);  
39.         __task_unlink_rq(t);  
40.   
41.         t->state |= TASK_RUNNING;  
42.         /* This is an optimisation to help the processor's branch 
43.          * predictor take this most common call. 
44.          */  
45.         t->calls++;  
46.         if (likely(t->process == process_session))  
47.             t = process_session(t);  
48.         else  
49.             t = t->process(t);  
50.   
51.         if (likely(t != NULL)) {  
52.             t->state &= ~TASK_RUNNING;  
53.             if (t->expire) {  
54.                 task_queue(t);  
55.                 expire = tick_first_2nz(expire, t->expire);  
56.             }  
57.   
58.             /* if the task has put itself back into the run queue, we want to ensure 
59.              * it will be served at the proper time, especially if it's reniced. 
60.              */  
61.             if (unlikely(task_in_rq(t)) && (!eb || tick_is_lt(t->rq.key, eb->key))) {  
62.                 eb = eb32_lookup_ge(&rqueue, rqueue_ticks - TIMER_LOOK_BACK);  
63.             }  
64.         }  
65.     }  
66.     *next = expire;  
67. }  

此函数的代码很简单，并且与之前的wake_expired_tasks()函数代码很相似。需要说明的就是在执行完process_session()之后，如果任务又出现在可执行队列中，那么如果当前任务的超时时间比下一次检查的任务的超时时间早，那么将会重新调用eb32_lookup_ge()来查找第一个可执行任务，那么很可能又找到当前任务，在此对其进行执行。

总结下任务状态链，任务的创建位于event_accept()函数中，然后以初始化状态被唤醒进入runqueue，然后被执行，执行完成之后有可能被销毁，也可能被移出到等待队列，还可能重新被唤醒进入可执行队列被再次执行。位于等待队列中的任务，在每一轮run_loop都会被检查是否超时时间已经到达，然后以超时状态将其唤醒转入可执行队列。任务处理过程其实是对相应SESSION的一个处理过程。