net/core/utils.c

   1 /*
   2  *      Generic address resultion entity
   3  *
   4  *      Authors:
   5  *      net_random Alan Cox
   6  *      net_ratelimit Andy Kleen
   7  *      in{4,6}_pton YOSHIFUJI Hideaki, Copyright (C)2006 USAGI/WIDE Project
   8  *
   9  *      Created by Alexey Kuznetsov <kuznet@ms2.inr.ac.ru>
  10  *
  11  *      This program is free software; you can redistribute it and/or
  12  *      modify it under the terms of the GNU General Public License
  13  *      as published by the Free Software Foundation; either version
  14  *      2 of the License, or (at your option) any later version.
  15  */
  16
  17 #include <linux/module.h>
  18 #include <linux/jiffies.h>
  19 #include <linux/kernel.h>
  20 #include <linux/inet.h>
  21 #include <linux/mm.h>
  22 #include <linux/net.h>
  23 #include <linux/string.h>
  24 #include <linux/types.h>
  25 #include <linux/random.h>
  26 #include <linux/percpu.h>
  27 #include <linux/init.h>
  28
  29 #include <asm/byteorder.h>
  30 #include <asm/system.h>
  31 #include <asm/uaccess.h>
  32
  33 /*
  34   This is a maximally equidistributed combined Tausworthe generator
  35   based on code from GNU Scientific Library 1.5 (30 Jun 2004)
  36
  37    x_n = (s1_n ^ s2_n ^ s3_n)
  38
  39    s1_{n+1} = (((s1_n & 4294967294) <<12) ^ (((s1_n <<13) ^ s1_n) >>19))
  40    s2_{n+1} = (((s2_n & 4294967288) << 4) ^ (((s2_n << 2) ^ s2_n) >>25))
  41    s3_{n+1} = (((s3_n & 4294967280) <<17) ^ (((s3_n << 3) ^ s3_n) >>11))
  42
  43    The period of this generator is about 2^88.
  44
  45    From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe
  46    Generators", Mathematics of Computation, 65, 213 (1996), 203--213.
  47
  48    This is available on the net from L'Ecuyer's home page,
  49
  50    http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
  51    ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps
  52
  53    There is an erratum in the paper "Tables of Maximally
  54    Equidistributed Combined LFSR Generators", Mathematics of
  55    Computation, 68, 225 (1999), 261--269:
  56    http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
  57
  58         ... the k_j most significant bits of z_j must be non-
  59         zero, for each j. (Note: this restriction also applies to the
  60         computer code given in [4], but was mistakenly not mentioned in
  61         that paper.)
  62
  63    This affects the seeding procedure by imposing the requirement
  64    s1 > 1, s2 > 7, s3 > 15.
  65
  66 */
  67 struct nrnd_state {
  68         u32 s1, s2, s3;
  69 };
  70
  71 static DEFINE_PER_CPU(struct nrnd_state, net_rand_state);
  72
  73 static u32 __net_random(struct nrnd_state *state)
  74 {
  75 #define TAUSWORTHE(s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b)
  76
  77         state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12);
  78         state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4);
  79         state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17);
  80
  81         return (state->s1 ^ state->s2 ^ state->s3);
  82 }
  83
  84 static void __net_srandom(struct nrnd_state *state, unsigned long s)
  85 {
  86         if (s == 0)
  87                 s = 1;      /* default seed is 1 */
  88
  89 #define LCG(n) (69069 * n)
  90         state->s1 = LCG(s);
  91         state->s2 = LCG(state->s1);
  92         state->s3 = LCG(state->s2);
  93
  94         /* "warm it up" */
  95         __net_random(state);
  96         __net_random(state);
  97         __net_random(state);
  98         __net_random(state);
  99         __net_random(state);
 100         __net_random(state);
 101 }
 102
 103
 104 unsigned long net_random(void)
 105 {
 106         unsigned long r;
 107         struct nrnd_state *state = &get_cpu_var(net_rand_state);
 108         r = __net_random(state);
 109         put_cpu_var(state);
 110         return r;
 111 }
 112
 113
 114 void net_srandom(unsigned long entropy)
 115 {
 116         struct nrnd_state *state = &get_cpu_var(net_rand_state);
 117         __net_srandom(state, state->s1^entropy);
 118         put_cpu_var(state);
 119 }
 120
 121 void __init net_random_init(void)
 122 {
 123         int i;
 124
 125         for_each_possible_cpu(i) {
 126                 struct nrnd_state *state = &per_cpu(net_rand_state,i);
 127                 __net_srandom(state, i+jiffies);
 128         }
 129 }
 130
 131 static int net_random_reseed(void)
 132 {
 133         int i;
 134         unsigned long seed;
 135
 136         for_each_possible_cpu(i) {
 137                 struct nrnd_state *state = &per_cpu(net_rand_state,i);
 138
 139                 get_random_bytes(&seed, sizeof(seed));
 140                 __net_srandom(state, seed);
 141         }
 142         return 0;
 143 }
 144 late_initcall(net_random_reseed);
 145
 146 int net_msg_cost = 5*HZ;
 147 int net_msg_burst = 10;
 148
 149 /*
 150  * All net warning printk()s should be guarded by this function.
 151  */
 152 int net_ratelimit(void)
 153 {
 154         return __printk_ratelimit(net_msg_cost, net_msg_burst);
 155 }
 156
 157 EXPORT_SYMBOL(net_random);
 158 EXPORT_SYMBOL(net_ratelimit);
 159 EXPORT_SYMBOL(net_srandom);
 160
 161 /*
 162  * Convert an ASCII string to binary IP.
 163  * This is outside of net/ipv4/ because various code that uses IP addresses
 164  * is otherwise not dependent on the TCP/IP stack.
 165  */
 166
 167 __be32 in_aton(const char *str)
 168 {
 169         unsigned long l;
 170         unsigned int val;
 171         int i;
 172
 173         l = 0;
 174         for (i = 0; i < 4; i++)
 175         {
 176                 l <<= 8;
 177                 if (*str != '\0')
 178                 {
 179                         val = 0;
 180                         while (*str != '\0' && *str != '.' && *str != '\n')
 181                         {
 182                                 val *= 10;
 183                                 val += *str - '0';
 184                                 str++;
 185                         }
 186                         l |= val;
 187                         if (*str != '\0')
 188                                 str++;
 189                 }
 190         }
 191         return(htonl(l));
 192 }
 193
 194 EXPORT_SYMBOL(in_aton);
 195
 196 #define IN6PTON_XDIGIT          0x00010000
 197 #define IN6PTON_DIGIT           0x00020000
 198 #define IN6PTON_COLON_MASK      0x00700000
 199 #define IN6PTON_COLON_1         0x00100000      /* single : requested */
 200 #define IN6PTON_COLON_2         0x00200000      /* second : requested */
 201 #define IN6PTON_COLON_1_2       0x00400000      /* :: requested */
 202 #define IN6PTON_DOT             0x00800000      /* . */
 203 #define IN6PTON_DELIM           0x10000000
 204 #define IN6PTON_NULL            0x20000000      /* first/tail */
 205 #define IN6PTON_UNKNOWN         0x40000000
 206
 207 static inline int digit2bin(char c, char delim)
 208 {
 209         if (c == delim || c == '\0')
 210                 return IN6PTON_DELIM;
 211         if (c == '.')
 212                 return IN6PTON_DOT;
 213         if (c >= '0' && c <= '9')
 214                 return (IN6PTON_DIGIT | (c - '0'));
 215         return IN6PTON_UNKNOWN;
 216 }
 217
 218 static inline int xdigit2bin(char c, char delim)
 219 {
 220         if (c == delim || c == '\0')
 221                 return IN6PTON_DELIM;
 222         if (c == ':')
 223                 return IN6PTON_COLON_MASK;
 224         if (c == '.')
 225                 return IN6PTON_DOT;
 226         if (c >= '0' && c <= '9')
 227                 return (IN6PTON_XDIGIT | IN6PTON_DIGIT| (c - '0'));
 228         if (c >= 'a' && c <= 'f')
 229                 return (IN6PTON_XDIGIT | (c - 'a' + 10));
 230         if (c >= 'A' && c <= 'F')
 231                 return (IN6PTON_XDIGIT | (c - 'A' + 10));
 232         return IN6PTON_UNKNOWN;
 233 }
 234
 235 int in4_pton(const char *src, int srclen,
 236              u8 *dst,
 237              char delim, const char **end)
 238 {
 239         const char *s;
 240         u8 *d;
 241         u8 dbuf[4];
 242         int ret = 0;
 243         int i;
 244         int w = 0;
 245
 246         if (srclen < 0)
 247                 srclen = strlen(src);
 248         s = src;
 249         d = dbuf;
 250         i = 0;
 251         while(1) {
 252                 int c;
 253                 c = xdigit2bin(srclen > 0 ? *s : '\0', delim);
 254                 if (!(c & (IN6PTON_DIGIT | IN6PTON_DOT | IN6PTON_DELIM))) {
 255                         goto out;
 256                 }
 257                 if (c & (IN6PTON_DOT | IN6PTON_DELIM)) {
 258                         if (w == 0)
 259                                 goto out;
 260                         *d++ = w & 0xff;
 261                         w = 0;
 262                         i++;
 263                         if (c & IN6PTON_DELIM) {
 264                                 if (i != 4)
 265                                         goto out;
 266                                 break;
 267                         }
 268                         goto cont;
 269                 }
 270                 w = (w * 10) + c;
 271                 if ((w & 0xffff) > 255) {
 272                         goto out;
 273                 }
 274 cont:
 275                 if (i >= 4)
 276                         goto out;
 277                 s++;
 278                 srclen--;
 279         }
 280         ret = 1;
 281         memcpy(dst, dbuf, sizeof(dbuf));
 282 out:
 283         if (end)
 284                 *end = s;
 285         return ret;
 286 }
 287
 288 EXPORT_SYMBOL(in4_pton);
 289
 290 int in6_pton(const char *src, int srclen,
 291              u8 *dst,
 292              char delim, const char **end)
 293 {
 294         const char *s, *tok = NULL;
 295         u8 *d, *dc = NULL;
 296         u8 dbuf[16];
 297         int ret = 0;
 298         int i;
 299         int state = IN6PTON_COLON_1_2 | IN6PTON_XDIGIT | IN6PTON_NULL;
 300         int w = 0;
 301
 302         memset(dbuf, 0, sizeof(dbuf));
 303
 304         s = src;
 305         d = dbuf;
 306         if (srclen < 0)
 307                 srclen = strlen(src);
 308
 309         while (1) {
 310                 int c;
 311
 312                 c = xdigit2bin(srclen > 0 ? *s : '\0', delim);
 313                 if (!(c & state))
 314                         goto out;
 315                 if (c & (IN6PTON_DELIM | IN6PTON_COLON_MASK)) {
 316                         /* process one 16-bit word */
 317                         if (!(state & IN6PTON_NULL)) {
 318                                 *d++ = (w >> 8) & 0xff;
 319                                 *d++ = w & 0xff;
 320                         }
 321                         w = 0;
 322                         if (c & IN6PTON_DELIM) {
 323                                 /* We've processed last word */
 324                                 break;
 325                         }
 326                         /*
 327                          * COLON_1 => XDIGIT
 328                          * COLON_2 => XDIGIT|DELIM
 329                          * COLON_1_2 => COLON_2
 330                          */
 331                         switch (state & IN6PTON_COLON_MASK) {
 332                         case IN6PTON_COLON_2:
 333                                 dc = d;
 334                                 state = IN6PTON_XDIGIT | IN6PTON_DELIM;
 335                                 if (dc - dbuf >= sizeof(dbuf))
 336                                         state |= IN6PTON_NULL;
 337                                 break;
 338                         case IN6PTON_COLON_1|IN6PTON_COLON_1_2:
 339                                 state = IN6PTON_XDIGIT | IN6PTON_COLON_2;
 340                                 break;
 341                         case IN6PTON_COLON_1:
 342                                 state = IN6PTON_XDIGIT;
 343                                 break;
 344                         case IN6PTON_COLON_1_2:
 345                                 state = IN6PTON_COLON_2;
 346                                 break;
 347                         default:
 348                                 state = 0;
 349                         }
 350                         tok = s + 1;
 351                         goto cont;
 352                 }
 353
 354                 if (c & IN6PTON_DOT) {
 355                         ret = in4_pton(tok ? tok : s, srclen + (int)(s - tok), d, delim, &s);
 356                         if (ret > 0) {
 357                                 d += 4;
 358                                 break;
 359                         }
 360                         goto out;
 361                 }
 362
 363                 w = (w << 4) | (0xff & c);
 364                 state = IN6PTON_COLON_1 | IN6PTON_DELIM;
 365                 if (!(w & 0xf000)) {
 366                         state |= IN6PTON_XDIGIT;
 367                 }
 368                 if (!dc && d + 2 < dbuf + sizeof(dbuf)) {
 369                         state |= IN6PTON_COLON_1_2;
 370                         state &= ~IN6PTON_DELIM;
 371                 }
 372                 if (d + 2 >= dbuf + sizeof(dbuf)) {
 373                         state &= ~(IN6PTON_COLON_1|IN6PTON_COLON_1_2);
 374                 }
 375 cont:
 376                 if ((dc && d + 4 < dbuf + sizeof(dbuf)) ||
 377                     d + 4 == dbuf + sizeof(dbuf)) {
 378                         state |= IN6PTON_DOT;
 379                 }
 380                 if (d >= dbuf + sizeof(dbuf)) {
 381                         state &= ~(IN6PTON_XDIGIT|IN6PTON_COLON_MASK);
 382                 }
 383                 s++;
 384                 srclen--;
 385         }
 386
 387         i = 15; d--;
 388
 389         if (dc) {
 390                 while(d >= dc)
 391                         dst[i--] = *d--;
 392                 while(i >= dc - dbuf)
 393                         dst[i--] = 0;
 394                 while(i >= 0)
 395                         dst[i--] = *d--;
 396         } else
 397                 memcpy(dst, dbuf, sizeof(dbuf));
 398
 399         ret = 1;
 400 out:
 401         if (end)
 402                 *end = s;
 403         return ret;
 404 }
 405
 406 EXPORT_SYMBOL(in6_pton);