Statistics
| Branch: | Revision:

iof-bird-daemon / proto / bgp / attrs.c @ 4827b69f

History | View | Annotate | Download (36.2 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, int buflen);
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, int buflen)
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, p->as4_session ? 4 : 2, 11);
77
}
78

    
79
static int
80
bgp_check_next_hop(struct bgp_proto *p UNUSED, byte *a, int len)
81
{
82
#ifdef IPV6
83
  return -1;
84
#else
85
  ip_addr addr;
86

    
87
  memcpy(&addr, a, len);
88
  ipa_ntoh(addr);
89
  if (ipa_classify(addr) & IADDR_HOST)
90
    return 0;
91
  else
92
    return 8;
93
#endif
94
}
95

    
96
static int
97
bgp_check_aggregator(struct bgp_proto *p, byte *a UNUSED, int len)
98
{
99
  int exp_len = p->as4_session ? 8 : 6;
100
  
101
  return (len == exp_len) ? 0 : 5;
102
}
103

    
104
static void
105
bgp_format_aggregator(eattr *a, byte *buf, int buflen UNUSED)
106
{
107
  struct adata *ad =  a->u.ptr;
108
  byte *data = ad->data;
109
  u32 as;
110

    
111
  if (bgp_as4_support)
112
    {
113
      as = get_u32(data);
114
      data += 4;
115
    }
116
  else
117
    {
118
      as = get_u16(data);
119
      data += 2;
120
    }
121

    
122
  bsprintf(buf, "%d.%d.%d.%d AS%d", data[0], data[1], data[2], data[3], as);
123
}
124

    
125
static int
126
bgp_check_cluster_list(struct bgp_proto *p UNUSED, byte *a UNUSED, int len)
127
{
128
  return ((len % 4) == 0) ? 0 : 5;
129
}
130

    
131
static void
132
bgp_format_cluster_list(eattr *a, byte *buf, int buflen UNUSED)
133
{
134
  int_set_format(a->u.ptr, 0, buf, buflen);
135
}
136

    
137
static int
138
bgp_check_reach_nlri(struct bgp_proto *p UNUSED, byte *a UNUSED, int len UNUSED)
139
{
140
#ifdef IPV6
141
  p->mp_reach_start = a;
142
  p->mp_reach_len = len;
143
#endif
144
  return -1;
145
}
146

    
147
static int
148
bgp_check_unreach_nlri(struct bgp_proto *p UNUSED, byte *a UNUSED, int len UNUSED)
149
{
150
#ifdef IPV6
151
  p->mp_unreach_start = a;
152
  p->mp_unreach_len = len;
153
#endif
154
  return -1;
155
}
156

    
157
static struct attr_desc bgp_attr_table[] = {
158
  { NULL, -1, 0, 0, 0,                                                                /* Undefined */
159
    NULL, NULL },
160
  { "origin", 1, BAF_TRANSITIVE, EAF_TYPE_INT, 1,                                /* BA_ORIGIN */
161
    bgp_check_origin, bgp_format_origin },
162
  { "as_path", -1, BAF_TRANSITIVE, EAF_TYPE_AS_PATH, 1,                                /* BA_AS_PATH */
163
    bgp_check_as_path, NULL },
164
  { "next_hop", 4, BAF_TRANSITIVE, EAF_TYPE_IP_ADDRESS, 1,                        /* BA_NEXT_HOP */
165
    bgp_check_next_hop, NULL },
166
  { "med", 4, BAF_OPTIONAL, EAF_TYPE_INT, 1,                                        /* BA_MULTI_EXIT_DISC */
167
    NULL, NULL },
168
  { "local_pref", 4, BAF_TRANSITIVE, EAF_TYPE_INT, 0,                                /* BA_LOCAL_PREF */
169
    NULL, NULL },
170
  { "atomic_aggr", 0, BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1,                        /* BA_ATOMIC_AGGR */
171
    NULL, NULL },
172
  { "aggregator", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1,        /* BA_AGGREGATOR */
173
    bgp_check_aggregator, bgp_format_aggregator },
174
  { "community", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_INT_SET, 1,        /* BA_COMMUNITY */
175
    NULL, NULL },
176
  { "originator_id", 4, BAF_OPTIONAL, EAF_TYPE_ROUTER_ID, 0,                        /* BA_ORIGINATOR_ID */
177
    NULL, NULL },
178
  { "cluster_list", -1, BAF_OPTIONAL, EAF_TYPE_INT_SET, 0,                        /* BA_CLUSTER_LIST */
179
    bgp_check_cluster_list, bgp_format_cluster_list }, 
180
  { NULL, },                                                                        /* BA_DPA */
181
  { NULL, },                                                                        /* BA_ADVERTISER */
182
  { NULL, },                                                                        /* BA_RCID_PATH */
183
  { "mp_reach_nlri", -1, BAF_OPTIONAL, EAF_TYPE_OPAQUE, 1,                        /* BA_MP_REACH_NLRI */
184
    bgp_check_reach_nlri, NULL },
185
  { "mp_unreach_nlri", -1, BAF_OPTIONAL, EAF_TYPE_OPAQUE, 1,                        /* BA_MP_UNREACH_NLRI */
186
    bgp_check_unreach_nlri, NULL },
187
  { NULL, },                                                                        /* BA_EXTENDED_COMM */
188
  { "as4_path", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1,                /* BA_AS4_PATH */
189
    NULL, NULL },
190
  { "as4_aggregator", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1,        /* BA_AS4_PATH */
191
    NULL, NULL }
192
};
193

    
194
/* BA_AS4_PATH is type EAF_TYPE_OPAQUE and not type EAF_TYPE_AS_PATH because
195
 * EAF_TYPE_AS_PATH is supposed to have different format (2 or 4 B for each ASN)
196
 * depending on bgp_as4_support variable.
197
 */
198

    
199
#define ATTR_KNOWN(code) ((code) < ARRAY_SIZE(bgp_attr_table) && bgp_attr_table[code].name)
200

    
201
static inline struct adata *
202
bgp_alloc_adata(struct linpool *pool, unsigned len)
203
{
204
  struct adata *ad = lp_alloc(pool, sizeof(struct adata) + len);
205
  ad->length = len;
206
  return ad;
207
}
208

    
209
static void
210
bgp_set_attr(eattr *e, unsigned attr, uintptr_t val)
211
{
212
  ASSERT(ATTR_KNOWN(attr));
213
  e->id = EA_CODE(EAP_BGP, attr);
214
  e->type = bgp_attr_table[attr].type;
215
  e->flags = bgp_attr_table[attr].expected_flags;
216
  if (e->type & EAF_EMBEDDED)
217
    e->u.data = val;
218
  else
219
    e->u.ptr = (struct adata *) val;
220
}
221

    
222
static byte *
223
bgp_set_attr_wa(eattr *e, struct linpool *pool, unsigned attr, unsigned len)
224
{
225
  struct adata *ad = bgp_alloc_adata(pool, len);
226
  bgp_set_attr(e, attr, (uintptr_t) ad);
227
  return ad->data;
228
}
229

    
230
void
231
bgp_attach_attr(ea_list **to, struct linpool *pool, unsigned attr, uintptr_t val)
232
{
233
  ea_list *a = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
234
  a->next = *to;
235
  *to = a;
236
  a->flags = EALF_SORTED;
237
  a->count = 1;
238
  bgp_set_attr(a->attrs, attr, val);
239
}
240

    
241
byte *
242
bgp_attach_attr_wa(ea_list **to, struct linpool *pool, unsigned attr, unsigned len)
243
{
244
  struct adata *ad = bgp_alloc_adata(pool, len);
245
  bgp_attach_attr(to, pool, attr, (uintptr_t) ad);
246
  return ad->data;
247
}
248

    
249
static int
250
bgp_encode_attr_hdr(byte *dst, unsigned int flags, unsigned code, int len)
251
{
252
  int wlen;
253

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

    
256
  if (len < 256)
257
    {
258
      *dst++ = flags;
259
      *dst++ = code;
260
      *dst++ = len;
261
      wlen = 3;
262
    }
263
  else
264
    {
265
      *dst++ = flags | BAF_EXT_LEN;
266
      *dst++ = code;
267
      put_u16(dst, len);
268
      wlen = 4;
269
    }
270

    
271
  return wlen;
272
}
273

    
274
static void
275
aggregator_convert_to_old(struct adata *aggr, byte *dst, int *new_used)
276
{
277
  byte *src = aggr->data;
278
  *new_used = 0;
279

    
280
  u32 as = get_u32(src);
281
  if (as > 0xFFFF) 
282
    {
283
      as = AS_TRANS;
284
      *new_used = 1;
285
    }
286
  put_u16(dst, as);
287

    
288
  /* Copy IPv4 address */
289
  memcpy(dst + 2, src + 4, 4);
290
}
291

    
292
static void
293
aggregator_convert_to_new(struct adata *aggr, byte *dst)
294
{
295
  byte *src = aggr->data;
296

    
297
  u32 as   = get_u16(src);
298
  put_u32(dst, as);
299

    
300
  /* Copy IPv4 address */
301
  memcpy(dst + 4, src + 2, 4);
302
}
303

    
304
static int
305
bgp_get_attr_len(eattr *a)
306
{
307
  int len;
308
  if (ATTR_KNOWN(EA_ID(a->id)))
309
    {
310
      int code = EA_ID(a->id);
311
      struct attr_desc *desc = &bgp_attr_table[code];
312
      len = desc->expected_length;
313
      if (len < 0)
314
        {
315
          ASSERT(!(a->type & EAF_EMBEDDED));
316
          len = a->u.ptr->length;
317
        }
318
    }
319
  else
320
    {
321
      ASSERT((a->type & EAF_TYPE_MASK) == EAF_TYPE_OPAQUE);
322
      len = a->u.ptr->length;
323
    }
324
  
325
  return len;
326
}
327

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

    
330
/**
331
 * bgp_encode_attrs - encode BGP attributes
332
 * @p: BGP instance
333
 * @w: buffer
334
 * @attrs: a list of extended attributes
335
 * @remains: remaining space in the buffer
336
 *
337
 * The bgp_encode_attrs() function takes a list of extended attributes
338
 * and converts it to its BGP representation (a part of an Update message).
339
 *
340
 * Result: Length of the attribute block generated or -1 if not enough space.
341
 */
342
unsigned int
343
bgp_encode_attrs(struct bgp_proto *p, byte *w, ea_list *attrs, int remains)
344
{
345
  unsigned int i, code, flags;
346
  byte *start = w;
347
  int len, rv;
348

    
349
  for(i=0; i<attrs->count; i++)
350
    {
351
      eattr *a = &attrs->attrs[i];
352
      ASSERT(EA_PROTO(a->id) == EAP_BGP);
353
      code = EA_ID(a->id);
354
#ifdef IPV6
355
      /* When talking multiprotocol BGP, the NEXT_HOP attributes are used only temporarily. */
356
      if (code == BA_NEXT_HOP)
357
        continue;
358
#endif
359

    
360
      /* When AS4-aware BGP speaker is talking to non-AS4-aware BGP speaker,
361
       * we have to convert our 4B AS_PATH to 2B AS_PATH and send our AS_PATH 
362
       * as optional AS4_PATH attribute.
363
       */
364
      if ((code == BA_AS_PATH) && bgp_as4_support && (! p->as4_session))
365
        {
366
          len = a->u.ptr->length;
367

    
368
          if (remains < (len + 4))
369
            goto err_no_buffer;
370

    
371
          /* Using temporary buffer because don't know a length of created attr
372
           * and therefore a length of a header. Perhaps i should better always
373
           * use BAF_EXT_LEN. */
374
          
375
          byte buf[len];
376
          int new_used;
377
          int nl = as_path_convert_to_old(a->u.ptr, buf, &new_used);
378

    
379
          DBG("BGP: Encoding old AS_PATH\n");
380
          rv = bgp_encode_attr_hdr(w, BAF_TRANSITIVE, BA_AS_PATH, nl);
381
          ADVANCE(w, remains, rv);
382
          memcpy(w, buf, nl);
383
          ADVANCE(w, remains, nl);
384

    
385
          if (! new_used)
386
            continue;
387

    
388
          if (remains < (len + 4))
389
            goto err_no_buffer;
390

    
391
          /* We should discard AS_CONFED_SEQUENCE or AS_CONFED_SET path segments 
392
           * here but we don't support confederations and such paths we already
393
           * discarded in bgp_check_as_path().
394
           */
395

    
396
          DBG("BGP: Encoding AS4_PATH\n");
397
          rv = bgp_encode_attr_hdr(w, BAF_OPTIONAL | BAF_TRANSITIVE, BA_AS4_PATH, len);
398
          ADVANCE(w, remains, rv);
399
          memcpy(w, a->u.ptr->data, len);
400
          ADVANCE(w, remains, len);
401

    
402
          continue;
403
        }
404

    
405
      /* The same issue with AGGREGATOR attribute */
406
      if ((code == BA_AGGREGATOR) && bgp_as4_support && (! p->as4_session))
407
        {
408
          int new_used;
409

    
410
          len = 6;
411
          if (remains < (len + 3))
412
            goto err_no_buffer;
413

    
414
          rv = bgp_encode_attr_hdr(w, BAF_OPTIONAL | BAF_TRANSITIVE, BA_AGGREGATOR, len);
415
          ADVANCE(w, remains, rv);
416
          aggregator_convert_to_old(a->u.ptr, w, &new_used);
417
          ADVANCE(w, remains, len);
418

    
419
          if (! new_used)
420
            continue;
421

    
422
          len = 8;
423
          if (remains < (len + 3))
424
            goto err_no_buffer;
425

    
426
          rv = bgp_encode_attr_hdr(w, BAF_OPTIONAL | BAF_TRANSITIVE, BA_AS4_AGGREGATOR, len);
427
          ADVANCE(w, remains, rv);
428
          memcpy(w, a->u.ptr->data, len);
429
          ADVANCE(w, remains, len);
430

    
431
          continue;
432
        }
433

    
434
      /* Standard path continues here ... */
435

    
436
      flags = a->flags & (BAF_OPTIONAL | BAF_TRANSITIVE | BAF_PARTIAL);
437
      len = bgp_get_attr_len(a);
438

    
439
      if (remains < len + 4)
440
        goto err_no_buffer;
441

    
442
      rv = bgp_encode_attr_hdr(w, flags, code, len);
443
      ADVANCE(w, remains, rv);
444

    
445
      switch (a->type & EAF_TYPE_MASK)
446
        {
447
        case EAF_TYPE_INT:
448
        case EAF_TYPE_ROUTER_ID:
449
          if (len == 4)
450
            put_u32(w, a->u.data);
451
          else
452
            *w = a->u.data;
453
          break;
454
        case EAF_TYPE_IP_ADDRESS:
455
          {
456
            ip_addr ip = *(ip_addr *)a->u.ptr->data;
457
            ipa_hton(ip);
458
            memcpy(w, &ip, len);
459
            break;
460
          }
461
        case EAF_TYPE_INT_SET:
462
          {
463
            u32 *z = (u32 *)a->u.ptr->data;
464
            int i;
465
            for(i=0; i<len; i+=4)
466
              put_u32(w+i, *z++);
467
            break;
468
          }
469
        case EAF_TYPE_OPAQUE:
470
        case EAF_TYPE_AS_PATH:
471
          memcpy(w, a->u.ptr->data, len);
472
          break;
473
        default:
474
          bug("bgp_encode_attrs: unknown attribute type %02x", a->type);
475
        }
476
      ADVANCE(w, remains, len);
477
    }
478
  return w - start;
479

    
480
 err_no_buffer:
481
  return -1;
482
}
483

    
484
static void
485
bgp_init_prefix(struct fib_node *N)
486
{
487
  struct bgp_prefix *p = (struct bgp_prefix *) N;
488
  p->bucket_node.next = NULL;
489
}
490

    
491
static int
492
bgp_compare_u32(const u32 *x, const u32 *y)
493
{
494
  return (*x < *y) ? -1 : (*x > *y) ? 1 : 0;
495
}
496

    
497
static void
498
bgp_normalize_set(u32 *dest, u32 *src, unsigned cnt)
499
{
500
  memcpy(dest, src, sizeof(u32) * cnt);
501
  qsort(dest, cnt, sizeof(u32), (int(*)(const void *, const void *)) bgp_compare_u32);
502
}
503

    
504
static void
505
bgp_rehash_buckets(struct bgp_proto *p)
506
{
507
  struct bgp_bucket **old = p->bucket_hash;
508
  struct bgp_bucket **new;
509
  unsigned oldn = p->hash_size;
510
  unsigned i, e, mask;
511
  struct bgp_bucket *b;
512

    
513
  p->hash_size = p->hash_limit;
514
  DBG("BGP: Rehashing bucket table from %d to %d\n", oldn, p->hash_size);
515
  p->hash_limit *= 4;
516
  if (p->hash_limit >= 65536)
517
    p->hash_limit = ~0;
518
  new = p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
519
  mask = p->hash_size - 1;
520
  for (i=0; i<oldn; i++)
521
    while (b = old[i])
522
      {
523
        old[i] = b->hash_next;
524
        e = b->hash & mask;
525
        b->hash_next = new[e];
526
        if (b->hash_next)
527
          b->hash_next->hash_prev = b;
528
        b->hash_prev = NULL;
529
        new[e] = b;
530
      }
531
  mb_free(old);
532
}
533

    
534
static struct bgp_bucket *
535
bgp_new_bucket(struct bgp_proto *p, ea_list *new, unsigned hash)
536
{
537
  struct bgp_bucket *b;
538
  unsigned ea_size = sizeof(ea_list) + new->count * sizeof(eattr);
539
  unsigned ea_size_aligned = BIRD_ALIGN(ea_size, CPU_STRUCT_ALIGN);
540
  unsigned size = sizeof(struct bgp_bucket) + ea_size;
541
  unsigned i;
542
  byte *dest;
543
  unsigned index = hash & (p->hash_size - 1);
544

    
545
  /* Gather total size of non-inline attributes */
546
  for (i=0; i<new->count; i++)
547
    {
548
      eattr *a = &new->attrs[i];
549
      if (!(a->type & EAF_EMBEDDED))
550
        size += BIRD_ALIGN(sizeof(struct adata) + a->u.ptr->length, CPU_STRUCT_ALIGN);
551
    }
552

    
553
  /* Create the bucket and hash it */
554
  b = mb_alloc(p->p.pool, size);
555
  b->hash_next = p->bucket_hash[index];
556
  if (b->hash_next)
557
    b->hash_next->hash_prev = b;
558
  p->bucket_hash[index] = b;
559
  b->hash_prev = NULL;
560
  b->hash = hash;
561
  add_tail(&p->bucket_queue, &b->send_node);
562
  init_list(&b->prefixes);
563
  memcpy(b->eattrs, new, ea_size);
564
  dest = ((byte *)b->eattrs) + ea_size_aligned;
565

    
566
  /* Copy values of non-inline attributes */
567
  for (i=0; i<new->count; i++)
568
    {
569
      eattr *a = &b->eattrs->attrs[i];
570
      if (!(a->type & EAF_EMBEDDED))
571
        {
572
          struct adata *oa = a->u.ptr;
573
          struct adata *na = (struct adata *) dest;
574
          memcpy(na, oa, sizeof(struct adata) + oa->length);
575
          a->u.ptr = na;
576
          dest += BIRD_ALIGN(sizeof(struct adata) + na->length, CPU_STRUCT_ALIGN);
577
        }
578
    }
579

    
580
  /* If needed, rehash */
581
  p->hash_count++;
582
  if (p->hash_count > p->hash_limit)
583
    bgp_rehash_buckets(p);
584

    
585
  return b;
586
}
587

    
588
static int
589
bgp_export_check(struct bgp_proto *p, ea_list *new)
590
{
591
  eattr *a;
592
  struct adata *d;
593

    
594
  /* Check if next hop is valid */
595
  a = ea_find(new, EA_CODE(EAP_BGP, BA_NEXT_HOP));
596
  if (!a || ipa_equal(p->next_hop, *(ip_addr *)a->u.ptr))
597
    {
598
      DBG("\tInvalid NEXT_HOP\n");
599
      return 0;
600
    }
601

    
602
  /* Check if we aren't forbidden to export the route by communities */
603
  a = ea_find(new, EA_CODE(EAP_BGP, BA_COMMUNITY));
604
  if (a)
605
    {
606
      d = a->u.ptr;
607
      if (int_set_contains(d, BGP_COMM_NO_ADVERTISE))
608
        {
609
          DBG("\tNO_ADVERTISE\n");
610
          return 0;
611
        }
612
      if (!p->is_internal &&
613
          (int_set_contains(d, BGP_COMM_NO_EXPORT) ||
614
           int_set_contains(d, BGP_COMM_NO_EXPORT_SUBCONFED)))
615
        {
616
          DBG("\tNO_EXPORT\n");
617
          return 0;
618
        }
619
    }
620

    
621
  return 1;
622
}
623

    
624
static struct bgp_bucket *
625
bgp_get_bucket(struct bgp_proto *p, ea_list *attrs, int originate)
626
{
627
  ea_list *new;
628
  unsigned i, cnt, hash, code;
629
  eattr *a, *d;
630
  u32 seen = 0;
631
  struct bgp_bucket *b;
632

    
633
  /* Merge the attribute list */
634
  new = alloca(ea_scan(attrs));
635
  ea_merge(attrs, new);
636
  ea_sort(new);
637

    
638
  /* Normalize attributes */
639
  d = new->attrs;
640
  cnt = new->count;
641
  new->count = 0;
642
  for(i=0; i<cnt; i++)
643
    {
644
      a = &new->attrs[i];
645
#ifdef LOCAL_DEBUG
646
      {
647
        byte buf[EA_FORMAT_BUF_SIZE];
648
        ea_format(a, buf);
649
        DBG("\t%s\n", buf);
650
      }
651
#endif
652
      if (EA_PROTO(a->id) != EAP_BGP)
653
        continue;
654
      code = EA_ID(a->id);
655
      if (ATTR_KNOWN(code))
656
        {
657
          if (!bgp_attr_table[code].allow_in_ebgp && !p->is_internal)
658
            continue;
659
          /* The flags might have been zero if the attr was added by filters */
660
          a->flags = (a->flags & BAF_PARTIAL) | bgp_attr_table[code].expected_flags;
661
          if (code < 32)
662
            seen |= 1 << code;
663
        }
664
      else
665
        {
666
          /* Don't re-export unknown non-transitive attributes */
667
          if (!(a->flags & BAF_TRANSITIVE))
668
            continue;
669
        }
670
      *d = *a;
671
      if ((d->type & EAF_ORIGINATED) && !originate && (d->flags & BAF_TRANSITIVE) && (d->flags & BAF_OPTIONAL))
672
        d->flags |= BAF_PARTIAL;
673
      switch (d->type & EAF_TYPE_MASK)
674
        {
675
        case EAF_TYPE_INT_SET:
676
          {
677
            struct adata *z = alloca(sizeof(struct adata) + d->u.ptr->length);
678
            z->length = d->u.ptr->length;
679
            bgp_normalize_set((u32 *) z->data, (u32 *) d->u.ptr->data, z->length / 4);
680
            d->u.ptr = z;
681
            break;
682
          }
683
        default: ;
684
        }
685
      d++;
686
      new->count++;
687
    }
688

    
689
  /* Hash */
690
  hash = ea_hash(new);
691
  for(b=p->bucket_hash[hash & (p->hash_size - 1)]; b; b=b->hash_next)
692
    if (b->hash == hash && ea_same(b->eattrs, new))
693
      {
694
        DBG("Found bucket.\n");
695
        return b;
696
      }
697

    
698
  /* Ensure that there are all mandatory attributes */
699
  for(i=0; i<ARRAY_SIZE(bgp_mandatory_attrs); i++)
700
    if (!(seen & (1 << bgp_mandatory_attrs[i])))
701
      {
702
        log(L_ERR "%s: Mandatory attribute %s missing", p->p.name, bgp_attr_table[bgp_mandatory_attrs[i]].name);
703
        return NULL;
704
      }
705

    
706
  if (!bgp_export_check(p, new))
707
    return NULL;
708

    
709
  /* Create new bucket */
710
  DBG("Creating bucket.\n");
711
  return bgp_new_bucket(p, new, hash);
712
}
713

    
714
void
715
bgp_free_bucket(struct bgp_proto *p, struct bgp_bucket *buck)
716
{
717
  if (buck->hash_next)
718
    buck->hash_next->hash_prev = buck->hash_prev;
719
  if (buck->hash_prev)
720
    buck->hash_prev->hash_next = buck->hash_next;
721
  else
722
    p->bucket_hash[buck->hash & (p->hash_size-1)] = buck->hash_next;
723
  mb_free(buck);
724
}
725

    
726
void
727
bgp_rt_notify(struct proto *P, net *n, rte *new, rte *old UNUSED, ea_list *attrs)
728
{
729
  struct bgp_proto *p = (struct bgp_proto *) P;
730
  struct bgp_bucket *buck;
731
  struct bgp_prefix *px;
732

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

    
735
  if (new)
736
    {
737
      buck = bgp_get_bucket(p, attrs, new->attrs->source != RTS_BGP);
738
      if (!buck)                        /* Inconsistent attribute list */
739
        return;
740
    }
741
  else
742
    {
743
      if (!(buck = p->withdraw_bucket))
744
        {
745
          buck = p->withdraw_bucket = mb_alloc(P->pool, sizeof(struct bgp_bucket));
746
          init_list(&buck->prefixes);
747
        }
748
    }
749
  px = fib_get(&p->prefix_fib, &n->n.prefix, n->n.pxlen);
750
  if (px->bucket_node.next)
751
    {
752
      DBG("\tRemoving old entry.\n");
753
      rem_node(&px->bucket_node);
754
    }
755
  add_tail(&buck->prefixes, &px->bucket_node);
756
  bgp_schedule_packet(p->conn, PKT_UPDATE);
757
}
758

    
759

    
760
static int
761
bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
762
{
763
  ea_list *ea = lp_alloc(pool, sizeof(ea_list) + 4*sizeof(eattr));
764
  rta *rta = e->attrs;
765
  byte *z;
766

    
767
  ea->next = *attrs;
768
  *attrs = ea;
769
  ea->flags = EALF_SORTED;
770
  ea->count = 4;
771

    
772
  bgp_set_attr(ea->attrs, BA_ORIGIN,
773
       ((rta->source == RTS_OSPF_EXT1) || (rta->source == RTS_OSPF_EXT2)) ? ORIGIN_INCOMPLETE : ORIGIN_IGP);
774

    
775
  if (p->is_internal)
776
    bgp_set_attr_wa(ea->attrs+1, pool, BA_AS_PATH, 0);
777
  else
778
    {
779
      z = bgp_set_attr_wa(ea->attrs+1, pool, BA_AS_PATH, bgp_as4_support ? 6 : 4);
780
      z[0] = AS_PATH_SEQUENCE;
781
      z[1] = 1;                                /* 1 AS */
782

    
783
      if (bgp_as4_support)
784
        put_u32(z+2, p->local_as);
785
      else
786
        put_u16(z+2, p->local_as);
787
    }
788

    
789
  z = bgp_set_attr_wa(ea->attrs+2, pool, BA_NEXT_HOP, NEXT_HOP_LENGTH);
790
  if (p->cf->next_hop_self ||
791
      !p->is_internal ||
792
      rta->dest != RTD_ROUTER)
793
    set_next_hop(z, p->source_addr);
794
  else
795
    set_next_hop(z, e->attrs->gw);
796

    
797
  bgp_set_attr(ea->attrs+3, BA_LOCAL_PREF, 0);
798

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

    
802

    
803
static inline int
804
bgp_as_path_loopy(struct bgp_proto *p, rta *a)
805
{
806
  eattr *e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
807
  return (e && as_path_is_member(e->u.ptr, p->local_as));
808
}
809

    
810
static inline int
811
bgp_originator_id_loopy(struct bgp_proto *p, rta *a)
812
{
813
  eattr *e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
814
  return (e && (e->u.data == p->local_id));
815
}
816

    
817
static inline int
818
bgp_cluster_list_loopy(struct bgp_proto *p, rta *a)
819
{
820
  eattr *e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
821
  return (e && p->rr_client && int_set_contains(e->u.ptr, p->rr_cluster_id));
822
}
823

    
824

    
825
static inline void
826
bgp_path_prepend(rte *e, ea_list **attrs, struct linpool *pool, u32 as)
827
{
828
  eattr *a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
829
  bgp_attach_attr(attrs, pool, BA_AS_PATH, (uintptr_t) as_path_prepend(pool, a->u.ptr, as));
830
}
831

    
832
static inline void
833
bgp_cluster_list_prepend(rte *e, ea_list **attrs, struct linpool *pool, u32 cid)
834
{
835
  eattr *a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
836
  bgp_attach_attr(attrs, pool, BA_CLUSTER_LIST, (uintptr_t) int_set_add(pool, a ? a->u.ptr : NULL, cid));
837
}
838

    
839
static int
840
bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool, int rr)
841
{
842
  eattr *a;
843

    
844
  if (!p->is_internal && !p->rs_client)
845
    {
846
      bgp_path_prepend(e, attrs, pool, p->local_as);
847

    
848
      /* The MULTI_EXIT_DISC attribute received from a neighboring AS MUST NOT be
849
       * propagated to other neighboring ASes.
850
       * Perhaps it would be better to undefine it.
851
       */
852
      a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
853
      if (a)
854
        bgp_attach_attr(attrs, pool, BA_MULTI_EXIT_DISC, 0);
855
    }
856

    
857
  a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP));
858
  if (a && !p->cf->next_hop_self && (p->is_internal || (!p->is_internal && e->attrs->iface == p->neigh->iface)))
859
    {
860
      /* Leave the original next hop attribute, will check later where does it point */
861
    }
862
  else
863
    {
864
      /* Need to create new one */
865
      byte *b = bgp_attach_attr_wa(attrs, pool, BA_NEXT_HOP, NEXT_HOP_LENGTH);
866
      set_next_hop(b, p->source_addr);
867
    }
868

    
869
  if (rr)
870
    {
871
      /* Handling route reflection, RFC 4456 */
872
      struct bgp_proto *src = (struct bgp_proto *) e->attrs->proto;
873

    
874
      a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
875
      if (!a)
876
        bgp_attach_attr(attrs, pool, BA_ORIGINATOR_ID, src->remote_id);
877

    
878
      /* We attach proper cluster ID according to whether the route is entering or leaving the cluster */
879
      bgp_cluster_list_prepend(e, attrs, pool, src->rr_client ? src->rr_cluster_id : p->rr_cluster_id);
880

    
881
      /* Two RR clients with different cluster ID, hmmm */
882
      if (src->rr_client && p->rr_client && (src->rr_cluster_id != p->rr_cluster_id))
883
        bgp_cluster_list_prepend(e, attrs, pool, p->rr_cluster_id);
884
    }
885

    
886
  return 0;                                /* Leave decision to the filters */
887
}
888

    
889
int
890
bgp_import_control(struct proto *P, rte **new, ea_list **attrs, struct linpool *pool)
891
{
892
  rte *e = *new;
893
  struct bgp_proto *p = (struct bgp_proto *) P;
894
  struct bgp_proto *new_bgp = (e->attrs->proto->proto == &proto_bgp) ? (struct bgp_proto *) e->attrs->proto : NULL;
895

    
896
  if (p == new_bgp)                        /* Poison reverse updates */
897
    return -1;
898
  if (new_bgp)
899
    {
900
      /* We should check here for cluster list loop, because the receiving BGP instance
901
         might have different cluster ID  */
902
      if (bgp_cluster_list_loopy(p, e->attrs))
903
        return -1;
904

    
905
      if (p->local_as == new_bgp->local_as && p->is_internal && new_bgp->is_internal)
906
        {
907
          /* Redistribution of internal routes with IBGP */
908
          if (p->rr_client || new_bgp->rr_client)
909
            /* Route reflection, RFC 4456 */
910
            return bgp_update_attrs(p, e, attrs, pool, 1);
911
          else
912
            return -1;
913
        }
914
      else
915
        return bgp_update_attrs(p, e, attrs, pool, 0);
916
    }
917
  else
918
    return bgp_create_attrs(p, e, attrs, pool);
919
}
920

    
921
static inline u32
922
bgp_get_neighbor(rte *r)
923
{
924
  eattr *e = ea_find(r->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
925
  u32 as;
926

    
927
  if (e && as_path_get_last(e->u.ptr, &as))
928
    return as;
929
  else
930
    return ((struct bgp_proto *) r->attrs->proto)->remote_as;
931
}
932

    
933
int
934
bgp_rte_better(rte *new, rte *old)
935
{
936
  struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->proto;
937
  struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->proto;
938
  eattr *x, *y;
939
  u32 n, o;
940

    
941
  /* Start with local preferences */
942
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
943
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
944
  n = x ? x->u.data : new_bgp->cf->default_local_pref;
945
  o = y ? y->u.data : old_bgp->cf->default_local_pref;
946
  if (n > o)
947
    return 1;
948
  if (n < o)
949
    return 0;
950

    
951
  /* RFC 4271 9.1.2.2. a)  Use AS path lengths */
952
  if (new_bgp->cf->compare_path_lengths || old_bgp->cf->compare_path_lengths)
953
    {
954
      x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
955
      y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
956
      n = x ? as_path_getlen(x->u.ptr) : AS_PATH_MAXLEN;
957
      o = y ? as_path_getlen(y->u.ptr) : AS_PATH_MAXLEN;
958
      if (n < o)
959
        return 1;
960
      if (n > o)
961
        return 0;
962
    }
963

    
964
  /* RFC 4271 9.1.2.2. b) Use origins */
965
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
966
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
967
  n = x ? x->u.data : ORIGIN_INCOMPLETE;
968
  o = y ? y->u.data : ORIGIN_INCOMPLETE;
969
  if (n < o)
970
    return 1;
971
  if (n > o)
972
    return 0;
973

    
974
  /* RFC 4271 9.1.2.2. c) Compare MED's */
975

    
976
  if (bgp_get_neighbor(new) == bgp_get_neighbor(old))
977
    {
978
      x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
979
      y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
980
      n = x ? x->u.data : new_bgp->cf->default_med;
981
      o = y ? y->u.data : old_bgp->cf->default_med;
982
      if (n < o)
983
        return 1;
984
      if (n > o)
985
        return 0;
986
    }
987

    
988
  /* RFC 4271 9.1.2.2. d) Prefer external peers */
989
  if (new_bgp->is_internal > old_bgp->is_internal)
990
    return 0;
991
  if (new_bgp->is_internal < old_bgp->is_internal)
992
    return 1;
993

    
994
  /* Skipping RFC 4271 9.1.2.2. e) */
995
  /* We don't have interior distances */
996

    
997
  /* RFC 4456 9. b) Compare cluster list lengths */
998
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
999
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
1000
  n = x ? int_set_get_size(x->u.ptr) : 0;
1001
  o = y ? int_set_get_size(y->u.ptr) : 0;
1002
  if (n < o)
1003
    return 1;
1004
  if (n > o)
1005
    return 0;
1006

    
1007
  /* RFC 4271 9.1.2.2. f) Compare BGP identifiers */
1008
  /* RFC 4456 9. a) Use ORIGINATOR_ID instead of local neighor ID */
1009
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
1010
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
1011
  n = x ? x->u.data : new_bgp->remote_id;
1012
  o = y ? y->u.data : old_bgp->remote_id;
1013
  if (n < o)
1014
    return 1;
1015
  if (n > o)
1016
    return 0;
1017

    
1018

    
1019
  /* RFC 4271 9.1.2.2. g) Compare peer IP adresses */
1020
  return (ipa_compare(new_bgp->cf->remote_ip, old_bgp->cf->remote_ip) < 0);
1021
}
1022

    
1023
static struct adata *
1024
bgp_aggregator_convert_to_new(struct adata *old, struct linpool *pool)
1025
{
1026
  struct adata *newa = lp_alloc(pool, sizeof(struct adata) + 8);
1027
  newa->length = 8;
1028
  aggregator_convert_to_new(old, newa->data);
1029
  return newa;
1030
}
1031

    
1032

    
1033
/* Take last req_as ASNs from path old2 (in 2B format), convert to 4B format
1034
 * and append path old4 (in 4B format).
1035
 */
1036
static struct adata *
1037
bgp_merge_as_paths(struct adata *old2, struct adata *old4, int req_as, struct linpool *pool)
1038
{
1039
  byte buf[old2->length * 2];
1040

    
1041
  int ol = as_path_convert_to_new(old2, buf, req_as);
1042
  int nl = ol + (old4 ? old4->length : 0);
1043

    
1044
  struct adata *newa = lp_alloc(pool, sizeof(struct adata) + nl);
1045
  newa->length = nl;
1046
  memcpy(newa->data, buf, ol);
1047
  if (old4) memcpy(newa->data + ol, old4->data, old4->length);
1048

    
1049
  return newa;
1050
}
1051

    
1052
static int
1053
as4_aggregator_valid(struct adata *aggr)
1054
{
1055
  if (aggr->length != 8)
1056
    return 0;
1057

    
1058
  u32 *a = (u32 *) aggr->data;
1059

    
1060
  if ((a[0] == 0) || (a[1] == 0))
1061
    return 0;
1062
}
1063

    
1064
static int
1065
as4_path_sanitize_and_get_length(struct adata *path)
1066
{
1067
  int res = 0;
1068
  u8 *p, *dst;
1069
  int len, plen, copy;
1070

    
1071
  dst = p = path->data;
1072
  len = path->length;
1073

    
1074
  while (len)
1075
    {
1076
      if (len <= 2) /* We do not allow empty segments */
1077
        goto inconsistent_path;
1078

    
1079
      switch (p[0])
1080
        {
1081
        case AS_PATH_SET:
1082
          plen = 2 + 4 * p[1];
1083
          copy = 1;
1084
          res++;
1085
          break;
1086

    
1087
        case AS_PATH_SEQUENCE:
1088
          plen = 2 + 4 * p[1];
1089
          copy = 1;
1090
          res += p[1];
1091
          break;
1092

    
1093
        case AS_PATH_CONFED_SEQUENCE:
1094
        case AS_PATH_CONFED_SET:
1095
          log(L_WARN "BGP: AS4_PATH attribute contains AS_CONFED_* segment, skipping segment");
1096
          plen = 2 + 4 * p[1];
1097
          copy = 0;
1098
          break;
1099

    
1100
        default:
1101
          goto unknown_segment;
1102
        }
1103

    
1104
      if (len < plen)
1105
        goto inconsistent_path;
1106

    
1107
      if (copy)
1108
        {
1109
          if (dst != p)
1110
            memmove(dst, p, plen);
1111
          dst += plen;
1112
        }
1113

    
1114
      len -= plen;
1115
      p += plen;
1116
    }
1117

    
1118
  path->length = dst - path->data;
1119
  return res;
1120

    
1121
 inconsistent_path:
1122
  log(L_WARN "BGP: AS4_PATH attribute is inconsistent, skipping attribute");
1123
  return -1;
1124

    
1125
 unknown_segment:
1126
  log(L_WARN "BGP: AS4_PATH attribute contains unknown segment, skipping attribute");
1127
  return -1;
1128
}
1129

    
1130

    
1131

    
1132
/* Reconstruct 4B AS_PATH and AGGREGATOR according to RFC 4893 4.2.3 */
1133
static void
1134
bgp_reconstruct_4b_atts(struct bgp_proto *p, rta *a, struct linpool *pool)
1135
{
1136
  eattr *p2 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1137
  eattr *p4 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS4_PATH));
1138
  eattr *a2 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AGGREGATOR));
1139
  eattr *a4 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS4_AGGREGATOR));
1140
  int a4_removed = 0;
1141

    
1142
  if (a4 && !as4_aggregator_valid(a4->u.ptr))
1143
    {
1144
      log(L_WARN "BGP: AS4_AGGREGATOR attribute is invalid, skipping attribute");
1145
      a4 = NULL;
1146
      a4_removed = 1;
1147
    }
1148

    
1149
  if (a2)
1150
    {
1151
      u32 a2_as = get_u16(a2->u.ptr->data);
1152

    
1153
      if (a4)
1154
        {
1155
          if (a2_as != AS_TRANS)
1156
            {
1157
              /* Routes were aggregated by old router and therefore AS4_PATH
1158
               * and AS4_AGGREGATOR is invalid
1159
               *
1160
               * Convert AS_PATH and AGGREGATOR to 4B format and finish.
1161
               */
1162

    
1163
              a2->u.ptr = bgp_aggregator_convert_to_new(a2->u.ptr, pool);
1164
              p2->u.ptr = bgp_merge_as_paths(p2->u.ptr, NULL, AS_PATH_MAXLEN, pool);
1165

    
1166
              return;
1167
            }
1168
          else
1169
            {
1170
              /* Common case, use AS4_AGGREGATOR attribute */
1171
              a2->u.ptr = a4->u.ptr;
1172
            }
1173
        }
1174
      else
1175
        {
1176
          /* Common case, use old AGGREGATOR attribute */
1177
          a2->u.ptr = bgp_aggregator_convert_to_new(a2->u.ptr, pool);
1178

    
1179
          if ((a2_as == AS_TRANS) && !a4_removed)
1180
            log(L_WARN "BGP: AGGREGATOR attribute contain AS_TRANS, but AS4_AGGREGATOR is missing");
1181
        }
1182
    }
1183
  else
1184
    if (a4)
1185
      log(L_WARN "BGP: AS4_AGGREGATOR attribute received, but AGGREGATOR attribute is missing");
1186

    
1187
  int p2_len = as_path_getlen(p2->u.ptr);
1188
  int p4_len = p4 ? as4_path_sanitize_and_get_length(p4->u.ptr) : -1;
1189

    
1190
  if ((p4_len <= 0) || (p2_len < p4_len))
1191
    p2->u.ptr = bgp_merge_as_paths(p2->u.ptr, NULL, AS_PATH_MAXLEN, pool);
1192
  else
1193
    p2->u.ptr = bgp_merge_as_paths(p2->u.ptr, p4->u.ptr, p2_len - p4_len, pool);
1194
}
1195

    
1196
static void
1197
bgp_remove_as4_attrs(struct bgp_proto *p, rta *a)
1198
{
1199
  unsigned id1 = EA_CODE(EAP_BGP, BA_AS4_PATH);
1200
  unsigned id2 = EA_CODE(EAP_BGP, BA_AS4_AGGREGATOR);
1201
  ea_list **el = &(a->eattrs);
1202

    
1203
  /* We know that ea_lists constructed in bgp_decode_attrs have one attribute per ea_list struct */
1204
  while (*el != NULL)
1205
    {
1206
      unsigned fid = (*el)->attrs[0].id;
1207

    
1208
      if ((fid == id1) || (fid == id2))
1209
        {
1210
          *el = (*el)->next;
1211
          if (p->as4_session)
1212
            log(L_WARN "BGP: Unexpected AS4_* attributes received");
1213
        }
1214
      else
1215
        el = &((*el)->next);
1216
    }
1217
}
1218

    
1219
/**
1220
 * bgp_decode_attrs - check and decode BGP attributes
1221
 * @conn: connection
1222
 * @attr: start of attribute block
1223
 * @len: length of attribute block
1224
 * @pool: linear pool to make all the allocations in
1225
 * @mandatory: 1 iff presence of mandatory attributes has to be checked
1226
 *
1227
 * This function takes a BGP attribute block (a part of an Update message), checks
1228
 * its consistency and converts it to a list of BIRD route attributes represented
1229
 * by a &rta.
1230
 */
1231
struct rta *
1232
bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct linpool *pool, int mandatory)
1233
{
1234
  struct bgp_proto *bgp = conn->bgp;
1235
  rta *a = lp_alloc(pool, sizeof(struct rta));
1236
  unsigned int flags, code, l, i, type;
1237
  int errcode;
1238
  byte *z, *attr_start;
1239
  byte seen[256/8];
1240
  eattr *e;
1241
  ea_list *ea;
1242
  struct adata *ad;
1243

    
1244
  a->proto = &bgp->p;
1245
  a->source = RTS_BGP;
1246
  a->scope = SCOPE_UNIVERSE;
1247
  a->cast = RTC_UNICAST;
1248
  a->dest = RTD_ROUTER;
1249
  a->flags = 0;
1250
  a->aflags = 0;
1251
  a->from = bgp->cf->remote_ip;
1252
  a->eattrs = NULL;
1253

    
1254
  /* Parse the attributes */
1255
  bzero(seen, sizeof(seen));
1256
  DBG("BGP: Parsing attributes\n");
1257
  while (len)
1258
    {
1259
      if (len < 2)
1260
        goto malformed;
1261
      attr_start = attr;
1262
      flags = *attr++;
1263
      code = *attr++;
1264
      len -= 2;
1265
      if (flags & BAF_EXT_LEN)
1266
        {
1267
          if (len < 2)
1268
            goto malformed;
1269
          l = get_u16(attr);
1270
          attr += 2;
1271
          len -= 2;
1272
        }
1273
      else
1274
        {
1275
          if (len < 1)
1276
            goto malformed;
1277
          l = *attr++;
1278
          len--;
1279
        }
1280
      if (l > len)
1281
        goto malformed;
1282
      len -= l;
1283
      z = attr;
1284
      attr += l;
1285
      DBG("Attr %02x %02x %d\n", code, flags, l);
1286
      if (seen[code/8] & (1 << (code%8)))
1287
        goto malformed;
1288
      if (ATTR_KNOWN(code))
1289
        {
1290
          struct attr_desc *desc = &bgp_attr_table[code];
1291
          if (desc->expected_length >= 0 && desc->expected_length != (int) l)
1292
            { errcode = 5; goto err; }
1293
          if ((desc->expected_flags ^ flags) & (BAF_OPTIONAL | BAF_TRANSITIVE))
1294
            { errcode = 4; goto err; }
1295
          if (!desc->allow_in_ebgp && !bgp->is_internal)
1296
            continue;
1297
          if (desc->validate)
1298
            {
1299
              errcode = desc->validate(bgp, z, l);
1300
              if (errcode > 0)
1301
                goto err;
1302
              if (errcode < 0)
1303
                continue;
1304
            }
1305
          type = desc->type;
1306
        }
1307
      else                                /* Unknown attribute */
1308
        {
1309
          if (!(flags & BAF_OPTIONAL))
1310
            { errcode = 2; goto err; }
1311
          type = EAF_TYPE_OPAQUE;
1312
        }
1313
      seen[code/8] |= (1 << (code%8));
1314
      ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
1315
      ea->next = a->eattrs;
1316
      a->eattrs = ea;
1317
      ea->flags = 0;
1318
      ea->count = 1;
1319
      ea->attrs[0].id = EA_CODE(EAP_BGP, code);
1320
      ea->attrs[0].flags = flags;
1321
      ea->attrs[0].type = type;
1322
      if (type & EAF_EMBEDDED)
1323
        ad = NULL;
1324
      else
1325
        {
1326
          ad = lp_alloc(pool, sizeof(struct adata) + l);
1327
          ea->attrs[0].u.ptr = ad;
1328
          ad->length = l;
1329
          memcpy(ad->data, z, l);
1330
        }
1331
      switch (type)
1332
        {
1333
        case EAF_TYPE_ROUTER_ID:
1334
        case EAF_TYPE_INT:
1335
          if (l == 1)
1336
            ea->attrs[0].u.data = *z;
1337
          else
1338
            ea->attrs[0].u.data = get_u32(z);
1339
          break;
1340
        case EAF_TYPE_IP_ADDRESS:
1341
          ipa_ntoh(*(ip_addr *)ad->data);
1342
          break;
1343
        case EAF_TYPE_INT_SET:
1344
          {
1345
            u32 *z = (u32 *) ad->data;
1346
            for(i=0; i<ad->length/4; i++)
1347
              z[i] = ntohl(z[i]);
1348
            break;
1349
          }
1350
        }
1351
    }
1352

    
1353
#ifdef IPV6
1354
  /* If we received MP_REACH_NLRI we should check mandatory attributes */
1355
  if (bgp->mp_reach_len != 0)
1356
    mandatory = 1;
1357
#endif
1358

    
1359
  /* If there is no (reachability) NLRI, we should exit now */
1360
  if (! mandatory)
1361
    return a;
1362

    
1363
  /* Check if all mandatory attributes are present */
1364
  for(i=0; i < ARRAY_SIZE(bgp_mandatory_attrs); i++)
1365
    {
1366
      code = bgp_mandatory_attrs[i];
1367
      if (!(seen[code/8] & (1 << (code%8))))
1368
        {
1369
          bgp_error(conn, 3, 3, &bgp_mandatory_attrs[i], 1);
1370
          return NULL;
1371
        }
1372
    }
1373

    
1374
  /* When receiving attributes from non-AS4-aware BGP speaker,
1375
   * we have to reconstruct 4B AS_PATH and AGGREGATOR attributes
1376
   */
1377
  if (bgp_as4_support && (! bgp->as4_session))
1378
    bgp_reconstruct_4b_atts(bgp, a, pool);
1379

    
1380
  if (bgp_as4_support)
1381
    bgp_remove_as4_attrs(bgp, a);
1382

    
1383
  /* If the AS path attribute contains our AS, reject the routes */
1384
  if (bgp_as_path_loopy(bgp, a))
1385
    goto loop;
1386

    
1387
  /* Two checks for IBGP loops caused by route reflection, RFC 4456 */ 
1388
  if (bgp_originator_id_loopy(bgp, a) ||
1389
      bgp_cluster_list_loopy(bgp, a))
1390
    goto loop;
1391

    
1392
  /* If there's no local preference, define one */
1393
  if (!(seen[0] & (1 << BA_LOCAL_PREF)))
1394
    bgp_attach_attr(&a->eattrs, pool, BA_LOCAL_PREF, 0);
1395

    
1396
  return a;
1397

    
1398
loop:
1399
  DBG("BGP: Path loop!\n");
1400
  return NULL;
1401

    
1402
malformed:
1403
  bgp_error(conn, 3, 1, NULL, 0);
1404
  return NULL;
1405

    
1406
err:
1407
  bgp_error(conn, 3, errcode, attr_start, z+l-attr_start);
1408
  return NULL;
1409
}
1410

    
1411
int
1412
bgp_get_attr(eattr *a, byte *buf, int buflen)
1413
{
1414
  unsigned int i = EA_ID(a->id);
1415
  struct attr_desc *d;
1416

    
1417
  if (ATTR_KNOWN(i))
1418
    {
1419
      d = &bgp_attr_table[i];
1420
      buf += bsprintf(buf, "%s", d->name);
1421
      if (d->format)
1422
        {
1423
          *buf++ = ':';
1424
          *buf++ = ' ';
1425
          d->format(a, buf, buflen);
1426
          return GA_FULL;
1427
        }
1428
      return GA_NAME;
1429
    }
1430
  bsprintf(buf, "%02x%s", i, (a->flags & BAF_TRANSITIVE) ? " [t]" : "");
1431
  return GA_NAME;
1432
}
1433

    
1434
void
1435
bgp_attr_init(struct bgp_proto *p)
1436
{
1437
  p->hash_size = 256;
1438
  p->hash_limit = p->hash_size * 4;
1439
  p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
1440
  init_list(&p->bucket_queue);
1441
  p->withdraw_bucket = NULL;
1442
  fib_init(&p->prefix_fib, p->p.pool, sizeof(struct bgp_prefix), 0, bgp_init_prefix);
1443
}
1444

    
1445
void
1446
bgp_get_route_info(rte *e, byte *buf, ea_list *attrs)
1447
{
1448
  eattr *p = ea_find(attrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1449
  eattr *o = ea_find(attrs, EA_CODE(EAP_BGP, BA_ORIGIN));
1450
  u32 origas;
1451

    
1452
  buf += bsprintf(buf, " (%d) [", e->pref);
1453
  if (p && as_path_get_first(p->u.ptr, &origas))
1454
    buf += bsprintf(buf, "AS%u", origas);
1455
  if (o)
1456
    buf += bsprintf(buf, "%c", "ie?"[o->u.data]);
1457
  strcpy(buf, "]");
1458
}