[thirdparty/bird.git] / proto / ospf / rt.c

/*
 *	BIRD -- OSPF
 *
 *	(c) 2000 Ondrej Filip <feela@network.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#include "ospf.h"

#define LOCAL_DEBUG

void
init_infib(struct fib_node *fn)
{
  struct infib *f=(struct infib *)fn;

  f->metric=LSINFINITY;
  f->en=NULL;
}

void
init_efib(struct fib_node *fn)
{
  struct extfib *f=(struct extfib *)fn;

  f->metric=LSINFINITY;
  f->metric2=LSINFINITY;
  f->nh=ipa_from_u32(0);
  f->nhi=NULL;
}

void
ospf_rt_spfa(struct ospf_area *oa)
{
  struct top_hash_entry *en;
  u32 i,*rts;
  struct ospf_lsa_rt *rt;
  struct ospf_lsa_rt_link *rtl,*rr;
  struct fib *in=&oa->infib;
  struct infib *nf;
  struct fib_iterator fit;
  bird_clock_t delta;
  int age=0,flush=0;
  struct proto *p=&oa->po->proto;
  struct proto_ospf *po=oa->po;
  ip_addr ip;
  struct ospf_lsa_net *ln;

  debug("%s: Starting routing table calculation for area %I\n",p->name,
    oa->areaid);

  if(oa->rt==NULL) return;

  WALK_SLIST(SNODE en, oa->lsal)
  {
    en->color=OUTSPF;
    en->dist=LSINFINITY;
    en->nhi=NULL;
  }

  FIB_WALK(in,nftmp)
  {
    nf=(struct infib *)nftmp;
    nf->metric=LSINFINITY;
  }
  FIB_WALK_END;

  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: %I, id: %I, type: %u\n",oa->rt->lsa.rt,oa->rt->lsa.id,oa->rt->lsa.type);

  while(!EMPTY_LIST(oa->cand))
  {
    struct top_hash_entry *act,*tmp;
    node *n;
    u16 met;

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

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

    act->color=INSPF;
    switch(act->lsa.type)
    {
      case LSA_T_RT:
        rt=(struct ospf_lsa_rt *)act->lsa_body;
	if((rt->VEB)&(1>>LSA_RT_V)) oa->trcap=1;
	rr=(struct ospf_lsa_rt_link *)(rt+1);
	DBG("  Number of links: %u\n",rt->links);
	for(i=0;i<rt->links;i++)
	{
	  tmp=NULL;
	  rtl=(rr+i);
	  DBG("     Working on link: %I (type: %u)  ",rtl->id,rtl->type);
	  switch(rtl->type)
	  {
            case LSART_STUB:
	     DBG("\n");
	     ip=ipa_from_u32(rtl->id);
	     nf=fib_get(in,&ip, ipa_mklen(ipa_from_u32(rtl->data)));
	     if(nf->metric>(met=act->dist+rtl->metric))
	     {
	       nf->metric=met;
	       nf->en=act;
	     }
	     break;
	    case LSART_VLNK:
	      DBG("Ignoring\n");
	      continue;
	      break;
	    case LSART_NET:
	      tmp=ospf_hash_find(oa->gr,rtl->id,rtl->id,LSA_T_NET);
	      if(tmp==NULL) DBG("Fuck!\n");
	      else DBG("Found. :-)\n");
	      break;
	    case LSART_PTP:
	      tmp=ospf_hash_find(oa->gr,rtl->id,rtl->id,LSA_T_RT);
	      DBG("PTP searched.\n");
	      break;
	    default:
	      log("Unknown link type in router lsa.");
	      break;
	  }
	  add_cand(&oa->cand,tmp,act,act->dist+rtl->metric,oa);
	}
        break;
      case LSA_T_NET:	/* FIXME Add to fib */
        ln=act->lsa_body;
	ip=ipa_and(ipa_from_u32(act->lsa.id),ln->netmask);
        nf=fib_get(in,&ip, ipa_mklen(ln->netmask));
	if(nf->metric>act->dist)
	{
	  nf->metric=act->dist;
	  nf->en=act;
	}

	rts=(u32 *)(ln+1);
	for(i=0;i<(act->lsa.length-sizeof(struct ospf_lsa_header)-
	  sizeof(struct ospf_lsa_net))/sizeof(u32);i++)
	{
	  DBG("     Working on router %I ",*(rts+i));
	  tmp=ospf_hash_find(oa->gr, *(rts+i), *(rts+i), LSA_T_RT);
	  if(tmp!=NULL) DBG("Found :-)\n");
	  else DBG("Fuck!\n");
          add_cand(&oa->cand,tmp,act,act->dist,oa);
	}
        break;
    }
  }
  /* Now sync our fib with nest's */
  DBG("\nNow syncing my rt table with nest's\n\n");
  FIB_ITERATE_INIT(&fit,in);
again:
  FIB_ITERATE_START(in,&fit,nftmp)
  {
    nf=(struct infib *)nftmp;
    if(nf->metric==LSINFINITY) 
    {
      net *ne;
      struct top_hash_entry *en=nf->en;
      ln=en->lsa_body;
  
      ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
      DBG("Deleting rt entry %I\n     (IP: %I, GW: %I, Iface: %s)\n",
        nf->fn.prefix,ip,en->nh,en->nhi->name);
      rte_update(p->table, ne, p, NULL);

      /* Now delete my fib */
      FIB_ITERATE_PUT(&fit, nftmp);
      fib_delete(in, nftmp);
      goto again;
    }
    else
    {
      /* Update routing table */
      if(nf->en->nhi==NULL)
      {
        struct top_hash_entry *en=nf->en;
        struct ospf_neighbor *neigh;
        neighbor *nn;

        if((neigh=find_neigh_noifa(po,en->lsa.rt))==NULL)
	{
	  goto skip;
	}
        nn=neigh_find(p,&neigh->ip,0);
        DBG("     Next hop calculated: %I\n", nn->addr);
        en->nh=nn->addr;
        en->nhi=nn->iface;
      }

      {
        net *ne;
        rta a0;
        rte *e;
	struct top_hash_entry *en=nf->en;
        ln=en->lsa_body;
  
        bzero(&a0, sizeof(a0));
  
        a0.proto=p;
        a0.source=RTS_OSPF;
        a0.scope=SCOPE_UNIVERSE;	/* What's this good for? */
        a0.cast=RTC_UNICAST;
        a0.dest=RTD_ROUTER;
        a0.flags=0;
        a0.aflags=0;
        a0.iface=en->nhi;
        a0.gw=en->nh;
        a0.from=en->nh;		/* FIXME Just a test */
        ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
        e=rte_get_temp(&a0);
        e->u.ospf.metric1=nf->metric;
        e->u.ospf.metric2=LSINFINITY;
        e->u.ospf.tag=0;			/* FIXME Some config? */
        e->pflags = 0;
        e->net=ne;
	e->pref = p->preference;
        DBG("Modifying rt entry %I\n     (IP: %I, GW: %I, Iface: %s)\n",
          nf->fn.prefix,ip,en->nh,en->nhi->name);
        rte_update(p->table, ne, p, e);
      }
    }

  }
skip:
  FIB_ITERATE_END(nftmp);
  ospf_ext_spfa(po);
}

void
ospf_ext_spfa(struct proto_ospf *po)	/* FIXME looking into inter-area */
{
  struct top_hash_entry *en,*etmp,*absr;
  struct fib *ef=&po->efib;
  struct extfib *nf;
  struct fib_iterator fit;
  struct ospf_area *oa=NULL,*atmp,*absroa;
  struct proto *p=&po->proto;
  struct ospf_lsa_ext *le;
  struct ospf_lsa_ext_tos *lt;
  int mlen;
  ip_addr ip,nnh;
  struct iface *nnhi=NULL;
  u16 met,met2;
  u32 tag;
  neighbor *nn;

  debug("%s: Starting routing table calculation for external routes\n",
    p->name);

  FIB_WALK(ef,nftmp)
  {
    nf=(struct extfib *)nftmp;
    nf->metric=LSINFINITY;
    nf->metric2=LSINFINITY;
  }
  FIB_WALK_END;

  WALK_LIST(oa,po->area_list)
  {
    if(!oa->stub) break;
  }

  if(oa==NULL) return;

  WALK_SLIST(en,oa->lsal)
  {
    if(en->lsa.type!=LSA_T_EXT) continue;
    if(en->lsa.age==LSA_MAXAGE) continue;
    if(en->lsa.rt==p->cf->global->router_id) continue;

    le=en->lsa_body;
    lt=(struct ospf_lsa_ext_tos *)(le+1);

    if(lt->metric==LSINFINITY) continue;
    ip=ipa_and(ipa_from_u32(en->lsa.id),le->netmask);
    mlen=ipa_mklen(le->netmask);
    if((mlen<0)||(mlen>32))
    {
      log("%s: Invalid mask in LSA. ID: %I, RT: %I, Type: %u, Mask %I",
        p->name,en->lsa.id,en->lsa.rt,en->lsa.type,le->netmask);
      continue;
    }

    nf=NULL;

    WALK_LIST(atmp,po->area_list)
    {
      if((nf=fib_find(&atmp->infib,&ip, mlen))!=NULL) break;
    }

    if(nf!=NULL) continue;	/* Some intra area path exists */
    
    absr=NULL;
    absroa=NULL;
    nnhi=NULL;

    met=0;met2=0;tag=0;

    WALK_LIST(atmp,po->area_list)
    {
      if((etmp=ospf_hash_find(atmp->gr,en->lsa.rt,en->lsa.rt,LSA_T_RT))!=NULL)
      {
        if((absr==NULL) || (absr->dist>etmp->dist) ||
          ((etmp->dist==absr->dist) && (absroa->areaid<atmp->areaid)))
        {
          absr=etmp;
          absroa=atmp;
	  break;
        }
      }
    }
    if((absr==NULL)||(absr->dist==LSINFINITY)) continue;

    if(ipa_compare(lt->fwaddr,ipa_from_u32(0))==0)
    {
      if(lt->etos>0)
      {
        met=absr->dist;
        met2=lt->metric;
      }
      else
      {
        met=absr->dist+lt->metric;
	met2=LSINFINITY;
      }
      tag=lt->tag;
    }
    else
    {
      nf=NULL;
      WALK_LIST(atmp,po->area_list)
      {
        if((nf=fib_route(&atmp->infib,lt->fwaddr,32))!=NULL)
	{
	  break;
	}
      }
      if(nf==NULL) continue;
      if(lt->etos>0)
      {
        met=nf->metric;
        met2=lt->metric;
      }
      else
      {
        met=nf->metric+lt->metric;
	met2=LSINFINITY;
      }
      tag=lt->tag;

      if((nn=neigh_find(p,&lt->fwaddr,0))!=NULL)
      {
        nnh=nn->addr;
        nnhi=nn->iface;
      }
    }

    nf=fib_get(ef,&ip, mlen);
    if((nf->metric>met) || ((nf->metric==met)&&(nf->metric2>met2)))
    {
      nf->metric=met;
      nf->metric2=met2;
      nf->tag=tag;
      if(nnhi!=NULL)
      {
        nf->nh=nnh;
        nf->nhi=nnhi;
      }
      else
      {
        if(absr->nhi==NULL)
        {
          struct ospf_neighbor *neigh;

          if((neigh=find_neigh_noifa(po,absr->lsa.rt))==NULL)
	  {
	     continue;
	  }
          nn=neigh_find(p,&neigh->ip,0);
          DBG("     Next hop calculated: %I\n", nn->addr);
          nf->nh=nn->addr;
          nf->nhi=nn->iface;
        }
        else
        {
          nf->nh=absr->nh;
	  nf->nhi=absr->nhi;
        }
      }
    }
  }

  DBG("\nNow syncing my rt table with nest's\n\n");
  FIB_ITERATE_INIT(&fit,ef);
noch:
  FIB_ITERATE_START(ef,&fit,nftmp)
  {
    nf=(struct extfib *)nftmp;
    if(nf->metric==LSINFINITY) 
    {
      net *ne;
  
      ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
      DBG("Deleting rt entry %I\n     (IP: %I, GW: %I)\n",
        nf->fn.prefix,ip,nf->nh);
      rte_update(p->table, ne, p, NULL);

      /* Now delete my fib */
      FIB_ITERATE_PUT(&fit, nftmp);
      fib_delete(ef, nftmp);
      goto noch;
    }
    else
    {
      net *ne;
      rta a0;
      rte *e;
  
      bzero(&a0, sizeof(a0));
  
      a0.proto=p;
      a0.source=RTS_OSPF_EXT;
      a0.scope=SCOPE_UNIVERSE;	/* What's this good for? */
      a0.cast=RTC_UNICAST;
      a0.dest=RTD_ROUTER;
      a0.flags=0;
      a0.aflags=0;
      a0.iface=nf->nhi;
      a0.gw=nf->nh;
      a0.from=nf->nh;		/* FIXME Just a test */
      ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
      e=rte_get_temp(&a0);
      e->u.ospf.metric1=nf->metric;
      e->u.ospf.metric2=nf->metric2;
      e->u.ospf.tag=nf->tag;
      e->pflags = 0;
      e->net=ne;
      e->pref = p->preference;
      DBG("Modifying rt entry %I\n     (IP: %I, GW: %I)\n",
        nf->fn.prefix,ip,nf->nh);
      rte_update(p->table, ne, p, e);
    }
  }
let:
  FIB_ITERATE_END(nftmp);
}

void
add_cand(list *l, struct top_hash_entry *en, struct top_hash_entry *par, 
  u16 dist, struct ospf_area *oa)
{
  node *prev,*n;
  int flag=0,added=0;
  struct top_hash_entry *act;
  struct proto *p=&oa->po->proto;

  if(en==NULL) return;
  if(en->lsa.age==LSA_MAXAGE) return;
  /* FIXME Does it have link back? Test it! */
  if(en->color==INSPF) return;

  if(dist>=en->dist) return;
  /*
   * FIXME The line above is not a bug, but we don't support
   * multiple next hops. I'll start as soon as nest will
   */
  DBG("     Adding candidate: rt: %I, id: %I, type: %u\n",en->lsa.rt,en->lsa.id,en->lsa.type);

  en->nhi=NULL;
  
  calc_next_hop(par,en,oa);

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

  en->dist=dist;
  en->color=CANDIDATE;

  prev=NULL;

  if(EMPTY_LIST(*l))
  {
    add_head(l,&en->cn);
  }
  else
  {
    WALK_LIST(n,*l)
    {
      act=SKIP_BACK(struct top_hash_entry, cn, n);
      if((act->dist>dist)||
        ((act->dist==dist)&&(act->lsa.type==LSA_T_NET)))
      {
        if(prev==NULL) add_head(l,&en->cn);
        else insert_node(&en->cn,prev);
	added=1;
        break;
      }
      prev=n;
    }

    if(!added)
    {
      add_tail(l,&en->cn);
    }
  }
  /* FIXME Some VLINK staff should be here */
}

void
calc_next_hop(struct top_hash_entry *par, struct top_hash_entry *en,
  struct ospf_area *oa)
{
  struct ospf_neighbor *neigh;
  struct proto *p=&oa->po->proto;
  struct proto_ospf *po=oa->po;
  DBG("     Next hop called\n");
  if(par==oa->rt) return;
  if(par->nhi==NULL)
  {
    neighbor *nn;
    DBG("     Next hop calculating for id: %I rt: %I type: %u\n",en->lsa.id,en->lsa.rt,en->lsa.type);
    if(par->lsa.type!=LSA_T_RT) return;
    if((neigh=find_neigh_noifa(po,par->lsa.rt))==NULL) return;
    nn=neigh_find(p,&neigh->ip,0);
    DBG("     Next hop calculated: %I\n", nn->addr);
    en->nh=nn->addr;
    en->nhi=nn->iface;
    return;
  }
  en->nh=par->nh;
  en->nhi=par->nhi;
  DBG("     Next hop calculated: %I\n", en->nh);
}
Commit	Line	Data
dfa9a53a OF	1	/*
	2	* BIRD -- OSPF
	3	*
	4	* (c) 2000 Ondrej Filip <feela@network.cz>
	5	*
	6	* Can be freely distributed and used under the terms of the GNU GPL.
	7	*/
	8
	9	#include "ospf.h"
	10
aa1e082c OF	11	#define LOCAL_DEBUG
aa1e082c OF	12
a92847e7	13	void
d345cda5	14	init_infib(struct fib_node *fn)
a92847e7	15	{
d345cda5	16	struct infib f=(struct infib )fn;
a92847e7	17
d345cda5 OF	18	f->metric=LSINFINITY;
d345cda5 OF	19	f->en=NULL;
a92847e7 OF	20	}
a92847e7 OF	21
aa1e082c OF	22	void
	23	init_efib(struct fib_node *fn)
	24	{
	25	struct extfib f=(struct extfib )fn;
	26
	27	f->metric=LSINFINITY;
	28	f->metric2=LSINFINITY;
	29	f->nh=ipa_from_u32(0);
	30	f->nhi=NULL;
	31	}
	32
dfa9a53a	33	void
a02c6c18	34	ospf_rt_spfa(struct ospf_area *oa)
dfa9a53a	35	{
d1660fd3	36	struct top_hash_entry *en;
dfa9a53a	37	u32 i,*rts;
2add26df	38	struct ospf_lsa_rt *rt;
85195f1a	39	struct ospf_lsa_rt_link rtl,rr;
d345cda5 OF	40	struct fib *in=&oa->infib;
d345cda5 OF	41	struct infib *nf;
aa1e082c	42	struct fib_iterator fit;
c45f48fb OF	43	bird_clock_t delta;
c45f48fb OF	44	int age=0,flush=0;
a02c6c18	45	struct proto *p=&oa->po->proto;
b57a45b8	46	struct proto_ospf *po=oa->po;
d345cda5	47	ip_addr ip;
d345cda5	48	struct ospf_lsa_net *ln;
dfa9a53a	49
3b8b1bd0 OF	50	debug("%s: Starting routing table calculation for area %I\n",p->name,
	51	oa->areaid);
	52
102e3e0e OF	53	if(oa->rt==NULL) return;
102e3e0e OF	54
d1660fd3	55	WALK_SLIST(SNODE en, oa->lsal)
dfa9a53a OF	56	{
	57	en->color=OUTSPF;
	58	en->dist=LSINFINITY;
b57a45b8	59	en->nhi=NULL;
dfa9a53a OF	60	}
dfa9a53a OF	61
d345cda5 OF	62	FIB_WALK(in,nftmp)
	63	{
	64	nf=(struct infib *)nftmp;
	65	nf->metric=LSINFINITY;
	66	}
	67	FIB_WALK_END;
	68
dfa9a53a OF	69	init_list(&oa->cand); /* Empty list of candidates */
	70	oa->trcap=0;
	71
85195f1a OF	72	DBG("LSA db prepared, adding me into candidate list.\n");
85195f1a OF	73
dfa9a53a OF	74	oa->rt->dist=0;
dfa9a53a OF	75	oa->rt->color=CANDIDATE;
85195f1a OF	76	add_head(&oa->cand, &oa->rt->cn);
85195f1a OF	77	DBG("RT LSA: rt: %I, id: %I, type: %u\n",oa->rt->lsa.rt,oa->rt->lsa.id,oa->rt->lsa.type);
dfa9a53a OF	78
	79	while(!EMPTY_LIST(oa->cand))
	80	{
	81	struct top_hash_entry act,tmp;
	82	node *n;
d345cda5	83	u16 met;
dfa9a53a OF	84
dfa9a53a OF	85	n=HEAD(oa->cand);
e80e9d0d	86	act=SKIP_BACK(struct top_hash_entry, cn, n);
dfa9a53a	87	rem_node(n);
dfa9a53a	88
85195f1a OF	89	DBG("Working on LSA: rt: %I, id: %I, type: %u\n",act->lsa.rt,act->lsa.id,act->lsa.type);
85195f1a OF	90
dfa9a53a OF	91	act->color=INSPF;
	92	switch(act->lsa.type)
	93	{
	94	case LSA_T_RT:
	95	rt=(struct ospf_lsa_rt *)act->lsa_body;
	96	if((rt->VEB)&(1>>LSA_RT_V)) oa->trcap=1;
85195f1a OF	97	rr=(struct ospf_lsa_rt_link *)(rt+1);
	98	DBG(" Number of links: %u\n",rt->links);
	99	for(i=0;i<rt->links;i++)
dfa9a53a OF	100	{
dfa9a53a OF	101	tmp=NULL;
85195f1a OF	102	rtl=(rr+i);
	103	DBG(" Working on link: %I (type: %u) ",rtl->id,rtl->type);
	104	switch(rtl->type)
dfa9a53a	105	{
fe95ab68	106	case LSART_STUB:
d345cda5 OF	107	DBG("\n");
	108	ip=ipa_from_u32(rtl->id);
	109	nf=fib_get(in,&ip, ipa_mklen(ipa_from_u32(rtl->data)));
	110	if(nf->metric>(met=act->dist+rtl->metric))
	111	{
	112	nf->metric=met;
	113	nf->en=act;
	114	}
	115	break;
dfa9a53a	116	case LSART_VLNK:
85195f1a	117	DBG("Ignoring\n");
dfa9a53a OF	118	continue;
	119	break;
	120	case LSART_NET:
85195f1a OF	121	tmp=ospf_hash_find(oa->gr,rtl->id,rtl->id,LSA_T_NET);
	122	if(tmp==NULL) DBG("Fuck!\n");
	123	else DBG("Found. :-)\n");
dfa9a53a	124	break;
fe95ab68	125	case LSART_PTP:
85195f1a OF	126	tmp=ospf_hash_find(oa->gr,rtl->id,rtl->id,LSA_T_RT);
85195f1a OF	127	DBG("PTP searched.\n");
dfa9a53a OF	128	break;
dfa9a53a OF	129	default:
df49d4e1	130	log("Unknown link type in router lsa.");
dfa9a53a OF	131	break;
dfa9a53a OF	132	}
a02c6c18	133	add_cand(&oa->cand,tmp,act,act->dist+rtl->metric,oa);
dfa9a53a OF	134	}
dfa9a53a OF	135	break;
d345cda5 OF	136	case LSA_T_NET: /* FIXME Add to fib */
	137	ln=act->lsa_body;
	138	ip=ipa_and(ipa_from_u32(act->lsa.id),ln->netmask);
	139	nf=fib_get(in,&ip, ipa_mklen(ln->netmask));
	140	if(nf->metric>act->dist)
	141	{
	142	nf->metric=act->dist;
	143	nf->en=act;
	144	}
	145
	146	rts=(u32 *)(ln+1);
dfa9a53a OF	147	for(i=0;i<(act->lsa.length-sizeof(struct ospf_lsa_header)-
	148	sizeof(struct ospf_lsa_net))/sizeof(u32);i++)
	149	{
85195f1a OF	150	DBG(" Working on router %I ",*(rts+i));
	151	tmp=ospf_hash_find(oa->gr, (rts+i), (rts+i), LSA_T_RT);
	152	if(tmp!=NULL) DBG("Found :-)\n");
	153	else DBG("Fuck!\n");
a02c6c18	154	add_cand(&oa->cand,tmp,act,act->dist,oa);
dfa9a53a OF	155	}
	156	break;
	157	}
d345cda5 OF	158	}
	159	/* Now sync our fib with nest's */
	160	DBG("\nNow syncing my rt table with nest's\n\n");
	161	FIB_ITERATE_INIT(&fit,in);
	162	again:
	163	FIB_ITERATE_START(in,&fit,nftmp)
	164	{
	165	nf=(struct infib *)nftmp;
	166	if(nf->metric==LSINFINITY)
c6c56264 OF	167	{
c6c56264 OF	168	net *ne;
d345cda5 OF	169	struct top_hash_entry *en=nf->en;
	170	ln=en->lsa_body;
	171
d345cda5 OF	172	ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
	173	DBG("Deleting rt entry %I\n (IP: %I, GW: %I, Iface: %s)\n",
	174	nf->fn.prefix,ip,en->nh,en->nhi->name);
	175	rte_update(p->table, ne, p, NULL);
	176
	177	/* Now delete my fib */
	178	FIB_ITERATE_PUT(&fit, nftmp);
	179	fib_delete(in, nftmp);
	180	goto again;
c6c56264	181	}
85195f1a OF	182	else
85195f1a OF	183	{
d345cda5	184	/* Update routing table */
b57a45b8 OF	185	if(nf->en->nhi==NULL)
	186	{
	187	struct top_hash_entry *en=nf->en;
	188	struct ospf_neighbor *neigh;
	189	neighbor *nn;
	190
	191	if((neigh=find_neigh_noifa(po,en->lsa.rt))==NULL)
	192	{
	193	goto skip;
	194	}
	195	nn=neigh_find(p,&neigh->ip,0);
	196	DBG(" Next hop calculated: %I\n", nn->addr);
	197	en->nh=nn->addr;
	198	en->nhi=nn->iface;
	199	}
	200
85195f1a	201	{
d345cda5 OF	202	net *ne;
	203	rta a0;
	204	rte *e;
	205	struct top_hash_entry *en=nf->en;
	206	ln=en->lsa_body;
	207
	208	bzero(&a0, sizeof(a0));
	209
	210	a0.proto=p;
	211	a0.source=RTS_OSPF;
	212	a0.scope=SCOPE_UNIVERSE; /* What's this good for? */
	213	a0.cast=RTC_UNICAST;
	214	a0.dest=RTD_ROUTER;
	215	a0.flags=0;
	216	a0.aflags=0;
	217	a0.iface=en->nhi;
	218	a0.gw=en->nh;
	219	a0.from=en->nh; /* FIXME Just a test */
	220	ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
	221	e=rte_get_temp(&a0);
	222	e->u.ospf.metric1=nf->metric;
0822995c	223	e->u.ospf.metric2=LSINFINITY;
d345cda5 OF	224	e->u.ospf.tag=0; /* FIXME Some config? */
	225	e->pflags = 0;
	226	e->net=ne;
916c8c0a	227	e->pref = p->preference;
d345cda5 OF	228	DBG("Modifying rt entry %I\n (IP: %I, GW: %I, Iface: %s)\n",
	229	nf->fn.prefix,ip,en->nh,en->nhi->name);
	230	rte_update(p->table, ne, p, e);
85195f1a OF	231	}
85195f1a OF	232	}
a92847e7	233
2add26df	234	}
b57a45b8	235	skip:
d345cda5	236	FIB_ITERATE_END(nftmp);
7e681ef3	237	ospf_ext_spfa(po);
fafe44b6 OF	238	}
	239
	240	void
aa1e082c	241	ospf_ext_spfa(struct proto_ospf po) / FIXME looking into inter-area */
fafe44b6	242	{
aa1e082c	243	struct top_hash_entry en,etmp,*absr;
7e681ef3	244	struct fib *ef=&po->efib;
aa1e082c	245	struct extfib *nf;
7e681ef3	246	struct fib_iterator fit;
aa1e082c OF	247	struct ospf_area oa=NULL,atmp,*absroa;
	248	struct proto *p=&po->proto;
	249	struct ospf_lsa_ext *le;
	250	struct ospf_lsa_ext_tos *lt;
	251	int mlen;
8fb0c2c2 OF	252	ip_addr ip,nnh;
8fb0c2c2 OF	253	struct iface *nnhi=NULL;
aa1e082c	254	u16 met,met2;
a7a3a0a3	255	u32 tag;
8fb0c2c2	256	neighbor *nn;
aa1e082c OF	257
	258	debug("%s: Starting routing table calculation for external routes\n",
	259	p->name);
	260
7e681ef3 OF	261	FIB_WALK(ef,nftmp)
	262	{
	263	nf=(struct extfib *)nftmp;
	264	nf->metric=LSINFINITY;
	265	nf->metric2=LSINFINITY;
	266	}
	267	FIB_WALK_END;
	268
aa1e082c OF	269	WALK_LIST(oa,po->area_list)
	270	{
	271	if(!oa->stub) break;
	272	}
	273
	274	if(oa==NULL) return;
	275
	276	WALK_SLIST(en,oa->lsal)
	277	{
	278	if(en->lsa.type!=LSA_T_EXT) continue;
	279	if(en->lsa.age==LSA_MAXAGE) continue;
	280	if(en->lsa.rt==p->cf->global->router_id) continue;
	281
	282	le=en->lsa_body;
	283	lt=(struct ospf_lsa_ext_tos *)(le+1);
	284
	285	if(lt->metric==LSINFINITY) continue;
	286	ip=ipa_and(ipa_from_u32(en->lsa.id),le->netmask);
	287	mlen=ipa_mklen(le->netmask);
508c36ab OF	288	if((mlen<0)\|\|(mlen>32))
508c36ab OF	289	{
df49d4e1	290	log("%s: Invalid mask in LSA. ID: %I, RT: %I, Type: %u, Mask %I",
0850ce22	291	p->name,en->lsa.id,en->lsa.rt,en->lsa.type,le->netmask);
4ee21789	292	continue;
508c36ab	293	}
aa1e082c OF	294
	295	nf=NULL;
	296
	297	WALK_LIST(atmp,po->area_list)
	298	{
7e681ef3	299	if((nf=fib_find(&atmp->infib,&ip, mlen))!=NULL) break;
aa1e082c	300	}
d345cda5	301
aa1e082c	302	if(nf!=NULL) continue; /* Some intra area path exists */
7e681ef3	303
aa1e082c OF	304	absr=NULL;
aa1e082c OF	305	absroa=NULL;
8fb0c2c2	306	nnhi=NULL;
aa1e082c	307
a7a3a0a3	308	met=0;met2=0;tag=0;
aa1e082c	309
508c36ab OF	310	WALK_LIST(atmp,po->area_list)
	311	{
	312	if((etmp=ospf_hash_find(atmp->gr,en->lsa.rt,en->lsa.rt,LSA_T_RT))!=NULL)
	313	{
	314	if((absr==NULL) \|\| (absr->dist>etmp->dist) \|\|
	315	((etmp->dist==absr->dist) && (absroa->areaid<atmp->areaid)))
	316	{
	317	absr=etmp;
	318	absroa=atmp;
	319	break;
	320	}
	321	}
	322	}
9a04d030	323	if((absr==NULL)\|\|(absr->dist==LSINFINITY)) continue;
508c36ab	324
31834faa	325	if(ipa_compare(lt->fwaddr,ipa_from_u32(0))==0)
aa1e082c	326	{
508c36ab OF	327	if(lt->etos>0)
	328	{
	329	met=absr->dist;
	330	met2=lt->metric;
	331	}
	332	else
	333	{
	334	met=absr->dist+lt->metric;
a7a3a0a3	335	met2=LSINFINITY;
508c36ab	336	}
a7a3a0a3	337	tag=lt->tag;
508c36ab OF	338	}
	339	else
	340	{
	341	nf=NULL;
aa1e082c OF	342	WALK_LIST(atmp,po->area_list)
aa1e082c OF	343	{
508c36ab	344	if((nf=fib_route(&atmp->infib,lt->fwaddr,32))!=NULL)
aa1e082c	345	{
508c36ab	346	break;
aa1e082c OF	347	}
aa1e082c OF	348	}
508c36ab	349	if(nf==NULL) continue;
aa1e082c OF	350	if(lt->etos>0)
aa1e082c OF	351	{
508c36ab	352	met=nf->metric;
aa1e082c OF	353	met2=lt->metric;
	354	}
	355	else
	356	{
508c36ab	357	met=nf->metric+lt->metric;
a7a3a0a3	358	met2=LSINFINITY;
aa1e082c	359	}
a7a3a0a3	360	tag=lt->tag;
8fb0c2c2 OF	361
	362	if((nn=neigh_find(p,&lt->fwaddr,0))!=NULL)
	363	{
	364	nnh=nn->addr;
	365	nnhi=nn->iface;
	366	}
aa1e082c	367	}
508c36ab	368
7e681ef3	369	nf=fib_get(ef,&ip, mlen);
aa1e082c OF	370	if((nf->metric>met) \|\| ((nf->metric==met)&&(nf->metric2>met2)))
	371	{
	372	nf->metric=met;
	373	nf->metric2=met2;
a7a3a0a3	374	nf->tag=tag;
8fb0c2c2	375	if(nnhi!=NULL)
aa1e082c	376	{
8fb0c2c2 OF	377	nf->nh=nnh;
8fb0c2c2 OF	378	nf->nhi=nnhi;
aa1e082c OF	379	}
	380	else
	381	{
8fb0c2c2 OF	382	if(absr->nhi==NULL)
	383	{
	384	struct ospf_neighbor *neigh;
	385
	386	if((neigh=find_neigh_noifa(po,absr->lsa.rt))==NULL)
	387	{
	388	continue;
	389	}
	390	nn=neigh_find(p,&neigh->ip,0);
	391	DBG(" Next hop calculated: %I\n", nn->addr);
	392	nf->nh=nn->addr;
	393	nf->nhi=nn->iface;
	394	}
	395	else
	396	{
	397	nf->nh=absr->nh;
	398	nf->nhi=absr->nhi;
	399	}
aa1e082c OF	400	}
	401	}
	402	}
	403
	404	DBG("\nNow syncing my rt table with nest's\n\n");
7e681ef3 OF	405	FIB_ITERATE_INIT(&fit,ef);
	406	noch:
	407	FIB_ITERATE_START(ef,&fit,nftmp)
aa1e082c	408	{
7e681ef3	409	nf=(struct extfib *)nftmp;
aa1e082c OF	410	if(nf->metric==LSINFINITY)
	411	{
	412	net *ne;
aa1e082c	413
aa1e082c	414	ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
7e681ef3 OF	415	DBG("Deleting rt entry %I\n (IP: %I, GW: %I)\n",
7e681ef3 OF	416	nf->fn.prefix,ip,nf->nh);
aa1e082c OF	417	rte_update(p->table, ne, p, NULL);
	418
	419	/* Now delete my fib */
7e681ef3 OF	420	FIB_ITERATE_PUT(&fit, nftmp);
	421	fib_delete(ef, nftmp);
	422	goto noch;
aa1e082c OF	423	}
	424	else
	425	{
	426	net *ne;
	427	rta a0;
	428	rte *e;
	429
	430	bzero(&a0, sizeof(a0));
	431
	432	a0.proto=p;
	433	a0.source=RTS_OSPF_EXT;
	434	a0.scope=SCOPE_UNIVERSE; /* What's this good for? */
	435	a0.cast=RTC_UNICAST;
	436	a0.dest=RTD_ROUTER;
	437	a0.flags=0;
	438	a0.aflags=0;
	439	a0.iface=nf->nhi;
	440	a0.gw=nf->nh;
	441	a0.from=nf->nh; /* FIXME Just a test */
	442	ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
	443	e=rte_get_temp(&a0);
	444	e->u.ospf.metric1=nf->metric;
	445	e->u.ospf.metric2=nf->metric2;
a7a3a0a3	446	e->u.ospf.tag=nf->tag;
aa1e082c OF	447	e->pflags = 0;
	448	e->net=ne;
	449	e->pref = p->preference;
7e681ef3 OF	450	DBG("Modifying rt entry %I\n (IP: %I, GW: %I)\n",
7e681ef3 OF	451	nf->fn.prefix,ip,nf->nh);
aa1e082c OF	452	rte_update(p->table, ne, p, e);
	453	}
	454	}
7e681ef3 OF	455	let:
7e681ef3 OF	456	FIB_ITERATE_END(nftmp);
dfa9a53a OF	457	}
	458
	459	void
468f2347	460	add_cand(list l, struct top_hash_entry en, struct top_hash_entry *par,
a02c6c18	461	u16 dist, struct ospf_area *oa)
dfa9a53a	462	{
e80e9d0d	463	node prev,n;
85195f1a	464	int flag=0,added=0;
e80e9d0d	465	struct top_hash_entry *act;
a02c6c18	466	struct proto *p=&oa->po->proto;
dfa9a53a OF	467
	468	if(en==NULL) return;
	469	if(en->lsa.age==LSA_MAXAGE) return;
	470	/* FIXME Does it have link back? Test it! */
	471	if(en->color==INSPF) return;
	472
e80e9d0d OF	473	if(dist>=en->dist) return;
	474	/*
	475	* FIXME The line above is not a bug, but we don't support
	476	* multiple next hops. I'll start as soon as nest will
	477	*/
85195f1a	478	DBG(" Adding candidate: rt: %I, id: %I, type: %u\n",en->lsa.rt,en->lsa.id,en->lsa.type);
c6c56264 OF	479
c6c56264 OF	480	en->nhi=NULL;
dfa9a53a	481
a02c6c18	482	calc_next_hop(par,en,oa);
e80e9d0d	483
85195f1a	484	if(en->color==CANDIDATE) /* We found a shorter path */
dfa9a53a	485	{
e80e9d0d	486	rem_node(&en->cn);
dfa9a53a	487	}
dfa9a53a	488
e80e9d0d OF	489	en->dist=dist;
e80e9d0d OF	490	en->color=CANDIDATE;
dfa9a53a	491
e80e9d0d	492	prev=NULL;
dfa9a53a	493
85195f1a	494	if(EMPTY_LIST(*l))
e80e9d0d	495	{
85195f1a OF	496	add_head(l,&en->cn);
	497	}
	498	else
	499	{
	500	WALK_LIST(n,*l)
dfa9a53a	501	{
85195f1a OF	502	act=SKIP_BACK(struct top_hash_entry, cn, n);
	503	if((act->dist>dist)\|\|
	504	((act->dist==dist)&&(act->lsa.type==LSA_T_NET)))
	505	{
	506	if(prev==NULL) add_head(l,&en->cn);
	507	else insert_node(&en->cn,prev);
	508	added=1;
	509	break;
	510	}
	511	prev=n;
	512	}
	513
	514	if(!added)
	515	{
	516	add_tail(l,&en->cn);
dfa9a53a OF	517	}
dfa9a53a OF	518	}
e80e9d0d	519	/* FIXME Some VLINK staff should be here */
dfa9a53a	520	}
468f2347	521
c6c56264 OF	522	void
c6c56264 OF	523	calc_next_hop(struct top_hash_entry par, struct top_hash_entry en,
a02c6c18	524	struct ospf_area *oa)
468f2347	525	{
c6c56264	526	struct ospf_neighbor *neigh;
a02c6c18 OF	527	struct proto *p=&oa->po->proto;
a02c6c18 OF	528	struct proto_ospf *po=oa->po;
85195f1a OF	529	DBG(" Next hop called\n");
85195f1a OF	530	if(par==oa->rt) return;
c6c56264	531	if(par->nhi==NULL)
468f2347	532	{
c6c56264	533	neighbor *nn;
85195f1a	534	DBG(" Next hop calculating for id: %I rt: %I type: %u\n",en->lsa.id,en->lsa.rt,en->lsa.type);
c6c56264	535	if(par->lsa.type!=LSA_T_RT) return;
a92847e7 OF	536	if((neigh=find_neigh_noifa(po,par->lsa.rt))==NULL) return;
	537	nn=neigh_find(p,&neigh->ip,0);
	538	DBG(" Next hop calculated: %I\n", nn->addr);
	539	en->nh=nn->addr;
	540	en->nhi=nn->iface;
	541	return;
	542	}
	543	en->nh=par->nh;
	544	en->nhi=par->nhi;
	545	DBG(" Next hop calculated: %I\n", en->nh);
	546	}
d345cda5	547