summaryrefslogtreecommitdiff
path: root/proto/bgp/attrs.c
diff options
context:
space:
mode:
Diffstat (limited to 'proto/bgp/attrs.c')
-rw-r--r--proto/bgp/attrs.c117
1 files changed, 107 insertions, 10 deletions
diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c
index 8e25c4d2..d34e2ae3 100644
--- a/proto/bgp/attrs.c
+++ b/proto/bgp/attrs.c
@@ -621,12 +621,14 @@ bgp_encode_attrs(struct bgp_proto *p, byte *w, ea_list *attrs, int remains)
return -1;
}
+/*
static void
bgp_init_prefix(struct fib_node *N)
{
struct bgp_prefix *p = (struct bgp_prefix *) N;
p->bucket_node.next = NULL;
}
+*/
static int
bgp_compare_u32(const u32 *x, const u32 *y)
@@ -870,30 +872,125 @@ bgp_free_bucket(struct bgp_proto *p, struct bgp_bucket *buck)
mb_free(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);
+}
+
+static inline u32 px_hash_size(struct bgp_proto *p)
+{ return 1 << p->px_hash_order; }
+
+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;
+
+ 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);
+}
+
+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);
+
+ 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;
+
+ 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);
+
+ return bp;
+}
+
+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;
+ 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);
+}
+
+
void
bgp_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old UNUSED, ea_list *attrs)
{
struct bgp_proto *p = (struct bgp_proto *) P;
struct bgp_bucket *buck;
struct bgp_prefix *px;
+ rte *key;
+ u32 path_id;
DBG("BGP: Got route %I/%d %s\n", n->n.prefix, n->n.pxlen, new ? "up" : "down");
if (new)
{
+ key = new;
buck = bgp_get_bucket(p, n, attrs, new->attrs->source != RTS_BGP);
if (!buck) /* Inconsistent attribute list */
return;
}
else
{
+ key = old;
if (!(buck = p->withdraw_bucket))
{
buck = p->withdraw_bucket = mb_alloc(P->pool, sizeof(struct bgp_bucket));
init_list(&buck->prefixes);
}
}
- px = fib_get(&p->prefix_fib, &n->n.prefix, n->n.pxlen);
+ path_id = p->add_path_tx ? key->attrs->src->global_id : 0;
+ px = bgp_get_prefix(p, n->n.prefix, n->n.pxlen, path_id);
if (px->bucket_node.next)
{
DBG("\tRemoving old entry.\n");
@@ -1026,7 +1123,7 @@ bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *p
if (rr)
{
/* Handling route reflection, RFC 4456 */
- struct bgp_proto *src = (struct bgp_proto *) e->attrs->proto;
+ struct bgp_proto *src = (struct bgp_proto *) e->attrs->src->proto;
a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
if (!a)
@@ -1076,7 +1173,8 @@ bgp_import_control(struct proto *P, rte **new, ea_list **attrs, struct linpool *
{
rte *e = *new;
struct bgp_proto *p = (struct bgp_proto *) P;
- struct bgp_proto *new_bgp = (e->attrs->proto->proto == &proto_bgp) ? (struct bgp_proto *) e->attrs->proto : NULL;
+ struct bgp_proto *new_bgp = (e->attrs->src->proto->proto == &proto_bgp) ?
+ (struct bgp_proto *) e->attrs->src->proto : NULL;
if (p == new_bgp) /* Poison reverse updates */
return -1;
@@ -1115,7 +1213,7 @@ bgp_get_neighbor(rte *r)
if (e && as_path_get_first(e->u.ptr, &as))
return as;
else
- return ((struct bgp_proto *) r->attrs->proto)->remote_as;
+ return ((struct bgp_proto *) r->attrs->src->proto)->remote_as;
}
static inline int
@@ -1128,8 +1226,8 @@ rte_resolvable(rte *rt)
int
bgp_rte_better(rte *new, rte *old)
{
- struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->proto;
- struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->proto;
+ struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->src->proto;
+ struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->src->proto;
eattr *x, *y;
u32 n, o;
@@ -1263,7 +1361,7 @@ same_group(rte *r, u32 lpref, u32 lasn)
static inline int
use_deterministic_med(rte *r)
{
- struct proto *P = r->attrs->proto;
+ struct proto *P = r->attrs->src->proto;
return (P->proto == &proto_bgp) && ((struct bgp_proto *) P)->cf->deterministic_med;
}
@@ -1548,7 +1646,6 @@ bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct lin
int withdraw = 0;
bzero(a, sizeof(rta));
- a->proto = &bgp->p;
a->source = RTS_BGP;
a->scope = SCOPE_UNIVERSE;
a->cast = RTC_UNICAST;
@@ -1757,14 +1854,14 @@ bgp_get_attr(eattr *a, byte *buf, int buflen)
}
void
-bgp_attr_init(struct bgp_proto *p)
+bgp_init_bucket_table(struct bgp_proto *p)
{
p->hash_size = 256;
p->hash_limit = p->hash_size * 4;
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);
+ // fib_init(&p->prefix_fib, p->p.pool, sizeof(struct bgp_prefix), 0, bgp_init_prefix);
}
void
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-30 19:42:20 +0000