]>
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 struct ospf_route
*ospf_route_new(void)
44 struct ospf_route
*new;
46 new = XCALLOC(MTYPE_OSPF_ROUTE
, sizeof(struct ospf_route
));
48 new->paths
= list_new();
49 new->paths
->del
= (void (*)(void *))ospf_path_free
;
54 void ospf_route_free(struct ospf_route
*or)
57 list_delete(& or->paths
);
59 XFREE(MTYPE_OSPF_ROUTE
, or);
62 struct ospf_path
*ospf_path_new(void)
64 struct ospf_path
*new;
66 new = XCALLOC(MTYPE_OSPF_PATH
, sizeof(struct ospf_path
));
71 static struct ospf_path
*ospf_path_dup(struct ospf_path
*path
)
73 struct ospf_path
*new;
75 new = ospf_path_new();
76 memcpy(new, path
, sizeof(struct ospf_path
));
81 void ospf_path_free(struct ospf_path
*op
)
83 XFREE(MTYPE_OSPF_PATH
, op
);
86 void ospf_route_delete(struct ospf
*ospf
, struct route_table
*rt
)
88 struct route_node
*rn
;
89 struct ospf_route
* or ;
91 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
92 if ((or = rn
->info
) != NULL
) {
93 if (or->type
== OSPF_DESTINATION_NETWORK
)
95 ospf
, (struct prefix_ipv4
*)&rn
->p
, or);
96 else if (or->type
== OSPF_DESTINATION_DISCARD
)
97 ospf_zebra_delete_discard(
98 ospf
, (struct prefix_ipv4
*)&rn
->p
);
102 void ospf_route_table_free(struct route_table
*rt
)
104 struct route_node
*rn
;
105 struct ospf_route
* or ;
107 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
108 if ((or = rn
->info
) != NULL
) {
112 route_unlock_node(rn
);
115 route_table_finish(rt
);
118 /* If a prefix exists in the new routing table, then return 1,
119 otherwise return 0. Since the ZEBRA-RIB does an implicit
120 withdraw, it is not necessary to send a delete, an add later
121 will act like an implicit delete. */
122 static int ospf_route_exist_new_table(struct route_table
*rt
,
123 struct prefix_ipv4
*prefix
)
125 struct route_node
*rn
;
130 rn
= route_node_lookup(rt
, (struct prefix
*)prefix
);
134 route_unlock_node(rn
);
143 /* If a prefix and a nexthop match any route in the routing table,
144 then return 1, otherwise return 0. */
145 int ospf_route_match_same(struct route_table
*rt
, struct prefix_ipv4
*prefix
,
146 struct ospf_route
*newor
)
148 struct route_node
*rn
;
149 struct ospf_route
* or ;
150 struct ospf_path
*op
;
151 struct ospf_path
*newop
;
158 rn
= route_node_lookup(rt
, (struct prefix
*)prefix
);
159 if (!rn
|| !rn
->info
)
162 route_unlock_node(rn
);
165 if (or->type
== newor
->type
&& or->cost
== newor
->cost
) {
166 if (or->type
== OSPF_DESTINATION_NETWORK
) {
167 if (or->paths
->count
!= newor
->paths
->count
)
170 /* Check each path. */
171 for (n1
= listhead(or->paths
),
172 n2
= listhead(newor
->paths
);
173 n1
&& n2
; n1
= listnextnode_unchecked(n1
),
174 n2
= listnextnode_unchecked(n2
)) {
175 op
= listgetdata(n1
);
176 newop
= listgetdata(n2
);
178 if (!IPV4_ADDR_SAME(&op
->nexthop
,
181 if (op
->ifindex
!= newop
->ifindex
)
185 } else if (prefix_same(&rn
->p
, (struct prefix
*)prefix
))
191 /* delete routes generated from AS-External routes if there is a inter/intra
194 static void ospf_route_delete_same_ext(struct ospf
*ospf
,
195 struct route_table
*external_routes
,
196 struct route_table
*routes
)
198 struct route_node
*rn
, *ext_rn
;
200 if ((external_routes
== NULL
) || (routes
== NULL
))
203 /* Remove deleted routes */
204 for (rn
= route_top(routes
); rn
; rn
= route_next(rn
)) {
205 if (rn
&& rn
->info
) {
206 struct prefix_ipv4
*p
= (struct prefix_ipv4
*)(&rn
->p
);
207 if ((ext_rn
= route_node_lookup(external_routes
,
208 (struct prefix
*)p
))) {
210 ospf_zebra_delete(ospf
, p
,
212 ospf_route_free(ext_rn
->info
);
215 route_unlock_node(ext_rn
);
221 /* rt: Old, cmprt: New */
222 static void ospf_route_delete_uniq(struct ospf
*ospf
, struct route_table
*rt
,
223 struct route_table
*cmprt
)
225 struct route_node
*rn
;
226 struct ospf_route
* or ;
228 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
229 if ((or = rn
->info
) != NULL
)
230 if (or->path_type
== OSPF_PATH_INTRA_AREA
||
231 or->path_type
== OSPF_PATH_INTER_AREA
) {
232 if (or->type
== OSPF_DESTINATION_NETWORK
) {
233 if (!ospf_route_exist_new_table(
235 (struct prefix_ipv4
*)&rn
242 } else if (or->type
== OSPF_DESTINATION_DISCARD
)
243 if (!ospf_route_exist_new_table(
245 (struct prefix_ipv4
*)&rn
247 ospf_zebra_delete_discard(
254 /* Install routes to table. */
255 void ospf_route_install(struct ospf
*ospf
, struct route_table
*rt
)
257 struct route_node
*rn
;
258 struct ospf_route
* or ;
260 /* rt contains new routing table, new_table contains an old one.
263 ospf_route_table_free(ospf
->old_table
);
265 ospf
->old_table
= ospf
->new_table
;
266 ospf
->new_table
= rt
;
268 /* Delete old routes. */
270 ospf_route_delete_uniq(ospf
, ospf
->old_table
, rt
);
271 if (ospf
->old_external_route
)
272 ospf_route_delete_same_ext(ospf
, ospf
->old_external_route
, rt
);
274 /* Install new routes. */
275 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
276 if ((or = rn
->info
) != NULL
) {
277 if (or->type
== OSPF_DESTINATION_NETWORK
) {
278 if (!ospf_route_match_same(
280 (struct prefix_ipv4
*)&rn
->p
, or))
283 (struct prefix_ipv4
*)&rn
->p
,
285 } else if (or->type
== OSPF_DESTINATION_DISCARD
)
286 if (!ospf_route_match_same(
288 (struct prefix_ipv4
*)&rn
->p
, or))
289 ospf_zebra_add_discard(
291 (struct prefix_ipv4
*)&rn
->p
);
295 /* RFC2328 16.1. (4). For "router". */
296 void ospf_intra_add_router(struct route_table
*rt
, struct vertex
*v
,
297 struct ospf_area
*area
)
299 struct route_node
*rn
;
300 struct ospf_route
* or ;
301 struct prefix_ipv4 p
;
302 struct router_lsa
*lsa
;
304 if (IS_DEBUG_OSPF_EVENT
)
305 zlog_debug("ospf_intra_add_router: Start");
307 lsa
= (struct router_lsa
*)v
->lsa
;
309 if (IS_DEBUG_OSPF_EVENT
)
310 zlog_debug("ospf_intra_add_router: LS ID: %pI4",
313 if (!OSPF_IS_AREA_BACKBONE(area
))
314 ospf_vl_up_check(area
, lsa
->header
.id
, v
);
316 if (!CHECK_FLAG(lsa
->flags
, ROUTER_LSA_SHORTCUT
))
317 area
->shortcut_capability
= 0;
319 /* If the newly added vertex is an area border router or AS boundary
320 router, a routing table entry is added whose destination type is
322 if (!IS_ROUTER_LSA_BORDER(lsa
) && !IS_ROUTER_LSA_EXTERNAL(lsa
)) {
323 if (IS_DEBUG_OSPF_EVENT
)
325 "ospf_intra_add_router: this router is neither ASBR nor ABR, skipping it");
329 /* Update ABR and ASBR count in this area. */
330 if (IS_ROUTER_LSA_BORDER(lsa
))
332 if (IS_ROUTER_LSA_EXTERNAL(lsa
))
335 /* The Options field found in the associated router-LSA is copied
336 into the routing table entry's Optional capabilities field. Call
337 the newly added vertex Router X. */
338 or = ospf_route_new();
341 or->u
.std
.area_id
= area
->area_id
;
342 or->u
.std
.external_routing
= area
->external_routing
;
343 or->path_type
= OSPF_PATH_INTRA_AREA
;
344 or->cost
= v
->distance
;
345 or->type
= OSPF_DESTINATION_ROUTER
;
346 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
347 or->u
.std
.options
= lsa
->header
.options
;
348 or->u
.std
.flags
= lsa
->flags
;
350 /* If Router X is the endpoint of one of the calculating router's
351 virtual links, and the virtual link uses Area A as Transit area:
352 the virtual link is declared up, the IP address of the virtual
353 interface is set to the IP address of the outgoing interface
354 calculated above for Router X, and the virtual neighbor's IP
355 address is set to Router X's interface address (contained in
356 Router X's router-LSA) that points back to the root of the
357 shortest- path tree; equivalently, this is the interface that
358 points back to Router X's parent vertex on the shortest-path tree
359 (similar to the calculation in Section 16.1.1). */
363 p
.prefixlen
= IPV4_MAX_BITLEN
;
366 if (IS_DEBUG_OSPF_EVENT
)
367 zlog_debug("ospf_intra_add_router: talking about %pFX", &p
);
369 rn
= route_node_get(rt
, (struct prefix
*)&p
);
371 /* Note that we keep all routes to ABRs and ASBRs, not only the best */
372 if (rn
->info
== NULL
)
373 rn
->info
= list_new();
375 route_unlock_node(rn
);
377 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
379 listnode_add(rn
->info
, or);
381 if (IS_DEBUG_OSPF_EVENT
)
382 zlog_debug("ospf_intra_add_router: Stop");
385 /* RFC2328 16.1. (4). For transit network. */
386 void ospf_intra_add_transit(struct route_table
*rt
, struct vertex
*v
,
387 struct ospf_area
*area
)
389 struct route_node
*rn
;
390 struct ospf_route
* or ;
391 struct prefix_ipv4 p
;
392 struct network_lsa
*lsa
;
394 lsa
= (struct network_lsa
*)v
->lsa
;
396 /* If the newly added vertex is a transit network, the routing table
397 entry for the network is located. The entry's Destination ID is
398 the IP network number, which can be obtained by masking the
399 Vertex ID (Link State ID) with its associated subnet mask (found
400 in the body of the associated network-LSA). */
403 p
.prefixlen
= ip_masklen(lsa
->mask
);
406 rn
= route_node_get(rt
, (struct prefix
*)&p
);
408 /* If the routing table entry already exists (i.e., there is already
409 an intra-area route to the destination installed in the routing
410 table), multiple vertices have mapped to the same IP network.
411 For example, this can occur when a new Designated Router is being
412 established. In this case, the current routing table entry
413 should be overwritten if and only if the newly found path is just
414 as short and the current routing table entry's Link State Origin
415 has a smaller Link State ID than the newly added vertex' LSA. */
417 struct ospf_route
*cur_or
;
419 route_unlock_node(rn
);
422 if (v
->distance
> cur_or
->cost
423 || IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
, &lsa
->header
.id
)
427 ospf_route_free(rn
->info
);
430 or = ospf_route_new();
433 or->u
.std
.area_id
= area
->area_id
;
434 or->u
.std
.external_routing
= area
->external_routing
;
435 or->path_type
= OSPF_PATH_INTRA_AREA
;
436 or->cost
= v
->distance
;
437 or->type
= OSPF_DESTINATION_NETWORK
;
438 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
440 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
445 /* RFC2328 16.1. second stage. */
446 void ospf_intra_add_stub(struct route_table
*rt
, struct router_lsa_link
*link
,
447 struct vertex
*v
, struct ospf_area
*area
,
448 int parent_is_root
, int lsa_pos
)
451 struct route_node
*rn
;
452 struct ospf_route
* or ;
453 struct prefix_ipv4 p
;
454 struct router_lsa
*lsa
;
455 struct ospf_interface
*oi
= NULL
;
456 struct ospf_path
*path
;
458 if (IS_DEBUG_OSPF_EVENT
)
459 zlog_debug("ospf_intra_add_stub(): Start");
461 lsa
= (struct router_lsa
*)v
->lsa
;
464 p
.prefix
= link
->link_id
;
465 p
.prefixlen
= ip_masklen(link
->link_data
);
468 if (IS_DEBUG_OSPF_EVENT
)
469 zlog_debug("ospf_intra_add_stub(): processing route to %pFX",
472 /* (1) Calculate the distance D of stub network from the root. D is
473 equal to the distance from the root to the router vertex
474 (calculated in stage 1), plus the stub network link's advertised
476 cost
= v
->distance
+ ntohs(link
->m
[0].metric
);
478 if (IS_DEBUG_OSPF_EVENT
)
480 "ospf_intra_add_stub(): calculated cost is %d + %d = %d",
481 v
->distance
, ntohs(link
->m
[0].metric
), cost
);
483 /* PtP links with /32 masks adds host routes to remote, directly
484 * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
485 * Such routes can just be ignored for the sake of tidyness.
487 if (parent_is_root
&& link
->link_data
.s_addr
== 0xffffffff
488 && ospf_if_lookup_by_local_addr(area
->ospf
, NULL
, link
->link_id
)) {
489 if (IS_DEBUG_OSPF_EVENT
)
490 zlog_debug("%s: ignoring host route %pI4/32 to self.",
491 __func__
, &link
->link_id
);
495 rn
= route_node_get(rt
, (struct prefix
*)&p
);
497 /* Lookup current routing table. */
499 struct ospf_route
*cur_or
;
501 route_unlock_node(rn
);
505 if (IS_DEBUG_OSPF_EVENT
)
507 "ospf_intra_add_stub(): another route to the same prefix found with cost %u",
510 /* Compare this distance to the current best cost to the stub
511 network. This is done by looking up the stub network's
512 current routing table entry. If the calculated distance D is
513 larger, go on to examine the next stub network link in the
515 if (cost
> cur_or
->cost
) {
516 if (IS_DEBUG_OSPF_EVENT
)
518 "ospf_intra_add_stub(): old route is better, exit");
522 /* (2) If this step is reached, the stub network's routing table
523 entry must be updated. Calculate the set of next hops that
524 would result from using the stub network link. This
525 calculation is shown in Section 16.1.1; input to this
526 calculation is the destination (the stub network) and the
527 parent vertex (the router vertex). If the distance D is the
528 same as the current routing table cost, simply add this set
529 of next hops to the routing table entry's list of next hops.
530 In this case, the routing table already has a Link State
531 Origin. If this Link State Origin is a router-LSA whose Link
532 State ID is smaller than V's Router ID, reset the Link State
533 Origin to V's router-LSA. */
535 if (cost
== cur_or
->cost
) {
536 if (IS_DEBUG_OSPF_EVENT
)
538 "ospf_intra_add_stub(): routes are equal, merge");
540 ospf_route_copy_nexthops_from_vertex(area
, cur_or
, v
);
542 if (IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
,
545 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
549 /* Otherwise D is smaller than the routing table cost.
550 Overwrite the current routing table entry by setting the
551 routing table entry's cost to D, and by setting the entry's
552 list of next hops to the newly calculated set. Set the
553 routing table entry's Link State Origin to V's router-LSA.
554 Then go on to examine the next stub network link. */
556 if (cost
< cur_or
->cost
) {
557 if (IS_DEBUG_OSPF_EVENT
)
559 "ospf_intra_add_stub(): new route is better, set it");
563 list_delete_all_node(cur_or
->paths
);
565 ospf_route_copy_nexthops_from_vertex(area
, cur_or
, v
);
567 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
572 if (IS_DEBUG_OSPF_EVENT
)
573 zlog_debug("ospf_intra_add_stub(): installing new route");
575 or = ospf_route_new();
578 or->u
.std
.area_id
= area
->area_id
;
579 or->u
.std
.external_routing
= area
->external_routing
;
580 or->path_type
= OSPF_PATH_INTRA_AREA
;
582 or->type
= OSPF_DESTINATION_NETWORK
;
583 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
585 /* Nexthop is depend on connection type. */
586 if (v
!= area
->spf
) {
587 if (IS_DEBUG_OSPF_EVENT
)
589 "ospf_intra_add_stub(): this network is on remote router");
590 ospf_route_copy_nexthops_from_vertex(area
, or, v
);
592 if (IS_DEBUG_OSPF_EVENT
)
594 "ospf_intra_add_stub(): this network is on this router");
597 * Only deal with interface data when we
600 if (!area
->spf_dry_run
)
601 oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
);
603 if (oi
|| area
->spf_dry_run
) {
604 if (IS_DEBUG_OSPF_EVENT
)
606 "ospf_intra_add_stub(): the lsa pos is %d",
609 path
= ospf_path_new();
610 path
->nexthop
.s_addr
= INADDR_ANY
;
613 path
->ifindex
= oi
->ifp
->ifindex
;
614 if (CHECK_FLAG(oi
->connected
->flags
,
615 ZEBRA_IFA_UNNUMBERED
))
616 path
->unnumbered
= 1;
619 listnode_add(or->paths
, path
);
621 if (IS_DEBUG_OSPF_EVENT
)
623 "ospf_intra_add_stub(): where's the interface ?");
629 if (IS_DEBUG_OSPF_EVENT
)
630 zlog_debug("ospf_intra_add_stub(): Stop");
633 static const char *const ospf_path_type_str
[] = {
634 "unknown-type", "intra-area", "inter-area", "type1-external",
638 void ospf_route_table_dump(struct route_table
*rt
)
640 struct route_node
*rn
;
641 struct ospf_route
* or ;
642 struct listnode
*pnode
;
643 struct ospf_path
*path
;
645 zlog_debug("========== OSPF routing table ==========");
646 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
647 if ((or = rn
->info
) != NULL
) {
648 if (or->type
== OSPF_DESTINATION_NETWORK
) {
649 zlog_debug("N %-18pFX %-15pI4 %s %d", &rn
->p
,
651 ospf_path_type_str
[or->path_type
],
653 for (ALL_LIST_ELEMENTS_RO(or->paths
, pnode
,
655 zlog_debug(" -> %pI4",
658 zlog_debug("R %-18pI4 %-15pI4 %s %d",
661 ospf_path_type_str
[or->path_type
],
664 zlog_debug("========================================");
667 void ospf_route_table_print(struct vty
*vty
, struct route_table
*rt
)
669 struct route_node
*rn
;
670 struct ospf_route
* or ;
671 struct listnode
*pnode
;
672 struct ospf_path
*path
;
674 vty_out(vty
, "========== OSPF routing table ==========\n");
675 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
676 if ((or = rn
->info
) != NULL
) {
677 if (or->type
== OSPF_DESTINATION_NETWORK
) {
678 vty_out(vty
, "N %-18pFX %-15pI4 %s %d\n",
679 &rn
->p
, & or->u
.std
.area_id
,
680 ospf_path_type_str
[or->path_type
],
682 for (ALL_LIST_ELEMENTS_RO(or->paths
, pnode
,
684 if (path
->nexthop
.s_addr
!= 0)
685 vty_out(vty
, " -> %pI4\n",
688 vty_out(vty
, " -> %s\n",
689 "directly connected");
691 vty_out(vty
, "R %-18pI4 %-15pI4 %s %d\n",
692 &rn
->p
.u
.prefix4
, & or->u
.std
.area_id
,
693 ospf_path_type_str
[or->path_type
],
696 vty_out(vty
, "========================================\n");
699 /* This is 16.4.1 implementation.
700 o Intra-area paths using non-backbone areas are always the most preferred.
701 o The other paths, intra-area backbone paths and inter-area paths,
702 are of equal preference. */
703 static int ospf_asbr_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
704 struct ospf_route
*r2
)
706 uint8_t r1_type
, r2_type
;
708 r1_type
= r1
->path_type
;
709 r2_type
= r2
->path_type
;
711 /* r1/r2 itself is backbone, and it's Inter-area path. */
712 if (OSPF_IS_AREA_ID_BACKBONE(r1
->u
.std
.area_id
))
713 r1_type
= OSPF_PATH_INTER_AREA
;
714 if (OSPF_IS_AREA_ID_BACKBONE(r2
->u
.std
.area_id
))
715 r2_type
= OSPF_PATH_INTER_AREA
;
717 return (r1_type
- r2_type
);
720 /* Compare two routes.
721 ret < 0 -- r1 is better.
722 ret == 0 -- r1 and r2 are the same.
723 ret > 0 -- r2 is better. */
724 int ospf_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
725 struct ospf_route
*r2
)
729 /* Path types of r1 and r2 are not the same. */
730 if ((ret
= (r1
->path_type
- r2
->path_type
)))
733 if (IS_DEBUG_OSPF_EVENT
)
734 zlog_debug("Route[Compare]: Path types are the same.");
735 /* Path types are the same, compare any cost. */
736 switch (r1
->path_type
) {
737 case OSPF_PATH_INTRA_AREA
:
738 case OSPF_PATH_INTER_AREA
:
740 case OSPF_PATH_TYPE1_EXTERNAL
:
741 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
742 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
748 case OSPF_PATH_TYPE2_EXTERNAL
:
749 if ((ret
= (r1
->u
.ext
.type2_cost
- r2
->u
.ext
.type2_cost
)))
752 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
753 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
761 /* Anyway, compare the costs. */
762 return (r1
->cost
- r2
->cost
);
765 static int ospf_path_exist(struct list
*plist
, struct in_addr nexthop
,
766 struct ospf_interface
*oi
)
768 struct listnode
*node
, *nnode
;
769 struct ospf_path
*path
;
771 for (ALL_LIST_ELEMENTS(plist
, node
, nnode
, path
))
772 if (IPV4_ADDR_SAME(&path
->nexthop
, &nexthop
)
773 && path
->ifindex
== oi
->ifp
->ifindex
)
779 void ospf_route_copy_nexthops_from_vertex(struct ospf_area
*area
,
780 struct ospf_route
*to
,
783 struct listnode
*node
;
784 struct ospf_path
*path
;
785 struct vertex_nexthop
*nexthop
;
786 struct vertex_parent
*vp
;
787 struct ospf_interface
*oi
= NULL
;
791 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
792 nexthop
= vp
->nexthop
;
795 * Only deal with interface data when we
798 if (!area
->spf_dry_run
)
799 oi
= ospf_if_lookup_by_lsa_pos(area
, nexthop
->lsa_pos
);
801 if ((oi
&& !ospf_path_exist(to
->paths
, nexthop
->router
, oi
))
802 || area
->spf_dry_run
) {
803 path
= ospf_path_new();
804 path
->nexthop
= nexthop
->router
;
807 path
->ifindex
= oi
->ifp
->ifindex
;
808 if (CHECK_FLAG(oi
->connected
->flags
,
809 ZEBRA_IFA_UNNUMBERED
))
810 path
->unnumbered
= 1;
813 listnode_add(to
->paths
, path
);
818 struct ospf_path
*ospf_path_lookup(struct list
*plist
, struct ospf_path
*path
)
820 struct listnode
*node
;
821 struct ospf_path
*op
;
823 for (ALL_LIST_ELEMENTS_RO(plist
, node
, op
)) {
824 if (!IPV4_ADDR_SAME(&op
->nexthop
, &path
->nexthop
))
826 if (!IPV4_ADDR_SAME(&op
->adv_router
, &path
->adv_router
))
828 if (op
->ifindex
!= path
->ifindex
)
835 void ospf_route_copy_nexthops(struct ospf_route
*to
, struct list
*from
)
837 struct listnode
*node
, *nnode
;
838 struct ospf_path
*path
;
842 for (ALL_LIST_ELEMENTS(from
, node
, nnode
, path
))
843 /* The same routes are just discarded. */
844 if (!ospf_path_lookup(to
->paths
, path
))
845 listnode_add(to
->paths
, ospf_path_dup(path
));
848 void ospf_route_subst_nexthops(struct ospf_route
*to
, struct list
*from
)
851 list_delete_all_node(to
->paths
);
852 ospf_route_copy_nexthops(to
, from
);
855 void ospf_route_subst(struct route_node
*rn
, struct ospf_route
*new_or
,
856 struct ospf_route
*over
)
859 ospf_route_free(rn
->info
);
861 ospf_route_copy_nexthops(new_or
, over
->paths
);
863 route_unlock_node(rn
);
866 void ospf_route_add(struct route_table
*rt
, struct prefix_ipv4
*p
,
867 struct ospf_route
*new_or
, struct ospf_route
*over
)
869 struct route_node
*rn
;
871 rn
= route_node_get(rt
, (struct prefix
*)p
);
873 ospf_route_copy_nexthops(new_or
, over
->paths
);
876 if (IS_DEBUG_OSPF_EVENT
)
877 zlog_debug("ospf_route_add(): something's wrong !");
878 route_unlock_node(rn
);
885 void ospf_prune_unreachable_networks(struct route_table
*rt
)
887 struct route_node
*rn
, *next
;
888 struct ospf_route
* or ;
890 if (IS_DEBUG_OSPF_EVENT
)
891 zlog_debug("Pruning unreachable networks");
893 for (rn
= route_top(rt
); rn
; rn
= next
) {
894 next
= route_next(rn
);
895 if (rn
->info
!= NULL
) {
897 if (listcount(or->paths
) == 0) {
898 if (IS_DEBUG_OSPF_EVENT
)
899 zlog_debug("Pruning route to %pFX",
904 route_unlock_node(rn
);
910 void ospf_prune_unreachable_routers(struct route_table
*rtrs
)
912 struct route_node
*rn
, *next
;
913 struct ospf_route
* or ;
914 struct listnode
*node
, *nnode
;
917 if (IS_DEBUG_OSPF_EVENT
)
918 zlog_debug("Pruning unreachable routers");
920 for (rn
= route_top(rtrs
); rn
; rn
= next
) {
921 next
= route_next(rn
);
922 if ((paths
= rn
->info
) == NULL
)
925 for (ALL_LIST_ELEMENTS(paths
, node
, nnode
, or)) {
926 if (listcount(or->paths
) == 0) {
927 if (IS_DEBUG_OSPF_EVENT
) {
928 zlog_debug("Pruning route to rtr %pI4",
935 listnode_delete(paths
, or);
940 if (listcount(paths
) == 0) {
941 if (IS_DEBUG_OSPF_EVENT
)
942 zlog_debug("Pruning router node %pI4",
947 route_unlock_node(rn
);
952 int ospf_add_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
953 struct ospf_area
*area
, struct prefix_ipv4
*p
)
955 struct route_node
*rn
;
956 struct ospf_route
* or, *new_or
;
958 rn
= route_node_get(rt
, (struct prefix
*)p
);
961 if (IS_DEBUG_OSPF_EVENT
)
963 "ospf_add_discard_route(): router installation error");
967 if (rn
->info
) /* If the route to the same destination is found */
969 route_unlock_node(rn
);
973 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
974 if (IS_DEBUG_OSPF_EVENT
)
976 "ospf_add_discard_route(): an intra-area route exists");
980 if (or->type
== OSPF_DESTINATION_DISCARD
) {
981 if (IS_DEBUG_OSPF_EVENT
)
983 "ospf_add_discard_route(): discard entry already installed");
987 ospf_route_free(rn
->info
);
990 if (IS_DEBUG_OSPF_EVENT
)
991 zlog_debug("ospf_add_discard_route(): adding %pFX", p
);
993 new_or
= ospf_route_new();
994 new_or
->type
= OSPF_DESTINATION_DISCARD
;
995 new_or
->id
.s_addr
= INADDR_ANY
;
997 new_or
->u
.std
.area_id
= area
->area_id
;
998 new_or
->u
.std
.external_routing
= area
->external_routing
;
999 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
1002 ospf_zebra_add_discard(ospf
, p
);
1007 void ospf_delete_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
1008 struct prefix_ipv4
*p
)
1010 struct route_node
*rn
;
1011 struct ospf_route
* or ;
1013 if (IS_DEBUG_OSPF_EVENT
)
1014 zlog_debug("ospf_delete_discard_route(): deleting %pFX", p
);
1016 rn
= route_node_lookup(rt
, (struct prefix
*)p
);
1019 if (IS_DEBUG_OSPF_EVENT
)
1021 "ospf_delete_discard_route(): no route found");
1027 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
1028 if (IS_DEBUG_OSPF_EVENT
)
1030 "ospf_delete_discard_route(): an intra-area route exists");
1034 if (or->type
!= OSPF_DESTINATION_DISCARD
) {
1035 if (IS_DEBUG_OSPF_EVENT
)
1037 "ospf_delete_discard_route(): not a discard entry");
1041 /* free the route entry and the route node */
1042 ospf_route_free(rn
->info
);
1045 route_unlock_node(rn
);
1046 route_unlock_node(rn
);
1048 /* remove the discard entry from the rib */
1049 ospf_zebra_delete_discard(ospf
, p
);