1/* OSPF SPF calculation. 2 Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada 3 4This file is part of GNU Zebra. 5 6GNU Zebra is free software; you can redistribute it and/or modify it 7under the terms of the GNU General Public License as published by the 8Free Software Foundation; either version 2, or (at your option) any 9later version. 10 11GNU Zebra is distributed in the hope that it will be useful, but 12WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GNU Zebra; see the file COPYING. If not, write to the Free 18Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 1902111-1307, USA. */ 20 21#include <zebra.h> 22 23#include "thread.h" 24#include "memory.h" 25#include "hash.h" 26#include "linklist.h" 27#include "prefix.h" 28#include "if.h" 29#include "table.h" 30#include "log.h" 31#include "sockunion.h" /* for inet_ntop () */ 32 33#include "ospfd/ospfd.h" 34#include "ospfd/ospf_interface.h" 35#include "ospfd/ospf_ism.h" 36#include "ospfd/ospf_asbr.h" 37#include "ospfd/ospf_lsa.h" 38#include "ospfd/ospf_lsdb.h" 39#include "ospfd/ospf_neighbor.h" 40#include "ospfd/ospf_nsm.h" 41#include "ospfd/ospf_spf.h" 42#include "ospfd/ospf_route.h" 43#include "ospfd/ospf_ia.h" 44#include "ospfd/ospf_ase.h" 45#include "ospfd/ospf_abr.h" 46#include "ospfd/ospf_dump.h" 47 48#define DEBUG 49 50struct vertex_nexthop * 51vertex_nexthop_new (struct vertex *parent) 52{ 53 struct vertex_nexthop *new; 54 55 new = XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop)); 56 new->parent = parent; 57 58 return new; 59} 60 61void 62vertex_nexthop_free (struct vertex_nexthop *nh) 63{ 64 XFREE (MTYPE_OSPF_NEXTHOP, nh); 65} 66 67struct vertex_nexthop * 68vertex_nexthop_dup (struct vertex_nexthop *nh) 69{ 70 struct vertex_nexthop *new; 71 72 new = vertex_nexthop_new (nh->parent); 73 74 new->oi = nh->oi; 75 new->router = nh->router; 76 77 return new; 78} 79 80 81struct vertex * 82ospf_vertex_new (struct ospf_lsa *lsa) 83{ 84 struct vertex *new; 85 86 new = XMALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex)); 87 memset (new, 0, sizeof (struct vertex)); 88 89 new->flags = 0; 90 new->type = lsa->data->type; 91 new->id = lsa->data->id; 92 new->lsa = lsa->data; 93 new->distance = 0; 94 new->child = list_new (); 95 new->nexthop = list_new (); 96 97 return new; 98} 99 100void 101ospf_vertex_free (struct vertex *v) 102{ 103 listnode node; 104 105 list_delete (v->child); 106 107 if (listcount (v->nexthop) > 0) 108 for (node = listhead (v->nexthop); node; nextnode (node)) 109 vertex_nexthop_free (node->data); 110 111 list_delete (v->nexthop); 112 113 XFREE (MTYPE_OSPF_VERTEX, v); 114} 115 116void 117ospf_vertex_add_parent (struct vertex *v) 118{ 119 struct vertex_nexthop *nh; 120 listnode node; 121 122 for (node = listhead (v->nexthop); node; nextnode (node)) 123 { 124 nh = (struct vertex_nexthop *) getdata (node); 125 126 /* No need to add two links from the same parent. */ 127 if (listnode_lookup (nh->parent->child, v) == NULL) 128 listnode_add (nh->parent->child, v); 129 } 130} 131 132void 133ospf_spf_init (struct ospf_area *area) 134{ 135 struct vertex *v; 136 137 /* Create root node. */ 138 v = ospf_vertex_new (area->router_lsa_self); 139 140 area->spf = v; 141 142 /* Reset ABR and ASBR router counts. */ 143 area->abr_count = 0; 144 area->asbr_count = 0; 145} 146 147int 148ospf_spf_has_vertex (struct route_table *rv, struct route_table *nv, 149 struct lsa_header *lsa) 150{ 151 struct prefix p; 152 struct route_node *rn; 153 154 p.family = AF_INET; 155 p.prefixlen = IPV4_MAX_BITLEN; 156 p.u.prefix4 = lsa->id; 157 158 if (lsa->type == OSPF_ROUTER_LSA) 159 rn = route_node_get (rv, &p); 160 else 161 rn = route_node_get (nv, &p); 162 163 if (rn->info != NULL) 164 { 165 route_unlock_node (rn); 166 return 1; 167 } 168 return 0; 169} 170 171listnode 172ospf_vertex_lookup (list vlist, struct in_addr id, int type) 173{ 174 listnode node; 175 struct vertex *v; 176 177 for (node = listhead (vlist); node; nextnode (node)) 178 { 179 v = (struct vertex *) getdata (node); 180 if (IPV4_ADDR_SAME (&id, &v->id) && type == v->type) 181 return node; 182 } 183 184 return NULL; 185} 186 187int 188ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v) 189{ 190 int i; 191 int length; 192 struct router_lsa *rl; 193 struct network_lsa *nl; 194 195 /* In case of W is Network LSA. */ 196 if (w->type == OSPF_NETWORK_LSA) 197 { 198 if (v->type == OSPF_NETWORK_LSA) 199 return 0; 200 201 nl = (struct network_lsa *) w; 202 length = (ntohs (w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4; 203 204 for (i = 0; i < length; i++) 205 if (IPV4_ADDR_SAME (&nl->routers[i], &v->id)) 206 return 1; 207 return 0; 208 } 209 210 /* In case of W is Router LSA. */ 211 if (w->type == OSPF_ROUTER_LSA) 212 { 213 rl = (struct router_lsa *) w; 214 215 length = ntohs (w->length); 216 217 for (i = 0; 218 i < ntohs (rl->links) && length >= sizeof (struct router_lsa); 219 i++, length -= 12) 220 { 221 switch (rl->link[i].type) 222 { 223 case LSA_LINK_TYPE_POINTOPOINT: 224 case LSA_LINK_TYPE_VIRTUALLINK: 225 /* Router LSA ID. */ 226 if (v->type == OSPF_ROUTER_LSA && 227 IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id)) 228 { 229 return 1; 230 } 231 break; 232 case LSA_LINK_TYPE_TRANSIT: 233 /* Network LSA ID. */ 234 if (v->type == OSPF_NETWORK_LSA && 235 IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id)) 236 { 237 return 1; 238 } 239 break; 240 case LSA_LINK_TYPE_STUB: 241 /* Not take into count? */ 242 continue; 243 default: 244 break; 245 } 246 } 247 } 248 return 0; 249} 250 251/* Add the nexthop to the list, only if it is unique. 252 * If it's not unique, free the nexthop entry. 253 */ 254void 255ospf_nexthop_add_unique (struct vertex_nexthop *new, list nexthop) 256{ 257 struct vertex_nexthop *nh; 258 listnode node; 259 int match; 260 261 match = 0; 262 for (node = listhead (nexthop); node; nextnode (node)) 263 { 264 nh = node->data; 265 266 /* Compare the two entries. */ 267 /* XXX 268 * Comparing the parent preserves the shortest path tree 269 * structure even when the nexthops are identical. 270 */ 271 if (nh->oi == new->oi && 272 IPV4_ADDR_SAME (&nh->router, &new->router) && 273 nh->parent == new->parent) 274 { 275 match = 1; 276 break; 277 } 278 } 279 280 if (!match) 281 listnode_add (nexthop, new); 282 else 283 vertex_nexthop_free (new); 284} 285 286/* Merge entries in list b into list a. */ 287void 288ospf_nexthop_merge (list a, list b) 289{ 290 struct listnode *n; 291 292 for (n = listhead (b); n; nextnode (n)) 293 { 294 ospf_nexthop_add_unique (n->data, a); 295 } 296} 297 298#define ROUTER_LSA_MIN_SIZE 12 299#define ROUTER_LSA_TOS_SIZE 4 300 301struct router_lsa_link * 302ospf_get_next_link (struct vertex *v, struct vertex *w, 303 struct router_lsa_link *prev_link) 304{ 305 u_char *p; 306 u_char *lim; 307 struct router_lsa_link *l; 308 309 if (prev_link == NULL) 310 p = ((u_char *) v->lsa) + 24; 311 else 312 { 313 p = (u_char *)prev_link; 314 p += (ROUTER_LSA_MIN_SIZE + 315 (prev_link->m[0].tos_count * ROUTER_LSA_TOS_SIZE)); 316 } 317 318 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length); 319 320 while (p < lim) 321 { 322 l = (struct router_lsa_link *) p; 323 324 p += (ROUTER_LSA_MIN_SIZE + 325 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE)); 326 327 if (l->m[0].type == LSA_LINK_TYPE_STUB) 328 continue; 329 330 /* Defer NH calculation via VLs until summaries from 331 transit areas area confidered */ 332 333 if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK) 334 continue; 335 336 if (IPV4_ADDR_SAME (&l->link_id, &w->id)) 337 return l; 338 } 339 340 return NULL; 341} 342 343/* Calculate nexthop from root to vertex W. */ 344void 345ospf_nexthop_calculation (struct ospf_area *area, 346 struct vertex *v, struct vertex *w) 347{ 348 listnode node; 349 struct vertex_nexthop *nh, *x; 350 struct ospf_interface *oi = NULL; 351 struct router_lsa_link *l = NULL; 352 353 354 if (IS_DEBUG_OSPF_EVENT) 355 zlog_info ("ospf_nexthop_calculation(): Start"); 356 357 /* W's parent is root. */ 358 if (v == area->spf) 359 { 360 if (w->type == OSPF_VERTEX_ROUTER) 361 { 362 while ((l = ospf_get_next_link (v, w, l))) 363 { 364 struct router_lsa_link *l2 = NULL; 365 366 if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) 367 { 368 while ((l2 = ospf_get_next_link (w, v, l2))) 369 { 370 oi = ospf_if_is_configured (&(l2->link_data)); 371 372 if (oi == NULL) 373 continue; 374 375 if (! IPV4_ADDR_SAME (&oi->address->u.prefix4, 376 &l->link_data)) 377 continue; 378 379 break; 380 } 381 382 if (oi && l2) 383 { 384 nh = vertex_nexthop_new (v); 385 nh->oi = oi; 386 nh->router = l2->link_data; 387 listnode_add (w->nexthop, nh); 388 } 389 } 390 } 391 } 392 else 393 { 394 while ((l = ospf_get_next_link (v, w, l))) 395 { 396 oi = ospf_if_is_configured (&(l->link_data)); 397 if (oi) 398 { 399 nh = vertex_nexthop_new (v); 400 nh->oi = oi; 401 nh->router.s_addr = 0; 402 listnode_add (w->nexthop, nh); 403 } 404 } 405 } 406 return; 407 } 408 /* In case of W's parent is network connected to root. */ 409 else if (v->type == OSPF_VERTEX_NETWORK) 410 { 411 for (node = listhead (v->nexthop); node; nextnode (node)) 412 { 413 x = (struct vertex_nexthop *) getdata (node); 414 if (x->parent == area->spf) 415 { 416 while ((l = ospf_get_next_link (w, v, l))) 417 { 418 nh = vertex_nexthop_new (v); 419 nh->oi = x->oi; 420 nh->router = l->link_data; 421 listnode_add (w->nexthop, nh); 422 } 423 return; 424 } 425 } 426 } 427 428 /* Inherit V's nexthop. */ 429 for (node = listhead (v->nexthop); node; nextnode (node)) 430 { 431 nh = vertex_nexthop_dup (node->data); 432 nh->parent = v; 433 ospf_nexthop_add_unique (nh, w->nexthop); 434 } 435} 436 437void 438ospf_install_candidate (list candidate, struct vertex *w) 439{ 440 listnode node; 441 struct vertex *cw; 442 443 if (list_isempty (candidate)) 444 { 445 listnode_add (candidate, w); 446 return; 447 } 448 449 /* Install vertex with sorting by distance. */ 450 for (node = listhead (candidate); node; nextnode (node)) 451 { 452 cw = (struct vertex *) getdata (node); 453 if (cw->distance > w->distance) 454 { 455 list_add_node_prev (candidate, node, w); 456 break; 457 } 458 else if (node->next == NULL) 459 { 460 list_add_node_next (candidate, node, w); 461 break; 462 } 463 } 464} 465 466/* RFC2328 Section 16.1 (2). */ 467void 468ospf_spf_next (struct vertex *v, struct ospf_area *area, 469 list candidate, struct route_table *rv, 470 struct route_table *nv) 471{ 472 struct ospf_lsa *w_lsa = NULL; 473 struct vertex *w, *cw; 474 u_char *p; 475 u_char *lim; 476 struct router_lsa_link *l = NULL; 477 struct in_addr *r; 478 listnode node; 479 int type = 0; 480 481 /* If this is a router-LSA, and bit V of the router-LSA (see Section 482 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */ 483 if (v->type == OSPF_VERTEX_ROUTER) 484 { 485 if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa)) 486 area->transit = OSPF_TRANSIT_TRUE; 487 } 488 489 p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4; 490 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length); 491 492 while (p < lim) 493 { 494 /* In case of V is Router-LSA. */ 495 if (v->lsa->type == OSPF_ROUTER_LSA) 496 { 497 l = (struct router_lsa_link *) p; 498 499 p += (ROUTER_LSA_MIN_SIZE + 500 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE)); 501 502 /* (a) If this is a link to a stub network, examine the next 503 link in V's LSA. Links to stub networks will be 504 considered in the second stage of the shortest path 505 calculation. */ 506 if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB) 507 continue; 508 509 /* (b) Otherwise, W is a transit vertex (router or transit 510 network). Look up the vertex W's LSA (router-LSA or 511 network-LSA) in Area A's link state database. */ 512 switch (type) 513 { 514 case LSA_LINK_TYPE_POINTOPOINT: 515 case LSA_LINK_TYPE_VIRTUALLINK: 516 if (type == LSA_LINK_TYPE_VIRTUALLINK) 517 { 518 if (IS_DEBUG_OSPF_EVENT) 519 zlog_info ("looking up LSA through VL: %s", 520 inet_ntoa (l->link_id)); 521 } 522 523 w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id, 524 l->link_id); 525 if (w_lsa) 526 { 527 if (IS_DEBUG_OSPF_EVENT) 528 zlog_info("found the LSA"); 529 } 530 break; 531 case LSA_LINK_TYPE_TRANSIT: 532 if (IS_DEBUG_OSPF_EVENT) 533 534 zlog_info ("Looking up Network LSA, ID: %s", 535 inet_ntoa(l->link_id)); 536 w_lsa = ospf_lsa_lookup_by_id (area, OSPF_NETWORK_LSA, 537 l->link_id); 538 if (w_lsa) 539 if (IS_DEBUG_OSPF_EVENT) 540 zlog_info("found the LSA"); 541 break; 542 default: 543 zlog_warn ("Invalid LSA link type %d", type); 544 continue; 545 } 546 } 547 else 548 { 549 /* In case of V is Network-LSA. */ 550 r = (struct in_addr *) p ; 551 p += sizeof (struct in_addr); 552 553 /* Lookup the vertex W's LSA. */ 554 w_lsa = ospf_lsa_lookup_by_id (area, OSPF_ROUTER_LSA, *r); 555 } 556 557 /* (b cont.) If the LSA does not exist, or its LS age is equal 558 to MaxAge, or it does not have a link back to vertex V, 559 examine the next link in V's LSA.[23] */ 560 if (w_lsa == NULL) 561 continue; 562 563 if (IS_LSA_MAXAGE (w_lsa)) 564 continue; 565 566 if (! ospf_lsa_has_link (w_lsa->data, v->lsa)) 567 { 568 if (IS_DEBUG_OSPF_EVENT) 569 zlog_info ("The LSA doesn't have a link back"); 570 continue; 571 } 572 573 /* (c) If vertex W is already on the shortest-path tree, examine 574 the next link in the LSA. */ 575 if (ospf_spf_has_vertex (rv, nv, w_lsa->data)) 576 { 577 if (IS_DEBUG_OSPF_EVENT) 578 zlog_info ("The LSA is already in SPF"); 579 continue; 580 } 581 582 /* (d) Calculate the link state cost D of the resulting path 583 from the root to vertex W. D is equal to the sum of the link 584 state cost of the (already calculated) shortest path to 585 vertex V and the advertised cost of the link between vertices 586 V and W. If D is: */ 587 588 /* prepare vertex W. */ 589 w = ospf_vertex_new (w_lsa); 590 591 /* calculate link cost D. */ 592 if (v->lsa->type == OSPF_ROUTER_LSA) 593 w->distance = v->distance + ntohs (l->m[0].metric); 594 else 595 w->distance = v->distance; 596 597 /* Is there already vertex W in candidate list? */ 598 node = ospf_vertex_lookup (candidate, w->id, w->type); 599 if (node == NULL) 600 { 601 /* Calculate nexthop to W. */ 602 ospf_nexthop_calculation (area, v, w); 603 604 ospf_install_candidate (candidate, w); 605 } 606 else 607 { 608 cw = (struct vertex *) getdata (node); 609 610 /* if D is greater than. */ 611 if (cw->distance < w->distance) 612 { 613 ospf_vertex_free (w); 614 continue; 615 } 616 /* equal to. */ 617 else if (cw->distance == w->distance) 618 { 619 /* Calculate nexthop to W. */ 620 ospf_nexthop_calculation (area, v, w); 621 ospf_nexthop_merge (cw->nexthop, w->nexthop); 622 list_delete_all_node (w->nexthop); 623 ospf_vertex_free (w); 624 } 625 /* less than. */ 626 else 627 { 628 /* Calculate nexthop. */ 629 ospf_nexthop_calculation (area, v, w); 630 631 /* Remove old vertex from candidate list. */ 632 ospf_vertex_free (cw); 633 listnode_delete (candidate, cw); 634 635 /* Install new to candidate. */ 636 ospf_install_candidate (candidate, w); 637 } 638 } 639 } 640} 641 642/* Add vertex V to SPF tree. */ 643void 644ospf_spf_register (struct vertex *v, struct route_table *rv, 645 struct route_table *nv) 646{ 647 struct prefix p; 648 struct route_node *rn; 649 650 p.family = AF_INET; 651 p.prefixlen = IPV4_MAX_BITLEN; 652 p.u.prefix4 = v->id; 653 654 if (v->type == OSPF_VERTEX_ROUTER) 655 rn = route_node_get (rv, &p); 656 else 657 rn = route_node_get (nv, &p); 658 659 rn->info = v; 660} 661 662void 663ospf_spf_route_free (struct route_table *table) 664{ 665 struct route_node *rn; 666 struct vertex *v; 667 668 for (rn = route_top (table); rn; rn = route_next (rn)) 669 { 670 if ((v = rn->info)) 671 { 672 ospf_vertex_free (v); 673 rn->info = NULL; 674 } 675 676 route_unlock_node (rn); 677 } 678 679 route_table_finish (table); 680} 681 682void 683ospf_spf_dump (struct vertex *v, int i) 684{ 685 listnode cnode; 686 listnode nnode; 687 struct vertex_nexthop *nexthop; 688 689 if (v->type == OSPF_VERTEX_ROUTER) 690 { 691 if (IS_DEBUG_OSPF_EVENT) 692 zlog_info ("SPF Result: %d [R] %s", i, inet_ntoa (v->lsa->id)); 693 } 694 else 695 { 696 struct network_lsa *lsa = (struct network_lsa *) v->lsa; 697 if (IS_DEBUG_OSPF_EVENT) 698 zlog_info ("SPF Result: %d [N] %s/%d", i, inet_ntoa (v->lsa->id), 699 ip_masklen (lsa->mask)); 700 701 for (nnode = listhead (v->nexthop); nnode; nextnode (nnode)) 702 { 703 nexthop = getdata (nnode); 704 if (IS_DEBUG_OSPF_EVENT) 705 zlog_info (" nexthop %s", inet_ntoa (nexthop->router)); 706 } 707 } 708 709 i++; 710 711 for (cnode = listhead (v->child); cnode; nextnode (cnode)) 712 { 713 v = getdata (cnode); 714 ospf_spf_dump (v, i); 715 } 716} 717 718/* Second stage of SPF calculation. */ 719void 720ospf_spf_process_stubs (struct ospf_area *area, struct vertex * v, 721 struct route_table *rt) 722{ 723 listnode cnode; 724 struct vertex *child; 725 726 if (IS_DEBUG_OSPF_EVENT) 727 zlog_info ("ospf_process_stub():processing stubs for area %s", 728 inet_ntoa (area->area_id)); 729 if (v->type == OSPF_VERTEX_ROUTER) 730 { 731 u_char *p; 732 u_char *lim; 733 struct router_lsa_link *l; 734 struct router_lsa *rlsa; 735 736 if (IS_DEBUG_OSPF_EVENT) 737 zlog_info ("ospf_process_stub():processing router LSA, id: %s", 738 inet_ntoa (v->lsa->id)); 739 rlsa = (struct router_lsa *) v->lsa; 740 741 742 if (IS_DEBUG_OSPF_EVENT) 743 zlog_info ("ospf_process_stub(): we have %d links to process", 744 ntohs (rlsa->links)); 745 p = ((u_char *) v->lsa) + 24; 746 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length); 747 748 while (p < lim) 749 { 750 l = (struct router_lsa_link *) p; 751 752 p += (ROUTER_LSA_MIN_SIZE + 753 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE)); 754 755 if (l->m[0].type == LSA_LINK_TYPE_STUB) 756 ospf_intra_add_stub (rt, l, v, area); 757 } 758 } 759 760 if (IS_DEBUG_OSPF_EVENT) 761 zlog_info ("children of V:"); 762 for (cnode = listhead (v->child); cnode; nextnode (cnode)) 763 { 764 child = getdata (cnode); 765 if (IS_DEBUG_OSPF_EVENT) 766 zlog_info (" child : %s", inet_ntoa (child->id)); 767 } 768 769 for (cnode = listhead (v->child); cnode; nextnode (cnode)) 770 { 771 child = getdata (cnode); 772 773 if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED)) 774 continue; 775 776 ospf_spf_process_stubs (area, child, rt); 777 778 SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED); 779 } 780} 781 782void 783ospf_rtrs_free (struct route_table *rtrs) 784{ 785 struct route_node *rn; 786 list or_list; 787 listnode node; 788 789 if (IS_DEBUG_OSPF_EVENT) 790 zlog_info ("Route: Router Routing Table free"); 791 792 for (rn = route_top (rtrs); rn; rn = route_next (rn)) 793 if ((or_list = rn->info) != NULL) 794 { 795 for (node = listhead (or_list); node; nextnode (node)) 796 ospf_route_free (node->data); 797 798 list_delete (or_list); 799 800 /* Unlock the node. */ 801 rn->info = NULL; 802 route_unlock_node (rn); 803 } 804 route_table_finish (rtrs); 805} 806 807void 808ospf_rtrs_print (struct route_table *rtrs) 809{ 810 struct route_node *rn; 811 list or_list; 812 listnode ln; 813 listnode pnode; 814 struct ospf_route *or; 815 struct ospf_path *path; 816 char buf1[BUFSIZ]; 817 char buf2[BUFSIZ]; 818 819 if (IS_DEBUG_OSPF_EVENT) 820 zlog_info ("ospf_rtrs_print() start"); 821 822 for (rn = route_top (rtrs); rn; rn = route_next (rn)) 823 if ((or_list = rn->info) != NULL) 824 for (ln = listhead (or_list); ln; nextnode (ln)) 825 { 826 or = getdata (ln); 827 828 switch (or->path_type) 829 { 830 case OSPF_PATH_INTRA_AREA: 831 if (IS_DEBUG_OSPF_EVENT) 832 zlog_info ("%s [%d] area: %s", 833 inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), or->cost, 834 inet_ntop (AF_INET, &or->u.std.area_id, 835 buf2, BUFSIZ)); 836 break; 837 case OSPF_PATH_INTER_AREA: 838 if (IS_DEBUG_OSPF_EVENT) 839 zlog_info ("%s IA [%d] area: %s", 840 inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), or->cost, 841 inet_ntop (AF_INET, &or->u.std.area_id, 842 buf2, BUFSIZ)); 843 break; 844 default: 845 break; 846 } 847 848 for (pnode = listhead (or->path); pnode; nextnode (pnode)) 849 { 850 path = getdata (pnode); 851 if (path->nexthop.s_addr == 0) 852 { 853 if (IS_DEBUG_OSPF_EVENT) 854 zlog_info (" directly attached to %s\r\n", 855 IF_NAME (path->oi)); 856 } 857 else 858 { 859 if (IS_DEBUG_OSPF_EVENT) 860 zlog_info (" via %s, %s\r\n", 861 inet_ntoa (path->nexthop), IF_NAME (path->oi)); 862 } 863 } 864 } 865 866 zlog_info ("ospf_rtrs_print() end"); 867} 868 869/* Calculating the shortest-path tree for an area. */ 870void 871ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, 872 struct route_table *new_rtrs) 873{ 874 list candidate; 875 listnode node; 876 struct vertex *v; 877 struct route_table *rv; 878 struct route_table *nv; 879 880 if (IS_DEBUG_OSPF_EVENT) 881 { 882 zlog_info ("ospf_spf_calculate: Start"); 883 zlog_info ("ospf_spf_calculate: running Dijkstra for area %s", 884 inet_ntoa (area->area_id)); 885 } 886 887 /* Check router-lsa-self. If self-router-lsa is not yet allocated, 888 return this area's calculation. */ 889 if (! area->router_lsa_self) 890 { 891 if (IS_DEBUG_OSPF_EVENT) 892 zlog_info ("ospf_spf_calculate: " 893 "Skip area %s's calculation due to empty router_lsa_self", 894 inet_ntoa (area->area_id)); 895 return; 896 } 897 898 /* RFC2328 16.1. (1). */ 899 /* Initialize the algorithm's data structures. */ 900 rv = route_table_init (); 901 nv = route_table_init (); 902 903 /* Clear the list of candidate vertices. */ 904 candidate = list_new (); 905 906 /* Initialize the shortest-path tree to only the root (which is the 907 router doing the calculation). */ 908 ospf_spf_init (area); 909 v = area->spf; 910 ospf_spf_register (v, rv, nv); 911 912 /* Set Area A's TransitCapability to FALSE. */ 913 area->transit = OSPF_TRANSIT_FALSE; 914 area->shortcut_capability = 1; 915 916 for (;;) 917 { 918 /* RFC2328 16.1. (2). */ 919 ospf_spf_next (v, area, candidate, rv, nv); 920 921 /* RFC2328 16.1. (3). */ 922 /* If at this step the candidate list is empty, the shortest- 923 path tree (of transit vertices) has been completely built and 924 this stage of the procedure terminates. */ 925 if (listcount (candidate) == 0) 926 break; 927 928 /* Otherwise, choose the vertex belonging to the candidate list 929 that is closest to the root, and add it to the shortest-path 930 tree (removing it from the candidate list in the 931 process). */ 932 node = listhead (candidate); 933 v = getdata (node); 934 ospf_vertex_add_parent (v); 935 936 /* Reveve from the candidate list. */ 937 listnode_delete (candidate, v); 938 939 /* Add to SPF tree. */ 940 ospf_spf_register (v, rv, nv); 941 942 /* Note that when there is a choice of vertices closest to the 943 root, network vertices must be chosen before router vertices 944 in order to necessarily find all equal-cost paths. */ 945 /* We don't do this at this moment, we should add the treatment 946 above codes. -- kunihiro. */ 947 948 /* RFC2328 16.1. (4). */ 949 if (v->type == OSPF_VERTEX_ROUTER) 950 ospf_intra_add_router (new_rtrs, v, area); 951 else 952 ospf_intra_add_transit (new_table, v, area); 953 954 /* RFC2328 16.1. (5). */ 955 /* Iterate the algorithm by returning to Step 2. */ 956 } 957 958 if (IS_DEBUG_OSPF_EVENT) 959 { 960 ospf_spf_dump (area->spf, 0); 961 ospf_route_table_dump (new_table); 962 } 963 964 /* Second stage of SPF calculation procedure's */ 965 ospf_spf_process_stubs (area, area->spf, new_table); 966 967 /* Free all vertices which allocated for SPF calculation */ 968 ospf_spf_route_free (rv); 969 ospf_spf_route_free (nv); 970 971 /* Free candidate list */ 972 list_free (candidate); 973 974 /* Increment SPF Calculation Counter. */ 975 area->spf_calculation++; 976 977 ospf_top->ts_spf = time (NULL); 978 979 if (IS_DEBUG_OSPF_EVENT) 980 zlog_info ("ospf_spf_calculate: Stop"); 981} 982 983/* Timer for SPF calculation. */ 984int 985ospf_spf_calculate_timer (struct thread *t) 986{ 987 struct route_table *new_table, *new_rtrs; 988 struct ospf *ospf; 989 /* struct ospf_area *area; */ 990 listnode node; 991 992 if (IS_DEBUG_OSPF_EVENT) 993 zlog_info ("SPF: Timer (SPF calculation expire)"); 994 995 ospf = THREAD_ARG (t); 996 ospf->t_spf_calc = NULL; 997 998 /* Allocate new table tree. */ 999 new_table = route_table_init (); 1000 new_rtrs = route_table_init (); 1001 1002 ospf_vl_unapprove (); 1003 1004 /* Calculate SPF for each area. */ 1005 for (node = listhead (ospf->areas); node; node = nextnode (node)) 1006 ospf_spf_calculate (node->data, new_table, new_rtrs); 1007 1008 ospf_vl_shut_unapproved (); 1009 1010 ospf_ia_routing (new_table, new_rtrs); 1011 1012 ospf_prune_unreachable_networks (new_table); 1013 ospf_prune_unreachable_routers (new_rtrs); 1014 1015 /* AS-external-LSA calculation should not be performed here. */ 1016 1017 /* If new Router Route is installed, 1018 then schedule re-calculate External routes. */ 1019 if (1) 1020 ospf_ase_calculate_schedule (); 1021 1022 ospf_ase_calculate_timer_add (); 1023 1024 /* Update routing table. */ 1025 ospf_route_install (new_table); 1026 1027 /* Update ABR/ASBR routing table */ 1028 if (ospf_top->old_rtrs) 1029 { 1030 /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */ 1031 /* ospf_route_delete (ospf_top->old_rtrs); */ 1032 ospf_rtrs_free (ospf_top->old_rtrs); 1033 } 1034 1035 ospf_top->old_rtrs = ospf_top->new_rtrs; 1036 ospf_top->new_rtrs = new_rtrs; 1037 1038 if (OSPF_IS_ABR) 1039 ospf_abr_task (new_table, new_rtrs); 1040 1041 if (IS_DEBUG_OSPF_EVENT) 1042 zlog_info ("SPF: calculation complete"); 1043 1044 return 0; 1045} 1046 1047/* Add schedule for SPF calculation. To avoid frequenst SPF calc, we 1048 set timer for SPF calc. */ 1049void 1050ospf_spf_calculate_schedule () 1051{ 1052 time_t ht, delay; 1053 1054 if (IS_DEBUG_OSPF_EVENT) 1055 zlog_info ("SPF: calculation timer scheduled"); 1056 1057 /* OSPF instance does not exist. */ 1058 if (!ospf_top) 1059 return; 1060 1061 /* SPF calculation timer is already scheduled. */ 1062 if (ospf_top->t_spf_calc) 1063 { 1064 if (IS_DEBUG_OSPF_EVENT) 1065 zlog_info ("SPF: calculation timer is already scheduled: %p", 1066 ospf_top->t_spf_calc); 1067 return; 1068 } 1069 1070 ht = time (NULL) - ospf_top->ts_spf; 1071 1072 /* Get SPF calculation delay time. */ 1073 if (ht < ospf_top->spf_holdtime) 1074 { 1075 if (ospf_top->spf_holdtime - ht < ospf_top->spf_delay) 1076 delay = ospf_top->spf_delay; 1077 else 1078 delay = ospf_top->spf_holdtime - ht; 1079 } 1080 else 1081 delay = ospf_top->spf_delay; 1082 1083 if (IS_DEBUG_OSPF_EVENT) 1084 zlog_info ("SPF: calculation timer delay = %ld", delay); 1085 ospf_top->t_spf_calc = 1086 thread_add_timer (master, ospf_spf_calculate_timer, ospf_top, delay); 1087} 1088 1089