]>
git.proxmox.com Git - mirror_frr.git/blob - ospfd/ospf_route.c
3 * Copyright (C) 1999, 2000 Toshiaki Takada
5 * This file is part of GNU Zebra.
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
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.
17 * You should have received a copy of the GNU General Public License along
18 * with this program; see the file COPYING; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
31 #include "sockunion.h"
33 #include "ospfd/ospfd.h"
34 #include "ospfd/ospf_interface.h"
35 #include "ospfd/ospf_asbr.h"
36 #include "ospfd/ospf_lsa.h"
37 #include "ospfd/ospf_route.h"
38 #include "ospfd/ospf_spf.h"
39 #include "ospfd/ospf_zebra.h"
40 #include "ospfd/ospf_dump.h"
42 const char *ospf_path_type_name(int path_type
)
45 case OSPF_PATH_INTRA_AREA
:
47 case OSPF_PATH_INTER_AREA
:
49 case OSPF_PATH_TYPE1_EXTERNAL
:
51 case OSPF_PATH_TYPE2_EXTERNAL
:
58 struct ospf_route
*ospf_route_new(void)
60 struct ospf_route
*new;
62 new = XCALLOC(MTYPE_OSPF_ROUTE
, sizeof(struct ospf_route
));
64 new->paths
= list_new();
65 new->paths
->del
= (void (*)(void *))ospf_path_free
;
70 void ospf_route_free(struct ospf_route
*or)
73 list_delete(& or->paths
);
75 XFREE(MTYPE_OSPF_ROUTE
, or);
78 struct ospf_path
*ospf_path_new(void)
80 struct ospf_path
*new;
82 new = XCALLOC(MTYPE_OSPF_PATH
, sizeof(struct ospf_path
));
87 static struct ospf_path
*ospf_path_dup(struct ospf_path
*path
)
89 struct ospf_path
*new;
92 new = ospf_path_new();
93 memcpy(new, path
, sizeof(struct ospf_path
));
95 /* optional TI-LFA backup paths */
96 if (path
->srni
.backup_label_stack
) {
97 memsize
= sizeof(struct mpls_label_stack
)
98 + (sizeof(mpls_label_t
)
99 * path
->srni
.backup_label_stack
->num_labels
);
100 new->srni
.backup_label_stack
=
101 XCALLOC(MTYPE_OSPF_PATH
, memsize
);
102 memcpy(new->srni
.backup_label_stack
,
103 path
->srni
.backup_label_stack
, memsize
);
109 void ospf_path_free(struct ospf_path
*op
)
111 /* optional TI-LFA backup paths */
112 if (op
->srni
.backup_label_stack
)
113 XFREE(MTYPE_OSPF_PATH
, op
->srni
.backup_label_stack
);
115 XFREE(MTYPE_OSPF_PATH
, op
);
118 void ospf_route_delete(struct ospf
*ospf
, struct route_table
*rt
)
120 struct route_node
*rn
;
121 struct ospf_route
* or ;
123 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
124 if ((or = rn
->info
) != NULL
) {
125 if (or->type
== OSPF_DESTINATION_NETWORK
)
127 ospf
, (struct prefix_ipv4
*)&rn
->p
, or);
128 else if (or->type
== OSPF_DESTINATION_DISCARD
)
129 ospf_zebra_delete_discard(
130 ospf
, (struct prefix_ipv4
*)&rn
->p
);
134 void ospf_route_table_free(struct route_table
*rt
)
136 struct route_node
*rn
;
137 struct ospf_route
* or ;
139 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
140 if ((or = rn
->info
) != NULL
) {
144 route_unlock_node(rn
);
147 route_table_finish(rt
);
150 /* If a prefix exists in the new routing table, then return 1,
151 otherwise return 0. Since the ZEBRA-RIB does an implicit
152 withdraw, it is not necessary to send a delete, an add later
153 will act like an implicit delete. */
154 static int ospf_route_exist_new_table(struct route_table
*rt
,
155 struct prefix_ipv4
*prefix
)
157 struct route_node
*rn
;
162 rn
= route_node_lookup(rt
, (struct prefix
*)prefix
);
166 route_unlock_node(rn
);
175 static int ospf_route_backup_path_same(struct sr_nexthop_info
*srni1
,
176 struct sr_nexthop_info
*srni2
)
178 struct mpls_label_stack
*ls1
, *ls2
;
181 ls1
= srni1
->backup_label_stack
;
182 ls2
= srni2
->backup_label_stack
;
187 if ((ls1
&& !ls2
) || (!ls1
&& ls2
))
190 if (ls1
->num_labels
!= ls2
->num_labels
)
193 for (label_count
= 0; label_count
< ls1
->num_labels
; label_count
++) {
194 if (ls1
->label
[label_count
] != ls2
->label
[label_count
])
198 if (!IPV4_ADDR_SAME(&srni1
->backup_nexthop
, &srni2
->backup_nexthop
))
204 /* If a prefix and a nexthop match any route in the routing table,
205 then return 1, otherwise return 0. */
206 int ospf_route_match_same(struct route_table
*rt
, struct prefix_ipv4
*prefix
,
207 struct ospf_route
*newor
)
209 struct route_node
*rn
;
210 struct ospf_route
* or ;
211 struct ospf_path
*op
;
212 struct ospf_path
*newop
;
219 rn
= route_node_lookup(rt
, (struct prefix
*)prefix
);
220 if (!rn
|| !rn
->info
)
223 route_unlock_node(rn
);
226 if (or->type
== newor
->type
&& or->cost
== newor
->cost
) {
230 if (or->type
== OSPF_DESTINATION_NETWORK
) {
231 if (or->paths
->count
!= newor
->paths
->count
)
234 /* Check each path. */
235 for (n1
= listhead(or->paths
),
236 n2
= listhead(newor
->paths
);
237 n1
&& n2
; n1
= listnextnode_unchecked(n1
),
238 n2
= listnextnode_unchecked(n2
)) {
239 op
= listgetdata(n1
);
240 newop
= listgetdata(n2
);
242 if (!IPV4_ADDR_SAME(&op
->nexthop
,
245 if (op
->ifindex
!= newop
->ifindex
)
248 /* check TI-LFA backup paths */
249 if (!ospf_route_backup_path_same(&op
->srni
,
254 } else if (prefix_same(&rn
->p
, (struct prefix
*)prefix
))
260 /* delete routes generated from AS-External routes if there is a inter/intra
263 static void ospf_route_delete_same_ext(struct ospf
*ospf
,
264 struct route_table
*external_routes
,
265 struct route_table
*routes
)
267 struct route_node
*rn
, *ext_rn
;
269 if ((external_routes
== NULL
) || (routes
== NULL
))
272 /* Remove deleted routes */
273 for (rn
= route_top(routes
); rn
; rn
= route_next(rn
)) {
274 if (rn
&& rn
->info
) {
275 struct prefix_ipv4
*p
= (struct prefix_ipv4
*)(&rn
->p
);
276 if ((ext_rn
= route_node_lookup(external_routes
,
277 (struct prefix
*)p
))) {
279 ospf_zebra_delete(ospf
, p
,
281 ospf_route_free(ext_rn
->info
);
284 route_unlock_node(ext_rn
);
290 /* rt: Old, cmprt: New */
291 static void ospf_route_delete_uniq(struct ospf
*ospf
, struct route_table
*rt
,
292 struct route_table
*cmprt
)
294 struct route_node
*rn
;
295 struct ospf_route
* or ;
297 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
298 if ((or = rn
->info
) != NULL
)
299 if (or->path_type
== OSPF_PATH_INTRA_AREA
||
300 or->path_type
== OSPF_PATH_INTER_AREA
) {
301 if (or->type
== OSPF_DESTINATION_NETWORK
) {
302 if (!ospf_route_exist_new_table(
304 (struct prefix_ipv4
*)&rn
311 } else if (or->type
== OSPF_DESTINATION_DISCARD
)
312 if (!ospf_route_exist_new_table(
314 (struct prefix_ipv4
*)&rn
316 ospf_zebra_delete_discard(
323 /* Install routes to table. */
324 void ospf_route_install(struct ospf
*ospf
, struct route_table
*rt
)
326 struct route_node
*rn
;
327 struct ospf_route
* or ;
329 /* rt contains new routing table, new_table contains an old one.
332 ospf_route_table_free(ospf
->old_table
);
334 ospf
->old_table
= ospf
->new_table
;
335 ospf
->new_table
= rt
;
337 /* Delete old routes. */
339 ospf_route_delete_uniq(ospf
, ospf
->old_table
, rt
);
340 if (ospf
->old_external_route
)
341 ospf_route_delete_same_ext(ospf
, ospf
->old_external_route
, rt
);
343 /* Install new routes. */
344 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
345 if ((or = rn
->info
) != NULL
) {
346 if (or->type
== OSPF_DESTINATION_NETWORK
) {
347 if (!ospf_route_match_same(
349 (struct prefix_ipv4
*)&rn
->p
, or))
352 (struct prefix_ipv4
*)&rn
->p
,
354 } else if (or->type
== OSPF_DESTINATION_DISCARD
)
355 if (!ospf_route_match_same(
357 (struct prefix_ipv4
*)&rn
->p
, or))
358 ospf_zebra_add_discard(
360 (struct prefix_ipv4
*)&rn
->p
);
364 /* RFC2328 16.1. (4). For "router". */
365 void ospf_intra_add_router(struct route_table
*rt
, struct vertex
*v
,
366 struct ospf_area
*area
, bool add_all
)
368 struct route_node
*rn
;
369 struct ospf_route
* or ;
370 struct prefix_ipv4 p
;
371 struct router_lsa
*lsa
;
373 if (IS_DEBUG_OSPF_EVENT
)
374 zlog_debug("ospf_intra_add_router: Start");
376 lsa
= (struct router_lsa
*)v
->lsa
;
378 if (IS_DEBUG_OSPF_EVENT
)
379 zlog_debug("ospf_intra_add_router: LS ID: %pI4",
382 if (!OSPF_IS_AREA_BACKBONE(area
))
383 ospf_vl_up_check(area
, lsa
->header
.id
, v
);
385 if (!CHECK_FLAG(lsa
->flags
, ROUTER_LSA_SHORTCUT
))
386 area
->shortcut_capability
= 0;
388 /* If the newly added vertex is an area border router or AS boundary
389 router, a routing table entry is added whose destination type is
391 if (!add_all
&& !IS_ROUTER_LSA_BORDER(lsa
) &&
392 !IS_ROUTER_LSA_EXTERNAL(lsa
)) {
393 if (IS_DEBUG_OSPF_EVENT
)
395 "ospf_intra_add_router: this router is neither ASBR nor ABR, skipping it");
399 /* Update ABR and ASBR count in this area. */
400 if (IS_ROUTER_LSA_BORDER(lsa
))
402 if (IS_ROUTER_LSA_EXTERNAL(lsa
))
405 /* The Options field found in the associated router-LSA is copied
406 into the routing table entry's Optional capabilities field. Call
407 the newly added vertex Router X. */
408 or = ospf_route_new();
411 or->u
.std
.area_id
= area
->area_id
;
412 or->u
.std
.external_routing
= area
->external_routing
;
413 or->path_type
= OSPF_PATH_INTRA_AREA
;
414 or->cost
= v
->distance
;
415 or->type
= OSPF_DESTINATION_ROUTER
;
416 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
417 or->u
.std
.options
= lsa
->header
.options
;
418 or->u
.std
.flags
= lsa
->flags
;
420 /* If Router X is the endpoint of one of the calculating router's
421 virtual links, and the virtual link uses Area A as Transit area:
422 the virtual link is declared up, the IP address of the virtual
423 interface is set to the IP address of the outgoing interface
424 calculated above for Router X, and the virtual neighbor's IP
425 address is set to Router X's interface address (contained in
426 Router X's router-LSA) that points back to the root of the
427 shortest- path tree; equivalently, this is the interface that
428 points back to Router X's parent vertex on the shortest-path tree
429 (similar to the calculation in Section 16.1.1). */
433 p
.prefixlen
= IPV4_MAX_BITLEN
;
436 if (IS_DEBUG_OSPF_EVENT
)
437 zlog_debug("ospf_intra_add_router: talking about %pFX", &p
);
439 rn
= route_node_get(rt
, (struct prefix
*)&p
);
441 /* Note that we keep all routes to ABRs and ASBRs, not only the best */
442 if (rn
->info
== NULL
)
443 rn
->info
= list_new();
445 route_unlock_node(rn
);
447 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
449 listnode_add(rn
->info
, or);
451 if (IS_DEBUG_OSPF_EVENT
)
452 zlog_debug("ospf_intra_add_router: Stop");
455 /* RFC2328 16.1. (4). For transit network. */
456 void ospf_intra_add_transit(struct route_table
*rt
, struct vertex
*v
,
457 struct ospf_area
*area
)
459 struct route_node
*rn
;
460 struct ospf_route
* or ;
461 struct prefix_ipv4 p
;
462 struct network_lsa
*lsa
;
464 lsa
= (struct network_lsa
*)v
->lsa
;
466 /* If the newly added vertex is a transit network, the routing table
467 entry for the network is located. The entry's Destination ID is
468 the IP network number, which can be obtained by masking the
469 Vertex ID (Link State ID) with its associated subnet mask (found
470 in the body of the associated network-LSA). */
473 p
.prefixlen
= ip_masklen(lsa
->mask
);
476 rn
= route_node_get(rt
, (struct prefix
*)&p
);
478 /* If the routing table entry already exists (i.e., there is already
479 an intra-area route to the destination installed in the routing
480 table), multiple vertices have mapped to the same IP network.
481 For example, this can occur when a new Designated Router is being
482 established. In this case, the current routing table entry
483 should be overwritten if and only if the newly found path is just
484 as short and the current routing table entry's Link State Origin
485 has a smaller Link State ID than the newly added vertex' LSA. */
487 struct ospf_route
*cur_or
;
489 route_unlock_node(rn
);
492 if (v
->distance
> cur_or
->cost
493 || IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
, &lsa
->header
.id
)
497 ospf_route_free(rn
->info
);
500 or = ospf_route_new();
503 or->u
.std
.area_id
= area
->area_id
;
504 or->u
.std
.external_routing
= area
->external_routing
;
505 or->path_type
= OSPF_PATH_INTRA_AREA
;
506 or->cost
= v
->distance
;
507 or->type
= OSPF_DESTINATION_NETWORK
;
508 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
510 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
515 /* RFC2328 16.1. second stage. */
516 void ospf_intra_add_stub(struct route_table
*rt
, struct router_lsa_link
*link
,
517 struct vertex
*v
, struct ospf_area
*area
,
518 int parent_is_root
, int lsa_pos
)
521 struct route_node
*rn
;
522 struct ospf_route
* or ;
523 struct prefix_ipv4 p
;
524 struct router_lsa
*lsa
;
525 struct ospf_interface
*oi
= NULL
;
526 struct ospf_path
*path
;
528 if (IS_DEBUG_OSPF_EVENT
)
529 zlog_debug("ospf_intra_add_stub(): Start");
531 lsa
= (struct router_lsa
*)v
->lsa
;
534 p
.prefix
= link
->link_id
;
535 p
.prefixlen
= ip_masklen(link
->link_data
);
538 if (IS_DEBUG_OSPF_EVENT
)
539 zlog_debug("ospf_intra_add_stub(): processing route to %pFX",
542 /* (1) Calculate the distance D of stub network from the root. D is
543 equal to the distance from the root to the router vertex
544 (calculated in stage 1), plus the stub network link's advertised
546 cost
= v
->distance
+ ntohs(link
->m
[0].metric
);
548 if (IS_DEBUG_OSPF_EVENT
)
550 "ospf_intra_add_stub(): calculated cost is %d + %d = %d",
551 v
->distance
, ntohs(link
->m
[0].metric
), cost
);
553 /* PtP links with /32 masks adds host routes to remote, directly
554 * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
555 * Such routes can just be ignored for the sake of tidyness.
557 if (parent_is_root
&& link
->link_data
.s_addr
== 0xffffffff
558 && ospf_if_lookup_by_local_addr(area
->ospf
, NULL
, link
->link_id
)) {
559 if (IS_DEBUG_OSPF_EVENT
)
560 zlog_debug("%s: ignoring host route %pI4/32 to self.",
561 __func__
, &link
->link_id
);
565 rn
= route_node_get(rt
, (struct prefix
*)&p
);
567 /* Lookup current routing table. */
569 struct ospf_route
*cur_or
;
571 route_unlock_node(rn
);
575 if (IS_DEBUG_OSPF_EVENT
)
577 "ospf_intra_add_stub(): another route to the same prefix found with cost %u",
580 /* Compare this distance to the current best cost to the stub
581 network. This is done by looking up the stub network's
582 current routing table entry. If the calculated distance D is
583 larger, go on to examine the next stub network link in the
585 if (cost
> cur_or
->cost
) {
586 if (IS_DEBUG_OSPF_EVENT
)
588 "ospf_intra_add_stub(): old route is better, exit");
592 /* (2) If this step is reached, the stub network's routing table
593 entry must be updated. Calculate the set of next hops that
594 would result from using the stub network link. This
595 calculation is shown in Section 16.1.1; input to this
596 calculation is the destination (the stub network) and the
597 parent vertex (the router vertex). If the distance D is the
598 same as the current routing table cost, simply add this set
599 of next hops to the routing table entry's list of next hops.
600 In this case, the routing table already has a Link State
601 Origin. If this Link State Origin is a router-LSA whose Link
602 State ID is smaller than V's Router ID, reset the Link State
603 Origin to V's router-LSA. */
605 if (cost
== cur_or
->cost
) {
606 if (IS_DEBUG_OSPF_EVENT
)
608 "ospf_intra_add_stub(): routes are equal, merge");
610 ospf_route_copy_nexthops_from_vertex(area
, cur_or
, v
);
612 if (IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
,
615 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
619 /* Otherwise D is smaller than the routing table cost.
620 Overwrite the current routing table entry by setting the
621 routing table entry's cost to D, and by setting the entry's
622 list of next hops to the newly calculated set. Set the
623 routing table entry's Link State Origin to V's router-LSA.
624 Then go on to examine the next stub network link. */
626 if (cost
< cur_or
->cost
) {
627 if (IS_DEBUG_OSPF_EVENT
)
629 "ospf_intra_add_stub(): new route is better, set it");
633 list_delete_all_node(cur_or
->paths
);
635 ospf_route_copy_nexthops_from_vertex(area
, cur_or
, v
);
637 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
642 if (IS_DEBUG_OSPF_EVENT
)
643 zlog_debug("ospf_intra_add_stub(): installing new route");
645 or = ospf_route_new();
648 or->u
.std
.area_id
= area
->area_id
;
649 or->u
.std
.external_routing
= area
->external_routing
;
650 or->path_type
= OSPF_PATH_INTRA_AREA
;
652 or->type
= OSPF_DESTINATION_NETWORK
;
653 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
655 /* Nexthop is depend on connection type. */
656 if (v
!= area
->spf
) {
657 if (IS_DEBUG_OSPF_EVENT
)
659 "ospf_intra_add_stub(): this network is on remote router");
660 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
662 if (IS_DEBUG_OSPF_EVENT
)
664 "ospf_intra_add_stub(): this network is on this router");
667 * Only deal with interface data when we
670 if (!area
->spf_dry_run
)
671 oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
);
673 if (oi
|| area
->spf_dry_run
) {
674 if (IS_DEBUG_OSPF_EVENT
)
676 "ospf_intra_add_stub(): the lsa pos is %d",
679 path
= ospf_path_new();
680 path
->nexthop
.s_addr
= INADDR_ANY
;
683 path
->ifindex
= oi
->ifp
->ifindex
;
684 if (CHECK_FLAG(oi
->connected
->flags
,
685 ZEBRA_IFA_UNNUMBERED
))
686 path
->unnumbered
= 1;
689 listnode_add(or->paths
, path
);
691 if (IS_DEBUG_OSPF_EVENT
)
693 "ospf_intra_add_stub(): where's the interface ?");
699 if (IS_DEBUG_OSPF_EVENT
)
700 zlog_debug("ospf_intra_add_stub(): Stop");
703 static const char *const ospf_path_type_str
[] = {
704 "unknown-type", "intra-area", "inter-area", "type1-external",
708 void ospf_route_table_dump(struct route_table
*rt
)
710 struct route_node
*rn
;
711 struct ospf_route
* or ;
712 struct listnode
*pnode
;
713 struct ospf_path
*path
;
715 zlog_debug("========== OSPF routing table ==========");
716 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
717 if ((or = rn
->info
) != NULL
) {
718 if (or->type
== OSPF_DESTINATION_NETWORK
) {
719 zlog_debug("N %-18pFX %-15pI4 %s %d", &rn
->p
,
721 ospf_path_type_str
[or->path_type
],
723 for (ALL_LIST_ELEMENTS_RO(or->paths
, pnode
,
725 zlog_debug(" -> %pI4",
728 zlog_debug("R %-18pI4 %-15pI4 %s %d",
731 ospf_path_type_str
[or->path_type
],
734 zlog_debug("========================================");
737 void ospf_router_route_table_dump(struct route_table
*rt
)
739 struct route_node
*rn
;
740 struct ospf_route
*or;
741 struct listnode
*node
;
743 zlog_debug("========== OSPF routing table ==========");
744 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
)) {
745 for (ALL_LIST_ELEMENTS_RO((struct list
*)rn
->info
, node
, or)) {
746 assert(or->type
== OSPF_DESTINATION_ROUTER
);
747 zlog_debug("R %-18pI4 %-15pI4 %s %d", &rn
->p
.u
.prefix4
,
749 ospf_path_type_str
[or->path_type
], or->cost
);
752 zlog_debug("========================================");
755 /* This is 16.4.1 implementation.
756 o Intra-area paths using non-backbone areas are always the most preferred.
757 o The other paths, intra-area backbone paths and inter-area paths,
758 are of equal preference. */
759 static int ospf_asbr_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
760 struct ospf_route
*r2
)
762 uint8_t r1_type
, r2_type
;
764 r1_type
= r1
->path_type
;
765 r2_type
= r2
->path_type
;
767 /* r1/r2 itself is backbone, and it's Inter-area path. */
768 if (OSPF_IS_AREA_ID_BACKBONE(r1
->u
.std
.area_id
))
769 r1_type
= OSPF_PATH_INTER_AREA
;
770 if (OSPF_IS_AREA_ID_BACKBONE(r2
->u
.std
.area_id
))
771 r2_type
= OSPF_PATH_INTER_AREA
;
773 return (r1_type
- r2_type
);
776 /* Compare two routes.
777 ret < 0 -- r1 is better.
778 ret == 0 -- r1 and r2 are the same.
779 ret > 0 -- r2 is better. */
780 int ospf_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
781 struct ospf_route
*r2
)
785 /* Path types of r1 and r2 are not the same. */
786 if ((ret
= (r1
->path_type
- r2
->path_type
)))
789 if (IS_DEBUG_OSPF_EVENT
)
790 zlog_debug("Route[Compare]: Path types are the same.");
791 /* Path types are the same, compare any cost. */
792 switch (r1
->path_type
) {
793 case OSPF_PATH_INTRA_AREA
:
794 case OSPF_PATH_INTER_AREA
:
796 case OSPF_PATH_TYPE1_EXTERNAL
:
797 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
798 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
804 case OSPF_PATH_TYPE2_EXTERNAL
:
805 if ((ret
= (r1
->u
.ext
.type2_cost
- r2
->u
.ext
.type2_cost
)))
808 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
809 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
817 /* Anyway, compare the costs. */
818 return (r1
->cost
- r2
->cost
);
821 static int ospf_path_exist(struct list
*plist
, struct in_addr nexthop
,
822 struct ospf_interface
*oi
)
824 struct listnode
*node
, *nnode
;
825 struct ospf_path
*path
;
827 for (ALL_LIST_ELEMENTS(plist
, node
, nnode
, path
))
828 if (IPV4_ADDR_SAME(&path
->nexthop
, &nexthop
)
829 && path
->ifindex
== oi
->ifp
->ifindex
)
835 void ospf_route_copy_nexthops_from_vertex(struct ospf_area
*area
,
836 struct ospf_route
*to
,
839 struct listnode
*node
;
840 struct ospf_path
*path
;
841 struct vertex_nexthop
*nexthop
;
842 struct vertex_parent
*vp
;
843 struct ospf_interface
*oi
= NULL
;
847 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
848 nexthop
= vp
->nexthop
;
851 * Only deal with interface data when we
854 if (!area
->spf_dry_run
)
855 oi
= ospf_if_lookup_by_lsa_pos(area
, nexthop
->lsa_pos
);
857 if ((oi
&& !ospf_path_exist(to
->paths
, nexthop
->router
, oi
))
858 || area
->spf_dry_run
) {
859 path
= ospf_path_new();
860 path
->nexthop
= nexthop
->router
;
861 path
->adv_router
= v
->id
;
864 path
->ifindex
= oi
->ifp
->ifindex
;
865 if (CHECK_FLAG(oi
->connected
->flags
,
866 ZEBRA_IFA_UNNUMBERED
))
867 path
->unnumbered
= 1;
870 listnode_add(to
->paths
, path
);
875 struct ospf_path
*ospf_path_lookup(struct list
*plist
, struct ospf_path
*path
)
877 struct listnode
*node
;
878 struct ospf_path
*op
;
880 for (ALL_LIST_ELEMENTS_RO(plist
, node
, op
)) {
881 if (!IPV4_ADDR_SAME(&op
->nexthop
, &path
->nexthop
))
883 if (!IPV4_ADDR_SAME(&op
->adv_router
, &path
->adv_router
))
885 if (op
->ifindex
!= path
->ifindex
)
892 void ospf_route_copy_nexthops(struct ospf_route
*to
, struct list
*from
)
894 struct listnode
*node
, *nnode
;
895 struct ospf_path
*path
;
899 for (ALL_LIST_ELEMENTS(from
, node
, nnode
, path
))
900 /* The same routes are just discarded. */
901 if (!ospf_path_lookup(to
->paths
, path
))
902 listnode_add(to
->paths
, ospf_path_dup(path
));
905 void ospf_route_subst_nexthops(struct ospf_route
*to
, struct list
*from
)
908 list_delete_all_node(to
->paths
);
909 ospf_route_copy_nexthops(to
, from
);
912 void ospf_route_subst(struct route_node
*rn
, struct ospf_route
*new_or
,
913 struct ospf_route
*over
)
916 ospf_route_free(rn
->info
);
918 ospf_route_copy_nexthops(new_or
, over
->paths
);
920 route_unlock_node(rn
);
923 void ospf_route_add(struct route_table
*rt
, struct prefix_ipv4
*p
,
924 struct ospf_route
*new_or
, struct ospf_route
*over
)
926 struct route_node
*rn
;
928 rn
= route_node_get(rt
, (struct prefix
*)p
);
930 ospf_route_copy_nexthops(new_or
, over
->paths
);
933 if (IS_DEBUG_OSPF_EVENT
)
934 zlog_debug("ospf_route_add(): something's wrong !");
935 route_unlock_node(rn
);
942 void ospf_prune_unreachable_networks(struct route_table
*rt
)
944 struct route_node
*rn
, *next
;
945 struct ospf_route
* or ;
947 if (IS_DEBUG_OSPF_EVENT
)
948 zlog_debug("Pruning unreachable networks");
950 for (rn
= route_top(rt
); rn
; rn
= next
) {
951 next
= route_next(rn
);
952 if (rn
->info
!= NULL
) {
954 if (listcount(or->paths
) == 0) {
955 if (IS_DEBUG_OSPF_EVENT
)
956 zlog_debug("Pruning route to %pFX",
961 route_unlock_node(rn
);
967 void ospf_prune_unreachable_routers(struct route_table
*rtrs
)
969 struct route_node
*rn
, *next
;
970 struct ospf_route
* or ;
971 struct listnode
*node
, *nnode
;
974 if (IS_DEBUG_OSPF_EVENT
)
975 zlog_debug("Pruning unreachable routers");
977 for (rn
= route_top(rtrs
); rn
; rn
= next
) {
978 next
= route_next(rn
);
979 if ((paths
= rn
->info
) == NULL
)
982 for (ALL_LIST_ELEMENTS(paths
, node
, nnode
, or)) {
983 if (listcount(or->paths
) == 0) {
984 if (IS_DEBUG_OSPF_EVENT
) {
985 zlog_debug("Pruning route to rtr %pI4",
992 listnode_delete(paths
, or);
997 if (listcount(paths
) == 0) {
998 if (IS_DEBUG_OSPF_EVENT
)
999 zlog_debug("Pruning router node %pI4",
1002 list_delete(&paths
);
1004 route_unlock_node(rn
);
1009 int ospf_add_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
1010 struct ospf_area
*area
, struct prefix_ipv4
*p
)
1012 struct route_node
*rn
;
1013 struct ospf_route
* or, *new_or
;
1015 rn
= route_node_get(rt
, (struct prefix
*)p
);
1018 if (IS_DEBUG_OSPF_EVENT
)
1020 "ospf_add_discard_route(): router installation error");
1024 if (rn
->info
) /* If the route to the same destination is found */
1026 route_unlock_node(rn
);
1030 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
1031 if (IS_DEBUG_OSPF_EVENT
)
1033 "ospf_add_discard_route(): an intra-area route exists");
1037 if (or->type
== OSPF_DESTINATION_DISCARD
) {
1038 if (IS_DEBUG_OSPF_EVENT
)
1040 "ospf_add_discard_route(): discard entry already installed");
1044 ospf_route_free(rn
->info
);
1047 if (IS_DEBUG_OSPF_EVENT
)
1048 zlog_debug("ospf_add_discard_route(): adding %pFX", p
);
1050 new_or
= ospf_route_new();
1051 new_or
->type
= OSPF_DESTINATION_DISCARD
;
1052 new_or
->id
.s_addr
= INADDR_ANY
;
1054 new_or
->u
.std
.area_id
= area
->area_id
;
1055 new_or
->u
.std
.external_routing
= area
->external_routing
;
1056 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
1059 ospf_zebra_add_discard(ospf
, p
);
1064 void ospf_delete_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
1065 struct prefix_ipv4
*p
)
1067 struct route_node
*rn
;
1068 struct ospf_route
* or ;
1070 if (IS_DEBUG_OSPF_EVENT
)
1071 zlog_debug("ospf_delete_discard_route(): deleting %pFX", p
);
1073 rn
= route_node_lookup(rt
, (struct prefix
*)p
);
1076 if (IS_DEBUG_OSPF_EVENT
)
1078 "ospf_delete_discard_route(): no route found");
1084 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
1085 if (IS_DEBUG_OSPF_EVENT
)
1087 "ospf_delete_discard_route(): an intra-area route exists");
1091 if (or->type
!= OSPF_DESTINATION_DISCARD
) {
1092 if (IS_DEBUG_OSPF_EVENT
)
1094 "ospf_delete_discard_route(): not a discard entry");
1098 /* free the route entry and the route node */
1099 ospf_route_free(rn
->info
);
1102 route_unlock_node(rn
);
1103 route_unlock_node(rn
);
1105 /* remove the discard entry from the rib */
1106 ospf_zebra_delete_discard(ospf
, p
);