Statistics
| Branch: | Revision:

iof-bird-daemon / proto / bgp / attrs.c @ 99f70c78

History | View | Annotate | Download (21.8 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 byte bgp_mandatory_attrs[] = { BA_ORIGIN, BA_AS_PATH, BA_NEXT_HOP };
26

    
27
struct attr_desc {
28
  char *name;
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
}