jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2021, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <AK/HashMap.h>
8#include <AK/Singleton.h>
9#include <Kernel/Debug.h>
10#include <Kernel/Locking/MutexProtected.h>
11#include <Kernel/Net/LoopbackAdapter.h>
12#include <Kernel/Net/NetworkTask.h>
13#include <Kernel/Net/NetworkingManagement.h>
14#include <Kernel/Net/Routing.h>
15#include <Kernel/Thread.h>
16
17namespace Kernel {
18
19static Singleton<SpinlockProtected<HashMap<IPv4Address, MACAddress>, LockRank::None>> s_arp_table;
20static Singleton<SpinlockProtected<Route::RouteList, LockRank::None>> s_routing_table;
21
22class ARPTableBlocker final : public Thread::Blocker {
23public:
24 ARPTableBlocker(IPv4Address ip_addr, Optional<MACAddress>& addr);
25
26 virtual StringView state_string() const override { return "Routing (ARP)"sv; }
27 virtual Type blocker_type() const override { return Type::Routing; }
28 virtual bool setup_blocker() override;
29
30 virtual void will_unblock_immediately_without_blocking(UnblockImmediatelyReason) override;
31
32 bool unblock_if_matching_ip_address(bool from_add_blocker, IPv4Address const& ip_address, MACAddress const& mac_address)
33 {
34 if (m_ip_address != ip_address)
35 return false;
36
37 {
38 SpinlockLocker lock(m_lock);
39 if (m_did_unblock)
40 return false;
41 m_did_unblock = true;
42 m_mac_address = mac_address;
43 }
44
45 if (!from_add_blocker)
46 unblock_from_blocker();
47 return true;
48 }
49
50 IPv4Address const& ip_address() const { return m_ip_address; }
51
52private:
53 IPv4Address const m_ip_address;
54 Optional<MACAddress>& m_mac_address;
55 bool m_did_unblock { false };
56};
57
58class ARPTableBlockerSet final : public Thread::BlockerSet {
59public:
60 void unblock_blockers_waiting_for_ipv4_address(IPv4Address const& ipv4_address, MACAddress const& mac_address)
61 {
62 BlockerSet::unblock_all_blockers_whose_conditions_are_met([&](auto& b, void*, bool&) {
63 VERIFY(b.blocker_type() == Thread::Blocker::Type::Routing);
64 auto& blocker = static_cast<ARPTableBlocker&>(b);
65 return blocker.unblock_if_matching_ip_address(false, ipv4_address, mac_address);
66 });
67 }
68
69protected:
70 virtual bool should_add_blocker(Thread::Blocker& b, void*) override
71 {
72 VERIFY(b.blocker_type() == Thread::Blocker::Type::Routing);
73 auto& blocker = static_cast<ARPTableBlocker&>(b);
74 auto maybe_mac_address = arp_table().with([&](auto const& table) -> auto{
75 return table.get(blocker.ip_address());
76 });
77 if (!maybe_mac_address.has_value())
78 return true;
79 return !blocker.unblock_if_matching_ip_address(true, blocker.ip_address(), maybe_mac_address.value());
80 }
81};
82
83static Singleton<ARPTableBlockerSet> s_arp_table_blocker_set;
84
85ARPTableBlocker::ARPTableBlocker(IPv4Address ip_addr, Optional<MACAddress>& addr)
86 : m_ip_address(ip_addr)
87 , m_mac_address(addr)
88{
89}
90
91bool ARPTableBlocker::setup_blocker()
92{
93 return add_to_blocker_set(*s_arp_table_blocker_set);
94}
95
96void ARPTableBlocker::will_unblock_immediately_without_blocking(UnblockImmediatelyReason)
97{
98 auto addr = arp_table().with([&](auto const& table) -> auto{
99 return table.get(ip_address());
100 });
101
102 SpinlockLocker lock(m_lock);
103 if (!m_did_unblock) {
104 m_did_unblock = true;
105 m_mac_address = move(addr);
106 }
107}
108
109SpinlockProtected<HashMap<IPv4Address, MACAddress>, LockRank::None>& arp_table()
110{
111 return *s_arp_table;
112}
113
114void update_arp_table(IPv4Address const& ip_addr, MACAddress const& addr, UpdateTable update)
115{
116 arp_table().with([&](auto& table) {
117 if (update == UpdateTable::Set)
118 table.set(ip_addr, addr);
119 if (update == UpdateTable::Delete)
120 table.remove(ip_addr);
121 });
122 s_arp_table_blocker_set->unblock_blockers_waiting_for_ipv4_address(ip_addr, addr);
123
124 if constexpr (ARP_DEBUG) {
125 arp_table().with([&](auto const& table) {
126 dmesgln("ARP table ({} entries):", table.size());
127 for (auto& it : table)
128 dmesgln("{} :: {}", it.value.to_string(), it.key.to_string());
129 });
130 }
131}
132
133SpinlockProtected<Route::RouteList, LockRank::None>& routing_table()
134{
135 return *s_routing_table;
136}
137
138ErrorOr<void> update_routing_table(IPv4Address const& destination, IPv4Address const& gateway, IPv4Address const& netmask, u16 flags, LockRefPtr<NetworkAdapter> adapter, UpdateTable update)
139{
140 dbgln_if(ROUTING_DEBUG, "update_routing_table {} {} {} {} {} {}", destination, gateway, netmask, flags, adapter, update == UpdateTable::Set ? "Set" : "Delete");
141
142 auto route_entry = adopt_lock_ref_if_nonnull(new (nothrow) Route { destination, gateway, netmask, flags, adapter.release_nonnull() });
143 if (!route_entry)
144 return ENOMEM;
145
146 TRY(routing_table().with([&](auto& table) -> ErrorOr<void> {
147 if (update == UpdateTable::Set) {
148 for (auto const& route : table) {
149 if (route == *route_entry)
150 return EEXIST;
151 }
152 table.append(*route_entry);
153 }
154 if (update == UpdateTable::Delete) {
155 for (auto& route : table) {
156 dbgln_if(ROUTING_DEBUG, "candidate: {} {} {} {} {}", route.destination, route.gateway, route.netmask, route.flags, route.adapter);
157 if (route.matches(*route_entry)) {
158 // FIXME: Remove all entries, not only the first one.
159 table.remove(route);
160 return {};
161 }
162 }
163 return ESRCH;
164 }
165 return {};
166 }));
167
168 return {};
169}
170
171bool RoutingDecision::is_zero() const
172{
173 return adapter.is_null() || next_hop.is_zero();
174}
175
176static MACAddress multicast_ethernet_address(IPv4Address const& address)
177{
178 return MACAddress { 0x01, 0x00, 0x5e, (u8)(address[1] & 0x7f), address[2], address[3] };
179}
180
181RoutingDecision route_to(IPv4Address const& target, IPv4Address const& source, LockRefPtr<NetworkAdapter> const through, AllowUsingGateway allow_using_gateway)
182{
183 auto matches = [&](auto& adapter) {
184 if (!through)
185 return true;
186
187 return through == adapter;
188 };
189 auto if_matches = [&](auto& adapter, auto const& mac) -> RoutingDecision {
190 if (!matches(adapter))
191 return { nullptr, {} };
192 return { adapter, mac };
193 };
194
195 if (target[0] == 0 && target[1] == 0 && target[2] == 0 && target[3] == 0)
196 return if_matches(*NetworkingManagement::the().loopback_adapter(), NetworkingManagement::the().loopback_adapter()->mac_address());
197 if (target[0] == 127)
198 return if_matches(*NetworkingManagement::the().loopback_adapter(), NetworkingManagement::the().loopback_adapter()->mac_address());
199
200 auto target_addr = target.to_u32();
201 auto source_addr = source.to_u32();
202
203 LockRefPtr<NetworkAdapter> local_adapter = nullptr;
204 LockRefPtr<Route> chosen_route = nullptr;
205
206 NetworkingManagement::the().for_each([source_addr, &target_addr, &local_adapter, &matches, &through](NetworkAdapter& adapter) {
207 auto adapter_addr = adapter.ipv4_address().to_u32();
208 auto adapter_mask = adapter.ipv4_netmask().to_u32();
209
210 if (target_addr == adapter_addr) {
211 local_adapter = NetworkingManagement::the().loopback_adapter();
212 return;
213 }
214
215 if (!adapter.link_up() || (adapter_addr == 0 && !through))
216 return;
217
218 if (source_addr != 0 && source_addr != adapter_addr)
219 return;
220
221 if ((target_addr & adapter_mask) == (adapter_addr & adapter_mask) && matches(adapter))
222 local_adapter = adapter;
223 });
224
225 u32 longest_prefix_match = 0;
226 routing_table().for_each([&target_addr, &matches, &longest_prefix_match, &chosen_route](auto& route) {
227 auto route_addr = route.destination.to_u32();
228 auto route_mask = route.netmask.to_u32();
229
230 if (route_addr == 0 && matches(*route.adapter)) {
231 dbgln_if(ROUTING_DEBUG, "Resorting to default route found for adapter: {}", route.adapter->name());
232 chosen_route = route;
233 }
234
235 // We have a direct match and we can exit the routing table earlier.
236 if (target_addr == route_addr) {
237 dbgln_if(ROUTING_DEBUG, "Target address has a direct match in the routing table");
238 chosen_route = route;
239 return;
240 }
241
242 if ((target_addr & route_mask) == (route_addr & route_mask) && (route_addr != 0)) {
243 auto prefix = (target_addr & (route_addr & route_mask));
244
245 if (chosen_route && prefix == longest_prefix_match) {
246 chosen_route = (route.netmask.to_u32() > chosen_route->netmask.to_u32()) ? route : chosen_route;
247 dbgln_if(ROUTING_DEBUG, "Found a matching prefix match. Using longer netmask: {}", chosen_route->netmask);
248 }
249
250 if (prefix > longest_prefix_match) {
251 dbgln_if(ROUTING_DEBUG, "Found a longer prefix match - route: {}, netmask: {}", route.destination.to_string(), route.netmask);
252 longest_prefix_match = prefix;
253 chosen_route = route;
254 }
255 }
256 });
257
258 if (local_adapter && target == local_adapter->ipv4_address())
259 return { local_adapter, local_adapter->mac_address() };
260
261 if (!local_adapter && !chosen_route) {
262 dbgln_if(ROUTING_DEBUG, "Routing: Couldn't find a suitable adapter for route to {}", target);
263 return { nullptr, {} };
264 }
265
266 LockRefPtr<NetworkAdapter> adapter = nullptr;
267 IPv4Address next_hop_ip;
268
269 if (local_adapter) {
270 dbgln_if(ROUTING_DEBUG, "Routing: Got adapter for route (direct): {} ({}/{}) for {}",
271 local_adapter->name(),
272 local_adapter->ipv4_address(),
273 local_adapter->ipv4_netmask(),
274 target);
275
276 adapter = local_adapter;
277 next_hop_ip = target;
278 } else if (chosen_route && allow_using_gateway == AllowUsingGateway::Yes) {
279 dbgln_if(ROUTING_DEBUG, "Routing: Got adapter for route (using gateway {}): {} ({}/{}) for {}",
280 chosen_route->gateway,
281 chosen_route->adapter->name(),
282 chosen_route->adapter->ipv4_address(),
283 chosen_route->adapter->ipv4_netmask(),
284 target);
285 adapter = chosen_route->adapter;
286 next_hop_ip = chosen_route->gateway;
287 } else {
288 return { nullptr, {} };
289 }
290
291 // If it's a broadcast, we already know everything we need to know.
292 // FIXME: We should also deal with the case where `target_addr` is
293 // a broadcast to a subnet rather than a full broadcast.
294 if (target_addr == 0xffffffff && matches(adapter))
295 return { adapter, { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } };
296
297 if (adapter == NetworkingManagement::the().loopback_adapter())
298 return { adapter, adapter->mac_address() };
299
300 if ((target_addr & IPv4Address { 240, 0, 0, 0 }.to_u32()) == IPv4Address { 224, 0, 0, 0 }.to_u32())
301 return { adapter, multicast_ethernet_address(target) };
302
303 {
304 auto addr = arp_table().with([&](auto const& table) -> auto{
305 return table.get(next_hop_ip);
306 });
307 if (addr.has_value()) {
308 dbgln_if(ARP_DEBUG, "Routing: Using cached ARP entry for {} ({})", next_hop_ip, addr.value().to_string());
309 return { adapter, addr.value() };
310 }
311 }
312
313 dbgln_if(ARP_DEBUG, "Routing: Sending ARP request via adapter {} for IPv4 address {}", adapter->name(), next_hop_ip);
314
315 ARPPacket request;
316 request.set_operation(ARPOperation::Request);
317 request.set_target_hardware_address({ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff });
318 request.set_target_protocol_address(next_hop_ip);
319 request.set_sender_hardware_address(adapter->mac_address());
320 request.set_sender_protocol_address(adapter->ipv4_address());
321 adapter->send({ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff }, request);
322
323 if (NetworkTask::is_current()) {
324 // FIXME: Waiting for the ARP response from inside the NetworkTask would
325 // deadlock, so let's hope that whoever called route_to() tries again in a bit.
326 dbgln_if(ARP_DEBUG, "Routing: Not waiting for ARP response from inside NetworkTask, sent ARP request using adapter {} for {}", adapter->name(), target);
327 return { nullptr, {} };
328 }
329
330 Optional<MACAddress> addr;
331 if (!Thread::current()->block<ARPTableBlocker>({}, next_hop_ip, addr).was_interrupted()) {
332 if (addr.has_value()) {
333 dbgln_if(ARP_DEBUG, "Routing: Got ARP response using adapter {} for {} ({})",
334 adapter->name(),
335 next_hop_ip,
336 addr.value().to_string());
337 return { adapter, addr.value() };
338 }
339 }
340
341 dbgln_if(ROUTING_DEBUG, "Routing: Couldn't find route using adapter {} for {}", adapter->name(), target);
342 return { nullptr, {} };
343}
344
345}