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 struct hash *ecomhash;
  34 \f
  35 /* Allocate a new ecommunities.  */
  36 struct ecommunity *
  37 ecommunity_new ()
  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    Exteneded 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 (void *arg1, void *arg2)
 251 {
 252   const struct ecommunity *ecom1 = arg1;
 253   const struct ecommunity *ecom2 = arg2;
 254
 255   if (ecom1->size == ecom2->size
 256       && memcmp (ecom1->val, ecom2->val, ecom1->size * ECOMMUNITY_SIZE) == 0)
 257     return 1;
 258   return 0;
 259 }
 260
 261 /* Initialize Extended Comminities related hash. */
 262 void
 263 ecommunity_init (void)
 264 {
 265   ecomhash = hash_create (ecommunity_hash_make, ecommunity_cmp);
 266 }
 267 \f
 268 /* Extended Communities token enum. */
 269 enum ecommunity_token
 270 {
 271   ecommunity_token_rt,
 272   ecommunity_token_soo,
 273   ecommunity_token_val,
 274   ecommunity_token_unknown
 275 };
 276
 277 /* Get next Extended Communities token from the string. */
 278 static const char *
 279 ecommunity_gettoken (const char *str, struct ecommunity_val *eval,
 280                      enum ecommunity_token *token)
 281 {
 282   int ret;
 283   int dot = 0;
 284   int digit = 0;
 285   int separator = 0;
 286   const char *p = str;
 287   char *endptr;
 288   struct in_addr ip;
 289   as_t as = 0;
 290   u_int32_t val = 0;
 291   char buf[INET_ADDRSTRLEN + 1];
 292
 293   /* Skip white space. */
 294   while (isspace ((int) *p))
 295     {
 296       p++;
 297       str++;
 298     }
 299
 300   /* Check the end of the line. */
 301   if (*p == '\0')
 302     return NULL;
 303
 304   /* "rt" and "soo" keyword parse. */
 305   if (! isdigit ((int) *p))
 306     {
 307       /* "rt" match check.  */
 308       if (tolower ((int) *p) == 'r')
 309         {
 310           p++;
 311           if (tolower ((int) *p) == 't')
 312             {
 313               p++;
 314               *token = ecommunity_token_rt;
 315               return p;
 316             }
 317           if (isspace ((int) *p) || *p == '\0')
 318             {
 319               *token = ecommunity_token_rt;
 320               return p;
 321             }
 322           goto error;
 323         }
 324       /* "soo" match check.  */
 325       else if (tolower ((int) *p) == 's')
 326         {
 327           p++;
 328           if (tolower ((int) *p) == 'o')
 329             {
 330               p++;
 331               if (tolower ((int) *p) == 'o')
 332                 {
 333                   p++;
 334                   *token = ecommunity_token_soo;
 335                   return p;
 336                 }
 337               if (isspace ((int) *p) || *p == '\0')
 338                 {
 339                   *token = ecommunity_token_soo;
 340                   return p;
 341                 }
 342               goto error;
 343             }
 344           if (isspace ((int) *p) || *p == '\0')
 345             {
 346               *token = ecommunity_token_soo;
 347               return p;
 348             }
 349           goto error;
 350         }
 351       goto error;
 352     }
 353
 354   /* What a mess, there are several possibilities:
 355    *
 356    * a) A.B.C.D:MN
 357    * b) EF:OPQR
 358    * c) GHJK:MN
 359    *
 360    * A.B.C.D: Four Byte IP
 361    * EF:      Two byte ASN
 362    * GHJK:    Four-byte ASN
 363    * MN:      Two byte value
 364    * OPQR:    Four byte value
 365    *
 366    */
 367   while (isdigit ((int) *p) || *p == ':' || *p == '.')
 368     {
 369       if (*p == ':')
 370         {
 371           if (separator)
 372             goto error;
 373
 374           separator = 1;
 375           digit = 0;
 376
 377           if ((p - str) > INET_ADDRSTRLEN)
 378             goto error;
 379           memset (buf, 0, INET_ADDRSTRLEN + 1);
 380           memcpy (buf, str, p - str);
 381
 382           if (dot)
 383             {
 384               /* Parsing A.B.C.D in:
 385                * A.B.C.D:MN
 386                */
 387               ret = inet_aton (buf, &ip);
 388               if (ret == 0)
 389                 goto error;
 390             }
 391           else
 392             {
 393               /* ASN */
 394               as = strtoul (buf, &endptr, 10);
 395               if (*endptr != '\0' || as == BGP_AS4_MAX)
 396                 goto error;
 397             }
 398         }
 399       else if (*p == '.')
 400         {
 401           if (separator)
 402             goto error;
 403           dot++;
 404           if (dot > 4)
 405             goto error;
 406         }
 407       else
 408         {
 409           digit = 1;
 410
 411           /* We're past the IP/ASN part */
 412           if (separator)
 413             {
 414               val *= 10;
 415               val += (*p - '0');
 416             }
 417         }
 418       p++;
 419     }
 420
 421   /* Low digit part must be there. */
 422   if (!digit || !separator)
 423     goto error;
 424
 425   /* Encode result into routing distinguisher.  */
 426   if (dot)
 427     {
 428       if (val > UINT16_MAX)
 429         goto error;
 430
 431       eval->val[0] = ECOMMUNITY_ENCODE_IP;
 432       eval->val[1] = 0;
 433       memcpy (&eval->val[2], &ip, sizeof (struct in_addr));
 434       eval->val[6] = (val >> 8) & 0xff;
 435       eval->val[7] = val & 0xff;
 436     }
 437   else if (as > BGP_AS_MAX)
 438     {
 439       if (val > UINT16_MAX)
 440         goto error;
 441
 442       eval->val[0] = ECOMMUNITY_ENCODE_AS4;
 443       eval->val[1] = 0;
 444       eval->val[2] = (as >>24) & 0xff;
 445       eval->val[3] = (as >>16) & 0xff;
 446       eval->val[4] = (as >>8) & 0xff;
 447       eval->val[5] =  as & 0xff;
 448       eval->val[6] = (val >> 8) & 0xff;
 449       eval->val[7] = val & 0xff;
 450     }
 451   else
 452     {
 453       eval->val[0] = ECOMMUNITY_ENCODE_AS;
 454       eval->val[1] = 0;
 455
 456       eval->val[2] = (as >>8) & 0xff;
 457       eval->val[3] = as & 0xff;
 458       eval->val[4] = (val >>24) & 0xff;
 459       eval->val[5] = (val >>16) & 0xff;
 460       eval->val[6] = (val >>8) & 0xff;
 461       eval->val[7] = val & 0xff;
 462     }
 463   *token = ecommunity_token_val;
 464   return p;
 465
 466  error:
 467   *token = ecommunity_token_unknown;
 468   return p;
 469 }
 470
 471 /* Convert string to extended community attribute.
 472
 473    When type is already known, please specify both str and type.  str
 474    should not include keyword such as "rt" and "soo".  Type is
 475    ECOMMUNITY_ROUTE_TARGET or ECOMMUNITY_SITE_ORIGIN.
 476    keyword_included should be zero.
 477
 478    For example route-map's "set extcommunity" command case:
 479
 480    "rt 100:1 100:2 100:3"        -> str = "100:1 100:2 100:3"
 481                                     type = ECOMMUNITY_ROUTE_TARGET
 482                                     keyword_included = 0
 483
 484    "soo 100:1"                   -> str = "100:1"
 485                                     type = ECOMMUNITY_SITE_ORIGIN
 486                                     keyword_included = 0
 487
 488    When string includes keyword for each extended community value.
 489    Please specify keyword_included as non-zero value.
 490
 491    For example standard extcommunity-list case:
 492
 493    "rt 100:1 rt 100:2 soo 100:1" -> str = "rt 100:1 rt 100:2 soo 100:1"
 494                                     type = 0
 495                                     keyword_include = 1
 496 */
 497 struct ecommunity *
 498 ecommunity_str2com (const char *str, int type, int keyword_included)
 499 {
 500   struct ecommunity *ecom = NULL;
 501   enum ecommunity_token token;
 502   struct ecommunity_val eval;
 503   int keyword = 0;
 504
 505   while ((str = ecommunity_gettoken (str, &eval, &token)))
 506     {
 507       switch (token)
 508         {
 509         case ecommunity_token_rt:
 510         case ecommunity_token_soo:
 511           if (! keyword_included || keyword)
 512             {
 513               if (ecom)
 514                 ecommunity_free (ecom);
 515               return NULL;
 516             }
 517           keyword = 1;
 518
 519           if (token == ecommunity_token_rt)
 520             {
 521               type = ECOMMUNITY_ROUTE_TARGET;
 522             }
 523           if (token == ecommunity_token_soo)
 524             {
 525               type = ECOMMUNITY_SITE_ORIGIN;
 526             }
 527           break;
 528         case ecommunity_token_val:
 529           if (keyword_included)
 530             {
 531               if (! keyword)
 532                 {
 533                   if (ecom)
 534                     ecommunity_free (ecom);
 535                   return NULL;
 536                 }
 537               keyword = 0;
 538             }
 539           if (ecom == NULL)
 540             ecom = ecommunity_new ();
 541           eval.val[1] = type;
 542           ecommunity_add_val (ecom, &eval);
 543           break;
 544         case ecommunity_token_unknown:
 545         default:
 546           if (ecom)
 547             ecommunity_free (ecom);
 548           return NULL;
 549         }
 550     }
 551   return ecom;
 552 }
 553
 554 /* Convert extended community attribute to string.
 555
 556    Due to historical reason of industry standard implementation, there
 557    are three types of format.
 558
 559    route-map set extcommunity format
 560         "rt 100:1 100:2"
 561         "soo 100:3"
 562
 563    extcommunity-list
 564         "rt 100:1 rt 100:2 soo 100:3"
 565
 566    "show ip bgp" and extcommunity-list regular expression matching
 567         "RT:100:1 RT:100:2 SoO:100:3"
 568
 569    For each formath please use below definition for format:
 570
 571    ECOMMUNITY_FORMAT_ROUTE_MAP
 572    ECOMMUNITY_FORMAT_COMMUNITY_LIST
 573    ECOMMUNITY_FORMAT_DISPLAY
 574 */
 575 char *
 576 ecommunity_ecom2str (struct ecommunity *ecom, int format)
 577 {
 578   int i;
 579   u_int8_t *pnt;
 580   int encode = 0;
 581   int type = 0;
 582 #define ECOMMUNITY_STR_DEFAULT_LEN  27
 583   int str_size;
 584   int str_pnt;
 585   char *str_buf;
 586   const char *prefix;
 587   int len = 0;
 588   int first = 1;
 589
 590   /* For parse Extended Community attribute tupple. */
 591   struct ecommunity_as
 592   {
 593     as_t as;
 594     u_int32_t val;
 595   } eas;
 596
 597   struct ecommunity_ip
 598   {
 599     struct in_addr ip;
 600     u_int16_t val;
 601   } eip;
 602
 603   if (ecom->size == 0)
 604     {
 605       str_buf = XMALLOC (MTYPE_ECOMMUNITY_STR, 1);
 606       str_buf[0] = '\0';
 607       return str_buf;
 608     }
 609
 610   /* Prepare buffer.  */
 611   str_buf = XMALLOC (MTYPE_ECOMMUNITY_STR, ECOMMUNITY_STR_DEFAULT_LEN + 1);
 612   str_size = ECOMMUNITY_STR_DEFAULT_LEN + 1;
 613   str_pnt = 0;
 614
 615   for (i = 0; i < ecom->size; i++)
 616     {
 617       /* Space between each value.  */
 618       if (! first)
 619         str_buf[str_pnt++] = ' ';
 620
 621       pnt = ecom->val + (i * 8);
 622
 623       /* High-order octet of type. */
 624       encode = *pnt++;
 625       if (encode != ECOMMUNITY_ENCODE_AS && encode != ECOMMUNITY_ENCODE_IP
 626                       && encode != ECOMMUNITY_ENCODE_AS4)
 627         {
 628           len = sprintf (str_buf + str_pnt, "?");
 629           str_pnt += len;
 630           first = 0;
 631           continue;
 632         }
 633
 634       /* Low-order octet of type. */
 635       type = *pnt++;
 636       if (type !=  ECOMMUNITY_ROUTE_TARGET && type != ECOMMUNITY_SITE_ORIGIN)
 637         {
 638           len = sprintf (str_buf + str_pnt, "?");
 639           str_pnt += len;
 640           first = 0;
 641           continue;
 642         }
 643
 644       switch (format)
 645         {
 646         case ECOMMUNITY_FORMAT_COMMUNITY_LIST:
 647           prefix = (type == ECOMMUNITY_ROUTE_TARGET ? "rt " : "soo ");
 648           break;
 649         case ECOMMUNITY_FORMAT_DISPLAY:
 650           prefix = (type == ECOMMUNITY_ROUTE_TARGET ? "RT:" : "SoO:");
 651           break;
 652         case ECOMMUNITY_FORMAT_ROUTE_MAP:
 653           prefix = "";
 654           break;
 655         default:
 656           prefix = "";
 657           break;
 658         }
 659
 660       /* Make it sure size is enough.  */
 661       while (str_pnt + ECOMMUNITY_STR_DEFAULT_LEN >= str_size)
 662         {
 663           str_size *= 2;
 664           str_buf = XREALLOC (MTYPE_ECOMMUNITY_STR, str_buf, str_size);
 665         }
 666
 667       /* Put string into buffer.  */
 668       if (encode == ECOMMUNITY_ENCODE_AS4)
 669         {
 670           eas.as = (*pnt++ << 24);
 671           eas.as |= (*pnt++ << 16);
 672           eas.as |= (*pnt++ << 8);
 673           eas.as |= (*pnt++);
 674
 675           eas.val = (*pnt++ << 8);
 676           eas.val |= (*pnt++);
 677
 678           len = sprintf( str_buf + str_pnt, "%s%d:%d", prefix,
 679                         eas.as, eas.val );
 680           str_pnt += len;
 681           first = 0;
 682         }
 683       if (encode == ECOMMUNITY_ENCODE_AS)
 684         {
 685           eas.as = (*pnt++ << 8);
 686           eas.as |= (*pnt++);
 687
 688           eas.val = (*pnt++ << 24);
 689           eas.val |= (*pnt++ << 16);
 690           eas.val |= (*pnt++ << 8);
 691           eas.val |= (*pnt++);
 692
 693           len = sprintf (str_buf + str_pnt, "%s%d:%d", prefix,
 694                          eas.as, eas.val);
 695           str_pnt += len;
 696           first = 0;
 697         }
 698       else if (encode == ECOMMUNITY_ENCODE_IP)
 699         {
 700           memcpy (&eip.ip, pnt, 4);
 701           pnt += 4;
 702           eip.val = (*pnt++ << 8);
 703           eip.val |= (*pnt++);
 704
 705           len = sprintf (str_buf + str_pnt, "%s%s:%d", prefix,
 706                          inet_ntoa (eip.ip), eip.val);
 707           str_pnt += len;
 708           first = 0;
 709         }
 710     }
 711   return str_buf;
 712 }
 713
 714 int
 715 ecommunity_match (const struct ecommunity *ecom1,
 716                   const struct ecommunity *ecom2)
 717 {
 718   int i = 0;
 719   int j = 0;
 720
 721   if (ecom1 == NULL && ecom2 == NULL)
 722     return 1;
 723
 724   if (ecom1 == NULL || ecom2 == NULL)
 725     return 0;
 726
 727   if (ecom1->size < ecom2->size)
 728     return 0;
 729
 730   /* Every community on com2 needs to be on com1 for this to match */
 731   while (i < ecom1->size && j < ecom2->size)
 732     {
 733       if (memcmp (ecom1->val + i, ecom2->val + j, ECOMMUNITY_SIZE) == 0)
 734         j++;
 735       i++;
 736     }
 737
 738   if (j == ecom2->size)
 739     return 1;
 740   else
 741     return 0;
 742 }
 743