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