netfilter-devel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
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.

  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).