Kernel: Add a global routing table

Previously the system had no concept of assigning different routes for
different destination addresses as the default gateway IP address was
directly assigned to a network adapter. This default gateway was
statically assigned and any update  would remove the previously existing
route.

This patch is a beginning step towards implementing #180. It implements
a simple global routing table that is referenced during the routing
process. With this implementation it is now possible for a user or
service (i.e. DHCP) to dynamically add routes to the table.

The routing table will select the most specific route when possible. It
will select any direct match between the destination and routing entry
addresses. If the destination address overlaps between multiple entries,
the Kernel will use the longest prefix match, or the longest number of
matching bits between the destination address and the routing address.
In the event that there is no entries found for a specific destination
address, this implementation supports entries for a default route to be
set for any specified interface.

This is a small first step towards enhancing the system's routing
capabilities. Future enhancements would include referencing a
configuration file at boot to load pre-defined static routes.

4 files changed, 104 insertions, 15 deletions

diff --git a/Kernel/API/POSIX/net/route.h b/Kernel/API/POSIX/net/route.h
index 0073e7e892..8c3c6b8bfa 100644
--- a/Kernel/API/POSIX/net/route.h
+++ b/Kernel/API/POSIX/net/route.h
@@ -14,6 +14,7 @@ extern "C" {
 #endif
 
 struct rtentry {
+    struct sockaddr rt_dst;     /* the target address */
     struct sockaddr rt_gateway; /* the gateway address */
     struct sockaddr rt_genmask; /* the target network mask */
     unsigned short int rt_flags;
diff --git a/Kernel/Net/IPv4Socket.cpp b/Kernel/Net/IPv4Socket.cpp
index 184b3cd0b8..264c7a34f5 100644
--- a/Kernel/Net/IPv4Socket.cpp
+++ b/Kernel/Net/IPv4Socket.cpp
@@ -624,16 +624,20 @@ ErrorOr<void> IPv4Socket::ioctl(OpenFileDescription&, unsigned request, Userspac
             return ENODEV;
 
         switch (request) {
-        case SIOCADDRT:
+        case SIOCADDRT: {
             if (!Process::current().is_superuser())
                 return EPERM;
             if (route.rt_gateway.sa_family != AF_INET)
                 return EAFNOSUPPORT;
             if ((route.rt_flags & (RTF_UP | RTF_GATEWAY)) != (RTF_UP | RTF_GATEWAY))
                 return EINVAL; // FIXME: Find the correct value to return
-            adapter->set_ipv4_gateway(IPv4Address(((sockaddr_in&)route.rt_gateway).sin_addr.s_addr));
-            return {};
 
+            auto destination = IPv4Address(((sockaddr_in&)route.rt_dst).sin_addr.s_addr);
+            auto gateway = IPv4Address(((sockaddr_in&)route.rt_gateway).sin_addr.s_addr);
+            auto genmask = IPv4Address(((sockaddr_in&)route.rt_genmask).sin_addr.s_addr);
+
+            return update_routing_table(destination, gateway, genmask, adapter, UpdateTable::Set);
+        }
         case SIOCDELRT:
             // FIXME: Support gateway deletion
             return {};
diff --git a/Kernel/Net/Routing.cpp b/Kernel/Net/Routing.cpp
index c8b197b994..feba06a32b 100644
--- a/Kernel/Net/Routing.cpp
+++ b/Kernel/Net/Routing.cpp
@@ -17,6 +17,7 @@
 namespace Kernel {
 
 static Singleton<SpinlockProtected<HashMap<IPv4Address, MACAddress>>> s_arp_table;
+static Singleton<SpinlockProtected<Route::RouteList>> s_routing_table;
 
 class ARPTableBlocker final : public Thread::Blocker {
 public:
@@ -129,6 +130,32 @@ void update_arp_table(IPv4Address const& ip_addr, MACAddress const& addr, Update
     }
 }
 
+SpinlockProtected<Route::RouteList>& routing_table()
+{
+    return *s_routing_table;
+}
+
+ErrorOr<void> update_routing_table(IPv4Address const& destination, IPv4Address const& gateway, IPv4Address const& netmask, RefPtr<NetworkAdapter> adapter, UpdateTable update)
+{
+    auto route_entry = adopt_ref_if_nonnull(new (nothrow) Route { destination, gateway, netmask, adapter.release_nonnull() });
+    if (!route_entry)
+        return ENOMEM;
+
+    TRY(routing_table().with([&](auto& table) -> ErrorOr<void> {
+        // TODO: Add support for deleting routing entries
+        if (update == UpdateTable::Set) {
+            for (auto const& route : table) {
+                if (route == *route_entry)
+                    return EEXIST;
+            }
+            table.append(*route_entry);
+        }
+        return {};
+    }));
+
+    return {};
+}
+
 bool RoutingDecision::is_zero() const
 {
     return adapter.is_null() || next_hop.is_zero();
@@ -162,9 +189,9 @@ RoutingDecision route_to(IPv4Address const& target, IPv4Address const& source, R
     auto source_addr = source.to_u32();
 
     RefPtr<NetworkAdapter> local_adapter = nullptr;
-    RefPtr<NetworkAdapter> gateway_adapter = nullptr;
+    RefPtr<Route> chosen_route = nullptr;
 
-    NetworkingManagement::the().for_each([source_addr, &target_addr, &local_adapter, &gateway_adapter, &matches, &through](NetworkAdapter& adapter) {
+    NetworkingManagement::the().for_each([source_addr, &target_addr, &local_adapter, &matches, &through](NetworkAdapter& adapter) {
         auto adapter_addr = adapter.ipv4_address().to_u32();
         auto adapter_mask = adapter.ipv4_netmask().to_u32();
 
@@ -181,15 +208,45 @@ RoutingDecision route_to(IPv4Address const& target, IPv4Address const& source, R
 
         if ((target_addr & adapter_mask) == (adapter_addr & adapter_mask) && matches(adapter))
             local_adapter = adapter;
+    });
 
-        if (adapter.ipv4_gateway().to_u32() != 0 && matches(adapter))
-            gateway_adapter = adapter;
+    u32 longest_prefix_match = 0;
+    routing_table().for_each([&target_addr, &matches, &longest_prefix_match, &chosen_route](auto& route) {
+        auto route_addr = route.destination.to_u32();
+        auto route_mask = route.netmask.to_u32();
+
+        if (route_addr == 0 && matches(*route.adapter)) {
+            dbgln_if(ROUTING_DEBUG, "Resorting to default route found for adapter: {}", route.adapter->name());
+            chosen_route = route;
+        }
+
+        // We have a direct match and we can exit the routing table earlier.
+        if (target_addr == route_addr) {
+            dbgln_if(ROUTING_DEBUG, "Target address has a direct match in the routing table");
+            chosen_route = route;
+            return;
+        }
+
+        if ((target_addr & route_mask) == (route_addr & route_mask) && (route_addr != 0)) {
+            auto prefix = (target_addr & (route_addr & route_mask));
+
+            if (chosen_route && prefix == longest_prefix_match) {
+                chosen_route = (route.netmask.to_u32() > chosen_route->netmask.to_u32()) ? route : chosen_route;
+                dbgln_if(ROUTING_DEBUG, "Found a matching prefix match. Using longer netmask: {}", chosen_route->netmask);
+            }
+
+            if (prefix > longest_prefix_match) {
+                dbgln_if(ROUTING_DEBUG, "Found a longer prefix match - route: {}, netmask: {}", route.destination.to_string(), route.netmask);
+                longest_prefix_match = prefix;
+                chosen_route = route;
+            }
+        }
     });
 
     if (local_adapter && target == local_adapter->ipv4_address())
         return { local_adapter, local_adapter->mac_address() };
 
-    if (!local_adapter && !gateway_adapter) {
+    if (!local_adapter && !chosen_route) {
         dbgln_if(ROUTING_DEBUG, "Routing: Couldn't find a suitable adapter for route to {}", target);
         return { nullptr, {} };
     }
@@ -206,15 +263,15 @@ RoutingDecision route_to(IPv4Address const& target, IPv4Address const& source, R
 
         adapter = local_adapter;
         next_hop_ip = target;
-    } else if (gateway_adapter && allow_using_gateway == AllowUsingGateway::Yes) {
+    } else if (chosen_route && allow_using_gateway == AllowUsingGateway::Yes) {
         dbgln_if(ROUTING_DEBUG, "Routing: Got adapter for route (using gateway {}): {} ({}/{}) for {}",
-            gateway_adapter->ipv4_gateway(),
-            gateway_adapter->name(),
-            gateway_adapter->ipv4_address(),
-            gateway_adapter->ipv4_netmask(),
+            chosen_route->gateway,
+            chosen_route->adapter->name(),
+            chosen_route->adapter->ipv4_address(),
+            chosen_route->adapter->ipv4_netmask(),
             target);
-        adapter = gateway_adapter;
-        next_hop_ip = gateway_adapter->ipv4_gateway();
+        adapter = chosen_route->adapter;
+        next_hop_ip = chosen_route->gateway;
     } else {
         return { nullptr, {} };
     }
diff --git a/Kernel/Net/Routing.h b/Kernel/Net/Routing.h
index b08eaba1ef..721c64d6cb 100644
--- a/Kernel/Net/Routing.h
+++ b/Kernel/Net/Routing.h
@@ -6,12 +6,37 @@
 
 #pragma once
 
+#include <AK/IPv4Address.h>
+#include <AK/NonnullRefPtr.h>
 #include <Kernel/Locking/MutexProtected.h>
 #include <Kernel/Net/NetworkAdapter.h>
 #include <Kernel/Thread.h>
 
 namespace Kernel {
 
+struct Route : public RefCounted<Route> {
+    Route(IPv4Address const& destination, IPv4Address const& gateway, IPv4Address const& netmask, NonnullRefPtr<NetworkAdapter> adapter)
+        : destination(destination)
+        , gateway(gateway)
+        , netmask(netmask)
+        , adapter(adapter)
+    {
+    }
+
+    bool operator==(Route const& other)
+    {
+        return destination == other.destination && gateway == other.gateway && netmask == other.netmask && adapter.ptr() == other.adapter.ptr();
+    }
+
+    const IPv4Address destination;
+    const IPv4Address gateway;
+    const IPv4Address netmask;
+    NonnullRefPtr<NetworkAdapter> adapter;
+
+    IntrusiveListNode<Route, RefPtr<Route>> route_list_node {};
+    using RouteList = IntrusiveList<&Route::route_list_node>;
+};
+
 struct RoutingDecision {
     RefPtr<NetworkAdapter> adapter;
     MACAddress next_hop;
@@ -25,6 +50,7 @@ enum class UpdateTable {
 };
 
 void update_arp_table(IPv4Address const&, MACAddress const&, UpdateTable update);
+ErrorOr<void> update_routing_table(IPv4Address const& destination, IPv4Address const& gateway, IPv4Address const& netmask, RefPtr<NetworkAdapter> const adapter, UpdateTable update);
 
 enum class AllowUsingGateway {
     Yes,
@@ -34,5 +60,6 @@ enum class AllowUsingGateway {
 RoutingDecision route_to(IPv4Address const& target, IPv4Address const& source, RefPtr<NetworkAdapter> const through = nullptr, AllowUsingGateway = AllowUsingGateway::Yes);
 
 SpinlockProtected<HashMap<IPv4Address, MACAddress>>& arp_table();
+SpinlockProtected<Route::RouteList>& routing_table();
 
 }