sap_tables.c revision 11820
1/* 2 * Copyright (c) 1995 John Hay. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 3. All advertising materials mentioning features or use of this software 13 * must display the following acknowledgement: 14 * This product includes software developed by John Hay. 15 * 4. Neither the name of the author nor the names of any co-contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY John Hay AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL John Hay OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 * 31 * $Id: sap_tables.c,v 1.9 1995/10/11 18:57:29 jhay Exp $ 32 */ 33 34#include "defs.h" 35#include <string.h> 36#include <stdlib.h> 37/* XXX I thought that this should work! #include <sys/systm.h> */ 38#include <machine/cpufunc.h> 39 40#define FIXLEN(s) { if ((s)->sa_len == 0) (s)->sa_len = sizeof (*(s));} 41 42sap_hash sap_head[SAPHASHSIZ]; 43 44void 45sapinit(void) 46{ 47 int i; 48 49 for (i=0; i<SAPHASHSIZ; i++) 50 sap_head[i].forw = sap_head[i].back = 51 (struct sap_entry *)&sap_head[i]; 52} 53 54/* 55 * XXX Make sure that this hash is good enough. 56 * 57 * This hash use the first 8 letters of the ServName and the ServType 58 * to create a 32 bit hash value. 59 * 60 * NOTE: The first two letters of ServName will be used to generate 61 * the lower bits of the hash. This is used to index into the hash table. 62 */ 63#define rol(x) (((x * 2) & 0xFFFF) + ((x & 0x8000) != 0)) 64 65int 66saphash(u_short ServType, char *ServName) 67{ 68 int hsh, i; 69 char name[SERVNAMELEN]; 70 71 bzero(name, SERVNAMELEN); 72 strncpy(name, ServName, SERVNAMELEN); 73 ServName = name; 74 75 hsh = 0; 76 77 for (i=0;i<8;i++) { 78 hsh = rol(hsh) + *ServName; 79 ServName++; 80 } 81 82 hsh = rol(hsh) + (ServType >> 8); 83 hsh = rol(hsh) + (ServType & 0xff); 84 hsh = (hsh >> 7) ^ hsh; 85 return hsh; 86} 87 88/* 89 * Look for an exact match on ServType and ServName. It is 90 * mostly used by the function that process SAP RESPONSE packets. 91 * 92 * A hash is created and used to index into the hash table. Then 93 * that list is walk through searching for a match. 94 * 95 * If no match is found NULL is returned. 96 */ 97struct sap_entry * 98sap_lookup(u_short ServType, char *ServName) 99{ 100 register struct sap_entry *sap; 101 register struct sap_hash *sh; 102 int hsh; 103 104 hsh = saphash(ServType, ServName); 105 sh = &sap_head[hsh & SAPHASHMASK]; 106 107 for(sap = sh->forw; sap != (sap_entry *)sh; sap = sap->forw) { 108 if ((hsh == sap->hash) && 109 (ServType == sap->sap.ServType) && 110 (strncmp(ServName, sap->sap.ServName, SERVNAMELEN) == 0)) { 111 return sap; 112 } 113 } 114 return NULL; 115} 116 117/* 118 * This returns the nearest service of the specified type. If no 119 * suitable service is found or if that service is on the interface 120 * where the request came from, NULL is returned. 121 * 122 * When checking interfaces clones must be considered also. 123 * 124 * XXX TODO: 125 * Maybe we can use RIP tables to get the fastest service (ticks). 126 */ 127struct sap_entry * 128sap_nearestserver(ushort ServType, struct interface *ifp) 129{ 130 register struct sap_entry *sap; 131 register struct sap_entry *csap; 132 struct sap_hash *sh; 133 register struct sap_entry *best = NULL; 134 register int besthops = HOPCNT_INFINITY; 135 136 sh = sap_head; 137 138 for (; sh < &sap_head[SAPHASHSIZ]; sh++) 139 for(sap = sh->forw; sap != (sap_entry *)sh; sap = sap->forw) { 140 if (ServType != sap->sap.ServType) 141 continue; 142 if (ifp == sap->ifp) 143 continue; 144 145 csap = sap->clone; 146 while (csap) { 147 if (ifp == csap->ifp) 148 /* 149 * I would have loved to use 150 * something else here. 151 */ 152 goto next; 153 csap = csap->clone; 154 } 155 156 if (ntohs(sap->sap.hops) < besthops) { 157 best = sap; 158 besthops = ntohs(best->sap.hops); 159 } 160next:; 161 } 162 return best; 163} 164 165/* 166 * Add a entry to the SAP table. 167 * 168 * If the malloc fail, the entry will silently be thrown away. 169 */ 170void 171sap_add(struct sap_info *si, struct sockaddr *from) 172{ 173 register struct sap_entry *nsap; 174 register struct sap_hash *sh; 175 176 FIXLEN(from); 177 nsap = malloc(sizeof(struct sap_entry)); 178 if (nsap == NULL) 179 return; 180 181 nsap->sap = *si; 182 nsap->source = *from; 183 nsap->clone = NULL; 184 nsap->ifp = if_ifwithnet(from); 185 nsap->state = RTS_CHANGED; 186 nsap->timer = 0; 187 nsap->hash = saphash(si->ServType, si->ServName); 188 189 sh = &sap_head[nsap->hash & SAPHASHMASK]; 190 191 insque(nsap, sh); 192} 193 194/* 195 * Change an existing SAP entry. If a clone exist for the old one, 196 * check if it is cheaper. If it is change tothe clone, otherwise 197 * delete all the clones. 198 */ 199void 200sap_change(struct sap_entry *sap, 201 struct sap_info *si, 202 struct sockaddr *from) 203{ 204 struct sap_entry *osap = NULL; 205 206 FIXLEN(from); 207 /* 208 * If the hopcount (metric) is HOPCNT_INFINITY (16) it means that 209 * a service has gone down. We should keep it like that for 30 210 * seconds, so that it will get broadcast and then change to a 211 * clone if one exist. 212 */ 213 if (sap->clone && (ntohs(si->hops) != HOPCNT_INFINITY)) { 214 /* 215 * There are three possibilities: 216 * 1. The new path is cheaper than the old one. 217 * Free all the clones. 218 * 219 * 2. The new path is the same cost as the old ones. 220 * If it is on the list of clones remove it 221 * from the clone list and free it. 222 * 223 * 3. The new path is more expensive than the old one. 224 * Use the values of the first clone and take it 225 * out of the list, to be freed at the end. 226 */ 227 osap = sap->clone; 228 if (ntohs(osap->sap.hops) > ntohs(si->hops)) { 229 struct sap_entry *nsap; 230 231 while (osap) { 232 nsap = osap->clone; 233 free(osap); 234 osap = nsap; 235 } 236 sap->clone = NULL; 237 } else if (ntohs(osap->sap.hops) == ntohs(si->hops)) { 238 struct sap_entry *psap; 239 240 psap = sap; 241 while (osap) { 242 if (equal(&osap->source, from)) { 243 psap->clone = osap->clone; 244 free(osap); 245 osap = psap->clone; 246 } else { 247 psap = osap; 248 osap = osap->clone; 249 } 250 } 251 } else { 252 from = &osap->source; 253 si = &osap->sap; 254 sap->clone = osap->clone; 255 } 256 } 257 sap->sap = *si; 258 sap->source = *from; 259 sap->ifp = if_ifwithnet(from); 260 sap->state = RTS_CHANGED; 261 if (ntohs(si->hops) == HOPCNT_INFINITY) 262 sap->timer = EXPIRE_TIME; 263 else 264 sap->timer = 0; 265 266 if (osap) 267 free(osap); 268} 269 270/* 271 * Add a clone to the specified SAP entry. A clone is a different 272 * route to the same service. We must know about them when we use 273 * the split horizon algorithm. 274 * 275 * If the malloc fail, the entry will silently be thrown away. 276 */ 277void 278sap_add_clone(struct sap_entry *sap, 279 struct sap_info *clone, 280 struct sockaddr *from) 281{ 282 register struct sap_entry *nsap; 283 register struct sap_entry *csap; 284 285 FIXLEN(from); 286 nsap = malloc(sizeof(struct sap_entry)); 287 if (nsap == NULL) 288 return; 289 290 if (ftrace) 291 fprintf(ftrace, "CLONE ADD %04.4X %s.\n", 292 ntohs(clone->ServType), 293 clone->ServName); 294 295 nsap->sap = *clone; 296 nsap->source = *from; 297 nsap->clone = NULL; 298 nsap->ifp = if_ifwithnet(from); 299 nsap->state = RTS_CHANGED; 300 nsap->timer = 0; 301 nsap->hash = saphash(clone->ServType, clone->ServName); 302 303 csap = sap; 304 while (csap->clone) 305 csap = csap->clone; 306 csap->clone = nsap; 307} 308 309/* 310 * Remove a SAP entry from the table and free the memory 311 * used by it. 312 * 313 * If the service have clone, do a sap_change to it and free 314 * the clone. 315 */ 316void 317sap_delete(struct sap_entry *sap) 318{ 319 if (sap->clone) { 320 sap_change(sap, &sap->clone->sap, &sap->clone->source); 321 return; 322 } 323 remque(sap); 324 free(sap); 325} 326 327