diff options
| -rw-r--r-- | nest/route.h | 53 | ||||
| -rw-r--r-- | nest/rt-attr.c | 299 |
2 files changed, 281 insertions, 71 deletions
diff --git a/nest/route.h b/nest/route.h index 2bcc2b5..0de5455 100644 --- a/nest/route.h +++ b/nest/route.h @@ -185,12 +185,11 @@ typedef struct rta { byte tos; /* TOS of this route */ byte flags; /* Route flags (RTF_...) */ byte aflags; /* Attribute cache flags (RTAF_...) */ + byte rfu; /* Padding */ ip_addr gw; /* Next hop */ ip_addr from; /* Advertising router */ struct iface *iface; /* Outgoing interface */ struct ea_list *attrs; /* Extended Attribute chain */ - union { /* Protocol-specific data */ - } u; } rta; #define RTS_DUMMY 0 /* Dummy route to be removed soon */ @@ -228,24 +227,32 @@ typedef struct rta { */ typedef struct eattr { - byte protocol; /* Protocol ID (EAP_...) */ - byte flags; /* Attribute flags (EAF_...) */ - byte id; /* Protocol-dependent ID */ - byte rfu; /* ??? */ + word id; /* EA_CODE(EAP_..., protocol-dependent ID) */ + byte flags; /* Protocol-dependent flags */ + byte type; /* Attribute type and several flags (EAF_...) */ union { u32 data; struct adata *ptr; /* Attribute data elsewhere */ } u; } eattr; +/* FIXME: Introduce real protocol numbers? */ #define EAP_GENERIC 0 /* Generic attributes */ #define EAP_BGP 1 /* BGP attributes */ -#define EAF_OPTIONAL 0x80 /* Refer to BGP specs for full meaning */ -#define EAF_TRANSITIVE 0x40 -#define EAF_PARTIAL 0x20 -#define EAF_EXTENDED_LENGTH 0x10 /* Not used by us, internal to BGP */ -#define EAF_LONGWORD 0x01 /* Embedded value [Not a BGP flag!] */ +#define EA_CODE(proto,id) (((proto) << 8) | (id)) +#define EA_PROTO(ea) ((ea) >> 8) +#define EA_ID(ea) ((ea) & 0xff) + +#define EAF_TYPE_MASK 0x0f /* Mask with this to get type */ +#define EAF_TYPE_INT 0x01 /* 32-bit signed integer number */ +#define EAF_TYPE_OPAQUE 0x02 /* Opaque byte string (not filterable) */ +#define EAF_TYPE_IP_ADDRESS 0x04 /* IP address [FIXME: embed at least for IPv4?] */ +#define EAF_TYPE_AS_PATH 0x06 /* BGP AS path [FIXME: define storage layout] */ +#define EAF_TYPE_INT_SET 0x0a /* Set of integers (e.g., a community list) */ +#define EAF_EMBEDDED 0x01 /* Data stored in eattr.u.data (part of type spec) */ +#define EAF_VAR_LENGTH 0x02 /* Attribute length is variable */ +#define EAF_INLINE 0x80 /* Copy of an attribute inlined in rte (temporary ea_lists only) */ struct adata { unsigned int length; @@ -254,28 +261,30 @@ struct adata { typedef struct ea_list { struct ea_list *next; /* In case we have an override list */ - byte sorted; /* `Really sorted' flag (???) */ + byte flags; /* Flags: EALF_... */ byte rfu; - word nattrs; /* Number of attributes */ + word count; /* Number of attributes */ eattr attrs[0]; /* Attribute definitions themselves */ } ea_list; -eattr *ea_find(ea_list *, unsigned protocol, unsigned id); +#define EALF_SORTED 1 /* Attributes are sorted by code */ +#define EALF_BISECT 2 /* Use interval bisection for searching */ +#define EALF_CACHED 4 /* Attributes belonging to cached rta */ -#define EA_LIST_NEW(p, alloc, n) do { \ - unsigned cnt = n; \ - p = alloc(sizeof(ea_list) + cnt*sizeof(eattr)); \ - memset(p, 0, sizeof(ea_list)); \ - p->nattrs = cnt; \ -} while(0) +eattr *ea_find(ea_list *, unsigned ea); +void ea_dump(ea_list *); +void ea_sort(ea_list *); /* Sort entries in all sub-lists */ +unsigned ea_scan(ea_list *); /* How many bytes do we need for merged ea_list (0=merge not needed) */ +void ea_merge(ea_list *from, ea_list *to); /* Merge sub-lists to allocated buffer */ void rta_init(void); rta *rta_lookup(rta *); /* Get rta equivalent to this one, uc++ */ static inline rta *rta_clone(rta *r) { r->uc++; return r; } -void _rta_free(rta *r); -static inline void rta_free(rta *r) { if (r && !--r->uc) _rta_free(r); } +void rta__free(rta *r); +static inline void rta_free(rta *r) { if (r && !--r->uc) rta__free(r); } void rta_dump(rta *); void rta_dump_all(void); +static inline eattr * rta_find(rta *a, unsigned ea) { return ea_find(a->attrs, ea); } /* * Default protocol preferences diff --git a/nest/rt-attr.c b/nest/rt-attr.c index aa4a59a..2cb2bc5 100644 --- a/nest/rt-attr.c +++ b/nest/rt-attr.c @@ -1,12 +1,13 @@ /* * BIRD -- Route Attribute Cache * - * (c) 1998 Martin Mares <mj@ucw.cz> + * (c) 1998--1999 Martin Mares <mj@ucw.cz> * * Can be freely distributed and used under the terms of the GNU GPL. */ #include <string.h> +#include <alloca.h> #include "nest/bird.h" #include "nest/route.h" @@ -22,33 +23,246 @@ static rta *first_rta; static slab *rta_slab; static pool *rta_pool; +/* + * Extended Attributes + */ + +eattr * +ea_find(ea_list *e, unsigned id) +{ + eattr *a; + int l, r, m; + + while (e) + { + if (e->flags & EALF_BISECT) + { + l = 0; + r = e->count + 1; + while (l <= r) + { + m = (l+r) / 2; + a = &e->attrs[m]; + if (a->id == id) + return a; + else if (a->id < id) + l = m+1; + else + r = m-1; + } + } + else + for(m=0; m<e->count; m++) + if (e->attrs[m].id == id) + return &e->attrs[m]; + e = e->next; + } + return NULL; +} + +static inline void +ea_do_sort(ea_list *e) +{ + unsigned n = e->count; + eattr *a = e->attrs; + eattr *b = alloca(n * sizeof(eattr)); + unsigned s, ss; + + /* We need to use a stable sorting algorithm, hence mergesort */ + do + { + s = ss = 0; + while (s < n) + { + eattr *p, *q, *lo, *hi; + p = b; + ss = s; + *p++ = a[s++]; + while (s < n && p[-1].id <= a[s].id) + *p++ = a[s++]; + if (s < n) + { + q = p; + *p++ = a[s++]; + while (s < n && p[-1].id <= a[s].id) + *p++ = a[s++]; + lo = b; + hi = q; + s = ss; + while (lo < q && hi < p) + if (lo->id <= hi->id) + a[s++] = *lo++; + else + a[s++] = *hi++; + while (lo < q) + a[s++] = *lo++; + while (hi < p) + a[s++] = *hi++; + } + } + } + while (ss); +} + +static inline void +ea_do_prune(ea_list *e) +{ + eattr *s, *d; + int i; + + /* Discard duplicates. Do you remember sorting was stable? */ + s = d = e->attrs + 1; + for(i=1; i<e->count; i++) + if (s->id != d[-1].id) + *d++ = *s++; + else + s++; + e->count = d - e->attrs; +} + +void +ea_sort(ea_list *e) +{ + while (e) + { + if (!(e->flags & EALF_SORTED)) + { + ea_do_sort(e); + ea_do_prune(e); + e->flags |= EALF_SORTED; + } +#if 0 /* FIXME: Remove this after some testing */ + if (e->count > 5) +#endif + e->flags |= EALF_BISECT; + e = e->next; + } +} + +unsigned +ea_scan(ea_list *e) +{ + unsigned cnt = 0; + + while (e) + { + cnt += e->count; + e = e->next; + } + return sizeof(ea_list) + sizeof(eattr)*cnt; +} + +void +ea_merge(ea_list *e, ea_list *t) +{ + eattr *d = t->attrs; + + t->flags = 0; + t->count = 0; + t->next = NULL; + while (e) + { + memcpy(d, e->attrs, sizeof(eattr)*e->count); + t->count += e->count; + d += e->count; + e = e->next; + } +} + static inline int ea_same(ea_list *x, ea_list *y) { int c; - while (x && y) + if (!x || !y) + return x == y; + ASSERT(!x->next && !y->next); + if (x->count != y->count) + return 0; + for(c=0; c<x->count; c++) { - if (x->nattrs != y->nattrs) + eattr *a = &x->attrs[c]; + eattr *b = &y->attrs[c]; + + if (a->id != b->id || + a->flags != b->flags || + a->type != b->type || + ((a->type & EAF_EMBEDDED) ? a->u.data != b->u.data : + (a->u.ptr->length != b->u.ptr->length || memcmp(a->u.ptr, b->u.ptr, a->u.ptr->length)))) return 0; - for(c=0; c<x->nattrs; c++) + } + return 1; +} + +static inline ea_list * +ea_list_copy(ea_list *o) +{ + ea_list *n; + unsigned i, len; + + if (!o) + return NULL; + ASSERT(!o->next); + len = sizeof(ea_list) + sizeof(eattr) * o->count; + n = mb_alloc(rta_pool, len); + memcpy(n, o, len); + n->flags |= EALF_CACHED; + for(i=0; i<o->count; i++) + { + eattr *a = &n->attrs[i]; + if (!(a->flags & EAF_EMBEDDED)) + { + unsigned size = sizeof(struct adata) + a->u.ptr->length; + struct adata *d = mb_alloc(rta_pool, size); + memcpy(d, a->u.ptr, size); + a->u.ptr = d; + } + } + return n; +} + +void +ea_dump(ea_list *e) +{ + int i; + + if (!e) + { + debug("NONE"); + return; + } + while (e) + { + debug("[%c%c%c]", + (e->flags & EALF_SORTED) ? 'S' : 's', + (e->flags & EALF_BISECT) ? 'B' : 'b', + (e->flags & EALF_CACHED) ? 'C' : 'c'); + for(i=0; i<e->count; i++) { - eattr *a = &x->attrs[c]; - eattr *b = &y->attrs[c]; - - if (a->protocol != b->protocol || - a->flags != b->flags || - a->id != b->id || - ((a->flags & EAF_LONGWORD) ? a->u.data != b->u.data : - (a->u.ptr->length != b->u.ptr->length || memcmp(a->u.ptr, b->u.ptr, a->u.ptr->length)))) - return 0; + eattr *a = &e->attrs[i]; + debug(" %02x:%02x.%02x", EA_PROTO(a->id), EA_ID(a->id), a->flags); + if (a->type & EAF_INLINE) + debug("*"); + debug("=%c", "?iO?I?P???S?????" [a->type & EAF_TYPE_MASK]); + if (a->type & EAF_EMBEDDED) + debug(":%08x", a->u.data); + else + { + int j, len = a->u.ptr->length; + debug("[%d]:", len); + for(j=0; j<len; j++) + debug("%02x", a->u.ptr->data[j]); + } } - x = x->next; - y = y->next; + if (e = e->next) + debug(" | "); } - return (!x && !y); } +/* + * rta's + */ + static inline int rta_same(rta *x, rta *y) { @@ -62,38 +276,7 @@ rta_same(rta *x, rta *y) ipa_equal(x->gw, y->gw) && ipa_equal(x->from, y->from) && x->iface == y->iface && - ea_same(x->attrs, y->attrs) && - (!x->proto->rta_same || x->proto->rta_same(x, y))); -} - -static inline ea_list * -ea_list_copy(ea_list *o) -{ - ea_list *n, **p, *z; - unsigned i; - - p = &n; - while (o) - { - z = mb_alloc(rta_pool, sizeof(ea_list) + sizeof(eattr) * o->nattrs); - memcpy(z, o, sizeof(ea_list) + sizeof(eattr) * o->nattrs); - *p = z; - p = &z->next; - for(i=0; i<o->nattrs; i++) - { - eattr *a = o->attrs + i; - if (!(a->flags & EAF_LONGWORD)) - { - unsigned size = sizeof(struct adata) + a->u.ptr->length; - struct adata *d = mb_alloc(rta_pool, size); - memcpy(d, a->u.ptr, size); - a->u.ptr = d; - } - } - o = o->next; - } - *p = NULL; - return n; + ea_same(x->attrs, y->attrs)); } static rta * @@ -112,9 +295,22 @@ rta_lookup(rta *o) { rta *r; + ASSERT(!(o->aflags & RTAF_CACHED)); + if (o->attrs) + { + if (o->attrs->next) /* Multiple ea_list's, need to merge them */ + { + ea_list *ml = alloca(ea_scan(o->attrs)); + ea_merge(o->attrs, ml); + o->attrs = ml; + } + ea_sort(o->attrs); + } + for(r=first_rta; r; r=r->next) if (rta_same(r, o)) return rta_clone(r); + r = rta_copy(o); r->aflags = RTAF_CACHED; r->next = first_rta; @@ -123,7 +319,7 @@ rta_lookup(rta *o) } void -_rta_free(rta *a) +rta__free(rta *a) { } @@ -152,6 +348,11 @@ rta_dump(rta *a) debug(" ->%I", a->gw); if (a->dest == RTD_DEVICE || a->dest == RTD_ROUTER) debug(" [%s]", a->iface ? a->iface->name : "???" ); + if (a->attrs) + { + debug(" EA: "); + ea_dump(a->attrs); + } } void |