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