@@ -158,6 +158,9 @@ struct netdev_flow_key {
#define EM_FLOW_INSERT_INV_PROB_SHIFT 20
#define EM_FLOW_INSERT_INV_PROB_MAX (1 << EM_FLOW_INSERT_INV_PROB_SHIFT)
#define EM_FLOW_INSERT_INV_PROB_MASK (EM_FLOW_INSERT_INV_PROB_MAX - 1)
+/* We will use bits higher than EM_FLOW_INSERT_INV_PROB_SHIFT of the random
+ * value for EMC replacement policy. */
+BUILD_ASSERT_DECL(32 - EM_FLOW_INSERT_INV_PROB_SHIFT >= EM_FLOW_HASH_SEGS);
/* 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 (EM_FLOW_INSERT_INV_PROB_MAX / \
@@ -2058,7 +2061,7 @@ emc_change_entry(struct emc_entry *ce, struct dp_netdev_flow *flow,
static inline void
emc_insert(struct emc_cache *cache, const struct netdev_flow_key *key,
- struct dp_netdev_flow *flow)
+ struct dp_netdev_flow *flow, uint32_t random_value)
{
struct emc_entry *to_be_replaced = NULL;
struct emc_entry *current_entry;
@@ -2071,12 +2074,12 @@ emc_insert(struct emc_cache *cache, const struct netdev_flow_key *key,
}
/* Replacement policy: put the flow in an empty (not alive) entry, or
- * in the first entry where it can be */
+ * in the random entry where it can be */
if (!to_be_replaced
|| (emc_entry_alive(to_be_replaced)
- && !emc_entry_alive(current_entry))
- || current_entry->key.hash < to_be_replaced->key.hash) {
+ && (!emc_entry_alive(current_entry) || random_value & 1))) {
to_be_replaced = current_entry;
+ random_value >>= 1;
}
}
/* We didn't find the miniflow in the cache.
@@ -2094,11 +2097,17 @@ emc_probabilistic_insert(struct dp_netdev_pmd_thread *pmd,
* default the value is UINT32_MAX / 100 which yields an insertion
* probability of 1/100 ie. 1% */
- uint32_t min;
+ uint32_t min, random_value;
atomic_read_relaxed(&pmd->dp->emc_insert_min, &min);
- if (min && (random_uint32() & EM_FLOW_INSERT_INV_PROB_MASK) < min) {
- emc_insert(&pmd->flow_cache, key, flow);
+ if (!min) {
+ return;
+ }
+
+ random_value = random_uint32();
+ if ((random_value & EM_FLOW_INSERT_INV_PROB_MASK) < min) {
+ emc_insert(&pmd->flow_cache, key, flow,
+ random_value >> EM_FLOW_INSERT_INV_PROB_SHIFT);
}
}
Current EMC replacement policy allows to replace active EMC entry even if there are dead (empty) entries available. This leads to EMC trashing even on few hundreds of flows. In some cases PMD threads starts to execute classifier lookups even in tests with 50 - 100 active flows. Looks like the hash comparison rule was introduced to randomly choose one of alive entries to replace. But it doesn't work as needed and also hashes has nothing common with randomness. Lets fix the replacement policy by removing hash checking and using the random value passed from 'emc_probabilistic_insert()' only while considering replace of the alive entry. This should give us nearly fair way to choose the entry to replace. We are avoiding calculation of the new random value by reusing bits of already generated random for probabilistic EMC insertion. Bits higher than 'EM_FLOW_INSERT_INV_PROB_SHIFT' are used because lower bits are less than 'min' and not fully random. Not replacing of alive entries while dead ones exists allows to significantly decrease EMC trashing. Testing shows stable work of exact match cache without misses with up to 3072 - 6144 active flows (depends on traffic pattern). Signed-off-by: Ilya Maximets <i.maximets@samsung.com> --- Some test results from Antonio Fischetti here: https://mail.openvswitch.org/pipermail/ovs-dev/2017-August/336707.html lib/dpif-netdev.c | 23 ++++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-)