bgp_table.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508
  1. /* BGP routing table
  2. Copyright (C) 1998, 2001 Kunihiro Ishiguro
  3. This file is part of GNU Zebra.
  4. GNU Zebra is free software; you can redistribute it and/or modify it
  5. under the terms of the GNU General Public License as published by the
  6. Free Software Foundation; either version 2, or (at your option) any
  7. later version.
  8. GNU Zebra is distributed in the hope that it will be useful, but
  9. WITHOUT ANY WARRANTY; without even the implied warranty of
  10. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  11. General Public License for more details.
  12. You should have received a copy of the GNU General Public License
  13. along with GNU Zebra; see the file COPYING. If not, write to the Free
  14. Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  15. 02111-1307, USA. */
  16. #include <zebra.h>
  17. #include "prefix.h"
  18. #include "memory.h"
  19. #include "sockunion.h"
  20. #include "vty.h"
  21. #include "bgpd/bgpd.h"
  22. #include "bgpd/bgp_table.h"
  23. static void bgp_node_delete (struct bgp_node *);
  24. static void bgp_table_free (struct bgp_table *);
  25. struct bgp_table *
  26. bgp_table_init (afi_t afi, safi_t safi)
  27. {
  28. struct bgp_table *rt;
  29. rt = XCALLOC (MTYPE_BGP_TABLE, sizeof (struct bgp_table));
  30. bgp_table_lock(rt);
  31. rt->type = BGP_TABLE_MAIN;
  32. rt->afi = afi;
  33. rt->safi = safi;
  34. return rt;
  35. }
  36. void
  37. bgp_table_lock (struct bgp_table *rt)
  38. {
  39. rt->lock++;
  40. }
  41. void
  42. bgp_table_unlock (struct bgp_table *rt)
  43. {
  44. assert (rt->lock > 0);
  45. rt->lock--;
  46. if (rt->lock == 0)
  47. bgp_table_free (rt);
  48. }
  49. void
  50. bgp_table_finish (struct bgp_table **rt)
  51. {
  52. if (*rt != NULL)
  53. {
  54. bgp_table_unlock(*rt);
  55. *rt = NULL;
  56. }
  57. }
  58. static struct bgp_node *
  59. bgp_node_create (void)
  60. {
  61. return XCALLOC (MTYPE_BGP_NODE, sizeof (struct bgp_node));
  62. }
  63. /* Allocate new route node with prefix set. */
  64. static struct bgp_node *
  65. bgp_node_set (struct bgp_table *table, struct prefix *prefix)
  66. {
  67. struct bgp_node *node;
  68. node = bgp_node_create ();
  69. prefix_copy (&node->p, prefix);
  70. node->table = table;
  71. return node;
  72. }
  73. /* Free route node. */
  74. static void
  75. bgp_node_free (struct bgp_node *node)
  76. {
  77. XFREE (MTYPE_BGP_NODE, node);
  78. }
  79. /* Free route table. */
  80. static void
  81. bgp_table_free (struct bgp_table *rt)
  82. {
  83. struct bgp_node *tmp_node;
  84. struct bgp_node *node;
  85. if (rt == NULL)
  86. return;
  87. node = rt->top;
  88. /* Bulk deletion of nodes remaining in this table. This function is not
  89. called until workers have completed their dependency on this table.
  90. A final bgp_unlock_node() will not be called for these nodes. */
  91. while (node)
  92. {
  93. if (node->l_left)
  94. {
  95. node = node->l_left;
  96. continue;
  97. }
  98. if (node->l_right)
  99. {
  100. node = node->l_right;
  101. continue;
  102. }
  103. tmp_node = node;
  104. node = node->parent;
  105. tmp_node->table->count--;
  106. tmp_node->lock = 0; /* to cause assert if unlocked after this */
  107. bgp_node_free (tmp_node);
  108. if (node != NULL)
  109. {
  110. if (node->l_left == tmp_node)
  111. node->l_left = NULL;
  112. else
  113. node->l_right = NULL;
  114. }
  115. else
  116. {
  117. break;
  118. }
  119. }
  120. assert (rt->count == 0);
  121. if (rt->owner)
  122. {
  123. peer_unlock (rt->owner);
  124. rt->owner = NULL;
  125. }
  126. XFREE (MTYPE_BGP_TABLE, rt);
  127. return;
  128. }
  129. /* Utility mask array. */
  130. static u_char maskbit[] =
  131. {
  132. 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff
  133. };
  134. /* Common prefix route genaration. */
  135. static void
  136. route_common (struct prefix *n, struct prefix *p, struct prefix *new)
  137. {
  138. int i;
  139. u_char diff;
  140. u_char mask;
  141. u_char *np = (u_char *)&n->u.prefix;
  142. u_char *pp = (u_char *)&p->u.prefix;
  143. u_char *newp = (u_char *)&new->u.prefix;
  144. for (i = 0; i < p->prefixlen / 8; i++)
  145. {
  146. if (np[i] == pp[i])
  147. newp[i] = np[i];
  148. else
  149. break;
  150. }
  151. new->prefixlen = i * 8;
  152. if (new->prefixlen != p->prefixlen)
  153. {
  154. diff = np[i] ^ pp[i];
  155. mask = 0x80;
  156. while (new->prefixlen < p->prefixlen && !(mask & diff))
  157. {
  158. mask >>= 1;
  159. new->prefixlen++;
  160. }
  161. newp[i] = np[i] & maskbit[new->prefixlen % 8];
  162. }
  163. }
  164. static void
  165. set_link (struct bgp_node *node, struct bgp_node *new)
  166. {
  167. unsigned int bit = prefix_bit (&new->p.u.prefix, node->p.prefixlen);
  168. node->link[bit] = new;
  169. new->parent = node;
  170. }
  171. /* Lock node. */
  172. struct bgp_node *
  173. bgp_lock_node (struct bgp_node *node)
  174. {
  175. node->lock++;
  176. return node;
  177. }
  178. /* Unlock node. */
  179. void
  180. bgp_unlock_node (struct bgp_node *node)
  181. {
  182. assert (node->lock > 0);
  183. node->lock--;
  184. if (node->lock == 0)
  185. bgp_node_delete (node);
  186. }
  187. /* Find matched prefix. */
  188. struct bgp_node *
  189. bgp_node_match (const struct bgp_table *table, struct prefix *p)
  190. {
  191. struct bgp_node *node;
  192. struct bgp_node *matched;
  193. matched = NULL;
  194. node = table->top;
  195. /* Walk down tree. If there is matched route then store it to
  196. matched. */
  197. while (node && node->p.prefixlen <= p->prefixlen &&
  198. prefix_match (&node->p, p))
  199. {
  200. if (node->info)
  201. matched = node;
  202. node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
  203. }
  204. /* If matched route found, return it. */
  205. if (matched)
  206. return bgp_lock_node (matched);
  207. return NULL;
  208. }
  209. struct bgp_node *
  210. bgp_node_match_ipv4 (const struct bgp_table *table, struct in_addr *addr)
  211. {
  212. struct prefix_ipv4 p;
  213. memset (&p, 0, sizeof (struct prefix_ipv4));
  214. p.family = AF_INET;
  215. p.prefixlen = IPV4_MAX_PREFIXLEN;
  216. p.prefix = *addr;
  217. return bgp_node_match (table, (struct prefix *) &p);
  218. }
  219. #ifdef HAVE_IPV6
  220. struct bgp_node *
  221. bgp_node_match_ipv6 (const struct bgp_table *table, struct in6_addr *addr)
  222. {
  223. struct prefix_ipv6 p;
  224. memset (&p, 0, sizeof (struct prefix_ipv6));
  225. p.family = AF_INET6;
  226. p.prefixlen = IPV6_MAX_PREFIXLEN;
  227. p.prefix = *addr;
  228. return bgp_node_match (table, (struct prefix *) &p);
  229. }
  230. #endif /* HAVE_IPV6 */
  231. /* Lookup same prefix node. Return NULL when we can't find route. */
  232. struct bgp_node *
  233. bgp_node_lookup (const struct bgp_table *table, struct prefix *p)
  234. {
  235. struct bgp_node *node;
  236. node = table->top;
  237. while (node && node->p.prefixlen <= p->prefixlen &&
  238. prefix_match (&node->p, p))
  239. {
  240. if (node->p.prefixlen == p->prefixlen && node->info)
  241. return bgp_lock_node (node);
  242. node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
  243. }
  244. return NULL;
  245. }
  246. /* Add node to routing table. */
  247. struct bgp_node *
  248. bgp_node_get (struct bgp_table *const table, struct prefix *p)
  249. {
  250. struct bgp_node *new;
  251. struct bgp_node *node;
  252. struct bgp_node *match;
  253. match = NULL;
  254. node = table->top;
  255. while (node && node->p.prefixlen <= p->prefixlen &&
  256. prefix_match (&node->p, p))
  257. {
  258. if (node->p.prefixlen == p->prefixlen)
  259. {
  260. bgp_lock_node (node);
  261. return node;
  262. }
  263. match = node;
  264. node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
  265. }
  266. if (node == NULL)
  267. {
  268. new = bgp_node_set (table, p);
  269. if (match)
  270. set_link (match, new);
  271. else
  272. table->top = new;
  273. }
  274. else
  275. {
  276. new = bgp_node_create ();
  277. route_common (&node->p, p, &new->p);
  278. new->p.family = p->family;
  279. new->table = table;
  280. set_link (new, node);
  281. if (match)
  282. set_link (match, new);
  283. else
  284. table->top = new;
  285. if (new->p.prefixlen != p->prefixlen)
  286. {
  287. match = new;
  288. bgp_lock_node (match);
  289. new = bgp_node_set (table, p);
  290. set_link (match, new);
  291. table->count++;
  292. }
  293. }
  294. table->count++;
  295. bgp_lock_node (new);
  296. return new;
  297. }
  298. /* Delete node from the routing table. */
  299. static void
  300. bgp_node_delete (struct bgp_node *node)
  301. {
  302. struct bgp_node *child;
  303. struct bgp_node *parent;
  304. assert (node->lock == 0);
  305. assert (node->info == NULL);
  306. if (node->l_left && node->l_right)
  307. return;
  308. if (node->l_left)
  309. child = node->l_left;
  310. else
  311. child = node->l_right;
  312. parent = node->parent;
  313. if (child)
  314. child->parent = parent;
  315. if (parent)
  316. {
  317. if (parent->l_left == node)
  318. parent->l_left = child;
  319. else
  320. parent->l_right = child;
  321. }
  322. else
  323. node->table->top = child;
  324. node->table->count--;
  325. bgp_node_free (node);
  326. /* If parent node is stub then delete it also. */
  327. if (parent && parent->lock == 0)
  328. bgp_node_delete (parent);
  329. }
  330. /* Get fist node and lock it. This function is useful when one want
  331. to lookup all the node exist in the routing table. */
  332. struct bgp_node *
  333. bgp_table_top (const struct bgp_table *const table)
  334. {
  335. /* If there is no node in the routing table return NULL. */
  336. if (table->top == NULL)
  337. return NULL;
  338. /* Lock the top node and return it. */
  339. bgp_lock_node (table->top);
  340. return table->top;
  341. }
  342. /* Unlock current node and lock next node then return it. */
  343. struct bgp_node *
  344. bgp_route_next (struct bgp_node *node)
  345. {
  346. struct bgp_node *next;
  347. struct bgp_node *start;
  348. /* Node may be deleted from bgp_unlock_node so we have to preserve
  349. next node's pointer. */
  350. if (node->l_left)
  351. {
  352. next = node->l_left;
  353. bgp_lock_node (next);
  354. bgp_unlock_node (node);
  355. return next;
  356. }
  357. if (node->l_right)
  358. {
  359. next = node->l_right;
  360. bgp_lock_node (next);
  361. bgp_unlock_node (node);
  362. return next;
  363. }
  364. start = node;
  365. while (node->parent)
  366. {
  367. if (node->parent->l_left == node && node->parent->l_right)
  368. {
  369. next = node->parent->l_right;
  370. bgp_lock_node (next);
  371. bgp_unlock_node (start);
  372. return next;
  373. }
  374. node = node->parent;
  375. }
  376. bgp_unlock_node (start);
  377. return NULL;
  378. }
  379. /* Unlock current node and lock next node until limit. */
  380. struct bgp_node *
  381. bgp_route_next_until (struct bgp_node *node, struct bgp_node *limit)
  382. {
  383. struct bgp_node *next;
  384. struct bgp_node *start;
  385. /* Node may be deleted from bgp_unlock_node so we have to preserve
  386. next node's pointer. */
  387. if (node->l_left)
  388. {
  389. next = node->l_left;
  390. bgp_lock_node (next);
  391. bgp_unlock_node (node);
  392. return next;
  393. }
  394. if (node->l_right)
  395. {
  396. next = node->l_right;
  397. bgp_lock_node (next);
  398. bgp_unlock_node (node);
  399. return next;
  400. }
  401. start = node;
  402. while (node->parent && node != limit)
  403. {
  404. if (node->parent->l_left == node && node->parent->l_right)
  405. {
  406. next = node->parent->l_right;
  407. bgp_lock_node (next);
  408. bgp_unlock_node (start);
  409. return next;
  410. }
  411. node = node->parent;
  412. }
  413. bgp_unlock_node (start);
  414. return NULL;
  415. }
  416. unsigned long
  417. bgp_table_count (const struct bgp_table *table)
  418. {
  419. return table->count;
  420. }