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 <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(&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 > >> d...@openvswitch.org > >> https://mail.openvswitch.org/mailman/listinfo/ovs-dev > > > > > > _______________________________________________ dev mailing list d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev
