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