isis_spf.c 45 KB

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