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