From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from BN8PR05CU002.outbound.protection.outlook.com (mail-eastus2azon11011017.outbound.protection.outlook.com [52.101.57.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 3409A35DA75 for ; Thu, 2 Apr 2026 10:56:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=fail smtp.client-ip=52.101.57.17 ARC-Seal:i=2; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1775127406; cv=fail; b=L7V8jWI4txXO6rlRt0JUwC0oMd3XF66ICUCdzljb0sLVXrk9F46UZc4kniLil+MlUx3FH9XA6/+UD0hgzUM+NRHnvqTKDKoRz65ciPE4vV6FcGvmRVQMW4OEbz2/MHZ4uJ08gqSA/hPAFhZDurxEd4WMHpzb0V/B91NUTByN4c0= ARC-Message-Signature:i=2; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1775127406; c=relaxed/simple; bh=hmxBEELP6trxS6qN406ZKIcS/l315JhhQ+s+rRQ8nVA=; h=Message-ID:Date:MIME-Version:Subject:To:CC:References:From: In-Reply-To:Content-Type; b=g7bG2ojhDupN7CFZixzhTti7KimF88JQLDr4pc5lmRzXCDx4eLKnRlqypdVkVqe9jmGhiu85N6BXC+11Nw4atv4XIdI7IC16vjp0u26rQx1EENQF4mThF5OcQ8ThfzSYPhRszjs7zdJaRotH507LWV6RWBktdVGyHBWvRMxGrFg= ARC-Authentication-Results:i=2; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=amd.com; spf=fail smtp.mailfrom=amd.com; dkim=pass (1024-bit key) header.d=amd.com header.i=@amd.com header.b=C41j5SlO; arc=fail smtp.client-ip=52.101.57.17 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=amd.com Authentication-Results: smtp.subspace.kernel.org; spf=fail smtp.mailfrom=amd.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=amd.com header.i=@amd.com header.b="C41j5SlO" ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=vSxtyqnBIVhoIO2dCaocNeOEQtHpmsq7tLFq/CI2z7rbZRx6JQBVUFRdS0Mh7phUETB/Z6EDB8FicvVRdhIKMRdP+RDMf72wYzT3uG/eSs9tsoaC26LBeNn5JzeEJuB69HMGHd0+liguxi88EpD/tf7qEoV8qy0GKXrx2sHQAoFktkBlIWwBEPyRc2ZueQxIpyG0k3FuqhA+c0W99OA0rBKe0cPpIfzzJIta3MGuKcWN3P126Fn4UvGY8pbvRVJ6+vb2a+Lqb+lLN3nLqV7RH7QOyXkAjfmaax477ZM3x1j2+pAhVY+nDCNPlI4/jyfKUNoYFSGye9gHJg/vpTIy7g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector10001; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=OnEGXmZ9IJpzkO4T5TFAM25Iq3AUzuHR5w//OOORQWk=; b=c1l1sNiiwHBDsKDRl0JDE5HADoGXKbfx0EwPYTxOVSE72+UjhzFSvi3MKMB6v3SZM33YmFbec6m34kuPJZ2GyNbXlXyOvncBVhSgj50cTUUiSRRgN2yLGh465XQ8MvCoXqAUhkB+LGY1QPoS6QXVc14I2EENdzGHehM7gv/A8nxdzhySdnQbhtkx0o136tItdngGkkNM+Ch0z2TunF8hgr0w/DkJ+U2NTNVysxRd+LUz6YzRtf5J0/lcAg/Xfhpy06DAhHOzhxoUJpJMBozd4HIPgURTxo6j2zWVpHGarc9iAQvEcFN0dvKlQkHgyWJp8DpZTuzzriUDfZIp9jzUrw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 165.204.84.17) smtp.rcpttodomain=infradead.org smtp.mailfrom=amd.com; dmarc=pass (p=quarantine sp=quarantine pct=100) action=none header.from=amd.com; dkim=none (message not signed); arc=none (0) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amd.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=OnEGXmZ9IJpzkO4T5TFAM25Iq3AUzuHR5w//OOORQWk=; b=C41j5SlOGK4FTsbaB0fBh1kF4W2nnoBEx9Im4OZrf/fmtwt16Mv2O5Fw4HXZdB+ac90B8RpTodK4V1Nn6UI1LvOCp+amO/Xs0ktMhP7hjrz7X2gcF612guHmq5ZKjAr0t5+M5TfFT0m6IxO0d8jG90T0rOD10v5iKcXoxPce6i4= Received: from BL0PR05CA0024.namprd05.prod.outlook.com (2603:10b6:208:91::34) by CH2PR12MB4295.namprd12.prod.outlook.com (2603:10b6:610:a7::20) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.9769.15; Thu, 2 Apr 2026 10:56:40 +0000 Received: from BL6PEPF00022575.namprd02.prod.outlook.com (2603:10b6:208:91:cafe::c0) by BL0PR05CA0024.outlook.office365.com (2603:10b6:208:91::34) with Microsoft SMTP Server (version=TLS1_3, cipher=TLS_AES_256_GCM_SHA384) id 15.20.9769.16 via Frontend Transport; Thu, 2 Apr 2026 10:56:40 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 165.204.84.17) smtp.mailfrom=amd.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=amd.com; Received-SPF: Pass (protection.outlook.com: domain of amd.com designates 165.204.84.17 as permitted sender) receiver=protection.outlook.com; client-ip=165.204.84.17; helo=satlexmb08.amd.com; pr=C Received: from satlexmb08.amd.com (165.204.84.17) by BL6PEPF00022575.mail.protection.outlook.com (10.167.249.43) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.9769.17 via Frontend Transport; Thu, 2 Apr 2026 10:56:40 +0000 Received: from SATLEXMB04.amd.com (10.181.40.145) by satlexmb08.amd.com (10.181.42.217) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.2.2562.17; Thu, 2 Apr 2026 05:56:39 -0500 Received: from satlexmb08.amd.com (10.181.42.217) by SATLEXMB04.amd.com (10.181.40.145) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2507.39; Thu, 2 Apr 2026 05:56:39 -0500 Received: from [10.136.42.52] (10.180.168.240) by satlexmb08.amd.com (10.181.42.217) with Microsoft SMTP Server id 15.2.2562.17 via Frontend Transport; Thu, 2 Apr 2026 05:56:35 -0500 Message-ID: Date: Thu, 2 Apr 2026 16:26:34 +0530 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime To: Peter Zijlstra CC: Vincent Guittot , , , , , , , , , , , , References: <20260219075840.162631716@infradead.org> <20260219080624.942813440@infradead.org> <20260223115100.GI2995752@noisy.programming.kicks-ass.net> <0d3680c3-3e17-47b8-8fdb-0cc1f97ffce0@amd.com> <99fa12f9-71d3-4766-8742-a3adc9ce4271@amd.com> <20260402102215.GT3738010@noisy.programming.kicks-ass.net> Content-Language: en-US From: K Prateek Nayak In-Reply-To: <20260402102215.GT3738010@noisy.programming.kicks-ass.net> Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit Received-SPF: None (SATLEXMB04.amd.com: kprateek.nayak@amd.com does not designate permitted sender hosts) X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: BL6PEPF00022575:EE_|CH2PR12MB4295:EE_ X-MS-Office365-Filtering-Correlation-Id: d5534544-f303-48e6-d01b-08de90a684e9 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0;ARA:13230040|36860700016|82310400026|1800799024|30052699003|376014|7416014|18002099003|22082099003|56012099003; X-Microsoft-Antispam-Message-Info: E9z48A9FzN60q6+QhROI1ju/A2xzkQavAOAeHsF0TnVi2qKDhJaCMBiGYvHszckxqbfViTFCP39UB/4h9WAvmF0XqHVaOqXD1vQ4mivLU7NNgNvuj/gZGHXN/w8gAS2O5/Dh2sDPzK6uiRaNf5fvqyJrGdyeTvV+Yuk3O3EnCZccI8/xH/vSdcNjCsxTaykjgslbdm1dOnZJLO4KOqRKcpGTKWLbJG5rCLHZAIoiox6MQ2mIhTxJNfRUParOSzmcC9K8RwSyjIGLVizNv69sXPUiBZwlkvLtwNNB293u2sqv6qtadqTy8Vzz2VGjBVWZ5JWG9hEub58es0g/ZMOyVksuV9uT0+MU4nf5UtAGR5t/+Sl7XR54ckXvMBrkXhe6kb2fqROyEMsyFVPHg3cj81SmxWm+llqcoi8FUdXn19Kh4uPfemMxtFljsW/1x+wj7KwvoIcqNev5EDJkQM0K6e4dGFl56rVPIrJjYo//QtS5vPjJP4SX0enTKVD7QYp1Onb10Zo59Zajzsr/2a8pFQYqzqn/cM1XOxnobFE1rFDuBCks/DjRRZAFqlJDBHSrTCuBGFw2Veu+Q6IzKfrr7we4/0uYoEAEc7Pq+jDdkD/YeZV2hMe0DhRmgjfSTra1ppOpnp5KfOY2jtnA76T/S3vnx9YzSiDfzzmTbsy4nZnnbUec8WEjJxI7qJWhZJ0usHSGQNL4nX2sslti/p8CZNc3mC/T3y79nIWjUnvyeRJunkC+mSFA2U3SZjavXfy7CGi7lNB44DSffv07IsnEbg== X-Forefront-Antispam-Report: CIP:165.204.84.17;CTRY:US;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:satlexmb08.amd.com;PTR:InfoDomainNonexistent;CAT:NONE;SFS:(13230040)(36860700016)(82310400026)(1800799024)(30052699003)(376014)(7416014)(18002099003)(22082099003)(56012099003);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: /EkgBZBhcix330qg3HyKpCumZ3bT6QBl/g7fT0i0cPWmwBbyGtlLz/oQt7xvDok/yxJothAq+f0sYGeoo+xZhRSIsIGwWX/6wp10WDNWnZ60kG8SIffRZF2LeMOi3xAFNSsbxGHwdd42MOJ3fl/Wwb/ZfTsvlsd/td4tQjBfZY0Wy9slwXWW3MdeRc6E3zXt5hS7F+mULM7knXcPY3y874OufNBtwNxc+KhXfbCPD8TOFdG+O2znNKF3uzu5kPj6kBF+FQzELMh6n1sHfAUW3pXybm9a4CWfwXiFimRH8Lhc75PJuiC8v1hEmks3DMrMQPJnIrrfV2T1k3G1s/8qr1vBjaMnGOfRVh2IAHHZaE8uTAw35s/aenw8HPy+IQWK8xgYs2MAO0BRMRff8zt/2MnI5xfM2OvlwGrz198EnbzV4XfgtjMzphOTguCU3JEr X-OriginatorOrg: amd.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 02 Apr 2026 10:56:40.1639 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: d5534544-f303-48e6-d01b-08de90a684e9 X-MS-Exchange-CrossTenant-Id: 3dd8961f-e488-4e60-8e11-a82d994e183d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=3dd8961f-e488-4e60-8e11-a82d994e183d;Ip=[165.204.84.17];Helo=[satlexmb08.amd.com] X-MS-Exchange-CrossTenant-AuthSource: BL6PEPF00022575.namprd02.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: CH2PR12MB4295 Hello Peter, On 4/2/2026 3:52 PM, Peter Zijlstra wrote: > On Thu, Apr 02, 2026 at 10:58:18AM +0530, K Prateek Nayak wrote: >> On 3/30/2026 1:25 PM, K Prateek Nayak wrote: >>> ------------[ cut here ]------------ >>> (w_vruntime >> 63) != (w_vruntime >> 62) >>> WARNING: kernel/sched/fair.c:692 at __enqueue_entity+0x382/0x3a0, CPU#5: stress-ng/5062 >> >> Back to this: I still see this with latest set of changes on >> queue:sched/urgent but it doesn't go kaboom. Nonetheless, it suggests we >> are closing in on the s64 limitations of "sum_w_vruntime" which isn't >> very comforting. > > Yeah, we are pushing 64bit pretty hard :/ And if all we would care about > was x86_64 I'd have long since used the fact that imul has a 128bit > result and idiv actually divides 128bit. But even among 64bit > architectures that is somewhat rare :/ Guess we have to make do with what is more abundant. We haven't crashed and burnt yet so it should be a fun debug for future us when we get there :-) > >> Here is one scenario where it was triggered when running: >> >> stress-ng --yield=32 -t 10000000s& >> while true; do perf bench sched messaging -p -t -l 100000 -g 16; done >> >> on a 256CPUs machine after about an hour into the run: >> >> __enqeue_entity: entity_key(-141245081754) weight(90891264) overflow_mul(5608800059305154560) vlag(57498) delayed?(0) >> cfs_rq: zero_vruntime(3809707759657809) sum_w_vruntime(0) sum_weight(0) nr_queued(1) >> cfs_rq->curr: entity_key(0) vruntime(3809707759657809) deadline(3809723966988476) weight(37) >> >> The above comes from __enqueue_entity() after a place_entity(). Breaking >> this down: >> >> vlag_initial = 57498 >> vlag = (57498 * (37 + 90891264)) / 37 = 141,245,081,754 >> >> vruntime = 3809707759657809 - 141245081754 = 3,809,566,514,576,055 >> entity_key(se, cfs_rq) = -141,245,081,754 >> >> Now, multiplying the entity_key with its own weight results to >> 5,608,800,059,305,154,560 (same as what overflow_mul() suggests) but >> in Python, without overflow, this would be: -1,2837,944,014,404,397,056 > > Oh gawd, this is a 'fun' case. > >> One way to avoid the warning entirely would be to pull the zero_vruntime >> close to avg_vruntime is we are enqueuing a very heavy entity. >> >> The correct way to do this would be to compute the actual avg_vruntime() >> and move the zero_vruntime to that point (but that requires at least one >> multiply + divide + update_zero_vruntime()). >> >> One seemingly cheap way by which I've been able to avoid the warning is >> with: >> >> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c >> index 226509231e67..bc708bb8b5d0 100644 >> --- a/kernel/sched/fair.c >> +++ b/kernel/sched/fair.c >> @@ -5329,6 +5329,7 @@ static void >> place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) >> { >> u64 vslice, vruntime = avg_vruntime(cfs_rq); >> + bool update_zero = false; >> s64 lag = 0; >> >> if (!se->custom_slice) >> @@ -5406,6 +5407,17 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) >> load += avg_vruntime_weight(cfs_rq, curr->load.weight); >> >> lag *= load + avg_vruntime_weight(cfs_rq, se->load.weight); >> + /* >> + * If the entity_key() * sum_weight of all the enqueued entities >> + * is more than the sum_w_vruntime, move the zero_vruntime >> + * point to the vruntime of the entity which prevents using >> + * more bits than necessary for sum_w_vruntime until the >> + * next avg_vruntime(). >> + * >> + * XXX: Cheap enough check? >> + */ >> + if (abs(lag) > abs(cfs_rq->sum_w_vruntime)) >> + update_zero = true; >> if (WARN_ON_ONCE(!load)) >> load = 1; >> lag = div64_long(lag, load); >> @@ -5413,6 +5425,9 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) >> >> se->vruntime = vruntime - lag; >> >> + if (update_zero) >> + update_zero_vruntime(cfs_rq, -lag); >> + >> if (sched_feat(PLACE_REL_DEADLINE) && se->rel_deadline) { >> se->deadline += se->vruntime; >> se->rel_deadline = 0; >> --- >> >> But I'm sure it'll make people nervous since we basically move the >> zero_vruntime to se->vruntime. It isn't too bad if: >> >> abs(sum_w_vuntime - (lag * load)) < abs(lag * se->load.weight) >> >> but we already know that the latter overflows so is there any other >> cheaper indicator that we can use to detect the necessity to adjust the >> avg_vruntime beforehand at place_entity()? > > So in general I think it would be fine to move zero_vruntime to the > heaviest entity in the tree. And if there are multiple equal heaviest > weights, any one of them should be fine. > > Per necessity heavy entities are more tightly clustered -- the lag is > inversely proportional to weight, and the spread is proportional to the > lag bound. > > I suspect something simple like comparing the entity weight against the > sum_weight might be enough. If the pre-existing tree is, in aggregate, > heavier than the new element, the avg will not move very drastically. > However, if the new element is (significantly) heavier than the tree, > the avg will move significantly (as demonstrated here). > > That is, something like the below... But with a comment ofc :-) > > Does that make sense? Let me go queue an overnight test to see if I trip that warning or not. I initially did think this might work but then convinced myself that testing the spread with "sum_w_vruntime" might prove to be better but we'll know for sure tomorrow ;-) -- Thanks and Regards, Prateek