Statistics
| Branch: | Revision:

iof-bird-daemon / proto / bgp / attrs.c @ bd2d8190

History | View | Annotate | Download (21.1 KB)

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 int 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_OPTIONAL, EAF_TYPE_OPAQUE, 1,                /* BA_ATOMIC_AGGR */
96
    NULL, NULL },
97
  { "aggregator", 6, BAF_OPTIONAL, 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(tmp);
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
        }
376
      if (code < 32)
377
        seen |= 1 << code;
378
      *d = *a;
379
      if ((d->type & EAF_ORIGINATED) && !originate && (d->flags & BAF_TRANSITIVE) && (d->flags & BAF_OPTIONAL))
380
        d->flags |= BAF_PARTIAL;
381
      switch (d->type & EAF_TYPE_MASK)
382
        {
383
        case EAF_TYPE_INT_SET:
384
          {
385
            struct adata *z = alloca(sizeof(struct adata) + d->u.ptr->length);
386
            z->length = d->u.ptr->length;
387
            bgp_normalize_set((u32 *) z->data, (u32 *) d->u.ptr->data, z->length / 4);
388
            d->u.ptr = z;
389
            break;
390
          }
391
        default:
392
        }
393
      d++;
394
      new->count++;
395
    }
396

    
397
  /* Hash */
398
  hash = ea_hash(new);
399
  for(b=p->bucket_hash[hash & (p->hash_size - 1)]; b; b=b->hash_next)
400
    if (b->hash == hash && ea_same(b->eattrs, new))
401
      {
402
        DBG("Found bucket.\n");
403
        return b;
404
      }
405

    
406
  /* Ensure that there are all mandatory attributes */
407
  for(i=0; i<ARRAY_SIZE(bgp_mandatory_attrs); i++)
408
    if (!(seen & (1 << bgp_mandatory_attrs[i])))
409
      {
410
        log(L_ERR "%s: Mandatory attribute %s missing", p->p.name, bgp_attr_table[bgp_mandatory_attrs[i]].name);
411
        return NULL;
412
      }
413

    
414
  if (!bgp_export_check(p, new))
415
    return NULL;
416

    
417
  /* Create new bucket */
418
  DBG("Creating bucket.\n");
419
  return bgp_new_bucket(p, new, hash);
420
}
421

    
422
void
423
bgp_free_bucket(struct bgp_proto *p, struct bgp_bucket *buck)
424
{
425
  if (buck->hash_next)
426
    buck->hash_next->hash_prev = buck->hash_prev;
427
  if (buck->hash_prev)
428
    buck->hash_prev->hash_next = buck->hash_next;
429
  else
430
    p->bucket_hash[buck->hash & (p->hash_size-1)] = buck->hash_next;
431
  mb_free(buck);
432
}
433

    
434
void
435
bgp_rt_notify(struct proto *P, net *n, rte *new, rte *old, ea_list *tmpa)
436
{
437
  struct bgp_proto *p = (struct bgp_proto *) P;
438
  struct bgp_bucket *buck;
439
  struct bgp_prefix *px;
440

    
441
  DBG("BGP: Got route %I/%d %s\n", n->n.prefix, n->n.pxlen, new ? "up" : "down");
442

    
443
  if (new)
444
    {
445
      buck = bgp_get_bucket(p, new->attrs->eattrs, tmpa, new->attrs->source != RTS_BGP);
446
      if (!buck)                        /* Inconsistent attribute list */
447
        return;
448
    }
449
  else
450
    {
451
      if (!(buck = p->withdraw_bucket))
452
        {
453
          buck = p->withdraw_bucket = mb_alloc(P->pool, sizeof(struct bgp_bucket));
454
          init_list(&buck->prefixes);
455
        }
456
    }
457
  px = fib_get(&p->prefix_fib, &n->n.prefix, n->n.pxlen);
458
  if (px->bucket_node.next)
459
    {
460
      DBG("\tRemoving old entry.\n");
461
      rem_node(&px->bucket_node);
462
    }
463
  add_tail(&buck->prefixes, &px->bucket_node);
464
  bgp_schedule_packet(p->conn, PKT_UPDATE);
465
}
466

    
467
static int
468
bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
469
{
470
  ea_list *ea = lp_alloc(pool, sizeof(ea_list) + 3*sizeof(eattr));
471
  eattr *a = ea->attrs;
472
  rta *rta = e->attrs;
473

    
474
  ea->next = *attrs;
475
  *attrs = ea;
476
  ea->flags = EALF_SORTED;
477
  ea->count = 3;
478

    
479
  a->id = EA_CODE(EAP_BGP, BA_ORIGIN);
480
  a->flags = BAF_TRANSITIVE;
481
  a->type = EAF_TYPE_INT;
482
  if (rta->source == RTS_RIP_EXT || rta->source == RTS_OSPF_EXT)
483
    a->u.data = 2;                        /* Incomplete */
484
  else
485
    a->u.data = 0;                        /* IGP */
486
  a++;
487

    
488
  a->id = EA_CODE(EAP_BGP, BA_AS_PATH);
489
  a->flags = BAF_TRANSITIVE;
490
  a->type = EAF_TYPE_AS_PATH;
491
  if (p->is_internal)
492
    {
493
      a->u.ptr = lp_alloc(pool, sizeof(struct adata));
494
      a->u.ptr->length = 0;
495
    }
496
  else
497
    {
498
      byte *z;
499
      a->u.ptr = lp_alloc(pool, sizeof(struct adata) + 4);
500
      a->u.ptr->length = 4;
501
      z = a->u.ptr->data;
502
      z[0] = 2;                                /* AS_SEQUENCE */
503
      z[1] = 1;                                /* 1 AS */
504
      put_u16(z+2, p->local_as);
505
    }
506
  a++;
507

    
508
  a->id = EA_CODE(EAP_BGP, BA_NEXT_HOP);
509
  a->flags = BAF_TRANSITIVE;
510
  a->type = EAF_TYPE_IP_ADDRESS;
511
  a->u.ptr = lp_alloc(pool, sizeof(struct adata) + sizeof(ip_addr));
512
  a->u.ptr->length = sizeof(ip_addr);
513
  if (p->cf->next_hop_self ||
514
      !p->is_internal ||
515
      rta->dest != RTD_ROUTER)
516
    *(ip_addr *)a->u.ptr->data = p->local_addr;
517
  else
518
    *(ip_addr *)a->u.ptr->data = e->attrs->gw;
519

    
520
  return 0;                                /* Leave decision to the filters */
521
}
522

    
523
static ea_list *
524
bgp_path_prepend(struct linpool *pool, eattr *a, ea_list *old, int as)
525
{
526
  struct ea_list *e = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
527
  struct adata *olda = a->u.ptr;
528

    
529
  e->next = old;
530
  e->flags = EALF_SORTED;
531
  e->count = 1;
532
  e->attrs[0].id = EA_CODE(EAP_BGP, BA_AS_PATH);
533
  e->attrs[0].flags = BAF_TRANSITIVE;
534
  e->attrs[0].type = EAF_TYPE_AS_PATH;
535
  e->attrs[0].u.ptr = as_path_prepend(pool, olda, as);
536
  return e;
537
}
538

    
539
static int
540
bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
541
{
542
  eattr *a;
543

    
544
  if (!p->is_internal)
545
    *attrs = bgp_path_prepend(pool, ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH)), *attrs, p->local_as);
546

    
547
  a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP));
548
  if (a && (p->is_internal || (!p->is_internal && e->attrs->iface == p->neigh->iface)))
549
    {
550
      /* Leave the original next hop attribute, will check later where does it point */
551
    }
552
  else
553
    {
554
      /* Need to create new one */
555
      ea_list *ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
556
      ea->next = *attrs;
557
      *attrs = ea;
558
      ea->flags = EALF_SORTED;
559
      ea->count = 1;
560
      a = ea->attrs;
561
      a->id = EA_CODE(EAP_BGP, BA_NEXT_HOP);
562
      a->flags = BAF_TRANSITIVE;
563
      a->type = EAF_TYPE_IP_ADDRESS;
564
      a->u.ptr = lp_alloc(pool, sizeof(struct adata) + sizeof(ip_addr));
565
      a->u.ptr->length = sizeof(ip_addr);
566
      *(ip_addr *)a->u.ptr->data = p->local_addr;
567
    }
568

    
569
  return 0;                                /* Leave decision to the filters */
570
}
571

    
572
int
573
bgp_import_control(struct proto *P, rte **new, ea_list **attrs, struct linpool *pool)
574
{
575
  rte *e = *new;
576
  struct bgp_proto *p = (struct bgp_proto *) P;
577
  struct bgp_proto *new_bgp = (e->attrs->proto->proto == &proto_bgp) ? (struct bgp_proto *) e->attrs->proto : NULL;
578

    
579
  if (p == new_bgp)                        /* Poison reverse updates */
580
    return -1;
581
  if (new_bgp)
582
    {
583
      if (p->local_as == new_bgp->local_as && p->is_internal && new_bgp->is_internal)
584
        return -1;                        /* Don't redistribute internal routes with IBGP */
585
      return bgp_update_attrs(p, e, attrs, pool);
586
    }
587
  else
588
    return bgp_create_attrs(p, e, attrs, pool);
589
}
590

    
591
int
592
bgp_rte_better(rte *new, rte *old)
593
{
594
  struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->proto;
595
  struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->proto;
596
  eattr *x, *y;
597
  u32 n, o;
598

    
599
  /* Start with local preferences */
600
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
601
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
602
  n = x ? x->u.data : new_bgp->cf->default_local_pref;
603
  o = y ? y->u.data : old_bgp->cf->default_local_pref;
604
  if (n > o)
605
    return 1;
606
  if (n < o)
607
    return 0;
608

    
609
  /* Use AS path lengths */
610
  if (new_bgp->cf->compare_path_lengths || old_bgp->cf->compare_path_lengths)
611
    {
612
      x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
613
      y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
614
      n = x ? as_path_getlen(x->u.ptr) : 100000;
615
      o = y ? as_path_getlen(y->u.ptr) : 100000;
616
      if (n < o)
617
        return 1;
618
      if (n > o)
619
        return 0;
620
    }
621

    
622
  /* Use origins */
623
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
624
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
625
  n = x ? x->u.data : 2;
626
  o = y ? y->u.data : 2;
627
  if (n < o)
628
    return 1;
629
  if (n > o)
630
    return 0;
631

    
632
  /* Compare MED's */
633
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
634
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
635
  n = x ? x->u.data : new_bgp->cf->default_med;
636
  o = y ? y->u.data : old_bgp->cf->default_med;
637
  if (n < o)
638
    return 1;
639
  if (n > o)
640
    return 0;
641

    
642
  /* A tie breaking procedure according to RFC 1771, section 9.1.2.1 */
643
  /* We don't have interior distances */
644
  /* We prefer external peers */
645
  if (new_bgp->is_internal > old_bgp->is_internal)
646
    return 0;
647
  if (new_bgp->is_internal < old_bgp->is_internal)
648
    return 1;
649
  /* Finally we compare BGP identifiers */
650
  return (new_bgp->remote_id < old_bgp->remote_id);
651
}
652

    
653
static int
654
bgp_path_loopy(struct bgp_proto *p, eattr *a)
655
{
656
  byte *path = a->u.ptr->data;
657
  int len = a->u.ptr->length;
658
  int i, n;
659

    
660
  while (len > 0)
661
    {
662
      n = path[1];
663
      len -= 2 - 2*n;
664
      path += 2;
665
      for(i=0; i<n; i++)
666
        {
667
          if (get_u16(path) == p->local_as)
668
            return 1;
669
          path += 2;
670
        }
671
    }
672
  return 0;
673
}
674

    
675
struct rta *
676
bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct linpool *pool)
677
{
678
  struct bgp_proto *bgp = conn->bgp;
679
  rta *a = lp_alloc(pool, sizeof(struct rta));
680
  unsigned int flags, code, l, i, type;
681
  int errcode;
682
  byte *z, *attr_start;
683
  byte seen[256/8];
684
  eattr *e;
685
  ea_list *ea;
686
  struct adata *ad;
687
  neighbor *neigh;
688
  ip_addr nexthop;
689

    
690
  a->proto = &bgp->p;
691
  a->source = RTS_BGP;
692
  a->scope = SCOPE_UNIVERSE;
693
  a->cast = RTC_UNICAST;
694
  a->dest = RTD_ROUTER;
695
  a->flags = 0;
696
  a->aflags = 0;
697
  a->from = bgp->cf->remote_ip;
698
  a->eattrs = NULL;
699

    
700
  /* Parse the attributes */
701
  bzero(seen, sizeof(seen));
702
  DBG("BGP: Parsing attributes\n");
703
  while (len)
704
    {
705
      if (len < 2)
706
        goto malformed;
707
      attr_start = attr;
708
      flags = *attr++;
709
      code = *attr++;
710
      len -= 2;
711
      if (flags & BAF_EXT_LEN)
712
        {
713
          if (len < 2)
714
            goto malformed;
715
          l = get_u16(attr);
716
          attr += 2;
717
          len -= 2;
718
        }
719
      else
720
        {
721
          if (len < 1)
722
            goto malformed;
723
          l = *attr++;
724
          len--;
725
        }
726
      if (l > len)
727
        goto malformed;
728
      len -= l;
729
      z = attr;
730
      attr += l;
731
      DBG("Attr %02x %02x %d\n", code, flags, l);
732
      if (seen[code/8] & (1 << (code%8)))
733
        goto malformed;
734
      if (code && code < ARRAY_SIZE(bgp_attr_table))
735
        {
736
          struct attr_desc *desc = &bgp_attr_table[code];
737
          if (desc->expected_length >= 0 && desc->expected_length != (int) l)
738
            { errcode = 5; goto err; }
739
          if ((desc->expected_flags ^ flags) & (BAF_OPTIONAL | BAF_TRANSITIVE))
740
            { errcode = 4; goto err; }
741
          if (!desc->allow_in_ebgp && !bgp->is_internal)
742
            continue;
743
          if (desc->validate)
744
            {
745
              errcode = desc->validate(bgp, z, l);
746
              if (errcode > 0)
747
                goto err;
748
              if (errcode < 0)
749
                continue;
750
            }
751
          type = desc->type;
752
        }
753
      else                                /* Unknown attribute */
754
        {
755
          if (!(flags & BAF_OPTIONAL))
756
            { errcode = 2; goto err; }
757
          type = EAF_TYPE_OPAQUE;
758
        }
759
      seen[code/8] |= (1 << (code%8));
760
      ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
761
      ea->next = a->eattrs;
762
      a->eattrs = ea;
763
      ea->flags = 0;
764
      ea->count = 1;
765
      ea->attrs[0].id = EA_CODE(EAP_BGP, code);
766
      ea->attrs[0].flags = flags;
767
      ea->attrs[0].type = type;
768
      if (type & EAF_EMBEDDED)
769
        ad = NULL;
770
      else
771
        {
772
          ad = lp_alloc(pool, sizeof(struct adata) + l);
773
          ea->attrs[0].u.ptr = ad;
774
          ad->length = l;
775
          memcpy(ad->data, z, l);
776
        }
777
      switch (type)
778
        {
779
        case EAF_TYPE_ROUTER_ID:
780
        case EAF_TYPE_INT:
781
          if (l == 1)
782
            ea->attrs[0].u.data = *z;
783
          else
784
            ea->attrs[0].u.data = get_u32(z);
785
          break;
786
        case EAF_TYPE_IP_ADDRESS:
787
          ipa_ntoh(*(ip_addr *)ad->data);
788
          break;
789
        case EAF_TYPE_INT_SET:
790
          {
791
            u32 *z = (u32 *) ad->data;
792
            for(i=0; i<ad->length/4; i++)
793
              z[i] = ntohl(z[i]);
794
            break;
795
          }
796
        }
797
    }
798

    
799
  /* Check if all mandatory attributes are present */
800
  for(i=0; i < sizeof(bgp_mandatory_attrs)/sizeof(bgp_mandatory_attrs[0]); i++)
801
    {
802
      code = bgp_mandatory_attrs[i];
803
      if (!(seen[code/8] & (1 << (code%8))))
804
        {
805
          bgp_error(conn, 3, 3, code, 1);
806
          return NULL;
807
        }
808
    }
809

    
810
  /* If the AS path attribute contains our AS, reject the routes */
811
  e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
812
  ASSERT(e);
813
  if (bgp_path_loopy(bgp, e))
814
    {
815
      DBG("BGP: Path loop!\n");
816
      return NULL;
817
    }
818

    
819
  /* Fill in the remaining rta fields */
820
  e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP));
821
  ASSERT(e);
822
  nexthop = *(ip_addr *) e->u.ptr->data;
823
  if (ipa_equal(nexthop, bgp->local_addr))
824
    {
825
      DBG("BGP: Loop!\n");
826
      return NULL;
827
    }
828
  neigh = neigh_find(&bgp->p, &nexthop, 0) ? : bgp->neigh;
829
  a->gw = neigh->addr;
830
  a->iface = neigh->iface;
831
  return rta_lookup(a);
832

    
833
malformed:
834
  bgp_error(conn, 3, 1, len, 0);
835
  return NULL;
836

    
837
err:
838
  bgp_error(conn, 3, errcode, code, 0);        /* FIXME: Return attribute data! */
839
  return NULL;
840
}
841

    
842
int
843
bgp_get_attr(eattr *a, byte *buf)
844
{
845
  unsigned int i = EA_ID(a->id);
846
  struct attr_desc *d;
847

    
848
  if (i && i < sizeof(bgp_attr_table)/sizeof(bgp_attr_table[0]))
849
    {
850
      d = &bgp_attr_table[i];
851
      buf += bsprintf(buf, "%s", d->name);
852
      if (d->format)
853
        {
854
          *buf++ = ':';
855
          *buf++ = ' ';
856
          d->format(a, buf);
857
          return GA_FULL;
858
        }
859
      return GA_NAME;
860
    }
861
  bsprintf(buf, "%02x%s", i, (a->flags & BAF_TRANSITIVE) ? "[t]" : "");
862
  return GA_NAME;
863
}
864

    
865
void
866
bgp_attr_init(struct bgp_proto *p)
867
{
868
  p->hash_size = 256;
869
  p->hash_limit = p->hash_size * 4;
870
  p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
871
  init_list(&p->bucket_queue);
872
  p->withdraw_bucket = NULL;
873
  fib_init(&p->prefix_fib, p->p.pool, sizeof(struct bgp_prefix), 0, bgp_init_prefix);
874
}