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