Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * Device round robin policy for multipath. | |
3 | * | |
4 | * | |
5 | * Version: $Id: multipath_drr.c,v 1.1.2.1 2004/09/16 07:42:34 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 | ||
1da177e4 LT |
15 | #include <asm/system.h> |
16 | #include <asm/uaccess.h> | |
17 | #include <linux/types.h> | |
1da177e4 LT |
18 | #include <linux/errno.h> |
19 | #include <linux/timer.h> | |
20 | #include <linux/mm.h> | |
21 | #include <linux/kernel.h> | |
22 | #include <linux/fcntl.h> | |
23 | #include <linux/stat.h> | |
24 | #include <linux/socket.h> | |
25 | #include <linux/in.h> | |
26 | #include <linux/inet.h> | |
27 | #include <linux/netdevice.h> | |
28 | #include <linux/inetdevice.h> | |
29 | #include <linux/igmp.h> | |
30 | #include <linux/proc_fs.h> | |
31 | #include <linux/seq_file.h> | |
6efd8455 | 32 | #include <linux/module.h> |
1da177e4 LT |
33 | #include <linux/mroute.h> |
34 | #include <linux/init.h> | |
35 | #include <net/ip.h> | |
36 | #include <net/protocol.h> | |
37 | #include <linux/skbuff.h> | |
38 | #include <net/sock.h> | |
39 | #include <net/icmp.h> | |
40 | #include <net/udp.h> | |
41 | #include <net/raw.h> | |
42 | #include <linux/notifier.h> | |
43 | #include <linux/if_arp.h> | |
44 | #include <linux/netfilter_ipv4.h> | |
45 | #include <net/ipip.h> | |
46 | #include <net/checksum.h> | |
47 | #include <net/ip_mp_alg.h> | |
48 | ||
49 | struct multipath_device { | |
50 | int ifi; /* interface index of device */ | |
51 | atomic_t usecount; | |
52 | int allocated; | |
53 | }; | |
54 | ||
55 | #define MULTIPATH_MAX_DEVICECANDIDATES 10 | |
56 | ||
57 | static struct multipath_device state[MULTIPATH_MAX_DEVICECANDIDATES]; | |
58 | static DEFINE_SPINLOCK(state_lock); | |
1da177e4 LT |
59 | |
60 | static int inline __multipath_findslot(void) | |
61 | { | |
62 | int i; | |
63 | ||
64 | for (i = 0; i < MULTIPATH_MAX_DEVICECANDIDATES; i++) { | |
65 | if (state[i].allocated == 0) | |
66 | return i; | |
67 | } | |
68 | return -1; | |
69 | } | |
70 | ||
71 | static int inline __multipath_finddev(int ifindex) | |
72 | { | |
73 | int i; | |
74 | ||
75 | for (i = 0; i < MULTIPATH_MAX_DEVICECANDIDATES; i++) { | |
76 | if (state[i].allocated != 0 && | |
77 | state[i].ifi == ifindex) | |
78 | return i; | |
79 | } | |
80 | return -1; | |
81 | } | |
82 | ||
83 | static int drr_dev_event(struct notifier_block *this, | |
84 | unsigned long event, void *ptr) | |
85 | { | |
86 | struct net_device *dev = ptr; | |
87 | int devidx; | |
88 | ||
89 | switch (event) { | |
90 | case NETDEV_UNREGISTER: | |
91 | case NETDEV_DOWN: | |
92 | spin_lock_bh(&state_lock); | |
93 | ||
94 | devidx = __multipath_finddev(dev->ifindex); | |
95 | if (devidx != -1) { | |
96 | state[devidx].allocated = 0; | |
97 | state[devidx].ifi = 0; | |
98 | atomic_set(&state[devidx].usecount, 0); | |
99 | } | |
100 | ||
101 | spin_unlock_bh(&state_lock); | |
102 | break; | |
3ff50b79 | 103 | } |
1da177e4 LT |
104 | |
105 | return NOTIFY_DONE; | |
106 | } | |
107 | ||
0742fd53 | 108 | static struct notifier_block drr_dev_notifier = { |
1da177e4 LT |
109 | .notifier_call = drr_dev_event, |
110 | }; | |
111 | ||
1da177e4 LT |
112 | |
113 | static void drr_safe_inc(atomic_t *usecount) | |
114 | { | |
115 | int n; | |
116 | ||
117 | atomic_inc(usecount); | |
118 | ||
119 | n = atomic_read(usecount); | |
120 | if (n <= 0) { | |
121 | int i; | |
122 | ||
123 | spin_lock_bh(&state_lock); | |
124 | ||
125 | for (i = 0; i < MULTIPATH_MAX_DEVICECANDIDATES; i++) | |
126 | atomic_set(&state[i].usecount, 0); | |
127 | ||
128 | spin_unlock_bh(&state_lock); | |
129 | } | |
130 | } | |
131 | ||
132 | static void drr_select_route(const struct flowi *flp, | |
133 | struct rtable *first, struct rtable **rp) | |
134 | { | |
135 | struct rtable *nh, *result, *cur_min; | |
e905a9ed | 136 | int min_usecount = -1; |
1da177e4 LT |
137 | int devidx = -1; |
138 | int cur_min_devidx = -1; | |
139 | ||
1da177e4 LT |
140 | /* 1. make sure all alt. nexthops have the same GC related data */ |
141 | /* 2. determine the new candidate to be returned */ | |
142 | result = NULL; | |
143 | cur_min = NULL; | |
144 | for (nh = rcu_dereference(first); nh; | |
5ef213f6 | 145 | nh = rcu_dereference(nh->u.dst.rt_next)) { |
1da177e4 LT |
146 | if ((nh->u.dst.flags & DST_BALANCED) != 0 && |
147 | multipath_comparekeys(&nh->fl, flp)) { | |
148 | int nh_ifidx = nh->u.dst.dev->ifindex; | |
149 | ||
150 | nh->u.dst.lastuse = jiffies; | |
151 | nh->u.dst.__use++; | |
152 | if (result != NULL) | |
153 | continue; | |
154 | ||
155 | /* search for the output interface */ | |
156 | ||
157 | /* this is not SMP safe, only add/remove are | |
158 | * SMP safe as wrong usecount updates have no big | |
159 | * impact | |
160 | */ | |
161 | devidx = __multipath_finddev(nh_ifidx); | |
162 | if (devidx == -1) { | |
e905a9ed | 163 | /* add the interface to the array |
1da177e4 LT |
164 | * SMP safe |
165 | */ | |
166 | spin_lock_bh(&state_lock); | |
167 | ||
168 | /* due to SMP: search again */ | |
169 | devidx = __multipath_finddev(nh_ifidx); | |
170 | if (devidx == -1) { | |
171 | /* add entry for device */ | |
172 | devidx = __multipath_findslot(); | |
173 | if (devidx == -1) { | |
174 | /* unlikely but possible */ | |
175 | continue; | |
176 | } | |
177 | ||
178 | state[devidx].allocated = 1; | |
179 | state[devidx].ifi = nh_ifidx; | |
180 | atomic_set(&state[devidx].usecount, 0); | |
181 | min_usecount = 0; | |
182 | } | |
183 | ||
184 | spin_unlock_bh(&state_lock); | |
185 | } | |
186 | ||
187 | if (min_usecount == 0) { | |
188 | /* if the device has not been used it is | |
189 | * the primary target | |
190 | */ | |
191 | drr_safe_inc(&state[devidx].usecount); | |
192 | result = nh; | |
193 | } else { | |
194 | int count = | |
195 | atomic_read(&state[devidx].usecount); | |
196 | ||
197 | if (min_usecount == -1 || | |
198 | count < min_usecount) { | |
199 | cur_min = nh; | |
200 | cur_min_devidx = devidx; | |
201 | min_usecount = count; | |
202 | } | |
203 | } | |
204 | } | |
205 | } | |
206 | ||
207 | if (!result) { | |
208 | if (cur_min) { | |
209 | drr_safe_inc(&state[cur_min_devidx].usecount); | |
210 | result = cur_min; | |
211 | } else { | |
212 | result = first; | |
213 | } | |
214 | } | |
215 | ||
216 | *rp = result; | |
1da177e4 LT |
217 | } |
218 | ||
219 | static struct ip_mp_alg_ops drr_ops = { | |
220 | .mp_alg_select_route = drr_select_route, | |
1da177e4 LT |
221 | }; |
222 | ||
223 | static int __init drr_init(void) | |
224 | { | |
225 | int err = register_netdevice_notifier(&drr_dev_notifier); | |
226 | ||
227 | if (err) | |
228 | return err; | |
229 | ||
37e20a66 | 230 | err = multipath_alg_register(&drr_ops, IP_MP_ALG_DRR); |
1da177e4 LT |
231 | if (err) |
232 | goto fail; | |
233 | ||
234 | return 0; | |
235 | ||
236 | fail: | |
237 | unregister_netdevice_notifier(&drr_dev_notifier); | |
238 | return err; | |
239 | } | |
240 | ||
241 | static void __exit drr_exit(void) | |
242 | { | |
243 | unregister_netdevice_notifier(&drr_dev_notifier); | |
244 | multipath_alg_unregister(&drr_ops, IP_MP_ALG_DRR); | |
245 | } | |
246 | ||
247 | module_init(drr_init); | |
248 | module_exit(drr_exit); | |
6efd8455 | 249 | MODULE_LICENSE("GPL"); |