ospf6_lsdb.c 12 KB

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