Statistics
| Branch: | Revision:

iof-bird-daemon / proto / bgp / attrs.c @ 11cb6202

History | View | Annotate | Download (30.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
#undef LOCAL_DEBUG
10

    
11
#include <stdlib.h>
12

    
13
#include "nest/bird.h"
14
#include "nest/iface.h"
15
#include "nest/protocol.h"
16
#include "nest/route.h"
17
#include "nest/attrs.h"
18
#include "conf/conf.h"
19
#include "lib/resource.h"
20
#include "lib/string.h"
21
#include "lib/unaligned.h"
22

    
23
#include "bgp.h"
24

    
25
static byte bgp_mandatory_attrs[] = { BA_ORIGIN, BA_AS_PATH
26
#ifndef IPV6
27
,BA_NEXT_HOP
28
#endif
29
};
30

    
31
struct attr_desc {
32
  char *name;
33
  int expected_length;
34
  int expected_flags;
35
  int type;
36
  int allow_in_ebgp;
37
  int (*validate)(struct bgp_proto *p, byte *attr, int len);
38
  void (*format)(eattr *ea, byte *buf);
39
};
40

    
41
static int
42
bgp_check_origin(struct bgp_proto *p UNUSED, byte *a UNUSED, int len)
43
{
44
  if (len > 2)
45
    return 6;
46
  return 0;
47
}
48

    
49
static void
50
bgp_format_origin(eattr *a, byte *buf)
51
{
52
  static char *bgp_origin_names[] = { "IGP", "EGP", "Incomplete" };
53

    
54
  bsprintf(buf, bgp_origin_names[a->u.data]);
55
}
56

    
57
static int
58
bgp_check_path(byte *a, int len, int bs, int errcode)
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
          bs * a[1] + 2 > len)
66
        return errcode;
67
      len -= bs * a[1] + 2;
68
      a += bs * a[1] + 2;
69
    }
70
  return 0;
71
}
72

    
73
static int
74
bgp_check_as_path(struct bgp_proto *p, byte *a, int len)
75
{
76
  return bgp_check_path(a, len, (bgp_as4_support && p->as4_support) ? 4 : 2, 11);
77
}
78

    
79
static int
80
bgp_check_as4_path(struct bgp_proto *p, byte *a, int len)
81
{
82
  if (bgp_as4_support && (! p->as4_support))
83
    return bgp_check_path(a, len, 4, 9);
84
  else 
85
    return 0;
86
}
87

    
88

    
89
static int
90
bgp_check_next_hop(struct bgp_proto *p UNUSED, byte *a, int len)
91
{
92
#ifdef IPV6
93
  return -1;
94
#else
95
  ip_addr addr;
96

    
97
  memcpy(&addr, a, len);
98
  ipa_ntoh(addr);
99
  if (ipa_classify(addr) & IADDR_HOST)
100
    return 0;
101
  else
102
    return 8;
103
#endif
104
}
105

    
106
static int
107
bgp_check_aggregator(struct bgp_proto *p UNUSED, UNUSED byte *a, int len)
108
{
109
  int exp_len = (bgp_as4_support && p->as4_support) ? 8 : 6;
110
  
111
  return (len == exp_len) ? 0 : 5;
112
}
113

    
114
static int
115
bgp_check_reach_nlri(struct bgp_proto *p UNUSED, byte *a UNUSED, int len UNUSED)
116
{
117
#ifdef IPV6
118
  p->mp_reach_start = a;
119
  p->mp_reach_len = len;
120
#endif
121
  return -1;
122
}
123

    
124
static int
125
bgp_check_unreach_nlri(struct bgp_proto *p UNUSED, byte *a UNUSED, int len UNUSED)
126
{
127
#ifdef IPV6
128
  p->mp_unreach_start = a;
129
  p->mp_unreach_len = len;
130
#endif
131
  return -1;
132
}
133

    
134
static struct attr_desc bgp_attr_table[] = {
135
  { NULL, -1, 0, 0, 0,                                                                /* Undefined */
136
    NULL, NULL },
137
  { "origin", 1, BAF_TRANSITIVE, EAF_TYPE_INT, 1,                                /* BA_ORIGIN */
138
    bgp_check_origin, bgp_format_origin },
139
  { "as_path", -1, BAF_TRANSITIVE, EAF_TYPE_AS_PATH, 1,                                /* BA_AS_PATH */
140
    bgp_check_as_path, NULL },
141
  { "next_hop", 4, BAF_TRANSITIVE, EAF_TYPE_IP_ADDRESS, 1,                        /* BA_NEXT_HOP */
142
    bgp_check_next_hop, NULL },
143
  { "med", 4, BAF_OPTIONAL, EAF_TYPE_INT, 0,                                        /* BA_MULTI_EXIT_DISC */
144
    NULL, NULL },
145
  { "local_pref", 4, BAF_TRANSITIVE, EAF_TYPE_INT, 0,                                /* BA_LOCAL_PREF */
146
    NULL, NULL },
147
  { "atomic_aggr", 0, BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1,                        /* BA_ATOMIC_AGGR */
148
    NULL, NULL },
149
  { "aggregator", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1,        /* BA_AGGREGATOR */
150
    bgp_check_aggregator, NULL },
151
  { "community", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_INT_SET, 1,        /* BA_COMMUNITY */
152
    NULL, NULL },
153
  { NULL, },                                                                        /* BA_ORIGINATOR_ID */
154
  { NULL, },                                                                        /* BA_CLUSTER_LIST */
155
  { NULL, },                                                                        /* BA_DPA */
156
  { NULL, },                                                                        /* BA_ADVERTISER */
157
  { NULL, },                                                                        /* BA_RCID_PATH */
158
  { "mp_reach_nlri", -1, BAF_OPTIONAL, EAF_TYPE_OPAQUE, 1,                        /* BA_MP_REACH_NLRI */
159
    bgp_check_reach_nlri, NULL },
160
  { "mp_unreach_nlri", -1, BAF_OPTIONAL, EAF_TYPE_OPAQUE, 1,                        /* BA_MP_UNREACH_NLRI */
161
    bgp_check_unreach_nlri, NULL },
162
  { NULL, },                                                                        /* BA_EXTENDED_COMM */
163
  { "as4_path", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1,                /* BA_AS4_PATH */
164
    bgp_check_as4_path, NULL },
165
  { "as4_aggregator", 8, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1,        /* BA_AS4_PATH */
166
    NULL, NULL }
167
};
168

    
169
/* BA_AS4_PATH is type EAF_TYPE_OPAQUE and not type EAF_TYPE_AS_PATH because
170
 * EAF_TYPE_AS_PATH is supposed to have different format (2 or 4 B for each ASN)
171
 * depending on bgp_as4_support variable.
172
 */
173

    
174
#define ATTR_KNOWN(code) ((code) < ARRAY_SIZE(bgp_attr_table) && bgp_attr_table[code].name)
175

    
176
static byte *
177
bgp_set_attr(eattr *e, struct linpool *pool, unsigned attr, unsigned val)
178
{
179
  ASSERT(ATTR_KNOWN(attr));
180
  e->id = EA_CODE(EAP_BGP, attr);
181
  e->type = bgp_attr_table[attr].type;
182
  e->flags = bgp_attr_table[attr].expected_flags;
183
  if (e->type & EAF_EMBEDDED)
184
    {
185
      e->u.data = val;
186
      return NULL;
187
    }
188
  else
189
    {
190
      e->u.ptr = lp_alloc(pool, sizeof(struct adata) + val);
191
      e->u.ptr->length = val;
192
      return e->u.ptr->data;
193
    }
194
}
195

    
196
byte *
197
bgp_attach_attr(ea_list **to, struct linpool *pool, unsigned attr, unsigned val)
198
{
199
  ea_list *a = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
200
  a->next = *to;
201
  *to = a;
202
  a->flags = EALF_SORTED;
203
  a->count = 1;
204
  return bgp_set_attr(a->attrs, pool, attr, val);
205
}
206

    
207
static int
208
bgp_encode_attr_hdr(byte *dst, unsigned int flags, unsigned code, int len)
209
{
210
  int wlen;
211

    
212
  DBG("\tAttribute %02x (%d bytes, flags %02x)\n", code, len, flags);
213

    
214
  if (len < 256)
215
    {
216
      *dst++ = flags;
217
      *dst++ = code;
218
      *dst++ = len;
219
      wlen = 3;
220
    }
221
  else
222
    {
223
      *dst++ = flags | BAF_EXT_LEN;
224
      *dst++ = code;
225
      put_u16(dst, len);
226
      wlen = 4;
227
    }
228

    
229
  return wlen;
230
}
231

    
232
static void
233
aggregator_convert_to_old(struct adata *aggr, byte *dst, int *new_used)
234
{
235
  byte *src = aggr->data;
236
  *new_used = 0;
237

    
238
  u32 as = get_u32(src);
239
  if (as > 0xFFFF) 
240
    {
241
      as = AS_TRANS;
242
      *new_used = 1;
243
    }
244
  put_u16(dst, as);
245

    
246
  /* Copy IPv4 address */
247
  memcpy(dst + 2, src + 4, 4);
248
}
249

    
250
static void
251
aggregator_convert_to_new(struct adata *aggr, byte *dst)
252
{
253
  byte *src = aggr->data;
254

    
255
  u32 as   = get_u16(src);
256
  put_u32(dst, as);
257

    
258
  /* Copy IPv4 address */
259
  memcpy(dst + 4, src + 2, 4);
260
}
261

    
262
static int
263
bgp_get_attr_len(eattr *a)
264
{
265
  int len;
266
  if (ATTR_KNOWN(EA_ID(a->id)))
267
    {
268
      int code = EA_ID(a->id);
269
      struct attr_desc *desc = &bgp_attr_table[code];
270
      len = desc->expected_length;
271
      if (len < 0)
272
        {
273
          ASSERT(!(a->type & EAF_EMBEDDED));
274
          len = a->u.ptr->length;
275
        }
276
    }
277
  else
278
    {
279
      ASSERT((a->type & EAF_TYPE_MASK) == EAF_TYPE_OPAQUE);
280
      len = a->u.ptr->length;
281
    }
282
  
283
  return len;
284
}
285

    
286
#define ADVANCE(w, r, l) do { r -= l; w += l; } while (0)
287

    
288
/**
289
 * bgp_encode_attrs - encode BGP attributes
290
 * @p: BGP instance
291
 * @w: buffer
292
 * @attrs: a list of extended attributes
293
 * @remains: remaining space in the buffer
294
 *
295
 * The bgp_encode_attrs() function takes a list of extended attributes
296
 * and converts it to its BGP representation (a part of an Update message).
297
 *
298
 * Result: Length of the attribute block generated.
299
 */
300
unsigned int
301
bgp_encode_attrs(struct bgp_proto *p, byte *w, ea_list *attrs, int remains)
302
{
303
  unsigned int i, code, flags;
304
  byte *start = w;
305
  int len, rv;
306

    
307
  for(i=0; i<attrs->count; i++)
308
    {
309
      eattr *a = &attrs->attrs[i];
310
      ASSERT(EA_PROTO(a->id) == EAP_BGP);
311
      code = EA_ID(a->id);
312
#ifdef IPV6
313
      /* When talking multiprotocol BGP, the NEXT_HOP attributes are used only temporarily. */
314
      if (code == BA_NEXT_HOP)
315
        continue;
316
#endif
317

    
318
      /* When AS4-aware BGP speaker is talking to non-AS4-aware BGP speaker,
319
       * we have to convert our 4B AS_PATH to 2B AS_PATH and send our AS_PATH 
320
       * as optional AS4_PATH attribute.
321
       */
322
      if ((code == BA_AS_PATH) && bgp_as4_support && (! p->as4_support))
323
        {
324
          len = a->u.ptr->length;
325

    
326
          if (remains < (len + 4))
327
            goto err_no_buffer;
328

    
329
          /* Using temporary buffer because don't know a length of created attr
330
           * and therefore a length of a header. Perhaps i should better always
331
           * use BAF_EXT_LEN. */
332
          
333
          byte buf[len];
334
          int new_used;
335
          int nl = as_path_convert_to_old(a->u.ptr, buf, &new_used);
336

    
337
          rv = bgp_encode_attr_hdr(w, BAF_TRANSITIVE, BA_AS_PATH, nl);
338
          ADVANCE(w, remains, rv);
339
          memcpy(w, buf, nl);
340
          ADVANCE(w, remains, nl);
341

    
342
          if (! new_used)
343
            continue;
344

    
345
          if (remains < (len + 4))
346
            goto err_no_buffer;
347

    
348
          /* We should discard AS_CONFED_SEQUENCE or AS_CONFED_SET path segments 
349
           * here but we don't support confederations and such paths we already
350
           * discarded in bgp_check_as_path().
351
           */
352

    
353
          rv = bgp_encode_attr_hdr(w, BAF_OPTIONAL | BAF_TRANSITIVE, BA_AS4_PATH, len);
354
          ADVANCE(w, remains, rv);
355
          memcpy(w, a->u.ptr->data, len);
356
          ADVANCE(w, remains, len);
357

    
358
          continue;
359
        }
360

    
361
      /* The same issue with AGGREGATOR attribute */
362
      if ((code == BA_AGGREGATOR) && bgp_as4_support && (! p->as4_support))
363
        {
364
          int new_used;
365

    
366
          len = 6;
367
          if (remains < (len + 3))
368
            goto err_no_buffer;
369

    
370
          rv = bgp_encode_attr_hdr(w, BAF_OPTIONAL | BAF_TRANSITIVE, BA_AGGREGATOR, len);
371
          ADVANCE(w, remains, rv);
372
          aggregator_convert_to_old(a->u.ptr, w, &new_used);
373
          ADVANCE(w, remains, len);
374

    
375
          if (! new_used)
376
            continue;
377

    
378
          len = 8;
379
          if (remains < (len + 3))
380
            goto err_no_buffer;
381

    
382
          rv = bgp_encode_attr_hdr(w, BAF_OPTIONAL | BAF_TRANSITIVE, BA_AS4_AGGREGATOR, len);
383
          ADVANCE(w, remains, rv);
384
          memcpy(w, a->u.ptr->data, len);
385
          ADVANCE(w, remains, len);
386

    
387
          continue;
388
        }
389

    
390
      /* Standard path continues here ... */
391

    
392
      flags = a->flags & (BAF_OPTIONAL | BAF_TRANSITIVE | BAF_PARTIAL);
393
      len = bgp_get_attr_len(a);
394

    
395
      if (remains < len + 4)
396
        goto err_no_buffer;
397

    
398
      rv = bgp_encode_attr_hdr(w, flags, code, len);
399
      ADVANCE(w, remains, rv);
400

    
401
      switch (a->type & EAF_TYPE_MASK)
402
        {
403
        case EAF_TYPE_INT:
404
        case EAF_TYPE_ROUTER_ID:
405
          if (len == 4)
406
            put_u32(w, a->u.data);
407
          else
408
            *w = a->u.data;
409
          break;
410
        case EAF_TYPE_IP_ADDRESS:
411
          {
412
            ip_addr ip = *(ip_addr *)a->u.ptr->data;
413
            ipa_hton(ip);
414
            memcpy(w, &ip, len);
415
            break;
416
          }
417
        case EAF_TYPE_INT_SET:
418
          {
419
            u32 *z = (u32 *)a->u.ptr->data;
420
            int i;
421
            for(i=0; i<len; i+=4)
422
              put_u32(w+i, *z++);
423
            break;
424
          }
425
        case EAF_TYPE_OPAQUE:
426
        case EAF_TYPE_AS_PATH:
427
          memcpy(w, a->u.ptr->data, len);
428
          break;
429
        default:
430
          bug("bgp_encode_attrs: unknown attribute type %02x", a->type);
431
        }
432
      ADVANCE(w, remains, len);
433
    }
434
  return w - start;
435

    
436
 err_no_buffer:
437
  log(L_ERR "BGP: attribute list too long, ignoring the remaining attributes");
438
  return w - start;
439
}
440

    
441
static void
442
bgp_init_prefix(struct fib_node *N)
443
{
444
  struct bgp_prefix *p = (struct bgp_prefix *) N;
445
  p->bucket_node.next = NULL;
446
}
447

    
448
static int
449
bgp_compare_u32(const u32 *x, const u32 *y)
450
{
451
  return (*x < *y) ? -1 : (*x > *y) ? 1 : 0;
452
}
453

    
454
static void
455
bgp_normalize_set(u32 *dest, u32 *src, unsigned cnt)
456
{
457
  memcpy(dest, src, sizeof(u32) * cnt);
458
  qsort(dest, cnt, sizeof(u32), (int(*)(const void *, const void *)) bgp_compare_u32);
459
}
460

    
461
static void
462
bgp_rehash_buckets(struct bgp_proto *p)
463
{
464
  struct bgp_bucket **old = p->bucket_hash;
465
  struct bgp_bucket **new;
466
  unsigned oldn = p->hash_size;
467
  unsigned i, e, mask;
468
  struct bgp_bucket *b;
469

    
470
  p->hash_size = p->hash_limit;
471
  DBG("BGP: Rehashing bucket table from %d to %d\n", oldn, p->hash_size);
472
  p->hash_limit *= 4;
473
  if (p->hash_limit >= 65536)
474
    p->hash_limit = ~0;
475
  new = p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
476
  mask = p->hash_size - 1;
477
  for (i=0; i<oldn; i++)
478
    while (b = old[i])
479
      {
480
        old[i] = b->hash_next;
481
        e = b->hash & mask;
482
        b->hash_next = new[e];
483
        if (b->hash_next)
484
          b->hash_next->hash_prev = b;
485
        b->hash_prev = NULL;
486
        new[e] = b;
487
      }
488
  mb_free(old);
489
}
490

    
491
static struct bgp_bucket *
492
bgp_new_bucket(struct bgp_proto *p, ea_list *new, unsigned hash)
493
{
494
  struct bgp_bucket *b;
495
  unsigned ea_size = sizeof(ea_list) + new->count * sizeof(eattr);
496
  unsigned ea_size_aligned = BIRD_ALIGN(ea_size, CPU_STRUCT_ALIGN);
497
  unsigned size = sizeof(struct bgp_bucket) + ea_size;
498
  unsigned i;
499
  byte *dest;
500
  unsigned index = hash & (p->hash_size - 1);
501

    
502
  /* Gather total size of non-inline attributes */
503
  for (i=0; i<new->count; i++)
504
    {
505
      eattr *a = &new->attrs[i];
506
      if (!(a->type & EAF_EMBEDDED))
507
        size += BIRD_ALIGN(sizeof(struct adata) + a->u.ptr->length, CPU_STRUCT_ALIGN);
508
    }
509

    
510
  /* Create the bucket and hash it */
511
  b = mb_alloc(p->p.pool, size);
512
  b->hash_next = p->bucket_hash[index];
513
  if (b->hash_next)
514
    b->hash_next->hash_prev = b;
515
  p->bucket_hash[index] = b;
516
  b->hash_prev = NULL;
517
  b->hash = hash;
518
  add_tail(&p->bucket_queue, &b->send_node);
519
  init_list(&b->prefixes);
520
  memcpy(b->eattrs, new, ea_size);
521
  dest = ((byte *)b->eattrs) + ea_size_aligned;
522

    
523
  /* Copy values of non-inline attributes */
524
  for (i=0; i<new->count; i++)
525
    {
526
      eattr *a = &b->eattrs->attrs[i];
527
      if (!(a->type & EAF_EMBEDDED))
528
        {
529
          struct adata *oa = a->u.ptr;
530
          struct adata *na = (struct adata *) dest;
531
          memcpy(na, oa, sizeof(struct adata) + oa->length);
532
          a->u.ptr = na;
533
          dest += BIRD_ALIGN(sizeof(struct adata) + na->length, CPU_STRUCT_ALIGN);
534
        }
535
    }
536

    
537
  /* If needed, rehash */
538
  p->hash_count++;
539
  if (p->hash_count > p->hash_limit)
540
    bgp_rehash_buckets(p);
541

    
542
  return b;
543
}
544

    
545
static int
546
bgp_export_check(struct bgp_proto *p, ea_list *new)
547
{
548
  eattr *a;
549
  struct adata *d;
550

    
551
  /* Check if next hop is valid */
552
  a = ea_find(new, EA_CODE(EAP_BGP, BA_NEXT_HOP));
553
  if (!a || ipa_equal(p->next_hop, *(ip_addr *)a->u.ptr))
554
    {
555
      DBG("\tInvalid NEXT_HOP\n");
556
      return 0;
557
    }
558

    
559
  /* Check if we aren't forbidden to export the route by communities */
560
  a = ea_find(new, EA_CODE(EAP_BGP, BA_COMMUNITY));
561
  if (a)
562
    {
563
      d = a->u.ptr;
564
      if (int_set_contains(d, BGP_COMM_NO_ADVERTISE))
565
        {
566
          DBG("\tNO_ADVERTISE\n");
567
          return 0;
568
        }
569
      if (!p->is_internal &&
570
          (int_set_contains(d, BGP_COMM_NO_EXPORT) ||
571
           int_set_contains(d, BGP_COMM_NO_EXPORT_SUBCONFED)))
572
        {
573
          DBG("\tNO_EXPORT\n");
574
          return 0;
575
        }
576
    }
577

    
578
  return 1;
579
}
580

    
581
static struct bgp_bucket *
582
bgp_get_bucket(struct bgp_proto *p, ea_list *attrs, int originate)
583
{
584
  ea_list *new;
585
  unsigned i, cnt, hash, code;
586
  eattr *a, *d;
587
  u32 seen = 0;
588
  struct bgp_bucket *b;
589

    
590
  /* Merge the attribute list */
591
  new = alloca(ea_scan(attrs));
592
  ea_merge(attrs, new);
593
  ea_sort(new);
594

    
595
  /* Normalize attributes */
596
  d = new->attrs;
597
  cnt = new->count;
598
  new->count = 0;
599
  for(i=0; i<cnt; i++)
600
    {
601
      a = &new->attrs[i];
602
#ifdef LOCAL_DEBUG
603
      {
604
        byte buf[EA_FORMAT_BUF_SIZE];
605
        ea_format(a, buf);
606
        DBG("\t%s\n", buf);
607
      }
608
#endif
609
      if (EA_PROTO(a->id) != EAP_BGP)
610
        continue;
611
      code = EA_ID(a->id);
612
      if (ATTR_KNOWN(code))
613
        {
614
          if (!bgp_attr_table[code].allow_in_ebgp && !p->is_internal)
615
            continue;
616
          /* The flags might have been zero if the attr was added by filters */
617
          a->flags = (a->flags & BAF_PARTIAL) | bgp_attr_table[code].expected_flags;
618
          if (code < 32)
619
            seen |= 1 << code;
620
        }
621
      else
622
        {
623
          /* Don't re-export unknown non-transitive attributes */
624
          if (!(a->flags & BAF_TRANSITIVE))
625
            continue;
626
        }
627
      *d = *a;
628
      if ((d->type & EAF_ORIGINATED) && !originate && (d->flags & BAF_TRANSITIVE) && (d->flags & BAF_OPTIONAL))
629
        d->flags |= BAF_PARTIAL;
630
      switch (d->type & EAF_TYPE_MASK)
631
        {
632
        case EAF_TYPE_INT_SET:
633
          {
634
            struct adata *z = alloca(sizeof(struct adata) + d->u.ptr->length);
635
            z->length = d->u.ptr->length;
636
            bgp_normalize_set((u32 *) z->data, (u32 *) d->u.ptr->data, z->length / 4);
637
            d->u.ptr = z;
638
            break;
639
          }
640
        default: ;
641
        }
642
      d++;
643
      new->count++;
644
    }
645

    
646
  /* Hash */
647
  hash = ea_hash(new);
648
  for(b=p->bucket_hash[hash & (p->hash_size - 1)]; b; b=b->hash_next)
649
    if (b->hash == hash && ea_same(b->eattrs, new))
650
      {
651
        DBG("Found bucket.\n");
652
        return b;
653
      }
654

    
655
  /* Ensure that there are all mandatory attributes */
656
  for(i=0; i<ARRAY_SIZE(bgp_mandatory_attrs); i++)
657
    if (!(seen & (1 << bgp_mandatory_attrs[i])))
658
      {
659
        log(L_ERR "%s: Mandatory attribute %s missing", p->p.name, bgp_attr_table[bgp_mandatory_attrs[i]].name);
660
        return NULL;
661
      }
662

    
663
  if (!bgp_export_check(p, new))
664
    return NULL;
665

    
666
  /* Create new bucket */
667
  DBG("Creating bucket.\n");
668
  return bgp_new_bucket(p, new, hash);
669
}
670

    
671
void
672
bgp_free_bucket(struct bgp_proto *p, struct bgp_bucket *buck)
673
{
674
  if (buck->hash_next)
675
    buck->hash_next->hash_prev = buck->hash_prev;
676
  if (buck->hash_prev)
677
    buck->hash_prev->hash_next = buck->hash_next;
678
  else
679
    p->bucket_hash[buck->hash & (p->hash_size-1)] = buck->hash_next;
680
  mb_free(buck);
681
}
682

    
683
void
684
bgp_rt_notify(struct proto *P, net *n, rte *new, rte *old UNUSED, ea_list *attrs)
685
{
686
  struct bgp_proto *p = (struct bgp_proto *) P;
687
  struct bgp_bucket *buck;
688
  struct bgp_prefix *px;
689

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

    
692
  if (new)
693
    {
694
      buck = bgp_get_bucket(p, attrs, new->attrs->source != RTS_BGP);
695
      if (!buck)                        /* Inconsistent attribute list */
696
        return;
697
    }
698
  else
699
    {
700
      if (!(buck = p->withdraw_bucket))
701
        {
702
          buck = p->withdraw_bucket = mb_alloc(P->pool, sizeof(struct bgp_bucket));
703
          init_list(&buck->prefixes);
704
        }
705
    }
706
  px = fib_get(&p->prefix_fib, &n->n.prefix, n->n.pxlen);
707
  if (px->bucket_node.next)
708
    {
709
      DBG("\tRemoving old entry.\n");
710
      rem_node(&px->bucket_node);
711
    }
712
  add_tail(&buck->prefixes, &px->bucket_node);
713
  bgp_schedule_packet(p->conn, PKT_UPDATE);
714
}
715

    
716
static int
717
bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
718
{
719
  ea_list *ea = lp_alloc(pool, sizeof(ea_list) + 4*sizeof(eattr));
720
  rta *rta = e->attrs;
721
  byte *z;
722

    
723
  ea->next = *attrs;
724
  *attrs = ea;
725
  ea->flags = EALF_SORTED;
726
  ea->count = 4;
727

    
728
  bgp_set_attr(ea->attrs, pool, BA_ORIGIN,
729
       ((rta->source == RTS_OSPF_EXT1) || (rta->source == RTS_OSPF_EXT2)) ? ORIGIN_INCOMPLETE : ORIGIN_IGP);
730

    
731
  if (p->is_internal)
732
    bgp_set_attr(ea->attrs+1, pool, BA_AS_PATH, 0);
733
  else
734
    {
735
      z = bgp_set_attr(ea->attrs+1, pool, BA_AS_PATH, bgp_as4_support ? 6 : 4);
736
      z[0] = AS_PATH_SEQUENCE;
737
      z[1] = 1;                                /* 1 AS */
738

    
739
      if (bgp_as4_support)
740
        put_u32(z+2, p->local_as);
741
      else
742
        put_u16(z+2, p->local_as);
743
    }
744

    
745
  z = bgp_set_attr(ea->attrs+2, pool, BA_NEXT_HOP, sizeof(ip_addr));
746
  if (p->cf->next_hop_self ||
747
      !p->is_internal ||
748
      rta->dest != RTD_ROUTER)
749
    {
750
      if (ipa_nonzero(p->cf->source_addr))
751
        *(ip_addr *)z = p->cf->source_addr;
752
      else
753
        *(ip_addr *)z = p->local_addr;
754
    }
755
  else
756
    *(ip_addr *)z = e->attrs->gw;
757

    
758
  bgp_set_attr(ea->attrs+3, pool, BA_LOCAL_PREF, 0);
759

    
760
  return 0;                                /* Leave decision to the filters */
761
}
762

    
763
static ea_list *
764
bgp_path_prepend(struct linpool *pool, eattr *a, ea_list *old, int as)
765
{
766
  struct ea_list *e = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
767
  struct adata *olda = a->u.ptr;
768

    
769
  e->next = old;
770
  e->flags = EALF_SORTED;
771
  e->count = 1;
772
  e->attrs[0].id = EA_CODE(EAP_BGP, BA_AS_PATH);
773
  e->attrs[0].flags = BAF_TRANSITIVE;
774
  e->attrs[0].type = EAF_TYPE_AS_PATH;
775
  e->attrs[0].u.ptr = as_path_prepend(pool, olda, as);
776
  return e;
777
}
778

    
779
static int
780
bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
781
{
782
  eattr *a;
783

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

    
787
  a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP));
788
  if (a && (p->is_internal || (!p->is_internal && e->attrs->iface == p->neigh->iface)))
789
    {
790
      /* Leave the original next hop attribute, will check later where does it point */
791
    }
792
  else
793
    {
794
      /* Need to create new one */
795
      *(ip_addr *) bgp_attach_attr(attrs, pool, BA_NEXT_HOP, sizeof(ip_addr)) = p->local_addr;
796
    }
797

    
798
  return 0;                                /* Leave decision to the filters */
799
}
800

    
801
int
802
bgp_import_control(struct proto *P, rte **new, ea_list **attrs, struct linpool *pool)
803
{
804
  rte *e = *new;
805
  struct bgp_proto *p = (struct bgp_proto *) P;
806
  struct bgp_proto *new_bgp = (e->attrs->proto->proto == &proto_bgp) ? (struct bgp_proto *) e->attrs->proto : NULL;
807

    
808
  if (p == new_bgp)                        /* Poison reverse updates */
809
    return -1;
810
  if (new_bgp)
811
    {
812
      if (p->local_as == new_bgp->local_as && p->is_internal && new_bgp->is_internal)
813
        return -1;                        /* Don't redistribute internal routes with IBGP */
814
      return bgp_update_attrs(p, e, attrs, pool);
815
    }
816
  else
817
    return bgp_create_attrs(p, e, attrs, pool);
818
}
819

    
820
int
821
bgp_rte_better(rte *new, rte *old)
822
{
823
  struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->proto;
824
  struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->proto;
825
  eattr *x, *y;
826
  u32 n, o;
827

    
828
  /* Start with local preferences */
829
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
830
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
831
  n = x ? x->u.data : new_bgp->cf->default_local_pref;
832
  o = y ? y->u.data : old_bgp->cf->default_local_pref;
833
  if (n > o)
834
    return 1;
835
  if (n < o)
836
    return 0;
837

    
838
  /* Use AS path lengths */
839
  if (new_bgp->cf->compare_path_lengths || old_bgp->cf->compare_path_lengths)
840
    {
841
      x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
842
      y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
843
      n = x ? as_path_getlen(x->u.ptr) : AS_PATH_MAXLEN;
844
      o = y ? as_path_getlen(y->u.ptr) : AS_PATH_MAXLEN;
845
      if (n < o)
846
        return 1;
847
      if (n > o)
848
        return 0;
849
    }
850

    
851
  /* Use origins */
852
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
853
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
854
  n = x ? x->u.data : ORIGIN_INCOMPLETE;
855
  o = y ? y->u.data : ORIGIN_INCOMPLETE;
856
  if (n < o)
857
    return 1;
858
  if (n > o)
859
    return 0;
860

    
861
  /* Compare MED's */
862
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
863
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
864
  n = x ? x->u.data : new_bgp->cf->default_med;
865
  o = y ? y->u.data : old_bgp->cf->default_med;
866
  if (n < o)
867
    return 1;
868
  if (n > o)
869
    return 0;
870

    
871
  /* A tie breaking procedure according to RFC 1771, section 9.1.2.1 */
872
  /* We don't have interior distances */
873
  /* We prefer external peers */
874
  if (new_bgp->is_internal > old_bgp->is_internal)
875
    return 0;
876
  if (new_bgp->is_internal < old_bgp->is_internal)
877
    return 1;
878
  /* Finally we compare BGP identifiers */
879
  return (new_bgp->remote_id < old_bgp->remote_id);
880
}
881

    
882
static int
883
bgp_path_loopy(struct bgp_proto *p, eattr *a)
884
{
885
  return as_path_is_member(a->u.ptr, p->local_as);
886
}
887

    
888

    
889
static struct adata *
890
bgp_aggregator_convert_to_new(struct adata *old, struct linpool *pool)
891
{
892
  struct adata *newa = lp_alloc(pool, sizeof(struct adata) + 8);
893
  newa->length = 8;
894
  aggregator_convert_to_new(old, newa->data);
895
  return newa;
896
}
897

    
898

    
899
/* Take last req_as ASNs from path old2 (in 2B format), convert to 4B format
900
 * and append path old4 (in 4B format).
901
 */
902
static struct adata *
903
bgp_merge_as_paths(struct adata *old2, struct adata *old4, int req_as, struct linpool *pool)
904
{
905
  byte buf[old2->length * 2];
906

    
907
  int ol = as_path_convert_to_new(old2, buf, req_as);
908
  int nl = ol + (old4 ? old4->length : 0);
909

    
910
  struct adata *newa = lp_alloc(pool, sizeof(struct adata) + nl);
911
  newa->length = nl;
912
  memcpy(newa->data, buf, ol);
913
  if (old4) memcpy(newa->data + ol, old4->data, old4->length);
914

    
915
  return newa;
916
}
917

    
918

    
919
/* Reconstruct 4B AS_PATH and AGGREGATOR according to RFC4893 4.2.3 */
920
static void
921
bgp_reconstruct_4b_atts(struct bgp_proto *p, rta *a, struct linpool *pool)
922
{
923
  eattr *p2 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
924
  eattr *p4 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS4_PATH));
925
  eattr *a2 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AGGREGATOR));
926
  eattr *a4 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS4_AGGREGATOR));
927

    
928
  if (a2)
929
    {
930
      u32 a2_as = get_u16(a2->u.ptr->data);
931

    
932
      if (a4)
933
        {
934
          if (a2_as != AS_TRANS)
935
            {
936
              /* Routes were aggregated by old router and therefore AS4_PATH
937
               * and AS4_AGGREGATOR is invalid
938
               *
939
               * Convert AS_PATH and AGGREGATOR to 4B format and finish.
940
               */
941

    
942
              a2->u.ptr = bgp_aggregator_convert_to_new(a2->u.ptr, pool);
943
              p2->u.ptr = bgp_merge_as_paths(p2->u.ptr, NULL, AS_PATH_MAXLEN, pool);
944

    
945
              return;
946
            }
947
          else
948
            {
949
              /* Common case, use AS4_AGGREGATOR attribute */
950
              a2->u.ptr = a4->u.ptr;
951
            }
952
        }
953
      else
954
        {
955
          /* Common case, use old AGGREGATOR attribute */
956
          a2->u.ptr = bgp_aggregator_convert_to_new(a2->u.ptr, pool);
957

    
958
          if (a2_as == AS_TRANS)
959
            log(L_WARN "BGP: AGGREGATOR attribute contain AS_TRANS, but AS4_AGGREGATOR is missing");
960
        }
961
    }
962
  else
963
    if (a4)
964
      log(L_WARN "BGP: AS4_AGGREGATOR attribute received, but AGGREGATOR attribute is missing");
965

    
966
  int p2_len = as_path_getlen(p2->u.ptr);
967
  int p4_len = p4 ? as_path_getlen(p4->u.ptr) : AS_PATH_MAXLEN;
968

    
969
  if (p2_len < p4_len)
970
    p2->u.ptr = bgp_merge_as_paths(p2->u.ptr, NULL, AS_PATH_MAXLEN, pool);
971
  else
972
    p2->u.ptr = bgp_merge_as_paths(p2->u.ptr, p4->u.ptr, p2_len - p4_len, pool);
973

    
974
}
975

    
976
static void
977
bgp_remove_as4_attrs(struct bgp_proto *p, rta *a)
978
{
979
  unsigned id1 = EA_CODE(EAP_BGP, BA_AS4_PATH);
980
  unsigned id2 = EA_CODE(EAP_BGP, BA_AS4_AGGREGATOR);
981
  ea_list **el = &(a->eattrs);
982

    
983
  /* We know that ea_lists constructed in bgp_decode_attrs have one attribute per ea_list struct */
984
  while (*el != NULL)
985
    {
986
      unsigned fid = (*el)->attrs[0].id;
987

    
988
      if ((fid == id1) || (fid == id2))
989
        {
990
          *el = (*el)->next;
991
          if (p->as4_support)
992
            log(L_WARN "BGP: Unexpected AS4_* attributes received");
993
        }
994
      else
995
        el = &((*el)->next);
996
    }
997
}
998

    
999
/**
1000
 * bgp_decode_attrs - check and decode BGP attributes
1001
 * @conn: connection
1002
 * @attr: start of attribute block
1003
 * @len: length of attribute block
1004
 * @pool: linear pool to make all the allocations in
1005
 * @mandatory: 1 iff presence of mandatory attributes has to be checked
1006
 *
1007
 * This function takes a BGP attribute block (a part of an Update message), checks
1008
 * its consistency and converts it to a list of BIRD route attributes represented
1009
 * by a &rta.
1010
 */
1011
struct rta *
1012
bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct linpool *pool, int mandatory)
1013
{
1014
  struct bgp_proto *bgp = conn->bgp;
1015
  rta *a = lp_alloc(pool, sizeof(struct rta));
1016
  unsigned int flags, code, l, i, type;
1017
  int errcode;
1018
  byte *z, *attr_start;
1019
  byte seen[256/8];
1020
  eattr *e;
1021
  ea_list *ea;
1022
  struct adata *ad;
1023

    
1024
  a->proto = &bgp->p;
1025
  a->source = RTS_BGP;
1026
  a->scope = SCOPE_UNIVERSE;
1027
  a->cast = RTC_UNICAST;
1028
  a->dest = RTD_ROUTER;
1029
  a->flags = 0;
1030
  a->aflags = 0;
1031
  a->from = bgp->cf->remote_ip;
1032
  a->eattrs = NULL;
1033

    
1034
  /* Parse the attributes */
1035
  bzero(seen, sizeof(seen));
1036
  DBG("BGP: Parsing attributes\n");
1037
  while (len)
1038
    {
1039
      if (len < 2)
1040
        goto malformed;
1041
      attr_start = attr;
1042
      flags = *attr++;
1043
      code = *attr++;
1044
      len -= 2;
1045
      if (flags & BAF_EXT_LEN)
1046
        {
1047
          if (len < 2)
1048
            goto malformed;
1049
          l = get_u16(attr);
1050
          attr += 2;
1051
          len -= 2;
1052
        }
1053
      else
1054
        {
1055
          if (len < 1)
1056
            goto malformed;
1057
          l = *attr++;
1058
          len--;
1059
        }
1060
      if (l > len)
1061
        goto malformed;
1062
      len -= l;
1063
      z = attr;
1064
      attr += l;
1065
      DBG("Attr %02x %02x %d\n", code, flags, l);
1066
      if (seen[code/8] & (1 << (code%8)))
1067
        goto malformed;
1068
      if (ATTR_KNOWN(code))
1069
        {
1070
          struct attr_desc *desc = &bgp_attr_table[code];
1071
          if (desc->expected_length >= 0 && desc->expected_length != (int) l)
1072
            { errcode = 5; goto err; }
1073
          if ((desc->expected_flags ^ flags) & (BAF_OPTIONAL | BAF_TRANSITIVE))
1074
            { errcode = 4; goto err; }
1075
          if (!desc->allow_in_ebgp && !bgp->is_internal)
1076
            continue;
1077
          if (desc->validate)
1078
            {
1079
              errcode = desc->validate(bgp, z, l);
1080
              if (errcode > 0)
1081
                goto err;
1082
              if (errcode < 0)
1083
                continue;
1084
            }
1085
          type = desc->type;
1086
        }
1087
      else                                /* Unknown attribute */
1088
        {
1089
          if (!(flags & BAF_OPTIONAL))
1090
            { errcode = 2; goto err; }
1091
          type = EAF_TYPE_OPAQUE;
1092
        }
1093
      seen[code/8] |= (1 << (code%8));
1094
      ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
1095
      ea->next = a->eattrs;
1096
      a->eattrs = ea;
1097
      ea->flags = 0;
1098
      ea->count = 1;
1099
      ea->attrs[0].id = EA_CODE(EAP_BGP, code);
1100
      ea->attrs[0].flags = flags;
1101
      ea->attrs[0].type = type;
1102
      if (type & EAF_EMBEDDED)
1103
        ad = NULL;
1104
      else
1105
        {
1106
          ad = lp_alloc(pool, sizeof(struct adata) + l);
1107
          ea->attrs[0].u.ptr = ad;
1108
          ad->length = l;
1109
          memcpy(ad->data, z, l);
1110
        }
1111
      switch (type)
1112
        {
1113
        case EAF_TYPE_ROUTER_ID:
1114
        case EAF_TYPE_INT:
1115
          if (l == 1)
1116
            ea->attrs[0].u.data = *z;
1117
          else
1118
            ea->attrs[0].u.data = get_u32(z);
1119
          break;
1120
        case EAF_TYPE_IP_ADDRESS:
1121
          ipa_ntoh(*(ip_addr *)ad->data);
1122
          break;
1123
        case EAF_TYPE_INT_SET:
1124
          {
1125
            u32 *z = (u32 *) ad->data;
1126
            for(i=0; i<ad->length/4; i++)
1127
              z[i] = ntohl(z[i]);
1128
            break;
1129
          }
1130
        }
1131
    }
1132

    
1133
#ifdef IPV6
1134
  if (seen[BA_MP_REACH_NLRI / 8] & (1 << (BA_MP_REACH_NLRI % 8)))
1135
    mandatory = 1;
1136
#endif
1137

    
1138
  /* Check if all mandatory attributes are present */
1139
  if (mandatory)
1140
    {
1141
      for(i=0; i < ARRAY_SIZE(bgp_mandatory_attrs); i++)
1142
        {
1143
          code = bgp_mandatory_attrs[i];
1144
          if (!(seen[code/8] & (1 << (code%8))))
1145
            {
1146
              bgp_error(conn, 3, 3, &bgp_mandatory_attrs[i], 1);
1147
              return NULL;
1148
            }
1149
        }
1150
    }
1151
  
1152
  /* When receiving attributes from non-AS4-aware BGP speaker,
1153
   * we have to reconstruct 4B AS_PATH and AGGREGATOR attributes
1154
   */
1155
  if (bgp_as4_support && (! bgp->as4_support))
1156
    bgp_reconstruct_4b_atts(bgp, a, pool);
1157

    
1158
  if (bgp_as4_support)
1159
    bgp_remove_as4_attrs(bgp, a);
1160

    
1161
  /* If the AS path attribute contains our AS, reject the routes */
1162
  e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1163
  if (e && bgp_path_loopy(bgp, e))
1164
    {
1165
      DBG("BGP: Path loop!\n");
1166
      return NULL;
1167
    }
1168

    
1169
  /* If there's no local preference, define one */
1170
  if (!(seen[0] && (1 << BA_LOCAL_PREF)))
1171
    bgp_attach_attr(&a->eattrs, pool, BA_LOCAL_PREF, 0);
1172
  return a;
1173

    
1174
malformed:
1175
  bgp_error(conn, 3, 1, NULL, 0);
1176
  return NULL;
1177

    
1178
err:
1179
  bgp_error(conn, 3, errcode, attr_start, z+l-attr_start);
1180
  return NULL;
1181
}
1182

    
1183
int
1184
bgp_get_attr(eattr *a, byte *buf)
1185
{
1186
  unsigned int i = EA_ID(a->id);
1187
  struct attr_desc *d;
1188

    
1189
  if (ATTR_KNOWN(i))
1190
    {
1191
      d = &bgp_attr_table[i];
1192
      buf += bsprintf(buf, "%s", d->name);
1193
      if (d->format)
1194
        {
1195
          *buf++ = ':';
1196
          *buf++ = ' ';
1197
          d->format(a, buf);
1198
          return GA_FULL;
1199
        }
1200
      return GA_NAME;
1201
    }
1202
  bsprintf(buf, "%02x%s", i, (a->flags & BAF_TRANSITIVE) ? " [t]" : "");
1203
  return GA_NAME;
1204
}
1205

    
1206
void
1207
bgp_attr_init(struct bgp_proto *p)
1208
{
1209
  p->hash_size = 256;
1210
  p->hash_limit = p->hash_size * 4;
1211
  p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
1212
  init_list(&p->bucket_queue);
1213
  p->withdraw_bucket = NULL;
1214
  fib_init(&p->prefix_fib, p->p.pool, sizeof(struct bgp_prefix), 0, bgp_init_prefix);
1215
}
1216

    
1217
void
1218
bgp_get_route_info(rte *e, byte *buf, ea_list *attrs)
1219
{
1220
  eattr *p = ea_find(attrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1221
  eattr *o = ea_find(attrs, EA_CODE(EAP_BGP, BA_ORIGIN));
1222
  u32 origas;
1223

    
1224
  buf += bsprintf(buf, " (%d) [", e->pref);
1225
  if (p && as_path_get_first(p->u.ptr, &origas))
1226
    buf += bsprintf(buf, "AS%u", origas);
1227
  if (o)
1228
    buf += bsprintf(buf, "%c", "ie?"[o->u.data]);
1229
  strcpy(buf, "]");
1230
}