[Patch net 0/2] net_sched: fix a regression in sch_htb

[Patch net 0/2] net_sched: fix a regression in sch_htb

[Cong Wang]

This patchset contains a fix for the regression reported by Alan and a
selftest to cover that case. Please see each patch description for more
details.

---

Cong Wang (2):
  sch_htb: make htb_deactivate() idempotent
  selftests/tc-testing: Add a test case to cover basic HTB+FQ_CODEL case

 net/sched/sch_htb.c                           | 15 ++++----
 .../tc-testing/tc-tests/infra/qdiscs.json     | 35 +++++++++++++++++++
 2 files changed, 41 insertions(+), 9 deletions(-)

-- 
2.34.1

[Patch net 1/2] sch_htb: make htb_deactivate() idempotent

[Cong Wang]

Alan reported a NULL pointer dereference in htb_next_rb_node()
after we made htb_qlen_notify() idempotent.

It turns out in the following case it introduced some regression:

htb_dequeue_tree():
  |-> fq_codel_dequeue()
    |-> qdisc_tree_reduce_backlog()
      |-> htb_qlen_notify()
        |-> htb_deactivate()
  |-> htb_next_rb_node()
  |-> htb_deactivate()

For htb_next_rb_node(), after calling the 1st htb_deactivate(), the
clprio[prio]->ptr could be already set to  NULL, which means
htb_next_rb_node() is vulnerable here.

For htb_deactivate(), although we checked qlen before calling it, in
case of qlen==0 after qdisc_tree_reduce_backlog(), we may call it again
which triggers the warning inside.

To fix the issues here, we need to:

1) Make htb_deactivate() idempotent, that is, simply return if we
   already call it before.
2) Make htb_next_rb_node() safe against ptr==NULL.

Many thanks to Alan for testing and for the reproducer.

Fixes: 5ba8b837b522 ("sch_htb: make htb_qlen_notify() idempotent")
Reported-by: Alan J. Wylie <alan@wylie.me.uk>
Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
---
 net/sched/sch_htb.c | 15 ++++++---------
 1 file changed, 6 insertions(+), 9 deletions(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 4b9a639b642e..14bf71f57057 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -348,7 +348,8 @@ static void htb_add_to_wait_tree(struct htb_sched *q,
  */
 static inline void htb_next_rb_node(struct rb_node **n)
 {
-	*n = rb_next(*n);
+	if (*n)
+		*n = rb_next(*n);
 }
 
 /**
@@ -609,8 +610,8 @@ static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
  */
 static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
 {
-	WARN_ON(!cl->prio_activity);
-
+	if (!cl->prio_activity)
+		return;
 	htb_deactivate_prios(q, cl);
 	cl->prio_activity = 0;
 }
@@ -1485,8 +1486,6 @@ static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
 {
 	struct htb_class *cl = (struct htb_class *)arg;
 
-	if (!cl->prio_activity)
-		return;
 	htb_deactivate(qdisc_priv(sch), cl);
 }
 
@@ -1740,8 +1739,7 @@ static int htb_delete(struct Qdisc *sch, unsigned long arg,
 	if (cl->parent)
 		cl->parent->children--;
 
-	if (cl->prio_activity)
-		htb_deactivate(q, cl);
+	htb_deactivate(q, cl);
 
 	if (cl->cmode != HTB_CAN_SEND)
 		htb_safe_rb_erase(&cl->pq_node,
@@ -1949,8 +1947,7 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
 			/* turn parent into inner node */
 			qdisc_purge_queue(parent->leaf.q);
 			parent_qdisc = parent->leaf.q;
-			if (parent->prio_activity)
-				htb_deactivate(q, parent);
+			htb_deactivate(q, parent);
 
 			/* remove from evt list because of level change */
 			if (parent->cmode != HTB_CAN_SEND) {
-- 
2.34.1

[Patch net 2/2] selftests/tc-testing: Add a test case to cover basic HTB+FQ_CODEL case

[Cong Wang]

Integrate the reproducer from Alan into TC selftests and use scapy to
generate TCP traffic instead of relying on ping command.

Cc: Alan J. Wylie <alan@wylie.me.uk>
Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
---
 .../tc-testing/tc-tests/infra/qdiscs.json     | 35 +++++++++++++++++++
 1 file changed, 35 insertions(+)

diff --git a/tools/testing/selftests/tc-testing/tc-tests/infra/qdiscs.json b/tools/testing/selftests/tc-testing/tc-tests/infra/qdiscs.json
index e26bbc169783..5a8c21735b3a 100644
--- a/tools/testing/selftests/tc-testing/tc-tests/infra/qdiscs.json
+++ b/tools/testing/selftests/tc-testing/tc-tests/infra/qdiscs.json
@@ -352,5 +352,40 @@
             "$TC qdisc del dev $DUMMY handle 1:0 root",
             "$IP addr del 10.10.10.10/24 dev $DUMMY || true"
         ]
+    },
+    {
+        "id": "62c4",
+        "name": "Test HTB with FQ_CODEL - basic functionality",
+        "category": [
+            "qdisc",
+            "htb",
+            "fq_codel"
+        ],
+        "plugins": {
+            "requires": [
+                "nsPlugin",
+                "scapyPlugin"
+            ]
+        },
+        "setup": [
+            "$TC qdisc add dev $DEV1 root handle 1: htb default 11",
+            "$TC class add dev $DEV1 parent 1: classid 1:1 htb rate 10kbit",
+            "$TC class add dev $DEV1 parent 1:1 classid 1:11 htb rate 10kbit prio 0 quantum 1486",
+            "$TC qdisc add dev $DEV1 parent 1:11 fq_codel quantum 300 noecn",
+            "sleep 0.5"
+        ],
+        "scapy": {
+            "iface": "$DEV0",
+            "count": 5,
+            "packet": "Ether()/IP(dst='10.10.10.1', src='10.10.10.10')/TCP(sport=12345, dport=80)"
+        },
+        "cmdUnderTest": "$TC -s qdisc show dev $DEV1",
+        "expExitCode": "0",
+        "verifyCmd": "$TC -s qdisc show dev $DEV1 | grep -A 5 'qdisc fq_codel'",
+        "matchPattern": "Sent [0-9]+ bytes [0-9]+ pkt",
+        "matchCount": "1",
+        "teardown": [
+            "$TC qdisc del dev $DEV1 handle 1: root"
+        ]
     }
 ]
-- 
2.34.1

Re: [Patch net 1/2] sch_htb: make htb_deactivate() idempotent

[Victor Nogueira]

On 4/28/25 20:29, Cong Wang wrote:
> Alan reported a NULL pointer dereference in htb_next_rb_node()
> after we made htb_qlen_notify() idempotent.
> 
> It turns out in the following case it introduced some regression:
> 
> htb_dequeue_tree():
>    |-> fq_codel_dequeue()
>      |-> qdisc_tree_reduce_backlog()
>        |-> htb_qlen_notify()
>          |-> htb_deactivate()
>    |-> htb_next_rb_node()
>    |-> htb_deactivate()
> 
> For htb_next_rb_node(), after calling the 1st htb_deactivate(), the
> clprio[prio]->ptr could be already set to  NULL, which means
> htb_next_rb_node() is vulnerable here.

If I'm not missing something, the issue seems to be that
fq_codel_dequeue or codel_qdisc_dequeue may call qdisc_tree_reduce_backlog
with sch->q.qlen == 0 after commit 342debc12183. This will cause
htb_qlen_notify to be called which will deactivate before we
call htb_next_rb_node further down in htb_dequeue_tree (as you
said above).

If that's so, couldn't we instead of doing:

> @@ -348,7 +348,8 @@ static void htb_add_to_wait_tree(struct htb_sched *q,
>    */
>   static inline void htb_next_rb_node(struct rb_node **n)
>   {
> -	*n = rb_next(*n);
> +	if (*n)
> +		*n = rb_next(*n);
>   }

do something like:

@@ -921,7 +921,9 @@ static struct sk_buff *htb_dequeue_tree(struct 
htb_sched *q, const int prio,
                 cl->leaf.deficit[level] -= qdisc_pkt_len(skb);
                 if (cl->leaf.deficit[level] < 0) {
                         cl->leaf.deficit[level] += cl->quantum;
-                       htb_next_rb_node(level ? 
&cl->parent->inner.clprio[prio].ptr :
+                       /* Account for (fq_)codel child deactivating 
after dequeue */
+                       if (likely(cl->prio_activity))
+                               htb_next_rb_node(level ? 
&cl->parent->inner.clprio[prio].ptr :
  
&q->hlevel[0].hprio[prio].ptr);
                 }
                 /* this used to be after charge_class but this constelation

That way it's clear that the issue is a corner case where the
child qdisc deactivates the parent. Otherwise it seems like
we need to check for (*n) being NULL for every call to
htb_next_rb_node.

cheers,
Victor

Re: [Patch net 1/2] sch_htb: make htb_deactivate() idempotent

[Paolo Abeni]

On 4/30/25 5:19 PM, Victor Nogueira wrote:
> If that's so, couldn't we instead of doing:
> 
>> @@ -348,7 +348,8 @@ static void htb_add_to_wait_tree(struct htb_sched *q,
>>    */
>>   static inline void htb_next_rb_node(struct rb_node **n)
>>   {
>> -	*n = rb_next(*n);
>> +	if (*n)
>> +		*n = rb_next(*n);
>>   }
> 
> do something like:
> 
> @@ -921,7 +921,9 @@ static struct sk_buff *htb_dequeue_tree(struct 
> htb_sched *q, const int prio,
>                  cl->leaf.deficit[level] -= qdisc_pkt_len(skb);
>                  if (cl->leaf.deficit[level] < 0) {
>                          cl->leaf.deficit[level] += cl->quantum;
> -                       htb_next_rb_node(level ? 
> &cl->parent->inner.clprio[prio].ptr :
> +                       /* Account for (fq_)codel child deactivating 
> after dequeue */
> +                       if (likely(cl->prio_activity))
> +                               htb_next_rb_node(level ? 
> &cl->parent->inner.clprio[prio].ptr :
>   
> &q->hlevel[0].hprio[prio].ptr);
>                  }
>                  /* this used to be after charge_class but this constelation
> 
> That way it's clear that the issue is a corner case where the
> child qdisc deactivates the parent. Otherwise it seems like
> we need to check for (*n) being NULL for every call to
> htb_next_rb_node.

@Victor, I think that the Cong's suggested patch is simpler to very/tie
to code change to the actually addressed issue. I started at your
suggest code for a bit, and out of sheer htb ignorance I'm less
confident about it fixing the thing.

Do you have strong feeling vs Cong's suggested approach?

Thanks,

Paolo

Re: [Patch net 1/2] sch_htb: make htb_deactivate() idempotent

[Victor Nogueira]

On 5/2/25 06:59, Paolo Abeni wrote:
> On 4/30/25 5:19 PM, Victor Nogueira wrote:
>> If that's so, couldn't we instead of doing:
>>
>>> @@ -348,7 +348,8 @@ static void htb_add_to_wait_tree(struct htb_sched *q,
>>>     */
>>>    static inline void htb_next_rb_node(struct rb_node **n)
>>>    {
>>> -	*n = rb_next(*n);
>>> +	if (*n)
>>> +		*n = rb_next(*n);
>>>    }
>>
>> do something like:
>>
>> @@ -921,7 +921,9 @@ static struct sk_buff *htb_dequeue_tree(struct
>> htb_sched *q, const int prio,
>>                   cl->leaf.deficit[level] -= qdisc_pkt_len(skb);
>>                   if (cl->leaf.deficit[level] < 0) {
>>                           cl->leaf.deficit[level] += cl->quantum;
>> -                       htb_next_rb_node(level ?
>> &cl->parent->inner.clprio[prio].ptr :
>> +                       /* Account for (fq_)codel child deactivating
>> after dequeue */
>> +                       if (likely(cl->prio_activity))
>> +                               htb_next_rb_node(level ?
>> &cl->parent->inner.clprio[prio].ptr :
>>    
>> &q->hlevel[0].hprio[prio].ptr);
>>                   }
>>                   /* this used to be after charge_class but this constelation
>>
>> That way it's clear that the issue is a corner case where the
>> child qdisc deactivates the parent. Otherwise it seems like
>> we need to check for (*n) being NULL for every call to
>> htb_next_rb_node.
> 
> @Victor, I think that the Cong's suggested patch is simpler to very/tie
> to code change to the actually addressed issue. I started at your
> suggest code for a bit, and out of sheer htb ignorance I'm less
> confident about it fixing the thing.
> 
> Do you have strong feeling vs Cong's suggested approach?

I have no strong feelings, I'm ok with merging the patch
as is.

cheers,
Victor

Re: [Patch net 1/2] sch_htb: make htb_deactivate() idempotent

[Cong Wang]

On Wed, Apr 30, 2025 at 12:19:03PM -0300, Victor Nogueira wrote:
> On 4/28/25 20:29, Cong Wang wrote:
> > Alan reported a NULL pointer dereference in htb_next_rb_node()
> > after we made htb_qlen_notify() idempotent.
> > 
> > It turns out in the following case it introduced some regression:
> > 
> > htb_dequeue_tree():
> >    |-> fq_codel_dequeue()
> >      |-> qdisc_tree_reduce_backlog()
> >        |-> htb_qlen_notify()
> >          |-> htb_deactivate()
> >    |-> htb_next_rb_node()
> >    |-> htb_deactivate()
> > 
> > For htb_next_rb_node(), after calling the 1st htb_deactivate(), the
> > clprio[prio]->ptr could be already set to  NULL, which means
> > htb_next_rb_node() is vulnerable here.
> 
> If I'm not missing something, the issue seems to be that
> fq_codel_dequeue or codel_qdisc_dequeue may call qdisc_tree_reduce_backlog
> with sch->q.qlen == 0 after commit 342debc12183. This will cause
> htb_qlen_notify to be called which will deactivate before we
> call htb_next_rb_node further down in htb_dequeue_tree (as you
> said above).
> 
> If that's so, couldn't we instead of doing:
> 
> > @@ -348,7 +348,8 @@ static void htb_add_to_wait_tree(struct htb_sched *q,
> >    */
> >   static inline void htb_next_rb_node(struct rb_node **n)
> >   {
> > -	*n = rb_next(*n);
> > +	if (*n)
> > +		*n = rb_next(*n);
> >   }
> 
> do something like:
> 
> @@ -921,7 +921,9 @@ static struct sk_buff *htb_dequeue_tree(struct htb_sched
> *q, const int prio,
>                 cl->leaf.deficit[level] -= qdisc_pkt_len(skb);
>                 if (cl->leaf.deficit[level] < 0) {
>                         cl->leaf.deficit[level] += cl->quantum;
> -                       htb_next_rb_node(level ?
> &cl->parent->inner.clprio[prio].ptr :
> +                       /* Account for (fq_)codel child deactivating after
> dequeue */
> +                       if (likely(cl->prio_activity))
> +                               htb_next_rb_node(level ?

It reads odd to me to check cl->prio_activity before htb_next_rb_node(),
and I don't see any existing pattern of using this.

My patch pretty much follows all the existing patterns of checking
either cl->prio_activity or cl->leaf.q->q.qlen. So, although it looks
bigger from diffstat, it is safer from this point of view.

Thanks!

Re: [Patch net 0/2] net_sched: fix a regression in sch_htb

[patchwork-bot+netdevbpf]

Hello:

This series was applied to netdev/net.git (main)
by Jakub Kicinski <kuba@kernel.org>:

On Mon, 28 Apr 2025 16:29:53 -0700 you wrote:
> This patchset contains a fix for the regression reported by Alan and a
> selftest to cover that case. Please see each patch description for more
> details.
> 
> ---
> 
> Cong Wang (2):
>   sch_htb: make htb_deactivate() idempotent
>   selftests/tc-testing: Add a test case to cover basic HTB+FQ_CODEL case
> 
> [...]

Here is the summary with links:
  - [net,1/2] sch_htb: make htb_deactivate() idempotent
    https://git.kernel.org/netdev/net/c/376947861013
  - [net,2/2] selftests/tc-testing: Add a test case to cover basic HTB+FQ_CODEL case
    https://git.kernel.org/netdev/net/c/63890286f557

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html