[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, *nx;
  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);

  flush=can_flush_lsa(oa);

  if((delta=now-oa->lage)>=AGINGDELTA)
  {
     oa->lage=now;
     age=1;
  }

  WALK_SLIST_DELSAFE(SNODE en, nx, oa->lsal)
  {
    en->color=OUTSPF;
    en->dist=LSINFINITY;
    en->nhi=NULL;
    if(age) ospf_age(en,delta,flush,oa);
  }

  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.\n");
	      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=0;
        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;
  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))
    {
      die("Invalid length of prefix! ID: %I, RT: %I, Type: %u, mask %I",
        en->lsa.id,en->lsa.rt,en->lsa.type,le->netmask);
    }

    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;

    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) 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=0;
      }
    }
    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=0;
      }


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