[ovs-dev] [PATCH] dpcls: cache miniflow blocks during lookup
Harry van Haaren
harry.van.haaren at intel.com
Fri Jun 1 10:45:27 UTC 2018
Lookup consists of 3 main stages:
1) hashing of the packet miniflow based on subtable mf bits
2) lookup of that hash into cmap
3) verification of the rule based on the rule mf bits
Before this commit, the iteration of stages 1) and 3) was
totally independant, and the work done was duplicate. The
reason is that the bits in the subtable and the rule are
identical.
This commit optimizes away this duplicate work by caching
the data values retrieved from the packet miniflow, storing
them in a linear array that matches the subtable mf blocks.
Once the cmap lookup has completed, the *same* miniflow
must be iterated, and the cached miniflow block data is now
re-used. This avoids iterating the packet miniflow for the
second time, and reducing the overhead of rule verification.
Performance:
This patch was tested using VSPerf with phy2phy_cont test,
varying the number of flows, and with EMC en/dis-abled.
Results are based on initial testing here - please verify
with your use-case and report back :)
Flows | EMC | Master mpps | +Patch mpps | Perf Gain
----------------------------------------------------
4K | 1 | ~15.1 | ~15.2 | + ~0.6 %
4K | 0 | ~14.6 | ~15.9 | + ~8.2 %
1M | 1 | ~13.5 | ~14.4 | + ~6.5 %
1M | 0 | ~14.6 | ~15.8 | + ~8.2 %
The approx neutral performance with EMC enabled and a low
flow count (4K) is due to that DPCLS is not often hit as
EMC will match many of the flows. In cases where EMC is
disabled, we see a consistent performance improvement as
DPCLS is used for each packet match.
Input and feedback welcomed,
Signed-off-by: Harry van Haaren <harry.van.haaren at intel.com>
---
lib/dpif-netdev.c | 60 ++++++++++++++++++++++++++++++++++++++++++-------------
1 file changed, 46 insertions(+), 14 deletions(-)
diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index 818b184..ba03040 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -2185,7 +2185,8 @@ netdev_flow_key_init_masked(struct netdev_flow_key *dst,
* 'mask'. */
static inline uint32_t
netdev_flow_key_hash_in_mask(const struct netdev_flow_key *key,
- const struct netdev_flow_key *mask)
+ const struct netdev_flow_key *mask,
+ uint64_t *blocks)
{
const uint64_t *p = miniflow_get_values(&mask->mf);
uint32_t hash = 0;
@@ -2193,6 +2194,7 @@ netdev_flow_key_hash_in_mask(const struct netdev_flow_key *key,
NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(value, key, mask->mf.map) {
hash = hash_add64(hash, value & *p++);
+ *blocks++ = value;
}
return hash_finish(hash, (p - miniflow_get_values(&mask->mf)) * 8);
@@ -6203,6 +6205,9 @@ dpif_dummy_register(enum dummy_level level)
/* A set of rules that all have the same fields wildcarded. */
struct dpcls_subtable {
+ /* number of bits set in miniflow, aka blocks used in hash calculation */
+ uint32_t num_mf_bits;
+
/* The fields are only used by writers. */
struct cmap_node cmap_node OVS_GUARDED; /* Within dpcls 'subtables_map'. */
@@ -6263,11 +6268,17 @@ dpcls_create_subtable(struct dpcls *cls, const struct netdev_flow_key *mask)
cmap_init(&subtable->rules);
subtable->hit_cnt = 0;
netdev_flow_key_clone(&subtable->mask, mask);
+
+ /* count the number of bits in this subtable miniflow */
+ subtable->num_mf_bits = __builtin_popcountll(mask->mf.map.bits[0]) +
+ __builtin_popcountll(mask->mf.map.bits[1]);
+
cmap_insert(&cls->subtables_map, &subtable->cmap_node, mask->hash);
/* Add the new subtable at the end of the pvector (with no hits yet) */
pvector_insert(&cls->subtables, subtable, 0);
- VLOG_DBG("Creating %"PRIuSIZE". subtable %p for in_port %d",
- cmap_count(&cls->subtables_map), subtable, cls->in_port);
+ VLOG_DBG("Creating %"PRIuSIZE". subtable %p for in_port %d, mf bits %d\n",
+ cmap_count(&cls->subtables_map), subtable, cls->in_port,
+ subtable->num_mf_bits);
pvector_publish(&cls->subtables);
return subtable;
@@ -6287,7 +6298,6 @@ dpcls_find_subtable(struct dpcls *cls, const struct netdev_flow_key *mask)
return dpcls_create_subtable(cls, mask);
}
-
/* Periodically sort the dpcls subtable vectors according to hit counts */
static void
dpcls_sort_subtable_vector(struct dpcls *cls)
@@ -6375,18 +6385,21 @@ dpcls_remove(struct dpcls *cls, struct dpcls_rule *rule)
}
}
-/* Returns true if 'target' satisfies 'key' in 'mask', that is, if each 1-bit
- * in 'mask' the values in 'key' and 'target' are the same. */
+/* Returns true if the packet represented by pkt_blocks equals rule,
+ * after the pkt_blocks have been masked by the subtable mask.
+ */
static inline bool
dpcls_rule_matches_key(const struct dpcls_rule *rule,
- const struct netdev_flow_key *target)
+ const uint64_t *pkt_blocks,
+ const uint32_t mf_bits)
{
- const uint64_t *keyp = miniflow_get_values(&rule->flow.mf);
- const uint64_t *maskp = miniflow_get_values(&rule->mask->mf);
- uint64_t value;
+ const uint64_t *tbl_blocks_mask = miniflow_get_values(&rule->mask->mf);
+ const uint64_t *rule_block_values = miniflow_get_values(&rule->flow.mf);
- NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(value, target, rule->flow.mf.map) {
- if (OVS_UNLIKELY((value & *maskp++) != *keyp++)) {
+ int i;
+ for (i = 0; i < mf_bits; i++) {
+ const uint64_t masked_data = pkt_blocks[i] & tbl_blocks_mask[i];
+ if (masked_data != rule_block_values[i]) {
return false;
}
}
@@ -6436,16 +6449,31 @@ dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key keys[],
* search-key against each subtable, but when a match is found for a
* search-key, the search for that key can stop because the rules are
* non-overlapping. */
+
+ /* calculate the number of blocks that the miniflow *could* take. This is
+ * results in one uint64_t being reserved on the stack for any potential
+ * miniflow data. It is over-provisioned for any real-world usecase, but
+ * this gaurantees there is space for all miniflow values.
+ */
+#define MF_BLOCKS_MAX (MAP_T_BITS * FLOWMAP_UNITS)
+ uint64_t blocks_pkts[NETDEV_MAX_BURST * MF_BLOCKS_MAX];
+
PVECTOR_FOR_EACH (subtable, &cls->subtables) {
int i;
+ /* make space on stack to cache miniflow block data from packets */
+ const uint32_t mf_bits = subtable->num_mf_bits;
+
/* Compute hashes for the remaining keys. Each search-key is
* masked with the subtable's mask to avoid hashing the wildcarded
* bits. */
ULLONG_FOR_EACH_1(i, keys_map) {
+ const uint32_t block_idx = i * MF_BLOCKS_MAX;
hashes[i] = netdev_flow_key_hash_in_mask(&keys[i],
- &subtable->mask);
+ &subtable->mask,
+ &blocks_pkts[block_idx]);
}
+
/* Lookup. */
found_map = cmap_find_batch(&subtable->rules, keys_map, hashes, nodes);
/* Check results. When the i-th bit of found_map is set, it means
@@ -6457,7 +6485,11 @@ dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key keys[],
struct dpcls_rule *rule;
CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) {
- if (OVS_LIKELY(dpcls_rule_matches_key(rule, &keys[i]))) {
+ const uint64_t *blocks = &blocks_pkts[i * MF_BLOCKS_MAX];
+ int rule_matches = dpcls_rule_matches_key(rule, blocks,
+ mf_bits);
+
+ if (OVS_LIKELY(rule_matches)) {
rules[i] = rule;
/* Even at 20 Mpps the 32-bit hit_cnt cannot wrap
* within one second optimization interval. */
--
2.7.4
More information about the dev
mailing list