random32: Various minor cleanups
Subsystems (3)
cover random32: Various minor cleanups
I was looking for self-test code to emulate for lib/glob.c and, while canvassing other code with self-tests, found some code that made me itch, so I scratched it.
7 patches;
1/7: Mark the self-test data as __initconst
2/7: Remove excess calls to prandom_u32_state in initialization 3/7: Replace an #ifdef with a stub prandom_state_selftest() 4/7: Use <asm/unaligned.h> instead of hand-rolling it 5/7: Make prandom_u32_max efficient for powers of 2 6/7: Randomize timeout to the millisecond, not the second 7/7: Remove redundant U suffixes on integers
I have a big follow-on patch series to replace all the (many) instances of "prandom_u32() % x" in the kernel with prandom_u32_max(x), which is more efficient.
As of patch 5/7, "prandom_u32() & (x-1)" can also be replaced by "prandom_u32_max(x)", but that's optional.
Patch 6/7 is dubious, and I'd like comments. I just don't see a reason why integer granularity would be desirable.
PATCH 1/7 lib/random32.c: Mark self-test data as __initconst
So it can be thrown away along with the code that uses it.
--- lib/random32.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
lib/random32.c +2 -2
@@ -296,7 +296,7 @@ late_initcall(prandom_reseed);static struct prandom_test1 {u32 seed;u32 result; -} test1[] = { +}const test1[]__initconst = { {1U ,3484351685U }, {2U ,2623130059U }, {3U ,3125133893U },
@@ -307,7 +307,7 @@ static struct prandom_test2 {u32 seed;u32 iteration;u32 result; -} test2[] = { +} const test2[] __initconst = {/* Test cases against taus113 from GSL library. */ {931557656U ,959U ,2975593782U }, {1339693295U ,876U ,3887776532U },
Signature · 1 line
2.0.0
Re: [PATCH 1/7] lib/random32.c: Mark self-test data as __initconst
Quoted 3 lines · George Spelvin
So it can be thrown away along with the code that uses it.
Signed-off-by George Spelvin <[email protected]>
Fine by me.
PATCH 2/7 lib/random32.c: Remove excess calls to prandom_u32_state in initialization
In reply to George SpelvinUnrolling code in single-use code paths is just silly. There are two instances:
1) prandom_warmup() calls 10 times.
2) prandom_state_selftest() can avoid one call and simplify the loop logic by repeating an assignment to a local variable (that probably adds zero code anyway)
--- lib/random32.c | 21 ++++++++------------- 1 file changed, 8 insertions(+), 13 deletions(-)
lib/random32.c +8 -13
@@ -134,17 +134,11 @@ EXPORT_SYMBOL(prandom_bytes);static void prandom_warmup (struct rnd_state *state) { +int i; +/* Calling RNG ten times to satify recurrence condition */ -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); +for (i =0 ; i <10 ; i++) +prandom_u32_state (state); }static void prandom_seed_very_weak (struct rnd_state *state,u32 seed)
@@ -433,14 +427,15 @@ static void __init prandom_state_selftest(void)for (i =0 ; i <ARRAY_SIZE (test2); i++) {struct rnd_state state; +u32 result;prandom_seed_very_weak (&state, test2[i].seed);prandom_warmup (&state); -for (j =0 ; j < test2[i].iteration -1 ; j++) -prandom_u32_state (&state); +for (j =0 ; j < test2[i].iteration; j++) + result =prandom_u32_state (&state); -if (test2[i].result !=prandom_u32_state (&state)) +if (test2[i].result != result) errors++; runs++;
Signature · 1 line
2.0.0
Re: [PATCH 2/7] lib/random32.c: Remove excess calls to prandom_u32_state in initialization
Quoted 9 lines · George Spelvin
Unrolling code in single-use code paths is just silly. There are two instances:
1)
prandom_warmup()calls 10 times.
2)prandom_state_selftest()can avoid one call and simplify the loop logic by repeating an assignment to a local variable (that probably adds zero code anyway)Signed-off-by George Spelvin <[email protected]>
Fine by me although we simply resembled initialization code from GSL here. I think that your subject line is a bit misleading though.
Quoted 50 lines
--- lib/random32.c | 21 ++++++++------------- 1 file changed, 8 insertions(+), 13 deletions(-)lib/random32.c +8
-13@@ -134,17 +134,11 @@ EXPORT_SYMBOL(prandom_bytes);static void prandom_warmup (struct rnd_state *state) { +int i; +/* Calling RNG ten times to satify recurrence condition */ -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); -prandom_u32_state (state); +for (i =0 ; i <10 ; i++) +prandom_u32_state (state); }static void prandom_seed_very_weak (struct rnd_state *state,u32 seed)@@ -433,14 +427,15 @@ static void __init prandom_state_selftest(void)for (i =0 ; i <ARRAY_SIZE (test2); i++) {struct rnd_state state; +u32 result;prandom_seed_very_weak (&state, test2[i].seed);prandom_warmup (&state); -for (j =0 ; j < test2[i].iteration -1 ; j++) -prandom_u32_state (&state); +for (j =0 ; j < test2[i].iteration; j++) + result =prandom_u32_state (&state); -if (test2[i].result !=prandom_u32_state (&state)) +if (test2[i].result != result) errors++; runs++;
Re: [PATCH 2/7] lib/random32.c: Remove excess calls to prandom_u32_state in initialization
Thank you for your time and attention on all these comments.
Quoted 2 lines
Fine by me although we simply resembled initialization code from GSL here. I think that your subject line is a bit misleading though.
Yes, I had a hard time coming up with a good summary. I'm removing *static* calls but not dynamic ones.
How about "don't unroll one-time initialization code"? Would that be a better way to put it?
PATCH 3/7 lib/random32.c: Replace an #ifdef with a stub prandom_state_selftest()
In reply to George SpelvinThe preferred Linux style for optional features is to define no-op stub functions rather than wrap each call site in #ifdef.
--- lib/random32.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
lib/random32.c +2 -2
@@ -40,6 +40,8 @@#ifdef CONFIG_RANDOM32_SELFTEST static void __init prandom_state_selftest (void ); +#else +#define prandom_state_selftest () (void)0#endif static DEFINE_PER_CPU(struct rnd_state, net_rand_state);
@@ -188,9 +190,7 @@ static int __init prandom_init(void) {int i; -#ifdef CONFIG_RANDOM32_SELFTEST prandom_state_selftest (); -#endif for_each_possible_cpu (i) {struct rnd_state *state = &per_cpu (net_rand_state,i);
Signature · 1 line
2.0.0
Re: [PATCH 3/7] lib/random32.c: Replace an #ifdef with a stub prandom_state_selftest()
Quoted 13 lines · George Spelvin
The preferred Linux style for optional features is to define no-op stub functions rather than wrap each call site in #ifdef.
Signed-off-by George Spelvin <[email protected]>--- lib/random32.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)lib/random32.c +0
-0
lib/random32.c line 44
Quoted 5 lines
lib/random32.c +2
-0@@ -40,6 +40,8 @@#ifdef CONFIG_RANDOM32_SELFTEST static void __init prandom_state_selftest (void ); +#else +#define prandom_state_selftest () (void)0
Fine by me. I think you can remove this '(void)0' here, though.
Quoted 14 lines
lib/random32.c +0
-2#endif static DEFINE_PER_CPU(struct rnd_state, net_rand_state);@@ -188,9 +190,7 @@ static int __init prandom_init(void) {int i; -#ifdef CONFIG_RANDOM32_SELFTEST prandom_state_selftest (); -#endif for_each_possible_cpu (i) {struct rnd_state *state = &per_cpu (net_rand_state,i);
Re: [PATCH 3/7] lib/random32.c: Replace an #ifdef with a stub prandom_state_selftest()
Quoted 6 lines
lib/random32.c line 44
Quoted 4 lines
#ifdef CONFIG_RANDOM32_SELFTEST static void __init prandom_state_selftest(void);lib/random32.c +2
-0+#else +#define prandom_state_selftest () (void)0Fine by me. I think you can remove this '(void)0' here, though.
That's the standard way to write a no-op statement in C.
I seem to recall there's a reason that the empty string can cause problems in some syntactic contexts, but I can't figure out what the situation is.
At first, I thought of the obvious:
if (condition)
prandom_state_selftest();
unconditional_code();
... but the semicolon makes that work. I'll try to remember the reason.
(I know that nobody uses it in any such context, but it's good manners to make a function-like macro behave as exactly like a function as possible.)
PATCH 4/7 lib/random32.c: Use <asm/unaligned.h> instead of hand-rolling it
In reply to George SpelvinThe functions exist for a reason; the manual byte-at-a-time code is unnecessarily slow (and bloated).
--- lib/random32.c | 23 +++++++++++------------ 1 file changed, 11 insertions(+), 12 deletions(-)
lib/random32.c +11 -12
@@ -37,6 +37,7 @@#include <linux/jiffies.h> #include <linux/random.h> #include <linux/sched.h> +#include <asm/unaligned.h> #ifdef CONFIG_RANDOM32_SELFTEST static void __init prandom_state_selftest (void );
@@ -97,25 +98,23 @@ EXPORT_SYMBOL(prandom_u32);*/ void prandom_bytes_state (struct rnd_state *state,void *buf,int bytes) { -unsigned char *p = buf; +u8 *p = buf;int i; -for (i =0 ; i <round_down (bytes,sizeof (u32)); i +=sizeof (u32)) { -u32 random =prandom_u32_state (state); -int j; +for (i =0 ; i <round_down (bytes,sizeof (u32)); i +=sizeof (u32)) +put_unaligned_le32 (prandom_u32_state (state), p+i); -for (j =0 ; j <sizeof (u32); j++) { - p[i + j] = random; - random >>=BITS_PER_BYTE ; - } - }if (i < bytes) {u32 random =prandom_u32_state (state); -for (; i < bytes; i++) { - p[i] = random; - random >>=BITS_PER_BYTE ; +if (bytes &2 ) { +put_unaligned_le16 ((u16 )random, p+i); +if ((bytes &1 ) ==0 ) +return ; + i +=2 ; + random >>=16 ; } + p[i] = (u8 )random; } }EXPORT_SYMBOL (prandom_bytes_state);
Signature · 1 line
2.0.0
Re: [PATCH 4/7] lib/random32.c: Use <asm/unaligned.h> instead of hand-rolling it
Quoted 4 lines · George Spelvin
The functions exist for a reason; the manual byte-at-a-time code is unnecessarily slow (and bloated).
Signed-off-by George Spelvin <[email protected]>
Seems fine by me, since it's random anyway archs might not care about the *_le32, though this might yield additional work in some cases I presume.
Quoted 19 lines
--- lib/random32.c | 23 +++++++++++------------ 1 file changed, 11 insertions(+), 12 deletions(-)lib/random32.c +1
-0@@ -37,6 +37,7 @@#include <linux/jiffies.h> #include <linux/random.h> #include <linux/sched.h> +#include <asm/unaligned.h> #ifdef CONFIG_RANDOM32_SELFTEST static void __init prandom_state_selftest (void );@@ -97,25 +98,23 @@ EXPORT_SYMBOL(prandom_u32);*/ void prandom_bytes_state (struct rnd_state *state,void *buf,int bytes)
lib/random32.c EXPORT_SYMBOL(prandom_u32); · line 105
Quoted 10 lines
lib/random32.c +3
-4{ -unsigned char *p = buf; +u8 *p = buf;int i; -for (i =0 ; i <round_down (bytes,sizeof (u32)); i +=sizeof (u32)) { -u32 random =prandom_u32_state (state); -int j; +for (i =0 ; i <round_down (bytes,sizeof (u32)); i +=sizeof (u32)) +put_unaligned_le32 (prandom_u32_state (state), p+i);
Nit: 'p + i'
Quoted 4 lines
lib/random32.c +0
-3-for (j =0 ; j <sizeof (u32); j++) { - p[i + j] = random; - random >>=BITS_PER_BYTE ;
lib/random32.c EXPORT_SYMBOL(prandom_u32); · line 111
Quoted 10 lines
lib/random32.c +2
-5- } - }if (i < bytes) {u32 random =prandom_u32_state (state); -for (; i < bytes; i++) { - p[i] = random; - random >>=BITS_PER_BYTE ; +if (bytes &2 ) { +put_unaligned_le16 ((u16 )random, p+i);
Ditto.
lib/random32.c EXPORT_SYMBOL(prandom_u32); · line 117
Quoted 6 lines
lib/random32.c +5
-0+if ((bytes &1 ) ==0 ) +return ; + i +=2 ; + random >>=16 ; } + p[i] = (u8 )random;
Nit: '(u8) random'
You could probably use a switch statement with fall-through for filling the remaining stuff, might simplify it further, perhaps.
Quoted 4 lines
lib/random32.c +0
-0} }EXPORT_SYMBOL (prandom_bytes_state);
Re: [PATCH 4/7] lib/random32.c: Use <asm/unaligned.h> instead of hand-rolling it
Quoted 3 lines
Seems fine by me, since it's random anyway archs might not care about the
*_le32, though this might yield additional work in some cases I presume.
If you think that's okay, sure. I kept it consistent to get byte-for-byte identical results.
If variations in that are allowed, that can also
simplify the trailing storage case:
+ if (bytes & 2)
+ put_unaligned_le16((u16)random, p+i);
+ if (bytes & 1)
+ p[i+bytes-1] = (u8)(random >> 16);
Quoted 4 lines
lib/random32.c EXPORT_SYMBOL(prandom_u32); · line 105
Quoted 2 lines
lib/random32.c +2
-0+for (i =0 ; i <round_down (bytes,sizeof (u32)); i +=sizeof (u32)) +put_unaligned_le32 (prandom_u32_state (state), p+i);Nit: 'p + i'
I don't really care, but I'm happy without the spaces; I add them to show what binds more weakly, and in this case that's the argument-separating comma.
Quoted 3 lines
lib/random32.c EXPORT_SYMBOL(prandom_u32); · line 117
Quoted 1 line
lib/random32.c +1
-0+ p[i] = (u8 )random;Nit: '(u8) random'
Actually, my style and most of the kerel is to not put a space in a cast, since it binds so tighty.
E.g. compare
git grep ')[a-z]' kernel/
git grep ') [a-z]' kernel/
Notice that the second is alsmost all comments.
(There are some spaces in kernel/ptrace.v.)
I'd rather leave it without the space unless you feel very strongly about it.
Re: [PATCH 4/7] lib/random32.c: Use <asm/unaligned.h> instead of hand-rolling it
Quoted 10 lines · George Spelvin
Quoted 3 lines
Seems fine by me, since it's random anyway archs might not care about the
*_le32, though this might yield additional work in some cases I presume.If you think that's okay, sure. I kept it consistent to get byte-for-byte identical results.
If variations in that are allowed, that can also simplify the trailing storage case:
Review
Quoted 4 lines
(quoted diff) +4
-0+ if (bytes & 2) + put_unaligned_le16((u16)random, p+i); + if (bytes & 1) + p[i+bytes-1] = (u8)(random >> 16);
Yes, please! Otherwise the code looks much too complicated for what it does.
Quoted 7 lines
Quoted 1 line
Nit: '(u8) random'
Actually, my style and most of the kerel is to not put a space in a cast, since it binds so tighty.
E.g. compare
Quoted 8 lines
git grep ')[a-z]'
kernel/
git grep ') [a-z]'kernel/Notice that the second is alsmost all comments. (There are some spaces in
kernel/ptrace.v.)I'd rather leave it without the space unless you feel very strongly about it.
IMHO I wouldn't put a whitespace here.
Bye,
Hannes
Re: [PATCH 4/7] lib/random32.c: Use <asm/unaligned.h> instead of hand-rolling it
In reply to George SpelvinOn 06/08/2014 02:40 PM, George Spelvin wrote:
...
Quoted 8 lines
Quoted 4 lines
lib/random32.c EXPORT_SYMBOL(prandom_u32); · line 105
Quoted 2 lines
lib/random32.c +2
-0+for (i =0 ; i <round_down (bytes,sizeof (u32)); i +=sizeof (u32)) +put_unaligned_le32 (prandom_u32_state (state), p+i);Nit: 'p + i'
I don't really care, but I'm happy without the spaces; I add them to show what binds more weakly, and in this case that's the argument-separating comma.
If you invent such things, then first send a patch to Documentation/CodingStyle to change and discuss this.
Otherwise, I urge you to read:
vi Documentation/CodingStyle +206
PATCH 5/7 lib/random32.c: Make prandom_u32_max efficient for powers of 2
In reply to George SpelvinThe multiply-and-shift is efficient in the general case, but slower than a simple bitwise AND if the range is a power of 2. Make the function handle this case so callers don't have to worry about micro-optimizing it.
--- include/linux/random.h | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-)
include/linux/random.h +13 -1
@@ -47,11 +47,23 @@ void prandom_bytes_state(struct rnd_state *state, void *buf, int nbytes);* generator, that is, prandom_u32(). This is useful when requesting a * random index of an array containing ep_ro elements, for example. * +* If ep_ro is a power of 2 known at compile time, a modulo operation +* reduces to a simple mask to extract the low order bits. Otherwise, +* it uses a multiply and shift, which is faster than a general modulus. +* * Returns: pseudo-random number in interval [0, ep_ro) */ static inline u32 prandom_u32_max (u32 ep_ro) { -return (u32)(((u64 )prandom_u32 () * ep_ro) >>32 ); +/* +* Instead of just __builtin_constant_p(ep_ro), this test is +* "is it known at compile time that ep_ro is a power of 2?", and +* can in theory handle the case that it's an unknown power of 2. +*/ +if (__builtin_constant_p (ep_ro & (ep_ro-1 )) && !(ep_ro & (ep_ro-1 ))) +return prandom_u32 () & (ep_ro-1 ); +else +return (u32)((u64 )prandom_u32 () * ep_ro >>32 ); }/*
Signature · 1 line
2.0.0
Re: [PATCH 5/7] lib/random32.c: Make prandom_u32_max efficient for powers of 2
Quoted 25 lines · George Spelvin
The multiply-and-shift is efficient in the general case, but slower than a simple bitwise AND if the range is a power of 2. Make the function handle this case so callers don't have to worry about micro-optimizing it.
Signed-off-by George Spelvin <[email protected]>--- include/linux/random.h | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-)include/linux/random.h +4
-0@@ -47,11 +47,23 @@ void prandom_bytes_state(struct rnd_state *state, void *buf, int nbytes);* generator, that is, prandom_u32(). This is useful when requesting a * random index of an array containing ep_ro elements, for example. * +* If ep_ro is a power of 2 known at compile time, a modulo operation +* reduces to a simple mask to extract the low order bits. Otherwise, +* it uses a multiply and shift, which is faster than a general modulus. +* * Returns: pseudo-random number in interval [0, ep_ro) */ static inline u32 prandom_u32_max (u32 ep_ro) {
include/linux/random.h void prandom_bytes_state(struct rnd_state *state, void *buf, int nbytes); · line 66
Quoted 10 lines
include/linux/random.h +9
-1-return (u32)(((u64 )prandom_u32 () * ep_ro) >>32 ); +/* +* Instead of just __builtin_constant_p(ep_ro), this test is +* "is it known at compile time that ep_ro is a power of 2?", and +* can in theory handle the case that it's an unknown power of 2. +*/ +if (__builtin_constant_p (ep_ro & (ep_ro-1 )) && !(ep_ro & (ep_ro-1 ))) +return prandom_u32 () & (ep_ro-1 ); +else +return (u32)((u64 )prandom_u32 () * ep_ro >>32 );
Okay, I guess it's fine since we expect a random number here anyway, so it doesn't matter much how we get to the result; otherwise I'd have complained as both function don't do the same thing. Please leave some whitespace, i.e. I mean "ep_ro-1" -> "ep_ro - 1".
Btw, there are many other users which hard code prandom_u32_max() resp. reciprocal_scale() function in the source tree. If you have some cycles, feel free to migrate them and let them use these functions.
Quoted 4 lines
include/linux/random.h +0
-0}/*
Re: [PATCH 5/7] lib/random32.c: Make prandom_u32_max efficient for powers of 2
In reply to George SpelvinQuoted 17 lines · George Spelvin
include/linux/random.h +4
-1@@ -47,11 +47,23 @@ void prandom_bytes_state(struct rnd_state *state, void *buf, int nbytes);* generator, that is, prandom_u32(). This is useful when requesting a * random index of an array containing ep_ro elements, for example. * +* If ep_ro is a power of 2 known at compile time, a modulo operation +* reduces to a simple mask to extract the low order bits. Otherwise, +* it uses a multiply and shift, which is faster than a general modulus. +* * Returns: pseudo-random number in interval [0, ep_ro) */ static inline u32 prandom_u32_max (u32 ep_ro) { -return (u32)(((u64 )prandom_u32 () * ep_ro) >>32 );
include/linux/random.h void prandom_bytes_state(struct rnd_state *state, void *buf, int nbytes); · line 67
Quoted 10 lines
include/linux/random.h +9
-0+/* +* Instead of just __builtin_constant_p(ep_ro), this test is +* "is it known at compile time that ep_ro is a power of 2?", and +* can in theory handle the case that it's an unknown power of 2. +*/ +if (__builtin_constant_p (ep_ro & (ep_ro-1 )) && !(ep_ro & (ep_ro-1 ))) +return prandom_u32 () & (ep_ro-1 ); +else +return (u32)((u64 )prandom_u32 () * ep_ro >>32 ); }
Have you checked assembler output if this helps anything at all? Constant propagation in the compiler should be able to figure that out all by itself. The only places I use __builtin_constant_p today are where I also make use of inline assembler.
Please check this as it makes the code more complicated and I doubt it is worth it.
Btw, IIRC there is a function is_power_of_2 somewhere. ;)
Thanks,
Hannes
Re: [PATCH 5/7] lib/random32.c: Make prandom_u32_max efficient for powers of 2
On 06/08/2014 07:34 PM, Hannes Frederic Sowa wrote:
...
Quoted 1 line
Please check this as it makes the code more complicated and I doubt it is worth it.
Agreed.
Re: [PATCH 5/7] lib/random32.c: Make prandom_u32_max efficient for powers of 2
Quoted 4 lines · Daniel Borkmann
Quoted 1 line · Hannes Frederic Sowa
Please check this as it makes the code more complicated and I doubt it is worth it.
Agreed.
Just to clarify, the goal is to be able to replace "prandom_u32() % range" all over the kernel with "prandom_u32_max(range)" and promise people that it's guaranteed to be just as good.
My goal is a one-time cleanup to eliminate "prandom_u32() % range" so people will stop cutting and pasting it into new code.
(FIXME: Add a kdoc update on the subject.)
It uglifies the random32 code for sure, but by encapsulating the cleverness it lets all the call sites be simpler and reduces arguments about the change.
E.g. have a look at all the prandom_u32 calls in net/core/pktgen.c.
Re: [PATCH 5/7] lib/random32.c: Make prandom_u32_max efficient for powers of 2
In reply to Hannes Frederic SowaThank you for your comments!
Quoted 4 lines
Have you checked assembler output if this helps anything at all? Constant propagation in the compiler should be able to figure that out all by itself. The only places I use
__builtin_constant_ptoday are where I also make use of inline assembler.
Yes, I did. (I'll expand the commit comment for v2; my bad.)
It seems that GCC isn't smart enough to reduce this to a single shift. With the multiply and reduce, the code looks like:
call prandom_u32
xorl %edx, %edx
shldl $4, %eax, %edx
movl %edx, %eaxInstead of the hoped-for
call prandom_u32 shrl $28, %eax
Converting to a single mask is something the compiler can't do, because it doesn't understand that using the lsbits instead of the msbits is okay.
With the mask, it turns into the spectacularly simple:
call prandom_u32
andl $15, %eaxAn interesting question is which is preferred in general.
The AND allows non-constant powers of 2 without requiring CLZ. But I don't recall seeing that actually happen anywhere. And the shift allows a smaller encoding (8-bit rather than 32-bit immediate constant) when the power of 2 is known at compile time and is larger than 128 (for example, PAGE_SIZE).
Me, I thought it was in the noise and not worth stressing about, but I also understand the hackers's urge for maximum tweaking.
The other thing that I couldn't think of a clean wrapper for is the "probability 1 in N" case that happens in several bits of code. For example, in drivers/mtd/ubi/debug.h, I made the following change:
static inline int ubi_dbg_is_bitflip(const struct ubi_device *ubi) {
- if (ubi->dbg.emulate_bitflips)
- return !(prandom_u32() % 200);
- return 0;
+ return ubi->dbg.emulate_bitflips && prandom_u32() < -1u/200;
}
GCC doesn't know how to optimize "prandom_u32_max(200) == 0", which is basically the same. It spits out:
call prandom_u32
movl %eax, %edx
movl $200, %eax
mull %edx
testl %edx, %edxI couldn't think of a good enough function name for this, so I just left it as inline code. (Using "-1u/200" rather than the technically correct "(u32)(((u64)1 << 32)/200)" is okay as long as 200 isn't a power of 2, and even if it were, the error wouldn't matter since it's approximate anyway.)
Quoted 1 line
Btw, IIRC there is a function
is_power_of_2somewhere. ;)
In <linux/log2.h>; thanks for the pointer.
Re: [PATCH 5/7] lib/random32.c: Make prandom_u32_max efficient for powers of 2
Thanks for your detailed explanation!
Quoted 11 lines · George Spelvin
Thank you for your comments!
Quoted 4 lines
Have you checked assembler output if this helps anything at all? Constant propagation in the compiler should be able to figure that out all by itself. The only places I use
__builtin_constant_ptoday are where I also make use of inline assembler.Yes, I did. (I'll expand the commit comment for v2; my bad.)
It seems that GCC isn't smart enough to reduce this to a single shift. With the multiply and reduce, the code looks like:
Quoted 8 lines
call prandom_u32 xorl %edx, %edx shldl $4, %eax, %edx movl %edx, %eaxInstead of the hoped-for
call prandom_u32 shrl $28, %eax
On x86_64 I get the above result. Seems like gcc doesn't see the downcast to u32 far enough ahead and stays in DI mode on i386, thus the shldl. It shouldn't matter that much... ;)
Quoted 3 lines
Converting to a single mask is something the compiler can't do, because it doesn't understand that using the lsbits instead of the msbits is okay.
Yep, sure.
Quoted 11 lines
With the mask, it turns into the spectacularly simple:
call prandom_u32 andl $15, %eaxAn interesting question is which is preferred in general.
The AND allows non-constant powers of 2 without requiring CLZ. But I don't recall seeing that actually happen anywhere. And the shift allows a smaller encoding (8-bit rather than 32-bit immediate constant) when the power of 2 is known at compile time and is larger than 128 (for example,
PAGE_SIZE).
I actually don't know if folding logic in gcc is so enhanced to see that coming. ;) Would be interesting tough, maybe I'll try that later.
Quoted 2 lines
Me, I thought it was in the noise and not worth stressing about, but I also understand the hackers's urge for maximum tweaking.
Totally ok. ;)
I don't have any problems with the patch, although such a detailed changelog would be nice + some approx. numbers of how many times we run into the new optimization.
Bye,
Hannes
PATCH 6/7 lib/random32.c: Randomize timeout to the millisecond, not the second
In reply to George SpelvinIf you're going to bother randomizing it, do it right. And use prandom_u32_max(), which is designed for the job, rather than "% 40".
--- lib/random32.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)
lib/random32.c +3 -3
@@ -208,14 +208,14 @@ static DEFINE_TIMER(seed_timer, __prandom_timer, 0, 0);static void __prandom_timer (unsigned long dontcare) {u32 entropy; -unsigned long expires; +unsigned int expires;get_random_bytes (&entropy,sizeof (entropy));prandom_seed (entropy);/* reseed every ~60 seconds, in [40 .. 80) interval with slack */ - expires =40 + (prandom_u32 () %40 ); - seed_timer.expires = jiffies +msecs_to_jiffies (expires *MSEC_PER_SEC ); + expires =40000 +prandom_u32_max (40000 ); + seed_timer.expires = jiffies +msecs_to_jiffies (expires);add_timer (&seed_timer); }
Signature · 1 line
2.0.0
Re: [PATCH 6/7] lib/random32.c: Randomize timeout to the millisecond, not the second
Quoted 5 lines · George Spelvin
If you're going to bother randomizing it, do it right. And use
prandom_u32_max(), which is designed for the job, rather than "% 40".Signed-off-by George Spelvin <[email protected]>
Fine by me this cleanup, although not strictly needed.
Quoted 27 lines
--- lib/random32.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)lib/random32.c +3
-3@@ -208,14 +208,14 @@ static DEFINE_TIMER(seed_timer, __prandom_timer, 0, 0);static void __prandom_timer (unsigned long dontcare) {u32 entropy; -unsigned long expires; +unsigned int expires;get_random_bytes (&entropy,sizeof (entropy));prandom_seed (entropy);/* reseed every ~60 seconds, in [40 .. 80) interval with slack */ - expires =40 + (prandom_u32 () %40 ); - seed_timer.expires = jiffies +msecs_to_jiffies (expires *MSEC_PER_SEC ); + expires =40000 +prandom_u32_max (40000 ); + seed_timer.expires = jiffies +msecs_to_jiffies (expires);add_timer (&seed_timer); }
Re: [PATCH 6/7] lib/random32.c: Randomize timeout to the millisecond, not the second
Quoted 1 line
Fine by me this cleanup, although not strictly needed.
Agreed. The timer slack is set to HZ (1 second) anyway.
It just dawned on me that a simpler and more efficient way to do this (which I'll do in v2 of this) would be:
/* reseed every ~60 seconds, in [40 .. 80) interval with slack */
- expires = 40 + (prandom_u32() % 40);
- seed_timer.expires = jiffies + msecs_to_jiffies(expires * MSEC_PER_SEC);
+ expires = 40*HZ + prandom_u32_max(40*HZ);
+ seed_timer.expires = jiffies + expires;
That avoids calling msecs_to_jiffies entirely.
Re: [PATCH 6/7] lib/random32.c: Randomize timeout to the millisecond, not the second
Quoted 6 lines · George Spelvin
Quoted 1 line
Fine by me this cleanup, although not strictly needed.
Agreed. The timer slack is set to HZ (1 second) anyway.
It just dawned on me that a simpler and more efficient way to do this (which I'll do in v2 of this) would be:
Note, when you talk about efficiency here, this is called once every 40+ secs ... ;)
Quoted 8 lines
/* reseed every ~60 seconds, in [40 .. 80) interval with slack */lib/random32.c +2
-2- expires =40 + (prandom_u32 () %40 ); - seed_timer.expires = jiffies +msecs_to_jiffies (expires *MSEC_PER_SEC ); + expires =40 *HZ +prandom_u32_max (40 *HZ ); + seed_timer.expires = jiffies + expires;That avoids calling
msecs_to_jiffiesentirely.
Re: [PATCH 6/7] lib/random32.c: Randomize timeout to the millisecond, not the second
Quoted 2 lines
Note, when you talk about efficiency here, this is called once every 40+ secs ... ;)
Agreed, in this case the code size saving (avoid a function call) is the main benefit. And I prefer to avoid inefficiency on general priinciples, if it's not serving some other goal.
Re: [PATCH 6/7] lib/random32.c: Randomize timeout to the millisecond, not the second
Quoted 6 lines · George Spelvin
Quoted 2 lines
Note, when you talk about efficiency here, this is called once every 40+ secs ... ;)
Agreed, in this case the code size saving (avoid a function call) is the main benefit. And I prefer to avoid inefficiency on general priinciples, if it's not serving some other goal.
Hm, don't think it will make much of a difference.
PATCH 7/7 lib/random32.c: Remove redundant U suffixes on integers
In reply to George SpelvinGet rid of a few of the extraneous U suffixes on ordinary integers.
--- lib/random32.c | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-)
lib/random32.c +5 -6
@@ -58,10 +58,10 @@ u32 prandom_u32_state(struct rnd_state *state) {#define TAUSWORTHE (s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b) - state->s1 =TAUSWORTHE (state->s1,6U ,13U ,4294967294U ,18U ); - state->s2 =TAUSWORTHE (state->s2,2U ,27U ,4294967288U ,2U ); - state->s3 =TAUSWORTHE (state->s3,13U ,21U ,4294967280U ,7U ); - state->s4 =TAUSWORTHE (state->s4,3U ,12U ,4294967168U ,13U ); + state->s1 =TAUSWORTHE (state->s1,6 ,13 ,4294967294U ,18 ); + state->s2 =TAUSWORTHE (state->s2,2 ,27 ,4294967288U ,2 ); + state->s3 =TAUSWORTHE (state->s3,13 ,21 ,4294967280U ,7 ); + state->s4 =TAUSWORTHE (state->s4,3 ,12 ,4294967168U ,13 );return (state->s1 ^ state->s2 ^ state->s3 ^ state->s4); }
@@ -77,9 +77,8 @@ EXPORT_SYMBOL(prandom_u32_state);u32 prandom_u32 (void ) {struct rnd_state *state = &get_cpu_var (net_rand_state); -u32 res; +u32 res =prandom_u32_state (state); - res =prandom_u32_state (state);put_cpu_var (state);return res;
Signature · 1 line
2.0.0
Re: [PATCH 7/7] lib/random32.c: Remove redundant U suffixes on integers
[ Please also Cc Hannes in your series. ]
Quoted 13 lines · George Spelvin
Get rid of a few of the extraneous U suffixes on ordinary integers.
Signed-off-by George Spelvin <[email protected]>--- lib/random32.c | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-)lib/random32.c +0
-0@@ -58,10 +58,10 @@ u32 prandom_u32_state(struct rnd_state *state) {
lib/random32.c u32 prandom_u32_state(struct rnd_state *state) · line 64
Quoted 10 lines
lib/random32.c +4
-4#define TAUSWORTHE (s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b) - state->s1 =TAUSWORTHE (state->s1,6U ,13U ,4294967294U ,18U ); - state->s2 =TAUSWORTHE (state->s2,2U ,27U ,4294967288U ,2U ); - state->s3 =TAUSWORTHE (state->s3,13U ,21U ,4294967280U ,7U ); - state->s4 =TAUSWORTHE (state->s4,3U ,12U ,4294967168U ,13U ); + state->s1 =TAUSWORTHE (state->s1,6 ,13 ,4294967294U ,18 ); + state->s2 =TAUSWORTHE (state->s2,2 ,27 ,4294967288U ,2 ); + state->s3 =TAUSWORTHE (state->s3,13 ,21 ,4294967280U ,7 ); + state->s4 =TAUSWORTHE (state->s4,3 ,12 ,4294967168U ,13 );
I don't see the point in why we _need_ to change this here.
lib/random32.c EXPORT_SYMBOL(prandom_u32_state); · line 82
Quoted 11 lines
lib/random32.c +1
-2return (state->s1 ^ state->s2 ^ state->s3 ^ state->s4); }@@ -77,9 +77,8 @@ EXPORT_SYMBOL(prandom_u32_state);u32 prandom_u32 (void ) {struct rnd_state *state = &get_cpu_var (net_rand_state); -u32 res; +u32 res =prandom_u32_state (state); - res =prandom_u32_state (state);put_cpu_var (state);
Ditto.
Quoted 2 lines
lib/random32.c +0
-0return res;
Re: [PATCH 7/7] lib/random32.c: Remove redundant U suffixes on integers
Quoted 1 line
[ Please also Cc Hannes in your series. ]
Thank you! But there are two frequent kernel contributors with that name; the other is Hannes Reinecke <[email protected]>.
Quoted 1 line
I don't see the point in why we _need_ to change this here.
We don't. It was just a slight legibility improvement (at least, *I* find it more legible) included as long as I was working in the area. But split out to avoid making review of the substantive parts any more difficult, and so it can be dropped easily if there are objections.
We tend to avoid cosmetic cleanups if there is not other work to do in an area, so I assume that if there *is* other work to do in an area, cosmetic cleanups are okay.
Re: [PATCH 7/7] lib/random32.c: Remove redundant U suffixes on integers
Quoted 4 lines · George Spelvin
Quoted 1 line
[ Please also Cc Hannes in your series. ]
Thank you! But there are two frequent kernel contributors with that name; the other is Hannes Reinecke <[email protected]>.
I mean <[email protected]> which I already did for you. I thought this would have been obvious based on:
git log lib/random32.c
;)