bgpd/bgp_ecommunity.c

   1 /* BGP Extended Communities Attribute
   2    Copyright (C) 2000 Kunihiro Ishiguro <kunihiro@zebra.org>
   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 #include "prefix.h"
  26 #include "command.h"
  27
  28 #include "bgpd/bgpd.h"
  29 #include "bgpd/bgp_ecommunity.h"
  30 #include "bgpd/bgp_aspath.h"
  31
  32 /* Hash of community attribute. */
  33 static struct hash *ecomhash;
  34 \f
  35 /* Allocate a new ecommunities.  */
  36 static struct ecommunity *
  37 ecommunity_new (void)
  38 {
  39   return (struct ecommunity *) XCALLOC (MTYPE_ECOMMUNITY,
  40                                         sizeof (struct ecommunity));
  41 }
  42
  43 /* Allocate ecommunities.  */
  44 void
  45 ecommunity_free (struct ecommunity *ecom)
  46 {
  47   if (ecom->val)
  48     XFREE (MTYPE_ECOMMUNITY_VAL, ecom->val);
  49   if (ecom->str)
  50     XFREE (MTYPE_ECOMMUNITY_STR, ecom->str);
  51   XFREE (MTYPE_ECOMMUNITY, ecom);
  52 }
  53
  54 /* Add a new Extended Communities value to Extended Communities
  55    Attribute structure.  When the value is already exists in the
  56    structure, we don't add the value.  Newly added value is sorted by
  57    numerical order.  When the value is added to the structure return 1
  58    else return 0.  */
  59 static int
  60 ecommunity_add_val (struct ecommunity *ecom, struct ecommunity_val *eval)
  61 {
  62   u_int8_t *p;
  63   int ret;
  64   int c;
  65
  66   /* When this is fist value, just add it.  */
  67   if (ecom->val == NULL)
  68     {
  69       ecom->size++;
  70       ecom->val = XMALLOC (MTYPE_ECOMMUNITY_VAL, ecom_length (ecom));
  71       memcpy (ecom->val, eval->val, ECOMMUNITY_SIZE);
  72       return 1;
  73     }
  74
  75   /* If the value already exists in the structure return 0.  */
  76   c = 0;
  77   for (p = ecom->val; c < ecom->size; p += ECOMMUNITY_SIZE, c++)
  78     {
  79       ret = memcmp (p, eval->val, ECOMMUNITY_SIZE);
  80       if (ret == 0)
  81         return 0;
  82       if (ret > 0)
  83         break;
  84     }
  85
  86   /* Add the value to the structure with numerical sorting.  */
  87   ecom->size++;
  88   ecom->val = XREALLOC (MTYPE_ECOMMUNITY_VAL, ecom->val, ecom_length (ecom));
  89
  90   memmove (ecom->val + (c + 1) * ECOMMUNITY_SIZE,
  91            ecom->val + c * ECOMMUNITY_SIZE,
  92            (ecom->size - 1 - c) * ECOMMUNITY_SIZE);
  93   memcpy (ecom->val + c * ECOMMUNITY_SIZE, eval->val, ECOMMUNITY_SIZE);
  94
  95   return 1;
  96 }
  97
  98 /* This function takes pointer to Extended Communites strucutre then
  99    create a new Extended Communities structure by uniq and sort each
 100    Extended Communities value.  */
 101 static struct ecommunity *
 102 ecommunity_uniq_sort (struct ecommunity *ecom)
 103 {
 104   int i;
 105   struct ecommunity *new;
 106   struct ecommunity_val *eval;
 107
 108   if (! ecom)
 109     return NULL;
 110
 111   new = ecommunity_new ();
 112
 113   for (i = 0; i < ecom->size; i++)
 114     {
 115       eval = (struct ecommunity_val *) (ecom->val + (i * ECOMMUNITY_SIZE));
 116       ecommunity_add_val (new, eval);
 117     }
 118   return new;
 119 }
 120
 121 /* Parse Extended Communites Attribute in BGP packet.  */
 122 struct ecommunity *
 123 ecommunity_parse (u_int8_t *pnt, u_short length)
 124 {
 125   struct ecommunity tmp;
 126   struct ecommunity *new;
 127
 128   /* Length check.  */
 129   if (length % ECOMMUNITY_SIZE)
 130     return NULL;
 131
 132   /* Prepare tmporary structure for making a new Extended Communities
 133      Attribute.  */
 134   tmp.size = length / ECOMMUNITY_SIZE;
 135   tmp.val = pnt;
 136
 137   /* Create a new Extended Communities Attribute by uniq and sort each
 138      Extended Communities value  */
 139   new = ecommunity_uniq_sort (&tmp);
 140
 141   return ecommunity_intern (new);
 142 }
 143
 144 /* Duplicate the Extended Communities Attribute structure.  */
 145 struct ecommunity *
 146 ecommunity_dup (struct ecommunity *ecom)
 147 {
 148   struct ecommunity *new;
 149
 150   new = XCALLOC (MTYPE_ECOMMUNITY, sizeof (struct ecommunity));
 151   new->size = ecom->size;
 152   if (new->size)
 153     {
 154       new->val = XMALLOC (MTYPE_ECOMMUNITY_VAL, ecom->size * ECOMMUNITY_SIZE);
 155       memcpy (new->val, ecom->val, ecom->size * ECOMMUNITY_SIZE);
 156     }
 157   else
 158     new->val = NULL;
 159   return new;
 160 }
 161
 162 /* Retrun string representation of communities attribute. */
 163 char *
 164 ecommunity_str (struct ecommunity *ecom)
 165 {
 166   if (! ecom->str)
 167     ecom->str = ecommunity_ecom2str (ecom, ECOMMUNITY_FORMAT_DISPLAY);
 168   return ecom->str;
 169 }
 170
 171 /* Merge two Extended Communities Attribute structure.  */
 172 struct ecommunity *
 173 ecommunity_merge (struct ecommunity *ecom1, struct ecommunity *ecom2)
 174 {
 175   if (ecom1->val)
 176     ecom1->val = XREALLOC (MTYPE_ECOMMUNITY_VAL, ecom1->val,
 177                            (ecom1->size + ecom2->size) * ECOMMUNITY_SIZE);
 178   else
 179     ecom1->val = XMALLOC (MTYPE_ECOMMUNITY_VAL,
 180                           (ecom1->size + ecom2->size) * ECOMMUNITY_SIZE);
 181
 182   memcpy (ecom1->val + (ecom1->size * ECOMMUNITY_SIZE),
 183           ecom2->val, ecom2->size * ECOMMUNITY_SIZE);
 184   ecom1->size += ecom2->size;
 185
 186   return ecom1;
 187 }
 188
 189 /* Intern Extended Communities Attribute.  */
 190 struct ecommunity *
 191 ecommunity_intern (struct ecommunity *ecom)
 192 {
 193   struct ecommunity *find;
 194
 195   assert (ecom->refcnt == 0);
 196
 197   find = (struct ecommunity *) hash_get (ecomhash, ecom, hash_alloc_intern);
 198
 199   if (find != ecom)
 200     ecommunity_free (ecom);
 201
 202   find->refcnt++;
 203
 204   if (! find->str)
 205     find->str = ecommunity_ecom2str (find, ECOMMUNITY_FORMAT_DISPLAY);
 206
 207   return find;
 208 }
 209
 210 /* Unintern Extended Communities Attribute.  */
 211 void
 212 ecommunity_unintern (struct ecommunity *ecom)
 213 {
 214   struct ecommunity *ret;
 215
 216   if (ecom->refcnt)
 217     ecom->refcnt--;
 218
 219   /* Pull off from hash.  */
 220   if (ecom->refcnt == 0)
 221     {
 222       /* Extended community must be in the hash.  */
 223       ret = (struct ecommunity *) hash_release (ecomhash, ecom);
 224       assert (ret != NULL);
 225
 226       ecommunity_free (ecom);
 227     }
 228 }
 229
 230 /* Utinity function to make hash key.  */
 231 unsigned int
 232 ecommunity_hash_make (void *arg)
 233 {
 234   const struct ecommunity *ecom = arg;
 235   int c;
 236   unsigned int key;
 237   u_int8_t *pnt;
 238
 239   key = 0;
 240   pnt = ecom->val;
 241
 242   for (c = 0; c < ecom->size * ECOMMUNITY_SIZE; c++)
 243     key += pnt[c];
 244
 245   return key;
 246 }
 247
 248 /* Compare two Extended Communities Attribute structure.  */
 249 int
 250 ecommunity_cmp (const void *arg1, const void *arg2)
 251 {
 252   const struct ecommunity *ecom1 = arg1;
 253   const struct ecommunity *ecom2 = arg2;
 254
 255   return (ecom1->size == ecom2->size
 256           && memcmp (ecom1->val, ecom2->val, ecom1->size * ECOMMUNITY_SIZE) == 0);
 257 }
 258
 259 /* Initialize Extended Comminities related hash. */
 260 void
 261 ecommunity_init (void)
 262 {
 263   ecomhash = hash_create (ecommunity_hash_make, ecommunity_cmp);
 264 }
 265 \f
 266 /* Extended Communities token enum. */
 267 enum ecommunity_token
 268 {
 269   ecommunity_token_rt,
 270   ecommunity_token_soo,
 271   ecommunity_token_val,
 272   ecommunity_token_unknown
 273 };
 274
 275 /* Get next Extended Communities token from the string. */
 276 static const char *
 277 ecommunity_gettoken (const char *str, struct ecommunity_val *eval,
 278                      enum ecommunity_token *token)
 279 {
 280   int ret;
 281   int dot = 0;
 282   int digit = 0;
 283   int separator = 0;
 284   const char *p = str;
 285   char *endptr;
 286   struct in_addr ip;
 287   as_t as = 0;
 288   u_int32_t val = 0;
 289   char buf[INET_ADDRSTRLEN + 1];
 290
 291   /* Skip white space. */
 292   while (isspace ((int) *p))
 293     {
 294       p++;
 295       str++;
 296     }
 297
 298   /* Check the end of the line. */
 299   if (*p == '\0')
 300     return NULL;
 301
 302   /* "rt" and "soo" keyword parse. */
 303   if (! isdigit ((int) *p))
 304     {
 305       /* "rt" match check.  */
 306       if (tolower ((int) *p) == 'r')
 307         {
 308           p++;
 309           if (tolower ((int) *p) == 't')
 310             {
 311               p++;
 312               *token = ecommunity_token_rt;
 313               return p;
 314             }
 315           if (isspace ((int) *p) || *p == '\0')
 316             {
 317               *token = ecommunity_token_rt;
 318               return p;
 319             }
 320           goto error;
 321         }
 322       /* "soo" match check.  */
 323       else if (tolower ((int) *p) == 's')
 324         {
 325           p++;
 326           if (tolower ((int) *p) == 'o')
 327             {
 328               p++;
 329               if (tolower ((int) *p) == 'o')
 330                 {
 331                   p++;
 332                   *token = ecommunity_token_soo;
 333                   return p;
 334                 }
 335               if (isspace ((int) *p) || *p == '\0')
 336                 {
 337                   *token = ecommunity_token_soo;
 338                   return p;
 339                 }
 340               goto error;
 341             }
 342           if (isspace ((int) *p) || *p == '\0')
 343             {
 344               *token = ecommunity_token_soo;
 345               return p;
 346             }
 347           goto error;
 348         }
 349       goto error;
 350     }
 351
 352   /* What a mess, there are several possibilities:
 353    *
 354    * a) A.B.C.D:MN
 355    * b) EF:OPQR
 356    * c) GHJK:MN
 357    *
 358    * A.B.C.D: Four Byte IP
 359    * EF:      Two byte ASN
 360    * GHJK:    Four-byte ASN
 361    * MN:      Two byte value
 362    * OPQR:    Four byte value
 363    *
 364    */
 365   while (isdigit ((int) *p) || *p == ':' || *p == '.')
 366     {
 367       if (*p == ':')
 368         {
 369           if (separator)
 370             goto error;
 371
 372           separator = 1;
 373           digit = 0;
 374
 375           if ((p - str) > INET_ADDRSTRLEN)
 376             goto error;
 377           memset (buf, 0, INET_ADDRSTRLEN + 1);
 378           memcpy (buf, str, p - str);
 379
 380           if (dot)
 381             {
 382               /* Parsing A.B.C.D in:
 383                * A.B.C.D:MN
 384                */
 385               ret = inet_aton (buf, &ip);
 386               if (ret == 0)
 387                 goto error;
 388             }
 389           else
 390             {
 391               /* ASN */
 392               as = strtoul (buf, &endptr, 10);
 393               if (*endptr != '\0' || as == BGP_AS4_MAX)
 394                 goto error;
 395             }
 396         }
 397       else if (*p == '.')
 398         {
 399           if (separator)
 400             goto error;
 401           dot++;
 402           if (dot > 4)
 403             goto error;
 404         }
 405       else
 406         {
 407           digit = 1;
 408
 409           /* We're past the IP/ASN part */
 410           if (separator)
 411             {
 412               val *= 10;
 413               val += (*p - '0');
 414             }
 415         }
 416       p++;
 417     }
 418
 419   /* Low digit part must be there. */
 420   if (!digit || !separator)
 421     goto error;
 422
 423   /* Encode result into routing distinguisher.  */
 424   if (dot)
 425     {
 426       if (val > UINT16_MAX)
 427         goto error;
 428
 429       eval->val[0] = ECOMMUNITY_ENCODE_IP;
 430       eval->val[1] = 0;
 431       memcpy (&eval->val[2], &ip, sizeof (struct in_addr));
 432       eval->val[6] = (val >> 8) & 0xff;
 433       eval->val[7] = val & 0xff;
 434     }
 435   else if (as > BGP_AS_MAX)
 436     {
 437       if (val > UINT16_MAX)
 438         goto error;
 439
 440       eval->val[0] = ECOMMUNITY_ENCODE_AS4;
 441       eval->val[1] = 0;
 442       eval->val[2] = (as >>24) & 0xff;
 443       eval->val[3] = (as >>16) & 0xff;
 444       eval->val[4] = (as >>8) & 0xff;
 445       eval->val[5] =  as & 0xff;
 446       eval->val[6] = (val >> 8) & 0xff;
 447       eval->val[7] = val & 0xff;
 448     }
 449   else
 450     {
 451       eval->val[0] = ECOMMUNITY_ENCODE_AS;
 452       eval->val[1] = 0;
 453
 454       eval->val[2] = (as >>8) & 0xff;
 455       eval->val[3] = as & 0xff;
 456       eval->val[4] = (val >>24) & 0xff;
 457       eval->val[5] = (val >>16) & 0xff;
 458       eval->val[6] = (val >>8) & 0xff;
 459       eval->val[7] = val & 0xff;
 460     }
 461   *token = ecommunity_token_val;
 462   return p;
 463
 464  error:
 465   *token = ecommunity_token_unknown;
 466   return p;
 467 }
 468
 469 /* Convert string to extended community attribute.
 470
 471    When type is already known, please specify both str and type.  str
 472    should not include keyword such as "rt" and "soo".  Type is
 473    ECOMMUNITY_ROUTE_TARGET or ECOMMUNITY_SITE_ORIGIN.
 474    keyword_included should be zero.
 475
 476    For example route-map's "set extcommunity" command case:
 477
 478    "rt 100:1 100:2 100:3"        -> str = "100:1 100:2 100:3"
 479                                     type = ECOMMUNITY_ROUTE_TARGET
 480                                     keyword_included = 0
 481
 482    "soo 100:1"                   -> str = "100:1"
 483                                     type = ECOMMUNITY_SITE_ORIGIN
 484                                     keyword_included = 0
 485
 486    When string includes keyword for each extended community value.
 487    Please specify keyword_included as non-zero value.
 488
 489    For example standard extcommunity-list case:
 490
 491    "rt 100:1 rt 100:2 soo 100:1" -> str = "rt 100:1 rt 100:2 soo 100:1"
 492                                     type = 0
 493                                     keyword_include = 1
 494 */
 495 struct ecommunity *
 496 ecommunity_str2com (const char *str, int type, int keyword_included)
 497 {
 498   struct ecommunity *ecom = NULL;
 499   enum ecommunity_token token;
 500   struct ecommunity_val eval;
 501   int keyword = 0;
 502
 503   while ((str = ecommunity_gettoken (str, &eval, &token)))
 504     {
 505       switch (token)
 506         {
 507         case ecommunity_token_rt:
 508         case ecommunity_token_soo:
 509           if (! keyword_included || keyword)
 510             {
 511               if (ecom)
 512                 ecommunity_free (ecom);
 513               return NULL;
 514             }
 515           keyword = 1;
 516
 517           if (token == ecommunity_token_rt)
 518             {
 519               type = ECOMMUNITY_ROUTE_TARGET;
 520             }
 521           if (token == ecommunity_token_soo)
 522             {
 523               type = ECOMMUNITY_SITE_ORIGIN;
 524             }
 525           break;
 526         case ecommunity_token_val:
 527           if (keyword_included)
 528             {
 529               if (! keyword)
 530                 {
 531                   if (ecom)
 532                     ecommunity_free (ecom);
 533                   return NULL;
 534                 }
 535               keyword = 0;
 536             }
 537           if (ecom == NULL)
 538             ecom = ecommunity_new ();
 539           eval.val[1] = type;
 540           ecommunity_add_val (ecom, &eval);
 541           break;
 542         case ecommunity_token_unknown:
 543         default:
 544           if (ecom)
 545             ecommunity_free (ecom);
 546           return NULL;
 547         }
 548     }
 549   return ecom;
 550 }
 551
 552 /* Convert extended community attribute to string.
 553
 554    Due to historical reason of industry standard implementation, there
 555    are three types of format.
 556
 557    route-map set extcommunity format
 558         "rt 100:1 100:2"
 559         "soo 100:3"
 560
 561    extcommunity-list
 562         "rt 100:1 rt 100:2 soo 100:3"
 563
 564    "show ip bgp" and extcommunity-list regular expression matching
 565         "RT:100:1 RT:100:2 SoO:100:3"
 566
 567    For each formath please use below definition for format:
 568
 569    ECOMMUNITY_FORMAT_ROUTE_MAP
 570    ECOMMUNITY_FORMAT_COMMUNITY_LIST
 571    ECOMMUNITY_FORMAT_DISPLAY
 572 */
 573 char *
 574 ecommunity_ecom2str (struct ecommunity *ecom, int format)
 575 {
 576   int i;
 577   u_int8_t *pnt;
 578   int encode = 0;
 579   int type = 0;
 580 #define ECOMMUNITY_STR_DEFAULT_LEN  27
 581   int str_size;
 582   int str_pnt;
 583   char *str_buf;
 584   const char *prefix;
 585   int len = 0;
 586   int first = 1;
 587
 588   /* For parse Extended Community attribute tupple. */
 589   struct ecommunity_as
 590   {
 591     as_t as;
 592     u_int32_t val;
 593   } eas;
 594
 595   struct ecommunity_ip
 596   {
 597     struct in_addr ip;
 598     u_int16_t val;
 599   } eip;
 600
 601   if (ecom->size == 0)
 602     {
 603       str_buf = XMALLOC (MTYPE_ECOMMUNITY_STR, 1);
 604       str_buf[0] = '\0';
 605       return str_buf;
 606     }
 607
 608   /* Prepare buffer.  */
 609   str_buf = XMALLOC (MTYPE_ECOMMUNITY_STR, ECOMMUNITY_STR_DEFAULT_LEN + 1);
 610   str_size = ECOMMUNITY_STR_DEFAULT_LEN + 1;
 611   str_pnt = 0;
 612
 613   for (i = 0; i < ecom->size; i++)
 614     {
 615       /* Space between each value.  */
 616       if (! first)
 617         str_buf[str_pnt++] = ' ';
 618
 619       pnt = ecom->val + (i * 8);
 620
 621       /* High-order octet of type. */
 622       encode = *pnt++;
 623       if (encode != ECOMMUNITY_ENCODE_AS && encode != ECOMMUNITY_ENCODE_IP
 624                       && encode != ECOMMUNITY_ENCODE_AS4)
 625         {
 626           len = sprintf (str_buf + str_pnt, "?");
 627           str_pnt += len;
 628           first = 0;
 629           continue;
 630         }
 631
 632       /* Low-order octet of type. */
 633       type = *pnt++;
 634       if (type !=  ECOMMUNITY_ROUTE_TARGET && type != ECOMMUNITY_SITE_ORIGIN)
 635         {
 636           len = sprintf (str_buf + str_pnt, "?");
 637           str_pnt += len;
 638           first = 0;
 639           continue;
 640         }
 641
 642       switch (format)
 643         {
 644         case ECOMMUNITY_FORMAT_COMMUNITY_LIST:
 645           prefix = (type == ECOMMUNITY_ROUTE_TARGET ? "rt " : "soo ");
 646           break;
 647         case ECOMMUNITY_FORMAT_DISPLAY:
 648           prefix = (type == ECOMMUNITY_ROUTE_TARGET ? "RT:" : "SoO:");
 649           break;
 650         case ECOMMUNITY_FORMAT_ROUTE_MAP:
 651           prefix = "";
 652           break;
 653         default:
 654           prefix = "";
 655           break;
 656         }
 657
 658       /* Make it sure size is enough.  */
 659       while (str_pnt + ECOMMUNITY_STR_DEFAULT_LEN >= str_size)
 660         {
 661           str_size *= 2;
 662           str_buf = XREALLOC (MTYPE_ECOMMUNITY_STR, str_buf, str_size);
 663         }
 664
 665       /* Put string into buffer.  */
 666       if (encode == ECOMMUNITY_ENCODE_AS4)
 667         {
 668           eas.as = (*pnt++ << 24);
 669           eas.as |= (*pnt++ << 16);
 670           eas.as |= (*pnt++ << 8);
 671           eas.as |= (*pnt++);
 672
 673           eas.val = (*pnt++ << 8);
 674           eas.val |= (*pnt++);
 675
 676           len = sprintf( str_buf + str_pnt, "%s%u:%d", prefix,
 677                         eas.as, eas.val );
 678           str_pnt += len;
 679           first = 0;
 680         }
 681       if (encode == ECOMMUNITY_ENCODE_AS)
 682         {
 683           eas.as = (*pnt++ << 8);
 684           eas.as |= (*pnt++);
 685
 686           eas.val = (*pnt++ << 24);
 687           eas.val |= (*pnt++ << 16);
 688           eas.val |= (*pnt++ << 8);
 689           eas.val |= (*pnt++);
 690
 691           len = sprintf (str_buf + str_pnt, "%s%u:%d", prefix,
 692                          eas.as, eas.val);
 693           str_pnt += len;
 694           first = 0;
 695         }
 696       else if (encode == ECOMMUNITY_ENCODE_IP)
 697         {
 698           memcpy (&eip.ip, pnt, 4);
 699           pnt += 4;
 700           eip.val = (*pnt++ << 8);
 701           eip.val |= (*pnt++);
 702
 703           len = sprintf (str_buf + str_pnt, "%s%s:%d", prefix,
 704                          inet_ntoa (eip.ip), eip.val);
 705           str_pnt += len;
 706           first = 0;
 707         }
 708     }
 709   return str_buf;
 710 }
 711
 712 int
 713 ecommunity_match (const struct ecommunity *ecom1,
 714                   const struct ecommunity *ecom2)
 715 {
 716   int i = 0;
 717   int j = 0;
 718
 719   if (ecom1 == NULL && ecom2 == NULL)
 720     return 1;
 721
 722   if (ecom1 == NULL || ecom2 == NULL)
 723     return 0;
 724
 725   if (ecom1->size < ecom2->size)
 726     return 0;
 727
 728   /* Every community on com2 needs to be on com1 for this to match */
 729   while (i < ecom1->size && j < ecom2->size)
 730     {
 731       if (memcmp (ecom1->val + i, ecom2->val + j, ECOMMUNITY_SIZE) == 0)
 732         j++;
 733       i++;
 734     }
 735
 736   if (j == ecom2->size)
 737     return 1;
 738   else
 739     return 0;
 740 }
 741