[ovs-dev] [PATCH v2 1/2] dpif-netdev: Decrease range of values for EMC probability.

Ilya Maximets i.maximets at samsung.com
Mon Jul 31 14:41:26 UTC 2017


Currently, real insertion probability is higher than configured
for the maximum case because of wrong usage of the random value.

i.e. if 'emc-invert-inv-prob' == UINT32_MAX, then 'emc_insert_min'
equals to 1. In this case we're allowing insert if random vailue
is less or equal to 1. So, two of 2**32 values (0 and 1) are
allowed and real probability is 2 times higher than configured.

This happens because 'random_uint32()' returns value in range
[0; UINT32_MAX], but for the checking to be correct we should
generate random value in range [0; UINT32_MAX - 1].

To fix this we have 4 possible solutions:

 1. need to use uint64_t for 'emc-insert-min' and calculate it
    as '(UINT32_MAX + 1) / inverse_prob' to fairly check the full
    range [0; UINT32_MAX].

    This may decrease performance becaue of 64 bit atomic ops.

 2. Forbid the '2**32 - 1' as the value for 'emc-insert-min'
    because it's the only value we have issues with.

    This will require additional explanations and not very friendly
    for users.

 3. Generate random value in range [0; UINT32_MAX - 1].

    This will require heavy division operation.

 4. Decrease the range of available values for 'emc-insert-inv-prob'.

    Actually, we don't need to have so much different values for
    that option. I beleve that values higher than 1M are completely
    useless. Choosing the upper limit as a power of 2 like 2**20 we
    will be able to mask the generated random value in a fast way
    and also avoid range issue, because same uint32_t can be used to
    store 2**20.

This patch implements solution #4.

CC: Ciara Loftus <ciara.loftus at intel.com>
Fixes: 4c30b24602c3 ("dpif-netdev: Conditional EMC insert")
Signed-off-by: Ilya Maximets <i.maximets at samsung.com>
---

Infrastructure and logic introduced here will be used for fixing
emc replacement policy.

 lib/dpif-netdev.c    | 12 ++++++++----
 vswitchd/vswitch.xml |  3 ++-
 2 files changed, 10 insertions(+), 5 deletions(-)

diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index 47a9fa0..123a7c9 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -152,9 +152,12 @@ struct netdev_flow_key {
 #define EM_FLOW_HASH_MASK (EM_FLOW_HASH_ENTRIES - 1)
 #define EM_FLOW_HASH_SEGS 2
 
+#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)
 /* 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 /                     \
+#define DEFAULT_EM_FLOW_INSERT_MIN (EM_FLOW_INSERT_INV_PROB_MAX /        \
                                     DEFAULT_EM_FLOW_INSERT_INV_PROB)
 
 struct emc_entry {
@@ -2077,7 +2080,7 @@ emc_probabilistic_insert(struct dp_netdev_pmd_thread *pmd,
     uint32_t min;
     atomic_read_relaxed(&pmd->dp->emc_insert_min, &min);
 
-    if (min && random_uint32() <= min) {
+    if (min && (random_uint32() & EM_FLOW_INSERT_INV_PROB_MASK) < min) {
         emc_insert(&pmd->flow_cache, key, flow);
     }
 }
@@ -2894,8 +2897,9 @@ dpif_netdev_set_config(struct dpif *dpif, const struct smap *other_config)
     }
 
     atomic_read_relaxed(&dp->emc_insert_min, &cur_min);
-    if (insert_prob <= UINT32_MAX) {
-        insert_min = insert_prob == 0 ? 0 : UINT32_MAX / insert_prob;
+    if (insert_prob < EM_FLOW_INSERT_INV_PROB_MAX) {
+        insert_min = insert_prob == 0
+                     ? 0 : EM_FLOW_INSERT_INV_PROB_MAX / insert_prob;
     } else {
         insert_min = DEFAULT_EM_FLOW_INSERT_MIN;
         insert_prob = DEFAULT_EM_FLOW_INSERT_INV_PROB;
diff --git a/vswitchd/vswitch.xml b/vswitchd/vswitch.xml
index 074535b..61f252e 100644
--- a/vswitchd/vswitch.xml
+++ b/vswitchd/vswitch.xml
@@ -381,7 +381,8 @@
       </column>
 
       <column name="other_config" key="emc-insert-inv-prob"
-              type='{"type": "integer", "minInteger": 0, "maxInteger": 4294967295}'>
+              type='{"type": "integer",
+                     "minInteger": 0, "maxInteger": 1048575}'>
         <p>
           Specifies the inverse probability (1/emc-insert-inv-prob) of a flow
           being inserted into the Exact Match Cache (EMC). On average one in
-- 
2.7.4



More information about the dev mailing list