lib/random32.c

   1 /*
   2   This is a maximally equidistributed combined Tausworthe generator
   3   based on code from GNU Scientific Library 1.5 (30 Jun 2004)
   4
   5   lfsr113 version:
   6
   7    x_n = (s1_n ^ s2_n ^ s3_n ^ s4_n)
   8
   9    s1_{n+1} = (((s1_n & 4294967294) << 18) ^ (((s1_n <<  6) ^ s1_n) >> 13))
  10    s2_{n+1} = (((s2_n & 4294967288) <<  2) ^ (((s2_n <<  2) ^ s2_n) >> 27))
  11    s3_{n+1} = (((s3_n & 4294967280) <<  7) ^ (((s3_n << 13) ^ s3_n) >> 21))
  12    s4_{n+1} = (((s4_n & 4294967168) << 13) ^ (((s4_n <<  3) ^ s4_n) >> 12))
  13
  14    The period of this generator is about 2^113 (see erratum paper).
  15
  16    From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe
  17    Generators", Mathematics of Computation, 65, 213 (1996), 203--213:
  18    http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
  19    ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps
  20
  21    There is an erratum in the paper "Tables of Maximally
  22    Equidistributed Combined LFSR Generators", Mathematics of
  23    Computation, 68, 225 (1999), 261--269:
  24    http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
  25
  26         ... the k_j most significant bits of z_j must be non-
  27         zero, for each j. (Note: this restriction also applies to the
  28         computer code given in [4], but was mistakenly not mentioned in
  29         that paper.)
  30
  31    This affects the seeding procedure by imposing the requirement
  32    s1 > 1, s2 > 7, s3 > 15, s4 > 127.
  33
  34 */
  35
  36 #include <linux/types.h>
  37 #include <linux/percpu.h>
  38 #include <linux/export.h>
  39 #include <linux/jiffies.h>
  40 #include <linux/random.h>
  41
  42 static DEFINE_PER_CPU(struct rnd_state, net_rand_state);
  43
  44 /**
  45  *      prandom_u32_state - seeded pseudo-random number generator.
  46  *      @state: pointer to state structure holding seeded state.
  47  *
  48  *      This is used for pseudo-randomness with no outside seeding.
  49  *      For more random results, use prandom_u32().
  50  */
  51 u32 prandom_u32_state(struct rnd_state *state)
  52 {
  53 #define TAUSWORTHE(s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b)
  54
  55         state->s1 = TAUSWORTHE(state->s1,  6U, 13U, 4294967294U, 18U);
  56         state->s2 = TAUSWORTHE(state->s2,  2U, 27U, 4294967288U,  2U);
  57         state->s3 = TAUSWORTHE(state->s3, 13U, 21U, 4294967280U,  7U);
  58         state->s4 = TAUSWORTHE(state->s4,  3U, 12U, 4294967168U, 13U);
  59
  60         return (state->s1 ^ state->s2 ^ state->s3 ^ state->s4);
  61 }
  62 EXPORT_SYMBOL(prandom_u32_state);
  63
  64 /**
  65  *      prandom_u32 - pseudo random number generator
  66  *
  67  *      A 32 bit pseudo-random number is generated using a fast
  68  *      algorithm suitable for simulation. This algorithm is NOT
  69  *      considered safe for cryptographic use.
  70  */
  71 u32 prandom_u32(void)
  72 {
  73         unsigned long r;
  74         struct rnd_state *state = &get_cpu_var(net_rand_state);
  75         r = prandom_u32_state(state);
  76         put_cpu_var(state);
  77         return r;
  78 }
  79 EXPORT_SYMBOL(prandom_u32);
  80
  81 /*
  82  *      prandom_bytes_state - get the requested number of pseudo-random bytes
  83  *
  84  *      @state: pointer to state structure holding seeded state.
  85  *      @buf: where to copy the pseudo-random bytes to
  86  *      @bytes: the requested number of bytes
  87  *
  88  *      This is used for pseudo-randomness with no outside seeding.
  89  *      For more random results, use prandom_bytes().
  90  */
  91 void prandom_bytes_state(struct rnd_state *state, void *buf, int bytes)
  92 {
  93         unsigned char *p = buf;
  94         int i;
  95
  96         for (i = 0; i < round_down(bytes, sizeof(u32)); i += sizeof(u32)) {
  97                 u32 random = prandom_u32_state(state);
  98                 int j;
  99
 100                 for (j = 0; j < sizeof(u32); j++) {
 101                         p[i + j] = random;
 102                         random >>= BITS_PER_BYTE;
 103                 }
 104         }
 105         if (i < bytes) {
 106                 u32 random = prandom_u32_state(state);
 107
 108                 for (; i < bytes; i++) {
 109                         p[i] = random;
 110                         random >>= BITS_PER_BYTE;
 111                 }
 112         }
 113 }
 114 EXPORT_SYMBOL(prandom_bytes_state);
 115
 116 /**
 117  *      prandom_bytes - get the requested number of pseudo-random bytes
 118  *      @buf: where to copy the pseudo-random bytes to
 119  *      @bytes: the requested number of bytes
 120  */
 121 void prandom_bytes(void *buf, int bytes)
 122 {
 123         struct rnd_state *state = &get_cpu_var(net_rand_state);
 124
 125         prandom_bytes_state(state, buf, bytes);
 126         put_cpu_var(state);
 127 }
 128 EXPORT_SYMBOL(prandom_bytes);
 129
 130 static void prandom_warmup(struct rnd_state *state)
 131 {
 132         /* Calling RNG ten times to satify recurrence condition */
 133         prandom_u32_state(state);
 134         prandom_u32_state(state);
 135         prandom_u32_state(state);
 136         prandom_u32_state(state);
 137         prandom_u32_state(state);
 138         prandom_u32_state(state);
 139         prandom_u32_state(state);
 140         prandom_u32_state(state);
 141         prandom_u32_state(state);
 142         prandom_u32_state(state);
 143 }
 144
 145 /**
 146  *      prandom_seed - add entropy to pseudo random number generator
 147  *      @seed: seed value
 148  *
 149  *      Add some additional seeding to the prandom pool.
 150  */
 151 void prandom_seed(u32 entropy)
 152 {
 153         int i;
 154         /*
 155          * No locking on the CPUs, but then somewhat random results are, well,
 156          * expected.
 157          */
 158         for_each_possible_cpu (i) {
 159                 struct rnd_state *state = &per_cpu(net_rand_state, i);
 160
 161                 state->s1 = __seed(state->s1 ^ entropy, 2U);
 162                 prandom_warmup(state);
 163         }
 164 }
 165 EXPORT_SYMBOL(prandom_seed);
 166
 167 /*
 168  *      Generate some initially weak seeding values to allow
 169  *      to start the prandom_u32() engine.
 170  */
 171 static int __init prandom_init(void)
 172 {
 173         int i;
 174
 175         for_each_possible_cpu(i) {
 176                 struct rnd_state *state = &per_cpu(net_rand_state,i);
 177
 178 #define LCG(x)  ((x) * 69069U)  /* super-duper LCG */
 179                 state->s1 = __seed(LCG((i + jiffies) ^ random_get_entropy()), 2U);
 180                 state->s2 = __seed(LCG(state->s1),   8U);
 181                 state->s3 = __seed(LCG(state->s2),  16U);
 182                 state->s4 = __seed(LCG(state->s3), 128U);
 183
 184                 prandom_warmup(state);
 185         }
 186         return 0;
 187 }
 188 core_initcall(prandom_init);
 189
 190 static void __prandom_timer(unsigned long dontcare);
 191 static DEFINE_TIMER(seed_timer, __prandom_timer, 0, 0);
 192
 193 static void __prandom_timer(unsigned long dontcare)
 194 {
 195         u32 entropy;
 196
 197         get_random_bytes(&entropy, sizeof(entropy));
 198         prandom_seed(entropy);
 199         /* reseed every ~60 seconds, in [40 .. 80) interval with slack */
 200         seed_timer.expires = jiffies + (40 * HZ + (prandom_u32() % (40 * HZ)));
 201         add_timer(&seed_timer);
 202 }
 203
 204 static void prandom_start_seed_timer(void)
 205 {
 206         set_timer_slack(&seed_timer, HZ);
 207         seed_timer.expires = jiffies + 40 * HZ;
 208         add_timer(&seed_timer);
 209 }
 210
 211 /*
 212  *      Generate better values after random number generator
 213  *      is fully initialized.
 214  */
 215 static void __prandom_reseed(bool late)
 216 {
 217         int i;
 218         unsigned long flags;
 219         static bool latch = false;
 220         static DEFINE_SPINLOCK(lock);
 221
 222         /* only allow initial seeding (late == false) once */
 223         spin_lock_irqsave(&lock, flags);
 224         if (latch && !late)
 225                 goto out;
 226         latch = true;
 227
 228         for_each_possible_cpu(i) {
 229                 struct rnd_state *state = &per_cpu(net_rand_state,i);
 230                 u32 seeds[4];
 231
 232                 get_random_bytes(&seeds, sizeof(seeds));
 233                 state->s1 = __seed(seeds[0],   2U);
 234                 state->s2 = __seed(seeds[1],   8U);
 235                 state->s3 = __seed(seeds[2],  16U);
 236                 state->s4 = __seed(seeds[3], 128U);
 237
 238                 prandom_warmup(state);
 239         }
 240 out:
 241         spin_unlock_irqrestore(&lock, flags);
 242 }
 243
 244 void prandom_reseed_late(void)
 245 {
 246         __prandom_reseed(true);
 247 }
 248
 249 static int __init prandom_reseed(void)
 250 {
 251         __prandom_reseed(false);
 252         prandom_start_seed_timer();
 253         return 0;
 254 }
 255 late_initcall(prandom_reseed);