Annotation of embedaddon/quagga/isisd/isis_spf.c, revision 1.1
1.1 ! misho 1: /*
! 2: * IS-IS Rout(e)ing protocol - isis_spf.c
! 3: * The SPT algorithm
! 4: *
! 5: * Copyright (C) 2001,2002 Sampo Saaristo
! 6: * Tampere University of Technology
! 7: * Institute of Communications Engineering
! 8: *
! 9: * This program is free software; you can redistribute it and/or modify it
! 10: * under the terms of the GNU General Public Licenseas published by the Free
! 11: * Software Foundation; either version 2 of the License, or (at your option)
! 12: * any later version.
! 13: *
! 14: * This program is distributed in the hope that it will be useful,but WITHOUT
! 15: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
! 16: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
! 17: * more details.
! 18:
! 19: * You should have received a copy of the GNU General Public License along
! 20: * with this program; if not, write to the Free Software Foundation, Inc.,
! 21: * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
! 22: */
! 23:
! 24: #include <zebra.h>
! 25:
! 26: #include "thread.h"
! 27: #include "linklist.h"
! 28: #include "vty.h"
! 29: #include "log.h"
! 30: #include "command.h"
! 31: #include "memory.h"
! 32: #include "prefix.h"
! 33: #include "hash.h"
! 34: #include "if.h"
! 35: #include "table.h"
! 36:
! 37: #include "isis_constants.h"
! 38: #include "isis_common.h"
! 39: #include "dict.h"
! 40: #include "isisd.h"
! 41: #include "isis_misc.h"
! 42: #include "isis_adjacency.h"
! 43: #include "isis_circuit.h"
! 44: #include "isis_tlv.h"
! 45: #include "isis_pdu.h"
! 46: #include "isis_lsp.h"
! 47: #include "isis_dynhn.h"
! 48: #include "isis_spf.h"
! 49: #include "isis_route.h"
! 50: #include "isis_csm.h"
! 51:
! 52: extern struct isis *isis;
! 53: extern struct thread_master *master;
! 54: extern struct host host;
! 55:
! 56: int isis_run_spf_l1 (struct thread *thread);
! 57: int isis_run_spf_l2 (struct thread *thread);
! 58:
! 59: /* 7.2.7 */
! 60: static void
! 61: remove_excess_adjs (struct list *adjs)
! 62: {
! 63: struct listnode *node, *excess = NULL;
! 64: struct isis_adjacency *adj, *candidate = NULL;
! 65: int comp;
! 66:
! 67: for (ALL_LIST_ELEMENTS_RO (adjs, node, adj))
! 68: {
! 69: if (excess == NULL)
! 70: excess = node;
! 71: candidate = listgetdata (excess);
! 72:
! 73: if (candidate->sys_type < adj->sys_type)
! 74: {
! 75: excess = node;
! 76: candidate = adj;
! 77: continue;
! 78: }
! 79: if (candidate->sys_type > adj->sys_type)
! 80: continue;
! 81:
! 82: comp = memcmp (candidate->sysid, adj->sysid, ISIS_SYS_ID_LEN);
! 83: if (comp > 0)
! 84: {
! 85: excess = node;
! 86: candidate = adj;
! 87: continue;
! 88: }
! 89: if (comp < 0)
! 90: continue;
! 91:
! 92: if (candidate->circuit->circuit_id > adj->circuit->circuit_id)
! 93: {
! 94: excess = node;
! 95: candidate = adj;
! 96: continue;
! 97: }
! 98:
! 99: if (candidate->circuit->circuit_id < adj->circuit->circuit_id)
! 100: continue;
! 101:
! 102: comp = memcmp (candidate->snpa, adj->snpa, ETH_ALEN);
! 103: if (comp > 0)
! 104: {
! 105: excess = node;
! 106: candidate = adj;
! 107: continue;
! 108: }
! 109: }
! 110:
! 111: list_delete_node (adjs, excess);
! 112:
! 113: return;
! 114: }
! 115:
! 116: #ifdef EXTREME_DEBUG
! 117: static const char *
! 118: vtype2string (enum vertextype vtype)
! 119: {
! 120: switch (vtype)
! 121: {
! 122: case VTYPE_PSEUDO_IS:
! 123: return "pseudo_IS";
! 124: break;
! 125: case VTYPE_PSEUDO_TE_IS:
! 126: return "pseudo_TE-IS";
! 127: break;
! 128: case VTYPE_NONPSEUDO_IS:
! 129: return "IS";
! 130: break;
! 131: case VTYPE_NONPSEUDO_TE_IS:
! 132: return "TE-IS";
! 133: break;
! 134: case VTYPE_ES:
! 135: return "ES";
! 136: break;
! 137: case VTYPE_IPREACH_INTERNAL:
! 138: return "IP internal";
! 139: break;
! 140: case VTYPE_IPREACH_EXTERNAL:
! 141: return "IP external";
! 142: break;
! 143: case VTYPE_IPREACH_TE:
! 144: return "IP TE";
! 145: break;
! 146: #ifdef HAVE_IPV6
! 147: case VTYPE_IP6REACH_INTERNAL:
! 148: return "IP6 internal";
! 149: break;
! 150: case VTYPE_IP6REACH_EXTERNAL:
! 151: return "IP6 external";
! 152: break;
! 153: #endif /* HAVE_IPV6 */
! 154: default:
! 155: return "UNKNOWN";
! 156: }
! 157: return NULL; /* Not reached */
! 158: }
! 159:
! 160: static const char *
! 161: vid2string (struct isis_vertex *vertex, u_char * buff)
! 162: {
! 163: switch (vertex->type)
! 164: {
! 165: case VTYPE_PSEUDO_IS:
! 166: case VTYPE_PSEUDO_TE_IS:
! 167: return rawlspid_print (vertex->N.id);
! 168: break;
! 169: case VTYPE_NONPSEUDO_IS:
! 170: case VTYPE_NONPSEUDO_TE_IS:
! 171: case VTYPE_ES:
! 172: return sysid_print (vertex->N.id);
! 173: break;
! 174: case VTYPE_IPREACH_INTERNAL:
! 175: case VTYPE_IPREACH_EXTERNAL:
! 176: case VTYPE_IPREACH_TE:
! 177: #ifdef HAVE_IPV6
! 178: case VTYPE_IP6REACH_INTERNAL:
! 179: case VTYPE_IP6REACH_EXTERNAL:
! 180: #endif /* HAVE_IPV6 */
! 181: prefix2str ((struct prefix *) &vertex->N.prefix, (char *) buff, BUFSIZ);
! 182: break;
! 183: default:
! 184: return "UNKNOWN";
! 185: }
! 186:
! 187: return (char *) buff;
! 188: }
! 189: #endif /* EXTREME_DEBUG */
! 190:
! 191: static struct isis_spftree *
! 192: isis_spftree_new ()
! 193: {
! 194: struct isis_spftree *tree;
! 195:
! 196: tree = XCALLOC (MTYPE_ISIS_SPFTREE, sizeof (struct isis_spftree));
! 197: if (tree == NULL)
! 198: {
! 199: zlog_err ("ISIS-Spf: isis_spftree_new Out of memory!");
! 200: return NULL;
! 201: }
! 202:
! 203: tree->tents = list_new ();
! 204: tree->paths = list_new ();
! 205: return tree;
! 206: }
! 207:
! 208: static void
! 209: isis_vertex_del (struct isis_vertex *vertex)
! 210: {
! 211: list_delete (vertex->Adj_N);
! 212:
! 213: XFREE (MTYPE_ISIS_VERTEX, vertex);
! 214:
! 215: return;
! 216: }
! 217:
! 218: #if 0 /* HT: Not used yet. */
! 219: static void
! 220: isis_spftree_del (struct isis_spftree *spftree)
! 221: {
! 222: spftree->tents->del = (void (*)(void *)) isis_vertex_del;
! 223: list_delete (spftree->tents);
! 224:
! 225: spftree->paths->del = (void (*)(void *)) isis_vertex_del;
! 226: list_delete (spftree->paths);
! 227:
! 228: XFREE (MTYPE_ISIS_SPFTREE, spftree);
! 229:
! 230: return;
! 231: }
! 232: #endif
! 233:
! 234: void
! 235: spftree_area_init (struct isis_area *area)
! 236: {
! 237: if ((area->is_type & IS_LEVEL_1) && area->spftree[0] == NULL)
! 238: {
! 239: area->spftree[0] = isis_spftree_new ();
! 240: #ifdef HAVE_IPV6
! 241: area->spftree6[0] = isis_spftree_new ();
! 242: #endif
! 243:
! 244: /* thread_add_timer (master, isis_run_spf_l1, area,
! 245: isis_jitter (PERIODIC_SPF_INTERVAL, 10)); */
! 246: }
! 247:
! 248: if ((area->is_type & IS_LEVEL_2) && area->spftree[1] == NULL)
! 249: {
! 250: area->spftree[1] = isis_spftree_new ();
! 251: #ifdef HAVE_IPV6
! 252: area->spftree6[1] = isis_spftree_new ();
! 253: #endif
! 254: /* thread_add_timer (master, isis_run_spf_l2, area,
! 255: isis_jitter (PERIODIC_SPF_INTERVAL, 10)); */
! 256: }
! 257:
! 258: return;
! 259: }
! 260:
! 261: static struct isis_vertex *
! 262: isis_vertex_new (void *id, enum vertextype vtype)
! 263: {
! 264: struct isis_vertex *vertex;
! 265:
! 266: vertex = XCALLOC (MTYPE_ISIS_VERTEX, sizeof (struct isis_vertex));
! 267: if (vertex == NULL)
! 268: {
! 269: zlog_err ("isis_vertex_new Out of memory!");
! 270: return NULL;
! 271: }
! 272:
! 273: vertex->type = vtype;
! 274: switch (vtype)
! 275: {
! 276: case VTYPE_ES:
! 277: case VTYPE_NONPSEUDO_IS:
! 278: case VTYPE_NONPSEUDO_TE_IS:
! 279: memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN);
! 280: break;
! 281: case VTYPE_PSEUDO_IS:
! 282: case VTYPE_PSEUDO_TE_IS:
! 283: memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN + 1);
! 284: break;
! 285: case VTYPE_IPREACH_INTERNAL:
! 286: case VTYPE_IPREACH_EXTERNAL:
! 287: case VTYPE_IPREACH_TE:
! 288: #ifdef HAVE_IPV6
! 289: case VTYPE_IP6REACH_INTERNAL:
! 290: case VTYPE_IP6REACH_EXTERNAL:
! 291: #endif /* HAVE_IPV6 */
! 292: memcpy (&vertex->N.prefix, (struct prefix *) id,
! 293: sizeof (struct prefix));
! 294: break;
! 295: default:
! 296: zlog_err ("WTF!");
! 297: }
! 298:
! 299: vertex->Adj_N = list_new ();
! 300:
! 301: return vertex;
! 302: }
! 303:
! 304: /*
! 305: * Add this IS to the root of SPT
! 306: */
! 307: static void
! 308: isis_spf_add_self (struct isis_spftree *spftree, struct isis_area *area,
! 309: int level)
! 310: {
! 311: struct isis_vertex *vertex;
! 312: struct isis_lsp *lsp;
! 313: u_char lspid[ISIS_SYS_ID_LEN + 2];
! 314: #ifdef EXTREME_DEBUG
! 315: u_char buff[BUFSIZ];
! 316: #endif /* EXTREME_DEBUG */
! 317: memcpy (lspid, isis->sysid, ISIS_SYS_ID_LEN);
! 318: LSP_PSEUDO_ID (lspid) = 0;
! 319: LSP_FRAGMENT (lspid) = 0;
! 320:
! 321: lsp = lsp_search (lspid, area->lspdb[level - 1]);
! 322:
! 323: if (lsp == NULL)
! 324: zlog_warn ("ISIS-Spf: could not find own l%d LSP!", level);
! 325:
! 326: if (!area->oldmetric)
! 327: vertex = isis_vertex_new (isis->sysid, VTYPE_NONPSEUDO_TE_IS);
! 328: else
! 329: vertex = isis_vertex_new (isis->sysid, VTYPE_NONPSEUDO_IS);
! 330:
! 331: vertex->lsp = lsp;
! 332:
! 333: listnode_add (spftree->paths, vertex);
! 334:
! 335: #ifdef EXTREME_DEBUG
! 336: zlog_debug ("ISIS-Spf: added this IS %s %s depth %d dist %d to PATHS",
! 337: vtype2string (vertex->type), vid2string (vertex, buff),
! 338: vertex->depth, vertex->d_N);
! 339: #endif /* EXTREME_DEBUG */
! 340:
! 341: return;
! 342: }
! 343:
! 344: static struct isis_vertex *
! 345: isis_find_vertex (struct list *list, void *id, enum vertextype vtype)
! 346: {
! 347: struct listnode *node;
! 348: struct isis_vertex *vertex;
! 349: struct prefix *p1, *p2;
! 350:
! 351: for (ALL_LIST_ELEMENTS_RO (list, node, vertex))
! 352: {
! 353: if (vertex->type != vtype)
! 354: continue;
! 355: switch (vtype)
! 356: {
! 357: case VTYPE_ES:
! 358: case VTYPE_NONPSEUDO_IS:
! 359: case VTYPE_NONPSEUDO_TE_IS:
! 360: if (memcmp ((u_char *) id, vertex->N.id, ISIS_SYS_ID_LEN) == 0)
! 361: return vertex;
! 362: break;
! 363: case VTYPE_PSEUDO_IS:
! 364: case VTYPE_PSEUDO_TE_IS:
! 365: if (memcmp ((u_char *) id, vertex->N.id, ISIS_SYS_ID_LEN + 1) == 0)
! 366: return vertex;
! 367: break;
! 368: case VTYPE_IPREACH_INTERNAL:
! 369: case VTYPE_IPREACH_EXTERNAL:
! 370: case VTYPE_IPREACH_TE:
! 371: #ifdef HAVE_IPV6
! 372: case VTYPE_IP6REACH_INTERNAL:
! 373: case VTYPE_IP6REACH_EXTERNAL:
! 374: #endif /* HAVE_IPV6 */
! 375: p1 = (struct prefix *) id;
! 376: p2 = (struct prefix *) &vertex->N.id;
! 377: if (p1->family == p2->family && p1->prefixlen == p2->prefixlen &&
! 378: memcmp (&p1->u.prefix, &p2->u.prefix,
! 379: PSIZE (p1->prefixlen)) == 0)
! 380: return vertex;
! 381: break;
! 382: }
! 383: }
! 384:
! 385: return NULL;
! 386: }
! 387:
! 388: /*
! 389: * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
! 390: */
! 391: static struct isis_vertex *
! 392: isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype,
! 393: void *id, struct isis_adjacency *adj, u_int32_t cost,
! 394: int depth, int family)
! 395: {
! 396: struct isis_vertex *vertex, *v;
! 397: struct listnode *node;
! 398: #ifdef EXTREME_DEBUG
! 399: u_char buff[BUFSIZ];
! 400: #endif
! 401:
! 402: vertex = isis_vertex_new (id, vtype);
! 403: vertex->d_N = cost;
! 404: vertex->depth = depth;
! 405:
! 406: if (adj)
! 407: listnode_add (vertex->Adj_N, adj);
! 408: #ifdef EXTREME_DEBUG
! 409: zlog_debug ("ISIS-Spf: add to TENT %s %s depth %d dist %d",
! 410: vtype2string (vertex->type), vid2string (vertex, buff),
! 411: vertex->depth, vertex->d_N);
! 412: #endif /* EXTREME_DEBUG */
! 413: listnode_add (spftree->tents, vertex);
! 414: if (list_isempty (spftree->tents))
! 415: {
! 416: listnode_add (spftree->tents, vertex);
! 417: return vertex;
! 418: }
! 419:
! 420: /* XXX: This cant use the standard ALL_LIST_ELEMENT macro */
! 421: for (node = listhead (spftree->tents); node; node = listnextnode (node))
! 422: {
! 423: v = listgetdata (node);
! 424: if (v->d_N > vertex->d_N)
! 425: {
! 426: list_add_node_prev (spftree->tents, node, vertex);
! 427: break;
! 428: }
! 429: else if (v->d_N == vertex->d_N)
! 430: {
! 431: /* Tie break, add according to type */
! 432: while (v && v->d_N == vertex->d_N && v->type > vertex->type)
! 433: {
! 434: if (v->type > vertex->type)
! 435: {
! 436: break;
! 437: }
! 438: /* XXX: this seems dubious, node is the loop iterator */
! 439: node = listnextnode (node);
! 440: (node) ? (v = listgetdata (node)) : (v = NULL);
! 441: }
! 442: list_add_node_prev (spftree->tents, node, vertex);
! 443: break;
! 444: }
! 445: else if (node->next == NULL)
! 446: {
! 447: list_add_node_next (spftree->tents, node, vertex);
! 448: break;
! 449: }
! 450: }
! 451: return vertex;
! 452: }
! 453:
! 454: static struct isis_vertex *
! 455: isis_spf_add_local (struct isis_spftree *spftree, enum vertextype vtype,
! 456: void *id, struct isis_adjacency *adj, u_int32_t cost,
! 457: int family)
! 458: {
! 459: struct isis_vertex *vertex;
! 460:
! 461: vertex = isis_find_vertex (spftree->tents, id, vtype);
! 462:
! 463: if (vertex)
! 464: {
! 465: /* C.2.5 c) */
! 466: if (vertex->d_N == cost)
! 467: {
! 468: if (adj)
! 469: listnode_add (vertex->Adj_N, adj);
! 470: /* d) */
! 471: if (listcount (vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
! 472: remove_excess_adjs (vertex->Adj_N);
! 473: }
! 474: /* f) */
! 475: else if (vertex->d_N > cost)
! 476: {
! 477: listnode_delete (spftree->tents, vertex);
! 478: goto add2tent;
! 479: }
! 480: /* e) do nothing */
! 481: return vertex;
! 482: }
! 483:
! 484: add2tent:
! 485: return isis_spf_add2tent (spftree, vtype, id, adj, cost, 1, family);
! 486: }
! 487:
! 488: static void
! 489: process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id,
! 490: u_int16_t dist, u_int16_t depth, struct isis_adjacency *adj,
! 491: int family)
! 492: {
! 493: struct isis_vertex *vertex;
! 494: #ifdef EXTREME_DEBUG
! 495: u_char buff[255];
! 496: #endif
! 497:
! 498: /* C.2.6 b) */
! 499: if (dist > MAX_PATH_METRIC)
! 500: return;
! 501: /* c) */
! 502: vertex = isis_find_vertex (spftree->paths, id, vtype);
! 503: if (vertex)
! 504: {
! 505: #ifdef EXTREME_DEBUG
! 506: zlog_debug ("ISIS-Spf: process_N %s %s dist %d already found from PATH",
! 507: vtype2string (vtype), vid2string (vertex, buff), dist);
! 508: #endif /* EXTREME_DEBUG */
! 509: assert (dist >= vertex->d_N);
! 510: return;
! 511: }
! 512:
! 513: vertex = isis_find_vertex (spftree->tents, id, vtype);
! 514: /* d) */
! 515: if (vertex)
! 516: {
! 517: /* 1) */
! 518: #ifdef EXTREME_DEBUG
! 519: zlog_debug ("ISIS-Spf: process_N %s %s dist %d",
! 520: vtype2string (vtype), vid2string (vertex, buff), dist);
! 521: #endif /* EXTREME_DEBUG */
! 522: if (vertex->d_N == dist)
! 523: {
! 524: if (adj)
! 525: listnode_add (vertex->Adj_N, adj);
! 526: /* 2) */
! 527: if (listcount (vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
! 528: remove_excess_adjs (vertex->Adj_N);
! 529: /* 3) */
! 530: return;
! 531: }
! 532: else if (vertex->d_N < dist)
! 533: {
! 534: return;
! 535: /* 4) */
! 536: }
! 537: else
! 538: {
! 539: listnode_delete (spftree->tents, vertex);
! 540: }
! 541: }
! 542:
! 543: isis_spf_add2tent (spftree, vtype, id, adj, dist, depth, family);
! 544: return;
! 545: }
! 546:
! 547: /*
! 548: * C.2.6 Step 1
! 549: */
! 550: static int
! 551: isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp,
! 552: uint32_t cost, uint16_t depth, int family)
! 553: {
! 554: struct listnode *node, *fragnode = NULL;
! 555: u_int16_t dist;
! 556: struct is_neigh *is_neigh;
! 557: struct te_is_neigh *te_is_neigh;
! 558: struct ipv4_reachability *ipreach;
! 559: struct te_ipv4_reachability *te_ipv4_reach;
! 560: enum vertextype vtype;
! 561: struct prefix prefix;
! 562: #ifdef HAVE_IPV6
! 563: struct ipv6_reachability *ip6reach;
! 564: #endif /* HAVE_IPV6 */
! 565:
! 566:
! 567: if (!lsp->adj)
! 568: return ISIS_WARNING;
! 569: if (lsp->tlv_data.nlpids == NULL || !speaks (lsp->tlv_data.nlpids, family))
! 570: return ISIS_OK;
! 571:
! 572: lspfragloop:
! 573: if (lsp->lsp_header->seq_num == 0)
! 574: {
! 575: zlog_warn ("isis_spf_process_lsp(): lsp with 0 seq_num"
! 576: " - do not process");
! 577: return ISIS_WARNING;
! 578: }
! 579:
! 580: if (!ISIS_MASK_LSP_OL_BIT (lsp->lsp_header->lsp_bits))
! 581: {
! 582: if (lsp->tlv_data.is_neighs)
! 583: {
! 584: for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.is_neighs, node, is_neigh))
! 585: {
! 586: /* C.2.6 a) */
! 587: /* Two way connectivity */
! 588: if (!memcmp (is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
! 589: continue;
! 590: dist = cost + is_neigh->metrics.metric_default;
! 591: vtype = LSP_PSEUDO_ID (is_neigh->neigh_id) ? VTYPE_PSEUDO_IS
! 592: : VTYPE_NONPSEUDO_IS;
! 593: process_N (spftree, vtype, (void *) is_neigh->neigh_id, dist,
! 594: depth + 1, lsp->adj, family);
! 595: }
! 596: }
! 597: if (lsp->tlv_data.te_is_neighs)
! 598: {
! 599: for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_is_neighs, node,
! 600: te_is_neigh))
! 601: {
! 602: uint32_t metric;
! 603: if (!memcmp (te_is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
! 604: continue;
! 605: memcpy (&metric, te_is_neigh->te_metric, 3);
! 606: dist = cost + ntohl (metric << 8);
! 607: vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
! 608: : VTYPE_NONPSEUDO_TE_IS;
! 609: process_N (spftree, vtype, (void *) te_is_neigh->neigh_id, dist,
! 610: depth + 1, lsp->adj, family);
! 611: }
! 612: }
! 613: if (family == AF_INET && lsp->tlv_data.ipv4_int_reachs)
! 614: {
! 615: prefix.family = AF_INET;
! 616: for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv4_int_reachs,
! 617: node, ipreach))
! 618: {
! 619: dist = cost + ipreach->metrics.metric_default;
! 620: vtype = VTYPE_IPREACH_INTERNAL;
! 621: prefix.u.prefix4 = ipreach->prefix;
! 622: prefix.prefixlen = ip_masklen (ipreach->mask);
! 623: process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
! 624: lsp->adj, family);
! 625: }
! 626: }
! 627:
! 628: if (family == AF_INET && lsp->tlv_data.ipv4_ext_reachs)
! 629: {
! 630: prefix.family = AF_INET;
! 631: for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv4_ext_reachs,
! 632: node, ipreach))
! 633: {
! 634: dist = cost + ipreach->metrics.metric_default;
! 635: vtype = VTYPE_IPREACH_EXTERNAL;
! 636: prefix.u.prefix4 = ipreach->prefix;
! 637: prefix.prefixlen = ip_masklen (ipreach->mask);
! 638: process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
! 639: lsp->adj, family);
! 640: }
! 641: }
! 642: if (family == AF_INET && lsp->tlv_data.te_ipv4_reachs)
! 643: {
! 644: prefix.family = AF_INET;
! 645: for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_ipv4_reachs,
! 646: node, te_ipv4_reach))
! 647: {
! 648: dist = cost + ntohl (te_ipv4_reach->te_metric);
! 649: vtype = VTYPE_IPREACH_TE;
! 650: prefix.u.prefix4 = newprefix2inaddr (&te_ipv4_reach->prefix_start,
! 651: te_ipv4_reach->control);
! 652: prefix.prefixlen = (te_ipv4_reach->control & 0x3F);
! 653: process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
! 654: lsp->adj, family);
! 655: }
! 656: }
! 657: #ifdef HAVE_IPV6
! 658: if (family == AF_INET6 && lsp->tlv_data.ipv6_reachs)
! 659: {
! 660: prefix.family = AF_INET6;
! 661: for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv6_reachs,
! 662: node, ip6reach))
! 663: {
! 664: dist = cost + ip6reach->metric;
! 665: vtype = (ip6reach->control_info & CTRL_INFO_DISTRIBUTION) ?
! 666: VTYPE_IP6REACH_EXTERNAL : VTYPE_IP6REACH_INTERNAL;
! 667: prefix.prefixlen = ip6reach->prefix_len;
! 668: memcpy (&prefix.u.prefix6.s6_addr, ip6reach->prefix,
! 669: PSIZE (ip6reach->prefix_len));
! 670: process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
! 671: lsp->adj, family);
! 672: }
! 673: }
! 674: #endif /* HAVE_IPV6 */
! 675: }
! 676:
! 677: if (fragnode == NULL)
! 678: fragnode = listhead (lsp->lspu.frags);
! 679: else
! 680: fragnode = listnextnode (fragnode);
! 681:
! 682: if (fragnode)
! 683: {
! 684: lsp = listgetdata (fragnode);
! 685: goto lspfragloop;
! 686: }
! 687:
! 688: return ISIS_OK;
! 689: }
! 690:
! 691: static int
! 692: isis_spf_process_pseudo_lsp (struct isis_spftree *spftree,
! 693: struct isis_lsp *lsp, uint16_t cost,
! 694: uint16_t depth, int family)
! 695: {
! 696: struct listnode *node, *fragnode = NULL;
! 697: struct is_neigh *is_neigh;
! 698: struct te_is_neigh *te_is_neigh;
! 699: enum vertextype vtype;
! 700:
! 701: pseudofragloop:
! 702:
! 703: if (lsp->lsp_header->seq_num == 0)
! 704: {
! 705: zlog_warn ("isis_spf_process_pseudo_lsp(): lsp with 0 seq_num"
! 706: " - do not process");
! 707: return ISIS_WARNING;
! 708: }
! 709:
! 710: if (lsp->tlv_data.is_neighs)
! 711: for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.is_neighs, node, is_neigh))
! 712: {
! 713: vtype = LSP_PSEUDO_ID (is_neigh->neigh_id) ? VTYPE_PSEUDO_IS
! 714: : VTYPE_NONPSEUDO_IS;
! 715: /* Two way connectivity */
! 716: if (!memcmp (is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
! 717: continue;
! 718: if (isis_find_vertex
! 719: (spftree->tents, (void *) is_neigh->neigh_id, vtype) == NULL
! 720: && isis_find_vertex (spftree->paths, (void *) is_neigh->neigh_id,
! 721: vtype) == NULL)
! 722: {
! 723: /* C.2.5 i) */
! 724: isis_spf_add2tent (spftree, vtype, is_neigh->neigh_id, lsp->adj,
! 725: cost, depth, family);
! 726: }
! 727: }
! 728: if (lsp->tlv_data.te_is_neighs)
! 729: for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_is_neighs, node, te_is_neigh))
! 730: {
! 731: vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
! 732: : VTYPE_NONPSEUDO_TE_IS;
! 733: /* Two way connectivity */
! 734: if (!memcmp (te_is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
! 735: continue;
! 736: if (isis_find_vertex
! 737: (spftree->tents, (void *) te_is_neigh->neigh_id, vtype) == NULL
! 738: && isis_find_vertex (spftree->paths, (void *) te_is_neigh->neigh_id,
! 739: vtype) == NULL)
! 740: {
! 741: /* C.2.5 i) */
! 742: isis_spf_add2tent (spftree, vtype, te_is_neigh->neigh_id, lsp->adj,
! 743: cost, depth, family);
! 744: }
! 745: }
! 746:
! 747: if (fragnode == NULL)
! 748: fragnode = listhead (lsp->lspu.frags);
! 749: else
! 750: fragnode = listnextnode (fragnode);
! 751:
! 752: if (fragnode)
! 753: {
! 754: lsp = listgetdata (fragnode);
! 755: goto pseudofragloop;
! 756: }
! 757:
! 758: return ISIS_OK;
! 759: }
! 760:
! 761: static int
! 762: isis_spf_preload_tent (struct isis_spftree *spftree,
! 763: struct isis_area *area, int level, int family)
! 764: {
! 765: struct isis_vertex *vertex;
! 766: struct isis_circuit *circuit;
! 767: struct listnode *cnode, *anode, *ipnode;
! 768: struct isis_adjacency *adj;
! 769: struct isis_lsp *lsp;
! 770: struct list *adj_list;
! 771: struct list *adjdb;
! 772: struct prefix_ipv4 *ipv4;
! 773: struct prefix prefix;
! 774: int retval = ISIS_OK;
! 775: u_char lsp_id[ISIS_SYS_ID_LEN + 2];
! 776: #ifdef HAVE_IPV6
! 777: struct prefix_ipv6 *ipv6;
! 778: #endif /* HAVE_IPV6 */
! 779:
! 780: for (ALL_LIST_ELEMENTS_RO (area->circuit_list, cnode, circuit))
! 781: {
! 782: if (circuit->state != C_STATE_UP)
! 783: continue;
! 784: if (!(circuit->circuit_is_type & level))
! 785: continue;
! 786: if (family == AF_INET && !circuit->ip_router)
! 787: continue;
! 788: #ifdef HAVE_IPV6
! 789: if (family == AF_INET6 && !circuit->ipv6_router)
! 790: continue;
! 791: #endif /* HAVE_IPV6 */
! 792: /*
! 793: * Add IP(v6) addresses of this circuit
! 794: */
! 795: if (family == AF_INET)
! 796: {
! 797: prefix.family = AF_INET;
! 798: for (ALL_LIST_ELEMENTS_RO (circuit->ip_addrs, ipnode, ipv4))
! 799: {
! 800: prefix.u.prefix4 = ipv4->prefix;
! 801: prefix.prefixlen = ipv4->prefixlen;
! 802: isis_spf_add_local (spftree, VTYPE_IPREACH_INTERNAL, &prefix,
! 803: NULL, 0, family);
! 804: }
! 805: }
! 806: #ifdef HAVE_IPV6
! 807: if (family == AF_INET6)
! 808: {
! 809: prefix.family = AF_INET6;
! 810: for (ALL_LIST_ELEMENTS_RO (circuit->ipv6_non_link, ipnode, ipv6))
! 811: {
! 812: prefix.prefixlen = ipv6->prefixlen;
! 813: prefix.u.prefix6 = ipv6->prefix;
! 814: isis_spf_add_local (spftree, VTYPE_IP6REACH_INTERNAL,
! 815: &prefix, NULL, 0, family);
! 816: }
! 817: }
! 818: #endif /* HAVE_IPV6 */
! 819: if (circuit->circ_type == CIRCUIT_T_BROADCAST)
! 820: {
! 821: /*
! 822: * Add the adjacencies
! 823: */
! 824: adj_list = list_new ();
! 825: adjdb = circuit->u.bc.adjdb[level - 1];
! 826: isis_adj_build_up_list (adjdb, adj_list);
! 827: if (listcount (adj_list) == 0)
! 828: {
! 829: list_delete (adj_list);
! 830: if (isis->debugs & DEBUG_SPF_EVENTS)
! 831: zlog_debug ("ISIS-Spf: no L%d adjacencies on circuit %s",
! 832: level, circuit->interface->name);
! 833: continue;
! 834: }
! 835: anode = listhead (adj_list);
! 836: while (anode)
! 837: {
! 838: adj = listgetdata (anode);
! 839: if (!speaks (&adj->nlpids, family))
! 840: {
! 841: anode = listnextnode (anode);
! 842: continue;
! 843: }
! 844: switch (adj->sys_type)
! 845: {
! 846: case ISIS_SYSTYPE_ES:
! 847: isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj,
! 848: circuit->te_metric[level - 1], family);
! 849: break;
! 850: case ISIS_SYSTYPE_IS:
! 851: case ISIS_SYSTYPE_L1_IS:
! 852: case ISIS_SYSTYPE_L2_IS:
! 853: vertex =
! 854: isis_spf_add_local (spftree, VTYPE_NONPSEUDO_IS,
! 855: adj->sysid, adj,
! 856: circuit->te_metric[level - 1], family);
! 857: memcpy (lsp_id, adj->sysid, ISIS_SYS_ID_LEN);
! 858: LSP_PSEUDO_ID (lsp_id) = 0;
! 859: LSP_FRAGMENT (lsp_id) = 0;
! 860: lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
! 861: if (!lsp)
! 862: zlog_warn ("No lsp found for IS adjacency");
! 863: /* else {
! 864: isis_spf_process_lsp (spftree, lsp, vertex->d_N, 1, family);
! 865: } */
! 866: break;
! 867: case ISIS_SYSTYPE_UNKNOWN:
! 868: default:
! 869: zlog_warn ("isis_spf_preload_tent unknow adj type");
! 870: }
! 871: anode = listnextnode (anode);
! 872: }
! 873: list_delete (adj_list);
! 874: /*
! 875: * Add the pseudonode
! 876: */
! 877: if (level == 1)
! 878: memcpy (lsp_id, circuit->u.bc.l1_desig_is, ISIS_SYS_ID_LEN + 1);
! 879: else
! 880: memcpy (lsp_id, circuit->u.bc.l2_desig_is, ISIS_SYS_ID_LEN + 1);
! 881: lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
! 882: adj = isis_adj_lookup (lsp_id, adjdb);
! 883: /* if no adj, we are the dis or error */
! 884: if (!adj && !circuit->u.bc.is_dr[level - 1])
! 885: {
! 886: zlog_warn ("ISIS-Spf: No adjacency found for DR");
! 887: }
! 888: if (lsp == NULL || lsp->lsp_header->rem_lifetime == 0)
! 889: {
! 890: zlog_warn ("ISIS-Spf: No lsp found for DR");
! 891: }
! 892: else
! 893: {
! 894: isis_spf_process_pseudo_lsp (spftree, lsp,
! 895: circuit->te_metric[level - 1], 0, family);
! 896:
! 897: }
! 898: }
! 899: else if (circuit->circ_type == CIRCUIT_T_P2P)
! 900: {
! 901: adj = circuit->u.p2p.neighbor;
! 902: if (!adj)
! 903: continue;
! 904: switch (adj->sys_type)
! 905: {
! 906: case ISIS_SYSTYPE_ES:
! 907: isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj,
! 908: circuit->te_metric[level - 1], family);
! 909: break;
! 910: case ISIS_SYSTYPE_IS:
! 911: case ISIS_SYSTYPE_L1_IS:
! 912: case ISIS_SYSTYPE_L2_IS:
! 913: if (speaks (&adj->nlpids, family))
! 914: isis_spf_add_local (spftree, VTYPE_NONPSEUDO_IS, adj->sysid,
! 915: adj, circuit->te_metric[level - 1],
! 916: family);
! 917: break;
! 918: case ISIS_SYSTYPE_UNKNOWN:
! 919: default:
! 920: zlog_warn ("isis_spf_preload_tent unknow adj type");
! 921: break;
! 922: }
! 923: }
! 924: else
! 925: {
! 926: zlog_warn ("isis_spf_preload_tent unsupported media");
! 927: retval = ISIS_WARNING;
! 928: }
! 929:
! 930: }
! 931:
! 932: return retval;
! 933: }
! 934:
! 935: /*
! 936: * The parent(s) for vertex is set when added to TENT list
! 937: * now we just put the child pointer(s) in place
! 938: */
! 939: static void
! 940: add_to_paths (struct isis_spftree *spftree, struct isis_vertex *vertex,
! 941: struct isis_area *area, int level)
! 942: {
! 943: #ifdef EXTREME_DEBUG
! 944: u_char buff[BUFSIZ];
! 945: #endif /* EXTREME_DEBUG */
! 946: listnode_add (spftree->paths, vertex);
! 947:
! 948: #ifdef EXTREME_DEBUG
! 949: zlog_debug ("ISIS-Spf: added %s %s depth %d dist %d to PATHS",
! 950: vtype2string (vertex->type), vid2string (vertex, buff),
! 951: vertex->depth, vertex->d_N);
! 952: #endif /* EXTREME_DEBUG */
! 953: if (vertex->type > VTYPE_ES)
! 954: {
! 955: if (listcount (vertex->Adj_N) > 0)
! 956: isis_route_create ((struct prefix *) &vertex->N.prefix, vertex->d_N,
! 957: vertex->depth, vertex->Adj_N, area, level);
! 958: else if (isis->debugs & DEBUG_SPF_EVENTS)
! 959: zlog_debug ("ISIS-Spf: no adjacencies do not install route");
! 960: }
! 961:
! 962: return;
! 963: }
! 964:
! 965: static void
! 966: init_spt (struct isis_spftree *spftree)
! 967: {
! 968: spftree->tents->del = spftree->paths->del = (void (*)(void *)) isis_vertex_del;
! 969: list_delete_all_node (spftree->tents);
! 970: list_delete_all_node (spftree->paths);
! 971: spftree->tents->del = spftree->paths->del = NULL;
! 972:
! 973: return;
! 974: }
! 975:
! 976: static int
! 977: isis_run_spf (struct isis_area *area, int level, int family)
! 978: {
! 979: int retval = ISIS_OK;
! 980: struct listnode *node;
! 981: struct isis_vertex *vertex;
! 982: struct isis_spftree *spftree = NULL;
! 983: u_char lsp_id[ISIS_SYS_ID_LEN + 2];
! 984: struct isis_lsp *lsp;
! 985: struct route_table *table = NULL;
! 986: struct route_node *rode;
! 987: struct isis_route_info *rinfo;
! 988:
! 989: if (family == AF_INET)
! 990: spftree = area->spftree[level - 1];
! 991: #ifdef HAVE_IPV6
! 992: else if (family == AF_INET6)
! 993: spftree = area->spftree6[level - 1];
! 994: #endif
! 995:
! 996: assert (spftree);
! 997:
! 998: /* Make all routes in current route table inactive. */
! 999: if (family == AF_INET)
! 1000: table = area->route_table[level - 1];
! 1001: #ifdef HAVE_IPV6
! 1002: else if (family == AF_INET6)
! 1003: table = area->route_table6[level - 1];
! 1004: #endif
! 1005:
! 1006: for (rode = route_top (table); rode; rode = route_next (rode))
! 1007: {
! 1008: if (rode->info == NULL)
! 1009: continue;
! 1010: rinfo = rode->info;
! 1011:
! 1012: UNSET_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
! 1013: }
! 1014:
! 1015: /*
! 1016: * C.2.5 Step 0
! 1017: */
! 1018: init_spt (spftree);
! 1019: /* a) */
! 1020: isis_spf_add_self (spftree, area, level);
! 1021: /* b) */
! 1022: retval = isis_spf_preload_tent (spftree, area, level, family);
! 1023:
! 1024: /*
! 1025: * C.2.7 Step 2
! 1026: */
! 1027: if (listcount (spftree->tents) == 0)
! 1028: {
! 1029: zlog_warn ("ISIS-Spf: TENT is empty");
! 1030: goto out;
! 1031: }
! 1032:
! 1033: while (listcount (spftree->tents) > 0)
! 1034: {
! 1035: node = listhead (spftree->tents);
! 1036: vertex = listgetdata (node);
! 1037: /* Remove from tent list */
! 1038: list_delete_node (spftree->tents, node);
! 1039: if (isis_find_vertex (spftree->paths, vertex->N.id, vertex->type))
! 1040: continue;
! 1041: add_to_paths (spftree, vertex, area, level);
! 1042: if (vertex->type == VTYPE_PSEUDO_IS ||
! 1043: vertex->type == VTYPE_NONPSEUDO_IS)
! 1044: {
! 1045: memcpy (lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1);
! 1046: LSP_FRAGMENT (lsp_id) = 0;
! 1047: lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
! 1048: if (lsp)
! 1049: {
! 1050: if (LSP_PSEUDO_ID (lsp_id))
! 1051: {
! 1052: isis_spf_process_pseudo_lsp (spftree, lsp, vertex->d_N,
! 1053: vertex->depth, family);
! 1054:
! 1055: }
! 1056: else
! 1057: {
! 1058: isis_spf_process_lsp (spftree, lsp, vertex->d_N,
! 1059: vertex->depth, family);
! 1060: }
! 1061: }
! 1062: else
! 1063: {
! 1064: zlog_warn ("ISIS-Spf: No LSP found for %s",
! 1065: rawlspid_print (lsp_id));
! 1066: }
! 1067: }
! 1068: }
! 1069:
! 1070: out:
! 1071: thread_add_event (master, isis_route_validate, area, 0);
! 1072: spftree->lastrun = time (NULL);
! 1073: spftree->pending = 0;
! 1074:
! 1075: return retval;
! 1076: }
! 1077:
! 1078: int
! 1079: isis_run_spf_l1 (struct thread *thread)
! 1080: {
! 1081: struct isis_area *area;
! 1082: int retval = ISIS_OK;
! 1083:
! 1084: area = THREAD_ARG (thread);
! 1085: assert (area);
! 1086:
! 1087: area->spftree[0]->t_spf = NULL;
! 1088:
! 1089: if (!(area->is_type & IS_LEVEL_1))
! 1090: {
! 1091: if (isis->debugs & DEBUG_SPF_EVENTS)
! 1092: zlog_warn ("ISIS-SPF (%s) area does not share level",
! 1093: area->area_tag);
! 1094: return ISIS_WARNING;
! 1095: }
! 1096:
! 1097: if (isis->debugs & DEBUG_SPF_EVENTS)
! 1098: zlog_debug ("ISIS-Spf (%s) L1 SPF needed, periodic SPF", area->area_tag);
! 1099:
! 1100: if (area->ip_circuits)
! 1101: retval = isis_run_spf (area, 1, AF_INET);
! 1102:
! 1103: THREAD_TIMER_ON (master, area->spftree[0]->t_spf, isis_run_spf_l1, area,
! 1104: isis_jitter (PERIODIC_SPF_INTERVAL, 10));
! 1105:
! 1106: return retval;
! 1107: }
! 1108:
! 1109: int
! 1110: isis_run_spf_l2 (struct thread *thread)
! 1111: {
! 1112: struct isis_area *area;
! 1113: int retval = ISIS_OK;
! 1114:
! 1115: area = THREAD_ARG (thread);
! 1116: assert (area);
! 1117:
! 1118: area->spftree[1]->t_spf = NULL;
! 1119:
! 1120: if (!(area->is_type & IS_LEVEL_2))
! 1121: {
! 1122: if (isis->debugs & DEBUG_SPF_EVENTS)
! 1123: zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
! 1124: return ISIS_WARNING;
! 1125: }
! 1126:
! 1127: if (isis->debugs & DEBUG_SPF_EVENTS)
! 1128: zlog_debug ("ISIS-Spf (%s) L2 SPF needed, periodic SPF", area->area_tag);
! 1129:
! 1130: if (area->ip_circuits)
! 1131: retval = isis_run_spf (area, 2, AF_INET);
! 1132:
! 1133: THREAD_TIMER_ON (master, area->spftree[1]->t_spf, isis_run_spf_l2, area,
! 1134: isis_jitter (PERIODIC_SPF_INTERVAL, 10));
! 1135:
! 1136: return retval;
! 1137: }
! 1138:
! 1139: int
! 1140: isis_spf_schedule (struct isis_area *area, int level)
! 1141: {
! 1142: int retval = ISIS_OK;
! 1143: struct isis_spftree *spftree = area->spftree[level - 1];
! 1144: time_t diff, now = time (NULL);
! 1145:
! 1146: if (spftree->pending)
! 1147: return retval;
! 1148:
! 1149: diff = now - spftree->lastrun;
! 1150:
! 1151: /* FIXME: let's wait a minute before doing the SPF */
! 1152: if (now - isis->uptime < 60 || isis->uptime == 0)
! 1153: {
! 1154: if (level == 1)
! 1155: THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area, 60);
! 1156: else
! 1157: THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area, 60);
! 1158:
! 1159: spftree->pending = 1;
! 1160: return retval;
! 1161: }
! 1162:
! 1163: THREAD_TIMER_OFF (spftree->t_spf);
! 1164:
! 1165: if (diff < MINIMUM_SPF_INTERVAL)
! 1166: {
! 1167: if (level == 1)
! 1168: THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area,
! 1169: MINIMUM_SPF_INTERVAL - diff);
! 1170: else
! 1171: THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area,
! 1172: MINIMUM_SPF_INTERVAL - diff);
! 1173:
! 1174: spftree->pending = 1;
! 1175: }
! 1176: else
! 1177: {
! 1178: spftree->pending = 0;
! 1179: retval = isis_run_spf (area, level, AF_INET);
! 1180: if (level == 1)
! 1181: THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area,
! 1182: isis_jitter (PERIODIC_SPF_INTERVAL, 10));
! 1183: else
! 1184: THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area,
! 1185: isis_jitter (PERIODIC_SPF_INTERVAL, 10));
! 1186: }
! 1187:
! 1188: return retval;
! 1189: }
! 1190:
! 1191: #ifdef HAVE_IPV6
! 1192: static int
! 1193: isis_run_spf6_l1 (struct thread *thread)
! 1194: {
! 1195: struct isis_area *area;
! 1196: int retval = ISIS_OK;
! 1197:
! 1198: area = THREAD_ARG (thread);
! 1199: assert (area);
! 1200:
! 1201: area->spftree6[0]->t_spf = NULL;
! 1202:
! 1203: if (!(area->is_type & IS_LEVEL_1))
! 1204: {
! 1205: if (isis->debugs & DEBUG_SPF_EVENTS)
! 1206: zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
! 1207: return ISIS_WARNING;
! 1208: }
! 1209:
! 1210: if (isis->debugs & DEBUG_SPF_EVENTS)
! 1211: zlog_debug ("ISIS-Spf (%s) L1 SPF needed, periodic SPF", area->area_tag);
! 1212:
! 1213: if (area->ipv6_circuits)
! 1214: retval = isis_run_spf (area, 1, AF_INET6);
! 1215:
! 1216: THREAD_TIMER_ON (master, area->spftree6[0]->t_spf, isis_run_spf6_l1, area,
! 1217: isis_jitter (PERIODIC_SPF_INTERVAL, 10));
! 1218:
! 1219: return retval;
! 1220: }
! 1221:
! 1222: static int
! 1223: isis_run_spf6_l2 (struct thread *thread)
! 1224: {
! 1225: struct isis_area *area;
! 1226: int retval = ISIS_OK;
! 1227:
! 1228: area = THREAD_ARG (thread);
! 1229: assert (area);
! 1230:
! 1231: area->spftree6[1]->t_spf = NULL;
! 1232:
! 1233: if (!(area->is_type & IS_LEVEL_2))
! 1234: {
! 1235: if (isis->debugs & DEBUG_SPF_EVENTS)
! 1236: zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
! 1237: return ISIS_WARNING;
! 1238: }
! 1239:
! 1240: if (isis->debugs & DEBUG_SPF_EVENTS)
! 1241: zlog_debug ("ISIS-Spf (%s) L2 SPF needed, periodic SPF.", area->area_tag);
! 1242:
! 1243: if (area->ipv6_circuits)
! 1244: retval = isis_run_spf (area, 2, AF_INET6);
! 1245:
! 1246: THREAD_TIMER_ON (master, area->spftree6[1]->t_spf, isis_run_spf6_l2, area,
! 1247: isis_jitter (PERIODIC_SPF_INTERVAL, 10));
! 1248:
! 1249: return retval;
! 1250: }
! 1251:
! 1252: int
! 1253: isis_spf_schedule6 (struct isis_area *area, int level)
! 1254: {
! 1255: int retval = ISIS_OK;
! 1256: struct isis_spftree *spftree = area->spftree6[level - 1];
! 1257: time_t diff, now = time (NULL);
! 1258:
! 1259: if (spftree->pending)
! 1260: return retval;
! 1261:
! 1262: diff = now - spftree->lastrun;
! 1263:
! 1264: /* FIXME: let's wait a minute before doing the SPF */
! 1265: if (now - isis->uptime < 60 || isis->uptime == 0)
! 1266: {
! 1267: if (level == 1)
! 1268: THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area, 60);
! 1269: else
! 1270: THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area, 60);
! 1271:
! 1272: spftree->pending = 1;
! 1273: return retval;
! 1274: }
! 1275:
! 1276: THREAD_TIMER_OFF (spftree->t_spf);
! 1277:
! 1278: if (diff < MINIMUM_SPF_INTERVAL)
! 1279: {
! 1280: if (level == 1)
! 1281: THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area,
! 1282: MINIMUM_SPF_INTERVAL - diff);
! 1283: else
! 1284: THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area,
! 1285: MINIMUM_SPF_INTERVAL - diff);
! 1286:
! 1287: spftree->pending = 1;
! 1288: }
! 1289: else
! 1290: {
! 1291: spftree->pending = 0;
! 1292: retval = isis_run_spf (area, level, AF_INET6);
! 1293:
! 1294: if (level == 1)
! 1295: THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area,
! 1296: isis_jitter (PERIODIC_SPF_INTERVAL, 10));
! 1297: else
! 1298: THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area,
! 1299: isis_jitter (PERIODIC_SPF_INTERVAL, 10));
! 1300: }
! 1301:
! 1302: return retval;
! 1303: }
! 1304: #endif
! 1305:
! 1306: static void
! 1307: isis_print_paths (struct vty *vty, struct list *paths)
! 1308: {
! 1309: struct listnode *node;
! 1310: struct isis_vertex *vertex;
! 1311: struct isis_dynhn *dyn, *nh_dyn = NULL;
! 1312: struct isis_adjacency *adj;
! 1313: #if 0
! 1314: u_char buff[255];
! 1315: #endif /* 0 */
! 1316:
! 1317: vty_out (vty, "System Id Metric Next-Hop"
! 1318: " Interface SNPA%s", VTY_NEWLINE);
! 1319:
! 1320: for (ALL_LIST_ELEMENTS_RO (paths, node, vertex))
! 1321: {
! 1322: if (vertex->type != VTYPE_NONPSEUDO_IS)
! 1323: continue;
! 1324: if (memcmp (vertex->N.id, isis->sysid, ISIS_SYS_ID_LEN) == 0)
! 1325: {
! 1326: vty_out (vty, "%s --%s", host.name?host.name:"",
! 1327: VTY_NEWLINE);
! 1328: }
! 1329: else
! 1330: {
! 1331: dyn = dynhn_find_by_id ((u_char *) vertex->N.id);
! 1332: adj = listgetdata (listhead (vertex->Adj_N));
! 1333: if (adj)
! 1334: {
! 1335: nh_dyn = dynhn_find_by_id (adj->sysid);
! 1336: vty_out (vty, "%-20s %-10u %-20s %-11s %-5s%s",
! 1337: (dyn != NULL) ? dyn->name.name :
! 1338: (const u_char *)rawlspid_print ((u_char *) vertex->N.id),
! 1339: vertex->d_N, (nh_dyn != NULL) ? nh_dyn->name.name :
! 1340: (const u_char *)rawlspid_print (adj->sysid),
! 1341: adj->circuit->interface->name,
! 1342: snpa_print (adj->snpa), VTY_NEWLINE);
! 1343: }
! 1344: else
! 1345: {
! 1346: vty_out (vty, "%s %u %s", dyn ? dyn->name.name :
! 1347: (const u_char *) rawlspid_print (vertex->N.id),
! 1348: vertex->d_N, VTY_NEWLINE);
! 1349: }
! 1350: }
! 1351: #if 0
! 1352: vty_out (vty, "%s %s %u %s", vtype2string (vertex->type),
! 1353: vid2string (vertex, buff), vertex->d_N, VTY_NEWLINE);
! 1354: #endif
! 1355: }
! 1356: }
! 1357:
! 1358: DEFUN (show_isis_topology,
! 1359: show_isis_topology_cmd,
! 1360: "show isis topology",
! 1361: SHOW_STR
! 1362: "IS-IS information\n"
! 1363: "IS-IS paths to Intermediate Systems\n")
! 1364: {
! 1365: struct listnode *node;
! 1366: struct isis_area *area;
! 1367: int level;
! 1368:
! 1369: if (!isis->area_list || isis->area_list->count == 0)
! 1370: return CMD_SUCCESS;
! 1371:
! 1372: for (ALL_LIST_ELEMENTS_RO (isis->area_list, node, area))
! 1373: {
! 1374: vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
! 1375: VTY_NEWLINE);
! 1376:
! 1377: for (level = 0; level < ISIS_LEVELS; level++)
! 1378: {
! 1379: if (area->ip_circuits > 0 && area->spftree[level]
! 1380: && area->spftree[level]->paths->count > 0)
! 1381: {
! 1382: vty_out (vty, "IS-IS paths to level-%d routers that speak IP%s",
! 1383: level + 1, VTY_NEWLINE);
! 1384: isis_print_paths (vty, area->spftree[level]->paths);
! 1385: }
! 1386: #ifdef HAVE_IPV6
! 1387: if (area->ipv6_circuits > 0 && area->spftree6[level]
! 1388: && area->spftree6[level]->paths->count > 0)
! 1389: {
! 1390: vty_out (vty,
! 1391: "IS-IS paths to level-%d routers that speak IPv6%s",
! 1392: level + 1, VTY_NEWLINE);
! 1393: isis_print_paths (vty, area->spftree6[level]->paths);
! 1394: }
! 1395: #endif /* HAVE_IPV6 */
! 1396: }
! 1397: }
! 1398:
! 1399: return CMD_SUCCESS;
! 1400: }
! 1401:
! 1402: DEFUN (show_isis_topology_l1,
! 1403: show_isis_topology_l1_cmd,
! 1404: "show isis topology level-1",
! 1405: SHOW_STR
! 1406: "IS-IS information\n"
! 1407: "IS-IS paths to Intermediate Systems\n"
! 1408: "Paths to all level-1 routers in the area\n")
! 1409: {
! 1410: struct listnode *node;
! 1411: struct isis_area *area;
! 1412:
! 1413: if (!isis->area_list || isis->area_list->count == 0)
! 1414: return CMD_SUCCESS;
! 1415:
! 1416: for (ALL_LIST_ELEMENTS_RO (isis->area_list, node, area))
! 1417: {
! 1418: vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
! 1419: VTY_NEWLINE);
! 1420:
! 1421: if (area->ip_circuits > 0 && area->spftree[0]
! 1422: && area->spftree[0]->paths->count > 0)
! 1423: {
! 1424: vty_out (vty, "IS-IS paths to level-1 routers that speak IP%s",
! 1425: VTY_NEWLINE);
! 1426: isis_print_paths (vty, area->spftree[0]->paths);
! 1427: }
! 1428: #ifdef HAVE_IPV6
! 1429: if (area->ipv6_circuits > 0 && area->spftree6[0]
! 1430: && area->spftree6[0]->paths->count > 0)
! 1431: {
! 1432: vty_out (vty, "IS-IS paths to level-1 routers that speak IPv6%s",
! 1433: VTY_NEWLINE);
! 1434: isis_print_paths (vty, area->spftree6[0]->paths);
! 1435: }
! 1436: #endif /* HAVE_IPV6 */
! 1437: }
! 1438:
! 1439: return CMD_SUCCESS;
! 1440: }
! 1441:
! 1442: DEFUN (show_isis_topology_l2,
! 1443: show_isis_topology_l2_cmd,
! 1444: "show isis topology level-2",
! 1445: SHOW_STR
! 1446: "IS-IS information\n"
! 1447: "IS-IS paths to Intermediate Systems\n"
! 1448: "Paths to all level-2 routers in the domain\n")
! 1449: {
! 1450: struct listnode *node;
! 1451: struct isis_area *area;
! 1452:
! 1453: if (!isis->area_list || isis->area_list->count == 0)
! 1454: return CMD_SUCCESS;
! 1455:
! 1456: for (ALL_LIST_ELEMENTS_RO (isis->area_list, node, area))
! 1457: {
! 1458: vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
! 1459: VTY_NEWLINE);
! 1460:
! 1461: if (area->ip_circuits > 0 && area->spftree[1]
! 1462: && area->spftree[1]->paths->count > 0)
! 1463: {
! 1464: vty_out (vty, "IS-IS paths to level-2 routers that speak IP%s",
! 1465: VTY_NEWLINE);
! 1466: isis_print_paths (vty, area->spftree[1]->paths);
! 1467: }
! 1468: #ifdef HAVE_IPV6
! 1469: if (area->ipv6_circuits > 0 && area->spftree6[1]
! 1470: && area->spftree6[1]->paths->count > 0)
! 1471: {
! 1472: vty_out (vty, "IS-IS paths to level-2 routers that speak IPv6%s",
! 1473: VTY_NEWLINE);
! 1474: isis_print_paths (vty, area->spftree6[1]->paths);
! 1475: }
! 1476: #endif /* HAVE_IPV6 */
! 1477: }
! 1478:
! 1479: return CMD_SUCCESS;
! 1480: }
! 1481:
! 1482: void
! 1483: isis_spf_cmds_init ()
! 1484: {
! 1485: install_element (VIEW_NODE, &show_isis_topology_cmd);
! 1486: install_element (VIEW_NODE, &show_isis_topology_l1_cmd);
! 1487: install_element (VIEW_NODE, &show_isis_topology_l2_cmd);
! 1488:
! 1489: install_element (ENABLE_NODE, &show_isis_topology_cmd);
! 1490: install_element (ENABLE_NODE, &show_isis_topology_l1_cmd);
! 1491: install_element (ENABLE_NODE, &show_isis_topology_l2_cmd);
! 1492: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to isis_spf.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 / isisd