On Fri 27 Sep 2019 at 21:12:13 +0200, Kamil Rytarowski wrote:
> Thank you for the analysis. Please prepare a patch and commit. Please
> add in the message:
>
> Reported-by: syzbot+68c37d09c833f8ec1341%syzkaller.appspotmail.com@localhost
How about this patch. I managed to avoid getting into 64-bit
calculations because I realised that all sample values are uint32_t.
Absolute delta values of those also fit into uint32_t. If you always do
the subtraction in the right order, you never even get a negative value
that you have to correct. Overall I also didn't introduce more
conditional jumps, but I have probably changed the amount of code in
each arm of the conditions.
For review, I left a bunch of //-comments in that I'd remove before
committing but they may be useful to follow the changes. Since the diff
may be a bit annoying to read, I also include the new version of the
code (it is all fairly closely together).
I compile-tested the below but have not run it.
--- kern_rndq.c.orig 2019-09-27 21:47:28.066249621 +0200
+++ kern_rndq.c 2019-09-27 22:44:13.307581068 +0200
@@ -324,22 +324,30 @@
* non-zero. If any of these are zero, return zero.
*/
static inline uint32_t
-rnd_delta_estimate(rnd_delta_t *d, uint32_t v, int32_t delta)
+rnd_delta_estimate(rnd_delta_t *d, uint32_t v, uint32_t delta)
{
- int32_t delta2, delta3;
+ uint32_t delta2, delta3;
d->insamples++;
/*
* Calculate the second and third order differentials
*/
- delta2 = d->dx - delta;
- if (delta2 < 0)
- delta2 = -delta2;
-
- delta3 = d->d2x - delta2;
- if (delta3 < 0)
- delta3 = -delta3;
+ if (delta > d->dx)
+ delta2 = delta - d->dx; // u32 - u32 makes u32
+ else
+ delta2 = d->dx - delta; // u32 - u32 makes u32
+ // can't happen anymore:
+// if (delta2 < 0)
+// delta2 = -delta2; /* back to ~32 bits */
+
+ if (delta2 > d->dx)
+ delta3 = delta2 - d->d2x; // u32 - u32 makes u32
+ else
+ delta3 = d->d2x - delta2; // u32 - u32 makes u32
+ // can't happen anymore:
+// if (delta3 < 0)
+// delta3 = -delta3;
d->x = v;
d->dx = delta;
@@ -357,24 +365,29 @@
}
/*
- * Delta estimator for 32-bit timeestamps. Must handle wrap.
+ * Delta estimator for 32-bit timestamps.
+ * Timestaps generally increase, but may wrap around to 0.
+ * If t decreases, it is assumed that wrap-around occurred (once).
*/
static inline uint32_t
rnd_dt_estimate(krndsource_t *rs, uint32_t t)
{
- int32_t delta;
+ uint32_t delta;
uint32_t ret;
rnd_delta_t *d = &rs->time_delta;
- if (t < d->x) {
- delta = UINT32_MAX - d->x + t;
+ if (t < (uint32_t)d->x) {
+ // t wrapped around
+ delta = UINT32_MAX - (uint32_t)d->x + t;
} else {
- delta = d->x - t;
+ // t >= d->x, the normal case of slightly increasing time
+ delta = t - (uint32_t)d->x;
}
- if (delta < 0) {
- delta = -delta;
- }
+// can't happen any more:
+// //if (delta < 0) {
+// delta = -delta;
+// }
ret = rnd_delta_estimate(d, t, delta);
@@ -391,21 +404,27 @@
}
/*
- * Delta estimator for 32 or bit values. "Wrap" isn't.
+ * Delta estimator for arbitrary unsigned 32 bit values.
*/
static inline uint32_t
rnd_dv_estimate(krndsource_t *rs, uint32_t v)
{
- int32_t delta;
+ uint32_t delta;
uint32_t ret;
rnd_delta_t *d = &rs->value_delta;
- delta = d->x - v;
-
- if (delta < 0) {
- delta = -delta;
+ if (v >= (uint32_t)d->x) {
+ // u32 - u32 makes u32
+ delta = v - (uint32_t)d->x;
+ } else {
+ delta = (uint32_t)d->x - v;
}
- ret = rnd_delta_estimate(d, v, (uint32_t)delta);
+
+ // can't happen anymore
+// if (delta < 0) {
+// delta = -delta;
+// }
+ ret = rnd_delta_estimate(d, v, delta);
KASSERT(d->x == v);
KASSERT(d->dx == delta);
-----
new code:
/*
* Use the timing/value of the event to estimate the entropy gathered.
* If all the differentials (first, second, and third) are non-zero, return
* non-zero. If any of these are zero, return zero.
*/
static inline uint32_t
rnd_delta_estimate(rnd_delta_t *d, uint32_t v, uint32_t delta)
{
uint32_t delta2, delta3;
d->insamples++;
/*
* Calculate the second and third order differentials
*/
if (delta > d->dx)
delta2 = delta - d->dx; // u32 - u32 makes u32
else
delta2 = d->dx - delta; // u32 - u32 makes u32
// can't happen anymore:
// if (delta2 < 0)
// delta2 = -delta2; /* back to ~32 bits */
if (delta2 > d->dx)
delta3 = delta2 - d->d2x; // u32 - u32 makes u32
else
delta3 = d->d2x - delta2; // u32 - u32 makes u32
// can't happen anymore:
// if (delta3 < 0)
// delta3 = -delta3;
d->x = v;
d->dx = delta;
d->d2x = delta2;
/*
* If any delta is 0, we got no entropy. If all are non-zero, we
* might have something.
*/
if (delta == 0 || delta2 == 0 || delta3 == 0)
return 0;
d->outbits++;
return 1;
}
/*
* Delta estimator for 32-bit timestamps.
* Timestaps generally increase, but may wrap around to 0.
* If t decreases, it is assumed that wrap-around occurred (once).
*/
static inline uint32_t
rnd_dt_estimate(krndsource_t *rs, uint32_t t)
{
uint32_t delta;
uint32_t ret;
rnd_delta_t *d = &rs->time_delta;
if (t < (uint32_t)d->x) {
// t wrapped around
delta = UINT32_MAX - (uint32_t)d->x + t;
} else {
// t >= d->x, the normal case of slightly increasing time
delta = t - (uint32_t)d->x;
}
// can't happen any more:
// //if (delta < 0) {
// delta = -delta;
// }
ret = rnd_delta_estimate(d, t, delta);
KASSERT(d->x == t);
KASSERT(d->dx == delta);
#ifdef RND_VERBOSE
if (deltacnt++ % 1151 == 0) {
rnd_printf_verbose("rnd_dt_estimate: %s x = %lld, dx = %lld, "
"d2x = %lld\n", rs->name,
(int)d->x, (int)d->dx, (int)d->d2x);
}
#endif
return ret;
}
/*
* Delta estimator for arbitrary unsigned 32 bit values.
*/
static inline uint32_t
rnd_dv_estimate(krndsource_t *rs, uint32_t v)
{
uint32_t delta;
uint32_t ret;
rnd_delta_t *d = &rs->value_delta;
if (v >= (uint32_t)d->x) {
// u32 - u32 makes u32
delta = v - (uint32_t)d->x;
} else {
delta = (uint32_t)d->x - v;
}
// can't happen anymore
// if (delta < 0) {
// delta = -delta;
// }
ret = rnd_delta_estimate(d, v, delta);
KASSERT(d->x == v);
KASSERT(d->dx == delta);
#ifdef RND_VERBOSE
if (deltacnt++ % 1151 == 0) {
rnd_printf_verbose("rnd_dv_estimate: %s x = %lld, dx = %lld, "
" d2x = %lld\n", rs->name,
(long long int)d->x,
(long long int)d->dx,
(long long int)d->d2x);
}
#endif
return ret;
}
-Olaf.
--
Olaf 'Rhialto' Seibert -- rhialto at falu dot nl
___ Anyone who is capable of getting themselves made President should on
\X/ no account be allowed to do the job. --Douglas Adams, "THGTTG"
Attachment:
signature.asc
Description: PGP signature