ospf6d/ospf6_flood.c

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