3. 流表查找与匹配：内核中流表查找流程、哈希表设计、通配符匹配与精确匹配的区别

3.1 内核数据路径中的流表查找流程

OVS 内核数据路径（Kernel Datapath）的核心任务是将到达的报文与已缓存的流表项进行匹配。查找流程设计为快速路径，以最小化每个报文的处理延迟。整个流程可概括为以下步骤：

1. 报文解析（Parse）：从报文头部提取关键字段，如源/目的 MAC、IP 地址、端口号、VLAN ID 等，构建查找关键字（Key）。
2. 哈希计算（Hash）：对关键字进行哈希运算，生成哈希值，用于索引哈希表。
3. 精确匹配查找（Exact Match Lookup）：在 EMC（Exact Match Cache） 中查找。EMC 是一个小型、高速的精确匹配缓存，存储最近匹配成功的流表项。
4. 通配符匹配查找（Wildcard Match Lookup）：若 EMC 未命中，则进入 MFC（Masked Flow Cache） 或 DPDK Flow Table 进行通配符匹配。此步骤需要遍历或使用更复杂的查找结构（如 TSS、Tuple Space Search）。
5. 动作执行（Execute Actions）：匹配成功后，执行流表项中定义的动作集（如 Output、Drop、Modify Fields、Recirculate）。
6. 缓存更新（Cache Update）：若在 MFC 中匹配成功，则将结果插入 EMC，加速后续相同流的处理。

3.2 哈希表设计：EMC 与 MFC 的数据结构

OVS 内核数据路径使用两种核心哈希表结构来支持不同粒度的匹配：

3.2.1 EMC 哈希表设计

EMC 采用桶式哈希表，每个桶包含一个固定大小的条目数组（通常为 4 或 8 个条目）。哈希冲突时，采用线性探测或链地址法解决。关键字由报文头部字段（如 5 元组）组成，哈希函数通常使用 Jhash 或 MurmurHash 以平衡速度与分布均匀性。

3.2.2 MFC 哈希表设计

MFC 需要支持通配符匹配，因此不能直接使用简单哈希。其核心设计是掩码数组（Mask Array）：

• 每个流表项关联一个掩码（Mask），用于指定哪些位参与匹配。
• 所有流表项按掩码分组，每组内使用精确哈希。
• 查找时，依次遍历所有掩码组，对每个组计算哈希并查找。

3.3 精确匹配 vs 通配符匹配

两种匹配模式在 OVS 流表中并存，服务于不同的使用场景：

3.3.1 精确匹配的实现细节

在 OVS 内核模块中，精确匹配通过 struct sw_flow_key 结构体表示。该结构体包含所有可匹配字段的紧凑排列。查找时，将报文解析后的关键字与 EMC 中的条目进行 memcmp 比较。由于关键字长度固定（通常 48 字节），比较操作非常高效。

/* 内核中精确匹配的关键比较 */
static inline bool flow_key_equal(const struct sw_flow_key *a,
                                  const struct sw_flow_key *b)
{
    return !memcmp(a, b, sizeof(struct sw_flow_key));
}

3.3.2 通配符匹配的实现细节

通配符匹配使用 struct sw_flow_mask 结构体，其中包含一个掩码位图。匹配时，需要将关键字与流表项进行掩码后比较：

/* 通配符匹配的核心逻辑 */
static inline bool flow_masked_equal(const struct sw_flow_key *key,
                                     const struct sw_flow_key *masked_key,
                                     const struct sw_flow_mask *mask)
{
    const u32 *kp = (const u32 *)key;
    const u32 *mp = (const u32 *)masked_key;
    const u32 *msp = (const u32 *)&mask->key;
    int i;

    for (i = 0; i < sizeof(struct sw_flow_key) / sizeof(u32); i++) {
        if ((kp[i] & msp[i]) != mp[i])
            return false;
    }
    return true;
}

3.4 流表查找的优化策略

• EMC 预热（Warm-up）：在流量突发前，通过用户态控制器主动插入预期流的精确匹配项，避免初始阶段的 MFC 遍历。
• 哈希种子随机化：每次系统启动时随机化哈希种子，防止攻击者构造哈希冲突攻击（Hash DoS）。
• 多级缓存：在 EMC 和 MFC 之间引入 SMC（Secondary Match Cache），存储近期匹配但未达到 EMC 插入阈值的流。
• 批量查找（Batching）：在 DPDK 加速路径中，将多个报文的关键字打包，使用 SIMD 指令并行计算哈希和比较。

3.5 常见问题与排查思路