0044001 /*
0044002 ipr.c
0044003
0044004 Copyright 1995 Philip Homburg
0044005 */
0044006
0044007 #include "inet.h"
0044008 #include "clock.h"
0044009
0044010 #include "type.h"
0044011 #include "assert.h"
0044012 #include "buf.h"
0044013 #include "event.h"
0044014 #include "io.h"
0044015 #include "ip_int.h"
0044016 #include "ipr.h"
0044017
0044018 THIS_FILE
0044019
0044020 #define OROUTE_NR 32
0044021 #define OROUTE_STATIC_NR 16
0044022 #define OROUTE_HASH_ASS_NR 4
0044023 #define OROUTE_HASH_NR 32
0044024 #define OROUTE_HASH_MASK (OROUTE_HASH_NR-1)
0044025
0044026 #define hash_oroute(port_nr, ipaddr, hash_tmp) (hash_tmp= (ipaddr), \
0044027 hash_tmp= (hash_tmp >> 20) ^ hash_tmp, \
0044028 hash_tmp= (hash_tmp >> 10) ^ hash_tmp, \
0044029 hash_tmp= (hash_tmp >> 5) ^ hash_tmp, \
0044030 (hash_tmp + (port_nr)) & OROUTE_HASH_MASK)hash_oroute() / hash_iroute()
hash_oroute() and hash_oroute() are identical.
hash_oroute()is #define'd in ipr.c:
#define hash_oroute(port_nr, ipaddr, hash_tmp) (hash_tmp= (ipaddr), \
hash_tmp= (hash_tmp >> 20) ^ hash_tmp, \
hash_tmp= (hash_tmp >> 10) ^ hash_tmp, \
hash_tmp= (hash_tmp >> 5) ^ hash_tmp, \
(hash_tmp + (port_nr)) & OROUTE_HASH_MASK)
where OROUTE_HASH_MASK is #define'd as the following:
#define OROUTE_HASH_NR 32
#define OROUTE_HASH_MASK (OROUTE_HASH_NR-1)
For an address of 192.160.1.1 on ip port 0:
hash_tmp = 192.160.1.1 = 11000000 10100000 00000001 00000001 (binary)
hash_tmp = (192.160.1.1 >> 20) ^ 192.170.1.1
= 00000000 00000000 00001100 00001010 ^ 11000000 10100000 00000001 00000001
= 11000000 10100000 00001101 00001011 = 192.168.13.11
hash_tmp = (192.168.13.11 >> 10) ^ 192.168.13.11
= 00000000 00110000 00101000 00000011 ^ 11000000 10100000 00001101 00001011
= 11000000 10010000 00100101 00001000 = 192.144.37.8
hash_tmp = (192.144.37.8 >> 5) ^ 192.144.37.8
= 00000110 00000100 10000001 00101000 ^ 11000000 10010000 00100101 00001000
= 11000110 10010100 10100100 00100000 = 198.148.164.32
return value: hash_tmp + port_nr & OROUTE_HASH_MASK
= hash_tmp + port_nr & (OROUTE_HASH_NR - 1)
= 198.148.164.32 + 0 & (32-1)
= 11000110 10010100 10100100 00100000 + 0 & 00011111
= 0
Therefore, hash_iroute(0, 192.160.1.1, 0) equals 0.
As mentioned earlier, hash_oroute() and hash_iroute() are identical. Furthermore, OROUTE_HASH_NR and IROUTE_HASH_NR are both 32 and OROUTE_HASH_MASK and IROUTE_HASH_MASK are both 31 (0001 1111 binary).
Note that the initial value of hash_tmp is meaningless.
0044031
0044032 typedef struct oroute_hash
0044033 {
0044034 ipaddr_t orh_addr;
0044035 oroute_t *orh_route;
0044036 } oroute_hash_t;oroute_table[] / oroute_hash_table[]
"Ouput routing" is routing that is done for outgoing packets. As an example, suppose that there are two ethernet ports with corresponding ip devices of "/dev/ip0" (192.30.1.1/255.255.255.0) and "/dev/ip1" (192.30.2.1/255.255.255.0). If the following add_route command is issued:
add_route -g 192.30.2.254 -d 192.50.1.0 -m 2 -n 255.255.255.0 -I /dev/ip0
then outgoing ip packets (that did not, however, arrive on another interface) are sent out the ethernet port that corresponds to /dev/ip0 to the gateway with ip address of 192.30.2.254.
Output routes are stored in two different arrays, oroute_table[] and oroute_hash_table[][]. oroute_table[] is the main table and oroute_hash_table[][] is the cache, where routes can be quickly looked up. oroute_table[] has 32 elements and each element is of type oroute_t:
typedef struct oroute
{
int ort_port;
ipaddr_t ort_dest;
ipaddr_t ort_subnetmask;
int ort_dist;
i32_t ort_pref;
ipaddr_t ort_gateway;
time_t ort_exp_tim;
time_t ort_timestamp;
int ort_flags;
struct oroute *ort_nextnw;
struct oroute *ort_nextgw;
struct oroute *ort_nextdist;
} oroute_t;
int ort_port: The port number (e.g., ip0 is 0).
ipaddr_t ort_dest: The network address of the routing entry (e.g., 192.50.1.0).
ipaddr_t ort_subnetmask: The subnet mask of the routing entry (e.g., 255.255.255.0).
int ort_dist: The distance to the route. Routes with low distances are chosen over routes with high distances.
i32_t ort_pref: The preference of the route. Routes with high preferences are chosen over routes with low preferences. The distance of a route is of higher importance. In other words, the relative preference of two routes is only significant if and only if these two routes are tied for the lowest distance.
ipaddr_t ort_gateway: The ip address of the gateway. Packets that are not destined to systems on the local network are sent to the gateway.
time_t ort_exp_tim: The expiration time for the entry. Note that when using add_route, this value will always 0. The entries, therefore, do not expire.
time_t ort_timestamp: The time at which the entry is added to oroute_table[].
int ort_flags:
#define ORTF_EMPTY 0
#define ORTF_INUSE 1
#define ORTF_STATIC 2
Only OROUTE_STATIC_NR (#define'd as 16) static routes are allowed in the output routing table. Static and dynamic routes cannot replace static routes, even if 2 routes are to the same network.
struct oroute *ort_nextnw:
struct oroute *ort_nextgw:
struct oroute *ort_nextdist:
ort_nextnw, ort_nextgw, and ort_nextdist can best be described using a figure. The figure below represents the main output routing table, oroute_table[]:
The ort_nextnw field (red) is the linked list of routes to specific networks/subnet mask pairs. A, B, C, D, and E all are routes to different network/subnet mask pairs. For example, A could be the route to 192.30.1.0/255.255.255.0 and B could be the route to 192.30.2.0/255.255.255.0.
The ort_nextgw field (blue) links the linked lists of routes with the same network/subnet mask pairs but different gateways. D, F, and G are all routes to the same network/subnet mask pairs but all have different gateways. ort_nextdist connec
The ort_nextdist field (green) links the linked lists of routes with the same network/subnet mask pairs and the same gateway but with possibly different distances/preferences. F, H, I, and J are all routes to the same network/subnet mask pairs and the same gateway but have possibly different distances/preferences.
The oroute_hash_table[][] is a 2-dimensional array of dimensions 32x4 whose entries are of type oroute_hash_t:
typedef struct oroute_hash
{
ipaddr_t irh_addr;
iroute_t *irh_route;
} oroute_hash_t;
ipaddr_t irh_addr: The ip address (not the network address) of a system.
iroute_t *irh_route: The best route for the ip address above.
If an entry for a system does not exist in oroute_hash_table[][], the best route for the system is determined from the entries in oroute_table[]. The ip address of this system and the best route to the system (which together form an oroute_hash_t struct) is then placed in oroute_hash_table[][]. The first dimension corresponds to the hash of the ip address, as determined by the #define hash_iroute. The second dimension will be 0. The entry with the same hash that was formerly in the 0th slot will be pushed to the 1st slot, the entry that was formerly in the 1st slot will be pushed to the 2nd slot, and then entry that was formerly in the 2nd slot will be pushed to the 3rd slot. The entry that was formerly in the 3rd slot will be pushed out of oroute_hash_table[][].
The best route for the ip address can later be quickly retrieved from oroute_hash_table[][] (if it hasn't since been pushed out).
0044037
0044038 PRIVATE oroute_t oroute_table[OROUTE_NR];
0044039 PRIVATE oroute_t *oroute_head;If the main output routing table is searched for a route, oroute_head is the first route to be analyzed. See the figure in the comment for 44036 for more information.
0044040 PRIVATE int static_oroute_nr;
0044041 PRIVATE oroute_hash_t oroute_hash_table[OROUTE_HASH_NR][OROUTE_HASH_ASS_NR];oroute_table[] / oroute_hash_table[]
"Ouput routing" is routing that is done for outgoing packets. As an example, suppose that there are two ethernet ports with corresponding ip devices of "/dev/ip0" (192.30.1.1/255.255.255.0) and "/dev/ip1" (192.30.2.1/255.255.255.0). If the following add_route command is issued:
add_route -g 192.30.2.254 -d 192.50.1.0 -m 2 -n 255.255.255.0 -I /dev/ip0
then outgoing ip packets (that did not, however, arrive on another interface) are sent out the ethernet port that corresponds to /dev/ip0 to the gateway with ip address of 192.30.2.254.
Output routes are stored in two different arrays, oroute_table[] and oroute_hash_table[][]. oroute_table[] is the main table and oroute_hash_table[][] is the cache, where routes can be quickly looked up. oroute_table[] has 32 elements and each element is of type oroute_t:
typedef struct oroute
{
int ort_port;
ipaddr_t ort_dest;
ipaddr_t ort_subnetmask;
int ort_dist;
i32_t ort_pref;
ipaddr_t ort_gateway;
time_t ort_exp_tim;
time_t ort_timestamp;
int ort_flags;
struct oroute *ort_nextnw;
struct oroute *ort_nextgw;
struct oroute *ort_nextdist;
} oroute_t;
int ort_port: The port number (e.g., ip0 is 0).
ipaddr_t ort_dest: The network address of the routing entry (e.g., 192.50.1.0).
ipaddr_t ort_subnetmask: The subnet mask of the routing entry (e.g., 255.255.255.0).
int ort_dist: The distance to the route. Routes with low distances are chosen over routes with high distances.
i32_t ort_pref: The preference of the route. Routes with high preferences are chosen over routes with low preferences. The distance of a route is of higher importance. In other words, the relative preference of two routes is only significant if and only if these two routes are tied for the lowest distance.
ipaddr_t ort_gateway: The ip address of the gateway. Packets that are not destined to systems on the local network are sent to the gateway.
time_t ort_exp_tim: The expiration time for the entry. Note that when using add_route, this value will always 0. The entries, therefore, do not expire.
time_t ort_timestamp: The time at which the entry is added to oroute_table[].
int ort_flags:
#define ORTF_EMPTY 0
#define ORTF_INUSE 1
#define ORTF_STATIC 2
Only OROUTE_STATIC_NR (#define'd as 16) static routes are allowed in the output routing table. Static and dynamic routes cannot replace static routes, even if 2 routes are to the same network.
struct oroute *ort_nextnw:
struct oroute *ort_nextgw:
struct oroute *ort_nextdist:
ort_nextnw, ort_nextgw, and ort_nextdist can best be described using a figure. The figure below represents the main output routing table, oroute_table[]:
The ort_nextnw field (red) is the linked list of routes to specific networks/subnet mask pairs. A, B, C, D, and E all are routes to different network/subnet mask pairs. For example, A could be the route to 192.30.1.0/255.255.255.0 and B could be the route to 192.30.2.0/255.255.255.0.
The ort_nextgw field (blue) links the linked lists of routes with the same network/subnet mask pairs but different gateways. D, F, and G are all routes to the same network/subnet mask pairs but all have different gateways. ort_nextdist connec
The ort_nextdist field (green) links the linked lists of routes with the same network/subnet mask pairs and the same gateway but with possibly different distances/preferences. F, H, I, and J are all routes to the same network/subnet mask pairs and the same gateway but have possibly different distances/preferences.
The oroute_hash_table[][] is a 2-dimensional array of dimensions 32x4 whose entries are of type oroute_hash_t:
typedef struct oroute_hash
{
ipaddr_t irh_addr;
iroute_t *irh_route;
} oroute_hash_t;
ipaddr_t irh_addr: The ip address (not the network address) of a system.
iroute_t *irh_route: The best route for the ip address above.
If an entry for a system does not exist in oroute_hash_table[][], the best route for the system is determined from the entries in oroute_table[]. The ip address of this system and the best route to the system (which together form an oroute_hash_t struct) is then placed in oroute_hash_table[][]. The first dimension corresponds to the hash of the ip address, as determined by the #define hash_iroute. The second dimension will be 0. The entry with the same hash that was formerly in the 0th slot will be pushed to the 1st slot, the entry that was formerly in the 1st slot will be pushed to the 2nd slot, and then entry that was formerly in the 2nd slot will be pushed to the 3rd slot. The entry that was formerly in the 3rd slot will be pushed out of oroute_hash_table[][].
The best route for the ip address can later be quickly retrieved from oroute_hash_table[][] (if it hasn't since been pushed out).
0044042
0044043 #define IROUTE_NR (sizeof(int) == 2 ? 64 : 512)
0044044 #define IROUTE_HASH_ASS_NR 4
0044045 #define IROUTE_HASH_NR 32
0044046 #define IROUTE_HASH_MASK (IROUTE_HASH_NR-1)
0044047
0044048 #define hash_iroute(port_nr, ipaddr, hash_tmp) (hash_tmp= (ipaddr), \
0044049 hash_tmp= (hash_tmp >> 20) ^ hash_tmp, \
0044050 hash_tmp= (hash_tmp >> 10) ^ hash_tmp, \
0044051 hash_tmp= (hash_tmp >> 5) ^ hash_tmp, \
0044052 (hash_tmp + (port_nr)) & IROUTE_HASH_MASK)hash_oroute() / hash_iroute()
hash_oroute() and hash_oroute() are identical.
hash_oroute()is #define'd in ipr.c:
#define hash_oroute(port_nr, ipaddr, hash_tmp) (hash_tmp= (ipaddr), \
hash_tmp= (hash_tmp >> 20) ^ hash_tmp, \
hash_tmp= (hash_tmp >> 10) ^ hash_tmp, \
hash_tmp= (hash_tmp >> 5) ^ hash_tmp, \
(hash_tmp + (port_nr)) & OROUTE_HASH_MASK)
where OROUTE_HASH_MASK is #define'd as the following:
#define OROUTE_HASH_NR 32
#define OROUTE_HASH_MASK (OROUTE_HASH_NR-1)
For an address of 192.160.1.1 on ip port 0:
hash_tmp = 192.160.1.1 = 11000000 10100000 00000001 00000001 (binary)
hash_tmp = (192.160.1.1 >> 20) ^ 192.170.1.1
= 00000000 00000000 00001100 00001010 ^ 11000000 10100000 00000001 00000001
= 11000000 10100000 00001101 00001011 = 192.168.13.11
hash_tmp = (192.168.13.11 >> 10) ^ 192.168.13.11
= 00000000 00110000 00101000 00000011 ^ 11000000 10100000 00001101 00001011
= 11000000 10010000 00100101 00001000 = 192.144.37.8
hash_tmp = (192.144.37.8 >> 5) ^ 192.144.37.8
= 00000110 00000100 10000001 00101000 ^ 11000000 10010000 00100101 00001000
= 11000110 10010100 10100100 00100000 = 198.148.164.32
return value: hash_tmp + port_nr & OROUTE_HASH_MASK
= hash_tmp + port_nr & (OROUTE_HASH_NR - 1)
= 198.148.164.32 + 0 & (32-1)
= 11000110 10010100 10100100 00100000 + 0 & 00011111
= 0
Therefore, hash_iroute(0, 192.160.1.1, 0) equals 0.
As mentioned earlier, hash_oroute() and hash_iroute() are identical. Furthermore, OROUTE_HASH_NR and IROUTE_HASH_NR are both 32 and OROUTE_HASH_MASK and IROUTE_HASH_MASK are both 31 (0001 1111 binary).
Note that the initial value of hash_tmp is meaningless.
0044053
0044054 typedef struct iroute_hash
0044055 {
0044056 ipaddr_t irh_addr;
0044057 iroute_t *irh_route;
0044058 } iroute_hash_t;iroute_table[] / iroute_hash_table[]
"Input routing" is routing that is done between interfaces. As an example, suppose that there are two ethernet ports and the corresponding ip port of the first ethernet (which corresponds to the device "/dev/ip0") has an ip address/subnet mask of 192.30.1.1/255.255.255.0 and the ip port of the second ethernet (which corresponds to the device "/dev/ip1") has an ip address/subnet mask of 192.30.2.1/255.255.255.0. If the following add_route command is issued:
add_route -i -g 0.0.0.0 -d 192.30.1.0 -m 1 -n 255.255.255.0 -I /dev/ip0
then ip packets arriving on the second ethernet destined for the 192.30.1.0/255.255.255.0 network will be routed to the first ethernet port.
Input routes are stored in two different arrays, iroute_table[] and iroute_hash_table[][]. iroute_table[] is the main table and iroute_hash_table[][] is the cache, where routes can be quickly looked up. iroute_table[] has 512 elements and each element is of type iroute_t:
typedef struct iroute
{
ipaddr_t irt_dest;
ipaddr_t irt_gateway;
ipaddr_t irt_subnetmask;
int irt_dist;
int irt_port;
int irt_flags;
} iroute_t;
ipaddr_t irt_dest: The network address of the routing entry (e.g., 192.30.1.0).
ipaddr_t irt_gateway: The gateway to which packets that are not destined to machines on the local network are sent.
ipaddr_t irt_subnetmask: The subnet mask of the routing entry (e.g., 255.255.255.0).
int irt_dist: The distance. Routes with low distances are chosen over routes with high distances.
int irt_port: The port number (e.g., ip0 is 0).
int irt_flags: irt_flags can be one of the following:
#define IRTF_EMPTY 0
#define IRTF_INUSE 1
#define IRTF_STATIC 2
Static input routes behave differently than dynamic input routes. If a static route is added to the input routing table, the route will not not replace any pre-existing route (static or dynamic) even if the values of the route (e.g., destination network) are the same. A dynamic input route, on the other hand, will replace another dynamic input route.
The iroute_hash_table[][] is a 2-dimensional array of dimensions 32x4 whose entries are of type iroute_hash_t:
typedef struct iroute_hash
{
ipaddr_t irh_addr;
iroute_t *irh_route;
} iroute_hash_t;
ipaddr_t irh_addr: The ip address (not the network address) of a system.
iroute_t *irh_route: The best route for the ip address above.
If an entry for a system does not exist in iroute_hash_table[][], the best route for the system is determined from the entries in iroute_table[]. The ip address of this system and the best route to the system (which together form an iroute_hash_t struct) is then placed in iroute_hash_table[][]. The first dimension corresponds to the hash of the ip address, as determined by the #define hash_iroute. The second dimension will be 0. The entry with the same hash that was formerly in the 0th slot will be pushed to the 1st slot, the entry that was formerly in the 1st slot will be pushed to the 2nd slot, and then entry that was formerly in the 2nd slot will be pushed to the 3rd slot. The entry that was formerly in the 3rd slot will be pushed out of iroute_hash_table[][].
The best route for the ip address can then later be quickly retrieved from iroute_hash_table[][] (if it hasn't since been pushed out).
0044059
0044060 PRIVATE iroute_t iroute_table[IROUTE_NR];IROUTE_NR is #define'd as 512 for a system running in protected mode.
#define IROUTE_NR (sizeof(int) == 2 ? 64 : 512)
0044061 PRIVATE iroute_hash_t iroute_hash_table[IROUTE_HASH_NR][IROUTE_HASH_ASS_NR];
0044062
0044063 FORWARD oroute_t *oroute_find_ent ARGS(( int port_nr, ipaddr_t dest ));
0044064 FORWARD void oroute_del ARGS(( oroute_t *oroute ));
0044065 FORWARD oroute_t *sort_dists ARGS(( oroute_t *oroute ));
0044066 FORWARD oroute_t *sort_gws ARGS(( oroute_t *oroute ));
0044067 FORWARD oroute_uncache_nw ARGS(( ipaddr_t dest, ipaddr_t netmask ));
0044068 FORWARD iroute_uncache_nw ARGS(( ipaddr_t dest, ipaddr_t netmask ));
0044069
0044070 PUBLIC void ipr_init()ipr_init()
ipr_init() simply marks all the entries in the input routing table and the output routing table as unused.
0044071 {
0044072 int i;
0044073 oroute_t *oroute;
0044074 iroute_t *iroute;
0044075
0044076 #if ZERO
0044077 for (i= 0, oroute= oroute_table; i<OROUTE_NR; i++, oroute++)
0044078 oroute->ort_flags= ORTF_EMPTY;
0044079 static_oroute_nr= 0;
0044080 #endif
0044081 assert(OROUTE_HASH_ASS_NR == 4);
0044082
0044083 #if ZERO
0044084 for (i= 0, iroute= iroute_table; i<IROUTE_NR; i++, iroute++)
0044085 iroute->irt_flags= IRTF_EMPTY;IROUTE_NR, the number of entries in the input routing table, is #define'd as 512 if the processor is operating in protected mode.
0044086 #endif
0044087 assert(IROUTE_HASH_ASS_NR == 4);
0044088 }
0044089
0044090
0044091 PUBLIC iroute_t *iroute_frag(port_nr, dest)
0044092 int port_nr;
0044093 ipaddr_t dest;iroute_frag()
iroute_frag(port_nr, dest) first looks in the input route cache (i.e., iroute_hash_table[][]) for a route for the network to which dest, iroute_frag()'s second parameter, belongs and if it doesn't find the route in the cache, looks for the route in the main input routing table (i.e., iroute_table[]).
If iroute_frag() doesn't find the route in the cache or the routing table, it returns NULL. If iroute_frag() cannot find the route in the cache but finds the route in the main routing table, it places the route in the cache.
0044094 {
0044095 int hash, i, r_hash_ind;
0044096 iroute_hash_t *iroute_hash;
0044097 iroute_hash_t tmp_hash;
0044098 iroute_t *iroute, *bestroute;
0044099 time_t currtim;
0044100 unsigned long hash_tmp;
0044101
0044102 currtim= get_time();get_time()
get_time() returns the number of clock ticks since reboot.
Several of the clients (eth, arp, ip, tcp, and udp) use get_time() to determine an appropriate timeout value for a given operation. For example, the arp code calls get_time() to determine an appropriate amount of time to wait for a response from an arp request before giving up.
0044103
0044104 hash= hash_iroute(port_nr, dest, hash_tmp);hash_oroute() / hash_iroute()
hash_oroute() and hash_oroute() are identical.
hash_oroute()is #define'd in ipr.c:
#define hash_oroute(port_nr, ipaddr, hash_tmp) (hash_tmp= (ipaddr), \
hash_tmp= (hash_tmp >> 20) ^ hash_tmp, \
hash_tmp= (hash_tmp >> 10) ^ hash_tmp, \
hash_tmp= (hash_tmp >> 5) ^ hash_tmp, \
(hash_tmp + (port_nr)) & OROUTE_HASH_MASK)
where OROUTE_HASH_MASK is #define'd as the following:
#define OROUTE_HASH_NR 32
#define OROUTE_HASH_MASK (OROUTE_HASH_NR-1)
For an address of 192.160.1.1 on ip port 0:
hash_tmp = 192.160.1.1 = 11000000 10100000 00000001 00000001 (binary)
hash_tmp = (192.160.1.1 >> 20) ^ 192.170.1.1
= 00000000 00000000 00001100 00001010 ^ 11000000 10100000 00000001 00000001
= 11000000 10100000 00001101 00001011 = 192.168.13.11
hash_tmp = (192.168.13.11 >> 10) ^ 192.168.13.11
= 00000000 00110000 00101000 00000011 ^ 11000000 10100000 00001101 00001011
= 11000000 10010000 00100101 00001000 = 192.144.37.8
hash_tmp = (192.144.37.8 >> 5) ^ 192.144.37.8
= 00000110 00000100 10000001 00101000 ^ 11000000 10010000 00100101 00001000
= 11000110 10010100 10100100 00100000 = 198.148.164.32
return value: hash_tmp + port_nr & OROUTE_HASH_MASK
= hash_tmp + port_nr & (OROUTE_HASH_NR - 1)
= 198.148.164.32 + 0 & (32-1)
= 11000110 10010100 10100100 00100000 + 0 & 00011111
= 0
Therefore, hash_iroute(0, 192.160.1.1, 0) equals 0.
As mentioned earlier, hash_oroute() and hash_iroute() are identical. Furthermore, OROUTE_HASH_NR and IROUTE_HASH_NR are both 32 and OROUTE_HASH_MASK and IROUTE_HASH_MASK are both 31 (0001 1111 binary).
Note that the initial value of hash_tmp is meaningless.
0044105 iroute_hash= &iroute_hash_table[hash][0];iroute_hash is a pointer to the hashth row of iroute_hash_table[][], where hash is the value returned by hash_iroute().
In lines 44105 - 44135, if the destination address is one of the following entries:
iroute_hash[0].irh_addr
iroute_hash[1].irh_addr
iroute_hash[2].irh_addr
iroute_hash[3].irh_addr
then the route to this destination is already in the cache (i.e., iroute_hash_table[][]) and this route (which is of type iroute_t) can be returned. If the destination address is not one of the entries, a best route to the destination must be found in the main input routing table (i.e., iroute_table[]).
0044106 if (iroute_hash[0].irh_addr == dest)
0044107 iroute= iroute_hash[0].irh_route;
0044108 else if (iroute_hash[1].irh_addr == dest)
0044109 {
0044110 tmp_hash= iroute_hash[1];
0044111 iroute_hash[1]= iroute_hash[0];
0044112 iroute_hash[0]= tmp_hash;
0044113 iroute= tmp_hash.irh_route;
0044114 }
0044115 else if (iroute_hash[2].irh_addr == dest)
0044116 {
0044117 tmp_hash= iroute_hash[2];
0044118 iroute_hash[2]= iroute_hash[1];
0044119 iroute_hash[1]= iroute_hash[0];
0044120 iroute_hash[0]= tmp_hash;
0044121 iroute= tmp_hash.irh_route;
0044122 }
0044123 else if (iroute_hash[3].irh_addr == dest)
0044124 {
0044125 tmp_hash= iroute_hash[3];
0044126 iroute_hash[3]= iroute_hash[2];
0044127 iroute_hash[2]= iroute_hash[1];
0044128 iroute_hash[1]= iroute_hash[0];
0044129 iroute_hash[0]= tmp_hash;
0044130 iroute= tmp_hash.irh_route;
0044131 }
0044132 else
0044133 iroute= NULL;
0044134 if (iroute)
0044135 return iroute;
0044136 The destination was not in the cache (i.e., iroute_hash_table[][]). A best route must be found in the main input routing table (i.e., iroute_table[]).
0044137 bestroute= NULL;
0044138 for (i= 0, iroute= iroute_table; i < IROUTE_NR; i++, iroute++)
0044139 {
0044140 if (!(iroute->irt_flags & IRTF_INUSE))
0044141 continue;
0044142 if (((dest ^ iroute->irt_dest) & iroute->irt_subnetmask) != 0)
0044143 continue;If the destination is not in the same network as the entry in the routing table, the routing entry is not relevant for this destination.
For example, if the destination is 192.130.5.1 and the routing entry is for the 192.130.4.0/255.255.255.0 network:
(192.130.5.1 ^ 192.130.4.0) & (255.255.255.0)
= 0.0.1.1 & 255.255.255.0 = 0.0.1.0
Therefore, the routing entry is not relevant. This is logical since the network containing 192.130.5.1 and the 192.130.4.0/255.255.255.0 network could be on different sides of the world.
0044144 if (!bestroute)
0044145 {
0044146 bestroute= iroute;
0044147 continue;
0044148 }Since the destination address is in the same network as the network for this routing entry, it is a candidate for the best route. If there is more than one candidate, the best route will be decided by the following criteria:
Lines 44150 - 44159: The more specific the route, the better the route. For example, if the input routing table contains the following routes:
Destination Subnet mask Gateway 1.2.3.4 255.255.255.255 201.68.39.223 1.2.3.0 255.255.255.0 201.68.39.254 1.2.0.0 255.255.0.0 201.68.41.223 default 0.0.0.0 201.68.41.254
and a packet is sent to 1.2.3.4, which route is chosen? The first route is chosen because the route is the most specific, even if this route had the greatest distance. Similarly, the second route is chosen for packets sent to 1.2.3.5.
Lines 44161 - 44168: A dynamic route is better than a static route.
Lines 44170 - 44178: A route through the current port is preferred.
The criteria are ranked in order of significance. For example, if route A is more specific than route B, route A will be chosen over route B even if route B is a dynamic route and route A is a static route.
0044149
0044150 /* More specific netmasks are better */
0044151 if (iroute->irt_subnetmask != bestroute->irt_subnetmask)
0044152 {
0044153 if (ntohl(iroute->irt_subnetmask) >
0044154 ntohl(bestroute->irt_subnetmask))htons() / ntohs() / htonl() / ntohl()
From htons(3):
"htons() converts a 16-bit quantity from host byte order to network byte order."
Different CPU architectures group multiple bytes differently. For example, on a "little-endian" machine (an example of which is the Intel CPU), the value 0x1234 is stored in memory as 0x3412. However, on a "big-endian" machine, the value 0x1234 is stored in memory as 0x1234.
It is important that values in a header are sent across a network in a consistent manner independent of the architecture of the sending or receiving system. For this reason, a standard was chosen. The standard chosen was big-endian although it could have just as well been little-endian.
htons() is defined in /include/net/hton.h, as:
#define htons(x) (_tmp=(x), ((_tmp>>8) & 0xff) | ((_tmp<<8) & 0xff00))
ntohs() converts a 16-bit quantity from network byte order to host byte order, the reverse of htons().
htonl() and ntohl() are identical to htons() and ntohs() except that they convert 32-bit quantities instead of 16-bit quantities.
Processes generally supply header information when sending packets. The data in these fields is converted to the network format (i.e., big-endian) by the process before the process copies the data to the network service.
0044155 {
0044156 bestroute= iroute;
0044157 }
0044158 continue;
0044159 }
0044160
0044161 /* Dynamic routes override static routes */
0044162 if ((iroute->irt_flags & IRTF_STATIC) !=
0044163 (bestroute->irt_flags & IRTF_STATIC))
0044164 {
0044165 if (bestroute->irt_flags & IRTF_STATIC)
0044166 bestroute= iroute;
0044167 continue;
0044168 }
0044169
0044170 /* A route to the local interface give an opportunity
0044171 * to send redirects.
0044172 */
0044173 if (iroute->irt_port != bestroute->irt_port)
0044174 {
0044175 if (iroute->irt_port == port_nr)
0044176 bestroute= iroute;
0044177 continue;
0044178 }
0044179 }
0044180 if (bestroute == NULL)
0044181 return NULL;If the network to which the destination address belongs is not in the input routing table, return NULL.
0044182 Insert the route into the first slot in the cache (i.e., iroute_hash_table[][]) and bump the other routes down to the next slot.
0044183 iroute_hash[3]= iroute_hash[2];
0044184 iroute_hash[2]= iroute_hash[1];
0044185 iroute_hash[1]= iroute_hash[0];
0044186 iroute_hash[0].irh_addr= dest;
0044187 iroute_hash[0].irh_route= bestroute;
0044188
0044189 return bestroute;
0044190 }
0044191
0044192 PUBLIC int oroute_frag(port_nr, dest, ttl, nexthop)
0044193 int port_nr;
0044194 ipaddr_t dest;
0044195 int ttl;
0044196 ipaddr_t *nexthop;oroute_frag()
oroute_frag(port_nr, dest, ttl, nexthop) calls oroute_find_ent() to find an output route in the output route cache or the output routing table for the destination dest, oroute_frag()'s second parameter. If a route is found, the ip address of the destination's gateway is returned in a reference of nexthop, oroute_frag()'s last parameter.
0044197 {
0044198 oroute_t *oroute;
0044199
0044200 oroute= oroute_find_ent(port_nr, dest);oroute_find_ent()
oroute_find_ent(port_nr, dest) attempts first to find a route for the ip address dest, oroute_find_ent()'s second parameter, in the output route cache (i.e., output_hash_table[][]). If the route isn't in the cache, oroute_find_ent() looks for the route in the main output routing table (i.e., oroute_table[]) and then places the route in the output route cache.
0044201 if (!oroute || oroute->ort_dist > ttl)
0044202 return EDSTNOTRCH;ttl, oroute_frag()'s third parameter, is an upper limit to an acceptable distance to the destination. If the distance to the destination is greater than ttl or if a route to the destination is not in the output routing table, return EDSTNORCH (Error DeSTination NOt ReaCHable).
0044203
0044204 *nexthop= oroute->ort_gateway;The ip address of the destination's gateway is returned in a reference of nexthop, oroute_frag()'s last parameter.
0044205 return NW_OK;
0044206 }
0044207
0044208
0044209 PUBLIC int ipr_add_oroute(port_nr, dest, subnetmask, gateway,
0044210 timeout, dist, static_route, preference, oroute_p)
0044211 int port_nr;
0044212 ipaddr_t dest;
0044213 ipaddr_t subnetmask;
0044214 ipaddr_t gateway;
0044215 time_t timeout;
0044216 int dist;
0044217 int static_route;
0044218 i32_t preference;
0044219 oroute_t **oroute_p;ipr_add_oroute()
ipr_add_oroute() adds an output route to the main output routing table and, if successful, returns a reference to the new entry in the last parameter (if not NULL). ipr_add_oroute() finds either an empty entry, an expired entry, an entry with the same port, network, subnet mask, and smaller distance, or the oldest entry to use for a new dynamic route. Only an empty entry, an expired entry, or the oldest entry can be used for a new static route.
For a detailed description of the layout of the main output routing table (and specifically, the nextnw, nextgw, and nextdist fields), click here.
0044220 {
0044221 int i;
0044222 ip_port_t *ip_port;
0044223 oroute_t *oroute, *oldest_route, *prev, *nw_route, *gw_route,
0044224 *prev_route;
0044225 time_t currtim;
0044226
0044227 oldest_route= 0;
0044228 currtim= get_time();get_time()
get_time() returns the number of clock ticks since reboot.
Several of the clients (eth, arp, ip, tcp, and udp) use get_time() to determine an appropriate timeout value for a given operation. For example, the arp code calls get_time() to determine an appropriate amount of time to wait for a response from an arp request before giving up.
0044229
0044230 DBLOCK(0x10,
0044231 printf("adding oroute to "); writeIpAddr(dest);
0044232 printf("["); writeIpAddr(subnetmask); printf("] through ");
0044233 writeIpAddr(gateway);
0044234 printf(" timeout: %lds, distance %d\n",
0044235 (long)timeout/HZ, dist));
0044236
0044237 ip_port= &ip_port_table[port_nr];
0044238
0044239 /* Validate gateway */
0044240 if (((gateway ^ ip_port->ip_ipaddr) & ip_port->ip_subnetmask) != 0)The ip address of the gateway must be in the same network as the ip address of the ip port. For example, if the ip address/subnet mask of the ip port is 192.30.1.15/255.255.255.0 and the ip address of the gateway is 192.30.1.254, then this gateway is in the same network:
(192.30.1.254 ^ 192.30.1.15) & 255.255.255.0
= 0.0.0.242 & 255.255.255.0 = 0
0044241 {
0044242 DBLOCK(2, printf("ipr_add_oroute: invalid gateway: "); writeIpAddr(gateway); printf("\n"));
0044243 return EINVAL;
0044244 }
0044245
0044246 if (static_route)The number of static routes in the main output routing table is limited to 16 (OROUTE_STATIC_NR is #define'd as 16). Static routes do not replace other static routes, even if the network is the same.
0044247 {
0044248 if (static_oroute_nr >= OROUTE_STATIC_NR)
0044249 return ENOMEM;
0044250 static_oroute_nr++;
0044251 }
0044252 elseThe route is dynamic. Try to find any routes in the main output routing table that have the same port, network and subnet (lines 44255-44264) and that have the same gateway (lines 44265-44269). If such a route is found and the distance and preference are the same, update the timeout for the route and then return the route (lines 44285-44286). If a dynamic route is found that has a smaller distance, this route is chosen to be overwritten with the new information (i.e., oldest_route is set to this route).
0044253 {
0044254 /* Try to track down any old routes. */
0044255 for(oroute= oroute_head; oroute; oroute= oroute->ort_nextnw)
0044256 {
0044257 if (oroute->ort_port != port_nr)
0044258 continue;
0044259 if (oroute->ort_dest == dest &&
0044260 oroute->ort_subnetmask == subnetmask)
0044261 {
0044262 break;
0044263 }
0044264 }
0044265 for(; oroute; oroute= oroute->ort_nextgw)
0044266 {
0044267 if (oroute->ort_gateway == gateway)
0044268 break;
0044269 }
0044270 for(; oroute; oroute= oroute->ort_nextdist)
0044271 {
0044272 if ((oroute->ort_flags & ORTF_STATIC) != 0)
0044273 continue;
0044274 if (oroute->ort_dist > dist)
0044275 continue;If the new route has a greater distance than the existing route in the routing table, the new route replaces the existing route. If the new route has a smaller distance than the existing route, the existing route is kept. Why is this the case? Here is an explanation from Philip Homburg (the author of the Minix network service):
"Dynamic output routes are created as a result of default router advertisements, redirects, and TTL exceeded errors.
The TCP implementation requires a conservative estimate of the distance to the destination. So when a TTL exceeded comes in, any entry with a lower TTL will get deleted. Eventually, dynamic routing entries time-out, and default routes typically have a dist of 1."
The key word above is "conservative", which in this context means "safe." For example, if one router sends a router advertisement for a network with a distance of 5 hops and then another router sends a router advertisement for the same network with a distance of 7 hops, the second, more conservative distance is believed.
0044276 if (oroute->ort_dist == dist &&
0044277 oroute->ort_pref == preference)
0044278 {
0044279 if (timeout)
0044280 oroute->ort_exp_tim= currtim + timeout;
0044281 else
0044282 oroute->ort_exp_tim= 0;
0044283 oroute->ort_timestamp= currtim;
0044284 assert(oroute->ort_port == port_nr);
0044285 if (oroute_p != NULL)
0044286 *oroute_p= oroute;If oroute_p, ipr_add_oroute()'s last parameter, is NULL, then the caller has not passed in a pointer to a pointer to an oroute_t struct and instead passed in the value NULL for oroute_p. This is actually the case every time that ipr_add_oroute() is called (e.g., by ip_ioctl()).
0044287 return NW_OK;
0044288 }
0044289 break;
0044290 }
0044291 if (oroute)If a route has been found that has the same port, network, and subnet mask as a route in the output routing table and has a distance that is greater than the route, this route is chosen to be overwritten (i.e., oldest_route is set to this route).
0044292 {
0044293 assert(oroute->ort_port == port_nr);
0044294 oroute_del(oroute);
0044295 oroute->ort_flags= 0;
0044296 oldest_route= oroute;
0044297 }
0044298 }
0044299
0044300 if (oldest_route == NULL)If a route in the output routing table with the same port, network, and subnet mask as the route and a smaller distance than the route is not found, an entry in oroute_table[] must be found to place the new route. If an unused entry is found, use that entry (lines 44305-44306). If an expired entry for a dynamic route is found, use that entry (lines 44307-44315). Otherwise, use the oldest entry in oroute_table[] (lines 44322-44329).
Note that the variable name "oldest_route" is a misnomer since oldest_route can be an unused entry in oroute_table[] or an existing entry in oroute_table[] with the same port, network, and subnet (see line 44291). Naturally, oldest_route can also be the oldest route in oroute_table[].
0044301 {
0044302 /* Look for an unused entry, or remove an existing one */
0044303 for (i= 0, oroute= oroute_table; i<OROUTE_NR; i++, oroute++)
0044304 {
0044305 if ((oroute->ort_flags & ORTF_INUSE) == 0)
0044306 break;
0044307 if (oroute->ort_exp_tim && oroute->ort_exp_tim <
0044308 currtim)
0044309 {
0044310 oroute_del(oroute);oroute_del()
oroute_del(oroute) removes the output route oroute, oroute_del()'s only parameter, from the main output routing table and, if the route is also in the output route cache, removes the route from the output route cache (using oroute_uncache_nw).
0044311 oroute->ort_flags= 0;
0044312 break;
0044313 }
0044314 if (oroute->ort_flags & ORTF_STATIC)
0044315 continue;
0044316 if (oroute->ort_dest == 0)To add a default route using the utility add_route, one specifies the 0.0.0.0 network:
add_route -i -g 192.31.231.1 -d 0.0.0.0 -m 5 -n 0.0.0.0 -I /dev/ip0
0044317 {
0044318 /* Never remove default routes. */
0044319 continue;
0044320 }
0044321 if (oldest_route == NULL)
0044322 {
0044323 oldest_route= oroute;
0044324 continue;
0044325 }
0044326 if (oroute->ort_timestamp < oldest_route->ort_timestamp)
0044327 {
0044328 oldest_route= oroute;
0044329 }
0044330 }
0044331 if (i < OROUTE_NR)
0044332 oldest_route= oroute;
0044333 else
0044334 {
0044335 assert(oldest_route);
0044336 oroute_del(oldest_route);
0044337 oldest_route->ort_flags= 0;
0044338 }
0044339 }
0044340 At this point, either an empty route, an expired route, an old route, or a route with a smaller distance and the same port, network, and subnet mask has been found and will be used for the new route.
0044341 oldest_route->ort_dest= dest;
0044342 oldest_route->ort_gateway= gateway;
0044343 oldest_route->ort_subnetmask= subnetmask;
0044344 if (timeout)
0044345 oldest_route->ort_exp_tim= currtim + timeout;
0044346 else
0044347 oldest_route->ort_exp_tim= 0;
0044348 oldest_route->ort_timestamp= currtim;
0044349 oldest_route->ort_dist= dist;
0044350 oldest_route->ort_port= port_nr;
0044351 oldest_route->ort_flags= ORTF_INUSE;
0044352 oldest_route->ort_pref= preference;
0044353 if (static_route)
0044354 oldest_route->ort_flags |= ORTF_STATIC;
0044355
0044356 /* Insert the route by tearing apart the routing table,
0044357 * and insert the entry during the reconstruction.
0044358 */Assume that output routes A - M exist in the main output routing table:
(Note that this would be an unusual routing table. Routes A, C, D, E, and F could also have branches and sub-branches.)
Routes A, B, C, D, E, and F are all different networks (i.e., they are linked by their ort_nextnw fields). Routes B, G, H, I, and J are all for the same network and subnet but have different gateways (i.e., they are linked by their ort_nextgw fields). Routes H, K, L, and M are all for the same network and subnet and have the same gateway but have different distances and/or preferences.
Assume that the network and subnet for routes B, G, I, and J are the same as dest and subnetmask, ipr_add_oroute()'s second and third parameters, and also assume that the network and subnet and the gateway for routes H, K, L, and M are the same as dest and subnetmask and gateway, ipr_add_oroute()'s second and third and fourth parameters.
As is stated in the author's comment above, the routing table will be torn apart. First, the B->G->H->I->J linked list will be removed from the A->B->C->D->E->F linked list (the first for loop; lines 44359-44373) and then the H->K->L-> M linked list will be removed from the B->G->H->I->J linked list (the second for loop; lines 44375-44386).
0044359 for (prev= 0, nw_route= oroute_head; nw_route;
0044360 prev= nw_route, nw_route= nw_route->ort_nextnw)
0044361 {
0044362 if (nw_route->ort_port != port_nr)
0044363 continue;
0044364 if (nw_route->ort_dest == dest &&
0044365 nw_route->ort_subnetmask == subnetmask)
0044366 {
0044367 if (prev)
0044368 prev->ort_nextnw= nw_route->ort_nextnw;
0044369 else
0044370 oroute_head= nw_route->ort_nextnw;
0044371 break;
0044372 }
0044373 }
0044374 prev_route= nw_route;
0044375 for(prev= NULL, gw_route= nw_route; gw_route;
0044376 prev= gw_route, gw_route= gw_route->ort_nextgw)
0044377 {
0044378 if (gw_route->ort_gateway == gateway)
0044379 {
0044380 if (prev)
0044381 prev->ort_nextgw= gw_route->ort_nextgw;
0044382 else
0044383 nw_route= gw_route->ort_nextgw;
0044384 break;
0044385 }
0044386 }
0044387 oldest_route->ort_nextdist= gw_route;
0044388 gw_route= oldest_route;Note that for the following figures, the assumption is made (for simplicity's sake) that sort_dists() and sort_gws() do not alter the order of the routes in their respective linked lists.
Lines 44387-44388 prepend the new route (route N in the diagram) to the linked list of routes that have the same network and the same gateway.
0044389 gw_route= sort_dists(gw_route);sort_dists()
For a given output route, the ort_nextdist field points to a linked list of routes for the same network and the same gateway but with possibly different distances. sort_dists(oroute) finds the best route to the network in the linked list that begins with oroute (sort_dists()'s only parameter), moves this route to the beginning of the linked list, and returns the route (which is, obviously, the beginning of the modified linked list). The route to the network with the smallest distance is the best route. If two routes to the network are tied for the smallest distance, the route with the greater preference is the best route.
The function name "sort_dists" is somewhat misleading since the function does not do a full sort of the routes. sort_dists() simply moves the best route to a network for a given gateway to the beginning of the linked list of routes. In this way, sort_dists() is similar to sort_gws(), which also doesn't do a full sort.
0044390 gw_route->ort_nextgw= nw_route;
0044391 nw_route= gw_route;Lines 44390-44391 prepend the first route in the modified linked list of routes that have the same network and the same gateway (route N in the diagram) to the linked list of routes that have the same network (but not the same gateway).
0044392 nw_route= sort_gws(nw_route);sort_gws()
For a given output route, the ort_nextgw field points to a linked list of routes for the same network (but not the same gateway). sort_gws(oroute) finds the best route to a gateway in the linked list that begins with oroute (sort_gws()'s only parameter), moves this route to the beginning of the linked list, and returns this route (which is, obviously, the beginning of the modified linked list). The route to a gateway with the least distance is the best route. If two routes to gateways are tied for the least distance, the route with the greater preference is the best route.
The function name "sort_gws" is a misnomer since the function does not do a full sort of the routes. sort_gws() simply moves the best route to a network to the beginning of the linked list of routes. In this way, sort_gws() is similar to sort_dists(), which also doesn't do a full sort.
0044393 nw_route->ort_nextnw= oroute_head;
0044394 oroute_head= nw_route;Lines 44393-44394 prepend the first route in the modified linked list of routes that have the same network but not the same gateway (route N in the diagram) to the linked list of all routes (i.e., route N becomes oroute_head).
0044395 if (nw_route != prev_route)
0044396 oroute_uncache_nw(nw_route->ort_dest, nw_route->ort_subnetmask);oroute_uncache_nw()
oroute_uncache_nw(dest, netmask) eliminates from the output route cache (i.e., oroute_hash_table[][]) any routes for destinations that are in the network defined by the dest/netmask pair.
For example, if the following destinations appear in the output route cache:
192.30.1.1
192.30.2.1
and the dest/netmask pair is 192.30.3.1/255.255.0.0, then the routes for both destinations will be removed from the output route cache.
(192.30.1.1 ^ 192.30.3.1) & 255.255.0.0
= (0.0.2.0) & 255.255.0.0
= 0
(192.30.2.1 ^ 192.30.3.1) & 255.255.0.0
= (0.0.1.0) & 255.255.0.0
= 0
oroute_uncache_nw() performs the identical task for output routes as iroute_uncache_nw() performs for input routes.
0044397 if (oroute_p != NULL)
0044398 *oroute_p= oldest_route;If oroute_p (ipr_add_oroute()'s last parameter) is NULL, then the caller has not passed in a pointer to a pointer to an oroute_t struct and instead passed in the value NULL for oroute_p. This is actually the case every time that ipr_add_oroute() is called (e.g., by ip_ioctl()).
0044399 return NW_OK;
0044400 }
0044401
0044402
0044403 PUBLIC void ipr_gateway_down(port_nr, gateway, timeout)
0044404 int port_nr;
0044405 ipaddr_t gateway;
0044406 time_t timeout;ipr_gateway_down() is not used in any version of the network service. ipr_gateway_down() switches to another gateway if the gateway for a route is down. However, there is no code to detect that a gateway is down.
0044407 {
0044408 oroute_t *route_ind;
0044409 time_t currtim;
0044410 int i;
0044411 int result;
0044412
0044413 currtim= get_time();
0044414 for (i= 0, route_ind= oroute_table; i<OROUTE_NR; i++, route_ind++)
0044415 {
0044416 if (!(route_ind->ort_flags & ORTF_INUSE))
0044417 continue;
0044418 if (route_ind->ort_gateway != gateway)
0044419 continue;
0044420 if (route_ind->ort_exp_tim && route_ind->ort_exp_tim < currtim)
0044421 continue;
0044422 result= ipr_add_oroute(port_nr, route_ind->ort_dest,
0044423 route_ind->ort_subnetmask, gateway,
0044424 timeout, ORTD_UNREACHABLE, FALSE, 0, NULL);
0044425 assert(result == NW_OK);
0044426 }
0044427 }
0044428
0044429
0044430 PUBLIC void ipr_destunrch(port_nr, dest, netmask, timeout)
0044431 int port_nr;
0044432 ipaddr_t dest;
0044433 ipaddr_t netmask;
0044434 time_t timeout;ipr_destunrch()
ipr_destunrch(port_nr, dest, netmask, timeout) searches for a route in the output routing table and, if one is found, changes the distance of the route to ORTD_UNREACHABLE (#define'd as 512 - a very large number).
ipr_destunrch() is called from icmp_dst_unreach().
0044435 {
0044436 oroute_t *oroute;
0044437 int result;
0044438
0044439 oroute= oroute_find_ent(port_nr, dest);oroute_find_ent()
oroute_find_ent(port_nr, dest) attempts first to find a route for the ip address dest, oroute_find_ent()'s second parameter, in the output route cache (i.e., output_hash_table[][]). If the route isn't in the cache, oroute_find_ent() looks for the route in the main output routing table (i.e., oroute_table[]) and then places the route in the output route cache.
0044440
0044441 if (!oroute)
0044442 {
0044443 DBLOCK(1, printf("got a dest unreachable for ");
0044444 writeIpAddr(dest); printf("but no route present\n"));
0044445
0044446 return;
0044447 }
0044448 result= ipr_add_oroute(port_nr, dest, netmask, oroute->ort_gateway,
0044449 timeout, ORTD_UNREACHABLE, FALSE, 0, NULL);ORTD_UNREACHABLE is #define'd in ipr.h as 512 (i.e., a very high number; IP_MAX_TTL is only 255). If ipr_add_oroute() finds here a route with the same network, the same subnet mask, the same gateway, and a distance that is smaller than 512, it will replace the entry.
ipr_add_oroute()
ipr_add_oroute() adds an output route to the main output routing table and, if successful, returns a reference to the new entry in the last parameter (if not NULL). ipr_add_oroute() finds either an empty entry, an expired entry, an entry with the same port, network, subnet mask, and smaller distance, or the oldest entry to use for a new dynamic route. Only an empty entry, an expired entry, or the oldest entry can be used for a new static route.
For a detailed description of the layout of the main output routing table (and specifically, the nextnw, nextgw, and nextdist fields), click here.
0044450 assert(result == NW_OK);
0044451 }
0044452
0044453
0044454 PUBLIC void ipr_redirect(port_nr, dest, netmask, old_gateway, new_gateway,
0044455 timeout)
0044456 int port_nr;
0044457 ipaddr_t dest;
0044458 ipaddr_t netmask;
0044459 ipaddr_t old_gateway;
0044460 ipaddr_t new_gateway;
0044461 time_t timeout;ipr_redirect()
ipr_redirect(port_nr, dest, netmask, old_gateway, new_gateway, timeout) attempts to find a route for the destination dest, ipr_redirect()'s second parameter, in the output routing table. If a dynamic route whose gateway is old_gateway (ipr_redirect()'s fourth parameter) is found, this route is marked as unreachable and a new route with values of port_nr, dest, netmask, new_gateway, and timeout is added to the output routing table.
0044462 {
0044463 oroute_t *oroute;
0044464 int result;
0044465
0044466 oroute= oroute_find_ent(port_nr, dest);oroute_find_ent()
oroute_find_ent(port_nr, dest) attempts first to find a route for the ip address dest, oroute_find_ent()'s second parameter, in the output route cache (i.e., output_hash_table[][]). If the route isn't in the cache, oroute_find_ent() looks for the route in the main output routing table (i.e., oroute_table[]) and then places the route in the output route cache.
0044467
0044468 if (!oroute)
0044469 {
0044470 DBLOCK(1, printf("got a redirect for ");
0044471 writeIpAddr(dest); printf("but no route present\n"));
0044472 return;
0044473 }
0044474 if (oroute->ort_gateway != old_gateway)
0044475 {
0044476 DBLOCK(1, printf("got a redirect from ");
0044477 writeIpAddr(old_gateway); printf(" for ");
0044478 writeIpAddr(dest); printf(" but curr gateway is ");
0044479 writeIpAddr(oroute->ort_gateway); printf("\n"));
0044480 return;
0044481 }
0044482 if (oroute->ort_flags & ORTF_STATIC)
0044483 {
0044484 if (oroute->ort_dest == dest)
0044485 {
0044486 DBLOCK(1, printf("got a redirect for ");
0044487 writeIpAddr(dest);
0044488 printf("but route is fixed\n"));
0044489 return;
0044490 }
0044491 }
0044492 else
0044493 {
0044494 result= ipr_add_oroute(port_nr, dest, netmask,
0044495 oroute->ort_gateway, HZ, ORTD_UNREACHABLE,
0044496 FALSE, 0, NULL);Label the route to the network as unreachable.
ORTD_UNREACHABLE is #define'd in ipr.h as 512 (i.e., a very high number; IP_MAX_TTL is only 255). If ipr_add_oroute() finds here a route with the same network, the same subnet mask, the same gateway, and a distance that is smaller than 512, it will replace the entry.
ipr_add_oroute()
ipr_add_oroute() adds an output route to the main output routing table and, if successful, returns a reference to the new entry in the last parameter (if not NULL). ipr_add_oroute() finds either an empty entry, an expired entry, an entry with the same port, network, subnet mask, and smaller distance, or the oldest entry to use for a new dynamic route. Only an empty entry, an expired entry, or the oldest entry can be used for a new static route.
For a detailed description of the layout of the main output routing table (and specifically, the nextnw, nextgw, and nextdist fields), click here.
0044497 assert(result == NW_OK);
0044498 }
0044499 result= ipr_add_oroute(port_nr, dest, netmask, new_gateway,
0044500 timeout, 1, FALSE, 0, NULL);Add a route of the network, subnet mask, and the new gateway to the output routing table.
ipr_add_oroute()
ipr_add_oroute() adds an output route to the main output routing table and, if successful, returns a reference to the new entry in the last parameter (if not NULL). ipr_add_oroute() finds either an empty entry, an expired entry, an entry with the same port, network, subnet mask, and smaller distance, or the oldest entry to use for a new dynamic route. Only an empty entry, an expired entry, or the oldest entry can be used for a new static route.
For a detailed description of the layout of the main output routing table (and specifically, the nextnw, nextgw, and nextdist fields), click here.
0044501 assert(result == NW_OK);
0044502 }
0044503
0044504
0044505 PUBLIC void ipr_ttl_exc(port_nr, dest, netmask, timeout)
0044506 int port_nr;
0044507 ipaddr_t dest;
0044508 ipaddr_t netmask;
0044509 time_t timeout;ipr_ttl_exc()
ipr_ttl_exc(port_nr, dest, netmask, timeout) finds a route in the output routing table whose destination is dest, ipr_ttl_exc()'s second parameter, and, if a route is found, increases the distance of the route by a multiple of 2 if the result is less than IP_MAX_TTL (#define'd as 255) and increases the distance by one if the result is greater than IP_MAX_TTL.
ipr_ttl_exc() is called by icmp_time_exceeded() upon receipt of a time-exceeded icmp message.
0044510 {
0044511 oroute_t *oroute;
0044512 int new_dist;
0044513 int result;
0044514
0044515 oroute= oroute_find_ent(port_nr, dest);oroute_find_ent()
oroute_find_ent(port_nr, dest) attempts first to find a route for the ip address dest, oroute_find_ent()'s second parameter, in the output route cache (i.e., output_hash_table[][]). If the route isn't in the cache, oroute_find_ent() looks for the route in the main output routing table (i.e., oroute_table[]) and then places the route in the output route cache.
0044516
0044517 if (!oroute)
0044518 {
0044519 DBLOCK(1, printf("got a ttl exceeded for ");
0044520 writeIpAddr(dest); printf("but no route present\n"));
0044521 return;
0044522 }
0044523
0044524 new_dist= oroute->ort_dist * 2;
0044525 if (new_dist>IP_MAX_TTL)
0044526 {
0044527 new_dist= oroute->ort_dist+1;
0044528 if (new_dist>IP_MAX_TTL)
0044529 {
0044530 DBLOCK(1, printf("got a ttl exceeded for ");
0044531 writeIpAddr(dest);
0044532 printf(" but dist is %d\n",
0044533 oroute->ort_dist));
0044534 return;
0044535 }
0044536 }
0044537
0044538 result= ipr_add_oroute(port_nr, dest, netmask, oroute->ort_gateway,
0044539 timeout, new_dist, FALSE, 0, NULL);Increase the distance of the existing route either by 1 (line 44527) or by a multiple of 2 (line 44524).
ipr_add_oroute()
ipr_add_oroute() adds an output route to the main output routing table and, if successful, returns a reference to the new entry in the last parameter (if not NULL). ipr_add_oroute() finds either an empty entry, an expired entry, an entry with the same port, network, subnet mask, and smaller distance, or the oldest entry to use for a new dynamic route. Only an empty entry, an expired entry, or the oldest entry can be used for a new static route.
For a detailed description of the layout of the main output routing table (and specifically, the nextnw, nextgw, and nextdist fields), click here.
0044540 assert(result == NW_OK);
0044541 }
0044542
0044543
0044544 PUBLIC int ipr_get_oroute(ent_no, route_ent)
0044545 int ent_no;
0044546 nwio_route_t *route_ent;ipr_get_oroute()
ipr_get_oroute(ent_no, route_ent) returns the values of the ent_no (ipr_get_oroute()'s first parameter) element of the main output routing table in route_ent (ipr_get_oroute()'s second parameter). Note that route_ent is a refernce to an nwio_route_t struct.
ipr_get_oroute() is called by ip_ioctl() (which is called by the pr_routes utility) for a NWIOGIPOROUTE (NetWork IO Get IP Output ROUTE) request.
0044547 {
0044548 oroute_t *oroute;An understanding of the oroute_t type is helpful to understanding this function.
oroute_table[] / oroute_hash_table[]
"Ouput routing" is routing that is done for outgoing packets. As an example, suppose that there are two ethernet ports with corresponding ip devices of "/dev/ip0" (192.30.1.1/255.255.255.0) and "/dev/ip1" (192.30.2.1/255.255.255.0). If the following add_route command is issued:
add_route -g 192.30.2.254 -d 192.50.1.0 -m 2 -n 255.255.255.0 -I /dev/ip0
then outgoing ip packets (that did not, however, arrive on another interface) are sent out the ethernet port that corresponds to /dev/ip0 to the gateway with ip address of 192.30.2.254.
Output routes are stored in two different arrays, oroute_table[] and oroute_hash_table[][]. oroute_table[] is the main table and oroute_hash_table[][] is the cache, where routes can be quickly looked up. oroute_table[] has 32 elements and each element is of type oroute_t:
typedef struct oroute
{
int ort_port;
ipaddr_t ort_dest;
ipaddr_t ort_subnetmask;
int ort_dist;
i32_t ort_pref;
ipaddr_t ort_gateway;
time_t ort_exp_tim;
time_t ort_timestamp;
int ort_flags;
struct oroute *ort_nextnw;
struct oroute *ort_nextgw;
struct oroute *ort_nextdist;
} oroute_t;
int ort_port: The port number (e.g., ip0 is 0).
ipaddr_t ort_dest: The network address of the routing entry (e.g., 192.50.1.0).
ipaddr_t ort_subnetmask: The subnet mask of the routing entry (e.g., 255.255.255.0).
int ort_dist: The distance to the route. Routes with low distances are chosen over routes with high distances.
i32_t ort_pref: The preference of the route. Routes with high preferences are chosen over routes with low preferences. The distance of a route is of higher importance. In other words, the relative preference of two routes is only significant if and only if these two routes are tied for the lowest distance.
ipaddr_t ort_gateway: The ip address of the gateway. Packets that are not destined to systems on the local network are sent to the gateway.
time_t ort_exp_tim: The expiration time for the entry. Note that when using add_route, this value will always 0. The entries, therefore, do not expire.
time_t ort_timestamp: The time at which the entry is added to oroute_table[].
int ort_flags:
#define ORTF_EMPTY 0
#define ORTF_INUSE 1
#define ORTF_STATIC 2
Only OROUTE_STATIC_NR (#define'd as 16) static routes are allowed in the output routing table. Static and dynamic routes cannot replace static routes, even if 2 routes are to the same network.
struct oroute *ort_nextnw:
struct oroute *ort_nextgw:
struct oroute *ort_nextdist:
ort_nextnw, ort_nextgw, and ort_nextdist can best be described using a figure. The figure below represents the main output routing table, oroute_table[]:
The ort_nextnw field (red) is the linked list of routes to specific networks/subnet mask pairs. A, B, C, D, and E all are routes to different network/subnet mask pairs. For example, A could be the route to 192.30.1.0/255.255.255.0 and B could be the route to 192.30.2.0/255.255.255.0.
The ort_nextgw field (blue) links the linked lists of routes with the same network/subnet mask pairs but different gateways. D, F, and G are all routes to the same network/subnet mask pairs but all have different gateways. ort_nextdist connec
The ort_nextdist field (green) links the linked lists of routes with the same network/subnet mask pairs and the same gateway but with possibly different distances/preferences. F, H, I, and J are all routes to the same network/subnet mask pairs and the same gateway but have possibly different distances/preferences.
The oroute_hash_table[][] is a 2-dimensional array of dimensions 32x4 whose entries are of type oroute_hash_t:
typedef struct oroute_hash
{
ipaddr_t irh_addr;
iroute_t *irh_route;
} oroute_hash_t;
ipaddr_t irh_addr: The ip address (not the network address) of a system.
iroute_t *irh_route: The best route for the ip address above.
If an entry for a system does not exist in oroute_hash_table[][], the best route for the system is determined from the entries in oroute_table[]. The ip address of this system and the best route to the system (which together form an oroute_hash_t struct) is then placed in oroute_hash_table[][]. The first dimension corresponds to the hash of the ip address, as determined by the #define hash_iroute. The second dimension will be 0. The entry with the same hash that was formerly in the 0th slot will be pushed to the 1st slot, the entry that was formerly in the 1st slot will be pushed to the 2nd slot, and then entry that was formerly in the 2nd slot will be pushed to the 3rd slot. The entry that was formerly in the 3rd slot will be pushed out of oroute_hash_table[][].
The best route for the ip address can later be quickly retrieved from oroute_hash_table[][] (if it hasn't since been pushed out).
0044549
0044550 if (ent_no<0 || ent_no>= OROUTE_NR)
0044551 return ENOENT;
0044552
0044553 oroute= &oroute_table[ent_no];
0044554 if ((oroute->ort_flags & ORTF_INUSE) && oroute->ort_exp_tim &&
0044555 oroute->ort_exp_tim < get_time())
0044556 {
0044557 oroute_del(oroute);
0044558 oroute->ort_flags &= ~ORTF_INUSE;
0044559 }
0044560
0044561 route_ent->nwr_ent_no= ent_no;
0044562 route_ent->nwr_ent_count= OROUTE_NR;
0044563 route_ent->nwr_dest= oroute->ort_dest;
0044564 route_ent->nwr_netmask= oroute->ort_subnetmask;
0044565 route_ent->nwr_gateway= oroute->ort_gateway;
0044566 route_ent->nwr_dist= oroute->ort_dist;
0044567 route_ent->nwr_flags= NWRF_EMPTY;
0044568 if (oroute->ort_flags & ORTF_INUSE)
0044569 {
0044570 route_ent->nwr_flags |= NWRF_INUSE;
0044571 if (oroute->ort_flags & ORTF_STATIC)
0044572 route_ent->nwr_flags |= NWRF_STATIC;
0044573 }
0044574 route_ent->nwr_pref= oroute->ort_pref;
0044575 route_ent->nwr_ifaddr= ip_get_ifaddr(oroute->ort_port);
0044576 return NW_OK;
0044577 }
0044578
0044579
0044580 PRIVATE oroute_t *oroute_find_ent(port_nr, dest)
0044581 int port_nr;
0044582 ipaddr_t dest;oroute_find_ent()
oroute_find_ent(port_nr, dest) attempts first to find a route for the ip address dest, oroute_find_ent()'s second parameter, in the output route cache (i.e., output_hash_table[][]). If the route isn't in the cache, oroute_find_ent() looks for the route in the main output routing table (i.e., oroute_table[]) and then places the route in the output route cache.
0044583 {
0044584 int hash, i, r_hash_ind;
0044585 oroute_hash_t *oroute_hash;
0044586 oroute_hash_t tmp_hash;
0044587 oroute_t *oroute, *bestroute;
0044588 time_t currtim;
0044589 unsigned long hash_tmp;
0044590
0044591 currtim= get_time();get_time()
get_time() returns the number of clock ticks since reboot.
Several of the clients (eth, arp, ip, tcp, and udp) use get_time() to determine an appropriate timeout value for a given operation. For example, the arp code calls get_time() to determine an appropriate amount of time to wait for a response from an arp request before giving up.
0044592
0044593 hash= hash_oroute(port_nr, dest, hash_tmp);hash_oroute() / hash_iroute()
hash_oroute() and hash_oroute() are identical.
hash_oroute()is #define'd in ipr.c:
#define hash_oroute(port_nr, ipaddr, hash_tmp) (hash_tmp= (ipaddr), \
hash_tmp= (hash_tmp >> 20) ^ hash_tmp, \
hash_tmp= (hash_tmp >> 10) ^ hash_tmp, \
hash_tmp= (hash_tmp >> 5) ^ hash_tmp, \
(hash_tmp + (port_nr)) & OROUTE_HASH_MASK)
where OROUTE_HASH_MASK is #define'd as the following:
#define OROUTE_HASH_NR 32
#define OROUTE_HASH_MASK (OROUTE_HASH_NR-1)
For an address of 192.160.1.1 on ip port 0:
hash_tmp = 192.160.1.1 = 11000000 10100000 00000001 00000001 (binary)
hash_tmp = (192.160.1.1 >> 20) ^ 192.170.1.1
= 00000000 00000000 00001100 00001010 ^ 11000000 10100000 00000001 00000001
= 11000000 10100000 00001101 00001011 = 192.168.13.11
hash_tmp = (192.168.13.11 >> 10) ^ 192.168.13.11
= 00000000 00110000 00101000 00000011 ^ 11000000 10100000 00001101 00001011
= 11000000 10010000 00100101 00001000 = 192.144.37.8
hash_tmp = (192.144.37.8 >> 5) ^ 192.144.37.8
= 00000110 00000100 10000001 00101000 ^ 11000000 10010000 00100101 00001000
= 11000110 10010100 10100100 00100000 = 198.148.164.32
return value: hash_tmp + port_nr & OROUTE_HASH_MASK
= hash_tmp + port_nr & (OROUTE_HASH_NR - 1)
= 198.148.164.32 + 0 & (32-1)
= 11000110 10010100 10100100 00100000 + 0 & 00011111
= 0
Therefore, hash_iroute(0, 192.160.1.1, 0) equals 0.
As mentioned earlier, hash_oroute() and hash_iroute() are identical. Furthermore, OROUTE_HASH_NR and IROUTE_HASH_NR are both 32 and OROUTE_HASH_MASK and IROUTE_HASH_MASK are both 31 (0001 1111 binary).
Note that the initial value of hash_tmp is meaningless.
0044594 oroute_hash= &oroute_hash_table[hash][0];oroute_hash is a pointer to the hashth row of oroute_hash_table[][], where hash is the value returned by hash_oroute().
In lines 44595 - 44622, if the destination address is one of the following entries:
oroute_hash[0].orh_addr
oroute_hash[1].orh_addr
oroute_hash[2].orh_addr
oroute_hash[3].orh_addr
then the route to this destination is already in the cache (i.e., oroute_hash_table[][]) and this route (which is of type oroute_t) can be returned. If the destination address is not one of the entries, a best route to the destination must be found in the main output routing table (i.e., oroute_table[]).
0044595 if (oroute_hash[0].orh_addr == dest)
0044596 oroute= oroute_hash[0].orh_route;
0044597 else if (oroute_hash[1].orh_addr == dest)
0044598 {
0044599 tmp_hash= oroute_hash[1];
0044600 oroute_hash[1]= oroute_hash[0];
0044601 oroute_hash[0]= tmp_hash;
0044602 oroute= tmp_hash.orh_route;
0044603 }
0044604 else if (oroute_hash[2].orh_addr == dest)
0044605 {
0044606 tmp_hash= oroute_hash[2];
0044607 oroute_hash[2]= oroute_hash[1];
0044608 oroute_hash[1]= oroute_hash[0];
0044609 oroute_hash[0]= tmp_hash;
0044610 oroute= tmp_hash.orh_route;
0044611 }
0044612 else if (oroute_hash[3].orh_addr == dest)
0044613 {
0044614 tmp_hash= oroute_hash[3];
0044615 oroute_hash[3]= oroute_hash[2];
0044616 oroute_hash[2]= oroute_hash[1];
0044617 oroute_hash[1]= oroute_hash[0];
0044618 oroute_hash[0]= tmp_hash;
0044619 oroute= tmp_hash.orh_route;
0044620 }
0044621 else
0044622 oroute= NULL;
0044623 if (oroute)If a route was found in the output route cache, verify that the corresponding route in the main output routing table has not expired. If the route has expired, remove the route from the main output routing table. If the route has not expired, return the route.
0044624 {
0044625 assert(oroute->ort_port == port_nr);
0044626 if (oroute->ort_exp_tim && oroute->ort_exp_tim<currtim)
0044627 {
0044628 oroute_del(oroute);oroute_del()
oroute_del(oroute) removes the output route oroute, oroute_del()'s only parameter, from the main output routing table and, if the route is also in the output route cache, removes the route from the output route cache (using oroute_uncache_nw).
0044629 oroute->ort_flags &= ~ORTF_INUSE;
0044630 }
0044631 else
0044632 return oroute;
0044633 }
0044634 The destination was either not found in the cache (i.e., oroute_hash_table[][]) or the associated route in the main output routing table (oroute_table[]) has expired. A best route must be found in the main output routing table.
0044635 bestroute= NULL;
0044636 for (oroute= oroute_head; oroute; oroute= oroute->ort_nextnw)
0044637 {
0044638 if (((dest ^ oroute->ort_dest) & oroute->ort_subnetmask) != 0)
0044639 continue;If the destination is not in the same network as the entry in the routing table, the routing entry is not relevant for this destination.
For example, if the destination is 192.130.5.1 and the routing entry is for the 192.130.4.0/255.255.255.0 network:
(192.130.5.1 ^ 192.130.4.0) & (255.255.255.0)
= 0.0.1.1 & 255.255.255.0 = 0.0.1.0
Therefore, the routing entry is not relevant. This is logical since the network containing 192.130.5.1 and the 192.130.4.0/255.255.255.0 network could be on different sides of the world.
0044640 if (oroute->ort_port != port_nr)
0044641 continue;The route in the main output routing table must have a port number of port_nr, oroute_find_ent()'s first parameter.
0044642 if (!bestroute)
0044643 {
0044644 bestroute= oroute;
0044645 continue;
0044646 }
0044647 assert(oroute->ort_dest != bestroute->ort_dest);Since the destination address is in the same network as the network for this routing entry, it is a candidate for the best route. If there is more than one candidate, the best route will be decided by the subnet mask. The more specific the subnet mask, the better (e.g., 255.255.255.0 beats 255.255.0.0).
0044648 if (ntohl(oroute->ort_subnetmask) >
0044649 ntohl(bestroute->ort_subnetmask))
0044650 {
0044651 bestroute= oroute;
0044652 continue;
0044653 }
0044654 }
0044655 if (bestroute == NULL)
0044656 return NULL;If the network to which the destination address belongs is not in the input routing table, return NULL.
0044657 Insert the route into the first slot in the cache (i.e., oroute_hash_table[][]) and bump the other routes down to the next slot.
0044658 oroute_hash[3]= oroute_hash[2];
0044659 oroute_hash[2]= oroute_hash[1];
0044660 oroute_hash[1]= oroute_hash[0];
0044661 oroute_hash[0].orh_addr= dest;
0044662 oroute_hash[0].orh_route= bestroute;
0044663
0044664 return bestroute;
0044665 }
0044666
0044667
0044668 PRIVATE void oroute_del(oroute)
0044669 oroute_t *oroute;oroute_del()
oroute_del(oroute) removes the output route oroute, oroute_del()'s only parameter, from the main output routing table and, if the route is also in the output route cache, removes the route from the output route cache (using oroute_uncache_nw).
0044670 {
0044671 oroute_t *prev, *nw_route, *gw_route, *dist_route, *prev_route;
0044672 An output routing table (i.e., iroute_table[]) is as follows:
All routes in the linked list linked by the ort_nextnw field are for different networks and/or subnet masks. Therefore, routes 1,2,3,4, and 5 are for different networks and/or subnet masks.
All routes in the linked list linked by the ort_nextgw field are for the same network and subnet mask but are for different gateways. Therefore, routes 2,6,7, and 11 are for the same network and subnet mask but for a different gateway.
All routes in the linked list linked by the ort_nextdist field are for the same network, subnet mask, and gateway but have different distances and/or preferences. Therefore, routes 7, 8, 9, and 10 are for the same network, subnet mask, and gateway but have different distances and/or preferences.
Assume that oroute, oroute_del()'s only parameter, is route 9.
Lines 44673-44687 find route 2, the first route in the linked list of routes with the same network and subnet mask but different gateways as oroute and de-links this route from the ort_nextnw linked list.
Lines 44688-44699 find route 7, the first route in the linked list of routes with the same network, subnet mask and gateway (but possibly different distances) as oroute and de-links this route from the ort_nextgw linked list.
Lines 44700-44710 find route 9, which is oroute, and de-links this route from the ort_nextdist linked list.
0044673 for (prev= NULL, nw_route= oroute_head; nw_route;
0044674 prev= nw_route, nw_route= nw_route->ort_nextnw)
0044675 {
0044676 if (oroute->ort_port == nw_route->ort_port &&
0044677 oroute->ort_dest == nw_route->ort_dest &&
0044678 oroute->ort_subnetmask == nw_route->ort_subnetmask)
0044679 {
0044680 break;
0044681 }
0044682 }
0044683 assert(nw_route);
0044684 if (prev)
0044685 prev->ort_nextnw= nw_route->ort_nextnw;
0044686 else
0044687 oroute_head= nw_route->ort_nextnw;
0044688 prev_route= nw_route;
0044689 for (prev= NULL, gw_route= nw_route; gw_route;
0044690 prev= gw_route, gw_route= gw_route->ort_nextgw)
0044691 {
0044692 if (oroute->ort_gateway == gw_route->ort_gateway)
0044693 break;
0044694 }
0044695 assert(gw_route);
0044696 if (prev)
0044697 prev->ort_nextgw= gw_route->ort_nextgw;
0044698 else
0044699 nw_route= gw_route->ort_nextgw;
0044700 for (prev= NULL, dist_route= gw_route; dist_route;
0044701 prev= dist_route, dist_route= dist_route->ort_nextdist)
0044702 {
0044703 if (oroute == dist_route)
0044704 break;
0044705 }
0044706 assert(dist_route);
0044707 if (prev)
0044708 prev->ort_nextdist= dist_route->ort_nextdist;
0044709 else
0044710 gw_route= dist_route->ort_nextdist;
0044711 gw_route= sort_dists(gw_route);sort_dists()
For a given output route, the ort_nextdist field points to a linked list of routes for the same network and the same gateway but with possibly different distances. sort_dists(oroute) finds the best route to the network in the linked list that begins with oroute (sort_dists()'s only parameter), moves this route to the beginning of the linked list, and returns the route (which is, obviously, the beginning of the modified linked list). The route to the network with the smallest distance is the best route. If two routes to the network are tied for the smallest distance, the route with the greater preference is the best route.
The function name "sort_dists" is somewhat misleading since the function does not do a full sort of the routes. sort_dists() simply moves the best route to a network for a given gateway to the beginning of the linked list of routes. In this way, sort_dists() is similar to sort_gws(), which also doesn't do a full sort.
0044712 if (gw_route != NULL)
0044713 {
0044714 gw_route->ort_nextgw= nw_route;
0044715 nw_route= gw_route;
0044716 }At this point, the output routing table appears as follows (the dotted blue line was just added):
Note that the in the figure above and the figure below, it is assumed that sort_dists() and sort_gws() do not alter the order of the routes in the ort_nextdist and ort_nextgw linked lists.
0044717 nw_route= sort_gws(nw_route);sort_gws()
For a given output route, the ort_nextgw field points to a linked list of routes for the same network (but not the same gateway). sort_gws(oroute) finds the best route to a gateway in the linked list that begins with oroute (sort_gws()'s only parameter), moves this route to the beginning of the linked list, and returns this route (which is, obviously, the beginning of the modified linked list). The route to a gateway with the least distance is the best route. If two routes to gateways are tied for the least distance, the route with the greater preference is the best route.
The function name "sort_gws" is a misnomer since the function does not do a full sort of the routes. sort_gws() simply moves the best route to a network to the beginning of the linked list of routes. In this way, sort_gws() is similar to sort_dists(), which also doesn't do a full sort.
0044718 if (nw_route != NULL)
0044719 {
0044720 nw_route->ort_nextnw= oroute_head;
0044721 oroute_head= nw_route;
0044722 }At this point, the output routing table appears as follows (the dotted red line was just added):
Note that route 7 has become the new oroute_head.
0044723 if (nw_route != prev_route)
0044724 {
0044725 oroute_uncache_nw(prev_route->ort_dest,
0044726 prev_route->ort_subnetmask);oroute_uncache_nw()
oroute_uncache_nw(dest, netmask) eliminates from the output route cache (i.e., oroute_hash_table[][]) any routes for destinations that are in the network defined by the dest/netmask pair.
For example, if the following destinations appear in the output route cache:
192.30.1.1
192.30.2.1
and the dest/netmask pair is 192.30.3.1/255.255.0.0, then the routes for both destinations will be removed from the output route cache.
(192.30.1.1 ^ 192.30.3.1) & 255.255.0.0
= (0.0.2.0) & 255.255.0.0
= 0
(192.30.2.1 ^ 192.30.3.1) & 255.255.0.0
= (0.0.1.0) & 255.255.0.0
= 0
oroute_uncache_nw() performs the identical task for output routes as iroute_uncache_nw() performs for input routes.
0044727 }
0044728 }
0044729
0044730
0044731 PRIVATE oroute_t *sort_dists(oroute)
0044732 oroute_t *oroute;sort_dists()
For a given output route, the ort_nextdist field points to a linked list of routes for the same network and the same gateway but with possibly different distances. sort_dists(oroute) finds the best route to the network in the linked list that begins with oroute (sort_dists()'s only parameter), moves this route to the beginning of the linked list, and returns the route (which is, obviously, the beginning of the modified linked list). The route to the network with the smallest distance is the best route. If two routes to the network are tied for the smallest distance, the route with the greater preference is the best route.
The function name "sort_dists" is somewhat misleading since the function does not do a full sort of the routes. sort_dists() simply moves the best route to a network for a given gateway to the beginning of the linked list of routes. In this way, sort_dists() is similar to sort_gws(), which also doesn't do a full sort.
0044733 {
0044734 oroute_t *r, *prev, *best, *best_prev;
0044735 int best_dist, best_pref;
0044736
0044737 best= NULL;The for loop on lines 44738-44756 simply finds the best route to a network in a linked list of routes. The route to a network with the least distance is the best route. If two routes to the network are tied for the least distance, the route with the greater preference is the best route.
0044738 for (prev= NULL, r= oroute; r; prev= r, r= r->ort_nextdist)
0044739 {
0044740 if (best == NULL)
0044741 ; /* Force assignment to best */
0044742 else if (r->ort_dist != best_dist)
0044743 {
0044744 if (r->ort_dist > best_dist)
0044745 continue;
0044746 }
0044747 else
0044748 {
0044749 if (r->ort_pref <= best_pref)
0044750 continue;
0044751 }
0044752 best= r;
0044753 best_prev= prev;
0044754 best_dist= r->ort_dist;
0044755 best_pref= r->ort_pref;
0044756 }Lines 44758-44761 handle the case that oroute is null (in which case, null is returned). Lines 44762-44766 handle the case that oroute is a linked list with exactly one route (in which case, oroute - which will be a single route - is returned).
0044757 if (!best)
0044758 {
0044759 assert(oroute == NULL);
0044760 return oroute;
0044761 }
0044762 if (!best_prev)
0044763 {
0044764 assert(best == oroute);
0044765 return oroute;
0044766 }Line 44767 removes best from the linked list by linking the route before best to the route after best and line 44768 then inserts best before the previous beginning of the linked list (i.e., oroute). The new beginning of the linked list is then returned.
0044767 best_prev->ort_nextdist= best->ort_nextdist;
0044768 best->ort_nextdist= oroute;
0044769 return best;
0044770 }
0044771
0044772
0044773 PRIVATE oroute_t *sort_gws(oroute)
0044774 oroute_t *oroute;sort_gws()
For a given output route, the ort_nextgw field points to a linked list of routes for the same network (but not the same gateway). sort_gws(oroute) finds the best route to a gateway in the linked list that begins with oroute (sort_gws()'s only parameter), moves this route to the beginning of the linked list, and returns this route (which is, obviously, the beginning of the modified linked list). The route to a gateway with the least distance is the best route. If two routes to gateways are tied for the least distance, the route with the greater preference is the best route.
The function name "sort_gws" is a misnomer since the function does not do a full sort of the routes. sort_gws() simply moves the best route to a network to the beginning of the linked list of routes. In this way, sort_gws() is similar to sort_dists(), which also doesn't do a full sort.
0044775 {
0044776 oroute_t *r, *prev, *best, *best_prev;
0044777 int best_dist, best_pref;
0044778
0044779 best= NULL;The for loop on lines 44780-44798 simply finds the best route to a gateway in a linked list of routes. The route to a gateway with the least distance is the best route. If two routes to gateways are tied for the least distance, the route with the greater preference is the best route.
0044780 for (prev= NULL, r= oroute; r; prev= r, r= r->ort_nextgw)
0044781 {
0044782 if (best == NULL)
0044783 ; /* Force assignment to best */
0044784 else if (r->ort_dist != best_dist)
0044785 {
0044786 if (r->ort_dist > best_dist)
0044787 continue;
0044788 }
0044789 else
0044790 {
0044791 if (r->ort_pref <= best_pref)
0044792 continue;
0044793 }
0044794 best= r;
0044795 best_prev= prev;
0044796 best_dist= r->ort_dist;
0044797 best_pref= r->ort_pref;
0044798 }Lines 44799-44803 handle the case that oroute is null (in which case, null is returned). Lines 44804-44807 handle the case that oroute is a linked list with exactly one route (in which case, oroute - which will be a single route - is returned).
0044799 if (!best)
0044800 {
0044801 assert(oroute == NULL);
0044802 return oroute;
0044803 }
0044804 if (!best_prev)
0044805 {
0044806 assert(best == oroute);
0044807 return oroute;
0044808 }Line 44809 removes best from the linked list by linking the route before best to the route after best and line 44810 then inserts best before the previous beginning of the linked list (i.e., oroute). The new beginning of the linked list is then returned.
0044809 best_prev->ort_nextgw= best->ort_nextgw;
0044810 best->ort_nextgw= oroute;
0044811 return best;
0044812 }
0044813
0044814
0044815 PRIVATE oroute_uncache_nw(dest, netmask)
0044816 ipaddr_t dest;
0044817 ipaddr_t netmask;oroute_uncache_nw()
oroute_uncache_nw(dest, netmask) eliminates from the output route cache (i.e., oroute_hash_table[][]) any routes for destinations that are in the network defined by the dest/netmask pair.
For example, if the following destinations appear in the output route cache:
192.30.1.1
192.30.2.1
and the dest/netmask pair is 192.30.3.1/255.255.0.0, then the routes for both destinations will be removed from the output route cache.
(192.30.1.1 ^ 192.30.3.1) & 255.255.0.0
= (0.0.2.0) & 255.255.0.0
= 0
(192.30.2.1 ^ 192.30.3.1) & 255.255.0.0
= (0.0.1.0) & 255.255.0.0
= 0
oroute_uncache_nw() performs the identical task for output routes as iroute_uncache_nw() performs for input routes.
0044818 {
0044819 int i, j;
0044820 oroute_hash_t *oroute_hash;
0044821
0044822 for (i= 0, oroute_hash= &oroute_hash_table[0][0];
0044823 i<OROUTE_HASH_NR; i++, oroute_hash += OROUTE_HASH_ASS_NR)Search every element in the output route cache (i.e., oroute_hash_table[][]) for networks that are a subset of the network defined by the dest/netmask pair.
0044824 {
0044825 for (j= 0; j<OROUTE_HASH_ASS_NR; j++)
0044826 {
0044827 if (((oroute_hash[j].orh_addr ^ dest) & netmask) == 0)
0044828 {
0044829 oroute_hash[j].orh_addr= 0;
0044830 oroute_hash[j].orh_route= NULL;
0044831 }
0044832 }
0044833 }
0044834 }
0044835
0044836
0044837 /*
0044838 * Input routing
0044839 */
0044840
0044841 PUBLIC int ipr_get_iroute(ent_no, route_ent)
0044842 int ent_no;
0044843 nwio_route_t *route_ent;ipr_get_iroute()
ipr_get_iroute(ent_no, route_ent) returns the values of the ent_no (ipr_get_iroute()'s first parameter) element of the input routing table in route_ent (ipr_get_iroute()'s second parameter). Note that route_ent is a refernce to an nwio_route_t struct.
ipr_get_iroute() is called by ip_ioctl() (which is called by the pr_routes utility) for a NWIOGIPIROUTE (NetWork IO Get IP Input ROUTE) request.
0044844 {
0044845 iroute_t *iroute;An understanding of the iroute_t type is helpful to understanding this function.
iroute_table[] / iroute_hash_table[]
"Input routing" is routing that is done between interfaces. As an example, suppose that there are two ethernet ports and the corresponding ip port of the first ethernet (which corresponds to the device "/dev/ip0") has an ip address/subnet mask of 192.30.1.1/255.255.255.0 and the ip port of the second ethernet (which corresponds to the device "/dev/ip1") has an ip address/subnet mask of 192.30.2.1/255.255.255.0. If the following add_route command is issued:
add_route -i -g 0.0.0.0 -d 192.30.1.0 -m 1 -n 255.255.255.0 -I /dev/ip0
then ip packets arriving on the second ethernet destined for the 192.30.1.0/255.255.255.0 network will be routed to the first ethernet port.
Input routes are stored in two different arrays, iroute_table[] and iroute_hash_table[][]. iroute_table[] is the main table and iroute_hash_table[][] is the cache, where routes can be quickly looked up. iroute_table[] has 512 elements and each element is of type iroute_t:
typedef struct iroute
{
ipaddr_t irt_dest;
ipaddr_t irt_gateway;
ipaddr_t irt_subnetmask;
int irt_dist;
int irt_port;
int irt_flags;
} iroute_t;
ipaddr_t irt_dest: The network address of the routing entry (e.g., 192.30.1.0).
ipaddr_t irt_gateway: The gateway to which packets that are not destined to machines on the local network are sent.
ipaddr_t irt_subnetmask: The subnet mask of the routing entry (e.g., 255.255.255.0).
int irt_dist: The distance. Routes with low distances are chosen over routes with high distances.
int irt_port: The port number (e.g., ip0 is 0).
int irt_flags: irt_flags can be one of the following:
#define IRTF_EMPTY 0
#define IRTF_INUSE 1
#define IRTF_STATIC 2
Static input routes behave differently than dynamic input routes. If a static route is added to the input routing table, the route will not not replace any pre-existing route (static or dynamic) even if the values of the route (e.g., destination network) are the same. A dynamic input route, on the other hand, will replace another dynamic input route.
The iroute_hash_table[][] is a 2-dimensional array of dimensions 32x4 whose entries are of type iroute_hash_t:
typedef struct iroute_hash
{
ipaddr_t irh_addr;
iroute_t *irh_route;
} iroute_hash_t;
ipaddr_t irh_addr: The ip address (not the network address) of a system.
iroute_t *irh_route: The best route for the ip address above.
If an entry for a system does not exist in iroute_hash_table[][], the best route for the system is determined from the entries in iroute_table[]. The ip address of this system and the best route to the system (which together form an iroute_hash_t struct) is then placed in iroute_hash_table[][]. The first dimension corresponds to the hash of the ip address, as determined by the #define hash_iroute. The second dimension will be 0. The entry with the same hash that was formerly in the 0th slot will be pushed to the 1st slot, the entry that was formerly in the 1st slot will be pushed to the 2nd slot, and then entry that was formerly in the 2nd slot will be pushed to the 3rd slot. The entry that was formerly in the 3rd slot will be pushed out of iroute_hash_table[][].
The best route for the ip address can then later be quickly retrieved from iroute_hash_table[][] (if it hasn't since been pushed out).
0044846
0044847 if (ent_no<0 || ent_no>= IROUTE_NR)
0044848 return ENOENT;
0044849
0044850 iroute= &iroute_table[ent_no];
0044851
0044852 route_ent->nwr_ent_count= IROUTE_NR;
0044853 route_ent->nwr_dest= iroute->irt_dest;
0044854 route_ent->nwr_netmask= iroute->irt_subnetmask;
0044855 route_ent->nwr_gateway= iroute->irt_gateway;
0044856 route_ent->nwr_dist= iroute->irt_dist;
0044857 route_ent->nwr_flags= NWRF_EMPTY;
0044858 if (iroute->irt_flags & IRTF_INUSE)
0044859 {
0044860 route_ent->nwr_flags |= NWRF_INUSE;
0044861 if (iroute->irt_flags & IRTF_STATIC)
0044862 route_ent->nwr_flags |= NWRF_STATIC;
0044863 if (iroute->irt_dist == IRTD_UNREACHABLE)
0044864 route_ent->nwr_flags |= NWRF_UNREACHABLE;
0044865 }
0044866 route_ent->nwr_pref= 0;
0044867 route_ent->nwr_ifaddr= ip_get_ifaddr(iroute->irt_port);Each input route is associated with an ip port, which is irt_port.
ip_get_ifaddr()
ip_get_ifaddr(port_nr) simply returns the ip address of the ip port whose index within ip_port_table[] is port_nr, ip_get_ifaddr()'s only parameter.
0044868 return NW_OK;
0044869 }
0044870
0044871
0044872 PUBLIC int ipr_add_iroute(port_nr, dest, subnetmask, gateway,
0044873 dist, static_route, iroute_p)
0044874 int port_nr;
0044875 ipaddr_t dest;
0044876 ipaddr_t subnetmask;
0044877 ipaddr_t gateway;
0044878 int dist;
0044879 int static_route;
0044880 iroute_t **iroute_p;ipr_add_iroute()
ipr_add_iroute(port_nr, dest, subnetmask, gateway, dist, static_route, iroute_p) adds an input route (with the values of the ipr_add_iroute()'s parameters) to the input routing table and removes any associated entries from the input route cache.
Note that static routes are handled differently than dynamic routes. A static input route does not replace any pre-existing route (static or dynamic) even if the values are the same. A dynamic input route, on the other hand, will replace another dynamic input route.
ipr_add_route() is called by ip_ioctl() when called by the add_route utility with the -i option.
0044881 {
0044882 int i;
0044883 iroute_t *iroute, *unused_route;
0044884
0044885 unused_route= NULL;
0044886 if (static_route)
0044887 {
0044888 /* Static routes are not reused automatically, so we look
0044889 * for an unused entry.
0044890 */
0044891 for(i= 0, iroute= iroute_table; i<IROUTE_NR; i++, iroute++)
0044892 {
0044893 if ((iroute->irt_flags & IRTF_INUSE) == 0)
0044894 break;
0044895 }
0044896 if (i != IROUTE_NR)
0044897 unused_route= iroute;
0044898 }
0044899 elseAdd a dynamic input route. If a dynamic input route already exists with the same values, overwrite this route.
0044900 {
0044901 /* Try to track down any old routes, and look for an
0044902 * unused one.
0044903 */
0044904 for(i= 0, iroute= iroute_table; i<IROUTE_NR; i++, iroute++)
0044905 {
0044906 if ((iroute->irt_flags & IRTF_INUSE) == 0)
0044907 {
0044908 unused_route= iroute;
0044909 continue;
0044910 }
0044911 if ((iroute->irt_flags & IRTF_STATIC) != 0)
0044912 continue;
0044913 if (iroute->irt_port != port_nr ||
0044914 iroute->irt_dest != dest ||
0044915 iroute->irt_subnetmask != subnetmask ||
0044916 iroute->irt_gateway != gateway)
0044917 {
0044918 continue;
0044919 }
0044920 break;
0044921 }
0044922 if (i != IROUTE_NR)
0044923 unused_route= iroute;
0044924 }
0044925 If an unused entry is not found, return ENOMEM. Otherwise, fill in the available entry's fields with the values that were passed in as parameters.
0044926 if (unused_route == NULL)
0044927 return ENOMEM;
0044928 iroute= unused_route;
0044929
0044930 iroute->irt_port= port_nr;
0044931 iroute->irt_dest= dest;
0044932 iroute->irt_subnetmask= subnetmask;
0044933 iroute->irt_gateway= gateway;
0044934 iroute->irt_dist= dist;
0044935 iroute->irt_flags= IRTF_INUSE;
0044936 if (static_route)
0044937 iroute->irt_flags |= IRTF_STATIC;
0044938
0044939 iroute_uncache_nw(iroute->irt_dest, iroute->irt_subnetmask);
0044940 if (iroute_p != NULL)
0044941 *iroute_p= iroute;
0044942 return NW_OK;
0044943 }
0044944
0044945
0044946 PUBLIC int ipr_del_iroute(port_nr, dest, subnetmask, gateway,
0044947 dist, static_route)
0044948 int port_nr;
0044949 ipaddr_t dest;
0044950 ipaddr_t subnetmask;
0044951 ipaddr_t gateway;
0044952 int dist;
0044953 int static_route;ipr_del_iroute()
ipr_del_iroute(port_nr, dest, subnetmask, gateway, dist, static_route) eliminates from the main input routing table (i.e., iroute_table[][]) any routes whose port number, destination, subnet mask, gateway, distance and whether it's a static route match up with the parameters of ipr_del_iroute().
0044954 {
0044955 int i;
0044956 iroute_t *iroute;
0044957
0044958 /* Try to track down any old routes, and look for an
0044959 * unused one.
0044960 */
0044961 for(i= 0, iroute= iroute_table; i<IROUTE_NR; i++, iroute++)Look for matching entries in the main input routing table (i.e., iroute_table[]). The route must be valid (lines 44963-44964) and the route must have the same values as the parameters passed into ipr_del_iroute() (lines 44965-44974).
0044962 {
0044963 if ((iroute->irt_flags & IRTF_INUSE) == 0)
0044964 continue;
0044965 if (iroute->irt_port != port_nr ||
0044966 iroute->irt_dest != dest ||
0044967 iroute->irt_subnetmask != subnetmask ||
0044968 iroute->irt_gateway != gateway)
0044969 {
0044970 continue;
0044971 }
0044972 if (!!(iroute->irt_flags & IRTF_STATIC) != static_route)
0044973 continue;
0044974 break;
0044975 }
0044976
0044977 if (i == IROUTE_NR)
0044978 return ESRCH;
0044979
0044980 iroute_uncache_nw(iroute->irt_dest, iroute->irt_subnetmask);
0044981 iroute->irt_flags= IRTF_EMPTY;
0044982 return NW_OK;
0044983 }
0044984
0044985
0044986 PRIVATE iroute_uncache_nw(dest, netmask)
0044987 ipaddr_t dest;
0044988 ipaddr_t netmask;iroute_uncache_nw()
iroute_uncache_nw(dest, netmask) eliminates from the input route cache (i.e., iroute_hash_table[][]) any routes for destinations that are in the network defined by the dest/netmask pair.
For example, if the following destinations appear in the input route cache:
192.30.1.1
192.30.2.1
and the dest/netmask pair is 192.30.3.1/255.255.0.0, then the routes for both destinations will be removed from the input route cache.
(192.30.1.1 ^ 192.30.3.1) & 255.255.0.0
= (0.0.2.0) & 255.255.0.0
= 0
(192.30.2.1 ^ 192.30.3.1) & 255.255.0.0
= (0.0.1.0) & 255.255.0.0
= 0
iroute_uncache_nw() performs the identical task for input routes as oroute_uncache_nw() performs for output routes.
0044989 {
0044990 int i, j;
0044991 iroute_hash_t *iroute_hash;
0044992
0044993 for (i= 0, iroute_hash= &iroute_hash_table[0][0];
0044994 i<IROUTE_HASH_NR; i++, iroute_hash += IROUTE_HASH_ASS_NR)Search every element in the input route cache (i.e., iroute_hash_table[][]) for networks that are a subset of the network defined by the dest/netmask pair.
0044995 {
0044996 for (j= 0; j<IROUTE_HASH_ASS_NR; j++)
0044997 {
0044998 if (((iroute_hash[j].irh_addr ^ dest) &
0044999 netmask) == 0)
0045000 {
0045001 iroute_hash[j].irh_addr= 0;
0045002 iroute_hash[j].irh_route= NULL;
0045003 }
0045004 }
0045005 }
0045006 }
0045007
0045008
0045009
0045010 /*
0045011 * Debugging, management
0045012 */
0045013
0045014 /*
0045015 * $PchId: ipr.c,v 1.9 1996/07/31 17:26:33 philip Exp $
0045016 */
Most of the functions within ipr.c locate routes within these tables or manipulate these tables.
oroute_table[] / oroute_hash_table[]
"Ouput routing" is routing that is done for outgoing packets. As an example, suppose that there are two ethernet ports with corresponding ip devices of "/dev/ip0" (192.30.1.1/255.255.255.0) and "/dev/ip1" (192.30.2.1/255.255.255.0). If the following add_route command is issued:
add_route -g 192.30.2.254 -d 192.50.1.0 -m 2 -n 255.255.255.0 -I /dev/ip0
then outgoing ip packets (that did not, however, arrive on another interface) are sent out the ethernet port that corresponds to /dev/ip0 to the gateway with ip address of 192.30.2.254.
Output routes are stored in two different arrays, oroute_table[] and oroute_hash_table[][]. oroute_table[] is the main table and oroute_hash_table[][] is the cache, where routes can be quickly looked up. oroute_table[] has 32 elements and each element is of type oroute_t:
int ort_port: The port number (e.g., ip0 is 0).
ipaddr_t ort_dest: The network address of the routing entry (e.g., 192.50.1.0).
ipaddr_t ort_subnetmask: The subnet mask of the routing entry (e.g., 255.255.255.0).
int ort_dist: The distance to the route. Routes with low distances are chosen over routes with high distances.
i32_t ort_pref: The preference of the route. Routes with high preferences are chosen over routes with low preferences. The distance of a route is of higher importance. In other words, the relative preference of two routes is only significant if and only if these two routes are tied for the lowest distance.
ipaddr_t ort_gateway: The ip address of the gateway. Packets that are not destined to systems on the local network are sent to the gateway.
time_t ort_exp_tim: The expiration time for the entry. Note that when using add_route, this value will always 0. The entries, therefore, do not expire.
time_t ort_timestamp: The time at which the entry is added to oroute_table[].
int ort_flags:
#define ORTF_EMPTY 0
#define ORTF_INUSE 1
#define ORTF_STATIC 2
Only OROUTE_STATIC_NR (#define'd as 16) static routes are allowed in the output routing table. Static and dynamic routes cannot replace static routes, even if 2 routes are to the same network.
struct oroute *ort_nextnw:
struct oroute *ort_nextgw:
struct oroute *ort_nextdist:
ort_nextnw, ort_nextgw, and ort_nextdist can best be described using a figure. The figure below represents the main output routing table, oroute_table[]:
The ort_nextnw field (red) is the linked list of routes to specific networks/subnet mask pairs. A, B, C, D, and E all are routes to different network/subnet mask pairs. For example, A could be the route to 192.30.1.0/255.255.255.0 and B could be the route to 192.30.2.0/255.255.255.0.
The ort_nextgw field (blue) links the linked lists of routes with the same network/subnet mask pairs but different gateways. D, F, and G are all routes to the same network/subnet mask pairs but all have different gateways. ort_nextdist connec
The ort_nextdist field (green) links the linked lists of routes with the same network/subnet mask pairs and the same gateway but with possibly different distances/preferences. F, H, I, and J are all routes to the same network/subnet mask pairs and the same gateway but have possibly different distances/preferences.
The oroute_hash_table[][] is a 2-dimensional array of dimensions 32x4 whose entries are of type oroute_hash_t:
ipaddr_t irh_addr: The ip address (not the network address) of a system.
iroute_t *irh_route: The best route for the ip address above.
If an entry for a system does not exist in oroute_hash_table[][], the best route for the system is determined from the entries in oroute_table[]. The ip address of this system and the best route to the system (which together form an oroute_hash_t struct) is then placed in oroute_hash_table[][]. The first dimension corresponds to the hash of the ip address, as determined by the #define hash_iroute. The second dimension will be 0. The entry with the same hash that was formerly in the 0th slot will be pushed to the 1st slot, the entry that was formerly in the 1st slot will be pushed to the 2nd slot, and then entry that was formerly in the 2nd slot will be pushed to the 3rd slot. The entry that was formerly in the 3rd slot will be pushed out of oroute_hash_table[][].
The best route for the ip address can later be quickly retrieved from oroute_hash_table[][] (if it hasn't since been pushed out).
iroute_table[] / iroute_hash_table[]
"Input routing" is routing that is done between interfaces. As an example, suppose that there are two ethernet ports and the corresponding ip port of the first ethernet (which corresponds to the device "/dev/ip0") has an ip address/subnet mask of 192.30.1.1/255.255.255.0 and the ip port of the second ethernet (which corresponds to the device "/dev/ip1") has an ip address/subnet mask of 192.30.2.1/255.255.255.0. If the following add_route command is issued:
add_route -i -g 0.0.0.0 -d 192.30.1.0 -m 1 -n 255.255.255.0 -I /dev/ip0
then ip packets arriving on the second ethernet destined for the 192.30.1.0/255.255.255.0 network will be routed to the first ethernet port.
Input routes are stored in two different arrays, iroute_table[] and iroute_hash_table[][]. iroute_table[] is the main table and iroute_hash_table[][] is the cache, where routes can be quickly looked up. iroute_table[] has 512 elements and each element is of type iroute_t:
ipaddr_t irt_dest: The network address of the routing entry (e.g., 192.30.1.0).
ipaddr_t irt_gateway: The gateway to which packets that are not destined to machines on the local network are sent.
ipaddr_t irt_subnetmask: The subnet mask of the routing entry (e.g., 255.255.255.0).
int irt_dist: The distance. Routes with low distances are chosen over routes with high distances.
int irt_port: The port number (e.g., ip0 is 0).
int irt_flags: irt_flags can be one of the following:
#define IRTF_EMPTY 0
#define IRTF_INUSE 1
#define IRTF_STATIC 2
Static input routes behave differently than dynamic input routes. If a static route is added to the input routing table, the route will not not replace any pre-existing route (static or dynamic) even if the values of the route (e.g., destination network) are the same. A dynamic input route, on the other hand, will replace another dynamic input route.
The iroute_hash_table[][] is a 2-dimensional array of dimensions 32x4 whose entries are of type iroute_hash_t:
ipaddr_t irh_addr: The ip address (not the network address) of a system.
iroute_t *irh_route: The best route for the ip address above.
If an entry for a system does not exist in iroute_hash_table[][], the best route for the system is determined from the entries in iroute_table[]. The ip address of this system and the best route to the system (which together form an iroute_hash_t struct) is then placed in iroute_hash_table[][]. The first dimension corresponds to the hash of the ip address, as determined by the #define hash_iroute. The second dimension will be 0. The entry with the same hash that was formerly in the 0th slot will be pushed to the 1st slot, the entry that was formerly in the 1st slot will be pushed to the 2nd slot, and then entry that was formerly in the 2nd slot will be pushed to the 3rd slot. The entry that was formerly in the 3rd slot will be pushed out of iroute_hash_table[][].
The best route for the ip address can then later be quickly retrieved from iroute_hash_table[][] (if it hasn't since been pushed out).
network daemons
Network daemons provide services in addition to the routing services provided by the network service. These daemons and the utilities used to configure them are described in the boot man page:
"Simpler configuration tools
The rarpd, irdpd and nonamed daemons are complex little programs that try to obtain information about their surroundings automatically to tell the machine what its place in the network is. It should come as no surprise that there are simpler utilities to configure a machine. On a memory starved machine it may even be wise to configure a machine statically to get rid of the daemons. The first daemon, rarpd, can be replaced by:
ifconfig -h host-IP-address
to set the IP address of the machine. Note that this is only necessary if there is no external RARP service. The second daemon irdpd can be replaced by setting a static route:
add_route -g router-IP-address"