1/* 2 * Copyright (C) 1999 Yasuhiro Ohara 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 */ 21/* Shortest Path First calculation for OSPFv3 */ 22 23#include "ospf6d.h" 24 25#include "linklist.h" 26#include "prefix.h" 27#include "table.h" 28 29#include "ospf6_proto.h" 30#include "ospf6_lsa.h" 31#include "ospf6_lsdb.h" 32#include "ospf6_route.h" 33#include "ospf6_spf.h" 34#include "ospf6_neighbor.h" 35#include "ospf6_interface.h" 36#include "ospf6_area.h" 37 38#include "ospf6_bintree.h" 39#include "ospf6_linklist.h" 40 41struct bintree *_candidate_list; 42struct linklist *nexthop_list; 43 44struct ospf6_spf_candidate_node 45{ 46 u_int32_t cost; 47 struct linklist *list; 48}; 49 50int 51ospf6_spf_candidate_node_cmp (void *a, void *b) 52{ 53 struct ospf6_spf_candidate_node *ca = a; 54 struct ospf6_spf_candidate_node *cb = b; 55 return ca->cost - cb->cost; 56} 57 58int 59ospf6_spf_vertex_cmp (void *a, void *b) 60{ 61 return 1; 62} 63 64void 65ospf6_spf_candidate_node_print (int indent_num, void *node) 66{ 67 struct ospf6_spf_candidate_node *cn = node; 68 char format[256]; 69 70 snprintf (format, sizeof (format), "%%%ds %%d (num: %%d)", 71 indent_num * 2 + 1); 72 zlog_info (format, " ", cn->cost, cn->list->count); 73} 74 75void 76ospf6_spf_candidate_init () 77{ 78 _candidate_list = bintree_create (); 79 _candidate_list->cmp = ospf6_spf_candidate_node_cmp; 80} 81 82u_int32_t 83ospf6_spf_candidate_count () 84{ 85 u_int32_t count = 0; 86 struct bintree_node node; 87 struct ospf6_spf_candidate_node *cnode; 88 89 for (bintree_head (_candidate_list, &node); ! bintree_end (&node); 90 bintree_next (&node)) 91 { 92 cnode = node.data; 93 count += cnode->list->count; 94 } 95 96 return count; 97} 98 99void 100ospf6_spf_candidate_print () 101{ 102 zlog_info ("---------------------------"); 103 bintree_print (ospf6_spf_candidate_node_print, _candidate_list); 104 zlog_info ("---------------------------"); 105} 106 107void 108ospf6_spf_candidate_enqueue (struct ospf6_vertex *v) 109{ 110 struct ospf6_spf_candidate_node req, *node; 111 112 memset (&req, 0, sizeof (req)); 113 req.cost = v->distance; 114 node = bintree_lookup (&req, _candidate_list); 115 116 if (node == NULL) 117 { 118 node = malloc (sizeof (struct ospf6_spf_candidate_node)); 119 node->cost = v->distance; 120 node->list = linklist_create (); 121 node->list->cmp = ospf6_spf_vertex_cmp; 122 bintree_add (node, _candidate_list); 123 } 124 125 linklist_add (v, node->list); 126 127#if 0 128 if (IS_OSPF6_DUMP_SPF) 129 ospf6_spf_candidate_print (); 130#endif 131} 132 133struct ospf6_vertex * 134ospf6_spf_candidate_dequeue () 135{ 136 struct ospf6_spf_candidate_node *node; 137 struct linklist_node lnode; 138 struct ospf6_vertex *ret; 139 140 node = bintree_lookup_min (_candidate_list); 141 if (node == NULL) 142 return NULL; 143 144 linklist_head (node->list, &lnode); 145 ret = lnode.data; 146 147 linklist_remove (ret, node->list); 148 if (node->list->count == 0) 149 { 150 linklist_delete (node->list); 151 bintree_remove (node, _candidate_list); 152 } 153 154#if 0 155 if (IS_OSPF6_DUMP_SPF) 156 ospf6_spf_candidate_print (); 157#endif 158 159 return ret; 160} 161 162void 163ospf6_spf_candidate_remove (struct ospf6_vertex *v) 164{ 165 struct bintree_node node; 166 struct ospf6_spf_candidate_node *cnode = NULL; 167 168 for (bintree_head (_candidate_list, &node); ! bintree_end (&node); 169 bintree_next (&node)) 170 { 171 cnode = node.data; 172 if (linklist_lookup (v, cnode->list)) 173 { 174 linklist_remove (v, cnode->list); 175 break; 176 } 177 } 178 179 if (cnode->list->count == 0) 180 { 181 linklist_delete (cnode->list); 182 bintree_remove (cnode, _candidate_list); 183 } 184} 185 186 187#define TIMER_SEC_MICRO 1000000 188 189/* timeval calculation */ 190static void 191ospf6_timeval_add (const struct timeval *t1, const struct timeval *t2, 192 struct timeval *result) 193{ 194 long moveup = 0; 195 196 result->tv_usec = t1->tv_usec + t2->tv_usec; 197 while (result->tv_usec > TIMER_SEC_MICRO) 198 { 199 result->tv_usec -= TIMER_SEC_MICRO; 200 moveup ++; 201 } 202 203 result->tv_sec = t1->tv_sec + t2->tv_sec + moveup; 204} 205 206static void 207ospf6_timeval_add_equal (const struct timeval *t, struct timeval *result) 208{ 209 struct timeval tmp; 210 ospf6_timeval_add (t, result, &tmp); 211 result->tv_sec = tmp.tv_sec; 212 result->tv_usec = tmp.tv_usec; 213} 214 215/* Compare timeval a and b. It returns an integer less than, equal 216 to, or great than zero if a is found, respectively, to be less 217 than, to match, or be greater than b. */ 218static int 219ospf6_timeval_cmp (const struct timeval t1, const struct timeval t2) 220{ 221 return (t1.tv_sec == t2.tv_sec 222 ? t1.tv_usec - t2.tv_usec : t1.tv_sec - t2.tv_sec); 223} 224 225 226static int 227ospf6_spf_lsd_num (struct ospf6_vertex *V, struct ospf6_area *o6a) 228{ 229 u_int16_t type; 230 u_int32_t id, adv_router; 231 struct ospf6_lsa *lsa; 232 233 if (V->vertex_id.id.s_addr) 234 type = htons (OSPF6_LSA_TYPE_NETWORK); 235 else 236 type = htons (OSPF6_LSA_TYPE_ROUTER); 237 id = V->vertex_id.id.s_addr; 238 adv_router = V->vertex_id.adv_router.s_addr; 239 240 lsa = ospf6_lsdb_lookup_lsdb (type, id, adv_router, o6a->lsdb); 241 if (! lsa) 242 { 243 zlog_err ("SPF: Can't find associated LSA for %s", V->string); 244 return 0; 245 } 246 247 return ospf6_lsa_lsd_num ((struct ospf6_lsa_header *) lsa->header); 248} 249 250/* RFC2328 section 16.1.1: 251 Check if there is at least one router in the path 252 from the root to this vertex. */ 253static int 254ospf6_spf_is_router_to_root (struct ospf6_vertex *c, 255 struct ospf6_spftree *spf_tree) 256{ 257 listnode node; 258 struct ospf6_vertex *p; 259 260 if (spf_tree->root == c) 261 return 0; 262 263 for (node = listhead (c->parent_list); node; nextnode (node)) 264 { 265 p = (struct ospf6_vertex *) getdata (node); 266 267 if (p == spf_tree->root) 268 return 0; 269 270 if (p->vertex_id.id.s_addr == 0) /* this is router */ 271 continue; 272 else if (ospf6_spf_is_router_to_root (p, spf_tree)) 273 continue; 274 275 return 0; 276 } 277 278 return 1; 279} 280 281static struct in6_addr * 282ospf6_spf_get_ipaddr (u_int32_t id, u_int32_t adv_router, u_int32_t ifindex) 283{ 284 char buf[64]; 285 struct ospf6_interface *o6i; 286 struct ospf6_neighbor *o6n; 287 struct ospf6_lsa *lsa; 288 struct ospf6_lsdb_node node; 289 290 o6i = ospf6_interface_lookup_by_index (ifindex); 291 if (! o6i) 292 { 293 zlog_err ("SPF: Can't find interface: index %d", ifindex); 294 return (struct in6_addr *) NULL; 295 } 296 297 /* Find Link-LSA of the vertex in question */ 298 lsa = NULL; 299 for (ospf6_lsdb_type_router (&node, htons (OSPF6_LSA_TYPE_LINK), 300 adv_router, o6i->lsdb); 301 ! ospf6_lsdb_is_end (&node); 302 ospf6_lsdb_next (&node)) 303 lsa = node.lsa; 304 305 /* return Linklocal Address field if the Link-LSA exists */ 306 if (lsa) 307 { 308 struct ospf6_link_lsa *link_lsa; 309 link_lsa = (struct ospf6_link_lsa *) (lsa->header + 1); 310 return &link_lsa->llsa_linklocal; 311 } 312 313 zlog_warn ("SPF: Can't find Link-LSA for %s, " 314 "use source address from his packet", 315 inet_ntop (AF_INET, &adv_router, buf, sizeof (buf))); 316 317 o6n = ospf6_neighbor_lookup (adv_router, o6i); 318 if (! o6n) 319 { 320 inet_ntop (AF_INET, &adv_router, buf, sizeof (buf)); 321 zlog_err ("SPF: Can't find neighbor %s in %s", 322 buf, o6i->interface->name); 323 return (struct in6_addr *) NULL; 324 } 325 326 return &o6n->hisaddr; 327} 328 329static int 330ospf6_spf_nexthop_calculation (struct ospf6_vertex *W, 331 u_int32_t ifindex, 332 struct ospf6_vertex *V, 333 struct ospf6_spftree *spf_tree) 334{ 335 struct ospf6_nexthop *nexthop, *n; 336 u_int32_t adv_router, id; 337 struct in6_addr nexthop_ipaddr, *ipaddr; 338 unsigned int nexthop_ifindex; 339 struct linklist_node node; 340 341 /* until this, nexthop_list should be untouched */ 342 assert (list_isempty (W->nexthop_list)); 343 344 /* If ther is at least one intervening router from root to W */ 345 if (ospf6_spf_is_router_to_root (W, spf_tree)) 346 { 347 /* Create no new nexthop, Inherit from the intervening router */ 348 for (linklist_head (V->nexthop_list, &node); ! linklist_end (&node); 349 linklist_next (&node)) 350 linklist_add (node.data, W->nexthop_list); 351 return 0; 352 } 353 354 /* Create new nexthop */ 355 356 adv_router = W->vertex_id.adv_router.s_addr; 357 id = W->vertex_id.id.s_addr; 358 359 nexthop_ifindex = 0; 360 memset (&nexthop_ipaddr, 0, sizeof (struct in6_addr)); 361 if (spf_tree->root && V == spf_tree->root) 362 { 363 nexthop_ifindex = ifindex; 364 if (! id) /* xxx, if V is router */ 365 { 366 ipaddr = ospf6_spf_get_ipaddr (id, adv_router, ifindex); 367 if (! ipaddr) 368 { 369 /* xxx, should trigger error and quit SPF calculation... */ 370 memset (&nexthop_ipaddr, 0xff, sizeof (struct in6_addr)); 371 return -1; 372 } 373 else 374 memcpy (&nexthop_ipaddr, ipaddr, sizeof (struct in6_addr)); 375 } 376 } 377 else 378 { 379 /* V is broadcast network, W is router */ 380 assert (V->vertex_id.id.s_addr != 0); 381 assert (W->vertex_id.id.s_addr == 0); 382 383 /* there should be the only one nexthop in V */ 384 assert (V->nexthop_list->count == 1); 385 386 linklist_head (V->nexthop_list, &node); 387 n = (struct ospf6_nexthop *) node.data; 388 nexthop_ifindex = n->ifindex; 389 ipaddr = ospf6_spf_get_ipaddr (id, adv_router, n->ifindex); 390 if (! ipaddr) 391 { 392 /* xxx, should trigger error and quit SPF calculation... */ 393 memset (&nexthop_ipaddr, 0xff, sizeof (struct in6_addr)); 394 return -1; 395 } 396 else 397 memcpy (&nexthop_ipaddr, ipaddr, sizeof (struct in6_addr)); 398 } 399 400 nexthop = XCALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_nexthop)); 401 nexthop->ifindex = nexthop_ifindex; 402 memcpy (&nexthop->address, &nexthop_ipaddr, sizeof (nexthop->address)); 403 404 linklist_add (nexthop, W->nexthop_list); 405 406 /* to hold malloced memory */ 407 linklist_add (nexthop, nexthop_list); 408 409 return 0; 410} 411 412static struct ospf6_vertex * 413ospf6_spf_vertex_create (int index, struct ospf6_vertex *V, 414 struct ospf6_area *o6a) 415{ 416 struct ospf6_lsa *lsa; 417 struct ospf6_router_lsa *router_lsa; 418 struct ospf6_router_lsd *router_lsd; 419 struct ospf6_network_lsa *network_lsa; 420 struct ospf6_network_lsd *network_lsd; 421 u_int32_t id, adv_router; 422 u_int16_t type; 423 void *lsd; 424 struct ospf6_vertex *W; 425 u_int16_t distance; 426 u_int32_t ifindex; 427 int backreference, lsdnum, i; 428 char buf_router[16], buf_id[16]; 429 430 type = id = adv_router = 0; 431 432 /* Get Linkstate description */ 433 lsd = ospf6_lsa_lsd_get (index, (struct ospf6_lsa_header *) V->lsa->header); 434 if (! lsd) 435 { 436 zlog_err ("SPF: Can't find %dth Link description from %s", 437 index, V->lsa->str); 438 return (struct ospf6_vertex *) NULL; 439 } 440 441 /* Check Link state description */ 442 distance = 0; 443 ifindex = 0; 444 if (V->lsa->header->type == htons (OSPF6_LSA_TYPE_ROUTER)) 445 { 446 router_lsd = lsd; 447 if (router_lsd->type == OSPF6_ROUTER_LSD_TYPE_POINTTOPOINT) 448 { 449 type = htons (OSPF6_LSA_TYPE_ROUTER); 450 id = htonl (0); 451 } 452 else if (router_lsd->type == OSPF6_ROUTER_LSD_TYPE_TRANSIT_NETWORK) 453 { 454 type = htons (OSPF6_LSA_TYPE_NETWORK); 455 id = router_lsd->neighbor_interface_id; 456 } 457 adv_router = router_lsd->neighbor_router_id; 458 distance = ntohs (router_lsd->metric); 459 ifindex = ntohl (router_lsd->interface_id); 460 } 461 else if (V->lsa->header->type == htons (OSPF6_LSA_TYPE_NETWORK)) 462 { 463 network_lsd = lsd; 464 type = htons (OSPF6_LSA_TYPE_ROUTER); 465 id = htonl (0); 466 adv_router = network_lsd->adv_router; 467 } 468 469 /* Avoid creating candidate of myself */ 470 if (adv_router == o6a->ospf6->router_id && 471 type == htons (OSPF6_LSA_TYPE_ROUTER)) 472 { 473 return (struct ospf6_vertex *) NULL; 474 } 475 476 /* Find Associated LSA for W */ 477 lsa = ospf6_lsdb_lookup_lsdb (type, id, adv_router, o6a->lsdb); 478 479 if (! lsa) 480 { 481 inet_ntop (AF_INET, &adv_router, buf_router, sizeof (buf_router)); 482 inet_ntop (AF_INET, &id, buf_id, sizeof (buf_id)); 483 484 if (type == htons (OSPF6_LSA_TYPE_ROUTER)) 485 zlog_err ("SPF: Can't find LSA for W (%s *): not found", 486 buf_router); 487 else 488 zlog_err ("SPF: Can't find LSA for W (%s %s): not found", 489 buf_router, buf_id); 490 return (struct ospf6_vertex *) NULL; 491 } 492 493 if (IS_LSA_MAXAGE (lsa)) 494 { 495 zlog_err ("SPF: Associated LSA for W is MaxAge: %s", lsa->str); 496 return (struct ospf6_vertex *) NULL; 497 } 498 499 /* Check back reference from W's lsa to V's lsa */ 500 backreference = 0; 501 lsdnum = ospf6_lsa_lsd_num ((struct ospf6_lsa_header *) lsa->header); 502 for (i = 0; i < lsdnum; i++) 503 { 504 if (ospf6_lsa_lsd_is_refer_ok (i, (struct ospf6_lsa_header *) lsa->header, 505 index, (struct ospf6_lsa_header *) V->lsa->header)) 506 backreference++; 507 } 508 if (! backreference) 509 { 510 zlog_err ("SPF: Back reference failed: V: %s, W: %s", 511 V->lsa->str, lsa->str); 512 return (struct ospf6_vertex *) NULL; 513 } 514 515 /* Allocate new ospf6_vertex for W */ 516 W = (struct ospf6_vertex *) XMALLOC (MTYPE_OSPF6_VERTEX, 517 sizeof (struct ospf6_vertex)); 518 if (! W) 519 { 520 zlog_err ("SPF: Can't allocate memory for Vertex"); 521 return (struct ospf6_vertex *) NULL; 522 } 523 memset (W, 0, sizeof (struct ospf6_vertex)); 524 525 /* Initialize */ 526 W->vertex_id.family = AF_UNSPEC; 527 W->vertex_id.prefixlen = 64; /* xxx */ 528 W->lsa = lsa; 529 if (type == htons (OSPF6_LSA_TYPE_ROUTER)) 530 W->vertex_id.id.s_addr = htonl (0); /* XXX */ 531 else 532 W->vertex_id.id.s_addr = W->lsa->header->id; 533 W->vertex_id.adv_router.s_addr = W->lsa->header->adv_router; 534 W->nexthop_list = linklist_create (); 535 W->path_list = list_new (); 536 W->parent_list = list_new (); 537 W->distance = V->distance + distance; 538 W->depth = V->depth + 1; 539 540 inet_ntop (AF_INET, &W->vertex_id.adv_router.s_addr, 541 buf_router, sizeof (buf_router)); 542 inet_ntop (AF_INET, &W->vertex_id.id.s_addr, buf_id, sizeof (buf_id)); 543 snprintf (W->string, sizeof (W->string), "[%s-%s (%d)]", 544 buf_router, buf_id, W->distance); 545 546 /* capability bits and optional capabilities */ 547 if (W->vertex_id.id.s_addr == 0) 548 { 549 router_lsa = (struct ospf6_router_lsa *) (W->lsa->header + 1); 550 W->capability_bits = router_lsa->bits; 551 memcpy (W->opt_capability, router_lsa->options, 552 sizeof (W->opt_capability)); 553 } 554 else 555 { 556 network_lsa = (struct ospf6_network_lsa *) (W->lsa->header + 1); 557 W->capability_bits = network_lsa->reserved; 558 memcpy (W->opt_capability, network_lsa->options, 559 sizeof (W->opt_capability)); 560 } 561 562 /* Link to Parent node */ 563 listnode_add (W->parent_list, V); 564 565 /* Nexthop Calculation */ 566 if (ospf6_spf_nexthop_calculation (W, ifindex, V, o6a->spf_tree) < 0) 567 return NULL; 568 569 return W; 570} 571 572static void 573ospf6_spf_vertex_delete (struct ospf6_vertex *v) 574{ 575 linklist_delete (v->nexthop_list); 576 list_delete (v->path_list); 577 list_delete (v->parent_list); 578 XFREE (MTYPE_OSPF6_VERTEX, v); 579} 580 581static void 582ospf6_spf_vertex_merge (struct ospf6_vertex *w, struct ospf6_vertex *x) 583{ 584 listnode node; 585 struct linklist_node lnode; 586 587 /* merge should be done on two nodes which are 588 almost the same */ 589 590 /* these w and x should be both candidate. 591 candidate should not have any children */ 592 assert (list_isempty (w->path_list)); 593 assert (list_isempty (x->path_list)); 594 595 /* merge parent list */ 596 for (node = listhead (w->parent_list); node; nextnode (node)) 597 { 598 if (listnode_lookup (x->parent_list, getdata (node))) 599 continue; 600 listnode_add (x->parent_list, getdata (node)); 601 } 602 603 /* merge nexthop list */ 604 for (linklist_head (w->nexthop_list, &lnode); ! linklist_end (&lnode); 605 linklist_next (&lnode)) 606 linklist_add (lnode.data, x->nexthop_list); 607} 608 609static void 610ospf6_spf_initialize (list candidate_list, struct ospf6_area *o6a) 611{ 612 listnode node; 613 struct ospf6_vertex *v; 614 struct ospf6_lsa *lsa; 615 u_int16_t type; 616 u_int32_t id, adv_router; 617 struct linklist_node lnode; 618 619 struct ospf6_nexthop *nexthop; 620 struct interface *ifp; 621 char buf_router[64], buf_id[64]; 622 623 /* delete topology routing table for this area */ 624 ospf6_route_remove_all (o6a->table_topology); 625 626 /* Delete previous spf tree */ 627 for (node = listhead (o6a->spf_tree->list); node; nextnode (node)) 628 { 629 v = (struct ospf6_vertex *) getdata (node); 630 ospf6_spf_vertex_delete (v); 631 } 632 list_delete_all_node (o6a->spf_tree->list); 633 634 for (linklist_head (nexthop_list, &lnode); ! linklist_end (&lnode); 635 linklist_next (&lnode)) 636 XFREE (MTYPE_OSPF6_VERTEX, lnode.data); 637 linklist_remove_all (nexthop_list); 638 639 /* Find self originated Router-LSA */ 640 type = htons (OSPF6_LSA_TYPE_ROUTER); 641 id = htonl (0); 642 adv_router = ospf6->router_id; 643 644 lsa = ospf6_lsdb_lookup_lsdb (type, id, adv_router, o6a->lsdb); 645 646 if (! lsa) 647 { 648 if (IS_OSPF6_DUMP_SPF) 649 zlog_info ("SPF: Can't find self originated Router-LSA"); 650 return; 651 } 652 if (IS_LSA_MAXAGE (lsa)) 653 { 654 zlog_err ("SPF: MaxAge self originated Router-LSA"); 655 return; 656 } 657 658 /* Create root vertex */ 659 v = (struct ospf6_vertex *) XMALLOC (MTYPE_OSPF6_VERTEX, 660 sizeof (struct ospf6_vertex)); 661 if (! v) 662 { 663 zlog_err ("SPF: Can't allocate memory for root vertex"); 664 return; 665 } 666 memset (v, 0, sizeof (struct ospf6_vertex)); 667 668 v->vertex_id.family = AF_UNSPEC; /* XXX */ 669 v->vertex_id.prefixlen = 64; /* XXX */ 670 v->vertex_id.id.s_addr = htonl (0); 671 v->vertex_id.adv_router.s_addr = ospf6->router_id; 672 if (ospf6_is_asbr (ospf6)) 673 OSPF6_OPT_SET (v->opt_capability, OSPF6_OPT_E); 674 OSPF6_OPT_SET (v->opt_capability, OSPF6_OPT_V6); 675 OSPF6_OPT_SET (v->opt_capability, OSPF6_OPT_R); 676 v->nexthop_list = linklist_create (); 677 v->path_list = list_new (); 678 v->parent_list = list_new (); 679 v->distance = 0; 680 v->depth = 0; 681 v->lsa = lsa; 682 683 inet_ntop (AF_INET, &v->vertex_id.adv_router.s_addr, 684 buf_router, sizeof (buf_router)); 685 inet_ntop (AF_INET, &v->vertex_id.id.s_addr, buf_id, sizeof (buf_id)); 686 snprintf (v->string, sizeof (v->string), "[%s-%s (%d)]", 687 buf_router, buf_id, v->distance); 688 689 nexthop = XCALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_nexthop)); 690 ifp = if_lookup_by_name ("lo0"); 691 if (ifp) 692 nexthop->ifindex = ifp->ifindex; 693 inet_pton (AF_INET6, "::1", &nexthop->address); 694 linklist_add (nexthop, v->nexthop_list); 695 linklist_add (nexthop, nexthop_list); 696 697 o6a->spf_tree->root = v; 698 listnode_add (candidate_list, v); 699 700 ospf6_spf_candidate_enqueue (v); 701} 702 703static struct ospf6_vertex * 704ospf6_spf_get_closest_candidate (list candidate_list) 705{ 706 listnode node; 707 struct ospf6_vertex *candidate, *closest; 708 709 closest = (struct ospf6_vertex *) NULL; 710 for (node = listhead (candidate_list); node; nextnode (node)) 711 { 712 candidate = (struct ospf6_vertex *) getdata (node); 713 714 if (closest && candidate->distance > closest->distance) 715 continue; 716 717 /* always choose network vertices if those're the same cost */ 718 if (closest && candidate->distance == closest->distance 719 && closest->vertex_id.id.s_addr != 0) 720 continue; 721 722 closest = candidate; 723 } 724 725 return closest; 726} 727 728static struct ospf6_vertex * 729ospf6_spf_get_same_candidate (struct ospf6_vertex *w, list candidate_list) 730{ 731 listnode node; 732 struct ospf6_vertex *c, *same; 733 734 same = (struct ospf6_vertex *) NULL; 735 for (node = listhead (candidate_list); node; nextnode (node)) 736 { 737 c = (struct ospf6_vertex *) getdata (node); 738 if (w->vertex_id.adv_router.s_addr != c->vertex_id.adv_router.s_addr) 739 continue; 740 if (w->vertex_id.id.s_addr != c->vertex_id.id.s_addr) 741 continue; 742 743 if (same) 744 zlog_warn ("SPF: duplicate candidates in candidate_list"); 745 746 same = c; 747 } 748 749 return same; 750} 751 752static void 753ospf6_spf_install (struct ospf6_vertex *vertex, struct ospf6_area *o6a) 754{ 755 listnode node; 756 struct ospf6_vertex *parent; 757 struct ospf6_nexthop *nexthop; 758 struct ospf6_route_req request; 759 struct linklist_node lnode; 760 761 struct ospf6_router_lsa *router_lsa; 762 struct ospf6_network_lsa *network_lsa; 763 764 router_lsa = OSPF6_LSA_HEADER_END (vertex->lsa->header); 765 network_lsa = OSPF6_LSA_HEADER_END (vertex->lsa->header); 766 767 if (IS_OSPF6_DUMP_SPF) 768 { 769 zlog_info ("SPF: Install: %s", vertex->string); 770 } 771 772 listnode_add (o6a->spf_tree->list, vertex); 773 774 for (node = listhead (vertex->parent_list); node; nextnode (node)) 775 { 776 parent = (struct ospf6_vertex *) getdata (node); 777 listnode_add (parent->path_list, vertex); 778 vertex->depth = parent->depth + 1; 779 } 780 781#if 0 782 if (vertex == o6a->spf_tree->root) 783 return; 784#endif /*0*/ 785 786 /* install route to topology table */ 787 memset (&request, 0, sizeof (request)); 788 if (vertex->vertex_id.id.s_addr) /* xxx */ 789 request.route.type = OSPF6_DEST_TYPE_NETWORK; 790 else 791 request.route.type = OSPF6_DEST_TYPE_ROUTER; 792 memcpy (&request.route.prefix, &vertex->vertex_id, 793 sizeof (struct prefix)); 794 795 request.path.area_id = o6a->area_id; 796 request.path.type = OSPF6_PATH_TYPE_INTRA; 797 request.path.cost = vertex->distance; 798 request.path.cost_e2 = 0; 799 request.path.origin.type = vertex->lsa->header->type; 800 request.path.origin.id = vertex->lsa->header->id; 801 request.path.origin.adv_router = vertex->lsa->header->adv_router; 802 if (vertex->lsa->header->type == htons (OSPF6_LSA_TYPE_ROUTER)) 803 request.path.router_bits = router_lsa->bits; 804 memcpy (&request.path.capability, vertex->opt_capability, 805 sizeof (request.path.capability)); 806 807#if 0 808 if (IS_OSPF6_DUMP_SPF) 809 zlog_info ("SPF: install %d nexthops for %s", 810 listcount (vertex->nexthop_list), vertex->string); 811#endif 812 813 for (linklist_head (vertex->nexthop_list, &lnode); ! linklist_end (&lnode); 814 linklist_next (&lnode)) 815 { 816 nexthop = lnode.data; 817 818 request.nexthop.ifindex = nexthop->ifindex; 819 memcpy (&request.nexthop.address, &nexthop->address, 820 sizeof (request.nexthop.address)); 821 822 ospf6_route_add (&request, o6a->table_topology); 823 } 824} 825 826struct ospf6_vertex * 827ospf6_spf_lookup (struct ospf6_vertex *w, struct ospf6_area *o6a) 828{ 829 listnode node; 830 struct ospf6_vertex *v; 831 832 for (node = listhead (o6a->spf_tree->list); node; nextnode (node)) 833 { 834 v = (struct ospf6_vertex *) getdata (node); 835 836 if (w->vertex_id.adv_router.s_addr != v->vertex_id.adv_router.s_addr) 837 continue; 838 if (w->vertex_id.id.s_addr != v->vertex_id.id.s_addr) 839 continue; 840 841 return v; 842 } 843 844 return (struct ospf6_vertex *) NULL; 845} 846 847u_int32_t stat_node = 0; 848u_int32_t stat_candidate = 0; 849u_int32_t stat_candidate_max = 0; 850u_int32_t stat_spf = 0; 851 852 853/* RFC2328 section 16.1 , RFC2740 section 3.8.1 */ 854static int 855ospf6_spf_calculation (struct ospf6_area *o6a) 856{ 857 list candidate_list; 858 struct ospf6_vertex *V, *W, *X; 859 int ldnum, i; 860 861 if (! o6a || ! o6a->spf_tree) 862 { 863 zlog_err ("SPF: Can't calculate SPF tree: malformed area"); 864 return -1; 865 } 866 867 stat_spf ++; 868 stat_node = 0; 869 stat_candidate = 0; 870 stat_candidate_max = 0; 871 872 if (IS_OSPF6_DUMP_SPF) 873 zlog_info ("SPF: Calculation for area %s", o6a->str); 874 875 ospf6_route_table_freeze (o6a->table_topology); 876 ospf6_route_remove_all (o6a->table_topology); 877 878 /* (1): Initialize the algorithm's data structures */ 879 candidate_list = list_new (); 880 ospf6_spf_initialize (candidate_list, o6a); 881 stat_candidate ++; 882 883 /* (3): Install closest from candidate list; if empty, break */ 884 while (listcount (candidate_list)) 885 { 886 V = ospf6_spf_get_closest_candidate (candidate_list); 887 listnode_delete (candidate_list, V); 888 889 { 890 struct ospf6_vertex *V_; 891 892 if (stat_candidate_max < ospf6_spf_candidate_count ()) 893 stat_candidate_max = ospf6_spf_candidate_count (); 894 895 V_ = ospf6_spf_candidate_dequeue (); 896 897#if 0 898 if (IS_OSPF6_DUMP_SPF) 899 { 900 zlog_info ("Candidate list count: %lu", 901 (u_long)ospf6_spf_candidate_count ()); 902 zlog_info ("*** Candidate %s: %p <-> %p", 903 (V == V_ ? "same" : "*** differ ***"), V, V_); 904 zlog_info (" %p: %s", V, V->string); 905 zlog_info (" %p: %s", V_, V_->string); 906 } 907#endif 908 909 } 910 911 stat_node++; 912 ospf6_spf_install (V, o6a); 913 914 /* (2): Examin LSA of just added vertex */ 915 ldnum = ospf6_spf_lsd_num (V, o6a); 916 for (i = 0; i < ldnum; i++) 917 { 918 /* (b): If no LSA, or MaxAge, or LinkBack fail, examin next */ 919 W = ospf6_spf_vertex_create (i, V, o6a); 920 if (! W) 921 continue; 922 923 stat_candidate ++; 924 925 /* (c) */ 926 if (ospf6_spf_lookup (W, o6a)) 927 { 928 if (IS_OSPF6_DUMP_SPF) 929 zlog_info ("SPF: %s: Already in SPF tree", W->string); 930 ospf6_spf_vertex_delete (W); 931 continue; 932 } 933 934 /* (d) */ 935 X = ospf6_spf_get_same_candidate (W, candidate_list); 936 if (X && X->distance < W->distance) 937 { 938 if (IS_OSPF6_DUMP_SPF) 939 zlog_info ("SPF: %s: More closer found", W->string); 940 ospf6_spf_vertex_delete (W); 941 continue; 942 } 943 if (X && X->distance == W->distance) 944 { 945 if (IS_OSPF6_DUMP_SPF) 946 zlog_info ("SPF: %s: new ECMP candidate", W->string); 947 ospf6_spf_vertex_merge (W, X); 948 ospf6_spf_vertex_delete (W); 949 continue; 950 } 951 952 if (X) 953 { 954 if (IS_OSPF6_DUMP_SPF) 955 zlog_info ("SPF: %s: Swap with old candidate", W->string); 956 listnode_delete (candidate_list, X); 957 ospf6_spf_candidate_remove (X); 958 ospf6_spf_vertex_delete (X); 959 } 960 else 961 { 962 if (IS_OSPF6_DUMP_SPF) 963 zlog_info ("SPF: %s: New Candidate", W->string); 964 } 965 966 if (stat_candidate_max < ospf6_spf_candidate_count ()) 967 stat_candidate_max = ospf6_spf_candidate_count (); 968 969 listnode_add (candidate_list, W); 970 ospf6_spf_candidate_enqueue (W); 971 } 972 } 973 974 assert (listcount (candidate_list) == 0); 975 list_free (candidate_list); 976 assert (ospf6_spf_candidate_count () == 0); 977 978 /* Clear thread timer */ 979 o6a->spf_tree->t_spf_calculation = (struct thread *) NULL; 980 981 if (IS_OSPF6_DUMP_SPF) 982 { 983 zlog_info ("SPF: Calculation for area %s done", o6a->str); 984 zlog_info ("SPF: Statistics: %luth", (u_long)stat_spf); 985 zlog_info ("SPF: Node Number: %lu", (u_long)stat_node); 986 zlog_info ("SPF: Candidate Number: %lu Max: %lu", 987 (u_long) stat_candidate, (u_long) stat_candidate_max); 988 } 989 990 ospf6_route_table_thaw (o6a->table_topology); 991 return 0; 992} 993 994int 995ospf6_spf_calculation_thread (struct thread *t) 996{ 997 struct ospf6_area *o6a; 998 struct timeval start, end, runtime, interval; 999 1000 o6a = (struct ospf6_area *) THREAD_ARG (t); 1001 if (! o6a) 1002 { 1003 zlog_err ("SPF: Thread error"); 1004 return -1; 1005 } 1006 1007 if (! o6a->spf_tree) 1008 { 1009 zlog_err ("SPF: Can't find SPF Tree for area: %s", o6a->str); 1010 return -1; 1011 } 1012 1013 /* execute SPF calculation */ 1014 gettimeofday (&start, (struct timezone *) NULL); 1015 ospf6_spf_calculation (o6a); 1016 gettimeofday (&end, (struct timezone *) NULL); 1017 1018 /* update statistics */ 1019 o6a->spf_tree->timerun ++; 1020 ospf6_timeval_sub (&end, &start, &runtime); 1021 ospf6_timeval_add_equal (&runtime, &o6a->spf_tree->runtime_total); 1022 1023 if (o6a->spf_tree->timerun == 1) 1024 { 1025 o6a->spf_tree->runtime_min.tv_sec = runtime.tv_sec; 1026 o6a->spf_tree->runtime_min.tv_usec = runtime.tv_usec; 1027 o6a->spf_tree->runtime_max.tv_sec = runtime.tv_sec; 1028 o6a->spf_tree->runtime_max.tv_usec = runtime.tv_usec; 1029 } 1030 if (ospf6_timeval_cmp (o6a->spf_tree->runtime_min, runtime) > 0) 1031 { 1032 o6a->spf_tree->runtime_min.tv_sec = runtime.tv_sec; 1033 o6a->spf_tree->runtime_min.tv_usec = runtime.tv_usec; 1034 } 1035 if (ospf6_timeval_cmp (runtime, o6a->spf_tree->runtime_max) > 0) 1036 { 1037 o6a->spf_tree->runtime_max.tv_sec = runtime.tv_sec; 1038 o6a->spf_tree->runtime_max.tv_usec = runtime.tv_usec; 1039 } 1040 1041 if (o6a->spf_tree->timerun == 1) 1042 { 1043 ospf6_timeval_sub (&start, &ospf6->starttime, &interval); 1044 ospf6_timeval_add_equal (&interval, &o6a->spf_tree->interval_total); 1045 o6a->spf_tree->interval_min.tv_sec = interval.tv_sec; 1046 o6a->spf_tree->interval_min.tv_usec = interval.tv_usec; 1047 o6a->spf_tree->interval_max.tv_sec = interval.tv_sec; 1048 o6a->spf_tree->interval_max.tv_usec = interval.tv_usec; 1049 } 1050 else 1051 { 1052 ospf6_timeval_sub (&start, &o6a->spf_tree->updated_time, &interval); 1053 ospf6_timeval_add_equal (&interval, &o6a->spf_tree->interval_total); 1054 if (ospf6_timeval_cmp (o6a->spf_tree->interval_min, interval) > 0) 1055 { 1056 o6a->spf_tree->interval_min.tv_sec = interval.tv_sec; 1057 o6a->spf_tree->interval_min.tv_usec = interval.tv_usec; 1058 } 1059 if (ospf6_timeval_cmp (interval, o6a->spf_tree->interval_max) > 0) 1060 { 1061 o6a->spf_tree->interval_max.tv_sec = interval.tv_sec; 1062 o6a->spf_tree->interval_max.tv_usec = interval.tv_usec; 1063 } 1064 } 1065 o6a->spf_tree->updated_time.tv_sec = end.tv_sec; 1066 o6a->spf_tree->updated_time.tv_usec = end.tv_usec; 1067 1068 /* clear thread */ 1069 o6a->spf_tree->t_spf_calculation = (struct thread *) NULL; 1070 1071 return 0; 1072} 1073 1074void 1075ospf6_spf_database_hook (struct ospf6_lsa *old, struct ospf6_lsa *new) 1076{ 1077 struct ospf6_area *o6a = NULL; 1078 struct ospf6_interface *o6i = NULL; 1079 1080 if (new->header->type == htons (OSPF6_LSA_TYPE_ROUTER) || 1081 new->header->type == htons (OSPF6_LSA_TYPE_NETWORK)) 1082 o6a = new->scope; 1083 else if (new->header->type == htons (OSPF6_LSA_TYPE_LINK)) 1084 { 1085 o6i = new->scope; 1086 o6a = o6i->area; 1087 } 1088 1089 if (o6a) 1090 ospf6_spf_calculation_schedule (o6a->area_id); 1091} 1092 1093void 1094ospf6_spf_calculation_schedule (u_int32_t area_id) 1095{ 1096 struct ospf6_area *o6a; 1097 char buf[64]; 1098 1099 o6a = ospf6_area_lookup (area_id, ospf6); 1100 if (! o6a) 1101 { 1102 inet_ntop (AF_INET, &area_id, buf, sizeof (buf)); 1103 zlog_err ("SPF: Can't find area: %s", buf); 1104 return; 1105 } 1106 1107 if (! o6a->spf_tree) 1108 { 1109 zlog_err ("SPF: Can't find SPF Tree for area: %s", o6a->str); 1110 return; 1111 } 1112 1113 if (o6a->spf_tree->t_spf_calculation) 1114 return; 1115 1116 o6a->spf_tree->t_spf_calculation = 1117 thread_add_event (master, ospf6_spf_calculation_thread, o6a, 0); 1118} 1119 1120struct ospf6_spftree * 1121ospf6_spftree_create () 1122{ 1123 struct ospf6_spftree *spf_tree; 1124 spf_tree = (struct ospf6_spftree *) XMALLOC (MTYPE_OSPF6_SPFTREE, 1125 sizeof (struct ospf6_spftree)); 1126 if (! spf_tree) 1127 { 1128 zlog_err ("SPF: Can't allocate memory for SPF tree"); 1129 return (struct ospf6_spftree *) NULL; 1130 } 1131 memset (spf_tree, 0, sizeof (spf_tree)); 1132 1133 spf_tree->list = list_new (); 1134 1135 return spf_tree; 1136} 1137 1138void 1139ospf6_spftree_delete (struct ospf6_spftree *spf_tree) 1140{ 1141 listnode node; 1142 struct ospf6_vertex *v; 1143 1144 /* Delete spf tree */ 1145 for (node = listhead (spf_tree->list); node; nextnode (node)) 1146 { 1147 v = (struct ospf6_vertex *) getdata (node); 1148 ospf6_spf_vertex_delete (v); 1149 } 1150 list_delete_all_node (spf_tree->list); 1151 1152 XFREE (MTYPE_OSPF6_SPFTREE, spf_tree); 1153} 1154 1155void 1156ospf6_nexthop_show (struct vty *vty, struct ospf6_nexthop *nexthop) 1157{ 1158 char buf[128], *ifname; 1159 struct ospf6_interface *o6i; 1160 1161 ifname = NULL; 1162 1163 o6i = ospf6_interface_lookup_by_index (nexthop->ifindex); 1164 if (! o6i) 1165 { 1166 zlog_err ("Spf: invalid ifindex %d in nexthop", nexthop->ifindex); 1167 } 1168 else 1169 ifname = o6i->interface->name; 1170 1171 inet_ntop (AF_INET6, &nexthop->address, buf, sizeof (buf)); 1172 vty_out (vty, " %s%%%s(%d)%s", buf, ifname, 1173 nexthop->ifindex, VTY_NEWLINE); 1174} 1175 1176void 1177ospf6_vertex_show (struct vty *vty, struct ospf6_vertex *vertex) 1178{ 1179 listnode node; 1180 struct ospf6_vertex *v; 1181 struct linklist_node lnode; 1182 1183 vty_out (vty, "SPF node %s%s", vertex->string, VTY_NEWLINE); 1184 vty_out (vty, " cost to this node: %d%s", vertex->distance, VTY_NEWLINE); 1185 vty_out (vty, " hops to this node: %d%s", vertex->depth, VTY_NEWLINE); 1186 1187 vty_out (vty, " nexthops reachable to this node:%s", VTY_NEWLINE); 1188 for (linklist_head (vertex->nexthop_list, &lnode); 1189 ! linklist_end (&lnode); 1190 linklist_next (&lnode)) 1191 ospf6_nexthop_show (vty, (struct ospf6_nexthop *) lnode.data); 1192 1193 vty_out (vty, " parent nodes to this node:%s", VTY_NEWLINE); 1194 if (! list_isempty (vertex->parent_list)) 1195 vty_out (vty, " "); 1196 for (node = listhead (vertex->parent_list); node; nextnode (node)) 1197 { 1198 v = (struct ospf6_vertex *) getdata (node); 1199 vty_out (vty, "%s ", v->string); 1200 } 1201 if (! list_isempty (vertex->parent_list)) 1202 vty_out (vty, "%s", VTY_NEWLINE); 1203 1204 vty_out (vty, " child nodes to this node:%s", VTY_NEWLINE); 1205 if (! list_isempty (vertex->path_list)) 1206 vty_out (vty, " "); 1207 for (node = listhead (vertex->path_list); node; nextnode (node)) 1208 { 1209 v = (struct ospf6_vertex *) getdata (node); 1210 vty_out (vty, "%s ", v->string); 1211 } 1212 if (! list_isempty (vertex->path_list)) 1213 vty_out (vty, "%s", VTY_NEWLINE); 1214 1215 vty_out (vty, "%s", VTY_NEWLINE); 1216} 1217 1218void 1219ospf6_spf_statistics_show (struct vty *vty, struct ospf6_spftree *spf_tree) 1220{ 1221 listnode node; 1222 struct ospf6_vertex *vertex; 1223 u_int router_count, network_count, maxdepth; 1224 struct timeval runtime_avg, interval_avg, last_updated, now; 1225 char rmin[64], rmax[64], ravg[64]; 1226 char imin[64], imax[64], iavg[64]; 1227 char last_updated_string[64]; 1228 1229 maxdepth = router_count = network_count = 0; 1230 for (node = listhead (spf_tree->list); node; nextnode (node)) 1231 { 1232 vertex = (struct ospf6_vertex *) getdata (node); 1233 if (vertex->vertex_id.id.s_addr) 1234 network_count++; 1235 else 1236 router_count++; 1237 if (maxdepth < vertex->depth) 1238 maxdepth = vertex->depth; 1239 } 1240 1241 ospf6_timeval_div (&spf_tree->runtime_total, spf_tree->timerun, 1242 &runtime_avg); 1243 ospf6_timeval_string (&spf_tree->runtime_min, rmin, sizeof (rmin)); 1244 ospf6_timeval_string (&spf_tree->runtime_max, rmax, sizeof (rmax)); 1245 ospf6_timeval_string (&runtime_avg, ravg, sizeof (ravg)); 1246 1247 ospf6_timeval_div (&spf_tree->interval_total, spf_tree->timerun, 1248 &interval_avg); 1249 ospf6_timeval_string (&spf_tree->interval_min, imin, sizeof (imin)); 1250 ospf6_timeval_string (&spf_tree->interval_max, imax, sizeof (imax)); 1251 ospf6_timeval_string (&interval_avg, iavg, sizeof (iavg)); 1252 1253 gettimeofday (&now, (struct timezone *) NULL); 1254 ospf6_timeval_sub (&now, &spf_tree->updated_time, &last_updated); 1255 ospf6_timeval_string (&last_updated, last_updated_string, 1256 sizeof (last_updated_string)); 1257 1258 vty_out (vty, " SPF algorithm executed %d times%s", 1259 spf_tree->timerun, VTY_NEWLINE); 1260 vty_out (vty, " Average time to run SPF: %s%s", 1261 ravg, VTY_NEWLINE); 1262 vty_out (vty, " Maximum time to run SPF: %s%s", 1263 rmax, VTY_NEWLINE); 1264 vty_out (vty, " Average interval of SPF: %s%s", 1265 iavg, VTY_NEWLINE); 1266 vty_out (vty, " SPF last updated: %s ago%s", 1267 last_updated_string, VTY_NEWLINE); 1268 vty_out (vty, " Current SPF node count: %d%s", 1269 listcount (spf_tree->list), VTY_NEWLINE); 1270 vty_out (vty, " Router: %d Network: %d%s", 1271 router_count, network_count, VTY_NEWLINE); 1272 vty_out (vty, " Maximum of Hop count to nodes: %d%s", 1273 maxdepth, VTY_NEWLINE); 1274} 1275 1276DEFUN (show_ipv6_ospf6_area_spf_node, 1277 show_ipv6_ospf6_area_spf_node_cmd, 1278 "show ipv6 ospf6 area A.B.C.D spf node", 1279 SHOW_STR 1280 IP6_STR 1281 OSPF6_STR 1282 OSPF6_AREA_STR 1283 OSPF6_AREA_ID_STR 1284 "Shortest Path First caculation\n" 1285 "vertex infomation\n" 1286 ) 1287{ 1288 listnode i; 1289 u_int32_t area_id; 1290 struct ospf6_area *o6a; 1291 struct ospf6_vertex *vertex; 1292 1293 OSPF6_CMD_CHECK_RUNNING (); 1294 1295 inet_pton (AF_INET, argv[0], &area_id); 1296 o6a = ospf6_area_lookup (area_id, ospf6); 1297 if (! o6a) 1298 return CMD_SUCCESS; 1299 1300 for (i = listhead (o6a->spf_tree->list); i; nextnode (i)) 1301 { 1302 vertex = (struct ospf6_vertex *) getdata (i); 1303 ospf6_vertex_show (vty, vertex); 1304 } 1305 1306 return CMD_SUCCESS; 1307} 1308 1309static void 1310ospf6_spftree_show (struct vty *vty, char *prefix, int current_rest, 1311 struct ospf6_vertex *v) 1312{ 1313 char *p; 1314 int psize; 1315 int restnum; 1316 listnode node; 1317 1318 vty_out (vty, "%s+-%s%s", prefix, v->string, VTY_NEWLINE); 1319 1320 if (listcount (v->path_list) == 0) 1321 return; 1322 1323 psize = strlen (prefix) + 3; 1324 p = malloc (psize); 1325 if (!p) 1326 { 1327 vty_out (vty, "depth too long ...%s", VTY_NEWLINE); 1328 return; 1329 } 1330 1331 restnum = listcount (v->path_list); 1332 for (node = listhead (v->path_list); node; nextnode (node)) 1333 { 1334 --restnum; 1335 snprintf (p, psize, "%s%s", prefix, (current_rest ? "| " : " ")); 1336 ospf6_spftree_show (vty, p, restnum, 1337 (struct ospf6_vertex *) getdata (node)); 1338 } 1339 1340 free (p); 1341} 1342 1343DEFUN (show_ipv6_ospf6_area_spf_tree, 1344 show_ipv6_ospf6_area_spf_tree_cmd, 1345 "show ipv6 ospf6 area A.B.C.D spf tree", 1346 SHOW_STR 1347 IP6_STR 1348 OSPF6_STR 1349 OSPF6_AREA_STR 1350 OSPF6_AREA_ID_STR 1351 "Shortest Path First caculation\n" 1352 "Displays spf tree\n") 1353{ 1354 u_int32_t area_id; 1355 struct ospf6_area *o6a; 1356 1357 OSPF6_CMD_CHECK_RUNNING (); 1358 1359 inet_pton (AF_INET, argv[0], &area_id); 1360 o6a = ospf6_area_lookup (area_id, ospf6); 1361 if (! o6a) 1362 return CMD_SUCCESS; 1363 1364 vty_out (vty, "%s SPF tree for Area %s%s%s", 1365 VTY_NEWLINE, o6a->str, VTY_NEWLINE, VTY_NEWLINE); 1366 1367 if (! o6a->spf_tree->root) 1368 return CMD_SUCCESS; 1369 1370 ospf6_spftree_show (vty, "", 0, o6a->spf_tree->root); 1371 return CMD_SUCCESS; 1372} 1373 1374DEFUN (show_ipv6_ospf6_area_topology, 1375 show_ipv6_ospf6_area_topology_cmd, 1376 "show ipv6 ospf6 area A.B.C.D topology", 1377 SHOW_STR 1378 IP6_STR 1379 OSPF6_STR 1380 OSPF6_AREA_STR 1381 OSPF6_AREA_ID_STR 1382 OSPF6_SPF_STR 1383 "Displays SPF topology table\n") 1384{ 1385 struct ospf6_area *o6a; 1386 u_int32_t area_id; 1387 1388 OSPF6_CMD_CHECK_RUNNING (); 1389 1390 inet_pton (AF_INET, argv[0], &area_id); 1391 o6a = ospf6_area_lookup (area_id, ospf6); 1392 1393 if (! o6a) 1394 return CMD_SUCCESS; 1395 1396 argc -= 1; 1397 argv += 1; 1398 1399 return ospf6_route_table_show (vty, argc, argv, o6a->table_topology); 1400} 1401 1402ALIAS (show_ipv6_ospf6_area_topology, 1403 show_ipv6_ospf6_area_topology_router_cmd, 1404 "show ipv6 ospf6 area A.B.C.D topology (A.B.C.D|<0-4294967295>|detail)", 1405 SHOW_STR 1406 IP6_STR 1407 OSPF6_STR 1408 OSPF6_AREA_STR 1409 OSPF6_AREA_ID_STR 1410 OSPF6_SPF_STR 1411 "Displays SPF topology table\n" 1412 OSPF6_ROUTER_ID_STR 1413 OSPF6_ROUTER_ID_STR 1414 ) 1415 1416ALIAS (show_ipv6_ospf6_area_topology, 1417 show_ipv6_ospf6_area_topology_router_lsid_cmd, 1418 "show ipv6 ospf6 area A.B.C.D topology (A.B.C.D|<0-4294967295>) (A.B.C.D|<0-4294967295>)", 1419 SHOW_STR 1420 IP6_STR 1421 OSPF6_STR 1422 OSPF6_AREA_STR 1423 OSPF6_AREA_ID_STR 1424 OSPF6_SPF_STR 1425 "Displays SPF topology table\n" 1426 OSPF6_ROUTER_ID_STR 1427 OSPF6_ROUTER_ID_STR 1428 OSPF6_LS_ID_STR 1429 OSPF6_LS_ID_STR 1430 ) 1431 1432void 1433ospf6_spf_init () 1434{ 1435 nexthop_list = linklist_create (); 1436 ospf6_spf_candidate_init (); 1437 install_element (VIEW_NODE, &show_ipv6_ospf6_area_spf_node_cmd); 1438 install_element (VIEW_NODE, &show_ipv6_ospf6_area_spf_tree_cmd); 1439 install_element (VIEW_NODE, &show_ipv6_ospf6_area_topology_cmd); 1440 install_element (VIEW_NODE, &show_ipv6_ospf6_area_topology_router_cmd); 1441 install_element (VIEW_NODE, &show_ipv6_ospf6_area_topology_router_lsid_cmd); 1442 install_element (ENABLE_NODE, &show_ipv6_ospf6_area_spf_node_cmd); 1443 install_element (ENABLE_NODE, &show_ipv6_ospf6_area_spf_tree_cmd); 1444 install_element (ENABLE_NODE, &show_ipv6_ospf6_area_topology_cmd); 1445 install_element (ENABLE_NODE, &show_ipv6_ospf6_area_topology_router_cmd); 1446 install_element (ENABLE_NODE, &show_ipv6_ospf6_area_topology_router_lsid_cmd); 1447} 1448 1449