summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--nest/route.h13
-rw-r--r--nest/rt-table.c144
2 files changed, 130 insertions, 27 deletions
diff --git a/nest/route.h b/nest/route.h
index e599f5b9..97678e18 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -150,20 +150,27 @@ typedef struct network {
} net;
struct hostcache {
- struct fib htable;
+ slab *slab; /* Slab holding all hostentries */
+ struct hostentry **hash_table; /* Hash table for hostentries */
+ unsigned hash_order, hash_shift;
+ unsigned hash_max, hash_min;
+ unsigned hash_items;
+
list hostentries;
byte update_hostcache;
};
struct hostentry {
- struct fib_node fn;
node ln;
+ ip_addr addr; /* IP of host, part of key */
+ struct rtable *tab; /* Dependent table, part of key*/
+ struct hostentry *next; /* Next in hash chain */
+ unsigned hash_key; /* Hash key */
unsigned uc; /* Use count */
struct iface *iface; /* Chosen outgoing interface */
ip_addr gw; /* Chosen next hop */
byte dest; /* Chosen route destination type (RTD_...) */
byte pxlen; /* Pxlen from net that matches route */
- struct rtable *tab;
};
typedef struct rte {
diff --git a/nest/rt-table.c b/nest/rt-table.c
index f40cc806..80877698 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -1287,11 +1287,106 @@ rt_feed_baby_abort(struct proto *p)
}
}
+
+static inline unsigned
+ptr_hash(void *ptr)
+{
+ uintptr_t p = (uintptr_t) ptr;
+ return p ^ (p << 8) ^ (p >> 16);
+}
+
+static inline unsigned
+hc_hash(ip_addr a, rtable *dep)
+{
+ return (ipa_hash(a) ^ ptr_hash(dep)) & 0xffff;
+}
+
+static inline void
+hc_insert(struct hostcache *hc, struct hostentry *he)
+{
+ unsigned int k = he->hash_key >> hc->hash_shift;
+ he->next = hc->hash_table[k];
+ hc->hash_table[k] = he;
+}
+
+static inline void
+hc_remove(struct hostcache *hc, struct hostentry *he)
+{
+ struct hostentry **hep;
+ unsigned int k = he->hash_key >> hc->hash_shift;
+
+ for (hep = &hc->hash_table[k]; *hep != he; hep = &(*hep)->next);
+ *hep = he->next;
+}
+
+#define HC_DEF_ORDER 10
+#define HC_HI_MARK *4
+#define HC_HI_STEP 2
+#define HC_HI_ORDER 16 /* Must be at most 16 */
+#define HC_LO_MARK /5
+#define HC_LO_STEP 2
+#define HC_LO_ORDER 10
+
+static void
+hc_alloc_table(struct hostcache *hc, unsigned order)
+{
+ unsigned hsize = 1 << order;
+ hc->hash_order = order;
+ hc->hash_shift = 16 - order;
+ hc->hash_max = (order >= HC_HI_ORDER) ? ~0 : (hsize HC_HI_MARK);
+ hc->hash_min = (order <= HC_LO_ORDER) ? 0 : (hsize HC_LO_MARK);
+
+ hc->hash_table = mb_allocz(rt_table_pool, hsize * sizeof(struct hostentry *));
+}
+
static void
-hostentry_init(struct fib_node *fn)
+hc_resize(struct hostcache *hc, unsigned new_order)
{
- ((struct hostentry *) fn)->uc = 0;
- ((struct hostentry *) fn)->tab = NULL;
+ unsigned old_size = 1 << hc->hash_order;
+ struct hostentry **old_table = hc->hash_table;
+ struct hostentry *he, *hen;
+ int i;
+
+ hc_alloc_table(hc, new_order);
+ for (i = 0; i < old_size; i++)
+ for (he = old_table[i]; he != NULL; he=hen)
+ {
+ hen = he->next;
+ hc_insert(hc, he);
+ }
+ mb_free(old_table);
+}
+
+static struct hostentry *
+hc_new_hostentry(struct hostcache *hc, ip_addr a, rtable *dep, unsigned k)
+{
+ struct hostentry *he = sl_alloc(hc->slab);
+
+ he->addr = a;
+ he->tab = dep;
+ he->hash_key = k;
+ he->uc = 0;
+
+ add_tail(&hc->hostentries, &he->ln);
+ hc_insert(hc, he);
+
+ hc->hash_items++;
+ if (hc->hash_items > hc->hash_max)
+ hc_resize(hc, hc->hash_order + HC_HI_STEP);
+
+ return he;
+}
+
+static void
+hc_delete_hostentry(struct hostcache *hc, struct hostentry *he)
+{
+ rem_node(&he->ln);
+ hc_remove(hc, he);
+ sl_free(hc->slab, he);
+
+ hc->hash_items--;
+ if (hc->hash_items < hc->hash_min)
+ hc_resize(hc, hc->hash_order - HC_LO_STEP);
}
static void
@@ -1299,7 +1394,11 @@ rt_init_hostcache(rtable *tab)
{
struct hostcache *hc = mb_allocz(rt_table_pool, sizeof(struct hostcache));
init_list(&hc->hostentries);
- fib_init(&hc->htable, rt_table_pool, sizeof(struct hostentry), 0, hostentry_init);
+
+ hc->hash_items = 0;
+ hc_alloc_table(hc, HC_DEF_ORDER);
+ hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry));
+
tab->hostcache = hc;
}
@@ -1316,7 +1415,8 @@ rt_free_hostcache(rtable *tab)
log(L_ERR "Hostcache is not empty in table %s", tab->name);
}
- fib_free(&hc->htable);
+ rfree(hc->slab);
+ mb_free(hc->hash_table);
mb_free(hc);
}
@@ -1332,7 +1432,7 @@ rt_notify_hostcache(rtable *tab, net *net)
WALK_LIST(n, hc->hostentries)
{
struct hostentry *he = SKIP_BACK(struct hostentry, ln, n);
- if (ipa_in_net(he->fn.prefix, net->n.prefix, net->n.pxlen) &&
+ if (ipa_in_net(he->addr, net->n.prefix, net->n.pxlen) &&
(he->pxlen <= net->n.pxlen))
{
rt_schedule_hcu(tab);
@@ -1360,18 +1460,18 @@ rt_update_hostentry(rtable *tab, struct hostentry *he)
ip_addr old_gw = he->gw;
byte old_dest = he->dest;
- net *n = fib_route(&tab->fib, he->fn.prefix, MAX_PREFIX_LENGTH);
+ net *n = fib_route(&tab->fib, he->addr, MAX_PREFIX_LENGTH);
if (n && n->routes)
{
rta *a = n->routes->attrs;
if (a->dest == RTD_DEVICE)
{
- if (if_local_addr(he->fn.prefix, a->iface))
+ if (if_local_addr(he->addr, a->iface))
{
/* The host address is a local address, this is not valid */
log(L_WARN "Next hop address %I is a local address of iface %s",
- he->fn.prefix, a->iface->name);
+ he->addr, a->iface->name);
he->iface = NULL;
he->gw = IPA_NONE;
he->dest = RTD_UNREACHABLE;
@@ -1380,7 +1480,7 @@ rt_update_hostentry(rtable *tab, struct hostentry *he)
{
/* The host is directly reachable, us it as a gateway */
he->iface = a->iface;
- he->gw = he->fn.prefix;
+ he->gw = he->addr;
he->dest = RTD_ROUTER;
}
}
@@ -1419,9 +1519,7 @@ rt_update_hostcache(rtable *tab)
he = SKIP_BACK(struct hostentry, ln, n);
if (!he->uc)
{
- /* Delete a hostentry */
- rem_node(&he->ln);
- fib_delete(&hc->htable, he);
+ hc_delete_hostentry(hc, he);
continue;
}
@@ -1433,30 +1531,28 @@ rt_update_hostcache(rtable *tab)
}
static struct hostentry *
-rt_find_hostentry(rtable *tab, ip_addr *a, rtable *dep)
+rt_find_hostentry(rtable *tab, ip_addr a, rtable *dep)
{
struct hostentry *he;
if (!tab->hostcache)
rt_init_hostcache(tab);
- he = fib_get(&tab->hostcache->htable, a, MAX_PREFIX_LENGTH);
- if (!he->tab)
- {
- /* New entry */
- add_tail(&tab->hostcache->hostentries, &he->ln);
- he->tab = dep;
-
- rt_update_hostentry(tab, he);
- }
+ unsigned int k = hc_hash(a, dep);
+ struct hostcache *hc = tab->hostcache;
+ for (he = hc->hash_table[k >> hc->hash_shift]; he != NULL; he = he->next)
+ if (ipa_equal(he->addr, a) && (he->tab == dep))
+ return he;
+ he = hc_new_hostentry(hc, a, dep, k);
+ rt_update_hostentry(tab, he);
return he;
}
void
rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr *gw)
{
- rta_apply_hostentry(a, rt_find_hostentry(tab, gw, dep));
+ rta_apply_hostentry(a, rt_find_hostentry(tab, *gw, dep));
}
/*
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-25 10:23:50 +0000