Statistics
| Branch: | Revision:

iof-bird-daemon / proto / bgp / attrs.c @ 54e55169

History | View | Annotate | Download (23.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
#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, byte *a, 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, 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, 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, byte *a, int len)
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, byte *a, int len)
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 = 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 += 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 += 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 *t, *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, 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_EXT) ? 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
    *(ip_addr *)z = p->local_addr;
580
  else
581
    *(ip_addr *)z = e->attrs->gw;
582

    
583
  bgp_set_attr(ea->attrs+3, pool, BA_LOCAL_PREF, 0);
584

    
585
  return 0;                                /* Leave decision to the filters */
586
}
587

    
588
static ea_list *
589
bgp_path_prepend(struct linpool *pool, eattr *a, ea_list *old, int as)
590
{
591
  struct ea_list *e = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
592
  struct adata *olda = a->u.ptr;
593

    
594
  e->next = old;
595
  e->flags = EALF_SORTED;
596
  e->count = 1;
597
  e->attrs[0].id = EA_CODE(EAP_BGP, BA_AS_PATH);
598
  e->attrs[0].flags = BAF_TRANSITIVE;
599
  e->attrs[0].type = EAF_TYPE_AS_PATH;
600
  e->attrs[0].u.ptr = as_path_prepend(pool, olda, as);
601
  return e;
602
}
603

    
604
static int
605
bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
606
{
607
  eattr *a;
608

    
609
  if (!p->is_internal && (a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH))))
610
    *attrs = bgp_path_prepend(pool, a, *attrs, p->local_as);
611

    
612
  a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP));
613
  if (a && (p->is_internal || (!p->is_internal && e->attrs->iface == p->neigh->iface)))
614
    {
615
      /* Leave the original next hop attribute, will check later where does it point */
616
    }
617
  else
618
    {
619
      /* Need to create new one */
620
      *(ip_addr *) bgp_attach_attr(attrs, pool, BA_NEXT_HOP, sizeof(ip_addr)) = p->local_addr;
621
    }
622

    
623
  return 0;                                /* Leave decision to the filters */
624
}
625

    
626
int
627
bgp_import_control(struct proto *P, rte **new, ea_list **attrs, struct linpool *pool)
628
{
629
  rte *e = *new;
630
  struct bgp_proto *p = (struct bgp_proto *) P;
631
  struct bgp_proto *new_bgp = (e->attrs->proto->proto == &proto_bgp) ? (struct bgp_proto *) e->attrs->proto : NULL;
632

    
633
  if (p == new_bgp)                        /* Poison reverse updates */
634
    return -1;
635
  if (new_bgp)
636
    {
637
      if (p->local_as == new_bgp->local_as && p->is_internal && new_bgp->is_internal)
638
        return -1;                        /* Don't redistribute internal routes with IBGP */
639
      return bgp_update_attrs(p, e, attrs, pool);
640
    }
641
  else
642
    return bgp_create_attrs(p, e, attrs, pool);
643
}
644

    
645
int
646
bgp_rte_better(rte *new, rte *old)
647
{
648
  struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->proto;
649
  struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->proto;
650
  eattr *x, *y;
651
  u32 n, o;
652

    
653
  /* Start with local preferences */
654
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
655
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
656
  n = x ? x->u.data : new_bgp->cf->default_local_pref;
657
  o = y ? y->u.data : old_bgp->cf->default_local_pref;
658
  if (n > o)
659
    return 1;
660
  if (n < o)
661
    return 0;
662

    
663
  /* Use AS path lengths */
664
  if (new_bgp->cf->compare_path_lengths || old_bgp->cf->compare_path_lengths)
665
    {
666
      x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
667
      y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
668
      n = x ? as_path_getlen(x->u.ptr) : 100000;
669
      o = y ? as_path_getlen(y->u.ptr) : 100000;
670
      if (n < o)
671
        return 1;
672
      if (n > o)
673
        return 0;
674
    }
675

    
676
  /* Use origins */
677
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
678
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
679
  n = x ? x->u.data : ORIGIN_INCOMPLETE;
680
  o = y ? y->u.data : ORIGIN_INCOMPLETE;
681
  if (n < o)
682
    return 1;
683
  if (n > o)
684
    return 0;
685

    
686
  /* Compare MED's */
687
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
688
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
689
  n = x ? x->u.data : new_bgp->cf->default_med;
690
  o = y ? y->u.data : old_bgp->cf->default_med;
691
  if (n < o)
692
    return 1;
693
  if (n > o)
694
    return 0;
695

    
696
  /* A tie breaking procedure according to RFC 1771, section 9.1.2.1 */
697
  /* We don't have interior distances */
698
  /* We prefer external peers */
699
  if (new_bgp->is_internal > old_bgp->is_internal)
700
    return 0;
701
  if (new_bgp->is_internal < old_bgp->is_internal)
702
    return 1;
703
  /* Finally we compare BGP identifiers */
704
  return (new_bgp->remote_id < old_bgp->remote_id);
705
}
706

    
707
static int
708
bgp_path_loopy(struct bgp_proto *p, eattr *a)
709
{
710
  byte *path = a->u.ptr->data;
711
  int len = a->u.ptr->length;
712
  int i, n;
713

    
714
  while (len > 0)
715
    {
716
      n = path[1];
717
      len -= 2 + 2*n;
718
      path += 2;
719
      for(i=0; i<n; i++)
720
        {
721
          if (get_u16(path) == p->local_as)
722
            return 1;
723
          path += 2;
724
        }
725
    }
726
  return 0;
727
}
728

    
729
/**
730
 * bgp_decode_attrs - check and decode BGP attributes
731
 * @conn: connection
732
 * @attr: start of attribute block
733
 * @len: length of attribute block
734
 * @pool: linear pool to make all the allocations in
735
 * @mandatory: 1 iff presence of mandatory attributes has to be checked
736
 *
737
 * This function takes a BGP attribute block (a part of an Update message), checks
738
 * its consistency and converts it to a list of BIRD route attributes represented
739
 * by a &rta.
740
 */
741
struct rta *
742
bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct linpool *pool, int mandatory)
743
{
744
  struct bgp_proto *bgp = conn->bgp;
745
  rta *a = lp_alloc(pool, sizeof(struct rta));
746
  unsigned int flags, code, l, i, type;
747
  int errcode;
748
  byte *z, *attr_start;
749
  byte seen[256/8];
750
  eattr *e;
751
  ea_list *ea;
752
  struct adata *ad;
753

    
754
  a->proto = &bgp->p;
755
  a->source = RTS_BGP;
756
  a->scope = SCOPE_UNIVERSE;
757
  a->cast = RTC_UNICAST;
758
  a->dest = RTD_ROUTER;
759
  a->flags = 0;
760
  a->aflags = 0;
761
  a->from = bgp->cf->remote_ip;
762
  a->eattrs = NULL;
763

    
764
  /* Parse the attributes */
765
  bzero(seen, sizeof(seen));
766
  DBG("BGP: Parsing attributes\n");
767
  while (len)
768
    {
769
      if (len < 2)
770
        goto malformed;
771
      attr_start = attr;
772
      flags = *attr++;
773
      code = *attr++;
774
      len -= 2;
775
      if (flags & BAF_EXT_LEN)
776
        {
777
          if (len < 2)
778
            goto malformed;
779
          l = get_u16(attr);
780
          attr += 2;
781
          len -= 2;
782
        }
783
      else
784
        {
785
          if (len < 1)
786
            goto malformed;
787
          l = *attr++;
788
          len--;
789
        }
790
      if (l > len)
791
        goto malformed;
792
      len -= l;
793
      z = attr;
794
      attr += l;
795
      DBG("Attr %02x %02x %d\n", code, flags, l);
796
      if (seen[code/8] & (1 << (code%8)))
797
        goto malformed;
798
      if (ATTR_KNOWN(code))
799
        {
800
          struct attr_desc *desc = &bgp_attr_table[code];
801
          if (desc->expected_length >= 0 && desc->expected_length != (int) l)
802
            { errcode = 5; goto err; }
803
          if ((desc->expected_flags ^ flags) & (BAF_OPTIONAL | BAF_TRANSITIVE))
804
            { errcode = 4; goto err; }
805
          if (!desc->allow_in_ebgp && !bgp->is_internal)
806
            continue;
807
          if (desc->validate)
808
            {
809
              errcode = desc->validate(bgp, z, l);
810
              if (errcode > 0)
811
                goto err;
812
              if (errcode < 0)
813
                continue;
814
            }
815
          type = desc->type;
816
        }
817
      else                                /* Unknown attribute */
818
        {
819
          if (!(flags & BAF_OPTIONAL))
820
            { errcode = 2; goto err; }
821
          type = EAF_TYPE_OPAQUE;
822
        }
823
      seen[code/8] |= (1 << (code%8));
824
      ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
825
      ea->next = a->eattrs;
826
      a->eattrs = ea;
827
      ea->flags = 0;
828
      ea->count = 1;
829
      ea->attrs[0].id = EA_CODE(EAP_BGP, code);
830
      ea->attrs[0].flags = flags;
831
      ea->attrs[0].type = type;
832
      if (type & EAF_EMBEDDED)
833
        ad = NULL;
834
      else
835
        {
836
          ad = lp_alloc(pool, sizeof(struct adata) + l);
837
          ea->attrs[0].u.ptr = ad;
838
          ad->length = l;
839
          memcpy(ad->data, z, l);
840
        }
841
      switch (type)
842
        {
843
        case EAF_TYPE_ROUTER_ID:
844
        case EAF_TYPE_INT:
845
          if (l == 1)
846
            ea->attrs[0].u.data = *z;
847
          else
848
            ea->attrs[0].u.data = get_u32(z);
849
          break;
850
        case EAF_TYPE_IP_ADDRESS:
851
          ipa_ntoh(*(ip_addr *)ad->data);
852
          break;
853
        case EAF_TYPE_INT_SET:
854
          {
855
            u32 *z = (u32 *) ad->data;
856
            for(i=0; i<ad->length/4; i++)
857
              z[i] = ntohl(z[i]);
858
            break;
859
          }
860
        }
861
    }
862

    
863
#ifdef IPV6
864
  if (seen[BA_MP_REACH_NLRI / 8] & (1 << (BA_MP_REACH_NLRI % 8)))
865
    mandatory = 1;
866
#endif
867

    
868
  /* Check if all mandatory attributes are present */
869
  if (mandatory)
870
    {
871
      for(i=0; i < ARRAY_SIZE(bgp_mandatory_attrs); i++)
872
        {
873
          code = bgp_mandatory_attrs[i];
874
          if (!(seen[code/8] & (1 << (code%8))))
875
            {
876
              bgp_error(conn, 3, 3, &bgp_mandatory_attrs[i], 1);
877
              return NULL;
878
            }
879
        }
880
    }
881

    
882
  /* If the AS path attribute contains our AS, reject the routes */
883
  e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
884
  if (e && bgp_path_loopy(bgp, e))
885
    {
886
      DBG("BGP: Path loop!\n");
887
      return NULL;
888
    }
889

    
890
  /* If there's no local preference, define one */
891
  if (!(seen[0] && (1 << BA_LOCAL_PREF)))
892
    bgp_attach_attr(&a->eattrs, pool, BA_LOCAL_PREF, 0);
893
  return a;
894

    
895
malformed:
896
  bgp_error(conn, 3, 1, NULL, 0);
897
  return NULL;
898

    
899
err:
900
  bgp_error(conn, 3, errcode, attr_start, z+l-attr_start);
901
  return NULL;
902
}
903

    
904
int
905
bgp_get_attr(eattr *a, byte *buf)
906
{
907
  unsigned int i = EA_ID(a->id);
908
  struct attr_desc *d;
909

    
910
  if (ATTR_KNOWN(i))
911
    {
912
      d = &bgp_attr_table[i];
913
      buf += bsprintf(buf, "%s", d->name);
914
      if (d->format)
915
        {
916
          *buf++ = ':';
917
          *buf++ = ' ';
918
          d->format(a, buf);
919
          return GA_FULL;
920
        }
921
      return GA_NAME;
922
    }
923
  bsprintf(buf, "%02x%s", i, (a->flags & BAF_TRANSITIVE) ? " [t]" : "");
924
  return GA_NAME;
925
}
926

    
927
void
928
bgp_attr_init(struct bgp_proto *p)
929
{
930
  p->hash_size = 256;
931
  p->hash_limit = p->hash_size * 4;
932
  p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
933
  init_list(&p->bucket_queue);
934
  p->withdraw_bucket = NULL;
935
  fib_init(&p->prefix_fib, p->p.pool, sizeof(struct bgp_prefix), 0, bgp_init_prefix);
936
}
937

    
938
void
939
bgp_get_route_info(rte *e, byte *buf, ea_list *attrs)
940
{
941
  eattr *p = ea_find(attrs, EA_CODE(EAP_BGP, BA_AS_PATH));
942
  eattr *o = ea_find(attrs, EA_CODE(EAP_BGP, BA_ORIGIN));
943
  int origas;
944

    
945
  buf += bsprintf(buf, " (%d) [", e->pref);
946
  if (p && (origas = as_path_get_first(p->u.ptr)) >= 0)
947
    buf += bsprintf(buf, "AS%d", origas);
948
  if (o)
949
    buf += bsprintf(buf, "%c", "ie?"[o->u.data]);
950
  strcpy(buf, "]");
951
}