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