Skip to contentSkip to conversation

netfilter: nf_tables: restrict expression reduction to first expression

PATCH Superseded Pablo Neira Ayuso 3 participants 11 messages May 18, 2022

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

PATCH 1/1 netfilter: nf_tables: restrict expression reduction to first expression

Either userspace or kernelspace need to pre-fetch keys inconditionally before comparisons for this to work. Otherwise, register tracking data is misleading and it might result in reducing expressions which are not yet registers.

First expression is guaranteed to be evaluated always, therefore, keep tracking registers and restrict reduction to first expression.

Fixes b2d306542ff9 ("netfilter: nf_tables: do not reduce read-only expressions")

---
@Phil, you mentioned about a way to simplify this patch, I don't see how, just let me know.

 net/netfilter/nf_tables_api.c | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)
net/netfilter/nf_tables_api.c +9 -2
index 16c3a39689f4..2c82fecc4094 100644
@@ -8362,6 +8362,7 @@ static int nf_tables_commit_chain_prepare(struct net *net, struct nft_chain *cha
 	void *data, *data_boundary;
 	struct nft_rule_dp *prule;
 	struct nft_rule *rule;
+	bool reduce;
 
 	/* already handled or inactive chain? */
 	if (chain->blob_next || !nft_is_active_next(net, chain))
@@ -8398,12 +8399,18 @@ static int nf_tables_commit_chain_prepare(struct net *net, struct nft_chain *cha
 
 		size = 0;
 		track.last = nft_expr_last(rule);
+		reduce = true;
 		nft_rule_for_each_expr(expr, last, rule) {
 			track.cur = expr;
 
 			if (nft_expr_reduce(&track, expr)) {
-				expr = track.cur;
-				continue;
+				if (reduce) {
+					reduce = false;
+					expr = track.cur;
+					continue;
+				}
+			} else if (reduce) {
+				reduce = false;
 			}
 
 			if (WARN_ON_ONCE(data + expr->ops->size > data_boundary))
Signature · 1 line
2.30.2
reviewer
#1 lore raw

Hi,

Quoted 5 lines · Pablo Neira Ayuso

Either userspace or kernelspace need to pre-fetch keys inconditionally before comparisons for this to work. Otherwise, register tracking data is misleading and it might result in reducing expressions which are not yet registers.

Quoted 8 lines

First expression is guaranteed to be evaluated always, therefore, keep tracking registers and restrict reduction to first expression.

Fixes b2d306542ff9 ("netfilter: nf_tables: do not reduce read-only expressions")

---
@Phil, you mentioned about a way to simplify this patch, I don't see how, just let me know.

Not a big one. Instead of:

|	if (nft_expr_reduce(&track, expr)) {
|		if (reduce) {
|			reduce = false;
|			expr = track.cur;
|			continue;
|		}
|	} else if (reduce) {
|		reduce = false;
|	}

One could do:

|	if (nft_expr_reduce(&track, expr) && reduce) {
|		reduce = false;
|		expr = track.cur;
|		continue;
|	}
|	reduce = false;

Regarding later pre-fetching, one should distinguish between expressions that (may) set verdict register and those that don't. There are pitfalls though, e.g. error conditions handled that way.

Maybe introduce a new nft_expr_type field and set reduce like so:

| reduce = reduce && expr->ops->type->reduce;

Cheers, Phil

author maintainer
#2 lore raw
Quoted 29 lines · Phil Sutter

Hi,

Quoted 5 lines · Pablo Neira Ayuso

Either userspace or kernelspace need to pre-fetch keys inconditionally before comparisons for this to work. Otherwise, register tracking data is misleading and it might result in reducing expressions which are not yet registers.

Quoted 8 lines

First expression is guaranteed to be evaluated always, therefore, keep tracking registers and restrict reduction to first expression.

Fixes b2d306542ff9 ("netfilter: nf_tables: do not reduce read-only expressions")

---
@Phil, you mentioned about a way to simplify this patch, I don't see how, just let me know.

Not a big one. Instead of:

|	if (nft_expr_reduce(&track, expr)) {
|		if (reduce) {
|			reduce = false;
|			expr = track.cur;
|			continue;
|		}
|	} else if (reduce) {
|		reduce = false;
|	}
Quoted 8 lines

One could do:

|	if (nft_expr_reduce(&track, expr) && reduce) {
|		reduce = false;
|		expr = track.cur;
|		continue;
|	}
|	reduce = false;

I'll send v2 using this idiom.

Quoted 7 lines

Regarding later pre-fetching, one should distinguish between expressions that (may) set verdict register and those that don't. There are pitfalls though, e.g. error conditions handled that way.

Maybe introduce a new nft_expr_type field and set reduce like so:

| reduce = reduce && expr->ops->type->reduce;

Could you elaborate?

reviewer
#3 lore raw
Quoted 45 lines · Pablo Neira Ayuso
Quoted 29 lines · Phil Sutter

Hi,

Quoted 5 lines · Pablo Neira Ayuso

Either userspace or kernelspace need to pre-fetch keys inconditionally before comparisons for this to work. Otherwise, register tracking data is misleading and it might result in reducing expressions which are not yet registers.

Quoted 8 lines

First expression is guaranteed to be evaluated always, therefore, keep tracking registers and restrict reduction to first expression.

Fixes b2d306542ff9 ("netfilter: nf_tables: do not reduce read-only expressions")

---
@Phil, you mentioned about a way to simplify this patch, I don't see how, just let me know.

Not a big one. Instead of:

|	if (nft_expr_reduce(&track, expr)) {
|		if (reduce) {
|			reduce = false;
|			expr = track.cur;
|			continue;
|		}
|	} else if (reduce) {
|		reduce = false;
|	}
Quoted 8 lines

One could do:

|	if (nft_expr_reduce(&track, expr) && reduce) {
|		reduce = false;
|		expr = track.cur;
|		continue;
|	}
|	reduce = false;

I'll send v2 using this idiom.

Quoted 4 lines

Regarding later pre-fetching, one should distinguish between expressions that (may) set verdict register and those that don't. There are pitfalls though, e.g. error conditions handled that way.

Quoted 5 lines
Quoted 3 lines

Maybe introduce a new nft_expr_type field and set reduce like so:

| reduce = reduce && expr->ops->type->reduce;

Could you elaborate?

Well, an expression which may set verdict register to NFT_BREAK should prevent reduction of later expressions in same rule as it may stop rule evaluation at run-time. This is obvious for nft_cmp, but nft_meta is also a candidate: NFT_META_IFTYPE causes NFT_BREAK if pkt->skb->dev is NULL. The optimizer must not assume later expressions are evaluated.

A first step might be said nft_expr_type field indicating a given expression might stop expression evaluation. Therefore:

| reduce = reduce && expr->ops->type->reduce;

would continue expression reduction if not already stopped and the current expression doesn't end it.

Taking nft_meta as example again:

* Behaviour changes based on nft_expr_type::select_ops result
* Some keys are guaranteed to not stop expression evaluation:
NFT_META_LEN for instance will always just fetch skb->len. So introduce a callback instead:

| bool nft_expr_ops::may_break(const struct nft_expr *expr);

Then "ask" the expression whether it may change verdict register:

| reduce = reduce && expr->ops->may_break(expr);

With nft_meta_get_ops, we'd have:

| bool nft_meta_get_may_break(const struct nft_expr *expr)
| {
| 	switch (nft_expr_priv(expr)->key) {
| 	case NFT_META_LEN:
| 	case NFT_META_PROTOCOL::
| 	[...]
| 		return false;
| 	case NFT_META_IFTYPE:
| 	[...]
| 		return true;
| 	}
| }

Another thing about your proposed patch: Expressions may update registers even if not reduced. Could that upset later reduction decision? E.g.:

| ip saddr 1.0.0.1 ip daddr 2.0.0.2 accept
| ip daddr 3.0.0.3 accept

Code no longer allows the first rule's 'ip daddr' expression to be reduced (no matter what's in registers already), but it's existence causes reduction of the second rule's 'ip daddr' expression, right?

Cheers, Phil

maintainer
#4 lore raw
Quoted 9 lines · Phil Sutter
Quoted 3 lines
Quoted 1 line

| reduce = reduce && expr->ops->type->reduce;

Could you elaborate?

Well, an expression which may set verdict register to NFT_BREAK should prevent reduction of later expressions in same rule as it may stop rule evaluation at run-time. This is obvious for nft_cmp, but nft_meta is also a candidate: NFT_META_IFTYPE causes NFT_BREAK if pkt->skb->dev is NULL. The optimizer must not assume later expressions are evaluated.

This all seems fragile to me, with huge potential to add subtle bugs that will be hard to track down.

author maintainer
#5 lore raw
Quoted 5 lines · Florian Westphal
Quoted 4 lines · Phil Sutter
Quoted 3 lines
Quoted 1 line

| reduce = reduce && expr->ops->type->reduce;

Could you elaborate?

Quoted 8 lines
Quoted 5 lines

Well, an expression which may set verdict register to NFT_BREAK should prevent reduction of later expressions in same rule as it may stop rule evaluation at run-time. This is obvious for nft_cmp, but nft_meta is also a candidate: NFT_META_IFTYPE causes NFT_BREAK if pkt->skb->dev is NULL. The optimizer must not assume later expressions are evaluated.

This all seems fragile to me, with huge potential to add subtle bugs that will be hard to track down.

We can expose flags to indicate that an expression is reduced and expressions that are prefetched.

New test infrastructure will help to catch bugs, more selftests and userspace validation of bytecode through exposed flags.

It would be good not to re-fetch data into register that is already there.

maintainer
#6 lore raw
Quoted 11 lines · Pablo Neira Ayuso
Quoted 2 lines

This all seems fragile to me, with huge potential to add subtle bugs that will be hard to track down.

We can expose flags to indicate that an expression is reduced and expressions that are prefetched.

New test infrastructure will help to catch bugs, more selftests and userspace validation of bytecode through exposed flags.

It would be good not to re-fetch data into register that is already there.

I wonder if we should explore doing this from userspace only, i.e. provide hints to kernel which expressions should be dropped in a given chain.

Thats more transparent and would permit to reshuffle expressions, e.g. first add all 'load instructions' and then do the comparisions register opererations.

Kind of reverse approach to what you and Phil are doing, instead of eliding expressions in the data path representation based on in-kernel logic and a debug infra that annotates 'soft off' expressions, annotate them in userspace and then tell kernel what it can discard.

Downside is that userspace would have to delete+re-add entire chain to keep the 'elide' as-is.

With proposed scheme, we will have to patch kernel and then tell users that they must upgrade kernel or risk that their ruelset is incorrect.

With userspace approach, we could slowly extend nft and add explicit optimization flags to the commandline tool, with default of re-fetch.

author maintainer
#7 lore raw
Quoted 21 lines · Florian Westphal
Quoted 11 lines · Pablo Neira Ayuso
Quoted 2 lines

This all seems fragile to me, with huge potential to add subtle bugs that will be hard to track down.

We can expose flags to indicate that an expression is reduced and expressions that are prefetched.

New test infrastructure will help to catch bugs, more selftests and userspace validation of bytecode through exposed flags.

It would be good not to re-fetch data into register that is already there.

I wonder if we should explore doing this from userspace only, i.e. provide hints to kernel which expressions should be dropped in a given chain.

Thats more transparent and would permit to reshuffle expressions, e.g. first add all 'load instructions' and then do the comparisions register opererations.

Quoted 7 lines

Kind of reverse approach to what you and Phil are doing, instead of eliding expressions in the data path representation based on in-kernel logic and a debug infra that annotates 'soft off' expressions, annotate them in userspace and then tell kernel what it can discard.

Downside is that userspace would have to delete+re-add entire chain to keep the 'elide' as-is.

Problem is incremental ruleset updates, we'd go back to iptables way (dump ruleset, rework, reload).

Quoted 5 lines

With proposed scheme, we will have to patch kernel and then tell users that they must upgrade kernel or risk that their ruelset is incorrect.

With userspace approach, we could slowly extend nft and add explicit optimization flags to the commandline tool, with default of re-fetch.

I would revisit to enable expression reduction for keys that do not depend on datapath data by canceling tracking in such case.

author maintainer
#8 lore raw
In reply to Phil Sutter
Quoted 50 lines · Phil Sutter
Quoted 49 lines · Pablo Neira Ayuso
Quoted 29 lines · Phil Sutter

Hi,

Quoted 5 lines · Pablo Neira Ayuso

Either userspace or kernelspace need to pre-fetch keys inconditionally before comparisons for this to work. Otherwise, register tracking data is misleading and it might result in reducing expressions which are not yet registers.

Quoted 8 lines

First expression is guaranteed to be evaluated always, therefore, keep tracking registers and restrict reduction to first expression.

Fixes b2d306542ff9 ("netfilter: nf_tables: do not reduce read-only expressions")

---
@Phil, you mentioned about a way to simplify this patch, I don't see how, just let me know.

Not a big one. Instead of:

|	if (nft_expr_reduce(&track, expr)) {
|		if (reduce) {
|			reduce = false;
|			expr = track.cur;
|			continue;
|		}
|	} else if (reduce) {
|		reduce = false;
|	}
Quoted 8 lines

One could do:

|	if (nft_expr_reduce(&track, expr) && reduce) {
|		reduce = false;
|		expr = track.cur;
|		continue;
|	}
|	reduce = false;

I'll send v2 using this idiom.

Quoted 7 lines

Regarding later pre-fetching, one should distinguish between expressions that (may) set verdict register and those that don't. There are pitfalls though, e.g. error conditions handled that way.

Maybe introduce a new nft_expr_type field and set reduce like so:

| reduce = reduce && expr->ops->type->reduce;

Quoted 7 lines
Quoted 1 line

Could you elaborate?

Well, an expression which may set verdict register to NFT_BREAK should prevent reduction of later expressions in same rule as it may stop rule evaluation at run-time. This is obvious for nft_cmp, but nft_meta is also a candidate: NFT_META_IFTYPE causes NFT_BREAK if pkt->skb->dev is NULL. The optimizer must not assume later expressions are evaluated.

How many other expression are breaking when fetching the key?

Quoted 23 lines

A first step might be said nft_expr_type field indicating a given expression might stop expression evaluation. Therefore:

| reduce = reduce && expr->ops->type->reduce;

would continue expression reduction if not already stopped and the current expression doesn't end it.

Taking nft_meta as example again:

* Behaviour changes based on nft_expr_type::select_ops result
* Some keys are guaranteed to not stop expression evaluation:
NFT_META_LEN for instance will always just fetch skb->len. So introduce a callback instead:

| bool nft_expr_ops::may_break(const struct nft_expr *expr);

Then "ask" the expression whether it may change verdict register:

| reduce = reduce && expr->ops->may_break(expr);

With nft_meta_get_ops, we'd have:

Quoted 12 lines
| bool nft_meta_get_may_break(const struct nft_expr *expr)
| {
| 	switch (nft_expr_priv(expr)->key) {
| 	case NFT_META_LEN:
| 	case NFT_META_PROTOCOL::
| 	[...]
| 		return false;
| 	case NFT_META_IFTYPE:
| 	[...]
| 		return true;
| 	}
| }

And simply remove that NFT_BREAK and set a value that will not ever match via nft_cmp?

Quoted 10 lines

Another thing about your proposed patch: Expressions may update registers even if not reduced. Could that upset later reduction decision? E.g.:

| ip saddr 1.0.0.1 ip daddr 2.0.0.2 accept
| ip daddr 3.0.0.3 accept

Code no longer allows the first rule's 'ip daddr' expression to be reduced (no matter what's in registers already), but it's existence causes reduction of the second rule's 'ip daddr' expression, right?

We cannot make assumptions on ip daddr because there is a cmp right before (to test for ip saddr 1.0.0.1), unless keys are inconditionally prefetched.

author maintainer
#9 lore raw
Quoted 97 lines · Pablo Neira Ayuso
Quoted 50 lines · Phil Sutter
Quoted 49 lines · Pablo Neira Ayuso
Quoted 29 lines · Phil Sutter

Hi,

Quoted 5 lines · Pablo Neira Ayuso

Either userspace or kernelspace need to pre-fetch keys inconditionally before comparisons for this to work. Otherwise, register tracking data is misleading and it might result in reducing expressions which are not yet registers.

Quoted 8 lines

First expression is guaranteed to be evaluated always, therefore, keep tracking registers and restrict reduction to first expression.

Fixes b2d306542ff9 ("netfilter: nf_tables: do not reduce read-only expressions")

---
@Phil, you mentioned about a way to simplify this patch, I don't see how, just let me know.

Not a big one. Instead of:

|	if (nft_expr_reduce(&track, expr)) {
|		if (reduce) {
|			reduce = false;
|			expr = track.cur;
|			continue;
|		}
|	} else if (reduce) {
|		reduce = false;
|	}
Quoted 8 lines

One could do:

|	if (nft_expr_reduce(&track, expr) && reduce) {
|		reduce = false;
|		expr = track.cur;
|		continue;
|	}
|	reduce = false;

I'll send v2 using this idiom.

Quoted 7 lines

Regarding later pre-fetching, one should distinguish between expressions that (may) set verdict register and those that don't. There are pitfalls though, e.g. error conditions handled that way.

Maybe introduce a new nft_expr_type field and set reduce like so:

| reduce = reduce && expr->ops->type->reduce;

Quoted 7 lines
Quoted 1 line

Could you elaborate?

Well, an expression which may set verdict register to NFT_BREAK should prevent reduction of later expressions in same rule as it may stop rule evaluation at run-time. This is obvious for nft_cmp, but nft_meta is also a candidate: NFT_META_IFTYPE causes NFT_BREAK if pkt->skb->dev is NULL. The optimizer must not assume later expressions are evaluated.

How many other expression are breaking when fetching the key?

Quoted 23 lines

A first step might be said nft_expr_type field indicating a given expression might stop expression evaluation. Therefore:

| reduce = reduce && expr->ops->type->reduce;

would continue expression reduction if not already stopped and the current expression doesn't end it.

Taking nft_meta as example again:

* Behaviour changes based on nft_expr_type::select_ops result
* Some keys are guaranteed to not stop expression evaluation:
NFT_META_LEN for instance will always just fetch skb->len. So introduce a callback instead:

| bool nft_expr_ops::may_break(const struct nft_expr *expr);

Then "ask" the expression whether it may change verdict register:

| reduce = reduce && expr->ops->may_break(expr);

With nft_meta_get_ops, we'd have:

Quoted 12 lines
| bool nft_meta_get_may_break(const struct nft_expr *expr)
| {
| 	switch (nft_expr_priv(expr)->key) {
| 	case NFT_META_LEN:
| 	case NFT_META_PROTOCOL::
| 	[...]
| 		return false;
| 	case NFT_META_IFTYPE:
| 	[...]
| 		return true;
| 	}
| }
Quoted 2 lines

And simply remove that NFT_BREAK and set a value that will not ever match via nft_cmp?

Canceling tracking of keys that might break is probably a more simple solution.

reviewer
#10 lore raw
In reply to Pablo Neira Ayuso
Quoted 53 lines · Pablo Neira Ayuso
Quoted 52 lines · Phil Sutter
Quoted 50 lines · Pablo Neira Ayuso
Quoted 29 lines · Phil Sutter

Hi,

Quoted 5 lines · Pablo Neira Ayuso

Either userspace or kernelspace need to pre-fetch keys inconditionally before comparisons for this to work. Otherwise, register tracking data is misleading and it might result in reducing expressions which are not yet registers.

Quoted 8 lines

First expression is guaranteed to be evaluated always, therefore, keep tracking registers and restrict reduction to first expression.

Fixes b2d306542ff9 ("netfilter: nf_tables: do not reduce read-only expressions")

---
@Phil, you mentioned about a way to simplify this patch, I don't see how, just let me know.

Not a big one. Instead of:

|	if (nft_expr_reduce(&track, expr)) {
|		if (reduce) {
|			reduce = false;
|			expr = track.cur;
|			continue;
|		}
|	} else if (reduce) {
|		reduce = false;
|	}
Quoted 8 lines

One could do:

|	if (nft_expr_reduce(&track, expr) && reduce) {
|		reduce = false;
|		expr = track.cur;
|		continue;
|	}
|	reduce = false;

I'll send v2 using this idiom.

Quoted 7 lines

Regarding later pre-fetching, one should distinguish between expressions that (may) set verdict register and those that don't. There are pitfalls though, e.g. error conditions handled that way.

Maybe introduce a new nft_expr_type field and set reduce like so:

| reduce = reduce && expr->ops->type->reduce;

Could you elaborate?

Quoted 7 lines
Quoted 5 lines

Well, an expression which may set verdict register to NFT_BREAK should prevent reduction of later expressions in same rule as it may stop rule evaluation at run-time. This is obvious for nft_cmp, but nft_meta is also a candidate: NFT_META_IFTYPE causes NFT_BREAK if pkt->skb->dev is NULL. The optimizer must not assume later expressions are evaluated.

How many other expression are breaking when fetching the key?

* nft_ct
* nft_exthdr
* nft_fib
* nft_flow_offload
* nft_fwd_netdev
* nft_osf
* nft_payload
* nft_rt
* nft_socket
* nft_synproxy
* nft_tproxy
* nft_tunnel
* nft_xfrm

Quoted 36 lines
Quoted 23 lines

A first step might be said nft_expr_type field indicating a given expression might stop expression evaluation. Therefore:

| reduce = reduce && expr->ops->type->reduce;

would continue expression reduction if not already stopped and the current expression doesn't end it.

Taking nft_meta as example again:

* Behaviour changes based on nft_expr_type::select_ops result
* Some keys are guaranteed to not stop expression evaluation:
NFT_META_LEN for instance will always just fetch skb->len. So introduce a callback instead:

| bool nft_expr_ops::may_break(const struct nft_expr *expr);

Then "ask" the expression whether it may change verdict register:

| reduce = reduce && expr->ops->may_break(expr);

With nft_meta_get_ops, we'd have:

Quoted 12 lines
| bool nft_meta_get_may_break(const struct nft_expr *expr)
| {
| 	switch (nft_expr_priv(expr)->key) {
| 	case NFT_META_LEN:
| 	case NFT_META_PROTOCOL::
| 	[...]
| 		return false;
| 	case NFT_META_IFTYPE:
| 	[...]
| 		return true;
| 	}
| }
Quoted 2 lines

And simply remove that NFT_BREAK and set a value that will not ever match via nft_cmp?

If possible, yes. If given interface is not available, we store 0 or an empty string for ifindex or ifname for instance. There might be types without unreachable values, though. (ifgroup maybe?)

Quoted 7 lines
Quoted 7 lines

Another thing about your proposed patch: Expressions may update registers even if not reduced. Could that upset later reduction decision? E.g.:

| ip saddr 1.0.0.1 ip daddr 2.0.0.2 accept
| ip daddr 3.0.0.3 accept

Quoted 7 lines
Quoted 3 lines

Code no longer allows the first rule's 'ip daddr' expression to be reduced (no matter what's in registers already), but it's existence causes reduction of the second rule's 'ip daddr' expression, right?

We cannot make assumptions on ip daddr because there is a cmp right before (to test for ip saddr 1.0.0.1), unless keys are inconditionally prefetched.

That's right, and I fear calling nft_expr_reduce() might cause that even if not evicting the expression.

Cheers, Phil