From b77ae37d11aa6e16dce31f50ca42ea30714a793e Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 17 Mar 1999 13:09:09 +0000 Subject: Implemented extended route attributes and all related functions. --- nest/rt-attr.c | 299 +++++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 250 insertions(+), 49 deletions(-) (limited to 'nest/rt-attr.c') 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 + * (c) 1998--1999 Martin Mares * * Can be freely distributed and used under the terms of the GNU GPL. */ #include +#include #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; mcount; 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; icount; 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; ccount; 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; cnattrs; 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; icount; 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; icount; 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; ju.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; inattrs; 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 -- cgit v1.2.3