From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from BL2PR02CU003.outbound.protection.outlook.com (mail-eastusazon11011067.outbound.protection.outlook.com [52.101.52.67]) (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 10A3A9463 for ; Wed, 29 Apr 2026 05:03:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=fail smtp.client-ip=52.101.52.67 ARC-Seal:i=2; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1777439040; cv=fail; b=aRxVWUUDslqHoR0WJdAocVq4NUIOrz/8Od6f5P+P9OcMpUUypp56YkVhcmu25gRm0btdVNFUT9gW5bRvM22RXargS/q64utxkcssfOsz1s1RomQOIKDNRNjuou6K3/m2HdBynb9tYrJ7+9BpVC9+Hh7TKDXSu5JBxFYv/QCEvD4= ARC-Message-Signature:i=2; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1777439040; c=relaxed/simple; bh=+z8Qmg7tB8/eSR0WJ7ugUEWo5w0C48jJ3vFhHlTPRLY=; h=Message-ID:Date:MIME-Version:Subject:To:CC:References:From: In-Reply-To:Content-Type; b=ayhW7Cs4qRn3e/dJHswqQ8j66sQowTLb3SHFA0Yi6N1MIOAuEYg/DJQhUaM/KzCWZa/290G1iYfHDwJZ2bFyToH6X38SptPiWbhKFQLmCG8s7NiaMMtTo1FuimOHLB344Aa/q1NSIJ2whmFrRARJ+ruJShedgrtiPZV6Ub9ygvI= 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=MfVvN91w; arc=fail smtp.client-ip=52.101.52.67 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="MfVvN91w" ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=T4GfjDq8TgcIlbjP58oaAH4dYTOfB/NRcUexXvzUj8GMogHwolT3clk9Op1E+tOF7PGbPNv0f7CjwJvWFD1RypWVVFYDvVgcXILRHINr8xKB7hDaFG5vJgW6Ho0U8fUCrGU3/CZ7nOYkuLYzF20nCSe+Z/cy2BEx9ng0OqbFR77SeC08sjgsb16Vee1uWbNLB1dBoV31qPMkr2jHuMbRrkzEfyjD0rNt2e/kD8z1/YI0886KWdc2fUSfYLBsdBiUMeZgwFIL8aSR6LREzrGjobj4PKEcw0jLsO54KIAlgAWp6QAj0oHH8RTB5d5T3xVnpT9gTRPebKxq+dO+tWbW3Q== 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=bqSnT0287eiGrR8kJYUgcv9HuwcQ9R6wa07ckkNhxkc=; b=Mapb7mOQSvPxI35QbP72AhWlDlBd4nh4LlKgolfoeVyc7jXb/RqNlWiuYEuFts0zqxyNmjIrVTtUhlkGF39uwrFjmSJc6rCMmfPP7U+yt6Z+a4SUC7Lgob7LVJXDGF/BNcd6LD3PT2za1ANFk8QEbX17bSEUlgmskm7bY+sYx/7nZnwjBXCL7o/922J97tD3e2MWn8my1twJVA6gtT3hFYFBQbsc2J2ZTCPGLb+vU7wLMMkBJwNDxUwEsQOpI5Y2QhVKBhnRWZa/vOxkZS+uQPk8AWHoNmBnWIKHFJQx6w8GFNWY9xz2vCzwGV7qXf9lzIaYpmCEL23TzNCvFEAdUQ== 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=bqSnT0287eiGrR8kJYUgcv9HuwcQ9R6wa07ckkNhxkc=; b=MfVvN91w2pWvoykInmvJ5exO1dKadPZm8vRnjnHFTI9Gurqc0OnJjWzqmEPxIPbd5VVESIGISgw0ebecbobPaqZvHllWFyYn9BTvboSzVSqgV+gvNz7vktk+lUeQfla2fLoWo1UhB/3wbLLB/UBdVSk/dTa79AiF0gOv572Kd8U= Received: from BY5PR20CA0014.namprd20.prod.outlook.com (2603:10b6:a03:1f4::27) by BL1PR12MB5945.namprd12.prod.outlook.com (2603:10b6:208:398::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.9870.18; Wed, 29 Apr 2026 05:03:54 +0000 Received: from SJ1PEPF000023D7.namprd21.prod.outlook.com (2603:10b6:a03:1f4:cafe::df) by BY5PR20CA0014.outlook.office365.com (2603:10b6:a03:1f4::27) with Microsoft SMTP Server (version=TLS1_3, cipher=TLS_AES_256_GCM_SHA384) id 15.20.9846.28 via Frontend Transport; Wed, 29 Apr 2026 05:03:53 +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 SJ1PEPF000023D7.mail.protection.outlook.com (10.167.244.72) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.9891.0 via Frontend Transport; Wed, 29 Apr 2026 05:03:52 +0000 Received: from satlexmb08.amd.com (10.181.42.217) by satlexmb08.amd.com (10.181.42.217) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.2562.17; Wed, 29 Apr 2026 00:03:52 -0500 Received: from [10.136.41.76] (10.180.168.240) by satlexmb08.amd.com (10.181.42.217) with Microsoft SMTP Server id 15.2.2562.17 via Frontend Transport; Wed, 29 Apr 2026 00:03:49 -0500 Message-ID: <4870ea19-78d4-44b2-9f18-14c3f8782726@amd.com> Date: Wed, 29 Apr 2026 10:33:48 +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 RESEND] sched/fair: Fix overflow in vruntime_eligible() To: Peter Zijlstra CC: Zhan Xusheng , Ingo Molnar , Vincent Guittot , Juri Lelli , , Zhan Xusheng , Dietmar Eggemann , Valentin Schneider , Ben Segall , Steven Rostedt , Mel Gorman References: <20260415145742.10359-1-zhanxusheng@xiaomi.com> <20260428144951.121765-1-zhanxusheng@xiaomi.com> <57e94d7e-b8fb-49bc-a914-8a7401e43af3@amd.com> <20260428173521.GK3126523@noisy.programming.kicks-ass.net> Content-Language: en-US From: K Prateek Nayak In-Reply-To: <20260428173521.GK3126523@noisy.programming.kicks-ass.net> Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SJ1PEPF000023D7:EE_|BL1PR12MB5945:EE_ X-MS-Office365-Filtering-Correlation-Id: d8425f10-356d-40f7-738b-08dea5acb574 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0;ARA:13230040|376014|36860700016|7416014|82310400026|1800799024|22082099003|56012099003|18002099003; X-Microsoft-Antispam-Message-Info: 7u7rMo4qN5pKHeO14DmB/XRZXSKR2gc1ZoYUXKsMamdnKec/+I2hi68BcczGQf7jmjuuH3Zvmep2+lIC9BF210qyWAj+a2w/4EaAOvuQRa31K0AzLzl7Hbfhv/d/jETBVlHx6cE4grF4xqG15HbNKU+gktAynts2cuxp44LMZfda23qoniHV2liAPKAhYdWwe2PQP+1QZt4DWJR5C4JdgTf0JhkxD6f5iDZz557doMCFTJWo0rjfVUph1STfGcb9b0S1C0iSgVzNXmP7aTe/zFpd/Zh1i/P5GRNzo8e+e5+bGrghj7qhb24XFXb7X27/sBxlMk5ecTUO/WqreX2icq+QNZXj/N1YvSIa6rT2oFoiTAFMElZppFnB8/QMpH84JfEHqXqg2OdMwdA0s97jnw48HgPL5jMv9sMy1+nfI+xFHXrwzdK4kX8CnnG9JNodQ7g0OwM6170PRvrQ68fOqEwm28HvRxUO9vkCBsc3CproSUX8iS0F9i1TyysN0yXfhkro/SAdZkTVU8M+3IN4FE7HoLhJF9ieSMI8gN+4Z8sEtrtO0Q+ZmsiWcsPUOruKCpZ0iEvpQ+WXgn9dFXLL5mvqW6n8pl7gHcr0fNRCUPp1FZOFFIneUbbcvmh5n+wlpnrbnD1E5Pv7rPbvpOsdRhySuCuziyIa251vCYGtr7zNJZ7w+6EX4yYWBOu6VS1f8LY2TbFGwfXPXIexPpLV1Kop9Hbtg171o+v3U6m2XRL4g8CPTRJPWCQJy5F/LlnzqFDZlj0hEog/WtFwZsne0Q== 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)(376014)(36860700016)(7416014)(82310400026)(1800799024)(22082099003)(56012099003)(18002099003);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: ms3JbiMhGHSE2bZzXFUT6Tx3LlXD2FJfPP45u3mo8xLCBMKa02M64MtOHHOmJZiirh7nXdMIsxoeEEh+vZh6kTfYXnd9wMYudMAJOthLxlhU4cq+z5o5fgArIBNSRfI850Hh2YIYWCckOhEy3Xn+zppR2QQ+xpWuFzFWv3g81xhCPGcW2jtz5jZwrCSb0raY9nwKJU8HiG+dypDC/IilyPZc1jjaO1ZmM6jb0UFRAZLimS/2qJhRDS03X5SpepE3h9s6FO4NhepBDkcJkHI3t6nPv1RbNT571S8WV0JzVbX0/42Cynlm71+gzoah1cZYwiXpEGC+q+ipHYez51+FD7BvUkY9Pj9yf8uQgFcGAIdst/imCd9x3Dz8RXqY1m3tyQtTTt02OPEs0MbJu3wLn42OJPkS0d8m0GBSmUWxxRKGCKKTQybcLEqna3QvwhsK X-OriginatorOrg: amd.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 29 Apr 2026 05:03:52.9642 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: d8425f10-356d-40f7-738b-08dea5acb574 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: SJ1PEPF000023D7.namprd21.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: BL1PR12MB5945 Hello Peter, On 4/28/2026 11:05 PM, Peter Zijlstra wrote: > On Tue, Apr 28, 2026 at 09:47:11PM +0530, K Prateek Nayak wrote: >> (+ scheduler folks) >> >> Hello Zhan, >> >> On 4/28/2026 8:19 PM, Zhan Xusheng wrote: >>> After commit 556146ce5e94 ("sched/fair: Avoid overflow in >>> enqueue_entity()"), place_entity() can shift cfs_rq->zero_vruntime >>> towards a newly enqueued heavy entity. This can make (vruntime - >>> zero_vruntime) very large for other entities and cause key * load in >>> vruntime_eligible() to overflow s64, flipping the eligibility result. >> >> So the commit in question moves the zero_vruntime only when the >> load > sum_weight. >> >> You seem to have found a case where the entity_key() is already large >> enough that moving the zero_vruntime farther will make the eligibility >> check overflow which we were hoping will not be the case. >> >> Do you have a reproducer that fails pick_eevdf() after introduction of >> commit 556146ce5e94? Also, do you see any splats in the dmesg since we >> have a defensive WARN_ON() to catch an overflow. > > Right, either a reproducer or a trace showing the values leading up to > this are the absolute minimum you need to provide. That is, you need a > definite description of how you got there, otherwise you cannot judge > the solution is sound. > > Anyway... let me construct a worst case. > > So if you have this cgroup crap on, then you can have an entity of > weight 2, and vlag should then be bounded by: (slice+TICK_NSEC) * > NICE_0_LOAD, which is around 44 bits as per the comment on entity_key(). > > The other end is 100*NICE_0_LOAD, so lets wake that, then you get: > > {key, weight}[] := { > puny: { (slice + TICK_NSEC) * NICE_0_LOAD, 2 }, > max: { 0, 100*NICE_0_LOAD }, > } So MAX_SHARES is (1UL << 18) and we then scale it up so the weight can can go up to (1 << 28) I suppose in UP setting. So let us assume there is a single task with the largest custom slice on each cgroup making the min_slice equal to 100ms. Things start off in such a way that puny having a vruntime of say -1 is picked over max which had a vruntime of 0 for the sake of simplicity. Deadline then becomes: puny->deadline = -1 + __calc_delta(100ms, NICE_0_LOAD, 2) which is 52428800000000 - 1. At 10HZ tick + RUN_TO_PARITY, we get 10ms error so that puts the entity_key() at 57671680000000 (46 bits) > > The avg_vruntime() would end up being very close to 0 (which is > zero_vruntime), so no real help making that more accurate. > > vruntime_eligible(puny) ends up with: > > avg = 2 * puny.key (+ 0) > weight = 2 + 100 * NICE_0_LOAD > > avg >= puny.key * weight > > And that is: (slice + TICK_NSEC) * NICE_0_LOAD * NICE_0_LOAD * 100 > > and yes, I suppose that can exceed 64bit :-( Then the worst case right side would be: 57671680000000 * load /* load = ((1 << 28) + 2) */ and yes that goes beyond 64-bits at 15481123719086080000000. I'm running with this configurations: echo 2 > /sys/fs/cgroup/cg0/cpu.weight echo 10000 > /sys/fs/cgroup/cg1/cpu.weight Weight of 2 actually gets scaled up to 20480 for UP scenario so I go try to make it even smaller with SMP and wait until it gets picked again. So it goes from ... cfs_rq[0]:/cg0 .se->vruntime : 11602839.678164 .se->deadline : 19092472.390575 .se->sum_exec_runtime : 4243.207300 .se->slice : 100.000000 .se->custom_slice : 1 .se->load.weight : 14 .se->avg.load_avg : 2 .se->avg.util_avg : 0 .se->avg.runnable_avg : 1024 cfs_rq[0]:/cg1 .se->vruntime : 11602835.026387 .se->deadline : 11602835.706227 .se->sum_exec_runtime : 2646719.706164 .se->slice : 100.000000 .se->custom_slice : 1 .se->load.weight : 104857600 .se->avg.load_avg : 102389 .se->avg.util_avg : 1024 .se->avg.runnable_avg : 1024 cfs_rq[0]:/ .left_deadline : 19092472.390575 .left_vruntime : 11602839.678164 .zero_vruntime : 11602835.026387 .sum_w_vruntime : 65124878 (25 bits) .sum_weight : 14 .sum_shift : 0 .avg_vruntime : 11602835.026387 .right_vruntime : 11602839.678164 .spread : 0.000000 ... to ... cfs_rq[0]:/cg0 .se->vruntime : 19392969.031442 .se->deadline : 26881950.428361 .se->sum_exec_runtime : 4347.216748 .se->slice : 100.000000 .se->custom_slice : 1 .se->load.weight : 14 .se->avg.load_avg : 1 .se->avg.util_avg : 904 .se->avg.runnable_avg : 1024 cfs_rq[0]:/cg1 .se->vruntime : 11602851.024250 .se->deadline : 11602851.144214 .se->sum_exec_runtime : 2648319.534241 .se->slice : 100.000000 .se->custom_slice : 1 .se->load.weight : 104857600 .se->avg.load_avg : 102386 .se->avg.util_avg : 1024 .se->avg.runnable_avg : 1024 cfs_rq[0]:/ .left_deadline : 26881950.428361 .left_vruntime : 19392969.031442 .zero_vruntime : 11602852.064342 .sum_w_vruntime : 109061637539400 (46 bits) .sum_weight : 14 .sum_shift : 0 .avg_vruntime : 11602852.064342 .right_vruntime : 19392969.031442 .spread : 0.000000 without any splat so I'm not sure if there is something that prevents a possible crash since a weight of 104857600 should have definitely made that entity_key() overflow. > > Can someone double check that? I have a silly head-ache and could easily > have made mistake. Not sure what the best solution is either. I think we > can show avg cannot overflow, and if this multiplication overflows, then > it must be larger, so perhaps the proposed patch is the best option. > > Dunno, need clear head :/ -- Thanks and Regards, Prateek