bgpd/bgp_community.c

   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     }
 340 }
 341
 342 /* Create new community attribute. */
 343 struct community *
 344 community_parse (u_int32_t *pnt, u_short length)
 345 {
 346   struct community tmp;
 347   struct community *new;
 348
 349   /* If length is malformed return NULL. */
 350   if (length % 4)
 351     return NULL;
 352
 353   /* Make temporary community for hash look up. */
 354   tmp.size = length / 4;
 355   tmp.val = pnt;
 356
 357   new = community_uniq_sort (&tmp);
 358
 359   return community_intern (new);
 360 }
 361
 362 struct community *
 363 community_dup (struct community *com)
 364 {
 365   struct community *new;
 366
 367   new = XCALLOC (MTYPE_COMMUNITY, sizeof (struct community));
 368   new->size = com->size;
 369   if (new->size)
 370     {
 371       new->val = XMALLOC (MTYPE_COMMUNITY_VAL, com->size * 4);
 372       memcpy (new->val, com->val, com->size * 4);
 373     }
 374   else
 375     new->val = NULL;
 376   return new;
 377 }
 378
 379 /* Retrun string representation of communities attribute. */
 380 char *
 381 community_str (struct community *com)
 382 {
 383   if (!com)
 384     return NULL;
 385
 386   if (! com->str)
 387     com->str = community_com2str (com);
 388   return com->str;
 389 }
 390
 391 /* Make hash value of community attribute. This function is used by
 392    hash package.*/
 393 unsigned int
 394 community_hash_make (struct community *com)
 395 {
 396   int c;
 397   unsigned int key;
 398   unsigned char *pnt;
 399
 400   key = 0;
 401   pnt = (unsigned char *)com->val;
 402
 403   for(c = 0; c < com->size * 4; c++)
 404     key += pnt[c];
 405
 406   return key;
 407 }
 408
 409 int
 410 community_match (const struct community *com1, const struct community *com2)
 411 {
 412   int i = 0;
 413   int j = 0;
 414
 415   if (com1 == NULL && com2 == NULL)
 416     return 1;
 417
 418   if (com1 == NULL || com2 == NULL)
 419     return 0;
 420
 421   if (com1->size < com2->size)
 422     return 0;
 423
 424   /* Every community on com2 needs to be on com1 for this to match */
 425   while (i < com1->size && j < com2->size)
 426     {
 427       if (memcmp (com1->val + i, com2->val + j, sizeof (u_int32_t)) == 0)
 428         j++;
 429       i++;
 430     }
 431
 432   if (j == com2->size)
 433     return 1;
 434   else
 435     return 0;
 436 }
 437
 438 /* If two aspath have same value then return 1 else return 0. This
 439    function is used by hash package. */
 440 int
 441 community_cmp (const struct community *com1, const struct community *com2)
 442 {
 443   if (com1 == NULL && com2 == NULL)
 444     return 1;
 445   if (com1 == NULL || com2 == NULL)
 446     return 0;
 447
 448   if (com1->size == com2->size)
 449     if (memcmp (com1->val, com2->val, com1->size * 4) == 0)
 450       return 1;
 451   return 0;
 452 }
 453
 454 /* Add com2 to the end of com1. */
 455 struct community *
 456 community_merge (struct community *com1, struct community *com2)
 457 {
 458   if (com1->val)
 459     com1->val = XREALLOC (MTYPE_COMMUNITY_VAL, com1->val,
 460                           (com1->size + com2->size) * 4);
 461   else
 462     com1->val = XMALLOC (MTYPE_COMMUNITY_VAL, (com1->size + com2->size) * 4);
 463
 464   memcpy (com1->val + com1->size, com2->val, com2->size * 4);
 465   com1->size += com2->size;
 466
 467   return com1;
 468 }
 469
 470 /* Community token enum. */
 471 enum community_token
 472 {
 473   community_token_val,
 474   community_token_no_export,
 475   community_token_no_advertise,
 476   community_token_local_as,
 477   community_token_unknown
 478 };
 479
 480 /* Get next community token from string. */
 481 static const char *
 482 community_gettoken (const char *buf, enum community_token *token,
 483                     u_int32_t *val)
 484 {
 485   const char *p = buf;
 486
 487   /* Skip white space. */
 488   while (isspace ((int) *p))
 489     p++;
 490
 491   /* Check the end of the line. */
 492   if (*p == '\0')
 493     return NULL;
 494
 495   /* Well known community string check. */
 496   if (isalpha ((int) *p))
 497     {
 498       if (strncmp (p, "internet", strlen ("internet")) == 0)
 499         {
 500           *val = COMMUNITY_INTERNET;
 501           *token = community_token_no_export;
 502           p += strlen ("internet");
 503           return p;
 504         }
 505       if (strncmp (p, "no-export", strlen ("no-export")) == 0)
 506         {
 507           *val = COMMUNITY_NO_EXPORT;
 508           *token = community_token_no_export;
 509           p += strlen ("no-export");
 510           return p;
 511         }
 512       if (strncmp (p, "no-advertise", strlen ("no-advertise")) == 0)
 513         {
 514           *val = COMMUNITY_NO_ADVERTISE;
 515           *token = community_token_no_advertise;
 516           p += strlen ("no-advertise");
 517           return p;
 518         }
 519       if (strncmp (p, "local-AS", strlen ("local-AS")) == 0)
 520         {
 521           *val = COMMUNITY_LOCAL_AS;
 522           *token = community_token_local_as;
 523           p += strlen ("local-AS");
 524           return p;
 525         }
 526
 527       /* Unknown string. */
 528       *token = community_token_unknown;
 529       return NULL;
 530     }
 531
 532   /* Community value. */
 533   if (isdigit ((int) *p))
 534     {
 535       int separator = 0;
 536       int digit = 0;
 537       u_int32_t community_low = 0;
 538       u_int32_t community_high = 0;
 539
 540       while (isdigit ((int) *p) || *p == ':')
 541         {
 542           if (*p == ':')
 543             {
 544               if (separator)
 545                 {
 546                   *token = community_token_unknown;
 547                   return NULL;
 548                 }
 549               else
 550                 {
 551                   separator = 1;
 552                   digit = 0;
 553                   community_high = community_low << 16;
 554                   community_low = 0;
 555                 }
 556             }
 557           else
 558             {
 559               digit = 1;
 560               community_low *= 10;
 561               community_low += (*p - '0');
 562             }
 563           p++;
 564         }
 565       if (! digit)
 566         {
 567           *token = community_token_unknown;
 568           return NULL;
 569         }
 570       *val = community_high + community_low;
 571       *token = community_token_val;
 572       return p;
 573     }
 574   *token = community_token_unknown;
 575   return NULL;
 576 }
 577
 578 /* convert string to community structure */
 579 struct community *
 580 community_str2com (const char *str)
 581 {
 582   struct community *com = NULL;
 583   struct community *com_sort = NULL;
 584   u_int32_t val = 0;
 585   enum community_token token = community_token_unknown;
 586
 587   do
 588     {
 589       str = community_gettoken (str, &token, &val);
 590
 591       switch (token)
 592         {
 593         case community_token_val:
 594         case community_token_no_export:
 595         case community_token_no_advertise:
 596         case community_token_local_as:
 597           if (com == NULL)
 598             com = community_new();
 599           community_add_val (com, val);
 600           break;
 601         case community_token_unknown:
 602         default:
 603           if (com)
 604             community_free (com);
 605           return NULL;
 606         }
 607     } while (str);
 608
 609   if (! com)
 610     return NULL;
 611
 612   com_sort = community_uniq_sort (com);
 613   community_free (com);
 614
 615   return com_sort;
 616 }
 617
 618 /* Return communities hash entry count.  */
 619 unsigned long
 620 community_count (void)
 621 {
 622   return comhash->count;
 623 }
 624
 625 /* Return communities hash.  */
 626 struct hash *
 627 community_hash (void)
 628 {
 629   return comhash;
 630 }
 631
 632 /* Initialize comminity related hash. */
 633 void
 634 community_init (void)
 635 {
 636   comhash = hash_create ((unsigned int (*) (void *))community_hash_make,
 637                          (int (*) (const void *, const void *))community_cmp);
 638 }
 639
 640 void
 641 community_finish (void)
 642 {
 643   hash_free (comhash);
 644   comhash = NULL;
 645 }