ospf6_flood.c 28 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886
  1. /*
  2. * Copyright (C) 2003 Yasuhiro Ohara
  3. *
  4. * This file is part of GNU Zebra.
  5. *
  6. * GNU Zebra is free software; you can redistribute it and/or modify it
  7. * under the terms of the GNU General Public License as published by the
  8. * Free Software Foundation; either version 2, or (at your option) any
  9. * later version.
  10. *
  11. * GNU Zebra is distributed in the hope that it will be useful, but
  12. * WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14. * General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU General Public License
  17. * along with GNU Zebra; see the file COPYING. If not, write to the
  18. * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19. * Boston, MA 02111-1307, USA.
  20. */
  21. #include <zebra.h>
  22. #include "log.h"
  23. #include "thread.h"
  24. #include "linklist.h"
  25. #include "vty.h"
  26. #include "ospf6d.h"
  27. #include "ospf6_proto.h"
  28. #include "ospf6_lsa.h"
  29. #include "ospf6_lsdb.h"
  30. #include "ospf6_message.h"
  31. #include "ospf6_route.h"
  32. #include "ospf6_spf.h"
  33. #include "ospf6_top.h"
  34. #include "ospf6_area.h"
  35. #include "ospf6_interface.h"
  36. #include "ospf6_neighbor.h"
  37. void *
  38. ospf6_get_lsa_scope (u_int16_t type, struct ospf6_neighbor *from)
  39. {
  40. void *scope = NULL;
  41. if (from == NULL)
  42. return NULL;
  43. switch (OSPF6_LSA_SCOPE (type))
  44. {
  45. case OSPF6_LSA_SCOPE_AS:
  46. scope = (from)->ospf6_if->area->ospf6;
  47. break;
  48. case OSPF6_LSA_SCOPE_AREA:
  49. scope = (from)->ospf6_if->area;
  50. break;
  51. case OSPF6_LSA_SCOPE_LINKLOCAL:
  52. scope = (from)->ospf6_if;
  53. break;
  54. default:
  55. break;
  56. }
  57. return scope;
  58. }
  59. struct ospf6_lsdb *
  60. ospf6_get_scoped_lsdb (u_int16_t type, void *scope)
  61. {
  62. struct ospf6_lsdb *lsdb = NULL;
  63. if (scope == NULL)
  64. return NULL;
  65. switch (OSPF6_LSA_SCOPE (type))
  66. {
  67. case OSPF6_LSA_SCOPE_AS:
  68. lsdb = ((struct ospf6 *)(scope))->lsdb;
  69. break;
  70. case OSPF6_LSA_SCOPE_AREA:
  71. lsdb = ((struct ospf6_area *)(scope))->lsdb;
  72. break;
  73. case OSPF6_LSA_SCOPE_LINKLOCAL:
  74. lsdb = ((struct ospf6_interface *)(scope))->lsdb;
  75. break;
  76. default:
  77. break;
  78. }
  79. return lsdb;
  80. }
  81. void
  82. ospf6_decrement_onretrans (struct ospf6_lsa *lsa)
  83. {
  84. struct ospf6_lsdb *lsdb;
  85. struct ospf6_lsa *src;
  86. lsdb = ospf6_get_scoped_lsdb (lsa->header->type, lsa->scope);
  87. if (lsdb == NULL)
  88. {
  89. zlog_warn ("Decrement onretrans: no such scope: %s", lsa->name);
  90. return;
  91. }
  92. src = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
  93. lsa->header->adv_router, lsdb);
  94. if (src && src != lsa)
  95. src->onretrans--;
  96. if (src->onretrans < 0)
  97. zlog_warn ("internal error: onretrans");
  98. }
  99. void
  100. ospf6_flood_clear (struct ospf6_lsa *lsa)
  101. {
  102. struct ospf6_neighbor *on;
  103. struct ospf6_interface *oi, *ospf6_if = NULL;
  104. struct ospf6_area *oa, *area = NULL;
  105. struct ospf6 *ospf6 = NULL;
  106. u_int16_t scope_type;
  107. list scoped_interfaces;
  108. struct ospf6_lsa *rxmt;
  109. listnode i, j;
  110. scoped_interfaces = list_new ();
  111. scope_type = OSPF6_LSA_SCOPE (lsa->header->type);
  112. if (scope_type == OSPF6_LSA_SCOPE_LINKLOCAL)
  113. {
  114. ospf6_if = (struct ospf6_interface *) lsa->scope;
  115. area = ospf6_if->area;
  116. ospf6 = area->ospf6;
  117. }
  118. else if (scope_type == OSPF6_LSA_SCOPE_AREA)
  119. {
  120. area = (struct ospf6_area *) lsa->scope;
  121. ospf6 = area->ospf6;
  122. }
  123. else if (scope_type == OSPF6_LSA_SCOPE_AS)
  124. {
  125. ospf6 = (struct ospf6 *) lsa->scope;
  126. }
  127. else
  128. {
  129. zlog_warn ("Can't decide LSA scope, quit ospf6_flood_clear ()");
  130. return;
  131. }
  132. /* Collect eligible interfaces */
  133. for (i = listhead (ospf6->area_list); i; nextnode (i))
  134. {
  135. oa = (struct ospf6_area *) getdata (i);
  136. if (scope_type != OSPF6_LSA_SCOPE_AS && oa != area)
  137. continue;
  138. for (j = listhead (oa->if_list); j; nextnode (j))
  139. {
  140. oi = (struct ospf6_interface *) getdata (j);
  141. if (scope_type != OSPF6_LSA_SCOPE_AS &&
  142. scope_type != OSPF6_LSA_SCOPE_AREA && oi != ospf6_if)
  143. continue;
  144. listnode_add (scoped_interfaces, oi);
  145. }
  146. }
  147. for (i = listhead (scoped_interfaces); i; nextnode (i))
  148. {
  149. oi = (struct ospf6_interface *) getdata (i);
  150. for (j = listhead (oi->neighbor_list); j; nextnode (j))
  151. {
  152. on = (struct ospf6_neighbor *) getdata (j);
  153. rxmt = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
  154. lsa->header->adv_router, on->retrans_list);
  155. if (rxmt && ! ospf6_lsa_compare (rxmt, lsa))
  156. {
  157. if (IS_OSPF6_DEBUG_LSA (DATABASE))
  158. zlog_info ("Remove %s from retrans_list of %s",
  159. rxmt->name, on->name);
  160. ospf6_decrement_onretrans (rxmt);
  161. ospf6_lsdb_remove (rxmt, on->retrans_list);
  162. }
  163. }
  164. }
  165. list_delete (scoped_interfaces);
  166. }
  167. /* RFC2328 section 13.2 Installing LSAs in the database */
  168. void
  169. ospf6_install_lsa (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
  170. {
  171. struct ospf6_lsa *old;
  172. if (IS_OSPF6_DEBUG_LSA (RECV) || IS_OSPF6_DEBUG_LSA (DATABASE))
  173. zlog_info ("Install LSA: %s", lsa->name);
  174. /* Remove the old instance from all neighbors' Link state
  175. retransmission list (RFC2328 13.2 last paragraph) */
  176. old = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
  177. lsa->header->adv_router, lsdb);
  178. if (old)
  179. ospf6_flood_clear (old);
  180. /* actually install */
  181. gettimeofday (&lsa->installed, (struct timezone *) NULL);
  182. ospf6_lsdb_add (lsa, lsdb);
  183. return;
  184. }
  185. /* RFC2328 section 13.3 Next step in the flooding procedure */
  186. void
  187. ospf6_flood_lsa (struct ospf6_lsa *lsa, struct ospf6_neighbor *from)
  188. {
  189. struct ospf6 *scope_as = NULL;
  190. struct ospf6_area *oa, *scope_area = NULL;
  191. struct ospf6_interface *oi, *scope_linklocal = NULL;
  192. struct ospf6_neighbor *on;
  193. list eligible_interfaces;
  194. listnode i, j;
  195. u_int16_t scope_type;
  196. struct ospf6_lsa *req;
  197. int retrans_added = 0;
  198. scope_type = OSPF6_LSA_SCOPE (lsa->header->type);
  199. switch (scope_type)
  200. {
  201. case OSPF6_LSA_SCOPE_AS:
  202. scope_as = (struct ospf6 *) lsa->scope;
  203. break;
  204. case OSPF6_LSA_SCOPE_AREA:
  205. scope_as = ((struct ospf6_area *) lsa->scope)->ospf6;
  206. scope_area = (struct ospf6_area *) lsa->scope;
  207. break;
  208. case OSPF6_LSA_SCOPE_LINKLOCAL:
  209. scope_as = ((struct ospf6_interface *) lsa->scope)->area->ospf6;
  210. scope_area = ((struct ospf6_interface *) lsa->scope)->area;
  211. scope_linklocal = (struct ospf6_interface *) lsa->scope;
  212. break;
  213. default:
  214. if (IS_OSPF6_DEBUG_LSA (SEND))
  215. zlog_info ("Can't decide LSA scope");
  216. return;
  217. }
  218. if (IS_OSPF6_DEBUG_LSA (SEND))
  219. zlog_info ("Flood %s", lsa->name);
  220. /* Collect eligible interfaces */
  221. eligible_interfaces = list_new ();
  222. for (i = listhead (scope_as->area_list); i; nextnode (i))
  223. {
  224. oa = (struct ospf6_area *) getdata (i);
  225. if (scope_type != OSPF6_LSA_SCOPE_AS &&
  226. oa != scope_area)
  227. continue;
  228. for (j = listhead (oa->if_list); j; nextnode (j))
  229. {
  230. oi = (struct ospf6_interface *) getdata (j);
  231. if (scope_type != OSPF6_LSA_SCOPE_AS &&
  232. scope_type != OSPF6_LSA_SCOPE_AREA &&
  233. oi != scope_linklocal)
  234. continue;
  235. listnode_add (eligible_interfaces, oi);
  236. }
  237. }
  238. /* For each eligible interface: */
  239. for (i = listhead (eligible_interfaces); i; nextnode (i))
  240. {
  241. oi = (struct ospf6_interface *) getdata (i);
  242. /* (1) For each neighbor */
  243. for (j = listhead (oi->neighbor_list); j; nextnode (j))
  244. {
  245. on = (struct ospf6_neighbor *) getdata (j);
  246. /* (a) if neighbor state < Exchange, examin next */
  247. if (on->state < OSPF6_NEIGHBOR_EXCHANGE)
  248. continue;
  249. /* (b) if neighbor not yet Full, check request-list */
  250. if (on->state != OSPF6_NEIGHBOR_FULL)
  251. {
  252. req = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
  253. lsa->header->adv_router,
  254. on->request_list);
  255. if (req)
  256. {
  257. /* If new LSA less recent, examin next neighbor */
  258. if (ospf6_lsa_compare (lsa, req) > 0)
  259. continue;
  260. /* If the same instance, delete from request-list and
  261. examin next neighbor */
  262. if (ospf6_lsa_compare (lsa, req) == 0)
  263. {
  264. if (IS_OSPF6_DEBUG_LSA (SEND) || IS_OSPF6_DEBUG_LSA (DATABASE))
  265. zlog_info ("Remove %s from request-list of %s: "
  266. "the same instance", req->name, on->name);
  267. ospf6_lsdb_remove (req, on->request_list);
  268. continue;
  269. }
  270. /* If the new LSA is more recent, delete from
  271. request-list */
  272. if (ospf6_lsa_compare (lsa, req) < 0)
  273. {
  274. if (IS_OSPF6_DEBUG_LSA (SEND) || IS_OSPF6_DEBUG_LSA (DATABASE))
  275. zlog_info ("Remove %s from request-list of %s: "
  276. "newer instance", req->name, on->name);
  277. ospf6_lsdb_remove (req, on->request_list);
  278. /* fall through */
  279. }
  280. }
  281. }
  282. /* (c) If the new LSA was received from this neighbor,
  283. examin next neighbor */
  284. if (from == on)
  285. continue;
  286. /* (d) add retrans-list, schedule retransmission */
  287. if (IS_OSPF6_DEBUG_LSA (SEND) || IS_OSPF6_DEBUG_LSA (DATABASE))
  288. zlog_info (" Add copy of %s to retrans-list of %s",
  289. lsa->name, on->name);
  290. lsa->onretrans++;
  291. ospf6_lsdb_add (ospf6_lsa_copy (lsa), on->retrans_list);
  292. if (on->thread_send_lsupdate == NULL)
  293. on->thread_send_lsupdate =
  294. thread_add_event (master, ospf6_lsupdate_send_neighbor,
  295. on, on->ospf6_if->rxmt_interval);
  296. retrans_added++;
  297. }
  298. /* (2) examin next interface if not added to retrans-list */
  299. if (retrans_added == 0)
  300. continue;
  301. /* (3) If the new LSA was received on this interface,
  302. and it was from DR or BDR, examin next interface */
  303. if (from && from->ospf6_if == oi &&
  304. (from->router_id == oi->drouter || from->router_id == oi->bdrouter))
  305. continue;
  306. /* (4) If the new LSA was received on this interface,
  307. and the interface state is BDR, examin next interface */
  308. if (from && from->ospf6_if == oi && oi->state == OSPF6_INTERFACE_BDR)
  309. continue;
  310. /* (5) flood the LSA out the interface. */
  311. if (if_is_broadcast (oi->interface))
  312. {
  313. if (IS_OSPF6_DEBUG_LSA (SEND) || IS_OSPF6_DEBUG_LSA (DATABASE))
  314. zlog_info (" Add copy of %s to lsupdate_list of %s",
  315. lsa->name, oi->interface->name);
  316. ospf6_lsdb_add (ospf6_lsa_copy (lsa), oi->lsupdate_list);
  317. if (oi->thread_send_lsupdate == NULL)
  318. oi->thread_send_lsupdate =
  319. thread_add_event (master, ospf6_lsupdate_send_interface, oi, 0);
  320. }
  321. else
  322. {
  323. for (j = listhead (oi->neighbor_list); j; nextnode (j))
  324. {
  325. on = (struct ospf6_neighbor *) getdata (j);
  326. THREAD_OFF (on->thread_send_lsupdate);
  327. on->thread_send_lsupdate =
  328. thread_add_event (master, ospf6_lsupdate_send_neighbor, on, 0);
  329. }
  330. }
  331. }
  332. list_delete (eligible_interfaces);
  333. }
  334. /* RFC2328 13.5 (Table 19): Sending link state acknowledgements. */
  335. static void
  336. ospf6_acknowledge_lsa_bdrouter (struct ospf6_lsa *lsa, int ismore_recent,
  337. struct ospf6_neighbor *from)
  338. {
  339. struct ospf6_interface *oi;
  340. assert (from && from->ospf6_if);
  341. oi = from->ospf6_if;
  342. /* LSA has been flood back out receiving interface.
  343. No acknowledgement sent. */
  344. if (CHECK_FLAG (lsa->flag, OSPF6_LSA_FLOODBACK))
  345. {
  346. if (IS_OSPF6_DEBUG_LSA (RECV))
  347. zlog_info (" BDR, FloodBack, No acknowledgement.");
  348. return;
  349. }
  350. /* LSA is more recent than database copy, but was not flooded
  351. back out receiving interface. Delayed acknowledgement sent
  352. if advertisement received from Designated Router,
  353. otherwide do nothing. */
  354. if (ismore_recent < 0)
  355. {
  356. if (IS_OSPF6_DEBUG_LSA (RECV))
  357. zlog_info (" BDR, Not FloodBack, MoreRecent, ");
  358. if (oi->drouter == from->router_id)
  359. {
  360. if (IS_OSPF6_DEBUG_LSA (RECV))
  361. zlog_info (" From DR, Delayed acknowledgement.");
  362. /* Delayed acknowledgement */
  363. if (IS_OSPF6_DEBUG_LSA (DATABASE))
  364. zlog_info (" Add copy of %s to lsack_list of %s",
  365. lsa->name, oi->interface->name);
  366. ospf6_lsdb_add (ospf6_lsa_copy (lsa), oi->lsack_list);
  367. if (oi->thread_send_lsack == NULL)
  368. oi->thread_send_lsack =
  369. thread_add_timer (master, ospf6_lsack_send_interface, oi, 3);
  370. }
  371. else
  372. {
  373. if (IS_OSPF6_DEBUG_LSA (RECV))
  374. zlog_info (" Not From DR, No acknowledgement.");
  375. }
  376. return;
  377. }
  378. /* LSA is a duplicate, and was treated as an implied acknowledgement.
  379. Delayed acknowledgement sent if advertisement received from
  380. Designated Router, otherwise do nothing */
  381. if (CHECK_FLAG (lsa->flag, OSPF6_LSA_DUPLICATE) &&
  382. CHECK_FLAG (lsa->flag, OSPF6_LSA_IMPLIEDACK))
  383. {
  384. if (IS_OSPF6_DEBUG_LSA (RECV))
  385. zlog_info (" BDR, Duplicate, ImpliedAck, ");
  386. if (oi->drouter == from->router_id)
  387. {
  388. if (IS_OSPF6_DEBUG_LSA (RECV))
  389. zlog_info (" From DR, Delayed acknowledgement.");
  390. /* Delayed acknowledgement */
  391. if (IS_OSPF6_DEBUG_LSA (DATABASE))
  392. zlog_info (" Add copy of %s to lsack_list of %s",
  393. lsa->name, oi->interface->name);
  394. ospf6_lsdb_add (ospf6_lsa_copy (lsa), oi->lsack_list);
  395. if (oi->thread_send_lsack == NULL)
  396. oi->thread_send_lsack =
  397. thread_add_timer (master, ospf6_lsack_send_interface, oi, 3);
  398. }
  399. else
  400. {
  401. if (IS_OSPF6_DEBUG_LSA (RECV))
  402. zlog_info (" Not From DR, No acknowledgement.");
  403. }
  404. return;
  405. }
  406. /* LSA is a duplicate, and was not treated as an implied acknowledgement.
  407. Direct acknowledgement sent */
  408. if (CHECK_FLAG (lsa->flag, OSPF6_LSA_DUPLICATE) &&
  409. ! CHECK_FLAG (lsa->flag, OSPF6_LSA_IMPLIEDACK))
  410. {
  411. if (IS_OSPF6_DEBUG_LSA (RECV))
  412. zlog_info (" BDR, Duplicate, Not ImpliedAck, Direct acknowledgement.");
  413. if (IS_OSPF6_DEBUG_LSA (DATABASE))
  414. zlog_info (" Add copy of %s to lsack_list of %s",
  415. lsa->name, from->name);
  416. ospf6_lsdb_add (ospf6_lsa_copy (lsa), from->lsack_list);
  417. if (from->thread_send_lsack == NULL)
  418. from->thread_send_lsack =
  419. thread_add_event (master, ospf6_lsack_send_neighbor, from, 0);
  420. return;
  421. }
  422. /* LSA's LS age is equal to Maxage, and there is no current instance
  423. of the LSA in the link state database, and none of router's
  424. neighbors are in states Exchange or Loading */
  425. /* Direct acknowledgement sent, but this case is handled in
  426. early of ospf6_receive_lsa () */
  427. }
  428. static void
  429. ospf6_acknowledge_lsa_allother (struct ospf6_lsa *lsa, int ismore_recent,
  430. struct ospf6_neighbor *from)
  431. {
  432. struct ospf6_interface *oi;
  433. assert (from && from->ospf6_if);
  434. oi = from->ospf6_if;
  435. /* LSA has been flood back out receiving interface.
  436. No acknowledgement sent. */
  437. if (CHECK_FLAG (lsa->flag, OSPF6_LSA_FLOODBACK))
  438. {
  439. if (IS_OSPF6_DEBUG_LSA (RECV))
  440. zlog_info (" AllOther, FloodBack, No acknowledgement.");
  441. return;
  442. }
  443. /* LSA is more recent than database copy, but was not flooded
  444. back out receiving interface. Delayed acknowledgement sent. */
  445. if (ismore_recent < 0)
  446. {
  447. if (IS_OSPF6_DEBUG_LSA (RECV))
  448. zlog_info (" AllOther, Not FloodBack, Delayed acknowledgement.");
  449. /* Delayed acknowledgement */
  450. if (IS_OSPF6_DEBUG_LSA (DATABASE))
  451. zlog_info (" Add copy of %s to lsack_list of %s",
  452. lsa->name, oi->interface->name);
  453. ospf6_lsdb_add (ospf6_lsa_copy (lsa), oi->lsack_list);
  454. if (oi->thread_send_lsack == NULL)
  455. oi->thread_send_lsack =
  456. thread_add_timer (master, ospf6_lsack_send_interface, oi, 3);
  457. return;
  458. }
  459. /* LSA is a duplicate, and was treated as an implied acknowledgement.
  460. No acknowledgement sent. */
  461. if (CHECK_FLAG (lsa->flag, OSPF6_LSA_DUPLICATE) &&
  462. CHECK_FLAG (lsa->flag, OSPF6_LSA_IMPLIEDACK))
  463. {
  464. if (IS_OSPF6_DEBUG_LSA (RECV))
  465. zlog_info (" AllOther, Duplicate, ImpliedAck, No acknowledgement.");
  466. return;
  467. }
  468. /* LSA is a duplicate, and was not treated as an implied acknowledgement.
  469. Direct acknowledgement sent */
  470. if (CHECK_FLAG (lsa->flag, OSPF6_LSA_DUPLICATE) &&
  471. ! CHECK_FLAG (lsa->flag, OSPF6_LSA_IMPLIEDACK))
  472. {
  473. if (IS_OSPF6_DEBUG_LSA (RECV))
  474. zlog_info (" AllOther, Duplicate, Not ImpliedAck, Direct acknowledgement.");
  475. if (IS_OSPF6_DEBUG_LSA (DATABASE))
  476. zlog_info (" Add copy of %s to lsack_list of %s",
  477. lsa->name, from->name);
  478. ospf6_lsdb_add (ospf6_lsa_copy (lsa), from->lsack_list);
  479. if (from->thread_send_lsack == NULL)
  480. from->thread_send_lsack =
  481. thread_add_event (master, ospf6_lsack_send_neighbor, from, 0);
  482. return;
  483. }
  484. /* LSA's LS age is equal to Maxage, and there is no current instance
  485. of the LSA in the link state database, and none of router's
  486. neighbors are in states Exchange or Loading */
  487. /* Direct acknowledgement sent, but this case is handled in
  488. early of ospf6_receive_lsa () */
  489. }
  490. void
  491. ospf6_acknowledge_lsa (struct ospf6_lsa *lsa, int ismore_recent,
  492. struct ospf6_neighbor *from)
  493. {
  494. struct ospf6_interface *oi;
  495. assert (from && from->ospf6_if);
  496. oi = from->ospf6_if;
  497. if (oi->state == OSPF6_INTERFACE_BDR)
  498. ospf6_acknowledge_lsa_bdrouter (lsa, ismore_recent, from);
  499. else
  500. ospf6_acknowledge_lsa_allother (lsa, ismore_recent, from);
  501. }
  502. /* RFC2328 section 13 (4):
  503. if MaxAge LSA and if we have no instance, and no neighbor
  504. is in states Exchange or Loading
  505. returns 1 if match this case, else returns 0 */
  506. static int
  507. ospf6_is_maxage_lsa_drop (struct ospf6_lsa *lsa,
  508. struct ospf6_neighbor *from)
  509. {
  510. struct ospf6_lsdb *lsdb = NULL;
  511. struct ospf6_neighbor *on;
  512. struct ospf6_interface *oi, *ospf6_if = NULL;
  513. struct ospf6_area *oa, *area = NULL;
  514. struct ospf6 *ospf6 = NULL;
  515. u_int16_t scope_type;
  516. list scoped_interfaces;
  517. listnode i, j;
  518. int count = 0;
  519. if (! OSPF6_LSA_IS_MAXAGE (lsa))
  520. return 0;
  521. lsdb = ospf6_get_scoped_lsdb (lsa->header->type, lsa->scope);
  522. if (lsdb == NULL)
  523. {
  524. zlog_info ("Can't decide scoped LSDB");
  525. return 0;
  526. }
  527. if (ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
  528. lsa->header->adv_router, lsdb))
  529. return 0;
  530. scoped_interfaces = list_new ();
  531. scope_type = OSPF6_LSA_SCOPE (lsa->header->type);
  532. if (scope_type == OSPF6_LSA_SCOPE_LINKLOCAL)
  533. {
  534. ospf6_if = (struct ospf6_interface *) lsa->scope;
  535. area = ospf6_if->area;
  536. ospf6 = area->ospf6;
  537. }
  538. else if (scope_type == OSPF6_LSA_SCOPE_AREA)
  539. {
  540. area = (struct ospf6_area *) lsa->scope;
  541. ospf6 = area->ospf6;
  542. }
  543. else if (scope_type == OSPF6_LSA_SCOPE_AS)
  544. {
  545. ospf6 = (struct ospf6 *) lsa->scope;
  546. }
  547. else
  548. {
  549. zlog_info ("Can't decide LSA scope");
  550. return 0;
  551. }
  552. /* Collect eligible interfaces */
  553. for (i = listhead (ospf6->area_list); i; nextnode (i))
  554. {
  555. oa = (struct ospf6_area *) getdata (i);
  556. if (scope_type != OSPF6_LSA_SCOPE_AS && oa != area)
  557. continue;
  558. for (j = listhead (oa->if_list); j; nextnode (j))
  559. {
  560. oi = (struct ospf6_interface *) getdata (j);
  561. if (scope_type != OSPF6_LSA_SCOPE_AS &&
  562. scope_type != OSPF6_LSA_SCOPE_AREA && oi != ospf6_if)
  563. continue;
  564. listnode_add (scoped_interfaces, oi);
  565. }
  566. }
  567. for (i = listhead (scoped_interfaces); i; nextnode (i))
  568. {
  569. oi = (struct ospf6_interface *) getdata (i);
  570. for (j = listhead (oi->neighbor_list); j; nextnode (j))
  571. {
  572. on = (struct ospf6_neighbor *) getdata (j);
  573. if (on->state == OSPF6_NEIGHBOR_EXCHANGE ||
  574. on->state == OSPF6_NEIGHBOR_LOADING)
  575. count ++;
  576. }
  577. }
  578. list_delete (scoped_interfaces);
  579. if (count == 0)
  580. return 1;
  581. return 0;
  582. }
  583. /* RFC2328 section 13 The Flooding Procedure */
  584. void
  585. ospf6_receive_lsa (struct ospf6_lsa_header *lsa_header,
  586. struct ospf6_neighbor *from)
  587. {
  588. struct ospf6_lsa *new = NULL, *old = NULL, *rem = NULL;
  589. int ismore_recent;
  590. unsigned short cksum;
  591. struct ospf6_lsdb *lsdb = NULL;
  592. ismore_recent = 1;
  593. /* make lsa structure for received lsa */
  594. new = ospf6_lsa_create (lsa_header);
  595. if (IS_OSPF6_DEBUG_LSA (RECV))
  596. {
  597. zlog_info ("LSA Receive from %s", from->name);
  598. ospf6_lsa_header_print (new);
  599. }
  600. new->scope = ospf6_get_lsa_scope (new->header->type, from);
  601. if (new->scope == NULL)
  602. {
  603. zlog_warn ("Can't decide LSA scope, ignore");
  604. ospf6_lsa_delete (new);
  605. return;
  606. }
  607. /* (1) LSA Checksum */
  608. cksum = ntohs (new->header->checksum);
  609. if (ntohs (ospf6_lsa_checksum (new->header)) != cksum)
  610. {
  611. if (IS_OSPF6_DEBUG_LSA (RECV))
  612. zlog_info ("Wrong LSA Checksum");
  613. ospf6_lsa_delete (new);
  614. return;
  615. }
  616. /* (3) Ebit Missmatch: AS-External-LSA */
  617. if (ntohs (new->header->type) == OSPF6_LSTYPE_AS_EXTERNAL &&
  618. ospf6_area_is_stub (from->ospf6_if->area))
  619. {
  620. if (IS_OSPF6_DEBUG_LSA (RECV))
  621. zlog_info ("AS-External-LSA in stub area");
  622. ospf6_lsa_delete (new);
  623. return;
  624. }
  625. /* (4) if MaxAge LSA and if we have no instance, and no neighbor
  626. is in states Exchange or Loading */
  627. if (ospf6_is_maxage_lsa_drop (new, from))
  628. {
  629. /* log */
  630. if (IS_OSPF6_DEBUG_LSA (RECV))
  631. zlog_info ("Drop MaxAge LSA with Direct acknowledgement.");
  632. /* a) Acknowledge back to neighbor (Direct acknowledgement, 13.5) */
  633. if (IS_OSPF6_DEBUG_LSA (DATABASE))
  634. zlog_info (" Add %s to lsack_list of %s",
  635. new->name, from->name);
  636. ospf6_lsdb_add (new, from->lsack_list);
  637. if (from->thread_send_lsack == NULL)
  638. from->thread_send_lsack =
  639. thread_add_event (master, ospf6_lsack_send_neighbor, from, 0);
  640. /* b) Discard */
  641. /* "new" LSA will be discarded just after the LSAck sent */
  642. return;
  643. }
  644. /* (5) */
  645. /* lookup the same database copy in lsdb */
  646. lsdb = ospf6_get_scoped_lsdb (new->header->type, new->scope);
  647. if (lsdb == NULL)
  648. {
  649. zlog_warn ("Can't decide scoped LSDB, ignore");
  650. ospf6_lsa_delete (new);
  651. return;
  652. }
  653. old = ospf6_lsdb_lookup (new->header->type, new->header->id,
  654. new->header->adv_router, lsdb);
  655. if (old)
  656. {
  657. ismore_recent = ospf6_lsa_compare (new, old);
  658. if (ntohl (new->header->seqnum) == ntohl (old->header->seqnum))
  659. {
  660. if (IS_OSPF6_DEBUG_LSA (RECV))
  661. zlog_info ("Duplicated LSA");
  662. SET_FLAG (new->flag, OSPF6_LSA_DUPLICATE);
  663. }
  664. }
  665. /* if no database copy or received is more recent */
  666. if (old == NULL || ismore_recent < 0)
  667. {
  668. /* in case we have no database copy */
  669. ismore_recent = -1;
  670. /* (a) MinLSArrival check */
  671. if (old)
  672. {
  673. struct timeval now, res;
  674. gettimeofday (&now, (struct timezone *) NULL);
  675. timersub (&now, &old->installed, &res);
  676. if (res.tv_sec < MIN_LS_ARRIVAL)
  677. {
  678. if (IS_OSPF6_DEBUG_LSA (RECV) || IS_OSPF6_DEBUG_LSA (TIMER))
  679. zlog_info ("LSA can't be updated within MinLSArrival");
  680. ospf6_lsa_delete (new);
  681. return; /* examin next lsa */
  682. }
  683. }
  684. /* (b) immediately flood and (c) remove from all retrans-list */
  685. ospf6_flood_lsa (new, from);
  686. /* (d), installing lsdb, which may cause routing
  687. table calculation (replacing database copy) */
  688. ospf6_install_lsa (new, lsdb);
  689. /* (e) possibly acknowledge */
  690. ospf6_acknowledge_lsa (new, ismore_recent, from);
  691. /* (f) */
  692. /* Self Originated LSA, section 13.4 */
  693. if (new->header->adv_router == from->ospf6_if->area->ospf6->router_id
  694. && (! old || ismore_recent < 0))
  695. {
  696. /* We have to make a new instance of the LSA
  697. or have to flush this LSA. */
  698. if (IS_OSPF6_DEBUG_LSA (RECV))
  699. zlog_info ("New instance of the self-originated LSA");
  700. SET_FLAG (new->flag, OSPF6_LSA_REFRESH);
  701. ospf6_lsa_re_originate (new);
  702. }
  703. return;
  704. }
  705. /* (6) if there is instance on sending neighbor's request list */
  706. if (ospf6_lsdb_lookup (new->header->type, new->header->id,
  707. new->header->adv_router, from->request_list))
  708. {
  709. /* if no database copy, should go above state (5) */
  710. assert (old);
  711. if (IS_OSPF6_DEBUG_LSA (RECV))
  712. zlog_info ("LSA is not newer and on request-list of sending neighbor");
  713. /* BadLSReq */
  714. thread_add_event (master, bad_lsreq, from, 0);
  715. ospf6_lsa_delete (new);
  716. return;
  717. }
  718. /* (7) if neither one is more recent */
  719. if (ismore_recent == 0)
  720. {
  721. if (IS_OSPF6_DEBUG_LSA (RECV))
  722. zlog_info ("The same instance as database copy");
  723. /* (a) if on retrans-list, Treat this LSA as an Ack: Implied Ack */
  724. rem = ospf6_lsdb_lookup (new->header->type, new->header->id,
  725. new->header->adv_router, from->retrans_list);
  726. if (rem)
  727. {
  728. if (IS_OSPF6_DEBUG_LSA (RECV))
  729. zlog_info ("Treat as an Implied acknowledgement");
  730. SET_FLAG (new->flag, OSPF6_LSA_IMPLIEDACK);
  731. if (IS_OSPF6_DEBUG_LSA (DATABASE))
  732. zlog_info ("Remove %s from retrans_list of %s",
  733. rem->name, from->name);
  734. ospf6_decrement_onretrans (rem);
  735. ospf6_lsdb_remove (rem, from->retrans_list);
  736. }
  737. /* (b) possibly acknowledge */
  738. ospf6_acknowledge_lsa (new, ismore_recent, from);
  739. ospf6_lsa_delete (new);
  740. return;
  741. }
  742. /* (8) previous database copy is more recent */
  743. {
  744. assert (old);
  745. /* If database copy is in 'Seqnumber Wrapping',
  746. simply discard the received LSA */
  747. if (OSPF6_LSA_IS_MAXAGE (old) &&
  748. old->header->seqnum == htonl (MAX_SEQUENCE_NUMBER))
  749. {
  750. if (IS_OSPF6_DEBUG_LSA (RECV))
  751. zlog_info ("Database copy is in Seqnumber Wrapping");
  752. ospf6_lsa_delete (new);
  753. return;
  754. }
  755. /* Otherwise, Send database copy of this LSA to this neighbor */
  756. {
  757. if (IS_OSPF6_DEBUG_LSA (RECV))
  758. zlog_info ("Database is more recent, send back directly");
  759. /* XXX, MinLSArrival check !? RFC 2328 13 (8) */
  760. if (IS_OSPF6_DEBUG_LSA (DATABASE))
  761. zlog_info (" Add copy of %s to lsupdate_list of %s",
  762. old->name, from->name);
  763. ospf6_lsdb_add (ospf6_lsa_copy (old), from->lsupdate_list);
  764. if (from->thread_send_lsupdate == NULL)
  765. from->thread_send_lsupdate =
  766. thread_add_event (master, ospf6_lsupdate_send_neighbor, from, 0);
  767. ospf6_lsa_delete (new);
  768. return;
  769. }
  770. return;
  771. }
  772. }