[ovs-dev] [PATCH 7/7] lib/dpif-netdev: Integrate megaflow classifier.
Jarno Rajahalme
jrajahalme at nicira.com
Wed Oct 1 23:02:37 UTC 2014
flow inserts and removals are simplified:
- No need for classifier internal mutex, as dpif-netdev already has a
'flow_mutex'
- Number of memory allocations/frees can be halved
Lookup code path is a bit more effcient as well, as we can rely on
netdev_flow_key always having inline data.
Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
lib/classifier.c | 85 -------
lib/classifier.h | 3 -
lib/dpif-netdev.c | 657 ++++++++++++++++++++++++++++++++++++++++-------------
3 files changed, 502 insertions(+), 243 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index ee737a7..9691cd5 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -958,91 +958,6 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow,
return best ? best->cls_rule : NULL;
}
-/* Returns true if 'target' satisifies 'match', that is, if each bit for which
- * 'match' specifies a particular value has the correct value in 'target'.
- *
- * 'flow' and 'mask' have the same mask! */
-static bool
-miniflow_and_mask_matches_miniflow(const struct miniflow *flow,
- const struct minimask *mask,
- const struct miniflow *target)
-{
- const uint32_t *flowp = miniflow_get_u32_values(flow);
- const uint32_t *maskp = miniflow_get_u32_values(&mask->masks);
- uint32_t target_u32;
-
- MINIFLOW_FOR_EACH_IN_MAP(target_u32, target, mask->masks.map) {
- if ((*flowp++ ^ target_u32) & *maskp++) {
- return false;
- }
- }
-
- return true;
-}
-
-static inline struct cls_match *
-find_match_miniflow(const struct cls_subtable *subtable,
- const struct miniflow *flow,
- uint32_t hash)
-{
- struct cls_match *rule;
-
- CMAP_FOR_EACH_WITH_HASH (rule, cmap_node, hash, &subtable->rules) {
- if (miniflow_and_mask_matches_miniflow(&rule->flow, &subtable->mask,
- flow)) {
- return rule;
- }
- }
-
- return NULL;
-}
-
-/* For each miniflow in 'flows' performs a classifier lookup writing the result
- * into the corresponding slot in 'rules'. If a particular entry in 'flows' is
- * NULL it is skipped.
- *
- * This function is optimized for use in the userspace datapath and therefore
- * does not implement a lot of features available in the standard
- * classifier_lookup() function. Specifically, it does not implement
- * priorities, instead returning any rule which matches the flow.
- *
- * Returns true if all flows found a corresponding rule. */
-bool
-classifier_lookup_miniflow_batch(const struct classifier *cls,
- const struct miniflow **flows,
- struct cls_rule **rules, size_t len)
-{
- struct cls_subtable *subtable;
- size_t i, begin = 0;
-
- memset(rules, 0, len * sizeof *rules);
- PVECTOR_FOR_EACH (subtable, &cls->subtables) {
- for (i = begin; i < len; i++) {
- struct cls_match *match;
- uint32_t hash;
-
- if (OVS_UNLIKELY(rules[i] || !flows[i])) {
- continue;
- }
-
- hash = miniflow_hash_in_minimask(flows[i], &subtable->mask, 0);
- match = find_match_miniflow(subtable, flows[i], hash);
- if (OVS_UNLIKELY(match)) {
- rules[i] = match->cls_rule;
- }
- }
-
- while (begin < len && (rules[begin] || !flows[begin])) {
- begin++;
- }
- if (begin >= len) {
- return true;
- }
- }
-
- return false;
-}
-
/* Finds and returns a rule in 'cls' with exactly the same priority and
* matching criteria as 'target'. Returns a null pointer if 'cls' doesn't
* contain an exact match. */
diff --git a/lib/classifier.h b/lib/classifier.h
index d6ab144..44cdc86 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -295,9 +295,6 @@ void classifier_remove(struct classifier *, struct cls_rule *);
struct cls_rule *classifier_lookup(const struct classifier *,
const struct flow *,
struct flow_wildcards *);
-bool classifier_lookup_miniflow_batch(const struct classifier *cls,
- const struct miniflow **flows,
- struct cls_rule **rules, size_t len);
bool classifier_rule_overlaps(const struct classifier *,
const struct cls_rule *);
diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index 6b8201b..b4686fc 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -31,7 +31,6 @@
#include <sys/stat.h>
#include <unistd.h>
-#include "classifier.h"
#include "cmap.h"
#include "csum.h"
#include "dpif.h"
@@ -43,6 +42,7 @@
#include "cmap.h"
#include "latch.h"
#include "list.h"
+#include "match.h"
#include "meta-flow.h"
#include "netdev.h"
#include "netdev-dpdk.h"
@@ -57,6 +57,7 @@
#include "packet-dpif.h"
#include "packets.h"
#include "poll-loop.h"
+#include "pvector.h"
#include "random.h"
#include "seq.h"
#include "shash.h"
@@ -68,9 +69,6 @@
VLOG_DEFINE_THIS_MODULE(dpif_netdev);
-/* By default, choose a priority in the middle. */
-#define NETDEV_RULE_PRIORITY 0x8000
-
#define FLOW_DUMP_MAX_BATCH 50
/* Use per thread recirc_depth to prevent recirculation loop. */
#define MAX_RECIRC_DEPTH 5
@@ -98,7 +96,9 @@ static struct vlog_rate_limit upcall_rl = VLOG_RATE_LIMIT_INIT(600, 600);
- FLOW_U32_SIZE(metadata) \
)
struct netdev_flow_key {
- struct miniflow flow;
+ uint32_t hash; /* hash function differs for different users. */
+ uint32_t len;
+ struct miniflow mf;
uint32_t buf[NETDEV_KEY_BUF_SIZE_U32];
};
@@ -106,7 +106,7 @@ struct netdev_flow_key {
*
* 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 'cls_rule'(rule) that matches the miniflow.
+ * packet. It stores the 'dpcls_rule' (rule) that matches the miniflow.
*
* A cache entry holds a reference to its 'dp_netdev_flow'.
*
@@ -129,10 +129,8 @@ struct netdev_flow_key {
#define EM_FLOW_HASH_SEGS 2
struct emc_entry {
- uint32_t hash;
- uint32_t mf_len;
- struct netdev_flow_key mf;
struct dp_netdev_flow *flow;
+ struct netdev_flow_key key; /* key.hash used for emc hash value. */
};
struct emc_cache {
@@ -146,7 +144,32 @@ struct emc_cache {
(CURRENT_ENTRY) = &(EMC)->entries[srch_hash__ & EM_FLOW_HASH_MASK], \
i__ < EM_FLOW_HASH_SEGS; \
i__++, srch_hash__ >>= EM_FLOW_HASH_SHIFT)
+
+/* Simple non-wildcarding single-priority classifier. */
+struct dpcls {
+ struct cmap subtables_map;
+ struct pvector subtables;
+};
+
+/* A rule to be inserted to the classifier.
+ * 'flow' and 'mask' point to classifier managed memory. */
+struct dpcls_rule {
+ struct cmap_node cmap_node; /* Within struct dpcls_subtable 'rules'. */
+ struct netdev_flow_key *mask; /* subtable's mask */
+ struct netdev_flow_key flow; /* Matching rule. Mask is in the subtable. */
+ /* 'flow' must be the last field. */
+};
+
+static void dpcls_init(struct dpcls *);
+static void dpcls_destroy(struct dpcls *);
+static void dpcls_insert(struct dpcls *, struct dpcls_rule *,
+ const struct netdev_flow_key *mask);
+static void dpcls_remove(struct dpcls *, struct dpcls_rule *);
+static bool dpcls_lookup(const struct dpcls *cls,
+ const struct netdev_flow_key keys[],
+ struct dpcls_rule **rules, size_t cnt);
+
/* Datapath based on the network device interface from netdev.h.
*
*
@@ -175,7 +198,7 @@ struct dp_netdev {
* changes to 'cls' must be made while still holding the 'flow_mutex'.
*/
struct ovs_mutex flow_mutex;
- struct classifier cls;
+ struct dpcls cls;
struct cmap flow_table OVS_GUARDED; /* Flow table. */
/* Statistics.
@@ -243,6 +266,7 @@ struct dp_netdev_port {
char *type; /* Port type as requested by user. */
};
+
/* A flow in dp_netdev's 'flow_table'.
*
*
@@ -282,13 +306,11 @@ struct dp_netdev_port {
*/
struct dp_netdev_flow {
bool dead;
- /* Packet classification. */
- const struct cls_rule cr; /* In owning dp_netdev's 'cls'. */
/* Hash table index by unmasked flow. */
- const struct cmap_node node; /* In owning dp_netdev's 'flow_table'. */
- const struct flow flow; /* The flow that created this entry. */
-
+ const struct cmap_node node; /* In owning dp_netdev's 'flow_table'. */
+ const struct netdev_flow_key key; /* Unmasked flow that created this
+ * entry. */
/* Number of references.
* The classifier owns one reference.
* Any thread trying to keep a rule from being freed should hold its own
@@ -302,6 +324,10 @@ struct dp_netdev_flow {
/* Actions. */
OVSRCU_TYPE(struct dp_netdev_actions *) actions;
+
+ /* Packet classification. */
+ struct dpcls_rule cr; /* In owning dp_netdev's 'cls'. */
+ /* 'cr' must be the last member. */
};
static void dp_netdev_flow_unref(struct dp_netdev_flow *);
@@ -417,10 +443,10 @@ emc_cache_init(struct emc_cache *flow_cache)
for (i = 0; i < ARRAY_SIZE(flow_cache->entries); i++) {
flow_cache->entries[i].flow = NULL;
- flow_cache->entries[i].hash = 0;
- flow_cache->entries[i].mf_len = 0;
- miniflow_initialize(&flow_cache->entries[i].mf.flow,
- flow_cache->entries[i].mf.buf);
+ flow_cache->entries[i].key.hash = 0;
+ flow_cache->entries[i].key.len = 0;
+ miniflow_initialize(&flow_cache->entries[i].key.mf,
+ flow_cache->entries[i].key.buf);
}
}
@@ -557,7 +583,7 @@ create_dp_netdev(const char *name, const struct dpif_class *class,
atomic_flag_clear(&dp->destroyed);
ovs_mutex_init(&dp->flow_mutex);
- classifier_init(&dp->cls, NULL);
+ dpcls_init(&dp->cls);
cmap_init(&dp->flow_table);
ovsthread_stats_init(&dp->stats);
@@ -647,7 +673,7 @@ dp_netdev_free(struct dp_netdev *dp)
}
ovsthread_stats_destroy(&dp->stats);
- classifier_destroy(&dp->cls);
+ dpcls_destroy(&dp->cls);
cmap_destroy(&dp->flow_table);
ovs_mutex_destroy(&dp->flow_mutex);
seq_destroy(dp->port_seq);
@@ -1084,7 +1110,6 @@ dp_netdev_flow_free(struct dp_netdev_flow *flow)
}
ovsthread_stats_destroy(&flow->stats);
- cls_rule_destroy(CONST_CAST(struct cls_rule *, &flow->cr));
dp_netdev_actions_free(dp_netdev_flow_get_actions(flow));
free(flow);
}
@@ -1100,11 +1125,10 @@ static void
dp_netdev_remove_flow(struct dp_netdev *dp, struct dp_netdev_flow *flow)
OVS_REQUIRES(dp->flow_mutex)
{
- struct cls_rule *cr = CONST_CAST(struct cls_rule *, &flow->cr);
struct cmap_node *node = CONST_CAST(struct cmap_node *, &flow->node);
- classifier_remove(&dp->cls, cr);
- cmap_remove(&dp->flow_table, node, flow_hash(&flow->flow, 0));
+ dpcls_remove(&dp->cls, &flow->cr);
+ cmap_remove(&dp->flow_table, node, flow->key.hash);
flow->dead = true;
dp_netdev_flow_unref(flow);
@@ -1208,7 +1232,7 @@ dpif_netdev_port_poll_wait(const struct dpif *dpif_)
}
static struct dp_netdev_flow *
-dp_netdev_flow_cast(const struct cls_rule *cr)
+dp_netdev_flow_cast(const struct dpcls_rule *cr)
{
return cr ? CONTAINER_OF(cr, struct dp_netdev_flow, cr) : NULL;
}
@@ -1236,12 +1260,15 @@ static bool dp_netdev_flow_ref(struct dp_netdev_flow *flow)
*/
BUILD_ASSERT_DECL(offsetof(struct miniflow, inline_values)
== sizeof(uint64_t));
-BUILD_ASSERT_DECL(offsetof(struct netdev_flow_key, flow) == 0);
static inline struct netdev_flow_key *
-miniflow_to_netdev_flow_key(const struct miniflow *mf)
+miniflow_to_netdev_flow_key(const struct miniflow *miniflow)
{
- return (struct netdev_flow_key *) CONST_CAST(struct miniflow *, mf);
+ struct netdev_flow_key *key;
+
+ INIT_CONTAINER(key, miniflow, mf);
+
+ return key;
}
/* Given the number of bits set in the miniflow map, returns the size of the
@@ -1249,25 +1276,144 @@ miniflow_to_netdev_flow_key(const struct miniflow *mf)
static inline uint32_t
netdev_flow_key_size(uint32_t flow_u32s)
{
- return MINIFLOW_VALUES_SIZE(flow_u32s)
- + offsetof(struct miniflow, inline_values);
+ return offsetof(struct netdev_flow_key, mf.inline_values) +
+ MINIFLOW_VALUES_SIZE(flow_u32s);
}
-/* Used to compare 'netdev_flow_key's (miniflows) in the exact match cache. */
static inline bool
netdev_flow_key_equal(const struct netdev_flow_key *a,
- const struct netdev_flow_key *b,
- uint32_t size)
+ const struct netdev_flow_key *b)
+{
+ /* 'b's size and hash may be not set yet. */
+ return !memcmp(a, b, a->len);
+}
+
+/* Used to compare 'netdev_flow_key' in the exact match cache to a miniflow.
+ * The maps are compared bitwise, so both 'key->mf' 'mf' must have been
+ * generated by miniflow_extract. */
+static inline bool
+netdev_flow_key_equal_mf(const struct netdev_flow_key *key,
+ const struct miniflow *mf)
{
- return !memcmp(a, b, size);
+ return !memcmp(&key->mf, mf,
+ key->len - offsetof(struct netdev_flow_key, mf));
}
static inline void
netdev_flow_key_clone(struct netdev_flow_key *dst,
- const struct netdev_flow_key *src,
- uint32_t size)
+ const struct netdev_flow_key *src)
+{
+ memcpy(dst, src, src->len);
+}
+
+/* Returns a hash value for 'key'. 'key's len must be set.
+ * This hash is used for unmasked flow key. */
+static inline uint32_t
+netdev_flow_key_hash(const struct netdev_flow_key *key)
+{
+ return hash_words((const uint32_t *)&key->mf,
+ (key->len - offsetof(struct netdev_flow_key, mf)) / 4,
+ 0);
+}
+
+static void
+netdev_flow_key_from_flow(struct netdev_flow_key *dst,
+ const struct flow *src)
{
- memcpy(dst, src, size);
+ miniflow_initialize(&dst->mf, dst->buf);
+ miniflow_extract_from_flow(&dst->mf, src);
+ dst->len = netdev_flow_key_size(count_1bits(dst->mf.map));
+ dst->hash = netdev_flow_key_hash(dst);
+}
+
+/* Initialize a netdev_flow_key 'mask' from 'key' and 'wc'. */
+static inline void
+netdev_flow_mask_init(struct netdev_flow_key *mask,
+ const struct netdev_flow_key *key,
+ const struct flow_wildcards *wc)
+{
+ const uint32_t *mask_u32 = (const uint32_t *) &wc->masks;
+ uint32_t *dst = mask->mf.inline_values;
+ uint64_t map, mask_map = 0;
+ uint32_t hash = 0;
+ int n;
+
+ /* Also check fields that may have been compressed by the
+ * miniflow_extract(). */
+ map = (wc->masks.tunnel.ip_dst) ? MINIFLOW_MAP(tunnel) : 0;
+ map |= MINIFLOW_MAP(skb_priority) | MINIFLOW_MAP(pkt_mark)
+ | MINIFLOW_MAP(recirc_id) | MINIFLOW_MAP(dp_hash);
+ map |= key->mf.map;
+
+ while (map) {
+ uint64_t rm1bit = rightmost_1bit(map);
+ int i = raw_ctz(map);
+
+ if (mask_u32[i]) {
+ mask_map |= rm1bit;
+ *dst++ = mask_u32[i];
+ hash = hash_add(hash, mask_u32[i]);
+ }
+ map -= rm1bit;
+ }
+
+ mask->mf.values_inline = true;
+ mask->mf.map = mask_map;
+
+ hash = hash_add(hash, mask_map);
+ hash = hash_add(hash, mask_map >> 32);
+
+ n = dst - mask->mf.inline_values;
+
+ mask->hash = hash_finish(hash, n * 4);
+ mask->len = netdev_flow_key_size(n);
+}
+
+/* Iterate through all netdev_flow_key u32 values specified by 'MAP' */
+#define NETDEV_FLOW_KEY_FOR_EACH_IN_MAP(VALUE, KEY, MAP) \
+ const uint32_t *fp_ = (KEY)->mf.inline_values; \
+ uint64_t rm1bit_, fmap_, map_; \
+ for (fmap_ = (KEY)->mf.map, map_ = (MAP), rm1bit_ = rightmost_1bit(MAP); \
+ mf_get_next_in_map(&fmap_, rm1bit_, &fp_, &(VALUE)); \
+ map_ -= rm1bit_, rm1bit_ = rightmost_1bit(map_))
+
+/* Initializes 'dst' as a copy of 'src' masked with 'mask'. */
+static inline void
+netdev_flow_key_init_masked(struct netdev_flow_key *dst,
+ const struct netdev_flow_key *key,
+ const struct netdev_flow_key *mask)
+{
+ uint32_t *dst_u32 = dst->mf.inline_values;
+ const uint32_t *mask_u32 = mask->mf.inline_values;
+ uint32_t hash = 0;
+ uint32_t value;
+
+ dst->len = mask->len;
+ dst->mf.values_inline = true;
+ dst->mf.map = mask->mf.map;
+
+ NETDEV_FLOW_KEY_FOR_EACH_IN_MAP(value, key, mask->mf.map) {
+ *dst_u32 = value & *mask_u32++;
+ hash = hash_add(hash, *dst_u32++);
+ }
+ dst->hash = hash_finish(hash, (dst_u32 - dst->mf.inline_values) * 4);
+}
+
+/* Returns a hash value for the bits of 'key' where there are 1-bits in
+ * 'mask'. */
+static inline uint32_t
+netdev_flow_key_hash_in_mask(const struct netdev_flow_key *key,
+ const struct netdev_flow_key *mask)
+{
+ const uint32_t *p = mask->mf.inline_values;
+ uint32_t hash = 0;
+ uint32_t key_u32;
+
+ NETDEV_FLOW_KEY_FOR_EACH_IN_MAP(key_u32, key, mask->mf.map) {
+ hash = hash_add(hash, key_u32 & *p++);
+ }
+
+ return hash_finish(hash, (p - mask->mf.inline_values) * 4);
}
static inline bool
@@ -1287,7 +1433,7 @@ emc_clear_entry(struct emc_entry *ce)
static inline void
emc_change_entry(struct emc_entry *ce, struct dp_netdev_flow *flow,
- const struct netdev_flow_key *mf, uint32_t hash)
+ const struct netdev_flow_key *key)
{
if (ce->flow != flow) {
if (ce->flow) {
@@ -1300,30 +1446,22 @@ emc_change_entry(struct emc_entry *ce, struct dp_netdev_flow *flow,
ce->flow = NULL;
}
}
- if (mf) {
- uint32_t mf_len = netdev_flow_key_size(count_1bits(mf->flow.map));
-
- netdev_flow_key_clone(&ce->mf, mf, mf_len);
- ce->hash = hash;
- ce->mf_len = mf_len;
+ if (key) {
+ netdev_flow_key_clone(&ce->key, key);
}
}
static inline void
-emc_insert(struct emc_cache *cache, const struct miniflow *mf, uint32_t hash,
+emc_insert(struct emc_cache *cache, const struct netdev_flow_key *key,
struct dp_netdev_flow *flow)
{
struct emc_entry *to_be_replaced = NULL;
struct emc_entry *current_entry;
- EMC_FOR_EACH_POS_WITH_HASH(cache, current_entry, hash) {
- if (current_entry->hash == hash
- && netdev_flow_key_equal(¤t_entry->mf,
- miniflow_to_netdev_flow_key(mf),
- current_entry->mf_len)) {
-
+ EMC_FOR_EACH_POS_WITH_HASH(cache, current_entry, key->hash) {
+ if (netdev_flow_key_equal(¤t_entry->key, key)) {
/* We found the entry with the 'mf' miniflow */
- emc_change_entry(current_entry, flow, NULL, 0);
+ emc_change_entry(current_entry, flow, NULL);
return;
}
@@ -1332,29 +1470,27 @@ emc_insert(struct emc_cache *cache, const struct miniflow *mf, uint32_t hash,
if (!to_be_replaced
|| (emc_entry_alive(to_be_replaced)
&& !emc_entry_alive(current_entry))
- || current_entry->hash < to_be_replaced->hash) {
+ || current_entry->key.hash < to_be_replaced->key.hash) {
to_be_replaced = current_entry;
}
}
/* We didn't find the miniflow in the cache.
* The 'to_be_replaced' entry is where the new flow will be stored */
- emc_change_entry(to_be_replaced, flow, miniflow_to_netdev_flow_key(mf),
- hash);
+ emc_change_entry(to_be_replaced, flow, key);
}
static inline struct dp_netdev_flow *
-emc_lookup(struct emc_cache *cache, const struct miniflow *mf, uint32_t hash)
+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, hash) {
- if (current_entry->hash == hash && emc_entry_alive(current_entry)
- && netdev_flow_key_equal(¤t_entry->mf,
- miniflow_to_netdev_flow_key(mf),
- current_entry->mf_len)) {
+ EMC_FOR_EACH_POS_WITH_HASH(cache, current_entry, key->hash) {
+ if (current_entry->key.hash == key->hash
+ && emc_entry_alive(current_entry)
+ && netdev_flow_key_equal_mf(¤t_entry->key, &key->mf)) {
- /* We found the entry with the 'mf' miniflow */
+ /* We found the entry with the 'key->mf' miniflow */
return current_entry->flow;
}
}
@@ -1363,26 +1499,28 @@ emc_lookup(struct emc_cache *cache, const struct miniflow *mf, uint32_t hash)
}
static struct dp_netdev_flow *
-dp_netdev_lookup_flow(const struct dp_netdev *dp, const struct miniflow *key)
+dp_netdev_lookup_flow(const struct dp_netdev *dp,
+ const struct netdev_flow_key *key)
{
struct dp_netdev_flow *netdev_flow;
- struct cls_rule *rule;
+ struct dpcls_rule *rule;
- classifier_lookup_miniflow_batch(&dp->cls, &key, &rule, 1);
+ dpcls_lookup(&dp->cls, key, &rule, 1);
netdev_flow = dp_netdev_flow_cast(rule);
return netdev_flow;
}
+/* 'key->hash' needs to be initialized for this. */
static struct dp_netdev_flow *
-dp_netdev_find_flow(const struct dp_netdev *dp, const struct flow *flow)
+dp_netdev_find_flow(const struct dp_netdev *dp,
+ const struct netdev_flow_key *key)
{
- struct dp_netdev_flow *netdev_flow;
+ struct dp_netdev_flow *flow;
- CMAP_FOR_EACH_WITH_HASH (netdev_flow, node, flow_hash(flow, 0),
- &dp->flow_table) {
- if (flow_equal(&netdev_flow->flow, flow)) {
- return netdev_flow;
+ CMAP_FOR_EACH_WITH_HASH (flow, node, key->hash, &dp->flow_table) {
+ if (netdev_flow_key_equal(&flow->key, key)) {
+ return flow;
}
}
@@ -1411,12 +1549,13 @@ static void
dp_netdev_flow_to_dpif_flow(const struct dp_netdev_flow *netdev_flow,
struct ofpbuf *buffer, struct dpif_flow *flow)
{
- struct flow_wildcards wc;
+ struct match match;
struct dp_netdev_actions *actions;
- minimask_expand(&netdev_flow->cr.match.mask, &wc);
- odp_flow_key_from_mask(buffer, &wc.masks, &netdev_flow->flow,
- odp_to_u32(wc.masks.in_port.odp_port),
+ miniflow_expand(&netdev_flow->key.mf, &match.flow);
+ miniflow_expand(&netdev_flow->cr.mask->mf, &match.wc.masks);
+ odp_flow_key_from_mask(buffer, &match.wc.masks, &match.flow,
+ odp_to_u32(match.wc.masks.in_port.odp_port),
SIZE_MAX, true);
flow->mask = ofpbuf_data(buffer);
flow->mask_len = ofpbuf_size(buffer);
@@ -1525,55 +1664,61 @@ dpif_netdev_flow_get(const struct dpif *dpif, const struct dpif_flow_get *get)
{
struct dp_netdev *dp = get_dp_netdev(dpif);
struct dp_netdev_flow *netdev_flow;
- struct flow key;
+ struct flow flow;
+ struct netdev_flow_key key;
int error;
- error = dpif_netdev_flow_from_nlattrs(get->key, get->key_len, &key);
+ error = dpif_netdev_flow_from_nlattrs(get->key, get->key_len, &flow);
if (error) {
return error;
}
-
+ netdev_flow_key_from_flow(&key, &flow);
netdev_flow = dp_netdev_find_flow(dp, &key);
-
if (netdev_flow) {
dp_netdev_flow_to_dpif_flow(netdev_flow, get->buffer, get->flow);
- } else {
+ } else {
error = ENOENT;
}
return error;
}
-static int
-dp_netdev_flow_add(struct dp_netdev *dp, struct match *match,
+static struct dp_netdev_flow *
+dp_netdev_flow_add(struct dp_netdev *dp, struct netdev_flow_key *key,
+ struct flow_wildcards *wc,
const struct nlattr *actions, size_t actions_len)
OVS_REQUIRES(dp->flow_mutex)
{
- struct dp_netdev_flow *netdev_flow;
-
- netdev_flow = xzalloc(sizeof *netdev_flow);
- *CONST_CAST(struct flow *, &netdev_flow->flow) = match->flow;
-
- ovs_refcount_init(&netdev_flow->ref_cnt);
+ struct dp_netdev_flow *flow;
+ struct netdev_flow_key mask;
- ovsthread_stats_init(&netdev_flow->stats);
+ netdev_flow_mask_init(&mask, key, wc);
+ /* Make sure wc does not have metadata!. */
+ ovs_assert(!(mask.mf.map & (MINIFLOW_MAP(metadata) | MINIFLOW_MAP(regs))));
- ovsrcu_set(&netdev_flow->actions,
- dp_netdev_actions_create(actions, actions_len));
+ /* Do not allocate extra space. */
+ flow = xmalloc(sizeof *flow - sizeof flow->cr.flow + mask.len);
+ flow->dead = false;
+ netdev_flow_key_clone(CONST_CAST(struct netdev_flow_key *, &flow->key),
+ key);
+ ovs_refcount_init(&flow->ref_cnt);
+ ovsthread_stats_init(&flow->stats);
+ ovsrcu_set(&flow->actions, dp_netdev_actions_create(actions, actions_len));
- cls_rule_init(CONST_CAST(struct cls_rule *, &netdev_flow->cr),
- match, NETDEV_RULE_PRIORITY);
cmap_insert(&dp->flow_table,
- CONST_CAST(struct cmap_node *, &netdev_flow->node),
- flow_hash(&match->flow, 0));
- classifier_insert(&dp->cls,
- CONST_CAST(struct cls_rule *, &netdev_flow->cr));
+ CONST_CAST(struct cmap_node *, &flow->node), flow->key.hash);
+ netdev_flow_key_init_masked(&flow->cr.flow, key, &mask);
+ dpcls_insert(&dp->cls, &flow->cr, &mask);
if (OVS_UNLIKELY(VLOG_IS_DBG_ENABLED())) {
+ struct match match;
struct ds ds = DS_EMPTY_INITIALIZER;
+ miniflow_expand(&flow->key.mf, &match.flow);
+ miniflow_expand(&flow->cr.mask->mf, &match.wc.masks);
+
ds_put_cstr(&ds, "flow_add: ");
- match_format(match, &ds, OFP_DEFAULT_PRIORITY);
+ match_format(&match, &ds, OFP_DEFAULT_PRIORITY);
ds_put_cstr(&ds, ", actions:");
format_odp_actions(&ds, actions, actions_len);
@@ -1582,7 +1727,7 @@ dp_netdev_flow_add(struct dp_netdev *dp, struct match *match,
ds_destroy(&ds);
}
- return 0;
+ return flow;
}
static void
@@ -1606,32 +1751,34 @@ dpif_netdev_flow_put(struct dpif *dpif, const struct dpif_flow_put *put)
{
struct dp_netdev *dp = get_dp_netdev(dpif);
struct dp_netdev_flow *netdev_flow;
- struct miniflow miniflow;
- struct match match;
+ struct flow flow;
+ struct flow_wildcards wc;
+ struct netdev_flow_key key;
int error;
- error = dpif_netdev_flow_from_nlattrs(put->key, put->key_len, &match.flow);
+ error = dpif_netdev_flow_from_nlattrs(put->key, put->key_len, &flow);
if (error) {
return error;
}
error = dpif_netdev_mask_from_nlattrs(put->key, put->key_len,
put->mask, put->mask_len,
- &match.flow, &match.wc.masks);
+ &flow, &wc.masks);
if (error) {
return error;
}
- miniflow_init(&miniflow, &match.flow);
+ netdev_flow_key_from_flow(&key, &flow);
ovs_mutex_lock(&dp->flow_mutex);
- netdev_flow = dp_netdev_lookup_flow(dp, &miniflow);
+ netdev_flow = dp_netdev_lookup_flow(dp, &key);
if (!netdev_flow) {
if (put->flags & DPIF_FP_CREATE) {
if (cmap_count(&dp->flow_table) < MAX_FLOWS) {
if (put->stats) {
memset(put->stats, 0, sizeof *put->stats);
}
- error = dp_netdev_flow_add(dp, &match, put->actions,
- put->actions_len);
+ dp_netdev_flow_add(dp, &key, &wc, put->actions,
+ put->actions_len);
+ error = 0;
} else {
error = EFBIG;
}
@@ -1640,7 +1787,7 @@ dpif_netdev_flow_put(struct dpif *dpif, const struct dpif_flow_put *put)
}
} else {
if (put->flags & DPIF_FP_MODIFY
- && flow_equal(&match.flow, &netdev_flow->flow)) {
+ && netdev_flow_key_equal(&netdev_flow->key, &key)) {
struct dp_netdev_actions *new_actions;
struct dp_netdev_actions *old_actions;
@@ -1666,7 +1813,6 @@ dpif_netdev_flow_put(struct dpif *dpif, const struct dpif_flow_put *put)
}
}
ovs_mutex_unlock(&dp->flow_mutex);
- miniflow_destroy(&miniflow);
return error;
}
@@ -1676,13 +1822,15 @@ dpif_netdev_flow_del(struct dpif *dpif, const struct dpif_flow_del *del)
{
struct dp_netdev *dp = get_dp_netdev(dpif);
struct dp_netdev_flow *netdev_flow;
- struct flow key;
+ struct flow flow;
+ struct netdev_flow_key key;
int error;
- error = dpif_netdev_flow_from_nlattrs(del->key, del->key_len, &key);
+ error = dpif_netdev_flow_from_nlattrs(del->key, del->key_len, &flow);
if (error) {
return error;
}
+ netdev_flow_key_from_flow(&key, &flow);
ovs_mutex_lock(&dp->flow_mutex);
netdev_flow = dp_netdev_find_flow(dp, &key);
@@ -1806,21 +1954,23 @@ dpif_netdev_flow_dump_next(struct dpif_flow_dump_thread *thread_,
struct dp_netdev_flow *netdev_flow = netdev_flows[i];
struct dpif_flow *f = &flows[i];
struct dp_netdev_actions *dp_actions;
+ struct flow flow;
struct flow_wildcards wc;
struct ofpbuf buf;
- minimask_expand(&netdev_flow->cr.match.mask, &wc);
+ miniflow_expand(&netdev_flow->cr.mask->mf, &wc.masks);
+ miniflow_expand(&netdev_flow->key.mf, &flow);
/* Key. */
ofpbuf_use_stack(&buf, keybuf, sizeof *keybuf);
- odp_flow_key_from_flow(&buf, &netdev_flow->flow, &wc.masks,
- netdev_flow->flow.in_port.odp_port, true);
+ odp_flow_key_from_flow(&buf, &flow, &wc.masks, flow.in_port.odp_port,
+ true);
f->key = ofpbuf_data(&buf);
f->key_len = ofpbuf_size(&buf);
/* Mask. */
ofpbuf_use_stack(&buf, maskbuf, sizeof *maskbuf);
- odp_flow_key_from_mask(&buf, &wc.masks, &netdev_flow->flow,
+ odp_flow_key_from_mask(&buf, &wc.masks, &flow,
odp_to_u32(wc.masks.in_port.odp_port),
SIZE_MAX, true);
f->mask = ofpbuf_data(&buf);
@@ -2583,23 +2733,22 @@ emc_processing(struct dp_netdev_pmd_thread *pmd, struct dpif_packet **packets,
size_t notfound_cnt = 0;
n_batches = 0;
- miniflow_initialize(&key.flow, key.buf);
+ miniflow_initialize(&key.mf, key.buf);
for (i = 0; i < cnt; i++) {
struct dp_netdev_flow *flow;
- uint32_t hash;
if (OVS_UNLIKELY(ofpbuf_size(&packets[i]->ofpbuf) < ETH_HEADER_LEN)) {
dpif_packet_delete(packets[i]);
continue;
}
- miniflow_extract(&packets[i]->ofpbuf, md, &key.flow);
-
- hash = dpif_netdev_packet_get_dp_hash(packets[i], &key.flow);
+ miniflow_extract(&packets[i]->ofpbuf, md, &key.mf);
+ key.len = 0; /* Not computed yet. */
+ key.hash = dpif_netdev_packet_get_dp_hash(packets[i], &key.mf);
- flow = emc_lookup(flow_cache, &key.flow, hash);
+ flow = emc_lookup(flow_cache, &key);
if (OVS_UNLIKELY(!dp_netdev_queue_batches(packets[i], md,
- flow, &key.flow,
+ flow, &key.mf,
batches, &n_batches,
ARRAY_SIZE(batches)))) {
if (i != notfound_cnt) {
@@ -2629,51 +2778,52 @@ fast_path_processing(struct dp_netdev_pmd_thread *pmd,
enum { PKT_ARRAY_SIZE = NETDEV_MAX_RX_BATCH };
#endif
struct packet_batch batches[PKT_ARRAY_SIZE];
- const struct miniflow *mfs[PKT_ARRAY_SIZE]; /* NULL at bad packets. */
- struct cls_rule *rules[PKT_ARRAY_SIZE];
+ struct dpcls_rule *rules[PKT_ARRAY_SIZE];
struct dp_netdev *dp = pmd->dp;
struct emc_cache *flow_cache = &pmd->flow_cache;
size_t n_batches, i;
bool any_miss;
for (i = 0; i < cnt; i++) {
- mfs[i] = &keys[i].flow;
+ /* Key length is needed in all the cases, hash computed on demand. */
+ keys[i].len = netdev_flow_key_size(count_1bits(keys[i].mf.map));
}
- any_miss = !classifier_lookup_miniflow_batch(&dp->cls, mfs, rules, cnt);
+ any_miss = !dpcls_lookup(&dp->cls, keys, rules, cnt);
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;
- struct match match;
ofpbuf_use_stub(&actions, actions_stub, sizeof actions_stub);
ofpbuf_use_stub(&put_actions, slow_stub, sizeof slow_stub);
for (i = 0; i < cnt; i++) {
- const struct dp_netdev_flow *netdev_flow;
+ struct dp_netdev_flow *netdev_flow;
struct ofpbuf *add_actions;
+ struct flow flow;
+ struct flow_wildcards wc;
int error;
- if (OVS_LIKELY(rules[i] || !mfs[i])) {
+ if (OVS_LIKELY(rules[i])) {
continue;
}
/* It's possible that an earlier slow path execution installed
- * the rule this flow needs. In this case, it's a lot cheaper
+ * a rule covering this flow. In this case, it's a lot cheaper
* to catch it here than execute a miss. */
- netdev_flow = dp_netdev_lookup_flow(dp, mfs[i]);
+ netdev_flow = dp_netdev_lookup_flow(dp, &keys[i]);
if (netdev_flow) {
- rules[i] = CONST_CAST(struct cls_rule *, &netdev_flow->cr);
+ rules[i] = &netdev_flow->cr;
continue;
}
- miniflow_expand(mfs[i], &match.flow);
+ miniflow_expand(&keys[i].mf, &flow);
ofpbuf_clear(&actions);
ofpbuf_clear(&put_actions);
- error = dp_netdev_upcall(dp, packets[i], &match.flow, &match.wc,
- DPIF_UC_MISS, NULL, &actions,
- &put_actions);
+ error = dp_netdev_upcall(dp, packets[i], &flow, &wc,
+ DPIF_UC_MISS, NULL, &actions,
+ &put_actions);
if (OVS_UNLIKELY(error && error != ENOSPC)) {
continue;
}
@@ -2689,19 +2839,28 @@ fast_path_processing(struct dp_netdev_pmd_thread *pmd,
? &put_actions
: &actions;
- ovs_mutex_lock(&dp->flow_mutex);
- /* XXX: There's a brief race where this flow could have already
- * been installed since we last did the flow lookup. This could be
- * solved by moving the mutex lock outside the loop, but that's an
- * awful long time to be locking everyone out of making flow
- * installs. If we move to a per-core classifier, it would be
- * reasonable. */
- if (OVS_LIKELY(error != ENOSPC)
- && !dp_netdev_lookup_flow(dp, mfs[i])) {
- dp_netdev_flow_add(dp, &match, ofpbuf_data(add_actions),
- ofpbuf_size(add_actions));
+ if (OVS_LIKELY(error != ENOSPC)) {
+ keys[i].hash = netdev_flow_key_hash(&keys[i]);
+
+ /* XXX: There's a race window where a flow covering this packet
+ * could have already been installed since we last did the flow
+ * lookup before upcall. This could be solved by moving the
+ * mutex lock outside the loop, but that's an awful long time
+ * to be locking everyone out of making flow installs. If we
+ * move to a per-core classifier, it would be reasonable. */
+ ovs_mutex_lock(&dp->flow_mutex);
+ netdev_flow = dp_netdev_lookup_flow(dp, &keys[i]);
+ if (OVS_LIKELY(!netdev_flow)) {
+ netdev_flow = dp_netdev_flow_add(dp, &keys[i], &wc,
+ ofpbuf_data(add_actions),
+ ofpbuf_size(add_actions));
+ }
+ ovs_mutex_unlock(&dp->flow_mutex);
+
+ /* EMC uses different hash. */
+ keys[i].hash = dpif_packet_get_dp_hash(packets[i]);
+ emc_insert(flow_cache, &keys[i], netdev_flow);
}
- ovs_mutex_unlock(&dp->flow_mutex);
}
ofpbuf_uninit(&actions);
@@ -2711,7 +2870,7 @@ fast_path_processing(struct dp_netdev_pmd_thread *pmd,
int dropped_cnt = 0;
for (i = 0; i < cnt; i++) {
- if (OVS_UNLIKELY(!rules[i] && mfs[i])) {
+ if (OVS_UNLIKELY(!rules[i])) {
dpif_packet_delete(packets[i]);
dropped_cnt++;
}
@@ -2725,15 +2884,15 @@ fast_path_processing(struct dp_netdev_pmd_thread *pmd,
struct dpif_packet *packet = packets[i];
struct dp_netdev_flow *flow;
- if (OVS_UNLIKELY(!rules[i] || !mfs[i])) {
+ if (OVS_UNLIKELY(!rules[i])) {
continue;
}
flow = dp_netdev_flow_cast(rules[i]);
- emc_insert(flow_cache, mfs[i], dpif_packet_get_dp_hash(packet),
- flow);
- dp_netdev_queue_batches(packet, md, flow, mfs[i], batches, &n_batches,
- ARRAY_SIZE(batches));
+ keys[i].hash = dpif_packet_get_dp_hash(packet);
+ emc_insert(flow_cache, &keys[i], flow);
+ dp_netdev_queue_batches(packet, md, flow, &keys[i].mf, batches,
+ &n_batches, ARRAY_SIZE(batches));
}
for (i = 0; i < n_batches; i++) {
@@ -3084,3 +3243,191 @@ dpif_dummy_register(bool override)
unixctl_command_register("dpif-dummy/delete-port", "dp port",
2, 2, dpif_dummy_delete_port, NULL);
}
+
+/* Datapath Classifier. */
+
+/* A set of rules that all have the same fields wildcarded. */
+struct dpcls_subtable {
+ /* The fields are only used by writers. */
+ struct cmap_node cmap_node; /* Within struct classifier 'subtables_map'. */
+
+ /* These fields are accessed by readers. */
+ struct cmap rules; /* Contains "struct dpcls_rule"s. */
+ struct netdev_flow_key mask; /* Wildcards for fields (const). */
+ /* 'mask' must be the last field. */
+};
+
+/* Initializes 'cls' as a classifier that initially contains no classification
+ * rules. */
+static void
+dpcls_init(struct dpcls *cls)
+{
+ cmap_init(&cls->subtables_map);
+ pvector_init(&cls->subtables);
+}
+
+static void
+dpcls_destroy_subtable(struct dpcls *cls, struct dpcls_subtable *subtable)
+{
+ pvector_remove(&cls->subtables, subtable);
+ cmap_remove(&cls->subtables_map, &subtable->cmap_node,
+ subtable->mask.hash);
+ cmap_destroy(&subtable->rules);
+ ovsrcu_postpone(free, subtable);
+}
+
+/* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the
+ * caller's responsibility.
+ * May only be called after all the readers have been terminated. */
+static void
+dpcls_destroy(struct dpcls *cls)
+{
+ if (cls) {
+ struct dpcls_subtable *subtable;
+
+ CMAP_FOR_EACH (subtable, cmap_node, &cls->subtables_map) {
+ dpcls_destroy_subtable(cls, subtable);
+ }
+ cmap_destroy(&cls->subtables_map);
+ pvector_destroy(&cls->subtables);
+ }
+}
+
+static struct dpcls_subtable *
+dpcls_create_subtable(struct dpcls *cls, const struct netdev_flow_key *mask)
+{
+ struct dpcls_subtable *subtable;
+
+ /* Need to add one. */
+ subtable = xmalloc(sizeof *subtable - sizeof subtable->mask + mask->len);
+ cmap_init(&subtable->rules);
+ netdev_flow_key_clone(&subtable->mask, mask);
+ cmap_insert(&cls->subtables_map, &subtable->cmap_node, mask->hash);
+ pvector_insert(&cls->subtables, subtable, 0);
+
+ return subtable;
+}
+
+static inline struct dpcls_subtable *
+dpcls_find_subtable(struct dpcls *cls, const struct netdev_flow_key *mask)
+{
+ struct dpcls_subtable *subtable;
+
+ CMAP_FOR_EACH_WITH_HASH (subtable, cmap_node, mask->hash,
+ &cls->subtables_map) {
+ if (netdev_flow_key_equal(&subtable->mask, mask)) {
+ return subtable;
+ }
+ }
+ return dpcls_create_subtable(cls, mask);
+}
+
+/* Insert 'rule' into 'cls'. */
+static void
+dpcls_insert(struct dpcls *cls, struct dpcls_rule *rule,
+ const struct netdev_flow_key *mask)
+{
+ struct dpcls_subtable *subtable = dpcls_find_subtable(cls, mask);
+
+ rule->mask = &subtable->mask;
+ cmap_insert(&subtable->rules, &rule->cmap_node, rule->flow.hash);
+}
+
+/* Removes 'rule' from 'cls', also destructing the 'rule'. */
+static void
+dpcls_remove(struct dpcls *cls, struct dpcls_rule *rule)
+{
+ struct dpcls_subtable *subtable;
+
+ ovs_assert(rule->mask);
+
+ INIT_CONTAINER(subtable, rule->mask, mask);
+
+ if (cmap_remove(&subtable->rules, &rule->cmap_node, rule->flow.hash)
+ == 0) {
+ dpcls_destroy_subtable(cls, subtable);
+ }
+
+ rule->mask = NULL;
+}
+
+/* Returns true if 'target' satisifies 'key' in 'mask', that is, if each 1-bit
+ * in 'mask' the values in 'key' and 'target' are the same.
+ *
+ * Note: 'key' and 'mask' have the same mask, and 'key' is already masked. */
+static inline bool
+dpcls_rule_matches_key(const struct dpcls_rule *rule,
+ const struct netdev_flow_key *target)
+{
+ const uint32_t *keyp = rule->flow.mf.inline_values;
+ const uint32_t *maskp = rule->mask->mf.inline_values;
+ uint32_t target_u32;
+
+ NETDEV_FLOW_KEY_FOR_EACH_IN_MAP(target_u32, target, rule->flow.mf.map) {
+ if (OVS_UNLIKELY((target_u32 & *maskp++) != *keyp++)) {
+ return false;
+ }
+ }
+ return true;
+}
+
+static inline struct dpcls_rule *
+dpcls_subtable_find_match(const struct dpcls_subtable *subtable,
+ const struct netdev_flow_key *key)
+{
+ struct dpcls_rule *rule;
+ uint32_t hash;
+
+ hash = netdev_flow_key_hash_in_mask(key, &subtable->mask);
+
+ CMAP_FOR_EACH_WITH_HASH (rule, cmap_node, hash, &subtable->rules) {
+ if (OVS_LIKELY(dpcls_rule_matches_key(rule, key))) {
+ return rule;
+ }
+ }
+
+ return NULL;
+}
+
+/* For each miniflow in 'flows' performs a classifier lookup writing the result
+ * into the corresponding slot in 'rules'. If a particular entry in 'flows' is
+ * NULL it is skipped.
+ *
+ * This function is optimized for use in the userspace datapath and therefore
+ * does not implement a lot of features available in the standard
+ * classifier_lookup() function. Specifically, it does not implement
+ * priorities, instead returning any rule which matches the flow.
+ *
+ * Returns true if all flows found a corresponding rule. */
+static bool
+dpcls_lookup(const struct dpcls *cls, const struct netdev_flow_key keys[],
+ struct dpcls_rule **rules, size_t cnt)
+{
+ struct dpcls_subtable *subtable;
+ size_t i, begin = 0;
+
+ memset(rules, 0, cnt * sizeof *rules);
+ PVECTOR_FOR_EACH (subtable, &cls->subtables) {
+ for (i = begin; i < cnt; i++) {
+ struct dpcls_rule *rule;
+
+ if (OVS_UNLIKELY(rules[i])) {
+ continue;
+ }
+
+ rule = dpcls_subtable_find_match(subtable, &keys[i]);
+ if (OVS_UNLIKELY(rule)) {
+ rules[i] = rule;
+ }
+ }
+
+ while (begin < cnt && rules[begin]) {
+ begin++;
+ }
+ if (begin >= cnt) {
+ return true;
+ }
+ }
+
+ return false;
+}
--
1.7.10.4
More information about the dev
mailing list