[PATCH net 0/2] net/sched: avoid walk() while deleting filters that still use rtnl_lock

[PATCH net 0/2] net/sched: avoid walk() while deleting filters that still use rtnl_lock

[Davide Caratti]

we don't need to use walk() on deletion of TC filters, at least for those
implementations that don't have TCF_PROTO_OPS_DOIT_UNLOCKED.

- patch 1/2 restores walk() semantic in cls_u32, that was recently
  changed to fix semi-configured filters in the error path of u32_change().
- patch 2/2 moves the delete_empty() logic to cls_flower, the only filter
  that currently needs to guard against concurrent insert/delete.
  For flower, the current delete_empty() still [ab,]uses walk(), to
  preserve the bugfixes introduced by [1] and [2]: a follow-up commit
  in the future can implement a proper delete_empty() that avoids calls
  to fl_walk().

(tested with tdc "concurrency", "matchall", "basic" and "u32")

[1] 6676d5e416ee ("net: sched: set dedicated tcf_walker flag when tp is empty")
[2] 8b64678e0af8 ("net: sched: refactor tp insert/delete for concurrent execution")

Davide Caratti (2):
  Revert "net/sched: cls_u32: fix refcount leak in the error path of
    u32_change()"
  net/sched: add delete_empty() to filters and use it in cls_flower

 include/net/sch_generic.h |  2 ++
 net/sched/cls_api.c       | 29 ++++-------------------------
 net/sched/cls_flower.c    | 23 +++++++++++++++++++++++
 net/sched/cls_u32.c       | 25 -------------------------
 4 files changed, 29 insertions(+), 50 deletions(-)

-- 
2.24.1

[PATCH net 1/2] Revert "net/sched: cls_u32: fix refcount leak in the error path of u32_change()"

[Davide Caratti]

A more generic fix, that preserves the semantic of rule dumping, has been
proposed.

This reverts commit 275c44aa194b7159d1191817b20e076f55f0e620.

Suggested-by: Jamal Hadi Salim <jhs@mojatatu.com>
Signed-off-by: Davide Caratti <dcaratti@redhat.com>
---
 net/sched/cls_u32.c | 25 -------------------------
 1 file changed, 25 deletions(-)

diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index 66c6bcec16cb..a0e6fac613de 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -1108,33 +1108,10 @@ static int u32_change(struct net *net, struct sk_buff *in_skb,
 	return err;
 }
 
-static bool u32_hnode_empty(struct tc_u_hnode *ht, bool *non_root_ht)
-{
-	int i;
-
-	if (!ht)
-		return true;
-	if (!ht->is_root) {
-		*non_root_ht = true;
-		return false;
-	}
-	if (*non_root_ht)
-		return false;
-	if (ht->refcnt < 2)
-		return true;
-
-	for (i = 0; i <= ht->divisor; i++) {
-		if (rtnl_dereference(ht->ht[i]))
-			return false;
-	}
-	return true;
-}
-
 static void u32_walk(struct tcf_proto *tp, struct tcf_walker *arg,
 		     bool rtnl_held)
 {
 	struct tc_u_common *tp_c = tp->data;
-	bool non_root_ht = false;
 	struct tc_u_hnode *ht;
 	struct tc_u_knode *n;
 	unsigned int h;
@@ -1147,8 +1124,6 @@ static void u32_walk(struct tcf_proto *tp, struct tcf_walker *arg,
 	     ht = rtnl_dereference(ht->next)) {
 		if (ht->prio != tp->prio)
 			continue;
-		if (u32_hnode_empty(ht, &non_root_ht))
-			return;
 		if (arg->count >= arg->skip) {
 			if (arg->fn(tp, ht, arg) < 0) {
 				arg->stop = 1;
-- 
2.24.1

[PATCH net 2/2] net/sched: add delete_empty() to filters and use it in cls_flower

[Davide Caratti]

on tc filters that don't support lockless insertion/removal, there is no
need to guard against concurrent insertion when a removal is in progress.
Therefore, we can avoid taking the filter lock and doing a full walk()
when deleting: it's sufficient to decrease the refcount.
This fixes situations where walk() was wrongly detecting a non-empty
filter on deletion, like it happened with cls_u32 in the error path of
change(), thus leading to failures in the following tdc selftests:

 6aa7: (filter, u32) Add/Replace u32 with source match and invalid indev
 6658: (filter, u32) Add/Replace u32 with custom hash table and invalid handle
 74c2: (filter, u32) Add/Replace u32 filter with invalid hash table id

On cls_flower, and on (future) lockless filters, this check is necessary:
move all the check_empty() logic in a callback so that each filter
can have its own implementation.

Fixes: 6676d5e416ee ("net: sched: set dedicated tcf_walker flag when tp is empty")
Suggested-by: Jamal Hadi Salim <jhs@mojatatu.com>
Suggested-by: Vlad Buslov <vladbu@mellanox.com>
Signed-off-by: Davide Caratti <dcaratti@redhat.com>
---
 include/net/sch_generic.h |  2 ++
 net/sched/cls_api.c       | 29 ++++-------------------------
 net/sched/cls_flower.c    | 23 +++++++++++++++++++++++
 3 files changed, 29 insertions(+), 25 deletions(-)

diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
index 144f264ea394..5e294da0967e 100644
--- a/include/net/sch_generic.h
+++ b/include/net/sch_generic.h
@@ -308,6 +308,8 @@ struct tcf_proto_ops {
 	int			(*delete)(struct tcf_proto *tp, void *arg,
 					  bool *last, bool rtnl_held,
 					  struct netlink_ext_ack *);
+	bool			(*delete_empty)(struct tcf_proto *tp,
+						bool rtnl_held);
 	void			(*walk)(struct tcf_proto *tp,
 					struct tcf_walker *arg, bool rtnl_held);
 	int			(*reoffload)(struct tcf_proto *tp, bool add,
diff --git a/net/sched/cls_api.c b/net/sched/cls_api.c
index 6a0eacafdb19..7900db8d4c06 100644
--- a/net/sched/cls_api.c
+++ b/net/sched/cls_api.c
@@ -308,33 +308,12 @@ static void tcf_proto_put(struct tcf_proto *tp, bool rtnl_held,
 		tcf_proto_destroy(tp, rtnl_held, true, extack);
 }
 
-static int walker_check_empty(struct tcf_proto *tp, void *fh,
-			      struct tcf_walker *arg)
-{
-	if (fh) {
-		arg->nonempty = true;
-		return -1;
-	}
-	return 0;
-}
-
-static bool tcf_proto_is_empty(struct tcf_proto *tp, bool rtnl_held)
-{
-	struct tcf_walker walker = { .fn = walker_check_empty, };
-
-	if (tp->ops->walk) {
-		tp->ops->walk(tp, &walker, rtnl_held);
-		return !walker.nonempty;
-	}
-	return true;
-}
-
 static bool tcf_proto_check_delete(struct tcf_proto *tp, bool rtnl_held)
 {
-	spin_lock(&tp->lock);
-	if (tcf_proto_is_empty(tp, rtnl_held))
-		tp->deleting = true;
-	spin_unlock(&tp->lock);
+	if (tp->ops->delete_empty)
+		return tp->ops->delete_empty(tp, rtnl_held);
+
+	tp->deleting = true;
 	return tp->deleting;
 }
 
diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
index 0d125de54285..e0316d18529e 100644
--- a/net/sched/cls_flower.c
+++ b/net/sched/cls_flower.c
@@ -2773,6 +2773,28 @@ static void fl_bind_class(void *fh, u32 classid, unsigned long cl)
 		f->res.class = cl;
 }
 
+static int walker_check_empty(struct tcf_proto *tp, void *fh,
+			      struct tcf_walker *arg)
+{
+	if (fh) {
+		arg->nonempty = true;
+		return -1;
+	}
+	return 0;
+}
+
+static bool fl_delete_empty(struct tcf_proto *tp, bool rtnl_held)
+{
+	struct tcf_walker walker = { .fn = walker_check_empty, };
+
+	spin_lock(&tp->lock);
+	fl_walk(tp, &walker, rtnl_held);
+	tp->deleting = !walker.nonempty;
+	spin_unlock(&tp->lock);
+
+	return tp->deleting;
+}
+
 static struct tcf_proto_ops cls_fl_ops __read_mostly = {
 	.kind		= "flower",
 	.classify	= fl_classify,
@@ -2782,6 +2804,7 @@ static struct tcf_proto_ops cls_fl_ops __read_mostly = {
 	.put		= fl_put,
 	.change		= fl_change,
 	.delete		= fl_delete,
+	.delete_empty	= fl_delete_empty,
 	.walk		= fl_walk,
 	.reoffload	= fl_reoffload,
 	.hw_add		= fl_hw_add,
-- 
2.24.1

Re: [PATCH net 2/2] net/sched: add delete_empty() to filters and use it in cls_flower

[Vlad Buslov]

On Tue 24 Dec 2019 at 11:30, Davide Caratti <dcaratti@redhat.com> wrote:
> on tc filters that don't support lockless insertion/removal, there is no
> need to guard against concurrent insertion when a removal is in progress.
> Therefore, we can avoid taking the filter lock and doing a full walk()
> when deleting: it's sufficient to decrease the refcount.
> This fixes situations where walk() was wrongly detecting a non-empty
> filter on deletion, like it happened with cls_u32 in the error path of
> change(), thus leading to failures in the following tdc selftests:
>
>  6aa7: (filter, u32) Add/Replace u32 with source match and invalid indev
>  6658: (filter, u32) Add/Replace u32 with custom hash table and invalid handle
>  74c2: (filter, u32) Add/Replace u32 filter with invalid hash table id
>
> On cls_flower, and on (future) lockless filters, this check is necessary:
> move all the check_empty() logic in a callback so that each filter
> can have its own implementation.
>
> Fixes: 6676d5e416ee ("net: sched: set dedicated tcf_walker flag when tp is empty")
> Suggested-by: Jamal Hadi Salim <jhs@mojatatu.com>
> Suggested-by: Vlad Buslov <vladbu@mellanox.com>
> Signed-off-by: Davide Caratti <dcaratti@redhat.com>
> ---
>  include/net/sch_generic.h |  2 ++
>  net/sched/cls_api.c       | 29 ++++-------------------------
>  net/sched/cls_flower.c    | 23 +++++++++++++++++++++++
>  3 files changed, 29 insertions(+), 25 deletions(-)
>
> diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
> index 144f264ea394..5e294da0967e 100644
> --- a/include/net/sch_generic.h
> +++ b/include/net/sch_generic.h
> @@ -308,6 +308,8 @@ struct tcf_proto_ops {
>  	int			(*delete)(struct tcf_proto *tp, void *arg,
>  					  bool *last, bool rtnl_held,
>  					  struct netlink_ext_ack *);
> +	bool			(*delete_empty)(struct tcf_proto *tp,
> +						bool rtnl_held);

Hi Davide,

Thanks again for fixing this!

Could you add a comment to TCF_PROTO_OPS_DOIT_UNLOCKED flag with
something like "Classifiers implementing this flag are expected to
define tcf_proto_ops->delete_empty(), otherwise hard to debug race
conditions can occur during classifier instance deletion with concurrent
filter insertion."? My original intention was not to require unlocked
classifiers to implement any new APIs but since it is no longer the case
it is better if we document it.

>  	void			(*walk)(struct tcf_proto *tp,
>  					struct tcf_walker *arg, bool rtnl_held);
>  	int			(*reoffload)(struct tcf_proto *tp, bool add,
> diff --git a/net/sched/cls_api.c b/net/sched/cls_api.c
> index 6a0eacafdb19..7900db8d4c06 100644
> --- a/net/sched/cls_api.c
> +++ b/net/sched/cls_api.c
> @@ -308,33 +308,12 @@ static void tcf_proto_put(struct tcf_proto *tp, bool rtnl_held,
>  		tcf_proto_destroy(tp, rtnl_held, true, extack);
>  }
>
> -static int walker_check_empty(struct tcf_proto *tp, void *fh,
> -			      struct tcf_walker *arg)
> -{
> -	if (fh) {
> -		arg->nonempty = true;
> -		return -1;
> -	}
> -	return 0;
> -}
> -
> -static bool tcf_proto_is_empty(struct tcf_proto *tp, bool rtnl_held)
> -{
> -	struct tcf_walker walker = { .fn = walker_check_empty, };
> -
> -	if (tp->ops->walk) {
> -		tp->ops->walk(tp, &walker, rtnl_held);
> -		return !walker.nonempty;
> -	}
> -	return true;
> -}
> -
>  static bool tcf_proto_check_delete(struct tcf_proto *tp, bool rtnl_held)
>  {
> -	spin_lock(&tp->lock);
> -	if (tcf_proto_is_empty(tp, rtnl_held))
> -		tp->deleting = true;
> -	spin_unlock(&tp->lock);
> +	if (tp->ops->delete_empty)
> +		return tp->ops->delete_empty(tp, rtnl_held);
> +
> +	tp->deleting = true;
>  	return tp->deleting;
>  }
>
> diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
> index 0d125de54285..e0316d18529e 100644
> --- a/net/sched/cls_flower.c
> +++ b/net/sched/cls_flower.c
> @@ -2773,6 +2773,28 @@ static void fl_bind_class(void *fh, u32 classid, unsigned long cl)
>  		f->res.class = cl;
>  }
>
> +static int walker_check_empty(struct tcf_proto *tp, void *fh,
> +			      struct tcf_walker *arg)
> +{
> +	if (fh) {
> +		arg->nonempty = true;
> +		return -1;
> +	}
> +	return 0;
> +}
> +
> +static bool fl_delete_empty(struct tcf_proto *tp, bool rtnl_held)
> +{
> +	struct tcf_walker walker = { .fn = walker_check_empty, };
> +
> +	spin_lock(&tp->lock);
> +	fl_walk(tp, &walker, rtnl_held);
> +	tp->deleting = !walker.nonempty;

I guess we can reduce this code to just:

spin_lock(&tp->lock);
tp->deleting = idr_is_empty(&head->handle_idr);
spin_unlock(&tp->lock);

> +	spin_unlock(&tp->lock);
> +
> +	return tp->deleting;
> +}
> +
>  static struct tcf_proto_ops cls_fl_ops __read_mostly = {
>  	.kind		= "flower",
>  	.classify	= fl_classify,
> @@ -2782,6 +2804,7 @@ static struct tcf_proto_ops cls_fl_ops __read_mostly = {
>  	.put		= fl_put,
>  	.change		= fl_change,
>  	.delete		= fl_delete,
> +	.delete_empty	= fl_delete_empty,
>  	.walk		= fl_walk,
>  	.reoffload	= fl_reoffload,
>  	.hw_add		= fl_hw_add,

Re: [PATCH net 0/2] net/sched: avoid walk() while deleting filters that still use rtnl_lock

[Jamal Hadi Salim]

Davide,
Thanks for the effort. Looks good to me - will wait for you to
address Vlad's comments then run a couple of tests...

cheers,
jamal

On 2019-12-24 4:30 a.m., Davide Caratti wrote:
> we don't need to use walk() on deletion of TC filters, at least for those
> implementations that don't have TCF_PROTO_OPS_DOIT_UNLOCKED.
> 
> - patch 1/2 restores walk() semantic in cls_u32, that was recently
>    changed to fix semi-configured filters in the error path of u32_change().
> - patch 2/2 moves the delete_empty() logic to cls_flower, the only filter
>    that currently needs to guard against concurrent insert/delete.
>    For flower, the current delete_empty() still [ab,]uses walk(), to
>    preserve the bugfixes introduced by [1] and [2]: a follow-up commit
>    in the future can implement a proper delete_empty() that avoids calls
>    to fl_walk().
> 
> (tested with tdc "concurrency", "matchall", "basic" and "u32")
> 
> [1] 6676d5e416ee ("net: sched: set dedicated tcf_walker flag when tp is empty")
> [2] 8b64678e0af8 ("net: sched: refactor tp insert/delete for concurrent execution")
> 
> Davide Caratti (2):
>    Revert "net/sched: cls_u32: fix refcount leak in the error path of
>      u32_change()"
>    net/sched: add delete_empty() to filters and use it in cls_flower
> 
>   include/net/sch_generic.h |  2 ++
>   net/sched/cls_api.c       | 29 ++++-------------------------
>   net/sched/cls_flower.c    | 23 +++++++++++++++++++++++
>   net/sched/cls_u32.c       | 25 -------------------------
>   4 files changed, 29 insertions(+), 50 deletions(-)
> 

Re: [PATCH net 2/2] net/sched: add delete_empty() to filters and use it in cls_flower

[Davide Caratti]

hello Jamal and Vlad,

thanks for looking at this.

On Tue, 2019-12-24 at 11:48 +0000, Vlad Buslov wrote:
> I guess we can reduce this code to just:
> 
> spin_lock(&tp->lock);
> tp->deleting = idr_is_empty(&head->handle_idr);
> spin_unlock(&tp->lock);

on the current version of delete_empty() for cls_flower, we are assuming
an empty filter also when the IDR is allocated, but its refcount is zero:

1931         idr_for_each_entry_continue_ul(&head->handle_idr, f, tmp, id) {
1932                 /* don't return filters that are being deleted */
1933                 if (!refcount_inc_not_zero(&f->refcnt))
1934                         continue;
1935                 if (arg->fn(tp, f, arg) < 0) {
1936                         __fl_put(f);
1937                         arg->stop = 1;
1938                         break;
1939                 }
1940                 __fl_put(f);
1941                 arg->count++;
1942         }

but probably this is relevant to dump(), not delete(). Correct?

 # ./tdc.py -c flower -d enp2s0

^^ I'm running several loops of this, just to make sure. If I don't find
anything relevant in few hours, I will send a v2.
thanks!
-- 
davide

Re: [PATCH net 2/2] net/sched: add delete_empty() to filters and use it in cls_flower

[Vlad Buslov]

On Tue 24 Dec 2019 at 16:53, Davide Caratti <dcaratti@redhat.com> wrote:
> hello Jamal and Vlad,
>
> thanks for looking at this.
>
> On Tue, 2019-12-24 at 11:48 +0000, Vlad Buslov wrote:
>> I guess we can reduce this code to just:
>>
>> spin_lock(&tp->lock);
>> tp->deleting = idr_is_empty(&head->handle_idr);
>> spin_unlock(&tp->lock);
>
> on the current version of delete_empty() for cls_flower, we are assuming
> an empty filter also when the IDR is allocated, but its refcount is zero:
>
> 1931         idr_for_each_entry_continue_ul(&head->handle_idr, f, tmp, id) {
> 1932                 /* don't return filters that are being deleted */
> 1933                 if (!refcount_inc_not_zero(&f->refcnt))
> 1934                         continue;
> 1935                 if (arg->fn(tp, f, arg) < 0) {
> 1936                         __fl_put(f);
> 1937                         arg->stop = 1;
> 1938                         break;
> 1939                 }
> 1940                 __fl_put(f);
> 1941                 arg->count++;
> 1942         }
>
> but probably this is relevant to dump(), not delete(). Correct?

I don't think that it is possible to get filter with refcnt==0 from idr
when holding the tp lock (filter is inserted with refcnt==1 and removed
from idr before releasing the last reference in fl_delete()). fl_walk()
doesn't take the lock by itself so it needs to deal with concurrent
removals.

>
>  # ./tdc.py -c flower -d enp2s0
>
> ^^ I'm running several loops of this, just to make sure. If I don't find
> anything relevant in few hours, I will send a v2.
> thanks!

Re: [PATCH net 0/2] net/sched: avoid walk() while deleting filters that still use rtnl_lock

[David Miller]

From: Davide Caratti <dcaratti@redhat.com>
Date: Tue, 24 Dec 2019 10:30:51 +0100

> we don't need to use walk() on deletion of TC filters, at least for those
> implementations that don't have TCF_PROTO_OPS_DOIT_UNLOCKED.
> 
> - patch 1/2 restores walk() semantic in cls_u32, that was recently
>   changed to fix semi-configured filters in the error path of u32_change().
> - patch 2/2 moves the delete_empty() logic to cls_flower, the only filter
>   that currently needs to guard against concurrent insert/delete.
>   For flower, the current delete_empty() still [ab,]uses walk(), to
>   preserve the bugfixes introduced by [1] and [2]: a follow-up commit
>   in the future can implement a proper delete_empty() that avoids calls
>   to fl_walk().
> 
> (tested with tdc "concurrency", "matchall", "basic" and "u32")
> 
> [1] 6676d5e416ee ("net: sched: set dedicated tcf_walker flag when tp is empty")
> [2] 8b64678e0af8 ("net: sched: refactor tp insert/delete for concurrent execution")

I think you really need to do the revert and the new version of the fix
in the same commit or similar.

Otherwise this series will not bisect cleanly, because any test on this
functionality will fail after patch #1.

Thanks.