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

[Andreas Dilger]

On Mar 18, 2019, at 7:32 PM, George Spelvin <lkml@xxxxxxx> 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@xxxxxxx>
    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@xxxxxxx>

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@xxxxxxxxx>

> Signed-off-by: George Spelvin <lkml@xxxxxxx>
> Cc: "Theodore Ts'o" <tytso@xxxxxxx>
> Cc: Andreas Dilger <adilger.kernel@xxxxxxxxx>
> Cc: linux-ext4@xxxxxxxxxxxxxxx
> ---
> 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: signature.asc
Description: Message signed with OpenPGP