Merge git://git.infradead.org/mtd-2.6
[linux-2.6] / 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);