usr.sbin/IPXrouted/sap_tables.c

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