1、前言

我们在前面的文章中提到，在 Open vSwitch 实现中，存在快速路径和慢速路径两个概念，其中内核 datapath 代表了快速路径，当网络数据报文到达网卡后，OVS 内核 datapath 会首先接收到这个报文，然后在内核态进行流表查找并进行处理。因此，本文将会讲述 OVS 内核态流表查找流程。

2、元组空间搜索

2.1、原理

OpenFlow 协议支持多字段匹配，直至 1.3 版本，OpenFlow 已经支持 39 个匹配字段。作为兼容 OpenFlow 协议的虚拟交换机，OVS 的多字段流表查找开销，是影响网络数据报文转发的重要因素。在网络报文过滤等领域已经对多字段查找进行了大量研究，若将每一个字段作为一个维度，多字段流分类算法可以分为两类：

单维组合分类算法：单独地对每个字段进行匹配，并对每个字段的匹配结果进行合并，从而找到最终的匹配规则，例如递归流分类、位向量流分类等；
多维联合分类算法：将所有字段看做一个维度，进行联合查找，例如决策树、元组空间搜索等。

OVS 在内核态使用了元组空间搜索算法（Tuple Space Search，简称 TSS）进行流表查找，因此本节主要讲述元组空间搜索算法。

元组空间搜索算法的核心思想是，把所有规则按照每个字段的前缀长度进行组合，并划分为不同的元组中，然后在这些元组集合中进行哈希查找。我们举例说明，假设现有 10 条规则以及 3 个匹配字段，每个匹配字段长度均为 4，如表 1 所示：

规则	字段 1	字段 2	字段 3
R1	01**	0***	1***
R2	000*	01**	010*
R3	011*	11**	100*
R4	10**	*	1***
R5	11**	*	0***
R6	01**	1***	0***
R7	10**	0***	1***
R8	101*	01**	111*
R9	0***	101*	1010
R10	1***	111*	1100

表 1：规则集

我们将每条规则各匹配字段的前缀长度提取出来，按照前缀长度进行组合，并根据前缀长度组合进行分组，如表 2 所示：

前缀长度组合	规则
[2,1,1]	R1, R6, R7
[3,2,3]	R2, R3, R8
[2,0,1]	R4, R5
[1,3,4]	R9, R10

表 2：前缀长度组合

我们将每个前缀长度组合称为元组，每个元组对应于哈希表的一个桶，同一前缀长度组合内的所有规则放置在同一个哈希桶内，如图 1 所示：

图 1：元组空间搜索

我们可以从图 1 看到，10 条规则被划分为 4 个元组，因此最多只需要四次查找，就可以找到对应的规则。

2.2、优缺点

元组空间搜索算法有哪些优缺点呢？首先我们来看看优点，从论文 The Design and Implementation of Open vSwitch 我们可以得到结论：

因为 TSS 基于哈希表实现，因此支持高效的、常数时间的表项更新，这使得该算法适用于虚拟化数字中心的网络环境；
TSS 支持任意数量的字段匹配；
TSS 的空间复杂度为 O(N)，N 为规则数目。

元组空间搜索算法的缺点是，由于基于哈希表实现，因此查找的时间复杂度不能确定。当所有规则各个字段的前缀长度组合数目过多时，查找性能会大大降低，最坏情况下需要查找所有规则。

3、内核态流表查找流程

3.1、流程梳理

从上一篇文章《深入理解 Open vSwitch（三）：流缓存设计
》中，我们了解到 OVS 内核 datapath 实现了 microflow + megaflow 流缓存，因此内核态流表查找也将围绕着这两层流缓存进行：

图 2：OVS 流缓存的数据结构

我们结合图 2 可以得出如下查找流程：

查找 microflow 缓存：根据数据报文 SKB 的 hash 值，定位到 mask_cache_entry 数组中的某个元素，并得到该元素缓存的掩码数组索引值；
查找 megaflow 缓存：根据步骤 1 中查找到的掩码数组索引值，定位到掩码数组中的某个元素，并得到该元素的掩码，然后根据掩码定位到具体的哈希桶，并遍历该哈希桶中的所有节点，直到找到匹配的 flow。

3.2、查找 microflow 缓存

OVS 内核态流表查找的入口函数是定义在 datapath/flow_table.c 文件中的 ovs_flow_tbl_lookup_stats 函数：

struct sw_flow *ovs_flow_tbl_lookup_stats(struct flow_table *tbl,
                      const struct sw_flow_key *key,
                      u32 skb_hash,
                      u32 *n_mask_hit)
{
    struct mask_array *ma = rcu_dereference(tbl->mask_array);
    struct table_instance *ti = rcu_dereference(tbl->ti);
    struct mask_cache_entry *entries, *ce;
    struct sw_flow *flow;
    u32 hash;
    int seg;

    *n_mask_hit = 0;
    if (unlikely(!skb_hash)) {
        u32 mask_index = 0;

        return flow_lookup(tbl, ti, ma, key, n_mask_hit, &mask_index);
    }

    /* Pre and post recirulation flows usually have the same skb_hash
     * value. To avoid hash collisions, rehash the 'skb_hash' with
     * 'recirc_id'.  */
    if (key->recirc_id)
        skb_hash = jhash_1word(skb_hash, key->recirc_id);

    ce = NULL;
    hash = skb_hash;
    entries = this_cpu_ptr(tbl->mask_cache);

    /* Find the cache entry 'ce' to operate on. */
    for (seg = 0; seg < MC_HASH_SEGS; seg++) {
        int index = hash & (MC_HASH_ENTRIES - 1);
        struct mask_cache_entry *e;

        e = &entries[index];
        if (e->skb_hash == skb_hash) {
            flow = flow_lookup(tbl, ti, ma, key, n_mask_hit,
                       &e->mask_index);
            if (!flow)
                e->skb_hash = 0;
            return flow;
        }

        if (!ce || e->skb_hash < ce->skb_hash)
            ce = e;  /* A better replacement cache candidate. */

        hash >>= MC_HASH_SHIFT;
    }

    /* Cache miss, do full lookup. */
    flow = flow_lookup(tbl, ti, ma, key, n_mask_hit, &ce->mask_index);
    if (flow)
        ce->skb_hash = skb_hash;

    return flow;
}

ovs_flow_tbl_lookup_stats() 的函数参数如下：

tbl：类型为 struct flow_table，表示专属于每个 datapath 的流表组织结构；
key：类型为 struct sw_flow_key，表示从数据报文提取出来的匹配关键字；
skb_hash：表示数据报文 SKB 的 hash 值；
n_mask_hit：输出参数，表示尝试匹配掩码的次数。

对 microflow 缓存的查找基于 SKB hash 值。因此，我们可以看到，当 skb_hash 为 0 时，OVS 则会进行完全查找：

//如果 skb_hash 为 0，则 full lookup
if (unlikely(!skb_hash)) {
    u32 mask_index = 0;

    return flow_lookup(tbl, ti, ma, key, n_mask_hit, &mask_index);
}

此外，如果一个数据报文需要在 OVS 中重入流水线（recirculation），那么在 recirculation 之前和之后，这个报文的 SKB hash 值都是一致的，为了防止哈希冲突，需要将 skb_hash 再进行一次哈希（rehash）：

/* Pre and post recirulation flows usually have the same skb_hash
 * value. To avoid hash collisions, rehash the 'skb_hash' with
 * 'recirc_id'.  */
if (key->recirc_id)
    skb_hash = jhash_1word(skb_hash, key->recirc_id);

在进行 microflow 缓存查找时，OVS 会把 skb_hash 分为 4 个字节，并按照从低到高的顺序，以次使用每个字节作为 mask_cache_entry 数组的索引值，然后判断对应的 mask_cache_entry->skb_hash 是否与 skb_hash 一致，是则使用对应的 mask_cache_entry->mask_index 作为掩码数组的索引值来进行下一步的 megaflow 缓存查找：

ce = NULL;
hash = skb_hash;
// mask_cache_entry 数组，大小为 256，即 microflow cache
entries = this_cpu_ptr(tbl->mask_cache);

/* Find the cache entry 'ce' to operate on. */
// 将 hash 分为 4 个字节，从低到高的顺序，进行查找
//MC_HASH_SEGS 为 4
for (seg = 0; seg < MC_HASH_SEGS; seg++) {
    //MC_HASH_ENTRIES 为 256
    int index = hash & (MC_HASH_ENTRIES - 1);   // 将 hash 最低的字节按位与，即取出 hash 最低字节
    struct mask_cache_entry *e;

    e = &entries[index];
    if (e->skb_hash == skb_hash) {
        flow = flow_lookup(tbl, ti, ma, key, n_mask_hit,
                   &e->mask_index);
        if (!flow)
            e->skb_hash = 0;
        return flow;
    }

    // 选出 4 个字节中 skb hash 值最小的那个，作为没找到缓存时的最佳候选
    if (!ce || e->skb_hash < ce->skb_hash)
        ce = e;  /* A better replacement cache candidate. */

    hash >>= MC_HASH_SHIFT;
}

flow_table 结构体的 mask_cache_entry 数组（mask_cache）是一个 Linux per-CPU 变量，因此首先需要获取指向当前 CPU 的 mask_cache 变量的指针：

entries = this_cpu_ptr(tbl->mask_cache);

随后，OVS 按照从低到高的顺序遍历 skb_hash 的 4 个字节，将每个字节作为索引值来访问 mask_cache_entry 数组中的元素，如果对应的 mask_cache_entry->skb_hash 与报文的 skb_hash 一致，则调用 flow_lookup 函数来进行下一步的查找。

另外需要注意的是，mask_cache_entry 数组中每个元素的成员变量 skb_hash 和 mask_index 的初始值均为 0，即初始状态下，microflow 缓存都是未命中的。那么，mask_cache_entry 数组是如何填充的呢？ 我们可以从上文遍历 skb_hash 的 4 个字节的代码块中看到，当查找 microflow 缓存失败时，OVS 会把在取成员变量 skb_hash 最小的 mask_cache_entry 作为 ce（candidate entry）：

if (!ce || e->skb_hash < ce->skb_hash)
    ce = e;  /* A better replacement cache candidate. */

然后在后续的 megaflow 缓存完全查找中，将相应的值填充进成员变量 skb_hash 和 mask_index：

flow = flow_lookup(tbl, ti, ma, key, n_mask_hit, &ce->mask_index);
if (flow)
    ce->skb_hash = skb_hash;

flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
if (flow) { /* Found */
    *index = i;
    return flow;
}

3.3、查找 megaflow 缓存

查找 megaflow 缓存的入口函数是定义在 datapath/flow_table.c 文件中的 flow_lookup 函数：

static struct sw_flow *flow_lookup(struct flow_table *tbl,
                   struct table_instance *ti,
                   const struct mask_array *ma,
                   const struct sw_flow_key *key,
                   u32 *n_mask_hit,
                   u32 *index)
{
    struct sw_flow_mask *mask;
    struct sw_flow *flow;
    int i;

    if (*index < ma->max) {
        mask = rcu_dereference_ovsl(ma->masks[*index]);
        if (mask) {
            flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
            if (flow)
                return flow;
        }
    }

    for (i = 0; i < ma->max; i++)  {

        if (i == *index)
            continue;

        mask = rcu_dereference_ovsl(ma->masks[i]);
        if (!mask)
            continue;

        flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
        if (flow) { /* Found */
            *index = i;
            return flow;
        }
    }

    return NULL;
}

flow_lookup 函数的参数如下：

tbl：类型为 struct flow_table，表示专属于每个 datapath 的流表组织结构；
ti：类型为 struct table_instance，表示流表实例，以哈希表结构组织，等同于 megaflow 缓存；
ma：类型为 struct mask_array，表示掩码数组；
key：类型为 struct sw_flow_key，表示从数据报文提取出来的匹配关键字；
n_mask_hit：输出参数，表示尝试匹配掩码的次数；
index：掩码数组的索引值。

需要注意的是，在上文的 microflow 缓存查找过程中，在 microflow 缓存命中和缓存未命中的情况下，都会调用 flow_lookup 函数进行 megaflow 缓存查找，因此 flow_lookup 函数需要同时处理这两个情况。

OVS 首先会根据传入的参数 index 来获取掩码数组中对应的元素，然后调用 masked_flow_lookup 函数：

// 根据传入的 index 获取到掩码数组的掩码，根据该掩码进行查找
if (*index < ma->max) {
    mask = rcu_dereference_ovsl(ma->masks[*index]);
    if (mask) {
        flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
        if (flow)
            return flow;
    }
}

masked_flow_lookup 函数定义如下：

static struct sw_flow *masked_flow_lookup(struct table_instance *ti,
                      const struct sw_flow_key *unmasked,
                      const struct sw_flow_mask *mask,
                      u32 *n_mask_hit)
{
    struct sw_flow *flow;
    struct hlist_head *head;
    u32 hash;
    struct sw_flow_key masked_key;

    ovs_flow_mask_key(&masked_key, unmasked, false, mask);
    hash = flow_hash(&masked_key, &mask->range);
    head = find_bucket(ti, hash);
    (*n_mask_hit)++;
    hlist_for_each_entry_rcu(flow, head, flow_table.node[ti->node_ver]) {
        if (flow->mask == mask && flow->flow_table.hash == hash &&
            flow_cmp_masked_key(flow, &masked_key, &mask->range))
            return flow;
    }
    return NULL;
}

masked_flow_lookup() 的工作如下：

首先会调用 ovs_flow_mask_key 函数进行掩码计算，该函数的工作是将数据报文的匹配关键字 unmasked 和掩码 mask 进行按位与计算，并把计算结果赋值给 masked_key；
根据按位与的计算结果 masked_key 与掩码的有效范围 mask->range 进行哈希计算；
根据哈希计算的结果获取流表实例（ti）的哈希桶的链表头；
遍历链表中的每个 flow 节点，直至找到与匹配关键字与 masked_key 一致的 flow。

我们回到 flow_lookup 函数。当调用 masked_flow_lookup 函数并查找到匹配的 flow 之后，则会立即返回这个 flow，反之如果查找失败，则会遍历整个掩码数组来进行完全查找：

for (i = 0; i < ma->max; i++)  {
    // 这个 index 所对应的掩码在上面已经查找过并且查找失败，因此跳过
    if (i == *index)
        continue;

    mask = rcu_dereference_ovsl(ma->masks[i]);
    if (!mask)
        continue;

    // 查找成功
    flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
    if (flow) { /* Found */
        *index = i;
        return flow;
    }
}

3.4、缓存未命中时怎么办？

我们在上文讲述了 OVS 内核态流表查找流程，其中包括 microflow 缓存查找以及 megaflow 缓存查找。如果内核态的缓存未命中会怎么办呢？其实通过之前的文章我们可以了解到，当数据报文未能在 OVS 内核态的快速路径匹配到相应的 flow 时，这时只能被上送到（upcall）到用户态的慢速路径，并在用户态中进行流表查找。我们简单看一下 datapath/datapath.c 文件中调用 ovs_flow_tbl_lookup_stats 函数的地方：

/* Look up flow. */
flow = ovs_flow_tbl_lookup_stats(&dp->table, key, skb_get_hash(skb),
                 &n_mask_hit);
if (unlikely(!flow)) {
    struct dp_upcall_info upcall;
    int error;

    memset(&upcall, 0, sizeof(upcall));
    upcall.cmd = OVS_PACKET_CMD_MISS;
    upcall.portid = ovs_vport_find_upcall_portid(p, skb);
    upcall.mru = OVS_CB(skb)->mru;
    error = ovs_dp_upcall(dp, skb, key, &upcall, 0);
    if (unlikely(error))
        kfree_skb(skb);
    else
        consume_skb(skb);
    stats_counter = &stats->n_missed;
    goto out;
}

可见，当通过 ovs_flow_tbl_lookup_stats 函数在查找流表失败时，OVS 就会调用 ovs_dp_upcall 函数执行 upcall 流程。

4、总结

本文首先介绍了元组空间搜索算法的原理和优缺点，然后围绕着 microflow 和 megaflow 缓存来讲述 OVS 内核态流表查找流程。至于 OVS 内核态缓存未命中时的 upcall 处理，以及如何生成 megaflow 缓存，将会在后续的文章讲述。

crezov

路漫漫其修远兮，吾将上下而求索

深入理解 Open vSwitch（四）：内核态流表查找分析

1、前言

2、元组空间搜索

2.1、原理

2.2、优缺点

3、内核态流表查找流程

3.1、流程梳理

3.2、查找 microflow 缓存

3.3、查找 megaflow 缓存

3.4、缓存未命中时怎么办？

4、总结

参考资料

One comment:

发表评论取消回复

联系我

1、前言

2、元组空间搜索

2.1、原理

2.2、优缺点

3、内核态流表查找流程

3.1、流程梳理

3.2、查找 microflow 缓存

3.3、查找 megaflow 缓存

3.4、缓存未命中时怎么办？

4、总结

参考资料

One comment:

发表评论 取消回复

联系我

发表评论取消回复