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