ospf_route.c 26 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047
  1. /*
  2. * OSPF routing table.
  3. * Copyright (C) 1999, 2000 Toshiaki Takada
  4. *
  5. * This file is part of GNU Zebra.
  6. *
  7. * GNU Zebra is free software; you can redistribute it and/or modify it
  8. * under the terms of the GNU General Public License as published by the
  9. * Free Software Foundation; either version 2, or (at your option) any
  10. * later version.
  11. *
  12. * GNU Zebra is distributed in the hope that it will be useful, but
  13. * WITHOUT ANY WARRANTY; without even the implied warranty of
  14. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15. * General Public License for more details.
  16. *
  17. * You should have received a copy of the GNU General Public License
  18. * along with GNU Zebra; see the file COPYING. If not, write to the Free
  19. * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  20. * 02111-1307, USA.
  21. */
  22. #include <zebra.h>
  23. #include "prefix.h"
  24. #include "table.h"
  25. #include "memory.h"
  26. #include "linklist.h"
  27. #include "log.h"
  28. #include "if.h"
  29. #include "command.h"
  30. #include "sockunion.h"
  31. #include "ospfd/ospfd.h"
  32. #include "ospfd/ospf_interface.h"
  33. #include "ospfd/ospf_asbr.h"
  34. #include "ospfd/ospf_lsa.h"
  35. #include "ospfd/ospf_route.h"
  36. #include "ospfd/ospf_spf.h"
  37. #include "ospfd/ospf_zebra.h"
  38. #include "ospfd/ospf_dump.h"
  39. struct ospf_route *
  40. ospf_route_new ()
  41. {
  42. struct ospf_route *new;
  43. new = XCALLOC (MTYPE_OSPF_ROUTE, sizeof (struct ospf_route));
  44. new->ctime = time (NULL);
  45. new->mtime = new->ctime;
  46. new->paths = list_new ();
  47. new->paths->del = (void (*) (void *))ospf_path_free;
  48. return new;
  49. }
  50. void
  51. ospf_route_free (struct ospf_route *or)
  52. {
  53. if (or->paths)
  54. list_delete (or->paths);
  55. XFREE (MTYPE_OSPF_ROUTE, or);
  56. }
  57. struct ospf_path *
  58. ospf_path_new ()
  59. {
  60. struct ospf_path *new;
  61. new = XCALLOC (MTYPE_OSPF_PATH, sizeof (struct ospf_path));
  62. return new;
  63. }
  64. struct ospf_path *
  65. ospf_path_dup (struct ospf_path *path)
  66. {
  67. struct ospf_path *new;
  68. new = ospf_path_new ();
  69. memcpy (new, path, sizeof (struct ospf_path));
  70. return new;
  71. }
  72. void
  73. ospf_path_free (struct ospf_path *op)
  74. {
  75. XFREE (MTYPE_OSPF_PATH, op);
  76. }
  77. void
  78. ospf_route_delete (struct route_table *rt)
  79. {
  80. struct route_node *rn;
  81. struct ospf_route *or;
  82. for (rn = route_top (rt); rn; rn = route_next (rn))
  83. if ((or = rn->info) != NULL)
  84. {
  85. if (or->type == OSPF_DESTINATION_NETWORK)
  86. ospf_zebra_delete ((struct prefix_ipv4 *) &rn->p,
  87. or);
  88. else if (or->type == OSPF_DESTINATION_DISCARD)
  89. ospf_zebra_delete_discard ((struct prefix_ipv4 *) &rn->p);
  90. }
  91. }
  92. void
  93. ospf_route_table_free (struct route_table *rt)
  94. {
  95. struct route_node *rn;
  96. struct ospf_route *or;
  97. for (rn = route_top (rt); rn; rn = route_next (rn))
  98. if ((or = rn->info) != NULL)
  99. {
  100. ospf_route_free (or);
  101. rn->info = NULL;
  102. route_unlock_node (rn);
  103. }
  104. route_table_finish (rt);
  105. }
  106. /* If a prefix and a nexthop match any route in the routing table,
  107. then return 1, otherwise return 0. */
  108. int
  109. ospf_route_match_same (struct route_table *rt, struct prefix_ipv4 *prefix,
  110. struct ospf_route *newor)
  111. {
  112. struct route_node *rn;
  113. struct ospf_route *or;
  114. struct ospf_path *op;
  115. struct ospf_path *newop;
  116. listnode n1;
  117. listnode n2;
  118. if (! rt || ! prefix)
  119. return 0;
  120. rn = route_node_lookup (rt, (struct prefix *) prefix);
  121. if (! rn || ! rn->info)
  122. return 0;
  123. route_unlock_node (rn);
  124. or = rn->info;
  125. if (or->type == newor->type && or->cost == newor->cost)
  126. {
  127. if (or->type == OSPF_DESTINATION_NETWORK)
  128. {
  129. if (or->paths->count != newor->paths->count)
  130. return 0;
  131. /* Check each path. */
  132. for (n1 = listhead (or->paths), n2 = listhead (newor->paths);
  133. n1 && n2; nextnode (n1), nextnode (n2))
  134. {
  135. op = getdata (n1);
  136. newop = getdata (n2);
  137. if (! IPV4_ADDR_SAME (&op->nexthop, &newop->nexthop))
  138. return 0;
  139. }
  140. return 1;
  141. }
  142. else if (prefix_same (&rn->p, (struct prefix *) prefix))
  143. return 1;
  144. }
  145. return 0;
  146. }
  147. /* delete routes generated from AS-External routes if there is a inter/intra
  148. * area route
  149. */
  150. void
  151. ospf_route_delete_same_ext(struct route_table *external_routes,
  152. struct route_table *routes)
  153. {
  154. struct route_node *rn,
  155. *ext_rn;
  156. if ( (external_routes == NULL) || (routes == NULL) )
  157. return;
  158. /* Remove deleted routes */
  159. for ( rn = route_top (routes); rn; rn = route_next (rn) )
  160. {
  161. if (rn && rn->info)
  162. {
  163. struct prefix_ipv4 *p = (struct prefix_ipv4 *)(&rn->p);
  164. if ( (ext_rn = route_node_lookup (external_routes, (struct prefix *)p)) )
  165. {
  166. ospf_zebra_delete (p, ext_rn->info);
  167. if (ext_rn->info)
  168. {
  169. ospf_route_free( ext_rn->info);
  170. ext_rn->info = NULL;
  171. }
  172. route_unlock_node (ext_rn);
  173. }
  174. }
  175. }
  176. }
  177. /* rt: Old, cmprt: New */
  178. void
  179. ospf_route_delete_uniq (struct route_table *rt, struct route_table *cmprt)
  180. {
  181. struct route_node *rn;
  182. struct ospf_route *or;
  183. for (rn = route_top (rt); rn; rn = route_next (rn))
  184. if ((or = rn->info) != NULL)
  185. if (or->path_type == OSPF_PATH_INTRA_AREA ||
  186. or->path_type == OSPF_PATH_INTER_AREA)
  187. {
  188. if (or->type == OSPF_DESTINATION_NETWORK)
  189. {
  190. if (! ospf_route_match_same (cmprt,
  191. (struct prefix_ipv4 *) &rn->p, or))
  192. ospf_zebra_delete ((struct prefix_ipv4 *) &rn->p, or);
  193. }
  194. else if (or->type == OSPF_DESTINATION_DISCARD)
  195. if (! ospf_route_match_same (cmprt,
  196. (struct prefix_ipv4 *) &rn->p, or))
  197. ospf_zebra_delete_discard ((struct prefix_ipv4 *) &rn->p);
  198. }
  199. }
  200. /* Install routes to table. */
  201. void
  202. ospf_route_install (struct ospf *ospf, struct route_table *rt)
  203. {
  204. struct route_node *rn;
  205. struct ospf_route *or;
  206. /* rt contains new routing table, new_table contains an old one.
  207. updating pointers */
  208. if (ospf->old_table)
  209. ospf_route_table_free (ospf->old_table);
  210. ospf->old_table = ospf->new_table;
  211. ospf->new_table = rt;
  212. /* Delete old routes. */
  213. if (ospf->old_table)
  214. ospf_route_delete_uniq (ospf->old_table, rt);
  215. if (ospf->old_external_route)
  216. ospf_route_delete_same_ext (ospf->old_external_route, rt);
  217. /* Install new routes. */
  218. for (rn = route_top (rt); rn; rn = route_next (rn))
  219. if ((or = rn->info) != NULL)
  220. {
  221. if (or->type == OSPF_DESTINATION_NETWORK)
  222. {
  223. if (! ospf_route_match_same (ospf->old_table,
  224. (struct prefix_ipv4 *)&rn->p, or))
  225. ospf_zebra_add ((struct prefix_ipv4 *) &rn->p, or);
  226. }
  227. else if (or->type == OSPF_DESTINATION_DISCARD)
  228. if (! ospf_route_match_same (ospf->old_table,
  229. (struct prefix_ipv4 *) &rn->p, or))
  230. ospf_zebra_add_discard ((struct prefix_ipv4 *) &rn->p);
  231. }
  232. }
  233. void
  234. ospf_intra_route_add (struct route_table *rt, struct vertex *v,
  235. struct ospf_area *area)
  236. {
  237. struct route_node *rn;
  238. struct ospf_route *or;
  239. struct prefix_ipv4 p;
  240. struct ospf_path *path;
  241. struct vertex_nexthop *nexthop;
  242. listnode nnode;
  243. p.family = AF_INET;
  244. p.prefix = v->id;
  245. if (v->type == OSPF_VERTEX_ROUTER)
  246. p.prefixlen = IPV4_MAX_BITLEN;
  247. else
  248. {
  249. struct network_lsa *lsa = (struct network_lsa *) v->lsa;
  250. p.prefixlen = ip_masklen (lsa->mask);
  251. }
  252. apply_mask_ipv4 (&p);
  253. rn = route_node_get (rt, (struct prefix *) &p);
  254. if (rn->info)
  255. {
  256. zlog_warn ("Same routing information exists for %s", inet_ntoa (v->id));
  257. route_unlock_node (rn);
  258. return;
  259. }
  260. or = ospf_route_new ();
  261. if (v->type == OSPF_VERTEX_NETWORK)
  262. {
  263. or->type = OSPF_DESTINATION_NETWORK;
  264. LIST_LOOP (v->nexthop, nexthop, nnode)
  265. {
  266. nexthop = getdata (nnode);
  267. path = ospf_path_new ();
  268. path->nexthop = nexthop->router;
  269. listnode_add (or->paths, path);
  270. }
  271. }
  272. else
  273. or->type = OSPF_DESTINATION_ROUTER;
  274. or->id = v->id;
  275. or->u.std.area_id = area->area_id;
  276. #ifdef HAVE_NSSA
  277. or->u.std.external_routing= area->external_routing;
  278. #endif /* HAVE_NSSA */
  279. or->path_type = OSPF_PATH_INTRA_AREA;
  280. or->cost = v->distance;
  281. rn->info = or;
  282. }
  283. /* RFC2328 16.1. (4). For "router". */
  284. void
  285. ospf_intra_add_router (struct route_table *rt, struct vertex *v,
  286. struct ospf_area *area)
  287. {
  288. struct route_node *rn;
  289. struct ospf_route *or;
  290. struct prefix_ipv4 p;
  291. struct router_lsa *lsa;
  292. if (IS_DEBUG_OSPF_EVENT)
  293. zlog_info ("ospf_intra_add_router: Start");
  294. lsa = (struct router_lsa *) v->lsa;
  295. if (IS_DEBUG_OSPF_EVENT)
  296. zlog_info ("ospf_intra_add_router: LS ID: %s",
  297. inet_ntoa (lsa->header.id));
  298. ospf_vl_up_check (area, lsa->header.id, v);
  299. if (!CHECK_FLAG (lsa->flags, ROUTER_LSA_SHORTCUT))
  300. area->shortcut_capability = 0;
  301. /* If the newly added vertex is an area border router or AS boundary
  302. router, a routing table entry is added whose destination type is
  303. "router". */
  304. if (! IS_ROUTER_LSA_BORDER (lsa) && ! IS_ROUTER_LSA_EXTERNAL (lsa))
  305. {
  306. if (IS_DEBUG_OSPF_EVENT)
  307. zlog_info ("ospf_intra_add_router: "
  308. "this router is neither ASBR nor ABR, skipping it");
  309. return;
  310. }
  311. /* Update ABR and ASBR count in this area. */
  312. if (IS_ROUTER_LSA_BORDER (lsa))
  313. area->abr_count++;
  314. if (IS_ROUTER_LSA_EXTERNAL (lsa))
  315. area->asbr_count++;
  316. /* The Options field found in the associated router-LSA is copied
  317. into the routing table entry's Optional capabilities field. Call
  318. the newly added vertex Router X. */
  319. or = ospf_route_new ();
  320. or->id = v->id;
  321. or->u.std.area_id = area->area_id;
  322. #ifdef HAVE_NSSA
  323. or->u.std.external_routing = area->external_routing;
  324. #endif /* HAVE_NSSA */
  325. or->path_type = OSPF_PATH_INTRA_AREA;
  326. or->cost = v->distance;
  327. or->type = OSPF_DESTINATION_ROUTER;
  328. or->u.std.origin = (struct lsa_header *) lsa;
  329. or->u.std.options = lsa->header.options;
  330. or->u.std.flags = lsa->flags;
  331. /* If Router X is the endpoint of one of the calculating router's
  332. virtual links, and the virtual link uses Area A as Transit area:
  333. the virtual link is declared up, the IP address of the virtual
  334. interface is set to the IP address of the outgoing interface
  335. calculated above for Router X, and the virtual neighbor's IP
  336. address is set to Router X's interface address (contained in
  337. Router X's router-LSA) that points back to the root of the
  338. shortest- path tree; equivalently, this is the interface that
  339. points back to Router X's parent vertex on the shortest-path tree
  340. (similar to the calculation in Section 16.1.1). */
  341. p.family = AF_INET;
  342. p.prefix = v->id;
  343. p.prefixlen = IPV4_MAX_BITLEN;
  344. if (IS_DEBUG_OSPF_EVENT)
  345. zlog_info ("ospf_intra_add_router: talking about %s/%d",
  346. inet_ntoa (p.prefix), p.prefixlen);
  347. rn = route_node_get (rt, (struct prefix *) &p);
  348. /* Note that we keep all routes to ABRs and ASBRs, not only the best */
  349. if (rn->info == NULL)
  350. rn->info = list_new ();
  351. else
  352. route_unlock_node (rn);
  353. ospf_route_copy_nexthops_from_vertex (or, v);
  354. listnode_add (rn->info, or);
  355. zlog_info ("ospf_intra_add_router: Start");
  356. }
  357. /* RFC2328 16.1. (4). For transit network. */
  358. void
  359. ospf_intra_add_transit (struct route_table *rt, struct vertex *v,
  360. struct ospf_area *area)
  361. {
  362. struct route_node *rn;
  363. struct ospf_route *or;
  364. struct prefix_ipv4 p;
  365. struct network_lsa *lsa;
  366. lsa = (struct network_lsa*) v->lsa;
  367. /* If the newly added vertex is a transit network, the routing table
  368. entry for the network is located. The entry's Destination ID is
  369. the IP network number, which can be obtained by masking the
  370. Vertex ID (Link State ID) with its associated subnet mask (found
  371. in the body of the associated network-LSA). */
  372. p.family = AF_INET;
  373. p.prefix = v->id;
  374. p.prefixlen = ip_masklen (lsa->mask);
  375. apply_mask_ipv4 (&p);
  376. rn = route_node_get (rt, (struct prefix *) &p);
  377. /* If the routing table entry already exists (i.e., there is already
  378. an intra-area route to the destination installed in the routing
  379. table), multiple vertices have mapped to the same IP network.
  380. For example, this can occur when a new Designated Router is being
  381. established. In this case, the current routing table entry
  382. should be overwritten if and only if the newly found path is just
  383. as short and the current routing table entry's Link State Origin
  384. has a smaller Link State ID than the newly added vertex' LSA. */
  385. if (rn->info)
  386. {
  387. struct ospf_route *cur_or;
  388. route_unlock_node (rn);
  389. cur_or = rn->info;
  390. if (v->distance > cur_or->cost ||
  391. IPV4_ADDR_CMP (&cur_or->u.std.origin->id, &lsa->header.id) > 0)
  392. return;
  393. ospf_route_free (rn->info);
  394. }
  395. or = ospf_route_new ();
  396. or->id = v->id;
  397. or->u.std.area_id = area->area_id;
  398. #ifdef HAVE_NSSA
  399. or->u.std.external_routing = area->external_routing;
  400. #endif /* HAVE_NSSA */
  401. or->path_type = OSPF_PATH_INTRA_AREA;
  402. or->cost = v->distance;
  403. or->type = OSPF_DESTINATION_NETWORK;
  404. or->u.std.origin = (struct lsa_header *) lsa;
  405. ospf_route_copy_nexthops_from_vertex (or, v);
  406. rn->info = or;
  407. }
  408. /* RFC2328 16.1. second stage. */
  409. void
  410. ospf_intra_add_stub (struct route_table *rt, struct router_lsa_link *link,
  411. struct vertex *v, struct ospf_area *area)
  412. {
  413. u_int32_t cost;
  414. struct route_node *rn;
  415. struct ospf_route *or;
  416. struct prefix_ipv4 p;
  417. struct router_lsa *lsa;
  418. struct ospf_interface *oi;
  419. struct ospf_path *path;
  420. if (IS_DEBUG_OSPF_EVENT)
  421. zlog_info ("ospf_intra_add_stub(): Start");
  422. lsa = (struct router_lsa *) v->lsa;
  423. p.family = AF_INET;
  424. p.prefix = link->link_id;
  425. p.prefixlen = ip_masklen (link->link_data);
  426. apply_mask_ipv4 (&p);
  427. if (IS_DEBUG_OSPF_EVENT)
  428. zlog_info ("ospf_intra_add_stub(): processing route to %s/%d",
  429. inet_ntoa (p.prefix), p.prefixlen);
  430. /* (1) Calculate the distance D of stub network from the root. D is
  431. equal to the distance from the root to the router vertex
  432. (calculated in stage 1), plus the stub network link's advertised
  433. cost. */
  434. cost = v->distance + ntohs (link->m[0].metric);
  435. if (IS_DEBUG_OSPF_EVENT)
  436. zlog_info ("ospf_intra_add_stub(): calculated cost is %d + %d = %d",
  437. v->distance, ntohs(link->m[0].metric), cost);
  438. rn = route_node_get (rt, (struct prefix *) &p);
  439. /* Lookup current routing table. */
  440. if (rn->info)
  441. {
  442. struct ospf_route *cur_or;
  443. route_unlock_node (rn);
  444. cur_or = rn->info;
  445. if (IS_DEBUG_OSPF_EVENT)
  446. zlog_info ("ospf_intra_add_stub(): "
  447. "another route to the same prefix found");
  448. /* Compare this distance to the current best cost to the stub
  449. network. This is done by looking up the stub network's
  450. current routing table entry. If the calculated distance D is
  451. larger, go on to examine the next stub network link in the
  452. LSA. */
  453. if (cost > cur_or->cost)
  454. {
  455. if (IS_DEBUG_OSPF_EVENT)
  456. zlog_info ("ospf_intra_add_stub(): old route is better, exit");
  457. return;
  458. }
  459. /* (2) If this step is reached, the stub network's routing table
  460. entry must be updated. Calculate the set of next hops that
  461. would result from using the stub network link. This
  462. calculation is shown in Section 16.1.1; input to this
  463. calculation is the destination (the stub network) and the
  464. parent vertex (the router vertex). If the distance D is the
  465. same as the current routing table cost, simply add this set
  466. of next hops to the routing table entry's list of next hops.
  467. In this case, the routing table already has a Link State
  468. Origin. If this Link State Origin is a router-LSA whose Link
  469. State ID is smaller than V's Router ID, reset the Link State
  470. Origin to V's router-LSA. */
  471. if (cost == cur_or->cost)
  472. {
  473. if (IS_DEBUG_OSPF_EVENT)
  474. zlog_info ("ospf_intra_add_stub(): routes are equal, merge");
  475. ospf_route_copy_nexthops_from_vertex (cur_or, v);
  476. if (IPV4_ADDR_CMP (&cur_or->u.std.origin->id, &lsa->header.id) < 0)
  477. cur_or->u.std.origin = (struct lsa_header *) lsa;
  478. return;
  479. }
  480. /* Otherwise D is smaller than the routing table cost.
  481. Overwrite the current routing table entry by setting the
  482. routing table entry's cost to D, and by setting the entry's
  483. list of next hops to the newly calculated set. Set the
  484. routing table entry's Link State Origin to V's router-LSA.
  485. Then go on to examine the next stub network link. */
  486. if (cost < cur_or->cost)
  487. {
  488. if (IS_DEBUG_OSPF_EVENT)
  489. zlog_info ("ospf_intra_add_stub(): new route is better, set it");
  490. cur_or->cost = cost;
  491. list_delete_all_node (cur_or->paths);
  492. ospf_route_copy_nexthops_from_vertex (cur_or, v);
  493. cur_or->u.std.origin = (struct lsa_header *) lsa;
  494. return;
  495. }
  496. }
  497. if (IS_DEBUG_OSPF_EVENT)
  498. zlog_info ("ospf_intra_add_stub(): installing new route");
  499. or = ospf_route_new ();
  500. or->id = v->id;
  501. or->u.std.area_id = area->area_id;
  502. #ifdef HAVE_NSSA
  503. or->u.std.external_routing = area->external_routing;
  504. #endif /* HAVE_NSSA */
  505. or->path_type = OSPF_PATH_INTRA_AREA;
  506. or->cost = cost;
  507. or->type = OSPF_DESTINATION_NETWORK;
  508. or->u.std.origin = (struct lsa_header *) lsa;
  509. /* Nexthop is depend on connection type. */
  510. if (v != area->spf)
  511. {
  512. if (IS_DEBUG_OSPF_EVENT)
  513. zlog_info ("ospf_intra_add_stub(): this network is on remote router");
  514. ospf_route_copy_nexthops_from_vertex (or, v);
  515. }
  516. else
  517. {
  518. if (IS_DEBUG_OSPF_EVENT)
  519. zlog_info ("ospf_intra_add_stub(): this network is on this router");
  520. if ((oi = ospf_if_lookup_by_prefix (area->ospf, &p)))
  521. {
  522. if (IS_DEBUG_OSPF_EVENT)
  523. zlog_info ("ospf_intra_add_stub(): the interface is %s",
  524. IF_NAME (oi));
  525. path = ospf_path_new ();
  526. path->nexthop.s_addr = 0;
  527. path->oi = oi;
  528. listnode_add (or->paths, path);
  529. }
  530. else
  531. {
  532. if (IS_DEBUG_OSPF_EVENT)
  533. zlog_info ("ospf_intra_add_stub(): where's the interface ?");
  534. }
  535. }
  536. rn->info = or;
  537. if (IS_DEBUG_OSPF_EVENT)
  538. zlog_info("ospf_intra_add_stub(): Stop");
  539. }
  540. char *ospf_path_type_str[] =
  541. {
  542. "unknown-type",
  543. "intra-area",
  544. "inter-area",
  545. "type1-external",
  546. "type2-external"
  547. };
  548. void
  549. ospf_route_table_dump (struct route_table *rt)
  550. {
  551. struct route_node *rn;
  552. struct ospf_route *or;
  553. char buf1[BUFSIZ];
  554. char buf2[BUFSIZ];
  555. listnode pnode;
  556. struct ospf_path *path;
  557. #if 0
  558. zlog_info ("Type Dest Area Path Type Cost Next Adv.");
  559. zlog_info (" Hop(s) Router(s)");
  560. #endif /* 0 */
  561. zlog_info ("========== OSPF routing table ==========");
  562. for (rn = route_top (rt); rn; rn = route_next (rn))
  563. if ((or = rn->info) != NULL)
  564. {
  565. if (or->type == OSPF_DESTINATION_NETWORK)
  566. {
  567. zlog_info ("N %s/%d\t%s\t%s\t%d",
  568. inet_ntop (AF_INET, &rn->p.u.prefix4, buf1, BUFSIZ),
  569. rn->p.prefixlen,
  570. inet_ntop (AF_INET, &or->u.std.area_id, buf2,
  571. BUFSIZ),
  572. ospf_path_type_str[or->path_type],
  573. or->cost);
  574. for (pnode = listhead (or->paths); pnode; nextnode (pnode))
  575. {
  576. path = getdata (pnode);
  577. zlog_info (" -> %s", inet_ntoa (path->nexthop));
  578. }
  579. }
  580. else
  581. zlog_info ("R %s\t%s\t%s\t%d",
  582. inet_ntop (AF_INET, &rn->p.u.prefix4, buf1, BUFSIZ),
  583. inet_ntop (AF_INET, &or->u.std.area_id, buf2,
  584. BUFSIZ),
  585. ospf_path_type_str[or->path_type],
  586. or->cost);
  587. }
  588. zlog_info ("========================================");
  589. }
  590. void
  591. ospf_terminate ()
  592. {
  593. struct ospf *ospf;
  594. listnode node;
  595. LIST_LOOP (om->ospf, ospf, node)
  596. {
  597. if (ospf->new_table)
  598. ospf_route_delete (ospf->new_table);
  599. if (ospf->old_external_route)
  600. ospf_route_delete (ospf->old_external_route);
  601. }
  602. }
  603. /* This is 16.4.1 implementation.
  604. o Intra-area paths using non-backbone areas are always the most preferred.
  605. o The other paths, intra-area backbone paths and inter-area paths,
  606. are of equal preference. */
  607. int
  608. ospf_asbr_route_cmp (struct ospf *ospf, struct ospf_route *r1,
  609. struct ospf_route *r2)
  610. {
  611. u_char r1_type, r2_type;
  612. r1_type = r1->path_type;
  613. r2_type = r2->path_type;
  614. /* If RFC1583Compat flag is on -- all paths are equal. */
  615. if (CHECK_FLAG (ospf->config, OSPF_RFC1583_COMPATIBLE))
  616. return 0;
  617. /* r1/r2 itself is backbone, and it's Inter-area path. */
  618. if (OSPF_IS_AREA_ID_BACKBONE (r1->u.std.area_id))
  619. r1_type = OSPF_PATH_INTER_AREA;
  620. if (OSPF_IS_AREA_ID_BACKBONE (r2->u.std.area_id))
  621. r2_type = OSPF_PATH_INTER_AREA;
  622. return (r1_type - r2_type);
  623. }
  624. /* Compare two routes.
  625. ret < 0 -- r1 is better.
  626. ret == 0 -- r1 and r2 are the same.
  627. ret > 0 -- r2 is better. */
  628. int
  629. ospf_route_cmp (struct ospf *ospf, struct ospf_route *r1,
  630. struct ospf_route *r2)
  631. {
  632. int ret = 0;
  633. /* Path types of r1 and r2 are not the same. */
  634. if ((ret = (r1->path_type - r2->path_type)))
  635. return ret;
  636. if (IS_DEBUG_OSPF_EVENT)
  637. zlog_info ("Route[Compare]: Path types are the same.");
  638. /* Path types are the same, compare any cost. */
  639. switch (r1->path_type)
  640. {
  641. case OSPF_PATH_INTRA_AREA:
  642. case OSPF_PATH_INTER_AREA:
  643. break;
  644. case OSPF_PATH_TYPE1_EXTERNAL:
  645. if (!CHECK_FLAG (ospf->config, OSPF_RFC1583_COMPATIBLE))
  646. {
  647. ret = ospf_asbr_route_cmp (ospf, r1->u.ext.asbr, r2->u.ext.asbr);
  648. if (ret != 0)
  649. return ret;
  650. }
  651. break;
  652. case OSPF_PATH_TYPE2_EXTERNAL:
  653. if ((ret = (r1->u.ext.type2_cost - r2->u.ext.type2_cost)))
  654. return ret;
  655. if (!CHECK_FLAG (ospf->config, OSPF_RFC1583_COMPATIBLE))
  656. {
  657. ret = ospf_asbr_route_cmp (ospf, r1->u.ext.asbr, r2->u.ext.asbr);
  658. if (ret != 0)
  659. return ret;
  660. }
  661. break;
  662. }
  663. /* Anyway, compare the costs. */
  664. return (r1->cost - r2->cost);
  665. }
  666. int
  667. ospf_path_exist (struct list *plist, struct in_addr nexthop,
  668. struct ospf_interface *oi)
  669. {
  670. listnode node;
  671. struct ospf_path *path;
  672. for (node = listhead (plist); node; nextnode (node))
  673. {
  674. path = node->data;
  675. if (IPV4_ADDR_SAME (&path->nexthop, &nexthop) && path->oi == oi)
  676. return 1;
  677. }
  678. return 0;
  679. }
  680. void
  681. ospf_route_copy_nexthops_from_vertex (struct ospf_route *to,
  682. struct vertex *v)
  683. {
  684. listnode nnode;
  685. struct ospf_path *path;
  686. struct vertex_nexthop *nexthop;
  687. assert (to->paths);
  688. for (nnode = listhead (v->nexthop); nnode; nextnode (nnode))
  689. {
  690. nexthop = getdata (nnode);
  691. if (nexthop->oi != NULL)
  692. {
  693. if (! ospf_path_exist (to->paths, nexthop->router, nexthop->oi))
  694. {
  695. path = ospf_path_new ();
  696. path->nexthop = nexthop->router;
  697. path->oi = nexthop->oi;
  698. listnode_add (to->paths, path);
  699. }
  700. }
  701. }
  702. }
  703. struct ospf_path *
  704. ospf_path_lookup (list plist, struct ospf_path *path)
  705. {
  706. listnode node;
  707. for (node = listhead (plist); node; nextnode (node))
  708. {
  709. struct ospf_path *op = node->data;
  710. if (IPV4_ADDR_SAME (&op->nexthop, &path->nexthop) &&
  711. IPV4_ADDR_SAME (&op->adv_router, &path->adv_router))
  712. return op;
  713. }
  714. return NULL;
  715. }
  716. void
  717. ospf_route_copy_nexthops (struct ospf_route *to, list from)
  718. {
  719. listnode node;
  720. assert (to->paths);
  721. for (node = listhead (from); node; nextnode (node))
  722. /* The same routes are just discarded. */
  723. if (!ospf_path_lookup (to->paths, node->data))
  724. listnode_add (to->paths, ospf_path_dup (node->data));
  725. }
  726. void
  727. ospf_route_subst_nexthops (struct ospf_route *to, list from)
  728. {
  729. list_delete_all_node (to->paths);
  730. ospf_route_copy_nexthops (to, from);
  731. }
  732. void
  733. ospf_route_subst (struct route_node *rn, struct ospf_route *new_or,
  734. struct ospf_route *over)
  735. {
  736. route_lock_node (rn);
  737. ospf_route_free (rn->info);
  738. ospf_route_copy_nexthops (new_or, over->paths);
  739. rn->info = new_or;
  740. route_unlock_node (rn);
  741. }
  742. void
  743. ospf_route_add (struct route_table *rt, struct prefix_ipv4 *p,
  744. struct ospf_route *new_or, struct ospf_route *over)
  745. {
  746. struct route_node *rn;
  747. rn = route_node_get (rt, (struct prefix *) p);
  748. ospf_route_copy_nexthops (new_or, over->paths);
  749. if (rn->info)
  750. {
  751. if (IS_DEBUG_OSPF_EVENT)
  752. zlog_info ("ospf_route_add(): something's wrong !");
  753. route_unlock_node (rn);
  754. return;
  755. }
  756. rn->info = new_or;
  757. }
  758. void
  759. ospf_prune_unreachable_networks (struct route_table *rt)
  760. {
  761. struct route_node *rn, *next;
  762. struct ospf_route *or;
  763. if (IS_DEBUG_OSPF_EVENT)
  764. zlog_info ("Pruning unreachable networks");
  765. for (rn = route_top (rt); rn; rn = next)
  766. {
  767. next = route_next (rn);
  768. if (rn->info != NULL)
  769. {
  770. or = rn->info;
  771. if (listcount (or->paths) == 0)
  772. {
  773. if (IS_DEBUG_OSPF_EVENT)
  774. zlog_info ("Pruning route to %s/%d",
  775. inet_ntoa (rn->p.u.prefix4), rn->p.prefixlen);
  776. ospf_route_free (or);
  777. rn->info = NULL;
  778. route_unlock_node (rn);
  779. }
  780. }
  781. }
  782. }
  783. void
  784. ospf_prune_unreachable_routers (struct route_table *rtrs)
  785. {
  786. struct route_node *rn, *next;
  787. struct ospf_route *or;
  788. listnode node, nnext;
  789. list paths;
  790. if (IS_DEBUG_OSPF_EVENT)
  791. zlog_info ("Pruning unreachable routers");
  792. for (rn = route_top (rtrs); rn; rn = next)
  793. {
  794. next = route_next (rn);
  795. if ((paths = rn->info) == NULL)
  796. continue;
  797. for (node = listhead (paths); node; node = nnext)
  798. {
  799. nnext = node->next;
  800. or = getdata (node);
  801. if (listcount (or->paths) == 0)
  802. {
  803. if (IS_DEBUG_OSPF_EVENT)
  804. {
  805. zlog_info ("Pruning route to rtr %s",
  806. inet_ntoa (rn->p.u.prefix4));
  807. zlog_info (" via area %s",
  808. inet_ntoa (or->u.std.area_id));
  809. }
  810. listnode_delete (paths, or);
  811. ospf_route_free (or);
  812. }
  813. }
  814. if (listcount (paths) == 0)
  815. {
  816. if (IS_DEBUG_OSPF_EVENT)
  817. zlog_info ("Pruning router node %s", inet_ntoa (rn->p.u.prefix4));
  818. list_delete (paths);
  819. rn->info = NULL;
  820. route_unlock_node (rn);
  821. }
  822. }
  823. }
  824. int
  825. ospf_add_discard_route (struct route_table *rt, struct ospf_area *area,
  826. struct prefix_ipv4 *p)
  827. {
  828. struct route_node *rn;
  829. struct ospf_route *or, *new_or;
  830. rn = route_node_get (rt, (struct prefix *) p);
  831. if (rn == NULL)
  832. {
  833. if (IS_DEBUG_OSPF_EVENT)
  834. zlog_info ("ospf_add_discard_route(): router installation error");
  835. return 0;
  836. }
  837. if (rn->info) /* If the route to the same destination is found */
  838. {
  839. route_unlock_node (rn);
  840. or = rn->info;
  841. if (or->path_type == OSPF_PATH_INTRA_AREA)
  842. {
  843. if (IS_DEBUG_OSPF_EVENT)
  844. zlog_info ("ospf_add_discard_route(): "
  845. "an intra-area route exists");
  846. return 0;
  847. }
  848. if (or->type == OSPF_DESTINATION_DISCARD)
  849. {
  850. if (IS_DEBUG_OSPF_EVENT)
  851. zlog_info ("ospf_add_discard_route(): "
  852. "discard entry already installed");
  853. return 0;
  854. }
  855. ospf_route_free (rn->info);
  856. }
  857. new_or = ospf_route_new ();
  858. new_or->type = OSPF_DESTINATION_DISCARD;
  859. new_or->id.s_addr = 0;
  860. new_or->cost = 0;
  861. new_or->u.std.area_id = area->area_id;
  862. #ifdef HAVE_NSSA
  863. new_or->u.std.external_routing = area->external_routing;
  864. #endif /* HAVE_NSSA */
  865. new_or->path_type = OSPF_PATH_INTER_AREA;
  866. rn->info = new_or;
  867. ospf_zebra_add_discard (p);
  868. return 1;
  869. }
  870. void
  871. ospf_delete_discard_route (struct prefix_ipv4 *p)
  872. {
  873. ospf_zebra_delete_discard(p);
  874. }