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