]>
git.proxmox.com Git - mirror_frr.git/blob - ospfd/ospf_route.c
ec0c5524c93678aa2114ee281fdd2cff6e0637b7
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
)
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 (!IS_ROUTER_LSA_BORDER(lsa
) && !IS_ROUTER_LSA_EXTERNAL(lsa
)) {
392 if (IS_DEBUG_OSPF_EVENT
)
394 "ospf_intra_add_router: this router is neither ASBR nor ABR, skipping it");
398 /* Update ABR and ASBR count in this area. */
399 if (IS_ROUTER_LSA_BORDER(lsa
))
401 if (IS_ROUTER_LSA_EXTERNAL(lsa
))
404 /* The Options field found in the associated router-LSA is copied
405 into the routing table entry's Optional capabilities field. Call
406 the newly added vertex Router X. */
407 or = ospf_route_new();
410 or->u
.std
.area_id
= area
->area_id
;
411 or->u
.std
.external_routing
= area
->external_routing
;
412 or->path_type
= OSPF_PATH_INTRA_AREA
;
413 or->cost
= v
->distance
;
414 or->type
= OSPF_DESTINATION_ROUTER
;
415 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
416 or->u
.std
.options
= lsa
->header
.options
;
417 or->u
.std
.flags
= lsa
->flags
;
419 /* If Router X is the endpoint of one of the calculating router's
420 virtual links, and the virtual link uses Area A as Transit area:
421 the virtual link is declared up, the IP address of the virtual
422 interface is set to the IP address of the outgoing interface
423 calculated above for Router X, and the virtual neighbor's IP
424 address is set to Router X's interface address (contained in
425 Router X's router-LSA) that points back to the root of the
426 shortest- path tree; equivalently, this is the interface that
427 points back to Router X's parent vertex on the shortest-path tree
428 (similar to the calculation in Section 16.1.1). */
432 p
.prefixlen
= IPV4_MAX_BITLEN
;
435 if (IS_DEBUG_OSPF_EVENT
)
436 zlog_debug("ospf_intra_add_router: talking about %pFX", &p
);
438 rn
= route_node_get(rt
, (struct prefix
*)&p
);
440 /* Note that we keep all routes to ABRs and ASBRs, not only the best */
441 if (rn
->info
== NULL
)
442 rn
->info
= list_new();
444 route_unlock_node(rn
);
446 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
448 listnode_add(rn
->info
, or);
450 if (IS_DEBUG_OSPF_EVENT
)
451 zlog_debug("ospf_intra_add_router: Stop");
454 /* RFC2328 16.1. (4). For transit network. */
455 void ospf_intra_add_transit(struct route_table
*rt
, struct vertex
*v
,
456 struct ospf_area
*area
)
458 struct route_node
*rn
;
459 struct ospf_route
* or ;
460 struct prefix_ipv4 p
;
461 struct network_lsa
*lsa
;
463 lsa
= (struct network_lsa
*)v
->lsa
;
465 /* If the newly added vertex is a transit network, the routing table
466 entry for the network is located. The entry's Destination ID is
467 the IP network number, which can be obtained by masking the
468 Vertex ID (Link State ID) with its associated subnet mask (found
469 in the body of the associated network-LSA). */
472 p
.prefixlen
= ip_masklen(lsa
->mask
);
475 rn
= route_node_get(rt
, (struct prefix
*)&p
);
477 /* If the routing table entry already exists (i.e., there is already
478 an intra-area route to the destination installed in the routing
479 table), multiple vertices have mapped to the same IP network.
480 For example, this can occur when a new Designated Router is being
481 established. In this case, the current routing table entry
482 should be overwritten if and only if the newly found path is just
483 as short and the current routing table entry's Link State Origin
484 has a smaller Link State ID than the newly added vertex' LSA. */
486 struct ospf_route
*cur_or
;
488 route_unlock_node(rn
);
491 if (v
->distance
> cur_or
->cost
492 || IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
, &lsa
->header
.id
)
496 ospf_route_free(rn
->info
);
499 or = ospf_route_new();
502 or->u
.std
.area_id
= area
->area_id
;
503 or->u
.std
.external_routing
= area
->external_routing
;
504 or->path_type
= OSPF_PATH_INTRA_AREA
;
505 or->cost
= v
->distance
;
506 or->type
= OSPF_DESTINATION_NETWORK
;
507 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
509 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
514 /* RFC2328 16.1. second stage. */
515 void ospf_intra_add_stub(struct route_table
*rt
, struct router_lsa_link
*link
,
516 struct vertex
*v
, struct ospf_area
*area
,
517 int parent_is_root
, int lsa_pos
)
520 struct route_node
*rn
;
521 struct ospf_route
* or ;
522 struct prefix_ipv4 p
;
523 struct router_lsa
*lsa
;
524 struct ospf_interface
*oi
= NULL
;
525 struct ospf_path
*path
;
527 if (IS_DEBUG_OSPF_EVENT
)
528 zlog_debug("ospf_intra_add_stub(): Start");
530 lsa
= (struct router_lsa
*)v
->lsa
;
533 p
.prefix
= link
->link_id
;
534 p
.prefixlen
= ip_masklen(link
->link_data
);
537 if (IS_DEBUG_OSPF_EVENT
)
538 zlog_debug("ospf_intra_add_stub(): processing route to %pFX",
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
)
549 "ospf_intra_add_stub(): calculated cost is %d + %d = %d",
550 v
->distance
, ntohs(link
->m
[0].metric
), cost
);
552 /* PtP links with /32 masks adds host routes to remote, directly
553 * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
554 * Such routes can just be ignored for the sake of tidyness.
556 if (parent_is_root
&& link
->link_data
.s_addr
== 0xffffffff
557 && ospf_if_lookup_by_local_addr(area
->ospf
, NULL
, link
->link_id
)) {
558 if (IS_DEBUG_OSPF_EVENT
)
559 zlog_debug("%s: ignoring host route %pI4/32 to self.",
560 __func__
, &link
->link_id
);
564 rn
= route_node_get(rt
, (struct prefix
*)&p
);
566 /* Lookup current routing table. */
568 struct ospf_route
*cur_or
;
570 route_unlock_node(rn
);
574 if (IS_DEBUG_OSPF_EVENT
)
576 "ospf_intra_add_stub(): another route to the same prefix found with cost %u",
579 /* Compare this distance to the current best cost to the stub
580 network. This is done by looking up the stub network's
581 current routing table entry. If the calculated distance D is
582 larger, go on to examine the next stub network link in the
584 if (cost
> cur_or
->cost
) {
585 if (IS_DEBUG_OSPF_EVENT
)
587 "ospf_intra_add_stub(): old route is better, exit");
591 /* (2) If this step is reached, the stub network's routing table
592 entry must be updated. Calculate the set of next hops that
593 would result from using the stub network link. This
594 calculation is shown in Section 16.1.1; input to this
595 calculation is the destination (the stub network) and the
596 parent vertex (the router vertex). If the distance D is the
597 same as the current routing table cost, simply add this set
598 of next hops to the routing table entry's list of next hops.
599 In this case, the routing table already has a Link State
600 Origin. If this Link State Origin is a router-LSA whose Link
601 State ID is smaller than V's Router ID, reset the Link State
602 Origin to V's router-LSA. */
604 if (cost
== cur_or
->cost
) {
605 if (IS_DEBUG_OSPF_EVENT
)
607 "ospf_intra_add_stub(): routes are equal, merge");
609 ospf_route_copy_nexthops_from_vertex(area
, cur_or
, v
);
611 if (IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
,
614 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
618 /* Otherwise D is smaller than the routing table cost.
619 Overwrite the current routing table entry by setting the
620 routing table entry's cost to D, and by setting the entry's
621 list of next hops to the newly calculated set. Set the
622 routing table entry's Link State Origin to V's router-LSA.
623 Then go on to examine the next stub network link. */
625 if (cost
< cur_or
->cost
) {
626 if (IS_DEBUG_OSPF_EVENT
)
628 "ospf_intra_add_stub(): new route is better, set it");
632 list_delete_all_node(cur_or
->paths
);
634 ospf_route_copy_nexthops_from_vertex(area
, cur_or
, v
);
636 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
641 if (IS_DEBUG_OSPF_EVENT
)
642 zlog_debug("ospf_intra_add_stub(): installing new route");
644 or = ospf_route_new();
647 or->u
.std
.area_id
= area
->area_id
;
648 or->u
.std
.external_routing
= area
->external_routing
;
649 or->path_type
= OSPF_PATH_INTRA_AREA
;
651 or->type
= OSPF_DESTINATION_NETWORK
;
652 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
654 /* Nexthop is depend on connection type. */
655 if (v
!= area
->spf
) {
656 if (IS_DEBUG_OSPF_EVENT
)
658 "ospf_intra_add_stub(): this network is on remote router");
659 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
661 if (IS_DEBUG_OSPF_EVENT
)
663 "ospf_intra_add_stub(): this network is on this router");
666 * Only deal with interface data when we
669 if (!area
->spf_dry_run
)
670 oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
);
672 if (oi
|| area
->spf_dry_run
) {
673 if (IS_DEBUG_OSPF_EVENT
)
675 "ospf_intra_add_stub(): the lsa pos is %d",
678 path
= ospf_path_new();
679 path
->nexthop
.s_addr
= INADDR_ANY
;
682 path
->ifindex
= oi
->ifp
->ifindex
;
683 if (CHECK_FLAG(oi
->connected
->flags
,
684 ZEBRA_IFA_UNNUMBERED
))
685 path
->unnumbered
= 1;
688 listnode_add(or->paths
, path
);
690 if (IS_DEBUG_OSPF_EVENT
)
692 "ospf_intra_add_stub(): where's the interface ?");
698 if (IS_DEBUG_OSPF_EVENT
)
699 zlog_debug("ospf_intra_add_stub(): Stop");
702 static const char *const ospf_path_type_str
[] = {
703 "unknown-type", "intra-area", "inter-area", "type1-external",
707 void ospf_route_table_dump(struct route_table
*rt
)
709 struct route_node
*rn
;
710 struct ospf_route
* or ;
711 struct listnode
*pnode
;
712 struct ospf_path
*path
;
714 zlog_debug("========== OSPF routing table ==========");
715 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
716 if ((or = rn
->info
) != NULL
) {
717 if (or->type
== OSPF_DESTINATION_NETWORK
) {
718 zlog_debug("N %-18pFX %-15pI4 %s %d", &rn
->p
,
720 ospf_path_type_str
[or->path_type
],
722 for (ALL_LIST_ELEMENTS_RO(or->paths
, pnode
,
724 zlog_debug(" -> %pI4",
727 zlog_debug("R %-18pI4 %-15pI4 %s %d",
730 ospf_path_type_str
[or->path_type
],
733 zlog_debug("========================================");
736 /* This is 16.4.1 implementation.
737 o Intra-area paths using non-backbone areas are always the most preferred.
738 o The other paths, intra-area backbone paths and inter-area paths,
739 are of equal preference. */
740 static int ospf_asbr_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
741 struct ospf_route
*r2
)
743 uint8_t r1_type
, r2_type
;
745 r1_type
= r1
->path_type
;
746 r2_type
= r2
->path_type
;
748 /* r1/r2 itself is backbone, and it's Inter-area path. */
749 if (OSPF_IS_AREA_ID_BACKBONE(r1
->u
.std
.area_id
))
750 r1_type
= OSPF_PATH_INTER_AREA
;
751 if (OSPF_IS_AREA_ID_BACKBONE(r2
->u
.std
.area_id
))
752 r2_type
= OSPF_PATH_INTER_AREA
;
754 return (r1_type
- r2_type
);
757 /* Compare two routes.
758 ret < 0 -- r1 is better.
759 ret == 0 -- r1 and r2 are the same.
760 ret > 0 -- r2 is better. */
761 int ospf_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
762 struct ospf_route
*r2
)
766 /* Path types of r1 and r2 are not the same. */
767 if ((ret
= (r1
->path_type
- r2
->path_type
)))
770 if (IS_DEBUG_OSPF_EVENT
)
771 zlog_debug("Route[Compare]: Path types are the same.");
772 /* Path types are the same, compare any cost. */
773 switch (r1
->path_type
) {
774 case OSPF_PATH_INTRA_AREA
:
775 case OSPF_PATH_INTER_AREA
:
777 case OSPF_PATH_TYPE1_EXTERNAL
:
778 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
779 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
785 case OSPF_PATH_TYPE2_EXTERNAL
:
786 if ((ret
= (r1
->u
.ext
.type2_cost
- r2
->u
.ext
.type2_cost
)))
789 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
790 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
798 /* Anyway, compare the costs. */
799 return (r1
->cost
- r2
->cost
);
802 static int ospf_path_exist(struct list
*plist
, struct in_addr nexthop
,
803 struct ospf_interface
*oi
)
805 struct listnode
*node
, *nnode
;
806 struct ospf_path
*path
;
808 for (ALL_LIST_ELEMENTS(plist
, node
, nnode
, path
))
809 if (IPV4_ADDR_SAME(&path
->nexthop
, &nexthop
)
810 && path
->ifindex
== oi
->ifp
->ifindex
)
816 void ospf_route_copy_nexthops_from_vertex(struct ospf_area
*area
,
817 struct ospf_route
*to
,
820 struct listnode
*node
;
821 struct ospf_path
*path
;
822 struct vertex_nexthop
*nexthop
;
823 struct vertex_parent
*vp
;
824 struct ospf_interface
*oi
= NULL
;
828 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
829 nexthop
= vp
->nexthop
;
832 * Only deal with interface data when we
835 if (!area
->spf_dry_run
)
836 oi
= ospf_if_lookup_by_lsa_pos(area
, nexthop
->lsa_pos
);
838 if ((oi
&& !ospf_path_exist(to
->paths
, nexthop
->router
, oi
))
839 || area
->spf_dry_run
) {
840 path
= ospf_path_new();
841 path
->nexthop
= nexthop
->router
;
842 path
->adv_router
= v
->id
;
845 path
->ifindex
= oi
->ifp
->ifindex
;
846 if (CHECK_FLAG(oi
->connected
->flags
,
847 ZEBRA_IFA_UNNUMBERED
))
848 path
->unnumbered
= 1;
851 listnode_add(to
->paths
, path
);
856 struct ospf_path
*ospf_path_lookup(struct list
*plist
, struct ospf_path
*path
)
858 struct listnode
*node
;
859 struct ospf_path
*op
;
861 for (ALL_LIST_ELEMENTS_RO(plist
, node
, op
)) {
862 if (!IPV4_ADDR_SAME(&op
->nexthop
, &path
->nexthop
))
864 if (!IPV4_ADDR_SAME(&op
->adv_router
, &path
->adv_router
))
866 if (op
->ifindex
!= path
->ifindex
)
873 void ospf_route_copy_nexthops(struct ospf_route
*to
, struct list
*from
)
875 struct listnode
*node
, *nnode
;
876 struct ospf_path
*path
;
880 for (ALL_LIST_ELEMENTS(from
, node
, nnode
, path
))
881 /* The same routes are just discarded. */
882 if (!ospf_path_lookup(to
->paths
, path
))
883 listnode_add(to
->paths
, ospf_path_dup(path
));
886 void ospf_route_subst_nexthops(struct ospf_route
*to
, struct list
*from
)
889 list_delete_all_node(to
->paths
);
890 ospf_route_copy_nexthops(to
, from
);
893 void ospf_route_subst(struct route_node
*rn
, struct ospf_route
*new_or
,
894 struct ospf_route
*over
)
897 ospf_route_free(rn
->info
);
899 ospf_route_copy_nexthops(new_or
, over
->paths
);
901 route_unlock_node(rn
);
904 void ospf_route_add(struct route_table
*rt
, struct prefix_ipv4
*p
,
905 struct ospf_route
*new_or
, struct ospf_route
*over
)
907 struct route_node
*rn
;
909 rn
= route_node_get(rt
, (struct prefix
*)p
);
911 ospf_route_copy_nexthops(new_or
, over
->paths
);
914 if (IS_DEBUG_OSPF_EVENT
)
915 zlog_debug("ospf_route_add(): something's wrong !");
916 route_unlock_node(rn
);
923 void ospf_prune_unreachable_networks(struct route_table
*rt
)
925 struct route_node
*rn
, *next
;
926 struct ospf_route
* or ;
928 if (IS_DEBUG_OSPF_EVENT
)
929 zlog_debug("Pruning unreachable networks");
931 for (rn
= route_top(rt
); rn
; rn
= next
) {
932 next
= route_next(rn
);
933 if (rn
->info
!= NULL
) {
935 if (listcount(or->paths
) == 0) {
936 if (IS_DEBUG_OSPF_EVENT
)
937 zlog_debug("Pruning route to %pFX",
942 route_unlock_node(rn
);
948 void ospf_prune_unreachable_routers(struct route_table
*rtrs
)
950 struct route_node
*rn
, *next
;
951 struct ospf_route
* or ;
952 struct listnode
*node
, *nnode
;
955 if (IS_DEBUG_OSPF_EVENT
)
956 zlog_debug("Pruning unreachable routers");
958 for (rn
= route_top(rtrs
); rn
; rn
= next
) {
959 next
= route_next(rn
);
960 if ((paths
= rn
->info
) == NULL
)
963 for (ALL_LIST_ELEMENTS(paths
, node
, nnode
, or)) {
964 if (listcount(or->paths
) == 0) {
965 if (IS_DEBUG_OSPF_EVENT
) {
966 zlog_debug("Pruning route to rtr %pI4",
973 listnode_delete(paths
, or);
978 if (listcount(paths
) == 0) {
979 if (IS_DEBUG_OSPF_EVENT
)
980 zlog_debug("Pruning router node %pI4",
985 route_unlock_node(rn
);
990 int ospf_add_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
991 struct ospf_area
*area
, struct prefix_ipv4
*p
)
993 struct route_node
*rn
;
994 struct ospf_route
* or, *new_or
;
996 rn
= route_node_get(rt
, (struct prefix
*)p
);
999 if (IS_DEBUG_OSPF_EVENT
)
1001 "ospf_add_discard_route(): router installation error");
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
)
1014 "ospf_add_discard_route(): an intra-area route exists");
1018 if (or->type
== OSPF_DESTINATION_DISCARD
) {
1019 if (IS_DEBUG_OSPF_EVENT
)
1021 "ospf_add_discard_route(): discard entry already installed");
1025 ospf_route_free(rn
->info
);
1028 if (IS_DEBUG_OSPF_EVENT
)
1029 zlog_debug("ospf_add_discard_route(): adding %pFX", p
);
1031 new_or
= ospf_route_new();
1032 new_or
->type
= OSPF_DESTINATION_DISCARD
;
1033 new_or
->id
.s_addr
= INADDR_ANY
;
1035 new_or
->u
.std
.area_id
= area
->area_id
;
1036 new_or
->u
.std
.external_routing
= area
->external_routing
;
1037 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
1040 ospf_zebra_add_discard(ospf
, p
);
1045 void ospf_delete_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
1046 struct prefix_ipv4
*p
)
1048 struct route_node
*rn
;
1049 struct ospf_route
* or ;
1051 if (IS_DEBUG_OSPF_EVENT
)
1052 zlog_debug("ospf_delete_discard_route(): deleting %pFX", p
);
1054 rn
= route_node_lookup(rt
, (struct prefix
*)p
);
1057 if (IS_DEBUG_OSPF_EVENT
)
1059 "ospf_delete_discard_route(): no route found");
1065 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
1066 if (IS_DEBUG_OSPF_EVENT
)
1068 "ospf_delete_discard_route(): an intra-area route exists");
1072 if (or->type
!= OSPF_DESTINATION_DISCARD
) {
1073 if (IS_DEBUG_OSPF_EVENT
)
1075 "ospf_delete_discard_route(): not a discard entry");
1079 /* free the route entry and the route node */
1080 ospf_route_free(rn
->info
);
1083 route_unlock_node(rn
);
1084 route_unlock_node(rn
);
1086 /* remove the discard entry from the rib */
1087 ospf_zebra_delete_discard(ospf
, p
);