bgp_community.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650
  1. /* Community attribute related functions.
  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 "hash.h"
  18. #include "memory.h"
  19. #include "bgpd/bgp_community.h"
  20. /* Hash of community attribute. */
  21. static struct hash *comhash;
  22. /* Allocate a new communities value. */
  23. static struct community *
  24. community_new (void)
  25. {
  26. return (struct community *) XCALLOC (MTYPE_COMMUNITY,
  27. sizeof (struct community));
  28. }
  29. /* Free communities value. */
  30. void
  31. community_free (struct community *com)
  32. {
  33. if (com->val)
  34. XFREE (MTYPE_COMMUNITY_VAL, com->val);
  35. if (com->str)
  36. XFREE (MTYPE_COMMUNITY_STR, com->str);
  37. XFREE (MTYPE_COMMUNITY, com);
  38. }
  39. /* Add one community value to the community. */
  40. static void
  41. community_add_val (struct community *com, u_int32_t val)
  42. {
  43. com->size++;
  44. if (com->val)
  45. com->val = XREALLOC (MTYPE_COMMUNITY_VAL, com->val, com_length (com));
  46. else
  47. com->val = XMALLOC (MTYPE_COMMUNITY_VAL, com_length (com));
  48. val = htonl (val);
  49. memcpy (com_lastval (com), &val, sizeof (u_int32_t));
  50. }
  51. /* Delete one community. */
  52. void
  53. community_del_val (struct community *com, u_int32_t *val)
  54. {
  55. int i = 0;
  56. int c = 0;
  57. if (! com->val)
  58. return;
  59. while (i < com->size)
  60. {
  61. if (memcmp (com->val + i, val, sizeof (u_int32_t)) == 0)
  62. {
  63. c = com->size -i -1;
  64. if (c > 0)
  65. memmove (com->val + i, com->val + (i + 1), c * sizeof (*val));
  66. com->size--;
  67. if (com->size > 0)
  68. com->val = XREALLOC (MTYPE_COMMUNITY_VAL, com->val,
  69. com_length (com));
  70. else
  71. {
  72. XFREE (MTYPE_COMMUNITY_VAL, com->val);
  73. com->val = NULL;
  74. }
  75. return;
  76. }
  77. i++;
  78. }
  79. }
  80. /* Delete all communities listed in com2 from com1 */
  81. struct community *
  82. community_delete (struct community *com1, struct community *com2)
  83. {
  84. int i = 0;
  85. while(i < com2->size)
  86. {
  87. community_del_val (com1, com2->val + i);
  88. i++;
  89. }
  90. return com1;
  91. }
  92. /* Callback function from qsort(). */
  93. static int
  94. community_compare (const void *a1, const void *a2)
  95. {
  96. u_int32_t v1;
  97. u_int32_t v2;
  98. memcpy (&v1, a1, sizeof (u_int32_t));
  99. memcpy (&v2, a2, sizeof (u_int32_t));
  100. v1 = ntohl (v1);
  101. v2 = ntohl (v2);
  102. if (v1 < v2)
  103. return -1;
  104. if (v1 > v2)
  105. return 1;
  106. return 0;
  107. }
  108. int
  109. community_include (struct community *com, u_int32_t val)
  110. {
  111. int i;
  112. val = htonl (val);
  113. for (i = 0; i < com->size; i++)
  114. if (memcmp (&val, com_nthval (com, i), sizeof (u_int32_t)) == 0)
  115. return 1;
  116. return 0;
  117. }
  118. u_int32_t
  119. community_val_get (struct community *com, int i)
  120. {
  121. u_char *p;
  122. u_int32_t val;
  123. p = (u_char *) com->val;
  124. p += (i * 4);
  125. memcpy (&val, p, sizeof (u_int32_t));
  126. return ntohl (val);
  127. }
  128. /* Sort and uniq given community. */
  129. struct community *
  130. community_uniq_sort (struct community *com)
  131. {
  132. int i;
  133. struct community *new;
  134. u_int32_t val;
  135. if (! com)
  136. return NULL;
  137. new = community_new ();;
  138. for (i = 0; i < com->size; i++)
  139. {
  140. val = community_val_get (com, i);
  141. if (! community_include (new, val))
  142. community_add_val (new, val);
  143. }
  144. qsort (new->val, new->size, sizeof (u_int32_t), community_compare);
  145. return new;
  146. }
  147. /* Convert communities attribute to string.
  148. For Well-known communities value, below keyword is used.
  149. 0x0 "internet"
  150. 0xFFFFFF01 "no-export"
  151. 0xFFFFFF02 "no-advertise"
  152. 0xFFFFFF03 "local-AS"
  153. For other values, "AS:VAL" format is used. */
  154. static char *
  155. community_com2str (struct community *com)
  156. {
  157. int i;
  158. char *str;
  159. char *pnt;
  160. int len;
  161. int first;
  162. u_int32_t comval;
  163. u_int16_t as;
  164. u_int16_t val;
  165. if (!com)
  166. return NULL;
  167. /* When communities attribute is empty. */
  168. if (com->size == 0)
  169. {
  170. str = XMALLOC (MTYPE_COMMUNITY_STR, 1);
  171. str[0] = '\0';
  172. return str;
  173. }
  174. /* Memory allocation is time consuming work. So we calculate
  175. required string length first. */
  176. len = 0;
  177. for (i = 0; i < com->size; i++)
  178. {
  179. memcpy (&comval, com_nthval (com, i), sizeof (u_int32_t));
  180. comval = ntohl (comval);
  181. switch (comval)
  182. {
  183. case COMMUNITY_INTERNET:
  184. len += strlen (" internet");
  185. break;
  186. case COMMUNITY_NO_EXPORT:
  187. len += strlen (" no-export");
  188. break;
  189. case COMMUNITY_NO_ADVERTISE:
  190. len += strlen (" no-advertise");
  191. break;
  192. case COMMUNITY_LOCAL_AS:
  193. len += strlen (" local-AS");
  194. break;
  195. default:
  196. len += strlen (" 65536:65535");
  197. break;
  198. }
  199. }
  200. /* Allocate memory. */
  201. str = pnt = XMALLOC (MTYPE_COMMUNITY_STR, len);
  202. first = 1;
  203. /* Fill in string. */
  204. for (i = 0; i < com->size; i++)
  205. {
  206. memcpy (&comval, com_nthval (com, i), sizeof (u_int32_t));
  207. comval = ntohl (comval);
  208. if (first)
  209. first = 0;
  210. else
  211. *pnt++ = ' ';
  212. switch (comval)
  213. {
  214. case COMMUNITY_INTERNET:
  215. strcpy (pnt, "internet");
  216. pnt += strlen ("internet");
  217. break;
  218. case COMMUNITY_NO_EXPORT:
  219. strcpy (pnt, "no-export");
  220. pnt += strlen ("no-export");
  221. break;
  222. case COMMUNITY_NO_ADVERTISE:
  223. strcpy (pnt, "no-advertise");
  224. pnt += strlen ("no-advertise");
  225. break;
  226. case COMMUNITY_LOCAL_AS:
  227. strcpy (pnt, "local-AS");
  228. pnt += strlen ("local-AS");
  229. break;
  230. default:
  231. as = (comval >> 16) & 0xFFFF;
  232. val = comval & 0xFFFF;
  233. sprintf (pnt, "%u:%d", as, val);
  234. pnt += strlen (pnt);
  235. break;
  236. }
  237. }
  238. *pnt = '\0';
  239. return str;
  240. }
  241. /* Intern communities attribute. */
  242. struct community *
  243. community_intern (struct community *com)
  244. {
  245. struct community *find;
  246. /* Assert this community structure is not interned. */
  247. assert (com->refcnt == 0);
  248. /* Lookup community hash. */
  249. find = (struct community *) hash_get (comhash, com, hash_alloc_intern);
  250. /* Arguemnt com is allocated temporary. So when it is not used in
  251. hash, it should be freed. */
  252. if (find != com)
  253. community_free (com);
  254. /* Increment refrence counter. */
  255. find->refcnt++;
  256. /* Make string. */
  257. if (! find->str)
  258. find->str = community_com2str (find);
  259. return find;
  260. }
  261. /* Free community attribute. */
  262. void
  263. community_unintern (struct community **com)
  264. {
  265. struct community *ret;
  266. if ((*com)->refcnt)
  267. (*com)->refcnt--;
  268. /* Pull off from hash. */
  269. if ((*com)->refcnt == 0)
  270. {
  271. /* Community value com must exist in hash. */
  272. ret = (struct community *) hash_release (comhash, *com);
  273. assert (ret != NULL);
  274. community_free (*com);
  275. *com = NULL;
  276. }
  277. }
  278. /* Create new community attribute. */
  279. struct community *
  280. community_parse (u_int32_t *pnt, u_short length)
  281. {
  282. struct community tmp;
  283. struct community *new;
  284. /* If length is malformed return NULL. */
  285. if (length % 4)
  286. return NULL;
  287. /* Make temporary community for hash look up. */
  288. tmp.size = length / 4;
  289. tmp.val = pnt;
  290. new = community_uniq_sort (&tmp);
  291. return community_intern (new);
  292. }
  293. struct community *
  294. community_dup (struct community *com)
  295. {
  296. struct community *new;
  297. new = XCALLOC (MTYPE_COMMUNITY, sizeof (struct community));
  298. new->size = com->size;
  299. if (new->size)
  300. {
  301. new->val = XMALLOC (MTYPE_COMMUNITY_VAL, com->size * 4);
  302. memcpy (new->val, com->val, com->size * 4);
  303. }
  304. else
  305. new->val = NULL;
  306. return new;
  307. }
  308. /* Retrun string representation of communities attribute. */
  309. char *
  310. community_str (struct community *com)
  311. {
  312. if (!com)
  313. return NULL;
  314. if (! com->str)
  315. com->str = community_com2str (com);
  316. return com->str;
  317. }
  318. /* Make hash value of community attribute. This function is used by
  319. hash package.*/
  320. unsigned int
  321. community_hash_make (struct community *com)
  322. {
  323. unsigned char *pnt = (unsigned char *)com->val;
  324. int size = com->size * 4;
  325. unsigned int key = 0;
  326. int c;
  327. for (c = 0; c < size; c += 4)
  328. {
  329. key += pnt[c];
  330. key += pnt[c + 1];
  331. key += pnt[c + 2];
  332. key += pnt[c + 3];
  333. }
  334. return key;
  335. }
  336. int
  337. community_match (const struct community *com1, const struct community *com2)
  338. {
  339. int i = 0;
  340. int j = 0;
  341. if (com1 == NULL && com2 == NULL)
  342. return 1;
  343. if (com1 == NULL || com2 == NULL)
  344. return 0;
  345. if (com1->size < com2->size)
  346. return 0;
  347. /* Every community on com2 needs to be on com1 for this to match */
  348. while (i < com1->size && j < com2->size)
  349. {
  350. if (memcmp (com1->val + i, com2->val + j, sizeof (u_int32_t)) == 0)
  351. j++;
  352. i++;
  353. }
  354. if (j == com2->size)
  355. return 1;
  356. else
  357. return 0;
  358. }
  359. /* If two aspath have same value then return 1 else return 0. This
  360. function is used by hash package. */
  361. int
  362. community_cmp (const struct community *com1, const struct community *com2)
  363. {
  364. if (com1 == NULL && com2 == NULL)
  365. return 1;
  366. if (com1 == NULL || com2 == NULL)
  367. return 0;
  368. if (com1->size == com2->size)
  369. if (memcmp (com1->val, com2->val, com1->size * 4) == 0)
  370. return 1;
  371. return 0;
  372. }
  373. /* Add com2 to the end of com1. */
  374. struct community *
  375. community_merge (struct community *com1, struct community *com2)
  376. {
  377. if (com1->val)
  378. com1->val = XREALLOC (MTYPE_COMMUNITY_VAL, com1->val,
  379. (com1->size + com2->size) * 4);
  380. else
  381. com1->val = XMALLOC (MTYPE_COMMUNITY_VAL, (com1->size + com2->size) * 4);
  382. memcpy (com1->val + com1->size, com2->val, com2->size * 4);
  383. com1->size += com2->size;
  384. return com1;
  385. }
  386. /* Community token enum. */
  387. enum community_token
  388. {
  389. community_token_val,
  390. community_token_no_export,
  391. community_token_no_advertise,
  392. community_token_local_as,
  393. community_token_unknown
  394. };
  395. /* Get next community token from string. */
  396. static const char *
  397. community_gettoken (const char *buf, enum community_token *token,
  398. u_int32_t *val)
  399. {
  400. const char *p = buf;
  401. /* Skip white space. */
  402. while (isspace ((int) *p))
  403. p++;
  404. /* Check the end of the line. */
  405. if (*p == '\0')
  406. return NULL;
  407. /* Well known community string check. */
  408. if (isalpha ((int) *p))
  409. {
  410. if (strncmp (p, "internet", strlen ("internet")) == 0)
  411. {
  412. *val = COMMUNITY_INTERNET;
  413. *token = community_token_no_export;
  414. p += strlen ("internet");
  415. return p;
  416. }
  417. if (strncmp (p, "no-export", strlen ("no-export")) == 0)
  418. {
  419. *val = COMMUNITY_NO_EXPORT;
  420. *token = community_token_no_export;
  421. p += strlen ("no-export");
  422. return p;
  423. }
  424. if (strncmp (p, "no-advertise", strlen ("no-advertise")) == 0)
  425. {
  426. *val = COMMUNITY_NO_ADVERTISE;
  427. *token = community_token_no_advertise;
  428. p += strlen ("no-advertise");
  429. return p;
  430. }
  431. if (strncmp (p, "local-AS", strlen ("local-AS")) == 0)
  432. {
  433. *val = COMMUNITY_LOCAL_AS;
  434. *token = community_token_local_as;
  435. p += strlen ("local-AS");
  436. return p;
  437. }
  438. /* Unknown string. */
  439. *token = community_token_unknown;
  440. return NULL;
  441. }
  442. /* Community value. */
  443. if (isdigit ((int) *p))
  444. {
  445. int separator = 0;
  446. int digit = 0;
  447. u_int32_t community_low = 0;
  448. u_int32_t community_high = 0;
  449. while (isdigit ((int) *p) || *p == ':')
  450. {
  451. if (*p == ':')
  452. {
  453. if (separator)
  454. {
  455. *token = community_token_unknown;
  456. return NULL;
  457. }
  458. else
  459. {
  460. separator = 1;
  461. digit = 0;
  462. community_high = community_low << 16;
  463. community_low = 0;
  464. }
  465. }
  466. else
  467. {
  468. digit = 1;
  469. community_low *= 10;
  470. community_low += (*p - '0');
  471. }
  472. p++;
  473. }
  474. if (! digit)
  475. {
  476. *token = community_token_unknown;
  477. return NULL;
  478. }
  479. *val = community_high + community_low;
  480. *token = community_token_val;
  481. return p;
  482. }
  483. *token = community_token_unknown;
  484. return NULL;
  485. }
  486. /* convert string to community structure */
  487. struct community *
  488. community_str2com (const char *str)
  489. {
  490. struct community *com = NULL;
  491. struct community *com_sort = NULL;
  492. u_int32_t val = 0;
  493. enum community_token token = community_token_unknown;
  494. do
  495. {
  496. str = community_gettoken (str, &token, &val);
  497. switch (token)
  498. {
  499. case community_token_val:
  500. case community_token_no_export:
  501. case community_token_no_advertise:
  502. case community_token_local_as:
  503. if (com == NULL)
  504. com = community_new();
  505. community_add_val (com, val);
  506. break;
  507. case community_token_unknown:
  508. default:
  509. if (com)
  510. community_free (com);
  511. return NULL;
  512. }
  513. } while (str);
  514. if (! com)
  515. return NULL;
  516. com_sort = community_uniq_sort (com);
  517. community_free (com);
  518. return com_sort;
  519. }
  520. /* Return communities hash entry count. */
  521. unsigned long
  522. community_count (void)
  523. {
  524. return comhash->count;
  525. }
  526. /* Return communities hash. */
  527. struct hash *
  528. community_hash (void)
  529. {
  530. return comhash;
  531. }
  532. /* Initialize comminity related hash. */
  533. void
  534. community_init (void)
  535. {
  536. comhash = hash_create ((unsigned int (*) (void *))community_hash_make,
  537. (int (*) (const void *, const void *))community_cmp);
  538. }
  539. void
  540. community_finish (void)
  541. {
  542. hash_free (comhash);
  543. comhash = NULL;
  544. }