Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Fri, 24 Mar 2023 15:12:19 +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: <ZB1NU1Yc8DSi4zrW@chenyu5-mobl1>
References: <20230306132521.968182689@infradead.org>
 <20230306141502.569748782@infradead.org>
 <ZBm39VNJCwioq+V4@chenyu5-mobl1>
 <20230321160458.GB2273492@hirez.programming.kicks-ass.net>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <20230321160458.GB2273492@hirez.programming.kicks-ass.net>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?WvRL5FlV9hWae6QSCl7A3uCeodoAnxE9QSolnnWSwUP4aNzBHZrxOL27k58m?=
 =?us-ascii?Q?uSFdUICEsiQUYk8Xqkk24Ek4O+cJaFe5Y3+qydgtQXwDWVsKvsJvJhuxgs/k?=
 =?us-ascii?Q?K9jzXNh4kwP4eKB7k2Nb+DvpRuRrXFlEQdHIH+DtPOdsZLDy3CV+UHGcjqa+?=
 =?us-ascii?Q?ocH+xHVWojRWiQcigkyKc5HCl0L7QdkAT8dJOw4JyJ6DuaGerZBFcF6DVNiO?=
 =?us-ascii?Q?/HhTFDJGv/u9Pj4n9eLsd5EMT95K6yViu4ZVjNVXEmzrM/chUlX29fIuEL5w?=
 =?us-ascii?Q?K9VNlq+JZ0ruzpki0q9pt8To/a4Md1XFGAllMk7GMs9U3HR5a4EDvH5Mneg+?=
 =?us-ascii?Q?SLpbqpqQwJ27vqkE8iaAGFvrqZG1eUwLJFU47qyCTUD4sJSXE/mGOUQM0KxL?=
 =?us-ascii?Q?ZgPsdAHO6Ga+7XtNL3mrnIf3EEDs20uvQm87Wp27eybLtWxhFT0d/F9t8jWr?=
 =?us-ascii?Q?KOIF/3/shKo2vjcUXzeFAVwVidR7wploMxPCOukUlELT6ivazofocdc8tU+7?=
 =?us-ascii?Q?2lMJRC87bHwvkuZauvDfakdlHTf78tXKIaTm1YPB9FiQg049nfmpVQ4QpKcJ?=
 =?us-ascii?Q?gNo/AxiQa2x6S3zyasSMIvc4tzHKH8iSEirDNDKvmua8efNMgueCw7c7E27Q?=
 =?us-ascii?Q?dkooymNRjjsMh1jcDLyODFudeii8IK2bKkkOMfbFKLCZy+OQQruTowI81Y9o?=
 =?us-ascii?Q?0hBjNZiXIQNDT+Iey+YQkDndJlalgPCc27wohWNJXTTQ8RuAP0tEh3a7V+Lm?=
 =?us-ascii?Q?wo1tmWNXEJP0IKwLbLPOSfYPBl/cKH1A7UPfNN//wyeNgNQoJsQJKZHmwKWA?=
 =?us-ascii?Q?6biv6sctdXWMc0utMrwFI9ajF+U8S9C9tmgHaMcr6hKIfyKokvmP5GU9M6g5?=
 =?us-ascii?Q?yo/OeoCvS3HNBBxVO4gF918oucQuhDSgYpBfPvLpe7FODTXYygEevNRVFRXY?=
 =?us-ascii?Q?+0dTN7PvQB6Rdhmd2JzZtuInMedhQH5xnY7BIc1yzEkqNEOOZwxKtZm/2/gC?=
 =?us-ascii?Q?j9wYgtdJRY3Z0EbqzlCy25Tm+4clGAYP580/zu+SsCkyJANbcRHHTPepOEtJ?=
 =?us-ascii?Q?3NOikqxhoUQPR5/AFyE5Qt+zzOwyMraMxciW7n4emFCPmkDBUFBWBfOyr2QK?=
 =?us-ascii?Q?WzHjJfzWBVSLngjUZG/XgQ0KSa/QheSnzMMZYMh2FgYWW2GP9LFjmtXHE9qd?=
 =?us-ascii?Q?fIjte+hs2GTXPmodbjNsbXbt/Se1zPyMcka7dMSb4rDowl/6TiyEkCufJ9mC?=
 =?us-ascii?Q?ZpqaNxvy87JXXhrcEdR1+zsR7aGWRKJNdTj2/I5cXC4muCqpisaxgUc21Avk?=
 =?us-ascii?Q?pQamtmzz2cqw32W5vdCXQLD9P6rY1e5ClzmVOa83bUumYQRX3hYTf4rVLmm2?=
 =?us-ascii?Q?Vwm88XwaxiG0y7PTs5RHg8inpJCpMU4Gu1DGa2WrBgexKgRCEO//4SG7I5eH?=
 =?us-ascii?Q?SYmjfEwf/tdf67CbPr9nD3YNyUwGko6s/sqWSdcGZG1zEMskwWBS9iNynsjz?=
 =?us-ascii?Q?BOF5lvqUJp9WxO3N3MSxRkAFceRTKXsaV0Qf5mkAr5kVATLVXqTOtCFPejXZ?=
 =?us-ascii?Q?cjCVKs8YUMPRaN4dlH9HRxKZ31gHNsEAzdZcokQg?=
X-MS-Exchange-CrossTenant-Network-Message-Id: a96705f1-da81-4a13-1d87-08db2c372995
X-MS-Exchange-CrossTenant-AuthSource: MN0PR11MB6206.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 24 Mar 2023 07:12:43.8642
 (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: E9NPyvmATjA8Tn3MCkEzywGpgs/sbBhuUXyCIPwVNZWGiM0cQnhIXCIdoSet1/veZ5elAnfspNqxdz2H8207VQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DS7PR11MB7860
X-OriginatorOrg: intel.com
X-Spam-Status: No, score=-2.5 required=5.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_MED,
        RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE
        autolearn=unavailable autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

On 2023-03-21 at 17:04:58 +0100, Peter Zijlstra wrote:
> On Tue, Mar 21, 2023 at 09:58:13PM +0800, Chen Yu wrote:
> > 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?
> 
> Yeah, I ran into that the other day, I think I'll introduce vlag_i = V - v_i
> or so.
> 
> > > + * \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?
> 
> Or worse, SCHED_IDLE, where weight is 2 (IIRC) or cgroups, then vtime
> advances at 512 times realtime. Now, the tick puts a limit on how long
> we'll overshoot these super low weight entities, for HZ=1000 we still
> only get 0.5s of vtime for weight=2.
>
> That would be only 30 bits used, except we use double FIXEDPOINT_SHIFT
> on 64bit, so we'll end up at 40-ish.
> 
> That should give us enough room to carry an average of deltas around
> min_vruntime.
> 
I'm trying to digest how ticks could prevent the overflow.
In update_curr() -> update_min_vruntime(cfs_rq), the cfs_rq->min_vruntime
is set to
max (cfs_rq->min_vruntime, min(curr->vruntime, leftmost(se->vruntime)))
so, although curr->vruntime increase by 0.5 seconds in each tick,
the leftmost(se->vruntime) could still be very small and unchanged,
thus the delta between v_i and cfs_rq->min_vruntime is still large.
Instead sysctl_sched_latency could decide how far it is between the
se.vruntime and the cfs_rq.min_vruntime, by calculating the vruntime
delta between task1 and task2:

    sched_vslice(task1) = (NICE0_LOAD/se1.weight)  * (w1/Sum wi * sysctl_sched_latency)
    sched_vslice(task2) = (NICE0_LOAD/se2.weight)  * (w2/Sum wi * sysctl_sched_latency)

Besides in patch 10, entity_eligible() checks
\Sum (v_i - v)*w_i >= (v_i - v)*(\Sum w_i)
and the \Sum w_i could become large if there are many runnable tasks and
bring overflow? But yes, if the vi -v is very small we can get rid of this
issue IMO.

thanks,
Chenyu
> But yes, I've seen this go sideways and I need to stare a bit more at
> this. One of the things I've considered is changing the min_vruntime
> update rules to instead move to avg_vruntime() to minimize the deltas.
> But I've not yet actually written that code.
>