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