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