]>
Commit | Line | Data |
---|---|---|
718e3744 | 1 | /* |
508e53e2 | 2 | * Copyright (C) 2003 Yasuhiro Ohara |
718e3744 | 3 | * |
4 | * This file is part of GNU Zebra. | |
5 | * | |
6 | * GNU Zebra is free software; you can redistribute it and/or modify it | |
7 | * under the terms of the GNU General Public License as published by the | |
8 | * Free Software Foundation; either version 2, or (at your option) any | |
9 | * later version. | |
10 | * | |
11 | * GNU Zebra is distributed in the hope that it will be useful, but | |
12 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | * General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU General Public License | |
17 | * along with GNU Zebra; see the file COPYING. If not, write to the | |
18 | * Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
19 | * Boston, MA 02111-1307, USA. | |
20 | */ | |
508e53e2 | 21 | |
718e3744 | 22 | /* Shortest Path First calculation for OSPFv3 */ |
23 | ||
508e53e2 | 24 | #include <zebra.h> |
718e3744 | 25 | |
508e53e2 | 26 | #include "log.h" |
27 | #include "memory.h" | |
28 | #include "command.h" | |
29 | #include "vty.h" | |
718e3744 | 30 | #include "prefix.h" |
508e53e2 | 31 | #include "pqueue.h" |
32 | #include "linklist.h" | |
33 | #include "thread.h" | |
718e3744 | 34 | |
718e3744 | 35 | #include "ospf6_lsa.h" |
36 | #include "ospf6_lsdb.h" | |
37 | #include "ospf6_route.h" | |
508e53e2 | 38 | #include "ospf6_area.h" |
718e3744 | 39 | #include "ospf6_spf.h" |
508e53e2 | 40 | #include "ospf6_intra.h" |
718e3744 | 41 | #include "ospf6_interface.h" |
049207c3 | 42 | #include "ospf6d.h" |
718e3744 | 43 | |
508e53e2 | 44 | unsigned char conf_debug_ospf6_spf = 0; |
718e3744 | 45 | |
46 | int | |
508e53e2 | 47 | ospf6_vertex_cmp (void *a, void *b) |
718e3744 | 48 | { |
508e53e2 | 49 | struct ospf6_vertex *va = (struct ospf6_vertex *) a; |
50 | struct ospf6_vertex *vb = (struct ospf6_vertex *) b; | |
718e3744 | 51 | |
508e53e2 | 52 | /* ascending order */ |
53 | return (va->cost - vb->cost); | |
718e3744 | 54 | } |
55 | ||
508e53e2 | 56 | int |
57 | ospf6_vertex_id_cmp (void *a, void *b) | |
718e3744 | 58 | { |
508e53e2 | 59 | struct ospf6_vertex *va = (struct ospf6_vertex *) a; |
60 | struct ospf6_vertex *vb = (struct ospf6_vertex *) b; | |
61 | int ret = 0; | |
718e3744 | 62 | |
508e53e2 | 63 | ret = ntohl (ospf6_linkstate_prefix_adv_router (&va->vertex_id)) - |
64 | ntohl (ospf6_linkstate_prefix_adv_router (&vb->vertex_id)); | |
65 | if (ret) | |
66 | return ret; | |
718e3744 | 67 | |
508e53e2 | 68 | ret = ntohl (ospf6_linkstate_prefix_id (&va->vertex_id)) - |
69 | ntohl (ospf6_linkstate_prefix_id (&vb->vertex_id)); | |
718e3744 | 70 | return ret; |
71 | } | |
72 | ||
508e53e2 | 73 | struct ospf6_vertex * |
74 | ospf6_vertex_create (struct ospf6_lsa *lsa) | |
718e3744 | 75 | { |
508e53e2 | 76 | struct ospf6_vertex *v; |
77 | int i; | |
718e3744 | 78 | |
508e53e2 | 79 | v = (struct ospf6_vertex *) |
80 | XMALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_vertex)); | |
718e3744 | 81 | |
508e53e2 | 82 | /* type */ |
83 | if (ntohs (lsa->header->type) == OSPF6_LSTYPE_ROUTER) | |
84 | v->type = OSPF6_VERTEX_TYPE_ROUTER; | |
85 | else if (ntohs (lsa->header->type) == OSPF6_LSTYPE_NETWORK) | |
86 | v->type = OSPF6_VERTEX_TYPE_NETWORK; | |
718e3744 | 87 | else |
508e53e2 | 88 | assert (0); |
718e3744 | 89 | |
508e53e2 | 90 | /* vertex_id */ |
91 | ospf6_linkstate_prefix (lsa->header->adv_router, lsa->header->id, | |
92 | &v->vertex_id); | |
718e3744 | 93 | |
508e53e2 | 94 | /* name */ |
95 | ospf6_linkstate_prefix2str (&v->vertex_id, v->name, sizeof (v->name)); | |
718e3744 | 96 | |
508e53e2 | 97 | /* Associated LSA */ |
98 | v->lsa = lsa; | |
718e3744 | 99 | |
508e53e2 | 100 | /* capability bits + options */ |
101 | v->capability = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header)); | |
102 | v->options[0] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 1); | |
103 | v->options[1] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 2); | |
104 | v->options[2] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 3); | |
718e3744 | 105 | |
508e53e2 | 106 | for (i = 0; i < OSPF6_MULTI_PATH_LIMIT; i++) |
107 | ospf6_nexthop_clear (&v->nexthop[i]); | |
718e3744 | 108 | |
508e53e2 | 109 | v->parent = NULL; |
110 | v->child_list = list_new (); | |
111 | v->child_list->cmp = ospf6_vertex_id_cmp; | |
718e3744 | 112 | |
508e53e2 | 113 | return v; |
718e3744 | 114 | } |
115 | ||
508e53e2 | 116 | void |
117 | ospf6_vertex_delete (struct ospf6_vertex *v) | |
718e3744 | 118 | { |
508e53e2 | 119 | list_delete (v->child_list); |
120 | XFREE (MTYPE_OSPF6_VERTEX, v); | |
718e3744 | 121 | } |
122 | ||
508e53e2 | 123 | struct ospf6_lsa * |
124 | ospf6_lsdesc_lsa (caddr_t lsdesc, struct ospf6_vertex *v) | |
718e3744 | 125 | { |
508e53e2 | 126 | struct ospf6_lsa *lsa; |
127 | u_int16_t type = 0; | |
128 | u_int32_t id = 0, adv_router = 0; | |
718e3744 | 129 | |
508e53e2 | 130 | if (VERTEX_IS_TYPE (NETWORK, v)) |
718e3744 | 131 | { |
508e53e2 | 132 | type = htons (OSPF6_LSTYPE_ROUTER); |
133 | id = htonl (0); | |
134 | adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc); | |
718e3744 | 135 | } |
136 | else | |
137 | { | |
508e53e2 | 138 | if (ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc)) |
718e3744 | 139 | { |
508e53e2 | 140 | type = htons (OSPF6_LSTYPE_ROUTER); |
718e3744 | 141 | id = htonl (0); |
508e53e2 | 142 | adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc); |
718e3744 | 143 | } |
508e53e2 | 144 | else if (ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, lsdesc)) |
718e3744 | 145 | { |
508e53e2 | 146 | type = htons (OSPF6_LSTYPE_NETWORK); |
147 | id = htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc)); | |
148 | adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc); | |
718e3744 | 149 | } |
718e3744 | 150 | } |
151 | ||
508e53e2 | 152 | lsa = ospf6_lsdb_lookup (type, id, adv_router, v->area->lsdb); |
718e3744 | 153 | |
508e53e2 | 154 | if (IS_OSPF6_DEBUG_SPF (DETAIL)) |
718e3744 | 155 | { |
508e53e2 | 156 | char ibuf[16], abuf[16]; |
157 | inet_ntop (AF_INET, &id, ibuf, sizeof (ibuf)); | |
158 | inet_ntop (AF_INET, &adv_router, abuf, sizeof (abuf)); | |
159 | if (lsa) | |
160 | zlog_info (" Link to: %s", lsa->name); | |
161 | else | |
162 | zlog_info (" Link to: [%s Id:%s Adv:%s] No LSA", | |
163 | OSPF6_LSTYPE_NAME (type), ibuf, abuf); | |
718e3744 | 164 | } |
165 | ||
508e53e2 | 166 | return lsa; |
718e3744 | 167 | } |
168 | ||
508e53e2 | 169 | char * |
170 | ospf6_lsdesc_backlink (struct ospf6_lsa *lsa, | |
171 | caddr_t lsdesc, struct ospf6_vertex *v) | |
718e3744 | 172 | { |
508e53e2 | 173 | caddr_t backlink, found = NULL; |
174 | int size; | |
718e3744 | 175 | |
508e53e2 | 176 | size = (OSPF6_LSA_IS_TYPE (ROUTER, lsa) ? |
177 | sizeof (struct ospf6_router_lsdesc) : | |
178 | sizeof (struct ospf6_network_lsdesc)); | |
179 | for (backlink = OSPF6_LSA_HEADER_END (lsa->header) + 4; | |
180 | backlink + size <= OSPF6_LSA_END (lsa->header); backlink += size) | |
718e3744 | 181 | { |
508e53e2 | 182 | assert (! (OSPF6_LSA_IS_TYPE (NETWORK, lsa) && |
183 | VERTEX_IS_TYPE (NETWORK, v))); | |
718e3744 | 184 | |
508e53e2 | 185 | if (OSPF6_LSA_IS_TYPE (NETWORK, lsa) && |
186 | NETWORK_LSDESC_GET_NBR_ROUTERID (backlink) | |
187 | == v->lsa->header->adv_router) | |
188 | found = backlink; | |
189 | else if (VERTEX_IS_TYPE (NETWORK, v) && | |
190 | ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, backlink) && | |
191 | ROUTER_LSDESC_GET_NBR_ROUTERID (backlink) | |
192 | == v->lsa->header->adv_router && | |
193 | ROUTER_LSDESC_GET_NBR_IFID (backlink) | |
194 | == ntohl (v->lsa->header->id)) | |
195 | found = backlink; | |
196 | else | |
197 | { | |
198 | if (! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, backlink) || | |
199 | ! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc)) | |
200 | continue; | |
201 | if (ROUTER_LSDESC_GET_NBR_IFID (backlink) != | |
202 | ROUTER_LSDESC_GET_IFID (lsdesc) || | |
203 | ROUTER_LSDESC_GET_NBR_IFID (lsdesc) != | |
204 | ROUTER_LSDESC_GET_IFID (backlink)) | |
205 | continue; | |
206 | if (ROUTER_LSDESC_GET_NBR_ROUTERID (backlink) != | |
207 | v->lsa->header->adv_router || | |
208 | ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc) != | |
209 | lsa->header->adv_router) | |
210 | continue; | |
211 | found = backlink; | |
212 | } | |
718e3744 | 213 | } |
718e3744 | 214 | |
508e53e2 | 215 | if (IS_OSPF6_DEBUG_SPF (DETAIL)) |
216 | zlog_info (" Backlink %s", (found ? "OK" : "FAIL")); | |
718e3744 | 217 | |
508e53e2 | 218 | return found; |
718e3744 | 219 | } |
220 | ||
508e53e2 | 221 | void |
222 | ospf6_nexthop_calc (struct ospf6_vertex *w, struct ospf6_vertex *v, | |
223 | caddr_t lsdesc) | |
718e3744 | 224 | { |
508e53e2 | 225 | int i, ifindex; |
226 | struct ospf6_interface *oi; | |
227 | u_int16_t type; | |
228 | u_int32_t adv_router; | |
229 | struct ospf6_lsa *lsa; | |
230 | struct ospf6_link_lsa *link_lsa; | |
231 | char buf[64]; | |
718e3744 | 232 | |
508e53e2 | 233 | assert (VERTEX_IS_TYPE (ROUTER, w)); |
234 | ifindex = (VERTEX_IS_TYPE (NETWORK, v) ? v->nexthop[0].ifindex : | |
235 | ROUTER_LSDESC_GET_IFID (lsdesc)); | |
236 | oi = ospf6_interface_lookup_by_ifindex (ifindex); | |
237 | if (oi == NULL) | |
718e3744 | 238 | { |
508e53e2 | 239 | if (IS_OSPF6_DEBUG_SPF (SUMMARY)) |
240 | zlog_warn ("Can't find interface in SPF: ifindex %d", ifindex); | |
241 | return; | |
718e3744 | 242 | } |
243 | ||
508e53e2 | 244 | type = htons (OSPF6_LSTYPE_LINK); |
245 | adv_router = (VERTEX_IS_TYPE (NETWORK, v) ? | |
246 | NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc) : | |
247 | ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc)); | |
718e3744 | 248 | |
508e53e2 | 249 | i = 0; |
250 | for (lsa = ospf6_lsdb_type_router_head (type, adv_router, oi->lsdb); lsa; | |
251 | lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa)) | |
718e3744 | 252 | { |
508e53e2 | 253 | if (VERTEX_IS_TYPE (ROUTER, v) && |
254 | htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc)) != lsa->header->id) | |
718e3744 | 255 | continue; |
256 | ||
508e53e2 | 257 | link_lsa = (struct ospf6_link_lsa *) OSPF6_LSA_HEADER_END (lsa->header); |
258 | if (IS_OSPF6_DEBUG_SPF (DETAIL)) | |
259 | { | |
260 | inet_ntop (AF_INET6, &link_lsa->linklocal_addr, buf, sizeof (buf)); | |
261 | zlog_info (" nexthop %s from %s", buf, lsa->name); | |
262 | } | |
718e3744 | 263 | |
508e53e2 | 264 | if (i < OSPF6_MULTI_PATH_LIMIT) |
265 | { | |
266 | memcpy (&w->nexthop[i].address, &link_lsa->linklocal_addr, | |
267 | sizeof (struct in6_addr)); | |
268 | w->nexthop[i].ifindex = ifindex; | |
269 | i++; | |
270 | } | |
718e3744 | 271 | } |
272 | ||
508e53e2 | 273 | if (i == 0 && IS_OSPF6_DEBUG_SPF (SUMMARY)) |
274 | zlog_info ("No nexthop for %s found", w->name); | |
718e3744 | 275 | } |
276 | ||
508e53e2 | 277 | int |
278 | ospf6_spf_install (struct ospf6_vertex *v, | |
279 | struct ospf6_route_table *result_table) | |
718e3744 | 280 | { |
508e53e2 | 281 | struct ospf6_route *route; |
282 | int i, j; | |
283 | struct ospf6_vertex *prev, *w; | |
718e3744 | 284 | listnode node; |
718e3744 | 285 | |
508e53e2 | 286 | if (IS_OSPF6_DEBUG_SPF (SUMMARY)) |
287 | zlog_info ("SPF install %s hops %d cost %d", | |
288 | v->name, v->hops, v->cost); | |
718e3744 | 289 | |
508e53e2 | 290 | route = ospf6_route_lookup (&v->vertex_id, result_table); |
291 | if (route && route->path.cost < v->cost) | |
718e3744 | 292 | { |
508e53e2 | 293 | if (IS_OSPF6_DEBUG_SPF (SUMMARY)) |
294 | zlog_info (" already installed with lower cost (%d), ignore", | |
295 | route->path.cost); | |
296 | ospf6_vertex_delete (v); | |
297 | return -1; | |
718e3744 | 298 | } |
508e53e2 | 299 | else if (route && route->path.cost == v->cost) |
718e3744 | 300 | { |
508e53e2 | 301 | if (IS_OSPF6_DEBUG_SPF (SUMMARY)) |
302 | zlog_info (" another path found, merge"); | |
718e3744 | 303 | |
508e53e2 | 304 | for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && |
305 | i < OSPF6_MULTI_PATH_LIMIT; i++) | |
306 | { | |
307 | for (j = 0; j < OSPF6_MULTI_PATH_LIMIT; j++) | |
308 | { | |
309 | if (ospf6_nexthop_is_set (&route->nexthop[j])) | |
310 | { | |
311 | if (ospf6_nexthop_is_same (&route->nexthop[j], | |
312 | &v->nexthop[i])) | |
313 | break; | |
314 | else | |
315 | continue; | |
316 | } | |
317 | ospf6_nexthop_copy (&route->nexthop[j], &v->nexthop[i]); | |
318 | break; | |
319 | } | |
320 | } | |
718e3744 | 321 | |
508e53e2 | 322 | prev = (struct ospf6_vertex *) route->route_option; |
323 | if (prev->hops > v->hops) | |
324 | { | |
325 | LIST_LOOP (prev->child_list, w, node) | |
326 | { | |
327 | assert (w->parent == prev); | |
328 | w->parent = v; | |
329 | listnode_add_sort (v->child_list, w); | |
330 | } | |
331 | listnode_delete (prev->parent->child_list, prev); | |
332 | listnode_add_sort (v->parent->child_list, v); | |
718e3744 | 333 | |
508e53e2 | 334 | ospf6_vertex_delete (prev); |
335 | route->route_option = v; | |
336 | } | |
337 | else | |
338 | ospf6_vertex_delete (v); | |
718e3744 | 339 | |
508e53e2 | 340 | return -1; |
718e3744 | 341 | } |
508e53e2 | 342 | |
343 | /* There should be no case where candidate being installed (variable | |
344 | "v") is closer than the one in the SPF tree (variable "route"). | |
6452df09 | 345 | In the case something has gone wrong with the behavior of |
508e53e2 | 346 | Priority-Queue. */ |
6452df09 | 347 | |
348 | /* the case where the route exists already is handled and returned | |
349 | up to here. */ | |
508e53e2 | 350 | assert (route == NULL); |
351 | ||
352 | route = ospf6_route_create (); | |
353 | memcpy (&route->prefix, &v->vertex_id, sizeof (struct prefix)); | |
354 | route->type = OSPF6_DEST_TYPE_LINKSTATE; | |
355 | route->path.type = OSPF6_PATH_TYPE_INTRA; | |
356 | route->path.origin.type = v->lsa->header->type; | |
357 | route->path.origin.id = v->lsa->header->id; | |
358 | route->path.origin.adv_router = v->lsa->header->adv_router; | |
359 | route->path.metric_type = 1; | |
360 | route->path.cost = v->cost; | |
361 | route->path.cost_e2 = v->hops; | |
362 | route->path.router_bits = v->capability; | |
363 | route->path.options[0] = v->options[0]; | |
364 | route->path.options[1] = v->options[1]; | |
365 | route->path.options[2] = v->options[2]; | |
366 | ||
367 | for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && | |
368 | i < OSPF6_MULTI_PATH_LIMIT; i++) | |
369 | ospf6_nexthop_copy (&route->nexthop[i], &v->nexthop[i]); | |
370 | ||
371 | if (v->parent) | |
372 | listnode_add_sort (v->parent->child_list, v); | |
373 | route->route_option = v; | |
374 | ||
375 | ospf6_route_add (route, result_table); | |
376 | return 0; | |
718e3744 | 377 | } |
378 | ||
508e53e2 | 379 | void |
380 | ospf6_spf_table_finish (struct ospf6_route_table *result_table) | |
718e3744 | 381 | { |
508e53e2 | 382 | struct ospf6_route *route; |
718e3744 | 383 | struct ospf6_vertex *v; |
508e53e2 | 384 | for (route = ospf6_route_head (result_table); route; |
385 | route = ospf6_route_next (route)) | |
718e3744 | 386 | { |
508e53e2 | 387 | v = (struct ospf6_vertex *) route->route_option; |
388 | ospf6_vertex_delete (v); | |
389 | ospf6_route_remove (route, result_table); | |
718e3744 | 390 | } |
718e3744 | 391 | } |
392 | ||
6452df09 | 393 | /* RFC2328 16.1. Calculating the shortest-path tree for an area */ |
394 | /* RFC2740 3.8.1. Calculating the shortest path tree for an area */ | |
508e53e2 | 395 | void |
396 | ospf6_spf_calculation (u_int32_t router_id, | |
397 | struct ospf6_route_table *result_table, | |
398 | struct ospf6_area *oa) | |
399 | { | |
400 | struct pqueue *candidate_list; | |
401 | struct ospf6_vertex *root, *v, *w; | |
402 | int i; | |
403 | int size; | |
404 | caddr_t lsdesc; | |
405 | struct ospf6_lsa *lsa; | |
718e3744 | 406 | |
508e53e2 | 407 | /* initialize */ |
408 | candidate_list = pqueue_create (); | |
409 | candidate_list->cmp = ospf6_vertex_cmp; | |
718e3744 | 410 | |
508e53e2 | 411 | ospf6_spf_table_finish (result_table); |
718e3744 | 412 | |
508e53e2 | 413 | /* Install the calculating router itself as the root of the SPF tree */ |
414 | /* construct root vertex */ | |
415 | lsa = ospf6_lsdb_lookup (htons (OSPF6_LSTYPE_ROUTER), htonl (0), | |
416 | router_id, oa->lsdb); | |
417 | if (lsa == NULL) | |
418 | return; | |
419 | root = ospf6_vertex_create (lsa); | |
420 | root->area = oa; | |
421 | root->cost = 0; | |
422 | root->hops = 0; | |
6452df09 | 423 | root->nexthop[0].ifindex = 0; /* loopbak I/F is better ... */ |
508e53e2 | 424 | inet_pton (AF_INET6, "::1", &root->nexthop[0].address); |
718e3744 | 425 | |
508e53e2 | 426 | /* Actually insert root to the candidate-list as the only candidate */ |
427 | pqueue_enqueue (root, candidate_list); | |
718e3744 | 428 | |
508e53e2 | 429 | /* Iterate until candidate-list becomes empty */ |
430 | while (candidate_list->size) | |
718e3744 | 431 | { |
508e53e2 | 432 | /* get closest candidate from priority queue */ |
433 | v = pqueue_dequeue (candidate_list); | |
718e3744 | 434 | |
6452df09 | 435 | /* installing may result in merging or rejecting of the vertex */ |
508e53e2 | 436 | if (ospf6_spf_install (v, result_table) < 0) |
437 | continue; | |
718e3744 | 438 | |
508e53e2 | 439 | /* For each LS description in the just-added vertex V's LSA */ |
440 | size = (VERTEX_IS_TYPE (ROUTER, v) ? | |
441 | sizeof (struct ospf6_router_lsdesc) : | |
442 | sizeof (struct ospf6_network_lsdesc)); | |
443 | for (lsdesc = OSPF6_LSA_HEADER_END (v->lsa->header) + 4; | |
444 | lsdesc + size <= OSPF6_LSA_END (v->lsa->header); lsdesc += size) | |
718e3744 | 445 | { |
508e53e2 | 446 | lsa = ospf6_lsdesc_lsa (lsdesc, v); |
447 | if (lsa == NULL) | |
718e3744 | 448 | continue; |
449 | ||
508e53e2 | 450 | if (! ospf6_lsdesc_backlink (lsa, lsdesc, v)) |
451 | continue; | |
718e3744 | 452 | |
508e53e2 | 453 | w = ospf6_vertex_create (lsa); |
454 | w->area = oa; | |
455 | w->parent = v; | |
456 | if (VERTEX_IS_TYPE (ROUTER, v)) | |
718e3744 | 457 | { |
508e53e2 | 458 | w->cost = v->cost + ROUTER_LSDESC_GET_METRIC (lsdesc); |
459 | w->hops = v->hops + (VERTEX_IS_TYPE (NETWORK, w) ? 0 : 1); | |
718e3744 | 460 | } |
508e53e2 | 461 | else /* NETWORK */ |
718e3744 | 462 | { |
508e53e2 | 463 | w->cost = v->cost; |
464 | w->hops = v->hops + 1; | |
718e3744 | 465 | } |
466 | ||
508e53e2 | 467 | /* nexthop calculation */ |
468 | if (w->hops == 0) | |
469 | w->nexthop[0].ifindex = ROUTER_LSDESC_GET_IFID (lsdesc); | |
470 | else if (w->hops == 1 && v->hops == 0) | |
471 | ospf6_nexthop_calc (w, v, lsdesc); | |
718e3744 | 472 | else |
473 | { | |
508e53e2 | 474 | for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && |
475 | i < OSPF6_MULTI_PATH_LIMIT; i++) | |
476 | ospf6_nexthop_copy (&w->nexthop[i], &v->nexthop[i]); | |
718e3744 | 477 | } |
478 | ||
508e53e2 | 479 | /* add new candidate to the candidate_list */ |
480 | if (IS_OSPF6_DEBUG_SPF (SUMMARY)) | |
481 | zlog_info (" New candidate: %s hops %d cost %d", | |
482 | w->name, w->hops, w->cost); | |
483 | pqueue_enqueue (w, candidate_list); | |
718e3744 | 484 | } |
485 | } | |
486 | ||
508e53e2 | 487 | pqueue_delete (candidate_list); |
718e3744 | 488 | } |
489 | ||
490 | int | |
491 | ospf6_spf_calculation_thread (struct thread *t) | |
492 | { | |
508e53e2 | 493 | struct ospf6_area *oa; |
494 | struct timeval start, end, runtime; | |
718e3744 | 495 | |
508e53e2 | 496 | oa = (struct ospf6_area *) THREAD_ARG (t); |
497 | oa->thread_spf_calculation = NULL; | |
718e3744 | 498 | |
508e53e2 | 499 | if (IS_OSPF6_DEBUG_SPF (SUMMARY)) |
500 | zlog_info ("SPF calculation for area %s", oa->name); | |
718e3744 | 501 | |
502 | /* execute SPF calculation */ | |
503 | gettimeofday (&start, (struct timezone *) NULL); | |
508e53e2 | 504 | ospf6_spf_calculation (oa->ospf6->router_id, oa->spf_table, oa); |
718e3744 | 505 | gettimeofday (&end, (struct timezone *) NULL); |
506 | ||
508e53e2 | 507 | if (IS_OSPF6_DEBUG_SPF (SUMMARY)) |
718e3744 | 508 | { |
508e53e2 | 509 | timersub (&end, &start, &runtime); |
510 | zlog_info ("SPF calculation for area %s: runtime %ld sec %ld usec", | |
511 | oa->name, runtime.tv_sec, runtime.tv_usec); | |
718e3744 | 512 | } |
513 | ||
508e53e2 | 514 | ospf6_intra_route_calculation (oa); |
6452df09 | 515 | ospf6_intra_brouter_calculation (oa); |
718e3744 | 516 | |
517 | return 0; | |
518 | } | |
519 | ||
520 | void | |
508e53e2 | 521 | ospf6_spf_schedule (struct ospf6_area *oa) |
718e3744 | 522 | { |
508e53e2 | 523 | if (oa->thread_spf_calculation) |
718e3744 | 524 | return; |
508e53e2 | 525 | oa->thread_spf_calculation = |
526 | thread_add_event (master, ospf6_spf_calculation_thread, oa, 0); | |
718e3744 | 527 | } |
528 | ||
529 | void | |
508e53e2 | 530 | ospf6_spf_display_subtree (struct vty *vty, char *prefix, int rest, |
531 | struct ospf6_vertex *v) | |
718e3744 | 532 | { |
533 | listnode node; | |
508e53e2 | 534 | struct ospf6_vertex *c; |
535 | char *next_prefix; | |
536 | int len; | |
537 | int restnum; | |
718e3744 | 538 | |
508e53e2 | 539 | /* "prefix" is the space prefix of the display line */ |
049207c3 | 540 | vty_out (vty, "%s+-%s [%d]%s", prefix, v->name, v->cost, VNL); |
718e3744 | 541 | |
508e53e2 | 542 | len = strlen (prefix) + 4; |
543 | next_prefix = (char *) malloc (len); | |
544 | if (next_prefix == NULL) | |
718e3744 | 545 | { |
049207c3 | 546 | vty_out (vty, "malloc failed%s", VNL); |
508e53e2 | 547 | return; |
718e3744 | 548 | } |
508e53e2 | 549 | snprintf (next_prefix, len, "%s%s", prefix, (rest ? "| " : " ")); |
718e3744 | 550 | |
508e53e2 | 551 | restnum = listcount (v->child_list); |
552 | LIST_LOOP (v->child_list, c, node) | |
718e3744 | 553 | { |
508e53e2 | 554 | restnum--; |
555 | ospf6_spf_display_subtree (vty, next_prefix, restnum, c); | |
718e3744 | 556 | } |
718e3744 | 557 | |
508e53e2 | 558 | free (next_prefix); |
718e3744 | 559 | } |
560 | ||
508e53e2 | 561 | DEFUN (debug_ospf6_spf_detail, |
562 | debug_ospf6_spf_detail_cmd, | |
563 | "debug ospf6 spf detail", | |
564 | DEBUG_STR | |
565 | OSPF6_STR | |
566 | "Debug SPF Calculation\n" | |
567 | "Debug Detailed SPF\n" | |
568 | ) | |
718e3744 | 569 | { |
508e53e2 | 570 | unsigned char level = 0; |
571 | level = OSPF6_DEBUG_SPF_SUMMARY | OSPF6_DEBUG_SPF_DETAIL; | |
572 | OSPF6_DEBUG_SPF_ON (level); | |
573 | return CMD_SUCCESS; | |
718e3744 | 574 | } |
575 | ||
508e53e2 | 576 | DEFUN (debug_ospf6_spf, |
577 | debug_ospf6_spf_cmd, | |
578 | "debug ospf6 spf", | |
579 | DEBUG_STR | |
718e3744 | 580 | OSPF6_STR |
508e53e2 | 581 | "Debug SPF Calculation\n" |
582 | ) | |
718e3744 | 583 | { |
508e53e2 | 584 | unsigned char level = 0; |
585 | level = OSPF6_DEBUG_SPF_SUMMARY; | |
586 | OSPF6_DEBUG_SPF_ON (level); | |
718e3744 | 587 | return CMD_SUCCESS; |
588 | } | |
589 | ||
508e53e2 | 590 | DEFUN (no_debug_ospf6_spf_detail, |
591 | no_debug_ospf6_spf_detail_cmd, | |
592 | "no debug ospf6 spf detail", | |
593 | NO_STR | |
594 | DEBUG_STR | |
595 | OSPF6_STR | |
596 | "Quit Debugging SPF Calculation\n" | |
597 | "Quit Debugging Detailed SPF (change to debug summary)\n" | |
598 | ) | |
718e3744 | 599 | { |
508e53e2 | 600 | unsigned char level = 0; |
601 | level = OSPF6_DEBUG_SPF_DETAIL; | |
602 | OSPF6_DEBUG_SPF_OFF (level); | |
603 | return CMD_SUCCESS; | |
718e3744 | 604 | } |
605 | ||
508e53e2 | 606 | DEFUN (no_debug_ospf6_spf, |
607 | no_debug_ospf6_spf_cmd, | |
608 | "no debug ospf6 spf", | |
609 | NO_STR | |
610 | DEBUG_STR | |
718e3744 | 611 | OSPF6_STR |
508e53e2 | 612 | "Quit Debugging SPF Calculation\n" |
613 | ) | |
718e3744 | 614 | { |
508e53e2 | 615 | unsigned char level = 0; |
616 | level = OSPF6_DEBUG_SPF_SUMMARY | OSPF6_DEBUG_SPF_DETAIL; | |
617 | OSPF6_DEBUG_SPF_OFF (level); | |
718e3744 | 618 | return CMD_SUCCESS; |
619 | } | |
620 | ||
508e53e2 | 621 | int |
622 | config_write_ospf6_debug_spf (struct vty *vty) | |
718e3744 | 623 | { |
508e53e2 | 624 | if (IS_OSPF6_DEBUG_SPF (DETAIL)) |
049207c3 | 625 | vty_out (vty, "debug ospf6 spf detail%s", VNL); |
508e53e2 | 626 | else if (IS_OSPF6_DEBUG_SPF (SUMMARY)) |
049207c3 | 627 | vty_out (vty, "debug ospf6 spf%s", VNL); |
508e53e2 | 628 | return 0; |
718e3744 | 629 | } |
630 | ||
508e53e2 | 631 | void |
632 | install_element_ospf6_debug_spf () | |
633 | { | |
634 | install_element (ENABLE_NODE, &debug_ospf6_spf_cmd); | |
635 | install_element (ENABLE_NODE, &debug_ospf6_spf_detail_cmd); | |
636 | install_element (ENABLE_NODE, &no_debug_ospf6_spf_cmd); | |
637 | install_element (ENABLE_NODE, &no_debug_ospf6_spf_detail_cmd); | |
638 | install_element (CONFIG_NODE, &debug_ospf6_spf_cmd); | |
639 | install_element (CONFIG_NODE, &debug_ospf6_spf_detail_cmd); | |
640 | install_element (CONFIG_NODE, &no_debug_ospf6_spf_cmd); | |
641 | install_element (CONFIG_NODE, &no_debug_ospf6_spf_detail_cmd); | |
642 | } | |
718e3744 | 643 | |
644 | void | |
645 | ospf6_spf_init () | |
646 | { | |
718e3744 | 647 | } |
648 | ||
508e53e2 | 649 |