ospf6_lsdb.c 14 KB

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