]>
Commit | Line | Data |
---|---|---|
ca10883e DS |
1 | /* |
2 | Copyright (c) 2007, 2008 by Juliusz Chroboczek | |
3 | Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek | |
4 | ||
5 | Permission is hereby granted, free of charge, to any person obtaining a copy | |
6 | of this software and associated documentation files (the "Software"), to deal | |
7 | in the Software without restriction, including without limitation the rights | |
8 | to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
9 | copies of the Software, and to permit persons to whom the Software is | |
10 | furnished to do so, subject to the following conditions: | |
11 | ||
12 | The above copyright notice and this permission notice shall be included in | |
13 | all copies or substantial portions of the Software. | |
14 | ||
15 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
16 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
17 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
18 | AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
19 | LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
20 | OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | |
21 | THE SOFTWARE. | |
22 | */ | |
23 | ||
24 | #include <zebra.h> | |
25 | #include "if.h" | |
26 | ||
27 | #include "babeld.h" | |
28 | #include "util.h" | |
29 | #include "kernel.h" | |
30 | #include "babel_interface.h" | |
31 | #include "source.h" | |
32 | #include "neighbour.h" | |
33 | #include "route.h" | |
34 | #include "xroute.h" | |
35 | #include "message.h" | |
36 | #include "resend.h" | |
37 | ||
38 | static void consider_route(struct babel_route *route); | |
39 | ||
40 | struct babel_route **routes = NULL; | |
41 | static int route_slots = 0, max_route_slots = 0; | |
42 | int kernel_metric = 0; | |
43 | int diversity_kind = DIVERSITY_NONE; | |
44 | int diversity_factor = BABEL_DEFAULT_DIVERSITY_FACTOR; | |
45 | int keep_unfeasible = 0; | |
46 | ||
47 | int smoothing_half_life = 0; | |
48 | static int two_to_the_one_over_hl = 0; /* 2^(1/hl) * 0x10000 */ | |
49 | ||
50 | /* We maintain a list of "slots", ordered by prefix. Every slot | |
51 | contains a linked list of the routes to this prefix, with the | |
52 | installed route, if any, at the head of the list. */ | |
53 | ||
54 | static int | |
55 | route_compare(const unsigned char *prefix, unsigned char plen, | |
56 | struct babel_route *route) | |
57 | { | |
58 | int i = memcmp(prefix, route->src->prefix, 16); | |
59 | if(i != 0) | |
60 | return i; | |
61 | ||
62 | if(plen < route->src->plen) | |
63 | return -1; | |
64 | else if(plen > route->src->plen) | |
65 | return 1; | |
66 | else | |
67 | return 0; | |
68 | } | |
69 | ||
70 | /* Performs binary search, returns -1 in case of failure. In the latter | |
71 | case, new_return is the place where to insert the new element. */ | |
72 | ||
73 | static int | |
74 | find_route_slot(const unsigned char *prefix, unsigned char plen, | |
75 | int *new_return) | |
76 | { | |
77 | int p, m, g, c; | |
78 | ||
79 | if(route_slots < 1) { | |
80 | if(new_return) | |
81 | *new_return = 0; | |
82 | return -1; | |
83 | } | |
84 | ||
85 | p = 0; g = route_slots - 1; | |
86 | ||
87 | do { | |
88 | m = (p + g) / 2; | |
89 | c = route_compare(prefix, plen, routes[m]); | |
90 | if(c == 0) | |
91 | return m; | |
92 | else if(c < 0) | |
93 | g = m - 1; | |
94 | else | |
95 | p = m + 1; | |
96 | } while(p <= g); | |
97 | ||
98 | if(new_return) | |
99 | *new_return = p; | |
100 | ||
101 | return -1; | |
102 | } | |
103 | ||
104 | struct babel_route * | |
105 | find_route(const unsigned char *prefix, unsigned char plen, | |
106 | struct neighbour *neigh, const unsigned char *nexthop) | |
107 | { | |
108 | struct babel_route *route; | |
109 | int i = find_route_slot(prefix, plen, NULL); | |
110 | ||
111 | if(i < 0) | |
112 | return NULL; | |
113 | ||
114 | route = routes[i]; | |
115 | ||
116 | while(route) { | |
117 | if(route->neigh == neigh && memcmp(route->nexthop, nexthop, 16) == 0) | |
118 | return route; | |
119 | route = route->next; | |
120 | } | |
121 | ||
122 | return NULL; | |
123 | } | |
124 | ||
125 | struct babel_route * | |
126 | find_installed_route(const unsigned char *prefix, unsigned char plen) | |
127 | { | |
128 | int i = find_route_slot(prefix, plen, NULL); | |
129 | ||
130 | if(i >= 0 && routes[i]->installed) | |
131 | return routes[i]; | |
132 | ||
133 | return NULL; | |
134 | } | |
135 | ||
136 | /* Returns an overestimate of the number of installed routes. */ | |
137 | int | |
138 | installed_routes_estimate(void) | |
139 | { | |
140 | return route_slots; | |
141 | } | |
142 | ||
143 | static int | |
144 | resize_route_table(int new_slots) | |
145 | { | |
146 | struct babel_route **new_routes; | |
147 | assert(new_slots >= route_slots); | |
148 | ||
149 | if(new_slots == 0) { | |
150 | new_routes = NULL; | |
151 | free(routes); | |
152 | } else { | |
153 | new_routes = realloc(routes, new_slots * sizeof(struct babel_route*)); | |
154 | if(new_routes == NULL) | |
155 | return -1; | |
156 | } | |
157 | ||
158 | max_route_slots = new_slots; | |
159 | routes = new_routes; | |
160 | return 1; | |
161 | } | |
162 | ||
163 | /* Insert a route into the table. If successful, retains the route. | |
164 | On failure, caller must free the route. */ | |
165 | static struct babel_route * | |
166 | insert_route(struct babel_route *route) | |
167 | { | |
168 | int i, n; | |
169 | ||
170 | assert(!route->installed); | |
171 | ||
172 | i = find_route_slot(route->src->prefix, route->src->plen, &n); | |
173 | ||
174 | if(i < 0) { | |
175 | if(route_slots >= max_route_slots) | |
176 | resize_route_table(max_route_slots < 1 ? 8 : 2 * max_route_slots); | |
177 | if(route_slots >= max_route_slots) | |
178 | return NULL; | |
179 | route->next = NULL; | |
180 | if(n < route_slots) | |
181 | memmove(routes + n + 1, routes + n, | |
182 | (route_slots - n) * sizeof(struct babel_route*)); | |
183 | route_slots++; | |
184 | routes[n] = route; | |
185 | } else { | |
186 | struct babel_route *r; | |
187 | r = routes[i]; | |
188 | while(r->next) | |
189 | r = r->next; | |
190 | r->next = route; | |
191 | route->next = NULL; | |
192 | } | |
193 | ||
194 | return route; | |
195 | } | |
196 | ||
197 | void | |
198 | flush_route(struct babel_route *route) | |
199 | { | |
200 | int i; | |
201 | struct source *src; | |
202 | unsigned oldmetric; | |
203 | int lost = 0; | |
204 | ||
205 | oldmetric = route_metric(route); | |
206 | src = route->src; | |
207 | ||
208 | if(route->installed) { | |
209 | uninstall_route(route); | |
210 | lost = 1; | |
211 | } | |
212 | ||
213 | i = find_route_slot(route->src->prefix, route->src->plen, NULL); | |
214 | assert(i >= 0 && i < route_slots); | |
215 | ||
216 | if(route == routes[i]) { | |
217 | routes[i] = route->next; | |
218 | route->next = NULL; | |
219 | free(route); | |
220 | ||
221 | if(routes[i] == NULL) { | |
222 | if(i < route_slots - 1) | |
223 | memmove(routes + i, routes + i + 1, | |
224 | (route_slots - i - 1) * sizeof(struct babel_route*)); | |
225 | routes[route_slots - 1] = NULL; | |
226 | route_slots--; | |
227 | } | |
228 | ||
229 | if(route_slots == 0) | |
230 | resize_route_table(0); | |
231 | else if(max_route_slots > 8 && route_slots < max_route_slots / 4) | |
232 | resize_route_table(max_route_slots / 2); | |
233 | } else { | |
234 | struct babel_route *r = routes[i]; | |
235 | while(r->next != route) | |
236 | r = r->next; | |
237 | r->next = route->next; | |
238 | route->next = NULL; | |
239 | free(route); | |
240 | } | |
241 | ||
242 | if(lost) | |
243 | route_lost(src, oldmetric); | |
244 | ||
245 | release_source(src); | |
246 | } | |
247 | ||
248 | void | |
249 | flush_all_routes() | |
250 | { | |
251 | int i; | |
252 | ||
253 | /* Start from the end, to avoid shifting the table. */ | |
254 | i = route_slots - 1; | |
255 | while(i >= 0) { | |
256 | while(i < route_slots) { | |
257 | /* Uninstall first, to avoid calling route_lost. */ | |
258 | if(routes[i]->installed) | |
259 | uninstall_route(routes[i]); | |
260 | flush_route(routes[i]); | |
261 | } | |
262 | i--; | |
263 | } | |
264 | ||
265 | check_sources_released(); | |
266 | } | |
267 | ||
268 | void | |
269 | flush_neighbour_routes(struct neighbour *neigh) | |
270 | { | |
271 | int i; | |
272 | ||
273 | i = 0; | |
274 | while(i < route_slots) { | |
275 | struct babel_route *r; | |
276 | r = routes[i]; | |
277 | while(r) { | |
278 | if(r->neigh == neigh) { | |
279 | flush_route(r); | |
280 | goto again; | |
281 | } | |
282 | r = r->next; | |
283 | } | |
284 | i++; | |
285 | again: | |
286 | ; | |
287 | } | |
288 | } | |
289 | ||
290 | void | |
291 | flush_interface_routes(struct interface *ifp, int v4only) | |
292 | { | |
293 | int i; | |
294 | ||
295 | i = 0; | |
296 | while(i < route_slots) { | |
297 | struct babel_route *r; | |
298 | r = routes[i]; | |
299 | while(r) { | |
300 | if(r->neigh->ifp == ifp && | |
301 | (!v4only || v4mapped(r->nexthop))) { | |
302 | flush_route(r); | |
303 | goto again; | |
304 | } | |
305 | r = r->next; | |
306 | } | |
307 | i++; | |
308 | again: | |
309 | ; | |
310 | } | |
311 | } | |
312 | ||
313 | struct route_stream { | |
314 | int installed; | |
315 | int index; | |
316 | struct babel_route *next; | |
317 | }; | |
318 | ||
319 | ||
320 | struct route_stream * | |
321 | route_stream(int installed) | |
322 | { | |
323 | struct route_stream *stream; | |
324 | ||
325 | stream = malloc(sizeof(struct route_stream)); | |
326 | if(stream == NULL) | |
327 | return NULL; | |
328 | ||
329 | stream->installed = installed; | |
330 | stream->index = installed ? 0 : -1; | |
331 | stream->next = NULL; | |
332 | ||
333 | return stream; | |
334 | } | |
335 | ||
336 | struct babel_route * | |
337 | route_stream_next(struct route_stream *stream) | |
338 | { | |
339 | if(stream->installed) { | |
340 | while(stream->index < route_slots && !routes[stream->index]->installed) | |
341 | stream->index++; | |
342 | ||
343 | if(stream->index < route_slots) | |
344 | return routes[stream->index++]; | |
345 | else | |
346 | return NULL; | |
347 | } else { | |
348 | struct babel_route *next; | |
349 | if(!stream->next) { | |
350 | stream->index++; | |
351 | if(stream->index >= route_slots) | |
352 | return NULL; | |
353 | stream->next = routes[stream->index]; | |
354 | } | |
355 | next = stream->next; | |
356 | stream->next = next->next; | |
357 | return next; | |
358 | } | |
359 | } | |
360 | ||
361 | void | |
362 | route_stream_done(struct route_stream *stream) | |
363 | { | |
364 | free(stream); | |
365 | } | |
366 | ||
367 | static int | |
368 | metric_to_kernel(int metric) | |
369 | { | |
370 | return metric < INFINITY ? kernel_metric : KERNEL_INFINITY; | |
371 | } | |
372 | ||
373 | /* This is used to maintain the invariant that the installed route is at | |
374 | the head of the list. */ | |
375 | static void | |
376 | move_installed_route(struct babel_route *route, int i) | |
377 | { | |
378 | assert(i >= 0 && i < route_slots); | |
379 | assert(route->installed); | |
380 | ||
381 | if(route != routes[i]) { | |
382 | struct babel_route *r = routes[i]; | |
383 | while(r->next != route) | |
384 | r = r->next; | |
385 | r->next = route->next; | |
386 | route->next = routes[i]; | |
387 | routes[i] = route; | |
388 | } | |
389 | } | |
390 | ||
391 | void | |
392 | install_route(struct babel_route *route) | |
393 | { | |
394 | int i, rc; | |
395 | ||
396 | if(route->installed) | |
397 | return; | |
398 | ||
399 | if(!route_feasible(route)) | |
400 | zlog_err("WARNING: installing unfeasible route " | |
401 | "(this shouldn't happen)."); | |
402 | ||
403 | i = find_route_slot(route->src->prefix, route->src->plen, NULL); | |
404 | assert(i >= 0 && i < route_slots); | |
405 | ||
406 | if(routes[i] != route && routes[i]->installed) { | |
407 | zlog_err("WARNING: attempting to install duplicate route " | |
408 | "(this shouldn't happen)."); | |
409 | return; | |
410 | } | |
411 | ||
412 | rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen, | |
413 | route->nexthop, | |
414 | route->neigh->ifp->ifindex, | |
415 | metric_to_kernel(route_metric(route)), NULL, 0, 0); | |
416 | if(rc < 0) { | |
417 | int save = errno; | |
418 | zlog_err("kernel_route(ADD): %s", safe_strerror(errno)); | |
419 | if(save != EEXIST) | |
420 | return; | |
421 | } | |
422 | route->installed = 1; | |
423 | move_installed_route(route, i); | |
424 | ||
425 | } | |
426 | ||
427 | void | |
428 | uninstall_route(struct babel_route *route) | |
429 | { | |
430 | int rc; | |
431 | ||
432 | if(!route->installed) | |
433 | return; | |
434 | ||
435 | rc = kernel_route(ROUTE_FLUSH, route->src->prefix, route->src->plen, | |
436 | route->nexthop, | |
437 | route->neigh->ifp->ifindex, | |
438 | metric_to_kernel(route_metric(route)), NULL, 0, 0); | |
439 | if(rc < 0) | |
440 | zlog_err("kernel_route(FLUSH): %s", safe_strerror(errno)); | |
441 | ||
442 | route->installed = 0; | |
443 | } | |
444 | ||
445 | /* This is equivalent to uninstall_route followed with install_route, | |
446 | but without the race condition. The destination of both routes | |
447 | must be the same. */ | |
448 | ||
449 | static void | |
450 | switch_routes(struct babel_route *old, struct babel_route *new) | |
451 | { | |
452 | int rc; | |
453 | ||
454 | if(!old) { | |
455 | install_route(new); | |
456 | return; | |
457 | } | |
458 | ||
459 | if(!old->installed) | |
460 | return; | |
461 | ||
462 | if(!route_feasible(new)) | |
463 | zlog_err("WARNING: switching to unfeasible route " | |
464 | "(this shouldn't happen)."); | |
465 | ||
466 | rc = kernel_route(ROUTE_MODIFY, old->src->prefix, old->src->plen, | |
467 | old->nexthop, old->neigh->ifp->ifindex, | |
468 | metric_to_kernel(route_metric(old)), | |
469 | new->nexthop, new->neigh->ifp->ifindex, | |
470 | metric_to_kernel(route_metric(new))); | |
471 | if(rc < 0) { | |
472 | zlog_err("kernel_route(MODIFY): %s", safe_strerror(errno)); | |
473 | return; | |
474 | } | |
475 | ||
476 | old->installed = 0; | |
477 | new->installed = 1; | |
478 | move_installed_route(new, find_route_slot(new->src->prefix, new->src->plen, | |
479 | NULL)); | |
480 | } | |
481 | ||
482 | static void | |
483 | change_route_metric(struct babel_route *route, | |
484 | unsigned refmetric, unsigned cost, unsigned add) | |
485 | { | |
486 | int old, new; | |
487 | int newmetric = MIN(refmetric + cost + add, INFINITY); | |
488 | ||
489 | old = metric_to_kernel(route_metric(route)); | |
490 | new = metric_to_kernel(newmetric); | |
491 | ||
492 | if(route->installed && old != new) { | |
493 | int rc; | |
494 | rc = kernel_route(ROUTE_MODIFY, route->src->prefix, route->src->plen, | |
495 | route->nexthop, route->neigh->ifp->ifindex, | |
496 | old, | |
497 | route->nexthop, route->neigh->ifp->ifindex, | |
498 | new); | |
499 | if(rc < 0) { | |
500 | zlog_err("kernel_route(MODIFY metric): %s", safe_strerror(errno)); | |
501 | return; | |
502 | } | |
503 | } | |
504 | ||
505 | /* Update route->smoothed_metric using the old metric. */ | |
506 | route_smoothed_metric(route); | |
507 | ||
508 | route->refmetric = refmetric; | |
509 | route->cost = cost; | |
510 | route->add_metric = add; | |
511 | ||
512 | if(smoothing_half_life == 0) { | |
513 | route->smoothed_metric = route_metric(route); | |
514 | route->smoothed_metric_time = babel_now.tv_sec; | |
515 | } | |
516 | } | |
517 | ||
518 | static void | |
519 | retract_route(struct babel_route *route) | |
520 | { | |
521 | /* We cannot simply remove the route from the kernel, as that might | |
522 | cause a routing loop -- see RFC 6126 Sections 2.8 and 3.5.5. */ | |
523 | change_route_metric(route, INFINITY, INFINITY, 0); | |
524 | } | |
525 | ||
526 | int | |
527 | route_feasible(struct babel_route *route) | |
528 | { | |
529 | return update_feasible(route->src, route->seqno, route->refmetric); | |
530 | } | |
531 | ||
532 | int | |
533 | route_old(struct babel_route *route) | |
534 | { | |
535 | return route->time < babel_now.tv_sec - route->hold_time * 7 / 8; | |
536 | } | |
537 | ||
538 | int | |
539 | route_expired(struct babel_route *route) | |
540 | { | |
541 | return route->time < babel_now.tv_sec - route->hold_time; | |
542 | } | |
543 | ||
544 | static int | |
545 | channels_interfere(int ch1, int ch2) | |
546 | { | |
547 | if(ch1 == BABEL_IF_CHANNEL_NONINTERFERING | |
548 | || ch2 == BABEL_IF_CHANNEL_NONINTERFERING) | |
549 | return 0; | |
550 | if(ch1 == BABEL_IF_CHANNEL_INTERFERING | |
551 | || ch2 == BABEL_IF_CHANNEL_INTERFERING) | |
552 | return 1; | |
553 | return ch1 == ch2; | |
554 | } | |
555 | ||
556 | int | |
557 | route_interferes(struct babel_route *route, struct interface *ifp) | |
558 | { | |
559 | struct babel_interface *babel_ifp = NULL; | |
560 | switch(diversity_kind) { | |
561 | case DIVERSITY_NONE: | |
562 | return 1; | |
563 | case DIVERSITY_INTERFACE_1: | |
564 | return route->neigh->ifp == ifp; | |
565 | case DIVERSITY_CHANNEL_1: | |
566 | case DIVERSITY_CHANNEL: | |
567 | if(route->neigh->ifp == ifp) | |
568 | return 1; | |
569 | babel_ifp = babel_get_if_nfo(ifp); | |
570 | if(channels_interfere(babel_ifp->channel, | |
571 | babel_get_if_nfo(route->neigh->ifp)->channel)) | |
572 | return 1; | |
573 | if(diversity_kind == DIVERSITY_CHANNEL) { | |
574 | int i; | |
575 | for(i = 0; i < DIVERSITY_HOPS; i++) { | |
576 | if(route->channels[i] == 0) | |
577 | break; | |
578 | if(channels_interfere(babel_ifp->channel, route->channels[i])) | |
579 | return 1; | |
580 | } | |
581 | } | |
582 | return 0; | |
583 | default: | |
584 | zlog_err("Unknown kind of diversity."); | |
585 | return 1; | |
586 | } | |
587 | } | |
588 | ||
589 | int | |
590 | update_feasible(struct source *src, | |
591 | unsigned short seqno, unsigned short refmetric) | |
592 | { | |
593 | if(src == NULL) | |
594 | return 1; | |
595 | ||
596 | if(src->time < babel_now.tv_sec - SOURCE_GC_TIME) | |
597 | /* Never mind what is probably stale data */ | |
598 | return 1; | |
599 | ||
600 | if(refmetric >= INFINITY) | |
601 | /* Retractions are always feasible */ | |
602 | return 1; | |
603 | ||
604 | return (seqno_compare(seqno, src->seqno) > 0 || | |
605 | (src->seqno == seqno && refmetric < src->metric)); | |
606 | } | |
607 | ||
608 | void | |
609 | change_smoothing_half_life(int half_life) | |
610 | { | |
611 | if(half_life <= 0) { | |
612 | smoothing_half_life = 0; | |
613 | two_to_the_one_over_hl = 0; | |
614 | return; | |
615 | } | |
616 | ||
617 | smoothing_half_life = half_life; | |
618 | switch(smoothing_half_life) { | |
619 | case 1: two_to_the_one_over_hl = 131072; break; | |
620 | case 2: two_to_the_one_over_hl = 92682; break; | |
621 | case 3: two_to_the_one_over_hl = 82570; break; | |
622 | case 4: two_to_the_one_over_hl = 77935; break; | |
623 | default: | |
624 | /* 2^(1/x) is 1 + log(2)/x + O(1/x^2) at infinity. */ | |
625 | two_to_the_one_over_hl = 0x10000 + 45426 / half_life; | |
626 | } | |
627 | } | |
628 | ||
629 | /* Update the smoothed metric, return the new value. */ | |
630 | int | |
631 | route_smoothed_metric(struct babel_route *route) | |
632 | { | |
633 | int metric = route_metric(route); | |
634 | ||
635 | if(smoothing_half_life <= 0 || /* no smoothing */ | |
636 | metric >= INFINITY || /* route retracted */ | |
637 | route->smoothed_metric_time > babel_now.tv_sec || /* clock stepped */ | |
638 | route->smoothed_metric == metric) { /* already converged */ | |
639 | route->smoothed_metric = metric; | |
640 | route->smoothed_metric_time = babel_now.tv_sec; | |
641 | } else { | |
642 | int diff; | |
643 | /* We randomise the computation, to minimise global synchronisation | |
644 | and hence oscillations. */ | |
645 | while(route->smoothed_metric_time <= | |
646 | babel_now.tv_sec - smoothing_half_life) { | |
647 | diff = metric - route->smoothed_metric; | |
648 | route->smoothed_metric += roughly(diff) / 2; | |
649 | route->smoothed_metric_time += smoothing_half_life; | |
650 | } | |
651 | while(route->smoothed_metric_time < babel_now.tv_sec) { | |
652 | diff = metric - route->smoothed_metric; | |
653 | route->smoothed_metric += | |
654 | roughly(diff) * (two_to_the_one_over_hl - 0x10000) / 0x10000; | |
655 | route->smoothed_metric_time++; | |
656 | } | |
657 | ||
658 | diff = metric - route->smoothed_metric; | |
659 | if(diff > -4 && diff < 4) | |
660 | route->smoothed_metric = metric; | |
661 | } | |
662 | ||
663 | /* change_route_metric relies on this */ | |
664 | assert(route->smoothed_metric_time == babel_now.tv_sec); | |
665 | return route->smoothed_metric; | |
666 | } | |
667 | ||
668 | static int | |
669 | route_acceptable(struct babel_route *route, int feasible, | |
670 | struct neighbour *exclude) | |
671 | { | |
672 | if(route_expired(route)) | |
673 | return 0; | |
674 | if(feasible && !route_feasible(route)) | |
675 | return 0; | |
676 | if(exclude && route->neigh == exclude) | |
677 | return 0; | |
678 | return 1; | |
679 | } | |
680 | ||
681 | /* Find the best route according to the weak ordering. Any | |
682 | linearisation of the strong ordering (see consider_route) will do, | |
683 | we use sm <= sm'. We could probably use a lexical ordering, but | |
684 | that's probably overkill. */ | |
685 | ||
686 | struct babel_route * | |
687 | find_best_route(const unsigned char *prefix, unsigned char plen, int feasible, | |
688 | struct neighbour *exclude) | |
689 | { | |
690 | struct babel_route *route = NULL, *r = NULL; | |
691 | int i = find_route_slot(prefix, plen, NULL); | |
692 | ||
693 | if(i < 0) | |
694 | return NULL; | |
695 | ||
696 | route = routes[i]; | |
697 | while(route && !route_acceptable(route, feasible, exclude)) | |
698 | route = route->next; | |
699 | ||
700 | if(!route) | |
701 | return NULL; | |
702 | ||
703 | r = route->next; | |
704 | while(r) { | |
705 | if(route_acceptable(r, feasible, exclude) && | |
706 | (route_smoothed_metric(r) < route_smoothed_metric(route))) | |
707 | route = r; | |
708 | r = r->next; | |
709 | } | |
710 | ||
711 | return route; | |
712 | } | |
713 | ||
714 | void | |
715 | update_route_metric(struct babel_route *route) | |
716 | { | |
717 | int oldmetric = route_metric(route); | |
718 | int old_smoothed_metric = route_smoothed_metric(route); | |
719 | ||
720 | if(route_expired(route)) { | |
721 | if(route->refmetric < INFINITY) { | |
722 | route->seqno = seqno_plus(route->src->seqno, 1); | |
723 | retract_route(route); | |
724 | if(oldmetric < INFINITY) | |
725 | route_changed(route, route->src, oldmetric); | |
726 | } | |
727 | } else { | |
728 | struct neighbour *neigh = route->neigh; | |
729 | int add_metric = input_filter(route->src->id, | |
730 | route->src->prefix, route->src->plen, | |
731 | neigh->address, | |
732 | neigh->ifp->ifindex); | |
733 | change_route_metric(route, route->refmetric, | |
734 | neighbour_cost(route->neigh), add_metric); | |
735 | if(route_metric(route) != oldmetric || | |
736 | route_smoothed_metric(route) != old_smoothed_metric) | |
737 | route_changed(route, route->src, oldmetric); | |
738 | } | |
739 | } | |
740 | ||
741 | /* Called whenever a neighbour's cost changes, to update the metric of | |
742 | all routes through that neighbour. */ | |
743 | void | |
744 | update_neighbour_metric(struct neighbour *neigh, int changed) | |
745 | { | |
746 | ||
747 | if(changed) { | |
748 | int i; | |
749 | ||
750 | for(i = 0; i < route_slots; i++) { | |
751 | struct babel_route *r = routes[i]; | |
752 | while(r) { | |
753 | if(r->neigh == neigh) | |
754 | update_route_metric(r); | |
755 | r = r->next; | |
756 | } | |
757 | } | |
758 | } | |
759 | } | |
760 | ||
761 | void | |
762 | update_interface_metric(struct interface *ifp) | |
763 | { | |
764 | int i; | |
765 | ||
766 | for(i = 0; i < route_slots; i++) { | |
767 | struct babel_route *r = routes[i]; | |
768 | while(r) { | |
769 | if(r->neigh->ifp == ifp) | |
770 | update_route_metric(r); | |
771 | r = r->next; | |
772 | } | |
773 | } | |
774 | } | |
775 | ||
776 | /* This is called whenever we receive an update. */ | |
777 | struct babel_route * | |
778 | update_route(const unsigned char *router_id, | |
779 | const unsigned char *prefix, unsigned char plen, | |
780 | unsigned short seqno, unsigned short refmetric, | |
781 | unsigned short interval, | |
782 | struct neighbour *neigh, const unsigned char *nexthop, | |
783 | const unsigned char *channels, int channels_len) | |
784 | { | |
785 | struct babel_route *route; | |
786 | struct source *src; | |
787 | int metric, feasible; | |
788 | int add_metric; | |
789 | int hold_time = MAX((4 * interval) / 100 + interval / 50, 15); | |
790 | ||
791 | if(memcmp(router_id, myid, 8) == 0) | |
792 | return NULL; | |
793 | ||
794 | if(martian_prefix(prefix, plen)) { | |
795 | zlog_err("Rejecting martian route to %s through %s.", | |
796 | format_prefix(prefix, plen), format_address(nexthop)); | |
797 | return NULL; | |
798 | } | |
799 | ||
800 | add_metric = input_filter(router_id, prefix, plen, | |
801 | neigh->address, neigh->ifp->ifindex); | |
802 | if(add_metric >= INFINITY) | |
803 | return NULL; | |
804 | ||
805 | route = find_route(prefix, plen, neigh, nexthop); | |
806 | ||
807 | if(route && memcmp(route->src->id, router_id, 8) == 0) | |
808 | /* Avoid scanning the source table. */ | |
809 | src = route->src; | |
810 | else | |
811 | src = find_source(router_id, prefix, plen, 1, seqno); | |
812 | ||
813 | if(src == NULL) | |
814 | return NULL; | |
815 | ||
816 | feasible = update_feasible(src, seqno, refmetric); | |
817 | metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY); | |
818 | ||
819 | if(route) { | |
820 | struct source *oldsrc; | |
821 | unsigned short oldmetric; | |
822 | int lost = 0; | |
823 | ||
824 | oldsrc = route->src; | |
825 | oldmetric = route_metric(route); | |
826 | ||
827 | /* If a successor switches sources, we must accept his update even | |
828 | if it makes a route unfeasible in order to break any routing loops | |
829 | in a timely manner. If the source remains the same, we ignore | |
830 | the update. */ | |
831 | if(!feasible && route->installed) { | |
832 | debugf(BABEL_DEBUG_COMMON,"Unfeasible update for installed route to %s " | |
833 | "(%s %d %d -> %s %d %d).", | |
834 | format_prefix(src->prefix, src->plen), | |
835 | format_eui64(route->src->id), | |
836 | route->seqno, route->refmetric, | |
837 | format_eui64(src->id), seqno, refmetric); | |
838 | if(src != route->src) { | |
839 | uninstall_route(route); | |
840 | lost = 1; | |
841 | } | |
842 | } | |
843 | ||
844 | route->src = retain_source(src); | |
845 | if((feasible || keep_unfeasible) && refmetric < INFINITY) | |
846 | route->time = babel_now.tv_sec; | |
847 | route->seqno = seqno; | |
848 | ||
849 | memset(&route->channels, 0, sizeof(route->channels)); | |
850 | if(channels_len > 0) | |
851 | memcpy(&route->channels, channels, | |
852 | MIN(channels_len, DIVERSITY_HOPS)); | |
853 | ||
854 | change_route_metric(route, | |
855 | refmetric, neighbour_cost(neigh), add_metric); | |
856 | route->hold_time = hold_time; | |
857 | ||
858 | route_changed(route, oldsrc, oldmetric); | |
859 | if(lost) | |
860 | route_lost(oldsrc, oldmetric); | |
861 | ||
862 | if(!feasible) | |
863 | send_unfeasible_request(neigh, route->installed && route_old(route), | |
864 | seqno, metric, src); | |
865 | release_source(oldsrc); | |
866 | } else { | |
867 | struct babel_route *new_route; | |
868 | ||
869 | if(refmetric >= INFINITY) | |
870 | /* Somebody's retracting a route we never saw. */ | |
871 | return NULL; | |
872 | if(!feasible) { | |
873 | send_unfeasible_request(neigh, 0, seqno, metric, src); | |
874 | if(!keep_unfeasible) | |
875 | return NULL; | |
876 | } | |
877 | ||
878 | route = malloc(sizeof(struct babel_route)); | |
879 | if(route == NULL) { | |
880 | perror("malloc(route)"); | |
881 | return NULL; | |
882 | } | |
883 | ||
884 | route->src = retain_source(src); | |
885 | route->refmetric = refmetric; | |
886 | route->cost = neighbour_cost(neigh); | |
887 | route->add_metric = add_metric; | |
888 | route->seqno = seqno; | |
889 | route->neigh = neigh; | |
890 | memcpy(route->nexthop, nexthop, 16); | |
891 | route->time = babel_now.tv_sec; | |
892 | route->hold_time = hold_time; | |
893 | route->smoothed_metric = MAX(route_metric(route), INFINITY / 2); | |
894 | route->smoothed_metric_time = babel_now.tv_sec; | |
895 | route->installed = 0; | |
896 | memset(&route->channels, 0, sizeof(route->channels)); | |
897 | if(channels_len > 0) | |
898 | memcpy(&route->channels, channels, | |
899 | MIN(channels_len, DIVERSITY_HOPS)); | |
900 | route->next = NULL; | |
901 | new_route = insert_route(route); | |
902 | if(new_route == NULL) { | |
903 | zlog_err("Couldn't insert route."); | |
904 | free(route); | |
905 | return NULL; | |
906 | } | |
907 | consider_route(route); | |
908 | } | |
909 | return route; | |
910 | } | |
911 | ||
912 | /* We just received an unfeasible update. If it's any good, send | |
913 | a request for a new seqno. */ | |
914 | void | |
915 | send_unfeasible_request(struct neighbour *neigh, int force, | |
916 | unsigned short seqno, unsigned short metric, | |
917 | struct source *src) | |
918 | { | |
919 | struct babel_route *route = find_installed_route(src->prefix, src->plen); | |
920 | ||
921 | if(seqno_minus(src->seqno, seqno) > 100) { | |
922 | /* Probably a source that lost its seqno. Let it time-out. */ | |
923 | return; | |
924 | } | |
925 | ||
926 | if(force || !route || route_metric(route) >= metric + 512) { | |
927 | send_unicast_multihop_request(neigh, src->prefix, src->plen, | |
928 | src->metric >= INFINITY ? | |
929 | src->seqno : | |
930 | seqno_plus(src->seqno, 1), | |
931 | src->id, 127); | |
932 | } | |
933 | } | |
934 | ||
935 | /* This takes a feasible route and decides whether to install it. | |
936 | This uses the strong ordering, which is defined by sm <= sm' AND | |
937 | m <= m'. This ordering is not total, which is what causes | |
938 | hysteresis. */ | |
939 | ||
940 | static void | |
941 | consider_route(struct babel_route *route) | |
942 | { | |
943 | struct babel_route *installed; | |
944 | struct xroute *xroute; | |
945 | ||
946 | if(route->installed) | |
947 | return; | |
948 | ||
949 | if(!route_feasible(route)) | |
950 | return; | |
951 | ||
952 | xroute = find_xroute(route->src->prefix, route->src->plen); | |
953 | if(xroute) | |
954 | return; | |
955 | ||
956 | installed = find_installed_route(route->src->prefix, route->src->plen); | |
957 | ||
958 | if(installed == NULL) | |
959 | goto install; | |
960 | ||
961 | if(route_metric(route) >= INFINITY) | |
962 | return; | |
963 | ||
964 | if(route_metric(installed) >= INFINITY) | |
965 | goto install; | |
966 | ||
967 | if(route_metric(installed) >= route_metric(route) && | |
968 | route_smoothed_metric(installed) > route_smoothed_metric(route)) | |
969 | goto install; | |
970 | ||
971 | return; | |
972 | ||
973 | install: | |
974 | switch_routes(installed, route); | |
975 | if(installed && route->installed) | |
976 | send_triggered_update(route, installed->src, route_metric(installed)); | |
977 | else | |
978 | send_update(NULL, 1, route->src->prefix, route->src->plen); | |
979 | return; | |
980 | } | |
981 | ||
982 | void | |
983 | retract_neighbour_routes(struct neighbour *neigh) | |
984 | { | |
985 | int i; | |
986 | ||
987 | for(i = 0; i < route_slots; i++) { | |
988 | struct babel_route *r = routes[i]; | |
989 | while(r) { | |
990 | if(r->neigh == neigh) { | |
991 | if(r->refmetric != INFINITY) { | |
992 | unsigned short oldmetric = route_metric(r); | |
993 | retract_route(r); | |
994 | if(oldmetric != INFINITY) | |
995 | route_changed(r, r->src, oldmetric); | |
996 | } | |
997 | } | |
998 | r = r->next; | |
999 | } | |
ca10883e DS |
1000 | } |
1001 | } | |
1002 | ||
1003 | void | |
1004 | send_triggered_update(struct babel_route *route, struct source *oldsrc, | |
1005 | unsigned oldmetric) | |
1006 | { | |
1007 | unsigned newmetric, diff; | |
1008 | /* 1 means send speedily, 2 means resend */ | |
1009 | int urgent; | |
1010 | ||
1011 | if(!route->installed) | |
1012 | return; | |
1013 | ||
1014 | newmetric = route_metric(route); | |
1015 | diff = | |
1016 | newmetric >= oldmetric ? newmetric - oldmetric : oldmetric - newmetric; | |
1017 | ||
1018 | if(route->src != oldsrc || (oldmetric < INFINITY && newmetric >= INFINITY)) | |
1019 | /* Switching sources can cause transient routing loops. | |
1020 | Retractions can cause blackholes. */ | |
1021 | urgent = 2; | |
1022 | else if(newmetric > oldmetric && oldmetric < 6 * 256 && diff >= 512) | |
1023 | /* Route getting significantly worse */ | |
1024 | urgent = 1; | |
1025 | else if(unsatisfied_request(route->src->prefix, route->src->plen, | |
1026 | route->seqno, route->src->id)) | |
1027 | /* Make sure that requests are satisfied speedily */ | |
1028 | urgent = 1; | |
1029 | else if(oldmetric >= INFINITY && newmetric < INFINITY) | |
1030 | /* New route */ | |
1031 | urgent = 0; | |
1032 | else if(newmetric < oldmetric && diff < 1024) | |
1033 | /* Route getting better. This may be a transient fluctuation, so | |
1034 | don't advertise it to avoid making routes unfeasible later on. */ | |
1035 | return; | |
1036 | else if(diff < 384) | |
1037 | /* Don't fret about trivialities */ | |
1038 | return; | |
1039 | else | |
1040 | urgent = 0; | |
1041 | ||
1042 | if(urgent >= 2) | |
1043 | send_update_resend(NULL, route->src->prefix, route->src->plen); | |
1044 | else | |
1045 | send_update(NULL, urgent, route->src->prefix, route->src->plen); | |
1046 | ||
1047 | if(oldmetric < INFINITY) { | |
1048 | if(newmetric >= oldmetric + 512) { | |
1049 | send_request_resend(NULL, route->src->prefix, route->src->plen, | |
1050 | route->src->metric >= INFINITY ? | |
1051 | route->src->seqno : | |
1052 | seqno_plus(route->src->seqno, 1), | |
1053 | route->src->id); | |
1054 | } else if(newmetric >= oldmetric + 288) { | |
1055 | send_request(NULL, route->src->prefix, route->src->plen); | |
1056 | } | |
1057 | } | |
1058 | } | |
1059 | ||
1060 | /* A route has just changed. Decide whether to switch to a different route or | |
1061 | send an update. */ | |
1062 | void | |
1063 | route_changed(struct babel_route *route, | |
1064 | struct source *oldsrc, unsigned short oldmetric) | |
1065 | { | |
1066 | if(route->installed) { | |
1067 | struct babel_route *better_route; | |
1068 | /* Do this unconditionally -- microoptimisation is not worth it. */ | |
1069 | better_route = | |
1070 | find_best_route(route->src->prefix, route->src->plen, 1, NULL); | |
1071 | if(better_route && route_metric(better_route) < route_metric(route)) | |
1072 | consider_route(better_route); | |
1073 | } | |
1074 | ||
1075 | if(route->installed) { | |
1076 | /* We didn't change routes after all. */ | |
1077 | send_triggered_update(route, oldsrc, oldmetric); | |
1078 | } else { | |
1079 | /* Reconsider routes even when their metric didn't decrease, | |
1080 | they may not have been feasible before. */ | |
1081 | consider_route(route); | |
1082 | } | |
1083 | } | |
1084 | ||
1085 | /* We just lost the installed route to a given destination. */ | |
1086 | void | |
1087 | route_lost(struct source *src, unsigned oldmetric) | |
1088 | { | |
1089 | struct babel_route *new_route; | |
1090 | new_route = find_best_route(src->prefix, src->plen, 1, NULL); | |
1091 | if(new_route) { | |
1092 | consider_route(new_route); | |
1093 | } else if(oldmetric < INFINITY) { | |
1094 | /* Avoid creating a blackhole. */ | |
1095 | send_update_resend(NULL, src->prefix, src->plen); | |
1096 | /* If the route was usable enough, try to get an alternate one. | |
1097 | If it was not, we could be dealing with oscillations around | |
1098 | the value of INFINITY. */ | |
1099 | if(oldmetric <= INFINITY / 2) | |
1100 | send_request_resend(NULL, src->prefix, src->plen, | |
1101 | src->metric >= INFINITY ? | |
1102 | src->seqno : seqno_plus(src->seqno, 1), | |
1103 | src->id); | |
1104 | } | |
1105 | } | |
1106 | ||
1107 | /* This is called periodically to flush old routes. It will also send | |
1108 | requests for routes that are about to expire. */ | |
1109 | void | |
1110 | expire_routes(void) | |
1111 | { | |
1112 | struct babel_route *r; | |
1113 | int i; | |
1114 | ||
1115 | debugf(BABEL_DEBUG_COMMON,"Expiring old routes."); | |
1116 | ||
1117 | i = 0; | |
1118 | while(i < route_slots) { | |
1119 | r = routes[i]; | |
1120 | while(r) { | |
1121 | /* Protect against clock being stepped. */ | |
1122 | if(r->time > babel_now.tv_sec || route_old(r)) { | |
1123 | flush_route(r); | |
1124 | goto again; | |
1125 | } | |
1126 | ||
1127 | update_route_metric(r); | |
1128 | ||
1129 | if(r->installed && r->refmetric < INFINITY) { | |
1130 | if(route_old(r)) | |
1131 | /* Route about to expire, send a request. */ | |
1132 | send_unicast_request(r->neigh, | |
1133 | r->src->prefix, r->src->plen); | |
1134 | } | |
1135 | r = r->next; | |
1136 | } | |
1137 | i++; | |
1138 | again: | |
1139 | ; | |
1140 | } | |
1141 | } |