1 /*
2 * OSPF routing table.
3 * Copyright (C) 1999, 2000 Toshiaki Takada
4 *
5 * This file is part of GNU Zebra.
6 *
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
10 * later version.
11 *
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.
16 *
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
20 */
21
22 #include <zebra.h>
23
24 #include "prefix.h"
25 #include "table.h"
26 #include "memory.h"
27 #include "linklist.h"
28 #include "log.h"
29 #include "if.h"
30 #include "command.h"
31 #include "sockunion.h"
32
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"
41
ospf_route_new(void)42 struct ospf_route *ospf_route_new(void)
43 {
44 struct ospf_route *new;
45
46 new = XCALLOC(MTYPE_OSPF_ROUTE, sizeof(struct ospf_route));
47
48 new->paths = list_new();
49 new->paths->del = (void (*)(void *))ospf_path_free;
50
51 return new;
52 }
53
ospf_route_free(struct ospf_route * or)54 void ospf_route_free(struct ospf_route *or)
55 {
56 if (or->paths)
57 list_delete(& or->paths);
58
59 XFREE(MTYPE_OSPF_ROUTE, or);
60 }
61
ospf_path_new(void)62 struct ospf_path *ospf_path_new(void)
63 {
64 struct ospf_path *new;
65
66 new = XCALLOC(MTYPE_OSPF_PATH, sizeof(struct ospf_path));
67
68 return new;
69 }
70
ospf_path_dup(struct ospf_path * path)71 static struct ospf_path *ospf_path_dup(struct ospf_path *path)
72 {
73 struct ospf_path *new;
74
75 new = ospf_path_new();
76 memcpy(new, path, sizeof(struct ospf_path));
77
78 return new;
79 }
80
ospf_path_free(struct ospf_path * op)81 void ospf_path_free(struct ospf_path *op)
82 {
83 XFREE(MTYPE_OSPF_PATH, op);
84 }
85
ospf_route_delete(struct ospf * ospf,struct route_table * rt)86 void ospf_route_delete(struct ospf *ospf, struct route_table *rt)
87 {
88 struct route_node *rn;
89 struct ospf_route * or ;
90
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(
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);
99 }
100 }
101
ospf_route_table_free(struct route_table * rt)102 void ospf_route_table_free(struct route_table *rt)
103 {
104 struct route_node *rn;
105 struct ospf_route * or ;
106
107 for (rn = route_top(rt); rn; rn = route_next(rn))
108 if ((or = rn->info) != NULL) {
109 ospf_route_free(or);
110
111 rn->info = NULL;
112 route_unlock_node(rn);
113 }
114
115 route_table_finish(rt);
116 }
117
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. */
ospf_route_exist_new_table(struct route_table * rt,struct prefix_ipv4 * prefix)122 static int ospf_route_exist_new_table(struct route_table *rt,
123 struct prefix_ipv4 *prefix)
124 {
125 struct route_node *rn;
126
127 assert(rt);
128 assert(prefix);
129
130 rn = route_node_lookup(rt, (struct prefix *)prefix);
131 if (!rn) {
132 return 0;
133 }
134 route_unlock_node(rn);
135
136 if (!rn->info) {
137 return 0;
138 }
139
140 return 1;
141 }
142
143 /* If a prefix and a nexthop match any route in the routing table,
144 then return 1, otherwise return 0. */
ospf_route_match_same(struct route_table * rt,struct prefix_ipv4 * prefix,struct ospf_route * newor)145 int ospf_route_match_same(struct route_table *rt, struct prefix_ipv4 *prefix,
146 struct ospf_route *newor)
147 {
148 struct route_node *rn;
149 struct ospf_route * or ;
150 struct ospf_path *op;
151 struct ospf_path *newop;
152 struct listnode *n1;
153 struct listnode *n2;
154
155 if (!rt || !prefix)
156 return 0;
157
158 rn = route_node_lookup(rt, (struct prefix *)prefix);
159 if (!rn || !rn->info)
160 return 0;
161
162 route_unlock_node(rn);
163
164 or = rn->info;
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)
168 return 0;
169
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);
177
178 if (!IPV4_ADDR_SAME(&op->nexthop,
179 &newop->nexthop))
180 return 0;
181 if (op->ifindex != newop->ifindex)
182 return 0;
183 }
184 return 1;
185 } else if (prefix_same(&rn->p, (struct prefix *)prefix))
186 return 1;
187 }
188 return 0;
189 }
190
191 /* delete routes generated from AS-External routes if there is a inter/intra
192 * area route
193 */
ospf_route_delete_same_ext(struct ospf * ospf,struct route_table * external_routes,struct route_table * routes)194 static void ospf_route_delete_same_ext(struct ospf *ospf,
195 struct route_table *external_routes,
196 struct route_table *routes)
197 {
198 struct route_node *rn, *ext_rn;
199
200 if ((external_routes == NULL) || (routes == NULL))
201 return;
202
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))) {
209 if (ext_rn->info) {
210 ospf_zebra_delete(ospf, p,
211 ext_rn->info);
212 ospf_route_free(ext_rn->info);
213 ext_rn->info = NULL;
214 }
215 route_unlock_node(ext_rn);
216 }
217 }
218 }
219 }
220
221 /* rt: Old, cmprt: New */
ospf_route_delete_uniq(struct ospf * ospf,struct route_table * rt,struct route_table * cmprt)222 static void ospf_route_delete_uniq(struct ospf *ospf, struct route_table *rt,
223 struct route_table *cmprt)
224 {
225 struct route_node *rn;
226 struct ospf_route * or ;
227
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(
234 cmprt,
235 (struct prefix_ipv4 *)&rn
236 ->p))
237 ospf_zebra_delete(
238 ospf,
239 (struct prefix_ipv4
240 *)&rn->p,
241 or);
242 } else if (or->type == OSPF_DESTINATION_DISCARD)
243 if (!ospf_route_exist_new_table(
244 cmprt,
245 (struct prefix_ipv4 *)&rn
246 ->p))
247 ospf_zebra_delete_discard(
248 ospf,
249 (struct prefix_ipv4
250 *)&rn->p);
251 }
252 }
253
254 /* Install routes to table. */
ospf_route_install(struct ospf * ospf,struct route_table * rt)255 void ospf_route_install(struct ospf *ospf, struct route_table *rt)
256 {
257 struct route_node *rn;
258 struct ospf_route * or ;
259
260 /* rt contains new routing table, new_table contains an old one.
261 updating pointers */
262 if (ospf->old_table)
263 ospf_route_table_free(ospf->old_table);
264
265 ospf->old_table = ospf->new_table;
266 ospf->new_table = rt;
267
268 /* Delete old routes. */
269 if (ospf->old_table)
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);
273
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(
279 ospf->old_table,
280 (struct prefix_ipv4 *)&rn->p, or))
281 ospf_zebra_add(
282 ospf,
283 (struct prefix_ipv4 *)&rn->p,
284 or);
285 } else if (or->type == OSPF_DESTINATION_DISCARD)
286 if (!ospf_route_match_same(
287 ospf->old_table,
288 (struct prefix_ipv4 *)&rn->p, or))
289 ospf_zebra_add_discard(
290 ospf,
291 (struct prefix_ipv4 *)&rn->p);
292 }
293 }
294
295 /* RFC2328 16.1. (4). For "router". */
ospf_intra_add_router(struct route_table * rt,struct vertex * v,struct ospf_area * area)296 void ospf_intra_add_router(struct route_table *rt, struct vertex *v,
297 struct ospf_area *area)
298 {
299 struct route_node *rn;
300 struct ospf_route * or ;
301 struct prefix_ipv4 p;
302 struct router_lsa *lsa;
303
304 if (IS_DEBUG_OSPF_EVENT)
305 zlog_debug("ospf_intra_add_router: Start");
306
307 lsa = (struct router_lsa *)v->lsa;
308
309 if (IS_DEBUG_OSPF_EVENT)
310 zlog_debug("ospf_intra_add_router: LS ID: %s",
311 inet_ntoa(lsa->header.id));
312
313 if (!OSPF_IS_AREA_BACKBONE(area))
314 ospf_vl_up_check(area, lsa->header.id, v);
315
316 if (!CHECK_FLAG(lsa->flags, ROUTER_LSA_SHORTCUT))
317 area->shortcut_capability = 0;
318
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
321 "router". */
322 if (!IS_ROUTER_LSA_BORDER(lsa) && !IS_ROUTER_LSA_EXTERNAL(lsa)) {
323 if (IS_DEBUG_OSPF_EVENT)
324 zlog_debug(
325 "ospf_intra_add_router: this router is neither ASBR nor ABR, skipping it");
326 return;
327 }
328
329 /* Update ABR and ASBR count in this area. */
330 if (IS_ROUTER_LSA_BORDER(lsa))
331 area->abr_count++;
332 if (IS_ROUTER_LSA_EXTERNAL(lsa))
333 area->asbr_count++;
334
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();
339
340 or->id = v->id;
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;
349
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). */
360
361 p.family = AF_INET;
362 p.prefix = v->id;
363 p.prefixlen = IPV4_MAX_BITLEN;
364 apply_mask_ipv4(&p);
365
366 if (IS_DEBUG_OSPF_EVENT)
367 zlog_debug("ospf_intra_add_router: talking about %s/%d",
368 inet_ntoa(p.prefix), p.prefixlen);
369
370 rn = route_node_get(rt, (struct prefix *)&p);
371
372 /* Note that we keep all routes to ABRs and ASBRs, not only the best */
373 if (rn->info == NULL)
374 rn->info = list_new();
375 else
376 route_unlock_node(rn);
377
378 ospf_route_copy_nexthops_from_vertex(area, or, v);
379
380 listnode_add(rn->info, or);
381
382 if (IS_DEBUG_OSPF_EVENT)
383 zlog_debug("ospf_intra_add_router: Stop");
384 }
385
386 /* RFC2328 16.1. (4). For transit network. */
ospf_intra_add_transit(struct route_table * rt,struct vertex * v,struct ospf_area * area)387 void ospf_intra_add_transit(struct route_table *rt, struct vertex *v,
388 struct ospf_area *area)
389 {
390 struct route_node *rn;
391 struct ospf_route * or ;
392 struct prefix_ipv4 p;
393 struct network_lsa *lsa;
394
395 lsa = (struct network_lsa *)v->lsa;
396
397 /* If the newly added vertex is a transit network, the routing table
398 entry for the network is located. The entry's Destination ID is
399 the IP network number, which can be obtained by masking the
400 Vertex ID (Link State ID) with its associated subnet mask (found
401 in the body of the associated network-LSA). */
402 p.family = AF_INET;
403 p.prefix = v->id;
404 p.prefixlen = ip_masklen(lsa->mask);
405 apply_mask_ipv4(&p);
406
407 rn = route_node_get(rt, (struct prefix *)&p);
408
409 /* If the routing table entry already exists (i.e., there is already
410 an intra-area route to the destination installed in the routing
411 table), multiple vertices have mapped to the same IP network.
412 For example, this can occur when a new Designated Router is being
413 established. In this case, the current routing table entry
414 should be overwritten if and only if the newly found path is just
415 as short and the current routing table entry's Link State Origin
416 has a smaller Link State ID than the newly added vertex' LSA. */
417 if (rn->info) {
418 struct ospf_route *cur_or;
419
420 route_unlock_node(rn);
421 cur_or = rn->info;
422
423 if (v->distance > cur_or->cost
424 || IPV4_ADDR_CMP(&cur_or->u.std.origin->id, &lsa->header.id)
425 > 0)
426 return;
427
428 ospf_route_free(rn->info);
429 }
430
431 or = ospf_route_new();
432
433 or->id = v->id;
434 or->u.std.area_id = area->area_id;
435 or->u.std.external_routing = area->external_routing;
436 or->path_type = OSPF_PATH_INTRA_AREA;
437 or->cost = v->distance;
438 or->type = OSPF_DESTINATION_NETWORK;
439 or->u.std.origin = (struct lsa_header *)lsa;
440
441 ospf_route_copy_nexthops_from_vertex(area, or, v);
442
443 rn->info = or ;
444 }
445
446 /* RFC2328 16.1. second stage. */
ospf_intra_add_stub(struct route_table * rt,struct router_lsa_link * link,struct vertex * v,struct ospf_area * area,int parent_is_root,int lsa_pos)447 void ospf_intra_add_stub(struct route_table *rt, struct router_lsa_link *link,
448 struct vertex *v, struct ospf_area *area,
449 int parent_is_root, int lsa_pos)
450 {
451 uint32_t cost;
452 struct route_node *rn;
453 struct ospf_route * or ;
454 struct prefix_ipv4 p;
455 struct router_lsa *lsa;
456 struct ospf_interface *oi = NULL;
457 struct ospf_path *path;
458
459 if (IS_DEBUG_OSPF_EVENT)
460 zlog_debug("ospf_intra_add_stub(): Start");
461
462 lsa = (struct router_lsa *)v->lsa;
463
464 p.family = AF_INET;
465 p.prefix = link->link_id;
466 p.prefixlen = ip_masklen(link->link_data);
467 apply_mask_ipv4(&p);
468
469 if (IS_DEBUG_OSPF_EVENT)
470 zlog_debug("ospf_intra_add_stub(): processing route to %s/%d",
471 inet_ntoa(p.prefix), p.prefixlen);
472
473 /* (1) Calculate the distance D of stub network from the root. D is
474 equal to the distance from the root to the router vertex
475 (calculated in stage 1), plus the stub network link's advertised
476 cost. */
477 cost = v->distance + ntohs(link->m[0].metric);
478
479 if (IS_DEBUG_OSPF_EVENT)
480 zlog_debug(
481 "ospf_intra_add_stub(): calculated cost is %d + %d = %d",
482 v->distance, ntohs(link->m[0].metric), cost);
483
484 /* PtP links with /32 masks adds host routes to remote, directly
485 * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
486 * Such routes can just be ignored for the sake of tidyness.
487 */
488 if (parent_is_root && link->link_data.s_addr == 0xffffffff
489 && ospf_if_lookup_by_local_addr(area->ospf, NULL, link->link_id)) {
490 if (IS_DEBUG_OSPF_EVENT)
491 zlog_debug("%s: ignoring host route %s/32 to self.",
492 __func__, inet_ntoa(link->link_id));
493 return;
494 }
495
496 rn = route_node_get(rt, (struct prefix *)&p);
497
498 /* Lookup current routing table. */
499 if (rn->info) {
500 struct ospf_route *cur_or;
501
502 route_unlock_node(rn);
503
504 cur_or = rn->info;
505
506 if (IS_DEBUG_OSPF_EVENT)
507 zlog_debug(
508 "ospf_intra_add_stub(): another route to the same prefix found with cost %u",
509 cur_or->cost);
510
511 /* Compare this distance to the current best cost to the stub
512 network. This is done by looking up the stub network's
513 current routing table entry. If the calculated distance D is
514 larger, go on to examine the next stub network link in the
515 LSA. */
516 if (cost > cur_or->cost) {
517 if (IS_DEBUG_OSPF_EVENT)
518 zlog_debug(
519 "ospf_intra_add_stub(): old route is better, exit");
520 return;
521 }
522
523 /* (2) If this step is reached, the stub network's routing table
524 entry must be updated. Calculate the set of next hops that
525 would result from using the stub network link. This
526 calculation is shown in Section 16.1.1; input to this
527 calculation is the destination (the stub network) and the
528 parent vertex (the router vertex). If the distance D is the
529 same as the current routing table cost, simply add this set
530 of next hops to the routing table entry's list of next hops.
531 In this case, the routing table already has a Link State
532 Origin. If this Link State Origin is a router-LSA whose Link
533 State ID is smaller than V's Router ID, reset the Link State
534 Origin to V's router-LSA. */
535
536 if (cost == cur_or->cost) {
537 if (IS_DEBUG_OSPF_EVENT)
538 zlog_debug(
539 "ospf_intra_add_stub(): routes are equal, merge");
540
541 ospf_route_copy_nexthops_from_vertex(area, cur_or, v);
542
543 if (IPV4_ADDR_CMP(&cur_or->u.std.origin->id,
544 &lsa->header.id)
545 < 0)
546 cur_or->u.std.origin = (struct lsa_header *)lsa;
547 return;
548 }
549
550 /* Otherwise D is smaller than the routing table cost.
551 Overwrite the current routing table entry by setting the
552 routing table entry's cost to D, and by setting the entry's
553 list of next hops to the newly calculated set. Set the
554 routing table entry's Link State Origin to V's router-LSA.
555 Then go on to examine the next stub network link. */
556
557 if (cost < cur_or->cost) {
558 if (IS_DEBUG_OSPF_EVENT)
559 zlog_debug(
560 "ospf_intra_add_stub(): new route is better, set it");
561
562 cur_or->cost = cost;
563
564 list_delete_all_node(cur_or->paths);
565
566 ospf_route_copy_nexthops_from_vertex(area, cur_or, v);
567
568 cur_or->u.std.origin = (struct lsa_header *)lsa;
569 return;
570 }
571 }
572
573 if (IS_DEBUG_OSPF_EVENT)
574 zlog_debug("ospf_intra_add_stub(): installing new route");
575
576 or = ospf_route_new();
577
578 or->id = v->id;
579 or->u.std.area_id = area->area_id;
580 or->u.std.external_routing = area->external_routing;
581 or->path_type = OSPF_PATH_INTRA_AREA;
582 or->cost = cost;
583 or->type = OSPF_DESTINATION_NETWORK;
584 or->u.std.origin = (struct lsa_header *)lsa;
585
586 /* Nexthop is depend on connection type. */
587 if (v != area->spf) {
588 if (IS_DEBUG_OSPF_EVENT)
589 zlog_debug(
590 "ospf_intra_add_stub(): this network is on remote router");
591 ospf_route_copy_nexthops_from_vertex(area, or, v);
592 } else {
593 if (IS_DEBUG_OSPF_EVENT)
594 zlog_debug(
595 "ospf_intra_add_stub(): this network is on this router");
596
597 /*
598 * Only deal with interface data when we
599 * don't do a dry run
600 */
601 if (!area->spf_dry_run)
602 oi = ospf_if_lookup_by_lsa_pos(area, lsa_pos);
603
604 if (oi || area->spf_dry_run) {
605 if (IS_DEBUG_OSPF_EVENT)
606 zlog_debug(
607 "ospf_intra_add_stub(): the lsa pos is %d",
608 lsa_pos);
609
610 path = ospf_path_new();
611 path->nexthop.s_addr = INADDR_ANY;
612
613 if (oi) {
614 path->ifindex = oi->ifp->ifindex;
615 if (CHECK_FLAG(oi->connected->flags,
616 ZEBRA_IFA_UNNUMBERED))
617 path->unnumbered = 1;
618 }
619
620 listnode_add(or->paths, path);
621 } else {
622 if (IS_DEBUG_OSPF_EVENT)
623 zlog_debug(
624 "ospf_intra_add_stub(): where's the interface ?");
625 }
626 }
627
628 rn->info = or ;
629
630 if (IS_DEBUG_OSPF_EVENT)
631 zlog_debug("ospf_intra_add_stub(): Stop");
632 }
633
634 static const char *const ospf_path_type_str[] = {
635 "unknown-type", "intra-area", "inter-area", "type1-external",
636 "type2-external"
637 };
638
ospf_route_table_dump(struct route_table * rt)639 void ospf_route_table_dump(struct route_table *rt)
640 {
641 struct route_node *rn;
642 struct ospf_route * or ;
643 struct listnode *pnode;
644 struct ospf_path *path;
645
646 zlog_debug("========== OSPF routing table ==========");
647 for (rn = route_top(rt); rn; rn = route_next(rn))
648 if ((or = rn->info) != NULL) {
649 if (or->type == OSPF_DESTINATION_NETWORK) {
650 zlog_debug("N %-18pFX %-15pI4 %s %d", &rn->p,
651 &or->u.std.area_id,
652 ospf_path_type_str[or->path_type],
653 or->cost);
654 for (ALL_LIST_ELEMENTS_RO(or->paths, pnode,
655 path))
656 zlog_debug(" -> %s",
657 inet_ntoa(path->nexthop));
658 } else
659 zlog_debug("R %-18pI4 %-15pI4 %s %d",
660 &rn->p.u.prefix4,
661 &or->u.std.area_id,
662 ospf_path_type_str[or->path_type],
663 or->cost);
664 }
665 zlog_debug("========================================");
666 }
667
ospf_route_table_print(struct vty * vty,struct route_table * rt)668 void ospf_route_table_print(struct vty *vty, struct route_table *rt)
669 {
670 struct route_node *rn;
671 struct ospf_route * or ;
672 struct listnode *pnode;
673 struct ospf_path *path;
674
675 vty_out(vty, "========== OSPF routing table ==========\n");
676 for (rn = route_top(rt); rn; rn = route_next(rn))
677 if ((or = rn->info) != NULL) {
678 if (or->type == OSPF_DESTINATION_NETWORK) {
679 vty_out(vty, "N %-18pFX %-15pI4 %s %d\n",
680 &rn->p, & or->u.std.area_id,
681 ospf_path_type_str[or->path_type],
682 or->cost);
683 for (ALL_LIST_ELEMENTS_RO(or->paths, pnode,
684 path))
685 vty_out(vty, " -> %s\n",
686 path->nexthop.s_addr != 0
687 ? inet_ntoa(
688 path->nexthop)
689 : "directly connected");
690 } else
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],
694 or->cost);
695 }
696 vty_out(vty, "========================================\n");
697 }
698
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. */
ospf_asbr_route_cmp(struct ospf * ospf,struct ospf_route * r1,struct ospf_route * r2)703 static int ospf_asbr_route_cmp(struct ospf *ospf, struct ospf_route *r1,
704 struct ospf_route *r2)
705 {
706 uint8_t r1_type, r2_type;
707
708 r1_type = r1->path_type;
709 r2_type = r2->path_type;
710
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;
716
717 return (r1_type - r2_type);
718 }
719
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. */
ospf_route_cmp(struct ospf * ospf,struct ospf_route * r1,struct ospf_route * r2)724 int ospf_route_cmp(struct ospf *ospf, struct ospf_route *r1,
725 struct ospf_route *r2)
726 {
727 int ret = 0;
728
729 /* Path types of r1 and r2 are not the same. */
730 if ((ret = (r1->path_type - r2->path_type)))
731 return ret;
732
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:
739 break;
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,
743 r2->u.ext.asbr);
744 if (ret != 0)
745 return ret;
746 }
747 break;
748 case OSPF_PATH_TYPE2_EXTERNAL:
749 if ((ret = (r1->u.ext.type2_cost - r2->u.ext.type2_cost)))
750 return ret;
751
752 if (!CHECK_FLAG(ospf->config, OSPF_RFC1583_COMPATIBLE)) {
753 ret = ospf_asbr_route_cmp(ospf, r1->u.ext.asbr,
754 r2->u.ext.asbr);
755 if (ret != 0)
756 return ret;
757 }
758 break;
759 }
760
761 /* Anyway, compare the costs. */
762 return (r1->cost - r2->cost);
763 }
764
ospf_path_exist(struct list * plist,struct in_addr nexthop,struct ospf_interface * oi)765 static int ospf_path_exist(struct list *plist, struct in_addr nexthop,
766 struct ospf_interface *oi)
767 {
768 struct listnode *node, *nnode;
769 struct ospf_path *path;
770
771 for (ALL_LIST_ELEMENTS(plist, node, nnode, path))
772 if (IPV4_ADDR_SAME(&path->nexthop, &nexthop)
773 && path->ifindex == oi->ifp->ifindex)
774 return 1;
775
776 return 0;
777 }
778
ospf_route_copy_nexthops_from_vertex(struct ospf_area * area,struct ospf_route * to,struct vertex * v)779 void ospf_route_copy_nexthops_from_vertex(struct ospf_area *area,
780 struct ospf_route *to,
781 struct vertex *v)
782 {
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;
788
789 assert(to->paths);
790
791 for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) {
792 nexthop = vp->nexthop;
793
794 /*
795 * Only deal with interface data when we
796 * don't do a dry run
797 */
798 if (!area->spf_dry_run)
799 oi = ospf_if_lookup_by_lsa_pos(area, nexthop->lsa_pos);
800
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;
805
806 if (oi) {
807 path->ifindex = oi->ifp->ifindex;
808 if (CHECK_FLAG(oi->connected->flags,
809 ZEBRA_IFA_UNNUMBERED))
810 path->unnumbered = 1;
811 }
812
813 listnode_add(to->paths, path);
814 }
815 }
816 }
817
ospf_path_lookup(struct list * plist,struct ospf_path * path)818 struct ospf_path *ospf_path_lookup(struct list *plist, struct ospf_path *path)
819 {
820 struct listnode *node;
821 struct ospf_path *op;
822
823 for (ALL_LIST_ELEMENTS_RO(plist, node, op)) {
824 if (!IPV4_ADDR_SAME(&op->nexthop, &path->nexthop))
825 continue;
826 if (!IPV4_ADDR_SAME(&op->adv_router, &path->adv_router))
827 continue;
828 if (op->ifindex != path->ifindex)
829 continue;
830 return op;
831 }
832 return NULL;
833 }
834
ospf_route_copy_nexthops(struct ospf_route * to,struct list * from)835 void ospf_route_copy_nexthops(struct ospf_route *to, struct list *from)
836 {
837 struct listnode *node, *nnode;
838 struct ospf_path *path;
839
840 assert(to->paths);
841
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));
846 }
847
ospf_route_subst_nexthops(struct ospf_route * to,struct list * from)848 void ospf_route_subst_nexthops(struct ospf_route *to, struct list *from)
849 {
850
851 list_delete_all_node(to->paths);
852 ospf_route_copy_nexthops(to, from);
853 }
854
ospf_route_subst(struct route_node * rn,struct ospf_route * new_or,struct ospf_route * over)855 void ospf_route_subst(struct route_node *rn, struct ospf_route *new_or,
856 struct ospf_route *over)
857 {
858 route_lock_node(rn);
859 ospf_route_free(rn->info);
860
861 ospf_route_copy_nexthops(new_or, over->paths);
862 rn->info = new_or;
863 route_unlock_node(rn);
864 }
865
ospf_route_add(struct route_table * rt,struct prefix_ipv4 * p,struct ospf_route * new_or,struct ospf_route * over)866 void ospf_route_add(struct route_table *rt, struct prefix_ipv4 *p,
867 struct ospf_route *new_or, struct ospf_route *over)
868 {
869 struct route_node *rn;
870
871 rn = route_node_get(rt, (struct prefix *)p);
872
873 ospf_route_copy_nexthops(new_or, over->paths);
874
875 if (rn->info) {
876 if (IS_DEBUG_OSPF_EVENT)
877 zlog_debug("ospf_route_add(): something's wrong !");
878 route_unlock_node(rn);
879 return;
880 }
881
882 rn->info = new_or;
883 }
884
ospf_prune_unreachable_networks(struct route_table * rt)885 void ospf_prune_unreachable_networks(struct route_table *rt)
886 {
887 struct route_node *rn, *next;
888 struct ospf_route * or ;
889
890 if (IS_DEBUG_OSPF_EVENT)
891 zlog_debug("Pruning unreachable networks");
892
893 for (rn = route_top(rt); rn; rn = next) {
894 next = route_next(rn);
895 if (rn->info != NULL) {
896 or = rn->info;
897 if (listcount(or->paths) == 0) {
898 if (IS_DEBUG_OSPF_EVENT)
899 zlog_debug("Pruning route to %s/%d",
900 inet_ntoa(rn->p.u.prefix4),
901 rn->p.prefixlen);
902
903 ospf_route_free(or);
904 rn->info = NULL;
905 route_unlock_node(rn);
906 }
907 }
908 }
909 }
910
ospf_prune_unreachable_routers(struct route_table * rtrs)911 void ospf_prune_unreachable_routers(struct route_table *rtrs)
912 {
913 struct route_node *rn, *next;
914 struct ospf_route * or ;
915 struct listnode *node, *nnode;
916 struct list *paths;
917
918 if (IS_DEBUG_OSPF_EVENT)
919 zlog_debug("Pruning unreachable routers");
920
921 for (rn = route_top(rtrs); rn; rn = next) {
922 next = route_next(rn);
923 if ((paths = rn->info) == NULL)
924 continue;
925
926 for (ALL_LIST_ELEMENTS(paths, node, nnode, or)) {
927 if (listcount(or->paths) == 0) {
928 if (IS_DEBUG_OSPF_EVENT) {
929 zlog_debug("Pruning route to rtr %s",
930 inet_ntoa(rn->p.u.prefix4));
931 zlog_debug(
932 " via area %s",
933 inet_ntoa(or->u.std.area_id));
934 }
935
936 listnode_delete(paths, or);
937 ospf_route_free(or);
938 }
939 }
940
941 if (listcount(paths) == 0) {
942 if (IS_DEBUG_OSPF_EVENT)
943 zlog_debug("Pruning router node %s",
944 inet_ntoa(rn->p.u.prefix4));
945
946 list_delete(&paths);
947 rn->info = NULL;
948 route_unlock_node(rn);
949 }
950 }
951 }
952
ospf_add_discard_route(struct ospf * ospf,struct route_table * rt,struct ospf_area * area,struct prefix_ipv4 * p)953 int ospf_add_discard_route(struct ospf *ospf, struct route_table *rt,
954 struct ospf_area *area, struct prefix_ipv4 *p)
955 {
956 struct route_node *rn;
957 struct ospf_route * or, *new_or;
958
959 rn = route_node_get(rt, (struct prefix *)p);
960
961 if (rn == NULL) {
962 if (IS_DEBUG_OSPF_EVENT)
963 zlog_debug(
964 "ospf_add_discard_route(): router installation error");
965 return 0;
966 }
967
968 if (rn->info) /* If the route to the same destination is found */
969 {
970 route_unlock_node(rn);
971
972 or = rn->info;
973
974 if (or->path_type == OSPF_PATH_INTRA_AREA) {
975 if (IS_DEBUG_OSPF_EVENT)
976 zlog_debug(
977 "ospf_add_discard_route(): an intra-area route exists");
978 return 0;
979 }
980
981 if (or->type == OSPF_DESTINATION_DISCARD) {
982 if (IS_DEBUG_OSPF_EVENT)
983 zlog_debug(
984 "ospf_add_discard_route(): discard entry already installed");
985 return 0;
986 }
987
988 ospf_route_free(rn->info);
989 }
990
991 if (IS_DEBUG_OSPF_EVENT)
992 zlog_debug(
993 "ospf_add_discard_route(): adding %s/%d",
994 inet_ntoa(p->prefix), p->prefixlen);
995
996 new_or = ospf_route_new();
997 new_or->type = OSPF_DESTINATION_DISCARD;
998 new_or->id.s_addr = INADDR_ANY;
999 new_or->cost = 0;
1000 new_or->u.std.area_id = area->area_id;
1001 new_or->u.std.external_routing = area->external_routing;
1002 new_or->path_type = OSPF_PATH_INTER_AREA;
1003 rn->info = new_or;
1004
1005 ospf_zebra_add_discard(ospf, p);
1006
1007 return 1;
1008 }
1009
ospf_delete_discard_route(struct ospf * ospf,struct route_table * rt,struct prefix_ipv4 * p)1010 void ospf_delete_discard_route(struct ospf *ospf, struct route_table *rt,
1011 struct prefix_ipv4 *p)
1012 {
1013 struct route_node *rn;
1014 struct ospf_route * or ;
1015
1016 if (IS_DEBUG_OSPF_EVENT)
1017 zlog_debug(
1018 "ospf_delete_discard_route(): deleting %s/%d",
1019 inet_ntoa(p->prefix), p->prefixlen);
1020
1021 rn = route_node_lookup(rt, (struct prefix *)p);
1022
1023 if (rn == NULL) {
1024 if (IS_DEBUG_OSPF_EVENT)
1025 zlog_debug(
1026 "ospf_delete_discard_route(): no route found");
1027 return;
1028 }
1029
1030 or = rn->info;
1031
1032 if (or->path_type == OSPF_PATH_INTRA_AREA) {
1033 if (IS_DEBUG_OSPF_EVENT)
1034 zlog_debug(
1035 "ospf_delete_discard_route(): an intra-area route exists");
1036 return;
1037 }
1038
1039 if (or->type != OSPF_DESTINATION_DISCARD) {
1040 if (IS_DEBUG_OSPF_EVENT)
1041 zlog_debug(
1042 "ospf_delete_discard_route(): not a discard entry");
1043 return;
1044 }
1045
1046 /* free the route entry and the route node */
1047 ospf_route_free(rn->info);
1048
1049 rn->info = NULL;
1050 route_unlock_node(rn);
1051 route_unlock_node(rn);
1052
1053 /* remove the discard entry from the rib */
1054 ospf_zebra_delete_discard(ospf, p);
1055
1056 return;
1057 }
1058