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