sap_tables.c revision 108533
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 * 3150479Speter * $FreeBSD: head/usr.sbin/IPXrouted/sap_tables.c 108533 2003-01-01 18:49:04Z schweikh $ 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 13811820Sjulian if (ntohs(sap->sap.hops) < besthops) { 13911820Sjulian best = sap; 14011820Sjulian besthops = ntohs(best->sap.hops); 14111820Sjulian } 14211820Sjuliannext:; 14311820Sjulian } 14411820Sjulian return best; 14511820Sjulian} 14611820Sjulian 14711820Sjulian/* 148108533Sschweikh * Add an entry to the SAP table. 14911820Sjulian * 15011820Sjulian * If the malloc fail, the entry will silently be thrown away. 15111820Sjulian */ 15211820Sjulianvoid 15311820Sjuliansap_add(struct sap_info *si, struct sockaddr *from) 15411820Sjulian{ 15511820Sjulian register struct sap_entry *nsap; 15611820Sjulian register struct sap_hash *sh; 15711820Sjulian 15827244Sjhay if (ntohs(si->hops) == HOPCNT_INFINITY) 15927244Sjhay return; 16027244Sjhay 16111820Sjulian FIXLEN(from); 16211820Sjulian nsap = malloc(sizeof(struct sap_entry)); 16311820Sjulian if (nsap == NULL) 16411820Sjulian return; 16511820Sjulian 16611820Sjulian nsap->sap = *si; 16711820Sjulian nsap->source = *from; 16811820Sjulian nsap->clone = NULL; 16911820Sjulian nsap->ifp = if_ifwithnet(from); 17011820Sjulian nsap->state = RTS_CHANGED; 17111820Sjulian nsap->timer = 0; 17211820Sjulian nsap->hash = saphash(si->ServType, si->ServName); 17311820Sjulian 17411820Sjulian sh = &sap_head[nsap->hash & SAPHASHMASK]; 17511820Sjulian 17611820Sjulian insque(nsap, sh); 17727244Sjhay TRACE_SAP_ACTION("ADD", nsap); 17811820Sjulian} 17911820Sjulian 18011820Sjulian/* 18111820Sjulian * Change an existing SAP entry. If a clone exist for the old one, 18211820Sjulian * check if it is cheaper. If it is change tothe clone, otherwise 18311820Sjulian * delete all the clones. 18411820Sjulian */ 18511820Sjulianvoid 18611820Sjuliansap_change(struct sap_entry *sap, 18711820Sjulian struct sap_info *si, 18811820Sjulian struct sockaddr *from) 18911820Sjulian{ 19011820Sjulian struct sap_entry *osap = NULL; 19111820Sjulian 19211820Sjulian FIXLEN(from); 19327244Sjhay TRACE_SAP_ACTION("CHANGE FROM", sap); 19411820Sjulian /* 19511820Sjulian * If the hopcount (metric) is HOPCNT_INFINITY (16) it means that 19611820Sjulian * a service has gone down. We should keep it like that for 30 19711820Sjulian * seconds, so that it will get broadcast and then change to a 19811820Sjulian * clone if one exist. 19911820Sjulian */ 20011820Sjulian if (sap->clone && (ntohs(si->hops) != HOPCNT_INFINITY)) { 20111820Sjulian /* 20211820Sjulian * There are three possibilities: 20311820Sjulian * 1. The new path is cheaper than the old one. 20411820Sjulian * Free all the clones. 20511820Sjulian * 20611820Sjulian * 2. The new path is the same cost as the old ones. 20711820Sjulian * If it is on the list of clones remove it 20811820Sjulian * from the clone list and free it. 20911820Sjulian * 21011820Sjulian * 3. The new path is more expensive than the old one. 21111820Sjulian * Use the values of the first clone and take it 21211820Sjulian * out of the list, to be freed at the end. 21311820Sjulian */ 21411820Sjulian osap = sap->clone; 21511820Sjulian if (ntohs(osap->sap.hops) > ntohs(si->hops)) { 21611820Sjulian struct sap_entry *nsap; 21711820Sjulian 21811820Sjulian while (osap) { 21911820Sjulian nsap = osap->clone; 22027244Sjhay TRACE_SAP_ACTION("DELETE", osap); 22111820Sjulian free(osap); 22211820Sjulian osap = nsap; 22311820Sjulian } 22411820Sjulian sap->clone = NULL; 22511820Sjulian } else if (ntohs(osap->sap.hops) == ntohs(si->hops)) { 22611820Sjulian struct sap_entry *psap; 22711820Sjulian 22811820Sjulian psap = sap; 22911820Sjulian while (osap) { 23011820Sjulian if (equal(&osap->source, from)) { 23111820Sjulian psap->clone = osap->clone; 23227244Sjhay TRACE_SAP_ACTION("DELETE", osap); 23311820Sjulian free(osap); 23411820Sjulian osap = psap->clone; 23511820Sjulian } else { 23611820Sjulian psap = osap; 23711820Sjulian osap = osap->clone; 23811820Sjulian } 23911820Sjulian } 24011820Sjulian } else { 24111820Sjulian from = &osap->source; 24211820Sjulian si = &osap->sap; 24311820Sjulian sap->clone = osap->clone; 24411820Sjulian } 24511820Sjulian } 24611820Sjulian sap->sap = *si; 24711820Sjulian sap->source = *from; 24811820Sjulian sap->ifp = if_ifwithnet(from); 24911820Sjulian sap->state = RTS_CHANGED; 25011820Sjulian if (ntohs(si->hops) == HOPCNT_INFINITY) 25111820Sjulian sap->timer = EXPIRE_TIME; 25211820Sjulian else 25311820Sjulian sap->timer = 0; 25411820Sjulian 25527244Sjhay if (osap) { 25627244Sjhay TRACE_SAP_ACTION("DELETE", osap); 25711820Sjulian free(osap); 25827244Sjhay } 25927244Sjhay TRACE_SAP_ACTION("CHANGE TO", sap); 26011820Sjulian} 26111820Sjulian 26211820Sjulian/* 26311820Sjulian * Add a clone to the specified SAP entry. A clone is a different 26411820Sjulian * route to the same service. We must know about them when we use 26511820Sjulian * the split horizon algorithm. 26611820Sjulian * 26711820Sjulian * If the malloc fail, the entry will silently be thrown away. 26811820Sjulian */ 26911820Sjulianvoid 27011820Sjuliansap_add_clone(struct sap_entry *sap, 27111820Sjulian struct sap_info *clone, 27211820Sjulian struct sockaddr *from) 27311820Sjulian{ 27411820Sjulian register struct sap_entry *nsap; 27511820Sjulian register struct sap_entry *csap; 27611820Sjulian 27727244Sjhay if (ntohs(clone->hops) == HOPCNT_INFINITY) 27827244Sjhay return; 27927244Sjhay 28011820Sjulian FIXLEN(from); 28111820Sjulian nsap = malloc(sizeof(struct sap_entry)); 28211820Sjulian if (nsap == NULL) 28311820Sjulian return; 28411820Sjulian 28511820Sjulian if (ftrace) 28611820Sjulian fprintf(ftrace, "CLONE ADD %04.4X %s.\n", 28711820Sjulian ntohs(clone->ServType), 28811820Sjulian clone->ServName); 28911820Sjulian 29011820Sjulian nsap->sap = *clone; 29111820Sjulian nsap->source = *from; 29211820Sjulian nsap->clone = NULL; 29311820Sjulian nsap->ifp = if_ifwithnet(from); 29411820Sjulian nsap->state = RTS_CHANGED; 29511820Sjulian nsap->timer = 0; 29611820Sjulian nsap->hash = saphash(clone->ServType, clone->ServName); 29711820Sjulian 29811820Sjulian csap = sap; 29911820Sjulian while (csap->clone) 30011820Sjulian csap = csap->clone; 30111820Sjulian csap->clone = nsap; 30227244Sjhay TRACE_SAP_ACTION("ADD CLONE", nsap); 30311820Sjulian} 30411820Sjulian 30511820Sjulian/* 30611820Sjulian * Remove a SAP entry from the table and free the memory 30711820Sjulian * used by it. 30811820Sjulian * 30911820Sjulian * If the service have clone, do a sap_change to it and free 31011820Sjulian * the clone. 31111820Sjulian */ 31211820Sjulianvoid 31311820Sjuliansap_delete(struct sap_entry *sap) 31411820Sjulian{ 31511820Sjulian if (sap->clone) { 31611820Sjulian sap_change(sap, &sap->clone->sap, &sap->clone->source); 31711820Sjulian return; 31811820Sjulian } 31911820Sjulian remque(sap); 32027244Sjhay TRACE_SAP_ACTION("DELETE", sap); 32111820Sjulian free(sap); 32211820Sjulian} 323