]>
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_only
)
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
) {
360 zlog_debug("%s: Start", __func__
);
362 zlog_debug("%s: REACHRUN: Start", __func__
);
364 lsa
= (struct router_lsa
*)v
->lsa
;
366 if (IS_DEBUG_OSPF_EVENT
)
367 zlog_debug("%s: LS ID: %pI4", __func__
, &lsa
->header
.id
);
370 if (!OSPF_IS_AREA_BACKBONE(area
))
371 ospf_vl_up_check(area
, lsa
->header
.id
, v
);
373 if (!CHECK_FLAG(lsa
->flags
, ROUTER_LSA_SHORTCUT
))
374 area
->shortcut_capability
= 0;
376 /* If the newly added vertex is an area border router or AS
377 boundary router, a routing table entry is added whose
378 destination type is "router". */
379 if (!IS_ROUTER_LSA_BORDER(lsa
) &&
380 !IS_ROUTER_LSA_EXTERNAL(lsa
)) {
381 if (IS_DEBUG_OSPF_EVENT
)
383 "%s: this router is neither ASBR nor ABR, skipping it",
388 /* Update ABR and ASBR count in this area. */
389 if (IS_ROUTER_LSA_BORDER(lsa
))
391 if (IS_ROUTER_LSA_EXTERNAL(lsa
))
395 /* The Options field found in the associated router-LSA is copied
396 into the routing table entry's Optional capabilities field. Call
397 the newly added vertex Router X. */
398 or = ospf_route_new();
401 or->u
.std
.area_id
= area
->area_id
;
402 or->u
.std
.external_routing
= area
->external_routing
;
403 or->path_type
= OSPF_PATH_INTRA_AREA
;
404 or->cost
= v
->distance
;
405 or->type
= OSPF_DESTINATION_ROUTER
;
406 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
407 or->u
.std
.options
= lsa
->header
.options
;
408 or->u
.std
.flags
= lsa
->flags
;
410 /* If Router X is the endpoint of one of the calculating router's
411 virtual links, and the virtual link uses Area A as Transit area:
412 the virtual link is declared up, the IP address of the virtual
413 interface is set to the IP address of the outgoing interface
414 calculated above for Router X, and the virtual neighbor's IP
415 address is set to Router X's interface address (contained in
416 Router X's router-LSA) that points back to the root of the
417 shortest- path tree; equivalently, this is the interface that
418 points back to Router X's parent vertex on the shortest-path tree
419 (similar to the calculation in Section 16.1.1). */
423 p
.prefixlen
= IPV4_MAX_BITLEN
;
426 if (IS_DEBUG_OSPF_EVENT
)
427 zlog_debug("%s: talking about %pFX", __func__
, &p
);
429 rn
= route_node_get(rt
, (struct prefix
*)&p
);
431 /* Note that we keep all routes to ABRs and ASBRs, not only the best */
432 if (rn
->info
== NULL
)
433 rn
->info
= list_new();
435 route_unlock_node(rn
);
437 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
439 listnode_add(rn
->info
, or);
441 if (IS_DEBUG_OSPF_EVENT
) {
443 zlog_debug("%s: Stop", __func__
);
445 zlog_debug("%s: REACHRUN: Stop", __func__
);
449 /* RFC2328 16.1. (4). For transit network. */
450 void ospf_intra_add_transit(struct route_table
*rt
, struct vertex
*v
,
451 struct ospf_area
*area
)
453 struct route_node
*rn
;
454 struct ospf_route
* or ;
455 struct prefix_ipv4 p
;
456 struct network_lsa
*lsa
;
458 lsa
= (struct network_lsa
*)v
->lsa
;
460 /* If the newly added vertex is a transit network, the routing table
461 entry for the network is located. The entry's Destination ID is
462 the IP network number, which can be obtained by masking the
463 Vertex ID (Link State ID) with its associated subnet mask (found
464 in the body of the associated network-LSA). */
467 p
.prefixlen
= ip_masklen(lsa
->mask
);
470 rn
= route_node_get(rt
, (struct prefix
*)&p
);
472 /* If the routing table entry already exists (i.e., there is already
473 an intra-area route to the destination installed in the routing
474 table), multiple vertices have mapped to the same IP network.
475 For example, this can occur when a new Designated Router is being
476 established. In this case, the current routing table entry
477 should be overwritten if and only if the newly found path is just
478 as short and the current routing table entry's Link State Origin
479 has a smaller Link State ID than the newly added vertex' LSA. */
481 struct ospf_route
*cur_or
;
483 route_unlock_node(rn
);
486 if (v
->distance
> cur_or
->cost
487 || IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
, &lsa
->header
.id
)
491 ospf_route_free(rn
->info
);
494 or = ospf_route_new();
497 or->u
.std
.area_id
= area
->area_id
;
498 or->u
.std
.external_routing
= area
->external_routing
;
499 or->path_type
= OSPF_PATH_INTRA_AREA
;
500 or->cost
= v
->distance
;
501 or->type
= OSPF_DESTINATION_NETWORK
;
502 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
504 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
509 /* RFC2328 16.1. second stage. */
510 void ospf_intra_add_stub(struct route_table
*rt
, struct router_lsa_link
*link
,
511 struct vertex
*v
, struct ospf_area
*area
,
512 int parent_is_root
, int lsa_pos
)
515 struct route_node
*rn
;
516 struct ospf_route
* or ;
517 struct prefix_ipv4 p
;
518 struct router_lsa
*lsa
;
519 struct ospf_interface
*oi
= NULL
;
520 struct ospf_path
*path
;
522 if (IS_DEBUG_OSPF_EVENT
)
523 zlog_debug("%s: Start", __func__
);
525 lsa
= (struct router_lsa
*)v
->lsa
;
528 p
.prefix
= link
->link_id
;
529 p
.prefixlen
= ip_masklen(link
->link_data
);
532 if (IS_DEBUG_OSPF_EVENT
)
533 zlog_debug("%s: processing route to %pFX", __func__
, &p
);
535 /* (1) Calculate the distance D of stub network from the root. D is
536 equal to the distance from the root to the router vertex
537 (calculated in stage 1), plus the stub network link's advertised
539 cost
= v
->distance
+ ntohs(link
->m
[0].metric
);
541 if (IS_DEBUG_OSPF_EVENT
)
542 zlog_debug("%s: calculated cost is %d + %d = %d", __func__
,
543 v
->distance
, ntohs(link
->m
[0].metric
), cost
);
545 /* PtP links with /32 masks adds host routes to remote, directly
546 * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
547 * Such routes can just be ignored for the sake of tidyness.
549 if (parent_is_root
&& link
->link_data
.s_addr
== 0xffffffff
550 && ospf_if_lookup_by_local_addr(area
->ospf
, NULL
, link
->link_id
)) {
551 if (IS_DEBUG_OSPF_EVENT
)
552 zlog_debug("%s: ignoring host route %pI4/32 to self.",
553 __func__
, &link
->link_id
);
557 rn
= route_node_get(rt
, (struct prefix
*)&p
);
559 /* Lookup current routing table. */
561 struct ospf_route
*cur_or
;
563 route_unlock_node(rn
);
567 if (IS_DEBUG_OSPF_EVENT
)
569 "%s: another route to the same prefix found with cost %u",
570 __func__
, cur_or
->cost
);
572 /* Compare this distance to the current best cost to the stub
573 network. This is done by looking up the stub network's
574 current routing table entry. If the calculated distance D is
575 larger, go on to examine the next stub network link in the
577 if (cost
> cur_or
->cost
) {
578 if (IS_DEBUG_OSPF_EVENT
)
579 zlog_debug("%s: old route is better, exit",
584 /* (2) If this step is reached, the stub network's routing table
585 entry must be updated. Calculate the set of next hops that
586 would result from using the stub network link. This
587 calculation is shown in Section 16.1.1; input to this
588 calculation is the destination (the stub network) and the
589 parent vertex (the router vertex). If the distance D is the
590 same as the current routing table cost, simply add this set
591 of next hops to the routing table entry's list of next hops.
592 In this case, the routing table already has a Link State
593 Origin. If this Link State Origin is a router-LSA whose Link
594 State ID is smaller than V's Router ID, reset the Link State
595 Origin to V's router-LSA. */
597 if (cost
== cur_or
->cost
) {
598 if (IS_DEBUG_OSPF_EVENT
)
599 zlog_debug("%s: routes are equal, merge",
602 ospf_route_copy_nexthops_from_vertex(area
, cur_or
, v
);
604 if (IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
,
607 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
611 /* Otherwise D is smaller than the routing table cost.
612 Overwrite the current routing table entry by setting the
613 routing table entry's cost to D, and by setting the entry's
614 list of next hops to the newly calculated set. Set the
615 routing table entry's Link State Origin to V's router-LSA.
616 Then go on to examine the next stub network link. */
618 if (cost
< cur_or
->cost
) {
619 if (IS_DEBUG_OSPF_EVENT
)
620 zlog_debug("%s: new route is better, set it",
625 list_delete_all_node(cur_or
->paths
);
627 ospf_route_copy_nexthops_from_vertex(area
, cur_or
, v
);
629 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
634 if (IS_DEBUG_OSPF_EVENT
)
635 zlog_debug("%s: installing new route", __func__
);
637 or = ospf_route_new();
640 or->u
.std
.area_id
= area
->area_id
;
641 or->u
.std
.external_routing
= area
->external_routing
;
642 or->path_type
= OSPF_PATH_INTRA_AREA
;
644 or->type
= OSPF_DESTINATION_NETWORK
;
645 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
647 /* Nexthop is depend on connection type. */
648 if (v
!= area
->spf
) {
649 if (IS_DEBUG_OSPF_EVENT
)
650 zlog_debug("%s: this network is on remote router",
652 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
654 if (IS_DEBUG_OSPF_EVENT
)
655 zlog_debug("%s: this network is on this router",
659 * Only deal with interface data when we
662 if (!area
->spf_dry_run
)
663 oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
);
665 if (oi
|| area
->spf_dry_run
) {
666 if (IS_DEBUG_OSPF_EVENT
)
667 zlog_debug("%s: the lsa pos is %d", __func__
,
670 path
= ospf_path_new();
671 path
->nexthop
.s_addr
= INADDR_ANY
;
674 path
->ifindex
= oi
->ifp
->ifindex
;
675 if (CHECK_FLAG(oi
->connected
->flags
,
676 ZEBRA_IFA_UNNUMBERED
))
677 path
->unnumbered
= 1;
680 listnode_add(or->paths
, path
);
682 if (IS_DEBUG_OSPF_EVENT
)
683 zlog_debug("%s: where's the interface ?",
690 if (IS_DEBUG_OSPF_EVENT
)
691 zlog_debug("%s: Stop", __func__
);
694 static const char *const ospf_path_type_str
[] = {
695 "unknown-type", "intra-area", "inter-area", "type1-external",
699 void ospf_route_table_dump(struct route_table
*rt
)
701 struct route_node
*rn
;
702 struct ospf_route
* or ;
703 struct listnode
*pnode
;
704 struct ospf_path
*path
;
706 zlog_debug("========== OSPF routing table ==========");
707 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
708 if ((or = rn
->info
) != NULL
) {
709 if (or->type
== OSPF_DESTINATION_NETWORK
) {
710 zlog_debug("N %-18pFX %-15pI4 %s %d", &rn
->p
,
712 ospf_path_type_str
[or->path_type
],
714 for (ALL_LIST_ELEMENTS_RO(or->paths
, pnode
,
716 zlog_debug(" -> %pI4",
719 zlog_debug("R %-18pI4 %-15pI4 %s %d",
722 ospf_path_type_str
[or->path_type
],
725 zlog_debug("========================================");
728 void ospf_router_route_table_dump(struct route_table
*rt
)
730 struct route_node
*rn
;
731 struct ospf_route
*or;
732 struct listnode
*node
;
734 zlog_debug("========== OSPF routing table ==========");
735 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
)) {
736 for (ALL_LIST_ELEMENTS_RO((struct list
*)rn
->info
, node
, or)) {
737 assert(or->type
== OSPF_DESTINATION_ROUTER
);
738 zlog_debug("R %-18pI4 %-15pI4 %s %d", &rn
->p
.u
.prefix4
,
740 ospf_path_type_str
[or->path_type
], or->cost
);
743 zlog_debug("========================================");
746 /* This is 16.4.1 implementation.
747 o Intra-area paths using non-backbone areas are always the most preferred.
748 o The other paths, intra-area backbone paths and inter-area paths,
749 are of equal preference. */
750 static int ospf_asbr_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
751 struct ospf_route
*r2
)
753 uint8_t r1_type
, r2_type
;
755 r1_type
= r1
->path_type
;
756 r2_type
= r2
->path_type
;
758 /* r1/r2 itself is backbone, and it's Inter-area path. */
759 if (OSPF_IS_AREA_ID_BACKBONE(r1
->u
.std
.area_id
))
760 r1_type
= OSPF_PATH_INTER_AREA
;
761 if (OSPF_IS_AREA_ID_BACKBONE(r2
->u
.std
.area_id
))
762 r2_type
= OSPF_PATH_INTER_AREA
;
764 return (r1_type
- r2_type
);
767 /* Compare two routes.
768 ret < 0 -- r1 is better.
769 ret == 0 -- r1 and r2 are the same.
770 ret > 0 -- r2 is better. */
771 int ospf_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
772 struct ospf_route
*r2
)
776 /* Path types of r1 and r2 are not the same. */
777 if ((ret
= (r1
->path_type
- r2
->path_type
)))
780 if (IS_DEBUG_OSPF_EVENT
)
781 zlog_debug("Route[Compare]: Path types are the same.");
782 /* Path types are the same, compare any cost. */
783 switch (r1
->path_type
) {
784 case OSPF_PATH_INTRA_AREA
:
785 case OSPF_PATH_INTER_AREA
:
787 case OSPF_PATH_TYPE1_EXTERNAL
:
788 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
789 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
795 case OSPF_PATH_TYPE2_EXTERNAL
:
796 if ((ret
= (r1
->u
.ext
.type2_cost
- r2
->u
.ext
.type2_cost
)))
799 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
800 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
808 /* Anyway, compare the costs. */
809 return (r1
->cost
- r2
->cost
);
812 static int ospf_path_exist(struct list
*plist
, struct in_addr nexthop
,
813 struct ospf_interface
*oi
)
815 struct listnode
*node
, *nnode
;
816 struct ospf_path
*path
;
818 for (ALL_LIST_ELEMENTS(plist
, node
, nnode
, path
))
819 if (IPV4_ADDR_SAME(&path
->nexthop
, &nexthop
)
820 && path
->ifindex
== oi
->ifp
->ifindex
)
826 void ospf_route_copy_nexthops_from_vertex(struct ospf_area
*area
,
827 struct ospf_route
*to
,
830 struct listnode
*node
;
831 struct ospf_path
*path
;
832 struct vertex_nexthop
*nexthop
;
833 struct vertex_parent
*vp
;
834 struct ospf_interface
*oi
= NULL
;
838 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
839 nexthop
= vp
->nexthop
;
842 * Only deal with interface data when we
845 if (!area
->spf_dry_run
)
846 oi
= ospf_if_lookup_by_lsa_pos(area
, nexthop
->lsa_pos
);
848 if ((oi
&& !ospf_path_exist(to
->paths
, nexthop
->router
, oi
))
849 || area
->spf_dry_run
) {
850 path
= ospf_path_new();
851 path
->nexthop
= nexthop
->router
;
852 path
->adv_router
= v
->id
;
855 path
->ifindex
= oi
->ifp
->ifindex
;
856 if (CHECK_FLAG(oi
->connected
->flags
,
857 ZEBRA_IFA_UNNUMBERED
))
858 path
->unnumbered
= 1;
861 listnode_add(to
->paths
, path
);
866 struct ospf_path
*ospf_path_lookup(struct list
*plist
, struct ospf_path
*path
)
868 struct listnode
*node
;
869 struct ospf_path
*op
;
871 for (ALL_LIST_ELEMENTS_RO(plist
, node
, op
)) {
872 if (!IPV4_ADDR_SAME(&op
->nexthop
, &path
->nexthop
))
874 if (!IPV4_ADDR_SAME(&op
->adv_router
, &path
->adv_router
))
876 if (op
->ifindex
!= path
->ifindex
)
883 void ospf_route_copy_nexthops(struct ospf_route
*to
, struct list
*from
)
885 struct listnode
*node
, *nnode
;
886 struct ospf_path
*path
;
890 for (ALL_LIST_ELEMENTS(from
, node
, nnode
, path
))
891 /* The same routes are just discarded. */
892 if (!ospf_path_lookup(to
->paths
, path
))
893 listnode_add(to
->paths
, ospf_path_dup(path
));
896 void ospf_route_subst_nexthops(struct ospf_route
*to
, struct list
*from
)
899 list_delete_all_node(to
->paths
);
900 ospf_route_copy_nexthops(to
, from
);
903 void ospf_route_subst(struct route_node
*rn
, struct ospf_route
*new_or
,
904 struct ospf_route
*over
)
907 ospf_route_free(rn
->info
);
909 ospf_route_copy_nexthops(new_or
, over
->paths
);
911 route_unlock_node(rn
);
914 void ospf_route_add(struct route_table
*rt
, struct prefix_ipv4
*p
,
915 struct ospf_route
*new_or
, struct ospf_route
*over
)
917 struct route_node
*rn
;
919 rn
= route_node_get(rt
, (struct prefix
*)p
);
921 ospf_route_copy_nexthops(new_or
, over
->paths
);
924 if (IS_DEBUG_OSPF_EVENT
)
925 zlog_debug("%s: something's wrong !", __func__
);
926 route_unlock_node(rn
);
933 void ospf_prune_unreachable_networks(struct route_table
*rt
)
935 struct route_node
*rn
, *next
;
936 struct ospf_route
* or ;
938 if (IS_DEBUG_OSPF_EVENT
)
939 zlog_debug("Pruning unreachable networks");
941 for (rn
= route_top(rt
); rn
; rn
= next
) {
942 next
= route_next(rn
);
943 if (rn
->info
!= NULL
) {
945 if (listcount(or->paths
) == 0) {
946 if (IS_DEBUG_OSPF_EVENT
)
947 zlog_debug("Pruning route to %pFX",
952 route_unlock_node(rn
);
958 void ospf_prune_unreachable_routers(struct route_table
*rtrs
)
960 struct route_node
*rn
, *next
;
961 struct ospf_route
* or ;
962 struct listnode
*node
, *nnode
;
965 if (IS_DEBUG_OSPF_EVENT
)
966 zlog_debug("Pruning unreachable routers");
968 for (rn
= route_top(rtrs
); rn
; rn
= next
) {
969 next
= route_next(rn
);
970 if ((paths
= rn
->info
) == NULL
)
973 for (ALL_LIST_ELEMENTS(paths
, node
, nnode
, or)) {
974 if (listcount(or->paths
) == 0) {
975 if (IS_DEBUG_OSPF_EVENT
) {
976 zlog_debug("Pruning route to rtr %pI4",
983 listnode_delete(paths
, or);
988 if (listcount(paths
) == 0) {
989 if (IS_DEBUG_OSPF_EVENT
)
990 zlog_debug("Pruning router node %pI4",
995 route_unlock_node(rn
);
1000 int ospf_add_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
1001 struct ospf_area
*area
, struct prefix_ipv4
*p
)
1003 struct route_node
*rn
;
1004 struct ospf_route
* or, *new_or
;
1006 rn
= route_node_get(rt
, (struct prefix
*)p
);
1009 if (IS_DEBUG_OSPF_EVENT
)
1010 zlog_debug("%s: router installation error", __func__
);
1014 if (rn
->info
) /* If the route to the same destination is found */
1016 route_unlock_node(rn
);
1020 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
1021 if (IS_DEBUG_OSPF_EVENT
)
1022 zlog_debug("%s: an intra-area route exists",
1027 if (or->type
== OSPF_DESTINATION_DISCARD
) {
1028 if (IS_DEBUG_OSPF_EVENT
)
1030 "%s: discard entry already installed",
1035 ospf_route_free(rn
->info
);
1038 if (IS_DEBUG_OSPF_EVENT
)
1039 zlog_debug("%s: adding %pFX", __func__
, p
);
1041 new_or
= ospf_route_new();
1042 new_or
->type
= OSPF_DESTINATION_DISCARD
;
1043 new_or
->id
.s_addr
= INADDR_ANY
;
1045 new_or
->u
.std
.area_id
= area
->area_id
;
1046 new_or
->u
.std
.external_routing
= area
->external_routing
;
1047 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
1050 ospf_zebra_add_discard(ospf
, p
);
1055 void ospf_delete_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
1056 struct prefix_ipv4
*p
)
1058 struct route_node
*rn
;
1059 struct ospf_route
* or ;
1061 if (IS_DEBUG_OSPF_EVENT
)
1062 zlog_debug("%s: deleting %pFX", __func__
, p
);
1064 rn
= route_node_lookup(rt
, (struct prefix
*)p
);
1067 if (IS_DEBUG_OSPF_EVENT
)
1068 zlog_debug("%s: no route found", __func__
);
1074 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
1075 if (IS_DEBUG_OSPF_EVENT
)
1076 zlog_debug("%s: an intra-area route exists", __func__
);
1080 if (or->type
!= OSPF_DESTINATION_DISCARD
) {
1081 if (IS_DEBUG_OSPF_EVENT
)
1082 zlog_debug("%s: not a discard entry", __func__
);
1086 /* free the route entry and the route node */
1087 ospf_route_free(rn
->info
);
1090 route_unlock_node(rn
);
1091 route_unlock_node(rn
);
1093 /* remove the discard entry from the rib */
1094 ospf_zebra_delete_discard(ospf
, p
);