<!DOCTYPE html><html><head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> </head> <body> Hi Stephen, <div class="moz-cite-prefix">On 17/10/2024 04:23, Stephen Hemminger wrote: </div> <blockquote type="cite" cite="mid:20241016202344.000c00f1@hermes.local"> <pre class="moz-quote-pre" wrap="">On Wed, 16 Oct 2024 17:28:17 +0100 "Medvedkin, Vladimir" <a class="moz-txt-link-rfc2396E" href="mailto:vladimir.medvedkin@intel.com"><vladimir.medvedkin@intel.com></a> wrote: </pre> <blockquote type="cite"> <pre class="moz-quote-pre" wrap="">Hi Stephen, On 15/10/2024 23:29, Stephen Hemminger wrote: </pre> <blockquote type="cite"> <pre class="moz-quote-pre" wrap="">On Fri, 11 Oct 2024 18:17:00 +0000 Vladimir Medvedkin<a class="moz-txt-link-rfc2396E" href="mailto:vladimir.medvedkin@intel.com"><vladimir.medvedkin@intel.com></a> wrote: </pre> <blockquote type="cite"> <pre class="moz-quote-pre" wrap="">+ +uint32_t +rte_thash_get_rand_poly(uint32_t poly_degree) +{ + uint32_t ret_poly; + + if (poly_degree > 32) </pre> </blockquote> </blockquote> </blockquote> <pre class="moz-quote-pre" wrap=""> Error log here? </pre> <blockquote type="cite"> <blockquote type="cite"> <blockquote type="cite"> <pre class="moz-quote-pre" wrap="">+ return 0; + + do + ret_poly = __thash_get_rand_poly(poly_degree); + while (thash_test_poly_order(ret_poly, poly_degree)); </pre> </blockquote> <pre class="moz-quote-pre" wrap="">Unbounded loop adds some risk, should there be an upper limit on retries. </pre> </blockquote> <pre class="moz-quote-pre" wrap=""> Thisis the probabilisticpartof the algorithm. __thash_get_rand_poly() returns a random polynomial that either satisfies the order criteria (element <x> of the field must generate multiplicative subgroup of order not less than some number), or not. The probability that it does not meet this criteria is strictly less than 1. Thus, with each attempt, the probability of not finding suitable polynomial exponentially tends to zero. </pre> </blockquote> <pre class="moz-quote-pre" wrap=""> Never trust probabilities to converge. Just add an upper bound of something big like 32 tries and log error and give up.</pre> </blockquote> I disagree. I don't want this to give up. Take a look at this algorithm from the perspective of an equivalent bounded random function: <a aria-label="Link https://lxr.missinglinkelectronics.com/dpdk/lib/eal/common/rte_random.c#L171" id="menur73" href="https://lxr.missinglinkelectronics.com/dpdk/lib/eal/common/rte_random.c#L171" rel="noreferrer noopener" target="_blank" class="fui-Link ___1q1shib f2hkw1w f3rmtva f1ewtqcl fyind8e f1k6fduh f1w7gpdv fk6fouc fjoy568 figsok6 f1s184ao f1mk8lai fnbmjn9 f1o700av f13mvf36 f1cmlufx f9n3di6 f1ids18y f1tx3yz7 f1deo86v f1eh06m1 f1iescvh fhgqx19 f1olyrje f1p93eir f1nev41a f1h8hb77 f1lqvz6u f10aw75t fsle3fq f17ae5zn moz-txt-link-freetext" title="https://lxr.missinglinkelectronics.com/dpdk/lib/eal/common/rte_random.c#l171">https://lxr.missinglinkelectronics.com/dpdk/lib/eal/common/rte_random.c#L171</a> or <a class="moz-txt-link-freetext" href="https://elixir.bootlin.com/linux/v6.11.3/source/include/linux/random.h#L60">https://elixir.bootlin.com/linux/v6.11.3/source/include/linux/random.h#L60</a> The job must be done. Imagine if these random functions may return something like "EAGAIN". The caller needs random value at this point to continue, so there are only 2 options left - either panic or call the function again. We definitely don't want to panic here. But calling this algorithm again will have the same effect as not having runtime bound inside the algorithm at all. In other words, here I prefer to have "Las Vegas" rather than "Monte Carlo" algorithm. And it make sense since in these particular cases (i.e. my algorithm and bounded random implementations) we have: 1. A simple deterministic algorithm for checking the compliance of some random variable with a condition 2. Every random variable is independent from each other. So probability of getting unsatisfying random variable after n steps drops exponentially (negative outcome probabilities multiplies). That's why those algorithms runtime expected value is bounded. <blockquote type="cite" cite="mid:20241016202344.000c00f1@hermes.local"> <pre class="moz-quote-pre" wrap=""> </pre> <blockquote type="cite"> <pre class="moz-quote-pre" wrap=""> </pre> <blockquote type="cite"> <pre class="moz-quote-pre" wrap=""> </pre> <blockquote type="cite"> <pre class="moz-quote-pre" wrap="">+ + return ret_poly; +} diff --git a/lib/hash/version.map b/lib/hash/version.map index 4f13f1d5aa..7ce6ab1121 100644 --- a/lib/hash/version.map +++ b/lib/hash/version.map @@ -61,4 +61,5 @@ INTERNAL { rte_thash_gfni_stub; rte_thash_gfni_bulk_stub; + rte_thash_get_rand_poly; </pre> </blockquote> <pre class="moz-quote-pre" wrap="">Why does this function need to be moved to its own file? Only used in one place in rte_thash.c. </pre> </blockquote> <pre class="moz-quote-pre" wrap="">It was done just for convenience. If you insist, I'll move it to rte_thash.c </pre> </blockquote> <pre class="moz-quote-pre" wrap=""> It is actually good to put in seperate file, but you can keep the old name. Best to reserve names with rte_ prefix for user visible prefixes. </pre> </blockquote> <pre class="moz-signature" cols="72">-- Regards, Vladimir</pre> </body> </html>