/src/openvswitch/lib/dpif-netdev-private-dfc.h

Source (jump to first uncovered line)
/*
 * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2015 Nicira, Inc.
 * Copyright (c) 2019, 2020, 2021 Intel Corporation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef DPIF_NETDEV_PRIVATE_DFC_H
#define DPIF_NETDEV_PRIVATE_DFC_H 1

#include "dpif.h"
#include "dpif-netdev-private-dpcls.h"
#include "dpif-netdev-private-flow.h"

#include <stdbool.h>
#include <stdint.h>

#ifdef  __cplusplus
extern "C" {
#endif

/* EMC cache and SMC cache compose the datapath flow cache (DFC)
 *
 * Exact match cache for frequently used flows
 *
 * The cache uses a 32-bit hash of the packet (which can be the RSS hash) to
 * search its entries for a miniflow that matches exactly the miniflow of the
 * packet. It stores the 'dpcls_rule' (rule) that matches the miniflow.
 *
 * A cache entry holds a reference to its 'dp_netdev_flow'.
 *
 * A miniflow with a given hash can be in one of EM_FLOW_HASH_SEGS different
 * entries. The 32-bit hash is split into EM_FLOW_HASH_SEGS values (each of
 * them is EM_FLOW_HASH_SHIFT bits wide and the remainder is thrown away). Each
 * value is the index of a cache entry where the miniflow could be.
 *
 *
 * Signature match cache (SMC)
 *
 * This cache stores a 16-bit signature for each flow without storing keys, and
 * stores the corresponding 16-bit flow_table index to the 'dp_netdev_flow'.
 * Each flow thus occupies 32bit which is much more memory efficient than EMC.
 * SMC uses a set-associative design that each bucket contains
 * SMC_ENTRY_PER_BUCKET number of entries.
 * Since 16-bit flow_table index is used, if there are more than 2^16
 * dp_netdev_flow, SMC will miss them that cannot be indexed by a 16-bit value.
 *
 *
 * Thread-safety
 * =============
 *
 * Each pmd_thread has its own private exact match cache and signature match
 * cache.
 * If dp_netdev_input is not called from a pmd thread, a mutex is used.
 */

#define EM_FLOW_HASH_SHIFT 13
#define EM_FLOW_HASH_ENTRIES (1u << EM_FLOW_HASH_SHIFT)
#define EM_FLOW_HASH_MASK (EM_FLOW_HASH_ENTRIES - 1)
#define EM_FLOW_HASH_SEGS 2

/* SMC uses a set-associative design. A bucket contains a set of entries that
 * a flow item can occupy. For now, it uses one hash function rather than two
 * as for the EMC design. */
#define SMC_ENTRY_PER_BUCKET 4
#define SMC_ENTRIES (1u << 20)
#define SMC_BUCKET_CNT (SMC_ENTRIES / SMC_ENTRY_PER_BUCKET)
#define SMC_MASK (SMC_BUCKET_CNT - 1)

/* Default EMC insert probability is 1 / DEFAULT_EM_FLOW_INSERT_INV_PROB */
#define DEFAULT_EM_FLOW_INSERT_INV_PROB 100
#define DEFAULT_EM_FLOW_INSERT_MIN (UINT32_MAX /                     \
                                    DEFAULT_EM_FLOW_INSERT_INV_PROB)

/* Forward declaration for SMC function prototype that requires access to
 * 'struct dp_netdev_pmd_thread'. */
struct dp_netdev_pmd_thread;

/* Forward declaration for EMC and SMC batch insert function prototypes that
 * require access to 'struct dpcls_rule'. */
struct dpcls_rule;

struct emc_entry {
    struct dp_netdev_flow *flow;
    struct netdev_flow_key key;   /* key.hash used for emc hash value. */
};

struct emc_cache {
    struct emc_entry entries[EM_FLOW_HASH_ENTRIES];
    int sweep_idx;                /* For emc_cache_slow_sweep(). */
};

struct smc_bucket {
    uint16_t sig[SMC_ENTRY_PER_BUCKET];
    uint16_t flow_idx[SMC_ENTRY_PER_BUCKET];
};

/* Signature match cache, differentiate from EMC cache */
struct smc_cache {
    struct smc_bucket buckets[SMC_BUCKET_CNT];
};

struct dfc_cache {
    struct emc_cache emc_cache;
    struct smc_cache smc_cache;
};

/* Iterate in the exact match cache through every entry that might contain a
 * miniflow with hash 'HASH'. */
#define EMC_FOR_EACH_POS_WITH_HASH(EMC, CURRENT_ENTRY, HASH)                 \
    for (uint32_t i__ = 0, srch_hash__ = (HASH);                             \
         (CURRENT_ENTRY) = &(EMC)->entries[srch_hash__ & EM_FLOW_HASH_MASK], \
         i__ < EM_FLOW_HASH_SEGS;                                            \
         i__++, srch_hash__ >>= EM_FLOW_HASH_SHIFT)

void dfc_cache_init(struct dfc_cache *flow_cache);

void dfc_cache_uninit(struct dfc_cache *flow_cache);

/* Check and clear dead flow references slowly (one entry at each
 * invocation).  */
void emc_cache_slow_sweep(struct emc_cache *flow_cache);

static inline bool
emc_entry_alive(struct emc_entry *ce)
{
    return ce->flow && !ce->flow->dead;
}

/* Used to compare 'netdev_flow_key' in the exact match cache to a miniflow.
 * The maps are compared bitwise, so both 'key->mf' and 'mf' must have been
 * generated by miniflow_extract. */
static inline bool
emc_flow_key_equal_mf(const struct netdev_flow_key *key,
                         const struct miniflow *mf)
{
    return !memcmp(&key->mf, mf, key->len);
}

static inline struct dp_netdev_flow *
emc_lookup(struct emc_cache *cache, const struct netdev_flow_key *key)
{
    struct emc_entry *current_entry;

    EMC_FOR_EACH_POS_WITH_HASH (cache, current_entry, key->hash) {
        if (current_entry->key.hash == key->hash
            && emc_entry_alive(current_entry)
            && emc_flow_key_equal_mf(&current_entry->key, &key->mf)) {

            /* We found the entry with the 'key->mf' miniflow */
            return current_entry->flow;
        }
    }

    return NULL;
}

/* Insert a batch of keys/flows into the EMC and SMC caches. */
void
emc_probabilistic_insert_batch(struct dp_netdev_pmd_thread *pmd,
                               const struct netdev_flow_key *keys,
                               struct dpcls_rule **rules,
                               uint32_t emc_insert_mask);

void
smc_insert_batch(struct dp_netdev_pmd_thread *pmd,
                               const struct netdev_flow_key *keys,
                               struct dpcls_rule **rules,
                               uint32_t smc_insert_mask);

struct dp_netdev_flow *
smc_lookup_single(struct dp_netdev_pmd_thread *pmd,
                  struct dp_packet *packet,
                  struct netdev_flow_key *key);

#ifdef  __cplusplus
}
#endif

#endif /* dpif-netdev-private-dfc.h */

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2015 Nicira, Inc.
3		* Copyright (c) 2019, 2020, 2021 Intel Corporation.
4		*
5		* Licensed under the Apache License, Version 2.0 (the "License");
6		* you may not use this file except in compliance with the License.
7		* You may obtain a copy of the License at:
8		*
9		* http://www.apache.org/licenses/LICENSE-2.0
10		*
11		* Unless required by applicable law or agreed to in writing, software
12		* distributed under the License is distributed on an "AS IS" BASIS,
13		* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14		* See the License for the specific language governing permissions and
15		* limitations under the License.
16		*/
17
18		#ifndef DPIF_NETDEV_PRIVATE_DFC_H
19		#define DPIF_NETDEV_PRIVATE_DFC_H 1
20
21		#include "dpif.h"
22		#include "dpif-netdev-private-dpcls.h"
23		#include "dpif-netdev-private-flow.h"
24
25		#include <stdbool.h>
26		#include <stdint.h>
27
28		#ifdef __cplusplus
29		extern "C" {
30		#endif
31
32		/* EMC cache and SMC cache compose the datapath flow cache (DFC)
33		*
34		* Exact match cache for frequently used flows
35		*
36		* The cache uses a 32-bit hash of the packet (which can be the RSS hash) to
37		* search its entries for a miniflow that matches exactly the miniflow of the
38		* packet. It stores the 'dpcls_rule' (rule) that matches the miniflow.
39		*
40		* A cache entry holds a reference to its 'dp_netdev_flow'.
41		*
42		* A miniflow with a given hash can be in one of EM_FLOW_HASH_SEGS different
43		* entries. The 32-bit hash is split into EM_FLOW_HASH_SEGS values (each of
44		* them is EM_FLOW_HASH_SHIFT bits wide and the remainder is thrown away). Each
45		* value is the index of a cache entry where the miniflow could be.
46		*
47		*
48		* Signature match cache (SMC)
49		*
50		* This cache stores a 16-bit signature for each flow without storing keys, and
51		* stores the corresponding 16-bit flow_table index to the 'dp_netdev_flow'.
52		* Each flow thus occupies 32bit which is much more memory efficient than EMC.
53		* SMC uses a set-associative design that each bucket contains
54		* SMC_ENTRY_PER_BUCKET number of entries.
55		* Since 16-bit flow_table index is used, if there are more than 2^16
56		* dp_netdev_flow, SMC will miss them that cannot be indexed by a 16-bit value.
57		*
58		*
59		* Thread-safety
60		* =============
61		*
62		* Each pmd_thread has its own private exact match cache and signature match
63		* cache.
64		* If dp_netdev_input is not called from a pmd thread, a mutex is used.
65		*/
66
67	0	#define EM_FLOW_HASH_SHIFT 13
68	0	#define EM_FLOW_HASH_ENTRIES (1u << EM_FLOW_HASH_SHIFT)
69	0	#define EM_FLOW_HASH_MASK (EM_FLOW_HASH_ENTRIES - 1)
70	0	#define EM_FLOW_HASH_SEGS 2
71
72		/* SMC uses a set-associative design. A bucket contains a set of entries that
73		* a flow item can occupy. For now, it uses one hash function rather than two
74		* as for the EMC design. */
75	0	#define SMC_ENTRY_PER_BUCKET 4
76	0	#define SMC_ENTRIES (1u << 20)
77	0	#define SMC_BUCKET_CNT (SMC_ENTRIES / SMC_ENTRY_PER_BUCKET)
78	0	#define SMC_MASK (SMC_BUCKET_CNT - 1)
79
80		/* Default EMC insert probability is 1 / DEFAULT_EM_FLOW_INSERT_INV_PROB */
81	0	#define DEFAULT_EM_FLOW_INSERT_INV_PROB 100
82	0	#define DEFAULT_EM_FLOW_INSERT_MIN (UINT32_MAX / \
83	0	DEFAULT_EM_FLOW_INSERT_INV_PROB)
84
85		/* Forward declaration for SMC function prototype that requires access to
86		* 'struct dp_netdev_pmd_thread'. */
87		struct dp_netdev_pmd_thread;
88
89		/* Forward declaration for EMC and SMC batch insert function prototypes that
90		* require access to 'struct dpcls_rule'. */
91		struct dpcls_rule;
92
93		struct emc_entry {
94		struct dp_netdev_flow *flow;
95		struct netdev_flow_key key; /* key.hash used for emc hash value. */
96		};
97
98		struct emc_cache {
99		struct emc_entry entries[EM_FLOW_HASH_ENTRIES];
100		int sweep_idx; /* For emc_cache_slow_sweep(). */
101		};
102
103		struct smc_bucket {
104		uint16_t sig[SMC_ENTRY_PER_BUCKET];
105		uint16_t flow_idx[SMC_ENTRY_PER_BUCKET];
106		};
107
108		/* Signature match cache, differentiate from EMC cache */
109		struct smc_cache {
110		struct smc_bucket buckets[SMC_BUCKET_CNT];
111		};
112
113		struct dfc_cache {
114		struct emc_cache emc_cache;
115		struct smc_cache smc_cache;
116		};
117
118		/* Iterate in the exact match cache through every entry that might contain a
119		* miniflow with hash 'HASH'. */
120		#define EMC_FOR_EACH_POS_WITH_HASH(EMC, CURRENT_ENTRY, HASH) \
121	0	for (uint32_t i__ = 0, srch_hash__ = (HASH); \
122	0	(CURRENT_ENTRY) = &(EMC)->entries[srch_hash__ & EM_FLOW_HASH_MASK], \
123	0	i__ < EM_FLOW_HASH_SEGS; \
124	0	i__++, srch_hash__ >>= EM_FLOW_HASH_SHIFT)
125
126		void dfc_cache_init(struct dfc_cache *flow_cache);
127
128		void dfc_cache_uninit(struct dfc_cache *flow_cache);
129
130		/* Check and clear dead flow references slowly (one entry at each
131		* invocation). */
132		void emc_cache_slow_sweep(struct emc_cache *flow_cache);
133
134		static inline bool
135		emc_entry_alive(struct emc_entry *ce)
136	0	{
137	0	return ce->flow && !ce->flow->dead;
138	0	} Unexecuted instantiation: dpif-netdev.c:emc_entry_alive Unexecuted instantiation: dpif-netdev-private-dfc.c:emc_entry_alive Unexecuted instantiation: dpif-netdev-private-dpif.c:emc_entry_alive Unexecuted instantiation: dpif-netdev-private-extract.c:emc_entry_alive Unexecuted instantiation: dpif-netdev-extract-study.c:emc_entry_alive Unexecuted instantiation: dpif-netdev-lookup.c:emc_entry_alive Unexecuted instantiation: dpif-netdev-lookup-autovalidator.c:emc_entry_alive Unexecuted instantiation: dpif-netdev-lookup-generic.c:emc_entry_alive
139
140		/* Used to compare 'netdev_flow_key' in the exact match cache to a miniflow.
141		* The maps are compared bitwise, so both 'key->mf' and 'mf' must have been
142		* generated by miniflow_extract. */
143		static inline bool
144		emc_flow_key_equal_mf(const struct netdev_flow_key *key,
145		const struct miniflow *mf)
146	0	{
147	0	return !memcmp(&key->mf, mf, key->len);
148	0	} Unexecuted instantiation: dpif-netdev.c:emc_flow_key_equal_mf Unexecuted instantiation: dpif-netdev-private-dfc.c:emc_flow_key_equal_mf Unexecuted instantiation: dpif-netdev-private-dpif.c:emc_flow_key_equal_mf Unexecuted instantiation: dpif-netdev-private-extract.c:emc_flow_key_equal_mf Unexecuted instantiation: dpif-netdev-extract-study.c:emc_flow_key_equal_mf Unexecuted instantiation: dpif-netdev-lookup.c:emc_flow_key_equal_mf Unexecuted instantiation: dpif-netdev-lookup-autovalidator.c:emc_flow_key_equal_mf Unexecuted instantiation: dpif-netdev-lookup-generic.c:emc_flow_key_equal_mf
149
150		static inline struct dp_netdev_flow *
151		emc_lookup(struct emc_cache cache, const struct netdev_flow_key key)
152	0	{
153	0	struct emc_entry *current_entry;
154
155	0	EMC_FOR_EACH_POS_WITH_HASH (cache, current_entry, key->hash) {
156	0	if (current_entry->key.hash == key->hash
157	0	&& emc_entry_alive(current_entry)
158	0	&& emc_flow_key_equal_mf(&current_entry->key, &key->mf)) {
159
160		/* We found the entry with the 'key->mf' miniflow */
161	0	return current_entry->flow;
162	0	}
163	0	}
164
165	0	return NULL;
166	0	} Unexecuted instantiation: dpif-netdev.c:emc_lookup Unexecuted instantiation: dpif-netdev-private-dfc.c:emc_lookup Unexecuted instantiation: dpif-netdev-private-dpif.c:emc_lookup Unexecuted instantiation: dpif-netdev-private-extract.c:emc_lookup Unexecuted instantiation: dpif-netdev-extract-study.c:emc_lookup Unexecuted instantiation: dpif-netdev-lookup.c:emc_lookup Unexecuted instantiation: dpif-netdev-lookup-autovalidator.c:emc_lookup Unexecuted instantiation: dpif-netdev-lookup-generic.c:emc_lookup
167
168		/* Insert a batch of keys/flows into the EMC and SMC caches. */
169		void
170		emc_probabilistic_insert_batch(struct dp_netdev_pmd_thread *pmd,
171		const struct netdev_flow_key *keys,
172		struct dpcls_rule **rules,
173		uint32_t emc_insert_mask);
174
175		void
176		smc_insert_batch(struct dp_netdev_pmd_thread *pmd,
177		const struct netdev_flow_key *keys,
178		struct dpcls_rule **rules,
179		uint32_t smc_insert_mask);
180
181		struct dp_netdev_flow *
182		smc_lookup_single(struct dp_netdev_pmd_thread *pmd,
183		struct dp_packet *packet,
184		struct netdev_flow_key *key);
185
186		#ifdef __cplusplus
187		}
188		#endif
189
190		#endif /* dpif-netdev-private-dfc.h */

Coverage Report

Created: 2025-07-12 06:35