ospf6d/ospf6_flood.c

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