- Rewrote whole interface logic. Removed support for multiple addresses per

  interface since it makes much trouble everywhere. Instead, we understand
  secondary addresses as subinterfaces.

- In case interface addresses or basic flags change, we simply convert it
  to a down/up sequence.

- Implemented the universal neighbour cache. (Just forget what did previous
  includes say of neighbour caching, this one is brand new.)

5 files changed, 244 insertions, 95 deletions

diff --git a/TODO b/TODO
index f1ad0278..ded7ab96 100644
--- a/TODO
+++ b/TODO
@@ -1,15 +1,17 @@
 Core
 ~~~~
+* router id
+
 - fake multipath?
 - config file: symbolic constants?
 - counters (according to SNMP MIB?)
 - generation of subnet mask ICMP's for v6?
-- neighbor cache: local broadcast address?
 - ipv4: recognize site scope addresses?
 - ifdef out some debugging code?
 - better memory allocators
 - default preferences of protocols: prefer BGP over OSPF/RIP external routes?
 - all internal tables are in host order
+- secondary addresses -> subinterfaces
 
 - filter: logging of dropped routes (?)
 - limitation of memory consumption: per-process and total (?)
diff --git a/nest/iface.c b/nest/iface.c
index 79a7b7d9..5342f120 100644
--- a/nest/iface.c
+++ b/nest/iface.c
@@ -1,24 +1,168 @@
 /*
- *	BIRD -- Management of Interfaces
+ *	BIRD -- Management of Interfaces and Neighbor Cache
  *
  *	(c) 1998 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"
 
-list iface_list;
-
 static pool *if_pool;
 
+/*
+ *	Neighbor Cache
+ *
+ *	FIXME: Use hashing to get some real speed.
+ *	FIXME: Cleanup when a protocol goes down.
+ */
+
+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 */
+{
+  if (i->flags & (IF_ADMIN_DOWN | IF_IGNORE))
+    return 0;
+  if ((i->flags & IF_UNNUMBERED) && ipa_equal(*a, i->opposite))
+    return 1;
+  if (!ipa_in_net(*a, i->prefix, i->pxlen))
+    return 0;
+  if (ipa_equal(*a, i->prefix) ||	/* Network address */
+      ipa_equal(*a, i->brd) ||		/* Broadcast */
+      ipa_equal(*a, i->ip))		/* Our own address */
+    return -1;
+  if (!(i->flags & IF_UP))
+    return 0;
+  return 1;
+}
+
+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 || j->pxlen > i->pxlen)
+	  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)
+    {
+      n->sibling = j->neigh;
+      j->neigh = n;
+    }
+  else
+    n->sibling = NULL;
+  n->proto = p;
+  n->data = NULL;
+  n->flags = flags;
+  return n;
+}
+
 void
-if_dump(struct iface *i)
+neigh_dump(neighbor *n)
+{
+  debug("%p %08x ", n, _I(n->addr));
+  if (n->iface)
+    debug("%s ", n->iface->name);
+  else
+    debug("[] ");
+  debug("%s %p", n->proto->name, n->data);
+  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;
+	n->sibling = i->neigh;
+	i->neigh = n;
+	DBG("Waking up sticky neighbor %08x\n", _I(n->addr));
+	n->proto->neigh_notify(n);
+      }
+}
+
+static void
+neigh_if_down(struct iface *i)
 {
-  struct ifa *a;
+  neighbor *n, *m;
 
+  for(m=i->neigh; n = m;)
+    {
+      m = n->sibling;
+      DBG("Flushing neighbor %08x on %s\n", _I(n->addr), n->iface->name);
+      n->iface = NULL;
+      n->proto->neigh_notify(n);
+      if (!(n->flags & NEF_STICKY))
+	{
+	  rem_node(&n->n);
+	  sl_free(neigh_slab, n);
+	}
+      i->neigh = NULL;
+    }
+}
+
+/*
+ *	The Interface List
+ */
+
+list iface_list;
+
+void
+if_dump(struct iface *i)
+{
   debug("IF%d: %s", i->index, i->name);
   if (i->flags & IF_ADMIN_DOWN)
     debug(" ADMIN-DOWN");
@@ -39,8 +183,7 @@ if_dump(struct iface *i)
   if (i->flags & IF_IGNORE)
     debug(" IGN");
   debug(" MTU=%d\n", i->mtu);
-  for(a=i->ifa; a; a=a->next)
-    debug("\t%08x, net %08x/%-2d bc %08x -> %08x\n", _I(a->ip), _I(a->prefix), a->pxlen, _I(a->brd), _I(a->opposite));
+  debug("\t%08x, net %08x/%-2d bc %08x -> %08x\n", _I(i->ip), _I(i->prefix), i->pxlen, _I(i->brd), _I(i->opposite));
 }
 
 void
@@ -54,64 +197,36 @@ if_dump_all(void)
   debug("\n");
 }
 
-struct if_with_a {
-  struct iface i;
-  struct ifa a[0];
-};
-
-static struct iface *
-if_copy(struct iface *j)
+static inline int
+if_change_too_big_p(struct iface *i, struct iface *j)
 {
-  int len;
-  struct if_with_a *w;
-  struct iface *i;
-  struct ifa *a, **b, *c;
-
-  len = 0;
-  for(a=j->ifa; a; a=a->next)
-    len++;
-  w = mb_alloc(if_pool, sizeof(struct if_with_a) + len*sizeof(struct ifa));
-  i = &w->i;
-  c = w->a;
-  memcpy(i, j, sizeof(struct iface));
-  b = &i->ifa;
-  a = j->ifa;
-  while (a)
-    {
-      *b = c;
-      memcpy(c, a, sizeof(struct ifa));
-      b = &c->next;
-      a = a->next;
-      c++;
-    }
-  *b = NULL;
-  return i;
+  if (!ipa_equal(i->ip, j->ip) ||
+      !ipa_equal(i->prefix, j->prefix) ||
+      i->pxlen != j->pxlen ||
+      !ipa_equal(i->brd, j->brd) ||
+      !ipa_equal(i->opposite, j->opposite))
+    return 1;				/* Changed addresses */
+  if ((i->flags ^ j->flags) & ~(IF_UP | IF_ADMIN_DOWN | IF_UPDATED))
+    return 1;
+  return 0;
 }
 
 static inline void
-if_free(struct iface *i)
+if_copy(struct iface *to, struct iface *from)
 {
-  mb_free(i);
+  to->flags = from->flags;
+  to->mtu = from->mtu;
+  to->index = from->index;
 }
 
 static unsigned
 if_changed(struct iface *i, struct iface *j)
 {
   unsigned f = 0;
-  struct ifa *x, *y;
 
-  x = i->ifa;
-  y = j->ifa;
-  while (x && y)
-    {
-      x = x->next;
-      y = y->next;
-    }
-  if (x || y)
-    f |= IF_CHANGE_ADDR;
   if (i->mtu != j->mtu)
     f |= IF_CHANGE_MTU;
-  if (i->flags != j->flags)
+  if ((i->flags ^ j->flags) & ~IF_UPDATED)
     {
       f |= IF_CHANGE_FLAGS;
       if ((i->flags ^ j->flags) & IF_UP)
@@ -127,30 +242,51 @@ static void
 if_notify_change(unsigned c, struct iface *old, struct iface *new)
 {
   debug("Interface change notification (%x) for %s\n", c, new->name);
+  if (old)
+    if_dump(old);
+  if (new)
+    if_dump(new);
+
+  if (c & IF_CHANGE_UP)
+    neigh_if_up(new);
+
+  /* FIXME: Notify protocols here */
+
+  if (c & IF_CHANGE_DOWN)
+    neigh_if_down(old);
 }
 
 void
 if_update(struct iface *new)
 {
   struct iface *i;
+  unsigned c;
 
   WALK_LIST(i, iface_list)
     if (!strcmp(new->name, i->name))
       {
-	unsigned c = if_changed(i, new);
-	if (c)
+	if (if_change_too_big_p(i, new)) /* Changed a lot, convert it to down/up */
 	  {
-	    struct iface *j = if_copy(new);
-	    if_notify_change(c, i, j);
-	    insert_node(&j->n, &i->n);
+	    DBG("Interface %s changed too much -- forcing down/up transition\n", i->name);
+	    i->flags &= ~IF_UP;
+	    if_notify_change(IF_CHANGE_DOWN | IF_CHANGE_FLAGS, i, NULL);
 	    rem_node(&i->n);
-	    if_free(i);
+	    goto newif;
 	  }
+	c = if_changed(i, new);
+	if_copy(i, new);		/* Even if c==0 as we might need to update i->index et al. */
+	i->flags |= IF_UPDATED;
+	if (c)
+	  if_notify_change(c, i, new);
 	return;
       }
-  i = if_copy(new);
+
+  i = mb_alloc(if_pool, sizeof(struct iface));
+newif:
+  memcpy(i, new, sizeof(*i));
+  i->flags |= IF_UPDATED;
   add_tail(&iface_list, &i->n);
-  if_notify_change(IF_CHANGE_UP | IF_CHANGE_FLAGS | IF_CHANGE_MTU | IF_CHANGE_ADDR, NULL, i);
+  if_notify_change(IF_CHANGE_UP | IF_CHANGE_FLAGS | IF_CHANGE_MTU, NULL, i);
 }
 
 void
@@ -174,4 +310,6 @@ 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);
 }
diff --git a/nest/iface.h b/nest/iface.h
index 4df98739..c3594493 100644
--- a/nest/iface.h
+++ b/nest/iface.h
@@ -18,8 +18,13 @@ struct iface {
   char name[16];
   unsigned flags;
   unsigned mtu;
-  struct ifa *ifa;			/* First address is primary */
   unsigned index;			/* OS-dependent interface index */
+  ip_addr ip;				/* IP address of this host */
+  ip_addr prefix;			/* Network prefix */
+  unsigned pxlen;			/* Prefix length */
+  ip_addr brd;				/* Broadcast address */
+  ip_addr opposite;			/* Opposite end of a point-to-point link */
+  struct neighbor *neigh;		/* List of neighbors on this interface */
 };
 
 #define IF_UP 1
@@ -33,25 +38,12 @@ struct iface {
 #define IF_IGNORE 256
 #define IF_UPDATED 0x1000		/* Touched in last scan */
 
-/* Interface address */
-
-struct ifa {
-  struct ifa *next;
-  ip_addr ip;				/* IP address of this host */
-  ip_addr prefix;			/* Network prefix */
-  unsigned pxlen;			/* Prefix length */
-  ip_addr brd;				/* Broadcast address */
-  ip_addr opposite;			/* Opposite end of a point-to-point link */
-  struct neighbor *neigh;		/* List of neighbors on this interface */
-};
-
 /* Interface change events */
 
 #define IF_CHANGE_UP 1
 #define IF_CHANGE_DOWN 2
-#define IF_CHANGE_FLAGS 4
+#define IF_CHANGE_FLAGS 4		/* Can be converted to down/up internally */
 #define IF_CHANGE_MTU 8
-#define IF_CHANGE_ADDR 16
 
 void if_init(void);
 void if_dump(struct iface *);
@@ -59,4 +51,39 @@ void if_dump_all(void);
 void if_update(struct iface *);
 void if_end_update(void);
 
+/*
+ *	Neighbor Cache. We hold (direct neighbor, protocol) pairs we've seen
+ *	along with pointer to protocol-specific data.
+ *
+ *	The primary goal of this cache is to quickly validate all incoming
+ *	packets if their have been sent by our neighbors and to notify
+ *	protocols about lost neighbors when an interface goes down.
+ *
+ *	Anyway, it can also contain `sticky' entries for currently unreachable
+ *	addresses which cause notification when the address becomes a neighbor.
+ */
+
+typedef struct neighbor {
+  node n;				/* Node in global neighbor list */
+  ip_addr addr;				/* Address of the neighbor */
+  struct iface *iface;			/* Interface address it's connected to */
+  struct neighbor *sibling;		/* Next in per-device chain */
+  struct proto *proto;			/* Protocol this belongs to */
+  void *data;				/* Protocol-specific data */
+  unsigned flags;
+} neighbor;
+
+#define NEF_STICKY 1
+
+/*
+ * Find neighbor or return NULL if it doesn't exist.
+ * If you specify flags == NEF_STICKY, a sticky entry is created if the
+ * address is not a neighbor, but NULL can still be returned if the address
+ * given is invalid.
+ */
+neighbor *neigh_find(struct proto *, ip_addr *, unsigned flags);
+
+void neigh_dump(neighbor *);
+void neigh_dump_all(void);
+
 #endif
diff --git a/nest/protocol.h b/nest/protocol.h
index 26db2489..45776ecb 100644
--- a/nest/protocol.h
+++ b/nest/protocol.h
@@ -55,7 +55,7 @@ struct proto {
 
   void (*if_notify)(struct proto *, struct iface *new, struct iface *old);
   void (*rt_notify)(struct proto *, struct rte *new, struct rte *old);
-  void (*neigh_lost_notify)(struct proto *, struct neighbor *neigh);
+  void (*neigh_notify)(struct neighbor *neigh);
   void (*dump)(struct proto *);			/* Debugging dump */
   void (*start)(struct proto *);		/* Start the instance */
   void (*shutdown)(struct proto *, int time);	/* Stop the instance */
diff --git a/nest/route.h b/nest/route.h
index 255d31a5..f00dded7 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -13,6 +13,7 @@
 #include "lib/timer.h"
 
 struct protocol;
+struct proto;
 
 /*
  *	Generic data structure for storing network prefixes. Also used
@@ -61,25 +62,6 @@ void fib_free(struct fib *);		/* Destroy the fib */
 	} while (0)
 
 /*
- *	Neighbor Cache. We hold (direct neighbor, protocol) pairs we've seen
- *	along with pointer to protocol-specific data.
- *
- *	The primary goal of this cache is to quickly validate all incoming
- *	packets if their have been sent by our neighbors and to notify
- *	protocols about lost neighbors when an interface goes down.
- */
-
-typedef struct neighbor {
-  ip_addr addr;				/* Address of the neighbor */
-  struct next *next;			/* Next in hashed chain */
-  struct next *sibling;			/* Next in per-device chain */
-  struct proto *proto;			/* Protocol this belongs to */
-  void *data;				/* Protocol-specific data */
-} neighbor;
-
-neighbor *neigh_find(ip_addr *);	/* NULL if not a neighbor */
-
-/*
  *	Master Routing Tables. Generally speaking, each of them is a list
  *	of FIB (one per TOS) with each entry pointing to a list of route entries
  *	representing routes to given network.