ipr.c contains the functions that affect the routing of packets. The output routing table affects the routing of packets that are being sent by a process on the system and the input routing table affects the routing of packets that are received on one interface but are not destined for the ip port associated with that interface.

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:

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).



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).


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"

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.

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).

oroute_table[], the output routing table, has OROUTE_NR (32) entries.

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.

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).

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.

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).

IROUTE_NR is #define'd as 512 for a system running in protected mode.

#define IROUTE_NR (sizeof(int) == 2 ? 64 : 512)

As #define'd above on lines 44045 and 44046:

#define IROUTE_HASH_ASS_NR 4

#define IROUTE_HASH_NR 32

ipr_init()

ipr_init() simply marks all the entries in the input routing table and the output routing table as unused.

OROUTE_NR, the number of entries in the output routing table, is #define'd as 32.

IROUTE_NR, the number of entries in the input routing table, is #define'd as 512 if the processor is operating in protected mode.

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.

Note that there is a tmp_hash as well as a hash_tmp (see line 44100). This is somewhat confusing.

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.

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.

iroute_hash is a pointer to the hash^th 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[]).

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[]).

If an entry is not "in use", it is invalid.

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.

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.

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.

If the network to which the destination address belongs is not in the input routing table, return NULL.

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.

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.

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.

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).

The ip address of the destination's gateway is returned in a reference of nexthop, oroute_frag()'s last parameter.

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.

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.

Find the ip port whose index within ip_port_table[] is port_nr, ipr_add_oroute()'s first parameter.

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

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.

The 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).

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.

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()).

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).

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[].

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).

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

An empty or expired entry was found in oroute_table[].

No empty or expired entries in oroute_table[]. Overwrite the oldest entry in oroute_table[].

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.

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).

Skip the routes whose ip port is not the same as port_nr, ipr_add_oroute()'s first parameter.

The linked list beginning with the B route is removed from the network (ort_nextnw) linked list.

The linked list beginning with the H route is removed from the gateway (ort_nextgw) linked list.

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.

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.

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).

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.

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).

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.

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()).

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.

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().

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.

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.

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.

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.

Static routes are fixed. They cannot be redirected.

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.

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.

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.

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.

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.

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.

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).

If the entry in the main output routing table has expired, remove the entry from the table.

Each output route is associated with an ip port, which is oroute_t's ort_port field.

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.

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.

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.

oroute_hash is a pointer to the hash^th 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[]).

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.

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).

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.

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.

The route in the main output routing table must have a port number of port_nr, oroute_find_ent()'s first parameter.

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).

If the network to which the destination address belongs is not in the input routing table, return NULL.

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.

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).

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.

At this point, the output routing table appears as follows:

At this point, the output routing table appears as follows:

At this point, the output routing table appears as follows:

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.

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.

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.

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.

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.

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.

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.

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).

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.

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.

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.

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).

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.

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.

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.

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.

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).

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.

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.

Add a dynamic input route. If a dynamic input route already exists with the same values, overwrite this route.

If there are no routes with identical values in the input routing table, use an unused entry.

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.

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().

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).

If static_route is 1, only remove static routes. If static_route is 0, only remove dynamic routes.

The route was not found.

Also uncache the entry (see iroute_uncache_nw() below).

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.

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.