2 * Copyright (C) 2003 Yasuhiro Ohara
4 * This file is part of GNU Zebra.
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
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.
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.
22 /* Shortest Path First calculation for OSPFv3 */
35 #include "ospf6_lsa.h"
36 #include "ospf6_lsdb.h"
37 #include "ospf6_route.h"
38 #include "ospf6_area.h"
39 #include "ospf6_spf.h"
40 #include "ospf6_intra.h"
41 #include "ospf6_interface.h"
44 unsigned char conf_debug_ospf6_spf
= 0;
47 ospf6_vertex_cmp (void *a
, void *b
)
49 struct ospf6_vertex
*va
= (struct ospf6_vertex
*) a
;
50 struct ospf6_vertex
*vb
= (struct ospf6_vertex
*) b
;
53 return (va
->cost
- vb
->cost
);
57 ospf6_vertex_id_cmp (void *a
, void *b
)
59 struct ospf6_vertex
*va
= (struct ospf6_vertex
*) a
;
60 struct ospf6_vertex
*vb
= (struct ospf6_vertex
*) b
;
63 ret
= ntohl (ospf6_linkstate_prefix_adv_router (&va
->vertex_id
)) -
64 ntohl (ospf6_linkstate_prefix_adv_router (&vb
->vertex_id
));
68 ret
= ntohl (ospf6_linkstate_prefix_id (&va
->vertex_id
)) -
69 ntohl (ospf6_linkstate_prefix_id (&vb
->vertex_id
));
74 ospf6_vertex_create (struct ospf6_lsa
*lsa
)
76 struct ospf6_vertex
*v
;
79 v
= (struct ospf6_vertex
*)
80 XMALLOC (MTYPE_OSPF6_VERTEX
, sizeof (struct ospf6_vertex
));
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
;
91 ospf6_linkstate_prefix (lsa
->header
->adv_router
, lsa
->header
->id
,
95 ospf6_linkstate_prefix2str (&v
->vertex_id
, v
->name
, sizeof (v
->name
));
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);
106 for (i
= 0; i
< OSPF6_MULTI_PATH_LIMIT
; i
++)
107 ospf6_nexthop_clear (&v
->nexthop
[i
]);
110 v
->child_list
= list_new ();
111 v
->child_list
->cmp
= ospf6_vertex_id_cmp
;
117 ospf6_vertex_delete (struct ospf6_vertex
*v
)
119 list_delete (v
->child_list
);
120 XFREE (MTYPE_OSPF6_VERTEX
, v
);
124 ospf6_lsdesc_lsa (caddr_t lsdesc
, struct ospf6_vertex
*v
)
126 struct ospf6_lsa
*lsa
;
128 u_int32_t id
= 0, adv_router
= 0;
130 if (VERTEX_IS_TYPE (NETWORK
, v
))
132 type
= htons (OSPF6_LSTYPE_ROUTER
);
134 adv_router
= NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc
);
138 if (ROUTER_LSDESC_IS_TYPE (POINTTOPOINT
, lsdesc
))
140 type
= htons (OSPF6_LSTYPE_ROUTER
);
142 adv_router
= ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc
);
144 else if (ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK
, lsdesc
))
146 type
= htons (OSPF6_LSTYPE_NETWORK
);
147 id
= htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc
));
148 adv_router
= ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc
);
152 lsa
= ospf6_lsdb_lookup (type
, id
, adv_router
, v
->area
->lsdb
);
154 if (IS_OSPF6_DEBUG_SPF (DETAIL
))
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
));
160 zlog_info (" Link to: %s", lsa
->name
);
162 zlog_info (" Link to: [%s Id:%s Adv:%s] No LSA",
163 OSPF6_LSTYPE_NAME (type
), ibuf
, abuf
);
170 ospf6_lsdesc_backlink (struct ospf6_lsa
*lsa
,
171 caddr_t lsdesc
, struct ospf6_vertex
*v
)
173 caddr_t backlink
, found
= NULL
;
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
)
182 assert (! (OSPF6_LSA_IS_TYPE (NETWORK
, lsa
) &&
183 VERTEX_IS_TYPE (NETWORK
, v
)));
185 if (OSPF6_LSA_IS_TYPE (NETWORK
, lsa
) &&
186 NETWORK_LSDESC_GET_NBR_ROUTERID (backlink
)
187 == v
->lsa
->header
->adv_router
)
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
))
198 if (! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT
, backlink
) ||
199 ! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT
, lsdesc
))
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
))
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
)
215 if (IS_OSPF6_DEBUG_SPF (DETAIL
))
216 zlog_info (" Backlink %s", (found
? "OK" : "FAIL"));
222 ospf6_nexthop_calc (struct ospf6_vertex
*w
, struct ospf6_vertex
*v
,
226 struct ospf6_interface
*oi
;
228 u_int32_t adv_router
;
229 struct ospf6_lsa
*lsa
;
230 struct ospf6_link_lsa
*link_lsa
;
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
);
239 if (IS_OSPF6_DEBUG_SPF (SUMMARY
))
240 zlog_warn ("Can't find interface in SPF: ifindex %d", ifindex
);
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
));
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
))
253 if (VERTEX_IS_TYPE (ROUTER
, v
) &&
254 htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc
)) != lsa
->header
->id
)
257 link_lsa
= (struct ospf6_link_lsa
*) OSPF6_LSA_HEADER_END (lsa
->header
);
258 if (IS_OSPF6_DEBUG_SPF (DETAIL
))
260 inet_ntop (AF_INET6
, &link_lsa
->linklocal_addr
, buf
, sizeof (buf
));
261 zlog_info (" nexthop %s from %s", buf
, lsa
->name
);
264 if (i
< OSPF6_MULTI_PATH_LIMIT
)
266 memcpy (&w
->nexthop
[i
].address
, &link_lsa
->linklocal_addr
,
267 sizeof (struct in6_addr
));
268 w
->nexthop
[i
].ifindex
= ifindex
;
273 if (i
== 0 && IS_OSPF6_DEBUG_SPF (SUMMARY
))
274 zlog_info ("No nexthop for %s found", w
->name
);
278 ospf6_spf_install (struct ospf6_vertex
*v
,
279 struct ospf6_route_table
*result_table
)
281 struct ospf6_route
*route
;
283 struct ospf6_vertex
*prev
, *w
;
286 if (IS_OSPF6_DEBUG_SPF (SUMMARY
))
287 zlog_info ("SPF install %s hops %d cost %d",
288 v
->name
, v
->hops
, v
->cost
);
290 route
= ospf6_route_lookup (&v
->vertex_id
, result_table
);
291 if (route
&& route
->path
.cost
< v
->cost
)
293 if (IS_OSPF6_DEBUG_SPF (SUMMARY
))
294 zlog_info (" already installed with lower cost (%d), ignore",
296 ospf6_vertex_delete (v
);
299 else if (route
&& route
->path
.cost
== v
->cost
)
301 if (IS_OSPF6_DEBUG_SPF (SUMMARY
))
302 zlog_info (" another path found, merge");
304 for (i
= 0; ospf6_nexthop_is_set (&v
->nexthop
[i
]) &&
305 i
< OSPF6_MULTI_PATH_LIMIT
; i
++)
307 for (j
= 0; j
< OSPF6_MULTI_PATH_LIMIT
; j
++)
309 if (ospf6_nexthop_is_set (&route
->nexthop
[j
]))
311 if (ospf6_nexthop_is_same (&route
->nexthop
[j
],
317 ospf6_nexthop_copy (&route
->nexthop
[j
], &v
->nexthop
[i
]);
322 prev
= (struct ospf6_vertex
*) route
->route_option
;
323 if (prev
->hops
> v
->hops
)
325 LIST_LOOP (prev
->child_list
, w
, node
)
327 assert (w
->parent
== prev
);
329 listnode_add_sort (v
->child_list
, w
);
331 listnode_delete (prev
->parent
->child_list
, prev
);
332 listnode_add_sort (v
->parent
->child_list
, v
);
334 ospf6_vertex_delete (prev
);
335 route
->route_option
= v
;
338 ospf6_vertex_delete (v
);
343 /* There should be no case where candidate being installed (variable
344 "v") is closer than the one in the SPF tree (variable "route").
345 In the case something has gone wrong with the behavior of
348 /* the case where the route exists already is handled and returned
350 assert (route
== NULL
);
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];
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
]);
372 listnode_add_sort (v
->parent
->child_list
, v
);
373 route
->route_option
= v
;
375 ospf6_route_add (route
, result_table
);
380 ospf6_spf_table_finish (struct ospf6_route_table
*result_table
)
382 struct ospf6_route
*route
;
383 struct ospf6_vertex
*v
;
384 for (route
= ospf6_route_head (result_table
); route
;
385 route
= ospf6_route_next (route
))
387 v
= (struct ospf6_vertex
*) route
->route_option
;
388 ospf6_vertex_delete (v
);
389 ospf6_route_remove (route
, result_table
);
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 */
396 ospf6_spf_calculation (u_int32_t router_id
,
397 struct ospf6_route_table
*result_table
,
398 struct ospf6_area
*oa
)
400 struct pqueue
*candidate_list
;
401 struct ospf6_vertex
*root
, *v
, *w
;
405 struct ospf6_lsa
*lsa
;
408 candidate_list
= pqueue_create ();
409 candidate_list
->cmp
= ospf6_vertex_cmp
;
411 ospf6_spf_table_finish (result_table
);
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
);
419 root
= ospf6_vertex_create (lsa
);
423 root
->nexthop
[0].ifindex
= 0; /* loopbak I/F is better ... */
424 inet_pton (AF_INET6
, "::1", &root
->nexthop
[0].address
);
426 /* Actually insert root to the candidate-list as the only candidate */
427 pqueue_enqueue (root
, candidate_list
);
429 /* Iterate until candidate-list becomes empty */
430 while (candidate_list
->size
)
432 /* get closest candidate from priority queue */
433 v
= pqueue_dequeue (candidate_list
);
435 /* installing may result in merging or rejecting of the vertex */
436 if (ospf6_spf_install (v
, result_table
) < 0)
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
)
446 lsa
= ospf6_lsdesc_lsa (lsdesc
, v
);
450 if (! ospf6_lsdesc_backlink (lsa
, lsdesc
, v
))
453 w
= ospf6_vertex_create (lsa
);
456 if (VERTEX_IS_TYPE (ROUTER
, v
))
458 w
->cost
= v
->cost
+ ROUTER_LSDESC_GET_METRIC (lsdesc
);
459 w
->hops
= v
->hops
+ (VERTEX_IS_TYPE (NETWORK
, w
) ? 0 : 1);
464 w
->hops
= v
->hops
+ 1;
467 /* nexthop calculation */
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
);
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
]);
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
);
487 pqueue_delete (candidate_list
);
491 ospf6_spf_calculation_thread (struct thread
*t
)
493 struct ospf6_area
*oa
;
494 struct timeval start
, end
, runtime
;
496 oa
= (struct ospf6_area
*) THREAD_ARG (t
);
497 oa
->thread_spf_calculation
= NULL
;
499 if (IS_OSPF6_DEBUG_SPF (SUMMARY
))
500 zlog_info ("SPF calculation for area %s", oa
->name
);
502 /* execute SPF calculation */
503 gettimeofday (&start
, (struct timezone
*) NULL
);
504 ospf6_spf_calculation (oa
->ospf6
->router_id
, oa
->spf_table
, oa
);
505 gettimeofday (&end
, (struct timezone
*) NULL
);
507 if (IS_OSPF6_DEBUG_SPF (SUMMARY
))
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
);
514 ospf6_intra_route_calculation (oa
);
515 ospf6_intra_brouter_calculation (oa
);
521 ospf6_spf_schedule (struct ospf6_area
*oa
)
523 if (oa
->thread_spf_calculation
)
525 oa
->thread_spf_calculation
=
526 thread_add_event (master
, ospf6_spf_calculation_thread
, oa
, 0);
530 ospf6_spf_display_subtree (struct vty
*vty
, char *prefix
, int rest
,
531 struct ospf6_vertex
*v
)
534 struct ospf6_vertex
*c
;
539 /* "prefix" is the space prefix of the display line */
540 vty_out (vty
, "%s+-%s [%d]%s", prefix
, v
->name
, v
->cost
, VNL
);
542 len
= strlen (prefix
) + 4;
543 next_prefix
= (char *) malloc (len
);
544 if (next_prefix
== NULL
)
546 vty_out (vty
, "malloc failed%s", VNL
);
549 snprintf (next_prefix
, len
, "%s%s", prefix
, (rest
? "| " : " "));
551 restnum
= listcount (v
->child_list
);
552 LIST_LOOP (v
->child_list
, c
, node
)
555 ospf6_spf_display_subtree (vty
, next_prefix
, restnum
, c
);
561 DEFUN (debug_ospf6_spf_detail
,
562 debug_ospf6_spf_detail_cmd
,
563 "debug ospf6 spf detail",
566 "Debug SPF Calculation\n"
567 "Debug Detailed SPF\n"
570 unsigned char level
= 0;
571 level
= OSPF6_DEBUG_SPF_SUMMARY
| OSPF6_DEBUG_SPF_DETAIL
;
572 OSPF6_DEBUG_SPF_ON (level
);
576 DEFUN (debug_ospf6_spf
,
581 "Debug SPF Calculation\n"
584 unsigned char level
= 0;
585 level
= OSPF6_DEBUG_SPF_SUMMARY
;
586 OSPF6_DEBUG_SPF_ON (level
);
590 DEFUN (no_debug_ospf6_spf_detail
,
591 no_debug_ospf6_spf_detail_cmd
,
592 "no debug ospf6 spf detail",
596 "Quit Debugging SPF Calculation\n"
597 "Quit Debugging Detailed SPF (change to debug summary)\n"
600 unsigned char level
= 0;
601 level
= OSPF6_DEBUG_SPF_DETAIL
;
602 OSPF6_DEBUG_SPF_OFF (level
);
606 DEFUN (no_debug_ospf6_spf
,
607 no_debug_ospf6_spf_cmd
,
608 "no debug ospf6 spf",
612 "Quit Debugging SPF Calculation\n"
615 unsigned char level
= 0;
616 level
= OSPF6_DEBUG_SPF_SUMMARY
| OSPF6_DEBUG_SPF_DETAIL
;
617 OSPF6_DEBUG_SPF_OFF (level
);
622 config_write_ospf6_debug_spf (struct vty
*vty
)
624 if (IS_OSPF6_DEBUG_SPF (DETAIL
))
625 vty_out (vty
, "debug ospf6 spf detail%s", VNL
);
626 else if (IS_OSPF6_DEBUG_SPF (SUMMARY
))
627 vty_out (vty
, "debug ospf6 spf%s", VNL
);
632 install_element_ospf6_debug_spf ()
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
);