]>
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
18 * along with GNU Zebra; see the file COPYING. If not, write to the Free
19 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
32 #include "sockunion.h"
34 #include "ospfd/ospfd.h"
35 #include "ospfd/ospf_interface.h"
36 #include "ospfd/ospf_asbr.h"
37 #include "ospfd/ospf_lsa.h"
38 #include "ospfd/ospf_route.h"
39 #include "ospfd/ospf_spf.h"
40 #include "ospfd/ospf_zebra.h"
41 #include "ospfd/ospf_dump.h"
43 struct ospf_route
*ospf_route_new()
45 struct ospf_route
*new;
47 new = XCALLOC(MTYPE_OSPF_ROUTE
, sizeof(struct ospf_route
));
49 new->paths
= list_new();
50 new->paths
->del
= (void (*)(void *))ospf_path_free
;
55 void ospf_route_free(struct ospf_route
* or)
58 list_delete(or->paths
);
60 XFREE(MTYPE_OSPF_ROUTE
, or);
63 struct ospf_path
*ospf_path_new()
65 struct ospf_path
*new;
67 new = XCALLOC(MTYPE_OSPF_PATH
, sizeof(struct ospf_path
));
72 static struct ospf_path
*ospf_path_dup(struct ospf_path
*path
)
74 struct ospf_path
*new;
76 new = ospf_path_new();
77 memcpy(new, path
, sizeof(struct ospf_path
));
82 void ospf_path_free(struct ospf_path
*op
)
84 XFREE(MTYPE_OSPF_PATH
, op
);
87 void ospf_route_delete(struct route_table
*rt
)
89 struct route_node
*rn
;
90 struct ospf_route
* or ;
92 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
93 if ((or = rn
->info
) != NULL
) {
94 if (or->type
== OSPF_DESTINATION_NETWORK
)
95 ospf_zebra_delete((struct prefix_ipv4
*)&rn
->p
,
97 else if (or->type
== OSPF_DESTINATION_DISCARD
)
98 ospf_zebra_delete_discard(
99 (struct prefix_ipv4
*)&rn
->p
);
103 void ospf_route_table_free(struct route_table
*rt
)
105 struct route_node
*rn
;
106 struct ospf_route
* or ;
108 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
109 if ((or = rn
->info
) != NULL
) {
113 route_unlock_node(rn
);
116 route_table_finish(rt
);
119 /* If a prefix exists in the new routing table, then return 1,
120 otherwise return 0. Since the ZEBRA-RIB does an implicit
121 withdraw, it is not necessary to send a delete, an add later
122 will act like an implicit delete. */
123 static int ospf_route_exist_new_table(struct route_table
*rt
,
124 struct prefix_ipv4
*prefix
)
126 struct route_node
*rn
;
131 rn
= route_node_lookup(rt
, (struct prefix
*)prefix
);
135 route_unlock_node(rn
);
144 /* If a prefix and a nexthop match any route in the routing table,
145 then return 1, otherwise return 0. */
146 int ospf_route_match_same(struct route_table
*rt
, struct prefix_ipv4
*prefix
,
147 struct ospf_route
*newor
)
149 struct route_node
*rn
;
150 struct ospf_route
* or ;
151 struct ospf_path
*op
;
152 struct ospf_path
*newop
;
159 rn
= route_node_lookup(rt
, (struct prefix
*)prefix
);
160 if (!rn
|| !rn
->info
)
163 route_unlock_node(rn
);
166 if (or->type
== newor
->type
&& or->cost
== newor
->cost
) {
167 if (or->type
== OSPF_DESTINATION_NETWORK
) {
168 if (or->paths
->count
!= newor
->paths
->count
)
171 /* Check each path. */
172 for (n1
= listhead(or->paths
),
173 n2
= listhead(newor
->paths
);
175 n1
= listnextnode(n1
), n2
= listnextnode(n2
)) {
176 op
= listgetdata(n1
);
177 newop
= listgetdata(n2
);
179 if (!IPV4_ADDR_SAME(&op
->nexthop
,
182 if (op
->ifindex
!= newop
->ifindex
)
186 } else if (prefix_same(&rn
->p
, (struct prefix
*)prefix
))
192 /* delete routes generated from AS-External routes if there is a inter/intra
195 static void ospf_route_delete_same_ext(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(p
, ext_rn
->info
);
211 ospf_route_free(ext_rn
->info
);
214 route_unlock_node(ext_rn
);
220 /* rt: Old, cmprt: New */
221 static void ospf_route_delete_uniq(struct route_table
*rt
,
222 struct route_table
*cmprt
)
224 struct route_node
*rn
;
225 struct ospf_route
* or ;
227 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
228 if ((or = rn
->info
) != NULL
)
229 if (or->path_type
== OSPF_PATH_INTRA_AREA
||
230 or->path_type
== OSPF_PATH_INTER_AREA
) {
231 if (or->type
== OSPF_DESTINATION_NETWORK
) {
232 if (!ospf_route_exist_new_table(
234 (struct prefix_ipv4
*)&rn
240 } else if (or->type
== OSPF_DESTINATION_DISCARD
)
241 if (!ospf_route_exist_new_table(
243 (struct prefix_ipv4
*)&rn
245 ospf_zebra_delete_discard(
251 /* Install routes to table. */
252 void ospf_route_install(struct ospf
*ospf
, struct route_table
*rt
)
254 struct route_node
*rn
;
255 struct ospf_route
* or ;
257 /* rt contains new routing table, new_table contains an old one.
260 ospf_route_table_free(ospf
->old_table
);
262 ospf
->old_table
= ospf
->new_table
;
263 ospf
->new_table
= rt
;
265 /* Delete old routes. */
267 ospf_route_delete_uniq(ospf
->old_table
, rt
);
268 if (ospf
->old_external_route
)
269 ospf_route_delete_same_ext(ospf
->old_external_route
, rt
);
271 /* Install new routes. */
272 for (rn
= route_top(rt
); rn
; rn
= route_next(rn
))
273 if ((or = rn
->info
) != NULL
) {
274 if (or->type
== OSPF_DESTINATION_NETWORK
) {
275 if (!ospf_route_match_same(
277 (struct prefix_ipv4
*)&rn
->p
, or))
279 (struct prefix_ipv4
*)&rn
->p
,
281 } else if (or->type
== OSPF_DESTINATION_DISCARD
)
282 if (!ospf_route_match_same(
284 (struct prefix_ipv4
*)&rn
->p
, or))
285 ospf_zebra_add_discard(
286 (struct prefix_ipv4
*)&rn
->p
);
290 /* RFC2328 16.1. (4). For "router". */
291 void ospf_intra_add_router(struct route_table
*rt
, struct vertex
*v
,
292 struct ospf_area
*area
)
294 struct route_node
*rn
;
295 struct ospf_route
* or ;
296 struct prefix_ipv4 p
;
297 struct router_lsa
*lsa
;
299 if (IS_DEBUG_OSPF_EVENT
)
300 zlog_debug("ospf_intra_add_router: Start");
302 lsa
= (struct router_lsa
*)v
->lsa
;
304 if (IS_DEBUG_OSPF_EVENT
)
305 zlog_debug("ospf_intra_add_router: LS ID: %s",
306 inet_ntoa(lsa
->header
.id
));
308 if (!OSPF_IS_AREA_BACKBONE(area
))
309 ospf_vl_up_check(area
, lsa
->header
.id
, v
);
311 if (!CHECK_FLAG(lsa
->flags
, ROUTER_LSA_SHORTCUT
))
312 area
->shortcut_capability
= 0;
314 /* If the newly added vertex is an area border router or AS boundary
315 router, a routing table entry is added whose destination type is
317 if (!IS_ROUTER_LSA_BORDER(lsa
) && !IS_ROUTER_LSA_EXTERNAL(lsa
)) {
318 if (IS_DEBUG_OSPF_EVENT
)
320 "ospf_intra_add_router: "
321 "this router is neither ASBR nor ABR, skipping it");
325 /* Update ABR and ASBR count in this area. */
326 if (IS_ROUTER_LSA_BORDER(lsa
))
328 if (IS_ROUTER_LSA_EXTERNAL(lsa
))
331 /* The Options field found in the associated router-LSA is copied
332 into the routing table entry's Optional capabilities field. Call
333 the newly added vertex Router X. */
334 or = ospf_route_new();
337 or->u
.std
.area_id
= area
->area_id
;
338 or->u
.std
.external_routing
= area
->external_routing
;
339 or->path_type
= OSPF_PATH_INTRA_AREA
;
340 or->cost
= v
->distance
;
341 or->type
= OSPF_DESTINATION_ROUTER
;
342 or->u
.std
.origin
= (struct lsa_header
*)lsa
;
343 or->u
.std
.options
= lsa
->header
.options
;
344 or->u
.std
.flags
= lsa
->flags
;
346 /* If Router X is the endpoint of one of the calculating router's
347 virtual links, and the virtual link uses Area A as Transit area:
348 the virtual link is declared up, the IP address of the virtual
349 interface is set to the IP address of the outgoing interface
350 calculated above for Router X, and the virtual neighbor's IP
351 address is set to Router X's interface address (contained in
352 Router X's router-LSA) that points back to the root of the
353 shortest- path tree; equivalently, this is the interface that
354 points back to Router X's parent vertex on the shortest-path tree
355 (similar to the calculation in Section 16.1.1). */
359 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
);