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