Implemented outgoing attribute cache.

3 files changed, 203 insertions, 12 deletions

diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c
index 841fe103..5c1e70db 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 6ae594a6..78bb426f 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 2d95f9b7..e85d5c07 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: