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#include <zebra.h> 23 24#include "log.h" 25#include "thread.h" 26#include "linklist.h" 27#include "vty.h" 28#include "command.h" 29 30#include "ospf6d.h" 31#include "ospf6_proto.h" 32#include "ospf6_lsa.h" 33#include "ospf6_lsdb.h" 34#include "ospf6_message.h" 35#include "ospf6_route.h" 36#include "ospf6_spf.h" 37 38#include "ospf6_top.h" 39#include "ospf6_area.h" 40#include "ospf6_interface.h" 41#include "ospf6_neighbor.h" 42 43#include "ospf6_flood.h" 44 45unsigned char conf_debug_ospf6_flooding; 46 47struct ospf6_lsdb * 48ospf6_get_scoped_lsdb (struct ospf6_lsa *lsa) 49{ 50 struct ospf6_lsdb *lsdb = NULL; 51 switch (OSPF6_LSA_SCOPE (lsa->header->type)) 52 { 53 case OSPF6_SCOPE_LINKLOCAL: 54 lsdb = OSPF6_INTERFACE (lsa->lsdb->data)->lsdb; 55 break; 56 case OSPF6_SCOPE_AREA: 57 lsdb = OSPF6_AREA (lsa->lsdb->data)->lsdb; 58 break; 59 case OSPF6_SCOPE_AS: 60 lsdb = OSPF6_PROCESS (lsa->lsdb->data)->lsdb; 61 break; 62 default: 63 assert (0); 64 break; 65 } 66 return lsdb; 67} 68 69struct ospf6_lsdb * 70ospf6_get_scoped_lsdb_self (struct ospf6_lsa *lsa) 71{ 72 struct ospf6_lsdb *lsdb_self = NULL; 73 switch (OSPF6_LSA_SCOPE (lsa->header->type)) 74 { 75 case OSPF6_SCOPE_LINKLOCAL: 76 lsdb_self = OSPF6_INTERFACE (lsa->lsdb->data)->lsdb_self; 77 break; 78 case OSPF6_SCOPE_AREA: 79 lsdb_self = OSPF6_AREA (lsa->lsdb->data)->lsdb_self; 80 break; 81 case OSPF6_SCOPE_AS: 82 lsdb_self = OSPF6_PROCESS (lsa->lsdb->data)->lsdb_self; 83 break; 84 default: 85 assert (0); 86 break; 87 } 88 return lsdb_self; 89} 90 91void 92ospf6_lsa_originate (struct ospf6_lsa *lsa) 93{ 94 struct ospf6_lsa *old; 95 struct ospf6_lsdb *lsdb_self; 96 97 /* find previous LSA */ 98 old = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id, 99 lsa->header->adv_router, lsa->lsdb); 100 101 /* if the new LSA does not differ from previous, 102 suppress this update of the LSA */ 103 if (old && ! OSPF6_LSA_IS_DIFFER (lsa, old)) 104 { 105 if (IS_OSPF6_DEBUG_ORIGINATE_TYPE (lsa->header->type)) 106 zlog_debug ("Suppress updating LSA: %s", lsa->name); 107 ospf6_lsa_delete (lsa); 108 return; 109 } 110 111 /* store it in the LSDB for self-originated LSAs */ 112 lsdb_self = ospf6_get_scoped_lsdb_self (lsa); 113 ospf6_lsdb_add (ospf6_lsa_copy (lsa), lsdb_self); 114 115 lsa->refresh = thread_add_timer (master, ospf6_lsa_refresh, lsa, 116 OSPF_LS_REFRESH_TIME); 117 118 if (IS_OSPF6_DEBUG_LSA_TYPE (lsa->header->type) || 119 IS_OSPF6_DEBUG_ORIGINATE_TYPE (lsa->header->type)) 120 { 121 zlog_debug ("LSA Originate:"); 122 ospf6_lsa_header_print (lsa); 123 } 124 125 ospf6_install_lsa (lsa); 126 ospf6_flood (NULL, lsa); 127} 128 129void 130ospf6_lsa_originate_process (struct ospf6_lsa *lsa, 131 struct ospf6 *process) 132{ 133 lsa->lsdb = process->lsdb; 134 ospf6_lsa_originate (lsa); 135} 136 137void 138ospf6_lsa_originate_area (struct ospf6_lsa *lsa, 139 struct ospf6_area *oa) 140{ 141 lsa->lsdb = oa->lsdb; 142 ospf6_lsa_originate (lsa); 143} 144 145void 146ospf6_lsa_originate_interface (struct ospf6_lsa *lsa, 147 struct ospf6_interface *oi) 148{ 149 lsa->lsdb = oi->lsdb; 150 ospf6_lsa_originate (lsa); 151} 152 153void 154ospf6_lsa_purge (struct ospf6_lsa *lsa) 155{ 156 struct ospf6_lsa *self; 157 struct ospf6_lsdb *lsdb_self; 158 159 /* remove it from the LSDB for self-originated LSAs */ 160 lsdb_self = ospf6_get_scoped_lsdb_self (lsa); 161 self = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id, 162 lsa->header->adv_router, lsdb_self); 163 if (self) 164 { 165 THREAD_OFF (self->expire); 166 THREAD_OFF (self->refresh); 167 ospf6_lsdb_remove (self, lsdb_self); 168 } 169 170 ospf6_lsa_premature_aging (lsa); 171} 172 173 174void 175ospf6_increment_retrans_count (struct ospf6_lsa *lsa) 176{ 177 /* The LSA must be the original one (see the description 178 in ospf6_decrement_retrans_count () below) */ 179 lsa->retrans_count++; 180} 181 182void 183ospf6_decrement_retrans_count (struct ospf6_lsa *lsa) 184{ 185 struct ospf6_lsdb *lsdb; 186 struct ospf6_lsa *orig; 187 188 /* The LSA must be on the retrans-list of a neighbor. It means 189 the "lsa" is a copied one, and we have to decrement the 190 retransmission count of the original one (instead of this "lsa"'s). 191 In order to find the original LSA, first we have to find 192 appropriate LSDB that have the original LSA. */ 193 lsdb = ospf6_get_scoped_lsdb (lsa); 194 195 /* Find the original LSA of which the retrans_count should be decremented */ 196 orig = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id, 197 lsa->header->adv_router, lsdb); 198 if (orig) 199 { 200 orig->retrans_count--; 201 assert (orig->retrans_count >= 0); 202 } 203} 204 205/* RFC2328 section 13.2 Installing LSAs in the database */ 206void 207ospf6_install_lsa (struct ospf6_lsa *lsa) 208{ 209 struct timeval now; 210 struct ospf6_lsa *old; 211 212 if (IS_OSPF6_DEBUG_LSA_TYPE (lsa->header->type) || 213 IS_OSPF6_DEBUG_EXAMIN_TYPE (lsa->header->type)) 214 zlog_debug ("Install LSA: %s", lsa->name); 215 216 /* Remove the old instance from all neighbors' Link state 217 retransmission list (RFC2328 13.2 last paragraph) */ 218 old = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id, 219 lsa->header->adv_router, lsa->lsdb); 220 if (old) 221 { 222 THREAD_OFF (old->expire); 223 THREAD_OFF (old->refresh); 224 ospf6_flood_clear (old); 225 } 226 227 quagga_gettime (QUAGGA_CLK_MONOTONIC, &now); 228 if (! OSPF6_LSA_IS_MAXAGE (lsa)) 229 lsa->expire = thread_add_timer (master, ospf6_lsa_expire, lsa, 230 OSPF_LSA_MAXAGE + lsa->birth.tv_sec - now.tv_sec); 231 else 232 lsa->expire = NULL; 233 234 if (OSPF6_LSA_IS_SEQWRAP(lsa) && 235 ! (CHECK_FLAG(lsa->flag,OSPF6_LSA_SEQWRAPPED) && 236 lsa->header->seqnum == htonl(OSPF_MAX_SEQUENCE_NUMBER))) 237 { 238 if (IS_OSPF6_DEBUG_EXAMIN_TYPE (lsa->header->type)) 239 zlog_debug("lsa install wrapping: sequence 0x%x", 240 ntohl(lsa->header->seqnum)); 241 SET_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED); 242 /* in lieu of premature_aging, since we do not want to recreate this lsa 243 * and/or mess with timers etc, we just want to wrap the sequence number 244 * and reflood the lsa before continuing. 245 * NOTE: Flood needs to be called right after this function call, by the 246 * caller 247 */ 248 lsa->header->seqnum = htonl (OSPF_MAX_SEQUENCE_NUMBER); 249 lsa->header->age = htons (OSPF_LSA_MAXAGE); 250 ospf6_lsa_checksum (lsa->header); 251 } 252 253 /* actually install */ 254 lsa->installed = now; 255 ospf6_lsdb_add (lsa, lsa->lsdb); 256 257 return; 258} 259 260/* RFC2740 section 3.5.2. Sending Link State Update packets */ 261/* RFC2328 section 13.3 Next step in the flooding procedure */ 262static void 263ospf6_flood_interface (struct ospf6_neighbor *from, 264 struct ospf6_lsa *lsa, struct ospf6_interface *oi) 265{ 266 struct listnode *node, *nnode; 267 struct ospf6_neighbor *on; 268 struct ospf6_lsa *req; 269 int retrans_added = 0; 270 int is_debug = 0; 271 272 if (IS_OSPF6_DEBUG_FLOODING || 273 IS_OSPF6_DEBUG_FLOOD_TYPE (lsa->header->type)) 274 { 275 is_debug++; 276 zlog_debug ("Flooding on %s: %s", oi->interface->name, lsa->name); 277 } 278 279 /* (1) For each neighbor */ 280 for (ALL_LIST_ELEMENTS (oi->neighbor_list, node, nnode, on)) 281 { 282 if (is_debug) 283 zlog_debug ("To neighbor %s", on->name); 284 285 /* (a) if neighbor state < Exchange, examin next */ 286 if (on->state < OSPF6_NEIGHBOR_EXCHANGE) 287 { 288 if (is_debug) 289 zlog_debug ("Neighbor state less than ExChange, next neighbor"); 290 continue; 291 } 292 293 /* (b) if neighbor not yet Full, check request-list */ 294 if (on->state != OSPF6_NEIGHBOR_FULL) 295 { 296 if (is_debug) 297 zlog_debug ("Neighbor not yet Full"); 298 299 req = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id, 300 lsa->header->adv_router, on->request_list); 301 if (req == NULL) 302 { 303 if (is_debug) 304 zlog_debug ("Not on request-list for this neighbor"); 305 /* fall through */ 306 } 307 else 308 { 309 /* If new LSA less recent, examin next neighbor */ 310 if (ospf6_lsa_compare (lsa, req) > 0) 311 { 312 if (is_debug) 313 zlog_debug ("Requesting is older, next neighbor"); 314 continue; 315 } 316 317 /* If the same instance, delete from request-list and 318 examin next neighbor */ 319 if (ospf6_lsa_compare (lsa, req) == 0) 320 { 321 if (is_debug) 322 zlog_debug ("Requesting the same, remove it, next neighbor"); 323 if (req == on->last_ls_req) 324 { 325 ospf6_lsa_unlock (req); 326 on->last_ls_req = NULL; 327 } 328 ospf6_lsdb_remove (req, on->request_list); 329 ospf6_check_nbr_loading (on); 330 continue; 331 } 332 333 /* If the new LSA is more recent, delete from request-list */ 334 if (ospf6_lsa_compare (lsa, req) < 0) 335 { 336 if (is_debug) 337 zlog_debug ("Received is newer, remove requesting"); 338 if (req == on->last_ls_req) 339 { 340 ospf6_lsa_unlock (req); 341 on->last_ls_req = NULL; 342 } 343 ospf6_lsdb_remove (req, on->request_list); 344 ospf6_check_nbr_loading (on); 345 /* fall through */ 346 } 347 } 348 } 349 350 /* (c) If the new LSA was received from this neighbor, 351 examin next neighbor */ 352 if (from == on) 353 { 354 if (is_debug) 355 zlog_debug ("Received is from the neighbor, next neighbor"); 356 continue; 357 } 358 359 /* (d) add retrans-list, schedule retransmission */ 360 if (is_debug) 361 zlog_debug ("Add retrans-list of this neighbor"); 362 ospf6_increment_retrans_count (lsa); 363 ospf6_lsdb_add (ospf6_lsa_copy (lsa), on->retrans_list); 364 if (on->thread_send_lsupdate == NULL) 365 on->thread_send_lsupdate = 366 thread_add_timer (master, ospf6_lsupdate_send_neighbor, 367 on, on->ospf6_if->rxmt_interval); 368 retrans_added++; 369 } 370 371 /* (2) examin next interface if not added to retrans-list */ 372 if (retrans_added == 0) 373 { 374 if (is_debug) 375 zlog_debug ("No retransmission scheduled, next interface"); 376 return; 377 } 378 379 /* (3) If the new LSA was received on this interface, 380 and it was from DR or BDR, examin next interface */ 381 if (from && from->ospf6_if == oi && 382 (from->router_id == oi->drouter || from->router_id == oi->bdrouter)) 383 { 384 if (is_debug) 385 zlog_debug ("Received is from the I/F's DR or BDR, next interface"); 386 return; 387 } 388 389 /* (4) If the new LSA was received on this interface, 390 and the interface state is BDR, examin next interface */ 391 if (from && from->ospf6_if == oi) 392 { 393 if (oi->state == OSPF6_INTERFACE_BDR) 394 { 395 if (is_debug) 396 zlog_debug ("Received is from the I/F, itself BDR, next interface"); 397 return; 398 } 399 SET_FLAG(lsa->flag, OSPF6_LSA_FLOODBACK); 400 } 401 402 /* (5) flood the LSA out the interface. */ 403 if (is_debug) 404 zlog_debug ("Schedule flooding for the interface"); 405 if ((oi->type == OSPF_IFTYPE_BROADCAST) || 406 (oi->type == OSPF_IFTYPE_POINTOPOINT)) 407 { 408 ospf6_lsdb_add (ospf6_lsa_copy (lsa), oi->lsupdate_list); 409 if (oi->thread_send_lsupdate == NULL) 410 oi->thread_send_lsupdate = 411 thread_add_event (master, ospf6_lsupdate_send_interface, oi, 0); 412 } 413 else 414 { 415 /* reschedule retransmissions to all neighbors */ 416 for (ALL_LIST_ELEMENTS (oi->neighbor_list, node, nnode, on)) 417 { 418 THREAD_OFF (on->thread_send_lsupdate); 419 on->thread_send_lsupdate = 420 thread_add_event (master, ospf6_lsupdate_send_neighbor, on, 0); 421 } 422 } 423} 424 425static void 426ospf6_flood_area (struct ospf6_neighbor *from, 427 struct ospf6_lsa *lsa, struct ospf6_area *oa) 428{ 429 struct listnode *node, *nnode; 430 struct ospf6_interface *oi; 431 432 for (ALL_LIST_ELEMENTS (oa->if_list, node, nnode, oi)) 433 { 434 if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_LINKLOCAL && 435 oi != OSPF6_INTERFACE (lsa->lsdb->data)) 436 continue; 437 438#if 0 439 if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_AS && 440 ospf6_is_interface_virtual_link (oi)) 441 continue; 442#endif/*0*/ 443 444 ospf6_flood_interface (from, lsa, oi); 445 } 446} 447 448static void 449ospf6_flood_process (struct ospf6_neighbor *from, 450 struct ospf6_lsa *lsa, struct ospf6 *process) 451{ 452 struct listnode *node, *nnode; 453 struct ospf6_area *oa; 454 455 for (ALL_LIST_ELEMENTS (process->area_list, node, nnode, oa)) 456 { 457 if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_AREA && 458 oa != OSPF6_AREA (lsa->lsdb->data)) 459 continue; 460 if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_LINKLOCAL && 461 oa != OSPF6_INTERFACE (lsa->lsdb->data)->area) 462 continue; 463 464 if (ntohs (lsa->header->type) == OSPF6_LSTYPE_AS_EXTERNAL && 465 IS_AREA_STUB (oa)) 466 continue; 467 468 ospf6_flood_area (from, lsa, oa); 469 } 470} 471 472void 473ospf6_flood (struct ospf6_neighbor *from, struct ospf6_lsa *lsa) 474{ 475 ospf6_flood_process (from, lsa, ospf6); 476} 477 478static void 479ospf6_flood_clear_interface (struct ospf6_lsa *lsa, struct ospf6_interface *oi) 480{ 481 struct listnode *node, *nnode; 482 struct ospf6_neighbor *on; 483 struct ospf6_lsa *rem; 484 485 for (ALL_LIST_ELEMENTS (oi->neighbor_list, node, nnode, on)) 486 { 487 rem = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id, 488 lsa->header->adv_router, on->retrans_list); 489 if (rem && ! ospf6_lsa_compare (rem, lsa)) 490 { 491 if (IS_OSPF6_DEBUG_FLOODING || 492 IS_OSPF6_DEBUG_FLOOD_TYPE (lsa->header->type)) 493 zlog_debug ("Remove %s from retrans_list of %s", 494 rem->name, on->name); 495 ospf6_decrement_retrans_count (rem); 496 ospf6_lsdb_remove (rem, on->retrans_list); 497 } 498 } 499} 500 501static void 502ospf6_flood_clear_area (struct ospf6_lsa *lsa, struct ospf6_area *oa) 503{ 504 struct listnode *node, *nnode; 505 struct ospf6_interface *oi; 506 507 for (ALL_LIST_ELEMENTS (oa->if_list, node, nnode, oi)) 508 { 509 if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_LINKLOCAL && 510 oi != OSPF6_INTERFACE (lsa->lsdb->data)) 511 continue; 512 513#if 0 514 if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_AS && 515 ospf6_is_interface_virtual_link (oi)) 516 continue; 517#endif/*0*/ 518 519 ospf6_flood_clear_interface (lsa, oi); 520 } 521} 522 523static void 524ospf6_flood_clear_process (struct ospf6_lsa *lsa, struct ospf6 *process) 525{ 526 struct listnode *node, *nnode; 527 struct ospf6_area *oa; 528 529 for (ALL_LIST_ELEMENTS (process->area_list, node, nnode, oa)) 530 { 531 if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_AREA && 532 oa != OSPF6_AREA (lsa->lsdb->data)) 533 continue; 534 if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_LINKLOCAL && 535 oa != OSPF6_INTERFACE (lsa->lsdb->data)->area) 536 continue; 537 538 if (ntohs (lsa->header->type) == OSPF6_LSTYPE_AS_EXTERNAL && 539 IS_AREA_STUB (oa)) 540 continue; 541 542 ospf6_flood_clear_area (lsa, oa); 543 } 544} 545 546void 547ospf6_flood_clear (struct ospf6_lsa *lsa) 548{ 549 ospf6_flood_clear_process (lsa, ospf6); 550} 551 552 553/* RFC2328 13.5 (Table 19): Sending link state acknowledgements. */ 554static void 555ospf6_acknowledge_lsa_bdrouter (struct ospf6_lsa *lsa, int ismore_recent, 556 struct ospf6_neighbor *from) 557{ 558 struct ospf6_interface *oi; 559 int is_debug = 0; 560 561 if (IS_OSPF6_DEBUG_FLOODING || 562 IS_OSPF6_DEBUG_FLOOD_TYPE (lsa->header->type)) 563 is_debug++; 564 565 assert (from && from->ospf6_if); 566 oi = from->ospf6_if; 567 568 /* LSA is more recent than database copy, but was not flooded 569 back out receiving interface. Delayed acknowledgement sent 570 if advertisement received from Designated Router, 571 otherwide do nothing. */ 572 if (ismore_recent < 0) 573 { 574 if (oi->drouter == from->router_id) 575 { 576 if (is_debug) 577 zlog_debug ("Delayed acknowledgement (BDR & MoreRecent & from DR)"); 578 /* Delayed acknowledgement */ 579 ospf6_lsdb_add (ospf6_lsa_copy (lsa), oi->lsack_list); 580 if (oi->thread_send_lsack == NULL) 581 oi->thread_send_lsack = 582 thread_add_timer (master, ospf6_lsack_send_interface, oi, 3); 583 } 584 else 585 { 586 if (is_debug) 587 zlog_debug ("No acknowledgement (BDR & MoreRecent & ! from DR)"); 588 } 589 return; 590 } 591 592 /* LSA is a duplicate, and was treated as an implied acknowledgement. 593 Delayed acknowledgement sent if advertisement received from 594 Designated Router, otherwise do nothing */ 595 if (CHECK_FLAG (lsa->flag, OSPF6_LSA_DUPLICATE) && 596 CHECK_FLAG (lsa->flag, OSPF6_LSA_IMPLIEDACK)) 597 { 598 if (oi->drouter == from->router_id) 599 { 600 if (is_debug) 601 zlog_debug ("Delayed acknowledgement (BDR & Duplicate & ImpliedAck & from DR)"); 602 /* Delayed acknowledgement */ 603 ospf6_lsdb_add (ospf6_lsa_copy (lsa), oi->lsack_list); 604 if (oi->thread_send_lsack == NULL) 605 oi->thread_send_lsack = 606 thread_add_timer (master, ospf6_lsack_send_interface, oi, 3); 607 } 608 else 609 { 610 if (is_debug) 611 zlog_debug ("No acknowledgement (BDR & Duplicate & ImpliedAck & ! from DR)"); 612 } 613 return; 614 } 615 616 /* LSA is a duplicate, and was not treated as an implied acknowledgement. 617 Direct acknowledgement sent */ 618 if (CHECK_FLAG (lsa->flag, OSPF6_LSA_DUPLICATE) && 619 ! CHECK_FLAG (lsa->flag, OSPF6_LSA_IMPLIEDACK)) 620 { 621 if (is_debug) 622 zlog_debug ("Direct acknowledgement (BDR & Duplicate)"); 623 ospf6_lsdb_add (ospf6_lsa_copy (lsa), from->lsack_list); 624 if (from->thread_send_lsack == NULL) 625 from->thread_send_lsack = 626 thread_add_event (master, ospf6_lsack_send_neighbor, from, 0); 627 return; 628 } 629 630 /* LSA's LS age is equal to Maxage, and there is no current instance 631 of the LSA in the link state database, and none of router's 632 neighbors are in states Exchange or Loading */ 633 /* Direct acknowledgement sent, but this case is handled in 634 early of ospf6_receive_lsa () */ 635} 636 637static void 638ospf6_acknowledge_lsa_allother (struct ospf6_lsa *lsa, int ismore_recent, 639 struct ospf6_neighbor *from) 640{ 641 struct ospf6_interface *oi; 642 int is_debug = 0; 643 644 if (IS_OSPF6_DEBUG_FLOODING || 645 IS_OSPF6_DEBUG_FLOOD_TYPE (lsa->header->type)) 646 is_debug++; 647 648 assert (from && from->ospf6_if); 649 oi = from->ospf6_if; 650 651 /* LSA has been flood back out receiving interface. 652 No acknowledgement sent. */ 653 if (CHECK_FLAG (lsa->flag, OSPF6_LSA_FLOODBACK)) 654 { 655 if (is_debug) 656 zlog_debug ("No acknowledgement (AllOther & FloodBack)"); 657 return; 658 } 659 660 /* LSA is more recent than database copy, but was not flooded 661 back out receiving interface. Delayed acknowledgement sent. */ 662 if (ismore_recent < 0) 663 { 664 if (is_debug) 665 zlog_debug ("Delayed acknowledgement (AllOther & MoreRecent)"); 666 /* Delayed acknowledgement */ 667 ospf6_lsdb_add (ospf6_lsa_copy (lsa), oi->lsack_list); 668 if (oi->thread_send_lsack == NULL) 669 oi->thread_send_lsack = 670 thread_add_timer (master, ospf6_lsack_send_interface, oi, 3); 671 return; 672 } 673 674 /* LSA is a duplicate, and was treated as an implied acknowledgement. 675 No acknowledgement sent. */ 676 if (CHECK_FLAG (lsa->flag, OSPF6_LSA_DUPLICATE) && 677 CHECK_FLAG (lsa->flag, OSPF6_LSA_IMPLIEDACK)) 678 { 679 if (is_debug) 680 zlog_debug ("No acknowledgement (AllOther & Duplicate & ImpliedAck)"); 681 return; 682 } 683 684 /* LSA is a duplicate, and was not treated as an implied acknowledgement. 685 Direct acknowledgement sent */ 686 if (CHECK_FLAG (lsa->flag, OSPF6_LSA_DUPLICATE) && 687 ! CHECK_FLAG (lsa->flag, OSPF6_LSA_IMPLIEDACK)) 688 { 689 if (is_debug) 690 zlog_debug ("Direct acknowledgement (AllOther & Duplicate)"); 691 ospf6_lsdb_add (ospf6_lsa_copy (lsa), from->lsack_list); 692 if (from->thread_send_lsack == NULL) 693 from->thread_send_lsack = 694 thread_add_event (master, ospf6_lsack_send_neighbor, from, 0); 695 return; 696 } 697 698 /* LSA's LS age is equal to Maxage, and there is no current instance 699 of the LSA in the link state database, and none of router's 700 neighbors are in states Exchange or Loading */ 701 /* Direct acknowledgement sent, but this case is handled in 702 early of ospf6_receive_lsa () */ 703} 704 705static void 706ospf6_acknowledge_lsa (struct ospf6_lsa *lsa, int ismore_recent, 707 struct ospf6_neighbor *from) 708{ 709 struct ospf6_interface *oi; 710 711 assert (from && from->ospf6_if); 712 oi = from->ospf6_if; 713 714 if (oi->state == OSPF6_INTERFACE_BDR) 715 ospf6_acknowledge_lsa_bdrouter (lsa, ismore_recent, from); 716 else 717 ospf6_acknowledge_lsa_allother (lsa, ismore_recent, from); 718} 719 720/* RFC2328 section 13 (4): 721 if MaxAge LSA and if we have no instance, and no neighbor 722 is in states Exchange or Loading 723 returns 1 if match this case, else returns 0 */ 724static int 725ospf6_is_maxage_lsa_drop (struct ospf6_lsa *lsa, struct ospf6_neighbor *from) 726{ 727 struct ospf6_neighbor *on; 728 struct ospf6_interface *oi; 729 struct ospf6_area *oa; 730 struct ospf6 *process = NULL; 731 struct listnode *i, *j, *k; 732 int count = 0; 733 734 if (! OSPF6_LSA_IS_MAXAGE (lsa)) 735 return 0; 736 737 if (ospf6_lsdb_lookup (lsa->header->type, lsa->header->id, 738 lsa->header->adv_router, lsa->lsdb)) 739 return 0; 740 741 process = from->ospf6_if->area->ospf6; 742 743 for (ALL_LIST_ELEMENTS_RO (process->area_list, i, oa)) 744 for (ALL_LIST_ELEMENTS_RO (oa->if_list, j, oi)) 745 for (ALL_LIST_ELEMENTS_RO (oi->neighbor_list, k, on)) 746 if (on->state == OSPF6_NEIGHBOR_EXCHANGE || 747 on->state == OSPF6_NEIGHBOR_LOADING) 748 count++; 749 750 if (count == 0) 751 return 1; 752 return 0; 753} 754 755/* RFC2328 section 13 The Flooding Procedure */ 756void 757ospf6_receive_lsa (struct ospf6_neighbor *from, 758 struct ospf6_lsa_header *lsa_header) 759{ 760 struct ospf6_lsa *new = NULL, *old = NULL, *rem = NULL; 761 int ismore_recent; 762 int is_debug = 0; 763 764 ismore_recent = 1; 765 assert (from); 766 767 /* make lsa structure for received lsa */ 768 new = ospf6_lsa_create (lsa_header); 769 770 if (IS_OSPF6_DEBUG_FLOODING || 771 IS_OSPF6_DEBUG_FLOOD_TYPE (new->header->type)) 772 { 773 is_debug++; 774 zlog_debug ("LSA Receive from %s", from->name); 775 ospf6_lsa_header_print (new); 776 } 777 778 /* (1) LSA Checksum */ 779 if (! ospf6_lsa_checksum_valid (new->header)) 780 { 781 if (is_debug) 782 zlog_debug ("Wrong LSA Checksum, discard"); 783 ospf6_lsa_delete (new); 784 return; 785 } 786 787 /* (2) Examine the LSA's LS type. 788 RFC2470 3.5.1. Receiving Link State Update packets */ 789 if (IS_AREA_STUB (from->ospf6_if->area) && 790 OSPF6_LSA_SCOPE (new->header->type) == OSPF6_SCOPE_AS) 791 { 792 if (is_debug) 793 zlog_debug ("AS-External-LSA (or AS-scope LSA) in stub area, discard"); 794 ospf6_lsa_delete (new); 795 return; 796 } 797 798 /* (3) LSA which have reserved scope is discarded 799 RFC2470 3.5.1. Receiving Link State Update packets */ 800 /* Flooding scope check. LSAs with unknown scope are discarded here. 801 Set appropriate LSDB for the LSA */ 802 switch (OSPF6_LSA_SCOPE (new->header->type)) 803 { 804 case OSPF6_SCOPE_LINKLOCAL: 805 new->lsdb = from->ospf6_if->lsdb; 806 break; 807 case OSPF6_SCOPE_AREA: 808 new->lsdb = from->ospf6_if->area->lsdb; 809 break; 810 case OSPF6_SCOPE_AS: 811 new->lsdb = from->ospf6_if->area->ospf6->lsdb; 812 break; 813 default: 814 if (is_debug) 815 zlog_debug ("LSA has reserved scope, discard"); 816 ospf6_lsa_delete (new); 817 return; 818 } 819 820 /* (4) if MaxAge LSA and if we have no instance, and no neighbor 821 is in states Exchange or Loading */ 822 if (ospf6_is_maxage_lsa_drop (new, from)) 823 { 824 /* log */ 825 if (is_debug) 826 zlog_debug ("Drop MaxAge LSA with direct acknowledgement."); 827 828 /* a) Acknowledge back to neighbor (Direct acknowledgement, 13.5) */ 829 ospf6_lsdb_add (ospf6_lsa_copy (new), from->lsack_list); 830 if (from->thread_send_lsack == NULL) 831 from->thread_send_lsack = 832 thread_add_event (master, ospf6_lsack_send_neighbor, from, 0); 833 834 /* b) Discard */ 835 ospf6_lsa_delete (new); 836 return; 837 } 838 839 /* (5) */ 840 /* lookup the same database copy in lsdb */ 841 old = ospf6_lsdb_lookup (new->header->type, new->header->id, 842 new->header->adv_router, new->lsdb); 843 if (old) 844 { 845 ismore_recent = ospf6_lsa_compare (new, old); 846 if (ntohl (new->header->seqnum) == ntohl (old->header->seqnum)) 847 { 848 if (is_debug) 849 zlog_debug ("Received is duplicated LSA"); 850 SET_FLAG (new->flag, OSPF6_LSA_DUPLICATE); 851 } 852 } 853 854 /* if no database copy or received is more recent */ 855 if (old == NULL || ismore_recent < 0) 856 { 857 /* in case we have no database copy */ 858 ismore_recent = -1; 859 860 /* (a) MinLSArrival check */ 861 if (old) 862 { 863 struct timeval now, res; 864 quagga_gettime (QUAGGA_CLK_MONOTONIC, &now); 865 timersub (&now, &old->installed, &res); 866 if (res.tv_sec < OSPF_MIN_LS_ARRIVAL) 867 { 868 if (is_debug) 869 zlog_debug ("LSA can't be updated within MinLSArrival, discard"); 870 ospf6_lsa_delete (new); 871 return; /* examin next lsa */ 872 } 873 } 874 875 quagga_gettime (QUAGGA_CLK_MONOTONIC, &new->received); 876 877 if (is_debug) 878 zlog_debug ("Install, Flood, Possibly acknowledge the received LSA"); 879 880 /* Remove older copies of this LSA from retx lists */ 881 if (old) 882 ospf6_flood_clear (old); 883 884 /* (b) immediately flood and (c) remove from all retrans-list */ 885 /* Prevent self-originated LSA to be flooded. this is to make 886 reoriginated instance of the LSA not to be rejected by other routers 887 due to MinLSArrival. */ 888 if (new->header->adv_router != from->ospf6_if->area->ospf6->router_id) 889 ospf6_flood (from, new); 890 891 /* (d), installing lsdb, which may cause routing 892 table calculation (replacing database copy) */ 893 ospf6_install_lsa (new); 894 895 /* (e) possibly acknowledge */ 896 ospf6_acknowledge_lsa (new, ismore_recent, from); 897 898 /* (f) Self Originated LSA, section 13.4 */ 899 if (new->header->adv_router == from->ospf6_if->area->ospf6->router_id) 900 { 901 /* Self-originated LSA (newer than ours) is received from 902 another router. We have to make a new instance of the LSA 903 or have to flush this LSA. */ 904 if (is_debug) 905 { 906 zlog_debug ("Newer instance of the self-originated LSA"); 907 zlog_debug ("Schedule reorigination"); 908 } 909 new->refresh = thread_add_event (master, ospf6_lsa_refresh, new, 0); 910 } 911 912 return; 913 } 914 915 /* (6) if there is instance on sending neighbor's request list */ 916 if (ospf6_lsdb_lookup (new->header->type, new->header->id, 917 new->header->adv_router, from->request_list)) 918 { 919 /* if no database copy, should go above state (5) */ 920 assert (old); 921 922 if (is_debug) 923 { 924 zlog_debug ("Received is not newer, on the neighbor's request-list"); 925 zlog_debug ("BadLSReq, discard the received LSA"); 926 } 927 928 /* BadLSReq */ 929 thread_add_event (master, bad_lsreq, from, 0); 930 931 ospf6_lsa_delete (new); 932 return; 933 } 934 935 /* (7) if neither one is more recent */ 936 if (ismore_recent == 0) 937 { 938 if (is_debug) 939 zlog_debug ("The same instance as database copy (neither recent)"); 940 941 /* (a) if on retrans-list, Treat this LSA as an Ack: Implied Ack */ 942 rem = ospf6_lsdb_lookup (new->header->type, new->header->id, 943 new->header->adv_router, from->retrans_list); 944 if (rem) 945 { 946 if (is_debug) 947 { 948 zlog_debug ("It is on the neighbor's retrans-list."); 949 zlog_debug ("Treat as an Implied acknowledgement"); 950 } 951 SET_FLAG (new->flag, OSPF6_LSA_IMPLIEDACK); 952 ospf6_decrement_retrans_count (rem); 953 ospf6_lsdb_remove (rem, from->retrans_list); 954 } 955 956 if (is_debug) 957 zlog_debug ("Possibly acknowledge and then discard"); 958 959 /* (b) possibly acknowledge */ 960 ospf6_acknowledge_lsa (new, ismore_recent, from); 961 962 ospf6_lsa_delete (new); 963 return; 964 } 965 966 /* (8) previous database copy is more recent */ 967 { 968 assert (old); 969 970 /* If database copy is in 'Seqnumber Wrapping', 971 simply discard the received LSA */ 972 if (OSPF6_LSA_IS_MAXAGE (old) && 973 old->header->seqnum == htonl (OSPF_MAX_SEQUENCE_NUMBER)) 974 { 975 if (is_debug) 976 { 977 zlog_debug ("The LSA is in Seqnumber Wrapping"); 978 zlog_debug ("MaxAge & MaxSeqNum, discard"); 979 } 980 ospf6_lsa_delete (new); 981 return; 982 } 983 984 /* Otherwise, Send database copy of this LSA to this neighbor */ 985 { 986 if (is_debug) 987 { 988 zlog_debug ("Database copy is more recent."); 989 zlog_debug ("Send back directly and then discard"); 990 } 991 992 /* XXX, MinLSArrival check !? RFC 2328 13 (8) */ 993 994 ospf6_lsdb_add (ospf6_lsa_copy (old), from->lsupdate_list); 995 if (from->thread_send_lsupdate == NULL) 996 from->thread_send_lsupdate = 997 thread_add_event (master, ospf6_lsupdate_send_neighbor, from, 0); 998 ospf6_lsa_delete (new); 999 return; 1000 } 1001 return; 1002 } 1003} 1004 1005 1006DEFUN (debug_ospf6_flooding, 1007 debug_ospf6_flooding_cmd, 1008 "debug ospf6 flooding", 1009 DEBUG_STR 1010 OSPF6_STR 1011 "Debug OSPFv3 flooding function\n" 1012 ) 1013{ 1014 OSPF6_DEBUG_FLOODING_ON (); 1015 return CMD_SUCCESS; 1016} 1017 1018DEFUN (no_debug_ospf6_flooding, 1019 no_debug_ospf6_flooding_cmd, 1020 "no debug ospf6 flooding", 1021 NO_STR 1022 DEBUG_STR 1023 OSPF6_STR 1024 "Debug OSPFv3 flooding function\n" 1025 ) 1026{ 1027 OSPF6_DEBUG_FLOODING_OFF (); 1028 return CMD_SUCCESS; 1029} 1030 1031int 1032config_write_ospf6_debug_flood (struct vty *vty) 1033{ 1034 if (IS_OSPF6_DEBUG_FLOODING) 1035 vty_out (vty, "debug ospf6 flooding%s", VNL); 1036 return 0; 1037} 1038 1039void 1040install_element_ospf6_debug_flood (void) 1041{ 1042 install_element (ENABLE_NODE, &debug_ospf6_flooding_cmd); 1043 install_element (ENABLE_NODE, &no_debug_ospf6_flooding_cmd); 1044 install_element (CONFIG_NODE, &debug_ospf6_flooding_cmd); 1045 install_element (CONFIG_NODE, &no_debug_ospf6_flooding_cmd); 1046} 1047 1048 1049 1050 1051 1052