Linux Kernel

An overview of Openvswitch implementation

Author: Cong Wang <xiyou.wangcong@gmail.com>

This is NOT a tutorial on how to use openvswitch, this is for developers who want to know the implementation details of openvswitch project, thus, I assume you at least know the basic concepts of openvswitch and know how to use it. If not, see www.openvswitch.org to get some documents or slides.

Let’s start from the user-space part. Openvswitch user-space contains several components: they are a few daemons which actually implements the switch and the flow table, the core of openvswitch, and several utilities to manage the switch, the database, and even talk to the kernel directly.

There are three daemons started by openvswitch service: ovs-vswitchd, which is the core implementation of the switch; ovsdb-server, which manipulates the database of the vswitch configuration and flows; and ovs-brcompatd which keeps the compatibility with the traditional bridges (that is the one you create with ‘brctl’ command) .

Their relationship is shown in the picture below:

Obviously, the most important one is ovs-vswitchd, it implements the switch, it directly talks with kernel via netlink protocol (we will see the details later). And ovs-vsctl is the utility used primarily to manage the switch, which of course needs to talk with ovs-vswitchd. Ovs-vswitchd saves and changes the switch configuration into a database, which is directly managed by ovsdb-server, therefore, ovs-vswitchd will need to talk to ovsdb-server too, via Unix domain socket, in order to retrieve or save the configuration information. This is also why your openvswitch configuration could survive from reboot even you are not using ifcfg* files.

Ovs-brcompatd is omitted here, we are not very interested in it now.

Ovs-vsctl can do lots of things for you, so most of time, you will use ovs-vsctl to manage openvswitch. Ovs-appctl is also available to manage the ovs-vswitchd itself, it sends some internal commands to ovs-vswitchd daemon to change some configurations.

However, sometimes you may need to manage the datapath in the kernel directly by yourself, in this case, assume ovs-vswitchd is not running, you can invoke ovs-dpctl to let ovs-vswitchd to manage the datapath in the kernel space directly, without database.

And, when you need to talk with ovsdb-server directly, to do some database operation, you can run ovsdb-client, or you want to manipulate the database directly without ovsdb-server, ovsdb-tool is handy too.

What’s more, openvswitch can be also administered and monitored by a remote controller. This is why we could define the network by software! sFlow is a protocol for packet sampling and monitoring, while OpenFlow is a protocol to manage the flow table of a switch, bridge, or device. Openvswitch supports both OpenFlow and sFlow. With ovs-ofctl, you can use OpenFlow to connect to the switch and do some monitoring and administering in the remote. sFlowTrend, which is not a part of openvswitch package, is the one that is capable for sFlow.

Now, let’s take a look at the kernel part.

As mentioned previously, the user-space communicates with the kernel-space via netlink protocol, generic netlink is used in this case. So there are several groups of genl commands defined by the kernel, they are used to get/set/add/delete some datapath/flow/vport and execute some actions on a specific packet.

The ones used to control datapatch are:

enum ovs_datapath_cmd {

OVS_DP_CMD_UNSPEC,

OVS_DP_CMD_NEW,

OVS_DP_CMD_DEL,

OVS_DP_CMD_GET,

OVS_DP_CMD_SET

};

and there are corresponding kernel functions which does the job:

ovs_dp_cmd_new()

ovs_dp_cmd_del()

ovs_dp_cmd_get()

ovs_dp_cmd_set()

Similar functions are defined for vport and flow commands too.

Before we talk about the details of the data structures, let’s see how a packet is sent out or received from a port of an ovs bridge. When is packet is send out from the ovs bridge, an internal device defined by openvswitch module, which is viewed, by the kernel, as a struct vport too. The packet will be finally passed to internal_dev_xmit(), which in turn “receives” the packet. Now, the kernel needs to look at the flow table, to see if there is any “cache” for how to forward this packet. This is done by function ovs_flow_tbl_lookup(), which needs a key. The key is extracted by ovs_flow_extract() which briefly collects the details of the packet (L2~L4) and then constructs a unique key for this flow. Assume this is the first packet going out after we create the ovs bridge, so, there is no “cache” in the kernel, and the kernel doesn’t know how to handle this packet! Then it will pass it to the user-space with “upcall” which uses genl too. The user-space daemon, ovs-vswitchd, will check the database and see which is the destination port for this packet, and will response to the kernel with OVS_ACTION_ATTR_OUTPUT to tell kernel which is the port it should forward to, in this case let’s assume it is eth0. and finally a OVS_PACKET_CMD_EXECUTE command is to let the kernel execute the action we just set. That is, the kernel will execute this genl command in function do_execute_actions() and finally forward the packet to the port “eth0” with do_output(). Then it goes to outside!

The receiving side is similar. The openvswitch module registers an rx_handler for the underlying (non-internal) devices, it is netdev_frame_hook(), so once the underlying device receives packets on wire, openvswitch will forward it to user-space to check where it should goes, and what actions it needs to execute on it. For example, if this is a VLAN packet, the VLAN tag should be removed from the packet first, and then forwarded to a right port. The user-space could learn that which is the right port to forward a given packet.

The internal devices are special, when a packet is sent to an internal device, it is be immediately sent up to openvswitch to decide where it should go, instead of really sending it out. There is actually no way out of an internal device directly.

Besides OVS_ACTION_ATTR_OUTPUT, the kernel also defines some other actions:

OVS_ACTION_ATTR_USERSPACE, which tells the kernel to pass the packet to user-space

OVS_ACTION_ATTR_SET: Modify the header of the packet

OVS_ACTION_ATTR_PUSH_VLAN: Insert a vlan tag into the packet

OVS_ACTION_ATTR_POP_VLAN: Remove the vlan tag from the packet

OVS_ACTION_ATTR_SAMPLE: Do sampling

With these commands combined, the user-space could implement some different policies, like a bridge, a bond or a VLAN device etc. GRE tunnel is not currently in upstream, so we don’t care about it now.

So far, you already know how the packets are handled by openvswitch module. There are much more details, especially about the flow and datapath mentioned previously. A flow in kernel is represented as struct sw_flow, and datapath is defined as struct datapath, and the actions on a flow is defined as struct sw_flow_actions, and plus the one we mentioned, struct vport. These structures are the most important ones for openvswitch kernel module, their relationship is demonstrated in this picture:

The most important one needs to mention is each struct sk_buff is associated with a struct sw_flow, which is via a pointer in ovs control block. And the above actions is associated with each flow, every time when a packet passed to openvswitch module, it first needs to lookup the flow table which is contained in a datapath which in turn either contains in a struct vport or in a global linked-list, with the key we mentioned. If a flow is found, the corresponding actions will be executed. Remember that datapath, flow, vport, all could be changed by the user-space with some specific genl command.

As you can see, the kernel part only implements a mechanism and the fast path (except the first packet), and the user-space implements different policies upon the mechanism provided by the kernel, the slow path. The user-space is much more complicated, so I will not cover its details here.

Update: Ben, one of the most active developers for openvswitch, pointed out some mistakes in the previous version, I updated this article as he suggested. Thanks to Ben!

从 IPv4 到 IPv6

稍微熟悉 IPv6 的人都知道,IPv6 相对于 IPv4 并不只是简单地把地址从 32 位扩展到了 128 位,它同时还修复了 IPv4 协议设计中的一些不足。正如地址空间一样,当然设计 IPv4 时的不足已经逐渐凸显,理解这些 IPv4 的不足以及 IPv6 对它的改进对于深入理解 IPv6 至关重要。我在学习 IPv6 的时候就特别想找一个这样的文档,可惜一直没有发现,所以在这里简单总结一下,以方便初学 IPv6 的人。

1. 地址空间的划分

从 32 位一下子扩展到 128 位一个最明显的变化是,你很可能再也无法用脑子记住一个 IP 地址(除了 ::1 这种简单的地址)。玩笑。:-)

言归正传,IPv4 中的 A、B、C 类地址划分在 IPv6 中不存在了,这种死板的分配方式问题多多,本身就属于设计的不合理,连 IPv4 自己都已经舍弃它改用 Classless Inter-Domain Routing 了。所以,IPv6 的一个显著的变化是没了网络掩码(mask),而改用前缀(prefix)了,这样可以完全通过前缀决定网络了。同时,网络掩码的中间可以包含0,可它几乎没有什么用处,但前缀却是直接指定前x位含1,直接避免了含0的可能性,简化了设计。

在功能上,IPv4 中的地址分为三类:单播(unicast)、多播(multicast)和广播(broadcast),而 IPv6 中不再有广播地址,反而多了一个任播( anycast)。wikipedia 上有一幅图可以很好的解释它们的区别:

但是,任播地址是直接从单播地址上拿出来,并没有单独分类,IPv6 协议这么写的:

Anycast addresses are allocated from the unicast address space, using any of the defined unicast address formats. Thus, anycast addresses are syntactically indistinguishable from unicast addresses. When a unicast address is assigned to more than one interface, thus turning it into an anycast address, the nodes to which the address is assigned must be explicitly configured to know that it is an anycast address.
更详细的信息可见 RFC2373。好了,那么单播和多播地址又是如何划分的呢?这一点和 IPv4 一样,也是根据地址中的头几位来区分:

(图片来自《TCP/IP guide》)

从这里你可以看到了,单播地址还有多了一个非常重要的概念:约束(scope)。虽然在 IPv4 中 192.168.. 这种地址被用于私有地址,不应该出现在互联网上,但是,这种保证仅仅取决于路由,而非协议本身。而 IPv6 直接从协议规范上禁止了私有地址(其实叫 link-local 和 site-local )被转发到互联网,它为不同的地址划分了不同的范围,一个范围内的地址只能在这个范围内使用。

如上图,IPv6 规定了三种约束:link-local,site-local,和 global。link-local 的可达范围是本地物理连接的网络,任何路由都不能转发目的地址为这种地址的包(它是给 neighbour discovery 使用的);site-local 的可达范围是整个组织、站点,组织内部的路由可以转发这种包,但是绝对不能把它们转发到互联网上;global 就是可以在互联网上使用的地址。一个设备可以有多个 IPv6 地址,比如一个 link-local 的地址和一个 site-local 的。

多播地址的划分和 IPv4 类似,故此省略。

2. IPv6 头

让我们对比一下 IPv4 和 IPv6 的头部:

(图片来自这里

不难发现,IPv6 的头部结构明显简单了一些:

第一个最明显的改变是没有了 header checksum,这个是没有必要的,因为 checksum 完全可以由上层的 TCP,UDP 协议来做,在 IP 层再做一次是浪费。当然 IPv4 UDP 中的 checksum 可以不做,而到了 IPv6 UDP 中的 checksum 就是必须的了。给 IP 头做 checksum 的另一个缺点是,每次 TTL 改变的时候都需要重新计算 checksum。

第二个改变是没有了 IP options,因此也就没有了 Ip Header Length,因此 IPv6 头部也就是固定的大小,40 个字节。IPv6 之所以这么做一是因为它使用了 next header,使得这个没有必要;二是,这可以提高 IP 头的解析速度。

第三个改变是多了一个 Next Header,正如刚才提到的,如果你对网络比较熟悉的话,你不难发现这个设计的灵感来自于 IPSec,Next Header 是指向下一个头,有点儿类似于单链表。下一个头可以是一个 option(所以IP option没有必要)头,比如 Hop-by-Hop,也可以上一层的协议头,比如 TCP,UDP。这种灵活的设计使得 IPv6 头部可“链接”多个头部。

第四个改变是,IPv6 不再有 Fragment Offset 和 ID,这是因为分片(fragment)的 IPv6 包可以用 Next Header 来表示(知道它强大了吧?),而且 IPv6 协议已经禁止在中间的 router 上进行分片,如果需要分片必须在 host 上完成(PMTU),这可以大大提高路由的速度。其实 IP 包分片性能很差,IPv4 包分片的问题多多:ID 的生成是个问题,在对端把分段的包进行组装又是一个头疼的问题(该预留多少内存?中间少了几个分片怎么办?收到重复的分片怎么办?),所以能尽量避免分片就避免。

3. 邻居发现( Neighbour Discovery

IPv6 相比 IPv4 另一个显著的变化是没有了 ARP 协议,邻居发现协议使用的是 ICMPv6。ARP 协议是一个尴尬的存在,它处于第三层,但又不像 ICMP 协议那样基于 IP,而是和 IP 并列,从它的头部就可以看出:

(图片来自这里

这种设计使得 OSI 分层模式变得含糊。而 IPv6 使用的 ICMPv6 则完全基于 IP 之上,无须设计另外一个并列于 IP 层的协议。正如前面提到,邻居发现协议使用的是 link-local 地址,所以不会造成更大链路范围上的影响。link-local 地址是根据 MAC 地址自动生成的(协议规定的算法),因此有了 link-local 地址就可以马上和路由器进行通信了,因此也就有了 IP 地址自动分配的功能,即类似于 IPv4 的 DHCP,在 IPv6 上这被称为自动配置(Stateless Address Autoconfiguration)。

当然了,因为没有广播地址,邻居发现协议使用的是多播地址。具体协议的细节可以参考 ICMPv6 协议的定义,和 ICMP 并无显著的差别,故省略。

rp_filter 的一个例子

我们都知道 Linux 反向路由查询,它的原理很简单,检查流入本机的 IP 地址是否合法,是否可能路由进来,是否是最佳路由。但是像多数网络问题,理论很简单,代码你看了也能懂,可实际情况往往比较复杂。之前一直没有碰到过实际中的例子,最近总算碰到一个。

情况是这样的,我有两个 vlan 设备,eth0.7 和 eth0.9,都是经过 vconfig 创建的虚拟网卡,eth0 硬件本身不能处理 vlan tag。现在的问题是,我给这两个网卡配置了同一个 IP 地址,192.168.122.74。你也许会感觉奇怪,但这是可行的,毕竟 eth0.7 和 eth0.9 不在同一个 vlan!你可以想象成它们的网线接在不同的局域网中。好了,问题出来了,现在我们在另外一台机器,物理上连接着 eth0,上面分别发送 vlan tag 是 7 和 9 的两个 arp request,结果是只有先被 ifup 起来的那个网卡回应!为什么?

我一开始的想法这可能是内核的bug,毕竟 vlan 那一部分经常出现一些问题。但经过人肉跟踪 vlan tag 的处理流程,发现基本上不太可能是内核的问题,至少不是内核 vlan 处理代码的问题。其实,这部分内核代码经过重写之后还是很清晰的,推荐你有时间阅读一下。

所以问题一定是在 arp 处理的代码中,所以最后锁定到了 arp_process()。分析一下里面的代码你不难看到里面调用了 ip_route_input_noref(),所以路由有可能是其中一个因素。所以我们看一下路由表:

ip r s

default via 192.168.122.1 dev eth0
192.168.122.0/24 dev eth0.7 proto kernel scope link src 192.168.122.74
192.168.122.0/24 dev eth0.9 proto kernel scope link src 192.168.122.74

然后尝试换一个顺序对 eth0.7 和 eth0.9 进行 ifup,你会发现其实是路由的顺序决定了你能得到哪个 arp reply!这时你应该能明白了,是 rp_filter 在起作用。查看一下它们的 /proc/sys/net/ipv4/conf/X/rp_filter 设置,果然都是1,那么在这种情况下,eth0.9 因为不是最佳路由,因此发送给它的 arp request 就被丢弃了。我们也可以把 /proc/sys/net/ipv4/conf/eth0.9/log_martians 打开,很容易看到下面的log:

[87317.980514] IPv4: martian source 192.168.122.74 from 192.168.122.1, on dev eth0.9
[87317.998162] ll header: 00000000: ff ff ff ff ff ff 52 54 00 2e 23 92 08 06 00 01 ……RT..#…..
[87318.015159] ll header: 00000010: 08 00 ..

另外,分析过程中用到的两条相关的 tcpdump 命令:

tcpdump arp -xx -ni eth0

tcpdump -xx -ni eth0 vlan

Linux 内核中的 KMP 实现

Linux 内核中使用到了字符串搜索,所以它也有 KMP 算法的实现,代码在 lib/ts_kmp.c 中。

Linux 内核中用到 KMP 算法的地方有三处:iptables string match 模块、iptables conntrack amanda 模块(不知道这个是用来干什么的)、以及 ematch qdisc。iptables string match 是通过字符串搜索来匹配一个包,然后进行相应的处理,比如用下面的命令可以阻止对domain.com服务器的HTTP请求:

iptables -I INPUT 1 -p tcp —dport 80 -m string —string “domain.com” —algo kmp -j DROP

至于 ematch qdisc,和它类似,可以通过字符串匹配到对应的包进行 QoS,比如这个例子

tc filter add dev eth0 parent 10:12 prio 10 protocol ip basic match ‘text(kmp foobar from 0 to 200)’ flowid 10:1

总之,在内核中实现 KMP 算法是有必要的。下面来看具体实现。

我们知道,KMP 算法中最核心的地方就是 prefix 的计算,也称为 next 数组,它用来表示当字符 pattern[i] 匹配失败后应该从 pattern[next[i]] 字符继续进行匹配,而不总是从头开始,因此它的时间复杂度是O(n)。如果你对 KMP 不熟悉的话,网上有很多介绍,我觉得这篇文章还算不错,在继续看下面的代码之前可以读一下它。

内核中实现比网上的很多代码都更容易理解,因为在匹配开始之前,它就先把 prefix 计算好了。计算 prefix 的函数是:

[c]
static inline void compute_prefix_tbl(const u8 pattern, unsigned int len,
unsigned int
prefix_tbl, int flags)
{
unsigned int k, q;
const u8 icase = flags & TS_IGNORECASE;

    for (k = 0, q = 1; q  0 &amp;&amp; (icase ? toupper(pattern[k]) : pattern[k])
                != (icase ? toupper(pattern[q]) : pattern[q]))
                    k = prefix_tbl[k-1];
            if ((icase ? toupper(pattern[k]) : pattern[k])
                == (icase ? toupper(pattern[q]) : pattern[q]))
                    k++;
            prefix_tbl[q] = k;
    }

}
[/c]

结合 KMP 实现的主函数来理解更一目了然:

[c]
static unsigned int kmp_find(struct ts_config conf, struct ts_state state)
{
struct ts_kmp kmp = ts_config_priv(conf);
unsigned int i, q = 0, text_len, consumed = state->offset;
const u8
text;
const int icase = conf->flags & TS_IGNORECASE;

    for (;;) {
            text_len = conf-&gt;get_next_block(consumed, &amp;text, conf, state);

            if (unlikely(text_len == 0))
                    break;

            for (i = 0; i  0 &amp;&amp; kmp-&gt;pattern[q]
                        != (icase ? toupper(text[i]) : text[i]))
                            q = kmp-&gt;prefix_tbl[q - 1];
                    if (kmp-&gt;pattern[q]
                        == (icase ? toupper(text[i]) : text[i]))
                            q++;
                    if (unlikely(q == kmp-&gt;pattern_len)) {
                            state-&gt;offset = consumed + i + 1;
                            return state-&gt;offset - kmp-&gt;pattern_len;
                    }
            }

            consumed += text_len;
    }

    return UINT_MAX;

}
[/c]

内核中的 KMP 函数接口是封装过的,你不能直接调用它。如果你的内核模块中要使用它,可以参考 lib/textsearch.c 中给的例子:

[c]
int pos;
struct ts_config conf;
struct ts_state state;
const char
pattern = “chicken”;
const char *example = “We dance the funky chicken”;

conf = textsearch_prepare(“kmp”, pattern, strlen(pattern),
GFP_KERNEL, TS_AUTOLOAD);
if (IS_ERR(conf)) {
err = PTR_ERR(conf);
goto errout;
}

pos = textsearch_find_continuous(conf, &state, example, strlen(example));
if (pos != UINT_MAX)
panic(“Oh my god, dancing chickens at %dn”, pos);

textsearch_destroy(conf);
[/c]

关于 schedule() 函数

今天在 LKML 上看到一个补丁:http://permalink.gmane.org/gmane.linux.kernel/1337629,它对 schedule() 函数做了很好的注释,分享一下:

+ *
+ * The main means of driving the scheduler and thus entering this function are:
+ *
+ *   1\. Explicit blocking: mutex, semaphore, waitqueue, etc.
+ *
+ *   2\. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
+ *      paths. For example, see arch/x86/entry_64.S.
+ *
+ *      To drive preemption between tasks, the scheduler sets the flag in timer
+ *      interrupt handler scheduler_tick().
+ *
+ *   3\. Wakeups don't really cause entry into schedule(). They add a
+ *      task to the run-queue and that's it.
+ *
+ *      Now, if the new task added to the run-queue preempts the current
+ *      task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
+ *      called on the nearest possible occasion:
+ *
+ *       - If the kernel is preemptible (CONFIG_PREEMPT=y):
+ *
+ *         - in syscall or exception context, at the next outmost
+ *           preempt_enable(). (this might be as soon as the wake_up()'s
+ *           spin_unlock()!)
+ *
+ *         - in IRQ context, return from interrupt-handler to
+ *           preemptible context
+ *
+ *       - If the kernel is not preemptible (CONFIG_PREEMPT is not set)
+ *         then at the next:
+ *
+ *          - cond_resched() call
+ *          - explicit schedule() call
+ *          - return from syscall or exception to user-space
+ *          - return from interrupt-handler to user-space

Linux kernel memory model

稍微了解 Linux 内核的人都知道,在 x86 上内核中所有的 struct page 是放在一个数组中管理的,它就是 mem_map,通过它我们就可以用 pfn 作为 index 来找到对应的 struct page 了:

[c]

define __pfn_to_page(pfn) (mem_map + ((pfn) - ARCH_PFN_OFFSET))

define __page_to_pfn(page) ((unsigned long)((page) - mem_map) +

                             ARCH_PFN_OFFSET)

[/c]

这是以前旧的 memory model(这个词很流行,你应该在很多地方见过,比如 C/C++标准),现在情况变了。

因为对 NUMA 和内存热插拔(memory hot-plug)的支持,Linux 内核中现在又引入两个新的 memory model,之前那个旧的被称为 Flat memory,新的两个被称为 Discontiguous memory 和 Sparse memory。它们对应的选项是:CONFIG_FLATMEM,CONFIG_DISCONTIGMEM,CONFIG_SPARSEMEM。让我们来看看这两个新的 memory model。

顺便多说两句,NUMA 和内存热插拔并没有直接的联系,NUMA 系统不一定支持内存的热插拔,而可以进行内存热插拔的系统也不一定是 NUMA 的!NUMA 支持对应的选项是 CONFIG_NUMA,而内存热插拔对应的选项是 CONFIG_MEMORY_HOTPLUG 和 CONFIG_MEMORY_HOTREMOVE。由此也可以看出 Linux 内核配置是多么灵活,你可以任意搭配你需要的选项。

CONFIG_DISCONTIGMEM

mm/Kconfig 中对它的介绍是:

This option provides enhanced support for discontiguous memory systems, over FLATMEM. These systems have holes in their physical address spaces, and this option provides more efficient handling of these holes. However, the vast majority of hardware has quite flat address spaces, and can have degraded performance from the extra overhead that this option imposes.

Many NUMA configurations will have this as the only option.
Discontiguous memory 其实很简单,它上从 flat memory 的基础上对 NUMA 进行扩展得出来的。每一个 node 都有一个 struct pglist_data,对于 discontiguous memory 其中记录了每个 node 的 node_start_pfn、node_spanned_pages、node_mem_map,分别表示该 node 的起始页的 PFN、物理页的数量、这些页面的 mem_map。我们可以看 alloc_node_mem_map() 是如何初始化这几个值的:

[c]
static void __init_refok alloc_node_mem_map(struct pglist_data pgdat)
{
/
Skip empty nodes */
if (!pgdat->node_spanned_pages)
return;

ifdef CONFIG_FLAT_NODE_MEM_MAP

    /* ia64 gets its own node_mem_map, before this, without bootmem */
    if (!pgdat-&gt;node_mem_map) {
            unsigned long size, start, end;
            struct page *map;

            /*
             * The zone's endpoints aren't required to be MAX_ORDER
             * aligned but the node_mem_map endpoints must be in order
             * for the buddy allocator to function correctly.
             */
            start = pgdat-&gt;node_start_pfn &amp; ~(MAX_ORDER_NR_PAGES - 1);
            end = pgdat-&gt;node_start_pfn + pgdat-&gt;node_spanned_pages;
            end = ALIGN(end, MAX_ORDER_NR_PAGES);
            size =  (end - start) * sizeof(struct page);
            map = alloc_remap(pgdat-&gt;node_id, size);
            if (!map)
                    map = alloc_bootmem_node_nopanic(pgdat, size);
            pgdat-&gt;node_mem_map = map + (pgdat-&gt;node_start_pfn - start);
    }
    //....

}
[/c]

所以,它对应的 pfn_to_page() 和 page_to_pfn() 定义如下:

[c]

define arch_local_page_offset(pfn, nid)

    ((pfn) - NODE_DATA(nid)-&gt;node_start_pfn)

define __pfn_to_page(pfn)

({ unsigned long pfn = (pfn);
unsigned long
nid = arch_pfn_to_nid(pfn);
NODE_DATA(
nid)->node_mem_map + arch_local_page_offset(pfn, nid);
})

define __page_to_pfn(pg)

({ const struct page __pg = (pg);
struct pglist_data
pgdat = NODE_DATA(page_to_nid(pg));
(unsigned long)(pg - pgdat->node_mem_map) +
__pgdat->node_start_pfn;
})
[/c]

两个 node 之间的内存未必是连续的,中间可能有内存空洞,空洞的单位是 64M,但整个内存依然是 flat 的:

[c]
/*

  • generic node memory support, the following assumptions apply:
    *
  • 1) memory comes in 64Mb contiguous chunks which are either present or not
  • 2) we will not have more than 64Gb in total
    *
  • for now assume that 64Gb is max amount of RAM for whole system
  • 64Gb / 4096bytes/page = 16777216 pages
    */

    define MAX_NR_PAGES 16777216

    define MAX_SECTIONS 1024

    define PAGES_PER_SECTION (MAX_NR_PAGES/MAX_SECTIONS)

extern s8 physnode_map[];

static inline int pfn_to_nid(unsigned long pfn)
{

ifdef CONFIG_NUMA

    return((int) physnode_map[(pfn) / PAGES_PER_SECTION]);

else

    return 0;

endif

}
[/c]

CONFIG_SPARSEMEM

Sparse memory 是一个相对比较复杂的模型。mm/Kconfig 中对它的介绍是:

This will be the only option for some systems, including memory hotplug systems. This is normal. For many other systems, this will be an alternative to “Discontiguous Memory”. This option provides some potential performance benefits, along with decreased code complexity, but it is newer, and more experimental.

它主要是因为支持内存热插拔引入的。对于支持内存热插拔的系统,系统中的某一个部分内存可以随时被移除和添加,这就是得原本连续的内存空间变得稀疏。这个内存模型是把所有的内存空间划分成一个个 section,每个 section 都是同样大小的,可以进行热插拔的内存大小就是以 section 为单位的。在 x86_64 上面,每个 section 是 128M:

[c]

ifdef CONFIG_X86_32

ifdef CONFIG_X86_PAE

define SECTION_SIZE_BITS 29

define MAX_PHYSADDR_BITS 36

define MAX_PHYSMEM_BITS 36

else

define SECTION_SIZE_BITS 26

define MAX_PHYSADDR_BITS 32

define MAX_PHYSMEM_BITS 32

endif

else / CONFIG_X86_32 /

define SECTION_SIZE_BITS 27 / matt - 128 is convenient right now /

define MAX_PHYSADDR_BITS 44

define MAX_PHYSMEM_BITS 46

endif

[/c]

每个 section 有自己的 mem_map,所以其 __pfn_to_page 的定义如下:

[c]
/*

  • Note: section’s mem_map is encorded to reflect its start_pfn.
  • section[i].section_mem_map == mem_map’s address - start_pfn;
    */

    define __page_to_pfn(pg)

    ({ const struct page *__pg = (pg);
     int __sec = page_to_section(__pg);                      
     (unsigned long)(__pg - __section_mem_map_addr(__nr_to_section(__sec))); 
    
    })

define __pfn_to_page(pfn)

({ unsigned long pfn = (pfn);
struct mem_section *
sec = pfn_to_section(pfn);
section_mem_map_addr(sec) + __pfn;
})
[/c]

Sparse memory 还有两个变异:SPARSEMEM_EXTREME 和 SPARSEMEM_VMEMMAP,前者是对更稀疏的内存做了优化,采用了两层 memory section,即二维数组:

[c]

ifdef CONFIG_SPARSEMEM_EXTREME

define SECTIONS_PER_ROOT (PAGE_SIZE / sizeof (struct mem_section))

else

define SECTIONS_PER_ROOT 1

endif

define SECTION_NR_TO_ROOT(sec) ((sec) / SECTIONS_PER_ROOT)

define NR_SECTION_ROOTS DIV_ROUND_UP(NR_MEM_SECTIONS, SECTIONS_PER_ROOT)

define SECTION_ROOT_MASK (SECTIONS_PER_ROOT - 1)

ifdef CONFIG_SPARSEMEM_EXTREME

extern struct mem_section *mem_section[NR_SECTION_ROOTS];

else

extern struct mem_section mem_section[NR_SECTION_ROOTS][SECTIONS_PER_ROOT];

endif

static inline struct mem_section *__nr_to_section(unsigned long nr)
{
if (!mem_section[SECTION_NR_TO_ROOT(nr)])
return NULL;
return &mem_section[SECTION_NR_TO_ROOT(nr)][nr & SECTION_ROOT_MASK];
}
[/c]

后者是针对 x86_64 这种虚拟地址空间比较大的平台做了速度的优化,把 mem_map 里所有 struct page 的地址一一映射进 vmemmap 地址中去,这样它们的虚拟地址就是连续的了:

[c]

define VMEMMAP_START _AC(0xffffea0000000000, UL)

define vmemmap ((struct page *)VMEMMAP_START)

/ memmap is virtually contiguous. /

define __pfn_to_page(pfn) (vmemmap + (pfn))

define __page_to_pfn(page) (unsigned long)((page) - vmemmap)

[/c]

不过额外的代价就是初始化的时候要对每一个 struct page 做 populate,参见 sparse_mem_map_populate() 函数。另外可参考内存热插拔代码中函数 add_section() 和 remove_section() 的实现。

我的内核配置文件

我们知道,在KVM里测试内核会碰到一个很严重的问题:那就是在 host 编译的内核不能直接在 guest 里使用。有两个原因:一是 host 和 guest 的硬件可能不一样,所以需要的 config 不一样;二是内核模块即便是安装进了 initramfs 也仍有很多需要安装到 /lib/modules/uname -r

有三种解决办法:

1. host 和 guest 都使用发行版自带的 config,这个 config 是可以在很多机器上运行,所以基本上一定可以在你的guest 里使用,然后用 guestfish 把编译的内核模块拷贝进 guest;这么做的好处是 host 和 guest 都使用同一个 config;坏处也显然,需要进行太多host => guest 拷贝操作。

2. 在 1) 的基础上进行改进,把 host 作为 build server,为 guest 提供 PXE,NFS 服务,这样 guest 里就可以直接使用编译好的内核以及内核模块。这个方法的缺点是,需要一些系统管理技巧,我暂时还没有时间折腾;优点是,如果你的 build server 搭建得比较好,你甚至可以给其它机器(非虚拟)提供服务。

3. guest 使用和 host 不同的 config,guest 的 config 是经过专门定制的,只编译本机器所需要的内核特性和模块,并且把所有的模块都编译进内核(builtin),这样我们甚至不需要 initramfs!优点是,config 很少,即使重新编译花费时间也很少;缺点也很显然,config 很难用于别的机器,尤其是非虚拟化的机器。需要特别注意:如果你的系统用了 LVM 那么它将无法使用!因为内核无法自己检测 LVM!另外,编译进内核的模块和不像单独加载的模块那样灵活,比如 netconsole 模块,我们通常是通过模块参数来指定其功能,而一旦变成 builtin 我们就不得不通过 configfs 来进行操作了,也就是说测试脚本就得重写了。

为了定制上述 3) 中专门的 config,我花了不少时间把我的 config 精简到最少,但同时又包含了 KVM 里需要功能以及我调试用到的选项,我把最终的 config 放到了 github 上进行管理:

https://github.com/congwang/kernelconfig/blob/master/kvm-mini-config

我的目标是让它可以在尽可能多的 KVM guest 上可以运行(显然不可能保证所有),同时尽量不破坏用户空间的程序比如 systemd(取决于发行版),当然还要保持编译出的内核可能的小。欢迎帮忙测试。:-)

下一步是尝试实现第2种方法,我们需要搭建一个集编译内核、PXE服务器、NFS服务器于一身的服务器,准备弄一个新的 github 项目去搞一下。

当然,如果你有其它更好的主意,希望不吝赐教!

附我常用的一些内核调试选项:

一定要有的:
CONFIG_DEBUG_KERNEL=y

内存相关:
CONFIG_SLUB_DEBUG=y
CONFIG_DEBUG_VM=y
CONFIG_DEBUG_LIST=y

内核加锁相关:
CONFIG_DEBUG_ATOMIC_SLEEP=y
CONFIG_LOCKDEP=y
CONFIG_DEBUG_SPINLOCK=y
CONFIG_DEBUG_MUTEXES=y
CONFIG_DEBUG_LOCK_ALLOC=y
CONFIG_PROVE_LOCKING=y
CONFIG_PROVE_RCU=y

ftrace 相关:
CONFIG_FTRACE=y
CONFIG_FUNCTION_TRACER=y

锁死检测:
CONFIG_LOCKUP_DETECTOR=y
CONFIG_HARDLOCKUP_DETECTOR=y
CONFIG_BOOTPARAM_HARDLOCKUP_PANIC=y
CONFIG_BOOTPARAM_HARDLOCKUP_PANIC_VALUE=1
CONFIG_BOOTPARAM_SOFTLOCKUP_PANIC=y
CONFIG_BOOTPARAM_SOFTLOCKUP_PANIC_VALUE=1
CONFIG_DETECT_HUNG_TASK=y
CONFIG_DEFAULT_HUNG_TASK_TIMEOUT=300

kdump 相关:
CONFIG_KEXEC=y
CONFIG_CRASH_DUMP=y
CONFIG_PHYSICAL_START=0x1000000
CONFIG_RELOCATABLE=y

netconsole 相关:
CONFIG_NETCONSOLE=y
CONFIG_NETCONSOLE_DYNAMIC=y
CONFIG_NETPOLL=y

kprobe,jump label 相关:
CONFIG_KPROBES=y
CONFIG_JUMP_LABEL=y

为什么Linux内核不允许在中断中休眠?

我以前一直以为 Linux 内核之所以不允许在中断中休眠是因为中断上下文中无法获取 thread_info,task_struct 等进程相关的结构体,从而无法调度。

今天又重新看了一下相关的代码,发现实际上不是。在最新的代码中,x86 32 使用的 irq stack 中也保存了thread_info,我们可以看 execute_on_irq_stack() 的定义:

[c]
union irqctx {
struct threadinfo tinfo;
u32 stack[THREAD_SIZE/sizeof(u32)];
} __attribute
((aligned(THREAD_SIZE)));

static inline int
execute_on_irq_stack(int overflow, struct irq_desc desc, int irq)
{
union irq_ctx
curctx, irqctx;
u32
isp, arg1, arg2;

    curctx = (union irq_ctx *) current_thread_info();
    irqctx = __this_cpu_read(hardirq_ctx);

    /*
     * this is where we switch to the IRQ stack. However, if we are
     * already using the IRQ stack (because we interrupted a hardirq
     * handler) we can't do that and just have to keep using the
     * current stack (which is the irq stack already after all)
     */
    if (unlikely(curctx == irqctx))
            return 0;

    /* build the stack frame on the IRQ stack */
    isp = (u32 *) ((char *)irqctx + sizeof(*irqctx));
    irqctx-&gt;tinfo.task = curctx-&gt;tinfo.task;
    irqctx-&gt;tinfo.previous_esp = current_stack_pointer;

    /* Copy the preempt_count so that the [soft]irq checks work. */
    irqctx-&gt;tinfo.preempt_count = curctx-&gt;tinfo.preempt_count;

    if (unlikely(overflow))
            call_on_stack(print_stack_overflow, isp);

    asm volatile("xchgl     %%ebx,%%esp     n"
                 "call      *%%edi          n"
                 "movl      %%ebx,%%esp     n"
                 : "=a" (arg1), "=d" (arg2), "=b" (isp)
                 :  "0" (irq),   "1" (desc),  "2" (isp),
                    "D" (desc-&gt;handle_irq)
                 : "memory", "cc", "ecx");
    return 1;

}
[/c]

(注:x86 都已经使用 irq stack 了,和进程的内核栈独立开了,这样即使 irq 处理函数中占用了很多栈也不会影响外面的了。)

所以这不是问题。也就是说,技术上我们完全可以做到在中断中休眠。Linux 内核之所以没有这么做是出于设计上的原因。

如果这还不足以说明问题的话,还有个例子:do_page_fault() 也是在中断上下文中调用的(注:此处更严格的讲是 trap,而非 interrupt,但无论哪个都肯定不是普通的进程上下文,相对而言还算是中断上下文),但是它是可能休眠的,至少它明显调用了可能休眠的函数 down_read() 。

为什么要这么设计呢?因为在 Linux 内核中能让 do_page_fault() 休眠的地方基本上只有copy_from_user(),copy_to_user()(其它地方触发 page fault 会导致 oops),它们在使用用户空间的页面时可能会因为对应的页面不在物理内存中而触发 swap 等,即 handle_mm_fault() 所做的。这种情况下休眠是合理的,因为调用 copy_from_user() 的进程本身就是需要等待这个资源。休眠不就是为了等待资源吗?

为什么其它中断(注:此处是指 IRQ,或者严格意义上的 interrupt,非 trap)不能休眠?假设 CPU 上正在执行的是某个高优先级的进程 A,它本身没有使用任何网络通信,突然网卡中断来了,它被中断而且被休眠了,那么,这看起来就像是进程 A 本身在等待某网络资源,而实际上根本不是。

换句话说,如果在 IRQ 中休眠,被打断的当前进程很可能不是需要等待的进程,更进一步讲,在中断中我们根本无法知道到底是哪个进程需要休眠。更何况,这里还没有考虑到在某个中断中休眠会不会影响下一个中断之类的更复杂的问题。由此可见,如果真允许在中断中休眠的话,那么设计将会是很复杂的。

因此,这完全是一个设计的问题。中断中休眠技术上可实现,但设计上不好。

另外,Linux 内核中很多会休眠的函数会调用 might_sleep(),它是用来检测是否在中断上下文中,如果是就是触发一个警告 “BUG: sleeping function called from invalid context”。可是为什么 do_page_fault() 中的函数没有呢?这是因为普通的 IRQ 在进入处理函数之前都会调用 irq_enter(),它里面改变了进程的 preempt 的值:

[c]

define __irq_enter()

    do {                                            
            account_system_vtime(current);          
            add_preempt_count(HARDIRQ_OFFSET);      
            trace_hardirq_enter();                  
    } while (0)

void irq_enter(void)
{
int cpu = smp_processor_id();

    rcu_irq_enter();
    if (is_idle_task(current) &amp;&amp; !in_interrupt()) {
            /*
             * Prevent raise_softirq from needlessly waking up ksoftirqd
             * here, as softirq will be serviced on return from interrupt.
             */
            local_bh_disable();
            tick_check_idle(cpu);
            _local_bh_enable();
    }

    __irq_enter();

}
[/c]

而 page fault 的话不会经过这个流程。这也从另一面证明了这是个设计的问题。

顺便说一句,比较新的 Linux 内核中已经支持中断线程化了:

[c]
int request_threaded_irq(unsigned int irq, irq_handler_t handler,
irq_handler_t thread_fn, unsigned long irqflags,
const char devname, void dev_id)
[/c]

所以一部分中断处理可以在进程上下文中完成了。

perfbook 读书笔记:ACCESS_ONCE()

如果你看过 Linux 内核中的 RCU 的实现,你应该注意到了这个叫做 ACCESS_ONCE() 宏,但是并没有很多人真正理解它的含义。网上有的地方甚至对此有错误的解释,所以特写此文来澄清一下。

虽然我早在读 perfbook 之前就了解了 ACCESS_ONCE() 的含义(通过询问大牛 Paul),但这本书中正好也没有很详细地介绍这个宏,所以就当是此书的读书笔记了。

定义

它的定义很简单,在 include/linux/compiler.h 的底部:

[c]

define ACCESS_ONCE(x) ((volatile typeof(x) )&(x))

[/c]

仅从语法上讲,这似乎毫无意义,先取其地址,在通过指针取其值。而实际上不然,多了一个关键词 volatile,所以它的含义就是强制编译器每次使用 x 都从内存中获取。

原因
仅仅从定义来看基本上看不大出来为什么要引入这么一个东西。可以通过几个例子(均来自 Paul,我做了小的修改)看一下。

1. 循环中有每次都要读取的全局变量:

[c]

static int should_continue;
static void do_something(void);

while (should_continue)
do_something();
[/c]

假设 do_something() 函数中并没有对变量 should_continue 做任何修改,那么,编译器完全有可能把它优化成:

[c]

if (should_continue)
for (;;)
do_something();
[/c]

这很好理解,不是吗?对于单线程的程序,这么做完全没问题,可是对于多线程,问题就出来了:如果这个线程在执行do_something() 的期间,另外一个线程改变了 should_continue 的值,那么上面的优化就是完全错误的了!更严重的问题是,编译器根本就没有办法知道这段代码是不是并发的,也就无从决定进行的优化是不是正确的!

这里有两种解决办法:1) 给 should_continue 加锁,毕竟多个进程访问和修改全局变量需要锁是很自然的;2) 禁止编译器做此优化。加锁的方法有些过了,毕竟 should_continue 只是一个布尔,而且退一步讲,就算每次读到的值不是最新的 should_continue 的值也可能是无所谓的,大不了多循环几次,所以禁止编译器做优化是一个更简单也更容易的解决办法。我们使用 ACCESS_ONCE() 来访问 should_continue:

[c]

while (ACCESS_ONCE(should_continue))
do_something();
[/c]

2. 指针读取一次,但要dereference多次:

[c]

p = global_ptr;
if (p && p->s && p->s->func)
p->s->func();
[/c]

那么编译器也有可能把它编译成:

[c]

if (global_ptr && global_ptr->s && global_ptr->s->func)
global_ptr->s->func();
[/c]

你可以谴责编译器有些笨了,但事实上这是C标准允许的。这种情况下,另外的进程做了 global_ptr = NULL; 就会导致后一段代码 segfault,而前一段代码没问题。同上,所以这时候也要用 ACCESS_ONCE():

[c]

p = ACCESS_ONCE(global_ptr);
if (p && p->s && p->s->func)
p->s->func();
[/c]

3. watchdog 中的变量:

[c]
for (;;) {
still_working = 1;
do_something();
}
[/c]

假设 do_something() 定义是可见的,而且没有修改 still_working 的值,那么,编译器可能会把它优化成:

[c]
still_working = 1;
for (;;) {
do_something();
}
[/c]

如果其它进程同时执行了:

[c]
for (;;) {
still_working = 0;
sleep(10);
if (!still_working)
panic();
}
[/c]

通过 still_working 变量来检测 wathcdog 是否停止了,并且等待10秒后,它确实停止了,panic()!经过编译器优化后,就算它没有停止也会 panic!!所以也应该加上 ACCESS_ONCE():

[c]
for (;;) {
ACCESS_ONCE(still_working) = 1;
do_something();
}
[/c]

综上,我们不难看出,需要使用 ACCESS_ONCE() 的两个条件是:

1. 在无锁的情况下访问全局变量;
2. 对该变量的访问可能被编译器优化成合并成一次(上面第1、3个例子)或者拆分成多次(上面第2个例子)。

例子

Linus 在邮件中给出的另外一个例子是:

编译器有可能把下面的代码:

[c]
if (a > MEMORY) {
do1;
do2;
do3;
} else {
do2;
}
[/c]

优化成:

[c]
if (a > MEMORY)
do1;
do2;
if (a > MEMORY)
do3;
[/c]

这里完全符合上面我总结出来的两个条件,所以也应该使用 ACCESS_ONCE()。正如 Linus 所说,不是编译器一定会这么优化,而是你无法证明它不会做这样的优化。

So the rule is: if you access unlocked values, you use ACCESS_ONCE(). You
don’t say “but it can’t matter”. Because you simply don’t know.

再看实际中的例子:

commit 0ad92ad03aa444b312bd318b0341011a8be09d13
Author: Eric Dumazet
Date:   Tue Nov 1 12:56:59 2011 +0000

    udp: fix a race in encap_rcv handling

    udp_queue_rcv_skb() has a possible race in encap_rcv handling, since
    this pointer can be changed anytime.

    We should use ACCESS_ONCE() to close the race.

diff --git a/net/ipv4/udp.c b/net/ipv4/udp.c
index 131d8a7..ab0966d 100644
--- a/net/ipv4/udp.c
+++ b/net/ipv4/udp.c
@@ -1397,6 +1397,8 @@ int udp_queue_rcv_skb(struct sock *sk, struct sk_buff *skb)
     nf_reset(skb);

     if (up->encap_type) {
+        int (*encap_rcv)(struct sock *sk, struct sk_buff *skb);
+
         /*
          * This is an encapsulation socket so pass the skb to
          * the socket's udp_encap_rcv() hook. Otherwise, just
@@ -1409,11 +1411,11 @@ int udp_queue_rcv_skb(struct sock *sk, struct sk_buff *skb)
          */

         /* if we're overly short, let UDP handle it */
-        if (skb->len > sizeof(struct udphdr) &&
-            up->encap_rcv != NULL) {
+        encap_rcv = ACCESS_ONCE(up->encap_rcv);
+        if (skb->len > sizeof(struct udphdr) && encap_rcv != NULL) {
             int ret;

-            ret = (*up->encap_rcv)(sk, skb);
+            ret = encap_rcv(sk, skb);
             if (ret <= 0) {
                 UDP_INC_STATS_BH(sock_net(sk),
                          UDP_MIB_INDATAGRAMS,

更多

或许看了上面的会让你有一种错觉,volatile 可以解决同步的问题,其实不然,它只解决其中一个方面。而且上面所有的例子有一个共同的特点:所有的写操作都是简单的赋值(相对于大于CPU字宽的结构体赋值),简单赋值操作在所有平台上都是原子性的,而如果是做加法操作,原子性未必可以保证,更不用说需要 memory barrier 的时候了。所以,不要滥用 volatile。

perfbook 读书笔记:SLAB_DESTROY_BY_RCU

perfbook 书中第8.3.3.6节讲到了类型安全,提到了Linux内核中的 SLAB_DESTROY_BY_RCU。但是书中并没有更详细的介绍这个特性。这里更详细地说一下。

要理解 SLABDESTROYBY_RCU,最重要的是看 kmem_cache_destroy(),以 slub 为例,
[c]
void kmem_cache_destroy(struct kmem_cache *s)
{
down_write(&slub_lock);
s->refcount—;
if (!s->refcount) {
list_del(&s->list);
up_write(&slub_lock);
if (kmem_cache_close(s)) {
printk(KERN_ERR “SLUB %s: %s called for cache that “
“still has objects.n”, s->name, __func
);
dump_stack();
}
if (s->flags & SLAB_DESTROY_BY_RCU)
rcu_barrier();
sysfs_slab_remove(s);
} else
up_write(&slub_lock);
}
[/c]

看那两行就足够了,rcu_barrier(); 是用来等待所有的 call_rcu() 回调函数结束,那么,kmem_cache_destroy() 在 SLAB_DESTROY_BY_RCU 的情况很明显就是等待所有 kmem_cache_free() 完成。

和普通的用 kmem_cache_alloc() 分配出来的对象相比,这种内存分配方式提供了更弱的保证,普通的分配可以保证对象不会被释放回 cache 中,而这个仅仅保证它不会被彻底释放,但不保证它会被放回 cache 重新利用,也就是说类型是不变的,即所谓的类型安全。实际上,在此期间它很有可能已经被放回 cache 重新利用了。

正是因为这种保证更弱了,所以在 rcu_read_lock() 并发区内就要多一个检查,检查是否还是之前的那个对象,因为这是类型安全的,所以对它进行同类型的检查是完全合法的。一个很好的例子是 __lock_task_sighand():

[c]
struct sighand_struct __lock_task_sighand(struct task_struct tsk,
unsigned long flags)
{
struct sighand_struct
sighand;

    for (;;) {
            local_irq_save(*flags);
            rcu_read_lock();
            sighand = rcu_dereference(tsk-&gt;sighand);
            if (unlikely(sighand == NULL)) {
                    rcu_read_unlock();
                    local_irq_restore(*flags);
                    break;
            }

            spin_lock(&amp;sighand-&gt;siglock);
            if (likely(sighand == tsk-&gt;sighand)) {
                    rcu_read_unlock();
                    break;
            }
            spin_unlock(&amp;sighand-&gt;siglock);
            rcu_read_unlock();
            local_irq_restore(*flags);
    }

    return sighand;

}
[/c]

注意,->siglock 是在 ->ctor() 中初始化的,所以刚分配出来的 sighand 的 ->siglock 也是已初始化的。

在此基础上,Linux 内核中还衍生出一个新的哈希链表,hlist_nulls,具体可以参考 Documentation/RCU/rculist_nulls.txt。