From 85195f1a53eb350cd32ecba69c208dbece6fb776 Mon Sep 17 00:00:00 2001 From: Ondrej Filip Date: Sun, 30 Apr 2000 22:14:31 +0000 Subject: Many small changes and bug fixes. Routing table calculation works. I'm waiting for rt lookup to add stub networks. --- proto/ospf/iface.c | 12 +++-- proto/ospf/lsalib.c | 39 +++++++++----- proto/ospf/lsalib.h | 2 +- proto/ospf/lsupd.c | 2 +- proto/ospf/neighbor.c | 17 ++++-- proto/ospf/ospf.h | 1 + proto/ospf/rt.c | 142 +++++++++++++++++++++++++++++++++----------------- proto/ospf/rt.h | 4 +- proto/ospf/topology.c | 24 +++++++-- 9 files changed, 167 insertions(+), 76 deletions(-) (limited to 'proto') diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c index 47ab8dcb..7015f012 100644 --- a/proto/ospf/iface.c +++ b/proto/ospf/iface.c @@ -73,9 +73,8 @@ downint(struct ospf_iface *ifa) void ospf_int_sm(struct ospf_iface *ifa, int event) { - struct proto *p; - - p=(struct proto *)(ifa->proto); + struct proto *p=(struct proto *)(ifa->proto); + struct proto_ospf *po=ifa->proto; DBG("%s: SM on iface %s. Event is \"%s\".\n", p->name, ifa->iface->name, ospf_ism[event]); @@ -105,12 +104,14 @@ ospf_int_sm(struct ospf_iface *ifa, int event) } addifa_rtlsa(ifa); } + originate_rt_lsa(ifa->oa,po); break; case ISM_BACKS: case ISM_WAITF: if(ifa->state==OSPF_IS_WAITING) { bdr_election(ifa ,p); + originate_rt_lsa(ifa->oa,po); } break; case ISM_NEICH: @@ -119,16 +120,21 @@ ospf_int_sm(struct ospf_iface *ifa, int event) { bdr_election(ifa ,p); } + originate_rt_lsa(ifa->oa,po); + break; case ISM_DOWN: iface_chstate(ifa, OSPF_IS_DOWN); downint(ifa); + originate_rt_lsa(ifa->oa,po); break; case ISM_LOOP: /* Useless? */ iface_chstate(ifa, OSPF_IS_LOOP); downint(ifa); + originate_rt_lsa(ifa->oa,po); break; case ISM_UNLOOP: iface_chstate(ifa, OSPF_IS_DOWN); + originate_rt_lsa(ifa->oa,po); break; default: die("%s: ISM - Unknown event?",p->name); diff --git a/proto/ospf/lsalib.c b/proto/ospf/lsalib.c index 9ad56840..261ed341 100644 --- a/proto/ospf/lsalib.c +++ b/proto/ospf/lsalib.c @@ -319,26 +319,26 @@ lsa_comp(struct ospf_lsa_header *l1, struct ospf_lsa_header *l2) /* LSA can be temporarrily, but body must be mb_alloced. */ struct top_hash_entry * -lsa_install_new(struct ospf_lsa_header *lsa, void *body, struct ospf_area *oa) +lsa_install_new(struct ospf_lsa_header *lsa, void *body, struct ospf_area *oa, + struct proto *p) { - int change=0,i; + int change=0; + unsigned i; struct top_hash_entry *en; if((en=ospf_hash_find_header(oa->gr,lsa))==NULL) { en=ospf_hash_get_header(oa->gr,lsa); change=1; - s_add_tail(&oa->lsal, SNODE en); } else { - if(en->lsa.options!=lsa->options) change=1; - if((en->lsa.age==LSA_MAXAGE)||(lsa->age==LSA_MAXAGE)) change=1; - if(en->lsa.length!=lsa->length) change=1; + if((en->lsa.length!=lsa->length)||(en->lsa.options!=lsa->options)|| + ((en->lsa.age==LSA_MAXAGE)||(lsa->age==LSA_MAXAGE))) change=1; else { u8 *k=en->lsa_body,*l=body; - for(i=0;ilength;i++) + for(i=0;i<(lsa->length-sizeof(struct ospf_lsa_header));i++) { if(*(k+i)!=*(l+i)) { @@ -346,15 +346,26 @@ lsa_install_new(struct ospf_lsa_header *lsa, void *body, struct ospf_area *oa) break; } } - s_rem_node(SNODE en); - s_add_tail(&oa->lsal, SNODE en); + /* FIXME delete routes to stub networks! */ + } + if(change) s_rem_node(SNODE en); + } + + if(change) + { + s_add_tail(&oa->lsal, SNODE en); + en->inst_t=now; + if(en->lsa_body!=NULL) mb_free(en->lsa_body); + en->lsa_body=body; + en->lsa.length=lsa->length; + memcpy(&en->lsa,lsa,sizeof(struct ospf_lsa_header)); + /* FIXME decide if route calcualtion must be done and how */ + if(oa->rt!=NULL) + { + DBG("Starting routing table calculation.\n"); + ospf_rt_spfa(oa, p); } } - en->inst_t=now; - if(en->lsa_body!=NULL)mb_free(en->lsa_body); - en->lsa_body=body; - memcpy(&en->lsa,lsa,sizeof(struct ospf_lsa_header)); - /* FIXME decide if route calcualtion must be done and how */ return en; } diff --git a/proto/ospf/lsalib.h b/proto/ospf/lsalib.h index bba8c26b..b16ec78a 100644 --- a/proto/ospf/lsalib.h +++ b/proto/ospf/lsalib.h @@ -22,6 +22,6 @@ u16 lsasum_check(struct ospf_lsa_header *h,void *body,struct proto_ospf *po); #define CMP_OLDER -1 int lsa_comp(struct ospf_lsa_header *l1, struct ospf_lsa_header *l2); struct top_hash_entry *lsa_install_new(struct ospf_lsa_header *lsa, void *body, - struct ospf_area *oa); + struct ospf_area *oa, struct proto *p); #endif /* _BIRD_OSPF_LSALIB_H_ */ diff --git a/proto/ospf/lsupd.c b/proto/ospf/lsupd.c index 2735695e..3390abb4 100644 --- a/proto/ospf/lsupd.c +++ b/proto/ospf/lsupd.c @@ -319,7 +319,7 @@ ospf_lsupd_rx(struct ospf_lsupd_packet *ps, struct proto *p, body=mb_alloc(p->pool,lsatmp.length-sizeof(struct ospf_lsa_header)); ntohlsab(lsa+1,body,lsatmp.type, lsatmp.length-sizeof(struct ospf_lsa_header)); - lsadb=lsa_install_new(&lsatmp,body, oa); + lsadb=lsa_install_new(&lsatmp,body, oa, p); DBG("New LSA installed in DB\n"); /* FIXME 145 (5f) self originated? */ diff --git a/proto/ospf/neighbor.c b/proto/ospf/neighbor.c index 4a450c1d..4a44b6b2 100644 --- a/proto/ospf/neighbor.c +++ b/proto/ospf/neighbor.c @@ -178,9 +178,8 @@ void ospf_neigh_sm(struct ospf_neighbor *n, int event) /* Interface state machine */ { - struct proto *p; - - p=(struct proto *)(n->ifa->proto); + struct proto *p=(struct proto *)(n->ifa->proto); + struct proto_ospf *po=n->ifa->proto; DBG("%s: Neighbor state machine for neighbor %I, event \"%s\".\n", p->name, n->rid, ospf_inm[event]); @@ -203,7 +202,7 @@ ospf_neigh_sm(struct ospf_neighbor *n, int event) } break; case INM_2WAYREC: - if(n->state==NEIGHBOR_INIT) + if(n->stateifa, ISM_NEICH); } break; case INM_NEGDONE: @@ -236,6 +236,7 @@ ospf_neigh_sm(struct ospf_neighbor *n, int event) break; case INM_LOADDONE: neigh_chstate(n,NEIGHBOR_FULL); + originate_rt_lsa(n->ifa->oa,po); break; case INM_ADJOK: switch(n->state) @@ -271,11 +272,13 @@ ospf_neigh_sm(struct ospf_neighbor *n, int event) case INM_LLDOWN: case INM_INACTTIM: neigh_chstate(n,NEIGHBOR_DOWN); + ospf_int_sm(n->ifa, ISM_NEICH); break; case INM_1WAYREC: if(n->state>=NEIGHBOR_2WAY) { neigh_chstate(n,NEIGHBOR_DOWN); + ospf_int_sm(n->ifa, ISM_NEICH); } break; default: @@ -287,7 +290,7 @@ ospf_neigh_sm(struct ospf_neighbor *n, int event) void bdr_election(struct ospf_iface *ifa, struct proto *p) { - struct ospf_neighbor *neigh,*ndr,*nbdr,me; + struct ospf_neighbor *neigh,*ndr,*nbdr,me,*tmp; u32 myid, ndrid, nbdrid; int doadj; @@ -335,7 +338,11 @@ bdr_election(struct ospf_iface *ifa, struct proto *p) doadj=0; if((ifa->drid!=ndrid) || (ifa->bdrid!=nbdrid)) doadj=1; ifa->drid=ndrid; + if((tmp=find_neigh(ifa,ndrid))==NULL) die("Error i BDR election.\n"); + ifa->drip=tmp->ip; ifa->bdrid=nbdrid; + if((tmp=find_neigh(ifa,nbdrid))==NULL) die("Error i BDR election.\n"); + ifa->bdrip=tmp->ip; DBG("%s: DR=%I, BDR=%I\n",p->name, ifa->drid, ifa->bdrid); diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h index bd45392f..31024f35 100644 --- a/proto/ospf/ospf.h +++ b/proto/ospf/ospf.h @@ -26,6 +26,7 @@ #include "nest/iface.h" #include "nest/route.h" #include "conf/conf.h" +#include #define OSPF_PROTO 89 #ifndef IPV6 diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c index e950cf31..7b3ca4d5 100644 --- a/proto/ospf/rt.c +++ b/proto/ospf/rt.c @@ -14,8 +14,7 @@ ospf_rt_spfa(struct ospf_area *oa, struct proto *p) struct top_hash_entry *en, *nx; u32 i,*rts; struct ospf_lsa_rt *rt; - struct ospf_lsa_rt_link *rtl; - rta a0,*a; + struct ospf_lsa_rt_link *rtl,*rr; /* * First of all, mark all vertices as they are not in SPF @@ -32,9 +31,12 @@ ospf_rt_spfa(struct ospf_area *oa, struct proto *p) 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, &en->cn); + 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)) { @@ -46,33 +48,43 @@ ospf_rt_spfa(struct ospf_area *oa, struct proto *p) 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; - rtl=(struct ospf_lsa_rt_link *)(rt+1); - for(i=0;rt->links;i++) + rr=(struct ospf_lsa_rt_link *)(rt+1); + DBG(" Number of links: %u\n",rt->links); + for(i=0;ilinks;i++) { tmp=NULL; - switch((rtl+i)->type) + rtl=(rr+i); + DBG(" Working on link: %I (type: %u) ",rtl->id,rtl->type); + switch(rtl->type) { case LSART_STUB: case LSART_VLNK: + DBG("Ignoring\n"); continue; break; case LSART_NET: - tmp=ospf_hash_find(oa->gr,rtl->data,rtl->id,LSA_T_RT); + /* FIXME Oh shit so bad complication */ + 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->data,rtl->id,LSA_T_NET); + case LSART_PTP: /* FIXME */ + 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,p); + add_cand(&oa->cand,tmp,act,act->dist+rtl->metric,p,oa); } break; case LSA_T_NET: @@ -81,8 +93,11 @@ ospf_rt_spfa(struct ospf_area *oa, struct proto *p) for(i=0;i<(act->lsa.length-sizeof(struct ospf_lsa_header)- sizeof(struct ospf_lsa_net))/sizeof(u32);i++) { - tmp=ospf_hash_find(oa->gr, *rts, *rts, LSA_T_RT); - add_cand(&oa->cand,tmp,act,act->dist,p); + 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,p,oa); } break; } @@ -90,37 +105,47 @@ ospf_rt_spfa(struct ospf_area *oa, struct proto *p) if((act->lsa.type==LSA_T_NET)&&(act->nhi!=NULL)) { net *ne; + rta a0; rte *e; ip_addr ip; - struct ospf_lsa_net *ln=en->lsa_body; + struct ospf_lsa_net *ln=act->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; /* FIXME */ + a0.dest=RTD_ROUTER; a0.flags=0; + a0.aflags=0; a0.iface=act->nhi; a0.gw=act->nh; - ip=ipa_from_u32(act->lsa.id); - - + a0.from=act->nh; /* FIXME Just a test */ + ip=ipa_and(ipa_from_u32(act->lsa.id),ln->netmask); ne=net_get(p->table, ip, ipa_mklen(ln->netmask)); e=rte_get_temp(&a0); - e->u.ospf.metric1=en->dist; + e->u.ospf.metric1=act->dist; e->u.ospf.metric2=0; e->u.ospf.tag=0; /* FIXME Some config? */ - + e->pflags = 0; + e->net=ne; + DBG("Modifying rt entry %I mask %I\n (IP: %I, GW: %I, Iface: %s)\n", + act->lsa.id,ln->netmask,ip,act->nh,act->nhi->name); rte_update(p->table, ne, p, e); - - //a0.from=act->lsa.rt; } - - - - + else + { + if(act->lsa.type==LSA_T_NET) + { + struct ospf_lsa_net *ln=act->lsa_body; + DBG("NOT modifying rt entry %I mask %I\n",act->lsa.id,ln->netmask); + } + } } + DBG("Now calculating routes for stub networks.\n"); + /* Now calculate routes to stub networks */ WALK_SLIST_DELSAFE(SNODE en, SNODE nx, oa->lsal) @@ -129,20 +154,24 @@ ospf_rt_spfa(struct ospf_area *oa, struct proto *p) { if(en->dist==LSINFINITY) { - s_rem_node(SNODE en); + /* FIXME I cannot remove node If I'm not FULL states */ + //s_rem_node(SNODE en); /* FIXME Remove from routing table! */ - mb_free(en->lsa_body); - ospf_hash_delete(oa->gr, en); + //mb_free(en->lsa_body); + //ospf_hash_delete(oa->gr, en); } - if(en->lsa.type==LSA_T_NET) + if(en->lsa.type==LSA_T_RT) { + DBG("Working on LSA: rt: %I, id: %I, type: %u\n",en->lsa.rt,en->lsa.id,en->lsa.type); rt=(struct ospf_lsa_rt *)en->lsa_body; if((rt->VEB)&(1>>LSA_RT_V)) oa->trcap=1; - rtl=(struct ospf_lsa_rt_link *)(rt+1); - for(i=0;rt->links;i++) + rr=(struct ospf_lsa_rt_link *)(rt+1); + for(i=0;ilinks;i++) { - if((rtl+i)->type==LSART_STUB) + rtl=rr+i; + if(rtl->type==LSART_STUB) { + DBG(" Working on stub network: %I\n",rtl->id); /* Check destination and so on (pg 166) */ } } @@ -153,10 +182,10 @@ ospf_rt_spfa(struct ospf_area *oa, struct proto *p) void add_cand(list *l, struct top_hash_entry *en, struct top_hash_entry *par, - u16 dist, struct proto *p) + u16 dist, struct proto *p, struct ospf_area *oa) { node *prev,*n; - int flag=0; + int flag=0,added=0; struct top_hash_entry *act; if(en==NULL) return; @@ -169,12 +198,13 @@ add_cand(list *l, struct top_hash_entry *en, struct top_hash_entry *par, * 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,p); + calc_next_hop(par,en,p,oa); - if(en->color==CANDIDATE) /* We found shorter path */ + if(en->color==CANDIDATE) /* We found a shorter path */ { rem_node(&en->cn); } @@ -184,37 +214,55 @@ add_cand(list *l, struct top_hash_entry *en, struct top_hash_entry *par, prev=NULL; - WALK_LIST(n,*l) + if(EMPTY_LIST(*l)) { - act=SKIP_BACK(struct top_hash_entry, cn, n); - if((act->dist>dist)|| - ((act->dist==dist)&&(act->lsa.type==LSA_T_NET))) + add_head(l,&en->cn); + } + else + { + WALK_LIST(n,*l) { - if(prev==NULL) add_head(l,&en->cn); - else insert_node(&en->cn,prev); - break; + 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); } - prev=n; } /* FIXME Some VLINK staff should be here */ - } void calc_next_hop(struct top_hash_entry *par, struct top_hash_entry *en, - struct proto *p) + struct proto *p, struct ospf_area *oa) { struct ospf_neighbor *neigh; struct proto_ospf *po=(struct proto_ospf *)p; + 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,en->lsa.rt))==NULL) bug("XXX\n"); + if((neigh=find_neigh_noifa(po,en->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); } diff --git a/proto/ospf/rt.h b/proto/ospf/rt.h index 9539751c..93c1109c 100644 --- a/proto/ospf/rt.h +++ b/proto/ospf/rt.h @@ -12,8 +12,8 @@ void ospf_rt_spfa(struct ospf_area *oa, struct proto *p); void add_cand(list *l, struct top_hash_entry *en, struct top_hash_entry *par, - u16 dist, struct proto *p); + u16 dist, struct proto *p, struct ospf_area *oa); void calc_next_hop(struct top_hash_entry *par, struct top_hash_entry *en, - struct proto *p); + struct proto *p, struct ospf_area *oa); #endif /* _BIRD_OSPF_RT_H_ */ diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c index db15f63c..b448f51f 100644 --- a/proto/ospf/topology.c +++ b/proto/ospf/topology.c @@ -188,6 +188,7 @@ addifa_rtlsa(struct ospf_iface *ifa) ifa->oa=oa; oa->rt=originate_rt_lsa(oa,po); + DBG("RT LSA: rt: %I, id: %I, type: %u\n",oa->rt->lsa.rt,oa->rt->lsa.id,oa->rt->lsa.type); flood_lsa(NULL,NULL,&oa->rt->lsa,po,NULL,oa); } @@ -199,7 +200,7 @@ originate_rt_lsa(struct ospf_area *oa, struct proto_ospf *po) struct top_hash_entry *en; void *body; - DBG("%s: Originating RT_lsa for area \"%d\".\n", po->proto.name, oa->areaid); + DBG("%s: Originating RT_lsa for area \"%I\".\n", po->proto.name, oa->areaid); lsa.age=0; lsa.id=rtid; @@ -215,7 +216,7 @@ originate_rt_lsa(struct ospf_area *oa, struct proto_ospf *po) } body=originate_rt_lsa_body(oa, &lsa.length, po); lsasum_calculate(&lsa,body,po); - en=lsa_install_new(&lsa, body, oa); + en=lsa_install_new(&lsa, body, oa, &po->proto); return en; } @@ -258,7 +259,11 @@ ospf_top_hash_u32(u32 a) static inline unsigned ospf_top_hash(struct top_graph *f, u32 lsaid, u32 rtrid, u32 type) { +#if 1 /* Dirty patch to make rt table calculation work. */ + return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32((type==2) ? lsaid : rtrid) + type) & f->hash_mask; +#else return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) + type) & f->hash_mask; +#endif } struct top_graph * @@ -329,8 +334,21 @@ ospf_hash_find(struct top_graph *f, u32 lsa, u32 rtr, u32 type) { struct top_hash_entry *e = f->hash_table[ospf_top_hash(f, lsa, rtr, type)]; +#if 1 + if(type==2 && lsa==rtr) + { + while (e && (e->lsa.id != lsa || e->lsa.type != 2 )) + e = e->next; + } + else + { + while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr)) + e = e->next; + } +#else while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type)) e = e->next; +#endif return e; } @@ -389,7 +407,7 @@ ospf_top_dump(struct top_graph *f) struct top_hash_entry *e = f->hash_table[i]; while (e) { - debug("\t%04x %08x %08x %p\n", e->lsa.type, e->lsa.id, + debug("\t%04x %08I %08I %p\n", e->lsa.type, e->lsa.id, e->lsa.rt, e->lsa_body); e = e->next; } -- cgit v1.2.3