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