net/core/utils.c

   1 /*
   2  *      Generic address resultion entity
   3  *
   4  *      Authors:
   5  *      net_random Alan Cox
   6  *      net_ratelimit Andy Kleen
   7  *
   8  *      Created by Alexey Kuznetsov <kuznet@ms2.inr.ac.ru>
   9  *
  10  *      This program is free software; you can redistribute it and/or
  11  *      modify it under the terms of the GNU General Public License
  12  *      as published by the Free Software Foundation; either version
  13  *      2 of the License, or (at your option) any later version.
  14  */
  15
  16 #include <linux/module.h>
  17 #include <linux/jiffies.h>
  18 #include <linux/kernel.h>
  19 #include <linux/mm.h>
  20 #include <linux/string.h>
  21 #include <linux/types.h>
  22 #include <linux/random.h>
  23 #include <linux/percpu.h>
  24
  25 #include <asm/system.h>
  26 #include <asm/uaccess.h>
  27
  28
  29 /*
  30   This is a maximally equidistributed combined Tausworthe generator
  31   based on code from GNU Scientific Library 1.5 (30 Jun 2004)
  32
  33    x_n = (s1_n ^ s2_n ^ s3_n)
  34
  35    s1_{n+1} = (((s1_n & 4294967294) <<12) ^ (((s1_n <<13) ^ s1_n) >>19))
  36    s2_{n+1} = (((s2_n & 4294967288) << 4) ^ (((s2_n << 2) ^ s2_n) >>25))
  37    s3_{n+1} = (((s3_n & 4294967280) <<17) ^ (((s3_n << 3) ^ s3_n) >>11))
  38
  39    The period of this generator is about 2^88.
  40
  41    From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe
  42    Generators", Mathematics of Computation, 65, 213 (1996), 203--213.
  43
  44    This is available on the net from L'Ecuyer's home page,
  45
  46    http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
  47    ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps
  48
  49    There is an erratum in the paper "Tables of Maximally
  50    Equidistributed Combined LFSR Generators", Mathematics of
  51    Computation, 68, 225 (1999), 261--269:
  52    http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
  53
  54         ... the k_j most significant bits of z_j must be non-
  55         zero, for each j. (Note: this restriction also applies to the
  56         computer code given in [4], but was mistakenly not mentioned in
  57         that paper.)
  58
  59    This affects the seeding procedure by imposing the requirement
  60    s1 > 1, s2 > 7, s3 > 15.
  61
  62 */
  63 struct nrnd_state {
  64         u32 s1, s2, s3;
  65 };
  66
  67 static DEFINE_PER_CPU(struct nrnd_state, net_rand_state);
  68
  69 static u32 __net_random(struct nrnd_state *state)
  70 {
  71 #define TAUSWORTHE(s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b)
  72
  73         state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12);
  74         state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4);
  75         state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17);
  76
  77         return (state->s1 ^ state->s2 ^ state->s3);
  78 }
  79
  80 static void __net_srandom(struct nrnd_state *state, unsigned long entropy)
  81 {
  82         u32 s = state->s1 ^ entropy;
  83
  84         if (s == 0)
  85                 s = 1;      /* default seed is 1 */
  86
  87 #define LCG(n) (69069 * n)
  88         state->s1 = LCG(s);
  89         state->s2 = LCG(state->s1);
  90         state->s3 = LCG(state->s2);
  91
  92         /* "warm it up" */
  93         __net_random(state);
  94         __net_random(state);
  95         __net_random(state);
  96         __net_random(state);
  97         __net_random(state);
  98         __net_random(state);
  99 }
 100
 101
 102 unsigned long net_random(void)
 103 {
 104         unsigned long r;
 105         struct nrnd_state *state = &get_cpu_var(net_rand_state);
 106         r = __net_random(state);
 107         put_cpu_var(state);
 108         return r;
 109 }
 110
 111
 112 void net_srandom(unsigned long entropy)
 113 {
 114         struct nrnd_state *state = &get_cpu_var(net_rand_state);
 115         __net_srandom(state, entropy);
 116         put_cpu_var(state);
 117 }
 118
 119 void __init net_random_init(void)
 120 {
 121         int i;
 122         unsigned long seed[NR_CPUS];
 123
 124         get_random_bytes(seed, sizeof(seed));
 125
 126         for (i = 0; i < NR_CPUS; i++) {
 127                 struct nrnd_state *state = &per_cpu(net_rand_state,i);
 128
 129                 memset(state, 0, sizeof(*state));
 130                 __net_srandom(state, seed[i]);
 131         }
 132 }
 133
 134 int net_msg_cost = 5*HZ;
 135 int net_msg_burst = 10;
 136
 137 /*
 138  * All net warning printk()s should be guarded by this function.
 139  */
 140 int net_ratelimit(void)
 141 {
 142         return __printk_ratelimit(net_msg_cost, net_msg_burst);
 143 }
 144
 145 EXPORT_SYMBOL(net_random);
 146 EXPORT_SYMBOL(net_ratelimit);
 147 EXPORT_SYMBOL(net_srandom);