]> git.proxmox.com Git - mirror_frr.git/blame - isisd/isis_spf.c
projects / mirror_frr.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Initial revision
[mirror_frr.git] / isisd / isis_spf.c
CommitLineData
eb5d44eb 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 *
9 * This program is free software; you can redistribute it and/or modify it
10 * under the terms of the GNU General Public Licenseas published by the Free
11 * Software Foundation; either version 2 of the License, or (at your option)
12 * any later version.
13 *
14 * This program is distributed in the hope that it will be useful,but WITHOUT
15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
17 * more details.
18
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write to the Free Software Foundation, Inc.,
21 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22 */
23
24#include <stdlib.h>
25#include <stdio.h>
26#include <zebra.h>
27#include <net/ethernet.h>
28
29#include "thread.h"
30#include "linklist.h"
31#include "vty.h"
32#include "log.h"
33#include "command.h"
34#include "memory.h"
35#include "prefix.h"
36#include "hash.h"
37#include "if.h"
38#include "table.h"
39
40#include "isis_constants.h"
41#include "isis_common.h"
42#include "dict.h"
43#include "isisd.h"
44#include "isis_misc.h"
45#include "isis_adjacency.h"
46#include "isis_circuit.h"
47#include "isis_tlv.h"
48#include "isis_pdu.h"
49#include "isis_lsp.h"
50#include "isis_dynhn.h"
51#include "isis_spf.h"
52#include "isis_route.h"
53#include "isis_csm.h"
54
55extern struct isis *isis;
56extern struct thread_master *master;
57extern struct host host;
58
59int isis_run_spf_l1 (struct thread *thread);
60int isis_run_spf_l2 (struct thread *thread);
61
62/* performace issue ???? */
63void
64union_adjlist( struct list *target, struct list *source )
65{
66 struct isis_adjacency *adj, *adj2;
67 struct listnode *node, *node2;
68
69 zlog_info ("Union adjlist!");
70 for (node = listhead (source); node; nextnode (node)) {
71 adj = getdata (node);
72
73 /* lookup adjacency in the source list */
74 for (node2 = listhead (target); node2; nextnode (node2)) {
75 adj2 = getdata(node2);
76 if (adj == adj2) break;
77 }
78
79 if (!node2) listnode_add (target, adj);
80 }
81}
82
83
84/* 7.2.7 */
85void
86remove_excess_adjs (struct list *adjs)
87{
88 struct listnode *node, *excess = NULL;
89 struct isis_adjacency *adj, *candidate = NULL;
90 int comp;
91
92 for (node = listhead (adjs); node; nextnode (node)) {
93 if (excess == NULL)
94 excess = node;
95 candidate = getdata (excess);
96 adj = getdata (node);
97 if (candidate->sys_type < adj->sys_type) {
98 excess = node;
99 candidate = adj;
100 continue;
101 }
102 if (candidate->sys_type > adj->sys_type)
103 continue;
104
105 comp = memcmp (candidate->sysid, adj->sysid, ISIS_SYS_ID_LEN);
106 if (comp > 0) {
107 excess = node;
108 candidate = adj;
109 continue;
110 }
111 if (comp < 0)
112 continue;
113
114 if (candidate->circuit->circuit_id > adj->circuit->circuit_id) {
115 excess = node;
116 candidate = adj;
117 continue;
118 }
119
120 if (candidate->circuit->circuit_id < adj->circuit->circuit_id)
121 continue;
122
123 comp = memcmp (candidate->snpa, adj->snpa, ETH_ALEN);
124 if (comp > 0) {
125 excess = node;
126 candidate = adj;
127 continue;
128 }
129 }
130
131 list_delete_node (adjs, excess);
132
133 return;
134}
135
136const char *
137vtype2string (enum vertextype vtype)
138{
139 switch (vtype) {
140 case VTYPE_PSEUDO_IS:
141 return "pseudo_IS";
142 break;
143 case VTYPE_NONPSEUDO_IS:
144 return "IS";
145 break;
146 case VTYPE_ES:
147 return "ES";
148 break;
149 case VTYPE_IPREACH_INTERNAL:
150 return "IP internal";
151 break;
152 case VTYPE_IPREACH_EXTERNAL:
153 return "IP external";
154 break;
155#ifdef HAVE_IPV6
156 case VTYPE_IP6REACH_INTERNAL:
157 return "IP6 internal";
158 break;
159 case VTYPE_IP6REACH_EXTERNAL:
160 return "IP6 external";
161 break;
162#endif /* HAVE_IPV6 */
163 default:
164 return "UNKNOWN";
165 }
166 return NULL; /* Not reached */
167}
168
169char *
170vid2string (struct isis_vertex *vertex, u_char *buff)
171{
172 switch (vertex->type) {
173 case VTYPE_PSEUDO_IS:
174 return rawlspid_print (vertex->N.id);
175 break;
176 case VTYPE_NONPSEUDO_IS:
177 case VTYPE_ES:
178 return sysid_print (vertex->N.id);
179 break;
180 case VTYPE_IPREACH_INTERNAL:
181 case VTYPE_IPREACH_EXTERNAL:
182#ifdef HAVE_IPV6
183 case VTYPE_IP6REACH_INTERNAL:
184 case VTYPE_IP6REACH_EXTERNAL:
185#endif /* HAVE_IPV6 */
186 prefix2str ((struct prefix *)&vertex->N.prefix, buff, BUFSIZ);
187 break;
188 default:
189 return "UNKNOWN";
190 }
191
192 return buff;
193}
194
195struct isis_spftree *
196isis_spftree_new ()
197{
198 struct isis_spftree *tree;
199
200 tree = XMALLOC (MTYPE_ISIS_SPFTREE, sizeof (struct isis_spftree));
201 if (tree == NULL) {
202 zlog_err ("ISIS-Spf: isis_spftree_new Out of memory!");
203 return NULL;
204 }
205 memset (tree, 0, sizeof (struct isis_spftree));
206
207 tree->tents = list_new ();
208 tree->paths = list_new ();
209 return tree;
210}
211
212void
213isis_vertex_del (struct isis_vertex *vertex)
214{
215
216 list_delete (vertex->Adj_N);
217
218 XFREE (MTYPE_ISIS_VERTEX, vertex);
219
220 return;
221}
222
223void
224isis_spftree_del (struct isis_spftree *spftree)
225{
226
227 spftree->tents->del = (void *)isis_vertex_del;
228 list_delete (spftree->tents);
229
230 spftree->paths->del = (void *)isis_vertex_del;
231 list_delete (spftree->paths);
232
233 XFREE (MTYPE_ISIS_SPFTREE, spftree);
234
235 return;
236}
237
238void
239spftree_area_init (struct isis_area *area)
240{
241
242 if ((area->is_type & IS_LEVEL_1) && area->spftree[0] == NULL) {
243 area->spftree[0] = isis_spftree_new ();
244#ifdef HAVE_IPV6
245 area->spftree6[0] = isis_spftree_new ();
246#endif
247
248 /* thread_add_timer (master, isis_run_spf_l1, area,
249 isis_jitter (PERIODIC_SPF_INTERVAL, 10)); */
250 }
251
252 if ((area->is_type & IS_LEVEL_2) && area->spftree[1] == NULL) {
253 area->spftree[1] = isis_spftree_new ();
254#ifdef HAVE_IPV6
255 area->spftree6[1] = isis_spftree_new ();
256#endif
257 /* thread_add_timer (master, isis_run_spf_l2, area,
258 isis_jitter (PERIODIC_SPF_INTERVAL, 10)); */
259 }
260
261 return;
262}
263
264struct isis_vertex *
265isis_vertex_new (void *id, enum vertextype vtype)
266{
267 struct isis_vertex *vertex;
268
269 vertex = XMALLOC (MTYPE_ISIS_VERTEX, sizeof (struct isis_vertex));
270 if (vertex == NULL) {
271 zlog_err ("isis_vertex_new Out of memory!");
272 return NULL;
273 }
274
275 memset (vertex, 0, sizeof (struct isis_vertex));
276 vertex->type = vtype;
277 switch (vtype) {
278 case VTYPE_ES:
279 case VTYPE_NONPSEUDO_IS:
280 memcpy (vertex->N.id, (u_char *)id, ISIS_SYS_ID_LEN);
281 break;
282 case VTYPE_PSEUDO_IS:
283 memcpy (vertex->N.id, (u_char *)id, ISIS_SYS_ID_LEN + 1);
284 break;
285 case VTYPE_IPREACH_INTERNAL:
286 case VTYPE_IPREACH_EXTERNAL:
287#ifdef HAVE_IPV6
288 case VTYPE_IP6REACH_INTERNAL:
289 case VTYPE_IP6REACH_EXTERNAL:
290#endif /* HAVE_IPV6 */
291 memcpy (&vertex->N.prefix, (struct prefix *)id,
292 sizeof (struct prefix));
293 break;
294 default:
295 zlog_err ("WTF!");
296 }
297
298 vertex->Adj_N = list_new ();
299
300 return vertex;
301}
302
303/*
304 * Add this IS to the root of SPT
305 */
306void
307isis_spf_add_self (struct isis_spftree *spftree, struct isis_area *area,
308 int level)
309{
310 struct isis_vertex *vertex;
311 struct isis_lsp *lsp;
312 u_char lspid[ISIS_SYS_ID_LEN + 2];
313#ifdef EXTREME_DEBUG
314 u_char buff[BUFSIZ];
315#endif /* EXTREME_DEBUG */
316 memcpy (lspid, isis->sysid, ISIS_SYS_ID_LEN);
317 LSP_PSEUDO_ID(lspid) = 0;
318 LSP_FRAGMENT(lspid) = 0;
319
320 lsp = lsp_search (lspid, area->lspdb[level - 1]);
321
322 if (lsp == NULL)
323 zlog_warn ("ISIS-Spf: could not find own l%d LSP!", level);
324
325 vertex = isis_vertex_new (isis->sysid, VTYPE_NONPSEUDO_IS);
326 vertex->lsp = lsp;
327
328 listnode_add (spftree->paths, vertex);
329
330#ifdef EXTREME_DEBUG
331 zlog_info ("ISIS-Spf: added this IS %s %s depth %d dist %d to PATHS",
332 vtype2string(vertex->type), vid2string(vertex, buff),
333 vertex->depth, vertex->d_N);
334#endif /* EXTREME_DEBUG */
335
336 return;
337}
338
339struct isis_vertex *
340isis_find_vertex (struct list *list, void *id, enum vertextype vtype)
341{
342 struct listnode *node;
343 struct isis_vertex *vertex;
344 struct prefix *p1, *p2;
345
346 for (node = listhead (list); node; nextnode (node)) {
347 vertex = getdata (node);
348 if (vertex->type != vtype)
349 continue;
350 switch (vtype) {
351 case VTYPE_ES:
352 case VTYPE_NONPSEUDO_IS:
353 if (memcmp ((u_char *)id, vertex->N.id, ISIS_SYS_ID_LEN) == 0)
354 return vertex;
355 break;
356 case VTYPE_PSEUDO_IS:
357 if (memcmp ((u_char *)id, vertex->N.id, ISIS_SYS_ID_LEN + 1) == 0)
358 return vertex;
359 break;
360 case VTYPE_IPREACH_INTERNAL:
361 case VTYPE_IPREACH_EXTERNAL:
362#ifdef HAVE_IPV6
363 case VTYPE_IP6REACH_INTERNAL:
364 case VTYPE_IP6REACH_EXTERNAL:
365#endif /* HAVE_IPV6 */
366 p1 = (struct prefix *)id;
367 p2 = (struct prefix *)&vertex->N.id;
368 if (p1->family == p2->family && p1->prefixlen == p2->prefixlen &&
369 memcmp (&p1->u.prefix, &p2->u.prefix, PSIZE (p1->prefixlen)) == 0)
370 return vertex;
371 break;
372 }
373 }
374
375 return NULL;
376}
377
378
379
380/*
381 * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
382 */
383struct isis_vertex *
384isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype,
385 void *id, struct isis_adjacency *adj, u_int16_t cost,
386 int depth, int family)
387{
388 struct isis_vertex *vertex, *v;
389 struct listnode *node;
390#ifdef EXTREME_DEBUG
391 u_char buff[BUFSIZ];
392#endif
393
394 vertex = isis_vertex_new (id, vtype);
395 vertex->d_N = cost;
396 vertex->depth = depth;
397
398 if (adj)
399 listnode_add (vertex->Adj_N, adj);
400#ifdef EXTREME_DEBUG
401 zlog_info ("ISIS-Spf: add to TENT %s %s depth %d dist %d",
402 vtype2string(vertex->type), vid2string(vertex, buff),
403 vertex->depth, vertex->d_N);
404#endif /* EXTREME_DEBUG */
405 listnode_add (spftree->tents, vertex);
406 if (list_isempty (spftree->tents)) {
407 listnode_add (spftree->tents, vertex);
408 return vertex;
409 }
410 for (node = listhead (spftree->tents); node; nextnode (node)) {
411 v = getdata (node);
412 if (v->d_N > vertex->d_N) {
413 list_add_node_prev (spftree->tents, node, vertex);
414 break;
415 } else if (v->d_N == vertex->d_N) {
416 /* Tie break, add according to type */
417 while (v && v->d_N == vertex->d_N && v->type > vertex->type) {
418 if (v->type > vertex->type) {
419 break;
420 }
421 nextnode (node);
422 (node) ? (v = getdata (node)) : (v = NULL);
423 }
424 list_add_node_prev (spftree->tents, node, vertex);
425 break;
426 } else if (node->next == NULL) {
427 list_add_node_next (spftree->tents, node, vertex);
428 break;
429 }
430 }
431 return vertex;
432}
433
434struct isis_vertex *
435isis_spf_add_local (struct isis_spftree *spftree, enum vertextype vtype,
436 void *id, struct isis_adjacency *adj, u_int16_t cost,
437 int family)
438{
439 struct isis_vertex *vertex;
440
441 vertex = isis_find_vertex (spftree->tents, id, vtype);
442
443 if (vertex) {
444 /* C.2.5 c) */
445 if (vertex->d_N == cost) {
446 if (adj)
447 listnode_add (vertex->Adj_N, adj);
448 /* d) */
449 if (listcount (vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
450 remove_excess_adjs (vertex->Adj_N);
451 }
452 /* f) */
453 else if (vertex->d_N > cost) {
454 listnode_delete (spftree->tents, vertex);
455 goto add2tent;
456 }
457 /* e) do nothing */
458 return vertex;
459 }
460
461 add2tent:
462 return isis_spf_add2tent (spftree, vtype, id, adj, cost, 1, family);
463}
464
465void
466process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id,
467 u_int16_t dist, u_int16_t depth, struct isis_adjacency *adj,
468 int family)
469{
470 struct isis_vertex *vertex;
471#ifdef EXTREME_DEBUG
472 u_char buff[255];
473#endif
474
475 /* C.2.6 b) */
476 if (dist > MAX_PATH_METRIC)
477 return;
478 /* c) */
479 vertex = isis_find_vertex (spftree->paths, id, vtype);
480 if (vertex) {
481#ifdef EXTREME_DEBUG
482 zlog_info ("ISIS-Spf: process_N %s %s dist %d already found from PATH",
483 vtype2string(vtype), vid2string(vertex, buff), dist);
484#endif /* EXTREME_DEBUG */
485 assert (dist >= vertex->d_N);
486 return;
487 }
488
489 vertex = isis_find_vertex (spftree->tents, id, vtype);
490 /* d) */
491 if (vertex) {
492 /* 1) */
493#ifdef EXTREME_DEBUG
494 zlog_info ("ISIS-Spf: process_N %s %s dist %d",
495 vtype2string(vtype), vid2string(vertex, buff), dist);
496#endif /* EXTREME_DEBUG */
497 if (vertex->d_N == dist) {
498 if (adj)
499 listnode_add (vertex->Adj_N, adj);
500 /* 2) */
501 if (listcount(vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
502 remove_excess_adjs (vertex->Adj_N);
503 /* 3) */
504 return;
505 } else if (vertex->d_N < dist) {
506 return;
507 /* 4) */
508 } else {
509 listnode_delete (spftree->tents, vertex);
510 }
511 }
512
513 isis_spf_add2tent (spftree, vtype, id, adj, dist, depth, family);
514 return;
515}
516
517/*
518 * C.2.6 Step 1
519 */
520int
521isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp,
522 uint16_t cost, uint16_t depth, int family)
523{
524 struct listnode *node, *fragnode = NULL;
525 u_int16_t dist;
526 struct is_neigh *is_neigh;
527 struct ipv4_reachability *ipreach;
528 enum vertextype vtype;
529 struct prefix prefix;
530#ifdef HAVE_IPV6
531 struct ipv6_reachability *ip6reach;
532#endif /* HAVE_IPV6 */
533
534
535 if (!lsp->adj)
536 return ISIS_WARNING;
537 if (lsp->tlv_data.nlpids == NULL ||
538 !speaks (lsp->tlv_data.nlpids, family))
539 return ISIS_OK;
540
541 lspfragloop:
542 if (lsp->lsp_header->seq_num == 0) {
543 zlog_warn ("isis_spf_process_lsp(): lsp with 0 seq_num"
544 " - do not process");
545 return ISIS_WARNING;
546 }
547
548 if (!ISIS_MASK_LSP_OL_BIT(lsp->lsp_header->lsp_bits)) {
549 if (lsp->tlv_data.is_neighs) {
550 for (node = listhead (lsp->tlv_data.is_neighs); node; nextnode (node)) {
551 is_neigh = getdata (node);
552 /* C.2.6 a) */
553 /* Two way connectivity */
554 if (!memcmp (is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
555 continue;
556 dist = cost + is_neigh->metrics.metric_default;
557 vtype = LSP_PSEUDO_ID(is_neigh->neigh_id) ? VTYPE_PSEUDO_IS
558 : VTYPE_NONPSEUDO_IS;
559 process_N (spftree, vtype, (void *)is_neigh->neigh_id, dist, depth+1,
560 lsp->adj, family);
561 }
562 }
563 if (family == AF_INET && lsp->tlv_data.ipv4_int_reachs) {
564 prefix.family = AF_INET;
565 for (node = listhead (lsp->tlv_data.ipv4_int_reachs); node;
566 nextnode (node)) {
567 ipreach = getdata (node);
568 dist = cost + ipreach->metrics.metric_default;
569 vtype = VTYPE_IPREACH_INTERNAL;
570 prefix.u.prefix4 = ipreach->prefix;
571 prefix.prefixlen = ip_masklen (ipreach->mask);
572 process_N (spftree, vtype, (void *)&prefix, dist, depth + 1,
573 lsp->adj, family);
574 }
575 }
576
577 if (family == AF_INET && lsp->tlv_data.ipv4_ext_reachs) {
578 prefix.family = AF_INET;
579 for (node = listhead (lsp->tlv_data.ipv4_ext_reachs); node;
580 nextnode (node)) {
581 ipreach = getdata (node);
582 dist = cost + ipreach->metrics.metric_default;
583 vtype = VTYPE_IPREACH_EXTERNAL;
584 prefix.u.prefix4 = ipreach->prefix;
585 prefix.prefixlen = ip_masklen (ipreach->mask);
586 process_N (spftree, vtype, (void *)&prefix, dist, depth + 1,
587 lsp->adj, family);
588 }
589 }
590#ifdef HAVE_IPV6
591 if (family == AF_INET6 && lsp->tlv_data.ipv6_reachs) {
592 prefix.family = AF_INET6;
593 for (node = listhead (lsp->tlv_data.ipv6_reachs); node;
594 nextnode (node)) {
595 ip6reach = getdata (node);
596 dist = cost + ip6reach->metric;
597 vtype = (ip6reach->control_info & CTRL_INFO_DISTRIBUTION) ?
598 VTYPE_IP6REACH_EXTERNAL : VTYPE_IP6REACH_INTERNAL;
599 prefix.prefixlen = ip6reach->prefix_len;
600 memcpy (&prefix.u.prefix6.s6_addr, ip6reach->prefix,
601 PSIZE(ip6reach->prefix_len));
602 process_N (spftree, vtype, (void *)&prefix, dist, depth + 1,
603 lsp->adj, family);
604 }
605 }
606#endif /* HAVE_IPV6 */
607 }
608
609 if (fragnode == NULL)
610 fragnode = listhead (lsp->lspu.frags);
611 else
612 fragnode = nextnode (fragnode);
613
614 if (fragnode) {
615 lsp = getdata (fragnode);
616 goto lspfragloop;
617 }
618
619 return ISIS_OK;
620}
621
622int
623isis_spf_process_pseudo_lsp (struct isis_spftree *spftree,struct isis_lsp *lsp,
624 uint16_t cost, uint16_t depth, int family)
625{
626 struct listnode *node, *fragnode = NULL;
627 struct is_neigh *is_neigh;
628 enum vertextype vtype;
629
630 pseudofragloop:
631
632 if (lsp->lsp_header->seq_num == 0) {
633 zlog_warn ("isis_spf_process_pseudo_lsp(): lsp with 0 seq_num"
634 " - do not process");
635 return ISIS_WARNING;
636 }
637
638 for (node = (lsp->tlv_data.is_neighs ?
639 listhead (lsp->tlv_data.is_neighs) : NULL);
640 node; nextnode (node)) {
641 is_neigh = getdata (node);
642 vtype = LSP_PSEUDO_ID(is_neigh->neigh_id) ? VTYPE_PSEUDO_IS
643 : VTYPE_NONPSEUDO_IS;
644 /* Two way connectivity */
645 if (!memcmp (is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
646 continue;
647 if (isis_find_vertex (spftree->tents, (void *)is_neigh->neigh_id, vtype)
648 == NULL &&
649 isis_find_vertex (spftree->paths, (void *)is_neigh->neigh_id, vtype)
650 == NULL) {
651 /* C.2.5 i) */
652 isis_spf_add2tent (spftree, vtype, is_neigh->neigh_id, lsp->adj,
653 cost, depth, family);
654 }
655 }
656
657 if (fragnode == NULL)
658 fragnode = listhead (lsp->lspu.frags);
659 else
660 fragnode = nextnode (fragnode);
661
662 if (fragnode) {
663 lsp = getdata (fragnode);
664 goto pseudofragloop;
665 }
666
667
668 return ISIS_OK;
669}
670
671int
672isis_spf_preload_tent (struct isis_spftree *spftree,
673 struct isis_area *area, int level, int family)
674{
675 struct isis_vertex *vertex;
676 struct isis_circuit *circuit;
677 struct listnode *cnode, *anode, *ipnode;
678 struct isis_adjacency *adj;
679 struct isis_lsp *lsp;
680 struct list *adj_list;
681 struct list *adjdb;
682 struct prefix_ipv4 *ipv4;
683 struct prefix prefix;
684 int retval = ISIS_OK;
685 u_char lsp_id[ISIS_SYS_ID_LEN + 2];
686#ifdef HAVE_IPV6
687 struct prefix_ipv6 *ipv6;
688#endif /* HAVE_IPV6 */
689
690 for (cnode = listhead (area->circuit_list); cnode; nextnode (cnode)) {
691 circuit = getdata (cnode);
692 if (circuit->state != C_STATE_UP)
693 continue;
694 if (!(circuit->circuit_is_type & level))
695 continue;
696 if (family == AF_INET && !circuit->ip_router)
697 continue;
698#ifdef HAVE_IPV6
699 if (family == AF_INET6 && !circuit->ipv6_router)
700 continue;
701#endif /* HAVE_IPV6 */
702 /*
703 * Add IP(v6) addresses of this circuit
704 */
705 if (family == AF_INET) {
706 prefix.family = AF_INET;
707 for (ipnode = (circuit->ip_addrs ? listhead (circuit->ip_addrs) : NULL);
708 ipnode; nextnode (ipnode)) {
709 ipv4 = getdata (ipnode);
710 prefix.u.prefix4 = ipv4->prefix;
711 prefix.prefixlen = ipv4->prefixlen;
712 isis_spf_add_local (spftree, VTYPE_IPREACH_INTERNAL, &prefix, NULL, 0,
713 family);
714 }
715 }
716#ifdef HAVE_IPV6
717 if (family == AF_INET6) {
718 prefix.family = AF_INET6;
719 for (ipnode = (circuit->ipv6_non_link ? listhead
720 (circuit->ipv6_non_link) : NULL); ipnode;
721 nextnode (ipnode)) {
722 ipv6 = getdata (ipnode);
723 prefix.prefixlen = ipv6->prefixlen;
724 prefix.u.prefix6 = ipv6->prefix;
725 isis_spf_add_local (spftree, VTYPE_IP6REACH_INTERNAL,
726 &prefix, NULL, 0, family);
727 }
728 }
729#endif /* HAVE_IPV6 */
730 if (circuit->circ_type == CIRCUIT_T_BROADCAST ) {
731 /*
732 * Add the adjacencies
733 */
734 adj_list = list_new ();
735 adjdb = circuit->u.bc.adjdb[level - 1];
736 isis_adj_build_up_list (adjdb, adj_list);
737 if (listcount (adj_list) == 0) {
738 list_delete (adj_list);
739 zlog_warn ("ISIS-Spf: no L%d adjacencies on circuit %s",
740 level, circuit->interface->name);
741 continue;
742 }
743 anode = listhead (adj_list);
744 while (anode) {
745 adj = getdata (anode);
746 if (!speaks (&adj->nlpids, family))
747 continue;
748 switch (adj->sys_type) {
749 case ISIS_SYSTYPE_ES:
750 isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj,
751 circuit->metrics[level - 1].metric_default,
752 family);
753 break;
754 case ISIS_SYSTYPE_IS:
755 case ISIS_SYSTYPE_L1_IS:
756 case ISIS_SYSTYPE_L2_IS:
757 vertex =
758 isis_spf_add_local (spftree, VTYPE_NONPSEUDO_IS,
759 adj->sysid, adj,
760 circuit->metrics[level - 1].metric_default,
761 family);
762 memcpy (lsp_id, adj->sysid, ISIS_SYS_ID_LEN);
763 LSP_PSEUDO_ID(lsp_id) = 0;
764 LSP_FRAGMENT(lsp_id) = 0;
765 lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
766 if (!lsp)
767 zlog_warn ("No lsp found for IS adjacency");
768 /* else {
769 isis_spf_process_lsp (spftree, lsp, vertex->d_N, 1, family);
770 } */
771 break;
772 case ISIS_SYSTYPE_UNKNOWN:
773 default:
774 zlog_warn ("isis_spf_preload_tent unknow adj type");
775 }
776 anode = nextnode (anode);
777 }
778 list_delete (adj_list);
779 /*
780 * Add the pseudonode
781 */
782 if (level == 1)
783 memcpy (lsp_id, circuit->u.bc.l1_desig_is, ISIS_SYS_ID_LEN + 1);
784 else
785 memcpy (lsp_id, circuit->u.bc.l2_desig_is, ISIS_SYS_ID_LEN + 1);
786 lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
787 adj = isis_adj_lookup (lsp_id, adjdb);
788 /* if no adj, we are the dis or error */
789 if (!adj && !circuit->u.bc.is_dr[level - 1]) {
790 zlog_warn ("ISIS-Spf: No adjacency found for DR");
791 }
792 if (lsp == NULL || lsp->lsp_header->rem_lifetime == 0) {
793 zlog_warn ("ISIS-Spf: No lsp found for DR");
794 } else {
795 isis_spf_process_pseudo_lsp
796 (spftree, lsp, circuit->metrics[level - 1].metric_default, 0,
797 family);
798
799 }
800 } else if (circuit->circ_type == CIRCUIT_T_P2P ) {
801 adj = circuit->u.p2p.neighbor;
802 if (!adj)
803 continue;
804 switch (adj->sys_type) {
805 case ISIS_SYSTYPE_ES:
806 isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj,
807 circuit->metrics[level - 1].metric_default,
808 family);
809 break;
810 case ISIS_SYSTYPE_IS:
811 case ISIS_SYSTYPE_L1_IS:
812 case ISIS_SYSTYPE_L2_IS:
813 if (speaks (&adj->nlpids, family))
814 isis_spf_add_local (spftree, VTYPE_NONPSEUDO_IS, adj->sysid, adj,
815 circuit->metrics[level - 1].metric_default,
816 family);
817 break;
818 case ISIS_SYSTYPE_UNKNOWN:
819 default:
820 zlog_warn ("isis_spf_preload_tent unknow adj type");
821 break;
822 }
823 } else {
824 zlog_warn ("isis_spf_preload_tent unsupported media");
825 retval = ISIS_WARNING;
826 }
827
828 }
829
830 return retval;
831}
832
833/*
834 * The parent(s) for vertex is set when added to TENT list
835 * now we just put the child pointer(s) in place
836 */
837void
838add_to_paths (struct isis_spftree *spftree, struct isis_vertex *vertex,
839 struct isis_area *area)
840{
841
842#ifdef EXTREME_DEBUG
843 u_char buff[BUFSIZ];
844#endif /* EXTREME_DEBUG */
845 listnode_add (spftree->paths, vertex);
846
847#ifdef EXTREME_DEBUG
848 zlog_info ("ISIS-Spf: added %s %s depth %d dist %d to PATHS",
849 vtype2string(vertex->type), vid2string(vertex, buff),
850 vertex->depth, vertex->d_N);
851#endif /* EXTREME_DEBUG */
852 if (vertex->type > VTYPE_ES) {
853 if (listcount(vertex->Adj_N) > 0)
854 isis_route_create ((struct prefix *)&vertex->N.prefix,
855 vertex->d_N, vertex->depth, vertex->Adj_N, area);
856 else if (isis->debugs & DEBUG_SPF_EVENTS)
857 zlog_info ("ISIS-Spf: no adjacencies do not install route");
858 }
859
860 return;
861}
862
863
864void
865init_spt (struct isis_spftree *spftree)
866{
867 spftree->tents->del = spftree->paths->del = (void *)isis_vertex_del;
868 list_delete_all_node (spftree->tents);
869 list_delete_all_node (spftree->paths);
870 spftree->tents->del = spftree->paths->del = NULL;
871
872 return;
873}
874
875int
876isis_run_spf (struct isis_area *area, int level, int family)
877{
878 int retval = ISIS_OK;
879 struct listnode *node;
880 struct isis_vertex *vertex;
881 struct isis_spftree *spftree = NULL;
882 u_char lsp_id[ISIS_SYS_ID_LEN + 2];
883 struct isis_lsp *lsp;
884
885 if (family == AF_INET)
886 spftree = area->spftree[level - 1];
887#ifdef HAVE_IPV6
888 else if (family == AF_INET6)
889 spftree = area->spftree6[level - 1];
890#endif
891
892 assert (spftree);
893
894 /*
895 * C.2.5 Step 0
896 */
897 init_spt (spftree);
898 /* a) */
899 isis_spf_add_self (spftree, area, level);
900 /* b) */
901 retval = isis_spf_preload_tent (spftree, area, level, family);
902
903 /*
904 * C.2.7 Step 2
905 */
906 if (listcount (spftree->tents) == 0) {
907 zlog_warn ("ISIS-Spf: TENT is empty");
908 spftree->lastrun = time (NULL);
909 return retval;
910 }
911
912 while (listcount (spftree->tents) > 0) {
913 node = listhead (spftree->tents);
914 vertex = getdata (node);
915 /* Remove from tent list */
916 list_delete_node (spftree->tents, node);
917 if (isis_find_vertex (spftree->paths, vertex->N.id, vertex->type))
918 continue;
919 add_to_paths (spftree, vertex, area);
920 if (vertex->type == VTYPE_PSEUDO_IS ||
921 vertex->type == VTYPE_NONPSEUDO_IS) {
922 memcpy (lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1);
923 LSP_FRAGMENT(lsp_id) = 0;
924 lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
925 if (lsp) {
926 if (LSP_PSEUDO_ID (lsp_id)) {
927 isis_spf_process_pseudo_lsp (spftree, lsp, vertex->d_N,
928 vertex->depth, family);
929
930 } else {
931 isis_spf_process_lsp (spftree, lsp, vertex->d_N, vertex->depth,
932 family);
933 }
934 } else {
935 zlog_warn ("ISIS-Spf: No LSP found for %s", rawlspid_print (lsp_id));
936 }
937 }
938 }
939
940 thread_add_event (master, isis_route_validate, area, 0);
941 spftree->lastrun = time (NULL);
942 spftree->pending = 0;
943
944 if (level == 1)
945 spftree->t_spf_periodic = thread_add_timer (master,
946 isis_run_spf_l1, area,
947 isis_jitter
948 (PERIODIC_SPF_INTERVAL, 10));
949 else
950 spftree->t_spf_periodic = thread_add_timer (master,
951 isis_run_spf_l2, area,
952 isis_jitter
953 (PERIODIC_SPF_INTERVAL, 10));
954
955 return retval;
956}
957
958int
959isis_run_spf_l1 (struct thread *thread)
960{
961 struct isis_area *area;
962 int retval = ISIS_OK;
963
964 area = THREAD_ARG(thread);
965 assert (area);
966
967 if (!(area->is_type & IS_LEVEL_1)) {
968 if (isis->debugs & DEBUG_SPF_EVENTS) {
969 zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
970 }
971 return ISIS_WARNING;
972 }
973
974 if (isis->debugs & DEBUG_SPF_EVENTS) {
975 zlog_info ("ISIS-Spf (%s) L1 SPF needed, periodic SPF",
976 area->area_tag);
977 }
978
979 if (area->ip_circuits)
980 retval = isis_run_spf (area, 1, AF_INET);
981#ifdef HAVE_IPV6
982 if (area->ipv6_circuits)
983 retval = isis_run_spf (area, 1, AF_INET6);
984#endif
985 return retval;
986}
987
988int
989isis_run_spf_l2 (struct thread *thread)
990{
991 struct isis_area *area;
992 int retval = ISIS_OK;
993
994 area = THREAD_ARG(thread);
995 assert (area);
996
997 if (!(area->is_type & IS_LEVEL_2)) {
998 if (isis->debugs & DEBUG_SPF_EVENTS) {
999 zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
1000 }
1001 return ISIS_WARNING;
1002 }
1003
1004 if (isis->debugs & DEBUG_SPF_EVENTS) {
1005 zlog_info ("ISIS-Spf (%s) L2 SPF needed, periodic SPF",
1006 area->area_tag);
1007 }
1008
1009 if (area->ip_circuits)
1010 retval = isis_run_spf (area, 2, AF_INET);
1011#ifdef HAVE_IPV6
1012 if (area->ipv6_circuits)
1013 retval = isis_run_spf (area, 2, AF_INET6);
1014#endif
1015
1016 return retval;
1017}
1018
1019int
1020isis_spf_schedule (struct isis_area *area, int level)
1021{
1022 int retval = ISIS_OK;
1023 struct isis_spftree *spftree = area->spftree[level - 1];
1024 time_t diff, now = time (NULL);
1025
1026 if (spftree->pending)
1027 return retval;
1028
1029 diff = now - spftree->lastrun;
1030
1031 /* FIXME: let's wait a minute before doing the SPF */
1032 if (now - isis->uptime < 60 || isis->uptime == 0) {
1033 if (level == 1)
1034 thread_add_timer (master, isis_run_spf_l1, area,
1035 60);
1036 else
1037 thread_add_timer (master, isis_run_spf_l2, area,
1038 60);
1039
1040 spftree->pending = 1;
1041 return retval;
1042 }
1043 if (spftree->t_spf_periodic)
1044 thread_cancel (spftree->t_spf_periodic);
1045
1046 if (diff < MINIMUM_SPF_INTERVAL) {
1047 if (level == 1)
1048 thread_add_timer (master, isis_run_spf_l1, area,
1049 MINIMUM_SPF_INTERVAL - diff);
1050 else
1051 thread_add_timer (master, isis_run_spf_l2, area,
1052 MINIMUM_SPF_INTERVAL - diff);
1053
1054 spftree->pending = 1;
1055 } else {
1056 spftree->pending = 0;
1057 retval = isis_run_spf (area, level, AF_INET);
1058 }
1059
1060 return retval;
1061}
1062
1063#ifdef HAVE_IPV6
1064int
1065isis_spf_schedule6 (struct isis_area *area, int level)
1066{
1067 int retval = ISIS_OK;
1068 struct isis_spftree *spftree = area->spftree6[level - 1];
1069 time_t diff, now = time (NULL);
1070
1071 if (spftree->pending)
1072 return retval;
1073
1074 diff = now - spftree->lastrun;
1075
1076 if (spftree->t_spf_periodic)
1077 thread_cancel (spftree->t_spf_periodic);
1078
1079 /* FIXME: let's wait a minute before doing the SPF */
1080 if (now - isis->uptime < 60 || isis->uptime == 0) {
1081 if (level == 1)
1082 thread_add_timer (master, isis_run_spf_l1, area,
1083 60);
1084 else
1085 thread_add_timer (master, isis_run_spf_l2, area,
1086 60);
1087
1088 spftree->pending = 1;
1089 return retval;
1090 }
1091
1092
1093 if (diff < MINIMUM_SPF_INTERVAL) {
1094 if (level == 1)
1095 thread_add_timer (master, isis_run_spf_l1, area,
1096 MINIMUM_SPF_INTERVAL - diff);
1097 else
1098 thread_add_timer (master, isis_run_spf_l2, area,
1099 MINIMUM_SPF_INTERVAL - diff);
1100
1101 spftree->pending = 1;
1102 } else {
1103 spftree->pending = 0;
1104 retval = isis_run_spf (area, level, AF_INET6);
1105 }
1106
1107 return retval;
1108}
1109
1110#endif
1111
1112void
1113isis_print_paths (struct vty *vty, struct list *paths)
1114{
1115 struct listnode *node, *anode;
1116 struct isis_vertex *vertex;
1117 struct isis_dynhn *dyn, *nh_dyn = NULL;
1118 struct isis_adjacency *adj;
1119#ifdef EXTREME_DEBUG
1120 u_char buff[255];
1121#endif
1122
1123 vty_out (vty, "System Id Metric Next-Hop"
1124 " Interface SNPA%s", VTY_NEWLINE);
1125 for (node = listhead (paths); node; nextnode (node)) {
1126 vertex = getdata (node);
1127 if (vertex->type != VTYPE_NONPSEUDO_IS)
1128 continue;
1129 if (memcmp (vertex->N.id, isis->sysid, ISIS_SYS_ID_LEN) == 0) {
1130 vty_out (vty, "%s --%s", host.name, VTY_NEWLINE);
1131 } else {
1132 dyn = dynhn_find_by_id ((u_char *)vertex->N.id);
1133 anode = listhead (vertex->Adj_N);
1134 adj = getdata (anode);
1135 if (adj) {
1136 nh_dyn = dynhn_find_by_id (adj->sysid);
1137 vty_out (vty, "%-20s %-10u %-20s %-11s %-5s%s",
1138 (dyn != NULL) ? dyn->name.name :
1139 (u_char *)rawlspid_print ((u_char *)vertex->N.id),
1140 vertex->d_N, (nh_dyn != NULL) ? nh_dyn->name.name :
1141 (u_char *)rawlspid_print (adj->sysid),
1142 adj->circuit->interface->name,
1143 snpa_print (adj->snpa), VTY_NEWLINE);
1144 } else {
1145 vty_out (vty, "%s %u %s", dyn ? dyn->name.name :
1146 (u_char *)rawlspid_print (vertex->N.id),
1147 vertex->d_N, VTY_NEWLINE);
1148 }
1149
1150 }
1151#if 0
1152 vty_out (vty, "%s %s %u %s", vtype2string(vertex->type),
1153 vid2string(vertex, buff), vertex->d_N, VTY_NEWLINE);
1154#endif
1155 }
1156
1157
1158}
1159
1160DEFUN (show_isis_topology,
1161 show_isis_topology_cmd,
1162 "show isis topology",
1163 SHOW_STR
1164 "IS-IS information\n"
1165 "IS-IS paths to Intermediate Systems\n")
1166{
1167 struct listnode *node;
1168 struct isis_area *area;
1169 int level;
1170
1171 if (!isis->area_list || isis->area_list->count == 0)
1172 return CMD_SUCCESS;
1173
1174 for (node = listhead (isis->area_list); node; nextnode (node)) {
1175 area = getdata (node);
1176
1177 vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
1178 VTY_NEWLINE);
1179
1180 for (level=0; level < ISIS_LEVELS; level++) {
1181 if (area->ip_circuits > 0 && area->spftree[level]
1182 && area->spftree[level]->paths->count > 0) {
1183 vty_out (vty, "IS-IS paths to level-%d routers that speak IP%s",
1184 level+1, VTY_NEWLINE);
1185 isis_print_paths (vty, area->spftree[level]->paths);
1186 }
1187#ifdef HAVE_IPV6
1188 if (area->ipv6_circuits > 0 && area->spftree6[level]
1189 && area->spftree6[level]->paths->count > 0) {
1190 vty_out (vty, "IS-IS paths to level-%d routers that speak IPv6%s",
1191 level+1, VTY_NEWLINE);
1192 isis_print_paths (vty, area->spftree6[level]->paths);
1193 }
1194#endif /* HAVE_IPV6 */
1195 }
1196 }
1197
1198 return CMD_SUCCESS;
1199}
1200
1201
1202DEFUN (show_isis_topology_l1,
1203 show_isis_topology_l1_cmd,
1204 "show isis topology level-1",
1205 SHOW_STR
1206 "IS-IS information\n"
1207 "IS-IS paths to Intermediate Systems\n"
1208 "Paths to all level-1 routers in the area\n")
1209{
1210 struct listnode *node;
1211 struct isis_area *area;
1212
1213 if (!isis->area_list || isis->area_list->count == 0)
1214 return CMD_SUCCESS;
1215
1216 for (node = listhead (isis->area_list); node; nextnode (node)) {
1217 area = getdata (node);
1218
1219 vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
1220 VTY_NEWLINE);
1221
1222 if (area->ip_circuits > 0 && area->spftree[0]
1223 && area->spftree[0]->paths->count > 0) {
1224 vty_out (vty, "IS-IS paths to level-1 routers that speak IP%s",
1225 VTY_NEWLINE);
1226 isis_print_paths (vty, area->spftree[0]->paths);
1227 }
1228#ifdef HAVE_IPV6
1229 if (area->ipv6_circuits > 0 && area->spftree6[0]
1230 && area->spftree6[0]->paths->count > 0) {
1231 vty_out (vty, "IS-IS paths to level-1 routers that speak IPv6%s",
1232 VTY_NEWLINE);
1233 isis_print_paths (vty, area->spftree6[0]->paths);
1234 }
1235#endif /* HAVE_IPV6 */
1236 }
1237
1238
1239 return CMD_SUCCESS;
1240}
1241
1242DEFUN (show_isis_topology_l2,
1243 show_isis_topology_l2_cmd,
1244 "show isis topology level-2",
1245 SHOW_STR
1246 "IS-IS information\n"
1247 "IS-IS paths to Intermediate Systems\n"
1248 "Paths to all level-2 routers in the domain\n")
1249{
1250 struct listnode *node;
1251 struct isis_area *area;
1252
1253 if (!isis->area_list || isis->area_list->count == 0)
1254 return CMD_SUCCESS;
1255
1256 for (node = listhead (isis->area_list); node; nextnode (node)) {
1257 area = getdata (node);
1258
1259 vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
1260 VTY_NEWLINE);
1261
1262 if (area->ip_circuits > 0 && area->spftree[1]
1263 && area->spftree[1]->paths->count > 0) {
1264 vty_out (vty, "IS-IS paths to level-2 routers that speak IP%s",
1265 VTY_NEWLINE);
1266 isis_print_paths (vty, area->spftree[1]->paths);
1267 }
1268#ifdef HAVE_IPV6
1269 if (area->ipv6_circuits > 0 && area->spftree6[1]
1270 && area->spftree6[1]->paths->count > 0) {
1271 vty_out (vty, "IS-IS paths to level-2 routers that speak IPv6%s",
1272 VTY_NEWLINE);
1273 isis_print_paths (vty, area->spftree6[1]->paths);
1274 }
1275#endif /* HAVE_IPV6 */
1276 }
1277
1278
1279 return CMD_SUCCESS;
1280}
1281
1282
1283void
1284isis_spf_cmds_init ()
1285{
1286 install_element (VIEW_NODE, &show_isis_topology_cmd);
1287 install_element (VIEW_NODE, &show_isis_topology_l1_cmd);
1288 install_element (VIEW_NODE, &show_isis_topology_l2_cmd);
1289
1290 install_element (ENABLE_NODE, &show_isis_topology_cmd);
1291 install_element (ENABLE_NODE, &show_isis_topology_l1_cmd);
1292 install_element (ENABLE_NODE, &show_isis_topology_l2_cmd);
1293}
FRRouting mirror