]>
Commit | Line | Data |
---|---|---|
1 | /* | |
2 | * BIRD -- BGP Attributes | |
3 | * | |
4 | * (c) 2000 Martin Mares <mj@ucw.cz> | |
5 | * | |
6 | * Can be freely distributed and used under the terms of the GNU GPL. | |
7 | */ | |
8 | ||
9 | #undef LOCAL_DEBUG | |
10 | ||
11 | #include <stdlib.h> | |
12 | ||
13 | #include "nest/bird.h" | |
14 | #include "nest/iface.h" | |
15 | #include "nest/protocol.h" | |
16 | #include "nest/route.h" | |
17 | #include "nest/attrs.h" | |
18 | #include "conf/conf.h" | |
19 | #include "lib/resource.h" | |
20 | #include "lib/string.h" | |
21 | #include "lib/unaligned.h" | |
22 | ||
23 | #include "bgp.h" | |
24 | ||
25 | static byte bgp_mandatory_attrs[] = { BA_ORIGIN, BA_AS_PATH | |
26 | #ifndef IPV6 | |
27 | ,BA_NEXT_HOP | |
28 | #endif | |
29 | }; | |
30 | ||
31 | struct attr_desc { | |
32 | char *name; | |
33 | int expected_length; | |
34 | int expected_flags; | |
35 | int type; | |
36 | int allow_in_ebgp; | |
37 | int (*validate)(struct bgp_proto *p, byte *attr, int len); | |
38 | void (*format)(eattr *ea, byte *buf); | |
39 | }; | |
40 | ||
41 | static int | |
42 | bgp_check_origin(struct bgp_proto *p UNUSED, byte *a UNUSED, int len) | |
43 | { | |
44 | if (len > 2) | |
45 | return 6; | |
46 | return 0; | |
47 | } | |
48 | ||
49 | static void | |
50 | bgp_format_origin(eattr *a, byte *buf) | |
51 | { | |
52 | static char *bgp_origin_names[] = { "IGP", "EGP", "Incomplete" }; | |
53 | ||
54 | bsprintf(buf, bgp_origin_names[a->u.data]); | |
55 | } | |
56 | ||
57 | static int | |
58 | bgp_check_path(struct bgp_proto *p UNUSED, byte *a, int len) | |
59 | { | |
60 | while (len) | |
61 | { | |
62 | DBG("Path segment %02x %02x\n", a[0], a[1]); | |
63 | if (len < 2 || | |
64 | a[0] != AS_PATH_SET && a[0] != AS_PATH_SEQUENCE || | |
65 | 2*a[1] + 2 > len) | |
66 | return 11; | |
67 | len -= 2*a[1] + 2; | |
68 | a += 2*a[1] + 2; | |
69 | } | |
70 | return 0; | |
71 | } | |
72 | ||
73 | static int | |
74 | bgp_check_next_hop(struct bgp_proto *p UNUSED, byte *a, int len) | |
75 | { | |
76 | #ifdef IPV6 | |
77 | return -1; | |
78 | #else | |
79 | ip_addr addr; | |
80 | ||
81 | memcpy(&addr, a, len); | |
82 | ipa_ntoh(addr); | |
83 | if (ipa_classify(addr) & IADDR_HOST) | |
84 | return 0; | |
85 | else | |
86 | return 8; | |
87 | #endif | |
88 | } | |
89 | ||
90 | static int | |
91 | bgp_check_reach_nlri(struct bgp_proto *p UNUSED, byte *a UNUSED, int len UNUSED) | |
92 | { | |
93 | #ifdef IPV6 | |
94 | p->mp_reach_start = a; | |
95 | p->mp_reach_len = len; | |
96 | #endif | |
97 | return -1; | |
98 | } | |
99 | ||
100 | static int | |
101 | bgp_check_unreach_nlri(struct bgp_proto *p UNUSED, byte *a UNUSED, int len UNUSED) | |
102 | { | |
103 | #ifdef IPV6 | |
104 | p->mp_unreach_start = a; | |
105 | p->mp_unreach_len = len; | |
106 | #endif | |
107 | return -1; | |
108 | } | |
109 | ||
110 | static struct attr_desc bgp_attr_table[] = { | |
111 | { NULL, -1, 0, 0, 0, /* Undefined */ | |
112 | NULL, NULL }, | |
113 | { "origin", 1, BAF_TRANSITIVE, EAF_TYPE_INT, 1, /* BA_ORIGIN */ | |
114 | bgp_check_origin, bgp_format_origin }, | |
115 | { "as_path", -1, BAF_TRANSITIVE, EAF_TYPE_AS_PATH, 1, /* BA_AS_PATH */ | |
116 | bgp_check_path, NULL }, | |
117 | { "next_hop", 4, BAF_TRANSITIVE, EAF_TYPE_IP_ADDRESS, 1, /* BA_NEXT_HOP */ | |
118 | bgp_check_next_hop, NULL }, | |
119 | { "med", 4, BAF_OPTIONAL, EAF_TYPE_INT, 0, /* BA_MULTI_EXIT_DISC */ | |
120 | NULL, NULL }, | |
121 | { "local_pref", 4, BAF_TRANSITIVE, EAF_TYPE_INT, 0, /* BA_LOCAL_PREF */ | |
122 | NULL, NULL }, | |
123 | { "atomic_aggr", 0, BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1, /* BA_ATOMIC_AGGR */ | |
124 | NULL, NULL }, | |
125 | { "aggregator", 6, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_OPAQUE, 1, /* BA_AGGREGATOR */ | |
126 | NULL, NULL }, | |
127 | { "community", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_INT_SET, 1, /* BA_COMMUNITY */ | |
128 | NULL, NULL }, | |
129 | { NULL, }, /* BA_ORIGINATOR_ID */ | |
130 | { NULL, }, /* BA_CLUSTER_LIST */ | |
131 | { NULL, }, /* BA_DPA */ | |
132 | { NULL, }, /* BA_ADVERTISER */ | |
133 | { NULL, }, /* BA_RCID_PATH */ | |
134 | { "mp_reach_nlri", -1, BAF_OPTIONAL, EAF_TYPE_OPAQUE, 1, /* BA_MP_REACH_NLRI */ | |
135 | bgp_check_reach_nlri, NULL }, | |
136 | { "mp_unreach_nlri", -1, BAF_OPTIONAL, EAF_TYPE_OPAQUE, 1, /* BA_MP_UNREACH_NLRI */ | |
137 | bgp_check_unreach_nlri, NULL }, | |
138 | }; | |
139 | ||
140 | #define ATTR_KNOWN(code) ((code) < ARRAY_SIZE(bgp_attr_table) && bgp_attr_table[code].name) | |
141 | ||
142 | static byte * | |
143 | bgp_set_attr(eattr *e, struct linpool *pool, unsigned attr, unsigned val) | |
144 | { | |
145 | ASSERT(ATTR_KNOWN(attr)); | |
146 | e->id = EA_CODE(EAP_BGP, attr); | |
147 | e->type = bgp_attr_table[attr].type; | |
148 | e->flags = bgp_attr_table[attr].expected_flags; | |
149 | if (e->type & EAF_EMBEDDED) | |
150 | { | |
151 | e->u.data = val; | |
152 | return NULL; | |
153 | } | |
154 | else | |
155 | { | |
156 | e->u.ptr = lp_alloc(pool, sizeof(struct adata) + val); | |
157 | e->u.ptr->length = val; | |
158 | return e->u.ptr->data; | |
159 | } | |
160 | } | |
161 | ||
162 | byte * | |
163 | bgp_attach_attr(ea_list **to, struct linpool *pool, unsigned attr, unsigned val) | |
164 | { | |
165 | ea_list *a = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr)); | |
166 | a->next = *to; | |
167 | *to = a; | |
168 | a->flags = EALF_SORTED; | |
169 | a->count = 1; | |
170 | return bgp_set_attr(a->attrs, pool, attr, val); | |
171 | } | |
172 | ||
173 | /** | |
174 | * bgp_encode_attrs - encode BGP attributes | |
175 | * @w: buffer | |
176 | * @attrs: a list of extended attributes | |
177 | * @remains: remaining space in the buffer | |
178 | * | |
179 | * The bgp_encode_attrs() function takes a list of extended attributes | |
180 | * and converts it to its BGP representation (a part of an Update message). | |
181 | * | |
182 | * Result: Length of the attribute block generated. | |
183 | */ | |
184 | unsigned int | |
185 | bgp_encode_attrs(byte *w, ea_list *attrs, int remains) | |
186 | { | |
187 | unsigned int i, code, flags; | |
188 | byte *start = w; | |
189 | int len; | |
190 | ||
191 | for(i=0; i<attrs->count; i++) | |
192 | { | |
193 | eattr *a = &attrs->attrs[i]; | |
194 | ASSERT(EA_PROTO(a->id) == EAP_BGP); | |
195 | code = EA_ID(a->id); | |
196 | #ifdef IPV6 | |
197 | /* When talking multiprotocol BGP, the NEXT_HOP attributes are used only temporarily. */ | |
198 | if (code == BA_NEXT_HOP) | |
199 | continue; | |
200 | #endif | |
201 | flags = a->flags & (BAF_OPTIONAL | BAF_TRANSITIVE | BAF_PARTIAL); | |
202 | if (ATTR_KNOWN(code)) | |
203 | { | |
204 | struct attr_desc *desc = &bgp_attr_table[code]; | |
205 | len = desc->expected_length; | |
206 | if (len < 0) | |
207 | { | |
208 | ASSERT(!(a->type & EAF_EMBEDDED)); | |
209 | len = a->u.ptr->length; | |
210 | } | |
211 | } | |
212 | else | |
213 | { | |
214 | ASSERT((a->type & EAF_TYPE_MASK) == EAF_TYPE_OPAQUE); | |
215 | len = a->u.ptr->length; | |
216 | } | |
217 | DBG("\tAttribute %02x (type %02x, %d bytes, flags %02x)\n", code, a->type, len, flags); | |
218 | if (remains < len + 4) | |
219 | { | |
220 | log(L_ERR "BGP: attribute list too long, ignoring the remaining attributes"); | |
221 | break; | |
222 | } | |
223 | if (len < 256) | |
224 | { | |
225 | *w++ = flags; | |
226 | *w++ = code; | |
227 | *w++ = len; | |
228 | remains -= 3; | |
229 | } | |
230 | else | |
231 | { | |
232 | *w++ = flags | BAF_EXT_LEN; | |
233 | *w++ = code; | |
234 | put_u16(w, len); | |
235 | w += 2; | |
236 | remains -= 4; | |
237 | } | |
238 | switch (a->type & EAF_TYPE_MASK) | |
239 | { | |
240 | case EAF_TYPE_INT: | |
241 | case EAF_TYPE_ROUTER_ID: | |
242 | if (len == 4) | |
243 | put_u32(w, a->u.data); | |
244 | else | |
245 | *w = a->u.data; | |
246 | break; | |
247 | case EAF_TYPE_IP_ADDRESS: | |
248 | { | |
249 | ip_addr ip = *(ip_addr *)a->u.ptr->data; | |
250 | ipa_hton(ip); | |
251 | memcpy(w, &ip, len); | |
252 | break; | |
253 | } | |
254 | case EAF_TYPE_INT_SET: | |
255 | { | |
256 | u32 *z = (u32 *)a->u.ptr->data; | |
257 | int i; | |
258 | for(i=0; i<len; i+=4) | |
259 | put_u32(w+i, *z++); | |
260 | break; | |
261 | } | |
262 | case EAF_TYPE_OPAQUE: | |
263 | case EAF_TYPE_AS_PATH: | |
264 | memcpy(w, a->u.ptr->data, len); | |
265 | break; | |
266 | default: | |
267 | bug("bgp_encode_attrs: unknown attribute type %02x", a->type); | |
268 | } | |
269 | remains -= len; | |
270 | w += len; | |
271 | } | |
272 | return w - start; | |
273 | } | |
274 | ||
275 | static void | |
276 | bgp_init_prefix(struct fib_node *N) | |
277 | { | |
278 | struct bgp_prefix *p = (struct bgp_prefix *) N; | |
279 | p->bucket_node.next = NULL; | |
280 | } | |
281 | ||
282 | static int | |
283 | bgp_compare_u32(const u32 *x, const u32 *y) | |
284 | { | |
285 | return (*x < *y) ? -1 : (*x > *y) ? 1 : 0; | |
286 | } | |
287 | ||
288 | static void | |
289 | bgp_normalize_set(u32 *dest, u32 *src, unsigned cnt) | |
290 | { | |
291 | memcpy(dest, src, sizeof(u32) * cnt); | |
292 | qsort(dest, cnt, sizeof(u32), (int(*)(const void *, const void *)) bgp_compare_u32); | |
293 | } | |
294 | ||
295 | static void | |
296 | bgp_rehash_buckets(struct bgp_proto *p) | |
297 | { | |
298 | struct bgp_bucket **old = p->bucket_hash; | |
299 | struct bgp_bucket **new; | |
300 | unsigned oldn = p->hash_size; | |
301 | unsigned i, e, mask; | |
302 | struct bgp_bucket *b; | |
303 | ||
304 | p->hash_size = p->hash_limit; | |
305 | DBG("BGP: Rehashing bucket table from %d to %d\n", oldn, p->hash_size); | |
306 | p->hash_limit *= 4; | |
307 | if (p->hash_limit >= 65536) | |
308 | p->hash_limit = ~0; | |
309 | new = p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *)); | |
310 | mask = p->hash_size - 1; | |
311 | for (i=0; i<oldn; i++) | |
312 | while (b = old[i]) | |
313 | { | |
314 | old[i] = b->hash_next; | |
315 | e = b->hash & mask; | |
316 | b->hash_next = new[e]; | |
317 | if (b->hash_next) | |
318 | b->hash_next->hash_prev = b; | |
319 | b->hash_prev = NULL; | |
320 | new[e] = b; | |
321 | } | |
322 | mb_free(old); | |
323 | } | |
324 | ||
325 | static struct bgp_bucket * | |
326 | bgp_new_bucket(struct bgp_proto *p, ea_list *new, unsigned hash) | |
327 | { | |
328 | struct bgp_bucket *b; | |
329 | unsigned ea_size = sizeof(ea_list) + new->count * sizeof(eattr); | |
330 | unsigned ea_size_aligned = BIRD_ALIGN(ea_size, CPU_STRUCT_ALIGN); | |
331 | unsigned size = sizeof(struct bgp_bucket) + ea_size; | |
332 | unsigned i; | |
333 | byte *dest; | |
334 | unsigned index = hash & (p->hash_size - 1); | |
335 | ||
336 | /* Gather total size of non-inline attributes */ | |
337 | for (i=0; i<new->count; i++) | |
338 | { | |
339 | eattr *a = &new->attrs[i]; | |
340 | if (!(a->type & EAF_EMBEDDED)) | |
341 | size += BIRD_ALIGN(sizeof(struct adata) + a->u.ptr->length, CPU_STRUCT_ALIGN); | |
342 | } | |
343 | ||
344 | /* Create the bucket and hash it */ | |
345 | b = mb_alloc(p->p.pool, size); | |
346 | b->hash_next = p->bucket_hash[index]; | |
347 | if (b->hash_next) | |
348 | b->hash_next->hash_prev = b; | |
349 | p->bucket_hash[index] = b; | |
350 | b->hash_prev = NULL; | |
351 | b->hash = hash; | |
352 | add_tail(&p->bucket_queue, &b->send_node); | |
353 | init_list(&b->prefixes); | |
354 | memcpy(b->eattrs, new, ea_size); | |
355 | dest = ((byte *)b->eattrs) + ea_size_aligned; | |
356 | ||
357 | /* Copy values of non-inline attributes */ | |
358 | for (i=0; i<new->count; i++) | |
359 | { | |
360 | eattr *a = &b->eattrs->attrs[i]; | |
361 | if (!(a->type & EAF_EMBEDDED)) | |
362 | { | |
363 | struct adata *oa = a->u.ptr; | |
364 | struct adata *na = (struct adata *) dest; | |
365 | memcpy(na, oa, sizeof(struct adata) + oa->length); | |
366 | a->u.ptr = na; | |
367 | dest += BIRD_ALIGN(sizeof(struct adata) + na->length, CPU_STRUCT_ALIGN); | |
368 | } | |
369 | } | |
370 | ||
371 | /* If needed, rehash */ | |
372 | p->hash_count++; | |
373 | if (p->hash_count > p->hash_limit) | |
374 | bgp_rehash_buckets(p); | |
375 | ||
376 | return b; | |
377 | } | |
378 | ||
379 | static int | |
380 | bgp_export_check(struct bgp_proto *p, ea_list *new) | |
381 | { | |
382 | eattr *a; | |
383 | struct adata *d; | |
384 | ||
385 | /* Check if next hop is valid */ | |
386 | a = ea_find(new, EA_CODE(EAP_BGP, BA_NEXT_HOP)); | |
387 | if (!a || ipa_equal(p->next_hop, *(ip_addr *)a->u.ptr)) | |
388 | { | |
389 | DBG("\tInvalid NEXT_HOP\n"); | |
390 | return 0; | |
391 | } | |
392 | ||
393 | /* Check if we aren't forbidden to export the route by communities */ | |
394 | a = ea_find(new, EA_CODE(EAP_BGP, BA_COMMUNITY)); | |
395 | if (a) | |
396 | { | |
397 | d = a->u.ptr; | |
398 | if (int_set_contains(d, BGP_COMM_NO_ADVERTISE)) | |
399 | { | |
400 | DBG("\tNO_ADVERTISE\n"); | |
401 | return 0; | |
402 | } | |
403 | if (!p->is_internal && | |
404 | (int_set_contains(d, BGP_COMM_NO_EXPORT) || | |
405 | int_set_contains(d, BGP_COMM_NO_EXPORT_SUBCONFED))) | |
406 | { | |
407 | DBG("\tNO_EXPORT\n"); | |
408 | return 0; | |
409 | } | |
410 | } | |
411 | ||
412 | return 1; | |
413 | } | |
414 | ||
415 | static struct bgp_bucket * | |
416 | bgp_get_bucket(struct bgp_proto *p, ea_list *attrs, int originate) | |
417 | { | |
418 | ea_list *new; | |
419 | unsigned i, cnt, hash, code; | |
420 | eattr *a, *d; | |
421 | u32 seen = 0; | |
422 | struct bgp_bucket *b; | |
423 | ||
424 | /* Merge the attribute list */ | |
425 | new = alloca(ea_scan(attrs)); | |
426 | ea_merge(attrs, new); | |
427 | ea_sort(new); | |
428 | ||
429 | /* Normalize attributes */ | |
430 | d = new->attrs; | |
431 | cnt = new->count; | |
432 | new->count = 0; | |
433 | for(i=0; i<cnt; i++) | |
434 | { | |
435 | a = &new->attrs[i]; | |
436 | #ifdef LOCAL_DEBUG | |
437 | { | |
438 | byte buf[EA_FORMAT_BUF_SIZE]; | |
439 | ea_format(a, buf); | |
440 | DBG("\t%s\n", buf); | |
441 | } | |
442 | #endif | |
443 | if (EA_PROTO(a->id) != EAP_BGP) | |
444 | continue; | |
445 | code = EA_ID(a->id); | |
446 | if (ATTR_KNOWN(code)) | |
447 | { | |
448 | if (!bgp_attr_table[code].allow_in_ebgp && !p->is_internal) | |
449 | continue; | |
450 | /* The flags might have been zero if the attr was added by filters */ | |
451 | a->flags = (a->flags & BAF_PARTIAL) | bgp_attr_table[code].expected_flags; | |
452 | if (code < 32) | |
453 | seen |= 1 << code; | |
454 | } | |
455 | else | |
456 | { | |
457 | /* Don't re-export unknown non-transitive attributes */ | |
458 | if (!(a->flags & BAF_TRANSITIVE)) | |
459 | continue; | |
460 | } | |
461 | *d = *a; | |
462 | if ((d->type & EAF_ORIGINATED) && !originate && (d->flags & BAF_TRANSITIVE) && (d->flags & BAF_OPTIONAL)) | |
463 | d->flags |= BAF_PARTIAL; | |
464 | switch (d->type & EAF_TYPE_MASK) | |
465 | { | |
466 | case EAF_TYPE_INT_SET: | |
467 | { | |
468 | struct adata *z = alloca(sizeof(struct adata) + d->u.ptr->length); | |
469 | z->length = d->u.ptr->length; | |
470 | bgp_normalize_set((u32 *) z->data, (u32 *) d->u.ptr->data, z->length / 4); | |
471 | d->u.ptr = z; | |
472 | break; | |
473 | } | |
474 | default: ; | |
475 | } | |
476 | d++; | |
477 | new->count++; | |
478 | } | |
479 | ||
480 | /* Hash */ | |
481 | hash = ea_hash(new); | |
482 | for(b=p->bucket_hash[hash & (p->hash_size - 1)]; b; b=b->hash_next) | |
483 | if (b->hash == hash && ea_same(b->eattrs, new)) | |
484 | { | |
485 | DBG("Found bucket.\n"); | |
486 | return b; | |
487 | } | |
488 | ||
489 | /* Ensure that there are all mandatory attributes */ | |
490 | for(i=0; i<ARRAY_SIZE(bgp_mandatory_attrs); i++) | |
491 | if (!(seen & (1 << bgp_mandatory_attrs[i]))) | |
492 | { | |
493 | log(L_ERR "%s: Mandatory attribute %s missing", p->p.name, bgp_attr_table[bgp_mandatory_attrs[i]].name); | |
494 | return NULL; | |
495 | } | |
496 | ||
497 | if (!bgp_export_check(p, new)) | |
498 | return NULL; | |
499 | ||
500 | /* Create new bucket */ | |
501 | DBG("Creating bucket.\n"); | |
502 | return bgp_new_bucket(p, new, hash); | |
503 | } | |
504 | ||
505 | void | |
506 | bgp_free_bucket(struct bgp_proto *p, struct bgp_bucket *buck) | |
507 | { | |
508 | if (buck->hash_next) | |
509 | buck->hash_next->hash_prev = buck->hash_prev; | |
510 | if (buck->hash_prev) | |
511 | buck->hash_prev->hash_next = buck->hash_next; | |
512 | else | |
513 | p->bucket_hash[buck->hash & (p->hash_size-1)] = buck->hash_next; | |
514 | mb_free(buck); | |
515 | } | |
516 | ||
517 | void | |
518 | bgp_rt_notify(struct proto *P, net *n, rte *new, rte *old UNUSED, ea_list *attrs) | |
519 | { | |
520 | struct bgp_proto *p = (struct bgp_proto *) P; | |
521 | struct bgp_bucket *buck; | |
522 | struct bgp_prefix *px; | |
523 | ||
524 | DBG("BGP: Got route %I/%d %s\n", n->n.prefix, n->n.pxlen, new ? "up" : "down"); | |
525 | ||
526 | if (new) | |
527 | { | |
528 | buck = bgp_get_bucket(p, attrs, new->attrs->source != RTS_BGP); | |
529 | if (!buck) /* Inconsistent attribute list */ | |
530 | return; | |
531 | } | |
532 | else | |
533 | { | |
534 | if (!(buck = p->withdraw_bucket)) | |
535 | { | |
536 | buck = p->withdraw_bucket = mb_alloc(P->pool, sizeof(struct bgp_bucket)); | |
537 | init_list(&buck->prefixes); | |
538 | } | |
539 | } | |
540 | px = fib_get(&p->prefix_fib, &n->n.prefix, n->n.pxlen); | |
541 | if (px->bucket_node.next) | |
542 | { | |
543 | DBG("\tRemoving old entry.\n"); | |
544 | rem_node(&px->bucket_node); | |
545 | } | |
546 | add_tail(&buck->prefixes, &px->bucket_node); | |
547 | bgp_schedule_packet(p->conn, PKT_UPDATE); | |
548 | } | |
549 | ||
550 | static int | |
551 | bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool) | |
552 | { | |
553 | ea_list *ea = lp_alloc(pool, sizeof(ea_list) + 4*sizeof(eattr)); | |
554 | rta *rta = e->attrs; | |
555 | byte *z; | |
556 | ||
557 | ea->next = *attrs; | |
558 | *attrs = ea; | |
559 | ea->flags = EALF_SORTED; | |
560 | ea->count = 4; | |
561 | ||
562 | bgp_set_attr(ea->attrs, pool, BA_ORIGIN, | |
563 | ((rta->source == RTS_OSPF_EXT1) || (rta->source == RTS_OSPF_EXT2)) ? ORIGIN_INCOMPLETE : ORIGIN_IGP); | |
564 | ||
565 | if (p->is_internal) | |
566 | bgp_set_attr(ea->attrs+1, pool, BA_AS_PATH, 0); | |
567 | else | |
568 | { | |
569 | z = bgp_set_attr(ea->attrs+1, pool, BA_AS_PATH, 4); | |
570 | z[0] = AS_PATH_SEQUENCE; | |
571 | z[1] = 1; /* 1 AS */ | |
572 | put_u16(z+2, p->local_as); | |
573 | } | |
574 | ||
575 | z = bgp_set_attr(ea->attrs+2, pool, BA_NEXT_HOP, sizeof(ip_addr)); | |
576 | if (p->cf->next_hop_self || | |
577 | !p->is_internal || | |
578 | rta->dest != RTD_ROUTER) | |
579 | { | |
580 | if (ipa_nonzero(p->cf->source_addr)) | |
581 | *(ip_addr *)z = p->cf->source_addr; | |
582 | else | |
583 | *(ip_addr *)z = p->local_addr; | |
584 | } | |
585 | else | |
586 | *(ip_addr *)z = e->attrs->gw; | |
587 | ||
588 | bgp_set_attr(ea->attrs+3, pool, BA_LOCAL_PREF, 0); | |
589 | ||
590 | return 0; /* Leave decision to the filters */ | |
591 | } | |
592 | ||
593 | static ea_list * | |
594 | bgp_path_prepend(struct linpool *pool, eattr *a, ea_list *old, int as) | |
595 | { | |
596 | struct ea_list *e = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr)); | |
597 | struct adata *olda = a->u.ptr; | |
598 | ||
599 | e->next = old; | |
600 | e->flags = EALF_SORTED; | |
601 | e->count = 1; | |
602 | e->attrs[0].id = EA_CODE(EAP_BGP, BA_AS_PATH); | |
603 | e->attrs[0].flags = BAF_TRANSITIVE; | |
604 | e->attrs[0].type = EAF_TYPE_AS_PATH; | |
605 | e->attrs[0].u.ptr = as_path_prepend(pool, olda, as); | |
606 | return e; | |
607 | } | |
608 | ||
609 | static int | |
610 | bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool) | |
611 | { | |
612 | eattr *a; | |
613 | ||
614 | if (!p->is_internal && (a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH)))) | |
615 | *attrs = bgp_path_prepend(pool, a, *attrs, p->local_as); | |
616 | ||
617 | a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP)); | |
618 | if (a && (p->is_internal || (!p->is_internal && e->attrs->iface == p->neigh->iface))) | |
619 | { | |
620 | /* Leave the original next hop attribute, will check later where does it point */ | |
621 | } | |
622 | else | |
623 | { | |
624 | /* Need to create new one */ | |
625 | *(ip_addr *) bgp_attach_attr(attrs, pool, BA_NEXT_HOP, sizeof(ip_addr)) = p->local_addr; | |
626 | } | |
627 | ||
628 | return 0; /* Leave decision to the filters */ | |
629 | } | |
630 | ||
631 | int | |
632 | bgp_import_control(struct proto *P, rte **new, ea_list **attrs, struct linpool *pool) | |
633 | { | |
634 | rte *e = *new; | |
635 | struct bgp_proto *p = (struct bgp_proto *) P; | |
636 | struct bgp_proto *new_bgp = (e->attrs->proto->proto == &proto_bgp) ? (struct bgp_proto *) e->attrs->proto : NULL; | |
637 | ||
638 | if (p == new_bgp) /* Poison reverse updates */ | |
639 | return -1; | |
640 | if (new_bgp) | |
641 | { | |
642 | if (p->local_as == new_bgp->local_as && p->is_internal && new_bgp->is_internal) | |
643 | return -1; /* Don't redistribute internal routes with IBGP */ | |
644 | return bgp_update_attrs(p, e, attrs, pool); | |
645 | } | |
646 | else | |
647 | return bgp_create_attrs(p, e, attrs, pool); | |
648 | } | |
649 | ||
650 | int | |
651 | bgp_rte_better(rte *new, rte *old) | |
652 | { | |
653 | struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->proto; | |
654 | struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->proto; | |
655 | eattr *x, *y; | |
656 | u32 n, o; | |
657 | ||
658 | /* Start with local preferences */ | |
659 | x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF)); | |
660 | y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_LOCAL_PREF)); | |
661 | n = x ? x->u.data : new_bgp->cf->default_local_pref; | |
662 | o = y ? y->u.data : old_bgp->cf->default_local_pref; | |
663 | if (n > o) | |
664 | return 1; | |
665 | if (n < o) | |
666 | return 0; | |
667 | ||
668 | /* Use AS path lengths */ | |
669 | if (new_bgp->cf->compare_path_lengths || old_bgp->cf->compare_path_lengths) | |
670 | { | |
671 | x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH)); | |
672 | y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH)); | |
673 | n = x ? as_path_getlen(x->u.ptr) : 100000; | |
674 | o = y ? as_path_getlen(y->u.ptr) : 100000; | |
675 | if (n < o) | |
676 | return 1; | |
677 | if (n > o) | |
678 | return 0; | |
679 | } | |
680 | ||
681 | /* Use origins */ | |
682 | x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN)); | |
683 | y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN)); | |
684 | n = x ? x->u.data : ORIGIN_INCOMPLETE; | |
685 | o = y ? y->u.data : ORIGIN_INCOMPLETE; | |
686 | if (n < o) | |
687 | return 1; | |
688 | if (n > o) | |
689 | return 0; | |
690 | ||
691 | /* Compare MED's */ | |
692 | x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC)); | |
693 | y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC)); | |
694 | n = x ? x->u.data : new_bgp->cf->default_med; | |
695 | o = y ? y->u.data : old_bgp->cf->default_med; | |
696 | if (n < o) | |
697 | return 1; | |
698 | if (n > o) | |
699 | return 0; | |
700 | ||
701 | /* A tie breaking procedure according to RFC 1771, section 9.1.2.1 */ | |
702 | /* We don't have interior distances */ | |
703 | /* We prefer external peers */ | |
704 | if (new_bgp->is_internal > old_bgp->is_internal) | |
705 | return 0; | |
706 | if (new_bgp->is_internal < old_bgp->is_internal) | |
707 | return 1; | |
708 | /* Finally we compare BGP identifiers */ | |
709 | return (new_bgp->remote_id < old_bgp->remote_id); | |
710 | } | |
711 | ||
712 | static int | |
713 | bgp_path_loopy(struct bgp_proto *p, eattr *a) | |
714 | { | |
715 | byte *path = a->u.ptr->data; | |
716 | int len = a->u.ptr->length; | |
717 | int i, n; | |
718 | ||
719 | while (len > 0) | |
720 | { | |
721 | n = path[1]; | |
722 | len -= 2 + 2*n; | |
723 | path += 2; | |
724 | for(i=0; i<n; i++) | |
725 | { | |
726 | if (get_u16(path) == p->local_as) | |
727 | return 1; | |
728 | path += 2; | |
729 | } | |
730 | } | |
731 | return 0; | |
732 | } | |
733 | ||
734 | /** | |
735 | * bgp_decode_attrs - check and decode BGP attributes | |
736 | * @conn: connection | |
737 | * @attr: start of attribute block | |
738 | * @len: length of attribute block | |
739 | * @pool: linear pool to make all the allocations in | |
740 | * @mandatory: 1 iff presence of mandatory attributes has to be checked | |
741 | * | |
742 | * This function takes a BGP attribute block (a part of an Update message), checks | |
743 | * its consistency and converts it to a list of BIRD route attributes represented | |
744 | * by a &rta. | |
745 | */ | |
746 | struct rta * | |
747 | bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct linpool *pool, int mandatory) | |
748 | { | |
749 | struct bgp_proto *bgp = conn->bgp; | |
750 | rta *a = lp_alloc(pool, sizeof(struct rta)); | |
751 | unsigned int flags, code, l, i, type; | |
752 | int errcode; | |
753 | byte *z, *attr_start; | |
754 | byte seen[256/8]; | |
755 | eattr *e; | |
756 | ea_list *ea; | |
757 | struct adata *ad; | |
758 | ||
759 | a->proto = &bgp->p; | |
760 | a->source = RTS_BGP; | |
761 | a->scope = SCOPE_UNIVERSE; | |
762 | a->cast = RTC_UNICAST; | |
763 | a->dest = RTD_ROUTER; | |
764 | a->flags = 0; | |
765 | a->aflags = 0; | |
766 | a->from = bgp->cf->remote_ip; | |
767 | a->eattrs = NULL; | |
768 | ||
769 | /* Parse the attributes */ | |
770 | bzero(seen, sizeof(seen)); | |
771 | DBG("BGP: Parsing attributes\n"); | |
772 | while (len) | |
773 | { | |
774 | if (len < 2) | |
775 | goto malformed; | |
776 | attr_start = attr; | |
777 | flags = *attr++; | |
778 | code = *attr++; | |
779 | len -= 2; | |
780 | if (flags & BAF_EXT_LEN) | |
781 | { | |
782 | if (len < 2) | |
783 | goto malformed; | |
784 | l = get_u16(attr); | |
785 | attr += 2; | |
786 | len -= 2; | |
787 | } | |
788 | else | |
789 | { | |
790 | if (len < 1) | |
791 | goto malformed; | |
792 | l = *attr++; | |
793 | len--; | |
794 | } | |
795 | if (l > len) | |
796 | goto malformed; | |
797 | len -= l; | |
798 | z = attr; | |
799 | attr += l; | |
800 | DBG("Attr %02x %02x %d\n", code, flags, l); | |
801 | if (seen[code/8] & (1 << (code%8))) | |
802 | goto malformed; | |
803 | if (ATTR_KNOWN(code)) | |
804 | { | |
805 | struct attr_desc *desc = &bgp_attr_table[code]; | |
806 | if (desc->expected_length >= 0 && desc->expected_length != (int) l) | |
807 | { errcode = 5; goto err; } | |
808 | if ((desc->expected_flags ^ flags) & (BAF_OPTIONAL | BAF_TRANSITIVE)) | |
809 | { errcode = 4; goto err; } | |
810 | if (!desc->allow_in_ebgp && !bgp->is_internal) | |
811 | continue; | |
812 | if (desc->validate) | |
813 | { | |
814 | errcode = desc->validate(bgp, z, l); | |
815 | if (errcode > 0) | |
816 | goto err; | |
817 | if (errcode < 0) | |
818 | continue; | |
819 | } | |
820 | type = desc->type; | |
821 | } | |
822 | else /* Unknown attribute */ | |
823 | { | |
824 | if (!(flags & BAF_OPTIONAL)) | |
825 | { errcode = 2; goto err; } | |
826 | type = EAF_TYPE_OPAQUE; | |
827 | } | |
828 | seen[code/8] |= (1 << (code%8)); | |
829 | ea = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr)); | |
830 | ea->next = a->eattrs; | |
831 | a->eattrs = ea; | |
832 | ea->flags = 0; | |
833 | ea->count = 1; | |
834 | ea->attrs[0].id = EA_CODE(EAP_BGP, code); | |
835 | ea->attrs[0].flags = flags; | |
836 | ea->attrs[0].type = type; | |
837 | if (type & EAF_EMBEDDED) | |
838 | ad = NULL; | |
839 | else | |
840 | { | |
841 | ad = lp_alloc(pool, sizeof(struct adata) + l); | |
842 | ea->attrs[0].u.ptr = ad; | |
843 | ad->length = l; | |
844 | memcpy(ad->data, z, l); | |
845 | } | |
846 | switch (type) | |
847 | { | |
848 | case EAF_TYPE_ROUTER_ID: | |
849 | case EAF_TYPE_INT: | |
850 | if (l == 1) | |
851 | ea->attrs[0].u.data = *z; | |
852 | else | |
853 | ea->attrs[0].u.data = get_u32(z); | |
854 | break; | |
855 | case EAF_TYPE_IP_ADDRESS: | |
856 | ipa_ntoh(*(ip_addr *)ad->data); | |
857 | break; | |
858 | case EAF_TYPE_INT_SET: | |
859 | { | |
860 | u32 *z = (u32 *) ad->data; | |
861 | for(i=0; i<ad->length/4; i++) | |
862 | z[i] = ntohl(z[i]); | |
863 | break; | |
864 | } | |
865 | } | |
866 | } | |
867 | ||
868 | #ifdef IPV6 | |
869 | if (seen[BA_MP_REACH_NLRI / 8] & (1 << (BA_MP_REACH_NLRI % 8))) | |
870 | mandatory = 1; | |
871 | #endif | |
872 | ||
873 | /* Check if all mandatory attributes are present */ | |
874 | if (mandatory) | |
875 | { | |
876 | for(i=0; i < ARRAY_SIZE(bgp_mandatory_attrs); i++) | |
877 | { | |
878 | code = bgp_mandatory_attrs[i]; | |
879 | if (!(seen[code/8] & (1 << (code%8)))) | |
880 | { | |
881 | bgp_error(conn, 3, 3, &bgp_mandatory_attrs[i], 1); | |
882 | return NULL; | |
883 | } | |
884 | } | |
885 | } | |
886 | ||
887 | /* If the AS path attribute contains our AS, reject the routes */ | |
888 | e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH)); | |
889 | if (e && bgp_path_loopy(bgp, e)) | |
890 | { | |
891 | DBG("BGP: Path loop!\n"); | |
892 | return NULL; | |
893 | } | |
894 | ||
895 | /* If there's no local preference, define one */ | |
896 | if (!(seen[0] && (1 << BA_LOCAL_PREF))) | |
897 | bgp_attach_attr(&a->eattrs, pool, BA_LOCAL_PREF, 0); | |
898 | return a; | |
899 | ||
900 | malformed: | |
901 | bgp_error(conn, 3, 1, NULL, 0); | |
902 | return NULL; | |
903 | ||
904 | err: | |
905 | bgp_error(conn, 3, errcode, attr_start, z+l-attr_start); | |
906 | return NULL; | |
907 | } | |
908 | ||
909 | int | |
910 | bgp_get_attr(eattr *a, byte *buf) | |
911 | { | |
912 | unsigned int i = EA_ID(a->id); | |
913 | struct attr_desc *d; | |
914 | ||
915 | if (ATTR_KNOWN(i)) | |
916 | { | |
917 | d = &bgp_attr_table[i]; | |
918 | buf += bsprintf(buf, "%s", d->name); | |
919 | if (d->format) | |
920 | { | |
921 | *buf++ = ':'; | |
922 | *buf++ = ' '; | |
923 | d->format(a, buf); | |
924 | return GA_FULL; | |
925 | } | |
926 | return GA_NAME; | |
927 | } | |
928 | bsprintf(buf, "%02x%s", i, (a->flags & BAF_TRANSITIVE) ? " [t]" : ""); | |
929 | return GA_NAME; | |
930 | } | |
931 | ||
932 | void | |
933 | bgp_attr_init(struct bgp_proto *p) | |
934 | { | |
935 | p->hash_size = 256; | |
936 | p->hash_limit = p->hash_size * 4; | |
937 | p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *)); | |
938 | init_list(&p->bucket_queue); | |
939 | p->withdraw_bucket = NULL; | |
940 | fib_init(&p->prefix_fib, p->p.pool, sizeof(struct bgp_prefix), 0, bgp_init_prefix); | |
941 | } | |
942 | ||
943 | void | |
944 | bgp_get_route_info(rte *e, byte *buf, ea_list *attrs) | |
945 | { | |
946 | eattr *p = ea_find(attrs, EA_CODE(EAP_BGP, BA_AS_PATH)); | |
947 | eattr *o = ea_find(attrs, EA_CODE(EAP_BGP, BA_ORIGIN)); | |
948 | int origas; | |
949 | ||
950 | buf += bsprintf(buf, " (%d) [", e->pref); | |
951 | if (p && (origas = as_path_get_first(p->u.ptr)) >= 0) | |
952 | buf += bsprintf(buf, "AS%d", origas); | |
953 | if (o) | |
954 | buf += bsprintf(buf, "%c", "ie?"[o->u.data]); | |
955 | strcpy(buf, "]"); | |
956 | } |