Annotation of embedaddon/bird/proto/bgp/attrs.c, revision 1.1.1.1
1.1 misho 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: /*
26: * UPDATE message error handling
27: *
28: * All checks from RFC 4271 6.3 are done as specified with these exceptions:
29: * - The semantic check of an IP address from NEXT_HOP attribute is missing.
30: * - Checks of some optional attribute values are missing.
31: * - Syntactic and semantic checks of NLRIs (done in DECODE_PREFIX())
32: * are probably inadequate.
33: *
34: * Loop detection based on AS_PATH causes updates to be withdrawn. RFC
35: * 4271 does not explicitly specifiy the behavior in that case.
36: *
37: * Loop detection related to route reflection (based on ORIGINATOR_ID
38: * and CLUSTER_LIST) causes updates to be withdrawn. RFC 4456 8
39: * specifies that such updates should be ignored, but that is generally
40: * a bad idea.
41: *
42: * Error checking of optional transitive attributes is done according to
43: * draft-ietf-idr-optional-transitive-03, but errors are handled always
44: * as withdraws.
45: *
46: * Unexpected AS_CONFED_* segments in AS_PATH are logged and removed,
47: * but unknown segments cause a session drop with Malformed AS_PATH
48: * error (see validate_path()). The behavior in such case is not
49: * explicitly specified by RFC 4271. RFC 5065 specifies that
50: * inconsistent AS_CONFED_* segments should cause a session drop, but
51: * implementations that pass invalid AS_CONFED_* segments are
52: * widespread.
53: *
54: * Error handling of AS4_* attributes is done as specified by
55: * draft-ietf-idr-rfc4893bis-03. There are several possible
56: * inconsistencies between AGGREGATOR and AS4_AGGREGATOR that are not
57: * handled by that draft, these are logged and ignored (see
58: * bgp_reconstruct_4b_attrs()).
59: */
60:
61:
62: static byte bgp_mandatory_attrs[] = { BA_ORIGIN, BA_AS_PATH
63: #ifndef IPV6
64: ,BA_NEXT_HOP
65: #endif
66: };
67:
68: struct attr_desc {
69: char *name;
70: int expected_length;
71: int expected_flags;
72: int type;
73: int allow_in_ebgp;
74: int (*validate)(struct bgp_proto *p, byte *attr, int len);
75: void (*format)(eattr *ea, byte *buf, int buflen);
76: };
77:
78: #define IGNORE -1
79: #define WITHDRAW -2
80:
81: static int
82: bgp_check_origin(struct bgp_proto *p UNUSED, byte *a, int len UNUSED)
83: {
84: if (*a > 2)
85: return 6;
86: return 0;
87: }
88:
89: static void
90: bgp_format_origin(eattr *a, byte *buf, int buflen UNUSED)
91: {
92: static char *bgp_origin_names[] = { "IGP", "EGP", "Incomplete" };
93:
94: bsprintf(buf, bgp_origin_names[a->u.data]);
95: }
96:
97: static int
98: path_segment_contains(byte *p, int bs, u32 asn)
99: {
100: int i;
101: int len = p[1];
102: p += 2;
103:
104: for(i=0; i<len; i++)
105: {
106: u32 asn2 = (bs == 4) ? get_u32(p) : get_u16(p);
107: if (asn2 == asn)
108: return 1;
109: p += bs;
110: }
111:
112: return 0;
113: }
114:
115: /* Validates path attribute, removes AS_CONFED_* segments, and also returns path length */
116: static int
117: validate_path(struct bgp_proto *p, int as_path, int bs, byte *idata, uint *ilength)
118: {
119: int res = 0;
120: u8 *a, *dst;
121: int len, plen;
122:
123: dst = a = idata;
124: len = *ilength;
125:
126: while (len)
127: {
128: if (len < 2)
129: return -1;
130:
131: plen = 2 + bs * a[1];
132: if (len < plen)
133: return -1;
134:
135: if (a[1] == 0)
136: {
137: log(L_WARN "%s: %s_PATH attribute contains empty segment, skipping it",
138: p->p.name, as_path ? "AS" : "AS4");
139: goto skip;
140: }
141:
142: switch (a[0])
143: {
144: case AS_PATH_SET:
145: res++;
146: break;
147:
148: case AS_PATH_SEQUENCE:
149: res += a[1];
150: break;
151:
152: case AS_PATH_CONFED_SEQUENCE:
153: case AS_PATH_CONFED_SET:
154: if (as_path && path_segment_contains(a, bs, p->remote_as))
155: {
156: log(L_WARN "%s: AS_CONFED_* segment with peer ASN found, misconfigured confederation?", p->p.name);
157: return -1;
158: }
159:
160: log(L_WARN "%s: %s_PATH attribute contains AS_CONFED_* segment, skipping segment",
161: p->p.name, as_path ? "AS" : "AS4");
162: goto skip;
163:
164: default:
165: return -1;
166: }
167:
168: if (dst != a)
169: memmove(dst, a, plen);
170: dst += plen;
171:
172: skip:
173: len -= plen;
174: a += plen;
175: }
176:
177: *ilength = dst - idata;
178: return res;
179: }
180:
181: static inline int
182: validate_as_path(struct bgp_proto *p, byte *a, int *len)
183: {
184: return validate_path(p, 1, p->as4_session ? 4 : 2, a, len);
185: }
186:
187: static inline int
188: validate_as4_path(struct bgp_proto *p, struct adata *path)
189: {
190: return validate_path(p, 0, 4, path->data, &path->length);
191: }
192:
193: static int
194: bgp_check_next_hop(struct bgp_proto *p UNUSED, byte *a UNUSED6, int len UNUSED6)
195: {
196: #ifdef IPV6
197: return IGNORE;
198: #else
199: ip_addr addr;
200:
201: memcpy(&addr, a, len);
202: ipa_ntoh(addr);
203: if (ipa_classify(addr) & IADDR_HOST)
204: return 0;
205: else
206: return 8;
207: #endif
208: }
209:
210: static void
211: bgp_format_next_hop(eattr *a, byte *buf, int buflen UNUSED)
212: {
213: ip_addr *ipp = (ip_addr *) a->u.ptr->data;
214: #ifdef IPV6
215: /* in IPv6, we might have two addresses in NEXT HOP */
216: if ((a->u.ptr->length == NEXT_HOP_LENGTH) && ipa_nonzero(ipp[1]))
217: {
218: bsprintf(buf, "%I %I", ipp[0], ipp[1]);
219: return;
220: }
221: #endif
222:
223: bsprintf(buf, "%I", ipp[0]);
224: }
225:
226: static int
227: bgp_check_aggregator(struct bgp_proto *p, byte *a UNUSED, int len)
228: {
229: int exp_len = p->as4_session ? 8 : 6;
230:
231: return (len == exp_len) ? 0 : WITHDRAW;
232: }
233:
234: static void
235: bgp_format_aggregator(eattr *a, byte *buf, int buflen UNUSED)
236: {
237: struct adata *ad = a->u.ptr;
238: byte *data = ad->data;
239: u32 as;
240:
241: as = get_u32(data);
242: data += 4;
243:
244: bsprintf(buf, "%d.%d.%d.%d AS%u", data[0], data[1], data[2], data[3], as);
245: }
246:
247: static int
248: bgp_check_community(struct bgp_proto *p UNUSED, byte *a UNUSED, int len)
249: {
250: return ((len % 4) == 0) ? 0 : WITHDRAW;
251: }
252:
253: static int
254: bgp_check_cluster_list(struct bgp_proto *p UNUSED, byte *a UNUSED, int len)
255: {
256: return ((len % 4) == 0) ? 0 : 5;
257: }
258:
259: static void
260: bgp_format_cluster_list(eattr *a, byte *buf, int buflen)
261: {
262: /* Truncates cluster lists larger than buflen, probably not a problem */
263: int_set_format(a->u.ptr, 0, -1, buf, buflen);
264: }
265:
266: static int
267: bgp_check_reach_nlri(struct bgp_proto *p UNUSED, byte *a UNUSED, int len UNUSED)
268: {
269: #ifdef IPV6
270: p->mp_reach_start = a;
271: p->mp_reach_len = len;
272: #endif
273: return IGNORE;
274: }
275:
276: static int
277: bgp_check_unreach_nlri(struct bgp_proto *p UNUSED, byte *a UNUSED, int len UNUSED)
278: {
279: #ifdef IPV6
280: p->mp_unreach_start = a;
281: p->mp_unreach_len = len;
282: #endif
283: return IGNORE;
284: }
285:
286: static int
287: bgp_check_ext_community(struct bgp_proto *p UNUSED, byte *a UNUSED, int len)
288: {
289: return ((len % 8) == 0) ? 0 : WITHDRAW;
290: }
291:
292: static int
293: bgp_check_large_community(struct bgp_proto *p UNUSED, byte *a UNUSED, int len)
294: {
295: return ((len % 12) == 0) ? 0 : WITHDRAW;
296: }
297:
298:
299: static struct attr_desc bgp_attr_table[] = {
300: { NULL, -1, 0, 0, 0, /* Undefined */
301: NULL, NULL },
302: { "origin", 1, BAF_TRANSITIVE, EAF_TYPE_INT, 1, /* BA_ORIGIN */
303: bgp_check_origin, bgp_format_origin },
304: { "as_path", -1, BAF_TRANSITIVE, EAF_TYPE_AS_PATH, 1, /* BA_AS_PATH */
305: NULL, NULL }, /* is checked by validate_as_path() as a special case */
306: { "next_hop", 4, BAF_TRANSITIVE, EAF_TYPE_IP_ADDRESS, 1, /* BA_NEXT_HOP */
307: bgp_check_next_hop, bgp_format_next_hop },
308: { "med", 4, BAF_OPTIONAL, EAF_TYPE_INT, 1, /* BA_MULTI_EXIT_DISC */
309: NULL, NULL },
310: { "local_pref", 4, BAF_TRANSITIVE, EAF_TYPE_INT, 0, /* BA_LOCAL_PREF */
311: NULL, NULL },
312: { "atomic_aggr", 0, BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1, /* BA_ATOMIC_AGGR */
313: NULL, NULL },
314: { "aggregator", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1, /* BA_AGGREGATOR */
315: bgp_check_aggregator, bgp_format_aggregator },
316: { "community", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_INT_SET, 1, /* BA_COMMUNITY */
317: bgp_check_community, NULL },
318: { "originator_id", 4, BAF_OPTIONAL, EAF_TYPE_ROUTER_ID, 0, /* BA_ORIGINATOR_ID */
319: NULL, NULL },
320: { "cluster_list", -1, BAF_OPTIONAL, EAF_TYPE_INT_SET, 0, /* BA_CLUSTER_LIST */
321: bgp_check_cluster_list, bgp_format_cluster_list },
322: { .name = NULL }, /* BA_DPA */
323: { .name = NULL }, /* BA_ADVERTISER */
324: { .name = NULL }, /* BA_RCID_PATH */
325: { "mp_reach_nlri", -1, BAF_OPTIONAL, EAF_TYPE_OPAQUE, 1, /* BA_MP_REACH_NLRI */
326: bgp_check_reach_nlri, NULL },
327: { "mp_unreach_nlri", -1, BAF_OPTIONAL, EAF_TYPE_OPAQUE, 1, /* BA_MP_UNREACH_NLRI */
328: bgp_check_unreach_nlri, NULL },
329: { "ext_community", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_EC_SET, 1, /* BA_EXT_COMMUNITY */
330: bgp_check_ext_community, NULL },
331: { "as4_path", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1, /* BA_AS4_PATH */
332: NULL, NULL },
333: { "as4_aggregator", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1, /* BA_AS4_PATH */
334: NULL, NULL },
335: [BA_LARGE_COMMUNITY] =
336: { "large_community", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_LC_SET, 1,
337: bgp_check_large_community, NULL }
338: };
339:
340: /* BA_AS4_PATH is type EAF_TYPE_OPAQUE and not type EAF_TYPE_AS_PATH.
341: * It does not matter as this attribute does not appear on routes in the routing table.
342: */
343:
344: #define ATTR_KNOWN(code) ((code) < ARRAY_SIZE(bgp_attr_table) && bgp_attr_table[code].name)
345:
346: static inline struct adata *
347: bgp_alloc_adata(struct linpool *pool, unsigned len)
348: {
349: struct adata *ad = lp_alloc(pool, sizeof(struct adata) + len);
350: ad->length = len;
351: return ad;
352: }
353:
354: static void
355: bgp_set_attr(eattr *e, unsigned attr, uintptr_t val)
356: {
357: ASSERT(ATTR_KNOWN(attr));
358: e->id = EA_CODE(EAP_BGP, attr);
359: e->type = bgp_attr_table[attr].type;
360: e->flags = bgp_attr_table[attr].expected_flags;
361: if (e->type & EAF_EMBEDDED)
362: e->u.data = val;
363: else
364: e->u.ptr = (struct adata *) val;
365: }
366:
367: static byte *
368: bgp_set_attr_wa(eattr *e, struct linpool *pool, unsigned attr, unsigned len)
369: {
370: struct adata *ad = bgp_alloc_adata(pool, len);
371: bgp_set_attr(e, attr, (uintptr_t) ad);
372: return ad->data;
373: }
374:
375: void
376: bgp_attach_attr(ea_list **to, struct linpool *pool, unsigned attr, uintptr_t val)
377: {
378: ea_list *a = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
379: a->next = *to;
380: *to = a;
381: a->flags = EALF_SORTED;
382: a->count = 1;
383: bgp_set_attr(a->attrs, attr, val);
384: }
385:
386: byte *
387: bgp_attach_attr_wa(ea_list **to, struct linpool *pool, unsigned attr, unsigned len)
388: {
389: struct adata *ad = bgp_alloc_adata(pool, len);
390: bgp_attach_attr(to, pool, attr, (uintptr_t) ad);
391: return ad->data;
392: }
393:
394: static int
395: bgp_encode_attr_hdr(byte *dst, uint flags, unsigned code, int len)
396: {
397: int wlen;
398:
399: DBG("\tAttribute %02x (%d bytes, flags %02x)\n", code, len, flags);
400:
401: if (len < 256)
402: {
403: *dst++ = flags;
404: *dst++ = code;
405: *dst++ = len;
406: wlen = 3;
407: }
408: else
409: {
410: *dst++ = flags | BAF_EXT_LEN;
411: *dst++ = code;
412: put_u16(dst, len);
413: wlen = 4;
414: }
415:
416: return wlen;
417: }
418:
419: static void
420: aggregator_convert_to_old(struct adata *aggr, byte *dst, int *new_used)
421: {
422: byte *src = aggr->data;
423: *new_used = 0;
424:
425: u32 as = get_u32(src);
426: if (as > 0xFFFF)
427: {
428: as = AS_TRANS;
429: *new_used = 1;
430: }
431: put_u16(dst, as);
432:
433: /* Copy IPv4 address */
434: memcpy(dst + 2, src + 4, 4);
435: }
436:
437: static void
438: aggregator_convert_to_new(struct adata *aggr, byte *dst)
439: {
440: byte *src = aggr->data;
441:
442: u32 as = get_u16(src);
443: put_u32(dst, as);
444:
445: /* Copy IPv4 address */
446: memcpy(dst + 4, src + 2, 4);
447: }
448:
449: static int
450: bgp_get_attr_len(eattr *a)
451: {
452: int len;
453: if (ATTR_KNOWN(EA_ID(a->id)))
454: {
455: int code = EA_ID(a->id);
456: struct attr_desc *desc = &bgp_attr_table[code];
457: len = desc->expected_length;
458: if (len < 0)
459: {
460: ASSERT(!(a->type & EAF_EMBEDDED));
461: len = a->u.ptr->length;
462: }
463: }
464: else
465: {
466: ASSERT((a->type & EAF_TYPE_MASK) == EAF_TYPE_OPAQUE);
467: len = a->u.ptr->length;
468: }
469:
470: return len;
471: }
472:
473: #define ADVANCE(w, r, l) do { r -= l; w += l; } while (0)
474:
475: /**
476: * bgp_encode_attrs - encode BGP attributes
477: * @p: BGP instance
478: * @w: buffer
479: * @attrs: a list of extended attributes
480: * @remains: remaining space in the buffer
481: *
482: * The bgp_encode_attrs() function takes a list of extended attributes
483: * and converts it to its BGP representation (a part of an Update message).
484: *
485: * Result: Length of the attribute block generated or -1 if not enough space.
486: */
487: uint
488: bgp_encode_attrs(struct bgp_proto *p, byte *w, ea_list *attrs, int remains)
489: {
490: uint i, code, type, flags;
491: byte *start = w;
492: int len, rv;
493:
494: for(i=0; i<attrs->count; i++)
495: {
496: eattr *a = &attrs->attrs[i];
497: ASSERT(EA_PROTO(a->id) == EAP_BGP);
498: code = EA_ID(a->id);
499:
500: #ifdef IPV6
501: /* When talking multiprotocol BGP, the NEXT_HOP attributes are used only temporarily. */
502: if (code == BA_NEXT_HOP)
503: continue;
504: #endif
505:
506: /* When AS4-aware BGP speaker is talking to non-AS4-aware BGP speaker,
507: * we have to convert our 4B AS_PATH to 2B AS_PATH and send our AS_PATH
508: * as optional AS4_PATH attribute.
509: */
510: if ((code == BA_AS_PATH) && (! p->as4_session))
511: {
512: len = a->u.ptr->length;
513:
514: if (remains < (len + 4))
515: goto err_no_buffer;
516:
517: /* Using temporary buffer because don't know a length of created attr
518: * and therefore a length of a header. Perhaps i should better always
519: * use BAF_EXT_LEN. */
520:
521: byte buf[len];
522: int new_used;
523: int nl = as_path_convert_to_old(a->u.ptr, buf, &new_used);
524:
525: DBG("BGP: Encoding old AS_PATH\n");
526: rv = bgp_encode_attr_hdr(w, BAF_TRANSITIVE, BA_AS_PATH, nl);
527: ADVANCE(w, remains, rv);
528: memcpy(w, buf, nl);
529: ADVANCE(w, remains, nl);
530:
531: if (! new_used)
532: continue;
533:
534: if (remains < (len + 4))
535: goto err_no_buffer;
536:
537: /* We should discard AS_CONFED_SEQUENCE or AS_CONFED_SET path segments
538: * here but we don't support confederations and such paths we already
539: * discarded in bgp_check_as_path().
540: */
541:
542: DBG("BGP: Encoding AS4_PATH\n");
543: rv = bgp_encode_attr_hdr(w, BAF_OPTIONAL | BAF_TRANSITIVE, BA_AS4_PATH, len);
544: ADVANCE(w, remains, rv);
545: memcpy(w, a->u.ptr->data, len);
546: ADVANCE(w, remains, len);
547:
548: continue;
549: }
550:
551: /* The same issue with AGGREGATOR attribute */
552: if ((code == BA_AGGREGATOR) && (! p->as4_session))
553: {
554: int new_used;
555:
556: len = 6;
557: if (remains < (len + 3))
558: goto err_no_buffer;
559:
560: rv = bgp_encode_attr_hdr(w, BAF_OPTIONAL | BAF_TRANSITIVE, BA_AGGREGATOR, len);
561: ADVANCE(w, remains, rv);
562: aggregator_convert_to_old(a->u.ptr, w, &new_used);
563: ADVANCE(w, remains, len);
564:
565: if (! new_used)
566: continue;
567:
568: len = 8;
569: if (remains < (len + 3))
570: goto err_no_buffer;
571:
572: rv = bgp_encode_attr_hdr(w, BAF_OPTIONAL | BAF_TRANSITIVE, BA_AS4_AGGREGATOR, len);
573: ADVANCE(w, remains, rv);
574: memcpy(w, a->u.ptr->data, len);
575: ADVANCE(w, remains, len);
576:
577: continue;
578: }
579:
580: /* Standard path continues here ... */
581:
582: type = a->type & EAF_TYPE_MASK;
583: flags = a->flags & (BAF_OPTIONAL | BAF_TRANSITIVE | BAF_PARTIAL);
584: len = bgp_get_attr_len(a);
585:
586: /* Skip empty sets */
587: if (((type == EAF_TYPE_INT_SET) || (type == EAF_TYPE_EC_SET) || (type == EAF_TYPE_LC_SET)) && (len == 0))
588: continue;
589:
590: if (remains < len + 4)
591: goto err_no_buffer;
592:
593: rv = bgp_encode_attr_hdr(w, flags, code, len);
594: ADVANCE(w, remains, rv);
595:
596: switch (type)
597: {
598: case EAF_TYPE_INT:
599: case EAF_TYPE_ROUTER_ID:
600: if (len == 4)
601: put_u32(w, a->u.data);
602: else
603: *w = a->u.data;
604: break;
605: case EAF_TYPE_IP_ADDRESS:
606: {
607: ip_addr ip = *(ip_addr *)a->u.ptr->data;
608: ipa_hton(ip);
609: memcpy(w, &ip, len);
610: break;
611: }
612: case EAF_TYPE_INT_SET:
613: case EAF_TYPE_LC_SET:
614: case EAF_TYPE_EC_SET:
615: {
616: u32 *z = int_set_get_data(a->u.ptr);
617: int i;
618: for(i=0; i<len; i+=4)
619: put_u32(w+i, *z++);
620: break;
621: }
622: case EAF_TYPE_OPAQUE:
623: case EAF_TYPE_AS_PATH:
624: memcpy(w, a->u.ptr->data, len);
625: break;
626: default:
627: bug("bgp_encode_attrs: unknown attribute type %02x", a->type);
628: }
629: ADVANCE(w, remains, len);
630: }
631: return w - start;
632:
633: err_no_buffer:
634: return -1;
635: }
636:
637: /*
638: static void
639: bgp_init_prefix(struct fib_node *N)
640: {
641: struct bgp_prefix *p = (struct bgp_prefix *) N;
642: p->bucket_node.next = NULL;
643: }
644: */
645:
646: static int
647: bgp_compare_u32(const u32 *x, const u32 *y)
648: {
649: return (*x < *y) ? -1 : (*x > *y) ? 1 : 0;
650: }
651:
652: static inline void
653: bgp_normalize_int_set(u32 *dest, u32 *src, unsigned cnt)
654: {
655: memcpy(dest, src, sizeof(u32) * cnt);
656: qsort(dest, cnt, sizeof(u32), (int(*)(const void *, const void *)) bgp_compare_u32);
657: }
658:
659: static int
660: bgp_compare_ec(const u32 *xp, const u32 *yp)
661: {
662: u64 x = ec_get(xp, 0);
663: u64 y = ec_get(yp, 0);
664: return (x < y) ? -1 : (x > y) ? 1 : 0;
665: }
666:
667: static inline void
668: bgp_normalize_ec_set(struct adata *ad, u32 *src, int internal)
669: {
670: u32 *dst = int_set_get_data(ad);
671:
672: /* Remove non-transitive communities (EC_TBIT active) on external sessions */
673: if (! internal)
674: {
675: int len = int_set_get_size(ad);
676: u32 *t = dst;
677: int i;
678:
679: for (i=0; i < len; i += 2)
680: {
681: if (src[i] & EC_TBIT)
682: continue;
683:
684: *t++ = src[i];
685: *t++ = src[i+1];
686: }
687:
688: ad->length = (t - dst) * 4;
689: }
690: else
691: memcpy(dst, src, ad->length);
692:
693: qsort(dst, ad->length / 8, 8, (int(*)(const void *, const void *)) bgp_compare_ec);
694: }
695:
696: static int
697: bgp_compare_lc(const u32 *x, const u32 *y)
698: {
699: if (x[0] != y[0])
700: return (x[0] > y[0]) ? 1 : -1;
701: if (x[1] != y[1])
702: return (x[1] > y[1]) ? 1 : -1;
703: if (x[2] != y[2])
704: return (x[2] > y[2]) ? 1 : -1;
705: return 0;
706: }
707:
708: static inline void
709: bgp_normalize_lc_set(u32 *dest, u32 *src, unsigned cnt)
710: {
711: memcpy(dest, src, LCOMM_LENGTH * cnt);
712: qsort(dest, cnt, LCOMM_LENGTH, (int(*)(const void *, const void *)) bgp_compare_lc);
713: }
714:
715: static void
716: bgp_rehash_buckets(struct bgp_proto *p)
717: {
718: struct bgp_bucket **old = p->bucket_hash;
719: struct bgp_bucket **new;
720: unsigned oldn = p->hash_size;
721: unsigned i, e, mask;
722: struct bgp_bucket *b;
723:
724: p->hash_size = p->hash_limit;
725: DBG("BGP: Rehashing bucket table from %d to %d\n", oldn, p->hash_size);
726: p->hash_limit *= 4;
727: if (p->hash_limit >= 65536)
728: p->hash_limit = ~0;
729: new = p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
730: mask = p->hash_size - 1;
731: for (i=0; i<oldn; i++)
732: while (b = old[i])
733: {
734: old[i] = b->hash_next;
735: e = b->hash & mask;
736: b->hash_next = new[e];
737: if (b->hash_next)
738: b->hash_next->hash_prev = b;
739: b->hash_prev = NULL;
740: new[e] = b;
741: }
742: mb_free(old);
743: }
744:
745: static struct bgp_bucket *
746: bgp_new_bucket(struct bgp_proto *p, ea_list *new, unsigned hash)
747: {
748: struct bgp_bucket *b;
749: unsigned ea_size = sizeof(ea_list) + new->count * sizeof(eattr);
750: unsigned ea_size_aligned = BIRD_ALIGN(ea_size, CPU_STRUCT_ALIGN);
751: unsigned size = sizeof(struct bgp_bucket) + ea_size_aligned;
752: unsigned i;
753: byte *dest;
754: unsigned index = hash & (p->hash_size - 1);
755:
756: /* Gather total size of non-inline attributes */
757: for (i=0; i<new->count; i++)
758: {
759: eattr *a = &new->attrs[i];
760: if (!(a->type & EAF_EMBEDDED))
761: size += BIRD_ALIGN(sizeof(struct adata) + a->u.ptr->length, CPU_STRUCT_ALIGN);
762: }
763:
764: /* Create the bucket and hash it */
765: b = mb_alloc(p->p.pool, size);
766: b->hash_next = p->bucket_hash[index];
767: if (b->hash_next)
768: b->hash_next->hash_prev = b;
769: p->bucket_hash[index] = b;
770: b->hash_prev = NULL;
771: b->hash = hash;
772: add_tail(&p->bucket_queue, &b->send_node);
773: init_list(&b->prefixes);
774: memcpy(b->eattrs, new, ea_size);
775: dest = ((byte *)b->eattrs) + ea_size_aligned;
776:
777: /* Copy values of non-inline attributes */
778: for (i=0; i<new->count; i++)
779: {
780: eattr *a = &b->eattrs->attrs[i];
781: if (!(a->type & EAF_EMBEDDED))
782: {
783: struct adata *oa = a->u.ptr;
784: struct adata *na = (struct adata *) dest;
785: memcpy(na, oa, sizeof(struct adata) + oa->length);
786: a->u.ptr = na;
787: dest += BIRD_ALIGN(sizeof(struct adata) + na->length, CPU_STRUCT_ALIGN);
788: }
789: }
790:
791: /* If needed, rehash */
792: p->hash_count++;
793: if (p->hash_count > p->hash_limit)
794: bgp_rehash_buckets(p);
795:
796: return b;
797: }
798:
799: static struct bgp_bucket *
800: bgp_get_bucket(struct bgp_proto *p, net *n, ea_list *attrs, int originate)
801: {
802: ea_list *new;
803: unsigned i, cnt, hash, code;
804: eattr *a, *d;
805: u32 seen = 0;
806: struct bgp_bucket *b;
807:
808: /* Merge the attribute list */
809: new = alloca(ea_scan(attrs));
810: ea_merge(attrs, new);
811: ea_sort(new);
812:
813: /* Normalize attributes */
814: d = new->attrs;
815: cnt = new->count;
816: new->count = 0;
817: for(i=0; i<cnt; i++)
818: {
819: a = &new->attrs[i];
820: if (EA_PROTO(a->id) != EAP_BGP)
821: continue;
822: code = EA_ID(a->id);
823: if (ATTR_KNOWN(code))
824: {
825: if (!bgp_attr_table[code].allow_in_ebgp && !p->is_internal)
826: continue;
827: /* The flags might have been zero if the attr was added by filters */
828: a->flags = (a->flags & BAF_PARTIAL) | bgp_attr_table[code].expected_flags;
829: if (code < 32)
830: seen |= 1 << code;
831: }
832: else
833: {
834: /* Don't re-export unknown non-transitive attributes */
835: if (!(a->flags & BAF_TRANSITIVE))
836: continue;
837: }
838: *d = *a;
839: if ((d->type & EAF_ORIGINATED) && !originate && (d->flags & BAF_TRANSITIVE) && (d->flags & BAF_OPTIONAL))
840: d->flags |= BAF_PARTIAL;
841: switch (d->type & EAF_TYPE_MASK)
842: {
843: case EAF_TYPE_INT_SET:
844: {
845: struct adata *z = alloca(sizeof(struct adata) + d->u.ptr->length);
846: z->length = d->u.ptr->length;
847: bgp_normalize_int_set((u32 *) z->data, (u32 *) d->u.ptr->data, z->length / 4);
848: d->u.ptr = z;
849: break;
850: }
851: case EAF_TYPE_EC_SET:
852: {
853: struct adata *z = alloca(sizeof(struct adata) + d->u.ptr->length);
854: z->length = d->u.ptr->length;
855: bgp_normalize_ec_set(z, (u32 *) d->u.ptr->data, p->is_internal);
856: d->u.ptr = z;
857: break;
858: }
859: case EAF_TYPE_LC_SET:
860: {
861: struct adata *z = alloca(sizeof(struct adata) + d->u.ptr->length);
862: z->length = d->u.ptr->length;
863: bgp_normalize_lc_set((u32 *) z->data, (u32 *) d->u.ptr->data, z->length / LCOMM_LENGTH);
864: d->u.ptr = z;
865: break;
866: }
867: default: ;
868: }
869: d++;
870: new->count++;
871: }
872:
873: /* Hash */
874: hash = ea_hash(new);
875: for(b=p->bucket_hash[hash & (p->hash_size - 1)]; b; b=b->hash_next)
876: if (b->hash == hash && ea_same(b->eattrs, new))
877: {
878: DBG("Found bucket.\n");
879: return b;
880: }
881:
882: /* Ensure that there are all mandatory attributes */
883: for(i=0; i<ARRAY_SIZE(bgp_mandatory_attrs); i++)
884: if (!(seen & (1 << bgp_mandatory_attrs[i])))
885: {
886: log(L_ERR "%s: Mandatory attribute %s missing in route %I/%d", p->p.name, bgp_attr_table[bgp_mandatory_attrs[i]].name, n->n.prefix, n->n.pxlen);
887: return NULL;
888: }
889:
890: /* Check if next hop is valid */
891: a = ea_find(new, EA_CODE(EAP_BGP, BA_NEXT_HOP));
892: if (!a || ipa_equal(p->cf->remote_ip, *(ip_addr *)a->u.ptr->data))
893: {
894: log(L_ERR "%s: Invalid NEXT_HOP attribute in route %I/%d", p->p.name, n->n.prefix, n->n.pxlen);
895: return NULL;
896: }
897:
898: /* Create new bucket */
899: DBG("Creating bucket.\n");
900: return bgp_new_bucket(p, new, hash);
901: }
902:
903: void
904: bgp_free_bucket(struct bgp_proto *p, struct bgp_bucket *buck)
905: {
906: if (buck->hash_next)
907: buck->hash_next->hash_prev = buck->hash_prev;
908: if (buck->hash_prev)
909: buck->hash_prev->hash_next = buck->hash_next;
910: else
911: p->bucket_hash[buck->hash & (p->hash_size-1)] = buck->hash_next;
912: mb_free(buck);
913: }
914:
915:
916: /* Prefix hash table */
917:
918: #define PXH_KEY(n1) n1->n.prefix, n1->n.pxlen, n1->path_id
919: #define PXH_NEXT(n) n->next
920: #define PXH_EQ(p1,l1,i1,p2,l2,i2) ipa_equal(p1, p2) && l1 == l2 && i1 == i2
921: #define PXH_FN(p,l,i) ipa_hash32(p) ^ u32_hash((l << 16) ^ i)
922:
923: #define PXH_REHASH bgp_pxh_rehash
924: #define PXH_PARAMS /8, *2, 2, 2, 8, 20
925:
926:
927: HASH_DEFINE_REHASH_FN(PXH, struct bgp_prefix)
928:
929: void
930: bgp_init_prefix_table(struct bgp_proto *p, u32 order)
931: {
932: HASH_INIT(p->prefix_hash, p->p.pool, order);
933:
934: p->prefix_slab = sl_new(p->p.pool, sizeof(struct bgp_prefix));
935: }
936:
937: void
938: bgp_free_prefix_table(struct bgp_proto *p)
939: {
940: HASH_FREE(p->prefix_hash);
941:
942: rfree(p->prefix_slab);
943: p->prefix_slab = NULL;
944: }
945:
946: static struct bgp_prefix *
947: bgp_get_prefix(struct bgp_proto *p, ip_addr prefix, int pxlen, u32 path_id)
948: {
949: struct bgp_prefix *bp = HASH_FIND(p->prefix_hash, PXH, prefix, pxlen, path_id);
950:
951: if (bp)
952: return bp;
953:
954: bp = sl_alloc(p->prefix_slab);
955: bp->n.prefix = prefix;
956: bp->n.pxlen = pxlen;
957: bp->path_id = path_id;
958: bp->bucket_node.next = NULL;
959:
960: HASH_INSERT2(p->prefix_hash, PXH, p->p.pool, bp);
961:
962: return bp;
963: }
964:
965: void
966: bgp_free_prefix(struct bgp_proto *p, struct bgp_prefix *bp)
967: {
968: HASH_REMOVE2(p->prefix_hash, PXH, p->p.pool, bp);
969: sl_free(p->prefix_slab, bp);
970: }
971:
972:
973: void
974: bgp_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old UNUSED, ea_list *attrs)
975: {
976: struct bgp_proto *p = (struct bgp_proto *) P;
977: struct bgp_bucket *buck;
978: struct bgp_prefix *px;
979: rte *key;
980: u32 path_id;
981:
982: DBG("BGP: Got route %I/%d %s\n", n->n.prefix, n->n.pxlen, new ? "up" : "down");
983:
984: if (new)
985: {
986: key = new;
987: buck = bgp_get_bucket(p, n, attrs, new->attrs->source != RTS_BGP);
988: if (!buck) /* Inconsistent attribute list */
989: return;
990: }
991: else
992: {
993: key = old;
994: if (!(buck = p->withdraw_bucket))
995: {
996: buck = p->withdraw_bucket = mb_alloc(P->pool, sizeof(struct bgp_bucket));
997: init_list(&buck->prefixes);
998: }
999: }
1000: path_id = p->add_path_tx ? key->attrs->src->global_id : 0;
1001: px = bgp_get_prefix(p, n->n.prefix, n->n.pxlen, path_id);
1002: if (px->bucket_node.next)
1003: {
1004: DBG("\tRemoving old entry.\n");
1005: rem_node(&px->bucket_node);
1006: }
1007: add_tail(&buck->prefixes, &px->bucket_node);
1008: bgp_schedule_packet(p->conn, PKT_UPDATE);
1009: }
1010:
1011: static int
1012: bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
1013: {
1014: ea_list *ea = lp_alloc(pool, sizeof(ea_list) + 4*sizeof(eattr));
1015: rta *rta = e->attrs;
1016: byte *z;
1017:
1018: ea->next = *attrs;
1019: *attrs = ea;
1020: ea->flags = EALF_SORTED;
1021: ea->count = 4;
1022:
1023: bgp_set_attr(ea->attrs, BA_ORIGIN,
1024: ((rta->source == RTS_OSPF_EXT1) || (rta->source == RTS_OSPF_EXT2)) ? ORIGIN_INCOMPLETE : ORIGIN_IGP);
1025:
1026: if (p->is_internal)
1027: bgp_set_attr_wa(ea->attrs+1, pool, BA_AS_PATH, 0);
1028: else
1029: {
1030: z = bgp_set_attr_wa(ea->attrs+1, pool, BA_AS_PATH, 6);
1031: z[0] = AS_PATH_SEQUENCE;
1032: z[1] = 1; /* 1 AS */
1033: put_u32(z+2, p->local_as);
1034: }
1035:
1036: /* iBGP -> use gw, eBGP multi-hop -> use source_addr,
1037: eBGP single-hop -> use gw if on the same iface */
1038: z = bgp_set_attr_wa(ea->attrs+2, pool, BA_NEXT_HOP, NEXT_HOP_LENGTH);
1039: if (p->cf->next_hop_self ||
1040: rta->dest != RTD_ROUTER ||
1041: ipa_equal(rta->gw, IPA_NONE) ||
1042: ipa_is_link_local(rta->gw) ||
1043: (!p->is_internal && !p->cf->next_hop_keep &&
1044: (!p->neigh || (rta->iface != p->neigh->iface))))
1045: set_next_hop(z, p->source_addr);
1046: else
1047: set_next_hop(z, rta->gw);
1048:
1049: bgp_set_attr(ea->attrs+3, BA_LOCAL_PREF, p->cf->default_local_pref);
1050:
1051: return 0; /* Leave decision to the filters */
1052: }
1053:
1054:
1055: static inline int
1056: bgp_as_path_loopy(struct bgp_proto *p, rta *a)
1057: {
1058: int num = p->cf->allow_local_as + 1;
1059: eattr *e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1060: return (e && (num > 0) && as_path_contains(e->u.ptr, p->local_as, num));
1061: }
1062:
1063: static inline int
1064: bgp_originator_id_loopy(struct bgp_proto *p, rta *a)
1065: {
1066: eattr *e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
1067: return (e && (e->u.data == p->local_id));
1068: }
1069:
1070: static inline int
1071: bgp_cluster_list_loopy(struct bgp_proto *p, rta *a)
1072: {
1073: eattr *e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
1074: return (e && p->rr_client && int_set_contains(e->u.ptr, p->rr_cluster_id));
1075: }
1076:
1077:
1078: static inline void
1079: bgp_path_prepend(rte *e, ea_list **attrs, struct linpool *pool, u32 as)
1080: {
1081: eattr *a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1082: bgp_attach_attr(attrs, pool, BA_AS_PATH, (uintptr_t) as_path_prepend(pool, a->u.ptr, as));
1083: }
1084:
1085: static inline void
1086: bgp_cluster_list_prepend(rte *e, ea_list **attrs, struct linpool *pool, u32 cid)
1087: {
1088: eattr *a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
1089: bgp_attach_attr(attrs, pool, BA_CLUSTER_LIST, (uintptr_t) int_set_prepend(pool, a ? a->u.ptr : NULL, cid));
1090: }
1091:
1092: static int
1093: bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool, int rr)
1094: {
1095: eattr *a;
1096:
1097: if (!p->is_internal && !p->rs_client)
1098: {
1099: bgp_path_prepend(e, attrs, pool, p->local_as);
1100:
1101: /* The MULTI_EXIT_DISC attribute received from a neighboring AS MUST NOT be
1102: * propagated to other neighboring ASes.
1103: * Perhaps it would be better to undefine it.
1104: */
1105: a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
1106: if (a)
1107: bgp_attach_attr(attrs, pool, BA_MULTI_EXIT_DISC, 0);
1108: }
1109:
1110: /* iBGP -> keep next_hop, eBGP multi-hop -> use source_addr,
1111: * eBGP single-hop -> keep next_hop if on the same iface.
1112: * If the next_hop is zero (i.e. link-local), keep only if on the same iface.
1113: *
1114: * Note that same-iface-check uses iface from route, which is based on gw.
1115: */
1116: a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP));
1117: if (a && !p->cf->next_hop_self &&
1118: (p->cf->next_hop_keep ||
1119: (p->is_internal && ipa_nonzero(*((ip_addr *) a->u.ptr->data))) ||
1120: (p->neigh && (e->attrs->iface == p->neigh->iface))))
1121: {
1122: /* Leave the original next hop attribute, will check later where does it point */
1123: }
1124: else
1125: {
1126: /* Need to create new one */
1127: byte *b = bgp_attach_attr_wa(attrs, pool, BA_NEXT_HOP, NEXT_HOP_LENGTH);
1128: set_next_hop(b, p->source_addr);
1129: }
1130:
1131: if (rr)
1132: {
1133: /* Handling route reflection, RFC 4456 */
1134: struct bgp_proto *src = (struct bgp_proto *) e->attrs->src->proto;
1135:
1136: a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
1137: if (!a)
1138: bgp_attach_attr(attrs, pool, BA_ORIGINATOR_ID, src->remote_id);
1139:
1140: /* We attach proper cluster ID according to whether the route is entering or leaving the cluster */
1141: bgp_cluster_list_prepend(e, attrs, pool, src->rr_client ? src->rr_cluster_id : p->rr_cluster_id);
1142:
1143: /* Two RR clients with different cluster ID, hmmm */
1144: if (src->rr_client && p->rr_client && (src->rr_cluster_id != p->rr_cluster_id))
1145: bgp_cluster_list_prepend(e, attrs, pool, p->rr_cluster_id);
1146: }
1147:
1148: return 0; /* Leave decision to the filters */
1149: }
1150:
1151: static int
1152: bgp_community_filter(struct bgp_proto *p, rte *e)
1153: {
1154: eattr *a;
1155: struct adata *d;
1156:
1157: /* Check if we aren't forbidden to export the route by communities */
1158: a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_COMMUNITY));
1159: if (a)
1160: {
1161: d = a->u.ptr;
1162: if (int_set_contains(d, BGP_COMM_NO_ADVERTISE))
1163: {
1164: DBG("\tNO_ADVERTISE\n");
1165: return 1;
1166: }
1167: if (!p->is_internal &&
1168: (int_set_contains(d, BGP_COMM_NO_EXPORT) ||
1169: int_set_contains(d, BGP_COMM_NO_EXPORT_SUBCONFED)))
1170: {
1171: DBG("\tNO_EXPORT\n");
1172: return 1;
1173: }
1174: }
1175:
1176: return 0;
1177: }
1178:
1179: int
1180: bgp_import_control(struct proto *P, rte **new, ea_list **attrs, struct linpool *pool)
1181: {
1182: rte *e = *new;
1183: struct bgp_proto *p = (struct bgp_proto *) P;
1184: struct bgp_proto *new_bgp = (e->attrs->src->proto->proto == &proto_bgp) ?
1185: (struct bgp_proto *) e->attrs->src->proto : NULL;
1186:
1187: if (p == new_bgp) /* Poison reverse updates */
1188: return -1;
1189: if (new_bgp)
1190: {
1191: /* We should check here for cluster list loop, because the receiving BGP instance
1192: might have different cluster ID */
1193: if (bgp_cluster_list_loopy(p, e->attrs))
1194: return -1;
1195:
1196: if (p->cf->interpret_communities && bgp_community_filter(p, e))
1197: return -1;
1198:
1199: if (p->local_as == new_bgp->local_as && p->is_internal && new_bgp->is_internal)
1200: {
1201: /* Redistribution of internal routes with IBGP */
1202: if (p->rr_client || new_bgp->rr_client)
1203: /* Route reflection, RFC 4456 */
1204: return bgp_update_attrs(p, e, attrs, pool, 1);
1205: else
1206: return -1;
1207: }
1208: else
1209: return bgp_update_attrs(p, e, attrs, pool, 0);
1210: }
1211: else
1212: return bgp_create_attrs(p, e, attrs, pool);
1213: }
1214:
1215: static inline u32
1216: bgp_get_neighbor(rte *r)
1217: {
1218: eattr *e = ea_find(r->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1219: u32 as;
1220:
1221: if (e && as_path_get_first(e->u.ptr, &as))
1222: return as;
1223: else
1224: return ((struct bgp_proto *) r->attrs->src->proto)->remote_as;
1225: }
1226:
1227: static inline int
1228: rte_resolvable(rte *rt)
1229: {
1230: int rd = rt->attrs->dest;
1231: return (rd == RTD_ROUTER) || (rd == RTD_DEVICE) || (rd == RTD_MULTIPATH);
1232: }
1233:
1234: int
1235: bgp_rte_better(rte *new, rte *old)
1236: {
1237: struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->src->proto;
1238: struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->src->proto;
1239: eattr *x, *y;
1240: u32 n, o;
1241:
1242: /* Skip suppressed routes (see bgp_rte_recalculate()) */
1243: n = new->u.bgp.suppressed;
1244: o = old->u.bgp.suppressed;
1245: if (n > o)
1246: return 0;
1247: if (n < o)
1248: return 1;
1249:
1250: /* RFC 4271 9.1.2.1. Route resolvability test */
1251: n = rte_resolvable(new);
1252: o = rte_resolvable(old);
1253: if (n > o)
1254: return 1;
1255: if (n < o)
1256: return 0;
1257:
1258: /* Start with local preferences */
1259: x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
1260: y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
1261: n = x ? x->u.data : new_bgp->cf->default_local_pref;
1262: o = y ? y->u.data : old_bgp->cf->default_local_pref;
1263: if (n > o)
1264: return 1;
1265: if (n < o)
1266: return 0;
1267:
1268: /* RFC 4271 9.1.2.2. a) Use AS path lengths */
1269: if (new_bgp->cf->compare_path_lengths || old_bgp->cf->compare_path_lengths)
1270: {
1271: x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1272: y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1273: n = x ? as_path_getlen(x->u.ptr) : AS_PATH_MAXLEN;
1274: o = y ? as_path_getlen(y->u.ptr) : AS_PATH_MAXLEN;
1275: if (n < o)
1276: return 1;
1277: if (n > o)
1278: return 0;
1279: }
1280:
1281: /* RFC 4271 9.1.2.2. b) Use origins */
1282: x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
1283: y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
1284: n = x ? x->u.data : ORIGIN_INCOMPLETE;
1285: o = y ? y->u.data : ORIGIN_INCOMPLETE;
1286: if (n < o)
1287: return 1;
1288: if (n > o)
1289: return 0;
1290:
1291: /* RFC 4271 9.1.2.2. c) Compare MED's */
1292: /* Proper RFC 4271 path selection cannot be interpreted as finding
1293: * the best path in some ordering. It is implemented partially in
1294: * bgp_rte_recalculate() when deterministic_med option is
1295: * active. Without that option, the behavior is just an
1296: * approximation, which in specific situations may lead to
1297: * persistent routing loops, because it is nondeterministic - it
1298: * depends on the order in which routes appeared. But it is also the
1299: * same behavior as used by default in Cisco routers, so it is
1300: * probably not a big issue.
1301: */
1302: if (new_bgp->cf->med_metric || old_bgp->cf->med_metric ||
1303: (bgp_get_neighbor(new) == bgp_get_neighbor(old)))
1304: {
1305: x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
1306: y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
1307: n = x ? x->u.data : new_bgp->cf->default_med;
1308: o = y ? y->u.data : old_bgp->cf->default_med;
1309: if (n < o)
1310: return 1;
1311: if (n > o)
1312: return 0;
1313: }
1314:
1315: /* RFC 4271 9.1.2.2. d) Prefer external peers */
1316: if (new_bgp->is_internal > old_bgp->is_internal)
1317: return 0;
1318: if (new_bgp->is_internal < old_bgp->is_internal)
1319: return 1;
1320:
1321: /* RFC 4271 9.1.2.2. e) Compare IGP metrics */
1322: n = new_bgp->cf->igp_metric ? new->attrs->igp_metric : 0;
1323: o = old_bgp->cf->igp_metric ? old->attrs->igp_metric : 0;
1324: if (n < o)
1325: return 1;
1326: if (n > o)
1327: return 0;
1328:
1329: /* RFC 4271 9.1.2.2. f) Compare BGP identifiers */
1330: /* RFC 4456 9. a) Use ORIGINATOR_ID instead of local neighor ID */
1331: x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
1332: y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
1333: n = x ? x->u.data : new_bgp->remote_id;
1334: o = y ? y->u.data : old_bgp->remote_id;
1335:
1336: /* RFC 5004 - prefer older routes */
1337: /* (if both are external and from different peer) */
1338: if ((new_bgp->cf->prefer_older || old_bgp->cf->prefer_older) &&
1339: !new_bgp->is_internal && n != o)
1340: return 0;
1341:
1342: /* rest of RFC 4271 9.1.2.2. f) */
1343: if (n < o)
1344: return 1;
1345: if (n > o)
1346: return 0;
1347:
1348: /* RFC 4456 9. b) Compare cluster list lengths */
1349: x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
1350: y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
1351: n = x ? int_set_get_size(x->u.ptr) : 0;
1352: o = y ? int_set_get_size(y->u.ptr) : 0;
1353: if (n < o)
1354: return 1;
1355: if (n > o)
1356: return 0;
1357:
1358: /* RFC 4271 9.1.2.2. g) Compare peer IP adresses */
1359: return (ipa_compare(new_bgp->cf->remote_ip, old_bgp->cf->remote_ip) < 0);
1360: }
1361:
1362:
1363: int
1364: bgp_rte_mergable(rte *pri, rte *sec)
1365: {
1366: struct bgp_proto *pri_bgp = (struct bgp_proto *) pri->attrs->src->proto;
1367: struct bgp_proto *sec_bgp = (struct bgp_proto *) sec->attrs->src->proto;
1368: eattr *x, *y;
1369: u32 p, s;
1370:
1371: /* Skip suppressed routes (see bgp_rte_recalculate()) */
1372: if (pri->u.bgp.suppressed != sec->u.bgp.suppressed)
1373: return 0;
1374:
1375: /* RFC 4271 9.1.2.1. Route resolvability test */
1376: if (!rte_resolvable(sec))
1377: return 0;
1378:
1379: /* Start with local preferences */
1380: x = ea_find(pri->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
1381: y = ea_find(sec->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF));
1382: p = x ? x->u.data : pri_bgp->cf->default_local_pref;
1383: s = y ? y->u.data : sec_bgp->cf->default_local_pref;
1384: if (p != s)
1385: return 0;
1386:
1387: /* RFC 4271 9.1.2.2. a) Use AS path lengths */
1388: if (pri_bgp->cf->compare_path_lengths || sec_bgp->cf->compare_path_lengths)
1389: {
1390: x = ea_find(pri->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1391: y = ea_find(sec->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1392: p = x ? as_path_getlen(x->u.ptr) : AS_PATH_MAXLEN;
1393: s = y ? as_path_getlen(y->u.ptr) : AS_PATH_MAXLEN;
1394:
1395: if (p != s)
1396: return 0;
1397:
1398: // if (DELTA(p, s) > pri_bgp->cf->relax_multipath)
1399: // return 0;
1400: }
1401:
1402: /* RFC 4271 9.1.2.2. b) Use origins */
1403: x = ea_find(pri->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
1404: y = ea_find(sec->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
1405: p = x ? x->u.data : ORIGIN_INCOMPLETE;
1406: s = y ? y->u.data : ORIGIN_INCOMPLETE;
1407: if (p != s)
1408: return 0;
1409:
1410: /* RFC 4271 9.1.2.2. c) Compare MED's */
1411: if (pri_bgp->cf->med_metric || sec_bgp->cf->med_metric ||
1412: (bgp_get_neighbor(pri) == bgp_get_neighbor(sec)))
1413: {
1414: x = ea_find(pri->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
1415: y = ea_find(sec->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
1416: p = x ? x->u.data : pri_bgp->cf->default_med;
1417: s = y ? y->u.data : sec_bgp->cf->default_med;
1418: if (p != s)
1419: return 0;
1420: }
1421:
1422: /* RFC 4271 9.1.2.2. d) Prefer external peers */
1423: if (pri_bgp->is_internal != sec_bgp->is_internal)
1424: return 0;
1425:
1426: /* RFC 4271 9.1.2.2. e) Compare IGP metrics */
1427: p = pri_bgp->cf->igp_metric ? pri->attrs->igp_metric : 0;
1428: s = sec_bgp->cf->igp_metric ? sec->attrs->igp_metric : 0;
1429: if (p != s)
1430: return 0;
1431:
1432: /* Remaining criteria are ignored */
1433:
1434: return 1;
1435: }
1436:
1437:
1438:
1439: static inline int
1440: same_group(rte *r, u32 lpref, u32 lasn)
1441: {
1442: return (r->pref == lpref) && (bgp_get_neighbor(r) == lasn);
1443: }
1444:
1445: static inline int
1446: use_deterministic_med(rte *r)
1447: {
1448: struct proto *P = r->attrs->src->proto;
1449: return (P->proto == &proto_bgp) && ((struct bgp_proto *) P)->cf->deterministic_med;
1450: }
1451:
1452: int
1453: bgp_rte_recalculate(rtable *table, net *net, rte *new, rte *old, rte *old_best)
1454: {
1455: rte *r, *s;
1456: rte *key = new ? new : old;
1457: u32 lpref = key->pref;
1458: u32 lasn = bgp_get_neighbor(key);
1459: int old_is_group_best = 0;
1460:
1461: /*
1462: * Proper RFC 4271 path selection is a bit complicated, it cannot be
1463: * implemented just by rte_better(), because it is not a linear
1464: * ordering. But it can be splitted to two levels, where the lower
1465: * level chooses the best routes in each group of routes from the
1466: * same neighboring AS and higher level chooses the best route (with
1467: * a slightly different ordering) between the best-in-group routes.
1468: *
1469: * When deterministic_med is disabled, we just ignore this issue and
1470: * choose the best route by bgp_rte_better() alone. If enabled, the
1471: * lower level of the route selection is done here (for the group
1472: * to which the changed route belongs), all routes in group are
1473: * marked as suppressed, just chosen best-in-group is not.
1474: *
1475: * Global best route selection then implements higher level by
1476: * choosing between non-suppressed routes (as they are always
1477: * preferred over suppressed routes). Routes from BGP protocols
1478: * that do not set deterministic_med are just never suppressed. As
1479: * they do not participate in the lower level selection, it is OK
1480: * that this fn is not called for them.
1481: *
1482: * The idea is simple, the implementation is more problematic,
1483: * mostly because of optimizations in rte_recalculate() that
1484: * avoids full recalculation in most cases.
1485: *
1486: * We can assume that at least one of new, old is non-NULL and both
1487: * are from the same protocol with enabled deterministic_med. We
1488: * group routes by both neighbor AS (lasn) and preference (lpref),
1489: * because bgp_rte_better() does not handle preference itself.
1490: */
1491:
1492: /* If new and old are from different groups, we just process that
1493: as two independent events */
1494: if (new && old && !same_group(old, lpref, lasn))
1495: {
1496: int i1, i2;
1497: i1 = bgp_rte_recalculate(table, net, NULL, old, old_best);
1498: i2 = bgp_rte_recalculate(table, net, new, NULL, old_best);
1499: return i1 || i2;
1500: }
1501:
1502: /*
1503: * We could find the best-in-group and then make some shortcuts like
1504: * in rte_recalculate, but as we would have to walk through all
1505: * net->routes just to find it, it is probably not worth. So we
1506: * just have two simpler fast cases that use just the old route.
1507: * We also set suppressed flag to avoid using it in bgp_rte_better().
1508: */
1509:
1510: if (new)
1511: new->u.bgp.suppressed = 1;
1512:
1513: if (old)
1514: {
1515: old_is_group_best = !old->u.bgp.suppressed;
1516: old->u.bgp.suppressed = 1;
1517: int new_is_better = new && bgp_rte_better(new, old);
1518:
1519: /* The first case - replace not best with worse (or remove not best) */
1520: if (!old_is_group_best && !new_is_better)
1521: return 0;
1522:
1523: /* The second case - replace the best with better */
1524: if (old_is_group_best && new_is_better)
1525: {
1526: /* new is best-in-group, the see discussion below - this is
1527: a special variant of NBG && OBG. From OBG we can deduce
1528: that same_group(old_best) iff (old == old_best) */
1529: new->u.bgp.suppressed = 0;
1530: return (old == old_best);
1531: }
1532: }
1533:
1534: /* The default case - find a new best-in-group route */
1535: r = new; /* new may not be in the list */
1536: for (s=net->routes; rte_is_valid(s); s=s->next)
1537: if (use_deterministic_med(s) && same_group(s, lpref, lasn))
1538: {
1539: s->u.bgp.suppressed = 1;
1540: if (!r || bgp_rte_better(s, r))
1541: r = s;
1542: }
1543:
1544: /* Simple case - the last route in group disappears */
1545: if (!r)
1546: return 0;
1547:
1548: /* Found best-in-group */
1549: r->u.bgp.suppressed = 0;
1550:
1551: /*
1552: * There are generally two reasons why we have to force
1553: * recalculation (return 1): First, the new route may be wrongfully
1554: * chosen to be the best in the first case check in
1555: * rte_recalculate(), this may happen only if old_best is from the
1556: * same group. Second, another (different than new route)
1557: * best-in-group is chosen and that may be the proper best (although
1558: * rte_recalculate() without ignore that possibility).
1559: *
1560: * There are three possible cases according to whether the old route
1561: * was the best in group (OBG, stored in old_is_group_best) and
1562: * whether the new route is the best in group (NBG, tested by r == new).
1563: * These cases work even if old or new is NULL.
1564: *
1565: * NBG -> new is a possible candidate for the best route, so we just
1566: * check for the first reason using same_group().
1567: *
1568: * !NBG && OBG -> Second reason applies, return 1
1569: *
1570: * !NBG && !OBG -> Best in group does not change, old != old_best,
1571: * rte_better(new, old_best) is false and therefore
1572: * the first reason does not apply, return 0
1573: */
1574:
1575: if (r == new)
1576: return old_best && same_group(old_best, lpref, lasn);
1577: else
1578: return old_is_group_best;
1579: }
1580:
1581: static struct adata *
1582: bgp_aggregator_convert_to_new(struct adata *old, struct linpool *pool)
1583: {
1584: struct adata *newa = lp_alloc(pool, sizeof(struct adata) + 8);
1585: newa->length = 8;
1586: aggregator_convert_to_new(old, newa->data);
1587: return newa;
1588: }
1589:
1590:
1591: /* Take last req_as ASNs from path old2 (in 2B format), convert to 4B format
1592: * and append path old4 (in 4B format).
1593: */
1594: static struct adata *
1595: bgp_merge_as_paths(struct adata *old2, struct adata *old4, int req_as, struct linpool *pool)
1596: {
1597: byte buf[old2->length * 2];
1598:
1599: int ol = as_path_convert_to_new(old2, buf, req_as);
1600: int nl = ol + (old4 ? old4->length : 0);
1601:
1602: struct adata *newa = lp_alloc(pool, sizeof(struct adata) + nl);
1603: newa->length = nl;
1604: memcpy(newa->data, buf, ol);
1605: if (old4) memcpy(newa->data + ol, old4->data, old4->length);
1606:
1607: return newa;
1608: }
1609:
1610: static int
1611: as4_aggregator_valid(struct adata *aggr)
1612: {
1613: return aggr->length == 8;
1614: }
1615:
1616:
1617: /* Reconstruct 4B AS_PATH and AGGREGATOR according to RFC 4893 4.2.3 */
1618: static void
1619: bgp_reconstruct_4b_atts(struct bgp_proto *p, rta *a, struct linpool *pool)
1620: {
1621: eattr *p2 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1622: eattr *p4 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS4_PATH));
1623: eattr *a2 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AGGREGATOR));
1624: eattr *a4 =ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS4_AGGREGATOR));
1625: int a4_removed = 0;
1626:
1627: if (a4 && !as4_aggregator_valid(a4->u.ptr))
1628: {
1629: log(L_WARN "%s: AS4_AGGREGATOR attribute is invalid, skipping attribute", p->p.name);
1630: a4 = NULL;
1631: a4_removed = 1;
1632: }
1633:
1634: if (a2)
1635: {
1636: u32 a2_as = get_u16(a2->u.ptr->data);
1637:
1638: if (a4)
1639: {
1640: if (a2_as != AS_TRANS)
1641: {
1642: /* Routes were aggregated by old router and therefore AS4_PATH
1643: * and AS4_AGGREGATOR is invalid
1644: *
1645: * Convert AS_PATH and AGGREGATOR to 4B format and finish.
1646: */
1647:
1648: a2->u.ptr = bgp_aggregator_convert_to_new(a2->u.ptr, pool);
1649: p2->u.ptr = bgp_merge_as_paths(p2->u.ptr, NULL, AS_PATH_MAXLEN, pool);
1650:
1651: return;
1652: }
1653: else
1654: {
1655: /* Common case, use AS4_AGGREGATOR attribute */
1656: a2->u.ptr = a4->u.ptr;
1657: }
1658: }
1659: else
1660: {
1661: /* Common case, use old AGGREGATOR attribute */
1662: a2->u.ptr = bgp_aggregator_convert_to_new(a2->u.ptr, pool);
1663:
1664: if ((a2_as == AS_TRANS) && !a4_removed)
1665: log(L_WARN "%s: AGGREGATOR attribute contain AS_TRANS, but AS4_AGGREGATOR is missing", p->p.name);
1666: }
1667: }
1668: else
1669: if (a4)
1670: log(L_WARN "%s: AS4_AGGREGATOR attribute received, but AGGREGATOR attribute is missing", p->p.name);
1671:
1672: int p2_len = as_path_getlen_int(p2->u.ptr, 2);
1673: int p4_len = p4 ? validate_as4_path(p, p4->u.ptr) : -1;
1674:
1675: if (p4 && (p4_len < 0))
1676: log(L_WARN "%s: AS4_PATH attribute is malformed, skipping attribute", p->p.name);
1677:
1678: if ((p4_len <= 0) || (p2_len < p4_len))
1679: p2->u.ptr = bgp_merge_as_paths(p2->u.ptr, NULL, AS_PATH_MAXLEN, pool);
1680: else
1681: p2->u.ptr = bgp_merge_as_paths(p2->u.ptr, p4->u.ptr, p2_len - p4_len, pool);
1682: }
1683:
1684: static void
1685: bgp_remove_as4_attrs(struct bgp_proto *p, rta *a)
1686: {
1687: unsigned id1 = EA_CODE(EAP_BGP, BA_AS4_PATH);
1688: unsigned id2 = EA_CODE(EAP_BGP, BA_AS4_AGGREGATOR);
1689: ea_list **el = &(a->eattrs);
1690:
1691: /* We know that ea_lists constructed in bgp_decode attrs have one attribute per ea_list struct */
1692: while (*el != NULL)
1693: {
1694: unsigned fid = (*el)->attrs[0].id;
1695:
1696: if ((fid == id1) || (fid == id2))
1697: {
1698: *el = (*el)->next;
1699: if (p->as4_session)
1700: log(L_WARN "%s: Unexpected AS4_* attributes received", p->p.name);
1701: }
1702: else
1703: el = &((*el)->next);
1704: }
1705: }
1706:
1707: /**
1708: * bgp_decode_attrs - check and decode BGP attributes
1709: * @conn: connection
1710: * @attr: start of attribute block
1711: * @len: length of attribute block
1712: * @pool: linear pool to make all the allocations in
1713: * @mandatory: 1 iff presence of mandatory attributes has to be checked
1714: *
1715: * This function takes a BGP attribute block (a part of an Update message), checks
1716: * its consistency and converts it to a list of BIRD route attributes represented
1717: * by a &rta.
1718: */
1719: struct rta *
1720: bgp_decode_attrs(struct bgp_conn *conn, byte *attr, uint len, struct linpool *pool, int mandatory)
1721: {
1722: struct bgp_proto *bgp = conn->bgp;
1723: rta *a = lp_alloc(pool, sizeof(struct rta));
1724: uint flags, code, l, i, type;
1725: int errcode;
1726: byte *z, *attr_start;
1727: byte seen[256/8];
1728: ea_list *ea;
1729: struct adata *ad;
1730: int withdraw = 0;
1731:
1732: bzero(a, sizeof(rta));
1733: a->source = RTS_BGP;
1734: a->scope = SCOPE_UNIVERSE;
1735: a->cast = RTC_UNICAST;
1736: /* a->dest = RTD_ROUTER; -- set in bgp_set_next_hop() */
1737: a->from = bgp->cf->remote_ip;
1738:
1739: /* Parse the attributes */
1740: bzero(seen, sizeof(seen));
1741: DBG("BGP: Parsing attributes\n");
1742: while (len)
1743: {
1744: if (len < 2)
1745: goto malformed;
1746: attr_start = attr;
1747: flags = *attr++;
1748: code = *attr++;
1749: len -= 2;
1750: if (flags & BAF_EXT_LEN)
1751: {
1752: if (len < 2)
1753: goto malformed;
1754: l = get_u16(attr);
1755: attr += 2;
1756: len -= 2;
1757: }
1758: else
1759: {
1760: if (len < 1)
1761: goto malformed;
1762: l = *attr++;
1763: len--;
1764: }
1765: if (l > len)
1766: goto malformed;
1767: len -= l;
1768: z = attr;
1769: attr += l;
1770: DBG("Attr %02x %02x %d\n", code, flags, l);
1771: if (seen[code/8] & (1 << (code%8)))
1772: goto malformed;
1773: if (ATTR_KNOWN(code))
1774: {
1775: struct attr_desc *desc = &bgp_attr_table[code];
1776: if (desc->expected_length >= 0 && desc->expected_length != (int) l)
1777: { errcode = 5; goto err; }
1778: if ((desc->expected_flags ^ flags) & (BAF_OPTIONAL | BAF_TRANSITIVE))
1779: { errcode = 4; goto err; }
1780: if (!desc->allow_in_ebgp && !bgp->is_internal)
1781: continue;
1782: if (desc->validate)
1783: {
1784: errcode = desc->validate(bgp, z, l);
1785: if (errcode > 0)
1786: goto err;
1787: if (errcode == IGNORE)
1788: continue;
1789: if (errcode <= WITHDRAW)
1790: {
1791: log(L_WARN "%s: Attribute %s is malformed, withdrawing update",
1792: bgp->p.name, desc->name);
1793: withdraw = 1;
1794: }
1795: }
1796: else if (code == BA_AS_PATH)
1797: {
1798: /* Special case as it might also trim the attribute */
1799: if (validate_as_path(bgp, z, &l) < 0)
1800: { errcode = 11; goto err; }
1801: }
1802: type = desc->type;
1803: }
1804: else /* Unknown attribute */
1805: {
1806: if (!(flags & BAF_OPTIONAL))
1807: { errcode = 2; goto err; }
1808: type = EAF_TYPE_OPAQUE;
1809: }
1810:
1811: // Only OPTIONAL and TRANSITIVE attributes may have non-zero PARTIAL flag
1812: // if (!((flags & BAF_OPTIONAL) && (flags & BAF_TRANSITIVE)) && (flags & BAF_PARTIAL))
1813: // { errcode = 4; goto err; }
1814:
1815: seen[code/8] |= (1 << (code%8));
1816: ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
1817: ea->next = a->eattrs;
1818: a->eattrs = ea;
1819: ea->flags = 0;
1820: ea->count = 1;
1821: ea->attrs[0].id = EA_CODE(EAP_BGP, code);
1822: ea->attrs[0].flags = flags;
1823: ea->attrs[0].type = type;
1824: if (type & EAF_EMBEDDED)
1825: ad = NULL;
1826: else
1827: {
1828: ad = lp_alloc(pool, sizeof(struct adata) + l);
1829: ea->attrs[0].u.ptr = ad;
1830: ad->length = l;
1831: memcpy(ad->data, z, l);
1832: }
1833: switch (type)
1834: {
1835: case EAF_TYPE_ROUTER_ID:
1836: case EAF_TYPE_INT:
1837: if (l == 1)
1838: ea->attrs[0].u.data = *z;
1839: else
1840: ea->attrs[0].u.data = get_u32(z);
1841: break;
1842: case EAF_TYPE_IP_ADDRESS:
1843: ipa_ntoh(*(ip_addr *)ad->data);
1844: break;
1845: case EAF_TYPE_INT_SET:
1846: case EAF_TYPE_LC_SET:
1847: case EAF_TYPE_EC_SET:
1848: {
1849: u32 *z = (u32 *) ad->data;
1850: for(i=0; i<ad->length/4; i++)
1851: z[i] = ntohl(z[i]);
1852: break;
1853: }
1854: }
1855: }
1856:
1857: if (withdraw)
1858: goto withdraw;
1859:
1860: #ifdef IPV6
1861: /* If we received MP_REACH_NLRI we should check mandatory attributes */
1862: if (bgp->mp_reach_len != 0)
1863: mandatory = 1;
1864: #endif
1865:
1866: /* If there is no (reachability) NLRI, we should exit now */
1867: if (! mandatory)
1868: return a;
1869:
1870: /* Check if all mandatory attributes are present */
1871: for(i=0; i < ARRAY_SIZE(bgp_mandatory_attrs); i++)
1872: {
1873: code = bgp_mandatory_attrs[i];
1874: if (!(seen[code/8] & (1 << (code%8))))
1875: {
1876: bgp_error(conn, 3, 3, &bgp_mandatory_attrs[i], 1);
1877: return NULL;
1878: }
1879: }
1880:
1881: /* When receiving attributes from non-AS4-aware BGP speaker,
1882: * we have to reconstruct 4B AS_PATH and AGGREGATOR attributes
1883: */
1884: if (! bgp->as4_session)
1885: bgp_reconstruct_4b_atts(bgp, a, pool);
1886:
1887: bgp_remove_as4_attrs(bgp, a);
1888:
1889: /* If the AS path attribute contains our AS, reject the routes */
1890: if (bgp_as_path_loopy(bgp, a))
1891: goto withdraw;
1892:
1893: /* Two checks for IBGP loops caused by route reflection, RFC 4456 */
1894: if (bgp_originator_id_loopy(bgp, a) ||
1895: bgp_cluster_list_loopy(bgp, a))
1896: goto withdraw;
1897:
1898: /* If there's no local preference, define one */
1899: if (!(seen[0] & (1 << BA_LOCAL_PREF)))
1900: bgp_attach_attr(&a->eattrs, pool, BA_LOCAL_PREF, bgp->cf->default_local_pref);
1901:
1902: return a;
1903:
1904: withdraw:
1905: return NULL;
1906:
1907: malformed:
1908: bgp_error(conn, 3, 1, NULL, 0);
1909: return NULL;
1910:
1911: err:
1912: bgp_error(conn, 3, errcode, attr_start, z+l-attr_start);
1913: return NULL;
1914: }
1915:
1916: int
1917: bgp_get_attr(eattr *a, byte *buf, int buflen)
1918: {
1919: uint i = EA_ID(a->id);
1920: struct attr_desc *d;
1921: int len;
1922:
1923: if (ATTR_KNOWN(i))
1924: {
1925: d = &bgp_attr_table[i];
1926: len = bsprintf(buf, "%s", d->name);
1927: buf += len;
1928: if (d->format)
1929: {
1930: *buf++ = ':';
1931: *buf++ = ' ';
1932: d->format(a, buf, buflen - len - 2);
1933: return GA_FULL;
1934: }
1935: return GA_NAME;
1936: }
1937: bsprintf(buf, "%02x%s", i, (a->flags & BAF_TRANSITIVE) ? " [t]" : "");
1938: return GA_NAME;
1939: }
1940:
1941: void
1942: bgp_init_bucket_table(struct bgp_proto *p)
1943: {
1944: p->hash_size = 256;
1945: p->hash_limit = p->hash_size * 4;
1946: p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
1947: init_list(&p->bucket_queue);
1948: p->withdraw_bucket = NULL;
1949: // fib_init(&p->prefix_fib, p->p.pool, sizeof(struct bgp_prefix), 0, bgp_init_prefix);
1950: }
1951:
1952: void
1953: bgp_free_bucket_table(struct bgp_proto *p)
1954: {
1955: mb_free(p->bucket_hash);
1956: p->bucket_hash = NULL;
1957:
1958: struct bgp_bucket *b;
1959: WALK_LIST_FIRST(b, p->bucket_queue)
1960: {
1961: rem_node(&b->send_node);
1962: mb_free(b);
1963: }
1964:
1965: mb_free(p->withdraw_bucket);
1966: p->withdraw_bucket = NULL;
1967: }
1968:
1969: void
1970: bgp_get_route_info(rte *e, byte *buf, ea_list *attrs)
1971: {
1972: eattr *p = ea_find(attrs, EA_CODE(EAP_BGP, BA_AS_PATH));
1973: eattr *o = ea_find(attrs, EA_CODE(EAP_BGP, BA_ORIGIN));
1974: u32 origas;
1975:
1976: buf += bsprintf(buf, " (%d", e->pref);
1977:
1978: if (e->u.bgp.suppressed)
1979: buf += bsprintf(buf, "-");
1980:
1981: if (e->attrs->hostentry)
1982: {
1983: if (!rte_resolvable(e))
1984: buf += bsprintf(buf, "/-");
1985: else if (e->attrs->igp_metric >= IGP_METRIC_UNKNOWN)
1986: buf += bsprintf(buf, "/?");
1987: else
1988: buf += bsprintf(buf, "/%d", e->attrs->igp_metric);
1989: }
1990: buf += bsprintf(buf, ") [");
1991:
1992: if (p && as_path_get_last(p->u.ptr, &origas))
1993: buf += bsprintf(buf, "AS%u", origas);
1994: if (o)
1995: buf += bsprintf(buf, "%c", "ie?"[o->u.data]);
1996: strcpy(buf, "]");
1997: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>