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