]>
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 | |
6ac29a51 | 46 | static 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 */ |
403138e1 DT |
53 | if (va->cost != vb->cost) |
54 | return (va->cost - vb->cost); | |
55 | return (va->hops - vb->hops); | |
718e3744 | 56 | } |
57 | ||
6ac29a51 | 58 | static int |
508e53e2 | 59 | ospf6_vertex_id_cmp (void *a, void *b) |
718e3744 | 60 | { |
508e53e2 | 61 | struct ospf6_vertex *va = (struct ospf6_vertex *) a; |
62 | struct ospf6_vertex *vb = (struct ospf6_vertex *) b; | |
63 | int ret = 0; | |
718e3744 | 64 | |
508e53e2 | 65 | ret = ntohl (ospf6_linkstate_prefix_adv_router (&va->vertex_id)) - |
66 | ntohl (ospf6_linkstate_prefix_adv_router (&vb->vertex_id)); | |
67 | if (ret) | |
68 | return ret; | |
718e3744 | 69 | |
508e53e2 | 70 | ret = ntohl (ospf6_linkstate_prefix_id (&va->vertex_id)) - |
71 | ntohl (ospf6_linkstate_prefix_id (&vb->vertex_id)); | |
718e3744 | 72 | return ret; |
73 | } | |
74 | ||
6ac29a51 | 75 | static struct ospf6_vertex * |
508e53e2 | 76 | ospf6_vertex_create (struct ospf6_lsa *lsa) |
718e3744 | 77 | { |
508e53e2 | 78 | struct ospf6_vertex *v; |
79 | int i; | |
718e3744 | 80 | |
508e53e2 | 81 | v = (struct ospf6_vertex *) |
82 | XMALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_vertex)); | |
718e3744 | 83 | |
508e53e2 | 84 | /* type */ |
85 | if (ntohs (lsa->header->type) == OSPF6_LSTYPE_ROUTER) | |
86 | v->type = OSPF6_VERTEX_TYPE_ROUTER; | |
87 | else if (ntohs (lsa->header->type) == OSPF6_LSTYPE_NETWORK) | |
88 | v->type = OSPF6_VERTEX_TYPE_NETWORK; | |
718e3744 | 89 | else |
508e53e2 | 90 | assert (0); |
718e3744 | 91 | |
508e53e2 | 92 | /* vertex_id */ |
93 | ospf6_linkstate_prefix (lsa->header->adv_router, lsa->header->id, | |
94 | &v->vertex_id); | |
718e3744 | 95 | |
508e53e2 | 96 | /* name */ |
97 | ospf6_linkstate_prefix2str (&v->vertex_id, v->name, sizeof (v->name)); | |
718e3744 | 98 | |
508e53e2 | 99 | /* Associated LSA */ |
100 | v->lsa = lsa; | |
718e3744 | 101 | |
508e53e2 | 102 | /* capability bits + options */ |
103 | v->capability = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header)); | |
104 | v->options[0] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 1); | |
105 | v->options[1] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 2); | |
106 | v->options[2] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 3); | |
718e3744 | 107 | |
508e53e2 | 108 | for (i = 0; i < OSPF6_MULTI_PATH_LIMIT; i++) |
109 | ospf6_nexthop_clear (&v->nexthop[i]); | |
718e3744 | 110 | |
508e53e2 | 111 | v->parent = NULL; |
112 | v->child_list = list_new (); | |
113 | v->child_list->cmp = ospf6_vertex_id_cmp; | |
718e3744 | 114 | |
508e53e2 | 115 | return v; |
718e3744 | 116 | } |
117 | ||
6ac29a51 | 118 | static void |
508e53e2 | 119 | ospf6_vertex_delete (struct ospf6_vertex *v) |
718e3744 | 120 | { |
508e53e2 | 121 | list_delete (v->child_list); |
122 | XFREE (MTYPE_OSPF6_VERTEX, v); | |
718e3744 | 123 | } |
124 | ||
6ac29a51 | 125 | static struct ospf6_lsa * |
508e53e2 | 126 | ospf6_lsdesc_lsa (caddr_t lsdesc, struct ospf6_vertex *v) |
718e3744 | 127 | { |
508e53e2 | 128 | struct ospf6_lsa *lsa; |
129 | u_int16_t type = 0; | |
130 | u_int32_t id = 0, adv_router = 0; | |
718e3744 | 131 | |
508e53e2 | 132 | if (VERTEX_IS_TYPE (NETWORK, v)) |
718e3744 | 133 | { |
508e53e2 | 134 | type = htons (OSPF6_LSTYPE_ROUTER); |
135 | id = htonl (0); | |
136 | adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc); | |
718e3744 | 137 | } |
138 | else | |
139 | { | |
508e53e2 | 140 | if (ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc)) |
718e3744 | 141 | { |
508e53e2 | 142 | type = htons (OSPF6_LSTYPE_ROUTER); |
718e3744 | 143 | id = htonl (0); |
508e53e2 | 144 | adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc); |
718e3744 | 145 | } |
508e53e2 | 146 | else if (ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, lsdesc)) |
718e3744 | 147 | { |
508e53e2 | 148 | type = htons (OSPF6_LSTYPE_NETWORK); |
149 | id = htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc)); | |
150 | adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc); | |
718e3744 | 151 | } |
718e3744 | 152 | } |
153 | ||
508e53e2 | 154 | lsa = ospf6_lsdb_lookup (type, id, adv_router, v->area->lsdb); |
718e3744 | 155 | |
3b68735f | 156 | if (IS_OSPF6_DEBUG_SPF (PROCESS)) |
718e3744 | 157 | { |
508e53e2 | 158 | char ibuf[16], abuf[16]; |
159 | inet_ntop (AF_INET, &id, ibuf, sizeof (ibuf)); | |
160 | inet_ntop (AF_INET, &adv_router, abuf, sizeof (abuf)); | |
161 | if (lsa) | |
c6487d61 | 162 | zlog_debug (" Link to: %s", lsa->name); |
508e53e2 | 163 | else |
c6487d61 | 164 | zlog_debug (" Link to: [%s Id:%s Adv:%s] No LSA", |
165 | ospf6_lstype_name (type), ibuf, abuf); | |
718e3744 | 166 | } |
167 | ||
508e53e2 | 168 | return lsa; |
718e3744 | 169 | } |
170 | ||
6ac29a51 | 171 | static char * |
508e53e2 | 172 | ospf6_lsdesc_backlink (struct ospf6_lsa *lsa, |
173 | caddr_t lsdesc, struct ospf6_vertex *v) | |
718e3744 | 174 | { |
508e53e2 | 175 | caddr_t backlink, found = NULL; |
176 | int size; | |
718e3744 | 177 | |
508e53e2 | 178 | size = (OSPF6_LSA_IS_TYPE (ROUTER, lsa) ? |
179 | sizeof (struct ospf6_router_lsdesc) : | |
180 | sizeof (struct ospf6_network_lsdesc)); | |
181 | for (backlink = OSPF6_LSA_HEADER_END (lsa->header) + 4; | |
182 | backlink + size <= OSPF6_LSA_END (lsa->header); backlink += size) | |
718e3744 | 183 | { |
508e53e2 | 184 | assert (! (OSPF6_LSA_IS_TYPE (NETWORK, lsa) && |
185 | VERTEX_IS_TYPE (NETWORK, v))); | |
718e3744 | 186 | |
508e53e2 | 187 | if (OSPF6_LSA_IS_TYPE (NETWORK, lsa) && |
188 | NETWORK_LSDESC_GET_NBR_ROUTERID (backlink) | |
189 | == v->lsa->header->adv_router) | |
190 | found = backlink; | |
191 | else if (VERTEX_IS_TYPE (NETWORK, v) && | |
192 | ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, backlink) && | |
193 | ROUTER_LSDESC_GET_NBR_ROUTERID (backlink) | |
194 | == v->lsa->header->adv_router && | |
195 | ROUTER_LSDESC_GET_NBR_IFID (backlink) | |
196 | == ntohl (v->lsa->header->id)) | |
197 | found = backlink; | |
198 | else | |
199 | { | |
200 | if (! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, backlink) || | |
201 | ! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc)) | |
202 | continue; | |
203 | if (ROUTER_LSDESC_GET_NBR_IFID (backlink) != | |
204 | ROUTER_LSDESC_GET_IFID (lsdesc) || | |
205 | ROUTER_LSDESC_GET_NBR_IFID (lsdesc) != | |
206 | ROUTER_LSDESC_GET_IFID (backlink)) | |
207 | continue; | |
208 | if (ROUTER_LSDESC_GET_NBR_ROUTERID (backlink) != | |
209 | v->lsa->header->adv_router || | |
210 | ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc) != | |
211 | lsa->header->adv_router) | |
212 | continue; | |
213 | found = backlink; | |
214 | } | |
718e3744 | 215 | } |
718e3744 | 216 | |
3b68735f | 217 | if (IS_OSPF6_DEBUG_SPF (PROCESS)) |
c6487d61 | 218 | zlog_debug (" Backlink %s", (found ? "OK" : "FAIL")); |
718e3744 | 219 | |
508e53e2 | 220 | return found; |
718e3744 | 221 | } |
222 | ||
6ac29a51 | 223 | static void |
508e53e2 | 224 | ospf6_nexthop_calc (struct ospf6_vertex *w, struct ospf6_vertex *v, |
225 | caddr_t lsdesc) | |
718e3744 | 226 | { |
508e53e2 | 227 | int i, ifindex; |
228 | struct ospf6_interface *oi; | |
229 | u_int16_t type; | |
230 | u_int32_t adv_router; | |
231 | struct ospf6_lsa *lsa; | |
232 | struct ospf6_link_lsa *link_lsa; | |
233 | char buf[64]; | |
718e3744 | 234 | |
508e53e2 | 235 | assert (VERTEX_IS_TYPE (ROUTER, w)); |
236 | ifindex = (VERTEX_IS_TYPE (NETWORK, v) ? v->nexthop[0].ifindex : | |
237 | ROUTER_LSDESC_GET_IFID (lsdesc)); | |
238 | oi = ospf6_interface_lookup_by_ifindex (ifindex); | |
239 | if (oi == NULL) | |
718e3744 | 240 | { |
3b68735f | 241 | if (IS_OSPF6_DEBUG_SPF (PROCESS)) |
c6487d61 | 242 | zlog_debug ("Can't find interface in SPF: ifindex %d", ifindex); |
508e53e2 | 243 | return; |
718e3744 | 244 | } |
245 | ||
508e53e2 | 246 | type = htons (OSPF6_LSTYPE_LINK); |
247 | adv_router = (VERTEX_IS_TYPE (NETWORK, v) ? | |
248 | NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc) : | |
249 | ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc)); | |
718e3744 | 250 | |
508e53e2 | 251 | i = 0; |
252 | for (lsa = ospf6_lsdb_type_router_head (type, adv_router, oi->lsdb); lsa; | |
253 | lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa)) | |
718e3744 | 254 | { |
508e53e2 | 255 | if (VERTEX_IS_TYPE (ROUTER, v) && |
256 | htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc)) != lsa->header->id) | |
718e3744 | 257 | continue; |
258 | ||
508e53e2 | 259 | link_lsa = (struct ospf6_link_lsa *) OSPF6_LSA_HEADER_END (lsa->header); |
3b68735f | 260 | if (IS_OSPF6_DEBUG_SPF (PROCESS)) |
508e53e2 | 261 | { |
262 | inet_ntop (AF_INET6, &link_lsa->linklocal_addr, buf, sizeof (buf)); | |
c6487d61 | 263 | zlog_debug (" nexthop %s from %s", buf, lsa->name); |
508e53e2 | 264 | } |
718e3744 | 265 | |
508e53e2 | 266 | if (i < OSPF6_MULTI_PATH_LIMIT) |
267 | { | |
268 | memcpy (&w->nexthop[i].address, &link_lsa->linklocal_addr, | |
269 | sizeof (struct in6_addr)); | |
270 | w->nexthop[i].ifindex = ifindex; | |
271 | i++; | |
272 | } | |
718e3744 | 273 | } |
274 | ||
3b68735f | 275 | if (i == 0 && IS_OSPF6_DEBUG_SPF (PROCESS)) |
c6487d61 | 276 | zlog_debug ("No nexthop for %s found", w->name); |
718e3744 | 277 | } |
278 | ||
6ac29a51 | 279 | static int |
508e53e2 | 280 | ospf6_spf_install (struct ospf6_vertex *v, |
281 | struct ospf6_route_table *result_table) | |
718e3744 | 282 | { |
508e53e2 | 283 | struct ospf6_route *route; |
284 | int i, j; | |
87362ceb | 285 | struct ospf6_vertex *prev; |
718e3744 | 286 | |
3b68735f | 287 | if (IS_OSPF6_DEBUG_SPF (PROCESS)) |
c6487d61 | 288 | zlog_debug ("SPF install %s hops %d cost %d", |
289 | v->name, v->hops, v->cost); | |
718e3744 | 290 | |
508e53e2 | 291 | route = ospf6_route_lookup (&v->vertex_id, result_table); |
292 | if (route && route->path.cost < v->cost) | |
718e3744 | 293 | { |
3b68735f | 294 | if (IS_OSPF6_DEBUG_SPF (PROCESS)) |
c6487d61 | 295 | zlog_debug (" already installed with lower cost (%d), ignore", |
296 | route->path.cost); | |
508e53e2 | 297 | ospf6_vertex_delete (v); |
298 | return -1; | |
718e3744 | 299 | } |
508e53e2 | 300 | else if (route && route->path.cost == v->cost) |
718e3744 | 301 | { |
3b68735f | 302 | if (IS_OSPF6_DEBUG_SPF (PROCESS)) |
c6487d61 | 303 | zlog_debug (" another path found, merge"); |
718e3744 | 304 | |
508e53e2 | 305 | for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && |
306 | i < OSPF6_MULTI_PATH_LIMIT; i++) | |
307 | { | |
308 | for (j = 0; j < OSPF6_MULTI_PATH_LIMIT; j++) | |
309 | { | |
310 | if (ospf6_nexthop_is_set (&route->nexthop[j])) | |
311 | { | |
312 | if (ospf6_nexthop_is_same (&route->nexthop[j], | |
313 | &v->nexthop[i])) | |
314 | break; | |
315 | else | |
316 | continue; | |
317 | } | |
318 | ospf6_nexthop_copy (&route->nexthop[j], &v->nexthop[i]); | |
319 | break; | |
320 | } | |
321 | } | |
718e3744 | 322 | |
508e53e2 | 323 | prev = (struct ospf6_vertex *) route->route_option; |
403138e1 DT |
324 | assert (prev->hops <= v->hops); |
325 | ospf6_vertex_delete (v); | |
718e3744 | 326 | |
508e53e2 | 327 | return -1; |
718e3744 | 328 | } |
508e53e2 | 329 | |
330 | /* There should be no case where candidate being installed (variable | |
331 | "v") is closer than the one in the SPF tree (variable "route"). | |
6452df09 | 332 | In the case something has gone wrong with the behavior of |
508e53e2 | 333 | Priority-Queue. */ |
6452df09 | 334 | |
335 | /* the case where the route exists already is handled and returned | |
336 | up to here. */ | |
508e53e2 | 337 | assert (route == NULL); |
338 | ||
339 | route = ospf6_route_create (); | |
340 | memcpy (&route->prefix, &v->vertex_id, sizeof (struct prefix)); | |
341 | route->type = OSPF6_DEST_TYPE_LINKSTATE; | |
342 | route->path.type = OSPF6_PATH_TYPE_INTRA; | |
343 | route->path.origin.type = v->lsa->header->type; | |
344 | route->path.origin.id = v->lsa->header->id; | |
345 | route->path.origin.adv_router = v->lsa->header->adv_router; | |
346 | route->path.metric_type = 1; | |
347 | route->path.cost = v->cost; | |
348 | route->path.cost_e2 = v->hops; | |
349 | route->path.router_bits = v->capability; | |
350 | route->path.options[0] = v->options[0]; | |
351 | route->path.options[1] = v->options[1]; | |
352 | route->path.options[2] = v->options[2]; | |
353 | ||
354 | for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && | |
355 | i < OSPF6_MULTI_PATH_LIMIT; i++) | |
356 | ospf6_nexthop_copy (&route->nexthop[i], &v->nexthop[i]); | |
357 | ||
358 | if (v->parent) | |
359 | listnode_add_sort (v->parent->child_list, v); | |
360 | route->route_option = v; | |
361 | ||
362 | ospf6_route_add (route, result_table); | |
363 | return 0; | |
718e3744 | 364 | } |
365 | ||
508e53e2 | 366 | void |
367 | ospf6_spf_table_finish (struct ospf6_route_table *result_table) | |
718e3744 | 368 | { |
508e53e2 | 369 | struct ospf6_route *route; |
718e3744 | 370 | struct ospf6_vertex *v; |
508e53e2 | 371 | for (route = ospf6_route_head (result_table); route; |
372 | route = ospf6_route_next (route)) | |
718e3744 | 373 | { |
508e53e2 | 374 | v = (struct ospf6_vertex *) route->route_option; |
375 | ospf6_vertex_delete (v); | |
376 | ospf6_route_remove (route, result_table); | |
718e3744 | 377 | } |
718e3744 | 378 | } |
379 | ||
6452df09 | 380 | /* RFC2328 16.1. Calculating the shortest-path tree for an area */ |
381 | /* RFC2740 3.8.1. Calculating the shortest path tree for an area */ | |
508e53e2 | 382 | void |
383 | ospf6_spf_calculation (u_int32_t router_id, | |
384 | struct ospf6_route_table *result_table, | |
385 | struct ospf6_area *oa) | |
386 | { | |
387 | struct pqueue *candidate_list; | |
388 | struct ospf6_vertex *root, *v, *w; | |
389 | int i; | |
390 | int size; | |
391 | caddr_t lsdesc; | |
392 | struct ospf6_lsa *lsa; | |
718e3744 | 393 | |
508e53e2 | 394 | /* Install the calculating router itself as the root of the SPF tree */ |
395 | /* construct root vertex */ | |
396 | lsa = ospf6_lsdb_lookup (htons (OSPF6_LSTYPE_ROUTER), htonl (0), | |
397 | router_id, oa->lsdb); | |
398 | if (lsa == NULL) | |
399 | return; | |
1d19234e TG |
400 | |
401 | /* initialize */ | |
402 | candidate_list = pqueue_create (); | |
403 | candidate_list->cmp = ospf6_vertex_cmp; | |
404 | ||
405 | ospf6_spf_table_finish (result_table); | |
406 | ||
508e53e2 | 407 | root = ospf6_vertex_create (lsa); |
408 | root->area = oa; | |
409 | root->cost = 0; | |
410 | root->hops = 0; | |
6452df09 | 411 | root->nexthop[0].ifindex = 0; /* loopbak I/F is better ... */ |
508e53e2 | 412 | inet_pton (AF_INET6, "::1", &root->nexthop[0].address); |
718e3744 | 413 | |
508e53e2 | 414 | /* Actually insert root to the candidate-list as the only candidate */ |
415 | pqueue_enqueue (root, candidate_list); | |
718e3744 | 416 | |
508e53e2 | 417 | /* Iterate until candidate-list becomes empty */ |
418 | while (candidate_list->size) | |
718e3744 | 419 | { |
508e53e2 | 420 | /* get closest candidate from priority queue */ |
421 | v = pqueue_dequeue (candidate_list); | |
718e3744 | 422 | |
6452df09 | 423 | /* installing may result in merging or rejecting of the vertex */ |
508e53e2 | 424 | if (ospf6_spf_install (v, result_table) < 0) |
425 | continue; | |
718e3744 | 426 | |
508e53e2 | 427 | /* For each LS description in the just-added vertex V's LSA */ |
428 | size = (VERTEX_IS_TYPE (ROUTER, v) ? | |
429 | sizeof (struct ospf6_router_lsdesc) : | |
430 | sizeof (struct ospf6_network_lsdesc)); | |
431 | for (lsdesc = OSPF6_LSA_HEADER_END (v->lsa->header) + 4; | |
432 | lsdesc + size <= OSPF6_LSA_END (v->lsa->header); lsdesc += size) | |
718e3744 | 433 | { |
508e53e2 | 434 | lsa = ospf6_lsdesc_lsa (lsdesc, v); |
435 | if (lsa == NULL) | |
718e3744 | 436 | continue; |
437 | ||
508e53e2 | 438 | if (! ospf6_lsdesc_backlink (lsa, lsdesc, v)) |
439 | continue; | |
718e3744 | 440 | |
508e53e2 | 441 | w = ospf6_vertex_create (lsa); |
442 | w->area = oa; | |
443 | w->parent = v; | |
444 | if (VERTEX_IS_TYPE (ROUTER, v)) | |
718e3744 | 445 | { |
508e53e2 | 446 | w->cost = v->cost + ROUTER_LSDESC_GET_METRIC (lsdesc); |
447 | w->hops = v->hops + (VERTEX_IS_TYPE (NETWORK, w) ? 0 : 1); | |
718e3744 | 448 | } |
508e53e2 | 449 | else /* NETWORK */ |
718e3744 | 450 | { |
508e53e2 | 451 | w->cost = v->cost; |
452 | w->hops = v->hops + 1; | |
718e3744 | 453 | } |
454 | ||
508e53e2 | 455 | /* nexthop calculation */ |
456 | if (w->hops == 0) | |
457 | w->nexthop[0].ifindex = ROUTER_LSDESC_GET_IFID (lsdesc); | |
458 | else if (w->hops == 1 && v->hops == 0) | |
459 | ospf6_nexthop_calc (w, v, lsdesc); | |
718e3744 | 460 | else |
461 | { | |
508e53e2 | 462 | for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && |
463 | i < OSPF6_MULTI_PATH_LIMIT; i++) | |
464 | ospf6_nexthop_copy (&w->nexthop[i], &v->nexthop[i]); | |
718e3744 | 465 | } |
466 | ||
508e53e2 | 467 | /* add new candidate to the candidate_list */ |
3b68735f | 468 | if (IS_OSPF6_DEBUG_SPF (PROCESS)) |
c6487d61 | 469 | zlog_debug (" New candidate: %s hops %d cost %d", |
470 | w->name, w->hops, w->cost); | |
508e53e2 | 471 | pqueue_enqueue (w, candidate_list); |
718e3744 | 472 | } |
473 | } | |
474 | ||
508e53e2 | 475 | pqueue_delete (candidate_list); |
718e3744 | 476 | } |
477 | ||
6ac29a51 | 478 | static void |
2680aa2b | 479 | ospf6_spf_log_database (struct ospf6_area *oa) |
480 | { | |
481 | char *p, *end, buffer[256]; | |
482 | struct listnode *node; | |
483 | struct ospf6_interface *oi; | |
484 | ||
485 | p = buffer; | |
486 | end = buffer + sizeof (buffer); | |
487 | ||
488 | snprintf (p, end - p, "SPF on DB (#LSAs):"); | |
489 | p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end); | |
490 | snprintf (p, end - p, " Area %s: %d", oa->name, oa->lsdb->count); | |
491 | p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end); | |
492 | ||
1eb8ef25 | 493 | for (ALL_LIST_ELEMENTS_RO (oa->if_list, node, oi)) |
2680aa2b | 494 | { |
2680aa2b | 495 | snprintf (p, end - p, " I/F %s: %d", |
496 | oi->interface->name, oi->lsdb->count); | |
497 | p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end); | |
498 | } | |
499 | ||
c6487d61 | 500 | zlog_debug ("%s", buffer); |
2680aa2b | 501 | } |
502 | ||
6ac29a51 | 503 | static int |
718e3744 | 504 | ospf6_spf_calculation_thread (struct thread *t) |
505 | { | |
508e53e2 | 506 | struct ospf6_area *oa; |
507 | struct timeval start, end, runtime; | |
718e3744 | 508 | |
508e53e2 | 509 | oa = (struct ospf6_area *) THREAD_ARG (t); |
510 | oa->thread_spf_calculation = NULL; | |
718e3744 | 511 | |
2680aa2b | 512 | if (IS_OSPF6_DEBUG_SPF (PROCESS)) |
c6487d61 | 513 | zlog_debug ("SPF calculation for Area %s", oa->name); |
2680aa2b | 514 | if (IS_OSPF6_DEBUG_SPF (DATABASE)) |
515 | ospf6_spf_log_database (oa); | |
718e3744 | 516 | |
517 | /* execute SPF calculation */ | |
86f72dcb | 518 | quagga_gettime (QUAGGA_CLK_MONOTONIC, &start); |
508e53e2 | 519 | ospf6_spf_calculation (oa->ospf6->router_id, oa->spf_table, oa); |
86f72dcb | 520 | quagga_gettime (QUAGGA_CLK_MONOTONIC, &end); |
2680aa2b | 521 | timersub (&end, &start, &runtime); |
718e3744 | 522 | |
3b68735f | 523 | if (IS_OSPF6_DEBUG_SPF (PROCESS) || IS_OSPF6_DEBUG_SPF (TIME)) |
c6487d61 | 524 | zlog_debug ("SPF runtime: %ld sec %ld usec", |
525 | runtime.tv_sec, runtime.tv_usec); | |
718e3744 | 526 | |
508e53e2 | 527 | ospf6_intra_route_calculation (oa); |
6452df09 | 528 | ospf6_intra_brouter_calculation (oa); |
718e3744 | 529 | |
530 | return 0; | |
531 | } | |
532 | ||
533 | void | |
508e53e2 | 534 | ospf6_spf_schedule (struct ospf6_area *oa) |
718e3744 | 535 | { |
508e53e2 | 536 | if (oa->thread_spf_calculation) |
718e3744 | 537 | return; |
508e53e2 | 538 | oa->thread_spf_calculation = |
539 | thread_add_event (master, ospf6_spf_calculation_thread, oa, 0); | |
718e3744 | 540 | } |
541 | ||
542 | void | |
0c083ee9 | 543 | ospf6_spf_display_subtree (struct vty *vty, const char *prefix, int rest, |
508e53e2 | 544 | struct ospf6_vertex *v) |
718e3744 | 545 | { |
1eb8ef25 | 546 | struct listnode *node, *nnode; |
508e53e2 | 547 | struct ospf6_vertex *c; |
548 | char *next_prefix; | |
549 | int len; | |
550 | int restnum; | |
718e3744 | 551 | |
508e53e2 | 552 | /* "prefix" is the space prefix of the display line */ |
049207c3 | 553 | vty_out (vty, "%s+-%s [%d]%s", prefix, v->name, v->cost, VNL); |
718e3744 | 554 | |
508e53e2 | 555 | len = strlen (prefix) + 4; |
556 | next_prefix = (char *) malloc (len); | |
557 | if (next_prefix == NULL) | |
718e3744 | 558 | { |
049207c3 | 559 | vty_out (vty, "malloc failed%s", VNL); |
508e53e2 | 560 | return; |
718e3744 | 561 | } |
508e53e2 | 562 | snprintf (next_prefix, len, "%s%s", prefix, (rest ? "| " : " ")); |
718e3744 | 563 | |
508e53e2 | 564 | restnum = listcount (v->child_list); |
1eb8ef25 | 565 | for (ALL_LIST_ELEMENTS (v->child_list, node, nnode, c)) |
718e3744 | 566 | { |
508e53e2 | 567 | restnum--; |
568 | ospf6_spf_display_subtree (vty, next_prefix, restnum, c); | |
718e3744 | 569 | } |
718e3744 | 570 | |
508e53e2 | 571 | free (next_prefix); |
718e3744 | 572 | } |
573 | ||
3b68735f | 574 | DEFUN (debug_ospf6_spf_process, |
575 | debug_ospf6_spf_process_cmd, | |
576 | "debug ospf6 spf process", | |
508e53e2 | 577 | DEBUG_STR |
578 | OSPF6_STR | |
579 | "Debug SPF Calculation\n" | |
3b68735f | 580 | "Debug Detailed SPF Process\n" |
508e53e2 | 581 | ) |
718e3744 | 582 | { |
508e53e2 | 583 | unsigned char level = 0; |
3b68735f | 584 | level = OSPF6_DEBUG_SPF_PROCESS; |
508e53e2 | 585 | OSPF6_DEBUG_SPF_ON (level); |
586 | return CMD_SUCCESS; | |
718e3744 | 587 | } |
588 | ||
3b68735f | 589 | DEFUN (debug_ospf6_spf_time, |
590 | debug_ospf6_spf_time_cmd, | |
591 | "debug ospf6 spf time", | |
508e53e2 | 592 | DEBUG_STR |
718e3744 | 593 | OSPF6_STR |
508e53e2 | 594 | "Debug SPF Calculation\n" |
3b68735f | 595 | "Measure time taken by SPF Calculation\n" |
508e53e2 | 596 | ) |
718e3744 | 597 | { |
508e53e2 | 598 | unsigned char level = 0; |
3b68735f | 599 | level = OSPF6_DEBUG_SPF_TIME; |
508e53e2 | 600 | OSPF6_DEBUG_SPF_ON (level); |
718e3744 | 601 | return CMD_SUCCESS; |
602 | } | |
603 | ||
2680aa2b | 604 | DEFUN (debug_ospf6_spf_database, |
605 | debug_ospf6_spf_database_cmd, | |
606 | "debug ospf6 spf database", | |
607 | DEBUG_STR | |
608 | OSPF6_STR | |
609 | "Debug SPF Calculation\n" | |
610 | "Log number of LSAs at SPF Calculation time\n" | |
611 | ) | |
612 | { | |
613 | unsigned char level = 0; | |
614 | level = OSPF6_DEBUG_SPF_DATABASE; | |
615 | OSPF6_DEBUG_SPF_ON (level); | |
616 | return CMD_SUCCESS; | |
617 | } | |
618 | ||
3b68735f | 619 | DEFUN (no_debug_ospf6_spf_process, |
620 | no_debug_ospf6_spf_process_cmd, | |
621 | "no debug ospf6 spf process", | |
508e53e2 | 622 | NO_STR |
623 | DEBUG_STR | |
624 | OSPF6_STR | |
625 | "Quit Debugging SPF Calculation\n" | |
3b68735f | 626 | "Quit Debugging Detailed SPF Process\n" |
508e53e2 | 627 | ) |
718e3744 | 628 | { |
508e53e2 | 629 | unsigned char level = 0; |
3b68735f | 630 | level = OSPF6_DEBUG_SPF_PROCESS; |
508e53e2 | 631 | OSPF6_DEBUG_SPF_OFF (level); |
632 | return CMD_SUCCESS; | |
718e3744 | 633 | } |
634 | ||
3b68735f | 635 | DEFUN (no_debug_ospf6_spf_time, |
636 | no_debug_ospf6_spf_time_cmd, | |
637 | "no debug ospf6 spf time", | |
508e53e2 | 638 | NO_STR |
639 | DEBUG_STR | |
718e3744 | 640 | OSPF6_STR |
508e53e2 | 641 | "Quit Debugging SPF Calculation\n" |
3b68735f | 642 | "Quit Measuring time taken by SPF Calculation\n" |
508e53e2 | 643 | ) |
718e3744 | 644 | { |
508e53e2 | 645 | unsigned char level = 0; |
3b68735f | 646 | level = OSPF6_DEBUG_SPF_TIME; |
508e53e2 | 647 | OSPF6_DEBUG_SPF_OFF (level); |
718e3744 | 648 | return CMD_SUCCESS; |
649 | } | |
650 | ||
2680aa2b | 651 | DEFUN (no_debug_ospf6_spf_database, |
652 | no_debug_ospf6_spf_database_cmd, | |
653 | "no debug ospf6 spf database", | |
654 | NO_STR | |
655 | DEBUG_STR | |
656 | OSPF6_STR | |
657 | "Debug SPF Calculation\n" | |
658 | "Quit Logging number of LSAs at SPF Calculation time\n" | |
659 | ) | |
660 | { | |
661 | unsigned char level = 0; | |
662 | level = OSPF6_DEBUG_SPF_DATABASE; | |
663 | OSPF6_DEBUG_SPF_OFF (level); | |
664 | return CMD_SUCCESS; | |
665 | } | |
666 | ||
508e53e2 | 667 | int |
668 | config_write_ospf6_debug_spf (struct vty *vty) | |
718e3744 | 669 | { |
3b68735f | 670 | if (IS_OSPF6_DEBUG_SPF (PROCESS)) |
671 | vty_out (vty, "debug ospf6 spf process%s", VNL); | |
672 | if (IS_OSPF6_DEBUG_SPF (TIME)) | |
673 | vty_out (vty, "debug ospf6 spf time%s", VNL); | |
2680aa2b | 674 | if (IS_OSPF6_DEBUG_SPF (DATABASE)) |
675 | vty_out (vty, "debug ospf6 spf database%s", VNL); | |
508e53e2 | 676 | return 0; |
718e3744 | 677 | } |
678 | ||
508e53e2 | 679 | void |
6ac29a51 | 680 | install_element_ospf6_debug_spf (void) |
508e53e2 | 681 | { |
3b68735f | 682 | install_element (ENABLE_NODE, &debug_ospf6_spf_process_cmd); |
683 | install_element (ENABLE_NODE, &debug_ospf6_spf_time_cmd); | |
2680aa2b | 684 | install_element (ENABLE_NODE, &debug_ospf6_spf_database_cmd); |
3b68735f | 685 | install_element (ENABLE_NODE, &no_debug_ospf6_spf_process_cmd); |
686 | install_element (ENABLE_NODE, &no_debug_ospf6_spf_time_cmd); | |
2680aa2b | 687 | install_element (ENABLE_NODE, &no_debug_ospf6_spf_database_cmd); |
3b68735f | 688 | install_element (CONFIG_NODE, &debug_ospf6_spf_process_cmd); |
689 | install_element (CONFIG_NODE, &debug_ospf6_spf_time_cmd); | |
2680aa2b | 690 | install_element (CONFIG_NODE, &debug_ospf6_spf_database_cmd); |
3b68735f | 691 | install_element (CONFIG_NODE, &no_debug_ospf6_spf_process_cmd); |
692 | install_element (CONFIG_NODE, &no_debug_ospf6_spf_time_cmd); | |
2680aa2b | 693 | install_element (CONFIG_NODE, &no_debug_ospf6_spf_database_cmd); |
508e53e2 | 694 | } |
718e3744 | 695 | |
696 | void | |
6ac29a51 | 697 | ospf6_spf_init (void) |
718e3744 | 698 | { |
718e3744 | 699 | } |
700 | ||
508e53e2 | 701 |