Linux Kernel

Linux 网络流量控制(零)

我会在下周举行的 LinuxCon North America 上讲一下最近在做的 Linux 网络流量控制(traffic control),有机会来参加的朋友欢迎前来捧场!不能参加的朋友也可以在这里看到我的 slides。

网络流量控制是一个非常大的话题,不可能在一个小时的时间内全部讲完,只能选择其中比较重要的来讲。而且它很重要,直接关乎网络性能,可是讲解这部分代码的书几乎没有,已有的讲 Linux 内核网络的书基本上都跳过了这一个部分,所以我也会陆续在这里详细分析一下这些代码,一是弥补这个缺口,二是弥补讲稿中的不足。

skbuff 内存模型

众所周知,struct sk_buff 是 Linux 内核网络子系统中最重要的一个结构体,它是内核对网络数据包的一个抽象表示。要了解 Linux 网络子系统除了了解网络协议之外,了解内核如何表示和操作数据包也是至关重要的。Linux 内核中的 struct sk_buff (以下简称 skb)提供了一套非常复杂的内存模型,也对它进行了大量的优化,这也是为什么 Linux 网络如此高效。

我们从最简单的开始,分配一个最普通的 skb:

内核分配 skb 的函数是 __alloc_skb(),它有很多种包装供不同的场景使用。如上图所示,在这里我们分配了两部分内存:1) skb struct 本身,也叫元数据( meta data);2) 实际存放网络数据包的内存。这里你可以把 skb 看作是一堆指针,这些指针指向一块内存的不同区域。下面我们会看到,很多时候我们都是对指针本身进行操作。

注意:其实严格的说上图中所示的指针并不一定都是指针,Linux 内核进行了优化。在 64 位系统上,一个指针也是64位,储存指针的开销太大。而数据包本身不可能太大(以太网 MTU 是 1500 字节,就算是 jumbo frame 也才 9000 字节),因此 Linux 内核仅仅把 head 和 data 保存为指针,其它的只要存储相对于它们的偏移即可。下面的所有图中把它们表示为指针仅仅是为了方便。

而一个完整的网络数据包在内存中的表示通常有四个部分:

1) head room,位于 skb->head 和 skb->data 之间,也就是存放网络协议头的地方,比如 TCP,IP 头,以太网头都是位于此;

2) 用户数据,通常由应用层通过系统调用填充,介于 skb->data 和 skb->tail 之间;

3) tail room,介于 skb->tail 和 skb->end 之间,这部分是内核在用户数据后面填充的一部分;

4) skb->end 之后存放的是一个特殊的结构体 struct skb_shared_info,下面会讲到它。

刚分配出来的 skb 除了 skb->end 指向末尾的 struct skb_shared_info,其它指针都指向了开始处。通常第一步就是初始化 head room,调用 skb_reserve() 这个函数,如下图所示:

比如 TCP 层要发送一个数据包,head room 至少要是 tcphdr + iphdr + ethhdr。然后在协议头的后面开始预留数据区,调用的函数是 skb_put(),如下图所示:

到此为止,前面提到的四个部分才全部初始化完毕,通常情况下,这些操作要么是由传输层完成(发送),要么是由网卡驱动完成(接收)。一点一点往里填充数据或者向外读取数据则是各层协议的事情。数据包入栈时(即接收),数据是一层一层往里读取,协议头是一层一层剥掉。数据包出栈时(发送),协议头则是一层一层往外填写。

内核提供的剥掉协议头的操作函数是 skb_pull(),如名字所示,它是往下拉 skb->data:

类似地,往外推 skb->data 的操作叫做 skb_push():

很形象吧?

好,终于到前面一直默默无闻的 skb_shared_info 出场了。想象这么一种常见的情况:我们用 tcpdump 捕捉一个网卡收到的数据包。此时数据包入栈后会有两个部分同时进行读:一是协议栈本身,另一个就是 tcpdump 了。这种情况下要不要完全复制一份 skb 呢?没有必要,因为两部分都是读,网络数据本身是不变的,变的只是 strcut sk_buff 里面的指针,也就是说,我们只要复制一份 skb 让它指向同样的内存区域就行了!这正是 skb_clone() 所做的:

如图所示,skb_shared_info 此时记录了一些变化,dataref 变成了2,代表有两个 skb 同时指向这块内存区域。由此可见,skb_shared_info 保存的是多个 skb 之间共享的,但又不属于网络数据的数据(也就是不会被传输的数据),所以才放在 skb->end 之后啊。

这还没完,Linux 内核开发者觉得还不够,每次 clone 都还要分配一个 skb 结构体,对于要 clone 很多次的情形还可以进行优化——使用 fast clone(缩写为fclone)。fclone 很有技巧性,它在分配 skb 的 cache 里做了手脚,每次分配 skb 时,它都是分配一对,一个紧紧地跟在另一个后面,如下图所示:

不用的时候你完全看不到它,用的时候通过 skb+1 就能找得到!当然了,它需要在 skb 结构体里保存一些状态信息表明这部分到底有没有用到。

在写的情况下我们还是要完全拷贝 skb 及其数据的,调用 skb_copy() :

到此为止都比较简单,我们假设了所有的数据都是放在 skb->head 和 skb->end 之间,也就是所谓的线性(linear)。世界要是这么简单就好了,可惜现实远比这复杂。内核至少还提供了另外三种非线性的 skb 模型。

一种是网卡驱动常用的模型,数据存放在物理页面的不同位置,skb_shared_info 里有一个数组,存放一组 (页面、偏移、大小) 的信息,用来记录这些数据:

另一种是组装 IP 数据包分片(fragment)时用到的 frag_list 模型:

分片的数据有各自的 skb 结构体,它们通过 skb->next 链接成一个单链表,表头是第一个 skb 的 shared_info 中的 frag_list。

最后一种是 GSO 进行分段(segmentation)用到的一种模型,当一个大的 TCP 数据包被切割成几个 MTU 大小的数据时,它们也是通过 skb->next 链接到一起的:

与分片不同的是,相关的信息是记录在最前面一个 skb 的 skb_shared_info 里面的 gso_segs 和 gso_size 里。

正因为存在以上各种复杂的模型,很多 skb API 的实现(比如 skb_segment())非常复杂,其大部分代码都是用来处理非线性的这几种情况,这使得 skbuff.c 里的很多代码都不容易读懂。希望本文能够对你理解这部分代码有所帮助。

参考资料:

1. http://vger.kernel.org/~davem/skb_data.html

Ingress traffic control

相信很多人都知道 Linux 内核很难做 ingress 流量控制的,毕竟发送方理论上可以无限制地发送包到达网络接口。即使你控制了从网络接口到达协议栈的流量,你也很难从根源上控制这个流量。

利用 Linux 内核你可以轻松地完成前者,即控制从网络接口到达协议栈的流量。这个是通过一个叫做 ifb 的设备完成的,这个设备如此不起眼以至于很多人不知道它的存在。

它的使用很简单,加载 ifb 模块后,激活 ifbX 设备:

modprobe ifb numifbs=1
ip link set dev ifb0 up # ifb1, ifb2, ... 操作相同
`</pre>

然后就要通过 ingress tc filter 把流入某个网络接口的流量 redirect 到 ifbX 上:
<pre>`tc qdisc add dev eth0 handle ffff: ingress
tc filter add dev eth0 parent ffff: protocol ip u32 match u32 0 0 action mirred egress redirect dev ifb0

ingress 这个 qdisc 是不能加 class,但是我们这里使用了 ifb0,所以就可以在 ifb0 设备上添加各种 tc class,这样就和 egress 没有多少区别了。

ifb 的实现其实很简单,因为流入网络接口的流量是无法直接控制的,那么我们必须要把流入的包导入(通过 tc action)到一个中间的队列,该队列在 ifb 设备上,然后让这些包重走 tc 层,最后流入的包再重新入栈,流出的包重新出栈。看代码一目了然:

[c]

    while ((skb = __skb_dequeue(&amp;dp-&gt;tq)) != NULL) {
            u32 from = G_TC_FROM(skb-&gt;tc_verd);

            skb-&gt;tc_verd = 0;
            skb-&gt;tc_verd = SET_TC_NCLS(skb-&gt;tc_verd);

            u64_stats_update_begin(&amp;dp-&gt;tsync);
            dp-&gt;tx_packets++;
            dp-&gt;tx_bytes += skb-&gt;len;
            u64_stats_update_end(&amp;dp-&gt;tsync);

            rcu_read_lock();
            skb-&gt;dev = dev_get_by_index_rcu(dev_net(_dev), skb-&gt;skb_iif);
            if (!skb-&gt;dev) {
                    rcu_read_unlock();
                    dev_kfree_skb(skb);
                    _dev-&gt;stats.tx_dropped++;
                    if (skb_queue_len(&amp;dp-&gt;tq) != 0)
                            goto resched;
                    break;
            }
            rcu_read_unlock();
            skb-&gt;skb_iif = _dev-&gt;ifindex;

            if (from &amp; AT_EGRESS) {
                    dev_queue_xmit(skb);
            } else if (from &amp; AT_INGRESS) {
                    skb_pull(skb, skb-&gt;dev-&gt;hard_header_len);
                    netif_receive_skb(skb);
            } else
                    BUG();
    }

[/c]

这里有两个不太明显的地方值得注意:

1) 不论流入还是流出,tc 层的代码都是工作在 L2 的,也就是说代码是可以重入的,尤其是 skb 里的一些 header pointer;

2) 网络设备上的 ingress 队列只有一个,这也是为啥 ingress qdisc 只能做 filter 的原因,可以看下面的代码:

[c]
static int ing_filter(struct sk_buff skb, struct netdev_queue rxq)
{
struct net_device dev = skb->dev;
u32 ttl = G_TC_RTTL(skb->tc_verd);
int result = TC_ACT_OK;
struct Qdisc
q;

    if (unlikely(MAX_RED_LOOP %d)n",
                                 skb-&gt;skb_iif, dev-&gt;ifindex);
            return TC_ACT_SHOT;
    }

    skb-&gt;tc_verd = SET_TC_RTTL(skb-&gt;tc_verd, ttl);
    skb-&gt;tc_verd = SET_TC_AT(skb-&gt;tc_verd, AT_INGRESS);

    q = rxq-&gt;qdisc;
    if (q != &amp;noop_qdisc) {
            spin_lock(qdisc_lock(q));
            if (likely(!test_bit(__QDISC_STATE_DEACTIVATED, &amp;q-&gt;state)))
                    result = qdisc_enqueue_root(skb, q);
            spin_unlock(qdisc_lock(q));
    }

    return result;

}

static inline struct sk_buff handle_ing(struct sk_buff skb,
struct packet_type *pt_prev,
int
ret, struct net_device orig_dev)
{
struct netdev_queue
rxq = rcu_dereference(skb->dev->ingress_queue);

    if (!rxq || rxq-&gt;qdisc == &amp;noop_qdisc)
            goto out;

    if (*pt_prev) {
            *ret = deliver_skb(skb, *pt_prev, orig_dev);
            *pt_prev = NULL;
    }

    switch (ing_filter(skb, rxq)) {
    case TC_ACT_SHOT:
    case TC_ACT_STOLEN:
            kfree_skb(skb);
            return NULL;
    }

out:
skb->tc_verd = 0;
return skb;
}
[/c]

而经过 tc action 后是导入到了 ifb 设备的发送队列,见 net/sched/act_mirred.c 的 tcf_mirred() 函数:

[c]
//…
skb2->skb_iif = skb->dev->ifindex;
skb2->dev = dev;
err = dev_queue_xmit(skb2);
[/c]

也就是说这样就会有多个队列了,可以添加 class 了。:) 这大体也是 ingress traffic control 如何工作的了,可见 ifb 的存在既简单又巧妙地粘合了 egress 上的流量控制。

正如本文一开始讲到的,即使用 ifb 我们所做的流量控制仍然有限,很难从根本上控制发送方的速率。如果双方是通过交换机连接的话,或许通过 L2 上的一些协议可以控制速率,而如果中间经过路由器,那么所能做的就更加有限,只能期待传输层的协议进行控制,而不是靠传输层自身感受到丢包的多少去自动调整速率,因为这可能会花很长时间。

参考资料:

1. http://serverfault.com/questions/350023/tc-ingress-policing-and-ifb-mirroring
2. http://stackoverflow.com/questions/15881921/why-tc-cannot-do-ingress-shaping-does-ingress-shaping-make-sense

关于 OVS GRE tunnel

在 korg 内核的 openvswitch 支持 GRE 之前,我们都是用内核原生的 GRE tunnel 来配置,而现在, korg 内核中的 openvswitch 也已经支持 GRE tunnel 了。有兴趣的可以看 openvswitch: Add tunneling interface.openvswitch: Add gre tunnel support. 这两个 commit。

其实在 OVS 中添加 GRE 很简单,它无非就是把对 GRE 头和外部 IP 头的一些操作从原来的代码中抽象出来,做成内核“库函数”的形式,然后 OVS 中就可以直接调用它们了。难的是要从旧的 ip_gre 模块代码中抽象出这些“库函数”。详见 GRE: Refactor GRE tunneling code.

值得注意的是,OVS GRE tunnel 没有注册网络设备,也就是说你无法通过 ip link 看到它,它只是一个 vport 而已,所以能通过 ovs-vsctl show 可以看到。这是故意这么设计的,虽然这简化了用户的操作,但刚注意到时难免会感觉有些奇怪。

网上最流行的一篇讲解 OVS GRE tunnel 配置的教程是这篇文章,根据它我做了如下配置:

ovs-vsctl add-br grebr0
ovs-vsctl add-br phybr0
ovs-vsctl add-port phybr0 p1p1
ovs-vsctl add-port phybr0 tep0 — set Interface tep0 type=internal
ifconfig tep0 192.168.88.1/24
ifconfig p1p1 0.0.0.0
ovs-vsctl add-port grebr0 vnet0
ovs-vsctl add-port grebr0 gre1 — set Interface gre1 type=gre options:remote_ip=192.168.88.2

但是仔细分析一下,其实完全没有必要使用两个 bridge,通过 gre1 的包其实可以直接进入 p1p1,即最后的物理网卡。所以优化后的配置如下:

ovs-vsctl add-br grebr0
ifconfig p1p1 192.168.88.1/24
ovs-vsctl add-port grebr0 vnet0
ovs-vsctl add-port grebr0 gre1 — set Interface gre1 type=gre options:remote_ip=192.168.88.2

通过 GRE tunnel 的包是重新注入网络栈中的,所以它们会直接流向 p1p1,最终流向物理层。

注意,这并没有结束。虽然通过这个配置你已经可以 ping 通对方 host 上的 VM 了,但是,如果你运行 netperf 测试的话,你会发现吞吐量非常低。这也是网络上的教程没有提到的地方。

这里的原因是从 vnet0 里出来数据包很多是 MTU 的大小,我这里是1500。而经过 GRE tunnel 后外面又添加了 GRE 头和外层的 IP 头,所以包就会大于 1500。而物理网卡的 MTU 也是 1500!并且,这些包本身并不是 GSO 的,所以这些包最终会被 IP 层分片(fragment),所以性能非常差!

这里有两种解决方法:

1) 把 VM 里的网卡 MTU 调小,比如 1400,这样 host 上的 GRE 加上额外的头也不会超过 1500;

2) 让 VM 里发出来的包依旧维持 GSO,这样 host 上收到的包也是 GSO,它们最终会被分段(segment),而不是分片(fragment)。这个可以通过给 qemu 传递 vnet_hdr=on 来完成(我没有试过,仅分析了源代码)。

关于这个问题的进一步讨论可以看我提的问题

一个绝妙的内核 exploit

最近 Linux 内核爆出了一个严重的安全漏洞,非root用户可以通过该漏洞的 exploit 获取root权限。这并不罕见,值得一提的是这个补丁看起来如此平常以至于我们绝大多数人都不会以为这是安全问题。

先看这个问题的补丁,就是下面这个:

  static int perf_swevent_init(struct perf_event *event)
 {
-    int event_id = event->attr.config;
+    u64 event_id = event->attr.config;

     if (event->attr.type != PERF_TYPE_SOFTWARE)
         return -ENOENT;
我们第一眼的感觉就是这大概只是修复了编译器报的一个小警告吧,怎么会引起如此严重的安全问题呢? 在没打补丁的代码中 event_id 是个**带符号**的整型,而且就在下面不远处的两行代码中只检查了其上界: [c] if (event_id >= PERF_COUNT_SW_MAX) return -ENOENT; [/c] 而如果传递进来的 event->attr.config 值正好设置了符号位,那么 event_id 就会变成负值,而且能躲过上面的检查。 负值意味着什么呢?再继续看后面的代码: [c] if (!event->parent) { int err; err = swevent_hlist_get(event); if (err) return err; atomic_inc(&perf_swevent_enabled[event_id]); event->destroy = sw_perf_event_destroy; } [/c] 意味着数组越界!这时你应该身上开始冒冷汗了。继续,数组 perf_swevent_enabled[] 在 RHEL6 上的定义是: [c] atomic_t perf_swevent_enabled[PERF_COUNT_SW_MAX]; [/c] 而 atomic_t 基本上就是int,也就是说 perf_swevent_enabled[] 是整型数组,那么用 event_id 访问该数组时会把 event_id 的值乘以4再加上数组的起始地址。很简单哈! 好,通过 System.map 文件我们可以得到 perf_swevent_enabled 的地址:
ffffffff81f360c0 B perf_swevent_enabled

那么当 event->attr.config == 0xffffffff (即有符号的-1)时,在 x86_64 上面我们最终会得到:

0xffffffffffffffff * 4 + 0xffffffff81f360c0 == 0xFFFFFFFF81F360BC

同理,当 event->attr.config == 0xfffffffe 时我们得到:

0xfffffffffffffffe * 4 + 0xffffffff81f360c0 == 0xFFFFFFFF81F360B8

所以上述的 atomic_inc() 其实增加的是前面两个地址中存放的值,而这俩地址都指向内核空间(参见 Documentation/x86/x86_64/mm.txt)!这时你应该感到紧张了。。。

后面更有趣的事情发生在 sw_perf_event_destroy() 函数中,它是在 perf_event_open() 返回的 fd 被关闭时被调用,RHEL6 上其定义如下:

[c]
static void sw_perf_event_destroy(struct perf_event *event)
{
u64 event_id = event->attr.config;

    WARN_ON(event-&gt;parent);

    atomic_dec(&amp;perf_swevent_enabled[event_id]);
    swevent_hlist_put(event);

}
[/c]

很明显的不同是,event_id 这次是无符号的类型。那么,同上,当 event->attr.config == 0xffffffff 时我们得到:

0xffffffff * 4 + 0xffffffff81f360c0 == 0x0000000381F360BC

当 event->attr.config == 0xfffffffe 时我们得到:

0xfffffffe * 4 + 0xffffffff81f360c0 == 0x0000000381F360B8

所以这里的 atomic_dec() 实际上减小的是用户空间地址内的值。

上面是“基础知识”,带着这些知识我们看 exploit 代码究竟做了什么,代码片段如下:

[c]

define BASE 0x380000000

define SIZE 0x010000000

assert((map = mmap((void)BASE, SIZE, 3, 0x32, 0,0)) == (void)BASE);
memset(map, 0, SIZE);
sheep(-1); sheep(-2); // sheep will just invoke perf_event_open
// syscall with attr.config set to the param
for (i = 0; i < SIZE/4; i++) if (map[i]) {
assert(map[i+1]);
break;
}
[/c]

它首先会 mmap() 起始地址是 0x380000000 的一块内存区域。然后分别以 attr.config 为 -1 和 -2 调用两次 perf_event_open()。根据前面的计算,它实际上分别增加了 0xFFFFFFFF81F360BC 和 0xFFFFFFFF81F360B8 两处内存的值,减少了 0x0000000381F360BC 和 0x0000000381F360B8 的值。后面的 for 循环则是找出被减少的内存地址,这样一来也就可以算出 perf_swevent_enabled[] 数组的地址(System.map 并不总是存在,如果存在而且可读我们当然可以直接去读这个值)。

知道这个地址我们就可以操纵内核中某处的32bit的值,把其值加一。正因为如此,作者巧妙地选择了中断描述符表——一个16字节描述符的数组,它的地址可以通过 sidt 指令获取。它其中的描述符结构定义如下:

Offset     Size     Description
0     2     Offset low bits (0..15)
2     2     Selector (Code segment selector)
4     1     Zero
5     1     Type and Attributes (same as before)
6     2     Offset middle bits (16..31)
8     4     Offset high bits (32..63)
12     4     Zero

这里最有趣的是 offset 为8 的地方,在 x86_64 上面其值为 0xffffffff。作者选择的中断描述符是 0x4,所以相对于中断描述符表它的偏移实际上是 0x48。现在的任务就成了通过 perf_swevent_enabled[] 来计算出该中断描述符中偏移为8的内存地址,并对其加一!下面的代码就是做的这个工作:

[c]
sheep(-i + (((idt.addr&0xffffffff)-0x80000000)/4) + 16);
[/c]

i 是我们前面在 for 循环中搜到的 perf_swevent_enabled[] 的一个偏移,idt.addr 是中断描述符表的绝对内核地址,取其低32位并减去 0x80000000 是为了得到低28位作为偏移,除以4是因为数组是int,最后加的16就是 0x4 中断描述符中的偏移(4已经除去了),所以最终sheep()里面的参数就是我们想要的偏移,这样以来内核就替我们把 0x4 中断描述符中的偏移为 8 的 0xffffffff 加上了1,也就成了0,也就成了用户空间的地址!所以后面的 int 0x4 其实就会跳转到用户空间早已经设置好的代码!!!

而这段代码比较生涩,但其意思就是更改当前进程的 uid/gid 为0来提升权限,所以最终取得一个有 root 权限的 shell!整个攻击大功告成!

注:上面的链接可能不能用,exploit 代码也可以在这里看到:https://gist.github.com/onemouth/5625174

两个精彩的比喻

我们知道,计算机中有很多概念并不容易理解,有些时候一个好的比喻能胜过很多句解释。下面两个是我看到的两个很精彩的比喻,拿出来和大家分享一下。

第一比喻是关于吞吐量(throughput)和延迟(latency)的。如果你要搞网络性能优化,这两个概念是你必须要知道的,它们看似简单实则不是。我相信包括我在内的很多人都曾经认为大的吞吐量就意味着低延迟,高延迟就意味着吞吐量变小。下面的比喻可以解释这种观点根本不对。该比喻来自这里,我来做个大体意译(非逐字翻译)。

我们可以把网络发送数据包比喻成去街边的 ATM 取钱。每一个人从开始使用 ATM 到取钱结束整个过程都需要一分钟,所以这里的延迟是60秒,那吞吐量呢?当然是 1/60 人/秒。现在银行升级了他们的 ATM 机操作系统,每个人只要30秒就可以完成取款了!延迟是 30秒,吞吐量是 1/30 人/秒。很好理解,可是前面的问题依然存在对不对?别慌,看下面。

因为这附近来取钱的人比较多,现在银行决定在这里增加一台 ATM 机,一共有两台 ATM 机了。现在,一分钟可以让4个人完成取钱了,虽然你去排队取钱时在 ATM 机前还是要用 30 秒!也就是说,延迟没有变,但吞吐量增大了!可见,吞吐量可以不用通过减小延迟来提高。

好了,现在银行为了改进服务又做出了一个新的决定:每个来取钱的客户在取完钱之后必须在旁边填写一个调查问卷,用时也是30秒。那么,现在你去取钱的话从开始使用 ATM 到完成调查问卷离开的时间又是 60 秒了!换句话说,延迟是60秒。而吞吐量根本没变!一分钟之内还是可以进来4个人!可见,延迟增加了,而吞吐量没有变。

从这个比喻中我们可以看出,延迟测量的是每个客户(每个应用程序)感受到的时间长短,而吞吐量测量的是整个银行(整个操作系统)的处理效率,是两个完全不同的概念。用作者的原话说是:

In short, the throughput is a function of how many stages are in parallel while latency is a function of how many are in series when there are multiple stages in the processing. The stage with the lowest throughput determines the overall throughput.
正如银行为了让客户满意不光要提高自身的办事效率外,还要尽量缩短客户在银行办事所花的时间一样,操作系统不光要尽量让网络吞吐量大,而且还要让每个应用程序发送数据的延迟尽量小。这是两个不同的目标。

另外一个比喻是解释信号量(semaphore)和互斥锁(mutex)的区别。该比喻最初来自这里,我先翻译一下,然后对它做个改进。

互斥锁是一把公共厕所的钥匙。一个人使用厕所的时候可以拿到这把钥匙,用完之后把这把钥匙交给排队的下一个人。

信号量是没有人使用的厕所的钥匙数量,所有厕所的钥匙都一样。比如有4个厕所有相同的钥匙和锁。信号量的值就是钥匙的数量,一开始是4。当进来一个人的时候数量就是少一个,如果4个厕所都满了,信号量就成0了,出去一个人就增加1,并把钥匙交给排队的下一个人。

这个比喻并不是太好,尤其是它无法解释 二元(binary)信号量和互斥锁的区别!我把这个比喻做了改进。互斥锁的比喻还是和上面一样,需要指出的是,当你拿到那把钥匙的时候你就是它的拥有者(owner),别人是无法打开厕所门的。

而信号量到底是什么呢?它就是一个大的公共厕所,里面有若干个位置,外面的大门口有一个可以翻动牌子写着“已满”和“可用”,当里面还有空的位置的时候,进去的人不用翻动这个牌子,直到没有位置时最后一个进去的人必须把它设成“已满”,这时后面的人必须排队等候,然后出去的人必须把牌子翻到“可用”,如果需要的话。

很好理解对嘛?那么它怎么解释二元信号量呢?也就是当这个厕所里面只能容纳一个人的时候,每个人进去的时候都要把门口的牌子翻到“已满”,出去的时候翻到“可用”。它和互斥锁的区别马上就可以看出来了,翻动的牌子在外面可以被别人翻的,而锁住的锁只有拿钥匙的人才可以开!

当然了,信号量之所以翻译成“信号”,还是有道理的,因为它(厕所门口的牌子)标示的是资源(厕所空位)的状态,而互斥锁就是锁,它实实在在地锁住了资源。这在生产者消费者的情况下区别更明显。

深入理解 VXLAN

VXLAN 是非常新的一个 tunnel 技术,它是一个 L2 tunnel。Linux 内核的 upstream 中也刚刚加入 VXLAN 的实现。相比 GRE tunnel 它有着很的扩展性,同时解决了很多其它问题。

一,GRE tunnel 的不足

网络很多介绍 VXLAN 的文章都没有直接告诉你相比较 GRE tunnel,VXLAN 的优势在哪里,或者说 GRE tunnel 的不足在哪里。为了更好的了解 VXLAN,我们有必要看一下 GRE tunnel 的不足。

在我前面写的介绍 GRE tunnel 的文章中,其实并不容易看出 GRE tunnel 的不足之处。根本原因是图中给出的例子不太好,只有两个网络的话 GRE tunnel 的不足凸显不出来,让我们看看有三个网络的情况如何用 GRE tunnel 互联,如下图所示:

这下子就很明显了,要让这三个网络互联,我们需要建立三个 GRE tunnel。如果网络数量再增长,那么需要的 tunnel 数量更多。换句话说,GRE tunnel 的扩展性太差,从根本上讲还是因为它只是一个 point to point 的 tunnel。

二,VLAN 的不足

其实 VLAN 在某种程度上也可以看作一个 L2 over L2 的 tunnel,只不过它多了一个新的 VLAN header,这其中有12 bit 是 VLAN tag。所以 VLAN 的第一个不足之处就是它最多只支持 4096 个 VLAN 网络(当然这还要除去几个预留的),对于大型数据中心的来说,这个数量是远远不够的。

第二个不足就是,VLAN 这个所谓的 tunnel 是基于 L2 的,所以很难跨越 L2 的边界,在很大程度上限制了网络的灵活性。同时,VLAN 操作需手工介入较多,这对于管理成千上万台机器的管理员来说是难以接受的。

三,VXLAN 的引入

VXLAN 是 Virtual eXtensible LANs 的缩写,所以顾名思义,它是对 VLAN 的一个扩展,但又不仅限于此。

从数量上讲,它确实把 12 bit 的 VLAN tag 扩展成了 24 bit,所以至少暂时够用的了。从实现上讲,它是 L2 over UDP,它利用了 UDP 同时也是 IPv4 的单播和多播,可以跨 L3 边界,很巧妙地解决了 GRE tunnel 和 VLAN 存在的不足,让组网变得更加灵活。

四,VXLAN 的实现

VXLAN 的配置可以参考内核文档 Documentation/networking/vxlan.txt,本人目前还没有环境测试,所以只能做一些代码分析了。

Linux 内核中对 VXLAN 的实现是在 drivers/net/vxlan.c 源文件中,是由 Stephen Hemminger (iproute2 的维护者)完成的。代码质量相当高,所以可读性也很好,强烈推荐阅读一下。

看代码之前先看 VXLAN 的头是一个怎样的结构,如下图所示(图片来自参考资料4):

好了,现在我们可以看代码了。先看发送端,vxlan_xmit() 函数。首先需要说的是发送之前内核会检查目的地址,如果是L2 multicast,那么应该发送到 VXLAN group 组播地址,否则,如果 MAC 地址是已知的,直接单播到对应的 IP;如果未知,则广播到组播地址。代码如下,比文档还要好读。:-)

[c]
static __be32 vxlan_find_dst(struct vxlan_dev vxlan, struct sk_buff skb)
{
const struct ethhdr eth = (struct ethhdr ) skb->data;
const struct vxlan_fdb *f;

    if (is_multicast_ether_addr(eth-&gt;h_dest))
            return vxlan-&gt;gaddr;

    f = vxlan_find_mac(vxlan, eth-&gt;h_dest);
    if (f)
            return f-&gt;remote_ip;
    else
            return vxlan-&gt;gaddr;

}
[/c]

剩下的基本上就是一层一层的往外添加头了,依次添加 VXLAN header,UDP header,IP header:
[c]
//…
vxh = (struct vxlanhdr ) __skb_push(skb, sizeof(vxh));
vxh->vx_flags = htonl(VXLAN_FLAGS);
vxh->vx_vni = htonl(vxlan->vni <dest = htons(vxlan_port);
uh->source = htons(src_port);

    uh-&gt;len = htons(skb-&gt;len);
    uh-&gt;check = 0;

    __skb_push(skb, sizeof(*iph));
    skb_reset_network_header(skb);
    iph             = ip_hdr(skb);
    iph-&gt;version    = 4;
    iph-&gt;ihl        = sizeof(struct iphdr) &gt;&gt; 2;
    iph-&gt;frag_off   = df;
    iph-&gt;protocol   = IPPROTO_UDP;
    iph-&gt;tos        = vxlan_ecn_encap(tos, old_iph, skb);
    iph-&gt;daddr      = dst;
    iph-&gt;saddr      = fl4.saddr;
    iph-&gt;ttl        = ttl ? : ip4_dst_hoplimit(&amp;rt-&gt;dst);

    vxlan_set_owner(dev, skb);

[/c]

正如 GRE tunnel,比较复杂的地方是在接收端。因为 VXLAN 利用了 UDP,所以它在接收的时候势必需要有一个 UDP server 在监听某个端口,这个是在 VXLAN 初始化的时候完成的,即 vxlan_init_net() 函数:

[c]
static __net_init int vxlan_init_net(struct net net)
{
struct vxlan_net
vn = net_generic(net, vxlan_net_id);
struct sock *sk;
struct sockaddr_in vxlan_addr = {
.sin_family = AF_INET,
.sin_addr.s_addr = htonl(INADDR_ANY),
};
int rc;
unsigned h;

/* Create UDP socket for encapsulation receive. */
rc = sock_create_kern(AF_INET, SOCK_DGRAM, IPPROTO_UDP, &amp;vn-&gt;sock);
if (rc sock-&gt;sk;
sk_change_net(sk, net);

vxlan_addr.sin_port = htons(vxlan_port);

rc = kernel_bind(vn-&gt;sock, (struct sockaddr *) &amp;vxlan_addr,
         sizeof(vxlan_addr));
if (rc sock = NULL;
    return rc;
}

/* Disable multicast loopback */
inet_sk(sk)-&gt;mc_loop = 0;

/* Mark socket as an encapsulation socket. */
udp_sk(sk)-&gt;encap_type = 1;
udp_sk(sk)-&gt;encap_rcv = vxlan_udp_encap_recv;
udp_encap_enable();

for (h = 0; h vni_list[h]);

return 0;

}
[/c]

由此可见内核内部创建 socket 的 API 是sock_create_kern(),bind() 对应的是 kernel_bind()。注意到这里实现了一个hook,vxlan_udp_encap_recv(),这个正是接收端的主要代码。

发送端是一层一层往外填,那么接收端一定就是一层一层外里剥:

[c]
/ pop off outer UDP header /
__skb_pull(skb, sizeof(struct udphdr));

/* Need Vxlan and inner Ethernet header to be present */
if (!pskb_may_pull(skb, sizeof(struct vxlanhdr)))
    goto error;

/* Drop packets with reserved bits set */
vxh = (struct vxlanhdr *) skb-&gt;data;
if (vxh-&gt;vx_flags != htonl(VXLAN_FLAGS) ||
    (vxh-&gt;vx_vni &amp; htonl(0xff))) {
    netdev_dbg(skb-&gt;dev, "invalid vxlan flags=%#x vni=%#xn",
           ntohl(vxh-&gt;vx_flags), ntohl(vxh-&gt;vx_vni));
    goto error;
}

__skb_pull(skb, sizeof(struct vxlanhdr));

/* Is this VNI defined? */
vni = ntohl(vxh-&gt;vx_vni) &gt;&gt; 8;
vxlan = vxlan_find_vni(sock_net(sk), vni);
if (!vxlan) {
    netdev_dbg(skb-&gt;dev, "unknown vni %dn", vni);
    goto drop;
}

if (!pskb_may_pull(skb, ETH_HLEN)) {
    vxlan-&gt;dev-&gt;stats.rx_length_errors++;
    vxlan-&gt;dev-&gt;stats.rx_errors++;
    goto drop;
}

[/c]

在重新入栈之前还要做一些准备工作:

[c]
/ Re-examine inner Ethernet packet /
oip = ip_hdr(skb);
skb->protocol = eth_type_trans(skb, vxlan->dev);

/* Ignore packet loops (and multicast echo) */
if (compare_ether_addr(eth_hdr(skb)-&gt;h_source,
               vxlan-&gt;dev-&gt;dev_addr) == 0)
    goto drop;

if (vxlan-&gt;learn)
    vxlan_snoop(skb-&gt;dev, oip-&gt;saddr, eth_hdr(skb)-&gt;h_source);

__skb_tunnel_rx(skb, vxlan-&gt;dev);
skb_reset_network_header(skb);
skb-&gt;ip_summed = CHECKSUM_NONE;

[/c]

另外需要特别指出的是:1) 加入和离开组播地址是在 vxlan_open() 和 vxlan_stop() 中完成的;2) Linux 内核已经把 bridge 的 L2 learn 功能给抽出来了,所以 VXLAN 也实现了对 L2 地址的学习和转发:

[c]
static const struct net_device_ops vxlan_netdev_ops = {
.ndo_init = vxlan_init,
.ndo_open = vxlan_open,
.ndo_stop = vxlan_stop,
.ndo_start_xmit = vxlan_xmit,
.ndo_get_stats64 = vxlan_stats64,
.ndo_set_rx_mode = vxlan_set_multicast_list,
.ndo_change_mtu = eth_change_mtu,
.ndo_validate_addr = eth_validate_addr,
.ndo_set_mac_address = eth_mac_addr,
.ndo_fdb_add = vxlan_fdb_add,
.ndo_fdb_del = vxlan_fdb_delete,
.ndo_fdb_dump = vxlan_fdb_dump,
};
[/c]

附注:openvswitch 中的 VXLAN 的实现:http://openvswitch.org/pipermail/dev/2011-October/012051.html

参考资料:

1. http://tools.ietf.org/html/draft-mahalingam-dutt-dcops-vxlan-02
2. http://blogs.cisco.com/datacenter/digging-deeper-into-vxlan/
3. http://www.yellow-bricks.com/2012/11/02/vxlan-use-cases/
4. http://www.borgcube.com/blogs/2011/11/vxlan-primer-part-1/
5. http://www.borgcube.com/blogs/2012/03/vxlan-primer-part-2-lets-get-physical/
6. http://it20.info/2012/05/typical-vxlan-use-case/

深入理解 GRE tunnel

我以前写过一篇介绍 tunnel 的文章,只是做了大体的介绍。里面多数 tunnel 是很容易理解的,因为它们多是一对一的,换句话说,是直接从一端到另一端。比如 IPv6 over IPv4 的 tunnel,也就是 SIT,它的原理如下图所示:

显然,除了端点的 host A 和 host B之外,中间经过的任何设备都是看不到里面的 IPv6 的头,对于它们来说,经过 sit 发出的包和其它的 IPv4 的包没有任何区别。

GRE tunnel 却不一样了,它的原理从根本上和 sit,ipip 这样的 tunnel 就不一样。除了外层的 IP 头和内层的 IP 头之间多了一个 GRE 头之外,它最大的不同是,tunnel 不是建立在最终的 host 上,而是在中间的 router 上!换句话说,对于端点 host A 和 host B 来说,该 tunnel 是透明的(对比上面的 sit tunnel)。这是网上很多教程里没有直接告诉你的。理解这一点非常关键,正是因为它这么设计的,所以它才能解决 ipip tunnel 解决不了的问题。

所以,经过 GRE tunnel 发送的包(从 host A 发送到 host B)大体过程是这样子的(仍然借用了 LARTC 中的例子):

我们可以看出,从 host A 发出的包其实就是一个很普通的 IP 包,除了目的地址不直接可达外。该 GRE tunnel 的一端是建立在 router A上,另一段是建立在 router B上,所以添加外部的 IP 头是在 router A 上完成的,而去掉外面的 IP 头是在 router B上完成的,两个端点的 host 上几乎什么都不用做(除了配置路由,把发送到 10.0.2.0 的包路由到 router A)!

这么设计的好处也就很容易看出来了,ipip tunnel 是端对端的,通信也就只能是点对点的,而 GRE tunnel 却可以进行多播。

现在让我们看看Linux内核是怎么实现的,我们必须假设 router A 和 B 上都是运行的 Linux,而 host A 和 B上运行什么是无所谓的。

发送过程是很简单的,因为 router A 上配置了一条路由规则,凡是发往 10.0.2.0 网络的包都要经过 netb 这个 tunnel 设备,在内核中经过 forward 之后就最终到达这个 GRE tunnel 设备的 ndo_start_xmit(),也就是 ipgre_tunnel_xmit() 函数。这个函数所做的事情无非就是通过 tunnel 的 header_ops 构造一个新的头,并把对应的外部 IP 地址填进去,最后发送出去。

稍微难理解的是接收过程,即 router B 上面进行的操作。这里需要指出的一点是,GRE tunnel 自己定义了一个新的 IP proto,也就是 IPPROTO_GRE。当 router B 收到从 router A 过来的这个包时,它暂时还不知道这个是 GRE 的包,它首先会把它当作普通的 IP 包处理。因为外部的 IP 头的目的地址是该路由器的地址,所以它自己会接收这个包,把它交给上层,到了 IP 层之后才发现这个包不是 TCP,UDP,而是 GRE,这时内核会转交给 GRE 模块处理。

GRE 模块注册了一个 hook:

[c]
static const struct gre_protocol ipgre_protocol = {
.handler = ipgre_rcv,
.err_handler = ipgre_err,
};
[/c]

所以真正处理这个包的函数是 ipgre_rcv() 。ipgre_rcv() 所做的工作是:通过外层IP 头找到对应的 tunnel,然后剥去外层 IP 头,把这个“新的”包重新交给 IP 栈去处理,像接收到普通 IP 包一样。到了这里,“新的”包处理和其它普通的 IP 包已经没有什么两样了:根据 IP 头中目的地址转发给相应的 host。注意:这里我所谓的“新的”包其实并不新,内核用的还是同一个copy,只是skbuff 里相应的指针变了。

以上就是Linux 内核对 GRE tunnel 的整个处理过程。另外,GRE 的头如下所示(图片来自这里):

IP header in GRE tunnel

GRE header

How TSQ works

通常看到 TCP Small Queue (简称 TSQ)之后第一问题是,既然我们已经有 tcp_wmem 了,为何还需要一个新的 sysctl?

这个问题是理解 TSQ 的关键,其实 tcp_wmem 仅仅是从 TCP socket 层限制队列(或 buffer)中最多可以 queue 多少数据包,而实际上,一个包从 TCP 层发出到最后到达网卡,中间还经历了很多个 queue,TCP socket 只是其中一层罢了。而 TSQ 用了一个非常聪明的技巧来限制在所有这些 queue 中的包,从而降低 latency。

TSQ 的代码中最关键的一个地方是它实现了一个新的 skb destructor,也就是 tcp_wfree(),看它的定义:

[c]
static void tcp_wfree(struct sk_buff skb)
{
struct sock
sk = skb->sk;
struct tcp_sock *tp = tcp_sk(sk);

    if (test_and_clear_bit(TSQ_THROTTLED, &amp;tp-&gt;tsq_flags) &amp;&amp;
        !test_and_set_bit(TSQ_QUEUED, &amp;tp-&gt;tsq_flags)) {
            unsigned long flags;
            struct tsq_tasklet *tsq;

            /* Keep a ref on socket.
             * This last ref will be released in tcp_tasklet_func()
             */
            atomic_sub(skb-&gt;truesize - 1, &amp;sk-&gt;sk_wmem_alloc);

            /* queue this socket to tasklet queue */
            local_irq_save(flags);
            tsq = &amp;__get_cpu_var(tsq_tasklet);
            list_add(&amp;tp-&gt;tsq_node, &amp;tsq-&gt;head);
            tasklet_schedule(&amp;tsq-&gt;tasklet);
            local_irq_restore(flags);
    } else {
            sock_wfree(skb);
    }

}
[/c]

我们知道在Linux内核网络子系统中,kfree_skb() 是内核丢包的地方,而 skb 的 destructor 就是在丢包时被调用的,用来清理和该 skb 相关的东西。TSQ 实现新的 destructor 就是想在包被丢弃的时候做一些动作,也就是如果条件合适(设置了 TSQ_THROTTLED,没有设置 TSQ_QUEUED),那么就把它加入进 TSQ。

而在下一个 softIRQ 时,相应的 tasklet 就会调度,从而触发 tcp_tasklet_func():

[c]
static void tcp_tasklet_func(unsigned long data)
{
struct tsq_tasklet tsq = (struct tsq_tasklet )data;
LIST_HEAD(list);
unsigned long flags;
struct list_head q, n;
struct tcp_sock tp;
struct sock
sk;

    local_irq_save(flags);
    list_splice_init(&amp;tsq-&gt;head, &amp;list);
    local_irq_restore(flags);

    list_for_each_safe(q, n, &amp;list) {
            tp = list_entry(q, struct tcp_sock, tsq_node);
            list_del(&amp;tp-&gt;tsq_node);

            sk = (struct sock *)tp;
            bh_lock_sock(sk);

            if (!sock_owned_by_user(sk)) {
                    tcp_tsq_handler(sk);
            } else {
                    /* defer the work to tcp_release_cb() */
                    set_bit(TCP_TSQ_DEFERRED, &amp;tp-&gt;tsq_flags);
            }
            bh_unlock_sock(sk);

            clear_bit(TSQ_QUEUED, &amp;tp-&gt;tsq_flags);
            sk_free(sk);
    }

}
[/c]

这里对加入到 TSQ 队列中的 socket 进行处理,对于没有 owner 的 socket(不是由用户使用的socket),直接发送;否则就是推迟到 tcp_release_cb() 中发送,即 release_sock() 的时候。

现在,我们从总体上可以看出 TSQ 的用意了:当发送的包超过 sysctl_tcp_limit_output_bytes 时,就会发生抖动(throttle),这时就会把包推迟发送,推迟到什么时候呢?当然是该队列有空闲的时候!那么什么时候有空闲呢?包被丢弃的时候!内核发送的包是在即将被丢弃的时候(忽略tasklet,用tasklet仅仅是因为skb destructor 中不能进行发送),用户层发送的包则是关闭 socket 的时候,这种时候 TSQ 会有新的空间,所以可以重新入队。

可见,TSQ 的聪明之处在于,它虽然有自己的所谓队列,但并没有计算该队列的长度,而是巧妙地利用了内核中几个关键点来判断何时可以入队!这当然需要对 TCP 实现非常熟悉才可以,由此亦可见作者水平之高。

accept_ra 的一个例子

在 IPv6 中,Router Advertisement (简称 RA)是很关键的一个 ICMP 包,stateless autoconf 就是靠 RA 配置 IP 地址的,主机发送Router Solicitation(RS)广播,有点类似于 IPv4 中的 DHCP request,路由器就会回应 RA,类似于 DHCP reply。不同的是,DHCP 是 stateful 的,因为 DHCP 服务器必须维持一个地址表,而 IPv6 的路由器却不需要,所以是无状态的,而且 RA 的广播是周期性的。

以上是技术背景。显然,一般情况下你是要接受这个包的。而我遇到一种情况却不得不禁止掉这个选项。

情况是这样的,两台主机通过一个交换机连接,现在我们修改两台主机以及交换机的 MTU 为 9000,来发送大小为 8000 的 Jumbo Frame,IPv4 一切正常,可是到了 IPv6 下面却不行了,会收到 ICMPV6_PKT_TOOBIG。

在这里,需要指出 IPv6 和 IPv4 一个重要的区别是,包的分片(fragmentation)是在主机上完成的,而不是由 router 完成。wikipedia 上说:

In IPv4, routers perform fragmentation, whereas in IPv6, routers do not fragment, but drop the packets that are larger than the MTU.
而我这里所谓的主机完成是指 PMTU 的计算是由主机完成的:既然 IPv6 的 router 不进行分片,那么主机必须在发送之前知道整个 path 上最小的 MTU,即 PMTU。

好了,既然我们修改了主机的 MTU,那么 PMTU 也需要更新,尤其是 IPv6 路由表中的 MTU。幸运的是,这个是由内核自动完成的,通过 NETDEV_CHANGEMTU 这个异步通知完成。ip -6 r s 也可以看出对应的 MTU 确实变成了 9000,但是,不一会儿我就发现该 MTU 还会自动变会成之前的 1500。这很奇怪,然后我就捕捉一些包看看,发现原来每当收到 RA 的时候这个 MTU 就会变化!不用看代码你也能马上理解,RA 里肯定也包含了一个 router 的 MTU,这个 MTU 是 1500,所以 PMTU 才会跳回到 1500!

可是我们不是已经修改交换机的 MTU 了,为什么它还会发出 RA (MTU=1500) 的广播?连接上交换机一看,jumbo MTU 确实是改成了 9000,但 routing MTU 依旧是 1500,而且无法修改成 9000,毕竟千兆网卡还没有普及。所以现在的问题就是,这个配置其实是对的,8000 字节的包明显在物理上也是可以发送出去的,但 IPv6 就因为交换机的 routing MTU 是 1500 而无法发送,这种情况下我们就不得不禁止掉 accept_ra 这个选项了,地址的获取用 DHCPv6 了。