]>
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: %s",
311 inet_ntoa(lsa
->header
.id
));
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: "
326 "this router is neither ASBR nor ABR, skipping it");
330 /* Update ABR and ASBR count in this area. */
331 if (IS_ROUTER_LSA_BORDER(lsa
))
333 if (IS_ROUTER_LSA_EXTERNAL(lsa
))
336 /* The Options field found in the associated router-LSA is copied
337 into the routing table entry's Optional capabilities field. Call
338 the newly added vertex Router X. */
339 or = ospf_route_new();
342 or->u
.std
.area_id
= area
->area_id
;
343 or->u
.std
.external_routing
= area
->external_routing
;
344 or->path_type
= OSPF_PATH_INTRA_AREA
;
345 or->cost
= v
->distance
;
346 or->type
= OSPF_DESTINATION_ROUTER
;
347 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
348 or->u
.std
.options
= lsa
->header
.options
;
349 or->u
.std
.flags
= lsa
->flags
;
351 /* If Router X is the endpoint of one of the calculating router's
352 virtual links, and the virtual link uses Area A as Transit area:
353 the virtual link is declared up, the IP address of the virtual
354 interface is set to the IP address of the outgoing interface
355 calculated above for Router X, and the virtual neighbor's IP
356 address is set to Router X's interface address (contained in
357 Router X's router-LSA) that points back to the root of the
358 shortest- path tree; equivalently, this is the interface that
359 points back to Router X's parent vertex on the shortest-path tree
360 (similar to the calculation in Section 16.1.1). */
364 p
.prefixlen
= IPV4_MAX_BITLEN
;
367 if (IS_DEBUG_OSPF_EVENT
)
368 zlog_debug("ospf_intra_add_router: talking about %s/%d",
369 inet_ntoa(p
.prefix
), p
.prefixlen
);
371 rn
= route_node_get(rt
, (struct prefix
*)&p
);
373 /* Note that we keep all routes to ABRs and ASBRs, not only the best */
374 if (rn
->info
== NULL
)
375 rn
->info
= list_new();
377 route_unlock_node(rn
);
379 ospf_route_copy_nexthops_from_vertex(or, v
);
381 listnode_add(rn
->info
, or);
383 if (IS_DEBUG_OSPF_EVENT
)
384 zlog_debug("ospf_intra_add_router: Stop");
387 /* RFC2328 16.1. (4). For transit network. */
388 void ospf_intra_add_transit(struct route_table
*rt
, struct vertex
*v
,
389 struct ospf_area
*area
)
391 struct route_node
*rn
;
392 struct ospf_route
* or ;
393 struct prefix_ipv4 p
;
394 struct network_lsa
*lsa
;
396 lsa
= (struct network_lsa
*)v
->lsa
;
398 /* If the newly added vertex is a transit network, the routing table
399 entry for the network is located. The entry's Destination ID is
400 the IP network number, which can be obtained by masking the
401 Vertex ID (Link State ID) with its associated subnet mask (found
402 in the body of the associated network-LSA). */
405 p
.prefixlen
= ip_masklen(lsa
->mask
);
408 rn
= route_node_get(rt
, (struct prefix
*)&p
);
410 /* If the routing table entry already exists (i.e., there is already
411 an intra-area route to the destination installed in the routing
412 table), multiple vertices have mapped to the same IP network.
413 For example, this can occur when a new Designated Router is being
414 established. In this case, the current routing table entry
415 should be overwritten if and only if the newly found path is just
416 as short and the current routing table entry's Link State Origin
417 has a smaller Link State ID than the newly added vertex' LSA. */
419 struct ospf_route
*cur_or
;
421 route_unlock_node(rn
);
424 if (v
->distance
> cur_or
->cost
425 || IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
, &lsa
->header
.id
)
429 ospf_route_free(rn
->info
);
432 or = ospf_route_new();
435 or->u
.std
.area_id
= area
->area_id
;
436 or->u
.std
.external_routing
= area
->external_routing
;
437 or->path_type
= OSPF_PATH_INTRA_AREA
;
438 or->cost
= v
->distance
;
439 or->type
= OSPF_DESTINATION_NETWORK
;
440 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
442 ospf_route_copy_nexthops_from_vertex(or, v
);
447 /* RFC2328 16.1. second stage. */
448 void ospf_intra_add_stub(struct route_table
*rt
, struct router_lsa_link
*link
,
449 struct vertex
*v
, struct ospf_area
*area
,
450 int parent_is_root
, int lsa_pos
)
453 struct route_node
*rn
;
454 struct ospf_route
* or ;
455 struct prefix_ipv4 p
;
456 struct router_lsa
*lsa
;
457 struct ospf_interface
*oi
;
458 struct ospf_path
*path
;
460 if (IS_DEBUG_OSPF_EVENT
)
461 zlog_debug("ospf_intra_add_stub(): Start");
463 lsa
= (struct router_lsa
*)v
->lsa
;
466 p
.prefix
= link
->link_id
;
467 p
.prefixlen
= ip_masklen(link
->link_data
);
470 if (IS_DEBUG_OSPF_EVENT
)
471 zlog_debug("ospf_intra_add_stub(): processing route to %s/%d",
472 inet_ntoa(p
.prefix
), p
.prefixlen
);
474 /* (1) Calculate the distance D of stub network from the root. D is
475 equal to the distance from the root to the router vertex
476 (calculated in stage 1), plus the stub network link's advertised
478 cost
= v
->distance
+ ntohs(link
->m
[0].metric
);
480 if (IS_DEBUG_OSPF_EVENT
)
482 "ospf_intra_add_stub(): calculated cost is %d + %d = %d",
483 v
->distance
, ntohs(link
->m
[0].metric
), cost
);
485 /* PtP links with /32 masks adds host routes to remote, directly
486 * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
487 * Such routes can just be ignored for the sake of tidyness.
489 if (parent_is_root
&& link
->link_data
.s_addr
== 0xffffffff
490 && ospf_if_lookup_by_local_addr(area
->ospf
, NULL
, link
->link_id
)) {
491 if (IS_DEBUG_OSPF_EVENT
)
492 zlog_debug("%s: ignoring host route %s/32 to self.",
493 __func__
, inet_ntoa(link
->link_id
));
497 rn
= route_node_get(rt
, (struct prefix
*)&p
);
499 /* Lookup current routing table. */
501 struct ospf_route
*cur_or
;
503 route_unlock_node(rn
);
507 if (IS_DEBUG_OSPF_EVENT
)
509 "ospf_intra_add_stub(): "
510 "another route to the same prefix found with cost %u",
513 /* Compare this distance to the current best cost to the stub
514 network. This is done by looking up the stub network's
515 current routing table entry. If the calculated distance D is
516 larger, go on to examine the next stub network link in the
518 if (cost
> cur_or
->cost
) {
519 if (IS_DEBUG_OSPF_EVENT
)
521 "ospf_intra_add_stub(): old route is better, exit");
525 /* (2) If this step is reached, the stub network's routing table
526 entry must be updated. Calculate the set of next hops that
527 would result from using the stub network link. This
528 calculation is shown in Section 16.1.1; input to this
529 calculation is the destination (the stub network) and the
530 parent vertex (the router vertex). If the distance D is the
531 same as the current routing table cost, simply add this set
532 of next hops to the routing table entry's list of next hops.
533 In this case, the routing table already has a Link State
534 Origin. If this Link State Origin is a router-LSA whose Link
535 State ID is smaller than V's Router ID, reset the Link State
536 Origin to V's router-LSA. */
538 if (cost
== cur_or
->cost
) {
539 if (IS_DEBUG_OSPF_EVENT
)
541 "ospf_intra_add_stub(): routes are equal, merge");
543 ospf_route_copy_nexthops_from_vertex(cur_or
, v
);
545 if (IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
,
548 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
552 /* Otherwise D is smaller than the routing table cost.
553 Overwrite the current routing table entry by setting the
554 routing table entry's cost to D, and by setting the entry's
555 list of next hops to the newly calculated set. Set the
556 routing table entry's Link State Origin to V's router-LSA.
557 Then go on to examine the next stub network link. */
559 if (cost
< cur_or
->cost
) {
560 if (IS_DEBUG_OSPF_EVENT
)
562 "ospf_intra_add_stub(): new route is better, set it");
566 list_delete_all_node(cur_or
->paths
);
568 ospf_route_copy_nexthops_from_vertex(cur_or
, v
);
570 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
575 if (IS_DEBUG_OSPF_EVENT
)
576 zlog_debug("ospf_intra_add_stub(): installing new route");
578 or = ospf_route_new();
581 or->u
.std
.area_id
= area
->area_id
;
582 or->u
.std
.external_routing
= area
->external_routing
;
583 or->path_type
= OSPF_PATH_INTRA_AREA
;
585 or->type
= OSPF_DESTINATION_NETWORK
;
586 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
588 /* Nexthop is depend on connection type. */
589 if (v
!= area
->spf
) {
590 if (IS_DEBUG_OSPF_EVENT
)
592 "ospf_intra_add_stub(): this network is on remote router");
593 ospf_route_copy_nexthops_from_vertex(or, v
);
595 if (IS_DEBUG_OSPF_EVENT
)
597 "ospf_intra_add_stub(): this network is on this router");
599 if ((oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
))) {
600 if (IS_DEBUG_OSPF_EVENT
)
602 "ospf_intra_add_stub(): the interface is %s",
605 path
= ospf_path_new();
606 path
->nexthop
.s_addr
= 0;
607 path
->ifindex
= oi
->ifp
->ifindex
;
608 if (CHECK_FLAG(oi
->connected
->flags
,
609 ZEBRA_IFA_UNNUMBERED
))
610 path
->unnumbered
= 1;
611 listnode_add(or->paths
, path
);
613 if (IS_DEBUG_OSPF_EVENT
)
615 "ospf_intra_add_stub(): where's the interface ?");
621 if (IS_DEBUG_OSPF_EVENT
)
622 zlog_debug("ospf_intra_add_stub(): Stop");
625 static const char *const ospf_path_type_str
[] = {
626 "unknown-type", "intra-area", "inter-area", "type1-external",
630 void ospf_route_table_dump(struct route_table
*rt
)
632 struct route_node
*rn
;
633 struct ospf_route
* or ;
636 struct listnode
*pnode
;
637 struct ospf_path
*path
;
640 zlog_debug ("Type Dest Area Path Type Cost Next Adv.");
641 zlog_debug (" Hop(s) Router(s)");
644 zlog_debug("========== OSPF routing table ==========");
645 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
646 if ((or = rn
->info
) != NULL
) {
647 if (or->type
== OSPF_DESTINATION_NETWORK
) {
648 zlog_debug("N %s/%d\t%s\t%s\t%d",
649 inet_ntop(AF_INET
, &rn
->p
.u
.prefix4
,
653 & or->u
.std
.area_id
, buf2
,
655 ospf_path_type_str
[or->path_type
],
657 for (ALL_LIST_ELEMENTS_RO(or->paths
, pnode
,
660 inet_ntoa(path
->nexthop
));
662 zlog_debug("R %s\t%s\t%s\t%d",
663 inet_ntop(AF_INET
, &rn
->p
.u
.prefix4
,
666 & or->u
.std
.area_id
, buf2
,
668 ospf_path_type_str
[or->path_type
],
671 zlog_debug("========================================");
674 /* This is 16.4.1 implementation.
675 o Intra-area paths using non-backbone areas are always the most preferred.
676 o The other paths, intra-area backbone paths and inter-area paths,
677 are of equal preference. */
678 static int ospf_asbr_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
679 struct ospf_route
*r2
)
681 uint8_t r1_type
, r2_type
;
683 r1_type
= r1
->path_type
;
684 r2_type
= r2
->path_type
;
686 /* r1/r2 itself is backbone, and it's Inter-area path. */
687 if (OSPF_IS_AREA_ID_BACKBONE(r1
->u
.std
.area_id
))
688 r1_type
= OSPF_PATH_INTER_AREA
;
689 if (OSPF_IS_AREA_ID_BACKBONE(r2
->u
.std
.area_id
))
690 r2_type
= OSPF_PATH_INTER_AREA
;
692 return (r1_type
- r2_type
);
695 /* Compare two routes.
696 ret < 0 -- r1 is better.
697 ret == 0 -- r1 and r2 are the same.
698 ret > 0 -- r2 is better. */
699 int ospf_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
700 struct ospf_route
*r2
)
704 /* Path types of r1 and r2 are not the same. */
705 if ((ret
= (r1
->path_type
- r2
->path_type
)))
708 if (IS_DEBUG_OSPF_EVENT
)
709 zlog_debug("Route[Compare]: Path types are the same.");
710 /* Path types are the same, compare any cost. */
711 switch (r1
->path_type
) {
712 case OSPF_PATH_INTRA_AREA
:
713 case OSPF_PATH_INTER_AREA
:
715 case OSPF_PATH_TYPE1_EXTERNAL
:
716 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
717 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
723 case OSPF_PATH_TYPE2_EXTERNAL
:
724 if ((ret
= (r1
->u
.ext
.type2_cost
- r2
->u
.ext
.type2_cost
)))
727 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
728 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
736 /* Anyway, compare the costs. */
737 return (r1
->cost
- r2
->cost
);
740 static int ospf_path_exist(struct list
*plist
, struct in_addr nexthop
,
741 struct ospf_interface
*oi
)
743 struct listnode
*node
, *nnode
;
744 struct ospf_path
*path
;
746 for (ALL_LIST_ELEMENTS(plist
, node
, nnode
, path
))
747 if (IPV4_ADDR_SAME(&path
->nexthop
, &nexthop
)
748 && path
->ifindex
== oi
->ifp
->ifindex
)
754 void ospf_route_copy_nexthops_from_vertex(struct ospf_route
*to
,
757 struct listnode
*node
;
758 struct ospf_path
*path
;
759 struct vertex_nexthop
*nexthop
;
760 struct vertex_parent
*vp
;
764 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
765 nexthop
= vp
->nexthop
;
767 if (nexthop
->oi
!= NULL
) {
768 if (!ospf_path_exist(to
->paths
, nexthop
->router
,
770 path
= ospf_path_new();
771 path
->nexthop
= nexthop
->router
;
772 path
->ifindex
= nexthop
->oi
->ifp
->ifindex
;
773 if (CHECK_FLAG(nexthop
->oi
->connected
->flags
,
774 ZEBRA_IFA_UNNUMBERED
))
775 path
->unnumbered
= 1;
776 listnode_add(to
->paths
, path
);
782 struct ospf_path
*ospf_path_lookup(struct list
*plist
, struct ospf_path
*path
)
784 struct listnode
*node
;
785 struct ospf_path
*op
;
787 for (ALL_LIST_ELEMENTS_RO(plist
, node
, op
)) {
788 if (!IPV4_ADDR_SAME(&op
->nexthop
, &path
->nexthop
))
790 if (!IPV4_ADDR_SAME(&op
->adv_router
, &path
->adv_router
))
792 if (op
->ifindex
!= path
->ifindex
)
799 void ospf_route_copy_nexthops(struct ospf_route
*to
, struct list
*from
)
801 struct listnode
*node
, *nnode
;
802 struct ospf_path
*path
;
806 for (ALL_LIST_ELEMENTS(from
, node
, nnode
, path
))
807 /* The same routes are just discarded. */
808 if (!ospf_path_lookup(to
->paths
, path
))
809 listnode_add(to
->paths
, ospf_path_dup(path
));
812 void ospf_route_subst_nexthops(struct ospf_route
*to
, struct list
*from
)
815 list_delete_all_node(to
->paths
);
816 ospf_route_copy_nexthops(to
, from
);
819 void ospf_route_subst(struct route_node
*rn
, struct ospf_route
*new_or
,
820 struct ospf_route
*over
)
823 ospf_route_free(rn
->info
);
825 ospf_route_copy_nexthops(new_or
, over
->paths
);
827 route_unlock_node(rn
);
830 void ospf_route_add(struct route_table
*rt
, struct prefix_ipv4
*p
,
831 struct ospf_route
*new_or
, struct ospf_route
*over
)
833 struct route_node
*rn
;
835 rn
= route_node_get(rt
, (struct prefix
*)p
);
837 ospf_route_copy_nexthops(new_or
, over
->paths
);
840 if (IS_DEBUG_OSPF_EVENT
)
841 zlog_debug("ospf_route_add(): something's wrong !");
842 route_unlock_node(rn
);
849 void ospf_prune_unreachable_networks(struct route_table
*rt
)
851 struct route_node
*rn
, *next
;
852 struct ospf_route
* or ;
854 if (IS_DEBUG_OSPF_EVENT
)
855 zlog_debug("Pruning unreachable networks");
857 for (rn
= route_top(rt
); rn
; rn
= next
) {
858 next
= route_next(rn
);
859 if (rn
->info
!= NULL
) {
861 if (listcount(or->paths
) == 0) {
862 if (IS_DEBUG_OSPF_EVENT
)
863 zlog_debug("Pruning route to %s/%d",
864 inet_ntoa(rn
->p
.u
.prefix4
),
869 route_unlock_node(rn
);
875 void ospf_prune_unreachable_routers(struct route_table
*rtrs
)
877 struct route_node
*rn
, *next
;
878 struct ospf_route
* or ;
879 struct listnode
*node
, *nnode
;
882 if (IS_DEBUG_OSPF_EVENT
)
883 zlog_debug("Pruning unreachable routers");
885 for (rn
= route_top(rtrs
); rn
; rn
= next
) {
886 next
= route_next(rn
);
887 if ((paths
= rn
->info
) == NULL
)
890 for (ALL_LIST_ELEMENTS(paths
, node
, nnode
, or)) {
891 if (listcount(or->paths
) == 0) {
892 if (IS_DEBUG_OSPF_EVENT
) {
893 zlog_debug("Pruning route to rtr %s",
894 inet_ntoa(rn
->p
.u
.prefix4
));
897 inet_ntoa(or->u
.std
.area_id
));
900 listnode_delete(paths
, or);
905 if (listcount(paths
) == 0) {
906 if (IS_DEBUG_OSPF_EVENT
)
907 zlog_debug("Pruning router node %s",
908 inet_ntoa(rn
->p
.u
.prefix4
));
912 route_unlock_node(rn
);
917 int ospf_add_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
918 struct ospf_area
*area
, struct prefix_ipv4
*p
)
920 struct route_node
*rn
;
921 struct ospf_route
* or, *new_or
;
923 rn
= route_node_get(rt
, (struct prefix
*)p
);
926 if (IS_DEBUG_OSPF_EVENT
)
928 "ospf_add_discard_route(): router installation error");
932 if (rn
->info
) /* If the route to the same destination is found */
934 route_unlock_node(rn
);
938 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
939 if (IS_DEBUG_OSPF_EVENT
)
941 "ospf_add_discard_route(): "
942 "an intra-area route exists");
946 if (or->type
== OSPF_DESTINATION_DISCARD
) {
947 if (IS_DEBUG_OSPF_EVENT
)
949 "ospf_add_discard_route(): "
950 "discard entry already installed");
954 ospf_route_free(rn
->info
);
957 if (IS_DEBUG_OSPF_EVENT
)
959 "ospf_add_discard_route(): "
961 inet_ntoa(p
->prefix
), p
->prefixlen
);
963 new_or
= ospf_route_new();
964 new_or
->type
= OSPF_DESTINATION_DISCARD
;
965 new_or
->id
.s_addr
= 0;
967 new_or
->u
.std
.area_id
= area
->area_id
;
968 new_or
->u
.std
.external_routing
= area
->external_routing
;
969 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
972 ospf_zebra_add_discard(ospf
, p
);
977 void ospf_delete_discard_route(struct ospf
*ospf
, struct route_table
*rt
,
978 struct prefix_ipv4
*p
)
980 struct route_node
*rn
;
981 struct ospf_route
* or ;
983 if (IS_DEBUG_OSPF_EVENT
)
985 "ospf_delete_discard_route(): "
987 inet_ntoa(p
->prefix
), p
->prefixlen
);
989 rn
= route_node_lookup(rt
, (struct prefix
*)p
);
992 if (IS_DEBUG_OSPF_EVENT
)
994 "ospf_delete_discard_route(): no route found");
1000 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
1001 if (IS_DEBUG_OSPF_EVENT
)
1003 "ospf_delete_discard_route(): "
1004 "an intra-area route exists");
1008 if (or->type
!= OSPF_DESTINATION_DISCARD
) {
1009 if (IS_DEBUG_OSPF_EVENT
)
1011 "ospf_delete_discard_route(): "
1012 "not a discard entry");
1016 /* free the route entry and the route node */
1017 ospf_route_free(rn
->info
);
1020 route_unlock_node(rn
);
1021 route_unlock_node(rn
);
1023 /* remove the discard entry from the rib */
1024 ospf_zebra_delete_discard(ospf
, p
);