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

Submitted by Ilya Maximets on July 31, 2017, 2:41 p.m.

Details

Message ID 1501512087-29023-2-git-send-email-i.maximets@samsung.com
State New
Headers show

Commit Message

Ilya Maximets July 31, 2017, 2:41 p.m.
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@intel.com>
Fixes: 4c30b24602c3 ("dpif-netdev: Conditional EMC insert")
Signed-off-by: Ilya Maximets <i.maximets@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(-)

Comments

Fischetti, Antonio Aug. 3, 2017, 3:37 p.m.
LGTM, 
just wondering if a further comment would help, 
eg something like

+/* random_uint32() returns a value in the [0; UINT32_MAX] range.
+   For our checking to be correct we would need instead a random value
+   in the range [0; UINT32_MAX - 1]. To avoid further computation 
+   we use a decreased range of available values for 'emc-insert-inv-prob'
+   ie [0; 2**20 - 1]. */
+#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)

?

-Antonio

> -----Original Message-----
> From: ovs-dev-bounces@openvswitch.org [mailto:ovs-dev-bounces@openvswitch.org]
> On Behalf Of Ilya Maximets
> Sent: Monday, July 31, 2017 3:41 PM
> To: ovs-dev@openvswitch.org
> Cc: Heetae Ahn <heetae82.ahn@samsung.com>; Ilya Maximets
> <i.maximets@samsung.com>
> Subject: [ovs-dev] [PATCH v2 1/2] dpif-netdev: Decrease range of values for EMC
> probability.
> 
> 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@intel.com>
> Fixes: 4c30b24602c3 ("dpif-netdev: Conditional EMC insert")
> Signed-off-by: Ilya Maximets <i.maximets@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
> 
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
Ilya Maximets Aug. 4, 2017, 11:37 a.m.
Hi Antonio,

Thanks for review and testing. Comments inline.

Best regards, Ilya Maximets.

On 03.08.2017 18:37, Fischetti, Antonio wrote:
> LGTM, 
> just wondering if a further comment would help, 
> eg something like
> 
> +/* random_uint32() returns a value in the [0; UINT32_MAX] range.
> +   For our checking to be correct we would need instead a random value
> +   in the range [0; UINT32_MAX - 1]. To avoid further computation 
> +   we use a decreased range of available values for 'emc-insert-inv-prob'
> +   ie [0; 2**20 - 1]. */
> +#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)
> 
> ?
> 
> -Antonio

I don't think that such a comment will be useful for the reader.
This is more like explanation why we made this change and it should
be in commit message (which already has this information).

In addition, the next patch adds build time assert which will forbid
using of EM_FLOW_INSERT_INV_PROB_SHIFT higher than 30.

One thing we may clarify here is why 20 was chosen.
Something like this:

/* Set up maximum inverse EMC insertion probability to 2^20 - 1.
 * Higher values considered useless in practice. */

What do you think?

> 
>> -----Original Message-----
>> From: ovs-dev-bounces@openvswitch.org [mailto:ovs-dev-bounces@openvswitch.org]
>> On Behalf Of Ilya Maximets
>> Sent: Monday, July 31, 2017 3:41 PM
>> To: ovs-dev@openvswitch.org
>> Cc: Heetae Ahn <heetae82.ahn@samsung.com>; Ilya Maximets
>> <i.maximets@samsung.com>
>> Subject: [ovs-dev] [PATCH v2 1/2] dpif-netdev: Decrease range of values for EMC
>> probability.
>>
>> 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@intel.com>
>> Fixes: 4c30b24602c3 ("dpif-netdev: Conditional EMC insert")
>> Signed-off-by: Ilya Maximets <i.maximets@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
>>
>> _______________________________________________
>> dev mailing list
>> dev@openvswitch.org
>> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
> 
> 
>
Fischetti, Antonio Aug. 4, 2017, 1:55 p.m.
My reply inline.

Acked-by: Antonio Fischetti <antonio.fischetti@intel.com>

> -----Original Message-----
> From: Ilya Maximets [mailto:i.maximets@samsung.com]
> Sent: Friday, August 4, 2017 12:38 PM
> To: Fischetti, Antonio <antonio.fischetti@intel.com>; ovs-dev@openvswitch.org
> Cc: Heetae Ahn <heetae82.ahn@samsung.com>; Loftus, Ciara
> <ciara.loftus@intel.com>
> Subject: Re: [ovs-dev] [PATCH v2 1/2] dpif-netdev: Decrease range of values for
> EMC probability.
> 
> Hi Antonio,
> 
> Thanks for review and testing. Comments inline.
> 
> Best regards, Ilya Maximets.
> 
> On 03.08.2017 18:37, Fischetti, Antonio wrote:
> > LGTM,
> > just wondering if a further comment would help,
> > eg something like
> >
> > +/* random_uint32() returns a value in the [0; UINT32_MAX] range.
> > +   For our checking to be correct we would need instead a random value
> > +   in the range [0; UINT32_MAX - 1]. To avoid further computation
> > +   we use a decreased range of available values for 'emc-insert-inv-prob'
> > +   ie [0; 2**20 - 1]. */
> > +#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)
> >
> > ?
> >
> > -Antonio
> 
> I don't think that such a comment will be useful for the reader.
> This is more like explanation why we made this change and it should
> be in commit message (which already has this information).
> 
> In addition, the next patch adds build time assert which will forbid
> using of EM_FLOW_INSERT_INV_PROB_SHIFT higher than 30.
> 
> One thing we may clarify here is why 20 was chosen.
> Something like this:
> 
> /* Set up maximum inverse EMC insertion probability to 2^20 - 1.
>  * Higher values considered useless in practice. */
> 
> What do you think?

[Antonio] yes, sounds good. Thanks.


> 
> >
> >> -----Original Message-----
> >> From: ovs-dev-bounces@openvswitch.org [mailto:ovs-dev-
> bounces@openvswitch.org]
> >> On Behalf Of Ilya Maximets
> >> Sent: Monday, July 31, 2017 3:41 PM
> >> To: ovs-dev@openvswitch.org
> >> Cc: Heetae Ahn <heetae82.ahn@samsung.com>; Ilya Maximets
> >> <i.maximets@samsung.com>
> >> Subject: [ovs-dev] [PATCH v2 1/2] dpif-netdev: Decrease range of values for
> EMC
> >> probability.
> >>
> >> 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@intel.com>
> >> Fixes: 4c30b24602c3 ("dpif-netdev: Conditional EMC insert")
> >> Signed-off-by: Ilya Maximets <i.maximets@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
> >>
> >> _______________________________________________
> >> dev mailing list
> >> dev@openvswitch.org
> >> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
> >
> >
> >

Patch hide | download patch | download mbox

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