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