[0/6] Netfilter updates for net-next

Hi,

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

Thank you.

----------------------------------------------------------------

The following changes since commit 32efcc06d2a15fa87585614d12d6c2308cc2d3f3:

  tcp: export count for rehash attempts (2020-01-26 15:28:47 +0100)

are available in the git repository at:

  git://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git HEAD

for you to fetch changes up to 611973c1e06faef31d034deeb3ae7b7960b1f043:

  selftests: netfilter: Introduce tests for sets with range concatenation (2020-01-27 08:54:30 +0100)

----------------------------------------------------------------
Pablo Neira Ayuso (2):
      netfilter: nf_tables: add nft_setelem_parse_key()
      netfilter: nf_tables: add NFTA_SET_ELEM_KEY_END attribute

Stefano Brivio (4):
      netfilter: nf_tables: Support for sets with multiple ranged fields
      bitmap: Introduce bitmap_cut(): cut bits and shift remaining
      nf_tables: Add set type for arbitrary concatenation of ranges
      selftests: netfilter: Introduce tests for sets with range concatenation

 include/linux/bitmap.h                             |    4 +
 include/net/netfilter/nf_tables.h                  |   22 +-
 include/net/netfilter/nf_tables_core.h             |    1 +
 include/uapi/linux/netfilter/nf_tables.h           |   17 +
 lib/bitmap.c                                       |   66 +
 net/netfilter/Makefile                             |    3 +-
 net/netfilter/nf_tables_api.c                      |  260 ++-
 net/netfilter/nf_tables_set_core.c                 |    2 +
 net/netfilter/nft_dynset.c                         |    2 +-
 net/netfilter/nft_set_pipapo.c                     | 2102 ++++++++++++++++++++
 net/netfilter/nft_set_rbtree.c                     |    3 +
 tools/testing/selftests/netfilter/Makefile         |    3 +-
 .../selftests/netfilter/nft_concat_range.sh        | 1481 ++++++++++++++
 13 files changed, 3896 insertions(+), 70 deletions(-)
 create mode 100644 net/netfilter/nft_set_pipapo.c
 create mode 100755 tools/testing/selftests/netfilter/nft_concat_range.sh

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.