net/sched: Fixes for sch_ingress and sch_clsact

From: Peilin Ye <[email protected]>

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

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

Reported-by [email protected]

Closes https://lore.kernel.org/r/[email protected]/ open here

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

---
change in v5:
- avoid underflowing @ingress_needed_key in ->destroy(), reported by Pedro

change in v3, v4:
- add in-body From: tag

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

net/sched/sch_ingress.c +6 -0

index 84838128b9c5..f9ef6deb2770 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);

@@ -101,6 +104,9 @@ static void ingress_destroy(struct Qdisc *sch)
  {
  	struct ingress_sched_data *q = qdisc_priv(sch);
 
+	if (sch->parent != TC_H_INGRESS)
+		return;
+
  	tcf_block_put_ext(q->block, sch, &q->block_info);
  	net_dec_ingress_queue();
  }

From: Peilin Ye <[email protected]>

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

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

Reported-by [email protected]

Closes https://lore.kernel.org/r/[email protected]/ open here

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

---
change in v5:
- avoid underflowing @ingress_needed_key in ->destroy(), reported by Pedro

change in v3, v4:
- add in-body From: tag

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

net/sched/sch_ingress.c +6 -1

index 84838128b9c5..f9ef6deb2770 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);

@@ -101,6 +104,9 @@ static void ingress_destroy(struct Qdisc *sch)
 {
        struct ingress_sched_data *q = qdisc_priv(sch);
 
+       if (sch->parent != TC_H_INGRESS)
+               return;
+
        tcf_block_put_ext(q->block, sch, &q->block_info);
        net_dec_ingress_queue();
 }
--

2.20.1

From: Peilin Ye <[email protected]>

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]>

---
change in v5:
- avoid underflowing @egress_needed_key in ->destroy(), reported by Pedro

change in v3, v4:
- add in-body From: tag

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

net/sched/sch_ingress.c +6 -0

index f9ef6deb2770..35963929e117 100644
@@ -225,6 +225,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();
 

@@ -254,6 +257,9 @@ static void clsact_destroy(struct Qdisc *sch)
  {
  	struct clsact_sched_data *q = qdisc_priv(sch);
 
+	if (sch->parent != TC_H_CLSACT)
+		return;
+
  	tcf_block_put_ext(q->egress_block, sch, &q->egress_block_info);
  	tcf_block_put_ext(q->ingress_block, sch, &q->ingress_block_info);
 

Quoted 2 lines · Peilin Ye

From: Peilin Ye <[email protected]>

Quoted 6 lines

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]>

Tested-by Pedro Tammela <[email protected]>

Quoted 35 lines

---
change in v5:
- avoid underflowing @egress_needed_key in ->destroy(), reported by Pedro

change in v3, v4:
- add in-body From: tag

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

net/sched/sch_ingress.c +6 -0

index f9ef6deb2770..35963929e117 100644
@@ -225,6 +225,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();
 

@@ -254,6 +257,9 @@ static void clsact_destroy(struct Qdisc *sch)
  {
      struct clsact_sched_data *q = qdisc_priv(sch);
 
+     if (sch->parent != TC_H_CLSACT)
+             return;
+
      tcf_block_put_ext(q->egress_block, sch, &q->egress_block_info);
      tcf_block_put_ext(q->ingress_block, sch, &q->ingress_block_info);
 

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

Quoted 1 line

Quoted 1 line

qdisc.flags.value_() # TCQ_F_INGRESS

From: Peilin Ye <[email protected]>

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

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")

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

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

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

---
change in v3, v4:
- add in-body From: tag

  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 35963929e117..e43a45499372 100644
@@ -140,7 +140,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,

@@ -281,7 +281,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,

From: Peilin Ye <[email protected]>

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")

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

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

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

---
change in v3, v4:
- add in-body From: tag

  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");

From: Peilin Ye <[email protected]>

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-unlocked RTM_{NEW,DEL,GET}TFILTER requests (thanks Hillf Danton for the hint), when replacing ingress or clsact Qdiscs, for example, the old Qdisc ("@old") could access the same miniq_{in,e}gress pointer(s) concurrently with the new Qdisc ("@new"), causing race conditions [1] including a use-after-free bug 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

...

@old and @new should not affect each other. In other words, @old should never modify miniq_{in,e}gress after @new, and @new should not update @old's RCU state. Fixing without changing sch_api.c turned out to be difficult (please refer to Closes: for discussions). Instead, make sure @new's first call always happen after @old's last call, in qdisc_destroy(), has finished:

In qdisc_graft(), return -EAGAIN and tell the caller to replay (suggested by Vlad Buslov) if @old has any ongoing RTNL-unlocked 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-unlocked filter requests. Introduce a non-static version of qdisc_destroy() that does a TCQ_F_BUILTIN check, just like qdisc_put() etc.

Depends on patch "net/sched: Refactor qdisc_graft() for ingress and clsact Qdiscs".

[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-unlocked)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
mini_qdisc_pair_swap(A) (1st)
|
| RTM_NEWQDISC (B, RTNL-locked)
RCU sync 2 qdisc_graft(B)
| 1 notify_and_destroy(A)
|
tcf_block_release(A) 0 RTM_NEWTFILTER (Y, RTNL-unlocked)
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 only one of the possible consequences of concurrently accessing miniq_{in,e}gress pointers. The point is clear though: again, A should never modify those per-net_device pointers after B, and B should not update A's RCU state.

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]

Closes https://lore.kernel.org/r/[email protected]/ open here

Cc Hillf Danton <[email protected]>

Cc Vlad Buslov <[email protected]>

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

---
change in v5:
- reinitialize @q, @p (suggested by Vlad) and @tcm before replaying, just like @flags in tc_new_tfilter()

change in v3, v4:
- add in-body From: tag

changes in v2:
- replay the request if the current Qdisc has any ongoing RTNL-unlocked filter requests (Vlad)
- minor changes in code comments and commit log

  include/net/sch_generic.h |  8 ++++++++
  net/sched/sch_api.c       | 40 ++++++++++++++++++++++++++++++---------
  net/sched/sch_generic.c   | 14 +++++++++++---
  3 files changed, 50 insertions(+), 12 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 +31 -9

index f72a581666a2..286b7c58f5b9 100644
@@ -1080,10 +1080,18 @@ 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;
  			}
+
+			/* Replay if the current ingress (or clsact) Qdisc has ongoing
+			 * RTNL-unlocked filter request(s).  This is the counterpart of that
+			 * qdisc_refcount_inc_nz() call in __tcf_qdisc_find().
+			 */
+			if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping))
+				return -EAGAIN;
  		}
 
  		if (dev->flags & IFF_UP)

@@ -1104,8 +1112,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 +1135,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)

@@ -1450,19 +1464,22 @@ static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
  			struct netlink_ext_ack *extack)
  {
  	struct net *net = sock_net(skb->sk);
-	struct tcmsg *tcm = nlmsg_data(n);
  	struct nlattr *tca[TCA_MAX + 1];
  	struct net_device *dev;
+	struct Qdisc *q, *p;
+	struct tcmsg *tcm;
  	u32 clid;
-	struct Qdisc *q = NULL;
-	struct Qdisc *p = NULL;
  	int err;
 
+replay:
  	err = nlmsg_parse_deprecated(n, sizeof(*tcm), tca, TCA_MAX,
  				     rtm_tca_policy, extack);
  	if (err < 0)
  		return err;
 
+	tcm = nlmsg_data(n);
+	q = p = NULL;
+
  	dev = __dev_get_by_index(net, tcm->tcm_ifindex);
  	if (!dev)
  		return -ENODEV;

@@ -1515,8 +1532,11 @@ static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
  			return -ENOENT;
  		}
  		err = qdisc_graft(dev, p, skb, n, clid, NULL, q, extack);
-		if (err != 0)
+		if (err != 0) {
+			if (err == -EAGAIN)
+				goto replay;
  			return err;
+		}
  	} else {
  		qdisc_notify(net, skb, n, clid, NULL, q, NULL);
  	}

@@ -1704,6 +1724,8 @@ static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
  	if (err) {
  		if (q)
  			qdisc_put(q);
+		if (err == -EAGAIN)
+			goto replay;
  		return err;
  	}
 

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);

Quoted 91 lines · Peilin Ye

From: Peilin Ye <[email protected]>

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-unlocked RTM_{NEW,DEL,GET}TFILTER requests (thanks Hillf Danton for the hint), when replacing ingress or clsact Qdiscs, for example, the old Qdisc ("@old") could access the same miniq_{in,e}gress pointer(s) concurrently with the new Qdisc ("@new"), causing race conditions [1] including a use-after-free bug 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

...

@old and @new should not affect each other. In other words, @old should never modify miniq_{in,e}gress after @new, and @new should not update @old's RCU state. Fixing without changing sch_api.c turned out to be difficult (please refer to Closes: for discussions). Instead, make sure @new's first call always happen after @old's last call, in qdisc_destroy(), has finished:

In qdisc_graft(), return -EAGAIN and tell the caller to replay (suggested by Vlad Buslov) if @old has any ongoing RTNL-unlocked 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-unlocked filter requests. Introduce a non-static version of qdisc_destroy() that does a TCQ_F_BUILTIN check, just like qdisc_put() etc.

Depends on patch "net/sched: Refactor qdisc_graft() for ingress and clsact Qdiscs".

[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-unlocked)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
mini_qdisc_pair_swap(A) (1st)
|
| RTM_NEWQDISC (B, RTNL-locked)
RCU sync 2 qdisc_graft(B)
| 1 notify_and_destroy(A)
|
tcf_block_release(A) 0 RTM_NEWTFILTER (Y, RTNL-unlocked)
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 only one of the possible consequences of concurrently accessing miniq_{in,e}gress pointers. The point is clear though: again, A should never modify those per-net_device pointers after B, and B should not update A's RCU state.

Quoted 7 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]

Closes https://lore.kernel.org/r/[email protected]/ open here

Cc Hillf Danton <[email protected]>

Cc Vlad Buslov <[email protected]>

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

Tested-by Pedro Tammela <[email protected]>

Quoted 190 lines

---
change in v5:
- reinitialize @q, @p (suggested by Vlad) and @tcm before replaying, just like @flags in tc_new_tfilter()

change in v3, v4:
- add in-body From: tag

changes in v2:
- replay the request if the current Qdisc has any ongoing RTNL-unlocked filter requests (Vlad)
- minor changes in code comments and commit log

  include/net/sch_generic.h |  8 ++++++++
  net/sched/sch_api.c       | 40 ++++++++++++++++++++++++++++++---------
  net/sched/sch_generic.c   | 14 +++++++++++---
  3 files changed, 50 insertions(+), 12 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 +31 -9

index f72a581666a2..286b7c58f5b9 100644
@@ -1080,10 +1080,18 @@ 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;
                      }
+
+                     /* Replay if the current ingress (or clsact) Qdisc has ongoing
+                      * RTNL-unlocked filter request(s).  This is the counterpart of that
+                      * qdisc_refcount_inc_nz() call in __tcf_qdisc_find().
+                      */
+                     if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping))
+                             return -EAGAIN;
              }
 
              if (dev->flags & IFF_UP)

@@ -1104,8 +1112,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 +1135,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)

@@ -1450,19 +1464,22 @@ static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
                      struct netlink_ext_ack *extack)
  {
      struct net *net = sock_net(skb->sk);
-     struct tcmsg *tcm = nlmsg_data(n);
      struct nlattr *tca[TCA_MAX + 1];
      struct net_device *dev;
+     struct Qdisc *q, *p;
+     struct tcmsg *tcm;
      u32 clid;
-     struct Qdisc *q = NULL;
-     struct Qdisc *p = NULL;
      int err;
 
+replay:
      err = nlmsg_parse_deprecated(n, sizeof(*tcm), tca, TCA_MAX,
                                   rtm_tca_policy, extack);
      if (err < 0)
              return err;
 
+     tcm = nlmsg_data(n);
+     q = p = NULL;
+
      dev = __dev_get_by_index(net, tcm->tcm_ifindex);
      if (!dev)
              return -ENODEV;

@@ -1515,8 +1532,11 @@ static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
                      return -ENOENT;
              }
              err = qdisc_graft(dev, p, skb, n, clid, NULL, q, extack);
-             if (err != 0)
+             if (err != 0) {
+                     if (err == -EAGAIN)
+                             goto replay;
                      return err;
+             }
      } else {
              qdisc_notify(net, skb, n, clid, NULL, q, NULL);
      }

@@ -1704,6 +1724,8 @@ static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
      if (err) {
              if (q)
                      qdisc_put(q);
+             if (err == -EAGAIN)
+                     goto replay;
              return err;
      }
 

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);

When you have a moment - could you run tc monitor in parallel to the reproducer and double check it generates the correct events...

Quoted 2 lines · Jamal Hadi Salim

When you have a moment - could you run tc monitor in parallel to the reproducer and double check it generates the correct events...

FTR, I'll wait a bit to apply this series, to allow for the above tests. Unless someone will scream very loudly very soon, it's not going to enter today's PR. Since the addressed issue is an ancient one, it should not a problem, I hope.

Cheers,

Paolo

Quoted 91 lines · Peilin Ye

From: Peilin Ye <[email protected]>

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-unlocked RTM_{NEW,DEL,GET}TFILTER requests (thanks Hillf Danton for the hint), when replacing ingress or clsact Qdiscs, for example, the old Qdisc ("@old") could access the same miniq_{in,e}gress pointer(s) concurrently with the new Qdisc ("@new"), causing race conditions [1] including a use-after-free bug 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

...

@old and @new should not affect each other. In other words, @old should never modify miniq_{in,e}gress after @new, and @new should not update @old's RCU state. Fixing without changing sch_api.c turned out to be difficult (please refer to Closes: for discussions). Instead, make sure @new's first call always happen after @old's last call, in qdisc_destroy(), has finished:

In qdisc_graft(), return -EAGAIN and tell the caller to replay (suggested by Vlad Buslov) if @old has any ongoing RTNL-unlocked 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-unlocked filter requests. Introduce a non-static version of qdisc_destroy() that does a TCQ_F_BUILTIN check, just like qdisc_put() etc.

Depends on patch "net/sched: Refactor qdisc_graft() for ingress and clsact Qdiscs".

[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-unlocked)
__tcf_qdisc_find(A) 10
tcf_chain0_head_change(A)
mini_qdisc_pair_swap(A) (1st)
|
| RTM_NEWQDISC (B, RTNL-locked)
RCU sync 2 qdisc_graft(B)
| 1 notify_and_destroy(A)
|
tcf_block_release(A) 0 RTM_NEWTFILTER (Y, RTNL-unlocked)
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 only one of the possible consequences of concurrently accessing miniq_{in,e}gress pointers. The point is clear though: again, A should never modify those per-net_device pointers after B, and B should not update A's RCU state.

Quoted 7 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]

Closes https://lore.kernel.org/r/[email protected]/ open here

Cc Hillf Danton <[email protected]>

Cc Vlad Buslov <[email protected]>

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

Tested-by Pedro Tammela <[email protected]>

Quoted 3 lines · Pedro Tammela

Quoted 1 line · Peilin Ye

From: Peilin Ye <[email protected]>

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

[...] Peilin, Pedro will post the new repro.

Quoted 1 line · Jamal Hadi Salim

[...] Peilin, Pedro will post the new repro.

We tweaked the reproducer to:
---
r0 = socket$netlink(0x10, 0x3, 0x0)
r1 = socket(0x10, 0x803, 0x0)
sendmsg$nl_route_sched(r1, &(0x7f0000000300)={0x0, 0x0, &(0x7f0000000240)={&(0x7f0000000380)=ANY=[], 0x24}}, 0x0) getsockname$packet(r1, &(0x7f0000000200)={0x11, 0x0, <r2=>0x0, 0x1, 0x0, 0x6, @broadcast}, &(0x7f0000000440)=0x14)
sendmsg$nl_route(r0, &(0x7f0000000040)={0x0, 0x0, &(0x7f0000000000)={&(0x7f0000000080)=ANY=[@ANYBLOB="480000001000050700"/20, @ANYRES32=r2, @ANYBLOB="0000000000000000280012000900010076657468"], 0x48}}, 0x0)
sendmsg$nl_route_sched(0xffffffffffffffff, &(0x7f00000002c0)={0x0, 0x0, &(0x7f0000000280)={&(0x7f0000000540)=@newqdisc={0x30, 0x24, 0xf0b, 0x0, 0x0, {0x0, 0x0, 0x0, r2, {}, {0xfff1, 0xffff}}, [@qdisc_kind_options=@q_ingress={0xc}]}, 0x30}}, 0x0) sendmsg$nl_route_sched(0xffffffffffffffff, &(0x7f0000000340)={0x0, 0x0, &(0x7f00000000c0)={&(0x7f0000000580)=@newtfilter={0x3c, 0x2c, 0xd27, 0x0, 0x0, {0x0, 0x0, 0x0, r2, {}, {0xfff1, 0xffff}, {0xc}}, [@filter_kind_options=@f_flower={{0xb}, {0xc, 0x2, [@TCA_FLOWER_CLASSID={0x8}]}}]}, 0x3c}}, 0x0)
r4 = socket$netlink(0x10, 0x3, 0x0)
sendmmsg(r4, &(0x7f00000002c0), 0x40000000000009f, 0x0)
r5 = socket$netlink(0x10, 0x3, 0x0)
sendmmsg(r5, &(0x7f00000002c0), 0x40000000000009f, 0x0)
---

We then generate the C program with:
syz-prog2c -sandbox none -enable net_dev -threaded -repeat 0 -prog peilin.syz > repro.c

Now here comes a very important detail. The above will create a new net namespace to shoot the netlink messages. We are only able to reproduce the deadlock with your patches if we comment the creation of the new namespace out:
---

repro.c +3 -3

index ee8eb0726..5cdbfb289 100644
@@ -1121,9 +1121,8 @@ static int do_sandbox_none(void)
   sandbox_common();
   drop_caps();
   initialize_netdevices_init();
-  if (unshare(CLONE_NEWNET)) {
-  }
+  // Doesn't seem to deadlock in a new netns
+  // if (unshare(CLONE_NEWNET)) {
+  // }
   write_file("/proc/sys/net/ipv4/ping_group_range", "0 65535");
   initialize_netdevices();
   setup_binderfs();
 
---

The reason we did this was to check on the event with 'tc mon'. The splat is quite big, see attached. It has all the indications of a deadlock in the rtnl_lock.

Thanks a lot, I'll get right on it.

Quoted 1 line · On Fri, 26 May 2023 16:09:51 -0700 Peilin Ye wrote:

Thanks a lot, I'll get right on it.

Any insights? Is it just a live-lock inherent to the retry scheme or we actually forget to release the lock/refcnt?

Hi Jakub and all,

Quoted 5 lines · Jakub Kicinski

Quoted 1 line · On Fri, 26 May 2023 16:09:51 -0700 Peilin Ye wrote:

Thanks a lot, I'll get right on it.

Any insights? Is it just a live-lock inherent to the retry scheme or we actually forget to release the lock/refcnt?

I think it's just a thread holding the RTNL mutex for too long (replaying too many times). We could replay for arbitrary times in tc_{modify,get}_qdisc() if the user keeps sending RTNL-unlocked filter requests for the old Qdisc.

I tested the new reproducer Pedro posted, on:

1. All 6 v5 patches, FWIW, which caused a similar hang as Pedro reported

2. First 5 v5 patches, plus patch 6 in v1 (no replaying), did not trigger any issues (in about 30 minutes).

3. All 6 v5 patches, plus this diff:

net/sched/sch_api.c +4 -1

index 286b7c58f5b9..988718ba5abe 100644
@@ -1090,8 +1090,11 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
                         * RTNL-unlocked filter request(s).  This is the counterpart of that
                         * qdisc_refcount_inc_nz() call in __tcf_qdisc_find().
                         */
-                       if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping))
+                       if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping)) {
+                               rtnl_unlock();
+                               rtnl_lock();
                                return -EAGAIN;
+                       }
                }
 
                if (dev->flags & IFF_UP)

Did not trigger any issues (in about 30 mintues) either.

What would you suggest?

Thanks,
Peilin Ye

Quoted 7 lines · Peilin Ye

Hi Jakub and all,

Quoted 3 lines · Jakub Kicinski

Quoted 1 line · On Fri, 26 May 2023 16:09:51 -0700 Peilin Ye wrote:

Thanks a lot, I'll get right on it.

Quoted 7 lines

Quoted 2 lines

Any insights? Is it just a live-lock inherent to the retry scheme or we actually forget to release the lock/refcnt?

I think it's just a thread holding the RTNL mutex for too long (replaying too many times). We could replay for arbitrary times in tc_{modify,get}_qdisc() if the user keeps sending RTNL-unlocked filter requests for the old Qdisc.

Quoted 28 lines

I tested the new reproducer Pedro posted, on:

1. All 6 v5 patches, FWIW, which caused a similar hang as Pedro reported

2. First 5 v5 patches, plus patch 6 in v1 (no replaying), did not trigger any issues (in about 30 minutes).

3. All 6 v5 patches, plus this diff:

net/sched/sch_api.c +4 -1

index 286b7c58f5b9..988718ba5abe 100644
@@ -1090,8 +1090,11 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
                         * RTNL-unlocked filter request(s).  This is the counterpart of that
                         * qdisc_refcount_inc_nz() call in __tcf_qdisc_find().
                         */
-                       if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping))
+                       if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping)) {
+                               rtnl_unlock();
+                               rtnl_lock();
                                return -EAGAIN;
+                       }
                }
 
                if (dev->flags & IFF_UP)

Quoted 3 lines

Did not trigger any issues (in about 30 mintues) either.

What would you suggest?

I am more worried it is a wackamole situation. We fixed the first reproducer with essentially patches 1-4 but we opened a new one which the second reproducer catches. One thing the current reproducer does is create a lot rtnl contention in the beggining by creating all those devices and then after it is just creating/deleting qdisc and doing update with flower where such contention is reduced. i.e it may just take longer for the mole to pop up.

Why dont we push the V1 patch in and then worry about getting clever with EAGAIN after? Can you test the V1 version with the repro Pedro posted? It shouldnt have these issues. Also it would be interesting to see how performance of the parallel updates to flower is affected.

Quoted 8 lines · Jamal Hadi Salim

Quoted 7 lines · Peilin Ye

Hi Jakub and all,

Quoted 3 lines · Jakub Kicinski

Quoted 1 line · On Fri, 26 May 2023 16:09:51 -0700 Peilin Ye wrote:

Thanks a lot, I'll get right on it.

Quoted 7 lines

Quoted 7 lines

Quoted 2 lines

Any insights? Is it just a live-lock inherent to the retry scheme or we actually forget to release the lock/refcnt?

I think it's just a thread holding the RTNL mutex for too long (replaying too many times). We could replay for arbitrary times in tc_{modify,get}_qdisc() if the user keeps sending RTNL-unlocked filter requests for the old Qdisc.

After looking very carefully at the code I think I know what the issue might be:

Task 1 graft Qdisc Task 2 new filter

           +                    +
           |                    |
           v                    v
        rtnl_lock()       take  q->refcnt
           +                    +
           |                    |
           v                    v

Spin while q->refcnt!=1 Block on rtnl_lock() indefinitely due to -EAGAIN

This will cause a real deadlock with the proposed patch. I'll try to come up with a better approach. Sorry for not seeing it earlier.

Quoted 41 lines

Quoted 28 lines

I tested the new reproducer Pedro posted, on:

1. All 6 v5 patches, FWIW, which caused a similar hang as Pedro reported

2. First 5 v5 patches, plus patch 6 in v1 (no replaying), did not trigger any issues (in about 30 minutes).

3. All 6 v5 patches, plus this diff:

net/sched/sch_api.c +4 -1

index 286b7c58f5b9..988718ba5abe 100644
@@ -1090,8 +1090,11 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
                         * RTNL-unlocked filter request(s).  This is the counterpart of that
                         * qdisc_refcount_inc_nz() call in __tcf_qdisc_find().
                         */
-                       if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping))
+                       if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping)) {
+                               rtnl_unlock();
+                               rtnl_lock();
                                return -EAGAIN;
+                       }
                }
 
                if (dev->flags & IFF_UP)

Quoted 3 lines

Did not trigger any issues (in about 30 mintues) either.

What would you suggest?

I am more worried it is a wackamole situation. We fixed the first reproducer with essentially patches 1-4 but we opened a new one which the second reproducer catches. One thing the current reproducer does is create a lot rtnl contention in the beggining by creating all those devices and then after it is just creating/deleting qdisc and doing update with flower where such contention is reduced. i.e it may just take longer for the mole to pop up.

Quoted 4 lines

Why dont we push the V1 patch in and then worry about getting clever with EAGAIN after? Can you test the V1 version with the repro Pedro posted? It shouldnt have these issues. Also it would be interesting to see how performance of the parallel updates to flower is affected.

This or at least push first 4 patches of this series. They target other older commits and fix straightforward issues with the API.

If livelock with concurrent filters insertion is an issue, then it can be remedied by setting a new Qdisc->flags bit "DELETED-REJECT-NEW-FILTERS" and checking for it together with QDISC_CLASS_OPS_DOIT_UNLOCKED in order to force any concurrent filter insertion coming after the flag is set to synchronize on rtnl lock.

After looking very carefully at the code I think I know what the issue might be:

Task 1 graft Qdisc Task 2 new filter

           +                    +
           |                    |
           v                    v
        rtnl_lock()       take  q->refcnt
           +                    +
           |                    |
           v                    v

Spin while q->refcnt!=1 Block on rtnl_lock() indefinitely due to -EAGAIN

This will cause a real deadlock with the proposed patch. I'll try to come up with a better approach. Sorry for not seeing it earlier.

- Account for such cls_api behavior in sch_api by dropping and re-tacking the lock before replaying. This actually seems to be quite straightforward since 'replay' functionality that we are reusing for this is designed for similar behavior - it releases rtnl lock before loading a sch module, takes the lock again and safely replays the function by re-obtaining all the necessary data.

If livelock with concurrent filters insertion is an issue, then it can be remedied by setting a new Qdisc->flags bit "DELETED-REJECT-NEW-FILTERS" and checking for it together with QDISC_CLASS_OPS_DOIT_UNLOCKED in order to force any concurrent filter insertion coming after the flag is set to synchronize on rtnl lock.

Quoted 11 lines · Vlad Buslov

After looking very carefully at the code I think I know what the issue might be:

Task 1 graft Qdisc Task 2 new filter

           +                    +
           |                    |
           v                    v
        rtnl_lock()       take  q->refcnt
           +                    +
           |                    |
           v                    v

Quoted 4 lines

Spin while q->refcnt!=1 Block on rtnl_lock() indefinitely due to -EAGAIN

This will cause a real deadlock with the proposed patch. I'll try to come up with a better approach. Sorry for not seeing it earlier.

Thanks a lot for pointing this out! The reproducers add flower filters to ingress Qdiscs so I didn't think of rtnl_lock()'ed filter requests...

Quoted 6 lines · Vlad Buslov

- Account for such cls_api behavior in sch_api by dropping and re-tacking the lock before replaying. This actually seems to be quite straightforward since 'replay' functionality that we are reusing for this is designed for similar behavior - it releases rtnl lock before loading a sch module, takes the lock again and safely replays the function by re-obtaining all the necessary data.

Yes, I've tested this using that reproducer Pedro posted.

Quoted 5 lines · Vlad Buslov

If livelock with concurrent filters insertion is an issue, then it can be remedied by setting a new Qdisc->flags bit "DELETED-REJECT-NEW-FILTERS" and checking for it together with QDISC_CLASS_OPS_DOIT_UNLOCKED in order to force any concurrent filter insertion coming after the flag is set to synchronize on rtnl lock.

Thanks for the suggestion! I'll try this approach.

Currently QDISC_CLASS_OPS_DOIT_UNLOCKED is checked after taking a refcnt of the "being-deleted" Qdisc. I'll try forcing "late" requests (that arrive later than Qdisc is flagged as being-deleted) sync on RTNL lock without (before) taking the Qdisc refcnt (otherwise I think Task 1 will replay for even longer?).

Quoted 6 lines

Quoted 5 lines

If livelock with concurrent filters insertion is an issue, then it can be remedied by setting a new Qdisc->flags bit "DELETED-REJECT-NEW-FILTERS" and checking for it together with QDISC_CLASS_OPS_DOIT_UNLOCKED in order to force any concurrent filter insertion coming after the flag is set to synchronize on rtnl lock.

Quoted 7 lines

Thanks for the suggestion! I'll try this approach.

Currently QDISC_CLASS_OPS_DOIT_UNLOCKED is checked after taking a refcnt of the "being-deleted" Qdisc. I'll try forcing "late" requests (that arrive later than Qdisc is flagged as being-deleted) sync on RTNL lock without (before) taking the Qdisc refcnt (otherwise I think Task 1 will replay for even longer?).

Yeah, I see what you mean. Looking at the code __tcf_qdisc_find() already returns -EINVAL when q->refcnt is zero, so maybe returning -EINVAL from that function when "DELETED-REJECT-NEW-FILTERS" flags is set is also fine? Would be much easier to implement as opposed to moving rtnl_lock there.

Quoted 6 lines

Quoted 5 lines

If livelock with concurrent filters insertion is an issue, then it can be remedied by setting a new Qdisc->flags bit "DELETED-REJECT-NEW-FILTERS" and checking for it together with QDISC_CLASS_OPS_DOIT_UNLOCKED in order to force any concurrent filter insertion coming after the flag is set to synchronize on rtnl lock.

Quoted 7 lines

Thanks for the suggestion! I'll try this approach.

Currently QDISC_CLASS_OPS_DOIT_UNLOCKED is checked after taking a refcnt of the "being-deleted" Qdisc. I'll try forcing "late" requests (that arrive later than Qdisc is flagged as being-deleted) sync on RTNL lock without (before) taking the Qdisc refcnt (otherwise I think Task 1 will replay for even longer?).

Yeah, I see what you mean. Looking at the code __tcf_qdisc_find() already returns -EINVAL when q->refcnt is zero, so maybe returning -EINVAL from that function when "DELETED-REJECT-NEW-FILTERS" flags is set is also fine? Would be much easier to implement as opposed to moving rtnl_lock there.

Hi Vlad and all,

Quoted 14 lines · Vlad Buslov

Quoted 6 lines

Quoted 5 lines

If livelock with concurrent filters insertion is an issue, then it can be remedied by setting a new Qdisc->flags bit "DELETED-REJECT-NEW-FILTERS" and checking for it together with QDISC_CLASS_OPS_DOIT_UNLOCKED in order to force any concurrent filter insertion coming after the flag is set to synchronize on rtnl lock.

Quoted 7 lines

Thanks for the suggestion! I'll try this approach.

Currently QDISC_CLASS_OPS_DOIT_UNLOCKED is checked after taking a refcnt of the "being-deleted" Qdisc. I'll try forcing "late" requests (that arrive later than Qdisc is flagged as being-deleted) sync on RTNL lock without (before) taking the Qdisc refcnt (otherwise I think Task 1 will replay for even longer?).

Quoted 5 lines

Yeah, I see what you mean. Looking at the code __tcf_qdisc_find() already returns -EINVAL when q->refcnt is zero, so maybe returning -EINVAL from that function when "DELETED-REJECT-NEW-FILTERS" flags is set is also fine? Would be much easier to implement as opposed to moving rtnl_lock there.

I implemented [1] this suggestion and tested the livelock issue in QEMU (-m 16G, CONFIG_NR_CPUS=8). I tried deleting the ingress Qdisc (let's call it "request A") while it has a lot of ongoing filter requests, and here's the result:

#1 #2 #3 #4
----------------------------------------------------------
a. refcnt 89 93 230 571
b. replayed 167,568 196,450 336,291 878,027

   c. time real   0m2.478s   0m2.746s   0m3.693s   0m9.461s
           user   0m0.000s   0m0.000s   0m0.000s   0m0.000s
            sys   0m0.623s   0m0.681s   0m1.119s   0m2.770s

   a. is the Qdisc refcnt when A calls qdisc_graft() for the first time;
   b. is the number of times A has been replayed;
   c. is the time(1) output for A.

a. and b. are collected from printk() output. This is better than before, but A could still be replayed for hundreds of thousands of times and hang for a few seconds.

Is this okay? If not, is it possible (or should we) to make A really _wait_ on Qdisc refcnt, instead of "busy-replaying"?

Thanks,
Peilin Ye

[1] Diff against v5 patch 6 (printk() calls not included):

include/net/sch_generic.h +1 -0

index 3e9cc43cbc90..de7b0538b309 100644
@@ -94,6 +94,7 @@ struct Qdisc {
 #define TCQ_F_INVISIBLE                0x80 /* invisible by default in dump */
 #define TCQ_F_NOLOCK           0x100 /* qdisc does not require locking */
 #define TCQ_F_OFFLOADED                0x200 /* qdisc is offloaded to HW */
+#define TCQ_F_DESTROYING       0x400 /* destroying, reject filter requests */
        u32                     limit;
        const struct Qdisc_ops  *ops;
        struct qdisc_size_table __rcu *stab;

include/net/sch_generic.h +2 -0

+}
+
 /* For !TCQ_F_NOLOCK qdisc, qdisc_run_begin/end() must be invoked with
  * the qdisc root lock acquired.
  */

net/sched/cls_api.c +1 -1

index 2621550bfddc..3e7f6f286ac0 100644
@@ -1172,7 +1172,7 @@ static int __tcf_qdisc_find(struct net *net, struct Qdisc **q,
                *parent = (*q)->handle;
        } else {
                *q = qdisc_lookup_rcu(dev, TC_H_MAJ(*parent));
-               if (!*q) {
+               if (!*q || qdisc_is_destroying(*q)) {
                        NL_SET_ERR_MSG(extack, "Parent Qdisc doesn't exists");
                        err = -EINVAL;
                        goto errout_rcu;

net/sched/sch_api.c +10 -4

index 286b7c58f5b9..d6e47546c7fe 100644
@@ -1086,12 +1086,18 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
                                return -ENOENT;
                        }
 
-                       /* Replay if the current ingress (or clsact) Qdisc has ongoing
-                        * RTNL-unlocked filter request(s).  This is the counterpart of that
-                        * qdisc_refcount_inc_nz() call in __tcf_qdisc_find().
+                       /* If current ingress (clsact) Qdisc has ongoing filter requests, stop
+                        * accepting any more by marking it as "being destroyed", then tell the
+                        * caller to replay by returning -EAGAIN.
                         */
-                       if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping))
+                       q = dev_queue->qdisc_sleeping;
+                       if (!qdisc_refcount_dec_if_one(q)) {
+                               q->flags |= TCQ_F_DESTROYING;
+                               rtnl_unlock();
+                               schedule();
+                               rtnl_lock();
                                return -EAGAIN;
+                       }
                }
 
                if (dev->flags & IFF_UP)

include/net/sch_generic.h static inline bool qdisc_is_empty(const struct Qdisc *qdisc) · line 191

Quoted 3 lines · Peilin Ye

include/net/sch_generic.h +3 -0

+static inline bool qdisc_is_destroying(const struct Qdisc *qdisc)
+{
+       return qdisc->flags & TCQ_F_DESTROYING;

Hmm, do we need at least some kind of {READ|WRITE}_ONCE() for accessing flags since they are now used in unlocked filter code path?

Quoted 7 lines · Vlad Buslov

include/net/sch_generic.h static inline bool qdisc_is_empty(const struct Qdisc *qdisc) · line 191

Quoted 3 lines · Peilin Ye

include/net/sch_generic.h +3 -0

+static inline bool qdisc_is_destroying(const struct Qdisc *qdisc)
+{
+       return qdisc->flags & TCQ_F_DESTROYING;

Hmm, do we need at least some kind of {READ|WRITE}_ONCE() for accessing flags since they are now used in unlocked filter code path?

Thanks, after taking another look at cls_api.c, I noticed this code in tc_new_tfilter():

	err = tp->ops->change(net, skb, tp, cl, t->tcm_handle, tca, &fh,
			      flags, extack);
	if (err == 0) {
		tfilter_notify(net, skb, n, tp, block, q, parent, fh,
			       RTM_NEWTFILTER, false, rtnl_held, extack);
		tfilter_put(tp, fh);
		/* q pointer is NULL for shared blocks */
		if (q)
			q->flags &= ~TCQ_F_CAN_BYPASS;
	}               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

TCQ_F_CAN_BYPASS is cleared after e.g. adding a filter to the Qdisc, and it isn't atomic [1].

We also have this:

->dequeue()

    htb_dequeue()
      htb_dequeue_tree()
        qdisc_warn_nonwc():

  void qdisc_warn_nonwc(const char *txt, struct Qdisc *qdisc)
  {
          if (!(qdisc->flags & TCQ_F_WARN_NONWC)) {
                  pr_warn("%s: %s qdisc %X: is non-work-conserving?\n",
                          txt, qdisc->ops->id, qdisc->handle >> 16);
                  qdisc->flags |= TCQ_F_WARN_NONWC;
          }       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  }
  EXPORT_SYMBOL(qdisc_warn_nonwc);

Also non-atomic; isn't it possible for the above 2 underlined statements to race with each other? If true, I think we need to change Qdisc::flags to use atomic bitops, just like what we're doing for Qdisc::state and ::state2. It feels like a separate TODO, however.

I also thought about adding the new DELETED-REJECT-NEW-FILTERS flag to ::state2, but not sure if it's okay to extend it for our purpose.

Quoted 2 lines

I also thought about adding the new DELETED-REJECT-NEW-FILTERS flag to ::state2, but not sure if it's okay to extend it for our purpose.

As you described above qdisc->flags is already used to interact with cls api (including changing it dynamically), so I don't see why not.

Quoted 11 lines

	err = tp->ops->change(net, skb, tp, cl, t->tcm_handle, tca, &fh,
			      flags, extack);
	if (err == 0) {
		tfilter_notify(net, skb, n, tp, block, q, parent, fh,
			       RTM_NEWTFILTER, false, rtnl_held, extack);
		tfilter_put(tp, fh);
		/* q pointer is NULL for shared blocks */
		if (q)
			q->flags &= ~TCQ_F_CAN_BYPASS;
	}               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Quoted 2 lines

TCQ_F_CAN_BYPASS is cleared after e.g. adding a filter to the Qdisc, and it isn't atomic [1].

Yeah, I see we have already got such behavior in 3f05e6886a59 ("net_sched: unset TCQ_F_CAN_BYPASS when adding filters").

Quoted 17 lines

We also have this:

->dequeue()

    htb_dequeue()
      htb_dequeue_tree()
        qdisc_warn_nonwc():

  void qdisc_warn_nonwc(const char *txt, struct Qdisc *qdisc)
  {
          if (!(qdisc->flags & TCQ_F_WARN_NONWC)) {
                  pr_warn("%s: %s qdisc %X: is non-work-conserving?\n",
                          txt, qdisc->ops->id, qdisc->handle >> 16);
                  qdisc->flags |= TCQ_F_WARN_NONWC;
          }       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  }
  EXPORT_SYMBOL(qdisc_warn_nonwc);

Quoted 4 lines

Also non-atomic; isn't it possible for the above 2 underlined statements to race with each other? If true, I think we need to change Qdisc::flags to use atomic bitops, just like what we're doing for Qdisc::state and ::state2. It feels like a separate TODO, however.

It looks like even though 3f05e6886a59 ("net_sched: unset TCQ_F_CAN_BYPASS when adding filters") was introduced after cls api unlock by now we have these in exactly the same list of supported kernels (5.4 LTS and newer). Considering this, the conversion to the atomic bitops can be done as a standalone fix for cited commit and after it will have been accepted and backported the qdisc fix can just assume that qdisc->flags is an atomic bitops field in all target kernels and use it as-is. WDYT?

Quoted 5 lines · Vlad Buslov

Quoted 2 lines

I also thought about adding the new DELETED-REJECT-NEW-FILTERS flag to ::state2, but not sure if it's okay to extend it for our purpose.

As you described above qdisc->flags is already used to interact with cls api (including changing it dynamically), so I don't see why not.

Sorry, I don't follow, I meant qdisc->state2:

  enum qdisc_state2_t {
          /* Only for !TCQ_F_NOLOCK qdisc. Never access it directly.
           * Use qdisc_run_begin/end() or qdisc_is_running() instead.
           */
          __QDISC_STATE2_RUNNING,

};

NVM, I think using qdisc->flags after making it atomic sounds better.

Quoted 39 lines

Quoted 11 lines

	err = tp->ops->change(net, skb, tp, cl, t->tcm_handle, tca, &fh,
			      flags, extack);
	if (err == 0) {
		tfilter_notify(net, skb, n, tp, block, q, parent, fh,
			       RTM_NEWTFILTER, false, rtnl_held, extack);
		tfilter_put(tp, fh);
		/* q pointer is NULL for shared blocks */
		if (q)
			q->flags &= ~TCQ_F_CAN_BYPASS;
	}               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Quoted 2 lines

TCQ_F_CAN_BYPASS is cleared after e.g. adding a filter to the Qdisc, and it isn't atomic [1].

Yeah, I see we have already got such behavior in 3f05e6886a59 ("net_sched: unset TCQ_F_CAN_BYPASS when adding filters").

Quoted 17 lines

We also have this:

->dequeue()

    htb_dequeue()
      htb_dequeue_tree()
        qdisc_warn_nonwc():

  void qdisc_warn_nonwc(const char *txt, struct Qdisc *qdisc)
  {
          if (!(qdisc->flags & TCQ_F_WARN_NONWC)) {
                  pr_warn("%s: %s qdisc %X: is non-work-conserving?\n",
                          txt, qdisc->ops->id, qdisc->handle >> 16);
                  qdisc->flags |= TCQ_F_WARN_NONWC;
          }       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  }
  EXPORT_SYMBOL(qdisc_warn_nonwc);

Quoted 4 lines

Also non-atomic; isn't it possible for the above 2 underlined statements to race with each other? If true, I think we need to change Qdisc::flags to use atomic bitops, just like what we're doing for Qdisc::state and ::state2. It feels like a separate TODO, however.

Quoted 8 lines

It looks like even though 3f05e6886a59 ("net_sched: unset TCQ_F_CAN_BYPASS when adding filters") was introduced after cls api unlock by now we have these in exactly the same list of supported kernels (5.4 LTS and newer). Considering this, the conversion to the atomic bitops can be done as a standalone fix for cited commit and after it will have been accepted and backported the qdisc fix can just assume that qdisc->flags is an atomic bitops field in all target kernels and use it as-is. WDYT?

Sounds great, how about:

1. I'll post the non-replay version of the fix (after updating the commit message), and we apply that first, as suggested by Jamal

2. Make qdisc->flags atomic

3. Make the fix better by replaying and using the (now atomic) IS-DESTROYING flag with test_and_set_bit() and friends

?

Quoted 11 lines

Quoted 8 lines

It looks like even though 3f05e6886a59 ("net_sched: unset TCQ_F_CAN_BYPASS when adding filters") was introduced after cls api unlock by now we have these in exactly the same list of supported kernels (5.4 LTS and newer). Considering this, the conversion to the atomic bitops can be done as a standalone fix for cited commit and after it will have been accepted and backported the qdisc fix can just assume that qdisc->flags is an atomic bitops field in all target kernels and use it as-is. WDYT?

Sounds great, how about:

Quoted 2 lines

1. I'll post the non-replay version of the fix (after updating the commit message), and we apply that first, as suggested by Jamal

From my side there are no objections to any of the proposed approaches since we have never had any users with legitimate use-case where they need to replace/delete a qdisc concurrently with a filter update, so returning -EBUSY (or -EAGAIN) to the user in such case would work as either temporary or the final fix.

However, Jakub had reservations with such approach so don't know where we stand now regarding this.

Quoted 6 lines

2. Make qdisc->flags atomic

3. Make the fix better by replaying and using the (now atomic) IS-DESTROYING flag with test_and_set_bit() and friends

?

Again, no objections from my side. Ping me if you need help with any of these.

Quoted 33 lines

Quoted 14 lines

Quoted 6 lines

Quoted 5 lines

If livelock with concurrent filters insertion is an issue, then it can be remedied by setting a new Qdisc->flags bit "DELETED-REJECT-NEW-FILTERS" and checking for it together with QDISC_CLASS_OPS_DOIT_UNLOCKED in order to force any concurrent filter insertion coming after the flag is set to synchronize on rtnl lock.

Quoted 7 lines

Thanks for the suggestion! I'll try this approach.

Currently QDISC_CLASS_OPS_DOIT_UNLOCKED is checked after taking a refcnt of the "being-deleted" Qdisc. I'll try forcing "late" requests (that arrive later than Qdisc is flagged as being-deleted) sync on RTNL lock without (before) taking the Qdisc refcnt (otherwise I think Task 1 will replay for even longer?).

Quoted 5 lines

Yeah, I see what you mean. Looking at the code __tcf_qdisc_find() already returns -EINVAL when q->refcnt is zero, so maybe returning -EINVAL from that function when "DELETED-REJECT-NEW-FILTERS" flags is set is also fine? Would be much easier to implement as opposed to moving rtnl_lock there.

I implemented [1] this suggestion and tested the livelock issue in QEMU (-m 16G, CONFIG_NR_CPUS=8). I tried deleting the ingress Qdisc (let's call it "request A") while it has a lot of ongoing filter requests, and here's the result:

#1 #2 #3 #4
----------------------------------------------------------
a. refcnt 89 93 230 571
b. replayed 167,568 196,450 336,291 878,027

   c. time real   0m2.478s   0m2.746s   0m3.693s   0m9.461s
           user   0m0.000s   0m0.000s   0m0.000s   0m0.000s
            sys   0m0.623s   0m0.681s   0m1.119s   0m2.770s

Quoted 7 lines

   a. is the Qdisc refcnt when A calls qdisc_graft() for the first time;
   b. is the number of times A has been replayed;
   c. is the time(1) output for A.

a. and b. are collected from printk() output. This is better than before, but A could still be replayed for hundreds of thousands of times and hang for a few seconds.

I don't get where does few seconds waiting time come from. I'm probably missing something obvious here, but the waiting time should be the maximum filter op latency of new/get/del filter request that is already in-flight (i.e. already passed qdisc_is_destroying() check) and it should take several orders of magnitude less time.

do
tc filter add dev eth1 ingress proto all flower src_mac 00:11:22:33:44:55 action pass > /dev/null 2>&1 & done

do
tc filter add dev eth1 ingress proto all prio $i flower src_mac 00:11:22:33:44:55 action pass > /dev/null 2>&1 &
done ^^^^^^^

Quoted 41 lines · Vlad Buslov

Quoted 33 lines

Quoted 14 lines

Quoted 6 lines

Quoted 5 lines

If livelock with concurrent filters insertion is an issue, then it can be remedied by setting a new Qdisc->flags bit "DELETED-REJECT-NEW-FILTERS" and checking for it together with QDISC_CLASS_OPS_DOIT_UNLOCKED in order to force any concurrent filter insertion coming after the flag is set to synchronize on rtnl lock.

Quoted 7 lines

Thanks for the suggestion! I'll try this approach.

Currently QDISC_CLASS_OPS_DOIT_UNLOCKED is checked after taking a refcnt of the "being-deleted" Qdisc. I'll try forcing "late" requests (that arrive later than Qdisc is flagged as being-deleted) sync on RTNL lock without (before) taking the Qdisc refcnt (otherwise I think Task 1 will replay for even longer?).

Quoted 5 lines

Yeah, I see what you mean. Looking at the code __tcf_qdisc_find() already returns -EINVAL when q->refcnt is zero, so maybe returning -EINVAL from that function when "DELETED-REJECT-NEW-FILTERS" flags is set is also fine? Would be much easier to implement as opposed to moving rtnl_lock there.

I implemented [1] this suggestion and tested the livelock issue in QEMU (-m 16G, CONFIG_NR_CPUS=8). I tried deleting the ingress Qdisc (let's call it "request A") while it has a lot of ongoing filter requests, and here's the result:

#1 #2 #3 #4
----------------------------------------------------------
a. refcnt 89 93 230 571
b. replayed 167,568 196,450 336,291 878,027

   c. time real   0m2.478s   0m2.746s   0m3.693s   0m9.461s
           user   0m0.000s   0m0.000s   0m0.000s   0m0.000s
            sys   0m0.623s   0m0.681s   0m1.119s   0m2.770s

Quoted 7 lines

   a. is the Qdisc refcnt when A calls qdisc_graft() for the first time;
   b. is the number of times A has been replayed;
   c. is the time(1) output for A.

a. and b. are collected from printk() output. This is better than before, but A could still be replayed for hundreds of thousands of times and hang for a few seconds.

Quoted 5 lines

I don't get where does few seconds waiting time come from. I'm probably missing something obvious here, but the waiting time should be the maximum filter op latency of new/get/del filter request that is already in-flight (i.e. already passed qdisc_is_destroying() check) and it should take several orders of magnitude less time.

Yeah I agree, here's what I did:

In Terminal 1 I keep adding filters to eth1 in a naive and unrealistic loop:

  $ echo "1 1 32" > /sys/bus/netdevsim/new_device
  $ tc qdisc add dev eth1 ingress
  $ for (( i=1; i<=3000; i++ ))

Quoted 3 lines

do
tc filter add dev eth1 ingress proto all flower src_mac 00:11:22:33:44:55 action pass > /dev/null 2>&1 & done

When the loop is running, I delete the Qdisc in Terminal 2:

  $ time tc qdisc delete dev eth1 ingress

Which took seconds on average. However, if I specify a unique "prio" when adding filters in that loop, e.g.:

  $ for (( i=1; i<=3000; i++ ))

Quoted 3 lines

do
tc filter add dev eth1 ingress proto all prio $i flower src_mac 00:11:22:33:44:55 action pass > /dev/null 2>&1 &
done ^^^^^^^

Then deleting the Qdisc in Terminal 2 becomes a lot faster:

  real  0m0.712s
  user  0m0.000s
  sys   0m0.152s 

In fact it's so fast that I couldn't even make qdisc->refcnt > 1, so I did yet another test [1], which looks a lot better.

When I didn't specify "prio", sometimes that rhashtable_lookup_insert_fast() call in fl_ht_insert_unique() returns -EEXIST. Is it because that concurrent add-filter requests auto-allocated the same "prio" number, so they collided with each other? Do you think this is related to why it's slow?

Thanks,
Peilin Ye

[1] In a beefier QEMU setup (64 cores, -m 128G), I started 64 tc instances in -batch mode that keeps adding a unique filter (with "prio" and "handle" specified) then deletes it. Again, when they are running I delete the ingress Qdisc, and here's the result:

#1 #2 #3 #4
----------------------------------------------------------

    a. refcnt            64         63         64         64
    b. replayed         169      5,630        887      3,442
    c. time real   0m0.171s   0m0.147s   0m0.186s   0m0.111s
            user   0m0.000s   0m0.009s   0m0.001s   0m0.000s
             sys   0m0.112s   0m0.108s   0m0.115s   0m0.104s

Quoted 5 lines

When I didn't specify "prio", sometimes that rhashtable_lookup_insert_fast() call in fl_ht_insert_unique() returns -EEXIST. Is it because that concurrent add-filter requests auto-allocated the same "prio" number, so they collided with each other? Do you think this is related to why it's slow?

It is slow because when creating a filter without providing priority you are basically measuring the latency of creating a whole flower classifier instance (multiple memory allocation, initialization of all kinds of idrs, hash tables and locks, updating tp list in chain, etc.), not just a single filter, so significantly higher latency is expected.

Hi Vlad and all,

Quoted 14 lines · Vlad Buslov

Quoted 6 lines

Quoted 5 lines

If livelock with concurrent filters insertion is an issue, then it can be remedied by setting a new Qdisc->flags bit "DELETED-REJECT-NEW-FILTERS" and checking for it together with QDISC_CLASS_OPS_DOIT_UNLOCKED in order to force any concurrent filter insertion coming after the flag is set to synchronize on rtnl lock.

Quoted 7 lines

Thanks for the suggestion! I'll try this approach.

Currently QDISC_CLASS_OPS_DOIT_UNLOCKED is checked after taking a refcnt of the "being-deleted" Qdisc. I'll try forcing "late" requests (that arrive later than Qdisc is flagged as being-deleted) sync on RTNL lock without (before) taking the Qdisc refcnt (otherwise I think Task 1 will replay for even longer?).

Quoted 5 lines

Yeah, I see what you mean. Looking at the code __tcf_qdisc_find() already returns -EINVAL when q->refcnt is zero, so maybe returning -EINVAL from that function when "DELETED-REJECT-NEW-FILTERS" flags is set is also fine? Would be much easier to implement as opposed to moving rtnl_lock there.

I implemented [1] this suggestion and tested the livelock issue in QEMU (-m 16G, CONFIG_NR_CPUS=8). I tried deleting the ingress Qdisc (let's call it "request A") while it has a lot of ongoing filter requests, and here's the result:

#1 #2 #3 #4
----------------------------------------------------------

    a. refcnt            89         93        230        571
    b. replayed     167,568    196,450    336,291    878,027
    c. time real   0m2.478s   0m2.746s   0m3.693s   0m9.461s
            user   0m0.000s   0m0.000s   0m0.000s   0m0.000s
             sys   0m0.623s   0m0.681s   0m1.119s   0m2.770s

    a. is the Qdisc refcnt when A calls qdisc_graft() for the first time;
    b. is the number of times A has been replayed;
    c. is the time(1) output for A.

a. and b. are collected from printk() output. This is better than before, but A could still be replayed for hundreds of thousands of times and hang for a few seconds.

Is this okay? If not, is it possible (or should we) to make A really _wait_ on Qdisc refcnt, instead of "busy-replaying"?

Thanks,
Peilin Ye

[1] Diff against v5 patch 6 (printk() calls not included):

include/net/sch_generic.h +6 -0

index 3e9cc43cbc90..de7b0538b309 100644
@@ -94,6 +94,7 @@ struct Qdisc {
  #define TCQ_F_INVISIBLE                0x80 /* invisible by default in dump */
  #define TCQ_F_NOLOCK           0x100 /* qdisc does not require locking */
  #define TCQ_F_OFFLOADED                0x200 /* qdisc is offloaded to HW */
+#define TCQ_F_DESTROYING       0x400 /* destroying, reject filter requests */
         u32                     limit;
         const struct Qdisc_ops  *ops;
         struct qdisc_size_table __rcu *stab;

@@ -185,6 +186,11 @@ static inline bool qdisc_is_empty(const struct Qdisc *qdisc)
         return !READ_ONCE(qdisc->q.qlen);
  }
 
+static inline bool qdisc_is_destroying(const struct Qdisc *qdisc)
+{
+       return qdisc->flags & TCQ_F_DESTROYING;
+}
+
  /* For !TCQ_F_NOLOCK qdisc, qdisc_run_begin/end() must be invoked with
   * the qdisc root lock acquired.
   */

net/sched/cls_api.c +1 -1

index 2621550bfddc..3e7f6f286ac0 100644
@@ -1172,7 +1172,7 @@ static int __tcf_qdisc_find(struct net *net, struct Qdisc **q,
                 *parent = (*q)->handle;
         } else {
                 *q = qdisc_lookup_rcu(dev, TC_H_MAJ(*parent));
-               if (!*q) {
+               if (!*q || qdisc_is_destroying(*q)) {
                         NL_SET_ERR_MSG(extack, "Parent Qdisc doesn't exists");
                         err = -EINVAL;
                         goto errout_rcu;

net/sched/sch_api.c +0 -3

index 286b7c58f5b9..d6e47546c7fe 100644
@@ -1086,12 +1086,18 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
                                 return -ENOENT;
                         }
 
-                       /* Replay if the current ingress (or clsact) Qdisc has ongoing
-                        * RTNL-unlocked filter request(s).  This is the counterpart of that
-                        * qdisc_refcount_inc_nz() call in __tcf_qdisc_find().

net/sched/sch_api.c +2 -0

+                               rtnl_lock();
                                 return -EAGAIN;
+                       }
                 }
 
                 if (dev->flags & IFF_UP)

net/sched/sch_api.c static int qdisc_graft(struct net_device *dev, struct Qdisc *parent, · line 1097

Quoted 13 lines · Peilin Ye

net/sched/sch_api.c +8 -4

-                       /* Replay if the current ingress (or clsact) Qdisc has ongoing
-                        * RTNL-unlocked filter request(s).  This is the counterpart of that
-                        * qdisc_refcount_inc_nz() call in __tcf_qdisc_find().
+                       /* If current ingress (clsact) Qdisc has ongoing filter requests, stop
+                        * accepting any more by marking it as "being destroyed", then tell the
+                        * caller to replay by returning -EAGAIN.
                          */
-                       if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping))
+                       q = dev_queue->qdisc_sleeping;
+                       if (!qdisc_refcount_dec_if_one(q)) {
+                               q->flags |= TCQ_F_DESTROYING;
+                               rtnl_unlock();
+                               schedule();

Was this intended or just a leftover?
rtnl_lock() would reschedule if needed as it's a mutex_lock

Quoted 8 lines · Jamal Hadi Salim

Quoted 7 lines · Peilin Ye

Hi Jakub and all,

Quoted 3 lines · Jakub Kicinski

Quoted 1 line · On Fri, 26 May 2023 16:09:51 -0700 Peilin Ye wrote:

Thanks a lot, I'll get right on it.

Quoted 7 lines

Quoted 7 lines

Quoted 2 lines

Any insights? Is it just a live-lock inherent to the retry scheme or we actually forget to release the lock/refcnt?

I think it's just a thread holding the RTNL mutex for too long (replaying too many times). We could replay for arbitrary times in tc_{modify,get}_qdisc() if the user keeps sending RTNL-unlocked filter requests for the old Qdisc.

After looking very carefully at the code I think I know what the issue might be:

Task 1 graft Qdisc Task 2 new filter

           +                    +
           |                    |
           v                    v
        rtnl_lock()       take  q->refcnt
           +                    +
           |                    |
           v                    v

Spin while q->refcnt!=1 Block on rtnl_lock() indefinitely due to -EAGAIN

This will cause a real deadlock with the proposed patch. I'll try to come up with a better approach. Sorry for not seeing it earlier.

Quoted 41 lines

Quoted 28 lines

I tested the new reproducer Pedro posted, on:

1. All 6 v5 patches, FWIW, which caused a similar hang as Pedro reported

2. First 5 v5 patches, plus patch 6 in v1 (no replaying), did not trigger any issues (in about 30 minutes).

3. All 6 v5 patches, plus this diff:

net/sched/sch_api.c +4 -1

index 286b7c58f5b9..988718ba5abe 100644
@@ -1090,8 +1090,11 @@ static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
                         * RTNL-unlocked filter request(s).  This is the counterpart of that
                         * qdisc_refcount_inc_nz() call in __tcf_qdisc_find().
                         */
-                       if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping))
+                       if (!qdisc_refcount_dec_if_one(dev_queue->qdisc_sleeping)) {
+                               rtnl_unlock();
+                               rtnl_lock();
                                return -EAGAIN;
+                       }
                }
 
                if (dev->flags & IFF_UP)

Quoted 3 lines

Did not trigger any issues (in about 30 mintues) either.

What would you suggest?

I am more worried it is a wackamole situation. We fixed the first reproducer with essentially patches 1-4 but we opened a new one which the second reproducer catches. One thing the current reproducer does is create a lot rtnl contention in the beggining by creating all those devices and then after it is just creating/deleting qdisc and doing update with flower where such contention is reduced. i.e it may just take longer for the mole to pop up.

Quoted 4 lines

Why dont we push the V1 patch in and then worry about getting clever with EAGAIN after? Can you test the V1 version with the repro Pedro posted? It shouldnt have these issues. Also it would be interesting to see how performance of the parallel updates to flower is affected.

This or at least push first 4 patches of this series. They target other older commits and fix straightforward issues with the API.

Quoted 8 lines · Vlad Buslov

Quoted 4 lines · Jamal Hadi Salim

Why dont we push the V1 patch in and then worry about getting clever with EAGAIN after? Can you test the V1 version with the repro Pedro posted? It shouldnt have these issues. Also it would be interesting to see how performance of the parallel updates to flower is affected.

This or at least push first 4 patches of this series. They target other older commits and fix straightforward issues with the API.

Yes, lets get patch 1-4 in first ...

Link to v4: https://lore.kernel.org/r/[email protected]/
Link to v3 (incomplete): https://lore.kernel.org/r/[email protected]/
Link to v2: https://lore.kernel.org/r/[email protected]/
Link to v1: https://lore.kernel.org/r/[email protected]/

Hi all,

These are v5 fixes for ingress and clsact Qdiscs. Please take another look at patch 1, 2 and 6, thanks!