sap_tables.c revision 27244 
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 *	$Id: sap_tables.c,v 1.4 1997/07/01 00:33:41 bde Exp $
32 */
33
34#include "defs.h"
35#include <string.h>
36#include <stdlib.h>
37
38#define FIXLEN(s) { if ((s)->sa_len == 0) (s)->sa_len = sizeof (*(s));}
39
40sap_hash sap_head[SAPHASHSIZ];
41
42void
43sapinit(void)
44{
45	int i;
46
47	for (i=0; i<SAPHASHSIZ; i++)
48		sap_head[i].forw = sap_head[i].back =
49					(struct sap_entry *)&sap_head[i];
50}
51
52/*
53 * This hash use the first 14 letters of the ServName and the ServType
54 * to create a 32 bit hash value.
55 */
56int
57saphash(u_short ServType, char *ServName)
58{
59	int hsh, i;
60	char name[SERVNAMELEN];
61
62	bzero(name, SERVNAMELEN);
63	strncpy(name, ServName, SERVNAMELEN);
64	ServName = name;
65
66	hsh = 0;
67
68#define SMVAL   33
69
70	hsh = hsh * SMVAL + (ServType & 0xff);
71	hsh = hsh * SMVAL + (ServType >> 8);
72
73	for (i=0;i<14;i++) {
74		hsh = hsh * SMVAL + *ServName++;
75		ServName++;
76	}
77
78#undef SMVAL
79
80	return hsh;
81}
82
83/*
84 * Look for an exact match on ServType and ServName. It is
85 * mostly used by the function that process SAP RESPONSE packets.
86 *
87 * A hash is created and used to index into the hash table. Then
88 * that list is walk through searching for a match.
89 *
90 * If no match is found NULL is returned.
91 */
92struct sap_entry *
93sap_lookup(u_short ServType, char *ServName)
94{
95	register struct sap_entry *sap;
96	register struct sap_hash  *sh;
97	int hsh;
98
99	hsh = saphash(ServType, ServName);
100	sh = &sap_head[hsh & SAPHASHMASK];
101
102	for(sap = sh->forw; sap != (sap_entry *)sh; sap = sap->forw) {
103		if ((hsh == sap->hash) &&
104		    (ServType == sap->sap.ServType) &&
105		    (strncmp(ServName, sap->sap.ServName, SERVNAMELEN) == 0)) {
106			return sap;
107		}
108	}
109	return NULL;
110}
111
112/*
113 * This returns the nearest service of the specified type. If no
114 * suitable service is found or if that service is on the interface
115 * where the request came from, NULL is returned.
116 *
117 * When checking interfaces clones must be considered also.
118 *
119 * XXX TODO:
120 * Maybe we can use RIP tables to get the fastest service (ticks).
121 */
122struct sap_entry *
123sap_nearestserver(ushort ServType, struct interface *ifp)
124{
125	register struct sap_entry *sap;
126	register struct sap_entry *csap;
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			if (ifp == sap->ifp)
138				continue;
139
140			csap = sap->clone;
141			while (csap) {
142				if (ifp == csap->ifp)
143					/*
144					 * I would have loved to use
145					 * something else here.
146					 */
147					goto next;
148				csap = csap->clone;
149			}
150
151			if (ntohs(sap->sap.hops) < besthops) {
152				best = sap;
153				besthops = ntohs(best->sap.hops);
154			}
155next:;
156		}
157	return best;
158}
159
160/*
161 * Add a entry to the SAP table.
162 *
163 * If the malloc fail, the entry will silently be thrown away.
164 */
165void
166sap_add(struct sap_info *si, struct sockaddr *from)
167{
168	register struct sap_entry *nsap;
169	register struct sap_hash *sh;
170
171	if (ntohs(si->hops) == HOPCNT_INFINITY)
172		return;
173
174	FIXLEN(from);
175	nsap = malloc(sizeof(struct sap_entry));
176	if (nsap == NULL)
177		return;
178
179	nsap->sap = *si;
180	nsap->source = *from;
181	nsap->clone = NULL;
182	nsap->ifp = if_ifwithnet(from);
183	nsap->state = RTS_CHANGED;
184	nsap->timer = 0;
185	nsap->hash = saphash(si->ServType, si->ServName);
186
187	sh = &sap_head[nsap->hash & SAPHASHMASK];
188
189	insque(nsap, sh);
190	TRACE_SAP_ACTION("ADD", nsap);
191}
192
193/*
194 * Change an existing SAP entry. If a clone exist for the old one,
195 * check if it is cheaper. If it is change tothe clone, otherwise
196 * delete all the clones.
197 */
198void
199sap_change(struct sap_entry *sap,
200           struct sap_info *si,
201           struct sockaddr *from)
202{
203	struct sap_entry *osap = NULL;
204
205	FIXLEN(from);
206	TRACE_SAP_ACTION("CHANGE FROM", sap);
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				TRACE_SAP_ACTION("DELETE", osap);
234				free(osap);
235				osap = nsap;
236			}
237			sap->clone = NULL;
238		} else if (ntohs(osap->sap.hops) == ntohs(si->hops)) {
239			struct sap_entry *psap;
240
241			psap = sap;
242			while (osap) {
243				if (equal(&osap->source, from)) {
244					psap->clone = osap->clone;
245					TRACE_SAP_ACTION("DELETE", osap);
246					free(osap);
247					osap = psap->clone;
248				} else {
249					psap = osap;
250					osap = osap->clone;
251				}
252			}
253		} else {
254		from = &osap->source;
255		si = &osap->sap;
256		sap->clone = osap->clone;
257		}
258	}
259	sap->sap = *si;
260	sap->source = *from;
261	sap->ifp = if_ifwithnet(from);
262	sap->state = RTS_CHANGED;
263	if (ntohs(si->hops) == HOPCNT_INFINITY)
264		sap->timer = EXPIRE_TIME;
265	else
266		sap->timer = 0;
267
268	if (osap) {
269		TRACE_SAP_ACTION("DELETE", osap);
270		free(osap);
271	}
272	TRACE_SAP_ACTION("CHANGE TO", sap);
273}
274
275/*
276 * Add a clone to the specified SAP entry. A clone is a different
277 * route to the same service. We must know about them when we use
278 * the split horizon algorithm.
279 *
280 * If the malloc fail, the entry will silently be thrown away.
281 */
282void
283sap_add_clone(struct sap_entry *sap,
284	      struct sap_info *clone,
285	      struct sockaddr *from)
286{
287	register struct sap_entry *nsap;
288	register struct sap_entry *csap;
289
290	if (ntohs(clone->hops) == HOPCNT_INFINITY)
291		return;
292
293	FIXLEN(from);
294	nsap = malloc(sizeof(struct sap_entry));
295	if (nsap == NULL)
296		return;
297
298	if (ftrace)
299		fprintf(ftrace, "CLONE ADD %04.4X %s.\n",
300			ntohs(clone->ServType),
301			clone->ServName);
302
303	nsap->sap = *clone;
304	nsap->source = *from;
305	nsap->clone = NULL;
306	nsap->ifp = if_ifwithnet(from);
307	nsap->state = RTS_CHANGED;
308	nsap->timer = 0;
309	nsap->hash = saphash(clone->ServType, clone->ServName);
310
311	csap = sap;
312	while (csap->clone)
313		csap = csap->clone;
314	csap->clone = nsap;
315	TRACE_SAP_ACTION("ADD CLONE", nsap);
316}
317
318/*
319 * Remove a SAP entry from the table and free the memory
320 * used by it.
321 *
322 * If the service have clone, do a sap_change to it and free
323 * the clone.
324 */
325void
326sap_delete(struct sap_entry *sap)
327{
328	if (sap->clone) {
329		sap_change(sap, &sap->clone->sap, &sap->clone->source);
330		return;
331	}
332	remque(sap);
333	TRACE_SAP_ACTION("DELETE", sap);
334	free(sap);
335}
336