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