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