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, 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         lcom_ptr = lcom->val;
 402         for (i = 0; i < lcom->size; i++) {
 403                 lcom_ptr += (i * LCOMMUNITY_SIZE);
 404                 if (memcmp(ptr, lcom_ptr, LCOMMUNITY_SIZE) == 0)
 405                         return 1;
 406         }
 407         return 0;
 408 }
 409
 410 /* Convert large community attribute to string.
 411    The large coms will be in 65535:65531:0 format.
 412 */
 413 char *lcommunity_lcom2str(struct lcommunity *lcom, int format)
 414 {
 415         int i;
 416         u_int8_t *pnt;
 417 #define LCOMMUNITY_STR_DEFAULT_LEN  40
 418         int str_size;
 419         int str_pnt;
 420         char *str_buf;
 421         int len = 0;
 422         int first = 1;
 423         u_int32_t globaladmin, localdata1, localdata2;
 424
 425         if (lcom->size == 0) {
 426                 str_buf = XMALLOC(MTYPE_LCOMMUNITY_STR, 1);
 427                 str_buf[0] = '\0';
 428                 return str_buf;
 429         }
 430
 431         /* Prepare buffer.  */
 432         str_buf = XMALLOC(MTYPE_LCOMMUNITY_STR, LCOMMUNITY_STR_DEFAULT_LEN + 1);
 433         str_size = LCOMMUNITY_STR_DEFAULT_LEN + 1;
 434         str_pnt = 0;
 435
 436         for (i = 0; i < lcom->size; i++) {
 437                 /* Make it sure size is enough.  */
 438                 while (str_pnt + LCOMMUNITY_STR_DEFAULT_LEN >= str_size) {
 439                         str_size *= 2;
 440                         str_buf = XREALLOC(MTYPE_LCOMMUNITY_STR, str_buf,
 441                                            str_size);
 442                 }
 443
 444                 /* Space between each value.  */
 445                 if (!first)
 446                         str_buf[str_pnt++] = ' ';
 447
 448                 pnt = lcom->val + (i * LCOMMUNITY_SIZE);
 449
 450                 globaladmin = (*pnt++ << 24);
 451                 globaladmin |= (*pnt++ << 16);
 452                 globaladmin |= (*pnt++ << 8);
 453                 globaladmin |= (*pnt++);
 454
 455                 localdata1 = (*pnt++ << 24);
 456                 localdata1 |= (*pnt++ << 16);
 457                 localdata1 |= (*pnt++ << 8);
 458                 localdata1 |= (*pnt++);
 459
 460                 localdata2 = (*pnt++ << 24);
 461                 localdata2 |= (*pnt++ << 16);
 462                 localdata2 |= (*pnt++ << 8);
 463                 localdata2 |= (*pnt++);
 464
 465                 len = sprintf(str_buf + str_pnt, "%u:%u:%u", globaladmin,
 466                               localdata1, localdata2);
 467                 str_pnt += len;
 468                 first = 0;
 469         }
 470         return str_buf;
 471 }
 472
 473 int lcommunity_match(const struct lcommunity *lcom1,
 474                      const struct lcommunity *lcom2)
 475 {
 476         int i = 0;
 477         int j = 0;
 478
 479         if (lcom1 == NULL && lcom2 == NULL)
 480                 return 1;
 481
 482         if (lcom1 == NULL || lcom2 == NULL)
 483                 return 0;
 484
 485         if (lcom1->size < lcom2->size)
 486                 return 0;
 487
 488         /* Every community on com2 needs to be on com1 for this to match */
 489         while (i < lcom1->size && j < lcom2->size) {
 490                 if (memcmp(lcom1->val + (i * LCOMMUNITY_SIZE), lcom2->val + (j * LCOMMUNITY_SIZE),
 491                            LCOMMUNITY_SIZE)
 492                     == 0)
 493                         j++;
 494                 i++;
 495         }
 496
 497         if (j == lcom2->size)
 498                 return 1;
 499         else
 500                 return 0;
 501 }
 502
 503 /* Delete one lcommunity. */
 504 void lcommunity_del_val(struct lcommunity *lcom, u_char *ptr)
 505 {
 506         int i = 0;
 507         int c = 0;
 508
 509         if (!lcom->val)
 510                 return;
 511
 512         while (i < lcom->size) {
 513                 if (memcmp(lcom->val + i * LCOMMUNITY_SIZE, ptr,
 514                            LCOMMUNITY_SIZE)
 515                     == 0) {
 516                         c = lcom->size - i - 1;
 517
 518                         if (c > 0)
 519                                 memmove(lcom->val + i * LCOMMUNITY_SIZE,
 520                                         lcom->val + (i + 1) * LCOMMUNITY_SIZE,
 521                                         c * LCOMMUNITY_SIZE);
 522
 523                         lcom->size--;
 524
 525                         if (lcom->size > 0)
 526                                 lcom->val =
 527                                         XREALLOC(MTYPE_COMMUNITY_VAL, lcom->val,
 528                                                  lcom_length(lcom));
 529                         else {
 530                                 XFREE(MTYPE_COMMUNITY_VAL, lcom->val);
 531                                 lcom->val = NULL;
 532                         }
 533                         return;
 534                 }
 535                 i++;
 536         }
 537 }