src: Optimize prefix matches on byte-boundaries
Phil Sutter
reviewercover src: Optimize prefix matches on byte-boundaries
This mini-series optimizes prefix matches to skip the "bitwise" expression if they are byte-bound. We can simply reduce "cmp" expression length to achieve the same effect.
The first patch adds support for delinearization, this enables correct display of the IP address prefix matches added by iptables-nft with my (not yet accepted) patch applied.
The second patch enables nft to create such bytecode itself.
Phil Sutter (2):
src: Support odd-sized payload matches
src: Optimize prefix matches on byte-boundaries
src/netlink_delinearize.c | 11 +++++++++-- src/netlink_linearize.c | 4 +++- src/payload.c | 5 +++++ tests/py/ip/ct.t.payload | 4 ---- tests/py/ip/ip.t.payload | 6 ++---- tests/py/ip/ip.t.payload.bridge | 6 ++---- tests/py/ip/ip.t.payload.inet | 6 ++---- tests/py/ip/ip.t.payload.netdev | 6 ++---- tests/py/ip6/ip6.t.payload.inet | 5 ++--- tests/py/ip6/ip6.t.payload.ip6 | 5 ++--- 10 files changed, 29 insertions(+), 29 deletions(-)
Signature · 1 line
2.28.0
Phil Sutter
reviewerPATCH 1/2 src: Support odd-sized payload matches
When expanding a payload match, don't disregard oversized templates at the right offset. A more flexible user may extract less bytes from the packet if only parts of a field are interesting, e.g. only the prefix of source/destination address. Support that by using the template, but fix the length. Later when creating a relational expression for it, detect the unusually small payload expression length and turn the RHS value into a prefix expression.
--- src/netlink_delinearize.c | 6 ++++++ src/payload.c | 5 +++++ 2 files changed, 11 insertions(+)
src/netlink_delinearize.c +6 -0
@@ -1776,6 +1776,12 @@ static void payload_match_expand(struct rule_pp_ctx *ctx, tmp =constant_expr_splice (right, left->len);expr_set_type (tmp, left->dtype, left->byteorder); +if (left->payload.tmpl && (left->len < left->payload.tmpl->len)) { +mpz_lshift_ui (tmp->value, left->payload.tmpl->len - left->len); + tmp->len = left->payload.tmpl->len; + tmp =prefix_expr_alloc (&tmp->location, tmp, left->len); + } + nexpr =relational_expr_alloc (&expr->location, expr->op, left, tmp);if (expr->op ==OP_EQ )
src/payload.c +5 -0
@@ -822,6 +822,11 @@ void payload_expr_expand(struct list_head *list, struct expr *expr, expr->payload.offset += tmpl->len;if (expr->len ==0 )return ; + }else if (expr->len >0 ) { + new =payload_expr_alloc (&expr->location, desc, i); + new->len = expr->len; +list_add_tail (&new->list, list); +return ; }else break ; }
Signature · 1 line
2.28.0
Phil Sutter
reviewerPATCH 2/2 src: Optimize prefix matches on byte-boundaries
In reply to Phil SutterIf a prefix expression's length is on a byte-boundary, it is sufficient to just reduce the length passed to "cmp" expression. No need for explicit bitwise modification of data on LHS. The relevant code is already there, used for string prefix matches. There is one exception though, namely zero-length prefixes: Kernel doesn't accept zero-length "cmp" expressions, so keep them in the old code-path for now.
This patch depends upon the previous one to correctly parse odd-sized payload matches but has to extend support for non-payload LHS as well. In practice, this is needed for "ct" expressions as they allow matching against IP address prefixes, too.
--- src/netlink_delinearize.c | 5 +++-- src/netlink_linearize.c | 4 +++- tests/py/ip/ct.t.payload | 4 ---- tests/py/ip/ip.t.payload | 6 ++---- tests/py/ip/ip.t.payload.bridge | 6 ++---- tests/py/ip/ip.t.payload.inet | 6 ++---- tests/py/ip/ip.t.payload.netdev | 6 ++---- tests/py/ip6/ip6.t.payload.inet | 5 ++--- tests/py/ip6/ip6.t.payload.ip6 | 5 ++--- 9 files changed, 18 insertions(+), 29 deletions(-)
src/netlink_delinearize.c +3 -2
@@ -322,8 +322,9 @@ static void netlink_parse_cmp(struct netlink_parse_ctx *ctx,if (left->len > right->len &&expr_basetype (left) != &string_type) { -netlink_error (ctx, loc,"Relational expression size mismatch" ); - goto err_free; +mpz_lshift_ui (right->value, left->len - right->len); + right =prefix_expr_alloc (loc, right, right->len); + right->prefix->len = left->len; }else if (left->len >0 && left->len < right->len) {expr_free (left); left =netlink_parse_concat_expr (ctx, loc, sreg, right->len);
src/netlink_linearize.c +3 -1
@@ -533,7 +533,9 @@ static void netlink_gen_relational(struct netlink_linearize_ctx *ctx,return netlink_gen_flagcmp (ctx, expr, dreg);case EXPR_PREFIX : sreg =get_register (ctx, expr->left); -if (expr_basetype (expr->left)->type !=TYPE_STRING ) { +if (expr_basetype (expr->left)->type !=TYPE_STRING && + (!expr->right->prefix_len || + expr->right->prefix_len %BITS_PER_BYTE )) { len =div_round_up (expr->right->len,BITS_PER_BYTE );netlink_gen_expr (ctx, expr->left, sreg); right =netlink_gen_prefix (ctx, expr, sreg);
tests/py/ip/ct.t.payload +0 -4
@@ -21,25 +21,21 @@ ip test-ip4 output # ct original ip saddr 192.168.1.0/24 ip test-ip4 output [ ct load src_ip => reg 1 , dir original ] - [ bitwise reg 1 = (reg=1 & 0x00ffffff ) ^ 0x00000000 ] [ cmp eq reg 1 0x0001a8c0 ] # ct reply ip saddr 192.168.1.0/24 ip test-ip4 output [ ct load src_ip => reg 1 , dir reply ] - [ bitwise reg 1 = (reg=1 & 0x00ffffff ) ^ 0x00000000 ] [ cmp eq reg 1 0x0001a8c0 ] # ct original ip daddr 192.168.1.0/24 ip test-ip4 output [ ct load dst_ip => reg 1 , dir original ] - [ bitwise reg 1 = (reg=1 & 0x00ffffff ) ^ 0x00000000 ] [ cmp eq reg 1 0x0001a8c0 ] # ct reply ip daddr 192.168.1.0/24 ip test-ip4 output [ ct load dst_ip => reg 1 , dir reply ] - [ bitwise reg 1 = (reg=1 & 0x00ffffff ) ^ 0x00000000 ] [ cmp eq reg 1 0x0001a8c0 ] # ct l3proto ipv4
tests/py/ip/ip.t.payload +2 -4
@@ -358,14 +358,12 @@ ip test-ip4 input # ip saddr 192.168.2.0/24 ip test-ip4 input - [ payload load 4b @ network header + 12 => reg 1 ] - [ bitwise reg 1 = (reg=1 & 0x00ffffff ) ^ 0x00000000 ] + [ payload load 3b @ network header + 12 => reg 1 ] [ cmp eq reg 1 0x0002a8c0 ] # ip saddr != 192.168.2.0/24 ip test-ip4 input - [ payload load 4b @ network header + 12 => reg 1 ] - [ bitwise reg 1 = (reg=1 & 0x00ffffff ) ^ 0x00000000 ] + [ payload load 3b @ network header + 12 => reg 1 ] [ cmp neq reg 1 0x0002a8c0 ] # ip saddr 192.168.3.1 ip daddr 192.168.3.100
tests/py/ip/ip.t.payload.bridge +2 -4
@@ -466,16 +466,14 @@ bridge test-bridge input bridge test-bridge input [ meta load protocol => reg 1 ] [ cmp eq reg 1 0x00000008 ] - [ payload load 4b @ network header + 12 => reg 1 ] - [ bitwise reg 1 = (reg=1 & 0x00ffffff ) ^ 0x00000000 ] + [ payload load 3b @ network header + 12 => reg 1 ] [ cmp eq reg 1 0x0002a8c0 ] # ip saddr != 192.168.2.0/24 bridge test-bridge input [ meta load protocol => reg 1 ] [ cmp eq reg 1 0x00000008 ] - [ payload load 4b @ network header + 12 => reg 1 ] - [ bitwise reg 1 = (reg=1 & 0x00ffffff ) ^ 0x00000000 ] + [ payload load 3b @ network header + 12 => reg 1 ] [ cmp neq reg 1 0x0002a8c0 ] # ip saddr 192.168.3.1 ip daddr 192.168.3.100
tests/py/ip/ip.t.payload.inet +2 -4
@@ -466,16 +466,14 @@ inet test-inet input inet test-inet input [ meta load nfproto => reg 1 ] [ cmp eq reg 1 0x00000002 ] - [ payload load 4b @ network header + 12 => reg 1 ] - [ bitwise reg 1 = (reg=1 & 0x00ffffff ) ^ 0x00000000 ] + [ payload load 3b @ network header + 12 => reg 1 ] [ cmp eq reg 1 0x0002a8c0 ] # ip saddr != 192.168.2.0/24 inet test-inet input [ meta load nfproto => reg 1 ] [ cmp eq reg 1 0x00000002 ] - [ payload load 4b @ network header + 12 => reg 1 ] - [ bitwise reg 1 = (reg=1 & 0x00ffffff ) ^ 0x00000000 ] + [ payload load 3b @ network header + 12 => reg 1 ] [ cmp neq reg 1 0x0002a8c0 ] # ip saddr 192.168.3.1 ip daddr 192.168.3.100
tests/py/ip/ip.t.payload.netdev +2 -4
@@ -379,16 +379,14 @@ netdev test-netdev ingress netdev test-netdev ingress [ meta load protocol => reg 1 ] [ cmp eq reg 1 0x00000008 ] - [ payload load 4b @ network header + 12 => reg 1 ] - [ bitwise reg 1 = (reg=1 & 0x00ffffff ) ^ 0x00000000 ] + [ payload load 3b @ network header + 12 => reg 1 ] [ cmp eq reg 1 0x0002a8c0 ] # ip saddr != 192.168.2.0/24 netdev test-netdev ingress [ meta load protocol => reg 1 ] [ cmp eq reg 1 0x00000008 ] - [ payload load 4b @ network header + 12 => reg 1 ] - [ bitwise reg 1 = (reg=1 & 0x00ffffff ) ^ 0x00000000 ] + [ payload load 3b @ network header + 12 => reg 1 ] [ cmp neq reg 1 0x0002a8c0 ] # ip saddr 192.168.3.1 ip daddr 192.168.3.100
tests/py/ip6/ip6.t.payload.inet +2 -3
@@ -604,9 +604,8 @@ inet test-inet input inet test-inet input [ meta load nfproto => reg 1 ] [ cmp eq reg 1 0x0000000a ] - [ payload load 16b @ network header + 8 => reg 1 ] - [ bitwise reg 1 = (reg=1 & 0xffffffff 0xffffffff 0x00000000 0x00000000 ) ^ 0x00000000 0x00000000 0x00000000 0x00000000 ] - [ cmp eq reg 1 0x00000000 0x00000000 0x00000000 0x00000000 ] + [ payload load 8b @ network header + 8 => reg 1 ] + [ cmp eq reg 1 0x00000000 0x00000000 ] # ip6 saddr ::1 ip6 daddr ::2 inet test-inet input
tests/py/ip6/ip6.t.payload.ip6 +2 -3
@@ -452,9 +452,8 @@ ip6 test-ip6 input # ip6 saddr ::/64 ip6 test-ip6 input - [ payload load 16b @ network header + 8 => reg 1 ] - [ bitwise reg 1 = (reg=1 & 0xffffffff 0xffffffff 0x00000000 0x00000000 ) ^ 0x00000000 0x00000000 0x00000000 0x00000000 ] - [ cmp eq reg 1 0x00000000 0x00000000 0x00000000 0x00000000 ] + [ payload load 8b @ network header + 8 => reg 1 ] + [ cmp eq reg 1 0x00000000 0x00000000 ] # ip6 saddr ::1 ip6 daddr ::2 ip6 test-ip6 input
Signature · 1 line
2.28.0
Pablo Neira Ayuso
maintainerQuoted 9 lines · Phil Sutter
This mini-series optimizes prefix matches to skip the "bitwise" expression if they are byte-bound. We can simply reduce "cmp" expression length to achieve the same effect.
The first patch adds support for delinearization, this enables correct display of the IP address prefix matches added by iptables-nft with my (not yet accepted) patch applied.
The second patch enables nft to create such bytecode itself.
Patches LGTM, thanks.