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 *
| 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 50479 1999-08-28 01:35:59Z peter $
| 31 * $FreeBSD: head/usr.sbin/IPXrouted/sap_tables.c 108533 2003-01-01 18:49:04Z schweikh $
|
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
138 if (ntohs(sap->sap.hops) < besthops) {
139 best = sap;
140 besthops = ntohs(best->sap.hops);
141 }
142next:;
143 }
144 return best;
145}
146
147/*
| 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
138 if (ntohs(sap->sap.hops) < besthops) {
139 best = sap;
140 besthops = ntohs(best->sap.hops);
141 }
142next:;
143 }
144 return best;
145}
146
147/*
|
148 * Add a entry to the SAP table.
| 148 * Add an entry to the SAP table.
|
149 *
150 * If the malloc fail, the entry will silently be thrown away.
151 */
152void
153sap_add(struct sap_info *si, struct sockaddr *from)
154{
155 register struct sap_entry *nsap;
156 register 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 */
185void
186sap_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 */
269void
270sap_add_clone(struct sap_entry *sap,
271 struct sap_info *clone,
272 struct sockaddr *from)
273{
274 register struct sap_entry *nsap;
275 register 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 %04.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 */
312void
313sap_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}
| 149 *
150 * If the malloc fail, the entry will silently be thrown away.
151 */
152void
153sap_add(struct sap_info *si, struct sockaddr *from)
154{
155 register struct sap_entry *nsap;
156 register 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 */
185void
186sap_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 */
269void
270sap_add_clone(struct sap_entry *sap,
271 struct sap_info *clone,
272 struct sockaddr *from)
273{
274 register struct sap_entry *nsap;
275 register 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 %04.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 */
312void
313sap_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}
|