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