summaryrefslogtreecommitdiffstats
path: root/nest
diff options
context:
space:
mode:
authorOndrej Zajicek <santiago@crfreenet.org>2010-07-27 18:20:12 +0200
committerOndrej Zajicek <santiago@crfreenet.org>2010-07-27 18:20:12 +0200
commitc477f48916d74c2db6156145851f9536ae0a0a6c (patch)
treeaac42a01e92dadaa97ee59f1236a6d71567fbe18 /nest
parent7f0d245a5e6d2d789e1fce4b5388ea69aba3b428 (diff)
downloadbird-c477f48916d74c2db6156145851f9536ae0a0a6c.tar
bird-c477f48916d74c2db6156145851f9536ae0a0a6c.zip
Hostcache should use trie to filter relevant route changes.
Diffstat (limited to 'nest')
-rw-r--r--nest/route.h6
-rw-r--r--nest/rt-table.c30
2 files changed, 18 insertions, 18 deletions
diff --git a/nest/route.h b/nest/route.h
index 97678e1..45b78e3 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -155,8 +155,9 @@ struct hostcache {
unsigned hash_order, hash_shift;
unsigned hash_max, hash_min;
unsigned hash_items;
-
- list hostentries;
+ linpool *lp; /* Linpool for trie */
+ struct f_trie *trie; /* Trie of prefixes that might affect hostentries */
+ list hostentries; /* List of all hostentries */
byte update_hostcache;
};
@@ -170,7 +171,6 @@ struct hostentry {
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 */
};
typedef struct rte {
diff --git a/nest/rt-table.c b/nest/rt-table.c
index 8087769..af1a920 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -1399,6 +1399,9 @@ rt_init_hostcache(rtable *tab)
hc_alloc_table(hc, HC_DEF_ORDER);
hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry));
+ hc->lp = lp_new(rt_table_pool, 1008);
+ hc->trie = f_new_trie(hc->lp);
+
tab->hostcache = hc;
}
@@ -1416,6 +1419,7 @@ rt_free_hostcache(rtable *tab)
}
rfree(hc->slab);
+ rfree(hc->lp);
mb_free(hc->hash_table);
mb_free(hc);
}
@@ -1428,17 +1432,8 @@ rt_notify_hostcache(rtable *tab, net *net)
if (tab->hcu_scheduled)
return;
- node *n;
- WALK_LIST(n, hc->hostentries)
- {
- struct hostentry *he = SKIP_BACK(struct hostentry, ln, n);
- if (ipa_in_net(he->addr, net->n.prefix, net->n.pxlen) &&
- (he->pxlen <= net->n.pxlen))
- {
- rt_schedule_hcu(tab);
- return;
- }
- }
+ if (trie_match_prefix(hc->trie, net->n.prefix, net->n.pxlen))
+ rt_schedule_hcu(tab);
}
static int
@@ -1459,11 +1454,13 @@ rt_update_hostentry(rtable *tab, struct hostentry *he)
struct iface *old_iface = he->iface;
ip_addr old_gw = he->gw;
byte old_dest = he->dest;
+ int pxlen = 0;
net *n = fib_route(&tab->fib, he->addr, MAX_PREFIX_LENGTH);
if (n && n->routes)
{
rta *a = n->routes->attrs;
+ pxlen = n->n.pxlen;
if (a->dest == RTD_DEVICE)
{
@@ -1491,8 +1488,6 @@ rt_update_hostentry(rtable *tab, struct hostentry *he)
he->gw = a->gw;
he->dest = a->dest;
}
-
- he->pxlen = n->n.pxlen;
}
else
{
@@ -1500,10 +1495,11 @@ rt_update_hostentry(rtable *tab, struct hostentry *he)
he->iface = NULL;
he->gw = IPA_NONE;
he->dest = RTD_UNREACHABLE;
-
- he->pxlen = 0;
}
+ /* Add a prefix range to the trie */
+ trie_add_prefix(tab->hostcache->trie, he->addr, MAX_PREFIX_LENGTH, pxlen, MAX_PREFIX_LENGTH);
+
return hostentry_diff(he, old_iface, old_gw, old_dest);
}
@@ -1514,6 +1510,10 @@ rt_update_hostcache(rtable *tab)
struct hostentry *he;
node *n, *x;
+ /* Reset the trie */
+ lp_flush(hc->lp);
+ hc->trie = f_new_trie(hc->lp);
+
WALK_LIST_DELSAFE(n, x, hc->hostentries)
{
he = SKIP_BACK(struct hostentry, ln, n);