table.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810
  1. /*
  2. * Routing Table functions.
  3. * Copyright (C) 1998 Kunihiro Ishiguro
  4. *
  5. * This file is part of GNU Zebra.
  6. *
  7. * GNU Zebra is free software; you can redistribute it and/or modify it
  8. * under the terms of the GNU General Public License as published by the
  9. * Free Software Foundation; either version 2, or (at your option) any
  10. * later version.
  11. *
  12. * GNU Zebra is distributed in the hope that it will be useful, but
  13. * WITHOUT ANY WARRANTY; without even the implied warranty of
  14. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15. * General Public License for more details.
  16. *
  17. * You should have received a copy of the GNU General Public License
  18. * along with GNU Zebra; see the file COPYING. If not, write to the Free
  19. * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  20. * 02111-1307, USA.
  21. */
  22. #include <zebra.h>
  23. #include "prefix.h"
  24. #include "table.h"
  25. #include "memory.h"
  26. #include "sockunion.h"
  27. static void route_node_delete (struct route_node *);
  28. static void route_table_free (struct route_table *);
  29. /*
  30. * route_table_init_with_delegate
  31. */
  32. struct route_table *
  33. route_table_init_with_delegate (route_table_delegate_t *delegate)
  34. {
  35. struct route_table *rt;
  36. rt = XCALLOC (MTYPE_ROUTE_TABLE, sizeof (struct route_table));
  37. rt->delegate = delegate;
  38. return rt;
  39. }
  40. void
  41. route_table_finish (struct route_table *rt)
  42. {
  43. route_table_free (rt);
  44. }
  45. /* Allocate new route node. */
  46. static struct route_node *
  47. route_node_new (struct route_table *table)
  48. {
  49. return table->delegate->create_node (table->delegate, table);
  50. }
  51. /* Allocate new route node with prefix set. */
  52. static struct route_node *
  53. route_node_set (struct route_table *table, const struct prefix *prefix)
  54. {
  55. struct route_node *node;
  56. node = route_node_new (table);
  57. prefix_copy (&node->p, prefix);
  58. node->table = table;
  59. return node;
  60. }
  61. /* Free route node. */
  62. static void
  63. route_node_free (struct route_table *table, struct route_node *node)
  64. {
  65. table->delegate->destroy_node (table->delegate, table, node);
  66. }
  67. /* Free route table. */
  68. static void
  69. route_table_free (struct route_table *rt)
  70. {
  71. struct route_node *tmp_node;
  72. struct route_node *node;
  73. if (rt == NULL)
  74. return;
  75. node = rt->top;
  76. /* Bulk deletion of nodes remaining in this table. This function is not
  77. called until workers have completed their dependency on this table.
  78. A final route_unlock_node() will not be called for these nodes. */
  79. while (node)
  80. {
  81. if (node->l_left)
  82. {
  83. node = node->l_left;
  84. continue;
  85. }
  86. if (node->l_right)
  87. {
  88. node = node->l_right;
  89. continue;
  90. }
  91. tmp_node = node;
  92. node = node->parent;
  93. tmp_node->table->count--;
  94. tmp_node->lock = 0; /* to cause assert if unlocked after this */
  95. route_node_free (rt, tmp_node);
  96. if (node != NULL)
  97. {
  98. if (node->l_left == tmp_node)
  99. node->l_left = NULL;
  100. else
  101. node->l_right = NULL;
  102. }
  103. else
  104. {
  105. break;
  106. }
  107. }
  108. assert (rt->count == 0);
  109. XFREE (MTYPE_ROUTE_TABLE, rt);
  110. return;
  111. }
  112. /* Utility mask array. */
  113. static const u_char maskbit[] =
  114. {
  115. 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff
  116. };
  117. /* Common prefix route genaration. */
  118. static void
  119. route_common (const struct prefix *n, const struct prefix *p, struct prefix *new)
  120. {
  121. int i;
  122. u_char diff;
  123. u_char mask;
  124. const u_char *np = (const u_char *)&n->u.prefix;
  125. const u_char *pp = (const u_char *)&p->u.prefix;
  126. u_char *newp = (u_char *)&new->u.prefix;
  127. for (i = 0; i < p->prefixlen / 8; i++)
  128. {
  129. if (np[i] == pp[i])
  130. newp[i] = np[i];
  131. else
  132. break;
  133. }
  134. new->prefixlen = i * 8;
  135. if (new->prefixlen != p->prefixlen)
  136. {
  137. diff = np[i] ^ pp[i];
  138. mask = 0x80;
  139. while (new->prefixlen < p->prefixlen && !(mask & diff))
  140. {
  141. mask >>= 1;
  142. new->prefixlen++;
  143. }
  144. newp[i] = np[i] & maskbit[new->prefixlen % 8];
  145. }
  146. }
  147. static void
  148. set_link (struct route_node *node, struct route_node *new)
  149. {
  150. unsigned int bit = prefix_bit (&new->p.u.prefix, node->p.prefixlen);
  151. node->link[bit] = new;
  152. new->parent = node;
  153. }
  154. /* Lock node. */
  155. struct route_node *
  156. route_lock_node (struct route_node *node)
  157. {
  158. node->lock++;
  159. return node;
  160. }
  161. /* Unlock node. */
  162. void
  163. route_unlock_node (struct route_node *node)
  164. {
  165. assert (node->lock > 0);
  166. node->lock--;
  167. if (node->lock == 0)
  168. route_node_delete (node);
  169. }
  170. /* Find matched prefix. */
  171. struct route_node *
  172. route_node_match (const struct route_table *table, const struct prefix *p)
  173. {
  174. struct route_node *node;
  175. struct route_node *matched;
  176. matched = NULL;
  177. node = table->top;
  178. /* Walk down tree. If there is matched route then store it to
  179. matched. */
  180. while (node && node->p.prefixlen <= p->prefixlen &&
  181. prefix_match (&node->p, p))
  182. {
  183. if (node->info)
  184. matched = node;
  185. if (node->p.prefixlen == p->prefixlen)
  186. break;
  187. node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
  188. }
  189. /* If matched route found, return it. */
  190. if (matched)
  191. return route_lock_node (matched);
  192. return NULL;
  193. }
  194. struct route_node *
  195. route_node_match_ipv4 (const struct route_table *table,
  196. const struct in_addr *addr)
  197. {
  198. struct prefix_ipv4 p;
  199. memset (&p, 0, sizeof (struct prefix_ipv4));
  200. p.family = AF_INET;
  201. p.prefixlen = IPV4_MAX_PREFIXLEN;
  202. p.prefix = *addr;
  203. return route_node_match (table, (struct prefix *) &p);
  204. }
  205. #ifdef HAVE_IPV6
  206. struct route_node *
  207. route_node_match_ipv6 (const struct route_table *table,
  208. const struct in6_addr *addr)
  209. {
  210. struct prefix_ipv6 p;
  211. memset (&p, 0, sizeof (struct prefix_ipv6));
  212. p.family = AF_INET6;
  213. p.prefixlen = IPV6_MAX_PREFIXLEN;
  214. p.prefix = *addr;
  215. return route_node_match (table, (struct prefix *) &p);
  216. }
  217. #endif /* HAVE_IPV6 */
  218. /* Lookup same prefix node. Return NULL when we can't find route. */
  219. struct route_node *
  220. route_node_lookup (const struct route_table *table, const struct prefix *p)
  221. {
  222. struct route_node *node;
  223. u_char prefixlen = p->prefixlen;
  224. const u_char *prefix = &p->u.prefix;
  225. node = table->top;
  226. while (node && node->p.prefixlen <= prefixlen &&
  227. prefix_match (&node->p, p))
  228. {
  229. if (node->p.prefixlen == prefixlen)
  230. return node->info ? route_lock_node (node) : NULL;
  231. node = node->link[prefix_bit(prefix, node->p.prefixlen)];
  232. }
  233. return NULL;
  234. }
  235. /* Add node to routing table. */
  236. struct route_node *
  237. route_node_get (struct route_table *const table, const struct prefix *p)
  238. {
  239. struct route_node *new;
  240. struct route_node *node;
  241. struct route_node *match;
  242. u_char prefixlen = p->prefixlen;
  243. const u_char *prefix = &p->u.prefix;
  244. match = NULL;
  245. node = table->top;
  246. while (node && node->p.prefixlen <= prefixlen &&
  247. prefix_match (&node->p, p))
  248. {
  249. if (node->p.prefixlen == prefixlen)
  250. return route_lock_node (node);
  251. match = node;
  252. node = node->link[prefix_bit(prefix, node->p.prefixlen)];
  253. }
  254. if (node == NULL)
  255. {
  256. new = route_node_set (table, p);
  257. if (match)
  258. set_link (match, new);
  259. else
  260. table->top = new;
  261. }
  262. else
  263. {
  264. new = route_node_new (table);
  265. route_common (&node->p, p, &new->p);
  266. new->p.family = p->family;
  267. new->table = table;
  268. set_link (new, node);
  269. if (match)
  270. set_link (match, new);
  271. else
  272. table->top = new;
  273. if (new->p.prefixlen != p->prefixlen)
  274. {
  275. match = new;
  276. new = route_node_set (table, p);
  277. set_link (match, new);
  278. table->count++;
  279. }
  280. }
  281. table->count++;
  282. route_lock_node (new);
  283. return new;
  284. }
  285. /* Delete node from the routing table. */
  286. static void
  287. route_node_delete (struct route_node *node)
  288. {
  289. struct route_node *child;
  290. struct route_node *parent;
  291. assert (node->lock == 0);
  292. assert (node->info == NULL);
  293. if (node->l_left && node->l_right)
  294. return;
  295. if (node->l_left)
  296. child = node->l_left;
  297. else
  298. child = node->l_right;
  299. parent = node->parent;
  300. if (child)
  301. child->parent = parent;
  302. if (parent)
  303. {
  304. if (parent->l_left == node)
  305. parent->l_left = child;
  306. else
  307. parent->l_right = child;
  308. }
  309. else
  310. node->table->top = child;
  311. node->table->count--;
  312. route_node_free (node->table, node);
  313. /* If parent node is stub then delete it also. */
  314. if (parent && parent->lock == 0)
  315. route_node_delete (parent);
  316. }
  317. /* Get fist node and lock it. This function is useful when one want
  318. to lookup all the node exist in the routing table. */
  319. struct route_node *
  320. route_top (struct route_table *table)
  321. {
  322. /* If there is no node in the routing table return NULL. */
  323. if (table->top == NULL)
  324. return NULL;
  325. /* Lock the top node and return it. */
  326. route_lock_node (table->top);
  327. return table->top;
  328. }
  329. /* Unlock current node and lock next node then return it. */
  330. struct route_node *
  331. route_next (struct route_node *node)
  332. {
  333. struct route_node *next;
  334. struct route_node *start;
  335. /* Node may be deleted from route_unlock_node so we have to preserve
  336. next node's pointer. */
  337. if (node->l_left)
  338. {
  339. next = node->l_left;
  340. route_lock_node (next);
  341. route_unlock_node (node);
  342. return next;
  343. }
  344. if (node->l_right)
  345. {
  346. next = node->l_right;
  347. route_lock_node (next);
  348. route_unlock_node (node);
  349. return next;
  350. }
  351. start = node;
  352. while (node->parent)
  353. {
  354. if (node->parent->l_left == node && node->parent->l_right)
  355. {
  356. next = node->parent->l_right;
  357. route_lock_node (next);
  358. route_unlock_node (start);
  359. return next;
  360. }
  361. node = node->parent;
  362. }
  363. route_unlock_node (start);
  364. return NULL;
  365. }
  366. /* Unlock current node and lock next node until limit. */
  367. struct route_node *
  368. route_next_until (struct route_node *node, struct route_node *limit)
  369. {
  370. struct route_node *next;
  371. struct route_node *start;
  372. /* Node may be deleted from route_unlock_node so we have to preserve
  373. next node's pointer. */
  374. if (node->l_left)
  375. {
  376. next = node->l_left;
  377. route_lock_node (next);
  378. route_unlock_node (node);
  379. return next;
  380. }
  381. if (node->l_right)
  382. {
  383. next = node->l_right;
  384. route_lock_node (next);
  385. route_unlock_node (node);
  386. return next;
  387. }
  388. start = node;
  389. while (node->parent && node != limit)
  390. {
  391. if (node->parent->l_left == node && node->parent->l_right)
  392. {
  393. next = node->parent->l_right;
  394. route_lock_node (next);
  395. route_unlock_node (start);
  396. return next;
  397. }
  398. node = node->parent;
  399. }
  400. route_unlock_node (start);
  401. return NULL;
  402. }
  403. unsigned long
  404. route_table_count (const struct route_table *table)
  405. {
  406. return table->count;
  407. }
  408. /**
  409. * route_node_create
  410. *
  411. * Default function for creating a route node.
  412. */
  413. static struct route_node *
  414. route_node_create (route_table_delegate_t *delegate,
  415. struct route_table *table)
  416. {
  417. struct route_node *node;
  418. node = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct route_node));
  419. return node;
  420. }
  421. /**
  422. * route_node_destroy
  423. *
  424. * Default function for destroying a route node.
  425. */
  426. static void
  427. route_node_destroy (route_table_delegate_t *delegate,
  428. struct route_table *table, struct route_node *node)
  429. {
  430. XFREE (MTYPE_ROUTE_NODE, node);
  431. }
  432. /*
  433. * Default delegate.
  434. */
  435. static route_table_delegate_t default_delegate = {
  436. .create_node = route_node_create,
  437. .destroy_node = route_node_destroy
  438. };
  439. /*
  440. * route_table_init
  441. */
  442. struct route_table *
  443. route_table_init (void)
  444. {
  445. return route_table_init_with_delegate (&default_delegate);
  446. }
  447. /**
  448. * route_table_prefix_iter_cmp
  449. *
  450. * Compare two prefixes according to the order in which they appear in
  451. * an iteration over a tree.
  452. *
  453. * @return -1 if p1 occurs before p2 (p1 < p2)
  454. * 0 if the prefixes are identical (p1 == p2)
  455. * +1 if p1 occurs after p2 (p1 > p2)
  456. */
  457. int
  458. route_table_prefix_iter_cmp (struct prefix *p1, struct prefix *p2)
  459. {
  460. struct prefix common_space;
  461. struct prefix *common = &common_space;
  462. if (p1->prefixlen <= p2->prefixlen)
  463. {
  464. if (prefix_match (p1, p2))
  465. {
  466. /*
  467. * p1 contains p2, or is equal to it.
  468. */
  469. return (p1->prefixlen == p2->prefixlen) ? 0 : -1;
  470. }
  471. }
  472. else
  473. {
  474. /*
  475. * Check if p2 contains p1.
  476. */
  477. if (prefix_match (p2, p1))
  478. return 1;
  479. }
  480. route_common (p1, p2, common);
  481. assert (common->prefixlen < p1->prefixlen);
  482. assert (common->prefixlen < p2->prefixlen);
  483. /*
  484. * Both prefixes are longer than the common prefix.
  485. *
  486. * We need to check the bit after the common prefixlen to determine
  487. * which one comes later.
  488. */
  489. if (prefix_bit (&p1->u.prefix, common->prefixlen))
  490. {
  491. /*
  492. * We branch to the right to get to p1 from the common prefix.
  493. */
  494. assert (!prefix_bit (&p2->u.prefix, common->prefixlen));
  495. return 1;
  496. }
  497. /*
  498. * We branch to the right to get to p2 from the common prefix.
  499. */
  500. assert (prefix_bit (&p2->u.prefix, common->prefixlen));
  501. return -1;
  502. }
  503. /*
  504. * route_get_subtree_next
  505. *
  506. * Helper function that returns the first node that follows the nodes
  507. * in the sub-tree under 'node' in iteration order.
  508. */
  509. static struct route_node *
  510. route_get_subtree_next (struct route_node *node)
  511. {
  512. while (node->parent)
  513. {
  514. if (node->parent->l_left == node && node->parent->l_right)
  515. return node->parent->l_right;
  516. node = node->parent;
  517. }
  518. return NULL;
  519. }
  520. /**
  521. * route_table_get_next_internal
  522. *
  523. * Helper function to find the node that occurs after the given prefix in
  524. * order of iteration.
  525. *
  526. * @see route_table_get_next
  527. */
  528. static struct route_node *
  529. route_table_get_next_internal (const struct route_table *table,
  530. struct prefix *p)
  531. {
  532. struct route_node *node, *tmp_node;
  533. int cmp;
  534. node = table->top;
  535. while (node)
  536. {
  537. int match;
  538. if (node->p.prefixlen < p->prefixlen)
  539. match = prefix_match (&node->p, p);
  540. else
  541. match = prefix_match (p, &node->p);
  542. if (match)
  543. {
  544. if (node->p.prefixlen == p->prefixlen)
  545. {
  546. /*
  547. * The prefix p exists in the tree, just return the next
  548. * node.
  549. */
  550. route_lock_node (node);
  551. node = route_next (node);
  552. if (node)
  553. route_unlock_node (node);
  554. return (node);
  555. }
  556. if (node->p.prefixlen > p->prefixlen)
  557. {
  558. /*
  559. * Node is in the subtree of p, and hence greater than p.
  560. */
  561. return node;
  562. }
  563. /*
  564. * p is in the sub-tree under node.
  565. */
  566. tmp_node = node->link[prefix_bit (&p->u.prefix, node->p.prefixlen)];
  567. if (tmp_node)
  568. {
  569. node = tmp_node;
  570. continue;
  571. }
  572. /*
  573. * There are no nodes in the direction where p should be. If
  574. * node has a right child, then it must be greater than p.
  575. */
  576. if (node->l_right)
  577. return node->l_right;
  578. /*
  579. * No more children to follow, go upwards looking for the next
  580. * node.
  581. */
  582. return route_get_subtree_next (node);
  583. }
  584. /*
  585. * Neither node prefix nor 'p' contains the other.
  586. */
  587. cmp = route_table_prefix_iter_cmp (&node->p, p);
  588. if (cmp > 0)
  589. {
  590. /*
  591. * Node follows p in iteration order. Return it.
  592. */
  593. return node;
  594. }
  595. assert (cmp < 0);
  596. /*
  597. * Node and the subtree under it come before prefix p in
  598. * iteration order. Prefix p and its sub-tree are not present in
  599. * the tree. Go upwards and find the first node that follows the
  600. * subtree. That node will also succeed p.
  601. */
  602. return route_get_subtree_next (node);
  603. }
  604. return NULL;
  605. }
  606. /**
  607. * route_table_get_next
  608. *
  609. * Find the node that occurs after the given prefix in order of
  610. * iteration.
  611. */
  612. struct route_node *
  613. route_table_get_next (const struct route_table *table, struct prefix *p)
  614. {
  615. struct route_node *node;
  616. node = route_table_get_next_internal (table, p);
  617. if (node)
  618. {
  619. assert (route_table_prefix_iter_cmp (&node->p, p) > 0);
  620. route_lock_node (node);
  621. }
  622. return node;
  623. }
  624. /*
  625. * route_table_iter_init
  626. */
  627. void
  628. route_table_iter_init (route_table_iter_t * iter, struct route_table *table)
  629. {
  630. memset (iter, 0, sizeof (*iter));
  631. iter->state = RT_ITER_STATE_INIT;
  632. iter->table = table;
  633. }
  634. /*
  635. * route_table_iter_pause
  636. *
  637. * Pause an iteration over the table. This allows the iteration to be
  638. * resumed point after arbitrary additions/deletions from the table.
  639. * An iteration can be resumed by just calling route_table_iter_next()
  640. * on the iterator.
  641. */
  642. void
  643. route_table_iter_pause (route_table_iter_t * iter)
  644. {
  645. switch (iter->state)
  646. {
  647. case RT_ITER_STATE_INIT:
  648. case RT_ITER_STATE_PAUSED:
  649. case RT_ITER_STATE_DONE:
  650. return;
  651. case RT_ITER_STATE_ITERATING:
  652. /*
  653. * Save the prefix that we are currently at. The next call to
  654. * route_table_iter_next() will return the node after this prefix
  655. * in the tree.
  656. */
  657. prefix_copy (&iter->pause_prefix, &iter->current->p);
  658. route_unlock_node (iter->current);
  659. iter->current = NULL;
  660. iter->state = RT_ITER_STATE_PAUSED;
  661. return;
  662. default:
  663. assert (0);
  664. }
  665. }
  666. /*
  667. * route_table_iter_cleanup
  668. *
  669. * Release any resources held by the iterator.
  670. */
  671. void
  672. route_table_iter_cleanup (route_table_iter_t * iter)
  673. {
  674. if (iter->state == RT_ITER_STATE_ITERATING)
  675. {
  676. route_unlock_node (iter->current);
  677. iter->current = NULL;
  678. }
  679. assert (!iter->current);
  680. /*
  681. * Set the state to RT_ITER_STATE_DONE to make any
  682. * route_table_iter_next() calls on this iterator return NULL.
  683. */
  684. iter->state = RT_ITER_STATE_DONE;
  685. }