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