[PATCH net v3] net/sched: taprio: catch up in bounded time when the schedule falls behind

[PATCH net v3] net/sched: taprio: catch up in bounded time when the schedule falls behind

[Junjie Cao]

advance_sched() advances exactly one entry per hrtimer expiry. When the
operational schedule falls behind - the timer was delayed, the CPU was
starved, or the reference clock stepped forward - every elapsed entry is
replayed back to back from hrtimer context with current_entry_lock held,
and each replay rearms the timer with an expiry in the past. Once the
backlog is large enough the CPU never leaves timer processing and RCU
stalls follow. syzbot triggers this with schedules whose intervals are
shorter than the cost of servicing one expiry, so the backlog only ever
grows.

Skip whole periods arithmetically and walk at most one more to the entry
covering the current time. The software schedule restarts the list after
its last entry even when that is before cycle_time, so its period is
min(cycle_time, sum of intervals); record it at parse time. Advance
cycle_end_time by the period as well: with cycle_time it runs ahead of
the entries by the difference every lap, and skipping whole laps at once
would overflow it within minutes for a schedule with nanosecond
intervals and a cycle_time of seconds. Gate close times and budgets are
still only computed for the entry landed on, and an admin schedule
crossed by the jump is picked up by the existing
should_change_schedules() check on the recomputed end time. The walk is
capped at twice the entry count; a leftover is handled by the next
expiry as today.

Fixes: 5a781ccbd19e ("tc: Add support for configuring the taprio scheduler")
Reported-by: syzbot+19d01f6082ec61dd45b2@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=19d01f6082ec61dd45b2
Tested-by: syzbot+19d01f6082ec61dd45b2@syzkaller.appspotmail.com
Reported-by: syzbot+8785aaf121cfb2141e0d@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=8785aaf121cfb2141e0d
Tested-by: syzbot+8785aaf121cfb2141e0d@syzkaller.appspotmail.com
Reported-by: syzbot+2642f347f7309b4880dc@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=2642f347f7309b4880dc
Tested-by: syzbot+2642f347f7309b4880dc@syzkaller.appspotmail.com
Reported-by: syzbot+e4aa91d7f20c34417d4e@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=e4aa91d7f20c34417d4e
Tested-by: syzbot+e4aa91d7f20c34417d4e@syzkaller.appspotmail.com
Signed-off-by: Junjie Cao <junjie.cao@intel.com>
---
v3:
- jump in whole periods of min(cycle_time, sum of intervals) rather
  than cycle_time, and fold the walk into advance_sched() instead of a
  helper duplicating its step (Jakub)
- treat end == now as behind; comment on the cap and on rewriting the
  published entry (Jakub)
- advance cycle_end_time by the period as well, not left alone as I
  said in the v2 thread: with cycle_time it runs ahead of the entries
  by (cycle_time - sum) per lap, and skipping whole laps turns that
  into an s64 overflow within minutes for a schedule with nanosecond
  intervals and a cycle_time of seconds
- the walk finishes within num_entries steps once the first expiry has
  been serviced; a schedule whose cycle_time is shorter than its first
  entry starts with cycle_end_time behind that entry and takes one more
  expiry to line up, where today it replays until it does
- drop the minimum-interval patch and its selftest (Jakub)
- tags for a fourth syzbot bucket, tested by akpm with the v2 patch
  alone; all four re-tested with this version
v2: https://lore.kernel.org/all/20260820062715.278124-1-junjie.cao@intel.com/
- take now from the timer's clock base (Hillf Danton)
v1: https://lore.kernel.org/all/20260818071706.251035-1-junjie.cao@intel.com/

 net/sched/sch_taprio.c | 72 ++++++++++++++++++++++++++++++------------
 1 file changed, 52 insertions(+), 20 deletions(-)

diff --git a/net/sched/sch_taprio.c b/net/sched/sch_taprio.c
index 39ac5b97aa3a..901dfd2484e1 100644
--- a/net/sched/sch_taprio.c
+++ b/net/sched/sch_taprio.c
@@ -83,6 +83,10 @@ struct sched_gate_list {
 	s64 cycle_time;
 	s64 cycle_time_extension;
 	s64 base_time;
+	/* min(cycle_time, sum of intervals): the software schedule restarts
+	 * the list after the last entry even when cycle_time is not up yet.
+	 */
+	s64 period;
 };
 
 struct taprio_sched {
@@ -871,12 +875,13 @@ static struct sk_buff *taprio_dequeue(struct Qdisc *sch)
 }
 
 static bool should_restart_cycle(const struct sched_gate_list *oper,
-				 const struct sched_entry *entry)
+				 const struct sched_entry *entry,
+				 ktime_t end_time)
 {
 	if (list_is_last(&entry->list, &oper->entries))
 		return true;
 
-	if (ktime_compare(entry->end_time, oper->cycle_end_time) == 0)
+	if (ktime_compare(end_time, oper->cycle_end_time) == 0)
 		return true;
 
 	return false;
@@ -925,8 +930,9 @@ static enum hrtimer_restart advance_sched(struct hrtimer *timer)
 	int num_tc = netdev_get_num_tc(dev);
 	struct sched_entry *entry, *next;
 	struct Qdisc *sch = q->root;
-	ktime_t end_time;
-	int tc;
+	ktime_t end_time, next_start, now;
+	int budget, tc;
+	s64 behind;
 
 	spin_lock(&q->current_entry_lock);
 	entry = rcu_dereference_protected(q->current_entry,
@@ -952,23 +958,49 @@ static enum hrtimer_restart advance_sched(struct hrtimer *timer)
 		goto first_run;
 	}
 
-	if (should_restart_cycle(oper, entry)) {
-		next = list_first_entry(&oper->entries, struct sched_entry,
-					list);
-		oper->cycle_end_time = ktime_add_ns(oper->cycle_end_time,
-						    oper->cycle_time);
-	} else {
-		next = list_next_entry(entry, list);
+	now = hrtimer_cb_get_time(timer);
+	end_time = entry->end_time;
+	behind = ktime_sub(now, end_time);
+
+	/* Behind, e.g. delayed timer or stepped clock: skip whole periods
+	 * arithmetically and walk at most one more to the entry covering
+	 * now, instead of replaying the backlog one expiry at a time. The
+	 * cap bounds the walk; a leftover is picked up by the next expiry.
+	 */
+	if (unlikely(behind >= oper->period)) {
+		s64 jump = div64_s64(behind, oper->period) * oper->period;
+
+		end_time = ktime_add_ns(end_time, jump);
+		oper->cycle_end_time = ktime_add_ns(oper->cycle_end_time, jump);
 	}
 
-	end_time = ktime_add_ns(entry->end_time, next->interval);
-	end_time = min_t(ktime_t, end_time, oper->cycle_end_time);
+	budget = 2 * oper->num_entries;
+	do {
+		if (should_restart_cycle(oper, entry, end_time)) {
+			next = list_first_entry(&oper->entries,
+						struct sched_entry, list);
+			oper->cycle_end_time = ktime_add_ns(oper->cycle_end_time,
+							    oper->period);
+		} else {
+			next = list_next_entry(entry, list);
+		}
+
+		next_start = end_time;
+		end_time = ktime_add_ns(next_start, next->interval);
+		end_time = min_t(ktime_t, end_time, oper->cycle_end_time);
+		entry = next;
+	} while (unlikely(ktime_compare(end_time, now) <= 0) && budget--);
 
+	/* next can be the entry already published as q->current_entry (a
+	 * single-entry schedule, or a catch-up of whole periods), so the
+	 * close times and budgets below are rewritten in place while
+	 * taprio_dequeue_from_txq() may be reading them.
+	 */
 	for (tc = 0; tc < num_tc; tc++) {
 		if (next->gate_duration[tc] == oper->cycle_time)
 			next->gate_close_time[tc] = KTIME_MAX;
 		else
-			next->gate_close_time[tc] = ktime_add_ns(entry->end_time,
+			next->gate_close_time[tc] = ktime_add_ns(next_start,
 								 next->gate_duration[tc]);
 	}
 
@@ -1130,6 +1162,8 @@ static int parse_taprio_schedule(struct taprio_sched *q, struct nlattr **tb,
 				 struct sched_gate_list *new,
 				 struct netlink_ext_ack *extack)
 {
+	struct sched_entry *entry;
+	ktime_t cycle = 0;
 	int err = 0;
 
 	if (tb[TCA_TAPRIO_ATTR_SCHED_SINGLE_ENTRY]) {
@@ -1152,13 +1186,10 @@ static int parse_taprio_schedule(struct taprio_sched *q, struct nlattr **tb,
 	if (err < 0)
 		return err;
 
-	if (!new->cycle_time) {
-		struct sched_entry *entry;
-		ktime_t cycle = 0;
-
-		list_for_each_entry(entry, &new->entries, list)
-			cycle = ktime_add_ns(cycle, entry->interval);
+	list_for_each_entry(entry, &new->entries, list)
+		cycle = ktime_add_ns(cycle, entry->interval);
 
+	if (!new->cycle_time) {
 		if (cycle < 0 || cycle > INT_MAX) {
 			NL_SET_ERR_MSG(extack, "'cycle_time' is too big");
 			return -EINVAL;
@@ -1172,6 +1203,7 @@ static int parse_taprio_schedule(struct taprio_sched *q, struct nlattr **tb,
 		return -EINVAL;
 	}
 
+	new->period = min(new->cycle_time, cycle);
 	taprio_calculate_gate_durations(q, new);
 
 	return 0;
-- 
2.43.0

Re: [net,v3] net/sched: taprio: catch up in bounded time when the schedule falls behind

[netdev-bot+sashiko]

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

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

- [Medium] Data race on a live, RCU-published `struct sched_entry`: the
  new catch-up walk in `advance_sched()`…

Pre-existing issues:
- [Low] Claim that the new `sched_gate_list::period` contract
  (min(cycle_time, sum of intervals), net/sched/sch_taprio.c:86-89) is…

--

net/sched: taprio: catch up in bounded time when the schedule falls behind

advance_sched() used to advance exactly one schedule entry per hrtimer
expiry, so a delayed timer or a stepped reference clock made it replay the
whole backlog from timer context.  This patch skips whole periods
arithmetically, records the software period as min(cycle_time, sum of
intervals) at parse time, and caps the remaining walk at twice the entry
count.

Closes: https://syzkaller.appspot.com/bug?extid=19d01f6082ec61dd45b2
Closes: https://syzkaller.appspot.com/bug?extid=8785aaf121cfb2141e0d
Closes: https://syzkaller.appspot.com/bug?extid=2642f347f7309b4880dc
Closes: https://syzkaller.appspot.com/bug?extid=e4aa91d7f20c34417d4e

> diff --git a/net/sched/sch_taprio.c b/net/sched/sch_taprio.c
> index 39ac5b97aa3af..901dfd2484e10 100644
> --- a/net/sched/sch_taprio.c
> +++ b/net/sched/sch_taprio.c
> @@ -83,6 +83,10 @@ struct sched_gate_list {
>  	s64 cycle_time;
>  	s64 cycle_time_extension;
>  	s64 base_time;
> +	/* min(cycle_time, sum of intervals): the software schedule restarts
> +	 * the list after the last entry even when cycle_time is not up yet.
> +	 */
> +	s64 period;
>  };

[Severity: Low]
This is a pre-existing issue and not introduced by the patch, but now that
the effective software repetition length has a name, should the sites that
test for an "always open" gate use it too?

The "never closes" tests all compare against cycle_time rather than the new
period:

net/sched/sch_taprio.c:advance_sched() {
	if (next->gate_duration[tc] == oper->cycle_time)
		next->gate_close_time[tc] = KTIME_MAX;
}

net/sched/sch_taprio.c:taprio_set_budgets() {
	/* Traffic classes which never close have infinite budget */
	if (entry->gate_duration[tc] == sched->cycle_time)
		budget = INT_MAX;
}

The same equality against cycle_time is used in
taprio_update_queue_max_sdu() and setup_first_end_time(), while
taprio_calculate_gate_durations() accumulates gate_duration over the whole
circular list:

net/sched/sch_taprio.c:taprio_calculate_gate_durations() {
		cur = list_next_entry_circular(cur, &sched->entries, list);
	} while (cur != entry);
}

So gate_duration[tc] can be at most the sum of the intervals.  When
cycle_time is configured larger than that sum, does a gate that is open in
every entry still match "== cycle_time", or does it end up with a finite
gate_close_time and a finite byte budget instead of KTIME_MAX / INT_MAX?

> @@ -952,23 +958,49 @@ static enum hrtimer_restart advance_sched(struct hrtimer *timer)
>  		goto first_run;
>  	}
>  
> -	if (should_restart_cycle(oper, entry)) {
> -		next = list_first_entry(&oper->entries, struct sched_entry,
> -					list);
> -		oper->cycle_end_time = ktime_add_ns(oper->cycle_end_time,
> -						    oper->cycle_time);
> -	} else {
> -		next = list_next_entry(entry, list);
> +	now = hrtimer_cb_get_time(timer);
> +	end_time = entry->end_time;
> +	behind = ktime_sub(now, end_time);
> +
> +	/* Behind, e.g. delayed timer or stepped clock: skip whole periods
> +	 * arithmetically and walk at most one more to the entry covering
> +	 * now, instead of replaying the backlog one expiry at a time. The
> +	 * cap bounds the walk; a leftover is picked up by the next expiry.
> +	 */
> +	if (unlikely(behind >= oper->period)) {
> +		s64 jump = div64_s64(behind, oper->period) * oper->period;
> +
> +		end_time = ktime_add_ns(end_time, jump);
> +		oper->cycle_end_time = ktime_add_ns(oper->cycle_end_time, jump);
>  	}
>  
> -	end_time = ktime_add_ns(entry->end_time, next->interval);
> -	end_time = min_t(ktime_t, end_time, oper->cycle_end_time);
> +	budget = 2 * oper->num_entries;
> +	do {
> +		if (should_restart_cycle(oper, entry, end_time)) {
> +			next = list_first_entry(&oper->entries,
> +						struct sched_entry, list);
> +			oper->cycle_end_time = ktime_add_ns(oper->cycle_end_time,
> +							    oper->period);
> +		} else {
> +			next = list_next_entry(entry, list);
> +		}
> +
> +		next_start = end_time;
> +		end_time = ktime_add_ns(next_start, next->interval);
> +		end_time = min_t(ktime_t, end_time, oper->cycle_end_time);
> +		entry = next;
> +	} while (unlikely(ktime_compare(end_time, now) <= 0) && budget--);
>  
> +	/* next can be the entry already published as q->current_entry (a
> +	 * single-entry schedule, or a catch-up of whole periods), so the
> +	 * close times and budgets below are rewritten in place while
> +	 * taprio_dequeue_from_txq() may be reading them.
> +	 */
>  	for (tc = 0; tc < num_tc; tc++) {
>  		if (next->gate_duration[tc] == oper->cycle_time)
>  			next->gate_close_time[tc] = KTIME_MAX;
>  		else
> -			next->gate_close_time[tc] = ktime_add_ns(entry->end_time,
> +			next->gate_close_time[tc] = ktime_add_ns(next_start,
>  								 next->gate_duration[tc]);
>  	}

[Severity: Medium]
Can this race on the live entry be avoided rather than documented?

The walk reassigns entry = next on every iteration, so after num_entries
steps it lands back on the entry that is still published in
q->current_entry.  With the leftover r = behind % period, the extra step is
taken whenever r >= period - interval(current entry), so multi-entry
schedules can reach the case too, not just the single-entry one.

Once next == q->current_entry, advance_sched() rewrites gate_close_time[]
with plain 64-bit stores while the dequeue path reads it lockless:

net/sched/sch_taprio.c:taprio_entry_allows_tx() {
	return ktime_before(skb_end_time, entry->gate_close_time[tc]);
}

net/sched/sch_taprio.c:taprio_dequeue_from_txq() {
	if (gate_mask != TAPRIO_ALL_GATES_OPEN &&
	    !taprio_entry_allows_tx(guard, entry, tc))
		return NULL;

	/* ... and no budget. */
	if (gate_mask != TAPRIO_ALL_GATES_OPEN &&
	    taprio_update_budgets(entry, len, tc, num_tc) < 0)
		return NULL;
}

advance_sched() holds q->current_entry_lock and runs from the hrtimer
(HRTIMER_MODE_ABS, hardirq), while taprio_dequeue() ->
taprio_dequeue_tc_priority() -> taprio_dequeue_from_txq() only holds
rcu_read_lock() and never takes that lock.  On 32-bit, can
taprio_entry_allows_tx() observe a torn ktime_t here, since neither side
uses READ_ONCE()/WRITE_ONCE()?

The budget reset has the same overlap:

net/sched/sch_taprio.c:taprio_set_budgets() {
		atomic_set(&entry->budget[tc], budget);
}

Can this atomic_set() on the published entry discard a concurrent
atomic_sub()/atomic_sub_return() from taprio_update_budgets(), letting a
frame be released against a freshly reset budget?

The comment added above the loop states the overlap exists ("next can be
the entry already published as q->current_entry ... rewritten in place
while taprio_dequeue_from_txq() may be reading them").  Would it be
preferable to keep the writer off the published entry, for example by
stopping the walk one step earlier or by publishing before rewriting, so
the guard band and byte budget are not mutated underneath a reader?

[ ... ]

> @@ -1172,6 +1203,7 @@ static int parse_taprio_schedule(struct taprio_sched *q, struct nlattr **tb,
>  		return -EINVAL;
>  	}
>  
> +	new->period = min(new->cycle_time, cycle);
>  	taprio_calculate_gate_durations(q, new);
>  
>  	return 0;

-- 
Sashiko AI review · https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260901093340.420809-1-junjie.cao%40intel.com