4 files changed, 66 insertions, 15 deletions

diff --git a/nest/iface.h b/nest/iface.h
index af98a76..a982c17 100644
--- a/nest/iface.h
+++ b/nest/iface.h
@@ -99,6 +99,7 @@ typedef struct neighbor {
 #define NEF_STICKY 1
 
 neighbor *neigh_find(struct proto *, ip_addr *, unsigned flags);
+neighbor *neigh_find2(struct proto *p, ip_addr *a, struct iface *ifa, unsigned flags);
 
 static inline int neigh_connected_to(struct proto *p, ip_addr *a, struct iface *i)
 {
diff --git a/nest/neighbor.c b/nest/neighbor.c
index 2c5af6a..a44667f 100644
--- a/nest/neighbor.c
+++ b/nest/neighbor.c
@@ -100,13 +100,21 @@ if_connected(ip_addr *a, struct iface *i) /* -1=error, 1=match, 0=no match */
  * IP address, neigh_find() returns %NULL.
  */
 
+
 neighbor *
 neigh_find(struct proto *p, ip_addr *a, unsigned flags)
 {
+  return neigh_find2(p, a, NULL, flags);
+}
+
+
+neighbor *
+neigh_find2(struct proto *p, ip_addr *a, struct iface *ifa, unsigned flags)
+{
   neighbor *n;
   int class, scope = SCOPE_HOST;
   unsigned int h = neigh_hash(p, a);
-  struct iface *i, *j;
+  struct iface *i;
 
   WALK_LIST(n, neigh_hash_table[h])	/* Search the cache */
     if (n->proto == p && ipa_equal(*a, n->addr))
@@ -115,27 +123,31 @@ neigh_find(struct proto *p, ip_addr *a, unsigned flags)
   class = ipa_classify(*a);
   if (class < 0)			/* Invalid address */
     return NULL;
-  if ((class & IADDR_SCOPE_MASK) < SCOPE_SITE ||
+  if (((class & IADDR_SCOPE_MASK) == SCOPE_HOST) ||
+      (((class & IADDR_SCOPE_MASK) == SCOPE_LINK) && (ifa == NULL)) ||
       !(class & IADDR_HOST))
     return NULL;			/* Bad scope or a somecast */
 
-  j = NULL;
-  WALK_LIST(i, iface_list)
-    if ((scope = if_connected(a, i)) >= 0)
-      {
-	j = i;
-	break;
-      }
-  if (!j && !(flags & NEF_STICKY))
+  if (ifa)
+    scope = if_connected(a, ifa);
+  else
+    WALK_LIST(i, iface_list)
+      if ((scope = if_connected(a, i)) >= 0)
+	{
+	  ifa = i;
+	  break;
+	}
+
+  if (!ifa && !(flags & NEF_STICKY))
     return NULL;
 
   n = sl_alloc(neigh_slab);
   n->addr = *a;
-  n->iface = j;
-  if (j)
+  n->iface = ifa;
+  if (ifa)
     {
       add_tail(&neigh_hash_table[h], &n->n);
-      add_tail(&j->neighbors, &n->if_n);
+      add_tail(&ifa->neighbors, &n->if_n);
     }
   else
     {
diff --git a/nest/route.h b/nest/route.h
index 1bd23a6..e45a8c6 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -37,6 +37,7 @@ struct fib_node {
   byte pxlen;
   byte flags;				/* User-defined */
   byte x0, x1;				/* User-defined */
+  u32 uid;				/* Unique ID based on hash */
   ip_addr prefix;			/* In host order */
 };
 
diff --git a/nest/rt-fib.c b/nest/rt-fib.c
index 8d76f26..510aa76 100644
--- a/nest/rt-fib.c
+++ b/nest/rt-fib.c
@@ -172,6 +172,28 @@ fib_find(struct fib *f, ip_addr *a, int len)
   return e;
 }
 
+/*
+int
+fib_histogram(struct fib *f)
+{
+  log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries);
+
+  int i, j;
+  struct fib_node *e;
+
+  for (i = 0; i < f->hash_size; i++)
+    {
+      j = 0;
+      for (e = f->hash_table[i]; e != NULL; e = e->next)
+	j++;
+      if (j > 0)
+        log(L_WARN "Histogram line %d: %d", i, j);
+    }
+
+  log(L_WARN "Histogram dump end");
+}
+*/
+
 /**
  * fib_get - find or create a FIB node
  * @f: FIB to work with
@@ -187,6 +209,7 @@ fib_get(struct fib *f, ip_addr *a, int len)
   unsigned int h = ipa_hash(*a);
   struct fib_node **ee = f->hash_table + (h >> f->hash_shift);
   struct fib_node *g, *e = *ee;
+  u32 uid = h << 16;
 
   while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)))
     e = e->next;
@@ -196,17 +219,31 @@ fib_get(struct fib *f, ip_addr *a, int len)
   if (len < 0 || len > BITS_PER_IP_ADDRESS || !ip_is_prefix(*a,len))
     bug("fib_get() called for invalid address");
 #endif
+
+  while ((g = *ee) && g->uid < uid)
+    ee = &g->next;
+  while ((g = *ee) && g->uid == uid)
+    {
+      ee = &g->next;
+      uid++;
+    }
+
+  if ((uid >> 16) != h)
+    log(L_ERR "FIB hash table chains are too long");
+
+  // log (L_WARN "FIB_GET %I %x %x", *a, h, uid);
+
   e = sl_alloc(f->fib_slab);
   e->prefix = *a;
   e->pxlen = len;
-  while ((g = *ee) && ipa_hash(g->prefix) < h)
-    ee = &g->next;
   e->next = *ee;
+  e->uid = uid;
   *ee = e;
   e->readers = NULL;
   f->init(e);
   if (f->entries++ > f->entries_max)
     fib_rehash(f, HASH_HI_STEP);
+
   return e;
 }