summaryrefslogtreecommitdiffstats
path: root/nest/rt-attr.c
diff options
context:
space:
mode:
Diffstat (limited to 'nest/rt-attr.c')
-rw-r--r--nest/rt-attr.c299
1 files changed, 250 insertions, 49 deletions
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