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

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 <redacted>
Co-developed-by: Jamal Hadi Salim <jhs@mojatatu.com>
Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>
Signed-off-by: Victor Nogueira <redacted>

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