From nobody Mon Jun 8 04:19:37 2026 Received: from mail-pj1-f67.google.com (mail-pj1-f67.google.com [209.85.216.67]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 34AA13921D5 for ; Tue, 2 Jun 2026 05:46:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.67 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1780379191; cv=none; b=KaFWLqhGm+M4PP4zLKWwcmSjvSry0jldYs4g8VYlpfnQ/GpidRRME4fHyCqi7WV9NiPGoH46m6A0zd88elHqSenmBJktmT/1cK8XLl0rX4OEsTmRqQOlHeZFWzMCqQR3E5DZ8fH1rgTqkUwXuqnScTx0+tkoq6lJu0ATx7hxRBM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1780379191; c=relaxed/simple; bh=tIQg7MmRcDlQ+sHJq3ThoCDuLSvQQQEc14bhZNMYoZg=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version:Content-Type; b=ZKTCIoIuZVG6a2YBZJUqnb2d9XwRvPCBmUKUEbaHTSanlclScX+/DUpSB0ywQR6sbCVKzRkYnJ7YEnrizaoDuPQyvRagqXBLDfMyhtvWF/+Cm2CB6wh4sV5/VvGQHlPIMBby6l7JetHkwddutVU6GJBfxxWLWroZNiO4eV2r2I0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=qkhFPdjR; arc=none smtp.client-ip=209.85.216.67 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="qkhFPdjR" Received: by mail-pj1-f67.google.com with SMTP id 98e67ed59e1d1-36d9794d82aso1263441a91.0 for ; Mon, 01 Jun 2026 22:46:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1780379189; x=1780983989; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=90e0XlAJTc+JFyPbIMvRlYdkbDz3T32xXOZVRvtYWrs=; b=qkhFPdjRMG6NiU+pMyEAqp8DVLa46CkUP5e1rkOi8wXSM6Bi3EQz4qp6osObT5ERuv 6xJQBofJNSGUdZ+kInYt5QxpaUAyFreCDrZXCP9y5lHSe4Y5AML0ar2rfxGUvYENg9Sm 5wRQZvnlzKA6Ts0OWC18z4RmXIWh1TIzcz3yexikvE7O1YiClGOgR1KS1cb8xBB6jzSq AND2lh+5nZzNo5s5HfVZnV/dGOQACxkjh8hUu9mJJ+R97aS+dFOWaG2Zx0t0/dr03A2n bMRQ4HQfgWFG55tvf9g/2+xQ1nbOoYgS5JTmr5AZMApJf5AIicL6Y0lQP6yVQnIr2B3h PRzg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1780379189; x=1780983989; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=90e0XlAJTc+JFyPbIMvRlYdkbDz3T32xXOZVRvtYWrs=; b=I+E7WTkkTc9YIlNCDrItvDGj0dAktlTec4A9qYZcXxjElBPTQLbhGja14SZ+2I1UZZ x3YnwKukDW+qJoNs4UJm0T/owU7FXXojYs8oEp06QKYfFnNumjPhmHZLv9lmoAi7MAKH 9CXhXPu+oW1+WiAy4xjrd/B1hYYj/Ktij/UJAaHOlWbINj3igXyQAKaUHVjpCzwE4o1n mH2dRBzP8hixwg0BH1PkRf0r/CqWTRK6mWtak1zENEXNNrzprEWI+eU7zNXjIaFE6QyI vRXF8ixBRfUJA6hn3EVJ2mOVoxMYpt4/XYcIpB2n5/uJeuzSjitiC/PYh8sKlNKl1JpI GUcQ== X-Gm-Message-State: AOJu0Yys/p9sresSWAkeR267hNkGhcOGG1xCZ5DxQBWId3r+2UeziGVb 3SJGOJm1y2tQHlqCugpkP5HwGTNw0ORYAqOjh7t0aZKb0rJ2WkanQNqM X-Gm-Gg: Acq92OHLKfkUI1uj/9TrKiwX79KiH/rjOpSItey23tdeYS7ttoxxZbKHN7HtV/eP8M3 yM0yPMRKSrYJuTBRHzDmLz6HVvDrDdJotddH0UbSTvaIRp492BQup5E5XRdSwcRcPrSHmrEh4qL s81Nrj6R8p0JLk/Huslkijv0L5i74OeHH+WlH0kzcKy/eAxyhR9jUUcTqOMuoI8mRMhUFZ3Amju QhBVtHF8RHRCLrIOvAkNTDD5OIzXomdzxSvla6NBpBLifgsI3bf14MjFlxCZn0O2feenrhyHCuX l0SVCdMENbsyC2ivxURN2pccZTRJQDlXP89iqnY/YqUmhirQSvQWyL5p25nu2HHEKwHUFgqavDr n2CVCrG4jjAP89lTxHF3VkrcDw73DYuoCc0ke/jyABoKnORzpsZljT5lREsAy4SMJao5Zh/z47D DvqXl34MbX7estgpEVYORHmrcxfRGnyzuYg1LUWDBW8r7VcnXubZOtHZjPqJeN+pqGeTOjGVw= X-Received: by 2002:a17:90b:590d:b0:36b:b3f4:d574 with SMTP id 98e67ed59e1d1-36c68482266mr13713442a91.25.1780379189393; Mon, 01 Jun 2026 22:46:29 -0700 (PDT) Received: from lima-ubuntu.hz.ali.com ([47.246.98.221]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-36dd9183368sm1452483a91.3.2026.06.01.22.46.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 01 Jun 2026 22:46:28 -0700 (PDT) From: Qing Wang To: bsegall@google.com, chenl311@chinatelecom.cn, dietmar.eggemann@arm.com, juri.lelli@redhat.com, kprateek.nayak@amd.com, mgorman@suse.de, mingo@redhat.com, peterz@infradead.org, rostedt@goodmis.org, vincent.guittot@linaro.org, vschneid@redhat.com Cc: linux-kernel@vger.kernel.org, Qing Wang Subject: [PATCH v2] sched/fair: Replace random newidle_balance with Bresenham accumulator Date: Tue, 2 Jun 2026 13:46:19 +0800 Message-Id: <20260602054619.637201-1-wangqing7171@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20260506024455.2799069-1-wangqing7171@gmail.com> References: <20260506024455.2799069-1-wangqing7171@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable The current NI_RANDOM implementation uses a random dice roll to allow newidle_balance attempts according to the success rate. There is a better way to implememte it. Replace the random dice with a Bresenham accumulator that distributes the allowed attempts with uniformly spaced evenly across a 1024-step window: Each step do those: - Accumulate (1 + newidle_ratio) into newidle_window_pos. - If the accumulator reaches 1024, allow the balance attempt and subtract 1024. This guarantees exactly (1 + newidle_ratio) newidle_balance per 1024 steps and per newidle_balance with uniformly spaced for any ratio in [0, 1023]. Signed-off-by: Qing Wang --- V2: 1. Remove sched_rnd_state and sched_rng() since they are no longer used. include/linux/sched/topology.h | 1 + kernel/sched/core.c | 3 --- kernel/sched/fair.c | 18 +++++++++++++----- kernel/sched/sched.h | 6 ------ kernel/sched/topology.c | 1 + 5 files changed, 15 insertions(+), 14 deletions(-) diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h index 36553e14866d..fd6de240fb2b 100644 --- a/include/linux/sched/topology.h +++ b/include/linux/sched/topology.h @@ -95,6 +95,7 @@ struct sched_domain { unsigned int newidle_call; unsigned int newidle_success; unsigned int newidle_ratio; + unsigned int newidle_window_pos; u64 newidle_stamp; u64 max_newidle_lb_cost; unsigned long last_decay_max_lb_cost; diff --git a/kernel/sched/core.c b/kernel/sched/core.c index b8871449d3c6..4c0f613326d4 100644 --- a/kernel/sched/core.c +++ b/kernel/sched/core.c @@ -129,7 +129,6 @@ EXPORT_TRACEPOINT_SYMBOL_GPL(sched_dl_server_start_tp); EXPORT_TRACEPOINT_SYMBOL_GPL(sched_dl_server_stop_tp); =20 DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues); -DEFINE_PER_CPU(struct rnd_state, sched_rnd_state); =20 #ifdef CONFIG_SCHED_PROXY_EXEC DEFINE_STATIC_KEY_TRUE(__sched_proxy_exec); @@ -8820,8 +8819,6 @@ void __init sched_init_smp(void) { sched_init_numa(NUMA_NO_NODE); =20 - prandom_init_once(&sched_rnd_state); - /* * There's no userspace yet to cause hotplug operations; hence all the * CPU masks are stable and all blatant races in the below code cannot diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 3ebec186f982..c48f092dc5d4 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -12545,6 +12545,7 @@ static inline void update_newidle_stats(struct sche= d_domain *sd, unsigned int su ratio +=3D sd->newidle_success; =20 sd->newidle_ratio =3D min(1024, ratio); + sd->newidle_window_pos =3D 0; sd->newidle_call /=3D 2; sd->newidle_success /=3D 2; } @@ -13253,16 +13254,23 @@ static int sched_balance_newidle(struct rq *this_= rq, struct rq_flags *rf) =20 if (sched_feat(NI_RANDOM) && sd->newidle_ratio < 1024) { /* - * Throw a 1k sided dice; and only run - * newidle_balance according to the success - * rate. + * Base on accumulator of Bresenham's line algorithm + * + * Accumulate ratio each time and trigger balance + * when sum =E2=89=A5 1024. + * + * Ensures exactly ratio balances per 1024 calls + * and distributes ratio balance operations uniformly + * across every 1024 invocations. */ - u32 d1k =3D sched_rng() % 1024; weight =3D 1 + sd->newidle_ratio; - if (d1k > weight) { + + sd->newidle_window_pos +=3D weight; + if (sd->newidle_window_pos < 1024) { update_newidle_stats(sd, 0); continue; } + sd->newidle_window_pos -=3D 1024; weight =3D (1024 + weight/2) / weight; } =20 diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index 9f63b15d309d..b407835ae9a8 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -1384,12 +1384,6 @@ static inline bool is_migration_disabled(struct task= _struct *p) } =20 DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues); -DECLARE_PER_CPU(struct rnd_state, sched_rnd_state); - -static inline u32 sched_rng(void) -{ - return prandom_u32_state(this_cpu_ptr(&sched_rnd_state)); -} =20 static __always_inline struct rq *__this_rq(void) { diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c index 5847b83d9d55..0d8fa413f66c 100644 --- a/kernel/sched/topology.c +++ b/kernel/sched/topology.c @@ -1708,6 +1708,7 @@ sd_init(struct sched_domain_topology_level *tl, .newidle_call =3D 512, .newidle_success =3D 256, .newidle_ratio =3D 512, + .newidle_window_pos =3D 0, .newidle_stamp =3D now, =20 .max_newidle_lb_cost =3D 0, --=20 2.34.1