[PATCH RFC net-next 0/4] net/sched: optimizations around action binding and init

[PATCH RFC net-next 0/4] net/sched: optimizations around action binding and init

[Pedro Tammela]

Patches 1 and 2 are scaling optimizations for action binding in
rtnl-less filters. We saw a noticeable lock contention when testing
in a 56 core system, which disappeared after the patches.

Patches 3 and 4 propagate the expectation that such arrays are contiguous
and don't admit holes in them into leaf functions.

Pedro Tammela (4):
  net/sched: act_api: rely on rcu in tcf_idr_check_alloc
  net/sched: act_api: skip idr replace on bound actions
  net/sched: act_api: stop loop over ops array on NULL in
    tcf_action_init
  net/sched: act_api: stop loop over actions array on NULL in
    tcf_idr_insert_many

 include/net/act_api.h |  2 +-
 net/sched/act_api.c   | 75 ++++++++++++++++++++++++-------------------
 net/sched/cls_api.c   |  2 +-
 3 files changed, 44 insertions(+), 35 deletions(-)

-- 
2.40.1

[PATCH RFC net-next 1/4] net/sched: act_api: rely on rcu in tcf_idr_check_alloc

[Pedro Tammela]

Instead of relying only on the idrinfo->lock mutex for
bind/alloc logic, rely on a combination of rcu + mutex + atomics
to better scale the case where multiple rtnl-less filters are
binding to the same action object.

Action binding happens when an action index is specified explicitly and
an action exists which such index exists. Example:
  tc actions add action drop index 1
  tc filter add ... matchall action drop index 1
  tc filter add ... matchall action drop index 1
  tc filter add ... matchall action drop index 1
  tc filter ls ...
     filter protocol all pref 49150 matchall chain 0 filter protocol all pref 49150 matchall chain 0 handle 0x1
     not_in_hw
           action order 1: gact action drop
            random type none pass val 0
            index 1 ref 4 bind 3

   filter protocol all pref 49151 matchall chain 0 filter protocol all pref 49151 matchall chain 0 handle 0x1
     not_in_hw
           action order 1: gact action drop
            random type none pass val 0
            index 1 ref 4 bind 3

   filter protocol all pref 49152 matchall chain 0 filter protocol all pref 49152 matchall chain 0 handle 0x1
     not_in_hw
           action order 1: gact action drop
            random type none pass val 0
            index 1 ref 4 bind 3

When no index is specified, as before, grab the mutex and allocate
in the idr the next available id. In this version, as opposed to before,
it's simplified to store the -EBUSY pointer instead of the previous
alloc + replace combination.

When an index is specified, rely on rcu to find if there's an object in
such index. If there's none, fallback to the above, serializing on the
mutex and reserving the specified id. If there's one, it can be an -EBUSY
pointer, in which case we just try again until it's an action, or an action.
Given the rcu guarantees, the action found could be dead and therefore
we need to bump the refcount if it's not 0, handling the case it's
in fact 0.

As bind and the action refcount are already atomics, these increments can
happen without the mutex protection while many tcf_idr_check_alloc race
to bind to the same action instance.

Signed-off-by: Pedro Tammela <pctammela@mojatatu.com>
---
 net/sched/act_api.c | 56 +++++++++++++++++++++++++++------------------
 1 file changed, 34 insertions(+), 22 deletions(-)

diff --git a/net/sched/act_api.c b/net/sched/act_api.c
index c39252d61ebb..048e660aba30 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -824,43 +824,55 @@ int tcf_idr_check_alloc(struct tc_action_net *tn, u32 *index,
 	struct tcf_idrinfo *idrinfo = tn->idrinfo;
 	struct tc_action *p;
 	int ret;
+	u32 max;
 
-again:
-	mutex_lock(&idrinfo->lock);
 	if (*index) {
+again:
+		rcu_read_lock();
 		p = idr_find(&idrinfo->action_idr, *index);
+
 		if (IS_ERR(p)) {
 			/* This means that another process allocated
 			 * index but did not assign the pointer yet.
 			 */
-			mutex_unlock(&idrinfo->lock);
+			rcu_read_unlock();
 			goto again;
 		}
 
-		if (p) {
-			refcount_inc(&p->tcfa_refcnt);
-			if (bind)
-				atomic_inc(&p->tcfa_bindcnt);
-			*a = p;
-			ret = 1;
-		} else {
-			*a = NULL;
-			ret = idr_alloc_u32(&idrinfo->action_idr, NULL, index,
-					    *index, GFP_KERNEL);
-			if (!ret)
-				idr_replace(&idrinfo->action_idr,
-					    ERR_PTR(-EBUSY), *index);
+		if (!p) {
+			/* Empty slot, try to allocate it */
+			max = *index;
+			rcu_read_unlock();
+			goto new;
+		}
+
+		if (!refcount_inc_not_zero(&p->tcfa_refcnt)) {
+			/* Action was deleted in parallel */
+			rcu_read_unlock();
+			return -ENOENT;
 		}
+
+		if (bind)
+			atomic_inc(&p->tcfa_bindcnt);
+		*a = p;
+
+		rcu_read_unlock();
+
+		return 1;
 	} else {
+		/* Find a slot */
 		*index = 1;
-		*a = NULL;
-		ret = idr_alloc_u32(&idrinfo->action_idr, NULL, index,
-				    UINT_MAX, GFP_KERNEL);
-		if (!ret)
-			idr_replace(&idrinfo->action_idr, ERR_PTR(-EBUSY),
-				    *index);
+		max = UINT_MAX;
 	}
+
+new:
+	*a = NULL;
+
+	mutex_lock(&idrinfo->lock);
+	ret = idr_alloc_u32(&idrinfo->action_idr, ERR_PTR(-EBUSY), index, max,
+			    GFP_KERNEL);
 	mutex_unlock(&idrinfo->lock);
+
 	return ret;
 }
 EXPORT_SYMBOL(tcf_idr_check_alloc);
-- 
2.40.1

[PATCH RFC net-next 2/4] net/sched: act_api: skip idr replace on bound actions

[Pedro Tammela]

tcf_idr_insert_many will replace the allocated -EBUSY pointer in
tcf_idr_check_alloc with the real action pointer, exposing it
to all operations. This operation is only needed when the action pointer
is created (ACT_P_CREATED). For actions which are bound to (returned 0),
the pointer already resides in the idr making such operation a nop.

Even though it's a nop, it's still not a cheap operation as internally
the idr code walks the idr and then does a replace on the appropriate slot.
So if the action was bound, better skip the idr replace entirely.

Signed-off-by: Pedro Tammela <pctammela@mojatatu.com>
---
 include/net/act_api.h |  2 +-
 net/sched/act_api.c   | 11 ++++++-----
 net/sched/cls_api.c   |  2 +-
 3 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/include/net/act_api.h b/include/net/act_api.h
index 4ae0580b63ca..ea13e1e4a7c2 100644
--- a/include/net/act_api.h
+++ b/include/net/act_api.h
@@ -191,7 +191,7 @@ int tcf_idr_create_from_flags(struct tc_action_net *tn, u32 index,
 			      struct nlattr *est, struct tc_action **a,
 			      const struct tc_action_ops *ops, int bind,
 			      u32 flags);
-void tcf_idr_insert_many(struct tc_action *actions[]);
+void tcf_idr_insert_many(struct tc_action *actions[], int init_res[]);
 void tcf_idr_cleanup(struct tc_action_net *tn, u32 index);
 int tcf_idr_check_alloc(struct tc_action_net *tn, u32 *index,
 			struct tc_action **a, int bind);
diff --git a/net/sched/act_api.c b/net/sched/act_api.c
index 048e660aba30..bf6f9ca15a30 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -1286,7 +1286,7 @@ static const struct nla_policy tcf_action_policy[TCA_ACT_MAX + 1] = {
 	[TCA_ACT_HW_STATS]	= NLA_POLICY_BITFIELD32(TCA_ACT_HW_STATS_ANY),
 };
 
-void tcf_idr_insert_many(struct tc_action *actions[])
+void tcf_idr_insert_many(struct tc_action *actions[], int init_res[])
 {
 	int i;
 
@@ -1296,11 +1296,12 @@ void tcf_idr_insert_many(struct tc_action *actions[])
 
 		if (!a)
 			continue;
+		if (init_res[i] == 0) /* Bound */
+			continue;
+
 		idrinfo = a->idrinfo;
 		mutex_lock(&idrinfo->lock);
-		/* Replace ERR_PTR(-EBUSY) allocated by tcf_idr_check_alloc if
-		 * it is just created, otherwise this is just a nop.
-		 */
+		/* Replace ERR_PTR(-EBUSY) allocated by tcf_idr_check_alloc */
 		idr_replace(&idrinfo->action_idr, a, a->tcfa_index);
 		mutex_unlock(&idrinfo->lock);
 	}
@@ -1500,7 +1501,7 @@ int tcf_action_init(struct net *net, struct tcf_proto *tp, struct nlattr *nla,
 	/* We have to commit them all together, because if any error happened in
 	 * between, we could not handle the failure gracefully.
 	 */
-	tcf_idr_insert_many(actions);
+	tcf_idr_insert_many(actions, init_res);
 
 	*attr_size = tcf_action_full_attrs_size(sz);
 	err = i - 1;
diff --git a/net/sched/cls_api.c b/net/sched/cls_api.c
index 1976bd163986..6391b341284e 100644
--- a/net/sched/cls_api.c
+++ b/net/sched/cls_api.c
@@ -3309,7 +3309,7 @@ int tcf_exts_validate_ex(struct net *net, struct tcf_proto *tp, struct nlattr **
 			act->type = exts->type = TCA_OLD_COMPAT;
 			exts->actions[0] = act;
 			exts->nr_actions = 1;
-			tcf_idr_insert_many(exts->actions);
+			tcf_idr_insert_many(exts->actions, init_res);
 		} else if (exts->action && tb[exts->action]) {
 			int err;
 
-- 
2.40.1

[PATCH RFC net-next 3/4] net/sched: act_api: stop loop over ops array on NULL in tcf_action_init

[Pedro Tammela]

The ops array is contiguous, so stop processing whenever a NULL is found

Signed-off-by: Pedro Tammela <pctammela@mojatatu.com>
---
 net/sched/act_api.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/net/sched/act_api.c b/net/sched/act_api.c
index bf6f9ca15a30..8517bfbd69a6 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -1510,10 +1510,8 @@ int tcf_action_init(struct net *net, struct tcf_proto *tp, struct nlattr *nla,
 err:
 	tcf_action_destroy(actions, flags & TCA_ACT_FLAGS_BIND);
 err_mod:
-	for (i = 0; i < TCA_ACT_MAX_PRIO; i++) {
-		if (ops[i])
-			module_put(ops[i]->owner);
-	}
+	for (i = 0; i < TCA_ACT_MAX_PRIO && ops[i]; i++)
+		module_put(ops[i]->owner);
 	return err;
 }
 
-- 
2.40.1

[PATCH RFC net-next 4/4] net/sched: act_api: stop loop over actions array on NULL in tcf_idr_insert_many

[Pedro Tammela]

The actions array is contiguous, so stop processing whenever a NULL
is found. This is already the assumption for tcf_action_destroy[1],
which is called from tcf_actions_init.

[1] https://elixir.bootlin.com/linux/v6.7-rc3/source/net/sched/act_api.c#L1115

Signed-off-by: Pedro Tammela <pctammela@mojatatu.com>
---
 net/sched/act_api.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/net/sched/act_api.c b/net/sched/act_api.c
index 8517bfbd69a6..980dd3b51dd0 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -1290,12 +1290,10 @@ void tcf_idr_insert_many(struct tc_action *actions[], int init_res[])
 {
 	int i;
 
-	for (i = 0; i < TCA_ACT_MAX_PRIO; i++) {
+	for (i = 0; i < TCA_ACT_MAX_PRIO && actions[i]; i++) {
 		struct tc_action *a = actions[i];
 		struct tcf_idrinfo *idrinfo;
 
-		if (!a)
-			continue;
 		if (init_res[i] == 0) /* Bound */
 			continue;
 
-- 
2.40.1

Re: [PATCH RFC net-next 3/4] net/sched: act_api: stop loop over ops array on NULL in tcf_action_init

[Marcelo Ricardo Leitner]

On Tue, Nov 28, 2023 at 01:06:30PM -0300, Pedro Tammela wrote:
> @@ -1510,10 +1510,8 @@ int tcf_action_init(struct net *net, struct tcf_proto *tp, struct nlattr *nla,
>  err:
>  	tcf_action_destroy(actions, flags & TCA_ACT_FLAGS_BIND);
>  err_mod:
> -	for (i = 0; i < TCA_ACT_MAX_PRIO; i++) {
> -		if (ops[i])
> -			module_put(ops[i]->owner);
> -	}
> +	for (i = 0; i < TCA_ACT_MAX_PRIO && ops[i]; i++)
> +		module_put(ops[i]->owner);
>  	return err;

I was going to say:
Maybe it's time for a helper macro for this.

$ git grep TCA_ACT_MAX_PRIO
include/net/pkt_cls.h:  for (i = 0; i < TCA_ACT_MAX_PRIO && ((a) =
(exts)->actions[i]); i++)
include/net/pkt_cls.h:  for (i = 0; i < TCA_ACT_MAX_PRIO && ((a) =
actions[i]); i++)
...
net/sched/act_api.c:    for (i = 0; i < TCA_ACT_MAX_PRIO && actions[i]; i++) {
net/sched/act_api.c:    for (i = 0; i < TCA_ACT_MAX_PRIO; i++) {
net/sched/act_api.c:    for (i = 0; i < TCA_ACT_MAX_PRIO && actions[i]; i++) {
net/sched/act_api.c:    for (i = 0; i < TCA_ACT_MAX_PRIO; i++) {
...
net/sched/act_api.c:    for (i = 1; i <= TCA_ACT_MAX_PRIO && tb[i]; i++) {
net/sched/act_api.c:    for (i = 1; i <= TCA_ACT_MAX_PRIO && tb[i]; i++) {
net/sched/act_api.c:    for (i = 0; i < TCA_ACT_MAX_PRIO; i++) {
net/sched/act_api.c:    for (i = 0; i < TCA_ACT_MAX_PRIO && actions[i]; i++) {
...

But then, that's exactly what the first 2 hits are :)
So AFAICT this loop can be written as:

struct struct tc_action_ops *op;
tcf_act_for_each_action(i, op, ops)
	module_put(op->owner);

Thoughts? It would be iterating over struct tc_action_ops and not
tc_action, as in tcf_act_for_each_action() (which is the only user of
this macro today), but that seems okay.

  Marcelo

Re: [PATCH RFC net-next 1/4] net/sched: act_api: rely on rcu in tcf_idr_check_alloc

[Marcelo Ricardo Leitner]

On Tue, Nov 28, 2023 at 01:06:28PM -0300, Pedro Tammela wrote:
> Instead of relying only on the idrinfo->lock mutex for
> bind/alloc logic, rely on a combination of rcu + mutex + atomics
> to better scale the case where multiple rtnl-less filters are
> binding to the same action object.

LGTM

Re: [PATCH RFC net-next 3/4] net/sched: act_api: stop loop over ops array on NULL in tcf_action_init

[Pedro Tammela]

On 28/11/2023 16:11, Marcelo Ricardo Leitner wrote:
> On Tue, Nov 28, 2023 at 01:06:30PM -0300, Pedro Tammela wrote:
>> @@ -1510,10 +1510,8 @@ int tcf_action_init(struct net *net, struct tcf_proto *tp, struct nlattr *nla,
>>   err:
>>   	tcf_action_destroy(actions, flags & TCA_ACT_FLAGS_BIND);
>>   err_mod:
>> -	for (i = 0; i < TCA_ACT_MAX_PRIO; i++) {
>> -		if (ops[i])
>> -			module_put(ops[i]->owner);
>> -	}
>> +	for (i = 0; i < TCA_ACT_MAX_PRIO && ops[i]; i++)
>> +		module_put(ops[i]->owner);
>>   	return err;
> 
> I was going to say:
> Maybe it's time for a helper macro for this.
> 
> $ git grep TCA_ACT_MAX_PRIO
> include/net/pkt_cls.h:  for (i = 0; i < TCA_ACT_MAX_PRIO && ((a) =
> (exts)->actions[i]); i++)
> include/net/pkt_cls.h:  for (i = 0; i < TCA_ACT_MAX_PRIO && ((a) =
> actions[i]); i++)
> ...
> net/sched/act_api.c:    for (i = 0; i < TCA_ACT_MAX_PRIO && actions[i]; i++) {
> net/sched/act_api.c:    for (i = 0; i < TCA_ACT_MAX_PRIO; i++) {
> net/sched/act_api.c:    for (i = 0; i < TCA_ACT_MAX_PRIO && actions[i]; i++) {
> net/sched/act_api.c:    for (i = 0; i < TCA_ACT_MAX_PRIO; i++) {
> ...
> net/sched/act_api.c:    for (i = 1; i <= TCA_ACT_MAX_PRIO && tb[i]; i++) {
> net/sched/act_api.c:    for (i = 1; i <= TCA_ACT_MAX_PRIO && tb[i]; i++) {
> net/sched/act_api.c:    for (i = 0; i < TCA_ACT_MAX_PRIO; i++) {
> net/sched/act_api.c:    for (i = 0; i < TCA_ACT_MAX_PRIO && actions[i]; i++) {
> ...
> 
> But then, that's exactly what the first 2 hits are :)
> So AFAICT this loop can be written as:
> 
> struct struct tc_action_ops *op;
> tcf_act_for_each_action(i, op, ops)
> 	module_put(op->owner);
> 
> Thoughts? It would be iterating over struct tc_action_ops and not
> tc_action, as in tcf_act_for_each_action() (which is the only user of
> this macro today), but that seems okay.
> 
>    Marcelo
> 

Interesting, I didn't even notice those macros.
I believe it helps with code maintainability.

Do note, I saw a place that the action array is expected to be not 
contiguous. So any sed-like replacement must be done with care.

When we know for sure it's contiguous, I'm all in for macros!