Skip to contentSkip to conversation

net/sched: avoid walk() while deleting filters that still use rtnl_lock

PATCH In review Davide Caratti 4 participants 8 messages Dec 24, 2019 – Dec 26, 2019

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover net/sched: avoid walk() while deleting filters that still use rtnl_lock

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(-)
Signature · 1 line
2.24.1
#1 lore raw

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

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

This reverts commit 275c44aa194b7159d1191817b20e076f55f0e620.

---
 net/sched/cls_u32.c | 25 -------------------------
 1 file changed, 25 deletions(-)
net/sched/cls_u32.c +0 -25
index 66c6bcec16cb..a0e6fac613de 100644
@@ -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;
Signature · 1 line
2.24.1
#2 lore raw

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

In reply to 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")
---
 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(-)
include/net/sch_generic.h +2 -0
index 144f264ea394..5e294da0967e 100644
@@ -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,
net/sched/cls_api.c +4 -25
index 6a0eacafdb19..7900db8d4c06 100644
@@ -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;
 }
 
net/sched/cls_flower.c +23 -0
index 0d125de54285..e0316d18529e 100644
@@ -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,
Signature · 1 line
2.24.1
#3 lore raw

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

Quoted 31 lines · 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")
---
 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(-)
include/net/sch_generic.h +0 -0
index 144f264ea394..5e294da0967e 100644

include/net/sch_generic.h struct tcf_proto_ops { · line 312

Quoted 5 lines
include/net/sch_generic.h +2 -0
@@ -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.

Quoted 60 lines
include/net/sch_generic.h +0 -0
 	void			(*walk)(struct tcf_proto *tp,
 					struct tcf_walker *arg, bool rtnl_held);
 	int			(*reoffload)(struct tcf_proto *tp, bool add,
net/sched/cls_api.c +4 -25
index 6a0eacafdb19..7900db8d4c06 100644
@@ -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;
 }
 
net/sched/cls_flower.c +7 -0
index 0d125de54285..e0316d18529e 100644
@@ -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;
+	}

net/sched/cls_flower.c static void fl_bind_class(void *fh, u32 classid, unsigned long cl) · line 2792

Quoted 10 lines
net/sched/cls_flower.c +10 -0
+	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);

Quoted 16 lines
net/sched/cls_flower.c +6 -0
+	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,
#4 lore raw

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

hello Jamal and Vlad,

thanks for looking at this.

Quoted 5 lines · Vlad Buslov

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!

Signature · 1 line
davide
#5 lore raw

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

Quoted 25 lines · Davide Caratti

hello Jamal and Vlad,

thanks for looking at this.

Quoted 5 lines · Vlad Buslov

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++;
Quoted 3 lines

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.

Quoted 6 lines
 # ./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!

maintainer
#6 lore raw
In reply to Davide Caratti

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

Quoted 28 lines · 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(-)
maintainer
#7 lore raw
In reply to Davide Caratti

From: Davide Caratti <[email protected]>
Date: Tue, 24 Dec 2019 10:30:51 +0100

Quoted 12 lines

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().

Quoted 4 lines

(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.