]> git.proxmox.com Git - mirror_frr.git/blob - isisd/isis_spf.c
projects / mirror_frr.git / blob
? search:


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