summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMartin Mares <mj@ucw.cz>2000-03-01 15:51:47 +0100
committerMartin Mares <mj@ucw.cz>2000-03-01 15:51:47 +0100
commit85053fce04a2cba09332a6eb667f09f9c4182392 (patch)
treebe9f97620ba18d071e81068e46e0c77b4e682e6f
parent7293c5dd8175aac4650cb48c68c7dd278a74371e (diff)
downloadbird-85053fce04a2cba09332a6eb667f09f9c4182392.tar
bird-85053fce04a2cba09332a6eb667f09f9c4182392.zip
Reimplemented neighbor cache. Now uses real hashing.
-rw-r--r--TODO16
-rw-r--r--nest/Makefile2
-rw-r--r--nest/iface.c173
-rw-r--r--nest/iface.h4
-rw-r--r--nest/neighbor.c203
5 files changed, 213 insertions, 185 deletions
diff --git a/TODO b/TODO
index 0193d94..9989d89 100644
--- a/TODO
+++ b/TODO
@@ -1,14 +1,7 @@
Core
~~~~
-- IPv6: hashing functions etc.
-
-- krt-iface: check whether the interface alias hack works
-
- better memory allocators
- real attribute cache
-- real neighbor cache
-
-- preferences of protocols
- static: check validity of route destination?
- static: allow specifying a per-route filter program for setting route attributes?
@@ -16,16 +9,10 @@ Core
- rte_update: check whether all bits not covered by masklen are zero
- rte_update: debug mode
-- netlink: import Linux route attributes to our rta's, so that they can be filtered?
-
-- config: when parsing prefix, check zero bits
-
- krt: rescan interfaces when route addition fails?
- tagging of external routes?
-- io: use poll if available
-
Commands
~~~~~~~~
- showing of routing table as seen by given protocol
@@ -53,8 +40,11 @@ Globals
Various ideas
~~~~~~~~~~~~~
+- netlink: import Linux route attributes to our rta's, so that they can be filtered?
- config: executable config files
- client: access control
+- config: when parsing prefix, check zero bits
+- io: use poll if available
- IPv6 router advertisements
- real multipath (doesn't seem to be simple at all :()
- fake multipath (even less simple)
diff --git a/nest/Makefile b/nest/Makefile
index b9cb69b..69afae1 100644
--- a/nest/Makefile
+++ b/nest/Makefile
@@ -1,4 +1,4 @@
-source=rt-table.c rt-fib.c rt-attr.c proto.c iface.c rt-dev.c password.c cli.c locks.c cmds.c
+source=rt-table.c rt-fib.c rt-attr.c proto.c iface.c rt-dev.c password.c cli.c locks.c cmds.c neighbor.c
root-rel=../
dir-name=nest
diff --git a/nest/iface.c b/nest/iface.c
index 9b4eff0..4fa2c72 100644
--- a/nest/iface.c
+++ b/nest/iface.c
@@ -1,7 +1,7 @@
/*
* BIRD -- Management of Interfaces and Neighbor Cache
*
- * (c) 1998--1999 Martin Mares <mj@ucw.cz>
+ * (c) 1998--2000 Martin Mares <mj@ucw.cz>
*
* Can be freely distributed and used under the terms of the GNU GPL.
*/
@@ -20,174 +20,6 @@ static pool *if_pool;
static void auto_router_id(void);
-/*
- * Neighbor Cache
- *
- * FIXME: Use hashing to get some real speed.
- */
-
-static slab *neigh_slab;
-static list neigh_list;
-
-static int
-if_connected(ip_addr *a, struct iface *i) /* -1=error, 1=match, 0=no match */
-{
- struct ifa *b;
-
- if (!(i->flags & IF_UP))
- return 0;
- WALK_LIST(b, i->addrs)
- {
- if (ipa_equal(*a, b->ip))
- return -1;
- if (b->flags & IA_UNNUMBERED)
- {
- if (ipa_equal(*a, b->opposite))
- return 1;
- }
- else
- {
- if (ipa_in_net(*a, b->prefix, b->pxlen))
- {
- if (ipa_equal(*a, b->prefix) || /* Network address */
- ipa_equal(*a, b->brd)) /* Broadcast */
- return -1;
- return 1;
- }
- }
- }
- return 0;
-}
-
-neighbor *
-neigh_find(struct proto *p, ip_addr *a, unsigned flags)
-{
- neighbor *n;
- int class;
- struct iface *i, *j;
-
- WALK_LIST(n, neigh_list)
- if (n->proto == p && ipa_equal(*a, n->addr))
- return n;
-
- class = ipa_classify(*a);
- if (class < 0) /* Invalid address */
- return NULL;
- if ((class & IADDR_SCOPE_MASK) < SCOPE_SITE ||
- !(class & IADDR_HOST))
- return NULL; /* Bad scope or a somecast */
-
- j = NULL;
- WALK_LIST(i, iface_list)
- switch (if_connected(a, i))
- {
- case -1:
- return NULL;
- case 1:
- if (!j) /* FIXME: Search for _optimal_ iface route? */
- j = i;
- /* Fall-thru */
- }
- if (!j && !(flags & NEF_STICKY))
- return NULL;
-
- n = sl_alloc(neigh_slab);
- n->addr = *a;
- n->iface = j;
- add_tail(&neigh_list, &n->n);
- if (j)
- add_tail(&j->neighbors, &n->if_n);
- n->proto = p;
- n->data = NULL;
- n->aux = 0;
- n->flags = flags;
- return n;
-}
-
-void
-neigh_dump(neighbor *n)
-{
- debug("%p %I ", n, n->addr);
- if (n->iface)
- debug("%s ", n->iface->name);
- else
- debug("[] ");
- debug("%s %p %08x", n->proto->name, n->data, n->aux);
- if (n->flags & NEF_STICKY)
- debug(" STICKY");
- debug("\n");
-}
-
-void
-neigh_dump_all(void)
-{
- neighbor *n;
-
- debug("Known neighbors:\n");
- WALK_LIST(n, neigh_list)
- neigh_dump(n);
- debug("\n");
-}
-
-static void
-neigh_if_up(struct iface *i)
-{
- neighbor *n;
-
- WALK_LIST(n, neigh_list)
- if (!n->iface &&
- if_connected(&n->addr, i) > 0)
- {
- n->iface = i;
- add_tail(&i->neighbors, &n->if_n);
- DBG("Waking up sticky neighbor %I\n", n->addr);
- if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
- n->proto->neigh_notify(n);
- }
-}
-
-static void
-neigh_if_down(struct iface *i)
-{
- node *x, *y;
-
- WALK_LIST_DELSAFE(x, y, i->neighbors)
- {
- neighbor *n = SKIP_BACK(neighbor, if_n, x);
- DBG("Flushing neighbor %I on %s\n", n->addr, i->name);
- rem_node(&n->if_n);
- n->iface = NULL;
- if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
- n->proto->neigh_notify(n);
- if (!(n->flags & NEF_STICKY))
- {
- rem_node(&n->n);
- sl_free(neigh_slab, n);
- }
- }
-}
-
-void
-neigh_prune(void)
-{
- neighbor *n;
- node *m;
-
- DBG("Pruning neighbors\n");
- WALK_LIST_DELSAFE(n, m, neigh_list)
- if (n->proto->core_state == FS_FLUSHING)
- {
- rem_node(&n->n);
- if (n->iface)
- rem_node(&n->if_n);
- sl_free(neigh_slab, n);
- }
-}
-
-/*
- * The Interface List
- */
-
list iface_list;
void
@@ -577,8 +409,7 @@ if_init(void)
{
if_pool = rp_new(&root_pool, "Interfaces");
init_list(&iface_list);
- neigh_slab = sl_new(if_pool, sizeof(neighbor));
- init_list(&neigh_list);
+ neigh_init(if_pool);
}
/*
diff --git a/nest/iface.h b/nest/iface.h
index 5ac9f2f..e8e4e73 100644
--- a/nest/iface.h
+++ b/nest/iface.h
@@ -14,6 +14,7 @@
extern list iface_list;
struct proto;
+struct pool;
struct ifa { /* Interface address */
node n;
@@ -116,6 +117,9 @@ neighbor *neigh_find(struct proto *, ip_addr *, unsigned flags);
void neigh_dump(neighbor *);
void neigh_dump_all(void);
void neigh_prune(void);
+void neigh_if_up(struct iface *);
+void neigh_if_down(struct iface *);
+void neigh_init(struct pool *);
/*
* Interface Pattern Lists
diff --git a/nest/neighbor.c b/nest/neighbor.c
new file mode 100644
index 0000000..e9be865
--- /dev/null
+++ b/nest/neighbor.c
@@ -0,0 +1,203 @@
+/*
+ * BIRD -- Neighbor Cache
+ *
+ * (c) 1998--2000 Martin Mares <mj@ucw.cz>
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#define LOCAL_DEBUG
+
+#include "nest/bird.h"
+#include "nest/iface.h"
+#include "nest/protocol.h"
+#include "lib/resource.h"
+
+#define NEIGH_HASH_SIZE 256
+
+static slab *neigh_slab;
+static list sticky_neigh_list, neigh_hash_table[NEIGH_HASH_SIZE];
+
+static inline unsigned int
+neigh_hash(struct proto *p, ip_addr *a)
+{
+ return (p->hash_key ^ ipa_hash(*a)) & (NEIGH_HASH_SIZE-1);
+}
+
+static int
+if_connected(ip_addr *a, struct iface *i) /* -1=error, 1=match, 0=no match */
+{
+ struct ifa *b;
+
+ if (!(i->flags & IF_UP))
+ return 0;
+ WALK_LIST(b, i->addrs)
+ {
+ if (ipa_equal(*a, b->ip))
+ return -1;
+ if (b->flags & IA_UNNUMBERED)
+ {
+ if (ipa_equal(*a, b->opposite))
+ return 1;
+ }
+ else
+ {
+ if (ipa_in_net(*a, b->prefix, b->pxlen))
+ {
+ if (ipa_equal(*a, b->prefix) || /* Network address */
+ ipa_equal(*a, b->brd)) /* Broadcast */
+ return -1;
+ return 1;
+ }
+ }
+ }
+ return 0;
+}
+
+neighbor *
+neigh_find(struct proto *p, ip_addr *a, unsigned flags)
+{
+ neighbor *n;
+ int class;
+ unsigned int h = neigh_hash(p, a);
+ struct iface *i, *j;
+
+ WALK_LIST(n, neigh_hash_table[h]) /* Search the cache */
+ if (n->proto == p && ipa_equal(*a, n->addr))
+ return n;
+
+ class = ipa_classify(*a);
+ if (class < 0) /* Invalid address */
+ return NULL;
+ if ((class & IADDR_SCOPE_MASK) < SCOPE_SITE ||
+ !(class & IADDR_HOST))
+ return NULL; /* Bad scope or a somecast */
+
+ j = NULL;
+ WALK_LIST(i, iface_list)
+ switch (if_connected(a, i))
+ {
+ case -1:
+ return NULL;
+ case 1:
+ if (!j)
+ j = i;
+ /* Fall-thru */
+ }
+ if (!j && !(flags & NEF_STICKY))
+ return NULL;
+
+ n = sl_alloc(neigh_slab);
+ n->addr = *a;
+ n->iface = j;
+ if (j)
+ {
+ add_tail(&neigh_hash_table[h], &n->n);
+ add_tail(&j->neighbors, &n->if_n);
+ }
+ else
+ add_tail(&sticky_neigh_list, &n->n);
+ n->proto = p;
+ n->data = NULL;
+ n->aux = 0;
+ n->flags = flags;
+ return n;
+}
+
+void
+neigh_dump(neighbor *n)
+{
+ debug("%p %I ", n, n->addr);
+ if (n->iface)
+ debug("%s ", n->iface->name);
+ else
+ debug("[] ");
+ debug("%s %p %08x", n->proto->name, n->data, n->aux);
+ if (n->flags & NEF_STICKY)
+ debug(" STICKY");
+ debug("\n");
+}
+
+void
+neigh_dump_all(void)
+{
+ neighbor *n;
+ int i;
+
+ debug("Known neighbors:\n");
+ WALK_LIST(n, sticky_neigh_list)
+ neigh_dump(n);
+ for(i=0; i<NEIGH_HASH_SIZE; i++)
+ WALK_LIST(n, neigh_hash_table[i]);
+ debug("\n");
+}
+
+void
+neigh_if_up(struct iface *i)
+{
+ neighbor *n, *next;
+
+ WALK_LIST_DELSAFE(n, next, sticky_neigh_list)
+ if (!n->iface &&
+ if_connected(&n->addr, i) > 0)
+ {
+ n->iface = i;
+ add_tail(&i->neighbors, &n->if_n);
+ rem_node(&n->n);
+ add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
+ DBG("Waking up sticky neighbor %I\n", n->addr);
+ if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
+ n->proto->neigh_notify(n);
+ }
+}
+
+void
+neigh_if_down(struct iface *i)
+{
+ node *x, *y;
+
+ WALK_LIST_DELSAFE(x, y, i->neighbors)
+ {
+ neighbor *n = SKIP_BACK(neighbor, if_n, x);
+ DBG("Flushing neighbor %I on %s\n", n->addr, i->name);
+ rem_node(&n->if_n);
+ n->iface = NULL;
+ if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
+ n->proto->neigh_notify(n);
+ rem_node(&n->n);
+ if (n->flags & NEF_STICKY)
+ add_tail(&sticky_neigh_list, &n->n);
+ else
+ sl_free(neigh_slab, n);
+ }
+}
+
+void
+neigh_prune(void)
+{
+ neighbor *n;
+ node *m;
+ int i;
+
+ DBG("Pruning neighbors\n");
+ for(i=0; i<NEIGH_HASH_SIZE; i++)
+ WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
+ if (n->proto->core_state == FS_FLUSHING)
+ {
+ rem_node(&n->n);
+ if (n->iface)
+ rem_node(&n->if_n);
+ sl_free(neigh_slab, n);
+ }
+}
+
+void
+neigh_init(pool *if_pool)
+{
+ int i;
+
+ neigh_slab = sl_new(if_pool, sizeof(neighbor));
+ init_list(&sticky_neigh_list);
+ for(i=0; i<NEIGH_HASH_SIZE; i++)
+ init_list(&neigh_hash_table[i]);
+}