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

2017-08-04 Thread Fischetti, Antonio 
My reply inline.

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

> -Original Message-
> From: Ilya Maximets [mailto:i.maxim...@samsung.com]
> Sent: Friday, August 4, 2017 12:38 PM
> To: Fischetti, Antonio <antonio.fische...@intel.com>; ovs-dev@openvswitch.org
> Cc: Heetae Ahn <heetae82@samsung.com>; Loftus, Ciara
> <ciara.lof...@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-boun...@openvswitch.org [mailto:ovs-dev-
> boun...@openvswitch.org]
> >> On Behalf Of Ilya Maximets
> >> Sent: Monday, July 31, 2017 3:41 PM
> >> To: ovs-dev@openvswitch.org
> >> Cc: Heetae Ahn <heetae82@samsung.com>; Ilya Maximets
> >> <i.maxim...@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.lof...@intel.com>
> >> Fixes: 4c30b24602c3 ("dpif-netdev: Conditional EMC insert")
> >> Signed-off-by: Ilya Maximets &

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

2017-08-03 Thread Fischetti, Antonio 
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-boun...@openvswitch.org [mailto:ovs-dev-boun...@openvswitch.org]
> On Behalf Of Ilya Maximets
> Sent: Monday, July 31, 2017 3:41 PM
> To: ovs-dev@openvswitch.org
> Cc: Heetae Ahn <heetae82@samsung.com>; Ilya Maximets
> <i.maxim...@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.lof...@intel.com>
> Fixes: 4c30b24602c3 ("dpif-netdev: Conditional EMC insert")
> Signed-off-by: Ilya Maximets <i.maxim...@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(>dp->emc_insert_min, );
> 
> -if (min && random_uint32() <= min) {
> +if (min && (random_uint32() & EM_FLOW_INSERT_INV_PROB_MASK) < min) {
>  emc_insert(>flow_cache, key, flow);
>  }
>  }
> @@ -2894,8 +2897,9 @@ dpif_netdev_set_config(struct dpif *dpif, const struct
> smap *other_config)
>  }
> 
>  atomic_read_relaxed(>emc_insert_min, _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) {
> +ins

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

2017-07-31 Thread Ilya Maximets 
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 
Fixes: 4c30b24602c3 ("dpif-netdev: Conditional EMC insert")
Signed-off-by: Ilya Maximets 
---

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(>dp->emc_insert_min, );
 
-if (min && random_uint32() <= min) {
+if (min && (random_uint32() & EM_FLOW_INSERT_INV_PROB_MASK) < min) {
 emc_insert(>flow_cache, key, flow);
 }
 }
@@ -2894,8 +2897,9 @@ dpif_netdev_set_config(struct dpif *dpif, const struct 
smap *other_config)
 }
 
 atomic_read_relaxed(>emc_insert_min, _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 @@
   
 
   
+  type='{"type": "integer",
+ "minInteger": 0, "maxInteger": 1048575}'>
 
   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
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev