mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
* [PATCH net] net/sched: sch_qfq: bound backward slot rotation
@ 2026-11-16 12:17 Lin Jiapeng
  2026-11-18 12:18 ` netdev-bot+sashiko
  0 siblings, 1 reply; 2+ messages in thread
From: Lin Jiapeng @ 2026-11-16 12:17 UTC (permalink / raw)
  To: jhs, jiri, davem, edumazet, kuba, pabeni, horms, paolo.valente,
	netdev, linux-kernel
  Cc: Lin Jiapeng, TencentOS Corvus AI

From: Lin Jiapeng <jiapenglin@tencent.com>

QFQ+ keeps aggregates in timestamp-ordered slots and rotates the
occupied-slot bitmap when a group's start time decreases, avoiding the need
to move the aggregates themselves. Insertions are capped so that occupied
slots leave room for a later backward adjustment.

A stale aggregate can make the start-time decrease larger than the bitmap
can represent. Rotating then pushes existing members beyond full_slots,
and a later qfq_slot_remove() clears a bit in the following slot-list
pointers. KASAN reports the resulting corruption when the group is
selected:
  BUG: KASAN: slab-use-after-free in qfq_choose_next_agg+0xd04/0xd90
  Read of size 8 at addr ff11000102f73010 by task repro/92
  CPU: 0 UID: 1000 PID: 92 Comm: repro
  Call Trace:
   kasan_report+0xe4/0x1a0
   qfq_choose_next_agg+0xd04/0xd90
   qfq_dequeue+0x365/0x14b0
   qdisc_peek_dequeued+0x91/0x280
   tbf_dequeue+0x91/0xcd0
  Allocated by task 91:
   qfq_change_class+0xca5/0x1c50
   tc_ctl_tclass+0x4ee/0x1400
  Freed by task 37:
   kfree+0x1b3/0x550
   qfq_rm_from_agg+0x228/0x300
   qfq_destroy_qdisc+0x118/0x1e0
  The buggy address belongs to the object at ff11000102f73000,
  which belongs to the cache kmalloc-128 of size 128.
  The buggy address is located 16 bytes inside of
  freed 128-byte region [ff11000102f73000, ff11000102f73080)
The report is followed by a kernel panic.

Limit the backward adjustment according to BITS_PER_LONG and the
largest insertion slot. If it exceeds that limit, move the activating
aggregate's S/F and rounded start time forward by the same slot-aligned
delta before rotating. This preserves the timestamp and physical-slot
mapping, keeps every removal offset inside full_slots, and leaves
representable rotations unchanged.

Fixes: 462dbc9101ac ("pkt_sched: QFQ Plus: fair-queueing service at DRR cost")
Reported-by: TencentOS Corvus AI <corvus@tencent.com>
Signed-off-by: Lin Jiapeng <jiapenglin@tencent.com>
---
 net/sched/sch_qfq.c | 13 +++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/net/sched/sch_qfq.c b/net/sched/sch_qfq.c
index e900890e9c54..e83105ce9015 100644
--- a/net/sched/sch_qfq.c
+++ b/net/sched/sch_qfq.c
@@ -1300,7 +1300,7 @@ static int qfq_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 static void qfq_schedule_agg(struct qfq_sched *q, struct qfq_aggregate *agg)
 {
 	struct qfq_group *grp = agg->grp;
-	u64 roundedS;
+	u64 roundedS, slot;
 	int s;
 
 	roundedS = qfq_round_down(agg->S, grp->slot_shift);
@@ -1318,6 +1318,17 @@ static int qfq_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 		if (!qfq_gt(grp->S, agg->S))
 			goto skip_update;
 
+		slot = (grp->S - roundedS) >> grp->slot_shift;
+		if (unlikely(slot > BITS_PER_LONG - QFQ_MAX_SLOTS + 1)) {
+			u64 deltaS = grp->S - roundedS -
+				((u64)(BITS_PER_LONG - QFQ_MAX_SLOTS + 1) <<
+				 grp->slot_shift);
+
+			agg->S += deltaS;
+			agg->F += deltaS;
+			roundedS += deltaS;
+		}
+
 		/* create a slot for this agg->S */
 		qfq_slot_rotate(grp, roundedS);
 		/* group was surely ineligible, remove */
-- 
2.55.0


^ permalink raw reply	[flat|nested] 2+ messages in thread

* Re: [PATCH net] net/sched: sch_qfq: bound backward slot rotation
  2026-11-16 12:17 [PATCH net] net/sched: sch_qfq: bound backward slot rotation Lin Jiapeng
@ 2026-11-18 12:18 ` netdev-bot+sashiko
  0 siblings, 0 replies; 2+ messages in thread
From: netdev-bot+sashiko @ 2026-11-18 12:18 UTC (permalink / raw)
  To: ljp1205831794
  Cc: jhs, jiri, davem, edumazet, kuba, pabeni, horms, paolo.valente,
	netdev, linux-kernel, jiapenglin, corvus

Thank you for your contribution! Sashiko AI review found 3 potential
issue(s) to consider.

Critical: 1 · High: 1 · Medium: 0 · Low: 1

If you believe none of the issues are legitimate, please reply to each
issue of Medium severity or higher and explain why the AI is wrong.
If any of them are legitimate and you plan to respin, please let patchwork
know by including "pw-bot: cr" as a separate line at the end of your reply
(one such reply per series is enough).

- [Critical] The clamp added to qfq_schedule_agg() is a fixed constant
  (33 on 64-bit, 1 on 32-bit).
- [High] On 64-bit, the new clamp in qfq_schedule_agg()
  (net/sched/sch_qfq.c:1321-1333) allows a backward rotation of…
- [Low] Two existing comments in net/sched/sch_qfq.c now contradict the
  new code in qfq_schedule_agg().

--

net/sched: sch_qfq: bound backward slot rotation

This patch caps the backward slot rotation in qfq_schedule_agg() at
BITS_PER_LONG - QFQ_MAX_SLOTS + 1 slots. If the start-time decrease is
larger than that, it first moves the activating aggregate's S, F and
roundedS forward by the excess and then calls qfq_slot_rotate(). The
goal is to stop qfq_slot_remove() from clearing bits beyond full_slots,
in the slot-list pointers that follow it.

> diff --git a/net/sched/sch_qfq.c b/net/sched/sch_qfq.c
> index e900890e9c544..e83105ce90156 100644
> --- a/net/sched/sch_qfq.c
> +++ b/net/sched/sch_qfq.c

[ ... ]

> @@ -1318,6 +1318,17 @@ static void qfq_schedule_agg(struct qfq_sched *q, struct qfq_aggregate *agg)
>  		if (!qfq_gt(grp->S, agg->S))
>  			goto skip_update;
>  
> +		slot = (grp->S - roundedS) >> grp->slot_shift;
> +		if (unlikely(slot > BITS_PER_LONG - QFQ_MAX_SLOTS + 1)) {

[Severity: High]

On 64-bit this allows a rotation of 33 slots. Is that bound safe when
grp->slots[] has only QFQ_MAX_SLOTS (32) entries?

Every user indexes the lists modulo 32. For example, in qfq_slot_insert():

	i = (grp->front + slot) % QFQ_MAX_SLOTS;

	hlist_add_head(&agg->next, &grp->slots[i]);
	__set_bit(slot, &grp->full_slots);

After a 33-slot rotation the existing members sit at logical offsets
33..63. These share physical hlists with offsets 1..31.

Suppose a later skip_update insertion lands at offset j (1..30). It joins
the list that already holds the member tracked by bit j+32, so two
full_slots bits now describe one list.

A possible sequence:

  X at bit 0, physical slot f
  stale B is capped and rotated by 33:
      X moves to bit 33 (still physical f)
      B goes to bit 0 (physical f-1)
  Y is inserted at offset 1, which is physical f, the list X is on
  B is served, then Y, then X

That leaves full_slots == {32} over an empty list. When the shared list
empties, qfq_front_slot_remove() clears only bit 0, so the aliased bit
stays set. qfq_slot_scan() then shifts by 32 and returns qfq_slot_head()
of the empty slots[f], which is NULL.

>From there, qfq_choose_next_agg() takes the NULL as "group is now
inactive" and clears the ER bit, even though grp->full_slots is still
nonzero:

	new_front_agg = qfq_slot_scan(grp);

	if (new_front_agg == NULL) /* group is now inactive, remove from ER */
		__clear_bit(grp->index, &q->bitmaps[ER]);

Any later activation of this group with S >= grp->S takes skip_update
and is orphaned. Once the other aggregates drain, can qfq_dequeue() call
qfq_peek_skb() with a NULL in_serv_agg?

If the stale bit is reached from qfq_deactivate_agg() instead, this
dereferences NULL directly:

	agg = qfq_slot_scan(grp);
	roundedS = qfq_round_down(agg->S, grp->slot_shift);

If it is reached from qfq_front_slot_remove(), BUG_ON(!agg) fires.
Aliased lists also serve aggregates out of timestamp order.

The commit message says:

  "This preserves the timestamp and physical-slot mapping, keeps every
  removal offset inside full_slots"

Does that still hold once the bitmap and the physical lists no longer map
1:1? Should the bound keep every occupied offset below QFQ_MAX_SLOTS
rather than below BITS_PER_LONG?

> +			u64 deltaS = grp->S - roundedS -
> +				((u64)(BITS_PER_LONG - QFQ_MAX_SLOTS + 1) <<
> +				 grp->slot_shift);
> +
> +			agg->S += deltaS;
> +			agg->F += deltaS;
> +			roundedS += deltaS;
> +		}

[Severity: Critical]

The clamp is a fixed constant (33 on 64-bit, 1 on 32-bit) and never
reads grp->full_slots. It is only safe if the highest set bit of
grp->full_slots is at most QFQ_MAX_SLOTS - 2 at rotation time. Can that
assumption be broken?

Two sequences seem to break it:

(a) qfq_slot_insert() puts a member at the capped offset 30, and an
ordinary 1-slot backward rotation moves it to bit 31. A later capped
33-slot rotation moves it to bit 64. On 32-bit, any further 1-slot
rotation does the same.

(b) A capped rotation leaves old members at bits 33..63. A second stale
aggregate in the same group triggers another capped 33-slot rotation,
and bit 33 becomes bit 66.

In both cases qfq_slot_rotate() silently drops the bit:

	grp->full_slots <<= i;

The aggregate stays linked on its slots[] hlist, though. When it is later
removed through qfq_deactivate_agg()->qfq_slot_remove():

	offset = (roundedS - grp->S) >> grp->slot_shift;
	...
	if (hlist_empty(&grp->slots[i]))
		__clear_bit(offset, &grp->full_slots);

offset is >= BITS_PER_LONG here. Doesn't __clear_bit() then write into
the grp->slots[] hlist_head pointers that follow full_slots in struct
qfq_group? Offsets of 71 and above would flip real pointer bits.

That looks like the same corruption the commit message describes:

  "a later qfq_slot_remove() clears a bit in the following slot-list
  pointers"

Even when the stray clear hits a bit that is already zero, the aggregate
no longer has a bit in full_slots, so qfq_slot_scan() never reaches it.
Once the other aggregates drain, qfq_choose_next_agg() returns NULL while
sch->q.qlen > 0, and qfq_dequeue() calls qfq_peek_skb(NULL, ...).

Should the bound use the highest occupied bit, for example
__fls(grp->full_slots), instead of assuming it is QFQ_MAX_SLOTS - 2?

> +
>  		/* create a slot for this agg->S */
>  		qfq_slot_rotate(grp, roundedS);

[Severity: Low]

This isn't a bug, but two existing comments in sch_qfq.c now contradict
this rotation bound. The comment above qfq_slot_insert() says:

 * and not a '-1' because the start time of the group may be moved
 * backward by one slot after the aggregate has been inserted, and

The comment above qfq_slot_rotate() says:

 * Here too we should make sure that i is less than 32

With this change, qfq_slot_rotate() can run with i == 33 on 64-bit, and
neither comment is updated. Since slots[] really has 32 entries, the
comments seem to state the correct constraint.

[ ... ]

-- 
Sashiko AI review · https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20261116121710.77403-1-ljp1205831794%40gmail.com

^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2026-11-18 12:18 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2026-11-16 12:17 [PATCH net] net/sched: sch_qfq: bound backward slot rotation Lin Jiapeng
2026-11-18 12:18 ` netdev-bot+sashiko

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®