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