1 /* 2 * Generic address resultion entity 3 * 4 * Authors: 5 * net_random Alan Cox 6 * net_ratelimit Andi 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); 407