sap_tables.c revision 122760
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 * $FreeBSD: head/usr.sbin/IPXrouted/sap_tables.c 122760 2003-11-15 17:10:56Z trhodes $ 32 */ 33 34#include "defs.h" 35#include <search.h> 36#include <string.h> 37#include <stdlib.h> 38 39#define FIXLEN(s) { if ((s)->sa_len == 0) (s)->sa_len = sizeof (*(s));} 40 41sap_hash sap_head[SAPHASHSIZ]; 42 43void 44sapinit(void) 45{ 46 int i; 47 48 for (i=0; i<SAPHASHSIZ; i++) 49 sap_head[i].forw = sap_head[i].back = 50 (struct sap_entry *)&sap_head[i]; 51} 52 53/* 54 * This hash use the first 14 letters of the ServName and the ServType 55 * to create a 32 bit hash value. 56 */ 57int 58saphash(u_short ServType, char *ServName) 59{ 60 int hsh, i; 61 char name[SERVNAMELEN]; 62 63 bzero(name, SERVNAMELEN); 64 strncpy(name, ServName, SERVNAMELEN); 65 ServName = name; 66 67 hsh = 0; 68 69#define SMVAL 33 70 71 hsh = hsh * SMVAL + (ServType & 0xff); 72 hsh = hsh * SMVAL + (ServType >> 8); 73 74 for (i=0;i<14;i++) { 75 hsh = hsh * SMVAL + *ServName++; 76 ServName++; 77 } 78 79#undef SMVAL 80 81 return hsh; 82} 83 84/* 85 * Look for an exact match on ServType and ServName. It is 86 * mostly used by the function that process SAP RESPONSE packets. 87 * 88 * A hash is created and used to index into the hash table. Then 89 * that list is walk through searching for a match. 90 * 91 * If no match is found NULL is returned. 92 */ 93struct sap_entry * 94sap_lookup(u_short ServType, char *ServName) 95{ 96 register struct sap_entry *sap; 97 register struct sap_hash *sh; 98 int hsh; 99 100 hsh = saphash(ServType, ServName); 101 sh = &sap_head[hsh & SAPHASHMASK]; 102 103 for(sap = sh->forw; sap != (sap_entry *)sh; sap = sap->forw) { 104 if ((hsh == sap->hash) && 105 (ServType == sap->sap.ServType) && 106 (strncmp(ServName, sap->sap.ServName, SERVNAMELEN) == 0)) { 107 return sap; 108 } 109 } 110 return NULL; 111} 112 113/* 114 * This returns the nearest service of the specified type. If no 115 * suitable service is found or if that service is on the interface 116 * where the request came from, NULL is returned. 117 * 118 * When checking interfaces clones must be considered also. 119 * 120 * XXX TODO: 121 * Maybe we can use RIP tables to get the fastest service (ticks). 122 */ 123struct sap_entry * 124sap_nearestserver(ushort ServType, struct interface *ifp) 125{ 126 register struct sap_entry *sap; 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 138 if (ntohs(sap->sap.hops) < besthops) { 139 best = sap; 140 besthops = ntohs(best->sap.hops); 141 } 142 } 143 return best; 144} 145 146/* 147 * Add an entry to the SAP table. 148 * 149 * If the malloc fail, the entry will silently be thrown away. 150 */ 151void 152sap_add(struct sap_info *si, struct sockaddr *from) 153{ 154 register struct sap_entry *nsap; 155 register struct sap_hash *sh; 156 157 if (ntohs(si->hops) == HOPCNT_INFINITY) 158 return; 159 160 FIXLEN(from); 161 nsap = malloc(sizeof(struct sap_entry)); 162 if (nsap == NULL) 163 return; 164 165 nsap->sap = *si; 166 nsap->source = *from; 167 nsap->clone = NULL; 168 nsap->ifp = if_ifwithnet(from); 169 nsap->state = RTS_CHANGED; 170 nsap->timer = 0; 171 nsap->hash = saphash(si->ServType, si->ServName); 172 173 sh = &sap_head[nsap->hash & SAPHASHMASK]; 174 175 insque(nsap, sh); 176 TRACE_SAP_ACTION("ADD", nsap); 177} 178 179/* 180 * Change an existing SAP entry. If a clone exist for the old one, 181 * check if it is cheaper. If it is change tothe clone, otherwise 182 * delete all the clones. 183 */ 184void 185sap_change(struct sap_entry *sap, 186 struct sap_info *si, 187 struct sockaddr *from) 188{ 189 struct sap_entry *osap = NULL; 190 191 FIXLEN(from); 192 TRACE_SAP_ACTION("CHANGE FROM", sap); 193 /* 194 * If the hopcount (metric) is HOPCNT_INFINITY (16) it means that 195 * a service has gone down. We should keep it like that for 30 196 * seconds, so that it will get broadcast and then change to a 197 * clone if one exist. 198 */ 199 if (sap->clone && (ntohs(si->hops) != HOPCNT_INFINITY)) { 200 /* 201 * There are three possibilities: 202 * 1. The new path is cheaper than the old one. 203 * Free all the clones. 204 * 205 * 2. The new path is the same cost as the old ones. 206 * If it is on the list of clones remove it 207 * from the clone list and free it. 208 * 209 * 3. The new path is more expensive than the old one. 210 * Use the values of the first clone and take it 211 * out of the list, to be freed at the end. 212 */ 213 osap = sap->clone; 214 if (ntohs(osap->sap.hops) > ntohs(si->hops)) { 215 struct sap_entry *nsap; 216 217 while (osap) { 218 nsap = osap->clone; 219 TRACE_SAP_ACTION("DELETE", osap); 220 free(osap); 221 osap = nsap; 222 } 223 sap->clone = NULL; 224 } else if (ntohs(osap->sap.hops) == ntohs(si->hops)) { 225 struct sap_entry *psap; 226 227 psap = sap; 228 while (osap) { 229 if (equal(&osap->source, from)) { 230 psap->clone = osap->clone; 231 TRACE_SAP_ACTION("DELETE", osap); 232 free(osap); 233 osap = psap->clone; 234 } else { 235 psap = osap; 236 osap = osap->clone; 237 } 238 } 239 } else { 240 from = &osap->source; 241 si = &osap->sap; 242 sap->clone = osap->clone; 243 } 244 } 245 sap->sap = *si; 246 sap->source = *from; 247 sap->ifp = if_ifwithnet(from); 248 sap->state = RTS_CHANGED; 249 if (ntohs(si->hops) == HOPCNT_INFINITY) 250 sap->timer = EXPIRE_TIME; 251 else 252 sap->timer = 0; 253 254 if (osap) { 255 TRACE_SAP_ACTION("DELETE", osap); 256 free(osap); 257 } 258 TRACE_SAP_ACTION("CHANGE TO", sap); 259} 260 261/* 262 * Add a clone to the specified SAP entry. A clone is a different 263 * route to the same service. We must know about them when we use 264 * the split horizon algorithm. 265 * 266 * If the malloc fail, the entry will silently be thrown away. 267 */ 268void 269sap_add_clone(struct sap_entry *sap, 270 struct sap_info *clone, 271 struct sockaddr *from) 272{ 273 register struct sap_entry *nsap; 274 register struct sap_entry *csap; 275 276 if (ntohs(clone->hops) == HOPCNT_INFINITY) 277 return; 278 279 FIXLEN(from); 280 nsap = malloc(sizeof(struct sap_entry)); 281 if (nsap == NULL) 282 return; 283 284 if (ftrace) 285 fprintf(ftrace, "CLONE ADD %4.4X %s.\n", 286 ntohs(clone->ServType), 287 clone->ServName); 288 289 nsap->sap = *clone; 290 nsap->source = *from; 291 nsap->clone = NULL; 292 nsap->ifp = if_ifwithnet(from); 293 nsap->state = RTS_CHANGED; 294 nsap->timer = 0; 295 nsap->hash = saphash(clone->ServType, clone->ServName); 296 297 csap = sap; 298 while (csap->clone) 299 csap = csap->clone; 300 csap->clone = nsap; 301 TRACE_SAP_ACTION("ADD CLONE", nsap); 302} 303 304/* 305 * Remove a SAP entry from the table and free the memory 306 * used by it. 307 * 308 * If the service have clone, do a sap_change to it and free 309 * the clone. 310 */ 311void 312sap_delete(struct sap_entry *sap) 313{ 314 if (sap->clone) { 315 sap_change(sap, &sap->clone->sap, &sap->clone->source); 316 return; 317 } 318 remque(sap); 319 TRACE_SAP_ACTION("DELETE", sap); 320 free(sap); 321} 322