linux-kernel - Re: [RFC PATCH v1 08/50] fs/ext4/ialloc.c: Replace % with reciprocal

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <EC88E8EB-7303-45FB-85B9-A007FBE5F5A0@dilger.ca>
Date:   Sat, 28 Mar 2020 18:10:11 -0600
From:   Andreas Dilger <adilger@...ger.ca>
To:     George Spelvin <lkml@....ORG>
Cc:     Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        Theodore Ts'o <tytso@....edu>,
        linux-ext4 <linux-ext4@...r.kernel.org>
Subject: Re: [RFC PATCH v1 08/50] fs/ext4/ialloc.c: Replace % with
 reciprocal_scale() TO BE VERIFIED

On Mar 28, 2020, at 5:15 PM, George Spelvin <lkml@....ORG> wrote:
> 
> On Sat, Mar 28, 2020 at 04:56:17PM -0600, Andreas Dilger wrote:
>> 
>> So I think the current patch is fine.  The for-loop construct of
>> using "++g == ngroups && (g = 0)" to wrap "g" around is new to me,
>> but looks correct.
>> 
>> Reviewed-by: Andreas Dilger <adilger@...ger.ca>
> 
> Thank you.  Standing back and looking from higher altitude, I missed
> a second modulo at fallback_retry: which should be made consistent,
> so I need a one re-spin.
> 
> Also, we could, if desired, eliminate the i variable entirely
> using the fact that we have a copy of the starting position cached
> in parent_group.  I.e.
> 
> 		g = parent_group = reciprocal_scale(grp, ngroups);
> -		for (i = 0; i < ngroups; i++, ++g == ngroups && (g = 0)) {
> +		do {
> 			...
> -		}
> +			if (++g == ngroups)
> +				g = 0;
> +		} while (g != parent_group);
> 
> Or perhaps the following would be simpler, replacing the modulo
> with a conditional subtract:
> 
> -		g = parent_group = reciprocal_scale(grp, ngroups);
> +		parent_group = reciprocal_scale(grp, ngroups);
> -		for (i = 0; i < ngroups; i++, ++g == ngroups && (g = 0)) {
> +		for (i = 0; i < ngroups; i++) {
> +			g = parent_group + i;
> +			if (g >= ngroups)
> +				g -= ngroups;
> 
> The conditional branch starts out always false, and ends up always true,
> but except for a few bobbles when it switches, branch prediction should
> handle it very well.
> 
> Any preference?

I was looking at whether we could use a for-loop without "i"?  Something like:

	for (g = parent_group + 1; g != parent_group; ++g >= ngroups && (g = 0))

The initial group is parent_group + 1, to avoid special-casing when the
initial parent_group = 0 (which would prevent the loop from terminating).

Cheers, Andreas






Download attachment "signature.asc" of type "application/pgp-signature" (874 bytes)