table.c 9.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462
  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. node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
  178. }
  179. /* If matched route found, return it. */
  180. if (matched)
  181. return route_lock_node (matched);
  182. return NULL;
  183. }
  184. struct route_node *
  185. route_node_match_ipv4 (const struct route_table *table,
  186. const struct in_addr *addr)
  187. {
  188. struct prefix_ipv4 p;
  189. memset (&p, 0, sizeof (struct prefix_ipv4));
  190. p.family = AF_INET;
  191. p.prefixlen = IPV4_MAX_PREFIXLEN;
  192. p.prefix = *addr;
  193. return route_node_match (table, (struct prefix *) &p);
  194. }
  195. #ifdef HAVE_IPV6
  196. struct route_node *
  197. route_node_match_ipv6 (const struct route_table *table,
  198. const struct in6_addr *addr)
  199. {
  200. struct prefix_ipv6 p;
  201. memset (&p, 0, sizeof (struct prefix_ipv6));
  202. p.family = AF_INET6;
  203. p.prefixlen = IPV6_MAX_PREFIXLEN;
  204. p.prefix = *addr;
  205. return route_node_match (table, (struct prefix *) &p);
  206. }
  207. #endif /* HAVE_IPV6 */
  208. /* Lookup same prefix node. Return NULL when we can't find route. */
  209. struct route_node *
  210. route_node_lookup (struct route_table *table, struct prefix *p)
  211. {
  212. struct route_node *node;
  213. node = table->top;
  214. while (node && node->p.prefixlen <= p->prefixlen &&
  215. prefix_match (&node->p, p))
  216. {
  217. if (node->p.prefixlen == p->prefixlen && node->info)
  218. return route_lock_node (node);
  219. node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
  220. }
  221. return NULL;
  222. }
  223. /* Add node to routing table. */
  224. struct route_node *
  225. route_node_get (struct route_table *table, struct prefix *p)
  226. {
  227. struct route_node *new;
  228. struct route_node *node;
  229. struct route_node *match;
  230. match = NULL;
  231. node = table->top;
  232. while (node && node->p.prefixlen <= p->prefixlen &&
  233. prefix_match (&node->p, p))
  234. {
  235. if (node->p.prefixlen == p->prefixlen)
  236. {
  237. route_lock_node (node);
  238. return node;
  239. }
  240. match = node;
  241. node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
  242. }
  243. if (node == NULL)
  244. {
  245. new = route_node_set (table, p);
  246. if (match)
  247. set_link (match, new);
  248. else
  249. table->top = new;
  250. }
  251. else
  252. {
  253. new = route_node_new ();
  254. route_common (&node->p, p, &new->p);
  255. new->p.family = p->family;
  256. new->table = table;
  257. set_link (new, node);
  258. if (match)
  259. set_link (match, new);
  260. else
  261. table->top = new;
  262. if (new->p.prefixlen != p->prefixlen)
  263. {
  264. match = new;
  265. new = route_node_set (table, p);
  266. set_link (match, new);
  267. }
  268. }
  269. route_lock_node (new);
  270. return new;
  271. }
  272. /* Delete node from the routing table. */
  273. void
  274. route_node_delete (struct route_node *node)
  275. {
  276. struct route_node *child;
  277. struct route_node *parent;
  278. assert (node->lock == 0);
  279. assert (node->info == NULL);
  280. if (node->l_left && node->l_right)
  281. return;
  282. if (node->l_left)
  283. child = node->l_left;
  284. else
  285. child = node->l_right;
  286. parent = node->parent;
  287. if (child)
  288. child->parent = parent;
  289. if (parent)
  290. {
  291. if (parent->l_left == node)
  292. parent->l_left = child;
  293. else
  294. parent->l_right = child;
  295. }
  296. else
  297. node->table->top = child;
  298. route_node_free (node);
  299. /* If parent node is stub then delete it also. */
  300. if (parent && parent->lock == 0)
  301. route_node_delete (parent);
  302. }
  303. /* Get fist node and lock it. This function is useful when one want
  304. to lookup all the node exist in the routing table. */
  305. struct route_node *
  306. route_top (struct route_table *table)
  307. {
  308. /* If there is no node in the routing table return NULL. */
  309. if (table->top == NULL)
  310. return NULL;
  311. /* Lock the top node and return it. */
  312. route_lock_node (table->top);
  313. return table->top;
  314. }
  315. /* Unlock current node and lock next node then return it. */
  316. struct route_node *
  317. route_next (struct route_node *node)
  318. {
  319. struct route_node *next;
  320. struct route_node *start;
  321. /* Node may be deleted from route_unlock_node so we have to preserve
  322. next node's pointer. */
  323. if (node->l_left)
  324. {
  325. next = node->l_left;
  326. route_lock_node (next);
  327. route_unlock_node (node);
  328. return next;
  329. }
  330. if (node->l_right)
  331. {
  332. next = node->l_right;
  333. route_lock_node (next);
  334. route_unlock_node (node);
  335. return next;
  336. }
  337. start = node;
  338. while (node->parent)
  339. {
  340. if (node->parent->l_left == node && node->parent->l_right)
  341. {
  342. next = node->parent->l_right;
  343. route_lock_node (next);
  344. route_unlock_node (start);
  345. return next;
  346. }
  347. node = node->parent;
  348. }
  349. route_unlock_node (start);
  350. return NULL;
  351. }
  352. /* Unlock current node and lock next node until limit. */
  353. struct route_node *
  354. route_next_until (struct route_node *node, struct route_node *limit)
  355. {
  356. struct route_node *next;
  357. struct route_node *start;
  358. /* Node may be deleted from route_unlock_node so we have to preserve
  359. next node's pointer. */
  360. if (node->l_left)
  361. {
  362. next = node->l_left;
  363. route_lock_node (next);
  364. route_unlock_node (node);
  365. return next;
  366. }
  367. if (node->l_right)
  368. {
  369. next = node->l_right;
  370. route_lock_node (next);
  371. route_unlock_node (node);
  372. return next;
  373. }
  374. start = node;
  375. while (node->parent && node != limit)
  376. {
  377. if (node->parent->l_left == node && node->parent->l_right)
  378. {
  379. next = node->parent->l_right;
  380. route_lock_node (next);
  381. route_unlock_node (start);
  382. return next;
  383. }
  384. node = node->parent;
  385. }
  386. route_unlock_node (start);
  387. return NULL;
  388. }