ospf_route.c 27 KB

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