From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pj1-f66.google.com (mail-pj1-f66.google.com [209.85.216.66]) (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 8FD8A21D3E2 for ; Wed, 6 May 2026 02:45:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.66 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778035509; cv=none; b=PfJkaiXiNAJZ79q3FM7UDNu54Hz4VL8uajaHKeCOyqmjKKA1d4vVx3edZAEyDcZdmpggL5vCE6rH7q8n4HOlHX386QCvPEk+EkFyTheO6zAyQuu2otnKjejThuAOniyabEeJ8DPbV5JPLFrpzqQaNRDdOtCQUSD4B3uakrXBa40= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778035509; c=relaxed/simple; bh=Kz49k8fNBTPvV6OBwLokqk+/PneQHdOVNMqfqx9PEsE=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version:Content-Type; b=A+IdJa/esbyTBNyyvpbCGhfT3E/zEkISA8ChMT5OSIJ+FDWrt+kllz8QATOgEgMUjvxW9n81Ab107Kq6l1HPFt3UABMBZ4iiSkFQFfEQInorpaE1CgbVoKQHYD5pR02mxuUHmS/2z2nJT735ydHi1HE/06YAFL23na/plBhUzk8= 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=BxlL3Zn0; arc=none smtp.client-ip=209.85.216.66 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="BxlL3Zn0" Received: by mail-pj1-f66.google.com with SMTP id 98e67ed59e1d1-3652546e41aso2202484a91.1 for ; Tue, 05 May 2026 19:45:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1778035507; x=1778640307; 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=8IW0cioHiu/aXRWAvt9mmk8zh136itu+lJCBi/PObUU=; b=BxlL3Zn04jtOi++dY3CBKE9f3Jgk4uoa8OpZPGt3eQe4sVi10ravCuWcYNwBjnfZyT l4ufKIognzMqHFfP47th7umKd7YiZm/AMb2B1JkkdL2joMiKMcx/YhCdnw+gJWYa9WBu Sy4hXA3Ssx0Jwsf56cy1y9Q+QC83Pdy8JPley855Ly64scboJ/lmKCRArJdCwPDXknbr QZxK+cXnm5dyvcX5inXk2f/ewlAco3W8UdqCZALex/7YXfrUdU3tQjW1F6ziw7PXfWqv ZkTcusCWMPucrQQrsjVRwqoZ+rZ72JLiTA6qAeZ0vi/zYW3i3wuuh/yev59ByP6WWNM/ stiA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1778035507; x=1778640307; 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=8IW0cioHiu/aXRWAvt9mmk8zh136itu+lJCBi/PObUU=; b=ateLNZ1Rky76vx+C67YwxNkx6DSBDRrb83WZ9pJi+lrQ/QyWemmrpnV/s84JBGHMTL RPGwOuEZ1j9YEWfftz2gkWfjZkDr9mVW1a0MbFkefrhM5xxbv7s0rFU3HUp2qeZpkZ4D TFKLZnwQKnSM66T19Myy4clYoFG1ij9Th0VDGjc9C2UhPxMVcJ9ilb/1oWraOsT4jnci lYV2RVDV+N07XBBjguSwWsn9jY2P177/AMv8hYdFYL2snWaPN1JkvW/nXaXJ3mzJ0Aff ZX5eZt+lGrLpY+bd2N4wB/oWnhVntC9Pq11vcqRp5MdfutUVn7W/HAHRSs6EXCMqfN3B Akzw== X-Forwarded-Encrypted: i=1; AFNElJ/Xc81HLTQD9RN9lT8m/U01/FKsL2uQ0ZTC6OgyQSdFErd/1tKTmgRqutE93B6IX+SHwRtvPwIYTfHHsj0=@vger.kernel.org X-Gm-Message-State: AOJu0YzvdaK8S+SE2xuJSwKA1CyktAK6nS+1b6b3gBjEDtShh1sm12Xr OOxzFhgcTw72Wv6a6WNq28hEQFw/R3fIObZVoIIH/f0opMYVBi4byLRw X-Gm-Gg: AeBDieulmZktswlP/B+guUyzk2mxMNx4HglICAGYz4rxWAkv/FEWJKG901Zww/I25tq QgqNcPjHqUC6iinKEUzX5uko1aV4oijN8bclLQ79OHznmW5pp41nzMEKZitNtC14RnkKPf/3rnq gSkISWapT+AYiD1xrEE6szh0f4HA70GqXTFDq8j1h5sFPzTDx8t2jnps0Z61IyAV0RqPQHONTYY sHYDhPLZLQUWNwlG1OGlKeco787HD3xPrELeOO2y4vGup4ET8q3oCvNzH6WUI6ztVKr982AOXVc ImaX9af7rtg87AAXs1AZ7s5YlRGrJIt9uhpT7n+PQewLD8kY3h+9vE46T7E2MQrA7QH2Q/0Cn11 QkTMTZAJVSMBg13Imbms101OOH8Wz6zwnn+alMB0F/kRaQK9p7lzZfLdnXt8UE+1nOAb7uPE4XA I7hrnj4QwTik33FhD21FXJUBMnxWpElQzqgyXT4BKKU9eUaonkizrBxHFBmCBh X-Received: by 2002:a17:90b:1b4b:b0:35f:c1e1:a263 with SMTP id 98e67ed59e1d1-365ac27a3bbmr1342375a91.19.1778035506684; Tue, 05 May 2026 19:45:06 -0700 (PDT) Received: from lima-ubuntu.hz.ali.com ([47.246.98.218]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-365b4fb36f4sm409444a91.13.2026.05.05.19.45.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 05 May 2026 19:45:06 -0700 (PDT) From: Qing Wang To: Ingo Molnar , Peter Zijlstra , Juri Lelli , Vincent Guittot , Dietmar Eggemann , Steven Rostedt , Ben Segall , Mel Gorman , Valentin Schneider , K Prateek Nayak , Li Chen , linux-kernel@vger.kernel.org Cc: Qing Wang Subject: [PATCH] sched/fair: Replace random newidle_balance with Bresenham accumulator Date: Wed, 6 May 2026 10:44:55 +0800 Message-Id: <20260506024455.2799069-1-wangqing7171@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20260429085147.1029505-1-wangqing7171@gmail.com> References: <20260429085147.1029505-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: 8bit 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 --- include/linux/sched/topology.h | 1 + kernel/sched/fair.c | 18 +++++++++++++----- kernel/sched/topology.c | 1 + 3 files changed, 15 insertions(+), 5 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/fair.c b/kernel/sched/fair.c index 69361c63353a..7874f795f62d 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -12509,6 +12509,7 @@ static inline void update_newidle_stats(struct sched_domain *sd, unsigned int su ratio += sd->newidle_success; sd->newidle_ratio = min(1024, ratio); + sd->newidle_window_pos = 0; sd->newidle_call /= 2; sd->newidle_success /= 2; } @@ -13217,16 +13218,23 @@ static int sched_balance_newidle(struct rq *this_rq, struct rq_flags *rf) 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 ≥ 1024. + * + * Ensures exactly ratio balances per 1024 calls + * and distributes ratio balance operations uniformly + * across every 1024 invocations. */ - u32 d1k = sched_rng() % 1024; weight = 1 + sd->newidle_ratio; - if (d1k > weight) { + + sd->newidle_window_pos += weight; + if (sd->newidle_window_pos < 1024) { update_newidle_stats(sd, 0); continue; } + sd->newidle_window_pos -= 1024; weight = (1024 + weight/2) / weight; } 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 = 512, .newidle_success = 256, .newidle_ratio = 512, + .newidle_window_pos = 0, .newidle_stamp = now, .max_newidle_lb_cost = 0, -- 2.34.1