1 /* Community attribute related functions.
2 Copyright (C) 1998, 2001 Kunihiro Ishiguro
3
4 This file is part of GNU Zebra.
5
6 GNU Zebra is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 later version.
10
11 GNU Zebra is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GNU Zebra; see the file COPYING. If not, write to the Free
18 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
19 02111-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. */
29 static struct hash *comhash;
30
31 /* Allocate a new communities value. */
32 static struct community *
community_new(void)33 community_new (void)
34 {
35 return (struct community *) XCALLOC (MTYPE_COMMUNITY,
36 sizeof (struct community));
37 }
38
39 /* Free communities value. */
40 void
community_free(struct community * com)41 community_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. */
51 static void
community_add_val(struct community * com,u_int32_t val)52 community_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. */
65 void
community_del_val(struct community * com,u_int32_t * val)66 community_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 memmove (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 */
100 struct community *
community_delete(struct community * com1,struct community * com2)101 community_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(). */
115 static int
community_compare(const void * a1,const void * a2)116 community_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
133 int
community_include(struct community * com,u_int32_t val)134 community_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
147 u_int32_t
community_val_get(struct community * com,int i)148 community_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. */
162 struct community *
community_uniq_sort(struct community * com)163 community_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. */
197 static char *
community_com2str(struct community * com)198 community_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 if (!com)
210 return NULL;
211
212 /* When communities attribute is empty. */
213 if (com->size == 0)
214 {
215 str = XMALLOC (MTYPE_COMMUNITY_STR, 1);
216 str[0] = '\0';
217 return str;
218 }
219
220 /* Memory allocation is time consuming work. So we calculate
221 required string length first. */
222 len = 0;
223
224 for (i = 0; i < com->size; i++)
225 {
226 memcpy (&comval, com_nthval (com, i), sizeof (u_int32_t));
227 comval = ntohl (comval);
228
229 switch (comval)
230 {
231 case COMMUNITY_INTERNET:
232 len += strlen (" internet");
233 break;
234 case COMMUNITY_NO_EXPORT:
235 len += strlen (" no-export");
236 break;
237 case COMMUNITY_NO_ADVERTISE:
238 len += strlen (" no-advertise");
239 break;
240 case COMMUNITY_LOCAL_AS:
241 len += strlen (" local-AS");
242 break;
243 default:
244 len += strlen (" 65536:65535");
245 break;
246 }
247 }
248
249 /* Allocate memory. */
250 str = pnt = XMALLOC (MTYPE_COMMUNITY_STR, len);
251 first = 1;
252
253 /* Fill in string. */
254 for (i = 0; i < com->size; i++)
255 {
256 memcpy (&comval, com_nthval (com, i), sizeof (u_int32_t));
257 comval = ntohl (comval);
258
259 if (first)
260 first = 0;
261 else
262 *pnt++ = ' ';
263
264 switch (comval)
265 {
266 case COMMUNITY_INTERNET:
267 strcpy (pnt, "internet");
268 pnt += strlen ("internet");
269 break;
270 case COMMUNITY_NO_EXPORT:
271 strcpy (pnt, "no-export");
272 pnt += strlen ("no-export");
273 break;
274 case COMMUNITY_NO_ADVERTISE:
275 strcpy (pnt, "no-advertise");
276 pnt += strlen ("no-advertise");
277 break;
278 case COMMUNITY_LOCAL_AS:
279 strcpy (pnt, "local-AS");
280 pnt += strlen ("local-AS");
281 break;
282 default:
283 as = (comval >> 16) & 0xFFFF;
284 val = comval & 0xFFFF;
285 sprintf (pnt, "%u:%d", as, val);
286 pnt += strlen (pnt);
287 break;
288 }
289 }
290 *pnt = '\0';
291
292 return str;
293 }
294
295 /* Intern communities attribute. */
296 struct community *
community_intern(struct community * com)297 community_intern (struct community *com)
298 {
299 struct community *find;
300
301 /* Assert this community structure is not interned. */
302 assert (com->refcnt == 0);
303
304 /* Lookup community hash. */
305 find = (struct community *) hash_get (comhash, com, hash_alloc_intern);
306
307 /* Arguemnt com is allocated temporary. So when it is not used in
308 hash, it should be freed. */
309 if (find != com)
310 community_free (com);
311
312 /* Increment refrence counter. */
313 find->refcnt++;
314
315 /* Make string. */
316 if (! find->str)
317 find->str = community_com2str (find);
318
319 return find;
320 }
321
322 /* Free community attribute. */
323 void
community_unintern(struct community ** com)324 community_unintern (struct community **com)
325 {
326 struct community *ret;
327
328 if ((*com)->refcnt)
329 (*com)->refcnt--;
330
331 /* Pull off from hash. */
332 if ((*com)->refcnt == 0)
333 {
334 /* Community value com must exist in hash. */
335 ret = (struct community *) hash_release (comhash, *com);
336 assert (ret != NULL);
337
338 community_free (*com);
339 *com = NULL;
340 }
341 }
342
343 /* Create new community attribute. */
344 struct community *
community_parse(u_int32_t * pnt,u_short length)345 community_parse (u_int32_t *pnt, u_short length)
346 {
347 struct community tmp;
348 struct community *new;
349
350 /* If length is malformed return NULL. */
351 if (length % 4)
352 return NULL;
353
354 /* Make temporary community for hash look up. */
355 tmp.size = length / 4;
356 tmp.val = pnt;
357
358 new = community_uniq_sort (&tmp);
359
360 return community_intern (new);
361 }
362
363 struct community *
community_dup(struct community * com)364 community_dup (struct community *com)
365 {
366 struct community *new;
367
368 new = XCALLOC (MTYPE_COMMUNITY, sizeof (struct community));
369 new->size = com->size;
370 if (new->size)
371 {
372 new->val = XMALLOC (MTYPE_COMMUNITY_VAL, com->size * 4);
373 memcpy (new->val, com->val, com->size * 4);
374 }
375 else
376 new->val = NULL;
377 return new;
378 }
379
380 /* Retrun string representation of communities attribute. */
381 char *
community_str(struct community * com)382 community_str (struct community *com)
383 {
384 if (!com)
385 return NULL;
386
387 if (! com->str)
388 com->str = community_com2str (com);
389 return com->str;
390 }
391
392 /* Make hash value of community attribute. This function is used by
393 hash package.*/
394 unsigned int
community_hash_make(struct community * com)395 community_hash_make (struct community *com)
396 {
397 unsigned char *pnt = (unsigned char *)com->val;
398 int size = com->size * 4;
399 unsigned int key = 0;
400 int c;
401
402 for (c = 0; c < size; c += 4)
403 {
404 key += pnt[c];
405 key += pnt[c + 1];
406 key += pnt[c + 2];
407 key += pnt[c + 3];
408 }
409
410 return key;
411 }
412
413 int
community_match(const struct community * com1,const struct community * com2)414 community_match (const struct community *com1, const struct community *com2)
415 {
416 int i = 0;
417 int j = 0;
418
419 if (com1 == NULL && com2 == NULL)
420 return 1;
421
422 if (com1 == NULL || com2 == NULL)
423 return 0;
424
425 if (com1->size < com2->size)
426 return 0;
427
428 /* Every community on com2 needs to be on com1 for this to match */
429 while (i < com1->size && j < com2->size)
430 {
431 if (memcmp (com1->val + i, com2->val + j, sizeof (u_int32_t)) == 0)
432 j++;
433 i++;
434 }
435
436 if (j == com2->size)
437 return 1;
438 else
439 return 0;
440 }
441
442 /* If two aspath have same value then return 1 else return 0. This
443 function is used by hash package. */
444 int
community_cmp(const struct community * com1,const struct community * com2)445 community_cmp (const struct community *com1, const struct community *com2)
446 {
447 if (com1 == NULL && com2 == NULL)
448 return 1;
449 if (com1 == NULL || com2 == NULL)
450 return 0;
451
452 if (com1->size == com2->size)
453 if (memcmp (com1->val, com2->val, com1->size * 4) == 0)
454 return 1;
455 return 0;
456 }
457
458 /* Add com2 to the end of com1. */
459 struct community *
community_merge(struct community * com1,struct community * com2)460 community_merge (struct community *com1, struct community *com2)
461 {
462 if (com1->val)
463 com1->val = XREALLOC (MTYPE_COMMUNITY_VAL, com1->val,
464 (com1->size + com2->size) * 4);
465 else
466 com1->val = XMALLOC (MTYPE_COMMUNITY_VAL, (com1->size + com2->size) * 4);
467
468 memcpy (com1->val + com1->size, com2->val, com2->size * 4);
469 com1->size += com2->size;
470
471 return com1;
472 }
473
474 /* Community token enum. */
475 enum community_token
476 {
477 community_token_val,
478 community_token_no_export,
479 community_token_no_advertise,
480 community_token_local_as,
481 community_token_unknown
482 };
483
484 /* Get next community token from string. */
485 static const char *
community_gettoken(const char * buf,enum community_token * token,u_int32_t * val)486 community_gettoken (const char *buf, enum community_token *token,
487 u_int32_t *val)
488 {
489 const char *p = buf;
490
491 /* Skip white space. */
492 while (isspace ((int) *p))
493 p++;
494
495 /* Check the end of the line. */
496 if (*p == '\0')
497 return NULL;
498
499 /* Well known community string check. */
500 if (isalpha ((int) *p))
501 {
502 if (strncmp (p, "internet", strlen ("internet")) == 0)
503 {
504 *val = COMMUNITY_INTERNET;
505 *token = community_token_no_export;
506 p += strlen ("internet");
507 return p;
508 }
509 if (strncmp (p, "no-export", strlen ("no-export")) == 0)
510 {
511 *val = COMMUNITY_NO_EXPORT;
512 *token = community_token_no_export;
513 p += strlen ("no-export");
514 return p;
515 }
516 if (strncmp (p, "no-advertise", strlen ("no-advertise")) == 0)
517 {
518 *val = COMMUNITY_NO_ADVERTISE;
519 *token = community_token_no_advertise;
520 p += strlen ("no-advertise");
521 return p;
522 }
523 if (strncmp (p, "local-AS", strlen ("local-AS")) == 0)
524 {
525 *val = COMMUNITY_LOCAL_AS;
526 *token = community_token_local_as;
527 p += strlen ("local-AS");
528 return p;
529 }
530
531 /* Unknown string. */
532 *token = community_token_unknown;
533 return NULL;
534 }
535
536 /* Community value. */
537 if (isdigit ((int) *p))
538 {
539 int separator = 0;
540 int digit = 0;
541 u_int32_t community_low = 0;
542 u_int32_t community_high = 0;
543
544 while (isdigit ((int) *p) || *p == ':')
545 {
546 if (*p == ':')
547 {
548 if (separator)
549 {
550 *token = community_token_unknown;
551 return NULL;
552 }
553 else
554 {
555 separator = 1;
556 digit = 0;
557 community_high = community_low << 16;
558 community_low = 0;
559 }
560 }
561 else
562 {
563 digit = 1;
564 community_low *= 10;
565 community_low += (*p - '0');
566 }
567 p++;
568 }
569 if (! digit)
570 {
571 *token = community_token_unknown;
572 return NULL;
573 }
574 *val = community_high + community_low;
575 *token = community_token_val;
576 return p;
577 }
578 *token = community_token_unknown;
579 return NULL;
580 }
581
582 /* convert string to community structure */
583 struct community *
community_str2com(const char * str)584 community_str2com (const char *str)
585 {
586 struct community *com = NULL;
587 struct community *com_sort = NULL;
588 u_int32_t val = 0;
589 enum community_token token = community_token_unknown;
590
591 do
592 {
593 str = community_gettoken (str, &token, &val);
594
595 switch (token)
596 {
597 case community_token_val:
598 case community_token_no_export:
599 case community_token_no_advertise:
600 case community_token_local_as:
601 if (com == NULL)
602 com = community_new();
603 community_add_val (com, val);
604 break;
605 case community_token_unknown:
606 default:
607 if (com)
608 community_free (com);
609 return NULL;
610 }
611 } while (str);
612
613 if (! com)
614 return NULL;
615
616 com_sort = community_uniq_sort (com);
617 community_free (com);
618
619 return com_sort;
620 }
621
622 /* Return communities hash entry count. */
623 unsigned long
community_count(void)624 community_count (void)
625 {
626 return comhash->count;
627 }
628
629 /* Return communities hash. */
630 struct hash *
community_hash(void)631 community_hash (void)
632 {
633 return comhash;
634 }
635
636 /* Initialize comminity related hash. */
637 void
community_init(void)638 community_init (void)
639 {
640 comhash = hash_create ((unsigned int (*) (void *))community_hash_make,
641 (int (*) (const void *, const void *))community_cmp);
642 }
643
644 void
community_finish(void)645 community_finish (void)
646 {
647 hash_free (comhash);
648 comhash = NULL;
649 }
650