[PATCH net] net/sched: Avoid quadratic handle scan in qdisc_alloc_handle

[PATCH net] net/sched: Avoid quadratic handle scan in qdisc_alloc_handle

[Victor Nogueira]

qdisc_alloc_handle scans for a free auto-handle by probing the
per-device qdisc hash one handle at a time. With the 16-bucket hash
populated by tens of thousands of qdiscs, the failing scan is O(N^2)
under rtnl_lock. Each failing add holds RTNL for 0.6-0.9 s on a
production kernel and about 1.7 s with KASAN and lock debugging, and it
can be repeated back to back, stalling network administration in every
namespace.

First try the handle after the rotating cursor with one qdisc_lookup,
as the first iteration of the current loop does; that handle is
normally free. Only when it is taken, build a bitmap of the occupied
auto-handle majors in one pass over the hash and pick the first free
major from the cursor. The scan is cyclic over all 0x7FFF majors
starting from the same autohandle + 1 position as the current loop, so
it returns the same handle for the same device state and fails only
when all 0x7FFF majors are taken.

The root qdisc is seeded separately because qdisc_hash_add skips
parent == TC_H_ROOT.

When the next handle is free, only the single qdisc_lookup of the
current loop's first iteration runs; when it is taken, one O(N) walk
follows.

Measured as tc wall time on a defconfig kernel in a 2-vCPU guest, with
an HTB root holding 32768 classes and all 32767 auto-handles in use (a
no-op tc command takes 5-6.5 ms):

                                    unpatched     patched
  failing add, space exhausted      613-749 ms    8-10 ms
  add after a mid-range delete      572-573 ms    9 ms

The failure path returns -ENOMEM (bitmap allocation) or -ENOSPC (space
exhausted) through a handle out-parameter instead of the overloaded 0
return. Since either error is now possible, the extack message changes
from "Maximum number of qdisc handles was exceeded" to "Failed to
allocate a qdisc handle".

This is a less intrusive fix meant for backporting; a cleaner approach that
uses a per-device IDA over all qdisc handles is planned for net-next.

Conditions to recreate the bug:
  - unshare -Urn (Level 2, namespace-local CAP_NET_ADMIN)
  - classful qdisc (e.g. HTB) with many classes
  - attach ~32767 auto-handle child qdiscs to fill the handle space
  - the final tc qdisc add with no explicit handle scans the full space

Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")
Reported-by: Vega <vega@nebusec.ai>
Co-developed-by: Jamal Hadi Salim <jhs@mojatatu.com>
Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>
Signed-off-by: Victor Nogueira <victor@mojatatu.com>
---
 net/sched/sch_api.c | 86 ++++++++++++++++++++++++++++++++++++---------
 1 file changed, 70 insertions(+), 16 deletions(-)

diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
index 463ededcdcfe..f36c41224bcc 100644
--- a/net/sched/sch_api.c
+++ b/net/sched/sch_api.c
@@ -21,6 +21,7 @@
 #include <linux/proc_fs.h>
 #include <linux/seq_file.h>
 #include <linux/kmod.h>
+#include <linux/bitmap.h>
 #include <linux/list.h>
 #include <linux/hrtimer.h>
 #include <linux/slab.h>
@@ -770,22 +771,75 @@ void qdisc_class_hash_remove(struct Qdisc_class_hash *clhash,
 }
 EXPORT_SYMBOL(qdisc_class_hash_remove);
 
-/* Allocate an unique handle from space managed by kernel
- * Possible range is [8000-FFFF]:0000 (0x8000 values)
+#define QDISC_AUTO_HANDLE_BASE	0x8000	/* first auto-handle major */
+#define QDISC_AUTO_HANDLE_END	0xFFFE	/* last auto-handle major */
+#define QDISC_AUTO_HANDLE_COUNT	(QDISC_AUTO_HANDLE_END - \
+				 QDISC_AUTO_HANDLE_BASE + 1)
+
+/* Allocate a unique handle from space managed by kernel
+ * Possible range is [8000-FFFE]:0000 (0x7FFF values); 0xFFFF is the
+ * TC_H_ROOT/ingress major.
  */
-static u32 qdisc_alloc_handle(struct net_device *dev)
+static int qdisc_alloc_handle(struct net_device *dev, u32 *handlep)
 {
-	int i = 0x8000;
 	static u32 autohandle = TC_H_MAKE(0x80000000U, 0);
+	unsigned long start, bit;
+	unsigned long *bitmap;
+	struct Qdisc *q;
+	u32 handle, maj;
+	int b;
+
+	start = ((autohandle >> 16) - QDISC_AUTO_HANDLE_BASE + 1) %
+		QDISC_AUTO_HANDLE_COUNT;
+
+	/* The cursor moves past every handle it hands out, so the next
+	 * handle is normally free: try it with one hashed lookup before
+	 * walking the whole hash.
+	 */
+	handle = (start + QDISC_AUTO_HANDLE_BASE) << 16;
+	if (!qdisc_lookup(dev, handle)) {
+		autohandle = handle;
+		*handlep = handle;
+		return 0;
+	}
 
-	do {
-		autohandle += TC_H_MAKE(0x10000U, 0);
-		if (autohandle == TC_H_MAKE(TC_H_ROOT, 0))
-			autohandle = TC_H_MAKE(0x80000000U, 0);
-		if (!qdisc_lookup(dev, autohandle))
-			return autohandle;
-		cond_resched();
-	} while	(--i > 0);
+	bitmap = bitmap_zalloc(QDISC_AUTO_HANDLE_COUNT, GFP_KERNEL);
+	if (!bitmap)
+		return -ENOMEM;
+
+	/* Mark the occupied auto-handle majors: the hash holds all
+	 * qdiscs except root and ingress ones, and the root can carry
+	 * an auto-range handle.
+	 */
+	q = rtnl_dereference(dev->qdisc);
+	maj = TC_H_MAJ(q->handle) >> 16;
+	if (!(q->flags & TCQ_F_BUILTIN) && !TC_H_MIN(q->handle) &&
+	    maj >= QDISC_AUTO_HANDLE_BASE && maj <= QDISC_AUTO_HANDLE_END)
+		set_bit(maj - QDISC_AUTO_HANDLE_BASE, bitmap);
+
+	hash_for_each(dev->qdisc_hash, b, q, hash) {
+		maj = TC_H_MAJ(q->handle) >> 16;
+		if (maj >= QDISC_AUTO_HANDLE_BASE &&
+		    maj <= QDISC_AUTO_HANDLE_END && !TC_H_MIN(q->handle))
+			set_bit(maj - QDISC_AUTO_HANDLE_BASE, bitmap);
+	}
+
+	bit = find_next_zero_bit(bitmap, QDISC_AUTO_HANDLE_COUNT, start);
+	if (bit >= QDISC_AUTO_HANDLE_COUNT) {
+		bit = find_first_zero_bit(bitmap, start);
+		if (bit >= start)
+			bit = QDISC_AUTO_HANDLE_COUNT;
+	}
+
+	if (bit >= QDISC_AUTO_HANDLE_COUNT) {
+		bitmap_free(bitmap);
+		return -ENOSPC;
+	}
+
+	handle = (bit + QDISC_AUTO_HANDLE_BASE) << 16;
+	autohandle = handle;
+	bitmap_free(bitmap);
+	*handlep = handle;
 
 	return 0;
 }
@@ -1308,10 +1362,10 @@ static struct Qdisc *qdisc_create(struct net_device *dev,
 		handle = TC_H_MAKE(TC_H_INGRESS, 0);
 	} else {
 		if (handle == 0) {
-			handle = qdisc_alloc_handle(dev);
-			if (handle == 0) {
-				NL_SET_ERR_MSG(extack, "Maximum number of qdisc handles was exceeded");
-				err = -ENOSPC;
+			err = qdisc_alloc_handle(dev, &handle);
+			if (err) {
+				NL_SET_ERR_MSG(extack,
+					       "Failed to allocate a qdisc handle");
 				goto err_out3;
 			}
 		}
-- 
2.55.0

Re: [PATCH net] net/sched: Avoid quadratic handle scan in qdisc_alloc_handle

[Simon Horman]

On Fri, Sep 11, 2026 at 10:31:46AM -0300, Victor Nogueira wrote:
> qdisc_alloc_handle scans for a free auto-handle by probing the
> per-device qdisc hash one handle at a time. With the 16-bucket hash
> populated by tens of thousands of qdiscs, the failing scan is O(N^2)
> under rtnl_lock. Each failing add holds RTNL for 0.6-0.9 s on a
> production kernel and about 1.7 s with KASAN and lock debugging, and it
> can be repeated back to back, stalling network administration in every
> namespace.
> 
> First try the handle after the rotating cursor with one qdisc_lookup,
> as the first iteration of the current loop does; that handle is
> normally free. Only when it is taken, build a bitmap of the occupied
> auto-handle majors in one pass over the hash and pick the first free
> major from the cursor. The scan is cyclic over all 0x7FFF majors
> starting from the same autohandle + 1 position as the current loop, so
> it returns the same handle for the same device state and fails only
> when all 0x7FFF majors are taken.
> 
> The root qdisc is seeded separately because qdisc_hash_add skips
> parent == TC_H_ROOT.
> 
> When the next handle is free, only the single qdisc_lookup of the
> current loop's first iteration runs; when it is taken, one O(N) walk
> follows.
> 
> Measured as tc wall time on a defconfig kernel in a 2-vCPU guest, with
> an HTB root holding 32768 classes and all 32767 auto-handles in use (a
> no-op tc command takes 5-6.5 ms):
> 
>                                     unpatched     patched
>   failing add, space exhausted      613-749 ms    8-10 ms
>   add after a mid-range delete      572-573 ms    9 ms
> 
> The failure path returns -ENOMEM (bitmap allocation) or -ENOSPC (space
> exhausted) through a handle out-parameter instead of the overloaded 0
> return. Since either error is now possible, the extack message changes
> from "Maximum number of qdisc handles was exceeded" to "Failed to
> allocate a qdisc handle".
> 
> This is a less intrusive fix meant for backporting; a cleaner approach that
> uses a per-device IDA over all qdisc handles is planned for net-next.
> 
> Conditions to recreate the bug:
>   - unshare -Urn (Level 2, namespace-local CAP_NET_ADMIN)
>   - classful qdisc (e.g. HTB) with many classes
>   - attach ~32767 auto-handle child qdiscs to fill the handle space
>   - the final tc qdisc add with no explicit handle scans the full space
> 
> Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")
> Reported-by: Vega <vega@nebusec.ai>
> Co-developed-by: Jamal Hadi Salim <jhs@mojatatu.com>
> Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>
> Signed-off-by: Victor Nogueira <victor@mojatatu.com>

Reviewed-by: Simon Horman <horms@kernel.org>

Re: [PATCH net] net/sched: Avoid quadratic handle scan in qdisc_alloc_handle

[Jakub Kicinski]

On Fri, 11 Sep 2026 10:31:46 -0300 Victor Nogueira wrote:
> This is a less intrusive fix meant for backporting; a cleaner approach that
> uses a per-device IDA over all qdisc handles is planned for net-next.

I don't think this is net-worthy in the first place.
We have a ton of code under rtnl_lock.
We cannot provide any protection from malicious netns admin from
overloading the machine.
Nothing against the patch itself, but if you plan to do something
else in net-next let's just go with that from the start..
-- 
pw-bot: cr

Re: [PATCH net] net/sched: Avoid quadratic handle scan in qdisc_alloc_handle

[Jamal Hadi Salim]

[-- Attachment #1: Type: text/plain, Size: 1193 bytes --]

On Mon, Sep 14, 2026 at 10:11 PM Jakub Kicinski <kuba@kernel.org> wrote:
>
> On Fri, 11 Sep 2026 10:31:46 -0300 Victor Nogueira wrote:
> > This is a less intrusive fix meant for backporting; a cleaner approach that
> > uses a per-device IDA over all qdisc handles is planned for net-next.
>
> I don't think this is net-worthy in the first place.
> We have a ton of code under rtnl_lock.
> We cannot provide any protection from malicious netns admin from
> overloading the machine.

That is the one million dollar question.  We labelled this as net for
this exact reason. i.e malicious container could overload the whole
machine.
But it borders on "hardening" (improves performance), so net-next as a
target sounds reasonable. It was a coin toss.

Since we have a few similar "grey" issues in our pending queue - so
where's the line for net/net-next?

> Nothing against the patch itself, but if you plan to do something
> else in net-next let's just go with that from the start..

We could resend the same patch for net-next, the alternative "proper
fix" is more intrusive. See attached.
Another option: Is this worth fixing?

cheers,
jamal

> --
> pw-bot: cr

[-- Attachment #2: 0001-net-sched-allocate-qdisc-handles-from-a-per-device-I.patch --]
[-- Type: text/x-patch, Size: 6761 bytes --]

 include/linux/netdevice.h |   4 ++
 include/net/pkt_sched.h   |   1 +
 net/core/dev.c            |   6 +++
 net/sched/sch_api.c       | 102 +++++++++++++++++++++++++++++---------
 net/sched/sch_generic.c   |   1 +
 5 files changed, 90 insertions(+), 24 deletions(-)

diff --git a/include/linux/netdevice.h b/include/linux/netdevice.h
index 87cafc932e9e..f7fbd36f9ef8 100644
--- a/include/linux/netdevice.h
+++ b/include/linux/netdevice.h
@@ -2010,6 +2010,9 @@ enum netdev_reg_state {
  *	@tcx_egress:		BPF & clsact qdisc specific data for egress processing
  *	@nf_hooks_egress:	netfilter hooks executed for egress packets
  *	@qdisc_hash:		qdisc hash table
+ *	@qdisc_handle_ida:	IDA of the qdisc handle majors in the automatic
+ *				range that are in use; NULL until the first one
+ *				is handed out
  *	@watchdog_timeo:	Represents the timeout that is used by
  *				the watchdog (see dev_watchdog())
  *	@watchdog_lock:		protect watchdog_ref_held
@@ -2426,6 +2429,7 @@ struct net_device {

 #ifdef CONFIG_NET_SCHED
 	DECLARE_HASHTABLE	(qdisc_hash, 4);
+	struct ida		*qdisc_handle_ida;
 #endif
 	/* These may be needed for future network-power-down code. */
 	struct timer_list	watchdog_timer;
diff --git a/include/net/pkt_sched.h b/include/net/pkt_sched.h
index 90d3e7943b19..2f32af831835 100644
--- a/include/net/pkt_sched.h
+++ b/include/net/pkt_sched.h
@@ -102,6 +102,7 @@ int qdisc_set_default(const char *id);

 void qdisc_hash_add(struct Qdisc *q, bool invisible);
 void qdisc_hash_del(struct Qdisc *q);
+void qdisc_free_handle(struct net_device *dev, u32 handle);
 struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle);
 struct Qdisc *qdisc_lookup_rcu(struct net_device *dev, u32 handle);
 struct qdisc_rate_table *qdisc_get_rtab(struct tc_ratespec *r,
diff --git a/net/core/dev.c b/net/core/dev.c
index ecfbd72d5d1a..cb03f7c197f7 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -12277,6 +12277,12 @@ void free_netdev(struct net_device *dev)
 	netif_free_rx_queues(dev);

 	kfree(rcu_dereference_protected(dev->ingress_queue, 1));
+#ifdef CONFIG_NET_SCHED
+	if (dev->qdisc_handle_ida) {
+		ida_destroy(dev->qdisc_handle_ida);
+		kfree(dev->qdisc_handle_ida);
+	}
+#endif

 	__hw_addr_flush(&dev->rx_mode_addr_cache);

diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
index 463ededcdcfe..81933dccccba 100644
--- a/net/sched/sch_api.c
+++ b/net/sched/sch_api.c
@@ -770,26 +770,78 @@ void qdisc_class_hash_remove(struct Qdisc_class_hash *clhash,
 }
 EXPORT_SYMBOL(qdisc_class_hash_remove);

-/* Allocate an unique handle from space managed by kernel
- * Possible range is [8000-FFFF]:0000 (0x8000 values)
+/* A qdisc handle is always major:0, so the major alone identifies it. Every
+ * major in use on a device is tracked in dev->qdisc_handle_ida, whether
+ * userspace named it or the kernel picked it, which is what lets an
+ * automatic handle never collide with an explicit one.
+ *
+ * Userspace may name any major in [1, FFFF]. The kernel picks from
+ * [8000, FFFE], the same set the old rotating cursor could reach: FFFF is
+ * left out because it is the major of TC_H_ROOT and of the ingress and
+ * clsact qdiscs.
+ */
+#define QDISC_HANDLE_AUTO_MIN	0x8000
+#define QDISC_HANDLE_AUTO_MAX	0xFFFE
+
+/* Devices that never carry a qdisc handle of their own never pay for the
+ * IDA, so it is created on first use. Serialised by the rtnl lock.
  */
-static u32 qdisc_alloc_handle(struct net_device *dev)
+static struct ida *qdisc_get_handle_ida(struct net_device *dev)
 {
-	int i = 0x8000;
-	static u32 autohandle = TC_H_MAKE(0x80000000U, 0);
+	struct ida *ida = dev->qdisc_handle_ida;
+
+	ASSERT_RTNL();
+
+	if (!ida) {
+		ida = kmalloc_obj(*ida, GFP_KERNEL);
+		if (!ida)
+			return NULL;
+
+		ida_init(ida);
+		dev->qdisc_handle_ida = ida;
+	}
+
+	return ida;
+}
+
+/* Claim the major of *handle, or the lowest free major in the automatic
+ * range when *handle is zero, and store the resulting handle back.
+ */
+static int qdisc_reserve_handle(struct net_device *dev, u32 *handle)
+{
+	u32 min = QDISC_HANDLE_AUTO_MIN, max = QDISC_HANDLE_AUTO_MAX;
+	struct ida *ida;
+	int major;
+
+	ida = qdisc_get_handle_ida(dev);
+	if (!ida)
+		return -ENOMEM;

-	do {
-		autohandle += TC_H_MAKE(0x10000U, 0);
-		if (autohandle == TC_H_MAKE(TC_H_ROOT, 0))
-			autohandle = TC_H_MAKE(0x80000000U, 0);
-		if (!qdisc_lookup(dev, autohandle))
-			return autohandle;
-		cond_resched();
-	} while	(--i > 0);
+	if (*handle) {
+		min = TC_H_MAJ(*handle) >> 16;
+		max = min;
+	}
+
+	major = ida_alloc_range(ida, min, max, GFP_KERNEL);
+	if (major < 0) {
+		/* A named major that is taken is a collision, not exhaustion. */
+		return (*handle && major == -ENOSPC) ? -EEXIST : major;
+	}

+	*handle = TC_H_MAKE(major << 16, 0);
 	return 0;
 }

+/* Only ever called for a handle that qdisc_create() reserved, so the IDA the
+ * reservation was taken from is still there. Qdiscs that carry no handle of
+ * their own hold no major.
+ */
+void qdisc_free_handle(struct net_device *dev, u32 handle)
+{
+	if (handle)
+		ida_free(dev->qdisc_handle_ida, TC_H_MAJ(handle) >> 16);
+}
+
 void qdisc_tree_reduce_backlog(struct Qdisc *sch, int n, int len)
 {
 	const struct Qdisc_class_ops *cops;
@@ -1306,17 +1358,15 @@ static struct Qdisc *qdisc_create(struct net_device *dev,
 			goto err_out3;
 		}
 		handle = TC_H_MAKE(TC_H_INGRESS, 0);
-	} else {
-		if (handle == 0) {
-			handle = qdisc_alloc_handle(dev);
-			if (handle == 0) {
-				NL_SET_ERR_MSG(extack, "Maximum number of qdisc handles was exceeded");
-				err = -ENOSPC;
-				goto err_out3;
-			}
-		}
-		if (!netif_is_multiqueue(dev))
-			sch->flags |= TCQ_F_ONETXQUEUE;
+	} else if (!netif_is_multiqueue(dev)) {
+		sch->flags |= TCQ_F_ONETXQUEUE;
+	}
+
+	err = qdisc_reserve_handle(dev, &handle);
+	if (err) {
+		if (err == -ENOSPC)
+			NL_SET_ERR_MSG(extack, "Maximum number of qdisc handles was exceeded");
+		goto err_out3;
 	}

 	sch->handle = handle;
@@ -1383,6 +1433,10 @@ static struct Qdisc *qdisc_create(struct net_device *dev,
 		ops->destroy(sch);
 	qdisc_put_stab(rtnl_dereference(sch->stab));
 err_out3:
+	/* sch->handle is assigned only once the handle has been reserved, so
+	 * this is a no-op on the paths that failed before or during it.
+	 */
+	qdisc_free_handle(dev, sch->handle);
 	qdisc_lock_uninit(sch, ops);
 	netdev_put(dev, &sch->dev_tracker);
 	qdisc_free_rcu(sch);
diff --git a/net/sched/sch_generic.c b/net/sched/sch_generic.c
index 6f6a6f0d5eb0..21764a3ee1e0 100644
--- a/net/sched/sch_generic.c
+++ b/net/sched/sch_generic.c
@@ -1110,6 +1110,7 @@ static void __qdisc_destroy(struct Qdisc *qdisc)

 #ifdef CONFIG_NET_SCHED
 	qdisc_hash_del(qdisc);
+	qdisc_free_handle(dev, qdisc->handle);

 	qdisc_put_stab(rtnl_dereference(qdisc->stab));
 #endif
--
2.55.0

Re: [PATCH net] net/sched: Avoid quadratic handle scan in qdisc_alloc_handle

[Eric Dumazet]

On Tue, Sep 15, 2026 at 4:51 AM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
>
> On Mon, Sep 14, 2026 at 10:11 PM Jakub Kicinski <kuba@kernel.org> wrote:
> >
> > On Fri, 11 Sep 2026 10:31:46 -0300 Victor Nogueira wrote:
> > > This is a less intrusive fix meant for backporting; a cleaner approach that
> > > uses a per-device IDA over all qdisc handles is planned for net-next.
> >
> > I don't think this is net-worthy in the first place.
> > We have a ton of code under rtnl_lock.
> > We cannot provide any protection from malicious netns admin from
> > overloading the machine.
>
> That is the one million dollar question.  We labelled this as net for
> this exact reason. i.e malicious container could overload the whole
> machine.
> But it borders on "hardening" (improves performance), so net-next as a
> target sounds reasonable. It was a coin toss.
>
> Since we have a few similar "grey" issues in our pending queue - so
> where's the line for net/net-next?
>
> > Nothing against the patch itself, but if you plan to do something
> > else in net-next let's just go with that from the start..
>
> We could resend the same patch for net-next, the alternative "proper
> fix" is more intrusive. See attached.
> Another option: Is this worth fixing?

A really useful fix would be to get away from RTNL :)

Re: [PATCH net] net/sched: Avoid quadratic handle scan in qdisc_alloc_handle

[Jamal Hadi Salim]

On Tue, Sep 15, 2026 at 8:28 AM Eric Dumazet <edumazet@google.com> wrote:
>
> On Tue, Sep 15, 2026 at 4:51 AM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
> >
> > On Mon, Sep 14, 2026 at 10:11 PM Jakub Kicinski <kuba@kernel.org> wrote:
> > >
> > > On Fri, 11 Sep 2026 10:31:46 -0300 Victor Nogueira wrote:
> > > > This is a less intrusive fix meant for backporting; a cleaner approach that
> > > > uses a per-device IDA over all qdisc handles is planned for net-next.
> > >
> > > I don't think this is net-worthy in the first place.
> > > We have a ton of code under rtnl_lock.
> > > We cannot provide any protection from malicious netns admin from
> > > overloading the machine.
> >
> > That is the one million dollar question.  We labelled this as net for
> > this exact reason. i.e malicious container could overload the whole
> > machine.
> > But it borders on "hardening" (improves performance), so net-next as a
> > target sounds reasonable. It was a coin toss.
> >
> > Since we have a few similar "grey" issues in our pending queue - so
> > where's the line for net/net-next?
> >
> > > Nothing against the patch itself, but if you plan to do something
> > > else in net-next let's just go with that from the start..
> >
> > We could resend the same patch for net-next, the alternative "proper
> > fix" is more intrusive. See attached.
> > Another option: Is this worth fixing?
>
> A really useful fix would be to get away from RTNL :)

Indeed ;-> Right now the AI kiddies are trnding to targetting rtnl as
you can see from this one ;->

cheers,
jamal

Re: [PATCH net] net/sched: Avoid quadratic handle scan in qdisc_alloc_handle

[Jakub Kicinski]

On Tue, 15 Sep 2026 07:50:54 -0400 Jamal Hadi Salim wrote:
> On Mon, Sep 14, 2026 at 10:11 PM Jakub Kicinski <kuba@kernel.org> wrote:
> > On Fri, 11 Sep 2026 10:31:46 -0300 Victor Nogueira wrote:  
> > > This is a less intrusive fix meant for backporting; a cleaner approach that
> > > uses a per-device IDA over all qdisc handles is planned for net-next.  
> >
> > I don't think this is net-worthy in the first place.
> > We have a ton of code under rtnl_lock.
> > We cannot provide any protection from malicious netns admin from
> > overloading the machine.  
> 
> That is the one million dollar question.  We labelled this as net for
> this exact reason. i.e malicious container could overload the whole
> machine.
> But it borders on "hardening" (improves performance), so net-next as a
> target sounds reasonable. It was a coin toss.

IMO any attack from containers / user ns is hardening. If it leads
to a crash we take it via net _because it's a crash_ not because
user ns can trigger it.
 
> Since we have a few similar "grey" issues in our pending queue - so
> where's the line for net/net-next?

TBH the line shifts depending on how bad the AI flood is.
I tried to document some rules but it only lead to bikesheding.
So my recommendation is to write the final fix, without worrying
about keeping it simple. And assume the maintainers will redirect
to the other tree based on their judgement when applying.

With all the AI kiddies these days we routinely apply to a different
tree than tagged.

> > Nothing against the patch itself, but if you plan to do something
> > else in net-next let's just go with that from the start..  
> 
> We could resend the same patch for net-next, the alternative "proper
> fix" is more intrusive. See attached.

I'm not sure we have to do this, given Victor's patch already
drops the time 50x ?

> Another option: Is this worth fixing?

Right, I think it is but IDK if it's worth maintaining state for.
IOW Victor's patch would be enough for my taste.

Re: [PATCH net] net/sched: Avoid quadratic handle scan in qdisc_alloc_handle

[Jamal Hadi Salim]

On Tue, Sep 15, 2026 at 11:53 AM Jakub Kicinski <kuba@kernel.org> wrote:
>
> On Tue, 15 Sep 2026 07:50:54 -0400 Jamal Hadi Salim wrote:
> > On Mon, Sep 14, 2026 at 10:11 PM Jakub Kicinski <kuba@kernel.org> wrote:
> > > On Fri, 11 Sep 2026 10:31:46 -0300 Victor Nogueira wrote:
> > > > This is a less intrusive fix meant for backporting; a cleaner approach that
> > > > uses a per-device IDA over all qdisc handles is planned for net-next.
> > >
> > > I don't think this is net-worthy in the first place.
> > > We have a ton of code under rtnl_lock.
> > > We cannot provide any protection from malicious netns admin from
> > > overloading the machine.
> >
> > That is the one million dollar question.  We labelled this as net for
> > this exact reason. i.e malicious container could overload the whole
> > machine.
> > But it borders on "hardening" (improves performance), so net-next as a
> > target sounds reasonable. It was a coin toss.
>
> IMO any attack from containers / user ns is hardening. If it leads
> to a crash we take it via net _because it's a crash_ not because
> user ns can trigger it.
>

Ok - will review the pending ones with this in mind.

FWIW, here are the rules we have been using:

It is net if: Regression (worked before, broke) or always-triggerable
crash/UAF/leak/lockup
This specific bug could potentially cause a soft lockup but it wasnt
consistently...

It goes to net-next if:
a) Never worked (adds a cap, validation, accounting, or enforcement
that never existed, e.g. memcg-class)
b) Doc/comment
c) tests - although the exception we currently make is if we create a
tdc test for a net patch then it goes to net just dont cc stable on
it.

> > Since we have a few similar "grey" issues in our pending queue - so
> > where's the line for net/net-next?
>
> TBH the line shifts depending on how bad the AI flood is.
> I tried to document some rules but it only lead to bikesheding.
> So my recommendation is to write the final fix, without worrying
> about keeping it simple. And assume the maintainers will redirect
> to the other tree based on their judgement when applying.
>
> With all the AI kiddies these days we routinely apply to a different
> tree than tagged.
>

Given the flood, here are the priority rules we are using:
1) submit net before net-next
2) All bugs must be reproducible by our (semi-automated) system
(hybris). I dont even look at issues unless they are reproducible
(hence my nagging "do you have a PoC?" ;->)
3) Assign a priority to each bug and submit the highest priority ones
first. The priorities are assigned as follows:
- base (reproduced, ACCURATE) +1
- Crash (oops/panic/NULL-deref/OOM/corruption) +2
- UAF +2
- Lockup (soft lockup/livelock/infinite loop) +1
- leak +1
- simple-trigger (plain tc/tdc, no special PoC) +1
- privilege required: (root) +1 / (unshare -Urn) +2

The priority is capped at 9. So a priority 9 with net gets immediate attention.
A priority 9 that requires root permission is not as important as
priority 9 that requires cap_net_admin (-urn)
Yuan has a taxonomy as well; he calls these L1 and L2 when we pull the
reports from his system.
There is an exception: Priority 10. These are assigned to bugs which
require no root/cap_net_admin and other UPEs

We also capture all "pre-existing bugs" and address them when the
pending queue is empty. Most of these end up being a waste after fixes
go in.

> > > Nothing against the patch itself, but if you plan to do something
> > > else in net-next let's just go with that from the start..
> >
> > We could resend the same patch for net-next, the alternative "proper
> > fix" is more intrusive. See attached.
>
> I'm not sure we have to do this, given Victor's patch already
> drops the time 50x ?
>
> > Another option: Is this worth fixing?
>
> Right, I think it is but IDK if it's worth maintaining state for.
> IOW Victor's patch would be enough for my taste.

Ok, we'll send that patch as net-next.

cheers,
jamal

Re: [PATCH net] net/sched: Avoid quadratic handle scan in qdisc_alloc_handle

[Jakub Kicinski]

On Wed, 16 Sep 2026 06:34:57 -0400 Jamal Hadi Salim wrote:
> > IMO any attack from containers / user ns is hardening. If it leads
> > to a crash we take it via net _because it's a crash_ not because
> > user ns can trigger it.
> >  
> 
> Ok - will review the pending ones with this in mind.
> 
> FWIW, here are the rules we have been using:
> 
> It is net if: Regression (worked before, broke) or always-triggerable
> crash/UAF/leak/lockup
> This specific bug could potentially cause a soft lockup but it wasnt
> consistently...
> 
> It goes to net-next if:
> a) Never worked (adds a cap, validation, accounting, or enforcement
> that never existed, e.g. memcg-class)
> b) Doc/comment
> c) tests - although the exception we currently make is if we create a
> tdc test for a net patch then it goes to net just dont cc stable on
> it.
> 
> > > Since we have a few similar "grey" issues in our pending queue - so
> > > where's the line for net/net-next?  
>  [...]  
> 
> Given the flood, here are the priority rules we are using:
> 1) submit net before net-next
> 2) All bugs must be reproducible by our (semi-automated) system
> (hybris). I dont even look at issues unless they are reproducible
> (hence my nagging "do you have a PoC?" ;->)
> 3) Assign a priority to each bug and submit the highest priority ones
> first. The priorities are assigned as follows:
> - base (reproduced, ACCURATE) +1
> - Crash (oops/panic/NULL-deref/OOM/corruption) +2
> - UAF +2
> - Lockup (soft lockup/livelock/infinite loop) +1
> - leak +1
> - simple-trigger (plain tc/tdc, no special PoC) +1
> - privilege required: (root) +1 / (unshare -Urn) +2

nice system :)
no distinction between control path-trigger an packet trigger?

> The priority is capped at 9. So a priority 9 with net gets immediate attention.
> A priority 9 that requires root permission is not as important as
> priority 9 that requires cap_net_admin (-urn)
> Yuan has a taxonomy as well; he calls these L1 and L2 when we pull the
> reports from his system.
> There is an exception: Priority 10. These are assigned to bugs which
> require no root/cap_net_admin and other UPEs
> 
> We also capture all "pre-existing bugs" and address them when the
> pending queue is empty. Most of these end up being a waste after fixes
> go in.

Re: [PATCH net] net/sched: Avoid quadratic handle scan in qdisc_alloc_handle

[Jamal Hadi Salim]

On Wed, Sep 16, 2026 at 8:04 PM Jakub Kicinski <kuba@kernel.org> wrote:
>
> On Wed, 16 Sep 2026 06:34:57 -0400 Jamal Hadi Salim wrote:
> > > IMO any attack from containers / user ns is hardening. If it leads
> > > to a crash we take it via net _because it's a crash_ not because
> > > user ns can trigger it.
> > >
> >
> > Ok - will review the pending ones with this in mind.
> >
> > FWIW, here are the rules we have been using:
> >
> > It is net if: Regression (worked before, broke) or always-triggerable
> > crash/UAF/leak/lockup
> > This specific bug could potentially cause a soft lockup but it wasnt
> > consistently...
> >
> > It goes to net-next if:
> > a) Never worked (adds a cap, validation, accounting, or enforcement
> > that never existed, e.g. memcg-class)
> > b) Doc/comment
> > c) tests - although the exception we currently make is if we create a
> > tdc test for a net patch then it goes to net just dont cc stable on
> > it.
> >
> > > > Since we have a few similar "grey" issues in our pending queue - so
> > > > where's the line for net/net-next?
> >  [...]
> >
> > Given the flood, here are the priority rules we are using:
> > 1) submit net before net-next
> > 2) All bugs must be reproducible by our (semi-automated) system
> > (hybris). I dont even look at issues unless they are reproducible
> > (hence my nagging "do you have a PoC?" ;->)
> > 3) Assign a priority to each bug and submit the highest priority ones
> > first. The priorities are assigned as follows:
> > - base (reproduced, ACCURATE) +1
> > - Crash (oops/panic/NULL-deref/OOM/corruption) +2
> > - UAF +2
> > - Lockup (soft lockup/livelock/infinite loop) +1
> > - leak +1
> > - simple-trigger (plain tc/tdc, no special PoC) +1
> > - privilege required: (root) +1 / (unshare -Urn) +2
>
> nice system :)
> no distinction between control path-trigger an packet trigger?
>

At the moment we dont make a distinction - the existing point system
would still work, I think. Do you see it differently?

cheers,
jamal

Re: [PATCH net] net/sched: Avoid quadratic handle scan in qdisc_alloc_handle

[Jakub Kicinski]

On Thu, 17 Sep 2026 07:24:05 -0400 Jamal Hadi Salim wrote:
> On Wed, Sep 16, 2026 at 8:04 PM Jakub Kicinski <kuba@kernel.org> wrote:
> > > Given the flood, here are the priority rules we are using:
> > > 1) submit net before net-next
> > > 2) All bugs must be reproducible by our (semi-automated) system
> > > (hybris). I dont even look at issues unless they are reproducible
> > > (hence my nagging "do you have a PoC?" ;->)
> > > 3) Assign a priority to each bug and submit the highest priority ones
> > > first. The priorities are assigned as follows:
> > > - base (reproduced, ACCURATE) +1
> > > - Crash (oops/panic/NULL-deref/OOM/corruption) +2
> > > - UAF +2
> > > - Lockup (soft lockup/livelock/infinite loop) +1
> > > - leak +1
> > > - simple-trigger (plain tc/tdc, no special PoC) +1
> > > - privilege required: (root) +1 / (unshare -Urn) +2
> >
> > nice system :)
> > no distinction between control path-trigger an packet trigger?
>
> At the moment we dont make a distinction - the existing point system
> would still work, I think. Do you see it differently?

Right, a bit of a murky call. In abstract packet trigger could mean
remote attacker can crash a middlebox, that's _so_ much more serious.
But in practice most of our packet level attacks are for some insanely
pre-cooked skbs from AF_PACKET and such :/

It was just a thought.