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:   Tue, 16 May 2023 09:37:29 +0200
From:   luca abeni <luca.abeni@santannapisa.it>
To:     Vineeth Remanan 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: <20230516093729.0771938c@luca64>
In-Reply-To: <CAO7JXPgq8V5yHM6F2+iXf4XJ9cyT30Hn4ot5b2k7srjsaPc3JQ@mail.gmail.com>
References: <20230515025716.316888-1-vineeth@bitbyteword.org>
        <20230515025716.316888-3-vineeth@bitbyteword.org>
        <20230515100616.33ba5dd9@luca64>
        <CAO7JXPgq8V5yHM6F2+iXf4XJ9cyT30Hn4ot5b2k7srjsaPc3JQ@mail.gmail.com>
Organization: Scuola Superiore S. Anna
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?QmF3RGJGdXdGOGZoaU96MFRqYWtrZUlvUGYxbkVibi9mZHNUemt6elRXZXRi?=
 =?utf-8?B?TS9BazcrQU1rc1VtdzkySzNhRDJpdFIxQkJZSWFQWGVaaVFRd2ZpNGRBRGNz?=
 =?utf-8?B?K25tdy9zZmZrSU5ha0VkRXhCcGVSeEtFVUdQUzRuVGc1VE1VaU1VWkJDWFkw?=
 =?utf-8?B?Vkt1UEM1QmZSanBEK25kV0lqMEtVQjhub2pSU0trV0VMNlJxNTVuRTVXL09T?=
 =?utf-8?B?VFo1ZUs2SHBJK0ZwcWdaQ1RxKzdMV2hUUlc3STJYTzdmZWdoRGdiTlMzSXZi?=
 =?utf-8?B?V0Jscm4reDBlZjEvbVVFNkhHVkltOGtqSkV3bmE5WjVhWGhmSGJEd0hhMjdu?=
 =?utf-8?B?Vk9uSzN0TXp3bk8rYXJJZUJkdmdFK0xNeUJkbk5xU0ZWN3dXb2QvV3NDRk1T?=
 =?utf-8?B?Tmk4blg2NTI1bStFdlJlWlU5YjI2b1dLa1hPT2k0NEJ2b3R1SVlETkdXRFhL?=
 =?utf-8?B?blZBdVh0K2s3cnlRTndEbUY1MGk2eUhxVEl1dmhsbWtxeWtONmpPYU5ZdDBH?=
 =?utf-8?B?UU9JOE1wb2J6azZ1SDkvTDdTbHEwOHFhZWhZSUFFWE0xTnd6a3VVMDJ2NUJF?=
 =?utf-8?B?NEV6ajBFUU5jQVYrbXFwRDhLSUk4UnFZMVNCZWZNVGczQlUveHY4dEZjSWFR?=
 =?utf-8?B?eWN3cjFHN3BudnhiWG5OZ2tZaE9HM2M0c0xtejVZSmJWeTExQzEzdHNLYTJG?=
 =?utf-8?B?bDhKTG5RT3NvK3l0Y2w3WGpGQ251T20zc1NTTkhzYisyUVl4OVBrOWNSakMv?=
 =?utf-8?B?WUZwZzE2Qlc4SmdNaEd6WjZHeC9UV0RRK2lFRXBGUU9lZy9Sd20yMEp2eHVJ?=
 =?utf-8?B?WUlnR3UrcUVXVllnb1djWldMZ2prRUo4WkNteHpndWZPSkNma1RRU3pFd1Rv?=
 =?utf-8?B?QkdyQU5qYlUvdmNnb2pISFlHRE1acGJ5YmRkMWpvUEc5YXZKT0J4M1lJc3ln?=
 =?utf-8?B?b3ZrSHMxSk5ZaWdmWnhqZ1Bra25nSDZaT3h1ZlcrUVdWcWc3RDJZcWNlWVBv?=
 =?utf-8?B?MzUvUHA5U0pxQng0R3I1VjVHdWVzZEk5bDNlT2l0c2hxMzhMTUJwZDN2dDJV?=
 =?utf-8?B?OWVlY2dIeUxlVitmc1BPSUdqeTlIM0xhbXh0R3g4azZIWElrOVBtNllqZUt4?=
 =?utf-8?B?bGVWcmFzdXh4a05MT0toOFdkNnAwbkNseUVweDlROTlVMmd4cnkvWGJYVVZv?=
 =?utf-8?B?R3l0WFlHTkgzZ2hoOFg3NENrUHBQcy9XaVJ3THZnUHVMdUlMVm9BS0JibzMx?=
 =?utf-8?B?dy9PejdNRFgzSzMxQkdHNkhvN295Y1BxamtCaFVsNjBNZFZGRkhqV3JVdXhu?=
 =?utf-8?B?RGpoYmFMVzRQZWoySHBqejVOR25MSS9jZmY5eHVpWmNBa200NEJtRE8vckZY?=
 =?utf-8?B?c3NXS2FjOHU5NUwxQzZPazVUS1BjS1ptMW5pai9kaGs3VmZIeVpSbndwalln?=
 =?utf-8?B?REkxSVJOdFdCUHRBQytTSUJyMncvVHNhR2pZbVRaRXcyVHZSWFc2c3g1WEtV?=
 =?utf-8?B?VzB5NWd0QkdyUXVaSTdkVWx1RWxoaVJKcjdUVXVwRkU5aWo0MkpBSzdISEVU?=
 =?utf-8?B?YTk2cGQrTkRxQjhpQzVuZmlwSWFFaFN2SVpCb3F3ODYycXJGUk5MK2MzeUJJ?=
 =?utf-8?B?ejdaVTdiNWNMMGQ1ZEhIcURJN080b21sczJBM2lPZE1yWndjY2lBSkpWQUlT?=
 =?utf-8?B?RFYrdmZNYUw2NmtqTG1QK1FHY3c1aTVVb2hIa3JXYWlLQ0xxUnlBUXl3TENr?=
 =?utf-8?B?V016U3ZhQTY4STM4ZCtudVg4MW5QRng4d01UMUxMWnJmWEVrZ2NiRzR4SGRE?=
 =?utf-8?B?aGM4K0NVeDdRbmNZL2hFZm5sb2FUUUJaNnR5UUFkeXY4c09Lcm1wUU9TOHNy?=
 =?utf-8?B?M1dST1BiWEZVMDkyQ3FZM3JmcUt2clRkZWU4d3NLbm4wTExlNFo0NnJYcVRE?=
 =?utf-8?B?YWM3VlJHVnAvdERNclhwem1vQ2JmSGF5Z1ZRTkg1RFhrQklGK0o3cUlFdmFV?=
 =?utf-8?B?YllkTmhPeHZYbHEwTUpwWFZNSlhrOUJuNXpDeWc0TFRoUDl2dy9iM1krVUE2?=
 =?utf-8?B?bVRWMVNxYWRJNVFqL1B0WWs2SjZ1TUxMV2JEeWZkVDUyQXpGVnlWZWpHN05B?=
 =?utf-8?B?c0pqcEh0RStSRzgrSXVheE9OYUJaR0dxdXVCbkxUNFF0VktjN3VwSUFaY3dN?=
 =?utf-8?B?Tmc9PQ==?=
X-OriginatorOrg: santannapisa.it
X-MS-Exchange-CrossTenant-Network-Message-Id: c5d2b325-2987-462d-74af-08db55e069c0
X-MS-Exchange-CrossTenant-AuthSource: VI1PR03MB2880.eurprd03.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 16 May 2023 07:37:33.9756
 (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: rNPCaJqVLmkIm9gJ1zrBo/cEvEZUl/8VCzzja6bC85ql/AlbenHXyomdbKvRFqc3AiGxNNIOAxsLA2zJZcnmVcXc1FOPTAKuASK47bxNij0=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DU2PR03MB8076
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,
        URIBL_BLOCKED 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

On Mon, 15 May 2023 21:47:03 -0400
Vineeth Remanan Pillai <vineeth@bitbyteword.org> wrote:

> Hi Luca,
>=20
> On Mon, May 15, 2023 at 4:06=E2=80=AFAM luca abeni
> <luca.abeni@santannapisa.it> wrote:
>=20
> >
> > this patch is giving me some headaches:
> > =20
> Sorry about that.. I was also stressing out on how to get the
> reclaiming done right for the past couple of days ;-)

Well, this math is hard... :)

> > Vineeth Pillai <vineeth@bitbyteword.org> wrote:
> > [...] =20
> > >   *   Uextra:         Extra bandwidth not reserved:
> > > - *                   =3D Umax - \Sum(u_i / #cpus in the root
> > > domain)
> > > + *                   =3D Umax - this_bw =20
> >
> > While I agree that this setting should be OK, it ends up with
> >         dq =3D -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?)
> > =20
> I have noticed this behaviour where the reclaimed time is not equally
> distributed when we have more tasks than available processors. But it
> depended on where the task was scheduled. Within the same cpu, the
> distribution seemed to be proportional.

Yes, as far as I remember it is due to migrations. IIRC, the problem is
related to the fact that using "dq =3D -Uact / Umax * dt" a task running
on a core might end up trying to reclaim some idle time from other
cores (which is obviously not possible).
This is why m-GRUB used "1 - Uinact" instead of "Uact"

[...]
> > I need to think a little bit more about this...
> > =20
> Thanks for looking into this.. I have a basic idea why tasks with less
> bandwidth reclaim less in SMP when number of tasks is less than number
> of cpus, but do not yet have a verifiable fix for it.

I think I can now understand at least part of the problem. In my
understanding, the problem is due to using
	dq =3D -(max{u_i, (Umax - Uinact - Uextra)} / Umax) * dt

It should really be
	dq =3D -(max{u_i, (1 - Uinact - Uextra)} / Umax) * dt

(since we divide by Umax, using "Umax - ..." will lead to reclaiming up
to "Umax / Umax" =3D 1)

Did you try this equation?

I'll write more about this later... And thanks for coping with all my
comments!


				Luca
>=20
> If patches 1 and 4 looks good to you, we shall drop 2 and 3 and fix
> the SMP issue with varying bandwidth separately.. Patch 4 would
> differ a bit when I remove 2 and 3 so as to use the formula:
>  "dq =3D -(max{u, (Umax_reclaim - Uinact - Uextra)} / Umax_reclaim) dt"
>=20
> Thanks for your patience with all these brainstorming:-)
>=20
> Thanks,
> Vineeth