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                                    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
 129 void
 130 ospf6_lsa_originate_process (struct ospf6_lsa *lsa,
 131                              struct ospf6 *process)
 132 {
 133   lsa->lsdb = process->lsdb;
 134   ospf6_lsa_originate (lsa);
 135 }
 136
 137 void
 138 ospf6_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
 145 void
 146 ospf6_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
 153 void
 154 ospf6_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
 174 void
 175 ospf6_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
 182 void
 183 ospf6_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 */
 206 void
 207 ospf6_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 */
 262 static void
 263 ospf6_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
 425 static void
 426 ospf6_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
 448 static void
 449 ospf6_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
 472 void
 473 ospf6_flood (struct ospf6_neighbor *from, struct ospf6_lsa *lsa)
 474 {
 475   ospf6_flood_process (from, lsa, ospf6);
 476 }
 477
 478 static void
 479 ospf6_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
 501 static void
 502 ospf6_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
 523 static void
 524 ospf6_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
 546 void
 547 ospf6_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. */
 554 static void
 555 ospf6_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
 637 static void
 638 ospf6_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
 705 static void
 706 ospf6_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 */
 724 static int
 725 ospf6_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 */
 756 void
 757 ospf6_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 / 1000))
 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
1006 DEFUN (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
1018 DEFUN (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
1031 int
1032 config_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
1039 void
1040 install_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