Annotation of embedaddon/quagga/bgpd/bgp_aspath.c, revision 1.1.1.2

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

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>