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