From 7969ea3b41db05294c78a5e0ec0bd3c29ae8c549 Mon Sep 17 00:00:00 2001
From: Ondrej Zajicek <santiago@crfreenet.org>
Date: Sun, 11 Apr 2010 10:19:54 +0200
Subject: Fixes a bug in OSPF on NBMA interfaces.

A very tricky bug. OSPF on NBMA interfaces probably never really worked.
When a packet was sent to multiple destinations, the checksum was
calculated multiple times from a packet with already filled checksum
field (from previous calculation). Therefore, many packets were sent
with an invalid checksum.
---
 proto/ospf/packet.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/proto/ospf/packet.c b/proto/ospf/packet.c
index b47cbfc..e78eeea 100644
--- a/proto/ospf/packet.c
+++ b/proto/ospf/packet.c
@@ -76,6 +76,7 @@ ospf_pkt_finalize(struct ospf_iface *ifa, struct ospf_packet *pkt)
       }
       password_cpy(pkt->u.password, passwd->password, sizeof(union ospf_auth));
     case OSPF_AUTH_NONE:
+      pkt->checksum = 0;
       pkt->checksum = ipsum_calculate(pkt, sizeof(struct ospf_packet) -
                                   sizeof(union ospf_auth), (pkt + 1),
 				  ntohs(pkt->length) -
-- 
cgit v1.2.3


From 6e8067609673afef9eb9e786f4e43a73a3b544f0 Mon Sep 17 00:00:00 2001
From: Ondrej Zajicek <santiago@crfreenet.org>
Date: Sun, 11 Apr 2010 12:22:47 +0200
Subject: Fixes next hop calculation on NBMA and parallel PTP links.

---
 proto/ospf/neighbor.c | 21 ------------
 proto/ospf/neighbor.h |  1 -
 proto/ospf/rt.c       | 89 +++++++++++++++++++++++++++++++++++++++------------
 proto/ospf/topology.h |  3 ++
 4 files changed, 71 insertions(+), 43 deletions(-)

diff --git a/proto/ospf/neighbor.c b/proto/ospf/neighbor.c
index 69c5880..2563abd 100644
--- a/proto/ospf/neighbor.c
+++ b/proto/ospf/neighbor.c
@@ -536,27 +536,6 @@ find_neigh(struct ospf_iface *ifa, u32 rid)
   return NULL;
 }
 
-
-/* Find a closest neighbor which is at least 2-Way */
-struct ospf_neighbor *
-find_neigh_noifa(struct proto_ospf *po, u32 rid)
-{
-  struct ospf_neighbor *n = NULL, *m;
-  struct ospf_iface *ifa;
-
-  WALK_LIST(ifa, po->iface_list) if ((m = find_neigh(ifa, rid)) != NULL)
-  {
-    if (m->state >= NEIGHBOR_2WAY)
-    {
-      if (n == NULL)
-	n = m;
-      else if (m->ifa->cost < n->ifa->cost)
-	n = m;
-    }
-  }
-  return n;
-}
-
 struct ospf_area *
 ospf_find_area(struct proto_ospf *po, u32 aid)
 {
diff --git a/proto/ospf/neighbor.h b/proto/ospf/neighbor.h
index 67f7c57..5612eca 100644
--- a/proto/ospf/neighbor.h
+++ b/proto/ospf/neighbor.h
@@ -14,7 +14,6 @@ struct ospf_neighbor *ospf_neighbor_new(struct ospf_iface *ifa);
 void ospf_neigh_sm(struct ospf_neighbor *n, int event);
 void bdr_election(struct ospf_iface *ifa);
 struct ospf_neighbor *find_neigh(struct ospf_iface *ifa, u32 rid);
-struct ospf_neighbor *find_neigh_noifa(struct proto_ospf *po, u32 rid);
 struct ospf_area *ospf_find_area(struct proto_ospf *po, u32 aid);
 void ospf_neigh_remove(struct ospf_neighbor *n);
 void ospf_sh_neigh_info(struct ospf_neighbor *n);
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index c3798e7..6a30c68 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -477,6 +477,9 @@ link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry
 
   // FIXME lb should be properly set for vlinks */
   en->lb = IPA_NONE;
+#ifdef OSPFv3
+  en->lb_id = 0;
+#endif
   switch (en->lsa.type)
   {
     case LSA_T_RT:
@@ -500,6 +503,8 @@ link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry
 	  {
 #ifdef OSPFv2
 	    en->lb = ipa_from_u32(rtl->data);
+#else /* OSPFv3 */
+	    en->lb_id = rtl->lif;
 #endif
 	    return 1;
 	  }
@@ -1099,14 +1104,15 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
 	      struct top_hash_entry *par)
 {
   // struct proto *p = &oa->po->proto;
-  struct ospf_neighbor *neigh;
+  struct ospf_neighbor *neigh, *m;
   struct proto_ospf *po = oa->po;
   struct ospf_iface *ifa;
 
   /* 16.1.1. The next hop calculation */
   DBG("     Next hop called.\n");
-  if (ipa_equal(par->nh, IPA_NONE))
+  if (ipa_zero(par->nh))
   {
+    u32 rid = en->lsa.rt;
     DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
 	en->lsa.id, en->lsa.rt, en->lsa.type);
 
@@ -1130,32 +1136,73 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
       return 0;
     }
 
-    /* 
-     * Remaining cases - local neighbours.
-     * There are two problems with this code:
-     * 1) we use IP address from HELLO packet
-     *    and not the one from LSA (router or link).
-     *    This may break NBMA networks
-     * 2) we use find_neigh_noifa() and does not
-     *    take into account associated iface.
-     *    This breaks neighbors connected by more links.
-     */
-
-    if ((en->lsa.type == LSA_T_RT) && 
-	((par == oa->rt) || (par->lsa.type == LSA_T_NET)))
+    /* The second case - ptp or ptmp neighbor */
+    if ((en->lsa.type == LSA_T_RT) && (par == oa->rt))
     {
-      if ((neigh = find_neigh_noifa(po, en->lsa.rt)) != NULL)
+      /*
+       * We don't know which iface was used to reach this neighbor
+       * (there might be more parallel ifaces) so we will find
+       * the best PTP iface with given fully adjacent neighbor.
+       */
+      neigh = NULL;
+      WALK_LIST(ifa, po->iface_list)
+	if (ifa->type == OSPF_IT_PTP)
 	{
-	  en->nh = neigh->ip;
-	  en->nhi = neigh->ifa;
-	  return 1;
+	  m = find_neigh(ifa, rid);
+	  if (m && (m->state == NEIGHBOR_FULL))
+	  {
+	    if (!neigh || (m->ifa->cost < neigh->ifa->cost))
+	      neigh = m;
+	  }
 	}
-      return 0;
+
+      if (!neigh)
+	return 0;
+
+      en->nh = neigh->ip;
+      en->nhi = neigh->ifa;
+      return 1;
     }
 
+    /* The third case - bcast or nbma neighbor */
+    if ((en->lsa.type == LSA_T_RT) && (par->lsa.type == LSA_T_NET))
+    {
+      /* par->nhi should be defined from parent's calc_next_hop() */
+      if (!par->nhi)
+	goto bad;
+
+#ifdef OSPFv2
+      /*
+       * In this case, next-hop is the same as link-back, which is
+       * already computed in link_back().
+       */
+      if (ipa_zero(en->lb))
+	goto bad;
+
+      en->nh = en->lb;
+      en->nhi = par->nhi;
+      return 1;
+
+#else /* OSPFv3 */
+      /*
+       * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
+       * is computed in link_back().
+       */
+      struct top_hash_entry *llsa;
+      llsa = ospf_hash_find(po->gr, par->nhi->iface->index, en->lb_id, rid, LSA_T_LINK);
+
+      if (!llsa)
+	return 0;
+
+      en->nh = llsa->lladdr;
+      en->nhi = par->nhi;
+      return 1;
+#endif
+    }
+
+  bad:
     /* Probably bug or some race condition, we log it */
     log(L_ERR "Unexpected case in next hop calculation");
-
     return 0;
   }
 
diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h
index f6ba019..16d4c78 100644
--- a/proto/ospf/topology.h
+++ b/proto/ospf/topology.h
@@ -23,6 +23,9 @@ struct top_hash_entry
   ip_addr nh;			/* Next hop */
   ip_addr lb;			/* Link back */
   struct ospf_iface *nhi;	/* Next hop interface */
+#ifdef OSPFv3
+  u32 lb_id;			/* Interface ID of link back iface (for bcast or NBMA networks) */
+#endif
   u32 dist;			/* Distance from the root */
   u16 ini_age;
   u8 color;
-- 
cgit v1.2.3


From dcc6049444f5e12e0d0fcc4cfbb244c08b4c20b0 Mon Sep 17 00:00:00 2001
From: Ondrej Zajicek <santiago@crfreenet.org>
Date: Wed, 14 Apr 2010 14:46:21 +0200
Subject: Fixes IPv6 build on older systems.

---
 sysdep/unix/io.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/sysdep/unix/io.c b/sysdep/unix/io.c
index d1fad1f..c9e6fe1 100644
--- a/sysdep/unix/io.c
+++ b/sysdep/unix/io.c
@@ -668,6 +668,16 @@ get_sockaddr(struct sockaddr_in *sa, ip_addr *a, unsigned *port, int check)
 #define CMSG_RX_SPACE CMSG_SPACE(sizeof(struct in6_pktinfo))
 #define CMSG_TX_SPACE CMSG_SPACE(sizeof(struct in6_pktinfo))
 
+/*
+ * RFC 2292 uses IPV6_PKTINFO for both the socket option and the cmsg
+ * type, RFC 3542 changed the socket option to IPV6_RECVPKTINFO. If we
+ * don't have IPV6_RECVPKTINFO we suppose the OS implements the older
+ * RFC and we use IPV6_PKTINFO.
+ */
+#ifndef IPV6_RECVPKTINFO
+#define IPV6_RECVPKTINFO IPV6_PKTINFO
+#endif
+
 static char *
 sysio_register_cmsgs(sock *s)
 {
-- 
cgit v1.2.3


From 607d991424006c083be63878b6a606e76679e1ce Mon Sep 17 00:00:00 2001
From: Ondrej Zajicek <santiago@crfreenet.org>
Date: Wed, 14 Apr 2010 15:35:08 +0200
Subject: Fixes build on newer Linux systems.

---
 sysdep/unix/io.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/sysdep/unix/io.c b/sysdep/unix/io.c
index c9e6fe1..dc7146f 100644
--- a/sysdep/unix/io.c
+++ b/sysdep/unix/io.c
@@ -7,6 +7,10 @@
  *	Can be freely distributed and used under the terms of the GNU GPL.
  */
 
+/* Unfortunately, some glibc versions hide parts of RFC 3542 API
+   if _GNU_SOURCE is not defined. */
+#define _GNU_SOURCE 1
+
 #include <stdio.h>
 #include <stdlib.h>
 #include <time.h>
-- 
cgit v1.2.3


From 3b89a2327ba385abf2a8321a5a900faba3765612 Mon Sep 17 00:00:00 2001
From: Ondrej Zajicek <santiago@crfreenet.org>
Date: Wed, 21 Apr 2010 21:50:38 +0200
Subject: Fixes several problems in OSPF vlink implementation.

---
 proto/ospf/config.Y   |   1 -
 proto/ospf/iface.c    |  22 +-
 proto/ospf/rt.c       | 863 ++++++++++++++++++++++++++++----------------------
 proto/ospf/rt.h       |  30 +-
 proto/ospf/topology.c |  26 +-
 proto/ospf/topology.h |   2 +-
 6 files changed, 522 insertions(+), 422 deletions(-)

diff --git a/proto/ospf/config.Y b/proto/ospf/config.Y
index da7c97e..2196af7 100644
--- a/proto/ospf/config.Y
+++ b/proto/ospf/config.Y
@@ -164,7 +164,6 @@ ospf_vlink_start: VIRTUAL LINK idval
   add_tail(&this_area->vlink_list, NODE this_ipatt);
   init_list(&this_ipatt->ipn_list);
   OSPF_PATT->vid = $3;
-  OSPF_PATT->cost = COST_D;
   OSPF_PATT->helloint = HELLOINT_D;
   OSPF_PATT->rxmtint = RXMTINT_D;
   OSPF_PATT->inftransdelay = INFTRANSDELAY_D;
diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c
index 6931619..f401326 100644
--- a/proto/ospf/iface.c
+++ b/proto/ospf/iface.c
@@ -260,6 +260,7 @@ ospf_iface_down(struct ospf_iface *ifa)
     ifa->iface = NULL;
     ifa->addr = NULL;
     ifa->sk = NULL;
+    ifa->cost = 0;
     ifa->vip = IPA_NONE;
     return;
   }
@@ -445,27 +446,6 @@ ospf_iface_new(struct proto_ospf *po, struct iface *iface, struct ifa *addr,
 
 #ifdef OSPFv3
   ifa->instance_id = ip->instance_id;
-
-  /*
-  addr = NULL;
-  if (ifa->type != OSPF_IT_VLINK)
-    {
-      struct ifa *a;
-      WALK_LIST(a, iface->addrs)
-	if (a->scope == SCOPE_LINK)
-	  {
-	    addr = a;
-	    break;
-	  }
-
-      if (!addr)
-      {
-	log(L_ERR "%s: Missing link-local address on interface %s, declaring as stub", p->name,  iface->name);
-	ifa->ioprob = OSPF_I_LL;
-	ifa->stub = 1;
-      }
-    }
-  */
 #endif
 
   if (ip->type == OSPF_IT_UNDEF)
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index 6a30c68..d685961 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -14,7 +14,6 @@ static void add_cand(list * l, struct top_hash_entry *en,
 static int calc_next_hop(struct ospf_area *oa,
 			 struct top_hash_entry *en,
 			 struct top_hash_entry *par);
-static void ospf_ext_spf(struct proto_ospf *po);
 static void rt_sync(struct proto_ospf *po);
 
 /* In ospf_area->rtr we store paths to routers, but we use RID (and not IP address)
@@ -31,14 +30,13 @@ fill_ri(orta * orta)
 {
   orta->type = RTS_DUMMY;
   orta->options = 0;
-  orta->oa = NULL;
   orta->metric1 = LSINFINITY;
   orta->metric2 = LSINFINITY;
-  orta->nh = IPA_NONE;
-  orta->ifa = NULL;
-  orta->ar = NULL;
   orta->tag = 0;
   orta->rid = 0;
+  orta->oa = NULL;
+  orta->ifa = NULL;
+  orta->nh = IPA_NONE;
 }
 
 void
@@ -47,105 +45,161 @@ ospf_rt_initort(struct fib_node *fn)
   ort *ri = (ort *) fn;
   fill_ri(&ri->n);
   memcpy(&ri->o, &ri->n, sizeof(orta));
-  ri->efn = NULL;
 }
 
-/* If new is better return 1 */
+/* Whether the ASBR or the forward address destination is preferred in AS external route selection
+   according to 16.4.1. */
+static inline int
+epath_preferred(orta *ep)
+{
+  return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0);
+}
 
-/* 
- * This is hard to understand:
- * If rfc1583 is set to 1, it work likes normal route_better()
- * But if it is set to 0, it prunes number of AS boundary
- * routes before it starts the router decision
- */
+/* If new is better return 1 */
 static int
-ri_better(struct proto_ospf *po, orta * new, ort *nefn, orta * old, ort *oefn, int rfc1583)
+ri_better(struct proto_ospf *po, orta *new, orta *old)
 {
-  int newtype = new->type;
-  int oldtype = old->type;
-
   if (old->type == RTS_DUMMY)
     return 1;
 
   if (old->metric1 == LSINFINITY)
     return 1;
 
-  if (!rfc1583)
+  if (new->type < old->type)
+    return 1;
+
+  if (new->type > old->type)
+    return 0;
+
+  if (new->metric1 < old->metric1)
+    return 1;
+
+  if (new->metric1 > old->metric1)
+    return 0;
+
+  return 0;
+}
+
+
+/* 16.4. (3), return 1 if new is better */
+static int
+ri_better_asbr(struct proto_ospf *po, orta *new, orta *old)
+{
+  /* We know that the old ASBB is valid */
+
+  if (!po->rfc1583)
   {
-    if ((new->type < RTS_OSPF_EXT1) && (new->oa->areaid == 0)) newtype = RTS_OSPF_IA;
-    if ((old->type < RTS_OSPF_EXT1) && (old->oa->areaid == 0)) oldtype = RTS_OSPF_IA;
+    int new_pref = epath_preferred(new);
+    int old_pref = epath_preferred(old);
+
+    if (new_pref > old_pref)
+      return 1;
+
+    if (new_pref < old_pref)
+      return 0;
   }
 
-  if (newtype < oldtype)
+  if (new->metric1 < old->metric1)
     return 1;
 
-  if (newtype > oldtype)
+  if (new->metric1 > old->metric1)
     return 0;
 
-  /* Same type */
+  /* Larger area ID is preferred */
+  if (new->oa->areaid > old->oa->areaid)
+    return 1;
+
+  return 0;
+}
+
+/* 16.4. (6), return 1 if new is better */
+static int
+ri_better_ext(struct proto_ospf *po, orta *new, orta *old)
+{
+  if (old->type == RTS_DUMMY)
+    return 1;
+
+  if (old->metric1 == LSINFINITY)
+    return 1;
+
+  /* 16.4. (6a) */
+  if (new->type < old->type)
+    return 1;
+
+  if (new->type > old->type)
+    return 0;
+
+  /* 16.4. (6b), same type */
   if (new->type == RTS_OSPF_EXT2)
   {
-    if (new->metric2 < old->metric2) return 1;
-    if (new->metric2 > old->metric2) return 0;
+    if (new->metric2 < old->metric2)
+      return 1;
+
+    if (new->metric2 > old->metric2)
+      return 0;
   }
 
-  if (((new->type == RTS_OSPF_EXT2) || (new->type == RTS_OSPF_EXT1)) && (!po->rfc1583))
+  /* 16.4. (6c) */
+  if (!po->rfc1583)
   {
-    newtype = nefn->n.type;
-    oldtype = oefn->n.type;
+    u32 new_pref = new->options & ORTA_PREF;
+    u32 old_pref = old->options & ORTA_PREF;
 
-    if (nefn->n.oa->areaid == 0) newtype = RTS_OSPF_IA;
-    if (oefn->n.oa->areaid == 0) oldtype = RTS_OSPF_IA;
+    if (new_pref > old_pref)
+      return 1;
 
-    if (newtype < oldtype) return 1;
-    if (newtype > oldtype) return 0;
+    if (new_pref < old_pref)
+      return 0;
   }
 
+  /* 16.4. (6d) */
   if (new->metric1 < old->metric1)
     return 1;
 
   if (new->metric1 > old->metric1)
     return 0;
 
-  if (new->oa->areaid > old->oa->areaid) return 1;	/* Larger AREAID is preffered */
+  return 0;
+}
 
-  return 0;			/* Old is shorter or same */
+static inline void
+ri_install_net(struct proto_ospf *po, ip_addr prefix, int pxlen, orta *new)
+{
+  ort *old = (ort *) fib_get(&po->rtf, &prefix, pxlen);
+  if (ri_better(po, new, &old->n))
+    memcpy(&old->n, new, sizeof(orta));
 }
 
-static void
-ri_install(struct proto_ospf *po, ip_addr prefix, int pxlen, int dest,
-	   orta * new, ort * ipath)
+static inline void
+ri_install_rt(struct ospf_area *oa, u32 rid, orta *new)
 {
-  struct ospf_area *oa = new->oa;
-  ort *old;
+  ip_addr addr = ipa_from_rid(rid);
+  ort *old = (ort *) fib_get(&oa->rtr, &addr, MAX_PREFIX_LENGTH);
+  if (ri_better(oa->po, new, &old->n))
+    memcpy(&old->n, new, sizeof(orta));
+}
 
-  if (dest == ORT_NET)
-  {
-    struct area_net *anet;
-    old = (ort *) fib_get(&po->rtf, &prefix, pxlen);
-    if (ri_better(po, new, ipath, &old->n, old->efn, 1))
-    {
-      memcpy(&old->n, new, sizeof(orta));
-      old->efn = ipath;
-      if ((new->type == RTS_OSPF) && (anet = (struct area_net *)fib_route(&oa->net_fib, prefix, pxlen)))
-      {
-        anet->active = 1;
-        if (new->metric1 > anet->metric) anet->metric = new->metric1;
-      }
-    }
-  }
-  else
-  {
-    old = (ort *) fib_get(&oa->rtr, &prefix, pxlen);
+static inline void
+ri_install_ext(struct proto_ospf *po, ip_addr prefix, int pxlen, orta *new)
+{
+  ort *old = (ort *) fib_get(&po->rtf, &prefix, pxlen);
+  if (ri_better_ext(po, new, &old->n))
+    memcpy(&old->n, new, sizeof(orta));
+}
 
-    if (ri_better(po, new, ipath, &old->n, old->efn, 1))
-    {
-      memcpy(&old->n, new, sizeof(orta));
-      old->efn = ipath;
-    }
-  }
+static inline void
+update_anet(struct ospf_area *oa, ip_addr prefix, int pxlen, u32 metric)
+{
+  struct area_net *anet = (struct area_net *) fib_route(&oa->net_fib, prefix, pxlen);
+  if (!anet)
+    return;
+  
+  anet->active = 1;
+  if (metric > anet->metric)
+    anet->metric = metric;
 }
 
+
 #ifdef OSPFv2
 
 static struct ospf_iface *
@@ -188,17 +242,17 @@ find_stub_src(struct ospf_area *oa, ip_addr px, int pxlen)
 static void
 add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en)
 {
-  orta nf;
-  nf.type = RTS_OSPF;
-  nf.options = 0;
-  nf.metric1 = metric;
-  nf.metric2 = LSINFINITY;
-  nf.tag = 0;
-  nf.oa = oa;
-  nf.ar = en;
-  nf.nh = en->nh;
-  nf.ifa = en->nhi;
-  nf.rid = en->lsa.rt;
+  orta nf = {
+    .type = RTS_OSPF,
+    .options = 0,
+    .metric1 = metric,
+    .metric2 = LSINFINITY,
+    .tag = 0,
+    .rid = en->lsa.rt,
+    .oa = oa,
+    .ifa = en->nhi,
+    .nh = en->nh
+  };
 
   if (en == oa->rt)
   {
@@ -210,12 +264,14 @@ add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_
      */
 
     nf.ifa = find_stub_src(oa, px, pxlen);
+    nf.nh = IPA_NONE;
 
     if (!nf.ifa)
       return;
   }
 
-  ri_install(oa->po, px, pxlen, ORT_NET, &nf, NULL);
+  ri_install_net(oa->po, px, pxlen, &nf);
+  update_anet(oa, px, pxlen, metric);
 }
 
 #ifdef OSPFv3
@@ -255,6 +311,10 @@ process_prefixes(struct ospf_area *oa)
     if (!src)
       continue;
 
+    /* Reachable in SPF */
+    if (src->color != INSPF)
+      continue;
+
     if (src->lsa.age == LSA_MAXAGE)
       continue;
 
@@ -269,6 +329,10 @@ process_prefixes(struct ospf_area *oa)
 	if (pxopts & OPT_PX_NU)
 	  continue;
 
+	/* Store the first global address to use it later as a vlink endpoint */
+	if ((pxopts & OPT_PX_LA) && ipa_zero(src->lb))
+	  src->lb = pxa;
+
 	add_network(oa, pxa, pxlen, src->dist + metric, src);
       }
   }
@@ -329,7 +393,7 @@ ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct top_hash_entry *act, struct to
     }
 }
 
-/* 16.1 calculating shortest paths for an area */
+/* RFC 2328 16.1. calculating shortest paths for an area */
 static void
 ospf_rt_spfa(struct ospf_area *oa)
 {
@@ -337,10 +401,8 @@ ospf_rt_spfa(struct ospf_area *oa)
   struct proto_ospf *po = oa->po;
   struct ospf_lsa_rt *rt;
   struct ospf_lsa_net *ln;
-  struct ospf_iface *iface;
   struct top_hash_entry *act, *tmp;
   u32 i, *rts;
-  orta nf;
   node *n;
 
   if (oa->rt == NULL)
@@ -380,20 +442,27 @@ ospf_rt_spfa(struct ospf_area *oa)
       if (rt->options & OPT_RT_V)
 	oa->trcap = 1;
 
-      /* In OSPFv2, just ASBRs and ABRs are needed to add to oa->rtr table */
-      // ((rt->options & OPT_RT_V) || (rt->options & OPT_RT_E))
-
-      nf.type = RTS_OSPF;
-      nf.options = rt->options;
-      nf.metric1 = act->dist;
-      nf.metric2 = LSINFINITY;
-      nf.tag = 0;
-      nf.oa = oa;
-      nf.ar = act;
-      nf.nh = act->nh;
-      nf.ifa = act->nhi;
-      nf.rid = act->lsa.rt;
-      ri_install(po, ipa_from_rid(act->lsa.rt), MAX_PREFIX_LENGTH, ORT_ROUTER, &nf, NULL);
+      /*
+       * In OSPFv3, all routers are added to per-area routing
+       * tables. But we use it just for ASBRs and ABRs. For the
+       * purpose of the last step in SPF - prefix-LSA processing in
+       * process_prefixes(), we use information stored in LSA db.
+       */
+      if ((rt->options & OPT_RT_E) || (rt->options & OPT_RT_B))
+      {
+	orta nf = {
+	  .type = RTS_OSPF,
+	  .options = rt->options,
+	  .metric1 = act->dist,
+	  .metric2 = LSINFINITY,
+	  .tag = 0,
+	  .rid = act->lsa.rt,
+	  .oa = oa,
+	  .ifa = act->nhi,
+	  .nh = act->nh
+	};
+	ri_install_rt(oa, act->lsa.rt, &nf);
+      }
 
 #ifdef OSPFv2
       ospf_rt_spfa_rtlinks(oa, act, act);
@@ -430,37 +499,6 @@ ospf_rt_spfa(struct ospf_area *oa)
 #ifdef OSPFv3
   process_prefixes(oa);
 #endif
-
-  /* Find new/lost VLINK peers */
-  WALK_LIST(iface, po->iface_list)
-  {
-    if ((iface->type == OSPF_IT_VLINK) && (iface->voa == oa))
-    {
-      if ((tmp = ospf_hash_find_rt(po->gr, oa->areaid, iface->vid)) &&
-	  (!ipa_equal(tmp->lb, IPA_NONE)))
-      {
-        if ((iface->state != OSPF_IS_PTP) || (iface->vifa != tmp->nhi) || (!ipa_equal(iface->vip, tmp->lb)))
-        {
-          OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id);
-          ospf_iface_sm(iface, ISM_DOWN);
-	  iface->vifa = tmp->nhi;
-          iface->iface = tmp->nhi->iface;
-	  iface->addr = tmp->nhi->addr;
-	  iface->sk = tmp->nhi->sk;
-          iface->vip = tmp->lb;
-          ospf_iface_sm(iface, ISM_UP);
-        }
-      }
-      else
-      {
-        if (iface->state > OSPF_IS_DOWN)
-        {
-          OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", iface->vid);
-	  ospf_iface_sm(iface, ISM_DOWN);
-        }
-      }
-    }
-  }
 }
 
 static int
@@ -475,7 +513,9 @@ link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry
 
   if (!en || !par) return 0;
 
-  // FIXME lb should be properly set for vlinks */
+  /* In OSPFv2, en->lb is set here. In OSPFv3, en->lb is just cleared here,
+     it is set in process_prefixes() to any global addres in the area */
+
   en->lb = IPA_NONE;
 #ifdef OSPFv3
   en->lb_id = 0;
@@ -539,21 +579,22 @@ link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry
   return 0;
 }
 
-/* 16.3 examining summary-LSAs in transit areas */
+  
+/* RFC 2328 16.2. calculating inter-area routes */
 static void
-ospf_rt_sum_tr(struct ospf_area *oa)
+ospf_rt_sum(struct ospf_area *oa)
 {
-  // struct proto *p = &oa->po->proto;
   struct proto_ospf *po = oa->po;
-  struct ospf_area *bb = po->backbone;
-  ip_addr ip, abrip;
+  struct proto *p = &po->proto;
   struct top_hash_entry *en;
-  u32 dst_rid, metric, options;
+  ip_addr ip = IPA_NONE;
+  u32 dst_rid = 0;
+  u32 metric, options;
+  struct area_net *anet;
+  ort *abr;
   int pxlen = -1, type = -1;
-  ort *re = NULL, *abr;
-  orta nf;
 
-  if (!bb) return;
+  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid);
 
   WALK_SLIST(en, po->lsal)
   {
@@ -563,19 +604,20 @@ ospf_rt_sum_tr(struct ospf_area *oa)
     if (en->domain != oa->areaid)
       continue;
 
-    /* 16.3 (1a) */
+    /* 16.2. (1a) */
     if (en->lsa.age == LSA_MAXAGE)
       continue;
 
-    // if (en->dist == LSINFINITY)
-    //   continue;
-
-    /* 16.3 (2) */
+    /* 16.2. (2) */
     if (en->lsa.rt == po->router_id)
       continue;
 
+
     if (en->lsa.type == LSA_T_SUM_NET)
     {
+      struct ospf_area *oaa;
+      int skip = 0;
+
 #ifdef OSPFv2
       struct ospf_lsa_sum *ls = en->lsa_body;
       pxlen = ipa_mklen(ls->netmask);
@@ -593,9 +635,20 @@ ospf_rt_sum_tr(struct ospf_area *oa)
       metric = ls->metric & METRIC_MASK;
       options = 0;
       type = ORT_NET;
-      re = fib_find(&po->rtf, &ip, pxlen);
+
+      /* 16.2. (3) */
+      WALK_LIST(oaa, po->area_list)
+      {
+        if ((anet = fib_find(&oaa->net_fib, &ip, pxlen)) && anet->active)
+	{
+	  skip = 1;
+	  break;
+	}
+      }
+      if (skip)
+	continue;
     }
-    else // en->lsa.type == LSA_T_SUM_RT
+    else /* LSA_T_SUM_RT */
     {
 #ifdef OSPFv2
       struct ospf_lsa_sum *ls = en->lsa_body;
@@ -607,57 +660,62 @@ ospf_rt_sum_tr(struct ospf_area *oa)
       options = ls->options & OPTIONS_MASK;
 #endif
 
-      ip = ipa_from_rid(dst_rid);
-      pxlen = MAX_PREFIX_LENGTH;
       metric = ls->metric & METRIC_MASK;
       options |= ORTA_ASBR;
       type = ORT_ROUTER;
-      re = fib_find(&bb->rtr, &ip, pxlen);
     }
 
-    /* 16.3 (1b) */ 
-    if (metric == LSINFINITY) 
-      continue; 
+    /* 16.2. (1b) */
+    if (metric == LSINFINITY)
+      continue;
 
-    /* 16.3 (3) */
-    if (!re || !re->n.type) continue;
-    if (re->n.oa->areaid != 0) continue;
-    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA)) continue;
+    /* 16.2. (4) */
+    ip_addr abrip = ipa_from_rid(en->lsa.rt);
+    abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
+    if (!abr || !abr->n.type)
+      continue;
 
-    /* 16.3. (4) */
-    abrip = ipa_from_rid(en->lsa.rt);
-    abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
-    if (!abr || !abr->n.type) continue;
-
-    nf.type = re->n.type;
-    nf.options = options;
-    nf.metric1 = abr->n.metric1 + metric;
-    nf.metric2 = LSINFINITY;
-    nf.tag = 0;
-    nf.oa = oa;
-    nf.ar = abr->n.ar;
-    nf.nh = abr->n.nh;
-    nf.ifa = abr->n.ifa;
-    nf.rid = en->lsa.rt; /* ABR ID */
-    ri_install(po, ip, pxlen, type, &nf, NULL);
+    if (abr->n.metric1 == LSINFINITY)
+      continue;
+
+    if (!(abr->n.options & ORTA_ABR))
+      continue;
+
+    /* 16.2. (5) */
+    orta nf = {
+      .type = RTS_OSPF_IA,
+      .options = options,
+      .metric1 = abr->n.metric1 + metric,
+      .metric2 = LSINFINITY,
+      .tag = 0,
+      .rid = en->lsa.rt, /* ABR ID */
+      .oa = oa,
+      .ifa = abr->n.ifa,
+      .nh = abr->n.nh
+    };
+
+    if (type == ORT_NET)
+      ri_install_net(po, ip, pxlen, &nf);
+    else
+      ri_install_rt(oa, dst_rid, &nf);
   }
 }
-  
-/* 16.2 calculating inter-area routes */
+
+/* RFC 2328 16.3. examining summary-LSAs in transit areas */
 static void
-ospf_rt_sum(struct ospf_area *oa)
+ospf_rt_sum_tr(struct ospf_area *oa)
 {
+  // struct proto *p = &oa->po->proto;
   struct proto_ospf *po = oa->po;
-  struct proto *p = &po->proto;
+  struct ospf_area *bb = po->backbone;
+  ip_addr ip, abrip;
   struct top_hash_entry *en;
-  ip_addr ip, abrip;	/* abrIP is actually ID */
   u32 dst_rid, metric, options;
-  struct area_net *anet;
-  orta nf;
-  ort *abr;
   int pxlen = -1, type = -1;
+  ort *re = NULL, *abr;
 
-  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid);
+
+  if (!bb) return;
 
   WALK_SLIST(en, po->lsal)
   {
@@ -667,20 +725,16 @@ ospf_rt_sum(struct ospf_area *oa)
     if (en->domain != oa->areaid)
       continue;
 
-    /* Page 169 (1) */
+    /* 16.3 (1a) */
     if (en->lsa.age == LSA_MAXAGE)
       continue;
 
-    /* Page 169 (2) */
+    /* 16.3 (2) */
     if (en->lsa.rt == po->router_id)
       continue;
 
-
     if (en->lsa.type == LSA_T_SUM_NET)
     {
-      struct ospf_area *oaa;
-      int skip = 0;
-
 #ifdef OSPFv2
       struct ospf_lsa_sum *ls = en->lsa_body;
       pxlen = ipa_mklen(ls->netmask);
@@ -698,19 +752,9 @@ ospf_rt_sum(struct ospf_area *oa)
       metric = ls->metric & METRIC_MASK;
       options = 0;
       type = ORT_NET;
-
-      /* Page 169 (3) */
-      WALK_LIST(oaa, po->area_list)
-      {
-        if ((anet = fib_find(&oaa->net_fib, &ip, pxlen)) && anet->active)
-	{
-	  skip = 1;
-	  break;
-	}
-      }
-      if (skip) continue;
+      re = fib_find(&po->rtf, &ip, pxlen);
     }
-    else
+    else // en->lsa.type == LSA_T_SUM_RT
     {
 #ifdef OSPFv2
       struct ospf_lsa_sum *ls = en->lsa_body;
@@ -727,114 +771,54 @@ ospf_rt_sum(struct ospf_area *oa)
       metric = ls->metric & METRIC_MASK;
       options |= ORTA_ASBR;
       type = ORT_ROUTER;
+      re = fib_find(&bb->rtr, &ip, pxlen);
     }
 
-    /* Page 169 (1) */
-    if (metric == LSINFINITY)
-      continue;
-
-    /* Page 169 (4) */
-    abrip = ipa_from_rid(en->lsa.rt);
-
-    abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
-    if (!abr || !abr->n.type) continue;
-    if (abr->n.metric1 == LSINFINITY) continue;
-    if (!(abr->n.options & ORTA_ABR)) continue;
-
-    nf.type = RTS_OSPF_IA;
-    nf.options = options;
-    nf.metric1 = abr->n.metric1 + metric;
-    nf.metric2 = LSINFINITY;
-    nf.tag = 0;
-    nf.oa = oa;
-    nf.ar = abr->n.ar;
-    nf.nh = abr->n.nh;
-    nf.ifa = abr->n.ifa;
-    nf.rid = en->lsa.rt; /* ABR ID */
-    ri_install(po, ip, pxlen, type, &nf, NULL);
-  }
-}
-
-/**
- * ospf_rt_spf - calculate internal routes
- * @po: OSPF protocol
- *
- * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
- * It's based on Dijkstra's shortest path tree algorithms.
- * This function is invoked from ospf_disp().
- */
-void
-ospf_rt_spf(struct proto_ospf *po)
-{
-  struct proto *p = &po->proto;
-  struct ospf_area *oa;
-  ort *ri;
-  struct area_net *anet;
-
-  if (po->areano == 0) return;
+    /* 16.3 (1b) */ 
+    if (metric == LSINFINITY) 
+      continue; 
 
-  po->cleanup = 1;
+    /* 16.3 (3) */
+    if (!re || !re->n.type)
+      continue;
 
-  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
+    if (re->n.oa->areaid != 0)
+      continue;
 
-  /* 16. (1) - Invalidate old routing table */
-  FIB_WALK(&po->rtf, nftmp)
-  {
-    ri = (ort *) nftmp;
-    memcpy(&ri->o, &ri->n, sizeof(orta));	/* Backup old data */
-    fill_ri(&ri->n);
-  }
-  FIB_WALK_END;
+    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA))
+      continue;
 
+    /* 16.3. (4) */
+    abrip = ipa_from_rid(en->lsa.rt);
+    abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
+    if (!abr || !abr->n.type)
+      continue;
 
-  WALK_LIST(oa, po->area_list)
-  {
-    FIB_WALK(&oa->rtr, nftmp)
-    {
-      ri = (ort *) nftmp;
-      memcpy(&ri->o, &ri->n, sizeof(orta));	/* Backup old data */
-      fill_ri(&ri->n);
-    }
-    FIB_WALK_END;
+    metric = abr->n.metric1 + metric; /* IAC */
 
-    FIB_WALK(&oa->net_fib, nftmp)
+    /* 16.3. (5) */
+    if (metric <= re->n.metric1)
     {
-      anet = (struct area_net *) nftmp;
-      anet->active = 0;
-      anet->metric = 1;
+      /* We want to replace the next-hop even if the metric is equal
+	 to replace a virtual next-hop through vlink with a real one */
+      re->n.metric1 = metric;
+      re->n.nh = abr->n.nh;
+      re->n.ifa = abr->n.ifa;
     }
-    FIB_WALK_END;
-
-    /* 16. (2) */
-    ospf_rt_spfa(oa);
-  }
-
-  /* 16. (3) */
-  if ((po->areano == 1) || (!po->backbone))
-  {
-    ospf_rt_sum(HEAD(po->area_list));
-  }
-  else
-  {
-    ospf_rt_sum(po->backbone);
   }
+}
 
-  /* 16. (4) */
-  WALK_LIST(oa, po->area_list)
+/* RFC 2328 G.3 - incomplete resolution of virtual next hops */
+static void
+ospf_cleanup_vlinks(struct proto_ospf *po)
+{
+  FIB_WALK(&po->rtf, nftmp)
   {
-    if (oa->trcap && (oa->areaid != 0))
-    {
-      ospf_rt_sum_tr(oa);
-      break;
-    }
+    ort *nf = (ort *) nftmp;
+    if (nf->n.type && (nf->n.ifa->type == OSPF_IT_VLINK))
+      fill_ri(&nf->n);
   }
-
-  /* 16. (5) */
-  ospf_ext_spf(po);
-
-  rt_sync(po);
-
-  po->calcrt = 0;
+  FIB_WALK_END;
 }
 
 /**
@@ -848,7 +832,7 @@ ospf_rt_spf(struct proto_ospf *po)
 static void
 ospf_ext_spf(struct proto_ospf *po)
 {
-  ort *nf1, *nf2, *nfh;
+  ort *nf1, *nf2;
   orta nfa;
   struct top_hash_entry *en;
   struct proto *p = &po->proto;
@@ -857,7 +841,6 @@ ospf_ext_spf(struct proto_ospf *po)
   ip_addr ip, nh, rtid, rt_fwaddr;
   struct ospf_iface *nhi = NULL;
   u32 br_metric, rt_metric, rt_tag;
-  neighbor *nn;
   struct ospf_area *atmp;
 
   OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
@@ -867,6 +850,7 @@ ospf_ext_spf(struct proto_ospf *po)
     /* 16.4. (1) */
     if (en->lsa.type != LSA_T_EXT)
       continue;
+
     if (en->lsa.age == LSA_MAXAGE)
       continue;
 
@@ -926,52 +910,47 @@ ospf_ext_spf(struct proto_ospf *po)
     nf1 = NULL;
     WALK_LIST(atmp, po->area_list)
     {
-      nfh = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH);
-      if (!nfh || !nfh->n.type) continue;    
-      if (nf1 == NULL) nf1 = nfh;
-      else if (ri_better(po, &nfh->n, NULL, &nf1->n, NULL, po->rfc1583)) nf1 = nfh;
+      ort *nfh = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH);
+      if (!nfh || !nfh->n.type)
+	continue;
+
+      if (nfh->n.metric1 == LSINFINITY)
+	continue;
+
+      if (!nf1 || ri_better_asbr(po, &nfh->n, &nf1->n))
+	nf1 = nfh;
     }
 
     if (!nf1)
       continue;			/* No AS boundary router found */
 
-    if (nf1->n.metric1 == LSINFINITY)
-      continue;			/* distance is INF */
-
     if (!(nf1->n.options & ORTA_ASBR))
       continue;			/* It is not ASBR */
 
     if (!rt_fwaddr_valid)
     {
+      nf2 = nf1;
       nh = nf1->n.nh;
       nhi = nf1->n.ifa;
-      nfh = nf1;
       br_metric = nf1->n.metric1;
     }
     else
     {
+      /* FIXME: what about more specific dummy route? */
       nf2 = fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH);
-
-      if (!nf2)
-      {
-	DBG("Cannot find network route (GW=%I)\n", rt_fwaddr);
+      if (!nf2) /* nf2->n.type is checked later */
 	continue;
-      }
 
-      if ((nn = neigh_find(p, &rt_fwaddr, 0)) != NULL)
-      {
-	nh = rt_fwaddr;
-	nhi = ospf_iface_find(po, nn->iface);
-      }
-      else
-      {
-	nh = nf2->n.nh;
-	nhi = nf2->n.ifa;
-      }
+      if (nf2->n.metric1 == LSINFINITY)
+        continue;
+
+      if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA))
+	continue;
 
+      /* If nh is zero, it is a device route */
+      nh = ipa_nonzero(nf2->n.nh) ? nf2->n.nh : rt_fwaddr;
+      nhi = nf2->n.ifa;
       br_metric = nf2->n.metric1;
-      if (br_metric == LSINFINITY)
-        continue;			/* distance is INF */
     }
 
     if (ebit)
@@ -987,16 +966,144 @@ ospf_ext_spf(struct proto_ospf *po)
       nfa.metric2 = LSINFINITY;
     }
 
-    nfa.options = 0;
+    /* Whether the route is preferred in route selection according to 16.4.1 */
+    nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0;
+
     nfa.tag = rt_tag;
-    nfa.oa = (po->backbone == NULL) ? HEAD(po->area_list) : po->backbone;
-    nfa.ar = nf1->n.ar;
-    nfa.nh = nh;
-    nfa.ifa = nhi;
     nfa.rid = en->lsa.rt;
-    ri_install(po, ip, pxlen, ORT_NET, &nfa, nfh);
+    nfa.oa = nf1->n.oa; /* undefined in RFC 2328 */
+    nfa.ifa = nhi;
+    nfa.nh = nh;
+
+    ri_install_ext(po, ip, pxlen, &nfa);
+  }
+}
+
+/* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
+static void
+ospf_check_vlinks(struct proto_ospf *po)
+{
+  struct proto *p = &po->proto;
+
+  struct ospf_iface *iface;
+  WALK_LIST(iface, po->iface_list)
+  {
+    if (iface->type == OSPF_IT_VLINK)
+    {
+      struct top_hash_entry *tmp;
+      tmp = ospf_hash_find_rt(po->gr, iface->voa->areaid, iface->vid);
+
+      if (tmp && (tmp->color == INSPF)
+	  && (tmp->dist < LSINFINITY)
+	  && ipa_nonzero(tmp->lb))
+      {
+        if ((iface->state != OSPF_IS_PTP)
+	    || (iface->vifa != tmp->nhi)
+	    || !ipa_equal(iface->vip, tmp->lb))
+        {
+          OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id);
+          ospf_iface_sm(iface, ISM_DOWN);
+	  iface->vifa = tmp->nhi;
+          iface->iface = tmp->nhi->iface;
+	  iface->addr = tmp->nhi->addr;
+	  iface->sk = tmp->nhi->sk;
+	  iface->cost = tmp->dist;
+          iface->vip = tmp->lb;
+          ospf_iface_sm(iface, ISM_UP);
+        }
+	else if ((iface->state == OSPF_IS_PTP) && (iface->cost != tmp->dist))
+	{
+	  iface->cost = tmp->dist;
+	  schedule_rt_lsa(po->backbone);
+	}
+      }
+      else
+      {
+        if (iface->state > OSPF_IS_DOWN)
+        {
+          OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", iface->vid);
+	  ospf_iface_sm(iface, ISM_DOWN);
+        }
+      }
+    }
+  }
+}
+/**
+ * ospf_rt_spf - calculate internal routes
+ * @po: OSPF protocol
+ *
+ * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
+ * It's based on Dijkstra's shortest path tree algorithms.
+ * This function is invoked from ospf_disp().
+ */
+void
+ospf_rt_spf(struct proto_ospf *po)
+{
+  struct proto *p = &po->proto;
+  struct ospf_area *oa;
+  ort *ri;
+  struct area_net *anet;
+
+  if (po->areano == 0) return;
+
+  po->cleanup = 1;
+
+  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
+
+  /* 16. (1) - Invalidate old routing table */
+  FIB_WALK(&po->rtf, nftmp)
+  {
+    ri = (ort *) nftmp;
+    memcpy(&ri->o, &ri->n, sizeof(orta));	/* Backup old data */
+    fill_ri(&ri->n);
   }
+  FIB_WALK_END;
+
+
+  WALK_LIST(oa, po->area_list)
+  {
+    FIB_WALK(&oa->rtr, nftmp)
+    {
+      ri = (ort *) nftmp;
+      memcpy(&ri->o, &ri->n, sizeof(orta));	/* Backup old data */
+      fill_ri(&ri->n);
+    }
+    FIB_WALK_END;
+
+    FIB_WALK(&oa->net_fib, nftmp)
+    {
+      anet = (struct area_net *) nftmp;
+      anet->active = 0;
+      anet->metric = 1;
+    }
+    FIB_WALK_END;
+
+    /* 16. (2) */
+    ospf_rt_spfa(oa);
+  }
+
+  /* 16. (3) */
+  if ((po->areano == 1) || (!po->backbone))
+    ospf_rt_sum(HEAD(po->area_list));
+  else
+    ospf_rt_sum(po->backbone);
+
+  /* 16. (4) */
+  WALK_LIST(oa, po->area_list)
+    if (oa->trcap && (oa->areaid != 0))
+      ospf_rt_sum_tr(oa);
+
+  /* G.3 */
+  if (po->backbone && po->backbone->rt &&
+      (((struct ospf_lsa_rt *) po->backbone->rt->lsa_body)->options & OPT_RT_V))
+    ospf_cleanup_vlinks(po);
+
+  /* 16. (5) */
+  ospf_ext_spf(po);
+
+  rt_sync(po);
 
+  po->calcrt = 0;
 }
 
 /* Add LSA into list of candidates in Dijkstra's algorithm */
@@ -1031,7 +1138,7 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
   if (dist >= en->dist)
     return;
   /*
-   * FIXME The line above (=) is not a bug, but we don't support multiple
+   * The line above (=) is not a bug, but we don't support multiple
    * next hops. I'll start as soon as nest will
    */
 
@@ -1146,7 +1253,7 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
        */
       neigh = NULL;
       WALK_LIST(ifa, po->iface_list)
-	if (ifa->type == OSPF_IT_PTP)
+	if ((ifa->type == OSPF_IT_PTP) || (ifa->type == OSPF_IT_VLINK))
 	{
 	  m = find_neigh(ifa, rid);
 	  if (m && (m->state == NEIGHBOR_FULL))
@@ -1191,7 +1298,7 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
       struct top_hash_entry *llsa;
       llsa = ospf_hash_find(po->gr, par->nhi->iface->index, en->lb_id, rid, LSA_T_LINK);
 
-      if (!llsa)
+      if (!llsa || ipa_zero(llsa->lladdr))
 	return 0;
 
       en->nh = llsa->lladdr;
@@ -1236,76 +1343,63 @@ again1:
     check_sum_lsa(po, nf, ORT_NET);
     if (reload || memcmp(&nf->n, &nf->o, sizeof(orta)))
     {				/* Some difference */
-      net *ne;
-      rta a0;
-      rte *e;
-
-      bzero(&a0, sizeof(a0));
-
-      a0.proto = p;
-      a0.source = nf->n.type;
-      a0.scope = SCOPE_UNIVERSE;
-      a0.cast = RTC_UNICAST;
-      a0.dest = RTD_ROUTER;
-      a0.flags = 0;
-      a0.aflags = 0;
-      a0.iface = NULL;
-      if (nf->n.ifa) a0.iface = nf->n.ifa->iface;
-      a0.gw = nf->n.nh;
-
-      if (ipa_nonzero(nf->n.nh) && (!neigh_find2(p, &nf->n.nh, nf->n.ifa->iface, 0)))
-      {
-        int found = 0;
-        struct ospf_iface *ifa;
-        struct top_hash_entry *en;
-        OSPF_TRACE(D_EVENTS, "Trying to find correct next hop %I/%d via %I", nf->fn.prefix, nf->fn.pxlen, nf->n.nh);
-        WALK_LIST(ifa, po->iface_list)
-        {
-          if ((ifa->type == OSPF_IT_VLINK) && ipa_equal(ifa->vip, nf->n.nh))
-          {
-            if ((en = ospf_hash_find_rt(po->gr, ifa->voa->areaid, ifa->vid))
-		&& (!ipa_equal(en->nh, IPA_NONE)))
-            {
-              a0.gw = en->nh;
-              found = 1;
-            }
-            break;
-          }
-        }
-        if (!found) nf->n.metric1 = LSINFINITY; /* Delete it */
-      }
+      net *ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
+
+      rta a0 = {
+	.proto = p,
+	.source = nf->n.type,
+	.scope = SCOPE_UNIVERSE,
+	.cast = RTC_UNICAST
+      };
 
-      if (ipa_equal(nf->n.nh, IPA_NONE)) a0.dest = RTD_DEVICE;
+      if (!nf->n.type)
+	goto remove1;
 
-      if (!a0.iface)	/* Still no match? Can this really happen? */
-        nf->n.metric1 = LSINFINITY;
+      /* The distance is unreachable (or farther) */
+      if (nf->n.metric1 >= LSINFINITY)
+	goto remove1;
 
-      ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
-      if (nf->n.metric1 < LSINFINITY)
+      a0.iface = nf->n.ifa->iface;
+      if (ipa_nonzero(nf->n.nh))
       {
-        e = rte_get_temp(&a0);
-        e->u.ospf.metric1 = nf->n.metric1;
-        e->u.ospf.metric2 = nf->n.metric2;
-        e->u.ospf.tag = nf->n.tag;
-        e->u.ospf.router_id = nf->n.rid;
-        e->pflags = 0;
-        e->net = ne;
-        e->pref = p->preference;
-        DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n",
-	  a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
-	rte_update(p->table, ne, p, p, e);
+	neighbor *ng;
+	a0.dest = RTD_ROUTER;
+	a0.gw = nf->n.nh;
+
+	ng = neigh_find2(p, &a0.gw, a0.iface, 0);
+	if (!ng || (ng->scope == SCOPE_HOST))
+	  goto remove1;
       }
       else
-      {
-        rte_update(p->table, ne, p, p, NULL);
-        FIB_ITERATE_PUT(&fit, nftmp);
-        fib_delete(fib, nftmp);
-        goto again1;
-      }
+	a0.dest = RTD_DEVICE;
+
+      /* Add the route */
+      rte *e = rte_get_temp(&a0);
+      e->u.ospf.metric1 = nf->n.metric1;
+      e->u.ospf.metric2 = nf->n.metric2;
+      e->u.ospf.tag = nf->n.tag;
+      e->u.ospf.router_id = nf->n.rid;
+      e->pflags = 0;
+      e->net = ne;
+      e->pref = p->preference;
+      DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n",
+	  a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
+      rte_update(p->table, ne, p, p, e);
+      goto cont1;
+    
+    remove1:
+      /* Remove the route */
+      rte_update(p->table, ne, p, p, NULL);
+      FIB_ITERATE_PUT(&fit, nftmp);
+      fib_delete(fib, nftmp);
+      goto again1;
     }
   }
+  cont1:
   FIB_ITERATE_END(nftmp);
 
+  ospf_check_vlinks(po);
+
   WALK_LIST(oa, po->area_list)
   {
     FIB_ITERATE_INIT(&fit, &oa->rtr);
@@ -1338,7 +1432,8 @@ again2:
       {
         int fl = flush;
 
-        if (oaa == oa) continue;
+        if (oaa == oa)
+	  continue;
 
 	if ((oa == po->backbone) && oaa->trcap) fl = 1;
 
diff --git a/proto/ospf/rt.h b/proto/ospf/rt.h
index 559fa5c..6b23bff 100644
--- a/proto/ospf/rt.h
+++ b/proto/ospf/rt.h
@@ -17,22 +17,31 @@
 typedef struct orta
 {
   int type;
-  u32 options;			
-  /* router-LSA style options (for ORT_ROUTER), with V,E,B bits.
-     In OSPFv2, ASBRs from another areas (that we know from rt-summary-lsa),
-     have just ORTA_ASBR in options, their real options are unknown */
+  u32 options;
+  /*
+   * For ORT_ROUTER routes, options field are router-LSA style
+   * options, with V,E,B bits. In OSPFv2, ASBRs from another areas
+   * (that we know from rt-summary-lsa) have just ORTA_ASBR in
+   * options, their real options are unknown.
+   */
 #define ORTA_ASBR OPT_RT_E
 #define ORTA_ABR  OPT_RT_B
-  struct ospf_area *oa;
+  /*
+   * For ORT_NET routes, the field is almost unused with one
+   * exception: ORTA_PREF for external routes means that the route is
+   * preferred in AS external route selection according to 16.4.1. -
+   * it is intra-area path using non-backbone area. In other words,
+   * the forwarding address (or ASBR if forwarding address is zero) is
+   * intra-area (type == RTS_OSPF) and its area is not a backbone.
+   */
+#define ORTA_PREF 0x80000000
   u32 metric1;
   u32 metric2;
-  ip_addr nh;			/* Next hop */
-  struct ospf_iface *ifa;	/* Outgoing interface */
-  struct top_hash_entry *ar;	/* Advertising router (or ABR) */
   u32 tag;
   u32 rid;			/* Router ID of real advertising router */
-  /* For ext-LSA from different area, 'ar' is a type 1 LSA of ABR.
-     Router ID of real advertising router is stored in 'rid'. */
+  struct ospf_area *oa;
+  struct ospf_iface *ifa;	/* Outgoing interface */
+  ip_addr nh;			/* Next hop */
 }
 orta;
 
@@ -41,7 +50,6 @@ typedef struct ort
   struct fib_node fn;
   orta n;
   orta o;
-  struct ort *efn;		/* For RFC1583 */
 }
 ort;
 
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index 885c39b..be9e434 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -1114,6 +1114,8 @@ originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length)
   struct proto_ospf *po = oa->po;
   struct ospf_iface *ifa;
   struct ospf_lsa_prefix *lp;
+  struct ifa *vlink_addr = NULL;
+  int host_addr = 0;
   int net_lsa;
   int i = 0;
   u8 flags;
@@ -1139,10 +1141,15 @@ originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length)
     struct ifa *a;
     WALK_LIST(a, ifa->iface->addrs)
       {
-	if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) ||
-	    (a->flags & IA_SECONDARY) ||
+	if ((a->flags & IA_SECONDARY) ||
 	    (a->flags & IA_UNNUMBERED) ||
-	    (a->scope <= SCOPE_LINK) ||
+	    (a->scope <= SCOPE_LINK))
+	  continue;
+
+	if (!vlink_addr)
+	  vlink_addr = a;
+
+	if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) ||
 	    configured_stubnet(oa, a))
 	  continue;
 
@@ -1150,10 +1157,20 @@ originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length)
 	put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(a->pxlen)),
 			a->ip, a->pxlen, flags, ifa->cost);
 	i++;
+
+	if (flags & OPT_PX_LA)
+	  host_addr = 1;
       }
   }
 
-  /* FIXME Handle vlinks? see RFC5340, page 38 */
+  /* If there are some configured vlinks, add some global address,
+     which will be used as a vlink endpoint. */
+  if (!EMPTY_LIST(oa->ac->vlink_list) && !host_addr && vlink_addr)
+  {
+    put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(MAX_PREFIX_LENGTH)),
+		    vlink_addr->ip, MAX_PREFIX_LENGTH, OPT_PX_LA, 0);
+    i++;
+  }
 
   struct ospf_stubnet_config *sn;
   WALK_LIST(sn, oa->ac->stubnet_list)
@@ -1227,6 +1244,7 @@ prefix_advance(u32 *buf)
   return buf + IPV6_PREFIX_WORDS(pxl);
 }
 
+/* FIXME eliminate items wit LA bit set? see 4.4.3.9 */
 static void
 add_prefix(struct proto_ospf *po, u32 *px, int offset, int *pxc)
 {
diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h
index 16d4c78..7aa1625 100644
--- a/proto/ospf/topology.h
+++ b/proto/ospf/topology.h
@@ -21,7 +21,7 @@ struct top_hash_entry
   void *lsa_body;
   bird_clock_t inst_t;		/* Time of installation into DB */
   ip_addr nh;			/* Next hop */
-  ip_addr lb;			/* Link back */
+  ip_addr lb;			/* In OSPFv2, link back address. In OSPFv3, any global address in the area useful for vlinks */
   struct ospf_iface *nhi;	/* Next hop interface */
 #ifdef OSPFv3
   u32 lb_id;			/* Interface ID of link back iface (for bcast or NBMA networks) */
-- 
cgit v1.2.3


From 0ea8fb4abe5acad0b8f470bbdc5cc929b6a58ced Mon Sep 17 00:00:00 2001
From: Ondrej Zajicek <santiago@crfreenet.org>
Date: Sat, 24 Apr 2010 15:18:21 +0200
Subject: Fixes and enhancements in 'show ospf state' command.

Now it shows a distance, option to change showing reachable/all network
nodes and better handling of AS-external LSAs in multiple areas. The
command 'show ospf topology' was changed to not show stubnets in both
OSPFv2 and OSPFv3 (previously it displayed stubnets in OSPFv2).
---
 doc/bird.sgml         |  19 +++--
 proto/ospf/config.Y   |  18 +++-
 proto/ospf/iface.c    |   1 -
 proto/ospf/lsalib.c   |   8 +-
 proto/ospf/ospf.c     | 224 ++++++++++++++++++++++++++++++++++++++------------
 proto/ospf/ospf.h     |   3 +-
 proto/ospf/rt.c       |   9 +-
 proto/ospf/topology.h |   2 +-
 8 files changed, 209 insertions(+), 75 deletions(-)

diff --git a/doc/bird.sgml b/doc/bird.sgml
index 64185e9..61ebc7a 100644
--- a/doc/bird.sgml
+++ b/doc/bird.sgml
@@ -490,13 +490,18 @@ This argument can be omitted if there exists only a single instance.
 	<tag>show ospf neighbors [<m/name/] ["<m/interface/"]</tag>
 	Show a list of OSPF neighbors and a state of adjacency to them.
 
-	<tag>show ospf state [<m/name/]</tag>
-	Show detailed information about OSPF areas based on a content of link-state database.
-	It shows network topology,  aggregated networks and routers from other areas and external routes.
-
-	<tag>show ospf topology [<m/name/]</tag>
-	Show a topology of OSPF areas based on a content of link-state database.
-	It is just a stripped-down version of 'show ospf state'.
+	<tag>show ospf state [all] [<m/name/]</tag>
+	Show detailed information about OSPF areas based on a content
+	of the link-state database. It shows network topology, stub
+	networks, aggregated networks and routers from other areas and
+	external routes. The command shows information about reachable
+	network nodes, use option <cf/all/ to show information about
+	all network nodes in the link-state database.
+
+	<tag>show ospf topology [all] [<m/name/]</tag>
+	Show a topology of OSPF areas based on a content of the
+	link-state database.  It is just a stripped-down version of
+	'show ospf state'.
 
 	<tag>show static [<m/name/]</tag>
 	Show detailed information about static routes.
diff --git a/proto/ospf/config.Y b/proto/ospf/config.Y
index 2196af7..5caba00 100644
--- a/proto/ospf/config.Y
+++ b/proto/ospf/config.Y
@@ -314,11 +314,21 @@ CF_CLI(SHOW OSPF NEIGHBORS, optsym opttext, [<name>] [\"<interface>\"], [[Show i
 CF_CLI(SHOW OSPF INTERFACE, optsym opttext, [<name>] [\"<interface>\"], [[Show information about interface]])
 { ospf_sh_iface(proto_get_named($4, &proto_ospf), $5); };
 
-CF_CLI(SHOW OSPF TOPOLOGY, optsym opttext, [<name>], [[Show information about OSPF network topology]])
-{ ospf_sh_state(proto_get_named($4, &proto_ospf), 0); };
+CF_CLI_HELP(SHOW OSPF TOPOLOGY, [all] [<name>], [[Show information about OSPF network topology]])
 
-CF_CLI(SHOW OSPF STATE, optsym opttext, [<name>], [[Show information about OSPF network state]])
-{ ospf_sh_state(proto_get_named($4, &proto_ospf), 1); };
+CF_CLI(SHOW OSPF TOPOLOGY, optsym opttext, [<name>], [[Show information about reachable OSPF network topology]])
+{ ospf_sh_state(proto_get_named($4, &proto_ospf), 0, 1); };
+
+CF_CLI(SHOW OSPF TOPOLOGY ALL, optsym opttext, [<name>], [[Show information about all OSPF network topology]])
+{ ospf_sh_state(proto_get_named($5, &proto_ospf), 0, 0); };
+
+CF_CLI_HELP(SHOW OSPF STATE, [all] [<name>], [[Show information about OSPF network state]])
+
+CF_CLI(SHOW OSPF STATE, optsym opttext, [<name>], [[Show information about reachable OSPF network state]])
+{ ospf_sh_state(proto_get_named($4, &proto_ospf), 1, 1); };
+
+CF_CLI(SHOW OSPF STATE ALL, optsym opttext, [<name>], [[Show information about all OSPF network state]])
+{ ospf_sh_state(proto_get_named($5, &proto_ospf), 1, 0); };
 
 CF_CLI(SHOW OSPF LSADB, optsym opttext, [<name>], [[Show content of OSPF LSA database]])
 { ospf_sh_lsadb(proto_get_named($4, &proto_ospf)); };
diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c
index f401326..b5a509a 100644
--- a/proto/ospf/iface.c
+++ b/proto/ospf/iface.c
@@ -804,5 +804,4 @@ ospf_iface_shutdown(struct ospf_iface *ifa)
 {
   init_list(&ifa->neigh_list);
   hello_timer_hook(ifa->hello_timer);
-  ospf_sk_close(ifa);
 }
diff --git a/proto/ospf/lsalib.c b/proto/ospf/lsalib.c
index 35f02dc..53c2562 100644
--- a/proto/ospf/lsalib.c
+++ b/proto/ospf/lsalib.c
@@ -45,19 +45,16 @@ ospf_age(struct proto_ospf *po)
   struct top_hash_entry *en, *nxt;
   int flush = can_flush_lsa(po);
 
-  if (po->cleanup) OSPF_TRACE(D_EVENTS, "Running ospf_age cleanup");
-
   WALK_SLIST_DELSAFE(en, nxt, po->lsal)
   {
-    if (po->cleanup)
+    if (po->calcrt)
     {
+      /* Cleanup before ospf_rt_spf() */
       en->color = OUTSPF;
       en->dist = LSINFINITY;
       en->nhi = NULL;
       en->nh = IPA_NONE;
       en->lb = IPA_NONE;
-      DBG("Infinitying Type: %u, Id: %R, Rt: %R\n", en->lsa.type,
-	  en->lsa.id, en->lsa.rt);
     }
     if (en->lsa.age == LSA_MAXAGE)
     {
@@ -88,7 +85,6 @@ ospf_age(struct proto_ospf *po)
 	en->lsa.age = LSA_MAXAGE;
     }
   }
-  po->cleanup = 0;
 }
 
 void
diff --git a/proto/ospf/ospf.c b/proto/ospf/ospf.c
index 107e3a4..5929919 100644
--- a/proto/ospf/ospf.c
+++ b/proto/ospf/ospf.c
@@ -75,7 +75,7 @@
  * 
  * The function area_disp() is
  * responsible for late originating of router LSA and network LSA
- * and for cleanup after routing table calculation process in
+ * and for cleanup before routing table calculation process in
  * the area.
  * To every &ospf_iface, we connect one or more
  * &ospf_neighbor's -- a structure containing many timers and queues
@@ -161,7 +161,6 @@ ospf_start(struct proto *p)
   fib_init(&po->rtf, p->pool, sizeof(ort), 16, ospf_rt_initort);
   po->areano = 0;
   po->gr = ospf_top_new(p->pool);
-  po->cleanup = 1;
   s_init_list(&(po->lsal));
   if (EMPTY_LIST(c->area_list))
   {
@@ -1134,8 +1133,34 @@ lsa_compare_for_state(const void *p1, const void *p2)
   }
 }
 
+static int
+ext_compare_for_state(const void *p1, const void *p2)
+{
+  struct top_hash_entry * he1 = * (struct top_hash_entry **) p1;
+  struct top_hash_entry * he2 = * (struct top_hash_entry **) p2;
+  struct ospf_lsa_header *lsa1 = &(he1->lsa);
+  struct ospf_lsa_header *lsa2 = &(he2->lsa);
+
+  if (lsa1->rt != lsa2->rt)
+    return lsa1->rt - lsa2->rt;
+
+  if (lsa1->id != lsa2->id)
+    return lsa1->id - lsa2->id;
+ 
+  return lsa1->sn - lsa2->sn;
+}
+
+static inline void
+show_lsa_distance(struct top_hash_entry *he)
+{
+  if (he->color == INSPF)
+    cli_msg(-1016, "\t\tdistance %u", he->dist);
+  else
+    cli_msg(-1016, "\t\tunreachable");
+}
+
 static inline void
-show_lsa_router(struct proto_ospf *po, struct top_hash_entry *he)
+show_lsa_router(struct proto_ospf *po, struct top_hash_entry *he, int first, int verbose)
 {
   struct ospf_lsa_header *lsa = &(he->lsa);
   struct ospf_lsa_rt *rt = he->lsa_body;
@@ -1143,6 +1168,14 @@ show_lsa_router(struct proto_ospf *po, struct top_hash_entry *he)
   int max = lsa_rt_count(lsa);
   int i;
 
+  if (first)
+  {
+    cli_msg(-1016, "");
+    cli_msg(-1016, "\trouter %R", he->lsa.rt);
+    show_lsa_distance(he);
+  }
+
+
   for (i = 0; i < max; i++)
     if (rr[i].type == LSART_VLNK)
       cli_msg(-1016, "\t\tvlink %R metric %u", rr[i].id, rr[i].metric);
@@ -1175,6 +1208,9 @@ show_lsa_router(struct proto_ospf *po, struct top_hash_entry *he)
     }
 
 #ifdef OSPFv2
+  if (!verbose)
+    return;
+
   for (i = 0; i < max; i++)
     if (rr[i].type == LSART_STUB)
       cli_msg(-1016, "\t\tstubnet %I/%d metric %u", ipa_from_u32(rr[i].id),
@@ -1198,6 +1234,8 @@ show_lsa_network(struct top_hash_entry *he)
   cli_msg(-1016, "\tnetwork [%R-%u]", lsa->rt, lsa->id);
 #endif
 
+  show_lsa_distance(he);
+
   for (i = 0; i < lsa_net_count(lsa); i++)
     cli_msg(-1016, "\t\trouter %R", ln->routers[i]);
 }
@@ -1251,6 +1289,8 @@ show_lsa_external(struct top_hash_entry *he)
   int pxlen, ebit, rt_fwaddr_valid;
   u32 rt_tag, rt_metric;
 
+  he->domain = 0; /* Unmark the LSA */
+
   rt_metric = ext->metric & METRIC_MASK;
   ebit = ext->metric & LSA_EXT_EBIT;
 #ifdef OSPFv2
@@ -1289,7 +1329,7 @@ show_lsa_external(struct top_hash_entry *he)
 
 #ifdef OSPFv3
 static inline void
-show_lsa_prefix(struct top_hash_entry *he, struct ospf_lsa_header *olsa)
+show_lsa_prefix(struct top_hash_entry *he, struct ospf_lsa_header *cnode)
 {
   struct ospf_lsa_prefix *px = he->lsa_body;
   ip_addr pxa;
@@ -1299,10 +1339,14 @@ show_lsa_prefix(struct top_hash_entry *he, struct ospf_lsa_header *olsa)
   u32 *buf;
   int i;
 
-  /* We check whether given prefix-LSA is related to the last non-prefix-LSA */
-  if ((olsa == NULL) || (olsa->type != px->ref_type) || (olsa->rt != px->ref_rt) ||
-      !(((px->ref_type == LSA_T_RT)  && (px->ref_id == 0)) ||
-	((px->ref_type == LSA_T_NET) && (px->ref_id == olsa->id))))
+  /* We check whether given prefix-LSA is related to the current node */
+  if ((px->ref_type != cnode->type) || (px->ref_rt != cnode->rt))
+    return;
+
+  if ((px->ref_type == LSA_T_RT) && (px->ref_id != 0))
+    return;
+
+  if ((px->ref_type == LSA_T_NET) && (px->ref_id != cnode->id))
     return;
 
   buf = px->rest;
@@ -1319,18 +1363,14 @@ show_lsa_prefix(struct top_hash_entry *he, struct ospf_lsa_header *olsa)
 #endif
 
 void
-ospf_sh_state(struct proto *p, int verbose)
+ospf_sh_state(struct proto *p, int verbose, int reachable)
 {
   struct proto_ospf *po = (struct proto_ospf *) p;
-  struct top_graph *f = po->gr;
-  unsigned int i, j1, j2;
-  u32 last_rt = 0xFFFFFFFF;
+  struct ospf_lsa_header *cnode = NULL;
+  int num = po->gr->hash_entries;
+  unsigned int i, ix, j1, j2, jx;
   u32 last_area = 0xFFFFFFFF;
 
-#ifdef OSPFv3
-  struct ospf_lsa_header *olsa = NULL;
-#endif
-
   if (p->proto_state != PS_UP)
   {
     cli_msg(-1016, "%s: is not up", p->name);
@@ -1338,10 +1378,14 @@ ospf_sh_state(struct proto *p, int verbose)
     return;
   }
 
-  struct top_hash_entry *hea[f->hash_entries];
+  /* We store interesting area-scoped LSAs in array hea and 
+     global-scoped (LSA_T_EXT) LSAs in array hex */
+
+  struct top_hash_entry *hea[num];
+  struct top_hash_entry *hex[verbose ? num : 0];
   struct top_hash_entry *he;
 
-  j1 = j2 = 0;
+  j1 = j2 = jx = 0;
   WALK_SLIST(he, po->lsal)
   {
     int accept;
@@ -1355,13 +1399,18 @@ ospf_sh_state(struct proto *p, int verbose)
 
       case LSA_T_SUM_NET:
       case LSA_T_SUM_RT:
-      case LSA_T_EXT:
 #ifdef OSPFv3
       case LSA_T_PREFIX:
 #endif
 	accept = verbose;
 	break;
 
+      case LSA_T_EXT:
+	if (verbose)
+	{
+	  he->domain = 1; /* Abuse domain field to mark the LSA */
+	  hex[jx++] = he;
+	}
       default:
 	accept = 0;
       }
@@ -1372,66 +1421,137 @@ ospf_sh_state(struct proto *p, int verbose)
       j2++;
   }
 
-  if ((j1 + j2) != f->hash_entries)
+  if ((j1 + j2) != num)
     die("Fatal mismatch");
 
   qsort(hea, j1, sizeof(struct top_hash_entry *), lsa_compare_for_state);
+  qsort(hex, jx, sizeof(struct top_hash_entry *), ext_compare_for_state);
 
+  /*
+   * This code is a bit tricky, we have a primary LSAs (router and
+   * network) that are presented as a node, and secondary LSAs that
+   * are presented as a part of a primary node. cnode represents an
+   * currently opened node (whose header was presented). The LSAs are
+   * sorted to get secondary LSAs just after related primary LSA (if
+   * available). We present secondary LSAs only when related primary
+   * LSA is opened.
+   *
+   * AS-external LSAs are stored separately as they might be presented
+   * several times (for each area when related ASBR is opened). When
+   * the node is closed, related external routes are presented. We
+   * also have to take into account that in OSPFv3, there might be
+   * more router-LSAs and only the first should be considered as a
+   * primary. This is handled by not closing old router-LSA when next
+   * one is processed (which is not opened because there is already
+   * one opened).
+   */
+
+  ix = 0;
   for (i = 0; i < j1; i++)
   {
-    if (last_area != hea[i]->domain)
-    {
-      cli_msg(-1016, "");
-      cli_msg(-1016, "area %R", hea[i]->domain);
-      last_area = hea[i]->domain;
-      last_rt = 0xFFFFFFFF;
-    }
+    he = hea[i];
 
-    if ((hea[i]->lsa.rt != last_rt) && (hea[i]->lsa.type != LSA_T_NET)
-#ifdef OSPFv3
-	&& (hea[i]->lsa.type != LSA_T_PREFIX)
-#endif
-	)
+    /* If there is no opened node, we open the LSA (if appropriate) or skip to the next one */
+    if (!cnode)
     {
-      cli_msg(-1016, "");
-      cli_msg(-1016, (hea[i]->lsa.type != LSA_T_EXT) ? "\trouter %R" : "\txrouter %R", hea[i]->lsa.rt);
-      last_rt = hea[i]->lsa.rt;
+      if (((he->lsa.type == LSA_T_RT) || (he->lsa.type == LSA_T_NET))
+	  && ((he->color == INSPF) || !reachable))
+      {
+	cnode = &(he->lsa);
+
+	if (he->domain != last_area)
+	{
+	  cli_msg(-1016, "");
+	  cli_msg(-1016, "area %R", he->domain);
+	  last_area = he->domain;
+	  ix = 0;
+	}
+      }
+      else
+	continue;
     }
 
-    switch (hea[i]->lsa.type)
+    ASSERT(cnode && (he->domain == last_area) && (he->lsa.rt == cnode->rt));
+
+    switch (he->lsa.type)
     {
       case LSA_T_RT:
-        show_lsa_router(po, hea[i]);
+	show_lsa_router(po, he, he->lsa.id == cnode->id, verbose);
 	break;
 
       case LSA_T_NET:
-	show_lsa_network(hea[i]);
+	show_lsa_network(he);
 	break;
 
       case LSA_T_SUM_NET:
-	show_lsa_sum_net(hea[i]);
+	if (cnode->type == LSA_T_RT)
+	  show_lsa_sum_net(he);
 	break;
 
       case LSA_T_SUM_RT:
-	show_lsa_sum_rt(hea[i]);
-	break;
-
-      case LSA_T_EXT:
-	show_lsa_external(hea[i]);
+	if (cnode->type == LSA_T_RT)
+	  show_lsa_sum_rt(he);
 	break;
 
 #ifdef OSPFv3
       case LSA_T_PREFIX:
-	show_lsa_prefix(hea[i], olsa);
+	show_lsa_prefix(he, cnode);
 	break;
 #endif
+
+      case LSA_T_EXT:
+	show_lsa_external(he);
+	break;
     }
 
-#ifdef OSPFv3
-    if (hea[i]->lsa.type != LSA_T_PREFIX)
-      olsa = &(hea[i]->lsa);
-#endif
+    /* In these cases, we close the current node */
+    if ((i+1 == j1)
+	|| (hea[i+1]->domain != last_area)
+	|| (hea[i+1]->lsa.rt != cnode->rt)
+	|| (hea[i+1]->lsa.type == LSA_T_NET))
+    {
+      while ((ix < jx) && (hex[ix]->lsa.rt < cnode->rt))
+	ix++;
+
+      while ((ix < jx) && (hex[ix]->lsa.rt == cnode->rt))
+	show_lsa_external(hex[ix++]);
+
+      cnode = NULL;
+    }
+  }
+
+  int hdr = 0;
+  u32 last_rt = 0xFFFFFFFF;
+  for (ix = 0; ix < jx; ix++)
+  {
+    he = hex[ix];
+
+    /* If it is still marked, we show it now. */
+    if (he->domain)
+    {
+      he->domain = 0;
+
+      if ((he->color != INSPF) && reachable)
+	continue;
+
+      if (!hdr)
+      {
+	cli_msg(-1016, "");
+	cli_msg(-1016, "other ASBRs");
+	hdr = 1;
+      }
+
+      if (he->lsa.rt != last_rt)
+      {
+	cli_msg(-1016, "");
+	cli_msg(-1016, "\trouter %R", he->lsa.rt);
+	last_rt = he->lsa.rt;
+      }
+
+      show_lsa_external(he);
+    }
   }
+
   cli_msg(0, "");
 }
 
@@ -1468,7 +1588,7 @@ void
 ospf_sh_lsadb(struct proto *p)
 {
   struct proto_ospf *po = (struct proto_ospf *) p;
-  struct top_graph *f = po->gr;
+  int num = po->gr->hash_entries;
   unsigned int i, j;
   int last_dscope = -1;
   u32 last_domain = 0;
@@ -1480,14 +1600,14 @@ ospf_sh_lsadb(struct proto *p)
     return;
   }
 
-  struct top_hash_entry *hea[f->hash_entries];
+  struct top_hash_entry *hea[num];
   struct top_hash_entry *he;
 
   j = 0;
   WALK_SLIST(he, po->lsal)
     hea[j++] = he;
 
-  if (j != f->hash_entries)
+  if (j != num)
     die("Fatal mismatch");
 
   qsort(hea, j, sizeof(struct top_hash_entry *), lsa_compare_for_lsadb);
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index bb0b6af..103ca55 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -722,7 +722,6 @@ struct proto_ospf
   slist lsal;			/* List of all LSA's */
   int calcrt;			/* Routing table calculation scheduled?
 				   0=no, 1=normal, 2=forced reload */
-  int cleanup;                  /* Should I cleanup after RT calculation? */
   list iface_list;		/* Interfaces we really use */
   list area_list;
   int areano;			/* Number of area I belong to */
@@ -808,7 +807,7 @@ static inline void schedule_link_lsa(struct ospf_iface *ifa UNUSED) {}
 void ospf_sh_neigh(struct proto *p, char *iff);
 void ospf_sh(struct proto *p);
 void ospf_sh_iface(struct proto *p, char *iff);
-void ospf_sh_state(struct proto *p, int verbose);
+void ospf_sh_state(struct proto *p, int verbose, int reachable);
 void ospf_sh_lsadb(struct proto *p);
 
 
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index d685961..9e63d2c 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -681,6 +681,10 @@ ospf_rt_sum(struct ospf_area *oa)
     if (!(abr->n.options & ORTA_ABR))
       continue;
 
+    /* This check is not mentioned in RFC 2328 */
+    if (abr->n.type != RTS_OSPF)
+      continue;
+
     /* 16.2. (5) */
     orta nf = {
       .type = RTS_OSPF_IA,
@@ -966,6 +970,9 @@ ospf_ext_spf(struct proto_ospf *po)
       nfa.metric2 = LSINFINITY;
     }
 
+    /* Mark the LSA as reachable */
+    en->color = INSPF;
+
     /* Whether the route is preferred in route selection according to 16.4.1 */
     nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0;
 
@@ -1046,8 +1053,6 @@ ospf_rt_spf(struct proto_ospf *po)
 
   if (po->areano == 0) return;
 
-  po->cleanup = 1;
-
   OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
 
   /* 16. (1) - Invalidate old routing table */
diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h
index 7aa1625..2481676 100644
--- a/proto/ospf/topology.h
+++ b/proto/ospf/topology.h
@@ -22,7 +22,7 @@ struct top_hash_entry
   bird_clock_t inst_t;		/* Time of installation into DB */
   ip_addr nh;			/* Next hop */
   ip_addr lb;			/* In OSPFv2, link back address. In OSPFv3, any global address in the area useful for vlinks */
-  struct ospf_iface *nhi;	/* Next hop interface */
+  struct ospf_iface *nhi;	/* Next hop interface - valid only in ospf_rt_spf()*/
 #ifdef OSPFv3
   u32 lb_id;			/* Interface ID of link back iface (for bcast or NBMA networks) */
 #endif
-- 
cgit v1.2.3


From c1b51598d49ff737b926bd8ad2e308a5a15ce3a2 Mon Sep 17 00:00:00 2001
From: Ondrej Zajicek <santiago@crfreenet.org>
Date: Sun, 25 Apr 2010 19:13:49 +0200
Subject: Implements changes in checksum alg suggested by Joakim Tjernlund.

---
 lib/checksum.c | 51 ++++++++++++++++++---------------------------------
 1 file changed, 18 insertions(+), 33 deletions(-)

diff --git a/lib/checksum.c b/lib/checksum.c
index 33cb386..18b1f92 100644
--- a/lib/checksum.c
+++ b/lib/checksum.c
@@ -15,26 +15,21 @@
 #include "nest/bird.h"
 #include "checksum.h"
 
-static u16				/* One-complement addition */
-add16(u16 sum, u16 x)
-{
-  u16 z = sum + x;
-  return z + (z < sum);
-}
-
-static u32
+static inline u32
 add32(u32 sum, u32 x)
 {
   u32 z = sum + x;
-  return z + (z < sum);
+//  return z + (z < sum);
+
+ /* add carry */
+  if (z < x)
+    z++;
+  return z;
 }
 
 static u16
-ipsum_calc_block(u16 *x, unsigned len, u16 sum)
+ipsum_calc_block(u32 *buf, unsigned len, u16 isum)
 {
-  int rest;
-  u32 tmp, *xx;
-
   /*
    *  A few simple facts about the IP checksum (see RFC 1071 for detailed
    *  discussion):
@@ -47,27 +42,17 @@ ipsum_calc_block(u16 *x, unsigned len, u16 sum)
    *  usual alignment requirements and is reasonably fast.
    */
 
-  ASSERT(!(len % 2));
+  ASSERT(!(len % 4));
   if (!len)
-    return sum;
-  len >>= 1;
-  if ((unsigned long) x & 2)		/* Align to 32-bit boundary */
-    {
-      sum = add16(sum, *x++);
-      len--;
-    }
-  rest = len & 1;
-  len >>= 1;
-  tmp = 0;
-  xx = (u32 *) x;
-  while (len)
-    {
-      tmp = add32(tmp, *xx++);
-      len--;
-    }
-  sum = add16(sum, add16(tmp & 0xffff, tmp >> 16U));
-  if (rest)
-    sum = add16(sum, *(u16 *) xx);
+    return isum;
+
+  u32 *end = buf + (len >> 2);
+  u32 sum = isum;
+  while (buf < end)
+    sum = add32(sum, *buf++);
+
+  sum = (sum >> 16) + (sum & 0xffff);    /* add high-16 to low-16 */
+  sum += (sum >> 16); /* add carry */
   return sum;
 }
 
-- 
cgit v1.2.3


From 4e5fb4b60c59db3248fd12db2bc6f0424d798122 Mon Sep 17 00:00:00 2001
From: Ondrej Zajicek <santiago@crfreenet.org>
Date: Sun, 25 Apr 2010 20:12:34 +0200
Subject: Skip LSA host<->network endianity conversions on big endians.

---
 proto/ospf/lsalib.c |  6 ++++--
 proto/ospf/lsalib.h | 12 ++++++++++++
 2 files changed, 16 insertions(+), 2 deletions(-)

diff --git a/proto/ospf/lsalib.c b/proto/ospf/lsalib.c
index 53c2562..c932fe0 100644
--- a/proto/ospf/lsalib.c
+++ b/proto/ospf/lsalib.c
@@ -87,6 +87,7 @@ ospf_age(struct proto_ospf *po)
   }
 }
 
+#ifndef CPU_BIG_ENDIAN
 void
 htonlsah(struct ospf_lsa_header *h, struct ospf_lsa_header *n)
 {
@@ -138,6 +139,7 @@ ntohlsab(void *n, void *h, u16 len)
   for (i = 0; i < (len / sizeof(u32)); i++)
     hid[i] = ntohl(nid[i]);
 }
+#endif /* little endian */
 
 /*
 void
@@ -184,7 +186,7 @@ lsasum_calculate(struct ospf_lsa_header *h, void *body)
 
   //  log(L_WARN "Checksum %R %R %d start (len %d)", h->id, h->rt, h->type, length);
   htonlsah(h, h);
-  htonlsab(body, body, length - sizeof(struct ospf_lsa_header));
+  htonlsab1(body, length - sizeof(struct ospf_lsa_header));
 
   /*
   char buf[1024];
@@ -198,7 +200,7 @@ lsasum_calculate(struct ospf_lsa_header *h, void *body)
   //  log(L_WARN "Checksum result %4x", h->checksum);
 
   ntohlsah(h, h);
-  ntohlsab(body, body, length - sizeof(struct ospf_lsa_header));
+  ntohlsab1(body, length - sizeof(struct ospf_lsa_header));
 }
 
 /*
diff --git a/proto/ospf/lsalib.h b/proto/ospf/lsalib.h
index a799de3..f98a1bd 100644
--- a/proto/ospf/lsalib.h
+++ b/proto/ospf/lsalib.h
@@ -10,10 +10,22 @@
 #ifndef _BIRD_OSPF_LSALIB_H_
 #define _BIRD_OSPF_LSALIB_H_
 
+#ifdef CPU_BIG_ENDIAN
+static inline void htonlsah(struct ospf_lsa_header *h, struct ospf_lsa_header *n) { *n = *h; };
+static inline void ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h) { *h = *n; };
+static inline void htonlsab(void *h, void *n, u16 len) { memcpy(n, h, len); };
+static inline void ntohlsab(void *n, void *h, u16 len) { memcpy(h, n, len); };
+static inline void htonlsab1(void *h, u16 len) { };
+static inline void ntohlsab1(void *n, u16 len) { };
+#else
 void htonlsah(struct ospf_lsa_header *h, struct ospf_lsa_header *n);
 void ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h);
 void htonlsab(void *h, void *n, u16 len);
 void ntohlsab(void *n, void *h, u16 len);
+static inline void htonlsab1(void *h, u16 len) { htonlsab(h, h, len); };
+static inline void ntohlsab1(void *n, u16 len) { ntohlsab(n, n, len); };
+#endif
+
 void lsasum_calculate(struct ospf_lsa_header *header, void *body);
 u16 lsasum_check(struct ospf_lsa_header *h, void *body);
 #define CMP_NEWER 1
-- 
cgit v1.2.3


From 9d1ee1388771a3caa6c23163571a80457adfab2c Mon Sep 17 00:00:00 2001
From: Ondrej Zajicek <santiago@crfreenet.org>
Date: Mon, 26 Apr 2010 19:08:57 +0200
Subject: Neighbors on OSPF broadcast networks should be identified by IP
 address, not RID.

Allows simple support for multiple interfaces to the same network.
---
 proto/ospf/packet.c | 25 ++++++++++++++++++++++---
 1 file changed, 22 insertions(+), 3 deletions(-)

diff --git a/proto/ospf/packet.c b/proto/ospf/packet.c
index e78eeea..74ce550 100644
--- a/proto/ospf/packet.c
+++ b/proto/ospf/packet.c
@@ -242,6 +242,19 @@ ospf_pkt_checkauth(struct ospf_neighbor *n, struct ospf_iface *ifa, struct ospf_
  
 #endif
 
+#ifdef OSPFv2
+static inline struct ospf_neighbor *
+find_neigh_by_ip(struct ospf_iface *ifa, ip_addr ip)
+{
+  struct ospf_neighbor *n;
+  WALK_LIST(n, ifa->neigh_list)
+    if (ipa_equal(n->ip, ip))
+      return n;
+  return NULL;
+}
+#endif
+
+
 
 /**
  * ospf_rx_hook
@@ -419,10 +432,16 @@ ospf_rx_hook(sock *sk, int size)
     return 1;
   }
 
-  /* This is deviation from RFC 2328 - neighbours should be identified by
-   * IP address on broadcast and NBMA networks.
-   */
+#ifdef OSPFv2
+  /* In OSPFv2, neighbors are identified by either IP or Router ID, base on network type */
+  struct ospf_neighbor *n;
+  if ((ifa->type == OSPF_IT_BCAST) || (ifa->type == OSPF_IT_NBMA))
+    n = find_neigh_by_ip(ifa, sk->faddr);
+  else
+    n = find_neigh(ifa, rid);
+#else
   struct ospf_neighbor *n = find_neigh(ifa, rid);
+#endif
 
   if(!n && (ps->type != HELLO_P))
   {
-- 
cgit v1.2.3