From: Stefano Brivio <sbrivio@redhat.com>
To: Pablo Neira Ayuso <pablo@netfilter.org>, netfilter-devel@vger.kernel.org
Cc: "Florian Westphal" <fw@strlen.de>,
"Kadlecsik József" <kadlec@blackhole.kfki.hu>,
"Eric Garver" <eric@garver.life>, "Phil Sutter" <phil@nwl.cc>
Subject: [PATCH nf-next v2 5/8] nft_set_pipapo: Provide unrolled lookup loops for common field sizes
Date: Fri, 22 Nov 2019 14:40:04 +0100 [thread overview]
Message-ID: <8954376b602e231687c7513e461782dc8c781e09.1574428269.git.sbrivio@redhat.com> (raw)
In-Reply-To: <cover.1574428269.git.sbrivio@redhat.com>
For non-vectorised lookup implementations, this increases matching
rates by 20 to 30% for most set types.
Signed-off-by: Stefano Brivio <sbrivio@redhat.com>
---
v2: No changes
net/netfilter/nft_set_pipapo.c | 86 +++++++++++++++++++++++++++++-----
1 file changed, 73 insertions(+), 13 deletions(-)
diff --git a/net/netfilter/nft_set_pipapo.c b/net/netfilter/nft_set_pipapo.c
index 3cad9aedc168..0596dbd11319 100644
--- a/net/netfilter/nft_set_pipapo.c
+++ b/net/netfilter/nft_set_pipapo.c
@@ -526,6 +526,51 @@ static int pipapo_refill(unsigned long *map, int len, int rules,
return ret;
}
+#define NFT_PIPAPO_AND_BUCKET(map, bucket, bsize, idx) \
+ do { \
+ for (idx = 0; idx < (bsize); idx++) \
+ map[idx] &= *((bucket) + idx); \
+ } while (0)
+
+#define NFT_PIPAPO_MATCH_2(map, lt, bsize, pkt, offset, idx) \
+ do { \
+ NFT_PIPAPO_AND_BUCKET(map, \
+ lt + \
+ (offset + 0 + (*pkt >> 4)) * bsize, \
+ bsize, idx); \
+ NFT_PIPAPO_AND_BUCKET(map, \
+ lt + \
+ (offset + 16 + (*pkt & 0x0f)) * bsize, \
+ bsize, idx); \
+ pkt++; \
+ } while (0)
+
+#define NFT_PIPAPO_MATCH_4(map, lt, bsize, pkt, offset, idx) \
+ do { \
+ NFT_PIPAPO_MATCH_2(map, lt, bsize, pkt, offset, idx); \
+ NFT_PIPAPO_MATCH_2(map, lt, bsize, pkt, offset + 2 * 16, idx); \
+ } while (0)
+
+#define NFT_PIPAPO_MATCH_8(map, lt, bsize, pkt, offset, idx) \
+ do { \
+ NFT_PIPAPO_MATCH_4(map, lt, bsize, pkt, offset, idx); \
+ NFT_PIPAPO_MATCH_4(map, lt, bsize, pkt, offset + 4 * 16, idx); \
+ } while (0)
+
+#define NFT_PIPAPO_MATCH_12(map, lt, bsize, pkt, idx) \
+ do { \
+ NFT_PIPAPO_MATCH_8(map, lt, bsize, pkt, 0, idx); \
+ NFT_PIPAPO_MATCH_4(map, lt, bsize, pkt, 8 * 16, idx); \
+ } while (0)
+
+#define NFT_PIPAPO_MATCH_32(map, lt, bsize, pkt, idx) \
+ do { \
+ NFT_PIPAPO_MATCH_8(map, lt, bsize, pkt, 0, idx); \
+ NFT_PIPAPO_MATCH_8(map, lt, bsize, pkt, 8 * 16, idx); \
+ NFT_PIPAPO_MATCH_8(map, lt, bsize, pkt, 16 * 16, idx); \
+ NFT_PIPAPO_MATCH_8(map, lt, bsize, pkt, 24 * 16, idx); \
+ } while (0)
+
/**
* nft_pipapo_lookup() - Lookup function
* @net: Network namespace
@@ -566,24 +611,39 @@ static bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
nft_pipapo_for_each_field(f, i, m) {
bool last = i == m->field_count - 1;
unsigned long *lt = f->lt;
- int b, group;
+ int b, group, j;
/* For each 4-bit group: select lookup table bucket depending on
- * packet bytes value, then AND bucket value
+ * packet bytes value, then AND bucket value. Unroll loops for
+ * the most common cases (protocol, port, IPv4 address, MAC
+ * address, IPv6 address).
*/
- for (group = 0; group < f->groups; group++) {
- u8 v;
+ if (f->groups == 2) {
+ NFT_PIPAPO_MATCH_2(res_map, lt, f->bsize, rp, 0, j);
+ } else if (f->groups == 4) {
+ NFT_PIPAPO_MATCH_4(res_map, lt, f->bsize, rp, 0, j);
+ } else if (f->groups == 8) {
+ NFT_PIPAPO_MATCH_8(res_map, lt, f->bsize, rp, 0, j);
+ } else if (f->groups == 12) {
+ NFT_PIPAPO_MATCH_12(res_map, lt, f->bsize, rp, j);
+ } else if (f->groups == 32) {
+ NFT_PIPAPO_MATCH_32(res_map, lt, f->bsize, rp, j);
+ } else {
+ for (group = 0; group < f->groups; group++) {
+ u8 v;
+
+ if (group % 2) {
+ v = *rp & 0x0f;
+ rp++;
+ } else {
+ v = *rp >> 4;
+ }
+ __bitmap_and(res_map, res_map,
+ lt + v * f->bsize,
+ f->bsize * BITS_PER_LONG);
- if (group % 2) {
- v = *rp & 0x0f;
- rp++;
- } else {
- v = *rp >> 4;
+ lt += f->bsize * NFT_PIPAPO_BUCKETS;
}
- __bitmap_and(res_map, res_map, lt + v * f->bsize,
- f->bsize * BITS_PER_LONG);
-
- lt += f->bsize * NFT_PIPAPO_BUCKETS;
}
/* Now populate the bitmap for the next field, unless this is
--
2.20.1
next prev parent reply other threads:[~2019-11-22 13:40 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-11-22 13:39 [PATCH nf-next v2 0/8] nftables: Set implementation for arbitrary concatenation of ranges Stefano Brivio
2019-11-22 13:40 ` [PATCH nf-next v2 1/8] netfilter: nf_tables: Support for subkeys, set with multiple ranged fields Stefano Brivio
2019-11-23 20:01 ` Pablo Neira Ayuso
2019-11-25 9:30 ` Stefano Brivio
2019-11-25 9:58 ` Pablo Neira Ayuso
2019-11-25 13:26 ` Stefano Brivio
2019-11-25 14:30 ` Pablo Neira Ayuso
2019-11-25 14:54 ` Stefano Brivio
2019-11-25 20:38 ` Pablo Neira Ayuso
2019-11-22 13:40 ` [PATCH nf-next v2 2/8] bitmap: Introduce bitmap_cut(): cut bits and shift remaining Stefano Brivio
2019-11-22 13:40 ` [PATCH nf-next v2 3/8] nf_tables: Add set type for arbitrary concatenation of ranges Stefano Brivio
2019-11-27 9:29 ` Pablo Neira Ayuso
2019-11-27 11:02 ` Stefano Brivio
2019-11-27 18:29 ` Pablo Neira Ayuso
2019-11-22 13:40 ` [PATCH nf-next v2 4/8] selftests: netfilter: Introduce tests for sets with range concatenation Stefano Brivio
2019-11-22 13:40 ` Stefano Brivio [this message]
2019-11-22 13:40 ` [PATCH nf-next v2 6/8] nft_set_pipapo: Prepare for vectorised implementation: alignment Stefano Brivio
2019-11-22 13:40 ` [PATCH nf-next v2 7/8] nft_set_pipapo: Prepare for vectorised implementation: helpers Stefano Brivio
2019-11-22 13:40 ` [PATCH nf-next v2 8/8] nft_set_pipapo: Introduce AVX2-based lookup implementation Stefano Brivio
2019-11-26 6:36 ` kbuild test robot
2019-11-23 20:05 ` [PATCH nf-next v2 0/8] nftables: Set implementation for arbitrary concatenation of ranges Pablo Neira Ayuso
2019-11-25 9:31 ` Stefano Brivio
2019-11-25 10:02 ` Pablo Neira Ayuso
2019-11-25 13:36 ` 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=8954376b602e231687c7513e461782dc8c781e09.1574428269.git.sbrivio@redhat.com \
--to=sbrivio@redhat.com \
--cc=eric@garver.life \
--cc=fw@strlen.de \
--cc=kadlec@blackhole.kfki.hu \
--cc=netfilter-devel@vger.kernel.org \
--cc=pablo@netfilter.org \
--cc=phil@nwl.cc \
/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).