ospf6_lsdb.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582
  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_info ("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_info ("%p %p %s lsdb[%p]", debug->prev, debug->next, debug->name,
  79. debug->lsdb);
  80. zlog_info ("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. /* Macro version of check_bit (). */
  227. #define CHECK_BIT(X,P) ((((u_char *)(X))[(P) / 8]) >> (7 - ((P) % 8)) & 1)
  228. struct ospf6_lsa *
  229. ospf6_lsdb_lookup_next (u_int16_t type, u_int32_t id, u_int32_t adv_router,
  230. struct ospf6_lsdb *lsdb)
  231. {
  232. struct route_node *node;
  233. struct route_node *matched = NULL;
  234. struct prefix_ipv6 key;
  235. struct prefix *p;
  236. if (lsdb == NULL)
  237. return NULL;
  238. memset (&key, 0, sizeof (key));
  239. ospf6_lsdb_set_key (&key, &type, sizeof (type));
  240. ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
  241. ospf6_lsdb_set_key (&key, &id, sizeof (id));
  242. p = (struct prefix *) &key;
  243. {
  244. char buf[64];
  245. prefix2str (p, buf, sizeof (buf));
  246. zlog_info ("lsdb_lookup_next: key: %s", buf);
  247. }
  248. node = lsdb->table->top;
  249. /* walk down tree. */
  250. while (node && node->p.prefixlen <= p->prefixlen &&
  251. prefix_match (&node->p, p))
  252. {
  253. matched = node;
  254. node = node->link[CHECK_BIT(&p->u.prefix, node->p.prefixlen)];
  255. }
  256. if (matched)
  257. node = matched;
  258. else
  259. node = lsdb->table->top;
  260. route_lock_node (node);
  261. /* skip to real existing entry */
  262. while (node && node->info == NULL)
  263. node = route_next (node);
  264. if (! node)
  265. return NULL;
  266. if (prefix_same (&node->p, p))
  267. {
  268. struct route_node *prev = node;
  269. struct ospf6_lsa *lsa_prev;
  270. struct ospf6_lsa *lsa_next;
  271. node = route_next (node);
  272. while (node && node->info == NULL)
  273. node = route_next (node);
  274. lsa_prev = prev->info;
  275. lsa_next = (node ? node->info : NULL);
  276. assert (lsa_prev);
  277. assert (lsa_prev->next == lsa_next);
  278. if (lsa_next)
  279. assert (lsa_next->prev == lsa_prev);
  280. zlog_info ("lsdb_lookup_next: assert OK with previous LSA");
  281. }
  282. if (! node)
  283. return NULL;
  284. route_unlock_node (node);
  285. return (struct ospf6_lsa *) node->info;
  286. }
  287. /* Iteration function */
  288. struct ospf6_lsa *
  289. ospf6_lsdb_head (struct ospf6_lsdb *lsdb)
  290. {
  291. struct route_node *node;
  292. node = route_top (lsdb->table);
  293. if (node == NULL)
  294. return NULL;
  295. /* skip to the existing lsdb entry */
  296. while (node && node->info == NULL)
  297. node = route_next (node);
  298. if (node == NULL)
  299. return NULL;
  300. route_unlock_node (node);
  301. if (node->info)
  302. ospf6_lsa_lock ((struct ospf6_lsa *) node->info);
  303. return (struct ospf6_lsa *) node->info;
  304. }
  305. struct ospf6_lsa *
  306. ospf6_lsdb_next (struct ospf6_lsa *lsa)
  307. {
  308. struct ospf6_lsa *next = lsa->next;
  309. ospf6_lsa_unlock (lsa);
  310. if (next)
  311. ospf6_lsa_lock (next);
  312. return next;
  313. }
  314. struct ospf6_lsa *
  315. ospf6_lsdb_type_router_head (u_int16_t type, u_int32_t adv_router,
  316. struct ospf6_lsdb *lsdb)
  317. {
  318. struct route_node *node;
  319. struct prefix_ipv6 key;
  320. struct ospf6_lsa *lsa;
  321. memset (&key, 0, sizeof (key));
  322. ospf6_lsdb_set_key (&key, &type, sizeof (type));
  323. ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
  324. node = lsdb->table->top;
  325. /* Walk down tree. */
  326. while (node && node->p.prefixlen <= key.prefixlen &&
  327. prefix_match (&node->p, (struct prefix *) &key))
  328. node = node->link[CHECK_BIT(&key.prefix, node->p.prefixlen)];
  329. if (node)
  330. route_lock_node (node);
  331. while (node && node->info == NULL)
  332. node = route_next (node);
  333. if (node == NULL)
  334. return NULL;
  335. else
  336. route_unlock_node (node);
  337. if (! prefix_match ((struct prefix *) &key, &node->p))
  338. return NULL;
  339. lsa = node->info;
  340. ospf6_lsa_lock (lsa);
  341. return lsa;
  342. }
  343. struct ospf6_lsa *
  344. ospf6_lsdb_type_router_next (u_int16_t type, u_int32_t adv_router,
  345. struct ospf6_lsa *lsa)
  346. {
  347. struct ospf6_lsa *next = lsa->next;
  348. if (next)
  349. {
  350. if (next->header->type != type ||
  351. next->header->adv_router != adv_router)
  352. next = NULL;
  353. }
  354. if (next)
  355. ospf6_lsa_lock (next);
  356. ospf6_lsa_unlock (lsa);
  357. return next;
  358. }
  359. struct ospf6_lsa *
  360. ospf6_lsdb_type_head (u_int16_t type, struct ospf6_lsdb *lsdb)
  361. {
  362. struct route_node *node;
  363. struct prefix_ipv6 key;
  364. struct ospf6_lsa *lsa;
  365. memset (&key, 0, sizeof (key));
  366. ospf6_lsdb_set_key (&key, &type, sizeof (type));
  367. /* Walk down tree. */
  368. node = lsdb->table->top;
  369. while (node && node->p.prefixlen <= key.prefixlen &&
  370. prefix_match (&node->p, (struct prefix *) &key))
  371. node = node->link[CHECK_BIT(&key.prefix, node->p.prefixlen)];
  372. if (node)
  373. route_lock_node (node);
  374. while (node && node->info == NULL)
  375. node = route_next (node);
  376. if (node == NULL)
  377. return NULL;
  378. else
  379. route_unlock_node (node);
  380. if (! prefix_match ((struct prefix *) &key, &node->p))
  381. return NULL;
  382. lsa = node->info;
  383. ospf6_lsa_lock (lsa);
  384. return lsa;
  385. }
  386. struct ospf6_lsa *
  387. ospf6_lsdb_type_next (u_int16_t type, struct ospf6_lsa *lsa)
  388. {
  389. struct ospf6_lsa *next = lsa->next;
  390. if (next)
  391. {
  392. if (next->header->type != type)
  393. next = NULL;
  394. }
  395. if (next)
  396. ospf6_lsa_lock (next);
  397. ospf6_lsa_unlock (lsa);
  398. return next;
  399. }
  400. void
  401. ospf6_lsdb_remove_all (struct ospf6_lsdb *lsdb)
  402. {
  403. struct ospf6_lsa *lsa;
  404. for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa))
  405. ospf6_lsdb_remove (lsa, lsdb);
  406. }
  407. void
  408. ospf6_lsdb_show (struct vty *vty, int level,
  409. u_int16_t *type, u_int32_t *id, u_int32_t *adv_router,
  410. struct ospf6_lsdb *lsdb)
  411. {
  412. struct ospf6_lsa *lsa;
  413. void (*showfunc) (struct vty *, struct ospf6_lsa *) = NULL;
  414. if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
  415. showfunc = ospf6_lsa_show_summary;
  416. else if (level == OSPF6_LSDB_SHOW_LEVEL_DETAIL)
  417. showfunc = ospf6_lsa_show;
  418. else if (level == OSPF6_LSDB_SHOW_LEVEL_INTERNAL)
  419. showfunc = ospf6_lsa_show_internal;
  420. else if (level == OSPF6_LSDB_SHOW_LEVEL_DUMP)
  421. showfunc = ospf6_lsa_show_dump;
  422. if (type && id && adv_router)
  423. {
  424. lsa = ospf6_lsdb_lookup (*type, *id, *adv_router, lsdb);
  425. if (lsa)
  426. {
  427. if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
  428. ospf6_lsa_show (vty, lsa);
  429. else
  430. (*showfunc) (vty, lsa);
  431. }
  432. return;
  433. }
  434. if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
  435. ospf6_lsa_show_summary_header (vty);
  436. if (type && adv_router)
  437. lsa = ospf6_lsdb_type_router_head (*type, *adv_router, lsdb);
  438. else if (type)
  439. lsa = ospf6_lsdb_type_head (*type, lsdb);
  440. else
  441. lsa = ospf6_lsdb_head (lsdb);
  442. while (lsa)
  443. {
  444. if ((! adv_router || lsa->header->adv_router == *adv_router) &&
  445. (! id || lsa->header->id == *id))
  446. (*showfunc) (vty, lsa);
  447. if (type && adv_router)
  448. lsa = ospf6_lsdb_type_router_next (*type, *adv_router, lsa);
  449. else if (type)
  450. lsa = ospf6_lsdb_type_next (*type, lsa);
  451. else
  452. lsa = ospf6_lsdb_next (lsa);
  453. }
  454. }
  455. /* Decide new Link State ID to originate.
  456. note return value is network byte order */
  457. u_int32_t
  458. ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router,
  459. struct ospf6_lsdb *lsdb)
  460. {
  461. struct ospf6_lsa *lsa;
  462. u_int32_t id = 1;
  463. for (lsa = ospf6_lsdb_type_router_head (type, adv_router, lsdb); lsa;
  464. lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa))
  465. {
  466. if (ntohl (lsa->header->id) < id)
  467. continue;
  468. if (ntohl (lsa->header->id) > id)
  469. break;
  470. id++;
  471. }
  472. return ((u_int32_t) htonl (id));
  473. }
  474. /* Decide new LS sequence number to originate.
  475. note return value is network byte order */
  476. u_int32_t
  477. ospf6_new_ls_seqnum (u_int16_t type, u_int32_t id, u_int32_t adv_router,
  478. struct ospf6_lsdb *lsdb)
  479. {
  480. struct ospf6_lsa *lsa;
  481. signed long seqnum = 0;
  482. /* if current database copy not found, return InitialSequenceNumber */
  483. lsa = ospf6_lsdb_lookup (type, id, adv_router, lsdb);
  484. if (lsa == NULL)
  485. seqnum = INITIAL_SEQUENCE_NUMBER;
  486. else
  487. seqnum = (signed long) ntohl (lsa->header->seqnum) + 1;
  488. return ((u_int32_t) htonl (seqnum));
  489. }