Re: [PATCH net] net/sched: sch_qfq: bound backward slot rotation

From
netdev-bot+sashiko@kernel.org
Date
2026-11-18 12:18:23
Also in
lkml
Reply to
Lin Jiapeng, 2026-11-16
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.
quoted hunk ↗ jump to hunk
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
[ ... ]
quoted hunk ↗ jump to hunk
@@ -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?
quoted hunk ↗ jump to hunk
+			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?
quoted hunk ↗ jump to hunk
+
 		/* 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
Thread (2 messages) 2 messages, 2 authors, last reply 7h ago
Keyboard shortcuts
hback out one level
jnext message in thread / next series-diff position
kprevious message in thread / previous series-diff position
ldrill in
Escclose help / fold thread tree
?toggle this help