Title: 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 220.127.116.11/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 18.104.22.168/255.255.255.0. If the following add_route command is issued:
add_route -i -g 0.0.0.0 -d 22.214.171.124 -m 1 -n 255.255.255.0 -I /dev/ip0
then ip packets arriving on the second ethernet destined for the 126.96.36.199/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: The network address of the routing entry (e.g., 188.8.131.52).
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: 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).