ospf_spf.c 30 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138
  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 "ospfd/ospfd.h"
  27. #include "ospfd/ospf_interface.h"
  28. #include "ospfd/ospf_ism.h"
  29. #include "ospfd/ospf_asbr.h"
  30. #include "ospfd/ospf_lsa.h"
  31. #include "ospfd/ospf_lsdb.h"
  32. #include "ospfd/ospf_neighbor.h"
  33. #include "ospfd/ospf_nsm.h"
  34. #include "ospfd/ospf_spf.h"
  35. #include "ospfd/ospf_route.h"
  36. #include "ospfd/ospf_ia.h"
  37. #include "ospfd/ospf_ase.h"
  38. #include "ospfd/ospf_abr.h"
  39. #include "ospfd/ospf_dump.h"
  40. #define DEBUG
  41. struct vertex_nexthop *
  42. vertex_nexthop_new (struct vertex *parent)
  43. {
  44. struct vertex_nexthop *new;
  45. new = XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop));
  46. new->parent = parent;
  47. return new;
  48. }
  49. void
  50. vertex_nexthop_free (struct vertex_nexthop *nh)
  51. {
  52. XFREE (MTYPE_OSPF_NEXTHOP, nh);
  53. }
  54. struct vertex_nexthop *
  55. vertex_nexthop_dup (struct vertex_nexthop *nh)
  56. {
  57. struct vertex_nexthop *new;
  58. new = vertex_nexthop_new (nh->parent);
  59. new->oi = nh->oi;
  60. new->router = nh->router;
  61. return new;
  62. }
  63. struct vertex *
  64. ospf_vertex_new (struct ospf_lsa *lsa)
  65. {
  66. struct vertex *new;
  67. new = XMALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex));
  68. memset (new, 0, sizeof (struct vertex));
  69. new->flags = 0;
  70. new->type = lsa->data->type;
  71. new->id = lsa->data->id;
  72. new->lsa = lsa->data;
  73. new->distance = 0;
  74. new->child = list_new ();
  75. new->nexthop = list_new ();
  76. return new;
  77. }
  78. void
  79. ospf_vertex_free (struct vertex *v)
  80. {
  81. listnode node;
  82. list_delete (v->child);
  83. if (listcount (v->nexthop) > 0)
  84. for (node = listhead (v->nexthop); node; nextnode (node))
  85. vertex_nexthop_free (node->data);
  86. list_delete (v->nexthop);
  87. XFREE (MTYPE_OSPF_VERTEX, v);
  88. }
  89. void
  90. ospf_vertex_add_parent (struct vertex *v)
  91. {
  92. struct vertex_nexthop *nh;
  93. listnode node;
  94. for (node = listhead (v->nexthop); node; nextnode (node))
  95. {
  96. nh = (struct vertex_nexthop *) getdata (node);
  97. /* No need to add two links from the same parent. */
  98. if (listnode_lookup (nh->parent->child, v) == NULL)
  99. listnode_add (nh->parent->child, v);
  100. }
  101. }
  102. void
  103. ospf_spf_init (struct ospf_area *area)
  104. {
  105. struct vertex *v;
  106. /* Create root node. */
  107. v = ospf_vertex_new (area->router_lsa_self);
  108. area->spf = v;
  109. /* Reset ABR and ASBR router counts. */
  110. area->abr_count = 0;
  111. area->asbr_count = 0;
  112. }
  113. int
  114. ospf_spf_has_vertex (struct route_table *rv, struct route_table *nv,
  115. struct lsa_header *lsa)
  116. {
  117. struct prefix p;
  118. struct route_node *rn;
  119. p.family = AF_INET;
  120. p.prefixlen = IPV4_MAX_BITLEN;
  121. p.u.prefix4 = lsa->id;
  122. if (lsa->type == OSPF_ROUTER_LSA)
  123. rn = route_node_get (rv, &p);
  124. else
  125. rn = route_node_get (nv, &p);
  126. if (rn->info != NULL)
  127. {
  128. route_unlock_node (rn);
  129. return 1;
  130. }
  131. return 0;
  132. }
  133. listnode
  134. ospf_vertex_lookup (list vlist, struct in_addr id, int type)
  135. {
  136. listnode node;
  137. struct vertex *v;
  138. for (node = listhead (vlist); node; nextnode (node))
  139. {
  140. v = (struct vertex *) getdata (node);
  141. if (IPV4_ADDR_SAME (&id, &v->id) && type == v->type)
  142. return node;
  143. }
  144. return NULL;
  145. }
  146. int
  147. ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v)
  148. {
  149. int i;
  150. int length;
  151. struct router_lsa *rl;
  152. struct network_lsa *nl;
  153. /* In case of W is Network LSA. */
  154. if (w->type == OSPF_NETWORK_LSA)
  155. {
  156. if (v->type == OSPF_NETWORK_LSA)
  157. return 0;
  158. nl = (struct network_lsa *) w;
  159. length = (ntohs (w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;
  160. for (i = 0; i < length; i++)
  161. if (IPV4_ADDR_SAME (&nl->routers[i], &v->id))
  162. return 1;
  163. return 0;
  164. }
  165. /* In case of W is Router LSA. */
  166. if (w->type == OSPF_ROUTER_LSA)
  167. {
  168. rl = (struct router_lsa *) w;
  169. length = ntohs (w->length);
  170. for (i = 0;
  171. i < ntohs (rl->links) && length >= sizeof (struct router_lsa);
  172. i++, length -= 12)
  173. {
  174. switch (rl->link[i].type)
  175. {
  176. case LSA_LINK_TYPE_POINTOPOINT:
  177. case LSA_LINK_TYPE_VIRTUALLINK:
  178. /* Router LSA ID. */
  179. if (v->type == OSPF_ROUTER_LSA &&
  180. IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
  181. {
  182. return 1;
  183. }
  184. break;
  185. case LSA_LINK_TYPE_TRANSIT:
  186. /* Network LSA ID. */
  187. if (v->type == OSPF_NETWORK_LSA &&
  188. IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
  189. {
  190. return 1;
  191. }
  192. break;
  193. case LSA_LINK_TYPE_STUB:
  194. /* Not take into count? */
  195. continue;
  196. default:
  197. break;
  198. }
  199. }
  200. }
  201. return 0;
  202. }
  203. /* Add the nexthop to the list, only if it is unique.
  204. * If it's not unique, free the nexthop entry.
  205. */
  206. void
  207. ospf_nexthop_add_unique (struct vertex_nexthop *new, list nexthop)
  208. {
  209. struct vertex_nexthop *nh;
  210. listnode node;
  211. int match;
  212. match = 0;
  213. for (node = listhead (nexthop); node; nextnode (node))
  214. {
  215. nh = node->data;
  216. /* Compare the two entries. */
  217. /* XXX
  218. * Comparing the parent preserves the shortest path tree
  219. * structure even when the nexthops are identical.
  220. */
  221. if (nh->oi == new->oi &&
  222. IPV4_ADDR_SAME (&nh->router, &new->router) &&
  223. nh->parent == new->parent)
  224. {
  225. match = 1;
  226. break;
  227. }
  228. }
  229. if (!match)
  230. listnode_add (nexthop, new);
  231. else
  232. vertex_nexthop_free (new);
  233. }
  234. /* Merge entries in list b into list a. */
  235. void
  236. ospf_nexthop_merge (list a, list b)
  237. {
  238. struct listnode *n;
  239. for (n = listhead (b); n; nextnode (n))
  240. {
  241. ospf_nexthop_add_unique (n->data, a);
  242. }
  243. }
  244. #define ROUTER_LSA_MIN_SIZE 12
  245. #define ROUTER_LSA_TOS_SIZE 4
  246. struct router_lsa_link *
  247. ospf_get_next_link (struct vertex *v, struct vertex *w,
  248. struct router_lsa_link *prev_link)
  249. {
  250. u_char *p;
  251. u_char *lim;
  252. struct router_lsa_link *l;
  253. if (prev_link == NULL)
  254. p = ((u_char *) v->lsa) + 24;
  255. else
  256. {
  257. p = (u_char *) prev_link;
  258. p += (ROUTER_LSA_MIN_SIZE +
  259. (prev_link->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
  260. }
  261. lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
  262. while (p < lim)
  263. {
  264. l = (struct router_lsa_link *) p;
  265. p += (ROUTER_LSA_MIN_SIZE + (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
  266. if (l->m[0].type == LSA_LINK_TYPE_STUB)
  267. continue;
  268. /* Defer NH calculation via VLs until summaries from
  269. transit areas area confidered */
  270. if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
  271. continue;
  272. if (IPV4_ADDR_SAME (&l->link_id, &w->id))
  273. return l;
  274. }
  275. return NULL;
  276. }
  277. /* Consider supplied next-hop for inclusion to the supplied list
  278. * of next-hops, adjust list as neccessary
  279. */
  280. void
  281. ospf_spf_consider_nexthop (struct list *nexthops,
  282. struct vertex_nexthop *newhop)
  283. {
  284. struct listnode *nnode;
  285. struct vertex_nexthop *hop;
  286. LIST_LOOP (nexthops, hop, nnode)
  287. {
  288. assert (hop->oi);
  289. /* weed out hops with higher cost than the newhop */
  290. if (hop->oi->output_cost > newhop->oi->output_cost)
  291. {
  292. /* delete the existing nexthop */
  293. listnode_delete (nexthops, hop);
  294. vertex_nexthop_free (hop);
  295. }
  296. else if (hop->oi->output_cost < newhop->oi->output_cost)
  297. {
  298. return;
  299. }
  300. }
  301. /* new hop is <= existing hops, add it */
  302. listnode_add (nexthops, newhop);
  303. return;
  304. }
  305. /* Calculate nexthop from root to vertex W. */
  306. void
  307. ospf_nexthop_calculation (struct ospf_area *area,
  308. struct vertex *v, struct vertex *w)
  309. {
  310. listnode node;
  311. struct vertex_nexthop *nh, *x;
  312. struct ospf_interface *oi = NULL;
  313. struct router_lsa_link *l = NULL;
  314. if (IS_DEBUG_OSPF_EVENT)
  315. zlog_info ("ospf_nexthop_calculation(): Start");
  316. /* W's parent is root. */
  317. if (v == area->spf)
  318. {
  319. if (w->type == OSPF_VERTEX_ROUTER)
  320. {
  321. while ((l = ospf_get_next_link (v, w, l)))
  322. {
  323. struct router_lsa_link *l2 = NULL;
  324. if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
  325. {
  326. /* Check for PtMP, signified by PtP link V->W
  327. with link_data our PtMP interface. */
  328. oi = ospf_if_is_configured (area->ospf, &l->link_data);
  329. if (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
  330. {
  331. struct prefix_ipv4 la;
  332. la.prefixlen = oi->address->prefixlen;
  333. /* We link to them on PtMP interface
  334. - find the interface on w */
  335. while ((l2 = ospf_get_next_link (w, v, l2)))
  336. {
  337. la.prefix = l2->link_data;
  338. if (prefix_cmp ((struct prefix *) &la,
  339. oi->address) == 0)
  340. /* link_data is on our PtMP network */
  341. break;
  342. }
  343. }
  344. else
  345. {
  346. while ((l2 = ospf_get_next_link (w, v, l2)))
  347. {
  348. oi = ospf_if_is_configured (area->ospf,
  349. &(l2->link_data));
  350. if (oi == NULL)
  351. continue;
  352. if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
  353. &l->link_data))
  354. continue;
  355. break;
  356. }
  357. }
  358. if (oi && l2)
  359. {
  360. nh = vertex_nexthop_new (v);
  361. nh->oi = oi;
  362. nh->router = l2->link_data;
  363. ospf_spf_consider_nexthop (w->nexthop, nh);
  364. }
  365. }
  366. }
  367. }
  368. else
  369. {
  370. while ((l = ospf_get_next_link (v, w, l)))
  371. {
  372. oi = ospf_if_is_configured (area->ospf, &(l->link_data));
  373. if (oi)
  374. {
  375. nh = vertex_nexthop_new (v);
  376. nh->oi = oi;
  377. nh->router.s_addr = 0;
  378. listnode_add (w->nexthop, nh);
  379. }
  380. }
  381. }
  382. return;
  383. }
  384. /* In case of W's parent is network connected to root. */
  385. else if (v->type == OSPF_VERTEX_NETWORK)
  386. {
  387. for (node = listhead (v->nexthop); node; nextnode (node))
  388. {
  389. x = (struct vertex_nexthop *) getdata (node);
  390. if (x->parent == area->spf)
  391. {
  392. while ((l = ospf_get_next_link (w, v, l)))
  393. {
  394. nh = vertex_nexthop_new (v);
  395. nh->oi = x->oi;
  396. nh->router = l->link_data;
  397. listnode_add (w->nexthop, nh);
  398. }
  399. return;
  400. }
  401. }
  402. }
  403. /* Inherit V's nexthop. */
  404. for (node = listhead (v->nexthop); node; nextnode (node))
  405. {
  406. nh = vertex_nexthop_dup (node->data);
  407. nh->parent = v;
  408. ospf_nexthop_add_unique (nh, w->nexthop);
  409. }
  410. }
  411. void
  412. ospf_install_candidate (list candidate, struct vertex *w)
  413. {
  414. listnode node;
  415. struct vertex *cw;
  416. if (list_isempty (candidate))
  417. {
  418. listnode_add (candidate, w);
  419. return;
  420. }
  421. /* Install vertex with sorting by distance. */
  422. for (node = listhead (candidate); node; nextnode (node))
  423. {
  424. cw = (struct vertex *) getdata (node);
  425. if (cw->distance > w->distance)
  426. {
  427. list_add_node_prev (candidate, node, w);
  428. break;
  429. }
  430. else if (node->next == NULL)
  431. {
  432. list_add_node_next (candidate, node, w);
  433. break;
  434. }
  435. }
  436. }
  437. /* RFC2328 Section 16.1 (2). */
  438. void
  439. ospf_spf_next (struct vertex *v, struct ospf_area *area,
  440. list candidate, struct route_table *rv, struct route_table *nv)
  441. {
  442. struct ospf_lsa *w_lsa = NULL;
  443. struct vertex *w, *cw;
  444. u_char *p;
  445. u_char *lim;
  446. struct router_lsa_link *l = NULL;
  447. struct in_addr *r;
  448. listnode node;
  449. int type = 0;
  450. /* If this is a router-LSA, and bit V of the router-LSA (see Section
  451. A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
  452. if (v->type == OSPF_VERTEX_ROUTER)
  453. {
  454. if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa))
  455. area->transit = OSPF_TRANSIT_TRUE;
  456. }
  457. p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
  458. lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
  459. while (p < lim)
  460. {
  461. /* In case of V is Router-LSA. */
  462. if (v->lsa->type == OSPF_ROUTER_LSA)
  463. {
  464. l = (struct router_lsa_link *) p;
  465. p += (ROUTER_LSA_MIN_SIZE +
  466. (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
  467. /* (a) If this is a link to a stub network, examine the next
  468. link in V's LSA. Links to stub networks will be
  469. considered in the second stage of the shortest path
  470. calculation. */
  471. if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
  472. continue;
  473. /* (b) Otherwise, W is a transit vertex (router or transit
  474. network). Look up the vertex W's LSA (router-LSA or
  475. network-LSA) in Area A's link state database. */
  476. switch (type)
  477. {
  478. case LSA_LINK_TYPE_POINTOPOINT:
  479. case LSA_LINK_TYPE_VIRTUALLINK:
  480. if (type == LSA_LINK_TYPE_VIRTUALLINK)
  481. {
  482. if (IS_DEBUG_OSPF_EVENT)
  483. zlog_info ("looking up LSA through VL: %s",
  484. inet_ntoa (l->link_id));
  485. }
  486. w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id,
  487. l->link_id);
  488. if (w_lsa)
  489. {
  490. if (IS_DEBUG_OSPF_EVENT)
  491. zlog_info ("found the LSA");
  492. }
  493. break;
  494. case LSA_LINK_TYPE_TRANSIT:
  495. if (IS_DEBUG_OSPF_EVENT)
  496. zlog_info ("Looking up Network LSA, ID: %s",
  497. inet_ntoa (l->link_id));
  498. w_lsa = ospf_lsa_lookup_by_id (area, OSPF_NETWORK_LSA,
  499. l->link_id);
  500. if (w_lsa)
  501. if (IS_DEBUG_OSPF_EVENT)
  502. zlog_info ("found the LSA");
  503. break;
  504. default:
  505. zlog_warn ("Invalid LSA link type %d", type);
  506. continue;
  507. }
  508. }
  509. else
  510. {
  511. /* In case of V is Network-LSA. */
  512. r = (struct in_addr *) p;
  513. p += sizeof (struct in_addr);
  514. /* Lookup the vertex W's LSA. */
  515. w_lsa = ospf_lsa_lookup_by_id (area, OSPF_ROUTER_LSA, *r);
  516. }
  517. /* (b cont.) If the LSA does not exist, or its LS age is equal
  518. to MaxAge, or it does not have a link back to vertex V,
  519. examine the next link in V's LSA.[23] */
  520. if (w_lsa == NULL)
  521. continue;
  522. if (IS_LSA_MAXAGE (w_lsa))
  523. continue;
  524. if (!ospf_lsa_has_link (w_lsa->data, v->lsa))
  525. {
  526. if (IS_DEBUG_OSPF_EVENT)
  527. zlog_info ("The LSA doesn't have a link back");
  528. continue;
  529. }
  530. /* (c) If vertex W is already on the shortest-path tree, examine
  531. the next link in the LSA. */
  532. if (ospf_spf_has_vertex (rv, nv, w_lsa->data))
  533. {
  534. if (IS_DEBUG_OSPF_EVENT)
  535. zlog_info ("The LSA is already in SPF");
  536. continue;
  537. }
  538. /* (d) Calculate the link state cost D of the resulting path
  539. from the root to vertex W. D is equal to the sum of the link
  540. state cost of the (already calculated) shortest path to
  541. vertex V and the advertised cost of the link between vertices
  542. V and W. If D is: */
  543. /* prepare vertex W. */
  544. w = ospf_vertex_new (w_lsa);
  545. /* calculate link cost D. */
  546. if (v->lsa->type == OSPF_ROUTER_LSA)
  547. w->distance = v->distance + ntohs (l->m[0].metric);
  548. else
  549. w->distance = v->distance;
  550. /* Is there already vertex W in candidate list? */
  551. node = ospf_vertex_lookup (candidate, w->id, w->type);
  552. if (node == NULL)
  553. {
  554. /* Calculate nexthop to W. */
  555. ospf_nexthop_calculation (area, v, w);
  556. ospf_install_candidate (candidate, w);
  557. }
  558. else
  559. {
  560. cw = (struct vertex *) getdata (node);
  561. /* if D is greater than. */
  562. if (cw->distance < w->distance)
  563. {
  564. ospf_vertex_free (w);
  565. continue;
  566. }
  567. /* equal to. */
  568. else if (cw->distance == w->distance)
  569. {
  570. /* Calculate nexthop to W. */
  571. ospf_nexthop_calculation (area, v, w);
  572. ospf_nexthop_merge (cw->nexthop, w->nexthop);
  573. list_delete_all_node (w->nexthop);
  574. ospf_vertex_free (w);
  575. }
  576. /* less than. */
  577. else
  578. {
  579. /* Calculate nexthop. */
  580. ospf_nexthop_calculation (area, v, w);
  581. /* Remove old vertex from candidate list. */
  582. ospf_vertex_free (cw);
  583. listnode_delete (candidate, cw);
  584. /* Install new to candidate. */
  585. ospf_install_candidate (candidate, w);
  586. }
  587. }
  588. }
  589. }
  590. /* Add vertex V to SPF tree. */
  591. void
  592. ospf_spf_register (struct vertex *v, struct route_table *rv,
  593. struct route_table *nv)
  594. {
  595. struct prefix p;
  596. struct route_node *rn;
  597. p.family = AF_INET;
  598. p.prefixlen = IPV4_MAX_BITLEN;
  599. p.u.prefix4 = v->id;
  600. if (v->type == OSPF_VERTEX_ROUTER)
  601. rn = route_node_get (rv, &p);
  602. else
  603. rn = route_node_get (nv, &p);
  604. rn->info = v;
  605. }
  606. void
  607. ospf_spf_route_free (struct route_table *table)
  608. {
  609. struct route_node *rn;
  610. struct vertex *v;
  611. for (rn = route_top (table); rn; rn = route_next (rn))
  612. {
  613. if ((v = rn->info))
  614. {
  615. ospf_vertex_free (v);
  616. rn->info = NULL;
  617. }
  618. route_unlock_node (rn);
  619. }
  620. route_table_finish (table);
  621. }
  622. void
  623. ospf_spf_dump (struct vertex *v, int i)
  624. {
  625. listnode cnode;
  626. listnode nnode;
  627. struct vertex_nexthop *nexthop;
  628. if (v->type == OSPF_VERTEX_ROUTER)
  629. {
  630. if (IS_DEBUG_OSPF_EVENT)
  631. zlog_info ("SPF Result: %d [R] %s", i, inet_ntoa (v->lsa->id));
  632. }
  633. else
  634. {
  635. struct network_lsa *lsa = (struct network_lsa *) v->lsa;
  636. if (IS_DEBUG_OSPF_EVENT)
  637. zlog_info ("SPF Result: %d [N] %s/%d", i, inet_ntoa (v->lsa->id),
  638. ip_masklen (lsa->mask));
  639. for (nnode = listhead (v->nexthop); nnode; nextnode (nnode))
  640. {
  641. nexthop = getdata (nnode);
  642. if (IS_DEBUG_OSPF_EVENT)
  643. zlog_info (" nexthop %s", inet_ntoa (nexthop->router));
  644. }
  645. }
  646. i++;
  647. for (cnode = listhead (v->child); cnode; nextnode (cnode))
  648. {
  649. v = getdata (cnode);
  650. ospf_spf_dump (v, i);
  651. }
  652. }
  653. /* Second stage of SPF calculation. */
  654. void
  655. ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v,
  656. struct route_table *rt)
  657. {
  658. listnode cnode;
  659. struct vertex *child;
  660. if (IS_DEBUG_OSPF_EVENT)
  661. zlog_info ("ospf_process_stub():processing stubs for area %s",
  662. inet_ntoa (area->area_id));
  663. if (v->type == OSPF_VERTEX_ROUTER)
  664. {
  665. u_char *p;
  666. u_char *lim;
  667. struct router_lsa_link *l;
  668. struct router_lsa *rlsa;
  669. if (IS_DEBUG_OSPF_EVENT)
  670. zlog_info ("ospf_process_stub():processing router LSA, id: %s",
  671. inet_ntoa (v->lsa->id));
  672. rlsa = (struct router_lsa *) v->lsa;
  673. if (IS_DEBUG_OSPF_EVENT)
  674. zlog_info ("ospf_process_stub(): we have %d links to process",
  675. ntohs (rlsa->links));
  676. p = ((u_char *) v->lsa) + 24;
  677. lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
  678. while (p < lim)
  679. {
  680. l = (struct router_lsa_link *) p;
  681. p += (ROUTER_LSA_MIN_SIZE +
  682. (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
  683. if (l->m[0].type == LSA_LINK_TYPE_STUB)
  684. ospf_intra_add_stub (rt, l, v, area);
  685. }
  686. }
  687. if (IS_DEBUG_OSPF_EVENT)
  688. zlog_info ("children of V:");
  689. for (cnode = listhead (v->child); cnode; nextnode (cnode))
  690. {
  691. child = getdata (cnode);
  692. if (IS_DEBUG_OSPF_EVENT)
  693. zlog_info (" child : %s", inet_ntoa (child->id));
  694. }
  695. for (cnode = listhead (v->child); cnode; nextnode (cnode))
  696. {
  697. child = getdata (cnode);
  698. if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED))
  699. continue;
  700. ospf_spf_process_stubs (area, child, rt);
  701. SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED);
  702. }
  703. }
  704. void
  705. ospf_rtrs_free (struct route_table *rtrs)
  706. {
  707. struct route_node *rn;
  708. list or_list;
  709. listnode node;
  710. if (IS_DEBUG_OSPF_EVENT)
  711. zlog_info ("Route: Router Routing Table free");
  712. for (rn = route_top (rtrs); rn; rn = route_next (rn))
  713. if ((or_list = rn->info) != NULL)
  714. {
  715. for (node = listhead (or_list); node; nextnode (node))
  716. ospf_route_free (node->data);
  717. list_delete (or_list);
  718. /* Unlock the node. */
  719. rn->info = NULL;
  720. route_unlock_node (rn);
  721. }
  722. route_table_finish (rtrs);
  723. }
  724. void
  725. ospf_rtrs_print (struct route_table *rtrs)
  726. {
  727. struct route_node *rn;
  728. list or_list;
  729. listnode ln;
  730. listnode pnode;
  731. struct ospf_route *or;
  732. struct ospf_path *path;
  733. char buf1[BUFSIZ];
  734. char buf2[BUFSIZ];
  735. if (IS_DEBUG_OSPF_EVENT)
  736. zlog_info ("ospf_rtrs_print() start");
  737. for (rn = route_top (rtrs); rn; rn = route_next (rn))
  738. if ((or_list = rn->info) != NULL)
  739. for (ln = listhead (or_list); ln; nextnode (ln))
  740. {
  741. or = getdata (ln);
  742. switch (or->path_type)
  743. {
  744. case OSPF_PATH_INTRA_AREA:
  745. if (IS_DEBUG_OSPF_EVENT)
  746. zlog_info ("%s [%d] area: %s",
  747. inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
  748. or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
  749. buf2, BUFSIZ));
  750. break;
  751. case OSPF_PATH_INTER_AREA:
  752. if (IS_DEBUG_OSPF_EVENT)
  753. zlog_info ("%s IA [%d] area: %s",
  754. inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
  755. or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
  756. buf2, BUFSIZ));
  757. break;
  758. default:
  759. break;
  760. }
  761. for (pnode = listhead (or->paths); pnode; nextnode (pnode))
  762. {
  763. path = getdata (pnode);
  764. if (path->nexthop.s_addr == 0)
  765. {
  766. if (IS_DEBUG_OSPF_EVENT)
  767. zlog_info (" directly attached to %s\r\n",
  768. IF_NAME (path->oi));
  769. }
  770. else
  771. {
  772. if (IS_DEBUG_OSPF_EVENT)
  773. zlog_info (" via %s, %s\r\n",
  774. inet_ntoa (path->nexthop), IF_NAME (path->oi));
  775. }
  776. }
  777. }
  778. zlog_info ("ospf_rtrs_print() end");
  779. }
  780. /* Calculating the shortest-path tree for an area. */
  781. void
  782. ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table,
  783. struct route_table *new_rtrs)
  784. {
  785. list candidate;
  786. listnode node;
  787. struct vertex *v;
  788. struct route_table *rv;
  789. struct route_table *nv;
  790. if (IS_DEBUG_OSPF_EVENT)
  791. {
  792. zlog_info ("ospf_spf_calculate: Start");
  793. zlog_info ("ospf_spf_calculate: running Dijkstra for area %s",
  794. inet_ntoa (area->area_id));
  795. }
  796. /* Check router-lsa-self. If self-router-lsa is not yet allocated,
  797. return this area's calculation. */
  798. if (!area->router_lsa_self)
  799. {
  800. if (IS_DEBUG_OSPF_EVENT)
  801. zlog_info ("ospf_spf_calculate: "
  802. "Skip area %s's calculation due to empty router_lsa_self",
  803. inet_ntoa (area->area_id));
  804. return;
  805. }
  806. /* RFC2328 16.1. (1). */
  807. /* Initialize the algorithm's data structures. */
  808. rv = route_table_init ();
  809. nv = route_table_init ();
  810. /* Clear the list of candidate vertices. */
  811. candidate = list_new ();
  812. /* Initialize the shortest-path tree to only the root (which is the
  813. router doing the calculation). */
  814. ospf_spf_init (area);
  815. v = area->spf;
  816. ospf_spf_register (v, rv, nv);
  817. /* Set Area A's TransitCapability to FALSE. */
  818. area->transit = OSPF_TRANSIT_FALSE;
  819. area->shortcut_capability = 1;
  820. for (;;)
  821. {
  822. /* RFC2328 16.1. (2). */
  823. ospf_spf_next (v, area, candidate, rv, nv);
  824. /* RFC2328 16.1. (3). */
  825. /* If at this step the candidate list is empty, the shortest-
  826. path tree (of transit vertices) has been completely built and
  827. this stage of the procedure terminates. */
  828. if (listcount (candidate) == 0)
  829. break;
  830. /* Otherwise, choose the vertex belonging to the candidate list
  831. that is closest to the root, and add it to the shortest-path
  832. tree (removing it from the candidate list in the
  833. process). */
  834. node = listhead (candidate);
  835. v = getdata (node);
  836. ospf_vertex_add_parent (v);
  837. /* Reveve from the candidate list. */
  838. listnode_delete (candidate, v);
  839. /* Add to SPF tree. */
  840. ospf_spf_register (v, rv, nv);
  841. /* Note that when there is a choice of vertices closest to the
  842. root, network vertices must be chosen before router vertices
  843. in order to necessarily find all equal-cost paths. */
  844. /* We don't do this at this moment, we should add the treatment
  845. above codes. -- kunihiro. */
  846. /* RFC2328 16.1. (4). */
  847. if (v->type == OSPF_VERTEX_ROUTER)
  848. ospf_intra_add_router (new_rtrs, v, area);
  849. else
  850. ospf_intra_add_transit (new_table, v, area);
  851. /* RFC2328 16.1. (5). */
  852. /* Iterate the algorithm by returning to Step 2. */
  853. }
  854. if (IS_DEBUG_OSPF_EVENT)
  855. {
  856. ospf_spf_dump (area->spf, 0);
  857. ospf_route_table_dump (new_table);
  858. }
  859. /* Second stage of SPF calculation procedure's */
  860. ospf_spf_process_stubs (area, area->spf, new_table);
  861. /* Free all vertices which allocated for SPF calculation */
  862. ospf_spf_route_free (rv);
  863. ospf_spf_route_free (nv);
  864. /* Free candidate list */
  865. list_free (candidate);
  866. /* Increment SPF Calculation Counter. */
  867. area->spf_calculation++;
  868. area->ospf->ts_spf = time (NULL);
  869. if (IS_DEBUG_OSPF_EVENT)
  870. zlog_info ("ospf_spf_calculate: Stop");
  871. }
  872. /* Timer for SPF calculation. */
  873. int
  874. ospf_spf_calculate_timer (struct thread *thread)
  875. {
  876. struct ospf *ospf = THREAD_ARG (thread);
  877. struct route_table *new_table, *new_rtrs;
  878. listnode node;
  879. if (IS_DEBUG_OSPF_EVENT)
  880. zlog_info ("SPF: Timer (SPF calculation expire)");
  881. ospf->t_spf_calc = NULL;
  882. /* Allocate new table tree. */
  883. new_table = route_table_init ();
  884. new_rtrs = route_table_init ();
  885. ospf_vl_unapprove (ospf);
  886. /* Calculate SPF for each area. */
  887. for (node = listhead (ospf->areas); node; node = nextnode (node))
  888. ospf_spf_calculate (node->data, new_table, new_rtrs);
  889. ospf_vl_shut_unapproved (ospf);
  890. ospf_ia_routing (ospf, new_table, new_rtrs);
  891. ospf_prune_unreachable_networks (new_table);
  892. ospf_prune_unreachable_routers (new_rtrs);
  893. /* AS-external-LSA calculation should not be performed here. */
  894. /* If new Router Route is installed,
  895. then schedule re-calculate External routes. */
  896. if (1)
  897. ospf_ase_calculate_schedule (ospf);
  898. ospf_ase_calculate_timer_add (ospf);
  899. /* Update routing table. */
  900. ospf_route_install (ospf, new_table);
  901. /* Update ABR/ASBR routing table */
  902. if (ospf->old_rtrs)
  903. {
  904. /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
  905. /* ospf_route_delete (ospf->old_rtrs); */
  906. ospf_rtrs_free (ospf->old_rtrs);
  907. }
  908. ospf->old_rtrs = ospf->new_rtrs;
  909. ospf->new_rtrs = new_rtrs;
  910. if (IS_OSPF_ABR (ospf))
  911. ospf_abr_task (ospf);
  912. if (IS_DEBUG_OSPF_EVENT)
  913. zlog_info ("SPF: calculation complete");
  914. return 0;
  915. }
  916. /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
  917. set timer for SPF calc. */
  918. void
  919. ospf_spf_calculate_schedule (struct ospf *ospf)
  920. {
  921. time_t ht, delay;
  922. if (IS_DEBUG_OSPF_EVENT)
  923. zlog_info ("SPF: calculation timer scheduled");
  924. /* OSPF instance does not exist. */
  925. if (ospf == NULL)
  926. return;
  927. /* SPF calculation timer is already scheduled. */
  928. if (ospf->t_spf_calc)
  929. {
  930. if (IS_DEBUG_OSPF_EVENT)
  931. zlog_info ("SPF: calculation timer is already scheduled: %p",
  932. ospf->t_spf_calc);
  933. return;
  934. }
  935. ht = time (NULL) - ospf->ts_spf;
  936. /* Get SPF calculation delay time. */
  937. if (ht < ospf->spf_holdtime)
  938. {
  939. if (ospf->spf_holdtime - ht < ospf->spf_delay)
  940. delay = ospf->spf_delay;
  941. else
  942. delay = ospf->spf_holdtime - ht;
  943. }
  944. else
  945. delay = ospf->spf_delay;
  946. if (IS_DEBUG_OSPF_EVENT)
  947. zlog_info ("SPF: calculation timer delay = %ld", (long)delay);
  948. ospf->t_spf_calc =
  949. thread_add_timer (master, ospf_spf_calculate_timer, ospf, delay);
  950. }