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