]>
Commit | Line | Data |
---|---|---|
5734509c PJ |
1 | /* |
2 | * This file is free software: you may copy, redistribute and/or modify it | |
3 | * under the terms of the GNU General Public License as published by the | |
4 | * Free Software Foundation, either version 2 of the License, or (at your | |
5 | * option) any later version. | |
6 | * | |
7 | * This file is distributed in the hope that it will be useful, but | |
8 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
9 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
10 | * General Public License for more details. | |
11 | * | |
12 | * You should have received a copy of the GNU General Public License | |
13 | * along with this program. If not, see <http://www.gnu.org/licenses/>. | |
14 | * | |
15 | * This file incorporates work covered by the following copyright and | |
16 | * permission notice: | |
17 | * | |
18 | Copyright (c) 2007, 2008 by Juliusz Chroboczek | |
19 | Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek | |
20 | ||
21 | Permission is hereby granted, free of charge, to any person obtaining a copy | |
22 | of this software and associated documentation files (the "Software"), to deal | |
23 | in the Software without restriction, including without limitation the rights | |
24 | to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
25 | copies of the Software, and to permit persons to whom the Software is | |
26 | furnished to do so, subject to the following conditions: | |
27 | ||
28 | The above copyright notice and this permission notice shall be included in | |
29 | all copies or substantial portions of the Software. | |
30 | ||
31 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
32 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
33 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
34 | AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
35 | LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
36 | OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | |
37 | THE SOFTWARE. | |
38 | */ | |
39 | ||
40 | #include <stdlib.h> | |
41 | #include <string.h> | |
42 | #include <stdio.h> | |
43 | #include <errno.h> | |
44 | #include <assert.h> | |
45 | #include <sys/time.h> | |
46 | ||
47 | #include <zebra.h> | |
48 | #include "if.h" | |
49 | ||
50 | #include "babeld.h" | |
51 | #include "util.h" | |
52 | #include "kernel.h" | |
53 | #include "babel_interface.h" | |
54 | #include "source.h" | |
55 | #include "neighbour.h" | |
56 | #include "route.h" | |
57 | #include "xroute.h" | |
58 | #include "message.h" | |
59 | #include "resend.h" | |
60 | ||
61 | static void consider_route(struct route *route); | |
62 | ||
63 | struct route *routes = NULL; | |
64 | int numroutes = 0, maxroutes = 0; | |
65 | int kernel_metric = 0; | |
66 | int allow_duplicates = -1; | |
67 | ||
68 | struct route * | |
69 | find_route(const unsigned char *prefix, unsigned char plen, | |
70 | struct neighbour *neigh, const unsigned char *nexthop) | |
71 | { | |
72 | int i; | |
73 | for(i = 0; i < numroutes; i++) { | |
74 | if(routes[i].neigh == neigh && | |
75 | memcmp(routes[i].nexthop, nexthop, 16) == 0 && | |
76 | source_match(routes[i].src, prefix, plen)) | |
77 | return &routes[i]; | |
78 | } | |
79 | return NULL; | |
80 | } | |
81 | ||
82 | struct route * | |
83 | find_installed_route(const unsigned char *prefix, unsigned char plen) | |
84 | { | |
85 | int i; | |
86 | for(i = 0; i < numroutes; i++) { | |
87 | if(routes[i].installed && source_match(routes[i].src, prefix, plen)) | |
88 | return &routes[i]; | |
89 | } | |
90 | return NULL; | |
91 | } | |
92 | ||
93 | void | |
94 | flush_route(struct route *route) | |
95 | { | |
96 | int i; | |
97 | struct source *src; | |
98 | unsigned oldmetric; | |
99 | int lost = 0; | |
100 | ||
101 | i = route - routes; | |
102 | assert(i >= 0 && i < numroutes); | |
103 | ||
104 | oldmetric = route_metric(route); | |
105 | ||
106 | if(route->installed) { | |
107 | uninstall_route(route); | |
108 | lost = 1; | |
109 | } | |
110 | ||
111 | src = route->src; | |
112 | ||
113 | if(i != numroutes - 1) | |
114 | memcpy(routes + i, routes + numroutes - 1, sizeof(struct route)); | |
115 | numroutes--; | |
116 | VALGRIND_MAKE_MEM_UNDEFINED(routes + numroutes, sizeof(struct route)); | |
117 | ||
118 | if(numroutes == 0) { | |
119 | free(routes); | |
120 | routes = NULL; | |
121 | maxroutes = 0; | |
122 | } else if(maxroutes > 8 && numroutes < maxroutes / 4) { | |
123 | struct route *new_routes; | |
124 | int n = maxroutes / 2; | |
125 | new_routes = realloc(routes, n * sizeof(struct route)); | |
126 | if(new_routes != NULL) { | |
127 | routes = new_routes; | |
128 | maxroutes = n; | |
129 | } | |
130 | } | |
131 | ||
132 | if(lost) | |
133 | route_lost(src, oldmetric); | |
134 | } | |
135 | ||
136 | void | |
137 | flush_neighbour_routes(struct neighbour *neigh) | |
138 | { | |
139 | int i; | |
140 | ||
141 | i = 0; | |
142 | while(i < numroutes) { | |
143 | if(routes[i].neigh == neigh) { | |
144 | flush_route(&routes[i]); | |
145 | continue; | |
146 | } | |
147 | i++; | |
148 | } | |
149 | } | |
150 | ||
151 | void | |
152 | flush_interface_routes(struct interface *ifp, int v4only) | |
153 | { | |
154 | int i; | |
155 | ||
156 | i = 0; | |
157 | while(i < numroutes) { | |
158 | if(routes[i].neigh->ifp == ifp && | |
159 | (!v4only || v4mapped(routes[i].nexthop))) { | |
160 | flush_route(&routes[i]); | |
161 | continue; | |
162 | } | |
163 | i++; | |
164 | } | |
165 | } | |
166 | ||
167 | static int | |
168 | metric_to_kernel(int metric) | |
169 | { | |
170 | return metric < INFINITY ? kernel_metric : KERNEL_INFINITY; | |
171 | } | |
172 | ||
173 | void | |
174 | install_route(struct route *route) | |
175 | { | |
176 | int rc; | |
177 | ||
178 | if(route->installed) | |
179 | return; | |
180 | ||
181 | if(!route_feasible(route)) | |
182 | fprintf(stderr, "WARNING: installing unfeasible route " | |
183 | "(this shouldn't happen)."); | |
184 | ||
185 | rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen, | |
186 | route->nexthop, | |
187 | route->neigh->ifp->ifindex, | |
188 | metric_to_kernel(route_metric(route)), NULL, 0, 0); | |
189 | if(rc < 0) { | |
190 | int save = errno; | |
191 | zlog_err("kernel_route(ADD): %s", safe_strerror(errno)); | |
192 | if(save != EEXIST) | |
193 | return; | |
194 | } | |
195 | route->installed = 1; | |
196 | } | |
197 | ||
198 | void | |
199 | uninstall_route(struct route *route) | |
200 | { | |
201 | int rc; | |
202 | ||
203 | if(!route->installed) | |
204 | return; | |
205 | ||
206 | rc = kernel_route(ROUTE_FLUSH, route->src->prefix, route->src->plen, | |
207 | route->nexthop, | |
208 | route->neigh->ifp->ifindex, | |
209 | metric_to_kernel(route_metric(route)), NULL, 0, 0); | |
210 | if(rc < 0) | |
211 | zlog_err("kernel_route(FLUSH): %s", safe_strerror(errno)); | |
212 | ||
213 | route->installed = 0; | |
214 | } | |
215 | ||
216 | /* This is equivalent to uninstall_route followed with install_route, | |
217 | but without the race condition. The destination of both routes | |
218 | must be the same. */ | |
219 | ||
220 | static void | |
221 | switch_routes(struct route *old, struct route *new) | |
222 | { | |
223 | int rc; | |
224 | ||
225 | if(!old) { | |
226 | install_route(new); | |
227 | return; | |
228 | } | |
229 | ||
230 | if(!old->installed) | |
231 | return; | |
232 | ||
233 | if(!route_feasible(new)) | |
234 | fprintf(stderr, "WARNING: switching to unfeasible route " | |
235 | "(this shouldn't happen)."); | |
236 | ||
237 | rc = kernel_route(ROUTE_MODIFY, old->src->prefix, old->src->plen, | |
238 | old->nexthop, old->neigh->ifp->ifindex, | |
239 | metric_to_kernel(route_metric(old)), | |
240 | new->nexthop, new->neigh->ifp->ifindex, | |
241 | metric_to_kernel(route_metric(new))); | |
242 | if(rc < 0) { | |
243 | zlog_err("kernel_route(MODIFY): %s", safe_strerror(errno)); | |
244 | return; | |
245 | } | |
246 | ||
247 | old->installed = 0; | |
248 | new->installed = 1; | |
249 | } | |
250 | ||
251 | static void | |
252 | change_route_metric(struct route *route, unsigned newmetric) | |
253 | { | |
254 | int old, new; | |
255 | ||
256 | if(route_metric(route) == newmetric) | |
257 | return; | |
258 | ||
259 | old = metric_to_kernel(route_metric(route)); | |
260 | new = metric_to_kernel(newmetric); | |
261 | ||
262 | if(route->installed && old != new) { | |
263 | int rc; | |
264 | rc = kernel_route(ROUTE_MODIFY, route->src->prefix, route->src->plen, | |
265 | route->nexthop, route->neigh->ifp->ifindex, | |
266 | old, | |
267 | route->nexthop, route->neigh->ifp->ifindex, | |
268 | new); | |
269 | if(rc < 0) { | |
270 | zlog_err("kernel_route(MODIFY metric): %s", safe_strerror(errno)); | |
271 | return; | |
272 | } | |
273 | } | |
274 | ||
275 | route->metric = newmetric; | |
276 | } | |
277 | ||
278 | static void | |
279 | retract_route(struct route *route) | |
280 | { | |
281 | route->refmetric = INFINITY; | |
282 | change_route_metric(route, INFINITY); | |
283 | } | |
284 | ||
285 | int | |
286 | route_feasible(struct route *route) | |
287 | { | |
288 | return update_feasible(route->src, route->seqno, route->refmetric); | |
289 | } | |
290 | ||
291 | int | |
292 | route_old(struct route *route) | |
293 | { | |
294 | return route->time < babel_now.tv_sec - route->hold_time * 7 / 8; | |
295 | } | |
296 | ||
297 | int | |
298 | route_expired(struct route *route) | |
299 | { | |
300 | return route->time < babel_now.tv_sec - route->hold_time; | |
301 | } | |
302 | ||
303 | int | |
304 | update_feasible(struct source *src, | |
305 | unsigned short seqno, unsigned short refmetric) | |
306 | { | |
307 | if(src == NULL) | |
308 | return 1; | |
309 | ||
310 | if(src->time < babel_now.tv_sec - SOURCE_GC_TIME) | |
311 | /* Never mind what is probably stale data */ | |
312 | return 1; | |
313 | ||
314 | if(refmetric >= INFINITY) | |
315 | /* Retractions are always feasible */ | |
316 | return 1; | |
317 | ||
318 | return (seqno_compare(seqno, src->seqno) > 0 || | |
319 | (src->seqno == seqno && refmetric < src->metric)); | |
320 | } | |
321 | ||
322 | /* This returns the feasible route with the smallest metric. */ | |
323 | struct route * | |
324 | find_best_route(const unsigned char *prefix, unsigned char plen, int feasible, | |
325 | struct neighbour *exclude) | |
326 | { | |
327 | struct route *route = NULL; | |
328 | int i; | |
329 | ||
330 | for(i = 0; i < numroutes; i++) { | |
331 | if(!source_match(routes[i].src, prefix, plen)) | |
332 | continue; | |
333 | if(route_expired(&routes[i])) | |
334 | continue; | |
335 | if(feasible && !route_feasible(&routes[i])) | |
336 | continue; | |
337 | if(exclude && routes[i].neigh == exclude) | |
338 | continue; | |
339 | if(route && route_metric(route) <= route_metric(&routes[i])) | |
340 | continue; | |
341 | route = &routes[i]; | |
342 | } | |
343 | return route; | |
344 | } | |
345 | ||
346 | void | |
347 | update_route_metric(struct route *route) | |
348 | { | |
349 | int oldmetric = route_metric(route); | |
350 | ||
351 | if(route_expired(route)) { | |
352 | if(route->refmetric < INFINITY) { | |
353 | route->seqno = seqno_plus(route->src->seqno, 1); | |
354 | retract_route(route); | |
355 | if(oldmetric < INFINITY) | |
356 | route_changed(route, route->src, oldmetric); | |
357 | } | |
358 | } else { | |
359 | struct neighbour *neigh = route->neigh; | |
360 | int add_metric = input_filter(route->src->id, | |
361 | route->src->prefix, route->src->plen, | |
362 | neigh->address, | |
363 | neigh->ifp->ifindex); | |
364 | int newmetric = MIN(route->refmetric + | |
365 | add_metric + | |
366 | neighbour_cost(route->neigh), | |
367 | INFINITY); | |
368 | ||
369 | if(newmetric != oldmetric) { | |
370 | change_route_metric(route, newmetric); | |
371 | route_changed(route, route->src, oldmetric); | |
372 | } | |
373 | } | |
374 | } | |
375 | ||
376 | /* Called whenever a neighbour's cost changes, to update the metric of | |
377 | all routes through that neighbour. */ | |
378 | void | |
379 | update_neighbour_metric(struct neighbour *neigh, int changed) | |
380 | { | |
381 | if(changed) { | |
382 | int i; | |
383 | ||
384 | i = 0; | |
385 | while(i < numroutes) { | |
386 | if(routes[i].neigh == neigh) | |
387 | update_route_metric(&routes[i]); | |
388 | i++; | |
389 | } | |
390 | } | |
391 | } | |
392 | ||
393 | void | |
394 | update_interface_metric(struct interface *ifp) | |
395 | { | |
396 | int i; | |
397 | ||
398 | i = 0; | |
399 | while(i < numroutes) { | |
400 | if(routes[i].neigh->ifp == ifp) | |
401 | update_route_metric(&routes[i]); | |
402 | i++; | |
403 | } | |
404 | } | |
405 | ||
406 | /* This is called whenever we receive an update. */ | |
407 | struct route * | |
408 | update_route(const unsigned char *router_id, | |
409 | const unsigned char *prefix, unsigned char plen, | |
410 | unsigned short seqno, unsigned short refmetric, | |
411 | unsigned short interval, | |
412 | struct neighbour *neigh, const unsigned char *nexthop) | |
413 | { | |
414 | struct route *route; | |
415 | struct source *src; | |
416 | int metric, feasible; | |
417 | int add_metric; | |
418 | int hold_time = MAX((4 * interval) / 100 + interval / 50, 15); | |
419 | ||
420 | if(memcmp(router_id, myid, 8) == 0) | |
421 | return NULL; /* I have announced the route */ | |
422 | ||
423 | if(martian_prefix(prefix, plen)) { | |
424 | fprintf(stderr, "Rejecting martian route to %s through %s.\n", | |
425 | format_prefix(prefix, plen), format_address(router_id)); | |
426 | return NULL; | |
427 | } | |
428 | ||
429 | add_metric = input_filter(router_id, prefix, plen, | |
430 | neigh->address, neigh->ifp->ifindex); | |
431 | if(add_metric >= INFINITY) | |
432 | return NULL; | |
433 | ||
434 | src = find_source(router_id, prefix, plen, 1, seqno); | |
435 | if(src == NULL) | |
436 | return NULL; | |
437 | ||
438 | feasible = update_feasible(src, seqno, refmetric); | |
439 | route = find_route(prefix, plen, neigh, nexthop); | |
440 | metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY); | |
441 | ||
442 | if(route) { | |
443 | struct source *oldsrc; | |
444 | unsigned short oldmetric; | |
445 | int lost = 0; | |
446 | ||
447 | oldsrc = route->src; | |
448 | oldmetric = route_metric(route); | |
449 | ||
450 | /* If a successor switches sources, we must accept his update even | |
451 | if it makes a route unfeasible in order to break any routing loops | |
452 | in a timely manner. If the source remains the same, we ignore | |
453 | the update. */ | |
454 | if(!feasible && route->installed) { | |
455 | debugf(BABEL_DEBUG_COMMON,"Unfeasible update for installed route to %s " | |
456 | "(%s %d %d -> %s %d %d).", | |
457 | format_prefix(src->prefix, src->plen), | |
458 | format_address(route->src->id), | |
459 | route->seqno, route->refmetric, | |
460 | format_address(src->id), seqno, refmetric); | |
461 | if(src != route->src) { | |
462 | uninstall_route(route); | |
463 | lost = 1; | |
464 | } | |
465 | } | |
466 | ||
467 | route->src = src; | |
468 | if(feasible && refmetric < INFINITY) | |
469 | route->time = babel_now.tv_sec; | |
470 | route->seqno = seqno; | |
471 | route->refmetric = refmetric; | |
472 | change_route_metric(route, metric); | |
473 | route->hold_time = hold_time; | |
474 | ||
475 | route_changed(route, oldsrc, oldmetric); | |
476 | if(lost) | |
477 | route_lost(oldsrc, oldmetric); | |
478 | ||
479 | if(!feasible) | |
480 | send_unfeasible_request(neigh, route->installed && route_old(route), | |
481 | seqno, metric, src); | |
482 | } else { | |
483 | if(refmetric >= INFINITY) | |
484 | /* Somebody's retracting a route we never saw. */ | |
485 | return NULL; | |
486 | if(!feasible) { | |
487 | send_unfeasible_request(neigh, 0, seqno, metric, src); | |
488 | return NULL; | |
489 | } | |
490 | if(numroutes >= maxroutes) { | |
491 | struct route *new_routes; | |
492 | int n = maxroutes < 1 ? 8 : 2 * maxroutes; | |
493 | new_routes = routes == NULL ? | |
494 | malloc(n * sizeof(struct route)) : | |
495 | realloc(routes, n * sizeof(struct route)); | |
496 | if(new_routes == NULL) | |
497 | return NULL; | |
498 | maxroutes = n; | |
499 | routes = new_routes; | |
500 | } | |
501 | route = &routes[numroutes]; | |
502 | route->src = src; | |
503 | route->refmetric = refmetric; | |
504 | route->seqno = seqno; | |
505 | route->metric = metric; | |
506 | route->neigh = neigh; | |
507 | memcpy(route->nexthop, nexthop, 16); | |
508 | route->time = babel_now.tv_sec; | |
509 | route->hold_time = hold_time; | |
510 | route->installed = 0; | |
511 | numroutes++; | |
512 | consider_route(route); | |
513 | } | |
514 | return route; | |
515 | } | |
516 | ||
517 | /* We just received an unfeasible update. If it's any good, send | |
518 | a request for a new seqno. */ | |
519 | void | |
520 | send_unfeasible_request(struct neighbour *neigh, int force, | |
521 | unsigned short seqno, unsigned short metric, | |
522 | struct source *src) | |
523 | { | |
524 | struct route *route = find_installed_route(src->prefix, src->plen); | |
525 | ||
526 | if(seqno_minus(src->seqno, seqno) > 100) { | |
527 | /* Probably a source that lost its seqno. Let it time-out. */ | |
528 | return; | |
529 | } | |
530 | ||
531 | if(force || !route || route_metric(route) >= metric + 512) { | |
532 | send_unicast_multihop_request(neigh, src->prefix, src->plen, | |
533 | src->metric >= INFINITY ? | |
534 | src->seqno : | |
535 | seqno_plus(src->seqno, 1), | |
536 | src->id, 127); | |
537 | } | |
538 | } | |
539 | ||
540 | /* This takes a feasible route and decides whether to install it. */ | |
541 | static void | |
542 | consider_route(struct route *route) | |
543 | { | |
544 | struct route *installed; | |
545 | struct xroute *xroute; | |
546 | ||
547 | if(route->installed) | |
548 | return; | |
549 | ||
550 | if(!route_feasible(route)) | |
551 | return; | |
552 | ||
553 | xroute = find_xroute(route->src->prefix, route->src->plen); | |
554 | if(xroute && (allow_duplicates < 0 || xroute->metric >= allow_duplicates)) | |
555 | return; | |
556 | ||
557 | installed = find_installed_route(route->src->prefix, route->src->plen); | |
558 | ||
559 | if(installed == NULL) | |
560 | goto install; | |
561 | ||
562 | if(route_metric(route) >= INFINITY) | |
563 | return; | |
564 | ||
565 | if(route_metric(installed) >= INFINITY) | |
566 | goto install; | |
567 | ||
568 | if(route_metric(installed) >= route_metric(route) + 192) | |
569 | goto install; | |
570 | ||
571 | /* Avoid switching sources */ | |
572 | if(installed->src != route->src) | |
573 | return; | |
574 | ||
575 | if(route_metric(installed) >= route_metric(route) + 64) | |
576 | goto install; | |
577 | ||
578 | return; | |
579 | ||
580 | install: | |
581 | switch_routes(installed, route); | |
582 | if(installed && route->installed) | |
583 | send_triggered_update(route, installed->src, route_metric(installed)); | |
584 | else | |
585 | send_update(NULL, 1, route->src->prefix, route->src->plen); | |
586 | return; | |
587 | } | |
588 | ||
589 | void | |
590 | retract_neighbour_routes(struct neighbour *neigh) | |
591 | { | |
592 | int i; | |
593 | ||
594 | i = 0; | |
595 | while(i < numroutes) { | |
596 | if(routes[i].neigh == neigh) { | |
597 | if(routes[i].refmetric != INFINITY) { | |
598 | unsigned short oldmetric = route_metric(&routes[i]); | |
599 | retract_route(&routes[i]); | |
600 | if(oldmetric != INFINITY) | |
601 | route_changed(&routes[i], routes[i].src, oldmetric); | |
602 | } | |
603 | } | |
604 | i++; | |
605 | } | |
606 | } | |
607 | ||
608 | void | |
609 | send_triggered_update(struct route *route, struct source *oldsrc, | |
610 | unsigned oldmetric) | |
611 | { | |
612 | unsigned newmetric, diff; | |
613 | /* 1 means send speedily, 2 means resend */ | |
614 | int urgent; | |
615 | ||
616 | if(!route->installed) | |
617 | return; | |
618 | ||
619 | newmetric = route_metric(route); | |
620 | diff = | |
621 | newmetric >= oldmetric ? newmetric - oldmetric : oldmetric - newmetric; | |
622 | ||
623 | if(route->src != oldsrc || (oldmetric < INFINITY && newmetric >= INFINITY)) | |
624 | /* Switching sources can cause transient routing loops. | |
625 | Retractions can cause blackholes. */ | |
626 | urgent = 2; | |
627 | else if(newmetric > oldmetric && oldmetric < 6 * 256 && diff >= 512) | |
628 | /* Route getting significantly worse */ | |
629 | urgent = 1; | |
630 | else if(unsatisfied_request(route->src->prefix, route->src->plen, | |
631 | route->seqno, route->src->id)) | |
632 | /* Make sure that requests are satisfied speedily */ | |
633 | urgent = 1; | |
634 | else if(oldmetric >= INFINITY && newmetric < INFINITY) | |
635 | /* New route */ | |
636 | urgent = 0; | |
637 | else if(newmetric < oldmetric && diff < 1024) | |
638 | /* Route getting better. This may be a transient fluctuation, so | |
639 | don't advertise it to avoid making routes unfeasible later on. */ | |
640 | return; | |
641 | else if(diff < 384) | |
642 | /* Don't fret about trivialities */ | |
643 | return; | |
644 | else | |
645 | urgent = 0; | |
646 | ||
647 | if(urgent >= 2) | |
648 | send_update_resend(NULL, route->src->prefix, route->src->plen); | |
649 | else | |
650 | send_update(NULL, urgent, route->src->prefix, route->src->plen); | |
651 | ||
652 | if(oldmetric < INFINITY) { | |
653 | if(newmetric >= oldmetric + 512) { | |
654 | send_request_resend(NULL, route->src->prefix, route->src->plen, | |
655 | route->src->metric >= INFINITY ? | |
656 | route->src->seqno : | |
657 | seqno_plus(route->src->seqno, 1), | |
658 | route->src->id); | |
659 | } else if(newmetric >= oldmetric + 288) { | |
660 | send_request(NULL, route->src->prefix, route->src->plen); | |
661 | } | |
662 | } | |
663 | } | |
664 | ||
665 | /* A route has just changed. Decide whether to switch to a different route or | |
666 | send an update. */ | |
667 | void | |
668 | route_changed(struct route *route, | |
669 | struct source *oldsrc, unsigned short oldmetric) | |
670 | { | |
671 | if(route->installed) { | |
672 | if(route_metric(route) > oldmetric) { | |
673 | struct route *better_route; | |
674 | better_route = | |
675 | find_best_route(route->src->prefix, route->src->plen, 1, NULL); | |
676 | if(better_route && | |
677 | route_metric(better_route) <= route_metric(route) - 96) | |
678 | consider_route(better_route); | |
679 | } | |
680 | ||
681 | if(route->installed) | |
682 | /* We didn't change routes after all. */ | |
683 | send_triggered_update(route, oldsrc, oldmetric); | |
684 | } else { | |
685 | /* Reconsider routes even when their metric didn't decrease, | |
686 | they may not have been feasible before. */ | |
687 | consider_route(route); | |
688 | } | |
689 | } | |
690 | ||
691 | /* We just lost the installed route to a given destination. */ | |
692 | void | |
693 | route_lost(struct source *src, unsigned oldmetric) | |
694 | { | |
695 | struct route *new_route; | |
696 | new_route = find_best_route(src->prefix, src->plen, 1, NULL); | |
697 | if(new_route) { | |
698 | consider_route(new_route); | |
699 | } else if(oldmetric < INFINITY) { | |
700 | /* Complain loudly. */ | |
701 | send_update_resend(NULL, src->prefix, src->plen); | |
702 | send_request_resend(NULL, src->prefix, src->plen, | |
703 | src->metric >= INFINITY ? | |
704 | src->seqno : seqno_plus(src->seqno, 1), | |
705 | src->id); | |
706 | } | |
707 | } | |
708 | ||
709 | void | |
710 | expire_routes(void) | |
711 | { | |
712 | int i; | |
713 | ||
714 | debugf(BABEL_DEBUG_COMMON,"Expiring old routes."); | |
715 | ||
716 | i = 0; | |
717 | while(i < numroutes) { | |
718 | struct route *route = &routes[i]; | |
719 | ||
720 | if(route->time > babel_now.tv_sec || /* clock stepped */ | |
721 | route_old(route)) { | |
722 | flush_route(route); | |
723 | continue; | |
724 | } | |
725 | ||
726 | update_route_metric(route); | |
727 | ||
728 | if(route->installed && route->refmetric < INFINITY) { | |
729 | if(route_old(route)) | |
730 | send_unicast_request(route->neigh, | |
731 | route->src->prefix, route->src->plen); | |
732 | } | |
733 | i++; | |
734 | } | |
735 | } | |
736 | ||
737 | void | |
738 | babel_uninstall_all_routes(void) | |
739 | { | |
740 | while(numroutes > 0) { | |
741 | uninstall_route(&routes[0]); | |
742 | /* We need to flush the route so network_up won't reinstall it */ | |
743 | flush_route(&routes[0]); | |
744 | } | |
745 | } | |
746 | ||
747 | struct route * | |
748 | babel_route_get_by_source(struct source *src) | |
749 | { | |
750 | int i; | |
751 | for(i = 0; i < numroutes; i++) { | |
752 | if(routes[i].src == src) | |
753 | return &routes[i]; | |
754 | } | |
755 | return NULL; | |
756 | } |