path: root/proto/ospf/rt.c

/*
 *	BIRD -- OSPF
 *
 *	(c) 2000--2004 Ondrej Filip <feela@network.cz>
 *	(c) 2009--2014 Ondrej Zajicek <santiago@crfreenet.org>
 *	(c) 2009--2014 CZ.NIC z.s.p.o.
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#include "ospf.h"

static void add_cand(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par, u32 dist, int i, uint data, uint lif, uint nif);
static void rt_sync(struct ospf_proto *p);


static inline void reset_ri(ort *ort)
{
  bzero(&ort->n, sizeof(orta));
}

static inline int
nh_is_vlink(struct nexthop *nhs)
{
  return !nhs->iface;
}

static inline int
unresolved_vlink(ort *ort)
{
  return ort->n.nhs && nh_is_vlink(ort->n.nhs);
}

static inline struct nexthop *
new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight)
{
  struct nexthop *nh = lp_allocz(p->nhpool, sizeof(struct nexthop));
  nh->gw = gw;
  nh->iface = iface;
  nh->weight = weight;
  return nh;
}

/* Returns true if there are device nexthops in n */
static inline int
has_device_nexthops(const struct nexthop *n)
{
  for (; n; n = n->next)
    if (ipa_zero(n->gw))
      return 1;

  return 0;
}

/* Replace device nexthops with nexthops to gw */
static struct nexthop *
fix_device_nexthops(struct ospf_proto *p, const struct nexthop *n, ip_addr gw)
{
  struct nexthop *root1 = NULL;
  struct nexthop *root2 = NULL;
  struct nexthop **nn1 = &root1;
  struct nexthop **nn2 = &root2;

  if (!p->ecmp)
    return new_nexthop(p, gw, n->iface, n->weight);

  /* This is a bit tricky. We cannot just copy the list and update n->gw,
     because the list should stay sorted, so we create two lists, one with new
     gateways and one with old ones, and then merge them. */

  for (; n; n = n->next)
  {
    struct nexthop *nn = new_nexthop(p, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight);

    if (ipa_zero(n->gw))
    {
      *nn1 = nn;
      nn1 = &(nn->next);
    }
    else
    {
      *nn2 = nn;
      nn2 = &(nn->next);
    }
  }

  return nexthop_merge(root1, root2, 1, 1, p->ecmp, p->nhpool);
}


/* 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(const orta *ep)
{
  return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0);
}

/* Whether the ext route has ASBR/next_hop marked as preferred. */
static inline int
orta_pref(const orta *nf)
{
  return !!(nf->options & ORTA_PREF);
}

/* Classify orta entries according to RFC 3101 2.5 (6e) priorities:
   Type-7 LSA with P-bit, Type-5 LSA, Type-7 LSA without P-bit */
static int
orta_prio(const orta *nf)
{
  /* RFC 3101 2.5 (6e) priorities */
  u32 opts = nf->options & (ORTA_NSSA | ORTA_PROP);

  /* A Type-7 LSA with the P-bit set */
  if (opts == (ORTA_NSSA | ORTA_PROP))
    return 2;

  /* A Type-5 LSA */
  if (opts == 0)
    return 1;

  return 0;
}

/* Whether the route is better according to RFC 3101 2.5 (6e):
   Prioritize Type-7 LSA with P-bit, then Type-5 LSA, then higher router ID */
static int
orta_prefer_lsa(const orta *new, const orta *old)
{
  int pn = orta_prio(new);
  int po = orta_prio(old);

  return (pn > po) || ((pn == po) && (new->en->lsa.rt > old->en->lsa.rt));
}

/*
 * Compare an existing routing table entry with a new one. Applicable for
 * intra-area routes, inter-area routes and router entries. Returns integer
 * <, = or > than 0 if the new orta is less, equal or more preferred than
 * the old orta.
 */
static int
orta_compare(const struct ospf_proto *p, const orta *new, const orta *old)
{
  int r;

  if (!old->type)
    return 1;

  /* Prefer intra-area to inter-area to externals */
  r = ((int) old->type) - ((int) new->type);
  if (r) return r;

  /* Prefer lowest type 1 metric */
  r = ((int) old->metric1) - ((int) new->metric1);
  if (r) return r;


  /* Rest is BIRD-specific */

  /* Area-wide routes should not mix next-hops from different areas.
     This generally should not happen unless there is some misconfiguration. */
  if (new->oa->areaid != old->oa->areaid)
    return (new->oa->areaid > old->oa->areaid) ? 1 : -1;

  /* Prefer routes for configured stubnets (!nhs) to regular routes to dummy
     vlink nexthops. We intentionally return -1 if both are stubnets or vlinks. */
  if (!old->nhs)
    return -1;
  if (!new->nhs)
    return 1;
  if (nh_is_vlink(new->nhs))
    return -1;
  if (nh_is_vlink(old->nhs))
    return 1;


  if (p->ecmp)
    return 0;

  /* Prefer routes with higher Router ID, just to be more deterministic */
  if (new->rid > old->rid)
    return 1;

  return -1;
}

/*
 * Compare ASBR routing table entry with a new one, used for precompute ASBRs
 * for AS external route selection (RFC 2328 16.4 (3)), Returns integer < or >
 * than 0 if the new ASBR is less or more preferred than the old ASBR.
 */
static int
orta_compare_asbr(const struct ospf_proto *p, const orta *new, const orta *old)
{
  int r;

  if (!old->type)
    return 1;

  if (!p->rfc1583)
  {
    r = epath_preferred(new) - epath_preferred(old);
    if (r) return r;
  }

  r = ((int) old->metric1) - ((int) new->metric1);
  if (r) return r;

  /* Larger area ID is preferred */
  if (new->oa->areaid > old->oa->areaid)
    return 1;

  /* There is just one ASBR of that RID per area, so tie is not possible */
  return -1;
}

/*
 * Compare a routing table entry with a new one, for AS external routes
 * (RFC 2328 16.4) and NSSA routes (RFC 3101 2.5), Returns integer <, = or >
 * than 0 if the new orta is less, equal or more preferred than the old orta.
 */
static int
orta_compare_ext(const struct ospf_proto *p, const orta *new, const orta *old)
{
  int r;

  if (!old->type)
    return 1;

  /* 16.4 (6a) - prefer routes with lower type */
  r = ((int) old->type) - ((int) new->type);
  if (r) return r;

  /* 16.4 (6b) - prefer routes with lower type 2 metric */
  if (new->type == RTS_OSPF_EXT2)
  {
    r = ((int) old->metric2) - ((int) new->metric2);
    if (r) return r;
  }

  /* 16.4 (6c) - if not RFC1583, prefer routes with preferred ASBR/next_hop */
  if (!p->rfc1583)
  {
    r = orta_pref(new) - orta_pref(old);
    if (r) return r;
  }

  /* 16.4 (6d) - prefer routes with lower type 1 metric */
  r = ((int) old->metric1) - ((int) new->metric1);
  if (r) return r;


  if (p->ecmp && p->merge_external)
    return 0;

  /*
   * RFC 3101 2.5 (6e) - prioritize Type-7 LSA with P-bit, then Type-5 LSA, then
   * LSA with higher router ID. Although this should apply just to functionally
   * equivalent LSAs (i.e. ones with the same non-zero forwarding address), we
   * use it also to disambiguate otherwise equally preferred nexthops.
   */
  if (orta_prefer_lsa(new, old))
    return 1;

  return -1;
}


static inline void
ort_replace(ort *o, const orta *new)
{
  memcpy(&o->n, new, sizeof(orta));
}

static void
ort_merge(struct ospf_proto *p, ort *o, const orta *new)
{
  orta *old = &o->n;

  if (old->nhs != new->nhs)
  {
    old->nhs = nexthop_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
			  p->ecmp, p->nhpool);
    old->nhs_reuse = 1;
  }

  if (old->rid < new->rid)
    old->rid = new->rid;
}

static void
ort_merge_ext(struct ospf_proto *p, ort *o, const orta *new)
{
  orta *old = &o->n;

  if (old->nhs != new->nhs)
  {
    old->nhs = nexthop_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
			  p->ecmp, p->nhpool);
    old->nhs_reuse = 1;
  }

  if (old->tag != new->tag)
    old->tag = 0;

  /*
   * Even with multipath, we store only one LSA in orta.en for the purpose of
   * NSSA/ext translation. Therefore, we apply procedures from RFC 3101 2.5 (6e)
   * to all chosen LSAs for given network, not just to functionally equivalent
   * ones (i.e. ones with the same non-zero forwarding address).
   */
  if (orta_prefer_lsa(new, old))
  {
    old->options = new->options;
    old->rid = new->rid;
    old->oa = new->oa;
    old->en = new->en;
  }
}



static inline void
ri_install_net(struct ospf_proto *p, net_addr *net, const orta *new)
{
  ort *old = fib_get(&p->rtf, net);
  int cmp = orta_compare(p, new, &old->n);

  if (cmp > 0)
    ort_replace(old, new);
  else if (cmp == 0)
    ort_merge(p, old, new);
}

static inline void
ri_install_rt(struct ospf_area *oa, u32 rid, const orta *new)
{
  net_addr_ip4 nrid = net_from_rid(rid);
  ort *old = fib_get(&oa->rtr, (net_addr *) &nrid);
  int cmp = orta_compare(oa->po, new, &old->n);

  if (cmp > 0)
    ort_replace(old, new);
  else if (cmp == 0)
    ort_merge(oa->po, old, new);
}

static inline void
ri_install_asbr(struct ospf_proto *p, u32 rid, const orta *new)
{
  net_addr_ip4 nrid = net_from_rid(rid);
  ort *old = fib_get(&p->backbone->rtr, (net_addr *) &nrid);

  if (orta_compare_asbr(p, new, &old->n) > 0)
    ort_replace(old, new);
}

static inline void
ri_install_ext(struct ospf_proto *p, net_addr *net, const orta *new)
{
  ort *old = fib_get(&p->rtf, net);
  int cmp = orta_compare_ext(p, new, &old->n);

  if (cmp > 0)
    ort_replace(old, new);
  else if (cmp == 0)
    ort_merge_ext(p, old, new);
}

static inline struct ospf_iface *
rt_pos_to_ifa(struct ospf_area *oa, int pos)
{
  struct ospf_iface *ifa;

  WALK_LIST(ifa, oa->po->iface_list)
    if (ifa->oa == oa && pos >= ifa->rt_pos_beg && pos < ifa->rt_pos_end)
      return ifa;

  return NULL;
}

static inline struct ospf_iface *
px_pos_to_ifa(struct ospf_area *oa, int pos)
{
  struct ospf_iface *ifa;

  WALK_LIST(ifa, oa->po->iface_list)
    if (ifa->oa == oa && pos >= ifa->px_pos_beg && pos < ifa->px_pos_end)
      return ifa;

  return NULL;
}

static inline struct ospf_iface *
rt_find_iface2(struct ospf_area *oa, uint data)
{
  /* We should handle it differently for unnumbered PTP links */
  struct ospf_iface *ifa;
  WALK_LIST(ifa, oa->po->iface_list)
    if ((ifa->oa == oa) && ifa->addr && (ospf_iface_get_data(ifa) == data))
      return ifa;

  return NULL;
}

static inline struct ospf_iface *
rt_find_iface3(struct ospf_area *oa, uint lif)
{
  struct ospf_iface *ifa;
  WALK_LIST(ifa, oa->po->iface_list)
    if ((ifa->oa == oa) && (ifa->iface_id == lif))
      return ifa;

  return NULL;
}

static struct ospf_iface *
rt_find_iface(struct ospf_area *oa, int pos, uint data, uint lif)
{
  /*
   * We can use both position based lookup (which is more reliable) and data/lif
   * based lookup (which works even during graceful restart). We will prefer the
   * first approach, but use the second one for GR-enabled instances.
   */

  if (oa->po->gr_mode != OSPF_GR_ABLE)
    return rt_pos_to_ifa(oa, pos);
  else
    return ospf_is_v2(oa->po) ? rt_find_iface2(oa, data) : rt_find_iface3(oa, lif);
}


static void
add_network(struct ospf_area *oa, net_addr *net, int metric, struct top_hash_entry *en, int pos)
{
  struct ospf_proto *p = oa->po;

  orta nf = {
    .type = RTS_OSPF,
    .options = 0,
    .metric1 = metric,
    .rid = en->lsa.rt,
    .oa = oa,
    .nhs = en->nhs
  };

  if (!ospf_valid_prefix(net))
  {
    log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
	p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
    return;
  }

  if (en == oa->rt)
  {
    /*
     * Local stub networks do not have proper iface in en->nhi (because they all
     * have common top_hash_entry en). We have to find iface responsible for
     * that stub network. Configured stubnets do not have any iface. They will
     * be removed in rt_sync().
     */

    struct ospf_iface *ifa;
    ifa = ospf_is_v2(p) ? rt_pos_to_ifa(oa, pos) : px_pos_to_ifa(oa, pos);
    nf.nhs = ifa ? new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL;
  }

  ri_install_net(p, net, &nf);
}



static inline void
spfa_process_rt(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
{
  struct ospf_lsa_rt *rt = act->lsa_body;
  struct ospf_lsa_rt_walk rtl;
  struct top_hash_entry *tmp;
  int i;

  if (rt->options & OPT_RT_V)
    oa->trcap = 1;

  /*
   * 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
   * spfa_process_prefixes(), we use information stored in LSA db.
   */
  if (((rt->options & OPT_RT_E) || (rt->options & OPT_RT_B))
      && (act->lsa.rt != p->router_id))
  {
    orta nf = {
      .type = RTS_OSPF,
      .options = rt->options,
      .metric1 = act->dist,
      .rid = act->lsa.rt,
      .oa = oa,
      .nhs = act->nhs
    };
    ri_install_rt(oa, act->lsa.rt, &nf);
  }

  /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
  if (ospf_is_v3(p) && (act != oa->rt) && !(rt->options & OPT_R))
    return;

  /* Now process Rt links */
  for (lsa_walk_rt_init(p, act, &rtl), i = 0; lsa_walk_rt(&rtl); i++)
  {
    tmp = NULL;

    switch (rtl.type)
    {
    case LSART_STUB:

      /* Should not happen, LSART_STUB is not defined in OSPFv3 */
      if (ospf_is_v3(p))
	break;

      /*
       * RFC 2328 in 16.1. (2a) says to handle stub networks in an
       * second phase after the SPF for an area is calculated. We get
       * the same result by handing them here because add_network()
       * will keep the best (not the first) found route.
       */
      net_addr_ip4 net =
	NET_ADDR_IP4(ip4_from_u32(rtl.id & rtl.data), u32_masklen(rtl.data));

      add_network(oa, (net_addr *) &net, act->dist + rtl.metric, act, i);
      break;

    case LSART_NET:
      tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
      break;

    case LSART_VLNK:
    case LSART_PTP:
      tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
      break;
    }

    add_cand(oa, tmp, act, act->dist + rtl.metric, i, rtl.data, rtl.lif, rtl.nif);
  }
}

static inline void
spfa_process_net(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
{
  struct ospf_lsa_net *ln = act->lsa_body;
  struct top_hash_entry *tmp;
  int i, cnt;

  if (ospf_is_v2(p))
  {
    net_addr_ip4 net =
      NET_ADDR_IP4(ip4_from_u32(act->lsa.id & ln->optx), u32_masklen(ln->optx));

    add_network(oa, (net_addr *) &net, act->dist, act, -1);
  }

  cnt = lsa_net_count(&act->lsa);
  for (i = 0; i < cnt; i++)
  {
    tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
    add_cand(oa, tmp, act, act->dist, -1, 0, 0, 0);
  }
}

static inline void
spfa_process_prefixes(struct ospf_proto *p, struct ospf_area *oa)
{
  struct top_hash_entry *en, *src;
  struct ospf_lsa_prefix *px;
  u32 *buf;
  int i;

  WALK_SLIST(en, p->lsal)
  {
    if (en->lsa_type != LSA_T_PREFIX)
      continue;

    if (en->domain != oa->areaid)
      continue;

    if (en->lsa.age == LSA_MAXAGE)
      continue;

    px = en->lsa_body;

    /* For router prefix-LSA, we would like to find the first router-LSA */
    if (px->ref_type == LSA_T_RT)
      src = ospf_hash_find_rt(p->gr, oa->areaid, px->ref_rt);
    else
      src = ospf_hash_find(p->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type);

    if (!src)
      continue;

    /* Reachable in SPF */
    if (src->color != INSPF)
      continue;

    if ((src->lsa_type != LSA_T_RT) && (src->lsa_type != LSA_T_NET))
      continue;

    buf = px->rest;
    for (i = 0; i < px->pxcount; i++)
    {
      net_addr net;
      u8 pxopts;
      u16 metric;

      buf = ospf3_get_prefix(buf, ospf_get_af(p), &net, &pxopts, &metric);

      if (pxopts & OPT_PX_NU)
	continue;

      /* Store the first global address to use it later as a vlink endpoint */
      if ((pxopts & OPT_PX_LA) && (net.type == NET_IP6) && ipa_zero(src->lb))
	src->lb = ipa_from_ip6(net6_prefix(&net));

      add_network(oa, &net, src->dist + metric, src, i);
    }
  }
}

/* RFC 2328 16.1. calculating shortest paths for an area */
static void
ospf_rt_spfa(struct ospf_area *oa)
{
  struct ospf_proto *p = oa->po;
  struct top_hash_entry *act;
  node *n;

  if (oa->rt == NULL)
    return;
  if (oa->rt->lsa.age == LSA_MAXAGE)
    return;

  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %R", oa->areaid);

  /* 16.1. (1) */
  init_list(&oa->cand);		/* Empty list of candidates */
  oa->trcap = 0;

  DBG("LSA db prepared, adding me into candidate list.\n");

  oa->rt->dist = 0;
  oa->rt->color = CANDIDATE;
  add_head(&oa->cand, &oa->rt->cn);
  DBG("RT LSA: rt: %R, id: %R, type: %u\n",
      oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa_type);

  while (!EMPTY_LIST(oa->cand))
  {
    n = HEAD(oa->cand);
    act = SKIP_BACK(struct top_hash_entry, cn, n);
    rem_node(n);

    DBG("Working on LSA: rt: %R, id: %R, type: %u\n",
	act->lsa.rt, act->lsa.id, act->lsa_type);

    act->color = INSPF;
    switch (act->lsa_type)
    {
    case LSA_T_RT:
      spfa_process_rt(p, oa, act);
      break;

    case LSA_T_NET:
      spfa_process_net(p, oa, act);
      break;

    default:
      log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, act->lsa_type);
    }
  }

  if (ospf_is_v3(p))
    spfa_process_prefixes(p, oa);
}

static int
link_back(struct ospf_area *oa, struct top_hash_entry *en,
	  struct top_hash_entry *par, uint lif, uint nif)
{
  struct ospf_proto *p = oa->po;
  struct ospf_lsa_rt_walk rtl;
  struct top_hash_entry *tmp;
  struct ospf_lsa_net *ln;
  u32 i, cnt;

  if (!en || !par) return 0;

  /* We should check whether there is a link back from en to par,
     this is used in SPF calc (RFC 2328 16.1. (2b)). According to RFC 2328
     note 23, we don't have to find the same link that is used for par
     to en, any link is enough. This we do for ptp links. For net-rt
     links, we have to find the same link to compute proper lb/lb_id,
     which may be later used as the next hop. */

  /* In OSPFv2, en->lb is set here. In OSPFv3, en->lb is just cleared here,
     it is set in process_prefixes() to any global address in the area */

  en->lb = IPA_NONE;
  en->lb_id = 0;

  switch (en->lsa_type)
  {
  case LSA_T_RT:
    lsa_walk_rt_init(p, en, &rtl);
    while (lsa_walk_rt(&rtl))
    {
      switch (rtl.type)
      {
      case LSART_STUB:
	break;

      case LSART_NET:
	tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
	if (tmp == par)
	{
	  /*
	   * Note that there may be multiple matching Rt-fields if router 'en'
	   * have multiple interfaces to net 'par'. Perhaps we should do ECMP.
	   */
	  if (ospf_is_v2(p))
	    en->lb = ipa_from_u32(rtl.data);
	  else
	    en->lb_id = rtl.lif;

	  return 1;
	}
	break;

      case LSART_VLNK:
      case LSART_PTP:
	/*
	 * For OSPFv2, not necessary the same link, see RFC 2328 [23].
	 * For OSPFv3, we verify that by comparing nif and lif fields.
	 */
	if (ospf_is_v3(p) && ((rtl.lif != nif) || (rtl.nif != lif)))
	  break;

	tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
	if (tmp == par)
	  return 1;
	break;
      }
    }
    break;

  case LSA_T_NET:
    ln = en->lsa_body;
    cnt = lsa_net_count(&en->lsa);
    for (i = 0; i < cnt; i++)
    {
      tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
      if (tmp == par)
	return 1;
    }
    break;

  default:
    log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, en->lsa_type);
  }
  return 0;
}


/* RFC 2328 16.2. calculating inter-area routes */
static void
ospf_rt_sum(struct ospf_area *oa)
{
  struct ospf_proto *p = oa->po;
  struct top_hash_entry *en;
  net_addr net;
  u32 dst_rid, metric, options;
  ort *abr;
  int type;
  u8 pxopts;

  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid);

  WALK_SLIST(en, p->lsal)
  {
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
      continue;

    if (en->domain != oa->areaid)
      continue;

    /* 16.2. (1a) */
    if (en->lsa.age == LSA_MAXAGE)
      continue;

    /* 16.2. (2) */
    if (en->lsa.rt == p->router_id)
      continue;

    /* 16.2. (3) is handled later in ospf_rt_abr() by resetting such rt entry */

    if (en->lsa_type == LSA_T_SUM_NET)
    {
      lsa_parse_sum_net(en, ospf_is_v2(p), ospf_get_af(p), &net, &pxopts, &metric);

      if (!ospf_valid_prefix(&net))
      {
	log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
	    p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
	continue;
      }

      if (pxopts & OPT_PX_NU)
	continue;

      /* RFC 4576 4 - do not use LSAs with DN-bit on PE-routers */
      if (p->vpn_pe && (pxopts & OPT_PX_DN))
	continue;

      options = 0;
      type = ORT_NET;
    }
    else /* LSA_T_SUM_RT */
    {
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);

      /* We don't want local router in ASBR routing table */
      if (dst_rid == p->router_id)
	continue;

      options |= ORTA_ASBR;
      type = ORT_ROUTER;
    }

    /* 16.2. (1b) */
    if (metric == LSINFINITY)
      continue;

    /* 16.2. (4) */
    net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
    abr = fib_find(&oa->rtr, (net_addr *) &nrid);
    if (!abr || !abr->n.type)
      continue;

    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,
      .options = options,
      .metric1 = abr->n.metric1 + metric,
      .rid = en->lsa.rt, /* ABR ID */
      .oa = oa,
      .nhs = abr->n.nhs
    };

    if (type == ORT_NET)
      ri_install_net(p, &net, &nf);
    else
      ri_install_rt(oa, dst_rid, &nf);
  }
}

/* RFC 2328 16.3. examining summary-LSAs in transit areas */
static void
ospf_rt_sum_tr(struct ospf_area *oa)
{
  struct ospf_proto *p = oa->po;
  struct ospf_area *bb = p->backbone;
  struct top_hash_entry *en;
  ort *re, *abr;
  u32 metric;

  if (!bb)
    return;

  WALK_SLIST(en, p->lsal)
  {
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
      continue;

    if (en->domain != oa->areaid)
      continue;

    /* 16.3 (1a) */
    if (en->lsa.age == LSA_MAXAGE)
      continue;

    /* 16.3 (2) */
    if (en->lsa.rt == p->router_id)
      continue;

    if (en->lsa_type == LSA_T_SUM_NET)
    {
      net_addr net;
      u8 pxopts;

      lsa_parse_sum_net(en, ospf_is_v2(p), ospf_get_af(p), &net, &pxopts, &metric);

      if (!ospf_valid_prefix(&net))
      {
	log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
	    p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
	continue;
      }

      if (pxopts & OPT_PX_NU)
	continue;

      /* RFC 4576 4 - do not use LSAs with DN-bit on PE-routers */
      if (p->vpn_pe && (pxopts & OPT_PX_DN))
	continue;

      re = fib_find(&p->rtf, &net);
    }
    else // en->lsa_type == LSA_T_SUM_RT
    {
      u32 dst_rid, options;

      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);

      net_addr_ip4 nrid = net_from_rid(dst_rid);
      re = fib_find(&bb->rtr, (net_addr *) &nrid);
    }

    /* 16.3 (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.3. (4) */
    net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
    abr = fib_find(&oa->rtr, (net_addr *) &nrid);
    if (!abr || !abr->n.type)
      continue;

    metric = abr->n.metric1 + metric; /* IAC */

    /* 16.3. (5) */
    if ((metric < re->n.metric1) ||
	((metric == re->n.metric1) && unresolved_vlink(re)))
    {
      /* 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.
	 Proper ECMP would merge nexthops here, but we do not do that.
	 We restrict nexthops to fit one area to simplify check
	 12.4.3 p4 in decide_sum_lsa() */

      re->n.metric1 = metric;
      re->n.voa = oa;
      re->n.nhs = abr->n.nhs;
    }
  }
}

/* Decide about originating or flushing summary LSAs for condensed area networks */
static int
decide_anet_lsa(struct ospf_area *oa, struct area_net *anet, struct ospf_area *anet_oa)
{
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
  if (!oa_is_ext(oa) && !oa->ac->summary)
    return 0;

  if (oa == anet_oa)
    return 0;

  /* Do not condense routing info when exporting from backbone to the transit area */
  if ((anet_oa == oa->po->backbone) && oa->trcap)
    return 0;

  return (anet->active && !anet->hidden);
}

/* Decide about originating or flushing summary LSAs (12.4.3) */
static int
decide_sum_lsa(struct ospf_area *oa, ort *nf, int dest)
{
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
  if (!oa_is_ext(oa) && !oa->ac->summary)
    return 0;

  /* Invalid field - no route */
  if (!nf->n.type)
    return 0;

  /* 12.4.3 p2 */
  if (nf->n.type > RTS_OSPF_IA)
    return 0;

  /* 12.4.3 p3 */
  if ((nf->n.oa->areaid == oa->areaid))
    return 0;

  /* 12.4.3 p4 */
  if (nf->n.voa && (nf->n.voa->areaid == oa->areaid))
    return 0;

  /* 12.4.3 p5 */
  if (nf->n.metric1 >= LSINFINITY)
    return 0;

  /* 12.4.3 p6 - AS boundary router */
  if (dest == ORT_ROUTER)
  {
    /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */
    /* 12.4.3 p1 */
    return oa_is_ext(oa) && (nf->n.options & ORTA_ASBR);
  }

  /* 12.4.3 p7 - inter-area route */
  if (nf->n.type == RTS_OSPF_IA)
  {
    /* Inter-area routes are not repropagated into the backbone */
    return (oa != oa->po->backbone);
  }

  /* 12.4.3 p8 - intra-area route */

  /* Do not condense routing info when exporting from backbone to the transit area */
  if ((nf->n.oa == oa->po->backbone) && oa->trcap)
    return 1;

  struct area_net *anet = (struct area_net *)
    fib_route(&nf->n.oa->net_fib, nf->fn.addr);

  /* Condensed area network found */
  if (anet)
    return 0;

  return 1;
}

/* RFC 2328 16.7. p1 - originate or flush summary LSAs */
static inline void
check_sum_net_lsa(struct ospf_proto *p, ort *nf)
{
  struct area_net *anet = NULL;
  struct ospf_area *anet_oa = NULL;

  if (nf->area_net)
  {
    /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */
    if (nf->fn.addr->pxlen == 0)
      return;

    /* Find that area network */
    WALK_LIST(anet_oa, p->area_list)
    {
      anet = fib_find(&anet_oa->net_fib, nf->fn.addr);
      if (anet)
	break;
    }
  }

  struct ospf_area *oa;
  WALK_LIST(oa, p->area_list)
  {
    if (anet && decide_anet_lsa(oa, anet, anet_oa))
      ospf_originate_sum_net_lsa(p, oa, nf, anet->metric);
    else if (decide_sum_lsa(oa, nf, ORT_NET))
      ospf_originate_sum_net_lsa(p, oa, nf, nf->n.metric1);
  }
}

static inline void
check_sum_rt_lsa(struct ospf_proto *p, ort *nf)
{
  u32 rid = rid_from_net(nf->fn.addr);

  struct ospf_area *oa;
  WALK_LIST(oa, p->area_list)
    if (decide_sum_lsa(oa, nf, ORT_ROUTER))
      ospf_originate_sum_rt_lsa(p, oa, rid, nf->n.metric1, nf->n.options);
}

static inline int
decide_nssa_lsa(struct ospf_proto *p, ort *nf, struct ospf_lsa_ext_local *rt)
{
  struct ospf_area *oa = nf->n.oa;
  struct top_hash_entry *en = nf->n.en;

  if (!rt_is_nssa(nf) || !oa->translate)
    return 0;

  /* Condensed area network found */
  if (fib_route(&oa->enet_fib, nf->fn.addr))
    return 0;

  if (!en || (en->lsa_type != LSA_T_NSSA))
    return 0;

  /* We do not store needed data in struct orta, we have to parse the LSA */
  lsa_parse_ext(en, ospf_is_v2(p), ospf_get_af(p), rt);

  if (rt->pxopts & OPT_PX_NU)
    return 0;

  if (!rt->propagate || ipa_zero(rt->fwaddr))
    return 0;

  return 1;
}

/* RFC 3101 3.2 - translating Type-7 LSAs into Type-5 LSAs */
static inline void
check_nssa_lsa(struct ospf_proto *p, ort *nf)
{
  struct area_net *anet = NULL;
  struct ospf_area *oa = NULL;
  struct ospf_lsa_ext_local rt;

  /* Do not translate LSA if there is already the external LSA from route export */
  if (nf->external_rte)
    return;

  if (nf->area_net)
  {
    /* Find that area network */
    WALK_LIST(oa, p->area_list)
    {
      anet = fib_find(&oa->enet_fib, nf->fn.addr);
      if (anet)
	break;
    }
  }

  /* RFC 3101 3.2 (3) - originate the aggregated address range */
  if (anet && anet->active && !anet->hidden && oa->translate)
    ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, anet->metric,
			   (anet->metric & LSA_EXT3_EBIT), IPA_NONE, anet->tag, 0, 0);

  /* RFC 3101 3.2 (2) - originate the same network */
  else if (decide_nssa_lsa(p, nf, &rt))
    ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, rt.metric, rt.ebit, rt.fwaddr, rt.tag, 0, 0);
}

/* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
static void
ospf_check_vlinks(struct ospf_proto *p)
{
  struct ospf_iface *ifa;
  WALK_LIST(ifa, p->iface_list)
  {
    if (ifa->type == OSPF_IT_VLINK)
    {
      struct top_hash_entry *tmp;
      tmp = ospf_hash_find_rt(p->gr, ifa->voa->areaid, ifa->vid);

      if (tmp && (tmp->color == INSPF) && ipa_nonzero(tmp->lb) && tmp->nhs)
      {
	struct ospf_iface *nhi = ospf_iface_find(p, tmp->nhs->iface);

	if ((ifa->state != OSPF_IS_PTP)
	    || (ifa->vifa != nhi)
	    || !ipa_equal(ifa->vip, tmp->lb))
	{
	  OSPF_TRACE(D_EVENTS, "Vlink peer %R found", ifa->vid);
	  ospf_iface_sm(ifa, ISM_DOWN);
	  ifa->vifa = nhi;
	  ifa->addr = nhi->addr;
	  ifa->cost = tmp->dist;
	  ifa->vip = tmp->lb;
	  ospf_iface_sm(ifa, ISM_UP);
	}
	else if ((ifa->state == OSPF_IS_PTP) && (ifa->cost != tmp->dist))
	{
	  ifa->cost = tmp->dist;

	  /* RFC 2328 12.4 Event 8 - vlink state change */
	  ospf_notify_rt_lsa(ifa->oa);
	}
      }
      else
      {
	if (ifa->state > OSPF_IS_DOWN)
	{
	  OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", ifa->vid);
	  ospf_iface_sm(ifa, ISM_DOWN);
	}
      }
    }
  }
}


/* Miscellaneous route processing that needs to be done by ABRs */
static void
ospf_rt_abr1(struct ospf_proto *p)
{
  struct area_net *anet;
  ort *default_nf;
  net_addr default_net;

  /* RFC 2328 G.3 - incomplete resolution of virtual next hops - routers */
  FIB_WALK(&p->backbone->rtr, ort, nf)
  {
    if (nf->n.type && unresolved_vlink(nf))
      reset_ri(nf);
  }
  FIB_WALK_END;


  FIB_WALK(&p->rtf, ort, nf)
  {
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
    if (nf->n.type && unresolved_vlink(nf))
      reset_ri(nf);


    /* Compute condensed area networks */
    if (nf->n.type == RTS_OSPF)
    {
      anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.addr);
      if (anet)
      {
	if (!anet->active)
	{
	  anet->active = 1;

	  /* Get a RT entry and mark it to know that it is an area network */
	  ort *nfi = fib_get(&p->rtf, anet->fn.addr);
	  nfi->area_net = 1;

	  /* 16.2. (3) */
	  if (nfi->n.type == RTS_OSPF_IA)
	    reset_ri(nfi);
	}

	if (anet->metric < nf->n.metric1)
	  anet->metric = nf->n.metric1;
      }
    }
  }
  FIB_WALK_END;


  if (ospf_is_ip4(p))
    net_fill_ip4(&default_net, IP4_NONE, 0);
  else
    net_fill_ip6(&default_net, IP6_NONE, 0);

  default_nf = fib_get(&p->rtf, &default_net);
  default_nf->area_net = 1;

  struct ospf_area *oa;
  WALK_LIST(oa, p->area_list)
  {

    /* 12.4.3.1. - originate or flush default route for stub/NSSA areas */
    if (oa_is_stub(oa) || (oa_is_nssa(oa) && !oa->ac->summary))
      ospf_originate_sum_net_lsa(p, oa, default_nf, oa->ac->default_cost);

    /*
     * Originate type-7 default route for NSSA areas
     *
     * Because type-7 default LSAs are originated by ABRs, they do not
     * collide with other type-7 LSAs (as ABRs generate type-5 LSAs
     * for both external route export or external-NSSA translation),
     * so we use 0 for the src arg.
     */

    if (oa_is_nssa(oa) && oa->ac->default_nssa)
      ospf_originate_ext_lsa(p, oa, default_nf, LSA_M_RTCALC, oa->ac->default_cost,
			     (oa->ac->default_cost & LSA_EXT3_EBIT), IPA_NONE, 0, 0, 0);

    /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */
    if (oa_is_ext(oa))
    {
      FIB_WALK(&oa->rtr, ort, nf)
      {
	if (nf->n.options & ORTA_ASBR)
	  ri_install_asbr(p, rid_from_net(nf->fn.addr), &nf->n);
      }
      FIB_WALK_END;
    }
  }


  /* Originate or flush ASBR summary LSAs */
  FIB_WALK(&p->backbone->rtr, ort, nf)
  {
    check_sum_rt_lsa(p, nf);
  }
  FIB_WALK_END;


  /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
  ospf_check_vlinks(p);
}


static void
translator_timer_hook(timer *timer)
{
  struct ospf_area *oa = timer->data;

  if (oa->translate != TRANS_WAIT)
    return;

  oa->translate = TRANS_OFF;
  ospf_schedule_rtcalc(oa->po);
}

static void
ospf_rt_abr2(struct ospf_proto *p)
{
  struct ospf_area *oa;
  struct top_hash_entry *en;

  /* RFC 3101 3.1 - type-7 translator election */
  struct ospf_area *bb = p->backbone;
  WALK_LIST(oa, p->area_list)
    if (oa_is_nssa(oa))
    {
      int translate = 1;

      if (oa->ac->translator)
	goto decided;

      FIB_WALK(&oa->rtr, ort, nf)
      {
	if (!nf->n.type || !(nf->n.options & ORTA_ABR))
	  continue;

	ort *nf2 = fib_find(&bb->rtr, nf->fn.addr);
	if (!nf2 || !nf2->n.type || !(nf2->n.options & ORTA_ABR))
	  continue;

	en = ospf_hash_find_rt(p->gr, oa->areaid, nf->n.rid);
	if (!en || (en->color != INSPF))
	  continue;

	struct ospf_lsa_rt *rt = en->lsa_body;
	/* There is better candidate - Nt-bit or higher Router ID */
	if ((rt->options & OPT_RT_NT) || (p->router_id < nf->n.rid))
	{
	  translate = 0;
	  goto decided;
	}
      }
      FIB_WALK_END;

    decided:
      if (translate && (oa->translate != TRANS_ON))
      {
	if (oa->translate == TRANS_WAIT)
	  tm_stop(oa->translator_timer);

	oa->translate = TRANS_ON;
      }

      if (!translate && (oa->translate == TRANS_ON))
      {
	if (oa->translator_timer == NULL)
	  oa->translator_timer = tm_new_init(p->p.pool, translator_timer_hook, oa, 0, 0);

	/* Schedule the end of translation */
	tm_start(oa->translator_timer, oa->ac->transint S);
	oa->translate = TRANS_WAIT;
      }
    }


  /* Compute condensed external networks */
  FIB_WALK(&p->rtf, ort, nf)
  {
    if (rt_is_nssa(nf) && (nf->n.options & ORTA_PROP))
    {
      struct area_net *anet = fib_route(&nf->n.oa->enet_fib, nf->fn.addr);

      if (anet)
      {
	if (!anet->active)
	{
	  anet->active = 1;

	  /* Get a RT entry and mark it to know that it is an area network */
	  ort *nf2 = fib_get(&p->rtf, anet->fn.addr);
	  nf2->area_net = 1;
	}

	u32 metric = (nf->n.type == RTS_OSPF_EXT1) ?
	  nf->n.metric1 : ((nf->n.metric2 + 1) | LSA_EXT3_EBIT);

	if (anet->metric < metric)
	  anet->metric = metric;
      }
    }
  }
  FIB_WALK_END;


  FIB_WALK(&p->rtf, ort, nf)
  {
    check_sum_net_lsa(p, nf);
    check_nssa_lsa(p, nf);
  }
  FIB_WALK_END;
}


/* Like fib_route(), but ignores dummy rt entries */
static void *
ospf_fib_route_ip4(struct fib *f, ip4_addr a, int len)
{
  net_addr_ip4 net = NET_ADDR_IP4(a, len);
  ort *nf;

loop:
  nf = fib_find(f, (net_addr *) &net);
  if (nf && nf->n.type)
    return nf;

  if (net.pxlen > 0)
  {
    net.pxlen--;
    ip4_clrbit(&net.prefix, net.pxlen);
    goto loop;
  }

  return NULL;
}

static void *
ospf_fib_route_ip6(struct fib *f, ip6_addr a, int len)
{
  net_addr_ip6 net = NET_ADDR_IP6(a, len);
  ort *nf;

loop:
  nf = fib_find(f, (net_addr *) &net);
  if (nf && nf->n.type)
    return nf;

  if (net.pxlen > 0)
  {
    net.pxlen--;
    ip6_clrbit(&net.prefix, net.pxlen);
    goto loop;
  }

  return NULL;
}

static void *
ospf_fib_route(struct fib *f, ip_addr a)
{
  if (f->addr_type == NET_IP4)
    return ospf_fib_route_ip4(f, ipa_to_ip4(a), IP4_MAX_PREFIX_LENGTH);
  else
    return ospf_fib_route_ip6(f, ipa_to_ip6(a), IP6_MAX_PREFIX_LENGTH);
}


/* RFC 2328 16.4. calculating external routes */
static void
ospf_ext_spf(struct ospf_proto *p)
{
  struct top_hash_entry *en;
  struct ospf_lsa_ext_local rt;
  ort *nf1, *nf2;
  u32 br_metric;
  struct ospf_area *atmp;

  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");

  WALK_SLIST(en, p->lsal)
  {
    orta nfa = {};

    /* 16.4. (1) */
    if ((en->lsa_type != LSA_T_EXT) && (en->lsa_type != LSA_T_NSSA))
      continue;

    if (en->lsa.age == LSA_MAXAGE)
      continue;

    /* 16.4. (2) */
    if (en->lsa.rt == p->router_id)
      continue;

    DBG("%s: Working on LSA. ID: %R, RT: %R, Type: %u\n",
	p->p.name, en->lsa.id, en->lsa.rt, en->lsa_type);

    lsa_parse_ext(en, ospf_is_v2(p), ospf_get_af(p), &rt);

    if (!ospf_valid_prefix(&rt.net))
    {
      log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
	  p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
      continue;
    }

    if (rt.metric == LSINFINITY)
      continue;

    if (rt.pxopts & OPT_PX_NU)
      continue;

    /* RFC 4576 4 - do not use LSAs with DN-bit on PE-routers */
    if (p->vpn_pe && rt.downwards)
      continue;

    /* 16.4. (3) */
    /* If there are more areas, we already precomputed preferred ASBR
       entries in ospf_rt_abr1() and stored them in the backbone
       table. For NSSA, we examine the area to which the LSA is assigned */
    if (en->lsa_type == LSA_T_EXT)
      atmp = ospf_main_area(p);
    else /* NSSA */
      atmp = ospf_find_area(p, en->domain);

    if (!atmp)
      continue;			/* Should not happen */

    net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
    nf1 = fib_find(&atmp->rtr, (net_addr *) &nrid);

    if (!nf1 || !nf1->n.type)
      continue;			/* No AS boundary router found */

    if (!(nf1->n.options & ORTA_ASBR))
      continue;			/* It is not ASBR */

    /* 16.4. (3) NSSA - special rule for default routes */
    /* ABR should use default only if P-bit is set and summaries are active */
    if ((en->lsa_type == LSA_T_NSSA) && (rt.net.pxlen == 0) &&
	(p->areano > 1) && !(rt.propagate && atmp->ac->summary))
      continue;

    if (!rt.fbit)
    {
      nf2 = nf1;
      nfa.nhs = nf1->n.nhs;
      br_metric = nf1->n.metric1;
    }
    else
    {
      nf2 = ospf_fib_route(&p->rtf, rt.fwaddr);
      if (!nf2)
	continue;

      if (en->lsa_type == LSA_T_EXT)
      {
	/* For ext routes, we accept intra-area or inter-area routes */
	if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA))
	  continue;
      }
      else /* NSSA */
      {
	/* For NSSA routes, we accept just intra-area in the same area */
	if ((nf2->n.type != RTS_OSPF) || (nf2->n.oa != atmp))
	  continue;
      }

      /* Next-hop is a part of a configured stubnet */
      if (!nf2->n.nhs)
	continue;

      nfa.nhs = nf2->n.nhs;
      br_metric = nf2->n.metric1;

      /* Replace device nexthops with nexthops to forwarding address from LSA */
      if (has_device_nexthops(nfa.nhs))
      {
	nfa.nhs = fix_device_nexthops(p, nfa.nhs, rt.fwaddr);
	nfa.nhs_reuse = 1;
      }
    }

    if (rt.ebit)
    {
      nfa.type = RTS_OSPF_EXT2;
      nfa.metric1 = br_metric;
      nfa.metric2 = rt.metric;
    }
    else
    {
      nfa.type = RTS_OSPF_EXT1;
      nfa.metric1 = br_metric + rt.metric;
      nfa.metric2 = 0;
    }

    /* 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;
    if (en->lsa_type == LSA_T_NSSA)
    {
      nfa.options |= ORTA_NSSA;
      if (rt.propagate)
	nfa.options |= ORTA_PROP;
    }

    nfa.tag = rt.tag;
    nfa.rid = en->lsa.rt;
    nfa.oa = atmp; /* undefined in RFC 2328 */
    nfa.en = en; /* store LSA for later (NSSA processing) */

    ri_install_ext(p, &rt.net, &nfa);
  }
}

/* Cleanup of routing tables and data */
void
ospf_rt_reset(struct ospf_proto *p)
{
  struct ospf_area *oa;
  struct top_hash_entry *en;

  /* Reset old routing table */
  FIB_WALK(&p->rtf, ort, ri)
  {
    ri->area_net = 0;
    ri->keep = 0;
    reset_ri(ri);
  }
  FIB_WALK_END;

  /* Reset SPF data in LSA db */
  WALK_SLIST(en, p->lsal)
  {
    en->color = OUTSPF;
    en->dist = LSINFINITY;
    en->nhs = NULL;
    en->lb = IPA_NONE;

    if (en->mode == LSA_M_RTCALC)
      en->mode = LSA_M_RTCALC_STALE;
  }

  WALK_LIST(oa, p->area_list)
  {
    /* Reset ASBR routing tables */
    FIB_WALK(&oa->rtr, ort, ri)
    {
      reset_ri(ri);
    }
    FIB_WALK_END;

    /* Reset condensed area networks */
    if (p->areano > 1)
    {
      FIB_WALK(&oa->net_fib, struct area_net, anet)
      {
	anet->active = 0;
	anet->metric = 0;
      }
      FIB_WALK_END;

      FIB_WALK(&oa->enet_fib, struct area_net, anet)
      {
	anet->active = 0;
	anet->metric = 0;
      }
      FIB_WALK_END;
    }
  }
}

/**
 * ospf_rt_spf - calculate internal routes
 * @p: OSPF protocol instance
 *
 * 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 ospf_proto *p)
{
  struct ospf_area *oa;

  if (p->areano == 0)
    return;

  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");

  /* 16. (1) */
  ospf_rt_reset(p);

  /* 16. (2) */
  WALK_LIST(oa, p->area_list)
    ospf_rt_spfa(oa);

  /* 16. (3) */
  ospf_rt_sum(ospf_main_area(p));

  /* 16. (4) */
  WALK_LIST(oa, p->area_list)
    if (oa->trcap && (oa->areaid != 0))
      ospf_rt_sum_tr(oa);

  if (p->areano > 1)
    ospf_rt_abr1(p);

  /* 16. (5) */
  ospf_ext_spf(p);

  if (p->areano > 1)
    ospf_rt_abr2(p);

  rt_sync(p);
  lp_flush(p->nhpool);

  p->calcrt = 0;
}


static inline int
inherit_nexthops(struct nexthop *pn)
{
  /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
  return pn && (ipa_nonzero(pn->gw) || !pn->iface);
}

static inline ip_addr
link_lsa_lladdr(struct ospf_proto *p, struct top_hash_entry *en)
{
  struct ospf_lsa_link *link_lsa = en->lsa_body;
  ip6_addr ll = link_lsa->lladdr;

  if (ip6_zero(ll))
    return IPA_NONE;

  return ospf_is_ip4(p) ? ipa_from_ip4(ospf3_6to4(ll)) : ipa_from_ip6(ll);
}

static struct nexthop *
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
	      struct top_hash_entry *par, int pos, uint data, uint lif, uint nif)
{
  struct ospf_proto *p = oa->po;
  struct nexthop *pn = par->nhs;
  struct top_hash_entry *link = NULL;
  struct ospf_iface *ifa = NULL;
  ip_addr nh = IPA_NONE;
  u32 rid = en->lsa.rt;

  /* 16.1.1. The next hop calculation */
  DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
      en->lsa.id, en->lsa.rt, en->lsa_type);

  /* Usually, we inherit parent nexthops */
  if (inherit_nexthops(pn))
    return pn;

  /*
   * There are three cases:
   * 1) en is a local network (and par is root)
   * 2) en is a ptp or ptmp neighbor (and par is root)
   * 3) en is a bcast or nbma neighbor (and par is local network)
   */

  /* The first case - local network */
  if ((en->lsa_type == LSA_T_NET) && (par == oa->rt))
  {
    ifa = rt_find_iface(oa, pos, data, lif);
    if (!ifa)
      return NULL;

    if (ospf_is_v3(p) && (ifa->iface_id != lif))
      log(L_WARN "%s: Inconsistent interface ID %u/%u", p->p.name, ifa->iface_id, lif);

    return new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight);
  }

  /* The second case - ptp or ptmp neighbor */
  if ((en->lsa_type == LSA_T_RT) && (par == oa->rt))
  {
    ifa = rt_find_iface(oa, pos, data, lif);
    if (!ifa)
      return NULL;

    if (ospf_is_v3(p) && (ifa->iface_id != lif))
      log(L_WARN "%s: Inconsistent interface ID %u/%u", p->p.name, ifa->iface_id, lif);

    if (ifa->type == OSPF_IT_VLINK)
      return new_nexthop(p, IPA_NONE, NULL, 0);

    /* FIXME: On physical PtP links we may skip next-hop altogether */

    if (ospf_is_v2(p) || ospf_is_ip6(p))
    {
      /*
       * In this case, next-hop is a source address from neighbor's packets.
       * That is necessary for OSPFv2 and practical for OSPFv3 (as it works even
       * if neighbor uses LinkLSASuppression), but does not work with OSPFv3-AF
       * on IPv4 topology, where src is IPv6 but next-hop should be IPv4.
       */
      struct ospf_neighbor *m = find_neigh(ifa, rid);
      if (!m || (m->state != NEIGHBOR_FULL))
	return NULL;

      nh = m->ip;
    }
    else
    {
      /*
       * Next-hop is taken from lladdr field of Link-LSA, based on Neighbor
       * Iface ID (nif) field in our Router-LSA, which is just nbr->iface_id.
       */
      link = ospf_hash_find(p->gr, ifa->iface_id, nif, rid, LSA_T_LINK);
      if (!link)
	return NULL;

      nh = link_lsa_lladdr(p, link);
      if (ipa_zero(nh))
	return NULL;
    }

    struct nexthop *nhs = new_nexthop(p, nh, ifa->iface, ifa->ecmp_weight);

    if (ifa->addr->flags & IA_HOST)
      nhs->flags = RNF_ONLINK;

    return nhs;
  }

  /* 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 (!pn)
      goto bad;

    if (ospf_is_v2(p))
    {
      /*
       * 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;

      return new_nexthop(p, en->lb, pn->iface, pn->weight);
    }
    else /* OSPFv3 */
    {
      /*
       * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
       * is computed in link_back().
       */
      link = ospf_hash_find(p->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK);
      if (!link)
	return NULL;

      nh = link_lsa_lladdr(p, link);
      if (ipa_zero(nh))
	return NULL;

      return new_nexthop(p, nh, pn->iface, pn->weight);
    }
  }

 bad:
  /* Probably bug or some race condition, we log it */
  log(L_ERR "%s: Unexpected case in next hop calculation", p->p.name);
  return NULL;
}


/* Add LSA into list of candidates in Dijkstra's algorithm */
static void
add_cand(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par,
	 u32 dist, int pos, uint data, uint lif, uint nif)
{
  struct ospf_proto *p = oa->po;
  node *prev, *n;
  int added = 0;
  struct top_hash_entry *act;

  /* 16.1. (2b) */
  if (en == NULL)
    return;
  if (en->lsa.age == LSA_MAXAGE)
    return;

  if (ospf_is_v3(p) && (oa->options & OPT_V6) && (en->lsa_type == LSA_T_RT))
  {
    /* In OSPFv3 IPv6 unicast, check V6 flag */
    struct ospf_lsa_rt *rt = en->lsa_body;
    if (!(rt->options & OPT_V6))
      return;
  }

  /* 16.1. (2c) */
  if (en->color == INSPF)
    return;

  /* 16.1. (2d), also checks that dist < LSINFINITY */
  if (dist > en->dist)
    return;

  /* We should check whether there is a reverse link from en to par, */
  if (!link_back(oa, en, par, lif, nif))
    return;

  struct nexthop *nhs = calc_next_hop(oa, en, par, pos, data, lif, nif);
  if (!nhs)
  {
    log(L_WARN "%s: Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
	p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
    return;
  }

  /* If en->dist > 0, we know that en->color == CANDIDATE and en->nhs is defined. */
  if ((dist == en->dist) && !nh_is_vlink(en->nhs))
  {
    /*
     * For multipath, we should merge nexthops. We merge regular nexthops only.
     * Dummy vlink nexthops are less preferred and handled as a special case.
     *
     * During merging, new nexthops (nhs) can be reused if they are not
     * inherited from the parent (i.e. they are allocated in calc_next_hop()).
     * Current nexthops (en->nhs) can be reused if they weren't inherited in
     * previous steps (that is stored in nhs_reuse, i.e. created by merging or
     * allocated in calc_next_hop()).
     *
     * Generally, a node first inherits shared nexthops from its parent and
     * later possibly gets reusable (private) copy during merging. This is more
     * or less same for both top_hash_entry nodes and orta nodes.
     *
     * Note that when a child inherits a private nexthop from its parent, it
     * should make the nexthop shared for both parent and child, while we only
     * update nhs_reuse for the child node. This makes nhs_reuse field for the
     * parent technically incorrect, but it is not a problem as parent's nhs
     * will not be modified (and nhs_reuse examined) afterwards.
     */

    /* Keep old ones */
    if (!p->ecmp || nh_is_vlink(nhs) || (nhs == en->nhs))
      return;

    /* Merge old and new */
    int new_reuse = (par->nhs != nhs);
    en->nhs = nexthop_merge(en->nhs, nhs, en->nhs_reuse, new_reuse, p->ecmp, p->nhpool);
    en->nhs_reuse = 1;
    return;
  }

  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
      en->lsa.rt, en->lsa.id, en->lsa_type);

  if (en->color == CANDIDATE)
  {				/* We found a shorter path */
    rem_node(&en->cn);
  }
  en->nhs = nhs;
  en->dist = dist;
  en->color = CANDIDATE;
  en->nhs_reuse = (par->nhs != nhs);

  prev = NULL;

  if (EMPTY_LIST(oa->cand))
  {
    add_head(&oa->cand, &en->cn);
  }
  else
  {
    WALK_LIST(n, oa->cand)
    {
      act = SKIP_BACK(struct top_hash_entry, cn, n);
      if ((act->dist > dist) ||
	  ((act->dist == dist) && (act->lsa_type == LSA_T_RT)))
      {
	if (prev == NULL)
	  add_head(&oa->cand, &en->cn);
	else
	  insert_node(&en->cn, prev);
	added = 1;
	break;
      }
      prev = n;
    }

    if (!added)
    {
      add_tail(&oa->cand, &en->cn);
    }
  }
}

static inline int
ort_changed(ort *nf, rta *nr)
{
  rta *or = nf->old_rta;
  return !or ||
    (nf->n.metric1 != nf->old_metric1) || (nf->n.metric2 != nf->old_metric2) ||
    (nf->n.tag != nf->old_tag) || (nf->n.rid != nf->old_rid) ||
    (nr->source != or->source) || (nr->dest != or->dest) ||
    !nexthop_same(&(nr->nh), &(or->nh));
}

static void
rt_sync(struct ospf_proto *p)
{
  struct top_hash_entry *en;
  struct fib_iterator fit;
  struct fib *fib = &p->rtf;
  struct ospf_area *oa;

  /* This is used for forced reload of routes */
  int reload = (p->calcrt == 2);

  OSPF_TRACE(D_EVENTS, "Starting routing table synchronization");

  DBG("Now syncing my rt table with nest's\n");
  FIB_ITERATE_INIT(&fit, fib);
again1:
  FIB_ITERATE_START(fib, &fit, ort, nf)
  {
    /* Sanity check of next-hop addresses, failure should not happen */
    if (nf->n.type)
    {
      struct nexthop *nh;
      for (nh = nf->n.nhs; nh; nh = nh->next)
	if (ipa_nonzero(nh->gw))
	{
	  neighbor *nbr = neigh_find(&p->p, nh->gw, nh->iface,
				    (nh->flags & RNF_ONLINK) ? NEF_ONLINK : 0);
	  if (!nbr || (nbr->scope == SCOPE_HOST))
	    { reset_ri(nf); break; }
	}
    }

    /* Remove configured stubnets but keep the entries */
    if (nf->n.type && !nf->n.nhs)
    {
      reset_ri(nf);
      nf->keep = 1;
    }

    if (nf->n.type) /* Add the route */
    {
      rta a0 = {
	.source = nf->n.type,
	.dest = RTD_UNICAST,
	.nh = *(nf->n.nhs),
      };

      if (reload || ort_changed(nf, &a0))
      {
	nf->old_metric1 = nf->n.metric1;
	nf->old_metric2 = nf->n.metric2;
	nf->old_tag = nf->n.tag;
	nf->old_rid = nf->n.rid;

	struct {
	  ea_list l;
	  eattr a[5];
	} eattrs;

	eattrs.l = (ea_list) {};

	eattrs.a[eattrs.l.count++] =
	  EA_LITERAL_EMBEDDED(&ea_gen_preference, 0, p->p.main_channel->preference);

	eattrs.a[eattrs.l.count++] =
	  EA_LITERAL_EMBEDDED(&ea_ospf_metric1, 0, nf->n.metric1);

	if (nf->n.type == RTS_OSPF_EXT2)
	  eattrs.a[eattrs.l.count++] =
	    EA_LITERAL_EMBEDDED(&ea_ospf_metric2, 0, nf->n.metric2);

	if ((nf->n.type == RTS_OSPF_EXT1) || (nf->n.type == RTS_OSPF_EXT2))
	  eattrs.a[eattrs.l.count++] =
	    EA_LITERAL_EMBEDDED(&ea_ospf_tag, 0, nf->n.tag);

	eattrs.a[eattrs.l.count++] =
	  EA_LITERAL_EMBEDDED(&ea_ospf_router_id, 0, nf->n.rid);

	a0.eattrs = &eattrs.l;

	rta *a = rta_lookup(&a0);
	rte *e = rte_get_temp(a, p->p.main_source);

	rta_free(nf->old_rta);
	nf->old_rta = rta_clone(a);

	DBG("Mod rte type %d - %N via %I on iface %s, met %d\n",
	    a0.source, nf->fn.addr, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
	rte_update(&p->p, nf->fn.addr, e);
      }
    }
    else if (nf->old_rta)
    {
      /* Remove the route */
      rta_free(nf->old_rta);
      nf->old_rta = NULL;

      rte_update(&p->p, nf->fn.addr, NULL);
    }

    /* Remove unused rt entry, some special entries are persistent */
    if (!nf->n.type && !nf->external_rte && !nf->area_net && !nf->keep)
    {
      if (nf->lsa_id)
	idm_free(&p->idm, nf->lsa_id);

      FIB_ITERATE_PUT(&fit);
      fib_delete(fib, nf);
      goto again1;
    }
  }
  FIB_ITERATE_END;


  WALK_LIST(oa, p->area_list)
  {
    /* Cleanup ASBR hash tables */
    FIB_ITERATE_INIT(&fit, &oa->rtr);
again2:
    FIB_ITERATE_START(&oa->rtr, &fit, ort, nf)
    {
      if (!nf->n.type)
      {
	FIB_ITERATE_PUT(&fit);
	fib_delete(&oa->rtr, nf);
	goto again2;
      }
    }
    FIB_ITERATE_END;
  }

  /* Cleanup stale LSAs */
  WALK_SLIST(en, p->lsal)
    if (en->mode == LSA_M_RTCALC_STALE)
      ospf_flush_lsa(p, en);
}


/* RFC 3623 2.2 - checking for graceful restart termination conditions */
void
ospf_update_gr_recovery(struct ospf_proto *p)
{
  struct top_hash_entry *rt, *net, *nbr;
  struct ospf_lsa_rt_walk rtl;
  struct ospf_neighbor *n;
  struct ospf_iface *ifa;
  struct ospf_area *oa;
  const char *err_dsc = NULL;
  uint i, j, missing = 0, err_val = 0;

  /*
   * We check here for three cases:
   * RFC 3623 2.2 (1) - success when all adjacencies are established
   * RFC 3623 2.2 (2) - failure when inconsistent LSA was received
   * RFC 3623 2.2 (3) - grace period timeout
   *
   * It is handled by processing pre-restart local router-LSA and adjacent
   * network-LSAs, checking neighbor association for referenced routers (1)
   * and checking back links from their router-LSAs (2).
   *
   * TODO: Use timer for grace period timeout. We avoided that as function
   * ospf_stop_gr_recovery() called from ospf_disp() makes ending of graceful
   * restart uninterrupted by other events.
   */

  #define CONTINUE { missing++; continue; }

  if (current_time() > p->gr_timeout)
    goto timeout;

  WALK_LIST(oa, p->area_list)
  {
    /* Get the router-LSA */
    rt = oa->rt;
    if (!rt || (rt->lsa.age == LSA_MAXAGE))
      CONTINUE;

    for (lsa_walk_rt_init(p, rt, &rtl), i = 0; lsa_walk_rt(&rtl); i++)
    {
      if (rtl.type == LSART_STUB)
	continue;

      ifa = rt_find_iface(oa, i, rtl.data, rtl.lif);
      if (!ifa)
	DROP("inconsistent interface", ospf_is_v2(p) ? rtl.data : rtl.lif);

      switch (rtl.type)
      {
      case LSART_NET:
	/* Find the network-LSA */
	net = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
	if (!net)
	  CONTINUE;

	if (!link_back(oa, net, rt, rtl.lif, rtl.nif))
	  DROP("Inconsistent network-LSA", net->lsa.id);

	if (ifa->state == OSPF_IS_DR)
	{
	  /* Find all neighbors from the network-LSA */
	  struct ospf_lsa_net *net_body = net->lsa_body;
	  uint cnt = lsa_net_count(&net->lsa);
	  for (j = 0; j < cnt; i++)
	  {
	    n = find_neigh(ifa, net_body->routers[j]);
	    if (!n || (n->state != NEIGHBOR_FULL))
	      CONTINUE;

	    if (!n->got_my_rt_lsa)
	      DROP("not received my router-LSA", n->rid);

	    nbr = ospf_hash_find_rt(p->gr, oa->areaid, n->rid);
	    if (!link_back(oa, nbr, net, 0, 0))
	      DROP("inconsistent router-LSA", n->rid);
	  }
	}
	else
	{
	  /* Find the DR (by IP for OSPFv2) */
	  n = ospf_is_v2(p) ?
	    find_neigh_by_ip(ifa, ipa_from_u32(rtl.id)) :
	    find_neigh(ifa, rtl.id);
	  if (!n || (n->state != NEIGHBOR_FULL))
	    CONTINUE;

	  if (!n->got_my_rt_lsa)
	    DROP("not received my router-LSA", n->rid);
	}
	break;

      case LSART_VLNK:
      case LSART_PTP:
	/* Find the PtP peer */
	n = find_neigh(ifa, rtl.id);
	if (!n || (n->state != NEIGHBOR_FULL))
	  CONTINUE;

	if (!n->got_my_rt_lsa)
	  DROP("not received my router-LSA", n->rid);

	nbr = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
	if (!link_back(oa, nbr, rt, rtl.lif, rtl.nif))
	  DROP("inconsistent router-LSA", rtl.id);
      }
    }
  }

  #undef CONTINUE

  if (missing)
    return;

  OSPF_TRACE(D_EVENTS, "Graceful restart finished");
  ospf_stop_gr_recovery(p);
  return;

drop:
  log(L_INFO "%s: Graceful restart ended - %s (%R)", p->p.name, err_dsc, err_val);
  ospf_stop_gr_recovery(p);
  return;

timeout:
  log(L_INFO "%s: Graceful restart ended - grace period expired", p->p.name);
  ospf_stop_gr_recovery(p);
  return;
}