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