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