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