KASAN: slab-use-after-free Write in mini_qdisc_pair_swap

Hi Peilin,

Quoted 30 lines · Peilin Ye

+Cc: Vlad Buslov, Hillf Danton
Hi all,
Quoted 3 lines · Peilin Ye
I also reproduced this UAF using the syzkaller reproducer in the report (the C reproducer did not work for me for unknown reasons). I will look into this.
Currently, multiple ingress (clsact) Qdiscs can access the per-netdev *miniq_ingress (*miniq_egress) pointer concurrently. This is unfortunately true in two senses:
1. We allow adding ingress (clsact) Qdiscs under parents other than TC_H_INGRESS (TC_H_CLSACT):
  $ ip link add ifb0 numtxqueues 8 type ifb
  $ echo clsact > /proc/sys/net/core/default_qdisc
  $ tc qdisc add dev ifb0 handle 1: root mq
  $ tc qdisc show dev ifb0
  qdisc mq 1: root
  qdisc clsact 0: parent 1:8
  qdisc clsact 0: parent 1:7
  qdisc clsact 0: parent 1:6
  qdisc clsact 0: parent 1:5
  qdisc clsact 0: parent 1:4
  qdisc clsact 0: parent 1:3
  qdisc clsact 0: parent 1:2
  qdisc clsact 0: parent 1:1

Quoted 3 lines

This is obviously racy and should be prohibited. I've started working on patches to fix this. The syz repro for this UAF adds ingress Qdiscs under TC_H_ROOT, by the way.

Hmm, didn't realize it was the case.

Quoted 35 lines

2. After introducing RTNL-lockless RTM_{NEW,DEL,GET}TFILTER requests [1], it is possible that, when replacing ingress (clsact) Qdiscs, the old one can access *miniq_{in,e}gress concurrently with the new one. For example, the syz repro does something like the following:
Thread 1 creates sch_ingress Qdisc A (containing mini Qdisc a1 and a2), then adds a cls_flower filter X to Qdisc A.
Thread 2 creates sch_ingress Qdisc B (containing mini Qdisc b1 and b2) to replace Qdisc A, then adds a cls_flower filter Y to Qdisc B.
Device has 8 TXQs.
Thread 1 A's refcnt Thread 2
RTM_NEWQDISC (A, locked)
qdisc_create(A) 1
qdisc_graft(A) 9
RTM_NEWTFILTER (X, lockless)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
! mini_qdisc_pair_swap(A)
            |                        RTM_NEWQDISC (B, locked)
            |                    2    qdisc_graft(B)
            |                    1    notify_and_destroy(A)
            |                                  
            |                        RTM_NEWTFILTER (Y, lockless)
            |                         tcf_chain0_head_change(B)
            |                       ! mini_qdisc_pair_swap(B)
   tcf_block_release(A)          0             |
   qdisc_destroy(A)                            |
   tcf_chain0_head_change_cb_del(A)            |
 ! mini_qdisc_pair_swap(A)                     |
            |                                  |

Quoted 6 lines

... ...
As we can see there're interleaving mini_qdisc_pair_swap() calls between Qdisc A and B, causing all kinds of troubles, including the UAF (thread 2 writing to mini Qdisc a1's rcu_state after Qdisc A has already been freed) reported by syzbot.

Great analysis! However, it is still not quite clear to me how threads 1 and 2 access each other RCU state when q->miniqp is a private memory of the Qdisc, so 1 should only see A->miniqp and 2 only B->miniqp. And both miniqps should be protected from deallocation by reference that lockless RTM_NEWTFILTER obtains.

Quoted 8 lines

To fix this, I'm cooking a patch that, when replacing ingress (clsact) Qdiscs, in qdisc_graft():
I. We should make sure there's no on-the-fly lockless filter requests
for the old Qdisc, and return -EBUSY if there's any (or can/should we wait in RTM_NEWQDISC handler?)

Quoted 5 lines

II. We should destory the old Qdisc before publishing the new one
(i.e. setting it to dev_ingress_queue(dev)->qdisc_sleeping, so that subsequent filter requests can see it), because {ingress,clsact}_destroy() also call mini_qdisc_pair_swap(), which sets *miniq_{in,e}gress to NULL

Another approach would be to somehow detect concurrent Qdisc replace and return -EAGAIN from tcf_chain_tp_insert() before calling tcf_chain0_head_change(). This would leverage existing cls_api functionality that automatically retries after releasing all references to chain/tp and obtaining them again instead of messing with qdisc api. However, since I still didn't fully grasp the issue it is hard for me to reason whether such approach would be possible to implement in this case.

Quoted 12 lines

Future Qdiscs that support RTNL-lockless cls_ops, if any, won't need this fix, as long as their ->chain_head_change() don't access out-of-Qdisc-scope data, like pointers in struct net_device.
Do you think this is the right way to go? Thanks!
[1] Thanks Hillf Danton for the hint:
    https://syzkaller.appspot.com/text?tag=Patch&x=10d7cd5bc80000
Thanks,
Peilin Ye

Peilin Ye

2023-04-27 17:36 UTC #9 lore raw

Hi Pedro, Vlad,

Quoted 11 lines · Vlad Buslov

Quoted 4 lines · Peilin Ye
As we can see there're interleaving mini_qdisc_pair_swap() calls between Qdisc A and B, causing all kinds of troubles, including the UAF (thread 2 writing to mini Qdisc a1's rcu_state after Qdisc A has already been freed) reported by syzbot.
Great analysis! However, it is still not quite clear to me how threads 1 and 2 access each other RCU state when q->miniqp is a private memory of the Qdisc, so 1 should only see A->miniqp and 2 only B->miniqp. And both miniqps should be protected from deallocation by reference that lockless RTM_NEWTFILTER obtains.

Thanks for taking a look!

To elaborate, p_miniq is a pointer of pointer of struct mini_Qdisc, initialized in ingress_init() to point to eth0->miniq_ingress, which isn't private to A or B.

In other words, both A->miniqp->p_miniq and B->miniqp->p_miniq point to eth0->miniq_ingress.

For your reference, roughly speaking, mini_qdisc_pair_swap() does this:

  miniq_old = dev->miniq_ingress;

  if (destroying) {
          dev->miniq_ingress = NULL;
  } else {
          rcu_wait();
          dev->miniq_ingress = miniq_new;
  }

if (miniq_old)

          miniq_old->rcu_state = ...

Quoted 9 lines · Peilin Ye

Thread 1 A's refcnt Thread 2
RTM_NEWQDISC (A, locked)
qdisc_create(A) 1
qdisc_graft(A) 9
RTM_NEWTFILTER (X, lockless)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
! mini_qdisc_pair_swap(A)

1. A adds its first filter,
miniq_old (eth0->miniq_ingress) is NULL, RCU wait starts,
RCU wait ends,
change eth0->miniq_ingress to A's mini Qdisc.

Quoted 7 lines

            |                        RTM_NEWQDISC (B, locked)
            |                    2    qdisc_graft(B)
            |                    1    notify_and_destroy(A)
            |
            |                        RTM_NEWTFILTER (Y, lockless)
            |                         tcf_chain0_head_change(B)
            |                       ! mini_qdisc_pair_swap(B)

2. B adds its first filter,
miniq_old (eth0->miniq_ingress) is A's mini Qdisc, RCU wait starts,

Quoted 4 lines

   tcf_block_release(A)          0             |
   qdisc_destroy(A)                            |
   tcf_chain0_head_change_cb_del(A)            |
 ! mini_qdisc_pair_swap(A)                     |

3. A destroys itself,
miniq_old (eth0->miniq_ingress) is A's mini Qdisc, (destroying, so no RCU wait)
change eth0->miniq_ingress to NULL, update miniq_old, or A's mini Qdisc's RCU state, A is freed.

2. RCU wait ends,
change eth0->miniq_ingress to B's mini Qdisc,
use-after-free: update miniq_old, or A's mini Qdisc's RCU state.

I hope this helps. Sorry I didn't go into details; this UAF isn't the only thing that is unacceptable here:

Consider B. We add a filter Y to B, expecting ingress packets on eth0 to go through Y. Then all of a sudden, A sets eth0->miniq_ingress to NULL during its destruction, so packets will not find Y at all on datapath (sch_handle_ingress()). New filter becomes invisible - this is already buggy enough :-/

So I think B's first call to mini_qdisc_pair_swap() should happen after A's last call (in ingress_destroy()), which is what I am trying to achieve here.

Thanks,
Peilin Ye

Vlad Buslov

2023-04-28 12:44 UTC #10 lore raw

Quoted 79 lines · Peilin Ye

Hi Pedro, Vlad,
Quoted 11 lines · Vlad Buslov
Quoted 4 lines · Peilin Ye
As we can see there're interleaving mini_qdisc_pair_swap() calls between Qdisc A and B, causing all kinds of troubles, including the UAF (thread 2 writing to mini Qdisc a1's rcu_state after Qdisc A has already been freed) reported by syzbot.
Great analysis! However, it is still not quite clear to me how threads 1 and 2 access each other RCU state when q->miniqp is a private memory of the Qdisc, so 1 should only see A->miniqp and 2 only B->miniqp. And both miniqps should be protected from deallocation by reference that lockless RTM_NEWTFILTER obtains.
Thanks for taking a look!
To elaborate, p_miniq is a pointer of pointer of struct mini_Qdisc, initialized in ingress_init() to point to eth0->miniq_ingress, which isn't private to A or B.
In other words, both A->miniqp->p_miniq and B->miniqp->p_miniq point to eth0->miniq_ingress.
For your reference, roughly speaking, mini_qdisc_pair_swap() does this:
  miniq_old = dev->miniq_ingress;

  if (destroying) {
          dev->miniq_ingress = NULL;
  } else {
          rcu_wait();
          dev->miniq_ingress = miniq_new;
  }
if (miniq_old)
          miniq_old->rcu_state = ...
Quoted 9 lines · Peilin Ye
Thread 1 A's refcnt Thread 2
RTM_NEWQDISC (A, locked)
qdisc_create(A) 1
qdisc_graft(A) 9
RTM_NEWTFILTER (X, lockless)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
! mini_qdisc_pair_swap(A)
1. A adds its first filter,
miniq_old (eth0->miniq_ingress) is NULL, RCU wait starts,
RCU wait ends,
change eth0->miniq_ingress to A's mini Qdisc.
Quoted 7 lines
            |                        RTM_NEWQDISC (B, locked)
            |                    2    qdisc_graft(B)
            |                    1    notify_and_destroy(A)
            |
            |                        RTM_NEWTFILTER (Y, lockless)
            |                         tcf_chain0_head_change(B)
            |                       ! mini_qdisc_pair_swap(B)
2. B adds its first filter,
miniq_old (eth0->miniq_ingress) is A's mini Qdisc, RCU wait starts,
Quoted 4 lines
   tcf_block_release(A)          0             |
   qdisc_destroy(A)                            |
   tcf_chain0_head_change_cb_del(A)            |
 ! mini_qdisc_pair_swap(A)                     |
3. A destroys itself,
miniq_old (eth0->miniq_ingress) is A's mini Qdisc, (destroying, so no RCU wait)
change eth0->miniq_ingress to NULL, update miniq_old, or A's mini Qdisc's RCU state, A is freed.

Quoted 3 lines

2. RCU wait ends,
change eth0->miniq_ingress to B's mini Qdisc,
use-after-free: update miniq_old, or A's mini Qdisc's RCU state.

Thanks for the clarification.

Quoted 10 lines

I hope this helps. Sorry I didn't go into details; this UAF isn't the only thing that is unacceptable here:
Consider B. We add a filter Y to B, expecting ingress packets on eth0 to go through Y. Then all of a sudden, A sets eth0->miniq_ingress to NULL during its destruction, so packets will not find Y at all on datapath (sch_handle_ingress()). New filter becomes invisible - this is already buggy enough :-/

Quoted 3 lines

So I think B's first call to mini_qdisc_pair_swap() should happen after A's last call (in ingress_destroy()), which is what I am trying to achieve here.

Makes sense to me.

Peilin Ye

2023-05-06 00:10 UTC #11 lore raw

cover net/sched: Fixes for sch_ingress and sch_clsact

[a] https://syzkaller.appspot.com/bug?extid=b53a9c0d1ea4ad62da8b

Hi all,

These are fixes for ingress and clsact Qdiscs:

[1,2/6]: ingress and clsact Qdiscs should only be created under ffff:fff1
[3/6]: Under ffff:fff1, only create ingress and clsact Qdiscs (for now,
at least)
[4/6]: After creating ingress and clsact Qdiscs under ffff:fff1, do not
graft them again to anywhere else (e.g. as the inner Qdisc of a TBF Qdisc)
[5/6]: Prepare for [6/6], do not reuse that for-loop in qdisc_graft()
for ingress and clsact Qdiscs
[6/6]: Fix use-after-free [a] in mini_qdisc_pair_swap()

Please review (especially [6/6]), thanks! Other tasks, including:

- prohibiting sch_ingress, sch_clsact etc. in default_qdisc
- more cleanups for qdisc_graft()

Will be done in separate patches.

Thanks,
Peilin Ye (6):
net/sched: sch_ingress: Only create under TC_H_INGRESS net/sched: sch_clsact: Only create under TC_H_CLSACT net/sched: Reserve TC_H_INGRESS (TC_H_CLSACT) for ingress (clsact)
Qdiscs
net/sched: Prohibit regrafting ingress or clsact Qdiscs net/sched: Refactor qdisc_graft() for ingress and clsact Qdiscs net/sched: qdisc_destroy() old ingress and clsact Qdiscs before
grafting

 include/net/sch_generic.h |  8 ++++++
 net/sched/sch_api.c       | 54 +++++++++++++++++++++++++++++----------
 net/sched/sch_generic.c   | 14 +++++++---
 net/sched/sch_ingress.c   | 10 ++++++--
 4 files changed, 67 insertions(+), 19 deletions(-)

Signature · 1 line

2.20.1

Peilin Ye

2023-05-06 00:12 UTC #12 lore raw

PATCH 1/6 net/sched: sch_ingress: Only create under TC_H_INGRESS

ingress Qdiscs are only supposed to be created under TC_H_INGRESS. Similar to mq_init(), return -EOPNOTSUPP if 'parent' is not TC_H_INGRESS.

Fixes 1da177e4c3f4 ("Linux-2.6.12-rc2")

Reported-by [email protected]

Link https://lore.kernel.org/netdev/[email protected] open here

Signed-off-by Peilin Ye <[email protected]>

---
 net/sched/sch_ingress.c | 3 +++
 1 file changed, 3 insertions(+)

net/sched/sch_ingress.c +3 -0

index 84838128b9c5..3d71f7a3b4ad 100644
@@ -80,6 +80,9 @@ static int ingress_init(struct Qdisc *sch, struct nlattr *opt,
 	struct net_device *dev = qdisc_dev(sch);
 	int err;
 
+	if (sch->parent != TC_H_INGRESS)
+		return -EOPNOTSUPP;
+
 	net_inc_ingress_queue();
 
 	mini_qdisc_pair_init(&q->miniqp, sch, &dev->miniq_ingress);

Signature · 1 line

2.20.1

Peilin Ye

2023-05-06 00:13 UTC #14 lore raw

PATCH 2/6 net/sched: sch_clsact: Only create under TC_H_CLSACT

clsact Qdiscs are only supposed to be created under TC_H_CLSACT (which equals TC_H_INGRESS). Return -EOPNOTSUPP if 'parent' is not TC_H_CLSACT.

Fixes 1f211a1b929c ("net, sched: add clsact qdisc")

Signed-off-by Peilin Ye <[email protected]>

---
 net/sched/sch_ingress.c | 3 +++
 1 file changed, 3 insertions(+)

net/sched/sch_ingress.c +3 -0

index 3d71f7a3b4ad..13218a1fe4a5 100644
@@ -222,6 +222,9 @@ static int clsact_init(struct Qdisc *sch, struct nlattr *opt,
 	struct net_device *dev = qdisc_dev(sch);
 	int err;
 
+	if (sch->parent != TC_H_CLSACT)
+		return -EOPNOTSUPP;
+
 	net_inc_ingress_queue();
 	net_inc_egress_queue();

Signature · 1 line

2.20.1

Peilin Ye

2023-05-06 00:14 UTC #16 lore raw

PATCH 3/6 net/sched: Reserve TC_H_INGRESS (TC_H_CLSACT) for ingress (clsact) Qdiscs

Currently it is possible to add e.g. an HTB Qdisc under ffff:fff1 (TC_H_INGRESS, TC_H_CLSACT):

  $ ip link add name ifb0 type ifb
  $ tc qdisc add dev ifb0 parent ffff:fff1 htb
  $ tc qdisc add dev ifb0 clsact
  Error: Exclusivity flag on, cannot modify.
  $ drgn
  ...

Quoted 3 lines

Quoted 3 lines
Quoted 3 lines
ifb0 = netdev_get_by_name(prog, "ifb0")
qdisc = ifb0.ingress_queue.qdisc_sleeping
print(qdisc.ops.id.string_().decode())

htb

Quoted 1 line

Quoted 1 line
Quoted 1 line
qdisc.flags.value_() # TCQ_F_INGRESS

Only allow ingress and clsact Qdiscs under ffff:fff1. Return -EINVAL for everything else. Make TCQ_F_INGRESS a static flag of ingress and clsact Qdiscs.

Fixes 1da177e4c3f4 ("Linux-2.6.12-rc2")

Fixes 1f211a1b929c ("net, sched: add clsact qdisc")

Signed-off-by Peilin Ye <[email protected]>

---
 net/sched/sch_api.c     | 7 ++++++-
 net/sched/sch_ingress.c | 4 ++--
 2 files changed, 8 insertions(+), 3 deletions(-)

net/sched/sch_api.c +6 -1

index fdb8f429333d..383195955b7d 100644
@@ -1252,7 +1252,12 @@ static struct Qdisc *qdisc_create(struct net_device *dev,
 	sch->parent = parent;
 
 	if (handle == TC_H_INGRESS) {
-		sch->flags |= TCQ_F_INGRESS;
+		if (!(sch->flags & TCQ_F_INGRESS)) {
+			NL_SET_ERR_MSG(extack,
+				       "Specified parent ID is reserved for ingress and clsact Qdiscs");
+			err = -EINVAL;
+			goto err_out3;
+		}
 		handle = TC_H_MAKE(TC_H_INGRESS, 0);
 	} else {
 		if (handle == 0) {

net/sched/sch_ingress.c +2 -2

index 13218a1fe4a5..caea51e0d4e9 100644
@@ -137,7 +137,7 @@ static struct Qdisc_ops ingress_qdisc_ops __read_mostly = {
 	.cl_ops			=	&ingress_class_ops,
 	.id			=	"ingress",
 	.priv_size		=	sizeof(struct ingress_sched_data),
-	.static_flags		=	TCQ_F_CPUSTATS,
+	.static_flags		=	TCQ_F_INGRESS | TCQ_F_CPUSTATS,
 	.init			=	ingress_init,
 	.destroy		=	ingress_destroy,
 	.dump			=	ingress_dump,

@@ -275,7 +275,7 @@ static struct Qdisc_ops clsact_qdisc_ops __read_mostly = {
 	.cl_ops			=	&clsact_class_ops,
 	.id			=	"clsact",
 	.priv_size		=	sizeof(struct clsact_sched_data),
-	.static_flags		=	TCQ_F_CPUSTATS,
+	.static_flags		=	TCQ_F_INGRESS | TCQ_F_CPUSTATS,
 	.init			=	clsact_init,
 	.destroy		=	clsact_destroy,
 	.dump			=	ingress_dump,

Signature · 1 line

2.20.1

Peilin Ye

2023-05-06 00:15 UTC #18 lore raw

PATCH 4/6 net/sched: Prohibit regrafting ingress or clsact Qdiscs

Currently, after creating an ingress (or clsact) Qdisc and grafting it under TC_H_INGRESS (TC_H_CLSACT), it is possible to graft it again under e.g. a TBF Qdisc:

  $ ip link add ifb0 type ifb
  $ tc qdisc add dev ifb0 handle 1: root tbf rate 20kbit buffer 1600 limit 3000
  $ tc qdisc add dev ifb0 clsact
  $ tc qdisc link dev ifb0 handle ffff: parent 1:1
  $ tc qdisc show dev ifb0
  qdisc tbf 1: root refcnt 2 rate 20Kbit burst 1600b lat 560.0ms
  qdisc clsact ffff: parent ffff:fff1 refcnt 2
                                      ^^^^^^^^

clsact's refcount has increased: it is now grafted under both TC_H_CLSACT and 1:1.

ingress and clsact Qdiscs should only be used under TC_H_INGRESS (TC_H_CLSACT). Prohibit regrafting them.

Fixes 1da177e4c3f4 ("Linux-2.6.12-rc2")

Fixes 1f211a1b929c ("net, sched: add clsact qdisc")

Signed-off-by Peilin Ye <[email protected]>

---
 net/sched/sch_api.c | 5 +++++
 1 file changed, 5 insertions(+)

net/sched/sch_api.c +5 -0

index 383195955b7d..49b9c1bbfdd9 100644
@@ -1596,6 +1596,11 @@ static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
 					NL_SET_ERR_MSG(extack, "Invalid qdisc name");
 					return -EINVAL;
 				}
+				if (q->flags & TCQ_F_INGRESS) {
+					NL_SET_ERR_MSG(extack,
+						       "Cannot regraft ingress or clsact Qdiscs");
+					return -EINVAL;
+				}
 				if (q == p ||
 				    (p && check_loop(q, p, 0))) {
 					NL_SET_ERR_MSG(extack, "Qdisc parent/child loop detected");

Signature · 1 line

2.20.1

Peilin Ye

2023-05-06 00:15 UTC #20 lore raw

PATCH 5/6 net/sched: Refactor qdisc_graft() for ingress and clsact Qdiscs

Grafting ingress and clsact Qdiscs does not need a for-loop in qdisc_graft(). Refactor it. No functional changes intended.

Signed-off-by Peilin Ye <[email protected]>

---
 net/sched/sch_api.c | 20 ++++++++++----------
 1 file changed, 10 insertions(+), 10 deletions(-)

net/sched/sch_api.c +10 ~~-10~~

index 49b9c1bbfdd9..f72a581666a2 100644
@@ -1073,12 +1073,12 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
 
 	if (parent == NULL) {
 		unsigned int i, num_q, ingress;
+		struct netdev_queue *dev_queue;
 
 		ingress = 0;
 		num_q = dev->num_tx_queues;
 		if ((q && q->flags & TCQ_F_INGRESS) ||
 		    (new && new->flags & TCQ_F_INGRESS)) {
-			num_q = 1;
 			ingress = 1;
 			if (!dev_ingress_queue(dev)) {
 				NL_SET_ERR_MSG(extack, "Device does not have an ingress queue");

@@ -1094,18 +1094,18 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
 		if (new && new->ops->attach && !ingress)
 			goto skip;
 
-		for (i = 0; i < num_q; i++) {
-			struct netdev_queue *dev_queue = dev_ingress_queue(dev);
-
-			if (!ingress)
+		if (!ingress) {
+			for (i = 0; i < num_q; i++) {
 				dev_queue = netdev_get_tx_queue(dev, i);
+				old = dev_graft_qdisc(dev_queue, new);
 
-			old = dev_graft_qdisc(dev_queue, new);
-			if (new && i > 0)
-				qdisc_refcount_inc(new);
-
-			if (!ingress)
+				if (new && i > 0)
+					qdisc_refcount_inc(new);
 				qdisc_put(old);
+			}
+		} else {
+			dev_queue = dev_ingress_queue(dev);
+			old = dev_graft_qdisc(dev_queue, new);
 		}
 
 skip:

Signature · 1 line

2.20.1

Peilin Ye

2023-05-06 00:16 UTC #24 lore raw

PATCH 6/6 net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Link https://lore.kernel.org/netdev/[email protected] open here

mini_Qdisc_pair::p_miniq is a double pointer to mini_Qdisc, initialized in ingress_init() to point to net_device::miniq_ingress. ingress Qdiscs access this per-net_device pointer in mini_qdisc_pair_swap(). Similar for clsact Qdiscs and miniq_egress.

Unfortunately, after introducing RTNL-lockless RTM_{NEW,DEL,GET}TFILTER requests, when e.g. replacing ingress (clsact) Qdiscs, the old Qdisc could access the same miniq_{in,e}gress pointer(s) concurrently with the new Qdisc, causing race conditions [1] including a use-after-free in mini_qdisc_pair_swap() reported by syzbot:

 BUG: KASAN: slab-use-after-free in mini_qdisc_pair_swap+0x1c2/0x1f0 net/sched/sch_generic.c:1573
 Write of size 8 at addr ffff888045b31308 by task syz-executor690/14901
...
 Call Trace:
  <TASK>
  __dump_stack lib/dump_stack.c:88 [inline]
  dump_stack_lvl+0xd9/0x150 lib/dump_stack.c:106
  print_address_description.constprop.0+0x2c/0x3c0 mm/kasan/report.c:319
  print_report mm/kasan/report.c:430 [inline]
  kasan_report+0x11c/0x130 mm/kasan/report.c:536
  mini_qdisc_pair_swap+0x1c2/0x1f0 net/sched/sch_generic.c:1573
  tcf_chain_head_change_item net/sched/cls_api.c:495 [inline]
  tcf_chain0_head_change.isra.0+0xb9/0x120 net/sched/cls_api.c:509
  tcf_chain_tp_insert net/sched/cls_api.c:1826 [inline]
  tcf_chain_tp_insert_unique net/sched/cls_api.c:1875 [inline]
  tc_new_tfilter+0x1de6/0x2290 net/sched/cls_api.c:2266

...

The new (ingress or clsact) Qdisc should only call mini_qdisc_pair_swap() after the old Qdisc's last call (in {ingress,clsact}_destroy()) has finished.

To achieve this, in qdisc_graft(), return -EBUSY if the old (ingress or clsact) Qdisc has ongoing RTNL-lockless filter requests, and call qdisc_destroy() for "old" before grafting "new".

Introduce qdisc_refcount_dec_if_one() as the counterpart of qdisc_refcount_inc_nz() used for RTNL-lockless filter requests. Introduce a non-static version of qdisc_destroy() that does a TCQ_F_BUILTIN check, just like qdisc_put() etc.

[1] To illustrate, the syzkaller reproducer adds ingress Qdiscs under TC_H_ROOT (no longer possible after patch "net/sched: sch_ingress: Only create under TC_H_INGRESS") on eth0 that has 8 transmission queues:

Thread 1 creates ingress Qdisc A (containing mini Qdisc a1 and a2), then adds a flower filter X to A.

Thread 2 creates another ingress Qdisc B (containing mini Qdisc b1 and b2) to replace A, then adds a flower filter Y to B.

Thread 1 A's refcnt Thread 2
RTM_NEWQDISC (A, RTNL-locked)
qdisc_create(A) 1
qdisc_graft(A) 9

RTM_NEWTFILTER (X, RTNL-lockless)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
mini_qdisc_pair_swap(A) (1st)
|
| RTM_NEWQDISC (B, RTNL-locked)
RCU 2 qdisc_graft(B)
| 1 notify_and_destroy(A)
|
tcf_block_release(A) 0 RTM_NEWTFILTER (Y, RTNL-lockless)
qdisc_destroy(A) tcf_chain0_head_change(B)
tcf_chain0_head_change_cb_del(A) mini_qdisc_pair_swap(B) (2nd)
mini_qdisc_pair_swap(A) (3rd) |
... ...

Here, B calls mini_qdisc_pair_swap(), pointing eth0->miniq_ingress to its mini Qdisc, b1. Then, A calls mini_qdisc_pair_swap() again during ingress_destroy(), setting eth0->miniq_ingress to NULL, so ingress packets on eth0 will not find filter Y in sch_handle_ingress().

This is just one of the possible consequences of concurrently accessing net_device::miniq_{in,e}gress pointers. The point is clear, however:
B's first call to mini_qdisc_pair_swap() should take place after A's last call, in qdisc_destroy().

Fixes 7a096d579e8e ("net: sched: ingress: set 'unlocked' flag for Qdisc ops")

Fixes 87f373921c4e ("net: sched: ingress: set 'unlocked' flag for clsact Qdisc ops")

Reported-by [email protected]

Cc Hillf Danton <[email protected]>

Signed-off-by Peilin Ye <[email protected]>

---
 include/net/sch_generic.h |  8 ++++++++
 net/sched/sch_api.c       | 26 +++++++++++++++++++++-----
 net/sched/sch_generic.c   | 14 +++++++++++---
 3 files changed, 40 insertions(+), 8 deletions(-)

include/net/sch_generic.h +8 -0

index fab5ba3e61b7..3e9cc43cbc90 100644
@@ -137,6 +137,13 @@ static inline void qdisc_refcount_inc(struct Qdisc *qdisc)
 	refcount_inc(&qdisc->refcnt);
 }
 
+static inline bool qdisc_refcount_dec_if_one(struct Qdisc *qdisc)
+{
+	if (qdisc->flags & TCQ_F_BUILTIN)
+		return true;
+	return refcount_dec_if_one(&qdisc->refcnt);
+}
+
 /* Intended to be used by unlocked users, when concurrent qdisc release is
  * possible.
  */

@@ -652,6 +659,7 @@ void dev_deactivate_many(struct list_head *head);
 struct Qdisc *dev_graft_qdisc(struct netdev_queue *dev_queue,
 			      struct Qdisc *qdisc);
 void qdisc_reset(struct Qdisc *qdisc);
+void qdisc_destroy(struct Qdisc *qdisc);
 void qdisc_put(struct Qdisc *qdisc);
 void qdisc_put_unlocked(struct Qdisc *qdisc);
 void qdisc_tree_reduce_backlog(struct Qdisc *qdisc, int n, int len);

net/sched/sch_api.c +21 -5

index f72a581666a2..a2d07bc8ded6 100644
@@ -1080,10 +1080,20 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
 		if ((q && q->flags & TCQ_F_INGRESS) ||
 		    (new && new->flags & TCQ_F_INGRESS)) {
 			ingress = 1;
-			if (!dev_ingress_queue(dev)) {
+			dev_queue = dev_ingress_queue(dev);
+			if (!dev_queue) {
 				NL_SET_ERR_MSG(extack, "Device does not have an ingress queue");
 				return -ENOENT;
 			}
+
+			/* This is the counterpart of that qdisc_refcount_inc_nz() call in
+			 * __tcf_qdisc_find() for RTNL-lockless filter requests.
+			 */
+			if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping)) {
+				NL_SET_ERR_MSG(extack,
+					       "Current ingress or clsact Qdisc has ongoing filter request(s)");
+				return -EBUSY;
+			}
 		}
 
 		if (dev->flags & IFF_UP)

@@ -1104,8 +1114,16 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
 				qdisc_put(old);
 			}
 		} else {
-			dev_queue = dev_ingress_queue(dev);
-			old = dev_graft_qdisc(dev_queue, new);
+			old = dev_graft_qdisc(dev_queue, NULL);
+
+			/* {ingress,clsact}_destroy() "old" before grafting "new" to avoid
+			 * unprotected concurrent accesses to net_device::miniq_{in,e}gress
+			 * pointer(s) in mini_qdisc_pair_swap().
+			 */
+			qdisc_notify(net, skb, n, classid, old, new, extack);
+			qdisc_destroy(old);
+
+			dev_graft_qdisc(dev_queue, new);
 		}
 
 skip:

@@ -1119,8 +1137,6 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
 
 			if (new && new->ops->attach)
 				new->ops->attach(new);
-		} else {
-			notify_and_destroy(net, skb, n, classid, old, new, extack);
 		}
 
 		if (dev->flags & IFF_UP)

net/sched/sch_generic.c +11 -3

index 37e41f972f69..e14ed47f961c 100644
@@ -1046,7 +1046,7 @@ static void qdisc_free_cb(struct rcu_head *head)
 	qdisc_free(q);
 }
 
-static void qdisc_destroy(struct Qdisc *qdisc)
+static void __qdisc_destroy(struct Qdisc *qdisc)
 {
 	const struct Qdisc_ops  *ops = qdisc->ops;

@@ -1070,6 +1070,14 @@ static void qdisc_destroy(struct Qdisc *qdisc)
 	call_rcu(&qdisc->rcu, qdisc_free_cb);
 }
 
+void qdisc_destroy(struct Qdisc *qdisc)
+{
+	if (qdisc->flags & TCQ_F_BUILTIN)
+		return;
+
+	__qdisc_destroy(qdisc);
+}
+
 void qdisc_put(struct Qdisc *qdisc)
 {
 	if (!qdisc)

@@ -1079,7 +1087,7 @@ void qdisc_put(struct Qdisc *qdisc)
 	    !refcount_dec_and_test(&qdisc->refcnt))
 		return;
 
-	qdisc_destroy(qdisc);
+	__qdisc_destroy(qdisc);
 }
 EXPORT_SYMBOL(qdisc_put);

@@ -1094,7 +1102,7 @@ void qdisc_put_unlocked(struct Qdisc *qdisc)
 	    !refcount_dec_and_rtnl_lock(&qdisc->refcnt))
 		return;
 
-	qdisc_destroy(qdisc);
+	__qdisc_destroy(qdisc);
 	rtnl_unlock();
 }
 EXPORT_SYMBOL(qdisc_put_unlocked);

Signature · 1 line

2.20.1

Jamal Hadi Salim

maintainer Reviewed-by Acked-by on v1 1/6

2023-05-08 11:23 UTC #13 lore raw

Re: [PATCH net 1/6] net/sched: sch_ingress: Only create under TC_H_INGRESS

Quoted 9 lines · Peilin Ye

ingress Qdiscs are only supposed to be created under TC_H_INGRESS. Similar to mq_init(), return -EOPNOTSUPP if 'parent' is not TC_H_INGRESS.
Fixes 1da177e4c3f4 ("Linux-2.6.12-rc2")
Reported-by [email protected]
Link https://lore.kernel.org/netdev/[email protected] open here
Signed-off-by Peilin Ye <[email protected]>

cheers,
jamal

Quoted 21 lines

---
 net/sched/sch_ingress.c | 3 +++
 1 file changed, 3 insertions(+)

net/sched/sch_ingress.c +3 -1

index 84838128b9c5..3d71f7a3b4ad 100644
@@ -80,6 +80,9 @@ static int ingress_init(struct Qdisc *sch, struct nlattr *opt,
        struct net_device *dev = qdisc_dev(sch);
        int err;
 
+       if (sch->parent != TC_H_INGRESS)
+               return -EOPNOTSUPP;
+
        net_inc_ingress_queue();
 
        mini_qdisc_pair_init(&q->miniqp, sch, &dev->miniq_ingress);
--

2.20.1

Jamal Hadi Salim

maintainer Reviewed-by Acked-by on v1 2/6

2023-05-08 11:23 UTC #15 lore raw

Re: [PATCH net 2/6] net/sched: sch_clsact: Only create under TC_H_CLSACT

Quoted 7 lines · Peilin Ye

clsact Qdiscs are only supposed to be created under TC_H_CLSACT (which equals TC_H_INGRESS). Return -EOPNOTSUPP if 'parent' is not TC_H_CLSACT.
Fixes 1f211a1b929c ("net, sched: add clsact qdisc")
Signed-off-by Peilin Ye <[email protected]>

cheers,
jamal

Quoted 21 lines

---
 net/sched/sch_ingress.c | 3 +++
 1 file changed, 3 insertions(+)

net/sched/sch_ingress.c +3 -1

index 3d71f7a3b4ad..13218a1fe4a5 100644
@@ -222,6 +222,9 @@ static int clsact_init(struct Qdisc *sch, struct nlattr *opt,
        struct net_device *dev = qdisc_dev(sch);
        int err;
 
+       if (sch->parent != TC_H_CLSACT)
+               return -EOPNOTSUPP;
+
        net_inc_ingress_queue();
        net_inc_egress_queue();
 
--

2.20.1

Jamal Hadi Salim

maintainer Reviewed-by Acked-by on v1 3/6

2023-05-08 11:24 UTC #17 lore raw

Re: [PATCH net 3/6] net/sched: Reserve TC_H_INGRESS (TC_H_CLSACT) for ingress (clsact) Qdiscs

Quoted 17 lines · Peilin Ye

Currently it is possible to add e.g. an HTB Qdisc under ffff:fff1 (TC_H_INGRESS, TC_H_CLSACT):
  $ ip link add name ifb0 type ifb
  $ tc qdisc add dev ifb0 parent ffff:fff1 htb
  $ tc qdisc add dev ifb0 clsact
  Error: Exclusivity flag on, cannot modify.
  $ drgn
  ...
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
ifb0 = netdev_get_by_name(prog, "ifb0")
qdisc = ifb0.ingress_queue.qdisc_sleeping
print(qdisc.ops.id.string_().decode())
htb
Quoted 1 line
Quoted 1 line
Quoted 1 line
qdisc.flags.value_() # TCQ_F_INGRESS
2

Quoted 7 lines

Only allow ingress and clsact Qdiscs under ffff:fff1. Return -EINVAL for everything else. Make TCQ_F_INGRESS a static flag of ingress and clsact Qdiscs.
Fixes 1da177e4c3f4 ("Linux-2.6.12-rc2")
Fixes 1f211a1b929c ("net, sched: add clsact qdisc")
Signed-off-by Peilin Ye <[email protected]>

cheers,
jamal

Quoted 48 lines

---
 net/sched/sch_api.c     | 7 ++++++-
 net/sched/sch_ingress.c | 4 ++--
 2 files changed, 8 insertions(+), 3 deletions(-)

net/sched/sch_api.c +6 -1

index fdb8f429333d..383195955b7d 100644
@@ -1252,7 +1252,12 @@ static struct Qdisc *qdisc_create(struct net_device *dev,
        sch->parent = parent;
 
        if (handle == TC_H_INGRESS) {
-               sch->flags |= TCQ_F_INGRESS;
+               if (!(sch->flags & TCQ_F_INGRESS)) {
+                       NL_SET_ERR_MSG(extack,
+                                      "Specified parent ID is reserved for ingress and clsact Qdiscs");
+                       err = -EINVAL;
+                       goto err_out3;
+               }
                handle = TC_H_MAKE(TC_H_INGRESS, 0);
        } else {
                if (handle == 0) {

net/sched/sch_ingress.c +2 -3

index 13218a1fe4a5..caea51e0d4e9 100644
@@ -137,7 +137,7 @@ static struct Qdisc_ops ingress_qdisc_ops __read_mostly = {
        .cl_ops                 =       &ingress_class_ops,
        .id                     =       "ingress",
        .priv_size              =       sizeof(struct ingress_sched_data),
-       .static_flags           =       TCQ_F_CPUSTATS,
+       .static_flags           =       TCQ_F_INGRESS | TCQ_F_CPUSTATS,
        .init                   =       ingress_init,
        .destroy                =       ingress_destroy,
        .dump                   =       ingress_dump,

@@ -275,7 +275,7 @@ static struct Qdisc_ops clsact_qdisc_ops __read_mostly = {
        .cl_ops                 =       &clsact_class_ops,
        .id                     =       "clsact",
        .priv_size              =       sizeof(struct clsact_sched_data),
-       .static_flags           =       TCQ_F_CPUSTATS,
+       .static_flags           =       TCQ_F_INGRESS | TCQ_F_CPUSTATS,
        .init                   =       clsact_init,
        .destroy                =       clsact_destroy,
        .dump                   =       ingress_dump,
--

2.20.1

Jamal Hadi Salim

maintainer Reviewed-by Acked-by on v1 4/6

2023-05-08 11:24 UTC #19 lore raw

Re: [PATCH net 4/6] net/sched: Prohibit regrafting ingress or clsact Qdiscs

Quoted 17 lines · Peilin Ye

Currently, after creating an ingress (or clsact) Qdisc and grafting it under TC_H_INGRESS (TC_H_CLSACT), it is possible to graft it again under e.g. a TBF Qdisc:
  $ ip link add ifb0 type ifb
  $ tc qdisc add dev ifb0 handle 1: root tbf rate 20kbit buffer 1600 limit 3000
  $ tc qdisc add dev ifb0 clsact
  $ tc qdisc link dev ifb0 handle ffff: parent 1:1
  $ tc qdisc show dev ifb0
  qdisc tbf 1: root refcnt 2 rate 20Kbit burst 1600b lat 560.0ms
  qdisc clsact ffff: parent ffff:fff1 refcnt 2
                                      ^^^^^^^^
clsact's refcount has increased: it is now grafted under both TC_H_CLSACT and 1:1.

Quoted 6 lines

ingress and clsact Qdiscs should only be used under TC_H_INGRESS (TC_H_CLSACT). Prohibit regrafting them.
Fixes 1da177e4c3f4 ("Linux-2.6.12-rc2")
Fixes 1f211a1b929c ("net, sched: add clsact qdisc")
Signed-off-by Peilin Ye <[email protected]>

cheers,
jamal

Quoted 23 lines

---
 net/sched/sch_api.c | 5 +++++
 1 file changed, 5 insertions(+)

net/sched/sch_api.c +5 -1

index 383195955b7d..49b9c1bbfdd9 100644
@@ -1596,6 +1596,11 @@ static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
                                        NL_SET_ERR_MSG(extack, "Invalid qdisc name");
                                        return -EINVAL;
                                }
+                               if (q->flags & TCQ_F_INGRESS) {
+                                       NL_SET_ERR_MSG(extack,
+                                                      "Cannot regraft ingress or clsact Qdiscs");
+                                       return -EINVAL;
+                               }
                                if (q == p ||
                                    (p && check_loop(q, p, 0))) {
                                        NL_SET_ERR_MSG(extack, "Qdisc parent/child loop detected");
--

2.20.1

Jamal Hadi Salim

maintainer Reviewed-by Acked-by on v1 5/6

2023-05-08 11:29 UTC #21 lore raw

Re: [PATCH net 5/6] net/sched: Refactor qdisc_graft() for ingress and clsact Qdiscs

Quoted 5 lines · Peilin Ye

Grafting ingress and clsact Qdiscs does not need a for-loop in qdisc_graft(). Refactor it. No functional changes intended.
Signed-off-by Peilin Ye <[email protected]>

Fixed John's email address.

This one i am not so sure; num_q = 1 implies it will run on the for loop only once. I am not sure it improves readability either. Anyways for the effort you put into it i am tossing a coin and saying:

cheers,
jamal

Quoted 52 lines

 net/sched/sch_api.c | 20 ++++++++++----------
 1 file changed, 10 insertions(+), 10 deletions(-)

net/sched/sch_api.c +10 ~~-11~~

index 49b9c1bbfdd9..f72a581666a2 100644
@@ -1073,12 +1073,12 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
 
        if (parent == NULL) {
                unsigned int i, num_q, ingress;
+               struct netdev_queue *dev_queue;
 
                ingress = 0;
                num_q = dev->num_tx_queues;
                if ((q && q->flags & TCQ_F_INGRESS) ||
                    (new && new->flags & TCQ_F_INGRESS)) {
-                       num_q = 1;
                        ingress = 1;
                        if (!dev_ingress_queue(dev)) {
                                NL_SET_ERR_MSG(extack, "Device does not have an ingress queue");

@@ -1094,18 +1094,18 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
                if (new && new->ops->attach && !ingress)
                        goto skip;
 
-               for (i = 0; i < num_q; i++) {
-                       struct netdev_queue *dev_queue = dev_ingress_queue(dev);
-
-                       if (!ingress)
+               if (!ingress) {
+                       for (i = 0; i < num_q; i++) {
                                dev_queue = netdev_get_tx_queue(dev, i);
+                               old = dev_graft_qdisc(dev_queue, new);
 
-                       old = dev_graft_qdisc(dev_queue, new);
-                       if (new && i > 0)
-                               qdisc_refcount_inc(new);
-
-                       if (!ingress)
+                               if (new && i > 0)
+                                       qdisc_refcount_inc(new);
                                qdisc_put(old);
+                       }
+               } else {
+                       dev_queue = dev_ingress_queue(dev);
+                       old = dev_graft_qdisc(dev_queue, new);
                }
 
 skip:
--

2.20.1

Jamal Hadi Salim

maintainer Reviewed-by Acked-by on v1 6/6

2023-05-08 11:32 UTC #25 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 83 lines · Peilin Ye

mini_Qdisc_pair::p_miniq is a double pointer to mini_Qdisc, initialized in ingress_init() to point to net_device::miniq_ingress. ingress Qdiscs access this per-net_device pointer in mini_qdisc_pair_swap(). Similar for clsact Qdiscs and miniq_egress.
Unfortunately, after introducing RTNL-lockless RTM_{NEW,DEL,GET}TFILTER requests, when e.g. replacing ingress (clsact) Qdiscs, the old Qdisc could access the same miniq_{in,e}gress pointer(s) concurrently with the new Qdisc, causing race conditions [1] including a use-after-free in mini_qdisc_pair_swap() reported by syzbot:
 BUG: KASAN: slab-use-after-free in mini_qdisc_pair_swap+0x1c2/0x1f0 net/sched/sch_generic.c:1573
 Write of size 8 at addr ffff888045b31308 by task syz-executor690/14901
...
 Call Trace:
  <TASK>
  __dump_stack lib/dump_stack.c:88 [inline]
  dump_stack_lvl+0xd9/0x150 lib/dump_stack.c:106
  print_address_description.constprop.0+0x2c/0x3c0 mm/kasan/report.c:319
  print_report mm/kasan/report.c:430 [inline]
  kasan_report+0x11c/0x130 mm/kasan/report.c:536
  mini_qdisc_pair_swap+0x1c2/0x1f0 net/sched/sch_generic.c:1573
  tcf_chain_head_change_item net/sched/cls_api.c:495 [inline]
  tcf_chain0_head_change.isra.0+0xb9/0x120 net/sched/cls_api.c:509
  tcf_chain_tp_insert net/sched/cls_api.c:1826 [inline]
  tcf_chain_tp_insert_unique net/sched/cls_api.c:1875 [inline]
  tc_new_tfilter+0x1de6/0x2290 net/sched/cls_api.c:2266
...
The new (ingress or clsact) Qdisc should only call mini_qdisc_pair_swap() after the old Qdisc's last call (in {ingress,clsact}_destroy()) has finished.
To achieve this, in qdisc_graft(), return -EBUSY if the old (ingress or clsact) Qdisc has ongoing RTNL-lockless filter requests, and call qdisc_destroy() for "old" before grafting "new".
Introduce qdisc_refcount_dec_if_one() as the counterpart of qdisc_refcount_inc_nz() used for RTNL-lockless filter requests. Introduce a non-static version of qdisc_destroy() that does a TCQ_F_BUILTIN check, just like qdisc_put() etc.
[1] To illustrate, the syzkaller reproducer adds ingress Qdiscs under TC_H_ROOT (no longer possible after patch "net/sched: sch_ingress: Only create under TC_H_INGRESS") on eth0 that has 8 transmission queues:
Thread 1 creates ingress Qdisc A (containing mini Qdisc a1 and a2), then adds a flower filter X to A.
Thread 2 creates another ingress Qdisc B (containing mini Qdisc b1 and b2) to replace A, then adds a flower filter Y to B.
Thread 1 A's refcnt Thread 2
RTM_NEWQDISC (A, RTNL-locked)
qdisc_create(A) 1
qdisc_graft(A) 9
RTM_NEWTFILTER (X, RTNL-lockless)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
mini_qdisc_pair_swap(A) (1st)
|
| RTM_NEWQDISC (B, RTNL-locked)
RCU 2 qdisc_graft(B)
| 1 notify_and_destroy(A)
|
tcf_block_release(A) 0 RTM_NEWTFILTER (Y, RTNL-lockless)
qdisc_destroy(A) tcf_chain0_head_change(B)
tcf_chain0_head_change_cb_del(A) mini_qdisc_pair_swap(B) (2nd)
mini_qdisc_pair_swap(A) (3rd) |
... ...
Here, B calls mini_qdisc_pair_swap(), pointing eth0->miniq_ingress to its mini Qdisc, b1. Then, A calls mini_qdisc_pair_swap() again during ingress_destroy(), setting eth0->miniq_ingress to NULL, so ingress packets on eth0 will not find filter Y in sch_handle_ingress().
This is just one of the possible consequences of concurrently accessing net_device::miniq_{in,e}gress pointers. The point is clear, however:
B's first call to mini_qdisc_pair_swap() should take place after A's last call, in qdisc_destroy().

Quoted 6 lines

Fixes 7a096d579e8e ("net: sched: ingress: set 'unlocked' flag for Qdisc ops")
Fixes 87f373921c4e ("net: sched: ingress: set 'unlocked' flag for clsact Qdisc ops")
Reported-by [email protected]
Link https://lore.kernel.org/netdev/[email protected] open here
Cc Hillf Danton <[email protected]>
Signed-off-by Peilin Ye <[email protected]>

Thanks for the excellent analysis Peilin and for chasing this to the end. I have no doubt it was a lot of fun! ;->

cheers,
jamal

Quoted 135 lines

---
 include/net/sch_generic.h |  8 ++++++++
 net/sched/sch_api.c       | 26 +++++++++++++++++++++-----
 net/sched/sch_generic.c   | 14 +++++++++++---
 3 files changed, 40 insertions(+), 8 deletions(-)

include/net/sch_generic.h +8 -0

index fab5ba3e61b7..3e9cc43cbc90 100644
@@ -137,6 +137,13 @@ static inline void qdisc_refcount_inc(struct Qdisc *qdisc)
        refcount_inc(&qdisc->refcnt);
 }
 
+static inline bool qdisc_refcount_dec_if_one(struct Qdisc *qdisc)
+{
+       if (qdisc->flags & TCQ_F_BUILTIN)
+               return true;
+       return refcount_dec_if_one(&qdisc->refcnt);
+}
+
 /* Intended to be used by unlocked users, when concurrent qdisc release is
  * possible.
  */

@@ -652,6 +659,7 @@ void dev_deactivate_many(struct list_head *head);
 struct Qdisc *dev_graft_qdisc(struct netdev_queue *dev_queue,
                              struct Qdisc *qdisc);
 void qdisc_reset(struct Qdisc *qdisc);
+void qdisc_destroy(struct Qdisc *qdisc);
 void qdisc_put(struct Qdisc *qdisc);
 void qdisc_put_unlocked(struct Qdisc *qdisc);
 void qdisc_tree_reduce_backlog(struct Qdisc *qdisc, int n, int len);

net/sched/sch_api.c +21 -5

index f72a581666a2..a2d07bc8ded6 100644
@@ -1080,10 +1080,20 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
                if ((q && q->flags & TCQ_F_INGRESS) ||
                    (new && new->flags & TCQ_F_INGRESS)) {
                        ingress = 1;
-                       if (!dev_ingress_queue(dev)) {
+                       dev_queue = dev_ingress_queue(dev);
+                       if (!dev_queue) {
                                NL_SET_ERR_MSG(extack, "Device does not have an ingress queue");
                                return -ENOENT;
                        }
+
+                       /* This is the counterpart of that qdisc_refcount_inc_nz() call in
+                        * __tcf_qdisc_find() for RTNL-lockless filter requests.
+                        */
+                       if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping)) {
+                               NL_SET_ERR_MSG(extack,
+                                              "Current ingress or clsact Qdisc has ongoing filter request(s)");
+                               return -EBUSY;
+                       }
                }
 
                if (dev->flags & IFF_UP)

@@ -1104,8 +1114,16 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
                                qdisc_put(old);
                        }
                } else {
-                       dev_queue = dev_ingress_queue(dev);
-                       old = dev_graft_qdisc(dev_queue, new);
+                       old = dev_graft_qdisc(dev_queue, NULL);
+
+                       /* {ingress,clsact}_destroy() "old" before grafting "new" to avoid
+                        * unprotected concurrent accesses to net_device::miniq_{in,e}gress
+                        * pointer(s) in mini_qdisc_pair_swap().
+                        */
+                       qdisc_notify(net, skb, n, classid, old, new, extack);
+                       qdisc_destroy(old);
+
+                       dev_graft_qdisc(dev_queue, new);
                }
 
 skip:

@@ -1119,8 +1137,6 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
 
                        if (new && new->ops->attach)
                                new->ops->attach(new);
-               } else {
-                       notify_and_destroy(net, skb, n, classid, old, new, extack);
                }
 
                if (dev->flags & IFF_UP)

net/sched/sch_generic.c +11 -4

index 37e41f972f69..e14ed47f961c 100644
@@ -1046,7 +1046,7 @@ static void qdisc_free_cb(struct rcu_head *head)
        qdisc_free(q);
 }
 
-static void qdisc_destroy(struct Qdisc *qdisc)
+static void __qdisc_destroy(struct Qdisc *qdisc)
 {
        const struct Qdisc_ops  *ops = qdisc->ops;

@@ -1070,6 +1070,14 @@ static void qdisc_destroy(struct Qdisc *qdisc)
        call_rcu(&qdisc->rcu, qdisc_free_cb);
 }
 
+void qdisc_destroy(struct Qdisc *qdisc)
+{
+       if (qdisc->flags & TCQ_F_BUILTIN)
+               return;
+
+       __qdisc_destroy(qdisc);
+}
+
 void qdisc_put(struct Qdisc *qdisc)
 {
        if (!qdisc)

@@ -1079,7 +1087,7 @@ void qdisc_put(struct Qdisc *qdisc)
            !refcount_dec_and_test(&qdisc->refcnt))
                return;
 
-       qdisc_destroy(qdisc);
+       __qdisc_destroy(qdisc);
 }
 EXPORT_SYMBOL(qdisc_put);

@@ -1094,7 +1102,7 @@ void qdisc_put_unlocked(struct Qdisc *qdisc)
            !refcount_dec_and_rtnl_lock(&qdisc->refcnt))
                return;
 
-       qdisc_destroy(qdisc);
+       __qdisc_destroy(qdisc);
        rtnl_unlock();
 }
 EXPORT_SYMBOL(qdisc_put_unlocked);
--

2.20.1

Pedro Tammela

Tested-by on v1 5/6

2023-05-08 14:12 UTC #23 lore raw

Re: [PATCH net 5/6] net/sched: Refactor qdisc_graft() for ingress and clsact Qdiscs

Quoted 4 lines · Peilin Ye

Grafting ingress and clsact Qdiscs does not need a for-loop in qdisc_graft(). Refactor it. No functional changes intended.
Signed-off-by Peilin Ye <[email protected]>

Just a FYI:
If you decide to keep this refactoring, it will need to be back ported together with the subsequent fix.
I would personally leave it to net-next.

Thanks for chasing this!

Tested-by Pedro Tammela <[email protected]>

Quoted 50 lines

---
  net/sched/sch_api.c | 20 ++++++++++----------
  1 file changed, 10 insertions(+), 10 deletions(-)

net/sched/sch_api.c +10 ~~-10~~

index 49b9c1bbfdd9..f72a581666a2 100644
@@ -1073,12 +1073,12 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
 
  	if (parent == NULL) {
  		unsigned int i, num_q, ingress;
+		struct netdev_queue *dev_queue;
 
  		ingress = 0;
  		num_q = dev->num_tx_queues;
  		if ((q && q->flags & TCQ_F_INGRESS) ||
  		    (new && new->flags & TCQ_F_INGRESS)) {
-			num_q = 1;
  			ingress = 1;
  			if (!dev_ingress_queue(dev)) {
  				NL_SET_ERR_MSG(extack, "Device does not have an ingress queue");

@@ -1094,18 +1094,18 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
  		if (new && new->ops->attach && !ingress)
  			goto skip;
 
-		for (i = 0; i < num_q; i++) {
-			struct netdev_queue *dev_queue = dev_ingress_queue(dev);
-
-			if (!ingress)
+		if (!ingress) {
+			for (i = 0; i < num_q; i++) {
  				dev_queue = netdev_get_tx_queue(dev, i);
+				old = dev_graft_qdisc(dev_queue, new);
 
-			old = dev_graft_qdisc(dev_queue, new);
-			if (new && i > 0)
-				qdisc_refcount_inc(new);
-
-			if (!ingress)
+				if (new && i > 0)
+					qdisc_refcount_inc(new);
  				qdisc_put(old);
+			}
+		} else {
+			dev_queue = dev_ingress_queue(dev);
+			old = dev_graft_qdisc(dev_queue, new);
  		}
 
  skip:

Pedro Tammela

Tested-by on v1 6/6

2023-05-08 14:12 UTC #27 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

In reply to Jamal Hadi Salim

Quoted 82 lines · Peilin Ye

mini_Qdisc_pair::p_miniq is a double pointer to mini_Qdisc, initialized in ingress_init() to point to net_device::miniq_ingress. ingress Qdiscs access this per-net_device pointer in mini_qdisc_pair_swap(). Similar for clsact Qdiscs and miniq_egress.
Unfortunately, after introducing RTNL-lockless RTM_{NEW,DEL,GET}TFILTER requests, when e.g. replacing ingress (clsact) Qdiscs, the old Qdisc could access the same miniq_{in,e}gress pointer(s) concurrently with the new Qdisc, causing race conditions [1] including a use-after-free in mini_qdisc_pair_swap() reported by syzbot:
  BUG: KASAN: slab-use-after-free in mini_qdisc_pair_swap+0x1c2/0x1f0 net/sched/sch_generic.c:1573
  Write of size 8 at addr ffff888045b31308 by task syz-executor690/14901
...
  Call Trace:
   <TASK>
   __dump_stack lib/dump_stack.c:88 [inline]
   dump_stack_lvl+0xd9/0x150 lib/dump_stack.c:106
   print_address_description.constprop.0+0x2c/0x3c0 mm/kasan/report.c:319
   print_report mm/kasan/report.c:430 [inline]
   kasan_report+0x11c/0x130 mm/kasan/report.c:536
   mini_qdisc_pair_swap+0x1c2/0x1f0 net/sched/sch_generic.c:1573
   tcf_chain_head_change_item net/sched/cls_api.c:495 [inline]
   tcf_chain0_head_change.isra.0+0xb9/0x120 net/sched/cls_api.c:509
   tcf_chain_tp_insert net/sched/cls_api.c:1826 [inline]
   tcf_chain_tp_insert_unique net/sched/cls_api.c:1875 [inline]
   tc_new_tfilter+0x1de6/0x2290 net/sched/cls_api.c:2266
...
The new (ingress or clsact) Qdisc should only call mini_qdisc_pair_swap() after the old Qdisc's last call (in {ingress,clsact}_destroy()) has finished.
To achieve this, in qdisc_graft(), return -EBUSY if the old (ingress or clsact) Qdisc has ongoing RTNL-lockless filter requests, and call qdisc_destroy() for "old" before grafting "new".
Introduce qdisc_refcount_dec_if_one() as the counterpart of qdisc_refcount_inc_nz() used for RTNL-lockless filter requests. Introduce a non-static version of qdisc_destroy() that does a TCQ_F_BUILTIN check, just like qdisc_put() etc.
[1] To illustrate, the syzkaller reproducer adds ingress Qdiscs under TC_H_ROOT (no longer possible after patch "net/sched: sch_ingress: Only create under TC_H_INGRESS") on eth0 that has 8 transmission queues:
Thread 1 creates ingress Qdisc A (containing mini Qdisc a1 and a2), then adds a flower filter X to A.
Thread 2 creates another ingress Qdisc B (containing mini Qdisc b1 and b2) to replace A, then adds a flower filter Y to B.
Thread 1 A's refcnt Thread 2
RTM_NEWQDISC (A, RTNL-locked)
qdisc_create(A) 1
qdisc_graft(A) 9
RTM_NEWTFILTER (X, RTNL-lockless)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
mini_qdisc_pair_swap(A) (1st)
|
| RTM_NEWQDISC (B, RTNL-locked)
RCU 2 qdisc_graft(B)
| 1 notify_and_destroy(A)
|
tcf_block_release(A) 0 RTM_NEWTFILTER (Y, RTNL-lockless)
qdisc_destroy(A) tcf_chain0_head_change(B)
tcf_chain0_head_change_cb_del(A) mini_qdisc_pair_swap(B) (2nd)
mini_qdisc_pair_swap(A) (3rd) |
... ...
Here, B calls mini_qdisc_pair_swap(), pointing eth0->miniq_ingress to its mini Qdisc, b1. Then, A calls mini_qdisc_pair_swap() again during ingress_destroy(), setting eth0->miniq_ingress to NULL, so ingress packets on eth0 will not find filter Y in sch_handle_ingress().
This is just one of the possible consequences of concurrently accessing net_device::miniq_{in,e}gress pointers. The point is clear, however:
B's first call to mini_qdisc_pair_swap() should take place after A's last call, in qdisc_destroy().

Quoted 6 lines

Fixes 7a096d579e8e ("net: sched: ingress: set 'unlocked' flag for Qdisc ops")
Fixes 87f373921c4e ("net: sched: ingress: set 'unlocked' flag for clsact Qdisc ops")
Reported-by [email protected]
Link https://lore.kernel.org/netdev/[email protected] open here
Cc Hillf Danton <[email protected]>
Signed-off-by Peilin Ye <[email protected]>

Thanks for chasing this!

Tested-by Pedro Tammela <[email protected]>

Quoted 132 lines

---
  include/net/sch_generic.h |  8 ++++++++
  net/sched/sch_api.c       | 26 +++++++++++++++++++++-----
  net/sched/sch_generic.c   | 14 +++++++++++---
  3 files changed, 40 insertions(+), 8 deletions(-)

include/net/sch_generic.h +8 -0

index fab5ba3e61b7..3e9cc43cbc90 100644
@@ -137,6 +137,13 @@ static inline void qdisc_refcount_inc(struct Qdisc *qdisc)
  	refcount_inc(&qdisc->refcnt);
  }
 
+static inline bool qdisc_refcount_dec_if_one(struct Qdisc *qdisc)
+{
+	if (qdisc->flags & TCQ_F_BUILTIN)
+		return true;
+	return refcount_dec_if_one(&qdisc->refcnt);
+}
+
  /* Intended to be used by unlocked users, when concurrent qdisc release is
   * possible.
   */

@@ -652,6 +659,7 @@ void dev_deactivate_many(struct list_head *head);
  struct Qdisc *dev_graft_qdisc(struct netdev_queue *dev_queue,
  			      struct Qdisc *qdisc);
  void qdisc_reset(struct Qdisc *qdisc);
+void qdisc_destroy(struct Qdisc *qdisc);
  void qdisc_put(struct Qdisc *qdisc);
  void qdisc_put_unlocked(struct Qdisc *qdisc);
  void qdisc_tree_reduce_backlog(struct Qdisc *qdisc, int n, int len);

net/sched/sch_api.c +21 -5

index f72a581666a2..a2d07bc8ded6 100644
@@ -1080,10 +1080,20 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
  		if ((q && q->flags & TCQ_F_INGRESS) ||
  		    (new && new->flags & TCQ_F_INGRESS)) {
  			ingress = 1;
-			if (!dev_ingress_queue(dev)) {
+			dev_queue = dev_ingress_queue(dev);
+			if (!dev_queue) {
  				NL_SET_ERR_MSG(extack, "Device does not have an ingress queue");
  				return -ENOENT;
  			}
+
+			/* This is the counterpart of that qdisc_refcount_inc_nz() call in
+			 * __tcf_qdisc_find() for RTNL-lockless filter requests.
+			 */
+			if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping)) {
+				NL_SET_ERR_MSG(extack,
+					       "Current ingress or clsact Qdisc has ongoing filter request(s)");
+				return -EBUSY;
+			}
  		}
 
  		if (dev->flags & IFF_UP)

@@ -1104,8 +1114,16 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
  				qdisc_put(old);
  			}
  		} else {
-			dev_queue = dev_ingress_queue(dev);
-			old = dev_graft_qdisc(dev_queue, new);
+			old = dev_graft_qdisc(dev_queue, NULL);
+
+			/* {ingress,clsact}_destroy() "old" before grafting "new" to avoid
+			 * unprotected concurrent accesses to net_device::miniq_{in,e}gress
+			 * pointer(s) in mini_qdisc_pair_swap().
+			 */
+			qdisc_notify(net, skb, n, classid, old, new, extack);
+			qdisc_destroy(old);
+
+			dev_graft_qdisc(dev_queue, new);
  		}
 
  skip:

@@ -1119,8 +1137,6 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
 
  			if (new && new->ops->attach)
  				new->ops->attach(new);
-		} else {
-			notify_and_destroy(net, skb, n, classid, old, new, extack);
  		}
 
  		if (dev->flags & IFF_UP)

net/sched/sch_generic.c +11 -3

index 37e41f972f69..e14ed47f961c 100644
@@ -1046,7 +1046,7 @@ static void qdisc_free_cb(struct rcu_head *head)
  	qdisc_free(q);
  }
 
-static void qdisc_destroy(struct Qdisc *qdisc)
+static void __qdisc_destroy(struct Qdisc *qdisc)
  {
  	const struct Qdisc_ops  *ops = qdisc->ops;

@@ -1070,6 +1070,14 @@ static void qdisc_destroy(struct Qdisc *qdisc)
  	call_rcu(&qdisc->rcu, qdisc_free_cb);
  }
 
+void qdisc_destroy(struct Qdisc *qdisc)
+{
+	if (qdisc->flags & TCQ_F_BUILTIN)
+		return;
+
+	__qdisc_destroy(qdisc);
+}
+
  void qdisc_put(struct Qdisc *qdisc)
  {
  	if (!qdisc)

@@ -1079,7 +1087,7 @@ void qdisc_put(struct Qdisc *qdisc)
  	    !refcount_dec_and_test(&qdisc->refcnt))
  		return;
 
-	qdisc_destroy(qdisc);
+	__qdisc_destroy(qdisc);
  }
  EXPORT_SYMBOL(qdisc_put);

@@ -1094,7 +1102,7 @@ void qdisc_put_unlocked(struct Qdisc *qdisc)
  	    !refcount_dec_and_rtnl_lock(&qdisc->refcnt))
  		return;
 
-	qdisc_destroy(qdisc);
+	__qdisc_destroy(qdisc);
  	rtnl_unlock();
  }
  EXPORT_SYMBOL(qdisc_put_unlocked);

Peilin Ye

2023-05-08 21:58 UTC #26 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 2 lines · Jamal Hadi Salim

Thanks for the excellent analysis Peilin and for chasing this to the end. I have no doubt it was a lot of fun! ;->

Of course ;-)

Quoted 2 lines

Reviewed-by Jamal Hadi Salim <[email protected]>
Acked-by Jamal Hadi Salim <[email protected]>

Thanks for reviewing this!

Peilin Ye

2023-05-08 22:01 UTC #28 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

In reply to Pedro Tammela

Quoted 3 lines · Pedro Tammela

Thanks for chasing this!
Tested-by Pedro Tammela <[email protected]>

Thanks for testing, Pedro!

Thanks,
Peilin Ye

Peilin Ye

2023-05-08 22:24 UTC #22 lore raw

Re: [PATCH net 5/6] net/sched: Refactor qdisc_graft() for ingress and clsact Qdiscs

In reply to Jamal Hadi Salim

Quoted 10 lines · Jamal Hadi Salim

Quoted 3 lines · Peilin Ye
Grafting ingress and clsact Qdiscs does not need a for-loop in qdisc_graft(). Refactor it. No functional changes intended.
This one i am not so sure; num_q = 1 implies it will run on the for loop only once. I am not sure it improves readability either. Anyways for the effort you put into it i am tossing a coin and saying:
Reviewed-by Jamal Hadi Salim <[email protected]>
Acked-by Jamal Hadi Salim <[email protected]>

Yeah, it doesn't make much difference itself. I'm just afraid that, without [5/6], [6/6] would look like:

		for (i = 0; i < num_q; i++) {
			if (!ingress) {
				dev_queue = netdev_get_tx_queue(dev, i);
				old = dev_graft_qdisc(dev_queue, new);
			else {
				old = dev_graft_qdisc(dev_queue, NULL);
			}

			if (new && i > 0)
				qdisc_refcount_inc(new);

			if (!ingress) {
				qdisc_put(old);
			} else {
                                /* {ingress,clsact}_destroy() "old" before grafting "new" to avoid
                                 * unprotected concurrent accesses to net_device::miniq_{in,e}gress
                                 * pointer(s) in mini_qdisc_pair_swap().
                                 */
				qdisc_notify(net, skb, n, classid, old, new, extack);
				qdisc_destroy(old);
			}

			if (ingress)
				dev_graft_qdisc(dev_queue, new);
		}

The "!ingress" path doesn't share a single line with "ingress", which looks a bit weird to me. Personally I'd like to keep [5/6].

Thanks,
Peilin Ye

Jakub Kicinski

maintainer

2023-05-09 01:33 UTC #29 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 31 lines · On Fri, 5 May 2023 17:16:10 -0700 Peilin Ye wrote:

Thread 1 creates ingress Qdisc A (containing mini Qdisc a1 and a2), then adds a flower filter X to A.
Thread 2 creates another ingress Qdisc B (containing mini Qdisc b1 and b2) to replace A, then adds a flower filter Y to B.
Thread 1 A's refcnt Thread 2
RTM_NEWQDISC (A, RTNL-locked)
qdisc_create(A) 1
qdisc_graft(A) 9
RTM_NEWTFILTER (X, RTNL-lockless)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
mini_qdisc_pair_swap(A) (1st)
|
| RTM_NEWQDISC (B, RTNL-locked)
RCU 2 qdisc_graft(B)
| 1 notify_and_destroy(A)
|
tcf_block_release(A) 0 RTM_NEWTFILTER (Y, RTNL-lockless)
qdisc_destroy(A) tcf_chain0_head_change(B)
tcf_chain0_head_change_cb_del(A) mini_qdisc_pair_swap(B) (2nd)
mini_qdisc_pair_swap(A) (3rd) |
... ...
Here, B calls mini_qdisc_pair_swap(), pointing eth0->miniq_ingress to its mini Qdisc, b1. Then, A calls mini_qdisc_pair_swap() again during ingress_destroy(), setting eth0->miniq_ingress to NULL, so ingress packets on eth0 will not find filter Y in sch_handle_ingress().

Quoted 4 lines

This is just one of the possible consequences of concurrently accessing net_device::miniq_{in,e}gress pointers. The point is clear, however:
B's first call to mini_qdisc_pair_swap() should take place after A's last call, in qdisc_destroy().

Great analysis, thanks for squashing this bug.

Have you considered creating a fix more localized to the miniq implementation? It seems that having per-device miniq pointers is incompatible with using reference counted objects. So miniq is a more natural place to solve the problem. Otherwise workarounds in the core keep piling up (here qdisc_graft()).

Can we replace the rcu_assign_pointer in (3rd) with a cmpxchg()? If active qdisc is neither a1 nor a2 we should leave the dev state alone.

Peilin Ye

2023-05-10 20:11 UTC #30 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 1 line · Jakub Kicinski

Great analysis, thanks for squashing this bug.

Thanks, happy to help!

Quoted 9 lines

Have you considered creating a fix more localized to the miniq implementation? It seems that having per-device miniq pointers is incompatible with using reference counted objects. So miniq is a more natural place to solve the problem. Otherwise workarounds in the core keep piling up (here qdisc_graft()).
Can we replace the rcu_assign_pointer in (3rd) with a cmpxchg()? If active qdisc is neither a1 nor a2 we should leave the dev state alone.

Yes, I have tried fixing this in mini_qdisc_pair_swap(), but I am afraid it is hard:

(3rd) is called from ->destroy(), so currently it uses RCU_INIT_POINTER() to set dev->miniq_ingress to NULL. It will need a logic like:

I am A. Set dev->miniq_ingress to NULL, if and only if it is a1 or a2, and do it atomically.

We need more than a cmpxchg() to implement this "set NULL iff a1 or a2". Additionally:

Quoted 11 lines · On Fri, 5 May 2023 17:16:10 -0700 Peilin Ye wrote:

Thread 1 creates ingress Qdisc A (containing mini Qdisc a1 and a2), then adds a flower filter X to A.
Thread 2 creates another ingress Qdisc B (containing mini Qdisc b1 and b2) to replace A, then adds a flower filter Y to B.
Thread 1 A's refcnt Thread 2
RTM_NEWQDISC (A, RTNL-locked)
qdisc_create(A) 1
qdisc_graft(A) 9

Quoted 14 lines

RTM_NEWTFILTER (X, RTNL-lockless)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
mini_qdisc_pair_swap(A) (1st)
|
| RTM_NEWQDISC (B, RTNL-locked)
RCU 2 qdisc_graft(B)
| 1 notify_and_destroy(A)
|
tcf_block_release(A) 0 RTM_NEWTFILTER (Y, RTNL-lockless)
qdisc_destroy(A) tcf_chain0_head_change(B)
tcf_chain0_head_change_cb_del(A) mini_qdisc_pair_swap(B) (2nd)
mini_qdisc_pair_swap(A) (3rd) |
... ...

Looking at the code, I think there is no guarantee that (1st) cannot happen after (2nd), although unlikely? Can RTNL-lockless RTM_NEWTFILTER handlers get preempted?

If (1st) happens later than (2nd), we will need to make (1st) no-op, by detecting that we are the "old" Qdisc. I am not sure there is any (clean) way to do it. I even thought about:

(1) Get the containing Qdisc of "miniqp" we are working on, "qdisc";
(2) Test if "qdisc == qdisc->dev_queue->qdisc_sleeping". If false, it means we are the "old" Qdisc (have been replaced), and should do nothing.

However, for clsact Qdiscs I don't know if "miniqp" is the ingress or egress one, so I can't container_of() during step (1) ...

Eventually I created [5,6/6]. It is a workaround indeed, in the sense that it changes sch_api.c to avoid a mini Qdisc issue. However I think it makes the code correct in a relatively understandable way, without slowing down mini_qdisc_pair_swap() or sch_handle_*gress().

Thanks,
Peilin Ye

Jakub Kicinski

maintainer

2023-05-10 23:16 UTC #31 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 27 lines · On Wed, 10 May 2023 13:11:19 -0700 Peilin Ye wrote:

Quoted 11 lines · On Fri, 5 May 2023 17:16:10 -0700 Peilin Ye wrote:
Thread 1 creates ingress Qdisc A (containing mini Qdisc a1 and a2), then adds a flower filter X to A.
Thread 2 creates another ingress Qdisc B (containing mini Qdisc b1 and b2) to replace A, then adds a flower filter Y to B.
Thread 1 A's refcnt Thread 2
RTM_NEWQDISC (A, RTNL-locked)
qdisc_create(A) 1
qdisc_graft(A) 9
Quoted 14 lines
RTM_NEWTFILTER (X, RTNL-lockless)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
mini_qdisc_pair_swap(A) (1st)
|
| RTM_NEWQDISC (B, RTNL-locked)
RCU 2 qdisc_graft(B)
| 1 notify_and_destroy(A)
|
tcf_block_release(A) 0 RTM_NEWTFILTER (Y, RTNL-lockless)
qdisc_destroy(A) tcf_chain0_head_change(B)
tcf_chain0_head_change_cb_del(A) mini_qdisc_pair_swap(B) (2nd)
mini_qdisc_pair_swap(A) (3rd) |
... ...

Quoted 3 lines

Looking at the code, I think there is no guarantee that (1st) cannot happen after (2nd), although unlikely? Can RTNL-lockless RTM_NEWTFILTER handlers get preempted?

Right, we need qdisc_graft(B) to update the appropriate dev pointer to point to b1. With that the ordering should not matter. Probably using the ->attach() callback?

Quoted 11 lines

If (1st) happens later than (2nd), we will need to make (1st) no-op, by detecting that we are the "old" Qdisc. I am not sure there is any (clean) way to do it. I even thought about:
(1) Get the containing Qdisc of "miniqp" we are working on, "qdisc";
(2) Test if "qdisc == qdisc->dev_queue->qdisc_sleeping". If false, it means we are the "old" Qdisc (have been replaced), and should do nothing.
However, for clsact Qdiscs I don't know if "miniqp" is the ingress or egress one, so I can't container_of() during step (1) ...

And we can't be using multiple pieces of information to make the decision since AFAIU mini_qdisc_pair_swap() can race with qdisc_graft().

My thinking was to make sure that dev->miniq_* pointers always point to one of the miniqs of the currently attached qdisc. Right now, on a quick look, those pointers are not initialized during initial graft, only when first filter is added, and may be cleared when filters are removed. But I don't think that's strictly required, miniq with no filters should be fine.

Quoted 3 lines

Eventually I created [5,6/6]. It is a workaround indeed, in the sense that it changes sch_api.c to avoid a mini Qdisc issue. However I think it makes the code correct in a relatively understandable way,

What's your benchmark for being understandable?

Quoted 1 line

without slowing down mini_qdisc_pair_swap() or sch_handle_*gress().

Peilin Ye

2023-05-11 20:40 UTC #32 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 6 lines · Jakub Kicinski

My thinking was to make sure that dev->miniq_* pointers always point to one of the miniqs of the currently attached qdisc. Right now, on a quick look, those pointers are not initialized during initial graft, only when first filter is added, and may be cleared when filters are removed. But I don't think that's strictly required, miniq with no filters should be fine.

Ah, I see, thanks for explaining, I didn't think of that. Looking at sch_handle_ingress() BTW, currently mini Qdisc stats aren't being updated (mini_qdisc_bstats_cpu_update()) if there's no filters, is this intended? Should I keep this behavior by:

net/core/dev.c +1 -1

index 735096d42c1d..9016481377e0 100644
@@ -5116,7 +5116,7 @@ sch_handle_ingress(struct sk_buff *skb, struct packet_type **pt_prev, int *ret,
         * that are not configured with an ingress qdisc will bail
         * out here.
         */
-       if (!miniq)
+       if (!miniq || !miniq->filter_list)
                return skb;
 
        if (*pt_prev) {

Quoted 22 lines · Jakub Kicinski

Quoted 21 lines · On Wed, 10 May 2023 13:11:19 -0700 Peilin Ye wrote:
Quoted 19 lines · On Fri, 5 May 2023 17:16:10 -0700 Peilin Ye wrote:
Thread 1 A's refcnt Thread 2
RTM_NEWQDISC (A, RTNL-locked)
qdisc_create(A) 1
qdisc_graft(A) 9
RTM_NEWTFILTER (X, RTNL-lockless)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
mini_qdisc_pair_swap(A) (1st)
|
| RTM_NEWQDISC (B, RTNL-locked)
RCU 2 qdisc_graft(B)
| 1 notify_and_destroy(A)
|
tcf_block_release(A) 0 RTM_NEWTFILTER (Y, RTNL-lockless)
qdisc_destroy(A) tcf_chain0_head_change(B)
tcf_chain0_head_change_cb_del(A) mini_qdisc_pair_swap(B) (2nd)
mini_qdisc_pair_swap(A) (3rd) |
... ...

Quoted 7 lines

Quoted 3 lines
Looking at the code, I think there is no guarantee that (1st) cannot happen after (2nd), although unlikely? Can RTNL-lockless RTM_NEWTFILTER handlers get preempted?
Right, we need qdisc_graft(B) to update the appropriate dev pointer to point to b1. With that the ordering should not matter. Probably using the ->attach() callback?

->attach() is later than dev_graft_qdisc(). We should get ready for concurrent filter requests (i.e. have dev pointer pointing to b1) before grafting (publishing) B. Also currently qdisc_graft() doesn't call ->attach() for ingress and clsact Qdiscs.

But I see your point, thanks for the suggestion! I'll try ->init() and create v2.

Thanks,
Peilin Ye

Jakub Kicinski

maintainer

2023-05-11 23:20 UTC #33 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 18 lines · On Thu, 11 May 2023 13:40:10 -0700 Peilin Ye wrote:

Quoted 6 lines · Jakub Kicinski
My thinking was to make sure that dev->miniq_* pointers always point to one of the miniqs of the currently attached qdisc. Right now, on a quick look, those pointers are not initialized during initial graft, only when first filter is added, and may be cleared when filters are removed. But I don't think that's strictly required, miniq with no filters should be fine.
Ah, I see, thanks for explaining, I didn't think of that. Looking at sch_handle_ingress() BTW, currently mini Qdisc stats aren't being updated (mini_qdisc_bstats_cpu_update()) if there's no filters, is this intended? Should I keep this behavior by:
net/core/dev.c +0 -0
index 735096d42c1d..9016481377e0 100644

net/core/dev.c sch_handle_ingress(struct sk_buff *skb, struct packet_type **pt_prev, int *ret, · line 5122

Quoted 8 lines

net/core/dev.c +1 -1

@@ -5116,7 +5116,7 @@ sch_handle_ingress(struct sk_buff *skb, struct packet_type **pt_prev, int *ret,
         * that are not configured with an ingress qdisc will bail
         * out here.
         */
-       if (!miniq)
+       if (!miniq || !miniq->filter_list)
                return skb;
 
        if (*pt_prev) {

Good question, maybe Jiri or Daniel can answer?

Quoted 6 lines · Jakub Kicinski

Quoted 5 lines · On Wed, 10 May 2023 13:11:19 -0700 Peilin Ye wrote:
Quoted 3 lines
Looking at the code, I think there is no guarantee that (1st) cannot happen after (2nd), although unlikely? Can RTNL-lockless RTM_NEWTFILTER handlers get preempted?

Quoted 7 lines

Quoted 3 lines
Right, we need qdisc_graft(B) to update the appropriate dev pointer to point to b1. With that the ordering should not matter. Probably using the ->attach() callback?
->attach() is later than dev_graft_qdisc(). We should get ready for concurrent filter requests (i.e. have dev pointer pointing to b1) before grafting (publishing) B.

I thought even for "unlocked" filter operations the start of it is under the lock, but the lock gets dropped after qdisc/block are found. I could be misremembering, I haven't looked at the code.

Quoted 5 lines

Also currently qdisc_graft() doesn't call
->attach() for ingress and clsact Qdiscs.
But I see your point, thanks for the suggestion! I'll try ->init() and create v2.

->init() may be too early, aren't there any error points which could prevent the Qdisc from binding after ->init() was called?

Peilin Ye

2023-05-11 23:46 UTC #34 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 5 lines · Jakub Kicinski

Quoted 2 lines
But I see your point, thanks for the suggestion! I'll try ->init() and create v2.
->init() may be too early, aren't there any error points which could prevent the Qdisc from binding after ->init() was called?

You're right, it's in qdisc_create(), argh...

Quoted 8 lines · Jakub Kicinski

Quoted 8 lines
Quoted 7 lines
Quoted 3 lines
Looking at the code, I think there is no guarantee that (1st) cannot happen after (2nd), although unlikely? Can RTNL-lockless RTM_NEWTFILTER handlers get preempted?
Right, we need qdisc_graft(B) to update the appropriate dev pointer to point to b1. With that the ordering should not matter. Probably using the ->attach() callback?

Quoted 7 lines

Quoted 3 lines
->attach() is later than dev_graft_qdisc(). We should get ready for concurrent filter requests (i.e. have dev pointer pointing to b1) before grafting (publishing) B.
I thought even for "unlocked" filter operations the start of it is under the lock, but the lock gets dropped after qdisc/block are found. I could be misremembering, I haven't looked at the code.

No, f.e. RTM_NEWTFILTER is registered as RTNL_FLAG_DOIT_UNLOCKED, so tc_new_tfilter() starts and calls __tcf_qdisc_find() without RTNL mutex, at least in latest code.

Thinking,
Peilin Ye

Peilin Ye

2023-05-12 00:11 UTC #35 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 8 lines · Peilin Ye

Quoted 5 lines · Jakub Kicinski
Quoted 2 lines
But I see your point, thanks for the suggestion! I'll try ->init() and create v2.
->init() may be too early, aren't there any error points which could prevent the Qdisc from binding after ->init() was called?
You're right, it's in qdisc_create(), argh...

->destroy() is called for all error points between ->init() and dev_graft_qdisc(). I'll try handling it in ->destroy().

Thanks,
Peilin Ye

Peilin Ye

2023-05-15 22:45 UTC #36 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 7 lines · Peilin Ye

Quoted 4 lines
Quoted 2 lines
->init() may be too early, aren't there any error points which could prevent the Qdisc from binding after ->init() was called?
You're right, it's in qdisc_create(), argh...
->destroy() is called for all error points between ->init() and dev_graft_qdisc(). I'll try handling it in ->destroy().

Sorry for any confusion: there is no point at all undoing "setting dev pointer to b1" in ->destroy() because datapath has already been affected.

To summarize, grafting B mustn't fail after setting dev pointer to b1, so ->init() is too early, because e.g. if user requested [1] to create a rate estimator, gen_new_estimator() could fail after ->init() in qdisc_create().

On the other hand, ->attach() is too late because it's later than dev_graft_qdisc(), so concurrent filter requests might see uninitialized dev pointer in theory.

Please suggest; is adding another callback (or calling ->attach()) right before dev_graft_qdisc() for ingress (clsact) Qdiscs too much for this fix?

[1] e.g. $ tc qdisc add dev eth0 estimator 1s 8s clsact

Thanks,
Peilin Ye

Jakub Kicinski

maintainer

2023-05-16 19:22 UTC #37 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 18 lines · On Mon, 15 May 2023 15:45:15 -0700 Peilin Ye wrote:

Quoted 4 lines · Peilin Ye
Quoted 1 line
You're right, it's in qdisc_create(), argh...
->destroy() is called for all error points between ->init() and dev_graft_qdisc(). I'll try handling it in ->destroy().
Sorry for any confusion: there is no point at all undoing "setting dev pointer to b1" in ->destroy() because datapath has already been affected.
To summarize, grafting B mustn't fail after setting dev pointer to b1, so ->init() is too early, because e.g. if user requested [1] to create a rate estimator, gen_new_estimator() could fail after ->init() in qdisc_create().
On the other hand, ->attach() is too late because it's later than dev_graft_qdisc(), so concurrent filter requests might see uninitialized dev pointer in theory.

Quoted 5 lines

Please suggest; is adding another callback (or calling ->attach()) right before dev_graft_qdisc() for ingress (clsact) Qdiscs too much for this fix?
[1] e.g. $ tc qdisc add dev eth0 estimator 1s 8s clsact

Vlad, could you please clarify how you expect the unlocked filter operations to work when the qdisc has global state?

Vlad Buslov

2023-05-16 19:49 UTC #38 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 19 lines · Jakub Kicinski

Quoted 18 lines · On Mon, 15 May 2023 15:45:15 -0700 Peilin Ye wrote:
Quoted 4 lines · Peilin Ye
Quoted 1 line
You're right, it's in qdisc_create(), argh...
->destroy() is called for all error points between ->init() and dev_graft_qdisc(). I'll try handling it in ->destroy().
Sorry for any confusion: there is no point at all undoing "setting dev pointer to b1" in ->destroy() because datapath has already been affected.
To summarize, grafting B mustn't fail after setting dev pointer to b1, so ->init() is too early, because e.g. if user requested [1] to create a rate estimator, gen_new_estimator() could fail after ->init() in qdisc_create().
On the other hand, ->attach() is too late because it's later than dev_graft_qdisc(), so concurrent filter requests might see uninitialized dev pointer in theory.

Quoted 8 lines

Quoted 5 lines
Please suggest; is adding another callback (or calling ->attach()) right before dev_graft_qdisc() for ingress (clsact) Qdiscs too much for this fix?
[1] e.g. $ tc qdisc add dev eth0 estimator 1s 8s clsact
Vlad, could you please clarify how you expect the unlocked filter operations to work when the qdisc has global state?

Jakub, I didn't account for per-net_device pointer usage by miniqp code hence this bug. I didn't comment on the fix because I was away from my PC last week but Peilin's approach seems reasonable to me. When Peilin brought up the issue initially I also tried to come up with some trick to contain the changes to miniqp code instead of changing core but couldn't think of anything workable due to the limitations already discussed in this thread. I'm open to explore alternative approaches to solving this issue, if that is what you suggest.

Jakub Kicinski

maintainer

2023-05-16 21:50 UTC #39 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 11 lines · On Tue, 16 May 2023 22:35:51 +0300 Vlad Buslov wrote:

Quoted 2 lines
Vlad, could you please clarify how you expect the unlocked filter operations to work when the qdisc has global state?
Jakub, I didn't account for per-net_device pointer usage by miniqp code hence this bug. I didn't comment on the fix because I was away from my PC last week but Peilin's approach seems reasonable to me. When Peilin brought up the issue initially I also tried to come up with some trick to contain the changes to miniqp code instead of changing core but couldn't think of anything workable due to the limitations already discussed in this thread. I'm open to explore alternative approaches to solving this issue, if that is what you suggest.

Given Peilin's investigation I think fix without changing core may indeed be hard. I'm not sure if returning -EBUSY when qdisc refcnt is elevated will be appreciated by the users, do we already have similar behavior in other parts of TC?

Peilin Ye

2023-05-16 22:58 UTC #40 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 12 lines · Jakub Kicinski

Quoted 11 lines
Quoted 2 lines
Vlad, could you please clarify how you expect the unlocked filter operations to work when the qdisc has global state?
Jakub, I didn't account for per-net_device pointer usage by miniqp code hence this bug. I didn't comment on the fix because I was away from my PC last week but Peilin's approach seems reasonable to me. When Peilin brought up the issue initially I also tried to come up with some trick to contain the changes to miniqp code instead of changing core but couldn't think of anything workable due to the limitations already discussed in this thread. I'm open to explore alternative approaches to solving this issue, if that is what you suggest.

Quoted 4 lines

Given Peilin's investigation I think fix without changing core may indeed be hard. I'm not sure if returning -EBUSY when qdisc refcnt is elevated will be appreciated by the users, do we already have similar behavior in other parts of TC?

Seems like trying to delete an "in-use" cls_u32 filter returns -EBUSY:

net/sched/cls_u32.c:

	if (ht->refcnt == 1) {
		u32_destroy_hnode(tp, ht, extack);
	} else {
		NL_SET_ERR_MSG_MOD(extack, "Can not delete in-use filter");
		return -EBUSY;
	}

Thanks,
Peilin Ye

Jakub Kicinski

maintainer

2023-05-17 00:39 UTC #41 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 6 lines · On Tue, 16 May 2023 15:58:46 -0700 Peilin Ye wrote:

Quoted 4 lines
Given Peilin's investigation I think fix without changing core may indeed be hard. I'm not sure if returning -EBUSY when qdisc refcnt is elevated will be appreciated by the users, do we already have similar behavior in other parts of TC?
Seems like trying to delete an "in-use" cls_u32 filter returns -EBUSY

I meant -EBUSY due to a race (another operation being in flight). I think that's different.

Vlad Buslov

2023-05-17 08:52 UTC #42 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 10 lines · Jakub Kicinski

Quoted 6 lines · On Tue, 16 May 2023 15:58:46 -0700 Peilin Ye wrote:
Quoted 4 lines
Given Peilin's investigation I think fix without changing core may indeed be hard. I'm not sure if returning -EBUSY when qdisc refcnt is elevated will be appreciated by the users, do we already have similar behavior in other parts of TC?
Seems like trying to delete an "in-use" cls_u32 filter returns -EBUSY
I meant -EBUSY due to a race (another operation being in flight). I think that's different.

I wonder if somehow leveraging existing tc_modify_qdisc() 'replay' functionality instead of returning error to the user would be a better approach? Currently the function is replayed when qdisc_create() returns EAGAIN. It should be trivial to do the same for qdisc_graft() result.

Jakub Kicinski

maintainer

2023-05-17 18:48 UTC #43 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting

Quoted 5 lines · On Wed, 17 May 2023 11:49:10 +0300 Vlad Buslov wrote:

Quoted 4 lines · Jakub Kicinski
Quoted 2 lines · On Tue, 16 May 2023 15:58:46 -0700 Peilin Ye wrote:
Seems like trying to delete an "in-use" cls_u32 filter returns -EBUSY

Quoted 7 lines

Quoted 2 lines
I meant -EBUSY due to a race (another operation being in flight). I think that's different.
I wonder if somehow leveraging existing tc_modify_qdisc() 'replay' functionality instead of returning error to the user would be a better approach? Currently the function is replayed when qdisc_create() returns EAGAIN. It should be trivial to do the same for qdisc_graft() result.

Sounds better than returning -EBUSY to the user and expecting them to retry, yes.

Jakub Kicinski

maintainer

2023-05-17 18:48 UTC #45 lore raw

Re: [PATCH net 6/6] net/sched: qdisc_destroy() old ingress and clsact Qdiscs before grafting