table.c 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463
  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. void route_node_delete (struct route_node *);
  28. void route_table_free (struct route_table *);
  29. struct route_table *
  30. route_table_init (void)
  31. {
  32. struct route_table *rt;
  33. rt = XCALLOC (MTYPE_ROUTE_TABLE, sizeof (struct route_table));
  34. return rt;
  35. }
  36. void
  37. route_table_finish (struct route_table *rt)
  38. {
  39. route_table_free (rt);
  40. }
  41. /* Allocate new route node. */
  42. static struct route_node *
  43. route_node_new (void)
  44. {
  45. struct route_node *node;
  46. node = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct route_node));
  47. return node;
  48. }
  49. /* Allocate new route node with prefix set. */
  50. static struct route_node *
  51. route_node_set (struct route_table *table, struct prefix *prefix)
  52. {
  53. struct route_node *node;
  54. node = route_node_new ();
  55. prefix_copy (&node->p, prefix);
  56. node->table = table;
  57. return node;
  58. }
  59. /* Free route node. */
  60. static void
  61. route_node_free (struct route_node *node)
  62. {
  63. XFREE (MTYPE_ROUTE_NODE, node);
  64. }
  65. /* Free route table. */
  66. void
  67. route_table_free (struct route_table *rt)
  68. {
  69. struct route_node *tmp_node;
  70. struct route_node *node;
  71. if (rt == NULL)
  72. return;
  73. node = rt->top;
  74. while (node)
  75. {
  76. if (node->l_left)
  77. {
  78. node = node->l_left;
  79. continue;
  80. }
  81. if (node->l_right)
  82. {
  83. node = node->l_right;
  84. continue;
  85. }
  86. tmp_node = node;
  87. node = node->parent;
  88. if (node != NULL)
  89. {
  90. if (node->l_left == tmp_node)
  91. node->l_left = NULL;
  92. else
  93. node->l_right = NULL;
  94. route_node_free (tmp_node);
  95. }
  96. else
  97. {
  98. route_node_free (tmp_node);
  99. break;
  100. }
  101. }
  102. XFREE (MTYPE_ROUTE_TABLE, rt);
  103. return;
  104. }
  105. /* Utility mask array. */
  106. static const u_char maskbit[] =
  107. {
  108. 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff
  109. };
  110. /* Common prefix route genaration. */
  111. static void
  112. route_common (struct prefix *n, struct prefix *p, struct prefix *new)
  113. {
  114. int i;
  115. u_char diff;
  116. u_char mask;
  117. u_char *np = (u_char *)&n->u.prefix;
  118. u_char *pp = (u_char *)&p->u.prefix;
  119. u_char *newp = (u_char *)&new->u.prefix;
  120. for (i = 0; i < p->prefixlen / 8; i++)
  121. {
  122. if (np[i] == pp[i])
  123. newp[i] = np[i];
  124. else
  125. break;
  126. }
  127. new->prefixlen = i * 8;
  128. if (new->prefixlen != p->prefixlen)
  129. {
  130. diff = np[i] ^ pp[i];
  131. mask = 0x80;
  132. while (new->prefixlen < p->prefixlen && !(mask & diff))
  133. {
  134. mask >>= 1;
  135. new->prefixlen++;
  136. }
  137. newp[i] = np[i] & maskbit[new->prefixlen % 8];
  138. }
  139. }
  140. static void
  141. set_link (struct route_node *node, struct route_node *new)
  142. {
  143. unsigned int bit = prefix_bit (&new->p.u.prefix, node->p.prefixlen);
  144. node->link[bit] = new;
  145. new->parent = node;
  146. }
  147. /* Lock node. */
  148. struct route_node *
  149. route_lock_node (struct route_node *node)
  150. {
  151. node->lock++;
  152. return node;
  153. }
  154. /* Unlock node. */
  155. void
  156. route_unlock_node (struct route_node *node)
  157. {
  158. node->lock--;
  159. if (node->lock == 0)
  160. route_node_delete (node);
  161. }
  162. /* Find matched prefix. */
  163. struct route_node *
  164. route_node_match (const struct route_table *table, const struct prefix *p)
  165. {
  166. struct route_node *node;
  167. struct route_node *matched;
  168. matched = NULL;
  169. node = table->top;
  170. /* Walk down tree. If there is matched route then store it to
  171. matched. */
  172. while (node && node->p.prefixlen <= p->prefixlen &&
  173. prefix_match (&node->p, p))
  174. {
  175. if (node->info)
  176. matched = node;
  177. if (node->p.prefixlen == p->prefixlen)
  178. break;
  179. node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
  180. }
  181. /* If matched route found, return it. */
  182. if (matched)
  183. return route_lock_node (matched);
  184. return NULL;
  185. }
  186. struct route_node *
  187. route_node_match_ipv4 (const struct route_table *table,
  188. const struct in_addr *addr)
  189. {
  190. struct prefix_ipv4 p;
  191. memset (&p, 0, sizeof (struct prefix_ipv4));
  192. p.family = AF_INET;
  193. p.prefixlen = IPV4_MAX_PREFIXLEN;
  194. p.prefix = *addr;
  195. return route_node_match (table, (struct prefix *) &p);
  196. }
  197. #ifdef HAVE_IPV6
  198. struct route_node *
  199. route_node_match_ipv6 (const struct route_table *table,
  200. const struct in6_addr *addr)
  201. {
  202. struct prefix_ipv6 p;
  203. memset (&p, 0, sizeof (struct prefix_ipv6));
  204. p.family = AF_INET6;
  205. p.prefixlen = IPV6_MAX_PREFIXLEN;
  206. p.prefix = *addr;
  207. return route_node_match (table, (struct prefix *) &p);
  208. }
  209. #endif /* HAVE_IPV6 */
  210. /* Lookup same prefix node. Return NULL when we can't find route. */
  211. struct route_node *
  212. route_node_lookup (struct route_table *table, struct prefix *p)
  213. {
  214. struct route_node *node;
  215. node = table->top;
  216. while (node && node->p.prefixlen <= p->prefixlen &&
  217. prefix_match (&node->p, p))
  218. {
  219. if (node->p.prefixlen == p->prefixlen)
  220. return node->info ? route_lock_node (node) : NULL;
  221. node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
  222. }
  223. return NULL;
  224. }
  225. /* Add node to routing table. */
  226. struct route_node *
  227. route_node_get (struct route_table *table, struct prefix *p)
  228. {
  229. struct route_node *new;
  230. struct route_node *node;
  231. struct route_node *match;
  232. match = NULL;
  233. node = table->top;
  234. while (node && node->p.prefixlen <= p->prefixlen &&
  235. prefix_match (&node->p, p))
  236. {
  237. if (node->p.prefixlen == p->prefixlen)
  238. return route_lock_node (node);
  239. match = node;
  240. node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
  241. }
  242. if (node == NULL)
  243. {
  244. new = route_node_set (table, p);
  245. if (match)
  246. set_link (match, new);
  247. else
  248. table->top = new;
  249. }
  250. else
  251. {
  252. new = route_node_new ();
  253. route_common (&node->p, p, &new->p);
  254. new->p.family = p->family;
  255. new->table = table;
  256. set_link (new, node);
  257. if (match)
  258. set_link (match, new);
  259. else
  260. table->top = new;
  261. if (new->p.prefixlen != p->prefixlen)
  262. {
  263. match = new;
  264. new = route_node_set (table, p);
  265. set_link (match, new);
  266. }
  267. }
  268. route_lock_node (new);
  269. return new;
  270. }
  271. /* Delete node from the routing table. */
  272. void
  273. route_node_delete (struct route_node *node)
  274. {
  275. struct route_node *child;
  276. struct route_node *parent;
  277. assert (node->lock == 0);
  278. assert (node->info == NULL);
  279. if (node->l_left && node->l_right)
  280. return;
  281. if (node->l_left)
  282. child = node->l_left;
  283. else
  284. child = node->l_right;
  285. parent = node->parent;
  286. if (child)
  287. child->parent = parent;
  288. if (parent)
  289. {
  290. if (parent->l_left == node)
  291. parent->l_left = child;
  292. else
  293. parent->l_right = child;
  294. }
  295. else
  296. node->table->top = child;
  297. route_node_free (node);
  298. /* If parent node is stub then delete it also. */
  299. if (parent && parent->lock == 0)
  300. route_node_delete (parent);
  301. }
  302. /* Get fist node and lock it. This function is useful when one want
  303. to lookup all the node exist in the routing table. */
  304. struct route_node *
  305. route_top (struct route_table *table)
  306. {
  307. /* If there is no node in the routing table return NULL. */
  308. if (table->top == NULL)
  309. return NULL;
  310. /* Lock the top node and return it. */
  311. route_lock_node (table->top);
  312. return table->top;
  313. }
  314. /* Unlock current node and lock next node then return it. */
  315. struct route_node *
  316. route_next (struct route_node *node)
  317. {
  318. struct route_node *next;
  319. struct route_node *start;
  320. /* Node may be deleted from route_unlock_node so we have to preserve
  321. next node's pointer. */
  322. if (node->l_left)
  323. {
  324. next = node->l_left;
  325. route_lock_node (next);
  326. route_unlock_node (node);
  327. return next;
  328. }
  329. if (node->l_right)
  330. {
  331. next = node->l_right;
  332. route_lock_node (next);
  333. route_unlock_node (node);
  334. return next;
  335. }
  336. start = node;
  337. while (node->parent)
  338. {
  339. if (node->parent->l_left == node && node->parent->l_right)
  340. {
  341. next = node->parent->l_right;
  342. route_lock_node (next);
  343. route_unlock_node (start);
  344. return next;
  345. }
  346. node = node->parent;
  347. }
  348. route_unlock_node (start);
  349. return NULL;
  350. }
  351. /* Unlock current node and lock next node until limit. */
  352. struct route_node *
  353. route_next_until (struct route_node *node, struct route_node *limit)
  354. {
  355. struct route_node *next;
  356. struct route_node *start;
  357. /* Node may be deleted from route_unlock_node so we have to preserve
  358. next node's pointer. */
  359. if (node->l_left)
  360. {
  361. next = node->l_left;
  362. route_lock_node (next);
  363. route_unlock_node (node);
  364. return next;
  365. }
  366. if (node->l_right)
  367. {
  368. next = node->l_right;
  369. route_lock_node (next);
  370. route_unlock_node (node);
  371. return next;
  372. }
  373. start = node;
  374. while (node->parent && node != limit)
  375. {
  376. if (node->parent->l_left == node && node->parent->l_right)
  377. {
  378. next = node->parent->l_right;
  379. route_lock_node (next);
  380. route_unlock_node (start);
  381. return next;
  382. }
  383. node = node->parent;
  384. }
  385. route_unlock_node (start);
  386. return NULL;
  387. }