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