random periodicity detection fix

The input layer is now sending us a bunch of events in a row for each actual event. This shows up weaknesses in the periodicity detector and using the high clock rate from get_clock: each keystroke is getting accounted as 10 different tmaximal-entropy events.

A brief touch on a trackpad will generate as much as 2000 maximal entropy events which is more than 2k of /dev/random output. IOW, we're WAY overestimating input entropy. Here's one keystroke:

random 0024 0000 0000: mouse event
random 0035 0000 0000: added 11 entropy credits to input
random 0035 0000 0000: mouse event
random 0046 0000 0000: added 11 entropy credits to input
random 0046 0000 0000: mouse event
random 0056 0000 0000: added 10 entropy credits to input
random 0056 0000 0000: keyboard event
random 0067 0000 0000: added 11 entropy credits to input
random 0067 0000 0000: mouse event
random 0078 0000 0000: added 11 entropy credits to input
random 0078 0000 0000: awake
random 0078 0000 0000: reading 128 bits
random 0078 0000 0000: going to reseed blocking with 128 bits (128 of 0 requested) random 0078 0000 0000: trying to extract 128 bits from input
random 0006 0000 0000: debiting 72 entropy credits from input
random 0006 0072 0000: added 72 entropy credits to blocking
random 0006 0072 0000: trying to extract 128 bits from blocking random 0006 0000 0000: debiting 72 entropy credits from blocking random 0006 0000 0000: read got 72 bits (56 still needed)
random 0006 0000 0000: reading 56 bits
random 0006 0000 0000: going to reseed blocking with 64 bits (56 of 0 requested random 0006 0000 0000: trying to extract 64 bits from input
random 0006 0000 0000: debiting 0 entropy credits from input
random 0006 0000 0000: trying to extract 56 bits from blocking
random 0006 0000 0000: debiting 0 entropy credits from blocking random 0006 0000 0000: read got 0 bits (56 still needed)
random 0006 0000 0000: sleeping
random 0006 0000 0000: mouse event
random 0017 0000 0000: added 11 entropy credits to input
random 0017 0000 0000: mouse event
random 0028 0000 0000: added 11 entropy credits to input
random 0028 0000 0000: mouse event
random 0038 0000 0000: added 10 entropy credits to input
random 0038 0000 0000: keyboard event
random 0049 0000 0000: added 11 entropy credits to input
random 0049 0000 0000: mouse event
random 0060 0000 0000: added 11 entropy credits to input

The first step to fixing this is to check periodicity and estimate entropy against a slow clock like jiffies. We continue to mix in get_clock() rather than jiffies where available.

This throws away most of the duplicate events and gives us more sensible entropy estimates, but we still duplicates from input.c and keyboard.c.

Index: rnd/drivers/char/random.c
===================================================================
@@ -805,8 +805,8 @@
  */
 static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 {
-	cycles_t time;
-	long delta, delta2, delta3;
+	cycles_t data;
+	long delta, delta2, delta3, time;
 	int entropy = 0;
 
 	preempt_disable();

@@ -816,20 +816,12 @@
 		goto out;
 
 	/*
-	 * Use get_cycles() if implemented, otherwise fall back to
-	 * jiffies.
-	 */
-	time = get_cycles();
-	if (time)
-		num ^= (u32)((time >> 31) >> 1);
-	else
-		time = jiffies;
-
-	/*
 	 * Calculate number of bits of randomness we probably added.
 	 * We take into account the first, second and third-order deltas
 	 * in order to make our estimate.
 	 */
+	time = jiffies;
+
 	if (!state->dont_count_entropy) {
 		delta = time - state->last_time;
 		state->last_time = time;

@@ -861,7 +853,18 @@
 
 		entropy = int_ln_12bits(delta);
 	}
-	batch_entropy_store(num, time, entropy);
+
+	/*
+	 * Use get_cycles() if implemented, otherwise fall back to
+	 * jiffies.
+	 */
+	data = get_cycles();
+	if (data)
+		num ^= (u32)((data >> 31) >> 1);
+	else
+		data = time;
+
+	batch_entropy_store(num, data, entropy);
 out:
 	preempt_enable();
 }

Mathematics is the supreme nostalgia of our time.

Yes, indeed. I muttered about this long ago - let me see, yes,
http://marc.theaimsgroup.com/?l=linux-kernel&m=106271659930542&w=3

My patch did the opposite of your patch: I removed the add entropy call in input.c.

I don't recall the details, but I think my reason was that some events are synthetic, and I wanted all entropy calls to be derived from actual outside sources.

Also, when there are several sources, all constant or almost constant, then merging the streams might cause one to see variation where there isn't really any.
Also that is a reason not to do the adding so far away from the source.

Andries

Unfortunately almost all the original call sites have been dropped, so it's now easier to do it this way.

Further, the input folks can't be relied upon to do the right thing, so it's better to grab _all_ the relevant data in one place and do our own filtering. 5/5 is a step in that direction, but the filtering is currently primitive.

Eventually we can do as gendisk does and embed a pointer to an entropy_state in the input objects and get back to all devices being monitored independently.

I've got a few dozen more /dev/random cleanup patches to push before that happens though.

Agreed. Not a huge problem for input as the sources are all really a single console user (or so), but I'd like to check periodicity per-device and globally eventually.

Mathematics is the supreme nostalgia of our time.