Statistics
| Branch: | Revision:

iof-bird-daemon / proto / bgp / attrs.c @ 56a2bed4

History | View | Annotate | Download (20.5 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 struct bgp_bucket *
301
bgp_get_bucket(struct bgp_proto *p, ea_list *old, ea_list *tmp, int originate)
302
{
303
  ea_list *t, *new;
304
  unsigned i, cnt, hash, code;
305
  eattr *a, *d;
306
  u32 seen = 0;
307
  struct bgp_bucket *b;
308

    
309
  /* Merge the attribute lists */
310
  for(t=tmp; t->next; t=t->next)
311
    ;
312
  t->next = old;
313
  new = alloca(ea_scan(tmp));
314
  ea_merge(tmp, new);
315
  t->next = NULL;
316
  ea_sort(tmp);
317

    
318
  /* Normalize attributes */
319
  d = new->attrs;
320
  cnt = new->count;
321
  new->count = 0;
322
  for(i=0; i<cnt; i++)
323
    {
324
      a = &new->attrs[i];
325
#ifdef LOCAL_DEBUG
326
      {
327
        byte buf[EA_FORMAT_BUF_SIZE];
328
        ea_format(a, buf);
329
        DBG("\t%s\n", buf);
330
      }
331
#endif
332
      if (EA_PROTO(a->id) != EAP_BGP)
333
        continue;
334
      code = EA_ID(a->id);
335
      if (code < ARRAY_SIZE(bgp_attr_table))
336
        {
337
          if (!bgp_attr_table[code].allow_in_ebgp && !p->is_internal)
338
            continue;
339
        }
340
      if (code < 32)
341
        seen |= 1 << code;
342
      *d = *a;
343
      if ((d->type & EAF_ORIGINATED) && !originate && (d->flags & BAF_TRANSITIVE) && (d->flags & BAF_OPTIONAL))
344
        d->flags |= BAF_PARTIAL;
345
      switch (d->type & EAF_TYPE_MASK)
346
        {
347
        case EAF_TYPE_INT_SET:
348
          {
349
            struct adata *z = alloca(sizeof(struct adata) + d->u.ptr->length);
350
            z->length = d->u.ptr->length;
351
            bgp_normalize_set((u32 *) z->data, (u32 *) d->u.ptr->data, z->length / 4);
352
            d->u.ptr = z;
353
            break;
354
          }
355
        default:
356
        }
357
      d++;
358
      new->count++;
359
    }
360

    
361
  /* Hash */
362
  hash = ea_hash(new);
363
  for(b=p->bucket_hash[hash & (p->hash_size - 1)]; b; b=b->hash_next)
364
    if (b->hash == hash && ea_same(b->eattrs, new))
365
      {
366
        DBG("Found bucket.\n");
367
        return b;
368
      }
369

    
370
  /* Ensure that there are all mandatory attributes */
371
  for(i=0; i<ARRAY_SIZE(bgp_mandatory_attrs); i++)
372
    if (!(seen & (1 << bgp_mandatory_attrs[i])))
373
      {
374
        log(L_ERR "%s: Mandatory attribute %s missing", p->p.name, bgp_attr_table[bgp_mandatory_attrs[i]].name);
375
        return NULL;
376
      }
377

    
378
  /* Check if next hop is valid */
379
  a = ea_find(new, EA_CODE(EAP_BGP, BA_NEXT_HOP));
380
  ASSERT(a);
381
  if (ipa_equal(p->next_hop, *(ip_addr *)a->u.ptr))
382
    return NULL;
383

    
384
  /* Create new bucket */
385
  DBG("Creating bucket.\n");
386
  return bgp_new_bucket(p, new, hash);
387
}
388

    
389
void
390
bgp_free_bucket(struct bgp_proto *p, struct bgp_bucket *buck)
391
{
392
  if (buck->hash_next)
393
    buck->hash_next->hash_prev = buck->hash_prev;
394
  if (buck->hash_prev)
395
    buck->hash_prev->hash_next = buck->hash_next;
396
  else
397
    p->bucket_hash[buck->hash & (p->hash_size-1)] = buck->hash_next;
398
  mb_free(buck);
399
}
400

    
401
void
402
bgp_rt_notify(struct proto *P, net *n, rte *new, rte *old, ea_list *tmpa)
403
{
404
  struct bgp_proto *p = (struct bgp_proto *) P;
405
  struct bgp_bucket *buck;
406
  struct bgp_prefix *px;
407

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

    
410
  if (new)
411
    {
412
      buck = bgp_get_bucket(p, new->attrs->eattrs, tmpa, new->attrs->source != RTS_BGP);
413
      if (!buck)                        /* Inconsistent attribute list */
414
        return;
415
    }
416
  else
417
    {
418
      if (!(buck = p->withdraw_bucket))
419
        {
420
          buck = p->withdraw_bucket = mb_alloc(P->pool, sizeof(struct bgp_bucket));
421
          init_list(&buck->prefixes);
422
        }
423
    }
424
  px = fib_get(&p->prefix_fib, &n->n.prefix, n->n.pxlen);
425
  if (px->bucket_node.next)
426
    {
427
      DBG("\tRemoving old entry.\n");
428
      rem_node(&px->bucket_node);
429
    }
430
  add_tail(&buck->prefixes, &px->bucket_node);
431
  bgp_schedule_packet(p->conn, PKT_UPDATE);
432
}
433

    
434
static int
435
bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
436
{
437
  ea_list *ea = lp_alloc(pool, sizeof(ea_list) + 3*sizeof(eattr));
438
  eattr *a = ea->attrs;
439
  rta *rta = e->attrs;
440

    
441
  ea->next = *attrs;
442
  *attrs = ea;
443
  ea->flags = EALF_SORTED;
444
  ea->count = 3;
445

    
446
  a->id = EA_CODE(EAP_BGP, BA_ORIGIN);
447
  a->flags = BAF_TRANSITIVE;
448
  a->type = EAF_TYPE_INT;
449
  if (rta->source == RTS_RIP_EXT || rta->source == RTS_OSPF_EXT)
450
    a->u.data = 2;                        /* Incomplete */
451
  else
452
    a->u.data = 0;                        /* IGP */
453
  a++;
454

    
455
  a->id = EA_CODE(EAP_BGP, BA_AS_PATH);
456
  a->flags = BAF_TRANSITIVE;
457
  a->type = EAF_TYPE_AS_PATH;
458
  if (p->is_internal)
459
    {
460
      a->u.ptr = lp_alloc(pool, sizeof(struct adata));
461
      a->u.ptr->length = 0;
462
    }
463
  else
464
    {
465
      byte *z;
466
      a->u.ptr = lp_alloc(pool, sizeof(struct adata) + 4);
467
      a->u.ptr->length = 4;
468
      z = a->u.ptr->data;
469
      z[0] = 2;                                /* AS_SEQUENCE */
470
      z[1] = 1;                                /* 1 AS */
471
      put_u16(z+2, p->local_as);
472
    }
473
  a++;
474

    
475
  a->id = EA_CODE(EAP_BGP, BA_NEXT_HOP);
476
  a->flags = BAF_TRANSITIVE;
477
  a->type = EAF_TYPE_IP_ADDRESS;
478
  a->u.ptr = lp_alloc(pool, sizeof(struct adata) + sizeof(ip_addr));
479
  a->u.ptr->length = sizeof(ip_addr);
480
  if (p->cf->next_hop_self ||
481
      !p->is_internal ||
482
      rta->dest != RTD_ROUTER)
483
    *(ip_addr *)a->u.ptr->data = p->local_addr;
484
  else
485
    *(ip_addr *)a->u.ptr->data = e->attrs->gw;
486

    
487
  return 0;                                /* Leave decision to the filters */
488
}
489

    
490
static ea_list *
491
bgp_path_prepend(struct linpool *pool, eattr *a, ea_list *old, int as)
492
{
493
  struct ea_list *e = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
494
  struct adata *olda = a->u.ptr;
495

    
496
  e->next = old;
497
  e->flags = EALF_SORTED;
498
  e->count = 1;
499
  e->attrs[0].id = EA_CODE(EAP_BGP, BA_AS_PATH);
500
  e->attrs[0].flags = BAF_TRANSITIVE;
501
  e->attrs[0].type = EAF_TYPE_AS_PATH;
502
  e->attrs[0].u.ptr = as_path_prepend(pool, olda, as);
503
  return e;
504
}
505

    
506
static int
507
bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
508
{
509
  eattr *a;
510

    
511
  if (!p->is_internal)
512
    *attrs = bgp_path_prepend(pool, ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH)), *attrs, p->local_as);
513

    
514
  a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP));
515
  if (a && (p->is_internal || (!p->is_internal && e->attrs->iface == p->neigh->iface)))
516
    {
517
      /* Leave the original next hop attribute, will check later where does it point */
518
    }
519
  else
520
    {
521
      /* Need to create new one */
522
      ea_list *ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
523
      ea->next = *attrs;
524
      *attrs = ea;
525
      ea->flags = EALF_SORTED;
526
      ea->count = 1;
527
      a = ea->attrs;
528
      a->id = EA_CODE(EAP_BGP, BA_NEXT_HOP);
529
      a->flags = BAF_TRANSITIVE;
530
      a->type = EAF_TYPE_IP_ADDRESS;
531
      a->u.ptr = lp_alloc(pool, sizeof(struct adata) + sizeof(ip_addr));
532
      a->u.ptr->length = sizeof(ip_addr);
533
      *(ip_addr *)a->u.ptr->data = p->local_addr;
534
    }
535

    
536
  return 0;                                /* Leave decision to the filters */
537
}
538

    
539
int
540
bgp_import_control(struct proto *P, rte **new, ea_list **attrs, struct linpool *pool)
541
{
542
  rte *e = *new;
543
  struct bgp_proto *p = (struct bgp_proto *) P;
544
  struct bgp_proto *new_bgp = (e->attrs->proto->proto == &proto_bgp) ? (struct bgp_proto *) e->attrs->proto : NULL;
545

    
546
  if (p == new_bgp)                        /* Poison reverse updates */
547
    return -1;
548
  if (new_bgp)
549
    {
550
      if (p->local_as == new_bgp->local_as && p->is_internal && new_bgp->is_internal)
551
        return -1;                        /* Don't redistribute internal routes with IBGP */
552
      return bgp_update_attrs(p, e, attrs, pool);
553
    }
554
  else
555
    return bgp_create_attrs(p, e, attrs, pool);
556
}
557

    
558
int
559
bgp_rte_better(rte *new, rte *old)
560
{
561
  struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->proto;
562
  struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->proto;
563
  eattr *x, *y;
564
  u32 n, o;
565

    
566
  /* Start with local preferences */
567
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
568
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
569
  n = x ? x->u.data : new_bgp->cf->default_local_pref;
570
  o = y ? y->u.data : old_bgp->cf->default_local_pref;
571
  if (n > o)
572
    return 1;
573
  if (n < o)
574
    return 0;
575

    
576
  /* Use AS path lengths */
577
  if (new_bgp->cf->compare_path_lengths || old_bgp->cf->compare_path_lengths)
578
    {
579
      x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
580
      y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
581
      n = x ? as_path_getlen(x->u.ptr) : 100000;
582
      o = y ? as_path_getlen(y->u.ptr) : 100000;
583
      if (n < o)
584
        return 1;
585
      if (n > o)
586
        return 0;
587
    }
588

    
589
  /* Use origins */
590
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
591
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
592
  n = x ? x->u.data : 2;
593
  o = y ? y->u.data : 2;
594
  if (n < o)
595
    return 1;
596
  if (n > o)
597
    return 0;
598

    
599
  /* Compare MED's */
600
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
601
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
602
  n = x ? x->u.data : new_bgp->cf->default_med;
603
  o = y ? y->u.data : old_bgp->cf->default_med;
604
  if (n < o)
605
    return 1;
606
  if (n > o)
607
    return 0;
608

    
609
  /* A tie breaking procedure according to RFC 1771, section 9.1.2.1 */
610
  /* We don't have interior distances */
611
  /* We prefer external peers */
612
  if (new_bgp->is_internal > old_bgp->is_internal)
613
    return 0;
614
  if (new_bgp->is_internal < old_bgp->is_internal)
615
    return 1;
616
  /* Finally we compare BGP identifiers */
617
  return (new_bgp->remote_id < old_bgp->remote_id);
618
}
619

    
620
static int
621
bgp_path_loopy(struct bgp_proto *p, eattr *a)
622
{
623
  byte *path = a->u.ptr->data;
624
  int len = a->u.ptr->length;
625
  int i, n;
626

    
627
  while (len > 0)
628
    {
629
      n = path[1];
630
      len -= 2 - 2*n;
631
      path += 2;
632
      for(i=0; i<n; i++)
633
        {
634
          if (get_u16(path) == p->local_as)
635
            return 1;
636
          path += 2;
637
        }
638
    }
639
  return 0;
640
}
641

    
642
struct rta *
643
bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct linpool *pool)
644
{
645
  struct bgp_proto *bgp = conn->bgp;
646
  rta *a = lp_alloc(pool, sizeof(struct rta));
647
  unsigned int flags, code, l, i, type;
648
  int errcode;
649
  byte *z, *attr_start;
650
  byte seen[256/8];
651
  eattr *e;
652
  ea_list *ea;
653
  struct adata *ad;
654
  neighbor *neigh;
655
  ip_addr nexthop;
656

    
657
  a->proto = &bgp->p;
658
  a->source = RTS_BGP;
659
  a->scope = SCOPE_UNIVERSE;
660
  a->cast = RTC_UNICAST;
661
  a->dest = RTD_ROUTER;
662
  a->flags = 0;
663
  a->aflags = 0;
664
  a->from = bgp->cf->remote_ip;
665
  a->eattrs = NULL;
666

    
667
  /* Parse the attributes */
668
  bzero(seen, sizeof(seen));
669
  DBG("BGP: Parsing attributes\n");
670
  while (len)
671
    {
672
      if (len < 2)
673
        goto malformed;
674
      attr_start = attr;
675
      flags = *attr++;
676
      code = *attr++;
677
      len -= 2;
678
      if (flags & BAF_EXT_LEN)
679
        {
680
          if (len < 2)
681
            goto malformed;
682
          l = get_u16(attr);
683
          attr += 2;
684
          len -= 2;
685
        }
686
      else
687
        {
688
          if (len < 1)
689
            goto malformed;
690
          l = *attr++;
691
          len--;
692
        }
693
      if (l > len)
694
        goto malformed;
695
      len -= l;
696
      z = attr;
697
      attr += l;
698
      DBG("Attr %02x %02x %d\n", code, flags, l);
699
      if (seen[code/8] & (1 << (code%8)))
700
        goto malformed;
701
      if (code && code < ARRAY_SIZE(bgp_attr_table))
702
        {
703
          struct attr_desc *desc = &bgp_attr_table[code];
704
          if (desc->expected_length >= 0 && desc->expected_length != (int) l)
705
            { errcode = 5; goto err; }
706
          if ((desc->expected_flags ^ flags) & (BAF_OPTIONAL | BAF_TRANSITIVE))
707
            { errcode = 4; goto err; }
708
          if (!desc->allow_in_ebgp && !bgp->is_internal)
709
            continue;
710
          if (desc->validate)
711
            {
712
              errcode = desc->validate(bgp, z, l);
713
              if (errcode > 0)
714
                goto err;
715
              if (errcode < 0)
716
                continue;
717
            }
718
          type = desc->type;
719
        }
720
      else                                /* Unknown attribute */
721
        {
722
          if (!(flags & BAF_OPTIONAL))
723
            { errcode = 2; goto err; }
724
          type = EAF_TYPE_OPAQUE;
725
        }
726
      seen[code/8] |= (1 << (code%8));
727
      ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
728
      ea->next = a->eattrs;
729
      a->eattrs = ea;
730
      ea->flags = 0;
731
      ea->count = 1;
732
      ea->attrs[0].id = EA_CODE(EAP_BGP, code);
733
      ea->attrs[0].flags = flags;
734
      ea->attrs[0].type = type;
735
      if (type & EAF_EMBEDDED)
736
        ad = NULL;
737
      else
738
        {
739
          ad = lp_alloc(pool, sizeof(struct adata) + l);
740
          ea->attrs[0].u.ptr = ad;
741
          ad->length = l;
742
          memcpy(ad->data, z, l);
743
        }
744
      switch (type)
745
        {
746
        case EAF_TYPE_ROUTER_ID:
747
        case EAF_TYPE_INT:
748
          if (l == 1)
749
            ea->attrs[0].u.data = *z;
750
          else
751
            ea->attrs[0].u.data = get_u32(z);
752
          break;
753
        case EAF_TYPE_IP_ADDRESS:
754
          ipa_ntoh(*(ip_addr *)ad->data);
755
          break;
756
        case EAF_TYPE_INT_SET:
757
          {
758
            u32 *z = (u32 *) ad->data;
759
            for(i=0; i<ad->length/4; i++)
760
              z[i] = ntohl(z[i]);
761
            break;
762
          }
763
        }
764
    }
765

    
766
  /* Check if all mandatory attributes are present */
767
  for(i=0; i < sizeof(bgp_mandatory_attrs)/sizeof(bgp_mandatory_attrs[0]); i++)
768
    {
769
      code = bgp_mandatory_attrs[i];
770
      if (!(seen[code/8] & (1 << (code%8))))
771
        {
772
          bgp_error(conn, 3, 3, code, 1);
773
          return NULL;
774
        }
775
    }
776

    
777
  /* If the AS path attribute contains our AS, reject the routes */
778
  e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
779
  ASSERT(e);
780
  if (bgp_path_loopy(bgp, e))
781
    {
782
      DBG("BGP: Path loop!\n");
783
      return NULL;
784
    }
785

    
786
  /* Fill in the remaining rta fields */
787
  e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP));
788
  ASSERT(e);
789
  nexthop = *(ip_addr *) e->u.ptr->data;
790
  if (ipa_equal(nexthop, bgp->local_addr))
791
    {
792
      DBG("BGP: Loop!\n");
793
      return NULL;
794
    }
795
  neigh = neigh_find(&bgp->p, &nexthop, 0) ? : bgp->neigh;
796
  a->gw = neigh->addr;
797
  a->iface = neigh->iface;
798
  return rta_lookup(a);
799

    
800
malformed:
801
  bgp_error(conn, 3, 1, len, 0);
802
  return NULL;
803

    
804
err:
805
  bgp_error(conn, 3, errcode, code, 0);        /* FIXME: Return attribute data! */
806
  return NULL;
807
}
808

    
809
int
810
bgp_get_attr(eattr *a, byte *buf)
811
{
812
  unsigned int i = EA_ID(a->id);
813
  struct attr_desc *d;
814

    
815
  if (i && i < sizeof(bgp_attr_table)/sizeof(bgp_attr_table[0]))
816
    {
817
      d = &bgp_attr_table[i];
818
      buf += bsprintf(buf, "%s", d->name);
819
      if (d->format)
820
        {
821
          *buf++ = ':';
822
          *buf++ = ' ';
823
          d->format(a, buf);
824
          return GA_FULL;
825
        }
826
      return GA_NAME;
827
    }
828
  bsprintf(buf, "%02x%s", i, (a->flags & BAF_TRANSITIVE) ? "[t]" : "");
829
  return GA_NAME;
830
}
831

    
832
void
833
bgp_attr_init(struct bgp_proto *p)
834
{
835
  p->hash_size = 256;
836
  p->hash_limit = p->hash_size * 4;
837
  p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
838
  init_list(&p->bucket_queue);
839
  p->withdraw_bucket = NULL;
840
  fib_init(&p->prefix_fib, p->p.pool, sizeof(struct bgp_prefix), 0, bgp_init_prefix);
841
}