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