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$
  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
  41 sap_hash sap_head[SAPHASHSIZ];
  42
  43 void
  44 sapinit(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  */
  57 int
  58 saphash(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  */
  93 struct sap_entry *
  94 sap_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  */
 123 struct sap_entry *
 124 sap_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  */
 151 void
 152 sap_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 to the clone, otherwise
 182  * delete all the clones.
 183  */
 184 void
 185 sap_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  */
 268 void
 269 sap_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  */
 311 void
 312 sap_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 }