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