1 /*
2 ipr.c
3 Copyright 1995 Philip Homburg
4 */
5 #include "inet.h"
6 #include "clock.h"
7 #include "type.h"
8 #include "assert.h"
9 #include "buf.h"
10 #include "event.h"
11 #include "io.h"
12 #include "ip_int.h"
13 #include "ipr.h"
14 THIS_FILE
OROUTE_NR = number of route table entries for outgoing packets permitted.
15 #define OROUTE_NR 32
OROUTE_STATIC_NR = number of static route table entries for outgoing packets permitted.
16 #define OROUTE_STATIC_NR 16
17 #define OROUTE_HASH_ASS_NR 4
18 #define OROUTE_HASH_NR 32
19 #define OROUTE_HASH_MASK (OROUTE_HASH_NR-1)
20 #define hash_oroute(port_nr, ipaddr, hash_tmp) (hash_tmp= (ipaddr), \
21 hash_tmp= (hash_tmp >> 20) ^ hash_tmp, \
22 hash_tmp= (hash_tmp >> 10) ^ hash_tmp, \
23 hash_tmp= (hash_tmp >> 5) ^ hash_tmp, \
24 (hash_tmp + (port_nr)) & OROUTE_HASH_MASK)
25 typedef struct oroute_hash
26 {
27 ipaddr_t orh_addr;
28 oroute_t *orh_route;
29 } oroute_hash_t;
oroute_table handles the routing for outgoing packets. It stores the data which
would be seen if one typed "route print" in a windows machine.
ort_port: index in to ip_port_table. Index of which ip port it belongs to.
ort_dest: the destination ip address for the route. This ip address typically
represents a subnet or network. Therefore the last several digits of the ip address
would be zero. This route is used only if the destination address of the packet
belongs to the subnet or network represented by the ip address ort_dest.
ort_gateway: ip address to route all packets which use this route.
ort_subnetmask: subnet mask of route. Used with ort_dest to determine whether or
not a packet should use this route.
ort_dist: route distance. Used to determine which route is best.
ort_pref: used to determine which route is best(???). Not certain.
ort_exp_tim: expiration time for route. No longer used if current time is later than
ort_exp_tim. Set to 0 if route has no expiration time.
ort_timestamp: time that the route was added.
ort_flags: flags to store information about route.
ort_nextnw: next pointer in linked list of oroute entries which are being used.
ort_nextgw: next pointer in linked list of oroute entries which are being used and have the same
ort_port, ort_dest, and ort_subnetmask.
ort_nextdist: next pointer in linked list of oroute entries which are being used and have the same
ort_port, ort_dest, ort_subnetmask, and ort_gateway.
30 PRIVATE oroute_t oroute_table[OROUTE_NR];
Head of linked list of oroute_table table entries. Next pointer is ort_nextnw.
31 PRIVATE oroute_t *oroute_head;
32 PRIVATE int static_oroute_nr;
oroute_hash_table stores recently used routes.
oroute_hash_table handles the routing for outgoing packets.
33 PRIVATE oroute_hash_t oroute_hash_table[OROUTE_HASH_NR][OROUTE_HASH_ASS_NR];
34 #define IROUTE_NR (sizeof(int) == 2 ? 64 : 512)
35 #define IROUTE_HASH_ASS_NR 4
36 #define IROUTE_HASH_NR 32
37 #define IROUTE_HASH_MASK (IROUTE_HASH_NR-1)
38 #define hash_iroute(port_nr, ipaddr, hash_tmp) (hash_tmp= (ipaddr), \
39 hash_tmp= (hash_tmp >> 20) ^ hash_tmp, \
40 hash_tmp= (hash_tmp >> 10) ^ hash_tmp, \
41 hash_tmp= (hash_tmp >> 5) ^ hash_tmp, \
42 (hash_tmp + (port_nr)) & IROUTE_HASH_MASK)
43 typedef struct iroute_hash
44 {
45 ipaddr_t irh_addr;
46 iroute_t *irh_route;
47 } iroute_hash_t;
iroute_table handles the routing for incoming packets. It forwards packets sent by
other machines ie it lets the compuer act as a router. iroute_table specifies where
to route the packets. The oroute_t structure is defined in inet/generic/ipr.h as follows.
irt_dest: the destination ip address for the route. This ip address typically represents
a subnet or network. Therefore the last several digits of the ip address would be zero.
This route is used only if the destination address of the packet belongs to the subnet
or network represented by the ip address irt_dest.
irt_gateway: ip address to route all packets which use this route.
irt_subnetmask: subnet mask of route. Used with irt_dest to determine
whether or not a packet should use this route.
irt_dist: route distance. Used to determine which route is best.
irt_port: index in to ip_port table. This route is used only for the ip channel which
corresponds to the element in the ip_port_table.
irt_flags: flags to store information about route.
48 PRIVATE iroute_t iroute_table[IROUTE_NR];
iroute_hash_table stores recently used routes.
iroute_hash_table handles the routing for incoming packets.
49 PRIVATE iroute_hash_t iroute_hash_table[IROUTE_HASH_NR][IROUTE_HASH_ASS_NR];
50 FORWARD oroute_t *oroute_find_ent ARGS(( int port_nr, ipaddr_t dest ));
51 FORWARD void oroute_del ARGS(( oroute_t *oroute ));
52 FORWARD oroute_t *sort_dists ARGS(( oroute_t *oroute ));
53 FORWARD oroute_t *sort_gws ARGS(( oroute_t *oroute ));
54 FORWARD oroute_uncache_nw ARGS(( ipaddr_t dest, ipaddr_t netmask ));
55 FORWARD iroute_uncache_nw ARGS(( ipaddr_t dest, ipaddr_t netmask ));
ipr_init(): initialization called in main function of inet.c. Initializes the oroute_table
which handles the routing for outgoing packets and the iroute_table which handles the routing
for incoming packets.
56 PUBLIC void ipr_init()
57 {
58 int i;
59 oroute_t *oroute;
60 iroute_t *iroute;
61 #if ZERO
62 for (i= 0, oroute= oroute_table; i<OROUTE_NR; i++, oroute++)
63 oroute->ort_flags= ORTF_EMPTY;
64 static_oroute_nr= 0;
65 #endif
66 assert(OROUTE_HASH_ASS_NR == 4);
67 #if ZERO
68 for (i= 0, iroute= iroute_table; i<IROUTE_NR; i++, iroute++)
69 iroute->irt_flags= IRTF_EMPTY;
70 #endif
71 assert(IROUTE_HASH_ASS_NR == 4);
72 }
iroute_frag(): returns a pointer to the route table entry (iroute_t) given the ip
port and the destination of the packet for an incoming packet. iroute_frag() is
called in ip_read.c to see if we should forward a received packet ie act as a router.
73 PUBLIC iroute_t *iroute_frag(port_nr, dest)
74 int port_nr;
75 ipaddr_t dest;
76 {
77 int hash, i, r_hash_ind;
78 iroute_hash_t *iroute_hash;
79 iroute_hash_t tmp_hash;
80 iroute_t *iroute, *bestroute;
81 time_t currtim;
82 unsigned long hash_tmp;
83 currtim= get_time();
hash = hash value for iroute_hash_table. iroute_frag checks if the address was stored
in iroute_hash_table which stores recently used routes. iroute_hash_table is used to speed
up looking up the route table.
84 hash= hash_iroute(port_nr, dest, hash_tmp);
85 iroute_hash= &iroute_hash_table[hash][0];
Hash table iroute_hash_table resolves collisions by chaining but there are only 4 elements
in the chain ie iroute_hash_table[hash][0], iroute_hash_table[hash][1], iroute_hash_table[hash][2]
iroute_hash_table[hash][3]. If the address was stored in iroute_hash_table it returns the corresponding
route table entry and the destination is placed at the head of the chain ie iroute_hash_table[hash][0].
Otherwise, iroute_frag checks the array iroute_table for a route which can used for the destination ip
address.
86 if (iroute_hash[0].irh_addr == dest)
87 iroute= iroute_hash[0].irh_route;
88 else if (iroute_hash[1].irh_addr == dest)
89 {
90 tmp_hash= iroute_hash[1];
91 iroute_hash[1]= iroute_hash[0];
92 iroute_hash[0]= tmp_hash;
93 iroute= tmp_hash.irh_route;
94 }
95 else if (iroute_hash[2].irh_addr == dest)
96 {
97 tmp_hash= iroute_hash[2];
98 iroute_hash[2]= iroute_hash[1];
99 iroute_hash[1]= iroute_hash[0];
100 iroute_hash[0]= tmp_hash;
101 iroute= tmp_hash.irh_route;
102 }
103 else if (iroute_hash[3].irh_addr == dest)
104 {
105 tmp_hash= iroute_hash[3];
106 iroute_hash[3]= iroute_hash[2];
107 iroute_hash[2]= iroute_hash[1];
108 iroute_hash[1]= iroute_hash[0];
109 iroute_hash[0]= tmp_hash;
110 iroute= tmp_hash.irh_route;
111 }
112 else
113 iroute= NULL;
114 if (iroute)
115 return iroute;
116 bestroute= NULL;
iroute_frag checks the array iroute_table for a route which can used for the destination
ip address.
117 for (i= 0, iroute= iroute_table; i < IROUTE_NR; i++, iroute++)
118 {
119 if (!(iroute->irt_flags & IRTF_INUSE))
120 continue;
((dest ^ iroute->irt_dest) & iroute->irt_subnetmask) != 0 means
route belongs on the same subnet as the destination ip address.
121 if (((dest ^ iroute->irt_dest) & iroute->irt_subnetmask) != 0)
122 continue;
123 if (!bestroute)
124 {
125 bestroute= iroute;
126 continue;
127 }
128 /* More specific netmasks are better */
129 if (iroute->irt_subnetmask != bestroute->irt_subnetmask)
130 {
131 if (ntohl(iroute->irt_subnetmask) >
132 ntohl(bestroute->irt_subnetmask))
133 {
134 bestroute= iroute;
135 }
136 continue;
137 }
138
139 /* Dynamic routes override static routes */
140 if ((iroute->irt_flags & IRTF_STATIC) !=
141 (bestroute->irt_flags & IRTF_STATIC))
142 {
143 if (bestroute->irt_flags & IRTF_STATIC)
144 bestroute= iroute;
145 continue;
146 }
147 /* A route to the local interface give an opportunity
148 * to send redirects.
149 */
150 if (iroute->irt_port != bestroute->irt_port)
151 {
152 if (iroute->irt_port == port_nr)
153 bestroute= iroute;
154 continue;
155 }
156 }
157 if (bestroute == NULL)
158 return NULL;
The destination is placed at the head of the chain ie iroute_hash_table[hash][0].
Last member of chain is removed.
159 iroute_hash[3]= iroute_hash[2];
160 iroute_hash[2]= iroute_hash[1];
161 iroute_hash[1]= iroute_hash[0];
162 iroute_hash[0].irh_addr= dest;
163 iroute_hash[0].irh_route= bestroute;
164 return bestroute;
165 }
oroute_frag():oroute_frag does the same thing as iroute_frag only for outgoing packets.
oroute_frag() returns a pointer to the route table entry (oroute_t) given the ip
channel and the destination of the packet for an outgoing packet. oroute_frag() is
called in ip_write.c to see where we should send a packet.
It does this by calling oroute_find_ent.
166 PUBLIC int oroute_frag(port_nr, dest, ttl, nexthop)
167 int port_nr;
168 ipaddr_t dest;
169 int ttl;
170 ipaddr_t *nexthop;
171 {
172 oroute_t *oroute;
173 oroute= oroute_find_ent(port_nr, dest);
174 if (!oroute || oroute->ort_dist > ttl)
175 return EDSTNOTRCH;
176 *nexthop= oroute->ort_gateway;
177 return NW_OK;
178 }
ipr_add_oroute(): ipr_add_oroute adds a route to the oroute_table which handles
outgoing packets. It implements the ioctl system call on an IP device with request
NWIOSIPOROUTE.
179 PUBLIC int ipr_add_oroute(port_nr, dest, subnetmask, gateway,
180 timeout, dist, static_route, preference, oroute_p)
181 int port_nr;
182 ipaddr_t dest;
183 ipaddr_t subnetmask;
184 ipaddr_t gateway;
185 time_t timeout;
186 int dist;
187 int static_route;
188 i32_t preference;
189 oroute_t **oroute_p;
190 {
191 int i;
192 ip_port_t *ip_port;
193 oroute_t *oroute, *oldest_route, *prev, *nw_route, *gw_route,
194 *prev_route;
195 time_t currtim;
196 oldest_route= 0;
197 currtim= get_time();
198 DBLOCK(0x10,
199 printf("adding oroute to "); writeIpAddr(dest);
200 printf("["); writeIpAddr(subnetmask); printf("] through ");
201 writeIpAddr(gateway);
202 printf(" timeout: %lds, distance %d\n",
203 (long)timeout/HZ, dist));
204 ip_port= &ip_port_table[port_nr];
First it checks if the gateway is on the same subnet as the destination address.
205 /* Validate gateway */
206 if (((gateway ^ ip_port->ip_ipaddr) & ip_port->ip_subnetmask) != 0)
207 {
208 DBLOCK(2, printf("ipr_add_oroute: invalid gateway: "); writeIpAddr(gateway); printf("\n"));
209 return EINVAL;
210 }
Static routes are always added as new routes.
211 if (static_route)
212 {
213 if (static_oroute_nr >= OROUTE_STATIC_NR)
214 return ENOMEM;
215 static_oroute_nr++;
216 }
217 else
Non-static routes modify old routes only if an old route has the same ip port,
destination address, subnet mask, gateway, and distance < dist.
218 {
219 /* Try to track down any old routes. */
220 for(oroute= oroute_head; oroute; oroute= oroute->ort_nextnw)
221 {
222 if (oroute->ort_port != port_nr)
223 continue;
224 if (oroute->ort_dest == dest &&
225 oroute->ort_subnetmask == subnetmask)
226 {
227 break;
228 }
229 }
If oroute != NULL, then oroute = head of linked list of oroute entries which have
the same ip port (ie network interface), network, and subnet.
230 for(; oroute; oroute= oroute->ort_nextgw)
231 {
232 if (oroute->ort_gateway == gateway)
233 break;
234 }
If oroute != NULL, then oroute = head of linked list of oroute entries which have
the same ip port (ie network interface), network, subnet, and gateway.
235 for(; oroute; oroute= oroute->ort_nextdist)
236 {
237 if ((oroute->ort_flags & ORTF_STATIC) != 0)
238 continue;
239 if (oroute->ort_dist > dist)
240 continue;
241 if (oroute->ort_dist == dist &&
242 oroute->ort_pref == preference)
243 {
244 if (timeout)
245 oroute->ort_exp_tim= currtim + timeout;
246 else
247 oroute->ort_exp_tim= 0;
248 oroute->ort_timestamp= currtim;
249 assert(oroute->ort_port == port_nr);
250 if (oroute_p != NULL)
251 *oroute_p= oroute;
252 return NW_OK;
253 }
254 break;
255 }
Delete old route oldest_route and replace with new route if found match.
256 if (oroute)
257 {
258 assert(oroute->ort_port == port_nr);
259 oroute_del(oroute);
260 oroute->ort_flags= 0;
261 oldest_route= oroute;
262 }
263 }
264 if (oldest_route == NULL)
No route in oroute_table is found which matches. A new route is added.
265 {
266 /* Look for an unused entry, or remove an existing one */
267 for (i= 0, oroute= oroute_table; i<OROUTE_NR; i++, oroute++)
268 {
269 if ((oroute->ort_flags & ORTF_INUSE) == 0)
270 break;
271 if (oroute->ort_exp_tim && oroute->ort_exp_tim <
272 currtim)
273 {
274 oroute_del(oroute);
275 oroute->ort_flags= 0;
276 break;
277 }
278 if (oroute->ort_flags & ORTF_STATIC)
279 continue;
280 if (oroute->ort_dest == 0)
281 {
282 /* Never remove default routes. */
283 continue;
284 }
285 if (oldest_route == NULL)
286 {
287 oldest_route= oroute;
288 continue;
289 }
290 if (oroute->ort_timestamp < oldest_route->ort_timestamp)
291 {
292 oldest_route= oroute;
293 }
294 }
295 if (i < OROUTE_NR)
296 oldest_route= oroute;
297 else
298 {
299 assert(oldest_route);
300 oroute_del(oldest_route);
301 oldest_route->ort_flags= 0;
302 }
303 }
oldest_route = route entry to copy new route to. Set oldest_route to the proper values.
304 oldest_route->ort_dest= dest;
305 oldest_route->ort_gateway= gateway;
306 oldest_route->ort_subnetmask= subnetmask;
307 if (timeout)
308 oldest_route->ort_exp_tim= currtim + timeout;
309 else
310 oldest_route->ort_exp_tim= 0;
311 oldest_route->ort_timestamp= currtim;
312 oldest_route->ort_dist= dist;
313 oldest_route->ort_port= port_nr;
314 oldest_route->ort_flags= ORTF_INUSE;
315 oldest_route->ort_pref= preference;
316 if (static_route)
317 oldest_route->ort_flags |= ORTF_STATIC;
318
319 /* Insert the route by tearing apart the routing table,
320 * and insert the entry during the reconstruction.
321 */
Insert the route. Sort the lists by calling sort_dists() and sort_gws() while inserting.
322 for (prev= 0, nw_route= oroute_head; nw_route;
323 prev= nw_route, nw_route= nw_route->ort_nextnw)
324 {
325 if (nw_route->ort_port != port_nr)
326 continue;
327 if (nw_route->ort_dest == dest &&
328 nw_route->ort_subnetmask == subnetmask)
329 {
330 if (prev)
331 prev->ort_nextnw= nw_route->ort_nextnw;
332 else
333 oroute_head= nw_route->ort_nextnw;
334 break;
335 }
336 }
337 prev_route= nw_route;
338 for(prev= NULL, gw_route= nw_route; gw_route;
339 prev= gw_route, gw_route= gw_route->ort_nextgw)
340 {
341 if (gw_route->ort_gateway == gateway)
342 {
343 if (prev)
344 prev->ort_nextgw= gw_route->ort_nextgw;
345 else
346 nw_route= gw_route->ort_nextgw;
347 break;
348 }
349 }
350 oldest_route->ort_nextdist= gw_route;
351 gw_route= oldest_route;
352 gw_route= sort_dists(gw_route);
353 gw_route->ort_nextgw= nw_route;
354 nw_route= gw_route;
355 nw_route= sort_gws(nw_route);
356 nw_route->ort_nextnw= oroute_head;
357 oroute_head= nw_route;
358 if (nw_route != prev_route)
359 oroute_uncache_nw(nw_route->ort_dest, nw_route->ort_subnetmask);
360 if (oroute_p != NULL)
361 *oroute_p= oldest_route;
362 return NW_OK;
363 }
ipr_gateway_down(): ipr_gateway_down is called to notify the routing table for outgoing packets that a gateway is down.
364 PUBLIC void ipr_gateway_down(port_nr, gateway, timeout)
365 int port_nr;
366 ipaddr_t gateway;
367 time_t timeout;
368 {
369 oroute_t *route_ind;
370 time_t currtim;
371 int i;
372 int result;
373 currtim= get_time();
374 for (i= 0, route_ind= oroute_table; i<OROUTE_NR; i++, route_ind++)
375 {
376 if (!(route_ind->ort_flags & ORTF_INUSE))
377 continue;
378 if (route_ind->ort_gateway != gateway)
379 continue;
380 if (route_ind->ort_exp_tim && route_ind->ort_exp_tim < currtim)
381 continue;
382 result= ipr_add_oroute(port_nr, route_ind->ort_dest,
383 route_ind->ort_subnetmask, gateway,
384 timeout, ORTD_UNREACHABLE, FALSE, 0, NULL);
385 assert(result == NW_OK);
386 }
387 }
ipr_destunrch(): ipr_destunrch is called to notify the routing table for outgoing packets that a destination is unreachable.
388 PUBLIC void ipr_destunrch(port_nr, dest, netmask, timeout)
389 int port_nr;
390 ipaddr_t dest;
391 ipaddr_t netmask;
392 time_t timeout;
393 {
394 oroute_t *oroute;
395 int result;
396 oroute= oroute_find_ent(port_nr, dest);
397 if (!oroute)
398 {
399 DBLOCK(1, printf("got a dest unreachable for ");
400 writeIpAddr(dest); printf("but no route present\n"));
401 return;
402 }
403 result= ipr_add_oroute(port_nr, dest, netmask, oroute->ort_gateway,
404 timeout, ORTD_UNREACHABLE, FALSE, 0, NULL);
405 assert(result == NW_OK);
406 }
ipr_redirect(): ipr_redirect is called to notify the routing table for outgoing packets that
the gateway for a old destination is unreachable and that a new gateway is being used.
407 PUBLIC void ipr_redirect(port_nr, dest, netmask, old_gateway, new_gateway,
408 timeout)
409 int port_nr;
410 ipaddr_t dest;
411 ipaddr_t netmask;
412 ipaddr_t old_gateway;
413 ipaddr_t new_gateway;
414 time_t timeout;
415 {
416 oroute_t *oroute;
417 int result;
418 oroute= oroute_find_ent(port_nr, dest);
419 if (!oroute)
420 {
421 DBLOCK(1, printf("got a redirect for ");
422 writeIpAddr(dest); printf("but no route present\n"));
423 return;
424 }
425 if (oroute->ort_gateway != old_gateway)
426 {
427 DBLOCK(1, printf("got a redirect from ");
428 writeIpAddr(old_gateway); printf(" for ");
429 writeIpAddr(dest); printf(" but curr gateway is ");
430 writeIpAddr(oroute->ort_gateway); printf("\n"));
431 return;
432 }
433 if (oroute->ort_flags & ORTF_STATIC)
434 {
435 if (oroute->ort_dest == dest)
436 {
437 DBLOCK(1, printf("got a redirect for ");
438 writeIpAddr(dest);
439 printf("but route is fixed\n"));
440 return;
441 }
442 }
443 else
444 {
445 result= ipr_add_oroute(port_nr, dest, netmask,
446 oroute->ort_gateway, HZ, ORTD_UNREACHABLE,
447 FALSE, 0, NULL);
448 assert(result == NW_OK);
449 }
450 result= ipr_add_oroute(port_nr, dest, netmask, new_gateway,
451 timeout, 1, FALSE, 0, NULL);
452 assert(result == NW_OK);
453 }
ipr_ttl_exc():ipr_ttl_exc is called to notify the routing table that a destination has received a ttl exceeded.
454 PUBLIC void ipr_ttl_exc(port_nr, dest, netmask, timeout)
455 int port_nr;
456 ipaddr_t dest;
457 ipaddr_t netmask;
458 time_t timeout;
459 {
460 oroute_t *oroute;
461 int new_dist;
462 int result;
463 oroute= oroute_find_ent(port_nr, dest);
464 if (!oroute)
465 {
466 DBLOCK(1, printf("got a ttl exceeded for ");
467 writeIpAddr(dest); printf("but no route present\n"));
468 return;
469 }
470 new_dist= oroute->ort_dist * 2;
471 if (new_dist>IP_MAX_TTL)
472 {
473 new_dist= oroute->ort_dist+1;
474 if (new_dist>IP_MAX_TTL)
475 {
476 DBLOCK(1, printf("got a ttl exceeded for ");
477 writeIpAddr(dest);
478 printf(" but dist is %d\n",
479 oroute->ort_dist));
480 return;
481 }
482 }
483 result= ipr_add_oroute(port_nr, dest, netmask, oroute->ort_gateway,
484 timeout, new_dist, FALSE, 0, NULL);
485 assert(result == NW_OK);
486 }
ipr_get_oroute(): ipr_get_oroute gets the route table entry from the oroute_table array
with index ent_no. Route entry is copied back to user in route_ent.
ipr_get_oroute implements the ioctl system call on request NWIOGIPOROUTE.
487 PUBLIC int ipr_get_oroute(ent_no, route_ent)
488 int ent_no;
489 nwio_route_t *route_ent;
490 {
491 oroute_t *oroute;
492 if (ent_no<0 || ent_no>= OROUTE_NR)
493 return ENOENT;
494 oroute= &oroute_table[ent_no];
495 if ((oroute->ort_flags & ORTF_INUSE) && oroute->ort_exp_tim &&
496 oroute->ort_exp_tim < get_time())
497 {
498 oroute_del(oroute);
499 oroute->ort_flags &= ~ORTF_INUSE;
500 }
501 route_ent->nwr_ent_no= ent_no;
502 route_ent->nwr_ent_count= OROUTE_NR;
503 route_ent->nwr_dest= oroute->ort_dest;
504 route_ent->nwr_netmask= oroute->ort_subnetmask;
505 route_ent->nwr_gateway= oroute->ort_gateway;
506 route_ent->nwr_dist= oroute->ort_dist;
507 route_ent->nwr_flags= NWRF_EMPTY;
508 if (oroute->ort_flags & ORTF_INUSE)
509 {
510 route_ent->nwr_flags |= NWRF_INUSE;
511 if (oroute->ort_flags & ORTF_STATIC)
512 route_ent->nwr_flags |= NWRF_STATIC;
513 }
514 route_ent->nwr_pref= oroute->ort_pref;
515 route_ent->nwr_ifaddr= ip_get_ifaddr(oroute->ort_port);
516 return NW_OK;
517 }
oroute_find_ent(): returns a pointer to the route table entry (oroute_t) given the ip
port and the destination of the packet for an outgoing packet. oroute_find_ent() is
called in ip_write.c to see to where we should route a packet.
518 PRIVATE oroute_t *oroute_find_ent(port_nr, dest)
519 int port_nr;
520 ipaddr_t dest;
521 {
522 int hash, i, r_hash_ind;
523 oroute_hash_t *oroute_hash;
524 oroute_hash_t tmp_hash;
525 oroute_t *oroute, *bestroute;
526 time_t currtim;
527 unsigned long hash_tmp;
528 currtim= get_time();
hash = hash value for oroute_hash_table. oroute_find_ent checks if the address was stored
in oroute_hash_table which stores recently used routes. oroute_hash_table is used to speed
up looking up the route table.
529 hash= hash_oroute(port_nr, dest, hash_tmp);
530 oroute_hash= &oroute_hash_table[hash][0];
Hash table oroute_hash_table resolves collisions by chaining but there are only 4 elements
in the chain ie oroute_hash_table[hash][0], oroute_hash_table[hash][1], oroute_hash_table[hash][2]
oroute_hash_table[hash][3]. If the address was stored in oroute_hash_table it returns the corresponding
route table entry and the destination is placed at the head of the chain ie iooute_hash_table[hash][0].
Otherwise, ipr_get_oroute checks the array oroute_table for a route which can used for the destination ip
address.
531 if (oroute_hash[0].orh_addr == dest)
532 oroute= oroute_hash[0].orh_route;
533 else if (oroute_hash[1].orh_addr == dest)
534 {
535 tmp_hash= oroute_hash[1];
536 oroute_hash[1]= oroute_hash[0];
537 oroute_hash[0]= tmp_hash;
538 oroute= tmp_hash.orh_route;
539 }
540 else if (oroute_hash[2].orh_addr == dest)
541 {
542 tmp_hash= oroute_hash[2];
543 oroute_hash[2]= oroute_hash[1];
544 oroute_hash[1]= oroute_hash[0];
545 oroute_hash[0]= tmp_hash;
546 oroute= tmp_hash.orh_route;
547 }
548 else if (oroute_hash[3].orh_addr == dest)
549 {
550 tmp_hash= oroute_hash[3];
551 oroute_hash[3]= oroute_hash[2];
552 oroute_hash[2]= oroute_hash[1];
553 oroute_hash[1]= oroute_hash[0];
554 oroute_hash[0]= tmp_hash;
555 oroute= tmp_hash.orh_route;
556 }
557 else
558 oroute= NULL;
559 if (oroute)
560 {
561 assert(oroute->ort_port == port_nr);
562 if (oroute->ort_exp_tim && oroute->ort_exp_tim<currtim)
563 {
564 oroute_del(oroute);
565 oroute->ort_flags &= ~ORTF_INUSE;
566 }
567 else
568 return oroute;
569 }
570 bestroute= NULL;
oroute_find_ent checks the array oroute_table for a route which can used for the destination
ip address.
571 for (oroute= oroute_head; oroute; oroute= oroute->ort_nextnw)
572 {
((dest ^ oroute->ort_dest) & oroute->ort_subnetmask) != 0 means
route belongs on the same subnet as the destination ip address.
573 if (((dest ^ oroute->ort_dest) & oroute->ort_subnetmask) != 0)
574 continue;
575 if (oroute->ort_port != port_nr)
576 continue;
577 if (!bestroute)
578 {
579 bestroute= oroute;
580 continue;
581 }
582 assert(oroute->ort_dest != bestroute->ort_dest);
583 if (ntohl(oroute->ort_subnetmask) >
584 ntohl(bestroute->ort_subnetmask))
585 {
586 bestroute= oroute;
587 continue;
588 }
589 }
590 if (bestroute == NULL)
591 return NULL;
The destination is placed at the head of the chain ie oroute_hash_table[hash][0].
Last member of chain is removed.
592 oroute_hash[3]= oroute_hash[2];
593 oroute_hash[2]= oroute_hash[1];
594 oroute_hash[1]= oroute_hash[0];
595 oroute_hash[0].orh_addr= dest;
596 oroute_hash[0].orh_route= bestroute;
597 return bestroute;
598 }
oroute_del(): oroute_del deletes a route for outgoing packets.
599 PRIVATE void oroute_del(oroute)
600 oroute_t *oroute;
601 {
602 oroute_t *prev, *nw_route, *gw_route, *dist_route, *prev_route;
First it finds the route in the linked lists of routes.
603 for (prev= NULL, nw_route= oroute_head; nw_route;
604 prev= nw_route, nw_route= nw_route->ort_nextnw)
605 {
606 if (oroute->ort_port == nw_route->ort_port &&
607 oroute->ort_dest == nw_route->ort_dest &&
608 oroute->ort_subnetmask == nw_route->ort_subnetmask)
609 {
610 break;
611 }
612 }
613 assert(nw_route);
614 if (prev)
615 prev->ort_nextnw= nw_route->ort_nextnw;
616 else
617 oroute_head= nw_route->ort_nextnw;
618 prev_route= nw_route;
619 for (prev= NULL, gw_route= nw_route; gw_route;
620 prev= gw_route, gw_route= gw_route->ort_nextgw)
621 {
622 if (oroute->ort_gateway == gw_route->ort_gateway)
623 break;
624 }
625 assert(gw_route);
626 if (prev)
627 prev->ort_nextgw= gw_route->ort_nextgw;
628 else
629 nw_route= gw_route->ort_nextgw;
630 for (prev= NULL, dist_route= gw_route; dist_route;
631 prev= dist_route, dist_route= dist_route->ort_nextdist)
632 {
633 if (oroute == dist_route)
634 break;
635 }
Next it deletes it.
636 assert(dist_route);
637 if (prev)
638 prev->ort_nextdist= dist_route->ort_nextdist;
639 else
640 gw_route= dist_route->ort_nextdist;
Finally it sorts the remaining routes in the linked list.
641 gw_route= sort_dists(gw_route);
642 if (gw_route != NULL)
643 {
644 gw_route->ort_nextgw= nw_route;
645 nw_route= gw_route;
646 }
647 nw_route= sort_gws(nw_route);
648 if (nw_route != NULL)
649 {
650 nw_route->ort_nextnw= oroute_head;
651 oroute_head= nw_route;
652 }
653 if (nw_route != prev_route)
654 {
655 oroute_uncache_nw(prev_route->ort_dest,
656 prev_route->ort_subnetmask);
657 }
658 }
sort_dists(): sort_dists sorts a linked list on the ort_dist and ort_pref field where
ort_nextdist points to the next member of the list. The sort simply places the best
element at the head of the list and returns it as the return value.
659 PRIVATE oroute_t *sort_dists(oroute)
660 oroute_t *oroute;
661 {
662 oroute_t *r, *prev, *best, *best_prev;
663 int best_dist, best_pref;
664 best= NULL;
665 for (prev= NULL, r= oroute; r; prev= r, r= r->ort_nextdist)
666 {
667 if (best == NULL)
668 ; /* Force assignment to best */
669 else if (r->ort_dist != best_dist)
670 {
671 if (r->ort_dist > best_dist)
672 continue;
673 }
674 else
675 {
676 if (r->ort_pref <= best_pref)
677 continue;
678 }
679 best= r;
680 best_prev= prev;
681 best_dist= r->ort_dist;
682 best_pref= r->ort_pref;
683 }
684 if (!best)
685 {
686 assert(oroute == NULL);
687 return oroute;
688 }
689 if (!best_prev)
690 {
691 assert(best == oroute);
692 return oroute;
693 }
694 best_prev->ort_nextdist= best->ort_nextdist;
695 best->ort_nextdist= oroute;
696 return best;
697 }
sort_gws(): sort_gws sorts a linked list on the ort_dist and ort_dest field where
ort_nextdist points to the next member of the list. The sort simply places the best
element at the head of the list and returns it as the return value.
698 PRIVATE oroute_t *sort_gws(oroute)
699 oroute_t *oroute;
700 {
701 oroute_t *r, *prev, *best, *best_prev;
702 int best_dist, best_pref;
703 best= NULL;
704 for (prev= NULL, r= oroute; r; prev= r, r= r->ort_nextgw)
705 {
706 if (best == NULL)
707 ; /* Force assignment to best */
708 else if (r->ort_dist != best_dist)
709 {
710 if (r->ort_dist > best_dist)
711 continue;
712 }
713 else
714 {
715 if (r->ort_pref <= best_pref)
716 continue;
717 }
718 best= r;
719 best_prev= prev;
720 best_dist= r->ort_dist;
721 best_pref= r->ort_pref;
722 }
723 if (!best)
724 {
725 assert(oroute == NULL);
726 return oroute;
727 }
728 if (!best_prev)
729 {
730 assert(best == oroute);
731 return oroute;
732 }
733 best_prev->ort_nextgw= best->ort_nextgw;
734 best->ort_nextgw= oroute;
735 return best;
736 }
oroute_uncache_nw zeros all of the entries in the oroute_hash table for the subnet
represented by the dest ip address and the subnetmask netmask. oroute_uncache_nw
is called to remove a route from the hash table oroute_hash table.
737 PRIVATE oroute_uncache_nw(dest, netmask)
738 ipaddr_t dest;
739 ipaddr_t netmask;
740 {
741 int i, j;
742 oroute_hash_t *oroute_hash;
743 for (i= 0, oroute_hash= &oroute_hash_table[0][0];
744 i<OROUTE_HASH_NR; i++, oroute_hash += OROUTE_HASH_ASS_NR)
745 {
746 for (j= 0; j<OROUTE_HASH_ASS_NR; j++)
747 {
748 if (((oroute_hash[j].orh_addr ^ dest) & netmask) == 0)
749 {
750 oroute_hash[j].orh_addr= 0;
751 oroute_hash[j].orh_route= NULL;
752 }
753 }
754 }
755 }
756 /*
757 * Input routing
758 */
ipr_get_iroute(): ipr_get_iroute gets the route table entry from the iroute_table array
with index ent_no. Route entry is copied back to user in route_ent.
ipr_get_iroute implements the ioctl system call on request NWIOGIPIROUTE.
759 PUBLIC int ipr_get_iroute(ent_no, route_ent)
760 int ent_no;
761 nwio_route_t *route_ent;
762 {
763 iroute_t *iroute;
764 if (ent_no<0 || ent_no>= IROUTE_NR)
765 return ENOENT;
766 iroute= &iroute_table[ent_no];
767 route_ent->nwr_ent_count= IROUTE_NR;
768 route_ent->nwr_dest= iroute->irt_dest;
769 route_ent->nwr_netmask= iroute->irt_subnetmask;
770 route_ent->nwr_gateway= iroute->irt_gateway;
771 route_ent->nwr_dist= iroute->irt_dist;
772 route_ent->nwr_flags= NWRF_EMPTY;
773 if (iroute->irt_flags & IRTF_INUSE)
774 {
775 route_ent->nwr_flags |= NWRF_INUSE;
776 if (iroute->irt_flags & IRTF_STATIC)
777 route_ent->nwr_flags |= NWRF_STATIC;
778 if (iroute->irt_dist == IRTD_UNREACHABLE)
779 route_ent->nwr_flags |= NWRF_UNREACHABLE;
780 }
781 route_ent->nwr_pref= 0;
782 route_ent->nwr_ifaddr= ip_get_ifaddr(iroute->irt_port);
783 return NW_OK;
784 }
ipr_add_iroute(): ipr_add_iroute adds a route to the iroute_table which handles
incoming packets. It implements the ioctl system call on an IP device with request
NWIOSIPIROUTE.
785 PUBLIC int ipr_add_iroute(port_nr, dest, subnetmask, gateway,
786 dist, static_route, iroute_p)
787 int port_nr;
788 ipaddr_t dest;
789 ipaddr_t subnetmask;
790 ipaddr_t gateway;
791 int dist;
792 int static_route;
793 iroute_t **iroute_p;
794 {
795 int i;
796 iroute_t *iroute, *unused_route;
797 unused_route= NULL;
798 if (static_route)
799 {
800 /* Static routes are not reused automatically, so we look
801 * for an unused entry.
802 */
803 for(i= 0, iroute= iroute_table; i<IROUTE_NR; i++, iroute++)
804 {
805 if ((iroute->irt_flags & IRTF_INUSE) == 0)
806 break;
807 }
808 if (i != IROUTE_NR)
809 unused_route= iroute;
810 }
811 else
812 {
813 /* Try to track down any old routes, and look for an
814 * unused one.
815 */
816 for(i= 0, iroute= iroute_table; i<IROUTE_NR; i++, iroute++)
817 {
818 if ((iroute->irt_flags & IRTF_INUSE) == 0)
819 {
820 unused_route= iroute;
821 continue;
822 }
823 if ((iroute->irt_flags & IRTF_STATIC) != 0)
824 continue;
825 if (iroute->irt_port != port_nr ||
826 iroute->irt_dest != dest ||
827 iroute->irt_subnetmask != subnetmask ||
828 iroute->irt_gateway != gateway)
829 {
830 continue;
831 }
832 break;
833 }
834 if (i != IROUTE_NR)
835 unused_route= iroute;
836 }
837 if (unused_route == NULL)
838 return ENOMEM;
839 iroute= unused_route;
Set new route to appropriate values.
840 iroute->irt_port= port_nr;
841 iroute->irt_dest= dest;
842 iroute->irt_subnetmask= subnetmask;
843 iroute->irt_gateway= gateway;
844 iroute->irt_dist= dist;
845 iroute->irt_flags= IRTF_INUSE;
846 if (static_route)
847 iroute->irt_flags |= IRTF_STATIC;
848
Remove route from cache ie hash table iroute_hash_table.
849 iroute_uncache_nw(iroute->irt_dest, iroute->irt_subnetmask);
850 if (iroute_p != NULL)
851 *iroute_p= iroute;
852 return NW_OK;
853 }
ipr_del_iroute deletes a route from the iroute_table which handles incoming packets by unsetting
the flag IRTF_INUSE. It implements the ioctl system call on an IP device with request NWIODIPIROUTE.
854 PUBLIC int ipr_del_iroute(port_nr, dest, subnetmask, gateway,
855 dist, static_route)
856 int port_nr;
857 ipaddr_t dest;
858 ipaddr_t subnetmask;
859 ipaddr_t gateway;
860 int dist;
861 int static_route;
862 {
863 int i;
864 iroute_t *iroute;
865 /* Try to track down any old routes, and look for an
866 * unused one.
867 */
868 for(i= 0, iroute= iroute_table; i<IROUTE_NR; i++, iroute++)
869 {
870 if ((iroute->irt_flags & IRTF_INUSE) == 0)
871 continue;
872 if (iroute->irt_port != port_nr ||
873 iroute->irt_dest != dest ||
874 iroute->irt_subnetmask != subnetmask ||
875 iroute->irt_gateway != gateway)
876 {
877 continue;
878 }
879 if (!!(iroute->irt_flags & IRTF_STATIC) != static_route)
880 continue;
881 break;
882 }
883 if (i == IROUTE_NR)
884 return ESRCH;
Remove route from cache ie hash table iroute_hash_table.
885 iroute_uncache_nw(iroute->irt_dest, iroute->irt_subnetmask);
Unset the flag IRTF_INUSE.
886 iroute->irt_flags= IRTF_EMPTY;
887 return NW_OK;
888 }
iroute_uncache_nw zeros all of the entries in the iroute_hash table for the subnet
represented by the dest ip address and the subnetmask netmask. iroute_uncache_nw
is called to remove a route from the hash table iroute_hash table.
889 PRIVATE iroute_uncache_nw(dest, netmask)
890 ipaddr_t dest;
891 ipaddr_t netmask;
892 {
893 int i, j;
894 iroute_hash_t *iroute_hash;
895 for (i= 0, iroute_hash= &iroute_hash_table[0][0];
896 i<IROUTE_HASH_NR; i++, iroute_hash += IROUTE_HASH_ASS_NR)
897 {
898 for (j= 0; j<IROUTE_HASH_ASS_NR; j++)
899 {
900 if (((iroute_hash[j].irh_addr ^ dest) &
901 netmask) == 0)
902 {
903 iroute_hash[j].irh_addr= 0;
904 iroute_hash[j].irh_route= NULL;
905 }
906 }
907 }
908 }
909 /*
910 * Debugging, management
911 */
912 /*
913 * $PchId: ipr.c,v 1.9 1996/07/31 17:26:33 philip Exp $
914 */
ipr.c is the code for routing of packets. The packets which are to be routed are in
ip_read.c and ip_write.c. ipr.c returns the next ip address it should route the packets
to. There are 2 route tables used in inet: 1) oroute_table and 2) iroute_table. oroute_table
handles the routing for outgoing packets. iroute_table handles the routing for incoming packets.
ach element in the arrays whether it is a iroute_t or oroute_t structure represents a route in
the route table.