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