Internet on FIRE

/*

 *        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(list * l, struct top_hash_entry *en, 

                     struct top_hash_entry *par, u32 dist,

                     struct ospf_area *oa, int i);

static void rt_sync(struct ospf_proto *p);

static inline void reset_ri(ort *ort)

{

  bzero(&ort->n, sizeof(orta));

}

void

ospf_rt_initort(struct fib_node *fn)

{

  ort *ri = (ort *) fn;

  reset_ri(ri);

  ri->old_rta = NULL;

  ri->fn.flags = 0;

}

static inline int

nh_is_vlink(struct mpnh *nhs)

{

  return !nhs->iface;

}

static inline int

unresolved_vlink(ort *ort)

{

  return ort->n.nhs && nh_is_vlink(ort->n.nhs);

}

static inline struct mpnh *

new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, unsigned char weight)

{

  struct mpnh *nh = lp_alloc(p->nhpool, sizeof(struct mpnh));

  nh->gw = gw;

  nh->iface = iface;

  nh->next = NULL;

  nh->weight = weight;

  return nh;

}

static inline struct mpnh *

copy_nexthop(struct ospf_proto *p, const struct mpnh *src)

{

  struct mpnh *nh = lp_alloc(p->nhpool, sizeof(struct mpnh));

  nh->gw = src->gw;

  nh->iface = src->iface;

  nh->next = NULL;

  nh->weight = src->weight;

  return nh;

}

/* Compare nexthops during merge.

   We need to maintain nhs sorted to eliminate duplicities */

static int

cmp_nhs(struct mpnh *s1, struct mpnh *s2)

{

  int r;

  if (!s1)

    return 1;

  if (!s2)

    return -1;

  r = ((int) s2->weight) - ((int) s1->weight);

  if (r)

    return r;

  r = ipa_compare(s1->gw, s2->gw);

  if (r)

    return r;

  return ((int) s1->iface->index) - ((int) s2->iface->index);

}

static struct mpnh *

merge_nexthops(struct ospf_proto *p, struct mpnh *s1, struct mpnh *s2, int r1, int r2)

{

  struct mpnh *root = NULL;

  struct mpnh **n = &root;

  int count = p->ecmp;

  /*

   * r1, r2 signalize whether we can reuse nexthops from s1, s2.

   * New nexthops (s2, new) can be reused if they are not inherited

   * from the parent (i.e. it is allocated in calc_next_hop()).

   * Current nexthops (s1, 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 allocalted in calc_next_hop()).

   *

   * Generally, a node first inherits shared nexthops from its

   * parent and later possibly gets reusable copy during merging.

   */

  while ((s1 || s2) && count--)

  {

    int cmp = cmp_nhs(s1, s2);

    if (cmp < 0)

    {

      *n = r1 ? s1 : copy_nexthop(p, s1);

      s1 = s1->next;

    }

    else if (cmp > 0)

    {

      *n = r2 ? s2 : copy_nexthop(p, s2);

      s2 = s2->next;

    }

    else

    {

      *n = r1 ? s1 : (r2 ? s2 : copy_nexthop(p, s1));

      s1 = s1->next;

      s2 = s2->next;

    }

    n = &((*n)->next);

  }

  *n = NULL;

  return root;

}

/* Returns true if there are device nexthops in n */

static inline int

has_device_nexthops(const struct mpnh *n)

{

  for (; n; n = n->next)

    if (ipa_zero(n->gw))

      return 1;

  return 0;

}

/* Replace device nexthops with nexthops to gw */

static struct mpnh *

fix_device_nexthops(struct ospf_proto *p, const struct mpnh *n, ip_addr gw)

{

  struct mpnh *root1 = NULL;

  struct mpnh *root2 = NULL;

  struct mpnh **nn1 = &root1;

  struct mpnh **nn2 = &root2;

  /* 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 mpnh *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 merge_nexthops(p, root1, root2, 1, 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(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 3103 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 == RTS_DUMMY)

    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 == RTS_DUMMY)

    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 3103 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 == RTS_DUMMY)

    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 = merge_nexthops(p, old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse);

    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 = merge_nexthops(p, old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse);

    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, ip_addr prefix, int pxlen, const orta *new)

{

  ort *old = (ort *) fib_get(&p->rtf, &prefix, pxlen);

  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)

{

  ip_addr addr = ipa_from_rid(rid);

  ort *old = (ort *) fib_get(&oa->rtr, &addr, MAX_PREFIX_LENGTH);

  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, ip_addr *addr, const orta *new)

{

  ort *old = (ort *) fib_get(&p->backbone->rtr, addr, MAX_PREFIX_LENGTH);

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

    ort_replace(old, new);

}

static inline void

ri_install_ext(struct ospf_proto *p, ip_addr prefix, int pxlen, const orta *new)

{

  ort *old = (ort *) fib_get(&p->rtf, &prefix, pxlen);

  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 void

add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en, int pos)

{

  struct ospf_proto *p = oa->po;

  orta nf = {

    .type = RTS_OSPF,

    .options = 0,

    .metric1 = metric,

    .metric2 = LSINFINITY,

    .tag = 0,

    .rid = en->lsa.rt,

    .oa = oa,

    .nhs = en->nhs

  };

  if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)

  {

    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 does 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 does 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, px, pxlen, &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;

  ip_addr prefix;

  int pxlen, 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,

      .metric2 = LSINFINITY,

      .tag = 0,

      .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.

       */

      prefix = ipa_from_u32(rtl.id & rtl.data);

      pxlen = u32_masklen(rtl.data);

      add_network(oa, prefix, pxlen, 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->cand, tmp, act, act->dist + rtl.metric, oa, i);

  }

}

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;

  ip_addr prefix;

  int pxlen, i, cnt;

  if (ospf_is_v2(p))

  {

    prefix = ipa_from_u32(act->lsa.id & ln->optx);

    pxlen = u32_masklen(ln->optx);

    add_network(oa, prefix, pxlen, 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->cand, tmp, act, act->dist, oa, -1);

  }

}

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;

  ip_addr pxa;

  int pxlen;

  u8 pxopts;

  u16 metric;

  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++)

      {

        buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &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) && ipa_zero(src->lb))

          src->lb = pxa;

        add_network(oa, pxa, pxlen, 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)

{

  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 addres 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)

        {

          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:

        /* Not necessary the same link, see RFC 2328 [23] */

        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;

  ip_addr ip, abrip;

  u32 dst_rid, metric, options;

  ort *abr;

  int pxlen = -1, type = -1;

  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), &ip, &pxlen, &pxopts, &metric);

      if (pxopts & OPT_PX_NU)

        continue;

      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)

      {

        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;

      }

      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) */

    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.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,

      .metric2 = LSINFINITY,

      .tag = 0,

      .rid = en->lsa.rt, /* ABR ID */

      .oa = oa,

      .nhs = abr->n.nhs

    };

    if (type == ORT_NET)

      ri_install_net(p, ip, pxlen, &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;

  ip_addr ip, abrip;

  u32 dst_rid, metric, options;

  int pxlen;

  u8 pxopts;

  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)

    {

      lsa_parse_sum_net(en, ospf_is_v2(p), &ip, &pxlen, &pxopts, &metric);

      if (pxopts & OPT_PX_NU)

        continue;

      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)

      {

        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;

      }

      re = fib_find(&p->rtf, &ip, pxlen);

    }

    else // en->lsa_type == LSA_T_SUM_RT

    {

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

      ip = ipa_from_rid(dst_rid);

      re = fib_find(&bb->rtr, &ip, MAX_PREFIX_LENGTH);

    }

    /* 16.3 (1b) */ 

    if (metric == LSINFINITY) 

      continue;