1: /*
2: * OSPF routing table.
3: * Copyright (C) 1999, 2000 Toshiaki Takada
4: *
5: * This file is part of GNU Zebra.
6: *
7: * GNU Zebra is free software; you can redistribute it and/or modify it
8: * under the terms of the GNU General Public License as published by the
9: * Free Software Foundation; either version 2, or (at your option) any
10: * later version.
11: *
12: * GNU Zebra is distributed in the hope that it will be useful, but
13: * WITHOUT ANY WARRANTY; without even the implied warranty of
14: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15: * General Public License for more details.
16: *
17: * You should have received a copy of the GNU General Public License
18: * along with GNU Zebra; see the file COPYING. If not, write to the Free
19: * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
20: * 02111-1307, USA.
21: */
22:
23: #include <zebra.h>
24:
25: #include "prefix.h"
26: #include "table.h"
27: #include "memory.h"
28: #include "linklist.h"
29: #include "log.h"
30: #include "if.h"
31: #include "command.h"
32: #include "sockunion.h"
33:
34: #include "ospfd/ospfd.h"
35: #include "ospfd/ospf_interface.h"
36: #include "ospfd/ospf_asbr.h"
37: #include "ospfd/ospf_lsa.h"
38: #include "ospfd/ospf_route.h"
39: #include "ospfd/ospf_spf.h"
40: #include "ospfd/ospf_zebra.h"
41: #include "ospfd/ospf_dump.h"
42:
43: struct ospf_route *
44: ospf_route_new ()
45: {
46: struct ospf_route *new;
47:
48: new = XCALLOC (MTYPE_OSPF_ROUTE, sizeof (struct ospf_route));
49:
50: new->ctime = quagga_time (NULL);
51: new->mtime = new->ctime;
52: new->paths = list_new ();
53: new->paths->del = (void (*) (void *))ospf_path_free;
54:
55: return new;
56: }
57:
58: void
59: ospf_route_free (struct ospf_route *or)
60: {
61: if (or->paths)
62: list_delete (or->paths);
63:
64: XFREE (MTYPE_OSPF_ROUTE, or);
65: }
66:
67: struct ospf_path *
68: ospf_path_new ()
69: {
70: struct ospf_path *new;
71:
72: new = XCALLOC (MTYPE_OSPF_PATH, sizeof (struct ospf_path));
73:
74: return new;
75: }
76:
77: static struct ospf_path *
78: ospf_path_dup (struct ospf_path *path)
79: {
80: struct ospf_path *new;
81:
82: new = ospf_path_new ();
83: memcpy (new, path, sizeof (struct ospf_path));
84:
85: return new;
86: }
87:
88: void
89: ospf_path_free (struct ospf_path *op)
90: {
91: XFREE (MTYPE_OSPF_PATH, op);
92: }
93:
94: void
95: ospf_route_delete (struct route_table *rt)
96: {
97: struct route_node *rn;
98: struct ospf_route *or;
99:
100: for (rn = route_top (rt); rn; rn = route_next (rn))
101: if ((or = rn->info) != NULL)
102: {
103: if (or->type == OSPF_DESTINATION_NETWORK)
104: ospf_zebra_delete ((struct prefix_ipv4 *) &rn->p,
105: or);
106: else if (or->type == OSPF_DESTINATION_DISCARD)
107: ospf_zebra_delete_discard ((struct prefix_ipv4 *) &rn->p);
108: }
109: }
110:
111: void
112: ospf_route_table_free (struct route_table *rt)
113: {
114: struct route_node *rn;
115: struct ospf_route *or;
116:
117: for (rn = route_top (rt); rn; rn = route_next (rn))
118: if ((or = rn->info) != NULL)
119: {
120: ospf_route_free (or);
121:
122: rn->info = NULL;
123: route_unlock_node (rn);
124: }
125:
126: route_table_finish (rt);
127: }
128:
129: /* If a prefix exists in the new routing table, then return 1,
130: otherwise return 0. Since the ZEBRA-RIB does an implicit
131: withdraw, it is not necessary to send a delete, an add later
132: will act like an implicit delete. */
133: static int
134: ospf_route_exist_new_table (struct route_table *rt, struct prefix_ipv4 *prefix)
135: {
136: struct route_node *rn;
137:
138: assert (rt);
139: assert (prefix);
140:
141: rn = route_node_lookup (rt, (struct prefix *) prefix);
142: if (!rn) {
143: return 0;
144: }
145: route_unlock_node (rn);
146:
147: if (!rn->info) {
148: return 0;
149: }
150:
151: return 1;
152: }
153:
154: /* If a prefix and a nexthop match any route in the routing table,
155: then return 1, otherwise return 0. */
156: int
157: ospf_route_match_same (struct route_table *rt, struct prefix_ipv4 *prefix,
158: struct ospf_route *newor)
159: {
160: struct route_node *rn;
161: struct ospf_route *or;
162: struct ospf_path *op;
163: struct ospf_path *newop;
164: struct listnode *n1;
165: struct listnode *n2;
166:
167: if (! rt || ! prefix)
168: return 0;
169:
170: rn = route_node_lookup (rt, (struct prefix *) prefix);
171: if (! rn || ! rn->info)
172: return 0;
173:
174: route_unlock_node (rn);
175:
176: or = rn->info;
177: if (or->type == newor->type && or->cost == newor->cost)
178: {
179: if (or->type == OSPF_DESTINATION_NETWORK)
180: {
181: if (or->paths->count != newor->paths->count)
182: return 0;
183:
184: /* Check each path. */
185: for (n1 = listhead (or->paths), n2 = listhead (newor->paths);
186: n1 && n2; n1 = listnextnode (n1), n2 = listnextnode (n2))
187: {
188: op = listgetdata (n1);
189: newop = listgetdata (n2);
190:
191: if (! IPV4_ADDR_SAME (&op->nexthop, &newop->nexthop))
192: return 0;
193: if (op->ifindex != newop->ifindex)
194: return 0;
195: }
196: return 1;
197: }
198: else if (prefix_same (&rn->p, (struct prefix *) prefix))
199: return 1;
200: }
201: return 0;
202: }
203:
204: /* delete routes generated from AS-External routes if there is a inter/intra
205: * area route
206: */
207: static void
208: ospf_route_delete_same_ext(struct route_table *external_routes,
209: struct route_table *routes)
210: {
211: struct route_node *rn,
212: *ext_rn;
213:
214: if ( (external_routes == NULL) || (routes == NULL) )
215: return;
216:
217: /* Remove deleted routes */
218: for ( rn = route_top (routes); rn; rn = route_next (rn) )
219: {
220: if (rn && rn->info)
221: {
222: struct prefix_ipv4 *p = (struct prefix_ipv4 *)(&rn->p);
223: if ( (ext_rn = route_node_lookup (external_routes, (struct prefix *)p)) )
224: {
225: if (ext_rn->info)
226: {
227: ospf_zebra_delete (p, ext_rn->info);
228: ospf_route_free( ext_rn->info);
229: ext_rn->info = NULL;
230: }
231: route_unlock_node (ext_rn);
232: }
233: }
234: }
235: }
236:
237: /* rt: Old, cmprt: New */
238: static void
239: ospf_route_delete_uniq (struct route_table *rt, struct route_table *cmprt)
240: {
241: struct route_node *rn;
242: struct ospf_route *or;
243:
244: for (rn = route_top (rt); rn; rn = route_next (rn))
245: if ((or = rn->info) != NULL)
246: if (or->path_type == OSPF_PATH_INTRA_AREA ||
247: or->path_type == OSPF_PATH_INTER_AREA)
248: {
249: if (or->type == OSPF_DESTINATION_NETWORK)
250: {
251: if (! ospf_route_exist_new_table (cmprt,
252: (struct prefix_ipv4 *) &rn->p))
253: ospf_zebra_delete ((struct prefix_ipv4 *) &rn->p, or);
254: }
255: else if (or->type == OSPF_DESTINATION_DISCARD)
256: if (! ospf_route_exist_new_table (cmprt,
257: (struct prefix_ipv4 *) &rn->p))
258: ospf_zebra_delete_discard ((struct prefix_ipv4 *) &rn->p);
259: }
260: }
261:
262: /* Install routes to table. */
263: void
264: ospf_route_install (struct ospf *ospf, struct route_table *rt)
265: {
266: struct route_node *rn;
267: struct ospf_route *or;
268:
269: /* rt contains new routing table, new_table contains an old one.
270: updating pointers */
271: if (ospf->old_table)
272: ospf_route_table_free (ospf->old_table);
273:
274: ospf->old_table = ospf->new_table;
275: ospf->new_table = rt;
276:
277: /* Delete old routes. */
278: if (ospf->old_table)
279: ospf_route_delete_uniq (ospf->old_table, rt);
280: if (ospf->old_external_route)
281: ospf_route_delete_same_ext (ospf->old_external_route, rt);
282:
283: /* Install new routes. */
284: for (rn = route_top (rt); rn; rn = route_next (rn))
285: if ((or = rn->info) != NULL)
286: {
287: if (or->type == OSPF_DESTINATION_NETWORK)
288: {
289: if (! ospf_route_match_same (ospf->old_table,
290: (struct prefix_ipv4 *)&rn->p, or))
291: ospf_zebra_add ((struct prefix_ipv4 *) &rn->p, or);
292: }
293: else if (or->type == OSPF_DESTINATION_DISCARD)
294: if (! ospf_route_match_same (ospf->old_table,
295: (struct prefix_ipv4 *) &rn->p, or))
296: ospf_zebra_add_discard ((struct prefix_ipv4 *) &rn->p);
297: }
298: }
299:
300: /* RFC2328 16.1. (4). For "router". */
301: void
302: ospf_intra_add_router (struct route_table *rt, struct vertex *v,
303: struct ospf_area *area)
304: {
305: struct route_node *rn;
306: struct ospf_route *or;
307: struct prefix_ipv4 p;
308: struct router_lsa *lsa;
309:
310: if (IS_DEBUG_OSPF_EVENT)
311: zlog_debug ("ospf_intra_add_router: Start");
312:
313: lsa = (struct router_lsa *) v->lsa;
314:
315: if (IS_DEBUG_OSPF_EVENT)
316: zlog_debug ("ospf_intra_add_router: LS ID: %s",
317: inet_ntoa (lsa->header.id));
318:
319: if (!OSPF_IS_AREA_BACKBONE(area))
320: ospf_vl_up_check (area, lsa->header.id, v);
321:
322: if (!CHECK_FLAG (lsa->flags, ROUTER_LSA_SHORTCUT))
323: area->shortcut_capability = 0;
324:
325: /* If the newly added vertex is an area border router or AS boundary
326: router, a routing table entry is added whose destination type is
327: "router". */
328: if (! IS_ROUTER_LSA_BORDER (lsa) && ! IS_ROUTER_LSA_EXTERNAL (lsa))
329: {
330: if (IS_DEBUG_OSPF_EVENT)
331: zlog_debug ("ospf_intra_add_router: "
332: "this router is neither ASBR nor ABR, skipping it");
333: return;
334: }
335:
336: /* Update ABR and ASBR count in this area. */
337: if (IS_ROUTER_LSA_BORDER (lsa))
338: area->abr_count++;
339: if (IS_ROUTER_LSA_EXTERNAL (lsa))
340: area->asbr_count++;
341:
342: /* The Options field found in the associated router-LSA is copied
343: into the routing table entry's Optional capabilities field. Call
344: the newly added vertex Router X. */
345: or = ospf_route_new ();
346:
347: or->id = v->id;
348: or->u.std.area_id = area->area_id;
349: or->u.std.external_routing = area->external_routing;
350: or->path_type = OSPF_PATH_INTRA_AREA;
351: or->cost = v->distance;
352: or->type = OSPF_DESTINATION_ROUTER;
353: or->u.std.origin = (struct lsa_header *) lsa;
354: or->u.std.options = lsa->header.options;
355: or->u.std.flags = lsa->flags;
356:
357: /* If Router X is the endpoint of one of the calculating router's
358: virtual links, and the virtual link uses Area A as Transit area:
359: the virtual link is declared up, the IP address of the virtual
360: interface is set to the IP address of the outgoing interface
361: calculated above for Router X, and the virtual neighbor's IP
362: address is set to Router X's interface address (contained in
363: Router X's router-LSA) that points back to the root of the
364: shortest- path tree; equivalently, this is the interface that
365: points back to Router X's parent vertex on the shortest-path tree
366: (similar to the calculation in Section 16.1.1). */
367:
368: p.family = AF_INET;
369: p.prefix = v->id;
370: p.prefixlen = IPV4_MAX_BITLEN;
371:
372: if (IS_DEBUG_OSPF_EVENT)
373: zlog_debug ("ospf_intra_add_router: talking about %s/%d",
374: inet_ntoa (p.prefix), p.prefixlen);
375:
376: rn = route_node_get (rt, (struct prefix *) &p);
377:
378: /* Note that we keep all routes to ABRs and ASBRs, not only the best */
379: if (rn->info == NULL)
380: rn->info = list_new ();
381: else
382: route_unlock_node (rn);
383:
384: ospf_route_copy_nexthops_from_vertex (or, v);
385:
386: listnode_add (rn->info, or);
387:
388: if (IS_DEBUG_OSPF_EVENT)
389: zlog_debug ("ospf_intra_add_router: Stop");
390: }
391:
392: /* RFC2328 16.1. (4). For transit network. */
393: void
394: ospf_intra_add_transit (struct route_table *rt, struct vertex *v,
395: struct ospf_area *area)
396: {
397: struct route_node *rn;
398: struct ospf_route *or;
399: struct prefix_ipv4 p;
400: struct network_lsa *lsa;
401:
402: lsa = (struct network_lsa*) v->lsa;
403:
404: /* If the newly added vertex is a transit network, the routing table
405: entry for the network is located. The entry's Destination ID is
406: the IP network number, which can be obtained by masking the
407: Vertex ID (Link State ID) with its associated subnet mask (found
408: in the body of the associated network-LSA). */
409: p.family = AF_INET;
410: p.prefix = v->id;
411: p.prefixlen = ip_masklen (lsa->mask);
412: apply_mask_ipv4 (&p);
413:
414: rn = route_node_get (rt, (struct prefix *) &p);
415:
416: /* If the routing table entry already exists (i.e., there is already
417: an intra-area route to the destination installed in the routing
418: table), multiple vertices have mapped to the same IP network.
419: For example, this can occur when a new Designated Router is being
420: established. In this case, the current routing table entry
421: should be overwritten if and only if the newly found path is just
422: as short and the current routing table entry's Link State Origin
423: has a smaller Link State ID than the newly added vertex' LSA. */
424: if (rn->info)
425: {
426: struct ospf_route *cur_or;
427:
428: route_unlock_node (rn);
429: cur_or = rn->info;
430:
431: if (v->distance > cur_or->cost ||
432: IPV4_ADDR_CMP (&cur_or->u.std.origin->id, &lsa->header.id) > 0)
433: return;
434:
435: ospf_route_free (rn->info);
436: }
437:
438: or = ospf_route_new ();
439:
440: or->id = v->id;
441: or->u.std.area_id = area->area_id;
442: or->u.std.external_routing = area->external_routing;
443: or->path_type = OSPF_PATH_INTRA_AREA;
444: or->cost = v->distance;
445: or->type = OSPF_DESTINATION_NETWORK;
446: or->u.std.origin = (struct lsa_header *) lsa;
447:
448: ospf_route_copy_nexthops_from_vertex (or, v);
449:
450: rn->info = or;
451: }
452:
453: /* RFC2328 16.1. second stage. */
454: void
455: ospf_intra_add_stub (struct route_table *rt, struct router_lsa_link *link,
456: struct vertex *v, struct ospf_area *area,
457: int parent_is_root, int lsa_pos)
458: {
459: u_int32_t cost;
460: struct route_node *rn;
461: struct ospf_route *or;
462: struct prefix_ipv4 p;
463: struct router_lsa *lsa;
464: struct ospf_interface *oi;
465: struct ospf_path *path;
466:
467: if (IS_DEBUG_OSPF_EVENT)
468: zlog_debug ("ospf_intra_add_stub(): Start");
469:
470: lsa = (struct router_lsa *) v->lsa;
471:
472: p.family = AF_INET;
473: p.prefix = link->link_id;
474: p.prefixlen = ip_masklen (link->link_data);
475: apply_mask_ipv4 (&p);
476:
477: if (IS_DEBUG_OSPF_EVENT)
478: zlog_debug ("ospf_intra_add_stub(): processing route to %s/%d",
479: inet_ntoa (p.prefix), p.prefixlen);
480:
481: /* (1) Calculate the distance D of stub network from the root. D is
482: equal to the distance from the root to the router vertex
483: (calculated in stage 1), plus the stub network link's advertised
484: cost. */
485: cost = v->distance + ntohs (link->m[0].metric);
486:
487: if (IS_DEBUG_OSPF_EVENT)
488: zlog_debug ("ospf_intra_add_stub(): calculated cost is %d + %d = %d",
489: v->distance, ntohs(link->m[0].metric), cost);
490:
491: /* PtP links with /32 masks adds host routes to remote, directly
492: * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
493: * Such routes can just be ignored for the sake of tidyness.
494: */
495: if (parent_is_root && link->link_data.s_addr == 0xffffffff &&
496: ospf_if_lookup_by_local_addr (area->ospf, NULL, link->link_id))
497: {
498: if (IS_DEBUG_OSPF_EVENT)
499: zlog_debug ("%s: ignoring host route %s/32 to self.",
500: __func__, inet_ntoa (link->link_id));
501: return;
502: }
503:
504: rn = route_node_get (rt, (struct prefix *) &p);
505:
506: /* Lookup current routing table. */
507: if (rn->info)
508: {
509: struct ospf_route *cur_or;
510:
511: route_unlock_node (rn);
512:
513: cur_or = rn->info;
514:
515: if (IS_DEBUG_OSPF_EVENT)
516: zlog_debug ("ospf_intra_add_stub(): "
517: "another route to the same prefix found with cost %u",
518: cur_or->cost);
519:
520: /* Compare this distance to the current best cost to the stub
521: network. This is done by looking up the stub network's
522: current routing table entry. If the calculated distance D is
523: larger, go on to examine the next stub network link in the
524: LSA. */
525: if (cost > cur_or->cost)
526: {
527: if (IS_DEBUG_OSPF_EVENT)
528: zlog_debug ("ospf_intra_add_stub(): old route is better, exit");
529: return;
530: }
531:
532: /* (2) If this step is reached, the stub network's routing table
533: entry must be updated. Calculate the set of next hops that
534: would result from using the stub network link. This
535: calculation is shown in Section 16.1.1; input to this
536: calculation is the destination (the stub network) and the
537: parent vertex (the router vertex). If the distance D is the
538: same as the current routing table cost, simply add this set
539: of next hops to the routing table entry's list of next hops.
540: In this case, the routing table already has a Link State
541: Origin. If this Link State Origin is a router-LSA whose Link
542: State ID is smaller than V's Router ID, reset the Link State
543: Origin to V's router-LSA. */
544:
545: if (cost == cur_or->cost)
546: {
547: if (IS_DEBUG_OSPF_EVENT)
548: zlog_debug ("ospf_intra_add_stub(): routes are equal, merge");
549:
550: ospf_route_copy_nexthops_from_vertex (cur_or, v);
551:
552: if (IPV4_ADDR_CMP (&cur_or->u.std.origin->id, &lsa->header.id) < 0)
553: cur_or->u.std.origin = (struct lsa_header *) lsa;
554: return;
555: }
556:
557: /* Otherwise D is smaller than the routing table cost.
558: Overwrite the current routing table entry by setting the
559: routing table entry's cost to D, and by setting the entry's
560: list of next hops to the newly calculated set. Set the
561: routing table entry's Link State Origin to V's router-LSA.
562: Then go on to examine the next stub network link. */
563:
564: if (cost < cur_or->cost)
565: {
566: if (IS_DEBUG_OSPF_EVENT)
567: zlog_debug ("ospf_intra_add_stub(): new route is better, set it");
568:
569: cur_or->cost = cost;
570:
571: list_delete_all_node (cur_or->paths);
572:
573: ospf_route_copy_nexthops_from_vertex (cur_or, v);
574:
575: cur_or->u.std.origin = (struct lsa_header *) lsa;
576: return;
577: }
578: }
579:
580: if (IS_DEBUG_OSPF_EVENT)
581: zlog_debug ("ospf_intra_add_stub(): installing new route");
582:
583: or = ospf_route_new ();
584:
585: or->id = v->id;
586: or->u.std.area_id = area->area_id;
587: or->u.std.external_routing = area->external_routing;
588: or->path_type = OSPF_PATH_INTRA_AREA;
589: or->cost = cost;
590: or->type = OSPF_DESTINATION_NETWORK;
591: or->u.std.origin = (struct lsa_header *) lsa;
592:
593: /* Nexthop is depend on connection type. */
594: if (v != area->spf)
595: {
596: if (IS_DEBUG_OSPF_EVENT)
597: zlog_debug ("ospf_intra_add_stub(): this network is on remote router");
598: ospf_route_copy_nexthops_from_vertex (or, v);
599: }
600: else
601: {
602: if (IS_DEBUG_OSPF_EVENT)
603: zlog_debug ("ospf_intra_add_stub(): this network is on this router");
604:
605: if ((oi = ospf_if_lookup_by_lsa_pos (area, lsa_pos)))
606: {
607: if (IS_DEBUG_OSPF_EVENT)
608: zlog_debug ("ospf_intra_add_stub(): the interface is %s",
609: IF_NAME (oi));
610:
611: path = ospf_path_new ();
612: path->nexthop.s_addr = 0;
613: path->ifindex = oi->ifp->ifindex;
614: listnode_add (or->paths, path);
615: }
616: else
617: {
618: if (IS_DEBUG_OSPF_EVENT)
619: zlog_debug ("ospf_intra_add_stub(): where's the interface ?");
620: }
621: }
622:
623: rn->info = or;
624:
625: if (IS_DEBUG_OSPF_EVENT)
626: zlog_debug("ospf_intra_add_stub(): Stop");
627: }
628:
629: const char *ospf_path_type_str[] =
630: {
631: "unknown-type",
632: "intra-area",
633: "inter-area",
634: "type1-external",
635: "type2-external"
636: };
637:
638: void
639: ospf_route_table_dump (struct route_table *rt)
640: {
641: struct route_node *rn;
642: struct ospf_route *or;
643: char buf1[BUFSIZ];
644: char buf2[BUFSIZ];
645: struct listnode *pnode;
646: struct ospf_path *path;
647:
648: #if 0
649: zlog_debug ("Type Dest Area Path Type Cost Next Adv.");
650: zlog_debug (" Hop(s) Router(s)");
651: #endif /* 0 */
652:
653: zlog_debug ("========== OSPF routing table ==========");
654: for (rn = route_top (rt); rn; rn = route_next (rn))
655: if ((or = rn->info) != NULL)
656: {
657: if (or->type == OSPF_DESTINATION_NETWORK)
658: {
659: zlog_debug ("N %s/%d\t%s\t%s\t%d",
660: inet_ntop (AF_INET, &rn->p.u.prefix4, buf1, BUFSIZ),
661: rn->p.prefixlen,
662: inet_ntop (AF_INET, &or->u.std.area_id, buf2,
663: BUFSIZ),
664: ospf_path_type_str[or->path_type],
665: or->cost);
666: for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path))
667: zlog_debug (" -> %s", inet_ntoa (path->nexthop));
668: }
669: else
670: zlog_debug ("R %s\t%s\t%s\t%d",
671: inet_ntop (AF_INET, &rn->p.u.prefix4, buf1, BUFSIZ),
672: inet_ntop (AF_INET, &or->u.std.area_id, buf2,
673: BUFSIZ),
674: ospf_path_type_str[or->path_type],
675: or->cost);
676: }
677: zlog_debug ("========================================");
678: }
679:
680: /* This is 16.4.1 implementation.
681: o Intra-area paths using non-backbone areas are always the most preferred.
682: o The other paths, intra-area backbone paths and inter-area paths,
683: are of equal preference. */
684: static int
685: ospf_asbr_route_cmp (struct ospf *ospf, struct ospf_route *r1,
686: struct ospf_route *r2)
687: {
688: u_char r1_type, r2_type;
689:
690: r1_type = r1->path_type;
691: r2_type = r2->path_type;
692:
693: /* r1/r2 itself is backbone, and it's Inter-area path. */
694: if (OSPF_IS_AREA_ID_BACKBONE (r1->u.std.area_id))
695: r1_type = OSPF_PATH_INTER_AREA;
696: if (OSPF_IS_AREA_ID_BACKBONE (r2->u.std.area_id))
697: r2_type = OSPF_PATH_INTER_AREA;
698:
699: return (r1_type - r2_type);
700: }
701:
702: /* Compare two routes.
703: ret < 0 -- r1 is better.
704: ret == 0 -- r1 and r2 are the same.
705: ret > 0 -- r2 is better. */
706: int
707: ospf_route_cmp (struct ospf *ospf, struct ospf_route *r1,
708: struct ospf_route *r2)
709: {
710: int ret = 0;
711:
712: /* Path types of r1 and r2 are not the same. */
713: if ((ret = (r1->path_type - r2->path_type)))
714: return ret;
715:
716: if (IS_DEBUG_OSPF_EVENT)
717: zlog_debug ("Route[Compare]: Path types are the same.");
718: /* Path types are the same, compare any cost. */
719: switch (r1->path_type)
720: {
721: case OSPF_PATH_INTRA_AREA:
722: case OSPF_PATH_INTER_AREA:
723: break;
724: case OSPF_PATH_TYPE1_EXTERNAL:
725: if (!CHECK_FLAG (ospf->config, OSPF_RFC1583_COMPATIBLE))
726: {
727: ret = ospf_asbr_route_cmp (ospf, r1->u.ext.asbr, r2->u.ext.asbr);
728: if (ret != 0)
729: return ret;
730: }
731: break;
732: case OSPF_PATH_TYPE2_EXTERNAL:
733: if ((ret = (r1->u.ext.type2_cost - r2->u.ext.type2_cost)))
734: return ret;
735:
736: if (!CHECK_FLAG (ospf->config, OSPF_RFC1583_COMPATIBLE))
737: {
738: ret = ospf_asbr_route_cmp (ospf, r1->u.ext.asbr, r2->u.ext.asbr);
739: if (ret != 0)
740: return ret;
741: }
742: break;
743: }
744:
745: /* Anyway, compare the costs. */
746: return (r1->cost - r2->cost);
747: }
748:
749: static int
750: ospf_path_exist (struct list *plist, struct in_addr nexthop,
751: struct ospf_interface *oi)
752: {
753: struct listnode *node, *nnode;
754: struct ospf_path *path;
755:
756: for (ALL_LIST_ELEMENTS (plist, node, nnode, path))
757: if (IPV4_ADDR_SAME (&path->nexthop, &nexthop) &&
758: path->ifindex == oi->ifp->ifindex)
759: return 1;
760:
761: return 0;
762: }
763:
764: void
765: ospf_route_copy_nexthops_from_vertex (struct ospf_route *to,
766: struct vertex *v)
767: {
768: struct listnode *node;
769: struct ospf_path *path;
770: struct vertex_nexthop *nexthop;
771: struct vertex_parent *vp;
772:
773: assert (to->paths);
774:
775: for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
776: {
777: nexthop = vp->nexthop;
778:
779: if (nexthop->oi != NULL)
780: {
781: if (! ospf_path_exist (to->paths, nexthop->router, nexthop->oi))
782: {
783: path = ospf_path_new ();
784: path->nexthop = nexthop->router;
785: path->ifindex = nexthop->oi->ifp->ifindex;
786: listnode_add (to->paths, path);
787: }
788: }
789: }
790: }
791:
792: struct ospf_path *
793: ospf_path_lookup (struct list *plist, struct ospf_path *path)
794: {
795: struct listnode *node;
796: struct ospf_path *op;
797:
798: for (ALL_LIST_ELEMENTS_RO (plist, node, op))
799: {
800: if (!IPV4_ADDR_SAME (&op->nexthop, &path->nexthop))
801: continue;
802: if (!IPV4_ADDR_SAME (&op->adv_router, &path->adv_router))
803: continue;
804: if (op->ifindex != path->ifindex)
805: continue;
806: return op;
807: }
808: return NULL;
809: }
810:
811: void
812: ospf_route_copy_nexthops (struct ospf_route *to, struct list *from)
813: {
814: struct listnode *node, *nnode;
815: struct ospf_path *path;
816:
817: assert (to->paths);
818:
819: for (ALL_LIST_ELEMENTS (from, node, nnode, path))
820: /* The same routes are just discarded. */
821: if (!ospf_path_lookup (to->paths, path))
822: listnode_add (to->paths, ospf_path_dup (path));
823: }
824:
825: void
826: ospf_route_subst_nexthops (struct ospf_route *to, struct list *from)
827: {
828:
829: list_delete_all_node (to->paths);
830: ospf_route_copy_nexthops (to, from);
831: }
832:
833: void
834: ospf_route_subst (struct route_node *rn, struct ospf_route *new_or,
835: struct ospf_route *over)
836: {
837: route_lock_node (rn);
838: ospf_route_free (rn->info);
839:
840: ospf_route_copy_nexthops (new_or, over->paths);
841: rn->info = new_or;
842: route_unlock_node (rn);
843: }
844:
845: void
846: ospf_route_add (struct route_table *rt, struct prefix_ipv4 *p,
847: struct ospf_route *new_or, struct ospf_route *over)
848: {
849: struct route_node *rn;
850:
851: rn = route_node_get (rt, (struct prefix *) p);
852:
853: ospf_route_copy_nexthops (new_or, over->paths);
854:
855: if (rn->info)
856: {
857: if (IS_DEBUG_OSPF_EVENT)
858: zlog_debug ("ospf_route_add(): something's wrong !");
859: route_unlock_node (rn);
860: return;
861: }
862:
863: rn->info = new_or;
864: }
865:
866: void
867: ospf_prune_unreachable_networks (struct route_table *rt)
868: {
869: struct route_node *rn, *next;
870: struct ospf_route *or;
871:
872: if (IS_DEBUG_OSPF_EVENT)
873: zlog_debug ("Pruning unreachable networks");
874:
875: for (rn = route_top (rt); rn; rn = next)
876: {
877: next = route_next (rn);
878: if (rn->info != NULL)
879: {
880: or = rn->info;
881: if (listcount (or->paths) == 0)
882: {
883: if (IS_DEBUG_OSPF_EVENT)
884: zlog_debug ("Pruning route to %s/%d",
885: inet_ntoa (rn->p.u.prefix4), rn->p.prefixlen);
886:
887: ospf_route_free (or);
888: rn->info = NULL;
889: route_unlock_node (rn);
890: }
891: }
892: }
893: }
894:
895: void
896: ospf_prune_unreachable_routers (struct route_table *rtrs)
897: {
898: struct route_node *rn, *next;
899: struct ospf_route *or;
900: struct listnode *node, *nnode;
901: struct list *paths;
902:
903: if (IS_DEBUG_OSPF_EVENT)
904: zlog_debug ("Pruning unreachable routers");
905:
906: for (rn = route_top (rtrs); rn; rn = next)
907: {
908: next = route_next (rn);
909: if ((paths = rn->info) == NULL)
910: continue;
911:
912: for (ALL_LIST_ELEMENTS (paths, node, nnode, or))
913: {
914: if (listcount (or->paths) == 0)
915: {
916: if (IS_DEBUG_OSPF_EVENT)
917: {
918: zlog_debug ("Pruning route to rtr %s",
919: inet_ntoa (rn->p.u.prefix4));
920: zlog_debug (" via area %s",
921: inet_ntoa (or->u.std.area_id));
922: }
923:
924: listnode_delete (paths, or);
925: ospf_route_free (or);
926: }
927: }
928:
929: if (listcount (paths) == 0)
930: {
931: if (IS_DEBUG_OSPF_EVENT)
932: zlog_debug ("Pruning router node %s", inet_ntoa (rn->p.u.prefix4));
933:
934: list_delete (paths);
935: rn->info = NULL;
936: route_unlock_node (rn);
937: }
938: }
939: }
940:
941: int
942: ospf_add_discard_route (struct route_table *rt, struct ospf_area *area,
943: struct prefix_ipv4 *p)
944: {
945: struct route_node *rn;
946: struct ospf_route *or, *new_or;
947:
948: rn = route_node_get (rt, (struct prefix *) p);
949:
950: if (rn == NULL)
951: {
952: if (IS_DEBUG_OSPF_EVENT)
953: zlog_debug ("ospf_add_discard_route(): router installation error");
954: return 0;
955: }
956:
957: if (rn->info) /* If the route to the same destination is found */
958: {
959: route_unlock_node (rn);
960:
961: or = rn->info;
962:
963: if (or->path_type == OSPF_PATH_INTRA_AREA)
964: {
965: if (IS_DEBUG_OSPF_EVENT)
966: zlog_debug ("ospf_add_discard_route(): "
967: "an intra-area route exists");
968: return 0;
969: }
970:
971: if (or->type == OSPF_DESTINATION_DISCARD)
972: {
973: if (IS_DEBUG_OSPF_EVENT)
974: zlog_debug ("ospf_add_discard_route(): "
975: "discard entry already installed");
976: return 0;
977: }
978:
979: ospf_route_free (rn->info);
980: }
981:
982: if (IS_DEBUG_OSPF_EVENT)
983: zlog_debug ("ospf_add_discard_route(): "
984: "adding %s/%d", inet_ntoa (p->prefix), p->prefixlen);
985:
986: new_or = ospf_route_new ();
987: new_or->type = OSPF_DESTINATION_DISCARD;
988: new_or->id.s_addr = 0;
989: new_or->cost = 0;
990: new_or->u.std.area_id = area->area_id;
991: new_or->u.std.external_routing = area->external_routing;
992: new_or->path_type = OSPF_PATH_INTER_AREA;
993: rn->info = new_or;
994:
995: ospf_zebra_add_discard (p);
996:
997: return 1;
998: }
999:
1000: void
1001: ospf_delete_discard_route (struct route_table *rt, struct prefix_ipv4 *p)
1002: {
1003: struct route_node *rn;
1004: struct ospf_route *or;
1005:
1006: if (IS_DEBUG_OSPF_EVENT)
1007: zlog_debug ("ospf_delete_discard_route(): "
1008: "deleting %s/%d", inet_ntoa (p->prefix), p->prefixlen);
1009:
1010: rn = route_node_lookup (rt, (struct prefix*)p);
1011:
1012: if (rn == NULL)
1013: {
1014: if (IS_DEBUG_OSPF_EVENT)
1015: zlog_debug("ospf_delete_discard_route(): no route found");
1016: return;
1017: }
1018:
1019: or = rn->info;
1020:
1021: if (or->path_type == OSPF_PATH_INTRA_AREA)
1022: {
1023: if (IS_DEBUG_OSPF_EVENT)
1024: zlog_debug ("ospf_delete_discard_route(): "
1025: "an intra-area route exists");
1026: return;
1027: }
1028:
1029: if (or->type != OSPF_DESTINATION_DISCARD)
1030: {
1031: if (IS_DEBUG_OSPF_EVENT)
1032: zlog_debug ("ospf_delete_discard_route(): "
1033: "not a discard entry");
1034: return;
1035: }
1036:
1037: /* free the route entry and the route node */
1038: ospf_route_free (rn->info);
1039:
1040: rn->info = NULL;
1041: route_unlock_node (rn);
1042: route_unlock_node (rn);
1043:
1044: /* remove the discard entry from the rib */
1045: ospf_zebra_delete_discard(p);
1046:
1047: return;
1048: }
1049:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ospf_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 / ospfd