深入理解 Open vSwitch(四):内核态流表查找分析

1、前言

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

2、元组空间搜索

2.1、原理

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

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

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 所示:

image

图 1:元组空间搜索

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

2.2、优缺点

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

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

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

3、内核态流表查找流程

3.1、流程梳理

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

image

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

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

  1. 查找 microflow 缓存:根据数据报文 SKB 的 hash 值,定位到 mask_cache_entry 数组中的某个元素,并得到该元素缓存的掩码数组索引值;
  2. 查找 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_hashmask_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_hashmask_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() 的工作如下:

  1. 首先会调用 ovs_flow_mask_key 函数进行掩码计算,该函数的工作是将数据报文的匹配关键字 unmasked 和掩码 mask 进行按位与计算,并把计算结果赋值给 masked_key
  2. 根据按位与的计算结果 masked_key 与掩码的有效范围 mask->range 进行哈希计算;
  3. 根据哈希计算的结果获取流表实例(ti)的哈希桶的链表头;
  4. 遍历链表中的每个 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 缓存,将会在后续的文章讲述。

参考资料

  1. https://www.sdnlab.com/15713.html
  2. https://segmentfault.com/a/1190000016113797

One comment:

  1. 谢谢分享!!!看了好几遍,收获很多,自己也总结了一下。有两个问题:关于mask命中次数+1,n_mask_hit没有初始化。另一个是,把一个hash分成了4份,如果都没有命中,更新skb_hash最小的mask_cache_entry,那这个利用率岂不是很低,如果4个桶,有3个不怎么用到的桶skb_hash很大,那相当于这个机制没啥用了。也可能这个hash算法缺点就这个样。

philo_zhou进行回复 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注