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