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