Line data Source code
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 0 : community_new (void)
34 : {
35 0 : return (struct community *) XCALLOC (MTYPE_COMMUNITY,
36 : sizeof (struct community));
37 : }
38 :
39 : /* Free communities value. */
40 : void
41 0 : community_free (struct community *com)
42 : {
43 0 : if (com->val)
44 0 : XFREE (MTYPE_COMMUNITY_VAL, com->val);
45 0 : if (com->str)
46 0 : XFREE (MTYPE_COMMUNITY_STR, com->str);
47 0 : XFREE (MTYPE_COMMUNITY, com);
48 0 : }
49 :
50 : /* Add one community value to the community. */
51 : static void
52 0 : community_add_val (struct community *com, u_int32_t val)
53 : {
54 0 : com->size++;
55 0 : if (com->val)
56 0 : com->val = XREALLOC (MTYPE_COMMUNITY_VAL, com->val, com_length (com));
57 : else
58 0 : com->val = XMALLOC (MTYPE_COMMUNITY_VAL, com_length (com));
59 :
60 0 : val = htonl (val);
61 0 : memcpy (com_lastval (com), &val, sizeof (u_int32_t));
62 0 : }
63 :
64 : /* Delete one community. */
65 : void
66 0 : community_del_val (struct community *com, u_int32_t *val)
67 : {
68 0 : int i = 0;
69 0 : int c = 0;
70 :
71 0 : if (! com->val)
72 0 : return;
73 :
74 0 : while (i < com->size)
75 : {
76 0 : if (memcmp (com->val + i, val, sizeof (u_int32_t)) == 0)
77 : {
78 0 : c = com->size -i -1;
79 :
80 0 : if (c > 0)
81 0 : memcpy (com->val + i, com->val + (i + 1), c * sizeof (*val));
82 :
83 0 : com->size--;
84 :
85 0 : if (com->size > 0)
86 0 : com->val = XREALLOC (MTYPE_COMMUNITY_VAL, com->val,
87 : com_length (com));
88 : else
89 : {
90 0 : XFREE (MTYPE_COMMUNITY_VAL, com->val);
91 0 : com->val = NULL;
92 : }
93 0 : return;
94 : }
95 0 : i++;
96 : }
97 : }
98 :
99 : /* Delete all communities listed in com2 from com1 */
100 : struct community *
101 0 : community_delete (struct community *com1, struct community *com2)
102 : {
103 0 : int i = 0;
104 :
105 0 : while(i < com2->size)
106 : {
107 0 : community_del_val (com1, com2->val + i);
108 0 : i++;
109 : }
110 :
111 0 : return com1;
112 : }
113 :
114 : /* Callback function from qsort(). */
115 : static int
116 0 : community_compare (const void *a1, const void *a2)
117 : {
118 : u_int32_t v1;
119 : u_int32_t v2;
120 :
121 0 : memcpy (&v1, a1, sizeof (u_int32_t));
122 0 : memcpy (&v2, a2, sizeof (u_int32_t));
123 0 : v1 = ntohl (v1);
124 0 : v2 = ntohl (v2);
125 :
126 0 : if (v1 < v2)
127 0 : return -1;
128 0 : if (v1 > v2)
129 0 : return 1;
130 0 : return 0;
131 : }
132 :
133 : int
134 0 : community_include (struct community *com, u_int32_t val)
135 : {
136 : int i;
137 :
138 0 : val = htonl (val);
139 :
140 0 : for (i = 0; i < com->size; i++)
141 0 : if (memcmp (&val, com_nthval (com, i), sizeof (u_int32_t)) == 0)
142 0 : return 1;
143 :
144 0 : return 0;
145 : }
146 :
147 : static u_int32_t
148 0 : community_val_get (struct community *com, int i)
149 : {
150 : u_char *p;
151 : u_int32_t val;
152 :
153 0 : p = (u_char *) com->val;
154 0 : p += (i * 4);
155 :
156 0 : memcpy (&val, p, sizeof (u_int32_t));
157 :
158 0 : return ntohl (val);
159 : }
160 :
161 : /* Sort and uniq given community. */
162 : struct community *
163 0 : community_uniq_sort (struct community *com)
164 : {
165 : int i;
166 : struct community *new;
167 : u_int32_t val;
168 :
169 0 : if (! com)
170 0 : return NULL;
171 :
172 0 : new = community_new ();;
173 :
174 0 : for (i = 0; i < com->size; i++)
175 : {
176 0 : val = community_val_get (com, i);
177 :
178 0 : if (! community_include (new, val))
179 0 : community_add_val (new, val);
180 : }
181 :
182 0 : qsort (new->val, new->size, sizeof (u_int32_t), community_compare);
183 :
184 0 : 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 0 : 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 0 : if (!com)
210 0 : return NULL;
211 :
212 : /* When communities attribute is empty. */
213 0 : if (com->size == 0)
214 : {
215 0 : str = XMALLOC (MTYPE_COMMUNITY_STR, 1);
216 0 : str[0] = '\0';
217 0 : return str;
218 : }
219 :
220 : /* Memory allocation is time consuming work. So we calculate
221 : required string length first. */
222 0 : len = 0;
223 :
224 0 : for (i = 0; i < com->size; i++)
225 : {
226 0 : memcpy (&comval, com_nthval (com, i), sizeof (u_int32_t));
227 0 : comval = ntohl (comval);
228 :
229 0 : switch (comval)
230 : {
231 : case COMMUNITY_INTERNET:
232 0 : len += strlen (" internet");
233 0 : break;
234 : case COMMUNITY_NO_EXPORT:
235 0 : len += strlen (" no-export");
236 0 : break;
237 : case COMMUNITY_NO_ADVERTISE:
238 0 : len += strlen (" no-advertise");
239 0 : break;
240 : case COMMUNITY_LOCAL_AS:
241 0 : len += strlen (" local-AS");
242 0 : break;
243 : default:
244 0 : len += strlen (" 65536:65535");
245 0 : break;
246 : }
247 : }
248 :
249 : /* Allocate memory. */
250 0 : str = pnt = XMALLOC (MTYPE_COMMUNITY_STR, len);
251 0 : first = 1;
252 :
253 : /* Fill in string. */
254 0 : for (i = 0; i < com->size; i++)
255 : {
256 0 : memcpy (&comval, com_nthval (com, i), sizeof (u_int32_t));
257 0 : comval = ntohl (comval);
258 :
259 0 : if (first)
260 0 : first = 0;
261 : else
262 0 : *pnt++ = ' ';
263 :
264 0 : switch (comval)
265 : {
266 : case COMMUNITY_INTERNET:
267 0 : strcpy (pnt, "internet");
268 0 : pnt += strlen ("internet");
269 0 : break;
270 : case COMMUNITY_NO_EXPORT:
271 0 : strcpy (pnt, "no-export");
272 0 : pnt += strlen ("no-export");
273 0 : break;
274 : case COMMUNITY_NO_ADVERTISE:
275 0 : strcpy (pnt, "no-advertise");
276 0 : pnt += strlen ("no-advertise");
277 0 : break;
278 : case COMMUNITY_LOCAL_AS:
279 0 : strcpy (pnt, "local-AS");
280 0 : pnt += strlen ("local-AS");
281 0 : break;
282 : default:
283 0 : as = (comval >> 16) & 0xFFFF;
284 0 : val = comval & 0xFFFF;
285 0 : sprintf (pnt, "%u:%d", as, val);
286 0 : pnt += strlen (pnt);
287 0 : break;
288 : }
289 : }
290 0 : *pnt = '\0';
291 :
292 0 : return str;
293 : }
294 :
295 : /* Intern communities attribute. */
296 : struct community *
297 0 : community_intern (struct community *com)
298 : {
299 : struct community *find;
300 :
301 : /* Assert this community structure is not interned. */
302 0 : assert (com->refcnt == 0);
303 :
304 : /* Lookup community hash. */
305 0 : 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 0 : if (find != com)
310 0 : community_free (com);
311 :
312 : /* Increment refrence counter. */
313 0 : find->refcnt++;
314 :
315 : /* Make string. */
316 0 : if (! find->str)
317 0 : find->str = community_com2str (find);
318 :
319 0 : return find;
320 : }
321 :
322 : /* Free community attribute. */
323 : void
324 0 : community_unintern (struct community **com)
325 : {
326 : struct community *ret;
327 :
328 0 : if ((*com)->refcnt)
329 0 : (*com)->refcnt--;
330 :
331 : /* Pull off from hash. */
332 0 : if ((*com)->refcnt == 0)
333 : {
334 : /* Community value com must exist in hash. */
335 0 : ret = (struct community *) hash_release (comhash, *com);
336 0 : assert (ret != NULL);
337 :
338 0 : community_free (*com);
339 0 : *com = NULL;
340 : }
341 0 : }
342 :
343 : /* Create new community attribute. */
344 : struct community *
345 0 : 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 0 : if (length % 4)
352 0 : return NULL;
353 :
354 : /* Make temporary community for hash look up. */
355 0 : tmp.size = length / 4;
356 0 : tmp.val = pnt;
357 :
358 0 : new = community_uniq_sort (&tmp);
359 :
360 0 : return community_intern (new);
361 : }
362 :
363 : struct community *
364 0 : community_dup (struct community *com)
365 : {
366 : struct community *new;
367 :
368 0 : new = XCALLOC (MTYPE_COMMUNITY, sizeof (struct community));
369 0 : new->size = com->size;
370 0 : if (new->size)
371 : {
372 0 : new->val = XMALLOC (MTYPE_COMMUNITY_VAL, com->size * 4);
373 0 : memcpy (new->val, com->val, com->size * 4);
374 : }
375 : else
376 0 : new->val = NULL;
377 0 : return new;
378 : }
379 :
380 : /* Retrun string representation of communities attribute. */
381 : char *
382 0 : community_str (struct community *com)
383 : {
384 0 : if (!com)
385 0 : return NULL;
386 :
387 0 : if (! com->str)
388 0 : com->str = community_com2str (com);
389 0 : return com->str;
390 : }
391 :
392 : /* Make hash value of community attribute. This function is used by
393 : hash package.*/
394 : unsigned int
395 0 : community_hash_make (struct community *com)
396 : {
397 0 : unsigned char *pnt = (unsigned char *)com->val;
398 0 : int size = com->size * 4;
399 0 : unsigned int key = 0;
400 : int c;
401 :
402 0 : for (c = 0; c < size; c += 4)
403 : {
404 0 : key += pnt[c];
405 0 : key += pnt[c + 1];
406 0 : key += pnt[c + 2];
407 0 : key += pnt[c + 3];
408 : }
409 :
410 0 : return key;
411 : }
412 :
413 : int
414 0 : community_match (const struct community *com1, const struct community *com2)
415 : {
416 0 : int i = 0;
417 0 : int j = 0;
418 :
419 0 : if (com1 == NULL && com2 == NULL)
420 0 : return 1;
421 :
422 0 : if (com1 == NULL || com2 == NULL)
423 0 : return 0;
424 :
425 0 : if (com1->size < com2->size)
426 0 : return 0;
427 :
428 : /* Every community on com2 needs to be on com1 for this to match */
429 0 : while (i < com1->size && j < com2->size)
430 : {
431 0 : if (memcmp (com1->val + i, com2->val + j, sizeof (u_int32_t)) == 0)
432 0 : j++;
433 0 : i++;
434 : }
435 :
436 0 : if (j == com2->size)
437 0 : return 1;
438 : else
439 0 : 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 0 : community_cmp (const struct community *com1, const struct community *com2)
446 : {
447 0 : if (com1 == NULL && com2 == NULL)
448 0 : return 1;
449 0 : if (com1 == NULL || com2 == NULL)
450 0 : return 0;
451 :
452 0 : if (com1->size == com2->size)
453 0 : if (memcmp (com1->val, com2->val, com1->size * 4) == 0)
454 0 : return 1;
455 0 : return 0;
456 : }
457 :
458 : /* Add com2 to the end of com1. */
459 : struct community *
460 0 : community_merge (struct community *com1, struct community *com2)
461 : {
462 0 : if (com1->val)
463 0 : com1->val = XREALLOC (MTYPE_COMMUNITY_VAL, com1->val,
464 : (com1->size + com2->size) * 4);
465 : else
466 0 : com1->val = XMALLOC (MTYPE_COMMUNITY_VAL, (com1->size + com2->size) * 4);
467 :
468 0 : memcpy (com1->val + com1->size, com2->val, com2->size * 4);
469 0 : com1->size += com2->size;
470 :
471 0 : 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 0 : community_gettoken (const char *buf, enum community_token *token,
487 : u_int32_t *val)
488 : {
489 0 : const char *p = buf;
490 :
491 : /* Skip white space. */
492 0 : while (isspace ((int) *p))
493 0 : p++;
494 :
495 : /* Check the end of the line. */
496 0 : if (*p == '\0')
497 0 : return NULL;
498 :
499 : /* Well known community string check. */
500 0 : if (isalpha ((int) *p))
501 : {
502 0 : if (strncmp (p, "internet", strlen ("internet")) == 0)
503 : {
504 0 : *val = COMMUNITY_INTERNET;
505 0 : *token = community_token_no_export;
506 0 : p += strlen ("internet");
507 0 : return p;
508 : }
509 0 : if (strncmp (p, "no-export", strlen ("no-export")) == 0)
510 : {
511 0 : *val = COMMUNITY_NO_EXPORT;
512 0 : *token = community_token_no_export;
513 0 : p += strlen ("no-export");
514 0 : return p;
515 : }
516 0 : if (strncmp (p, "no-advertise", strlen ("no-advertise")) == 0)
517 : {
518 0 : *val = COMMUNITY_NO_ADVERTISE;
519 0 : *token = community_token_no_advertise;
520 0 : p += strlen ("no-advertise");
521 0 : return p;
522 : }
523 0 : if (strncmp (p, "local-AS", strlen ("local-AS")) == 0)
524 : {
525 0 : *val = COMMUNITY_LOCAL_AS;
526 0 : *token = community_token_local_as;
527 0 : p += strlen ("local-AS");
528 0 : return p;
529 : }
530 :
531 : /* Unknown string. */
532 0 : *token = community_token_unknown;
533 0 : return NULL;
534 : }
535 :
536 : /* Community value. */
537 0 : if (isdigit ((int) *p))
538 : {
539 0 : int separator = 0;
540 0 : int digit = 0;
541 0 : u_int32_t community_low = 0;
542 0 : u_int32_t community_high = 0;
543 :
544 0 : while (isdigit ((int) *p) || *p == ':')
545 : {
546 0 : if (*p == ':')
547 : {
548 0 : if (separator)
549 : {
550 0 : *token = community_token_unknown;
551 0 : return NULL;
552 : }
553 : else
554 : {
555 0 : separator = 1;
556 0 : digit = 0;
557 0 : community_high = community_low << 16;
558 0 : community_low = 0;
559 : }
560 : }
561 : else
562 : {
563 0 : digit = 1;
564 0 : community_low *= 10;
565 0 : community_low += (*p - '0');
566 : }
567 0 : p++;
568 : }
569 0 : if (! digit)
570 : {
571 0 : *token = community_token_unknown;
572 0 : return NULL;
573 : }
574 0 : *val = community_high + community_low;
575 0 : *token = community_token_val;
576 0 : return p;
577 : }
578 0 : *token = community_token_unknown;
579 0 : return NULL;
580 : }
581 :
582 : /* convert string to community structure */
583 : struct community *
584 0 : community_str2com (const char *str)
585 : {
586 0 : struct community *com = NULL;
587 0 : struct community *com_sort = NULL;
588 0 : u_int32_t val = 0;
589 0 : enum community_token token = community_token_unknown;
590 :
591 : do
592 : {
593 0 : str = community_gettoken (str, &token, &val);
594 :
595 0 : 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 0 : if (com == NULL)
602 0 : com = community_new();
603 0 : community_add_val (com, val);
604 0 : break;
605 : case community_token_unknown:
606 : default:
607 0 : if (com)
608 0 : community_free (com);
609 0 : return NULL;
610 : }
611 0 : } while (str);
612 :
613 0 : if (! com)
614 0 : return NULL;
615 :
616 0 : com_sort = community_uniq_sort (com);
617 0 : community_free (com);
618 :
619 0 : return com_sort;
620 : }
621 :
622 : /* Return communities hash entry count. */
623 : unsigned long
624 0 : community_count (void)
625 : {
626 0 : return comhash->count;
627 : }
628 :
629 : /* Return communities hash. */
630 : struct hash *
631 0 : community_hash (void)
632 : {
633 0 : return comhash;
634 : }
635 :
636 : /* Initialize comminity related hash. */
637 : void
638 1 : community_init (void)
639 : {
640 1 : comhash = hash_create ((unsigned int (*) (void *))community_hash_make,
641 : (int (*) (const void *, const void *))community_cmp);
642 1 : }
643 :
644 : void
645 0 : community_finish (void)
646 : {
647 0 : hash_free (comhash);
648 0 : comhash = NULL;
649 0 : }
|
