isis_spf.c 46 KB

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