summaryrefslogtreecommitdiffstats
path: root/usr.sbin/IPXrouted/sap_tables.c
diff options
context:
space:
mode:
authorjulian <julian@FreeBSD.org>1995-10-26 21:28:30 +0000
committerjulian <julian@FreeBSD.org>1995-10-26 21:28:30 +0000
commit08d0610487a6192a11d0803de49d2ed6e9dd16f7 (patch)
treeb6b74427d5d1f5b58e8bf31836a53d1e4cf3c2c2 /usr.sbin/IPXrouted/sap_tables.c
parent90ae06d6ac1d2da3758389a70a20c91f3e9fd1dc (diff)
downloadFreeBSD-src-08d0610487a6192a11d0803de49d2ed6e9dd16f7.zip
FreeBSD-src-08d0610487a6192a11d0803de49d2ed6e9dd16f7.tar.gz
Reviewed by: julian and Mike Mitchel
Submitted by: john Hay (John.Hay@csir.co.za) John's IPXrouted.. this has not yet been seen to run correctly with Mike's IPX/SPX code (he has his own) bringing them both in is the first step in merging the two packages for 2.2
Diffstat (limited to 'usr.sbin/IPXrouted/sap_tables.c')
-rw-r--r--usr.sbin/IPXrouted/sap_tables.c326
1 files changed, 326 insertions, 0 deletions
diff --git a/usr.sbin/IPXrouted/sap_tables.c b/usr.sbin/IPXrouted/sap_tables.c
new file mode 100644
index 0000000..4f64a4c
--- /dev/null
+++ b/usr.sbin/IPXrouted/sap_tables.c
@@ -0,0 +1,326 @@
+/*
+ * Copyright (c) 1995 John Hay. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by John Hay.
+ * 4. Neither the name of the author nor the names of any co-contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY John Hay AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL John Hay OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $Id: sap_tables.c,v 1.9 1995/10/11 18:57:29 jhay Exp $
+ */
+
+#include "defs.h"
+#include <string.h>
+#include <stdlib.h>
+/* XXX I thought that this should work! #include <sys/systm.h> */
+#include <machine/cpufunc.h>
+
+#define FIXLEN(s) { if ((s)->sa_len == 0) (s)->sa_len = sizeof (*(s));}
+
+sap_hash sap_head[SAPHASHSIZ];
+
+void
+sapinit(void)
+{
+ int i;
+
+ for (i=0; i<SAPHASHSIZ; i++)
+ sap_head[i].forw = sap_head[i].back =
+ (struct sap_entry *)&sap_head[i];
+}
+
+/*
+ * XXX Make sure that this hash is good enough.
+ *
+ * This hash use the first 8 letters of the ServName and the ServType
+ * to create a 32 bit hash value.
+ *
+ * NOTE: The first two letters of ServName will be used to generate
+ * the lower bits of the hash. This is used to index into the hash table.
+ */
+#define rol(x) (((x * 2) & 0xFFFF) + ((x & 0x8000) != 0))
+
+int
+saphash(u_short ServType, char *ServName)
+{
+ int hsh, i;
+ char name[SERVNAMELEN];
+
+ bzero(name, SERVNAMELEN);
+ strncpy(name, ServName, SERVNAMELEN);
+ ServName = name;
+
+ hsh = 0;
+
+ for (i=0;i<8;i++) {
+ hsh = rol(hsh) + *ServName;
+ ServName++;
+ }
+
+ hsh = rol(hsh) + (ServType >> 8);
+ hsh = rol(hsh) + (ServType & 0xff);
+ hsh = (hsh >> 7) ^ hsh;
+ return hsh;
+}
+
+/*
+ * Look for an exact match on ServType and ServName. It is
+ * mostly used by the function that process SAP RESPONSE packets.
+ *
+ * A hash is created and used to index into the hash table. Then
+ * that list is walk through searching for a match.
+ *
+ * If no match is found NULL is returned.
+ */
+struct sap_entry *
+sap_lookup(u_short ServType, char *ServName)
+{
+ register struct sap_entry *sap;
+ register struct sap_hash *sh;
+ int hsh;
+
+ hsh = saphash(ServType, ServName);
+ sh = &sap_head[hsh & SAPHASHMASK];
+
+ for(sap = sh->forw; sap != (sap_entry *)sh; sap = sap->forw) {
+ if ((hsh == sap->hash) &&
+ (ServType == sap->sap.ServType) &&
+ (strncmp(ServName, sap->sap.ServName, SERVNAMELEN) == 0)) {
+ return sap;
+ }
+ }
+ return NULL;
+}
+
+/*
+ * This returns the nearest service of the specified type. If no
+ * suitable service is found or if that service is on the interface
+ * where the request came from, NULL is returned.
+ *
+ * When checking interfaces clones must be considered also.
+ *
+ * XXX TODO:
+ * Maybe we can use RIP tables to get the fastest service (ticks).
+ */
+struct sap_entry *
+sap_nearestserver(ushort ServType, struct interface *ifp)
+{
+ register struct sap_entry *sap;
+ register struct sap_entry *csap;
+ struct sap_hash *sh;
+ register struct sap_entry *best = NULL;
+ register int besthops = HOPCNT_INFINITY;
+
+ sh = sap_head;
+
+ for (; sh < &sap_head[SAPHASHSIZ]; sh++)
+ for(sap = sh->forw; sap != (sap_entry *)sh; sap = sap->forw) {
+ if (ServType != sap->sap.ServType)
+ continue;
+ if (ifp == sap->ifp)
+ continue;
+
+ csap = sap->clone;
+ while (csap) {
+ if (ifp == csap->ifp)
+ /*
+ * I would have loved to use
+ * something else here.
+ */
+ goto next;
+ csap = csap->clone;
+ }
+
+ if (ntohs(sap->sap.hops) < besthops) {
+ best = sap;
+ besthops = ntohs(best->sap.hops);
+ }
+next:;
+ }
+ return best;
+}
+
+/*
+ * Add a entry to the SAP table.
+ *
+ * If the malloc fail, the entry will silently be thrown away.
+ */
+void
+sap_add(struct sap_info *si, struct sockaddr *from)
+{
+ register struct sap_entry *nsap;
+ register struct sap_hash *sh;
+
+ FIXLEN(from);
+ nsap = malloc(sizeof(struct sap_entry));
+ if (nsap == NULL)
+ return;
+
+ nsap->sap = *si;
+ nsap->source = *from;
+ nsap->clone = NULL;
+ nsap->ifp = if_ifwithnet(from);
+ nsap->state = RTS_CHANGED;
+ nsap->timer = 0;
+ nsap->hash = saphash(si->ServType, si->ServName);
+
+ sh = &sap_head[nsap->hash & SAPHASHMASK];
+
+ insque(nsap, sh);
+}
+
+/*
+ * Change an existing SAP entry. If a clone exist for the old one,
+ * check if it is cheaper. If it is change tothe clone, otherwise
+ * delete all the clones.
+ */
+void
+sap_change(struct sap_entry *sap,
+ struct sap_info *si,
+ struct sockaddr *from)
+{
+ struct sap_entry *osap = NULL;
+
+ FIXLEN(from);
+ /*
+ * If the hopcount (metric) is HOPCNT_INFINITY (16) it means that
+ * a service has gone down. We should keep it like that for 30
+ * seconds, so that it will get broadcast and then change to a
+ * clone if one exist.
+ */
+ if (sap->clone && (ntohs(si->hops) != HOPCNT_INFINITY)) {
+ /*
+ * There are three possibilities:
+ * 1. The new path is cheaper than the old one.
+ * Free all the clones.
+ *
+ * 2. The new path is the same cost as the old ones.
+ * If it is on the list of clones remove it
+ * from the clone list and free it.
+ *
+ * 3. The new path is more expensive than the old one.
+ * Use the values of the first clone and take it
+ * out of the list, to be freed at the end.
+ */
+ osap = sap->clone;
+ if (ntohs(osap->sap.hops) > ntohs(si->hops)) {
+ struct sap_entry *nsap;
+
+ while (osap) {
+ nsap = osap->clone;
+ free(osap);
+ osap = nsap;
+ }
+ sap->clone = NULL;
+ } else if (ntohs(osap->sap.hops) == ntohs(si->hops)) {
+ struct sap_entry *psap;
+
+ psap = sap;
+ while (osap) {
+ if (equal(&osap->source, from)) {
+ psap->clone = osap->clone;
+ free(osap);
+ osap = psap->clone;
+ } else {
+ psap = osap;
+ osap = osap->clone;
+ }
+ }
+ } else {
+ from = &osap->source;
+ si = &osap->sap;
+ sap->clone = osap->clone;
+ }
+ }
+ sap->sap = *si;
+ sap->source = *from;
+ sap->ifp = if_ifwithnet(from);
+ sap->state = RTS_CHANGED;
+ if (ntohs(si->hops) == HOPCNT_INFINITY)
+ sap->timer = EXPIRE_TIME;
+ else
+ sap->timer = 0;
+
+ if (osap)
+ free(osap);
+}
+
+/*
+ * Add a clone to the specified SAP entry. A clone is a different
+ * route to the same service. We must know about them when we use
+ * the split horizon algorithm.
+ *
+ * If the malloc fail, the entry will silently be thrown away.
+ */
+void
+sap_add_clone(struct sap_entry *sap,
+ struct sap_info *clone,
+ struct sockaddr *from)
+{
+ register struct sap_entry *nsap;
+ register struct sap_entry *csap;
+
+ FIXLEN(from);
+ nsap = malloc(sizeof(struct sap_entry));
+ if (nsap == NULL)
+ return;
+
+ if (ftrace)
+ fprintf(ftrace, "CLONE ADD %04.4X %s.\n",
+ ntohs(clone->ServType),
+ clone->ServName);
+
+ nsap->sap = *clone;
+ nsap->source = *from;
+ nsap->clone = NULL;
+ nsap->ifp = if_ifwithnet(from);
+ nsap->state = RTS_CHANGED;
+ nsap->timer = 0;
+ nsap->hash = saphash(clone->ServType, clone->ServName);
+
+ csap = sap;
+ while (csap->clone)
+ csap = csap->clone;
+ csap->clone = nsap;
+}
+
+/*
+ * Remove a SAP entry from the table and free the memory
+ * used by it.
+ *
+ * If the service have clone, do a sap_change to it and free
+ * the clone.
+ */
+void
+sap_delete(struct sap_entry *sap)
+{
+ if (sap->clone) {
+ sap_change(sap, &sap->clone->sap, &sap->clone->source);
+ return;
+ }
+ remque(sap);
+ free(sap);
+}
+
OpenPOWER on IntegriCloud