Excercise 2: RIB (C)
Write down a small library in C language to store an IP routing
table, for both IPv4 and IPv6.
The library should allow performing longest-prefix matching operations.
Start by defining the API, then the data structures and, finally, the implementation.
For longest-prefix operations, you do not have to provide a true implementation but only pseudocode.
Report the references employed, if any.
Solution to the RIB excercise
For this exercise, the RIB table entries has been implemented as a linked list.
This is due to simplicity, as it is not an optimal solution.
An example of a more sophisticated solution,
especially for IPv6, is Fast IP Routing with LC-Tries
(source code available here), which implements the RIB as a level-compressed trie.
This implementation is considered a "fake" RIB in the sense
that added/delete/modified table entries will modify the linked list, but not the kernel RIB.
The test program rib is used to test the RIB library.
To keep the state between executions of rib, the RIB will be saved to/loaded from a file.
Even if the RIB is "fake", the initially retrieved values (Destination, Gateway, Iface, etc.) are "real", obtained from the kernel RIB.
The API
The API - overview
To get an idea how to design the API, use these commands and their output as a base:
ip -4 route
default via 10.0.2.2 dev eth0 proto static metric 100
10.0.2.0/24 dev eth0 proto kernel scope link src 10.0.2.15
10.0.2.2 dev eth0 proto dhcp scope link src 10.0.2.15 metric 1024
169.254.0.0/16 dev eth0 scope link metric 1000
ip -6 route
fe80::/64 dev eth0 proto kernel metric 256 pref medium
For this exercise, skip fields which are less relevant to this task.
That reduces the output to:
IPv4:
default via 10.0.2.2 dev eth0
10.0.2.0/24 dev eth0
10.0.2.2 dev eth0
169.254.0.0/16 dev eth0
IPv6:
fe80::/64 dev eth0
If the keyword "via" is not present for an entry, a gateway is not set for that entry.
Internally, the fields will be stored like this:
Destination Prefix Gateway Iface
0.0.0.0 0 10.0.2.2 eth0
10.0.2.0 24 0.0.0.0 eth0
10.0.2.2 32 0.0.0.0 eth0
169.254.0.0 16 0.0.0.0 eth0
fe80:: 64 :: eth0The rib and rib6 programs
The command options for rib and rib6 have much in common with the ip route command,
as described in ip-route(8).
ip route { add | del | change | append | replace | monitor } ROUTE
./rib [show] [FILE]
./rib { add | del | mod } ROUTE [FILE]
./rib match IP [FILE]
If the rib program is run without arguments,
it looks by default for the file rib.txt to load the RIB, and then shows the loaded RIB.
If rib.txt does not exist, the kernel RIB is loaded and shown instead (the kernel RIB is never modified, though).
Running rib with show subcommand or without it is equivalent.
Use FILE to load a RIB from another file.
Any changes to the loaded RIB (add/del/mod) are saved by default to rib.txt , or to FILE.
The match subcommand is used to test any arbitrary IP to print a matching route in the RIB (if any).
If more than one route match the IP, longest-prefix matching is applied to get the correct route.
The rib program only treats IPv4 addresses.
The rib6 program is the equivalent for treats IPv6, and uses rib6.txt by default.
The API reflects the subcommands add, del, mod, match, show.
The API - details
The rib_data_t and rib_entry_t are data structures described in detail below:
rib_entry_t = {Destination Gateway Mask Flags Iface} (the RIB columns discussed above) rib_entry_list_t = {linked list of rib_entry_t entries }
int librib_load_list(const char *input_file, rib_entry_t **list, int ip_version); /*
Load a RIB from file or, if file not found, from the 'ip -4 r' or 'ip -6 r' command.
The lines are validated and stored into a linked list.
(always called by the 'rib' program)
Returns non-zero on failure (I/O error, unexpected error).
*/
int librib_save_list(const char *output_file, rib_entry_t *list, int ip_version); /*
Save a RIB to file (called by the 'rib add/del/mod' subcommands).
Returns non-zero on failure (I/O error, unexpected error).
*/
int librib_show_list(rib_entry_t *list, int ip_version); /*
Print a list of RIB entries (called by 'rib show').
Returns non-zero on failure (unexpected error).
*/
int librib_delete_list(rib_entry_t *list); /*
Delete all RIB entries.
Returns non-zero on failure (unexpected error).
*/
int librib_add_entry(rib_entry_t **list, rib_data_t *new_data); /*
Add a new entry to the RIB.
One or more rib_entry_t values may be set.
Passing 0 to Destination sets the default gateway.
Returns non-zero on failure (unexpected error).
*/
int librib_del_entry(rib_entry_t **list, rib_data_t *matching_data); /*
Delete an existing entry in the RIB that matches the provided struct.
One or more rib_entry_t values may be set.
Passing a NULL struct o 0 to Destination deletes the default gateway.
Only one entry is deleted, even if several RIB entries match the provided struct.
Returns non-zero on failure (no matching entry to delete, unexpected error).
*/
int librib_mod_entry(rib_entry_t **list, rib_data_t *matching_and_modified_data); /*
Modify an existing entry in the RIB that matches the provided struct.
One or more rib_entry_t values may be set.
Only one entry is modified, even if several RIB entries match the provided struct.
Returns non-zero on failure (no matching entry to modify, unexpected error).
*/
rib_entry_t rib_get_entry(rib_entry_t **list, rib_data_t *matching_data); /*
Get the first RIB entry which matches matching_entry.
Returns a pointer to a rib_entry_t struct.
This function is called by other functions with a "matching entry" as argument: rib_del_entry(), rib_mod_entry()
Returns NULL on failure (no match, unexpected error).
*/
Data structures
/* IPv4 and IPv6 addresses may share memory space, as they are not used simultaneously */
typedef union ip_addr_t
{
struct in_addr ipv4;
struct in6_addr ipv6;
} ip_addr_t;
/* RIB entry data */
typedef struct rib_data_t
{
ip_addr_t dst; /* Destination (IP address)*/
ip_addr_t gw; /* Gateway */
uint8_t prefix; /* Destination CIDR Prefix: 0-32 (IPv4), 0-128 (IPv6), used to calculate mask */
char iface[IF_NAMESIZE];
} rib_data_t;
/* RIB entry in linked list */
typedef struct rib_entry_t
{
rib_data_t data;
struct rib_entry_t* next;
} rib_entry_t;
The implementation
Prerequisites
This code has been compiled and tested on Linux (Ubuntu 16.04).
Only make and gcc should suffice to compile the source code.
No additional third-party software should be required.
Portability has not been considered for this task.
The code may not work on other Linux distributions,
and will probably not do so on other platforms (i.e. Free/Open/NetBSD, MacOSX, Win32, CygWin, MSYS2).
Compile and run
make clean all run
Refer to the Makefile for build details.
Conclusions
This RIB implementation is focused on simplicity, not on efficiency.
As mentioned before, an improved version would be to replace the linked-list data structre with a level-compressed trie, as
described in Fast IP Routing with LC-Tries.
References
https://en.wikipedia.org/wiki/Routing_table
https://en.wikipedia.org/wiki/Classless_Inter-Domain_Routing#CIDR_blocks
https://www.geeksforgeeks.org/computer-networks-longest-prefix-matching-in-routers/
http://olegkutkov.me/2019/03/24/getting-linux-routing-table-using-netlink/
https://oroboro.com/linux-routing-tables-in-c/
https://www.geeksforgeeks.org/program-for-ip-forwarding-table-lookup/
http://www.drdobbs.com/cpp/fast-ip-routing-with-lc-tries/184410638
https://www.nada.kth.se/~snilsson/software/router/