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

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

[George Spelvin]

This came about as part of auditing prandom_u32() usage, but
this is a special case: sometimes the starting value comes
from prandom_u32, and sometimes it comes from a hash of a name.

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.

Feedback needed.

Signed-off-by: George Spelvin <lkml@sdf.org>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Andreas Dilger <adilger.kernel@dilger.ca>
Cc: linux-ext4@vger.kernel.org
---
 fs/ext4/ialloc.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/fs/ext4/ialloc.c b/fs/ext4/ialloc.c
index 7db0c8814f2ec..a4ea89b3ed368 100644
--- a/fs/ext4/ialloc.c
+++ b/fs/ext4/ialloc.c
@@ -457,9 +457,8 @@ static int find_group_orlov(struct super_block *sb, struct inode *parent,
 			grp = hinfo.hash;
 		} else
 			grp = prandom_u32();
-		parent_group = (unsigned)grp % ngroups;
-		for (i = 0; i < ngroups; i++) {
-			g = (parent_group + i) % ngroups;
+		g = parent_group = reciprocal_scale(grp, ngroups);
+		for (i = 0; i < ngroups; i++, ++g == ngroups && (g = 0)) {
 			get_orlov_stats(sb, g, flex_size, &stats);
 			if (!stats.free_inodes)
 				continue;
-- 
2.26.0

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

[Andreas Dilger]

[-- Attachment #1: Type: text/plain, Size: 2366 bytes --]

On Mar 18, 2019, at 7:32 PM, George Spelvin <lkml@sdf.org> wrote:
> 
> This came about as part of auditing prandom_u32() usage, but
> this is a special case: sometimes the starting value comes
> from prandom_u32, and sometimes it comes from a hash of a name.
> 
> 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>

> Signed-off-by: George Spelvin <lkml@sdf.org>
> Cc: "Theodore Ts'o" <tytso@mit.edu>
> Cc: Andreas Dilger <adilger.kernel@dilger.ca>
> Cc: linux-ext4@vger.kernel.org
> ---
> fs/ext4/ialloc.c | 5 ++---
> 1 file changed, 2 insertions(+), 3 deletions(-)
> 
> diff --git a/fs/ext4/ialloc.c b/fs/ext4/ialloc.c
> index 7db0c8814f2ec..a4ea89b3ed368 100644
> --- a/fs/ext4/ialloc.c
> +++ b/fs/ext4/ialloc.c
> @@ -457,9 +457,8 @@ static int find_group_orlov(struct super_block *sb, struct inode *parent,
> 			grp = hinfo.hash;
> 		} else
> 			grp = prandom_u32();
> -		parent_group = (unsigned)grp % ngroups;
> -		for (i = 0; i < ngroups; i++) {
> -			g = (parent_group + i) % ngroups;
> +		g = parent_group = reciprocal_scale(grp, ngroups);
> +		for (i = 0; i < ngroups; i++, ++g == ngroups && (g = 0)) {
> 			get_orlov_stats(sb, g, flex_size, &stats);
> 			if (!stats.free_inodes)
> 				continue;
> --
> 2.26.0
> 


Cheers, Andreas






[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]

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

[George Spelvin]

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

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

[Andreas Dilger]

[-- Attachment #1: Type: text/plain, Size: 1870 bytes --]

On Mar 28, 2020, at 5:15 PM, George Spelvin <lkml@SDF.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@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?

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






[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]

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

[George Spelvin]

On Sat, Mar 28, 2020 at 06:10:11PM -0600, Andreas Dilger wrote:
> On Mar 28, 2020, at 5:15 PM, George Spelvin <lkml@SDF.ORG> wrote:
>> 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);

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

That's the first option I presented, above.  Since a for() loop
tests before each iteration, if the counter is strictly modulo
ngroups, there's no way to execute the loop body more than ngroups-1
times.

That's why I changed to do{}while(), which has a minimum of 1 (it can't
handle ngroups == 0), but can mimic the current loop's execution
perfectly (no initial +1 offset).