]> git.sommitrealweird.co.uk Git - quagga-debian.git/blob - bgpd/bgp_community.c
New upstream version 1.2.3
[quagga-debian.git] / bgpd / bgp_community.c
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 *
33 community_new (void)
34 {
35   return (struct community *) XCALLOC (MTYPE_COMMUNITY,
36                                        sizeof (struct community));
37 }
38
39 /* Free communities value.  */
40 void
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
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
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 *
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
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
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
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 *
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 *
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 *
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
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 *
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 *
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 *
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
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
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
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 *
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 *
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 *
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
624 community_count (void)
625 {
626   return comhash->count;
627 }
628
629 /* Return communities hash.  */
630 struct hash *
631 community_hash (void)
632 {
633   return comhash;
634 }
635
636 /* Initialize comminity related hash. */
637 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
645 community_finish (void)
646 {
647   hash_free (comhash);
648   comhash = NULL;
649 }