attrs.c 36.2 KB
Newer Older
1
2
3
4
5
6
7
8
/*
 *	BIRD -- BGP Attributes
 *
 *	(c) 2000 Martin Mares <mj@ucw.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

Martin Mareš's avatar
Martin Mareš committed
9
#undef LOCAL_DEBUG
Martin Mareš's avatar
Martin Mareš committed
10

11
12
#include <stdlib.h>

13
14
15
16
#include "nest/bird.h"
#include "nest/iface.h"
#include "nest/protocol.h"
#include "nest/route.h"
17
#include "nest/attrs.h"
18
#include "conf/conf.h"
Martin Mareš's avatar
Martin Mareš committed
19
20
21
#include "lib/resource.h"
#include "lib/string.h"
#include "lib/unaligned.h"
22
23

#include "bgp.h"
Martin Mareš's avatar
Martin Mareš committed
24

Martin Mareš's avatar
Martin Mareš committed
25
26
27
28
29
static byte bgp_mandatory_attrs[] = { BA_ORIGIN, BA_AS_PATH
#ifndef IPV6
,BA_NEXT_HOP
#endif
};
30
31

struct attr_desc {
32
  char *name;
33
34
35
  int expected_length;
  int expected_flags;
  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
Martin Mareš's avatar
Martin Mareš committed
42
bgp_check_origin(struct bgp_proto *p UNUSED, byte *a UNUSED, int len)
43
44
45
46
47
48
49
{
  if (len > 2)
    return 6;
  return 0;
}

static void
50
bgp_format_origin(eattr *a, byte *buf, int buflen)
51
52
53
54
55
56
57
{
  static char *bgp_origin_names[] = { "IGP", "EGP", "Incomplete" };

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

static int
58
bgp_check_path(byte *a, int len, int bs, int errcode)
59
60
61
62
63
{
  while (len)
    {
      DBG("Path segment %02x %02x\n", a[0], a[1]);
      if (len < 2 ||
64
65
66
67
68
	  (a[0] != AS_PATH_SET && a[0] != AS_PATH_SEQUENCE) ||
	  bs * a[1] + 2 > len)
	return errcode;
      len -= bs * a[1] + 2;
      a += bs * a[1] + 2;
69
70
71
72
    }
  return 0;
}

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

79
static int
Martin Mareš's avatar
Martin Mareš committed
80
bgp_check_next_hop(struct bgp_proto *p UNUSED, byte *a, int len)
81
{
Martin Mareš's avatar
Martin Mareš committed
82
83
84
#ifdef IPV6
  return -1;
#else
85
86
87
88
89
90
91
92
  ip_addr addr;

  memcpy(&addr, a, len);
  ipa_ntoh(addr);
  if (ipa_classify(addr) & IADDR_HOST)
    return 0;
  else
    return 8;
Martin Mareš's avatar
Martin Mareš committed
93
94
95
#endif
}

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
102
103
  
  return (len == exp_len) ? 0 : 5;
}

104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
static void
bgp_format_aggregator(eattr *a, byte *buf, int buflen UNUSED)
{
  struct adata *ad =  a->u.ptr;
  byte *data = ad->data;
  u32 as;

  if (bgp_as4_support)
    {
      as = get_u32(data);
      data += 4;
    }
  else
    {
      as = get_u16(data);
      data += 2;
    }

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

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

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

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

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

static struct attr_desc bgp_attr_table[] = {
Martin Mareš's avatar
Martin Mareš committed
158
  { NULL, -1, 0, 0, 0,								/* Undefined */
159
    NULL, NULL },
Martin Mareš's avatar
Martin Mareš committed
160
  { "origin", 1, BAF_TRANSITIVE, EAF_TYPE_INT, 1,				/* BA_ORIGIN */
161
    bgp_check_origin, bgp_format_origin },
Martin Mareš's avatar
Martin Mareš committed
162
  { "as_path", -1, BAF_TRANSITIVE, EAF_TYPE_AS_PATH, 1,				/* BA_AS_PATH */
163
    bgp_check_as_path, NULL },
Martin Mareš's avatar
Martin Mareš committed
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 },
Martin Mareš's avatar
Martin Mareš committed
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 },
Martin Mareš's avatar
Martin Mareš committed
174
  { "community", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_INT_SET, 1,	/* BA_COMMUNITY */
Martin Mareš's avatar
Martin Mareš committed
175
    NULL, NULL },
176
  { "originator_id", 4, BAF_OPTIONAL, EAF_TYPE_ROUTER_ID, 0,			/* BA_ORIGINATOR_ID */
177
178
    NULL, NULL },
  { "cluster_list", -1, BAF_OPTIONAL, EAF_TYPE_INT_SET, 0,			/* BA_CLUSTER_LIST */
179
    bgp_check_cluster_list, bgp_format_cluster_list }, 
Martin Mareš's avatar
Martin Mareš committed
180
181
182
183
184
185
186
  { NULL, },									/* BA_DPA */
  { NULL, },									/* BA_ADVERTISER */
  { NULL, },									/* BA_RCID_PATH */
  { "mp_reach_nlri", -1, BAF_OPTIONAL, EAF_TYPE_OPAQUE, 1,			/* BA_MP_REACH_NLRI */
    bgp_check_reach_nlri, NULL },
  { "mp_unreach_nlri", -1, BAF_OPTIONAL, EAF_TYPE_OPAQUE, 1,			/* BA_MP_UNREACH_NLRI */
    bgp_check_unreach_nlri, NULL },
187
188
  { NULL, },									/* BA_EXTENDED_COMM */
  { "as4_path", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1,		/* BA_AS4_PATH */
189
190
    NULL, NULL },
  { "as4_aggregator", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1,	/* BA_AS4_PATH */
191
    NULL, NULL }
192
193
};

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

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

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

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

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

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

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

249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
static int
bgp_encode_attr_hdr(byte *dst, unsigned int flags, unsigned code, int len)
{
  int wlen;

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

  if (len < 256)
    {
      *dst++ = flags;
      *dst++ = code;
      *dst++ = len;
      wlen = 3;
    }
  else
    {
      *dst++ = flags | BAF_EXT_LEN;
      *dst++ = code;
      put_u16(dst, len);
      wlen = 4;
    }

  return wlen;
}

static void
aggregator_convert_to_old(struct adata *aggr, byte *dst, int *new_used)
{
  byte *src = aggr->data;
  *new_used = 0;

  u32 as = get_u32(src);
  if (as > 0xFFFF) 
    {
      as = AS_TRANS;
      *new_used = 1;
    }
  put_u16(dst, as);

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

static void
aggregator_convert_to_new(struct adata *aggr, byte *dst)
{
  byte *src = aggr->data;

  u32 as   = get_u16(src);
  put_u32(dst, as);

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

static int
bgp_get_attr_len(eattr *a)
{
  int len;
  if (ATTR_KNOWN(EA_ID(a->id)))
    {
      int code = EA_ID(a->id);
      struct attr_desc *desc = &bgp_attr_table[code];
      len = desc->expected_length;
      if (len < 0)
	{
	  ASSERT(!(a->type & EAF_EMBEDDED));
	  len = a->u.ptr->length;
	}
    }
  else
    {
      ASSERT((a->type & EAF_TYPE_MASK) == EAF_TYPE_OPAQUE);
      len = a->u.ptr->length;
    }
  
  return len;
}

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

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

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

      /* When AS4-aware BGP speaker is talking to non-AS4-aware BGP speaker,
       * we have to convert our 4B AS_PATH to 2B AS_PATH and send our AS_PATH 
       * as optional AS4_PATH attribute.
       */
364
      if ((code == BA_AS_PATH) && bgp_as4_support && (! p->as4_session))
365
366
	{
	  len = a->u.ptr->length;
367
368
369
370
371
372
373
374
375
376
377
378

	  if (remains < (len + 4))
	    goto err_no_buffer;

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

Ondřej Zajíček's avatar
Ondřej Zajíček committed
379
	  DBG("BGP: Encoding old AS_PATH\n");
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
	  rv = bgp_encode_attr_hdr(w, BAF_TRANSITIVE, BA_AS_PATH, nl);
	  ADVANCE(w, remains, rv);
	  memcpy(w, buf, nl);
	  ADVANCE(w, remains, nl);

	  if (! new_used)
	    continue;

	  if (remains < (len + 4))
	    goto err_no_buffer;

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

Ondřej Zajíček's avatar
Ondřej Zajíček committed
396
	  DBG("BGP: Encoding AS4_PATH\n");
397
398
399
400
401
402
	  rv = bgp_encode_attr_hdr(w, BAF_OPTIONAL | BAF_TRANSITIVE, BA_AS4_PATH, len);
	  ADVANCE(w, remains, rv);
	  memcpy(w, a->u.ptr->data, len);
	  ADVANCE(w, remains, len);

	  continue;
403
	}
404
405

      /* The same issue with AGGREGATOR attribute */
406
      if ((code == BA_AGGREGATOR) && bgp_as4_support && (! p->as4_session))
407
	{
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
	  int new_used;

	  len = 6;
	  if (remains < (len + 3))
	    goto err_no_buffer;

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

	  if (! new_used)
	    continue;

	  len = 8;
	  if (remains < (len + 3))
	    goto err_no_buffer;

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

	  continue;
432
	}
433
434
435
436
437
438
439
440
441
442
443
444

      /* Standard path continues here ... */

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

      if (remains < len + 4)
	goto err_no_buffer;

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

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

 err_no_buffer:
481
  return -1;
482
}
483

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

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

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

static void
bgp_rehash_buckets(struct bgp_proto *p)
{
Martin Mareš's avatar
Martin Mareš committed
507
  struct bgp_bucket **old = p->bucket_hash;
508
509
510
511
512
513
514
515
516
517
  struct bgp_bucket **new;
  unsigned oldn = p->hash_size;
  unsigned i, e, mask;
  struct bgp_bucket *b;

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

static struct bgp_bucket *
bgp_new_bucket(struct bgp_proto *p, ea_list *new, unsigned hash)
{
  struct bgp_bucket *b;
  unsigned ea_size = sizeof(ea_list) + new->count * sizeof(eattr);
Ondřej Filip's avatar
Ondřej Filip committed
539
  unsigned ea_size_aligned = BIRD_ALIGN(ea_size, CPU_STRUCT_ALIGN);
540
541
542
543
544
545
546
547
548
549
  unsigned size = sizeof(struct bgp_bucket) + ea_size;
  unsigned i;
  byte *dest;
  unsigned index = hash & (p->hash_size - 1);

  /* Gather total size of non-inline attributes */
  for (i=0; i<new->count; i++)
    {
      eattr *a = &new->attrs[i];
      if (!(a->type & EAF_EMBEDDED))
Ondřej Filip's avatar
Ondřej Filip committed
550
	size += BIRD_ALIGN(sizeof(struct adata) + a->u.ptr->length, CPU_STRUCT_ALIGN);
551
552
553
554
    }

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

  /* Copy values of non-inline attributes */
  for (i=0; i<new->count; i++)
    {
Martin Mareš's avatar
Martin Mareš committed
569
      eattr *a = &b->eattrs->attrs[i];
570
571
572
573
574
575
      if (!(a->type & EAF_EMBEDDED))
	{
	  struct adata *oa = a->u.ptr;
	  struct adata *na = (struct adata *) dest;
	  memcpy(na, oa, sizeof(struct adata) + oa->length);
	  a->u.ptr = na;
Ondřej Filip's avatar
Ondřej Filip committed
576
	  dest += BIRD_ALIGN(sizeof(struct adata) + na->length, CPU_STRUCT_ALIGN);
577
578
579
580
581
582
583
584
585
586
587
	}
    }

  /* If needed, rehash */
  p->hash_count++;
  if (p->hash_count > p->hash_limit)
    bgp_rehash_buckets(p);

  return b;
}

588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
static int
bgp_export_check(struct bgp_proto *p, ea_list *new)
{
  eattr *a;
  struct adata *d;

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

  /* Check if we aren't forbidden to export the route by communities */
  a = ea_find(new, EA_CODE(EAP_BGP, BA_COMMUNITY));
  if (a)
    {
      d = a->u.ptr;
      if (int_set_contains(d, BGP_COMM_NO_ADVERTISE))
	{
	  DBG("\tNO_ADVERTISE\n");
	  return 0;
	}
      if (!p->is_internal &&
	  (int_set_contains(d, BGP_COMM_NO_EXPORT) ||
	   int_set_contains(d, BGP_COMM_NO_EXPORT_SUBCONFED)))
	{
	  DBG("\tNO_EXPORT\n");
	  return 0;
	}
    }

  return 1;
}

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

633
634
635
  /* Merge the attribute list */
  new = alloca(ea_scan(attrs));
  ea_merge(attrs, new);
636
  ea_sort(new);
637
638
639
640
641
642
643
644
645
646

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

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

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

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

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

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

Martin Mareš's avatar
Martin Mareš committed
726
void
Martin Mareš's avatar
Martin Mareš committed
727
bgp_rt_notify(struct proto *P, net *n, rte *new, rte *old UNUSED, ea_list *attrs)
Martin Mareš's avatar
Martin Mareš committed
728
{
729
  struct bgp_proto *p = (struct bgp_proto *) P;
730
731
  struct bgp_bucket *buck;
  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
736

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

759

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

767
768
  ea->next = *attrs;
  *attrs = ea;
Martin Mareš's avatar
Martin Mareš committed
769
  ea->flags = EALF_SORTED;
770
  ea->count = 4;
Martin Mareš's avatar
Martin Mareš committed
771

772
  bgp_set_attr(ea->attrs, BA_ORIGIN,
Ondřej Filip's avatar
Ondřej Filip committed
773
       ((rta->source == RTS_OSPF_EXT1) || (rta->source == RTS_OSPF_EXT2)) ? ORIGIN_INCOMPLETE : ORIGIN_IGP);
Martin Mareš's avatar
Martin Mareš committed
774
775

  if (p->is_internal)
776
    bgp_set_attr_wa(ea->attrs+1, pool, BA_AS_PATH, 0);
Martin Mareš's avatar
Martin Mareš committed
777
778
  else
    {
779
      z = bgp_set_attr_wa(ea->attrs+1, pool, BA_AS_PATH, bgp_as4_support ? 6 : 4);
780
      z[0] = AS_PATH_SEQUENCE;
Martin Mareš's avatar
Martin Mareš committed
781
      z[1] = 1;				/* 1 AS */
782
783
784
785
786

      if (bgp_as4_support)
	put_u32(z+2, p->local_as);
      else
	put_u16(z+2, p->local_as);
Martin Mareš's avatar
Martin Mareš committed
787
788
    }

789
  z = bgp_set_attr_wa(ea->attrs+2, pool, BA_NEXT_HOP, sizeof(ip_addr));
790
791
792
  if (p->cf->next_hop_self ||
      !p->is_internal ||
      rta->dest != RTD_ROUTER)
793
794
795
796
797
798
    {
      if (ipa_nonzero(p->cf->source_addr))
        *(ip_addr *)z = p->cf->source_addr;
      else
        *(ip_addr *)z = p->local_addr;
    }
Martin Mareš's avatar
Martin Mareš committed
799
  else
800
    *(ip_addr *)z = e->attrs->gw;
801

802
  bgp_set_attr(ea->attrs+3, BA_LOCAL_PREF, 0);
Martin Mareš's avatar
Martin Mareš committed
803

804
  return 0;				/* Leave decision to the filters */
Martin Mareš's avatar
Martin Mareš committed
805
806
}

807
808
809
810
811
812
813
814
815
816

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

static inline int
bgp_originator_id_loopy(struct bgp_proto *p, rta *a)
817
{
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
  eattr *e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
  return (e && (e->u.data == p->local_id));
}

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


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

static inline void
bgp_cluster_list_prepend(rte *e, ea_list **attrs, struct linpool *pool, u32 cid)
{
  eattr *a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
  bgp_attach_attr(attrs, pool, BA_CLUSTER_LIST, (uintptr_t) int_set_add(pool, a ? a->u.ptr : NULL, cid));
Martin Mareš's avatar
Martin Mareš committed
842
843
}

844
static int
845
bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool, int rr)
Martin Mareš's avatar
Martin Mareš committed
846
{
847
848
  eattr *a;

849
  if (!p->is_internal && !p->rs_client)
850
851
852
853
854
855
856
857
858
859
860
    {
      bgp_path_prepend(e, attrs, pool, p->local_as);

      /* The MULTI_EXIT_DISC attribute received from a neighboring AS MUST NOT be
       * propagated to other neighboring ASes.
       * Perhaps it would be better to undefine it.
       */
      a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
      if (a)
	bgp_attach_attr(attrs, pool, BA_MULTI_EXIT_DISC, 0);
    }
Martin Mareš's avatar
Martin Mareš committed
861

862
863
864
865
866
867
868
869
  a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP));
  if (a && (p->is_internal || (!p->is_internal && e->attrs->iface == p->neigh->iface)))
    {
      /* Leave the original next hop attribute, will check later where does it point */
    }
  else
    {
      /* Need to create new one */
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
      bgp_attach_attr_ip(attrs, pool, BA_NEXT_HOP, p->local_addr);
    }

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

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

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

      /* Two RR clients with different cluster ID, hmmm */
      if (src->rr_client && p->rr_client && (src->rr_cluster_id != p->rr_cluster_id))
	bgp_cluster_list_prepend(e, attrs, pool, p->rr_cluster_id);
888
    }
Martin Mareš's avatar
Martin Mareš committed
889

890
  return 0;				/* Leave decision to the filters */
Martin Mareš's avatar
Martin Mareš committed
891
892
893
894
895
896
897
898
899
}

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

900
  if (p == new_bgp)			/* Poison reverse updates */
Martin Mareš's avatar
Martin Mareš committed
901
902
903
    return -1;
  if (new_bgp)
    {
904
905
906
907
908
      /* We should check here for cluster list loop, because the receiving BGP instance
	 might have different cluster ID  */
      if (bgp_cluster_list_loopy(p, e->attrs))
	return -1;

Martin Mareš's avatar
Martin Mareš committed
909
      if (p->local_as == new_bgp->local_as && p->is_internal && new_bgp->is_internal)
910
911
912
913
914
915
916
917
918
919
	{
	  /* Redistribution of internal routes with IBGP */
	  if (p->rr_client || new_bgp->rr_client)
	    /* Route reflection, RFC 4456 */
	    return bgp_update_attrs(p, e, attrs, pool, 1);
	  else
	    return -1;
	}
      else
	return bgp_update_attrs(p, e, attrs, pool, 0);
Martin Mareš's avatar
Martin Mareš committed
920
921
    }
  else
922
    return bgp_create_attrs(p, e, attrs, pool);
Martin Mareš's avatar
Martin Mareš committed
923
924
}

925
926
927
928
929
930
931
932
933
934
935
936
static inline u32
bgp_get_neighbor(rte *r)
{
  eattr *e = ea_find(r->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
  u32 as;

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

Martin Mareš's avatar
Martin Mareš committed
937
938
939
940
941
int
bgp_rte_better(rte *new, rte *old)
{
  struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->proto;
  struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->proto;
942
943
  eattr *x, *y;
  u32 n, o;
Martin Mareš's avatar
Martin Mareš committed
944
945

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

955
  /* RFC 4271 9.1.2.2. a)  Use AS path lengths */
956
  if (new_bgp->cf->compare_path_lengths || old_bgp->cf->compare_path_lengths)
Martin Mareš's avatar
Martin Mareš committed
957
    {
958
959
      x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
      y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
960
961
      n = x ? as_path_getlen(x->u.ptr) : AS_PATH_MAXLEN;
      o = y ? as_path_getlen(y->u.ptr) : AS_PATH_MAXLEN;
962
      if (n < o)
Martin Mareš's avatar
Martin Mareš committed
963
	return 1;
964
      if (n > o)
Martin Mareš's avatar
Martin Mareš committed
965
966
967
	return 0;
    }

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

978
  /* RFC 4271 9.1.2.2. c) Compare MED's */
979
980
981
982
983
984
985
986
987
988
989
990

  if (bgp_get_neighbor(new) == bgp_get_neighbor(old))
    {
      x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
      y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
      n = x ? x->u.data : new_bgp->cf->default_med;
      o = y ? y->u.data : old_bgp->cf->default_med;
      if (n < o)
	return 1;
      if (n > o)
	return 0;
    }
991

992
  /* RFC 4271 9.1.2.2. d) Prefer external peers */
Martin Mareš's avatar
Martin Mareš committed
993
994
995
996
997
  if (new_bgp->is_internal > old_bgp->is_internal)
    return 0;
  if (new_bgp->is_internal < old_bgp->is_internal)
    return 1;

998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
  /* Skipping RFC 4271 9.1.2.2. e) */
  /* We don't have interior distances */

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

  /* RFC 4271 9.1.2.2. f) Compare BGP identifiers */
  /* RFC 4456 9. a) Use ORIGINATOR_ID instead of local neighor ID */
  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
  n = x ? x->u.data : new_bgp->remote_id;
  o = y ? y->u.data : old_bgp->remote_id;
  if (n < o)
    return 1;
  if (n > o)
    return 0;
1021
1022


1023
1024
1025
1026
  /* RFC 4271 9.1.2.2. g) Compare peer IP adresses */
  return (ipa_compare(new_bgp->cf->remote_ip, old_bgp->cf->remote_ip) < 0);
}

1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
static struct adata *
bgp_aggregator_convert_to_new(struct adata *old, struct linpool *pool)
{
  struct adata *newa = lp_alloc(pool, sizeof(struct adata) + 8);
  newa->length = 8;
  aggregator_convert_to_new(old, newa->data);
  return newa;
}


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

  int ol = as_path_convert_to_new(old2, buf, req_as);
  int nl = ol + (old4 ? old4->length : 0);
Martin Mareš's avatar
Martin Mareš committed
1047

1048
1049
1050
1051
1052
1053
1054
1055
  struct adata *newa = lp_alloc(pool, sizeof(struct adata) + nl);
  newa->length = nl;
  memcpy(newa->data, buf, ol);
  if (old4) memcpy(newa->data + ol, old4->data, old4->length);

  return newa;
}

1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
static int
as4_aggregator_valid(struct adata *aggr)
{
  if (aggr->length != 8)
    return 0;

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

  if ((a[0] == 0) || (a[1] == 0))
    return 0;
}

static int
as4_path_sanitize_and_get_length(struct adata *path)
{
  int res = 0;
  u8 *p, *dst;
  int len, plen, copy;

  dst = p = path->data;
  len = path->length;

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

      switch (p[0])
	{
	case AS_PATH_SET:
	  plen = 2 + 4 * p[1];
	  copy = 1;
	  res++;
	  break;

	case AS_PATH_SEQUENCE:
	  plen = 2 + 4 * p[1];
	  copy = 1;
	  res += p[1];
	  break;

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

	default:
	  goto unknown_segment;
	}

      if (len < plen)
	goto inconsistent_path;

      if (copy)
	{
	  if (dst != p)
	    memmove(dst, p, plen);
	  dst += plen;
	}

      len -= plen;
      p += plen;
    }

  path->length = dst - path->data;
  return res;

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

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


1135

1136
/* Reconstruct 4B AS_PATH and AGGREGATOR according to RFC 4893 4.2.3 */
1137
1138
1139
1140
1141
1142
1143
static void
bgp_reconstruct_4b_atts(struct bgp_proto *p, rta *a, struct linpool *pool)
{
  eattr *p2 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
  eattr *p4 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS4_PATH));
  eattr *a2 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AGGREGATOR));
  eattr *a4 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS4_AGGREGATOR));
1144
1145
1146
1147
1148
1149
1150
1151
  int a4_removed = 0;

  if (a4 && !as4_aggregator_valid(a4->u.ptr))
    {
      log(L_WARN "BGP: AS4_AGGREGATOR attribute is invalid, skipping attribute");
      a4 = NULL;
      a4_removed = 1;
    }
1152
1153

  if (a2)
Martin Mareš's avatar
Martin Mareš committed
1154
    {
1155
1156
1157
      u32 a2_as = get_u16(a2->u.ptr->data);

      if (a4)
Martin Mareš's avatar
Martin Mareš committed
1158
	{
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
	  if (a2_as != AS_TRANS)
	    {
	      /* Routes were aggregated by old router and therefore AS4_PATH
	       * and AS4_AGGREGATOR is invalid
	       *
	       * Convert AS_PATH and AGGREGATOR to 4B format and finish.
	       */

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

	      return;
	    }
	  else
	    {
	      /* Common case, use AS4_AGGREGATOR attribute */
	      a2->u.ptr = a4->u.ptr;
	    }
	}
      else
	{
	  /* Common case, use old AGGREGATOR attribute */
	  a2->u.ptr = bgp_aggregator_convert_to_new(a2->u.ptr, pool);

1183
	  if ((a2_as == AS_TRANS) && !a4_removed)
1184
	    log(L_WARN "BGP: AGGREGATOR attribute contain AS_TRANS, but AS4_AGGREGATOR is missing");
Martin Mareš's avatar
Martin Mareš committed
1185
1186
	}
    }
1187
1188
1189
1190
1191
  else
    if (a4)
      log(L_WARN "BGP: AS4_AGGREGATOR attribute received, but AGGREGATOR attribute is missing");

  int p2_len = as_path_getlen(p2->u.ptr);
1192
  int p4_len = p4 ? as4_path_sanitize_and_get_length(p4->u.ptr) : -1;
1193

1194
  if ((p4_len <= 0) || (p2_len < p4_len))
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
    p2->u.ptr = bgp_merge_as_paths(p2->u.ptr, NULL, AS_PATH_MAXLEN, pool);
  else
    p2->u.ptr = bgp_merge_as_paths(p2->u.ptr, p4->u.ptr, p2_len - p4_len, pool);
}

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

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

      if ((fid == id1) || (fid == id2))
	{
	  *el = (*el)->next;
1215
	  if (p->as4_session)
1216
1217
1218
1219
1220
	    log(L_WARN "BGP: Unexpected AS4_* attributes received");
	}
      else
	el = &((*el)->next);
    }
Martin Mareš's avatar
Martin Mareš committed
1221
1222
}

Martin Mareš's avatar
Martin Mareš committed
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
/**
 * bgp_decode_attrs - check and decode BGP attributes
 * @conn: connection
 * @attr: start of attribute block
 * @len: length of attribute block
 * @pool: linear pool to make all the allocations in
 * @mandatory: 1 iff presence of mandatory attributes has to be checked
 *
 * This function takes a BGP attribute block (a part of an Update message), checks
 * its consistency and converts it to a list of BIRD route attributes represented
 * by a &rta.
 */
Martin Mareš's avatar
Martin Mareš committed
1235
struct rta *
1236
bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct linpool *pool, int mandatory)
Martin Mareš's avatar
Martin Mareš committed
1237
1238
1239
{
  struct bgp_proto *bgp = conn->bgp;
  rta *a = lp_alloc(pool, sizeof(struct rta));
Martin Mareš's avatar
Martin Mareš committed
1240
1241
  unsigned int flags, code, l, i, type;
  int errcode;
Martin Mareš's avatar
Martin Mareš committed
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
  byte *z, *attr_start;
  byte seen[256/8];
  eattr *e;
  ea_list *ea;
  struct adata *ad;

  a->proto = &bgp->p;
  a->source = RTS_BGP;
  a->scope = SCOPE_UNIVERSE;
  a->cast = RTC_UNICAST;
  a->dest = RTD_ROUTER;
  a->flags = 0;
  a->aflags = 0;
  a->from = bgp->cf->remote_ip;
  a->eattrs = NULL;

  /* Parse the attributes */
  bzero(seen, sizeof(seen));
  DBG("BGP: Parsing attributes\n");
  while (len)
    {
      if (len < 2)
	goto malformed;
      attr_start = attr;
      flags = *attr++;
      code = *attr++;
      len -= 2;
      if (flags & BAF_EXT_LEN)
	{
	  if (len < 2)
	    goto malformed;
	  l = get_u16(attr);
	  attr += 2;
	  len -= 2;
	}
      else
	{
	  if (len < 1)
	    goto malformed;
	  l = *attr++;
	  len--;
	}
      if (l > len)
	goto malformed;
      len -= l;
      z = attr;
      attr += l;
      DBG("Attr %02x %02x %d\n", code, flags, l);
      if (seen[code/8] & (1 << (code%8)))
	goto malformed;
1292
      if (ATTR_KNOWN(code))
Martin Mareš's avatar
Martin Mareš committed
1293
1294
1295
1296
1297
1298
	{
	  struct attr_desc *desc = &bgp_attr_table[code];
	  if (desc->expected_length >= 0 && desc->expected_length != (int) l)
	    { errcode = 5; goto err; }
	  if ((desc->expected_flags ^ flags) & (BAF_OPTIONAL | BAF_TRANSITIVE))
	    { errcode = 4; goto err; }
1299
1300
	  if (!desc->allow_in_ebgp && !bgp->is_internal)
	    continue;
Martin Mareš's avatar
Martin Mareš committed
1301
1302
1303
1304
1305
1306
1307
1308
	  if (desc->validate)
	    {
	      errcode = desc->validate(bgp, z, l);
	      if (errcode > 0)
		goto err;
	      if (errcode < 0)
		continue;
	    }
Martin Mareš's avatar
Martin Mareš committed
1309
1310
1311
	  type = desc->type;
	}
      else				/* Unknown attribute */
1312
	{
Martin Mareš's avatar
Martin Mareš committed
1313
1314
1315
1316
	  if (!(flags & BAF_OPTIONAL))
	    { errcode = 2; goto err; }
	  type = EAF_TYPE_OPAQUE;
	}
Martin Mareš's avatar
Martin Mareš committed
1317
1318
      seen[code/8] |= (1 << (code%8));
      ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
Martin Mareš's avatar
Martin Mareš committed
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
      ea->next = a->eattrs;
      a->eattrs = ea;
      ea->flags = 0;
      ea->count = 1;
      ea->attrs[0].id = EA_CODE(EAP_BGP, code);
      ea->attrs[0].flags = flags;
      ea->attrs[0].type = type;
      if (type & EAF_EMBEDDED)
	ad = NULL;
      else
	{
	  ad = lp_alloc(pool, sizeof(struct adata) + l);
	  ea->attrs[0].u.ptr = ad;
	  ad->length = l;
	  memcpy(ad->data, z, l);
	}
      switch (type)
	{
	case EAF_TYPE_ROUTER_ID:
	case EAF_TYPE_INT:
1339
1340
1341
1342
	  if (l == 1)
	    ea->attrs[0].u.data = *z;
	  else
	    ea->attrs[0].u.data = get_u32(z);
Martin Mareš's avatar
Martin Mareš committed
1343
1344
	  break;
	case EAF_TYPE_IP_ADDRESS:
1345
	  ipa_ntoh(*(ip_addr *)ad->data);
Martin Mareš's avatar
Martin Mareš committed
1346
	  break;
Martin Mareš's avatar
Martin Mareš committed
1347
1348
1349
1350
1351
1352
1353
	case EAF_TYPE_INT_SET:
	  {
	    u32 *z = (u32 *) ad->data;
	    for(i=0; i<ad->length/4; i++)
	      z[i] = ntohl(z[i]);
	    break;
	  }
Martin Mareš's avatar
Martin Mareš committed
1354
1355
1356
	}
    }

Martin Mareš's avatar
Martin Mareš committed
1357
#ifdef IPV6
1358
1359
  /* If we received MP_REACH_NLRI we should check mandatory attributes */
  if (bgp->mp_reach_len != 0)
Martin Mareš's avatar
Martin Mareš committed
1360
1361
1362
    mandatory = 1;
#endif

1363
1364
1365
1366
  /* If there is no (reachability) NLRI, we should exit now */
  if (! mandatory)
    return a;

Martin Mareš's avatar
Martin Mareš committed
1367
  /* Check if all mandatory attributes are present */
1368
  for(i=0; i < ARRAY_SIZE(bgp_mandatory_attrs); i++)
Martin Mareš's avatar
Martin Mareš committed
1369
    {
1370
1371
      code = bgp_mandatory_attrs[i];
      if (!(seen[code/8] & (1 << (code%8))))
Martin Mareš's avatar
Martin Mareš committed
1372
	{
1373
1374
	  bgp_error(conn, 3, 3, &bgp_mandatory_attrs[i], 1);
	  return NULL;
Martin Mareš's avatar
Martin Mareš committed
1375
1376
	}
    }
1377

1378
1379
1380
  /* When receiving attributes from non-AS4-aware BGP speaker,
   * we have to reconstruct 4B AS_PATH and AGGREGATOR attributes
   */
1381
  if (bgp_as4_support && (! bgp->as4_session))
1382
1383
1384
1385
    bgp_reconstruct_4b_atts(bgp, a, pool);

  if (bgp_as4_support)
    bgp_remove_as4_attrs(bgp, a);
Martin Mareš's avatar
Martin Mareš committed
1386

Martin Mareš's avatar
Martin Mareš committed
1387
  /* If the AS path attribute contains our AS, reject the routes */
1388
1389
1390
1391
1392
1393
1394
  if (bgp_as_path_loopy(bgp, a))
    goto loop;

  /* Two checks for IBGP loops caused by route reflection, RFC 4456 */ 
  if (bgp_originator_id_loopy(bgp, a) ||
      bgp_cluster_list_loopy(bgp, a))
    goto loop;
Martin Mareš's avatar
Martin Mareš committed
1395

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