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