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

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);
+}
+