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