]>
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 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("%s: Start", __func__
);
376 lsa
= (struct router_lsa
*)v
->lsa
;
378 if (IS_DEBUG_OSPF_EVENT
)
379 zlog_debug("%s: LS ID: %pI4", __func__
, &lsa
->header
.id
);
381 if (!OSPF_IS_AREA_BACKBONE(area
))
382 ospf_vl_up_check(area
, lsa
->header
.id
, v
);
384 if (!CHECK_FLAG(lsa
->flags
, ROUTER_LSA_SHORTCUT
))
385 area
->shortcut_capability
= 0;
387 /* If the newly added vertex is an area border router or AS boundary
388 router, a routing table entry is added whose destination type is
390 if (!add_all
&& !IS_ROUTER_LSA_BORDER(lsa
) &&
391 !IS_ROUTER_LSA_EXTERNAL(lsa
)) {
392 if (IS_DEBUG_OSPF_EVENT
)
394 "%s: 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("%s: talking about %pFX", __func__
, &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("%s: Stop", __func__
);
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("%s: Start", __func__
);
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("%s: processing route to %pFX", __func__
, &p
);
541 /* (1) Calculate the distance D of stub network from the root. D is
542 equal to the distance from the root to the router vertex
543 (calculated in stage 1), plus the stub network link's advertised
545 cost
= v
->distance
+ ntohs(link
->m
[0].metric
);
547 if (IS_DEBUG_OSPF_EVENT
)
548 zlog_debug("%s: calculated cost is %d + %d = %d", __func__
,
549 v
->distance
, ntohs(link
->m
[0].metric
), cost
);
551 /* PtP links with /32 masks adds host routes to remote, directly
552 * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
553 * Such routes can just be ignored for the sake of tidyness.
555 if (parent_is_root
&& link
->link_data
.s_addr
== 0xffffffff
556 && ospf_if_lookup_by_local_addr(area
->ospf
, NULL
, link
->link_id
)) {
557 if (IS_DEBUG_OSPF_EVENT
)
558 zlog_debug("%s: ignoring host route %pI4/32 to self.",
559 __func__
, &link
->link_id
);
563 rn
= route_node_get(rt
, (struct prefix
*)&p
);
565 /* Lookup current routing table. */
567 struct ospf_route
*cur_or
;
569 route_unlock_node(rn
);
573 if (IS_DEBUG_OSPF_EVENT
)
575 "%s: another route to the same prefix found with cost %u",
576 __func__
, cur_or
->cost
);
578 /* Compare this distance to the current best cost to the stub
579 network. This is done by looking up the stub network's
580 current routing table entry. If the calculated distance D is
581 larger, go on to examine the next stub network link in the
583 if (cost
> cur_or
->cost
) {
584 if (IS_DEBUG_OSPF_EVENT
)
585 zlog_debug("%s: old route is better, exit",
590 /* (2) If this step is reached, the stub network's routing table
591 entry must be updated. Calculate the set of next hops that
592 would result from using the stub network link. This
593 calculation is shown in Section 16.1.1; input to this
594 calculation is the destination (the stub network) and the
595 parent vertex (the router vertex). If the distance D is the
596 same as the current routing table cost, simply add this set
597 of next hops to the routing table entry's list of next hops.
598 In this case, the routing table already has a Link State
599 Origin. If this Link State Origin is a router-LSA whose Link
600 State ID is smaller than V's Router ID, reset the Link State
601 Origin to V's router-LSA. */
603 if (cost
== cur_or
->cost
) {
604 if (IS_DEBUG_OSPF_EVENT
)
605 zlog_debug("%s: routes are equal, merge",
608 ospf_route_copy_nexthops_from_vertex(area
, cur_or
, v
);
610 if (IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
,
613 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
617 /* Otherwise D is smaller than the routing table cost.
618 Overwrite the current routing table entry by setting the
619 routing table entry's cost to D, and by setting the entry's
620 list of next hops to the newly calculated set. Set the
621 routing table entry's Link State Origin to V's router-LSA.
622 Then go on to examine the next stub network link. */
624 if (cost
< cur_or
->cost
) {
625 if (IS_DEBUG_OSPF_EVENT
)
626 zlog_debug("%s: new route is better, set it",
631 list_delete_all_node(cur_or
->paths
);
633 ospf_route_copy_nexthops_from_vertex(area
, cur_or
, v
);
635 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
640 if (IS_DEBUG_OSPF_EVENT
)
641 zlog_debug("%s: installing new route", __func__
);
643 or = ospf_route_new();
646 or->u
.std
.area_id
= area
->area_id
;
647 or->u
.std
.external_routing
= area
->external_routing
;
648 or->path_type
= OSPF_PATH_INTRA_AREA
;
650 or->type
= OSPF_DESTINATION_NETWORK
;
651 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
653 /* Nexthop is depend on connection type. */
654 if (v
!= area
->spf
) {
655 if (IS_DEBUG_OSPF_EVENT
)
656 zlog_debug("%s: this network is on remote router",
658 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
660 if (IS_DEBUG_OSPF_EVENT
)
661 zlog_debug("%s: this network is on this router",
665 * Only deal with interface data when we
668 if (!area
->spf_dry_run
)
669 oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
);
671 if (oi
|| area
->spf_dry_run
) {
672 if (IS_DEBUG_OSPF_EVENT
)
673 zlog_debug("%s: the lsa pos is %d", __func__
,
676 path
= ospf_path_new();
677 path
->nexthop
.s_addr
= INADDR_ANY
;
680 path
->ifindex
= oi
->ifp
->ifindex
;
681 if (CHECK_FLAG(oi
->connected
->flags
,
682 ZEBRA_IFA_UNNUMBERED
))
683 path
->unnumbered
= 1;
686 listnode_add(or->paths
, path
);
688 if (IS_DEBUG_OSPF_EVENT
)
689 zlog_debug("%s: where's the interface ?",
696 if (IS_DEBUG_OSPF_EVENT
)
697 zlog_debug("%s: Stop", __func__
);
700 static const char *const ospf_path_type_str
[] = {
701 "unknown-type", "intra-area", "inter-area", "type1-external",
705 void ospf_route_table_dump(struct route_table
*rt
)
707 struct route_node
*rn
;
708 struct ospf_route
* or ;
709 struct listnode
*pnode
;
710 struct ospf_path
*path
;
712 zlog_debug("========== OSPF routing table ==========");
713 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
714 if ((or = rn
->info
) != NULL
) {
715 if (or->type
== OSPF_DESTINATION_NETWORK
) {
716 zlog_debug("N %-18pFX %-15pI4 %s %d", &rn
->p
,
718 ospf_path_type_str
[or->path_type
],
720 for (ALL_LIST_ELEMENTS_RO(or->paths
, pnode
,
722 zlog_debug(" -> %pI4",
725 zlog_debug("R %-18pI4 %-15pI4 %s %d",
728 ospf_path_type_str
[or->path_type
],
731 zlog_debug("========================================");
734 void ospf_router_route_table_dump(struct route_table
*rt
)
736 struct route_node
*rn
;
737 struct ospf_route
*or;
738 struct listnode
*node
;
740 zlog_debug("========== OSPF routing table ==========");
741 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
)) {
742 for (ALL_LIST_ELEMENTS_RO((struct list
*)rn
->info
, node
, or)) {
743 assert(or->type
== OSPF_DESTINATION_ROUTER
);
744 zlog_debug("R %-18pI4 %-15pI4 %s %d", &rn
->p
.u
.prefix4
,
746 ospf_path_type_str
[or->path_type
], or->cost
);
749 zlog_debug("========================================");
752 /* This is 16.4.1 implementation.
753 o Intra-area paths using non-backbone areas are always the most preferred.
754 o The other paths, intra-area backbone paths and inter-area paths,
755 are of equal preference. */
756 static int ospf_asbr_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
757 struct ospf_route
*r2
)
759 uint8_t r1_type
, r2_type
;
761 r1_type
= r1
->path_type
;
762 r2_type
= r2
->path_type
;
764 /* r1/r2 itself is backbone, and it's Inter-area path. */
765 if (OSPF_IS_AREA_ID_BACKBONE(r1
->u
.std
.area_id
))
766 r1_type
= OSPF_PATH_INTER_AREA
;
767 if (OSPF_IS_AREA_ID_BACKBONE(r2
->u
.std
.area_id
))
768 r2_type
= OSPF_PATH_INTER_AREA
;
770 return (r1_type
- r2_type
);
773 /* Compare two routes.
774 ret < 0 -- r1 is better.
775 ret == 0 -- r1 and r2 are the same.
776 ret > 0 -- r2 is better. */
777 int ospf_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
778 struct ospf_route
*r2
)
782 /* Path types of r1 and r2 are not the same. */
783 if ((ret
= (r1
->path_type
- r2
->path_type
)))
786 if (IS_DEBUG_OSPF_EVENT
)
787 zlog_debug("Route[Compare]: Path types are the same.");
788 /* Path types are the same, compare any cost. */
789 switch (r1
->path_type
) {
790 case OSPF_PATH_INTRA_AREA
:
791 case OSPF_PATH_INTER_AREA
:
793 case OSPF_PATH_TYPE1_EXTERNAL
:
794 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
795 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
801 case OSPF_PATH_TYPE2_EXTERNAL
:
802 if ((ret
= (r1
->u
.ext
.type2_cost
- r2
->u
.ext
.type2_cost
)))
805 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
806 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
814 /* Anyway, compare the costs. */
815 return (r1
->cost
- r2
->cost
);
818 static int ospf_path_exist(struct list
*plist
, struct in_addr nexthop
,
819 struct ospf_interface
*oi
)
821 struct listnode
*node
, *nnode
;
822 struct ospf_path
*path
;
824 for (ALL_LIST_ELEMENTS(plist
, node
, nnode
, path
))
825 if (IPV4_ADDR_SAME(&path
->nexthop
, &nexthop
)
826 && path
->ifindex
== oi
->ifp
->ifindex
)
832 void ospf_route_copy_nexthops_from_vertex(struct ospf_area
*area
,
833 struct ospf_route
*to
,
836 struct listnode
*node
;
837 struct ospf_path
*path
;
838 struct vertex_nexthop
*nexthop
;
839 struct vertex_parent
*vp
;
840 struct ospf_interface
*oi
= NULL
;
844 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
845 nexthop
= vp
->nexthop
;
848 * Only deal with interface data when we
851 if (!area
->spf_dry_run
)
852 oi
= ospf_if_lookup_by_lsa_pos(area
, nexthop
->lsa_pos
);
854 if ((oi
&& !ospf_path_exist(to
->paths
, nexthop
->router
, oi
))
855 || area
->spf_dry_run
) {
856 path
= ospf_path_new();
857 path
->nexthop
= nexthop
->router
;
858 path
->adv_router
= v
->id
;
861 path
->ifindex
= oi
->ifp
->ifindex
;
862 if (CHECK_FLAG(oi
->connected
->flags
,
863 ZEBRA_IFA_UNNUMBERED
))
864 path
->unnumbered
= 1;
867 listnode_add(to
->paths
, path
);
872 struct ospf_path
*ospf_path_lookup(struct list
*plist
, struct ospf_path
*path
)
874 struct listnode
*node
;
875 struct ospf_path
*op
;
877 for (ALL_LIST_ELEMENTS_RO(plist
, node
, op
)) {
878 if (!IPV4_ADDR_SAME(&op
->nexthop
, &path
->nexthop
))
880 if (!IPV4_ADDR_SAME(&op
->adv_router
, &path
->adv_router
))
882 if (op
->ifindex
!= path
->ifindex
)
889 void ospf_route_copy_nexthops(struct ospf_route
*to
, struct list
*from
)
891 struct listnode
*node
, *nnode
;
892 struct ospf_path
*path
;
896 for (ALL_LIST_ELEMENTS(from
, node
, nnode
, path
))
897 /* The same routes are just discarded. */
898 if (!ospf_path_lookup(to
->paths
, path
))
899 listnode_add(to
->paths
, ospf_path_dup(path
));
902 void ospf_route_subst_nexthops(struct ospf_route
*to
, struct list
*from
)
905 list_delete_all_node(to
->paths
);
906 ospf_route_copy_nexthops(to
, from
);
909 void ospf_route_subst(struct route_node
*rn
, struct ospf_route
*new_or
,
910 struct ospf_route
*over
)
913 ospf_route_free(rn
->info
);
915 ospf_route_copy_nexthops(new_or
, over
->paths
);
917 route_unlock_node(rn
);
920 void ospf_route_add(struct route_table
*rt
, struct prefix_ipv4
*p
,
921 struct ospf_route
*new_or
, struct ospf_route
*over
)
923 struct route_node
*rn
;
925 rn
= route_node_get(rt
, (struct prefix
*)p
);
927 ospf_route_copy_nexthops(new_or
, over
->paths
);
930 if (IS_DEBUG_OSPF_EVENT
)
931 zlog_debug("%s: something's wrong !", __func__
);
932 route_unlock_node(rn
);
939 void ospf_prune_unreachable_networks(struct route_table
*rt
)
941 struct route_node
*rn
, *next
;
942 struct ospf_route
* or ;
944 if (IS_DEBUG_OSPF_EVENT
)
945 zlog_debug("Pruning unreachable networks");
947 for (rn
= route_top(rt
); rn
; rn
= next
) {
948 next
= route_next(rn
);
949 if (rn
->info
!= NULL
) {
951 if (listcount(or->paths
) == 0) {
952 if (IS_DEBUG_OSPF_EVENT
)
953 zlog_debug("Pruning route to %pFX",
958 route_unlock_node(rn
);
964 void ospf_prune_unreachable_routers(struct route_table
*rtrs
)
966 struct route_node
*rn
, *next
;
967 struct ospf_route
* or ;
968 struct listnode
*node
, *nnode
;
971 if (IS_DEBUG_OSPF_EVENT
)
972 zlog_debug("Pruning unreachable routers");
974 for (rn
= route_top(rtrs
); rn
; rn
= next
) {
975 next
= route_next(rn
);
976 if ((paths
= rn
->info
) == NULL
)
979 for (ALL_LIST_ELEMENTS(paths
, node
, nnode
, or)) {
980 if (listcount(or->paths
) == 0) {
981 if (IS_DEBUG_OSPF_EVENT
) {
982 zlog_debug("Pruning route to rtr %pI4",
989 listnode_delete(paths
, or);
994 if (listcount(paths
) == 0) {
995 if (IS_DEBUG_OSPF_EVENT
)
996 zlog_debug("Pruning router node %pI4",
1001 route_unlock_node(rn
);
1006 int ospf_add_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
1007 struct ospf_area
*area
, struct prefix_ipv4
*p
)
1009 struct route_node
*rn
;
1010 struct ospf_route
* or, *new_or
;
1012 rn
= route_node_get(rt
, (struct prefix
*)p
);
1015 if (IS_DEBUG_OSPF_EVENT
)
1016 zlog_debug("%s: router installation error", __func__
);
1020 if (rn
->info
) /* If the route to the same destination is found */
1022 route_unlock_node(rn
);
1026 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
1027 if (IS_DEBUG_OSPF_EVENT
)
1028 zlog_debug("%s: an intra-area route exists",
1033 if (or->type
== OSPF_DESTINATION_DISCARD
) {
1034 if (IS_DEBUG_OSPF_EVENT
)
1036 "%s: discard entry already installed",
1041 ospf_route_free(rn
->info
);
1044 if (IS_DEBUG_OSPF_EVENT
)
1045 zlog_debug("%s: adding %pFX", __func__
, p
);
1047 new_or
= ospf_route_new();
1048 new_or
->type
= OSPF_DESTINATION_DISCARD
;
1049 new_or
->id
.s_addr
= INADDR_ANY
;
1051 new_or
->u
.std
.area_id
= area
->area_id
;
1052 new_or
->u
.std
.external_routing
= area
->external_routing
;
1053 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
1056 ospf_zebra_add_discard(ospf
, p
);
1061 void ospf_delete_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
1062 struct prefix_ipv4
*p
)
1064 struct route_node
*rn
;
1065 struct ospf_route
* or ;
1067 if (IS_DEBUG_OSPF_EVENT
)
1068 zlog_debug("%s: deleting %pFX", __func__
, p
);
1070 rn
= route_node_lookup(rt
, (struct prefix
*)p
);
1073 if (IS_DEBUG_OSPF_EVENT
)
1074 zlog_debug("%s: no route found", __func__
);
1080 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
1081 if (IS_DEBUG_OSPF_EVENT
)
1082 zlog_debug("%s: an intra-area route exists", __func__
);
1086 if (or->type
!= OSPF_DESTINATION_DISCARD
) {
1087 if (IS_DEBUG_OSPF_EVENT
)
1088 zlog_debug("%s: not a discard entry", __func__
);
1092 /* free the route entry and the route node */
1093 ospf_route_free(rn
->info
);
1096 route_unlock_node(rn
);
1097 route_unlock_node(rn
);
1099 /* remove the discard entry from the rib */
1100 ospf_zebra_delete_discard(ospf
, p
);