1/* Community attribute related functions.
2   Copyright (C) 1998, 2001 Kunihiro Ishiguro
3
4This file is part of GNU Zebra.
5
6GNU Zebra is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 2, or (at your option) any
9later version.
10
11GNU Zebra is distributed in the hope that it will be useful, but
12WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with GNU Zebra; see the file COPYING.  If not, write to the Free
18Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
1902111-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. */
29struct hash *comhash;
30
31/* Allocate a new communities value.  */
32struct community *
33community_new ()
34{
35  return (struct community *) XCALLOC (MTYPE_COMMUNITY,
36				       sizeof (struct community));
37}
38
39/* Free communities value.  */
40void
41community_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. */
51void
52community_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. */
65void
66community_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 */
100struct community *
101community_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(). */
115int
116community_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
133int
134community_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
147u_int32_t
148community_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. */
162struct community *
163community_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.  */
197static char *
198community_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.  */
293struct community *
294community_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. */
320void
321community_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. */
340struct community *
341community_parse (char *pnt, u_short length)
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;
352  tmp.val = (u_int32_t *) pnt;
353
354  new = community_uniq_sort (&tmp);
355
356  return community_intern (new);
357}
358
359struct community *
360community_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. */
377char *
378community_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.*/
387unsigned int
388community_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
403int
404community_match (struct community *com1, struct community *com2)
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. */
434int
435community_cmp (struct community *com1, struct community *com2)
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. */
449struct community *
450community_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. */
465enum 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. */
475char *
476community_gettoken (char *buf, enum community_token *token, u_int32_t *val)
477{
478  char *p = buf;
479
480  /* Skip white space. */
481  while (isspace ((int) *p))
482    p++;
483
484  /* Check the end of the line. */
485  if (*p == '\0')
486    return NULL;
487
488  /* Well known community string check. */
489  if (isalpha ((int) *p))
490    {
491      if (strncmp (p, "internet", strlen ("internet")) == 0)
492	{
493	  *val = COMMUNITY_INTERNET;
494	  *token = community_token_no_export;
495	  p += strlen ("internet");
496	  return p;
497	}
498      if (strncmp (p, "no-export", strlen ("no-export")) == 0)
499	{
500	  *val = COMMUNITY_NO_EXPORT;
501	  *token = community_token_no_export;
502	  p += strlen ("no-export");
503	  return p;
504	}
505      if (strncmp (p, "no-advertise", strlen ("no-advertise")) == 0)
506	{
507	  *val = COMMUNITY_NO_ADVERTISE;
508	  *token = community_token_no_advertise;
509	  p += strlen ("no-advertise");
510	  return p;
511	}
512      if (strncmp (p, "local-AS", strlen ("local-AS")) == 0)
513	{
514	  *val = COMMUNITY_LOCAL_AS;
515	  *token = community_token_local_as;
516	  p += strlen ("local-AS");
517	  return p;
518	}
519
520      /* Unknown string. */
521      *token = community_token_unknown;
522      return p;
523    }
524
525  /* Community value. */
526  if (isdigit ((int) *p))
527    {
528      int separator = 0;
529      int digit = 0;
530      u_int32_t community_low = 0;
531      u_int32_t community_high = 0;
532
533      while (isdigit ((int) *p) || *p == ':')
534	{
535	  if (*p == ':')
536	    {
537	      if (separator)
538		{
539		  *token = community_token_unknown;
540		  return p;
541		}
542	      else
543		{
544		  separator = 1;
545		  digit = 0;
546		  community_high = community_low << 16;
547		  community_low = 0;
548		}
549	    }
550	  else
551	    {
552	      digit = 1;
553	      community_low *= 10;
554	      community_low += (*p - '0');
555	    }
556	  p++;
557	}
558      if (! digit)
559	{
560	  *token = community_token_unknown;
561	  return p;
562	}
563      *val = community_high + community_low;
564      *token = community_token_val;
565      return p;
566    }
567  *token = community_token_unknown;
568  return p;
569}
570
571/* convert string to community structure */
572struct community *
573community_str2com (char *str)
574{
575  struct community *com = NULL;
576  struct community *com_sort = NULL;
577  u_int32_t val;
578  enum community_token token;
579
580  while ((str = community_gettoken (str, &token, &val)))
581    {
582      switch (token)
583	{
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;
598	}
599    }
600
601  if (! com)
602    return NULL;
603
604  com_sort = community_uniq_sort (com);
605  community_free (com);
606
607  return com_sort;
608}
609
610/* Return communities hash entry count.  */
611unsigned long
612community_count ()
613{
614  return comhash->count;
615}
616
617/* Return communities hash.  */
618struct hash *
619community_hash ()
620{
621  return comhash;
622}
623
624/* Initialize comminity related hash. */
625void
626community_init ()
627{
628  comhash = hash_create (community_hash_make, community_cmp);
629}
630