1 | #include <machine/rtems-bsd-kernel-space.h> |
---|
2 | |
---|
3 | /* $KAME: radix_mpath.c,v 1.17 2004/11/08 10:29:39 itojun Exp $ */ |
---|
4 | |
---|
5 | /* |
---|
6 | * Copyright (C) 2001 WIDE Project. |
---|
7 | * All rights reserved. |
---|
8 | * |
---|
9 | * Redistribution and use in source and binary forms, with or without |
---|
10 | * modification, are permitted provided that the following conditions |
---|
11 | * are met: |
---|
12 | * 1. Redistributions of source code must retain the above copyright |
---|
13 | * notice, this list of conditions and the following disclaimer. |
---|
14 | * 2. Redistributions in binary form must reproduce the above copyright |
---|
15 | * notice, this list of conditions and the following disclaimer in the |
---|
16 | * documentation and/or other materials provided with the distribution. |
---|
17 | * 3. Neither the name of the project nor the names of its contributors |
---|
18 | * may be used to endorse or promote products derived from this software |
---|
19 | * without specific prior written permission. |
---|
20 | * |
---|
21 | * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND |
---|
22 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
---|
23 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
---|
24 | * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE |
---|
25 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
---|
26 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
---|
27 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
---|
28 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
---|
29 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
---|
30 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
---|
31 | * SUCH DAMAGE. |
---|
32 | * THE AUTHORS DO NOT GUARANTEE THAT THIS SOFTWARE DOES NOT INFRINGE |
---|
33 | * ANY OTHERS' INTELLECTUAL PROPERTIES. IN NO EVENT SHALL THE AUTHORS |
---|
34 | * BE LIABLE FOR ANY INFRINGEMENT OF ANY OTHERS' INTELLECTUAL |
---|
35 | * PROPERTIES. |
---|
36 | */ |
---|
37 | |
---|
38 | #include <sys/cdefs.h> |
---|
39 | __FBSDID("$FreeBSD$"); |
---|
40 | |
---|
41 | #include <rtems/bsd/local/opt_inet.h> |
---|
42 | #include <rtems/bsd/local/opt_inet6.h> |
---|
43 | |
---|
44 | #include <sys/param.h> |
---|
45 | #include <sys/systm.h> |
---|
46 | #include <sys/malloc.h> |
---|
47 | #include <sys/socket.h> |
---|
48 | #include <sys/domain.h> |
---|
49 | #include <sys/syslog.h> |
---|
50 | #include <net/radix.h> |
---|
51 | #include <net/radix_mpath.h> |
---|
52 | #include <net/route.h> |
---|
53 | #include <net/route_var.h> |
---|
54 | #include <net/if.h> |
---|
55 | #include <net/if_var.h> |
---|
56 | |
---|
57 | /* |
---|
58 | * give some jitter to hash, to avoid synchronization between routers |
---|
59 | */ |
---|
60 | static uint32_t hashjitter; |
---|
61 | |
---|
62 | int |
---|
63 | rt_mpath_capable(struct rib_head *rnh) |
---|
64 | { |
---|
65 | |
---|
66 | return rnh->rnh_multipath; |
---|
67 | } |
---|
68 | |
---|
69 | int |
---|
70 | rn_mpath_capable(struct radix_head *rh) |
---|
71 | { |
---|
72 | |
---|
73 | return (rt_mpath_capable((struct rib_head *)rh)); |
---|
74 | } |
---|
75 | |
---|
76 | struct radix_node * |
---|
77 | rn_mpath_next(struct radix_node *rn) |
---|
78 | { |
---|
79 | struct radix_node *next; |
---|
80 | |
---|
81 | if (!rn->rn_dupedkey) |
---|
82 | return NULL; |
---|
83 | next = rn->rn_dupedkey; |
---|
84 | if (rn->rn_mask == next->rn_mask) |
---|
85 | return next; |
---|
86 | else |
---|
87 | return NULL; |
---|
88 | } |
---|
89 | |
---|
90 | #ifndef __rtems__ |
---|
91 | uint32_t |
---|
92 | #else /* __rtems__ */ |
---|
93 | u_int32_t |
---|
94 | #endif /* __rtems__ */ |
---|
95 | rn_mpath_count(struct radix_node *rn) |
---|
96 | { |
---|
97 | uint32_t i = 0; |
---|
98 | struct rtentry *rt; |
---|
99 | |
---|
100 | while (rn != NULL) { |
---|
101 | rt = (struct rtentry *)rn; |
---|
102 | i += rt->rt_weight; |
---|
103 | rn = rn_mpath_next(rn); |
---|
104 | } |
---|
105 | return (i); |
---|
106 | } |
---|
107 | |
---|
108 | struct rtentry * |
---|
109 | rt_mpath_matchgate(struct rtentry *rt, struct sockaddr *gate) |
---|
110 | { |
---|
111 | struct radix_node *rn; |
---|
112 | |
---|
113 | if (!gate || !rt->rt_gateway) |
---|
114 | return NULL; |
---|
115 | |
---|
116 | /* beyond here, we use rn as the master copy */ |
---|
117 | rn = (struct radix_node *)rt; |
---|
118 | do { |
---|
119 | rt = (struct rtentry *)rn; |
---|
120 | /* |
---|
121 | * we are removing an address alias that has |
---|
122 | * the same prefix as another address |
---|
123 | * we need to compare the interface address because |
---|
124 | * rt_gateway is a special sockadd_dl structure |
---|
125 | */ |
---|
126 | if (rt->rt_gateway->sa_family == AF_LINK) { |
---|
127 | if (!memcmp(rt->rt_ifa->ifa_addr, gate, gate->sa_len)) |
---|
128 | break; |
---|
129 | } |
---|
130 | |
---|
131 | /* |
---|
132 | * Check for other options: |
---|
133 | * 1) Routes with 'real' IPv4/IPv6 gateway |
---|
134 | * 2) Loopback host routes (another AF_LINK/sockadd_dl check) |
---|
135 | * */ |
---|
136 | if (rt->rt_gateway->sa_len == gate->sa_len && |
---|
137 | !memcmp(rt->rt_gateway, gate, gate->sa_len)) |
---|
138 | break; |
---|
139 | } while ((rn = rn_mpath_next(rn)) != NULL); |
---|
140 | |
---|
141 | return (struct rtentry *)rn; |
---|
142 | } |
---|
143 | |
---|
144 | /* |
---|
145 | * go through the chain and unlink "rt" from the list |
---|
146 | * the caller will free "rt" |
---|
147 | */ |
---|
148 | int |
---|
149 | rt_mpath_deldup(struct rtentry *headrt, struct rtentry *rt) |
---|
150 | { |
---|
151 | struct radix_node *t, *tt; |
---|
152 | |
---|
153 | if (!headrt || !rt) |
---|
154 | return (0); |
---|
155 | t = (struct radix_node *)headrt; |
---|
156 | tt = rn_mpath_next(t); |
---|
157 | while (tt) { |
---|
158 | if (tt == (struct radix_node *)rt) { |
---|
159 | t->rn_dupedkey = tt->rn_dupedkey; |
---|
160 | tt->rn_dupedkey = NULL; |
---|
161 | tt->rn_flags &= ~RNF_ACTIVE; |
---|
162 | tt[1].rn_flags &= ~RNF_ACTIVE; |
---|
163 | return (1); |
---|
164 | } |
---|
165 | t = tt; |
---|
166 | tt = rn_mpath_next((struct radix_node *)t); |
---|
167 | } |
---|
168 | return (0); |
---|
169 | } |
---|
170 | |
---|
171 | /* |
---|
172 | * check if we have the same key/mask/gateway on the table already. |
---|
173 | * Assume @rt rt_key host bits are cleared according to @netmask |
---|
174 | */ |
---|
175 | int |
---|
176 | rt_mpath_conflict(struct rib_head *rnh, struct rtentry *rt, |
---|
177 | struct sockaddr *netmask) |
---|
178 | { |
---|
179 | struct radix_node *rn, *rn1; |
---|
180 | struct rtentry *rt1; |
---|
181 | |
---|
182 | rn = (struct radix_node *)rt; |
---|
183 | rn1 = rnh->rnh_lookup(rt_key(rt), netmask, &rnh->head); |
---|
184 | if (!rn1 || rn1->rn_flags & RNF_ROOT) |
---|
185 | return (0); |
---|
186 | |
---|
187 | /* key/mask are the same. compare gateway for all multipaths */ |
---|
188 | do { |
---|
189 | rt1 = (struct rtentry *)rn1; |
---|
190 | |
---|
191 | /* sanity: no use in comparing the same thing */ |
---|
192 | if (rn1 == rn) |
---|
193 | continue; |
---|
194 | |
---|
195 | if (rt1->rt_gateway->sa_family == AF_LINK) { |
---|
196 | if (rt1->rt_ifa->ifa_addr->sa_len != rt->rt_ifa->ifa_addr->sa_len || |
---|
197 | bcmp(rt1->rt_ifa->ifa_addr, rt->rt_ifa->ifa_addr, |
---|
198 | rt1->rt_ifa->ifa_addr->sa_len)) |
---|
199 | continue; |
---|
200 | } else { |
---|
201 | if (rt1->rt_gateway->sa_len != rt->rt_gateway->sa_len || |
---|
202 | bcmp(rt1->rt_gateway, rt->rt_gateway, |
---|
203 | rt1->rt_gateway->sa_len)) |
---|
204 | continue; |
---|
205 | } |
---|
206 | |
---|
207 | /* all key/mask/gateway are the same. conflicting entry. */ |
---|
208 | return (EEXIST); |
---|
209 | } while ((rn1 = rn_mpath_next(rn1)) != NULL); |
---|
210 | |
---|
211 | return (0); |
---|
212 | } |
---|
213 | |
---|
214 | static struct rtentry * |
---|
215 | rt_mpath_selectrte(struct rtentry *rte, uint32_t hash) |
---|
216 | { |
---|
217 | struct radix_node *rn0, *rn; |
---|
218 | uint32_t total_weight; |
---|
219 | struct rtentry *rt; |
---|
220 | int64_t weight; |
---|
221 | |
---|
222 | /* beyond here, we use rn as the master copy */ |
---|
223 | rn0 = rn = (struct radix_node *)rte; |
---|
224 | rt = rte; |
---|
225 | |
---|
226 | /* gw selection by Modulo-N Hash (RFC2991) XXX need improvement? */ |
---|
227 | total_weight = rn_mpath_count(rn0); |
---|
228 | hash += hashjitter; |
---|
229 | hash %= total_weight; |
---|
230 | for (weight = abs((int32_t)hash); |
---|
231 | rt != NULL && weight >= rt->rt_weight; |
---|
232 | weight -= (rt == NULL) ? 0 : rt->rt_weight) { |
---|
233 | |
---|
234 | /* stay within the multipath routes */ |
---|
235 | if (rn->rn_dupedkey && rn->rn_mask != rn->rn_dupedkey->rn_mask) |
---|
236 | break; |
---|
237 | rn = rn->rn_dupedkey; |
---|
238 | rt = (struct rtentry *)rn; |
---|
239 | } |
---|
240 | |
---|
241 | return (rt); |
---|
242 | } |
---|
243 | |
---|
244 | struct rtentry * |
---|
245 | rt_mpath_select(struct rtentry *rte, uint32_t hash) |
---|
246 | { |
---|
247 | if (rn_mpath_next((struct radix_node *)rte) == NULL) |
---|
248 | return (rte); |
---|
249 | |
---|
250 | return (rt_mpath_selectrte(rte, hash)); |
---|
251 | } |
---|
252 | |
---|
253 | void |
---|
254 | rtalloc_mpath_fib(struct route *ro, uint32_t hash, u_int fibnum) |
---|
255 | { |
---|
256 | struct rtentry *rt; |
---|
257 | |
---|
258 | /* |
---|
259 | * XXX we don't attempt to lookup cached route again; what should |
---|
260 | * be done for sendto(3) case? |
---|
261 | */ |
---|
262 | if (ro->ro_rt && ro->ro_rt->rt_ifp && (ro->ro_rt->rt_flags & RTF_UP) |
---|
263 | && RT_LINK_IS_UP(ro->ro_rt->rt_ifp)) |
---|
264 | return; |
---|
265 | ro->ro_rt = rtalloc1_fib(&ro->ro_dst, 1, 0, fibnum); |
---|
266 | |
---|
267 | /* if the route does not exist or it is not multipath, don't care */ |
---|
268 | if (ro->ro_rt == NULL) |
---|
269 | return; |
---|
270 | if (rn_mpath_next((struct radix_node *)ro->ro_rt) == NULL) { |
---|
271 | RT_UNLOCK(ro->ro_rt); |
---|
272 | return; |
---|
273 | } |
---|
274 | |
---|
275 | rt = rt_mpath_selectrte(ro->ro_rt, hash); |
---|
276 | /* XXX try filling rt_gwroute and avoid unreachable gw */ |
---|
277 | |
---|
278 | /* gw selection has failed - there must be only zero weight routes */ |
---|
279 | if (!rt) { |
---|
280 | RT_UNLOCK(ro->ro_rt); |
---|
281 | ro->ro_rt = NULL; |
---|
282 | return; |
---|
283 | } |
---|
284 | if (ro->ro_rt != rt) { |
---|
285 | RTFREE_LOCKED(ro->ro_rt); |
---|
286 | ro->ro_rt = rt; |
---|
287 | RT_LOCK(ro->ro_rt); |
---|
288 | RT_ADDREF(ro->ro_rt); |
---|
289 | |
---|
290 | } |
---|
291 | RT_UNLOCK(ro->ro_rt); |
---|
292 | } |
---|
293 | |
---|
294 | extern int in6_inithead(void **head, int off); |
---|
295 | extern int in_inithead(void **head, int off); |
---|
296 | |
---|
297 | #ifdef INET |
---|
298 | int |
---|
299 | rn4_mpath_inithead(void **head, int off) |
---|
300 | { |
---|
301 | struct rib_head *rnh; |
---|
302 | |
---|
303 | hashjitter = arc4random(); |
---|
304 | if (in_inithead(head, off) == 1) { |
---|
305 | rnh = (struct rib_head *)*head; |
---|
306 | rnh->rnh_multipath = 1; |
---|
307 | return 1; |
---|
308 | } else |
---|
309 | return 0; |
---|
310 | } |
---|
311 | #endif |
---|
312 | |
---|
313 | #ifdef INET6 |
---|
314 | int |
---|
315 | rn6_mpath_inithead(void **head, int off) |
---|
316 | { |
---|
317 | struct rib_head *rnh; |
---|
318 | |
---|
319 | hashjitter = arc4random(); |
---|
320 | if (in6_inithead(head, off) == 1) { |
---|
321 | rnh = (struct rib_head *)*head; |
---|
322 | rnh->rnh_multipath = 1; |
---|
323 | return 1; |
---|
324 | } else |
---|
325 | return 0; |
---|
326 | } |
---|
327 | |
---|
328 | #endif |
---|