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                            __PRETTY_FUNCTION__, lsa->name,
 262                            ntohs(lsa->header->age), 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                                                 ospf6_lsa_unlock(req);
 334                                                 on->last_ls_req = NULL;
 335                                         }
 336                                         ospf6_lsdb_remove(req,
 337                                                           on->request_list);
 338                                         ospf6_check_nbr_loading(on);
 339                                         continue;
 340                                 }
 341
 342                                 /* If the new LSA is more recent, delete from
 343                                  * request-list */
 344                                 if (ospf6_lsa_compare(lsa, req) < 0) {
 345                                         if (is_debug)
 346                                                 zlog_debug(
 347                                                         "Received is newer, remove requesting");
 348                                         if (req == on->last_ls_req) {
 349                                                 ospf6_lsa_unlock(req);
 350                                                 on->last_ls_req = NULL;
 351                                         }
 352                                         if (req)
 353                                                 ospf6_lsdb_remove(req,
 354                                                         on->request_list);
 355                                         ospf6_check_nbr_loading(on);
 356                                         /* fall through */
 357                                 }
 358                         }
 359                 }
 360
 361                 /* (c) If the new LSA was received from this neighbor,
 362                    examin next neighbor */
 363                 if (from == on) {
 364                         if (is_debug)
 365                                 zlog_debug(
 366                                         "Received is from the neighbor, next neighbor");
 367                         continue;
 368                 }
 369
 370                 if (ospf6->inst_shutdown) {
 371                         if (is_debug)
 372                                 zlog_debug(
 373                                         "%s: Send LSA %s (age %d) update now",
 374                                         __PRETTY_FUNCTION__, lsa->name,
 375                                         ntohs(lsa->header->age));
 376                         ospf6_lsupdate_send_neighbor_now(on, lsa);
 377                         continue;
 378                 } else {
 379                         /* (d) add retrans-list, schedule retransmission */
 380                         if (is_debug)
 381                                 zlog_debug("Add retrans-list of this neighbor");
 382                         ospf6_increment_retrans_count(lsa);
 383                         ospf6_lsdb_add(ospf6_lsa_copy(lsa), on->retrans_list);
 384                         thread_add_timer(master, ospf6_lsupdate_send_neighbor,
 385                                          on, on->ospf6_if->rxmt_interval,
 386                                          &on->thread_send_lsupdate);
 387                         retrans_added++;
 388                 }
 389         }
 390
 391         /* (2) examin next interface if not added to retrans-list */
 392         if (retrans_added == 0) {
 393                 if (is_debug)
 394                         zlog_debug(
 395                                 "No retransmission scheduled, next interface");
 396                 return;
 397         }
 398
 399         /* (3) If the new LSA was received on this interface,
 400            and it was from DR or BDR, examin next interface */
 401         if (from && from->ospf6_if == oi
 402             && (from->router_id == oi->drouter
 403                 || from->router_id == oi->bdrouter)) {
 404                 if (is_debug)
 405                         zlog_debug(
 406                                 "Received is from the I/F's DR or BDR, next interface");
 407                 return;
 408         }
 409
 410         /* (4) If the new LSA was received on this interface,
 411            and the interface state is BDR, examin next interface */
 412         if (from && from->ospf6_if == oi) {
 413                 if (oi->state == OSPF6_INTERFACE_BDR) {
 414                         if (is_debug)
 415                                 zlog_debug(
 416                                         "Received is from the I/F, itself BDR, next interface");
 417                         return;
 418                 }
 419                 SET_FLAG(lsa->flag, OSPF6_LSA_FLOODBACK);
 420         }
 421
 422         /* (5) flood the LSA out the interface. */
 423         if (is_debug)
 424                 zlog_debug("Schedule flooding for the interface");
 425         if ((oi->type == OSPF_IFTYPE_BROADCAST)
 426             || (oi->type == OSPF_IFTYPE_POINTOPOINT)) {
 427                 ospf6_lsdb_add(ospf6_lsa_copy(lsa), oi->lsupdate_list);
 428                 thread_add_event(master, ospf6_lsupdate_send_interface, oi, 0,
 429                                  &oi->thread_send_lsupdate);
 430         } else {
 431                 /* reschedule retransmissions to all neighbors */
 432                 for (ALL_LIST_ELEMENTS(oi->neighbor_list, node, nnode, on)) {
 433                         THREAD_OFF(on->thread_send_lsupdate);
 434                         on->thread_send_lsupdate = NULL;
 435                         thread_add_event(master, ospf6_lsupdate_send_neighbor,
 436                                          on, 0, &on->thread_send_lsupdate);
 437                 }
 438         }
 439 }
 440
 441 void ospf6_flood_area(struct ospf6_neighbor *from, struct ospf6_lsa *lsa,
 442                       struct ospf6_area *oa)
 443 {
 444         struct listnode *node, *nnode;
 445         struct ospf6_interface *oi;
 446
 447         for (ALL_LIST_ELEMENTS(oa->if_list, node, nnode, oi)) {
 448                 if (OSPF6_LSA_SCOPE(lsa->header->type) == OSPF6_SCOPE_LINKLOCAL
 449                     && oi != OSPF6_INTERFACE(lsa->lsdb->data))
 450                         continue;
 451
 452 #if 0
 453       if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_AS &&
 454           ospf6_is_interface_virtual_link (oi))
 455         continue;
 456 #endif /*0*/
 457
 458                 ospf6_flood_interface(from, lsa, oi);
 459         }
 460 }
 461
 462 static void ospf6_flood_process(struct ospf6_neighbor *from,
 463                                 struct ospf6_lsa *lsa, struct ospf6 *process)
 464 {
 465         struct listnode *node, *nnode;
 466         struct ospf6_area *oa;
 467
 468         for (ALL_LIST_ELEMENTS(process->area_list, node, nnode, oa)) {
 469                 if (OSPF6_LSA_SCOPE(lsa->header->type) == OSPF6_SCOPE_AREA
 470                     && oa != OSPF6_AREA(lsa->lsdb->data))
 471                         continue;
 472                 if (OSPF6_LSA_SCOPE(lsa->header->type) == OSPF6_SCOPE_LINKLOCAL
 473                     && oa != OSPF6_INTERFACE(lsa->lsdb->data)->area)
 474                         continue;
 475
 476                 if (ntohs(lsa->header->type) == OSPF6_LSTYPE_AS_EXTERNAL
 477                     && IS_AREA_STUB(oa))
 478                         continue;
 479
 480                 ospf6_flood_area(from, lsa, oa);
 481         }
 482 }
 483
 484 void ospf6_flood(struct ospf6_neighbor *from, struct ospf6_lsa *lsa)
 485 {
 486         ospf6_flood_process(from, lsa, ospf6);
 487 }
 488
 489 static void ospf6_flood_clear_interface(struct ospf6_lsa *lsa,
 490                                         struct ospf6_interface *oi)
 491 {
 492         struct listnode *node, *nnode;
 493         struct ospf6_neighbor *on;
 494         struct ospf6_lsa *rem;
 495
 496         for (ALL_LIST_ELEMENTS(oi->neighbor_list, node, nnode, on)) {
 497                 rem = ospf6_lsdb_lookup(lsa->header->type, lsa->header->id,
 498                                         lsa->header->adv_router,
 499                                         on->retrans_list);
 500                 if (rem && !ospf6_lsa_compare(rem, lsa)) {
 501                         if (IS_OSPF6_DEBUG_FLOODING
 502                             || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa->header->type))
 503                                 zlog_debug("Remove %s from retrans_list of %s",
 504                                            rem->name, on->name);
 505                         ospf6_decrement_retrans_count(rem);
 506                         ospf6_lsdb_remove(rem, on->retrans_list);
 507                 }
 508         }
 509 }
 510
 511 static void ospf6_flood_clear_area(struct ospf6_lsa *lsa, struct ospf6_area *oa)
 512 {
 513         struct listnode *node, *nnode;
 514         struct ospf6_interface *oi;
 515
 516         for (ALL_LIST_ELEMENTS(oa->if_list, node, nnode, oi)) {
 517                 if (OSPF6_LSA_SCOPE(lsa->header->type) == OSPF6_SCOPE_LINKLOCAL
 518                     && oi != OSPF6_INTERFACE(lsa->lsdb->data))
 519                         continue;
 520
 521 #if 0
 522       if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_AS &&
 523           ospf6_is_interface_virtual_link (oi))
 524         continue;
 525 #endif /*0*/
 526
 527                 ospf6_flood_clear_interface(lsa, oi);
 528         }
 529 }
 530
 531 static void ospf6_flood_clear_process(struct ospf6_lsa *lsa,
 532                                       struct ospf6 *process)
 533 {
 534         struct listnode *node, *nnode;
 535         struct ospf6_area *oa;
 536
 537         for (ALL_LIST_ELEMENTS(process->area_list, node, nnode, oa)) {
 538                 if (OSPF6_LSA_SCOPE(lsa->header->type) == OSPF6_SCOPE_AREA
 539                     && oa != OSPF6_AREA(lsa->lsdb->data))
 540                         continue;
 541                 if (OSPF6_LSA_SCOPE(lsa->header->type) == OSPF6_SCOPE_LINKLOCAL
 542                     && oa != OSPF6_INTERFACE(lsa->lsdb->data)->area)
 543                         continue;
 544
 545                 if (ntohs(lsa->header->type) == OSPF6_LSTYPE_AS_EXTERNAL
 546                     && IS_AREA_STUB(oa))
 547                         continue;
 548
 549                 ospf6_flood_clear_area(lsa, oa);
 550         }
 551 }
 552
 553 void ospf6_flood_clear(struct ospf6_lsa *lsa)
 554 {
 555         ospf6_flood_clear_process(lsa, ospf6);
 556 }
 557
 558
 559 /* RFC2328 13.5 (Table 19): Sending link state acknowledgements. */
 560 static void ospf6_acknowledge_lsa_bdrouter(struct ospf6_lsa *lsa,
 561                                            int ismore_recent,
 562                                            struct ospf6_neighbor *from)
 563 {
 564         struct ospf6_interface *oi;
 565         int is_debug = 0;
 566
 567         if (IS_OSPF6_DEBUG_FLOODING
 568             || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa->header->type))
 569                 is_debug++;
 570
 571         assert(from && from->ospf6_if);
 572         oi = from->ospf6_if;
 573
 574         /* LSA is more recent than database copy, but was not flooded
 575            back out receiving interface. Delayed acknowledgement sent
 576            if advertisement received from Designated Router,
 577            otherwide do nothing. */
 578         if (ismore_recent < 0) {
 579                 if (oi->drouter == from->router_id) {
 580                         if (is_debug)
 581                                 zlog_debug(
 582                                         "Delayed acknowledgement (BDR & MoreRecent & from DR)");
 583                         /* Delayed acknowledgement */
 584                         ospf6_lsdb_add(ospf6_lsa_copy(lsa), oi->lsack_list);
 585                         thread_add_timer(master, ospf6_lsack_send_interface, oi,
 586                                          3, &oi->thread_send_lsack);
 587                 } else {
 588                         if (is_debug)
 589                                 zlog_debug(
 590                                         "No acknowledgement (BDR & MoreRecent & ! from DR)");
 591                 }
 592                 return;
 593         }
 594
 595         /* LSA is a duplicate, and was treated as an implied acknowledgement.
 596            Delayed acknowledgement sent if advertisement received from
 597            Designated Router, otherwise do nothing */
 598         if (CHECK_FLAG(lsa->flag, OSPF6_LSA_DUPLICATE)
 599             && CHECK_FLAG(lsa->flag, OSPF6_LSA_IMPLIEDACK)) {
 600                 if (oi->drouter == from->router_id) {
 601                         if (is_debug)
 602                                 zlog_debug(
 603                                         "Delayed acknowledgement (BDR & Duplicate & ImpliedAck & from DR)");
 604                         /* Delayed acknowledgement */
 605                         ospf6_lsdb_add(ospf6_lsa_copy(lsa), oi->lsack_list);
 606                         thread_add_timer(master, ospf6_lsack_send_interface, oi,
 607                                          3, &oi->thread_send_lsack);
 608                 } else {
 609                         if (is_debug)
 610                                 zlog_debug(
 611                                         "No acknowledgement (BDR & Duplicate & ImpliedAck & ! from DR)");
 612                 }
 613                 return;
 614         }
 615
 616         /* LSA is a duplicate, and was not treated as an implied
 617            acknowledgement.
 618            Direct acknowledgement sent */
 619         if (CHECK_FLAG(lsa->flag, OSPF6_LSA_DUPLICATE)
 620             && !CHECK_FLAG(lsa->flag, OSPF6_LSA_IMPLIEDACK)) {
 621                 if (is_debug)
 622                         zlog_debug("Direct acknowledgement (BDR & Duplicate)");
 623                 ospf6_lsdb_add(ospf6_lsa_copy(lsa), from->lsack_list);
 624                 thread_add_event(master, ospf6_lsack_send_neighbor, from, 0,
 625                                  &from->thread_send_lsack);
 626                 return;
 627         }
 628
 629         /* LSA's LS age is equal to Maxage, and there is no current instance
 630            of the LSA in the link state database, and none of router's
 631            neighbors are in states Exchange or Loading */
 632         /* Direct acknowledgement sent, but this case is handled in
 633            early of ospf6_receive_lsa () */
 634 }
 635
 636 static void ospf6_acknowledge_lsa_allother(struct ospf6_lsa *lsa,
 637                                            int ismore_recent,
 638                                            struct ospf6_neighbor *from)
 639 {
 640         struct ospf6_interface *oi;
 641         int is_debug = 0;
 642
 643         if (IS_OSPF6_DEBUG_FLOODING
 644             || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa->header->type))
 645                 is_debug++;
 646
 647         assert(from && from->ospf6_if);
 648         oi = from->ospf6_if;
 649
 650         /* LSA has been flood back out receiving interface.
 651            No acknowledgement sent. */
 652         if (CHECK_FLAG(lsa->flag, OSPF6_LSA_FLOODBACK)) {
 653                 if (is_debug)
 654                         zlog_debug("No acknowledgement (AllOther & FloodBack)");
 655                 return;
 656         }
 657
 658         /* LSA is more recent than database copy, but was not flooded
 659            back out receiving interface. Delayed acknowledgement sent. */
 660         if (ismore_recent < 0) {
 661                 if (is_debug)
 662                         zlog_debug(
 663                                 "Delayed acknowledgement (AllOther & MoreRecent)");
 664                 /* Delayed acknowledgement */
 665                 ospf6_lsdb_add(ospf6_lsa_copy(lsa), oi->lsack_list);
 666                 thread_add_timer(master, ospf6_lsack_send_interface, oi, 3,
 667                                  &oi->thread_send_lsack);
 668                 return;
 669         }
 670
 671         /* LSA is a duplicate, and was treated as an implied acknowledgement.
 672            No acknowledgement sent. */
 673         if (CHECK_FLAG(lsa->flag, OSPF6_LSA_DUPLICATE)
 674             && CHECK_FLAG(lsa->flag, OSPF6_LSA_IMPLIEDACK)) {
 675                 if (is_debug)
 676                         zlog_debug(
 677                                 "No acknowledgement (AllOther & Duplicate & ImpliedAck)");
 678                 return;
 679         }
 680
 681         /* LSA is a duplicate, and was not treated as an implied
 682            acknowledgement.
 683            Direct acknowledgement sent */
 684         if (CHECK_FLAG(lsa->flag, OSPF6_LSA_DUPLICATE)
 685             && !CHECK_FLAG(lsa->flag, OSPF6_LSA_IMPLIEDACK)) {
 686                 if (is_debug)
 687                         zlog_debug(
 688                                 "Direct acknowledgement (AllOther & Duplicate)");
 689                 ospf6_lsdb_add(ospf6_lsa_copy(lsa), from->lsack_list);
 690                 thread_add_event(master, ospf6_lsack_send_neighbor, from, 0,
 691                                  &from->thread_send_lsack);
 692                 return;
 693         }
 694
 695         /* LSA's LS age is equal to Maxage, and there is no current instance
 696            of the LSA in the link state database, and none of router's
 697            neighbors are in states Exchange or Loading */
 698         /* Direct acknowledgement sent, but this case is handled in
 699            early of ospf6_receive_lsa () */
 700 }
 701
 702 static void ospf6_acknowledge_lsa(struct ospf6_lsa *lsa, int ismore_recent,
 703                                   struct ospf6_neighbor *from)
 704 {
 705         struct ospf6_interface *oi;
 706
 707         assert(from && from->ospf6_if);
 708         oi = from->ospf6_if;
 709
 710         if (oi->state == OSPF6_INTERFACE_BDR)
 711                 ospf6_acknowledge_lsa_bdrouter(lsa, ismore_recent, from);
 712         else
 713                 ospf6_acknowledge_lsa_allother(lsa, ismore_recent, from);
 714 }
 715
 716 /* RFC2328 section 13 (4):
 717    if MaxAge LSA and if we have no instance, and no neighbor
 718    is in states Exchange or Loading
 719    returns 1 if match this case, else returns 0 */
 720 static int ospf6_is_maxage_lsa_drop(struct ospf6_lsa *lsa,
 721                                     struct ospf6_neighbor *from)
 722 {
 723         struct ospf6_neighbor *on;
 724         struct ospf6_interface *oi;
 725         struct ospf6_area *oa;
 726         struct ospf6 *process = NULL;
 727         struct listnode *i, *j, *k;
 728         int count = 0;
 729
 730         if (!OSPF6_LSA_IS_MAXAGE(lsa))
 731                 return 0;
 732
 733         if (ospf6_lsdb_lookup(lsa->header->type, lsa->header->id,
 734                               lsa->header->adv_router, lsa->lsdb))
 735                 return 0;
 736
 737         process = from->ospf6_if->area->ospf6;
 738
 739         for (ALL_LIST_ELEMENTS_RO(process->area_list, i, oa))
 740                 for (ALL_LIST_ELEMENTS_RO(oa->if_list, j, oi))
 741                         for (ALL_LIST_ELEMENTS_RO(oi->neighbor_list, k, on))
 742                                 if (on->state == OSPF6_NEIGHBOR_EXCHANGE
 743                                     || on->state == OSPF6_NEIGHBOR_LOADING)
 744                                         count++;
 745
 746         if (count == 0)
 747                 return 1;
 748         return 0;
 749 }
 750
 751 /* RFC2328 section 13 The Flooding Procedure */
 752 void ospf6_receive_lsa(struct ospf6_neighbor *from,
 753                        struct ospf6_lsa_header *lsa_header)
 754 {
 755         struct ospf6_lsa *new = NULL, *old = NULL, *rem = NULL;
 756         int ismore_recent;
 757         int is_debug = 0;
 758         unsigned int time_delta_ms;
 759
 760         ismore_recent = 1;
 761         assert(from);
 762
 763         /* make lsa structure for received lsa */
 764         new = ospf6_lsa_create(lsa_header);
 765
 766         if (IS_OSPF6_DEBUG_FLOODING
 767             || IS_OSPF6_DEBUG_FLOOD_TYPE(new->header->type)) {
 768                 is_debug++;
 769                 zlog_debug("LSA Receive from %s", from->name);
 770                 ospf6_lsa_header_print(new);
 771         }
 772
 773         /* (1) LSA Checksum */
 774         if (!ospf6_lsa_checksum_valid(new->header)) {
 775                 if (is_debug)
 776                         zlog_debug("Wrong LSA Checksum, discard");
 777                 ospf6_lsa_delete(new);
 778                 return;
 779         }
 780
 781         /* (2) Examine the LSA's LS type.
 782            RFC2470 3.5.1. Receiving Link State Update packets  */
 783         if (IS_AREA_STUB(from->ospf6_if->area)
 784             && OSPF6_LSA_SCOPE(new->header->type) == OSPF6_SCOPE_AS) {
 785                 if (is_debug)
 786                         zlog_debug(
 787                                 "AS-External-LSA (or AS-scope LSA) in stub area, discard");
 788                 ospf6_lsa_delete(new);
 789                 return;
 790         }
 791
 792         /* (3) LSA which have reserved scope is discarded
 793            RFC2470 3.5.1. Receiving Link State Update packets  */
 794         /* Flooding scope check. LSAs with unknown scope are discarded here.
 795            Set appropriate LSDB for the LSA */
 796         switch (OSPF6_LSA_SCOPE(new->header->type)) {
 797         case OSPF6_SCOPE_LINKLOCAL:
 798                 new->lsdb = from->ospf6_if->lsdb;
 799                 break;
 800         case OSPF6_SCOPE_AREA:
 801                 new->lsdb = from->ospf6_if->area->lsdb;
 802                 break;
 803         case OSPF6_SCOPE_AS:
 804                 new->lsdb = from->ospf6_if->area->ospf6->lsdb;
 805                 break;
 806         default:
 807                 if (is_debug)
 808                         zlog_debug("LSA has reserved scope, discard");
 809                 ospf6_lsa_delete(new);
 810                 return;
 811         }
 812
 813         /* (4) if MaxAge LSA and if we have no instance, and no neighbor
 814                is in states Exchange or Loading */
 815         if (ospf6_is_maxage_lsa_drop(new, from)) {
 816                 /* log */
 817                 if (is_debug)
 818                         zlog_debug(
 819                                 "Drop MaxAge LSA with direct acknowledgement.");
 820
 821                 /* a) Acknowledge back to neighbor (Direct acknowledgement,
 822                  * 13.5) */
 823                 ospf6_lsdb_add(ospf6_lsa_copy(new), from->lsack_list);
 824                 thread_add_event(master, ospf6_lsack_send_neighbor, from, 0,
 825                                  &from->thread_send_lsack);
 826
 827                 /* b) Discard */
 828                 ospf6_lsa_delete(new);
 829                 return;
 830         }
 831
 832         /* (5) */
 833         /* lookup the same database copy in lsdb */
 834         old = ospf6_lsdb_lookup(new->header->type, new->header->id,
 835                                 new->header->adv_router, new->lsdb);
 836         if (old) {
 837                 ismore_recent = ospf6_lsa_compare(new, old);
 838                 if (ntohl(new->header->seqnum) == ntohl(old->header->seqnum)) {
 839                         if (is_debug)
 840                                 zlog_debug("Received is duplicated LSA");
 841                         SET_FLAG(new->flag, OSPF6_LSA_DUPLICATE);
 842                 }
 843                 if (old->header->adv_router
 844                             == from->ospf6_if->area->ospf6->router_id
 845                     && OSPF6_LSA_IS_MAXAGE(new)) {
 846                         ospf6_acknowledge_lsa(new, ismore_recent, from);
 847                         ospf6_lsa_delete(new);
 848                         if (is_debug)
 849                                 zlog_debug(
 850                                         "%s: Received is self orig MAXAGE LSA %s, discard (ismore_recent %d)",
 851                                         __PRETTY_FUNCTION__, old->name,
 852                                         ismore_recent);
 853                         return;
 854                 }
 855         }
 856
 857         /* if no database copy or received is more recent */
 858         if (old == NULL || ismore_recent < 0) {
 859                 /* in case we have no database copy */
 860                 ismore_recent = -1;
 861
 862                 /* (a) MinLSArrival check */
 863                 if (old) {
 864                         struct timeval now, res;
 865                         monotime(&now);
 866                         timersub(&now, &old->installed, &res);
 867                         time_delta_ms =
 868                                 (res.tv_sec * 1000) + (int)(res.tv_usec / 1000);
 869                         if (time_delta_ms
 870                             < from->ospf6_if->area->ospf6->lsa_minarrival) {
 871                                 if (is_debug)
 872                                         zlog_debug(
 873                                                 "LSA can't be updated within MinLSArrival, %dms < %dms, discard",
 874                                                 time_delta_ms,
 875                                                 from->ospf6_if->area->ospf6
 876                                                         ->lsa_minarrival);
 877                                 ospf6_lsa_delete(new);
 878                                 return; /* examin next lsa */
 879                         }
 880                 }
 881
 882                 monotime(&new->received);
 883
 884                 if (is_debug)
 885                         zlog_debug(
 886                                 "Install, Flood, Possibly acknowledge the received LSA");
 887
 888                 /* Remove older copies of this LSA from retx lists */
 889                 if (old)
 890                         ospf6_flood_clear(old);
 891
 892                 /* (b) immediately flood and (c) remove from all retrans-list */
 893                 /* Prevent self-originated LSA to be flooded. this is to make
 894                 reoriginated instance of the LSA not to be rejected by other
 895                 routers
 896                 due to MinLSArrival. */
 897                 if (new->header->adv_router
 898                     != from->ospf6_if->area->ospf6->router_id)
 899                         ospf6_flood(from, new);
 900
 901                 /* (d), installing lsdb, which may cause routing
 902                         table calculation (replacing database copy) */
 903                 ospf6_install_lsa(new);
 904
 905                 if (OSPF6_LSA_IS_MAXAGE(new))
 906                         ospf6_maxage_remove(from->ospf6_if->area->ospf6);
 907
 908                 /* (e) possibly acknowledge */
 909                 ospf6_acknowledge_lsa(new, ismore_recent, from);
 910
 911                 /* (f) Self Originated LSA, section 13.4 */
 912                 if (new->header->adv_router
 913                     == from->ospf6_if->area->ospf6->router_id) {
 914                         /* Self-originated LSA (newer than ours) is received
 915                            from
 916                            another router. We have to make a new instance of the
 917                            LSA
 918                            or have to flush this LSA. */
 919                         if (is_debug) {
 920                                 zlog_debug(
 921                                         "Newer instance of the self-originated LSA");
 922                                 zlog_debug("Schedule reorigination");
 923                         }
 924                         new->refresh = NULL;
 925                         thread_add_event(master, ospf6_lsa_refresh, new, 0,
 926                                          &new->refresh);
 927                 }
 928
 929                 return;
 930         }
 931
 932         /* (6) if there is instance on sending neighbor's request list */
 933         if (ospf6_lsdb_lookup(new->header->type, new->header->id,
 934                               new->header->adv_router, from->request_list)) {
 935                 /* if no database copy, should go above state (5) */
 936                 assert(old);
 937
 938                 if (is_debug) {
 939                         zlog_debug(
 940                                 "Received is not newer, on the neighbor's request-list");
 941                         zlog_debug("BadLSReq, discard the received LSA");
 942                 }
 943
 944                 /* BadLSReq */
 945                 thread_add_event(master, bad_lsreq, from, 0, NULL);
 946
 947                 ospf6_lsa_delete(new);
 948                 return;
 949         }
 950
 951         /* (7) if neither one is more recent */
 952         if (ismore_recent == 0) {
 953                 if (is_debug)
 954                         zlog_debug(
 955                                 "The same instance as database copy (neither recent)");
 956
 957                 /* (a) if on retrans-list, Treat this LSA as an Ack: Implied Ack
 958                  */
 959                 rem = ospf6_lsdb_lookup(new->header->type, new->header->id,
 960                                         new->header->adv_router,
 961                                         from->retrans_list);
 962                 if (rem) {
 963                         if (is_debug) {
 964                                 zlog_debug(
 965                                         "It is on the neighbor's retrans-list.");
 966                                 zlog_debug(
 967                                         "Treat as an Implied acknowledgement");
 968                         }
 969                         SET_FLAG(new->flag, OSPF6_LSA_IMPLIEDACK);
 970                         ospf6_decrement_retrans_count(rem);
 971                         ospf6_lsdb_remove(rem, from->retrans_list);
 972                 }
 973
 974                 if (is_debug)
 975                         zlog_debug("Possibly acknowledge and then discard");
 976
 977                 /* (b) possibly acknowledge */
 978                 ospf6_acknowledge_lsa(new, ismore_recent, from);
 979
 980                 ospf6_lsa_delete(new);
 981                 return;
 982         }
 983
 984         /* (8) previous database copy is more recent */
 985         {
 986                 assert(old);
 987
 988                 /* If database copy is in 'Seqnumber Wrapping',
 989                    simply discard the received LSA */
 990                 if (OSPF6_LSA_IS_MAXAGE(old)
 991                     && old->header->seqnum == htonl(OSPF_MAX_SEQUENCE_NUMBER)) {
 992                         if (is_debug) {
 993                                 zlog_debug("The LSA is in Seqnumber Wrapping");
 994                                 zlog_debug("MaxAge & MaxSeqNum, discard");
 995                         }
 996                         ospf6_lsa_delete(new);
 997                         return;
 998                 }
 999
1000                 /* Otherwise, Send database copy of this LSA to this neighbor */
1001                 {
1002                         if (is_debug) {
1003                                 zlog_debug("Database copy is more recent.");
1004                                 zlog_debug(
1005                                         "Send back directly and then discard");
1006                         }
1007
1008                         /* Neighbor router sent recent age for LSA,
1009                          * Router could be restarted while current copy is
1010                          * MAXAGEd and not removed.*/
1011                         if (OSPF6_LSA_IS_MAXAGE(old)
1012                             && !OSPF6_LSA_IS_MAXAGE(new)) {
1013
1014                                 if (is_debug)
1015                                         zlog_debug(
1016                                                 "%s: Current copy of LSA %s is MAXAGE, but new has recent Age.",
1017                                                 old->name, __PRETTY_FUNCTION__);
1018
1019                                 ospf6_lsa_purge(old);
1020                                 if (new->header->adv_router
1021                                     != from->ospf6_if->area->ospf6->router_id)
1022                                         ospf6_flood(from, new);
1023
1024                                 ospf6_install_lsa(new);
1025                                 return;
1026                         }
1027
1028                         /* XXX, MinLSArrival check !? RFC 2328 13 (8) */
1029
1030                         ospf6_lsdb_add(ospf6_lsa_copy(old),
1031                                        from->lsupdate_list);
1032                         thread_add_event(master, ospf6_lsupdate_send_neighbor,
1033                                          from, 0, &from->thread_send_lsupdate);
1034
1035                         ospf6_lsa_delete(new);
1036                         return;
1037                 }
1038                 return;
1039         }
1040 }
1041
1042 DEFUN (debug_ospf6_flooding,
1043        debug_ospf6_flooding_cmd,
1044        "debug ospf6 flooding",
1045        DEBUG_STR
1046        OSPF6_STR
1047        "Debug OSPFv3 flooding function\n"
1048       )
1049 {
1050         OSPF6_DEBUG_FLOODING_ON();
1051         return CMD_SUCCESS;
1052 }
1053
1054 DEFUN (no_debug_ospf6_flooding,
1055        no_debug_ospf6_flooding_cmd,
1056        "no debug ospf6 flooding",
1057        NO_STR
1058        DEBUG_STR
1059        OSPF6_STR
1060        "Debug OSPFv3 flooding function\n"
1061       )
1062 {
1063         OSPF6_DEBUG_FLOODING_OFF();
1064         return CMD_SUCCESS;
1065 }
1066
1067 int config_write_ospf6_debug_flood(struct vty *vty)
1068 {
1069         if (IS_OSPF6_DEBUG_FLOODING)
1070                 vty_out(vty, "debug ospf6 flooding\n");
1071         return 0;
1072 }
1073
1074 void install_element_ospf6_debug_flood(void)
1075 {
1076         install_element(ENABLE_NODE, &debug_ospf6_flooding_cmd);
1077         install_element(ENABLE_NODE, &no_debug_ospf6_flooding_cmd);
1078         install_element(CONFIG_NODE, &debug_ospf6_flooding_cmd);
1079         install_element(CONFIG_NODE, &no_debug_ospf6_flooding_cmd);
1080 }