Kernel: Add simple ARP routing layer

This replaces the previous placeholder routing layer with a real one!
It's still very primitive, doesn't deal with things like timeouts very
well, and will probably need several more iterations to support more
normal networking things.

I haven't confirmed that this works with anything other than the QEMU
user networking layer, but I suspect that's what nearly everybody is
using at this point, so that's the important target to keep working.

6 files changed, 146 insertions, 47 deletions

diff --git a/Kernel/Net/IPv4Socket.cpp b/Kernel/Net/IPv4Socket.cpp
index cc1a0c7909..9ba3555358 100644
--- a/Kernel/Net/IPv4Socket.cpp
+++ b/Kernel/Net/IPv4Socket.cpp
@@ -169,12 +169,12 @@ ssize_t IPv4Socket::sendto(FileDescription&, const void* data, size_t data_lengt
         m_peer_port = ntohs(ia.sin_port);
     }
 
-    auto adapter = adapter_for_route_to(m_peer_address);
-    if (!adapter)
+    auto routing_decision = route_to(m_peer_address, m_local_address);
+    if (!routing_decision.adapter || routing_decision.next_hop.is_zero())
         return -EHOSTUNREACH;
 
     if (m_local_address.to_u32() == 0)
-        m_local_address = adapter->ipv4_address();
+        m_local_address = routing_decision.adapter->ipv4_address();
 
     int rc = allocate_local_port_if_needed();
     if (rc < 0)
@@ -183,7 +183,7 @@ ssize_t IPv4Socket::sendto(FileDescription&, const void* data, size_t data_lengt
     kprintf("sendto: destination=%s:%u\n", m_peer_address.to_string().characters(), m_peer_port);
 
     if (type() == SOCK_RAW) {
-        adapter->send_ipv4(MACAddress(), m_peer_address, (IPv4Protocol)protocol(), (const u8*)data, data_length);
+        routing_decision.adapter->send_ipv4(routing_decision.next_hop, m_peer_address, (IPv4Protocol)protocol(), (const u8*)data, data_length);
         return data_length;
     }
 
diff --git a/Kernel/Net/NetworkTask.cpp b/Kernel/Net/NetworkTask.cpp
index 87fe7ce768..f45bf0d2a9 100644
--- a/Kernel/Net/NetworkTask.cpp
+++ b/Kernel/Net/NetworkTask.cpp
@@ -16,6 +16,7 @@
 //#define NETWORK_TASK_DEBUG
 //#define ETHERNET_DEBUG
 //#define ETHERNET_VERY_DEBUG
+//#define ARP_DEBUG
 //#define IPV4_DEBUG
 //#define ICMP_DEBUG
 //#define UDP_DEBUG
@@ -27,14 +28,6 @@ static void handle_icmp(const EthernetFrameHeader&, const IPv4Packet&);
 static void handle_udp(const IPv4Packet&);
 static void handle_tcp(const IPv4Packet&);
 
-Lockable<HashMap<IPv4Address, MACAddress>>& arp_table()
-{
-    static Lockable<HashMap<IPv4Address, MACAddress>>* the;
-    if (!the)
-        the = new Lockable<HashMap<IPv4Address, MACAddress>>;
-    return *the;
-}
-
 void NetworkTask_main()
 {
     u8 octet = 15;
diff --git a/Kernel/Net/Routing.cpp b/Kernel/Net/Routing.cpp
index c9bf54f67e..a74c3e329a 100644
--- a/Kernel/Net/Routing.cpp
+++ b/Kernel/Net/Routing.cpp
@@ -1,10 +1,124 @@
-#include <Kernel/Net/LoopbackAdapter.h>
 #include <Kernel/Net/Routing.h>
+#include <Kernel/Thread.h>
 
-WeakPtr<NetworkAdapter> adapter_for_route_to(const IPv4Address& ipv4_address)
+//#define ROUTING_DEBUG
+
+Lockable<HashMap<IPv4Address, MACAddress>>& arp_table()
 {
-    // FIXME: Have an actual routing table.
-    if (ipv4_address == IPv4Address(127, 0, 0, 1))
-        return LoopbackAdapter::the().make_weak_ptr();
-    return NetworkAdapter::from_ipv4_address(IPv4Address(192, 168, 5, 2));
+    static Lockable<HashMap<IPv4Address, MACAddress>>* the;
+    if (!the)
+        the = new Lockable<HashMap<IPv4Address, MACAddress>>;
+    return *the;
+}
+
+RoutingDecision route_to(const IPv4Address& target, const IPv4Address& source)
+{
+    auto target_addr = target.to_u32();
+    auto source_addr = source.to_u32();
+
+    WeakPtr<NetworkAdapter> local_adapter = nullptr;
+    WeakPtr<NetworkAdapter> gateway_adapter = nullptr;
+
+    NetworkAdapter::for_each([source_addr, &target_addr, &local_adapter, &gateway_adapter](auto& adapter) {
+        auto adapter_addr = adapter.ipv4_address().to_u32();
+        auto adapter_mask = adapter.ipv4_netmask().to_u32();
+
+        if (source_addr != 0 && source_addr != adapter_addr)
+            return;
+
+        if ((target_addr & adapter_mask) == (adapter_addr & adapter_mask))
+            local_adapter = adapter.make_weak_ptr();
+
+        if (adapter.ipv4_gateway().to_u32() != 0)
+            gateway_adapter = adapter.make_weak_ptr();
+    });
+
+    if (!local_adapter && !gateway_adapter) {
+#ifdef ROUTING_DEBUG
+        kprintf("Routing: Couldn't find a suitable adapter for route to %s\n",
+            target.to_string().characters());
+#endif
+        return { nullptr, {} };
+    }
+
+    WeakPtr<NetworkAdapter> adapter = nullptr;
+    IPv4Address next_hop_ip;
+
+    if (local_adapter) {
+#ifdef ROUTING_DEBUG
+        kprintf("Routing: Got adapter for route (direct): %s (%s/%s) for %s\n",
+            local_adapter->name().characters(),
+            local_adapter->ipv4_address().to_string().characters(),
+            local_adapter->ipv4_netmask().to_string().characters(),
+            target.to_string().characters());
+#endif
+        adapter = local_adapter;
+        next_hop_ip = target;
+    } else if (gateway_adapter) {
+#ifdef ROUTING_DEBUG
+        kprintf("Routing: Got adapter for route (using gateway %s): %s (%s/%s) for %s\n",
+            gateway_adapter->ipv4_gateway().to_string().characters(),
+            gateway_adapter->name().characters(),
+            gateway_adapter->ipv4_address().to_string().characters(),
+            gateway_adapter->ipv4_netmask().to_string().characters(),
+            target.to_string().characters());
+#endif
+        adapter = gateway_adapter;
+        next_hop_ip = gateway_adapter->ipv4_gateway();
+    } else {
+        return { nullptr, {} };
+    }
+
+    {
+        LOCKER(arp_table().lock());
+        auto addr = arp_table().resource().get(next_hop_ip);
+        if (addr.has_value()) {
+#ifdef ROUTING_DEBUG
+            kprintf("Routing: Using cached ARP entry for %s (%s)\n",
+                next_hop_ip.to_string().characters(),
+                addr.value().to_string().characters());
+#endif
+            return { adapter, addr.value() };
+        }
+    }
+
+#ifdef ROUTING_DEBUG
+    kprintf("Routing: Sending ARP request via adapter %s for IPv4 address %s\n",
+        adapter->name().characters(),
+        next_hop_ip.to_string().characters());
+#endif
+
+    ARPPacket request;
+    request.set_operation(ARPOperation::Request);
+    request.set_target_hardware_address({ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff });
+    request.set_target_protocol_address(next_hop_ip);
+    request.set_sender_hardware_address(adapter->mac_address());
+    request.set_sender_protocol_address(adapter->ipv4_address());
+    adapter->send({ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff }, request);
+
+    (void)current->block_until("Routing (ARP)", [next_hop_ip] {
+        return arp_table().resource().get(next_hop_ip).has_value();
+    });
+
+    {
+        LOCKER(arp_table().lock());
+        auto addr = arp_table().resource().get(next_hop_ip);
+        if (addr.has_value()) {
+#ifdef ROUTING_DEBUG
+            kprintf("Routing: Got ARP response using adapter %s for %s (%s)\n",
+                adapter->name().characters(),
+                next_hop_ip.to_string().characters(),
+                addr.value().to_string().characters());
+#endif
+            return { adapter, addr.value() };
+        }
+    }
+
+#ifdef ROUTING_DEBUG
+    kprintf("Routing: Couldn't find route using adapter %s for %s\n",
+        adapter->name().characters(),
+        target.to_string().characters());
+#endif
+
+    return { nullptr, {} };
 }
diff --git a/Kernel/Net/Routing.h b/Kernel/Net/Routing.h
index 0feed2cf64..82ae87895b 100644
--- a/Kernel/Net/Routing.h
+++ b/Kernel/Net/Routing.h
@@ -2,4 +2,12 @@
 
 #include <Kernel/Net/NetworkAdapter.h>
 
-WeakPtr<NetworkAdapter> adapter_for_route_to(const IPv4Address&);
+struct RoutingDecision
+{
+    WeakPtr<NetworkAdapter> adapter;
+    const MACAddress& next_hop;
+};
+
+RoutingDecision route_to(const IPv4Address& target, const IPv4Address& source);
+
+Lockable<HashMap<IPv4Address, MACAddress>>& arp_table();
diff --git a/Kernel/Net/TCPSocket.cpp b/Kernel/Net/TCPSocket.cpp
index f7fe4af29c..e2d8c0f731 100644
--- a/Kernel/Net/TCPSocket.cpp
+++ b/Kernel/Net/TCPSocket.cpp
@@ -125,16 +125,8 @@ int TCPSocket::protocol_send(const void* data, int data_length)
 
 void TCPSocket::send_tcp_packet(u16 flags, const void* payload, int payload_size)
 {
-    if (!m_adapter) {
-        if (has_specific_local_address()) {
-            m_adapter = NetworkAdapter::from_ipv4_address(local_address());
-        } else {
-            m_adapter = adapter_for_route_to(peer_address());
-            if (m_adapter)
-                set_local_address(m_adapter->ipv4_address());
-        }
-    }
-    ASSERT(!!m_adapter);
+    auto routing_decision = route_to(peer_address(), local_address());
+    ASSERT(!!routing_decision.adapter);
 
     auto buffer = ByteBuffer::create_zeroed(sizeof(TCPPacket) + payload_size);
     auto& tcp_packet = *(TCPPacket*)(buffer.pointer());
@@ -170,7 +162,7 @@ void TCPSocket::send_tcp_packet(u16 flags, const void* payload, int payload_size
         tcp_packet.sequence_number(),
         tcp_packet.ack_number());
 #endif
-    m_adapter->send_ipv4(MACAddress(), peer_address(), IPv4Protocol::TCP, buffer.data(), buffer.size());
+    routing_decision.adapter->send_ipv4(routing_decision.next_hop, peer_address(), IPv4Protocol::TCP, buffer.data(), buffer.size());
 
     m_packets_out++;
     m_bytes_out += buffer.size();
@@ -249,19 +241,11 @@ KResult TCPSocket::protocol_listen()
 
 KResult TCPSocket::protocol_connect(FileDescription& description, ShouldBlock should_block)
 {
-    if (!m_adapter) {
-        if (has_specific_local_address()) {
-            m_adapter = NetworkAdapter::from_ipv4_address(local_address());
-            if (!m_adapter)
-                return KResult(-EADDRNOTAVAIL);
-        } else {
-            m_adapter = adapter_for_route_to(peer_address());
-            if (!m_adapter)
-                return KResult(-EHOSTUNREACH);
-
-            set_local_address(m_adapter->ipv4_address());
-        }
-    }
+    auto routing_decision = route_to(peer_address(), local_address());
+    if (!routing_decision.adapter || routing_decision.next_hop.is_zero())
+        return KResult(-EHOSTUNREACH);
+    if (!has_specific_local_address())
+        set_local_address(routing_decision.adapter->ipv4_address());
 
     allocate_local_port_if_needed();
 
diff --git a/Kernel/Net/UDPSocket.cpp b/Kernel/Net/UDPSocket.cpp
index e0fd77d040..bbadbb505e 100644
--- a/Kernel/Net/UDPSocket.cpp
+++ b/Kernel/Net/UDPSocket.cpp
@@ -63,8 +63,8 @@ int UDPSocket::protocol_receive(const KBuffer& packet_buffer, void* buffer, size
 
 int UDPSocket::protocol_send(const void* data, int data_length)
 {
-    auto adapter = adapter_for_route_to(peer_address());
-    if (!adapter)
+    auto routing_decision = route_to(peer_address(), local_address());
+    if (!routing_decision.adapter)
         return -EHOSTUNREACH;
     auto buffer = ByteBuffer::create_zeroed(sizeof(UDPPacket) + data_length);
     auto& udp_packet = *(UDPPacket*)(buffer.pointer());
@@ -73,11 +73,11 @@ int UDPSocket::protocol_send(const void* data, int data_length)
     udp_packet.set_length(sizeof(UDPPacket) + data_length);
     memcpy(udp_packet.payload(), data, data_length);
     kprintf("sending as udp packet from %s:%u to %s:%u!\n",
-        adapter->ipv4_address().to_string().characters(),
+        routing_decision.adapter->ipv4_address().to_string().characters(),
         local_port(),
         peer_address().to_string().characters(),
         peer_port());
-    adapter->send_ipv4(MACAddress(), peer_address(), IPv4Protocol::UDP, buffer.data(), buffer.size());
+    routing_decision.adapter->send_ipv4(routing_decision.next_hop, peer_address(), IPv4Protocol::UDP, buffer.data(), buffer.size());
     return data_length;
 }