ospf_spf.c 45 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491
  1. /* OSPF SPF calculation.
  2. Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
  3. This file is part of GNU Zebra.
  4. GNU Zebra is free software; you can redistribute it and/or modify it
  5. under the terms of the GNU General Public License as published by the
  6. Free Software Foundation; either version 2, or (at your option) any
  7. later version.
  8. GNU Zebra is distributed in the hope that it will be useful, but
  9. WITHOUT ANY WARRANTY; without even the implied warranty of
  10. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  11. General Public License for more details.
  12. You should have received a copy of the GNU General Public License
  13. along with GNU Zebra; see the file COPYING. If not, write to the Free
  14. Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  15. 02111-1307, USA. */
  16. #include <zebra.h>
  17. #include "thread.h"
  18. #include "memory.h"
  19. #include "hash.h"
  20. #include "linklist.h"
  21. #include "prefix.h"
  22. #include "if.h"
  23. #include "table.h"
  24. #include "log.h"
  25. #include "sockunion.h" /* for inet_ntop () */
  26. #include "pqueue.h"
  27. #include "ospfd/ospfd.h"
  28. #include "ospfd/ospf_interface.h"
  29. #include "ospfd/ospf_ism.h"
  30. #include "ospfd/ospf_asbr.h"
  31. #include "ospfd/ospf_lsa.h"
  32. #include "ospfd/ospf_lsdb.h"
  33. #include "ospfd/ospf_neighbor.h"
  34. #include "ospfd/ospf_nsm.h"
  35. #include "ospfd/ospf_spf.h"
  36. #include "ospfd/ospf_route.h"
  37. #include "ospfd/ospf_ia.h"
  38. #include "ospfd/ospf_ase.h"
  39. #include "ospfd/ospf_abr.h"
  40. #include "ospfd/ospf_dump.h"
  41. /* Variables to ensure a SPF scheduled log message is printed only once */
  42. static unsigned int spf_reason_flags = 0;
  43. static void
  44. ospf_clear_spf_reason_flags ()
  45. {
  46. spf_reason_flags = 0;
  47. }
  48. static void
  49. ospf_spf_set_reason (ospf_spf_reason_t reason)
  50. {
  51. spf_reason_flags |= 1 << reason;
  52. }
  53. static void
  54. ospf_get_spf_reason_str (char *buf)
  55. {
  56. if (!buf)
  57. return;
  58. buf[0] = '\0';
  59. if (spf_reason_flags)
  60. {
  61. if (spf_reason_flags & SPF_FLAG_ROUTER_LSA_INSTALL)
  62. strcat (buf, "R, ");
  63. if (spf_reason_flags & SPF_FLAG_NETWORK_LSA_INSTALL)
  64. strcat (buf, "N, ");
  65. if (spf_reason_flags & SPF_FLAG_SUMMARY_LSA_INSTALL)
  66. strcat (buf, "S, ");
  67. if (spf_reason_flags & SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL)
  68. strcat (buf, "AS, ");
  69. if (spf_reason_flags & SPF_FLAG_ABR_STATUS_CHANGE)
  70. strcat (buf, "ABR, ");
  71. if (spf_reason_flags & SPF_FLAG_ASBR_STATUS_CHANGE)
  72. strcat (buf, "ASBR, ");
  73. if (spf_reason_flags & SPF_FLAG_MAXAGE)
  74. strcat (buf, "M, ");
  75. buf[strlen(buf)-2] = '\0'; /* skip the last ", " */
  76. }
  77. }
  78. static void ospf_vertex_free (void *);
  79. /* List of allocated vertices, to simplify cleanup of SPF.
  80. * Not thread-safe obviously. If it ever needs to be, it'd have to be
  81. * dynamically allocated at begin of ospf_spf_calculate
  82. */
  83. static struct list vertex_list = { .del = ospf_vertex_free };
  84. /* Heap related functions, for the managment of the candidates, to
  85. * be used with pqueue. */
  86. static int
  87. cmp (void * node1 , void * node2)
  88. {
  89. struct vertex * v1 = (struct vertex *) node1;
  90. struct vertex * v2 = (struct vertex *) node2;
  91. if (v1 != NULL && v2 != NULL )
  92. {
  93. /* network vertices must be chosen before router vertices of same
  94. * cost in order to find all shortest paths
  95. */
  96. if ( ((v1->distance - v2->distance) == 0)
  97. && (v1->type != v2->type))
  98. {
  99. switch (v1->type)
  100. {
  101. case OSPF_VERTEX_NETWORK:
  102. return -1;
  103. case OSPF_VERTEX_ROUTER:
  104. return 1;
  105. }
  106. }
  107. else
  108. return (v1->distance - v2->distance);
  109. }
  110. return 0;
  111. }
  112. static void
  113. update_stat (void *node , int position)
  114. {
  115. struct vertex *v = node;
  116. /* Set the status of the vertex, when its position changes. */
  117. *(v->stat) = position;
  118. }
  119. static struct vertex_nexthop *
  120. vertex_nexthop_new (void)
  121. {
  122. return XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop));
  123. }
  124. static void
  125. vertex_nexthop_free (struct vertex_nexthop *nh)
  126. {
  127. XFREE (MTYPE_OSPF_NEXTHOP, nh);
  128. }
  129. /* Free the canonical nexthop objects for an area, ie the nexthop objects
  130. * attached to the first-hop router vertices, and any intervening network
  131. * vertices.
  132. */
  133. static void
  134. ospf_canonical_nexthops_free (struct vertex *root)
  135. {
  136. struct listnode *node, *nnode;
  137. struct vertex *child;
  138. for (ALL_LIST_ELEMENTS (root->children, node, nnode, child))
  139. {
  140. struct listnode *n2, *nn2;
  141. struct vertex_parent *vp;
  142. /* router vertices through an attached network each
  143. * have a distinct (canonical / not inherited) nexthop
  144. * which must be freed.
  145. *
  146. * A network vertex can only have router vertices as its
  147. * children, so only one level of recursion is possible.
  148. */
  149. if (child->type == OSPF_VERTEX_NETWORK)
  150. ospf_canonical_nexthops_free (child);
  151. /* Free child nexthops pointing back to this root vertex */
  152. for (ALL_LIST_ELEMENTS (child->parents, n2, nn2, vp))
  153. if (vp->parent == root && vp->nexthop)
  154. vertex_nexthop_free (vp->nexthop);
  155. }
  156. }
  157. /* TODO: Parent list should be excised, in favour of maintaining only
  158. * vertex_nexthop, with refcounts.
  159. */
  160. static struct vertex_parent *
  161. vertex_parent_new (struct vertex *v, int backlink, struct vertex_nexthop *hop)
  162. {
  163. struct vertex_parent *new;
  164. new = XMALLOC (MTYPE_OSPF_VERTEX_PARENT, sizeof (struct vertex_parent));
  165. if (new == NULL)
  166. return NULL;
  167. new->parent = v;
  168. new->backlink = backlink;
  169. new->nexthop = hop;
  170. return new;
  171. }
  172. static void
  173. vertex_parent_free (void *p)
  174. {
  175. XFREE (MTYPE_OSPF_VERTEX_PARENT, p);
  176. }
  177. static struct vertex *
  178. ospf_vertex_new (struct ospf_lsa *lsa)
  179. {
  180. struct vertex *new;
  181. new = XCALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex));
  182. new->flags = 0;
  183. new->stat = &(lsa->stat);
  184. new->type = lsa->data->type;
  185. new->id = lsa->data->id;
  186. new->lsa = lsa->data;
  187. new->children = list_new ();
  188. new->parents = list_new ();
  189. new->parents->del = vertex_parent_free;
  190. listnode_add (&vertex_list, new);
  191. if (IS_DEBUG_OSPF_EVENT)
  192. zlog_debug ("%s: Created %s vertex %s", __func__,
  193. new->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
  194. inet_ntoa (new->lsa->id));
  195. return new;
  196. }
  197. static void
  198. ospf_vertex_free (void *data)
  199. {
  200. struct vertex *v = data;
  201. if (IS_DEBUG_OSPF_EVENT)
  202. zlog_debug ("%s: Free %s vertex %s", __func__,
  203. v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
  204. inet_ntoa (v->lsa->id));
  205. /* There should be no parents potentially holding references to this vertex
  206. * Children however may still be there, but presumably referenced by other
  207. * vertices
  208. */
  209. //assert (listcount (v->parents) == 0);
  210. if (v->children)
  211. list_delete (v->children);
  212. v->children = NULL;
  213. if (v->parents)
  214. list_delete (v->parents);
  215. v->parents = NULL;
  216. v->lsa = NULL;
  217. XFREE (MTYPE_OSPF_VERTEX, v);
  218. }
  219. static void
  220. ospf_vertex_dump(const char *msg, struct vertex *v,
  221. int print_parents, int print_children)
  222. {
  223. if ( ! IS_DEBUG_OSPF_EVENT)
  224. return;
  225. zlog_debug("%s %s vertex %s distance %u flags %u",
  226. msg,
  227. v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
  228. inet_ntoa(v->lsa->id),
  229. v->distance,
  230. (unsigned int)v->flags);
  231. if (print_parents)
  232. {
  233. struct listnode *node;
  234. struct vertex_parent *vp;
  235. for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
  236. {
  237. char buf1[BUFSIZ];
  238. if (vp)
  239. {
  240. zlog_debug ("parent %s backlink %d nexthop %s interface %s",
  241. inet_ntoa(vp->parent->lsa->id), vp->backlink,
  242. inet_ntop(AF_INET, &vp->nexthop->router, buf1, BUFSIZ),
  243. vp->nexthop->oi ? IF_NAME(vp->nexthop->oi) : "NULL");
  244. }
  245. }
  246. }
  247. if (print_children)
  248. {
  249. struct listnode *cnode;
  250. struct vertex *cv;
  251. for (ALL_LIST_ELEMENTS_RO (v->children, cnode, cv))
  252. ospf_vertex_dump(" child:", cv, 0, 0);
  253. }
  254. }
  255. /* Add a vertex to the list of children in each of its parents. */
  256. static void
  257. ospf_vertex_add_parent (struct vertex *v)
  258. {
  259. struct vertex_parent *vp;
  260. struct listnode *node;
  261. assert (v && v->parents);
  262. for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
  263. {
  264. assert (vp->parent && vp->parent->children);
  265. /* No need to add two links from the same parent. */
  266. if (listnode_lookup (vp->parent->children, v) == NULL)
  267. listnode_add (vp->parent->children, v);
  268. }
  269. }
  270. static void
  271. ospf_spf_init (struct ospf_area *area)
  272. {
  273. struct vertex *v;
  274. /* Create root node. */
  275. v = ospf_vertex_new (area->router_lsa_self);
  276. area->spf = v;
  277. /* Reset ABR and ASBR router counts. */
  278. area->abr_count = 0;
  279. area->asbr_count = 0;
  280. }
  281. /* return index of link back to V from W, or -1 if no link found */
  282. static int
  283. ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v)
  284. {
  285. unsigned int i, length;
  286. struct router_lsa *rl;
  287. struct network_lsa *nl;
  288. /* In case of W is Network LSA. */
  289. if (w->type == OSPF_NETWORK_LSA)
  290. {
  291. if (v->type == OSPF_NETWORK_LSA)
  292. return -1;
  293. nl = (struct network_lsa *) w;
  294. length = (ntohs (w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;
  295. for (i = 0; i < length; i++)
  296. if (IPV4_ADDR_SAME (&nl->routers[i], &v->id))
  297. return i;
  298. return -1;
  299. }
  300. /* In case of W is Router LSA. */
  301. if (w->type == OSPF_ROUTER_LSA)
  302. {
  303. rl = (struct router_lsa *) w;
  304. length = ntohs (w->length);
  305. for (i = 0;
  306. i < ntohs (rl->links) && length >= sizeof (struct router_lsa);
  307. i++, length -= 12)
  308. {
  309. switch (rl->link[i].type)
  310. {
  311. case LSA_LINK_TYPE_POINTOPOINT:
  312. case LSA_LINK_TYPE_VIRTUALLINK:
  313. /* Router LSA ID. */
  314. if (v->type == OSPF_ROUTER_LSA &&
  315. IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
  316. {
  317. return i;
  318. }
  319. break;
  320. case LSA_LINK_TYPE_TRANSIT:
  321. /* Network LSA ID. */
  322. if (v->type == OSPF_NETWORK_LSA &&
  323. IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
  324. {
  325. return i;
  326. }
  327. break;
  328. case LSA_LINK_TYPE_STUB:
  329. /* Stub can't lead anywhere, carry on */
  330. continue;
  331. default:
  332. break;
  333. }
  334. }
  335. }
  336. return -1;
  337. }
  338. /* Find the next link after prev_link from v to w. If prev_link is
  339. * NULL, return the first link from v to w. Ignore stub and virtual links;
  340. * these link types will never be returned.
  341. */
  342. static struct router_lsa_link *
  343. ospf_get_next_link (struct vertex *v, struct vertex *w,
  344. struct router_lsa_link *prev_link)
  345. {
  346. u_char *p;
  347. u_char *lim;
  348. u_char lsa_type = LSA_LINK_TYPE_TRANSIT;
  349. struct router_lsa_link *l;
  350. if (w->type == OSPF_VERTEX_ROUTER)
  351. lsa_type = LSA_LINK_TYPE_POINTOPOINT;
  352. if (prev_link == NULL)
  353. p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
  354. else
  355. {
  356. p = (u_char *) prev_link;
  357. p += (OSPF_ROUTER_LSA_LINK_SIZE +
  358. (prev_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
  359. }
  360. lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
  361. while (p < lim)
  362. {
  363. l = (struct router_lsa_link *) p;
  364. p += (OSPF_ROUTER_LSA_LINK_SIZE + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
  365. if (l->m[0].type != lsa_type)
  366. continue;
  367. if (IPV4_ADDR_SAME (&l->link_id, &w->id))
  368. return l;
  369. }
  370. return NULL;
  371. }
  372. static void
  373. ospf_spf_flush_parents (struct vertex *w)
  374. {
  375. struct vertex_parent *vp;
  376. struct listnode *ln, *nn;
  377. /* delete the existing nexthops */
  378. for (ALL_LIST_ELEMENTS (w->parents, ln, nn, vp))
  379. {
  380. list_delete_node (w->parents, ln);
  381. vertex_parent_free (vp);
  382. }
  383. }
  384. /*
  385. * Consider supplied next-hop for inclusion to the supplied list of
  386. * equal-cost next-hops, adjust list as neccessary.
  387. */
  388. static void
  389. ospf_spf_add_parent (struct vertex *v, struct vertex *w,
  390. struct vertex_nexthop *newhop,
  391. unsigned int distance)
  392. {
  393. struct vertex_parent *vp, *wp;
  394. struct listnode *node;
  395. /* we must have a newhop, and a distance */
  396. assert (v && w && newhop);
  397. assert (distance);
  398. /* IFF w has already been assigned a distance, then we shouldn't get here
  399. * unless callers have determined V(l)->W is shortest / equal-shortest
  400. * path (0 is a special case distance (no distance yet assigned)).
  401. */
  402. if (w->distance)
  403. assert (distance <= w->distance);
  404. else
  405. w->distance = distance;
  406. if (IS_DEBUG_OSPF_EVENT)
  407. {
  408. char buf[2][INET_ADDRSTRLEN];
  409. zlog_debug ("%s: Adding %s as parent of %s",
  410. __func__,
  411. inet_ntop(AF_INET, &v->lsa->id, buf[0], sizeof(buf[0])),
  412. inet_ntop(AF_INET, &w->lsa->id, buf[1], sizeof(buf[1])));
  413. }
  414. /* Adding parent for a new, better path: flush existing parents from W. */
  415. if (distance < w->distance)
  416. {
  417. if (IS_DEBUG_OSPF_EVENT)
  418. zlog_debug ("%s: distance %d better than %d, flushing existing parents",
  419. __func__, distance, w->distance);
  420. ospf_spf_flush_parents (w);
  421. w->distance = distance;
  422. }
  423. /* new parent is <= existing parents, add it to parent list (if nexthop
  424. * not on parent list)
  425. */
  426. for (ALL_LIST_ELEMENTS_RO(w->parents, node, wp))
  427. {
  428. if (memcmp(newhop, wp->nexthop, sizeof(*newhop)) == 0)
  429. {
  430. if (IS_DEBUG_OSPF_EVENT)
  431. zlog_debug ("%s: ... nexthop already on parent list, skipping add", __func__);
  432. return;
  433. }
  434. }
  435. vp = vertex_parent_new (v, ospf_lsa_has_link (w->lsa, v->lsa), newhop);
  436. listnode_add (w->parents, vp);
  437. return;
  438. }
  439. /* 16.1.1. Calculate nexthop from root through V (parent) to
  440. * vertex W (destination), with given distance from root->W.
  441. *
  442. * The link must be supplied if V is the root vertex. In all other cases
  443. * it may be NULL.
  444. *
  445. * Note that this function may fail, hence the state of the destination
  446. * vertex, W, should /not/ be modified in a dependent manner until
  447. * this function returns. This function will update the W vertex with the
  448. * provided distance as appropriate.
  449. */
  450. static unsigned int
  451. ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
  452. struct vertex *w, struct router_lsa_link *l,
  453. unsigned int distance, int lsa_pos)
  454. {
  455. struct listnode *node, *nnode;
  456. struct vertex_nexthop *nh;
  457. struct vertex_parent *vp;
  458. struct ospf_interface *oi = NULL;
  459. unsigned int added = 0;
  460. char buf1[BUFSIZ];
  461. char buf2[BUFSIZ];
  462. if (IS_DEBUG_OSPF_EVENT)
  463. {
  464. zlog_debug ("ospf_nexthop_calculation(): Start");
  465. ospf_vertex_dump("V (parent):", v, 1, 1);
  466. ospf_vertex_dump("W (dest) :", w, 1, 1);
  467. zlog_debug ("V->W distance: %d", distance);
  468. }
  469. if (v == area->spf)
  470. {
  471. /* 16.1.1 para 4. In the first case, the parent vertex (V) is the
  472. root (the calculating router itself). This means that the
  473. destination is either a directly connected network or directly
  474. connected router. The outgoing interface in this case is simply
  475. the OSPF interface connecting to the destination network/router.
  476. */
  477. /* we *must* be supplied with the link data */
  478. assert (l != NULL);
  479. oi = ospf_if_lookup_by_lsa_pos (area, lsa_pos);
  480. if (!oi)
  481. {
  482. zlog_debug("%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
  483. __func__, lsa_pos,
  484. inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
  485. inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
  486. return 0;
  487. }
  488. if (IS_DEBUG_OSPF_EVENT)
  489. {
  490. zlog_debug("%s: considering link:%s "
  491. "type:%d link_id:%s link_data:%s",
  492. __func__, oi->ifp->name, l->m[0].type,
  493. inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
  494. inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
  495. }
  496. if (w->type == OSPF_VERTEX_ROUTER)
  497. {
  498. /* l is a link from v to w
  499. * l2 will be link from w to v
  500. */
  501. struct router_lsa_link *l2 = NULL;
  502. if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
  503. {
  504. struct in_addr nexthop = { .s_addr = 0 };
  505. /* If the destination is a router which connects to
  506. the calculating router via a Point-to-MultiPoint
  507. network, the destination's next hop IP address(es)
  508. can be determined by examining the destination's
  509. router-LSA: each link pointing back to the
  510. calculating router and having a Link Data field
  511. belonging to the Point-to-MultiPoint network
  512. provides an IP address of the next hop router.
  513. At this point l is a link from V to W, and V is the
  514. root ("us"). If it is a point-to-multipoint interface,
  515. then look through the links in the opposite direction (W to V).
  516. If any of them have an address that lands within the
  517. subnet declared by the PtMP link, then that link
  518. is a constituent of the PtMP link, and its address is
  519. a nexthop address for V.
  520. */
  521. if (oi->type == OSPF_IFTYPE_POINTOPOINT)
  522. {
  523. /* Having nexthop = 0 is tempting, but NOT acceptable.
  524. It breaks AS-External routes with a forwarding address,
  525. since ospf_ase_complete_direct_routes() will mistakenly
  526. assume we've reached the last hop and should place the
  527. forwarding address as nexthop.
  528. Also, users may configure multi-access links in p2p mode,
  529. so we need the IP to ARP the nexthop.
  530. */
  531. struct ospf_neighbor *nbr_w;
  532. nbr_w = ospf_nbr_lookup_by_routerid (oi->nbrs, &l->link_id);
  533. if (nbr_w != NULL)
  534. {
  535. added = 1;
  536. nexthop = nbr_w->src;
  537. }
  538. }
  539. else if (oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
  540. {
  541. struct prefix_ipv4 la;
  542. la.family = AF_INET;
  543. la.prefixlen = oi->address->prefixlen;
  544. /* V links to W on PtMP interface
  545. - find the interface address on W */
  546. while ((l2 = ospf_get_next_link (w, v, l2)))
  547. {
  548. la.prefix = l2->link_data;
  549. if (prefix_cmp ((struct prefix *) &la,
  550. oi->address) != 0)
  551. continue;
  552. /* link_data is on our PtMP network */
  553. added = 1;
  554. nexthop = l2->link_data;
  555. break;
  556. }
  557. }
  558. if (added)
  559. {
  560. /* found all necessary info to build nexthop */
  561. nh = vertex_nexthop_new ();
  562. nh->oi = oi;
  563. nh->router = nexthop;
  564. ospf_spf_add_parent (v, w, nh, distance);
  565. return 1;
  566. }
  567. else
  568. zlog_info("%s: could not determine nexthop for link %s",
  569. __func__, oi->ifp->name);
  570. } /* end point-to-point link from V to W */
  571. else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
  572. {
  573. struct ospf_vl_data *vl_data;
  574. /* VLink implementation limitations:
  575. * a) vl_data can only reference one nexthop, so no ECMP
  576. * to backbone through VLinks. Though transit-area
  577. * summaries may be considered, and those can be ECMP.
  578. * b) We can only use /one/ VLink, even if multiple ones
  579. * exist this router through multiple transit-areas.
  580. */
  581. vl_data = ospf_vl_lookup (area->ospf, NULL, l->link_id);
  582. if (vl_data
  583. && CHECK_FLAG (vl_data->flags, OSPF_VL_FLAG_APPROVED))
  584. {
  585. nh = vertex_nexthop_new ();
  586. nh->oi = vl_data->nexthop.oi;
  587. nh->router = vl_data->nexthop.router;
  588. ospf_spf_add_parent (v, w, nh, distance);
  589. return 1;
  590. }
  591. else
  592. zlog_info("ospf_nexthop_calculation(): "
  593. "vl_data for VL link not found");
  594. } /* end virtual-link from V to W */
  595. return 0;
  596. } /* end W is a Router vertex */
  597. else
  598. {
  599. assert(w->type == OSPF_VERTEX_NETWORK);
  600. nh = vertex_nexthop_new ();
  601. nh->oi = oi;
  602. nh->router.s_addr = 0; /* Nexthop not required */
  603. ospf_spf_add_parent (v, w, nh, distance);
  604. return 1;
  605. }
  606. } /* end V is the root */
  607. /* Check if W's parent is a network connected to root. */
  608. else if (v->type == OSPF_VERTEX_NETWORK)
  609. {
  610. /* See if any of V's parents are the root. */
  611. for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
  612. {
  613. if (vp->parent == area->spf) /* connects to root? */
  614. {
  615. /* 16.1.1 para 5. ...the parent vertex is a network that
  616. * directly connects the calculating router to the destination
  617. * router. The list of next hops is then determined by
  618. * examining the destination's router-LSA...
  619. */
  620. assert(w->type == OSPF_VERTEX_ROUTER);
  621. while ((l = ospf_get_next_link (w, v, l)))
  622. {
  623. /* ...For each link in the router-LSA that points back to the
  624. * parent network, the link's Link Data field provides the IP
  625. * address of a next hop router. The outgoing interface to
  626. * use can then be derived from the next hop IP address (or
  627. * it can be inherited from the parent network).
  628. */
  629. nh = vertex_nexthop_new ();
  630. nh->oi = vp->nexthop->oi;
  631. nh->router = l->link_data;
  632. added = 1;
  633. ospf_spf_add_parent (v, w, nh, distance);
  634. }
  635. /* Note lack of return is deliberate. See next comment. */
  636. }
  637. }
  638. /* NB: This code is non-trivial.
  639. *
  640. * E.g. it is not enough to know that V connects to the root. It is
  641. * also important that the while above, looping through all links from
  642. * W->V found at least one link, so that we know there is
  643. * bi-directional connectivity between V and W (which need not be the
  644. * case, e.g. when OSPF has not yet converged fully). Otherwise, if
  645. * we /always/ return here, without having checked that root->V->-W
  646. * actually resulted in a valid nexthop being created, then we we will
  647. * prevent SPF from finding/using higher cost paths.
  648. *
  649. * It is important, if root->V->W has not been added, that we continue
  650. * through to the intervening-router nexthop code below. So as to
  651. * ensure other paths to V may be used. This avoids unnecessary
  652. * blackholes while OSPF is convergening.
  653. *
  654. * I.e. we may have arrived at this function, examining V -> W, via
  655. * workable paths other than root -> V, and it's important to avoid
  656. * getting "confused" by non-working root->V->W path - it's important
  657. * to *not* lose the working non-root paths, just because of a
  658. * non-viable root->V->W.
  659. *
  660. * See also bug #330 (required reading!), and:
  661. *
  662. * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
  663. */
  664. if (added)
  665. return added;
  666. }
  667. /* 16.1.1 para 4. If there is at least one intervening router in the
  668. * current shortest path between the destination and the root, the
  669. * destination simply inherits the set of next hops from the
  670. * parent.
  671. */
  672. if (IS_DEBUG_OSPF_EVENT)
  673. zlog_debug ("%s: Intervening routers, adding parent(s)", __func__);
  674. for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
  675. {
  676. added = 1;
  677. ospf_spf_add_parent (v, w, vp->nexthop, distance);
  678. }
  679. return added;
  680. }
  681. /* RFC2328 Section 16.1 (2).
  682. * v is on the SPF tree. Examine the links in v's LSA. Update the list
  683. * of candidates with any vertices not already on the list. If a lower-cost
  684. * path is found to a vertex already on the candidate list, store the new cost.
  685. */
  686. static void
  687. ospf_spf_next (struct vertex *v, struct ospf_area *area,
  688. struct pqueue * candidate)
  689. {
  690. struct ospf_lsa *w_lsa = NULL;
  691. u_char *p;
  692. u_char *lim;
  693. struct router_lsa_link *l = NULL;
  694. struct in_addr *r;
  695. int type = 0, lsa_pos=-1, lsa_pos_next=0;
  696. /* If this is a router-LSA, and bit V of the router-LSA (see Section
  697. A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
  698. if (v->type == OSPF_VERTEX_ROUTER)
  699. {
  700. if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa))
  701. area->transit = OSPF_TRANSIT_TRUE;
  702. }
  703. if (IS_DEBUG_OSPF_EVENT)
  704. zlog_debug ("%s: Next vertex of %s vertex %s",
  705. __func__,
  706. v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
  707. inet_ntoa(v->lsa->id));
  708. p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
  709. lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
  710. while (p < lim)
  711. {
  712. struct vertex *w;
  713. unsigned int distance;
  714. /* In case of V is Router-LSA. */
  715. if (v->lsa->type == OSPF_ROUTER_LSA)
  716. {
  717. l = (struct router_lsa_link *) p;
  718. lsa_pos = lsa_pos_next; /* LSA link position */
  719. lsa_pos_next++;
  720. p += (OSPF_ROUTER_LSA_LINK_SIZE +
  721. (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
  722. /* (a) If this is a link to a stub network, examine the next
  723. link in V's LSA. Links to stub networks will be
  724. considered in the second stage of the shortest path
  725. calculation. */
  726. if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
  727. continue;
  728. /* Infinite distance links shouldn't be followed, except
  729. * for local links (a stub-routed router still wants to
  730. * calculate tree, so must follow its own links).
  731. */
  732. if ((v != area->spf) && l->m[0].metric >= OSPF_OUTPUT_COST_INFINITE)
  733. continue;
  734. /* (b) Otherwise, W is a transit vertex (router or transit
  735. network). Look up the vertex W's LSA (router-LSA or
  736. network-LSA) in Area A's link state database. */
  737. switch (type)
  738. {
  739. case LSA_LINK_TYPE_POINTOPOINT:
  740. case LSA_LINK_TYPE_VIRTUALLINK:
  741. if (type == LSA_LINK_TYPE_VIRTUALLINK)
  742. {
  743. if (IS_DEBUG_OSPF_EVENT)
  744. zlog_debug ("looking up LSA through VL: %s",
  745. inet_ntoa (l->link_id));
  746. }
  747. w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id,
  748. l->link_id);
  749. if (w_lsa)
  750. {
  751. if (IS_DEBUG_OSPF_EVENT)
  752. zlog_debug ("found Router LSA %s", inet_ntoa (l->link_id));
  753. }
  754. break;
  755. case LSA_LINK_TYPE_TRANSIT:
  756. if (IS_DEBUG_OSPF_EVENT)
  757. zlog_debug ("Looking up Network LSA, ID: %s",
  758. inet_ntoa (l->link_id));
  759. w_lsa = ospf_lsa_lookup_by_id (area, OSPF_NETWORK_LSA,
  760. l->link_id);
  761. if (w_lsa)
  762. if (IS_DEBUG_OSPF_EVENT)
  763. zlog_debug ("found the LSA");
  764. break;
  765. default:
  766. zlog_warn ("Invalid LSA link type %d", type);
  767. continue;
  768. }
  769. }
  770. else
  771. {
  772. /* In case of V is Network-LSA. */
  773. r = (struct in_addr *) p;
  774. p += sizeof (struct in_addr);
  775. /* Lookup the vertex W's LSA. */
  776. w_lsa = ospf_lsa_lookup_by_id (area, OSPF_ROUTER_LSA, *r);
  777. if (w_lsa)
  778. {
  779. if (IS_DEBUG_OSPF_EVENT)
  780. zlog_debug ("found Router LSA %s", inet_ntoa (w_lsa->data->id));
  781. }
  782. }
  783. /* (b cont.) If the LSA does not exist, or its LS age is equal
  784. to MaxAge, or it does not have a link back to vertex V,
  785. examine the next link in V's LSA.[23] */
  786. if (w_lsa == NULL)
  787. {
  788. if (IS_DEBUG_OSPF_EVENT)
  789. zlog_debug ("No LSA found");
  790. continue;
  791. }
  792. if (IS_LSA_MAXAGE (w_lsa))
  793. {
  794. if (IS_DEBUG_OSPF_EVENT)
  795. zlog_debug ("LSA is MaxAge");
  796. continue;
  797. }
  798. if (ospf_lsa_has_link (w_lsa->data, v->lsa) < 0 )
  799. {
  800. if (IS_DEBUG_OSPF_EVENT)
  801. zlog_debug ("The LSA doesn't have a link back");
  802. continue;
  803. }
  804. /* (c) If vertex W is already on the shortest-path tree, examine
  805. the next link in the LSA. */
  806. if (w_lsa->stat == LSA_SPF_IN_SPFTREE)
  807. {
  808. if (IS_DEBUG_OSPF_EVENT)
  809. zlog_debug ("The LSA is already in SPF");
  810. continue;
  811. }
  812. /* (d) Calculate the link state cost D of the resulting path
  813. from the root to vertex W. D is equal to the sum of the link
  814. state cost of the (already calculated) shortest path to
  815. vertex V and the advertised cost of the link between vertices
  816. V and W. If D is: */
  817. /* calculate link cost D. */
  818. if (v->lsa->type == OSPF_ROUTER_LSA)
  819. distance = v->distance + ntohs (l->m[0].metric);
  820. else /* v is not a Router-LSA */
  821. distance = v->distance;
  822. /* Is there already vertex W in candidate list? */
  823. if (w_lsa->stat == LSA_SPF_NOT_EXPLORED)
  824. {
  825. /* prepare vertex W. */
  826. w = ospf_vertex_new (w_lsa);
  827. /* Calculate nexthop to W. */
  828. if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos))
  829. pqueue_enqueue (w, candidate);
  830. else if (IS_DEBUG_OSPF_EVENT)
  831. zlog_debug ("Nexthop Calc failed");
  832. }
  833. else if (w_lsa->stat >= 0)
  834. {
  835. /* Get the vertex from candidates. */
  836. w = candidate->array[w_lsa->stat];
  837. /* if D is greater than. */
  838. if (w->distance < distance)
  839. {
  840. continue;
  841. }
  842. /* equal to. */
  843. else if (w->distance == distance)
  844. {
  845. /* Found an equal-cost path to W.
  846. * Calculate nexthop of to W from V. */
  847. ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos);
  848. }
  849. /* less than. */
  850. else
  851. {
  852. /* Found a lower-cost path to W.
  853. * nexthop_calculation is conditional, if it finds
  854. * valid nexthop it will call spf_add_parents, which
  855. * will flush the old parents
  856. */
  857. if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos))
  858. /* Decrease the key of the node in the heap.
  859. * trickle-sort it up towards root, just in case this
  860. * node should now be the new root due the cost change.
  861. * (next pqueu_{de,en}queue will fully re-heap the queue).
  862. */
  863. trickle_up (w_lsa->stat, candidate);
  864. }
  865. } /* end W is already on the candidate list */
  866. } /* end loop over the links in V's LSA */
  867. }
  868. static void
  869. ospf_spf_dump (struct vertex *v, int i)
  870. {
  871. struct listnode *cnode;
  872. struct listnode *nnode;
  873. struct vertex_parent *parent;
  874. if (v->type == OSPF_VERTEX_ROUTER)
  875. {
  876. if (IS_DEBUG_OSPF_EVENT)
  877. zlog_debug ("SPF Result: %d [R] %s", i, inet_ntoa (v->lsa->id));
  878. }
  879. else
  880. {
  881. struct network_lsa *lsa = (struct network_lsa *) v->lsa;
  882. if (IS_DEBUG_OSPF_EVENT)
  883. zlog_debug ("SPF Result: %d [N] %s/%d", i, inet_ntoa (v->lsa->id),
  884. ip_masklen (lsa->mask));
  885. }
  886. if (IS_DEBUG_OSPF_EVENT)
  887. for (ALL_LIST_ELEMENTS_RO (v->parents, nnode, parent))
  888. {
  889. zlog_debug (" nexthop %p %s %s",
  890. (void *)parent->nexthop,
  891. inet_ntoa (parent->nexthop->router),
  892. parent->nexthop->oi ? IF_NAME(parent->nexthop->oi)
  893. : "NULL");
  894. }
  895. i++;
  896. for (ALL_LIST_ELEMENTS_RO (v->children, cnode, v))
  897. ospf_spf_dump (v, i);
  898. }
  899. /* Second stage of SPF calculation. */
  900. static void
  901. ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v,
  902. struct route_table *rt,
  903. int parent_is_root)
  904. {
  905. struct listnode *cnode, *cnnode;
  906. struct vertex *child;
  907. if (IS_DEBUG_OSPF_EVENT)
  908. zlog_debug ("ospf_process_stub():processing stubs for area %s",
  909. inet_ntoa (area->area_id));
  910. if (v->type == OSPF_VERTEX_ROUTER)
  911. {
  912. u_char *p;
  913. u_char *lim;
  914. struct router_lsa_link *l;
  915. struct router_lsa *rlsa;
  916. int lsa_pos = 0;
  917. if (IS_DEBUG_OSPF_EVENT)
  918. zlog_debug ("ospf_process_stubs():processing router LSA, id: %s",
  919. inet_ntoa (v->lsa->id));
  920. rlsa = (struct router_lsa *) v->lsa;
  921. if (IS_DEBUG_OSPF_EVENT)
  922. zlog_debug ("ospf_process_stubs(): we have %d links to process",
  923. ntohs (rlsa->links));
  924. p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
  925. lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
  926. while (p < lim)
  927. {
  928. l = (struct router_lsa_link *) p;
  929. p += (OSPF_ROUTER_LSA_LINK_SIZE +
  930. (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
  931. if (l->m[0].type == LSA_LINK_TYPE_STUB)
  932. ospf_intra_add_stub (rt, l, v, area, parent_is_root, lsa_pos);
  933. lsa_pos++;
  934. }
  935. }
  936. ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1, 1);
  937. for (ALL_LIST_ELEMENTS (v->children, cnode, cnnode, child))
  938. {
  939. if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED))
  940. continue;
  941. /* the first level of routers connected to the root
  942. * should have 'parent_is_root' set, including those
  943. * connected via a network vertex.
  944. */
  945. if (area->spf == v)
  946. parent_is_root = 1;
  947. else if (v->type == OSPF_VERTEX_ROUTER)
  948. parent_is_root = 0;
  949. ospf_spf_process_stubs (area, child, rt, parent_is_root);
  950. SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED);
  951. }
  952. }
  953. void
  954. ospf_rtrs_free (struct route_table *rtrs)
  955. {
  956. struct route_node *rn;
  957. struct list *or_list;
  958. struct ospf_route *or;
  959. struct listnode *node, *nnode;
  960. if (IS_DEBUG_OSPF_EVENT)
  961. zlog_debug ("Route: Router Routing Table free");
  962. for (rn = route_top (rtrs); rn; rn = route_next (rn))
  963. if ((or_list = rn->info) != NULL)
  964. {
  965. for (ALL_LIST_ELEMENTS (or_list, node, nnode, or))
  966. ospf_route_free (or);
  967. list_delete (or_list);
  968. /* Unlock the node. */
  969. rn->info = NULL;
  970. route_unlock_node (rn);
  971. }
  972. route_table_finish (rtrs);
  973. }
  974. #if 0
  975. static void
  976. ospf_rtrs_print (struct route_table *rtrs)
  977. {
  978. struct route_node *rn;
  979. struct list *or_list;
  980. struct listnode *ln;
  981. struct listnode *pnode;
  982. struct ospf_route *or;
  983. struct ospf_path *path;
  984. char buf1[BUFSIZ];
  985. char buf2[BUFSIZ];
  986. if (IS_DEBUG_OSPF_EVENT)
  987. zlog_debug ("ospf_rtrs_print() start");
  988. for (rn = route_top (rtrs); rn; rn = route_next (rn))
  989. if ((or_list = rn->info) != NULL)
  990. for (ALL_LIST_ELEMENTS_RO (or_list, ln, or))
  991. {
  992. switch (or->path_type)
  993. {
  994. case OSPF_PATH_INTRA_AREA:
  995. if (IS_DEBUG_OSPF_EVENT)
  996. zlog_debug ("%s [%d] area: %s",
  997. inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
  998. or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
  999. buf2, BUFSIZ));
  1000. break;
  1001. case OSPF_PATH_INTER_AREA:
  1002. if (IS_DEBUG_OSPF_EVENT)
  1003. zlog_debug ("%s IA [%d] area: %s",
  1004. inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
  1005. or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
  1006. buf2, BUFSIZ));
  1007. break;
  1008. default:
  1009. break;
  1010. }
  1011. for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path))
  1012. {
  1013. if (path->nexthop.s_addr == 0)
  1014. {
  1015. if (IS_DEBUG_OSPF_EVENT)
  1016. zlog_debug (" directly attached to %s\r\n",
  1017. ifindex2ifname (path->ifindex));
  1018. }
  1019. else
  1020. {
  1021. if (IS_DEBUG_OSPF_EVENT)
  1022. zlog_debug (" via %s, %s\r\n",
  1023. inet_ntoa (path->nexthop),
  1024. ifindex2ifname (path->ifindex));
  1025. }
  1026. }
  1027. }
  1028. zlog_debug ("ospf_rtrs_print() end");
  1029. }
  1030. #endif
  1031. /* Calculating the shortest-path tree for an area. */
  1032. static void
  1033. ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table,
  1034. struct route_table *new_rtrs)
  1035. {
  1036. struct pqueue *candidate;
  1037. struct vertex *v;
  1038. if (IS_DEBUG_OSPF_EVENT)
  1039. {
  1040. zlog_debug ("ospf_spf_calculate: Start");
  1041. zlog_debug ("ospf_spf_calculate: running Dijkstra for area %s",
  1042. inet_ntoa (area->area_id));
  1043. }
  1044. /* Check router-lsa-self. If self-router-lsa is not yet allocated,
  1045. return this area's calculation. */
  1046. if (!area->router_lsa_self)
  1047. {
  1048. if (IS_DEBUG_OSPF_EVENT)
  1049. zlog_debug ("ospf_spf_calculate: "
  1050. "Skip area %s's calculation due to empty router_lsa_self",
  1051. inet_ntoa (area->area_id));
  1052. return;
  1053. }
  1054. /* RFC2328 16.1. (1). */
  1055. /* Initialize the algorithm's data structures. */
  1056. /* This function scans all the LSA database and set the stat field to
  1057. * LSA_SPF_NOT_EXPLORED. */
  1058. ospf_lsdb_clean_stat (area->lsdb);
  1059. /* Create a new heap for the candidates. */
  1060. candidate = pqueue_create();
  1061. candidate->cmp = cmp;
  1062. candidate->update = update_stat;
  1063. /* Initialize the shortest-path tree to only the root (which is the
  1064. router doing the calculation). */
  1065. ospf_spf_init (area);
  1066. v = area->spf;
  1067. /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the
  1068. * spanning tree. */
  1069. *(v->stat) = LSA_SPF_IN_SPFTREE;
  1070. /* Set Area A's TransitCapability to FALSE. */
  1071. area->transit = OSPF_TRANSIT_FALSE;
  1072. area->shortcut_capability = 1;
  1073. for (;;)
  1074. {
  1075. /* RFC2328 16.1. (2). */
  1076. ospf_spf_next (v, area, candidate);
  1077. /* RFC2328 16.1. (3). */
  1078. /* If at this step the candidate list is empty, the shortest-
  1079. path tree (of transit vertices) has been completely built and
  1080. this stage of the procedure terminates. */
  1081. if (candidate->size == 0)
  1082. break;
  1083. /* Otherwise, choose the vertex belonging to the candidate list
  1084. that is closest to the root, and add it to the shortest-path
  1085. tree (removing it from the candidate list in the
  1086. process). */
  1087. /* Extract from the candidates the node with the lower key. */
  1088. v = (struct vertex *) pqueue_dequeue (candidate);
  1089. /* Update stat field in vertex. */
  1090. *(v->stat) = LSA_SPF_IN_SPFTREE;
  1091. ospf_vertex_add_parent (v);
  1092. /* RFC2328 16.1. (4). */
  1093. if (v->type == OSPF_VERTEX_ROUTER)
  1094. ospf_intra_add_router (new_rtrs, v, area);
  1095. else
  1096. ospf_intra_add_transit (new_table, v, area);
  1097. /* RFC2328 16.1. (5). */
  1098. /* Iterate the algorithm by returning to Step 2. */
  1099. } /* end loop until no more candidate vertices */
  1100. if (IS_DEBUG_OSPF_EVENT)
  1101. {
  1102. ospf_spf_dump (area->spf, 0);
  1103. ospf_route_table_dump (new_table);
  1104. }
  1105. /* Second stage of SPF calculation procedure's */
  1106. ospf_spf_process_stubs (area, area->spf, new_table, 0);
  1107. /* Free candidate queue. */
  1108. pqueue_delete (candidate);
  1109. ospf_vertex_dump (__func__, area->spf, 0, 1);
  1110. /* Free nexthop information, canonical versions of which are attached
  1111. * the first level of router vertices attached to the root vertex, see
  1112. * ospf_nexthop_calculation.
  1113. */
  1114. ospf_canonical_nexthops_free (area->spf);
  1115. /* Increment SPF Calculation Counter. */
  1116. area->spf_calculation++;
  1117. quagga_gettime (QUAGGA_CLK_MONOTONIC, &area->ospf->ts_spf);
  1118. area->ts_spf = area->ospf->ts_spf;
  1119. if (IS_DEBUG_OSPF_EVENT)
  1120. zlog_debug ("ospf_spf_calculate: Stop. %zd vertices",
  1121. mtype_stats_alloc(MTYPE_OSPF_VERTEX));
  1122. /* Free SPF vertices, but not the list. List has ospf_vertex_free
  1123. * as deconstructor.
  1124. */
  1125. list_delete_all_node (&vertex_list);
  1126. }
  1127. /* Timer for SPF calculation. */
  1128. static int
  1129. ospf_spf_calculate_timer (struct thread *thread)
  1130. {
  1131. struct ospf *ospf = THREAD_ARG (thread);
  1132. struct route_table *new_table, *new_rtrs;
  1133. struct ospf_area *area;
  1134. struct listnode *node, *nnode;
  1135. struct timeval start_time, stop_time, spf_start_time;
  1136. int areas_processed = 0;
  1137. unsigned long ia_time, prune_time, rt_time;
  1138. unsigned long abr_time, total_spf_time, spf_time;
  1139. char rbuf[32]; /* reason_buf */
  1140. if (IS_DEBUG_OSPF_EVENT)
  1141. zlog_debug ("SPF: Timer (SPF calculation expire)");
  1142. ospf->t_spf_calc = NULL;
  1143. quagga_gettime (QUAGGA_CLK_MONOTONIC, &spf_start_time);
  1144. /* Allocate new table tree. */
  1145. new_table = route_table_init ();
  1146. new_rtrs = route_table_init ();
  1147. ospf_vl_unapprove (ospf);
  1148. /* Calculate SPF for each area. */
  1149. for (ALL_LIST_ELEMENTS (ospf->areas, node, nnode, area))
  1150. {
  1151. /* Do backbone last, so as to first discover intra-area paths
  1152. * for any back-bone virtual-links
  1153. */
  1154. if (ospf->backbone && ospf->backbone == area)
  1155. continue;
  1156. ospf_spf_calculate (area, new_table, new_rtrs);
  1157. areas_processed++;
  1158. }
  1159. /* SPF for backbone, if required */
  1160. if (ospf->backbone)
  1161. {
  1162. ospf_spf_calculate (ospf->backbone, new_table, new_rtrs);
  1163. areas_processed++;
  1164. }
  1165. quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
  1166. spf_time = timeval_elapsed (stop_time, spf_start_time);
  1167. ospf_vl_shut_unapproved (ospf);
  1168. start_time = stop_time; /* saving a call */
  1169. ospf_ia_routing (ospf, new_table, new_rtrs);
  1170. quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
  1171. ia_time = timeval_elapsed (stop_time, start_time);
  1172. quagga_gettime (QUAGGA_CLK_MONOTONIC, &start_time);
  1173. ospf_prune_unreachable_networks (new_table);
  1174. ospf_prune_unreachable_routers (new_rtrs);
  1175. quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
  1176. prune_time = timeval_elapsed (stop_time, start_time);
  1177. /* AS-external-LSA calculation should not be performed here. */
  1178. /* If new Router Route is installed,
  1179. then schedule re-calculate External routes. */
  1180. if (1)
  1181. ospf_ase_calculate_schedule (ospf);
  1182. ospf_ase_calculate_timer_add (ospf);
  1183. quagga_gettime (QUAGGA_CLK_MONOTONIC, &start_time);
  1184. /* Update routing table. */
  1185. ospf_route_install (ospf, new_table);
  1186. quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
  1187. rt_time = timeval_elapsed (stop_time, start_time);
  1188. /* Update ABR/ASBR routing table */
  1189. if (ospf->old_rtrs)
  1190. {
  1191. /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
  1192. /* ospf_route_delete (ospf->old_rtrs); */
  1193. ospf_rtrs_free (ospf->old_rtrs);
  1194. }
  1195. ospf->old_rtrs = ospf->new_rtrs;
  1196. ospf->new_rtrs = new_rtrs;
  1197. quagga_gettime (QUAGGA_CLK_MONOTONIC, &start_time);
  1198. if (IS_OSPF_ABR (ospf))
  1199. ospf_abr_task (ospf);
  1200. quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
  1201. abr_time = timeval_elapsed (stop_time, start_time);
  1202. quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
  1203. total_spf_time = timeval_elapsed (stop_time, spf_start_time);
  1204. ospf->ts_spf_duration.tv_sec = total_spf_time/1000000;
  1205. ospf->ts_spf_duration.tv_usec = total_spf_time % 1000000;
  1206. ospf_get_spf_reason_str (rbuf);
  1207. if (IS_DEBUG_OSPF_EVENT)
  1208. {
  1209. zlog_info ("SPF Processing Time(usecs): %ld", total_spf_time);
  1210. zlog_info ("\t SPF Time: %ld", spf_time);
  1211. zlog_info ("\t InterArea: %ld", ia_time);
  1212. zlog_info ("\t Prune: %ld", prune_time);
  1213. zlog_info ("\tRouteInstall: %ld", rt_time);
  1214. if (IS_OSPF_ABR (ospf))
  1215. zlog_info ("\t ABR: %ld (%d areas)",
  1216. abr_time, areas_processed);
  1217. zlog_info ("Reason(s) for SPF: %s", rbuf);
  1218. }
  1219. ospf_clear_spf_reason_flags ();
  1220. return 0;
  1221. }
  1222. /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
  1223. set timer for SPF calc. */
  1224. void
  1225. ospf_spf_calculate_schedule (struct ospf *ospf, ospf_spf_reason_t reason)
  1226. {
  1227. unsigned long delay, elapsed, ht;
  1228. struct timeval result;
  1229. if (IS_DEBUG_OSPF_EVENT)
  1230. zlog_debug ("SPF: calculation timer scheduled");
  1231. /* OSPF instance does not exist. */
  1232. if (ospf == NULL)
  1233. return;
  1234. ospf_spf_set_reason (reason);
  1235. /* SPF calculation timer is already scheduled. */
  1236. if (ospf->t_spf_calc)
  1237. {
  1238. if (IS_DEBUG_OSPF_EVENT)
  1239. zlog_debug ("SPF: calculation timer is already scheduled: %p",
  1240. (void *)ospf->t_spf_calc);
  1241. return;
  1242. }
  1243. /* XXX Monotic timers: we only care about relative time here. */
  1244. result = tv_sub (recent_relative_time (), ospf->ts_spf);
  1245. elapsed = (result.tv_sec * 1000) + (result.tv_usec / 1000);
  1246. ht = ospf->spf_holdtime * ospf->spf_hold_multiplier;
  1247. if (ht > ospf->spf_max_holdtime)
  1248. ht = ospf->spf_max_holdtime;
  1249. /* Get SPF calculation delay time. */
  1250. if (elapsed < ht)
  1251. {
  1252. /* Got an event within the hold time of last SPF. We need to
  1253. * increase the hold_multiplier, if it's not already at/past
  1254. * maximum value, and wasn't already increased..
  1255. */
  1256. if (ht < ospf->spf_max_holdtime)
  1257. ospf->spf_hold_multiplier++;
  1258. /* always honour the SPF initial delay */
  1259. if ( (ht - elapsed) < ospf->spf_delay)
  1260. delay = ospf->spf_delay;
  1261. else
  1262. delay = ht - elapsed;
  1263. }
  1264. else
  1265. {
  1266. /* Event is past required hold-time of last SPF */
  1267. delay = ospf->spf_delay;
  1268. ospf->spf_hold_multiplier = 1;
  1269. }
  1270. if (IS_DEBUG_OSPF_EVENT)
  1271. zlog_debug ("SPF: calculation timer delay = %ld", delay);
  1272. zlog_info ("SPF: Scheduled in %ld msec", delay);
  1273. ospf->t_spf_calc =
  1274. thread_add_timer_msec (master, ospf_spf_calculate_timer, ospf, delay);
  1275. }