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