Date:   Tue, 21 Mar 2023 21:58:13 +0800
From:   Chen Yu <yu.c.chen@intel.com>
To:     Peter Zijlstra <peterz@infradead.org>
CC:     <mingo@kernel.org>, <vincent.guittot@linaro.org>,
        <linux-kernel@vger.kernel.org>, <juri.lelli@redhat.com>,
        <dietmar.eggemann@arm.com>, <rostedt@goodmis.org>,
        <bsegall@google.com>, <mgorman@suse.de>, <bristot@redhat.com>,
        <corbet@lwn.net>, <qyousef@layalina.io>, <chris.hyser@oracle.com>,
        <patrick.bellasi@matbug.net>, <pjt@google.com>, <pavel@ucw.cz>,
        <qperret@google.com>, <tim.c.chen@linux.intel.com>,
        <joshdon@google.com>, <timj@gnu.org>, <kprateek.nayak@amd.com>,
        <youssefesmat@chromium.org>, <joel@joelfernandes.org>
Subject: Re: [PATCH 06/10] sched/fair: Add avg_vruntime
Message-ID: <ZBm39VNJCwioq+V4@chenyu5-mobl1>
References: <20230306132521.968182689@infradead.org>
 <20230306141502.569748782@infradead.org>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <20230306141502.569748782@infradead.org>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?xe7B8M3nDl04BIuj8h5nu3ztmSFORc035J2CLONy0gxAAIumkEJUYu9G9u0S?=
 =?us-ascii?Q?Jzc17L5POMSoQ58jRPI/0mrpfNGvQfZ4EYIrVcKqoO8bSZr+KX48p/1b/fLj?=
 =?us-ascii?Q?/716C/QJh4o1YZjjNR9jAIhhbaylBe4rPF4QI+Ps3khQYDPPe5s6yARAP7oP?=
 =?us-ascii?Q?23Jrvnh6ybirDlUJBFFrJpikWGIN9OnBDGk4MaVRAqbrknVDD+vtKPn9TTNI?=
 =?us-ascii?Q?F5OPM4AILYoxIlSOFlCg6aYX7zj4Wv4LcAN7egfdL5hA1X4QxIQeuY5b42M7?=
 =?us-ascii?Q?hH2nIq5wx3w4fA8pzdaQkfMBtRgwQm/7iCORNDG6FHgH+AnwSl5iYb1PD0Uu?=
 =?us-ascii?Q?SDj6HOQ8SVjlMGXCXJGu1/eJWr9YR9Xhx4wpjbo3tNtyjG3lLEovBxUp5L0i?=
 =?us-ascii?Q?xDJHch3knkgCa14/1e49qeG3GnzwLYuB1P8Y6RZ5aNHwbuL51AJPRCPdpiyO?=
 =?us-ascii?Q?k9oyc0GdMBSizTveTk1s/fNWCCLqIG6dhiqW/TQmHJqfHHBs5yJwxO3ZEfm1?=
 =?us-ascii?Q?kxKncfPgc0rcDoLuitooG7tj2gFTEOrLTgIrqRFLbz6L9k3qWQ/1aRVEVr/F?=
 =?us-ascii?Q?h05+0b/yCwJD9z8gI+kHtQrbQ8EZKsV8X888QMwmc9nLMG70I9WLPfz3Yoi9?=
 =?us-ascii?Q?X0eHxR5aOGueUlqAmPHTmkGJpU/6mBPcJRoJcZ9E3J4iadwPPZTPMK6qeybX?=
 =?us-ascii?Q?ijl3NXsDBJCA3g5DbmVeAktWlTajzoDBGETDSLIOg68Xua35bU0UujvNu8bX?=
 =?us-ascii?Q?NpRm2p+ziowfRzvOG1DeHcfGZFxiWTCdadCRx/760qtgtTIJdmgb5PnCivVN?=
 =?us-ascii?Q?g+Mq7pFCQVBTtmQDjxVJnMys9NfAUcA9pSG7ucLVjHnOnqAHpYzP2YVzC38c?=
 =?us-ascii?Q?xln7Il+rnYiiJQJIJZ4aO0wn24pQM8rP7cTfYVAKoCLmeIUtVkmndaH0aXYd?=
 =?us-ascii?Q?mYJiwxvSqFoQhTebgRM7Q747ZjppgkPiG2qyqKvjz2TtfQuzD5nZxtlCdCh2?=
 =?us-ascii?Q?tSnk2+WX0UdBoVMt518E+gzdzx4h9k9Uvxq86T8BupXf7u7G2XyI1EXEM/gs?=
 =?us-ascii?Q?890HRsuxmNAwpsqnQpxYlBlCOvYzpdlGQkwbzfHvjuPs77K2s5B/fIjEroLy?=
 =?us-ascii?Q?ze1XQC024NKItr/AeoWF3RJ+GIUbqJ6zWVISXsxT6NF0Z8fUHdQb9Cyr7dmB?=
 =?us-ascii?Q?u2bivgSa6F6GdIDR/NfEPNnmdrf+WyWoj4JCciPFGIyHQpOfvoz+mtMtoGWI?=
 =?us-ascii?Q?FPVGnRupMIw912SIEXRRjl/mktuT2BjbswIBEzjmKTUDzwfprnjYgJjEH5J9?=
 =?us-ascii?Q?L/iNLzuDtz82Y/eIf1qKHLidHGjTBnqN6siaEuYKHfA9Xu3dAFEJ7SjV3wwp?=
 =?us-ascii?Q?T4fZbUhzL6NxJxJX3v16AcUrE6ZwuqZSMKhpYXnu7TeFACwiZGRmZIQKim5h?=
 =?us-ascii?Q?kckMziH/I+IA2tbq0WEvDWHwqJ3Rm4j2kw/RCH8fMPUDspBlQ64GXIRnLLPc?=
 =?us-ascii?Q?4EpQ/1tmNyDm3uulAuF7Zu6IEYOb8ktZqiNabvkYxJ4gOm7PojRLS9MxJfmv?=
 =?us-ascii?Q?nasIhp8cRBcmnS0/NLV25eN+/wq2KmnFsEqdXGOu?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 43a3a5a3-2abe-42b0-bd48-08db2a145d5d
X-MS-Exchange-CrossTenant-AuthSource: MN0PR11MB6206.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 21 Mar 2023 13:58:36.1395
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: vIlvSHS+P4fMVMkeLXBRz4VFdejAHZqM9InCg4mDyZUBMRczLEms4XrMzBGTy4TjFoq+nq6/U48uV1nHK1MAIw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH7PR11MB7549
X-OriginatorOrg: intel.com
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

On 2023-03-06 at 14:25:27 +0100, Peter Zijlstra wrote:
[...]
>  
> +/*
> + * Compute virtual time from the per-task service numbers:
> + *
> + * Fair schedulers conserve lag: \Sum lag_i = 0
> + *
> + * lag_i = S - s_i = w_i * (V - v_i)
> + *
The definination of above lag_i seems to be inconsistent with the defininatin
of se->lag in PATCH 8. Maybe rename lag_i to something other to avoid confusion?
> + * \Sum lag_i = 0 -> \Sum w_i * (V - v_i) = V * \Sum w_i - \Sum w_i * v_i = 0
> + *
> + * From which we solve V:
> + *
> + *     \Sum v_i * w_i
> + * V = --------------
> + *        \Sum w_i
> + *
> + * However, since v_i is u64, and the multiplcation could easily overflow
> + * transform it into a relative form that uses smaller quantities:
> + *
> + * Substitute: v_i == (v_i - v) + v
> + *
> + *     \Sum ((v_i - v) + v) * w_i   \Sum (v_i - v) * w_i
> + * V = -------------------------- = -------------------- + v
> + *              \Sum w_i                   \Sum w_i
> + *
> + *
Not sure if I understand it correctly, does it mean  (v_i - v) * w_i will not
overflow? If the weight of task is 15 (nice 19), then if v_i - v > (S64_MAX / 15)
it gets overflow. Is it possible that v_i is much larger than cfs_rq->min_vruntime
in this case?

thanks,
Chenyu