Date: Tue, 24 May 2016 09:47:38 -0500 From: Pedro Giffuni <pfg@FreeBSD.org> To: Bruce Evans <brde@optusnet.com.au>, Kevin Lo <kevlo@freebsd.org> Cc: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: Re: svn commit: r300423 - in head/sys: fs/ext2fs ufs/ffs Message-ID: <b2633318-9e64-ab1f-4a21-931193eb4b36@FreeBSD.org> In-Reply-To: <20160524195127.C931@besplex.bde.org> References: <201605221431.u4MEVKXC007524@repo.freebsd.org> <20160524195127.C931@besplex.bde.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On 05/24/16 07:20, Bruce Evans wrote:
> On Sun, 22 May 2016, Kevin Lo wrote:
>
>> Log:
>> arc4random() returns 0 to (2**32)−1, use an alternative to initialize
>> i_gen if it's zero rather than a divide by 2.
>>
>> With inputs from delphij, mckusick, rmacklem
>>
>> Reviewed by: mckusick
>> ...
>> Modified: head/sys/fs/ext2fs/ext2_alloc.c
>> ==============================================================================
>>
>> --- head/sys/fs/ext2fs/ext2_alloc.c Sun May 22 14:13:20 2016
>> (r300422)
>> +++ head/sys/fs/ext2fs/ext2_alloc.c Sun May 22 14:31:20 2016
>> (r300423)
>> @@ -408,7 +408,8 @@ ext2_valloc(struct vnode *pvp, int mode,
>> /*
>> * Set up a new generation number for this inode.
>> */
>> - ip->i_gen = arc4random();
>> + while (ip->i_gen == 0 || ++ip->i_gen == 0)
>> + ip->i_gen = arc4random();
>
> This is a correct implementation of ffs's intended method, but ffs's
> intended method is wrong (see below for its wrongness).
>
> Correctness depends on i_gen having type uint32_t in ext2fs. This
> makes the code +ip_i_gen undead, so i_gen is re-randomized occasionally
> (averaged over all inodes, once for every ~2 billionth reuse of an
> inode, which is practically never. Bugs in ffs prevent it being done
> even that often there. So the re-randomization is almost useless. I
> think it is slighty worse than useless, since it may give the same
> i_gen immediately, while always incrementing (but skipping 0) always
> gives a new i_gen.
>
> ext2fs might not need this at all. For ffs, then special case of
> i_gen == 0 must be handled because we still pretend to support file
> systems created by newfs versions almost 25 years old. newfs didn't
> initialize di_gen back then, so all inodes started with di_gen == 0.
> ext2fs is less that 25 years old, so it has less history to support.
>
I agree ext2fs, and likely UFS2, can handle the case of di_gen == 0.
The additional question is where do we actually need to do randomization
in ext2fs? UFS does the randomization when formatting
so ffs_vget doesn't do randomization at all. arc4random is AFAICT,
only required for very old UFS1.
I lost interest in ext2fs and can't be bothered to look in linux ;).
>>
>> vfs_timestamp(&ts);
>> ip->i_birthtime = ts.tv_sec;
>>
>> Modified: head/sys/fs/ext2fs/ext2_vfsops.c
>> ==============================================================================
>>
>> --- head/sys/fs/ext2fs/ext2_vfsops.c Sun May 22 14:13:20 2016
>> (r300422)
>> +++ head/sys/fs/ext2fs/ext2_vfsops.c Sun May 22 14:31:20 2016
>> (r300423)
>> @@ -998,7 +998,8 @@ ext2_vget(struct mount *mp, ino_t ino, i
>> * already have one. This should only happen on old filesystems.
>> */
>> if (ip->i_gen == 0) {
>> - ip->i_gen = random() + 1;
>> + while (ip->i_gen == 0)
>> + ip->i_gen = arc4random();
>
> This is correct, but might be unnecessary (see above). "on old
> filesystems"
> was copied from ffs where it meant "on file systems created by versions
> of newfs that didn't initialize di_gen". Such file systems are restricted
> to ffs1. But i_gen stil occurs due to bugs in newfs -- it is missing this
> loop, so it sometimes sets i_gen to the random value of 1, and we
> can't/don't
> tell the difference between this and unitialized.
>
> I think ext2fs is more like ffs2 in a relevant way here. Both have the
> feature of speeding up newfs by only writing a few inodes. Thus most
> inode allocations occur in the kernel, and it hardly matters if newfs
> initialized i_gen for the few inodes that it initialized. extfs and
> ext2fs also have an inode non-clearing feature on unlink that might
> be relevant. I forget if ffs2 has this. So the code should be simplified
> by never expecting newfs to initialize i_gen to nonzero. It already
> almost does this, except in the comment. For this, it is necessary to
> skip i_gen == 0 (mod 2**32).
>
>> if ((vp->v_mount->mnt_flag & MNT_RDONLY) == 0)
>> ip->i_flag |= IN_MODIFIED;
>> }
>>
>> Modified: head/sys/ufs/ffs/ffs_alloc.c
>> ==============================================================================
>>
>> --- head/sys/ufs/ffs/ffs_alloc.c Sun May 22 14:13:20 2016 (r300422)
>> +++ head/sys/ufs/ffs/ffs_alloc.c Sun May 22 14:31:20 2016 (r300423)
>> @@ -1102,8 +1102,8 @@ dup_alloc:
>> /*
>> * Set up a new generation number for this inode.
>> */
>> - if (ip->i_gen == 0 || ++ip->i_gen == 0)
>> - ip->i_gen = arc4random() / 2 + 1;
>> + while (ip->i_gen == 0 || ++ip->i_gen == 0)
>> + ip->i_gen = arc4random();
>
> This is broken due to an old type error. In ffs, i_gen has type uint64_t,
> so it is physically impossible for ++ip->i_gen to wrap to 0.
> (i_gen is initialized from di_gen, and that has type uint32_t, so
> i_gen is initially <= UINT32_MAX and it would take 584 years to wrap
> with the modest inode recycling period of 1 nanosecond.)
> So the above is an obfuscated way of writing:
>
> if (ip->i_gen == 0) {
> /*
> * This value means uninitialized (or a bug). Init now.
> * The loop is to not have the usual bug here.
> */
> do
> ip->i_gen = arc4random();
> while (ip->i_gen == 0);
> } else
> ip->i_gen++;
>
> Now it is clear that i_gen can grow far above UINT32_MAX. But usually
> it doesn't. Growth above UINT32_MAX gets truncated when the vnode is
> recycled. Overflow occurs with i_gen is stored to di_gen, and growth
> resumes at a small truncated value.
>
> The type error gives truncation on most uses of i_gen: di_gen, ufid_gen
> and ueh_i_gen are all 32 bits. va_gen is 32-bits on 32-bit arches but
> is 64 bits on 64-bit arches. Various bugs result. The bugs are mostly
> features. It is not very useful to re-randomize on reaching the 32-bit
> boundary. The bugfeature normally avoids this. If i_gen were not
> truncated to 32 bits when the vnode is recycled (or on unmount), and
> if it were consistently truncated (that means, truncate it to 32 bits
> in va_gen on 64-bit arches), then the bugfeature would work perfectly.
> The top 32 bits in i_gen would then be unused except to record history
> for a few trillion years for most inodes.
>
>> DIP_SET(ip, i_gen, ip->i_gen);
>> if (fs->fs_magic == FS_UFS2_MAGIC) {
>> vfs_timestamp(&ts);
>> @@ -2080,7 +2080,8 @@ gotit:
>> bzero(ibp->b_data, (int)fs->fs_bsize);
>> dp2 = (struct ufs2_dinode *)(ibp->b_data);
>> for (i = 0; i < INOPB(fs); i++) {
>> - dp2->di_gen = arc4random() / 2 + 1;
>> + while (dp2->di_gen == 0)
>> + dp2->di_gen = arc4random();
>
> This seems to be correct. It is only for the ffs2 case, and di_gen was
> initialized to 0 by the bzero(), but the while loop is easier to read
> that the more optimal do-while loop that I wrote above.
>
>> dp2++;
>> }
>> /*
>>
>> Modified: head/sys/ufs/ffs/ffs_vfsops.c
>> ==============================================================================
>>
>> --- head/sys/ufs/ffs/ffs_vfsops.c Sun May 22 14:13:20 2016
>> (r300422)
>> +++ head/sys/ufs/ffs/ffs_vfsops.c Sun May 22 14:31:20 2016
>> (r300423)
>> @@ -1768,7 +1768,8 @@ ffs_vgetf(mp, ino, flags, vpp, ffs_flags
>> * already have one. This should only happen on old filesystems.
>> */
>> if (ip->i_gen == 0) {
>> - ip->i_gen = arc4random() / 2 + 1;
>> + while (ip->i_gen == 0)
>> + ip->i_gen = arc4random();
>
> This also seems to be correct. Now the compiler can easily optimize the
> while loop to a do-while loop, since a previous check for i_gen == 0 is
> visible.
>
> "should" in the comment is correct, except this should never happen
> now since file systems that were old when it was written now shouldn't
> exist. However, this does happen now, mostly for new file systems,
> due to a bug in newfs: newfs is missing this while loop, so it sometimes
> initializes di_gen to 0. Then we can't/don't tell if di_gen was
> initialized to a random value, so we-re-randomize it.
>
>> if ((vp->v_mount->mnt_flag & MNT_RDONLY) == 0) {
>> ip->i_flag |= IN_MODIFIED;
>> DIP_SET(ip, i_gen, ip->i_gen);
>
> All versions of newfs seem to have had buggy initialization:
> - they didn't initialize di_gen (except to 0) until 1997
> - the first 1997 version used /dev/urandom to initialize "long ret;".
> Assignment of this to "int32_t di_gen;" overflowed on 64-bit arches
> (alpha?). This gave a negative value which gave further overflows
> or suprising sign extensions mainly when assigned to "u_long va_gen'";
> most other types were consistently signed.
> - the next 1997 version used random(). This fixed the generation of
> negative values. 0 was still generated
> - the 2003 version used arc4random(). This gave negative values again.
> 0 was still generated. This is essentially the current version. The
> current version uses a wrapper function like the first 1997 version.
> - newfs doesn't seem to have ever had the version that did *random() / 2
> + 1
> like the kernel did. It thus escaped having the overflow/sign extension
> bugs that the kernel had. Dividing by 2 was apparently supposed to avoid
> these bugs. It worked with random() since random() returns at most
> INT32_MAX. But arc4random() returns at mist UINT32_MAX. Dividing this
> by 2 gives (u_int)INT32_MAX and adding 1 gives a value that overflows
> when assigned to int32_t. This was later fixed by changing lots of
> int32_t to uint32_t.
>
> I'm not sure about the security aspects of randomizing i_gen. The re-
> randomization is so accidental and infrequent that security must be
> unimportant. But I think a unique generation (over all inodes on all
> file systems) would be better than any randomness. FreeBSD-1 was closer
> to having that -- i_gen was initialized to the global nextgennumber++ if
> it was zero; it was not incremented for inode use. The globabl would
> have to be 64 bits now. Ensuring uniqueness is not easy since it means
> that you have to check inode numbers on not-very-trusted newly mounted
> file systems against all inode numbers already in use. Perhaps it works
> to always use a new set for every new mount (ignore the ones on disk).
>
> Bruce
Yes, I have always wondered: who is detecting if we have a repeated
generation number, the end user? And then if we get a repeated
generation number and try to fix it, how do we know that a new
random value we generate to replace the duplicate is unused?
I am rather afraid to hear the answers :-/.
Pedro.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?b2633318-9e64-ab1f-4a21-931193eb4b36>