Open×××多处理之-多队列TUN多实例

两年前我曾经提到了多个Open×××共享一个tun虚拟网卡，旨在减少管理开销和切换开销，因为我讨厌在外面对一大堆网卡做Bridge或者 Bonding，除了初衷不同，事实上的关于TUN的进展一直没有偏离我的思路，如果你看一下哪怕是Linux 3.9.6的内核的tun.c就知道我当初的思路并没有错，Linux内核社区同样也是这么做的，无疑，大牛们做的更好。

1.关于网卡多队列

硬 件在不断的进步，但是终究会遇到物理瓶颈，而此时再想扩展性能就需要横向优化了，就是说，一个芯片遇到了瓶颈，我就搞多个，这也是很合理的想法。随着应用 爆炸式增长，CPU首先遇到了瓶颈，因此多核心CPU开始风靡。作为网络的出入口，网卡在多核CPU环境遭遇瓶颈，网卡的多处理紧随其后，开启了多队列征 程。
       网卡的多队列是硬件优化路线上及其重要的一步，看比GPU对CPU的挑衅(事实上，硬件的进化很大分量都是网络游戏催生的，注意“网络”和“游戏”两个 词)。如果网卡支持多个队列的发送和接收，那么便可以将某一个队列的处理和某一个CPU核心绑定，从而加速整个系统的处理速度。但事实上，整个过程并非如 想象的那般简单。

2.网卡多队列优化的历史

值得注意的是，网卡的多队列对应用是透明的，即它并不改变任何处理逻辑和流程，它并不影响协议栈接口。它影响的仅仅是处理性能，然而万事总有例外，后面一节我会提到，多队列的TUN虚拟网卡和Open×××之间是如何互相***的。

2.1.接收多队列

起 初，为了迎合多处理器，高端网卡均在硬件层面支持了多发送队列和多接收队列(这个和PCIe的MSI-X也是很有关系的，它减低了多队列机制的实现难度， 增加了针对多队列机制的编程易度)。但是并没有明确规定“什么样的数据包进入哪个队列”，数据包与队列的映射关系和将来处理数据包的CPU无关，它们之间 也没有任何接口可供编程。
       此时的多队列，更多的是证实一种可行性，它简单地将数据包随机的hash到不同的网卡队列中。对于处理数据包的应用以及协议栈而言，无法预知可以在哪个网 卡队列得到数据包。诸如Intel这类厂商也公布了一些hash算法的细节，比如5元组hash等，这些细节是开发者唯一可以利用的资源。然而这就是技 术，也是所有历史的第一步，即首先要有一个可以经得起继续复杂化的最简单系统(注意，***文明没有能经得起复杂性)。

2.2.Receive Packet Steering

前面说过，事实总比理论更加复杂。因此有了一种软件解决方案(同时可以配合硬件)。
多 个网卡队列看似迎合了多个CPU核心，但是还要考虑到CPU的Cache命中率，以Linux为例，我们知道，Linux协议栈的处理大多数都是在处理数 据包头，而对于同一个五元组的同一个流而言，包头的数据几乎是相同的，也就是说，如果这些数据包被hash到不同的网卡接收队列，如果此时你有将不同的接 收队列绑定在不同的CPU核心上(正如大多数的知道多队列网卡这件事的初学者做的那样)，那么将会导致cacheline-pingpong现象，虽然看 上去确实是一个网卡队列对应一个CPU核心，但事实上，CPU的Cache将无法得到充分利用。这只是一个cacheline-pingpong的表征， 这个已经被诸多协议栈解决了，对于Linux而言，就是让网络接收硬中断的CPU处理即将的协议栈软中断逻辑。但是还有一个cacheline-ping 表征就是处理协议栈逻辑的那个CPU并不一定是应用运行的那个CPU。
       对于Linux而言，网络接收软中断的处理几乎都是在硬中断的那个CPU上进行的，但是如果应用运行在另外的CPU上，在socket层将会导致一次切换，从处理软中断的CPU切换到应用运行的CPU，导致cache数据报废。
       现在已经很明了了，那就是针对同一个数据流(看你怎么定义数据流了，5元组，4元组，甚至1元组，都可以)，网卡的多队列调度机制总是可以将该数据流的所 有数据包调度到同一个CPU核心上，同时该CPU核心也要是应用运行的那个CPU核心。那么必须需要一个动作，即应用程序告诉内核它运行在哪个CPU上， 而这个动作可以在socket层次的recv，poll等接口中进行。
       这样便解决了“大多数”的cacheline-pingpong问题。
       sleep(5);
       一般对于路由器/交换机这种三层以及三层以下的设备而言，根本没有必要运行上面的举措，但是这些底层设备的技术在10年前就成熟了，由于它们都是基础设 备，技术更不易和不宜变化，事实上，应用的发展对技术的发展推动性更大。对于服务器而言，数据包一般都是从本地发出并接收到本地的，即本地是数据的始发站 和终点站，不光对于纯应用服务器而言是这样，对于那种7层转发设备，比如WEB防火墙，正向代理，反向代理同样如此。这就不得不考虑App- pingpong的导致的cacheline-pingpong问题。
       现在想一下多个线程同时recv一个socket的情况，到底哪个线程设置的CPU有效呢？按照上述解释，最后一个设置的线程将会夺取数据包，随后在它处 理数据的时候，其它的线程同理也会这样，这就会造成一个流的数据包乱序到达不同的线程，乱序的危害不在于它能使程序出错，而是它会减低CPU cacheline的利用率，同一个流的前后数据包局部性关联很强，放在单一的CPU中处理，cache的命中率会很高。RPF的缺点在于，只要有谁设置 了一个流的处理CPU，那么软中断就会被牵着鼻子走，调度到那个CPU上。如何解决呢？下文分解。

2.3.Receive flow steering

上面的分析最后遇到了新的cacheling-pingpong问题，只是这个问题不再是网卡导致的，而是协议栈与应用之间的socket层导致的，那么解决办法当然在这个层开刀了。Very well，let's go on!
       造成问题的根本原因在于，应用程序运行的CPU和网卡队列虽然有了对应关系-在socket层可以设置处理一个flow的CPU(即一个socket等待 在哪个CPU上)，但是内核却无法追踪应用程序的行踪，下面两个对应关系已经建立：1.应用程序和数据流的对应关系(socket tuple，rxhash)；2.数据流和CPU的对应关系。第2个关系是多队列网卡建立的，那么第一个关系便需要由socket自己建立，因为 socket自己当然知道自己在哪个CPU上，也知道自己收发的数据包的各个元组信息，那么它便可以算出一个hash值，如果这个hash值能被硬件感 知，那么所有的对应关系不就建立起来了吗？即socket建立一个CPU和一个数据流的hash的对应关系，该hash和网卡队列的对应关系由网卡硬件建 立，那么网卡在接收某个数据流的数据包的时候就知道了和该数据包相关的socket在哪个CPU核心上等着它。
       当然，这只是理想情况，事实上，RPS和RFS是一回事，只是前者没有考虑应用在多个CPU核心上蹦跶(App-pingpong)而已。如果应用在 CPU之间蹦跶，比如多个线程绑在多个CPU核心上，同时处理一个socket，那么一个flow的处理CPU可能会频繁变动，这就是App pingpong，最终导致cacheling pingpong，而RFS简单解决了这一问题。
       RFS运用了一个简单的自适应感知算法，保证连续到来的数据包中的属于同一数据流的数据只由一个CPU处理，即便应用已经切换到别的CPU了，这就保证了 cacheling的高效利用，具体的算法，我将在实现了多线程Open×××之后描述多线程Open×××优化的时候给出。

2.4.Intel 82599 的ATR

Intel 82599系列万兆卡自身具有上面提到的所谓学习机制，即它在往外发送数据包的时候会用当前数据包的元组信息以及当前的队列信息对网卡芯片进行编程，使得 属于该数据流的反向数据包被其接收的时候可以自动被调度到这个队列，这就是Application Target Receive机制。效果是什么呢？效果就是如果一个应用程序在各个CPU之间不断跳跃，那么处理它的网卡队列也会随着跳跃，这是一种负反馈跟踪机制，虽 然违背了RPS的思想，但是确实效果不错，然而有一个问题，那就是但凡负反馈都会有延迟，当延迟大于跳跃间隔的时候，pingpong现象将会加重。以下 是Linux 2.6.32的ixgbe的ATR实现：

static void ixgbe_atr(struct ixgbe_adapter *adapter, struct sk_buff *skb,                   int queue, u32 tx_flags) {     /* Right now, we support IPv4 only */     struct ixgbe_atr_input atr_input;     struct tcphdr *th;     struct iphdr *iph = ip_hdr(skb);     struct ethhdr *eth = (struct ethhdr *)skb->data;     u16 vlan_id, src_port, dst_port, flex_bytes;     u32 src_ipv4_addr, dst_ipv4_addr;     u8 l4type = 0;     /* check if we're UDP or TCP */     if (iph->protocol == IPPROTO_TCP) {         th = tcp_hdr(skb);         src_port = th->source;         dst_port = th->dest;         l4type |= IXGBE_ATR_L4TYPE_TCP;         /* l4type IPv4 type is 0, no need to assign */     } else {         /* Unsupported L4 header, just bail here */         return;     }     memset(&atr_input, 0, sizeof(struct ixgbe_atr_input));     vlan_id = (tx_flags & IXGBE_TX_FLAGS_VLAN_MASK) >>                IXGBE_TX_FLAGS_VLAN_SHIFT;     src_ipv4_addr = iph->saddr;     dst_ipv4_addr = iph->daddr;     flex_bytes = eth->h_proto;     ixgbe_atr_set_vlan_id_82599(&atr_input, vlan_id);     ixgbe_atr_set_src_port_82599(&atr_input, dst_port);     ixgbe_atr_set_dst_port_82599(&atr_input, src_port);     ixgbe_atr_set_flex_byte_82599(&atr_input, flex_bytes);     ixgbe_atr_set_l4type_82599(&atr_input, l4type);     /* src and dst are inverted, think how the receiver sees them */     ixgbe_atr_set_src_ipv4_82599(&atr_input, dst_ipv4_addr);     ixgbe_atr_set_dst_ipv4_82599(&atr_input, src_ipv4_addr);     /* This assumes the Rx queue and Tx queue are bound to the same CPU */     ixgbe_fdir_add_signature_filter_82599(&adapter->hw, &atr_input, queue); }

3.多队列的TUN

我暂时对关于多队列的讨论告一段落，正式步入本文的正题，即TUN的多队列对Open×××的影响。
Linux内核在3.8中支持了多队列(multiqueue)，以下是关于patch的原文：

tuntap: multiqueue support

This patch converts tun/tap to a multiqueue devices and expose the multiqueuequeues as multiple file descriptors to userspace. Internally, each tun_file wereabstracted as a queue, and an array of pointers to tun_file structurs werestored in tun_structure device, so multiple tun_files were allowed to beattached to the device as multiple queues.
 When choosing txq, we first try to identify a flow through its rxhash, if itdoes not have such one, we could try recorded rxq and then use them to choosethe transmit queue. This policy may be changed in the future.
分 为两段，第一段是总体介绍，第二段指出了一个问题，最终以“This policy may be changed in the future”结尾，给出希望。然而正是第二段的这个多队列调度策略在Open×××中有问题，我才改它的，而且我也等不到“may be changed”的那一天，更何况还仅仅是“may”而已。

3.1.Open×××面临的问题

说了N遍了，它是单进程的，但是 我们可以运行多个实例，如今TUN支持多队列了，按照patch的意思，每一个queue对应一个file，那么如果我建立多个Open×××进程实例， 每一个实例均打开tun0设备，那么不管多少个实例，最终的虚拟网卡只有一个，那就是tun0，之前碰到的那些诸如在多个tun网卡间如何分发数据包的问 题(配合以大量的Bridge，Bonding，Policy Routing，ip conntrack，IP MARK等技术)就全部移交给tun网卡本身的多队列调度策略了。下面我们来看下tun网卡的多队列调度策略是怎么实现的，代码都在tun.c，非常简 单，和物理网卡的多队列分发策略类似，那就是针对每一个数据包计算一个hash值，看一下当前的flow entry表中能否找到一个flow的hash值与此相同的，如果找到，就直接设置该flow entry中保存的queue index为队列号，如果没有找到的话，且数据路径是从应用程序模拟TUN接收的话，则创建一个flow entry。尽在tun_flow_update：

static void tun_flow_update(struct tun_struct *tun, u32 rxhash,                 struct tun_file *tfile) {     struct hlist_head *head;     struct tun_flow_entry *e;     unsigned long delay = tun->ageing_time;     u16 queue_index = tfile->queue_index;     if (!rxhash)         return;     else         head = &tun->flows[tun_hashfn(rxhash)];     rcu_read_lock();     /* We may get a very small possibility of OOO during switching, not      * worth to optimize.*/     if (tun->numqueues == 1 || tfile->detached)         goto unlock;     e = tun_flow_find(head, rxhash);     if (likely(e)) {         /* TODO: keep queueing to old queue until it's empty? */         e->queue_index = queue_index;         e->updated = jiffies;     } else {         spin_lock_bh(&tun->lock);         if (!tun_flow_find(head, rxhash) &&             tun->flow_count < MAX_TAP_FLOWS)             tun_flow_create(tun, head, rxhash, queue_index);         if (!timer_pending(&tun->flow_gc_timer))             mod_timer(&tun->flow_gc_timer,                   round_jiffies_up(jiffies + delay));         spin_unlock_bh(&tun->lock);     } unlock:     rcu_read_unlock(); }

对于tun的xmit路径，执行了Linux内核协议栈设备层的ndo_select_queue回调：

static u16 tun_select_queue(struct net_device *dev, struct sk_buff *skb) {     struct tun_struct *tun = netdev_priv(dev);     struct tun_flow_entry *e;     u32 txq = 0;     u32 numqueues = 0;     rcu_read_lock();     numqueues = tun->numqueues;     txq = skb_get_rxhash(skb);     if (txq) {         e = tun_flow_find(&tun->flows[tun_hashfn(txq)], txq);         if (e)             txq = e->queue_index;         else             /* use multiply and shift instead of expensive divide */             txq = ((u64)txq * numqueues) >> 32;     } else if (likely(skb_rx_queue_recorded(skb))) {         txq = skb_get_rx_queue(skb);         while (unlikely(txq >= numqueues))             txq -= numqueues;     }     rcu_read_unlock();     return txq; }

这就是全部。但是我更希望在TUN2PHY的这个路径(tun receive)上按照源IP地址来创建数据流，在PHY2TUN这个路径(tun xmit)上按照目标地址查找数据流，如果找不到则将数据包广播到所有的队列，这么做完全是由于Open×××的特殊性导致的。第一，Open×××的每 一个实例都会携带一系列的Open×××客户端，不同实例的客户端之间没有任何关系，这样，如果Open×××使用多队列的TUN网卡，那么此时的多队列 就不仅仅具有优化意义了，还要具有路由的功能，这就说明Open×××使用的多队列机制额外附加了一个约束，那就是一个流必须始终被hash到同一个队 列，并且还必须是特定那个能处理它的队列。第二，使用单独的IP地址标示数据流而不是传统的5元组标示数据流计算量小了很多，而且对于Open×××而 言，这也足够了，从Open×××解密后发往TUN网卡的数据包，最终要模拟一个网卡接收动作，此时需要记住该数据包的源地址和该Open×××实例之间 的关联，那么所有在tun的xmit路径上发往该IP地址的数据包需要找到这个关联，取出队列号即找到了它对应的file，也就和具体的Open×××实 例对应上了。
       那么原始的多队列TUN驱动的队列调度算法有什么问题呢？话说如果有连续的数据流来自不同的Open×××实例的hash值一致，将会导致同一个flow entry的queue index被频繁update，这些数据流的回程流量在tun的xmit前的select queue中可能就会被定位了错误的queue，导致收到数据包的Open×××实例无法解析。在Open×××的multi.c中的 multi_process_incoming_tun函数中，multi_get_instance_by_virtual_addr将会找不到对应的 multi_instance。
      因此，需要用精确的单一IP地址匹配的方式代替可能冲突的5元组hash，问题是如何来实现之。为每一个queue挂一个路由表是可以的，在tun的 recv路径上使用源IP地址创建路由表，在tun的xmit路径上使用目标IP地址查询路由表。我又一次想到了移植一个路由表到tun驱动，...这真 是太固执了！但是我没有那么做，我所做的很简单，那就是针对一个IP地址做hash运算以便将带有规律的IP地址充分散列开，然后将此hash再进行取 模，将其插入链表，同时保存的还有该IP地址本身以及queue index。具体而言，我的修改如下

4.我的patch-针对Open×××

4.1.定义数据结构

#ifdef O××× enum dir { //来自Open×××的方向     DIR_TUN2PHY = 0, //去往Open×××的方向     DIR_PHY2TUN, }; #endif struct tun_flow_entry {     struct hlist_node hash_link;     struct rcu_head rcu;     struct tun_struct *tun;     u32 rxhash; #ifdef O××× // 保存来自Open×××方向的源地址     u32 key1; //保存来自Open×××方向的目标地址(暂时未用)     u32 key2; #endif     int queue_index;     unsigned long updated; };

4.2.定义关键操作函数

#ifdef O××× /* 通过一个IP地址生成足够散列的hash值  */ static u32 keys_get_hash(u32 *keys) { /*  * 事实上只需要使用一个IP地址做hash即可  * 因为在get_keys中，始终用key[0]来做判定IP：  * 如果是从TUN接收的数据包，key[0]为源IP；  * 如果是发往(xmit)TUN的数据包，key[0]为目标IP。     u32 key_l, key_h;     key_l = keys[1];     key_h = keys[0];     // 保证不管哪个方向的数据包的hash值都一样，     // 所以要对元组进行排序     if (keys[0] < keys[1]) {         key_l = keys[0];         key_h = keys[1];     }     return jhash_2words(key_l, key_h, 0x0); */     return jhash_2words(key[0], 0x01, 0x00); } /* 通过一个IP地址查找hash表  */ static struct tun_flow_entry *tun_flow_find(struct hlist_head *head,                         u32 hash,                             u32 *key) {     struct tun_flow_entry *e;     hlist_for_each_entry_rcu(e, head, hash_link) {         if (likely(e->rxhash != hash)) {             continue;         }         if ((e->key1 == key[0] /*&& e->key2 == key[1]) ||*/             /*(e->key1 == key[1] && e->key2 == key[0]*/)) {             return e;         }     }     return NULL; } /* 在不同的方向上以不同的IP地址作为查找键值  * 按照以下原则get key：  * 1.如果是从Open×××发往TUN的数据包，则根据源IP地址记录该IP地址  *   和Open×××实例之间的映射关系，即和tfile的queue index之间的映射；  * 2.如果是从物理网卡或者本机发往TUN的数据包，我们的目标是找出它该  *   发往哪个tfile的队列，即哪个queue，因此用目标IP地址来查表，如果  *   事先有来自该IP的数据包从Open×××模拟了TUN接收，则肯定能找到。  */ static void get_keys(struct sk_buff *skb,             struct tun_struct *tun,             u32 *key,             int dir) {     switch (tun->flags & TUN_TYPE_MASK) {     case TUN_TUN_DEV:         {             char *buf = skb_network_header(skb);             struct iphdr *hdr = (struct iphdr*)buf;             int i = 0;             if (dir == DIR_TUN2PHY) {                 key[0] = hdr->saddr;                 key[1] = hdr->daddr;             } else {                 key[0] = hdr->daddr;                 key[1] = hdr->saddr;             }         }         break;     case TUN_TAP_DEV:         // TODO         // 对于TAP的模式，我期望使用MAC地址而不是IP地址         break;     } } /* 创建一个flow entry，将定位到的那个IP以及其hash加入，连带着队列号  */ static struct tun_flow_entry *tun_flow_create(struct tun_struct *tun,                           struct hlist_head *head,                           u32 hash,                           u16 queue_index,                           u32 *keys) {     struct tun_flow_entry *e = kmalloc(sizeof(*e), GFP_ATOMIC);     if (e) {         tun_debug(KERN_INFO, tun, "create flow: hash %u index %u\n",               hash, queue_index);         e->updated = jiffies;         e->rxhash = hash;         e->queue_index = queue_index;         e->tun = tun;         e->key1 = keys[0];         // key2字段暂时没有用到         e->key2 = keys[1];         hlist_add_head_rcu(&e->hash_link, head);         ++tun->flow_count;     }     return e; } /* Linux协议栈在xmit一个数据包到dev的时候，会尝试调用其ndo_select_queue回调来  * 将其映射到multiqueue中的某一个，这样便可以在多处理器情形下优化数据包的传输效率  */ static u16 tun_select_queue(struct net_device *dev, struct sk_buff *skb) {     struct tun_flow_entry *e;     struct tun_struct *tun;     struct hlist_head *head;     u32 hash, key[2];     memset(key, 0, sizeof(key));     tun = netdev_priv(dev);     // 按照PHY2TUN的方向获得该数据包的目标IP地址     get_keys(skb, tun, key, DIR_PHY2TUN);     // 将目标IP地址进行散列     hash = keys_get_hash(key);     // 获取该散列对应的冲突链表     head = &tun->flows[tun_hashfn(hash)];     // 寻找和该目标地址对应的flow entry     // 该flow entry一般由TUN2PHY方向的数据包添加，key为源IP     e = tun_flow_find(head, hash, key);     if (unlikely(!e)) {         // 如果没有找到则尝试广播到所有的Open×××进程，由进程进行抉择         return MAX_TAP_QUEUES + 1;     } else {         return e->queue_index;     }     return 0; } #else ... #endif #ifdef O××× /* 该confirm函数是和select_queue类似的，只是这是TUN2PHY这个方向的，  * 之所以叫做confirm是因为它一般用来添加一个flow entry，该flow entry  * 被用来让来自PHY2TUN方向的select queue来查找。  */ static void tun_flow_confirm(struct tun_struct *tun,                 struct sk_buff *skb,                 struct tun_file *tfile) {     struct tun_flow_entry *e;     struct hlist_head *head;     u16 queue_index;     u32 hash, key[2];     rcu_read_lock();     memset(key, 0, sizeof(key));     queue_index = tfile->queue_index;     get_keys(skb, tun, key, DIR_TUN2PHY);     hash = keys_get_hash(key);     head = &tun->flows[tun_hashfn(hash)];     e = tun_flow_find(head, hash, key);     if (unlikely(!e)) {         tun_flow_create(tun, head, hash, queue_index, key);     } else {     }     rcu_read_unlock(); } #endif

4.3.修改recv以及xmit的流程

/* Net device start xmit */ static netdev_tx_t tun_net_xmit(struct sk_buff *skb, struct net_device *dev) {     struct tun_struct *tun = netdev_priv(dev);     int txq = skb->queue_mapping;     struct tun_file *tfile; #ifdef O×××     int i = 0; #endif ...     skb_orphan(skb);     nf_reset(skb); #ifdef O×××     if (skb->queue_mapping != MAX_TAP_QUEUES + 1) {         goto out;     }     // 没有找到flow entry，则不create，而是广播到所有的Open×××进程。     // 注意，create flow entry这个操作只在TUN2PHY一个方向进行，因为     // 只有那里知道一个数据包的源IP地址和对应的Open×××进程的queue index     // 之间的关系，在PHY2TUN这个方向，如果找不到目标地址对应的flow entry     // 那么除了查类似路由表之类的表之外是无法找到这个对应关系，而我没有     // 选择查表的方式，直接选择了广播，也是有原因的，详见正文。     for (i = 0; i < tun->numqueues; i++) {             struct sk_buff *bskb = skb_copy(skb, GFP_ATOMIC);         /* Enqueue packet */         tfile = rtnl_dereference(tun->tfiles[i]);         skb_queue_tail(&tfile->socket.sk->sk_receive_queue, bskb);         /* Notify and wake up reader process */         if (tfile->flags & TUN_FASYNC)             kill_fasync(&tfile->fasync, SIGIO, POLL_IN);         wake_up_interruptible_poll(&tfile->wq.wait, POLLIN |                        POLLRDNORM | POLLRDBAND);     }     kfree_skb(skb);     rcu_read_unlock();     return NETDEV_TX_OK; out: #endif

4.4.关于为何要广播

如果存在一个从Open×××后端主动发起的一个流量，它是首先经过tun的xmit路径 的，数据的目标是Open×××客户端，此时很显然查不到任何的flow entry，因为还没有任何数据包从tun的recv路径中经过从而创建flow entry，又或者虽然流量是Open×××客户端主动发起的，但是后端服务器迟迟不回复，导致flow entry被删除，然后回程数据包便成了找不到flow entry的数据包。如何将这类数据包导入到正确的Open×××实例，即导入到正确的queue index就是一个问题。
       由于我的设计是将一个TUN recv方向的源IP地址或者TUN xmit方向的目标IP地址作为一个数据流识别的要素，所以使用路由表是常规的选择，对于匹配不到路由项 的情况，一般采用默认路由给与转发，如果没有配置默认路由，将直接丢弃。因此如果采用路由表的方案，我们势必要创建一个可以转发所有流量的Open××× 实例作为”默认queue“，但这是不可能的。因此我们就必须针对每一个Open×××实例所代表的队列设置一个通配路由，但是这就限制了Open××× 实例们分配虚拟IP地址或者更复杂的，限制了针对网到网×××的网段IP地址，同时，路由查找需要保存的东西过多，一旦有查找不到的情况，通配路由的匹配 消耗过大，抵消了采用多队列TUN网卡的优势(还不如使用标准的Linux原生路由表匹配多个TUN网卡网段呢)，所以采用广播的方式，虽然这种方式可能 连累了无关的Open×××实例，但是它也只需要做一个地址验证，然后简单的丢弃即可。
       对于单独的一个Open×××实例，它所统领的IP地址范围或者网段范围相对于全局的路由表来讲是很小的，因此广播无法匹配flow entry的数据包可以有效减少单个包的延迟，特别是在多处理器情况下，单个不匹配路由表的包的查找全局路由表的延迟将被平摊到多个处理器核心同时查找小 范围的路由表上，因此采用广播方式在多处理器情况下是一种简单却又高效的做法。

4.5.一个关于Intel 82599的注释

不知你有没有注意到关于tun_select_queue的注释，写得太好了：

/* We try to identify a flow through its rxhash first. The reason that  * we do not check rxq no. is becuase some cards(e.g 82599), chooses  * the rxq based on the txq where the last packet of the flow comes. As  * the userspace application move between processors, we may get a  * different rxq no. here. If we could not get rxhash, then we would  * hope the rxq no. may help here.  */

为何TUN不使用数据包可能已经被保存的队列号而必须坚持要自己算一个呢？很显然，TUN是希望一个特定的数据流始终对应到一个特定 的queue index，并且这种对应是自学习的，且看在tun_flow_update中，只要一个流的tfile，即queue index改变了，每次都要更新一个流的queue index，这是为了让回程数据流使用。看出来这是什么了吗？这不就是类似Intel 82599的ATR机制吗？仔细盯住那tun_flow_update：

if (likely(e)) {                 /* TODO: keep queueing to old queue until it's empty? */                 e->queue_index = queue_index;                 e->updated = jiffies; }

这个不就跟上面提到的ixgbe_atr所一致吗？是的，但是这也意味着，每一个数据流的队列会时刻变化，回程流量的处理队列取决于上一次正向流量的处理队列，而正向流量的处理队列是可以发生变化的。
       Intel 82599的ATR就是这样，因此一个数据流的数据包在tun xmit的时候，其queue index取决于该流数据包最后一个发出时对Intel 82599网卡的编程结果，正如注释所述，它是取决于CPU的，而应用是会在CPU之间迁移的，所以它并不是固定的，TUN为了尽可能使同一个流量 hash到同一个tfile，即queue，所以坚持自己按照自己的固定算法算一个来使用。TUN应用和Intel 82599之间的PK，尽在tun_select_queue的注释啊！只可惜，被我的修改给解决了，二者正式联姻。
       之所以TUN的xmit路径必须通过算法保证流被hash到同一个queue，是因为它不像socket那样有一个socket元组查找的动作，一个数据 包，使用其元组而不是队列信息按照特定的查找算法就能找到一个socket，但是对于TUN xmit的流量而言，它根本就不经协议栈，所以就只能通过数据包本身的特性做hash，又因为hash会存在冲突，所以如果需要精确查找的话，还是不能仅 仅hash了事的。

5.使用效果

按照上面的描述修改tun驱动后，还需要修改Open×××的源码，这里就不细讲了，简单来说 就是在tun的ioctl时，加入多队列的支持。随后，启动N个Open×××进程实例，侦听不同的端口，随后加载我最近完成的一个不用iptables 以及ipvs的UDP负载均衡模块，然后注意，所有Open×××实例需要在同一个IP地址pool中分配虚拟IP地址。
       现在用多个OpenVP客户端连接这个服务器，会发现流量被分担到了多个实例上，由于tun驱动记载了流信息，所以能保证一个流量从那个Open×××实例发出，其回程流量便从哪个Open×××被接收并处理。

6.后记与后继

我对tun多队列支持的修改补丁仅仅是一种对流识别的弱化，仅仅用一个IP地址简单而高效地识别流并且精确匹配流(计算两无疑是小了很多，但然，参与的元组越少，计算量就越小)。但是还是感觉不能上桌！
       另外，我没有将这个支持多队列的TUN驱动移植到Linux 2.6.32这个老版本的内核上，因为没有意义，可能永远也不会用到，毕竟意念的东西是不能作为教堂里的圣物的，只是，仍在垃圾堆里有点不舍得，所以姑且 放在网上，如果有人能依此思想继续而为之或者置于github而忍受骂嘴，我将感激不尽！
       酒是什么？酒就是越晕越上劲越想喝；问题是什么，问题就是越复杂越上劲越想解决。我想，是时候实现Open×××的多线程了！看完荷兰VS巴西之后(我不 是球迷，也不算伪球迷，只是喜欢失败的那一方，如果是失败的两方之间的PK，那就更加悲凉了，最最悲凉的，不说了)，小睡一觉，然后继续去麦德龙。