Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * Random policy for multipath. | |
3 | * | |
4 | * | |
5 | * Version: $Id: multipath_random.c,v 1.1.2.3 2004/09/21 08:42:11 elueck Exp $ | |
6 | * | |
7 | * Authors: Einar Lueck <elueck@de.ibm.com><lkml@einar-lueck.de> | |
8 | * | |
9 | * This program is free software; you can redistribute it and/or | |
10 | * modify it under the terms of the GNU General Public License | |
11 | * as published by the Free Software Foundation; either version | |
12 | * 2 of the License, or (at your option) any later version. | |
13 | */ | |
14 | ||
15 | #include <linux/config.h> | |
16 | #include <asm/system.h> | |
17 | #include <asm/uaccess.h> | |
18 | #include <linux/types.h> | |
19 | #include <linux/sched.h> | |
20 | #include <linux/errno.h> | |
21 | #include <linux/timer.h> | |
22 | #include <linux/mm.h> | |
23 | #include <linux/kernel.h> | |
24 | #include <linux/fcntl.h> | |
25 | #include <linux/stat.h> | |
26 | #include <linux/socket.h> | |
27 | #include <linux/in.h> | |
28 | #include <linux/inet.h> | |
29 | #include <linux/netdevice.h> | |
30 | #include <linux/inetdevice.h> | |
31 | #include <linux/igmp.h> | |
32 | #include <linux/proc_fs.h> | |
33 | #include <linux/seq_file.h> | |
6efd8455 | 34 | #include <linux/module.h> |
1da177e4 LT |
35 | #include <linux/mroute.h> |
36 | #include <linux/init.h> | |
37 | #include <net/ip.h> | |
38 | #include <net/protocol.h> | |
39 | #include <linux/skbuff.h> | |
40 | #include <net/sock.h> | |
41 | #include <net/icmp.h> | |
42 | #include <net/udp.h> | |
43 | #include <net/raw.h> | |
44 | #include <linux/notifier.h> | |
45 | #include <linux/if_arp.h> | |
46 | #include <linux/netfilter_ipv4.h> | |
47 | #include <net/ipip.h> | |
48 | #include <net/checksum.h> | |
49 | #include <net/ip_mp_alg.h> | |
50 | ||
51 | #define MULTIPATH_MAX_CANDIDATES 40 | |
52 | ||
53 | /* interface to random number generation */ | |
54 | static unsigned int RANDOM_SEED = 93186752; | |
55 | ||
56 | static inline unsigned int random(unsigned int ubound) | |
57 | { | |
58 | static unsigned int a = 1588635695, | |
59 | q = 2, | |
60 | r = 1117695901; | |
61 | ||
62 | RANDOM_SEED = a*(RANDOM_SEED % q) - r*(RANDOM_SEED / q); | |
63 | ||
64 | return RANDOM_SEED % ubound; | |
65 | } | |
66 | ||
67 | ||
68 | static void random_select_route(const struct flowi *flp, | |
69 | struct rtable *first, | |
70 | struct rtable **rp) | |
71 | { | |
72 | struct rtable *rt; | |
73 | struct rtable *decision; | |
74 | unsigned char candidate_count = 0; | |
75 | ||
76 | /* count all candidate */ | |
77 | for (rt = rcu_dereference(first); rt; | |
78 | rt = rcu_dereference(rt->u.rt_next)) { | |
79 | if ((rt->u.dst.flags & DST_BALANCED) != 0 && | |
80 | multipath_comparekeys(&rt->fl, flp)) | |
81 | ++candidate_count; | |
82 | } | |
83 | ||
84 | /* choose a random candidate */ | |
85 | decision = first; | |
86 | if (candidate_count > 1) { | |
87 | unsigned char i = 0; | |
88 | unsigned char candidate_no = (unsigned char) | |
89 | random(candidate_count); | |
90 | ||
91 | /* find chosen candidate and adjust GC data for all candidates | |
92 | * to ensure they stay in cache | |
93 | */ | |
94 | for (rt = first; rt; rt = rt->u.rt_next) { | |
95 | if ((rt->u.dst.flags & DST_BALANCED) != 0 && | |
96 | multipath_comparekeys(&rt->fl, flp)) { | |
97 | rt->u.dst.lastuse = jiffies; | |
98 | ||
99 | if (i == candidate_no) | |
100 | decision = rt; | |
101 | ||
102 | if (i >= candidate_count) | |
103 | break; | |
104 | ||
105 | i++; | |
106 | } | |
107 | } | |
108 | } | |
109 | ||
110 | decision->u.dst.__use++; | |
111 | *rp = decision; | |
112 | } | |
113 | ||
114 | static struct ip_mp_alg_ops random_ops = { | |
115 | .mp_alg_select_route = random_select_route, | |
116 | }; | |
117 | ||
118 | static int __init random_init(void) | |
119 | { | |
120 | return multipath_alg_register(&random_ops, IP_MP_ALG_RANDOM); | |
121 | } | |
122 | ||
123 | static void __exit random_exit(void) | |
124 | { | |
125 | multipath_alg_unregister(&random_ops, IP_MP_ALG_RANDOM); | |
126 | } | |
127 | ||
128 | module_init(random_init); | |
129 | module_exit(random_exit); | |
6efd8455 | 130 | MODULE_LICENSE("GPL"); |