isis_spf.c 46 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703
  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 %d sec ago",
  1302. area->area_tag, level, 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 %d sec from now",
  1317. area->area_tag, level, area->min_spf_interval[level-1] - diff);
  1318. spftree->pending = 1;
  1319. return retval;
  1320. }
  1321. #endif
  1322. static void
  1323. isis_print_paths (struct vty *vty, struct list *paths, u_char *root_sysid)
  1324. {
  1325. struct listnode *node;
  1326. struct listnode *anode;
  1327. struct isis_vertex *vertex;
  1328. struct isis_adjacency *adj;
  1329. u_char buff[BUFSIZ];
  1330. vty_out (vty, "Vertex Type Metric "
  1331. "Next-Hop Interface Parent%s", VTY_NEWLINE);
  1332. for (ALL_LIST_ELEMENTS_RO (paths, node, vertex)) {
  1333. if (memcmp (vertex->N.id, root_sysid, ISIS_SYS_ID_LEN) == 0) {
  1334. vty_out (vty, "%-20s %-12s %-6s", print_sys_hostname (root_sysid),
  1335. "", "");
  1336. vty_out (vty, "%-30s", "");
  1337. } else {
  1338. int rows = 0;
  1339. vty_out (vty, "%-20s %-12s %-6u ", vid2string (vertex, buff),
  1340. vtype2string (vertex->type), vertex->d_N);
  1341. for (ALL_LIST_ELEMENTS_RO (vertex->Adj_N, anode, adj)) {
  1342. if (adj) {
  1343. if (rows) {
  1344. vty_out (vty, "%s", VTY_NEWLINE);
  1345. vty_out (vty, "%-20s %-12s %-6s ", "", "", "");
  1346. }
  1347. vty_out (vty, "%-20s %-9s ",
  1348. print_sys_hostname (adj->sysid),
  1349. adj->circuit->interface->name);
  1350. ++rows;
  1351. }
  1352. }
  1353. if (rows == 0)
  1354. vty_out (vty, "%-30s ", "");
  1355. }
  1356. /* Print list of parents for the ECMP DAG */
  1357. if (listcount (vertex->parents) > 0) {
  1358. struct listnode *pnode;
  1359. struct isis_vertex *pvertex;
  1360. int rows = 0;
  1361. for (ALL_LIST_ELEMENTS_RO (vertex->parents, pnode, pvertex)) {
  1362. if (rows) {
  1363. vty_out (vty, "%s", VTY_NEWLINE);
  1364. vty_out (vty, "%-72s", "");
  1365. }
  1366. vty_out (vty, "%s(%d)",
  1367. vid2string (pvertex, buff), pvertex->type);
  1368. ++rows;
  1369. }
  1370. } else {
  1371. vty_out (vty, " NULL ");
  1372. }
  1373. #if 0
  1374. if (listcount (vertex->children) > 0) {
  1375. struct listnode *cnode;
  1376. struct isis_vertex *cvertex;
  1377. for (ALL_LIST_ELEMENTS_RO (vertex->children, cnode, cvertex)) {
  1378. vty_out (vty, "%s", VTY_NEWLINE);
  1379. vty_out (vty, "%-72s", "");
  1380. vty_out (vty, "%s(%d) ",
  1381. vid2string (cvertex, buff), cvertex->type);
  1382. }
  1383. }
  1384. #endif
  1385. vty_out (vty, "%s", VTY_NEWLINE);
  1386. }
  1387. }
  1388. DEFUN (show_isis_topology,
  1389. show_isis_topology_cmd,
  1390. "show isis topology",
  1391. SHOW_STR
  1392. "IS-IS information\n"
  1393. "IS-IS paths to Intermediate Systems\n")
  1394. {
  1395. struct listnode *node;
  1396. struct isis_area *area;
  1397. int level;
  1398. if (!isis->area_list || isis->area_list->count == 0)
  1399. return CMD_SUCCESS;
  1400. for (ALL_LIST_ELEMENTS_RO (isis->area_list, node, area))
  1401. {
  1402. vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
  1403. VTY_NEWLINE);
  1404. for (level = 0; level < ISIS_LEVELS; level++)
  1405. {
  1406. if (area->ip_circuits > 0 && area->spftree[level]
  1407. && area->spftree[level]->paths->count > 0)
  1408. {
  1409. vty_out (vty, "IS-IS paths to level-%d routers that speak IP%s",
  1410. level + 1, VTY_NEWLINE);
  1411. isis_print_paths (vty, area->spftree[level]->paths, isis->sysid);
  1412. vty_out (vty, "%s", VTY_NEWLINE);
  1413. }
  1414. #ifdef HAVE_IPV6
  1415. if (area->ipv6_circuits > 0 && area->spftree6[level]
  1416. && area->spftree6[level]->paths->count > 0)
  1417. {
  1418. vty_out (vty,
  1419. "IS-IS paths to level-%d routers that speak IPv6%s",
  1420. level + 1, VTY_NEWLINE);
  1421. isis_print_paths (vty, area->spftree6[level]->paths, isis->sysid);
  1422. vty_out (vty, "%s", VTY_NEWLINE);
  1423. }
  1424. #endif /* HAVE_IPV6 */
  1425. }
  1426. vty_out (vty, "%s", VTY_NEWLINE);
  1427. }
  1428. return CMD_SUCCESS;
  1429. }
  1430. DEFUN (show_isis_topology_l1,
  1431. show_isis_topology_l1_cmd,
  1432. "show isis topology level-1",
  1433. SHOW_STR
  1434. "IS-IS information\n"
  1435. "IS-IS paths to Intermediate Systems\n"
  1436. "Paths to all level-1 routers in the area\n")
  1437. {
  1438. struct listnode *node;
  1439. struct isis_area *area;
  1440. if (!isis->area_list || isis->area_list->count == 0)
  1441. return CMD_SUCCESS;
  1442. for (ALL_LIST_ELEMENTS_RO (isis->area_list, node, area))
  1443. {
  1444. vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
  1445. VTY_NEWLINE);
  1446. if (area->ip_circuits > 0 && area->spftree[0]
  1447. && area->spftree[0]->paths->count > 0)
  1448. {
  1449. vty_out (vty, "IS-IS paths to level-1 routers that speak IP%s",
  1450. VTY_NEWLINE);
  1451. isis_print_paths (vty, area->spftree[0]->paths, isis->sysid);
  1452. vty_out (vty, "%s", VTY_NEWLINE);
  1453. }
  1454. #ifdef HAVE_IPV6
  1455. if (area->ipv6_circuits > 0 && area->spftree6[0]
  1456. && area->spftree6[0]->paths->count > 0)
  1457. {
  1458. vty_out (vty, "IS-IS paths to level-1 routers that speak IPv6%s",
  1459. VTY_NEWLINE);
  1460. isis_print_paths (vty, area->spftree6[0]->paths, isis->sysid);
  1461. vty_out (vty, "%s", VTY_NEWLINE);
  1462. }
  1463. #endif /* HAVE_IPV6 */
  1464. vty_out (vty, "%s", VTY_NEWLINE);
  1465. }
  1466. return CMD_SUCCESS;
  1467. }
  1468. DEFUN (show_isis_topology_l2,
  1469. show_isis_topology_l2_cmd,
  1470. "show isis topology level-2",
  1471. SHOW_STR
  1472. "IS-IS information\n"
  1473. "IS-IS paths to Intermediate Systems\n"
  1474. "Paths to all level-2 routers in the domain\n")
  1475. {
  1476. struct listnode *node;
  1477. struct isis_area *area;
  1478. if (!isis->area_list || isis->area_list->count == 0)
  1479. return CMD_SUCCESS;
  1480. for (ALL_LIST_ELEMENTS_RO (isis->area_list, node, area))
  1481. {
  1482. vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
  1483. VTY_NEWLINE);
  1484. if (area->ip_circuits > 0 && area->spftree[1]
  1485. && area->spftree[1]->paths->count > 0)
  1486. {
  1487. vty_out (vty, "IS-IS paths to level-2 routers that speak IP%s",
  1488. VTY_NEWLINE);
  1489. isis_print_paths (vty, area->spftree[1]->paths, isis->sysid);
  1490. vty_out (vty, "%s", VTY_NEWLINE);
  1491. }
  1492. #ifdef HAVE_IPV6
  1493. if (area->ipv6_circuits > 0 && area->spftree6[1]
  1494. && area->spftree6[1]->paths->count > 0)
  1495. {
  1496. vty_out (vty, "IS-IS paths to level-2 routers that speak IPv6%s",
  1497. VTY_NEWLINE);
  1498. isis_print_paths (vty, area->spftree6[1]->paths, isis->sysid);
  1499. vty_out (vty, "%s", VTY_NEWLINE);
  1500. }
  1501. #endif /* HAVE_IPV6 */
  1502. vty_out (vty, "%s", VTY_NEWLINE);
  1503. }
  1504. return CMD_SUCCESS;
  1505. }
  1506. void
  1507. isis_spf_cmds_init ()
  1508. {
  1509. install_element (VIEW_NODE, &show_isis_topology_cmd);
  1510. install_element (VIEW_NODE, &show_isis_topology_l1_cmd);
  1511. install_element (VIEW_NODE, &show_isis_topology_l2_cmd);
  1512. install_element (ENABLE_NODE, &show_isis_topology_cmd);
  1513. install_element (ENABLE_NODE, &show_isis_topology_l1_cmd);
  1514. install_element (ENABLE_NODE, &show_isis_topology_l2_cmd);
  1515. }