Re: [RFC PATCH v1 08/50] fs/ext4/ialloc.c: Replace % with reciprocal_scale() TO BE VERIFIED

[George Spelvin <lkml@SDF.ORG>]

On Sat, Mar 28, 2020 at 04:56:17PM -0600, Andreas Dilger wrote:
> On Mar 18, 2019, at 7:32 PM, George Spelvin <lkml@sdf.org> wrote:
>> Does the name hash algorithm have to be stable? In that case, this
>> change would alter it.  But it appears to use s_hash_seed which
>> is regenerated on "e2fsck -D", so maybe changing it isn't a big deal.
> 
> This function is only selecting a starting group when searching for
> a place to allocate a directory.  It does not need to be stable.
> 
> The use of the name hash was introduced in the following commit:
> 
>     f157a4aa98a18bd3817a72bea90d48494e2586e7
>     Author:     Theodore Ts'o <tytso@mit.edu>
>     AuthorDate: Sat Jun 13 11:09:42 2009 -0400
> 
>     ext4: Use hash of topdir directory name for Orlov parent group
> 
>     Instead of using a random number to determine the goal parent group
>     for Orlov top directories, use a hash of the directory name.  This
>     allows for repeatable results when trying to benchmark filesystem
>     layout algorithms.
> 
>     Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
> 
> 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@dilger.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?

(Seriously, thank you for a second set of eyes.  This patch set
contains so many almost-identical changes that my eyes were glazing
over and I couldn't see bugs.)