sap_tables.c revision 27244
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.4 1997/07/01 00:33:41 bde Exp $ 32 */ 33 34#include "defs.h" 35#include <string.h> 36#include <stdlib.h> 37 38#define FIXLEN(s) { if ((s)->sa_len == 0) (s)->sa_len = sizeof (*(s));} 39 40sap_hash sap_head[SAPHASHSIZ]; 41 42void 43sapinit(void) 44{ 45 int i; 46 47 for (i=0; i<SAPHASHSIZ; i++) 48 sap_head[i].forw = sap_head[i].back = 49 (struct sap_entry *)&sap_head[i]; 50} 51 52/* 53 * This hash use the first 14 letters of the ServName and the ServType 54 * to create a 32 bit hash value. 55 */ 56int 57saphash(u_short ServType, char *ServName) 58{ 59 int hsh, i; 60 char name[SERVNAMELEN]; 61 62 bzero(name, SERVNAMELEN); 63 strncpy(name, ServName, SERVNAMELEN); 64 ServName = name; 65 66 hsh = 0; 67 68#define SMVAL 33 69 70 hsh = hsh * SMVAL + (ServType & 0xff); 71 hsh = hsh * SMVAL + (ServType >> 8); 72 73 for (i=0;i<14;i++) { 74 hsh = hsh * SMVAL + *ServName++; 75 ServName++; 76 } 77 78#undef SMVAL 79 80 return hsh; 81} 82 83/* 84 * Look for an exact match on ServType and ServName. It is 85 * mostly used by the function that process SAP RESPONSE packets. 86 * 87 * A hash is created and used to index into the hash table. Then 88 * that list is walk through searching for a match. 89 * 90 * If no match is found NULL is returned. 91 */ 92struct sap_entry * 93sap_lookup(u_short ServType, char *ServName) 94{ 95 register struct sap_entry *sap; 96 register struct sap_hash *sh; 97 int hsh; 98 99 hsh = saphash(ServType, ServName); 100 sh = &sap_head[hsh & SAPHASHMASK]; 101 102 for(sap = sh->forw; sap != (sap_entry *)sh; sap = sap->forw) { 103 if ((hsh == sap->hash) && 104 (ServType == sap->sap.ServType) && 105 (strncmp(ServName, sap->sap.ServName, SERVNAMELEN) == 0)) { 106 return sap; 107 } 108 } 109 return NULL; 110} 111 112/* 113 * This returns the nearest service of the specified type. If no 114 * suitable service is found or if that service is on the interface 115 * where the request came from, NULL is returned. 116 * 117 * When checking interfaces clones must be considered also. 118 * 119 * XXX TODO: 120 * Maybe we can use RIP tables to get the fastest service (ticks). 121 */ 122struct sap_entry * 123sap_nearestserver(ushort ServType, struct interface *ifp) 124{ 125 register struct sap_entry *sap; 126 register struct sap_entry *csap; 127 struct sap_hash *sh; 128 register struct sap_entry *best = NULL; 129 register int besthops = HOPCNT_INFINITY; 130 131 sh = sap_head; 132 133 for (; sh < &sap_head[SAPHASHSIZ]; sh++) 134 for(sap = sh->forw; sap != (sap_entry *)sh; sap = sap->forw) { 135 if (ServType != sap->sap.ServType) 136 continue; 137 if (ifp == sap->ifp) 138 continue; 139 140 csap = sap->clone; 141 while (csap) { 142 if (ifp == csap->ifp) 143 /* 144 * I would have loved to use 145 * something else here. 146 */ 147 goto next; 148 csap = csap->clone; 149 } 150 151 if (ntohs(sap->sap.hops) < besthops) { 152 best = sap; 153 besthops = ntohs(best->sap.hops); 154 } 155next:; 156 } 157 return best; 158} 159 160/* 161 * Add a entry to the SAP table. 162 * 163 * If the malloc fail, the entry will silently be thrown away. 164 */ 165void 166sap_add(struct sap_info *si, struct sockaddr *from) 167{ 168 register struct sap_entry *nsap; 169 register struct sap_hash *sh; 170 171 if (ntohs(si->hops) == HOPCNT_INFINITY) 172 return; 173 174 FIXLEN(from); 175 nsap = malloc(sizeof(struct sap_entry)); 176 if (nsap == NULL) 177 return; 178 179 nsap->sap = *si; 180 nsap->source = *from; 181 nsap->clone = NULL; 182 nsap->ifp = if_ifwithnet(from); 183 nsap->state = RTS_CHANGED; 184 nsap->timer = 0; 185 nsap->hash = saphash(si->ServType, si->ServName); 186 187 sh = &sap_head[nsap->hash & SAPHASHMASK]; 188 189 insque(nsap, sh); 190 TRACE_SAP_ACTION("ADD", nsap); 191} 192 193/* 194 * Change an existing SAP entry. If a clone exist for the old one, 195 * check if it is cheaper. If it is change tothe clone, otherwise 196 * delete all the clones. 197 */ 198void 199sap_change(struct sap_entry *sap, 200 struct sap_info *si, 201 struct sockaddr *from) 202{ 203 struct sap_entry *osap = NULL; 204 205 FIXLEN(from); 206 TRACE_SAP_ACTION("CHANGE FROM", sap); 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 TRACE_SAP_ACTION("DELETE", osap); 234 free(osap); 235 osap = nsap; 236 } 237 sap->clone = NULL; 238 } else if (ntohs(osap->sap.hops) == ntohs(si->hops)) { 239 struct sap_entry *psap; 240 241 psap = sap; 242 while (osap) { 243 if (equal(&osap->source, from)) { 244 psap->clone = osap->clone; 245 TRACE_SAP_ACTION("DELETE", osap); 246 free(osap); 247 osap = psap->clone; 248 } else { 249 psap = osap; 250 osap = osap->clone; 251 } 252 } 253 } else { 254 from = &osap->source; 255 si = &osap->sap; 256 sap->clone = osap->clone; 257 } 258 } 259 sap->sap = *si; 260 sap->source = *from; 261 sap->ifp = if_ifwithnet(from); 262 sap->state = RTS_CHANGED; 263 if (ntohs(si->hops) == HOPCNT_INFINITY) 264 sap->timer = EXPIRE_TIME; 265 else 266 sap->timer = 0; 267 268 if (osap) { 269 TRACE_SAP_ACTION("DELETE", osap); 270 free(osap); 271 } 272 TRACE_SAP_ACTION("CHANGE TO", sap); 273} 274 275/* 276 * Add a clone to the specified SAP entry. A clone is a different 277 * route to the same service. We must know about them when we use 278 * the split horizon algorithm. 279 * 280 * If the malloc fail, the entry will silently be thrown away. 281 */ 282void 283sap_add_clone(struct sap_entry *sap, 284 struct sap_info *clone, 285 struct sockaddr *from) 286{ 287 register struct sap_entry *nsap; 288 register struct sap_entry *csap; 289 290 if (ntohs(clone->hops) == HOPCNT_INFINITY) 291 return; 292 293 FIXLEN(from); 294 nsap = malloc(sizeof(struct sap_entry)); 295 if (nsap == NULL) 296 return; 297 298 if (ftrace) 299 fprintf(ftrace, "CLONE ADD %04.4X %s.\n", 300 ntohs(clone->ServType), 301 clone->ServName); 302 303 nsap->sap = *clone; 304 nsap->source = *from; 305 nsap->clone = NULL; 306 nsap->ifp = if_ifwithnet(from); 307 nsap->state = RTS_CHANGED; 308 nsap->timer = 0; 309 nsap->hash = saphash(clone->ServType, clone->ServName); 310 311 csap = sap; 312 while (csap->clone) 313 csap = csap->clone; 314 csap->clone = nsap; 315 TRACE_SAP_ACTION("ADD CLONE", nsap); 316} 317 318/* 319 * Remove a SAP entry from the table and free the memory 320 * used by it. 321 * 322 * If the service have clone, do a sap_change to it and free 323 * the clone. 324 */ 325void 326sap_delete(struct sap_entry *sap) 327{ 328 if (sap->clone) { 329 sap_change(sap, &sap->clone->sap, &sap->clone->source); 330 return; 331 } 332 remque(sap); 333 TRACE_SAP_ACTION("DELETE", sap); 334 free(sap); 335} 336