]>
git.proxmox.com Git - mirror_frr.git/blob - ospfd/ospf_route.c
1 // SPDX-License-Identifier: GPL-2.0-or-later
4 * Copyright (C) 1999, 2000 Toshiaki Takada
16 #include "sockunion.h"
18 #include "ospfd/ospfd.h"
19 #include "ospfd/ospf_interface.h"
20 #include "ospfd/ospf_asbr.h"
21 #include "ospfd/ospf_lsa.h"
22 #include "ospfd/ospf_route.h"
23 #include "ospfd/ospf_spf.h"
24 #include "ospfd/ospf_zebra.h"
25 #include "ospfd/ospf_dump.h"
27 const char *ospf_path_type_name(int path_type
)
30 case OSPF_PATH_INTRA_AREA
:
32 case OSPF_PATH_INTER_AREA
:
34 case OSPF_PATH_TYPE1_EXTERNAL
:
36 case OSPF_PATH_TYPE2_EXTERNAL
:
43 struct ospf_route
*ospf_route_new(void)
45 struct ospf_route
*new;
47 new = XCALLOC(MTYPE_OSPF_ROUTE
, sizeof(struct ospf_route
));
49 new->paths
= list_new();
50 new->paths
->del
= (void (*)(void *))ospf_path_free
;
55 void ospf_route_free(struct ospf_route
*or)
58 list_delete(& or->paths
);
60 XFREE(MTYPE_OSPF_ROUTE
, or);
63 struct ospf_path
*ospf_path_new(void)
65 struct ospf_path
*new;
67 new = XCALLOC(MTYPE_OSPF_PATH
, sizeof(struct ospf_path
));
72 static struct ospf_path
*ospf_path_dup(struct ospf_path
*path
)
74 struct ospf_path
*new;
77 new = ospf_path_new();
78 memcpy(new, path
, sizeof(struct ospf_path
));
80 /* optional TI-LFA backup paths */
81 if (path
->srni
.backup_label_stack
) {
82 memsize
= sizeof(struct mpls_label_stack
)
83 + (sizeof(mpls_label_t
)
84 * path
->srni
.backup_label_stack
->num_labels
);
85 new->srni
.backup_label_stack
=
86 XCALLOC(MTYPE_OSPF_PATH
, memsize
);
87 memcpy(new->srni
.backup_label_stack
,
88 path
->srni
.backup_label_stack
, memsize
);
94 void ospf_path_free(struct ospf_path
*op
)
96 /* optional TI-LFA backup paths */
97 if (op
->srni
.backup_label_stack
)
98 XFREE(MTYPE_OSPF_PATH
, op
->srni
.backup_label_stack
);
100 XFREE(MTYPE_OSPF_PATH
, op
);
103 void ospf_route_delete(struct ospf
*ospf
, struct route_table
*rt
)
105 struct route_node
*rn
;
106 struct ospf_route
* or ;
108 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
109 if ((or = rn
->info
) != NULL
) {
110 if (or->type
== OSPF_DESTINATION_NETWORK
)
112 ospf
, (struct prefix_ipv4
*)&rn
->p
, or);
113 else if (or->type
== OSPF_DESTINATION_DISCARD
)
114 ospf_zebra_delete_discard(
115 ospf
, (struct prefix_ipv4
*)&rn
->p
);
119 void ospf_route_table_free(struct route_table
*rt
)
121 struct route_node
*rn
;
122 struct ospf_route
* or ;
124 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
125 if ((or = rn
->info
) != NULL
) {
129 route_unlock_node(rn
);
132 route_table_finish(rt
);
135 /* If a prefix exists in the new routing table, then return 1,
136 otherwise return 0. Since the ZEBRA-RIB does an implicit
137 withdraw, it is not necessary to send a delete, an add later
138 will act like an implicit delete. */
139 static int ospf_route_exist_new_table(struct route_table
*rt
,
140 struct prefix_ipv4
*prefix
)
142 struct route_node
*rn
;
147 rn
= route_node_lookup(rt
, (struct prefix
*)prefix
);
151 route_unlock_node(rn
);
160 static int ospf_route_backup_path_same(struct sr_nexthop_info
*srni1
,
161 struct sr_nexthop_info
*srni2
)
163 struct mpls_label_stack
*ls1
, *ls2
;
166 ls1
= srni1
->backup_label_stack
;
167 ls2
= srni2
->backup_label_stack
;
172 if ((ls1
&& !ls2
) || (!ls1
&& ls2
))
175 if (ls1
->num_labels
!= ls2
->num_labels
)
178 for (label_count
= 0; label_count
< ls1
->num_labels
; label_count
++) {
179 if (ls1
->label
[label_count
] != ls2
->label
[label_count
])
183 if (!IPV4_ADDR_SAME(&srni1
->backup_nexthop
, &srni2
->backup_nexthop
))
189 /* If a prefix and a nexthop match any route in the routing table,
190 then return 1, otherwise return 0. */
191 int ospf_route_match_same(struct route_table
*rt
, struct prefix_ipv4
*prefix
,
192 struct ospf_route
*newor
)
194 struct route_node
*rn
;
195 struct ospf_route
* or ;
196 struct ospf_path
*op
;
197 struct ospf_path
*newop
;
204 rn
= route_node_lookup(rt
, (struct prefix
*)prefix
);
205 if (!rn
|| !rn
->info
)
208 route_unlock_node(rn
);
211 if (or->type
== newor
->type
&& or->cost
== newor
->cost
) {
215 if (or->type
== OSPF_DESTINATION_NETWORK
) {
216 if (or->paths
->count
!= newor
->paths
->count
)
219 /* Check each path. */
220 for (n1
= listhead(or->paths
),
221 n2
= listhead(newor
->paths
);
222 n1
&& n2
; n1
= listnextnode_unchecked(n1
),
223 n2
= listnextnode_unchecked(n2
)) {
224 op
= listgetdata(n1
);
225 newop
= listgetdata(n2
);
227 if (!IPV4_ADDR_SAME(&op
->nexthop
,
230 if (op
->ifindex
!= newop
->ifindex
)
233 /* check TI-LFA backup paths */
234 if (!ospf_route_backup_path_same(&op
->srni
,
239 } else if (prefix_same(&rn
->p
, (struct prefix
*)prefix
))
245 /* delete routes generated from AS-External routes if there is a inter/intra
248 static void ospf_route_delete_same_ext(struct ospf
*ospf
,
249 struct route_table
*external_routes
,
250 struct route_table
*routes
)
252 struct route_node
*rn
, *ext_rn
;
254 if ((external_routes
== NULL
) || (routes
== NULL
))
257 /* Remove deleted routes */
258 for (rn
= route_top(routes
); rn
; rn
= route_next(rn
)) {
259 if (rn
&& rn
->info
) {
260 struct prefix_ipv4
*p
= (struct prefix_ipv4
*)(&rn
->p
);
261 if ((ext_rn
= route_node_lookup(external_routes
,
262 (struct prefix
*)p
))) {
264 ospf_zebra_delete(ospf
, p
,
266 ospf_route_free(ext_rn
->info
);
269 route_unlock_node(ext_rn
);
275 /* rt: Old, cmprt: New */
276 static void ospf_route_delete_uniq(struct ospf
*ospf
, struct route_table
*rt
,
277 struct route_table
*cmprt
)
279 struct route_node
*rn
;
280 struct ospf_route
* or ;
282 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
283 if ((or = rn
->info
) != NULL
)
284 if (or->path_type
== OSPF_PATH_INTRA_AREA
||
285 or->path_type
== OSPF_PATH_INTER_AREA
) {
286 if (or->type
== OSPF_DESTINATION_NETWORK
) {
287 if (!ospf_route_exist_new_table(
289 (struct prefix_ipv4
*)&rn
296 } else if (or->type
== OSPF_DESTINATION_DISCARD
)
297 if (!ospf_route_exist_new_table(
299 (struct prefix_ipv4
*)&rn
301 ospf_zebra_delete_discard(
308 /* Install routes to table. */
309 void ospf_route_install(struct ospf
*ospf
, struct route_table
*rt
)
311 struct route_node
*rn
;
312 struct ospf_route
* or ;
314 /* rt contains new routing table, new_table contains an old one.
317 ospf_route_table_free(ospf
->old_table
);
319 ospf
->old_table
= ospf
->new_table
;
320 ospf
->new_table
= rt
;
322 /* Delete old routes. */
324 ospf_route_delete_uniq(ospf
, ospf
->old_table
, rt
);
325 if (ospf
->old_external_route
)
326 ospf_route_delete_same_ext(ospf
, ospf
->old_external_route
, rt
);
328 /* Install new routes. */
329 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
330 if ((or = rn
->info
) != NULL
) {
331 if (or->type
== OSPF_DESTINATION_NETWORK
) {
332 if (!ospf_route_match_same(
334 (struct prefix_ipv4
*)&rn
->p
, or))
337 (struct prefix_ipv4
*)&rn
->p
,
339 } else if (or->type
== OSPF_DESTINATION_DISCARD
)
340 if (!ospf_route_match_same(
342 (struct prefix_ipv4
*)&rn
->p
, or))
343 ospf_zebra_add_discard(
345 (struct prefix_ipv4
*)&rn
->p
);
349 /* RFC2328 16.1. (4). For "router". */
350 void ospf_intra_add_router(struct route_table
*rt
, struct vertex
*v
,
351 struct ospf_area
*area
, bool add_all
)
353 struct route_node
*rn
;
354 struct ospf_route
* or ;
355 struct prefix_ipv4 p
;
356 struct router_lsa
*lsa
;
358 if (IS_DEBUG_OSPF_EVENT
)
359 zlog_debug("%s: Start", __func__
);
361 lsa
= (struct router_lsa
*)v
->lsa
;
363 if (IS_DEBUG_OSPF_EVENT
)
364 zlog_debug("%s: LS ID: %pI4", __func__
, &lsa
->header
.id
);
366 if (!OSPF_IS_AREA_BACKBONE(area
))
367 ospf_vl_up_check(area
, lsa
->header
.id
, v
);
369 if (!CHECK_FLAG(lsa
->flags
, ROUTER_LSA_SHORTCUT
))
370 area
->shortcut_capability
= 0;
372 /* If the newly added vertex is an area border router or AS boundary
373 router, a routing table entry is added whose destination type is
375 if (!add_all
&& !IS_ROUTER_LSA_BORDER(lsa
) &&
376 !IS_ROUTER_LSA_EXTERNAL(lsa
)) {
377 if (IS_DEBUG_OSPF_EVENT
)
379 "%s: this router is neither ASBR nor ABR, skipping it",
384 /* Update ABR and ASBR count in this area. */
385 if (IS_ROUTER_LSA_BORDER(lsa
))
387 if (IS_ROUTER_LSA_EXTERNAL(lsa
))
390 /* The Options field found in the associated router-LSA is copied
391 into the routing table entry's Optional capabilities field. Call
392 the newly added vertex Router X. */
393 or = ospf_route_new();
396 or->u
.std
.area_id
= area
->area_id
;
397 or->u
.std
.external_routing
= area
->external_routing
;
398 or->path_type
= OSPF_PATH_INTRA_AREA
;
399 or->cost
= v
->distance
;
400 or->type
= OSPF_DESTINATION_ROUTER
;
401 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
402 or->u
.std
.options
= lsa
->header
.options
;
403 or->u
.std
.flags
= lsa
->flags
;
405 /* If Router X is the endpoint of one of the calculating router's
406 virtual links, and the virtual link uses Area A as Transit area:
407 the virtual link is declared up, the IP address of the virtual
408 interface is set to the IP address of the outgoing interface
409 calculated above for Router X, and the virtual neighbor's IP
410 address is set to Router X's interface address (contained in
411 Router X's router-LSA) that points back to the root of the
412 shortest- path tree; equivalently, this is the interface that
413 points back to Router X's parent vertex on the shortest-path tree
414 (similar to the calculation in Section 16.1.1). */
418 p
.prefixlen
= IPV4_MAX_BITLEN
;
421 if (IS_DEBUG_OSPF_EVENT
)
422 zlog_debug("%s: talking about %pFX", __func__
, &p
);
424 rn
= route_node_get(rt
, (struct prefix
*)&p
);
426 /* Note that we keep all routes to ABRs and ASBRs, not only the best */
427 if (rn
->info
== NULL
)
428 rn
->info
= list_new();
430 route_unlock_node(rn
);
432 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
434 listnode_add(rn
->info
, or);
436 if (IS_DEBUG_OSPF_EVENT
)
437 zlog_debug("%s: Stop", __func__
);
440 /* RFC2328 16.1. (4). For transit network. */
441 void ospf_intra_add_transit(struct route_table
*rt
, struct vertex
*v
,
442 struct ospf_area
*area
)
444 struct route_node
*rn
;
445 struct ospf_route
* or ;
446 struct prefix_ipv4 p
;
447 struct network_lsa
*lsa
;
449 lsa
= (struct network_lsa
*)v
->lsa
;
451 /* If the newly added vertex is a transit network, the routing table
452 entry for the network is located. The entry's Destination ID is
453 the IP network number, which can be obtained by masking the
454 Vertex ID (Link State ID) with its associated subnet mask (found
455 in the body of the associated network-LSA). */
458 p
.prefixlen
= ip_masklen(lsa
->mask
);
461 rn
= route_node_get(rt
, (struct prefix
*)&p
);
463 /* If the routing table entry already exists (i.e., there is already
464 an intra-area route to the destination installed in the routing
465 table), multiple vertices have mapped to the same IP network.
466 For example, this can occur when a new Designated Router is being
467 established. In this case, the current routing table entry
468 should be overwritten if and only if the newly found path is just
469 as short and the current routing table entry's Link State Origin
470 has a smaller Link State ID than the newly added vertex' LSA. */
472 struct ospf_route
*cur_or
;
474 route_unlock_node(rn
);
477 if (v
->distance
> cur_or
->cost
478 || IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
, &lsa
->header
.id
)
482 ospf_route_free(rn
->info
);
485 or = ospf_route_new();
488 or->u
.std
.area_id
= area
->area_id
;
489 or->u
.std
.external_routing
= area
->external_routing
;
490 or->path_type
= OSPF_PATH_INTRA_AREA
;
491 or->cost
= v
->distance
;
492 or->type
= OSPF_DESTINATION_NETWORK
;
493 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
495 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
500 /* RFC2328 16.1. second stage. */
501 void ospf_intra_add_stub(struct route_table
*rt
, struct router_lsa_link
*link
,
502 struct vertex
*v
, struct ospf_area
*area
,
503 int parent_is_root
, int lsa_pos
)
506 struct route_node
*rn
;
507 struct ospf_route
* or ;
508 struct prefix_ipv4 p
;
509 struct router_lsa
*lsa
;
510 struct ospf_interface
*oi
= NULL
;
511 struct ospf_path
*path
;
513 if (IS_DEBUG_OSPF_EVENT
)
514 zlog_debug("%s: Start", __func__
);
516 lsa
= (struct router_lsa
*)v
->lsa
;
519 p
.prefix
= link
->link_id
;
520 p
.prefixlen
= ip_masklen(link
->link_data
);
523 if (IS_DEBUG_OSPF_EVENT
)
524 zlog_debug("%s: processing route to %pFX", __func__
, &p
);
526 /* (1) Calculate the distance D of stub network from the root. D is
527 equal to the distance from the root to the router vertex
528 (calculated in stage 1), plus the stub network link's advertised
530 cost
= v
->distance
+ ntohs(link
->m
[0].metric
);
532 if (IS_DEBUG_OSPF_EVENT
)
533 zlog_debug("%s: calculated cost is %d + %d = %d", __func__
,
534 v
->distance
, ntohs(link
->m
[0].metric
), cost
);
536 /* PtP links with /32 masks adds host routes to remote, directly
537 * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
538 * Such routes can just be ignored for the sake of tidyness.
540 if (parent_is_root
&& link
->link_data
.s_addr
== 0xffffffff
541 && ospf_if_lookup_by_local_addr(area
->ospf
, NULL
, link
->link_id
)) {
542 if (IS_DEBUG_OSPF_EVENT
)
543 zlog_debug("%s: ignoring host route %pI4/32 to self.",
544 __func__
, &link
->link_id
);
548 rn
= route_node_get(rt
, (struct prefix
*)&p
);
550 /* Lookup current routing table. */
552 struct ospf_route
*cur_or
;
554 route_unlock_node(rn
);
558 if (IS_DEBUG_OSPF_EVENT
)
560 "%s: another route to the same prefix found with cost %u",
561 __func__
, cur_or
->cost
);
563 /* Compare this distance to the current best cost to the stub
564 network. This is done by looking up the stub network's
565 current routing table entry. If the calculated distance D is
566 larger, go on to examine the next stub network link in the
568 if (cost
> cur_or
->cost
) {
569 if (IS_DEBUG_OSPF_EVENT
)
570 zlog_debug("%s: old route is better, exit",
575 /* (2) If this step is reached, the stub network's routing table
576 entry must be updated. Calculate the set of next hops that
577 would result from using the stub network link. This
578 calculation is shown in Section 16.1.1; input to this
579 calculation is the destination (the stub network) and the
580 parent vertex (the router vertex). If the distance D is the
581 same as the current routing table cost, simply add this set
582 of next hops to the routing table entry's list of next hops.
583 In this case, the routing table already has a Link State
584 Origin. If this Link State Origin is a router-LSA whose Link
585 State ID is smaller than V's Router ID, reset the Link State
586 Origin to V's router-LSA. */
588 if (cost
== cur_or
->cost
) {
589 if (IS_DEBUG_OSPF_EVENT
)
590 zlog_debug("%s: routes are equal, merge",
593 ospf_route_copy_nexthops_from_vertex(area
, cur_or
, v
);
595 if (IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
,
598 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
602 /* Otherwise D is smaller than the routing table cost.
603 Overwrite the current routing table entry by setting the
604 routing table entry's cost to D, and by setting the entry's
605 list of next hops to the newly calculated set. Set the
606 routing table entry's Link State Origin to V's router-LSA.
607 Then go on to examine the next stub network link. */
609 if (cost
< cur_or
->cost
) {
610 if (IS_DEBUG_OSPF_EVENT
)
611 zlog_debug("%s: new route is better, set it",
616 list_delete_all_node(cur_or
->paths
);
618 ospf_route_copy_nexthops_from_vertex(area
, cur_or
, v
);
620 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
625 if (IS_DEBUG_OSPF_EVENT
)
626 zlog_debug("%s: installing new route", __func__
);
628 or = ospf_route_new();
631 or->u
.std
.area_id
= area
->area_id
;
632 or->u
.std
.external_routing
= area
->external_routing
;
633 or->path_type
= OSPF_PATH_INTRA_AREA
;
635 or->type
= OSPF_DESTINATION_NETWORK
;
636 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
638 /* Nexthop is depend on connection type. */
639 if (v
!= area
->spf
) {
640 if (IS_DEBUG_OSPF_EVENT
)
641 zlog_debug("%s: this network is on remote router",
643 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
645 if (IS_DEBUG_OSPF_EVENT
)
646 zlog_debug("%s: this network is on this router",
650 * Only deal with interface data when we
653 if (!area
->spf_dry_run
)
654 oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
);
656 if (oi
|| area
->spf_dry_run
) {
657 if (IS_DEBUG_OSPF_EVENT
)
658 zlog_debug("%s: the lsa pos is %d", __func__
,
661 path
= ospf_path_new();
662 path
->nexthop
.s_addr
= INADDR_ANY
;
665 path
->ifindex
= oi
->ifp
->ifindex
;
666 if (CHECK_FLAG(oi
->connected
->flags
,
667 ZEBRA_IFA_UNNUMBERED
))
668 path
->unnumbered
= 1;
671 listnode_add(or->paths
, path
);
673 if (IS_DEBUG_OSPF_EVENT
)
674 zlog_debug("%s: where's the interface ?",
681 if (IS_DEBUG_OSPF_EVENT
)
682 zlog_debug("%s: Stop", __func__
);
685 static const char *const ospf_path_type_str
[] = {
686 "unknown-type", "intra-area", "inter-area", "type1-external",
690 void ospf_route_table_dump(struct route_table
*rt
)
692 struct route_node
*rn
;
693 struct ospf_route
* or ;
694 struct listnode
*pnode
;
695 struct ospf_path
*path
;
697 zlog_debug("========== OSPF routing table ==========");
698 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
699 if ((or = rn
->info
) != NULL
) {
700 if (or->type
== OSPF_DESTINATION_NETWORK
) {
701 zlog_debug("N %-18pFX %-15pI4 %s %d", &rn
->p
,
703 ospf_path_type_str
[or->path_type
],
705 for (ALL_LIST_ELEMENTS_RO(or->paths
, pnode
,
707 zlog_debug(" -> %pI4",
710 zlog_debug("R %-18pI4 %-15pI4 %s %d",
713 ospf_path_type_str
[or->path_type
],
716 zlog_debug("========================================");
719 void ospf_router_route_table_dump(struct route_table
*rt
)
721 struct route_node
*rn
;
722 struct ospf_route
*or;
723 struct listnode
*node
;
725 zlog_debug("========== OSPF routing table ==========");
726 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
)) {
727 for (ALL_LIST_ELEMENTS_RO((struct list
*)rn
->info
, node
, or)) {
728 assert(or->type
== OSPF_DESTINATION_ROUTER
);
729 zlog_debug("R %-18pI4 %-15pI4 %s %d", &rn
->p
.u
.prefix4
,
731 ospf_path_type_str
[or->path_type
], or->cost
);
734 zlog_debug("========================================");
737 /* This is 16.4.1 implementation.
738 o Intra-area paths using non-backbone areas are always the most preferred.
739 o The other paths, intra-area backbone paths and inter-area paths,
740 are of equal preference. */
741 static int ospf_asbr_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
742 struct ospf_route
*r2
)
744 uint8_t r1_type
, r2_type
;
746 r1_type
= r1
->path_type
;
747 r2_type
= r2
->path_type
;
749 /* r1/r2 itself is backbone, and it's Inter-area path. */
750 if (OSPF_IS_AREA_ID_BACKBONE(r1
->u
.std
.area_id
))
751 r1_type
= OSPF_PATH_INTER_AREA
;
752 if (OSPF_IS_AREA_ID_BACKBONE(r2
->u
.std
.area_id
))
753 r2_type
= OSPF_PATH_INTER_AREA
;
755 return (r1_type
- r2_type
);
758 /* Compare two routes.
759 ret < 0 -- r1 is better.
760 ret == 0 -- r1 and r2 are the same.
761 ret > 0 -- r2 is better. */
762 int ospf_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
763 struct ospf_route
*r2
)
767 /* Path types of r1 and r2 are not the same. */
768 if ((ret
= (r1
->path_type
- r2
->path_type
)))
771 if (IS_DEBUG_OSPF_EVENT
)
772 zlog_debug("Route[Compare]: Path types are the same.");
773 /* Path types are the same, compare any cost. */
774 switch (r1
->path_type
) {
775 case OSPF_PATH_INTRA_AREA
:
776 case OSPF_PATH_INTER_AREA
:
778 case OSPF_PATH_TYPE1_EXTERNAL
:
779 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
780 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
786 case OSPF_PATH_TYPE2_EXTERNAL
:
787 if ((ret
= (r1
->u
.ext
.type2_cost
- r2
->u
.ext
.type2_cost
)))
790 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
791 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
799 /* Anyway, compare the costs. */
800 return (r1
->cost
- r2
->cost
);
803 static int ospf_path_exist(struct list
*plist
, struct in_addr nexthop
,
804 struct ospf_interface
*oi
)
806 struct listnode
*node
, *nnode
;
807 struct ospf_path
*path
;
809 for (ALL_LIST_ELEMENTS(plist
, node
, nnode
, path
))
810 if (IPV4_ADDR_SAME(&path
->nexthop
, &nexthop
)
811 && path
->ifindex
== oi
->ifp
->ifindex
)
817 void ospf_route_copy_nexthops_from_vertex(struct ospf_area
*area
,
818 struct ospf_route
*to
,
821 struct listnode
*node
;
822 struct ospf_path
*path
;
823 struct vertex_nexthop
*nexthop
;
824 struct vertex_parent
*vp
;
825 struct ospf_interface
*oi
= NULL
;
829 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
830 nexthop
= vp
->nexthop
;
833 * Only deal with interface data when we
836 if (!area
->spf_dry_run
)
837 oi
= ospf_if_lookup_by_lsa_pos(area
, nexthop
->lsa_pos
);
839 if ((oi
&& !ospf_path_exist(to
->paths
, nexthop
->router
, oi
))
840 || area
->spf_dry_run
) {
841 path
= ospf_path_new();
842 path
->nexthop
= nexthop
->router
;
843 path
->adv_router
= v
->id
;
846 path
->ifindex
= oi
->ifp
->ifindex
;
847 if (CHECK_FLAG(oi
->connected
->flags
,
848 ZEBRA_IFA_UNNUMBERED
))
849 path
->unnumbered
= 1;
852 listnode_add(to
->paths
, path
);
857 struct ospf_path
*ospf_path_lookup(struct list
*plist
, struct ospf_path
*path
)
859 struct listnode
*node
;
860 struct ospf_path
*op
;
862 for (ALL_LIST_ELEMENTS_RO(plist
, node
, op
)) {
863 if (!IPV4_ADDR_SAME(&op
->nexthop
, &path
->nexthop
))
865 if (!IPV4_ADDR_SAME(&op
->adv_router
, &path
->adv_router
))
867 if (op
->ifindex
!= path
->ifindex
)
874 void ospf_route_copy_nexthops(struct ospf_route
*to
, struct list
*from
)
876 struct listnode
*node
, *nnode
;
877 struct ospf_path
*path
;
881 for (ALL_LIST_ELEMENTS(from
, node
, nnode
, path
))
882 /* The same routes are just discarded. */
883 if (!ospf_path_lookup(to
->paths
, path
))
884 listnode_add(to
->paths
, ospf_path_dup(path
));
887 void ospf_route_subst_nexthops(struct ospf_route
*to
, struct list
*from
)
890 list_delete_all_node(to
->paths
);
891 ospf_route_copy_nexthops(to
, from
);
894 void ospf_route_subst(struct route_node
*rn
, struct ospf_route
*new_or
,
895 struct ospf_route
*over
)
898 ospf_route_free(rn
->info
);
900 ospf_route_copy_nexthops(new_or
, over
->paths
);
902 route_unlock_node(rn
);
905 void ospf_route_add(struct route_table
*rt
, struct prefix_ipv4
*p
,
906 struct ospf_route
*new_or
, struct ospf_route
*over
)
908 struct route_node
*rn
;
910 rn
= route_node_get(rt
, (struct prefix
*)p
);
912 ospf_route_copy_nexthops(new_or
, over
->paths
);
915 if (IS_DEBUG_OSPF_EVENT
)
916 zlog_debug("%s: something's wrong !", __func__
);
917 route_unlock_node(rn
);
924 void ospf_prune_unreachable_networks(struct route_table
*rt
)
926 struct route_node
*rn
, *next
;
927 struct ospf_route
* or ;
929 if (IS_DEBUG_OSPF_EVENT
)
930 zlog_debug("Pruning unreachable networks");
932 for (rn
= route_top(rt
); rn
; rn
= next
) {
933 next
= route_next(rn
);
934 if (rn
->info
!= NULL
) {
936 if (listcount(or->paths
) == 0) {
937 if (IS_DEBUG_OSPF_EVENT
)
938 zlog_debug("Pruning route to %pFX",
943 route_unlock_node(rn
);
949 void ospf_prune_unreachable_routers(struct route_table
*rtrs
)
951 struct route_node
*rn
, *next
;
952 struct ospf_route
* or ;
953 struct listnode
*node
, *nnode
;
956 if (IS_DEBUG_OSPF_EVENT
)
957 zlog_debug("Pruning unreachable routers");
959 for (rn
= route_top(rtrs
); rn
; rn
= next
) {
960 next
= route_next(rn
);
961 if ((paths
= rn
->info
) == NULL
)
964 for (ALL_LIST_ELEMENTS(paths
, node
, nnode
, or)) {
965 if (listcount(or->paths
) == 0) {
966 if (IS_DEBUG_OSPF_EVENT
) {
967 zlog_debug("Pruning route to rtr %pI4",
974 listnode_delete(paths
, or);
979 if (listcount(paths
) == 0) {
980 if (IS_DEBUG_OSPF_EVENT
)
981 zlog_debug("Pruning router node %pI4",
986 route_unlock_node(rn
);
991 int ospf_add_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
992 struct ospf_area
*area
, struct prefix_ipv4
*p
)
994 struct route_node
*rn
;
995 struct ospf_route
* or, *new_or
;
997 rn
= route_node_get(rt
, (struct prefix
*)p
);
1000 if (IS_DEBUG_OSPF_EVENT
)
1001 zlog_debug("%s: router installation error", __func__
);
1005 if (rn
->info
) /* If the route to the same destination is found */
1007 route_unlock_node(rn
);
1011 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
1012 if (IS_DEBUG_OSPF_EVENT
)
1013 zlog_debug("%s: an intra-area route exists",
1018 if (or->type
== OSPF_DESTINATION_DISCARD
) {
1019 if (IS_DEBUG_OSPF_EVENT
)
1021 "%s: discard entry already installed",
1026 ospf_route_free(rn
->info
);
1029 if (IS_DEBUG_OSPF_EVENT
)
1030 zlog_debug("%s: adding %pFX", __func__
, p
);
1032 new_or
= ospf_route_new();
1033 new_or
->type
= OSPF_DESTINATION_DISCARD
;
1034 new_or
->id
.s_addr
= INADDR_ANY
;
1036 new_or
->u
.std
.area_id
= area
->area_id
;
1037 new_or
->u
.std
.external_routing
= area
->external_routing
;
1038 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
1041 ospf_zebra_add_discard(ospf
, p
);
1046 void ospf_delete_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
1047 struct prefix_ipv4
*p
)
1049 struct route_node
*rn
;
1050 struct ospf_route
* or ;
1052 if (IS_DEBUG_OSPF_EVENT
)
1053 zlog_debug("%s: deleting %pFX", __func__
, p
);
1055 rn
= route_node_lookup(rt
, (struct prefix
*)p
);
1058 if (IS_DEBUG_OSPF_EVENT
)
1059 zlog_debug("%s: no route found", __func__
);
1065 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
1066 if (IS_DEBUG_OSPF_EVENT
)
1067 zlog_debug("%s: an intra-area route exists", __func__
);
1071 if (or->type
!= OSPF_DESTINATION_DISCARD
) {
1072 if (IS_DEBUG_OSPF_EVENT
)
1073 zlog_debug("%s: not a discard entry", __func__
);
1077 /* free the route entry and the route node */
1078 ospf_route_free(rn
->info
);
1081 route_unlock_node(rn
);
1082 route_unlock_node(rn
);
1084 /* remove the discard entry from the rib */
1085 ospf_zebra_delete_discard(ospf
, p
);