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