From: David Miller <davem@davemloft.net>
To: pablo@netfilter.org
Cc: netfilter-devel@vger.kernel.org, netdev@vger.kernel.org
Subject: Re: [PATCH 0/6] Netfilter updates for net-next
Date: Mon, 27 Jan 2020 10:18:53 +0100 (CET) [thread overview]
Message-ID: <20200127.101853.1471544937358444588.davem@davemloft.net> (raw)
In-Reply-To: <20200127082054.318263-1-pablo@netfilter.org>
From: Pablo Neira Ayuso <pablo@netfilter.org>
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.
next prev parent reply other threads:[~2020-01-27 9:18 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-01-27 8:20 [PATCH 0/6] Netfilter updates for net-next Pablo Neira Ayuso
2020-01-27 8:20 ` [PATCH 1/6] netfilter: nf_tables: add nft_setelem_parse_key() Pablo Neira Ayuso
2020-01-27 8:20 ` [PATCH 2/6] netfilter: nf_tables: add NFTA_SET_ELEM_KEY_END attribute Pablo Neira Ayuso
2020-01-27 8:20 ` [PATCH 3/6] netfilter: nf_tables: Support for sets with multiple ranged fields Pablo Neira Ayuso
2020-01-27 8:20 ` [PATCH 4/6] bitmap: Introduce bitmap_cut(): cut bits and shift remaining Pablo Neira Ayuso
2020-01-27 8:20 ` [PATCH 5/6] nf_tables: Add set type for arbitrary concatenation of ranges Pablo Neira Ayuso
2020-01-27 8:20 ` [PATCH 6/6] selftests: netfilter: Introduce tests for sets with range concatenation Pablo Neira Ayuso
2020-01-27 9:18 ` David Miller [this message]
-- strict thread matches above, loose matches on Subject: below --
2020-04-29 19:42 [PATCH 0/6] Netfilter updates for net-next Pablo Neira Ayuso
2020-04-29 21:15 ` David Miller
2012-12-04 17:31 [PATCH 0/6] netfilter " pablo
2012-12-04 18:02 ` David Miller
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=20200127.101853.1471544937358444588.davem@davemloft.net \
--to=davem@davemloft.net \
--cc=netdev@vger.kernel.org \
--cc=netfilter-devel@vger.kernel.org \
--cc=pablo@netfilter.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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).