> -----Original Message----- > From: Medvedkin, Vladimir <vladimir.medved...@intel.com> > Sent: Tuesday, April 6, 2021 12:51 PM > To: dev@dpdk.org > Cc: Ananyev, Konstantin <konstantin.anan...@intel.com>; Chilikin, Andrey > <andrey.chili...@intel.com>; Kinsella, Ray <ray.kinse...@intel.com>; Wang, > Yipeng1 <yipeng1.w...@intel.com>; Gobriel, Sameh > <sameh.gobr...@intel.com>; Richardson, Bruce > <bruce.richard...@intel.com> > Subject: [PATCH v2 0/3] Predictable RSS feature > > This patch series introduces predictable RSS feature. > It is based on the idea of searching for partial hash collisions within > Toeplitz > hash. > > The Toeplitz hash function is a homomorphism between (G, ^) and (H, ^), > where (G, ^) - is a group of tuples and (H, ^) is a group of hashes with > respect > to XOR operation. So tuples and hashes could be treated as n-dimension and > 32-dimension vector spaces over GF(2). > So, f(x ^ y) == f(x) ^ f(y) > where f - is the toeplitz hash function and x, y are tuples. > > The ability to predict partial collisions allows user to compute input hash > value > with desired LSB values. > Usually number of LSB's are defined by the size of RSS Redirection Table. > > There could be number of use cases, for example: > 1) NAT. Using this library it is possible to select a new port number on a > translation in the way that rss hash for original tuple will have the same > LSB's > as rss hash for reverse tuple. > 2) IPSec/MPLS/Vxlan. It is possible to choose tunnel id to be pinned to a > desired queue. > 3) TCP stack. It is possible to choose a source port number for outgoing > connections in the way that received replies will be assigned to desired > queue. > 4) RSS hash key generation. Hash key initialization with random values does > not guarantee an uniform distribution amongst queues. This library uses > mathematically proved algorithm to complete the rss hash key to provide the > best distribution. > > v2: > - added extra API rte_thash_adjust_tuple() > - added extra tests for rte_thash_adjust_tuple() > - added extra fields to rte_thash_subtuple_helper struct > - fixed typos > > Vladimir Medvedkin (3): > hash: add predictable RSS API > hash: add predictable RSS implementation > test/hash: add additional thash tests > > app/test/test_thash.c | 468 +++++++++++++++++++++++++++++++- > lib/librte_hash/meson.build | 3 +- > lib/librte_hash/rte_thash.c | 637 > ++++++++++++++++++++++++++++++++++++++++++++ > lib/librte_hash/rte_thash.h | 180 +++++++++++++ > lib/librte_hash/version.map | 8 + > 5 files changed, 1289 insertions(+), 7 deletions(-) create mode 100644 > lib/librte_hash/rte_thash.c > > -- > 2.7.4
[Wang, Yipeng] Hi, Vladimir, thanks for the patch! I haven't fully understood every bit of the algorithm yet, but I did see issues that this patch could potentially solve. My understanding is that there are some restrictions for the current implementation, for example, it only supports port(16-bit) manipulation, but not multiple fields or IP. Still, I think it should be good for the use cases you listed. I would love to hear more feedbacks from people who are more familiar with doing NAT in production systems. For me, besides the comments I sent earlier, good documentation and references are needed with clear usage examples, as others pointed out already. Also, the current API design seems a bit cumbersome. To use the library, one needs: Init_ctx Add_helper. Get_helper Get_complement Then in a loop: Adjust_tuples Then XOR with the current tuple I wonder if an alternative all-in-one API could be designed for simpler use cases. Thanks!
