ospf6_lsdb.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593
  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 "memory.h"
  23. #include "log.h"
  24. #include "command.h"
  25. #include "prefix.h"
  26. #include "table.h"
  27. #include "vty.h"
  28. #include "ospf6_proto.h"
  29. #include "ospf6_lsa.h"
  30. #include "ospf6_lsdb.h"
  31. #include "ospf6d.h"
  32. struct ospf6_lsdb *
  33. ospf6_lsdb_create (void *data)
  34. {
  35. struct ospf6_lsdb *lsdb;
  36. lsdb = XCALLOC (MTYPE_OSPF6_LSDB, sizeof (struct ospf6_lsdb));
  37. if (lsdb == NULL)
  38. {
  39. zlog_warn ("Can't malloc lsdb");
  40. return NULL;
  41. }
  42. memset (lsdb, 0, sizeof (struct ospf6_lsdb));
  43. lsdb->data = data;
  44. lsdb->table = route_table_init ();
  45. return lsdb;
  46. }
  47. void
  48. ospf6_lsdb_delete (struct ospf6_lsdb *lsdb)
  49. {
  50. if (lsdb != NULL)
  51. {
  52. ospf6_lsdb_remove_all (lsdb);
  53. route_table_finish (lsdb->table);
  54. XFREE (MTYPE_OSPF6_LSDB, lsdb);
  55. }
  56. }
  57. static void
  58. ospf6_lsdb_set_key (struct prefix_ipv6 *key, void *value, int len)
  59. {
  60. assert (key->prefixlen % 8 == 0);
  61. memcpy ((caddr_t) &key->prefix + key->prefixlen / 8,
  62. (caddr_t) value, len);
  63. key->family = AF_INET6;
  64. key->prefixlen += len * 8;
  65. }
  66. #ifdef DEBUG
  67. static void
  68. _lsdb_count_assert (struct ospf6_lsdb *lsdb)
  69. {
  70. struct ospf6_lsa *debug;
  71. unsigned int num = 0;
  72. for (debug = ospf6_lsdb_head (lsdb); debug;
  73. debug = ospf6_lsdb_next (debug))
  74. num++;
  75. if (num == lsdb->count)
  76. return;
  77. zlog_debug ("PANIC !! lsdb[%p]->count = %d, real = %d",
  78. lsdb, lsdb->count, num);
  79. for (debug = ospf6_lsdb_head (lsdb); debug;
  80. debug = ospf6_lsdb_next (debug))
  81. zlog_debug ("%p %p %s lsdb[%p]", debug->prev, debug->next, debug->name,
  82. debug->lsdb);
  83. zlog_debug ("DUMP END");
  84. assert (num == lsdb->count);
  85. }
  86. #define ospf6_lsdb_count_assert(t) (_lsdb_count_assert (t))
  87. #else /*DEBUG*/
  88. #define ospf6_lsdb_count_assert(t) ((void) 0)
  89. #endif /*DEBUG*/
  90. void
  91. ospf6_lsdb_add (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
  92. {
  93. struct prefix_ipv6 key;
  94. struct route_node *current;
  95. struct ospf6_lsa *old = NULL;
  96. memset (&key, 0, sizeof (key));
  97. ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type));
  98. ospf6_lsdb_set_key (&key, &lsa->header->adv_router,
  99. sizeof (lsa->header->adv_router));
  100. ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id));
  101. current = route_node_get (lsdb->table, (struct prefix *) &key);
  102. old = current->info;
  103. current->info = lsa;
  104. lsa->rn = current;
  105. ospf6_lsa_lock (lsa);
  106. if (!old)
  107. {
  108. lsdb->count++;
  109. if (OSPF6_LSA_IS_MAXAGE (lsa))
  110. {
  111. if (lsdb->hook_remove)
  112. (*lsdb->hook_remove) (lsa);
  113. }
  114. else
  115. {
  116. if (lsdb->hook_add)
  117. (*lsdb->hook_add) (lsa);
  118. }
  119. }
  120. else
  121. {
  122. if (OSPF6_LSA_IS_CHANGED (old, lsa))
  123. {
  124. if (OSPF6_LSA_IS_MAXAGE (lsa))
  125. {
  126. if (lsdb->hook_remove)
  127. {
  128. (*lsdb->hook_remove) (old);
  129. (*lsdb->hook_remove) (lsa);
  130. }
  131. }
  132. else if (OSPF6_LSA_IS_MAXAGE (old))
  133. {
  134. if (lsdb->hook_add)
  135. (*lsdb->hook_add) (lsa);
  136. }
  137. else
  138. {
  139. if (lsdb->hook_remove)
  140. (*lsdb->hook_remove) (old);
  141. if (lsdb->hook_add)
  142. (*lsdb->hook_add) (lsa);
  143. }
  144. }
  145. ospf6_lsa_unlock (old);
  146. }
  147. ospf6_lsdb_count_assert (lsdb);
  148. }
  149. void
  150. ospf6_lsdb_remove (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
  151. {
  152. struct route_node *node;
  153. struct prefix_ipv6 key;
  154. memset (&key, 0, sizeof (key));
  155. ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type));
  156. ospf6_lsdb_set_key (&key, &lsa->header->adv_router,
  157. sizeof (lsa->header->adv_router));
  158. ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id));
  159. node = route_node_lookup (lsdb->table, (struct prefix *) &key);
  160. assert (node && node->info == lsa);
  161. node->info = NULL;
  162. lsdb->count--;
  163. if (lsdb->hook_remove)
  164. (*lsdb->hook_remove) (lsa);
  165. route_unlock_node (node); /* to free the lookup lock */
  166. route_unlock_node (node); /* to free the original lock */
  167. ospf6_lsa_unlock (lsa);
  168. ospf6_lsdb_count_assert (lsdb);
  169. }
  170. struct ospf6_lsa *
  171. ospf6_lsdb_lookup (u_int16_t type, u_int32_t id, u_int32_t adv_router,
  172. struct ospf6_lsdb *lsdb)
  173. {
  174. struct route_node *node;
  175. struct prefix_ipv6 key;
  176. if (lsdb == NULL)
  177. return NULL;
  178. memset (&key, 0, sizeof (key));
  179. ospf6_lsdb_set_key (&key, &type, sizeof (type));
  180. ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
  181. ospf6_lsdb_set_key (&key, &id, sizeof (id));
  182. node = route_node_lookup (lsdb->table, (struct prefix *) &key);
  183. if (node == NULL || node->info == NULL)
  184. return NULL;
  185. route_unlock_node (node);
  186. return (struct ospf6_lsa *) node->info;
  187. }
  188. struct ospf6_lsa *
  189. ospf6_lsdb_lookup_next (u_int16_t type, u_int32_t id, u_int32_t adv_router,
  190. struct ospf6_lsdb *lsdb)
  191. {
  192. struct route_node *node;
  193. struct route_node *matched = NULL;
  194. struct prefix_ipv6 key;
  195. struct prefix *p;
  196. if (lsdb == NULL)
  197. return NULL;
  198. memset (&key, 0, sizeof (key));
  199. ospf6_lsdb_set_key (&key, &type, sizeof (type));
  200. ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
  201. ospf6_lsdb_set_key (&key, &id, sizeof (id));
  202. p = (struct prefix *) &key;
  203. {
  204. char buf[64];
  205. prefix2str (p, buf, sizeof (buf));
  206. zlog_debug ("lsdb_lookup_next: key: %s", buf);
  207. }
  208. node = lsdb->table->top;
  209. /* walk down tree. */
  210. while (node && node->p.prefixlen <= p->prefixlen &&
  211. prefix_match (&node->p, p))
  212. {
  213. matched = node;
  214. node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
  215. }
  216. if (matched)
  217. node = matched;
  218. else
  219. node = lsdb->table->top;
  220. route_lock_node (node);
  221. /* skip to real existing entry */
  222. while (node && node->info == NULL)
  223. node = route_next (node);
  224. if (! node)
  225. return NULL;
  226. if (prefix_same (&node->p, p))
  227. {
  228. node = route_next (node);
  229. while (node && node->info == NULL)
  230. node = route_next (node);
  231. }
  232. if (! node)
  233. return NULL;
  234. route_unlock_node (node);
  235. return (struct ospf6_lsa *) node->info;
  236. }
  237. /* Iteration function */
  238. struct ospf6_lsa *
  239. ospf6_lsdb_head (struct ospf6_lsdb *lsdb)
  240. {
  241. struct route_node *node;
  242. node = route_top (lsdb->table);
  243. if (node == NULL)
  244. return NULL;
  245. /* skip to the existing lsdb entry */
  246. while (node && node->info == NULL)
  247. node = route_next (node);
  248. if (node == NULL)
  249. return NULL;
  250. if (node->info)
  251. ospf6_lsa_lock ((struct ospf6_lsa *) node->info);
  252. return (struct ospf6_lsa *) node->info;
  253. }
  254. struct ospf6_lsa *
  255. ospf6_lsdb_next (struct ospf6_lsa *lsa)
  256. {
  257. struct route_node *node = lsa->rn;
  258. struct ospf6_lsa *next = NULL;
  259. do {
  260. node = route_next (node);
  261. } while (node && node->info == NULL);
  262. if ((node != NULL) && (node->info != NULL))
  263. {
  264. next = node->info;
  265. ospf6_lsa_lock (next);
  266. }
  267. ospf6_lsa_unlock (lsa);
  268. return next;
  269. }
  270. struct ospf6_lsa *
  271. ospf6_lsdb_type_router_head (u_int16_t type, u_int32_t adv_router,
  272. struct ospf6_lsdb *lsdb)
  273. {
  274. struct route_node *node;
  275. struct prefix_ipv6 key;
  276. struct ospf6_lsa *lsa;
  277. memset (&key, 0, sizeof (key));
  278. ospf6_lsdb_set_key (&key, &type, sizeof (type));
  279. ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
  280. node = lsdb->table->top;
  281. /* Walk down tree. */
  282. while (node && node->p.prefixlen <= key.prefixlen &&
  283. prefix_match (&node->p, (struct prefix *) &key))
  284. node = node->link[prefix6_bit(&key.prefix, node->p.prefixlen)];
  285. if (node)
  286. route_lock_node (node);
  287. while (node && node->info == NULL)
  288. node = route_next (node);
  289. if (node == NULL)
  290. return NULL;
  291. if (! prefix_match ((struct prefix *) &key, &node->p))
  292. return NULL;
  293. lsa = node->info;
  294. ospf6_lsa_lock (lsa);
  295. return lsa;
  296. }
  297. struct ospf6_lsa *
  298. ospf6_lsdb_type_router_next (u_int16_t type, u_int32_t adv_router,
  299. struct ospf6_lsa *lsa)
  300. {
  301. struct ospf6_lsa *next = ospf6_lsdb_next(lsa);
  302. if (next)
  303. {
  304. if (next->header->type != type ||
  305. next->header->adv_router != adv_router)
  306. {
  307. route_unlock_node (next->rn);
  308. ospf6_lsa_unlock (next);
  309. next = NULL;
  310. }
  311. }
  312. return next;
  313. }
  314. struct ospf6_lsa *
  315. ospf6_lsdb_type_head (u_int16_t type, struct ospf6_lsdb *lsdb)
  316. {
  317. struct route_node *node;
  318. struct prefix_ipv6 key;
  319. struct ospf6_lsa *lsa;
  320. memset (&key, 0, sizeof (key));
  321. ospf6_lsdb_set_key (&key, &type, sizeof (type));
  322. /* Walk down tree. */
  323. node = lsdb->table->top;
  324. while (node && node->p.prefixlen <= key.prefixlen &&
  325. prefix_match (&node->p, (struct prefix *) &key))
  326. node = node->link[prefix6_bit(&key.prefix, node->p.prefixlen)];
  327. if (node)
  328. route_lock_node (node);
  329. while (node && node->info == NULL)
  330. node = route_next (node);
  331. if (node == NULL)
  332. return NULL;
  333. if (! prefix_match ((struct prefix *) &key, &node->p))
  334. return NULL;
  335. lsa = node->info;
  336. ospf6_lsa_lock (lsa);
  337. return lsa;
  338. }
  339. struct ospf6_lsa *
  340. ospf6_lsdb_type_next (u_int16_t type, struct ospf6_lsa *lsa)
  341. {
  342. struct ospf6_lsa *next = ospf6_lsdb_next (lsa);
  343. if (next)
  344. {
  345. if (next->header->type != type)
  346. {
  347. route_unlock_node (next->rn);
  348. ospf6_lsa_unlock (next);
  349. next = NULL;
  350. }
  351. }
  352. return next;
  353. }
  354. void
  355. ospf6_lsdb_remove_all (struct ospf6_lsdb *lsdb)
  356. {
  357. struct ospf6_lsa *lsa;
  358. if (lsdb == NULL)
  359. return;
  360. for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa))
  361. ospf6_lsdb_remove (lsa, lsdb);
  362. }
  363. void
  364. ospf6_lsdb_lsa_unlock (struct ospf6_lsa *lsa)
  365. {
  366. if (lsa != NULL)
  367. {
  368. if (lsa->rn != NULL)
  369. route_unlock_node (lsa->rn);
  370. ospf6_lsa_unlock (lsa);
  371. }
  372. }
  373. int
  374. ospf6_lsdb_maxage_remover (struct ospf6_lsdb *lsdb)
  375. {
  376. int reschedule = 0;
  377. struct ospf6_lsa *lsa;
  378. for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa))
  379. {
  380. if (! OSPF6_LSA_IS_MAXAGE (lsa))
  381. continue;
  382. if (lsa->retrans_count != 0)
  383. {
  384. reschedule = 1;
  385. continue;
  386. }
  387. if (IS_OSPF6_DEBUG_LSA_TYPE (lsa->header->type))
  388. zlog_debug ("Remove MaxAge %s", lsa->name);
  389. if (CHECK_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED))
  390. {
  391. UNSET_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED);
  392. /*
  393. * lsa->header->age = 0;
  394. */
  395. lsa->header->seqnum = htonl(OSPF_MAX_SEQUENCE_NUMBER + 1);
  396. ospf6_lsa_checksum (lsa->header);
  397. THREAD_OFF(lsa->refresh);
  398. thread_execute (master, ospf6_lsa_refresh, lsa, 0);
  399. } else {
  400. ospf6_lsdb_remove (lsa, lsdb);
  401. }
  402. }
  403. return (reschedule);
  404. }
  405. void
  406. ospf6_lsdb_show (struct vty *vty, enum ospf_lsdb_show_level level,
  407. u_int16_t *type, u_int32_t *id, u_int32_t *adv_router,
  408. struct ospf6_lsdb *lsdb)
  409. {
  410. struct ospf6_lsa *lsa;
  411. void (*showfunc) (struct vty *, struct ospf6_lsa *) = NULL;
  412. switch (level)
  413. {
  414. case OSPF6_LSDB_SHOW_LEVEL_DETAIL:
  415. showfunc = ospf6_lsa_show;
  416. break;
  417. case OSPF6_LSDB_SHOW_LEVEL_INTERNAL:
  418. showfunc = ospf6_lsa_show_internal;
  419. break;
  420. case OSPF6_LSDB_SHOW_LEVEL_DUMP:
  421. showfunc = ospf6_lsa_show_dump;
  422. break;
  423. case OSPF6_LSDB_SHOW_LEVEL_NORMAL:
  424. default:
  425. showfunc = ospf6_lsa_show_summary;
  426. }
  427. if (type && id && adv_router)
  428. {
  429. lsa = ospf6_lsdb_lookup (*type, *id, *adv_router, lsdb);
  430. if (lsa)
  431. {
  432. if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
  433. ospf6_lsa_show (vty, lsa);
  434. else
  435. (*showfunc) (vty, lsa);
  436. }
  437. return;
  438. }
  439. if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
  440. ospf6_lsa_show_summary_header (vty);
  441. if (type && adv_router)
  442. lsa = ospf6_lsdb_type_router_head (*type, *adv_router, lsdb);
  443. else if (type)
  444. lsa = ospf6_lsdb_type_head (*type, lsdb);
  445. else
  446. lsa = ospf6_lsdb_head (lsdb);
  447. while (lsa)
  448. {
  449. if ((! adv_router || lsa->header->adv_router == *adv_router) &&
  450. (! id || lsa->header->id == *id))
  451. (*showfunc) (vty, lsa);
  452. if (type && adv_router)
  453. lsa = ospf6_lsdb_type_router_next (*type, *adv_router, lsa);
  454. else if (type)
  455. lsa = ospf6_lsdb_type_next (*type, lsa);
  456. else
  457. lsa = ospf6_lsdb_next (lsa);
  458. }
  459. }
  460. /* Decide new Link State ID to originate.
  461. note return value is network byte order */
  462. u_int32_t
  463. ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router,
  464. struct ospf6_lsdb *lsdb)
  465. {
  466. struct ospf6_lsa *lsa;
  467. u_int32_t id = 1;
  468. for (lsa = ospf6_lsdb_type_router_head (type, adv_router, lsdb); lsa;
  469. lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa))
  470. {
  471. if (ntohl (lsa->header->id) < id)
  472. continue;
  473. if (ntohl (lsa->header->id) > id)
  474. {
  475. ospf6_lsdb_lsa_unlock (lsa);
  476. break;
  477. }
  478. id++;
  479. }
  480. return ((u_int32_t) htonl (id));
  481. }
  482. /* Decide new LS sequence number to originate.
  483. note return value is network byte order */
  484. u_int32_t
  485. ospf6_new_ls_seqnum (u_int16_t type, u_int32_t id, u_int32_t adv_router,
  486. struct ospf6_lsdb *lsdb)
  487. {
  488. struct ospf6_lsa *lsa;
  489. signed long seqnum = 0;
  490. /* if current database copy not found, return InitialSequenceNumber */
  491. lsa = ospf6_lsdb_lookup (type, id, adv_router, lsdb);
  492. if (lsa == NULL)
  493. seqnum = OSPF_INITIAL_SEQUENCE_NUMBER;
  494. else
  495. seqnum = (signed long) ntohl (lsa->header->seqnum) + 1;
  496. return ((u_int32_t) htonl (seqnum));
  497. }