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