static inline bool

emc_probabilistic_insert(struct dp_netdev_pmd_thread *pmd,

                         const struct netdev_flow_key *key,

                         struct dp_netdev_flow *flow)

{

    /* Insert an entry into the EMC based on probability value 'min'. By

     * default the value is UINT32_MAX / 100 which yields an insertion

     * probability of 1/100 ie. 1% */

    uint32_t min = pmd->ctx.emc_insert_min;

    if (min && random_uint32() <= min) {

        emc_insert(&(pmd->flow_cache).emc_cache, key, flow);

        return true;

    }

    return false;

}

入口在这里，往下走,传进去subtable有效字段有多大

static uint32_t

dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable,

                              uint32_t keys_map,

                              const struct netdev_flow_key *keys[],

                              struct dpcls_rule **rules)

{

    return lookup_generic_impl(subtable, keys_map, keys, rules,

                               subtable->mf_bits_set_unit0,

                               subtable->mf_bits_set_unit1);

}

static inline uint32_t ALWAYS_INLINE

lookup_generic_impl(struct dpcls_subtable *subtable,      // 当前的subtable

                    uint32_t keys_map,                    // miss_bit_map

                    const struct netdev_flow_key *keys[], // miss_key

                    struct dpcls_rule **rules,            // save hit_rule

                    const uint32_t bit_count_u0,

                    const uint32_t bit_count_u1)

{

    // 有几个包

    const uint32_t n_pkts = count_1bits(keys_map);

    ovs_assert(NETDEV_MAX_BURST >= n_pkts);

    uint32_t hashes[NETDEV_MAX_BURST];

    // 根据mask字段的大小开空间

    const uint32_t bit_count_total = bit_count_u0 + bit_count_u1;

    // 一个batch最大是NETDEV_MAX_BURST

    const uint32_t block_count_required = bit_count_total * NETDEV_MAX_BURST;

    uint64_t *mf_masks = subtable->mf_masks;

    int i;

    // 申请存储一个batch报文信息的数组，存放

    uint64_t *blocks_scratch = get_blocks_scratch(block_count_required); 

    // 获得每个key与当前表的mask“与运算”的结果

    ULLONG_FOR_EACH_1 (i, keys_map) {

            netdev_flow_key_flatten(keys[i],

                                    &subtable->mask, // 该表的掩码信息

                                    mf_masks,  // 由subtable->mask处理后的mask

                                    &blocks_scratch[i * bit_count_total],

                                    bit_count_u0,

                                    bit_count_u1);

    }

    // 算出来每一个key在该subtable里的hash值，该hash值由“mask字节数，key和mask与运算结果”得出

    ULLONG_FOR_EACH_1 (i, keys_map) {

        uint64_t *block_ptr = &blocks_scratch[i * bit_count_total];

        uint32_t hash = hash_add_words64(0, block_ptr, bit_count_total);

        hashes[i] = hash_finish(hash, bit_count_total * 8);

    }

    uint32_t found_map;

    const struct cmap_node *nodes[NETDEV_MAX_BURST];

    // 找到每个key在该subtable里的cmap，并且返回每个key有没有被找到，第i位是1则找到

    found_map = cmap_find_batch(&subtable->rules, keys_map, hashes, nodes);

    ULLONG_FOR_EACH_1 (i, found_map) {

        struct dpcls_rule *rule;

        // 可能不同的rule有相同的hash，看那个是匹配的

        CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) {

            const uint32_t cidx = i * bit_count_total;

            /*rule->mask & keys[i]的值与rule->flow相比较*/

            uint32_t match = netdev_rule_matches_key(rule, bit_count_total,

                                                     &blocks_scratch[cidx]);

            if (OVS_LIKELY(match)) {

                rules[i] = rule;

                subtable->hit_cnt++;

                goto next;

            }

        }

        ULLONG_SET0(found_map, i);  /* Did not match. */

    next:

        ; /* Keep Sparse happy. */

    }

    return found_map;

}

// 这个函数对应dpif-netdev.c里面的dpcls_flow_key_gen_masks()

static inline void

netdev_flow_key_flatten(const struct netdev_flow_key *key,  // 要查找的miss_key

                        const struct netdev_flow_key *mask,

                        const uint64_t *mf_masks,

                        uint64_t *blocks_scratch,

                        const uint32_t u0_count,

                        const uint32_t u1_count)

{

    /* Load mask from subtable, mask with packet mf, popcount to get idx. */

    const uint64_t *pkt_blocks = miniflow_get_values(&key->mf);

    const uint64_t *tbl_blocks = miniflow_get_values(&mask->mf); // 获取miss_key和mask的miniflow

    /* Packet miniflow bits to be masked by pre-calculated mf_masks. */

    const uint64_t pkt_bits_u0 = key->mf.map.bits[0];

    const uint32_t pkt_bits_u0_pop = count_1bits(pkt_bits_u0);

    const uint64_t pkt_bits_u1 = key->mf.map.bits[1];

// 这个函数就是把miss_key与subtable的掩码进行&运算

// 会运算出该mask在意字段结果，放到blocks_scratch里

    netdev_flow_key_flatten_unit(&pkt_blocks[0],   // key-mf的数据段

                                 &tbl_blocks[0],   // mask->mf的数据段

                                 &mf_masks[0],     // mask->mf->bits得来mask

                                 &blocks_scratch[0], // 存放的地址

                                 pkt_bits_u0,      // key->mf里的bits[0]

                                 u0_count);        // mask->mf->bits[0]里1的个数

    netdev_flow_key_flatten_unit(&pkt_blocks[pkt_bits_u0_pop], // 上边bits[0]的已经算过了，从bits[1]开始算

                                 &tbl_blocks[u0_count],

                                 &mf_masks[u0_count],

                                 &blocks_scratch[u0_count],

                                 pkt_bits_u1,

                                 u1_count);

}

static inline void

netdev_flow_key_flatten_unit(const uint64_t *pkt_blocks, // key-mf的数据段

                             const uint64_t *tbl_blocks, // mask->mf里的数据段

                             const uint64_t *mf_masks,   // mask->mf->bits得来mask

                             uint64_t *blocks_scratch,   // 存放到这里

                             const uint64_t pkt_mf_bits, // key->mf里的bits[01]

                             const uint32_t count)       // mask->mf->bits[0]里1的个数

{

// 说一下意思，这个我们流程就是用key和subtable的mask与运算，肯定只需要与运算mask里

// 不为0的字段，其他的mask不关心，然后这个操作就是为了得到key对应字段是key->mf的第几位，

// 比如mask的bits[0]=11111, key的bits[0] = 10100, mask里的第3个1在key里面是第1个

// 这一位与的结果就是tbl_blocks[2]&pkt_blocks[0], 也就是怎么找到key里的下标0

// 就看key当前位之前有几个1就行了。这里这样做的1010111，

// 蓝色1之前有count_1bits(1010111 & 0001111) = 3

//  对上边的mask举个例子 count = 4;

//  mask->mf->bits[0] = 111010 (2进制)

//  mf_masks = [1, 111, 1111, 11111] (2进制);

//  pkt_mf_bits = 010100

//  blocks_scratch = [0,0,0,0,pkt_blocks[1]&tbl_blocks[4],0]

    uint32_t i;

    for (i = 0; i < count; i++) {

        // 拿i=2举例

        uint64_t mf_mask = mf_masks[i];             // mf_mask = 001111

        uint64_t idx_bits = mf_mask & pkt_mf_bits;  // idx_bits = 000100

        const uint32_t pkt_idx = count_1bits(idx_bits); // pkt_idx = 1

        uint64_t pkt_has_mf_bit = (mf_mask + 1) & pkt_mf_bits;  // pkt_has_mf_bit = 010000

        // 是否求掩码：mask当前位对应的key的字段，如果key在当前位是0，下边算掩码就会变成0

        uint64_t no_bit = ((!pkt_has_mf_bit) > 0) - 1; // 2^64 - 1

        // mask里第i个字段与运算key对应的字段

        blocks_scratch[i] = pkt_blocks[pkt_idx] & tbl_blocks[i] & no_bit; //

    }

}

unsigned long

cmap_find_batch(const struct cmap *cmap, unsigned long map,

                uint32_t hashes[], const struct cmap_node *nodes[])

{

    const struct cmap_impl *impl = cmap_get_impl(cmap);

    unsigned long result = map;

    int i;

    // 每一位就是一个包，一字节8个包

    uint32_t h1s[sizeof map * CHAR_BIT];

    const struct cmap_bucket *b1s[sizeof map * CHAR_BIT];

    const struct cmap_bucket *b2s[sizeof map * CHAR_BIT];

    uint32_t c1s[sizeof map * CHAR_BIT];

    // 每个impl里桶的数量为impl->mask+1

    // 为什么mask是桶的个数减1:因为下标从0开始，找下表的时候直接(hash & impl->mask)就行了

    // 至于为什么开两个？因为buckets存放的方法也是一个值对应两个hash

    // 第一次hash1 = rehash(impl->basis, hash), 找buckets[hash1 & impl->mask], 遍历里面CMAP_K个元素

    // 第二次hash2 = other_hash(hash1), 找buckets[hash2 & impl->mask], 遍历里面CMAP_K个元素

    /* Compute hashes and prefetch 1st buckets. */

    ULLONG_FOR_EACH_1(i, map) {

        h1s[i] = rehash(impl, hashes[i]);

        b1s[i] = &impl->buckets[h1s[i] & impl->mask];

        OVS_PREFETCH(b1s[i]);

    }

    /* Lookups, Round 1. Only look up at the first bucket. */

    ULLONG_FOR_EACH_1(i, map) {

        uint32_t c1;

        const struct cmap_bucket *b1 = b1s[i];

        const struct cmap_node *node;

        do {

            c1 = read_even_counter(b1);

            // 找一下这个cmap_bucket里面有没有相同hash的

            node = cmap_find_in_bucket(b1, hashes[i]);

        } while (OVS_UNLIKELY(counter_changed(b1, c1)));

        if (!node) {

            /* Not found (yet); Prefetch the 2nd bucket. */

            b2s[i] = &impl->buckets[other_hash(h1s[i]) & impl->mask];

            OVS_PREFETCH(b2s[i]);

            c1s[i] = c1; /* We may need to check this after Round 2. */

            continue;

        }

        /* Found. */

        ULLONG_SET0(map, i); /* Ignore this on round 2. */

        OVS_PREFETCH(node);

        nodes[i] = node;

    }

    /* Round 2. Look into the 2nd bucket, if needed. */

    ULLONG_FOR_EACH_1(i, map) {

        uint32_t c2;

        const struct cmap_bucket *b2 = b2s[i];

        const struct cmap_node *node;

        do {

            c2 = read_even_counter(b2);

            node = cmap_find_in_bucket(b2, hashes[i]);

        } while (OVS_UNLIKELY(counter_changed(b2, c2)));

        if (!node) {

            // 可能被修改了，

            if (OVS_UNLIKELY(counter_changed(b1s[i], c1s[i]))) {

                node = cmap_find__(b1s[i], b2s[i], hashes[i]);

                if (node) {

                    goto found;

                }

            }

            /* Not found. */

            ULLONG_SET0(result, i); /* Fix the result. */

            continue;

        }

found:

        OVS_PREFETCH(node);

        nodes[i] = node;

    }

    return result;

}

2.3 fast_path_processing()

static inline void

fast_path_processing(struct dp_netdev_pmd_thread *pmd,

                     struct dp_packet_batch *packets_,

                     struct netdev_flow_key **keys,

                     struct dp_packet_flow_map *flow_map,

                     uint8_t *index_map,

                     odp_port_t in_port)

{

    const size_t cnt = dp_packet_batch_size(packets_);

#if !defined(__CHECKER__) && !defined(_WIN32)

    const size_t PKT_ARRAY_SIZE = cnt;

#else

    /* Sparse or MSVC doesn't like variable length array. */

    enum { PKT_ARRAY_SIZE = NETDEV_MAX_BURST };

#endif

    struct dp_packet *packet;

    struct dpcls *cls;

    struct dpcls_rule *rules[PKT_ARRAY_SIZE];

    struct dp_netdev *dp = pmd->dp;

    int upcall_ok_cnt = 0, upcall_fail_cnt = 0;

    int lookup_cnt = 0, add_lookup_cnt;

    bool any_miss;

    for (size_t i = 0; i < cnt; i++) {

        /* Key length is needed in all the cases, hash computed on demand. */

        keys[i]->len = netdev_flow_key_size(miniflow_n_values(&keys[i]->mf));

    }

    /* Get the classifier for the in_port */

    // 找到端口对应的dpcls结构，每个port有自己的dpcls，因为每个port收到的报文会更相似

    cls = dp_netdev_pmd_lookup_dpcls(pmd, in_port);

    if (OVS_LIKELY(cls)) {

        // 调用dpcls_lookup进行匹配

        any_miss = !dpcls_lookup(cls, (const struct netdev_flow_key **)keys,

                                rules, cnt, &lookup_cnt);

    } else {

        any_miss = true;

        memset(rules, 0, sizeof(rules));

    }

    // 如果有miss的，则需要进行openflow流表查询

    if (OVS_UNLIKELY(any_miss) && !fat_rwlock_tryrdlock(&dp->upcall_rwlock)) {

        uint64_t actions_stub[512 / 8], slow_stub[512 / 8];

        struct ofpbuf actions, put_actions;

        ofpbuf_use_stub(&actions, actions_stub, sizeof actions_stub);

        ofpbuf_use_stub(&put_actions, slow_stub, sizeof slow_stub);

        DP_PACKET_BATCH_FOR_EACH (i, packet, packets_) {

            struct dp_netdev_flow *netdev_flow;

            if (OVS_LIKELY(rules[i])) {

                continue;

            }

            // 此时可能已经更新了，在进入upcall之前如果再查一次，如果能够查到，会比upcall消耗的少得多

            netdev_flow = dp_netdev_pmd_lookup_flow(pmd, keys[i],

                                                    &add_lookup_cnt);

            if (netdev_flow) {

                lookup_cnt += add_lookup_cnt;

                rules[i] = &netdev_flow->cr;

                continue;

            }

            // 第一级和第二级流表查找失败后，就要查找第三级流表了，即openflow流表，这也称为upcall调用。

            // 在普通ovs下是通过netlink实现的，在ovs+dpdk下，直接在pmd线程中调用upcall_cb即可。

            // 开始查找openflow流表。如果查找openflow流表成功并需要下发到dpcls时，需要判断是否超出最大流表限制

            int error = handle_packet_upcall(pmd, packet, keys[i],

                                             &actions, &put_actions);

            if (OVS_UNLIKELY(error)) {

                upcall_fail_cnt++;

            } else {

                upcall_ok_cnt++;

            }

        }

        ofpbuf_uninit(&actions);

        ofpbuf_uninit(&put_actions);

        fat_rwlock_unlock(&dp->upcall_rwlock);

    } else if (OVS_UNLIKELY(any_miss)) {

        DP_PACKET_BATCH_FOR_EACH (i, packet, packets_) {

            if (OVS_UNLIKELY(!rules[i])) {

                dp_packet_delete(packet);

                COVERAGE_INC(datapath_drop_lock_error);

                upcall_fail_cnt++;

            }

        }

    }

    DP_PACKET_BATCH_FOR_EACH (i, packet, packets_) {

        struct dp_netdev_flow *flow;

        /* Get the original order of this packet in received batch. */

        int recv_idx = index_map[i];

        uint16_t tcp_flags;

        if (OVS_UNLIKELY(!rules[i])) {

            continue;

        }

        flow = dp_netdev_flow_cast(rules[i]);

        bool hook_cached = false;

        if (pmd->cached_hook && \

                pmd->cached_hook_pmd && \

                pmd->cached_hook->hook_flow_miss) {

            hook_cached = pmd->cached_hook->hook_flow_miss(pmd->cached_hook_pmd, packet, flow);

        }

        if (!hook_cached) {

            bool smc_enable_db;

            atomic_read_relaxed(&pmd->dp->smc_enable_db, &smc_enable_db);

            // 查找到了packet，如果开启了smc，更新smc

            if (smc_enable_db) {

                uint32_t hash =  dp_netdev_flow_hash(&flow->ufid);

                smc_insert(pmd, keys[i], hash);

            }

            // 查到了packet，看是否写会更新上一层cache（EMC）

            if (emc_probabilistic_insert(pmd, keys[i], flow)) {

                if (flow->status == OFFLOAD_NONE) {

                    queue_netdev_flow_put(pmd->dp->dp_flow_offload, \

                            pmd->dp->class, \

                            flow, NULL, DP_NETDEV_FLOW_OFFLOAD_OP_ADD);

                }

            }

        }

        /* Add these packets into the flow map in the same order

         * as received.

         */

        tcp_flags = miniflow_get_tcp_flags(&keys[i]->mf);

        packet_enqueue_to_flow_map(packet, flow, tcp_flags,

                                   flow_map, recv_idx);

    }

    // 更新各个信息

    pmd_perf_update_counter(&pmd->perf_stats, PMD_STAT_MASKED_HIT,

                            cnt - upcall_ok_cnt - upcall_fail_cnt);

    pmd_perf_update_counter(&pmd->perf_stats, PMD_STAT_MASKED_LOOKUP,

                            lookup_cnt);

    pmd_perf_update_counter(&pmd->perf_stats, PMD_STAT_MISS,

                            upcall_ok_cnt);

    pmd_perf_update_counter(&pmd->perf_stats, PMD_STAT_LOST,

                            upcall_fail_cnt);

}

 

2.4 smc更新smc_insert()

static inline void

smc_insert(struct dp_netdev_pmd_thread *pmd,

           const struct netdev_flow_key *key,

           uint32_t hash)

{

    struct smc_cache *smc_cache = &(pmd->flow_cache).smc_cache;

    struct smc_bucket *bucket = &smc_cache->buckets[key->hash & SMC_MASK];

    uint16_t index;

    uint32_t cmap_index;

    int i;

    //布谷鸟算法

    cmap_index = cmap_find_index(&pmd->flow_table, hash);

    index = (cmap_index >= UINT16_MAX) ? UINT16_MAX : (uint16_t)cmap_index;

    /* If the index is larger than SMC can handle (uint16_t), we don't

     * insert */

    if (index == UINT16_MAX) {

        //表明找到了

        return;

    }

    /* If an entry with same signature already exists, update the index */

    uint16_t sig = key->hash >> 16;

    for (i = 0; i < SMC_ENTRY_PER_BUCKET; i++) {

        if (bucket->sig[i] == sig) {

            bucket->flow_idx[i] = index;

            return;

        }

    }

    /* If there is an empty entry, occupy it. */

    for (i = 0; i < SMC_ENTRY_PER_BUCKET; i++) {

        if (bucket->flow_idx[i] == UINT16_MAX) {

            bucket->sig[i] = sig;

            bucket->flow_idx[i] = index;

            return;

        }

    }

    /* Otherwise, pick a random entry. */

    i = random_uint32() % SMC_ENTRY_PER_BUCKET;

    bucket->sig[i] = sig;

    bucket->flow_idx[i] = index;

}

3. upcall到openflow查找，然后更新dpcls

这里就不讲具体代码了，讲一下大概：到openflow查找后会更新dpcls，执行dp_netdev_flow_add() --> dpcls_insert() --> dpcls_find_subtable() --> cmap_insert()

dpcls_find_subtable()：

  找一下是否存在相同mask的subtable，存在返回这个subtable，不存在就创建一个subtable，创建的时候会调用dpcls_create_subtable，里面有个dpcls_subtable_get_best_impl会根据mask的miniflow的bits[0]和bits[1]选择的查找算法。

 

cmap_insert里hash算法用的就是布谷鸟hash，hash两次，插入的核心代码：

static bool

cmap_try_insert(struct cmap_impl *impl, struct cmap_node *node, uint32_t hash)

{

    uint32_t h1 = rehash(impl, hash);

    uint32_t h2 = other_hash(h1);

    // hash两次找到两个桶

    struct cmap_bucket *b1 = &impl->buckets[h1 & impl->mask];

    struct cmap_bucket *b2 = &impl->buckets[h2 & impl->mask];

    // 插入规则：

    // 1.是否有相同hash的node，就插到对应链上

    // 2.没有相同hash，就看有没有空的node

    // 3.都不行就通过bfs，看能否让b1,b2空出来一个，把这个放进去

    // 都不行就插入失败

    return (OVS_UNLIKELY(cmap_insert_dup(node, hash, b1) ||

                         cmap_insert_dup(node, hash, b2)) ||

            OVS_LIKELY(cmap_insert_bucket(node, hash, b1) ||

                       cmap_insert_bucket(node, hash, b2)) ||

            cmap_insert_bfs(impl, node, hash, b1, b2));

}

参考博客：

OVS-DPDK Datapath Classifier ：这个是理论上的流程，看完就知道这个算法流程了

ovs分类器 flow和miniflow ：很重要的结构体miniflow

OVS-DPDK DataPath Classifier反向设计 ：这个有很多详细的解释，但不怎么流畅