]>
Commit | Line | Data |
---|---|---|
718e3744 | 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 | struct hash *comhash; | |
30 | ||
31 | /* Allocate a new communities value. */ | |
32 | struct community * | |
33 | community_new () | |
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 | 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 | memcpy (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 | 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 | /* When communities attribute is empty. */ | |
210 | if (com->size == 0) | |
211 | { | |
212 | str = XMALLOC (MTYPE_COMMUNITY_STR, 1); | |
213 | str[0] = '\0'; | |
214 | return str; | |
215 | } | |
216 | ||
217 | /* Memory allocation is time consuming work. So we calculate | |
218 | required string length first. */ | |
219 | len = 0; | |
220 | ||
221 | for (i = 0; i < com->size; i++) | |
222 | { | |
223 | memcpy (&comval, com_nthval (com, i), sizeof (u_int32_t)); | |
224 | comval = ntohl (comval); | |
225 | ||
226 | switch (comval) | |
227 | { | |
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; | |
243 | } | |
244 | } | |
245 | ||
246 | /* Allocate memory. */ | |
247 | str = pnt = XMALLOC (MTYPE_COMMUNITY_STR, len); | |
248 | first = 1; | |
249 | ||
250 | /* Fill in string. */ | |
251 | for (i = 0; i < com->size; i++) | |
252 | { | |
253 | memcpy (&comval, com_nthval (com, i), sizeof (u_int32_t)); | |
254 | comval = ntohl (comval); | |
255 | ||
256 | if (first) | |
257 | first = 0; | |
258 | else | |
259 | *pnt++ = ' '; | |
260 | ||
261 | switch (comval) | |
262 | { | |
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; | |
285 | } | |
286 | } | |
287 | *pnt = '\0'; | |
288 | ||
289 | return str; | |
290 | } | |
291 | ||
292 | /* Intern communities attribute. */ | |
293 | struct community * | |
294 | community_intern (struct community *com) | |
295 | { | |
296 | struct community *find; | |
297 | ||
298 | /* Assert this community structure is not interned. */ | |
299 | assert (com->refcnt == 0); | |
300 | ||
301 | /* Lookup community hash. */ | |
302 | find = (struct community *) hash_get (comhash, com, hash_alloc_intern); | |
303 | ||
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); | |
308 | ||
309 | /* Increment refrence counter. */ | |
310 | find->refcnt++; | |
311 | ||
312 | /* Make string. */ | |
313 | if (! find->str) | |
314 | find->str = community_com2str (find); | |
315 | ||
316 | return find; | |
317 | } | |
318 | ||
319 | /* Free community attribute. */ | |
320 | void | |
321 | community_unintern (struct community *com) | |
322 | { | |
323 | struct community *ret; | |
324 | ||
325 | if (com->refcnt) | |
326 | com->refcnt--; | |
327 | ||
328 | /* Pull off from hash. */ | |
329 | if (com->refcnt == 0) | |
330 | { | |
331 | /* Community value com must exist in hash. */ | |
332 | ret = (struct community *) hash_release (comhash, com); | |
333 | assert (ret != NULL); | |
334 | ||
335 | community_free (com); | |
336 | } | |
337 | } | |
338 | ||
339 | /* Create new community attribute. */ | |
340 | struct community * | |
5228ad27 | 341 | community_parse (u_int32_t *pnt, u_short length) |
718e3744 | 342 | { |
343 | struct community tmp; | |
344 | struct community *new; | |
345 | ||
346 | /* If length is malformed return NULL. */ | |
347 | if (length % 4) | |
348 | return NULL; | |
349 | ||
350 | /* Make temporary community for hash look up. */ | |
351 | tmp.size = length / 4; | |
5228ad27 | 352 | tmp.val = pnt; |
718e3744 | 353 | |
354 | new = community_uniq_sort (&tmp); | |
355 | ||
356 | return community_intern (new); | |
357 | } | |
358 | ||
359 | struct community * | |
360 | community_dup (struct community *com) | |
361 | { | |
362 | struct community *new; | |
363 | ||
364 | new = XCALLOC (MTYPE_COMMUNITY, sizeof (struct community)); | |
365 | new->size = com->size; | |
366 | if (new->size) | |
367 | { | |
368 | new->val = XMALLOC (MTYPE_COMMUNITY_VAL, com->size * 4); | |
369 | memcpy (new->val, com->val, com->size * 4); | |
370 | } | |
371 | else | |
372 | new->val = NULL; | |
373 | return new; | |
374 | } | |
375 | ||
376 | /* Retrun string representation of communities attribute. */ | |
377 | char * | |
378 | community_str (struct community *com) | |
379 | { | |
380 | if (! com->str) | |
381 | com->str = community_com2str (com); | |
382 | return com->str; | |
383 | } | |
384 | ||
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) | |
389 | { | |
390 | int c; | |
391 | unsigned int key; | |
392 | unsigned char *pnt; | |
393 | ||
394 | key = 0; | |
395 | pnt = (unsigned char *)com->val; | |
396 | ||
397 | for(c = 0; c < com->size * 4; c++) | |
398 | key += pnt[c]; | |
399 | ||
400 | return key; | |
401 | } | |
402 | ||
403 | int | |
fd79ac91 | 404 | community_match (const struct community *com1, const struct community *com2) |
718e3744 | 405 | { |
406 | int i = 0; | |
407 | int j = 0; | |
408 | ||
409 | if (com1 == NULL && com2 == NULL) | |
410 | return 1; | |
411 | ||
412 | if (com1 == NULL || com2 == NULL) | |
413 | return 0; | |
414 | ||
415 | if (com1->size < com2->size) | |
416 | return 0; | |
417 | ||
418 | /* Every community on com2 needs to be on com1 for this to match */ | |
419 | while (i < com1->size && j < com2->size) | |
420 | { | |
421 | if (memcmp (com1->val + i, com2->val + j, sizeof (u_int32_t)) == 0) | |
422 | j++; | |
423 | i++; | |
424 | } | |
425 | ||
426 | if (j == com2->size) | |
427 | return 1; | |
428 | else | |
429 | return 0; | |
430 | } | |
431 | ||
432 | /* If two aspath have same value then return 1 else return 0. This | |
433 | function is used by hash package. */ | |
434 | int | |
fd79ac91 | 435 | community_cmp (const struct community *com1, const struct community *com2) |
718e3744 | 436 | { |
437 | if (com1 == NULL && com2 == NULL) | |
438 | return 1; | |
439 | if (com1 == NULL || com2 == NULL) | |
440 | return 0; | |
441 | ||
442 | if (com1->size == com2->size) | |
443 | if (memcmp (com1->val, com2->val, com1->size * 4) == 0) | |
444 | return 1; | |
445 | return 0; | |
446 | } | |
447 | ||
448 | /* Add com2 to the end of com1. */ | |
449 | struct community * | |
450 | community_merge (struct community *com1, struct community *com2) | |
451 | { | |
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); | |
457 | ||
458 | memcpy (com1->val + com1->size, com2->val, com2->size * 4); | |
459 | com1->size += com2->size; | |
460 | ||
461 | return com1; | |
462 | } | |
463 | ||
464 | /* Community token enum. */ | |
465 | enum community_token | |
466 | { | |
467 | community_token_val, | |
468 | community_token_no_export, | |
469 | community_token_no_advertise, | |
470 | community_token_local_as, | |
471 | community_token_unknown | |
472 | }; | |
473 | ||
474 | /* Get next community token from string. */ | |
fd79ac91 | 475 | const char * |
476 | community_gettoken (const char *buf, enum community_token *token, | |
477 | u_int32_t *val) | |
718e3744 | 478 | { |
fd79ac91 | 479 | const char *p = buf; |
718e3744 | 480 | |
481 | /* Skip white space. */ | |
482 | while (isspace ((int) *p)) | |
483 | p++; | |
484 | ||
485 | /* Check the end of the line. */ | |
486 | if (*p == '\0') | |
487 | return NULL; | |
488 | ||
489 | /* Well known community string check. */ | |
490 | if (isalpha ((int) *p)) | |
491 | { | |
492 | if (strncmp (p, "internet", strlen ("internet")) == 0) | |
493 | { | |
494 | *val = COMMUNITY_INTERNET; | |
495 | *token = community_token_no_export; | |
496 | p += strlen ("internet"); | |
497 | return p; | |
498 | } | |
499 | if (strncmp (p, "no-export", strlen ("no-export")) == 0) | |
500 | { | |
501 | *val = COMMUNITY_NO_EXPORT; | |
502 | *token = community_token_no_export; | |
503 | p += strlen ("no-export"); | |
504 | return p; | |
505 | } | |
506 | if (strncmp (p, "no-advertise", strlen ("no-advertise")) == 0) | |
507 | { | |
508 | *val = COMMUNITY_NO_ADVERTISE; | |
509 | *token = community_token_no_advertise; | |
510 | p += strlen ("no-advertise"); | |
511 | return p; | |
512 | } | |
513 | if (strncmp (p, "local-AS", strlen ("local-AS")) == 0) | |
514 | { | |
515 | *val = COMMUNITY_LOCAL_AS; | |
516 | *token = community_token_local_as; | |
517 | p += strlen ("local-AS"); | |
518 | return p; | |
519 | } | |
520 | ||
521 | /* Unknown string. */ | |
522 | *token = community_token_unknown; | |
523 | return p; | |
524 | } | |
525 | ||
526 | /* Community value. */ | |
527 | if (isdigit ((int) *p)) | |
528 | { | |
529 | int separator = 0; | |
530 | int digit = 0; | |
531 | u_int32_t community_low = 0; | |
532 | u_int32_t community_high = 0; | |
533 | ||
534 | while (isdigit ((int) *p) || *p == ':') | |
535 | { | |
536 | if (*p == ':') | |
537 | { | |
538 | if (separator) | |
539 | { | |
540 | *token = community_token_unknown; | |
541 | return p; | |
542 | } | |
543 | else | |
544 | { | |
545 | separator = 1; | |
546 | digit = 0; | |
547 | community_high = community_low << 16; | |
548 | community_low = 0; | |
549 | } | |
550 | } | |
551 | else | |
552 | { | |
553 | digit = 1; | |
554 | community_low *= 10; | |
555 | community_low += (*p - '0'); | |
556 | } | |
557 | p++; | |
558 | } | |
559 | if (! digit) | |
560 | { | |
561 | *token = community_token_unknown; | |
562 | return p; | |
563 | } | |
564 | *val = community_high + community_low; | |
565 | *token = community_token_val; | |
566 | return p; | |
567 | } | |
568 | *token = community_token_unknown; | |
569 | return p; | |
570 | } | |
571 | ||
572 | /* convert string to community structure */ | |
573 | struct community * | |
fd79ac91 | 574 | community_str2com (const char *str) |
718e3744 | 575 | { |
576 | struct community *com = NULL; | |
577 | struct community *com_sort = NULL; | |
578 | u_int32_t val; | |
579 | enum community_token token; | |
580 | ||
581 | while ((str = community_gettoken (str, &token, &val))) | |
582 | { | |
583 | switch (token) | |
584 | { | |
585 | case community_token_val: | |
586 | case community_token_no_export: | |
587 | case community_token_no_advertise: | |
588 | case community_token_local_as: | |
589 | if (com == NULL) | |
590 | com = community_new(); | |
591 | community_add_val (com, val); | |
592 | break; | |
593 | case community_token_unknown: | |
594 | default: | |
595 | if (com) | |
596 | community_free (com); | |
597 | return NULL; | |
598 | break; | |
599 | } | |
600 | } | |
601 | ||
602 | if (! com) | |
603 | return NULL; | |
604 | ||
605 | com_sort = community_uniq_sort (com); | |
606 | community_free (com); | |
607 | ||
608 | return com_sort; | |
609 | } | |
610 | ||
611 | /* Return communities hash entry count. */ | |
612 | unsigned long | |
613 | community_count () | |
614 | { | |
615 | return comhash->count; | |
616 | } | |
617 | ||
618 | /* Return communities hash. */ | |
619 | struct hash * | |
620 | community_hash () | |
621 | { | |
622 | return comhash; | |
623 | } | |
624 | ||
625 | /* Initialize comminity related hash. */ | |
626 | void | |
627 | community_init () | |
628 | { | |
629 | comhash = hash_create (community_hash_make, community_cmp); | |
630 | } |