Skip to contentSkip to conversation

net/sched: Return NULL when htb_lookup_leaf encounters an empty rbtree

PATCH Applied William Liu 2 participants 3 messages Jul 17, 2025

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

PATCH v2 1/2 net/sched: Return NULL when htb_lookup_leaf encounters an empty rbtree

htb_lookup_leaf has a BUG_ON that can trigger with the following:

tc qdisc del dev lo root
tc qdisc add dev lo root handle 1: htb default 1 tc class add dev lo parent 1: classid 1:1 htb rate 64bit tc qdisc add dev lo parent 1:1 handle 2: netem tc qdisc add dev lo parent 2:1 handle 3: blackhole ping -I lo -c1 -W0.001 127.0.0.1

The root cause is the following:

1. htb_dequeue calls htb_dequeue_tree which calls the dequeue handler on the selected leaf qdisc
2. netem_dequeue calls enqueue on the child qdisc
3. blackhole_enqueue drops the packet and returns a value that is not just NET_XMIT_SUCCESS
4. Because of this, netem_dequeue calls qdisc_tree_reduce_backlog, and since qlen is now 0, it calls htb_qlen_notify -> htb_deactivate -> htb_deactiviate_prios -> htb_remove_class_from_row -> htb_safe_rb_erase
5. As this is the only class in the selected hprio rbtree, __rb_change_child in __rb_erase_augmented sets the rb_root pointer to NULL
6. Because blackhole_dequeue returns NULL, netem_dequeue returns NULL, which causes htb_dequeue_tree to call htb_lookup_leaf with the same hprio rbtree, and fail the BUG_ON

The function graph for this scenario is shown here:

 0)               |  htb_enqueue() {
 0) + 13.635 us   |    netem_enqueue();
 0)   4.719 us    |    htb_activate_prios();
 0) # 2249.199 us |  }
 0)               |  htb_dequeue() {
 0)   2.355 us    |    htb_lookup_leaf();
 0)               |    netem_dequeue() {
 0) + 11.061 us   |      blackhole_enqueue();
 0)               |      qdisc_tree_reduce_backlog() {
 0)               |        qdisc_lookup_rcu() {
 0)   1.873 us    |          qdisc_match_from_root();
 0)   6.292 us    |        }
 0)   1.894 us    |        htb_search();
 0)               |        htb_qlen_notify() {
 0)   2.655 us    |          htb_deactivate_prios();
 0)   6.933 us    |        }
 0) + 25.227 us   |      }
 0)   1.983 us    |      blackhole_dequeue();
 0) + 86.553 us   |    }
 0) # 2932.761 us |    qdisc_warn_nonwc();
 0)               |    htb_lookup_leaf() {
 0)               |      BUG_ON();

------------------------------------------

The full original bug report can be seen here [1].

We can fix this just by returning NULL instead of the BUG_ON, as htb_dequeue_tree returns NULL when htb_lookup_leaf returns NULL.

[1] https://lore.kernel.org/netdev/pF5XOOIim0IuEfhI-SOxTgRvNoDwuux7UHKnE_Y5-zVd4wmGvNk2ceHjKb8ORnzw0cGwfmVu42g9dL7XyJLf1NEzaztboTWcm0Ogxuojoeo=@willsroot.io/

Fixes 512bb43eb542 ("pkt_sched: sch_htb: Optimize WARN_ONs in htb_dequeue_tree() etc.")
---
 net/sched/sch_htb.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
net/sched/sch_htb.c +3 -1
index 14bf71f57057..c968ea763774 100644
@@ -821,7 +821,9 @@ static struct htb_class *htb_lookup_leaf(struct htb_prio *hprio, const int prio)
 		u32 *pid;
 	} stk[TC_HTB_MAXDEPTH], *sp = stk;
 
-	BUG_ON(!hprio->row.rb_node);
+	if (unlikely(!hprio->row.rb_node))
+		return NULL;
+
 	sp->root = hprio->row.rb_node;
 	sp->pptr = &hprio->ptr;
 	sp->pid = &hprio->last_ptr_id;
Signature · 1 line
2.43.0
#1 lore raw

PATCH v2 2/2 selftests/tc-testing: Test htb_dequeue_tree with deactivation and row emptying

Ensure that any deactivation and row emptying that occurs during htb_dequeue_tree does not cause a kernel panic. This scenario originally triggered a kernel BUG_ON, and we are checking for a graceful fail now.

---
v1 -> v2:
- Moved test case to earlier in the file

---
 .../tc-testing/tc-tests/infra/qdiscs.json     | 26 +++++++++++++++++++
 1 file changed, 26 insertions(+)
tools/testing/selftests/tc-testing/tc-tests/infra/qdiscs.json +26 -0
index 5c6851e8d311..c54adc9b3604 100644
@@ -127,6 +127,32 @@
             "$IP addr del 10.10.10.10/24 dev $DUMMY"
         ]
     },
+    {
+        "id": "5456",
+        "name": "Test htb_dequeue_tree with deactivation and row emptying",
+        "category": [
+            "qdisc",
+            "htb"
+        ],
+        "plugins": {
+            "requires": "nsPlugin"
+        },
+        "setup": [
+            "$IP link set dev $DUMMY up || true",
+            "$IP addr add 10.10.11.10/24 dev $DUMMY || true",
+            "$TC qdisc add dev $DUMMY root handle 1: htb default 1",
+            "$TC class add dev $DUMMY parent 1: classid 1:1 htb rate 64bit ",
+            "$TC qdisc add dev $DUMMY parent 1:1 handle 2: netem",
+            "$TC qdisc add dev $DUMMY parent 2:1 handle 3: blackhole"
+        ],
+        "cmdUnderTest": "ping -c1 -W0.01 -I $DUMMY 10.10.11.11",
+        "expExitCode": "1",
+        "verifyCmd": "$TC -j qdisc show dev $DUMMY",
+        "matchJSON": [],
+        "teardown": [
+            "$TC qdisc del dev $DUMMY root"
+        ]
+    },
     {
         "id": "c024",
         "name": "Test TBF with SKBPRIO - catch qlen corner cases",
Signature · 1 line
2.43.0
#2 lore raw
In reply to William Liu
This series was applied to netdev/net.git (main) by Jakub Kicinski <[email protected]>:

Hello:

This series was applied to netdev/net.git (main)
by Jakub Kicinski <[email protected]>:

Quoted 10 lines · On Thu, 17 Jul 2025 02:28:38 +0000 you wrote:

htb_lookup_leaf has a BUG_ON that can trigger with the following:

tc qdisc del dev lo root
tc qdisc add dev lo root handle 1: htb default 1 tc class add dev lo parent 1: classid 1:1 htb rate 64bit tc qdisc add dev lo parent 1:1 handle 2: netem tc qdisc add dev lo parent 2:1 handle 3: blackhole ping -I lo -c1 -W0.001 127.0.0.1

[...]

Here is the summary with links:
- [net,v2,1/2] net/sched: Return NULL when htb_lookup_leaf encounters an empty rbtree

    https://git.kernel.org/netdev/net/c/0e1d5d9b5c59
  - [net,v2,2/2] selftests/tc-testing: Test htb_dequeue_tree with deactivation and row emptying
    https://git.kernel.org/netdev/net/c/88b06e4fb4bf

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html