linux-ext4 - 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 16:56:17 -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 18, 2019, at 7:32 PM, George Spelvin <lkml@....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@....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>

> Signed-off-by: George Spelvin <lkml@....org>
> Cc: "Theodore Ts'o" <tytso@....edu>
> Cc: Andreas Dilger <adilger.kernel@...ger.ca>
> Cc: linux-ext4@...r.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






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