sap_tables.c revision 27244
111820Sjulian/* 211820Sjulian * Copyright (c) 1995 John Hay. All rights reserved. 311820Sjulian * 411820Sjulian * Redistribution and use in source and binary forms, with or without 511820Sjulian * modification, are permitted provided that the following conditions 611820Sjulian * are met: 711820Sjulian * 1. Redistributions of source code must retain the above copyright 811820Sjulian * notice, this list of conditions and the following disclaimer. 911820Sjulian * 2. Redistributions in binary form must reproduce the above copyright 1011820Sjulian * notice, this list of conditions and the following disclaimer in the 1111820Sjulian * documentation and/or other materials provided with the distribution. 1211820Sjulian * 3. All advertising materials mentioning features or use of this software 1311820Sjulian * must display the following acknowledgement: 1411820Sjulian * This product includes software developed by John Hay. 1511820Sjulian * 4. Neither the name of the author nor the names of any co-contributors 1611820Sjulian * may be used to endorse or promote products derived from this software 1711820Sjulian * without specific prior written permission. 1811820Sjulian * 1911820Sjulian * THIS SOFTWARE IS PROVIDED BY John Hay AND CONTRIBUTORS ``AS IS'' AND 2011820Sjulian * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2111820Sjulian * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2211820Sjulian * ARE DISCLAIMED. IN NO EVENT SHALL John Hay OR CONTRIBUTORS BE LIABLE 2311820Sjulian * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2411820Sjulian * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2511820Sjulian * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2611820Sjulian * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2711820Sjulian * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2811820Sjulian * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2911820Sjulian * SUCH DAMAGE. 3011820Sjulian * 3127244Sjhay * $Id: sap_tables.c,v 1.4 1997/07/01 00:33:41 bde Exp $ 3211820Sjulian */ 3311820Sjulian 3411820Sjulian#include "defs.h" 3511820Sjulian#include <string.h> 3611820Sjulian#include <stdlib.h> 3711820Sjulian 3811820Sjulian#define FIXLEN(s) { if ((s)->sa_len == 0) (s)->sa_len = sizeof (*(s));} 3911820Sjulian 4011820Sjuliansap_hash sap_head[SAPHASHSIZ]; 4111820Sjulian 4211820Sjulianvoid 4311820Sjuliansapinit(void) 4411820Sjulian{ 4511820Sjulian int i; 4611820Sjulian 4711820Sjulian for (i=0; i<SAPHASHSIZ; i++) 4811820Sjulian sap_head[i].forw = sap_head[i].back = 4911820Sjulian (struct sap_entry *)&sap_head[i]; 5011820Sjulian} 5111820Sjulian 5211820Sjulian/* 5327244Sjhay * This hash use the first 14 letters of the ServName and the ServType 5411820Sjulian * to create a 32 bit hash value. 5511820Sjulian */ 5611820Sjulianint 5711820Sjuliansaphash(u_short ServType, char *ServName) 5811820Sjulian{ 5911820Sjulian int hsh, i; 6011820Sjulian char name[SERVNAMELEN]; 6111820Sjulian 6211820Sjulian bzero(name, SERVNAMELEN); 6311820Sjulian strncpy(name, ServName, SERVNAMELEN); 6411820Sjulian ServName = name; 6511820Sjulian 6611820Sjulian hsh = 0; 6711820Sjulian 6827244Sjhay#define SMVAL 33 6927244Sjhay 7027244Sjhay hsh = hsh * SMVAL + (ServType & 0xff); 7127244Sjhay hsh = hsh * SMVAL + (ServType >> 8); 7227244Sjhay 7327244Sjhay for (i=0;i<14;i++) { 7427244Sjhay hsh = hsh * SMVAL + *ServName++; 7511820Sjulian ServName++; 7611820Sjulian } 7711820Sjulian 7827244Sjhay#undef SMVAL 7927244Sjhay 8011820Sjulian return hsh; 8111820Sjulian} 8211820Sjulian 8311820Sjulian/* 8411820Sjulian * Look for an exact match on ServType and ServName. It is 8511820Sjulian * mostly used by the function that process SAP RESPONSE packets. 8611820Sjulian * 8711820Sjulian * A hash is created and used to index into the hash table. Then 8811820Sjulian * that list is walk through searching for a match. 8911820Sjulian * 9011820Sjulian * If no match is found NULL is returned. 9111820Sjulian */ 9211820Sjulianstruct sap_entry * 9311820Sjuliansap_lookup(u_short ServType, char *ServName) 9411820Sjulian{ 9511820Sjulian register struct sap_entry *sap; 9611820Sjulian register struct sap_hash *sh; 9711820Sjulian int hsh; 9811820Sjulian 9911820Sjulian hsh = saphash(ServType, ServName); 10011820Sjulian sh = &sap_head[hsh & SAPHASHMASK]; 10111820Sjulian 10211820Sjulian for(sap = sh->forw; sap != (sap_entry *)sh; sap = sap->forw) { 10311820Sjulian if ((hsh == sap->hash) && 10411820Sjulian (ServType == sap->sap.ServType) && 10511820Sjulian (strncmp(ServName, sap->sap.ServName, SERVNAMELEN) == 0)) { 10611820Sjulian return sap; 10711820Sjulian } 10811820Sjulian } 10911820Sjulian return NULL; 11011820Sjulian} 11111820Sjulian 11211820Sjulian/* 11311820Sjulian * This returns the nearest service of the specified type. If no 11411820Sjulian * suitable service is found or if that service is on the interface 11511820Sjulian * where the request came from, NULL is returned. 11611820Sjulian * 11711820Sjulian * When checking interfaces clones must be considered also. 11811820Sjulian * 11911820Sjulian * XXX TODO: 12011820Sjulian * Maybe we can use RIP tables to get the fastest service (ticks). 12111820Sjulian */ 12211820Sjulianstruct sap_entry * 12311820Sjuliansap_nearestserver(ushort ServType, struct interface *ifp) 12411820Sjulian{ 12511820Sjulian register struct sap_entry *sap; 12611820Sjulian register struct sap_entry *csap; 12711820Sjulian struct sap_hash *sh; 12811820Sjulian register struct sap_entry *best = NULL; 12911820Sjulian register int besthops = HOPCNT_INFINITY; 13011820Sjulian 13111820Sjulian sh = sap_head; 13211820Sjulian 13311820Sjulian for (; sh < &sap_head[SAPHASHSIZ]; sh++) 13411820Sjulian for(sap = sh->forw; sap != (sap_entry *)sh; sap = sap->forw) { 13511820Sjulian if (ServType != sap->sap.ServType) 13611820Sjulian continue; 13711820Sjulian if (ifp == sap->ifp) 13811820Sjulian continue; 13911820Sjulian 14011820Sjulian csap = sap->clone; 14111820Sjulian while (csap) { 14211820Sjulian if (ifp == csap->ifp) 14311820Sjulian /* 14411820Sjulian * I would have loved to use 14511820Sjulian * something else here. 14611820Sjulian */ 14711820Sjulian goto next; 14811820Sjulian csap = csap->clone; 14911820Sjulian } 15011820Sjulian 15111820Sjulian if (ntohs(sap->sap.hops) < besthops) { 15211820Sjulian best = sap; 15311820Sjulian besthops = ntohs(best->sap.hops); 15411820Sjulian } 15511820Sjuliannext:; 15611820Sjulian } 15711820Sjulian return best; 15811820Sjulian} 15911820Sjulian 16011820Sjulian/* 16111820Sjulian * Add a entry to the SAP table. 16211820Sjulian * 16311820Sjulian * If the malloc fail, the entry will silently be thrown away. 16411820Sjulian */ 16511820Sjulianvoid 16611820Sjuliansap_add(struct sap_info *si, struct sockaddr *from) 16711820Sjulian{ 16811820Sjulian register struct sap_entry *nsap; 16911820Sjulian register struct sap_hash *sh; 17011820Sjulian 17127244Sjhay if (ntohs(si->hops) == HOPCNT_INFINITY) 17227244Sjhay return; 17327244Sjhay 17411820Sjulian FIXLEN(from); 17511820Sjulian nsap = malloc(sizeof(struct sap_entry)); 17611820Sjulian if (nsap == NULL) 17711820Sjulian return; 17811820Sjulian 17911820Sjulian nsap->sap = *si; 18011820Sjulian nsap->source = *from; 18111820Sjulian nsap->clone = NULL; 18211820Sjulian nsap->ifp = if_ifwithnet(from); 18311820Sjulian nsap->state = RTS_CHANGED; 18411820Sjulian nsap->timer = 0; 18511820Sjulian nsap->hash = saphash(si->ServType, si->ServName); 18611820Sjulian 18711820Sjulian sh = &sap_head[nsap->hash & SAPHASHMASK]; 18811820Sjulian 18911820Sjulian insque(nsap, sh); 19027244Sjhay TRACE_SAP_ACTION("ADD", nsap); 19111820Sjulian} 19211820Sjulian 19311820Sjulian/* 19411820Sjulian * Change an existing SAP entry. If a clone exist for the old one, 19511820Sjulian * check if it is cheaper. If it is change tothe clone, otherwise 19611820Sjulian * delete all the clones. 19711820Sjulian */ 19811820Sjulianvoid 19911820Sjuliansap_change(struct sap_entry *sap, 20011820Sjulian struct sap_info *si, 20111820Sjulian struct sockaddr *from) 20211820Sjulian{ 20311820Sjulian struct sap_entry *osap = NULL; 20411820Sjulian 20511820Sjulian FIXLEN(from); 20627244Sjhay TRACE_SAP_ACTION("CHANGE FROM", sap); 20711820Sjulian /* 20811820Sjulian * If the hopcount (metric) is HOPCNT_INFINITY (16) it means that 20911820Sjulian * a service has gone down. We should keep it like that for 30 21011820Sjulian * seconds, so that it will get broadcast and then change to a 21111820Sjulian * clone if one exist. 21211820Sjulian */ 21311820Sjulian if (sap->clone && (ntohs(si->hops) != HOPCNT_INFINITY)) { 21411820Sjulian /* 21511820Sjulian * There are three possibilities: 21611820Sjulian * 1. The new path is cheaper than the old one. 21711820Sjulian * Free all the clones. 21811820Sjulian * 21911820Sjulian * 2. The new path is the same cost as the old ones. 22011820Sjulian * If it is on the list of clones remove it 22111820Sjulian * from the clone list and free it. 22211820Sjulian * 22311820Sjulian * 3. The new path is more expensive than the old one. 22411820Sjulian * Use the values of the first clone and take it 22511820Sjulian * out of the list, to be freed at the end. 22611820Sjulian */ 22711820Sjulian osap = sap->clone; 22811820Sjulian if (ntohs(osap->sap.hops) > ntohs(si->hops)) { 22911820Sjulian struct sap_entry *nsap; 23011820Sjulian 23111820Sjulian while (osap) { 23211820Sjulian nsap = osap->clone; 23327244Sjhay TRACE_SAP_ACTION("DELETE", osap); 23411820Sjulian free(osap); 23511820Sjulian osap = nsap; 23611820Sjulian } 23711820Sjulian sap->clone = NULL; 23811820Sjulian } else if (ntohs(osap->sap.hops) == ntohs(si->hops)) { 23911820Sjulian struct sap_entry *psap; 24011820Sjulian 24111820Sjulian psap = sap; 24211820Sjulian while (osap) { 24311820Sjulian if (equal(&osap->source, from)) { 24411820Sjulian psap->clone = osap->clone; 24527244Sjhay TRACE_SAP_ACTION("DELETE", osap); 24611820Sjulian free(osap); 24711820Sjulian osap = psap->clone; 24811820Sjulian } else { 24911820Sjulian psap = osap; 25011820Sjulian osap = osap->clone; 25111820Sjulian } 25211820Sjulian } 25311820Sjulian } else { 25411820Sjulian from = &osap->source; 25511820Sjulian si = &osap->sap; 25611820Sjulian sap->clone = osap->clone; 25711820Sjulian } 25811820Sjulian } 25911820Sjulian sap->sap = *si; 26011820Sjulian sap->source = *from; 26111820Sjulian sap->ifp = if_ifwithnet(from); 26211820Sjulian sap->state = RTS_CHANGED; 26311820Sjulian if (ntohs(si->hops) == HOPCNT_INFINITY) 26411820Sjulian sap->timer = EXPIRE_TIME; 26511820Sjulian else 26611820Sjulian sap->timer = 0; 26711820Sjulian 26827244Sjhay if (osap) { 26927244Sjhay TRACE_SAP_ACTION("DELETE", osap); 27011820Sjulian free(osap); 27127244Sjhay } 27227244Sjhay TRACE_SAP_ACTION("CHANGE TO", sap); 27311820Sjulian} 27411820Sjulian 27511820Sjulian/* 27611820Sjulian * Add a clone to the specified SAP entry. A clone is a different 27711820Sjulian * route to the same service. We must know about them when we use 27811820Sjulian * the split horizon algorithm. 27911820Sjulian * 28011820Sjulian * If the malloc fail, the entry will silently be thrown away. 28111820Sjulian */ 28211820Sjulianvoid 28311820Sjuliansap_add_clone(struct sap_entry *sap, 28411820Sjulian struct sap_info *clone, 28511820Sjulian struct sockaddr *from) 28611820Sjulian{ 28711820Sjulian register struct sap_entry *nsap; 28811820Sjulian register struct sap_entry *csap; 28911820Sjulian 29027244Sjhay if (ntohs(clone->hops) == HOPCNT_INFINITY) 29127244Sjhay return; 29227244Sjhay 29311820Sjulian FIXLEN(from); 29411820Sjulian nsap = malloc(sizeof(struct sap_entry)); 29511820Sjulian if (nsap == NULL) 29611820Sjulian return; 29711820Sjulian 29811820Sjulian if (ftrace) 29911820Sjulian fprintf(ftrace, "CLONE ADD %04.4X %s.\n", 30011820Sjulian ntohs(clone->ServType), 30111820Sjulian clone->ServName); 30211820Sjulian 30311820Sjulian nsap->sap = *clone; 30411820Sjulian nsap->source = *from; 30511820Sjulian nsap->clone = NULL; 30611820Sjulian nsap->ifp = if_ifwithnet(from); 30711820Sjulian nsap->state = RTS_CHANGED; 30811820Sjulian nsap->timer = 0; 30911820Sjulian nsap->hash = saphash(clone->ServType, clone->ServName); 31011820Sjulian 31111820Sjulian csap = sap; 31211820Sjulian while (csap->clone) 31311820Sjulian csap = csap->clone; 31411820Sjulian csap->clone = nsap; 31527244Sjhay TRACE_SAP_ACTION("ADD CLONE", nsap); 31611820Sjulian} 31711820Sjulian 31811820Sjulian/* 31911820Sjulian * Remove a SAP entry from the table and free the memory 32011820Sjulian * used by it. 32111820Sjulian * 32211820Sjulian * If the service have clone, do a sap_change to it and free 32311820Sjulian * the clone. 32411820Sjulian */ 32511820Sjulianvoid 32611820Sjuliansap_delete(struct sap_entry *sap) 32711820Sjulian{ 32811820Sjulian if (sap->clone) { 32911820Sjulian sap_change(sap, &sap->clone->sap, &sap->clone->source); 33011820Sjulian return; 33111820Sjulian } 33211820Sjulian remque(sap); 33327244Sjhay TRACE_SAP_ACTION("DELETE", sap); 33411820Sjulian free(sap); 33511820Sjulian} 336