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$ 3211820Sjulian */ 3311820Sjulian 3411820Sjulian#include "defs.h" 35122760Strhodes#include <search.h> 3611820Sjulian#include <string.h> 3711820Sjulian#include <stdlib.h> 3811820Sjulian 3911820Sjulian#define FIXLEN(s) { if ((s)->sa_len == 0) (s)->sa_len = sizeof (*(s));} 4011820Sjulian 4111820Sjuliansap_hash sap_head[SAPHASHSIZ]; 4211820Sjulian 4311820Sjulianvoid 4411820Sjuliansapinit(void) 4511820Sjulian{ 4611820Sjulian int i; 4711820Sjulian 4811820Sjulian for (i=0; i<SAPHASHSIZ; i++) 4911820Sjulian sap_head[i].forw = sap_head[i].back = 5011820Sjulian (struct sap_entry *)&sap_head[i]; 5111820Sjulian} 5211820Sjulian 5311820Sjulian/* 5427244Sjhay * This hash use the first 14 letters of the ServName and the ServType 5511820Sjulian * to create a 32 bit hash value. 5611820Sjulian */ 5711820Sjulianint 5811820Sjuliansaphash(u_short ServType, char *ServName) 5911820Sjulian{ 6011820Sjulian int hsh, i; 6111820Sjulian char name[SERVNAMELEN]; 6211820Sjulian 6311820Sjulian bzero(name, SERVNAMELEN); 6411820Sjulian strncpy(name, ServName, SERVNAMELEN); 6511820Sjulian ServName = name; 6611820Sjulian 6711820Sjulian hsh = 0; 6811820Sjulian 6927244Sjhay#define SMVAL 33 7027244Sjhay 7127244Sjhay hsh = hsh * SMVAL + (ServType & 0xff); 7227244Sjhay hsh = hsh * SMVAL + (ServType >> 8); 7327244Sjhay 7427244Sjhay for (i=0;i<14;i++) { 7527244Sjhay hsh = hsh * SMVAL + *ServName++; 7611820Sjulian ServName++; 7711820Sjulian } 7811820Sjulian 7927244Sjhay#undef SMVAL 8027244Sjhay 8111820Sjulian return hsh; 8211820Sjulian} 8311820Sjulian 8411820Sjulian/* 8511820Sjulian * Look for an exact match on ServType and ServName. It is 8611820Sjulian * mostly used by the function that process SAP RESPONSE packets. 8711820Sjulian * 8811820Sjulian * A hash is created and used to index into the hash table. Then 8911820Sjulian * that list is walk through searching for a match. 9011820Sjulian * 9111820Sjulian * If no match is found NULL is returned. 9211820Sjulian */ 9311820Sjulianstruct sap_entry * 9411820Sjuliansap_lookup(u_short ServType, char *ServName) 9511820Sjulian{ 9611820Sjulian register struct sap_entry *sap; 9711820Sjulian register struct sap_hash *sh; 9811820Sjulian int hsh; 9911820Sjulian 10011820Sjulian hsh = saphash(ServType, ServName); 10111820Sjulian sh = &sap_head[hsh & SAPHASHMASK]; 10211820Sjulian 10311820Sjulian for(sap = sh->forw; sap != (sap_entry *)sh; sap = sap->forw) { 10411820Sjulian if ((hsh == sap->hash) && 10511820Sjulian (ServType == sap->sap.ServType) && 10611820Sjulian (strncmp(ServName, sap->sap.ServName, SERVNAMELEN) == 0)) { 10711820Sjulian return sap; 10811820Sjulian } 10911820Sjulian } 11011820Sjulian return NULL; 11111820Sjulian} 11211820Sjulian 11311820Sjulian/* 11411820Sjulian * This returns the nearest service of the specified type. If no 11511820Sjulian * suitable service is found or if that service is on the interface 11611820Sjulian * where the request came from, NULL is returned. 11711820Sjulian * 11811820Sjulian * When checking interfaces clones must be considered also. 11911820Sjulian * 12011820Sjulian * XXX TODO: 12111820Sjulian * Maybe we can use RIP tables to get the fastest service (ticks). 12211820Sjulian */ 12311820Sjulianstruct sap_entry * 12411820Sjuliansap_nearestserver(ushort ServType, struct interface *ifp) 12511820Sjulian{ 12611820Sjulian register struct sap_entry *sap; 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 } 14211820Sjulian } 14311820Sjulian return best; 14411820Sjulian} 14511820Sjulian 14611820Sjulian/* 147108533Sschweikh * Add an entry to the SAP table. 14811820Sjulian * 14911820Sjulian * If the malloc fail, the entry will silently be thrown away. 15011820Sjulian */ 15111820Sjulianvoid 15211820Sjuliansap_add(struct sap_info *si, struct sockaddr *from) 15311820Sjulian{ 15411820Sjulian register struct sap_entry *nsap; 15511820Sjulian register struct sap_hash *sh; 15611820Sjulian 15727244Sjhay if (ntohs(si->hops) == HOPCNT_INFINITY) 15827244Sjhay return; 15927244Sjhay 16011820Sjulian FIXLEN(from); 16111820Sjulian nsap = malloc(sizeof(struct sap_entry)); 16211820Sjulian if (nsap == NULL) 16311820Sjulian return; 16411820Sjulian 16511820Sjulian nsap->sap = *si; 16611820Sjulian nsap->source = *from; 16711820Sjulian nsap->clone = NULL; 16811820Sjulian nsap->ifp = if_ifwithnet(from); 16911820Sjulian nsap->state = RTS_CHANGED; 17011820Sjulian nsap->timer = 0; 17111820Sjulian nsap->hash = saphash(si->ServType, si->ServName); 17211820Sjulian 17311820Sjulian sh = &sap_head[nsap->hash & SAPHASHMASK]; 17411820Sjulian 17511820Sjulian insque(nsap, sh); 17627244Sjhay TRACE_SAP_ACTION("ADD", nsap); 17711820Sjulian} 17811820Sjulian 17911820Sjulian/* 18011820Sjulian * Change an existing SAP entry. If a clone exist for the old one, 181228990Suqs * check if it is cheaper. If it is change to the clone, otherwise 18211820Sjulian * delete all the clones. 18311820Sjulian */ 18411820Sjulianvoid 18511820Sjuliansap_change(struct sap_entry *sap, 18611820Sjulian struct sap_info *si, 18711820Sjulian struct sockaddr *from) 18811820Sjulian{ 18911820Sjulian struct sap_entry *osap = NULL; 19011820Sjulian 19111820Sjulian FIXLEN(from); 19227244Sjhay TRACE_SAP_ACTION("CHANGE FROM", sap); 19311820Sjulian /* 19411820Sjulian * If the hopcount (metric) is HOPCNT_INFINITY (16) it means that 19511820Sjulian * a service has gone down. We should keep it like that for 30 19611820Sjulian * seconds, so that it will get broadcast and then change to a 19711820Sjulian * clone if one exist. 19811820Sjulian */ 19911820Sjulian if (sap->clone && (ntohs(si->hops) != HOPCNT_INFINITY)) { 20011820Sjulian /* 20111820Sjulian * There are three possibilities: 20211820Sjulian * 1. The new path is cheaper than the old one. 20311820Sjulian * Free all the clones. 20411820Sjulian * 20511820Sjulian * 2. The new path is the same cost as the old ones. 20611820Sjulian * If it is on the list of clones remove it 20711820Sjulian * from the clone list and free it. 20811820Sjulian * 20911820Sjulian * 3. The new path is more expensive than the old one. 21011820Sjulian * Use the values of the first clone and take it 21111820Sjulian * out of the list, to be freed at the end. 21211820Sjulian */ 21311820Sjulian osap = sap->clone; 21411820Sjulian if (ntohs(osap->sap.hops) > ntohs(si->hops)) { 21511820Sjulian struct sap_entry *nsap; 21611820Sjulian 21711820Sjulian while (osap) { 21811820Sjulian nsap = osap->clone; 21927244Sjhay TRACE_SAP_ACTION("DELETE", osap); 22011820Sjulian free(osap); 22111820Sjulian osap = nsap; 22211820Sjulian } 22311820Sjulian sap->clone = NULL; 22411820Sjulian } else if (ntohs(osap->sap.hops) == ntohs(si->hops)) { 22511820Sjulian struct sap_entry *psap; 22611820Sjulian 22711820Sjulian psap = sap; 22811820Sjulian while (osap) { 22911820Sjulian if (equal(&osap->source, from)) { 23011820Sjulian psap->clone = osap->clone; 23127244Sjhay TRACE_SAP_ACTION("DELETE", osap); 23211820Sjulian free(osap); 23311820Sjulian osap = psap->clone; 23411820Sjulian } else { 23511820Sjulian psap = osap; 23611820Sjulian osap = osap->clone; 23711820Sjulian } 23811820Sjulian } 23911820Sjulian } else { 24011820Sjulian from = &osap->source; 24111820Sjulian si = &osap->sap; 24211820Sjulian sap->clone = osap->clone; 24311820Sjulian } 24411820Sjulian } 24511820Sjulian sap->sap = *si; 24611820Sjulian sap->source = *from; 24711820Sjulian sap->ifp = if_ifwithnet(from); 24811820Sjulian sap->state = RTS_CHANGED; 24911820Sjulian if (ntohs(si->hops) == HOPCNT_INFINITY) 25011820Sjulian sap->timer = EXPIRE_TIME; 25111820Sjulian else 25211820Sjulian sap->timer = 0; 25311820Sjulian 25427244Sjhay if (osap) { 25527244Sjhay TRACE_SAP_ACTION("DELETE", osap); 25611820Sjulian free(osap); 25727244Sjhay } 25827244Sjhay TRACE_SAP_ACTION("CHANGE TO", sap); 25911820Sjulian} 26011820Sjulian 26111820Sjulian/* 26211820Sjulian * Add a clone to the specified SAP entry. A clone is a different 26311820Sjulian * route to the same service. We must know about them when we use 26411820Sjulian * the split horizon algorithm. 26511820Sjulian * 26611820Sjulian * If the malloc fail, the entry will silently be thrown away. 26711820Sjulian */ 26811820Sjulianvoid 26911820Sjuliansap_add_clone(struct sap_entry *sap, 27011820Sjulian struct sap_info *clone, 27111820Sjulian struct sockaddr *from) 27211820Sjulian{ 27311820Sjulian register struct sap_entry *nsap; 27411820Sjulian register struct sap_entry *csap; 27511820Sjulian 27627244Sjhay if (ntohs(clone->hops) == HOPCNT_INFINITY) 27727244Sjhay return; 27827244Sjhay 27911820Sjulian FIXLEN(from); 28011820Sjulian nsap = malloc(sizeof(struct sap_entry)); 28111820Sjulian if (nsap == NULL) 28211820Sjulian return; 28311820Sjulian 28411820Sjulian if (ftrace) 285122760Strhodes fprintf(ftrace, "CLONE ADD %4.4X %s.\n", 28611820Sjulian ntohs(clone->ServType), 28711820Sjulian clone->ServName); 28811820Sjulian 28911820Sjulian nsap->sap = *clone; 29011820Sjulian nsap->source = *from; 29111820Sjulian nsap->clone = NULL; 29211820Sjulian nsap->ifp = if_ifwithnet(from); 29311820Sjulian nsap->state = RTS_CHANGED; 29411820Sjulian nsap->timer = 0; 29511820Sjulian nsap->hash = saphash(clone->ServType, clone->ServName); 29611820Sjulian 29711820Sjulian csap = sap; 29811820Sjulian while (csap->clone) 29911820Sjulian csap = csap->clone; 30011820Sjulian csap->clone = nsap; 30127244Sjhay TRACE_SAP_ACTION("ADD CLONE", nsap); 30211820Sjulian} 30311820Sjulian 30411820Sjulian/* 30511820Sjulian * Remove a SAP entry from the table and free the memory 30611820Sjulian * used by it. 30711820Sjulian * 30811820Sjulian * If the service have clone, do a sap_change to it and free 30911820Sjulian * the clone. 31011820Sjulian */ 31111820Sjulianvoid 31211820Sjuliansap_delete(struct sap_entry *sap) 31311820Sjulian{ 31411820Sjulian if (sap->clone) { 31511820Sjulian sap_change(sap, &sap->clone->sap, &sap->clone->source); 31611820Sjulian return; 31711820Sjulian } 31811820Sjulian remque(sap); 31927244Sjhay TRACE_SAP_ACTION("DELETE", sap); 32011820Sjulian free(sap); 32111820Sjulian} 322