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