proto/bgp/attrs.c

   1 /*
   2  *      BIRD -- BGP Attributes
   3  *
   4  *      (c) 2000 Martin Mares <mj@ucw.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 #define LOCAL_DEBUG
  10
  11 #include <stdlib.h>
  12
  13 #include "nest/bird.h"
  14 #include "nest/iface.h"
  15 #include "nest/protocol.h"
  16 #include "nest/route.h"
  17 #include "nest/attrs.h"
  18 #include "conf/conf.h"
  19 #include "lib/resource.h"
  20 #include "lib/string.h"
  21 #include "lib/unaligned.h"
  22
  23 #include "bgp.h"
  24
  25 static byte bgp_mandatory_attrs[] = { BA_ORIGIN, BA_AS_PATH, BA_NEXT_HOP };
  26
  27 struct attr_desc {
  28   char *name;                           /* FIXME: Use the same names as in filters */
  29   int expected_length;
  30   int expected_flags;
  31   int type;
  32   int allow_in_ebgp;
  33   int (*validate)(struct bgp_proto *p, byte *attr, int len);
  34   void (*format)(eattr *ea, byte *buf);
  35 };
  36
  37 static int
  38 bgp_check_origin(struct bgp_proto *p, byte *a, int len)
  39 {
  40   if (len > 2)
  41     return 6;
  42   return 0;
  43 }
  44
  45 static void
  46 bgp_format_origin(eattr *a, byte *buf)
  47 {
  48   static char *bgp_origin_names[] = { "IGP", "EGP", "Incomplete" };
  49
  50   bsprintf(buf, bgp_origin_names[a->u.data]);
  51 }
  52
  53 static int
  54 bgp_check_path(struct bgp_proto *p, byte *a, int len)
  55 {
  56   while (len)
  57     {
  58       DBG("Path segment %02x %02x\n", a[0], a[1]);
  59       if (len < 2 ||
  60           a[0] != AS_PATH_SET && a[0] != AS_PATH_SEQUENCE ||
  61           2*a[1] + 2 > len)
  62         return 11;
  63       len -= 2*a[1] + 2;
  64       a += 2*a[1] + 2;
  65     }
  66   return 0;
  67 }
  68
  69 static int
  70 bgp_check_next_hop(struct bgp_proto *p, byte *a, int len)
  71 {
  72   ip_addr addr;
  73
  74   memcpy(&addr, a, len);
  75   ipa_ntoh(addr);
  76   if (ipa_classify(addr) & IADDR_HOST)
  77     return 0;
  78   else
  79     return 8;
  80 }
  81
  82 static struct attr_desc bgp_attr_table[] = {
  83   { NULL, -1, 0, 0, 0,                                          /* Undefined */
  84     NULL, NULL },
  85   { "origin", 1, BAF_TRANSITIVE, EAF_TYPE_INT, 1,               /* BA_ORIGIN */
  86     bgp_check_origin, bgp_format_origin },
  87   { "as_path", -1, BAF_TRANSITIVE, EAF_TYPE_AS_PATH, 1,         /* BA_AS_PATH */
  88     bgp_check_path, NULL },
  89   { "next_hop", 4, BAF_TRANSITIVE, EAF_TYPE_IP_ADDRESS, 1,      /* BA_NEXT_HOP */
  90     bgp_check_next_hop, NULL },
  91   { "MED", 4, BAF_OPTIONAL, EAF_TYPE_INT, 0,                    /* BA_MULTI_EXIT_DISC */
  92     NULL, NULL },
  93   { "local_pref", 4, BAF_OPTIONAL, EAF_TYPE_INT, 0,             /* BA_LOCAL_PREF */
  94     NULL, NULL },
  95   { "atomic_aggr", 0, BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1,               /* BA_ATOMIC_AGGR */
  96     NULL, NULL },
  97   { "aggregator", 6, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1,         /* BA_AGGREGATOR */
  98     NULL, NULL },
  99   { "community", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_INT_SET, 1,  /* BA_COMMUNITY */
 100     NULL, NULL },
 101 #if 0
 102   { 0, 0 },                                                                     /* BA_ORIGINATOR_ID */
 103   { 0, 0 },                                                                     /* BA_CLUSTER_LIST */
 104 #endif
 105 };
 106
 107 byte *
 108 bgp_encode_attrs(byte *w, struct bgp_bucket *buck)
 109 {
 110   int remains = 1024;
 111   unsigned int i, code, flags;
 112   byte *start = w;
 113   int len;
 114
 115   w += 2;
 116   for(i=0; i<buck->eattrs->count; i++)
 117     {
 118       eattr *a = &buck->eattrs->attrs[i];
 119       ASSERT(EA_PROTO(a->id) == EAP_BGP);
 120       code = EA_ID(a->id);
 121       flags = a->flags & (BAF_OPTIONAL | BAF_TRANSITIVE | BAF_PARTIAL);
 122       if (code && code < ARRAY_SIZE(bgp_attr_table))
 123         {
 124           struct attr_desc *desc = &bgp_attr_table[code];
 125           len = desc->expected_length;
 126           if (len < 0)
 127             {
 128               ASSERT(!(a->type & EAF_EMBEDDED));
 129               len = a->u.ptr->length;
 130             }
 131         }
 132       else
 133         {
 134           ASSERT((a->type & EAF_TYPE_MASK) == EAF_TYPE_OPAQUE);
 135           len = a->u.ptr->length;
 136         }
 137       DBG("\tAttribute %02x (type %02x, %d bytes, flags %02x)\n", code, a->type, len, flags);
 138       if (remains < len + 4)
 139         {
 140           log(L_ERR "BGP: attribute list too long, ignoring the remaining attributes");
 141           break;
 142         }
 143       if (len < 256)
 144         {
 145           *w++ = flags;
 146           *w++ = code;
 147           *w++ = len;
 148           remains -= 3;
 149         }
 150       else
 151         {
 152           *w++ = flags | BAF_EXT_LEN;
 153           *w++ = code;
 154           put_u16(w, len);
 155           w += 2;
 156           remains -= 4;
 157         }
 158       switch (a->type & EAF_TYPE_MASK)
 159         {
 160         case EAF_TYPE_INT:
 161         case EAF_TYPE_ROUTER_ID:
 162           if (len == 4)
 163             put_u32(w, a->u.data);
 164           else
 165             *w = a->u.data;
 166           break;
 167         case EAF_TYPE_IP_ADDRESS:
 168           {
 169             ip_addr ip = *(ip_addr *)a->u.ptr->data;
 170             ipa_hton(ip);
 171             memcpy(w, &ip, len);
 172             break;
 173           }
 174         case EAF_TYPE_INT_SET:
 175           {
 176             u32 *z = (u32 *)a->u.ptr->data;
 177             int i;
 178             for(i=0; i<len; i+=4)
 179               put_u32(w+i, *z++);
 180             break;
 181           }
 182         case EAF_TYPE_OPAQUE:
 183         case EAF_TYPE_AS_PATH:
 184           memcpy(w, a->u.ptr->data, len);
 185           break;
 186         default:
 187           bug("bgp_encode_attrs: unknown attribute type %02x", a->type);
 188         }
 189       remains -= len;
 190       w += len;
 191     }
 192   put_u16(start, w-start-2);
 193   return w;
 194 }
 195
 196 static void
 197 bgp_init_prefix(struct fib_node *N)
 198 {
 199   struct bgp_prefix *p = (struct bgp_prefix *) N;
 200   p->bucket_node.next = NULL;
 201 }
 202
 203 static int
 204 bgp_compare_u32(const u32 *x, const u32 *y)
 205 {
 206   return (*x < *y) ? -1 : (*x > *y) ? 1 : 0;
 207 }
 208
 209 static void
 210 bgp_normalize_set(u32 *dest, u32 *src, unsigned cnt)
 211 {
 212   memcpy(dest, src, sizeof(u32) * cnt);
 213   qsort(dest, cnt, sizeof(u32), (int(*)(const void *, const void *)) bgp_compare_u32);
 214 }
 215
 216 static void
 217 bgp_rehash_buckets(struct bgp_proto *p)
 218 {
 219   struct bgp_bucket **old = p->bucket_hash;
 220   struct bgp_bucket **new;
 221   unsigned oldn = p->hash_size;
 222   unsigned i, e, mask;
 223   struct bgp_bucket *b;
 224
 225   p->hash_size = p->hash_limit;
 226   DBG("BGP: Rehashing bucket table from %d to %d\n", oldn, p->hash_size);
 227   p->hash_limit *= 4;
 228   if (p->hash_limit >= 65536)
 229     p->hash_limit = ~0;
 230   new = p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
 231   mask = p->hash_size - 1;
 232   for (i=0; i<oldn; i++)
 233     while (b = old[i])
 234       {
 235         old[i] = b->hash_next;
 236         e = b->hash & mask;
 237         b->hash_next = new[e];
 238         if (b->hash_next)
 239           b->hash_next->hash_prev = b;
 240         b->hash_prev = NULL;
 241         new[e] = b;
 242       }
 243   mb_free(old);
 244 }
 245
 246 static struct bgp_bucket *
 247 bgp_new_bucket(struct bgp_proto *p, ea_list *new, unsigned hash)
 248 {
 249   struct bgp_bucket *b;
 250   unsigned ea_size = sizeof(ea_list) + new->count * sizeof(eattr);
 251   unsigned ea_size_aligned = ALIGN(ea_size, CPU_STRUCT_ALIGN);
 252   unsigned size = sizeof(struct bgp_bucket) + ea_size;
 253   unsigned i;
 254   byte *dest;
 255   unsigned index = hash & (p->hash_size - 1);
 256
 257   /* Gather total size of non-inline attributes */
 258   for (i=0; i<new->count; i++)
 259     {
 260       eattr *a = &new->attrs[i];
 261       if (!(a->type & EAF_EMBEDDED))
 262         size += ALIGN(sizeof(struct adata) + a->u.ptr->length, CPU_STRUCT_ALIGN);
 263     }
 264
 265   /* Create the bucket and hash it */
 266   b = mb_alloc(p->p.pool, size);
 267   b->hash_next = p->bucket_hash[index];
 268   if (b->hash_next)
 269     b->hash_next->hash_prev = b;
 270   p->bucket_hash[index] = b;
 271   b->hash_prev = NULL;
 272   b->hash = hash;
 273   add_tail(&p->bucket_queue, &b->send_node);
 274   init_list(&b->prefixes);
 275   memcpy(b->eattrs, new, ea_size);
 276   dest = ((byte *)b->eattrs) + ea_size_aligned;
 277
 278   /* Copy values of non-inline attributes */
 279   for (i=0; i<new->count; i++)
 280     {
 281       eattr *a = &new->attrs[i];
 282       if (!(a->type & EAF_EMBEDDED))
 283         {
 284           struct adata *oa = a->u.ptr;
 285           struct adata *na = (struct adata *) dest;
 286           memcpy(na, oa, sizeof(struct adata) + oa->length);
 287           a->u.ptr = na;
 288           dest += ALIGN(na->length, CPU_STRUCT_ALIGN);
 289         }
 290     }
 291
 292   /* If needed, rehash */
 293   p->hash_count++;
 294   if (p->hash_count > p->hash_limit)
 295     bgp_rehash_buckets(p);
 296
 297   return b;
 298 }
 299
 300 static int
 301 bgp_export_check(struct bgp_proto *p, ea_list *new)
 302 {
 303   eattr *a;
 304   struct adata *d;
 305
 306   /* Check if next hop is valid */
 307   a = ea_find(new, EA_CODE(EAP_BGP, BA_NEXT_HOP));
 308   if (!a || ipa_equal(p->next_hop, *(ip_addr *)a->u.ptr))
 309     {
 310       DBG("\tInvalid NEXT_HOP\n");
 311       return 0;
 312     }
 313
 314   /* Check if we aren't forbidden to export the route by communities */
 315   a = ea_find(new, EA_CODE(EAP_BGP, BA_COMMUNITY));
 316   if (a)
 317     {
 318       d = a->u.ptr;
 319       if (int_set_contains(d, BGP_COMM_NO_ADVERTISE))
 320         {
 321           DBG("\tNO_ADVERTISE\n");
 322           return 0;
 323         }
 324       if (!p->is_internal &&
 325           (int_set_contains(d, BGP_COMM_NO_EXPORT) ||
 326            int_set_contains(d, BGP_COMM_NO_EXPORT_SUBCONFED)))
 327         {
 328           DBG("\tNO_EXPORT\n");
 329           return 0;
 330         }
 331     }
 332
 333   return 1;
 334 }
 335
 336 static struct bgp_bucket *
 337 bgp_get_bucket(struct bgp_proto *p, ea_list *old, ea_list *tmp, int originate)
 338 {
 339   ea_list *t, *new;
 340   unsigned i, cnt, hash, code;
 341   eattr *a, *d;
 342   u32 seen = 0;
 343   struct bgp_bucket *b;
 344
 345   /* Merge the attribute lists */
 346   for(t=tmp; t->next; t=t->next)
 347     ;
 348   t->next = old;
 349   new = alloca(ea_scan(tmp));
 350   ea_merge(tmp, new);
 351   t->next = NULL;
 352   ea_sort(new);
 353
 354   /* Normalize attributes */
 355   d = new->attrs;
 356   cnt = new->count;
 357   new->count = 0;
 358   for(i=0; i<cnt; i++)
 359     {
 360       a = &new->attrs[i];
 361 #ifdef LOCAL_DEBUG
 362       {
 363         byte buf[EA_FORMAT_BUF_SIZE];
 364         ea_format(a, buf);
 365         DBG("\t%s\n", buf);
 366       }
 367 #endif
 368       if (EA_PROTO(a->id) != EAP_BGP)
 369         continue;
 370       code = EA_ID(a->id);
 371       if (code < ARRAY_SIZE(bgp_attr_table))
 372         {
 373           if (!bgp_attr_table[code].allow_in_ebgp && !p->is_internal)
 374             continue;
 375           /* The flags might have been zero if the attr was added by filters */
 376           a->flags = (a->flags & BAF_PARTIAL) | bgp_attr_table[code].expected_flags;
 377         }
 378       if (code < 32)
 379         seen |= 1 << code;
 380       *d = *a;
 381       if ((d->type & EAF_ORIGINATED) && !originate && (d->flags & BAF_TRANSITIVE) && (d->flags & BAF_OPTIONAL))
 382         d->flags |= BAF_PARTIAL;
 383       switch (d->type & EAF_TYPE_MASK)
 384         {
 385         case EAF_TYPE_INT_SET:
 386           {
 387             struct adata *z = alloca(sizeof(struct adata) + d->u.ptr->length);
 388             z->length = d->u.ptr->length;
 389             bgp_normalize_set((u32 *) z->data, (u32 *) d->u.ptr->data, z->length / 4);
 390             d->u.ptr = z;
 391             break;
 392           }
 393         default:
 394         }
 395       d++;
 396       new->count++;
 397     }
 398
 399   /* Hash */
 400   hash = ea_hash(new);
 401   for(b=p->bucket_hash[hash & (p->hash_size - 1)]; b; b=b->hash_next)
 402     if (b->hash == hash && ea_same(b->eattrs, new))
 403       {
 404         DBG("Found bucket.\n");
 405         return b;
 406       }
 407
 408   /* Ensure that there are all mandatory attributes */
 409   for(i=0; i<ARRAY_SIZE(bgp_mandatory_attrs); i++)
 410     if (!(seen & (1 << bgp_mandatory_attrs[i])))
 411       {
 412         log(L_ERR "%s: Mandatory attribute %s missing", p->p.name, bgp_attr_table[bgp_mandatory_attrs[i]].name);
 413         return NULL;
 414       }
 415
 416   if (!bgp_export_check(p, new))
 417     return NULL;
 418
 419   /* Create new bucket */
 420   DBG("Creating bucket.\n");
 421   return bgp_new_bucket(p, new, hash);
 422 }
 423
 424 void
 425 bgp_free_bucket(struct bgp_proto *p, struct bgp_bucket *buck)
 426 {
 427   if (buck->hash_next)
 428     buck->hash_next->hash_prev = buck->hash_prev;
 429   if (buck->hash_prev)
 430     buck->hash_prev->hash_next = buck->hash_next;
 431   else
 432     p->bucket_hash[buck->hash & (p->hash_size-1)] = buck->hash_next;
 433   mb_free(buck);
 434 }
 435
 436 void
 437 bgp_rt_notify(struct proto *P, net *n, rte *new, rte *old, ea_list *tmpa)
 438 {
 439   struct bgp_proto *p = (struct bgp_proto *) P;
 440   struct bgp_bucket *buck;
 441   struct bgp_prefix *px;
 442
 443   DBG("BGP: Got route %I/%d %s\n", n->n.prefix, n->n.pxlen, new ? "up" : "down");
 444
 445   if (new)
 446     {
 447       buck = bgp_get_bucket(p, new->attrs->eattrs, tmpa, new->attrs->source != RTS_BGP);
 448       if (!buck)                        /* Inconsistent attribute list */
 449         return;
 450     }
 451   else
 452     {
 453       if (!(buck = p->withdraw_bucket))
 454         {
 455           buck = p->withdraw_bucket = mb_alloc(P->pool, sizeof(struct bgp_bucket));
 456           init_list(&buck->prefixes);
 457         }
 458     }
 459   px = fib_get(&p->prefix_fib, &n->n.prefix, n->n.pxlen);
 460   if (px->bucket_node.next)
 461     {
 462       DBG("\tRemoving old entry.\n");
 463       rem_node(&px->bucket_node);
 464     }
 465   add_tail(&buck->prefixes, &px->bucket_node);
 466   bgp_schedule_packet(p->conn, PKT_UPDATE);
 467 }
 468
 469 static int
 470 bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
 471 {
 472   ea_list *ea = lp_alloc(pool, sizeof(ea_list) + 4*sizeof(eattr));
 473   eattr *a = ea->attrs;
 474   rta *rta = e->attrs;
 475
 476   ea->next = *attrs;
 477   *attrs = ea;
 478   ea->flags = EALF_SORTED;
 479   ea->count = 4;
 480
 481   a->id = EA_CODE(EAP_BGP, BA_ORIGIN);
 482   a->flags = BAF_TRANSITIVE;
 483   a->type = EAF_TYPE_INT;
 484   if (rta->source == RTS_RIP_EXT || rta->source == RTS_OSPF_EXT)
 485     a->u.data = 2;                      /* Incomplete */
 486   else
 487     a->u.data = 0;                      /* IGP */
 488   a++;
 489
 490   a->id = EA_CODE(EAP_BGP, BA_AS_PATH);
 491   a->flags = BAF_TRANSITIVE;
 492   a->type = EAF_TYPE_AS_PATH;
 493   if (p->is_internal)
 494     {
 495       a->u.ptr = lp_alloc(pool, sizeof(struct adata));
 496       a->u.ptr->length = 0;
 497     }
 498   else
 499     {
 500       byte *z;
 501       a->u.ptr = lp_alloc(pool, sizeof(struct adata) + 4);
 502       a->u.ptr->length = 4;
 503       z = a->u.ptr->data;
 504       z[0] = AS_PATH_SEQUENCE;
 505       z[1] = 1;                         /* 1 AS */
 506       put_u16(z+2, p->local_as);
 507     }
 508   a++;
 509
 510   a->id = EA_CODE(EAP_BGP, BA_NEXT_HOP);
 511   a->flags = BAF_TRANSITIVE;
 512   a->type = EAF_TYPE_IP_ADDRESS;
 513   a->u.ptr = lp_alloc(pool, sizeof(struct adata) + sizeof(ip_addr));
 514   a->u.ptr->length = sizeof(ip_addr);
 515   if (p->cf->next_hop_self ||
 516       !p->is_internal ||
 517       rta->dest != RTD_ROUTER)
 518     *(ip_addr *)a->u.ptr->data = p->local_addr;
 519   else
 520     *(ip_addr *)a->u.ptr->data = e->attrs->gw;
 521   a++;
 522
 523   a->id = EA_CODE(EAP_BGP, BA_LOCAL_PREF);
 524   a->flags = BAF_OPTIONAL;
 525   a->type = EAF_TYPE_INT;
 526   a->u.data = 0;
 527
 528   return 0;                             /* Leave decision to the filters */
 529 }
 530
 531 static ea_list *
 532 bgp_path_prepend(struct linpool *pool, eattr *a, ea_list *old, int as)
 533 {
 534   struct ea_list *e = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
 535   struct adata *olda = a->u.ptr;
 536
 537   e->next = old;
 538   e->flags = EALF_SORTED;
 539   e->count = 1;
 540   e->attrs[0].id = EA_CODE(EAP_BGP, BA_AS_PATH);
 541   e->attrs[0].flags = BAF_TRANSITIVE;
 542   e->attrs[0].type = EAF_TYPE_AS_PATH;
 543   e->attrs[0].u.ptr = as_path_prepend(pool, olda, as);
 544   return e;
 545 }
 546
 547 static int
 548 bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
 549 {
 550   eattr *a;
 551
 552   if (!p->is_internal)
 553     *attrs = bgp_path_prepend(pool, ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH)), *attrs, p->local_as);
 554
 555   a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP));
 556   if (a && (p->is_internal || (!p->is_internal && e->attrs->iface == p->neigh->iface)))
 557     {
 558       /* Leave the original next hop attribute, will check later where does it point */
 559     }
 560   else
 561     {
 562       /* Need to create new one */
 563       ea_list *ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
 564       ea->next = *attrs;
 565       *attrs = ea;
 566       ea->flags = EALF_SORTED;
 567       ea->count = 1;
 568       a = ea->attrs;
 569       a->id = EA_CODE(EAP_BGP, BA_NEXT_HOP);
 570       a->flags = BAF_TRANSITIVE;
 571       a->type = EAF_TYPE_IP_ADDRESS;
 572       a->u.ptr = lp_alloc(pool, sizeof(struct adata) + sizeof(ip_addr));
 573       a->u.ptr->length = sizeof(ip_addr);
 574       *(ip_addr *)a->u.ptr->data = p->local_addr;
 575     }
 576
 577   return 0;                             /* Leave decision to the filters */
 578 }
 579
 580 int
 581 bgp_import_control(struct proto *P, rte **new, ea_list **attrs, struct linpool *pool)
 582 {
 583   rte *e = *new;
 584   struct bgp_proto *p = (struct bgp_proto *) P;
 585   struct bgp_proto *new_bgp = (e->attrs->proto->proto == &proto_bgp) ? (struct bgp_proto *) e->attrs->proto : NULL;
 586
 587   if (p == new_bgp)                     /* Poison reverse updates */
 588     return -1;
 589   if (new_bgp)
 590     {
 591       if (p->local_as == new_bgp->local_as && p->is_internal && new_bgp->is_internal)
 592         return -1;                      /* Don't redistribute internal routes with IBGP */
 593       return bgp_update_attrs(p, e, attrs, pool);
 594     }
 595   else
 596     return bgp_create_attrs(p, e, attrs, pool);
 597 }
 598
 599 int
 600 bgp_rte_better(rte *new, rte *old)
 601 {
 602   struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->proto;
 603   struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->proto;
 604   eattr *x, *y;
 605   u32 n, o;
 606
 607   /* Start with local preferences */
 608   x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
 609   y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
 610   n = x ? x->u.data : new_bgp->cf->default_local_pref;
 611   o = y ? y->u.data : old_bgp->cf->default_local_pref;
 612   if (n > o)
 613     return 1;
 614   if (n < o)
 615     return 0;
 616
 617   /* Use AS path lengths */
 618   if (new_bgp->cf->compare_path_lengths || old_bgp->cf->compare_path_lengths)
 619     {
 620       x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
 621       y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
 622       n = x ? as_path_getlen(x->u.ptr) : 100000;
 623       o = y ? as_path_getlen(y->u.ptr) : 100000;
 624       if (n < o)
 625         return 1;
 626       if (n > o)
 627         return 0;
 628     }
 629
 630   /* Use origins */
 631   x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
 632   y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
 633   n = x ? x->u.data : 2;
 634   o = y ? y->u.data : 2;
 635   if (n < o)
 636     return 1;
 637   if (n > o)
 638     return 0;
 639
 640   /* Compare MED's */
 641   x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
 642   y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
 643   n = x ? x->u.data : new_bgp->cf->default_med;
 644   o = y ? y->u.data : old_bgp->cf->default_med;
 645   if (n < o)
 646     return 1;
 647   if (n > o)
 648     return 0;
 649
 650   /* A tie breaking procedure according to RFC 1771, section 9.1.2.1 */
 651   /* We don't have interior distances */
 652   /* We prefer external peers */
 653   if (new_bgp->is_internal > old_bgp->is_internal)
 654     return 0;
 655   if (new_bgp->is_internal < old_bgp->is_internal)
 656     return 1;
 657   /* Finally we compare BGP identifiers */
 658   return (new_bgp->remote_id < old_bgp->remote_id);
 659 }
 660
 661 static int
 662 bgp_path_loopy(struct bgp_proto *p, eattr *a)
 663 {
 664   byte *path = a->u.ptr->data;
 665   int len = a->u.ptr->length;
 666   int i, n;
 667
 668   while (len > 0)
 669     {
 670       n = path[1];
 671       len -= 2 - 2*n;
 672       path += 2;
 673       for(i=0; i<n; i++)
 674         {
 675           if (get_u16(path) == p->local_as)
 676             return 1;
 677           path += 2;
 678         }
 679     }
 680   return 0;
 681 }
 682
 683 struct rta *
 684 bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct linpool *pool, int mandatory)
 685 {
 686   struct bgp_proto *bgp = conn->bgp;
 687   rta *a = lp_alloc(pool, sizeof(struct rta));
 688   unsigned int flags, code, l, i, type;
 689   int errcode;
 690   byte *z, *attr_start;
 691   byte seen[256/8];
 692   eattr *e;
 693   ea_list *ea;
 694   struct adata *ad;
 695   neighbor *neigh;
 696   ip_addr nexthop;
 697
 698   a->proto = &bgp->p;
 699   a->source = RTS_BGP;
 700   a->scope = SCOPE_UNIVERSE;
 701   a->cast = RTC_UNICAST;
 702   a->dest = RTD_ROUTER;
 703   a->flags = 0;
 704   a->aflags = 0;
 705   a->from = bgp->cf->remote_ip;
 706   a->eattrs = NULL;
 707
 708   /* Parse the attributes */
 709   bzero(seen, sizeof(seen));
 710   DBG("BGP: Parsing attributes\n");
 711   while (len)
 712     {
 713       if (len < 2)
 714         goto malformed;
 715       attr_start = attr;
 716       flags = *attr++;
 717       code = *attr++;
 718       len -= 2;
 719       if (flags & BAF_EXT_LEN)
 720         {
 721           if (len < 2)
 722             goto malformed;
 723           l = get_u16(attr);
 724           attr += 2;
 725           len -= 2;
 726         }
 727       else
 728         {
 729           if (len < 1)
 730             goto malformed;
 731           l = *attr++;
 732           len--;
 733         }
 734       if (l > len)
 735         goto malformed;
 736       len -= l;
 737       z = attr;
 738       attr += l;
 739       DBG("Attr %02x %02x %d\n", code, flags, l);
 740       if (seen[code/8] & (1 << (code%8)))
 741         goto malformed;
 742       if (code && code < ARRAY_SIZE(bgp_attr_table))
 743         {
 744           struct attr_desc *desc = &bgp_attr_table[code];
 745           if (desc->expected_length >= 0 && desc->expected_length != (int) l)
 746             { errcode = 5; goto err; }
 747           if ((desc->expected_flags ^ flags) & (BAF_OPTIONAL | BAF_TRANSITIVE))
 748             { errcode = 4; goto err; }
 749           if (!desc->allow_in_ebgp && !bgp->is_internal)
 750             continue;
 751           if (desc->validate)
 752             {
 753               errcode = desc->validate(bgp, z, l);
 754               if (errcode > 0)
 755                 goto err;
 756               if (errcode < 0)
 757                 continue;
 758             }
 759           type = desc->type;
 760         }
 761       else                              /* Unknown attribute */
 762         {
 763           if (!(flags & BAF_OPTIONAL))
 764             { errcode = 2; goto err; }
 765           type = EAF_TYPE_OPAQUE;
 766         }
 767       seen[code/8] |= (1 << (code%8));
 768       ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
 769       ea->next = a->eattrs;
 770       a->eattrs = ea;
 771       ea->flags = 0;
 772       ea->count = 1;
 773       ea->attrs[0].id = EA_CODE(EAP_BGP, code);
 774       ea->attrs[0].flags = flags;
 775       ea->attrs[0].type = type;
 776       if (type & EAF_EMBEDDED)
 777         ad = NULL;
 778       else
 779         {
 780           ad = lp_alloc(pool, sizeof(struct adata) + l);
 781           ea->attrs[0].u.ptr = ad;
 782           ad->length = l;
 783           memcpy(ad->data, z, l);
 784         }
 785       switch (type)
 786         {
 787         case EAF_TYPE_ROUTER_ID:
 788         case EAF_TYPE_INT:
 789           if (l == 1)
 790             ea->attrs[0].u.data = *z;
 791           else
 792             ea->attrs[0].u.data = get_u32(z);
 793           break;
 794         case EAF_TYPE_IP_ADDRESS:
 795           ipa_ntoh(*(ip_addr *)ad->data);
 796           break;
 797         case EAF_TYPE_INT_SET:
 798           {
 799             u32 *z = (u32 *) ad->data;
 800             for(i=0; i<ad->length/4; i++)
 801               z[i] = ntohl(z[i]);
 802             break;
 803           }
 804         }
 805     }
 806
 807   /* Check if all mandatory attributes are present */
 808   if (mandatory)
 809     {
 810       for(i=0; i < ARRAY_SIZE(bgp_mandatory_attrs); i++)
 811         {
 812           code = bgp_mandatory_attrs[i];
 813           if (!(seen[code/8] & (1 << (code%8))))
 814             {
 815               bgp_error(conn, 3, 3, &bgp_mandatory_attrs[i], 1);
 816               return NULL;
 817             }
 818         }
 819     }
 820
 821   /* If the AS path attribute contains our AS, reject the routes */
 822   e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
 823   ASSERT(e);
 824   if (bgp_path_loopy(bgp, e))
 825     {
 826       DBG("BGP: Path loop!\n");
 827       return NULL;
 828     }
 829
 830   /* If there's no local preference, define one */
 831   if (!(seen[0] && (1 << BA_LOCAL_PREF)))
 832     {
 833       ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
 834       ea->next = a->eattrs;
 835       a->eattrs = ea;
 836       ea->flags = 0;
 837       ea->count = 1;
 838       ea->attrs[0].id = EA_CODE(EAP_BGP, BA_LOCAL_PREF);
 839       ea->attrs[0].flags = BAF_OPTIONAL;
 840       ea->attrs[0].type = EAF_TYPE_INT;
 841       ea->attrs[0].u.data = 0;
 842     }
 843
 844   /* Fill in the remaining rta fields */
 845   e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP));
 846   ASSERT(e);
 847   nexthop = *(ip_addr *) e->u.ptr->data;
 848   if (ipa_equal(nexthop, bgp->local_addr))
 849     {
 850       DBG("BGP: Loop!\n");
 851       return NULL;
 852     }
 853   neigh = neigh_find(&bgp->p, &nexthop, 0) ? : bgp->neigh;
 854   a->gw = neigh->addr;
 855   a->iface = neigh->iface;
 856   return a;
 857
 858 malformed:
 859   bgp_error(conn, 3, 1, NULL, 0);
 860   return NULL;
 861
 862 err:
 863   bgp_error(conn, 3, errcode, z-2, l+2);
 864   return NULL;
 865 }
 866
 867 int
 868 bgp_get_attr(eattr *a, byte *buf)
 869 {
 870   unsigned int i = EA_ID(a->id);
 871   struct attr_desc *d;
 872
 873   if (i && i < ARRAY_SIZE(bgp_attr_table))
 874     {
 875       d = &bgp_attr_table[i];
 876       buf += bsprintf(buf, "%s", d->name);
 877       if (d->format)
 878         {
 879           *buf++ = ':';
 880           *buf++ = ' ';
 881           d->format(a, buf);
 882           return GA_FULL;
 883         }
 884       return GA_NAME;
 885     }
 886   bsprintf(buf, "%02x%s", i, (a->flags & BAF_TRANSITIVE) ? "[t]" : "");
 887   return GA_NAME;
 888 }
 889
 890 void
 891 bgp_attr_init(struct bgp_proto *p)
 892 {
 893   p->hash_size = 256;
 894   p->hash_limit = p->hash_size * 4;
 895   p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
 896   init_list(&p->bucket_queue);
 897   p->withdraw_bucket = NULL;
 898   fib_init(&p->prefix_fib, p->p.pool, sizeof(struct bgp_prefix), 0, bgp_init_prefix);
 899 }