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: Windows password security audit tool. GUI, reports in PDF.

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

Date:   Sat, 28 Mar 2020 23:15:36 +0000
From:   George Spelvin <lkml@....ORG>
To:     Andreas Dilger <adilger@...ger.ca>
Cc:     Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        "Theodore Ts'o" <tytso@....edu>,
        linux-ext4 <linux-ext4@...r.kernel.org>, lkml@....org
Subject: Re: [RFC PATCH v1 08/50] fs/ext4/ialloc.c: Replace % with
 reciprocal_scale() TO BE VERIFIED

On Sat, Mar 28, 2020 at 04:56:17PM -0600, Andreas Dilger wrote:
> On Mar 18, 2019, at 7:32 PM, George Spelvin <lkml@....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@....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@....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@...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?

(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.)