summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMartin Mares <mj@ucw.cz>2000-04-12 16:09:26 +0200
committerMartin Mares <mj@ucw.cz>2000-04-12 16:09:26 +0200
commitc2b28c99103a643dd29ad48152999d6dac7722fe (patch)
tree2c72d266b21e9896b508df38bb219314fed96217
parenta2d157463accf02e2db9fd3dd174b7e46dae8938 (diff)
downloadbird-c2b28c99103a643dd29ad48152999d6dac7722fe.tar
bird-c2b28c99103a643dd29ad48152999d6dac7722fe.zip
Real bucket lists.
-rw-r--r--proto/bgp/attrs.c38
-rw-r--r--proto/bgp/bgp.h20
2 files changed, 43 insertions, 15 deletions
diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c
index 350123a..e42a6ea 100644
--- a/proto/bgp/attrs.c
+++ b/proto/bgp/attrs.c
@@ -21,12 +21,6 @@
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;
@@ -39,6 +33,13 @@ struct attr_desc {
extern struct attr_desc bgp_attr_table[];
static void
+bgp_init_prefix(struct fib_node *N)
+{
+ struct bgp_prefix *p = (struct bgp_prefix *) N;
+ /* FIXME */
+}
+
+static void
bgp_normalize_set(u32 *dest, u32 *src, unsigned cnt)
{
memcpy(dest, src, sizeof(u32) * cnt);
@@ -48,7 +49,7 @@ bgp_normalize_set(u32 *dest, u32 *src, unsigned cnt)
static void
bgp_rehash_buckets(struct bgp_proto *p)
{
- struct bgp_bucket **old = p->bucket_table;
+ struct bgp_bucket **old = p->bucket_hash;
struct bgp_bucket **new;
unsigned oldn = p->hash_size;
unsigned i, e, mask;
@@ -59,14 +60,17 @@ bgp_rehash_buckets(struct bgp_proto *p)
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 *));
+ new = p->bucket_hash = 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;
+ old[i] = b->hash_next;
e = b->hash & mask;
- b->next = new[e];
+ b->hash_next = new[e];
+ if (b->hash_next)
+ b->hash_next->hash_prev = b;
+ b->hash_prev = NULL;
new[e] = b;
}
mb_free(old);
@@ -93,8 +97,11 @@ bgp_new_bucket(struct bgp_proto *p, ea_list *new, unsigned hash)
/* 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_next = p->bucket_hash[index];
+ if (b->hash_next)
+ b->hash_next->hash_prev = b;
+ p->bucket_hash[index] = b;
+ b->hash_prev = NULL;
b->hash = hash;
memcpy(b->eattrs, new, ea_size);
dest = ((byte *)b->eattrs) + ea_size_aligned;
@@ -177,7 +184,7 @@ bgp_get_bucket(struct bgp_proto *p, ea_list *old, ea_list *tmp)
/* Hash */
hash = ea_hash(new);
- for(b=p->bucket_table[hash & (p->hash_size - 1)]; b; b=b->next)
+ for(b=p->bucket_hash[hash & (p->hash_size - 1)]; b; b=b->hash_next)
if (b->hash == hash && ea_same(b->eattrs, new))
{
DBG("Found bucket.\n");
@@ -688,5 +695,8 @@ 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 *));
+ p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
+ init_list(&p->bucket_queue);
+ p->withdraw_bucket = NULL;
+ fib_init(&p->prefix_fib, p->p.pool, sizeof(struct bgp_prefix), 0, bgp_init_prefix);
}
diff --git a/proto/bgp/bgp.h b/proto/bgp/bgp.h
index 78bb426..965196b 100644
--- a/proto/bgp/bgp.h
+++ b/proto/bgp/bgp.h
@@ -9,6 +9,8 @@
#ifndef _BIRD_BGP_H_
#define _BIRD_BGP_H_
+#include "nest/route.h"
+
struct linpool;
struct eattr;
@@ -53,8 +55,24 @@ 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 */
+ struct bgp_bucket **bucket_hash; /* Hash table of attribute buckets */
unsigned int hash_size, hash_count, hash_limit;
+ struct fib prefix_fib; /* Prefixes to be sent */
+ list bucket_queue; /* Queue of buckets to send */
+ struct bgp_bucket *withdraw_bucket; /* Withdrawn routes */
+};
+
+struct bgp_prefix {
+ struct fib_node n; /* Node in prefix fib */
+ node bucket_node; /* Node in per-bucket list */
+};
+
+struct bgp_bucket {
+ struct bgp_bucket *hash_next, *hash_prev; /* Node in bucket hash table */
+ node send_node; /* Node in send queue */
+ unsigned hash; /* Hash over extended attributes */
+ list prefixes; /* Prefixes in this buckets */
+ ea_list eattrs[0]; /* Per-bucket extended attributes */
};
#define BGP_PORT 179