Return to attrs.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / proto / bgp |
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: }