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