From: Pablo Neira Ayuso <firstname.lastname@example.org> To: Stefano Brivio <email@example.com> Cc: firstname.lastname@example.org, "Florian Westphal" <email@example.com>, "Kadlecsik József" <firstname.lastname@example.org>, "Eric Garver" <email@example.com>, "Phil Sutter" <firstname.lastname@example.org> Subject: Re: [PATCH nf-next v4 0/9] nftables: Set implementation for arbitrary concatenation of ranges Date: Mon, 27 Jan 2020 09:20:49 +0100 Message-ID: <20200127082049.2crc2luiw2g235sh@salvia> (raw) In-Reply-To: <email@example.com> 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.
next prev parent reply index Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top 2020-01-21 23:17 Stefano Brivio 2020-01-21 23:17 ` [PATCH nf-next v4 1/9] netfilter: nf_tables: add nft_setelem_parse_key() Stefano Brivio 2020-01-21 23:17 ` [PATCH nf-next v4 2/9] netfilter: nf_tables: add NFTA_SET_ELEM_KEY_END attribute Stefano Brivio 2020-01-21 23:17 ` [PATCH nf-next v4 3/9] netfilter: nf_tables: Support for sets with multiple ranged fields Stefano Brivio 2020-01-21 23:17 ` [PATCH nf-next v4 4/9] bitmap: Introduce bitmap_cut(): cut bits and shift remaining Stefano Brivio 2020-01-21 23:17 ` [PATCH nf-next v4 5/9] nf_tables: Add set type for arbitrary concatenation of ranges Stefano Brivio 2020-02-07 11:23 ` Pablo Neira Ayuso 2020-02-10 15:10 ` Stefano Brivio 2020-02-14 18:16 ` Pablo Neira Ayuso 2020-02-14 19:42 ` Stefano Brivio 2020-02-14 20:42 ` Pablo Neira Ayuso 2020-02-14 23:06 ` Stefano Brivio 2020-01-21 23:17 ` [PATCH nf-next v4 6/9] selftests: netfilter: Introduce tests for sets with range concatenation Stefano Brivio 2020-01-21 23:17 ` [PATCH nf-next v4 7/9] nft_set_pipapo: Prepare for vectorised implementation: alignment Stefano Brivio 2020-01-21 23:17 ` [PATCH nf-next v4 8/9] nft_set_pipapo: Prepare for vectorised implementation: helpers Stefano Brivio 2020-01-21 23:17 ` [PATCH nf-next v4 9/9] nft_set_pipapo: Introduce AVX2-based lookup implementation Stefano Brivio 2020-01-27 6:41 ` kbuild test robot 2020-01-27 8:20 ` Pablo Neira Ayuso [this message] 2020-02-20 10:52 ` [PATCH nf-next v4 0/9] nftables: Set implementation for arbitrary concatenation of ranges Phil Sutter 2020-02-20 11:04 ` Stefano Brivio
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20200127082049.2crc2luiw2g235sh@salvia \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
Netfilter-Devel Archive on lore.kernel.org Archives are clonable: git clone --mirror https://lore.kernel.org/netfilter-devel/0 netfilter-devel/git/0.git # If you have public-inbox 1.1+ installed, you may # initialize and index your mirror using the following commands: public-inbox-init -V2 netfilter-devel netfilter-devel/ https://lore.kernel.org/netfilter-devel \ email@example.com public-inbox-index netfilter-devel Example config snippet for mirrors Newsgroup available over NNTP: nntp://nntp.lore.kernel.org/org.kernel.vger.netfilter-devel AGPL code for this site: git clone https://public-inbox.org/public-inbox.git