Signed overflow in ufs i_modrev calculation

Discussion:

Martin Natano

2016-01-27 08:52:02 UTC

In ufs, the calculation of i_modrev can produce signed overflow on 32
bit architectures (found on i386). The tv.tv_usec * 4294 calculation is
designed to move the microseconds part of a struct timeval to the upper
bits of an unsigned(!) 32 bit value to make room for simple i_modrev
increments, but the calculation is performed signed, causing overflow.
The diff below gets rid of the overflow by casting to unsigned first.

While there I replaced the union _qcvt/SETHIGH/SETLOW dance with simple
bitshift operations.

Index: ufs/ext2fs/ext2fs_subr.c
===================================================================
RCS file: /cvs/src/sys/ufs/ext2fs/ext2fs_subr.c,v
retrieving revision 1.33
diff -u -p -u -r1.33 ext2fs_subr.c
--- ufs/ext2fs/ext2fs_subr.c 14 Mar 2015 03:38:52 -0000 1.33
+++ ufs/ext2fs/ext2fs_subr.c 27 Jan 2016 08:26:05 -0000
@@ -49,25 +49,6 @@
#include <ufs/ext2fs/ext2fs_extern.h>
#include <ufs/ext2fs/ext2fs_extents.h>

-union _qcvt {
- int64_t qcvt;
- int32_t val[2];
-};
-
-#define SETHIGH(q, h) { \
- union _qcvt tmp; \
- tmp.qcvt = (q); \
- tmp.val[_QUAD_HIGHWORD] = (h); \
- (q) = tmp.qcvt; \
-}
-
-#define SETLOW(q, l) { \
- union _qcvt tmp; \
- tmp.qcvt = (q); \
- tmp.val[_QUAD_LOWWORD] = (l); \
- (q) = tmp.qcvt; \
-}
-
#ifdef _KERNEL

/*
@@ -220,8 +201,8 @@ ext2fs_vinit(struct mount *mp, struct vo

/* Initialize modrev times */
getmicrouptime(&tv);
- SETHIGH(ip->i_modrev, tv.tv_sec);
- SETLOW(ip->i_modrev, tv.tv_usec * 4294);
+ ip->i_modrev = (u_quad_t)tv.tv_sec << 32;
+ ip->i_modrev |= (u_quad_t)tv.tv_usec * 4294;

*vpp = vp;

Index: ufs/ufs/ufs_vnops.c
===================================================================
RCS file: /cvs/src/sys/ufs/ufs/ufs_vnops.c,v
retrieving revision 1.123
diff -u -p -u -r1.123 ufs_vnops.c
--- ufs/ufs/ufs_vnops.c 8 Dec 2015 15:31:01 -0000 1.123
+++ ufs/ufs/ufs_vnops.c 27 Jan 2016 08:26:10 -0000
@@ -78,24 +78,6 @@ int filt_ufswrite(struct knote *, long);
int filt_ufsvnode(struct knote *, long);
void filt_ufsdetach(struct knote *);

-union _qcvt {
- int64_t qcvt;
- int32_t val[2];
-};
-
-#define SETHIGH(q, h) { \
- union _qcvt tmp; \
- tmp.qcvt = (q); \
- tmp.val[_QUAD_HIGHWORD] = (h); \
- (q) = tmp.qcvt; \
-}
-#define SETLOW(q, l) { \
- union _qcvt tmp; \
- tmp.qcvt = (q); \
- tmp.val[_QUAD_LOWWORD] = (l); \
- (q) = tmp.qcvt; \
-}
-
/*
* A virgin directory (no blushing please).
*/
@@ -1879,8 +1861,8 @@ ufs_vinit(struct mount *mntp, struct vop
* Initialize modrev times
*/
getmicrouptime(&mtv);
- SETHIGH(ip->i_modrev, mtv.tv_sec);
- SETLOW(ip->i_modrev, mtv.tv_usec * 4294);
+ ip->i_modrev = (u_quad_t)mtv.tv_sec << 32;
+ ip->i_modrev |= (u_quad_t)mtv.tv_usec * 4294;
*vpp = vp;
return (0);
}

cheers,
natano

Mike Belopuhov

2016-01-27 11:27:46 UTC

Permalink

NetBSD have fixed this a while ago with a different construct
that produces different results compared to your code:

http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/ufs/ufs/ufs_vnops.c.diff?r1=1.105&r2=1.107

Basically the difference is that you propagate carry bits into the upper
part while neither current code nor NetBSD code do. Can you please
post an example you've used to test this?

But curiosity took the better of me. Why do we have to multiply
microseconds by 4294? Does this number come from 0xffffffff/(1000*1000)?

FreeBSD did something completely different here:

http://bxr.su/FreeBSD/sys/ufs/ffs/ffs_softdep.c#2681
http://bxr.su/FreeBSD/sys/fs/ext2fs/ext2_vnops.c#1515
http://bxr.su/FreeBSD/sys/kern/vfs_subr.c#4317

Since it's an NFS revision thing the lower part can be anything,
including as simple as (usec &~ 0xffff) to make some room for the
counter... I don't think propagating carry bits into the upper
part makes much sense.

Martin Natano

2016-01-27 13:21:06 UTC

Permalink

Post by Mike Belopuhov

NetBSD have fixed this a while ago with a different construct
http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/ufs/ufs/ufs_vnops.c.diff?r1=1.105&r2=1.107
Basically the difference is that you propagate carry bits into the upper
part while neither current code nor NetBSD code do. Can you please
post an example you've used to test this?

There won't be any carry. tv_usec contains the microsecond part of a
timestamp, so the expected range is [0, 1,000,000). 999,999 * 4294 is
less than 2^32.

***@watschnbaum:test$ cat test.c
#include <sys/time.h>
#include <stdio.h>

int
main(void)
{
struct timeval tv;
u_quad_t modrev;

tv.tv_sec = 0x42424242;
tv.tv_usec = 999999;

modrev = (u_quad_t)tv.tv_sec << 32;
printf("0x%llx\n", modrev);

modrev |= (u_quad_t)tv.tv_usec * 4294;
printf("0x%llx\n", modrev);

modrev++;
modrev++;
modrev++;
modrev++;
printf("0x%llx\n", modrev);

return 0;
}
***@watschnbaum:test$ cc test.c
***@watschnbaum:test$ ./a.out
0x4242424200000000
0x42424242fff12cba
0x42424242fff12cbe

Post by Mike Belopuhov
But curiosity took the better of me. Why do we have to multiply
microseconds by 4294? Does this number come from 0xffffffff/(1000*1000)?

Yes, 4294 is the largest factor for which the assumption that
tv_usec * factor < 2^32 holds true.

Post by Mike Belopuhov
http://bxr.su/FreeBSD/sys/ufs/ffs/ffs_softdep.c#2681
http://bxr.su/FreeBSD/sys/fs/ext2fs/ext2_vnops.c#1515
http://bxr.su/FreeBSD/sys/kern/vfs_subr.c#4317
Since it's an NFS revision thing the lower part can be anything,
including as simple as (usec &~ 0xffff) to make some room for the
counter... I don't think propagating carry bits into the upper
part makes much sense.

I don't think (usec &~ 0xffff) would be a good idea. The purpose of
multiplying usec is to make room, such that it is unlikely that
i_modrev will jump backwards when it is set again after a couple of
i_modrev++. Also, &~ 0xffff would just waste the upper 12 bits of the
lower half of i_modrev (always zero).

cheers,
natano

Mike Belopuhov

2016-01-27 14:21:22 UTC

Permalink

Post by Martin Natano

Post by Mike Belopuhov

There won't be any carry. tv_usec contains the microsecond part of a
timestamp, so the expected range is [0, 1,000,000). 999,999 * 4294 is
less than 2^32.

Fair enough. I didn't realize that there was an upper bound on the
value of usec, but it makes sense.

Post by Martin Natano

Post by Mike Belopuhov
But curiosity took the better of me. Why do we have to multiply
microseconds by 4294? Does this number come from 0xffffffff/(1000*1000)?

Yes, 4294 is the largest factor for which the assumption that
tv_usec * factor < 2^32 holds true.

I see now. Thanks for an explanation.

Post by Martin Natano

Mike Belopuhov

2016-02-03 17:23:14 UTC

Permalink

Any OKs or objections to this diff? This looks solid to me, FWIW.

Post by Martin Natano
In ufs, the calculation of i_modrev can produce signed overflow on 32
bit architectures (found on i386). The tv.tv_usec * 4294 calculation is
designed to move the microseconds part of a struct timeval to the upper
bits of an unsigned(!) 32 bit value to make room for simple i_modrev
increments, but the calculation is performed signed, causing overflow.
The diff below gets rid of the overflow by casting to unsigned first.
While there I replaced the union _qcvt/SETHIGH/SETLOW dance with simple
bitshift operations.
Index: ufs/ext2fs/ext2fs_subr.c
===================================================================
RCS file: /cvs/src/sys/ufs/ext2fs/ext2fs_subr.c,v
retrieving revision 1.33
diff -u -p -u -r1.33 ext2fs_subr.c
--- ufs/ext2fs/ext2fs_subr.c 14 Mar 2015 03:38:52 -0000 1.33
+++ ufs/ext2fs/ext2fs_subr.c 27 Jan 2016 08:26:05 -0000
@@ -49,25 +49,6 @@
#include <ufs/ext2fs/ext2fs_extern.h>
#include <ufs/ext2fs/ext2fs_extents.h>
-union _qcvt {
- int64_t qcvt;
- int32_t val[2];
-};
-
-#define SETHIGH(q, h) { \
- union _qcvt tmp; \
- tmp.qcvt = (q); \
- tmp.val[_QUAD_HIGHWORD] = (h); \
- (q) = tmp.qcvt; \
-}
-
-#define SETLOW(q, l) { \
- union _qcvt tmp; \
- tmp.qcvt = (q); \
- tmp.val[_QUAD_LOWWORD] = (l); \
- (q) = tmp.qcvt; \
-}
-
#ifdef _KERNEL
/*
@@ -220,8 +201,8 @@ ext2fs_vinit(struct mount *mp, struct vo
/* Initialize modrev times */
getmicrouptime(&tv);
- SETHIGH(ip->i_modrev, tv.tv_sec);
- SETLOW(ip->i_modrev, tv.tv_usec * 4294);
+ ip->i_modrev = (u_quad_t)tv.tv_sec << 32;
+ ip->i_modrev |= (u_quad_t)tv.tv_usec * 4294;
*vpp = vp;
Index: ufs/ufs/ufs_vnops.c
===================================================================
RCS file: /cvs/src/sys/ufs/ufs/ufs_vnops.c,v
retrieving revision 1.123
diff -u -p -u -r1.123 ufs_vnops.c
--- ufs/ufs/ufs_vnops.c 8 Dec 2015 15:31:01 -0000 1.123
+++ ufs/ufs/ufs_vnops.c 27 Jan 2016 08:26:10 -0000
@@ -78,24 +78,6 @@ int filt_ufswrite(struct knote *, long);
int filt_ufsvnode(struct knote *, long);
void filt_ufsdetach(struct knote *);
-union _qcvt {
- int64_t qcvt;
- int32_t val[2];
-};
-
-#define SETHIGH(q, h) { \
- union _qcvt tmp; \
- tmp.qcvt = (q); \
- tmp.val[_QUAD_HIGHWORD] = (h); \
- (q) = tmp.qcvt; \
-}
-#define SETLOW(q, l) { \
- union _qcvt tmp; \
- tmp.qcvt = (q); \
- tmp.val[_QUAD_LOWWORD] = (l); \
- (q) = tmp.qcvt; \
-}
-
/*
* A virgin directory (no blushing please).
*/
@@ -1879,8 +1861,8 @@ ufs_vinit(struct mount *mntp, struct vop
* Initialize modrev times
*/
getmicrouptime(&mtv);
- SETHIGH(ip->i_modrev, mtv.tv_sec);
- SETLOW(ip->i_modrev, mtv.tv_usec * 4294);
+ ip->i_modrev = (u_quad_t)mtv.tv_sec << 32;
+ ip->i_modrev |= (u_quad_t)mtv.tv_usec * 4294;
*vpp = vp;
return (0);
}
cheers,
natano

Stefan Kempf

2016-02-03 17:41:24 UTC

Permalink

Post by Mike Belopuhov
Any OKs or objections to this diff? This looks solid to me, FWIW.

Looks good to me as well.

Post by Mike Belopuhov

Mike Belopuhov

2016-02-04 12:46:03 UTC

Permalink

Committed, thanks!