On Wed, Jan 22, 2020 at 12:17:50AM +0100, Stefano Brivio wrote: > Existing nftables set implementations allow matching entries with > interval expressions (rbtree), e.g. 192.0.2.1-192.0.2.4, entries > specifying field concatenation (hash, rhash), e.g. 192.0.2.1:22, > but not both. > > In other words, none of the set types allows matching on range > expressions for more than one packet field at a time, such as ipset > does with types bitmap:ip,mac, and, to a more limited extent > (netmasks, not arbitrary ranges), with types hash:net,net, > hash:net,port, hash:ip,port,net, and hash:net,port,net. > > As a pure hash-based approach is unsuitable for matching on ranges, > and "proxying" the existing red-black tree type looks impractical as > elements would need to be shared and managed across all employed > trees, this new set implementation intends to fill the functionality > gap by employing a relatively novel approach. > > The fundamental idea, illustrated in deeper detail in patch 5/9, is to > use lookup tables classifying a small number of grouped bits from each > field, and map the lookup results in a way that yields a verdict for > the full set of specified fields. > > The grouping bit aspect is loosely inspired by the Grouper algorithm, > by Jay Ligatti, Josh Kuhn, and Chris Gage (see patch 5/9 for the full > reference). > > A reference, stand-alone implementation of the algorithm itself is > available at: > https://pipapo.lameexcu.se > > Some notes about possible future optimisations are also mentioned > there. This algorithm reduces the matching problem to, essentially, > a repetitive sequence of simple bitwise operations, and is > particularly suitable to be optimised by leveraging SIMD instruction > sets. An AVX2-based implementation is also presented in this series. > > I plan to post the adaptation of the existing AVX2 vectorised > implementation for (at least) NEON at a later time. > > Patches 1/9 to 3/9 implement the needed infrastructure: new > attributes are used to describe length of single ranged fields in > concatenations and to denote the upper bound for ranges. > > Patch 4/9 adds a new bitmap operation that copies the source bitmap > onto the destination while removing a given region, and is needed to > delete regions of arrays mapping between lookup tables. > > Patch 5/9 is the actual set implementation. > > Patch 6/9 introduces selftests for the new implementation. Applied up to 6/9. Merge window will close soon and I'm going to be a bit defensive and take only the batch that include the initial implementation. I would prefer if we all use this round to start using the C implementation upstream and report bugs. While I have received positive feedback from other fellows meanwhile privately, this batch is large and I'm inclined to follow this approach. Please, don't be disappointed, and just follow up with more patches once merge window opens up again. Thanks.
