/* RSPF - Radio Shortest Path First * This code may be used for non-commercial purposes only. * Anders Klemets SM0RGV * 890918 - Version 2.0 * 900816 - Version 2.1 */ #include "global.h" #include "mbuf.h" #include "proc.h" #include "timer.h" #include "netuser.h" #include "internet.h" #include "pktdrvr.h" #include "ip.h" #include "iface.h" #include "ax25.h" #include "arp.h" #include "icmp.h" #include "socket.h" #include "rspf.h" extern struct route *rt_lookup __ARGS((int32 target)); extern struct lq *al_lookup __ARGS((struct iface *ifp,char *addr)); struct rspf_stat Rspf_stat; struct rspfreasm *Rspfreasmq = NULLRREASM; struct rspfiface *Rspfifaces = NULLRIFACE; struct rspfadj *Adjs = NULLADJ; struct rspfrouter *Rspfrouters = NULLRROUTER; struct mbuf *Rspfinq = NULLBUF; struct timer Rspfreasmt, Susptimer; char *Rrh_message = NULLCHAR; unsigned short Rspfpingmax = 5; static int Keeprouter = 0; static int16 Envelopeid = 0; static int Nrspfproc = 0; static unsigned char Rspfsubseq = 0; static short Rspfseq = -32768 + 1; static char *findlowroute __ARGS((int32 addr,int *low,int add,int32 *resaddr,int *resbits)); static void makeroutes __ARGS((void)); static void partialupdate __ARGS((struct rspfrouter *rr,struct mbuf *bp)); static struct rspfrouter *rr_lookup __ARGS((int32 addr)); static void rr_delete __ARGS((int32 addr)); static struct rspfiface *rtif_lookup __ARGS((int32 addr)); static void rspfcsum __ARGS((struct mbuf **bpp,int32 dest)); static void update_in __ARGS((struct mbuf *bp,int32 addr)); static void node_in __ARGS((struct mbuf *bp,int32 addr,int full)); static void sendonerspf __ARGS((int32 addr,int32 dest)); static void sendtoall __ARGS((struct mbuf *bp,int nodecnt,struct rspfiface *riface)); static int sendupdate __ARGS((struct mbuf *bp,int nodecnt,int32 addr)); static int isnewer __ARGS((short a,short b)); static void del_reasm __ARGS((struct rspfreasm *re)); static void reasmtimeout __ARGS((void *t)); static struct mbuf *rspfreasm __ARGS((struct mbuf *bp,struct rspfpacketh *rph,int32 addr)); static struct mbuf *fragmenter __ARGS((struct mbuf *bp,int nodes,int16 mtu)); static struct mbuf *makeadjupdate __ARGS((int32 addr,struct rspfrouter *rr)); static void pushadj __ARGS((struct mbuf **bpp,int32 addr,int bits)); static void sendrrh __ARGS((struct rspfiface *ri)); static void sendrspf __ARGS((void)); static void goodbadnews __ARGS((struct rspfadj *adj)); static void add_rspfadj __ARGS((struct rspfadj *adj)); static void rspfcheck __ARGS((struct rspfadj *adj)); static void rspfping __ARGS((int oldstate,void *p,void *v)); /* IP passes its RSPF packets to this function */ void rspf_input(iface,ip,bp,rxbroadcast) struct iface *iface; struct ip *ip; struct mbuf *bp; int rxbroadcast; { struct pseudo_header ph; /* Pseudo-header for checksumming */ if(bp == NULLBUF) return; ph.length = ip->length - IPLEN - ip->optlen; ph.source = ip->source; ph.dest = ip->dest; ph.protocol = ip->protocol; if(cksum(&ph,bp,ph.length) != 0){ /* Checksum failed, ignore packet completely */ free_p(bp); ++Rspf_stat.badcsum; return; } bp = pushdown(bp,1 + sizeof(ip->source) + sizeof(iface)); *bp->data = RSPFE_PACKET; memcpy(bp->data + 1,&ip->source,sizeof(ip->source)); memcpy(bp->data + 1 + sizeof(ip->source),&iface,sizeof(iface)); enqueue(&Rspfinq,bp); } /* Main loop in RSPF process */ void rspfmain(v,v1,v2) int v; void *v1,*v2; { union rspf rspf; /* Internal packet structure */ struct rspfadj *adj; /* Adjacency */ struct mbuf *bp, *tbp; struct rspfiface *riface; struct iface *iface; struct route *rp; int32 source; /* Source address */ int cmd; for(;;) { if(Rspfinq == NULLBUF) pwait(&Rspfinq); bp = dequeue(&Rspfinq); /* at least 5 bytes */ cmd = PULLCHAR(&bp); /* get internal event indicator */ pullup(&bp,(char *)&source,sizeof(source)); switch(cmd) { case RSPFE_RRH: sendrrh((struct rspfiface *)source); break; case RSPFE_CHECK: rspfcheck((struct rspfadj *)source); break; case RSPFE_UPDATE: sendrspf(); break; case RSPFE_ARP: adj = (struct rspfadj *) source; source = adj->addr; /* fall through */ case RSPFE_PACKET: pullup(&bp,(char *)&iface,sizeof(iface)); break; } if(cmd != RSPFE_PACKET && cmd != RSPFE_ARP) continue; if(cmd == RSPFE_PACKET && ntohrspf(&rspf,&bp) == -1){ free_p(bp); continue; } if(iface != NULLIF) { for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) if(riface->iface == iface) break; } else /* fails if there is no route or no RSPF interface */ riface = rtif_lookup(source); if(riface == NULLRIFACE) { free_p(bp); if(cmd == RSPFE_PACKET) ++Rspf_stat.norspfiface; continue; /* We do not use RSPF on this interface */ } /* If we dont have an entry in the routing table for this station, * or if the entry is less than 32 bits specific or has a higher * cost our new route, and is pointing to the wrong interface, * then add a correct, private, route. */ rp = rt_lookup(source); if(rp == NULLROUTE || (rp != NULLROUTE && rp->iface != riface->iface && (rp->bits < 32 || rp->metric > riface->quality))) rt_add(source,32,0,iface,riface->quality,0,1); if(cmd == RSPFE_ARP) { adj->cost = riface->quality; /* default cost */ add_rspfadj(adj); continue; } switch(rspf.hdr.type){ /* packet types */ case RSPF_RRH: ++Rspf_stat.rrhin; free_p(bp); adj = (struct rspfadj *)callocw(1,sizeof(struct rspfadj)); adj->addr = rspf.rrh.addr; adj->seq = rspf.rrh.seq; adj->cost = riface->quality; /* Default cost */ adj->state = RSPF_TENTATIVE; if(rspf.rrh.flags & RSPFMODE) adj->tos = DELAY; else adj->tos = RELIABILITY; add_rspfadj(adj); break; case RSPF_FULLPKT: ++Rspf_stat.updatein; /* Feed the packet through the reassembly queue */ if((tbp = rspfreasm(bp,&rspf.pkthdr,source)) != NULLBUF) update_in(tbp,source); break; } } } /* This function is called every time an RRH should be broadcasted. * An RRH is sent on the interface given by ri or on every RSPF interface. * The broadcast address of the interface must be routed onto the same * interface (using a static route for instance) otherwise there will be no * RRH sent on that interface. */ static void sendrrh(ri) struct rspfiface *ri; /* interface to use, if specified */ { struct pseudo_header ph; struct mbuf *bp, *data = NULLBUF; struct rspfiface *riface; struct route *rp; struct rrh rrh; for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) { if(ri != NULLRIFACE && riface != ri) continue; if((rp = rt_lookup(riface->iface->broadcast)) != NULLROUTE && rp->iface == riface->iface){ rrh.version = RSPF_VERSION; rrh.addr = riface->iface->addr; ph.length = 0; if(Rrh_message != NULLCHAR) { data = ambufw(strlen(Rrh_message)); memcpy(data->data,Rrh_message,strlen(Rrh_message)); ph.length = data->cnt = strlen(Rrh_message); } ph.length += RRHLEN; ph.source = riface->iface->addr; ph.dest = riface->iface->broadcast; ph.protocol = RSPF_PTCL; /* Start the RRH link level packet counter at 1, since adj->seq * is 0 only for ARP generated adjacencies. This is also correct * since rawsndcnt will increase by one when the RRH is sent. */ rrh.seq = riface->iface->rawsndcnt + 1; /* Default is to use the same mode as the interface */ if(Rspfownmode == -1) rrh.flags = !(riface->iface->flags & CONNECT_MODE); else rrh.flags = !(Rspfownmode & CONNECT_MODE); bp = htonrrh(&rrh,data,&ph); ++Rspf_stat.rrhout; ip_send(riface->iface->addr,riface->iface->broadcast,RSPF_PTCL, 0,2,bp,0,0,0); /* the ttl will be decremented to 1 */ } } } /* This function is called whenever an RRH packet has been received or when * a new entry is added to the ARP table. */ static void add_rspfadj(adj) struct rspfadj *adj; { struct rspfadj *oldadj, *tmp; struct rspfiface *riface; struct arp_tab *atp; struct lq *alp; int dif, origdif; /* Find the previous copy of the adjacency, if there was any */ /* Insert the new adjacency */ adj->next = Adjs; Adjs = adj; for(oldadj = Adjs; oldadj->next != NULLADJ; oldadj = oldadj->next) if(oldadj->next->addr == adj->addr) { tmp = oldadj->next; oldadj->next = oldadj->next->next; oldadj = tmp; break; } if(oldadj->addr != adj->addr || oldadj == adj) oldadj = NULLADJ; /* ARP entries give no sequence number, so save the old one */ if(oldadj != NULLADJ) { if(adj->seq == 0) adj->seq = oldadj->seq; if(adj->tos == 0) adj->tos = oldadj->tos; /* they give no TOS either */ } switch(adj->state) { case RSPF_TENTATIVE: if(oldadj != NULLADJ) { /* If the adjacency was in OK state, it will remain there. * An RRH or ARP upcall can never generate an OK -> Tentative * transition. */ if(oldadj->state == RSPF_OK) adj->state = RSPF_OK; adj->okcnt = oldadj->okcnt; /* If old state was Bad, don't announce this adjacency until * it is known to be OK, to prevent announcing an adjacency * with an state transition loop such as OK -> Suspect -> Bad -> * Tentative -> Suspect -> Bad -> Tentative -> ... */ if(oldadj->state == RSPF_BAD) { adj->okcnt = 0; stop_timer(&oldadj->timer); /* Enter Suspect state at once, there is no point in * dwelling as Tentative. */ rspfcheck(adj); } else { /* Inherit the old timer */ adj->timer.func = rspfevent; adj->timer.arg = (void *) &adj->timer; /* continue where the old timer is stopped */ adj->timer.start = read_timer(&oldadj->timer); stop_timer(&oldadj->timer); /* Set the timer to Suspectimer in the unlikely event that * the timer was stopped and oldadj is not Suspect or Bad. * Suspect state is dealt with further below. */ if(adj->timer.start == 0) adj->timer.start = dur_timer(&Susptimer); start_timer(&adj->timer); adj->timer.start = oldadj->timer.start; } /* We must now try to figure out from which AX.25 callsign this * packet came. Looking at the ARP table may sometimes help. */ if(oldadj->seq != 0 && adj->seq != 0 && (riface = rtif_lookup(adj->addr)) != NULLRIFACE && (atp = arp_lookup(ARP_AX25,adj->addr)) != NULLARP && atp->state == ARP_VALID && (alp = al_lookup(riface->iface,atp->hw_addr)) != NULLLQ){ /* The wrapping of the modulus is taken into account here */ if(oldadj->seq > (MAXINT16 - 100) && adj->seq < 100) origdif = adj->seq + MAXINT16 - oldadj->seq; else origdif = adj->seq - oldadj->seq; if((alp->currxcnt - adj->heard) > (MAXINT16 - 100) && adj->seq < 100) dif = origdif + MAXINT16 - (alp->currxcnt - adj->heard); else dif = origdif - (alp->currxcnt - adj->heard); adj->heard = alp->currxcnt; /* Update the counter */ /* At this point, "origdif" equals the difference in sequence * numbers between the two latest RRH packets, i.e. the * number of AX.25 frames the station has sent during since * the last RRH packet we heard. "dif" equals the number of * AX.25 frames that we actually heard from that station * during the same period. */ if(origdif > 0 && dif > 0) /* This algorithm can be improved, see 2.1 spec */ adj->cost = riface->quality*2-riface->quality*dif/origdif; } /* Ignore any new RRH's if a pinger process is already running */ if(oldadj->state == RSPF_SUSPECT) { if(adj->heard != 0) /* save new heard count */ oldadj->heard = adj->heard; oldadj->next = adj->next; /* adj is at start of chain */ Adjs = oldadj; stop_timer(&adj->timer); free((char *)adj); return; } } else { /* oldadj == NULLADJ */ rspfcheck(adj); /* enter Suspect state */ /* A new adjacency may affect the routing table even though no * routing updates have yet been received from it. */ makeroutes(); } break; case RSPF_OK: if(oldadj != NULLADJ) { if(oldadj->state == RSPF_SUSPECT) killproc(oldadj->pinger); adj->okcnt += oldadj->okcnt; stop_timer(&oldadj->timer); } else makeroutes(); /* routing table may change */ if(adj->okcnt == 1) /* A previously unkown route */ goodbadnews(adj); /* ..that is good news */ break; } free((char *)oldadj); } /* Take appropriate action if an adjacency is Bad or Tentative */ static void rspfcheck(adj) struct rspfadj *adj; { struct rspfadj *prev; for(prev = Adjs; prev != NULLADJ; prev = prev->next) if(prev->next == adj) break; switch(adj->state){ case RSPF_OK: adj->state = RSPF_TENTATIVE; /* note fall-thru */ case RSPF_TENTATIVE: if (Nrspfproc < RSPF_PROCMAX) { Nrspfproc++; adj->pinger = newproc("RSPF ping",1024,rspfping, (int)adj->state,adj,NULL,0); adj->state = RSPF_SUSPECT; /* The adjacency is now Suspect */ } else { /* Try later */ adj->timer.start = dur_timer(&Susptimer); start_timer(&adj->timer); } break; case RSPF_BAD: rr_delete(adj->addr); adj->cost = 255; if(adj->okcnt != 0) goodbadnews(adj); /* This is bad news... */ if(prev != NULLADJ) prev->next = adj->next; else Adjs = adj->next; stop_timer(&adj->timer); /* just in case */ free((char *)adj); /* delete the adjacency */ makeroutes(); /* update the routing table */ break; } } /* Send a ping to a suspect or tentative adjacency */ static void rspfping(oldstate, p, v) int oldstate; void *p, *v; { int s, fromlen, pcnt; struct icmp icmp; struct rspfadj *adj; struct sockaddr_in from; struct mbuf *bp; pause(((ptol(p) & 7)+1)*1000/MSPTICK); /* Pause for 1 to 8 seconds */ adj = (struct rspfadj *) p; adj->timer.func = rspfevent; /* Fill in timer values */ adj->timer.arg = (void *) &adj->timer; adj->timer.start = dur_timer(&Susptimer); if((s = socket(AF_INET,SOCK_RAW,IPPROTO_ICMP)) == -1){ --Nrspfproc; adj->state = oldstate; start_timer(&adj->timer); return; } fromlen = sizeof(from); for(pcnt=0; pcnt < Rspfpingmax; ++pcnt) { pingem(s,adj->addr,0,(int16)s,0); /* Now collect the reply */ alarm(30 * 1000/MSPTICK);/* Let each ping timeout after 30 seconds */ for(;;) { if(recv_mbuf(s,&bp,0,(char *)&from,&fromlen) == -1){ if(errno == EALARM) /* We timed out */ break; alarm(0); adj->state = oldstate; close_s(s); --Nrspfproc; start_timer(&adj->timer); return; } ntohicmp(&icmp,&bp); free_p(bp); if(icmp.type != ICMP_ECHO_REPLY || from.sin_addr.s_addr != adj->addr || icmp.args.echo.id != s) /* Ignore other people's responses */ continue; alarm(0); if(++adj->okcnt == 1) goodbadnews(adj); /* Good news */ close_s(s); --Nrspfproc; start_timer(&adj->timer); adj->state = RSPF_OK; /* Finally change state */ return; } } /* we give up, mark the adjacency as bad */ adj->state = RSPF_BAD; close_s(s); --Nrspfproc; start_timer(&adj->timer); } /* ARP upcalls come in two flavors: When an ARP Reply has been received, we * know for certain that bidirectional communication is possible with the * particular station. But when an ARP Request is received, or if an ARP * entry is added manually, it has yet to be determined if the link is * bidirectional so iface is NULLIF in those cases. */ void rspfarpupcall(addr,hardware,iface) int32 addr; /* Address being added to ARP table */ int16 hardware; /* Hardware type */ struct iface *iface; /* Interface used, if known */ { struct rspfadj *adj; struct mbuf *bp; struct rspfiface *riface; if((riface = rtif_lookup(addr)) == NULLRIFACE) return; /* Not a route to an RSPF interface */ /* Proceed only if the ARP entry is for a hardware type that is relevant * for the interface onto which IP datagrams are routed. */ switch(hardware) { case ARP_NETROM: if(riface->iface->type != CL_NETROM) return; break; case ARP_AX25: if(riface->iface->type != CL_AX25) return; break; case ARP_ETHER: if(riface->iface->type != CL_ETHERNET) return; break; case NHWTYPES: break; /* "Any interface type is ok" type entry */ default: return; } if((adj = (struct rspfadj *)calloc(1,sizeof(struct rspfadj)))==NULLADJ) return; adj->addr = addr; if(iface == NULLIF) /* A manual ARP entry or Request, may be no-good */ adj->state = RSPF_TENTATIVE; else { adj->state = RSPF_OK; adj->okcnt++; adj->timer.func = rspfevent; /* Fill in timer values */ adj->timer.arg = (void *) &adj->timer; adj->timer.start = dur_timer(&Susptimer); start_timer(&adj->timer); } if((bp = alloc_mbuf(1+sizeof(int32)+sizeof(iface))) == NULLBUF) { stop_timer(&adj->timer); free((char *)adj); return; } *bp->data = RSPFE_ARP; memcpy(bp->data + 1, (char *) &adj, sizeof(adj)); memcpy(bp->data + 1 + sizeof(adj), (char *) &iface, sizeof(iface)); bp->cnt = bp->size; enqueue(&Rspfinq,bp); } /* Called by "route add" command. */ void rspfrouteupcall(addr,bits,gateway) int32 addr; /* Address added to routing table */ unsigned bits; /* Significant bits in address */ int32 gateway; /* Address of gateway station */ { /* We are only interested in 32 bit specific routes that use a * gateway. Direct routes will be discovered anyway. */ if(bits != 32 || gateway == 0 || gateway == addr) return; if(rtif_lookup(addr) == NULLRIFACE) /* not routed onto RSPF interface */ return; rspfarpupcall(addr,NHWTYPES,NULLIF); /* proceed as an "arp add" upcall */ } /* When the suspect timer expires, we scan through the routing table for all * manual 32 bit specific routes through a gateway that are not an adjacency, * and calls rspfrouteupcall(). A similar thing is done for all manual ARP * entries. This will make sure that a station that was not reachable when * the "route add" or "arp add" command was executed will eventually be * discovered if it joins the network. */ void rspfsuspect(t) void *t; { struct rspfadj *adj; struct route *rp; struct arp_tab *ap; int i; start_timer(&Susptimer); /* restart the timer */ for(i = 0; i < HASHMOD; i++) /* Check the routing table */ for(rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next) { if((rp->flags & RTPRIVATE) || dur_timer(&rp->timer) != 0) continue; /* not this route */ for(adj = Adjs; adj != NULLADJ; adj = adj->next) if(adj->addr == rp->target) break; if(adj == NULLADJ) /* it is not already an adjacency */ rspfrouteupcall(rp->target,32,rp->gateway); } for(i=0; i < ARPSIZE; ++i) /* scan the ARP table */ for(ap = Arp_tab[i]; ap != NULLARP; ap = ap->next) { if(dur_timer(&ap->timer)) /* not a manual entry */ continue; for(adj = Adjs; adj != NULLADJ; adj = adj->next) if(adj->addr == ap->ip_addr) break; if(adj == NULLADJ) /* not already an adjacency */ rspfarpupcall(ap->ip_addr,ap->hardware,NULLIF); } } /* This non-layered function peeks at the routing table to figure out to which * interface datagrams for addr will be routed. Then it returns the matching * rspfiface structure. */ static struct rspfiface * rtif_lookup(addr) int32 addr; { struct rspfiface *riface; struct route *rp; if((rp = rt_lookup(addr)) == NULLROUTE) return NULLRIFACE; riface = Rspfifaces; while(riface != NULLRIFACE){ if(riface->iface == rp->iface) return riface; riface = riface->next; } return NULLRIFACE; } /* Send good or bad news partial routing updates. A cost of 255 should be * interpreted as bad news by the remote station. */ static void goodbadnews(adj) struct rspfadj *adj; { struct rspfnodeh nodeh; struct rspflinkh linkh; struct rspfiface *riface; struct rspfrouter *rr; struct mbuf *bp, *tbp, *wbp; int nodecnt = 1; if((riface = rtif_lookup(adj->addr)) == NULLRIFACE) return; bp = ambufw(5); bp->cnt = bp->size; *bp->data = 32; /* the number of significant bits in the address */ put32(bp->data+1,adj->addr); linkh.horizon = riface->horizon; linkh.erp = riface->erp; linkh.cost = adj->cost; linkh.adjn = 1; tbp = htonrspflink(&linkh,bp); nodeh.seq = Rspfseq; nodeh.subseq = ++Rspfsubseq; nodeh.links = 1; for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) { if(dup_p(&wbp,tbp,0,len_p(tbp)) != len_p(tbp)) { free_p(wbp); continue; } nodeh.addr = riface->iface->addr; bp = htonrspfnode(&nodeh,wbp); sendtoall(bp,1,riface); } free_p(tbp); /* If this is a new adjacency, then send it a routing update immediately */ if(adj->cost == 255 || adj->okcnt != 1) return; /* When two RSPF stations learn about each others existence, one of * them will usually have received an RRH from the other. The one that * received the RRH will send the peer a routing update immediately. * So in the code below, if no RRH has been received (seq is 0) and no * routing update has yet been received, we should expect to receive a * routing update shortly if the adjacency is running RSPF. * This could fail though if two RSPF stations learn about each other * solely through ARP upcalls and no RRH's or Updates were exchanged * prior to or during the establishment of the adjacency. */ if(adj->seq == 0 && rr_lookup(adj->addr) == NULLRROUTER) { if(adj->state != RSPF_SUSPECT) /* running in RSPF process, give up */ return; alarm(15 * 1000/MSPTICK); /* wait for an Update */ if(pwait(adj) == EALARM) return; /* still no sign of RSPF activity from the adjacency */ alarm(0); } ++adj->okcnt; /* we don't want to get here again */ if((bp = makeownupdate(adj->addr,1)) == NULLBUF) return; for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next) if((tbp = makeadjupdate(get32(rr->data->data),rr)) != NULLBUF){ append(&bp,tbp); nodecnt++; } sendupdate(bp,nodecnt,adj->addr); } /* This function is called whenever it is time to send a new RSPF update */ static void sendrspf() { struct rspfrouter *rr; struct mbuf *bp, *wbp, *tmp = NULLBUF; struct rspfiface *riface; struct rspfadj *adj; int nodecnt, incr = 1; for(nodecnt = 1, rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next) if(!rr->sent) /* don't send stale data */ if((bp = makeadjupdate(get32(rr->data->data),rr)) != NULLBUF){ append(&tmp,bp); nodecnt++; } for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) { /* Find an address that is routed onto this interface */ for(adj = Adjs; adj != NULLADJ; adj = adj->next) if(rtif_lookup(adj->addr) == riface) break; if(adj == NULLADJ) /* no adjacency on that interface? */ continue; if(dup_p(&wbp,tmp,0,len_p(tmp)) != len_p(tmp)) { free_p(wbp); continue; } if((bp = makeownupdate(adj->addr,incr)) != NULLBUF) { incr = 0; /* sequence number is incremented only once */ append(&bp,wbp); } else break; sendtoall(bp,nodecnt,riface); } free_p(tmp); for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next) if(!rr->sent) /* Mark router data as propagated */ ++rr->sent; } /* This function is used to answer "poll" messages */ static void sendonerspf(addr,dest) int32 addr; /* address of station whose routing update we will make */ int32 dest; /* address of station to send the update to */ { struct mbuf *bp; if(ismyaddr(addr)){ if((bp = makeownupdate(dest,0)) == NULLBUF) return; sendupdate(bp,1,dest); return; } if((bp = makeadjupdate(addr,NULLRROUTER)) == NULLBUF) return; sendupdate(bp,1,dest); } /* send an update to all adjacencies on an RSPF interface */ static void sendtoall(bp,nodecnt,riface) struct mbuf *bp; int nodecnt; /* number of reporting nodes in update */ struct rspfiface *riface; /* interface to sent to */ { struct rspfadj *adj; struct mbuf *wbp; int broad; for(broad = 0, adj = Adjs; adj != NULLADJ; adj = adj->next) /* If adj->seq is 0 we have never received an RRH from the * adjacency, and if there is no stored routing update, then * it is not known if the adjacency understands RSPF. */ if((adj->seq != 0 || rr_lookup(adj->addr) != NULLRROUTER) && riface == rtif_lookup(adj->addr)) { if((adj->tos & RELIABILITY) && !(adj->tos & DELAY)) { if(dup_p(&wbp,bp,0,len_p(bp)) != len_p(bp)) { free_p(wbp); continue; } sendupdate(wbp,nodecnt,adj->addr); /* private copy */ } else ++broad; /* send to broadcast IP address instead */ } if(broad != 0) if(dup_p(&wbp,bp,0,len_p(bp)) != len_p(bp)) free_p(wbp); else sendupdate(wbp,nodecnt,riface->iface->broadcast); free_p(bp); } /* This function sends a routing update to the adjacencies that we have * recevied RRH's from. */ static int sendupdate(bp,nodecnt,addr) struct mbuf *bp; /* Full packet, except for the packet header */ int nodecnt; /* Number of reporting nodes in the packet */ int32 addr; /* Station to send update to */ { struct rspfadj *adj; struct mbuf *tmp; int tos = 0; /* See if we are sending to a known adjacency, in use its TOS in * that case. */ for(adj = Adjs; adj != NULLADJ; adj = adj->next) if(adj->addr == addr) { tos = adj->tos; break; } if((tmp = fragmenter(bp,nodecnt,ip_mtu(addr) - IPLEN)) == NULLBUF) return -1; while((bp = dequeue(&tmp)) != NULLBUF){ rspfcsum(&bp,addr); /* Calculate the checksum */ ++Rspf_stat.updateout; ip_send(INADDR_ANY,addr,RSPF_PTCL,INET_CTL | tos,2,bp,0,0,0); } return 0; } /* Fragment a large mbuf if necessary into packets of maximum mtu bytes. * Each packet is prepended a RSPF routing update header, without the checksum. */ static struct mbuf * fragmenter(bp,nodes,mtu) struct mbuf *bp; /* packet to send, without packet header */ int nodes; /* The number of reporting nodes in the routing update */ int16 mtu; /* The maximum transmission unit */ { struct rspfnodeh nodeh; struct rspflinkh linkh; struct rspfpacketh pkth; struct mbuf *tbp, *tmp, *bpq = NULLBUF; int n, nodecnt, linkcnt, adjcnt, nodemax, sync; char *cp, fragn = 1; if(mtu < RSPFPKTLEN + RSPFNODELEN || bp == NULLBUF) { free_p(bp); return NULLBUF; } ++Envelopeid; nodemax = nodes; /* total number of nodes in envelope */ nodecnt = nodes; /* nodes left to packetize */ linkcnt = adjcnt = 0; while(len_p(bp) != 0){ n = min(mtu,len_p(bp)+RSPFPKTLEN); /* length of this packet */ n -= RSPFPKTLEN; tbp = NULLBUF; sync = 0; if(adjcnt){ tbp = ambufw(min(adjcnt*5,n/5*5)); tbp->cnt = tbp->size; cp = tbp->data; } while(n > 0){ while(adjcnt){ if((n -= 5) < 0) break; pullup(&bp,cp,5); cp += 5; adjcnt--; } if(linkcnt && n > 0){ if((n -= RSPFLINKLEN) < 0) break; ntohrspflink(&linkh,&bp); adjcnt = linkh.adjn; tmp = htonrspflink(&linkh,NULLBUF); append(&tbp,tmp); tmp = ambufw(min(5*adjcnt,n/5*5)); tmp->cnt = tmp->size; cp = tmp->data; append(&tbp,tmp); linkcnt--; continue; } if(nodecnt && linkcnt == 0 && n > 0){ if((n -= RSPFNODELEN) < 0) break; if(nodecnt == nodes) /* Set the sync octet */ sync = len_p(tbp) + 4; ntohrspfnode(&nodeh,&bp); linkcnt = nodeh.links; tmp = htonrspfnode(&nodeh,NULLBUF); append(&tbp,tmp); nodecnt--; } } pkth.version = RSPF_VERSION; /* The version number */ pkth.type = RSPF_FULLPKT; /* The packet type */ pkth.fragn = fragn++; /* The fragment number */ pkth.fragtot = 0; /* The total number of fragments */ pkth.csum = 0; /* The checksum */ pkth.sync = sync < 256 ? sync : 0; /* The sync octet */ pkth.nodes = nodemax; /* The number of nodes in envelope */ pkth.envid = Envelopeid; /* The envelope-ID */ tmp = htonrspf(&pkth,tbp); /* add packet header */ enqueue(&bpq,tmp); /* add packet to chain */ nodes = nodecnt; /* number of nodes left */ } free_p(bp); for(tbp = bpq; tbp != NULLBUF; tbp = tbp->anext) *(tbp->data + 3) = len_q(bpq); /* Set the fragment total counter */ return bpq; } /* Calculate the checksum on an RSPF routing update packet */ static void rspfcsum(bpp,dest) struct mbuf **bpp; int32 dest; { struct pseudo_header ph; int16 checksum; ph.length = len_p(*bpp); ph.source = locaddr(dest); ph.dest = dest; ph.protocol = RSPF_PTCL; if((checksum = cksum(&ph,*bpp,ph.length)) == 0) checksum = 0xffffffff; /* This assumes that the checksum really is at this position */ put16((*bpp)->data+4,checksum); } /* This function creates our own routing update and returns it in an mbuf */ struct mbuf * makeownupdate(dest,new) int32 dest; /* Address of a station that will get this update */ int new; /* True if the sequence number should be incremented */ { struct rspfadj *adj; struct rspflinkh linkh; struct rspfnodeh nodeh; struct rspfiface *riface, rifdefault; struct mbuf *bp = NULLBUF, *tbp, *tmp; struct route *rp; int i, adjcnt, lnkcnt, bits; int32 prev, low, cur; /* Set default values to apply to non-RSPF interfaces */ rifdefault.horizon = 32; rifdefault.erp = 0; rifdefault.quality = 0; /* Our adjacencies has to be sorted into groups of the same horizon, * ERP factor and cost. This is done by combining these numbers into a * single one, modulo 256 and take the lowest number first. */ low = 0; lnkcnt = 0; for(;;){ prev = low; low = 255*65536+255*256+255; for(adj = Adjs; adj != NULLADJ; adj = adj->next) /* Include all adjacecies that have been or are in OK state * in the update. Bad adjacencies are also included to give * them a chance to recover. Hopelessly Bad adjacencies are * eventually deleted elsewhere. */ if(adj->okcnt != 0 && (riface = rtif_lookup(adj->addr)) != NULLRIFACE) { cur = riface->horizon*65536+riface->erp*256+adj->cost; if(cur > prev && cur < low) low = cur; } /* Add any manual public, 1-31 bit specific routes. * Use the route metric only if it is greater than the default * quality to lessen a possible "wormhole" effect. */ for(bits = 1; bits <= 31; bits++) for(i = 0; i < HASHMOD; i++) for(rp = Routes[bits-1][i]; rp != NULLROUTE; rp = rp->next) if(!(rp->flags & RTPRIVATE) && !dur_timer(&rp->timer)) { if((riface = rtif_lookup(rp->target)) == NULLRIFACE) riface = &rifdefault; cur = riface->horizon*65536+riface->erp*256+ (rp->metric > riface->quality ? rp->metric : riface->quality); if(cur > prev && cur < low) low = cur; } /* Add any 32 bit routes on interfaces not using RSPF */ for(i = 0; i < HASHMOD; i++) for(rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next) if(!(rp->flags & RTPRIVATE) && rtif_lookup(rp->target) == NULLRIFACE) { cur = rifdefault.horizon*65536+rifdefault.erp*256+ (rp->metric > rifdefault.quality ? rp->metric : rifdefault.quality); if(cur > prev && cur < low) low = cur; } /* Add the default route */ if((rp = rt_blookup(0,0)) != NULLROUTE && !(rp->flags & RTPRIVATE) && !dur_timer(&rp->timer)) { if((riface = rtif_lookup(0)) == NULLRIFACE) riface = &rifdefault; cur = riface->horizon*65536+riface->erp*256+ (rp->metric > riface->quality ? rp->metric : riface->quality); if(cur > prev && cur < low) low = cur; } if(low == 255*65536+255*256+255) /* All done */ break; /* now start adding the routes */ adjcnt = 0; tbp = NULLBUF; for(adj = Adjs; adj != NULLADJ; adj = adj->next) if(adj->okcnt != 0 && (riface = rtif_lookup(adj->addr)) != NULLRIFACE) if(riface->horizon*65536+riface->erp*256+adj->cost == low){ pushadj(&tbp,adj->addr,32); adjcnt++; } for(bits = 1; bits <= 31; bits++) for(i = 0; i < HASHMOD; i++) for(rp = Routes[bits-1][i]; rp != NULLROUTE; rp = rp->next) if(!(rp->flags & RTPRIVATE) && !dur_timer(&rp->timer)){ if((riface = rtif_lookup(rp->target)) == NULLRIFACE) riface = &rifdefault; /* Manually entered local routes only */ if(riface->horizon*65536+riface->erp*256+ (rp->metric > riface->quality ? rp->metric : riface->quality) == low){ pushadj(&tbp,rp->target,bits); adjcnt++; } } for(i = 0; i < HASHMOD; i++) /* 32 bit specific routes */ for(rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next) if(!(rp->flags & RTPRIVATE) && rtif_lookup(rp->target) == NULLRIFACE) if(rifdefault.horizon*65536+rifdefault.erp*256+ (rp->metric > rifdefault.quality ? rp->metric : rifdefault.quality) == low){ pushadj(&tbp,rp->target,bits); adjcnt++; } /* Add the default route */ if((rp = rt_blookup(0,0)) != NULLROUTE && !(rp->flags & RTPRIVATE) && !dur_timer(&rp->timer)) { if((riface = rtif_lookup(0)) == NULLRIFACE) riface = &rifdefault; if(riface->horizon*65536+riface->erp*256+ (rp->metric > riface->quality ? rp->metric : riface->quality) == low){ pushadj(&tbp,0,0); adjcnt++; } } if(adjcnt != 0){ /* Prepend the link header */ linkh.horizon = ((low >> 16) & 255);/* Horizon value */ linkh.erp = ((low >> 8) & 255); /* ERP factor */ linkh.cost = (low & 255); /* Link cost */ linkh.adjn = adjcnt; /* Number of adjacencies */ tmp = htonrspflink(&linkh,tbp); append(&bp,tmp); lnkcnt++; } } /* Prepend the node header */ if(lnkcnt != 0){ /* Set our address to the IP address used on the destinations * interface. */ if(dest == INADDR_ANY || (riface = rtif_lookup(dest)) == NULLRIFACE) nodeh.addr = Ip_addr; else nodeh.addr = riface->iface->addr; if(new){ /* increase sequence number, clear subseq. number */ if(Rspfseq == 32768 - 2 || Rspfseq == -32768 + 1) Rspfseq = 0; /* wrap around */ else ++Rspfseq; Rspfsubseq = 0; } nodeh.seq = Rspfseq; nodeh.subseq = 0; nodeh.links = lnkcnt; return htonrspfnode(&nodeh,bp); } else { free_p(bp); return NULLBUF; } } /* Prepends an adjacency to bpp. Allocates bpp in large chunk for efficency */ static void pushadj(bpp,addr,bits) struct mbuf **bpp; int32 addr; int bits; { if(bpp == NULLBUFP) return; if(*bpp == NULLBUF) { *bpp = ambufw(60); /* good for 12 adjacencies */ (*bpp)->data += 55; (*bpp)->cnt = 5; } else *bpp = pushdown(*bpp,5); *(*bpp)->data = bits; put32((*bpp)->data+1,addr); } /* This function returns the latest routing update in network fromat from * the adjacency denoted by addr. */ static struct mbuf * makeadjupdate(addr,rr) int32 addr; struct rspfrouter *rr; /* pointer to stored routing entry, if known */ { struct mbuf *tmp, *tmp2, *tmp3, *bp = NULLBUF; struct rspfnodeh nodeh; struct rspflinkh linkh; int linkcnt = 0; if(rr == NULLRROUTER && (rr = rr_lookup(addr)) == NULLRROUTER) return NULLBUF; if(dup_p(&tmp,rr->data,0,len_p(rr->data)) != len_p(rr->data)) { free_p(tmp); return NULLBUF; } ntohrspfnode(&nodeh,&tmp); /* Get the node header */ while(nodeh.links--){ ntohrspflink(&linkh,&tmp); /* Decrement and check the horizon value */ if(--linkh.horizon > 0){ /* Duplicate the adjacencies */ if(dup_p(&tmp2,tmp,0,5*linkh.adjn) != 5*linkh.adjn){ free_p(tmp); free_p(tmp2); free_p(bp); return NULLBUF; } /* Prepend the link header */ tmp3 = htonrspflink(&linkh,tmp2); append(&bp,tmp3); linkcnt++; } pullup(&tmp,NULLCHAR,5*linkh.adjn); /* Skip the adjacencies */ } free_p(tmp); if(linkcnt == 0){ /* No links at all? */ free_p(bp); return NULLBUF; } nodeh.subseq = rr->subseq; nodeh.links = linkcnt; /* Prepend the node header */ return htonrspfnode(&nodeh,bp); } /* Returns 1 if sequence number a is newer than b. Sequence numbers start * at -32768 + 1 and then continues with 0 and the positive integer numbers * until reaching 32768 - 2 after which they continue with 0. * Algorithm taken from RFC-1131 but fixed bug when a or b is 0. */ static int isnewer(a,b) short a,b; { if((b < 0 && a > b) || (a >= 0 && b >= 0 && /* bug corrected here */ (((32768 - 1)/2 > (a-b) && (a-b) > 0) || (a-b) < -(32768 - 1)/2))) return 1; return 0; } /* Reassemble possibly fragmented packets into a single large one */ static struct mbuf * rspfreasm(bp,rph,addr) struct mbuf *bp; /* Routing update packet without packet header */ struct rspfpacketh *rph; /* Packet header */ int32 addr; /* Address of station we got the packet from */ { union rspf rspf; struct rspfreasm *re, *rtmp; struct mbuf *tbp, *bp1, *bp2; for(re = Rspfreasmq; re != NULLRREASM; re = re->next) if(re->addr == addr){ /* found another fragment */ if(dup_p(&tbp,re->data,0,RSPFPKTLEN) != RSPFPKTLEN) { free_p(tbp); free_p(bp); return NULLBUF; } ntohrspf(&rspf,&tbp); /* get its packet header */ if(rph->envid != rspf.pkthdr.envid) { del_reasm(re); /* an obsolete entry, delete it */ break; } /* Now try to find a place where this fragment fits in the chain */ bp1 = re->data; bp2 = NULLBUF; while(rph->fragn > rspf.pkthdr.fragn && bp1->anext != NULLBUF){ bp2 = bp1; bp1 = bp1->anext; if(dup_p(&tbp,bp1,0,RSPFPKTLEN) != RSPFPKTLEN) { free_p(bp); free_p(tbp); return NULLBUF; } ntohrspf(&rspf,&tbp); } if(rspf.pkthdr.fragn == rph->fragn) { free_p(bp); return NULLBUF; /* We already had this one */ } bp = htonrspf(rph,bp); /* Put the packet header back on */ /* Insert the fragment at the right place in the chain */ if(rph->fragn > rspf.pkthdr.fragn){ bp1->anext = bp; bp->anext = NULLBUF; } else { if(bp2 != NULLBUF) bp2->anext = bp; else re->data = bp; bp->anext = bp1; } if(len_q(re->data) == rspf.pkthdr.fragtot){ bp1 = NULLBUF; /* we have all the fragments */ while((bp2 = dequeue(&re->data)) != NULLBUF){ pullup(&bp2,NULLCHAR,RSPFPKTLEN); /* strip the headers */ append(&bp1,bp2); /* and form a single packet */ } del_reasm(re); stop_timer(&Rspfreasmt); reasmtimeout(NULL); /* restarts timer if necessary */ return bp1; /* return the completed packet */ } re->time = Clock; /* Update the timestamp */ goto timstart; /* We have to wait for fragments */ } /* At this point we know that there is no matching entry in the reassembly queue (any more) */ if(rph->fragtot == 1) /* Simple case, an un-fragmented packet */ return bp; tbp = htonrspf(rph,bp); /* Put the packet header back on */ rtmp = (struct rspfreasm *) callocw(1,sizeof(struct rspfreasm)); /* The values are filled in */ rtmp->addr = addr; rtmp->time = Clock; rtmp->data = tbp; rtmp->next = Rspfreasmq; Rspfreasmq = rtmp; timstart: /* Start the timer if needed */ if(!run_timer(&Rspfreasmt)){ Rspfreasmt.func = reasmtimeout; Rspfreasmt.arg = NULL; set_timer(&Rspfreasmt,RSPF_RTIME*1000); /* The reassembly timeout */ start_timer(&Rspfreasmt); } return NULLBUF; } /* Delete a reassembly descriptor from the queue */ static void del_reasm(re) struct rspfreasm *re; { struct rspfreasm *r, *prev = NULLRREASM; for(r = Rspfreasmq; r != NULLRREASM; prev = r, r = r->next) if(r == re){ free_q(&re->data); if(prev != NULLRREASM) prev->next = re->next; else Rspfreasmq = re->next; free((char *)re); break; } } /* When the reassembly timer times out, this function tries to make use of * any fragments in the reassembly queue. */ static void reasmtimeout(t) void *t; { union rspf rspf; struct rspfreasm *re; struct mbuf *bp, *tbp; int last = 0; int32 low; re = Rspfreasmq; while(re != NULLRREASM) if((Clock - re->time) >= RSPF_RTIME*1000/MSPTICK){ /* Try to use what we have */ bp = NULLBUF; while((tbp = dequeue(&re->data)) != NULLBUF){ ntohrspf(&rspf,&tbp); if(rspf.pkthdr.fragn != (last+1)){ /* a missing fragment */ if(bp != NULLBUF) update_in(bp,re->addr); bp = NULLBUF; if(rspf.pkthdr.sync != 0) pullup(&tbp,NULLCHAR,rspf.pkthdr.sync - 4); else { /* no sync possible in this fragment */ free_p(tbp); continue; } } append(&bp,tbp); last = rspf.pkthdr.fragn; } if(bp != NULLBUF) update_in(bp,re->addr); del_reasm(re); re = Rspfreasmq; /* start over again */ } else re = re->next; /* Find the oldest fragment and restart the reassembly timer */ low = 0; for(re = Rspfreasmq; re != NULLRREASM; re = re->next) if(re->time < low || low == 0) low = re->time; if(low){ Rspfreasmt.start = RSPF_RTIME*1000/MSPTICK - Clock + low; if(Rspfreasmt.start > 0) /* just to be safe */ start_timer(&Rspfreasmt); } } /* Handle incoming routing updates (a reassembled envelope) */ static void update_in(bp,addr) struct mbuf *bp; /* Reassembled data packet, without packet header */ int32 addr; /* Senders address (in host order) */ { struct rspfnodeh nodeh; struct rspflinkh linkh; struct rspfadj *adj; struct mbuf *tbp, *tmp, *b; int linkcnt = 0, adjcnt = 0; int16 offset = 0; tbp = b = NULLBUF; /* Check to see if the sender is an adjacency */ for(adj = Adjs; adj != NULLADJ; adj = adj->next) if(adj->addr == addr) break; /* One may argue that updates from non-adjacencies should not be * accepted since they will not contribute to the routing table. * But it might happen that the sender will very shortly become an * adjacency, and then its routing update will come handy. By increasing * Keeprouter, routing updates from disjoint routers will not be not be * purged when makeroutes() is called this time. */ if(adj == NULLADJ) { ++Rspf_stat.noadjupdate; Keeprouter += 2; } else psignal(adj,1); /* alert anyone waiting for the update */ while(offset < len_p(bp)){ if(adjcnt){ if(dup_p(&tmp,bp,offset,5) == 5){ append(&tbp,tmp); offset += 5; adjcnt--; continue; } else break; } if(tbp != NULLBUF){ tmp = htonrspflink(&linkh,tbp); append(&b,tmp); tbp = NULLBUF; } if(linkcnt){ if(dup_p(&tbp,bp,offset,RSPFLINKLEN) == RSPFLINKLEN){ ntohrspflink(&linkh,&tbp); adjcnt = linkh.adjn; offset += RSPFLINKLEN; linkcnt--; continue; } else break; } if(b != NULLBUF){ tmp = htonrspfnode(&nodeh,b); node_in(tmp,addr,1); /* a full router update */ b = NULLBUF; } if(dup_p(&tmp,bp,offset,RSPFNODELEN) == RSPFNODELEN){ ntohrspfnode(&nodeh,&tmp); linkcnt = nodeh.links; offset += RSPFNODELEN; } else { free_p(bp); free_p(tmp); return; } } if(tbp != NULLBUF){ /* adjust the adjacency counter in the link header */ linkh.adjn -= adjcnt; tmp = htonrspflink(&linkh,tbp); append(&b,tmp); } /* adjust the link counter in the node header */ nodeh.links -= linkcnt; tmp = htonrspfnode(&nodeh,b); free_p(bp); if(linkcnt || adjcnt) node_in(tmp,addr,0); /* a partial router update */ else node_in(tmp,addr,1); } static void node_in(bp,addr,full) struct mbuf *bp; /* A single update, starting with the node header */ int32 addr; /* Address of station we got packet from */ int full; /* False if we got a partial update */ { struct mbuf *tbp; struct rspfnodeh nodeh, rnodeh; struct rspfrouter *rr; if(dup_p(&tbp,bp,0,RSPFNODELEN) != RSPFNODELEN) { free_p(bp); free_p(tbp); return; } ntohrspfnode(&nodeh,&tbp); if(ismyaddr(nodeh.addr)){ /* If another station thinks our routing update sequence number is * larger than it really is, this might be because we have had * a fast system reset and routing updates from the old "epoch" * are still present in the network. */ if(isnewer(nodeh.seq,Rspfseq)) { Rspfseq = nodeh.seq + 1; /* Catch up */ if(nodeh.seq == 32768 - 2 || nodeh.seq == -32768 + 1) Rspfseq = 0; /* Wrap around */ sendonerspf(nodeh.addr,addr); /* Send him the latest packet */ } free_p(bp); /* We already know our own adjacencies! */ return; } if((rr = rr_lookup(nodeh.addr)) != NULLRROUTER) { if(dup_p(&tbp,rr->data,0,RSPFNODELEN) != RSPFNODELEN) { free_p(bp); free_p(tbp); return; } ntohrspfnode(&rnodeh,&tbp); if(nodeh.seq == rnodeh.seq && nodeh.subseq <= rr->subseq){ free_p(bp); return; /* We already have this one */ } if(isnewer(rnodeh.seq,nodeh.seq)){ /* Send him the latest packet */ sendonerspf(nodeh.addr,addr); free_p(bp); ++Rspf_stat.oldreport; return; } if(nodeh.subseq > rr->subseq && nodeh.seq == rnodeh.seq){ rr->subseq = nodeh.subseq; partialupdate(rr,bp); makeroutes(); return; } if(isnewer(nodeh.seq,rnodeh.seq) && !full){ partialupdate(rr,bp); makeroutes(); /* Send a "poll" packet */ --nodeh.seq; nodeh.subseq = 0; nodeh.links = 0; tbp = htonrspfnode(&nodeh,NULLBUF); sendupdate(tbp,1,addr); ++Rspf_stat.outpolls; return; } } else { rr = (struct rspfrouter *) callocw(1,sizeof(struct rspfrouter)); rr->next = Rspfrouters; Rspfrouters = rr; } free_p(rr->data); rr->data = bp; rr->subseq = nodeh.subseq; rr->time = Clock; rr->sent = 0; makeroutes(); return; } /* Return the matching RSPF route entry for addr (in host order) */ static struct rspfrouter * rr_lookup(addr) int32 addr; { struct rspfrouter *rr; for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next) /* this assumes that the first word of the header is the address */ if(rr->data != NULLBUF && get32(rr->data->data) == addr) return rr; return NULLRROUTER; } /* Delete the route entry for address addr */ static void rr_delete(addr) int32 addr; { struct rspfrouter *rr, *prev = NULLRROUTER; for(rr = Rspfrouters; rr != NULLRROUTER; prev = rr, rr = rr->next) /* this assumes that the first word of the header is the address */ if(rr->data != NULLBUF && get32(rr->data->data) == addr) { if(prev != NULLRROUTER) prev->next = rr->next; else Rspfrouters = rr->next; free_p(rr->data); free((char *)rr); return; } } /* Handle incoming partial routing updates. Adjacencies from bp will be * merged into rr->data */ static void partialupdate(rr,bp) struct rspfrouter *rr; /* current node entry in routing table */ struct mbuf *bp; /* data packet, starting with node header */ { struct rspflinkh linkh, rlinkh; struct rspfnodeh rnodeh; struct mbuf *wbp, *tbp, *tmp, *b; int adjcnt = 0, radjcnt, rlinkcnt = 0, bits, rbits, added = 0; int32 addr, raddr; rlinkh.adjn = 0; rr->time = Clock; rr->sent = 0; /* Make a working copy of the stored routing update */ if(dup_p(&wbp,rr->data,0,len_p(rr->data)) != len_p(rr->data)) { free_p(wbp); free_p(bp); return; } ntohrspfnode(&rnodeh,&wbp); pullup(&bp,NULLCHAR,RSPFNODELEN); /* Strip off the node header */ while(len_p(bp) > 0) if(adjcnt == 0) { if(ntohrspflink(&linkh,&bp) == -1) { free_p(wbp); free_p(bp); return; } adjcnt = linkh.adjn; } else { bits = PULLCHAR(&bp); /* get one adjacency to merge */ if(pullup(&bp,(char *)&addr,4) != 4) { free_p(wbp); free_p(bp); return; } addr = get32((char *)&addr); /* convert to host order */ --adjcnt; radjcnt = 0; b = tbp = NULLBUF; for(;;) { /* search through stored update */ if(radjcnt == 0 || len_p(wbp) == 0) { if(tbp != NULLBUF){ rlinkh.adjn -= radjcnt; tmp = htonrspflink(&rlinkh,tbp); ++rlinkcnt; append(&b,tmp); tbp = NULLBUF; } if(len_p(wbp) == 0) break; } if(radjcnt == 0) { ntohrspflink(&rlinkh,&wbp); radjcnt = rlinkh.adjn; if(rlinkh.horizon == linkh.horizon && rlinkh.cost == linkh.cost && rlinkh.erp == linkh.erp) { pushadj(&tbp,addr,bits); ++rlinkh.adjn; added = 1; } } else { rbits = PULLCHAR(&wbp); raddr = pull32(&wbp); --radjcnt; if(bits != rbits || addr != raddr) pushadj(&tbp,raddr,rbits); /* Put it back */ else --rlinkh.adjn; /* deleted one adjacency */ } } wbp = b; /* wbp now keeps link headers and adjacencies */ if(linkh.cost < 255 && !added){ /* Append the new link */ ++rnodeh.links; /* We will add one extra link */ tmp = ambufw(5); *tmp->data = bits; put32(tmp->data+1,addr); tmp->cnt = tmp->size; tbp = htonrspflink(&linkh,tmp); append(&wbp,tbp); } added = 0; } free_p(rr->data); rnodeh.links = rlinkcnt; rr->data = htonrspfnode(&rnodeh,wbp); } /* The shortest path first algorithm */ static void makeroutes() { int bits, i, low, adjcnt; struct mbuf *bp; struct route *rp, *rp2, *saved[HASHMOD]; struct rspfadj *adj, *lowadj, *gateway; char *lowp, *r; int32 lowaddr; struct rspflinkh linkh; struct rspfrouter *rr, *rrprev; if(Keeprouter) /* if false, purge unreachable router entries */ --Keeprouter; /* Before we change anything in the routing table, we have to save * each local adjacencies riface pointer */ for(adj = Adjs; adj != NULLADJ; adj = adj->next) adj->scratch = (void *) rtif_lookup(adj->addr); /* Remove all non-manual routes */ for(bits = 1; bits <= 32; bits++) for(i = 0; i < HASHMOD; i++) for(rp = Routes[bits-1][i]; rp != NULLROUTE; rp = rp->next) if(dur_timer(&rp->timer) != 0) rt_drop(rp->target,bits); if((rp = rt_blookup(0,0)) != NULLROUTE && dur_timer(&rp->timer) != 0) rt_drop(0,0); /* delete non-manual default route */ /* Temporarily remove all 32-bit specific manual routes. This will make * it possible to prevent loops in findlowroute() */ for(i = 0; i < HASHMOD; i++) { saved[i] = Routes[31][i]; Routes[31][i] = NULLROUTE; } for(;;) { lowadj = NULLADJ; lowp = NULLCHAR; low = 255; for(adj = Adjs; adj != NULLADJ; adj = adj->next){ if(adj->scratch == NULL) continue; /* skip unreachable adjacency */ if(!adj->added){ if(adj->cost <= low){ low = adj->cost; lowadj = adj; lowp = NULLCHAR; } } else if((r = findlowroute(adj->addr,&low,adj->cost,&lowaddr,&bits)) != NULLCHAR) { lowp = r; gateway = adj; lowadj = NULLADJ; } } if(lowadj != NULLADJ){ lowadj->added++; rp = rt_add(lowadj->addr,32,0, ((struct rspfiface *)lowadj->scratch)->iface, (int32)lowadj->cost,0,0); /* set the timer to a dummy value. This makes it possible to * distinguish between manual and RSPF-generated routes. * The timer is never started however since RSPF handles the * expiration of routes itself. */ set_timer(&rp->timer,MSPTICK); continue; } if(lowp != NULLCHAR){ /* Check if we already have this one */ rp = rt_blookup(lowaddr,bits); if((rp == NULLROUTE || (rp != NULLROUTE && rp->metric > (int32) low)) && !ismyaddr(lowaddr)) { /* This is a new route, or a route with strict lower cost than * the previous route (possible only if it was manual) */ rp = rt_add(lowaddr,bits,gateway->addr, ((struct rspfiface *)gateway->scratch)->iface, (int32)low,0,0); set_timer(&rp->timer,MSPTICK); /* a dummy value */ } *lowp |= 128; /* mark the route as added in any case */ } else break; /* no more routes */ } /* Add the saved 32 bit routes, if there isn't now a better route */ for(i = 0; i < HASHMOD; i++) { rp = saved[i]; while(rp != NULLROUTE) { rp2 = rt_blookup(rp->target,32); if(rp2 == NULLROUTE || (rp2 != NULLROUTE && rp2->metric >= rp->metric)) { rp2 = rt_add(rp->target,32,rp->gateway,rp->iface,rp->metric, 0,rp->flags & RTPRIVATE); rp2->uses = rp->uses; } rp2 = rp->next; free((char *)rp); rp = rp2; } } /* Reset all flags */ for(adj = Adjs; adj != NULLADJ; adj = adj->next) { adj->added = 0; adj->scratch = NULL; } for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next){ i = len_p(rr->data) - RSPFNODELEN; /* jump past the node header */ if(dup_p(&bp,rr->data,RSPFNODELEN,i) != i) { free_p(bp); continue; } adjcnt = 0; while(i > 0){ if(adjcnt){ if(!Keeprouter && (*bp->data & 128) == 0) { /* This router has an adjacency that was not added. That * means that the router is unreachable. Mark the * stored routing update for deletion. */ free_p(bp); free_p(rr->data); rr->data = NULLBUF; /* indicates disposal */ break; } *bp->data &= ~128; /* Clear the "added" bit */ pullup(&bp,NULLCHAR,5); i -= 5; --adjcnt; continue; } ntohrspflink(&linkh,&bp); adjcnt = linkh.adjn; i -= RSPFLINKLEN; } } if(Keeprouter) /* nothing more to do */ return; /* Delete any routers that were discovered as being unreachable */ rrprev = NULLRROUTER; rr = Rspfrouters; for(;;) { for(rrprev = NULLRROUTER, rr = Rspfrouters; rr != NULLRROUTER; rrprev = rr, rr = rr->next) if(rr->data == NULLBUF) { if(rrprev != NULLRROUTER) rrprev->next = rr->next; else Rspfrouters = rr->next; free((char *)rr); break; } if(rr == NULLRROUTER) break; } } /* Find a route from addr with the lowest cost. Returns a pointer to the * buffer that keeps the significant bit count of the selected route. */ static char * findlowroute(addr,low,add,resaddr,resbits) int32 addr; /* The node whose routes will be examined */ int *low; /* Lowest cost so far */ int add; /* Cost of this node */ int32 *resaddr; /* Resulting route stored here */ int *resbits; /* Significant bits of resulting route */ { struct mbuf *bp; struct rspfrouter *rr; struct rspflinkh linkh; struct route *rp; char *r, *retval = NULLCHAR; int adjcnt = 0; linkh.cost = 0; if((rr = rr_lookup(addr)) == NULLRROUTER) return NULLCHAR; if((rp = rt_blookup(addr,32)) != NULLROUTE && rp->metric < add) return NULLCHAR; /* already added this one, no loops thanks */ if(dup_p(&bp,rr->data,RSPFNODELEN,len_p(rr->data) - RSPFNODELEN) != len_p(rr->data) - RSPFNODELEN) { free_p(bp); return NULLCHAR; } while(len_p(bp) > 0){ if(adjcnt){ if(*bp->data & 128) { (void) PULLCHAR(&bp); if((r = findlowroute(pull32(&bp),low,add+linkh.cost,resaddr, resbits)) != NULLCHAR) retval = r; } else { *low = add + linkh.cost; retval = bp->data; *resbits = PULLCHAR(&bp); *resaddr = pull32(&bp); pullup(&bp,NULLCHAR,5*(adjcnt-1)); adjcnt = 1; /* No need to check the rest of this link */ } --adjcnt; continue; } ntohrspflink(&linkh,&bp); if((add + linkh.cost) <= *low) adjcnt = linkh.adjn; else pullup(&bp,NULLCHAR,5*linkh.adjn); } return retval; }