Annotation of embedaddon/quagga/bgpd/bgp_aspath.c, revision 1.1.1.1
1.1 misho 1: /* AS path management routines.
2: Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro
3: Copyright (C) 2005 Sun Microsystems, Inc.
4:
5: This file is part of GNU Zebra.
6:
7: GNU Zebra is free software; you can redistribute it and/or modify it
8: under the terms of the GNU General Public License as published by the
9: Free Software Foundation; either version 2, or (at your option) any
10: later version.
11:
12: GNU Zebra is distributed in the hope that it will be useful, but
13: WITHOUT ANY WARRANTY; without even the implied warranty of
14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15: General Public License for more details.
16:
17: You should have received a copy of the GNU General Public License
18: along with GNU Zebra; see the file COPYING. If not, write to the Free
19: Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
20: 02111-1307, USA. */
21:
22: #include <zebra.h>
23:
24: #include "hash.h"
25: #include "memory.h"
26: #include "vector.h"
27: #include "vty.h"
28: #include "str.h"
29: #include "log.h"
30: #include "stream.h"
31: #include "jhash.h"
32:
33: #include "bgpd/bgpd.h"
34: #include "bgpd/bgp_aspath.h"
35: #include "bgpd/bgp_debug.h"
36: #include "bgpd/bgp_attr.h"
37:
38: /* Attr. Flags and Attr. Type Code. */
39: #define AS_HEADER_SIZE 2
40:
41: /* Now FOUR octets are used for AS value. */
42: #define AS_VALUE_SIZE sizeof (as_t)
43: /* This is the old one */
44: #define AS16_VALUE_SIZE sizeof (as16_t)
45:
46: /* Maximum protocol segment length value */
47: #define AS_SEGMENT_MAX 255
48:
49: /* The following length and size macros relate specifically to Quagga's
50: * internal representation of AS-Segments, not per se to the on-wire
51: * sizes and lengths. At present (200508) they sort of match, however
52: * the ONLY functions which should now about the on-wire syntax are
53: * aspath_put, assegment_put and assegment_parse.
54: *
55: * aspath_put returns bytes written, the only definitive record of
56: * size of wire-format attribute..
57: */
58:
59: /* Calculated size in bytes of ASN segment data to hold N ASN's */
60: #define ASSEGMENT_DATA_SIZE(N,S) \
61: ((N) * ( (S) ? AS_VALUE_SIZE : AS16_VALUE_SIZE) )
62:
63: /* Calculated size of segment struct to hold N ASN's */
64: #define ASSEGMENT_SIZE(N,S) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N,S))
65:
66: /* AS segment octet length. */
67: #define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S)
68:
69: /* AS_SEQUENCE segments can be packed together */
70: /* Can the types of X and Y be considered for packing? */
71: #define ASSEGMENT_TYPES_PACKABLE(X,Y) \
72: ( ((X)->type == (Y)->type) \
73: && ((X)->type == AS_SEQUENCE))
74: /* Types and length of X,Y suitable for packing? */
75: #define ASSEGMENTS_PACKABLE(X,Y) \
76: ( ASSEGMENT_TYPES_PACKABLE( (X), (Y)) \
77: && ( ((X)->length + (Y)->length) <= AS_SEGMENT_MAX ) )
78:
79: /* As segment header - the on-wire representation
80: * NOT the internal representation!
81: */
82: struct assegment_header
83: {
84: u_char type;
85: u_char length;
86: };
87:
88: /* Hash for aspath. This is the top level structure of AS path. */
89: static struct hash *ashash;
90:
91: /* Stream for SNMP. See aspath_snmp_pathseg */
92: static struct stream *snmp_stream;
93:
94: static inline as_t *
95: assegment_data_new (int num)
96: {
97: return (XCALLOC (MTYPE_AS_SEG_DATA, ASSEGMENT_DATA_SIZE (num, 1)));
98: }
99:
100: static inline void
101: assegment_data_free (as_t *asdata)
102: {
103: XFREE (MTYPE_AS_SEG_DATA,asdata);
104: }
105:
106: /* Get a new segment. Note that 0 is an allowed length,
107: * and will result in a segment with no allocated data segment.
108: * the caller should immediately assign data to the segment, as the segment
109: * otherwise is not generally valid
110: */
111: static struct assegment *
112: assegment_new (u_char type, u_short length)
113: {
114: struct assegment *new;
115:
116: new = XCALLOC (MTYPE_AS_SEG, sizeof (struct assegment));
117:
118: if (length)
119: new->as = assegment_data_new (length);
120:
121: new->length = length;
122: new->type = type;
123:
124: return new;
125: }
126:
127: static void
128: assegment_free (struct assegment *seg)
129: {
130: if (!seg)
131: return;
132:
133: if (seg->as)
134: XFREE (MTYPE_AS_SEG_DATA, seg->as);
135: memset (seg, 0xfe, sizeof(struct assegment));
136: XFREE (MTYPE_AS_SEG, seg);
137:
138: return;
139: }
140:
141: /* free entire chain of segments */
142: static void
143: assegment_free_all (struct assegment *seg)
144: {
145: struct assegment *prev;
146:
147: while (seg)
148: {
149: prev = seg;
150: seg = seg->next;
151: assegment_free (prev);
152: }
153: }
154:
155: /* Duplicate just the given assegment and its data */
156: static struct assegment *
157: assegment_dup (struct assegment *seg)
158: {
159: struct assegment *new;
160:
161: new = assegment_new (seg->type, seg->length);
162: memcpy (new->as, seg->as, ASSEGMENT_DATA_SIZE (new->length, 1) );
163:
164: return new;
165: }
166:
167: /* Duplicate entire chain of assegments, return the head */
168: static struct assegment *
169: assegment_dup_all (struct assegment *seg)
170: {
171: struct assegment *new = NULL;
172: struct assegment *head = NULL;
173:
174: while (seg)
175: {
176: if (head)
177: {
178: new->next = assegment_dup (seg);
179: new = new->next;
180: }
181: else
182: head = new = assegment_dup (seg);
183:
184: seg = seg->next;
185: }
186: return head;
187: }
188:
189: /* prepend the as number to given segment, given num of times */
190: static struct assegment *
191: assegment_prepend_asns (struct assegment *seg, as_t asnum, int num)
192: {
193: as_t *newas;
194:
195: if (!num)
196: return seg;
197:
198: if (num >= AS_SEGMENT_MAX)
199: return seg; /* we don't do huge prepends */
200:
201: newas = assegment_data_new (seg->length + num);
202:
203: if (newas)
204: {
205: int i;
206: for (i = 0; i < num; i++)
207: newas[i] = asnum;
208:
209: memcpy (newas + num, seg->as, ASSEGMENT_DATA_SIZE (seg->length, 1));
210: XFREE (MTYPE_AS_SEG_DATA, seg->as);
211: seg->as = newas;
212: seg->length += num;
213: return seg;
214: }
215:
216: assegment_free_all (seg);
217: return NULL;
218: }
219:
220: /* append given array of as numbers to the segment */
221: static struct assegment *
222: assegment_append_asns (struct assegment *seg, as_t *asnos, int num)
223: {
224: as_t *newas;
225:
226: newas = XREALLOC (MTYPE_AS_SEG_DATA, seg->as,
227: ASSEGMENT_DATA_SIZE (seg->length + num, 1));
228:
229: if (newas)
230: {
231: seg->as = newas;
232: memcpy (seg->as + seg->length, asnos, ASSEGMENT_DATA_SIZE(num, 1));
233: seg->length += num;
234: return seg;
235: }
236:
237: assegment_free_all (seg);
238: return NULL;
239: }
240:
241: static int
242: int_cmp (const void *p1, const void *p2)
243: {
244: const as_t *as1 = p1;
245: const as_t *as2 = p2;
246:
247: return (*as1 == *as2)
248: ? 0 : ( (*as1 > *as2) ? 1 : -1);
249: }
250:
251: /* normalise the segment.
252: * In particular, merge runs of AS_SEQUENCEs into one segment
253: * Internally, we do not care about the wire segment length limit, and
254: * we want each distinct AS_PATHs to have the exact same internal
255: * representation - eg, so that our hashing actually works..
256: */
257: static struct assegment *
258: assegment_normalise (struct assegment *head)
259: {
260: struct assegment *seg = head, *pin;
261: struct assegment *tmp;
262:
263: if (!head)
264: return head;
265:
266: while (seg)
267: {
268: pin = seg;
269:
270: /* Sort values SET segments, for determinism in paths to aid
271: * creation of hash values / path comparisons
272: * and because it helps other lesser implementations ;)
273: */
274: if (seg->type == AS_SET || seg->type == AS_CONFED_SET)
275: {
276: int tail = 0;
277: int i;
278:
279: qsort (seg->as, seg->length, sizeof(as_t), int_cmp);
280:
281: /* weed out dupes */
282: for (i=1; i < seg->length; i++)
283: {
284: if (seg->as[tail] == seg->as[i])
285: continue;
286:
287: tail++;
288: if (tail < i)
289: seg->as[tail] = seg->as[i];
290: }
291: /* seg->length can be 0.. */
292: if (seg->length)
293: seg->length = tail + 1;
294: }
295:
296: /* read ahead from the current, pinned segment while the segments
297: * are packable/mergeable. Append all following packable segments
298: * to the segment we have pinned and remove these appended
299: * segments.
300: */
301: while (pin->next && ASSEGMENT_TYPES_PACKABLE(pin, pin->next))
302: {
303: tmp = pin->next;
304: seg = pin->next;
305:
306: /* append the next sequence to the pinned sequence */
307: pin = assegment_append_asns (pin, seg->as, seg->length);
308:
309: /* bypass the next sequence */
310: pin->next = seg->next;
311:
312: /* get rid of the now referenceless segment */
313: assegment_free (tmp);
314:
315: }
316:
317: seg = pin->next;
318: }
319: return head;
320: }
321:
322: static struct aspath *
323: aspath_new (void)
324: {
325: return XCALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
326: }
327:
328: /* Free AS path structure. */
329: void
330: aspath_free (struct aspath *aspath)
331: {
332: if (!aspath)
333: return;
334: if (aspath->segments)
335: assegment_free_all (aspath->segments);
336: if (aspath->str)
337: XFREE (MTYPE_AS_STR, aspath->str);
338: XFREE (MTYPE_AS_PATH, aspath);
339: }
340:
341: /* Unintern aspath from AS path bucket. */
342: void
343: aspath_unintern (struct aspath **aspath)
344: {
345: struct aspath *ret;
346: struct aspath *asp = *aspath;
347:
348: if (asp->refcnt)
349: asp->refcnt--;
350:
351: if (asp->refcnt == 0)
352: {
353: /* This aspath must exist in aspath hash table. */
354: ret = hash_release (ashash, asp);
355: assert (ret != NULL);
356: aspath_free (asp);
357: *aspath = NULL;
358: }
359: }
360:
361: /* Return the start or end delimiters for a particular Segment type */
362: #define AS_SEG_START 0
363: #define AS_SEG_END 1
364: static char
365: aspath_delimiter_char (u_char type, u_char which)
366: {
367: int i;
368: struct
369: {
370: int type;
371: char start;
372: char end;
373: } aspath_delim_char [] =
374: {
375: { AS_SET, '{', '}' },
376: { AS_CONFED_SET, '[', ']' },
377: { AS_CONFED_SEQUENCE, '(', ')' },
378: { 0 }
379: };
380:
381: for (i = 0; aspath_delim_char[i].type != 0; i++)
382: {
383: if (aspath_delim_char[i].type == type)
384: {
385: if (which == AS_SEG_START)
386: return aspath_delim_char[i].start;
387: else if (which == AS_SEG_END)
388: return aspath_delim_char[i].end;
389: }
390: }
391: return ' ';
392: }
393:
394: /* countup asns from this segment and index onward */
395: static int
396: assegment_count_asns (struct assegment *seg, int from)
397: {
398: int count = 0;
399: while (seg)
400: {
401: if (!from)
402: count += seg->length;
403: else
404: {
405: count += (seg->length - from);
406: from = 0;
407: }
408: seg = seg->next;
409: }
410: return count;
411: }
412:
413: unsigned int
414: aspath_count_confeds (struct aspath *aspath)
415: {
416: int count = 0;
417: struct assegment *seg = aspath->segments;
418:
419: while (seg)
420: {
421: if (seg->type == AS_CONFED_SEQUENCE)
422: count += seg->length;
423: else if (seg->type == AS_CONFED_SET)
424: count++;
425:
426: seg = seg->next;
427: }
428: return count;
429: }
430:
431: unsigned int
432: aspath_count_hops (struct aspath *aspath)
433: {
434: int count = 0;
435: struct assegment *seg = aspath->segments;
436:
437: while (seg)
438: {
439: if (seg->type == AS_SEQUENCE)
440: count += seg->length;
441: else if (seg->type == AS_SET)
442: count++;
443:
444: seg = seg->next;
445: }
446: return count;
447: }
448:
449: /* Estimate size aspath /might/ take if encoded into an
450: * ASPATH attribute.
451: *
452: * This is a quick estimate, not definitive! aspath_put()
453: * may return a different number!!
454: */
455: unsigned int
456: aspath_size (struct aspath *aspath)
457: {
458: int size = 0;
459: struct assegment *seg = aspath->segments;
460:
461: while (seg)
462: {
463: size += ASSEGMENT_SIZE(seg->length, 1);
464: seg = seg->next;
465: }
466: return size;
467: }
468:
469: /* Return highest public ASN in path */
470: as_t
471: aspath_highest (struct aspath *aspath)
472: {
473: struct assegment *seg = aspath->segments;
474: as_t highest = 0;
475: unsigned int i;
476:
477: while (seg)
478: {
479: for (i = 0; i < seg->length; i++)
480: if (seg->as[i] > highest
481: && (seg->as[i] < BGP_PRIVATE_AS_MIN
482: || seg->as[i] > BGP_PRIVATE_AS_MAX))
483: highest = seg->as[i];
484: seg = seg->next;
485: }
486: return highest;
487: }
488:
489: /* Return 1 if there are any 4-byte ASes in the path */
490: unsigned int
491: aspath_has_as4 (struct aspath *aspath)
492: {
493: struct assegment *seg = aspath->segments;
494: unsigned int i;
495:
496: while (seg)
497: {
498: for (i = 0; i < seg->length; i++)
499: if (seg->as[i] > BGP_AS_MAX)
500: return 1;
501: seg = seg->next;
502: }
503: return 0;
504: }
505:
506: /* Convert aspath structure to string expression. */
507: static char *
508: aspath_make_str_count (struct aspath *as)
509: {
510: struct assegment *seg;
511: int str_size;
512: int len = 0;
513: char *str_buf;
514:
515: /* Empty aspath. */
516: if (!as->segments)
517: {
518: str_buf = XMALLOC (MTYPE_AS_STR, 1);
519: str_buf[0] = '\0';
520: return str_buf;
521: }
522:
523: seg = as->segments;
524:
525: /* ASN takes 5 to 10 chars plus seperator, see below.
526: * If there is one differing segment type, we need an additional
527: * 2 chars for segment delimiters, and the final '\0'.
528: * Hopefully this is large enough to avoid hitting the realloc
529: * code below for most common sequences.
530: *
531: * This was changed to 10 after the well-known BGP assertion, which
532: * had hit some parts of the Internet in May of 2009.
533: */
534: #define ASN_STR_LEN (10 + 1)
535: str_size = MAX (assegment_count_asns (seg, 0) * ASN_STR_LEN + 2 + 1,
536: ASPATH_STR_DEFAULT_LEN);
537: str_buf = XMALLOC (MTYPE_AS_STR, str_size);
538:
539: while (seg)
540: {
541: int i;
542: char seperator;
543:
544: /* Check AS type validity. Set seperator for segment */
545: switch (seg->type)
546: {
547: case AS_SET:
548: case AS_CONFED_SET:
549: seperator = ',';
550: break;
551: case AS_SEQUENCE:
552: case AS_CONFED_SEQUENCE:
553: seperator = ' ';
554: break;
555: default:
556: XFREE (MTYPE_AS_STR, str_buf);
557: return NULL;
558: }
559:
560: /* We might need to increase str_buf, particularly if path has
561: * differing segments types, our initial guesstimate above will
562: * have been wrong. Need 10 chars for ASN, a seperator each and
563: * potentially two segment delimiters, plus a space between each
564: * segment and trailing zero.
565: *
566: * This definitely didn't work with the value of 5 bytes and
567: * 32-bit ASNs.
568: */
569: #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
570: if ( (len + SEGMENT_STR_LEN(seg)) > str_size)
571: {
572: str_size = len + SEGMENT_STR_LEN(seg);
573: str_buf = XREALLOC (MTYPE_AS_STR, str_buf, str_size);
574: }
575: #undef ASN_STR_LEN
576: #undef SEGMENT_STR_LEN
577:
578: if (seg->type != AS_SEQUENCE)
579: len += snprintf (str_buf + len, str_size - len,
580: "%c",
581: aspath_delimiter_char (seg->type, AS_SEG_START));
582:
583: /* write out the ASNs, with their seperators, bar the last one*/
584: for (i = 0; i < seg->length; i++)
585: {
586: len += snprintf (str_buf + len, str_size - len, "%u", seg->as[i]);
587:
588: if (i < (seg->length - 1))
589: len += snprintf (str_buf + len, str_size - len, "%c", seperator);
590: }
591:
592: if (seg->type != AS_SEQUENCE)
593: len += snprintf (str_buf + len, str_size - len, "%c",
594: aspath_delimiter_char (seg->type, AS_SEG_END));
595: if (seg->next)
596: len += snprintf (str_buf + len, str_size - len, " ");
597:
598: seg = seg->next;
599: }
600:
601: assert (len < str_size);
602:
603: str_buf[len] = '\0';
604:
605: return str_buf;
606: }
607:
608: static void
609: aspath_str_update (struct aspath *as)
610: {
611: if (as->str)
612: XFREE (MTYPE_AS_STR, as->str);
613: as->str = aspath_make_str_count (as);
614: }
615:
616: /* Intern allocated AS path. */
617: struct aspath *
618: aspath_intern (struct aspath *aspath)
619: {
620: struct aspath *find;
621:
622: /* Assert this AS path structure is not interned. */
623: assert (aspath->refcnt == 0);
624:
625: /* Check AS path hash. */
626: find = hash_get (ashash, aspath, hash_alloc_intern);
627:
628: if (find != aspath)
629: aspath_free (aspath);
630:
631: find->refcnt++;
632:
633: if (! find->str)
634: find->str = aspath_make_str_count (find);
635:
636: return find;
637: }
638:
639: /* Duplicate aspath structure. Created same aspath structure but
640: reference count and AS path string is cleared. */
641: struct aspath *
642: aspath_dup (struct aspath *aspath)
643: {
644: struct aspath *new;
645:
646: new = XCALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
647:
648: if (aspath->segments)
649: new->segments = assegment_dup_all (aspath->segments);
650: else
651: new->segments = NULL;
652:
653: new->str = aspath_make_str_count (aspath);
654:
655: return new;
656: }
657:
658: static void *
659: aspath_hash_alloc (void *arg)
660: {
661: struct aspath *aspath;
662:
663: /* New aspath structure is needed. */
664: aspath = aspath_dup (arg);
665:
666: /* Malformed AS path value. */
667: if (! aspath->str)
668: {
669: aspath_free (aspath);
670: return NULL;
671: }
672:
673: return aspath;
674: }
675:
676: /* parse as-segment byte stream in struct assegment */
677: static int
678: assegments_parse (struct stream *s, size_t length,
679: struct assegment **result, int use32bit)
680: {
681: struct assegment_header segh;
682: struct assegment *seg, *prev = NULL, *head = NULL;
683: size_t bytes = 0;
684:
685: /* empty aspath (ie iBGP or somesuch) */
686: if (length == 0)
687: return 0;
688:
689: if (BGP_DEBUG (as4, AS4_SEGMENT))
690: zlog_debug ("[AS4SEG] Parse aspath segment: got total byte length %lu",
691: (unsigned long) length);
692: /* basic checks */
693: if ((STREAM_READABLE(s) < length)
694: || (STREAM_READABLE(s) < AS_HEADER_SIZE)
695: || (length % AS16_VALUE_SIZE ))
696: return -1;
697:
698: while (bytes < length)
699: {
700: int i;
701: size_t seg_size;
702:
703: if ((length - bytes) <= AS_HEADER_SIZE)
704: {
705: if (head)
706: assegment_free_all (head);
707: return -1;
708: }
709:
710: /* softly softly, get the header first on its own */
711: segh.type = stream_getc (s);
712: segh.length = stream_getc (s);
713:
714: seg_size = ASSEGMENT_SIZE(segh.length, use32bit);
715:
716: if (BGP_DEBUG (as4, AS4_SEGMENT))
717: zlog_debug ("[AS4SEG] Parse aspath segment: got type %d, length %d",
718: segh.type, segh.length);
719:
720: /* check it.. */
721: if ( ((bytes + seg_size) > length)
722: /* 1771bis 4.3b: seg length contains one or more */
723: || (segh.length == 0)
724: /* Paranoia in case someone changes type of segment length.
725: * Shift both values by 0x10 to make the comparison operate
726: * on more, than 8 bits (otherwise it's a warning, bug #564).
727: */
728: || ((sizeof segh.length > 1)
729: && (0x10 + segh.length > 0x10 + AS_SEGMENT_MAX)))
730: {
731: if (head)
732: assegment_free_all (head);
733: return -1;
734: }
735:
736: switch (segh.type)
737: {
738: case AS_SEQUENCE:
739: case AS_SET:
740: case AS_CONFED_SEQUENCE:
741: case AS_CONFED_SET:
742: break;
743: default:
744: if (head)
745: assegment_free_all (head);
746: return -1;
747: }
748:
749: /* now its safe to trust lengths */
750: seg = assegment_new (segh.type, segh.length);
751:
752: if (head)
753: prev->next = seg;
754: else /* it's the first segment */
755: head = prev = seg;
756:
757: for (i = 0; i < segh.length; i++)
758: seg->as[i] = (use32bit) ? stream_getl (s) : stream_getw (s);
759:
760: bytes += seg_size;
761:
762: if (BGP_DEBUG (as4, AS4_SEGMENT))
763: zlog_debug ("[AS4SEG] Parse aspath segment: Bytes now: %lu",
764: (unsigned long) bytes);
765:
766: prev = seg;
767: }
768:
769: *result = assegment_normalise (head);
770: return 0;
771: }
772:
773: /* AS path parse function. pnt is a pointer to byte stream and length
774: is length of byte stream. If there is same AS path in the the AS
775: path hash then return it else make new AS path structure.
776:
777: On error NULL is returned.
778: */
779: struct aspath *
780: aspath_parse (struct stream *s, size_t length, int use32bit)
781: {
782: struct aspath as;
783: struct aspath *find;
784:
785: /* If length is odd it's malformed AS path. */
786: /* Nit-picking: if (use32bit == 0) it is malformed if odd,
787: * otherwise its malformed when length is larger than 2 and (length-2)
788: * is not dividable by 4.
789: * But... this time we're lazy
790: */
791: if (length % AS16_VALUE_SIZE )
792: return NULL;
793:
794: memset (&as, 0, sizeof (struct aspath));
795: if (assegments_parse (s, length, &as.segments, use32bit) < 0)
796: return NULL;
797:
798: /* If already same aspath exist then return it. */
799: find = hash_get (ashash, &as, aspath_hash_alloc);
800:
801: /* aspath_hash_alloc dupes segments too. that probably could be
802: * optimised out.
803: */
804: assegment_free_all (as.segments);
805: if (as.str)
806: XFREE (MTYPE_AS_STR, as.str);
807:
808: if (! find)
809: return NULL;
810: find->refcnt++;
811:
812: return find;
813: }
814:
815: static inline void
816: assegment_data_put (struct stream *s, as_t *as, int num, int use32bit)
817: {
818: int i;
819: assert (num <= AS_SEGMENT_MAX);
820:
821: for (i = 0; i < num; i++)
822: if ( use32bit )
823: stream_putl (s, as[i]);
824: else
825: {
826: if ( as[i] <= BGP_AS_MAX )
827: stream_putw(s, as[i]);
828: else
829: stream_putw(s, BGP_AS_TRANS);
830: }
831: }
832:
833: static inline size_t
834: assegment_header_put (struct stream *s, u_char type, int length)
835: {
836: size_t lenp;
837: assert (length <= AS_SEGMENT_MAX);
838: stream_putc (s, type);
839: lenp = stream_get_endp (s);
840: stream_putc (s, length);
841: return lenp;
842: }
843:
844: /* write aspath data to stream */
845: size_t
846: aspath_put (struct stream *s, struct aspath *as, int use32bit )
847: {
848: struct assegment *seg = as->segments;
849: size_t bytes = 0;
850:
851: if (!seg || seg->length == 0)
852: return 0;
853:
854: if (seg)
855: {
856: /*
857: * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
858: * At the moment, we would write out a partial aspath, and our peer
859: * will complain and drop the session :-/
860: *
861: * The general assumption here is that many things tested will
862: * never happen. And, in real live, up to now, they have not.
863: */
864: while (seg && (ASSEGMENT_LEN(seg, use32bit) <= STREAM_WRITEABLE(s)))
865: {
866: struct assegment *next = seg->next;
867: int written = 0;
868: int asns_packed = 0;
869: size_t lenp;
870:
871: /* Overlength segments have to be split up */
872: while ( (seg->length - written) > AS_SEGMENT_MAX)
873: {
874: assegment_header_put (s, seg->type, AS_SEGMENT_MAX);
875: assegment_data_put (s, seg->as, AS_SEGMENT_MAX, use32bit);
876: written += AS_SEGMENT_MAX;
877: bytes += ASSEGMENT_SIZE (written, use32bit);
878: }
879:
880: /* write the final segment, probably is also the first */
881: lenp = assegment_header_put (s, seg->type, seg->length - written);
882: assegment_data_put (s, (seg->as + written), seg->length - written,
883: use32bit);
884:
885: /* Sequence-type segments can be 'packed' together
886: * Case of a segment which was overlength and split up
887: * will be missed here, but that doesn't matter.
888: */
889: while (next && ASSEGMENTS_PACKABLE (seg, next))
890: {
891: /* NB: We should never normally get here given we
892: * normalise aspath data when parse them. However, better
893: * safe than sorry. We potentially could call
894: * assegment_normalise here instead, but it's cheaper and
895: * easier to do it on the fly here rather than go through
896: * the segment list twice every time we write out
897: * aspath's.
898: */
899:
900: /* Next segment's data can fit in this one */
901: assegment_data_put (s, next->as, next->length, use32bit);
902:
903: /* update the length of the segment header */
904: stream_putc_at (s, lenp, seg->length - written + next->length);
905: asns_packed += next->length;
906:
907: next = next->next;
908: }
909:
910: bytes += ASSEGMENT_SIZE (seg->length - written + asns_packed,
911: use32bit);
912: seg = next;
913: }
914: }
915: return bytes;
916: }
917:
918: /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
919: * We have no way to manage the storage, so we use a static stream
920: * wrapper around aspath_put.
921: */
922: u_char *
923: aspath_snmp_pathseg (struct aspath *as, size_t *varlen)
924: {
925: #define SNMP_PATHSEG_MAX 1024
926:
927: if (!snmp_stream)
928: snmp_stream = stream_new (SNMP_PATHSEG_MAX);
929: else
930: stream_reset (snmp_stream);
931:
932: if (!as)
933: {
934: *varlen = 0;
935: return NULL;
936: }
937: aspath_put (snmp_stream, as, 0); /* use 16 bit for now here */
938:
939: *varlen = stream_get_endp (snmp_stream);
940: return stream_pnt(snmp_stream);
941: }
942:
943: #define min(A,B) ((A) < (B) ? (A) : (B))
944:
945: static struct assegment *
946: aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset,
947: as_t as)
948: {
949: int i;
950:
951: /* If this is first AS set member, create new as-set segment. */
952: if (asset == NULL)
953: {
954: asset = assegment_new (AS_SET, 1);
955: if (! aspath->segments)
956: aspath->segments = asset;
957: else
958: {
959: struct assegment *seg = aspath->segments;
960: while (seg->next)
961: seg = seg->next;
962: seg->next = asset;
963: }
964: asset->type = AS_SET;
965: asset->length = 1;
966: asset->as[0] = as;
967: }
968: else
969: {
970: /* Check this AS value already exists or not. */
971: for (i = 0; i < asset->length; i++)
972: if (asset->as[i] == as)
973: return asset;
974:
975: asset->length++;
976: asset->as = XREALLOC (MTYPE_AS_SEG_DATA, asset->as,
977: asset->length * AS_VALUE_SIZE);
978: asset->as[asset->length - 1] = as;
979: }
980:
981:
982: return asset;
983: }
984:
985: /* Modify as1 using as2 for aggregation. */
986: struct aspath *
987: aspath_aggregate (struct aspath *as1, struct aspath *as2)
988: {
989: int i;
990: int minlen;
991: int match;
992: int from;
993: struct assegment *seg1 = as1->segments;
994: struct assegment *seg2 = as2->segments;
995: struct aspath *aspath = NULL;
996: struct assegment *asset;
997: struct assegment *prevseg = NULL;
998:
999: match = 0;
1000: minlen = 0;
1001: aspath = NULL;
1002: asset = NULL;
1003:
1004: /* First of all check common leading sequence. */
1005: while (seg1 && seg2)
1006: {
1007: /* Check segment type. */
1008: if (seg1->type != seg2->type)
1009: break;
1010:
1011: /* Minimum segment length. */
1012: minlen = min (seg1->length, seg2->length);
1013:
1014: for (match = 0; match < minlen; match++)
1015: if (seg1->as[match] != seg2->as[match])
1016: break;
1017:
1018: if (match)
1019: {
1020: struct assegment *seg = assegment_new (seg1->type, 0);
1021:
1022: seg = assegment_append_asns (seg, seg1->as, match);
1023:
1024: if (! aspath)
1025: {
1026: aspath = aspath_new ();
1027: aspath->segments = seg;
1028: }
1029: else
1030: prevseg->next = seg;
1031:
1032: prevseg = seg;
1033: }
1034:
1035: if (match != minlen || match != seg1->length
1036: || seg1->length != seg2->length)
1037: break;
1038:
1039: seg1 = seg1->next;
1040: seg2 = seg2->next;
1041: }
1042:
1043: if (! aspath)
1044: aspath = aspath_new();
1045:
1046: /* Make as-set using rest of all information. */
1047: from = match;
1048: while (seg1)
1049: {
1050: for (i = from; i < seg1->length; i++)
1051: asset = aspath_aggregate_as_set_add (aspath, asset, seg1->as[i]);
1052:
1053: from = 0;
1054: seg1 = seg1->next;
1055: }
1056:
1057: from = match;
1058: while (seg2)
1059: {
1060: for (i = from; i < seg2->length; i++)
1061: asset = aspath_aggregate_as_set_add (aspath, asset, seg2->as[i]);
1062:
1063: from = 0;
1064: seg2 = seg2->next;
1065: }
1066:
1067: assegment_normalise (aspath->segments);
1068: aspath_str_update (aspath);
1069: return aspath;
1070: }
1071:
1072: /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1073: attribute, check the leftmost AS number in the AS_PATH attribute is
1074: or not the peer's AS number. */
1075: int
1076: aspath_firstas_check (struct aspath *aspath, as_t asno)
1077: {
1078: if ( (aspath == NULL) || (aspath->segments == NULL) )
1079: return 0;
1080:
1081: if (aspath->segments
1082: && (aspath->segments->type == AS_SEQUENCE)
1083: && (aspath->segments->as[0] == asno ))
1084: return 1;
1085:
1086: return 0;
1087: }
1088:
1089: /* AS path loop check. If aspath contains asno then return >= 1. */
1090: int
1091: aspath_loop_check (struct aspath *aspath, as_t asno)
1092: {
1093: struct assegment *seg;
1094: int count = 0;
1095:
1096: if ( (aspath == NULL) || (aspath->segments == NULL) )
1097: return 0;
1098:
1099: seg = aspath->segments;
1100:
1101: while (seg)
1102: {
1103: int i;
1104:
1105: for (i = 0; i < seg->length; i++)
1106: if (seg->as[i] == asno)
1107: count++;
1108:
1109: seg = seg->next;
1110: }
1111: return count;
1112: }
1113:
1114: /* When all of AS path is private AS return 1. */
1115: int
1116: aspath_private_as_check (struct aspath *aspath)
1117: {
1118: struct assegment *seg;
1119:
1120: if ( !(aspath && aspath->segments) )
1121: return 0;
1122:
1123: seg = aspath->segments;
1124:
1125: while (seg)
1126: {
1127: int i;
1128:
1129: for (i = 0; i < seg->length; i++)
1130: {
1131: if ( (seg->as[i] < BGP_PRIVATE_AS_MIN)
1132: || (seg->as[i] > BGP_PRIVATE_AS_MAX) )
1133: return 0;
1134: }
1135: seg = seg->next;
1136: }
1137: return 1;
1138: }
1139:
1140: /* AS path confed check. If aspath contains confed set or sequence then return 1. */
1141: int
1142: aspath_confed_check (struct aspath *aspath)
1143: {
1144: struct assegment *seg;
1145:
1146: if ( !(aspath && aspath->segments) )
1147: return 0;
1148:
1149: seg = aspath->segments;
1150:
1151: while (seg)
1152: {
1153: if (seg->type == AS_CONFED_SET || seg->type == AS_CONFED_SEQUENCE)
1154: return 1;
1155: seg = seg->next;
1156: }
1157: return 0;
1158: }
1159:
1160: /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1161: AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1162: int
1163: aspath_left_confed_check (struct aspath *aspath)
1164: {
1165:
1166: if ( !(aspath && aspath->segments) )
1167: return 0;
1168:
1169: if ( (aspath->segments->type == AS_CONFED_SEQUENCE)
1170: || (aspath->segments->type == AS_CONFED_SET) )
1171: return 1;
1172:
1173: return 0;
1174: }
1175:
1176: /* Merge as1 to as2. as2 should be uninterned aspath. */
1177: static struct aspath *
1178: aspath_merge (struct aspath *as1, struct aspath *as2)
1179: {
1180: struct assegment *last, *new;
1181:
1182: if (! as1 || ! as2)
1183: return NULL;
1184:
1185: last = new = assegment_dup_all (as1->segments);
1186:
1187: /* find the last valid segment */
1188: while (last && last->next)
1189: last = last->next;
1190:
1191: last->next = as2->segments;
1192: as2->segments = new;
1193: aspath_str_update (as2);
1194: return as2;
1195: }
1196:
1197: /* Prepend as1 to as2. as2 should be uninterned aspath. */
1198: struct aspath *
1199: aspath_prepend (struct aspath *as1, struct aspath *as2)
1200: {
1201: struct assegment *seg1;
1202: struct assegment *seg2;
1203:
1204: if (! as1 || ! as2)
1205: return NULL;
1206:
1207: seg1 = as1->segments;
1208: seg2 = as2->segments;
1209:
1210: /* If as2 is empty, only need to dupe as1's chain onto as2 */
1211: if (seg2 == NULL)
1212: {
1213: as2->segments = assegment_dup_all (as1->segments);
1214: aspath_str_update (as2);
1215: return as2;
1216: }
1217:
1218: /* If as1 is empty AS, no prepending to do. */
1219: if (seg1 == NULL)
1220: return as2;
1221:
1222: /* find the tail as1's segment chain. */
1223: while (seg1 && seg1->next)
1224: seg1 = seg1->next;
1225:
1226: /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1227: if (seg1->type == AS_SEQUENCE && seg2->type == AS_CONFED_SEQUENCE)
1228: as2 = aspath_delete_confed_seq (as2);
1229:
1230: /* Compare last segment type of as1 and first segment type of as2. */
1231: if (seg1->type != seg2->type)
1232: return aspath_merge (as1, as2);
1233:
1234: if (seg1->type == AS_SEQUENCE)
1235: {
1236: /* We have two chains of segments, as1->segments and seg2,
1237: * and we have to attach them together, merging the attaching
1238: * segments together into one.
1239: *
1240: * 1. dupe as1->segments onto head of as2
1241: * 2. merge seg2's asns onto last segment of this new chain
1242: * 3. attach chain after seg2
1243: */
1244:
1245: /* dupe as1 onto as2's head */
1246: seg1 = as2->segments = assegment_dup_all (as1->segments);
1247:
1248: /* refind the tail of as2, reusing seg1 */
1249: while (seg1 && seg1->next)
1250: seg1 = seg1->next;
1251:
1252: /* merge the old head, seg2, into tail, seg1 */
1253: seg1 = assegment_append_asns (seg1, seg2->as, seg2->length);
1254:
1255: /* bypass the merged seg2, and attach any chain after it to
1256: * chain descending from as2's head
1257: */
1258: seg1->next = seg2->next;
1259:
1260: /* seg2 is now referenceless and useless*/
1261: assegment_free (seg2);
1262:
1263: /* we've now prepended as1's segment chain to as2, merging
1264: * the inbetween AS_SEQUENCE of seg2 in the process
1265: */
1266: aspath_str_update (as2);
1267: return as2;
1268: }
1269: else
1270: {
1271: /* AS_SET merge code is needed at here. */
1272: return aspath_merge (as1, as2);
1273: }
1274: /* XXX: Ermmm, what if as1 has multiple segments?? */
1275:
1276: /* Not reached */
1277: }
1278:
1279: /* Iterate over AS_PATH segments and wipe all occurences of the
1280: * listed AS numbers. Hence some segments may lose some or even
1281: * all data on the way, the operation is implemented as a smarter
1282: * version of aspath_dup(), which allocates memory to hold the new
1283: * data, not the original. The new AS path is returned.
1284: */
1285: struct aspath *
1286: aspath_filter_exclude (struct aspath * source, struct aspath * exclude_list)
1287: {
1288: struct assegment * srcseg, * exclseg, * lastseg;
1289: struct aspath * newpath;
1290:
1291: newpath = aspath_new();
1292: lastseg = NULL;
1293:
1294: for (srcseg = source->segments; srcseg; srcseg = srcseg->next)
1295: {
1296: unsigned i, y, newlen = 0, done = 0, skip_as;
1297: struct assegment * newseg;
1298:
1299: /* Find out, how much ASns are we going to pick from this segment.
1300: * We can't perform filtering right inline, because the size of
1301: * the new segment isn't known at the moment yet.
1302: */
1303: for (i = 0; i < srcseg->length; i++)
1304: {
1305: skip_as = 0;
1306: for (exclseg = exclude_list->segments; exclseg && !skip_as; exclseg = exclseg->next)
1307: for (y = 0; y < exclseg->length; y++)
1308: if (srcseg->as[i] == exclseg->as[y])
1309: {
1310: skip_as = 1;
1311: // There's no sense in testing the rest of exclusion list, bail out.
1312: break;
1313: }
1314: if (!skip_as)
1315: newlen++;
1316: }
1317: /* newlen is now the number of ASns to copy */
1318: if (!newlen)
1319: continue;
1320:
1321: /* Actual copying. Allocate memory and iterate once more, performing filtering. */
1322: newseg = assegment_new (srcseg->type, newlen);
1323: for (i = 0; i < srcseg->length; i++)
1324: {
1325: skip_as = 0;
1326: for (exclseg = exclude_list->segments; exclseg && !skip_as; exclseg = exclseg->next)
1327: for (y = 0; y < exclseg->length; y++)
1328: if (srcseg->as[i] == exclseg->as[y])
1329: {
1330: skip_as = 1;
1331: break;
1332: }
1333: if (skip_as)
1334: continue;
1335: newseg->as[done++] = srcseg->as[i];
1336: }
1337: /* At his point newlen must be equal to done, and both must be positive. Append
1338: * the filtered segment to the gross result. */
1339: if (!lastseg)
1340: newpath->segments = newseg;
1341: else
1342: lastseg->next = newseg;
1343: lastseg = newseg;
1344: }
1345: aspath_str_update (newpath);
1346: /* We are happy returning even an empty AS_PATH, because the administrator
1347: * might expect this very behaviour. There's a mean to avoid this, if necessary,
1348: * by having a match rule against certain AS_PATH regexps in the route-map index.
1349: */
1350: aspath_free (source);
1351: return newpath;
1352: }
1353:
1354: /* Add specified AS to the leftmost of aspath. */
1355: static struct aspath *
1356: aspath_add_one_as (struct aspath *aspath, as_t asno, u_char type)
1357: {
1358: struct assegment *assegment = aspath->segments;
1359:
1360: /* In case of empty aspath. */
1361: if (assegment == NULL || assegment->length == 0)
1362: {
1363: aspath->segments = assegment_new (type, 1);
1364: aspath->segments->as[0] = asno;
1365:
1366: if (assegment)
1367: assegment_free (assegment);
1368:
1369: return aspath;
1370: }
1371:
1372: if (assegment->type == type)
1373: aspath->segments = assegment_prepend_asns (aspath->segments, asno, 1);
1374: else
1375: {
1376: /* create new segment
1377: * push it onto head of aspath's segment chain
1378: */
1379: struct assegment *newsegment;
1380:
1381: newsegment = assegment_new (type, 1);
1382: newsegment->as[0] = asno;
1383:
1384: newsegment->next = assegment;
1385: aspath->segments = newsegment;
1386: }
1387:
1388: return aspath;
1389: }
1390:
1391: /* Add specified AS to the leftmost of aspath. */
1392: struct aspath *
1393: aspath_add_seq (struct aspath *aspath, as_t asno)
1394: {
1395: return aspath_add_one_as (aspath, asno, AS_SEQUENCE);
1396: }
1397:
1398: /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1399: as2's leftmost AS is same return 1. */
1400: int
1401: aspath_cmp_left (const struct aspath *aspath1, const struct aspath *aspath2)
1402: {
1403: const struct assegment *seg1 = NULL;
1404: const struct assegment *seg2 = NULL;
1405:
1406: if (!(aspath1 && aspath2))
1407: return 0;
1408:
1409: seg1 = aspath1->segments;
1410: seg2 = aspath2->segments;
1411:
1412: /* find first non-confed segments for each */
1413: while (seg1 && ((seg1->type == AS_CONFED_SEQUENCE)
1414: || (seg1->type == AS_CONFED_SET)))
1415: seg1 = seg1->next;
1416:
1417: while (seg2 && ((seg2->type == AS_CONFED_SEQUENCE)
1418: || (seg2->type == AS_CONFED_SET)))
1419: seg2 = seg2->next;
1420:
1421: /* Check as1's */
1422: if (!(seg1 && seg2
1423: && (seg1->type == AS_SEQUENCE) && (seg2->type == AS_SEQUENCE)))
1424: return 0;
1425:
1426: if (seg1->as[0] == seg2->as[0])
1427: return 1;
1428:
1429: return 0;
1430: }
1431:
1432: /* Truncate an aspath after a number of hops, and put the hops remaining
1433: * at the front of another aspath. Needed for AS4 compat.
1434: *
1435: * Returned aspath is a /new/ aspath, which should either by free'd or
1436: * interned by the caller, as desired.
1437: */
1438: struct aspath *
1439: aspath_reconcile_as4 ( struct aspath *aspath, struct aspath *as4path)
1440: {
1441: struct assegment *seg, *newseg, *prevseg = NULL;
1442: struct aspath *newpath = NULL, *mergedpath;
1443: int hops, cpasns = 0;
1444:
1445: if (!aspath)
1446: return NULL;
1447:
1448: seg = aspath->segments;
1449:
1450: /* CONFEDs should get reconciled too.. */
1451: hops = (aspath_count_hops (aspath) + aspath_count_confeds (aspath))
1452: - aspath_count_hops (as4path);
1453:
1454: if (hops < 0)
1455: {
1456: if (BGP_DEBUG (as4, AS4))
1457: zlog_warn ("[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1458: /* Something's gone wrong. The RFC says we should now ignore AS4_PATH,
1459: * which is daft behaviour - it contains vital loop-detection
1460: * information which must have been removed from AS_PATH.
1461: */
1462: hops = aspath_count_hops (aspath);
1463: }
1464:
1465: if (!hops)
1466: return aspath_dup (as4path);
1467:
1468: if ( BGP_DEBUG(as4, AS4))
1469: zlog_debug("[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1470: aspath->str, as4path->str);
1471:
1472: while (seg && hops > 0)
1473: {
1474: switch (seg->type)
1475: {
1476: case AS_SET:
1477: case AS_CONFED_SET:
1478: hops--;
1479: cpasns = seg->length;
1480: break;
1481: case AS_CONFED_SEQUENCE:
1482: /* Should never split a confed-sequence, if hop-count
1483: * suggests we must then something's gone wrong somewhere.
1484: *
1485: * Most important goal is to preserve AS_PATHs prime function
1486: * as loop-detector, so we fudge the numbers so that the entire
1487: * confed-sequence is merged in.
1488: */
1489: if (hops < seg->length)
1490: {
1491: if (BGP_DEBUG (as4, AS4))
1492: zlog_debug ("[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1493: " across 2/4 ASN boundary somewhere, broken..");
1494: hops = seg->length;
1495: }
1496: case AS_SEQUENCE:
1497: cpasns = MIN(seg->length, hops);
1498: hops -= seg->length;
1499: }
1500:
1501: assert (cpasns <= seg->length);
1502:
1503: newseg = assegment_new (seg->type, 0);
1504: newseg = assegment_append_asns (newseg, seg->as, cpasns);
1505:
1506: if (!newpath)
1507: {
1508: newpath = aspath_new ();
1509: newpath->segments = newseg;
1510: }
1511: else
1512: prevseg->next = newseg;
1513:
1514: prevseg = newseg;
1515: seg = seg->next;
1516: }
1517:
1518: /* We may be able to join some segments here, and we must
1519: * do this because... we want normalised aspaths in out hash
1520: * and we do not want to stumble in aspath_put.
1521: */
1522: mergedpath = aspath_merge (newpath, aspath_dup(as4path));
1523: aspath_free (newpath);
1524: mergedpath->segments = assegment_normalise (mergedpath->segments);
1525: aspath_str_update (mergedpath);
1526:
1527: if ( BGP_DEBUG(as4, AS4))
1528: zlog_debug ("[AS4] result of synthesizing is %s",
1529: mergedpath->str);
1530:
1531: return mergedpath;
1532: }
1533:
1534: /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1535: as2's leftmost AS is same return 1. (confederation as-path
1536: only). */
1537: int
1538: aspath_cmp_left_confed (const struct aspath *aspath1, const struct aspath *aspath2)
1539: {
1540: if (! (aspath1 && aspath2) )
1541: return 0;
1542:
1543: if ( !(aspath1->segments && aspath2->segments) )
1544: return 0;
1545:
1546: if ( (aspath1->segments->type != AS_CONFED_SEQUENCE)
1547: || (aspath2->segments->type != AS_CONFED_SEQUENCE) )
1548: return 0;
1549:
1550: if (aspath1->segments->as[0] == aspath2->segments->as[0])
1551: return 1;
1552:
1553: return 0;
1554: }
1555:
1556: /* Delete all leading AS_CONFED_SEQUENCE/SET segments from aspath.
1557: * See RFC3065, 6.1 c1 */
1558: struct aspath *
1559: aspath_delete_confed_seq (struct aspath *aspath)
1560: {
1561: struct assegment *seg;
1562:
1563: if (!(aspath && aspath->segments))
1564: return aspath;
1565:
1566: seg = aspath->segments;
1567:
1568: /* "if the first path segment of the AS_PATH is
1569: * of type AS_CONFED_SEQUENCE,"
1570: */
1571: if (aspath->segments->type != AS_CONFED_SEQUENCE)
1572: return aspath;
1573:
1574: /* "... that segment and any immediately following segments
1575: * of the type AS_CONFED_SET or AS_CONFED_SEQUENCE are removed
1576: * from the AS_PATH attribute,"
1577: */
1578: while (seg &&
1579: (seg->type == AS_CONFED_SEQUENCE || seg->type == AS_CONFED_SET))
1580: {
1581: aspath->segments = seg->next;
1582: assegment_free (seg);
1583: seg = aspath->segments;
1584: }
1585: aspath_str_update (aspath);
1586: return aspath;
1587: }
1588:
1589: /* Add new AS number to the leftmost part of the aspath as
1590: AS_CONFED_SEQUENCE. */
1591: struct aspath*
1592: aspath_add_confed_seq (struct aspath *aspath, as_t asno)
1593: {
1594: return aspath_add_one_as (aspath, asno, AS_CONFED_SEQUENCE);
1595: }
1596:
1597: /* Add new as value to as path structure. */
1598: static void
1599: aspath_as_add (struct aspath *as, as_t asno)
1600: {
1601: struct assegment *seg = as->segments;
1602:
1603: if (!seg)
1604: return;
1605:
1606: /* Last segment search procedure. */
1607: while (seg->next)
1608: seg = seg->next;
1609:
1610: assegment_append_asns (seg, &asno, 1);
1611: }
1612:
1613: /* Add new as segment to the as path. */
1614: static void
1615: aspath_segment_add (struct aspath *as, int type)
1616: {
1617: struct assegment *seg = as->segments;
1618: struct assegment *new = assegment_new (type, 0);
1619:
1620: if (seg)
1621: {
1622: while (seg->next)
1623: seg = seg->next;
1624: seg->next = new;
1625: }
1626: else
1627: as->segments = new;
1628: }
1629:
1630: struct aspath *
1631: aspath_empty (void)
1632: {
1633: return aspath_parse (NULL, 0, 1); /* 32Bit ;-) */
1634: }
1635:
1636: struct aspath *
1637: aspath_empty_get (void)
1638: {
1639: struct aspath *aspath;
1640:
1641: aspath = aspath_new ();
1642: aspath->str = aspath_make_str_count (aspath);
1643: return aspath;
1644: }
1645:
1646: unsigned long
1647: aspath_count (void)
1648: {
1649: return ashash->count;
1650: }
1651:
1652: /*
1653: Theoretically, one as path can have:
1654:
1655: One BGP packet size should be less than 4096.
1656: One BGP attribute size should be less than 4096 - BGP header size.
1657: One BGP aspath size should be less than 4096 - BGP header size -
1658: BGP mandantry attribute size.
1659: */
1660:
1661: /* AS path string lexical token enum. */
1662: enum as_token
1663: {
1664: as_token_asval,
1665: as_token_set_start,
1666: as_token_set_end,
1667: as_token_confed_seq_start,
1668: as_token_confed_seq_end,
1669: as_token_confed_set_start,
1670: as_token_confed_set_end,
1671: as_token_unknown
1672: };
1673:
1674: /* Return next token and point for string parse. */
1675: static const char *
1676: aspath_gettoken (const char *buf, enum as_token *token, u_long *asno)
1677: {
1678: const char *p = buf;
1679:
1680: /* Skip seperators (space for sequences, ',' for sets). */
1681: while (isspace ((int) *p) || *p == ',')
1682: p++;
1683:
1684: /* Check the end of the string and type specify characters
1685: (e.g. {}()). */
1686: switch (*p)
1687: {
1688: case '\0':
1689: return NULL;
1690: case '{':
1691: *token = as_token_set_start;
1692: p++;
1693: return p;
1694: case '}':
1695: *token = as_token_set_end;
1696: p++;
1697: return p;
1698: case '(':
1699: *token = as_token_confed_seq_start;
1700: p++;
1701: return p;
1702: case ')':
1703: *token = as_token_confed_seq_end;
1704: p++;
1705: return p;
1706: case '[':
1707: *token = as_token_confed_set_start;
1708: p++;
1709: return p;
1710: case ']':
1711: *token = as_token_confed_set_end;
1712: p++;
1713: return p;
1714: }
1715:
1716: /* Check actual AS value. */
1717: if (isdigit ((int) *p))
1718: {
1719: as_t asval;
1720:
1721: *token = as_token_asval;
1722: asval = (*p - '0');
1723: p++;
1724:
1725: while (isdigit ((int) *p))
1726: {
1727: asval *= 10;
1728: asval += (*p - '0');
1729: p++;
1730: }
1731: *asno = asval;
1732: return p;
1733: }
1734:
1735: /* There is no match then return unknown token. */
1736: *token = as_token_unknown;
1737: return p++;
1738: }
1739:
1740: struct aspath *
1741: aspath_str2aspath (const char *str)
1742: {
1743: enum as_token token = as_token_unknown;
1744: u_short as_type;
1745: u_long asno = 0;
1746: struct aspath *aspath;
1747: int needtype;
1748:
1749: aspath = aspath_new ();
1750:
1751: /* We start default type as AS_SEQUENCE. */
1752: as_type = AS_SEQUENCE;
1753: needtype = 1;
1754:
1755: while ((str = aspath_gettoken (str, &token, &asno)) != NULL)
1756: {
1757: switch (token)
1758: {
1759: case as_token_asval:
1760: if (needtype)
1761: {
1762: aspath_segment_add (aspath, as_type);
1763: needtype = 0;
1764: }
1765: aspath_as_add (aspath, asno);
1766: break;
1767: case as_token_set_start:
1768: as_type = AS_SET;
1769: aspath_segment_add (aspath, as_type);
1770: needtype = 0;
1771: break;
1772: case as_token_set_end:
1773: as_type = AS_SEQUENCE;
1774: needtype = 1;
1775: break;
1776: case as_token_confed_seq_start:
1777: as_type = AS_CONFED_SEQUENCE;
1778: aspath_segment_add (aspath, as_type);
1779: needtype = 0;
1780: break;
1781: case as_token_confed_seq_end:
1782: as_type = AS_SEQUENCE;
1783: needtype = 1;
1784: break;
1785: case as_token_confed_set_start:
1786: as_type = AS_CONFED_SET;
1787: aspath_segment_add (aspath, as_type);
1788: needtype = 0;
1789: break;
1790: case as_token_confed_set_end:
1791: as_type = AS_SEQUENCE;
1792: needtype = 1;
1793: break;
1794: case as_token_unknown:
1795: default:
1796: aspath_free (aspath);
1797: return NULL;
1798: }
1799: }
1800:
1801: aspath->str = aspath_make_str_count (aspath);
1802:
1803: return aspath;
1804: }
1805:
1806: /* Make hash value by raw aspath data. */
1807: unsigned int
1808: aspath_key_make (void *p)
1809: {
1810: struct aspath * aspath = (struct aspath *) p;
1811: unsigned int key = 0;
1812:
1813: if (!aspath->str)
1814: aspath_str_update (aspath);
1815:
1816: key = jhash (aspath->str, strlen(aspath->str), 2334325);
1817:
1818: return key;
1819: }
1820:
1821: /* If two aspath have same value then return 1 else return 0 */
1822: static int
1823: aspath_cmp (const void *arg1, const void *arg2)
1824: {
1825: const struct assegment *seg1 = ((const struct aspath *)arg1)->segments;
1826: const struct assegment *seg2 = ((const struct aspath *)arg2)->segments;
1827:
1828: while (seg1 || seg2)
1829: {
1830: int i;
1831: if ((!seg1 && seg2) || (seg1 && !seg2))
1832: return 0;
1833: if (seg1->type != seg2->type)
1834: return 0;
1835: if (seg1->length != seg2->length)
1836: return 0;
1837: for (i = 0; i < seg1->length; i++)
1838: if (seg1->as[i] != seg2->as[i])
1839: return 0;
1840: seg1 = seg1->next;
1841: seg2 = seg2->next;
1842: }
1843: return 1;
1844: }
1845:
1846: /* AS path hash initialize. */
1847: void
1848: aspath_init (void)
1849: {
1850: ashash = hash_create_size (32767, aspath_key_make, aspath_cmp);
1851: }
1852:
1853: void
1854: aspath_finish (void)
1855: {
1856: hash_free (ashash);
1857: ashash = NULL;
1858:
1859: if (snmp_stream)
1860: stream_free (snmp_stream);
1861: }
1862:
1863: /* return and as path value */
1864: const char *
1865: aspath_print (struct aspath *as)
1866: {
1867: return (as ? as->str : NULL);
1868: }
1869:
1870: /* Printing functions */
1871: /* Feed the AS_PATH to the vty; the suffix string follows it only in case
1872: * AS_PATH wasn't empty.
1873: */
1874: void
1875: aspath_print_vty (struct vty *vty, const char *format, struct aspath *as, const char * suffix)
1876: {
1877: assert (format);
1878: vty_out (vty, format, as->str);
1879: if (strlen (as->str) && strlen (suffix))
1880: vty_out (vty, "%s", suffix);
1881: }
1882:
1883: static void
1884: aspath_show_all_iterator (struct hash_backet *backet, struct vty *vty)
1885: {
1886: struct aspath *as;
1887:
1888: as = (struct aspath *) backet->data;
1889:
1890: vty_out (vty, "[%p:%u] (%ld) ", backet, backet->key, as->refcnt);
1891: vty_out (vty, "%s%s", as->str, VTY_NEWLINE);
1892: }
1893:
1894: /* Print all aspath and hash information. This function is used from
1895: `show ip bgp paths' command. */
1896: void
1897: aspath_print_all_vty (struct vty *vty)
1898: {
1899: hash_iterate (ashash,
1900: (void (*) (struct hash_backet *, void *))
1901: aspath_show_all_iterator,
1902: vty);
1903: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to bgp_aspath.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