Re: [PATCH 6/7] xen: Swap find_first_set_bit() for ffsl() - 1

From: Andrew Cooper <andrew.cooper3@citrix.com>
To: Jan Beulich <jbeulich@suse.com>
Cc: "Roger Pau Monné" <roger.pau@citrix.com>, "Wei Liu" <wl@xen.org>,
	"Stefano Stabellini" <sstabellini@kernel.org>,
	"Julien Grall" <julien@xen.org>,
	"Volodymyr Babchuk" <Volodymyr_Babchuk@epam.com>,
	"Bertrand Marquis" <bertrand.marquis@arm.com>,
	"Michal Orzel" <michal.orzel@amd.com>,
	"Oleksii Kurochko" <oleksii.kurochko@gmail.com>,
	"Shawn Anastasio" <sanastasio@raptorengineering.com>,
	"consulting @ bugseng . com" <consulting@bugseng.com>,
	"Simone Ballarin" <simone.ballarin@bugseng.com>,
	"Federico Serafini" <federico.serafini@bugseng.com>,
	"Nicola Vetrini" <nicola.vetrini@bugseng.com>,
	Xen-devel <xen-devel@lists.xenproject.org>
Subject: Re: [PATCH 6/7] xen: Swap find_first_set_bit() for ffsl() - 1
Date: Mon, 18 Mar 2024 12:27:42 +0000	[thread overview]
Message-ID: <2b40f2d6-9096-4e14-bdb3-e218bc3919fa@citrix.com> (raw)
In-Reply-To: <f088d9ac-fded-495e-9cc2-8514f7eb3e31@suse.com>

On 18/03/2024 9:13 am, Jan Beulich wrote:
> On 14.03.2024 19:51, Andrew Cooper wrote:
>> On 14/03/2024 6:47 pm, Andrew Cooper wrote:
>>> On 14/03/2024 2:30 pm, Jan Beulich wrote:
>>>> On 13.03.2024 18:27, Andrew Cooper wrote:
>>>>> --- a/xen/drivers/passthrough/x86/iommu.c
>>>>> +++ b/xen/drivers/passthrough/x86/iommu.c
>>>>> @@ -641,7 +641,7 @@ struct page_info *iommu_alloc_pgtable(struct domain_iommu *hd,
>>>>>      if ( contig_mask )
>>>>>      {
>>>>>          /* See pt-contig-markers.h for a description of the marker scheme. */
>>>>> -        unsigned int i, shift = find_first_set_bit(contig_mask);
>>>>> +        unsigned int i, shift = ffsl(contig_mask) - 1;
>>>> The need for subtracting 1 is why personally I dislike ffs() / ffsl() (and
>>>> why I think find_first_set_bit() and __ffs() (but no __ffsl()) were
>>>> introduced).
>>> It's sad that there are competing APIs with different bit-labelling, but
>>> the optimiser does cancel the -1 with arch_ffs() (for at least x86 and
>>> ARM that I studied in detail).
>>>
>>> I firmly believe that fewer APIs which are fully well defined (and can
>>> optimise based on the compiler's idea of safety) is still better than a
>>> maze of APIs with different behaviours.
> I agree here. The anomaly (as I would call it) with ffs(), though, is what
> makes me wonder whether we might not be better off introducing ctz() and
> clz() instead. Unlike ffs() their name says exactly what is meant. This is
> then also a clear hint, for Arm and RISC-V at least, what underlying
> instruction is used. Plus there are matching builtins (unlike for e.g.
> fls()).

I considered this, but I think it will be a bad idea.

Right now, almost all of our logic is expressed in terms of
ffs()/fls().  Rearranging this to clz/ctz is risky enough on its own,
let alone the potential for mistakes during backport.

Both ffs() and fls() are well defined for all inputs, and I've found a
way to let the optimiser deal with simplifying things when safe to do so.

Therefore, keeping ffs()/fls() is the right thing to do.  It's harder to
shoot yourself in the foot with, and optimiser can still do an good job
in the general case.

~Andrew