![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to bgp_community.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / bgpd|
Return to bgp_community.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / bgpd |
1.1 misho 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)
1.1.1.3 ! misho 81: memmove (com->val + i, com->val + (i + 1), c * sizeof (*val));
1.1 misho 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:
1.1.1.3 ! misho 147: u_int32_t
1.1 misho 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: {
1.1.1.2 misho 397: unsigned char *pnt = (unsigned char *)com->val;
398: int size = com->size * 4;
399: unsigned int key = 0;
1.1 misho 400: int c;
401:
1.1.1.2 misho 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:
1.1 misho 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: }