From: Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx> Date: Mon, 27 Jan 2020 09:20:48 +0100 > This batch contains Netfilter updates for net-next: > > 1) Add nft_setelem_parse_key() helper function. > > 2) Add NFTA_SET_ELEM_KEY_END to specify a range with one single element. > > 3) Add NFTA_SET_DESC_CONCAT to describe the set element concatenation, > from Stefano Brivio. > > 4) Add bitmap_cut() to copy n-bits from source to destination, > from Stefano Brivio. > > 5) Add set to match on arbitrary concatenations, from Stefano Brivio. > > 6) Add selftest for this new set type. An extract of Stefano's > description follows: > > "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." > > You can pull these changes from: > > git://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git Pulled, thanks Pablo.