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:   Mon, 15 May 2023 10:06:16 +0200
From:   luca abeni <luca.abeni@santannapisa.it>
To:     Vineeth Pillai <vineeth@bitbyteword.org>
Cc:     Juri Lelli <juri.lelli@redhat.com>,
        Daniel Bristot de Oliveira <bristot@redhat.com>,
        Peter Zijlstra <peterz@infradead.org>,
        Ingo Molnar <mingo@redhat.com>,
        Vincent Guittot <vincent.guittot@linaro.org>,
        Steven Rostedt <rostedt@goodmis.org>,
        Joel Fernandes <joel@joelfernandes.org>,
        Dietmar Eggemann <dietmar.eggemann@arm.com>,
        Ben Segall <bsegall@google.com>, Mel Gorman <mgorman@suse.de>,
        Valentin Schneider <vschneid@redhat.com>,
        Jonathan Corbet <corbet@lwn.net>, linux-kernel@vger.kernel.org,
        linux-doc@vger.kernel.org
Subject: Re: [PATCH v3 2/5] sched/deadline: Fix reclaim inaccuracy with SMP
Message-ID: <20230515100616.33ba5dd9@luca64>
In-Reply-To: <20230515025716.316888-3-vineeth@bitbyteword.org>
References: <20230515025716.316888-1-vineeth@bitbyteword.org>
        <20230515025716.316888-3-vineeth@bitbyteword.org>
Organization: Scuola Superiore S. Anna
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?avkb1NmBXW1R1/Ol5ivI2a/Gy2o2AcJprDfxR7F7IEsuLeB+EnS5OjHX3siM?=
 =?us-ascii?Q?+BUY2UwM2LJ63jAxfMwyOGkkTzKiz6xKN8yJpqYvGVZOz/fLdGpdZMzEqrcG?=
 =?us-ascii?Q?TRfv0YlMfvxjwB8HxF08N/wHpXbfBNmTmRIRPMBat4Ac6Bx5GMC7z36qXngO?=
 =?us-ascii?Q?xLWOt1ajX4nSwJSAK9sdEiAJx5bUa+fDwRKrOtsXexvNNL9izv1AEsz49O4B?=
 =?us-ascii?Q?5jx/guwsQ3Esmq3uL6ZqPYU2I5VTdrrsH8n4s62WzCsubLuSmDdVzW1AVYf9?=
 =?us-ascii?Q?M03VfqGv5KLFo2cF0S/POfrW9HuOrVwEE6sVIMP1uqjKpBSutXeURjlCuh5X?=
 =?us-ascii?Q?bWCpfuZYGwRFdR1EJSt4nnZFJNPy/mBwgP6RF+40gwZlt1dDfKzmyA6PyyJ/?=
 =?us-ascii?Q?2r4fgOzw1Hinwkv44uWPJBujIfVaTUE8d72q4pfqnD01qcXuE9P4s6E2rPNa?=
 =?us-ascii?Q?s/JmxSHW5XjKMVpWdRyUHGJW97oYPYAywPbAlof4Tn/ebxL7IJ+psuBgDDcq?=
 =?us-ascii?Q?FyzBS3QyHOhUNR1xkUGHVyHEKBM8+gDIQigwUxolNPlo8apkRAfmZHlFrRtp?=
 =?us-ascii?Q?8W8ZKmG4Au5AoNl4TwVgG9GO3a9abiXhJELVs2bQk7jcd2JQ991zv8dGNjUv?=
 =?us-ascii?Q?Tl4Z9kmTZGYbS4AWEM/rWfwfM/3o+eBmuVoOVG4FpPJOnU6zidsPUn0DJNMO?=
 =?us-ascii?Q?R1EtJp0BY3V0HH7Cet/9GKWQJ+7aCVLQPQN5qbZEdBNqiPJjF08Rt3//XQnB?=
 =?us-ascii?Q?B7fD+S3qT4UQ5Phoaho0/I6FTQZlV9HbIIAz6o5GDkAtwYD6eOQMdHv7ASk1?=
 =?us-ascii?Q?/psiUNUoDKz6ACrggwiQsgbHOOgvnIyVVfhpwmRaZNP07LmNh1hKkiGs6Fw4?=
 =?us-ascii?Q?ZMZmRDTmzMdOruNjAsK5xFP3TcGTebgXBYeCdB24kbjPv162T4SBT4FK93kN?=
 =?us-ascii?Q?z3C0Tg9m4Syk6xDy5/0TkYa8rBEa99gK+ctIyM9vVuHHGqZo45qhVXRWmZAE?=
 =?us-ascii?Q?S3T6v6iKemaXzN7s3+f9KlGVTXgvY3R67KargjezOC7BvCuPjLcNg93S/n1f?=
 =?us-ascii?Q?iphXW7p2FzQHnA+Cl49OIUQDeySILH3apA2ZyMhYxAM5O7TL4CSlT2zxElWq?=
 =?us-ascii?Q?MDO6r0GSDDP3lbsZezjSK3AG4VJL7vr1sjgqsBXUB0mLg5ssBFiyPVqjigSu?=
 =?us-ascii?Q?o6ZXWg3OSKXNZn+MTob3MTwLKGv5ySFUoCbBMGKUoH6EfO2V9NMpSqslbVB2?=
 =?us-ascii?Q?Tfwbwt/ROIUuP4lTBwaYgHs1dAVVQIMKqa8NoqCoUrGmMrOJLtsW53pgYmla?=
 =?us-ascii?Q?Uf20kblqVO8kgkQyMF9h/d6LyW4XeE1SUjjKUSktvGcYK7akvolzS8fjamvK?=
 =?us-ascii?Q?NRFZ+v74DHBSNYa6GbVuE0q+U3tnL1mgm05wbSwyaqczl51C1vtfqbM0Ttn7?=
 =?us-ascii?Q?flq6SMfpEWTxjyNptzgdlAz4jxPaIzqlahyJgAjl50TZplXdMcmPpH+VgxKn?=
 =?us-ascii?Q?mcj1Mg5AAwNC0/YKuhO5JkK1uQzHhKl6YAEBSqIvFOzPLr7HtT92El4BltW/?=
 =?us-ascii?Q?yu7CEMvLpLtktQ9Xlpk6I9L1I5Xek926VA/ZgSGZ0LlI7AKK7Toge28bFh0g?=
 =?us-ascii?Q?kw=3D=3D?=
X-OriginatorOrg: santannapisa.it
X-MS-Exchange-CrossTenant-Network-Message-Id: f22eb137-d604-40c8-2fd0-08db551b4413
X-MS-Exchange-CrossTenant-AuthSource: VI1PR03MB2880.eurprd03.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 15 May 2023 08:06:19.9074
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: d97360e3-138d-4b5f-956f-a646c364a01e
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: rqeiVZnkK8Um7mc3jW2rLJLPDs0LWev/6YLnlULUFca3Sp+xZ8WTsMKdsZwTyrX1umwk7TMavhcpWM92qGlBdiuxtG6L2C0QiKydEFYTRMU=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM7PR03MB6328
X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,
        RCVD_IN_MSPIKE_H2,SPF_HELO_PASS,SPF_PASS,T_SCC_BODY_TEXT_LINE
        autolearn=ham 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

Hi,

this patch is giving me some headaches:

On Sun, 14 May 2023 22:57:13 -0400
Vineeth Pillai <vineeth@bitbyteword.org> wrote:
[...]
>   *	Uextra:		Extra bandwidth not reserved:
> - *			= Umax - \Sum(u_i / #cpus in the root domain)
> + *			= Umax - this_bw

While I agree that this setting should be OK, it ends up with
	dq = -Uact / Umax * dt
which I remember I originally tried, and gave some issues
(I do not remember the details, but I think if you try N
identical reclaiming tasks, with N > M, the reclaimed time
is not distributed equally among them?)

I need to think a little bit more about this...


		Luca

>   *	u_i:		Bandwidth of an admitted dl task in the
>   *			root domain.
>   *
> @@ -1286,22 +1286,14 @@ int dl_runtime_exceeded(struct
> sched_dl_entity *dl_se) */
>  static u64 grub_reclaim(u64 delta, struct rq *rq, struct
> sched_dl_entity *dl_se) {
> -	u64 u_act;
> -	u64 u_inact = rq->dl.this_bw - rq->dl.running_bw; /* Utot -
> Uact */ -
>  	/*
> -	 * Instead of computing max{u, (rq->dl.max_bw - u_inact -
> u_extra)},
> -	 * we compare u_inact + rq->dl.extra_bw with
> -	 * rq->dl.max_bw - u, because u_inact + rq->dl.extra_bw can
> be larger
> -	 * than rq->dl.max_bw (so, rq->dl.max_bw - u_inact -
> rq->dl.extra_bw
> -	 * would be negative leading to wrong results)
> +	 * max{u, Umax - Uinact - Uextra}
> +	 * = max{u, max_bw - (this_bw - running_bw) + (this_bw -
> running_bw)}
> +	 * = max{u, running_bw} = running_bw
> +	 * So dq = -(max{u, Umax - Uinact - Uextra} / Umax) dt
> +	 *       = -(running_bw / max_bw) dt
>  	 */
> -	if (u_inact + rq->dl.extra_bw > rq->dl.max_bw - dl_se->dl_bw)
> -		u_act = dl_se->dl_bw;
> -	else
> -		u_act = rq->dl.max_bw - u_inact - rq->dl.extra_bw;
> -
> -	return div64_u64(delta * u_act, rq->dl.max_bw);
> +	return div64_u64(delta * rq->dl.running_bw, rq->dl.max_bw);
>  }
>  
>  /*