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:   Wed, 10 May 2023 09:07:35 +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 1/2] sched/deadline: accurate reclaim bandwidth for GRUB
Message-ID: <20230510090735.68f62cd4@nowhere>
In-Reply-To: <CAO7JXPhk5qbz9kmiu9WuXS+gXCt9+X8pP2c37hd9ChByLmXYjA@mail.gmail.com>
References: <20230508160829.2756405-1-vineeth@bitbyteword.org>
        <20230509132534.09098acc@luca64>
        <CAO7JXPhrqKWfsp860rRmEenxARi8U2gNMGsOn4m+aKporWwBcg@mail.gmail.com>
        <20230509224829.2fb547fd@nowhere>
        <20230509225417.61d36733@nowhere>
        <CAO7JXPhk5qbz9kmiu9WuXS+gXCt9+X8pP2c37hd9ChByLmXYjA@mail.gmail.com>
Organization: Scuola Superiore Sant'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?U2lBK1E3Zzl6bjl4YjFwT1dwbk50RFAxT0hjbXI3MDlmci92V2YvZFVVWWhI?=
 =?utf-8?B?TVNaaUx1TDFWeW1GMlhqaDE1djIzUnVFLzNYT1p6UE9FVW5uS2lpc29kMlJj?=
 =?utf-8?B?NENXTmhmMWlQQVE0bWlQSXZPYjdBUHZHZ0lBNHdOaU5lT2QvVDM1NFdJdExt?=
 =?utf-8?B?bmNjQk1OREYxYlorWmVqUkxmeC9PbmJra2VjemwvR1d1UnAvNXlXOTVUNm8w?=
 =?utf-8?B?TThPbVJtMldHUFkzNlVUK2tHRW9KNXIvTlZxSUNhdXE4NGxOQ25KZDRVbVRB?=
 =?utf-8?B?QUtKZGFkRENncUpjSmZFYUVIQ2I3L0VtUXpxaWo2OW13WFNvbkt3Tk1ySVl6?=
 =?utf-8?B?bG13SFpMemE2SE1vMklBbUtVaDFSdDZ6WHNKeHpqMnBKRUxsdTZlejFyeGJn?=
 =?utf-8?B?ZGZkSHQyRE53MkVTMlphZW5jYktVZW9lb1F5ZDZCNnZtd1VabERzNGQ2Q0lh?=
 =?utf-8?B?TjBBZkE4QjdZNVBVS0RLL0JZT2FrSVEzcXkzYkxiRUl6dm1QMW5NTWJIN2xN?=
 =?utf-8?B?SiszdWd3WnN1N0FIWU0vWEFTdmFlZWtDbGluTXNDREJraTkxMVJsT0swUFBF?=
 =?utf-8?B?Rmx2UmZPSTRJRGFjS3JKMW9PbDc5Rm1HSzRZT0RlUjh5ZEVKd3JPMkdpbWhw?=
 =?utf-8?B?TU1VVDdnM1NrbitDR0xpNXhiSDZqK0hieWNsazE5eXBxam1LZTVHVE91Y3ZQ?=
 =?utf-8?B?cTFKUnVYbWZNV00yblZmenIyeFo4cG1ESG9ld04vdlBqeTBBSHg4TUU3SHRO?=
 =?utf-8?B?RFNKU1VOcG91UGNqVUZxSWpVbHU4eUVBREJ4UmZFR0JhN2JPQ25RQUx0M2VO?=
 =?utf-8?B?alI1eTFzclNxZGViNGNvQmtaZ1ovWkcvMHJhbnMxYnU3UGxyUFFucFI4anBR?=
 =?utf-8?B?a1ZZMk1GN2VBUk55cmZFcldGN3Z0Y1A4NUJNSlVuSHVCR0plbmd2UDBGT0xL?=
 =?utf-8?B?UmpKWGx1UmFhWXZnZjVkdHZldkFqMFJIeFBBWGc2djVyalgzbGpiSkxnd1Fa?=
 =?utf-8?B?a2lHZTlqZDdqOEVLdW9uUnZzNitlSFBpNGVTUHZoLzNSNER1YjlXWXFUN0N5?=
 =?utf-8?B?OTRnTTN4N0JkSFNMYUNFajVUc2lvSjhUdk1lZ2FwNzNLL3hwbmN4QTJzUlNz?=
 =?utf-8?B?bnF0WnJDbjZBOVY0aTMyMHl2VC8rbzgwYzFjeDdJNkVlUExEVzZEQWkyd01Y?=
 =?utf-8?B?eGtuSjN6K21lMXRpaDZLQ2dJK2tpeEtNSm9LQ1RmWjRNWHQyNlJDdVZEZUJ2?=
 =?utf-8?B?YjY5YWdPRHk3OS9LMGtUTVhKcGlwd2J4Y3hJQ3dEalNQMXlTVEdPa2IrNHpn?=
 =?utf-8?B?aFFUMGQ2bWtBcVpjcnpSUG81Nkp5Nmp6cVZqQmtlREZ2R3FpUnV0UmNMMEFp?=
 =?utf-8?B?TnFaRUFoaG5hK0tFY0xZVXFZbGVubTJaZUJySHBLNlNWbEtYb2k4VW9JOUFS?=
 =?utf-8?B?N3h1ckhXMzBYdDFrVGVMd1VZeTdvZW4wWXZjWTlJdkFvRmdMOCsxSFkwbHk2?=
 =?utf-8?B?NTlkcVNLeDhYRk9CcWttNE4xbWhOclJoMGZuTDRKVCtvMWJJek9NcWJhOWFu?=
 =?utf-8?B?UWdEazcybGxUSDdoUDd5RW1ZTDhqU2Vrd1luU3VDRE1CSXJvbVBoWTFPREdQ?=
 =?utf-8?B?WUpNMVEzVzVONmlZOVFNbDNVKzZLeGJWRkVBN1NnNEtaWU1tRU5HR2JGMm1T?=
 =?utf-8?B?QXB3RiswZVl2N0RmNHk1RnFUMERQM3dRenMzQ1dTU0U0SGVSaUo5REZJQldZ?=
 =?utf-8?B?Y0w5NkIvSEgremJtTzRidWxTMVlDZHQzU1R1NGJmWU5jWUtJVUpVRkN0dHF5?=
 =?utf-8?B?TGFvOW9WMVd1N3BlQWtkZUEvbzNBc21lbVpxVkoxaHBZdU1La2lVQnR3T25G?=
 =?utf-8?B?Y0ErditiNVRxQVZPdlJySld3YmtrSHVBQnEzanpKUFBqemdyS09EcksxYXVk?=
 =?utf-8?B?bG1qY3VwMWtmbzNaNTl6MUxrTnBxb0NIY0RyYk14bVpSd2wwVi9seWtZWG5a?=
 =?utf-8?B?bzVtRDZZTE9SRFBKMnhvSVVMVER4dzJOQmltdlYxd1J2UThHdFRPUDg4SWRD?=
 =?utf-8?B?VmE4aWwrS3k3VUpWWG9EWXpxb2tSTFpNYlg0aGlMcUlmSU5TcEdCMDdCcEg5?=
 =?utf-8?B?WDAvZHlJblcrQk5WaUJHU1RpS1JwZVo3UFRQWXA0SHVLMU8rNnU2ZG92TjNY?=
 =?utf-8?B?N2c9PQ==?=
X-OriginatorOrg: santannapisa.it
X-MS-Exchange-CrossTenant-Network-Message-Id: 1526a5cb-1f35-444c-523c-08db512543f3
X-MS-Exchange-CrossTenant-AuthSource: VI1PR03MB2880.eurprd03.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 10 May 2023 07:07:50.1683
 (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: Z3jK4isjYIxuYC3ZMFW8LOYCUA+nANH57i4nb00vRCbvq2af5+ALKWK+xJpbqRlplH1UF36HLB+wMaELW5Gz7WOaPrq99r4ENoODamBwtk4=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: GVXPR03MB8353
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

Hi,

after thinking more about this (and re-reading the code, and your patch
:), I try to comment again:

On Tue, 9 May 2023 23:53:28 -0400
Vineeth Remanan Pillai <vineeth@bitbyteword.org> wrote:

> On Tue, May 9, 2023 at 4:54=E2=80=AFPM luca abeni
> <luca.abeni@santannapisa.it> wrote:
>=20
> > > Yes, this is the approximation I was mentioning... Instead of
> > > using a division, I approximated it with a different equation
> > > using a sum. =20
> >
> > Sorry, ignore this comment (and the following); I misinterpreted the
> > code (and my old notes).
> >
> > I do not understand why the "max{}" doe not work well, I need to
> > double think about it.
> > =20
> I was thinking more about this and was doing some more digging into
> this. I was also wrong about min{}. Giving it some more thought, I
> think (U/Umax) is indeed the only equation we need and it will take
> care of caping the reclaiming at Umax.

Uhm... I am not sure about this: for 1 single task on 1 CPU, yes,
u/Umax does the right thing. But when there are multiple tasks on the
CPU, I think it can cause issues (because every task ends up trying to
execute for Umax).

The "max{}" comes from the original multi-processor GRUB algorithm:
https://arxiv.org/pdf/1512.01984.pdf (see Equation (13) - in that
equation, the part we call u_extra is included in Uinact[p])

the "1 - u_inact - u_extra" part is needed to make sure that the
real-time guarantees are not broken by the reclaiming mechanism... But
it can end up with a task trying to consume too much time on a single
CPU, hence the "u/Umax" term in the "max{}" is needed to make sure that
a task will not consume more than Umax of a CPU.

Now, if we have one single task on a CPU u/Umax will always be larger
than the other term... But when we have multiple tasks the other term
is needed too.


> The reason why it was not
> working is because of the loss of precision when we did the inverse.

I agree


> I tried replacing (delta * running_bw * bw_ratio) by
> div64_u64(delta * running_bw, Umax) and it worked as expected and
> reclaimed only till Umax with only SCHED_FLAG_RECLAIM tasks. As an
> example a task with reservation (1, 100) and RT capacity 95%, and
> delta =3D 4ms, we get scaled_delta as
> delta * running_bw * bw_ratio ~=3D .040000 (roughly)
> div64_u64(delta * running_bw, Umax) ~=3D .04210526 (roughly)
>=20
> This caused the inverse logic to consume ~99% bw, while the other
> one consumed ~95% as expected.
>=20
> I still could not figure out why min{} works. As you mentioned in
> the previous thread, its the loss of precision thats the culprit and
> I think we only need U/Umax if we have enough precision. This along
> with accounting for both type of tasks will be the solution.

I agree with this.


(BTW, when considering multiple tasks on multiple CPUs, another
potential problem is given by u_extra... Now that I remember all the
details, u_extra is not "Umax - this_bw" - this is true when we consider
only one CPU, but is is "Umax - sum(u_i)/m" (where "sum(u_i)" is the
sum of the bandwidths of all the SCHED_DEADLINE tasks in the root
domain, and "m" is the number of CPUs in the root domain)... So, the
reclaimable CPU time is distributed uniformly on all the CPUs and this
could create some issues. But let's see what happens after the div64
fix and the SCHED_FLAG_RECLAIM fix)


			Thanks,
				Luca

>=20
> I will look deeper into any performance issues with using div64_u64
> over multiplication and shall let you know soon.
>=20
> Thanks,
> Vineeth