]>
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()
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()
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 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
)
94 ospf_zebra_delete((struct prefix_ipv4
*)&rn
->p
,
96 else if (or->type
== OSPF_DESTINATION_DISCARD
)
97 ospf_zebra_delete_discard(
98 (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
);
174 n1
= listnextnode(n1
), n2
= listnextnode(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 route_table
*external_routes
,
195 struct route_table
*routes
)
197 struct route_node
*rn
, *ext_rn
;
199 if ((external_routes
== NULL
) || (routes
== NULL
))
202 /* Remove deleted routes */
203 for (rn
= route_top(routes
); rn
; rn
= route_next(rn
)) {
204 if (rn
&& rn
->info
) {
205 struct prefix_ipv4
*p
= (struct prefix_ipv4
*)(&rn
->p
);
206 if ((ext_rn
= route_node_lookup(external_routes
,
207 (struct prefix
*)p
))) {
209 ospf_zebra_delete(p
, ext_rn
->info
);
210 ospf_route_free(ext_rn
->info
);
213 route_unlock_node(ext_rn
);
219 /* rt: Old, cmprt: New */
220 static void ospf_route_delete_uniq(struct route_table
*rt
,
221 struct route_table
*cmprt
)
223 struct route_node
*rn
;
224 struct ospf_route
* or ;
226 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
227 if ((or = rn
->info
) != NULL
)
228 if (or->path_type
== OSPF_PATH_INTRA_AREA
||
229 or->path_type
== OSPF_PATH_INTER_AREA
) {
230 if (or->type
== OSPF_DESTINATION_NETWORK
) {
231 if (!ospf_route_exist_new_table(
233 (struct prefix_ipv4
*)&rn
239 } else if (or->type
== OSPF_DESTINATION_DISCARD
)
240 if (!ospf_route_exist_new_table(
242 (struct prefix_ipv4
*)&rn
244 ospf_zebra_delete_discard(
250 /* Install routes to table. */
251 void ospf_route_install(struct ospf
*ospf
, struct route_table
*rt
)
253 struct route_node
*rn
;
254 struct ospf_route
* or ;
256 /* rt contains new routing table, new_table contains an old one.
259 ospf_route_table_free(ospf
->old_table
);
261 ospf
->old_table
= ospf
->new_table
;
262 ospf
->new_table
= rt
;
264 /* Delete old routes. */
266 ospf_route_delete_uniq(ospf
->old_table
, rt
);
267 if (ospf
->old_external_route
)
268 ospf_route_delete_same_ext(ospf
->old_external_route
, rt
);
270 /* Install new routes. */
271 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
272 if ((or = rn
->info
) != NULL
) {
273 if (or->type
== OSPF_DESTINATION_NETWORK
) {
274 if (!ospf_route_match_same(
276 (struct prefix_ipv4
*)&rn
->p
, or))
278 (struct prefix_ipv4
*)&rn
->p
,
280 } else if (or->type
== OSPF_DESTINATION_DISCARD
)
281 if (!ospf_route_match_same(
283 (struct prefix_ipv4
*)&rn
->p
, or))
284 ospf_zebra_add_discard(
285 (struct prefix_ipv4
*)&rn
->p
);
289 /* RFC2328 16.1. (4). For "router". */
290 void ospf_intra_add_router(struct route_table
*rt
, struct vertex
*v
,
291 struct ospf_area
*area
)
293 struct route_node
*rn
;
294 struct ospf_route
* or ;
295 struct prefix_ipv4 p
;
296 struct router_lsa
*lsa
;
298 if (IS_DEBUG_OSPF_EVENT
)
299 zlog_debug("ospf_intra_add_router: Start");
301 lsa
= (struct router_lsa
*)v
->lsa
;
303 if (IS_DEBUG_OSPF_EVENT
)
304 zlog_debug("ospf_intra_add_router: LS ID: %s",
305 inet_ntoa(lsa
->header
.id
));
307 if (!OSPF_IS_AREA_BACKBONE(area
))
308 ospf_vl_up_check(area
, lsa
->header
.id
, v
);
310 if (!CHECK_FLAG(lsa
->flags
, ROUTER_LSA_SHORTCUT
))
311 area
->shortcut_capability
= 0;
313 /* If the newly added vertex is an area border router or AS boundary
314 router, a routing table entry is added whose destination type is
316 if (!IS_ROUTER_LSA_BORDER(lsa
) && !IS_ROUTER_LSA_EXTERNAL(lsa
)) {
317 if (IS_DEBUG_OSPF_EVENT
)
319 "ospf_intra_add_router: "
320 "this router is neither ASBR nor ABR, skipping it");
324 /* Update ABR and ASBR count in this area. */
325 if (IS_ROUTER_LSA_BORDER(lsa
))
327 if (IS_ROUTER_LSA_EXTERNAL(lsa
))
330 /* The Options field found in the associated router-LSA is copied
331 into the routing table entry's Optional capabilities field. Call
332 the newly added vertex Router X. */
333 or = ospf_route_new();
336 or->u
.std
.area_id
= area
->area_id
;
337 or->u
.std
.external_routing
= area
->external_routing
;
338 or->path_type
= OSPF_PATH_INTRA_AREA
;
339 or->cost
= v
->distance
;
340 or->type
= OSPF_DESTINATION_ROUTER
;
341 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
342 or->u
.std
.options
= lsa
->header
.options
;
343 or->u
.std
.flags
= lsa
->flags
;
345 /* If Router X is the endpoint of one of the calculating router's
346 virtual links, and the virtual link uses Area A as Transit area:
347 the virtual link is declared up, the IP address of the virtual
348 interface is set to the IP address of the outgoing interface
349 calculated above for Router X, and the virtual neighbor's IP
350 address is set to Router X's interface address (contained in
351 Router X's router-LSA) that points back to the root of the
352 shortest- path tree; equivalently, this is the interface that
353 points back to Router X's parent vertex on the shortest-path tree
354 (similar to the calculation in Section 16.1.1). */
358 p
.prefixlen
= IPV4_MAX_BITLEN
;
361 if (IS_DEBUG_OSPF_EVENT
)
362 zlog_debug("ospf_intra_add_router: talking about %s/%d",
363 inet_ntoa(p
.prefix
), p
.prefixlen
);
365 rn
= route_node_get(rt
, (struct prefix
*)&p
);
367 /* Note that we keep all routes to ABRs and ASBRs, not only the best */
368 if (rn
->info
== NULL
)
369 rn
->info
= list_new();
371 route_unlock_node(rn
);
373 ospf_route_copy_nexthops_from_vertex(or, v
);
375 listnode_add(rn
->info
, or);
377 if (IS_DEBUG_OSPF_EVENT
)
378 zlog_debug("ospf_intra_add_router: Stop");
381 /* RFC2328 16.1. (4). For transit network. */
382 void ospf_intra_add_transit(struct route_table
*rt
, struct vertex
*v
,
383 struct ospf_area
*area
)
385 struct route_node
*rn
;
386 struct ospf_route
* or ;
387 struct prefix_ipv4 p
;
388 struct network_lsa
*lsa
;
390 lsa
= (struct network_lsa
*)v
->lsa
;
392 /* If the newly added vertex is a transit network, the routing table
393 entry for the network is located. The entry's Destination ID is
394 the IP network number, which can be obtained by masking the
395 Vertex ID (Link State ID) with its associated subnet mask (found
396 in the body of the associated network-LSA). */
399 p
.prefixlen
= ip_masklen(lsa
->mask
);
402 rn
= route_node_get(rt
, (struct prefix
*)&p
);
404 /* If the routing table entry already exists (i.e., there is already
405 an intra-area route to the destination installed in the routing
406 table), multiple vertices have mapped to the same IP network.
407 For example, this can occur when a new Designated Router is being
408 established. In this case, the current routing table entry
409 should be overwritten if and only if the newly found path is just
410 as short and the current routing table entry's Link State Origin
411 has a smaller Link State ID than the newly added vertex' LSA. */
413 struct ospf_route
*cur_or
;
415 route_unlock_node(rn
);
418 if (v
->distance
> cur_or
->cost
419 || IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
, &lsa
->header
.id
)
423 ospf_route_free(rn
->info
);
426 or = ospf_route_new();
429 or->u
.std
.area_id
= area
->area_id
;
430 or->u
.std
.external_routing
= area
->external_routing
;
431 or->path_type
= OSPF_PATH_INTRA_AREA
;
432 or->cost
= v
->distance
;
433 or->type
= OSPF_DESTINATION_NETWORK
;
434 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
436 ospf_route_copy_nexthops_from_vertex(or, v
);
441 /* RFC2328 16.1. second stage. */
442 void ospf_intra_add_stub(struct route_table
*rt
, struct router_lsa_link
*link
,
443 struct vertex
*v
, struct ospf_area
*area
,
444 int parent_is_root
, int lsa_pos
)
447 struct route_node
*rn
;
448 struct ospf_route
* or ;
449 struct prefix_ipv4 p
;
450 struct router_lsa
*lsa
;
451 struct ospf_interface
*oi
;
452 struct ospf_path
*path
;
454 if (IS_DEBUG_OSPF_EVENT
)
455 zlog_debug("ospf_intra_add_stub(): Start");
457 lsa
= (struct router_lsa
*)v
->lsa
;
460 p
.prefix
= link
->link_id
;
461 p
.prefixlen
= ip_masklen(link
->link_data
);
464 if (IS_DEBUG_OSPF_EVENT
)
465 zlog_debug("ospf_intra_add_stub(): processing route to %s/%d",
466 inet_ntoa(p
.prefix
), p
.prefixlen
);
468 /* (1) Calculate the distance D of stub network from the root. D is
469 equal to the distance from the root to the router vertex
470 (calculated in stage 1), plus the stub network link's advertised
472 cost
= v
->distance
+ ntohs(link
->m
[0].metric
);
474 if (IS_DEBUG_OSPF_EVENT
)
476 "ospf_intra_add_stub(): calculated cost is %d + %d = %d",
477 v
->distance
, ntohs(link
->m
[0].metric
), cost
);
479 /* PtP links with /32 masks adds host routes to remote, directly
480 * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
481 * Such routes can just be ignored for the sake of tidyness.
483 if (parent_is_root
&& link
->link_data
.s_addr
== 0xffffffff
484 && ospf_if_lookup_by_local_addr(area
->ospf
, NULL
, link
->link_id
)) {
485 if (IS_DEBUG_OSPF_EVENT
)
486 zlog_debug("%s: ignoring host route %s/32 to self.",
487 __func__
, inet_ntoa(link
->link_id
));
491 rn
= route_node_get(rt
, (struct prefix
*)&p
);
493 /* Lookup current routing table. */
495 struct ospf_route
*cur_or
;
497 route_unlock_node(rn
);
501 if (IS_DEBUG_OSPF_EVENT
)
503 "ospf_intra_add_stub(): "
504 "another route to the same prefix found with cost %u",
507 /* Compare this distance to the current best cost to the stub
508 network. This is done by looking up the stub network's
509 current routing table entry. If the calculated distance D is
510 larger, go on to examine the next stub network link in the
512 if (cost
> cur_or
->cost
) {
513 if (IS_DEBUG_OSPF_EVENT
)
515 "ospf_intra_add_stub(): old route is better, exit");
519 /* (2) If this step is reached, the stub network's routing table
520 entry must be updated. Calculate the set of next hops that
521 would result from using the stub network link. This
522 calculation is shown in Section 16.1.1; input to this
523 calculation is the destination (the stub network) and the
524 parent vertex (the router vertex). If the distance D is the
525 same as the current routing table cost, simply add this set
526 of next hops to the routing table entry's list of next hops.
527 In this case, the routing table already has a Link State
528 Origin. If this Link State Origin is a router-LSA whose Link
529 State ID is smaller than V's Router ID, reset the Link State
530 Origin to V's router-LSA. */
532 if (cost
== cur_or
->cost
) {
533 if (IS_DEBUG_OSPF_EVENT
)
535 "ospf_intra_add_stub(): routes are equal, merge");
537 ospf_route_copy_nexthops_from_vertex(cur_or
, v
);
539 if (IPV4_ADDR_CMP(&cur_or
->u
.std
.origin
->id
,
542 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
546 /* Otherwise D is smaller than the routing table cost.
547 Overwrite the current routing table entry by setting the
548 routing table entry's cost to D, and by setting the entry's
549 list of next hops to the newly calculated set. Set the
550 routing table entry's Link State Origin to V's router-LSA.
551 Then go on to examine the next stub network link. */
553 if (cost
< cur_or
->cost
) {
554 if (IS_DEBUG_OSPF_EVENT
)
556 "ospf_intra_add_stub(): new route is better, set it");
560 list_delete_all_node(cur_or
->paths
);
562 ospf_route_copy_nexthops_from_vertex(cur_or
, v
);
564 cur_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
569 if (IS_DEBUG_OSPF_EVENT
)
570 zlog_debug("ospf_intra_add_stub(): installing new route");
572 or = ospf_route_new();
575 or->u
.std
.area_id
= area
->area_id
;
576 or->u
.std
.external_routing
= area
->external_routing
;
577 or->path_type
= OSPF_PATH_INTRA_AREA
;
579 or->type
= OSPF_DESTINATION_NETWORK
;
580 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
582 /* Nexthop is depend on connection type. */
583 if (v
!= area
->spf
) {
584 if (IS_DEBUG_OSPF_EVENT
)
586 "ospf_intra_add_stub(): this network is on remote router");
587 ospf_route_copy_nexthops_from_vertex(or, v
);
589 if (IS_DEBUG_OSPF_EVENT
)
591 "ospf_intra_add_stub(): this network is on this router");
593 if ((oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
))) {
594 if (IS_DEBUG_OSPF_EVENT
)
596 "ospf_intra_add_stub(): the interface is %s",
599 path
= ospf_path_new();
600 path
->nexthop
.s_addr
= 0;
601 path
->ifindex
= oi
->ifp
->ifindex
;
602 if (CHECK_FLAG(oi
->connected
->flags
,
603 ZEBRA_IFA_UNNUMBERED
))
604 path
->unnumbered
= 1;
605 listnode_add(or->paths
, path
);
607 if (IS_DEBUG_OSPF_EVENT
)
609 "ospf_intra_add_stub(): where's the interface ?");
615 if (IS_DEBUG_OSPF_EVENT
)
616 zlog_debug("ospf_intra_add_stub(): Stop");
619 const char *ospf_path_type_str
[] = {"unknown-type", "intra-area", "inter-area",
620 "type1-external", "type2-external"};
622 void ospf_route_table_dump(struct route_table
*rt
)
624 struct route_node
*rn
;
625 struct ospf_route
* or ;
628 struct listnode
*pnode
;
629 struct ospf_path
*path
;
632 zlog_debug ("Type Dest Area Path Type Cost Next Adv.");
633 zlog_debug (" Hop(s) Router(s)");
636 zlog_debug("========== OSPF routing table ==========");
637 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
638 if ((or = rn
->info
) != NULL
) {
639 if (or->type
== OSPF_DESTINATION_NETWORK
) {
640 zlog_debug("N %s/%d\t%s\t%s\t%d",
641 inet_ntop(AF_INET
, &rn
->p
.u
.prefix4
,
645 & or->u
.std
.area_id
, buf2
,
647 ospf_path_type_str
[or->path_type
],
649 for (ALL_LIST_ELEMENTS_RO(or->paths
, pnode
,
652 inet_ntoa(path
->nexthop
));
654 zlog_debug("R %s\t%s\t%s\t%d",
655 inet_ntop(AF_INET
, &rn
->p
.u
.prefix4
,
658 & or->u
.std
.area_id
, buf2
,
660 ospf_path_type_str
[or->path_type
],
663 zlog_debug("========================================");
666 /* This is 16.4.1 implementation.
667 o Intra-area paths using non-backbone areas are always the most preferred.
668 o The other paths, intra-area backbone paths and inter-area paths,
669 are of equal preference. */
670 static int ospf_asbr_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
671 struct ospf_route
*r2
)
673 u_char r1_type
, r2_type
;
675 r1_type
= r1
->path_type
;
676 r2_type
= r2
->path_type
;
678 /* r1/r2 itself is backbone, and it's Inter-area path. */
679 if (OSPF_IS_AREA_ID_BACKBONE(r1
->u
.std
.area_id
))
680 r1_type
= OSPF_PATH_INTER_AREA
;
681 if (OSPF_IS_AREA_ID_BACKBONE(r2
->u
.std
.area_id
))
682 r2_type
= OSPF_PATH_INTER_AREA
;
684 return (r1_type
- r2_type
);
687 /* Compare two routes.
688 ret < 0 -- r1 is better.
689 ret == 0 -- r1 and r2 are the same.
690 ret > 0 -- r2 is better. */
691 int ospf_route_cmp(struct ospf
*ospf
, struct ospf_route
*r1
,
692 struct ospf_route
*r2
)
696 /* Path types of r1 and r2 are not the same. */
697 if ((ret
= (r1
->path_type
- r2
->path_type
)))
700 if (IS_DEBUG_OSPF_EVENT
)
701 zlog_debug("Route[Compare]: Path types are the same.");
702 /* Path types are the same, compare any cost. */
703 switch (r1
->path_type
) {
704 case OSPF_PATH_INTRA_AREA
:
705 case OSPF_PATH_INTER_AREA
:
707 case OSPF_PATH_TYPE1_EXTERNAL
:
708 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
709 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
715 case OSPF_PATH_TYPE2_EXTERNAL
:
716 if ((ret
= (r1
->u
.ext
.type2_cost
- r2
->u
.ext
.type2_cost
)))
719 if (!CHECK_FLAG(ospf
->config
, OSPF_RFC1583_COMPATIBLE
)) {
720 ret
= ospf_asbr_route_cmp(ospf
, r1
->u
.ext
.asbr
,
728 /* Anyway, compare the costs. */
729 return (r1
->cost
- r2
->cost
);
732 static int ospf_path_exist(struct list
*plist
, struct in_addr nexthop
,
733 struct ospf_interface
*oi
)
735 struct listnode
*node
, *nnode
;
736 struct ospf_path
*path
;
738 for (ALL_LIST_ELEMENTS(plist
, node
, nnode
, path
))
739 if (IPV4_ADDR_SAME(&path
->nexthop
, &nexthop
)
740 && path
->ifindex
== oi
->ifp
->ifindex
)
746 void ospf_route_copy_nexthops_from_vertex(struct ospf_route
*to
,
749 struct listnode
*node
;
750 struct ospf_path
*path
;
751 struct vertex_nexthop
*nexthop
;
752 struct vertex_parent
*vp
;
756 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
757 nexthop
= vp
->nexthop
;
759 if (nexthop
->oi
!= NULL
) {
760 if (!ospf_path_exist(to
->paths
, nexthop
->router
,
762 path
= ospf_path_new();
763 path
->nexthop
= nexthop
->router
;
764 path
->ifindex
= nexthop
->oi
->ifp
->ifindex
;
765 if (CHECK_FLAG(nexthop
->oi
->connected
->flags
,
766 ZEBRA_IFA_UNNUMBERED
))
767 path
->unnumbered
= 1;
768 listnode_add(to
->paths
, path
);
774 struct ospf_path
*ospf_path_lookup(struct list
*plist
, struct ospf_path
*path
)
776 struct listnode
*node
;
777 struct ospf_path
*op
;
779 for (ALL_LIST_ELEMENTS_RO(plist
, node
, op
)) {
780 if (!IPV4_ADDR_SAME(&op
->nexthop
, &path
->nexthop
))
782 if (!IPV4_ADDR_SAME(&op
->adv_router
, &path
->adv_router
))
784 if (op
->ifindex
!= path
->ifindex
)
791 void ospf_route_copy_nexthops(struct ospf_route
*to
, struct list
*from
)
793 struct listnode
*node
, *nnode
;
794 struct ospf_path
*path
;
798 for (ALL_LIST_ELEMENTS(from
, node
, nnode
, path
))
799 /* The same routes are just discarded. */
800 if (!ospf_path_lookup(to
->paths
, path
))
801 listnode_add(to
->paths
, ospf_path_dup(path
));
804 void ospf_route_subst_nexthops(struct ospf_route
*to
, struct list
*from
)
807 list_delete_all_node(to
->paths
);
808 ospf_route_copy_nexthops(to
, from
);
811 void ospf_route_subst(struct route_node
*rn
, struct ospf_route
*new_or
,
812 struct ospf_route
*over
)
815 ospf_route_free(rn
->info
);
817 ospf_route_copy_nexthops(new_or
, over
->paths
);
819 route_unlock_node(rn
);
822 void ospf_route_add(struct route_table
*rt
, struct prefix_ipv4
*p
,
823 struct ospf_route
*new_or
, struct ospf_route
*over
)
825 struct route_node
*rn
;
827 rn
= route_node_get(rt
, (struct prefix
*)p
);
829 ospf_route_copy_nexthops(new_or
, over
->paths
);
832 if (IS_DEBUG_OSPF_EVENT
)
833 zlog_debug("ospf_route_add(): something's wrong !");
834 route_unlock_node(rn
);
841 void ospf_prune_unreachable_networks(struct route_table
*rt
)
843 struct route_node
*rn
, *next
;
844 struct ospf_route
* or ;
846 if (IS_DEBUG_OSPF_EVENT
)
847 zlog_debug("Pruning unreachable networks");
849 for (rn
= route_top(rt
); rn
; rn
= next
) {
850 next
= route_next(rn
);
851 if (rn
->info
!= NULL
) {
853 if (listcount(or->paths
) == 0) {
854 if (IS_DEBUG_OSPF_EVENT
)
855 zlog_debug("Pruning route to %s/%d",
856 inet_ntoa(rn
->p
.u
.prefix4
),
861 route_unlock_node(rn
);
867 void ospf_prune_unreachable_routers(struct route_table
*rtrs
)
869 struct route_node
*rn
, *next
;
870 struct ospf_route
* or ;
871 struct listnode
*node
, *nnode
;
874 if (IS_DEBUG_OSPF_EVENT
)
875 zlog_debug("Pruning unreachable routers");
877 for (rn
= route_top(rtrs
); rn
; rn
= next
) {
878 next
= route_next(rn
);
879 if ((paths
= rn
->info
) == NULL
)
882 for (ALL_LIST_ELEMENTS(paths
, node
, nnode
, or)) {
883 if (listcount(or->paths
) == 0) {
884 if (IS_DEBUG_OSPF_EVENT
) {
885 zlog_debug("Pruning route to rtr %s",
886 inet_ntoa(rn
->p
.u
.prefix4
));
889 inet_ntoa(or->u
.std
.area_id
));
892 listnode_delete(paths
, or);
897 if (listcount(paths
) == 0) {
898 if (IS_DEBUG_OSPF_EVENT
)
899 zlog_debug("Pruning router node %s",
900 inet_ntoa(rn
->p
.u
.prefix4
));
904 route_unlock_node(rn
);
909 int ospf_add_discard_route(struct route_table
*rt
, struct ospf_area
*area
,
910 struct prefix_ipv4
*p
)
912 struct route_node
*rn
;
913 struct ospf_route
* or, *new_or
;
915 rn
= route_node_get(rt
, (struct prefix
*)p
);
918 if (IS_DEBUG_OSPF_EVENT
)
920 "ospf_add_discard_route(): router installation error");
924 if (rn
->info
) /* If the route to the same destination is found */
926 route_unlock_node(rn
);
930 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
931 if (IS_DEBUG_OSPF_EVENT
)
933 "ospf_add_discard_route(): "
934 "an intra-area route exists");
938 if (or->type
== OSPF_DESTINATION_DISCARD
) {
939 if (IS_DEBUG_OSPF_EVENT
)
941 "ospf_add_discard_route(): "
942 "discard entry already installed");
946 ospf_route_free(rn
->info
);
949 if (IS_DEBUG_OSPF_EVENT
)
951 "ospf_add_discard_route(): "
953 inet_ntoa(p
->prefix
), p
->prefixlen
);
955 new_or
= ospf_route_new();
956 new_or
->type
= OSPF_DESTINATION_DISCARD
;
957 new_or
->id
.s_addr
= 0;
959 new_or
->u
.std
.area_id
= area
->area_id
;
960 new_or
->u
.std
.external_routing
= area
->external_routing
;
961 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
964 ospf_zebra_add_discard(p
);
969 void ospf_delete_discard_route(struct route_table
*rt
, struct prefix_ipv4
*p
)
971 struct route_node
*rn
;
972 struct ospf_route
* or ;
974 if (IS_DEBUG_OSPF_EVENT
)
976 "ospf_delete_discard_route(): "
978 inet_ntoa(p
->prefix
), p
->prefixlen
);
980 rn
= route_node_lookup(rt
, (struct prefix
*)p
);
983 if (IS_DEBUG_OSPF_EVENT
)
985 "ospf_delete_discard_route(): no route found");
991 if (or->path_type
== OSPF_PATH_INTRA_AREA
) {
992 if (IS_DEBUG_OSPF_EVENT
)
994 "ospf_delete_discard_route(): "
995 "an intra-area route exists");
999 if (or->type
!= OSPF_DESTINATION_DISCARD
) {
1000 if (IS_DEBUG_OSPF_EVENT
)
1002 "ospf_delete_discard_route(): "
1003 "not a discard entry");
1007 /* free the route entry and the route node */
1008 ospf_route_free(rn
->info
);
1011 route_unlock_node(rn
);
1012 route_unlock_node(rn
);
1014 /* remove the discard entry from the rib */
1015 ospf_zebra_delete_discard(p
);