> -----Original Message----- > From: Darrell Ball [mailto:db...@vmware.com] > Sent: Friday, August 4, 2017 11:35 AM > To: Ilya Maximets <i.maxim...@samsung.com>; ovs-dev@openvswitch.org > Cc: Heetae Ahn <heetae82....@samsung.com>; Wang, Yipeng1 > <yipeng1.w...@intel.com>; Kevin Traynor <ktray...@redhat.com>; Loftus, > Ciara <ciara.lof...@intel.com>; Fischetti, Antonio > <antonio.fische...@intel.com> > Subject: Re: [PATCH v3 1/2] dpif-netdev: Decrease range of values for EMC > probability. > > > > -----Original Message----- > From: Ilya Maximets <i.maxim...@samsung.com> > Date: Friday, August 4, 2017 at 7:17 AM > To: "ovs-dev@openvswitch.org" <ovs-dev@openvswitch.org> > Cc: Heetae Ahn <heetae82....@samsung.com>, Darrell Ball > <db...@vmware.com>, Yipeng Wang <yipeng1.w...@intel.com>, Kevin > Traynor <ktray...@redhat.com>, Ciara Loftus <ciara.lof...@intel.com>, > Antonio Fischetti <antonio.fische...@intel.com>, Ilya Maximets > <i.maxim...@samsung.com> > Subject: [PATCH v3 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]. > > > I understand the calculation is slightly off. > If the user enters 4,294,967,295 then the probability to insert into emc will > be > 2 out of 4,294,967,295 rather than 1 out of 4,294,967,295, > > However, is there a general concern about such a low probability anyways ? > This max inverse value would be rarely, if ever used and if used, it would be > impossible > to see the difference in any real use case. > > The user might as well just disable emc rather than use such tiny > probabilities. > > This existing api was discussed extensively and was very contentious. > > However, if patch 2 really has an absolute dependency on this patch 1, we > can include it. > I have done various testing and don’t see that, but I have some comments > on the > other threads. > > [Wang, Yipeng] The dependency I can tell is that when do EMC_insert, the random bit is chosen by (random_value >> EM_FLOW_INSERT_INV_PROB_SHIFT & 1) in next patch, which means that the random bit will be "fully independent". If it is the only dependency, I guess it is fine to even not include this patch.
> 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> > Acked-by: Antonio Fischetti <antonio.fische...@intel.com> > --- > > Infrastructure and logic introduced here will be used for fixing > emc replacement policy. > > lib/dpif-netdev.c | 14 ++++++++++---- > vswitchd/vswitch.xml | 3 ++- > 2 files changed, 12 insertions(+), 5 deletions(-) > > diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c > index 8ecc9d1..e23c674 100644 > --- a/lib/dpif-netdev.c > +++ b/lib/dpif-netdev.c > @@ -153,9 +153,14 @@ struct netdev_flow_key { > #define EM_FLOW_HASH_MASK (EM_FLOW_HASH_ENTRIES - 1) > #define EM_FLOW_HASH_SEGS 2 > > +/* Set up maximum inverse EMC insertion probability to 2^20 - 1. > + * Higher values considered useless in practice. */ > +#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 { > @@ -2092,7 +2097,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); > } > } > @@ -2909,8 +2914,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 d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev