ospf6_lsdb.c 12 KB

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