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 = lcommunity_new();
 152         new->size = lcom->size;
 153         if (new->size) {
 154                 new->val = XMALLOC(MTYPE_LCOMMUNITY_VAL, lcom_length(lcom));
 155                 memcpy(new->val, lcom->val, lcom_length(lcom));
 156         } else
 157                 new->val = NULL;
 158         return new;
 159 }
 160
 161 /* Retrun string representation of communities attribute. */
 162 char *lcommunity_str(struct lcommunity *lcom)
 163 {
 164         if (!lcom->str)
 165                 lcom->str =
 166                         lcommunity_lcom2str(lcom, LCOMMUNITY_FORMAT_DISPLAY);
 167         return lcom->str;
 168 }
 169
 170 /* Merge two Large Communities Attribute structure.  */
 171 struct lcommunity *lcommunity_merge(struct lcommunity *lcom1,
 172                                     struct lcommunity *lcom2)
 173 {
 174         if (lcom1->val)
 175                 lcom1->val =
 176                         XREALLOC(MTYPE_LCOMMUNITY_VAL, lcom1->val,
 177                                  lcom_length(lcom1) + lcom_length(lcom2));
 178         else
 179                 lcom1->val =
 180                         XMALLOC(MTYPE_LCOMMUNITY_VAL,
 181                                 lcom_length(lcom1) + lcom_length(lcom2));
 182
 183         memcpy(lcom1->val + lcom_length(lcom1), lcom2->val, lcom_length(lcom2));
 184         lcom1->size += lcom2->size;
 185
 186         return lcom1;
 187 }
 188
 189 /* Intern Large Communities Attribute.  */
 190 struct lcommunity *lcommunity_intern(struct lcommunity *lcom)
 191 {
 192         struct lcommunity *find;
 193
 194         assert(lcom->refcnt == 0);
 195
 196         find = (struct lcommunity *)hash_get(lcomhash, lcom, hash_alloc_intern);
 197
 198         if (find != lcom)
 199                 lcommunity_free(&lcom);
 200
 201         find->refcnt++;
 202
 203         if (!find->str)
 204                 find->str =
 205                         lcommunity_lcom2str(find, LCOMMUNITY_FORMAT_DISPLAY);
 206
 207         return find;
 208 }
 209
 210 /* Unintern Large Communities Attribute.  */
 211 void lcommunity_unintern(struct lcommunity **lcom)
 212 {
 213         struct lcommunity *ret;
 214
 215         if ((*lcom)->refcnt)
 216                 (*lcom)->refcnt--;
 217
 218         /* Pull off from hash.  */
 219         if ((*lcom)->refcnt == 0) {
 220                 /* Large community must be in the hash.  */
 221                 ret = (struct lcommunity *)hash_release(lcomhash, *lcom);
 222                 assert(ret != NULL);
 223
 224                 lcommunity_free(lcom);
 225         }
 226 }
 227
 228 /* Utility function to make hash key.  */
 229 unsigned int lcommunity_hash_make(void *arg)
 230 {
 231         const struct lcommunity *lcom = arg;
 232         int size = lcom_length(lcom);
 233         u_int8_t *pnt = lcom->val;
 234         unsigned int key = 0;
 235         int c;
 236
 237         for (c = 0; c < size; c += LCOMMUNITY_SIZE) {
 238                 key += pnt[c];
 239                 key += pnt[c + 1];
 240                 key += pnt[c + 2];
 241                 key += pnt[c + 3];
 242                 key += pnt[c + 4];
 243                 key += pnt[c + 5];
 244                 key += pnt[c + 6];
 245                 key += pnt[c + 7];
 246                 key += pnt[c + 8];
 247                 key += pnt[c + 9];
 248                 key += pnt[c + 10];
 249                 key += pnt[c + 11];
 250         }
 251
 252         return key;
 253 }
 254
 255 /* Compare two Large Communities Attribute structure.  */
 256 int lcommunity_cmp(const void *arg1, const void *arg2)
 257 {
 258         const struct lcommunity *lcom1 = arg1;
 259         const struct lcommunity *lcom2 = arg2;
 260
 261         return (lcom1->size == lcom2->size
 262                 && memcmp(lcom1->val, lcom2->val, lcom_length(lcom1))
 263                            == 0);
 264 }
 265
 266 /* Return communities hash.  */
 267 struct hash *lcommunity_hash(void)
 268 {
 269         return lcomhash;
 270 }
 271
 272 /* Initialize Large Comminities related hash. */
 273 void lcommunity_init(void)
 274 {
 275         lcomhash = hash_create(lcommunity_hash_make, lcommunity_cmp, NULL);
 276 }
 277
 278 void lcommunity_finish(void)
 279 {
 280         hash_clean(lcomhash, (void (*)(void *))lcommunity_hash_free);
 281         hash_free(lcomhash);
 282         lcomhash = NULL;
 283 }
 284
 285 /* Large Communities token enum. */
 286 enum lcommunity_token {
 287         lcommunity_token_unknown = 0,
 288         lcommunity_token_val,
 289 };
 290
 291 /* Get next Large Communities token from the string. */
 292 static const char *lcommunity_gettoken(const char *str,
 293                                        struct lcommunity_val *lval,
 294                                        enum lcommunity_token *token)
 295 {
 296         const char *p = str;
 297
 298         /* Skip white space. */
 299         while (isspace((int)*p)) {
 300                 p++;
 301                 str++;
 302         }
 303
 304         /* Check the end of the line. */
 305         if (*p == '\0')
 306                 return NULL;
 307
 308         /* Community value. */
 309         if (isdigit((int)*p)) {
 310                 int separator = 0;
 311                 int digit = 0;
 312                 u_int32_t globaladmin = 0;
 313                 u_int32_t localdata1 = 0;
 314                 u_int32_t localdata2 = 0;
 315
 316                 while (isdigit((int)*p) || *p == ':') {
 317                         if (*p == ':') {
 318                                 if (separator == 2) {
 319                                         *token = lcommunity_token_unknown;
 320                                         return NULL;
 321                                 } else {
 322                                         separator++;
 323                                         digit = 0;
 324                                         if (separator == 1) {
 325                                                 globaladmin = localdata2;
 326                                         } else {
 327                                                 localdata1 = localdata2;
 328                                         }
 329                                         localdata2 = 0;
 330                                 }
 331                         } else {
 332                                 digit = 1;
 333                                 localdata2 *= 10;
 334                                 localdata2 += (*p - '0');
 335                         }
 336                         p++;
 337                 }
 338                 if (!digit) {
 339                         *token = lcommunity_token_unknown;
 340                         return NULL;
 341                 }
 342
 343                 /*
 344                  * Copy the large comm.
 345                  */
 346                 lval->val[0] = (globaladmin >> 24) & 0xff;
 347                 lval->val[1] = (globaladmin >> 16) & 0xff;
 348                 lval->val[2] = (globaladmin >> 8) & 0xff;
 349                 lval->val[3] = globaladmin & 0xff;
 350                 lval->val[4] = (localdata1 >> 24) & 0xff;
 351                 lval->val[5] = (localdata1 >> 16) & 0xff;
 352                 lval->val[6] = (localdata1 >> 8) & 0xff;
 353                 lval->val[7] = localdata1 & 0xff;
 354                 lval->val[8] = (localdata2 >> 24) & 0xff;
 355                 lval->val[9] = (localdata2 >> 16) & 0xff;
 356                 lval->val[10] = (localdata2 >> 8) & 0xff;
 357                 lval->val[11] = localdata2 & 0xff;
 358
 359                 *token = lcommunity_token_val;
 360                 return p;
 361         }
 362         *token = lcommunity_token_unknown;
 363         return p;
 364 }
 365
 366 /*
 367   Convert string to large community attribute.
 368   When type is already known, please specify both str and type.
 369
 370   When string includes keyword for each large community value.
 371   Please specify keyword_included as non-zero value.
 372 */
 373 struct lcommunity *lcommunity_str2com(const char *str)
 374 {
 375         struct lcommunity *lcom = NULL;
 376         enum lcommunity_token token = lcommunity_token_unknown;
 377         struct lcommunity_val lval;
 378
 379         while ((str = lcommunity_gettoken(str, &lval, &token))) {
 380                 switch (token) {
 381                 case lcommunity_token_val:
 382                         if (lcom == NULL)
 383                                 lcom = lcommunity_new();
 384                         lcommunity_add_val(lcom, &lval);
 385                         break;
 386                 case lcommunity_token_unknown:
 387                 default:
 388                         if (lcom)
 389                                 lcommunity_free(&lcom);
 390                         return NULL;
 391                 }
 392         }
 393         return lcom;
 394 }
 395
 396 int lcommunity_include(struct lcommunity *lcom, u_char *ptr)
 397 {
 398         int i;
 399         u_char *lcom_ptr;
 400
 401         for (i = 0; i < lcom->size; i++) {
 402                 lcom_ptr = lcom->val + (i * LCOMMUNITY_SIZE);
 403                 if (memcmp(ptr, lcom_ptr, LCOMMUNITY_SIZE) == 0)
 404                         return 1;
 405         }
 406         return 0;
 407 }
 408
 409 /* Convert large community attribute to string.
 410    The large coms will be in 65535:65531:0 format.
 411 */
 412 char *lcommunity_lcom2str(struct lcommunity *lcom, int format)
 413 {
 414         int i;
 415         u_int8_t *pnt;
 416 #define LCOMMUNITY_STR_DEFAULT_LEN  40
 417         int str_size;
 418         int str_pnt;
 419         char *str_buf;
 420         int len = 0;
 421         int first = 1;
 422         u_int32_t globaladmin, localdata1, localdata2;
 423
 424         if (lcom->size == 0) {
 425                 str_buf = XMALLOC(MTYPE_LCOMMUNITY_STR, 1);
 426                 str_buf[0] = '\0';
 427                 return str_buf;
 428         }
 429
 430         /* Prepare buffer.  */
 431         str_buf = XMALLOC(MTYPE_LCOMMUNITY_STR, LCOMMUNITY_STR_DEFAULT_LEN + 1);
 432         str_size = LCOMMUNITY_STR_DEFAULT_LEN + 1;
 433         str_pnt = 0;
 434
 435         for (i = 0; i < lcom->size; i++) {
 436                 /* Make it sure size is enough.  */
 437                 while (str_pnt + LCOMMUNITY_STR_DEFAULT_LEN >= str_size) {
 438                         str_size *= 2;
 439                         str_buf = XREALLOC(MTYPE_LCOMMUNITY_STR, str_buf,
 440                                            str_size);
 441                 }
 442
 443                 /* Space between each value.  */
 444                 if (!first)
 445                         str_buf[str_pnt++] = ' ';
 446
 447                 pnt = lcom->val + (i * LCOMMUNITY_SIZE);
 448
 449                 globaladmin = (*pnt++ << 24);
 450                 globaladmin |= (*pnt++ << 16);
 451                 globaladmin |= (*pnt++ << 8);
 452                 globaladmin |= (*pnt++);
 453
 454                 localdata1 = (*pnt++ << 24);
 455                 localdata1 |= (*pnt++ << 16);
 456                 localdata1 |= (*pnt++ << 8);
 457                 localdata1 |= (*pnt++);
 458
 459                 localdata2 = (*pnt++ << 24);
 460                 localdata2 |= (*pnt++ << 16);
 461                 localdata2 |= (*pnt++ << 8);
 462                 localdata2 |= (*pnt++);
 463
 464                 len = sprintf(str_buf + str_pnt, "%u:%u:%u", globaladmin,
 465                               localdata1, localdata2);
 466                 str_pnt += len;
 467                 first = 0;
 468         }
 469         return str_buf;
 470 }
 471
 472 int lcommunity_match(const struct lcommunity *lcom1,
 473                      const struct lcommunity *lcom2)
 474 {
 475         int i = 0;
 476         int j = 0;
 477
 478         if (lcom1 == NULL && lcom2 == NULL)
 479                 return 1;
 480
 481         if (lcom1 == NULL || lcom2 == NULL)
 482                 return 0;
 483
 484         if (lcom1->size < lcom2->size)
 485                 return 0;
 486
 487         /* Every community on com2 needs to be on com1 for this to match */
 488         while (i < lcom1->size && j < lcom2->size) {
 489                 if (memcmp(lcom1->val + (i * LCOMMUNITY_SIZE), lcom2->val + (j * LCOMMUNITY_SIZE),
 490                            LCOMMUNITY_SIZE)
 491                     == 0)
 492                         j++;
 493                 i++;
 494         }
 495
 496         if (j == lcom2->size)
 497                 return 1;
 498         else
 499                 return 0;
 500 }
 501
 502 /* Delete one lcommunity. */
 503 void lcommunity_del_val(struct lcommunity *lcom, u_char *ptr)
 504 {
 505         int i = 0;
 506         int c = 0;
 507
 508         if (!lcom->val)
 509                 return;
 510
 511         while (i < lcom->size) {
 512                 if (memcmp(lcom->val + i * LCOMMUNITY_SIZE, ptr,
 513                            LCOMMUNITY_SIZE)
 514                     == 0) {
 515                         c = lcom->size - i - 1;
 516
 517                         if (c > 0)
 518                                 memmove(lcom->val + i * LCOMMUNITY_SIZE,
 519                                         lcom->val + (i + 1) * LCOMMUNITY_SIZE,
 520                                         c * LCOMMUNITY_SIZE);
 521
 522                         lcom->size--;
 523
 524                         if (lcom->size > 0)
 525                                 lcom->val =
 526                                         XREALLOC(MTYPE_LCOMMUNITY_VAL, lcom->val,
 527                                                  lcom_length(lcom));
 528                         else {
 529                                 XFREE(MTYPE_LCOMMUNITY_VAL, lcom->val);
 530                                 lcom->val = NULL;
 531                         }
 532                         return;
 533                 }
 534                 i++;
 535         }
 536 }