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 <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         struct sap_entry *sap;
  97         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         struct sap_entry *sap;
 127         struct sap_entry *csap;
 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 next:;
 144                 }
 145         return best;
 146 }
 147
 148 /*
 149  * Add a entry to the SAP table.
 150  *
 151  * If the malloc fail, the entry will silently be thrown away.
 152  */
 153 void
 154 sap_add(struct sap_info *si, struct sockaddr *from)
 155 {
 156         struct sap_entry *nsap;
 157         struct sap_hash *sh;
 158
 159         if (ntohs(si->hops) == HOPCNT_INFINITY)
 160                 return;
 161
 162         FIXLEN(from);
 163         nsap = malloc(sizeof(struct sap_entry));
 164         if (nsap == NULL)
 165                 return;
 166
 167         nsap->sap = *si;
 168         nsap->source = *from;
 169         nsap->clone = NULL;
 170         nsap->ifp = if_ifwithnet(from);
 171         nsap->state = RTS_CHANGED;
 172         nsap->timer = 0;
 173         nsap->hash = saphash(si->ServType, si->ServName);
 174
 175         sh = &sap_head[nsap->hash & SAPHASHMASK];
 176
 177         insque(nsap, sh);
 178         TRACE_SAP_ACTION("ADD", nsap);
 179 }
 180
 181 /*
 182  * Change an existing SAP entry. If a clone exist for the old one,
 183  * check if it is cheaper. If it is change tothe clone, otherwise
 184  * delete all the clones.
 185  */
 186 void
 187 sap_change(struct sap_entry *sap,
 188            struct sap_info *si,
 189            struct sockaddr *from)
 190 {
 191         struct sap_entry *osap = NULL;
 192
 193         FIXLEN(from);
 194         TRACE_SAP_ACTION("CHANGE FROM", sap);
 195         /*
 196          * If the hopcount (metric) is HOPCNT_INFINITY (16) it means that
 197          * a service has gone down. We should keep it like that for 30
 198          * seconds, so that it will get broadcast and then change to a
 199          * clone if one exist.
 200          */
 201         if (sap->clone && (ntohs(si->hops) != HOPCNT_INFINITY)) {
 202                 /*
 203                  * There are three possibilities:
 204                  * 1. The new path is cheaper than the old one.
 205                  *      Free all the clones.
 206                  *
 207                  * 2. The new path is the same cost as the old ones.
 208                  *      If it is on the list of clones remove it
 209                  *      from the clone list and free it.
 210                  *
 211                  * 3. The new path is more expensive than the old one.
 212                  *      Use the values of the first clone and take it
 213                  *      out of the list, to be freed at the end.
 214                  */
 215                 osap = sap->clone;
 216                 if (ntohs(osap->sap.hops) > ntohs(si->hops)) {
 217                         struct sap_entry *nsap;
 218
 219                         while (osap) {
 220                                 nsap = osap->clone;
 221                                 TRACE_SAP_ACTION("DELETE", osap);
 222                                 free(osap);
 223                                 osap = nsap;
 224                         }
 225                         sap->clone = NULL;
 226                 } else if (ntohs(osap->sap.hops) == ntohs(si->hops)) {
 227                         struct sap_entry *psap;
 228
 229                         psap = sap;
 230                         while (osap) {
 231                                 if (equal(&osap->source, from)) {
 232                                         psap->clone = osap->clone;
 233                                         TRACE_SAP_ACTION("DELETE", osap);
 234                                         free(osap);
 235                                         osap = psap->clone;
 236                                 } else {
 237                                         psap = osap;
 238                                         osap = osap->clone;
 239                                 }
 240                         }
 241                 } else {
 242                 from = &osap->source;
 243                 si = &osap->sap;
 244                 sap->clone = osap->clone;
 245                 }
 246         }
 247         sap->sap = *si;
 248         sap->source = *from;
 249         sap->ifp = if_ifwithnet(from);
 250         sap->state = RTS_CHANGED;
 251         if (ntohs(si->hops) == HOPCNT_INFINITY)
 252                 sap->timer = EXPIRE_TIME;
 253         else
 254                 sap->timer = 0;
 255
 256         if (osap) {
 257                 TRACE_SAP_ACTION("DELETE", osap);
 258                 free(osap);
 259         }
 260         TRACE_SAP_ACTION("CHANGE TO", sap);
 261 }
 262
 263 /*
 264  * Add a clone to the specified SAP entry. A clone is a different
 265  * route to the same service. We must know about them when we use
 266  * the split horizon algorithm.
 267  *
 268  * If the malloc fail, the entry will silently be thrown away.
 269  */
 270 void
 271 sap_add_clone(struct sap_entry *sap,
 272               struct sap_info *clone,
 273               struct sockaddr *from)
 274 {
 275         struct sap_entry *nsap;
 276         struct sap_entry *csap;
 277
 278         if (ntohs(clone->hops) == HOPCNT_INFINITY)
 279                 return;
 280
 281         FIXLEN(from);
 282         nsap = malloc(sizeof(struct sap_entry));
 283         if (nsap == NULL)
 284                 return;
 285
 286         if (ftrace)
 287                 fprintf(ftrace, "CLONE ADD %04.4X %s.\n",
 288                         ntohs(clone->ServType),
 289                         clone->ServName);
 290
 291         nsap->sap = *clone;
 292         nsap->source = *from;
 293         nsap->clone = NULL;
 294         nsap->ifp = if_ifwithnet(from);
 295         nsap->state = RTS_CHANGED;
 296         nsap->timer = 0;
 297         nsap->hash = saphash(clone->ServType, clone->ServName);
 298
 299         csap = sap;
 300         while (csap->clone)
 301                 csap = csap->clone;
 302         csap->clone = nsap;
 303         TRACE_SAP_ACTION("ADD CLONE", nsap);
 304 }
 305
 306 /*
 307  * Remove a SAP entry from the table and free the memory
 308  * used by it.
 309  *
 310  * If the service have clone, do a sap_change to it and free
 311  * the clone.
 312  */
 313 void
 314 sap_delete(struct sap_entry *sap)
 315 {
 316         if (sap->clone) {
 317                 sap_change(sap, &sap->clone->sap, &sap->clone->source);
 318                 return;
 319         }
 320         remque(sap);
 321         TRACE_SAP_ACTION("DELETE", sap);
 322         free(sap);
 323 }