summaryrefslogtreecommitdiff
path: root/proto/bgp
diff options
context:
space:
mode:
Diffstat (limited to 'proto/bgp')
-rw-r--r--proto/bgp/attrs.c74
-rw-r--r--proto/bgp/bgp.c1
-rw-r--r--proto/bgp/bgp.h5
-rw-r--r--proto/bgp/packets.c3
4 files changed, 22 insertions, 61 deletions
diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c
index d34e2ae3..1d37bfd7 100644
--- a/proto/bgp/attrs.c
+++ b/proto/bgp/attrs.c
@@ -58,6 +58,7 @@
* bgp_reconstruct_4b_attrs()).
*/
+
static byte bgp_mandatory_attrs[] = { BA_ORIGIN, BA_AS_PATH
#ifndef IPV6
,BA_NEXT_HOP
@@ -875,70 +876,40 @@ bgp_free_bucket(struct bgp_proto *p, struct bgp_bucket *buck)
/* Prefix hash table */
-static inline u32 prefix_hash(ip_addr prefix, int pxlen, u32 path_id, u32 order)
-{
- u32 x = ipa_hash(prefix) + pxlen + path_id;
- return (x * 2902958171u) >> (32 - order);
-}
+#define PXH_KEY(n1) n1->n.prefix, n1->n.pxlen, n1->path_id
+#define PXH_NEXT(n) n->next
+#define PXH_EQ(p1,l1,i1,p2,l2,i2) ipa_equal(p1, p2) && l1 == l2 && i1 == i2
+#define PXH_FN(p,l,i) ipa_hash32(p) ^ u32_hash((l << 16) ^ i)
+
+#define PXH_REHASH bgp_pxh_rehash
+#define PXH_PARAMS /8, *2, 2, 2, 8, 20
+
-static inline u32 px_hash_size(struct bgp_proto *p)
-{ return 1 << p->px_hash_order; }
+HASH_DEFINE_REHASH_FN(PXH, struct bgp_prefix)
void
bgp_init_prefix_table(struct bgp_proto *p, u32 order)
{
- p->px_hash_count = 0;
- p->px_hash_order = order;
- p->prefix_table = mb_allocz(p->p.pool, px_hash_size(p) * sizeof(struct bgp_prefix *));
- p->prefix_slab = sl_new(p->p.pool, sizeof(struct bgp_prefix));
-}
-
-static void
-bgp_rehash_prefix_table(struct bgp_proto *p, int step)
-{
- struct bgp_prefix **old_tab, *px, *px_next;
- u32 old_size, hash, i;
+ HASH_INIT(p->prefix_hash, p->p.pool, order);
- old_tab = p->prefix_table;
- old_size = px_hash_size(p);
-
- p->px_hash_order += step;
- p->prefix_table = mb_allocz(p->p.pool, px_hash_size(p) * sizeof(struct bgp_prefix *));
-
- for (i = 0; i < old_size; i++)
- for (px = old_tab[i]; px; px = px_next)
- {
- px_next = px->next;
- hash = prefix_hash(px->n.prefix, px->n.pxlen, px->path_id, p->px_hash_order);
- px->next = p->prefix_table[hash];
- p->prefix_table[hash] = px;
- }
-
- mb_free(old_tab);
+ p->prefix_slab = sl_new(p->p.pool, sizeof(struct bgp_prefix));
}
static struct bgp_prefix *
bgp_get_prefix(struct bgp_proto *p, ip_addr prefix, int pxlen, u32 path_id)
{
- struct bgp_prefix *bp;
- u32 hash = prefix_hash(prefix, pxlen, path_id, p->px_hash_order);
+ struct bgp_prefix *bp = HASH_FIND(p->prefix_hash, PXH, prefix, pxlen, path_id);
- for (bp = p->prefix_table[hash]; bp; bp = bp->next)
- if (bp->n.pxlen == pxlen && ipa_equal(bp->n.prefix, prefix) && bp->path_id == path_id)
- return bp;
+ if (bp)
+ return bp;
bp = sl_alloc(p->prefix_slab);
bp->n.prefix = prefix;
bp->n.pxlen = pxlen;
bp->path_id = path_id;
- bp->next = p->prefix_table[hash];
- p->prefix_table[hash] = bp;
-
bp->bucket_node.next = NULL;
- p->px_hash_count++;
- if ((p->px_hash_count > px_hash_size(p)) && (p->px_hash_order < 18))
- bgp_rehash_prefix_table(p, 1);
+ HASH_INSERT2(p->prefix_hash, PXH, p->p.pool, bp);
return bp;
}
@@ -946,19 +917,8 @@ bgp_get_prefix(struct bgp_proto *p, ip_addr prefix, int pxlen, u32 path_id)
void
bgp_free_prefix(struct bgp_proto *p, struct bgp_prefix *bp)
{
- struct bgp_prefix **bpp;
- u32 hash = prefix_hash(bp->n.prefix, bp->n.pxlen, bp->path_id, p->px_hash_order);
-
- for (bpp = &p->prefix_table[hash]; *bpp; *bpp = (*bpp)->next)
- if (*bpp == bp)
- break;
-
- *bpp = bp->next;
+ HASH_REMOVE2(p->prefix_hash, PXH, p->p.pool, bp);
sl_free(p->prefix_slab, bp);
-
- p->px_hash_count--;
- if ((p->px_hash_count < (px_hash_size(p) / 4)) && (p->px_hash_order > 10))
- bgp_rehash_prefix_table(p, -1);
}
diff --git a/proto/bgp/bgp.c b/proto/bgp/bgp.c
index 98c49b30..a748669d 100644
--- a/proto/bgp/bgp.c
+++ b/proto/bgp/bgp.c
@@ -68,6 +68,7 @@
#include "bgp.h"
+
struct linpool *bgp_linpool; /* Global temporary pool */
static sock *bgp_listen_sk; /* Global listening socket */
static int bgp_counter; /* Number of protocol instances using the listening socket */
diff --git a/proto/bgp/bgp.h b/proto/bgp/bgp.h
index a35c362c..170b6bbe 100644
--- a/proto/bgp/bgp.h
+++ b/proto/bgp/bgp.h
@@ -12,6 +12,7 @@
#include <stdint.h>
#include "nest/route.h"
#include "nest/bfd.h"
+#include "lib/hash.h"
struct linpool;
struct eattr;
@@ -118,10 +119,8 @@ struct bgp_proto {
struct timer *startup_timer; /* Timer used to delay protocol startup due to previous errors (startup_delay) */
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 */
- struct bgp_prefix **prefix_table; /* Prefixes to be sent */
+ HASH(struct bgp_prefix) prefix_hash; /* Prefixes to be sent */
slab *prefix_slab; /* Slab holding prefix nodes */
- u32 px_hash_order, px_hash_count;
list bucket_queue; /* Queue of buckets to send */
struct bgp_bucket *withdraw_bucket; /* Withdrawn routes */
unsigned startup_delay; /* Time to delay protocol startup by due to errors */
diff --git a/proto/bgp/packets.c b/proto/bgp/packets.c
index 42064332..649d8078 100644
--- a/proto/bgp/packets.c
+++ b/proto/bgp/packets.c
@@ -244,7 +244,7 @@ bgp_encode_prefixes(struct bgp_proto *p, byte *w, struct bgp_bucket *buck, unsig
ip_addr a;
int bytes;
- while (!EMPTY_LIST(buck->prefixes) && remains >= (1+sizeof(ip_addr)))
+ while (!EMPTY_LIST(buck->prefixes) && (remains >= (5+sizeof(ip_addr))))
{
struct bgp_prefix *px = SKIP_BACK(struct bgp_prefix, bucket_node, HEAD(buck->prefixes));
DBG("\tDequeued route %I/%d\n", px->n.prefix, px->n.pxlen);
@@ -253,6 +253,7 @@ bgp_encode_prefixes(struct bgp_proto *p, byte *w, struct bgp_bucket *buck, unsig
{
put_u32(w, px->path_id);
w += 4;
+ remains -= 4;
}
*w++ = px->n.pxlen;
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-24 18:01:22 +0000