1/* 2 * Copyright (C) 2003 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 22/* Shortest Path First calculation for OSPFv3 */ 23 24#include <zebra.h> 25 26#include "log.h" 27#include "memory.h" 28#include "command.h" 29#include "vty.h" 30#include "prefix.h" 31#include "pqueue.h" 32#include "linklist.h" 33#include "thread.h" 34 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" 42#include "ospf6d.h" 43#include "ospf6_abr.h" 44 45unsigned char conf_debug_ospf6_spf = 0; 46 47static int 48ospf6_vertex_cmp (void *a, void *b) 49{ 50 struct ospf6_vertex *va = (struct ospf6_vertex *) a; 51 struct ospf6_vertex *vb = (struct ospf6_vertex *) b; 52 53 /* ascending order */ 54 if (va->cost != vb->cost) 55 return (va->cost - vb->cost); 56 return (va->hops - vb->hops); 57} 58 59static int 60ospf6_vertex_id_cmp (void *a, void *b) 61{ 62 struct ospf6_vertex *va = (struct ospf6_vertex *) a; 63 struct ospf6_vertex *vb = (struct ospf6_vertex *) b; 64 int ret = 0; 65 66 ret = ntohl (ospf6_linkstate_prefix_adv_router (&va->vertex_id)) - 67 ntohl (ospf6_linkstate_prefix_adv_router (&vb->vertex_id)); 68 if (ret) 69 return ret; 70 71 ret = ntohl (ospf6_linkstate_prefix_id (&va->vertex_id)) - 72 ntohl (ospf6_linkstate_prefix_id (&vb->vertex_id)); 73 return ret; 74} 75 76static struct ospf6_vertex * 77ospf6_vertex_create (struct ospf6_lsa *lsa) 78{ 79 struct ospf6_vertex *v; 80 int i; 81 82 v = (struct ospf6_vertex *) 83 XMALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_vertex)); 84 85 /* type */ 86 if (ntohs (lsa->header->type) == OSPF6_LSTYPE_ROUTER) 87 v->type = OSPF6_VERTEX_TYPE_ROUTER; 88 else if (ntohs (lsa->header->type) == OSPF6_LSTYPE_NETWORK) 89 v->type = OSPF6_VERTEX_TYPE_NETWORK; 90 else 91 assert (0); 92 93 /* vertex_id */ 94 ospf6_linkstate_prefix (lsa->header->adv_router, lsa->header->id, 95 &v->vertex_id); 96 97 /* name */ 98 ospf6_linkstate_prefix2str (&v->vertex_id, v->name, sizeof (v->name)); 99 100 /* Associated LSA */ 101 v->lsa = lsa; 102 103 /* capability bits + options */ 104 v->capability = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header)); 105 v->options[0] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 1); 106 v->options[1] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 2); 107 v->options[2] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 3); 108 109 for (i = 0; i < OSPF6_MULTI_PATH_LIMIT; i++) 110 ospf6_nexthop_clear (&v->nexthop[i]); 111 112 v->parent = NULL; 113 v->child_list = list_new (); 114 v->child_list->cmp = ospf6_vertex_id_cmp; 115 116 return v; 117} 118 119static void 120ospf6_vertex_delete (struct ospf6_vertex *v) 121{ 122 list_delete (v->child_list); 123 XFREE (MTYPE_OSPF6_VERTEX, v); 124} 125 126static struct ospf6_lsa * 127ospf6_lsdesc_lsa (caddr_t lsdesc, struct ospf6_vertex *v) 128{ 129 struct ospf6_lsa *lsa; 130 u_int16_t type = 0; 131 u_int32_t id = 0, adv_router = 0; 132 133 if (VERTEX_IS_TYPE (NETWORK, v)) 134 { 135 type = htons (OSPF6_LSTYPE_ROUTER); 136 id = htonl (0); 137 adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc); 138 } 139 else 140 { 141 if (ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc)) 142 { 143 type = htons (OSPF6_LSTYPE_ROUTER); 144 id = htonl (0); 145 adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc); 146 } 147 else if (ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, lsdesc)) 148 { 149 type = htons (OSPF6_LSTYPE_NETWORK); 150 id = htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc)); 151 adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc); 152 } 153 } 154 155 lsa = ospf6_lsdb_lookup (type, id, adv_router, v->area->lsdb); 156 157 if (IS_OSPF6_DEBUG_SPF (PROCESS)) 158 { 159 char ibuf[16], abuf[16]; 160 inet_ntop (AF_INET, &id, ibuf, sizeof (ibuf)); 161 inet_ntop (AF_INET, &adv_router, abuf, sizeof (abuf)); 162 if (lsa) 163 zlog_debug (" Link to: %s", lsa->name); 164 else 165 zlog_debug (" Link to: [%s Id:%s Adv:%s] No LSA", 166 ospf6_lstype_name (type), ibuf, abuf); 167 } 168 169 return lsa; 170} 171 172static char * 173ospf6_lsdesc_backlink (struct ospf6_lsa *lsa, 174 caddr_t lsdesc, struct ospf6_vertex *v) 175{ 176 caddr_t backlink, found = NULL; 177 int size; 178 179 size = (OSPF6_LSA_IS_TYPE (ROUTER, lsa) ? 180 sizeof (struct ospf6_router_lsdesc) : 181 sizeof (struct ospf6_network_lsdesc)); 182 for (backlink = OSPF6_LSA_HEADER_END (lsa->header) + 4; 183 backlink + size <= OSPF6_LSA_END (lsa->header); backlink += size) 184 { 185 assert (! (OSPF6_LSA_IS_TYPE (NETWORK, lsa) && 186 VERTEX_IS_TYPE (NETWORK, v))); 187 188 if (OSPF6_LSA_IS_TYPE (NETWORK, lsa) && 189 NETWORK_LSDESC_GET_NBR_ROUTERID (backlink) 190 == v->lsa->header->adv_router) 191 found = backlink; 192 else if (VERTEX_IS_TYPE (NETWORK, v) && 193 ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, backlink) && 194 ROUTER_LSDESC_GET_NBR_ROUTERID (backlink) 195 == v->lsa->header->adv_router && 196 ROUTER_LSDESC_GET_NBR_IFID (backlink) 197 == ntohl (v->lsa->header->id)) 198 found = backlink; 199 else 200 { 201 if (! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, backlink) || 202 ! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc)) 203 continue; 204 if (ROUTER_LSDESC_GET_NBR_IFID (backlink) != 205 ROUTER_LSDESC_GET_IFID (lsdesc) || 206 ROUTER_LSDESC_GET_NBR_IFID (lsdesc) != 207 ROUTER_LSDESC_GET_IFID (backlink)) 208 continue; 209 if (ROUTER_LSDESC_GET_NBR_ROUTERID (backlink) != 210 v->lsa->header->adv_router || 211 ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc) != 212 lsa->header->adv_router) 213 continue; 214 found = backlink; 215 } 216 } 217 218 if (IS_OSPF6_DEBUG_SPF (PROCESS)) 219 zlog_debug (" Backlink %s", (found ? "OK" : "FAIL")); 220 221 return found; 222} 223 224static void 225ospf6_nexthop_calc (struct ospf6_vertex *w, struct ospf6_vertex *v, 226 caddr_t lsdesc) 227{ 228 int i, ifindex; 229 struct ospf6_interface *oi; 230 u_int16_t type; 231 u_int32_t adv_router; 232 struct ospf6_lsa *lsa; 233 struct ospf6_link_lsa *link_lsa; 234 char buf[64]; 235 236 assert (VERTEX_IS_TYPE (ROUTER, w)); 237 ifindex = (VERTEX_IS_TYPE (NETWORK, v) ? v->nexthop[0].ifindex : 238 ROUTER_LSDESC_GET_IFID (lsdesc)); 239 oi = ospf6_interface_lookup_by_ifindex (ifindex); 240 if (oi == NULL) 241 { 242 if (IS_OSPF6_DEBUG_SPF (PROCESS)) 243 zlog_debug ("Can't find interface in SPF: ifindex %d", ifindex); 244 return; 245 } 246 247 type = htons (OSPF6_LSTYPE_LINK); 248 adv_router = (VERTEX_IS_TYPE (NETWORK, v) ? 249 NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc) : 250 ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc)); 251 252 i = 0; 253 for (lsa = ospf6_lsdb_type_router_head (type, adv_router, oi->lsdb); lsa; 254 lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa)) 255 { 256 if (VERTEX_IS_TYPE (ROUTER, v) && 257 htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc)) != lsa->header->id) 258 continue; 259 260 link_lsa = (struct ospf6_link_lsa *) OSPF6_LSA_HEADER_END (lsa->header); 261 if (IS_OSPF6_DEBUG_SPF (PROCESS)) 262 { 263 inet_ntop (AF_INET6, &link_lsa->linklocal_addr, buf, sizeof (buf)); 264 zlog_debug (" nexthop %s from %s", buf, lsa->name); 265 } 266 267 if (i < OSPF6_MULTI_PATH_LIMIT) 268 { 269 memcpy (&w->nexthop[i].address, &link_lsa->linklocal_addr, 270 sizeof (struct in6_addr)); 271 w->nexthop[i].ifindex = ifindex; 272 i++; 273 } 274 } 275 276 if (i == 0 && IS_OSPF6_DEBUG_SPF (PROCESS)) 277 zlog_debug ("No nexthop for %s found", w->name); 278} 279 280static int 281ospf6_spf_install (struct ospf6_vertex *v, 282 struct ospf6_route_table *result_table) 283{ 284 struct ospf6_route *route; 285 int i, j; 286 struct ospf6_vertex *prev; 287 288 if (IS_OSPF6_DEBUG_SPF (PROCESS)) 289 zlog_debug ("SPF install %s hops %d cost %d", 290 v->name, v->hops, v->cost); 291 292 route = ospf6_route_lookup (&v->vertex_id, result_table); 293 if (route && route->path.cost < v->cost) 294 { 295 if (IS_OSPF6_DEBUG_SPF (PROCESS)) 296 zlog_debug (" already installed with lower cost (%d), ignore", 297 route->path.cost); 298 ospf6_vertex_delete (v); 299 return -1; 300 } 301 else if (route && route->path.cost == v->cost) 302 { 303 if (IS_OSPF6_DEBUG_SPF (PROCESS)) 304 zlog_debug (" another path found, merge"); 305 306 for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && 307 i < OSPF6_MULTI_PATH_LIMIT; i++) 308 { 309 for (j = 0; j < OSPF6_MULTI_PATH_LIMIT; j++) 310 { 311 if (ospf6_nexthop_is_set (&route->nexthop[j])) 312 { 313 if (ospf6_nexthop_is_same (&route->nexthop[j], 314 &v->nexthop[i])) 315 break; 316 else 317 continue; 318 } 319 ospf6_nexthop_copy (&route->nexthop[j], &v->nexthop[i]); 320 break; 321 } 322 } 323 324 prev = (struct ospf6_vertex *) route->route_option; 325 assert (prev->hops <= v->hops); 326 ospf6_vertex_delete (v); 327 328 return -1; 329 } 330 331 /* There should be no case where candidate being installed (variable 332 "v") is closer than the one in the SPF tree (variable "route"). 333 In the case something has gone wrong with the behavior of 334 Priority-Queue. */ 335 336 /* the case where the route exists already is handled and returned 337 up to here. */ 338 assert (route == NULL); 339 340 route = ospf6_route_create (); 341 memcpy (&route->prefix, &v->vertex_id, sizeof (struct prefix)); 342 route->type = OSPF6_DEST_TYPE_LINKSTATE; 343 route->path.type = OSPF6_PATH_TYPE_INTRA; 344 route->path.origin.type = v->lsa->header->type; 345 route->path.origin.id = v->lsa->header->id; 346 route->path.origin.adv_router = v->lsa->header->adv_router; 347 route->path.metric_type = 1; 348 route->path.cost = v->cost; 349 route->path.cost_e2 = v->hops; 350 route->path.router_bits = v->capability; 351 route->path.options[0] = v->options[0]; 352 route->path.options[1] = v->options[1]; 353 route->path.options[2] = v->options[2]; 354 355 for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && 356 i < OSPF6_MULTI_PATH_LIMIT; i++) 357 ospf6_nexthop_copy (&route->nexthop[i], &v->nexthop[i]); 358 359 if (v->parent) 360 listnode_add_sort (v->parent->child_list, v); 361 route->route_option = v; 362 363 ospf6_route_add (route, result_table); 364 return 0; 365} 366 367void 368ospf6_spf_table_finish (struct ospf6_route_table *result_table) 369{ 370 struct ospf6_route *route; 371 struct ospf6_vertex *v; 372 for (route = ospf6_route_head (result_table); route; 373 route = ospf6_route_next (route)) 374 { 375 v = (struct ospf6_vertex *) route->route_option; 376 ospf6_vertex_delete (v); 377 ospf6_route_remove (route, result_table); 378 } 379} 380 381static const char *ospf6_spf_reason_str[] = 382 { 383 "R+", 384 "R-", 385 "N+", 386 "N-", 387 "L+", 388 "L-", 389 "R*", 390 "N*", 391 }; 392 393void ospf6_spf_reason_string (unsigned int reason, char *buf, int size) 394{ 395 size_t bit; 396 int len = 0; 397 398 if (!buf) 399 return; 400 401 for (bit = 0; bit <= (sizeof(ospf6_spf_reason_str) / sizeof(char *)); bit++) 402 { 403 if ((reason & (1 << bit)) && (len < size)) 404 { 405 len += snprintf((buf + len), (size - len), "%s%s", 406 (len > 0) ? ", " : "", ospf6_spf_reason_str[bit]); 407 } 408 } 409} 410 411/* RFC2328 16.1. Calculating the shortest-path tree for an area */ 412/* RFC2740 3.8.1. Calculating the shortest path tree for an area */ 413void 414ospf6_spf_calculation (u_int32_t router_id, 415 struct ospf6_route_table *result_table, 416 struct ospf6_area *oa) 417{ 418 struct pqueue *candidate_list; 419 struct ospf6_vertex *root, *v, *w; 420 int i; 421 int size; 422 caddr_t lsdesc; 423 struct ospf6_lsa *lsa; 424 425 ospf6_spf_table_finish (result_table); 426 427 /* Install the calculating router itself as the root of the SPF tree */ 428 /* construct root vertex */ 429 lsa = ospf6_lsdb_lookup (htons (OSPF6_LSTYPE_ROUTER), htonl (0), 430 router_id, oa->lsdb); 431 if (lsa == NULL) 432 return; 433 434 /* initialize */ 435 candidate_list = pqueue_create (); 436 candidate_list->cmp = ospf6_vertex_cmp; 437 438 root = ospf6_vertex_create (lsa); 439 root->area = oa; 440 root->cost = 0; 441 root->hops = 0; 442 root->nexthop[0].ifindex = 0; /* loopbak I/F is better ... */ 443 inet_pton (AF_INET6, "::1", &root->nexthop[0].address); 444 445 /* Actually insert root to the candidate-list as the only candidate */ 446 pqueue_enqueue (root, candidate_list); 447 448 /* Iterate until candidate-list becomes empty */ 449 while (candidate_list->size) 450 { 451 /* get closest candidate from priority queue */ 452 v = pqueue_dequeue (candidate_list); 453 454 /* installing may result in merging or rejecting of the vertex */ 455 if (ospf6_spf_install (v, result_table) < 0) 456 continue; 457 458 /* Skip overloaded routers */ 459 if ((OSPF6_LSA_IS_TYPE (ROUTER, v->lsa) && 460 ospf6_router_is_stub_router (v->lsa))) 461 continue; 462 463 /* For each LS description in the just-added vertex V's LSA */ 464 size = (VERTEX_IS_TYPE (ROUTER, v) ? 465 sizeof (struct ospf6_router_lsdesc) : 466 sizeof (struct ospf6_network_lsdesc)); 467 for (lsdesc = OSPF6_LSA_HEADER_END (v->lsa->header) + 4; 468 lsdesc + size <= OSPF6_LSA_END (v->lsa->header); lsdesc += size) 469 { 470 lsa = ospf6_lsdesc_lsa (lsdesc, v); 471 if (lsa == NULL) 472 continue; 473 474 if (! ospf6_lsdesc_backlink (lsa, lsdesc, v)) 475 continue; 476 477 w = ospf6_vertex_create (lsa); 478 w->area = oa; 479 w->parent = v; 480 if (VERTEX_IS_TYPE (ROUTER, v)) 481 { 482 w->cost = v->cost + ROUTER_LSDESC_GET_METRIC (lsdesc); 483 w->hops = v->hops + (VERTEX_IS_TYPE (NETWORK, w) ? 0 : 1); 484 } 485 else /* NETWORK */ 486 { 487 w->cost = v->cost; 488 w->hops = v->hops + 1; 489 } 490 491 /* nexthop calculation */ 492 if (w->hops == 0) 493 w->nexthop[0].ifindex = ROUTER_LSDESC_GET_IFID (lsdesc); 494 else if (w->hops == 1 && v->hops == 0) 495 ospf6_nexthop_calc (w, v, lsdesc); 496 else 497 { 498 for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && 499 i < OSPF6_MULTI_PATH_LIMIT; i++) 500 ospf6_nexthop_copy (&w->nexthop[i], &v->nexthop[i]); 501 } 502 503 /* add new candidate to the candidate_list */ 504 if (IS_OSPF6_DEBUG_SPF (PROCESS)) 505 zlog_debug (" New candidate: %s hops %d cost %d", 506 w->name, w->hops, w->cost); 507 pqueue_enqueue (w, candidate_list); 508 } 509 } 510 511 pqueue_delete (candidate_list); 512 513 oa->spf_calculation++; 514} 515 516static void 517ospf6_spf_log_database (struct ospf6_area *oa) 518{ 519 char *p, *end, buffer[256]; 520 struct listnode *node; 521 struct ospf6_interface *oi; 522 523 p = buffer; 524 end = buffer + sizeof (buffer); 525 526 snprintf (p, end - p, "SPF on DB (#LSAs):"); 527 p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end); 528 snprintf (p, end - p, " Area %s: %d", oa->name, oa->lsdb->count); 529 p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end); 530 531 for (ALL_LIST_ELEMENTS_RO (oa->if_list, node, oi)) 532 { 533 snprintf (p, end - p, " I/F %s: %d", 534 oi->interface->name, oi->lsdb->count); 535 p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end); 536 } 537 538 zlog_debug ("%s", buffer); 539} 540 541static int 542ospf6_spf_calculation_thread (struct thread *t) 543{ 544 struct ospf6_area *oa; 545 struct ospf6 *ospf6; 546 struct timeval start, end, runtime; 547 struct listnode *node; 548 struct ospf6_route *route; 549 int areas_processed = 0; 550 char rbuf[32]; 551 552 ospf6 = (struct ospf6 *)THREAD_ARG (t); 553 ospf6->t_spf_calc = NULL; 554 555 /* execute SPF calculation */ 556 quagga_gettime (QUAGGA_CLK_MONOTONIC, &start); 557 558 for (ALL_LIST_ELEMENTS_RO(ospf6->area_list, node, oa)) 559 { 560 561 if (oa == ospf6->backbone) 562 continue; 563 564 if (IS_OSPF6_DEBUG_SPF (PROCESS)) 565 zlog_debug ("SPF calculation for Area %s", oa->name); 566 if (IS_OSPF6_DEBUG_SPF (DATABASE)) 567 ospf6_spf_log_database (oa); 568 569 ospf6_spf_calculation (ospf6->router_id, oa->spf_table, oa); 570 ospf6_intra_route_calculation (oa); 571 ospf6_intra_brouter_calculation (oa); 572 573 areas_processed++; 574 } 575 576 if (ospf6->backbone) 577 { 578 if (IS_OSPF6_DEBUG_SPF (PROCESS)) 579 zlog_debug ("SPF calculation for Backbone area %s", 580 ospf6->backbone->name); 581 if (IS_OSPF6_DEBUG_SPF (DATABASE)) 582 ospf6_spf_log_database(ospf6->backbone); 583 584 ospf6_spf_calculation(ospf6->router_id, ospf6->backbone->spf_table, 585 ospf6->backbone); 586 ospf6_intra_route_calculation(ospf6->backbone); 587 ospf6_intra_brouter_calculation(ospf6->backbone); 588 areas_processed++; 589 } 590 591 /* Redo summaries if required */ 592 for (route = ospf6_route_head (ospf6->route_table); route; 593 route = ospf6_route_next (route)) 594 ospf6_abr_originate_summary(route); 595 596 quagga_gettime (QUAGGA_CLK_MONOTONIC, &end); 597 timersub (&end, &start, &runtime); 598 599 ospf6->ts_spf_duration = runtime; 600 601 ospf6_spf_reason_string(ospf6->spf_reason, rbuf, sizeof(rbuf)); 602 603 if (IS_OSPF6_DEBUG_SPF (PROCESS) || IS_OSPF6_DEBUG_SPF (TIME)) 604 zlog_debug ("SPF runtime: %ld sec %ld usec", 605 runtime.tv_sec, runtime.tv_usec); 606 607 zlog_info("SPF processing: # Areas: %d, SPF runtime: %ld sec %ld usec, " 608 "Reason: %s\n", areas_processed, runtime.tv_sec, runtime.tv_usec, 609 rbuf); 610 ospf6->last_spf_reason = ospf6->spf_reason; 611 ospf6_reset_spf_reason(ospf6); 612 return 0; 613} 614 615/* Add schedule for SPF calculation. To avoid frequenst SPF calc, we 616 set timer for SPF calc. */ 617void 618ospf6_spf_schedule (struct ospf6 *ospf6, unsigned int reason) 619{ 620 unsigned long delay, elapsed, ht; 621 struct timeval now, result; 622 623 ospf6_set_spf_reason(ospf6, reason); 624 625 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME)) 626 { 627 char rbuf[32]; 628 ospf6_spf_reason_string(reason, rbuf, sizeof(rbuf)); 629 zlog_debug ("SPF: calculation timer scheduled (reason %s)", rbuf); 630 } 631 632 /* OSPF instance does not exist. */ 633 if (ospf6 == NULL) 634 return; 635 636 /* SPF calculation timer is already scheduled. */ 637 if (ospf6->t_spf_calc) 638 { 639 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME)) 640 zlog_debug ("SPF: calculation timer is already scheduled: %p", 641 ospf6->t_spf_calc); 642 return; 643 } 644 645 /* XXX Monotic timers: we only care about relative time here. */ 646 now = recent_relative_time (); 647 timersub (&now, &ospf6->ts_spf, &result); 648 649 elapsed = (result.tv_sec * 1000) + (result.tv_usec / 1000); 650 ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier; 651 652 if (ht > ospf6->spf_max_holdtime) 653 ht = ospf6->spf_max_holdtime; 654 655 /* Get SPF calculation delay time. */ 656 if (elapsed < ht) 657 { 658 /* Got an event within the hold time of last SPF. We need to 659 * increase the hold_multiplier, if it's not already at/past 660 * maximum value, and wasn't already increased.. 661 */ 662 if (ht < ospf6->spf_max_holdtime) 663 ospf6->spf_hold_multiplier++; 664 665 /* always honour the SPF initial delay */ 666 if ( (ht - elapsed) < ospf6->spf_delay) 667 delay = ospf6->spf_delay; 668 else 669 delay = ht - elapsed; 670 } 671 else 672 { 673 /* Event is past required hold-time of last SPF */ 674 delay = ospf6->spf_delay; 675 ospf6->spf_hold_multiplier = 1; 676 } 677 678 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME)) 679 zlog_debug ("SPF: calculation timer delay = %ld", delay); 680 681 zlog_info ("SPF: Scheduled in %ld msec", delay); 682 683 ospf6->t_spf_calc = 684 thread_add_timer_msec (master, ospf6_spf_calculation_thread, ospf6, delay); 685} 686 687void 688ospf6_spf_display_subtree (struct vty *vty, const char *prefix, int rest, 689 struct ospf6_vertex *v) 690{ 691 struct listnode *node, *nnode; 692 struct ospf6_vertex *c; 693 char *next_prefix; 694 int len; 695 int restnum; 696 697 /* "prefix" is the space prefix of the display line */ 698 vty_out (vty, "%s+-%s [%d]%s", prefix, v->name, v->cost, VNL); 699 700 len = strlen (prefix) + 4; 701 next_prefix = (char *) malloc (len); 702 if (next_prefix == NULL) 703 { 704 vty_out (vty, "malloc failed%s", VNL); 705 return; 706 } 707 snprintf (next_prefix, len, "%s%s", prefix, (rest ? "| " : " ")); 708 709 restnum = listcount (v->child_list); 710 for (ALL_LIST_ELEMENTS (v->child_list, node, nnode, c)) 711 { 712 restnum--; 713 ospf6_spf_display_subtree (vty, next_prefix, restnum, c); 714 } 715 716 free (next_prefix); 717} 718 719DEFUN (debug_ospf6_spf_process, 720 debug_ospf6_spf_process_cmd, 721 "debug ospf6 spf process", 722 DEBUG_STR 723 OSPF6_STR 724 "Debug SPF Calculation\n" 725 "Debug Detailed SPF Process\n" 726 ) 727{ 728 unsigned char level = 0; 729 level = OSPF6_DEBUG_SPF_PROCESS; 730 OSPF6_DEBUG_SPF_ON (level); 731 return CMD_SUCCESS; 732} 733 734DEFUN (debug_ospf6_spf_time, 735 debug_ospf6_spf_time_cmd, 736 "debug ospf6 spf time", 737 DEBUG_STR 738 OSPF6_STR 739 "Debug SPF Calculation\n" 740 "Measure time taken by SPF Calculation\n" 741 ) 742{ 743 unsigned char level = 0; 744 level = OSPF6_DEBUG_SPF_TIME; 745 OSPF6_DEBUG_SPF_ON (level); 746 return CMD_SUCCESS; 747} 748 749DEFUN (debug_ospf6_spf_database, 750 debug_ospf6_spf_database_cmd, 751 "debug ospf6 spf database", 752 DEBUG_STR 753 OSPF6_STR 754 "Debug SPF Calculation\n" 755 "Log number of LSAs at SPF Calculation time\n" 756 ) 757{ 758 unsigned char level = 0; 759 level = OSPF6_DEBUG_SPF_DATABASE; 760 OSPF6_DEBUG_SPF_ON (level); 761 return CMD_SUCCESS; 762} 763 764DEFUN (no_debug_ospf6_spf_process, 765 no_debug_ospf6_spf_process_cmd, 766 "no debug ospf6 spf process", 767 NO_STR 768 DEBUG_STR 769 OSPF6_STR 770 "Quit Debugging SPF Calculation\n" 771 "Quit Debugging Detailed SPF Process\n" 772 ) 773{ 774 unsigned char level = 0; 775 level = OSPF6_DEBUG_SPF_PROCESS; 776 OSPF6_DEBUG_SPF_OFF (level); 777 return CMD_SUCCESS; 778} 779 780DEFUN (no_debug_ospf6_spf_time, 781 no_debug_ospf6_spf_time_cmd, 782 "no debug ospf6 spf time", 783 NO_STR 784 DEBUG_STR 785 OSPF6_STR 786 "Quit Debugging SPF Calculation\n" 787 "Quit Measuring time taken by SPF Calculation\n" 788 ) 789{ 790 unsigned char level = 0; 791 level = OSPF6_DEBUG_SPF_TIME; 792 OSPF6_DEBUG_SPF_OFF (level); 793 return CMD_SUCCESS; 794} 795 796DEFUN (no_debug_ospf6_spf_database, 797 no_debug_ospf6_spf_database_cmd, 798 "no debug ospf6 spf database", 799 NO_STR 800 DEBUG_STR 801 OSPF6_STR 802 "Debug SPF Calculation\n" 803 "Quit Logging number of LSAs at SPF Calculation time\n" 804 ) 805{ 806 unsigned char level = 0; 807 level = OSPF6_DEBUG_SPF_DATABASE; 808 OSPF6_DEBUG_SPF_OFF (level); 809 return CMD_SUCCESS; 810} 811 812static int 813ospf6_timers_spf_set (struct vty *vty, unsigned int delay, 814 unsigned int hold, 815 unsigned int max) 816{ 817 struct ospf6 *ospf = vty->index; 818 819 ospf->spf_delay = delay; 820 ospf->spf_holdtime = hold; 821 ospf->spf_max_holdtime = max; 822 823 return CMD_SUCCESS; 824} 825 826DEFUN (ospf6_timers_throttle_spf, 827 ospf6_timers_throttle_spf_cmd, 828 "timers throttle spf <0-600000> <0-600000> <0-600000>", 829 "Adjust routing timers\n" 830 "Throttling adaptive timer\n" 831 "OSPF6 SPF timers\n" 832 "Delay (msec) from first change received till SPF calculation\n" 833 "Initial hold time (msec) between consecutive SPF calculations\n" 834 "Maximum hold time (msec)\n") 835{ 836 unsigned int delay, hold, max; 837 838 if (argc != 3) 839 { 840 vty_out (vty, "Insufficient arguments%s", VTY_NEWLINE); 841 return CMD_WARNING; 842 } 843 844 VTY_GET_INTEGER_RANGE ("SPF delay timer", delay, argv[0], 0, 600000); 845 VTY_GET_INTEGER_RANGE ("SPF hold timer", hold, argv[1], 0, 600000); 846 VTY_GET_INTEGER_RANGE ("SPF max-hold timer", max, argv[2], 0, 600000); 847 848 return ospf6_timers_spf_set (vty, delay, hold, max); 849} 850 851DEFUN (no_ospf6_timers_throttle_spf, 852 no_ospf6_timers_throttle_spf_cmd, 853 "no timers throttle spf", 854 NO_STR 855 "Adjust routing timers\n" 856 "Throttling adaptive timer\n" 857 "OSPF6 SPF timers\n") 858{ 859 return ospf6_timers_spf_set (vty, 860 OSPF_SPF_DELAY_DEFAULT, 861 OSPF_SPF_HOLDTIME_DEFAULT, 862 OSPF_SPF_MAX_HOLDTIME_DEFAULT); 863} 864 865int 866config_write_ospf6_debug_spf (struct vty *vty) 867{ 868 if (IS_OSPF6_DEBUG_SPF (PROCESS)) 869 vty_out (vty, "debug ospf6 spf process%s", VNL); 870 if (IS_OSPF6_DEBUG_SPF (TIME)) 871 vty_out (vty, "debug ospf6 spf time%s", VNL); 872 if (IS_OSPF6_DEBUG_SPF (DATABASE)) 873 vty_out (vty, "debug ospf6 spf database%s", VNL); 874 return 0; 875} 876 877void 878ospf6_spf_config_write (struct vty *vty) 879{ 880 881 if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT || 882 ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT || 883 ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT) 884 vty_out (vty, " timers throttle spf %d %d %d%s", 885 ospf6->spf_delay, ospf6->spf_holdtime, 886 ospf6->spf_max_holdtime, VTY_NEWLINE); 887 888} 889 890void 891install_element_ospf6_debug_spf (void) 892{ 893 install_element (ENABLE_NODE, &debug_ospf6_spf_process_cmd); 894 install_element (ENABLE_NODE, &debug_ospf6_spf_time_cmd); 895 install_element (ENABLE_NODE, &debug_ospf6_spf_database_cmd); 896 install_element (ENABLE_NODE, &no_debug_ospf6_spf_process_cmd); 897 install_element (ENABLE_NODE, &no_debug_ospf6_spf_time_cmd); 898 install_element (ENABLE_NODE, &no_debug_ospf6_spf_database_cmd); 899 install_element (CONFIG_NODE, &debug_ospf6_spf_process_cmd); 900 install_element (CONFIG_NODE, &debug_ospf6_spf_time_cmd); 901 install_element (CONFIG_NODE, &debug_ospf6_spf_database_cmd); 902 install_element (CONFIG_NODE, &no_debug_ospf6_spf_process_cmd); 903 install_element (CONFIG_NODE, &no_debug_ospf6_spf_time_cmd); 904 install_element (CONFIG_NODE, &no_debug_ospf6_spf_database_cmd); 905} 906 907void 908ospf6_spf_init (void) 909{ 910 install_element (OSPF6_NODE, &ospf6_timers_throttle_spf_cmd); 911 install_element (OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd); 912} 913