[PATCH net 0/3] net/sched: taprio: fix software schedule livelocks

[PATCH net 0/3] net/sched: taprio: fix software schedule livelocks

[Junjie Cao]

advance_sched() livelocks the owning CPU in two independent ways:
schedules with entry intervals below the cost of servicing one hrtimer
expiry pass validation, because virtual devices inflate the link speed
behind the frame-length minimum, and a valid schedule that falls
behind - delayed timer, starved CPU, stepped clock - replays its whole
backlog one entry per expiry from hrtimer context.

Neither fix covers the other case. With only bounded catch-up, a 700ns
single-entry schedule on veth is still admitted and sustains ~1M timer
irqs/s on a release build. With only the interval floor, a stepped
clock still replays the backlog. Clamping the next expiry into the
future at runtime, as tested on one of the reproducer buckets in 2025
[1], keeps the stall detector quiet but leaves the sub-microsecond
schedule admitted, the CPU servicing an expiry every few microseconds
for the lifetime of the qdisc, and the gates drifting off the
configured timeline with every clamped expiry.

Patch 2 extends the patch generated by syzkaller's patching workflow
[2] to exempt txtime-assist, which never arms the per-entry hrtimer.
syzbot tested the series against the reproducers of all three known
buckets on net.git; tags on patch 2.

[1] https://lore.kernel.org/all/20250729010657.3326-1-hdanton@sina.com/
[2] https://lore.kernel.org/all/afe041f6-ef7d-4434-b2d0-096be49b5bcb@mail.kernel.org/


Junjie Cao (2):
  net/sched: taprio: catch up in bounded time when the schedule falls
    behind
  selftests/tc-testing: taprio: add case for the software minimum
    interval

Uladzislau Zhauniarovich (1):
  net/sched: taprio: enforce a minimum interval for software schedules

 net/sched/sch_taprio.c                        | 80 +++++++++++++++++--
 .../tc-testing/tc-tests/qdiscs/taprio.json    | 22 +++++
 2 files changed, 97 insertions(+), 5 deletions(-)

-- 
2.43.0

[PATCH net 1/3] 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 complete cycles arithmetically and walk at most one cycle of
entries to land on the entry covering the current time. Gate close
times and budgets are still only computed for the entry landed on. 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 as a safeguard against degenerate
intervals; leftover backlog is then handled by the next expiry as
today.

Fixes: 5a781ccbd19e ("tc: Add support for configuring the taprio scheduler")
Signed-off-by: Junjie Cao <junjie.cao@intel.com>
---
 net/sched/sch_taprio.c | 56 +++++++++++++++++++++++++++++++++++++++---
 1 file changed, 53 insertions(+), 3 deletions(-)

diff --git a/net/sched/sch_taprio.c b/net/sched/sch_taprio.c
index 299234a5f0fe..f3f90c5d2dca 100644
--- a/net/sched/sch_taprio.c
+++ b/net/sched/sch_taprio.c
@@ -915,6 +915,51 @@ static bool should_change_schedules(const struct sched_gate_list *admin,
 	return false;
 }
 
+/* The operational schedule fell behind, e.g. because the timer was delayed
+ * or the reference clock stepped forward. Advancing one entry per timer
+ * expiry would replay the whole backlog from hrtimer context, so skip
+ * complete cycles arithmetically and walk the remaining entries to land on
+ * the entry covering the current time.
+ */
+static void taprio_catch_up(struct sched_gate_list *oper,
+			    struct sched_entry **next, ktime_t *next_start,
+			    ktime_t *end_time, ktime_t now)
+{
+	int budget = 2 * oper->num_entries + 1;
+	struct sched_entry *entry = *next;
+	ktime_t start = *next_start;
+	ktime_t end = *end_time;
+	s64 behind = ktime_sub(now, end);
+
+	if (oper->cycle_time > 0 && behind >= oper->cycle_time) {
+		s64 jump = div64_s64(behind, oper->cycle_time) * oper->cycle_time;
+
+		start = ktime_add_ns(start, jump);
+		end = ktime_add_ns(end, jump);
+		oper->cycle_end_time = ktime_add_ns(oper->cycle_end_time, jump);
+	}
+
+	while (ktime_before(end, now) && --budget) {
+		if (list_is_last(&entry->list, &oper->entries) ||
+		    ktime_compare(end, oper->cycle_end_time) == 0) {
+			entry = list_first_entry(&oper->entries,
+						 struct sched_entry, list);
+			oper->cycle_end_time = ktime_add_ns(oper->cycle_end_time,
+							    oper->cycle_time);
+		} else {
+			entry = list_next_entry(entry, list);
+		}
+
+		start = end;
+		end = ktime_add_ns(end, entry->interval);
+		end = min_t(ktime_t, end, oper->cycle_end_time);
+	}
+
+	*next = entry;
+	*next_start = start;
+	*end_time = end;
+}
+
 static enum hrtimer_restart advance_sched(struct hrtimer *timer)
 {
 	struct taprio_sched *q = container_of(timer, struct taprio_sched,
@@ -924,7 +969,7 @@ 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;
+	ktime_t end_time, next_start, now;
 	int tc;
 
 	spin_lock(&q->current_entry_lock);
@@ -960,14 +1005,19 @@ static enum hrtimer_restart advance_sched(struct hrtimer *timer)
 		next = list_next_entry(entry, list);
 	}
 
-	end_time = ktime_add_ns(entry->end_time, next->interval);
+	next_start = entry->end_time;
+	end_time = ktime_add_ns(next_start, next->interval);
 	end_time = min_t(ktime_t, end_time, oper->cycle_end_time);
 
+	now = taprio_get_time(q);
+	if (unlikely(ktime_before(end_time, now)))
+		taprio_catch_up(oper, &next, &next_start, &end_time, now);
+
 	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]);
 	}
 
-- 
2.43.0

[PATCH net 2/3] net/sched: taprio: enforce a minimum interval for software schedules

[Junjie Cao]

From: Uladzislau Zhauniarovich <uladzislau.zhauniarovich@gmail.com>

The interval validation only requires an entry to cover the
transmission of a minimum sized frame at link speed. Virtual devices
inflate that budget: veth advertises 10Gb/s and bonding sums the
speeds of its members, so length_to_duration(ETH_ZLEN) evaluates to a
few tens of nanoseconds and schedules with nanosecond intervals pass
validation. In software mode each entry expiry is an hrtimer callback
costing on the order of 10us on a debug configuration and about a
microsecond on a release build; intervals below that cost rearm the
timer with an expiry already in the past, storming the CPU with back
to back timer interrupts until RCU stalls.

Require 100us per entry in software mode, leaving margin above the
timer service cost. Offloaded and txtime-assist schedules never arm
the per-entry hrtimer and keep the frame-length based minimum only.

Fixes: b5b73b26b3ca ("taprio: Fix allowing too small intervals")
Reported-by: syzbot+19d01f6082ec61dd45b2@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=19d01f6082ec61dd45b2
Reported-by: syzbot+8785aaf121cfb2141e0d@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=8785aaf121cfb2141e0d
Reported-by: syzbot+2642f347f7309b4880dc@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=2642f347f7309b4880dc
Tested-by: syzbot+19d01f6082ec61dd45b2@syzkaller.appspotmail.com
Tested-by: syzbot+8785aaf121cfb2141e0d@syzkaller.appspotmail.com
Tested-by: syzbot+2642f347f7309b4880dc@syzkaller.appspotmail.com
Link: https://lore.kernel.org/all/afe041f6-ef7d-4434-b2d0-096be49b5bcb@mail.kernel.org/
Signed-off-by: Uladzislau Zhauniarovich <uladzislau.zhauniarovich@gmail.com>
[jc: exempt txtime-assist, use s64 to keep rejecting negative
 cycle_time, rework commit message]
Signed-off-by: Junjie Cao <junjie.cao@intel.com>
---
 net/sched/sch_taprio.c | 24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)

diff --git a/net/sched/sch_taprio.c b/net/sched/sch_taprio.c
index f3f90c5d2dca..7519bc5c1aff 100644
--- a/net/sched/sch_taprio.c
+++ b/net/sched/sch_taprio.c
@@ -259,6 +259,26 @@ static int length_to_duration(struct taprio_sched *q, int len)
 	return div_u64(len * atomic64_read(&q->picos_per_byte), PSEC_PER_NSEC);
 }
 
+/* Software schedules service one hrtimer expiry per entry; intervals
+ * shorter than the expiry service cost rearm the timer with an expiry
+ * already in the past and storm the CPU. 100us leaves margin above the
+ * measured cost on debug configurations.
+ */
+#define TAPRIO_MIN_SW_INTERVAL_NS	(100 * NSEC_PER_USEC)
+
+static s64 taprio_min_interval(struct taprio_sched *q)
+{
+	s64 min_interval = length_to_duration(q, ETH_ZLEN);
+
+	/* Only pure software schedules arm the per-entry hrtimer. */
+	if (!FULL_OFFLOAD_IS_ENABLED(q->flags) &&
+	    !TXTIME_ASSIST_IS_ENABLED(q->flags))
+		min_interval = max_t(s64, min_interval,
+				     TAPRIO_MIN_SW_INTERVAL_NS);
+
+	return min_interval;
+}
+
 static int duration_to_length(struct taprio_sched *q, u64 duration)
 {
 	return div_u64(duration * PSEC_PER_NSEC, atomic64_read(&q->picos_per_byte));
@@ -1088,7 +1108,7 @@ static int fill_sched_entry(struct taprio_sched *q, struct nlattr **tb,
 			    struct sched_entry *entry,
 			    struct netlink_ext_ack *extack)
 {
-	int min_duration = length_to_duration(q, ETH_ZLEN);
+	s64 min_duration = taprio_min_interval(q);
 	u32 interval = 0;
 
 	if (tb[TCA_TAPRIO_SCHED_ENTRY_CMD])
@@ -1216,7 +1236,7 @@ static int parse_taprio_schedule(struct taprio_sched *q, struct nlattr **tb,
 		new->cycle_time = cycle;
 	}
 
-	if (new->cycle_time < new->num_entries * length_to_duration(q, ETH_ZLEN)) {
+	if (new->cycle_time < (s64)new->num_entries * taprio_min_interval(q)) {
 		NL_SET_ERR_MSG(extack, "'cycle_time' is too small");
 		return -EINVAL;
 	}
-- 
2.43.0

[PATCH net 3/3] selftests/tc-testing: taprio: add case for the software minimum interval

[Junjie Cao]

Entries below TAPRIO_MIN_SW_INTERVAL_NS must be rejected for software
schedules.

Signed-off-by: Junjie Cao <junjie.cao@intel.com>
---
 .../tc-testing/tc-tests/qdiscs/taprio.json    | 22 +++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/tools/testing/selftests/tc-testing/tc-tests/qdiscs/taprio.json b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/taprio.json
index cd19d05925e4..3fe66839f8ae 100644
--- a/tools/testing/selftests/tc-testing/tc-tests/qdiscs/taprio.json
+++ b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/taprio.json
@@ -154,6 +154,28 @@
             "echo \"1\" > /sys/bus/netdevsim/del_device"
         ]
     },
+    {
+        "id": "f4b2",
+        "name": "Add taprio Qdisc with software interval below the minimum",
+        "category": [
+            "qdisc",
+            "taprio"
+        ],
+        "plugins": {
+            "requires": "nsPlugin"
+        },
+        "setup": [
+            "echo \"1 1 8\" > /sys/bus/netdevsim/new_device"
+        ],
+        "cmdUnderTest": "$TC qdisc add dev $ETH root handle 1: taprio num_tc 2 queues 1@0 1@1 sched-entry S 01 50000 sched-entry S 02 50000 clockid CLOCK_TAI",
+        "expExitCode": "2",
+        "verifyCmd": "$TC qdisc show dev $ETH",
+        "matchPattern": "qdisc taprio 1: root refcnt",
+        "matchCount": "0",
+        "teardown": [
+            "echo \"1\" > /sys/bus/netdevsim/del_device"
+        ]
+    },
     {
         "id": "831f",
         "name": "Add taprio Qdisc with too short cycle-time",
-- 
2.43.0