bgpd/bgp_lcommunity.c

   1 /* BGP Large Communities Attribute
   2  *
   3  * Copyright (C) 2016 Keyur Patel <keyur@arrcus.com>
   4  *
   5  * This file is part of FreeRangeRouting (FRR).
   6  *
   7  * FRR is free software; you can redistribute it and/or modify it under the
   8  * terms of the GNU General Public License as published by the Free Software
   9  * Foundation; either version 2, or (at your option) any later version.
  10  *
  11  * FRR is distributed in the hope that it will be useful, but WITHOUT ANY
  12  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  13  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  14  * details.
  15  *
  16  * You should have received a copy of the GNU General Public License along
  17  * with this program; see the file COPYING; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20
  21 #include <zebra.h>
  22
  23 #include "hash.h"
  24 #include "memory.h"
  25 #include "prefix.h"
  26 #include "command.h"
  27 #include "filter.h"
  28
  29 #include "bgpd/bgpd.h"
  30 #include "bgpd/bgp_lcommunity.h"
  31 #include "bgpd/bgp_aspath.h"
  32
  33 /* Hash of community attribute. */
  34 static struct hash *lcomhash;
  35
  36 /* Allocate a new lcommunities.  */
  37 static struct lcommunity *lcommunity_new(void)
  38 {
  39         return (struct lcommunity *)XCALLOC(MTYPE_LCOMMUNITY,
  40                                             sizeof(struct lcommunity));
  41 }
  42
  43 /* Allocate lcommunities.  */
  44 void lcommunity_free(struct lcommunity **lcom)
  45 {
  46         if ((*lcom)->val)
  47                 XFREE(MTYPE_LCOMMUNITY_VAL, (*lcom)->val);
  48         if ((*lcom)->str)
  49                 XFREE(MTYPE_LCOMMUNITY_STR, (*lcom)->str);
  50         XFREE(MTYPE_LCOMMUNITY, *lcom);
  51         lcom = NULL;
  52 }
  53
  54 static void lcommunity_hash_free(struct lcommunity *lcom)
  55 {
  56         lcommunity_free(&lcom);
  57 }
  58
  59 /* Add a new Large Communities value to Large Communities
  60    Attribute structure.  When the value is already exists in the
  61    structure, we don't add the value.  Newly added value is sorted by
  62    numerical order.  When the value is added to the structure return 1
  63    else return 0.  */
  64 static int lcommunity_add_val(struct lcommunity *lcom,
  65                               struct lcommunity_val *lval)
  66 {
  67         u_int8_t *p;
  68         int ret;
  69         int c;
  70
  71         /* When this is fist value, just add it.  */
  72         if (lcom->val == NULL) {
  73                 lcom->size++;
  74                 lcom->val = XMALLOC(MTYPE_LCOMMUNITY_VAL, lcom_length(lcom));
  75                 memcpy(lcom->val, lval->val, LCOMMUNITY_SIZE);
  76                 return 1;
  77         }
  78
  79         /* If the value already exists in the structure return 0.  */
  80         c = 0;
  81         for (p = lcom->val; c < lcom->size; p += LCOMMUNITY_SIZE, c++) {
  82                 ret = memcmp(p, lval->val, LCOMMUNITY_SIZE);
  83                 if (ret == 0)
  84                         return 0;
  85                 if (ret > 0)
  86                         break;
  87         }
  88
  89         /* Add the value to the structure with numerical sorting.  */
  90         lcom->size++;
  91         lcom->val =
  92                 XREALLOC(MTYPE_LCOMMUNITY_VAL, lcom->val, lcom_length(lcom));
  93
  94         memmove(lcom->val + (c + 1) * LCOMMUNITY_SIZE,
  95                 lcom->val + c * LCOMMUNITY_SIZE,
  96                 (lcom->size - 1 - c) * LCOMMUNITY_SIZE);
  97         memcpy(lcom->val + c * LCOMMUNITY_SIZE, lval->val, LCOMMUNITY_SIZE);
  98
  99         return 1;
 100 }
 101
 102 /* This function takes pointer to Large Communites strucutre then
 103    create a new Large Communities structure by uniq and sort each
 104    Large Communities value.  */
 105 struct lcommunity *lcommunity_uniq_sort(struct lcommunity *lcom)
 106 {
 107         int i;
 108         struct lcommunity *new;
 109         struct lcommunity_val *lval;
 110
 111         if (!lcom)
 112                 return NULL;
 113
 114         new = lcommunity_new();
 115
 116         for (i = 0; i < lcom->size; i++) {
 117                 lval = (struct lcommunity_val *)(lcom->val
 118                                                  + (i * LCOMMUNITY_SIZE));
 119                 lcommunity_add_val(new, lval);
 120         }
 121         return new;
 122 }
 123
 124 /* Parse Large Communites Attribute in BGP packet.  */
 125 struct lcommunity *lcommunity_parse(u_int8_t *pnt, u_short length)
 126 {
 127         struct lcommunity tmp;
 128         struct lcommunity *new;
 129
 130         /* Length check.  */
 131         if (length % LCOMMUNITY_SIZE)
 132                 return NULL;
 133
 134         /* Prepare tmporary structure for making a new Large Communities
 135            Attribute.  */
 136         tmp.size = length / LCOMMUNITY_SIZE;
 137         tmp.val = pnt;
 138
 139         /* Create a new Large Communities Attribute by uniq and sort each
 140            Large Communities value  */
 141         new = lcommunity_uniq_sort(&tmp);
 142
 143         return lcommunity_intern(new);
 144 }
 145
 146 /* Duplicate the Large Communities Attribute structure.  */
 147 struct lcommunity *lcommunity_dup(struct lcommunity *lcom)
 148 {
 149         struct lcommunity *new;
 150
 151         new = XCALLOC(MTYPE_LCOMMUNITY, sizeof(struct lcommunity));
 152         new->size = lcom->size;
 153         if (new->size) {
 154                 new->val = XMALLOC(MTYPE_LCOMMUNITY_VAL,
 155                                    lcom->size * LCOMMUNITY_SIZE);
 156                 memcpy(new->val, lcom->val, lcom->size * LCOMMUNITY_SIZE);
 157         } else
 158                 new->val = NULL;
 159         return new;
 160 }
 161
 162 /* Retrun string representation of communities attribute. */
 163 char *lcommunity_str(struct lcommunity *lcom)
 164 {
 165         if (!lcom->str)
 166                 lcom->str =
 167                         lcommunity_lcom2str(lcom, LCOMMUNITY_FORMAT_DISPLAY);
 168         return lcom->str;
 169 }
 170
 171 /* Merge two Large Communities Attribute structure.  */
 172 struct lcommunity *lcommunity_merge(struct lcommunity *lcom1,
 173                                     struct lcommunity *lcom2)
 174 {
 175         if (lcom1->val)
 176                 lcom1->val =
 177                         XREALLOC(MTYPE_LCOMMUNITY_VAL, lcom1->val,
 178                                  (lcom1->size + lcom2->size) * LCOMMUNITY_SIZE);
 179         else
 180                 lcom1->val =
 181                         XMALLOC(MTYPE_LCOMMUNITY_VAL,
 182                                 (lcom1->size + lcom2->size) * LCOMMUNITY_SIZE);
 183
 184         memcpy(lcom1->val + (lcom1->size * LCOMMUNITY_SIZE), lcom2->val,
 185                lcom2->size * LCOMMUNITY_SIZE);
 186         lcom1->size += lcom2->size;
 187
 188         return lcom1;
 189 }
 190
 191 /* Intern Large Communities Attribute.  */
 192 struct lcommunity *lcommunity_intern(struct lcommunity *lcom)
 193 {
 194         struct lcommunity *find;
 195
 196         assert(lcom->refcnt == 0);
 197
 198         find = (struct lcommunity *)hash_get(lcomhash, lcom, hash_alloc_intern);
 199
 200         if (find != lcom)
 201                 lcommunity_free(&lcom);
 202
 203         find->refcnt++;
 204
 205         if (!find->str)
 206                 find->str =
 207                         lcommunity_lcom2str(find, LCOMMUNITY_FORMAT_DISPLAY);
 208
 209         return find;
 210 }
 211
 212 /* Unintern Large Communities Attribute.  */
 213 void lcommunity_unintern(struct lcommunity **lcom)
 214 {
 215         struct lcommunity *ret;
 216
 217         if ((*lcom)->refcnt)
 218                 (*lcom)->refcnt--;
 219
 220         /* Pull off from hash.  */
 221         if ((*lcom)->refcnt == 0) {
 222                 /* Large community must be in the hash.  */
 223                 ret = (struct lcommunity *)hash_release(lcomhash, *lcom);
 224                 assert(ret != NULL);
 225
 226                 lcommunity_free(lcom);
 227         }
 228 }
 229
 230 /* Utility function to make hash key.  */
 231 unsigned int lcommunity_hash_make(void *arg)
 232 {
 233         const struct lcommunity *lcom = arg;
 234         int size = lcom->size * LCOMMUNITY_SIZE;
 235         u_int8_t *pnt = lcom->val;
 236         unsigned int key = 0;
 237         int c;
 238
 239         for (c = 0; c < size; c += LCOMMUNITY_SIZE) {
 240                 key += pnt[c];
 241                 key += pnt[c + 1];
 242                 key += pnt[c + 2];
 243                 key += pnt[c + 3];
 244                 key += pnt[c + 4];
 245                 key += pnt[c + 5];
 246                 key += pnt[c + 6];
 247                 key += pnt[c + 7];
 248                 key += pnt[c + 8];
 249                 key += pnt[c + 9];
 250                 key += pnt[c + 10];
 251                 key += pnt[c + 11];
 252         }
 253
 254         return key;
 255 }
 256
 257 /* Compare two Large Communities Attribute structure.  */
 258 int lcommunity_cmp(const void *arg1, const void *arg2)
 259 {
 260         const struct lcommunity *lcom1 = arg1;
 261         const struct lcommunity *lcom2 = arg2;
 262
 263         return (lcom1->size == lcom2->size
 264                 && memcmp(lcom1->val, lcom2->val, lcom1->size * LCOMMUNITY_SIZE)
 265                            == 0);
 266 }
 267
 268 /* Return communities hash.  */
 269 struct hash *lcommunity_hash(void)
 270 {
 271         return lcomhash;
 272 }
 273
 274 /* Initialize Large Comminities related hash. */
 275 void lcommunity_init(void)
 276 {
 277         lcomhash = hash_create(lcommunity_hash_make, lcommunity_cmp, NULL);
 278 }
 279
 280 void lcommunity_finish(void)
 281 {
 282         hash_clean(lcomhash, (void (*)(void *))lcommunity_hash_free);
 283         hash_free(lcomhash);
 284         lcomhash = NULL;
 285 }
 286
 287 /* Large Communities token enum. */
 288 enum lcommunity_token {
 289         lcommunity_token_unknown = 0,
 290         lcommunity_token_val,
 291 };
 292
 293 /* Get next Large Communities token from the string. */
 294 static const char *lcommunity_gettoken(const char *str,
 295                                        struct lcommunity_val *lval,
 296                                        enum lcommunity_token *token)
 297 {
 298         const char *p = str;
 299
 300         /* Skip white space. */
 301         while (isspace((int)*p)) {
 302                 p++;
 303                 str++;
 304         }
 305
 306         /* Check the end of the line. */
 307         if (*p == '\0')
 308                 return NULL;
 309
 310         /* Community value. */
 311         if (isdigit((int)*p)) {
 312                 int separator = 0;
 313                 int digit = 0;
 314                 u_int32_t globaladmin = 0;
 315                 u_int32_t localdata1 = 0;
 316                 u_int32_t localdata2 = 0;
 317
 318                 while (isdigit((int)*p) || *p == ':') {
 319                         if (*p == ':') {
 320                                 if (separator == 2) {
 321                                         *token = lcommunity_token_unknown;
 322                                         return NULL;
 323                                 } else {
 324                                         separator++;
 325                                         digit = 0;
 326                                         if (separator == 1) {
 327                                                 globaladmin = localdata2;
 328                                         } else {
 329                                                 localdata1 = localdata2;
 330                                         }
 331                                         localdata2 = 0;
 332                                 }
 333                         } else {
 334                                 digit = 1;
 335                                 localdata2 *= 10;
 336                                 localdata2 += (*p - '0');
 337                         }
 338                         p++;
 339                 }
 340                 if (!digit) {
 341                         *token = lcommunity_token_unknown;
 342                         return NULL;
 343                 }
 344
 345                 /*
 346                  * Copy the large comm.
 347                  */
 348                 lval->val[0] = (globaladmin >> 24) & 0xff;
 349                 lval->val[1] = (globaladmin >> 16) & 0xff;
 350                 lval->val[2] = (globaladmin >> 8) & 0xff;
 351                 lval->val[3] = globaladmin & 0xff;
 352                 lval->val[4] = (localdata1 >> 24) & 0xff;
 353                 lval->val[5] = (localdata1 >> 16) & 0xff;
 354                 lval->val[6] = (localdata1 >> 8) & 0xff;
 355                 lval->val[7] = localdata1 & 0xff;
 356                 lval->val[8] = (localdata2 >> 24) & 0xff;
 357                 lval->val[9] = (localdata2 >> 16) & 0xff;
 358                 lval->val[10] = (localdata2 >> 8) & 0xff;
 359                 lval->val[11] = localdata2 & 0xff;
 360
 361                 *token = lcommunity_token_val;
 362                 return p;
 363         }
 364         *token = lcommunity_token_unknown;
 365         return p;
 366 }
 367
 368 /*
 369   Convert string to large community attribute.
 370   When type is already known, please specify both str and type.
 371
 372   When string includes keyword for each large community value.
 373   Please specify keyword_included as non-zero value.
 374 */
 375 struct lcommunity *lcommunity_str2com(const char *str)
 376 {
 377         struct lcommunity *lcom = NULL;
 378         enum lcommunity_token token = lcommunity_token_unknown;
 379         struct lcommunity_val lval;
 380
 381         while ((str = lcommunity_gettoken(str, &lval, &token))) {
 382                 switch (token) {
 383                 case lcommunity_token_val:
 384                         if (lcom == NULL)
 385                                 lcom = lcommunity_new();
 386                         lcommunity_add_val(lcom, &lval);
 387                         break;
 388                 case lcommunity_token_unknown:
 389                 default:
 390                         if (lcom)
 391                                 lcommunity_free(&lcom);
 392                         return NULL;
 393                 }
 394         }
 395         return lcom;
 396 }
 397
 398 int lcommunity_include(struct lcommunity *lcom, u_char *ptr)
 399 {
 400         int i;
 401         u_char *lcom_ptr;
 402
 403         lcom_ptr = lcom->val;
 404         for (i = 0; i < lcom->size; i++) {
 405                 lcom_ptr += (i * LCOMMUNITY_SIZE);
 406                 if (memcmp(ptr, lcom_ptr, LCOMMUNITY_SIZE) == 0)
 407                         return 1;
 408         }
 409         return 0;
 410 }
 411
 412 /* Convert large community attribute to string.
 413    The large coms will be in 65535:65531:0 format.
 414 */
 415 char *lcommunity_lcom2str(struct lcommunity *lcom, int format)
 416 {
 417         int i;
 418         u_int8_t *pnt;
 419 #define LCOMMUNITY_STR_DEFAULT_LEN  40
 420         int str_size;
 421         int str_pnt;
 422         char *str_buf;
 423         int len = 0;
 424         int first = 1;
 425         u_int32_t globaladmin, localdata1, localdata2;
 426
 427         if (lcom->size == 0) {
 428                 str_buf = XMALLOC(MTYPE_LCOMMUNITY_STR, 1);
 429                 str_buf[0] = '\0';
 430                 return str_buf;
 431         }
 432
 433         /* Prepare buffer.  */
 434         str_buf = XMALLOC(MTYPE_LCOMMUNITY_STR, LCOMMUNITY_STR_DEFAULT_LEN + 1);
 435         str_size = LCOMMUNITY_STR_DEFAULT_LEN + 1;
 436         str_pnt = 0;
 437
 438         for (i = 0; i < lcom->size; i++) {
 439                 /* Make it sure size is enough.  */
 440                 while (str_pnt + LCOMMUNITY_STR_DEFAULT_LEN >= str_size) {
 441                         str_size *= 2;
 442                         str_buf = XREALLOC(MTYPE_LCOMMUNITY_STR, str_buf,
 443                                            str_size);
 444                 }
 445
 446                 /* Space between each value.  */
 447                 if (!first)
 448                         str_buf[str_pnt++] = ' ';
 449
 450                 pnt = lcom->val + (i * 12);
 451
 452                 globaladmin = (*pnt++ << 24);
 453                 globaladmin |= (*pnt++ << 16);
 454                 globaladmin |= (*pnt++ << 8);
 455                 globaladmin |= (*pnt++);
 456
 457                 localdata1 = (*pnt++ << 24);
 458                 localdata1 |= (*pnt++ << 16);
 459                 localdata1 |= (*pnt++ << 8);
 460                 localdata1 |= (*pnt++);
 461
 462                 localdata2 = (*pnt++ << 24);
 463                 localdata2 |= (*pnt++ << 16);
 464                 localdata2 |= (*pnt++ << 8);
 465                 localdata2 |= (*pnt++);
 466
 467                 len = sprintf(str_buf + str_pnt, "%u:%u:%u", globaladmin,
 468                               localdata1, localdata2);
 469                 str_pnt += len;
 470                 first = 0;
 471         }
 472         return str_buf;
 473 }
 474
 475 int lcommunity_match(const struct lcommunity *lcom1,
 476                      const struct lcommunity *lcom2)
 477 {
 478         int i = 0;
 479         int j = 0;
 480
 481         if (lcom1 == NULL && lcom2 == NULL)
 482                 return 1;
 483
 484         if (lcom1 == NULL || lcom2 == NULL)
 485                 return 0;
 486
 487         if (lcom1->size < lcom2->size)
 488                 return 0;
 489
 490         /* Every community on com2 needs to be on com1 for this to match */
 491         while (i < lcom1->size && j < lcom2->size) {
 492                 if (memcmp(lcom1->val + (i * 12), lcom2->val + (j * 12),
 493                            LCOMMUNITY_SIZE)
 494                     == 0)
 495                         j++;
 496                 i++;
 497         }
 498
 499         if (j == lcom2->size)
 500                 return 1;
 501         else
 502                 return 0;
 503 }
 504
 505 /* Delete one lcommunity. */
 506 void lcommunity_del_val(struct lcommunity *lcom, u_char *ptr)
 507 {
 508         int i = 0;
 509         int c = 0;
 510
 511         if (!lcom->val)
 512                 return;
 513
 514         while (i < lcom->size) {
 515                 if (memcmp(lcom->val + i * LCOMMUNITY_SIZE, ptr,
 516                            LCOMMUNITY_SIZE)
 517                     == 0) {
 518                         c = lcom->size - i - 1;
 519
 520                         if (c > 0)
 521                                 memmove(lcom->val + i * LCOMMUNITY_SIZE,
 522                                         lcom->val + (i + 1) * LCOMMUNITY_SIZE,
 523                                         c * LCOMMUNITY_SIZE);
 524
 525                         lcom->size--;
 526
 527                         if (lcom->size > 0)
 528                                 lcom->val =
 529                                         XREALLOC(MTYPE_COMMUNITY_VAL, lcom->val,
 530                                                  lcom_length(lcom));
 531                         else {
 532                                 XFREE(MTYPE_COMMUNITY_VAL, lcom->val);
 533                                 lcom->val = NULL;
 534                         }
 535                         return;
 536                 }
 537                 i++;
 538         }
 539 }