usbmodeswitch: Updated to v.1.2.6 from shibby's branch.
[tomato.git] / release / src / router / zebra / bgpd / bgp_community.c
blob83b1cc5e7021d7d5749a00c63651d61ca970b446
1 /* Community attribute related functions.
2 Copyright (C) 1998, 2001 Kunihiro Ishiguro
4 This file is part of GNU Zebra.
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.
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.
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. */
21 #include <zebra.h>
23 #include "hash.h"
24 #include "memory.h"
26 #include "bgpd/bgp_community.h"
28 /* Hash of community attribute. */
29 struct hash *comhash;
31 /* Allocate a new communities value. */
32 struct community *
33 community_new ()
35 return (struct community *) XCALLOC (MTYPE_COMMUNITY,
36 sizeof (struct community));
39 /* Free communities value. */
40 void
41 community_free (struct community *com)
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);
50 /* Add one community value to the community. */
51 void
52 community_add_val (struct community *com, u_int32_t val)
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));
60 val = htonl (val);
61 memcpy (com_lastval (com), &val, sizeof (u_int32_t));
64 /* Delete one community. */
65 void
66 community_del_val (struct community *com, u_int32_t *val)
68 int i = 0;
69 int c = 0;
71 if (! com->val)
72 return;
74 while (i < com->size)
76 if (memcmp (com->val + i, val, sizeof (u_int32_t)) == 0)
78 c = com->size -i -1;
80 if (c > 0)
81 memcpy (com->val + i, com->val + (i + 1), c * sizeof (val));
83 com->size--;
85 if (com->size > 0)
86 com->val = XREALLOC (MTYPE_COMMUNITY_VAL, com->val,
87 com_length (com));
88 else
90 XFREE (MTYPE_COMMUNITY_VAL, com->val);
91 com->val = NULL;
93 return;
95 i++;
99 /* Delete all communities listed in com2 from com1 */
100 struct community *
101 community_delete (struct community *com1, struct community *com2)
103 int i = 0;
105 while(i < com2->size)
107 community_del_val (com1, com2->val + i);
108 i++;
111 return com1;
114 /* Callback function from qsort(). */
116 community_compare (const void *a1, const void *a2)
118 u_int32_t v1;
119 u_int32_t v2;
121 memcpy (&v1, a1, sizeof (u_int32_t));
122 memcpy (&v2, a2, sizeof (u_int32_t));
123 v1 = ntohl (v1);
124 v2 = ntohl (v2);
126 if (v1 < v2)
127 return -1;
128 if (v1 > v2)
129 return 1;
130 return 0;
134 community_include (struct community *com, u_int32_t val)
136 int i;
138 val = htonl (val);
140 for (i = 0; i < com->size; i++)
141 if (memcmp (&val, com_nthval (com, i), sizeof (u_int32_t)) == 0)
142 return 1;
144 return 0;
147 u_int32_t
148 community_val_get (struct community *com, int i)
150 u_char *p;
151 u_int32_t val;
153 p = (u_char *) com->val;
154 p += (i * 4);
156 memcpy (&val, p, sizeof (u_int32_t));
158 return ntohl (val);
161 /* Sort and uniq given community. */
162 struct community *
163 community_uniq_sort (struct community *com)
165 int i;
166 struct community *new;
167 u_int32_t val;
169 if (! com)
170 return NULL;
172 new = community_new ();;
174 for (i = 0; i < com->size; i++)
176 val = community_val_get (com, i);
178 if (! community_include (new, val))
179 community_add_val (new, val);
182 qsort (new->val, new->size, sizeof (u_int32_t), community_compare);
184 return new;
187 /* Convert communities attribute to string.
189 For Well-known communities value, below keyword is used.
191 0x0 "internet"
192 0xFFFFFF01 "no-export"
193 0xFFFFFF02 "no-advertise"
194 0xFFFFFF03 "local-AS"
196 For other values, "AS:VAL" format is used. */
197 static char *
198 community_com2str (struct community *com)
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;
209 /* When communities attribute is empty. */
210 if (com->size == 0)
212 str = XMALLOC (MTYPE_COMMUNITY_STR, 1);
213 str[0] = '\0';
214 return str;
217 /* Memory allocation is time consuming work. So we calculate
218 required string length first. */
219 len = 0;
221 for (i = 0; i < com->size; i++)
223 memcpy (&comval, com_nthval (com, i), sizeof (u_int32_t));
224 comval = ntohl (comval);
226 switch (comval)
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;
246 /* Allocate memory. */
247 str = pnt = XMALLOC (MTYPE_COMMUNITY_STR, len);
248 first = 1;
250 /* Fill in string. */
251 for (i = 0; i < com->size; i++)
253 memcpy (&comval, com_nthval (com, i), sizeof (u_int32_t));
254 comval = ntohl (comval);
256 if (first)
257 first = 0;
258 else
259 *pnt++ = ' ';
261 switch (comval)
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;
287 *pnt = '\0';
289 return str;
292 /* Intern communities attribute. */
293 struct community *
294 community_intern (struct community *com)
296 struct community *find;
298 /* Assert this community structure is not interned. */
299 assert (com->refcnt == 0);
301 /* Lookup community hash. */
302 find = (struct community *) hash_get (comhash, com, hash_alloc_intern);
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);
309 /* Increment refrence counter. */
310 find->refcnt++;
312 /* Make string. */
313 if (! find->str)
314 find->str = community_com2str (find);
316 return find;
319 /* Free community attribute. */
320 void
321 community_unintern (struct community *com)
323 struct community *ret;
325 if (com->refcnt)
326 com->refcnt--;
328 /* Pull off from hash. */
329 if (com->refcnt == 0)
331 /* Community value com must exist in hash. */
332 ret = (struct community *) hash_release (comhash, com);
333 assert (ret != NULL);
335 community_free (com);
339 /* Create new community attribute. */
340 struct community *
341 community_parse (char *pnt, u_short length)
343 struct community tmp;
344 struct community *new;
346 /* If length is malformed return NULL. */
347 if (length % 4)
348 return NULL;
350 /* Make temporary community for hash look up. */
351 tmp.size = length / 4;
352 tmp.val = (u_int32_t *) pnt;
354 new = community_uniq_sort (&tmp);
356 return community_intern (new);
359 struct community *
360 community_dup (struct community *com)
362 struct community *new;
364 new = XCALLOC (MTYPE_COMMUNITY, sizeof (struct community));
365 new->size = com->size;
366 if (new->size)
368 new->val = XMALLOC (MTYPE_COMMUNITY_VAL, com->size * 4);
369 memcpy (new->val, com->val, com->size * 4);
371 else
372 new->val = NULL;
373 return new;
376 /* Retrun string representation of communities attribute. */
377 char *
378 community_str (struct community *com)
380 if (! com->str)
381 com->str = community_com2str (com);
382 return com->str;
385 /* Make hash value of community attribute. This function is used by
386 hash package.*/
387 unsigned int
388 community_hash_make (struct community *com)
390 int c;
391 unsigned int key;
392 unsigned char *pnt;
394 key = 0;
395 pnt = (unsigned char *)com->val;
397 for(c = 0; c < com->size * 4; c++)
398 key += pnt[c];
400 return key;
404 community_match (struct community *com1, struct community *com2)
406 int i = 0;
407 int j = 0;
409 if (com1 == NULL && com2 == NULL)
410 return 1;
412 if (com1 == NULL || com2 == NULL)
413 return 0;
415 if (com1->size < com2->size)
416 return 0;
418 /* Every community on com2 needs to be on com1 for this to match */
419 while (i < com1->size && j < com2->size)
421 if (memcmp (com1->val + i, com2->val + j, sizeof (u_int32_t)) == 0)
422 j++;
423 i++;
426 if (j == com2->size)
427 return 1;
428 else
429 return 0;
432 /* If two aspath have same value then return 1 else return 0. This
433 function is used by hash package. */
435 community_cmp (struct community *com1, struct community *com2)
437 if (com1 == NULL && com2 == NULL)
438 return 1;
439 if (com1 == NULL || com2 == NULL)
440 return 0;
442 if (com1->size == com2->size)
443 if (memcmp (com1->val, com2->val, com1->size * 4) == 0)
444 return 1;
445 return 0;
448 /* Add com2 to the end of com1. */
449 struct community *
450 community_merge (struct community *com1, struct community *com2)
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);
458 memcpy (com1->val + com1->size, com2->val, com2->size * 4);
459 com1->size += com2->size;
461 return com1;
464 /* Community token enum. */
465 enum community_token
467 community_token_val,
468 community_token_no_export,
469 community_token_no_advertise,
470 community_token_local_as,
471 community_token_unknown
474 /* Get next community token from string. */
475 char *
476 community_gettoken (char *buf, enum community_token *token, u_int32_t *val)
478 char *p = buf;
480 /* Skip white space. */
481 while (isspace ((int) *p))
482 p++;
484 /* Check the end of the line. */
485 if (*p == '\0')
486 return NULL;
488 /* Well known community string check. */
489 if (isalpha ((int) *p))
491 if (strncmp (p, "internet", strlen ("internet")) == 0)
493 *val = COMMUNITY_INTERNET;
494 *token = community_token_no_export;
495 p += strlen ("internet");
496 return p;
498 if (strncmp (p, "no-export", strlen ("no-export")) == 0)
500 *val = COMMUNITY_NO_EXPORT;
501 *token = community_token_no_export;
502 p += strlen ("no-export");
503 return p;
505 if (strncmp (p, "no-advertise", strlen ("no-advertise")) == 0)
507 *val = COMMUNITY_NO_ADVERTISE;
508 *token = community_token_no_advertise;
509 p += strlen ("no-advertise");
510 return p;
512 if (strncmp (p, "local-AS", strlen ("local-AS")) == 0)
514 *val = COMMUNITY_LOCAL_AS;
515 *token = community_token_local_as;
516 p += strlen ("local-AS");
517 return p;
520 /* Unknown string. */
521 *token = community_token_unknown;
522 return p;
525 /* Community value. */
526 if (isdigit ((int) *p))
528 int separator = 0;
529 int digit = 0;
530 u_int32_t community_low = 0;
531 u_int32_t community_high = 0;
533 while (isdigit ((int) *p) || *p == ':')
535 if (*p == ':')
537 if (separator)
539 *token = community_token_unknown;
540 return p;
542 else
544 separator = 1;
545 digit = 0;
546 community_high = community_low << 16;
547 community_low = 0;
550 else
552 digit = 1;
553 community_low *= 10;
554 community_low += (*p - '0');
556 p++;
558 if (! digit)
560 *token = community_token_unknown;
561 return p;
563 *val = community_high + community_low;
564 *token = community_token_val;
565 return p;
567 *token = community_token_unknown;
568 return p;
571 /* convert string to community structure */
572 struct community *
573 community_str2com (char *str)
575 struct community *com = NULL;
576 struct community *com_sort = NULL;
577 u_int32_t val;
578 enum community_token token;
580 while ((str = community_gettoken (str, &token, &val)))
582 switch (token)
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;
601 if (! com)
602 return NULL;
604 com_sort = community_uniq_sort (com);
605 community_free (com);
607 return com_sort;
610 /* Return communities hash entry count. */
611 unsigned long
612 community_count ()
614 return comhash->count;
617 /* Return communities hash. */
618 struct hash *
619 community_hash ()
621 return comhash;
624 /* Initialize comminity related hash. */
625 void
626 community_init ()
628 comhash = hash_create (community_hash_make, community_cmp);