Messages in this thread
 Date Tue, 10 Jun 2014 12:14:01 -0400 From Theodore Ts'o <> Subject Re: [PATCH] random: mix all saved registers into entropy pool
`On Mon, May 19, 2014 at 05:17:19PM -0400, Jörn Engel wrote:> +/*> + * Ratelimit to a steady state of about once per jiffy.  A naïve approach> + * would be to return 1 every time jiffies changes.  But we want to avoid> + * being closely coupled to the timer interrupt.  So instead we increment> + * a counter on every call and shift it right every time jiffies changes.> + * If the counter is a power of two, return false;> + *> + * Effect is that some time after a jiffies change and cutting the counter> + * in half we reach another power of two and return false.  But the> + * likelihood of this happening is about the same at any time within a> + * jiffies interval.> + */> +static inline int ratelimited(struct fast_pool *p)> +{> +	int ret = !(p->regs_count == 0 || is_power_of_2(p->regs_count));> +> +	p->regs_count++;> +	if (p->last_shift != (u32)jiffies) {> +		p->regs_count >>= min(31u, (u32)jiffies - p->last_shift);> +		p->last_shift = (u32)jiffies;> +	}> +	return ret;> +}I wasn't convinced this would do the right thing, so I wrote a quicktest program where the main loop was basically this:	for (i=0; i < 1024; i++) {		jiffies = i >> 2;		r = ratelimited(jiffies);		printf("%5u %5u %5u %d\n", i, jiffies, regs_count, r);	}... which basically simulated a very simple scheme where there werefour interrupts for each clock tick.  In the steady state ratelimitedreturns true 75% of the time.  If this was as documented, we wouldexpect it to return true 25% of the time.  So I don't think this isworking quite right:   20     5     3 1   21     5     4 1   22     5     5 0   23     5     6 1   24     6     3 1   25     6     4 1   26     6     5 0   27     6     6 1   28     7     3 1   29     7     4 1   30     7     5 0   31     7     6 1   32     8     3 1> +static void mix_regs(struct pt_regs *regs, struct fast_pool *fast_pool)> +{> +	struct entropy_store	*r;> +	/* Two variables avoid decrementing by two without using atomics */> +	static int boot_count = BOOT_IRQS;> +	int in_boot = boot_count;> +> +	if (in_boot) {> +		boot_count = in_boot - 1;> +	} else if (ratelimited(fast_pool))> +		return;> +> +	/* During bootup we alternately feed both pools */> +	r = (in_boot & 1) ? &nonblocking_pool : &input_pool;> +	__mix_pool_bytes(r, regs, sizeof(*regs), NULL);> +}I'm also concerned about how much overhead this might eat up.  I'vealready had someone who was benchmarking a high performance storagearray where the increased interrupt latency before adding somethinglike this was something he noticed, and kvetched to me about.  Thept_regs structure is going to be larger than the fast_pool (which isonly 16 bytes), and we're going to be doing it once every jiffy, whichmeans between 100 and 1000 times per second.If we do this only during boot up, I'd be much less concerned, butdoing it all the time is making me a bit nervous about the overhead.If we knew which parts of the pt_regs were actually the "best" interms of entropy, we could xor that into the input[] array inadd_interrupt_randomness(), perhaps?  > -	input[0] = cycles ^ j_high ^ irq;> -	input[1] = now ^ c_high;> +	input[0] ^= cycles ^ j_high ^ irq;> +	input[1] ^= now ^ c_high;This is an unrelated change, so if you want to do this, let's discussthis on a separate commit.  We used to have something like this, butit causes static code checkers to complain about our using stackgarbage, and people argued convincingly that it really did add as muchunpredictability, especially when correlated with the ip field.(And yes, I know that instruction_pointer(regs) doesn't work on allplatforms, and _RET_IP_ becomes largely static --- but this is why I'dmuch rather have each architecture tell me which parts of regs wereactually the best, and use that as the initialized portions of theinput[] array.)Cheers,					- Ted--To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`

Last update: 2014-06-10 18:41    [W:0.117 / U:27.192 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site