1/* Community attribute related functions. 2 Copyright (C) 1998, 2001 Kunihiro Ishiguro 3 4This file is part of GNU Zebra. 5 6GNU Zebra is free software; you can redistribute it and/or modify it 7under the terms of the GNU General Public License as published by the 8Free Software Foundation; either version 2, or (at your option) any 9later version. 10 11GNU Zebra is distributed in the hope that it will be useful, but 12WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GNU Zebra; see the file COPYING. If not, write to the Free 18Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 1902111-1307, USA. */ 20 21#include <zebra.h> 22 23#include "hash.h" 24#include "memory.h" 25 26#include "bgpd/bgp_community.h" 27 28/* Hash of community attribute. */ 29struct hash *comhash; 30 31/* Allocate a new communities value. */ 32struct community * 33community_new () 34{ 35 return (struct community *) XCALLOC (MTYPE_COMMUNITY, 36 sizeof (struct community)); 37} 38 39/* Free communities value. */ 40void 41community_free (struct community *com) 42{ 43 if (com->val) 44 XFREE (MTYPE_COMMUNITY_VAL, com->val); 45 if (com->str) 46 XFREE (MTYPE_COMMUNITY_STR, com->str); 47 XFREE (MTYPE_COMMUNITY, com); 48} 49 50/* Add one community value to the community. */ 51void 52community_add_val (struct community *com, u_int32_t val) 53{ 54 com->size++; 55 if (com->val) 56 com->val = XREALLOC (MTYPE_COMMUNITY_VAL, com->val, com_length (com)); 57 else 58 com->val = XMALLOC (MTYPE_COMMUNITY_VAL, com_length (com)); 59 60 val = htonl (val); 61 memcpy (com_lastval (com), &val, sizeof (u_int32_t)); 62} 63 64/* Delete one community. */ 65void 66community_del_val (struct community *com, u_int32_t *val) 67{ 68 int i = 0; 69 int c = 0; 70 71 if (! com->val) 72 return; 73 74 while (i < com->size) 75 { 76 if (memcmp (com->val + i, val, sizeof (u_int32_t)) == 0) 77 { 78 c = com->size -i -1; 79 80 if (c > 0) 81 memcpy (com->val + i, com->val + (i + 1), c * sizeof (val)); 82 83 com->size--; 84 85 if (com->size > 0) 86 com->val = XREALLOC (MTYPE_COMMUNITY_VAL, com->val, 87 com_length (com)); 88 else 89 { 90 XFREE (MTYPE_COMMUNITY_VAL, com->val); 91 com->val = NULL; 92 } 93 return; 94 } 95 i++; 96 } 97} 98 99/* Delete all communities listed in com2 from com1 */ 100struct community * 101community_delete (struct community *com1, struct community *com2) 102{ 103 int i = 0; 104 105 while(i < com2->size) 106 { 107 community_del_val (com1, com2->val + i); 108 i++; 109 } 110 111 return com1; 112} 113 114/* Callback function from qsort(). */ 115int 116community_compare (const void *a1, const void *a2) 117{ 118 u_int32_t v1; 119 u_int32_t v2; 120 121 memcpy (&v1, a1, sizeof (u_int32_t)); 122 memcpy (&v2, a2, sizeof (u_int32_t)); 123 v1 = ntohl (v1); 124 v2 = ntohl (v2); 125 126 if (v1 < v2) 127 return -1; 128 if (v1 > v2) 129 return 1; 130 return 0; 131} 132 133int 134community_include (struct community *com, u_int32_t val) 135{ 136 int i; 137 138 val = htonl (val); 139 140 for (i = 0; i < com->size; i++) 141 if (memcmp (&val, com_nthval (com, i), sizeof (u_int32_t)) == 0) 142 return 1; 143 144 return 0; 145} 146 147u_int32_t 148community_val_get (struct community *com, int i) 149{ 150 u_char *p; 151 u_int32_t val; 152 153 p = (u_char *) com->val; 154 p += (i * 4); 155 156 memcpy (&val, p, sizeof (u_int32_t)); 157 158 return ntohl (val); 159} 160 161/* Sort and uniq given community. */ 162struct community * 163community_uniq_sort (struct community *com) 164{ 165 int i; 166 struct community *new; 167 u_int32_t val; 168 169 if (! com) 170 return NULL; 171 172 new = community_new ();; 173 174 for (i = 0; i < com->size; i++) 175 { 176 val = community_val_get (com, i); 177 178 if (! community_include (new, val)) 179 community_add_val (new, val); 180 } 181 182 qsort (new->val, new->size, sizeof (u_int32_t), community_compare); 183 184 return new; 185} 186 187/* Convert communities attribute to string. 188 189 For Well-known communities value, below keyword is used. 190 191 0x0 "internet" 192 0xFFFFFF01 "no-export" 193 0xFFFFFF02 "no-advertise" 194 0xFFFFFF03 "local-AS" 195 196 For other values, "AS:VAL" format is used. */ 197static char * 198community_com2str (struct community *com) 199{ 200 int i; 201 char *str; 202 char *pnt; 203 int len; 204 int first; 205 u_int32_t comval; 206 u_int16_t as; 207 u_int16_t val; 208 209 /* When communities attribute is empty. */ 210 if (com->size == 0) 211 { 212 str = XMALLOC (MTYPE_COMMUNITY_STR, 1); 213 str[0] = '\0'; 214 return str; 215 } 216 217 /* Memory allocation is time consuming work. So we calculate 218 required string length first. */ 219 len = 0; 220 221 for (i = 0; i < com->size; i++) 222 { 223 memcpy (&comval, com_nthval (com, i), sizeof (u_int32_t)); 224 comval = ntohl (comval); 225 226 switch (comval) 227 { 228 case COMMUNITY_INTERNET: 229 len += strlen (" internet"); 230 break; 231 case COMMUNITY_NO_EXPORT: 232 len += strlen (" no-export"); 233 break; 234 case COMMUNITY_NO_ADVERTISE: 235 len += strlen (" no-advertise"); 236 break; 237 case COMMUNITY_LOCAL_AS: 238 len += strlen (" local-AS"); 239 break; 240 default: 241 len += strlen (" 65536:65535"); 242 break; 243 } 244 } 245 246 /* Allocate memory. */ 247 str = pnt = XMALLOC (MTYPE_COMMUNITY_STR, len); 248 first = 1; 249 250 /* Fill in string. */ 251 for (i = 0; i < com->size; i++) 252 { 253 memcpy (&comval, com_nthval (com, i), sizeof (u_int32_t)); 254 comval = ntohl (comval); 255 256 if (first) 257 first = 0; 258 else 259 *pnt++ = ' '; 260 261 switch (comval) 262 { 263 case COMMUNITY_INTERNET: 264 strcpy (pnt, "internet"); 265 pnt += strlen ("internet"); 266 break; 267 case COMMUNITY_NO_EXPORT: 268 strcpy (pnt, "no-export"); 269 pnt += strlen ("no-export"); 270 break; 271 case COMMUNITY_NO_ADVERTISE: 272 strcpy (pnt, "no-advertise"); 273 pnt += strlen ("no-advertise"); 274 break; 275 case COMMUNITY_LOCAL_AS: 276 strcpy (pnt, "local-AS"); 277 pnt += strlen ("local-AS"); 278 break; 279 default: 280 as = (comval >> 16) & 0xFFFF; 281 val = comval & 0xFFFF; 282 sprintf (pnt, "%d:%d", as, val); 283 pnt += strlen (pnt); 284 break; 285 } 286 } 287 *pnt = '\0'; 288 289 return str; 290} 291 292/* Intern communities attribute. */ 293struct community * 294community_intern (struct community *com) 295{ 296 struct community *find; 297 298 /* Assert this community structure is not interned. */ 299 assert (com->refcnt == 0); 300 301 /* Lookup community hash. */ 302 find = (struct community *) hash_get (comhash, com, hash_alloc_intern); 303 304 /* Arguemnt com is allocated temporary. So when it is not used in 305 hash, it should be freed. */ 306 if (find != com) 307 community_free (com); 308 309 /* Increment refrence counter. */ 310 find->refcnt++; 311 312 /* Make string. */ 313 if (! find->str) 314 find->str = community_com2str (find); 315 316 return find; 317} 318 319/* Free community attribute. */ 320void 321community_unintern (struct community *com) 322{ 323 struct community *ret; 324 325 if (com->refcnt) 326 com->refcnt--; 327 328 /* Pull off from hash. */ 329 if (com->refcnt == 0) 330 { 331 /* Community value com must exist in hash. */ 332 ret = (struct community *) hash_release (comhash, com); 333 assert (ret != NULL); 334 335 community_free (com); 336 } 337} 338 339/* Create new community attribute. */ 340struct community * 341community_parse (char *pnt, u_short length) 342{ 343 struct community tmp; 344 struct community *new; 345 346 /* If length is malformed return NULL. */ 347 if (length % 4) 348 return NULL; 349 350 /* Make temporary community for hash look up. */ 351 tmp.size = length / 4; 352 tmp.val = (u_int32_t *) pnt; 353 354 new = community_uniq_sort (&tmp); 355 356 return community_intern (new); 357} 358 359struct community * 360community_dup (struct community *com) 361{ 362 struct community *new; 363 364 new = XCALLOC (MTYPE_COMMUNITY, sizeof (struct community)); 365 new->size = com->size; 366 if (new->size) 367 { 368 new->val = XMALLOC (MTYPE_COMMUNITY_VAL, com->size * 4); 369 memcpy (new->val, com->val, com->size * 4); 370 } 371 else 372 new->val = NULL; 373 return new; 374} 375 376/* Retrun string representation of communities attribute. */ 377char * 378community_str (struct community *com) 379{ 380 if (! com->str) 381 com->str = community_com2str (com); 382 return com->str; 383} 384 385/* Make hash value of community attribute. This function is used by 386 hash package.*/ 387unsigned int 388community_hash_make (struct community *com) 389{ 390 int c; 391 unsigned int key; 392 unsigned char *pnt; 393 394 key = 0; 395 pnt = (unsigned char *)com->val; 396 397 for(c = 0; c < com->size * 4; c++) 398 key += pnt[c]; 399 400 return key; 401} 402 403int 404community_match (struct community *com1, struct community *com2) 405{ 406 int i = 0; 407 int j = 0; 408 409 if (com1 == NULL && com2 == NULL) 410 return 1; 411 412 if (com1 == NULL || com2 == NULL) 413 return 0; 414 415 if (com1->size < com2->size) 416 return 0; 417 418 /* Every community on com2 needs to be on com1 for this to match */ 419 while (i < com1->size && j < com2->size) 420 { 421 if (memcmp (com1->val + i, com2->val + j, sizeof (u_int32_t)) == 0) 422 j++; 423 i++; 424 } 425 426 if (j == com2->size) 427 return 1; 428 else 429 return 0; 430} 431 432/* If two aspath have same value then return 1 else return 0. This 433 function is used by hash package. */ 434int 435community_cmp (struct community *com1, struct community *com2) 436{ 437 if (com1 == NULL && com2 == NULL) 438 return 1; 439 if (com1 == NULL || com2 == NULL) 440 return 0; 441 442 if (com1->size == com2->size) 443 if (memcmp (com1->val, com2->val, com1->size * 4) == 0) 444 return 1; 445 return 0; 446} 447 448/* Add com2 to the end of com1. */ 449struct community * 450community_merge (struct community *com1, struct community *com2) 451{ 452 if (com1->val) 453 com1->val = XREALLOC (MTYPE_COMMUNITY_VAL, com1->val, 454 (com1->size + com2->size) * 4); 455 else 456 com1->val = XMALLOC (MTYPE_COMMUNITY_VAL, (com1->size + com2->size) * 4); 457 458 memcpy (com1->val + com1->size, com2->val, com2->size * 4); 459 com1->size += com2->size; 460 461 return com1; 462} 463 464/* Community token enum. */ 465enum community_token 466{ 467 community_token_val, 468 community_token_no_export, 469 community_token_no_advertise, 470 community_token_local_as, 471 community_token_unknown 472}; 473 474/* Get next community token from string. */ 475char * 476community_gettoken (char *buf, enum community_token *token, u_int32_t *val) 477{ 478 char *p = buf; 479 480 /* Skip white space. */ 481 while (isspace ((int) *p)) 482 p++; 483 484 /* Check the end of the line. */ 485 if (*p == '\0') 486 return NULL; 487 488 /* Well known community string check. */ 489 if (isalpha ((int) *p)) 490 { 491 if (strncmp (p, "internet", strlen ("internet")) == 0) 492 { 493 *val = COMMUNITY_INTERNET; 494 *token = community_token_no_export; 495 p += strlen ("internet"); 496 return p; 497 } 498 if (strncmp (p, "no-export", strlen ("no-export")) == 0) 499 { 500 *val = COMMUNITY_NO_EXPORT; 501 *token = community_token_no_export; 502 p += strlen ("no-export"); 503 return p; 504 } 505 if (strncmp (p, "no-advertise", strlen ("no-advertise")) == 0) 506 { 507 *val = COMMUNITY_NO_ADVERTISE; 508 *token = community_token_no_advertise; 509 p += strlen ("no-advertise"); 510 return p; 511 } 512 if (strncmp (p, "local-AS", strlen ("local-AS")) == 0) 513 { 514 *val = COMMUNITY_LOCAL_AS; 515 *token = community_token_local_as; 516 p += strlen ("local-AS"); 517 return p; 518 } 519 520 /* Unknown string. */ 521 *token = community_token_unknown; 522 return p; 523 } 524 525 /* Community value. */ 526 if (isdigit ((int) *p)) 527 { 528 int separator = 0; 529 int digit = 0; 530 u_int32_t community_low = 0; 531 u_int32_t community_high = 0; 532 533 while (isdigit ((int) *p) || *p == ':') 534 { 535 if (*p == ':') 536 { 537 if (separator) 538 { 539 *token = community_token_unknown; 540 return p; 541 } 542 else 543 { 544 separator = 1; 545 digit = 0; 546 community_high = community_low << 16; 547 community_low = 0; 548 } 549 } 550 else 551 { 552 digit = 1; 553 community_low *= 10; 554 community_low += (*p - '0'); 555 } 556 p++; 557 } 558 if (! digit) 559 { 560 *token = community_token_unknown; 561 return p; 562 } 563 *val = community_high + community_low; 564 *token = community_token_val; 565 return p; 566 } 567 *token = community_token_unknown; 568 return p; 569} 570 571/* convert string to community structure */ 572struct community * 573community_str2com (char *str) 574{ 575 struct community *com = NULL; 576 struct community *com_sort = NULL; 577 u_int32_t val; 578 enum community_token token; 579 580 while ((str = community_gettoken (str, &token, &val))) 581 { 582 switch (token) 583 { 584 case community_token_val: 585 case community_token_no_export: 586 case community_token_no_advertise: 587 case community_token_local_as: 588 if (com == NULL) 589 com = community_new(); 590 community_add_val (com, val); 591 break; 592 case community_token_unknown: 593 default: 594 if (com) 595 community_free (com); 596 return NULL; 597 break; 598 } 599 } 600 601 if (! com) 602 return NULL; 603 604 com_sort = community_uniq_sort (com); 605 community_free (com); 606 607 return com_sort; 608} 609 610/* Return communities hash entry count. */ 611unsigned long 612community_count () 613{ 614 return comhash->count; 615} 616 617/* Return communities hash. */ 618struct hash * 619community_hash () 620{ 621 return comhash; 622} 623 624/* Initialize comminity related hash. */ 625void 626community_init () 627{ 628 comhash = hash_create (community_hash_make, community_cmp); 629} 630