summaryrefslogtreecommitdiffstats
path: root/proto
diff options
context:
space:
mode:
authorMartin Mares <mj@ucw.cz>2000-04-10 14:39:51 +0200
committerMartin Mares <mj@ucw.cz>2000-04-10 14:39:51 +0200
commitae8f5584990ce3bfb5b0bec2f7a1c052e45860df (patch)
tree1ba4bcf4c45c6e011ae0a9b9bbdcf31b7652ac35 /proto
parent6f57dcc07cdf54133bd57aeaec7446f59f2c91cd (diff)
downloadbird-ae8f5584990ce3bfb5b0bec2f7a1c052e45860df.tar
bird-ae8f5584990ce3bfb5b0bec2f7a1c052e45860df.zip
Implemented outgoing attribute cache.
Diffstat (limited to 'proto')
-rw-r--r--proto/bgp/attrs.c211
-rw-r--r--proto/bgp/bgp.h3
-rw-r--r--proto/bgp/packets.c1
3 files changed, 203 insertions, 12 deletions
diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c
index 841fe10..5c1e70d 100644
--- a/proto/bgp/attrs.c
+++ b/proto/bgp/attrs.c
@@ -19,13 +19,201 @@
#include "bgp.h"
+static int bgp_mandatory_attrs[] = { BA_ORIGIN, BA_AS_PATH, BA_NEXT_HOP };
+
+struct bgp_bucket {
+ struct bgp_bucket *next;
+ unsigned hash;
+ ea_list eattrs[0];
+};
+
+struct attr_desc {
+ char *name; /* FIXME: Use the same names as in filters */
+ int expected_length;
+ int expected_flags;
+ int type;
+ int (*validate)(struct bgp_proto *p, byte *attr, int len);
+ void (*format)(eattr *ea, byte *buf);
+};
+
+extern struct attr_desc bgp_attr_table[];
+
+static void
+bgp_normalize_set(u32 *dest, u32 *src, unsigned cnt)
+{
+ memcpy(dest, src, sizeof(u32) * cnt);
+ /* FIXME */
+}
+
+static void
+bgp_rehash_buckets(struct bgp_proto *p)
+{
+ struct bgp_bucket **old = p->bucket_table;
+ struct bgp_bucket **new;
+ unsigned oldn = p->hash_size;
+ unsigned i, e, mask;
+ struct bgp_bucket *b;
+
+ p->hash_size = p->hash_limit;
+ DBG("BGP: Rehashing bucket table from %d to %d\n", oldn, p->hash_size);
+ p->hash_limit *= 4;
+ if (p->hash_limit >= 65536)
+ p->hash_limit = ~0;
+ new = p->bucket_table = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
+ mask = p->hash_size - 1;
+ for (i=0; i<oldn; i++)
+ while (b = old[i])
+ {
+ old[i] = b->next;
+ e = b->hash & mask;
+ b->next = new[e];
+ new[e] = b;
+ }
+ mb_free(old);
+}
+
+static struct bgp_bucket *
+bgp_new_bucket(struct bgp_proto *p, ea_list *new, unsigned hash)
+{
+ struct bgp_bucket *b;
+ unsigned ea_size = sizeof(ea_list) + new->count * sizeof(eattr);
+ unsigned ea_size_aligned = ALIGN(ea_size, CPU_STRUCT_ALIGN);
+ unsigned size = sizeof(struct bgp_bucket) + ea_size;
+ unsigned i;
+ byte *dest;
+ unsigned index = hash & (p->hash_size - 1);
+
+ /* Gather total size of non-inline attributes */
+ for (i=0; i<new->count; i++)
+ {
+ eattr *a = &new->attrs[i];
+ if (!(a->type & EAF_EMBEDDED))
+ size += ALIGN(sizeof(struct adata) + a->u.ptr->length, CPU_STRUCT_ALIGN);
+ }
+
+ /* Create the bucket and hash it */
+ b = mb_alloc(p->p.pool, size);
+ b->next = p->bucket_table[index];
+ p->bucket_table[index] = b;
+ b->hash = hash;
+ memcpy(b->eattrs, new, ea_size);
+ dest = ((byte *)b->eattrs) + ea_size_aligned;
+
+ /* Copy values of non-inline attributes */
+ for (i=0; i<new->count; i++)
+ {
+ eattr *a = &new->attrs[i];
+ if (!(a->type & EAF_EMBEDDED))
+ {
+ struct adata *oa = a->u.ptr;
+ struct adata *na = (struct adata *) dest;
+ memcpy(na, oa, sizeof(struct adata) + oa->length);
+ a->u.ptr = na;
+ dest += ALIGN(na->length, CPU_STRUCT_ALIGN);
+ }
+ }
+
+ /* If needed, rehash */
+ p->hash_count++;
+ if (p->hash_count > p->hash_limit)
+ bgp_rehash_buckets(p);
+
+ return b;
+}
+
+static struct bgp_bucket *
+bgp_get_bucket(struct bgp_proto *p, ea_list *old, ea_list *tmp)
+{
+ ea_list *t, *new;
+ unsigned i, cnt;
+ eattr *a, *d;
+ u32 seen = 0;
+ unsigned hash;
+ struct bgp_bucket *b;
+
+ /* Merge the attribute lists */
+ for(t=tmp; t->next; t=t->next)
+ ;
+ t->next = old;
+ new = alloca(ea_scan(tmp));
+ ea_merge(tmp, new);
+ t->next = NULL;
+ ea_sort(tmp);
+
+ /* Normalize attributes */
+ d = new->attrs;
+ cnt = new->count;
+ new->count = 0;
+ for(i=0; i<cnt; i++)
+ {
+ a = &new->attrs[i];
+#ifdef LOCAL_DEBUG
+ {
+ byte buf[256];
+ ea_format(a, buf);
+ DBG("\t%s\n", buf);
+ }
+#endif
+ if (EA_PROTO(a->id) != EAP_BGP)
+ continue;
+ if (EA_ID(a->id) < 32)
+ seen |= 1 << EA_ID(a->id);
+ *d = *a;
+ switch (d->type & EAF_TYPE_MASK)
+ {
+ case EAF_TYPE_INT_SET:
+ {
+ struct adata *z = alloca(sizeof(struct adata) + d->u.ptr->length);
+ z->length = d->u.ptr->length;
+ bgp_normalize_set((u32 *) z->data, (u32 *) d->u.ptr->data, z->length / 4);
+ d->u.ptr = z;
+ break;
+ }
+ default:
+ }
+ d++;
+ new->count++;
+ }
+
+ /* Hash */
+ hash = ea_hash(new);
+ for(b=p->bucket_table[hash & (p->hash_size - 1)]; b; b=b->next)
+ if (b->hash == hash && ea_same(b->eattrs, new))
+ {
+ DBG("Found bucket.\n");
+ return b;
+ }
+
+ /* Ensure that there are all mandatory attributes */
+ /* FIXME: Introduce array size macro */
+ for(i=0; i<sizeof(bgp_mandatory_attrs)/sizeof(bgp_mandatory_attrs[0]); i++)
+ if (!(seen & (1 << bgp_mandatory_attrs[i])))
+ {
+ log(L_ERR "%s: Mandatory attribute %s missing", p->p.name, bgp_attr_table[bgp_mandatory_attrs[i]].name);
+ return NULL;
+ }
+
+ /* Create new bucket */
+ DBG("Creating bucket.\n");
+ return bgp_new_bucket(p, new, hash);
+}
+
void
bgp_rt_notify(struct proto *P, net *n, rte *new, rte *old, ea_list *tmpa)
{
+ struct bgp_proto *p = (struct bgp_proto *) P;
+
DBG("BGP: Got route %I/%d\n", n->n.prefix, n->n.pxlen);
+
+ if (new)
+ {
+ struct bgp_bucket *buck = bgp_get_bucket(p, new->attrs->eattrs, tmpa);
+ if (!buck) /* Inconsistent attribute list */
+ return;
+ }
+
/* FIXME: Normalize attributes */
/* FIXME: Check next hop */
- /* FIXME: Someone might have undefined the mandatory attributes */
}
static int
@@ -47,6 +235,7 @@ bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *p
a->u.data = 2; /* Incomplete */
else
a->u.data = 0; /* IGP */
+ a++;
a->id = EA_CODE(EAP_BGP, BA_AS_PATH);
a->flags = BAF_TRANSITIVE;
@@ -66,6 +255,7 @@ bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *p
z[1] = 1; /* 1 AS */
put_u16(z+2, p->local_as);
}
+ a++;
a->id = EA_CODE(EAP_BGP, BA_NEXT_HOP);
a->flags = BAF_TRANSITIVE;
@@ -277,15 +467,6 @@ bgp_check_local_pref(struct bgp_proto *p, byte *a, int len)
return 0;
}
-struct attr_desc {
- char *name; /* FIXME: Use the same names as in filters */
- int expected_length;
- int expected_flags;
- int type;
- int (*validate)(struct bgp_proto *p, byte *attr, int len);
- void (*format)(eattr *ea, byte *buf);
-};
-
static struct attr_desc bgp_attr_table[] = {
{ NULL, -1, 0, 0, /* Undefined */
NULL, NULL },
@@ -311,8 +492,6 @@ static struct attr_desc bgp_attr_table[] = {
#endif
};
-static int bgp_mandatory_attrs[] = { BA_ORIGIN, BA_AS_PATH, BA_NEXT_HOP };
-
struct rta *
bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct linpool *pool)
{
@@ -504,3 +683,11 @@ bgp_get_attr(eattr *a, byte *buf)
bsprintf(buf, "%02x%s", i, (a->flags & BAF_TRANSITIVE) ? "[t]" : "");
return GA_NAME;
}
+
+void
+bgp_attr_init(struct bgp_proto *p)
+{
+ p->hash_size = 256;
+ p->hash_limit = p->hash_size * 4;
+ p->bucket_table = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
+}
diff --git a/proto/bgp/bgp.h b/proto/bgp/bgp.h
index 6ae594a..78bb426 100644
--- a/proto/bgp/bgp.h
+++ b/proto/bgp/bgp.h
@@ -53,6 +53,8 @@ struct bgp_proto {
ip_addr next_hop; /* Either the peer or multihop_via */
struct neighbor *neigh; /* Neighbor entry corresponding to next_hop */
ip_addr local_addr; /* Address of the local end of the link to next_hop */
+ struct bgp_bucket **bucket_table; /* Hash table of attribute buckets */
+ unsigned int hash_size, hash_count, hash_limit;
};
#define BGP_PORT 179
@@ -77,6 +79,7 @@ int bgp_rte_better(struct rte *, struct rte *);
void bgp_rt_notify(struct proto *, struct network *, struct rte *, struct rte *, struct ea_list *);
int bgp_import_control(struct proto *, struct rte **, struct ea_list **, struct linpool *);
struct ea_list *bgp_path_prepend(struct linpool *pool, struct eattr *a, struct ea_list *old, int as);
+void bgp_attr_init(struct bgp_proto *);
/* packets.c */
diff --git a/proto/bgp/packets.c b/proto/bgp/packets.c
index 2d95f9b..e85d5c0 100644
--- a/proto/bgp/packets.c
+++ b/proto/bgp/packets.c
@@ -337,6 +337,7 @@ bgp_rx_keepalive(struct bgp_conn *conn, byte *pkt, unsigned len)
case BS_OPENCONFIRM:
DBG("BGP: UP!!!\n");
conn->state = BS_ESTABLISHED;
+ bgp_attr_init(conn->bgp);
proto_notify_state(&conn->bgp->p, PS_UP);
break;
case BS_ESTABLISHED: